Michel Chilowicz

Étienne Duris

Gilles Roussel

LDTA 2008

Keywords: program transformation, factorization, inlining, outlining, similarity metrics, software plagiarism

The high availability of a huge number of documents on the Web makes plagiarism very attractive and easy. This plagiarism concerns any kind of document, natural language texts as well as more structured information such as programs. In order to cope with this problem, many tools and algorithms have been proposed to find similarities. In this paper we present a new algorithm designed to detect similarities in source codes. Contrary to existing methods, this algorithm relies on the notion of function and focuses on obfuscation with inlining and outlining of functions. This method is also efficient against insertions, deletions and permutations of instruction blocks. It is based on code factorization and uses adapted pattern matching algorithms and structures such as suffix arrays.

Introduction

Current similarity detection techniques on source codes are mainly inspired from computer genomic algorithms [START_REF] Prechelt | Finding plagiarism among a set of programs JPlag[END_REF][START_REF] Schleimer | Winnowing: local algorithms for document fingerprinting[END_REF][START_REF] Irving | Plagiarism and collusion detection using the Smith-Waterman algorithm[END_REF] in which factorization and development (outlining and inlining) have not been widely explored. In this paper, we present a new similarity detection technique based on the factorization of source code that permits finding similarities and quantify them at a function-level thanks to a synthetized graph-call of the programs.

This technique consists in splitting each original function into sub-functions, sharing as much sub-functions as possible between original functions. The whole source code is then represented by a call graph: the vertices are the functions and the edges are the function calls. Thus, similar functions should derive in an identical, or comparable, set of sub-functions, i.e., leaves of the call graph. Depending on the measurement used to evaluate (sub-)function similarities, this technique may not be sensible to insertion, deletion, inversion, inlining or outlining of source code which are the most common methods of obfuscation.

The rest of this paper is organized as follows. Section 2 gives an overview of the whole detection process. The main steps of the factorization algorithm and call graph analysis are detailed in section 3 and 4. Related work and benchmarks are discussed in sections 5 and 6. The paper then presents a conclusion and introduces some future work.

Overview

Our work is directed towards finding similarities in source code in procedural languages at the level of function. Our aim is to experiment a similarity detection technique based on function transformations. Indeed, to be insensitive to outlining, inlining and source block displacements, we manipulate abstractions of the programs that are call graphs. Initially, the call graph is the one of the original program. Next, by using several algorithms, the call graph is enriched with new synthetic sub-functions that represent the granularity of similarities.

From source code to token sequences and call graph

From the original source code of a program, a lexical analysis provides us with a sequence of tokens. In this sequence, the concrete lexical tokens are represented by abstract parameterized tokens. Some tokens, such as function parameters or variable declarations are discarded. It is also possible to use normalization techniques, based on syntactic or semantic properties, to filter and enhance the result. For instance, the sequence we process is independent of the identifiers of variables and functions in order to defeat the simplest obfuscations2 . Since the tokens could be scattered and merged into synthetic sub-functions by the factorization process, each token is associated with its position (project, file, line number of the token) in the source code in order to backtrace information. A segment tree [START_REF] Cormen | Introduction to Algorithms[END_REF] is used to store this information, and is updated to take into account synthetic sub-functions.

After the normalization and the tokenization step, each function of the source code is represented as a sequence of two kinds of parameterized abstract tokens: a primitive token is a reserved keyword of the language, a constant or a variable identifiers and a call token, noted f , models a call3 to a function f . We respectively note Σ p and Σ c the sets of primitive and call tokens. For instance, figure 2 gives the token sequence and alphabets obtained from the C function f 2 of the figure 1.

Each original function of the source code being represented as a sequence of tokens, the next step of our algorithm is then to identify common factors in these functions and to factorize them in some new outlined synthetic functions. However, several factorizations are possible and they potentially require heavy computations. To cope with these problems, we use classical pattern matching data-structures, such as suffix arrays, and some new dedicated structures, such as the parent interval table, allowing our algorithms to be efficient.

The factorization process

To be able to efficiently identify common factors (identical substrings of tokens) in token sequences of functions, we use the suffix array structure [START_REF] Manber | Suffix arrays: a new method for on-line string searches[END_REF].

To minimize the number of synthetic outlined functions, we first seek if a (part of a) small function could be found in a larger one. At first sight, the notion of small could be perceived as the length of the factor (number of tokens); we rather use the notion of weight function w, that may include more parameters 4 . We note F 0 = {f 1 , . . . , f n } the set of all original functions, sorted by increasing weight. Thus, for each function f k ∈ F 0 we scan the functions F 0 <k = {f 1 , . . . , f k-1 } (functions whose weight are smaller than the weight of f k ) to find pairs of factors (u 1 , u 2 ) with u 1 ∈ fact (F 0 <k ) (u 1 is a factor of a function f j ∈ F 0 <k , i.e., j < k) and u 2 ∈ fact ({f k }) such as u 1 = u 2 . Thereafter, the occurrence u 1 is outlined into a new synthetic function g = u 1 whereas the occurrence u 2 from f k is replaced by the call token g . We note that the function f j of u 1 is unchanged at this step, to allow larger factors to be identified in a further f l for l > k. The next iteration of the algorithm will allow the entire sequence of g to be identified as common with the factor u 1 of f j , and the replacement of u 1 by g will occur at this time. Anyway, if the factor u 1 covers an entire function f j , there is no need to create a new function g. These operations of search and replacement of factors by call tokens are undertaken for all of the functions from F 0 . Thus, for the next iteration, a new set of functions F 1 ⊇ F 0 can be deduced from F 0 adding the new outlined functions and ordering the resulting set by increasing weight.

Several iterations of this algorithm are needed to achieve better precision for the call graph, in particular to detect shorter redundancies. Nevertheless, at the end of each iteration, we are able to evaluate a score of similarity between two functions. This score is based on the number and the weight of common leaves of the call-graph that are attainable from each of these functions. To ease the evaluation, only two kinds of functions are considered according to their content: either they only contain primitive tokens or only call tokens. A mixed function is transformed into a function containing only call tokens via an outlining of all subsequences of primitive tokens.

Example

For a better understanding, we introduce a small example explicited on figure 1: a bubble-sort in C where the recursive function subsort (f 2 ) calls the functions exchange (f 1 ) and min index (f 3 ). The function inlined subsort (f 4 ) could be considered as an obfuscated version of f 2 after the inlining of f 3 and f 1 . Actually, from such a source code, our algorithm first produces a sequence of abstract tokens. For example the dictionaries Σ p , Σ c and the raw sequence of abstract tokens extracted from f 2 are explicited on figure 2. Note that variable declaration tokens have been omitted. The first iteration of the algorithm searches matches in F 0 = {f 1 , . . . , f 4 } (we chose function indices with respect to increasing weight of functions, i.e. number of tokens in our example). During the examination of f 4 two matches in f 3 (new function Φ 1 ) and in f 1 (new function Φ 2 ) are found. The functions Φ 1 and Φ 2 are outlined and replaced by their call tokens in f 4 . Depending on the chosen weight-threshold for match reporting, another function Φ 3 corresponding to the lines 16 and 23 could be outlined. Here we consider instead that these lines yield two distinct primitive-token functions (leaves) f ′ 2 = f 2 [START_REF] Kurtz | Reducing the space requirement of suffix trees[END_REF] and f ′ 4 = f 4 [START_REF] Schleimer | Winnowing: local algorithms for document fingerprinting[END_REF]. In order to ensure that f 3 only contains call tokens, a new function f ′ 3 is also outlined, corresponding to the line 8 of f 3 : thus, f 3 only contains two call tokens to Φ 1 and f ′ 3 . Finally, at the end of the first iteration, the set of functions ordered by increasing weight is

F 1 = {f ′ 3 , f ′ 2 , f ′ 4 , Φ 2 , f 1 , f 4 , f 2 , Φ 1 , f 3 }.
During the second iteration, Φ 2 is found and replaced by a call token while examining f 1 and Φ 1 is found in f 3 . We then obtain the call graph explicited on figure 1 at the end of the second iteration.

This graph allows us to define three kinds of metrics, or scores, based on the number and the weight of leaves attainable from each function. We define more precisely in section 4 the score of inclusion (sc incl ) of a function into the other, the score of coverage (sc cover ) of a function by another one and finally the score of similarity (sc simil ) between two functions. For example, for functions f 2 and f 4 , we obtain following values:

sc incl (f 2 , f 4 ) ≈ 0.88 > sc cover (f 2 , f 4 ) ≈ 0.85 > sc simil (f 2 , f 4 ) ≈ 0.76.

Factorization algorithm

In this section, we focus on the algorithms and data-structures involved in the factorization of a given function f i using most-weighted non-overlapping factors of F <i . Realistic examples generate long sequences with a lot of tokens. For concision and in order to easily exhibit interesting cases, we will use a simplistic5 but illustrative running example with the alphabet {a, b} for primitive tokens and with five initial functions of F 0 :

f 1 = aba f 2 = aaba f 3 = bbaba f 4 = bababa f 5 = abaabbababa
We will show how f 5 could be factorized as aba • ab • bababa, and then be considered as constituted by sub-functions f 1 [0..2], f 2 [1..2] and f 4 [0..5].

Working with suffix array

First of all, we have to identify common factors (sub-sequences of tokens) in functions. Indeed, while inspecting the sequence of tokens of f 5 , we want to know which parts of others functions are candidates for a match. To deal with this problem, our algorithms rely on a suffix array [START_REF] Manber | Suffix arrays: a new method for on-line string searches[END_REF], i.e., an indexed table containing all suffixes of the functions, sorted according to a given order on the tokens, e.g. lexicographical. Various suffix array construction algorithms may be used such as the direct linear model of Kärkkäinen and Sanders [START_REF] Kärkkäinen | Simple linear work suffix array construction[END_REF]. The main advantage of this structure is its small size since for a string of length n only log 2 n bits are needed for each suffix whereas the better known construction of suffix tree requires at least 10 bytes by indexed token [START_REF] Kurtz | Reducing the space requirement of suffix trees[END_REF].

