Pierre-Cyrille Héam
email: pierre-cyrille.heam@inria.fr

Vincent Hugot
email: vincent.hugot@inria.fr

Olga Kouchnarenko
email: olga.kouchnarenko@inria.fr

Loops and Overloops for Tree-Walking Automata

Keywords: Tree-Walking Automata, loops, overloops, membership, emptiness, approximation

Tree-Walking Automata (TWA) have lately received renewed interest thanks to their tight connection to XML. This paper introduces the notion of tree overloops, which is closely related to tree loops, and investigates the use of both for the following common operations on TWA: testing membership, transformation into a Bottom-Up Tree Automaton (BUTA), and testing emptiness. Notably, we argue that the transformation into a BUTA is slightly less straightforward than was previously assumed, show that using overloops yields much smaller BUTA in the deterministic case, and provide a polynomial over-approximation of this construction which detects emptiness with surprising accuracy against randomly generated TWA.

Introduction

Tree-Walking Automata (TWA for short) are a well-established sequential model for recognising tree languages which was introduced in 1969 by Aho and Ullman [START_REF] Aho | Translations on a context free grammar[END_REF]. While TWA originally received far less attention than the better known branching model of tree automata, they have been steadily gathering interest in the last few years. Notably, important questions which had remained open for decades have recently been closed. This renewed interest is owed in great part to the ever-growing popularity of XML, with which they and their variants are tightly connected, in particular through Core XPath [START_REF] Cate | Transitive closure logic, nested tree walking automata, and XPath[END_REF] and streaming [START_REF] Segoufin | Validating Streaming XML Documents[END_REF].

In this context, it becomes helpful to have reasonably efficient algorithms for essential operations on TWA such as deciding membership and emptiness, as well as the transformation into a BUTA. Until now, research has been mainly focused on closing fundamental open problems concerning the expressiveness of TWA [START_REF] Bojańczyk | Tree-walking automata do not recognize all regular languages[END_REF][START_REF] Bojańczyk | 1-bounded TWA cannot be determinized[END_REF][START_REF] Bojańczyk | Tree-walking automata cannot be determinized[END_REF]. While algorithms for the above operations are known, they appear in print mostly as proof sketches, and there has been no focus on finding tighter complexity bounds. In contrast, this paper provides explicit algorithms for these tasks and deals with complexity issues. The common thread of our contributions is the notion of tree loop, which is pervasive to the algorithms we give. This notion is closely related to Knuth's construction for testing circularity of attribute grammars [START_REF] Knuth | Semantics of context-free languages[END_REF], and is a generalisation to trees of a similar construction for two-way word automata [START_REF] Shepherdson | The reduction of two-way automata to one-way automata[END_REF]. The contributions are organised as follows: Section 3.1 [p4] gives a thorough introduction to tree loops -the basic idea of which is more or less folklore -and introduces a new notion of tree overloop in Sec. 3.3 [p7] . Simple algorithms for testing membership follow naturally from this work; beyond the immediate application of the recursive definitions of loops and overloops, a more efficient method based on a Boolean matrix encoding of loops is given in Sec. 3.2 [p6] . To the best of our knowledge, no such algorithm existed in the literature. Section 4 deals with the transformation from TWA to BUTA, based on the proof sketches in [START_REF] Bojańczyk | Tree-Walking Automata, LATA'08[END_REF] and [10, p143]. Two variants are given in Sec. 4.1: one using loops and one using overloops. Section 4.2 [p11] proceeds to show that, in the deterministic case, the overloops-based construction admits a much smaller upper bound on the number of generated states.

The emptiness problem is known to be ExpTime-complete for TWA, and is traditionally tested by first transforming the TWA into a BUTA. Section 5 provides a polynomial-time algorithm which computes an "overapproximation" of this BUTA, and thus may decide emptiness positively. Should it prove inefficient against some families of TWA, then the approximation can be refined as much as needed. Section 6 [p15] presents random experiments performed to confirm our theoretical results. They involve both an ad-hoc random generation scheme for non-deterministic TWA, and a more interesting one, based on the results of [START_REF] Héam | Random Generation of Deterministic Tree (Walking) Automata[END_REF], which yields complete and deterministic TWA according to the uniform probability distribution -which imparts statistical significance to our results. The dependability of the approximation method developed in Sec. 5 is tested in Sec. 6.1 -it is shown to be astonishingly accurate against both schemes. Section 6.2 [p16] compares the respective sizes of the BUTA obtained from the loops and overloops-based transformations, and shows that overloops yield much smaller BUTA than loops in average. It is also shown that this size gain is independent of (and cumulates with) post-processing cleanup (cf. [START_REF] Heam | Random Generation of Positive TAGEDs wrt. the Emptiness Problem[END_REF]) of the BUTA. The ideas of these tests are illustrated on our running example, then validated against the above-mentioned uniform random generation scheme.

Note. This paper is an extended version of [START_REF] Héam | Loops and overloops for tree walking automata[END_REF].

Preliminaries

Let R ⊆ Q 2 be a binary relation on a set Q; we denote by R + and R * its transitive and reflexive-transitive closure, respectively. The notation n, m stands for the integer interval { n, n + 1, . . . , m }.

We denote by N * the set of words over N; if v, w ∈ N * , then v.w stands for the concatenation of the words v and w. A binary alphabet is a finite set of symbols, equipped with an arity function arity : Σ → {0, 2}. The subset of symbols of Σ with arity k is denoted by Σ k . The set T (Σ) of (binary) trees over Σ is defined inductively as the smallest set such that Σ 0 ⊆ T (Σ) and, if f ∈ Σ 2 and u 0 , u 1 ∈ T (Σ), then f (u 0 , u 1 ) ∈ T (Σ). If t ∈ T (Σ) is a tree, then the set of positions (or nodes)

Pos(t) ⊆ N * is defined inductively by Pos(t) = {ε} if t is a constant (i.e. t ∈ Σ 0 ) and Pos f (u 0 , u 1 ) = {ε} ∪ { k.α k | k ∈ 0, 1 and α k ∈ Pos(u k ) } otherwise.
We see a tree t as a function t : Pos(t) → Σ which maps a position to the symbol at that position in t. Positions are equipped with a non-strict (resp. strict) partial order (resp. ), such that α β iff β is a prefix of α (resp. α β and α = β). The size of a tree t is denoted by t and defined by t = |Pos(t)|. The parent function p(•) : Pos(t) \ {ε} → Pos(t) maps any (non-root) child node α.k (where k ∈ { 0, 1 }) to its father α. We denote by t|α the subtree of t under α. The reader is assumed to be well-acquainted with the bottom-up variety of branching tree automata (see for instance [START_REF] Comon | Tree automata techniques and applications[END_REF]).

A Tree-Walking Automaton (TWA) can be thought of intuitively as a head moving in the tree from father to son and from son to father. The head chooses its next move based on its internal state, the symbol at its current position, and whether its current position is the root of the tree, a left son, or a right son. A TWA accepts a tree if, starting from the root in an initial state, its head can move back to the root in a final state.

Formally, a TWA is a tuple A = Σ, Q, I, F, ∆ where Q is a finite set of states, Σ a binary alphabet, I ⊆ Q is a set of initial states, F ⊆ Q a subset of final -or accepting -states, and

∆ ⊆ Σ × Q × { , 0 , 1 } T : types × { ↑, , , } M : moves
×Q is a set of transitions. In this paper the tuple Σ, Q, I, F, ∆ will be assumed whenever we speak of a TWA A. Each node α of a tree t has a type in T, denoted by α, such that ε = (root), (β.0) = 0 (left son), (β.1) = 1 (right son). As we will seldom deal with the root in practice, we define for short the sons S = { 0 , 1 } ⊂ T. We will also put in relation types and moves through the function χ(•) : S → { , } such that χ(0 ) = and χ(1 ) = . For our convenience, we will take the special notation f, p, τ → µ, q for the tuple (f, p, τ, µ, q) ∈ ∆. Some of the parameters can be replaced by sets, with the obvious meaning that we consider the set of all transitions thus described. For instance Σ 2 , p,

T → , q = { (σ, p, τ, , q) | σ ∈ Σ 2 , τ ∈ T }. Note that all the transitions from Σ 0 , Q, T → { , }, Q ∪ Σ, Q, → ↑, Q are invalid. A configuration of A on a tree t is a pair c = (β, q) ∈ Pos(t) × Q; it is initial if c ∈ {ε} × I and final (or accepting) if c ∈ {ε} × F . It is a successor of a configuration (α, p) if t(α) , p, α → µ, q ∈ ∆, where µ is ↑ if β = p(α), if β = α, if β = α.0 and if β = α.1.
We write c 1 A c 2 (or simply c 1 c 2 whenever A is clear from the context) if the configuration c 2 is a successor of c 1 . A run is a sequence of successive configurations c 1 c 2 . . . c n . . .. A run is accepting (or successful) if it starts with an initial configuration and reaches a final configuration. A tree t is accepted or recognised by A if there exists an accepting run of A on t. The set of all accepted trees is the language of A, denoted by Lng (A).

Example: Let X be a TWA such that Σ 0 = { a, b, c } and Σ 2 = { f, g, h }, Q = { q , q u }, I = {q }, F = {q u }, and ∆ = a, q , { , 0 } → , q u ∪ Σ, q u , 0 → ↑, q u ∪ Σ 2 , q , { , 0 } → , q . Then X accepts exactly all trees whose leftmost leaf is labelled by a. We shall use this (trivial) example throughout the paper. X has two states and fourteen rules.

Loops, Overloops and the Membership Problem

Defining, Classifying and Computing Loops

The notion of loop turned out to be very useful to deal with TWA. Informally, loops arise naturally as a generalisation of the definition of an accepting run, where the automaton enters the root in a given initial state p in , moves along the tree, and then comes back to the root in a certain final state p out . In practice, the details of the moves which form the loop itself are largely irrelevant and are discarded: the most useful information is the pair of states (p in , p out ).

Definition 1 (Tree Loops).

Let A be a TWA, t a tree and α ∈ Pos(t). A pair of states (p, q) ∈ Q 2 is a loop of A on the subtree t|α if there exist n 0 and a run (α, p), (β 1 , s 1 ), . . . , (β n , s n ), (α, q) such that β k α for all k ∈ 1, n . Such a run is a looping run, and we say that it forms the loop (p, q). Example: The looping run (0, q ), (0.0, q ), (0.0, q u ), (0, q u ) of X on the subtree g(f (a, b), c)|0 = f (a, b) forms the loop (q , q u ).

