Elektrotehniški vestnik 80(5): 240-244, 2013 Original Scientific Paper
On the Use of Status Messages in Checking Sequences for the Distributed Test Architecture
Monika Kapus-Kolar
Jozef Stefan Institute, Department of Communication Systems, Jamova 39, SI-1111 Ljubljana, Slovenia E-mail: monika.kapus-kolar@ijs.si
Abstract. In the testing of reactive systems, a checking sequence (CS) is a sequence of inputs for which a proper response from the system under test means that the system would respond properly also to every other input sequence. In the paper, we suggest how to construct cheap CSs for multi-port systems under the assumption that there is a tester placed at each port, that the testers can communicate exclusively through the system, that there is no global clock and that any tester can at any time ask the system to issue at every port a status report. We consider those CSs in which all the problems of controllability, observability and state recognition specific to the distributed test architecture are solved simply with status requests. For such a CS, our method to some extent minimizes also the number of the employed requests.
Keywords: formal methods, testing, distributed test architecture, checking sequence, status message
O uporabi stanjskih sporočil v preverjalnih zaporedjih za porazdeljeno testno arhitekturo
V testiranju odzivnih sistemov je preverjalno zaporedje (PZ) zaporedje vhodnih sporočil, za katerega pravilen odziv testiranega sistema pomeni, da bi se sistem pravilno odzval tudi na vsako drugo zaporedje vhodnih sporočil. V članku svetujemo, kako konstruirati cenena PZ za večvratne sisteme ob predpostavki, da imajo vrata vsaka svojega preizkuševalca, da ti lahko komunirajo samo preko sistema, da ni skupne ure in da vsak preiskusševaleč lahko kadarkoli zahteva, da sistem na vseh vratih objavi svoje trenutno stanje. Obravnavamo tista PZ, ki vse za privzeto porazdeljeno testno arhitekturo značilne probleme kontrolabilnosti, observabilnosti in ugotavljanja stanja rešujejo preprosto z zahtevami po objavi stanja. Za taka PZ naša metoda zmanjšuje tudi število teh zahtev.
1 Introduction
In the testing of reactive systems, e.g. hardware čom-ponents or distributed serviče providers, a checking sequence (CS) is a sequenče of inputs for whičh a proper response from the system under test means that the system would respond properly also to every other input sequenče. CSs are the most desirable kind of test suites, for their appličation does not require that the system is repeatedly reliably reset into its initial state.
In the paper, we disčuss CS čonstručtion under the assumption that the system, čall it N, and its specification, čall it M, are multi-port deterministic finite state machines, that M is strongly connected, that N
Received 23 August 2013 Accepted 9 October 2013
has at most as many states as M, that there is a tester placed at each port, that the testers can communicate exclusively through N, that there is no global clock and that any tester can at any time ask the system to issue at every port a status report (SRP), i.e., an indication of its current state. With the exception of the last one, these are the usual assumptions in the automated construction of test suites for distributed systems and the last one is also increasingly popular [1], [2].
The assumed distributed test architecture brings specific problems of controllability, observability and state recognition. If, however, one decides to solve every such problem simply with status requests (SRQs), CS construction becomes very easy [1]. In the following, we, hence, focus on this particular class of CSs, showing how for such a CS, one can efficiently minimize, at least to some extent, the cost (e.g. the length) and, optionally, also and primarily the number of the employed SRQs.
2 The System and Its Specification
We assume that M and N both operate on the same set of ports and can in every state execute every input defined on the ports. Upon executing an input x in a state s, they execute a set y of outputs, at most one per port, and enter a state s', thereby executing a transition (s, s',x/y). Their choice of y and s' depends only on x and s. If x is an SRQ, s' = s and y for every port comprises an SRP. If x is an ordinary input, every member of y is an ordinary output, i.e., not an SRP. Moreover, if x is not an SRQ, it is possible that the choice of y and s' which N makes differs from the specified, i.e., from the choice which M makes.
b/(v,w) b/(v,)
b/(v,wX //a/(u,) A/(3,3)A^B/(3,3)
Figure 1. Example two-port M.
It is assumed that the only other way in which N can be an incorrect implementation of M is that its initial state is not the specified one. A CS is, hence, any input sequence checking the initial state of N and the implementation of every specified ordinary transition. It is assumed that via the latter, M can from every state reach every other state. For M, let init(M) denote its initial state, otr(M) the set of its ordinary transitions and str(M) the set of its status transitions.
For a given input x, let Z(x) denote the cost of application to N, presumably a real number greater than 0. Besides, let Z'(x) = 1 if x is an SRQ and maximum avoidance of SRQs is desirable and Z'(x) = 0 otherwise, with cost(x) denoting the pair (Z'(x),Z(x)) in R2. A (qi,q2) in R2 is considered less than or equal to a (q[,q2) in R2 if (qi < q[) V ((qi = q[) A (q2 < q2)). The sum of two members (qi, q2) and (q[,q'2) of R2 is (qi + q'l,q2 + q2). For every (qi,q2) in R2, -(qi,q2) denotes (-q^ -q2).
Example 1. Suppose that there is a port a accepting an ordinary input a and an SRQ A and a port 3 accepting an ordinary input b and an SRQ B, with Z(a) = Z(A) = Z(b) = Z(B) = 1 and Z'(A) = Z'(B) = 1. M can then be the one depicted in Fig. 1, with the state set {1, 2, 3}, 1 the initial state and the output set in every transition label encoded as a (ya, ) with ya the output at a, if any, and the output at 3, if any. For every state s and input x, let tsx denote the corresponding transition.
For a given transition sequence (TS) t = (ss2,xij yi)... (sk ,sk+ i ,xk fyk), let init(T) denote its initial state si, fin(T) its final state sk+ i, is(T) its input sequence xi...xk, ios(T) its input/output sequence (IOS) x ify i... xk fyk, cost(T) its cost £ i <i<k cost(xH), port(T) the port of xi and ports(T) the set of all the ports involved in ios(T). Let e denote a zero-length TS. Let sts(M) denote the set of all those TSs t = ti.. .tk of M which are synchronizable, i.e., for every 1 < i <k satisfy port(ti+ i) G ports(ti).
3 Candidate Checking Sequences
Like [1], we define that a checking TS (CTS), i.e., a TS whose input sequence is a CS, is a TS of M satisfying the following:
1)	It is synchronizable.
2)	There exists such a permutation ti.. .t\otr(M)| of the transitions in otr(M) that for every 1 < i < \otr(M)|, there is a segment t'iTitit'' with ti and t'' two status transitions and Ti a TS whose every member belongs to the set {t... ,ti-i}.
3)	It starts in init(M) and the input of its first transition is an SRQ.
To see that for such a TS t, is(T) is indeed a CS appropriate for the assumed distributed test architecture, observe the following:
1)	The first constraint solves the problem of controllability, i.e., secures that during the application of is(T) to N, every tester always knows the right time for enabling (so that it can be executed when N completes its current transition) the next input at its port.
2)	The second constraint by induction secures implementation checking for the consecutive transitions in ti.. .tiotr(M)|, as for every 1 < i < \otr(M)\, proper implementation of the transitions t i.. .ti- i implies that whenever ios(t'iTi) (actually its projections onto individual ports) is observed on N, the resulting state of N is exactly the initial state of ti, so that if ios(tit'i) is subsequently observed, one knows that ti is also properly implemented.
3)	The third constraint secures the checking of the initial state of N.
4 Representing Candidate Checking Sequences in a Digraph
The first step of our CS-construction procedure is to construct a digraph G in which promising CTSs are represented as specific walks. A digraph is a set of vertices of which some are connected by directed edges. Whenever introducing an edge, we will specify it as a (v, v', l, c) with v its initial vertex, v' its final vertex, l its label and c its cost. For our purposes, we define that every edge label is a (possibly empty) sequence of transitions of M and minuses, whereas every edge cost is a member of R2 . The cost of a digraph is the sum of its edge costs.
For a given walk w = (vi,v2, li,ci)... (vk,vk+i,lk, ck), let init(w) denote its initial vertex vi, fin(w) its final vertex vk+i, lab(w) its label l ..lk and cost(w) its cost £i<i<kci. If vi = vk+ i, w is a tour. If (k > 0) a (Ai<i<j<k+1 ((vi = vj) = ((i,j) = (1,k + 1)))), w is a cycle. An edge set is acyclic if no subset of it forms a cycle. An Euler tour of a digraph is a tour traversing each of its edges exactly ones.
The construction of G starts by selecting, for every transition t in otr(M), a minimum-cost transition t' in str(M) with tt' G sts(M). Call it next(t) and let str'(M) denote the set {next(t)\t G otr(M)}. One
242
KAPUS-KOLAR
Figure 2. Schematic representation of the digraph G.
also selects, for every state s of M and transition t in str'(M), a minimum-cost TS t in sts(M) with (init(r) = s) A (Tt £ sts(M)), call it tm.
We now describe the vertices and edges of G. As we see from its schematic representation in Fig. 2, its vertices are those in the sets Vi, V2 and Vs plus the vertices v0 and v'0, whereas its edges are those in the sets El, E2, E3, Econ, Estart and plus the edge e0. The vertices in Vi are the initial vertices of the edges in El. The vertices in V2 are the initial vertices of the edges in E2 wES. The vertices in Vs are the final vertices of the edges in E3.
El = {(vinit(t),port(t), Vinit(t'),port(t'),t, cost(t))
|(t £ str'(M))A(t' £ otr(M))A(tt' £ sts(M))}
Ei = {(v'init(t),port(t),V'init(t'),port(t'),t,Cost(t))
|(t £ otr(M)) A (t' £ otr(M)) A (tt' £ sts(M))}
ES = {(vinit(t) ,port(t), Vfin(t') port^t^^ tt '' COst(tt '))
|(t £ otr(M)) A (t' = next(t))}
Econ = {(v?init(t),port(t),vlnit(t),port(t), -t, -cost(t))
It £ str'(M)}l±l
K^p vLit{t),port{tyTs,t, Cost(Ts,t))
|(t £ str'(M)) A (v3S p £ V3)A ((s,p) = (init(t),port(t)))}
Estart = {(v0 ,vlit(M ),p,C' (0, °))IvLit{M ),p £ Vl }
Eend = {(v3Spp,v'o,e, (0,0))|vs3p £ Vs} eo = (v0,vo, e, (0, 0))
Example 2. For the M of Example 1, we choose
next(ti,a) = next(t2,b) = next(ts,a) = ti,A next(t2,a) = ts,A
next(tib) = next(tsb) = ti,A
Tl,t2,A = tl,a
Tl,t3,A = tl,at2,a T2,t1A = t2,ats,Ats,b
T2,t3,A = t2,a TS,t1A = ts,b TS,t2,A = tS,a
The transition tS,A in T2jtlA secures its synchronizabil-ity. The resulting G is given in Fig. 3.
For a given walk w in G whose first edge is not of a negative cost, let ts(w) denote the TS obtained from lab(w) by deleting every segment t-t with t a transition of M. We define that a walk w of G represents a CTS, namely ts(w), if it is an ew'e'e0 with e an edge in
Estart, w' a walk whose edge set is an acyclic subset of E2 and e' an edge in Eend. In the following, such a walk is called a checking walk (CW).
To see that for every CW w, ts(w) is indeed a CTS, observe the following:
1)	ts(w) is synchronizable and starts with a status transition starting in init(M).
2)	As those edges in w that are in Ei form an acyclic subset of it, there exists such a permutation tl ■■■t\otr(M)| of the transitions in otr(M) that for every 1 < i < ^tr(M)|, w has a segment eiwiei with ei and edge in El with lab(ei) a status transition, ei an edge in ES with lab(ei) a titi with ti a status transition and wi such a walk consisting of members of Ei that every transition in ts(wi) belongs to the set {ti,..., ti—i}.
Example 3. In the G of Example 2, one of the CWs, a
w, is
(v0, v	i	,e, (0, 0))wi,a	
(vS,a,	v2i,	a, -ti,A, (-1, -	1))w2,a
(vsS,a,	vsi,	a, tS,A, (-1, -	-1))ws,b
(vi,o,	vii,	-ti,A, (-1, -	-1))wi,b
(Vi,a,	vii,	a, -tiA, (-1, -	1))w2,b
(v2,o,	v2i,	^ -ti,A, (-1, -	-1))ws,a
(via,	v0	i e, (0, 0))(v0,vo,	< e, (0, 0))
with
wi,a = (vi,a, v2iia, ti A, (I' 1))(vi,a,vla,that2A, (1, 2))
wi,a = ^Io^I^MA (1, 1))(^^,ofVsS,ofti,atS,A, (1, 2))
wS,b = (v3,o,vS,p,tS,A, (1, 1))(vlp(1, 2))
wl,b = (vl,a,vi,p ,ti,A, (1, 1))(vip, V1, of tl, btl, A> (1, 2)) w2,b = (vl,o,v\,o,ti,A, (1, 1))(vl}a,vl,p,ti,a, (0, ^
Vp,vS,Ofti,bti,a, (1, 2)) ws , a = Vi a a,vi a a,ti , A, (1, 1))(vi a a,vS, a,ti , a, (0, 1))
Vs,a, Vs,a,ts,ati, A, (1, 2)) ts(wi,a) = ti,Ati,at i ,A ts(w ,a) = t ,At ,ats,A ts(ws,b) = ts,Ats,bti,A
ts(wi,b) = ti,Ati,bti,A
ts(w ,b) = ti,Ati,at ,bt ,A ts(ws,a) = t ,At ,ats,at ,A
lab(w) = ts(wi,a)-t i ,Ats(wi ,a )-ts,Ats(ws,b)-ti,A ts(wi,b) - ti,Ats(w ,b) - t ,Ats(ws,a) = ti,Ati,at ,A - t ,At ,At ,ats,A - ts,A ts,Ats,bti,A - ti,Ati,Ati,bti,A - ti,A ti,Ati,at ,bt ,A - t ,At ,At ,ats,at ,A ts(w) = ti,Ati,at ,At ,ats,Ats,bti,Ati,bti,Ati,at ,b t ,At ,ats,at ,A For each individual transition tsx in otr(M), wsx is that segment of w that secures the checking of its implementation. Thanks to the negative-cost edges in w, the corresponding segments ts(ws,x) of ts(w) partially overlap. To see that ts(w) is a CTS, observe that it is synchronizable, that it starts with ti,A and that ts(wi,a) = ti,ATi,ati,ati,A with Ti,a = e ts(wi,a) = ti,ATi,ati,ats,A with Ti,a = e
Figure 3. G for the example M, with the edges in E3 W {eo} bold and the edges in Econ W Estart W Eend dashed.
ts(w3,b) = t3,AT3,bh,bti,A with T3,b = e ts(wi,b) = ti,ATi,bti,bti,A with Ti,b = e ts(w2,b) = tl,AT2,bt2,bt2,A with T2,b = tl,a ts(w3,a) = t2,AT3,at3,at2,A with T3,a = t2,a
5 Finding a Cheap Candidate Checking Sequence
A digraph is edge-induced if its vertices are exactly the starts and the ends of its edges. A digraph is symmetric if for every vertex, the number of the incoming edges is the same as the number of the outgoing edges. A digraph is strongly connected if from every vertex, there is a walk to every other vertex. A component of a digraph is a strongly connected sub-digraph which is not a part of any larger strongly connected sub-digraph.
Following an idea of [3], for finding a cheap (though not necessarily minimum-cost) CW we suggest the following procedure:
1)	Construct one of the cheapest symmetric edge-induced digraphs (SEIDs) consisting of e0, the edges in E3 and any number of instances of the remaining edges of G. This is the most demanding step of the procedure, but can be accomplished in polynomial time [4].
2)	Enhance the digraph into a strongly connected SEID G', using the following procedure for merging two components Gl and G2 of its current version:
a) In G, select such a minimum-cost cycle
e1w1e1e/1'e2w2e2e2' with e1 and e2 two edges in El , wl and w2 two sub-walks whose every edge is in E2 , e1 and e2 two edges in E3 and e'l and e2' two edges in Econ that every edge
in e1w1e1 has an instance in G1 and every edge in e2w2e'2 has an instance in G2. b) For every vertex in the cycle, add to G' a new instance.
3) Construct the CW as any Euler tour of G'. As G' is symmetric, simply initialize the current CW approximation to a zero-length walk starting and ending in v0 and then repeatedly append to it one of the yet uncovered outgoing edges of its final vertex.
After the first step of the procedure, G' has the following properties:
1)	It is symmetric, every edge is an instance of an edge of G and for every edge in E3, there is at least one instance.
2)	Exactly one edge is an instance of e0. Hence, exactly one edge is an instance of an edge in Estart and exactly one edge is an instance of an edge in Eend, for otherwise the digraph would not be symmetric.
3)	There is no cycle consisting exclusively of instances of edges in E2, because for every such cycle, removal of its edges from G' would contradictorily result in an even cheaper SEID consisting of e0, the edges in E3 and any number of instances of the remaining edges of G.
In any subsequent merging of two components, all the properties of G' are preserved, because no edge is removed, every new edge is an instance of an edge in E1 W E2 W E3 i±i Econ, the new edges form a cycle and the set of those edges in E2 of which G' comprises an instance is preserved. Hence, the final version of G' also possesses the properties, which indeed makes the subsequently constructed tour w a CW. As an additional
244
KAPUS-KOLAR
improvement of the corresponding CTS ts(w), replace its first element with one of the cheapest transitions t in str(M) with init(t) = init(M).
[8] R.M. Hierons, "Canonical finite state machines for distributed systems," Theor. Comput. Sci., vol. 411, no. 2, pp. 566-580, 2010.
6 Discussion
In the usual approach to the construction of a CS without controllability problems [5], the first step is to secure the checking of a sufficient set of locally distinguishing sequences (LDSs) and a sufficient set of transfer IOSs (TIOSs). Without this step, the LDSs and the TIOSs, employed in the subsequently constructed transition implementation tests (TITs), cannot be trusted. In the considered special setting, a sufficient set of reliable LDSs and TIOSs is available by definition, as every SRQ is a (length one) reliable LDS and the label of every transition in sts(M) is a (length one) reliable TIOSs.
As another complication in the usual approach, the conceived TITs sometimes fail to completely check the implementation of the transition labels, so that additional tests are necessary [6]. In the considered special setting, we have not encountered the problem, in spite of relying on a straightforward generalization of the usual approach for the single-port case [7].
For the generalization, we had to find a way to adequately represent in the auxiliary digraph G only the synchronizable TSs of M. Interestingly, we discovered that the topology of the central (i.e. E2) part of G cannot be simply that of the relevant part of the canonical representation Xmin(M) [8] of sts(M), for then the dependency relation between the TITs employed in the constructed TS can have cycles even if the employed part of E2 is acyclic. We prevented this by also securing init(e) = init(e') for every two edges e and e' in E2 i±i E3 whose labels start with the same transition in otr(M). The hint seems useful also for the multi-port case without the status-reporting capability, for which a method with thorough global optimization of the CS has yet to be developed.
Monika Kapus-Kolar received her B.Sc. degree in electrical engineering from the University of Maribor, Slovenia, and her M.Sc. and Ph.D. degrees in computer science from the University of Ljubljana, Slovenia. Since 1981 she has been with the Jozef Stefan Institute, Ljubljana, where she is currently a researcher at the Department of Communication Systems. Her current research interests include formal specification techniques and methods for the development of real-time, concurrent and reactive systems.
References
[1]	R.M. Hierons, "Using status messages in the distributed test architecture," Inf. Soft. Tech., vol. 51, no. 7, pp. 1123-1130, 2009.
[2]	H. Dan, R.M. Hierons, "Controllability problems in MSC-based testing," Computer Journal, vol. 55, no. 11, pp. 1270-1287, 2012.
[3]	R.M. Hierons, H. Ural, "Optimizing the length of checking sequences," IEEE Trans. Comput., vol. 55, no. 5, pp. 618-629, 2006.
[4]	A.V. Aho, A.T. Dahbura, D. Lee, M.U. Uyar, "An optimization technique for protocol conformance test generation based on UIO sequences and Rural Chinese Postman Tours," IEEE Trans. Comm., vol. 39, no. 11, pp. 1604-1615, 1991.
[5]	R.M. Hierons, H. Ural, "Checking sequences for distributed test architectures," Dist. Comput., vol. 21, no. 3, pp. 223-238, 2008.
[6]	J. Chen, R.M. Hierons, H. Ural, "Overcoming observability problems in distributed test architectures," Inf. Proc. Let., vol. 98, no. 5, pp. 177-182, 2006.
[7]	H. Ural, X. Wu, F. Zhang, "On minimizing the lengths of checking sequences," IEEE Trans. Comput., vol. 46, no. 1, pp. 93-99, 1997.