2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing

Policy Description Language for Dynamic Access Control Models
Masaki HASHIMOTO† , Mira KIM† , Hidenori TSUJI† and Hidehiko TANAKA†† Graduate School of Information Security, INSTITUTE of INFORMATION SECURITY

2-14-1 Tsuruya-cho, Kanagawa-ku, Yokohama, 221-0835, Japan
Email: {dgs074105, mira, hide, tanaka}@iisec.ac.jp
After that, several researches about the policy description
language in recent years are presented.
1) Policy Description Problems in SELinux: SELinux
is the implementation of the Flask security architecture[4]for Linux kernel, mainly composed by the security server,
the object manager and the access vector cache. SELinuxevaluate the access control policy and forces access control
decisions by hooking system call functions which relate
to the access control in the kernel space. Because theauthorization can be evaluated with system call functions,
it is possible with SELinux that models like RBAC andDTE are achieved in the granularity of the system calllevel. However, describing ﬁne-grained access control rules
is highly difﬁcult for the human being on the other side,
though they must be described to control the accesses in theﬁne-grained granularity.
For instance, SELinux’s policy is composed by lining up
access control rules as the followings.

Abstract—Recently, dynamic access control models are proposed to restrict access domain appropriately in Multi-Layered
Defense. However, policy description languages proposed so far
can not express the models effectively in proper granularity. In
this paper, we propose a policy description language which candesignate precise condition for access control by using dynamic
status of application process. Using the proposed language, we
compose the policy of SELinux which is major implementationachieving Multi-Layered Defense and conﬁrm the advantagesof the proposed language by evaluating the response and theexpressiveness.
Keywords-Access control; Computer security;

I. I NTRODUCTION
In this paper, we propose a policy description language[1]which can describe the dynamic access control models to
expand the application range of Multi-Layered Defense. Ourlanguage expresses the dynamic status of processes as theground for authorizations, though languages proposed so far
describe access control rules based on the static information
like subjects, objects and operations.
Our language veriﬁes the information ﬂow of the futureor the past by reasoning, and uses the results as the access
control information for authorization. We present the implementation of the proposed language with Datalog[2], thesubset of Prolog[3], and explain about the concrete way ofdescribing the access control rules based on the future/past
information ﬂow and state designation of the processes.
As an experiment which demonstrates the validity of ourlanguage, we compose the policy of SELinux and evaluate
the response performance and the equality of the contentsof responses between original SELinux and our language.

allow acct t unconf ined t:f d use;allow acct t init t:process sigchld;allow acct t init t:process signull;allow acct t rpm t:f d use;
In the SELinux’s policy, one authorization rule is expressed in each line. The ﬁrst item “allow” in each line
shows the line as a rule to permit some action. The second
item designates the information of the subject which thisrule is applied to, and the information of the object andoperation are designated for the rest. The rules by the syntax
are enumerated over the 40,000 lines in the simplest edition
policy for the individual users in the SELinux.
As a result, even if each rule can be understood intuitively,
it is difﬁcult to predict what occurs actually with the policy
constructed as the collection of those lines. Additionally,
the situation must be more difﬁcult in the near future,
because the techniques have been already proposed which
expand the application range of the mandatory access control
mechanism to the application layers and other networked
systems from the operating system layer of a single system.
2) Recent Researches: SDSI[5] and SPKI[6] are theframework to evaluate reliability between the system byexchanging a certiﬁcate. SDSI uses the predicate of “speaksfor” to building the logic architecture and SPKI can encode
the predicates in the declaration as a tag. Furthermore, they

II. R ELATED W ORKS AND M OTIVATIONIn this chapter, we show the related works and explain
the motivation of our research. First, we show the policyof SELinux as an actual example of policy description
problems, then recent researches which focus policy descriptions are presented. Finally, we explain the purpose of ourresearch.
A. Related Works
In this section, we show the outline of SELinux as a preceding research which achieves Multi-Layered Defense ﬁrst,
and explain the problems related to the policy descriptions.
978-0-7695-3929-4/09 $26.00 © 2009 IEEE
DOI 10.1109/DASC.2009.129

37

as a result of the improvement in expression, because moreaccess control rules can be expressed in less descriptions.

