E Anceaume

Y Busnel
email: yann.busnel@univ-nantes.fr

A Distributed Information Divergence Estimation over Data Streams Emmanuelle Anceaume and Yann Busnel

Abstract-In this paper, we consider the setting of large scale distributed systems, in which each node needs to quickly process a huge amount of data received in the form of a stream that may have been tampered with by an adversary. In this situation, a fundamental problem is how to detect and quantify the amount of work performed by the adversary. To address this issue, we propose a novel algorithm AnKLe for estimating the Kullback-Leibler divergence of an observed stream compared with the expected one. AnKLe combines sampling techniques and information-theoretic methods. It is very efficient, both in terms of space and time complexities, and requires only a single pass over the data stream. We show that AnKLe is an (ε, δ)-approximation algorithm with a space complexity

Õ 1 ε + 1 ε 2
bits in "most" cases, and

Õ 1 ε + n-ε -1 ε 2
otherwise, where n is the number of distinct data items in a stream. Moreover, we propose a distributed version of AnKLe that requires at most O (rℓ (log n +1))bits of communication between the ℓ participating nodes, where r is number of rounds of the algorithm. Experimental results show that the estimation provided by AnKLe remains accurate even for different adversarial settings for which the quality of other methods dramatically decreases.

Index Terms-Data Stream; Kullback-Leibler Divergence; Randomized approximation algorithm; Byzantine Adversary; Performance Analysis

1I NTRODUCTION

The main objective of this paper is the online estimation of the similarity between observed data streams and expected (i.e. idealized) ones in order to detect in real time the presence of intrusions in network traffic. More precisely, we propose a distributed algorithm that approximates with guaranteed error bounds in a single pass and with both a small amount of storage memory and processing capacity, the relative entropy between massive and high frequency distributed sequences of data. This works perfectly fits the IP network traffic context, however it could be applied to any other data issued from distributed applications such as sensors readings. The problem of detecting changes in a data stream is similar to the problem of identifying patterns that do not conform to the expected behavior, which has been an active area of research for many decades. A comprehensive survey of these techniques, their advantages and their drawbacks is given in [START_REF] Chandola | Anomaly detection: A survey[END_REF]. A common feature of these techniques is their space complexity and their computational cost, as they rely on full space algorithms for analyzing their data.

Given our settings -the real time monitoring of network traffic with little capacities in terms of storage and processing -relying on full space algorithms for analyzing input data is not feasible. In contrast, two main approaches exist to monitor in real time massive data streams. The first one consists in regularly sampling the input streams so that only a limited amount of data items is locally kept [START_REF] Subhabrata | Sketch-based change detection: Methods, evaluation, and applications[END_REF], [START_REF] Karamcheti | Detecting malicious network traffic using inverse distribution of packet contents[END_REF], [START_REF] Lakhina | Mining anomalies using traffic feature distributions[END_REF]. This allows to exactly compute functions on these samples. However, accuracy of this computation fully depends on the volume of data that has been sampled and their locations in the stream. Worse, an adversary may easily take advantage of the sampling policy to hide its attacks among packets that are not sampled, or in a way that prevents its "malicious" packets to be correlated. In contrast, the streaming approach consists in scanning each piece of data of the input stream on the fly, and in locally keeping only compact synopses or sketches that contain the most important information about data items. This approach enables to derive some data streams statistic with guaranteed error bounds without making any assumptions on the order in which data items are received at nodes (i.e., data items ordering can be manipulated by an omnipotent adversary [START_REF] Anceaume | Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes[END_REF]). Most of the research done so far with this approach has focused on computing functions or statistic measures with error ε using poly(1/ε, log n) space where n is the domain size of the data items. These include the computation of the number of different data items in a given stream [START_REF] Bar-Yossef | Counting distinct elements in a data stream[END_REF], [START_REF] Flajolet | Probabilistic counting algorithms for data base applications[END_REF], [START_REF] Kane | An optimal algorithm for the distinct element problem[END_REF], the frequency moments [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF], the most frequent data items [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF], [START_REF] Charikar | Finding frequent items in data streams[END_REF], or the entropy of the stream [START_REF] Chakrabarti | A near-optimal algorithm for computing the entropy of a stream[END_REF], [START_REF] Lall | Data streaming algorithms for estimating entropy of network traffic[END_REF]. Note that in [START_REF] Guha | Sketching information divergences[END_REF], the authors propose a characterization of the information divergences that are not sketchable. They have proven that any distance that has not "norm-like" properties is not sketchable.

On the other hand, very few works have tackled the distributed streaming model, also called the functional monitoring problem [START_REF] Cormode | Algorithms for distributed functional monitoring[END_REF], which combines features of both the streaming model and communication complexity models. As in the streaming model, the input data is read on the fly, and processed with a minimum workspace and time. In the communication complexity model, each node receives an input data stream, performs some local computation, and communicates only with a coordinator who wishes to continuously compute or estimate a given function of the union of all the input streams. The challenging issue in this model is for the coordinator to compute the given function by minimizing the number of communicated bits [START_REF] Cormode | Algorithms for distributed functional monitoring[END_REF], [START_REF] Arackaparambil | Functional monitoring without monotonicity[END_REF], [START_REF] Gibbons | Estimating simple functions on the union of data streams[END_REF]. Cormode et al. [START_REF] Cormode | Algorithms for distributed functional monitoring[END_REF] pioneer the formal study of functions in this model by focusing on the estimation of the first three frequency moments F 0 , F 1 and F 2 [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF]. Arackaparambil et al. [START_REF] Arackaparambil | Functional monitoring without monotonicity[END_REF] consider the empirical entropy estimation [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF] and improve the work of Cormode by providing lower bounds on the frequency moments, and finally distributed algorithms for counting at any time t the number of items that have been received by a set of nodes from the inception of their streams have been proposed in [START_REF] Haung | Randomized algorithms for tracking distributed count, frequencies and ranks[END_REF], [START_REF] Liu | Continuous distributed counting for non-monotonic streams[END_REF].

In this paper, we go a step further by presenting a distributed algorithm that approximates the relative entropy among ℓ data streams by using

O log n + 1 ε 2 + 1 ε + log m ε 2 log 1 δ (log n + log m)
bits of space for each ℓ nodes, and ℓ+1 floats for the coordinator, where n is the number of distinct items, and m is the largest data stream observed at one of the ℓ nodes. This distributed algorithm relies on an estimator called AnKLe proposed in a previous work [START_REF] Anceaume | An information divergence estimation over data streams[END_REF], [START_REF] Anceaume | Ankle: Detecting attacks in large scale systems via information divergence[END_REF]. AnKLe estimates the Kullback-Leibler (KL) divergence between a stream and a uniform one streams. This divergence can be viewed as an extension of the Shannon entropy and is often referred to as the relative entropy [START_REF] Cover | Elements of information theory[END_REF]. Finally, we guarantee that the number of bits exchanged between the nodes in the system is upper bounded by O(rℓ(log n +1)). To the best of our knowledge, such a work has never been done so far.

The paper is organized as follows. First, Section 2 describes the system model and some background on information theory. Section 3 presents the buildings blocks of our algorithm AnKLe, while Section 4 analyses its quality. Section 5 extends AnKLe to a distributed setting and evaluates its quality. In Section 6, we empirically evaluate the accuracy of the estimation provided by AnKLe. Finally, we conclude in Section 7. For space constraint reasons, extended related work on the estimation of the relative entropy of data streams is presented in the companion paper [START_REF] Anceaume | A distributed information divergence estimation over data streams[END_REF].

2M ODEL AND BACKGROUND

Model

We present the computation model under which we analyze our algorithms and derive lower and upper bounds. We consider a set of ℓ nodes S (1) ,...,S (ℓ) such that each node S (i) receives a large sequence σ (i) of TCP/IP packets [START_REF] Demaine | Frequency estimation of internet packet streams with limited space[END_REF] modeled as data items or symbols u, v, w, . . . drawn from a large universe N . For a given stream σ (i) ,i ∈ {1, .., ℓ}, we denote by n (i) the number of distinct items that appear in σ (i) and by m (i) the size of σ (i) , that is the number of items in it 1 . Items arrive regularly and quickly, and due to memory constraints (i.e., nodes can locally store only a small amount of information with respect to the size of their input stream and perform simple operations on them), items must be processed sequentially and in an online manner. Nodes cannot communicate among each other. On the other hand, there exists a specific node, called coordinator, with which each node may communicate. We assume that communication is instantaneous. We refer the reader to [START_REF] Muthukrishnan | Data Streams: Algorithms and Applications[END_REF] for a detailed description of data streaming models and algorithms.