Figure 3 gives a representation of the suffix array for our running example, where each suffix appears only once: when the same suffix appears in several functions, we only show in this figure the smallest function index and position, and increment the rank in the array for each occurrence of this suffix. For the sake of clarity, it also shows the corresponding sequences, even if they are actually not stored: a suffix starting at position p of function f i is simply designated by the pair of integers (i, p). We also need the reverse suffix array, not represented here: given function index i and a position p defining a suffix of this function, it provides its rank in the suffix array.

Searching Factors through Parent Interval Table

The key idea of the suffix array structure is that suffixes sharing the same prefix are stored at consecutive ranks. Thus, the notion of rank interval makes sense: for instance, all factors starting with aba could be found in the interval [8..15]. Nevertheless, intuitively, we are looking in a "long" function for factors of "shorter" functions. Thus, if we search factors of the complete function f 5 = abaabbababa in the suffix array, we find the interval (singleton) [13..13] corresponding to the function f 5 itself. This is not a suffix of a function of smaller index, and we have to successively consider all shorter prefixes of this sequence until finding a rank interval concerning a function of smaller index.

To efficiently search for a maximal factor, we introduce a new data structure: the Parent Interval Table (PIT ). It is deduced from the complete interval tree of the suffix array, i.e., a suffix tree without its leaves. To each suffix s, the PIT associates a set of data ([k..h], l, α, ρ). In the suffix array, k and h (k = h) are the ranks of the first and the last suffixes that share the longest common prefix (lcp) with s; l is the value of this lcp of the interval [k..h]. Finally, α is the minimal index of the functions associated to its interval, and ρ is the rank of the longest suffix extracted from the function of index α in the interval. Figure 4 shows the structure represented by the PIT for our example. To find the maximal-lcp interval in the suffix array, different strategies may be used. The simplest is to build the complete interval tree of the suffix array, saving the parent pointers between intervals. Another way is to save only the needed intervals. An interval is needed if and only if its α-value is strictly smaller than the α-value of one of its children. We use a dedicated algorithm (not detailed here) to compute the PIT and the needed intervals on the branches thanks to the LCP table, already computed in linear time [START_REF] Rick | Simple and fast linear space computation of longest common subsequences[END_REF]. This algorithm uses a simple sequential reading of the LCP table with a stack simulating the current branch of the interval tree. It runs in linear time, with a memory complexity in the height of the interval tree (linear in the worst case).

Our algorithm identifies all the maximal factors of a function f i that match with parts of functions of F <i . Thus, for each position p in f i , it looks for a factor of a function in F <i sharing the longest prefix with f i [p..]. To find it, the information ([k..h], l, α, ρ) is retrieved from the PIT for the suffix f i [p..]:

• If α < i, then ρ is the rank in the suffix table of a function (f α , q) such as f α [q..q + l -1] is a maximal factor of f i [p..]. For instance, for f 5 [3..], (abbababa), the PIT yields the information ([8..16], 2, 1, 8): since α = 1 < 5 and ρ = 8 is the rank of (f 1 , 0) we found f 1 [0..0 + 2 -1] (ab) as a maximal factor of f 5 [3..].

• If α ≥ i, and since we are only looking for factors in F <i , we must examine the parent interval of smaller lcp, i.e., a parent node in the PIT, until finding an interval whose minimal function index is smaller than i.

Eliminating overlapping factors

Once a set of maximal factors is associated with f i , one for each position, overlapping between them is expected. For the example of f 5 , these factors appear in the three left-most column of the combinations of (parts of) these factors are allowed to cover the function f i . For instance, f 5 could be covered by ab.aa.bbaba.ba or by aba.ab.bababa.

To retain a factorization of f i using most-weighted 6 non-overlapping factors, all the matched factors are placed in a priority queue, and the mostweighted ones will be successively selected, as indicated by the numbered arrows in the figure 5. For each selected factor, we must remove all intersecting parts from all other candidate factors before selecting the next factor.

To achieve this, a segment tree [START_REF] Cormen | Introduction to Algorithms[END_REF] is created and fed with the intervals of positions of the factors found on f i . A range tree is an adaptation of a balanced binary tree: each node is a interval whose key is the low bound. This structure can be used to find k intersecting factors in O (max(k, log |f i |)). For each iteration we extract the most-weighted factor u from the priority queue and search all the intersecting factors V = v 1 , . . . , v |V | in the range tree. Since we use an homogeneous weight function 7 , u is not a strict factor of any factors of V (∀v ∈ V, w(u) ≥ w(v)). For each factor v k ∈ V , we remove it from the priority queue and from the range tree. If it is not a factor of u but shares an intersecting part on the left or on the right, we remove the intersecting part of v k with u to obtain v ′ k that is added in the range tree. Since there is at most one match for each position in f i , the most-weighted matches must be selected between at most |f i | matches. For each selected match there is at most |f i | -1 intersecting factors, each of them needed a time in O (log |f i |) to update the range tree and the queue. So the global 6 The weight function is defined on Σ * . In a first approach we define the weight function w(u ∈ Σ * ) = w(u 0 ) + w(u 1 ) + • • • + w(u |u|-1 ) and a constant weight vector associating to each primitive token a constant value. To infer the weights of the call tokens, we establish for each function f the set of reachable leaf functions lf (f ) according to the call graph of the previous iteration (see 4.1) and compute the sum of the weights of these reachable leaf functions. Thus the weight of a call token reflect the amount of coverage of code of its underlying called function. 7 A weight function w is homogeneous iff ∀(x, y) ∈ Σ 2 such as x ∈ fact (y), w(x) ≤ w(y).

W that associates to a set of leaf functions the sum of their weights. These data are used to introduce a concrete definition of the amount of information I contained in projects or shared between functions:

I :          I(f ) = W (lf (f )) I(f 1 ∩ f 2) = W (lf (f 1) ∩ lf (f 2)) I(f 1 ∪ f 2) = W (lf (f 1) ∪ lf (f 2))
Then we deduce a valuation for the metrics sc incl , sc cover and sc simil :

     sc incl sc cover sc simil      : (f 1, f 2) -→ W (lf (f 1) ∩ lf (f 2)) •      1/ min [W (lf (f 1)) , W (lf (f 2))] 1/ max [W (lf (f 1)) , W (lf (f 2))] 1/W (lf (f 1) ∪ lf (f 2))     
These metrics have different purposes. sc incl is useful to quantify plagiarism: if sc incl (f 1, f 2) = 1, then one of the internal functions shares all its reachable leaf functions with the other like in case of small functions copied from larger ones or the contrary. For instance, this score detects a plagiarism between the functions f 4 and Φ 1 of figure 1. sc cover quantifies the amount of coverage of the leaf functions of the heaviest function (in terms of the sum of the weights of the reachable leafs) by those of the lightest. Finally sc simil (f 1, f 2) measures the amount of similarity between f 1 and f 2:

sc simil (f 1, f 2) = 1 iff lf (f 1) = lf (f 2).
Since reachable functions are represented by sets, without order consideration in the defined family of metrics, two algorithmically distinct functions may be considered similar. This method may report false-positive matches, in particular if the length of leaf functions is not lower-bounded 8 .

For a graph of n functions, computing the weight vector and the similarity matrix requires the knowledge of the reachable leafs of each function (determined in O (n 2 ) through a graph-walk) and the computation of the intersection of the reachable leaves of each pair of function (in O (n)). Finally, the computation of a similarity matrix between all functions takes a temporal complexity in the worst case of O (n 3 ).

Clustering of similar functions

After each iteration, we introduce a clusterization process on the internal functions to obtain equivalent classes of functions. Each call token is replaced by a member of its equivalence class. This induces a simplification of the call graph with the removal of other functions of the class and some unshared leaf functions. In the example of figure 1, f 2 and f 4 may be clustered into an 8 If the leaf functions are reduced to primitive instructions all functions may be similar.

equivalent class with the removal of {f ′ 2 , f ′ 3 } or {f ′ 4 } depending on the removed function (f 2 or f 4 ). For the next iteration a new total order on Σ c is deduced. Here a call token to f 2 or f 4 will be considered equivalent. For instance, if two sequences f 2 f 2 f 4 and f 4 f 4 f 2 are encountered, they cannot be reported as a match. But if f 2 and f 4 are sufficiently similar to be clustered, they will be renamed and the two sequences will exactly match at the next iteration. Clustering introduces false-positives but increases the recall.

We also consider a clusterization process on the leaf functions in order to treat as similar near sequences of primitive tokens to cope with local additions, deletions or substitutions of tokens.

Related work

Many research work has already focused on the detection of similarities. Among them, some look for similarities in free texts [START_REF] Clough | Old and new challenges in automatic plagiarism detection[END_REF], in this section, however, we will focus on research work that search similarities in source code. These work may be divided into two main groups depending on their aim.

The first group of work focuses on software engineering. It attempts to find exact matching in order to factorize redundant cut-and-paste or to follow the evolutions between different versions of one project. Usually they do not address the problem of obfuscation. In this context exact methods of pattern matching [START_REF] Baker | On finding duplication and near-duplication in large software systems[END_REF][START_REF] Ducasse | A language independent approach for detecting duplicated code[END_REF][START_REF] Burd | Evaluating clone detection tools for use during preventative maintenance[END_REF] and complex algorithms on the abstract syntax trees [START_REF] Baxter | Clone detection using abstract syntax trees[END_REF] or the dependency graphs [START_REF] Horwitz | Interprocedural slicing using dependence graphs[END_REF][START_REF] Krinke | Identifying similar code with program dependence graphs[END_REF] may be applied. Several tools such as CCFinder [4] or CloneDR [6] are used to implement these approaches.

