Houari Mahfoud
email: .mahfoud@inria.fr

Abdessamad Imine
email: abdessamad.imine@inria.fr

Secure Querying of Recursive XML Views: A Standard XPath-based Technique

Keywords: Queries Rewriting, XML Access control, XML views, XPath Réécriture des requêtes, Contrôle d'accès pour documents XML, Vues XML, XPath

Most state-of-the art approaches for securing XML documents allow users to access data only through authorized views defined by annotating an XML grammar (e.g. DTD) with a collection of XPath expressions. To prevent improper disclosure of confidential information, user queries posed on these views need to be rewritten into equivalent queries on the underlying documents. This rewriting enables us to avoid the overhead of view materialization and maintenance. A major concern here is that query rewriting for recursive XML views is still an open problem.

To overcome this problem, some works have been proposed to translate XPath queries into nonstandard ones, called Regular XPath queries. However, query rewriting under Regular XPath can be of exponential size as it relies on automaton model. Most importantly, Regular XPath remains a theoretical achievement. Indeed, it is not commonly used in practice as translation and evaluation tools are not available. In this paper, we show that query rewriting is always possible for recursive XML views using only the expressive power of the standard XPath. We investigate the extension of the downward class of XPath, composed only by child and descendant axes, with some axes and operators and we propose a general approach to rewrite queries under recursive XML views. Unlike Regular XPath-based works, we provide a rewriting algorithm which processes the query only over the annotated DTD grammar and which can run in linear time in the size of the query. An experimental evaluation demonstrates that our algorithm is efficient and scales well.

Introduction