has the characteristics to express a policy as an English
writing, but SDSI can not deﬁne and use the corresponding
predicate to the applications because it can use only speaksfor as a predicate and SPKI can not deﬁne the suitablepredicate to the applications easily because of the restriction
from the tags though it uses more than one predicate.
Though the various conditions which are necessary for theauthorization decision can be deﬁned, as for PolicyMaker[7]and KeyNote[8] as well, the subject which can not deﬁne
the optional predicate corresponding to the application is reported in the same way. SecPAL[9] is the policy description
language by the constraint logic programming and demands
for access are authorized ofﬁcially when query to the setof the clauses succeeds. The syntax of SecPAL is close to
the natural language, and semantics is composed by three
deduction rules. And it can express many access control
models by supporting various expressions like the delegationof authority, the negation and the recursion, but it focuseson the control of more than one management domain by
the easy and clear policy description technique, hence, theexamination for the dynamic elements is not the main target.

III. P OLICY D ESCRIPTION L ANGUAGE
In this chapter, we present the basic design of the proposed language. First, we deﬁne the syntax and semantics
for the declarative statement and authorization query of
the policy. Next, we show several deductive rules to apply
to them. The proposed language adopts the syntax andsemantics to be similar to English which is intuitively easy
to understand, and deductive rules are very simple. The
predicate logic is the foundation of the our language.
A. Syntax and Semantics
We compose a policy as a set of the declarative statement(DS: D ECLARATIVE S TATEMENTS) and access control decisions are decided by Q (authorization queries) describedin the following syntax. Accesses are permitted or deniedby that answer.
DS ::= Policy Speciﬁes f act if f act1 ,..., f actn
Q ::= Policy Speciﬁes f act | ∃x(Q)B. Motivation of Our Research

E ::= x | A
T ::= claim E1 for E2 in E3
V ::= is authorized to T | will be authorized to T
| has role E | has type E| has state E | role trans Ef act ::= E V
claim ::= allow | auditallow | dontaudit| neverallow | transition

In this paper, we propose the expressive policy description
language which supports dynamic Multi-Layered Defensewith ﬁne-grained granularity by using the process status
information and the results of information ﬂow veriﬁcation
as the ground of authorizations. Our language deﬁnes layercomposition dynamically by evaluating values to change
during the system operations in addition to them, and aim to
express the access control models of ﬁne-grained granularity
beyond before. As for the description of the access control
models based on the dynamic information, recent researches
are not enough because they focuses in the technique to express delegation of authority brieﬂy between the several domains which are managed by own policies. Paying attention
to this point, our proposed language gives the authorization
decision to mandatory access control mechanism based on
the process status informations and the future and/or past
information ﬂow, supporting access control models which
consider the dynamic conditions.
For instance, it can be expected to give the least authority
set to the agent process for the other system corresponding
to the status of tasks, or to exclude the future rivalry ofauthority set between tasks in advance, and so on. And, byverifying past information ﬂow, the authorization decision
can be changed ﬂexibly whether the process pass throughthe trusted authentication mechanism which is speciﬁedby policy. Furthermore, it becomes possible to prevent the
information ﬂow which does not be intended by controlling
authorizations based on the dynamic status of the speciﬁc
process and the system, such as ”Disabled” and ”Polluted”.
Additionally, it can be expected to reduce the difﬁculty ofthe policy description shown with the example of SELinux

Bold forms represent ﬁxed numbers, predicates and variables which do not inﬂuence the semantics. Policy shows
the subject which deﬁnes each DS, and Policy Speciﬁed isalways ﬁxed in this syntax. f acts shows the actual contentsof the access control rule and f act1 ,... f actn are conditional
facts. As for Q, the conditinal clause of DS was removed
and Q express the conﬁrmation of the existence of the DS
and constants are substituted for variables as passible.
E denote constants and variables. Constants means subjects or objects for authorization and they represent processes, domains, roles, and so on. We designate them asalphabetical one character in the capital letter of italics fonts.
Variables are restricted its domain within the domain of
constants. Therefore, f acts and DS are not substituted forvariables. T denote objects and operation for access in the
DTE model; E1 for the contents of the operation, E2 forthe object classes and E3 for the types of the object. And
claim designates the kind of authorization. has role, hastype and has state express the attributes which the subject
holds respectively. role trans designates whether the subject
could transit to the role designated with objects. claim isequivalent to the predicate of the f act and they designate
the kind of permission.

