Claire Lemaitre
email: claire.lemaitre@inria.fr

Liviu Ciortuz

Pierre Peterlongo
email: pierre.peterlongo@inria.fr

Mapping-Free and Assembly-Free Discovery of Inversion Breakpoints from Raw NGS Reads

Keywords: structural variant, NGS, reference-free, de Bruijn graph

We propose a formal model and an algorithm for detecting inversion breakpoints without a reference genome, directly from raw NGS data. This model is characterized by a fixed size topological pattern in the de Bruijn Graph. We describe precisely the possible sources of false positives and false negatives and we additionally propose a sequence-based filter giving a good trade-off between precision and recall of the method. We implemented these ideas in a prototype called TakeABreak. Applied on simulated inversions in genomes of various complexity (from E. coli to a human chromosome dataset), TakeABreak provided promising results with a low memory footprint and a small computational time.

Introduction

Structural variation is an important source of variations in genomes, that can be involved in phenotypic variations, inherited diseases, evolution and speciation. The extent of structural variations in populations has been only recently acknowledged, thanks mainly to next generation sequencing (NGS). In fact, by sequencing the genomes of several human individuals, one can find more DNA involved in structural variations than in single nucleotide polymorphism (SNP) [START_REF] Mills | Genomes Project: Mapping copy number variation by population-scale genome sequencing[END_REF]. However, due to the small size of the reads these variants are much more difficult to identify than SNPs. Most methods proposed so far rely on mapping the reads on a reference genome. The main approach calls structural variant breakpoints when mapped read pairs show discordant mappings with respect to expected insert-size and orientation of the reads [START_REF] Medvedev | Computational methods for discovering structural variation with next-generation sequencing[END_REF]. Due mainly to repetitions in complex genomes and mapping errors, these methods suffer from high false positive rates and a small overlap between predictions obtained by different methods [START_REF] Alkan | Genome structural variation discovery and genotyping[END_REF]. Noteworthy, copy number variations seem to have focussed most attention and efforts, whereas balanced structural variants such as inversions have been less investigated [START_REF] Mills | Genomes Project: Mapping copy number variation by population-scale genome sequencing[END_REF], suggesting that the latter are even more difficult to detect in short read data.

All these approaches rely on a reference genome and on a first mapping step. This is a strong limitation when dealing with organisms with no available reference genome or one of poor quality or too distantly related. On the other hand, one can also perform full de novo assembly of re-sequenced genomes and compare the resulting assemblies [START_REF] Li | Structural variation in two human genomes mapped at single-nucleotide resolution by whole genome de novo assembly[END_REF], however de novo assembly remains a difficult and resource intensive task and this could be reduced by targeting directly inversion variants. The problem we address is therefore: can we identify inversion signatures directly in raw NGS reads without the need of any reference genome nor full assembly of the reads? Several methods have been developed recently for calling biological events of interest directly from raw unassembled reads, by targeting specific patterns in assembly graphs. Some of them are dedicated to detect SNPs or small indels [START_REF] Peterlongo | Identifying sNPs without a reference genome by comparing raw reads[END_REF][START_REF] Nordström | Mutation identification by direct comparison of whole-genome sequencing data from mutant and wild-type individuals using k-mers[END_REF][START_REF] Uricaru | discoSnp Software[END_REF] or alternative slicing events in RNA-seq data [START_REF] Sacomoto | Kissplice: de-novo calling alternative splicing events from rna-seq data[END_REF].

Cortex var [START_REF] Iqbal | De novo assembly and genotyping of variants using colored de bruijn graphs[END_REF] claims to detect any variant generating a bubble pattern, but does not target specifically inversions or other balanced structural variants.

The main contribution of this paper is an analysis and a formal modeling of topological patterns generated by inversions in the de Bruijn Graph. Additionally, we propose an algorithm detecting such inversion patterns. This algorithm was implemented in a tool called TakeABreak that was used as a proof of concept and that can be downloaded from http://colibread.inria.fr/TakeABreak/. Applying this tool on simulated datasets showed that i) the described model detects with high recall and precision inversion breakpoints ii) approximate repeats present in complex genomes only slightly decrease performances iii) time and memory are very limited.

Inversion Pattern in the de Bruijn Graph

Preliminaries

Given a sequence s on the DNA alphabet Σ = {A, C, G, T }, we use the concept of k-mers that are words of length k in s. We denote by ←s the reverse-complement of sequence s, for instance with s = T T GC, ←s = GCAA.

de Bruijn Graph. The approach we propose is based on the use of a de Bruijn Graph. Given a set of sequences such as reads in the assembly framework, a de Bruijn Graph is a directed graph where the set of vertices corresponds to the k-mers from the sequences, and a directed edge connects a source k-mer a to a target k-mer b if the k-1 suffix of a is equal to the k-1 prefix of b. Usually, in the genome assembly framework [START_REF] Zerbino | Velvet: algorithms for de novo short read assembly using de bruijn graphs[END_REF], a de Bruijn Graph node stores explicitly a kmer and implicitly its reverse complement. Thus there are two ways of traversing a node: either reading the explicit k-mer or reading the implicit one; we denote this notion by the state of the node: explicit or implicit. In this context, each edge is labeled by the states of its source and target nodes. In the following n → ω denotes the node storing explicitly or implicitly ω, in the state such that reading n → ω provides the k-mer ω. Respectively, n ← ω denotes the same node in the state such that reading n ← ω provides the k-mer ←ω . Given two nodes n → start and n → stop , we say that a path of length l exists from node n → start to node n → stop , iif node n → stop can be reached using l nodes from node n → start and for any traversed node, it should be entered and left in the same state (i.e. explicit or implicit). Let k-path denote a path of length k. ←b and u = ←v . Figure 1 proposes a graphical representation of an inversion. We call the breakpoints of the inversion, the junctions between the inverted segment and the non-inverted parts. Such a rearrangement generates therefore two breakpoints in each sequence.

Inversion Pattern

An inversion, such as shown in Figure 1, generates a particular motif in the de Bruijn Graph. The only differences in terms of k-mers between both sequences, with and without the inversion, involve the breakpoints of the inversion: only the k -1 k-mers spanning each breakpoints differentiate the two sequences. The breakpoints at the left of the inverted segments are then characterized by a fork in the de Bruijn Graph, which is defined by a common node n → a that branches to two distinct k-paths that end respectively in n → u and n ← v . Similarly, the other two breakpoints (at the right) are characterized by two k-paths starting from n ← u and n → v that join in n → b . These two forks, being connected by two common nodes (corresponding to the k-mers u and v respectively, and their reverse complements), lead to a particular motif in the de Bruijn Graph, that we call the inversion pattern, as exemplified in Figure 2.

It is important to note that the definition of the inversion pattern imposes conditions on the four k-mers a, u, v, b. First, a = ←b and u = ←v for the two distinct forks to exist. Second the node n → a must be branching, that is the first nucleotide of u must be different from the first nucleotide of ←v .

One major advantage of this motif is that it can be traversed by 4 k-paths in the de Bruijn Graph:

one from n → a to n → u ; one from n ← u to n → b , one from n ← b to n ← v ; one from n → v to n ← a .
Being composed of only fixed length paths, finding the presence of such motif in a de Bruijn Graph is rapid and rather simple.

Notice that this motif presents some drawbacks. First, it detects the presence of inversion breakpoints but it does not provide the inversion itself. As second drawback, the motif is perfectly symmetrical: starting from node n ← b , or n ← u or n → v leads to the discovery of the same inversion. As presented Section 3.2, we propose a way to output only once each inversion breakpoints. Finally, such a motif may witness approximate repeats instead of inversions (see Section 3.4).

Algorithm for Inversion Pattern Detection

Main Algorithm

This section describes an algorithm for efficient detection of the inversion pattern from an already constructed de Bruijn Graph.

A "naive" algorithm for detecting the inversion pattern would be to check for each possible starting k-mer a a k-path from n → a to n → u , then from n ← u to n → b , then from n ← b to n ← v and then from n → v to n ← α and finally checking that a = α. This approach would lead to the construction of 4k-paths from n → a leading to a combinatorial explosion in complex genomes.