Model of the Adversary: We suppose that the adversary is omnipotent in the sense that it may actively tamper with the data stream of any node by observing, inserting, dropping or re-ordering items of their input stream. We suppose that the algorithm used by a node to estimate the divergence is public knowledge (i.e., to avoid some kind of security by obscurity), however the adversary has not access to the local random values generated during the algorithm (e.g., the random choice of hash functions from a collection of 2-universal hash functions, see Section 3).

Preliminaries

We first present notations (summarized in Table 1) and background on data streams analysis that make this paper self-contained. Note that some of these notations are formally defined in the remaining of the paper.

Entropy

Intuitively, the entropy is a measure of the randomness of a data stream σ. The entropy H σ is minimum (i.e., equal to zero) when all the items in the stream are the same, and it reaches its maximum when all the items in the stream are distinct. Specifically, we have H σ = -u∈N p u log p u , where for each u ∈ N , p u = m u /m with m u representing the number of times the value u appears in the stream σ, and m = u∈N m u being the size of the stream. Thereafter, we will denote by "log" the logarithm in base 2, and by convention, we pose 0 log 0 = 0. Without loss of generality, we assume that items are ordered so that m 1 ≥ m 2 ≥ ... ≥ m n . Note that the number of times m u item u appears in a stream is commonly called the frequency of item u. The norm of the entropy is defined as F H = u∈N m u log m u .

Kullback-Leibler Divergence

The Kullback-Leibler (KL) divergence [START_REF] Kullback | On information and sufficiency[END_REF], also called the relative entropy, is a robust metric for measuring the statistical difference between two data streams. The KLdivergence is a member of a larger class of distances known as the Ali-Silvey distances [START_REF] Ali | General Class of Coefficients of Divergence of One Distribution from Another[END_REF]. Given two probability distributions p and q on N , the KL-divergence between p and q is defined as the expected value of the likelihood ratio with respect to q:

D(p||q)= u∈N p u log p u q u = H(p, q) -H(p),
where H(p)=-p u log p u is the (empirical) entropy of p and H(p, q)=-p u log q u is the cross entropy of p and q. As we use a logarithm in base 2, the divergence is measured in bits. It is zero if and only if p = q. Let p (U ) be the uniform distribution corresponding to a uniform stream, and q be the probability distribution corresponding to the input stream. In the rest of this paper we consider D(q||p (U ) ) as a measure of the divergence between the current stream and the ideal one.

Frequency Moments

Frequency moments are important statistical tools that have been introduced by Alon et al. [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF]. Computing frequency moments F k allows to quantify the amount of skew in a data stream. For each k ≥ 0, the k-th frequency moment F k of σ is defined as F k = u∈N m k u . Among the remarkable moments, F 0 , F 1 and "F ∞ " represent respectively the number of distinct elements in σ, the size of σ, and the most frequent item in σ [START_REF] Flajolet | Probabilistic counting algorithms for data base applications[END_REF].

2-universal Hash Functions

In the following, we intensively use hash functions randomly picked from a 2-universal hash functions family. A collection H of hash functions h : {1,...,M} → {0,...,M ′ } is said to be 2-universal if for every two different items x, y ∈ [M ], P h∈H {h(x)=h(y)} ≤ 1 M ′ , which is the probability of collision obtained if the hash function assigned truly random values to any x ∈ [M ].

Randomized (ε, δ)-approximation Algorithm

A randomized algorithm A is said to be an (ε, δ)approximation of a function φ on σ if for any sequence of items in the input stream σ, A outputs φ such that P{| φφ |> εφ} < δ, where ε, δ > 0 are given as parameters of the algorithm.

3D ETECTING ADVERSARIAL BEHAVIORS VIA THE KL-DIVERGENCE ESTIMATION

Building Blocks

We describe three algorithms that form the building blocks of the AnKLe (Attack-tolerant eNhanced Kullback-Leibler divergence Estimator) algorithm. All these algorithms have been designed in the stream data model (cf. Section 2.1). For self-containment reasons, we briefly review these building blocks and describe their theoretical guarantees.

Notation Meaning ℓ

Number of data streams in the system (Section 2.1)

S (i)
Site at which σ (i) is received (Section 2.1)

σ (i)
Input stream (Section 2.1)

m (i) Size of stream σ (i) (Section 2.1) n (i) Number of distinct data items in σ (i) (Section 2.1) N Domain of data items (Section 2.1) u, v, . . . Data items of N (Section 2.1) m (i) u Number of occurrences of data item u in σ (i) (Section 2.2) H Collection of 2-universal hash functions (Sec- tion 2.2) ε, δ
Quality parameters of the approximation algorithms (Section 2.2) p, q Probability distributions (Section 2.2)

p (U )
Uniform probability distribution (Section 2.2)

F k
Frequency moments of a stream (Section 2.2)

H(p) Entropy of distribution p (Section 2.2) F H Norm of the entropy (Section 2.2) Hσ
Entropy of a stream σ (Section 2.2)

H(p, q)
Cross entropy of p relative to q (Section 2.2) D(p||q)