38

We deﬁne the semantics of Q by the relations designatedby P, θ  Q in the following. P denotes the policy, a set ofDS. θ is the mapping function which maps the variables tothe constants or to the other variables and vars(X) designates
the variable clause which exists in the clause X. We interpret
Q as access control decision by the truth evaluation.
P, θ  Policy Speciﬁes fact
iff P, θ |= Policy Speciﬁes factθ,and dom(θ) ⊆ vars(Policy Speciﬁes fact)
P, θ− x  ∃x(Q) iff P, θ  Q
B. Deductive Rules
In the proposed language, it is possible to reduce theamount of description of policy by using the deductive rules
and the formal veriﬁcation of information ﬂow expressed in
the rest becomes possible.
RULE (a)(Policy Speciﬁes fact if f act1 , ..., f actk ) ∈ P
P |= Policy Speciﬁes f acti θ for all i ∈ {1..k}vars(factθ)=˙ 0̇
P |= Policy Speciﬁes factθ
RULE (b)P |= Policy Speciﬁes A has type B
P |= Policy Speciﬁes B will be authorized to C
P |= Policy Speciﬁes A will be authorized to C
RULE (c)P |= Policy Speciﬁes A has role B
P |= Policy Speciﬁes B has type C
P |= Policy Speciﬁes A has type C
RULE (d)P |= Policy Speciﬁes A has role B
P |= Policy Speciﬁes B role trans C
P |= Policy Speciﬁes A has role C
RULE (e)P |= Policy Speciﬁes A has type B
P |= Policy Speciﬁes B will be authorized
to transition C for D in E
P |= Policy Speciﬁes A has type C
RULE (a) deduces the statement with no variables fromthe statement with conditional clauses and θ which makes
each fact in the conditional clauses vars(factθ)=˙ 0̇. RULE (b)deduces the statement which designates A will be authorized
to C from the statement expressing A has type B and thestatement expressing B will be authorized to C. RULE (c)deduces the statement which designates Type C is assigned
to A from the statement expressing Role B is assigned to
A and the statement expressing Type C is assigned to Role
B. RULE (d) deduces the statement which designates Role
C is assigned to A from the statement expressing Role B is
assigned to A and the statement expressing Role B transit toRole C. RULE (e) deduces the statement which designates
Type C is assigned to A from the statement expressing Type
B is assigned to A and the statement expressing Type C isassigned to the target objects when Type B generates Class
D in Type E.
IV. I MPLEMENTATIONIn this chapter, we present the implementation of the
proposed language using Datalog and explain actual descriptions of the access control models based on the dynamic
elements. We treat the authority set which will be able tobe held in the future or the past as the information ﬂow.
A. Implementation of Proposed Language in Datalog
We implement the description language by using Datalog,
the subset of Prolog. Each declarative statement by the
proposed description technique is translated as a clause of
the Datalog program, and authorization decision sentence isevaluated by tabled resolution as an query for the program.
First, we deﬁnes the term of Datalog by followings. Literal
L has the name of the predicate and a series of arguments.
An argument takes constant or variable. A clause is written
as L0 ← L1 , ..., Ln and composed by one head literal in
the left part of “←” and the lists of the body literals in theright-hand side. Each predicate of the proposed description
technique translated into the Datalog literal as follows. The
left part of “→” is the description by the proposed language
and right-hand side is a Datalog literal after the translation.
Policy Speciﬁes E1 is authorized to claim E2 for E3 in E4→ isAuthedto(claim, E1 , E2 , E3 , E4 )Policy Speciﬁes E1 will be authorized to claim E2 for E3 in E4→ willbeAuthedto(claim, E1 , E2 , E3 , E4 )Policy Speciﬁes E1 has role E2 → hasRole(E1 , E2 )Policy Speciﬁes E1 has type E2 → hasType(E1 , E2 )Policy Speciﬁes E1 has state E2 → hasState(E1 , E2 )Policy Speciﬁes E1 role trans E2 → roleTrans(E1 , E2 )The predicate of f act in the declarative statement istranslated as the predicate of the Datalog literal, and thearguments of f act are translated as arguments of the Datalog
literal with translating technique in the proposed language.
And as for the declarative statement with the conditionalclause as well, we use conditional clause as the body of the
Datalog clause after the translation to Datalog literal by theabove technique.
B. Veriﬁcation of Information Flow
In this section, we present the veriﬁcation of the information ﬂow by the state designation in the proposed language
and show the actual description of access control using theresult of it.
In the proposed language, we verify the information ﬂow
in the future seen from one moment of the process using thereasoning with the embedded predicate will be authorized