Notice that loops are not only defined on whole trees, but on subtrees as well with the restriction that the automaton cannot leave the subtree during the looping run. It is in fact this restriction which grants loops their usefulness. TWA, unlike their branching cousins, whose runs are defined inductively, do not naturally lend themselves to inductive reasoning; and yet, thanks to the above restriction, loops are easily computed by induction. Thus loops and their variants can be thought of as convenient devices which hide the sequential, stateful aspect of TWA runs beneath a much more "user-friendly" layer of induction.

In the next few paragraphs we compute the loops of a TWA A on a subtree t|α. Definition 2 (Kinds of Loops). Clearly for all p ∈ Q, (p, p) is a loop; we call such loops trivial. A looping run of A on t|α is simple if it reaches α exactly twice. It is non-trivial if it reaches α at least twice. A loop is simple (resp. non-trivial) if there exists a simple (resp. non-trivial) looping run forming it.

Example: The loop (q , q u ) in the above example is simple, because (0, q ), (0.0, q ), (0.0, q u ), (0, q u ) only reaches α = 0 twice, on the first and last configuration. The TWA X forms only trivial and simple loops, but suppose that we alter it so that it also checks that the right-most leaf is a. During an accepting run it would go down and left, back up to the root, down and right, and back up to the root again, in a final state. Thus all accepting runs would be non-trivial and non-simple, reaching the root exactly three times.

Fortunately, we only ever need to compute simple loops, as we can deduce the rest from them thanks to the following lemma:

Lemma 3 (Loop Decomposition). If S ⊆ Q 2 is
the set of all simple loops of A on a given subtree u = t|α, then S * is the set of all loops of A on u.

Proof. Every looping run is either trivial or non-trivial. All trivial loops are in S * by the reflexive closure. Furthermore, every non-trivial looping run can easily be decomposed into one or more simple runs. Indeed, any non-trivial looping run has the following general form, where β k i α for all k, i, and the notation [x k ] k∈ 1,m designates the run obtained by concatenating the runs x 1 , . . . , x m :

= (α, p 0 ), (β k 1 , s k 1 ), . . . , (β k n k , s k n k ), (α, p k ) k∈ 1,m
. This is the composition of m simple looping runs k , for k ∈ 1, m , forming the simple loops (p k-1 , p k ). The remaining loops are obtained by transitive closure:

(p k-1 , p k ) k ∈ 1, m + = (p k-1 , p l ) k, l ∈ 1, m , k l .
Let us denote by τ (u) the set of all loops of A on a subtree u, where τ is the type of the root of u; if u is the subtree t|α then τ = α. Note that thanks to the above-mentioned restriction in the definition of loops, the type of the subtree's root is the only information which is actually needed from the context.

Let a ∈ Σ 0 be a leaf of type τ . We compute the loops on a. By definition of a looping run, A cannot move up; nor can it move down since leaves have no children. So the only transitions which can be activated are -transitions. As we are only interested in simple loops, we can only activate one of these transitions once, thus creating runs of the form (α, p) (α, q), and the corresponding loops (p, q). Let us have a general notation for this:

Definition 4 (Simple Here-Loops). H τ σ = { (p, q) | σ, p, τ → , q ∈ ∆ } .
Thus the simple loops on a are H τ a . By Lemma 3 we have τ (a) = (H τ a ) * . We now deal with inner nodes. Let f ∈ Σ 2 , and u = f (u 0 , u 1 ); again, τ denotes the type of the root of u. Clearly the elements of H τ f are loops on u, as above, but this time A can move down as well. It cannot move up on the first move (that would mean leaving the subtree), but it will obviously need to move up to rejoin the root if it ever moves down. To clarify all that, let us reason on what the first move of a simple looping run can be. It cannot be ↑ and all simple loops whose first move is are already computed in H τ f . Say the first move is : then the run can do whatever it wants in the left subtree u 0 , after which it has to move back up to the root to complete the loop. Again, we only consider simple loops, so no move can be made past this point, as the root has been reached twice already. Thus the general form of such a run is (ε, p), (0, p 0 ), (β 1 , s 1 ), . . . , (β n , s n ), (0, q 0 ), (ε, q), with all β k 0. But by definition, this means that (p 0 , q 0 ) is a loop on u 0 , i.e. (p 0 , q 0 ) ∈ 0 (u 0 ). Needless to say, the same applies (with 1 instead of 0 ) if the first move is . It follows that to determine whether (p, q) forms a simple loop on u, we need only check three things: ( ) A can move down (left or right) from state p into a state p θ , ( ) there is a loop (p θ , q θ ) on this subtree and ( ) in state q θ , A can move up from this subtree and into the state q. Formally:

τ (u) = H τ f ∪ (p, q) ∃θ ∈ S : ∃(p θ , q θ ) ∈ θ (u θ ) st. f, p, τ → χ(θ), p θ ∈ ∆ u θ (ε), q θ , θ → ↑, q ∈ ∆ * .
Theorem 5 (Loops). Let A be a TWA and t ∈ T (Σ). Then for all α ∈ Pos(t), α (t|α), as defined above, is the set of all loops of A on t|α.

Example: For the TWA X , 0 (a) = { (q , q u ) } * = { (q , q ), (q u , q u ), (q , q u ) }, and (f (a, b)) = (∅ ∪ {(q , q u )})

* (no simple here-loop, and one loop built on the left child). On the other hand, (f (b, a)) = ∅ * , because 1 (a) = 0 (b) = ∅ * .

A Direct Application of Loops to Membership Testing

Note that a reasonably efficient algorithm for testing membership is straightforwardly derived from the above computation of loops: Corollary 6 (TWA Membership). Let A be a TWA and t ∈ T (Σ). Then we have t ∈ Lng (A) if and only if

(t) ∩ (I × F ) = ∅.
Proof. There is a loop (q i , q f ) ∈ I × F of A on t iff there is a run of the form (ε, q i ), . . . , (ε, q f ). The first configuration is initial, and the last final. Therefore it is an accepting run, and t ∈ Lng (A).

Corollary 7. The complexity of TWA membership is

O |∆| + t • |Q| 3 .
Proof. A naïve computation of (t) would be done in O t

• (|Q| 3 + |Q| 2 • |∆|) . The following algorithm, while still simple, runs in O |∆| + t • |Q| 3 , at the cost of a O( t • |Q|
2 ) space complexity. Preliminaries. Transitions and loops will be represented by relations from Q to Q, coded as matrices of M |Q| (B) within the classical Boolean algebra (B, +, •). The states of Q are numbered and assimilated to their indices 1, n for the sake of denotational simplicity.

A relation R ⊆ Q 2 is represented by the matrix M[R] = (M[R] ij ), such that M[R] ij = 1 iff jRi.
The sum and product of matrices are defined as usual.

With those conventions we have the expected result regarding composition: let

R, R ⊆ Q 2 and P = M[R ] × M[R]; then P ij = n k=1 M[R ] ik M[R] kj . Thus P ij = 1 iff there exists k such that jRk and kR i, that is to say, j(R • R)i. In other words M[R • R] = M[R ] × M[R]. Input & Variables.
A TWA A and a tree t form the input. The core of the algorithm is the sub-function f , which takes as input α (a position in Pos(t)). Its call defines a matrix L α , representing the loops at position α. Algorithm. Initialisation. For each σ ∈ Σ, τ ∈ T, µ ∈ M, a matrix T σ,τ,µ is built such that T σ,τ,µ qp = 1 iff σ, p, τ → µ, q ∈ ∆. The positions of Pos(t) are topologically ordered as α 1 , . . . , α m = ε. Body. 3 . Correctness. After the call to f (α), it is plain that L α encodes α (t|α), as the computation of ( ) and ( ) is a straight-forward reformulation of the formula of Thm. 5 [p6] in terms of a Boolean matrix representation. The recursive nature of that formula has been unwound in this algorithm by the prior topological sorting of the positions.

For k = 1 to m, f (α k ) is called. Then L ε is returned. On a call to f (α): ( ) Populate the matrix L α = T t(α), α, + θ∈S T t(α.θ), (α.θ),↑ × L α.θ × T t(α), α,χ(θ) . ( )

From Loops to Overloops

We now introduce a new notion related to tree loops: tree overloops. An overloop is formed by a looping run followed by a move up; this apparently minor change has a number of positive consequences which we discuss in the next sections.

Definition 8 (Over-Root, Extended Positions and Transitions). The extended positions Pos(t) of a tree t ∈ T (Σ) are the set Pos(t) ∪ {ε}, where ε is called the overroot. The parent function p(•) is extended over Pos(t) into the extended parent function p(•), such that p(ε) = ε and ε ε. The notion of configuration is extended as well, so that the transitions of Σ, Q, → ↑, Q become valid. Their application yields configurations of the form (ε, q). Definition 9 (Tree Over-Loops). Let A be a TWA and t a tree. A pair of states (p, q) ∈ Q 2 forms an overloop of A on t|α if there exists a run (α, p), (β 1 , s 1 ), . . . , (β n , s n ), (p(α) , q) such that β k α for all k ∈ 1, n .

A way to compute overloops is to compute loops, then check for ↑-transitions:

Definition 10 (Up-Closure). Let L ⊆ Q 2 , τ ∈ T and σ ∈ Σ: U τ σ [L] = (p, q) ∈ Q 2 ∃p ∈ Q : (p, p ) ∈ L and σ, p , τ → ↑, q ∈ ∆ .
Lemma 11 (Up-Closure). Let A be a TWA. If L is the set of all loops of A on a subtree u = t|α, then U α t(α) [L] is the set of all overloops of A on u.

Proof. Immediate from Def. 9, as we have necessarily β n = α. Thus any overloop is a loop followed by a move up, and conversely.

Similarly to loops, we denote by ↑ τ (u) the set of all overloops of A on a subtree u, where τ is the type of the root of u. By Lem. 11 we have ↑ τ (u) = U τ u(ε) [ τ (u)], and in the case of leaves this yields ↑ τ (a) = U τ a [(H τ a ) * ]. However, in the case of inner nodes (say u = f (u 0 , u 1 )), in order to have an inductive computation of overloops instead of one based on loops, we need to compute the overloops of the father, knowing the overloops of the children. The simplest way is to compute the loops of the father and take the up-closure. We only need to check whether ( ) the automaton can go down and left (resp. right) from p to a state p 0 and ( ) there is a left (resp. right) overloop (p 0 , q 0 ): this forms a loop (p, q 0 ). Formally:

↑ τ (u) = U τ f H τ f ∪ (p, q θ ) ∃θ ∈ S : ∃p θ ∈ Q st. f, p, τ → χ(θ), p θ ∈ ∆ and (p θ , q θ ) ∈ ↑ θ (u θ ) * .
Theorem 12 (Overloops). Let A be a TWA and t ∈ T (Σ). Then for all α ∈ Pos(t), ↑ α (t|α), as defined above, is the set of all overloops of A on t|α.