XML has become the standard of representation and exchange of data across the web. With this emergence, a challenge is raised with regards to the security of XML documents whose content is available to one or more users based on their access privileges. First access control models for securing XML have been proposed in [7,[START_REF] Murata | Xml access control using static analysis[END_REF][START_REF] Vercammen | Query translation for xpathbased security views[END_REF]. However, these models suffer from various limitations. They can cause leakage of sensitive information [7], focus on the annotation of the entire XML data to deal with the static analysis limitations [START_REF] Murata | Xml access control using static analysis[END_REF], or based on costly schemes for rewriting user queries [START_REF] Vercammen | Query translation for xpathbased security views[END_REF].

To avoid these problems, the notion of XML security views was studied by Fan et al. [4]. We briefly review the main principle of the XML security viewbased approaches. We start by the fragment of XPath, called downward class, where the axes are limited to child and descendant axes. We use this fragment since it is commonly used in practice. A conform XML document T w.r.t a DTD D (i.e. T is an instance of D), can be queried simultaneously by different users. For each class of users a security view is defined by annotating D with some access conditions to specify the (in)accessible element types of the DTD. The annotated version of D is later sanitized by removing the inaccessible element types which results in a DTD view D v . Then the security view is defined as V =(D v , σ) where D v is given to the users, which describes accessible data they are able to see, and σ is a function used to extract for each XML document T conforms to D, its view T v representing only authorized data of the users. Each query over the view T v is translated into an equivalent one in order to be evaluated over the original data T.

Problem Statement. The problem of XPath queries rewriting studied in this paper is defined as follows:

Given a DTD D, an XML security view V =(D v , σ), and an XPath query Q over D v . The rewriting problem consists in defining a rewriting function R that computes another XPath query R(Q) over the original document D such that: for any instance T of D and its view T v computed w.r.t V , the evaluation of Q on T v yields the same result as the evaluation of R(Q) on T.

Most of the security view-based approaches of XPath queries rewriting deal only with non-recursive DTDs [4,9,[START_REF] Rassadko | Policy classes and query rewriting algorithm for xml security views[END_REF]. A DTD is recursive iff at least one of its elements is defined (directly or indirectly) in terms of itself. Note that recursive DTDs often arise when specifying medicals data and the problem of query rewriting is more intriguing in this case. A security view is recursive, if its view D v is recursive.

For each pair of element types A and B in the DTD, the σ function is an XPath expression denoting the set of paths to reach an element B from an element A in the DTD view (where some element types are hidden between A and B and generated by σ). However, in the case of recursive DTDs, the σ function is not computable since there may be an infinite set of paths from A to B and the notion of security view (as defined above) cannot be used in queries rewriting. That is why some authors [5,8] resort to the use of Regular XPath to avoid this problem. However, Regular XPath remains of theoretical use since no evaluation tools have been provided for practical use of this langage.

Inria

To the best of our knowledge, no practical approach exists for answering queries under recursive XML security views. Accordingly, the XPath query rewriting remains an open issue.

Contribution. Our main contribution is making possible the query rewriting for recursive XML security views using only the expressive power of the standard XPath. We show that extending the downward class of XPath queries with some axes and operators is sufficient to deal with the query rewriting under recursion (without the need of the Kleene star or the translation from XPath to Regular XPath).

Intuitively, for a query Q based on the downward class of XPath, our rewriting solution consists in computing another query Q ′ = R(Q) using an extended fragment of XPath in such a way for any instance T of D and its view T v (computed w.r.t D v ) the evaluation of Q on T v gives the same result than evaluating Q ′ on T.

We provide a linear rewriting algorithm for arbitrary views (recursive or not) which, unlike Regular XPath-based works (relying on Mixed Finite Automata [5]), consists only in processing the query over the annotated DTD to produce the equivalent query on any valid instance of the original DTD. We validate our solution with a performance evaluation which shows that our rewriting algorithm is efficient and scales well. Lastly, we show how our proposed solution can be extended to deal with a large fragment of XPath (including upward-axes) and to go beyond some limitations of existing access control specification languages.

Related Work. We briefly discuss two approaches of access control policy enforcement for XML documents with or without XML grammar.

In [7] authors propose a formal model to specify access control for XML documents independently of the DTD. The policy rules definition is based on XPath and each query is rewritten by adding a predicate access (which represents all accessible data) to that query. We use the same predicate access principle in our rewriting approach. However, inference of sensitive information can be detected since only the last subquery is controlled among all subqueries parsed by the query. To overcome this problem, we improve the method given in [7] by attaching a predicate access to each entity (element/attribute) parsed by the query.

Vercammen [START_REF] Vercammen | Query translation for xpathbased security views[END_REF] proposes a new method based on the intersection and union of XPath queries to avoid the problem of information leakage. The policy rules are translated to a single query which stands for all accessible data; this query is incorporated by intersection with each query requested over the user XML document view. However, this approach yields the same performance than the materialization of this view.

Other access control approaches are based on the notion of security views and the query rewriting principle. Fan et al. [4] propose the notion of security view by the annotation of a regular non-recursive DTD. The use of only downward class of XPath queries allowed them to achieve more precise query rewriting, i.e. computing all possible paths connecting each two adjacent elements in the query, which provides practically performance gains for the query evaluation. A view derivation algorithm is proposed to compute the DTD view, w.r.t. the access conditions, and an optimization step is also done over the rewritten query. However, to keep the DTD view regular, an inaccessible element may be replaced with anonymous element dummy which can be source of security breaches. In [9,[START_REF] Rassadko | Policy classes and query rewriting algorithm for xml security views[END_REF], authors refine the Fan's model by eliminating dummies, extending the class of XPath queries with upward -axes and with a novel notion of security views. Different types of policies are also discussed. These works can deal only with non-recursive DTDs. They are inapplicable to recursive DTDs because the description of paths connecting two element types may be infinite.

Unlike the XPath query rewriting over non-recursive DTDs, the problem posed by the recursion has not received a more attention. Authors of [5] extend the principle proposed in [4] with a translation of XPath queries to Regular XPath and propose a first algorithm for evaluating Regular XPath over XML data. In [8], a more generalized rewriting approach has been studied by dealing with restrictions on the class of queries and DTD types. The defined accessibility function is based on the Kleene star. It should be noted that the Kleene star cannot be expressed in the standard XPath.

Although the query formulation and rewriting on Regular XPath is more expressive than the standard XPath, we cannot find any practical system for both proposed approaches1 . Consequently, the need of a rewriting system of XPath queries over recursive XML security views remains an open issue.

Plan of the paper. The rest of the paper is organized as follows. Section 2 presents formally the query rewriting problem for recursive views, and sketches our solution to deal with this problem. In Section 3, we give the ingredients of our access control specification. Our rewriting approach is detailed in Section 4. Section 5 presents how our approach can be extended to consider a large fragment of XPath and used to overcome some limitations of existing access control approaches. An implementation issue is presented in Section 6. Finally, we conclude this paper in Section 7.

Formal Problem Statement

In this section we present the query rewriting problem for recursive views, and sketch our solution to deal with this problem.

Preliminaries

We briefly review some notions of Document Type Definitions (DTDs) and the class of XPath Queries most used in practice.

DTDs. Without loss of generality, we represent a DTD by a triple (Ele, P, root), where Ele is a finite set of element types, root is a distinguished type in Ele (called the root type) and P is a function defining element types such that for any A in Ele, P(A) is a regular expression α defined with:

α := str | ǫ | B | α","α | α"|"α | α*
where str denotes the text type PCDATA, ǫ is the empty word, B is an element type in Ele, and finally α","α, α"|"α, and α* denote concatenation, disjunction, and the Kleene closure respectively. We refer to A → P (A) as the production of A. For each element type B occurring in P(A), we refer to B as a subelement type (or child type) of A and to A as a superelement type (or parent type) of B. If an element type A is defined in term of an element type B directly (B is subelement type of A) or indirectly, then A is an ancestor type of B and B is a descendant type of A. The DTD is said recursive if some element type A is defined in terms of itself directly or indirectly.

We use the graph representation to depict our DTDs where dashed edges represent disjunction.

XML Documents. We model an XML document with an unranked ordered finite node-labeled tree, also called XML Tree. Let Σ be a finite set of node labels, an XML tree T over Σ is a structure defined as [START_REF] Cate | The complexity of query containment in expressive fragments of xpath 2.0[END_REF]:

T = (N, R ↓ , R → , L) where N is the set of nodes, R ↓ ⊆ N × N is the parent-child relation, R → ⊆ N × N
is a successor relation on (ordered) siblings, and L : N → Σ assigns a label to each node.

An XML document T conforms to a DTD D if the following conditions hold: (i) the root of T is the unique node labeled with root; (ii) each node in T is labeled either with element type A, called A element, or with str, called text node; (iii) for each node n of type A and with k ordered children n 1 , ..., n k , the word L(n 1 ), ..., L(n k ) belongs to the regular language defined by P(A); (iv) each text node carries a string value (PCDATA) and is the leaf of the tree. We call T an instance of D if T conforms to D. In the DTD instances depicted in our figures, we use X i to distinguish between elements of the same type X.

XPath Queries. We introduce the downward class of XPath queries referred to as X and defined as follows: where label refers to element type in Ele or * (that matches all labels), ∪ stands for union, c denotes text constant, axis is the XPath axis relation, and ↓, ↓ + denote child and descendant axis respectively, and finally qual is called an XPath qualifier (predicate or filter ) which can be a text content comparison, an XPath query, or a boolean expression (using boolean operators such as: and, or, not).

Let n be a node in an XML tree T. The evaluation of an XPath query p at node n, called context node n, results in a set of nodes which are reachable from n with p, denoted by n〚p〛. A qualifier q is said valid at node context n, denoted by n q, iff one of the following conditions holds: (i) q is given by p=c and there is at least one element reachable from n with p which has c as text content; (ii) q is an XPath query and n〚q〛 is nonempty; (iii) q is a boolean expression (e.g. not(p)) and it is evaluated to true at n.

XML Access Control Model

We define below some concepts of security specifications and XML security views as initially presented in [4,9]. Security Specifications. Given an XML document T conforms to a DTD D.

For each class of users some access privileges may be defined to restrict access to sensitive information on T. Thus, an access-control specification language is defined to specify what elements in T the users are granted, denied, or conditionally granted access to. An access specification in this language is defined as follows:

Definition 2.1 An access specification S is a pair (D,ann ) consisting of a DTD D and a partial mapping ann such that, for each production A → P (A) and each element type B in P(A), ann(A,B), if explicitly defined, is an annotation of the form:

ann(A,B) := Y | N | [Q]
where [Q] is a qualifier in our XPath fragment X . A special case is the root of D for which we define ann(root)=Y by default.

The specification values Y, N, and [Q] indicate that the B children of A elements in an XML document conforms to the DTD D are accessible, inaccessible, or conditionally accessible respectively. If ann(A,B ) is not explicitly defined, then B inherits the accessibility of A. On the other hand, if ann(A,B ) is explicitly defined then B may override the accessibility inherited from A. A text node is accessible only if its parent element is accessible. For an element node n of type B with parent node of type A, we say that n is concerned by an annotation if ann(A,B )=value exists, moreover, this annotation is valid at n if value=Y, or value=[Q] and n Q.

Security Views. To enforce an access specification, a security view is defined to compute for each document T conforms to a DTD D: (i) an instance view T v containing only accessible data; and, (ii) a DTD view D v which describes schema of all accessible data. Both documents T v and D v are seen only by authorized users.

More formally, let S =(D, ann) be an access specification. A security view for S is defined as a pair V =(D v , σ) where: (i) D v is a view of D computed by eliminating inaccessible element types2 from D, according to annotations given in S ; (ii) σ is a function used to extract accessible data in such a way that for each pair of types A and B where B occurs in P(A) in D v , the σ(A, B) is an XPath query (described in fragment X ) defining paths to reach element nodes B from an element node A in the original document T conforms to D. It should be noted that function σ is hidden from the users. A security view

V =(D v , σ) is said recursive if its D v is recursive.

DTD Recursion Problem

Most existing approaches [4,9,[START_REF] Rassadko | Policy classes and query rewriting algorithm for xml security views[END_REF] for securing access to XML documents are based on the notion of security view. Given a security view V =(D v , σ), the query rewriting principle is applied to translate each XPath query p over D v to another one p t over the original DTD D, such that for any instance T of D (T v of D v resp.), p t over T yields the same answer as p over D v (i.e. p t (T ) = p(T v )) 4 . Thanks to query rewriting we do not need to materialize view T v and its major problem namely the view maintenance. However, only non-recursive DTDs are considered. The security view as specified before cannot be applied in the case of recursive DTDs. To illustrate this problem we give the following example:

Example 2.2 For the query ↓ + ::H over the DTD given in Figure 2(a), we should enumerate all the paths from the root which give an accessible element H (as done in [4]): /root/A[q]/(B ∪ D/E/G)/H. However, the task is complicated in the case of recursion. With the same query over the DTD in Figure 2(b), the function σ used to extract accessible data, cannot be defined, e.g. σ(D, E) can be E, F/G/D/E, or F/G/D/F/G/D/E etc. Then σ(D, E) leads to infinitely many paths and cannot be defined in X . Moreover, the rewriting of the query ↓ + ::H is equivalent to the following regular expression: Since the Kleene Star (denoted by *) is not part of the standard XPath and cannot be expressed as outlined in [START_REF] Cate | The expressivity of xpath with transitive closure[END_REF][START_REF] Cate | The complexity of query containment in expressive fragments of xpath 2.0[END_REF], the rewriting of XPath queries is not always possible. We refer to this problem as the non-closure of XPath fragment under the query rewriting. The closure property is defined as follows: Definition 2.2 A class C of XPath queries is closed under query rewriting if there is a function Rewrite: C → C that, for any security view V =(D v , σ) and any query Q in C over D v , computes Q t =Rewrite(Q) in C such that for any instance T conforms to the original DTD D and its view T v w.r.t V , we have

/root/A[q]/B/H ∪ /root/A[q]/q 1 /(q 1 )*/H ∪ /root/A[q]/(q 2 )*/D/E/G/(D/G)*/H where: q 1 = D /G ∪ D /E/G, and q 2 = D /G ∪ D /E/G ∪ D /F /G.
Q(T v ) = Q t (T ).
It has been shown in [5] that the downward class (i.e. fragment X ) of XPath queries is not closed under query rewriting.

Theorem 1 For recursive XML security views, fragment X is not closed under query rewriting [5].

Our Proposed Solution

We show that the expressive power of the standard XPath [2] is sufficient to overcome the query rewriting problem over recursive views. We propose to redefine function Rewrite given in Definition 2.2 into Rewrite: C 1 → C 2 where C 2 is the fragment C 1 extended by adding some axes and operators. Using this extension, for any access specification S =(D, ann) and any query

Q in C 1 over D v (view of D computed w.r.t S ), we can compute Q t = Rewrite(Q) in C 2 such that for any instance T of D and its view T v w.r.t S, we have Q(T v ) = Q t (T ).
The input fragment C 1 in our case is fragment X (namely the downward class) defined in Section 2.1, which is used only to formulate user queries and to define access specifications, while C 2 is an extended fragment of X defined as follows:

:= ε | ↓ | ↑ | ↓ + | ↑ + | ↑ *
we enrich X by the self -axis (ε), the upward-axes parent (↑), ancestor (↑ + ), and ancestor -or -self (↑ * ), the position and the node comparison predicates.

The position predicate, defined with [n](n ∈ N ), is used to return the n th node from an ordered set of nodes. For instance, since we model the XML document with an ordered tree, the query ↓:: * [1] at an element node n returns its first child element, while ↑ + :: We summarize the augmented fragment of X by the following subsets X ⇑ (X with self and upward -axes), X ⇑

* [B = ′ topo ′ ][1]
[n] (X ⇑ with position predicate), and the final fragment X ⇑

[n,=] (X ⇑

[n] with node comparison predicate). It should be noted that for a given query Q, a rewriting technique must ensure the following conditions: (i) each subquery5 of Q refers only to accessible element nodes; and (ii) each relationship defined between two subqueries of Q is respected. For instance, the query ↓ + ::D/↓::* over the access specification depicted in Figure 2(b) must returns only accessible element nodes of type G or E which have an accessible D element as parent.

We define the accessibility problem as: "When does an element node of a given type is accessible?". It is clear that the function σ cannot solve this problem because of infinitely many possible paths involved by recursive views (see Example 2.2). We show in the next that the accessibility of a given element node w.r.t a given recursive view cannot be defined in the fragment X (even in X ⇑ ). We investigate the use of the augmented fragment X ⇑

[n] to solve the accessibility problem in particular, and the fragment X ⇑

[n,=] as a solution to avoid the non-closure of XPath fragment X in general.

Notations

Given an access specification S =(D, ann), and a document T conforms to D. We define two predicates A acc 1 and A acc 2 as follows 6 :

A acc 1 := ↑ * ::*[ε::root ann(A ′ ,A)∈ann ε::A/↑::A ′ ][1] [ε::root (ann(A ′ ,A)=Y |[Q])∈ann ε::A.σ(A ′ , A)/↑::A ′ ] A acc 2 := (ann(A ′ ,A)=[Q])∈ann not (↑ + ::A[not (Q )]/↑::A ′ )
Where and denote conjunction and disjunction respectively. The predicate A acc ] on an element node n of T returns an ordered set S of element nodes (n and/or some of its ancestor elements) such that for each one an annotation is defined. Thus, with S[qual 2 ] (n A acc 1 ) we ensure that the first element node in S is concerned by a valid annotation. With the second predicate, we use n A acc 2 to ensure that all qualifiers defined over ancestor elements of n are valid (we discuss this restriction in Section 5.2). These predicates are "powerful tools" to solve the accessibility problem as we will see in the next section.

Since the σ function is not computable in case of recursion, the parent/child relation defined between two element types in the query (e.g. query ↓ + ::A/↓::B defines parent/child relation between A and B ) cannot be rewritten in X . Accordingly, we define the two predicates A + and A B to rewrite parent/child relation:

A + := ↑ + ::*[A acc 1 ] A B := A + [1]/ε::B
For an element node n in T, n〚A + 〛 returns the set of all accessible ancestor elements of n. The element node n has an accessible B element as parent if and only if n A B .

We use these four predicates throughout the paper to formalize our solution.

Access Control with Recursive DTDs

Our access control framework is presented in Figure 3. For each class of users, the administrator defines an access specification S =(D, ann) over the DTD D.

The DTD view D v is derived first and given to the users to formulate their queries. For each instance T of D, we compute a virtual7 view T v of T to show only accessible data. Each X query Q over T v is efficiently rewritten, using the security view V (defined below in Section 3.1), to an equivalent X ⇑ [n,=] query Q t over T, in order to return only accessible data.

Recursive Security Views

We redefine the security view over an access specification S =(D, ann) to be V =(D v , ann), where D v is the view of D, computed by algorithm DeriveView illustrated in Figure 4, and used by the users to formulate their queries.

We use first a DTD parser8 to explore the DTD D into an expressive indexed structure in such a way, for each element type A in D, the set of its children types and descendant types are returned, also the content model P(A) is represented as a tree where all sub-expressions composing P(A) are detected as we explain in the next.

We define the recursive function Exp(A,access) that, according to a given access specification S=(D,ann), extracts the content model for the element type A and for all its descendant types in D. For each element type A parsed by Proof. For an element type A in D, we denote by |P (A)| the number of all subelement types and operators ("," or "|") defining P(A). The procedure Exp of Figure 4 works over the hierarchical, parse-tree representation of the regular expression P(A). This tree is given using the DTD parser cited above, where its intermediate nodes represent operators and the leaves are the subelement types of A. Each operator links two or more element types/sub-expressions. To compute the new content model of A, we parse all the element types B i (i.e. the leaves) of the P(A) tree to eliminate each inaccessible B i (i.e. ann(A, B i )=N exists). Next, each node operator with no children nodes is eliminated. Finally, the new resulting tree is translated into a regular expression which represents the content model P v (A).

Accessibility

Now we define the element node accessibility based on the use of recursive views: i) The element node n is concerned by a valid annotation, or ann(A, B) does not exist and there is an annotation defined over ancestor element n ′ of n where: n ′ is the first ancestor element of n concerned by an annotation, and this annotation is valid at n ′ .

ii) For each ancestor element n ′ of n concerned by an annotation with value

[Q ′ ], n ′ Q ′ must be verified.
Example 3.1 Consider the DTD depicted in Figure 2(b) where annotation q is ↓::D. For an element node n of type H within the instantiation of this DTD, if its parent element is of type C then n is not accessible. Otherwise, the first ancestor element of n which is concerned by an annotation can be either of type F (i.e. ann(D,F )=N ), of type E (i.e. ann(D,E )=Y ), or of type A (i.e.

ann(root,A)=[q]

). This means that n may be accessible if its first ancestor element is of type E or A, and it has no ancestor element n ′ of type A with n ′ q.

Note that the element node accessibility over recursive XML views cannot be defined in X ⇑ . We consider the access specification S =(D, ann) composed by the DTD of Figure 2(b) and the annotations depicted in the edges. Figure 5 represents (a) an instance T of D and (b) its view T v computed according to S. The query ↓ + :: H over T must be rewritten to return only the node H 2 , which is accessible w.r.t S. However ↓ + :: H[↑ + :: E or ↑ + :: A[q]] returns both the nodes H 1 and H 2 , and ↓ + :: H[(↑ + :: E or ↑ + :: A[q]) and not (↑ + :: F )] rejects the accessible node H 2 shown in T v .

We use the predicates A acc 1 and A acc 2 defined in Section 2.5 to satisfy the accessibility conditions (i) and (ii) respectively of Definition 3.1. Definition 3.2 For any security view V=(D v , ann) and any instance T conforms to the original DTD D, we define the accessibility predicate A acc which refers to an X ⇑

[n] qualifier such that, an element node n on T is accessible iff n A acc , with A acc := A acc 1 ∧ A acc 2 .

For an element type B in a DTD D, ↓ + ::B[A acc ] stands for all accessible B elements in an instance of D. Consider the element node H 1 of the XML document illustrated in Figure 5(a). Then, H 1 〚↑ * ::*[ε::A/↑::root ∨ ε::E/↑::D ∨ ε::F /↑::D ∨ ε::H/↑::C ∨ ε::root]〛 returns the set S={F 1 ,E 1 ,A 1 ,root} of ordered element nodes (element node H 1 and/or some of its ancestor elements) where for each one an annotation exists (e.g. ann(D,F )=N for element node F 1 ). Note that S [1] returns the ancestor element F 1 and the final predicate A acc 1 over the element node H 1 of Figure 5(a) is not satisfied (i.e. H 1 A acc 1 ) since the first ancestor element concerned by an annotation in S is not accessible (F 1 's annotation is not valid). The query ↓ + ::H[A acc ] over the instance T of Figure 5

Query Rewriting over Recursive XML Views

In this section we describe our XPath-based query rewriting algorithm. Given an access specification S =(D, ann), the security view V =(D v , ann) of S, an instance T conforms to D, and its virtual view T v computed w.r.t V. Then, for any query p over T v , the goal of query rewriting is to find a rewriting function that we define as:

X -→ X ⇑ [n,=] p -→ Rewrite(p) such that p(T v ) = Rewrite(p)(T )
Our rewriting function Rewrite ensures that only accessible element nodes are referred to by the subqueries of p, which is ensured by the accessibility predicate of Definition 3.2. Moreover, the relationships defined between each two subqueries of p must be respected.

Inria

Queries Without Predicates

For a DTD D=(Ele,P,root), we discuss the rewriting of queries without predicates with the form axis 1 ::E 1 /.../axis n ::E n where E i ∈ {Ele,*} and axis i is an XPath axis in fragment X . Given the query ↓ + ::E i /↓ + ::E j , it is clear that the rewritten query can be ↓ + ::E i [A acc ]/↓ + ::E j [A acc ] to return accessible E j elements which have at least one accessible ancestor element of type E i . However, it is not so simple in the case of child -axis.

Example 4.1 The query ↓ + ::A/↓::E over the view T v of Figure 6(d) returns E elements having an A element as parent. So the elements E 1 and E 2 are returned. Using the kleene closure, this query can be rewritten over the instance T of Figure 6(c) into: ↓ + ::A/↓::B/↓::D /(↓::B/↓::D )*/↓::E. However, using the standard XPath, a cycle in the DTD cannot be replaced by '↓ + '. For instance the query ↓ + ::A[A acc ]/↓ + ::E[A acc ] returns the elements E 1 , E 2 , and E 3 , while E 3 does not have a parent A.

We use the predicate A B (B can be any element type) defined in Section 2.5 to rewrite the parent/child relation. For instance, the query ↓ + ::A/↓::E of the previous example can be rewritten into ↓ + ::E[A acc ][A A ] to return only accessible E elements (verified with A acc ) which have an accessible parent of type A (verified with A A ). 6(d),A + returns the set of its ordered accessible ancestor elements {D 3 ,A 3 ,root}, that we denote E 3 〚A + 〛. The predicate A A (i.e. A + [1]/ε::A) does not hold at element node E 3 (i.e. E 3 A A ) since the first accessible ancestor element of E 3 is not of type A (i.e. A + [1] at E 3 returns its ancestor element D 3 ). However, A A holds at element nodes E 1 and E 2 . Property 2. For any security view V =(D v , ann) and any element type B in D v , the predicates A + and A B can be constructed in O(|ann|) time.

Proof. The same principle as the proof of Property 1.

Finally, given a (recursive) security view V =(D v , ann), we define the rewriting function Rewrite : X × Ele → χ ⇑

[n] that we use to rewrite an X query p=p 1 /.../p n (where each subquery p i is given with axis i ::E i ) over a node context of type E in D v , to an equivalent one Rewrite(p,E ) defined in X ⇑

[n] over the original DTD as:

Rewrite(p,E) := ↓ + ::E n [A acc ][pref ix -1 (p 1 /.../p n )]
Where the qualifier pref ix -1 (p 1 /.../p n ) is recursively defined over the descending list of subqueries of p. For each subquery p i , pref ix -1 (p 1 /.../p i-1 ) is already computed and used to compute pref ix -1 (p 1 /.../p i ) as follows:

• axis i = ↓: pref ix -1 (p 1 /.../p i ) := A Ei-1 [pref ix -1 (p 1 /.../p i-1 )] • axis i = ↓ + : pref ix -1 (p 1 /.../p i ) := ↑ + ::E i-1 [A acc ][pref ix -1 (p 1 /.../p i-1 )]
Recall that E is the type of context node at which the query is evaluated. As a special case we have: pref ix -1 (↓::E 1 )=A E , and pref ix -1 (↓ + ::E 1 )=↑ + ::E[A acc ].

Example 4.3 Consider the query ↓::A/↓::E over the node context root of the view T v of Figure 6(d). Using our algorithm Rewrite we obtain:

Rewrite(↓::A/↓::E, root) = ↓ + ::E[A acc ][A A [A root ]]= ↓ + ::E[A acc ][A + [1]/ε::A[A + [1]/ε::root]]
A + is given in Example 4.2. The evaluation of A + returns {A 1 ,root} at element node E 1 , {A 21 ,A 2 ,root} at E 2 , and {D 3 ,A 3 ,root} at E 3 . With A A we ensure that for an element node E referred to by the query, its first accessible ancestor element is of type A which is verified for E 1 , E 2 and not for E 3 in T v of Figure 6(d). Moreover, with A root we ensure that the A element returned by A A , which can be A 1 or A 21 for element nodes E 1 and E 2 respectively, must have root as the first accessible ancestor which is verified only for A 1 . Thus the query Rewrite(↓::A/↓::E, root) at root of Figure 6 The detail of Function Rewrite is given in Figure 7. After computing the descending list L of p's subqueries, we parse them to generate the pref ix -1 of the rewritten query as explained above. The node context A can be initialized to root of the DTD for rewriting p over the entire document. If p i is axis i ::*, then the *-label is replaced by the set of children/descendant types of E i-1 (axis i is ↓ or ↓ + resp.). Then, the rewriting of p i over p i-1 can result in a set of element types denoted by reach. Moreover, if E i =*, then it must exist at least one element type E in reach (result of the rewriting of p i-1 ) where E i is a child

RW_Pred(↓::E j ="c",E i ) := ↓ + ::E j [A acc ][ε::*="c"]/A + [1] = ε::E i RW_Pred(↓ + ::E j ="c",E i ) := ↓ + ::E j [A acc ][ε::*="c"]
Example 4.4 The query ↓ + ::A[↓::E], given in the proof of Theorem 3, is rewritten into:

Rewrite(↓ + ::A[↓::E], root) = ↓ + ::A[A acc ][↑ + ::root[A acc ]][RW_Pred(↓::E, A)] ≡ ↓ + ::A[A acc ][↓ + ::E[A acc ]/A + [1]=ε::A]
where ↑ + ::root[A acc ] is omitted since root is always accessible. The rewritten query over T v of Figure 6(d), returns the element nodes A 1 and A 21 .

The detail of Function RW_Pred is given in Figure 8. We have seen in Rewrite algorithm that the rewriting of subquery axis i+1 ::* over E i results in a set of element types (reach) reachable from E i . Then, the predicate q in axis i ::E i [q] is rewritten over element type E i (E i =*) as explained in the above definition of RW_Pred. While the predicate q in axis i ::E i /axis i+1 ::*[q] is rewritten over the set of element types resulting by the rewriting of axis i+1 ::* over E i . We denote this set by L. For a given predicate q 1 /.../q n over element type E, L :=reach(q 1 ,{E}) denotes the result of rewriting sub-predicate q 1 over E (element types reachable from E with q 1 ), sub-predicate q 2 is rewritten over L resulting in a new set L :=reach(q 2 ,L) (i.e. L :=reach(q 2 ,reach(q 1 ,{E}))), and so on until rewriting q n over L:=reach(q n-1 ,L). Each sub-predicate q i can contain other sub-predicates (case of axis i ::E i [f i ]). The *-labels in the sub-predicates are eliminated with the same principle explained in algorithm Rewrite using the precomputed lists of children and descendant types (Reach). The rewriting result of predicate q can be false if some element types in q are inaccessible (they do not appear in D v ) or some relationships are not respected (e.g. the rewriting of predicate ↓::

E i over element type E i-1 is false if E i is not a subelement type of E i-1 , such that E i / ∈ Reach(↓,E i-1
)). Rewriting result can be true (the predicate is omitted from the query) in case of not(q) with non valid q. Now, we generalize the formal definition of the algorithm Rewrite given in the previous section to handle predicates. Given the query p 1 /.../p n where p i = axis i ::E i [f i ] and f i ([f i ] is optional) is a predicate defined over element type E i . We rewrite this query over node context of type E as follows:

Rewrite(p, E) := ↓ + ::E n [A acc ][f ′ n ][pref ix -1 (p 1 /.../p n )]
where an intermediate step, pref ix -1 (p 1 /.../p i ) is recursively defined with:

• axis i = ↓: pref ix -1 (p 1 /.../p i ) := A Ei-1 [f ′ i-1 ][pref ix -1 (p 1 /.../p i-1 )] • axis i = ↓ + : pref ix -1 (p 1 /.../p i ) := ↑ + ::E i-1 [A acc ][f ′ i-1 ][pref ix -1 (p 1 /.../p i-1 )] where f ′ i-1 := RW_Pred(f i-1 , E i-1 ).
q ′ r := RW_Pred (qr,reach(q f ,L)); 20 if (q ′ r =f alse) then return f alse;

21 if (axis 1 =↓) then 22 qt := f s(↓ + , reach(q f , L))[A acc ][f ′ ][q ′ r ]/A + [1]=ε:: * ; 23 else 24 qt := f s(↓ + , reach(q f , L))[A acc ][f ′ ][q ′ r ];
25 else if (q is q 1 ∧...∧qn) then 26 if (∃ q i s.t RW_Pred(q i ,L)= f alse) then 27 qt := f alse;

28 else if (RW_Pred(q i ,L)= true f or each q i ) then 29 qt := true; 30 else 31 qt := RW _P red(q i ,L) =true RW_Pred (q i ,L); 32 else if (q is q 1 ∨...∨qn or q 1 ∪...∪qn) then 33 if (∃ q i s.t RW_Pred(q i ,L)= true) then

Inria

Since the query answering time concerns the rewriting time and the evaluation time of the rewritten query, then the existence of the *-label in the rewritten query can induce for poor performance when some inaccessible elements are parsed by the rewritten query. For instance, given the query ↓::E over context node n of type A with E=*. Without eliminating the *-label, this query is rewritten into ↓ + ::E[A acc ][A A ], and then for each descendant node of n of any element type, the predicates A acc and A A are evaluated. To improve the query evaluation time, the elimination of the *-label in the query is indispensable and ensures that two defined predicates are evaluated only at accessible descendant nodes of n (i.e. whose types appear in D v ). This elimination can give good performance since the size of D v (number of accessible element types) is too small than the size of the original DTD D in practice. For this reason, the precomputed lists Reach can be sorted in such a way the union of the children/descendant types of two element types of D v (e.g. Reach(↓,E 1 ) ∪ Reach(↓,E 2 )) can be linear on the size of D v . Accordingly, the *-label elimination phase, done in lines 18-23 of algorithm Rewrite and lines 3-8 of algorithm RW_Pred, can be efficiently improved to take at most |D v | time and any query p can be rewritten in this case in at most O(|p| * |D v |) time.

Extensions

We discuss some extensions of our proposed rewriting approach to deal with a large fragment of XPath queries, and to overcome some limitations of existing access specifications languages.

Upward-axes Rewriting

For the rewriting of upward-axes (↑ and ↑ + ), we extend the algorithms Rewrite and RW_Pred without increasing the complexity of the global rewriting (as explained in Theorem 4). In Rewrite, pref ix -1 (p 1 /.../p i ) is defined over upward-axes as follows:

• axis i =↑ : pref ix -1 (p 1 /.../p i ) := ↓ + ::E i-1 [A acc ][f ′ i-1 ][pref ix -1 (p 1 /.../p i-1 )]/A + [1]=ε::E i • axis i =↑ + : pref ix -1 (p 1 /.../p i ) := ↓ + ::E i-1 [A acc ][f ′ i-1 ][pref ix -1 (p 1 /.../p i-1 )] where f ′ i := RW_Pred(f i , E i ).
In RW_Pred, an intermediate predicate q i /../q n (q i =axis i ::E i [f i ]) is rewritten over element type E i-1 in case of upward-axes as follows:

• axis i =↑: RW_Pred(q i /.../q n ,E i-1 ) := A Ei [f ′ i ][RW_Pred(q i+1 /.../q n ,E i )]

• axis i =↑ + : RW_Pred(q i /.../q n ,E i-1 ) :=

↑ + ::E i [A acc ][f ′ i ][RW_Pred(q i+1 /.../q n ,E i )] where f ′ i := RW_Pred(f i , E i ).
Inria

Revision of Access Specifications

The node accessibility w.r.t the specification value [Q ] has been defined with two different meanings [4,9]. Like in [4], we have assumed in the definition of the element node accessibility that for each element node n concerned by an annotation of value [Q], if Q is not valid at n (i.e. n Q) then n and all its descendant elements are not accessible, even if there is some valid annotations defined over these descendants (condition (ii ) of Definition 3.1). However, in [9] the element node n can be not accessible (i.e. n Q), but one of its descendant element B ′ can be accessible if it is concerned by a valid annotation. We assume that both meanings are useful and an access control specification language must provide the definition of each of them. For this reason, we redefine the access specification of Definition 2.1 as follows: Definition 5.1 An access specification S is a pair (D, ann) consisting of a DTD D and a partial mapping ann such that, for each production A → P (A) and each element type B in P(A), ann(A,B), if explicitly defined, is an annotation of the form:

ann(A,B) := Y | N | [Q] | N h | [Q] h
Given an element node n of type B with parent node of type A, then with the specification values N and [Q], accessibility overwriting is allowed under n even though ann(A,B )=N or ann(A,B )=[Q] and n Q. The semantics of the new specification values N h and [Q ] h are given as follows. If the element node n is concerned by an annotation with value N h , then no overwriting of this value is permitted to descendant elements of n, i.e. if n ′ is a descendant element of n, then n ′ is not accessible even if it is concerned by a valid annotation. While if n is concerned by an annotation with value [Q] h , then the annotations defined under n (i.e. under B element type) take effect only if n Q. For instance, if a descendant element n ′ of n is concerned by an annotation of value [Q ′ ], then n ′ is accessible only if n ′ Q ′ and n Q. We call the annotation with value N h or [Q] h , downward-closed annotation. For the first policy, $name is a variable system denoting patient's name. For a given patient with name "Bob", if p pname="Bob" then all the fragment rooted at p is hidden from the patient "Bob" and any annotation under element node p can be applied since it is the medical data of another patient. Also, the annotation ann(patient, parent)=N h cannot be defined with ann(patient, parent)=N otherwise ann(medication, diagnosis)=Y makes diagnosis information of parent accessible to patient "Bob" as its own information. The same principle is applied with the annotation ann(patient, sibling)=N h . For the second policy, it is clear that a false evaluation of the predicate does not imply the inaccessibility of the sub patients, i.e. a given patient may not have "disease1 ", while its parent/sibling can be affected by this disease and must be shown to the research institute.

The new access specification defined can be taken into account simply by applying the following changes in our rewriting approach. The predicate A acc 1 is redefined with: 9A acc 1 := ↑ * ::*[ε::root ∨ ann(A ′ ,A)∈ann ε::A/↑::

A ′ ][1] [ε::root ∨ (ann(A ′ ,A)=Y |[Q]|[Q] h )∈ann ε::A.σ(A ′ , A)/↑::A ′ ] While The predicate A acc 2 is redefined with: A acc 2 := (ann(A ′ ,A)=N h )∈ann not (↑ + ::A/↑::A ′ ) (ann(A ′ ,A)=[Q] h )∈ann not (↑ + ::A[not (Q )]/↑::A ′ )

Experimental Results

We have developed a prototype to improve effectiveness of our rewriting approach. The performance study is done using a real-life recursive DTD and a various forms of XPath queries. The experimental results show the efficiency of our XPath query rewriting approach w.r.t the answering approach based on the materialization of the view. Notice that we cannot do comparison between our approach and the two existing approaches which deal with queries rewriting under recursive views [5,8], since they are based on the non-standard language "regular XPath", and no practical tool is present to evaluate regular XPath queries. The experiments were conducted using Ubuntu system, with a dual Core 2.53 GHz and 1 GB of memory.

XML Documents. Using ToXGene generator [1], we generated set of XML documents that conform to the hospital DTD of Figure 9 and with sizes ranging from 10MB to 100MB.

Security Specification. Figure 9(b) represents the hospital DTD view D v of a research institute studying inherited patterns of some diseases. This view shows only patients having one or more disease from {disease1, disease2, disease3 } with their parent hierarchy, and denies access to their name, address, test and doctor data. Formally, we define this view with the following annotations: Approaches. A comparison is done between our rewriting approach and the materialization approach. Given a security view V =(D v , ann), the materialization consists in incorporating an accessibility label (+/-) to each element node in the document which is concerned by an annotation of V. Each element node n, not yet labeled (i.e. no invalid downward-closed annotation is defined over its ancestor elements), is labeled with "+" if it is concerned by an annotation with value Y or with value [Q]|[Q] h and n Q (resp. n is labeled with "-" in case of annotation with value N |N h or with value [Q]|[Q] h and n Q). In case of an element node n concerned by an invalid downward-closed annotation (with value N h or with value [Q] h and n Q), the n and all its descendant elements are labeled with "-". After applying all the annotations of the security view V over the document, each unlabeled element node is annotated by inheritance from its nearest labeled ancestor element. The obtained document is called fully annotated document. Finally, the materialized view of the original document is computed by deleting all inaccessible element nodes (labeled with "-") from the fully annotated document and user queries are evaluated directly over this view. Thus, we compare the answering time of the materialization approach (defined as the view materialization time and query evaluation time over the materialized view) with that of our rewriting approach (defined as the rewriting time of the query and the evaluation time of the rewritten query over the original document).

Performance Results. The experimental results are shown in Figure 10 where the answering time of each query is evaluated using our rewriting algorithm and the materialization approach. The size of the answer ranges from few hundred to a few thousand of nodes. Figure 10 shows clearly that our algorithm remains more efficient than the materialization approach.

We observe first that the translation of XPath queries from X to X ⇑

[n,=] does not induce for a poor performance and the average of the answering time of our rewriting approach remains in general less than 8 seconds for a large XML document. Second, a query containing time-consuming elements like *-labels or parent axes does not degrade the rewriting performance as shown with the query Q 3 .

Inria

The proposed approach yields the first practical solution to rewrite XPath queries over recursive XML views using only the expressive power of the standard XPath. The extension of the downward class of XPath queries with some axes and operators has been investigated in order to make queries rewriting possible under recursion.

The conducted experimentation shows the efficiency of our approach by comparison with the materialization approach. Most importantly, the translation of queries from X to X ⇑

[n,=] does not impact the performance of the queries answering. We have discussed how our approach can be extended to deal with the upward-axes without additional cost. Lastly, a revision of the access specification language is presented to go beyond some limitations in the definition of some access privileges.

As future work, we plan first to provide an optimized version of our approach and also to use the same principle to secure XML updating.

  path := axis::label | path'['qual']' | path'/'path | path'∪'path qual := path | path = c | qual and qual | qual or qual | not qual | '('qual')' axis := ↓ | ↓ +

Example 2 . 1

 21 Consider the DTD D depicted in Figure 1(a) where the labels of the edges represent the following access specification: ann(root,A)=[q],

Figure 1 :

 1 Figure 1: Simple non-recursive DTD.

Figure 1 (

 1 b) depicts the resulting view D v .

Figure 2 :

 2 Figure 2: DTD Recursion Problems.

  Inria path := axis::label | path'['qual']' | path'['n']' | path'/'path | path'∪'path qual := path | path = c | path = ε::label | qual and qual | qual or qual | not qual | '('qual')' axis

1

  has the form ↑ * ::*[qual 1 ][1][qual 2 ]. Applying ↑ * ::*[qual 1

Figure 3 :

 3 Figure 3: XML Access Control Framework.

  Thus, these steps are done by parsing all the nodes of the P(A) tree in O(|P (A)|) time. If we consider that P ′ is the largest production in D then O(|P (A)|) is bounded by O(|P ′ |) and the content models of all element types of D are computed in at most O(|D| * |P ′ |) time.

Figure 5 :

 5 Figure 5: Example of Instance view.

Definition 3 . 1

 31 Given a security view V=(D v , ann) and a document T conforms to the original DTD D, then an element node n on T of type B with parent node of type A is accessible (shown in the view T v of T), if and only if the following conditions hold:

Example 3 . 2 acc 1 and A acc 2 are defined as follows: A acc 1 : 2 :

 321212 Consider the access specification depicted in Figure 2(b), the predicates A = ↑ * ::*[ε::root ∨ ε::A/↑::root ∨ ε::E/↑::D ∨ ε::F /↑::D ∨ ε::H/↑::C][1][ε::root ∨ ε::A[q]/↑::root ∨ ε::E/↑::D ]A acc = not (↑ + ::A[not (q)]/↑:: root)

Property 1 .

 1 (a) returns only the accessible element H 2 (shown in the view T v of Figure 5(b)). For any security view V =(D v , ann), the accessibility predicate A acc can be constructed in O(|ann|) time. Proof. For any security view V =(D v , ann), the construction of A acc 1 and A acc 2 depends only on the parsing of all annotations ann of V which is done in O(|ann|) time.

Figure 6 :

 6 Figure 6: Query Rewriting Problems.

Example 4 . 2

 42 Given the access specification of Figure 6(a), we define the predicate A + as follows: A + := ↑ + ::*[↑ * ::*[ε::E/↑::D ∨ ε::B/↑::D ∨ ε::D /↑::C ∨ ε::B/↑::A ∨ ε::root][1][ε::E/↑::D ∨ ε::D /↑::C ∨ ε::root]]. At element node E 3 of Figure

  (d) returns {E 1 }. Inria if ( reach={}) then return φ; // rewriting of predicate f i over reach elements 25 f ilters := RW_Pred(f i ,reach); 26 if (f ilters = f alse) then // invalid predicate 27 return φ; 28 else if (f ilters = true) then // omitte f i f rom p i 29 f ilters := ǫ; // rewritten query pt of p w.r.t A 30 if (f ilters = ǫ) then 31 pt := f s(reach, ↓ + )[A acc ][pt]; 32 else 33 pt := f s(reach, ↓ + )[A acc ][f ilters][pt]; 34 return pt;

Figure 7 :

 7 Figure 7: Algorithm for XPath Queries Rewriting.

Example 4 . 5

 45 Consider the query ↓ + ::A[↓::*/↓::D] over the Figure 6(b). Using our algorithm RW_Pred, the predicate ↓::*/↓::D is rewritten over element type A as follows: [RW_Pred(↓::*/↓::D,A)] = [(↓ + ::A∪ ↓ + ::D∪ ↓ + ::E)[A acc ][RW_Pred(↓::D,{A, D, E})]/A + [1]=ε::A] = [(↓ + ::A∪ ↓ + ::D∪ ↓ + ::E)[A acc ][↓ + ::D[A acc ]/A + [1]=ε::*]/A + [1]=ε::A].

  RW _P red(q i ,L) =f alse RW_Pred (q i ,L);37 else if case of not (q) then 38 if RW_Pred(q,L)= f alse then39 qt := true; 40 else if RW_Pred(q,L) = true then 41 qt := not (RW_Pred (q,L)); 42 else if case of ǫ then 43 qt := true; 44 return qt;

Figure 8 :

 8 Figure 8: Predicate Rewriting.

Example 5 . 1

 51 We consider the hospital DTD of Figure 9(a) and we give the following access specification: • A patient can access only to its own diagnosis information: ann(department, patient) = [pname=$name] h ann(patient, parent) = ann(patient, sibling)=N h ann(patient, visit) = N , ann(medication, diagnosis) = Y • A research institute can access to patients whose have "disease1": ann(department, patient) = ann(parent, patient) = ann(sibling, patient) = [visit/treatment/medication[diagnosis='disease1']]

Figure 9 :

 9 Figure 9: Hospital DTD.

Figure 10 :

 10 Figure 10: XPath Queries Evaluation Time.

RR n°7834

According to[START_REF] Rassadko | Query rewriting algorithm evaluation for xml security views[END_REF] the SMOQE system proposed in[6] has been removed because of conduction of future researches.Inria

An element type B is inaccessible if for each parent type A, either (i) the annotation ann(A,B )=N exists or (ii) A is an inaccessible element type.Inria

Note that ǫ denotes the empty path.

We denote by p(T) the result of evaluating query p over document T.RR n°7834

For example, the query ↓ + ::B[↓::C] contains two subqueries ↓ + ::B and ↓::C with a parent/child relation defined between C and B, and an ancestor/descendant relation defined between B and the node context at which the query is posed.

6 Note that A.σ(A ′ , A) gives A[Q] if ann(A ′ ,A)=[Q] and A otherwise. RR n°7834

The views of T are never materialized.

Available at: http://www.rpbourret.com/dtdparser/index.htm.Inria

Note that A.σ(A ′ , A) gives A[Q] if ann(A ′ ,A)=[Q]|[Q] h and A otherwise.Inria

rue du Jardin Botanique CS20101 54603 Villers-lès-Nancy Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

type of E if axis i =↓ or one of its descendant types if axis i =↓ + (lines 18-23). If the rewriting of p i over p i-1 stands for an empty set reach then the query is rejected (line 24). By fs we refer to the function fusion, e.g.

Function RW_Pred, called in the algorithm Rewrite, represents the predicates rewriting, which is the subject of the next section. As shown above, upward -axes and the position predicate are necessary for rewriting simple queries (without predicates). We prove below that fragment X ⇑

[n] is not closed under query rewriting. Extending this fragment with the node comparaison operator (which results in the final fragment X ⇑

[n,=] ) turns out sufficient to rewrite any query in X .

Theorem 3 For recursive XML security views, the XPath fragment X ⇑

[n] is not closed under query rewriting.

Proof. (by contradiction) We consider query with the form E[q] which represents the rewriting limitation of the XPath fragment X ⇑

[n] . Assume that the query rewriting can be done in X ⇑

[n] . The query ↓ + ::A[↓::E] over the view instance T v depicted in Figure 6(d) cannot be correctly rewritten, using the previous definition of algorithm Rewrite, into Rewrite(↓

. Indeed, the resulting query returns {A 1 , A 2 , A 21 }, but A 2 does not have an immediate child E. The limitation is due to the fact that predicate [↓::E] must return all descendant elements E having as the first accessible ancestor the node context A at which the predicate is evaluated (i.e. the element node returned by ↓::E/A + [1] must be the same element node of type A at which the predicate is evaluated). This cannot be expressed in X ⇑

[n] and can be done only by introducing the node set comparison (e.g. X ⇑

[n,=] ) as we will present in the following.

Predicates Rewriting

We explain the rewriting of predicates to complete the definition of our rewriting algorithm Rewrite. For a given query axis 1 ::E 1 [q 1 ]/.../axis n ::E n [q n ], we rewrite each predicate q i over the element type E i at which q i is defined. Given a security view V =(D v , ann) and a subquery E[q] (we take a simple predicate q=q 1 /.../q n where q i =axis i ::E i for more comprehension). We define the function RW_Pred : X × Ele → X ⇑ [n,=] to rewrite the predicate q in X over element type E in D v , to an equivalent one RW_Pred(q, E) in X ⇑

[n,=] , recursively defined over the descending list of sub-predicates of q as follows:

• axis i =↓: RW_Pred(q i /.../q n ,E i-1 ) :=

• axis i =↓ + : RW_Pred(q i /.../q n ,E i-1 ) :=

Given a query axis i ::E i [axis j ::E j ="c"] (text-content comparison), we have the following rewriting:

17 else if (q is q f /qr where q f = axis 1 ::E[f ] and qr is the remaining steps) then 18 rewrite q f as done in lines 3-16 ;

Complexity Analysis

Given a security specification S =(D,ann), we extract first the security view V =(D v , ann) corresponding to S, where D v is derived using our algorithm DeriveView of Figure 4. The user is allowed to request its authorized data represented with the DTD view D v . For each query Q in X , our algorithm Rewrite translates this query to an equivalent one Q t in X ⇑ [n,=] such that, for any instance T conforms to D, its virtual view T v conforms to D v , we have

The overall complexity time of our rewriting algorithm Rewrite is stated as follows:

Theorem 4 For any security view V=(D v , ann) and any X query Q over the DTD view D v , the algorithm Rewrite computes an equivalent query

Proof. Given an X query p=axis 1 ::E 1 [q 1 ]/.../axis n ::E n [q n ], we denote by |p| the number of subqueries and sub-predicates of p, e.g. |↓::E 1 [not(↓ + ::*)]|=2. Each subquery (or sub-predicate) p i =axis i ::E i [q i ] of p must be rewritten over p i-1 =axis i-1 ::E i-1 [q i-1 ] to check the accessibility of E i and to preserve the relationship defined between E i and E i-1 . This is done in a constant time by using the precomputed predicates A acc and A + as in lines 8-17 of algorithm Rewrite and lines 13-16 of algorithm RW_Pred. The *-label of each subquery (or sub-predicate) is eliminated as done in the lines 18-23 of algorithm Rewrite, and lines 3-8 of algorithm RW_Pred, which causes an additional cost |D v | 2 . For instance, to rewrite the query ↓::* over the set reach, the elimination of the *-label amounts to parse each element type E in reach and compute the union of its children types given by the precomputed list Reach(↓,E) (|Reach(↓,E)|=O|D v |). Next, the *-label of the query ↓::* is replaced by the union of children types of element types in reach which is done in at most O|D v | 2 time. Thus, a given query p can be rewritten in at most O(|p| * |D v | 2 ) time.

Query Rewriting Improvements

We discuss in this section some possible implementations of our rewriting algorithm Rewrite to improve the overall complexity of Theorem 4.

The first optimization can be done by avoiding the *-label elimination step discussed above. For a security view V =(D v , ann), an X query Q over the DTD view D v can be rewritten in a linear time O(|Q|). Using the precomputed predicates A acc and A + , each subquery p i of the query p can be rewritten over p i-1 in a constant time by adding the predicate A Ei-1 (i.e. A + [1]/ε::E i-1 ) or A acc , case of axis i =↓ and axis i =↓ + respectively. For instance, the query ↓::*/↓::B over context node of type A can be rewritten into ↓ + ::B[A acc ][A + [1]/ε::*/A + [1]/ε::A]. In the same way, each sub-predicate q i =axis i ::E i can be rewritten over q i-1 in a constant time into ↓ + ::E i [A acc ]/A + [1]=ε::E i-1 in case of axis i =↓, or into ↓ + ::E i Thus, the rewriting of the query p depends on the parsing of all its subqueries and sub-predicates which is done in O(|p|) time.


Mohamed Ghassane Kabadi
email: mkabadi@cran.uhp-nancy.fr

Taha Boukhobza
email: taha.boukhobza@cran.uhp-nancy.fr

Frederic Hamelin
email: frederic.hamelin@cran.uhp-nancy.fr

M-G Kabadi

Discrete mode observability analysis of switching structured linear systems with unknown input: A graphical approach

Keywords: discrete mode observability, state and input observability, switching structured linear systems, graph theory

Switching linear systems are described by a set of continuous state-space models together with conditions (switching law) that decide which model (mode) of this set is valid for the current continuous state. This article deals with the problem of the observability of discrete mode in which the switching law is assumed to be unknown. The formalization of the problem, based on a graph-theoretic approach, is to express sufficient conditions for generic observability of the discrete mode assuming only the knowledge of the system's structure. These conditions allow us to obtain criteria of sensor placement in order to recover the discrete mode observability using properties of the graph associated to the system. We obtain a sensor placement procedure based on classical and well-known graph theory algorithms, which have polynomial complexity orders.

I. INTRODUCTION

Over the past decade, study of hybrid systems has received particular attention in several scientific fields including automation. In general, this kind of systems can represent, through hybrid systems properties, several physical, technological and biological phenomena. It allows to model complex systems which combine the dynamics of the continuous parts of the system with the dynamics of the logic and discrete parts. Hybrid models are characterized by continuous processes (continuous differential equations) interacting with discrete processes (paradigms from discrete event systems). A hybrid system's structure is illustrated in figure I: these models have proven their efficiency for the representation of complex systems, unlike the homogeneous approach of continuous linear systems that is insufficient for modeling such systems. The transition from one mode to another one is strongly linked to the global nature of the behavior of the complex system to model. When the mode transition is abrupt, we can define a particular but very important framework of hybrid dynamical systems : switching continuous-time linear systems (SCTLS) or SLS (to simplify the notation). They are composed of a family of subsystems which are linear time-invariant and these subsystems (modes) are orchestrated by a switching law that specifies which subsystem is active. As an extension of the classical linear or affine state-space representations of dynamical systems, this modeling formalism has been thoroughly investigated through several studies. Knowing that, the focus is on the study of observability property for SLS with unknown input, this property plays a major role in command law synthesis, fault detection and isolation, fault tolerant command law synthesis and also for perturbations rejection. Many definitions of this property appear in the literature for SLS. For example, we quote [START_REF] Bemporad | Observability and controllability of piecewise affine and hybrid systems[END_REF], [START_REF] Collins | Observability of piecewise-affine hybrid systems[END_REF], [START_REF] Chaib | Observability of the discrete state for dynamical piecewise hybrid systems[END_REF] devoted to studying observability of hybrid systems where the discrete mode depends on the state trajectory or is associated to discrete outputs. We can also quote [START_REF] Vidal | Observability and identifiability of jump linear systems[END_REF], [START_REF] Babaali | On the observability of piecewise linear systems[END_REF], [START_REF] Bemporad | Observability and controllability of piecewise affine and hybrid systems[END_REF] for deterministic discrete-time switching linear systems. Knowing the different studies and investigations devoted to SLS, there exist several differences between deterministic discrete-time switching linear systems and deterministic continuous-time switching linear systems mainly proved in [START_REF] Vidal | Observability of linear hybrid systems[END_REF]. This article focuses on the definition of observability for deterministic continuoustime switching linear systems expressed in [START_REF] Babaali | Observability of switched linear systems in continuous time[END_REF], [START_REF] Santis | Observability of internal variables in interconnected switching systems[END_REF], [START_REF] Vidal | Observability of linear hybrid systems[END_REF], [START_REF] Zhendong | Switched Linear Systems: Control and Design[END_REF], [START_REF]Observability and detectability of linear switching systems: A structural approach[END_REF]. Conventional algebraic and geometric tools which are based on the numerical value of state-space matrices of system's model are needed. However, these variables are subject to parametric uncertainties due to identification processus and so, they are approximatively known. We consider here a structured switching linear system also in state-space form, knowing that a switching linear system is structured when each entry of the matrices of its state-space form is either a fixed zero or a free parameter. The location of the fixed zeros in these matrices constitutes the structure of the system. The approach is of interest to investigate many classical properties of structured systems that can be studied in terms of genericity. In this case, properties that are true for almost any value of the free parameters are called generic proprieties. In order to check generic properties as controllability, observability and so on (see [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF]), we can associate in natural way digraphs to structured systems and so verify structural properties by means of graph theoretic terms. This approach also presents a major advantage. Indeed, through the association of the digraph with the structured system, we can intuitively represent the structural changes on the graph and take into account them when analyzing the property of system. This fact is very interesting knowing that a switch can be related to a change in structure, as for example in the field of electronics [START_REF] Yang | Electrical switching and bistability in Organic/Polymeric thin films and memory devices[END_REF]. In this paper, our aim is to characterize the discrete mode observability for structured switching linear systems (SSLS). The outline of the paper is as follows. In section II, we expose the problem statement. After that we give some definitions and notations to the graph-theoretic approach in section III, then the main result is given in section IV and we conclude.

II. PROBLEM STATEMENT

Consider the state-space form of switching linear systems as follows:

Σ : ẋ(t) = A(r t )x(t) + B(r t )u(t) y(t) = C(r t )x(t) + D(r t )u(t) (1)
with x ∈ R n , u ∈ R m , y ∈ R p are respectively the state vector, unknown input vector and output vector and matrices A(•), B(•), C(•) and D(•) are of appropriate dimensions. Consider a discrete mode variable (mode sequence) as an exogenous input which is considered to be unobserved and defined by r t : [0, ∞) → Q def = {1, . . . , N }. Close to [START_REF] Babaali | Observability of switched linear systems in continuous time[END_REF], the switching signal is right-continuous and so impulses in state and input of SLS are excluded. The minimum dwell time is considered to avoid zeno behavior which is an undesired phenomenon for the well-definedness of SLS. In order to have more general framework, a generic study of discrete mode observability is assumed not for all initial conditions and unknown input u but for generic ones. We deal with structured switching linear systems (SSLS) which consider only the structure of modeled system and assume independent all the real parameters of matrices A(q), B(q), C(q), D(q) for each mode q ∈ Q of SLS. The studied structured state space form is

Σ Λ : ẋ(t) = A λ (rt)x(t) + B λ (rt)u(t) y(t) = C λ (rt)x(t) + D λ (rt)u(t) (2)
Real parameters of this state-space form are either fixed to zero or assumed to be nonzero parameters. In the latter case, they are substituted by free parameters noted λ i and the set of these parameters forms vector Λ = (λ 1 , λ 2 , ..., λ h ) T which can take values in R h . A λ (q), B λ (q), C λ (q) and D λ (q) represent structured matrices for each q ∈ Q and are obtained by replacing the non zeros parameters of A(q), B(q), C(q), D(q) for each mode q ∈ Q by free parameters from vector Λ. To address the discrete mode observability problem, some preliminary definitions are useful:

Definition 1: (Mode distinguishability) Two modes q ∈ Q and q ∈ Q (with q = q ) are distinguishable if at least one of the two following conditions holds: -there exist an integer s ≥ 0 and an expression Ψ q (y, ẏ, . . . , y (s) ) = 0 which is satisfied for mode q but is not satisfied for mode q for almost all initial conditions x 0 and input u.

-there exist an integer s ≥ 0 and an expression Ψ q (y, ẏ, . . . , y (s ) ) = 0 which is satisfied for mode q but is not satisfied for mode q for almost all initial conditions x 0 and input u.

Here, " for almost all initial conditions x 0 and input u " is to be understood as " for all (x T 0 , u T ) T ∈ R n+m except for the zero set of some polynomials with real coefficients in the n + m initial state and input components" Ṫhese polynomials can be written down explicitly, i.e. we can precisely describe them when the mode distinguishability fails to be true. Obviously u(t) ≡ 0 and x 0 = 0 are two of these polynomials. The zero set of some polynomial forms a proper algebraic variety of R n+m which has Lebesgue measure zero. So, by the expression " for almost all initial conditions x 0 and input u " we mean for all initial conditions and input functions except the ones belonging to a proper algebraic variety in the state and input space. The interpretation of Definition 1 is that q is distinguishable from q if, for generic initial state x 0 and unknown input u, we can rule out q or q when observing the output over [0, T ]. Relatively to the definitions of [START_REF] Babaali | Observability of switched linear systems in continuous time[END_REF], our notion of distinguishability of q and q is equivalent to the fact that q is discernible from q or vice-versa. The mutual mode discernibility, which is a dissymmetric property in [START_REF] Babaali | Observability of switched linear systems in continuous time[END_REF], is equivalent to have both conditions of Definition 1 satisfied.

Definition 2: (Location observability) SLS (Σ) is location observable if its modes are all distinguishable two-by-two i.e. ∀q ∈ Q, ∀q ∈ Q, with q = q , q and q are distinguishable. Comparatively with the notion of location observability defined in [START_REF] Santis | Observability of internal variables in interconnected switching systems[END_REF], [START_REF]Observability and detectability of linear switching systems: A structural approach[END_REF], our definition concerns as well autonomous as non-autonomous systems. In [START_REF] Santis | Observability of internal variables in interconnected switching systems[END_REF], [START_REF]Observability and detectability of linear switching systems: A structural approach[END_REF], location observability is defined as the ability to reconstruct the mode starting from the knowledge of the input and the output, for any nonzero input value and for all initial conditions. Since we deal with unknown input systems, this definition is not applicable and it cannot be achieved for autonomous systems. In definition 2, we relax this by accepting that the reconstruction of the mode may be possible not for all but for almost all inputs and initial conditions values. To establish the observability of SLS, we have to address, in addition to location observability reduced to the study of the distinguishability of each pair of modes, the state and input observability of each mode as defined classically in [START_REF] Trentelman | Control Theory for Linear Systems[END_REF]. To study location observability, it is pertinent and necessary to highlight the similarities and the differences between the models associated to these modes. Thus, we decompose each structured matrix into two parts: the first one is common to the two modes and the second one is specific to each mode i.e. for q ∈ Q, A λ (q) = A λ 0 + A λ q , B λ (q) = B λ 0 + B λ q , C λ (q) = C λ 0 +C λ q and D λ (q) = D λ 0 +D λ q where all nonzeros entries of structured matrices are assumed as free parameters λ i from vector Λ. For the sake of simplicity, we consider in the later that we have only two modes q ∈ {1, 2}.

III. GRAPHICAL REPRESENTATION OF STRUCTURED SWITCHING LINEAR SYSTEMS

In this subsection, our aim is to present a manner of modeling structure of SSLS (Σ Λ ) taking into account different modes of the system. For a such structure, we can associate in a natural way a directed graph noted G(Σ Λ ) constituted by a non-empty finite set V of elements called vertices and a finite set E of ordered pairs of distinct vertices called edges (directed edges). Notation G(Σ Λ ) = (V, E) means that V and E are respectively vertex set and edge set of G(Σ Λ ). Vertex set V defined by V = X∪U∪Y corresponds to the system's variables (inputs U = {u 1 , . . . , u m }, states X = {x 1 , . . . , x n } and outputs Y = {y 1 , . . . , y p }) and edge set E is defined by E 0 ∪ E q . E 0 represents the common part of both modes of SSLS and E q represents the specific part for each mode. They can be respectively defined by

E 0 = A 0 -edges ∪ B 0 -edges ∪ C 0 -edges ∪ D 0 -edges, where, A 0 -edges = {(x j , x i ) | A 0 (i, j) = 0}, B 0 -edges = {(u j , x i ) | B 0 (i, j) = 0}, C 0 -edges = {(x j , y i ) | C 0 (i, j) = 0} and D 0 -edges = {(u j , y i ) | D 0 (i, j) = 0} and E q = A q -edges ∪ B q -edges ∪ C q -edges ∪ D q -edges for each mode q ∈ {1, 2}, where, A q -edges = {(x j , x i ) | A q (i, j) = 0}, B q -edges = {(u j , x i ) | B q (i, j) = 0}, C q -edges = {(x j , y i ) | C q (i, j) = 0}
and D q -edges = {(u j , y i ) | D q (i, j) = 0}. The existence of free non zero parameters (non-zero entries) of common part

(A λ 0 , B λ 0 , C λ 0 , D λ 0 )
of SSLS is represented by edges e 0 ∈ E 0 indexed by 0 and the existence of free non-zero parameters of specific part (A λ q , B λ q , C λ q , D λ q ) of SSLS is represented by edges e q ∈ E q indexed by q for q ∈ {1, 2}.

Example 1: To the system defined by the following structured matrices, we associate the digraph in Figure 1.

A λ 0 =               0 0 λ1 0 0 0 0 0 0 0 0 0 λ2 0 0 0 0 0 0 0 0 0 0 λ3 0 0 0 0 0 0 0 0 0 λ4 0 0 0 0 0 0 0 λ5 0 0 0 λ6 0 0 0 0 0 0 0 0 0 0 λ7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 λ8 0 0 0 λ9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0               , B λ 0 =               0 0 0 0 0 0 0 0 0 0 0 0 λ13 0 0 0 0 λ14 0 λ15               , C λ 0 =      λ16 0 0 0 0 0 0 0 0 0 0 λ17 0 0 0 0 0 0 0 0 0 0 0 0 λ18 0 0 0 0 0 0 0 0 0 0 0 0 λ19 0 0 0 0 0 0 0 0 0 0 0 λ20      , All the entries of A λ 1 , B λ 1 , B λ 2 are zero except A λ 1 (1, 3) = λ 10 , B λ 1 (10, 2) = λ 11 , B λ 2 (9, 2) = λ 12 . The elements of matrices A λ 2 , C λ 1 , C λ 2 , D λ 0 , D λ 1 and D λ 2 are equal to zero.

A. Notations and definitions

The digraph representing the SSLS is built from the superposition of the digraphs related to each mode. In order to study the properties of the system associated to a specific mode q, we have to restrict the edge set to E 0 ∪ E q . In this context, many of the functions and specific vertex subsets, defined below, present an index q related to the considered mode.

• Two edges e 1 = (v 1 , v 1 ) and e 2 = (v 2 , v 2 ) are v-disjoint if v 1 = v 2 and v 1 = v 2 .
• Some edges are v-disjoint if they are mutually v-disjoint. In Example 1, (x 4 , x 3 ) and (x 3 , x 1 ) as well as (u 1 , x 7 ) and (x 7 , x 6 ) are v-disjoint. It is not the case for (u 2 , x 9 ) and (u 2 , x 10 ) which have the same begin vertex and for (x 2 , x 5 ) and (x 6 , x 5 ) which have the same end vertex.

• A path P is denoted P = v s0 → v s1 → . . . → v s i , where (v s j , v s j+1 ) ∈ E for j = 0, 1, . . . , i -1. We say in this case that P covers v s0 , v s1 , . . . , v s i .

• A path is simple when every vertex occurs only once in this path.

• A cycle is a path of the form v s0 → v s1 → . . . → v s i → v s0
, where v s0 , v s1 , . . . , v s i are distinct.

• For q ∈ {1, 2}, we say that path P is included in E 0 ∪ E q if all its edges are included in E 0 ∪ E q .

• Some paths (resp. cycles) are disjoint if they have no common vertex.

• A set of disjoint cycles is called a cycle family.

• P is a Y-topped path if its end vertex belongs to Y. A Y-topped path family consists of disjoint simple Y-topped paths.

• V 1 and V 2 represent two subsets of V. We denote by card(•) the cardinality function and

V 1 \ V 2 is the set of elements in V 1 which are not in V 2 . • A path P = v s0 → v s1 → . . . → v s i is said a V 1 -V 2 path if v s0 ∈ V 1 and v s i ∈ V 2 .
Moreover, if the only vertex of P which belongs to V 1 is v s0 and the only vertex of P which belongs to

V 2 is v s i , P is called a direct V 1 -V 2 path. • For q = {1, 2}, ρ q V 1 , V 2 is the maximal number of disjoint V 1 -V 2 paths included in E 0 ∪ E q . Moreover, a set of ρ q V 1 , V 2 disjoint V 1 -V 2 paths included in E 0 ∪ E q is a maximum V 1 -V 2 linkings in E 0 ∪ E q . • For q ∈ {1, 2}, µ q V 1 , V 2 denotes the minimal number of vertices of U ∪ X ∪ Y belonging to a maximum V 1 -V 2 linking included in E 0 ∪ E q . • For q ∈ {1, 2}, V ess,q V 1 , V 2 is the vertex subset including the vertices present in all the maximum V 1 -V 2 linkings included in E 0 ∪ E q .
• For q ∈ {1, 2}, there exists a unique vertex subset noted S o q V 1 , V 2 and called minimum output separator which is the set of begin vertices of all direct

V ess,q V 1 , V 2 -V 2 paths included in E 0 ∪ E q .
IV. RESULTS

A. Preliminaries

First of all, we begin to introduce some existing results, in graphical terms, for continuous state and input observability of SSLS. Whole of these results are based on several works in ( [START_REF] Boukhobza | State and input observability for structured linear systems: a graph-theoretic approach[END_REF], [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF], [START_REF] Commault | Sensor location for diagnosis in linear structured systems with disturbances[END_REF]). It is characterized the generic dimension of the observability subspace related to the degeneration of pencil matrix for each mode q ∈ {1, 2} ( due often to invariant properties [START_REF] Van Der Woude | Zero orders and dimensions of some invariant subspaces in linear structured systems[END_REF] such as invariant zeros). In this paper, our aim, through a subdivision close to [START_REF] Boukhobza | State and input observability for structured linear systems: a graph-theoretic approach[END_REF], [START_REF] Boukhobza | Observability of switching structured linear systems with unknown input :a graph-theoretic approach[END_REF], is to express propositions to assess the observability of the discrete mode for SSLS by using some subsets emerged from subdivision of SSLS into two distinct parts. Towards this end, the following definitions are useful. Definition 3: Consider SSLS (Σ Λ ) associated to digraph G(Σ Λ ). The following vertex subsets emerge from SSLS subdivision :

• X 1,q def = x i | ρ q U ∪ {x i }, Y > ρ q U, Y ; • Y 0,q def = Y ∩ V ess,q U, Y ; • Y 1,q def = Y \ Y 0,q ;
In order to rule on discrete mode observability of SSLS, we should be able to express an algebraic equation linking only output components of Y 1,q and their derivatives. This equation has to be satisfied by only one of the two modes q ∈ {1, 2}. The particularities of each subset proposed above are detailed in [START_REF] Boukhobza | Observability of switching structured linear systems with unknown input :a graph-theoretic approach[END_REF].

Definition 4: Consider SSLS (Σ Λ ) associated to digraph G(Σ Λ ) for q ∈ {1, 2}. We associate integer β q (Y) defined by µ q U, (S o q U, Y ∩ X) ∪ Y 0,q -ρ q U, (S o q U, Y ∩ X) ∪ Y 0,q plus the maximal number of vertices of X 1,q ∪ S o q U, Y covered by a disjoint union of : -a S o q U, Y -Y 1,q (Y) linking of maximal size; -a Y 1,q -topped path family ; -a cycle family covering only elements of X 1,q . As expressed in Lemma 3 of [START_REF] Boukhobza | Observability of switching structured linear systems with unknown input :a graph-theoretic approach[END_REF], β q (Y) is equal to the generic dimension of the observable subspace in the extended state and input space (x T , u T ) for each q ∈ {1, 2}.

Definition 5: (strongly connected component) Two vertices v i and v j are said to be strongly connected if it exists a path from v i to v j and a path from v j to v i .It is assumed that a vertex is strongly connected to itself. The relation " is strongly connected to " is an equivalence relation and we can define its equivalence classes. Each equivalent class is called a strongly connected component Definition 6: (maximal elements subset) Let's " ≤ " a partial order relation on S, {a, b} ∈ S and a ≤ b. a is a maximal element of S if a = b. A set of maximal elements of S is denoted by max(S). A same definition can be formulated for a set of minimal elements of S denoted by min(S).

B. Discrete mode observability of SSLS

Hypothesis 1: SSLS is assumed to be continuous state and input observable for each mode q ∈ {1, 2}. In this part, we will treat the observability of the discrete mode for SSLS with unknown input and so based only on the measurements given by the output set Y.

Proposition 1: A sufficient condition for location observability of SSLS represented by digraph G(Σ Λ ) is:

• There exists e κ = (v i , v j ) a specific edge of one mode q ∈ {1, 2} and y i ∈ Y 1,q such that there exists y i -topped path of length strictly greater than d q (y i ) = β q y -β q (y \ {y i }) which covers e κ ended by vertex v j .

• v j belongs to a direct s o q [max(u, x 1,q ), y 1,q ]-y i path included in E 0 ∪ E q . Proof: Sufficiency: The fact that, for some q, y i belongs to Y 1,q implies that there exists a vertex subset Y u ⊆ Y 1,q \ {y i } such that ρ q S o q [max(U, X 1,q ), Y u = card(max(U, X 1,q )). This implies, from Lemma 2 of [START_REF] Boukhobza | Observability of switching structured linear systems with unknown input :a graph-theoretic approach[END_REF], that there exist a matrix G, a function ϕ and an integer ν ≤ n 1 such that the dynamics equation of subsystem (Σ 1,q ) can be put on form:

Ẋ1,q = A 1,1 + (A 1,s , B 1,1 )G X 1,q + ϕ x (Y u , Ẏu , . . . , Y (ν) u ) def = ÃX 1,q + ϕ x (Y u , Ẏu , . . . , Y (ν) u ) Y 1,q = C 1,1 + (C 1,s , D 1,1 )G X 1,q + ϕ y (Y u , Ẏu , . . . , Y (ν) u ) def = CX 1,q + ϕ y (Y u , Ẏu , . . . , Y (ν) u ) (3)
Moreover, by definition of d q (y i ), we have that, there exists a minimal subset

Ỹ ⊆ Y 1,q (Y) \ (Y u ∪ {y i }), such that ∀k ≥ d q (y i ), y (k) i = s< ki αi,sy (s) i + l | y l ∈ Ỹ n 1 s=0 α l,s y (s) l + υ(Yu, . . . , Y (n 1 ) u ) (4)
where n 1 = card(X 1,q ). Since subset Ỹ is minimal i.e. ∀y j ∈ Ỹ, β q ( Ỹ∪{y i }∪Y u )\{y j } -β q (Y u ∪ Ỹ\{y j }) > k i , then in relation ( 4), all the components of Ỹ are present. Let us denote by max(U, X 1,q ) = x j the begin vertex of the so-called path P satisfying condition of Proposition 1 (i.e. P is a y i -topped path of length k + 1 strictly greater than d q (y i ) and covering e s ) and e j the j th Euclidean vector. Relation (4) can be written as:

Ci A k e j =   s<dq(y i ) α i,s Ci A s + y l ∈ Ỹ n1 s=0 α l,s Cl Ãs + υ(Y u , . . . , Y (n1) u )   e j ( 5
)
where each non-zero component of Cl Ãs is associated to the paths arriving to y l ∈ Ỹ of length s + 1. Since all the {x j }-Ỹ ∪ {y i } paths starting from x j cover, by definition, S o q {x j }, Ỹ∪{y i } def = {x r }, then there exist k r and k such that k r + k = k and Ci Ãk e j = Ci A kr ∆ r Ãk e j where ∆ r is a diagonal matrix which has only one non-zero element ∆ r (r, r) = 1. We can do the same reasoning for each term Cl Ãs e j and so there exist s r and s such that s r + s = s and Cl Ãs e j = Cl Ãsr ∆ r Ãs e j . The fact that end vertex of e κ i.e. x belongs to a direct S o q [{x j }, Y 1,q ]-y i path implies that specific edge e κ ∈ E q belongs to a S o q v P , Ỹ ∪ {y i } -Ỹ ∪ {y i } path. This means that edge e κ appears in only some S o q max(U, X 1,q ), Ỹ ∪ {y i } -Ỹ ∪ {y i } paths. Thus, some terms Ci A kr and Cl Ãsr , but not all, contain the nonzero parameter corresponding to edge e κ , which is specific to mode q. Denoting by C r = e T r , where e r is the r th Euclidean vector, we have that Ci Ãk e j = Ci A kr ∆ r Ãk e j = α C r Ãk e j and Cl Ãs e j = Cl Ãsr ∆ r Ãs e j = α l,s C r Ãs e j . Thus, after substitution of the previous terms in relation (??),

α Cr A k ej = sr ≤s<dq (y i ) α i,s αi,sCr A s-sr + l | y l ∈ Ỹ n 1 s=sr α l,s α l,s Cr Ãs-sr + υ(Yu, Ẏu, . . . , Y (n) u ) ej (6)
where some coefficients α and α l,s but not all depend on the weight of e κ . This weight cannot be factorized and simplified because all the coefficients do not depend on it (some S o q max(U, X 1,q ), Ỹ ∪ {y i } -Ỹ ∪ {y i } paths do not contain edge e κ ). Therefore, equality ( 6) is valid only if some of the coefficients α, α i,s and α l,s depend also on the weight λ κ of e κ . Thus, by means of equation ( 4) in which appear coefficients α i,s and α l,s , we obtain an algebraic relation depending on λ κ and satisfied only when the discrete mode variable is equal to q.2 In Example 1 above, a partial order of strongly connected components for both modes q ∈ {1, 2} is:

• y 1 ≤ x 1 ≤ x 3 ≤ x 4 . • y 2 ≤ x 2 ≤ x 3 ≤ x 4 . • y 3 ≤ x 5 ≤ x 2 ≤ x 3 ≤ x 4 . • y 4 ≤ x 5 ≤ x 2 ≤ x 3 ≤ x 4 . • y 3 ≤ x 5 ≤ x 6 ≤ x 7 ≤ u 1 . • y 4 ≤ x 8 ≤ x 5 ≤ x 6 ≤ x 7 ≤ u 1 . • y 4 ≤ x 8 ≤ x 9 ≤ u 2 . • y 5 ≤ x 10 ≤ u 2 . and then we have that X 1,1 = X 1,2 = {x 1 , x 2 , x 4 , x 8 , x 9 , x 10 }, Y 0,1 = Y 0,2 = 0, Y 1,1 = Y 1,2 = Y and max(U, X 1,q ) = {u 1 , u 2 , x 4 } thus S o q max(U, X 1,q ), Y 1 = {u 2 , x 3 , x 5 }. As example, (x 3 , x 1
) is a specific edge to mode 1. Since, for both modes, S o q U, Y ∩ X = {x 5 }, we can then calculate

µ q U, (S o q U, Y ∩ X) ∪ Y 0,q -ρ q U, (S o q U, Y ∩ X) ∪ Y 0,q = 4 -1 = 3. In this case, we have that d 1 (y 1 ) = β 1 Y -β 1 (Y \ {y 1 }) = 12 -11 = 1, this implies that output y 1 allows us to observe d 1 (y 1 ) = 1 new directions.
Let us search a y 1 -topped path P which length is strictly greater than d 1 (y 1 ) and including specific edge (x 3 , x 1 ), we can choose P = x 3 → x 1 → y 1 , whose length is equal to 2. We also have that the ending vertex x 1 of the specific edge (x 3 , x 1 ) for mode 1 belongs to a S o q [max(U, X 1,q ), Y 1,q ]y 1 path. So, Conditions of proposition 1 are satisfied. In the same manner, if we take (u 2 , x 9 ) as a specific edge of mode 2, we have

d 1 (y 4 ) = β 1 Y -β 1 (Y \ {y 4 }) = 12 -10 = 2.
Let us find a path P of length strictly greater than d 1 (y 4 ) and including specific edge (u 2 , x 9 ), we can choose P = u 2 → x 9 → x 8 → y 4 which length is equal to 3. We have also that the ending vertex x 9 of the specific edge (u 2 , x 9 ) belongs to a S o q [max(U, X 1,q ), Y 1,q ]-y 4 path. (So, conditions of proposition 1 are satisfied). When the proposition 1 is not satisfied, an additional sensor is required to recover discrete mode observability of SSLS. To do so, we define a new output vector Z representing the additional sensors collecting new measurements z(t) = H λ x (r t )x(t) + H λ u (r t )u(t). The completed system is denoted by Σ c Λ and a structured state-space form is as following:

Σ c Λ : ẋ(t) = A λ (rt)x(t) + B λ (rt)u(t) y(t) = C λ (rt)x(t) + D λ (rt)u(t) z(t) = H λ x (rt)x(t) + H λ u (rt)u(t) (7)
The additional sensor components can be represented by vertex set Z and edge subsets H x -edges and H u -edges. Proposition 2: Consider SSLS (Σ Λ ) associated to digraph G(Σ Λ ), when conditions of Proposition 1 are not satisfied. Let v i ∈ V i be the ending vertex of a specific edge associated to one mode q ∈ {1, 2} which belongs to any direct max(U, X 1,q ) -S o q [max(U, X 1,q ), Y 1,q ] path. In order to ensure that v i belongs to any direct S o q [max(U, X 1,q ), Y 1,q ] -Y 1,q path, an additional sensor z i ∈ Z has to be placed on vertex v i or on v j ∈ V j such that V i ≤ V j . After sensor placement, the length condition has to be checked in order to satisfy Proposition 1.

Proof. Let v i ∈ V i be the ending vertex of a specific edge for one mode q ∈ {1, 2} and v j ∈ V j such that v i and v j belong to any direct max(U, X 1,q ) -S o q [max(U, X 1,q ), Y 1,q ] path and V i ≤ V j . A sensor placement z i ∈ Z on v i ∈ V i such that S o q [max(U, X 1,q ), Y 1,q ] ≤ V i makes elements from S o q [max(U, X 1,q ), Y 1,q ] non essential. it is due to the addition of a new direct max(U, X 1,q ) -{z i } path which covers only v i (it can be the latest essential vertex in max(U, X 1,q )-{z i }) and then S o q [max(U, X 1,q ), Y 1,q ] ≤ S o q [max(U, X 1,q ), Y 1,q ∪ {z i }], so, v i belongs to a direct S o q [max(U, X 1,q ), Y 1,q ∪ {z i }]-Y 1,q path. The same reasoning can be done when an additional sensor z j ∈ Z is placed to measure v j ∈ V j such that V i ≤ V j .

Comments and interpretation

An additional sensor does not add a path from input U to output Y and so the cardinality of minimal output separator does not increase. The aim of proposition 2 is to formalize sensor placement problem in order to have the ending vertex of specific edge belonging to a direct S o q [max(U, X 1,q ), Y 1,q ]y i path included in E 0 ∪ E q under constraint that the length condition have to be checked after this placement. A length condition can be satisfied after a finite sensor placement iterations which is estimated as a number of vertices located at distance of y i , this distance is equal to the length of max(U, X 1,q ) -y i which covers specific edge. Ending vertex x 3 of specific edge (x 4 , x 3 ) of mode 1 and ending vertex x 6 of a specific edge (x 7 , x 6 ) of mode 2 do not belong respectively to S o q [max(U, X 1,q ), Y 1,q ]-y 1 path and S o q [max(U, X 1,q ), Y 1,q ]-y 4 path for both modes q ∈ {1, 2}. So the condition of Proposition 1 is not satisfied.

In order to satisfy these conditions to recover the discrete mode observability of SSLS of example 2, spreading procedure of Proposition 2 is needed.

• For mode 1, if an additional sensor z 1 is placed to measure state vertex x 4 then x 3 belongs to a S o q [max(U, X 1,q ), Y 1,q ]-y 1 path. After that , the length condition should be verified. We have that d

1 (y 1 ) = β 1 Y ∪ {z 1 } -β 1 (Y \ {y 1 }) = 12 -11 = 1.
We choose then a y 1 -topped path P = x 4 → x 3 → x 1 → y 1 which covers specific edge (x 4 , x 3 ) of mode 1 and its length is greater than 2. Condition of Proposition 1 is then satisfied.

• For mode 2, if an additional sensor z 2 is placed to measure state vertex x 7 or u 1 then x 6 belongs to a S o q [max(U, X 1,q ), Y 1,q ]-y 4 path. After that , the length condition should be verified. We have that d

2 (y 4 ) = β 2 Y ∪ {z 2 } -β 2 (Y \ {y 4 }) = 12 -10 = 2.
We choose then a y 4 -topped path P = x 7 → x 6 → x 5 → x 8 → y 4 which covers specific edge (x 7 , x 6 ) of mode 2 and its length is greater than 3. The condition of Proposition 1 is then satisfied. Figure 3

max(U, X 1,q ), Y 1 ∪ {z 1 , z 2 } = {u 2 , x 4 , x 7 }.

C. Algorithmic aspect and complexity

The evaluation of the complexity of an algorithm plays a key role in its effectiveness in treating data.The efficiency of an algorithm is strongly linked to the analysis of the amount of time taken by algorithm to run (time complexity) independently of any hardware or software support or storage locations (space complexity) in order to estimate memory space required for implementation. Estimating complexity of the algorithms proposed to verify discrete mode observability is estimated as follows:

Step belongs to a direct S o q [max(U, X 1,q ), Y 1,q ]-y i path for some y i ∈ Y 1,q then go to Step 5, else sensor placement procedure from Proposition 2 is needed and go to Step 1. For this step, we use Dijkstra's algorithm whose complexity order equals to O(|V | 2 ).

Step 5:If the length condition is satisfied then Proposition 1 is satisfied else a iterative sensor placement procedure is needed until satisfying the length condition. The evaluation of length condition requires an algorithm of complexity order O(|V | 6 ) [START_REF] Boukhobza | Observability of switching structured linear systems with unknown input :a graph-theoretic approach[END_REF]. Therefore all the algorithms proposed above have a polynomial complexity and thus the conditions mentioned in this article can be implemented using a polynomial complexity order algorithm O(|V | 6 ).

V. CONCLUSION

This paper proposes, through an intuitive graphical approach, a sufficient condition to investigate discrete mode observability of switching structured linear systems with unknown input. Under assumption that continuous state and input of SSLS are observable as it is widely treated in [START_REF] Boukhobza | State and input observability for structured linear systems: a graph-theoretic approach[END_REF], we propose a graphical criterion of sensor placement to recover the discrete mode observability of SSLS when this property is not satisfied. Rule on this property, only through the knowledge of the structure of the system, makes our approach interesting for the analysis of large scale systems using graph-theoretical techniques. Finally, two examples have been presented to illustrate the usefulness of the theoretic results.

Fig I :

 : Fig I:Hybrid Dynamical System's structure

Fig. 1 .

 1 Fig. 1. Digraph associated to system of Example 1

2 Consider

 2 Example 2 which keeps the same digraph structure of example 1 and consider new entries A λ 1 (3, 4) = λ 21 for mode 1 and A λ 2 (6, 7) = λ 22 for mode 2. The figure below shows the digraph's structure of example 2. Note that the

Fig. 2 .

 2 Fig. 2. Digraph associated to system of Example 2

  illustrates sensors placement of example 2 to recover the discrete mode discernability.

Fig. 3 .

 3 Fig. 3. Sensor placement recovering discrete mode observability of SSLS

  0:Identification of strongly connected components of G(Σ Λ ) using Tarjan's algorithm with O(|V | + |E|) time complexity (|V | and |E| denote respectively cardinality of vertex set and edge set of digraph). Step 1:Scheduling strongly connected components of G(Σ Λ ) by selection sort algorithm with O(n 2 ) time complexity (n: number of strongly connected components in digraph of SSLS). Step 2:Identification of output separator by Denic, Edmonts and Karp algorithm (D.E.K) with O(|V | 2 .|E|) time complexity. Step 3:Evaluating the location of ending vertices of specific edges for each mode relative to the output separator specified in proposition 1 and proposition 2, the evaluation can be done by Depth-first search (DFS) with O(|V | + |E|) time complexity. Step 4:If ending vertex of specific edge of mode q ∈ {1, 2}