The second group of work focuses on plagiarism detection. Its objectives are to detect similarities in the potential presence of intentional obfuscation. The oldest of these works [START_REF] Parker | Computer algorithms for plagiarism detection[END_REF][START_REF] Verco | Software for detecting suspected plagiarism: Comparing structure and attribute-counting systems[END_REF] that use different program metrics to compare whole programs are usually defeated by simple transformations. Consequently, techniques have been used to get around this problem. Several of these techniques [START_REF] Prechelt | Finding plagiarism among a set of programs JPlag[END_REF][START_REF] Schleimer | Winnowing: local algorithms for document fingerprinting[END_REF] are based on Karp-Rabin fingerprints of token n-grams [START_REF] Karp | Efficient randomized pattern-matching algorithms[END_REF]. Two popular applications accessible on the Web are used to implement these approaches. Moss [18] selects and stores fingerprints in a database through the Winnowing process [START_REF] Schleimer | Winnowing: local algorithms for document fingerprinting[END_REF] in order to compare it to a large number of programs. JPlag [START_REF] Jplag | [END_REF] extends matching code zones for identical fingerprints with the Greedy String Tiling algorithm [START_REF] Wise | Running karp-rabin matching and greedy string tiling[END_REF]. SourceSecure [START_REF] Ouddan | A multilanguage source code retrieval system using structural-semantic fingerprints[END_REF] considers alignment of semantic fingerprints of salient elements in code generated by grammaractions rules. Another approach [START_REF] Chen | Shared information and program plagiarism detection[END_REF] implemented by the web-service SID [START_REF]SID[END_REF] is based on the LZ compression technique [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF] to detect redundant code. As far as we know, the methods based on abstract syntax trees have not been used to address the detection of plagiarism.

Aside from the differences in the algorithms, unlike other tools that consider complete source code files for comparison, our method is based on a directed graph representing the program where similar parts of the code are merged into a single node.

We tested our similarity detection method on a set of 36 student projects (about 600 lines of ANSI-C code for each project) by comparing it against Moss [18] and JPlag [START_REF] Jplag | [END_REF]. Like Moss and JPlag we work on the raw token stream extracted from the bodies of functions without any preliminary normalization step by syntactic or semantic interpretation.

Among the student projects, we selected a random project that is humanly obfuscated using the following methods: no change (1), identifier substitutions (2), changes of positions of functions in the source code files (3), regular insertions and deletions of useless instructions (4), one level of inlining of functions [START_REF] Chen | Shared information and program plagiarism detection[END_REF], outlining of parts of functions (6), insertions of identical large blocks of code [START_REF] Clough | Old and new challenges in automatic plagiarism detection[END_REF]. We also added a non-plagiarized project (8) according to a human review.

We studied top inclusion scores from the generated similarity matrices via Moss, JPlag and our method after 5 iterations using the plagiarism metrics sc incl . Ideally the inclusion (or plagiarism) score between an original project and an obfuscated project based on the totality of code of it should be 1. The plagiarism scores for the different kinds of obfuscation can be found in figure 6 and the execution times (on a Pentium 4 3 Ghz CPU with 1 Go RAM using the Sun JRE 1.5) for our method in figure 7; since Moss and JPlag are server-side executed their running time can not be compared. We note that the parameters used (length of the fingerprinted n-grams and window size) by the Moss online-service are not known ; concerning JPlag the token length threshold was set to 10. For our factorization method we used a token length threshold of 10 to report a match and ignored leafs whose length is smaller than 10 for the computation of leaf sets.

We observed that almost all the studied student projects contained shared chucks of code potentially raising false-positive reporting problems. These can be avoided by discarding code shared by more than one fixed number of projects (here 10).

Our method, in spite of being directed towards the detection of inlining and outlining obfuscation, presents lower similarity scores on these kind of obfuscation than JPlag; the plagiarism score computed by JPlag is not documented and we will need more work to explain this difference. However, results are promising for the detection of code obfuscated by insertion and deletion of

Conclusions

Our factorization method for finding similarities in source code shows modest but promising results on preliminary tests. Its main advantage relies on the resistance against obfuscatory methods such as inlining, outlining or shift of blocks of code. We discuss here the limits of our approach and future developments to be considered.

Extreme outlining over the set of functions of projects could result in few short leaf functions (especially when using abstract tokens). For example all of the instructions and assignments could be outlined in leaf functions. Since our method does not consider the order of called functions, the precision is reduced. Some false positive may appear. This is why an upper threshold for the lengths of the leaf functions must be set. Considering new metrics for the comparison of pair of functions that takes into account the order of function calls may be envisaged. Furthermore, some data-flow analysis could be performed on specific parts of the code to reduce false positives.

Currently, our method does not deal with function calls with one or more function calls as argument. This type of situation is not unusual in source code and raises interesting schemes for obfuscation. A preliminary approach could add temporary local variables to unfold the composed calls into intermediate assignments.

Figure 3 .

 3 Figure 3. Suffix array for the example

Figure 4 .

 4 Figure 4. Tree structure represented by the PIT

  For instance, looking for maximal factor of f 4 [0..] (bababa) leads to ([26..27], 6, 4, 26): since α = 4 ≥ 4, we have to consider the interval of the parent node, ([23..27], 4, 3, 23). Now, α = 3 < 4 and ρ = 23 being the rank of (f 3 , 1), we found f 3 [1..1 + 4 -1] (baba) as a maximal factor of f 4 [0..].

Figure 5 .

 5 Figure 5. Selection of non-overlapping matches on f 5

Figure 6 .Figure 7 .

 67 Figure 6. Similarity scores between the original and the obfuscated projects

