Samir Adly

Ba Khiet Le

Unbounded Second-Order State-Dependent Moreau's Sweeping Processes in Hilbert Spaces

Keywords: Moreau's sweeping process, Quasi-variational inequalities, Differential inclusion

In this paper, an existence and uniqueness result of a class of second-order sweeping processes, with velocity in the moving set under perturbation in infinitedimensional Hilbert spaces, is studied by using an implicit discretization scheme. It is assumed that the moving set depends on the time, the state and is possibly unbounded. The assumptions on the Lipschitz continuity and the compactness of the moving set, and the linear growth boundedness of the perturbation force are weaker than the ones used in previous papers.

Introduction

In 1971, the sweeping process was introduced and deeply studied by J. J. Moreau in a series of papers (see, e.g., [START_REF] Moreau | Rafle par un convexe variable I, Sém[END_REF][START_REF] Moreau | Rafle par un convexe variable II[END_REF][START_REF] Moreau | Evolution problem associated with a moving convex set in a Hilbert space[END_REF][START_REF] Moreau | Numerical aspects of the sweeping process[END_REF]). This kind of problems plays an important role in elasto-plasticity, quasi-statics and nonsmooth dynamics with unilateral con-straints. Roughly speaking, a point is swept by a moving closed and convex set, which depends on time in a Hilbert space and can be formulated in the form of first-order differential inclusion involving normal cone operators. Sweeping processes represent a nice and powerful mathematical framework for many nonsmooth dynamical systems, including Lagrangian systems. There are plenty of existence and uniqueness results (see, e.g., [START_REF] Adly | Convex sweeping process in the framework of measure differential inclusions and evolution variational inequalities[END_REF][START_REF] Bounkhel | State dependent sweeping process in p-uniformly smooth and q-uniformly convex Banach spaces[END_REF][START_REF] Bounkhel | First and second order convex sweeping processes in reflexive smooth Banach spaces[END_REF][START_REF] Edmond | Relaxation of an optimal control problem involving a perturbed sweeping process[END_REF][START_REF] Edmond | BV solutions of nonconvex sweeping process differential inclusions with perturbation[END_REF][START_REF] Kunze | An introduction to Moreau's sweeping process[END_REF]) for variants of first-order sweeping processes in the literature. The second-order sweeping processes have been also considered by many authors (see, e.g., [START_REF] Bounkhel | First and second order convex sweeping processes in reflexive smooth Banach spaces[END_REF][START_REF] Kunze | An introduction to Moreau's sweeping process[END_REF][START_REF] Castaing | Quelques problèmes d'évolution du second ordre[END_REF][START_REF] Castaing | Evolution equations governed by the sweeping process[END_REF][START_REF] Bounkhel | General existence results for second order nonconvex sweeping process with unbounded perturbations[END_REF][START_REF] Bounkhel | Existence results on the second-order nonconvex sweeping processes with perturbations[END_REF]). In [START_REF] Castaing | Quelques problèmes d'évolution du second ordre[END_REF], Castaing studied for the first time the second-order sweeping processes, where the moving set depends on the state with convex, compact values. Let us note that the boundedness assumption on the moving set for the second-order case is essential in most previous works: see, for example, some recent papers [START_REF] Bounkhel | First and second order convex sweeping processes in reflexive smooth Banach spaces[END_REF][START_REF] Kunze | An introduction to Moreau's sweeping process[END_REF][START_REF] Bounkhel | General existence results for second order nonconvex sweeping process with unbounded perturbations[END_REF][START_REF] Bounkhel | Existence results on the second-order nonconvex sweeping processes with perturbations[END_REF]. In [START_REF] Castaing | Some contributions to nonconvex sweeping process[END_REF] , Castaing et al. considered the possibly unbounded moving set satisfying the classical Lipschitz continuity assumption with respect to Hausdorff distance. However, it is difficult for unbounded set to hold this assumption since the Hausdorff distance of two unbounded sets may equal the infinity, for example, the case of rotating hyperplane. In this paper, we propose an implicit discretization scheme based on the Moreau's catching-up algorithm [START_REF] Moreau | Evolution problem associated with a moving convex set in a Hilbert space[END_REF] with different techniques to analyze the second-order sweeping processes under perturbation in Hilbert spaces. The moving set depends on the time, the state and is possibly unbounded. The set is supposed to be closed, convex and to have a Lipschitz variation of intersection with some particular ball (with a Lipschitz constant depending on the radius of the ball). It is obvious that this kind of Lipschitz continuity assumption is more feasible than the classical one for the unbounded moving set. The perturbation force is supposed to be upper semicontinuous with convex and weakly compact values and only need to satisfy the weak linear growth condition (i.e., the intersection between the perturbation force and the ball with linear growth is nonempty). In addition, the compactness assumption on the moving set is weaker than the one used in previous works [START_REF] Bounkhel | First and second order convex sweeping processes in reflexive smooth Banach spaces[END_REF][START_REF] Kunze | An introduction to Moreau's sweeping process[END_REF][START_REF] Bounkhel | General existence results for second order nonconvex sweeping process with unbounded perturbations[END_REF][START_REF] Bounkhel | Existence results on the second-order nonconvex sweeping processes with perturbations[END_REF][START_REF] Castaing | Some contributions to nonconvex sweeping process[END_REF], since it only requires to check the Kuratowski measure of noncompactness for a fixed ball. We also consider the case when the moving set is anti-monotone (which replaces the compactness assumption) as in [START_REF] Bounkhel | Existence results on the second-order nonconvex sweeping processes with perturbations[END_REF] under the current settings. Our methodology is based on convex and variational analysis [START_REF] Rockafellar | Convex Analysis[END_REF][START_REF] Rockafellar | Variational Analysis[END_REF].

The paper is organized as follows. In Sect. 2, we recall some basic notations, definitions and useful results which are used throughout the paper. The existence and uniqueness of solutions are thoroughly analyzed in Sect. 3. Some conclusions end up the paper in Sect. 4.

Notation and Preliminaries

We begin with some notations used in the paper. Let H be a real Hilbert space. Denote by •, • , • the scalar product and the corresponding norm in H . Denote by I the identity operator, by B the unit ball in H . The distance from a point x to a set K is denoted by d(x, K ). If K is closed and convex, then for each x ∈ H , there exists uniquely a point y ∈ K which is nearest to x and set y := proj(K ; x). The normal cone of K is given by

N K (x) := { p ∈ H : p, y -x ≤ 0, for all y ∈ K }.
The support function of K is defined as follows

σ (K ; z) := sup x∈K x, z , z ∈ H. It is not difficult to see that z ∈ N K (x) if and only if σ (K ; z) = z, x and x ∈ K .
The Hausdorff distance between the sets A and B is given by for some L C > 0. Set

d H (A; B) := max{e(A, B); e(B, A)}, ( 1
)
Φ(v) := T 0 σ C(s); v(s) ds for v ∈ L ∞ ([0, T ]; H ). ( 2
)
Then, Φ is weakly lower semicontinuous, i.e.,

Φ(v) ≤ lim inf n→+∞ Φ(v n ),
where v n → v in weak-star topology of L ∞ ([0, T ]; H ).
The following lemma is a discrete version of Gronwall's inequality.

Lemma 2.2 Let α > 0 and (u n ), (β n ) be nonnegative sequences satisfying

u n ≤ α + n-1 k=0 β k u k ∀n = 0, 1, 2, . . . (with β -1 := 0). ( 3
)
Then, for all n, we have

u n ≤ α exp n-1 k=0 β k .
Finally, we recall the Kuratowski measure of noncompactness for a bounded set B in H , which is defined as follows

γ (B) := inf r > 0 : B = n i=1
B i for some n and B i with diam(B i ) ≤ r .

One has the following lemma (see, e.g., [START_REF] Deimling | Multivalued Differential Equations[END_REF]Proposition 9.1]).

Lemma 2.3 Let B 1 and B 2 be bounded sets of the infinite-dimensional Hilbert space H . Then,

(i) γ (B 1 ) = 0 ⇔ B 1 is relative compact. (ii) If B 1 ⊂ B 2 , then γ (B 1 ) ≤ γ (B 2 ). (iii) γ (B 1 + B 2 ) ≤ γ (B 1 ) + γ (B 2 ).
(iv) γ (x 0 + r B) = 2r for some x 0 ∈ H and r > 0.

Main Result

In this section, the existence and uniqueness of solutions of the following second-order sweeping processes

(S) ⎧ ⎨ ⎩ ü(t) ∈ -N C(t,u(t)) ( u(t)) -F(t, u(t), u(t)) a.e. t ∈ [0, T ], u(0) = u 0 , u(0) = v 0 ∈ C(0, u 0 ),
are analyzed thoroughly under weaker assumptions, by using an implicit discretization scheme and techniques different from previous works. The moving set C is supposed to be nonempty, closed, convex and to have a Lipschitz variation of intersection with some particular ball. The perturbation force F is upper semicontinuous with convex, weakly compact values and satisfies the weak linear growth condition. For details, let us make the assumptions below. Let H be a real Hilbert space and let be given

u 0 ∈ H, v 0 ∈ C(0, u 0 ).
Remark 1 Let us consider the simple case when C(•) depends only on t and is expressed in the form of unilateral inequality constraints, i.e.,

C(t) = {x ∈ R n : g 1 (t, x) ≤ 0, . . . , g m (t, x) ≤ 0}, (4)
where function g k : [0, T ] × R n → R is supposed to be of class C 1 for each k = 1, 2, . . . , m. Clearly, the convexity of the functions g k implies the convexity of the set C(t). In order to go beyond the convexity assumption of the set C(•), the class of prox-regular sets is more appropriate. However, the sublevels of prox-regular functions and levels of differentiable mappings with Lipschitz derivatives may fail to be prox-regular. We need some qualification conditions on the functions g k to ensure the prox-regularity of the set C(t) (see [START_REF] Adly | Preservation of prox-regularity of sets with application to constrained optimization[END_REF] for more details). In the present paper, we will content ourselves with the convexity assumption.

The following assumptions will be useful.

Assumption 1 (i) For all t ∈ [0, T ] and x ∈ H , C(t, x) ⊂ H is nonempty, closed, convex and there exists L C > 0 such that

Γ (t, x, s, y) ≤ L C (|t -s| + x -y ), (5)
for all s, t ∈ [0, T ] and x, y ∈ M 1 B where

(t, x, s, y) := ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ d H C(t, x) ∩ M 1 B; C(s, y) ∩ M 1 B , if C(t, x) ∩ M 1 B = ∅, C(s, y) ∩ M 1 B =∅, e C(t, x) ∩ M 1 B; C(s, y) , if C(t, x) ∩ M 1 B = ∅, C(s, y) ∩ M 1 B =∅, 0, if C(t, x) ∩ M 1 B = ∅, C(s, y) ∩ M 1 B =∅,
and

M 1 := 1 + u 0 + v 0 + (L C + 2L F )T + e (L C +2L F +1)T . ( 6
) (ii) For all t ∈ [0, T ], C(t, M 1 B) ∩ 2M 1 B is relatively compact in H , or equivalently γ C(t, M 1 B) ∩ 2M 1 B = 0, ( 7
)
where γ is the Kuratowski measure of noncompactness.

Assumption 2

The set-valued mapping F : gph(C) ⇒ H is upper semicontinuous with convex, weakly compact values in H and satisfies the weak linear growth condition, i.e., there exists L F > 0 such that, for all t ∈ [0, T ], x ∈ H and y ∈ C(t, x), then

F(t, x, y) ∩ L F (1 + x + y )B = ∅. (8)
Here gph(C) denotes the graph of C. Now we are ready for the main result.