Example: For the TWA X , ↑ 0 (a) = U 0 a 0 (a) = {(q u , q u ), (q , q u )}. However (f (a, b)) is the empty set. Thus a small adjustment is needed to test membership using overloops, as standard TWA -such as X -never admit any overloop at the root of a tree, for the lack of ↑-transitions.

Definition 13 (Overfinal State & Escaped TWA).

Let A = Σ, Q, I, F, ∆ be a TWA; it can be transformed into an escaped TWA

A = Σ, Q { } , I, F, ∆ Σ, F, → ↑, ,
where / ∈ Q is a fresh state, called overfinal state. [Clearly Lng (A) = Lng (A ).]

Example: Once X is escaped, we have ↑ (f (a, b)) = { (q u , ), (q , ) }.

Corollary 14 (TWA Membership Redux ). Let A be an escaped TWA and t ∈ T (Σ).

Then t ∈ Lng (A) if and only if ↑ (t) ∩ (I × { }) = ∅.
Proof. The couple (q i , ) ∈ I × { } is an overloop iff there is a run (ε, q i ), . . . , (ε, q f ), (ε, ). By Def. 13, we must have q f ∈ F ; therefore, by Cor. 6 we have immediately t ∈ Lng (A).

Transforming TWA into equivalent BUTA

It is well-known that every TWA is equivalent to a BUTA; a more general version of this result has been proven in [START_REF] Cosmadakis | Decidable optimization problems for database logic programs[END_REF] -using game-theoretic arguments -and the main idea of a loop-based transformation from TWA into BUTA is outlined in [START_REF] Bojańczyk | Tree-Walking Automata, LATA'08[END_REF] and [10, p143]. In this section we present two versions of it: the classical, loop-based one (Algo.

Data: A TWA A = Σ, Q, I, F, ∆ Result: A BUTA B such that Lng (B) = Lng (A)
Meta-Algorithm 1 where

P init ≡ (a, τ, H τ a * ) P indu ≡ (f, τ, (H τ f ∪ S) * ) P 0 ≡ (σ 0 , 0 , S 0 ) P 1 ≡ (σ 1 , 1 , S 1 ) F ≡ { (σ, , L) ∈ States | L ∩ (I × F ) = ∅ } S = (p, q) ∃θ ∈ S, (p θ , q θ ) ∈ S θ : f, p, τ → χ(θ), p θ ∈ ∆ and σ θ , q θ , θ → ↑, q ∈ ∆
P init ≡ (τ, U τ a [H τ a * ]) P indu ≡ (τ, U τ f (H τ f ∪ S) * ) P 0 ≡ (σ 0 , S 0 ) P 1 ≡ (σ 1 , S 1 ) F ≡ { ( , O) ∈ States | O ∩ (I × { }) = ∅ } S = (p, q θ ) ∃θ ∈ S, p θ ∈ Q : f, p, τ → χ(θ), p θ ∈ ∆ and (p θ , q θ ) ∈ S θ
Algorithm 3: Tranformation into BUTA, with overloops instantiations of Meta-Algorithm 1, whose inputs (between angle brackets • ) are substituted into its body. We go on to show that, in the case of deterministic TWA, the overloop-based construction results in much smaller equivalent BUTA than the classical one.

Two Variants: Loops and Overloops

Lemma 15 (Loop-Based Algorithm). Let A be a TWA, B the BUTA constructed by Algorithm 2, t ∈ T (Σ) and a position α ∈ Pos(t). Then for every type τ ∈ T there is a unique run ρ of B on t|α, which is such that ρ(ε) = (t(α), τ, τ (t|α)).

Proof. By structural induction on u = t|α. Base Case:

u = a ∈ Σ 0 . By line A in Algorithm 2, ρ(ε) = P = (a, τ, H τ a * ) = (t(α), τ, H τ a *
). This is the only possible run, as only one transition a → P is generated for each couple a, τ . By Theorem 5 we have H τ a * = τ (a). Inductive Case: u = f (u 0 , u 1 ). By induction hypothesis the run ρ 0 on u 0 is such that ρ 0 (ε) = P 0 = (u 0 (ε), 0 , 0 (u 0 )), and the run ρ 1 on u 1 is such that ρ 1 (ε) = P 1 = (u 1 (ε), 1 , 1 (u 1 )). By line B in Algo. 2 we use the rule f (P 0 , P 1 ) → P to build a run ρ such that ρ(ε

) = P = (f, τ, (H τ f ∪ S) * ) = (u(ε), τ, (H τ f ∪ S) *
), ρ|0 = ρ 0 and ρ|1 = ρ 1 . Since ρ 0 and ρ 1 are unique, so is ρ. By Theorem 5, (H τ f ∪ S) * = τ (u).

Theorem 16. Algorithm 2 is correct; that is, Lng (A) = Lng (B).

Proof. The following statements are equivalent by Lem. 15 and Cor. 6: ( ) t ∈ Lng (A) ( ) there is a loop (q i , q f ) ∈ I × F of A on t ( ) the run ρ of B on t is such that ρ(ε) = (t(ε), , (t)), with (q i , q f ) ∈ (t) ( ) ρ(ε) is a final state for B ( ) t ∈ Lng (B).

Two short but important remarks are in order. First: it might seem strange that our states are in Σ × T × 2 Q 2 , and not more simply in T × 2 Q 2 , as suggested in [START_REF] Samuelides | Automates d'arbres à jetons[END_REF]. In [START_REF] Bojańczyk | Tree-Walking Automata, LATA'08[END_REF] a similar construction -albeit deterministic, see the second remark -is proposed, which does not include Σ either. However, it is not clear how loops could be considered independently from the root symbol of the subtree that bears them. Consider for instance a, b ∈ Σ 0 with only the transitions { a, b } , p, τ → , q and b, q, τ → ↑, s ∈ ∆. Then the loops on a and b are exactly the same -{(p, q)} * -and yet, from their father's point of view, they behave very differently. If A can go down from a state s to p, it can form a loop (s, s ) if the child is b, but not if it is a. In contrast to the loop-based construction, the overloop-based algorithm (Algo. 3) suppresses this problem completely.

Second: the observation made in Lemma 15 that the run of B is unique, given a subtree and a type, makes it easy to adapt the algorithm to yield a deterministic BUTA. Indeed, every tree in T (Σ) is non-deterministically evaluated by B into exactly three possible states (one per type); the correct one is chosen according to the context during the run. Recall that rules f (P 0 , P 1 ) → P are built such that the "type" component of P θ is θ, and final states bear the root type . Hence, it suffices to group those three possible states into one element of Σ × (2 Q 2 ) |T| to achieve determinism3 , which brings us back to the states suggested in [START_REF] Bojańczyk | Tree-Walking Automata, LATA'08[END_REF].

Lemma 17 (Overloop-Based Algorithm). Let A be a TWA, B the BUTA constructed by Algorithm 3, t ∈ T (Σ) and a position α ∈ Pos(t). Then for every type τ ∈ T there is a unique run ρ of B on t|α, which is such that ρ(ε) = (τ, ↑ τ (t|α)).

Proof. See proof of Lemma 15. The only change is that this time, we build the loops, then deduce the overloops from them (Lem. 11 [p7] , Thm. 12).

Theorem 18. Algorithm 3 is correct; that is, Lng (A) = Lng (B).

Proof. By construction (i, ) ∈ I × { } is an overloop iff there exists f ∈ F such that (i, f ) is a loop. Same proof as Theorem 16.

Note that this construction can be adapted to yield deterministic BUTA in exactly the same way as for Algo. 2.

Overloops and the Deterministic Case: an Upper-Bound for the Size Definition 19 (Deterministic TWA). A TWA

A = Σ, Q, I, F, ∆ is deterministic (ie. a DTWA) if 4 | σ, p, τ → M, Q ∩ ∆| 1 for all σ ∈ Σ, p ∈ Q, τ ∈ T.

Example:

The running example TWA X happens to be a deterministic TWA.

Definition 20 (Functional Relation).

A relation R ⊆ Q 2 is functional (or rightunique, or a partial function) if, for all p, q, q ∈ Q, pRq and pRq =⇒ q = q .

Remark 21. There are 2 The idea is that every state which we build corresponds exactly to the set L of all loops (resp. overloops) of the automaton A on a certain subtree u. Since L ⊆ Q 2 , we can see it as a binary relation on the states. The intuition here is that, if A is deterministic, and enters the root of u in one given state p, then there "should be" only one possible outcome. More formally:

Lemma 24. If A is a deterministic TWA, then A is functional.

Proof. In a given configuration (α, p), over a tree t, | t(α), p, α → M, Q ∩ ∆| 1. Therefore, (α, p) has at most one successor.

However, in the case of loops, this does not suffice to make L functional because, determinism notwithstanding, a single (non-trivial) loop may reach the root several times, and in different states, before exiting the subtree. Thus there is nothing to prevent us from having both pLq and pLq , for q = q ; we show next that in that case, one of these loops is simply an extension of the other.

Lemma 25 (Hidden Loops). Let (p, q) and (p, q ) be loops of the TWA A on a given subtree t|α, such that q = q . Then if A is deterministic, either (q, q ) or (q , q) must be a loop of A on t|α.

Proof. By Definition 1, there exist two runs c 0 , . . . , c n and d 0 , . . . , d m such that c 0 = d 0 = (α, p), c n = (α, q) and d m = (α, q ). If n = m then c 0 n c n and c 0 n d n and by Lemma 24 and Remark 22, it follows that c n = d m . But this contradicts q = q , so we must have n = m. Say that n < m. Then c n = d n , and (α, q) = d n , . . . , d m = (α, q ) forms a run. Therefore (q, q ) is a loop. Similarly, if n > m, then by the same arguments (q , q) is a loop. Contrariwise, two overloops cannot be combined to form another overloop on the same subtree, which satisfies the above intuition of a "single outcome": Lemma 26. Let p, q, q ∈ Q, such that (p, q) and (p, q ) are overloops of the TWA A on a given subtree t|α. Then if A is deterministic, q = q .

Proof. By Def. 9, there exist s, s ∈ Q such that (α, p), . . . , (α, s), (p(α) , q) and (α, p), . . . , (α, s ), (p(α) , q ) are runs; thus (p, s) and (p, s ) are loops. If s = s , then by Lem. 25, say, (s, s ), is a loop. So there exist s 1 , . . . , s n ∈ Q, β 1 α , . . . , β n α such that (α, s), (β 1 , s 1 ), . . . , (β n , s n ), (α, s ) is a run. Thus we have in particular (α, s) (p(α) , q) and (α, s) (β 1 , s 1 ). It follows that p(α) = β 1 α, which is contradictory. Hence s = s . We have both (α, s) (p(α) , q) and (α, s) (p(α) , q ). Since is functional (Lem. 24), we have finally q = q .