We propose an algorithm whose longest walked paths are of length 2k, then strongly limiting the search space. The main idea is to start from any branching node (a node having more than one outgoing edge) n → a , to detect all nodes reachable by a k-path, storing them in several sets N α depending on the first letter α of these nodes. The second main step is then to detect any node n

→ b ( ← - b = a) such that there exist a k-path from n ← u to n → b and a k-path from n ← b to n ← v , with n ← u ∈ N α and n ← v ∈ N β and α = β.
In such case the pair of sequences au and vb is output. Algorithm 1 proposes a high level presentation of our algorithm.

Canonical Representation of Occurrences

The inversion pattern presents some symmetries. In most cases (see Section 3.3), the inversion pattern generated by an inversion will be detected by our algorithm as four distinct occurrences each starting from one of the four main nodes:

n → a , n ← u , n ← b and n → v .
The output of the algorithm 1 is a pair of words au and vb Output (au, vb)

Algorithm 1. Main algorithm to detect the inversion pattern depending both on the starting node n → a and the order of detection between n → u and n ← v . To avoid outputting several times the same inversion, we define its canonical representation as the smallest 2-words output in lexicographical order among the eight possible rearrangements: (au, vb),

(a ← -v , ← - u b), ( ← -u ← -a , ← - b ← -v ), ( ← -u b, a ← -v ), (vb, au), (v ← -a , ← - b u), ( ← - b ← -v , ← -u ← -a ), ( ← - b u, v ← -a ).
Only the canonical representation is reported and only once.

Presence of Small Inverted Repeats at the Breakpoints

If an inversion contains an inverted repeat of size larger or equal to k -1 at its breakpoints, this inversion will not generate the inversion pattern since it does not generate new k-mers nor new paths in the de Bruijn Graph with respect to the non inverted sequence. This is the case for instance if a = ←b or u = ←v . In the case of an inverted repeat whose length is smaller than k -1, such inversion still generates the inversion pattern, however the latter is not be fully symmetrical. Suppose there is an inverted repeat of size x < k -1 at the breakpoints or overlapping the breakpoints. As the first node n → a must be branching, it imposes that the repeated sequence is included in k-mer a and considered outside the inverted segment (note that even with the full sequences at hand, we can not decide if the inversion includes the repetition entirely, partially or not at all). The suffix of size x of a is then equal to the prefix of size x of ←b . It implies also that there are no more k -1 distinct k-mers at each breakpoint that differentiate the two sequences, but k -1x k-mers. Therefore the two forks of the inversion pattern, represented in Figure 2, are shortened. In this case, the nodes n ← u and n → v reached after k-paths are not necessarily branching and can not constitute starting k-mers in other occurrences of the inversion pattern. Instead k-mers at the end of (kx)-paths in the fork constitute the other starting k-mers.

In fact, such an inversion will still be detected as 4 occurrences but the sets of k-mers a, u, v and b will be different depending on the starting k-mer. Starting from inside (n ← u or n → v ) or outside (n → a or n ← b ) the inverted segment I will generate two distinct sets of 2k words overlapping on 2kx characters. To avoid duplicating once again artificially the number of occurrences, the output of the algorithm truncates the k-mers u and ←v such that all starting k-mers give the same sets of words (here of size 2k -x) and a unique canonical representative can be computed for each of the four occurrences (Figure 3).

Distinguishing Inversions from Approximate Repeats

Some approximate repeats may generate the inversion pattern in the de Bruijn Graph and are thus a source of false positives. Consider for instance that a given sequence au has at least four approximate copies in the sequence, such that au, au , a u and a u with u u (at least the first letter is different) and a a (at least one substitution or indel anywhere in a). In this situation, without loss of generality, calling ←b = a and ←v = u , the four paths au, vb(= ← -a u ), a ←v (= au ), and ←u b(= ←a u) exist and mimics the inversion pattern. More generally, high similarity between a and ←b and between u and ←v is characteristic of an approximate repeat.

In order to distinguish inversions from false positives due to approximate repeats, we filter out occurrences of the inversion model where a and ←b and where u and ←v have a Longest Common Subsequence (LCS) size higher than a given threshold. As an optimization, we try to detect earlier cases where a and ←b are too similar during the k-path search from n ← u to n → b . During this step, we forbid paths that go back on the previous path towards first node n → a , since the longer we take the former path, the more similar will be k-mers a and ←b . However, to permit the detection of inversions with small inverted repeats at the breakpoints, we tolerate to go back on the former path for a given maximum number of nodes (this parameter is usually fixed to 8).

Additionally, it is well known that high copy number repeats with approximate copies are an important source of complexity generating highly branching subparts in the de Bruijn Graph. Searching for inversions in such complex part of the graph presents two main drawbacks. First, as previously mentioned, it is a source of false positives, and second, it generates a possible huge number of kpaths whose enumeration can be highly time consuming. To overcome these two drawbacks we stop the inversion pattern detection from a node n a as soon as the product of the cardinality of the two largest sets N α is bigger than a limit (called LCT for Local Complexity Threshold ). This product is a lower approximation of the minimal number of couples of k-paths that are to be enumerated from the starting n a . Similarly, we apply the same strategy once a set of nodes B (see Algorithm 1 line 9) is detected from a node n → u : if the cardinality of B times the cardinality of the largest set N α is larger than LCT , then the exploration from node n → u stops. This last product reflects another lower bound of the number of paths to be checked. Note that this approach highly limits both false positives and computational time, while having a limited impact on recall, as shown in results Section 4.2.

TakeABreak Implementation

We implemented the proposed algorithm in a prototype called TakeABreak. It takes as input one or several sets of sequences in fasta or fastq format. Its main parameters are the k-mer size k; max sim ∈ [0, 100] the maximal similarity authorized between a and ←b and between u and ←v , expressed as a percentage of k-mer size; and LCT : the Local Complexity Threshold (see Section 3.4). Prior to the inversion pattern detection phase, the de Bruijn Graph is constructed using the Minia data structure [START_REF] Chikhi | Space-efficient and exact de bruijn graph representation based on a bloom filter[END_REF][START_REF] Salikhov | Using Cascading Bloom Filters to Improve the Memory Usage for de Brujin Graphs[END_REF]. This graph is constructed using only k-mers having at least 3 occurrences in order to discard sequencing errors. This is a very common parameter used for de Bruijn Graph-based assembly. The second phase implements algorithm 1. The output is a fasta file containing, for each detected inversion, its breakpoint sequences. These are the 2k -2 (or 2kx -2 in the case of an inverted repetition of size x) words centered on the canonical representation (au, vb). By removing the two extreme nucleotides, it ensures that the output paths are made of the k-mers that overlap the breakpoints and that must be specific to each sequence.

TakeABreak was implemented in C++ with the GATB library [START_REF] Drezen | The Genome Assembly and Analysis Tool Box[END_REF], providing notably the Minia data structure, and it can be downloaded from http://colibread.inria.fr/TakeABreak/.

Results

To evaluate the ability of TakeABreak to detect inversions in reads, we generated artificial read datasets. First, non-overlapping inversions of varying sizes were simulated in a copy of a real genome. Then we simulated the sequencing processing on both genomes, the original one and the one with artificial inversions. Finally both read sets were given as input to TakeABreak. To classify the results of TakeABreak as true positive or false positive, we first generated for each simulated inversion its canonical representation of breakpoints such as described in sections 3.2 and 3.3 and then called a prediction of TakeABreak as true positive if it is exactly present in this set of true breakpoints. Finally, recall and precision were computed as follows: recall as the number of true positives over the number of simulated inversions, and precision as the number of true positives over the number of predictions.