39

to. Additionally, we describe an access control rule basedon the veriﬁcation of the information ﬂow which existed in
the past, acquiring dynamically from the system, using thethe embedded predicate has state with user-deﬁned state bywhich process state designation should be made possible.
We verify the information ﬂow of the future and the pastwith the following process.
As for the future information ﬂow, DS is veriﬁed byevaluating the authorization decision sentence for which theembedded predicate will be authorized to was used. The
past information ﬂow is deduced by applying the rules (b)∼ (e) in the section III-B recursively to the authorization
decision sentence includes a variable clause.
For instance, we assume the DS which keeps the declarative statement of the following 11 rules and show the process
which deduces the future information ﬂow from a certain
authority set, denoting U for user, R for role, T for type, C
for object class and AV for operation.
Policy Speciﬁed UA has role RA
Policy Speciﬁed UB has role RB
Policy Speciﬁed UC has role RC
Policy Speciﬁed RB role trans RC
Policy Speciﬁed RA has type TA
Policy Speciﬁed RB has type TB
Policy Speciﬁed RC has type TC
Policy Speciﬁed TA is authorized
to transition TC for C in TB
Policy Speciﬁed TA is authorized
to allow AVA for C in TB
Policy Speciﬁed TC is authorized
to allow AVB for C in TD
Policy Speciﬁed TC is authorized
to allow AVA for C in TB
IF TC has state passedtdof HBAC and execution history based access control can be
described using the states of the process and the system byacquiring “process was started.”, “process was ﬁnished.”, andso on dynamically and it can be expected that the Chinese
Wall model can be described efﬁciently using the state of“The resource of a certain domain was read once.”
V. D ISCUSSION
In this chapter, we present the results of the experiment
which evaluates the advantages of the proposed language.
First, we show the outline of the experiment system andprograms. Then, we compare the response performance
to judge authorization with the proposed language andSELinux, examining the results considering the impact of theaccess vector cache (AVC). And, we conﬁrm the contentsof the responses and demonstrate that proposed language
can compose the policy of SELinux equivalently when thedefault policy of actual SELinux is constructed by the
proposed language. Finally, we compare the features which
can be used for the description about the proposed language
and SELinux to evaluate the expressiveness qualitatively.

(1)
(2)
(3)
(4)
(5)
(6)
(7)

A. Outline of Experiment System
The experiment system is implemented on the computerof the Pentium 4 (3.0GHz) and the memory 1GB and
OS is Debian/GNU Linux added the packages related to
SELinux. The versions of main softwares are libselinux1(2.0.65-5), selinux-basics (0.3.5) and selinux-policy-default(2:0.0.20080702-6).
With the experiment system, we change the source related
to SELinux so that we can acquire the address of sidtab
and avtab which exist in the kernel space, and get all thecontents of the table from the pointer to the acquired hashlayout. Then, we change the source to call the function
context struct compute av() from the outside of kernel,
and measure processing time except for the translation from
SID to the security context. Furthermore, we describe all theelements on avtab by the proposed language and compose
the policy database using Datalog from the descriptions andprepare the queries by the combination of the source context,
the target context and the target class.
We use the RDTSC instruction of x86 for the measurement of the time and devise not to read TSC of another coresetting the CPU afﬁnity ﬂag.

(8)
(9)
(10)
(11)