f3 f3 f1 Φ2 Φ1 int min_index(int t[],int start) { int i_min, j; i_min=start; j=start+1; while (j<SIZE) { if (t[j]<t[i_min]) i_min=j; j++; } return i_min; } void exchange(int t[],int a,int b) { int tmp; tmp=t[a]; t[a]=t[b]; t[a]=tmp; } void subsort(int t[],int i) { int i_min; if (i>=SIZE) return; exchange(t,i,i_min); subsort(t,i+1); } int i_min, j, tmp; if (i>=SIZE) return; i_min=i; j=i+1; while (j<SIZE) { if (t[j]<t[i_min]) i_min=j; j++; } tmp=t[i]; t[i]=t[i_min]; t[i_min]=tmp; } i_min=min_index(t,i); f1 f2 f4 Φ1 void inlined_subsort(int t[],int i) { inlined_subsort(t,i+1);

			Φ1
			f2
			Φ2
			f2[16]
			= f2'
			f4[23] = f4'	f3[8] = f3'
			f4
			Φ2
	Figure 1. Source code example and call graph deduced after two iterations
	Σ p	Σ c	Raw sequence of abstract tokens from f 2
	IF, LPAR, RPAR, GE	<min index>	IF LPAR identifier GE identifier RPAR RETURN SEMI
	identifier, ASSIGN	<exchange>	identifier ASSIGN <min index> SEMI
	RETURN	<subsort>	<exchange> SEMI
	SEMI		<subsort> SEMI

Figure 2. Tokenization of function f 2 (subsort)

This first step is also performed by other similarity detection tools[18,[START_REF] Jplag | [END_REF].

We note that function calls may be statically ambiguous in some languages like Java.

For instance, a function call could have a greater weight than a primitive token, or a usual instruction (assignment, semicolon) could have a lesser weight than a rare one (switch).

The example presented in section 2 is more detailed on the following web page: http://igm.univ-mlv.fr/ ∼ chilowi/research/finding similarities/

Call graph analysis

The process of factorization we apply is based on the algorithm previously described, which is iterated several times. Nevertheless, each iteration provides us with a call graph whose nodes are functions, with leaves being primitive functions (composed of only primitive tokens). This graph could be used to define and measure some metrics, or scores, relative to similarity between two functions. We will first define abstract metrics qualifying similarity between two projects, and then present how we value them in the concrete context of our process. Next, we will see that these metrics could be used to enhance the factorization algorithm at each iteration.

Quantifying plagiarism

To measure the degree of similarity on pairs of projects (a project being one or a set of functions), we define an abstract information metrics I(p i ) representing the amount of information contained in a project p i . The associated metrics I(p i ∩ p j ) and I(p i ∪ p j ) quantify respectively the amount of common information shared between two projects p i and p j and the total amount of information contained in the two projects p i and p j . We then define the three following metrics over projects:

• sc incl (p i , p j ) = I(p i ∩p j ) min(I(p i ),I(p j )) is the inclusion metrics and states the degree of inclusion of one project into another. In fact sc incl (p i , p j ) = 1 means that the smaller project (in term of amount of information) is included into the greater.

• sc cover (p i , p j ) = I(p i ∩p j ) max(I(p i ),I(p j )) is the coverage metrics and quantifies the degree of coverage of the greater project by the smaller project.

• sc simil (p i , p j ) = I(p i ∩p j ) I(p i ∪p j ) is the similarity metrics and measures the degree of similarity between the two projects p i and p j . We note that sc simil (p i , p j ) = 1 iff the projects p i and p j are identical according to the information metrics I.

In the particular case of our algorithm, we evaluate concrete metrics based on the previous definitions. Considering the graph of call relations deduced from the last iteration of the factorization algorithm, the set lf (f ) of leaf functions (functions of primitive tokens) reached by each internal function f (not leaf) is computed by transitive closure. Then, for each pair of internal functions (f 1, f 2) the set lf (f 1) ∩ lf (f 2) is computed. Based on the weight function w on leaf functions (w : f -→ |f | may be used), we define the function Presently, results of outlining processes are viewable as partial outlining graphs where leaf functions are selected according to their attainability from initial functions. Similarity between functions or clusters are used to locate similarities. A more human-friendly tool for the render of results remains to be studied.


Damien Masson
email: d.masson@esiee.fr

Serge Midonnet
email: serge.midonnet@univ-paris-est.fr

The Design of a Real-Time Event Manager Component

We review the issues with the conception of realtime event based applications and propose an event manager component design. We start from the design proposed by the Real-time Specification for Java to handle asynchronous events and we extend and generalize it to form an event manager component. This component manages the relations between the triggering of distributed events, the events handlers and the resource allocations (servers and processors). The allocation process consists of setting individual event handlers to servers and servers to processors. The component uses the description of the events relations to generate a state automaton used to release their handlers. The feasibility analysis is processed at a component level and takes into account the events relations and the association of the servers with the processors (affinity).

I. INTRODUCTION

The aim of this paper is the design of an event based real-time application in a high level programming language. Indeed, the idea which was taken as a joke ten years ago to program real-time application in Java is becoming a reality nowadays. The Java community requested a real-time specification in 1996 and a first release of the RTSJ was published in 2000. This first version specifies a set of classes to represent the scheduler, the real-time tasks and handlers of asynchronous events, the time and timers, memory regions and monitors to control shared resource accesses.

A new Specification Request (JSR-282) was recently presented in order to specify a new release (version 1.1) for RTSJ, and a new revision of the Reference Implementation (RI-1.1 alpha6) is provided by Timesys. This release improves the processing of asynchronous events (data can be associated with an event triggering) and describes the affinity of schedulable entities and processors in multiprocessors environments.

In a previous work [START_REF] Masson | RTSJ Extensions: Event Manager and Feasibility Analyzer[END_REF], [START_REF]Userland Approximate Slack Stealer with Low Time Complexity[END_REF], we focused on the implementation within the RTSJ of advanced mechanisms. We want here to go further with the design of an high level software component which homogenize different solutions for the handling of asynchronous event in real-time systems.

The component approach allows to encapsulate mixed and complex mechanisms such as the inter events relation expressions, resources allocation, feasibility analysis or system dimensioning.

This paper presents the existing approach within the RTSJ, defines a design for a component we call the Event Manager and proposes configurable CORBA-idl interfaces to implement it. All pieces of the component we propose are implemented as part of different work. The aim of this component is so to make them run together.

Section 2 presents the existing model of the RTSJ to represent asynchronous event, its limitations, and the need to at least another entity: the task server. Section 3 introduces our EventManager and Section 4 formalizes it. We conclude and present future works in Section 5.

II. COMPONENT DESIGN AND ABSTRACTIONS

We introduce in this section the design we propose to manage real-time events. We start by the model proposed in the RTSJ and we explain the need for an higher abstraction model.

A. The RTSJ Model

In order to generalize the Thread facility of regular Java programs, RTSJ proposes the notion of schedulable object (SO) through the interface Schedulable. A SO is an object which can be scheduled by a scheduler. A suitable context for the execution of such an object is created using scheduling and release parameters attached to each SO. Schedulable is an interface with getter and setter methods to access and modify scheduling parameters (priority and/or importance) (class SchedulingParameters) and release parameters (cost , period, deadline) (class ReleaseParameters). There is also methods to attach the SO to a particular scheduler or to add or remove it to the feasibility analysis.

Two main concrete classes implementing this interface are proposed: RealtimeThread which also extends the class java.lang.Thread, and AsyncEventHandler (AEH) which represents the logic to execute when an associated event, modeled with the class AsyncEvent (AE) is triggered. A RealtimeThread is always associated with one and only one thread, but AsyncEventHandlers can share a thread if a thread pool mechanism is implemented (this is a possibility offered by the specification but this is not mandatory).

We focus this work on the asynchronous events and their handlers which is the RTSJ model to implement event based applications. RTSJ proposes a many-to-many relation (n -n) between events and handlers. Practically, this means that it is possible to associate to an event trigger an unbounded number of handlers and that a given handler can be bounded to several events.

1) AsyncEvent (AE):

This class model an asynchronous event. No release parameters are directly associated with an event, but a method createReleaseParameters() permits to obtain a suitable instance of ReleaseParameters in order to associate it to an handler. The default behavior is to return an AperiodicParameters.

Methods add/removeHandler() permit respectively to add and remove an AEH to the list of associated handlers. The method fire() triggers the event. In practice, it means that all associated handlers are released and start to compete for execution. Methods bindTo() and unbindTo() permit to associate (or disassociate) the event to a kernel-level interruption like a key press, in order to automatize the call of the fire() method.

2) AsyncEventHandler (AEH): An AEH is a SO modeling the logic associated with an event triggering. It so implements the methods described in the Schedulable interface used to set and get the SO real-time properties:

B. Advance Event Handling: the Event Server

Reducing all non periodic traffic to sporadic traffic is too limited. To handle pure aperiodic traffic in real-time system, three solutions exist. The first on is the background scheduling (BS): lowest priorities are reserved for the non periodic traffic. This solution is easily implementable with the AE/AEH model. However, it does not permit to obtain good mean response times for aperiodic handlers. The second solution, the use of task servers, is introduced in [3] response times. A task server is a task with a limited budget and a policy to replenish this budget. The interference of this task has to be known or at least bounded. Then the aperiodic traffic handling is delegated to it. The AE/AEH model is not sufficient to implement task servers. It is possible within the RTSJ to assign common release parameters to a group of SOs. These special release parameters are modeled by the class Processing-GroupParameters (PGP). Unfortunately this behavior is underspecified [START_REF] Burns | Processing group parameters in the real-time specification for java[END_REF]. A contribution to extend the PGP semantic has been led in [START_REF] Wellings | Processing group parameters in the real-time specification for java[END_REF] but this approach relies on modifications on the specification.

The third solution is the use of a slack stealer. The slack stealer rely on an algorithm to compute the slack: the maximal amount of time available at instant t to execute aperiodic tasks at the highest priority without endangering the periodic tasks. It is a special kind of server which use the slack as its capacity. As the time complexity of slack computation algorithms is too high, approximation algorithms are proposed [START_REF] Davis | Scheduling slack time in fixed priority pre-emptive systems[END_REF]. Modified algorithms and a set of classes to write task servers and slack stealer with RTSJ is proposed in [START_REF] Masson | RTSJ Extensions: Event Manager and Feasibility Analyzer[END_REF].

We introduce here the EventServer (ES) entity which regroups both task server and slack stealer approaches. The model to handle aperiodic request is now composed by three entities: AE/AEH/ES.

C. Toward an Event Manager

The aim of this paper is to propose a higher abstraction level to design event handling. Indeed, the ES is not sufficient to model more complex relations between events triggering and handler releases. We want to design a software component able to endorse the responsibility of the event gesture from its happening to the execution of its handler within a server running on a processor. Such an entity can be parameterized by choosing between policy allocations for events on handlers, and for handlers on processors. The first gain for the developer is the ability to use those high level mechanisms together without having to acquire an expertize for all of them. One other utility of a centralization beside a manager is to simplify the end-to-end time-analysis.

III. THE EVENT MANAGER COMPONENT

We describe in this section a new software component we call an Event Manager. This component takes as an input the events and as an output the tasks assigned to processors. It endorses four responsibilities: managing the relations between events triggering and handlers releases, servicing the handlers in assigning them to task servers, allocating the servers on a processor set, and performing a feasibility analysis of the system.

Ë ÙÐ ÖÈÖÓÜÝ 1 Ú ÒØË ÖÚ Ö 1 Ú ÒØÀ Ò Ð Ö 1 Ú ÒØÈÖÓÜÝ 1 Ë ÙÐ ÖÈÖÓÜÝ p Ú ÒØË ÖÚ Ö m Ú ÒØÈÖÓÜÝ k Ú ÒØÀ Ò Ð Ö l E 1 E n P q P 2 P 1
Fig. 1. Distributed-event manager on multiprocessor architectures

A. Relations Between Events and Handlers

In the model presented in the last section, there is no entity aware of the relations between AE, AEH and servers. However, when several AEH are bounded to the same AE, their release model will be the same. And when several handlers are assigned to the same task server, their interference on the other tasks in the system are linked. The first gain having a centralized manager is so to keep knowledge of these relations and to use it for the analysis.

Moreover, with a centralized entity, we can define more complex relations between events and handlers. Such an entity allows us to manage the handlers in a more powerful way than the basic association n -n of the RTSJ model. We can for example imagine a system where a treatments should start only if two distinct events have occurred. Even more complex relations between the events happening can be described using logical operators. The manager can use an internal automaton in which an event happening corresponds to a transition. When the automaton reaches certain states, handlers are released. The logical operators and a language to produce the automaton is described in [START_REF] Curcio | Resource Reclamation using Meta-Events in a Real Time Java System[END_REF] and we will detail them in Section IV-F.

We can note that this model applies with both asynchronous events and sporadic/periodic events. The entity EventProxy designates the manager view of the event. EventHandler designates their handlers and MetaEventAutomaton the automaton.

B. Handlers Service

When the automaton reaches a state which corresponds to the release of an handler, this handler must be added to a server. According to a changeable policy, the manager will choose a server from a pool, or start a new server, and add the handler to its queue. The handler has release and scheduling parameters in order to permit the policy to choose a server, and the server to serve it. A special server can be used to scheduled sporadic tasks as soon as they are released. The servers are modeled by the entity EventServer and the policy by HandlerAllocationPolicy.

C. Processors Allocation