With this, we can conclude the proof of Theorem 23.

Proof of Theorem 23. By construction, for every state P = (τ, L) generated for B by Algorithm 3, there exists at least a subtree t such that L is the set of overloops of A on t. Note that the same bound (with a |Σ| factor) might be achievable using loops, if special provisions are made to determine which of two loops (p, q) and (p, q ) subsumes the other, and to remove the superfluous loops from the states as they are built. However, such provisions would be invalid if A is not deterministic, unlike the overloops method, which is applicable in all generality.

A Polynomial Over-Approximation for the Emptiness Problem

Data: An escaped TWA A = Σ, Q, I, F, ∆ (see Def. 13) Result:

Empty (only if Lng (A) = ∅) or Unknown initialise L 0 , L 1 , L to ∅; foreach a ∈ Σ 0 , τ ∈ T do L τ ← L τ ∪ U τ a [H τ a * ] repeat foreach f ∈ Σ 2 , τ ∈ T do L τ ← L τ ∪ U τ f (H τ f ∪ S) * where S = (p, q θ ) ∃θ ∈ S, p θ ∈ Q : f, p, τ → χ(θ), p θ ∈ ∆ and (p θ , q θ ) ∈ L θ until L 0 , L 1 , L remain unchanged return Empty if L ∩ (I × { }) = ∅, else Unknown
Algorithm 4: Approximation for emptiness, with overloops

Testing emptiness of a TWA A is an ExpTime-complete problem [START_REF] Bojańczyk | Tree-Walking Automata, LATA'08[END_REF]. This is rather unfortunate, as there are practical questions -such as satisfiability of some XPath fragments -which reduce to the emptiness of the language of a TWA. We present in this section a crude but fairly accurate and very expeditious overloops-based algorithm capable of detecting emptiness in a number of cases. Algorithm 4 [p13] is a variant of Algorithm 3 with the following properties:

Lemma 27 (Overloops Over-Approximation). Let A be a TWA; when the execution of Algorithm 4 ends, then for any τ ∈ T, L τ ⊇ t∈T(Σ) ↑ τ (t).

Proof. This result is fairly clear when comparing Algorithms 3 and 4. Let us consider a tree t and a subtree u = t|α, with τ = α. We show that ↑ τ (u) ⊆ L τ . Base case: u = a ∈ Σ 0 . Then by the first line of Algo. 4, we have

↑ τ (a) = U τ a [H τ a * ] ⊆ L τ . Inductive case: If u = f (u 0 , u 1 ), f ∈ Σ 2 ,
then by induction hypothesis we have ↑ 0 (u 0 ) ⊆ L 0 and ↑ 1 (u 1 ) ⊆ L 1 . The expression computed in the main loop is almost the same as that of Thm. 12 for ↑ τ (u), the only difference being that L θ is used instead of ↑ θ (u θ ). Since we have ↑ θ (u θ ) ⊆ L θ for all θ ∈ S, the expression in Algo. 4 computes at least all overloops of ↑ τ (u)and adds them to L τ . Thus ↑ τ (u) ⊆ L τ .

Theorem 28. Algorithm 4 is correct; that is, it yields Empty only if Lng (A) = ∅.

Proof. Suppose that Algo. 4 yields Empty. By definition, this is the case if and only if L ∩ (I × { }) = ∅. By Lemma 27, we have t∈T(Σ) ↑ τ (t) ⊆ L τ for all types τ , and it follows that in particular ( t∈T(Σ) ↑ (t)) ∩ (I × { }) = ∅. This can be equivalently rephrased as ∀t ∈ T (Σ), ↑ (t) ∩ (I × { }) = ∅. By Corollary 14, this translates into: for all t ∈ T (Σ) , t / ∈ Lng (A), that is to say,

Lng (A) = ∅.
| • |T| + |T| • |Q| 2 • (|Σ 2 | • |T|) times. Overall, the number of executions is in O(|Σ| • |T| 2 • |Q| 2 ). Globally, the execution time of Algo. 4 is in O(|Σ| • |T| 2 • |Q| 5
). This is of course a very loose bound.

Note that Algorithm 4 can easily be made just as coarse or as fine as the need dictates. At the coarse end of that gamut we have a variant of Algorithm 4 which forgoes type information, thus hoarding up all overloops in a single set L instead of three, and at the fine end we find something equivalent to Algorithm 3.

Experimental Results

Evaluating the Approximation's Effectiveness

Tests have been conducted against two different sets of randomly generated TWA. The first set comprised roughly twenty thousand random automata of various sizes (2 |Q| 20), with a small number of rules (|∆| ≈ 3 × |Q|) and the same alphabet as for our running example X . The random generation scheme which produced them was ad-hoc and did not have any pertinent statistical grounds. The approximation yielded astonishingly good results on this set: about 75% of the automata had empty languages, yet the approximation failed to detect emptiness in only two cases. To confirm those encouraging results, we generated a second set of (complete and deterministic5 ) TWA, this time according to a uniform probability distribution [START_REF] Héam | Random Generation of Deterministic Tree (Walking) Automata[END_REF]. The REGAL library [START_REF] Bassino | REGAL : A library to randomly and exhaustively generate automata[END_REF] was used as back-end to generate the underlying finite-state automata. More specifically, 2 000 TWA were uniformly generated for each |Q| within the range 2 |Q| 25. Figure 1 [p13] summarises the performance of the approximation on this set. The first curve presents the percentage of TWA whose language is detected to be empty by the approximation among the whole 2 000 TWA, for each |Q|. The second curve presents the same results, but only for the first 200 TWA 6 for each |Q| 10; the third curve presents the exact results for the same data as the second. It is visible that the approximation performs very well again, as the second and third curves are almost indistinguishable. Out of the 1 724 TWA for which both the approximation and an exact algorithm were run, of which 398 had empty languages, only four failures of the approximation were observed. Furthermore, the first curve shows that the approximation continues to catch cases of emptiness even for sizes completely intractable with exact algorithms. Those results, though statistically sound, are probably much better than what can be expected in practical applications; it is likely that random instances are in some sense trivial wrt. emptiness. In the absence of substantial testbeds from real-world applications of TWA, a study similar to [START_REF] Heam | Random Generation of Positive TAGEDs wrt. the Emptiness Problem[END_REF] could be conducted to flesh out the properties which would make an instance "difficult" wrt. emptiness.

Overloops Yield Smaller BUTA

Comparing the output of Algos. 2 & 3, we noted that the latter generates smaller automata. By way of example, if B l is the equivalent BUTA obtained from X by Algo. Note that the resulting automata are quite large, even for such a trivial TWA as X ! For comparison, consider the manually constructed (deterministic) minimal BUTA B m , and the7 smallest possible non-deterministic BUTA B s equivalent to the TWA X : we have B m = 56 and B s = 34. In other words, the loops and overloops-based constructions are about three and sixty times larger than the optimal, respectively. More important than the size of the final BUTA is the computation time; it just happens in practice to be roughly proportional to the size of the result, as far as our two transformations are concerned. Using a deterministic variant of either transformation and minimising the result would yield B m , but at the cost of a considerable increase of the worst-case complexity and average computation time. Another important point is that the huge size discrepancy between B l and B o cannot be reduced "in post-processing" using the standard BUTA reduction (elimination of unreachable states [START_REF] Comon | Tree automata techniques and applications[END_REF]): it would have no effect whatsoever, because Algorithms 2 and 3 yield reduced BUTA by construction. A more powerful operation such as the cleanup method described in [START_REF] Heam | Random Generation of Positive TAGEDs wrt. the Emptiness Problem[END_REF], which removes states which are not co-accessible as well as unreachable states, can bring down the sizes of B l and B o , but does in no way bridge the gap between them. Case in point, the automata after cleanup B l and B o are of sizes8 B l = 1617 and B o = 78, which yield the following ratios:

B l B o
≈ 20.9 and B l B o ≈ 20.7 and

B l B l ≈ B o B o ≈ 1.2 .
These figures suggest that the (substantial) size gains originating from the switch from loops to overloops-based algorithms are completely unrelated to (and do not interfere with) the (modest) size gains from post-processing. The observations drawn from this single example have been substantiated by more thorough experiments conducted on the same uniformly generated random TWA as in Fig. 1, the results of which are summarised in Fig. 2 [p15] . The legend uses the same notations as above. Two hundred TWA have been used to construct each data point.9

Demonstration Software

Readers interested in experimenting with this paper's algorithms will find online10 a proof of concept (binaries and OCaml source code), as well as comprehensive instructions for use.

Conclusion

In this paper we have introduced tree overloops, and applied both loops and overloops to common operations on TWA: deciding membership, transforming a TWA into a BUTA, and inexpensively testing emptiness. We have shown that the use of overloops simplifies the transformation into BUTA, and substantially lowers the upper bound in the deterministic case. We intend to pursue this further by using overloops to characterise useful classes of TWA and perform significant simplifications on the automata, hopefully leading to applications to XPath. Furthermore, while our theoretical results and experiments show that the overloops-based transformation yields much smaller BUTA than the loops-based one, both asymptotically and in average -and yields them proportionally faster, -it is clear that further advances remain possible in that respect. On-the-fly variants enabling to test emptiness (for instance) while forgoing the computation of the whole BUTA would also be of interest.

Algorithm 2 :

 2 Tranformation into BUTA, with loops Data: An escaped TWA A = Σ, Q, I, F, ∆ (see Def. 13) Result: A BUTA B such that Lng (B) = Lng (A) Meta-Algorithm 1 where

Figure 1 :

 1 Figure 1: Uniform random TWA: Emptiness results

Corollary 29 (|Q| 2 =

 292 Complexity of the Approximation). The execution of Algorithm 4 is done in time polynomial in the size of A -more precisely: O(|Σ| • |T| 2 • |Q| 5 ). Proof. For all types τ , all operations in Algo. 4 which alter L τ add elements to it. The first loop executes a fixed number of times (|Σ 0 | × |T|). The main loop contains only an inner loop which executes a fixed number of times as well (|Σ 2 | × |T|), and the main loop itself executes until no element is added to L 0 , L 1 or L during the iteration. Since an iteration can only add elements, and each iteration adds at least one, there can be at most τ ∈T |L τ | = τ ∈T |T| × |Q| 2 iterations of the main loop. Each iteration of both the first loop and the main inner loop computes a set of overloops, based on two sets of previouslycomputed (potential) overloops. This operation executes in a time which is in time O(|Q| 2 • |∆|) for the initial computation and O(|Q| 3 ) for the computation of the transitive closure. It is executed in total |Σ 0