Theorem 3.1 (Existence) Let H be a Hilbert space and let Assumptions 1, 2 hold. Then, for given initial condition u 0 ∈ H, v 0 ∈ C(0, u 0 ), there exists a solution u in the following sense

1. (S) is satisfied for a.e. t ∈ [0, T ]; 2. u(0) = u 0 , u(0) = v 0 ; 3. u ∈ C 1 ([0, T ]; H ) and ü ∈ L ∞ ([0, T ]; H ).
Proof We choose some positive integer n such that M 1 T /n < 1 and set h n := T /n,

t n i := ih for 0 ≤ i ≤ n. For 0 ≤ i ≤ n -1, given u n i and v n i , we want to find u n i+1 , v n i+1 satisfying v n i+1 -v n i h n + f n i ∈ -N C(t n i+1 ,u n i+1 ) (v n i+1 ), u n i+1 = u n i + h n v n i , (9)
where

f n i ∈ F(t n i , u n i , v n i ).
Clearly u n i+1 is defined uniquely in terms of u n i and v n i . The first line of ( 9) can be rewritten as

v n i+1 -v n i + h n f n i ∈ -N C(t n i+1 ,u n i+1 ) (v n i+1 ), ( 10
)
which is equivalent to

v n i+1 = proj C(t n i+1 , u n i+1 ); v i -h n f n i .
We have the algorithm to construct the sequences

(u n i ) n i=0 , (v n i ) n i=0 , ( f n i ) n i=0 as follows. Algorithm Initialization. Let u n 0 := u 0 , v n 0 := v 0 ∈ C(0, u 0 ), choose f n 0 ∈ F(0, u 0 , v 0 ) ∩ L F (1 + u 0 + v 0 )B. Iteration. One has current points u n i , v n i , f n i . Compute u n i+1 := u n i + h n v n i and v n i+1 := proj(C(t n i+1 , u n i+1 ); v n i -h n f n i ). ( 11
)
Then, choose

f n i+1 ∈ F(t n i+1 , u n i+1 , v n i+1 ) ∩ L F (1 + u n i+1 + v n i+1 )B and set i := i + 1.
The algorithm is well defined thanks to (i) of Assumption 1. Now we prove that the sequences

(u n i ) n i=0 , (v n i ) n i=0 , ( v n i+1 -v n i h n
) n i=0 and ( f n i ) n i=0 , generated by the algorithm above, are uniformly bounded. Particularly, we show that

u n i + v n i ≤ M 1 -1. ( 12
)
It is obviously true for i = 0. Suppose that (12) holds for up to some i ∈ {0, 1, . . . , n -1}, we will prove that (12) also holds for i + 1. Indeed, one has max{

u n i | , u n i+1 } ≤ M 1 and v n i+1 -v n i + h n f n i ≤ v n i+1 -v n i + h n f n i = d(C(t n i+1 , u n i+1 ); v n i ) + h n f n i ≤ e(C(t n i , u n i ) ∩ M 1 B; C(t n i+1 , u n i+1 )) + h n f n i ≤ (t n i , u n i , t n i+1 , u n i+1 ) + h n f n i ≤ h n L C (1 + v i ) + h n f n i (by using (i) of Assumption 1 ). ( 13
)
It implies that

v n i+1 ≤ v n i + h n L C (1 + v i ) + 2h n f n i ≤ v n i + h n L C (1 + v i ) + 2h n L F (1 + u n i + v n i ) ≤ v n i + h n L C + 2L F + 2L F u i + (L C + 2L F ) v i . ( 14
)
Consequently

v n i+1 ≤ v 0 + (i + 1)h n (L C + 2L F ) + h n 2L F i j=0 u j + (L C + 2L F ) i j=0 v j . ( 15
)
On the other hand

u n i+1 ≤ u n i + h n v n i ≤ . . . ≤ u 0 + h n i j=0 v j . ( 16
)
From ( 15) and ( 16), one has

u n i+1 + v n i+1 ≤ α + βh n i j=0 ( u j + v j ),
where

α = u 0 + v 0 + (L C + 2L F )T and β = L C + 2L F + 1. Using Lemma 2.
2, we obtain

u n i+1 + v n i+1 ≤ α + e βih n ≤ α + e βT = M 1 -1. (17)
Consequently, by induction we have

u n i + v n i ≤ M 1 -1, i = 1, 2, . . . , n. ( 18
)
On the other hand, one has

f n i ≤ L F (1 + u n i + v n i ) ≤ L F M 1 , i = 1, 2, . . . , n. ( 19
)
Furthermore, from (13) one draws that