With this example, when the future information ﬂow of UA
is veriﬁed, UA will be authorized the authority set of AVA
of C in TB and AVB of C in TD by deducing with the rules(1) (5) (8) and (9). And when the future information ﬂow
of UB is veriﬁed, UB will be authorized the authority set
of AVB of C in TD by deducing with the rules (2) (4) and(10). Similarly in the case of UC , the authority set of AVB
of C in TD will be authorized by deducing with the rules(3) (7) and (10). For the veriﬁcation of the past information
ﬂow, we deﬁne the state passedtd and give the truth value of“whether a certain subject accessed TD ” dynamically fromthe system. With this example again, ﬁxed authority set for
TB is authorized TC by evaluating the rules (2) (7) and (11)which designate TC accessed TD in the past.
In the proposed language, the information ﬂow can be
veriﬁed exhaustively by applying deductive rules recursively
even when the transition of the roll and the type piles up
to many times. Additionally, we can describe various access
control rules ﬂexibly in the proposed language using theuser-deﬁned state. For example, the access control models

B. Evaluations of Response Time and Contents
In this section, we conﬁrm the response performance andthe equality of the contents of response describing the default
policy of SELinux in the proposed language. In the experiments, we call the function context struct compute av()by using all the elements of sidtab at the round robin to thesecurity class, and measure the time when the acquisitionof AV as response. After that, we conﬁrms the equalityof the response contents, comparing the responsed AV of
40

300
250

300

Frequency

100

150

200

250
200
150

Frequency

50

100

0

50
0
0

50

100

150

1000

200

Figure 1.

2000

3000

4000

5000

6000

7000

Responce Time (μs)

Responce Time (μs)

Figure 2.

Response Time of SELinux

Response Time of Proposed Language with Datalog

SELinux could be expressed equivalently in the proposed
language. On the other hand, the response time of the
proposed language was inferior greatly for the query of
the same contents. We guess the inferior is caused by
the difference of the implementing form and the searchalgorithm of the policy database. About the implementing
form, the policy database and the evaluation functions are
implemented inside the kernel space for SELinux, while theproposed language with Datalog implements them in theuser space. Hence, for improvement, the processing system
of Datalog need to be set inside the kernel and the execution
steps concerned with the context switch can be reduced.
Additionally, about search algorithm, we can guess that
this difference is reduced because almost all queries areprocessing by the cache mechanism called AVC in actual
operations, and it is said generally the AVC hit rate of
SELinux is over 99%.

context struct compute av() and the result of querying
the Datalog with the combination of the same source context,
the same target context and the same target class.
We show the result of measurement of the response performance about SELinux and the proposed language in ﬁg.1
and ﬁg.2. Each ﬁgure shows the frequency distributions fromthe result of the experiments for 1,000 elements choosed at
random from 13,803,559 elements of all sid which makequeries combined at the round robin. The x-axis designates
the response time from a demand for a authorization decision
to acquisition of AV, and the y-axis designates the frequencyof each response time.
As a result, the response times of SELinux were minimumof 2.775μs, maximum of 177.2μs and median of 11.44μs.
And the response times of proposed language with Datalog
were minimum of 1,275μs, maximum of 6,485μs and median of 4,737μs. Beyond a two-digit number of difference
between SELinux and proposed language was conﬁrmed
from the experiments. As for the equality of contents of
responses, for 13,803,559 queries, same AV of 2,629 acquired and no AV of 13,281,253 acquired which mean thecontents of response was the same in SELinux and the
proposed language. As a result, about 96% responses wereequal in the contents of response. And, the rest of responses
were the error by querying to the context which was formed
dynamically at the time of the systems operation.
By the experiments, it was demonstrated that all thecontents of responses with the same query was corresponded
between SELinux and the proposed language with Datalog
except for the errors, and conﬁrmed that the policy of

C. Evaluation of ExpressivenessIn this section, we compare the features of the proposed
language and SELinux, evaluating the expressiveness qualitatively. Three functions used for policy descriptions areevaluated. Table I is the results.
The ﬁrst function is to make the rule enable/disable basedon some conditions. This means the result of not only
searching the existence of the queried statement in the policy
but also evaluating the various conditions given to each ruledecide the authorization decision. The expression of ﬂexible
authorization decisions using the second function and thethird function is achieved by using the ﬁrst function. For
example, by the former technique, rules become the forms

41

```
```Language```
Features`

1. Enabling/Disabling the rules based on the condition
2. Treating the system or process state as the condition
3. Treating the future/past information ﬂow as the condition

SELinux Policy

Proposed Language


X
X

◦
◦
◦

Table IC OMPARISON THE F EATURES OF D ESCRIPTION