Divergence of Kullback-Leibler between p and q (Section 2. Estimator of the norm of the entropy on frequent data items (Section 4)

Ys

Estimator of the norm of the entropy on sparse data items (Section 4) D i

Estimator of D(q

σ (i) ||p (U ) ) (Section 5) r
Number of rounds in the distributed algorithm (Section 5)

Table 1 List of symbols and notations

Estimating the k th Moment of a Stream

The AnKLe algorithm adopts the structure of the method proposed by Alon et al. [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF] (called in the following the AMS algorithm), to approximate the KL-divergence of a stream. The AMS algorithm estimates the k-th frequency moment of a stream as follows. It computes a basic estimator which takes the form of a random variable X whose mean value is exactly equal to the k th frequency moment of a stream and whose variance is very small. Specifically, X is defined as

X = m(g k -(g -1) k ),
where g is the exact number of times element v appears in the stream from a uniformly and randomly chosen position p (we have a p = v) in the stream onwards. To improve the accuracy of the estimation, several independent basic estimators are computed on the stream (specifically

s 1 × s 2 basic estimators X ij , for 1 ≤ i ≤ s 1 and 1 ≤ j ≤ s 2 ,
for s 1 × s 2 positions uniformly chosen at random in the stream σ), and the final estimator Y is set to be

Y = median 1≤j≤s2 (1/s 1 s1 i=1 X ij ) . Theorem 1 ([9]) For any ε, δ ∈ (0, 1), if s 1 ≥ Var[X]/(ε 2 E[X] 2 ) and s 2 = 4 log(1/δ), then Y is a (ε, δ)- approximation of E[X], i.e., P{| E[X] -Y |> εE[X]} < δ.

Estimating the Number of Items

The problem of estimating the number of distinct elements has received a lot of attention in the data stream model. First, the seminal work of Flajolet et al [START_REF] Flajolet | Probabilistic counting algorithms for data base applications[END_REF] has shown that it is possible to compute such an estimate using only logarithmic space in n by relying on properties of hash functions. Afterwards, follow-up enhancements have improved the quality of F 0 [START_REF] Kane | An optimal algorithm for the distinct element problem[END_REF], [START_REF] Bar-Yossef | Counting distinct elements in a data stream[END_REF], [START_REF] Durand | Log-log counting of large cardinalities[END_REF]. A comprehensive survey describing the literature on distinct elements in the data stream model is presented by Gibbons in [START_REF] Gibbons | Data Streams Management: Processing High-Speed Data Streams[END_REF]. The Durand and Flajolet algorithm [START_REF] Durand | Log-log counting of large cardinalities[END_REF] (referred to as the LogLog algorithm in the following) and described in Figure 1 computes an estimation F0 of the number of distinct items F 0 (denoted as n in this paper) in a stream. This algorithm builds upon the approaches proposed in [START_REF] Flajolet | Probabilistic counting algorithms for data base applications[END_REF] and [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF]. Briefly, it maintains a collection of κ registers M 1 ,...M κ , where κ a power of 2. It uses also a hash function h(.) that maps each distinct item read from the stream to i with probability 2 -(i+1) , where i ∈ [0,L] and L is typically equal to 32. For each stream item v, the log 2 κ least significant bits of h(v) are used to select one of the k registers M i , and the maximum between the remaining Llog 2 κ bits of h(v) and M i are used as the value of M i . Once all the items of the stream have been read, then the arithmetic mean 1 κ k j=1 M j approximates log 2 (n/κ) plus an additive bias. The estimate of n returned by the LogLog algorithm is F0 = α κ κ2 1 κ Mj , where α κ is a constant derived by the analysis [START_REF] Durand | Log-log counting of large cardinalities[END_REF] which allows to correct the systematic bias of the arithmetic mean in the asymptotic limit. Kane et al. [START_REF] Kane | An optimal algorithm for the distinct element problem[END_REF] improve this algorithm by assuming a truly random hash function and κ-wise independent hash functions, which provides the following estimation quality.

Theorem 2 ([8]

) For any ε, their algorithm outputs F0 such that P{| F0 -F 0 | > ε} < δ where δ =2 /3. The worst-case running time for each input symbol is O(1), and the total space required by the algorithm is O(1/ε 2 + log n) bits, which makes this algorithm optimal.

Determining the Most Frequent Identifiers

The problem of determining the c most frequent items in a stream has also been studied extensively in the data stream literature. Thereafter, we describe a deterministic algorithm that outputs items that occur more than m c in a stream. This algorithm, due to Misra and Gries [START_REF] Misra | Finding repeated elements[END_REF], maintains c counters such that for each counter, its key is the item read from the stream and its value is related to the frequency of items. Initially, all the counters are set to (-, 0). Afterwards, when an item is read from the stream, if that item has already a counter associated to it, then this counter is incremented. If this is not the case and if there are still free counters available, then one of these free counters is allocated to this new item and its value is set to 1. Otherwise, all the allocated counters are decremented by one, and if after this operation some of them are equal to 0 then their keys are erased and

j ∈ [0..c] do A[j] ← (⊥, ⊥); 1 for a i ∈ σ do 2 v = a i ; 3 if ∃u such that the item of A[u] is s then increment the 4 count value of A[u]; else 5 if ∃u ′ such that A[u ′ ]=(⊥, ⊥) then 6 A[u ′ ]=(v, 1)

The AnKLe algorithm

This section presents AnKLe, the algorithm we propose for computing the KL-divergence of a stream. Our starting point is the re-writing of the KL-divergence as follows. From Definition 1, we have

D(q σ ||p (U ) )= n i=1 q i log (q i ) - n i=1 q i log p (U ) i = log(n) -log(m)+ 1 m n i=1 m i log (m i ) . (1)
Thus estimating the KL-divergence amounts in (i) estimating the number of distinct items in the stream (i.e., F 0 ) in order to obtain a good approximation of log(n), and (ii) estimating n i=1 m i log (m i ), which corresponds to the norm of the entropy F H . While the first point is solved by relying on the KNW [START_REF] Kane | An optimal algorithm for the distinct element problem[END_REF] algorithm, the second point is tackled by extending the approach proposed by Alon et al. [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF] to deal with arbitrary distributions of items in the input stream.

Figure 3. AnKLe Algorithm

Input: An input stream σ of length m, k (number of frequent items), κ (see Figure 1), c (see Figure 2), s 1 ,s 2 (see Section 3.1.1)

Output: Estimation of D(qσ||p (U ) ) Choose s 1 × s 2 random integers in [1..m]; 1 for u 1 ∈ [0..s 1 ],u 2 ∈ [0..s 2 ] do S[u 1 ,u 2 ] ← (⊥, ⊥);
if (s i , -) ∈ F then (s i ,r i ) ← (s i , -) ; 16 else (s i ,r i ) ← (s i ,m(r i log r i -(r i -1) log(r i -1))); 17 Y S ← median 1≤j≤s 2 1 s 1 s 1 i=1 S ij ; 18 Y F ← (s i ,r i )∈ F r i log r i ; 19 p ← 1 -max 0, min Ys,Y F -m 10 • m ; 20 return D =log F0 -log m + p m Y S + Y F ; 21
The pseudo-code of AnKLe is presented in Figure 3 and consists of two phases. The first one (lines 3-13) is executed upon reception of the items of the stream, while the second one (lines 14-21) is run when m items have been read from the stream. The first phase is composed of three tasks (T 1 , T 2 and T 3 ), executed in parallel. Task T 1 (line 5) estimates the number of distinct items present in the stream, Task T 2 (line 7) identifies the k most frequent items in the stream, and Task T 3 samples random items in the stream in order to compute their exact frequency. Specifically, Task T 3 (lines 9-13) consists in running a sampling estimator X on the stream. The basic estimator X = X i,j is designed so that its mean value is equal to the norm of the entropy F H and its variance is small. More precisely, we have

X = m(g log g -(g -1) log(g -1)), ( 2
)
where g is the random variable representing the number of occurrences of an item ℓ in the stream. This item ℓ is such that its position j in the stream is a random number in [m]. The random variable g counts the number of times ℓ appears in the stream from position j onwards. Formally, g is defined as g =|{j : j ≥ ℓ,a j = a ℓ }|.

We can show as done in [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF], [START_REF] Lall | Data streaming algorithms for estimating entropy of network traffic[END_REF], that the estimator X is unbiased (i.e., its expectation is equal to F H ), i.e.,

E[X]= 1 m n i=1 mi j=1 m(j log j -(j -1) log(j -1)) = F H . (3)
To improve the accuracy of the estimation, s 1 ×s 2 such basic estimators X ij (for

1 ≤ i ≤ s 1 and 1 ≤ j ≤ s 2 )
are used, each one sampling a random position in the stream. From the implementation point of view, tracking these estimators consists in storing s 1 × s 2 counters, each one counting the number of occurrences of an item whose position has been randomly chosen in the stream. When item u is read from the input stream, if u has already one or more counters assigned to it then all these counters are incremented. In addition, if the position at which u has been read in the stream is one of the chosen locations, then a counter is assigned to u, and its value is set to 1. Thus for each of these "tracked" items, an exact count of their frequency is continuously maintained starting from a random position in the stream.

The post-processing phase of AnKLe algorithm estimates the KL-divergence of the input stream according to Relation (1). This phase is executed when m items have been read from the input stream. In this work, we suppose that m is a parameter of the algorithm, however by using techniques proposed in Chakrabarti et al. [START_REF] Chakrabarti | A near-optimal algorithm for computing the entropy of a stream[END_REF] we can extend our solution to streams whose size is a priori unknown. To accurately estimate the KL-divergence of the stream, one needs to cope with patterns in which a small number of items occur with a very high frequency with respect to the other items. When such patterns occur, the basic estimator X alone is unable to compute the norm of the entropy in bounded space [START_REF] Chakrabarti | A near-optimal algorithm for computing the entropy of a stream[END_REF]. Indeed, by analogy of the calculation performed in [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF], the variance of the estimator grows with the norm of the entropy. We extend [START_REF] Chakrabarti | A near-optimal algorithm for computing the entropy of a stream[END_REF] method to deal with any stream distribution in order to guarantee that whatever the strategy of the adversary, the error on the estimation is kept small (as shown in Section 6). Specifically, the estimator X is computed on unfrequent items (cf. lines 14-18) as done in Relation (3), while the contribution of highly frequent items on the norm of the entropy is directly computed as (si,ri)∈ F r i log r i (cf. lines 19). The set F represents the set of highly frequent items dynamically computed in Task T 2 . Finally, to prevent some of the items to appear in both terms, we weight the contribution of both terms by p (cf. line 21).

4A NALYSIS

In this section, we analyze the properties of the AnKLe algorithm given in Figure 3. This analysis is split into three phases. We first evaluate the quality of Y F through Lemma 5, we then evaluate the quality of Y S through Lemmata 6 and 7, and finally derive the quality of AnKLe algorithm by combining the previous results with the one of [START_REF] Kane | An optimal algorithm for the distinct element problem[END_REF] with Lemma 8.

In order to state the main theorem, we introduce the following notations. Let K be the set of the most frequent items i that satisfy mi >e(if any) returned at line 12 in Figure 3. Let n s and m s be respectively defined as n s = n-|K| and m s = m-k∈K m k . Parameter n s represents the number of "sparse" items (i.e., the remaining items of the stream after having removed the most frequent ones as identified by Task T 2 and after the execution of line 14). In the same way, m s represents the size of the sub-stream in the original stream occupied by these sparse items. Finally, the norm of the entropy of this substream is denoted by F s H . Theorem 4 For any δ and ε such that 1/3 < δ < 1 and 0 < ε < 1 2 , and for any constant ∆ > 0, the AnKLe algorithm gives an (ε, δ)-approximation of the KL-divergence, using

O log n + 1 ε 2 + 1 ε + µ ε 2 log 1 δ (log n + log m)
bits of space where µ = (log m + log e -1) if F s H ≥ m 2 ∆ms , and µ =(n -1 ε -1) otherwise. In particular, taking ∆ to be a constant, we get a poly-logarithmic space algorithm that works on streams whose F s H is not "too small". Note that this is the case for most of the streams, as Task T 2 aims at removing the most frequent items, raising then the norm of the entropy of the sparse sub-stream.

Proof: The first part of the proof is directly derived from Lemma 8. Regarding the space complexity of An-KLe, it is given by the sum of the complexity of each Task T 1 , T 2 and T 3 added up with the space required for the post-processing phase, which is O(1). From respectively [START_REF] Kane | An optimal algorithm for the distinct element problem[END_REF], [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF], [START_REF] Misra | Finding repeated elements[END_REF], we get that the space complexity of AnKLe is

O (C KNW + C MG + C AMS ), where:    C KNW = O log n + 1 ε 2 [8] C MG = O (c(log n + log m)) [9] C AMS = O (s 1 s 2 (log n + log m)) [29].
Lemmata 5 and 6, and the hypotheses on c, s 1 and s 2 presented in Equation 4 end the proof.

We now show a series of results that prove Lemmata 5, 6 and 8.

Evaluation of Y F

The following lemma computes the quality of Y F .

Lemma 5 For any

ε > 0, we have P{|Y F -Y F | > εY F } =0,
where Y F is defined at line 17 in Figure 3.

Proof: The proof combines the proof presented in [START_REF] Misra | Finding repeated elements[END_REF] and the fact that c>kcounters are used. For space constraint reasons, the proof is presented in the companion paper [START_REF] Anceaume | A distributed information divergence estimation over data streams[END_REF].

Evaluation of Y s

Let X s be the same estimator as X (which has been defined in Section 3.2), but X s is defined only on sparse items in the stream. From a derivation similar to the one used in Relation (1), X s is an unbiased estimator of F s H . Lemma 6 ∀ε, δ > 0, it exists s 1 and s 2 such that P{|Y s -F s H | > εF s H } < δ. Proof: For space constraint reasons, the proof is presented in [START_REF] Anceaume | A distributed information divergence estimation over data streams[END_REF].

We now derive a relation between E[X s ] and V [X s ] to deduce an estimation on the size of s 1 .

Lemma 7

Let us consider the sub-stream m s populated by sparse items. Then, for any constant

∆ > 0 if F s H ≥ m 2 ∆ms then V [X s ] ≤ ∆(log m + log e -1)E[X s ] 2 , otherwise V [X s ] ≤ (n s -1)E[X s ] 2 .
Proof: For space constraint reasons, the proof is presented in [START_REF] Anceaume | A distributed information divergence estimation over data streams[END_REF].

Evaluation of D

As |K| < 1/ε, we are now able to explicitly give the value of all the parameters of tasks T 2 and T 3 :

                       c = O 1 ε s 1 =        O log m + log e -1 ε 2 if F s H ≥ m 2 ∆ms O n s -1 ε 2 otherwise s 2 = O log 1 δ (4)
Using these values, we have the necessary material to derive the global quality of AnKLe. First of all, by linearity of expectation, the random variable D is an unbiased estimator of D(q σ ||p (U ) ), given by Equation 1.

Lemma 8 Given ε > 0 and δ > 1 3 , we have

P | D -D(q σ ||p (U ) )| > εD(q σ ||p (U ) ) < δ.
Proof: Let δ ′ = δ -1 3 . Then we have δ ′ > 0. Combining the independence of Y s and Y F and Lemmata 5 and 6, we have:

P{|Y s + Y F -E[Y s + Y F ]| > εE[Y s + Y F ]} ≤ P{|Y s -E[Y s ]| > εE[Y s ]} + P{|Y F -E[Y F ]| > εE[Y F ]} < δ ′
By definition of D(q σ ||p (U ) ) in Relation 1 and D in AnKLe algorithm at line 21, we have :

P{| D -D(q σ ||p (U ) )| > εD(q σ ||p (U ) )]} ≤ P{| log F0 -log F 0 | > ε log F 0 } + P 1 m | FH -F H | > ε m E[F H ] ≤ 1 3 + P 1 m | FH -F H | > ε m E[F H ] (from [8]) ≤ 1 3 + P |Y s + Y F -E[Y s + Y F ]| > εE[Y s + Y F ] < 1 3 + δ ′ = δ
that concludes the proof.

