Mehdi Stéphane Martin

Pascal Urso

Abstract unordered and ordered trees CRDT *

Keywords: Distributed System, Eventual Consistency, CRDT, Optimistic Replication, Data Consistency, Tree Consistance à terme, CRDT, Réplication optimiste, Arbres, Consistance des données

Trees are fundamental data structure for many areas of computer science and system engineering. In this report, we show how to ensure eventual consistency of optimistically replicated trees. In optimistic replication, the different replicas of a distributed system are allowed to diverge but should eventually reach the same value if no more mutations occur. A new method to ensure eventual consistency is to design Conflict-free Replicated Data Types (CRDT). In this report, we design a collection of tree CRDT using existing set CRDTs. The remaining concurrency problems particular to tree data structure are resolved using one or two layers of correction algorithm. For each of these layer, we propose different and independent policies. Any combination of set CRDT and policies can be constructed, giving to the distributed application programmer the entire control of the behavior of the shared data in face of concurrent mutations. We also propose to order these trees by adding a positioning layer which is also independent to obtain a collection of ordered tree CRDTs.

CRDT definition

Replication is a key feature in any large distributed system. When the replicated data are mutable, the consistency between the replicas must be ensured. This consistency can be strong or eventual. In the strong consistency model (aka atomic or linear consistency), a mutation seems to occurs instantaneously on all replicas. However, the CAP theorem [START_REF] Gilbert | Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services[END_REF] states that is impossible to achieve simultaneously strong consistency (C), availability (A) and to tolerate network partition (P).