In more details, inversions were simulated as follows. Each inversion was put sequentially. For each inversion, its first breakpoint is chosen uniformly along the sequence, then its size is sampled uniformly in a given interval (here [k -1000]), finally if it does not overlap and is sufficiently far from a formerly placed inversion (the min distance was fixed to k nucleotides) the inversion is kept and its sequence is reversed-complemented. To simulate reads, 100 bp reads are sampled uniformly along the genome, sequencing errors are put also uniformly with 1 % rate, the depth of coverage was fixed to 40x for each genome.

Results on a Bacterial Genome

TakeABreak was first evaluated on a simple and small dataset based on the bacterial E. coli K12 genome, in which 1000 random inversions were simulated. TakeABreak was applied on this simulated dataset with default parameters (k = 31, max sim = 80%, LCT = 100). On this simple dataset, TakeABreak proved to be highly efficient to detect inversion breakpoints, since it predicted the 1000 true positive inversions, leading to a 100% recall for 100% precision (see Table 1). Cortex var bubble caller [START_REF] Iqbal | De novo assembly and genotyping of variants using colored de bruijn graphs[END_REF] was run on the same data and failed to detect any of the simulated inversions.

Results on More Complex Genomes

Bacterial genomes are small and contain few repeats, leading to rather simple de Bruijn Graph and few false positives of the inversion pattern. To evaluate TakeABreak on more complex genomes, we simulated inversions in eukaryotic genomes and chromosomes, first in the full C. elegans genome (∼ 100 Mbp) and second in human chromosome 22 (∼ 35 Mbp without N bases). As expected (see Section 3.4), precision and recall decrease when the repeat content of the genome increases, as shown in Table 1. However, this effect is greatly limited by the use of filtering parameters max sim and LCT , since relaxing these parameters leads to millions of false positives (see Table 1).

Note that these parameters have to be fixed carefully as they can also affect the recall, as shown in Figure 4 where precision and recall results are represented for varying values of max sim and LCT . This figure shows that both parameters are useful to decrease the false positive rate and that the proposed default parameters offer a good trade-off between precision and recall.

Time and Memory Performances

These tests were performed with 2.3 GHz Intel Core i7 processors, with 8GB RAM. Table 2 shows time and memory performances of the prototype TakeA-Break for the different datasets. Time and memory increase with the complexity of the datasets. Even if the human chromosome dataset is smaller than the C. elegans one, the computational time is much larger for human. This shows that the complexity of the graph is not solely linked to the size of the genome, but also to its repeat content, with human chromosome 22 high copy number repeats generating sub-parts of the graph with high density of branching nodes and imbricated patterns of inversions.

Nevertheless, as presented Table 2, TakeABreak scales up to complex and large datasets. The highest memory consumption is reached during the de Bruijn Graph construction and is limited to 1GB, allowing TakeABreak to be executed on a standard desktop (note that the full human genome would need 6GB of memory [START_REF] Salikhov | Using Cascading Bloom Filters to Improve the Memory Usage for de Brujin Graphs[END_REF]). The graph construction time is limited to at most 20 minutes for the most complex dataset we used. The time needed for enumerating all inversion patterns is sensitive to genome complexity (from 1 second for E. coli to one hour and a half for human chromosome 22) and still remains acceptable. Moreover, in addition to dramatically improving the precision (see Section 4.2), we can notice that the default filters highly reduce the computational time (e.g. from 7h40 without filters to 1h30 with filters on the human dataset).

Discussion and Conclusion

In this work, we formalized for the first time the topological pattern generated by the inversion of a DNA segment in the de Bruijn Graph representing both sequences, with and without the inversion. We also proposed a first analysis of what kind of variant or sequence feature can or can not generate this pattern. The pattern involves only the 2k sequences around the breakpoints of the inversion (k being the k-mer size of the de Bruijn Graph). Therefore the size of the inversion does not limit the existence of the pattern as long as it is greater than k. The pattern is based on four k-mers at each side of the breakpoints that must be identical between both sequences with and without the inversion. As a consequence, the breakpoint regions must not contain any substitution or indel at distance less than k from both breakpoints, that is as if the inversion was generated by perfect blunt-ended double strand breaks. Finally, another feature that can prevent an inversion from generating this pattern is the presence of an inverted repeat of size ≥ k -1 at each breakpoints since all breakpoint sequences will follow the same paths in the de Bruijn Graph.

On the other hand, we showed that the pattern can be generated by other sequence features than inversions. First, some approximate repeats with appropriate combinations of differences can easily generate this pattern, these are considered as false positive or noise since they do not differentiate the compared genomes. If in small bacterial genomes, this situation is quite rare, our tests show that in more complex genomes this can dramatically increases the number of false positive calls, explaining why we added a sequence-based filter to this topology-based pattern. Indeed, with high copy number repeats, such as transposable elements in eukaryotic genomes, such combinations of at least two differences in repeats of size 2k is very likely to happen. Another variant that can generate the inversion pattern is the reciprocal translocation, since it has also two breakpoints per sequence (with and without the translocation) with the same combinations of four k-mers. We consider this as another advantage of this pattern, because, in this case, this is also a structural variant that can differentiates genomes and has therefore a potential biological interest.

In this work, we also proposed and implemented an efficient algorithm to enumerate all inversion patterns in a de Bruijn Graph, together with powerful filtering strategies to avoid false positives due to approximate repeats. The tests we performed on simulated data prove that this approach enables to recover almost all simulated inversions quite rapidly. The power of this pattern lies mainly in its fixed size. Contrary to structural variants with only one breakpoint, such as insertions and deletions, it is not necessary to traverse in the graph the full inverted segment to detect the presence of the inversion. In fact, insertions and deletions generate bubble patterns that can only be detected by traversing the full inserted or deleted sequence [START_REF] Iqbal | De novo assembly and genotyping of variants using colored de bruijn graphs[END_REF][START_REF] Sacomoto | Kissplice: de-novo calling alternative splicing events from rna-seq data[END_REF], this strongly limits the size of detectable events (at least in complex genomes) and increases the computational time. Inversions too could be detected as bubbles but Cortex var did not detect them, even the smallest ones, probably because it requires bubbles not to contain any branching node while such nodes are inherent of inversion patterns, as shown in this paper.

The tests and simulations we performed were meant to demonstrate the validity of our pattern and of our algorithm, we are aware that they can still be improved to better fit actual genome re-sequencing data. Indeed, only inversions were simulated without any other polymorphism that could impact the breakpoints. Inversions were put following a uniform distribution, whereas rearrangement distribution is likely not random and some rearrangements can be linked for instance to repeated sequences. Finally, only perfect blunt-ended breakpoints were simulated which may not reflect all molecular mechanisms of such events (for instance, non-homologous end joining is known to generate small indels at the very breakpoint). For all these reasons, recall values we obtained are likely to be over-estimated with respect to real inversions. However, our promising results on such simulated inversions open the way to further improvements of the model.

First, the model could largely be improved by additionally including SNP or small indel detection models such as [START_REF] Uricaru | discoSnp Software[END_REF]. Thus both SNP and inversion detection would not suffer from each other. This would improve recall for events that lie close to each other and could be used as preliminary step of the assembly process. Second, the breakpoint detection algorithm could be coupled with a third party local assembly or gap-filling tool, such as MindTheGap [START_REF] Lemaitre | MindTheGap Software[END_REF], to get the sequence of the inverted segment and not only its breakpoints. Finally, other biological variants can benefit from this approach. As already mentioned, reciprocal translocations can be detected by the proposed model as is. Additionally, the model could be extended to the detection of other rearrangements that have more than two breakpoints, such as transpositions that generate a three-fork model, thus showing high similarity with the model proposed in this paper. project and by the ANR (French National Research Agency), ANR-12-BS02-0008 Colib'read project and ANR-12-EMMA-0019-01 GATB project.

Fig. 1 .

 1 Fig. 1. Sequences aIb and a ← -I b, showing the four particular k-mers a, u, v and b at the breakpoints