5D ISTRIBUTED APPROXIMATION ALGORITHM

In this section, we propose an algorithm that computes the KL-divergence among a set of ℓ distributed data streams with respect to the expected one, so that the number of bits communicated between the ℓ sites and the coordinator is minimized. This amounts for the coordinator to compute an approximation of the global KL-divergence composed by the joint distribution of ℓ data streams. Specifically, let X = {X 1 ,X 2 ,...,X ℓ } be the random vector representing the set of discrete independent random variables X 1 ,...,X ℓ describing respectively the streams σ 1 ,...,σ ℓ . As the KL-divergence is additive for independent distributions, if each node S i computes locally an estimation D σi using AnKLe, we have D = 1≤i≤ℓ D σi .

A simple motivating application that would benefit from our distributed algorithm is the node sampling application. Suppose that the ℓ sites of a large scale and dynamic system are in charge of locally running a uniform node sampling service 2 , and locally feed AnKLe with the continuous stream σ ′ i of identifiers generated by their node sampling service. By doing so each site S i continuously estimates the KL-divergence D σ ′ i of σ ′ i to detect any deviation from a uniform stream. Indeed, in absence of malicious behaviors D σ ′ i should be close to 0 as any node of the system has the same probability to be output by the uniform node sampling service. Now, in presence of attacks, the adversary may judiciously bias the ℓ input streams σ 1 ,...,σ ℓ so that for each site S i , D σ ′ i remains small enough not to be considered locally as an attack. On the other hand, by periodically aggregating D σ ′ 1 ,..., D σ ′ ℓ , the coordinator can quickly detect whether the cumulated D σ ′ i exceeds some given threshold, and if this is the case informs the ℓ sites to temporarily stop using their sampling service until D shrinks to an acceptable value.

Our algorithm proceeds in rounds until all the data streams have been read in their entirety. In the following, we denote the substream of σ i received by S i during the round r by σ (r) i , and the cardinal of this substream by d r . Specifically, in a bootstrap phase corresponding to round r =1of the algorithm, each site S i computes a first estimation of the KL-divergence D σi of the received data stream σ i as described in Algorithm 3. Once node S i has received d 1 data items (where d 1 should typically be set to 100 [START_REF] Arackaparambil | Functional monitoring without monotonicity[END_REF]), then node S i sends its first estimation D σ (1) i to the coordinator, and starts a new round r =2 .

Upon receipt of D σ (1)

i from any S i , the coordinator asks all the ℓ -1 other nodes S j to send their own sketch D σ (1) j . Once the coordinator has received all D σ (1) i , for

1 ≤ i ≤ ℓ, it sets ∀i ∈ [ℓ], D σi ← D σ (1) i and computes D = 1≤i≤ℓ D σi .
2. A uniform node sampling service run at site S i continuously outputs the identifier of a random node that belongs to S i input stream σ i , which is made of the nodes ids exchanged within the system.