If the application is targeted for multiprocessors architectures and/or distributed environments, a processor must be choose to execute the server. The processors available can be viewed as a resource allocated to the event manager. We can distinguish two kinds of processor: some are reserved for the manager, others are shared with others SO or others event managers.

The theory of real-time multiprocessor scheduling is divided in two main approaches: global scheduling and partitioned scheduling. In the first one, the tasks are allowed to migrate from a processor to another at runtime. Whereas in the last one, the tasks are assigned statically to an unique processor. Once assigned to a processor, each processor schedules its own tasks set independently.

The processors are accessed by the manager through the SchedulerProxy entity. A scheduler proxy can be bounded to a scheduler which control one or several processors. The first case corresponds to a global scheduler and the second either to a local scheduler of a partitioned-based scheduled system or to a mono processor system.

D. Feasibility Analysis

The manager must provide interfaces to statute on the feasibility of the real-time constraints on the handlers and the servers. There is no entity responsible for this role, it is assumed by each component of the manager.

If a SchedulerProxy represents a scheduler reserved for the manager, well known results on feasibility analysis can be reused to decide the feasibility of the server set. However, if the scheduler is shared with other SO, the feasibility can no longer be analyzed by the component. For that purpose, the component must provide a bound on the interference the servers it serve can produce on other SO.

The automaton, which models the dependency relations between the events, can be used to transform the model in an equivalent -in the sense of the feasibility -of the starting system.

In our model, handlers have release and scheduling parameters used to choose the server where it will be executed. Some handlers can have deadline, in that case an admission control has to be performed before choosing the server. To choose the server among the ones which pass the admission control, a policy has to be chosen.

As resumed by Figure 1, a manager (EM) is so composed by a pool of servers (ES), a set of proxies which represent events (EP), a set of handlers (EH), a set of scheduler proxies which represent schedulers (SP), an automaton which describes the relation between EP set and EH set and a policy to assigned EH to ES and ES to SP.

IV. FORMALIZING THE EVENT MANAGER

We have introduced all the elements of our component: the event manager. We will now detail and formalize them using interface declaration, and discuss about the analysis of a system composed with one or several event managers.

A. EventManager (EM)

The EventManager interface has methods to add and remove elements in each set and getter and setter for the automaton and the policies.

For the sake of clarity, we do not detail the remove methods corresponding to add ones and getters corresponding to setters.

B. EventProxy (EP)

An EventProxy is the manager view of an event. It can be the local event itself if the event is local, or associated to a distant event.

Methods bind/unbindTo() permit to connect the proxy with a physical event on the local system or to a distant event. Method fire() triggers the event. Note that there is no method to add or remove handlers since this association is made by the MetaEventAutomaton component of the manager.

p u b l i c i n t e r f a c e E v e n t P r o x y {

void f i r e ( ) ; void bindT o ( S t r i n g h a p p e n i n g ) ; }

C. EventHandler (EH)

An EH is the most simple entity, it represents a logic associated to the EM. It inherits from the interface Servable which represents an object which can be handle by a server, by opposition with a Schedulable (SO). This logic must be wrote in the method handleEvent(). When added to a manager the EH is associated with one server with respect to the required ManagerPolicy. Then EH is enqueued in the server queue when the automaton reaches the appropriate state.

D. EventServer (ES)

An ES is a SO in the RTSJ sense. It maintains a queue of servable which can be sorted by arrival dates (FIFO). It is caracteryzed by a ServicePolicy (Deferrable, Polling, Slack Stealer...). Note that a servable could have release and scheduling parameters, but this is not mandatory. If it has such parameters, the queue can also be sorted by priorities or deadlines... This depends on a QueuePolicy which can be (but not limited to) FixedPriority (FP) or Deadline Monotonic (DM). When the deadline of a servable is reached, its priority can be increased or decreased (a max priority value must have been computed to ensure the feasibility), the job can be dropped... This depends on a DeadlineMissedPolicy. If its WCET is consumed but its execution not completed, the server can cancel it, or let it continue, this depends on a CostOverrunPolicy. Finally, when its period (or minimal interarrival time) is violated, a MITViolationPolicy (like the one of the RTSJ) can be applied. A server also has to provide a method to let know if a given SO can respect its release parameters. We will see in Section IV-G that it can be used by the EventHandlerAllocationPolicy to choose a server to execute a given handler.

E. SchedulerProxy (SP)

A SchedulerProxy is the manager view of a scheduler, which can be either a mono processor scheduler, a scheduler responsible of one processor on a partitioned-based multiprocessor architecture, or a global scheduler. An instance of SP manages the execution of servers on the scheduler it represents, according to a scheduling policy. It also implements a local feasibility algorithm. The feasibility algorithm determines if the known set of server is a feasible system. This feasibility analysis will also depends on the scheduling policy of the SP. The scheduler represented by the SP can be reserved for the manager, but it can also be shared with others SO or others managers. Then the method isFeasible() only concern the set of server, and an additional method getMaxInterference() is needed to permit the feasibility analysis.

F. MetaEventAutomaton (MEA)

The MEA is the automaton which controls an internal state that records all past fired event. The handler is activated only when the conditions described in the meta-event description are satisfied.

The relations between the event proxies are described using a logical expression. This expression uses a set of logical operators (AND, OR, THEN, NEXT, NOT, TIMES). The automaton is produced either using a description language (*.acf) and then compiled (rtmec) with a compil-type argument set to local for single node multiprocessor and set to distributed for distributed multiprocessor manager 1 or using the EventManager as a MEA factory to create a MEA corresponding to the expression expr (see the EventManager idl description). Figure 2 presents a MetaEvent example.

G. ManagerPolicy (MP)

The MP has two distinct roles: to manage the assignments of the handlers on the servers, and to manage the assignments of the ES on the SL. The first is handled by an HandlerAlloca-tionPolicy (HAP) and the second by a ServerAllocationPolicy (SAP).

1) HandlerAllocationPolicy (HAP):

There is several possibilities to assign the handlers on the servers. We can select the appropriate server because of its policy, of its priority, of its current charge, of the response time it can warranty at instant t, ... The role of an HAP is to choose from the set of server in the manager the one to serve a given handler, or to start a new server. The admission control method in the interface EventServer can be used to arbitrate the decision. The pool of server can also be viewed as a given limited resource, and use in a similar way than a pool of processors in multiprocessor scheduling theory. Then several policy can be applied. The placement issue can then be reduced to the Bin-Packing problem which has been largely studied. Many heuristics exist to solve it [START_REF] Coffman | Approximation algorithms for bin packing: a survey[END_REF]. The most classical we can cite are First-Fit, and Worst-Fit. First-Fit places a new object in the leftmost bin that still has room while Worst-Fit places a new object in the emptiest existing bin. First-Fit reduces the number of used servers and Worst-Fit reduces the load of each server (it uses all the server set). E v e n t S e r v e r a s s i g n E v e n t H a n d l e r ( E ve nt H a ndl e r eh ) ; } enum A l l o c a t i o n P o l i c y { F i r s t F i t , W o r s t F i t ; } 2) ServerAllocationPolicy (SAP): The role of the SAP is to choose a scheduler proxy for a given server. Then the server will be scheduled according to the scheduling policy of the proxy. There is several way to choose the proxy: again, we face a Bin-Packing problem, and well known heuristic can be proposed: First-Fit and Worst-Fit.

V. CONCLUSIONS AND FUTURE WORKS

We have presented the existing model of the RTSJ to represent asynchronous events, its limitations, and the need to extend it to allows the programming of a higher level handling of event. We had justify the need and the advantages of setting a centralized entity, the EventManager, which has a global view of the system from the event happening to the release on a processor of its handlers within a server. We proposed interfaces to implement this manager and justified our choices. It is important to note that each part of component proposed in the paper is implementable and implemented, except the global scheduling which is a work in progress.

We also want to propose, as soon as possible, all these implementations in a well designed package with runnable examples.

This will permits us to conduct extensive measures in order to validate the usability of our software component for hard real-time applications.

As part of future work, we want to study the possibility to introduce temporal behavior in the meta event automaton. This could allow us to deal with release parameters violation (like the minimal inter-arrival time) before the release of the handler, which could enhanced the performance of the component.

p u b l i c i n t e r f a c

  e E ventManager{ void a d d E v e n t P r o x y ( ) ; void a d d E v e n t S e r v e r ( ) ; void a d d E v e n t H a n d l e r ( ) ; void a d d E v e n t S e r v e r ( ) ; void a d d S c h e d u l i n g L o c a t i o n ( b oolean r e s e r v e d ) ; void s e t M e t a E v e n t A u t o m a t o n ( MetaEventAutomaton e , Set<E v e n t H a n d l e r > h a n d l e r s ) ; void s e t M e t a E v e n t A u t o m a t o n ( S t r i n g m e t a E v e n t D e s c r i p t i o n , Set<E v e n t H a n d l e r > h a n d l e r s ) ; void s e t M a n a g e r P o l i c y ( M a n a g e r P o l i c y mp) ; void s e t M a n a g e r P o l i c y ( H a n d l e r A l l o c a t i o n P o l i c y hap , S e r v e r A l l o c a t i o n p o l i c y s ap ) ; }

p u b l

  i c i n t e r f a c e E v e n t H a n d l e r : : S e r v a b l e { void h a n d l e E v e n t ( ) ; } p u b l i c i n t e r f a c e S e r v a b l e { void s e t R e l e a s e P a r a m e t e r s ( R e l e a s e P a r a m e t e r s r p ) ; void s e t S c h e d u l i n g P a r a m e t e r s ( S c h e d u l i n g P a r a m e t e r s sp ) ; }