and the formal proof of the proposed language are the future
works.

of “allow the process A to read the resource B.” On theother hand, by the latter technique, rules become the formsof “If the condition C is true, allow the process A to readthe resource B.”, introducing condition evaluation for therule, therefore, the rules are enable/disable depending on
the results of the evaluation of the condition.
The second function is to describe systems and processes
states as a condition and the state transition system can be
expressed efﬁciently by this function. Furthermore, we candescribe the authorization rules considering the transaction
processing states, the damage states, and the time states,and so on by this function. For example, the rules likefollowings can be expressed; “If the process A and B is instate ‘ﬁnished’, allow the process C to read the resource
D.” for the transaction processing state, “If the process
A is in state ‘polluted’, deny the process B to read theresource C-F.” for the damage states, “If the system is instate ‘AfterDate20090815’, allow the process A to read theresource B.” for the time states.
The third function is to describe the result of information
ﬂow veriﬁcation as a condition, and the rules based on
the temporal logic can be expressed by this function. For
example, the rules like followings can be expressed; “If it
would be authorized to write the resource A in the future,reading of the resource B can not be authorized.”, “”If it has
writing authority to the resource A from now on, reading to
the resource B will be recognized.”, “If the resource A had
been read in the past, writing to the resource B would not
be authorized.”

ACKNOWLEDGMENT
The authors are grateful to the anonymous referee for her/his
valuable comments.
R EFERENCES[1] “Trusted computer systems evaluation criteria,” DoD Computer
Security Center, Fort Meade, MD, Tech. Rep. CSC-STD-00183, August 1983.
[2] S. Ceri, G. Gottlob, and L. Tanca, “What you always wanted
to know about datalog (and never dared to ask),” IEEE Transactions on Knowledge and Data Engineering, vol. 1, no. 1, pp.
146–166, Mar 1989.
[3] D. H. D. Warren, L. M. Pereira, and F. Pereira, “Prolog the language and its implementation compared with lisp,” inProceedings of the 1977 symposium on Artiﬁcial intelligenceand programming languages. New York, NY, USA: ACM,
1977, pp. 109–115.
[4] R. Spencer, S. C. Corporation, S. Smalley, P. Loscocco, N. S.
Agency, and M. H. D. Andersen, “The ﬂask security architecture: System support for diverse security policies,” in in
Proceedings of The Eighth USENIX Security Symposium, 1999,
pp. 123–139.
[5] M. Abadi, “On sdsi’s linked local name spaces,” J. Comput.
Secur., vol. 6, no. 1-2, pp. 3–21, 1998.
[6] C. Ellison, B. Frantz, B. Lampson, R. Rivest, B. Thomas,
and T. Ylonen, SPKI Certiﬁcate Theory. United States: RFC
Editor, 1999, ch. 2693.

VI. C ONCLUSION[7] M. Blaze, J. Feigenbaum, and M. Strauss, “Compliance checking in the policymaker trust management system,” in FC’98: Proceedings of the Second International Conference on
Financial Cryptography. London, UK: Springer-Verlag, 1998,
pp. 254–274.

In this paper, we proposed a policy description language
which can describe dynamic access control models in addition to the existent models like RBAC and DTE to prepare
for the application range expansion of Multi-Layered Defense. We showed the description technique and some deductive rules which make each access control rule effective evaluating the dynamic information. And we implemented the
proposed language using Datalog, and explain the concrete
way of describing the access control rule by the proposed
technique which is based on the future/past information ﬂow
and state designation of the system and the process. Finally,
we conﬁrmed the advantages of the proposed language by
evaluating response times, response contents and expressions
by the experiments. The improvement of the performance[8] M. Blaze, J. Feigenbaum, and A. D. Keromytis, “Keynote:
Trust management for public-key infrastructures (position paper),” in Proceedings of the 6th International Workshop on
Security Protocols. London, UK: Springer-Verlag, 1999, pp.
59–63.
[9] M. Becker, C. Fournet, and A. Gordon, “Design and semantics of a decentralized authorization language,” in CSF ’07:
Proceedings of the 20th IEEE Computer Security Foundations
Symposium. Washington, DC, USA: IEEE Computer Society,2007, pp. 3–15.

42