Figure 2 :

 2 Figure 2: Uniform random TWA: Size results

  2, and B o by Algo. 3, then we have B l = 1986 and B o = 95, where the size of a BUTA B = Σ, Q, F, ∆ is defined -in the usual way [14] -as: B = |Q| + f (p1,...,pn)→q∈∆ n + 2 .

  Compute the reflexive and transitive closure of L α in place. Complexity. The initial topological sorting is done in O( t ), and the construction of the T σ,τ,µ matrices is done in O(|Σ| • |Q|

2 + |∆|). Within each call of f we have the following complexities: ( ) O(|Q| 2.3727 ) using the latest Coppersmith-Winograd-Stothers-Williams algorithm -or simply O(|Q| 3 ) with the conventional product ( ) Θ(|Q| 3 ) using the Roy-Floyd-Warshall algorithm. The complexity of any call to f is therefore O(|Q| 3 ); there are t calls to f . Hence the announced total complexity of O |∆| + t • |Q|

  |Q| 2 binary relations on Q, of which |Q + 1| Let A be a deterministic TWA and B its equivalent BUTA built by an application of Algorithm 3. Then B has at most |T| • 2 |Q| log 2 (|Q|+1) states.

|Q|

are partial functions, of which |Q| |Q| are total functions. Remark 22. If a relation R is functional, then so is R k , for any k ∈ N. By construction, a BUTA built by Algo. 2 (loop-based) has at most |Σ| • |T| • 2 |Q| 2 states, while one built by Algo. 3 (overloop-based) has at most |T| • 2 |Q| 2 . We will see in this section that, in the deterministic case, this upper bound is in fact much lower for the overloop-based algorithm than for the traditional loop-based one. More specifically, we will show that the following holds: Theorem 23 (Deterministic Upper-Bound).

  Thus, by Lemma 26, L is functional. Therefore, by Remark 21, there are at most |T| • |Q + 1| |Q| states (or, equivalently, |T| • 2 |Q| log 2 (|Q|+1) ).

		55
		50 45								Approximation -2000 samples Approximation -200 samples Exact -200 samples
		40
		35
	∅%	25 30
		20
		15
		10
		5
		0	2	4	6	8	10	12	14	16	18	20	22	24
									|Q|

Of course, if one does that, there are a number of optimisations which can be performed. For instance, since the star-component is only ever useful at the root, it suffices to replace it with a boolean indicating whether it contains a loop in I × F , i.e. whether it is a final state. Then we get states in Σ × (2 Q 2 ) |S| × {0, 1}.

In this paper we do not need the usual, stronger definition, where I is a singleton.

Note that |Q| is therefore proportional to the size of the generated TWA.

With the exception of the last data point (namely, |Q| = 10), for which only the first 124 TWA were tested; this is due to both time constraints and memory limitations of the computer used for the tests.

It happens to be unique (up to homomorphism) in this particular case.

In this trivial example, the sizes of the TWA X , of the "optimal" equivalent BUTA Bm and Bs, and of the post-cleanup overloops-based BUTA B o happen to be quite close. This observation should of course not be generalised.

The same remark as for Fig.1applies: Fig.2[p15] uses only 156 TWA for its last data point (|Q| = 7).

On http://lifc.univ-fcomte.fr/~vhugot/TWA.

Acknowledgements. The authors would like to thank the members of the INRIA ARC ACCESS for interesting discussions on this topic. Our thanks go as well to the anonymous reviewers -for both the conference version and the journal version -who provided the tighter complexity bound for Cor. 7, and whose careful proofreading improved the readability of this paper.