v n i+1 -v n i h n ≤ L C (1 + v i ) + 2 f n i ≤ L C M 1 + 2L F M 1 = (L C + 2L F )M 1 =: M 2 , i = 1, 2, . . . , n. ( 20
)
In conclusion, the sequences (u n i ) n i=0 , (v n i ) n i=0 are uniformly bounded by M 1 (more precisely by M 1 -1) and (

v n i+1 -v n i h n ) n i=0 , ( f n i ) n i=0 are uniformly bounded by M 2 . We construct the sequences of functions (u n (•)) n , (v n (•)) n , ( f n (•)) n , (θ n (•)) n , (η n (•)) n from [0, T ] to H as follows: on [t n i , t n i+1 [ for 0 ≤ i ≤ n -1, we set u n (t) := u n i + u n i+1 -u n i h n (t -t n i ), v n (t) := v n i + v n i+1 -v n i h n (t -t n i ),
and

f n (t) := f n i , θ n (t) := t n i , η n (t) := t n i+1 . ( 21
)
Then, for all t ∈]t n i ,

t n i+1 [ un (t) = u n i+1 -u n i h n = v n i ∈ C(t n i , u n i ), vn (t) = v n i+1 -v n i h n ,
and max{ sup

t∈[0,T ] |θ n (t) -t|, sup t∈[0,T ] |η n (t) -t|} ≤ h n → 0 as n → +∞. (22)
The sequence v n (•) n is equi-Lipschitz with ratio M 2 since

vn (t) = v n i+1 -v n i h n ≤ M 2 .
Next we prove that the set (t) = {v n (t)} is relatively compact for all t ∈ [0, T ]. Suppose to the contrary that there exists t 0 ∈ [0, T ] such that (t 0 ) is not relative compact. Then, let 3σ := γ ( (t 0 )) > 0. Note that

(t 0 ) ⊂ M 1 B, hence 3σ = γ ( (t 0 )) ≤ γ (M 1 B) = 2M 1 , which particularly implies that σ ≤ M 1 . For each n, we can find i such that t 0 ∈ [t n i , t n i+1 [. Then, v n (t 0 ) -v n i = v n i+1 -v n i h n (t 0 -t n i ) ≤ M 2 h n . ( 23
)
On the other hand,

v n i ∈ C(t n i , u n i ) ∩ M 1 B ⊂ C(t 0 , u n i ) + L C h n B ⊂ C(t 0 , M 1 B) + L C h n B. Thus v n (t 0 ) ∈ C(t 0 , M 1 B) + (L C + M 2 )h n B.
We can find n 0 large enough such that, for all n ≥ n 0 , we have

(L C + M 2 )h n = (L C + M 2 )T /n ≤ σ. Furthermore for all n, v n (t 0 ) ≤ M 1 , hence v n (t 0 ) ∈ C(t 0 , M 1 B) ∩ (M 1 + σ )B + σ B ⊂ C(t 0 , M 1 B) ∩ 2M 1 B +σ B for all n ≥ n 0 . Note that the set C(t 0 , M 1 B) ∩ 2M 1 B is relative compact (Assumption 1), hence γ C(t 0 , M 1 B) ∩ 2M 1 B = 0. Then, by using Lemma 2.3, one has 3σ = γ (t 0 ) = γ ({v n (t 0 ) : n ≥ n 0 }) ≤ γ (C(t 0 , M 1 B) ∩ 2M 1 B) + σ B ≤ γ (C(t 0 , M 1 B) ∩ 2M 1 B) + γ (σ B) = 2σ,
which is a contradiction. Thus the set (t) = {v n (t), n ≥ 1} is relatively compact for all t ∈ [0, T ]. By applying the Arzelà-Ascoli theorem (see, e.g., [START_REF] Kunze | An introduction to Moreau's sweeping process[END_REF]), there exists a Lipschitz function v(•) : [0, T ] → H with Lipschitz constant M 2 and [START_REF] Tolstonogov | Sweeping process with unbounded nonconvex perturbation[END_REF].

• (v n ) converges strongly to v(•) in C([0, T ]; H ); • ( vn ) converges weakly to v(•) in L ∞ ([0, T ]; H ). In particular, v(0) = v 0 . Let u : [0, T ] → H, t → u(t) = u 0 + t 0 v(s)ds. Then, u(0) = u 0 , u = v and ü ∈ L ∞ ([0, T ]; H ). Let us show that u n (•) converges strongly in C([0, T ]; H ) to u(•). Indeed, we have max t∈[0,T ] u n (t) -u(t) = max t∈[0,T ] u n (0) + t 0 v n (θ n (s))ds -u(0) - t 0 v(s)ds = max t∈[0,T ] t 0 (v n (θ n (s)) -v n (s) + v n (s) -v(s))ds ≤ max t∈[0,T ] t 0 (M 2 |θ n (s) -s| + v n (s) -v(s) ds ≤ T 0 (M 2 |θ n (s) -s| + v n (s) -v(s) )ds → 0, as n → +∞ since v n (•) converges strongly to v(•) in C([0, T ]; H ) and
In next step, we prove that for every t ∈ [0, T ], u(t) ∈ C(t, u(t)). From the fact that v n i ∈ C(t n i , u n i ) for all i, we deduce for every t ∈ [0, T ] that

v n (θ n (t)) ∈ C θ n (t), u n (θ n (t)) ∩ M 1 B ⊂ C(t, u(t)) + L C {|θ n (t) -t| + u n (θ n (t)) -u(t) }B.
It is easy to see that for every t ∈ [0, T ], v n (θ n (t)) → v(t) = u(t) and |θ n (t) -t| + u n (θ n (t))u(t) → 0 as n → +∞ because of ( 22) and the strongly convergence

of v n (•) to v(t), u n (•) to u(•) in C([0, T ]; H ). Since C(t, u(t)) is closed, we obtain that u(t) ∈ C(t, u(t)) for every t ∈ [0, T ]. It remains to prove that ü(t) ∈ -N C(t,u(t)) ( u(t)) -F(t, u(t), u(t)) a.e. t ∈ [0, T ]. (24)
Let us define

D(t) := C(t, u(t)) ∩ M 1 B, ∀t ∈ [0, T ], (25)
then D is nonempty, closed and convex and for all t, s ∈ [0, T ], one has

d H D(t), D(s) ≤ L C (|t -s| + u(t) -u(s) ) ≤ L C (1 + M 1 )|t -s|. ( 26
)
From ( 9) we have, for almost every t ∈ [0, T ], that

vn (t) + f n (t) ∈ -N C η n (t),u n (η n (t)) v n (η n (t)) = -N D(η n (t)) v n (η n (t)) (since v n (η n (t)) ≤ M 1 -1). (27) Let γ n (t) := -[ vn (t) + f n (t)] for all t ∈ [0, T ]. (28)
Then, for all c ∈ D η n (t) , we get

γ n (t), c -v n (η n (t)) ≤ 0.
Hence

σ D η n (t) ; γ n (t) + -γ n (t), v n (η n (t)) ≤ 0.
Then, integrating on [0, T ], one obtains

T 0 σ D η n (t) ; γ n (t) dt + T 0 -γ n (t), v n (η n (t)) dt ≤ 0. ( 29
)
Let us begin by estimating the second term in (29). First we prove that

T 0 ü(t), u(t) dt = lim n→+∞ T 0 vn (t), v n (η n (t)) dt. ( 30
) Indeed T 0 ü(t), u(t) dt = 1 2 T 0 d dt u2 (t)dt = 1 2 (v 2 (T ) -v 2 (0)) = 1 2 lim n→+∞ v 2 n (T ) -v 2 n (0) = 1 2 lim n→+∞ T 0 d dt v 2 n (t)dt = lim n→+∞ T 0 vn (t), v n (t) dt.
Note that we also have

lim n→+∞ T 0 vn (t), v n (t) dt = lim n→+∞ T 0 vn (t), v n (η n (t)) dt, since T 0 vn (t), v n (t) -v n (η n (t)) |dt ≤ M 2 2 T 0 |t -η n (t)|dt → 0,
as n → +∞. So we get (30).

Since f n (t) ≤ M 2 for all t ∈ [0, T ], the sequence ( f n ) is bounded in L ∞ ([0, T ]; H ). Therefore we can extract a subsequence, without relabeling for simplicity, converging weakly to some mapping f (•) in L ∞ ([0, T ]; H ). On the other hand, v n (η n (•)) converges strongly to u(•) in L 1 ([0, T ]; H ), so one has

T 0 f (t), u(t)) dt = lim n→+∞ T 0 f n (t), v n (η n (t)) dt. ( 31
)
From ( 30) and ( 31), one deduces that

T 0 v(t) + f (t), u(t) dt = lim n→+∞ T 0 -γ n (t), v n (η n (t)) dt. ( 32
)
For the first term in (29), we will show that

T 0 σ D(t); -v(t) -f (t) dt ≤ lim inf n→+∞ T 0 σ D η n (t) ; γ n (t) dt. ( 33
)
Let us recall that (Lemma 2.1) the convex function

x(•) → T 0 σ D(t); x(t) dt is weakly lower semicontinuous in L ∞ ([0, T ]; H ) and γ n (t) = -[v n (t) + f n (t)] for all t ∈ [0, T ]. In addition, vn (•), f n (•) weakly converges to v(•), f (•) in L ∞ ([0, T ]; H ), respectively. Consequently, one implies that γ n (•) → -v(•) -f (•) weakly in L ∞ ([0, T ]; H ). Therefore T 0 σ D(t); -v(t) -f (t) dt ≤ lim inf n→+∞ T 0 σ D(t); γ n (t) dt. ( 34
)
On the other hand

D(t) ⊂ D η n (t) + L C (1 + M 1 )|t -η n (t)|B ⊂ D η n (t) + L C (1 + M 1 )h n B.
Hence

T 0 σ D(t); γ n (t) dt ≤ T 0 σ D η n (t) ; γ n (t) dt + L C (1 + M 1 )h n T 0 γ n (t) dt ≤ T 0 σ D η n (t) ; γ n (t) dt + 2L C (1 + M 1 )T M 2 h n .
It leads to the following inequality

lim inf n→+∞ T 0 σ D(t); γ n (t) dt ≤ lim inf n→+∞ T 0 σ D η n (t) ; γ n (t) dt. (35)
From ( 34) and (35), we get the desired result (33). From (29), ( 32) and (33), we deduce that

T 0 σ D(t); -v(t) -f (t) dt + T 0 v(t) + f (t), u(t) dt ≤ 0. (36)
Note that u(t) ∈ D(t) for every t ∈ [0, T ], we have

σ (D(t); -v(t) -f (t)) + v(t) + f (t), u(t) ≥ 0 a.e. t ∈ [0, T ]. (37)
From ( 36) and (37), one infers that

σ D(t); -v(t) -f (t) + v(t) + f (t), u(t) = 0 a.e. t ∈ [0, T ], (38)
or equivalently,

ü(t) + f (t) ∈ -N D(t) u(t) = -N C(t,u(t)) u(t) a.e. t ∈ [0, T ]. (39)
On the other hand, one has

f n (t) ∈ F θ n (t), u n (θ n (t)), v n (θ n (t)
) for all t ∈ [0, T ] and F is upper semicontinuous with convex and weakly compact values in H . Classically, we obtain that f (t) ∈ F t, u(t), u(t) for almost all t ∈ [0, T ] (see, e.g., [21, Theorem V-14]). Thus

ü(t) ∈ -N C(t,u(t)) u(t) -F t, u(t), u(t) a.e. t ∈ [0, T ]. (40)
The result has been proved.

Remark 2 (i) It is obvious that the result is still true if we replace Assumption 1-(i) by the classical Lipschitz continuity assumption (see, e.g., [START_REF] Castaing | Some contributions to nonconvex sweeping process[END_REF]):

d H C(t, x); C(s, y) ≤ L C (|t -s| + x -y ), ∀ 0 ≤ t, s ≤ T and x, y ∈ H for some constant L C > 0. (41)
However, it is difficult for unbounded set to hold this kind of assumption, since the Hausdorff distance of two unbounded sets may equal the infinity. For example, the rotating hyperplane never satisfies (41), but satisfies Assumption 1-(i) with suitable parameters. This observation was also stated in [START_REF] Tolstonogov | Sweeping process with unbounded nonconvex perturbation[END_REF], when the author studied the first-order sweeping processes with the convex moving set depending on the time. Note that in our paper, the local Lipschitz variation of the moving set is assumed in a fixed ball, while in [START_REF] Tolstonogov | Sweeping process with unbounded nonconvex perturbation[END_REF], it is necessary to consider in any ball. Particularly, if F ≡ 0 and 0 ∈ C(t, x) for all t ∈ [0, T ] and x ∈ H , then (5) can be replaced by

d H C(t, x) ∩ M 1 B; C(s, y) ∩ M 1 B ≤ L C (|t -s| + x -y ), (42)
where M 1 := u 0 + v 0 T . Indeed, from [START_REF] Castaing | Quelques problèmes d'évolution du second ordre[END_REF] and 0 ∈ C(t i+1 , v n i+1 ) one has

v n i -v n i+1 , 0 -v n i+1 ≤ 0 ⇒ v n i+1 ≤ v n i ≤ . . . ≤ v 0 .
Thus

u n i ≤ u n i-1 + h n v n i-1 ≤ . . . ≤ u 0 + v 0 T.
(ii) The compactness assumption on the moving set C is also weaker than the one used in previous works [START_REF] Bounkhel | First and second order convex sweeping processes in reflexive smooth Banach spaces[END_REF][START_REF] Kunze | An introduction to Moreau's sweeping process[END_REF][START_REF] Bounkhel | General existence results for second order nonconvex sweeping process with unbounded perturbations[END_REF][START_REF] Bounkhel | Existence results on the second-order nonconvex sweeping processes with perturbations[END_REF][START_REF] Castaing | Some contributions to nonconvex sweeping process[END_REF] since it only requires to check the Kuratowski measure of noncompactness for a fixed ball. Furthermore, the perturbation force F only needs to satisfy the weak linear growth condition. (iii) In many applications, in practice, the set C(•) could be unbounded. This is the case, e.g., when C(•) coincides with a moving convex and closed cone. Such systems are called nonlinear complementarity systems and are of great interest in the modeling of nonregular electrical systems (see, e.g., Section 3.4 in [START_REF] Adly | Convex sweeping process in the framework of measure differential inclusions and evolution variational inequalities[END_REF]). (iv) The compactness assumption can be replaced by the anti-monotonicity of C as in [START_REF] Bounkhel | Existence results on the second-order nonconvex sweeping processes with perturbations[END_REF]. Again, one does not need the boundedness and the classical Lipschitz continuity of C.

(t) = u m (t) -u n (t), um (t) -un (t) = u m (t) -u n (t), v m i -v n j .
We have

v m i ∈ C(t m i , u m i )∩ M 1 B ⊂ C(t, u m i )+h m L C B, v n j ∈ C(t n j , u n j ) ⊂ C(t, u n j )+ h n L C B.
From the monotonicity of -C(t, •) and the boundedness of u m i , u n j by M 1 , one has

v m i -v n j , u m i -u n j ≤ 2M 1 L C (h n + h m ) ≤ 4M 1 L C h n . Hence d dt ϕ m,n (t) = u m (t) -u n (t), v m i -v n j ≤ u m (t) -u m i , v m i -v n j + u m i -u n j , v m i -v n j + u n j -u n (t), v m i -v n j ≤ 2M 2 1 h m + 4M 1 L C h n + 2M 2 1 h n ≤ 4M 1 (M 1 + L C )h n , due to the M 1 -Lipschitz continuity of u m (•), u n (•) and the boundedness by M 1 of u m i , u n j . Consequently, 1 2 u m (t) -u n (t) 2 = ϕ m,n (t) ≤ 4M 1 T (M 1 + L C )h n for all t ∈ [0, T ], (43)
which implies that (u n (•)) n is a Cauchy sequence in C([0, T ]; H ). Thus, there exists a M 1 -Lipschitz function u(•) such that u n (•) converges to u(•) uniformly and

u n (t) -u(t) ≤ 2 2M 1 T (M 1 + L C )h n .
Next we show the uniform convergence of (v n (•)) n . By using ( 22), (43) and the Lipschitz continuity of C, u n (•), v m (•), one has the following estimation

d C η n (t),u n (η n (t)) (v m (t)) ≤ e C η m (t), u m (η m (t) ∩ M 1 B; C η n (t), u n (η n (t)) + v m (η m (t)) -v m (t) ≤ L C h m + h n + u n (η n (t)) -u m (η m (t)) + M 2 h m ≤ (2L C + M 2 )h n + L C ( u n (η n (t)) -u n (η m (t)) + u n (η m (t)) -u m (η m (t)) ) ≤ (2L C + M 2 )h n + 2L C M 1 h n + 2 2M 1 T (M 1 + L C )h n .
In particular, we imply that

d C η n (t),u n (η n (t)) (v m (t)) → 0 as m, n → +∞. From (27)
and the fact that vn

(t) + f n (t) ≤ 2M 2 , one has -vn (t) -f n (t) ∈ N C η n (t),u n (η n (t)) v n (η n (t)) = 2M 2 ∂d C(η n (t),u n (η n (t))) (v n (η n (t))). ( 44
)
Thus

vn (t) + f n (t), v n (η n (t)) -v m (t) ≤ 2M 2 d C η n (t),u n (η n (t)) (v m (t)).
It implies that

vn (t), v n (t) -v m (t) ≤ vn (t), v n (t) -v n (η n (t)) -f n (t), v n (η n (t)) -v m (t) + 2M 2 d C η n (t),u n (η n (t)) (v m (t)) ≤ 2M 2 2 h n -f n (t), v n (t) -v m (t) + 2M 2 d C η n (t),u n (η n (t)) (v m (t)) = -f n (t), v n (t) -v m (t) + β n,m (t), where β n,m (t) := 2M 2 2 h n + 2M 2 d C η n (t),u n (η n (t)) (v m (t)),
and

β n,m ∞ → 0 as m, n → +∞.
Similarly, one has

vm (t), v m (t) -v n (t) ≤ -f m (t), v m (t) -v n (t) + β m,n (t).
As a consequence, we have, for almost every t ∈ [0, T ], that

vm (t) -vn (t), v m (t) -v n (t) ≤ -f m (t) -f n (t), v m (t) -v n (t) + β m,n (t) + β n,m (t) ≤ -f m (t) -f n (t), v m (θ m (t)) -v n (θ n (t)) + α m,n (t) ≤ α m,n (t), ( 45
)
where

α m,n (t) := β m,n (t) + β n,m (t) -f m (t) -f n (t), v m (t) -v m (θ m (t)) -f m (t) -f n (t), v n (θ n (t)) -v n (t) .
The last inequality holds since for some function k(•) ∈ L 1 ([0, T ]; R). Then, for given initial condition, the sweeping process (S) has at most a solution.

f m (t) ∈ F θ m (t), u m (θ m (t)), v m (θ m (t)) , f n (t) ∈ F θ n (t
Proof Suppose that there are two solutions u 1 (•), u 2 (•) of (S) such that u 1 (0) = u 2 (0) = u 0 and u1 (0) = u2 (0) = v 0 . Then, there exist f i (t) Then, the result follows by using Gronwall's inequality.

∈

Conclusions

In this paper, by using tools from convex and variational analysis, the existence and uniqueness result of a class of second-order state-dependent sweeping processes in Hilbert space, has been studied carefully. It is remarkable that the moving set is possibly unbounded and all main assumptions (the Lipschitz continuity and the compactness of the moving set, the linear growth boundedness of the perturbation force) are weaker than the ones used in previous works, which allows more applications in practice.

  Theorem 3.2 Let Assumptions 1-(i), 2 hold and suppose that -C(t, •) is monotone for each t ∈ [0, T ]. Furthermore, assume that F is monotone with respect to the third variable on gph(C), i.e., for all(t i , x i , y i ) ∈ gph(C) and z i ∈ F(t i , x i , y i ) (i = 1, 2), one has z 1z 2 , y 1y 2 ≥ 0. (•)) n , (v n (•)) n , ( f n (•)) n , (θ n (•)) n , (η n (•)) n as in Theorem 3.1.From the proof of Theorem 3.1, it is sufficient to prove the strong convergence of sequence v n (•) in C([0, T ]; H ). First we prove the convergence of u n (•). For all positive integers m ≥ n, let

	Then, for each initial condition, there exists a solution in the sense of Theorem 3.1.
	Proof We construct the sequences (u n i ) n i=0 , (v n i ) n i=0 , ( f n i ) n i=0 and the sequences of functions (u n ϕ m,n (t) := 1 2 u m (t) -u n (t) 2 .
	Then, ϕ m,n is differentiable almost every t ∈ [0, T ]. Let t ∈ [0, T ], at which ϕ m,n is
	differentiable. Then, there exist i, j such that t ∈ [t m i , t m i+1 [∩[t n j , t n j+1 [ and hence
	d dt	ϕ m,n

  ),u n (θ n (t)), v n (θ n (t)) ,and F is monotone with respect to the third variable. Note thatf m (t)f n (t), v m (t) -v m (θ m (t)) + f m (t)f n (t), v n (θ n (t)) -v n (t) ≤ 2M 2 2 (h m + h n ). (t) -v n (t) 2 ≤ 2α m,n (t) ≤ 2 α n,m ∞ . Since v m (0) = v n (0) = v 0 , one obtains, for all t ∈ [0, T ], that v m (t) -v n (t) 2 ≤ 2T α n,m ∞ → 0 as m, n → +∞.It deduces that (v n (•)) n is a Cauchy sequence in C([0, T ]; H ), which leads to the uniform convergence of (v n (•)) n . Thus, the result has followed. Theorem 3.3 (Uniqueness) Suppose that F satisfies the one-sided Lipschitz-like condition: for all t ∈ [0, T ]; x 1 , x 2 ∈ H; y 1 ∈ C(t, x 1 ), y 2 ∈ C(t, x 2 ) and z 1 ∈ F(t, x 1 , y 1 ), z 2 ∈ F(t, x 2 , y 2 ), one has z 1z 2 , y 1y 2 ≥ -k(t)( x 1x 2 2 + y 1y 2

	From (45), one has
	d dt	v m 2 ),	(46)
	Hence

α n,m ∞ → 0 as m, n → +∞.

  -u2 (t) 2 + u 1 (t)u 2 (t) 2 } = ü1 (t) -ü2 (t), u1 (t) -u2 (t) + u 1 (t)u 2 (t), u1 (t) -u2 (t) ≤ k(t) + 1/2 ( u 1 (t)u 2 (t) 2 + u1 (t) -u2 (t) 2 ).

	Thus
	1 2	d dt	{ u1 (t)

F t, u i (t), ui (t) , i = 1, 2 such that üi (t) + f i (t) ∈ -N C(t,u i (t)) ui (t) a.e. t ∈ [0, T ]. (

47

)

Using the monotonicity property of the normal cone and the condition (46), we have for almost every t ∈ [0, T ] that

ü1 (t) -ü2 (t), u1 (t) -u2 (t) ≤ k(t)( u 1 (t)u 2 (t) 2 + u1 (t) -u2 (t) 2 ).

Acknowledgments

The authors would like to acknowledge the referees for their careful reading and insightful suggestions. The research of the second author is supported by Fondecyt Postdoc Project 3150332.


Ramsay Taylor

John Derrick

mu2: A refactoring-based mutation testing framework for Erlang

We present a mutation testing framework for the Erlang functional programming language. Mutation testing evaluates a test set by mutating the original System Under Test (SUT) and measuring the test set's ability to detect the change. Designing mutation operators can be difficult, since they must modify the original program in a way that is both semantically significant, and a realistic simulation of a potential fault (either a fault with the system in its real context, or a common programmer error). The principal contribution of this work is the mu2 framework, which leverages the Wrangler refactoring API to allow users to specify their own mutation operators. The framework makes it possible to quickly and clearly define mutation operators that can have complex and subtle effects on the SUT. This allows users to define domain-specific operators that can simulate faults that are of particular relevance to their project, rather than relying on standard operators. The mutation testing framework was evaluated in an industrial setting and compared to code coverage test adequacy metrics. It was found to be a valuable compliment to code coverage techniques, since it was able to uncover additional testing limitations that could not be easily identified by coverage alone.

Introduction

Testing is a vital component of any software development process, and often accounts for a large portion of the development effort. The purpose of testing is to provide assurance that the software functions correctly. However, as software projects expand, the size and complexity of the test sets also expand. This can create a new requirement to provide assurance of the "correct functioning" of the test set, i.e. that the test set is adequately assessing the software functionality.

Although measures such as code coverage provide some information about a test set's scope, they may not provide an accurate measure of a test set's ability to detect faults [START_REF] Fraser | Behaviourally Adequate Software Testing[END_REF]. Mutation testing [START_REF] Hamlet | Testing programs with the aid of a compiler[END_REF] provides an alternative approach, which has been shown to be able to identify limitations of test sets that could not be identified even with advanced coverage metrics such as MC/DC [START_REF] Baker | An Empirical Evaluation of Mutation Testing for Improving the Test Quality of Safety-Critical Software[END_REF]. Mutation testing is a testing methodology which inserts deliberate faults into the System Under Test (SUT) to generate mutants of the program. The test set to be evaluated is run on each of these mutants. Since the tests were designed to evaluate the operation of the correct program they should report failure when run on the mutant. The mutation testing terminology is that the tests "kill" the mutants. Those mutants that are not killed are either semantically equivalent to the original program -that is, although they will have undergone a syntactic change, they will have identical behaviour to the original -or they identify a class of fault that the test set is not adequately identifying. The percentage of mutants killed provides a numeric metric for the effectiveness of the test set.

Mutation testing has been applied successfully to various imperative languages, such as Java, C, and Ada [START_REF] Baker | An Empirical Evaluation of Mutation Testing for Improving the Test Quality of Safety-Critical Software[END_REF][START_REF] Harman | Strong Higher Order Mutation-based Test Data Generation[END_REF][START_REF] Mateo | Mutation at the multi-class and system levels[END_REF][START_REF] Fraser | Achieving scalable mutation-based generation of whole test suites[END_REF]. Simple, random changes to the syntax of the source files can produce many thousands of mutants easily, but a very high proportion will simply not compile, and many more will be semantically equivalent. An improvement over simple mutation testing is provided by first parsing the source file and then applying mutation operators to the parsed form -changing the semantics of the program directly -before re-rendering the program to a source code file.

It is not practical to seed every possible fault into a program and measure a test set's ability to detect these, so it is important that the mutants generated are in some way representative of a broader class of system faults. In this case a test set's ability to identify a particular deliberate fault provides good evidence that the test set is well written with respect to this class of fault or this particular section of the system. This provides some assurance that it would also identify other faults if they were present. Given this, it is important that the faults that are seeded in the mutants are representative of faults that are either likely or significant to the system under test. Consequently, while some general mutation operators are useful and provide a baseline measure of the quality of a test set, a principle objective of this work was to allow the development of domain-specific mutation operators for particular use cases. Specifically, we provide:

-A framework that allows the rapid development of semantically-rich mutation operators for specific domains -Integration of mutation testing with the Erlang ecosystem and automation of a mutation testing workflow for Erlang modules -An evaluation of the mutation testing framework with an industrial partner that demonstrates mutations testing's value, but also how it can be used as a compliment to other test adequacy metrics

The paper is structured as follows: Section 2 contains some background on Erlang and mutation testing. It also describes the process of applying mutation testing to the kinds of test suites common in Erlang. Section 3 describes the mu2 framework that implements and automates that application of mutation testing to Erlang. Section 4 details our refactoring-based system for defining mutation operators that allows semantically rich operators to be developed rapidly. Section 5 documents the evaluation study carried out with Interoud Innovation. Finally, Section 6 concludes.

Background

Erlang

Erlang [START_REF] Armstrong | Concurrent Programming in ERLANG[END_REF][START_REF] Armstrong | [END_REF][START_REF]HOPL III: Proceedings of the Third ACM SIGPLAN Conference on History of Programming Languages[END_REF] is a programming language originally developed at Ericsson for use in their telecoms infrastructure products. It is now available as open source software, and used in a wide variety of companies both large and small. As a language it is declarative and uses several components of the functional programming paradigm, such as pattern matching and extensive use of recursion.

-module(abiftest).

-export([dv/2]).

dv(A,B) -> if (A == 0) and (B > 4) -> B; true -> B / A end.

Fig. 1. The abif test erlang module

An Erlang module contains a number of functions, each of which is defined by a series of patterns starting with a name, a set of parameters, the arrow symbol ->, the function definition, and ends with a full stop. For example, the abiftest module in Figure 1 contains just one function, dv, which takes two numbers A and B and divides B by A unless some conditions hold. Functions can have multiple patterns, with separate patterns separated by semicolons and the final pattern terminated with a full stop. The same syntax extends to internal decisions, such as the if statement in Figure 1, or case statements that match structural patterns over values. Patterns are matched in order with the first matching pattern being applied -hence the if statement having true as the final pattern, since this will always match and so functions like an else or otherwise in other languages.

Variable names begin with capital letters or the underscore character (e.g. Var, S), whilst lower case letters indicate an "atom" value (conceptually a user defined keyword, e.g. lock, unlock). Tuples are contained in curly brackets ({lock, S}), lists in square brackets ([a,b,c]). Strings are treated as lists but can be presented in double quotation marks. Erlang is an interpreted language and so the failure of the interpreter to find a matching pattern for a particular function application is reported at runtime. There is an exception throwing model for error handling, which allows pattern matching over the types of exceptions caught.

Erlang also features a process-oriented distributed programming model that uses asynchronous communication channels. Messages sent from one process to another accumulate in the receiver's message queue. The receive construct allows the process to pattern match over the incoming messages. The first message is compared to the patterns and, if it matches any one, then the relevant code is executed. In the event that the first message in the queue does not match any of the patterns in the current receive construct, then the second message in the queue is compared, and so on until a message matches. In this way it is possible for an Erlang process to skip some messages and handle particular message patterns with higher or lower priority. In the event that no message matches the current patterns the process with block until either a message arrives that does match, or a time limit (specified with the timeout pattern) is reached.

There is a large range of testing frameworks and support for Erlang. Conventional unit testing is often carried out with the Eunit [START_REF] Carlsson | EUnit: A Lightweight Unit Testing Framework for Erlang[END_REF] framework, but there is considerable use made of more advanced test generation and property-based testing using the Erlang QuickCheck system [START_REF] Arts | Testing telecoms software with quviq QuickCheck[END_REF].

Mutation Testing

The objectives of any test adequacy metric are:

-Give a general quality metric for the test set -Identify specific weaknesses of the test set -Give constructive feedback that guides a user to improve the test set and address the weaknesses Mutation testing -first described in [START_REF] Hamlet | Testing programs with the aid of a compiler[END_REF] -seeks to evaluate test sets by simulating faults in a software system and measuring the test set's ability to identify the faults. Standard mutation testing makes a modification to the software's source code to produce a 'mutant'. The mutant code is compiled and then tested using the test suite. If the mutant fails the test suite, such a mutant is referred to as 'killed', if not then it is 'alive'. Where a mutant remains alive it must be inspected to determine whether the mutation actually produced a functional change. In some cases the mutations to the source code have no effect on the semantics -changing the name of an unused variable, for example.

For a non-trivial program, it is not realistic to explore all possible mutations. This is why one would usually focus on those that seem 'representative' of the defects a program may contain. For example, a typical hypothesis here is of a 'competent programmer' who may introduce an occasional error (such as in a form of a comparison operator the wrong way around). In this case, a good test suite is the one that kills all single-comparison mutants.

For example, consider the simple test set given in Figure 2, which tests the abiftest module from Figure 1. The abiftest module passes all these tests, however, it contains a defect that is not identified by this test set. Specifically: the dv function can produce a divide by zero error if it is called in such a way that the first if decision is false but A contains the value 0. Because the decision is a -module(abiftest_tests).

-include_lib("eunit/include/eunit.hrl"). zero_test() -> ?assert(abiftest:dv(5,0) == 0.0). one_test() -> ?assert(abiftest:dv(1,5) == 5.0). two_test() -> ?assert(abiftest:dv(2,5) == 2.5). two_twos_test() -> ?assert(abiftest:dv(2,2) == 1.0). five_test() -> ?assert(abiftest:dv(5,5) == 1.0).

Fig. 2. A test set for abif test

conjunction this can be triggered by a test in which A is equal to 0, but B is less than 5. This is not covered by any of these test cases. Mutation testing assumes that all tests pass for the original source file. For the test results produced for each mutant, if any of the tests has failed then the test suite was able to identify the change. This is referred to as killing the mutant. If all the tests pass, then the change was not detected and the mutant remains alive. The count of killed vs alive mutants gives a numerical assessment of the fault identification power of the test suite, which meets the requirement for a general quality metric.

Reviewing the specific mutants that remained alive can give much more detailed information about the weaknesses of the test set. That a particular change went unnoticed by the test set implies that that section of the program is not adequately tested. This is the primary reason why the mu2 framework produces separate mutant files with only one mutation in each file, since this allows clear identification of the specific change that was not detected. This detail about each undetected mutation provides the required identification of specific weaknesses of the test set, and the fact that it is tied directly to the code provides immediate guidance on the areas of the testing to improve.

The mu2 Framework

Overview We have developed the mu2 framework to automate and simplify the process described in Section 2.2, but also to allow the definition of domainspecific mutation operators in an efficient way.

To support mutation testing the source file of the program is parsed and analysed, and possible mutations identified. Each mutant is produced by applying one mutation operator to one point in the program. This allows the mutation testing results to identify and characterise specific weaknesses of the test suite in both particular areas of the program and particular styles of fault. To make the mutation testing efficient it is preferable to first identify all the possible mutations, and then select mutations from the list to produce mutants, thus preventing the creation of multiple mutants with identical mutations.

Mutation operators are defined as a triple that includes a name, a function to identify applicable parts of the program, and a function to apply the change. The detailed structure of mutation operators is covered in Section 4. By automating the application of mutation operators and the generation and collation of mutants, mu2 allows a user to concentrate their efforts on developing innovative and rich mutation operators that reflect the specific faults they want to simulate, and against which they want to evaluate their test suite.

Mutant Generation The mu2 tool 1 takes as input an Erlang source file and a set of mutation operators. The source file is parsed and all of the possible applications of each of the mutation operators are enumerated. Mutants are then generated by selecting from the possible applications and producing a new Erlang source file with the mutation applied and a header comment added to describe the type and location of the mutation. The result is a folder containing as many mutant files as requested -up to the number of possible mutation applications. The test suite can then be run against each of these modules and the pass or fail status recorded.

The mu2 module provides the generate function to produce mutants. It can take parameters to specify a particular subset of available operators, or a limited number of mutants, but in its simplest form it takes the source file and an output folder:

Eshell V6.0 (abort with ^G) 1> mu2:generate("abiftest.erl","mutants"). Checking applicability of plus_to_minus, 98 more to try... This produces a series of files in the output folder, each names according to the original module name, the mutation operator applied, and the line and character position of the application. The mutant abiftest gt to le 5 22 5 26 is shown in Figure 3, next to the original source file. The name represents that it is built from the abiftest module by applying the gt to le operator (replacing a "greater than" operator with a "less than or equals" operator) at line 5, characters 22 through 26.

-module(abiftest). In a similar fashion, Figure 4 shows the application of the eq to le operator, replacing an equals operator with a "less than or equals" operator.

Test Set Evaluation

The exact process of evaluating the original test set against each mutant may vary between projects if there are substantial requirements for the testing environment. However, the mu2 framework includes some support functions to evaluate a test set against mutants. The test function takes a source folder, module name, mutant folder name, and a test function. It then takes each of the mutants in turn and moves them into the source folder, refactors the mutant name to the original module name, then compiles the module and runs the tests with the mutant in place of the original module.

The final result is a collation of mutant names and the atom ok or error to indicate the success or failure of the test set. Converting this into a simple killed/alive ratio is simple, but the retention of the mutant names allows the user to trace any mutants that survive and identify the weakness in the test set. In this simple example 11 of the 25 mutants were not killed. Of these only one can be considered semantically equivalent: replacing the == operator with the type-specific =:= is irrelevant, since it would not be meaningful for the function to behave differently with 0.0 than with 0.

However, all of the remaining tests highlight the weakness in the test setnamely that it does not adequately explore the combinations of ways of satisfying and falsifying the condition over A and B. The majority of surviving mutants have modified the condition B > 4 on line 5, characters 22 to 26. Although this condition is exercised, it is only exercised in a limited range of settings (it is only falsified when the other part of the decision is also falsified).

The addition of this test identifies that error in the original code (and, incidentally, achieves full MC/DC coverage of the system as discussed in [START_REF] Taylor | Smother -An MC/DC analysis tool for Erlang[END_REF]): div_zero_test() -> ?assert(abiftest:dv(0,2) == 2.0).

This succinctly demonstrates the way the mu2 framework meets the test adequacy metric requirements from Section 2.2. The mutation score of 11/25 is a general quality metric for the test set, and can be expressed as a percentage with the test set killing only 56% of mutants. This may not be directly comparable to other test adequacy metrics, but gives a similar intuition about the quality of the test suite that a 56% coverage score would do.

That the surviving mutants were predominantly located on line 5, characters 22 to 26 identified not only that decision point as the weakly tested element, but also identified the specific condition that was inadequately tested. Mutation testing is not limited to decision points, as collection of surviving mutants on any other program element (e.g. an output or a calculation) would provide similar evidence that that specific element was inadequately tested. Additionally, the mutants give some guidance on producing new tests, since it highlights some examples that should be distinguished -e.g. if B > 4 and B < 4 are not distinguished then clearly the system should be tested with values of B both greater and less than 4 (and, perhaps, B equal to 4).

Operator Definitions

Practical mutation testing requires that changes be made to the source program's parsed form rather than its source code. Erlang has many libraries in the standard installation that support the parsing of Erlang programs to an abstract syntax tree, but modifications to these trees can be complicated to specify and difficult to understand. The mutation operators that are used in this work can require quite subtle semantic changes that would be particularly complicated to specify in terms of standard syntax tree alterations.

To provide a more succinct and readable interface this work leverages the Wrangler refactoring system [START_REF] Li | A User-extensible Refactoring Tool for Erlang Programs[END_REF]. Wrangler is a refactoring system that presents an emacs interface, but it also contains a programatically accessible API. The Wrangler API allows refactorings to be specified in an elegant template format.

In general, refactoring is a process that changes a program's source code structure in a consistent way. Common refactorings include: renaming a variable everywhere it is used, extracting blocks of repeated code into a new function, or moving code between levels in a class hierarchy. In order to support such changes, refactoring tools require a rich understanding of the semantics of the target language (e.g. to understand scoping issues when renaming variables). Consequently, the Wrangler refactoring system provides an ideal platform on which to build the mutation operators required for Erlang mutation testing.

The template format of the Wrangler refactoring API uses a series of macros to specify code transformations. The ?RULE macro defines a rule with three components: a pattern of Erlang code to match, a programatic transformation on that code, and a programatic guard statement to limit the application of the rule. Several different macros define the traversal of the abstract syntax tree; the ?FULL TD TP macro traverses all nodes in the tree. As an example, a function to convert addition to subtraction at a specific program location is shown in Figure 5.

plus_to_minus(File, Loc) ->

?FULL_TD_TP([?RULE(?T("X@ + Y@"), ?TO_AST("X@ -Y@"), api_refac:start_end_loc(_This@)==Loc)], [File]). Fig. 5. The Wrangler API code to convert addition to subtraction However, this requires an understanding of the Wrangler system, and it requires the application of multiple Wrangler macros. To speed up the development of mutation operators and allow users to focus on interesting semantic operations the mu2 framework provides a simplified definition structure. A mu2 mutation operator is a triple containing a name that will be used to identify the change, a function to identify applicable locations, and a function to alter the code. The mu2 framework also provides several macros to implement common operations. {plus_to_minus, ?MUTATION_MATCH("X@ + Y@"), ?MUTATION_EXCHANGE("X@ + Y@", "X@ -Y@")} Fig. 6. The mu2 plus to minus operator definition Figure 6 shows the same replacement of addition with subtraction but as a mu2 operator. The ?MUTATION MATCH macro provides a simple way to express a location identifier function that simply matches a template, and the ?MUTATION EXCHANGE macro is for mutations that are simple rearrangements or syntax modifications that do not alter the meta-variables.

The significant power of the Wrangler API comes from the ability to perform arbitrary operations on the syntax tree as part of the refactoring operation. The meta-variables in the Wrangler patterns allow the syntax components to be manipulated easily. For example, Figure 7 shows a refactoring to re-order the patterns in a case statement, using the Pats@@@, Guards@@@, and Body@@@ meta variables that contain lists of the syntax components for the case statement. {swap_case_order, ?MUTATION_RESTRICT("case Expr@ of Pats@@@ when Guards@@@ -> Body@@@ end", is_valid_pattern_set(Pats@@@) ), ?MUTATION("case Expr@ of Pats@@@ when Guards@@@ -> Body@@@ end", begin A = random:uniform(length(Pats@@@)), B = random_not_n(length(Pats@@@), A), NewPats@@@ = swap(Pats@@@, A, B), NewGuards@@@ = swap(Guards@@@, A, B), NewBody@@@ = swap(Body@@@, A, B), ?TO_AST("case Expr@ of NewPats@@@ when NewGuards@@@ -> NewBody@@@ end") end)} Fig. 7. The mu2 swap case order operator

The ?MUTATION RESTRICT macro creates a location identifier that matches a pattern but also evaluates a boolean function over the metavariables (in this example is simply calls another function to check that the list of patterns is valid). The general ?MUTATION macro produces a modification function that matches a pattern and then performs an arbitrary function over the meta-variables. This function must return a Wrangler Abstract Syntax Tree, but this is simplified by the ?TO AST macro that can build an AST from a template, which can reference newly constructed meta-variables.

Evaluation

The mu2 framework was built as part of the EU funded PROWESS project2 (Property-based testing of web services). As part of the project the tool was evaluated in an industrial context, and we briefly explain here the evaluation and its results.

Research Questions

As discussed in Section 2.2, a test adequacy metric must produce both a rigorous assessment and measure of the quality of a test set, and useful feedback to guide a test developer to improve the test set. A simple measure of the rigour of an adequacy metric is the number of tests required -assuming that the test set developers don't produce spurious or overly-repetitive tests. The requirement for useful guidance is more difficult to measure.

Testing methodologies are often measured using code coverage as a test adequacy metric (e.g. [START_REF] Fraser | Whole Test Suite Generation[END_REF]). Several coverage metrics are available for Erlang, including basic line coverage metric provided by the cover tool that is included in the standard Erlang library, and MC/DC analysis provided by the Smother tool [START_REF] Taylor | Smother -An MC/DC analysis tool for Erlang[END_REF]. These have the advantage of requiring less time and effort to apply, since they only require the test suite to be run once, rather than once per mutant. However, [START_REF] Baker | An Empirical Evaluation of Mutation Testing for Improving the Test Quality of Safety-Critical Software[END_REF] showed that -for the imperative languages C and Ada -mutation testing was not only able to provide equivalent levels of quality assurance, but also provide complimentary information and guidance to the test developers.

Consequently, the mu2 framework is evaluated in comparison to these metrics to demonstrate that it provides similar complimentary benefits in a functional programming language. Specifically we choose the following research questions as the basis for our evaluation:

1. Does mutation testing require more tests than other test adequacy metrics (e.g. coverage) to achieve a maximal score? 2. Do test sets with high mutation scores also achieve high coverage scores, or are they testing different system behaviours? 3. How much longer does it take to perform mutation testing on realistic Erlang modules than testing to maximise coverage? 4. How useful is the feedback provided by mutation testing compared to other metrics?

Evaluation Results

The PROWESS project partner Interoud Innovation3 evaluated the mu2 framework by applying the procedure above. They did not develop any domain-specific operators and used the simple arithmetic and structural operators that are included by default with he framework. The evaluation itself consisted of an iterative process. The participant developers first measured the coverage and mutation score of their current tests set and then used feedback from the coverage tools and mutation testing tool to improve their test set. The feedback -either uncovered sections or code, or unkilled mutants -should prompt the developers to write new tests. Alternatively, particular execution sequences or mutants may be presented but impossible to cover and can be discarded. The augmented test set can be re-run and new feedback generated. This processes was repeated until there were no uncovered sections of code, no un-killed mutants, until all that remains was identified as impossible, or until the developers judged the remaining items not significant.

This produces a collection of test sets, each produced using feedback from a different metric. The original test set is referred to as T , then the test set developed using cover is T C, that produced from Smother is T S, and that produced from mu2 is T M . As well as comparing the improvement made in their own metric, the final test sets were each evaluated using all of the metrics. The numerical results for the metric are presented in tabular form below, followed by a description of each of the test sets. -This development took approximately 8 hours and tests were added for almost every mutant. Only 16 of the 83 mutants remained alive:

• 7 of them were not killed because the mutations were semantically equivalent to the original code (e.g. reordering completely specified case clauses or changing =:= to == when comparing atoms). • 7 of them were not killed because the mutation can never be executed.This is the case when the mutation is applied in an internal function with controlled input, so that it is impossible from the tests to cause the input that would make the test fail. In one example the mutant changed an equal comparison by a less than comparison but there is no way of passing a value less than normal into the function parameter, because a previous clause would have match for any other allowed value. This is related to the "impossible" conditions required by Smother, but statically determining the limitations on variable values is a complex problem. • 2 of them were not killed because tests to kill them would be too difficult to implement and not useful.

Developer feedback

The Interoud developers provided some subjective comments about the usefulness of the different strategies used to generate test cases, summarised here:

Cover

-Interoud developers think it may be easier to generate tests focusing on lines of code but it produces worse tests than other metrics.

Smother

-The test set developed for Smother was the most difficult to develop by the Interoud developers. Getting complete coverage in clause based functions is hard because it is likely that some unexpected input (i.e. values of different types or forbidden values, mostly on internal functions) is not covered. Interoud only developed tests using Eunit, but using QuickCheck should have made it easy to check all condition combinations. -About MC/DC coverage, Interoud developers think it is more useful than line coverage, as it focuses on important lines of code.

mu2

-The mutant based test set is very specific, which makes it more time consuming to apply. Interoud developers created tests for this pilot study that aimed to kill mutants in the most isolated way. Since several mutations are different changes to operators in the same condition, some of these tests kill several mutants.

-Interoud developers think that the mu2 tool is slow generating mutants, although this was not a problem since mutants were generated only once for all developed test sets. -Regarding mutation coverage, it was the easiest to develop test for and, although they tend to be too specific, they can be refactored later. -The default set of mutation operators was only of limited value, but Interoud developers think that the investment of time needed to develop more advanced operators would be worthwhile.

Evaluation Conclusions

As expected, the test set developed using only line coverage feedback (T C) did not achieve high scores in MC/DC or Mutation assessment. The Smother based test set (T S) and the mu2 based test set (T M ) achieved commendable performance when measured by each other's metric, but there were clearly some areas of difference that represent complementary value -features that are best identified with one metric or the other. It is significant that although the time taken to generate mutants was mentioned as a weakness of the mutation testing approach, the overall time taken to develop the mutation based test set was considerably shorter. The developers report that the mutants provided the most clear and direct feedback as to what feature was not being executed and how to write a relevant test, although there was some concern that these tests were then too narrowly targeted.

Conclusions

This work has produced a framework for applying mutation testing to Erlang programs, and that supports a powerful refactoring based system for defining domain-specific mutation operators. The industrial evaluation of the mu2 framework demonstrated that it was not only valuable as a test adequacy framework in itself, but that it provided complimentary information to MC/DC analysis of the same system.

Although at the start of this work there was no published mutation testing framework for any functional programming language, the recently released M uCheck [START_REF] Le | MuCheck: An Extensible Tool for Mutation Testing of Haskell Programs[END_REF] is a mutation testing environment for Haskell, designed to work with Haskell Quick Check. MuCheck provides conventional mutation operators for list operations and for reordering pattern in pattern matching. The authors make a similar observation in Haskell about the impact of mutations on recursive functions and how this can cause divergent behaviour.

The authors of [START_REF] Fraser | Mutation-Driven Generation of Unit Tests and Oracles[END_REF] proposed an approach to automatically generating tests that uses mutation testing to identify areas and types of fault that were of interest. By generating and optimising test sets to kill mutants they expect to create test sets more likely to identify real faults in systems. Because both the mutant generation and test set generation is automated this can be run on a large scale if resources are available. Erlang QuickCheck supports feature based testing that allows test generation to be targeted at specific "features". This could be used in conjunction with mu2 mutants to apply this approach to Erlang.

The mu2 framework has been released as an open-source project on GitHub.

-Fig. 3 .

 3 Fig. 3. The application of the gt to le operator to abiftest.erl

Fig. 4 .

 4 Fig. 4. The application of the eq to le operator to abiftest.erl

  This test set has been developed with the aim of improving line coverage using the Cover tool. It adds 67 Eunit tests to the original test set (4 QuickCheck properties and 148 Eunit tests).-That this test set achieves a higher percentage MC/DC (Smother ) score than the test set explicitly designed to achieve a high MC/DC score demonstrates a problem with representing MC/DC scores numerically. Since the developers of T C were aiming to simply execute all lines at least once, this test set executes more lines than T S, resulting in a large number of partially explored decisions. Meanwhile, the developers of T S thoroughly explored the decisions that they considered important, and ignored some that they considered less significant. However, that means that T S leaves a number of decisions completely unexplored, and these contribute multiple MC/DC elements to the percentage since they may contain multiple subcomponents with multiple potential evaluations. This development took approximately 20 hours, although part of that time was needed to find and fix the bug noted below. This development was also finished before reaching the maximum reachable MC/DC coverage since it was considered more than reasonable coverage.

	Original test	Cover based	Smother	Mu2	based
	set (T)	test set (TC)	based test set	test set (TM)
			(TS)
	Coverage(C) 31.17%	69.23%	53.44%	49.79%
	(77/247 lines)	(171/247 lines)	(132/247 lines)	(123/247 lines)
	Coverage(S) 47.99%	73.16%	69.84%	64.17%
	Coverage(M) 16.86% (14/83	49.39% (41/83	74.69% (62/83	80.72% (67/83
	killed)	killed)	killed)	killed)
	Original test set (T )
	-The original test set contains 4 QuickCheck properties and 81 Eunit tests.
	Cover based test set (T C)
	-Smother based test set (T S)
	-This test set adds 64 Eunit tests to the original test set (4 QuickCheck
	properties and 145 Eunit tests).
	-Mutation based test set (T M )
	-This test set has been developed with the aim of improving mutation cov-
	erage using the mu2 tool. It adds 15 Eunit tests to the original test set (4
	QuickCheck properties and 96 Eunit tests).

http://www.prowessproject.eu/

http://www.interoud.com/


Ammar Mohammed Sultan
email: ammar.alsultan@hotmail.com

Salmi Baharom

Abdul Azim
email: azim@upm.edu.my

Abd Ghani

Jamilah Din
email: jamilahd@upm.edu.my

Hazura Zulzalil
email: hazura@upm.edu.my

Genetic Algorithm Application for Enhancing State-Sensitivity Partitioning

Keywords: genetic algorithm (GA), state-sensitivity partitioning (SSP), test case, sequence of events, data state

Software testing is the most crucial phase in software development life cycle which intends to find faults as much as possible. Test case generation leads the research in software testing. So, many techniques were proposed for the sake of automating the test case generation process. State sensitivity partitioning is a technique that partitions the entire states of a module. The generated test cases are composed of sequences of events. However, there is an infinite set of sequences with no upper bound on the length of a sequence. Thus, a lengthy test sequence might be encountered with redundant data states, which will increase the size of test suite and, consequently, the process of testing will be ineffective. Therefore, there is a need to optimize those test cases generated by SSP. GA has been identified as the most common potential technique among several optimization techniques. Thus, GA is investigated to integrate it with the existing SSP. This paper addresses the issue on deriving the fitness function for optimizing the sequence of events produced by SSP.

Introduction

Amongst software development life cycle (SDLC) phases, software testing is the most crucial one [START_REF] Pressman | Software engineering: a practitioner's approach[END_REF]. It intends to execute the software and find faults as much as possible. Generally, test case generation dominates the research in software testing while other research areas include test execution and test oracles. Hence, a number of techniques were proposed for improving the effectiveness and efficiency of faults detection. State-sensitivity portioning (SSP) is one of them [START_REF] Baharom | Module documentation based testing using Grey-Box approach[END_REF][START_REF] Baharom | State-Sensitivity Partitioning Technique for Module Documentation-based Testing[END_REF][START_REF] Baharom | An experimental assessment of module documentationbased testing[END_REF].

SSP employs Parnas formal specifications in order to test a module that consists of one or more access programs, which share the same data structure. The output depends on the event triggered, input parameters, conditions and actions. Thus, test data for a module might consist of event sequences (or test sequences) rather than a single event. For the sake of avoiding the exhaustive testing of a module's entire states, SSP partitions the entire states according to their sensitiveness toward events, conditions and actions. Test sequences are selected manually based on all-transitions coverage criterion. However, the sequence of events can be very lengthy and might contain redundant data states, which makes the testing expensive and relatively ineffective.

In the literature, many optimization techniques have been suggested. One technique is search techniques [START_REF] Alsmadi | Effective Generation of Test Cases Using Genetic Algorithms and Optimization Theory[END_REF][START_REF] Kulkarni | Test Case Optimization Using Artificial Bee Colony Algorithm[END_REF] and, among them, genetic algorithm (GA) has been identified as the most common for generating test cases [START_REF] Ali | A Systematic Review of the Application and Empirical Investigation of Search-Based Test Case Generation[END_REF]. The success stories of GA inspired us to adopt GA in our work. Similar to other search techniques, the adoption of GA requires the derivation fitness function [START_REF] Harman | Search based software engineering: Techniques, taxonomy, tutorial, in Empirical Software Engineering and Verification[END_REF]. Thus, this paper describes the ongoing research that addresses the issue of deriving a fitness function in order to search within the population of states produced by SSP sequence of events. The remainder of this paper is organized as follows: an overview of SSP is presented in the next section; followed by a general overview on GA. Next, the fitness function application in SSP is being described followed by a case study. Finally, the last section summarizes the paper along with the conclusion.

2

State-Sensitivity Partitioning (SSP)

A module may consist of one or more access programs that share the same data structure. Its behavior is depending on the event triggered, the value of input parameters and conditions. Consequently, generating test cases for such a module might involve a large number of data states, which grows exponentially in terms of the number of program variables. For example, approximately 1020 tests (232 X 232) have to be performed in order to test the correctness of two variables A and B of 32 bit integers, as in [START_REF] Gannon | Software Specification: A Comparison of Formal Methods[END_REF]. Hence, it would take more than 30,000 years of testing with the assumption of performing 108 tests per second. Therefore, it is impossible to explore the space of entire states with limited time resources and memories. SSP is a test case generation technique for modules [START_REF] Baharom | Module documentation based testing using Grey-Box approach[END_REF][START_REF] Baharom | State-Sensitivity Partitioning Technique for Module Documentation-based Testing[END_REF][START_REF] Baharom | An experimental assessment of module documentationbased testing[END_REF]. The states are partitioned based on state's sensitivity towards events, conditions (pre-conditions) and actions (post-conditions). The goal is to group all states that behave similarly towards accessprograms (events), conditions and actions (either sensitive or insensitive) together.

SSP has six sequential steps, which are: (i) identifying sensitive access programs, (ii) partitioning states into equivalence classes, (iii) constructing a state transition model, (iv) selecting test cases based on all-transition coverage criteria, (v) adding the insensitive events to the end of each selected test case and (vi) applying boundary value analysis (BVA) technique in order to select the input parameters. Nonetheless, each test case from the fourth step must be represented by at least one sequence of events. The SSP sequence of events has to be selected randomly as long as it follows the specified conditions of the constructed state transition model in step three (3). Below is an example.

Example

In order to grasp the idea of SSP, let's consider the example of circular queue. Circular queue has three access programs, which are: add(), remove(), and front(). The former two access programs are sensitive as they modify the data states during their execution while the latter is insensitive as it does not modify the data states. According to SSP, the entire data states are partitioned into equivalence classes based on the number of identified sensitive access programs. So, the circular queue has four possible partitions. In the third step, a state transition model is constructed as in Fig. 1.

Once the state transition diagram is constructed, all-transitions coverage criteria will be used for selecting test cases. Table 1 lists the ten test cases obtained from the state transition model. Each test case will be represented by at least one sequence of events. Then, the insensitive events is going to be added to the end of the sequence. Lastly, the BVA technique is applied in order to determine the value of input parameter. With the assumption that maximum length of the circular queue is five, here are some examples of test sequences produced by SSP. TC1: _.add [START_REF] Pressman | Software engineering: a practitioner's approach[END_REF].front() TC2: _.remove().front() TC3: _.add [START_REF] Pressman | Software engineering: a practitioner's approach[END_REF].add(-1).remove().add(1295644148).add(-1295644148).front() TC4: _.add(0).add(Integer.Max_value).add(Integer.Min_value).add [START_REF] Pressman | Software engineering: a practitioner's approach[END_REF].add(-1).front()

Fig. 1. State Transition model for circular queue

As the SSP sequence of events is selected randomly, any sequence follows the conditions specified by the state transition model is valid. For example, a sequence of events for adding an item to a full queue might include adding twenty items; removing eighteen items, adding fifty more, removing fifty two, adding ten more, removing ten, adding one more and checking the result. Hence, the sequence of events might be lengthy and contain redundant data states. The lengthy sequence with redundant states makes testing expensive and ineffective. Also, there is a redundancy occurs between two or more test sequences (i.e. sequence of events), where a test sequence is subset from other sequence(s). Therefore, there is a need to optimize the test suites through removing redundant data states. Among the available techniques, search techniques are the most common for obtaining optimized test suites.

Genetic Algorithm (GA)

The applications of search techniques in the domain of software testing grew dramatically as they save efforts and times. For test cases generation, GA is the most common amongst all search techniques. It is a population based metaheuristic technique that follows the theory of natural evolution by Darwin. In GA, the optimal solutions evolved through applying reproduction and selection operations on populations over successive generations [START_REF] Holland John | Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[END_REF]. The typical GA consists of five repetitive steps that continue till the stopping criteria is met. The stopping criteria is either finding an optimum solution or reaching the maximum number of iterations. The GA steps are: 1) random initialization of population that contains candidate solutions. Each solution is represented as a chromosome or sequence of variables [START_REF] Li | Search Algorithms for Regression Test Case Prioritization[END_REF]; 2) evaluation of new candidate solutions, if the stopping criteria is not met; 3) selection of promising candidate solutions based on fitness function. Fitness function is used for evaluating the solution in terms of its ability to solve the problem; 4) crossover; and 5) mutation. GA performs search in parallel, which leads to fast calculations. Consequently, software testing leads the GA applications compared with other SDLC phases. This includes different disciplines such as test cases generation [START_REF] Ali | A Systematic Review of the Application and Empirical Investigation of Search-Based Test Case Generation[END_REF][START_REF] Mcminn | Search-based software test data generation: a survey[END_REF], test cases prioritization within test suites [START_REF] Conrad | Empirically studying the role of selection operators duringsearch-based test suite prioritization[END_REF], and test suites reductions [START_REF] Li | Search Algorithms for Regression Test Case Prioritization[END_REF]. However, prior to apply GA for optimizing the test cases, there is a need to derive the fitness function. Besides, the invocation of each event in the sequence may lead to different states. Therefore, there is a need to grasp the changes of states and search within for good solutions to be used in GA next iterations. In the next section, the derivation of fitness function is described.

Fitness Function Application in SSP

Fitness function plays an important role in guiding the search within a population of solutions. It judges whether a potential solution presents a good candidate and, hence, has to be used in GA next iterations. The fitness function comes from existing software metrics followed by several refinements according to the results [START_REF] Harman | Search based software engineering: Techniques, taxonomy, tutorial, in Empirical Software Engineering and Verification[END_REF]. Anyhow, SSP sequences of events produced a group of states which are unique and redundant states. In order to optimize SSP, we aim to remove the redundant states. There are two types of redundancies: (1) redundancy in test case level and (2) redundancy in test suite level. Therefore, the calculation of fitness function has to take both types into consideration. We introduce two score namely test case states minimization (TCSM) and test suite states minimization (TSSM). The fitness function is:

Fitness= TCSM + TSSM (1)

Test cases states minimization (TCSM)

TCSM aims to remove redundant states on the test case level, such as the states encountered when trying to add to after reaching the maximum in circular queue or removing when there is no item to be removed. In order to calculate TCSM, there is a need to differentiate between unique and redundant states per sequence of events. A score of TCSM is calculated based on the following equation: TCSM= USC+RSC (2) where USC is the unique states score per sequence of events and RSC is the redundant states score per sequence of events. Let A be a set of unique states in a sequence of events. The calculations for USC is shown in the following equation:

MAX MAX A i MAX MAX A USC i 1 ... 1 | | 1 1              (3)
where |A| is the cardinality for set A, which counts the number of unique states in the sequence of events and MAX is the maximum number of items that can be added to the data structure. For the calculation of RSC, let B be the set of redundant states in a sequence of events where B ⊆A and B∩A= B. The calculation for RSC as follows:

               | | 1 1 ... 1 1 B i MAX MAX MAX MAX B RSC i (4)
where |B| is the cardinality for set B, which counts the number of redundant states per sequence of events. Obviously, the score of TCSM can produce a negative value, which indicates that the sequence is unlikely to be in the GA next generations.

4.2

Test suites states minimization (TSSM)

TSSM focuses on removing redundancies between sequences of events in the test suites. This is due to the fact that some sequences of events are subsets from others. So, for a set C= {tc1, tc2… tcn} of test cases (tc), the TSSM is calculated as follows:

| C | TCO TSSM  (5)
where |C| is the cardinality for set C, which counts the number of test cases in the population and TCO is a test case occurrence, which counts the occurrences of a specific sequence within the suite. In order to calculate TCO, every sequence (test case) is considered as an individual set such as: {tc1}, {tc2}, {tcn}. If k is the counter for counting the occurrence of similar test cases, the sets are compared as follows:

; 1 ; 1      k k tc tc n n (6)

5

Case Study

Assume that the following test suite is produced from the SSP technique based on the circular queue example.

To get the fitness, equation (1) will be used. However, the values may be greater than or equal to one. So, there is a need to use the average fitness as follows:

Fitness Total Fitness Fitness Average  (7)
where Total Fitness is the summation of all fitness values in the population. Table 2 shows the fitness along with the average fitness for the population above. The results show that test cases with events close to the maximum number of items that can be added to the data structure. Hence, TC3 got the highest value followed by TC4. Besides, the test cases with redundant events, such as TC5, obtain the lowest value. TC1: _.add [START_REF] Pressman | Software engineering: a practitioner's approach[END_REF].front() TC2: _.remove().front() TC3: _.add [START_REF] Pressman | Software engineering: a practitioner's approach[END_REF].add(-1).remove().add(1295644148).add(-1295644148).add(0).add [START_REF] Pressman | Software engineering: a practitioner's approach[END_REF].add(-1).front() TC4: _.add(0).add(Integer.Max_value).add(Integer.Min_value).add [START_REF] Pressman | Software engineering: a practitioner's approach[END_REF].add(-1).front() TC5: _.remove().remove().front()

Conclusion

The integration of SSP and GA is promising in order to optimize sequence of events. Prior to any application, there is a need to derive a fitness function that guides the search for solutions within a population. This is a part of an on-going research which aims to enhance the effectiveness of test case generation technique for testing a module with internal memory. We believe that the adoption of GA can improve the effectiveness of SSP to overcome the redundancy issues in SSP and consequently will produce optimized test cases.

Table 1 .

 1 THE TEST CASES FOR CIRCULARQUEUE PROGRAM

	#	P	Event	Pre-Condition	Post-Condition
	1.	1	Add	len = 0	dataQ'[rear']=x, rear'=('rear+1)%QSIZE, len'='len+1
	2.	1	Remove	len = 0	dataQ'='dataQ, front'='front, rear'='rear, len' = 'len
	3.	2	Add	len = QSIZE	dataQ'='dataQ, front'='front, rear'='rear, len' = 'len
	4.	2	Remove	len = QSIZE	dataQ'[rear']=x, front'=('front+1)%QSIZE, len'='len-1
	5.	3	Add	0<len<QSIZE -1	dataQ'[rear']=x, rear'=('rear+1)%QSIZE, len'='len+1
	6.	3	Add	len = QSIZE -1	dataQ'[rear']=x, rear'=('rear+1)%QSIZE, len'='len+1
	7.	3	remove	1<len<QSIZE	dataQ'[rear']=x, front'=('front+1)%QSIZE, len'='len-1
	8.	3	remove	len = 1	dataQ'[rear']=x, front'=('front+1)%QSIZE, len'='len-1
	9.	4	Add	len<0 && len>QSIZE	dataQ'='dataQ, front'='front, rear'='rear, len' = 'len
	10.	4	remove	len<0 && len>QSIZE	dataQ'='dataQ, front'='front, rear'='rear, len' = 'len