p u b l i c i n t e r f a c

  e E v e n t S e r v e r { void a d d E v e n t H a n d l e r ( e v e n t H a n d l e r eh ) ; void s e t S e r v i c e P o l i c y ( S e r v i c e P o l i c y sp ) ; void s e t M I T V i o l a t i o n P o l i c y ( M I T V i o l a t i o n P o l i c y mvp ) ; void s e t D e a d l i n e M i s s e d P o l i c y ( D e a d l i n e M i s s e d P o l i c y dmp ) ; void s e t C o s t O v e r r u n P o l i c y ( C o s t O v e r r u n P o l i c y cop ) ; void s e t Q u e u e P o l i c y ( Q ue ue P ol i c y qp ) ; b oolean i s A d m i s s i b l e ( S c h e d u l a b l e s ) ; } enum S e r v i c e P o l i c y { POLLING , DEFERRABLE , SLACK STEALER ; } enum Q u e u e P o l i c y { FIFO ,DM, FP ; } enum D e a d l i n e M i s s e d P o l i c y { DROP, INCREASE , DECREASE , IGNORE ; } enum C o s t O v e r r u n P o l i c y { DROP, INCREASE , DECREASE , IGNORE ; } enum M I T V i o l a t i o n P o l i c y { REPLACE , IGNORE ,ADD; }

p u b l

  i c i n t e r f a c e S c h e d u l i n g L o c a t i o n { void a d d E v e n t S e r v e r ( E v e n t S e r v e r e s ) ; b oolean i s F e a s i b l e ( ) ; I n t e r f e r e n c e g e t M a x I n t e r f e r e n c e ( ) ; S c h e d u l i n g P o l i c y s e t S c h e d u l i n g P o l i c y ( ) ; b oolean i s R e s e r v e d ( ) ; } enum S c h e d u l i n g P o l i c y { RM,DM, EDF ; } p u b l i c c l a s s I n t e r f e r e n c e { R e l a t i v e T i m e p e r i o d ; R e l a t i v e T i m e wcet ; }

  1 java -jar rtmec.jar -compil-type={local,distributed} description.acf

Fig. 2 .

 2 Fig. 2. Urgency Stop Automaton Example: In this example the MetaEvent describes the relations between four events in a control application for a robot. The SensorTouch events and SensorLights relations indicate the mandatory stop condition for the robot.