This author is supported by the project ANR 2010 BLAN 0202 02 FREC. 2 This author is supported by the French DGA (Direction Générale de l'Armement).


Jacques M Bahi
email: jacques.bahi@univ-fcomte.fr

Christophe Guyeux

Abdallah Makhoul
email: abdallah.makhoul@univ-fcomte.fr

Congduc Pham
email: congduc.pham@univ-pau.fr

Low Cost Monitoring and Intruders Detection using Wireless Video Sensor Networks

There is a growing interest in the use of video sensor networks in surveillance applications in order to detect intruders with low cost. The essential concern of such networks is whether or not a specified target can pass or intrude the monitored region without being detected. This concern forms a serious challenge to wireless video sensor networks of weak computation and battery power.

In this paper, our aim is to prolong the whole network lifetime while fulfilling the surveillance application needs. We present a novel scheduling algorithm where only a subset of video nodes contribute significantly to detect intruders and prevent malicious attacker to predict the behavior of the network prior to intrusion. Our approach is chaos-based, where every node based on its last detection, a hash value and some pseudo-random numbers easily computes a decision function to go to sleep or active mode. We validate the efficiency of our approach through theoretical analysis and demonstrate the benefits of our scheduling algorithm by simulations. Results show that in addition of being able to increase the whole network lifetime and to present comparable results against random attacks (low stealth time), our scheme is also able to withstand malicious attacks due to its fully unpredictable behavior.

Introduction

Instead of using traditional vision systems built essentially from fixed video cameras, it is possible to deploy autonomous and small wireless video sensor nodes (WVSN) [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF] to achieve video surveillance of a given area of interest. Doing so lead to a much higher level of flexibility, therefore extending the range of surveillance applications that could be considered. More interestingly, this scenario can support dynamic deployment scenario even in so-called object and obstacle-rich environments or hard-to-access areas. Such wireless video sensor nodes can in addition be thrown in mass to constitute a 1 large scale surveillance infrastructure. In these scenarios, hundreds or thousands of video nodes of low capacity (resolution, processing, and storage) of a same or similar type can be deployed in an area of interest.

Surveillance applications have very specific needs due to their inherently critical nature associated to security [START_REF] He | Energy-efficient surveillance system using wireless sensor networks[END_REF][START_REF] Oh | Instrumenting wireless sensor networks for real-time surveillance[END_REF][START_REF] Zhu | Probabilistic approach to provisioning guaranteed qos for distributed event detection[END_REF]. The basic objective of video surveillance systems is to allow detection and/or identification of intruders. Therefore, in that context, the main goal of a video sensor network is to ensure the coverage of the whole area of interest at any time t. Another issue of prime importance is related to energy considerations since the scarcity of energy does have a direct impact on coverage, as it is not possible to have all the video nodes in activity at the same time. Therefore, a common approach is to define a subset of the deployed nodes to be active while the other nodes can sleep. There are already some techniques that schedule video nodes to work alternatively while maintaining the complete coverage [START_REF] Wang | Randomized approach for target coverage scheduling in directional sensor network[END_REF][START_REF] Pham | Risk-based adaptive scheduling in randomly deployed video sensor networks for critical surveillance applications[END_REF][START_REF] Pham | Performance study of multiple cover-set strategies for mission-critical video surveillance with wireless video sensors[END_REF]. The main idea in these techniques is to turn off a redundant node. Here redundancy means that the covered area by a node is completely covered by its neighbors too. However, these techniques usually depend on location or directional information, which is costly in energy and complexity. Usually it is very difficult to determine the redundant nodes without the location information. Fortunately, not all applications need a complete coverage at anytime, and in most surveillance applications for intrusion detection, most sensor nodes can move to a so-called "idle mode" in the absence of intrusions. When an intruder is detected by a node all the network will be alerted. In that context, it is critical to provide an effective scheme for turning off video nodes without degrading the surveillance quality.

In this paper, we present a solution to the joint scheduling problem in surveillance applications using video sensor nodes. We provide a chaotic sleeping scheme and conduct a theoretical and simulation analysis of both performances and security. Until now, only random approaches have been extensively studied in the literature to turn off video nodes without degrading the surveillance quality. Even if such methods present good scores in detecting random intrusions while preserving the lifetime of the network, they do not encompass the situation of a malicious attacker. That is to say, the intruder is not supposed to know something about the surveillance scheme, he cannot observe the WVSN for a while, or he is not authorized to deduce anything from his possible knowledge. In this paper, we intend to tackle with situations where the attacker is not supposed passive: he is smart and does not necessarily choose a random way to achieve his intrusion. In addition of preserving the network lifetime and being able to face random attacks, we show that our scheme is also capable to withstand attacks of a malicious adversary due to its unpredictable behavior.

The rest of the paper is organized as follows. In Section 2, related works related to surveillance applications with WVSN are presented. Smart threats and malicious attackers are introduced in Section 3. Basic recalls and terminologies on the fields of the mathematical theory of chaos and chaotic iterations are given in Section 4, and the link unifying them is explained too. The surveillance scheme based on the chaos theory is detailed in Section 5. We show in Section 6 that our proposed scheme can be used against malicious attacks. Simulation results in Section 7 compare our scheme to the classical random schedule in terms of intruder's stealth time, network lifetime and energy repartition. The paper ends by a conclusion section, where our contribution is summed up and planned future work is detailed.

Related Works

In video sensor networks, minimizing energy consumption and prolonging the system lifetime are major design objectives. Due to the significant energy-saving when a node is sleeping, a frequently used mechanism is to schedule the sensor nodes such that redundant nodes go to sleep as often and for as long as possible. By selecting only a subset of nodes to be active and keeping the remaining nodes in a sleep state, the energy consumption of the network is reduced, thereby extending the operational lifetime of the sensor network.

In this context, the coverage problem for wireless video sensor networks can be categorized as:

• Known-Targets Coverage Problem, which seeks to determine a subset of connected video nodes that covers a given set of target-locations scattered in a 2D plane.

• Region-Coverage Problem, which aims to find a subset of connected video nodes that ensures the coverage of the entire region of deployment in a 2D plane.

Most of the previous works have considered the known-targets coverage problem [START_REF] Cai | Target-oriented scheduling in directional sensor networks[END_REF][START_REF] Ai | Coverage by directional sensors in randomly deployed wireless sensor networks[END_REF][START_REF] Liu | Maximal lifetime scheduling for sensor surveillance systems with k sensors to one target[END_REF][START_REF] Cheng | Achieving minimum coverage breach under bandwidth constraints in wireless sensor networks[END_REF]. The objective is to ensure at all time the coverage of some targets with known locations that are deployed in a two-dimensional plane. For example, the authors in [START_REF] Cheng | Achieving minimum coverage breach under bandwidth constraints in wireless sensor networks[END_REF] organize sensor nodes into mutually exclusive subsets that are activated successively, where the size of each subset is restricted and not all of the targets need to be covered by the sensors in one subset. In [START_REF] Ai | Coverage by directional sensors in randomly deployed wireless sensor networks[END_REF], a directional sensor model is proposed, where a sensor is allowed to work in several directions. The idea behind this is to find a minimal set of directions that can cover the maximum number of targets. It is different from the approach described in [START_REF] Cai | Target-oriented scheduling in directional sensor networks[END_REF] that aims to find a group of non-disjoint cover sets, each set covering all the targets to maximize the network lifetime.

Regarding the Region-Coverage Problem in which this study takes place, existing works focus on finding an efficient deployment pattern so that the average overlapping area of each sensor is bounded. The authors in [START_REF] Ma | Some problems of directional sensor networks[END_REF] analyze new deployment strategies for satisfying some given coverage probability requirements with directional sensing models. A model of directed communications is introduced to ensure and repair the network connectivity. Based on a rotatable directional sensing model, the authors in [START_REF] Tao | Coverage-enhancing algorithm for directional sensor networks[END_REF] present a method to deterministically estimate the amount of directional nodes for a given coverage rate. A sensing connected sub-graph accompanied with a convex hull method is introduced to model a directional sensor network into several parts in a distributed manner. With adjustable sensing directions, the coverage algorithm tries to minimize the overlapping sensing area of directional sensors only with local topology information. Lastly, in [START_REF] Pham | Risk-based adaptive scheduling in randomly deployed video sensor networks for critical surveillance applications[END_REF], the authors present a distributed algorithm that ensures both coverage of the deployment area and network connectivity, by providing multiple cover sets to manage Field of View redundancies and reduce objects disambiguation.

All the above algorithms depend on the geographical location information (position and direction) of video nodes. These algorithms aim to provide a complete-coverage network so that any point in the target area would be covered by at least one video node. However, this strategy is not as energy-efficient as what we expect because of the following two reasons. Firstly, the energy cost and system complexity involved in obtaining geometric information may compromise the effect of those algorithms. Secondly, video nodes located at the edge of the area of interest must be always in an active state as long as the region is required to be completely covered. These video nodes will die after some time and their coverage area will be left without surveillance. Thus, the network coverage area will shrink gradually from outside to inside. This condition is unacceptable in video surveillance applications and intrusion detection, because the major goal here is to detect intruders as they cross a border or as they penetrate a protected area.

One direction to solve these problems is to schedule a node to sleep following a probabilistic approach. Each node remains awake with a given probability so that the coverage of the area can be guaranteed. However the probability can be modeled by an observer, who can take benefits from his observations to predict the dynamic of the network. This is obviously a security flaw. These considerations lead us to the introduction of smart threats given in the next section.

3 Smart Threats

Introduction

Let us suppose that an adversary tries to reach a location X into the area without being detected. We consider that this situation leads to two categories of attacks against WVSN surveillance.

On the one hand, the attacker only knows that the area is under surveillance. He tries to take its chance, for example by following the shortest way or by trying a random path. In this first category of attack that we call "blind elementary attacks", the intruder does not know how the surveillance is achieved as he does not observe the WVSN.

On the other hand, in the second category of attacks, called "malicious attacks" in this paper, the intruder is supposed to be intelligent. He can try to take benefits from his observations to understand the behavior of the WVSN. After having recorded the dynamic of the WVSN for a given time, the malicious intruder can try to determine when video nodes are turned on. This prediction can help the intruder to find a way to reach X without being detected.

In our opinion, the most reasonable way to evaluate the consequences of a malicious attack is to suppose that the intruder has access to the surveillance scheme. With this supposition, our security model encompasses the case where an attacker can have a physical access to a given node, thus determining the embedded mechanism used for video surveillance. In this Kerckhoffs-based principle, the attacker knows all but the initial parameters of the nodes. Moreover, he can observe the WVSN for a while. To achieve his intrusion, he can use all of the acquired knowledge -the sole difficulty is his lack of a secret parameter (the secret key) used to initialize the surveillance process.

The context of blind elementary attacks is well-known and understood: it has been studied a lot in the last decade, and various solutions have yet been proposed (Section 2). On the contrary, to the best of our knowledge, the case of an intelligent intruder (smart threat) has not yet really been treated. In this paper, we intend to propose a scheme able to withstand attacks encompassing these malicious intrusions, and thus to offer a first solution to the problem raised by the smart threats existence hypothesis.

Technically speaking, the proposed approach offers several benefits. Firstly, the node scheduling algorithm does not need location information. Therefore, the energy consumption is reduced because there is no need to locate the node itself and its neighbors. Secondly, we will show that it performs as well as a random scheduling, in terms of lifetime and intrusion detection against blind elementary attacks (see Section 7). Lastly, due to its chaotic properties, its coverage is unpredictable, and thus a malicious adversary has no solution to attack the network (Section 6).

Classification of Malicious Attacks

When a malicious adversary attacks a WVSN, he can concentrate his efforts either on the global network or on some specific nodes. Depending on the considered situation, he can perform either an active attack, modifying the network architecture or a node, or a passive attack based only on observations. He can have access to several WVSN using the same algorithm. Furthermore, he can build its own network to make some experiments. His objective is to find the secret key used in the targeted network: with this knowledge, the attacker will be able to predict the behavior of the video sensor nodes.

Active attacks have been already investigated several times in the literature. These studies encompass the cases where nodes can be added, moved, modified, or removed, where communications between nodes can be observed or modified, and where the global architecture of the network is attacked. However, some WVSN are such that any modification of the network is signaled, leading to the impossibility of such active attacks. On the contrary, passive observations and deductions of a malicious attacker are always possible. To the best of our knowledge, these threats have not yet been investigated.

The passive malicious attacks can be classified as follows.

• In the Target Only Attack (TOA), the adversary can only observe targeted networks.

• In the Constant Key Attack (CKA), the adversary has access to several WVSN using the same secret key. The areas under surveillance and the network architecture change from one WVSN to another, but the attacker knows that all these networks use the same algorithm with the same secret key.

• In the Known Original Attack (KOA), the attacker had previously accessed to the WVSN and its area. He had the opportunity to test various keys in a previous access. He hopes that this knowledge will help him to determine a way to realize his intrusion when the WVSN is really launched.

• In the Chosen Key Attack (CKA), the adversary has access to an exact copy of the network and area under surveillance than the one he want to attack. He has realized for instance a miniature model or a computer simulator having exactly the same behavior than the targeted network and its area. He can thus try several secret key, and if he achieves to reproduce exactly the same behavior for the network, then he can reasonably suppose that the true secret key has been discovered.

• Finally, in the Estimated Original Attack (EOA), the attacker has only an estimation, an approximation of the network and its area.

In each of these categories, the sole objective of the attacker is to obtain the value of the secret key. With this knowledge, he will able to determine the WVSN behavior, finding by doing so a way to achieve his intrusion.

Security Levels in CKA

We now take place in the Chosen Key Attack problem. Let k 0 be the secret key used to initiate the video-surveillance. Denote by Y k the probabilistic model that the attacker can build with his observations, and by K the set of all possible keys. Definition 1 (Insecurity) The WVSN is insecure against the Target Only Attack if and only if

∃k 1 ∈ K, p(Y k1 ) = p(Y k0 ) and ∀k 2 ∈ K, p(Y k2 ) = p(Y k0 )
On the contrary, Definition 2 (Security) The WVSN is secure against the Target Only Attack if and only

if ∀k ∈ K, p(Y k ) = p(Y k0 )
In that situation, it is easy to prove that the mutual information I(k 0 , Y k0 ) is equal to 0, which is often refered as perfect secrecy.

Basic Recalls

In the sequel S n denotes the n-th term of a sequence S and V i is the i-th component of a vector V . f k = f • ... • f denotes the k-th composition of a function f . Finally, the following notation is used: 1; N = {1, 2, . . . , N }.

Devaney's Chaotic Dynamical Systems

Consider a topological space (X , τ ) and a continuous function f : X → X . Definition 3 f is said to be topologically transitive if, for any pair of open sets U, V ⊂ X , there exists k > 0 such that f k (U ) ∩ V = ∅.

Definition 4 An element (a point) x is a periodic element (point) for f of period n ∈ N * , if f n (x) = x.
Definition 5 f is said to be regular on (X , τ ) if the set of periodic points for f is dense in X : for any point x in X , any neighborhood of x contains at least one periodic point (without necessarily the same period). Definition 6 f is said to be chaotic on (X , τ ) if f is regular and topologically transitive.

The chaos property is strongly linked to the notion of "sensitivity", defined on a metric space (X , d) by: Definition 7 f has sensitive dependence on initial conditions if there exists δ > 0 such that, for any x ∈ X and any neighborhood V of x, there exists y ∈ V and n > 0 such that d (f n (x), f n (y)) > δ. δ is called the constant of sensitivity of f . Indeed, Banks et al. have proven in [START_REF] Banks | On devaney's definition of chaos[END_REF] that when f is chaotic and (X , d) is a metric space, then f has the property of sensitive dependence on initial conditions (this property was formerly an element of the definition of chaos). To sum up, quoting Devaney in [START_REF] Devaney | An Introduction to Chaotic Dynamical Systems[END_REF], a chaotic dynamical system "is unpredictable because of the sensitive dependence on initial conditions. It cannot be broken down or simplified into two subsystems which do not interact because of topological transitivity. And in the midst of this random behavior, we nevertheless have an element of regularity". Fundamentally different behaviors are consequently possible and occur in an unpredictable way.

Chaotic Iterations

Let us consider a system of a finite number N ∈ N * of elements (or cells), so that each cell has a Boolean state. A sequence of length N of Boolean states of the cells corresponds to a particular state of the system. A sequence which elements are subsets of 1; N is called a strategy. The set of all strategies is denoted by S.

Definition 8 The set B denoting {0, 1}, let f : B N -→ B N be a function and S ∈ S be a strategy. The so-called chaotic iterations (CIs) are defined by [START_REF] Robert | Discrete Iterations: A Metric Study[END_REF] x 0 ∈ B N and

∀n ∈ N * , ∀i ∈ 1; N , x n i = x n-1 i if i / ∈ S n f (x n-1 ) S n if i ∈ S n . (1)
In other words, at the n-th iteration, only the S n -th cell is "iterated". Note that in a more general formulation, S n can be a subset of components and f (x n-1 ) S n can be replaced by f (x k ) S n , where k < n, describing for example, delays transmission. For the general definition of such chaotic iterations, see, e.g., [START_REF] Robert | Discrete Iterations: A Metric Study[END_REF].

The term "chaotic", in the name of these iterations, has a priori no link with the mathematical theory of chaos recalled previously. However, we have proven in [START_REF] Bahi | Hash functions using chaotic iterations[END_REF] that in a relevant metric space (X , d), the vectorial negation f 0 (x 1 , . . . , x N ) = (x 1 , . . . , x N ) satisfies the three conditions for Devaney's chaos. This result is recalled in the next section.

Chaotic Iterations and Devaney's Chaos

Denote by ∆ the discrete Boolean metric, ∆(x, y) = 0 ⇔ x = y. Given a function f : B N -→ B N , define the function

F f : 1; N × B N -→ B N such that F f (k, E) = E j .∆(k, j) + f (E) k .∆(k, j) j∈ 1;N , (2)
where + and . are the Boolean addition and product operations. The shift function is defined by σ : (S n ) n∈N ∈ S → (S n+1 ) n∈N ∈ S and the initial function i is the map which associates to a sequence, its first term: i : (S n ) n∈N ∈ S → S 0 ∈ 1; N . Consider the phase space: X = 1; N N × B N and the map

G f (S, E) = (σ(S), F f (i(S), E)) . (3)
The chaotic iterations can be described by the following iterations

X 0 ∈ X X k+1 = G f (X k ). (4)
Let us define a new distance between two points (S, E), ( Š, Ě) ∈ X by

d((S, E); ( Š, Ě)) = d e (E, Ě) + d s (S, Š), (5)
where

• d e (E, Ě) = N k=1 ∆(E k , Ěk ) ∈ 0; N , • d s (S, Š) = 9 N ∞ k=1 |S k -Šk | 10 k ∈ [0; 1].
This new distance has been introduced in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF][START_REF] Bahi | Hash functions using chaotic iterations[END_REF] to satisfy the following requirements. When the number of different cells between two systems is increasing, then their distance should increase too. In addition, if two systems present the same cells and their respective strategies start with the same terms, then the distance between these two points must be small because the evolution of the two systems will be the same for a while. The distance presented above follows these recommendations. Indeed, if the floor value d(X, Y ) is equal to n, then the systems E, Ě differ in n cells. In addition, d(X, Y )-d(X, Y ) is a measure of the differences between strategies S and Š. More precisely, this floating part is less than 10 -k if and only if the first k terms of the two strategies are equal. Moreover, if the k-th digit is nonzero, then the k-th terms of the two strategies are different.