Table 2 .

 2 THE

				FITNESS VALUES
	ID	SC	TSM	Fitness	Average Fitness
	TC1	0.2	0.4	0.6	0.15
	TC2	0.2	0.4	0.6	0.15
	TC3	1.2	0.2	1.4	0.35
	TC4	1	0.2	1.2	0.3
	TC5	0	0.2	0.2	0.05
		TOTAL		4	1


Takeshi Kitahara
email: kitahara@kddilabs.jp

Shuichi Nawata

Masaki Suzuki

Norihiro Fukumoto

Shigehiro Ano

A Practical Evaluation Method of Network Traffic Load for Capacity Planning

Keywords: capacity planning, traffic monitoring, traffic load testing, queuing simulation 1

Communications network operators are supposed to provide high quality network service at low cost. Operators always monitor the amount of traffic and decide equipment investment when the amount exceeds a certain threshold considering trade-offs between link capacity and its utilization. To find the proper threshold efficiently, this paper proposes a practical threshold definition method which consists of fine grained data collection and computer simulation. We evaluate the proposed method using commercial traffic data-set. The results show the proper timing for the equipment investment.

Introduction

The largest mission for communications network operator is to provide highquality network service at low cost, but there always exists trade-off between quality and cost. To ensure quality of network service, it is crucial to keep traffic load of the link below a certain threshold level and to upgrade the link capacity immediately after the load exceeds the threshold. From the viewpoint of the capital expenditure, on the other hand, this threshold value should be set to high so that traffic can be accommodated into the link as much as possible. Thus finding the appropriate threshold value is the main effort for capacity planning.