Fig. 2 .

 2 Fig. 2. Schematic example of the inversion pattern generated by sequences aIb (the blue path) and a ← -I b (the red path) in a de Bruijn Graph with k = 4. Nodes are represented as two-stage boxes, with the upper part in black showing the explicit kmer and the lower part, in grey, the implicit one. DNA k-mers are not represented, instead the node content shows proportion of full or junction of the four main k-mers a, u, v, b and their reverse complements. For sake of simplicity and without loss of generality, we consider that all k-mers of au, vb, a ←v and ←u b are explicitly stored. The state of a node traversed by edges entering and leaving its upper (resp. lower) part is explicit (resp. implicit). The green paths represent the paths enumerated by TakeABreak algorithm. The dashed green path is only checked, once the nodes nv and n b are found.

Fig. 3 .

 3 Fig. 3. Example of an inversion with small inverted repeats (red arrows) at the breakpoints. Breakpoint sequences au, vb (resp. a u , v b ) are obtained starting from nodes n → a or n ← b (resp. n ← u or n → v ). The unique canonical representative is represented by the two grey bottom lines.

Fig. 4 .

 4 Fig. 4. Effect of the filtering parameters, max sim (a) and LCT (b), on precision and recall values for the C. elegans (open symbols) and human chromosome 22 (solid symbols) datasets. Vertical dashed lines represent the default parameters.

Table 1 .

 1 Precision and recall results for TakeABreak on simulated datasets. The first part of the table presents results obtained with default parameters (k = 31, max sim = 80%, LCT = 100), the second part shows the decrease of precision when relaxing filtering parameters (k = 31, max sim = 100, LCT = 10000). # FP indicates the amounts of false positives.

	Recall (%) Precision (%) # FP

Table 2 .

 2 Time and memory performances of TakeABreak on simulated datasets with default parameters. For each dataset we indicated the number of reads and the total number of nucleotides it contains. Time values given in parenthesis are those obtained while relaxing the filter parameters (bottom part of Table1).

		Time (s)	Memory
		Graph	Inversion	Graph	Inversion
		construction	detection	construction	detection
	E. coli genome (3.7M reads 370 Mbp)	24	1	1GB	3MB
	C. elegans genome (80M reads, 8 Gbp)	78	935 (7408)	1GB	53MB
	Human chromosome 22 (28M reads 2.8 Gbp)	1205	5412 (27554)	1GB	153MB

Acknowledgments. The authors warmly thank Erwan Drezen and Guillaume Rizk for implementation support and Marie-France Sagot for interesting discussions. This work was supported by the Région Bretagne SAD-MIRAGE


Romaric Ludinard

Eric Totel

Frédéric Tronel

Vincent Nicomette

Mohamed Kaâniche

Eric Alata

Rim Akrout

Yann Bachy

Éric Totel

Éric Alata

An Invariant-based Approach for Detecting Attacks against Data in Web Applications

Keywords: intrusion detection, invariant discovery, invariant checking, and web applications

come   L'archive ouverte pluridisciplinaire

An Invariant-based Approach for Detecting Attacks against Data in Web Applications

Nowadays there is an important trend to transform traditional applications into their equivalent online counterpart, making possible for end users to remotely interact with their information systems through their Web browser. Such web-based applications offer all functionalities required by the end-user (e.g., webmail, online calendars, e-business, e-banking…). This paradigm shift did not lead to a significant change of the methodology and processes employed during the application development. Hence, the design faults that are commonly encountered with traditional applications are still present in these new web-based applications. As illustrated by recent statistics (see e.g., (IBM, 2012), these applications still exhibit a high number of vulnerabilities. They have become one of the preferred targets for the attackers. The consequences of these attacks are at least as critical as they were with traditional applications. Worse, the corresponding vulnerabilities can now be remotely exploited.

Several mechanisms have been developed to protect web applications against potential attacks. These mechanisms can be used at the network level (such as applicative firewalls), and at application level (such as input sanitization techniques). However such prevention mechanisms remain largely insufficient, as they do not take into account the semantic of the applications they are supposed to protect, thus providing a rather low protection. Hence, it is important to propose mechanisms that could more efficiently detect attacks affecting the integrity of the application state.

In this paper, we propose an approach to anomaly based intrusion detection at the application level that focuses on violations of the application state. This approach is based on the automatic generation of invariants that are discovered during a learning phase and verified during the execution of the application. The paper extends the results presented in [START_REF] Ludinard | Detecting Attacks against Data in Web Applications[END_REF] by providing more details about the implementation of the approach and the generation of the invariants. First Section State of the Art presents previous work about intrusion detection that can be applied in the context of web applications. Section Context and Case Study presents the context and a case study of our work. In Section Invariant Constraints in an Application, a typical example illustrates the ideas we are relying on. Then, a general overview our approach is outlined in Section Invariant based Detection Model), together with a discussion of how it can be applied to web applications (Section Ruby On Rails Implementation). The last part of the paper (Section IDS Assessment) shows how the intrusion detection mechanisms have been assessed, in order to demonstrate that they accurately detect the types of attacks we focus on.

State of the Art

Most work in the context of web attack detection focuses on abnormal network packets [START_REF] Robertson | Using Generalization and Characterization Techniques in the Anomaly-based Detection of Web Attacks[END_REF] or requests [START_REF] Vigna | A Stateful Intrusion Detection System for World-Wide Web Servers[END_REF] and do not take into account the state of the web application itself. We believe that application level mechanisms can help improving the intrusion 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.

Three types of approaches can be distinguished for detecting intrusions at application level: the first approach focuses on the correctness of the Control Flow Graph of the program such as [START_REF] Abadi | Control-flow integrity[END_REF] and [START_REF] Kiriansky | Secure execution via program shepherding[END_REF] and consists in verifying that the actions in the program are executed in a correct order. This work does not permit to detect attacks on data. The second approach focuses on the correctness of the data manipulations during program execution such as in [START_REF] Akritidis | Preventing Memory Error Exploits with WIT[END_REF] or in [START_REF] Castro | Securing software by enforcing data-flow integrity[END_REF]. In this case, a data-flow graph is computed prior to the execution that 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 process data flow that really occurs. If a vulnerability is exploited in the monitored program that corrupts some data, a deviation from the data-flow graph will be detected the next time this data is read. A third approach, as defined by [START_REF] Sarrouy | Application data consistency checking for anomaly based intrusion detection[END_REF], consists in checking the correctness of the data used by the program during its execution, rather than verifying the consistency of the data flow. This approach permits to detect a different kind of attacks on data compared to the data-flow approach (such as the use of incorrect values in legitimate variables). In [START_REF] Sarrouy | Application data consistency checking for anomaly based intrusion detection[END_REF] the application normal profile is modelled as a set of constraints on the data used by the application. This model is built during a two-fold learning phase. First the data items used by the application are logged. Then, a set of invariants is generated by a dedicated tool stemming from the testing field called Daikon [START_REF] Ernst | The Daikon system for dynamic detection of likely invariants[END_REF]. These invariants are then checked at run-time to perform the detection.

All these approaches are relevant in the context of both traditional and web applications. For instance, similar approaches have already been investigated by [START_REF] Cova | Swaddler: An Approach for the Anomaly-based Detection of State Violations in Web Applications[END_REF] in the context of PHP applications. In this work the authors focus both on the web application control flow and on the correctness of the data items used by the program. [START_REF] Felmetsger | Toward Automated Detection of Logic Vulnerabilities in Web Applications[END_REF] is an extension of this work to JSP. The authors propose to build the application normal behaviour during a learning phase where the invariant behaviour of the application is modelled using the Daikon tool. Then a model checking approach is used to verify if the invariants can be violated by the application, leading thus to the discovery of vulnerabilities in the application. This interesting approach suffers from several limitations, such as the discovery of invariants restricted to only inputs and outputs of the functions executed by a servlet, and the lack of consideration of temporal relationships between the variables used by the program.

In our work, we focus on the correctness of data only, but at a finer granularity (i.e., at the instruction execution level) like in [START_REF] Sarrouy | Application data consistency checking for anomaly based intrusion detection[END_REF], and we study the evolution of variables with respect to time so as to discover invariants on these variables. Compared to Swaddler developed by [START_REF] Cova | Swaddler: An Approach for the Anomaly-based Detection of State Violations in Web Applications[END_REF], we additionally introduce the notion of tainted data [START_REF] Cavallaro | Anomalous Taint Detection: Secure Systems Laboratory[END_REF] to reduce the set of variables we are checking.

