We propose a new model-based framework to combine functional and load tests for service oriented architectures. The new framework is based on the model of extended timed automata with inputs/ouputs and shared integer variables. A test generation algorithm to produce analog-clock tests is proposed. To illustrate our approach, we report on a case study from the eld of load balancing based architectures for BPEL compositions.
Nowadays testing has become an important phase in the development of any software system. During the last few decades very critical programming errors have been reported in di erent elds. Some of these errors were very dangerous and caused huge human/ nancial damages. For instance in 1996, the European rocket Ariane 5 exploded 37 seconds after launch1. The error was the result of a wrong reuse of code from Ariane 4. The nancial loss caused by this accident was estimated to be about $400 million. A second example of critical software errors was encountered in the medical eld. From 1985 to 1987, at least four patients died as a direct result of a radiation overdose received from the medical radiation therapy device Therac-252. The four victims received up to 100 times the intended dose. The accident was the result of a bug in the software powering the Therac-25 device.
Clearly, many other critical errors happened in many other elds. However, we restrict ourselves to the two previous presented examples due to space limitation. The important point to emphasize here is that a good percentage of these 1 http://www.ima.umn.edu/arnold/disasters/ariane.html 2 http://therac25.net/about.php errors could have been avoided by considering some more sophisticated testing e orts. However unfortunately, in practice such e orts are still minimal and the need for advanced testing solutions is still deep. Indeed software companies are still not making enough e orts at this level. A UK survey has noticed that 92% of test professionals perceive both the cost and complexity of software testing is increasing, but just 22% of test teams are willing to adopt this process3.
The remainder of this paper is organized as follows. In Section 2, we give a brief recall about some types of testing. In Section 3, we de ne the extended timed input output conformance relation etioco, as an extension of our previous timed conformance relation tioco. Section 4 is dedicated to describe formally our testing approach. Then, we propose in Section 5 a test generation algorithm to produce analog-clock tests. In Section 6, we report on an example to illustrate our approach. Finally, Section 7 provides a conclusion that summarizes the paper and discusses items for future work. 2
In this paper we mainly concentrate on two particular types of software testing namely functional and load testings. First, we consider functional testing which allows to check whether the speci ed functionality in the system requirements works correctly or not. This is done by sending some particular sequences of inputs to the SUT and then checking whether the correct outputs are generated or not. This type of testing falls under the class of black box testing. Second, we consider load testing which is achieved to assess the SUT's behaviour under both normal and peak load conditions. More precisely, load testing aims at estimating the maximum amount of work the SUT can manage with no signi cant performance degradation. Obviously, load testing is mainly dedicated to mutliuser systems. In general, this kind of testing is accomplished by simulating a signi cant number of users accessing the SUT concurrently.
In this context and in addition to conventional functional testing procedures,
load testing is a required procedure that reveals programming errors which would
not appear if the SUT is executed with a small (limited) workload or for a short
time. Such errors emerge when the system is executed under a heavy load or over
a long period of time. On the other hand, a given process under test may be
correctly implemented but fails under some particular load conditions because of
external causes (e.g. miscon guration, hardware failures, buggy load generator,
etc.) [
In this paper, we focus on conformance testing of a given SUT under various
load conditions, which constitutes an important testing area that is often
misun3 http://www.uk.sogeti.com/News{Events/Press-Releases/
derstood or overlooked. Indeed, in some cases, a system may perform correctly
and conformly to its speci cation under a certain load, but it disrespects this
speci cation when the load increases and goes above the expected values. This
may be due to some implementation errors which are discovered when
stressing the SUT. For early bug detection, we make use of model-based testing [
We extend the framework presented in a previous work [
Timed Labelled Transition Systems Let R be the set of non-negative reals, Q the set of non-negative rationals and N the set of non-negative integers. Given a nite set of actions Ac, the set (Ac [ R) of all nite-length real-time sequences over Ac will be denoted RT(Ac).
2 RT(Ac) is the empty sequence. Given Ac0 Ac and 2 RT(Ac), PAc0 ( ) denotes the projection of to Ac0 [ R, obtained by \erasing" from all actions not in Ac0 [ R. Similarly, DPAc0 ( ) denotes the (discrete) projection of to Ac0. For example, if Ac = fa; bg, Ac0 = fag and = a 1 b 2 a 3, then PAc0 ( ) = a 3 a 3 and DPAc0 ( ) = a a. The time spent in a sequence , denoted duration( ) is the sum of all delays in , for example, duration( ) = 0 and duration(a 1 b 0:5) = 1:5.
In the rest of the document, we assume given a set of actions Ac, partitioned in two disjoint sets: a set of input actions Acin and a set of output actions Acout. Actions in Acin [ Acout are called observable actions. We also assume there is an unobservable action 62 Ac. Let Ac = Ac [ f g.
A Timed Labelled Transition System (TLTS) over Ac is a tuple (S; s0; Ac; Td; Tt), where: { S is a set of states; { s0 is the initial state; { Td is a set of discrete transitions of the form (s; a; s0) where s; s0 2 S and a 2 Ac; { Tt is a set of timed transitions of the form (s; t; s0) where s; s0 2 S and t 2 R.
Timed transitions must be deterministic, that is, (s; t; s0) 2 Tt and (s; t; s00) 2 Tt implies s0 = s00. Tt must also satisfy the following conditions: (s; t; s0) 2 Tt and (s0; t0; s00) 2 Tt implies (s; t + t0; s00) 2 Tt; (s; t; s0) 2 Tt implies that for all t0 < t, there is some (s; t0; s00) 2 Tt.
We use standard notation concerning TLTS. For s; s0; si 2 S, ; i 2 Ac [ R, a; ai 2 Ac [ R, 2 RT(Ac ) and 2 RT(Ac), we have: { General transitions: s ! s0 Def (s; ; s0) 2 Td [ Tt;
= s ! D=ef 9s0 : s ! s0;
Def s 6! = 6 9s0 : s ! s0; s 1 !n s0 D=ef 9s1; s ! D=ef 9s0 : s ! s0;
Def s 6! = 6 9s0 : s ! s0. { Observable transitions: s ) s0 D=ef s = s0 or s ! s0; s )a s0 Def
= s 6 )a Def
= 6 9s0 : s )a s0; s a=1)an s0 D=ef 9s1; s ) D=ef 9s0 : s ) s0;
Def s 6) = 6 9s0 : s ) s0.
A sequence of the form s0 !1 s !2 !n s0 is called a run and a sequence of the form s0 )a1 s )a2 )an s0 an observable run. 3.2
Extended Timed Automata
We use timed automata [
Each edge is a tuple (q; q0; ; r ; inc; dec; d ; a), where: { q; q0 2 Q are the source and destination locations; { is the guard, a conjunction of constraints of the form x#c, where x 2 X [ I, c is an integer constant and # 2 f<; ; =; ; >g; { r X [ I is the set of clocks and integer variables that are reset to zero; { inc I is the set of integer variables (disjoint from r ) that are incremented by one; { dec I is the set of integer variables (disjoint from r and inc) that are decremented by one; { d 2 flazy; delayable; eagerg is the deadline; { a 2 Ac is the action.
An example of an extended timed automaton A = (Q; q0; X; I; Ac; E) over the set of actions Ac = fa; b; c; dg is given in Figure 1 where : { Q = fq0; q1; q2; q3g is the set of locations; { q0 is the initial location; { X = fxg is the nite set of clocks; { I = fig is the nite set of integer variables; { E is the set of edges drawn in the Figure.
The gure uses the following notation: { \x := 0" means resetting the clock x to 0; { \i := 0" means resetting the integer variable i to 0; { \i + +" means incrementing i by 1; 4 { \i " means decrementing i by 1. 5
An extended timed automaton A de nes an in nite TLTS which is denoted LA. Its states are pairs s = (q; vX ; vI), where q 2 Q, vX : X ! R is a clock valuation and vI : I ! N is an integer variable valuation. 0X is the valuation assigning 0 to every clock of A. 0I is the valuation assigning 0 to every integer variable of A. SA is the set of all states and s0A = (q0; 0X ; 0I) is the initial state.
- Discrete transitions are of the form where a 2 Ac and there is an edge 4 We can also use the usual notation \i := i + 1" instead. 5 We can also use the usual notation \i := i 1" instead.
(q; vX ; vI) !a (q0; vX0 ; vI0) (q; q0; ; r ; inc; dec; d ; a) where t 2 R; t > 0 and there is no edge such that: { either d = delayable and there exist 0
and (vX + t2; vI) 6j= ; { or d = eager and (vX ; vI) j= .
(q; vX ; vI) !t (q; vX + t; vI) (q; q00; ; r ; inc; dec; d ; a) such that (vX ; vI) satis es
and (vX0 ; vI0) is obtained by: { resetting to zero all clocks and integer variables in r ; { incrementing integer variables in inc by one; { decrementing variables in dec by one; { leaving all other variables unchanged.
- Timed transitions are of the form t1 < t2 t such that (vX + t1; vI) j=
Lazy edges do not impact the semantics. They denote that an edge is neither delayable, nor eager. More precisely, lazy edges cannot block time progress, whereas delayable and eager edges can. We do not allow delayable edges with guards of the form x < c since there is no latest time when the guard is still true. Similarly, we do not allow eager edges with guards of the form x > c since there is no earliest time when the guard becomes true. A state s 2 SA is reachable if there exists 2 RT(Ac) such that s0A ! s. The set of reachable states of A is denoted Reach(A). 3.3
Extended Timed Automata with Inputs and Outputs An extended timed automaton with inputs and outputs (ETAIO) is an extended timed automaton over the partitioned set of actions
For clarity, we will explicitly include inputs and outputs in the de nition of an ETAIO A and write
Ac = Acin [ Acout [ f g: (Q; q0; X; I; Acin; Acout; E)
(Q; q0; X; I; Ac ; E): instead of
An ETAIO is called observable if none of its edges is labelled by .
Given a set of inputs Ac0 Acin, an ETAIO A is called input-enabled with respect to Ac0 if it can accept any input in Ac0 at any state: 8s 2 Reach(A) : 8a 2 Ac0 : s !a :
It is simply said to be input-enabled when Ac0 = Acin. A is called lazy-input with respect to Ac0 if the deadlines on all the transitions labelled with input actions in Ac0 are lazy. It is called lazy-input if it is lazy-input with respect to Acin. Note that input-enabled does not imply lazy-input in general.
A is called deterministic if 8s; s0; s00 2 Reach(A) : 8a 2 Ac :
s !a s0 ^ s !a s00 ) s0 = s00: A is called non-blocking if 8s 2 Reach(A) : 8t 2 R : 9 2 RT(Acout [ f g) :
duration( ) = t ^ s ! : This condition guarantees that A will not block time in any environment.
The set of timed traces of an ETAIO A is de ned to be
A
TTr(A) = f j 2 RT(Ac ) ^ s0 !g: The set of observable timed traces of A is de ned to be
A
OTTr(A) = fPAc( ) j 2 RT(Ac ) ^ s0 !g:
The TLTS de ned by an ETAIO is called a timed input-output LTS (TIOLTS). From now on, unless otherwise stated, all the considered ETAIO are de ned with respect to the same sets Acin and Acout and unobservable action . As for ETAIO, a given TIOLTS L is denoted instead of (S; s0; Acin; Acout; Td; Tt)
(S; s0; Ac ; Td; Tt):
The two operators TTr( ) and OTTr( ) are extended in a natural way to the case of TIOLTS. 3.4
Parallel Composition of ETAIO with Shared Integer Variables
Ai = (Qi; q0i; Xi; I; Aciin; Aciout; Ei): That is the set of integer variables I is shared between all the considered ETAIO (Ai)1 i n while no other element from Qi, Xi, Aciin and Aciout is shared whith the other ETAIO (Aj)j6=i. The TIOLTS
LP = (SP ; s0P ; AciPn ; AcoPut; TdP ; TtP ) generated by the parallel product of the ETAIO is de ned as follows
(Ai)1 i n s0P = ((q01;
; q0n); (0X0 ; AciPn =
[ 1 i n
Aciin; AcoPut = ; 0Xn ); 0I) [ 1 i n
Aciout and SP , TdP and TtP are the smallest sets such that { s0P 2 SP ; { For sP = ((q1; ; qn); (vX0 ; ; vXn ); vI) 2 SP and
n : (qi; vXi ; vI ) ! (qi; vXi + ; vI ) 2 Tti ) s0P = ((q1; ; qn); (vX0 + ; ; vXn + ); vI) 2 SP and where and sP ! s0P 2 Tt (1) { For sP = ((q1; ; qn); (vX0 ; ; vXn ); vI) 2 SP , 1 i
n and ai 2 Ac i: 6 (qi; vXi ; vI ) !ai (qi0; vX0i ; vI0 ) 2 Td
i ) s0P = (q0p; vX0p; vI0) 2 SP
^ sP !ai s0P 2 Td q0p = (q1; ; qi 1; q0i; qi+1;
; qn) vX0p = (vX0 ; ; vXi 1 ; vX0i ; vXi+1 ; vXn ) (2)
It is worth noticing here that it is possible to de ne the parallel composition of n copies (Ai)1 i n of the same ETAIO A. In this case we assume it is possible to distinguish the sets of inputs and outputs of the di erent instances, such as particular identi er corresponds to each instance. Obviously, the n instances share the set of integer variables of the ETAIO A. The obtained TIOLTS is denoted LnP . 6 Ac i = Aciin [ Aciout [ f g 3.5
Modelling Issues In this section we illustrate some methodological aspects of our framework. First we explain how it is possible to combine both functional and load aspects within the same model. For instance in Figure 2 the response time to produce the output action b with respect to the input action a depends on the number of concurrent instances of the considered system under test as follows: { output b is generated within at most 1 time unit if the number of concurrent instances is smaller or equal to 100; { output b is generated within at most 2 time units if the number of concurrent instances is between 101 and 1000; { output b is generated within at most 3 time units if the number of concurrent instances is greater or equal to 1001;
In Figure 3 we show how to model the fact that the SUT may even produce di erent output actions with respect to the same input action depending on the current number of concurrent instances of the considered system. The SUT may produce either b, c or d. On the rst hand, output a may be seen as the normal output generated by the SUT when the load is smaller or equal to 100. On the other hand, output b may correspond to the situation where the SUT still produces the same desired output action. However this time the output action is mixed with a warning message to inform the user that the system is starting entering a critical area (load between 101 and 1000). Finally output c may correspond to the production of an error message meaning that the SUT is no longer able to produce the desired output action since the load is too high (greater or equal to 1001).
In Figure 4 we consider a more sophisticated situation where the SUT can produce complete di erent behaviours depending on the current load. Three distinct behaviours are possible according to the gure. Behaviour 1 can be considered as the nominal behaviour as in the previous example. The two other behaviours may correspond to the situation where the SUT is trying to nd a suitable way to deal with the increase of the current number of concurrent instances and to improve the quality of the service. For instance a possible solution may consist in allocating additional resources to overcome the current critical situation. 4
In this section, we are going to de ne a new extended timed input output conformance relation etioco. Then, we propose a new approach for deriving analogclock tests from the SUT speci cation. Finally, we discuss both test execution and correctness requirements. 4.1
Conformance Relation In order to formally de ne the conformance relation, we de ne a number of operators. Given a TIOLTS
L = (SL; s0L; AciLn; AcoLut; TdL; TtL) fs 2 SL j 9 2 RT(Ac L) : s0L ! s ^ PAc( ) = g: Given state s 2 SL, elapse(s) is the set of all delays which can elapse from s without L making any observable action. Formally: 2 RT(AcL)
= elapse(s) = ft > 0 j 9 2 RT(f g) : duration( ) = t ^ s !g:
Given state s 2 SL, out(s) is the set of all observable \events" (outputs or the passage of time) that can occur when the system is at state s. The de nition naturally extends to a set of states S. Formally: and out(s) = fa 2 AcoLut j s !ag [ elapse(s) out(S) = [ out(s): s2S
The speci cation of the system to be tested is given as a non-blocking ETAIO AS while the implementation can be modelled as a non-blocking, input-enabled ETAIO AI . 7 For n 1, let LSP;n (resp., LIP;n) be the parallel composition of n copies of AS (resp., AI ).
Input-enabledness is required so that the implementation can accept inputs from the tester at any state.
The extended timed input-output conformance relation, denoted etioco, is an
extension of our previous conformance relation tioco [
AI etioco AS
i
8n
A test (or test case) is an experiment performed on the implementation by an
agent (the tester). There are di erent types of tests, depending on the capabilities
of the tester to observe and react to events. In general, one may consider either
Analog-clock or Digital-clock tests [
It should be noted that we consider adaptive tests (following the terminology
of [
For n 1, let Acn (resp., Acinn) denote the union of all observable actions (resp., all input actions) of n copies of the speci cation AS . An analog-clock test for n parallel executions of AS is a total function
Tn : RT(Acn) ! Acinn [ fWait; Pass; Failg:
Tn( ) speci es the action the tester must take once it observes : { If Tn( ) = a 2 Acinn then the tester emits input a. { If Tn( ) = Wait then the tester waits (lets time elapse). { If Tn( ) 2 fPass; Failg then the tester produces a verdict (and stops). 7 AI may be unknown. We assume it simply exists. 4.3
Test Execution and Correctness Requirements The execution of the test Tn on the implementation AI can be de ned as the parallel composition of the TIOLTS de ned by Tn and LIP;n the TIOLTS corresponding to n copies of AI , with the usual synchronization rules for transitions carrying the same label. We will denote the product TIOLTS by LIP;nkTn. The execution of the test reaches a pass/fail verdict after bounded time.
Formally, we say that AI passes the test, denoted AI passes Tn, if state Fail is not reachable in the product LIP;nkTn. We say that an implementation passes (resp. fails) a set of tests (or test suite) T if it passes all tests (resp. fails at least one test) in T .
We say that an analog-clock test suite T is sound with respect to AS if 8AI : AI etioco AS ) AI passes T : We say that T is complete with respect to AS if
8AI : AI passes T ) AI etioco AS : 5
We adapt the untimed test generation algorithm of [
Fail ai! aj! bi!
Sli ? Sl
A c?
Sl0 AUA bj!
Slj
For all illegal outputs ai (outputs which cannot occur from any state in S) the test leads to Fail. For each legal output bi, the test proceeds to node Si, which is the set of states the speci cation can be in after emitting bi (and possibly performing unobservable actions). If there exists an input c which can be accepted by the speci cation at some state in S, then the test may decide to 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
S tsucc(fsnP;0g; 0); while(true) x 0; / x is a clock measuring elapsing time / await(output b is received at x < T or x = T ) if (b received at x)
else
S tsucc(S; T ); endif; if (S = ;) announce Fail; exit; endif; if (valid inputs(S) 6= ;) i pick(f0; 1g); / 0 to send an input / / and 1 to continue observation / endif; if (i = 0) a pick(valid inputs(S));
endif; endwhile;
Algorithm 1: On-the- y analog-clock test generation. emit this input (dashed arrow from S to S0). At any node, the algorithm may decide to stop the test and label this node as Pass.
Analog-clock tests cannot be directly represented as a nite tree, because
there is an a-priori in nite set of possible observable delays at a given node.
To remedy this, we use the idea of [
tsucc(S; t) = fs0 j 9s 2 S : 9 2 RT(f g) : duration( ) = t ^ s ! s0g where a 2 Acn and t 2 R. dsucc(S; a) contains all states which can be reached by some state in S performing action a. tsucc(S; t) contains all states which can be reached by some state in S via a sequence actions and takes exactly t time units.
The test operates as follows. It starts at state
P
S0 = tsucc(fsn;0g; 0) where snP;0 is the initial state of LSP;n. Given current state S: { if output a is received t time units after entering S, then S is updated to dsucc(tsucc(S; t); a). { If ever the set S becomes empty, the test announces Fail. { At any point, for an input b, if dsucc(S; b) 6= ;, the test may decide to emit b and update its state accordingly.
On-line analog-clock test generation is performed by Algorithm 1. The algorithm keeps running as long as no non-conformance is detected. At any time the tester can stop testing and declare Pass. The algorithm uses the following notation. Given a nonempty set X, pick(X) chooses randomly an element in X. Given a set of states S, valid inputs(S) is de ned as the set of valid inputs at S, that is: which contains no observable valid inputs(S) = fa 2 Acinnjdsucc(tsucc(S; 0); a) 6= ;g:
Following the same methodology as in our previous work [
Considering the scalability of load balancing based architectures, it is
increasingly necessary to develop appropriate quality assurance methodologies and
techniques, of which Testing is widely adopted and used one. In this context, we
proposed in [
For simplicity and due to restrictions on page number, we present in this section the modelling of the round-robin load balancing algorithm, where properties are supposed to be available only for the case in which two servers are clustered. Adding more servers would require a di erent model for the corresponding algorithm. However, we highlight that the basic ideas are the same as for considering two clustered servers.
In fact, when a load balancer is con gured to use the round-robin method, it rotates incoming requests around the servers that it manages. Figure 6 describes this principle. Actually, a node in the cluster is modelled by a state. LB, host2 and host3 represent the load balancer and two servers. To simplify, we designed host2 and host3 by the following respective values 1 and 2. Indeed, the load balancer should assign a request to a server conforming to the following conditions: { The identi er of the current instance (i) is less than the number of total requests (nb req), which corresponds to test instances number. { The execution of the instance of number (i) is completed by a server which is di erent from the server that treated the previous instance (i-1). This condition is checked by the function verif(currentserver) which return type is Boolean.
We underline that, according to Figure 6, the top and bottom transitions are enabled when a new request has arrived (by virtue of (nb req) being externally incremented), so the internal counter (i) is less than (nb req), enabling the transition ring. Furthermore, in order to ensure that the tester does not remain in an in nite wait of a sent request from the load balancer to a server, we considered a temporal constraint on network timeout. To model this constraint, we de ne a clock x which value does not exceed, for example, 100 milliseconds (tmax) as shown in Figure 6. Thus, the proposed model is characterized by: { send si!, where i belongs to f1, 2g, represents a synchronization message. { seq[] is an array which size is equal to the total number of handled requests by the load balancer. The value of an element seq[i] determines the server that treats the instance of number (i). { A transition between a server and the load balancer is of type update. In fact, it allows incrementing the value of the current instance and the initialization of the clock value to 0. 7
In this work, we proposed a new formal model-based framework to combine functional and load tests. Our solution is based on the model of extended timed automata with inputs/ouputs and shared integer variables. The latter allows high expressiveness for concurrent systems since it guarantees partial-observability and parallel composition. In addition, we de ned the new extended timed input output conformance relation etioco which allows to compare a given implementation with respect to its speci cation in our new framework. We also provided a new technique for deriving analog-clock tests from the speci cation of the SUT. An important contribution in this work is to use a rich formalism to model mutli-user systems and to combine functional and load tests, which constitutes an important testing area that is usually misunderstood or omitted.
Many extensions are possible for this work. First, we need selection techniques based on coverage criteria in order to guide test generation and to reduce the number of generated tests. Second, we can adapt our approach to consider digital-clocks since they allow to take into account time imprecision. We may also combine o -line and on-line testing within the same testing architecture aiming to better balance the space/time trade-o . As a future work direction, we are intending to implement our testing methodology in the context of distributed concurrent software architectures.