In the eventual consistency model, the replicas are allowed to diverge, but eventually reach the same value if no more mutations occur. A mechanism to obtain eventual consistency is to design Conflict-free Replicated Data Types (CRDT) [START_REF] Shapiro | Conflict-free replicated data types[END_REF]. CRDT can be state-based or operation-based. In state-based CRDTs -aka Convergent Replicated Data Type (CvRDT) -the data are computed by merging the state of the local replica with the state of another replica. Eventual consistency is achieved if the merge relation is a monotonic semilattice. In the operation-based CRDTs -aka Commutative Replicated Data Type (CmRDT) -the data is computed by executing remote operations on the local replica. Eventual consistency is achieved if operations are delivered in certain order and if the execution of the non-ordered operations commutes. For instance, using causal order, the execution of concurrent (in Lamport's definition [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF]) operations must commutes.

Set

In this section we show how is defined a set CRDT. We define a data type by a set of update operations and their pre-condition and post-conditions. The precondition is local (i.e. it must only be valid on the replica that generates the update) while the postconditions are global (i.e. it must be valid immediately after the update).

Consider the operations add(a) and rmv(a) for a set data type. In a sequential execution, the "traditional" definition of the pre-and post-conditions are In case of concurrent updates, the post-conditions add(a)||rmv(a) conflict. Indeed for a CvRDT, we cannot a have a merge that ensure the both postconditions. For a CmRDT, the execution of the two updates in two different orders either leads to two different set (Figure 1), either not ensures the postconditions.

Figure 1: Set with concurrent addition and remove [START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF] Thus, a set CRDT has different global post-conditions in order to take into account the concurrent updates while ensuring eventual consistency. Each CRDT has a payload which is an internal data structure not exposed to the client application, and lookup, a function on the payload that returns a set to the client application. For a set CRDT, the pre-conditions must be locally true on the lookup of the set.

Different set CRDTs [START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF] are the G-Set, 2P-Set, LWW-Set, PN-Set, and OR-Set. They are described below.

G-Set

In a Grow Only Set (G-Set), elements can only be added and not removed. The CvRDT merge mechanism is a classical set union.

2P-Set

In a Two Phases Set (2P-Set), an element may be added and removed, but never added again thereafter. The CvRDT 2P-Set (known as U-Set [START_REF] Wuu | Efficient solutions to the replicated log and dictionary problems[END_REF]) payload consists in two add-only set A and R. Adding an element adds it to A and deleting en elements add it to R. The lookup returns the difference A \ R. The set R is often called the tombstones set.

The CmRDT 2P-Set does not require tombstone but causal delivery; thus, a remove is always received after the addition of the element.

LWW-Set

In a Last Writer Wins Set (LWW-Set), each element is associated to a timestamp and a visibility flag. A local operation adds the element if not present and updates the timestamp and the visibility flag (true for add, false for rmv). The CvRDT merge mechanism makes the union of all elements and for each element the pair (timestamp, flag) of the maximum timestamp.

In the CmRDT, the execution of a remote operation updates the element only if timestamp of the operation is higher than the timestamp associated to the element. The both CRDTs requires tombstones and the lookup returns elements which have a true visibility flag. In the CmRDT, each operation contains the difference δ obtained during local execution. The remote operation execution adds δ to the counter. Element with a counter k = 0 can be removed, the others must be kept. The lookup contains elements with k > 0.

OR-Set

In a Observed Remove Set (OR-Set) each element is associated to a set of unique tag. A local add creates a tag for the element and a local rmv removes all the tag of the element. The CvRDT contains the set of element, and for each element a set T of tags added and a set R of tags removed. The merge operation is the union of each set. The lookup contains elements with T ∩ R = {}.

In the CmRDT, each operation contains the tag(s) added or removed. Since causal ordering is ensured and since tag are unique, the removed tag (and element with no tag) can be removed in the payload. The lookup contains the elements of the payload.

Comparison

From the application point of view, all set CRDTs provide a set lookup and the same pre-conditions on operations (except for G-Set, since the application cannot remove an element and for 2P-Set, since application cannot re-add an element). They also provide the same post-conditions of the local replica. The behavior of the presence of the elements in the lookup can be resumed as follow :

LWW-Set an element appears in the lookup if and only if the operation with the higher timestamp is an add.

C-Set an element appears in the lookup if and only if the sum of the add operations counters is greater than the sum of the rmv operations counters.

OR-Set an element appears in the lookup if and only if the tags associated by add operations are not all present in rmv operations.

Graph Trees

According to standard graph theory definition, a tree -more precisely an arborescence -is a connected directed acyclic graph in which a single node root is designated as the root and there is a unique path from root to any other node [START_REF] Diestel | Graph Theory[END_REF]. A tree is thus a ordered pair G = (V, E) with V a set of nodes and E ⊆ V × V a set of directed edges. If (x, y) ∈ V , we say that y is a child of x. Since G have no directed cycle, E * , the transitive closure of E, is a partial strict order on V . There is a path from x to y if and only if (x, y) ∈ E * . We define subtrees in a more general manner than usual by including edges directed to the subtree. In an actual tree there is only one such edge. Definition 1. An ordered pair (N, F ) is a subtree of the tree (V, E) and is rooted by

n ∈ N if N ⊂ V , F ⊆ E and (N, F \ ((V \ N ) × N )
) is a connected directed acyclic graph with a unique path from n to any other node and if

(V \ N, E \ F ) is a tree.
the node m and the operation rmv(N, F ) removes the set of nodes and edges appearing in a subtree. Other operations, e.g. adding a whole subtree, or removing a node while moving all its children under the father of n, can be defined upon these minimal operations 4 . We have the following formal definition of the sequential operations on a tree. For sake of simplicity, we consider that the root of the tree is always present and immutable.

• pre(add(n, m), (V, E)) ≡ n / ∈ V ∧ m ∈ V • post(add(n, m), (V, E)) ≡ n ∈ V ∧ (m, n) ∈ E • pre(rmv(N, F ), (V, E)) ≡ subtree((N, F ), (V, E)) • post(rmv(N, F ), (V, E)) ≡ N ∩ V = {} ∧ F ∩ E = {}.
With such pre-and post-conditions we can ensure that the graph (V, E) stays a tree in case of a sequential modifications. However, in case of a concurrent modifications, these post-conditions conflicts if a node is concurrently added and removed, if a node is concurrently deleted while a children is added, or if a node concurrently added under to different fathers.

Concurrent addition and deletion of the same element

The post-conditions of add(n, m)||rmv(N, F ) with n ∈ N conflicts, i.e. a node cannot be concurrently added and removed. Indeed, as for a set, the postcondition of add and rmv operations cannot be globally ensured while ensuring convergence.

We can uses sets CRDT to bypass the conflict. By using sets CRDT to handle both sets of nodes and edges, we obtain a data type (V, E) that is obviously eventually consistent. Such trees CRDT have the following behavior.

GG-Tree

In a Grow-only Graph Tree (GG-Tree) nodes and edges can only be added and never removed. A GG-Tree uses G-Sets as the sets of nodes V and edges E.

2G-Tree

In a Two-phases Graph Tree (2G-Tree) nodes and thus edges can only be added once. A 2G-Tree uses the lookup of a 2P-set as the set of nodes V . There is no need for using set CRDT for the edges since a new edge is only added with a new node. Thus, an edge cannot be added and removed concurrently.

LG-Tree In a Last-writer-wins Graph Tree (LG-Tree) a node, or a edge, appears in the lookup if and only if the operation with the higher timestamp applied on it is an add. LG-Tree uses the lookup of LWW-element-Sets as the sets of nodes V and edges E. The operations become add(n, m, t) and rmv(N, F, t). The execution of the operations consists in updating the timestamp and the visibility flag if the operation timestamp is newer that the attached timestamp.

CG-Tree An Counter Graph Tree (CG-Tree) a node or a edge appears in the lookup if and only if the sum of add operations applied on it is greater than the sum of rmv operations. A CG-Tree uses the lookup of C-Sets as the sets of nodes V and edges E. The operation add and rmv associate an increment to each element appearing in these operation. The execution of the operation applies this positive or negative increment to the targeted elements.

OG-Tree

In an Observed-remove Graph Tree (OG-Tree), a node or a edge appears in the lookup if and only if the tags associated by add operations applied on it are not all removed by rmv operations. An OG-Tree uses the lookup of OR-Sets as the sets of nodes V and edges E. The operation add associates a unique tag and rmv associates a set of tag to each element appearing in these operation. The execution of the operation adds or removes the tag(s) to the targeted elements.

Set lookup

From all the above tree CRDTs, we can obtain (V L , E L ) a pair of lookup sets which is eventually consistent since lookup of the set CRDTs is eventually consistent. However, in case of concurrent modifications, this pair (V L , E L ) is not a graph since E L may contain edge on nodes not in V L . For instance in the LG-Tree, if the operations add(n, m, t) and rmv(N, F, t ) with n ∈ N and t > t are generated concurrently, we get (m, n)

∈ E L while n / ∈ V L . The pair (V L , E L ∩ (V L × V L )
) is a graph but may not be a tree. It can be non-connected if a replica adds a node under m and another replica removes m concurrently. Also, there can be several paths between the root and a node since two replicas can add concurrently a node under two different fathers. Moreover, such a graph may contains cycles if, for instance, a replica generates add(x, root) followed by add(y, x) and another replica generates concurrently add(y, root) followed by add(x, y). We propose to compute a lookup from the pair (V L , E L ) on order to obtain a lookup which is an eventually consistent tree. In the following sections, we propose different policies to firstly reconnect or drop the isolated components to obtain a rooted graph, and to secondly to express a tree from the rooted graph.

Connection policy

The operations add(n, m)||rmv(N, F ) with m ∈ N and n / ∈ N conflicts since a naive lookup of the underlying sets CRDTs of nodes and edges is a non connected graph. However, several solutions can be designed to produce a graph which is rooted, i.e. with at least one path from the root to any other node. The solutions can be to "skip" such add, to "recreate" the removed ascendant(s), or to place such added nodes "somewhere" in the tree (for instance under the root). We compute a rooted graph (V C , E C ) directly from the lookup V L and E L of the supporting sets CRDTs.

We note

E G = (E L ∩ (V L × V L )). We call a orphan node, a node n in V L such that (root, n) / ∈ E * G .
Since a node is always added with an edge directed to it, an orphan node n has at least one edge in (m, n) ∈ E L directed to it; if m / ∈ V L , we call (m, n) an orphan edge, elsewhere m and n are parts of the same orphan component.

To compute (V C , E C ), we start by adding all non-orphan nodes and the edges between them in (V L , E L ). Then, we treat the orphan nodes in V L . Considering each orphan node n, we can apply the following "connection" policies : reappear recreates all paths leading to orphans components. We add all edges (n, y) such that y ∈ V L . For each orphan edge (x, n) we add all paths (nodes and edges) that have ever existed between root and y. This policy requires to keep as tombstones all the edge ever added to the graph. This algorithm is in Θ(|E| + |V |). compact places the orphan components under the connected node that have ever a path to it. We add all edges (n, y) such that y ∈ V L . For each orphan edge (x, n), we add (z, n) for all z which is a non-orphan node such that a path that does not contains non-orphan nodes have ever existed between z and x. This policy requires to keep as tombstones all the edge ever added to the graph. Let connectSet be a set associated on all node. By default this set is empty. We execute the follow algorithm with node previously deleted and connected to orphans edges. Using any of the above policies ensures that (V C , E C ) is a rooted graph for any tree CRDT. Such a graph is eventually consistent and there is at least one path from root to each other node.

The reappear and compact policies require to keep all edges that have ever existed as tombstones. In some set CRDTs approaches (such as CmRDT LWW-Set or all set CvRDTs), these tombstones already exist in the payload. In the compact policy, we can store only the set of node that have ever been accessible from one node.

Mapping policy

The operations add(n, m)||add(o, p) with n = o and m = k conflict. A node cannot be concurrently added under two different nodes, since the graph may contains different paths to a node and directed cycles. To obtain a tree we start from the rooted graph (V C , E C ) and we apply one of the three following "mapping" policies.

several : We construct all the acyclic paths in the graph. Thus, copies of the node can appear in different places in the tree. Remove a copy of the node removes all the others. The algorithm is a simple depth-first that begins on root node. For each node, the algorithm is 1. Mark the node.

2. Construct a list l composed of recursive calls on all unmarked children nodes.

3. Unmark the node. one : This policy adds in the tree each node in V L only once. Thus, the algorithm must make a choice on the edges : newer : The "newer" variation needs a timestamps on edges to select the newer. This is adapted to LG-Tree that already has such timestamp 11 . We construct a Maximal Spanning Tree (MST) with the edges sorted by timestamp. We will not obtain a tree composed with only newest edges since such edges may constitute a cycle. But we will obtain a tree with the maximal sum of timestamp. This tree will be rooted since root has no edge directed to it and must be included in the MST. Building a MST in a directed graph can be achieved in Θ(|E| + |V |log|V |) [START_REF] Gabow | Efficient algorithms for finding minimum spanning trees in undirected and directed graphs[END_REF].

higher : This variation is designed for CG-Tree and OG-Tree. We construct a MST maximising edges counters or edge tags numbers.

shortest : This variation can be used for all type of tree. For each node we select the shortest path to it. A Breath-first algorithm can be used to produce the tree in Θ(|E| + |V |).

zero : The zero policy removes all subtrees rooted by nodes which have more than one edge directed to them. For each node the algorithm checks the number of input edges. The algorithm traverses the graph starting from the root but does not add nodes with an in degree greater than two and does not visit its children. The algorithm is in Θ(|V | + |E|).

Discussion on graph trees

Thus, we can obtain a lookup using a graph structure managed by set CRDTs. This lookup function is composed in three phases. The first phase is the lookup of the underlying set CRDT. The second phase computes a rooted graph. The third phase expresses a tree from the rooted graph. Such data types are obviously CRDTs since the underlying sets are eventually consistent, and since the lookup tree is computed with deterministic policies 12 , this lookup is also eventually consistent. However, depending on the policy chosen, the client application can observe moves on the lookup tree. For instance, using a root policy, if a removed father is added again, its orphan son will move from the root to its original place.

We call monotonic policy, a policy where add and rmv operations do not move an existing node in the lookup. The non-monotonic policies are : root, compact and all one variations. The monotonic policies are skip, reappear, zero and several.

The lookup function works after each modification of the tree. The complexity of this function could be up to factorial for the several policy. So, some optimizations are useful. We call incremental lookup function, a lookup function which reuses an previous calculus to avoid recompute entire tree. For example, in the reappear policy, when an orphan node should be added, the incremental lookup function adds to the tree the several/one/zero paths leading to this node. On the other hand, when the father of an orphan node is added, the other reappeared paths must be removed of the lookup. Finally, when an orphan node is removed, the reappeared paths should disappear. Such incremental versions have the same worst-case complexity than non-incremental ones but are slightly more efficient. However, eventual consistency of the lookup is less straightforward to ensure in such incremental versions.

A special case : 2G-Tree

A two phases graph tree (2G-Tree) uses a 2P-set [START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF] as the set of nodes V . A 2P-Set consists in defining unique elements that can only be added once on all replicas. Thus, node and edge cannot be added and removed concurrently. The other main advantage of the 2G-Tree is that the conflict add||add does not occurs since a node can only be added once. Thus, 2G-Tree do not require any mapping policy.

In a 2G-Tree, the conflict add(n, m)||rmv(N, F ) with m ∈ N and n / ∈ N can be resolved using solutions presented above. Assuming that node can be found in constant time (using hash table), the skip policy can be computed incrementally in Θ(1) time. Indeed, the remove of a node consists in remove of the entire subtree, and addition of an orphan node has no effect. Moreover a CvRDT 2G-Tree can send constant size messages for remove : rmv(n) with n the root of the subtree. The reappear and compact policy can be computed in Θ(|V |) since there is only one path, of size at most |V |, leading to a given node. Finally, in the root policy, the addition of a node is always in Θ(1) time.

EDGE trees

Since a node is always added with an edge directed to it, one can represent a tree using only edges. Such a choice leads to a data structure we call edge tree. Given a finite or infinite set of nodes V , an edge tree is a subset of all ordered pairs. An edge tree has a root with no edge directed to it, and for all edge, it exists one unique parent edge. A subtree is rooted by a node and include the edge 14 directed to this node and a set of connected edges. Definition 2. An edge tree T rooted by root is a subset of V × V such that for all (x, y) ∈ T either x = root, or there exists a unique z ∈ V such that (z, x) ∈ T .

The set S is a subtree rooted by

n ∈ V of T if S ⊂ T , ∃(x, n) ∈ S, ∀(a, b) ∈ S. b = n =⇒ (n, b) ∈ S *
and T \ S is an edge tree.

We have the following formal definition of the sequential operations on an edge tree.

• pre(add(n, m), T ) ≡ ∃(z, m) ∈ T

• post(add(n, m), T ) ≡ (m, n) ∈ T

• pre(rmv(S), T ) ≡ subtree(S, T )

• post(rmv(S), T ) ≡ S ∩ T = {}. 14 In case of concurrent modifications, their can be several such edges.

RR n°7825

As for graph tree, the post-conditions of add and rmv conflict and an edge tree CRDT uses a set CRDT to handle the set of edges. We can apply the same connecting and mapping policies than for graph tree to compute a tree lookup of the CRDT set. We simply consider that a node belong to a tree if and only if it appears on an edge of tree.

Such GE-Tree, 2E-Tree or OE-Tree will have exactly the same behavior than respectively GG-Tree, 2G-Tree and OG-Tree. Indeed, in such trees, we cannot remove edges (GG-Tree), or we cannot have an edge directed to a removed node (2G-Tree and OG-Tree). Thus, GE-Tree, 2E-Tree and OE-Tree are optimizations of their respective xG-Tree.

The LE-Tree and CE-Tree have a different behavior than LG-Tree and CG-Tree. Indeed, let consider a first replica that inserts a node x under a node y, and then removes x, while a second replica insert x under a node z. Depending on the timestamps (LG-Tree) or on if another replica removes (y, x) concurrently (CN-Tree), the node x -and thus (z, x) -can appear or not in the lookup. In LE-Tree and CE-Tree, (z, x) appears in the lookup.

Word trees

In this section we introduce word trees, another data structure to manage concurrently modified trees. A word represents a path in the tree, a tree can be defined as a set of words : the set of paths existing in this tree. We use the standard definitions about words. Let Σ be a finite -or infinite -ordered alphabet, a word is a finite sequence of elements from Σ. The length of a word w, noted |w| is the number of elements of w. We denotes ε the empty word. The concatenation vw is the word formed by the joining end-to-end the words v and w. The set of all strings over Σ of any length is the Kleene closure of Σ and is denoted Σ * .

We define a tree as a set of the words representing all the paths in the tree. Since all the paths are present in the set, any prefix of a path is also a path of the tree. The empty word ε is the root of the tree. Definition 3. A word tree T is a subset of Σ * , such that ε ∈ T and ∀p, e ∈ Σ * . pe ∈ T =⇒ p ∈ T .

A subtree is defined as complete set of paths with a common prefix. Definition 4. In a tree T , a subtree P is a subset of T such that T \ P is a tree and such that ∃w ∈ T. ∃S ⊂ Σ * . P = {ws|s ∈ S} and S is a tree.

As for graph tree, there is two operations to modify a word tree. The operation add(n, p) with n ∈ Σ and p ∈ Σ * adds a new path and rmv(P ) removes the set of paths representing a subtree.

• pre(add(n, p), T ) ≡ p ∈ T ∧ pn / ∈ T

• post(add(n, p), T ) ≡ pn ∈ T

• pre(rmv(P ), T ) ≡ P ⊂ T ∧ subtree(P, T )

• post(rmv(P ), T ) ≡ P ∩ T = {}

RR n°7825

With such pre-and post-conditions, we can ensure that the set T is sill a tree in case of sequential modifications. In case of concurrent modifications, word trees differ from graph trees since only add||del conflicts occurs.

Concurrent addition and remove of the same element

A for mathematical set, the post-conditions of add(n, p) and rmv(P ) with np ∈ P conflicts since convergence cannot be achieved. As for graph trees, we can use set CRDT to bypass the conflict. The obtained tree CRDT have the following behavior :

GW-Tree a path can only be added and never removed.

2W-Tree a path can only be added once. Such a CRDT has the same behavior than the 2G-Tree and 2E-Tree.

LW-Tree a path appears in the lookup if and only if the operation with the higher timestamp applied on it is an add.

CW-Tree a path appears in the lookup if and only if the number of add operations applied on it is greater than the number of rmv operations.

OW-Tree a path appears in the lookup if and only if the tags associated by add operations applied on it are not all removed by rmv operations.

All the above data types are obviously eventually consistent. But the lookup presented must be a tree even in case of the concurrent addition of a node and remove of its father.

Concurrent addition of a path and remove of the prefix

As for graph and edge trees, the naive execution of operations add(n, p) and rmv(P ) with p ∈ P produce a set of path which is no longer a tree. Thus we need to compute a lookup which is a tree. We compute a lookup tree LT from the set of path LS obtained from the lookup of the supporting set CRDT.

We call a orphan path, a path in LS that has a prefix which is not in LS. We start by adding all non-orphan paths of LS to LT . Then, we treat the orphan paths in LS in length order (shortest first, then Σ order). Considering each orphan path a 1 a 2 . . . a n ∈ LS with ∀i ∈ [1, n]. a i ∈ Σ, we can apply the following connection policies : skip drops the orphan path.

reappear recreates the path leading to the orphan path. We add all a 1 . . . a j with j ∈ [1, n].

root places the orphan subtree under the root. We add a j . . . a n to LT with j such that a 1 . . . a j-1 / ∈ LS and ∀k ∈ [j, n], a 1 . . . a k ∈ LS.

compact places the orphan subtree under its longest non-orphan prefix. We add a 1 . . . a m a j . . . a n to LT with j and m such that m < j and a Using any of the above policies ensures that the lookup trees presented to the client by any CRDT tree are eventually consistent.

Theorem 1. The lookup sets LT computed using a skip, root, reappear, or compact policy are tree and are eventually consistent.

Proof. Since the set of paths LS is eventually consistent, and since the paths are treated is the same order and since each policy is deterministic, the computed set of paths LT is eventually consistent.

Set of path LT is a tree since :

skip there is no orphan path in LT .

reappear we add an orphan path in LT with all its prefixes.

root a suffix a j . . . a n is added to LT only if ∀k ∈ [j, n], a 1 . . . a k ∈ LS. Thus, all the prefixes a j . . . a k were also added to LT . Computing a lookup tree LT every time the lookup set LS is modified ensures easily eventual consistency, but only some policies are monotonic. We consider a policy as monotonic if the add(p) operation do not moves any already existing node in tree. The root and compact policies are not monotonic since when the missing ascendants are added again, the orphan subtree moves to its original place.

The advantage of monotonic policies is that the client of the tree CRDT will not observe such move, and that a client operation on an orphan path do not require a complex translation into an operation on the supporting set CRDT.

Complexity and optimisation

Lets assume that a hash table is used to implement the set of paths. Thus, checking for all prefixes of path if they belongs to a set have an average time complexity proportional to the length of the path. Thus, the time complexity to apply a policy to a path is linear. Also, the time complexity to compute a lookup tree is Θ(pk) in average, with p the number of paths in LS and k the average length of these paths. The worst case time complexity is Θ(n 2 ) with n the number of paths in T .

However, at least for the monotonic policies, we can compute LT incrementally, i.e. without parsing the whole set LS.

skip When an orphan path is supposed to be added in the lookup, we drop it. When an non-orphan path p is added, we add recursively all pa ∈ LS with a ∈ Σ. When a path n is supposed to be removed in the lookup, we remove all the paths that are prefixed by n. Moreover, a tree CmRDT can send only the operation rmv(n) with n the common prefix of the subtree, since the whole subtree will be removed.

reappear In the reappear policy, when an orphan path is removed we must remove the reappeared path to ensure eventual consistency. This can be done by marking the reappeared paths as "ghosts". When path previously marked as ghost is supposed to be added in the lookup, we unmark it. When an orphan path n is supposed to be added in the lookup, we add all the prefixes of n that are not existing and we mark them as ghost. When a path n is supposed to be removed in the lookup, if n is the prefix of a non-ghost path, we mark n as ghost, elsewhere we remove n and all the ghost prefixes of n that are the prefixes of not any ghost.

Ordered trees

In this section, we present ordered trees, where the set of children of a node is totally ordered. For this we need to add to the unordered trees presented above, an additional information called Position Identifier (PI) which allows to order the children. These position identifiers must be totally ordered to ensure eventual consistency and defined within a dense space to allow insertion of a node at an arbitrary position. These position identifiers can be associated to nodes or edges.

To obtain position identifiers, an idea to use PI already defined for sequence editing CRDTs such as Logoot [START_REF] Weiss | Logoot-undo: Distributed collaborative editing system on p2p networks[END_REF], Woot [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF], WOOTO [START_REF] Weiss | Wooki: a P2P Wiki-based Collaborative Writing Tool[END_REF], RGA [START_REF] Roh | Replicated abstract data types: Building blocks for collaborative applications[END_REF] or Treedoc [START_REF] Preguiça | A commutative replicated data type for cooperative editing[END_REF]. Such PIs are Unique Position Identifier (UPI) and thus constrain the behavior of the trees to some kind of two-phases set that does not allow concurrent insertions of the same element or re-insertions. So, we propose a new non-unique position identifier to allow such operations.

In the following figures, a plain arrow represents the child relation between node, and a dotted arrow represents the order between children.

Unique positioning for nodes

We associate each node to an unique position identifier (UPI). The order between the children of a node is given by their UPI. Since only graph trees manage nodes and since position identifiers are unique, we obtain a 2G-Tree. If a node is added twice concurrently, even at the same place in the ordered tree, we obtain two different nodes. The formal definition of the operation rmv do not change, a node is a pair (element, U P I) and an edge is a pair of node. The formal definition of operation add becomes :

• pre(add((n, u), (m, v)), (V, E)) ≡ (n, u) / ∈ V ∧ (m, v) ∈ V ∧ unique(u) • post(add((n, u), (m, v)), (V, E)) ≡ (n, u) ∈ V ∧ ((m, v), (n, u)) ∈ E
The conflict add||add does not occurs, since a node can only be added once with an UPI. In figure 10, a replica produces add(Z, A) while another replica produces add(Z , B) concurrently, but they are considered as two different elements with same characteristics. A tree with UPI associated to nodes can be built using any sequential editing UPIs. However the WOOT and RGA UPI requires tombstones and thus are more adapted to a 2P CvRDT that contains these tombstones. For 2P CmRDT, the Logoot or Treedoc UPI approaches are more suitable. The complexity of the children order computation depends on the approach used. An example of such construct is [START_REF] Martin | Collaborative peer to peer edition: Avoiding conflicts is better than solving conflicts[END_REF].

Unique positioning for Edges

To allow concurrent insertions on the same node at two different places in the tree or to build edge or word tree, we propose to associate UPI to edges. The order between the children of a node is given by the UPI of the outgoing edge. In graph and edge trees an edge becomes a triple (m, n, u) with m and n two nodes and u an UPI. In word trees, a path becomes u 1 a 1 u 2 a 2 u 2 . . . u n a n with a i elements of Σ and u i UPIs. The difference between ordered trees with edge positioning and node positioning is illustrated in figures 12 and 10.

Graph Tree

• pre(add(n, m, u), (V, E))

≡ n / ∈ V ∧ m ∈ V ∧ unique(u) • post(add(n, m, u), (V, E)) ≡ n ∈ V ∧ (m, n, u) ∈ E Edge Tree • pre(add(n, m, u), E) ≡ ∃(z, m, v) ∈ E ∧ unique(u) • post(add(n, m, u), E) ≡ (m, n, u) ∈ E Word Tree • pre(add(n, p, u), T ) ≡ p ∈ T ∧ pun / ∈ T ∧ unique(u)
• post(add(n, p, u), T ) ≡ pun ∈ T Such an edge tree is a 2E-Tree since an edge can only be added once. And such a word tree is a 2W-Tree since a path can only be added once. For graph tree, we can manage node using any set CRDT to obtain GG-Tree, 2G-Tree, LG-Tree, CG-Tree or OG-Tree. As for nodes UPI, any sequential editing UPI can be chosen, but these are more or less adapted to the underlying set CRDT. Logoot and Treedoc without tombstones are more appropriate to 2x and OG CmRDT. While WOOT and RGA are more appropriate to LG-Tree, CG-Tree and all CvRDT, As for unordered trees, the conflicts between addition of a node and remove of its father can be resolved using any connection policy. Conflicts between two concurrent additions of the same element in graph trees can be resolved using any mapping policy.

In graph tree with edge positioning, two concurrent insertion of a node at the same place (same father and same order between children) generates two edges (see Figure 13). In edge tree (and word tree), using a unique position identifier enforces to generate two instances of the edge (and path in word tree). To allow a different behavior, the position identifier must be non-unique. WOOTR elements are defined inductively upon an alphabet Σ (or set of node).

• and are elements • a triple a, e, f is an element if a ∈ Σ and e and f are elements.

The elements and mark respectively the begin and the end of a sequence. When a character a is inserted between two elements p and n, we add the element a, p, n . We call p the previous element and n the next element of this new element. The set of the WOOTR elements constitutes the characters present in the sequence. The elements are ordered using the WOOT algorithm [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF] assuming that elements with the same previous and next elements are ordered using their character. For instance, starting from an empty sequence, if a replica inserts a, followed by b, while another replica inserts c concurrently, we obtain the set { a, , , b, a, , , , c, , } and the sequence is abc.

Since elements are not unique, they can be inserted concurrently by two different replicas. However, they can also be added and removed concurrently. Thus, as in any set, we need to manage these concurrent operations. Eventual consistency can be achieved using a set CRDT such as LWW-Set, CG-Set or OR-Set. Contrary to the original WOOT, we do not require to keep deleted elements as tombstones since, when a remote insertion occurs, the WOOT algorithm can find the place of the deleted previous or next element before inserting the element itself. This is particularly suitable for CmRDT OR-Set and C-Set that do not keep all tombstones.

The size of WOOTR elements can be proportional to the size of the document. Due to this size, such a sequential editing CRDT may not be adapted to realtime collaborative text editing [START_REF] Ahmed-Nacer | Evaluating crdts for real-time document editing[END_REF]. However, we think that it can be useful for trees, since in tree the element are distributed under different fathers, the WOOTR elements grow more slowly.

RR n°7825

Non-unique position identifier

With non-unique position identifiers, only one edge (or path) will be present in the tree in case of concurrent insertion of an element at the same place in the tree. A non-unique position identifier can be used to order any variation of graph, edge or word tree.

For instance, the WOOTR identifier can be added to edge in graph or edge trees. Such edges are ordered pair (x, w) with the x the father node and w a WOOTR element defined on the set of nodes. In word tree, a path becomes w 1 . . . w n a string of WOOTR elements defined on the alphabet.

Conclusion

In this report, we have proposed several tree conflict-free replicated data types (CRDT). These data types are based on set CRDTs. As any CDRTs, tree CRDTs are eventually consistent and converge without requiring any synchronization.

The unordered tree data types are constructed using a tree representation (graph, edge or word), a set CRDT, one connection policy and one mapping policy (for graph and edge tree). Every combination of choices is possible and is a tree CRDT. Each of the choice correspond to the desired semantic to resolve the two or three different conflicts between operations. The choice of the set CRDT defines the semantic of the concurrent addition and remove of an element. The choice of the connection policy defines the semantic of concurrent remove of an element and addition of a child. The choice of the mapping policy, if required, defines the semantic of the concurrent additions of an element. With such a construct we give to the application programmer the entire control of the behavior of the tree CRDT.

The policies designed make some arbitrary choices to resolve the conflicts. We think that arbitrary choices are mandatory to ensure scalability in large-scale system. However, the application may have a particular semantic on nodes or operations, or the final user may be required to resolve the conflict. To facilitate such mechanism, we can adapt the root policy and the zero policy. We can adapt the root policy to place orphan elements under a special "lost-and-found" node and the zero policy to present to the application the conflicting nodes and edge separately from the tree.

The ordered tree data types are constructed upon unordered trees CRDT. They consist in associating a totally ordered position identifier to elements of the tree. These position identifier comes from existing sequence editing CRDT and ensure eventual consistency without synchronisation. Ordered trees share the same behavior than the corresponding unordered tree except that a tree node can be add at different positions under another node. The choice between the kinds of position identifiers is a question of performance and adaptability with the underlying set CRDT. Moreover, we introduce a new sequence editing CRDT called WOOTR. This sequence editing CRDT is the first to allow reintroduction of an element and to consider that concurrent insertion of an element at the same position is the same operation.

All the combination presented can be used for any application that require a tree. However, we think that some combination are more adapted to some RR n°7825 application context. For instance the unordered graph trees are more adapted to applications managing a composite pattern or a file system data structure. Indeed, in Unix-like files system, the hard links allow to place a file or a repository in several different repositories. One another hand, ordered word trees seems more adapted to collaborative editing of structured documents [START_REF] Martin | Scalable xml collaborative editing with undo[END_REF].

Finally, some constructs, especially trees builds on 2P-Set, are very efficient, other variations and some policies, especially the several policy in graph and edge trees, are quite costly in term of computation complexity. We need to establish the actual scalability of the constructs trough experimentation on realistic data set since the actual computation cost depends highly on the degree of concurrency.

•

  pre(add(a), S) ≡ a / ∈ S • post(add(a), S) ≡ a ∈ S • pre(rmv(a), S) ≡ a ∈ S • post(rmv(a), S) ≡ a / ∈ S

Figure 2 :

 2 Figure 2: Last Writer Wins Set : LWW-Set[START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF]

Figure 3 :

 3 Figure 3: Counter Set : C-Set[START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF]

Figure 4 :

 4 Figure4: Observed-Remove Set : OR-Set[START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF]

Figure 5 :

 5 Figure 5: Cycle generated by concurrent additions

  skip drops the orphan node. This algorithm consists simply on a graph traversal starting from the root and is in Θ(|E L | + |V L |).

Figure 6 :

 6 Figure 6: skip policy

Figure 7 :

 7 Figure 7: reappear policy

Figure 8 :

 8 Figure 8: root policy

Figure 9 :

 9 Figure 9: Compact policy

4 .

 4 Returns a tree composed of the node and the list l of children Obtaining a description of all simple paths in a directed graph can be computed using O(|V | 3 ) matrix operations. Such a tree contains up to |V |! edges in case of a complete graph.

compact a path a 1

 1 . . . a m a j . . . a n is added to LT only if ∀k ∈ [j, n], a 1 . . . a k ∈ LS. Thus all the prefixes a 1 . . . a m a j . . . a k were also added to LT .

Figure 10 :

 10 Figure 10: Concurrent operations add/add with node positioning

Figure 11 :

 11 Figure 11: concurrent operations add/del with skip policy

Figure 12 :

 12 Figure 12: Concurrent operations add/add with edge positioning

Figure 13 :

 13 Figure 13: Two concurrent insertions at the same place with edge positioning

  Example 1. For a lookup LS = {ε, a, ab, ac, abcd, abcde, abcdef g}, the orphans path are {abcd, abcde, abcdef g} and we obtain LT equal to :

	skip {ε, a, ab, ac}
	reappear {ε, a, ab, ac, abc, abcd, abcde, abcef, abcdef g}
	root {ε, a, ab, ac, d, de, g}
	compact {ε, a, ab, ac, abd, abde, abdeg}

1 . . . a m ∈ LT and a 1 . . . a m+1 / ∈ LS and a 1 . . . a j-1 / ∈ LS and ∀k ∈ [j, n], a 1 . . . a k ∈ LS.

RR n°7825

For instance, adding a whole subtree consists of a list of add operations; remove a node while keeping its children consists of a list of rmv and a list of add.RR n°7825

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

We consider that the graph can be modified trough two minimal operations add and rmv. The operation add(n, m) adds a node n in the graph under

* This work is a delivrable of french national research programs ConcRDanT (ANR-10-BLAN-0208).


Jonathan-Christofer Demay

Frédéric Majorczyk

Eric Totel

Frédéric Tronel

Detecting illegal system calls using a data-oriented detection model

The most common anomaly detection mechanisms at application level consist in detecting a deviation of the control-flow of a program. A popular method to detect such anomaly is the use of application sequences of system calls. However, such methods do not detect mimicry attacks or attacks against the integrity of the system call parameters. To enhance such detection mechanisms, we propose an approach to detect in the application the corruption of data items that have an influence on the system calls. This approach consists in building automatically a data-oriented behaviour model of an application by static analysis of its source code. The proposed approach is illustrated on various examples, and an injection method is experimented to obtain an approximation of the detection coverage of the generated mechanisms.

Introduction

Generally speaking, an attack against an application consists in exploiting a vulnerability in order to violate the confidentiality or integrity properties of the system or the application under attack. In the context of intrusion detection methods at application level, a lot of existing work focuses on the detection of the violation of the integrity property. Attacks against a process can consist in corrupting either the control-flow of the program (e.g., to execute injected code), or the data items manipulated by the program during its execution. A lot of papers focus on the detection of the program control-flow corruption, either considering the process as a white box, or seeing it as a black box. An exemple of a white box approach is to verify during the execution that the control-flow graph of the program is legal. An example of the black box approach consists in verifying that the trace of the process execution in the system is correct (e.g., the sequence of system calls [START_REF] Hofmeyr | Intrusion detection using sequences of system calls[END_REF]). Both approaches can be subject to false negatives, as the attacker can either corrupt data items that do not influence the control-flow of the program, or perform attacks that mimic [START_REF] Kruegel | Automating mimicry attacks using static binary analysis[END_REF] the normal behaviour of the application. Various papers [START_REF] Kruegel | On the detection of anomalous system call arguments[END_REF][START_REF] Bhatkar | Dataflow anomaly detection[END_REF][START_REF] Mutz | Exploiting execution context for the detection of anomalous system calls[END_REF][START_REF] Feng | Anomaly detection using call stack information[END_REF] have enhanced the black box approach in order to detect these types of refined attacks.

In this paper, we propose a white box approach for intrusion detection that aims at detecting the corruption of the data items in an application, so as to detect erroneous system calls (e.g., their arguments are not correct, or the data that led to their execution were incorrect). The approach relies on the building of a data-oriented behaviour model. This method can be presented as an interesting complement to the usual control-flow corruption detection method, in order to detect data oriented attacks. To attain this goal we use static analysis to build constraints on intrusion sensitive data items, then we instrument the software with executable assertions that check these constraints during the execution of the program.

The contribution of this paper is not to provide new static analysis techniques, as our work relies on an off-the-shelf static analyser called Frama-C [START_REF]CEA: Frama-c, framework for modular analysis of c[END_REF]. However, we want to show on real-life examples that a detection model can be built by static analysis and detect data attacks (even unknown ones).

The paper is organized in the following way: after a short related work section on white-box attack detection, we show how to build the behaviour model and emphasize the accuracy of the model on a previously known attack. Then we show the results of the software instrumentation on various examples. At the end we evaluate on an example the detection rate we can expect from the generated detection mechanisms.

Related Work

We believe that white box mechanisms can help improving the detection performance as they are able to take advantage of the internal state of the monitored program. Indeed, they have access to all the internal data structures and algorithms used by the program.

That is the case, for example, with Control-Flow Integrity [START_REF] Abadi | Control-flow integrity[END_REF] and Program Shepherding [START_REF] Kiriansky | Secure execution via program shepherding[END_REF]. These generic techniques verify the integrity of the control-flow of a program. A control-flow graph of the program is computed prior to its execution and then used at run time to check the integrity of the process control-flow. Because mimicry attacks still need to force the program control-flow to deviate from valid execution paths, they are caught by these approaches. However, unlike our approach, all those techniques are completely ineffective against computation data attacks (also called non-control data attacks [START_REF] Chen | Non-control-data attacks are realistic threats[END_REF]), since these attacks are performed using a valid execution path.

Other white box approaches that focus on non-control-data attacks and that do not exhibit this weakness have been proposed. For example, Write-Integrity Testing [START_REF] Akritidis | Preventing memory error exploits with wit[END_REF] enforces control-flow and data-flow integrity in a program. In the work on Data Flow Integrity [START_REF] Castro | Securing software by enforcing data-flow integrity[END_REF], a data-flow graph is computed prior to the execution. It contains, for each data item read by an instruction, the set of instructions that may have written its current value. This data-flow graph is then used at run time to verify the integrity of the data flow of the process. If the program has a vulnerability that is exploited to corrupt some data, the next time this data is read a deviation from the data-flow graph will be observed allowing thus the detection of the attack. This type of approach is very effective against all kinds of non-control-data attacks, but use a very different philosophy than our approach. They focus on the illegal modification of the data, whereas in our approach we focus on the correctness of the data. As a consequence some attacks missed by the data-flow integrity method (such as an illegal value stored in a correct variable) can be detected by our approach. Conversely some illegal writes can be missed by our approach (a legal value can be written in an incorrect variable), making both approaches complementary.

In this section, we explain how non-control-data attacks are real threats and how a data-oriented behavior model can detect them. We also present SIDAN3 (Software Instrumentation for the Detection of Attacks on Non-control-data) [START_REF] Demay | Sidan: a tool dedicated to software instrumentation for detecting attacks on non-control-data[END_REF], a tool we have developed that implements our detection model. Chen et al. [START_REF] Chen | Non-control-data attacks are realistic threats[END_REF] have demonstrated that non-control data attacks can be as severe as control-data attacks on various real world vulnerabilities. Among them, a vulnerability found in the implementation of the open source ftp server wu_ftpd will serve as an example to illustrate our approach. Figure 1 (left column) is an excerpt of the original code exhibiting the same vulnerability. Line 10, a string taken as user input (line 7) is printed without using a string format. Consequently, a user can forge an incorrect buffer containing string formats that allows to write directly in memory. In this case, the target could be the uid variable. As a consequence, the attacker can elevate its privilege at line 12, without corrupting the execution path, by forcing the parameter of the seteuid call to be the administrator identifier (zero). This example shows how such an attack violates a very simple constraint on the uid variable. Indeed, the uid variable should remain constant during the execution of the loop (lines 7 to 13) and should be equal to the value it has been assigned at uid (line 2). The problem we tackle in this paper is to automatically build such constraints in order to detect attacks at runtime.

Data oriented detection Model

In our approach, we consider that an attacker aims at modifying data items in the memory space of a process in order to execute one or more incorrect system calls. This objective can be fulfilled in two ways: either the attacker alters variables that influence the internal control-flow of the program (and thus executes system calls in an incorrect context), or the attacker modifies directly or indirectly the values of the parameters of one or more system calls (and thus executes legal system calls with incorrect values). Both types of attacks aims at modifying non-control data items in the program. Note here that non-control data items are all variables used by the program source code, and can thus have an impact on the control-flow of the application. They are opposed to control-data items that are used by the system (and not the application) to control the execution flow of the application (e.g., a return adress on the stack).

In order to detect these modifications, we propose to identify the set of constraints that should be verified at runtime for these items. Generally speaking, these constraints can be divided in two classes: the variation domain of the variables (e.g., a variable can take a restricted set of values), and the relationship between the variation domains of the variables (i.e., when a variable has particular values, other variables take a defined set of values). If we only check if a variable is within its variation domain, it may be easy for an attacker to impose a reasonable value that would fit in the variation domain, but that is incorrect in the context of the program. Clearly, if we can maintain the relationship with other variables, it will be more difficult for an attacker to modify simultaneously several variables that depend on each other while keeping the program in a consistent state. As a consequence, we propose to define a data behaviour model for intrusion detection that aims at taking into account these requirements.

Formally, we define for a given system call SC i its data behavior model by a triple (SC i ,V i ,C i ) where V i is the set of variables the system call depends on, and C i the set of constraints on these variables that can be deduced from the program analysis. We can define the normal data behavior model of the program by the set of all triples, DBM = {∀i, (SC i ,V i ,C i )}. In the following section, we address the two problems faced to build this model: how to determine the set of variables a system call depends on, and how to obtain the constraints that must be verified on these variables at runtime.

Building the set of variables Building V i requires the ability to determine in the program which are the variables that influence the execution of the particular system call SC i . Generally speaking, a system call can depend on a variable in two different ways: a variable either has an influence on the path in the program that leads to the execution of SC i or influences the parameters of SC i . These sets of variables can be built by using a static analysis technique called program slicing [START_REF] Weiser | Program slicing[END_REF]. A program slice can be defined as the parts of a program that potentially affect the values computed at some point of interest of this program. In our case, we are looking for all the variables that influence a system call, and thus all variables that are in the program slice whose point of interest is the system call itself. In the static analysis field, the computation of a program slice is generally based on the computation of a program dependency graph (PDG) [START_REF] Kuck | Dependence graphs and its use in optimization[END_REF]. The PDG is a directed graph whose vertices correspond to statements and control predicates, and edges correspond to data and control dependencies. This graph can be used to exhibit the set of variables a particular system call depends on, and the type of dependency. In our implementation, we directly use the PDG notion to discover in the program all variables a system call depends on. To illustrate this paragraph, we can consider the example on Figure 1: the seteuid call at line 5 depends on one vari-able: uid. However, the seteuid call at line 12 depends indirectly on the aux variable and directly on the uid variable.

Constraint discovery Automatically discovering constraints in the source code on the variables that are defined in the previous paragraph requires to use static analysis techniques. We could imagine any types of constraints, including for example temporal constraints. In practice, static analysis techniques often compute constant constraints, also called invariants. Indeed, any static analysis technique that is able to compute invariants from the source code fits our needs. Moreover, a popular technique for calculating such invariants is the abstract interpretation method [START_REF] Cousot | Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints[END_REF]. In practice, abstract interpretation provides a way to find properties on the variables of a program by computing abstract domains that represent abstractions of the real properties of the program. Several models have been developed to discover such invariants. Among them, we have chosen to focus on the build of numerical abstract domains, i.e., we intend to find numerical invariants. These types of domains can be classified in two groups: non-relational domains that find numerical properties on variables individually, and relational domains that permit to find numerical properties on logically linked variables. Non-relational domains include for example the interval domain [START_REF] Cousot | Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints[END_REF] (wich permits to find invariants of the form v i ∈ [c 1 , c 2 ] where v i is a variable of the program and c 1 and c 2 are numerical constants), the constant propagation domain (v i = c) and the congruence domain [START_REF] Granger | Static analysis of arithmetical congruences[END_REF] (v i ∈ aZ + b). Example of relational domains can be cited such as the polyhedron domain [START_REF] Cousot | Automatic discovery of linear restraints among variables of a program[END_REF] (α 1 v 1 +...+α n v n ≤ c), the linear equality domain [START_REF] Karr | Affine relationships among variables of a program[END_REF] (α 1 v 1 +...+α n v n = c) and the linear congruence equality domain [START_REF] Granger | Static analysis of linear congruence equalities among variables of a program[END_REF]

(α 1 v 1 + ... + α n v n ≡ a[b]
). The problem with relational domains is that the algorithms they use usually do not scale on large programs. That is why Frama-C uses computational methods that are based on non-relational domains. SIDAN Plugin in the Frama-C framework We implemented in SIDAN the computation of numerical constraints for a given system call. Frama-C provides a Value Analysis plugin that is able to provide a computation of the variation domains of the variables that influence the function calls. This plugin provides constraints of the type "integer variable x lies within the domain [0,5] in all executions" as a result. If we consider the example Figure 2, the assertion generated for the call to the function f , using the Value Analysis plugin of Frama-C alone would be a ∈ {1, 2} and b ∈ {0, 1}. Indeed, as the Value Analysis plugin uses a non-relational abstract domain, his result misses the relation between the variables a and b.

If we consider the program Figure 2, we see that when b == 0 then a == 1, and when b == 1 then a == 2. Actually, to obtain this result we have to consider that there are two paths leading to the call to the function f , and that the constraint to verify at the call to f should take these two paths into account. The Value Analysis plug-in uses an algorithm that can potentially keep in memory several invariants computation on several execution paths. The plug-in can be parametrized to define the number of paths explored in parallel by the Value Analysis plug-in, which is related to the number of states it keeps in memory before computing an union. If the number of paths explored in parallel is sufficient, the Value Analysis plug-in now has internally the information required to build these kinds of constraints. By using a hook in the Value Analysis plugin, it is possible for our plug-in to access this internal information while the analysis is performed. Thus, it allows us to build the invariant by using the variation domain of all the variables on each path. In the example we have described, the invariant generated for line 08 is ((

(b == 0) ∧ (a == 1)) ∨ ((b == 1) ∧ (a == 2))).
Note that the example we give here focuses on invariants computed for integers. In practice, the Value Analysis plug-in performs well on integers and floats, but is not very efficient for pointer analysis (at best, it detects access to an unallocated buffer and some out-of-bound access). Discovering constraints on strings is also unavailable due to the fact that the specification of the standard string functions is not included in Frama-C. In order to build some constraints on strings, we have preprocessed the source code to replace standard string comparisons by a set of character comparisons whenever possible (see Figure 3 line 3). As a result, some constraints on string buffers have been obtained in the programs we tested our approach on.

Generated assertions

In order to verify the constraints in the program, we insert executable assertions (see Figure 2 line 08), which is a technique heavily used in the dependability domain, and more precisely in defensive programming [START_REF] Goloubeva | Soft-error detection using control flow assertions[END_REF][START_REF] Vemu | Ceda: Control-flow error detection through assertions[END_REF].

The constraints that we can compute for a given system call deal with the variables that are available locally in the context of the system call. However, this call generally depends not only on the local variables but also on the variables manipulated by previous functions in the call stack. That is why it is necessary to compute invariants for all function calls that are on the path that leads to the system call. This implies that we must distribute the executable assertions on all the paths that lead to system calls. Moreover, some system calls can be performed in functions located in external libraries. As a consequence, we choose to insert executable assertions in front of each function call.

To demonstrate the assertion generation capabilities of our data-oriented detection model, we first use as an example a vulnerable version of OpenSSH.

The code in Figure 3 is inspired by this vulnerable version of OpenSSH and reproduces the basic structure of the real code. The vulnerability is located in the packet_read function and can be used to overwrite the value of the passwd variable with an empty string during the execution of do_authloop. This allows a successful authentication on the system with any known account (e.g., root) and without having to provide a valid password.

Among the assertions generated, the one located at line 11 in the example in Figure 3 has been produced by our plug-in and detects this attack against the program state.

In order to figure out the capability of our tool to generate assertions on common programs, we have applied it on SSH servers (OpenSSH and Dropbear SSH), http servers (fnord and ihttpd), and a smtp server (ssmtp). The results are summarized in Table 1. As a result, we could say that the number of assertions generated is obviously heavily dependant on the program source code.

Assessment of the detection mechanisms

Even though it is possible to test our detection mechanism against various real world attacks such as those described in [START_REF] Chen | Non-control-data attacks are realistic threats[END_REF], such a method would only cover a very small subset of all possible attacks. In order to evaluate the detection coverage of our approach, we would need to know all the vulnerabilities that afflict a program as well as every possible way of exploiting them. As it is not possible to automatically compute this from the source code, we need to define another method to evaluate the detection coverage of our model. In this section we propose a method to assess the detection mechanisms by simulating attacks against non-control-data items without prior knowledge of the vulnerabilities. Our goal is to simulate the consequences of non-control-data attacks by directly modifying in the process memory space the data items it is currently manipulating. In this section, we propose an approach to evaluate our detection mechanism that is similar to the ones proposed in the security field to help discover new vulnerabilities (fuzzing) and in the dependability field to evaluate fault detection and tolerance mechanisms (fault injection).

Simulation of attacks against non-control data

Generally speaking, a particular vulnerability usually allows the attacker to access a limited part of a process memory. However, in the worst case scenario it can give to an attacker an access to the whole memory space of a process. For that reason, our injection mechanism is given access to potentially every internal data item of the program under test. However, to accurately simulate a real non-control-data attack, we want to restrict (1) the locations and (2) the instants where an injection can occur during the execution of a program. Firstly, during such an attack not every data item is a potential target. The data items that may be of interest for an attacker are within the subset of data items that can influence the execution of the system calls. Consequently, we target only these data items (they define the locations of potential injections). Other data items are irrelevant for our simulation approach. Secondly, we will modify such items only when they are currently in use (i.e., when they are influencing the current execution of the program).

Code instrumentation and fault injection

To simulate this injection model, two problems have to be addressed: how do we determine the set of data items that are potential targets for a non-control-data attack, and how do we determine for each one of them when it is appropriate to inject a corrupted value. Clearly, the set of data we want to modify is the very same set of data items we have defined in Section 3.2.

The simplest way to determine the memory address of a variable we want to inject is to obtain it at execution time. This is why we have choosen to also embed the corrupting mechanisms within the source code. Moreover we have decided to distribute the injection mechanisms when the corresponding variables are reachable, that is right before every function call that depends on them. We used the same approach as described in Section 3.3 where we discussed the distribution of the detection mechanisms. In the end, each candidate function call is preceded by a call to the corrupting function implemented by a single external function called inject().

Each injection point is assigned a unique identifier. This identifier is passed as a parameter to the injection function. The remaining arguments are the number of variables that can be corrupted and for each one of them, its address and its size. The corrupting function is controlled by an external process using environment variables. This process controls the unique identifier of the injection that is to be activated, the variable that will be corrupted and the value used to perform the injection. An injection is triggered only once, even when the call to the corrupting function happens many times (e.g., in a loop). The tool presented in Section 3 has been modified in order to perform the instrumentation needed by our injection mechanism. Note that the set of variables A used in an assertion is always a subset of the set of variables I used in the injection process (see Figure 4). Indeed, the injection can be performed in any variable that influences the function call, unlike the assertions that only concern variables for which value constraints have been discovered.

Our goal is to evaluate our detection mechanism presented in Section 3. To do that, we need to cover a large set of memory corruptions that might be used by a malicious user to perform an intrusion. Very much like a fuzzing technique, we are going to randomly put the internal state of the process in an erroneous state. We perform various injections during the execution of the program used in our test environment in order to simulate the result of a vulnerability exploitation.

To activate a maximum of function calls in the program, we have written a set of scenarios whose goal is to make the control-flow pass through a maximum number of function calls. In the case of Dropbear SSH, we have written a set of 24 scenarios that allows us to reach 92% of the function calls.

During the injection process, for each function call that can be reached by a scenario, a random variable from the set of variables that influences the execution of this function call is chosen to be injected with a random value. Each time an attack is simulated, the controller logs if the scenario ended properly or if the process exited unexpectedly or found itself in a deadlock and needed to be killed after a time-out. The controller also logs the behavior of the process during the attack (in terms of system calls and their arguments). The whole test setup is shown in Figure 5.

Evaluation results

Using the experimentation protocol described in Section 4.2, we have performed a total of 120 000 injections on the Dropbear SSH server. As explained before for each injection, we have logged three kinds of information. Firstly, we have compared the output generated by the server during the injection with respect to the output generated without injection. These observations can be considered as an extremely accurate indicator of a potential attack. Indeed, in these cases, the modification of a single variable has been able to modify the execution of the SSH server upto the point its external behaviour (as seen by an SSH client) was changed. Note that 69.36% of the injections have lead to such an alert (either a deviation of output, or a crash of the server). Of course, while being an extremely accurate way of detecting intrusions, this approach is difficult to generalize in real life settings, since it would require to compare the output produced by the server for each command it receives with a reference output. Considering the generally extremely large set of outputs such a server can produce, this approach is hopeless. Here we were able to use such an approach because of the limited set of scenarios we have used during the assessment. Secondly, we also recorded the set of system calls (with their arguments) that were generated during normal executions of the different scenarios (training), and during injections. These recordings have been submitted afterward to an offline intrusion detection mechanism [START_REF] Kruegel | On the detection of anomalous system call arguments[END_REF]. Once again, this IDS was settled in optimum conditions, since it was trained for a given scenario. And even in these optimal conditions, note that it only detects 22.48% of injections. Finally we have recorded the alerts generated by our SIDAN tool. The results of all these measures are summarized in Table 2. A more detailed version of the obtained results is given by the Figure 6. We can see that SIDAN detects 62.36 % of the injections. This detection rate is comparable to the one obtained by the first IDS based on the comparison of the output generated by the server (but recall here, that we claim that this kind of IDS is extremely difficult to build in real settings). However, SIDAN is still prone to false negatives with at most 37.64% of injections missed. We can refine these figures by taking into account the fact that within these 37.64% of cases where SIDAN raised no alert, 10.63% where cases where : (1) neither the output generated by the SSH server deviated from the reference output. (2) nor the system call trace deviated from the reference trace. We can be highly confident that these cases do not correspond to exploitable attacks. Hence we can subtract these 10.63% from the figures obtained for false negatives for SIDAN. All in all, we can claim that the rate of false negatives for SIDAN lies within a 27.01% and 37.64%.

Conclusion and future work

In this article, we propose a sofware-level intrusion detection approach based on the internal state of the process that detects data attacks, which are missed by traditional control-flow approaches. Our mechanism relies on a data-oriented behavior model to detect erroneous states that could lead to illegal system calls. We present a tool that implements our approach by analyzing and instrumenting a program's source code. This tool has proved that our approach is useable in the context of real software and that it can detect real world non-control-data attacks (such as the null password attack on OpenSSH). We also propose a method to assess these intrusion detection systems against data attacks by using a fault injection mechanism. In the particular case of Dropbear SSH, by using our evaluation method, we have estimated, without prior knowledge of any attacks, an approximation of the detection coverage of our detection model. However, the current implementation of our tool computes the constraints needed by our detection model using only variation domains. This is clearly a limitation, because it does not permit the detection of data attacks on variables whose variation domain is statically unknown in the source code. That is why in the future we intend to use additional static analysis techniques to discover more constraints. We also plan to investigate for our evaluation method the possibility of replacing the set of hand written scenarios by automatically generated scenarios using fuzzing techniques [START_REF] Neves | Using attack injection to discover new vulnerabilities[END_REF].

Fig. 1 .

 1 Fig. 1. Example of string format vulnerability and useful assertions

Fig. 2 .

 2 Fig. 2. C code sample that emphasises relations between variables

Fig. 4 .

 4 Fig. 4. Different cases of injections and assertions

Fig. 6 .

 6 Fig. 6. Distribution of alerts

Table 1 .

 1 Assertions generated

	00: void do_authentication(){		00: void do_authentication(){
	01:	int auth = 0;		01:	int auth = 0;
		...			...
	03:	if(!strcmp(pwd, ""))		03:	if(pwd[0] != '\0')
		/* for users with no password */			/* for users with no password */
	05:	else		05:	else
		/* do_authloop(); */			/* do_authloop(); */
	07:	while(auth != 1) {		07:	while(auth != 1) {
	08:	type = packet_read(data);		08:	type = packet_read(data);
	09:	switch (type) {		09:	switch (type) {
	10:	case SSH_CMSG_AUTH_PASSWORD:		10:	case SSH_CMSG_AUTH_PASSWORD:
	11.			11:	assert(pwd[0] != '\0');
	12:	auth = auth_password(pwd, data);	12:	auth = auth_password(pwd, data);
	13:	break;		13:	break;
	14:	...			...
	15:	}		15:	}
	16:	}		16:	}
	17:	do_authenticated(user);		17:	do_authenticated(user);
	18: }			18: }
		Fig. 3. Example inspired from OpenSSH
			OpenSSH DropbearSSH	ihttpd	fnord	ssmtp
		Number of lines	38000	11000	1043	2303	2976
		Number of assertions	291	91	145	41	240
		Computation time	6 hours 3 hours 45 minutes 1 minute 17 seconds 5 hours 22 minutes

  Experimentation protocol SIDAN alert Unexpected server exit Incorrect server output Strace alert

			Controller
	Random injection function				End of scenario
	Random variable	Injection	Synchronisation	End of process
	Random value				Time-out
	Scenarios	Execution		Process	System calls alerts	Logs
					SIDAN	Logs
					alerts
						Logs
					process outputs
	Fig. 5. Injection detected 74827	21574	61470	26970
	Detection rate	62.36%	18.13%	51.23%	22.48%

Table 2 .

 2 Injection results on Dropbear SSH

http://www.rennes.supelec.fr/ren/rd/ssir/outils/sidan/