In order to demonstrate the feasibility of our approach at application level, we consider the example of applications implemented with the Ruby on Rails framework. This framework is receiving increasing interest by the software development community. In the next section, we present the main concepts of Ruby on Rails that are needed to explain our intrusion detection approach, and we present the application example used as a case study in our work.

Compared to previous work, the approach proposed in this paper presents innovative aspects:

-In all the work dedicated to intrusion detection that uses Daikon, the authors use the available Daikon front-ends or extend them. Thus, they obtain invariants on inputs or outputs of the methods or functions called. In our approach, we observe the execution of all single instructions in the interpreter and we obtain invariants on all the variables manipulated by all instructions executed by the interpreter. As a result of the previous point, much more invariants can be found compared to other approaches such as [START_REF] Cova | Swaddler: An Approach for the Anomaly-based Detection of State Violations in Web Applications[END_REF], [START_REF] Cavallaro | Anomalous Taint Detection: Secure Systems Laboratory[END_REF] and thus our approach should obtain a better coverage for the detection of attacks.

-Our approach uses Daikon in a non-conventional way to extract from the execution traces temporal relationships on the program variables, which is a completely new functionality for a work based on Daikon.

-The implementation we propose does not imply the modification of the interpreter, compared to other approaches, providing thus an elegant implementation of invariant discovery and checking. Ruby on Rails (http://rubyonrails.org/) (RoR) is a Model-View-Controller framework that eases the way to design web applications. The choice of RoR as a case study was dictated by the fact that it provides introspection mechanisms that make it possible to observe the behaviour of the application without modifying the Ruby interpreter. A typical RoR application is composed of several controllers (like shown by Figure 1). A request to an application determines which Rails controller must be used, and which action of this controller must be called. When one of these controllers is called, it interacts with the model to access the data usually stored into a database. Using this data, it generates a view that is returned to the user as result of its request.

Context and Case Study

Since all the requests sent to the application are processed by a controller (more precisely by an action in a given controller), we chose to apply our detection model at the controller level.

In this work we have applied our approach to an e-commerce application designed by Kereval (www.kereval.com) in the context of the ANR (French National Research Agency) funded project DALI (Design and Assessment of application Level Intrusion detection systems). This application called Insecure intentionally exhibits the common vulnerabilities of a web application. More precisely, it is vulnerable to the following attacks: SQL injection, cross-site scripting, request parameter modification and cookie manipulation. This e-commerce application has been designed without any knowledge of the intrusion detection mechanisms that have been subsequently designed to protect it. This implies that it was not developed with the objective to emphasize the accuracy of our approach.

Invariant Constraints in an Application

This section shows on a simple example drawn from the Insecure application how its normal behaviour can be characterized using invariants on variables, and how an attack can violate at run-time one or more such invariants. We claim that attacks that violate the application state integrity can be detected by checking invariants at run-time. One can notice that the user's login and password are passed as parameters to the action (and stored in the params hashtable variable). These parameters are in turn used by a method called User.authenticate. This method performs a request to the database (see Figure 3) to retrieve the actual user corresponding to these parameters. The normal behaviour of this method consists in returning a user object stored in the session whose attribute login If an attacker performs an SQL injection by setting '' 'OR '1'='1" as user login or password, he will be authenticated as the first user in the database which usually corresponds to the administrator. As a result, the previously mentioned invariant would be violated since session [:user].login != params [:user][:login]. This example illustrates a rather simple kind of invariants, in that sense that it links the output produced by a method call with its inputs. This type of invariants is well known and may even be discovered by static analysis tools (Karr). We claim that other types of relationships can be found and should be investigated. In the approaches based on Daikon such as [START_REF] Felmetsger | Toward Automated Detection of Logic Vulnerabilities in Web Applications[END_REF] no temporal relationships can be found between successive requests. The authors even claim that such relationships do not exist unless the programmer uses global storage variables such as session variables. In fact, bad programming practice can produce information flows from a request to another, for example by using page parameters. This is illustrated by the figures 4 and 5 that show two actions of the Order controller that are successively called when a client orders items from the e-commerce application. The first action is the new action that is in charge of presenting a summary of its order to the client. The client must validate all the needed information in the form (a valid postal address, a valid credit card number, etc.). Once the client has validated this form, the second action (create action) is triggered. The amount (price) of this order is transmitted as a parameter of the action. Thus an invariant can be deduced by observing the normal behaviour of the application. Namely, the variable param[:amount] in the create action must carry the same value as the variable @amount got in the new action. A possible attack against the application could consist in changing the amount parameter of the second request (using a plugin such as TamperData within the client navigator). However, if the previous invariant had been checked at execution, this attack would have been detected. The consideration of this particular kind of invariants is a major contribution of this paper. As far as we know RRABIDS is the first tool to propose this kind of invariants. format.html{redirect_to[:user, @order] } format.xml{render :xml=>@order,:status=>:created,:location=>@order } else @addresses=Address.all(:conditions=>{:user_id=>@user.id,:active => true}) format.html{render :action=>"new" } format.xml{render :xml=>@order.errors,:status => :unprocessable_entity} end end end ... end

Figure 5: Action called after order validation

In theory, this should be the role of the programmer to define relations between variables and check them at run-time. But in practice, very few programmers perform such checks unless they are forced to. Our work consists in automatically building such relationships and instrumenting the source code to insert such checks.

Invariant based Detection Model

Our work builds on the approach proposed by Sarrouy [START_REF] Sarrouy | Application data consistency checking for anomaly based intrusion detection[END_REF] which considered C applications. It is based on the dynamic discovery of invariants on traces that are generated during the execution of the program. However, compared to [START_REF] Sarrouy | Application data consistency checking for anomaly based intrusion detection[END_REF], we not only show that the behaviour of the program can be modelled as invariants, but we demonstrate that these invariants can be used at execution time to detect attacks. Three types of invariants are considered to describe: 1) relations between variables at a given execution point; 2) relations between the different values held by a given variable at different points of execution; and 3) relations between different variables at different points of execution.

Clearly, execution points play a central role in these objectives. In this paper, we define an execution point p to be a triple that consists of (i) the value of the program counter (pc), (ii) the state of the memory (mem) associated with the executed program (stack, heap, etc) and (iii) the logical time when this execution point occurs: p=(pc,mem,t).

Besides, it is also necessary to define precisely the notion of a program state. For a given execution and a given execution point, the state of a program consists in the set of all variables together with their associated values that are available at this point (global or local variables). Let σ be an execution of a program. We define S p,σ to be the state of this program at execution point p during execution σ. More precisely we model S p,σ as a partial function from the set of all possible variables to their definition sets. Hence S p,σ (v) is the value taken by variable v during execution σ at point p if v is defined or ⊥ otherwise (i.e., if v is not defined).

Since we want to discover invariants that are valid for all possible executions, we should not limit ourselves to a single given execution (such as σ). Instead we want to consider a set of possible executions that we denote Σ. For two executions σ 1 and σ 2 and two execution points p 1 ∈ σ 1 and p 2 ∈ σ 2 , we say that p 1 = (pc 1 , mem 1 , t 1 ) is equivalent to p 2 = (pc 2 , mem 2 , t 2 ) denoted p 1 ≡ p 2 , if and only if their program counters are equal, that is if pc 1 = pc 2 . Hence, two execution points are equivalent if they correspond to the same position in the program code (same program counter) without taking into account the state of their memories and their occurrence time. We introduce this equivalence relation to be consistent with the method used by Daikon to discover invariants. Indeed, Daikon analyzes traces that contain the values taken by possibly different variables at specific program counters. Hence, for Daikon two execution points are equivalent as long as they concern the same program counter. More precisely, three kinds of default program counters are defined by Daikon: (1) function entry points, (2) function exit points, and (3) any instruction within the body of a function. Note that in (Felmetsger et al.) only the first two are taken into account to compute invariants.