Traffic load is typically observed with a monitoring tool such as MRTG [START_REF] Shipway | Using MRTG with RRDtool and Routers2[END_REF] (Multi Router Traffic Grapher) in terms of average volume during several minutes, because watching traffic load with finer granularity requires computing resources. Considering practical use, the threshold mentioned above should be represented as the ratio of average traffic volume in minutes to the original link capacity. For example, the threshold would be 80% if five-minute average of 800Mbit/s is the maximum load for a certain GbE (Gigabit Ethernet) link so as not to degrade quality. However, averaging through minutes masks information about burstiness of traffic on each link. In the case of bursty traffic where the difference between the instantaneous peak and sever-al-minute average is large, probability of packet loss would be high compared to the case of traffic where such the difference is small even though average loads in minutes are equivalent. Thus capacity for links with bursty traffic should be upgraded earlier than links with not-bursty traffic. A lot of past work addressed characterizing traffic burstiness [START_REF] Leland | On the self-similar nature of Ethernet traffic (extended version)[END_REF][START_REF] Taqqu | Proof of a fundamental result in self-similar traffic modeling[END_REF][START_REF] Erramilli | Experimental Queuing Analysis with Long-Range Dependent Packet Traffic[END_REF][START_REF] Kandula | The nature of data center traffic: measurements & analysis[END_REF][START_REF] Benson | Understanding data center traffic characteristic[END_REF], but there are no generalized models which can be applied to individual network operating and/or planning task because network structure, network usage, and applications on network are quite diverse nowadays.