At round r>1, each node S i updates its estimation D σ (r) i with the sequence of data streams received since the beginning of round r. Let d r =2 d r-1 be an upper bound on the number of received items during round r. When node S i has received d r data items since the beginning of round r, it sends its current estimation D σ (r) i to the coordinator and starts a new round r +1.

Note that during round r, S i regularly compares D σ (r) i with D σ (r-1) i to detect whether significant variations in the stream have occurred before having received d r items. This allows to inform the coordinator as quickly as possible that some attack might be undergoing. Upon receipt of the first D σ (r) i from any S i , the coordinator asks all the ℓ -1 other nodes S j to send it back their own D σ (r) j . The coordinator locally updates the ℓ estimations and the global estimated divergence value. The communication flows between the ℓ sites and the coordinator is illustrated in the companion paper [START_REF] Anceaume | A distributed information divergence estimation over data streams[END_REF].

Theorem 9

The distributed AnKLe algorithm gives an (ε, δ)approximation of the KL-divergence between ℓ distributed input streams.

Proof: The statement of this theorem directly derives from Theorem 4 and the fact that the KL-divergence is additive for independent distributions.

Lemma 10 The distributed AnKLe algorithm gives an approximation of the global KL-divergence, using

O log n + 1 ε 2 + 1 ε + µ ε 2 log 1 δ (log n + log m)
bits of space for each ℓ nodes, and O (log n(ℓ +1)) bits of space for the coordinator, where µ = (log m + log e -1) if F s H ≥ m 2 ∆ms , and µ =(n -1 ε -1) otherwise. Proof: The statement of this theorem directly derives from Theorem 4 and the fact that the coordinator maintains ℓ memory slots to store each estimation of all the ℓ nodes plus the global estimation itself. Each of these slots requires O(log n) bits of space as the maximum value of the relative entropy with respect to the uniform distribution is log n +(n -1) log m [START_REF] Anceaume | Characterizing the adversarial power in uniform and ergodic node sampling[END_REF].

Lemma 11

The distributed AnKLe algorithm gives an approximation of the global KL-divergence D by sending O (rℓ (log n +1)) bits, where r is the number of rounds and n is the number of distinct items in all streams.

Proof: Suppose that the number of rounds of the algorithm is equal to r. An upper bound of the number of bits sent by any node during round r is given by the size of its local estimation of the KL-divergence, which is log n (cf. Lemma 10). Finally, at the end of each round, the coordinator sends 1 bit to at most ℓ -1 nodes.

6P ERFORMANCE ANALYSIS

In this section, we evaluate the accuracy of AnKLe by comparing its estimation with the exact value of the KL-divergence computed between the observed input stream and the uniform one. We also compare AnKLe with the estimator-based algorithms of Alon et al. [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF] and Chakrabarti et al. [START_REF] Chakrabarti | A near-optimal algorithm for computing the entropy of a stream[END_REF]. In the former case, the original estimator computes the k-th frequency moment of a stream, while in the latter case, the original estimator measures the entropy of a stream. We have adapted both algorithms to compute, instead, the norm of the entropy. We have fed these algorithms with both realworld data sets and synthetic traces. Real data give a realistic representation of some existing systems, while the latter ones allow to capture phenomenon which may be difficult to obtain from real-world traces, and thus allow to check the robustness of our metric. Real data have been downloaded from the repository of Internet network traffic [START_REF]the Internet Traffic Archive[END_REF]. Two of them represent two weeks logs of HTTP requests to the Internet service provider ClarkNet WWW server -ClarkNet is a full Internet access provider for the Metro Baltimore-Washington DC area -the other two ones contain two months of HTTP requests to the NASA Kennedy Space Center WWW server, and the last one represents seven months of HTTP requests to the WWW server of the University of Saskatchewan, Canada. In the following these data sets will be respectively referred to as ClarkNet, NASA, and Saskatchewan traces. the generated streams have a length of m =2 0 0 , 000 items. We have tested 750 different settings of the following parameters: n, the number of distinct items in the stream, s 1 and s 2 , which are related to the size of the estimator matrix in Task T 3 , and k, the number of counters used in Task T 2 . For each setting, we have conducted 10 trials of the same experiment and computed the average and the standard deviation. Except for the uniform and the zipfian-1 distributions that respectively model an ideal stream in which each item appears with the same frequency and a realistic one in absence of any attacks, the other four distributions capture different adversarial strategies. Specifically,

• the "Poisson" distribution allows to generate streams in which the frequency of a large quantity of items is significantly higher than the frequency of the remaining items. This type of stream might reflect an attack during which the adversary aims at over-representing a large number of its own node identifiers.

• the "Zipf-2" distribution engenders streams in which there is a small number of highly frequent items. This type of stream might correspond to an eclipse attack in which the objective of the adversary is to poison the routing tables of honest nodes. • the "Pascal" and "Zipf-4" distributions produce streams in which a very small number of items have a very high frequency 3 . These distributions might illustrate streams in which very few items (typically 1 to 3) are over-pushed by the adversary. Figure 4 summarizes the results obtained for the An-KLe, AMS and CCM estimators, averaged over 55,000 experiments (i.e. 750 different settings with 10 repetitions for each setting, over 6 synthetic distributions and 1000 settings for each data set). For clarity reasons, the average value of CCM for Zipf-1 has been cropped in Figure 4(a) since the estimated value of the KLdivergence by CCM is around 8.3. These results clearly 3. Pascal distribution is also known as Negative Binomial distribution. show that AnKLe outperforms the estimator CCM for all the distributions, even in scenario in which CCM should excel (i.e., Zipf-4), as this corresponds to a stream in which a very frequent item exists in the observed stream. Compared with the AMS estimator, the results obtained with AnKLe are for most of them better except for the Zipf-2 distribution. But even for this specific distribution, the standard deviation of AnKLe is four times smaller than the one of AMS (i.e., 0.09 versus 0.36), thus demonstrating that AnKLe provides a more robust and stable estimation than AMS on this distribution. Figure 4(b) confirms the relevance and efficiency of AnKLe when fed with real traces. Whatever the input traces, it clearly outperforms CCM and AMS estimators in terms of both average and standard deviation. Further results are presented in [START_REF] Anceaume | A distributed information divergence estimation over data streams[END_REF].

Figure 5 shows the evolution of the KL-divergence estimation as a function of n. The x-coordinate represents the number of distinct items in the stream as a ratio of its length m. The main observation that can be drawn from Figure 5(a) is that the CCM estimator behaves relatively badly in presence of a small number of distinct items with frequency uniformly distributed in the stream. However, its accuracy increases when the number of distinct items increases. The other two estimators are very close to the real value of the KLdivergence, with a clear advantage for AnKLe. This observation is confirmed in Figure 5(b) that corresponds to a zoom of Figure 5(a). This figure demonstrates that the estimation provided by AnKLe is very good. In average, the AnKLe estimation overlaps with the real value of the KL-divergence, contrary to AMS, and its standard deviation remains small, for any values of n. The evolution of the KL-divergence estimation as a function of k, and s 1 are presented in [START_REF] Anceaume | A distributed information divergence estimation over data streams[END_REF], in particular, we have observed that CCM is not adapted to uniform and near uniform streams, while AMS and AnKLe provide very good estimates for these distributions.

Figure 6 shows the KL-divergence estimation as a function of s 1 and k parameters. Several observations can be drawn from both figures. First, regarding Fig-ure 6(a), the robustness of CCM estimator greatly improves with increasing values of s 1 , as the cone-shaped curves converge for s 1 >m / 500. On the first hand, the value towards which the CCM converges underestimates the KL-divergence. Thus, s 1 has a greater impact on CCM robustness than on its accuracy. On the other hand, variations of s 1 have not impact on AMS robustness. This feature does not appear in AnKLe as the weight given to Task T 2 makes it preponderant with respect to Task T 3 , limiting accordingly the lack of robustness of Task T 3 . Finally, the main observation drawn from Figure 6(b) is that AnKLe fully overlaps with the exact value of the KL-divergence, which clearly demonstrates the robustness of this estimator in presence of any input streams. Regarding CCM, we can observe that when the number of counters k is less than 0.1n, then the Misra-Gries algorithm under-estimates the k most frequent items, which degrades the estimation of CCM. This confirms the theoretical bound of k ≥⌈7ε -1 ⌉ shown in [START_REF] Chakrabarti | A near-optimal algorithm for computing the entropy of a stream[END_REF]. On the other hand, variations of parameter k has not impact on AMS as this estimator does not decompose its computation according to items frequency characteristics. More results are presented in [START_REF] Anceaume | A distributed information divergence estimation over data streams[END_REF] with respect to the Poisson distribution. To summarize, experiments have validated the impressive accuracy and robustness of AnKLe in presence of a very large spectrum of distributions. This illustrates the importance of the weighting factor applied to both terms of the estimator.