We finally introduce the notion of unified state for a given variable v over the set of considered executions Σ at a given program counter pc to be the function defined by:

€ S pc (v) = S p,σ (v) p∈σ |p=(pc, *, *)  σ ∈ Σ 
The semantic of a unified state is as follows: given a program counter pc, a unified state describes the values that can be associated with any accessible variable at this point of the program (that is for all equivalent execution points). From this definition we can deduce the set of all variables V pc at a given execution point

V pc = {v | S pc (v) ≠⊥} .
This set of variables contains all variables that can be used by Daikon to compute an invariant for a given program counter. Two observations can be raised about this model:

-First, it requires to save the values of all the variables each time the program counter evolves. Since this would require a very large amount of memory, we need to reduce this set to a finite and usable set of variables. This is discussed in Section Reducing the Set of Variables; -Second, automatically finding invariants on these variables requires to define what types of invariant constraints are actually needed; this set of constraints is potentially dependent on the model of attacks we intend to detect. This is the purpose of Section Classes of Invariants. To reduce the set of variables to be logged, we emphasize two considerations:

Reducing the Set of Variables

-First, all variables are not of interest for intrusion detection: an attacker needs to interact with the application to attack it, and thus he needs to modify its inputs. The data used by the application are altered by propagation of the modified inputs. As a consequence, the variables that are of interest are those that depend on the external inputs of the application. This set of variables can be defined formally using the notion of causal dependencies.

-Even if we restrict the set of variables to the variables that depend on external inputs, the application states to be saved are potentially still very large. Consequently, we will only keep in memory all the evolutions of the variables that occur within a given window of time. In this work, we restrict the time window to two consecutive actions performed by a single user identified by its session id (see Figure 6).

Using the notion of causal dependencies as defined in (d'Ausbourg, 1994), we say that a variable v 1 at time t 1 is causally dependent on a variable v 0 at time t 0 (noted (v 0 , t 0 ) → (v 1 , t 1 ) if there exists an information flow from (v 0 , t 0 ) to (v 1 , t 1 ).

The set of variables that influence a variable (v 0 , t 0 ) is called the causality cone and denoted cause(v 0 ,

t 0 ) = {(v i , t i ) | (v i , t i ) → * (v 0 , t 0 )} (where → * is the transitive closure of the relation → ).
This definition can be extended using the execution point we have previously defined: for a given variable v 0 at point p 0 = (pc 0 , mem 0 , t 0 ), with the variable

v 0 ∈ V pc 0 , cause(v 0 , p 0 ) = {(v, p) | (v, p) → * (v 0 , p 0 )} , with (v, p) → (v 0 , p 0 ) ⇔ (v, t) → (v 0 , t 0 )
We then define the notion of a tainted variable: informally a variable is tainted if it depends on the external inputs of the program (e.g., for a web application, user inputs, data coming from the database or external configuration files are external inputs). Formally, it means that the causality cone of this variable at a point p of the program contains an input of the program.

We can finally define the tainted function T p,σ of a variable v

T p,σ (v) = S p,σ (v) if v is tainted ⊥ otherwise # $ % & %
We thus obtain the set of values that can be taken by a tainted variable at a given program counter:

€ T pc (v) = T p,σ (v) p∈σ |p≡(pc, *, *)  σ ∈ Σ



As previously, we can define the set of tainted variables accessible at a given program counter. We denote this set as TV pc = {v | T pc (v) ≠⊥} .

Classes of Invariants

Once the set of variable values has been built during an observation phase, we need to automatically generate the set of invariant constraints on this set of values that characterize the normal behaviour of the application. We selected a number of different invariants that could be useful to detect an intrusion inside the application:

-a variable at a specific execution point is always constant; such invariant could be useful to detect the integrity violation of some variables, e.g., some constant values stored in the database to configure the application; this type of invariant consists in finding a relation for a given program counter on all values of v in T pc (v).

-a variable at a specific execution point holds values that belong to small set of possible values; this type of invariants could be useful to detect the corruption of some data provided by a user, e.g., a parameter which describes a number of possible options for the execution of a request; this type of invariant consists in finding a relation for a given program counter on all values of v in T pc (v).

-a variable at a specific execution point is always equal to another variable at another point; this type of invariant puts in relation some variable values that could be incorrectly modified during an attack, violating the state of the application. For example, the SQL injection described in Section Invariant Constraints in an Application implies such state violation. This type of invariant denotes a link between two sets of variables TV pc1 and TV pc2 where pc 1 and pc 2 are two program counters.

-an order relationship between two variables at different execution points (< or >); like the equality invariant, this relationship describes a normal state of a program that could be altered by an attack that modifies the value of an application variable. This type of invariant denotes a link between two sets of variables TV pc1 and TV pc2 where pc 1 and pc 2 are two program counters.

In practice, complex invariants could be computed on the set of tainted variables, e.g., some linear relations between variables. However, the experience proved us that this restricted class of invariants is sufficient to detect the commonly known web application attacks. Moreover, the implementation actually shows that these four types of invariants generate a considerable number of actual invariants even on a small application.

The invariants that we discover must not only be true for a given execution σ, but also for all the executions of Σ. In practice, the first executions lead to the discovery of a large set of invariants. Then, this set is reduced by invalidating them on further executions of Σ.

Ruby On Rails Implementation

We introduced in Section Context and Case Study the Ruby on Rails framework in the context of which we built our prototype. The choice of this framework was essentially dictated by the functionalities available in the Ruby language. In order to carry out an implementation of our model, we require: (1) to be able to intercept the execution of any instruction in the interpreter and ( 2) to be able to access the current execution context (i.e., the variables that are part of this context) at each execution point in order to log the state of the program. The Ruby on Rails framework and Ruby interpreter offer such functionalities without any modification of the Ruby interpreter

Observation Phase

In practice, Ruby on Rails allows to write plugins for a given application. We wrote a plugin called trace_vars to trace and log the state of the application at each executed instruction. This plugin, written in Ruby, is independent of the application source code. It is loaded when the application starts. In an application, all controller classes inherit from an ApplicationController class. Thus, the behaviour of the whole application can be impacted by modifying the behaviour of the ApplicationController class. The goal of the trace_vars plugin is to interrupt the execution of the interpreter at each instruction executed in a Controller that inherits from the ApplicationController class, and to log the application state in a trace. For that purpose, we use the set_trace_func function provided by the Ruby interpreter for debugging purposes. In our implementation, we use this function to intercept the execution of each instruction in the Ruby interpreter. At each instruction step we log the variables that are in the set of tainted variables previously defined.

Observing the Program State.

In order to obtain the set of variables that are available in the context of the program at a given execution point, we can use the metaprogramming functionalities of Ruby. In particular we can obtain all the instance variables and the local variables of the current executing ruby program by using the instructions eval(''instance_variables'', binding) and eval(''local_variables'', binding).

Tainted Variables Identification.

In order to know if a variable in the state of the application must be logged, we can build its causality cone as defined in Section Reducing the Set of Variables. This was the approach used in [START_REF] Sarrouy | Application data consistency checking for anomaly based intrusion detection[END_REF]. However, the Ruby interpreter offers an interesting functionality that is available for any object at execution: the notion of tainted variables. For each object, a method tainted? permits to know if an object is causally dependent on the external inputs of the application. This functionality allows knowing if a variable is in the set of tainted variables without having to explicitly compute the dependencies between variables. However, this functionality is only partly implemented in Ruby, as an object can have attributes that are tainted without the object itself being tainted. As a consequence, when we investigate if a variable is tainted, we have to inspect if any of its attributes is tainted or not. If one of its attributes is tainted, we log this attribute.

Naming Variables in the Log.

To generate invariants on different instances of variables that evolve in time, we must modify the common use of Daikon (the tool that computes the invariants on the traces) by providing it with the values of the variables at different points in time. To offer such functionality, we could introduce additional variables by adding the execution point of the executed instruction to the name of the logged variables. With this approach, we would have the naming rule: programCounter VariableName. However, we must not forget that we will have to instrument the application source code to check for the invariants. As a consequence, we must find a way to link the program counter with the line in the source code where the invariant must be checked. To fulfill this constraint, we define the programCounter as a couple (line, numberOfOccurrences) where line is the line executed in the source code, and numberOfOccurrences the number of times that this line has been executed. The naming rule of variables becomes: line_numberOfOccurrences_variableName. During the observation phase, the variables are stored in a file that is formatted according to the grammar that can be recognized by the Daikon tool. In practice, for each execution of an action, we log the variables in a file. Then, when enough observations have been made, all files are merged into a single Daikon file. This file is in turn used to compute the invariants. An example of a trace obtained is given in Figure 7. -var 19_2_@_session[user].@attributes comparability 0 ... 17_1_@_params["user"]["login"] "evette" 1 19_2_@_session["user"].@attributes["login"] "evette" 1 In order to be able to find invariants that link variables of two consecutive requests, we need to keep in memory a window of two request executions. When we log the variables for a given action execution, we actually log the previous execution too. In practice, there can be numerous paths that can lead to a given action execution. In order to be able to discover all relations between a given action and its predecessors, we must execute all possible previous actions. This complicates the learning phase, but it is a testing problem that can be easily solved.

Generating Invariants

The invariants are generated with Daikon, a tool commonly used by the software testing community. Daikon is able to generate from a trace file likely invariants on the values held by the variables. The variable values must have been logged in the trace file. Considering the trace exhibited by Figure 7, one can see that the user login parameter of the request at line 17 of the program is equal to the user login in the session at line 19 of the program. The value held by this variable at line 19 corresponds to the second time line 19 is executed. This side effect comes from the fact that there are in practice two instructions at this line. The first one is a call to a method, and the second corresponds to an assignment of the result returned by the previous method into the considered variable. This complexity is due to the fact that we are working at source code level and not at a bytecode or binary level (with atomic instructions). The invariants that we try to discover are those proposed in Section Classes of Invariants. From the file generated for the UsersController and login action, we obtain the invariant shown by Figure 8. This invariant is exactly the one pointed out in Section Invariant Constraints in an Application.

17_1_@_params["user"]["login"] == 19_2_@_session[:user][:login] In order to check the invariants at run-time, the application is instrumented as illustrated by Figure 9. As previously shown, the invariants have semantically all the pieces of information required to weave them in the application source code. Indeed, each invariant includes the name of the variable and also the line in the source code it is related to. In order to weave the invariants in the application source code, two types of instructions need to be inserted:

-Saving the values held by the variables of interest; 12, an alert is an XML structure that combines two nodes: <To> and <From>. The <To> node concerns the currently executed request, and the <From> node describes the previous request. The <From> node is filled with information if an invariant dealing with a relationship between two consecutive actions is violated. Each of these nodes is filled with all the information required to diagnose the problem: the http request, the controller that has been called, the action that has been performed, and a description of the violated invariant with the values of the involved variables.

Preliminary Results

Even a small application (around 1000 lines of Ruby code) and a small class of possible invariant types can lead to a large number of invariants (around 10000). These invariants are woven in the source code. As a result, the small source code files containing the controllers of the application can become huge (see Table 1 for a subset of the application controllers) and the execution time of these controllers increases. We measured execution time for a given set of controller executions. The mean execution time of a controller for non-instrumented source code was about 16.5ms. The mean time for the same executions of the instrumented application reaches 125ms. As a consequence, the instrumented code is about 8 times slower than the noninstrumented one. This is clearly an important difference. However, it must be noted that it remains acceptable for a normal user as the response of the server still seems instantaneous.

IDS Assessment

This section presents the experiments carried out to assess the efficiency of IDS to detect potential attacks, through the assessment of the false negative rate (percentage of attacks seen as valid inputs by the IDS), and the false positive rate (percentage o false alarms).

The evaluation of these measures requires the activation of the application and the IDS under test with a workload corresponding to attack-free traffic representative of the various services delivered to the users, combined with a set of malicious traffic (referred to as attackload) that should cover various potential attack scenarios.

Sections Workload Definition and Attackload Definition discuss how the workload and the attackload were generated, respectively. Section Experiments and Results describes the experiments and the results obtained considering the Insecure application as a case study. The main conclusions are discussed in Section Discussion.

Workload Definition

The workload can be generated with different methods: 1) replay of execution traces collected during "normal" browsing of the web application, 2) use of synthetic traffic generators and 3) real-time browsing of the application. For our experiments, we developed a synthetic traffic generator which offers flexibility to automatically navigate through the different URL links that can be visited from the application under test and to generate various navigation scenarios.