For the purpose of obtaining an appropriate threshold of upgrading capacity for each link, we propose a practical method to evaluate traffic load considering its burstiness while satisfying the target level of packet loss ratio. Furthermore, we also evaluate this method using commercial traffic data-set in an operator's network.

Proposed method

There are two challenges to be addressed in this study. One is to comprehend the burstiness about the traffic on the target link and the other is to calculate the threshold for upgrading capacity considering burstiness. Thus the proposed method consists of 1) collecting data about inter-packet arrival time and packet size for several minutes on the target link and 2) evaluating the burstiness of the collected data and to calculate the threshold value using computer simulation.

1) Data collection

Burstiness of traffic cannot be estimated from five-minute average load where operators usually observe. To show that, we select four data-sets which were observed at two different points and on two different dates. Fig. 1 shows the data-sets. They are hereinafter referred to as Data 1, Data 2, Data 3 and Data 4. All data-sets describe traffic load on Link A or Link B in terms of bit/s for five minutes. Note that X-axes of all figures indicate 0 to 300 seconds. Each of Link A and Link B belongs to different commercial network. Traffic load during five minutes of Data 1 and Data 3 are nearly equal to that of Data 2 and Data 4, respectively. The normalized five-minute volumes of Data 1 through Data 4 are 1.003, 1.000, 1.210 and 1.223, respectively. Note that Yaxes of all figures are in the same scale. We also show three kinds of granularity of each data-set, which are one-millisecond, one-second and five-minutes. For evaluation of burstiness, the proposed method obtains packet-by-packet data. Note that this is only for deciding the threshold and observing fine grained data is not required for daily operation.