p u b l

  i c i n t e r f a c e M e t a S c h e d u l i n g P o l i c y { void s e t H a n d l e r A l l o c a t i o n P o l i c y ( H a n d l e r A l l o c a t i o n P o l i c y hap ) ; void s e t S e r v e r A l l o c a t i o n P o l i c y ( S e r v e r A l l o c a t i o n P o l i c y s ap ) ; }

  p u b l i c i n t e r f a c e E v e n t S e r v e r P o l i c y { A l l o c a t i o n P o l i c y g e t P o l i c y ( ) ;

p u b l

  i c i n t e r f a c e S c h e d u l i n g L o c a t i o n P o l i c y { A l l o c a t i o n P o l i c y g e t P o l i c y ( ) ; S c h e d u l e r P r o x y a s s i g n E v e n t S e r v e r ( E v e n t S e r v e r eh ) ; }


Guillaume Blin
email: gblin@univ-mlv.fr

Sylvie Hamel
email: hamelsyl@iro.umontreal.ca

Stéphane Vialette
email: vialette@univ-mlv.fr

Comparing RNA structures with biologically relevant operations cannot be done without strong combinatorial restrictions

come

Comparing RNA structures with biologically relevant operations cannot be done without strong combinatorial restrictions

Introduction

In computational biology, comparison of RNA molecules has recently attracted a lot of interest due to the rapidly increasing amount of known RNA molecules, especially non-coding RNAs. Very often, arc-annotated sequences, originally introduced in [START_REF] Evans | Algorithms and Complexity for Annotated Sequences Analysis[END_REF], are used to represent RNA structures. An arc-annotated sequence is a sequence over a given alphabet together with additional structural information specified by arcs connecting pairs of positions. The arcs determine the way the sequence folds into a three-dimensional space.

The problem of computing an edit distance between two arc-annotated sequences was introduced in [START_REF] Evans | Algorithms and Complexity for Annotated Sequences Analysis[END_REF] with a model that used only three edit operations (deletion, insertion and substitution) either on single letters (letters in the sequence with no incident arc) or pairs of letters (letters connected by an arc). In this model, the two letters of an arc are never considered separately, and hence the problem of computing the edit distance between two arc-annotated sequences becomes equivalent (when no pair of arcs are crossing) to the tree edit distance problem, that can be solved in polynomial-time [START_REF] Zhang | Simple fast algorithms for the editing distance between trees and related problems[END_REF].

To account for other possible RNA structural evolutionary events, new edit operations, such as creation, deletion or modification of arcs between pairs of letters, were introduced in [START_REF] Jiang | A general edit distance between RNA structures[END_REF] at the cost of computational tractability. Indeed, it has been shown in [START_REF] Blin | Extending the hardness of rna secondary structu[END_REF] that in case of non-crossing arcs, the problem of computing the edit distance between two arc-annotated sequences under this model is NP-hard. Playing the game of applying constraints either on the legal edit operations or on the allowed alignments, several papers have shed new light on the borderline between tractability and intractability [START_REF] Guignon | An edit distance between rna stem-loops[END_REF][START_REF] Blin | Alignment of RNA structures[END_REF]. Of particular importance, in [START_REF] Guignon | An edit distance between rna stem-loops[END_REF], the authors introduced the notion of conservative edit distance and mapping between two RNA stem-loops in order to design a polynomial-time algorithm for comparing general secondary RNA structures using the full set of biological edit operations introduced in [START_REF] Jiang | A general edit distance between RNA structures[END_REF]. This algorithm is based on a decomposition in stem-loop-like substructures that are pairwised compared and used to compare complete RNA secondary structures. As mentionned in [START_REF] Guignon | An edit distance between rna stem-loops[END_REF], whereas in the very restrictive case of conservative distance and mapping, the computation of the general edit distance is polynomial-time solvable, it is not known if the general, i.e., not conservative, edit distance between two stem-loops can be also computed in polynomial-time.

In this paper, we will show that this strong combinatorial restriction is actually necessary for the problem to become polynomial since it is NP-hard in the general case. Despite the fact that this result may be considered as purely theoretical, it proves that comparing two RNA structures using a full set of biologically relevant edit operations cannot be done without strong combinatorial restrictions.

Preliminaries

Given a finite alphabet Σ, an arc-annotated sequence is formally defined by a pair (S, P ), where S is a string of Σ * and P is a set of arcs connecting pairs of letters of S. In reference to RNA structures, letters are called bases. Bases with no incident arc are called single bases. In an arc-annotated sequence, two arcs (i 1 , j 1 ) and (i 2 , j 2 ) are crossing, if i 1 < i 2 < j 1 < j 2 or i 2 < i 1 < j 2 < j 1 . An arc (i 1 , j 1 ) is embedded into another arc (i 2 , j 2 ) if i 2 < i 1 < j 1 < j 2 . Evans [START_REF] Evans | Algorithms and Complexity for Annotated Sequences Analysis[END_REF] (see [START_REF] Guignon | An edit distance between rna stem-loops[END_REF] for extensions) introduced five different levels of arc structure: Unlimited -no restriction at all; Crossing -there is no base incident to more than one arc; Nested -there is no base incident to more than one arc and no two arcs are crossing; Stem -there is no base incident to more than one arc and given any two arcs, one is embedded into the other; Plain -there is no arc. There is an obvious inclusion relation between those levels: Plain ⊂ Stem ⊂ Nested ⊂ Crossing ⊂ Unlimited. An arc-annotated sequence (S 1 , P 1 ) is said to occur in another arc-annotated sequence (S 2 , P 2 ) if one can obtain the former from the latter by repeatedly deleting bases (deleting a base that is incident to an arc results in the deletion of the arc).

Among the many paradigms referring to arc-annotated sequences (see [START_REF] Blin | Alignment of RNA structures[END_REF] for more details) we focus in this article on the Longest Arc-Preserving Common Subsequence (Lapcs for short) [START_REF] Evans | Algorithms and Complexity for Annotated Sequences Analysis[END_REF][START_REF] Jiang | The longest common subsequence problem for arc-annotated sequences[END_REF][START_REF] Lin | The longest common subsequence problem for sequences with nested arc annotations[END_REF] and the general edit distance (Edit for short) [START_REF] Jiang | A general edit distance between RNA structures[END_REF][START_REF] Blin | Comparing rna structures: towards an intermediate model between the edit and the lapcs problems[END_REF]. Indeed, as shown in [START_REF] Blin | Alignment of RNA structures[END_REF], those two paradigms are quite related since the Lapcs problem is a special case of Edit when considering the complete set of edit operations defined in [START_REF] Jiang | A general edit distance between RNA structures[END_REF]. Therefore, the hardness results for Lapcs stands for Edit.

Formally, the Longest Arc-Preserving Common Subsequence problem is defined as follows: given two arc-annotated sequences (S 1 , P 1 ) and (S 2 , P 2 ), find the longest -in terms of sequence length -common arc-annotated subsequence that occurs in both (S 1 , P 1 ) and (S 2 , P 2 ). It has been shown in [START_REF] Jiang | A general edit distance between RNA structures[END_REF] that the Lapcs problem is NP-hard even for Nested structures, i.e., Lapcs(Nested, Nested). Still focussing on Nested structures, Alber et al. [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF] proved that the Lapcs(Nested, Nested) problem is solvable in O(3 k |Σ| k kn) time, where n is the maximum length of the two sequences and k is the length of the common subsequence searched for.

While Lapcs(Stem, Stem) might appear at first sight as yet another refinement of Lapcs, we emphasize here that our hardness result implies hardness of Edit(Stem. Stem) [START_REF] Blin | Alignment of RNA structures[END_REF]. This latter problem has been shown to be of particular interest to compare complete RNA secondary structures [START_REF] Guignon | An edit distance between rna stem-loops[END_REF]. Another consequence of our result is that further research on comparing RNA structures with a full set of edit operations aiming at polynomial-time solutions will have to introduce strong combinatorial restrictions.

Comparing RNA Stem-Loops is NP-complete

In this section, we prove that Lapcs over stem-loops (Lapcs(Stem, Stem)) is NP-complete (in Theorem 1); therefore answering an open question of [START_REF] Guignon | An edit distance between rna stem-loops[END_REF]. This last result induces the NP-hardness of Edit over stem-loops.

Theorem 1. Lapcs(Stem, Stem) is NP-complete.
Corollary 1. Comparing RNA structures with a full set of biologically relevant edit operations cannot be done without introducing strong combinatorial restrictions.

In the following, we consider the decision version of the problem which corresponds to deciding if there exists an arc-preserving common subsequence of length greater or equal to a given parameter k ′ .

It is easy to see that the Lapcs problem is in NP. In order to prove its NP-hardness, we define a reduction from the NP-complete 3SAT problem [START_REF] Garey | Computers and Intractability: a guide to the theory of NP-completeness[END_REF] which is defined as follows: Given a collection C q = {c 1 , c 2 , . . . , c q } of q clauses, where each clause consists of a set of 3 literals (representing the disjunction of those literals) over a finite set of n boolean variables V n = {x 1 , x 2 , . . . , x n }, is there an assignment of truth values to each variable of V n s.t. at least one of the literals in each clause is true?

Let (C q , V n ) be any instance of the 3SAT problem s.t. C q = {c 1 , c 2 , . . . , c q } and V n = {x 1 , x 2 , . . . , x n }. For convenience, let L j i denote the j th literal of the i th clause (i.e. c i ) of C q . In the following, given a sequence S over an alphabet Σ, let χ(i, c, S) denote the i th occurrence of the letter c in S.

We build two arc-annotated sequences (S 1 , P 1 ) and (S 2 , P 2 ) as follows. An illustration of a full example is given in Figures 1 and2, where n = 4 and q = 3. For readability reasons, the arc-annotated sequences resulting from the construction have been split into several parts and a schematic overview of the overall placement of each part is provided.

Let

S 1 = C 1 q W q C 1 q-1 ...C 1 2 W 2 C 1 1 W 1 S 1 M V 1 P 1 1 V 2 P 1 2 ...P 1 q-1 V q P 1 q and S 2 = C 2 q W q C 2 q-1 ...C 2 2 W 2 C 2 1 W 1 S 2 M V 1 P 2 1 V 2 P 2 2 ...P 2 q-1 V q P 2 q s.t. for all 1 ≤ i ≤ q, 1 ≤ k ≤ n, -C 1 i = R 3 i Q i R 2 i Q i X 1 1 X 1 2 ... X 1 n Q i R 2 i Q i R 1 i with X 1 k = x k s j x k if x k = L j i or x k = L j i ; X 1 k = x k x k otherwise; -P 1 i = Q q+i Q q+i R 3 q+i X 1 n ...X 1 n 2 +1 R 2 q+i X 1 n 2 ...X 1 1 R 1 q+i Q q+i Q q+i s.t. X 1 k = x k x k ; -C 2 i = X 2 1 ...X 2 n R 3 i Q i X 2 1 ... X 2 n 2 R 2 i X 2 n 2 +1 ...X 2 1 Q i R 1 i X 2 1 ...X 2 n s.t. ∀1 ≤ j ≤ 3, χ(j, X 2 k , C 2 i ) = x k x k s j (resp. s j x k x k ) if x k = L j i (resp. x k = L j i ); χ(j, X 2 k , C 2 i ) = x k x k otherwise; -P 2 i = X 2 n ...X 2 1 R 1 q+i Q q+i X 2 n ...X 2 n 2 +1 R 2 q+i X 2 n 2 ...X 2 1 Q q+i R 3 q+i X 2 n ...X 2 1 with X 2 k = x k x k . Moreover, let S 1 M = x 1 x 1 x 2 x 2 ...x n x n and S 2 M = x 1 x 1 x 2 x 2 ...x n x n .
Notice that, by construction, there is only one occurrence of each {s 1 , s 2 , s 3 } in C 2 i . For all 1 ≤ i ≤ q, let Q i (resp. Q q+i ) be a segment of n + 1 symbols y i (resp. y q+i ). Moreover, for all 1 ≤ i ≤ q, let W i (resp. V i ) be a segment of 20(max{q, n} 2 ) symbols w i (resp. v i ). Let us now define P 1 and P 2 .

For all 1 ≤ i ≤ q -1, (1) add an arc in

P 1 between χ(1, x k , C 1 i ) (resp. χ(1, x k , C 1 i )) and χ(1, x k , P 1 i+1 ) (resp. χ(1, x k , P 1 i+1 )), ∀1 ≤ k ≤ n (see Figure 1.d and 2.b); (2) add an arc in P 2 between χ(j, x k , C 2 i ) (resp. χ(j, x k , C 2 i )) and χ((4 -j), x k , P 2 i ) (resp. χ((4 -j), x k , P 2 i )), ∀1 ≤ k ≤ n (see Figure 1.c, 2.

a and 2.c); (3) add an arc in

P 2 between χ(1, R j i , C 2 i ) and χ(1, R j q+i , P 2 i ), ∀1 ≤ j ≤ 3 (see Figure 1.c, 2.

a and 2.c).

Clearly, this construction can be achieved in polynomial-time, and yields to sequences (S 1 , P 1 ) and (S 2 , P 2 ) that are both of type Stem. We now give an intuitive description of the different elements of this construction.

Each clause c i ∈ C q is represented by a pair (C 1 i , C 2 i ) of sequences. The sequence C 2 i is composed of three subsequences representing a selection mechanism of one of the three literals of c i . The pair (S 1 M , S 2 M ) of sequences is a control mechanism that will guarantee that a variable x k cannot be true and false simultaneously. Finally, for each clause c i ∈ C q , the pair (P 1 i , P 2 i ) of sequences is a propagation mechanism which aim is to propagate the selection of the assignment (i.e. true or false) of any literal x k all over C q . Notice that all the previous intuitive notions will be detailed and clarified afterwards.

In the rest of this article, we will refer to any such construction as a snailconstruction. In order to complete the instance of the Lapcs(Stem, Stem) problem, we define the parameter k ′ = 40q(max{q, n} 2 ) + 6qn + 8q + n which corresponds to the desired length of the solution. In the following, let (S 1 , P 1 ) and (S 2 , P 2 ) denote the arc-annotated sequences obtained by a snail-construction. We will denote S d the set of symbols deleted in a solution of Lapcs problem on (S 1 , P 1 ) and (S 2 , P 2 ) (i.e. the symbols that do not belong to the common subsequence).

We start the proof that the reduction from 3SAT to Lapcs(Stem, Stem) is correct by giving some properties about any optimal solution. Lemma 1. In any optimal solution of Lapcs problem on (S 1 , P 1 ) and (S 2 , P 2 ), at least one symbol incident to any arc would be deleted. Moreover, all the symbols of V i and W i , for 1 ≤ i ≤ q, will not be deleted.

Proof. By contradiction, let us suppose that there exist at least one arc s.t. the two symbols incident to this last are not deleted in a solution of Lapcs problem on (S 1 , P 1 ) and (S 2 , P 2 ). Then, by construction, it induces that at least one complete sequence V j or W j , for a given 1 ≤ j ≤ q, has been deleted. Since they have the same length, we will consider w.l.o.g. afterwards that V i has been deleted. Therefore, since S 1 is, by construction, smaller than S 2 the length of this optimal solution is at most

|S 1 | -|V j | = q i=1 (|C 1 i | + |P 1 i | + |V i | + |W i |) + |S 1 M |-|V j | = q i=1
((6n+11)+(6n+7)+(20(max{q, n} 2 ))+(20(max{q, n} 2 )))+ 2n -(20(max{q, n} 2 )) = q[12n + 18 + 40(max{q, n} 2 )] + 2n -(20(max{q, n} 2 )). Then, in order for this solution to be optimal, one should have q[12n + 18 + 40(max{q, n} 2 )] + 2n -(20(max{q, n} 2 )) ≥ 40q(max{q, n} 2 ) + 6qn + 8q + n. This can be reduced to 6qn + 10q -20(max{q, n} 2 ) + n ≥ 0. But, one can easily check that for any n ≥ 3 (which is always the case in 3SAT instances), this is not true; a contradiction. Lemma 2. Any optimal solution of Lapcs problem on (S 1 , P 1 ) and (S 2 , P 2 ) is of length 40q(max{q, n} 2 ) + 6qn + 8q + n.

Proof. By construction, in S 1 there is (1) ∀1 ≤ i ≤ n, 2q + 1 occurrences of x i (resp. x i ); (2) ∀1 ≤ i ≤ q, 4 occurrences of Q i (resp. Q q+i ); (3) ∀1 ≤ i ≤ q, 1 occurrence of each {R 1 i , R 2 q+i , R 3 i , R 1 q+i , R 3 q+i , W i , V i , s 1 , s 2 , s 3 }; (4) ∀1 ≤ i ≤ q, 2 occurrences of R 2 i . Whereas, in S 2 , there is (1) ∀1 ≤ i ≤ n, 6q + 1 occurrences of x i (resp. x i ); (2) ∀1 ≤ i ≤ q, 2 occurrences of Q i (resp. Q q+i ); (3) ∀1 ≤ i ≤ q, 1 occurrence of each {R 1 i , R 2 i , R 3 i , R 1 q+i , R 2 q+i , R 3 q+i , W i , V i , s 1 , s 2 , s 3 }.
Therefore, in any optimal solution there may be only [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF]

∀1 ≤ i ≤ n, 2q + 1 occurrences of x i (resp. x i ); (2) ∀1 ≤ i ≤ q, 2 occurrences of Q i (resp. Q q+i ); (3) ∀1 ≤ i ≤ q, 1 occurrence of each {R 1 i , R 2 i , R 3 i , R 1 q+i , R 2 q+i , R 3
q+i , W i , V i , s 1 , s 2 , s 3 }.

Fig. 1 .

 1 Fig. 1. Considering Cq = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x4) ∧ (x2 ∨ x3 ∨ x4). For readability, all the arcs have not been drawn, consecutive arcs are representing by a unique arc with lines for endpoints. Symbols over a grey background may be deleted to obtain an optimal LAPCS. a) A schematic view of the overall arrangement of the components of the two a.a. sequences. b) Description of S 1 M , S 2 M , P 1 1 , P 2 1 and the corresponding arcs in P1. c) Description of C 1 1 , C 2 1 , P 1 1 , P 2 1 and the corresponding arcs in P2. d) Description of C 1 1 , C 2 1 , P 1 2 , P 2 2 and the corresponding arcs in P1.