Several web crawlers exist but most of them cannot go through web pages that require prior authentication by providing a valid (login/password) or some specific inputs. Accordingly parts of the application may not be visited. Furthermore, additional functionalities are generally needed to facilitate the generation of attack-free traffic scenarios, such as defining (i) the maximum number of pages to be visited, or (ii) the maximum duration of a user interaction session, (iii) the number of users that can simultaneously interact with the application, or (iv) the time between consecutive user interactions with the application (usually called think time). As the crawlers we studied did not provide such a flexibility in their configuration, we developed our own crawler (See [START_REF] Akrout | Analyse de vulnérabilités et évaluation de systèmes de détection d'intrusions pour les applications Web[END_REF] for more details).

Attackload Definition

Attackload corresponds to malicious traffic that is aimed at exploiting vulnerabilities of the application. These malicious requests can be generated by hand, or automatically by web vulnerability scanners and attack tools.

Many vulnerability scanners have been developed in the last years [START_REF] Bau | State of the art: Automated black-box web application vulnerability testing[END_REF], [START_REF] Doupé | Why Johnny can't pentest : An analysis of black-box web vulnerability scanners[END_REF]). To detect vulnerabilities, they generate specially crafted inputs and analyze the corresponding responses to determine whether the input parameters submitted through the injection point are sanitized or not.

In our experiments, we used Wasapy, a vulnerability scanner developed at LAAS, which allows the automated detection and exploitation of different types of web vulnerabilities including SQL injections, OS commanding, File Include, XPath. algorithm implemented in Wasapy is briefly presented in the following considering the example of SQL injections (for more details, see [START_REF] Dessiatnikoff | A Clustering Approach for Web Vulnerabilities Detection[END_REF]).

The vulnerability detection and exploitation algorithm implemented in Wasapy is based on: i) the automatic generation of inputs based on a grammar that is specific to targeted vulnerabilities, and ii) the classification of the corresponding responses using data clustering techniques.

Three sets of requests are submitted at each injection point:

-R r corresponds to requests with randomly chosen data. They are very likely to generate error pages.

-R ii corresponds to syntactically invalid SQL injections that are designed to lead to unsuccessful executions.

-R vi corresponds to syntactically valid SQL injections. The main issue is to automatically determine whether they lead to a successful execution page or to a failed execution page. To do so, these responses are compared to those associated to sets R r and R ii using a similarity distance and a data clustering algorithm.

We note S r , S ii and S vi the responses associated to R r , R ii and R vi respectively. The R vi requests whose responses are not similar to any of the responses from S ii and S r are considered successful SQL injections.

Experiments and Results

To evaluate the IDS, we have considered as a case study the Insecure application presented in Section Context and Case Study which emulates an e-commerce web site. The users can perform atomic operations such as login to the web site, create an account, browse the list of products, write a review, add a product to a shopping cart, pay, etc. The application contains a few vulnerabilities including SQL injection, XSS, CSRF (Cross Site Request Forgery) and FileUpload vulnerabilities.

We have done two sets of experiments. In the first set, only non malicious traffic was submitted to the IDS to assess the rate of false positives under normal use conditions. The workload is generated automatically using the crawler discussed in Section Workload Definition. In the second set of experiments, we used Wasapy to identify the vulnerabilities of the application under test and automatically generate attacks that successfully exploit the identified vulnerabilities. These attacks are complemented by specially crafted attacks, not currently covered by Wasapy, that are run manually. During this second set of experiments, both false negatives (lack of detection) and false positives in the presence of attackload only, are identified.