It is proven in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF][START_REF] Bahi | Hash functions using chaotic iterations[END_REF] by using the sequential continuity that,

Proposition 1 ∀N ∈ N * , ∀f : B N → B N , G f is a continuous function on (X , d).
It is then checked in [START_REF] Bahi | Topological chaos and chaotic iterations, application to hash functions[END_REF][START_REF] Bahi | Hash functions using chaotic iterations[END_REF] that in the metric space (X , d), the vectorial negation f 0 (x 1 , . . . , x N ) = (x 1 , . . . , x N ) satisfies the three conditions for Devaney's chaos: regularity, transitivity, and sensitivity. This has led to the following result.

Proposition 2 CIs are chaotic on (X , d) as it is defined by Devaney. [START_REF] Bahi | Hash functions using chaotic iterations[END_REF] an hash function and a pseudo-random number generator (PRNG) able to pass the stringent TestU01 battery of tests in [START_REF] Bahi | A pseudo random numbers generator based on chaotic iterations. application to watermarking[END_REF].

These chaotic iterations have been used to define in

5 Chaos-Based Scheduling 5.1 The General Algorithm

Network Capabilities

The WVSN is supposed to be constituted by 2 N nodes V i , i ∈ 0, 2 N -1 . Each V i is able to wake up on a specific signal, to survey a given area (and to detect intrusions), to send a wake up signal to another node V j , and to go to sleep when it is required. Furthermore, it is supposed that V i embeds:

• The mechanisms required by the intrusion detection: a sensing function c i (t), such as a camera, which returns some digital data at each listening time, and a decision function d i (c) which returns if an intrusion is detected in this sensing values (c i (t)) or not.

• An internal clock having the time T i = r i T 0 as a reference.

• A vector of N binary digits, called the state of the system V i , and the capability to swap each bit of this vector (0 ↔ 1).

• An integer e i , called listening time, initialized to 0.

In other words, each node V i can achieve CIs. Thus, each node can compute, easily and by using a few resources, a hash value and some pseudo-random numbers as it is recalled in Section 4.2. We will denote by g i the seed of the PRNG used in node V i , which is equal to a secret parameter p i at time t = 0.

Deploying the Network

The deployment of video sensor nodes in the physical environment is the first operation (step) in the network lifecycle. It may take several forms. Sensor nodes may be randomly deployed dropping them from a plane, and placed one by one by a human or a robot. Deployment may be a one time activity or a continuous process. These methods have been extensively studied in the literature. In our method, the sole requirement to satisfy is to guarantee the uniform repartition into the region of interest.

Initialization of the WVSN

At time t = 0, a subset I ⊂ 0, 2 N -1 of nodes are woken up and ∀i ∈ I, e t0 i = T i .

Surveillance

The principle of surveillance applications is defined as follows. At each time t j = j × T 0 , j = 1, 2, . . .:

1. If a sleeping node V i has received n tj -1 i

1 wake up orders during the time interval [t j -1, t j ], then it goes into active mode and sets its listening time e

tj i to n tj -1 i T i .
2. If an active node V i has received n tj -1 i 1 orders to wake up during the time interval [t j-1 , t j ], then it increments its listening time:

e tj i = e tj -1 i + n tj -1 i T i .
3. For each node V i having a listening time e tj i = 0:

• V i ensures the surveillance of its area during T 0 ,

• If, during this time interval, an intrusion is detected, then the WVSN is under alert.

• If t j is the first listening time of V i after having activated, then:

-The hash value h tj i of the sensed value c i (t j ) is computed (cf. Section 4.2).

-The seed g i of the PRNG of V i is set to h tj i + t j , where + is the concatenation of the digits of h tj i and t j (thus even if

h tj i = h t k i , k < j, we have g tj i = g t k i ).
-The N bits of the state of the system V i are set to E tj i , where E tj i is the binary decomposition of i shown as a binary vector of length N. 6. For each active node having its listening time e tj i = 0:

• V i sends the wake up order to node V k , where k ∈ 0, 2 N -1 is the integer whose binary decomposition is the last state of the system V i (E tj+1 i

).

• V i goes to sleep.

6 Theoretical Study

Scheduling as Chaotic Iterations

The scheduling scheme presented above can be described as CIs. The global state E t of the whole system is constituted by the reunion of each internal state E t i of each node i. This is an element of B N×2 N

. The strategy at time t is the subset of 0; N × 2 N constituted by all of the strategies that are computed into the awaken nodes at time t. More precisely, if the node V k has computed the strategy S t k at time t, then the global strategy S t will contain the value S t k + k × N. Lastly, the iteration function is the vectorial negation defined :

B N×2 N → B N×2 N
. A subsequence E m t is extracted from E t , which determines the changes that occur in the network: nodes whose binary id is into E m t are nodes that achieve the surveillance at the considered time. Let us remark that S k and m k depend both on the outside world, due to the fact that S t i are regularly seeded with the digest of some sensed values.

Complexity

Even if the hash function and the PRNG taken from [START_REF] Bahi | Hash functions using chaotic iterations[END_REF] and [START_REF] Bahi | A pseudo random numbers generator based on chaotic iterations. application to watermarking[END_REF] respectively can be replaced by any cryptographically secure hash function and PRNG, we do not recommend their substitution. Indeed, all of the operations used by our scheme can be achieved by CIs. Each iteration of CIs is only constituted by the negation of a few binary digits. Obviously, such an operation is fast and does not consume a lot of energy. By doing so, we thus obtain an efficient video surveillance scheduling scheme compliant with WVSN requirements. Section 7 will detail more quantitatively this fact.

Coverage

The coverage of the whole area is guaranteed due to the following reasons.

Firstly, the scheduling process corresponds to CIs. These iterations are chaotic according to Devaney, thus they are transitive. This transitivity property is the formulation of an uniform distribution in terms of topology. It claims that the system will never stop to visit any sub-region of the whole area, regardless of how tiny the region is.

Secondly, as the choice of the nodes to wake up at each time are done by using CIs, this selection corresponds to the returned value of our PRNG proposed in [START_REF] Bahi | A pseudo random numbers generator based on chaotic iterations. application to watermarking[END_REF]. This "CI(X,Y)-generator" takes two PRNGs X,Y as input sequences, realizes CIs with X as strategy, the vectorial negation as update function, and selects the states to publish as outputs by using the second PRNG Y. By such a combination, we improve the statistical properties of the input PRNG used as strategy, and we add chaotic properties. The scheduling process corresponds to the CI(X,Y)-generator, with X=m and Y=S. As Y is statistically perfect (Y is CI(ISAAC,ISAAC), which can pass the whole NIST, DieHARD, and TestU01 batteries of tests), the uniform repartition of the states is then guaranteed.

Lastly, experiments of Section 7 will show that this intended uniform coverage is well obtained in practice.

Security Study

Qualitative Approach

Let us suppose that Oscar, an intruder, knows that the scheduling process is based on CIs, i.e. he knows the whole algorithm, except the seeds that have been used to initiate the PRNGs of each node. By doing so, we respect the Kerckhoffs' principle: the adversary has all except the secret key. Oscar's desire is to reach a particular location X of the area without being detected. To achieve his goal, he can choose two strategies. On the one hand, he can try a blind elementary attack, either by following a random way from its position to X, of by choosing the shortest path. The next subsection and the experiments will show that such an attack cannot work. On the other hand, Oscar can try to take benefits both from his knowledge and his observations. However, if he can determine the nodes that are awaken at time t, he cannot predict the awaken nodes at time t + 1, t + 2, ... To do so, he should be able to obtain S t+1 , S t+2 , ..., which are computed from the digests of some values that will be sensed in the future. As our hash function satisfy the avalanche effect, due to its chaotic properties, any error on the sensed value lead to a completely different digest.

As Oscar cannot determine the sensed values of each node, at each time and with an infinite precision, he does not have the knowledge of the current state of the global system. He has only access to an approximation of this state. As the global scheduling process is chaotic, this error on the initial condition is magnified at each iteration, leading to the impossibility for Oscar to predict the scheduling process. This qualitative approach for security will be formalized in the second section below.

Chaotic Properties

We now investigate the topological properties presented by the proposed video-surveillance scheme. First of all, let us recall two fundamental definitions from the mathematical theory of chaos. Definition 9 A function f is said to be expansive if ∃ε > 0, ∀x = y, ∃n ∈ N such that d (f n (x), f n (y)) ≥ ε.

Definition 10 A discrete dynamical system is said to be topologically mixing if and only if, for any pair of disjoint open sets U ,V = ∅, n 0 ∈ N can be found so that ∀n ≥ n 0 , f n (U ) ∩ V = ∅.