7C ONCLUSION AND FUTURE WORKS

We have proposed AnKLe, a novel algorithm for estimating the KL-divergence between the observed stream and the expected one. AnKLe is very efficient both in terms of space and time, and requires only a single pass over the data stream. We have characterized how the different parameters impact the precision of the estimation and the space complexity of AnKLe. We have shown that AnKLe is an (ε, δ)-approximation algorithm with a space complexity Õ 1 ε 2 + 1 ε bits in "most" of the cases. The distributed version of AnKLe can be used to compare different input streams, which may reveal as an interesting ingredient to detect isolated intrusions. Finally, simulations have also shown that AnKLe performs always better, in terms of accuracy and robustness, than other state-of-the-art estimator-based algorithms.

Figure 1 . 1 κ 3 for a i ∈ σ do 4 v = a i ; 5 x 9 Figure 2 .

 1134592 Figure 1. LogLog algorithm Input: An input stream σ; precision parameter κ; Output: Estimate F0 in σ Pick one 2-universal hash function h :[ 1 ..N] → [L]; 1

7 else for i =1to c do 8 9 if 10 A

 78910 Decrement the count of A[i]; the count value of A[i]=0then released. The pseudo-code of the Misra Gries algorithm is presented in Figure2. Theorem 3([29]) The Misra and Gries algorithm with parameter c returns for any item u an estimate mu such that m u -m c ≤ mu ≤ m u with O(c(log m + log n)) bits of space.

2 for a j ∈ σ do 3 v = a j ; 4 Task T 1 : 5 F0← 6 Task T 2 : 7 F 8 Task T 3 : 9 forall 13 F

 2341562783913 Algorithm in Fig.1(KNW[START_REF] Kane | An optimal algorithm for the distinct element problem[END_REF]) fed with v; ← Algorithm in Fig.2(Misra-Gries[START_REF] Misra | Finding repeated elements[END_REF]) fed with v; entries i of matrix S such that(s i ,r i ) =( ⊥, ⊥) do 10 if s i = v then r i ← r i +1;11 if j is one the s 1 × s 2 random integers then 12 assign (v, 1) to the first unused entry of S; ← the k most frequent items (s i ,r i ) of F and such that r i >e; 14 forall entries i of matrix S do[START_REF] Arackaparambil | Functional monitoring without monotonicity[END_REF]

  Comparisons between the Uniform distribution and the Uniform, Zipf-1, Zipf-2, Zipf-4, Pascal and Poisson distributions.

  Comparisons between a "uniform" data set and the real data ones.

Figure 4 .

 4 Figure 4. Comparison between the exact value of the KL-divergence and its estimations computed with AnKLe, AMS and CCM.

Figure 5 .

 5 Figure 5. KL-divergence estimation as a function of the size of the system n.

Figure 6 .

 6 Figure 6. KL-divergence as a function of s1 and s2 (on the left) and k (on the right) for the Pascal distribution.