In the following, we provide more details about the two sets of experiments, and the results obtained from these experiments. The experiments were conducted on a 3.6Ghz Pentium 4 with 6GB of RAM running Linux 2.6.32. The server was running Ruby (version 1.8) Rails (version 2.3.2) and libmsql-ruby 1.8.

Experiments with workload only. Our crawler was run during four hours, considering two different classes of users: regular users (80% of the traffic) and admin user (20% of the traffic). Each request is tagged with an identifier to facilitate the processing of the alarms raised by the IDS. Table 2 summarizes the results of these tests. 20 alarms were raised corresponding to the invalidation of four distinct invariants. These correspond to some normal browsing scenarios that were not activated during the learning phase. For example, one of these invariants asserts that the confirmation password is equal to the password, which in practice is an incorrect invariant. Another one asserts that the credit card of a user who purchases products is always the same, which is also not generally the case in practice.

Note that the number of raised alarms is less relevant than the number of invalidated invariants. Indeed, the number of raised alarms may be very different from a workload execution to another: if the crawler executes n times the scenario in which the password is different from the confirmation password, n alarms will be raised that correspond to a single invalidated invariant.

Experiments with attackload only. For these experiments, attackload was first automatically generated by Wasapy. Additionally, some attack scenarios that are not currently supported by Wasapy were manually generated.

The clustering algorithm of Wasapy was parameterized with 30 requests for each set R r , R ii and R vi . Thus, 90 crafted requests are sent through each injection point and each attack category. These values are determined empirically, however more requests could also be generated. When the four categories of vulnerabilities implemented in Wasapy are investigated (SQL Injection, XPATH injection, File Include and Os Commanding), 90 x 4, i.e., 360 crafted requests are sent for each injection point. Table 3 summarizes the results of these tests. Wasapy identified 37 injection points and as a consequence, sent 37 x 360 (i.e., 13320) crafted requests.

The IDS detected all the requests that actually succeeded in exploiting the vulnerabilities. Indeed, among the 90 x 37 requests sent by Wasapy to detect SQL vulnerabilities, only 11 were successful. The raised alarms exactly correspond to these 11 cases. There are no false positives, neither false negatives. The other requests sent on each injection point, corresponding to XPATH, OS Commanding and File Include attacks, were not successful because such vulnerabilities do not exist in the Insecure application. Interestingly, the IDS did not raise any alarm in these cases too.

Three additional attack scenarios were manually executed to exploit some other vulnerabilities: 1) the manual modification of the session cookie (enabling a user to log into the application without supplying any valid login/password, by using the session cookie of an already authenticated user), 2) the manual modification of requests parameters that enables to modify the price of a product during a purchase session and 3) the upload of a Javascript File instead of an image file. The manual modification of the price of a product is correctly detected as it corresponds to the violation of an invariant identified during the learning phase. However, the other attacks were not detected. The upload of a JavaScript File cannot be detected with the proposed IDS because the target of the attack is not the web application itself but the browser (it is a form of XSS attack). As a consequence, it seems difficult to be associated to an invariant. A similar observation can be made concerning the attacks based on the modification of the session cookie. It seems quite difficult to identify one invariant that could be relevant for this kind of attack.

Discussion

The experiments described in this section show that the intrusion detection system is particularly efficient to detect successful attacks on the Web application, i.e., crafted requests that actually lead to the violation of the application state integrity. No false positives and no false negatives were generated when the attackload only was sent to the application. Let us emphasize that our vulnerability detection algorithm, sending a large number of crafted requests per injection point, is particularly adapted to evaluate the number of false positives. Regarding the false negatives, some additional experiments still have to be carried out because the Insecure application does not include many vulnerabilities. The false negatives must be considered carefully and should be confirmed by testing the IDS on other Ruby applications. Finally, our experiments with attack free workload also illustrate the importance of the learning phase for the intrusion detection system. These experiments raised a few false positives that are associated to four invalidated invariants. These incorrect invariants were due to the learning phase, which was incomplete. A more complete learning phase would have not produced these invariants.

Conclusion

The application level anomaly based intrusion detection mechanisms presented in this paper rely on the modelling of the application normal behaviour using invariants. The violation of an invariant is then considered as an indication of an attack against the application. A first step consists in learning the normal behaviour of the application by logging at runtime the value of variables and automatically generating invariants on these data items. The invariants are then woven in the source code to detect a violation of the application normal state during its execution. Although we are looking for a reduced set of invariant classes, the experience proved us that the approach is able to discover a large number of invariants, even on a small application. Moreover, the assessment phase proved that common attacks, such as SQL injections were successfully and accurately detected by our approach. However, some attacks such as Cross Site Scripting or Session Hijacking are not detected by our approach. This is not surprising, as these attacks either impact the client browser, or do not violate the server normal application state. These attacks are thus not the type of attacks we claim to detect.

Figure 1 .

 1 Figure 1. Rails MVC framework in the context of our application

Figure 3 .

 3 Figure 3. SQL request in the user Model

  (session[:user].login) is equal to the login passed as parameter (params[:user][:login]). As a consequence, the relation session[:user].login == params[:user][:login] is an invariant of the application.

Figure 4 :

 4 Figure 4: Action called for a new order

  class User::OrdersController < User::UserController ... def create params[:order][:user_id] = @user.id params[:order][:card_expiration] = Date.parse( "#{params[:card_expiration][:year]}/#{params[:card_expiration][:month]}/1") @order = Order.new(params[:order]) @amount = params[:amount] respond_to do |format| if @order.save save_items session[:cart] = nil flash[:notice] = "Your order has been successfully placed"

Figure 6 .

 6 Figure 6. Variables causally dependent on user inputs

Figure 7 .

 7 Figure 7. Trace handled by Daikon

Figure 8 .Figure 9 .

 89 Figure 8. Example of Invariant generated by Daikon Run-Time Invariants Checking

  Login Action in the Users ControllerFigure2illustrates the Ruby code used in the application to authenticate a user. This code is located in the action login of the controller Users.

	class UsersController < ApplicationController ... def login if request.post? # whole user is stored in the session if session[:user] = User.authenticate(params[:user][:login], params[:user][:password]) flash[:notice] = 'You have been successfully logged in.' if session[:user].admin redirect_to :controller => '/admin/home', :action => 'index' else redirect_to :controller => '/user/home', :action => 'index' end else flash.now[:error] = 'Login failed' end end end ... end ... def self.authenticate(login, pass) user=find(:first,:conditions => "login = '#{login}' and password = '#{pass}'") end ... Figure 2. class User < ActiveRecord::Base end

Table 1

 1 Instrumentation results

	Subset of Insecure files	Initial number of	Lines of	Woven Invariants
		lines	instrumented code
	Application_controller.rb 20	20	0
	Home_controller.rb	11	537	239
	Products_controller.rb	26	1503	675
	Reviews_controller.rb	37	1547	691
	Users_controller.rb	51	1681	771

Table 2

 2 Number of invalidated invariants: workload only

	Number of requests	Number of raised alarms	Number of invalidated invariants
	1623	20	4

Table 3

 3 Attackload only

	Number of	Number of	Number of raised	False positives	False negatives
	crafted requests	successful	alarms
		attacks
	13320	11	11	0	0

-Checking the invariant itself at the right line (e.g., for the invariant of Figure 8, the invariant shall be woven at line 19 of the concerned Controller). If we consider an excerpt of the UsersController file that concerns only the login action Figure 10, and after having woven the invariant shown by Figure 8, we obtain the listing presented in Figure 11. In this listing the instruction saving the values held by variables of interest has been inserted and the checking of the invariant is done after the call to the authenticate method. As a result, the SQL injection described in Section Invariant Constraints in an Application can be detected, since it would violate this invariant. Consequently, an alert is generated (see Figure 12) describing precisely the violation observed with respect to the application state.