Databases Reference
In-Depth Information
The framework proposed for static analysis is based on the use of
automata
to compare schemas, authorizations, and queries. The static analysis tries to
evaluate anything that does not depend on the specific XML instance and
that can be evaluated simply on the basis of the schema and of the access
control policy. Formally, an automaton is defined as follows.
Definition 2 ((Non deterministic finite state automaton)).
A
non
deterministic finite state automaton
(NFA) M is a five-tuple of the form
(
Ω, Q, Q
init
,Q
fin
,δ
)
where:
•
Ω is the alphabet;
•
Q is a finite set of states of M;
Q
init
•
⊆
Q is the set of
initial
states of M;
Q
fin
•
⊆
Q is the set of
final
states of M;
•
δ
:
Q
×
Ω
→
Q is the
transition function
of M.
The set of strings accepted by M, denoted L
(
M
)
, is the language of the au-
tomaton.
Given the definition of non deterministic finite state automaton, it is pos-
sible to build a NFA corresponding to an arbitrary XPath expression
r
that
does not contain conditions. The NFA accepts a path iff it matches with
r
.
This correspondence is possible since XPath is limited to
//
operator and
conditions are not considered while building the NFA. However, if an XPath
expression contains conditions, it is possible to partially capture their seman-
tics b
y building two NFAs for the given XPath expression
r
:an
overestimation
M
[
r
]andan
underestimation
M
[
r
]
. The former automaton is obtained by as-
suming all conditions satisfied, while the latter is obtained by assuming all
conditions not satisfied.
Static Analysis
The static analysis exploits the definition of automaton and is composed of
the following four steps.
Step 1:
Create schema automata
. Given a schema (DTD or XML Schema)
that a document should follow, a
schema automaton M
G
is built. This
automaton accepts all and only the paths that are allowed by the schema.
Step 2:
Create access control automata
. For each role (group) in the system,
a pair of automata is defined: an
underestimate acces
s-con
trol automaton
M
Γ
and an
overestimate access-control automaton M
Γ
. For each role,
this pair of automata should accept the set of paths to elements and/or
attributes that the role is authorized to access. It is necessary to define
both an underestimate and an overestimate automaton since conditions
may be added to correctly handle the propagation of positive and negative
authorizations along the XML tree. In particular, since the “denials take
precedence” principle is adopted, an element is accessible only if it is the