2) Computer simulation

The simulation solves the least required link capacity under the given conditions regarding target packet loss ratio and buffer size when traffic pattern is provided as input. The input data in this study is time-series data describing a pair of inter-arrival time and length of each packet, which are extracted from Data 1 through Data 4. The size of each input data for the simulation ranges from around 70 Mbytes to 130 Mbytes. The least required capacity corresponds to the value of the threshold dis-cussed so far. The notations of R, B, X, m and p are output rate from the queue, buffer size, input traffic to the queue, input mean rate to the queue and target packet loss ratio, respectively. In the simulation, an event will be processed each time the packet #n (n = 1,…,N) arrives at the queue. Note that X consists of N packets. We define t n , l n and Q[n] as the time when the packet #n arrives, the length of the packet #n and the queue length at the time t n , respectively. Fig. 2 represents the relationship among the notations. According to Eq. ( 1), Q[n] will be updated each time n is increased, which means a packet arrives at the queue. This process will continue until n reaches N.

𝑄 𝑡𝑚𝑝 = 𝑄[𝑛 -1] -𝑅 • (𝑡 𝑛 -𝑡 𝑛-1 ) (𝑛 = 1,2, … , 𝑁) 𝑁 𝑙𝑜𝑠𝑠 = � 𝑁 𝑙𝑜𝑠𝑠 (𝑖𝑓 𝑄 𝑡𝑚𝑝 + 𝑙 𝑛 < 𝐵) 𝑁 𝑙𝑜𝑠𝑠 + 1 (𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒)
(

where N loss describes the number of packet losses during the simulation. Fig. 3 shows an example of queuing process. In this example, packet #n enters into the queue but packet #(n+1) is dropped. To calculate the least required capacity meeting the packet loss ratio p, the following steps are performed. Such the capacity is denoted as C opt and we employ a bisection method to find the value of C opt for this study.

Step 1

Determine p and B based on the operation policy. Calculate the value of m of a data-set X we focus on. Determine C low and C high for initial values of R. We used C low = m and C high = 10•m as the initial values, respectively. In addition, dC should be determined as the terminal condition. In this simulation, we employ 100 kbit/s as the value of dC.

Step 2

Perform the queuing simulation based on Eq. ( 1) in the both cases of C low and C high . The values of N loss for both cases are obtained through the simulation. Note that the simulation will be terminated, if N loss exceeds p•N during the simulation.

Step 3

Update C low and C high by using a bisection method [START_REF] Benson | Understanding data center traffic characteristic[END_REF]. If N loss /N > p, C low is set to (C low + C high )/2. In the same manner, if N loss /N < p, C high is set to (C low + C high )/2. Fig. 4 shows the conceptual diagram of the bisection method for this simulation.

Step 4

Repeat Step 3 until C high -C low < dC. Then the value obtained is C opt .

Time

t n-1 l n R (t n -t n-1 ) t n Q[n-1] Q[n] Queue length … B R (t n+1 -t n ) t n+1 l n+1 Q[n+1]
Packet #(n+1) is dropped.

. .

Fig. 4.

Bisection method for the simulation.

We defineρas m/C opt , which is the key indicator for capacity planning. This is because the value ofρrepresents maximum allowable ratio of traffic load to meet the target quality for the link.

Simulation result and discussion

Fig. 5 shows the result of the simulation using Data 1 through Data 4. In the simulation, buffer size B for each simulation is set to m multiplied by 1 and 10 milliseconds. This implies that maximum delay of the buffer is around 1 or 10 milliseconds. We observe the significant difference regardingρbetween Data 1 and Data 2 although the values m are nearly equivalent as mentioned before. This is also applied to between Data 3 and Data 4. Since each of Data 1 and Data 3 is bursty compared to each of Data 2 and Data 4 respectively as intuitively confirmed in Fig. 1, the difference ofρis found to depend on burstiness of the traffic. Furthermoreρ of Data 1 is quite close to that of Data 3 and this relationship is applied to between Data 2 and Data 4. This suggests that the degree of the burstiness should be dependent on the link we observed. In other words, average volume do not have a large impact on the value ofρ. In addition, we confirm the target packet loss ratio has a considerable impact to the value of ρ. This targeting is left to a policy of the trade-off between quality and investment. To make a right decision for operators, the obtained values ofρare quite beneficial. Furthermore, computing time required to obtain the results is important from the practical viewpoint. In this simulation, it takes about 10 to 20 minutes to complete a simulation to obtain one value of ρcorresponding to one point in Fig. 5.

There are not purely theoretical methods to calculate the value of ρ, becauseρis determined by quite many factors. The possible factors affectingρare the number of nodes where the traffic goes through, services and applications generating traffic, customers where the network is targeted for, and so on. This paper, however, does not focus on these factors because these factors themselves are not so important from the viewpoint of practical capacity planning. The largest interest for practitioners is "when do I need to increase the capacity?". predicted using conventional techniques of time-series analysis, the appropriate timing for enhancement of capacity can be easily estimated. If a practitioner collects some datasets on a certain link and calculates ρ corresponding to each dataset, the lowest value of ρ should be applied to the link against the unexpected excessive load while it depends on operator's policy. Note that we assume that the value ofρof the future, which is the time when total traffic volume increases, should not be significantly changed. Fig. 5 supports this assumption.

Conclusion

While research related to burstiness of traffic have been studied in these twenty years, network operators might still rely on their experienced knowledge. Since real traffic is quite diverse, there are no generalized models which can apply to all kinds of traffic. Thus we were eager to fill the gap between research and practice. This paper proposed a practical evaluation method for network capacity planning. We applied the proposed method to commercial traffic data which were observed at two different points and on two different dates. Since the proposed method is quite specific and concrete, network operators can easily apply this method to their work. We believe the contribution of this paper helps them to improve quality of their work.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Traffic volume during five minutes

Fig. 3 .

 3 Fig. 3. Example of simulation process.

  (a) Buffer size is 10ms (b) Buffer size is 1ms.

Fig. 5 .

 5 Fig. 5. Simulation results regarding maximum allowable ratio of traffic load ρ.

  The answer is when the observed mean rate reaches original link capacity C multiplied byρ. Since the mean rate is able to be

	Packet loss ratio	p	C low	C opt	C high	Output rate
			C low		C high
			C low	C high
				…

adfa, p. 1, 2011. © Springer-Verlag Berlin Heidelberg 2011