As proven in [START_REF] Guyeux | Chaotic iterations versus spread-spectrum: chaos and stego security[END_REF], chaotic iterations are expansive and topologically mixing when f is the vectorial negation f 0 . Consequently, these properties are inherited by the WVSN presented previously, which induce a greater unpredictability. Any difference on the initial parameter of the WVSN is in particular magnified up to be equal to the expansivity constant.

Now, what are the consequences for a wireless sensor network to be chaotic according to Devaney's definition? Firstly, the topological transitivity property implies indecomposability.

Definition 11 A dynamical system (X , f ) is indecomposable if it is not the union of two closed sets A, B ⊂ X such that f (A) ⊂ A, f (B) ⊂ B.
Hence, reducing the observed area in order to simplify its complexity, is impossible if Γ(f ) is strongly connected. Moreover, under this hypothesis the surveillance scheme is strongly transitive:

Definition 12 A dynamical system (X , f ) is strongly transitive if ∀x, y ∈ X , ∀r > 0, ∃z ∈ X , d(z, x) ≤ r ⇒ ∃n ∈ N * , f n (z) = y.
According to this definition, for all pair of points x, y in the phase space, a point z can be found in the neighborhood of x such that one of its iterate f n (z) is y. Indeed, this result has been stated during the proof of the transitivity presented in [START_REF] Bahi | Hash functions using chaotic iterations[END_REF]. Among other things, the strong transitivity leads to the fact that without the knowledge of the initial awaken nodes, all scheduling are possible. Additionally, no nodes of the output space can be discarded when studying the video-surveillance scheme: this space is intrinsically complicated and it cannot be decomposed or simplified.

Finally, these WVSN possess the instability property:

Definition 13 A dynamical system (X , f ) is unstable if for all x ∈ X , the orbit γ x : n ∈ N -→ f n (x) is unstable, that means: ∃ε > 0, ∀δ > 0, ∃y ∈ X , ∃n ∈ N, such that d(x, y) < δ and d (γ

x (n), γ y (n)) ≥ ε.
This property, which is implied by sensitive point dependence on initial conditions, leads to the fact that in all neighborhoods of any point x there are points that can be apart by ε in the future through iterations of the WVSN. Thus, we can claim that the behavior of these networks is unstable when Γ(f ) is strongly connected.

Cryptanalysis in CKA Framework

As stated in Section 6.1, the proposed videosurveillance scheme can be rewritten as:

X 0 ∈ X X k+1 = G f0 (X k ), (6)
where the phase space is X = 1; N × 2 N N × B N×2 N and f 0 stands for the vectorial negation on B N×2 N . We will now show that, Proposition 3 The videosurveillance scheme proposed in this document is secure when facing a chosen key attack.

Proof 1 Let N = N × 2 N . We suppose that X ∼ U B N , that is, X is uniformly distributed into B N . We will prove by a mathematical induction that ∀n ∈ N, X n ∼ U B N . The base case is immediate, as X 0 = X ∼ U B N . Let us now suppose that the statement X n ∼ U B N holds for some n. Let e ∈ B N and

B k = (0, • • • , 0, 1, 0, • • • , 0) ∈ B N (the digit 1 is in position k). So P X n+1 = e = N k=1 P (X n = e + B k , S n = k) .
These two events are independent, thus: P X n+1 = e = N k=1 P (X n = e + B k )×P (S n = k). According to the inductive hypothesis: P X n+1 = e = 1 2 N N k=1 P (S n = k). The set of events {S n = k} for k ∈ 1; N is a partition of the universe of possible, so

N k=1 P (S n = k) = 1. Finally, P X n+1 = e = 1
2 N , which leads to X n+1 ∼ U B N . This result is true ∀n ∈ N, we thus have proven that,

∀K ∈ [0; 1], Y K = X N0 ∼ U B N when X ∼ U B N
So the videosurveillance defined in this paper is secure in CKA.

Simulation Results

This section presents simulation results on comparing our chaotic approach to the standard C++ rand()-based approach with random intrusions. We use the OMNET++ simulation environment and the next node selection will either use chaotic iterations or the C++ rand() function (rand() % 2 n ) to produce a random number between 0 and 2 n . For these set of simulations, 128 sensor nodes (therefore n = 7) are randomly deployed in a 75m * 75m area. Unless specified, sensors have an 36 o AoV and sensor node captures at the rate of 0.2fps. Each node starts with a battery level of 100 units and taking 1 picture consummes 1 unit of battery. When a node V i is selected to wake up, it will be awake for T i seconds. We set all T i = T = 20s. According to the behavior defined in section 5, before going to sleep after an activity period of e i T , V i will determine the next node to be waked up. It can potentially elect itself in which case V i stays active for at least another T period. The elected node can be already active, in which case it simply increases its e i counter. We set about 50% of the sensor nodes to be active initially (each sensor draws a random value between 0 and 1 and if the value is greater than 0.5, it will be active). This initial threshold is tunable but we did not try to vary this parameter in this paper. The results presented here have been averaged over 10 simulation runs with different initial seeds. Figure 1 shows the percentage of active nodes. Both the chaotic and the standard rand() function have similar behavior: the percentage of active nodes progressively decreases due to battery shortage.

To compare both approaches in term of surveillance quality, we record to stealth time when intrusions are introduced in the area of interest. The stealth time is the time during which an intruder can travel in the field without being seen. The first intrusion starts at time 10s at a random position in the field. The scan line mobility model is then used with a constant velocity of 5m/s to make the intruder moving to the right part of the field. When the intruder is seen for the first time by a sensor, the stealth time is recorded and the mean stealth time computed. Then a new intrusion appears at another random position. This process is repeated until the simulation ends (i.e. no more sensor nodes with energy). Figure 2 shows the mean stealth time over the whole simulation duration. Figure 3 shows the same data but with a sliding window averaging filter of 20 values. As the nodes are uniformly distributed in the area of interest, there is a strong correlation between the percentage of active nodes and the stealth time as it can be expected. The result we want to highlight here is that our chaotic node selection approach has a similar level of performance in presence of random intrusions than standard rand() function while providing a formal proof of non-prediction by malicious intruders. The last result we want to show is the energy consumption distribution. We recorded every 10s the energy level of each sensor node in the field and computed the mean and the standard deviation. Figure 4 shows the evolution of the standard deviation during the network lifetime. We can see that the chaotic node selection provides a slightly better distribution of activity than the standard rand() function.

Conclusions and Perspectives

In this paper, a sleeping scheme for nodes has been proposed as an effective and secure solution to the joint scheduling problem in surveillance applications using WVSNs. It has been evaluated through theoretical and practical aspects of performance and security. As opposed to existing works, this scheduling scheme is not based only on randomness, but on the mathematical theory of chaos too. By doing so, we reinforce coverage and lifetime of the network, while obtaining a more secure scheme. We have considered in this paper the case where the intruder is smart and active. Furthermore, we have supposed that he can know the scheme and observe the behavior of the network. We have shown that, in addition of being able to preserve WVSN lifetime and to present comparable results against random attacks, our scheme is also able to withstand such malicious attacks due to its unpredictable behavior.

In future work, we intend to enlarge the security field in WVSN-based video surveillance, by making a classification of attacks that Oscar can achieve depending on the data he has access to. Our desire is to distinguish between several levels of security into each category of malicious attacks, from the weakest one to the strongest one. Additionally, we will study more precisely the topological properties of the scheduling scheme presented in this paper.

4 .

 4 N bits are computed with the PRNG of V i . These bits define an integerS tj i ∈ 0, 2 N -1 . Then the bit of E tj i in position S tj i is switched, which leads to a new state E tj+1 i. By doing so, CIs are realized. 5. Each active node V i decreases its listening time: e tj i = e tj i -1.

Figure 1 :

 1 Figure 1: Percentage of active nodes.

Figure 2 :

 2 Figure 2: Stealth time.

Figure 4 :

 4 Figure 3: Stealth time.


est destinée au dépôt

Spherical light, arbitrary nonparaxial accelerating beams and femtosecond laser micromachining of curved profiles

Abstract-We review our recent results applying caustics wave theory to the generation of arbitrary curved accelerating beams and their use in the field of femtosecond laser materials processing. We report experimental realization of highly nonparaxial accelerating beams with circular, parabolic and quartic trajectories that extend over more than 95 • of arc as well as spherical optical fields. We also report femtosecond laser curved edge profiling.

Accelerating optical beams are a novel class of electromagnetic wave associated with a localized intensity maximum that propagates along a curved trajectory. In the nonparaxial regime, beams accelerating along circular, parabolic (Weber beams) and elliptic (Mathieu beams) trajectories were predicted from Maxwell's equations and experimentally demonstrated [1][2][3]. Here, we review our recent results on generating arbitrary nonparaxial accelerating beams with another approach, i.e. from optical caustics, and report an important novel application, i.e. curved laser processing. Caustics accurately describe non-paraxial wave propagation using an appropriate wave-diffraction integral. In our case, Debye-Wolf integral is used to determine the phase mask to be applied at the entrance plane of a high numerical aperture aplanatic microscope objective [4]. Analytical integration provides results identical to those obtained from Maxwell's equations and numerical integration also allows other arbitrary profiles. Figure 1(a) shows the experimental intensity distribution of a 632.8 nm beam accelerating on a circular trajectory. The high agreement with the target trajectory (dashed white line) is shown in the magnified views A and B. This approach also allowed us to generate spherical fields, as predicted by [2]. Figure 1(b-c) show experimentally generated field that takes the form of a spherical cap extended down to the equator.

The same approach was applied to the spatial shaping of amplified femtosecond pulses at 800 nm and we used it for a novel technique of femtosecond laser micromachining [5]. Fig. 1(d) presents a 3D view of a silicon sample where the initial square-cut edge was processed into a circle. We anticipate a broad range of applications in different technological fields such as the processing of flat panels and photonic components.

François

  Courvoisier, Amaury Mathis, Luc Froehly, Maxime Jacquot, Remo Giust, Luca Furfaro, John Michael Dudley To cite this version: François Courvoisier, Amaury Mathis, Luc Froehly, Maxime Jacquot, Remo Giust, et al.. Spherical light, arbitrary nonparaxial accelerating beams and femtosecond laser micromachining of curved profiles. Progress In Electromagnetics Research Symposium (PIERS) 2013, Jan 2013, Sweden. pp.1P9. hal-00939425

Figure 1 :

 1 Figure 1: (a) Intensity distribution of a highly nonparaxial beam accelerating along a circle (b)-(c) 3D isointensity surface of experimental spherical field (radius 50 µm). (d) SEM view of a 100 µm thick silicon sample with the edge processed as a circular profile.