Table 2

 2

			presents some statistics
	of these data traces, in terms of stream size (cf. "#
	items"), number of distinct items in each stream (cf. "#
	distinct items") and the number of occurrences of the
	most frequent item (cf. "max. freq."). Note that all these
	benchmarks share a Zipfian behavior, with a lower α
	parameter for Saskatchwan.
	Consider now the distributions of synthetic traces. All
	Data trace	# items (m)	# distinct items (n)	max. freq.
	NASA (July)	1,891,715	81,983	17,572
	NASA (August)	1,569,898	75,058	6,530
	ClarkNet (August)	1,654,929	90,516	6,075
	ClarkNet (September)	1,673,794	94,787	7,239
	Saskatchewan	2,408,625	162,523	52,695

Table 2 Statistics

 2

of real data traces.

ACKNOWLEDGMENTS

The authors would like to warmly thank Sébastien Gambs for his valuable discussions at the early steps of this work [20].

Emmanuelle Anceaume received her Phd degree in Computer Science from the University Paris-Orsay (Paris-XI -France) for her work on dependability systems. She then spent one year at Cornell University and worked on unreliable failure detectors. She is a CNRS researcher at IRISA-UMR6074 lab. Her main research interests are in the field of distributed systems and algorithms with a focus on fault tolerance issues. In the context of dynamic and scalable systems, she is currently investigating dependability and security issues.

Yann Busnel is currently an Associate Professor in University of Nantes (France), involved in the Large-Scale Data Management team. He obtained his PhD degree in Computer Science in 2008 from the University of Rennes (France). Then, in 2009, he spent one year as a Researcher at MIDLAB, involved in the distributed systems research group of the University of Rome "La Sapienza" (Italy). He works essentially on very large scale dynamic distributed algorithm and data management in large-scale systems. He also a referee of several international journal and conferences.


Sana Damak Mallouli
email: sana.mallouli@gmail.com

Saïd Assar
email: said.assar@it-sudparis.eu

Enacting a Requirement Engineering Process with Meta-Tools: an Exploratory Project

Keywords: meta-modeling, intentional process modeling, meta-CASE, MetaEdit+, execution semantics. I

An engineering process can hardly be described rigorously because of its dynamic and decision-oriented nature. Applying goal-oriented modeling for representing such processes is a promising approach. However, goal-oriented process models have no clear operational semantics, and building an enactment engine for such models is a highly complex task. To avoid building such tools in an ad-hoc manner and to overcome maintainability and portability issues, we investigate in this paper the practical feasibility of meta-CASE and CAME based approaches for constructing an enactment tool for a goal-oriented model. We describe and analyze a project in which MetaEdit+, a leading meta-tool, is tested. Our aim is to evaluate the meta-tool approach and to explore its possibilities in terms of process model enactment. During this project, a requirement elicitation process is used as a preliminary test bed.

INTRODUCTION

Goal modeling is a prominent design paradigm in various domains such as business process modeling [START_REF] Bider | Goal-oriented business process modeling: Guest Editorial[END_REF], method engineering [START_REF] Ralyté | An Approach for Method Reengineering[END_REF], and requirements engineering [START_REF] Lapouchnian | Goal-oriented requirements engineering: An overview of the current research[END_REF]. In the method engineering context, the highly dynamic and decision-oriented nature of engineering processes has led to describe such processes using goal-oriented models [START_REF] Si-Said | Formalising Guidance for the CREWS Goal-Scenario Approach to Requirements Engineering[END_REF]. The main advantage of goal-oriented process modeling is its ability to go beyond the simple modeling of sequences of activities as proposed by other notations such as BPMN (Business Process Model and Notation) or SPEM (Systems Process Engineering Meta-model). However, how to enact goal-oriented models and how such enactment can be specified and implemented are still open research questions.

The general topic of this paper is how to construct a tool that provides enactment mechanisms for goal-oriented process models. In previous research projects, our research team has engineered multiple tools for earlier event-oriented methods [START_REF] Rolland | The RUBIS system[END_REF], context-oriented [START_REF] Si-Said | MENTOR: A Computer Aided Requirements Engineering Environment[END_REF], and goal-oriented methodological processes [START_REF] Souveyet | Process centred approach for developing tool support of situated methods[END_REF]. As these tools were built in an ad-hoc manner, recurrent problems have shown up. Maintainability is a key issue: as product and process metamodels are hard coded, it is very difficult to make the tools evolve when the meta-models are changed, even slightly. Portability is a bottleneck too: any evolution of the underlying technology makes the tool rapidly obsolete unless large updates are made to the code. Therefore, we have decided to investigate the possibility of using method engineering tools to solve these issues.

Meta-CASE and Computer Aided Method Engineering (CAME) technologies were introduced in the 90's as an answer to the general problem of providing software support to method and tool customization and/or creation [START_REF] Kelly | Evolution and issues in metaCASE[END_REF]. These meta-tools were expected to facilitate and to accelerate the production of method toolset, and to overcome maintainability and portability drawbacks. As any other software artifacts, tools and meta-tools need to be assessed and evaluated [START_REF] Gray | Issues in software engineering tool construction[END_REF]. However, research works that review meta-CASE/CAME tools are rather limited. Prominent evaluations are early works by Martiin & al. [START_REF] Marttiin | A comparative review of CASE shells: A preliminary framework and research outcomes[END_REF] [START_REF] Marttiin | A functional framework for evaluating method engineering environments: the case of Maestro II/Decamerone and MetaEdit+[END_REF]. Although more recent, works in [START_REF] Van De Veerd | An evaluation of computerized tools for method construction[END_REF] [START_REF] Niknafs | Computer-Aided Method Engineering: An Analysis of Existing Environments[END_REF] are not fundamentally different from earlier studies. In [START_REF] Van De Veerd | An evaluation of computerized tools for method construction[END_REF], the evaluation framework is inspired by Martiin & al. [START_REF] Marttiin | A comparative review of CASE shells: A preliminary framework and research outcomes[END_REF], and the results are limited to general appreciations. The study in [START_REF] Niknafs | Computer-Aided Method Engineering: An Analysis of Existing Environments[END_REF] is more detailed, but some studied tools are technically not available anymore (e.g., Mentor [START_REF] Si-Said | MENTOR: A Computer Aided Requirements Engineering Environment[END_REF]). The novelty lies in the evaluation framework; it is based on ISO 9126 quality model with more usability and portability concerns.

What emerge from these previous studies is that when it comes to process enactment, there is clearly not enough empirical knowledge about the use of meta-tool in real cases. Authors claim that support for process modeling is insufficient, and that mechanisms for expressing process enactment are limited or inexistent. So the goal of this paper is to experiment meta-CASE technology for enacting a goaloriented process, and to explore problems and issues related with such an approach. More precisely, this paper deals with the following research question: To which extent do metatools provide a viable and satisfying solution to the problem of building a maintainable and portable enactment engine for a goal-oriented formalism?

To answer this question, we empirically evaluate through a lab project MetaEdit+, a well-known meta-tool. This metatool was selected to run the project because it is recognized as a leading method engineering environment with high level of technical maturity [START_REF] Niknafs | Computer-Aided Method Engineering: An Analysis of Existing Environments[END_REF] [START_REF] Kelly | Domain-specific modeling: enabling full code generation[END_REF]. The project consisted in using MetaEdit+ to define a goal-oriented formalism and to construct an enactment tool to support it. Evaluation relied on inspecting the obtained system at the end of the project, and on analyzing data gathered along the engineering process. The evaluation is based on a quality framework that is synthesized from related works analysis. The framework is organized around three perspectives (Table 1): the proposed formalism for expressing the process enactment semantics, the meta-tools available for specifying the process, and the obtained target tool for process enactment. The rest of the paper is structured as follows. In Section 2, we briefly present works that are related to our research. Section 3 describes the Map formalism on which is based the project. In Section 4, the project itself is described. Section 5 presents the outcomes of the project in terms of meta-models and tool specifications, describes the obtained target tool and illustrates with a requirements elicitation process taken from the literature. Section 6 reports our evaluation of the project's outcomes using the quality framework. The paper ends with concluding remarks in which we discuss the results in regard with the research question, and we formulate revised research questions.

II. RELATED WORK

Providing process specification and enactment support is very important for Software and Method engineering fields. In this context, the Moskitt4ME approach [START_REF] Cervera | The MOSKitt4ME Approach: Providing Process Support in a Method Engineering Context[END_REF] is a relevant solution where process models are initially expressed using SPEM meta-model, then transformed into BPMN models. The BPMN process description can then be enacted using an off-the-shelf execution engine called "Activiti Engine".

Our research question is similar to the issue addressed in Moskitt4ME approach. However, our solution has two main particularities: (1) first, we use a goal-oriented process modeling language to capture fine grained software engineering processes and to go beyond what SPEM based approaches can do; (2) second, our target is to design a CAME tool itself and to adopt meta-models driven development in order to guarantee maintainability and portability.

Another recent work dealing with enactment process is presented in [START_REF] Bendraou | Definition of an Executable SPEM 2.0[END_REF]. This work proposes xSPEM tools (i.e., executable SPEM) for editing, simulating and verifying SPEM process models. The approach is based on dynamic meta-modeling (i.e., the definition of domain specific languages with behavioral semantics) in order to simulate and validate models. The basic idea is to extend the metamodel and assimilate its execution semantics to that of statebased machines and workflows.

xSPEM allows the simple modeling of sequences of activities. Thus, it is not well suited to represent engineering processes. For this reason, we are investigating goal-oriented process enactment in this paper.

III. THE MAP FORMALISM

Our research work concerns the Map formalism, a goaloriented model that is particularly well adapted for representing engineering processes. Based on the intention paradigm [START_REF] Rolland | Capturing System Intentionality with Maps[END_REF], the Map captures the intentions that a process is expected to fulfill, together with a set of available strategies to realize these intentions (Fig. 1a). Each intention can be realized by one or more strategy, and the process is represented as a labeled graph with intentions as nodes and strategies as edges [START_REF] Rolland | A Multi-Model View of Process Modelling[END_REF]. An edge enters a node if its strategy can be used to achieve the intention of the node. A section of the Map is a triplet composed of a source intention, a target intention and a strategy (e.g., <J, S JK1 , K> in Fig. 1a). Map operational semantics. Beyond precedence relationships between intention achievements, the operational semantics of the Map are decision-oriented. The combination of a past intention achievement, a strategy and an intention (i.e., the triplet <Jri 2 , SJL 1 , L> in Fig. 1b) is called a candidate section and is a fundamental concept for expressing the operational semantics. At each execution of a section, a new set of candidate sections (i.e., sections that can be executed in the next step) is computed. Given a certain state of the working products (i.e., the set of product instances,) and the history of achieved intentions, the candidate sections computation is done by checking which sections match with scheduling possibilities [START_REF] Edme | A proposal for intentional modeling and guiding of information system usage[END_REF].

IV. PROJECT OVERVIEW

The chosen meta-tool for the project is MetaEdit+ [START_REF]MetaCASE[END_REF]. Figure 2 presents an overview of the project's main steps. The method engineer defines meta-models (product and process) using MetaEdit+ Workbench toolset and the GOPRR (Graph, Object, Property, Relationship, Role) metamodeling concepts, and specifies generation rules with Merl scripting language. A customized version of MetaEdit+ editor is automatically constructed (i.e., target tool) this tool includes code generation functionalities. The method user can then use this tool to define a product and a process model, and generates an enactment engine.

The project was run with the requirement elicitation process underlying CREWS L'Ecritoire [START_REF] Rolland | Guiding goal modeling using scenarios[END_REF] [START_REF] Souveyet | Process centred approach for developing tool support of situated methods[END_REF]. Goal discovery and scenario authoring are complementary activities with CREWS L'Ecritoire: once a goal is discovered, a scenario is authored as a possible concretization of the goal, and can then be followed by further goal discovery from the authored scenario.

These goal-discovery/scenario-authoring sequences are repeated to incrementally populate the requirement chunks hierarchy (a Requirement Chunk (RC) is defined as a <goal, scenario> couple). The underlying RC elicitation process is described as a map.

This project was conducted by a group of three persons: a senior researcher, a PhD student and a master student. The senior researcher controlled the project, collected data and provided support all along the project in case of specific problems. The PhD student defined the Map formalism with MetaEdit+ and provided assistance in expressing and validating Map operational semantics. The tasks of the MSc student were to specify the code generator in MetaEdit+ scripting language for the target platform (VB.NET and MS Access), and to run CREWS L'Ecritoire case example.

V. PROJECT OUTPUT

A. Meta-Modeling

For the product part, as the Map formalism does not specify product models, we defined a standard E/R style product meta-model. This meta-model is simple and is not presented here for the sake of space. Figure 3 presents the meta-model for the process part expressed in GOPRR. Boxes represent objects, diamonds represent relationships, and circles are roles. Intention and Strategy concepts are defined as objects. They are connected by two relationships (Strategy-to-Intention and Intention-to-Strategy) and, beyond name and identifier, have certain properties necessary for expressing operational semantics (i.e., "State" attributes). "Product fragment", "Product consumption" and "Product generation" are specific attributes which are added to the Map definition. They are necessary for expressing the behavior of a map when it is executed [START_REF] Assar | A behavioral perspective in meta-modeling[END_REF], and play an important role in computing candidate sections.

B. Target Tool for CREWS L'Ecritoire

The product model is simple; it contains three objects (i.e., a requirement chunk, a goal and a scenario) and three links (And, Or, Refine). For the sake of space, details are not presented here, but interested readers can refer to [START_REF] Rolland | A Multi-Model View of Process Modelling[END_REF]. 4 presents the requirement chunks elicitation process expressed as a map. Three intentions are defined together with a set of strategies to achieve them; this model is a slightly simplified version of the original process in [START_REF] Rolland | A Multi-Model View of Process Modelling[END_REF].

C. Enactment specification

Enactment of a specific map is handled by the generated Map engine. This engine is a VB.NET program which manipulates an MS Access DB. The executable code of the Map engine and the relational structure of the DB are product dependant, and will be constructed by the code generator according to the product model (i.e., requirement chunks) and to the process model (i.e., the map). Indeed, for each method, a specific Map engine is generated; however, the code generator is generic.

Figure 5 shows the structure of the engine's DB that is generated for the CREWS L'Ecritoire case. Tables in the "Process" group are generic and contain the map, those in the "Trace" group will contain the results of the execution (product dependant), and those in the "Product" group will contain product instances (i.e., requirement chunks). The dependency of the Map engine towards the product structure impacts also the generated algorithm for candidate sections computing, which is an essential element in the enactment process. This calculation is based on the content of the engine's DB. For each realized intention Ri in the trace, a set of candidate sections is calculated by linking Ri to the corresponding intention I in the process map, and identifying all connecting strategies and connected intentions which form a possible path from Ri.

Figure 6 presents a screen shot of Map engine execution for CREWS L'Ecritoire case. From left to right top down, the 1st window contains the list of executed sections, the 2nd contains the stack of achieved intentions, the content in the 3rd window is static as it contains the sections of the process map under execution, and the last window contains the dynamically computed list of candidate sections.

VI. EVALUATION AND DISCUSSION

The quality framework (cf. Table 1) will now be used to evaluate and discuss the project results and outcomes. Results are synthesized in Table 2.

A. Formalism and meta-tool

For the process part, suitability and usability are clearly insufficient. Operational semantics are specified through a collection of scripts written in Merl (MetaEdit+ scripting language). These scripts define navigation logic through the meta-models and output (i.e., generate) instruction in target code (i.e., VB.NET). This step is very complex, and must be handled in two sub steps: write, run and debug first the target code for a sample Map engine DB, and when this code is satisfying, adapt it and integrate it into Merl generation scripts. Errors in the generated code are very hard to be directly corrected in the generating Merl scripts. Although the meta-tool provides a debugging facility, it is largely insufficient when the generated code becomes complex. The cognitive effort for correlating the generated code with procedures for generating such code (i.e., Merl scripts writing) was so high that the whole project team needed to cooperate frequently on this task.

B. Target tool

According to the project team perception, the obtained Map engine operates correctly and is easy to use, as the possibilities for interactions are limited to choosing a candidate section and inputting some data. However, the user interface is much less attractive although the Map enactment is made sufficiently clear through textual display windows (Fig. 6). This can be enhanced; it will however make the generated code and the generation scripts much more complex and less portable.

Concerning target tool maintainability, the scoring is mitigated. Any change to the Map formalism which does not impact the operational semantics is easily handled with MetaEdit+'s graphical interface and with small updates to the generated code. However, if the modification changes the operational semantics, the impact on the generated code can then be much larger. The portability issue is strategically more important as it impacts tool mid and long term existence. The scoring here is unsatisfactory because, although it is fully possible to update the generating scripts and the generated code to accommodate a new version of the target platform (e.g., a new version of VB) or a different platform (i.e., MySQL DBMS), the cost of this task is high. However, compared with an ad-hoc approach, the project is insufficient to get a real insight about the comparative advantage of using meta-CASE in terms of portability.

VII. CONCLUDING REMARKS

In this paper, we have reported an experimental development project dedicated to evaluating the contribution of meta-CASE to the enactment of Map, a goal-oriented process modeling formalism. As "building a system in and of itself does not constitute research", the contribution to basic research is "the synthesis of new concepts in a tangible product" [START_REF] Nunamaker | Systems development in information systems research[END_REF]. What we learned from this experience is resumed in the two following. First, providing mechanisms for enacting a goal-oriented process is possible only if operational semantics canat the conceptual levelbe expressed using the execution paradigm underlying a certain target platform. This is line with recent work about the necessity to raise the level of abstraction of compilation techniques up to the modeling phase [START_REF] Bendraou | Achieving process modeling and execution through the combination of aspect and model-driven engineering approaches[END_REF]. Second, in the Map case, building a generic Map engine is impossible as the algorithm for candidate section computation is product dependant. Meta-CASE technology provides thus an interesting possibility to overcome this problem by combining CASE customization and the design of adequate code generators. This opens the door to multiple applications in the field of Domain Specific Languages, CASE tool construction and process enactment.

A. Threats to validity

Some threats to the validity of this study are: the limitation to only one project, the dependence on participants' background, and the mix between development team and observation team.

B. Research question revisited

In meta-CASE actual technology, process operational semantics are expressed in a procedural manner in code generating scripts, and process enactment is obtained through the execution of generated code. These specifications are loosely correlated with the meta-modeling part, they are not specified in a declarative manner and they cannot be represented graphically. They are difficult to build and to validate. Indeed, like in compiler technology, the validity of the code generator cannot be demonstrated unless some formal notations are used, or the code generator itself is built using some generic tool. Thus, we revise our research question into: How to express in a rigorous manner process operational semantics at the meta-modeling level of abstraction in order to facilitate its validation and evolution? This is the subject of our actual research work. We are investigating graphical notations for expressing meta-models' operational semantics.

Figure 1 .

 1 Figure 1. A map example (a), and an illustration of achieved intentions and candidate sections (b)

Figure 2 .

 2 Figure 2. Overview of the engineering process underlying the exploratory project

Figure 3 .

 3 Figure 3. Map process meta-model defined in GOPRR

Figure 4 .

 4 Figure 4. CREWS L'Ecritoire process model defined in the target tool

Figure

  Figure4presents the requirement chunks elicitation process expressed as a map. Three intentions are defined together with a set of strategies to achieve them; this model is a slightly simplified version of the original process in[START_REF] Rolland | A Multi-Model View of Process Modelling[END_REF].

Figure 5 .

 5 Figure 5. Database structure of the Map engine for CREWS L'Ecritoire

Figure 6 .

 6 Figure 6. Interface for the generated target tool

TABLE I .

 I META-CASE EVALUATION FRAMEWORK Level of maintainability gains for the target meta tool  Level of portability gains for the target meta tool

	Perspective Formalism Meta-tool Target tool	Criteria  Level of expressiveness for process specification  Cognitive effort to specify the process part  Suitability for process specification  Ease of use for process specification 

TABLE II

 II

		.	PROJECT EVALUATION RESULTS
	Perspective Formalism	Criteria Expressiveness  Insufficient: execution semantics is Evaluation result
				expressed using a large set of
		procedural scripts Cognitive effort  Very high: the language designer must
				mentally correlate code generation
				actions (i.e., Merl scripts) with
	Meta-tool	Suitability		generated code (i.e., VB.net code)  Low: a simple text editor for
				developing generation scripts, there is
		no model nor a GUI Ease of use  Low: the validation of a script is very
				hard, with only a limited debugging
	Target tool	Maintainability	facility  Satisfactory in case of modifications to
				the PLM that do not alter its execution
				semantics; unsatisfactory otherwise,
				because of complex changes to code
		Portability		generation scripts  Unsatisfactory: moving to a different
				target platform induces high level of
				changes to code generation scripts