Fig. 2 .

 2 Fig. 2. Considering Cq = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x4) ∧ (x2 ∨ x3 ∨ x4). For readability all the arcs have not been drawn, consecutive arcs are representing by a unique arc with lines for endpoints. Symbols over a grey background may be deleted to obtain an optimal LAPCS. a) Description of C 1 2 , C 2 2 , P 1 2 , P 2 2 and the corresponding arcs in P2. c) Description of C 1 2 , C 2 2 , P 1 3 , P 2 3 and the corresponding arcs in P1. d) Description of C 1 3 , C 2 3 , P 1 3 , P 2 3 and the corresponding arcs in P2.

More precisely, by Lemma 1, and since, by construction, there is an arc in P 2 between χ(1, R j i , C 2 i ) and χ(1, R j q+i , P 2 i ), ∀j ∈ {1, 2, 3}, in any optimal solution, ∀1 ≤ i ≤ q, only half of the {R 1 i , R 2 i , R 3 i , R 1 q+i , R 2 q+i , R 3 q+i } may be conserved. Moreover, any x i (resp. x i ) of S 1 except in C 1 q , is linked by an arc to another x i (resp. x i ), therefore by Lemma 1, in any optimal solution, ∀1 ≤ i ≤ q -1, only half of the occurrences of x i (resp. x i ) may be conserved.

Finally, in any optimal solution, only half of the occurrences of {x i , x i } and one over {s 1 , s 2 , s 3 } in C 1 q and S 1 M may be conserved. Indeed, by construction, if this is not the case in C 1 q (resp. S 1 M ), it implies that at least one complete sequence Q q (resp. V 1 or W 1 ) is totally deleted -which is not optimal since it is of length n + 1 (resp. 20(max{q, n} 2 )).

On the whole, the maximal total length of any solution is thus equal to 40q(max{q, n} 2 ) + 6qn + 8q + n. Moreover, this solution is composed of (1)

Lemma 3. In any optimal solution of Lapcs problem on (S 1 , P 1 ) and

M ). By Lemma 1, at least one symbol incident to any arc is deleted. Therefore, ∀1 ≤ k ≤ n only one of {x k , x k } may be conserved between C 1 1 and C 2 1 .

Let us suppose that for a given 1 ≤ k ≤ n, χ(1, x k , S 1 M ) is deleted. According to the proof of Lemma 2, in any optimal solution, ∀1 ≤ k ≤ n exactly one of {x k , x k } has to be deleted. Then χ(1, x k , P 1 1 ) is deleted whereas χ(1, x k , P 1 1 ) is conserved.

By construction, in P 2 1 , since according to the proof of Lemma 2, both occurrences of

Let us first consider that {R 1 1 , R )), in order for χ(1, x k , P 1 1 ) to be conserved, one has to conserved χ(3, x k , P 2 1 ). Thus, by Lemma 1, χ(1, x k , C 2 1 ) has to be deleted and, according to the proof of Lemma 2, χ(1, x k , C 2 1 ) has to be conserved. Let us now consider that {R 1 1 , R 3 1 , R 2 q+1 } are conserved. By a similar reasoning, one can check that the only solution is to conserve, ∀1 ≤ k ≤ n, the second occurrence of any x k or x k in C 2 1 (resp. P 2 1 ) -i.e. the occurrences appearing between

) and χ(2, Q q+1 , P 2 1 )). Since by construction, there is an arc between χ(2, x k , C 2 1 ) (resp. χ(2, x k , C 2 1 )) and χ(2, x k , P 2 1 ) (resp. χ(2, x k , P 2 1 )), in order to χ(1, x k , P 1 1 ) to be conserved, one has to conserved χ(2, x k , P 2 1 ). Thus, by Lemma 1, χ(2, x k , C 2 1 ) has to be deleted and, according to the proof of Lemma 2, χ(2, x k , C 2 1 ) has to be conserved. Finally, let us consider that {R 2 1 , R )), in order to χ(1, x k , P 1 1 ) to be conserved, one has to conserved χ(1, x k , P 2 1 ). Thus, by Lemma 1, χ(3, x k , C 2 1 ) has to be deleted and, according to the proof of Lemma 2, χ(3, x k , C 2 1 ) has to be conserved. Therefore, in the three cases, if for a given 1

). It is easy to see that, by a similar reasoning, if for a given 1

). With a similar reasoning, by reccurence, since,

) is deleted. And therefore, with similar arguments, χ(1, x k , C 1 i+1 ) is conserved. Once more, it is easy to see that this result still holds if χ(1, x k , C 1 i ) is conserved.

Theorem 2. Given an instance of the problem 3SAT with n variables and q clauses, there exists a satisfying truth assignment iff the Lapcs of (S 1 , P 1 ) and (S 2 , P 2 ) is of length k ′ = 40q(max{q, n} 2 ) + 6qn + 8q + n.

Proof. (⇒) An optimal solution for C q = (x 1 ∨x 2 ∨x 3 )∧(x 1 ∨x 2 ∨x 4 )∧(x 2 ∨x 3 ∨x 4 ) -i.e. x 1 = x 3 = true and x 2 = x 4 = f alse -is illustrated in Figures 1 and2 where any symbol over a grey background have to be deleted. Suppose we have a solution of 3SAT, that is an assignment of each variable of V n satisfying C q .

Let us first list all the symbols to delete in 2.c); Let us now list all the symbols in S 2 to be deleted.

M ). For each L j i satisfying c i with the biggest index j with 1

By construction, the natural order of the symbols of S 1 and S 2 allows the corresponding set of undeleted symbols to be conserved in a common arc-preserving common subsequence between (S 1 , P 1 ) and (S 2 , P 2 ). Let us now prove that the length of this last is k ′ . One can easily check that this solution is composed of ∀1 ≤ k ≤ n, (1) 2q + 1 occurrences of either x k or x k , (2) ∀1 ≤ i ≤ q, 2 occurrences of Q i and Q q+i , (3) ∀1 ≤ i ≤ q, 1 occurrence of each {W i , V i } and either s 1 , s 2 or s 3 and (4) ∀1 ≤ i ≤ q, R j1 i , R j2 i , R j3 q+i s.t. {j 1 , j 2 , j 3 } = {1, 2, 3}. Thus, the length of the solution is 40q(max{q, n} 2 ) + 6qn + 8q + n.

(⇐) Suppose we have an optimal solution -i.e. a set of symbols S d to delete -for Lapcs of (S 1 , P 1 ) and (S 2 , P 2 ). Let us define the truth assignment of

By construction, if L j i = x k (resp. x k ) then in C 1 i , s j appears between x k and x k whereas in C 2 j it appears after x k (resp. before

. Therefore, we can ensure that one cannot obtain L j i and L j ′ i ′ being true whereas L j i = L j ′ i ′ (that is a variable cannot be simultaneously true and false). By Lemma 2, we can ensure that for any 1 ≤ i ≤ q exactly one of {s 1 , s 2 , s 3 } is conserved in C 1 i . Therefore, for any clause c i at least one of its literal is set to true. This ensures that our solution is a solution of 3SAT.

Proof. We use a straightforward brute-force algorithm for arc-annotated sequences [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF]: (i) generate all possible sequences of length k with all possible Stem arc annotations, and (ii) for each of these arc-annotated candidate sequences, check whether or not it occurs as a pattern in both S 1 and S 2 .

At the heart of this approach is the fact that it can be decided in O(n k) time whether or not this sequence occurs as an arc-preserving common subsequence [START_REF] Gramm | Pattern matching for arc-annotated sequences[END_REF]. It is easily seen that the above algorithm reduces to O(2 k-1 |Σ| k km) time for Lapcs(Stem, Stem). Indeed, there exist |Σ| k sequences of length k and hence, for a given sequence of length k, there exist k 2i different arc-annotations with i arcs. Therefore, there exist ⌊k/2⌋ i=0 k 2i = 2 k-1 arc-annotations of a given sequence of length k.

Future work

From a computational biology point of view, especially for comparing stems, one may, however, be mostly interested in the case k (length of the common subsequence searched) might not be assumed too small compared to n. A first approach is provided in [START_REF] Alber | Computing the similarity of two sequences with nested arc annotations[END_REF] where it is proved that, given two sequences of length at most n and nested arc structure, an arc-preserving common subsequence can be determined (if it exists) in O(3.31 k1+k2 n) time; obtained by deleting (together with corresponding arcs) k 1 letters from the first and k 2 letters from the second sequence. Improving the running time of the parameterization in case of stem arc structures appears to be a promising line of research.