Robert M Hierons
email: rob.hierons@brunel.ac.uk

Mercedes G Merayo
email: mgmerayo@fdi.ucm.es

Manuel Núñez

Controllability through nondeterminism in distributed testing

If the system under test interacts with its environment at physically distributed ports, there is a separate independent tester at each port, and there is no global clock then we are testing in the distributed test architecture. It is known that the distributed test architecture can lead to additional controllability problems in which a tester cannot know when to send an input and this has led to most test generation techniques aiming to produce controllable test cases. However, there may be no controllable test case that achieves a given objective. This paper introduces the notion of a test section, in which each tester has a fixed input sequence to apply and there is no attempt to synchronise the testers. It defines the notion of a test section being convergent and shows how convergent test sections can can be used as the basis of a less restrictive form of controllability.

Introduction

Software testing has traditionally been represented as a process in which a single tester synchronously interacts with the system under test (SUT). However, testing does not operate in this way if the SUT has multiple physically distributed interfaces (ports) at which it interacts with its environment; one might then have one local tester at each interface. For example, when testing the implementation of a layer of a communications protocol there might be one local tester that acts as the layer above the SUT and a second local tester that sits on a different machine [START_REF] Sarikaya | Synchronization and specification issues in protocol testing[END_REF][START_REF] Dssouli | Error detection with multiple observers[END_REF][START_REF] Dssouli | Conformance testing with multiple observers[END_REF]. More generally, if the SUT has multiple ports then there might be a separate tester at each port. If these testers do not synchronise their actions and there is no global clock then we are testing in the ISO standardised distributed test architecture [14].

Most work on formal testing in the distributed test architecture uses multiport finite state machine (FSM) models [START_REF] Sarikaya | Synchronization and specification issues in protocol testing[END_REF][START_REF] Dssouli | Error detection with multiple observers[END_REF][START_REF] Dssouli | Conformance testing with multiple observers[END_REF] in which a transition is triggered by an input, produces up to one output at each port, and possibly changes the state. We also use this approach, of assuming that the specification is a multiport FSM, and we use the term FSM for such models. Note, however, that some work has explored more general types of models in which, for example, a transition can be labelled by a partially-ordered multi-set of actions [START_REF] Haar | Testing input/output partial order automata[END_REF][START_REF] Bochmann | Testing systems specified as partial order input/output automata[END_REF][START_REF] Ponce De León | Unfolding-based test selection for concurrent conformance[END_REF][START_REF] Ponce De León | Model-based testing for concurrent systems: unfolding-based test selection[END_REF].

Previous work has shown that the distributed test architecture changes the nature of testing. Let us suppose that we wish to start a test sequence with input x 1 at port 1, this should lead to output y 1 at port 1 and we wish to follow this with input x 2 at port 2. We might implement this using a test case t in which the tester t 1 at port 1 applies x 1 and the tester t 2 at port 2 applies x 2 . Since we are testing in the distributed test architecture, tester t 2 does not observe the input or output at port 1 and so cannot know when to supply x 2 . Thus, if we use the test case t then we cannot guarantee that the inputs arrive in the correct order; this introduces non-determinism into testing even if the SUT is deterministic. This situation is normally called a controllability problem [START_REF] Sarikaya | Synchronization and specification issues in protocol testing[END_REF][START_REF] Dssouli | Error detection with multiple observers[END_REF][START_REF] Dssouli | Conformance testing with multiple observers[END_REF]; if a test case has no controllability problems then it is controllable. Controllability problems can lead to situations in which we cannot know whether a test objective has been achieved and also make it more difficult to debug a faulty system and trace failures back to requirements. As a result, almost all work in distributed testing aims to produce controllable test cases (see, for example, [START_REF] Sarikaya | Synchronization and specification issues in protocol testing[END_REF][START_REF] Dssouli | Error detection with multiple observers[END_REF][START_REF] Dssouli | Conformance testing with multiple observers[END_REF][START_REF] Luo | Generating synchronizable test sequences based on finite state machine with distributed ports[END_REF][START_REF] Ural | Constructing checking sequences for distributed testing[END_REF][START_REF] Hierons | Checking sequences for distributed test architectures[END_REF]).

While there are test generation algorithms that produce controllable test cases from FSMs, these have inherent limitations. In particular, one can construct an FSM M such that controllable testing can achieve very little. Consider, for example, the fragment of an FSM shown in Figure 1. Here, the label x p /(y q , y r ) on an arc means that the input is x p at port p and the output is y q at port q and y r at port r, withdenoting no output at the corresponding port. If an input sequence starts with x 2 then there is no change in state and the resultant output is at port 2 only. Thus, for a test sequence to be controllable we require that the next input is at port 2, since only the tester at port 2 observed the previous input and output. It is straightforward to see that this situation continues and so any controllable test case that starts with x 2 cannot contain x 1 and only visits state s 0 . If we now consider a test case that starts with x 1 , the first input takes the FSM to state s 1 and produces y 1 at port 1 only. Therefore, for a test sequence to be controllable, the next input must be at port 1. However, if we apply x 1 then the FSM returns to s 0 and produces output at port 1 only. Thus, any controllable test case that starts with x 1 cannot contain x 2 and only visits s 0 and s 1 . Hence, if an FSM is of the form shown in Figure 1 then controllable testing can only visit s 0 and s 1 irrespective of how many states the FSM has.

There are several ways in which one might try to tackle the above problem. One approach is for the testers to synchronise actions through message exchange [START_REF] Cacciari | Controllability and observability in distributed testing[END_REF][START_REF] Rafiq | Coordination algorithm for distributed testing[END_REF]. When feasible, this allows controllability problems to be overcome and provides a general solution. However, this requires a network to be introduced and so can make testing more expensive. Message latency might also lead to situations in which a test case cannot be executed since it has timing [START_REF] Hierons | Canonical finite state machines for distributed systems[END_REF]. In particular, it is possible to construct an FSM χ min (M ) from the specification FSM M such that the transitions of χ min (M ) are those that can be executed in controllable testing and it is possible to construct a non-deterministic FSM χ max (M ) such that controllable testing can show that an SUT is faulty if and only if there are traces of the SUT that are not in the language defined by χ max (M ). One can use χ min (M ) and χ max (M ) to reason about the potential effectiveness of controllable testing. If the tester decides that controllable testing is sufficiently powerful then they can use a recently developed technique that generates a test suite that achieves as much as possible given the constraint that testing is controllable [START_REF] Hierons | Generating complete controllable test suites for distributed testing[END_REF]. It is also possible to abandon the restriction that we use controllable test cases. However, as noted above, there are good practical reasons for using controllable test cases and it has also been shown that test generation problems, such as finding a prefix of a test case that is guaranteed to take M to a given state s, become undecidable [START_REF] Hierons | Reaching and distinguishing states of distributed systems[END_REF].

Consider now the part of an FSM, with three ports, shown in Figure 2. If testing starts with input x 1 then a controllable test case can then apply input at any port. There are two paths that take the FSM from s 1 to s 4 : one has label x 2 /(y 1 , y 2 , -)x 3 /(y 1 , y 2 , y 3 ) and the other has label x 3 /(-, -, y 3 )x 2 /(y 1 , y 2 , y 3 ). Both of these are uncontrollable: in the first case the tester at port 3 does not observe input or output from the transition with label x 2 /(y 1 , y 2 , -) and in the second case the tester at port 2 does not observe input or output from the transition with label x 3 /(-, -, y 3 ). However, if we just require that the tester at port 2 sends input x 2 and the tester at port 3 sends input x 3 then state s 4 is reached irrespective of the order in which the inputs are supplied. Thus, even though a corresponding test case is not controllable, we do know that it reaches s 4 , with this situation being similar to partial order reduction (see, for example, [START_REF] Godefroid | Using partial orders to improve automatic verification methods[END_REF]). In addition, the testers at ports 2 and 3 know when s 4 has been reached since at this point they receive particular outputs (y 2 at port 2, y 3 at port 3). Testing can thus continue with one of these testers applying an input in state s 4 . In contrast, if one considers the two paths then in one case the tester at port 1 observes y 1 and in the other the tester at port 1 observes y 1 y 1 . If the tester at port 1 observes y 1 then there are two possible explanations and the state is either s 2 or s 4 . As a result, one cannot guarantee that the tester at port 1 knows when s 4 has been reached. This paper formalises and extends these ideas, showing how one can relax controllable testing while retaining some of its benefits. The rest of the paper is structured as follows. We start in Section 2 by defining FSMs and the notation used. Section 3 shows how we can relax the notion of controllability. Section 4 then considers computational complexity issues and a bounded form. Finally, Section 5 draws conclusions and discusses related work.

Preliminaries

This paper concerns the testing of a state-based system and, as such, we will reason about sequences of inputs and outputs. In testing the SUT will receive a sequence of inputs and there will be a resultant sequence of input/output pairs, called an input/output sequence or trace. Definition 1. We let X be the set of inputs of the SUT and Y the set of outputs of the SUT. Given x ∈ X and y ∈ Y , the corresponding input/output pair x/y represents the SUT producing output y in response to input x.

A trace is a (possibly empty) sequence of input/output pairs. The trace that has input/output pair x 1 /y 1 followed by x 2 /y 2 , . . . , and finally x k /y k will be represented using either x 1 /y 1 x 2 /y 2 . . . x k /y k , x 1 x 2 . . . x k /y 1 y 2 . . . y k , or x/ȳ where x = x 1 x 2 . . . x k and ȳ = y 1 y 2 . . . y k .

Given a sequence ā and an element a we let a• ā denote the sequence in which a is followed by ā. Given a sequence ā = a 1 . . . a k , with k ≥ 0, we will let pre(ā) = {a 1 . . . a i |0 ≤ i ≤ k} denote the set of prefixes of ā and we use to represent the empty sequence. Given a set A of sequences, pre(A) = ā∈A {pre(ā)}.

Since a trace is a sequence of input/output pairs, all prefixes of traces are also traces and so

pre(x 1 /y 1 x 2 /y 2 . . . x k /y k ) = {x 1 /y 1 x 2 /y 2 . . . x i /y i |0 ≤ i ≤ k}
Work on testing from an FSM in the distributed test architecture has used multi-port FSMs. In such an FSM, there is a finite set of ports, which represent the interfaces at which the SUT interacts with its environment. We let P denote the set of (m) ports, with {1, . . . , m} denoting the names of the ports. If an input is received in a multi-port FSM then this triggers a transition, which can lead to a change in state and at most one output being produced at each port. Definition 2. A multi-port FSM M with m ports is defined by a tuple (S, s 0 , X, Y, δ, λ) in which:

-S is the finite set of states of M . -s 0 ∈ S is the initial state of M . -X = X 1 ∪ . . . ∪ X m is the finite input alphabet of M , where for 1 ≤ p ≤ m,
X p is the input alphabet at port p and for all 1 ≤ p < q ≤ m we have that

X p ∩ X q = ∅. -Y = (Y 1 ∪ {-}) × . . . × (Y m ∪ {-})
is the output alphabet of M , where for 1 ≤ p ≤ m, Y p is the output alphabet at port p,denotes no output, and for all 1 ≤ p < q ≤ m we have that that Y p ∩ Y q = ∅. In addition, the inputs and outputs are disjoint and so

X ∩ ∪ 1≤p≤m Y p = ∅. -δ is the (total) next state function of type S × X → S. -λ is the (total) output function of type S × X → Y .
If M receives input x when in state s then it moves to state s = δ(s, x) and outputs an m-tuple y = λ(s, x). This defines a transition t = (s, s , x/y). We let T denote the set of transitions of M . When we refer to actions, a subscript will denote the port at which it is observed and a superscript will denote its position in a sequence.

The functions δ and λ can be extended in the usual way to deal with sequences of inputs. Specifically, given a state s ∈ S and a sequence of inputs

x = x 1 x 2 • • • x n we define δ(s, x) as δ(δ((• • • δ(δ(s, x 1 ), x 2 ) . . .), x n-1 ), x n ),
that is, the state reached after following the sequence x and we define λ(s, x) as

λ(s, x 1 ) • λ(δ(s, x 1 ), x 2 ) • . . . λ(δ((• • • δ(δ(s, x 1 ), x 2 ), . . .), x n-1 ), x n ), that

is, the sequence of tuples of outputs observed after following the sequence x.

A

path of M is a sequence ρ = (s 1 , s 2 , x 1 /y 1 )(s 2 , s 3 , x 2 /y 2 ) . . . (s k , s k+1 , x k /y k ) of consecutive transitions. We let x 1 /y 1 x 2 /y 2 . . . x k /y k denote the label of ρ.
The requirement that the alphabets at the ports are pairwise disjoint is not a restriction since one can label inputs and outputs with port numbers. We will use the term FSM for multi-port FSMs and the term single-port FSM for FSMs with one port. Note that our FSMs are deterministic: the current state and input received uniquely determine the next state and output produced. Most work on testing from single-port FSMs has concerned such deterministic machines (see, for example, [START_REF] Chow | Testing software design modeled by finite state machines[END_REF][START_REF] Lee | Principles and methods of testing finite state machines: A survey[END_REF][START_REF] Moore | Gedanken experiments on sequential machines[END_REF]), as has almost all work on distributed testing from FSMs (see, for example, [START_REF] Sarikaya | Synchronization and specification issues in protocol testing[END_REF][START_REF] Dssouli | Error detection with multiple observers[END_REF][START_REF] Dssouli | Conformance testing with multiple observers[END_REF][START_REF] Luo | Generating synchronizable test sequences based on finite state machine with distributed ports[END_REF][START_REF] Ural | Constructing checking sequences for distributed testing[END_REF][START_REF] Hierons | Checking sequences for distributed test architectures[END_REF]).

Next we introduce notation to project the actions of an input sequence or a trace onto a port. Definition 3. Given a sequence x ∈ X * and a port p, the projection π p (x) of x at port p can be inductively defined as follows:

π p (x) = ⎧ ⎪ ⎨ ⎪ ⎩ if x = x if x = x • x ∧ x ∈ X p x • π p (x ) if z = x • x ∧ x ∈ X p Definition 4.
Let M = (S, s 0 , X, Y, δ, λ) be an FSM with port set P such that |P | = m. Given an input/output sequence z and a port p, the projection π p (z) of z at port p can be inductively defined as follows:

π p (z) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ if z = z if z = x/(y 1 , . . . , y m ) • z ∧ x ∈ X p ∧ y p = - x • π p (z ) i f z = x/(y 1 , . . . , y m ) • z ∧ x ∈ X p ∧ y p = - y p • π p (z ) if z = x/(y 1 , . . . , y m ) • z ∧ x ∈ X p ∧ y p = - x • y p • π p (z ) if z = x/(y 1 , . . . , y m ) • z ∧ x ∈ X p ∧ y p = -
We say that π p (z) is a local trace.

Given an input/output pair x/y, ports(x/y) = {p ∈ P |π p (x/y) = } denotes the set of ports involved in x/y. Given transition t = (s i , s j , x/y), ports(t) = ports(x/y) and port(x) denotes the port p ∈ P such that x ∈ X p .

Note that we have overloaded π p and ports: the first one was previously used to project sequences of inputs and the second one denotes both the ports involved in an input/output pair and in a transition.

Let us suppose that the input sequence x 1 . . . x k leads to output sequence y 1 . . . y k when applied to M . In order for x 1 . . . x k to be controllable [START_REF] Cacciari | Controllability and observability in distributed testing[END_REF][START_REF] Ural | Distributed testing without encountering controllability and observability problems[END_REF][START_REF] Hierons | Controllable test cases for the distributed test architecture[END_REF] we require that the tester that applies x i knows when to send x i and that this is the case for all 1 < i ≤ k. If the tester at p sends x i (p = port(x i )) then it knows when to send x i if it observed the previous transition and this is the case if either x i-1 is at port p or y i-1 has non-empty output at port p. Definition 5. Let M = (S, s 0 , X, Y, δ, λ) be an FSM with port set P . Trace

x 1 /y 1 x 2 /y 2 . . . x k /y k is controllable if port(x i ) ∈ ports(x i-1 /y i-1 ) for all 1 < i ≤ k. Further, input sequence x 1 . . . x k is controllable if x 1 . . . x k /λ(s 0 , x 1 . . . x k )
is controllable and a path is controllable if its label is controllable.

Previous work [START_REF] Hierons | UIO sequence based checking sequences for distributed test architectures[END_REF] showed how a directed graph G(M ) can be produced from FSM M such that the paths of G(M ), from the vertex representing the initial state of M , correspond to the controllable paths of M . The construction of G(M ) is based on the following concepts. Definition 6. Let M = (S, s 0 , X, Y, δ, λ) be an FSM with port set P . For each state s ∈ S and port p ∈ P we denote by Depart p (s) the set of transitions of M whose starting state is s and whose input is at port p, that is, the set {(s, s , x/y) ∈ T |x ∈ X p }. For each state s and set P ⊆ P of ports we denote by Arrive P (s) the set of transitions whose ending state is s and that involve the set P of ports, that is, the set {(s , s, x/y) ∈ T |ports(x/y) = P}.

In order to ensure controllability, transitions belonging to Arrive P (s) can only be followed by input at a port p if p ∈ P. Thus, given transitions τ = (s 1 , s 2 , x/y) and τ = (s 2 , s 3 , x /y ), we can follow τ by τ without causing controllability problems if port(x ) ∈ ports(x/y). It is straightforward to see that if τ ∈ Arrive P (s 2 ) then we can follow τ by τ in controllable testing if and only if there is some p ∈ P such that τ ∈ Depart p (s 2 ). We will use these properties to construct the desired graph. Definition 7. Let M = (S, s 0 , X, Y, δ, λ) be an FSM with port set P . The graph G(M ) = (V, E) provides all the controllable sequences contained in M . The vertex set of G(M ) is defined in two steps. First, we define an auxiliary vertex set as follows:

1. v P s0 is in V aux . 2. For all s ∈ S and P ⊆ P we include v P s in V aux if Arrive P (s) = ∅. Edge set E is defined by: for each t = (s, s , x/y) ∈ T and v P s ∈ V aux with port(x) ∈ P we include in E the edge (v P s , v Pt s , x/y) where P t = ports(x/y). Finally, V is the subset of V aux that includes all the nodes reachable from v P s0 .

The notion of path (see Definition 2) can also be used with graphs: a path is a sequence of consecutive edges. The vertex v P s0 (the initial vertex ) represents the situation in which the first input has not yet been applied; this first input can be at any port. v P s denotes the situation in which M has reached state s and P is the set of ports that can receive the next input if testing is controllable.

Example 1. Consider the fragment of an FSM M with port set P = {1, 2, 3} depicted in Figure 3 (a). Figure 3 (b) shows G(M ). For each of the transitions that reaches a state of M , a new vertex is included in G(M ). For example, the state s 2 is reached by transitions (s 1 , s 2 , x 2 /(y 1 , -, y 3 )) and (s 0 , s 2 , x 3 /(-, -, y 3 )). Thus, two vertexes, V {1,2,3} s2 and V {3} s2 , respectively, are generated. The superscripts of each vertex contains the ports that are involved in the corresponding transition. The graph only contains those transitions whose input corresponds to a port included in the set associated with one of the vertices related to the outgoing state. For example, the transition (s 1 , s 2 , x 2 /(y 1 , -, y 3 )) cannot be included in the graph because the port 2, in which the action x 2 must be applied, does not belong to the set of ports of the only vertex associated to state s 1 , that is, V {1,3} s2 . Intuitively, a tester placed at port 2 cannot know when to apply the input x 2 because no action in the previous transition has been produced at this port. In this case we would have a controllability problem. Finally, we do not include

V {1,2,3} s2 because it is not reachable from V {1,2,3} s0 .
The following relates paths of G(M ) and controllable traces of M [START_REF] Hierons | UIO sequence based checking sequences for distributed test architectures[END_REF]. Proposition 1. For each path ρ of M that starts at the initial state of M and has a controllable label, there is a path ρ in G(M ) that starts at v P s0 and has the same label. In addition, for each path ρ of G(M ) that starts at v P s0 , there is a path ρ of M that starts at the initial state of M and has the same label.

Extending the graph G(M )

We have seen that an FSM might have states that cannot be reached using controllable input sequences; there might be a state s such that no vertex of

s0 s1 s2 x1/(y1, -, y3) x3/(-, -, y3) x2/(y1, -, y3) (a) M V {1,2,3} s0 V {1,3} s1 V {3} s2 x3/(-, -, y3) x1/(y1, -, y3) (b) G(M ) Fig. 3: Generation of G(M ) the form v P s is reachable in G(M ).
In this section we explain how G(M ) can be extended through including parts of a test that are not controllable but where the lack of controllability is not problematic. First we introduce test sections. We will use a double overline to denote a test section. In using a test section x, each tester simply applies its input sequence. Note that we allow empty sequences of inputs for some of the ports. We now consider conditions under which edges corresponding to test sections can be added to G(M ).

It is straightforward to determine which vertices of G(M ) can have edges labelled with a particular test section leaving them: in order to be able to apply (x 1 , . . . , xm ) in a vertex v P s we require that for every p ∈ P we have that if the tester at p is to apply input (x p = ) then p ∈ P. Definition 9. Let M = (S, s 0 , X, Y, δ, λ) be an FSM with port set P and x = (x 1 , . . . , xm ) be a test section. Let G(M ) = (V, E).

Given v P s ∈ V , we say that x can be applied from v P s if for all p ∈ P we have that xp = implies that p ∈ P. Given states s, s ∈ S, we say that x is convergent from s to s if for all x ∈ IN T (x) we have that s = δ(s, x). We also say that x takes M from s to s . Further, we say that x is convergent from s if there exists a state s such that x is convergent from s to s .

Convergence requires that all interleavings of the input sequences take M from state s to s ; we do not have to control which interleaving occurs. Having reached s , we might continue testing in a controllable manner. Proposition 2. Let M = (S, s 0 , X, Y, δ, λ) be an FSM with port set P , x = (x 1 , . . . , xm ) be a test section and s, s ∈ S. If M is in state s, x takes M from s to s , and from s the local tester at port p applies xp (for all p ∈ P ) then M is guaranteed to be in state s after all inputs from x have been received.

If x takes M from s to s then there is potential to add a new edge to G(M ) that represents this fact. However, we then need to determine which vertex v P s should be reached and so the set P of ports at which the next input (after the test section) can be applied. This set of ports should be the ports whose tester can determine when all of the inputs from (x 1 , . . . , xm ) have been received. The following gives a condition under which the tester at port p can determine this. Definition 10. Let M = (S, s 0 , X, Y, δ, λ) be an FSM with port set P , x be a test section, s ∈ S be a state of M and p ∈ P be a port. We say that port p ∈ P is termination aware when x is applied from state s if for all x ∈ IN T (x) and x ∈ pre(IN T (x)) \ IN T (x) we have π p (λ(s, x)) = π p (λ(s, x )). Once all inputs from x have been received the tester at p observes a local trace of the form π p (λ(s, x)) for some x ∈ IN T (x); the above condition ensures that this observation cannot have been made if one or more inputs from x have not been received. The following is clear from the previous definition. Proposition 3. Given FSM M = (S, s 0 , X, Y, δ, λ) with port set P and p ∈ P , let us suppose that p is termination aware when (x 1 , . . . , xm ) is applied from state s ∈ S. If (x 1 , . . . , xm ) is applied from s then the tester at port p knows when all inputs from each xq have been received.

We can now combine the notions of convergence and termination to obtain a weaker type of controllability. Definition 11. Let M = (S, s 0 , X, Y, δ, λ) be an FSM with port set P , s, s ∈ S be states, x be a test section, and P, P ⊆ P be sets of ports. Let us suppose that x takes M from s to s , P is the set of ports that are termination aware when x is applied from state s, and P is the following set of ports

P ∪ {p ∈ P |∀x, x ∈ IN T (x) : π p (λ(s, x)) = π p (λ(s, x ))}
Then we say that (s, x, s , P, P ) is a semi-controllable tuple of M . We let Reach(M ) be the set of semi-controllable tuples of M .

If (s, x, s , P, P ) is a semi-controllable tuple then x = (x 1 , . . . , xm ) is a test section with the property that if x is applied from state s (and for all p such that xp = , the tester at p knows that the state is s) then it takes M to s and the testers in P are termination aware. In this definition, a port p is in P if either p is termination aware or there is fixed output at p when the test section is applied. Essentially, p ∈ P captures two scenarios that ensure that if the tester at p observes an output from a transition that is after x then this tester can know that the output did not result from the application of the test section. We will see that this condition is important if we later wish to apply inputs at p. Reach(M ) may be infinite and so an algorithm should not include a step that generates this set. Instead, in this section we assume that there is some fixed R ⊆ Reach(M ); this will be a parameter of the algorithms introduced. In the next section we consider the case where we place a bound k on the size of the test sections used and so it is possible to generate the corresponding set Reach(M, k).

If (s, x, s , P, P ) is a semi-controllable tuple, p ∈ P and x is applied from state s then the tester at p can apply an input after x and know that this will be received in state s . This potentially allows an input x p ∈ X P to be applied in a state s even if G(M ) does not have a reachable vertex of the form v P s with p ∈ P . In such cases, it is possible to execute additional transitions of M in testing and to know that this has been achieved despite this not being possible in controllable testing.

We will add vertices and edges based on R ⊆ Reach(M ); if v P s is a current vertex and (s, x, s , P, P ) ∈ R then there is the potential to add a new vertex and edge if x can be applied from v P s (Definition 9). Before providing an algorithm, for extending G(M ), we will describe two additional factors that should be considered.

Example 2. Consider again the part of an FSM shown in Figure 2. We know that ( , x 2 , x 3 ) is a test section that takes this FSM from s 1 to s 4 and also that the testers at ports 2 and 3 are termination aware. Let us suppose that we follow this test section by input x 2 at port 2 and the corresponding transition t takes the FSM to a state s 5 and produces output (y 1 , y 2 , -). Then ports(t) = {1, 2} and so normally one would expect to be able to apply input at either port 1 or port 2 after t. However, at this point there are two possible observations at port 1: either y 1 y 1 y 1 or y 1 y 1 y 1 y 1 , depending on which path from s 1 to s 4 was followed. In addition, one of these (y 1 y 1 y 1 ) is an observation that might have been made in state s 4 . Thus, the tester at port 1 need not be able to determine when s 5 has been reached if t follows the test section from s 1 to s 4 .

Let us suppose that (s, x, s , P, P ) ∈ Reach(M ) is used to reach s . The example above shows that the restriction, on ports where one can apply inputs, may still be required after we apply an additional input x at p ∈ P: even if the tester at p observes output in response to x, the tester need not be able to know that the output was in response to x. This is because there may have been several possible observations at p in response to a test section previously used. Naturally, there is no problem if the test section led to a fixed output sequence at port p; this is why we use P in addition to P in tuples in Reach(M ) (see Definition 11). Thus, if we use (s, x, s , P, P ) then we impose the restriction that (in the current test sequence) no future input is applied at a port outside of P . We will achieve this by adding a second set of ports to the label of a vertex. A vertex with label v P1,P2 will denote the situation in which (in controllable testing) input can be applied next at any port in P 1 and in the current test sequence we require that no further input is applied at ports outside of P 2 . The graphs we construct will have that if v P1,P2 is a vertex then P 1 ⊆ P 2 . Similar to before, we will say that (x 1 , . . . , xm ) can be applied from v P1,P2 s if for all p ∈ P we have that xp = implies that p ∈ P 1 .

The second factor is that the addition of a new vertex v P1,P2 s is only useful if this provides potential for test execution that is not provided by current vertices; if it is not subsumed by the current vertices.

Algorithm 1 U pdate(G, R):

Updating graph G Input G = (V, E) and R ⊆ Reach(M ) V = V while V = ∅ do Choose some v P 1 ,P 2 s ∈ V V = V \ {v P 1 ,P 2 s } for all r = (s, (x1, . . . , xm), s , P, P ) ∈ R do P 1 = P ∩ P2 P 2 = P ∩ P2 if ∀1 ≤ p ≤ m : (xp = ⇒ p ∈ P1) and v P 1 ,P 2 s
is not subsumed by V then

V = V ∪ {v P 1 ,P 2 s } V = V ∪ {v P 1 ,P 2 s } E = E ∪ {(v P 1 ,P 2 s , (x1, . . . , xm), v P 1 ,P 2 s
)} end if end for end while Output (V, E) Definition 12. Let M = (S, s 0 , X, Y, δ, λ) be an FSM with port set P and let us consider a graph G = (V, E). Given a state s ∈ S and sets P 1 , P 2 ⊆ P , we say that a vertex v P1,P2 s is subsumed by the set V of vertices if for all p ∈ P 1 there exist P 1 , P 2 such that v

P 1 ,P 2 s ∈ V and p ∈ P 1 .
This definition ignores P 2 ; we do this in order to limit the size of the extended graph we form (we avoid a, potentially exponential, subset construction). The factors discussed above lead to the Update function in Algorithm 1 that extends the current graph G, whose vertices are of the form v P1,P2 s , on the basis of a set R ⊆ Reach(M ). Having used Algorithm 1, there may now be potential to add new edges and further vertices that correspond to controllable testing from the vertices added. This process is outlined in Algorithm 2.

The overall algorithm starts with the traditional graph G(M ) as defined in Definition 7 and repeatedly applies the Update and Complete functions until a fixed point is found. This process is outlined in Algorithm 3 in which G (M ) is the graph G in which a vertex of the form v P s is renamed v ) in the graph (see the dotted edge and vertex).

Next we consider the complexity of constructing the final graph, assuming that R is given. A vertex v P1,P2 s is added if it is not subsumed by the current is not subsumed by a vertex in V then

Algorithm 2 Complete(G, M ): Completing graph G Input G = (V, E) and FSM M V = V while V = ∅ do Choose some v P 1 ,P 2 s ∈ V V = V \ {v P
V = V ∪ {v P 1 ,P 2 s } V = V ∪ {v P 1 ,P 2 s } E = E ∪ {(v P 1 ,P 2 s , x, v P 1 ,P 2 s )} end if end for end while Output (V, E) Algorithm 3 Generating the graph G Input FSM M , G(M ) = (V, E) and R ⊆ Reach(M ) V = {v P,P s |v P s ∈ V } E = {(v P,P s , a, v P ,P s )|(v P s , a, v P s ) ∈ E} G = (V , E ) repeat G = G G = Complete(Update(G, R), M) until G = G Output G
vertices and this is the case if and only if there exists p ∈ P such that no current vertex v

P 1 ,P 2 s has p ∈ P 1 . If v P1,P2
s is added then this increases the number of ports p such that there is a vertex v P 1 ,P 2 s with p ∈ P 1 . As a result, given state s, Algorithm 3 can add at most m vertices of the form v P1,P2 s . Therefore, if R has already been produced then Algorithm 3 is a polynomial time algorithm. In the next section we explore the case where there are bounds on test section size and the complexity of the problem of generating Reach(M ) in this situation.

Bounding convergent test sections

In the previous section we showed how G(M ) can be extended using test sections. In principle such test sections might be arbitrarily long but we will want to use relatively short test sections if we want testing to be efficient. Thus, in practice one might want to place upper bounds on the lengths of test used. The

V {1,2,3},{1,2,3} s0 V {1,2,3},{1,2,3} s1 V {2,3},{2,3} s4 V {1,2},{1,2} s2 V {3},{3} s3 x3/(-, -, y3) x2/(y1, y2, -) x1/(y1, y2, y3) ( , x2, x3)
Fig. 4: Extension of G(M ) following two results provide additional motivation; they show that even the process of checking whether a test section is convergent is coNP-complete.

Theorem 1. Let M = (S, s 0 , X, Y, δ, λ) be an FSM, s, s ∈ S be states of M , and x be a test section. The problem of deciding whether x is convergent from s to s is coNP-complete.

Proof. We start by proving that the problem is in coNP. A non-deterministic Turing machine might guess an interleaving x ∈ IN T (x) and check whether x takes M from s to s . Since this process takes polynomial time, a non-deterministic Turing machine can decide in polynomial time whether there is an interleaving of x take M from s to a state other than s . Thus, the problem of deciding whether all interleavings of x take M from s to s is in coNP.

We now prove that the problem is coNP-hard by relating it to the negation of the (NP-complete) Hamiltonian Path Problem (HPP). Let us suppose that we are given a directed graph G and we wish to solve the HPP, which is to determine whether there is a path that includes all vertices exactly once. Let v 1 , . . . , v n be the vertices of G. We will construct an FSM M with inputs x 1 , . . . , x n (each x i at a separate port i) and states s 0 , s 1 , . . . , s n , s e as follows.

1. From the initial state s 0 input x i takes M to s i . 2. In state s i = s e , input x j has the following effect:

(a) If G contains an edge from v i to v j then we include a transition to s j . (b) Otherwise there is a transition to the "error state" s e . (c) In state s e , all inputs lead to no change of state. (d) The outputs of the transitions can be chosen arbitrarily. Now consider the test section (x 1 , . . . , x n ) and its possible interleavings. The key observation is that an interleaving x = x i1 . . . x in of (x 1 , . . . , x n ) takes M from s 0 to a state other than s e if and only if v i1 . . . v in is a path of G and such a path of G must be a Hamiltonian path of G. Thus, G has a Hamiltonian path if and only if (x 1 , . . . , x n ) is not convergent from s 0 to s e for M . Since the HPP is NP-hard, this means that it is NP-hard to check that a test section is not convergent. The result therefore follows.

Theorem 2. Let M = (S, s 0 , X, Y, δ, λ) be an FSM, s ∈ S be a state of M , and x be a test section. The problem of deciding whether x is convergent from s is coNP-complete.

Proof. The problem being in coNP follows from Theorem 1 and there being polynomially many states. The proof that the problem is coNP-hard follows in the same way as the proof of Theorem 1 since in the constructed FSM we have that the test section (x 1 , . . . , x n ) is convergent if and only if it converges to s e (if the final state is not s e , for interleaving x i1 . . . x in , then it is s in ).

Since we want to have efficient algorithms, we now explore the case where we place an upper bound on the size of test sections considered. Definition 13. Let M = (S, s 0 , X, Y, δ, λ) be an FSM, s, s ∈ S be states of M , k ≥ 0, and x = (x 1 , . . . , xm ) be a test section.

x is k-convergent from s to s if x is convergent from s to s and m p=1 |x p | ≤ k. Further, x is k-convergent from s if there exists a state s such that x is k-convergent from s to s .
Let M = (S, s 0 , X, Y, δ, λ) be an FSM and k ≥ 0. We define Reach(M, k) as the following subset of Reach(M ) (s, (x 1 , . . . , xm ), s ,

P, P ) ∈ Reach(M ) m p=1 |x p | ≤ k
Importantly, if we place an upper bound on k, or we fix k, then the number of interleavings defined by a test section is also bounded. As a result, the process of checking which states are reached using interleavings of a test section takes polynomial time. We therefore obtain the following results. Theorem 3. Let M = (S, s 0 , X, Y, δ, λ) be an FSM, s ∈ S be a state, k ≥ 0, and x be a test section. If k is bounded then 1. Given state s ∈ S, the problem of deciding whether x is k-convergent from s to s can be decided in polynomial time. 2. The problem of deciding whether x is k-convergent from s can be decided in polynomial time.

The next result follows from the fact that for bounded k the number of possible test sections, and the number of interleavings of each one, are bounded by polynomials. This shows that if we bound (or fix) k then we can compute Reach(M, k) in polynomial time and so Algorithm 3 takes polynomial time. On the contrary, from Theorem 1, we have that this result does not hold if we do not bound k (unless P = N P ). This suggests that Algorithm 3 can be applied with the entire set Reach(M, k) if one wishes to restrict attention to a relatively small value of k but otherwise one might use heuristics to generate some R ⊆ Reach(M ).

Conclusions

This paper concerned testing in the distributed test architecture, where a local tester only observes events at its port, the testers do not synchronise, and there is no global clock. Almost all test generation algorithms, for testing from an FSM in the distributed test architecture, return controllable test sequences but this can be restrictive. For example, an FSM specification M may have states that cannot be reached in controllable testing. We introduced the notion of a test section, which contains a fixed input sequence for each port. We showed how test sections can be used to weaken the classical notion of controllability: rather than require that the path of the FSM specification M traversed is uniquely determined, we instead require that there is only one state of M that can be reached by a test section (the test section is convergent). Thus, the notion of a test section being convergent is similar to partial order reduction. We showed how, given a set R of convergent test sections, one can derive a directed graph G that describes what can be achieved using these test sections. In general, one cannot expect to generate all convergent test sections, since this set might be infinite. However, we found that if one bounds the size of the test sections then one can generate the complete set (that satisfies this upper bound) in polynomial time. As a result, one can also generate the graph G in polynomial time.

There are several possible lines of future work. First, it would be interesting to explore alternative conditions under which one can efficiently generate the set Reach(M ). There is also the potential for the approach to be generalised to allow test sections whose components are adaptive (the next input depends on the observed output) and also to non-deterministic FSMs. One might also explore notions of coverage. Finally, one might implement the proposed technique in a tool and then carry out industrial case studies.

Fig. 1 :

 1 Fig. 1: Part of an FSM where controllable testing achieves little

3 )Fig. 2 :

 32 Fig. 2: Part of an FSM with controllability problems

Theorem 4 .

 4 Let M = (S, s 0 , X, Y, δ, λ) be an FSM and k ≥ 0. If k is bounded then the problem of generating Reach(M, k) has polynomial time complexity.

Definition 8 .

 8 Let P be a set of m ports. Given m sequences of inputs such that for all 1 ≤ p ≤ m we have that xp ∈ X * p , we say that the tuple x = (x 1 , . . . , xm ) is a test section. Given a test section x = (x 1 , . . . , xm ), we denote by IN T (x) the set of interleavings of the sequences x1 , . . . , xm . Formally, for all x ∈ X * we have that x ∈ IN T (x) if and only if for all p ∈ P we have π p (x) = xp .

  Consider the (part of an) FSM M in Figure2. G(M ) is showed in Figure4(non-dotted vertices and lines). Next we explain how Algorithm 3 works. Consider test section ( , x 2 , x 3 ) and R = {(s 1 , ( , x 2 , x 3 ), s 4 , {2, 3}, {2, 3})}. Note that ports 2 and 3 are termination aware, because the conditions included in Definition 10 are satisfied.The application of the update function to G(M ) and R creates a new vertex V

			P,P s	.
	Example 3. {2,3},{2,3} s4	and a new edge (V s1 {1,2,3}{1,2,3}	, (-, x 2 , x 3 ), V s4 {2,3},{2,3}

  1 ,P 2

	s	}
	for all p ∈ P1 and x ∈ Xp do
	s = δ(s, x) and y = λ(s, x)
	P = ports(x/y), P 1 = P ∩ P2
	P 1 ,P 2 s if v

Research partially supported by the projects DArDOS (TIN2015-65845-C3-1-R (MINECO/FEDER)) and SICOMORo-CM (S2013/ICE-3006).


Benedikt Eberhardinger
email: eberhardinger@isse.de

Axel Habermaier
email: habermaier@isse.de

Hella Seebach
email: seebach@isse.de

Wolfgang Reif
email: reif@isse.de

Back-to-Back Testing of Self-Organization Mechanisms

Keywords: Adaptive Systems, Self-Organization, Software Engineering, Software Testing, Quality Assurance, Back-to-Back Testing, Model-Based Testing

When developing SO mechanisms, mapping requirements to actual designs and implementations demands a lot of expertise. Among other things, it is important to define the right degree of freedom for the system that allows for self-organization. Back-to-back testing supports this hard engineering task by an adequate testing method helping to reveal failures in this design and implementation procedure. Within this paper we propose a model-based approach for back-to-back testing. The approach is built on top of the S# framework and integrated into the Visual Studio development environment, enabling the creation of executable test models with comprehensive tooling support for model debugging. By applying the concepts to a self-organizing production cell, we show how it is used to fully automatically reveal faults of a SO mechanism.

Introduction

The increasing complexity of current software systems has led to an increase of autonomy of software components that are resilient, flexible, dependable, versatile, recoverable, customizable, and self-optimizing by adapting to changes that may occur in their environments [START_REF] De Lemos | Software Engineering for Self-Adaptive Systems II, chap[END_REF]. Self-organization (SO) has become a keystone in the development of autonomous systems, allowing them to adapt their behavior and structure in order to fulfill their goals under ever-changing environmental conditions. Mechanisms of SO are built on top of the concepts of classical feedback loops (cf. [START_REF] Kephart | The vision of autonomic computing[END_REF][START_REF] Richter | Towards a generic observer/controller architecture for organic computing[END_REF]). Therefore, the environment and the components are sensed and controlled, using the feedback to adapt the behavior and/or structure of the components. Different architectural concepts were developed to engineer SO mechanisms, e.g., the MAPE Cycle [START_REF] Kephart | The vision of autonomic computing[END_REF] or the Observer/Controller Architecture [START_REF] Richter | Towards a generic observer/controller architecture for organic computing[END_REF]. As an important part of the development of SO mechanisms, testing needs to be integrated in order to achieve the required quality level of the system. This paper presents a thorough approach for supporting the engineering of SO mechanisms by back-to-back (BtB) testing [START_REF] Vouk | Back-to-back testing[END_REF] of feedback loop-based self-organization mechanisms. In our experiences in developing SO mechanisms, mapping requirements to actual designs and implementations demands a lot of expertise. Among other things, it is important to allow the system the right degree of freedom to enable self-organization. Back-to-back testing supports this engineering task with an adequate testing method helping to reveal failures in this design and implementation procedure. In order to supply BtB testing for SO mechanisms, we are faced by the following challenges:

1. Supplying test oracles that are able to cope with the unbounded decision space formed by different possible configurations of the systems controlled by the SO mechanism(s) as well as the huge state space of the mechanisms themselves. 2. Systematic test case selection is needed since exhaustive testing is not possible due to the unbounded state space. Additionally, most SO algorithms are based on heuristics, making their behavior quite non-deterministic and their state space non-uniform. Thus, common test case selection strategies relying on structured program behavior cannot be used. 3. Automation of test execution and evaluation is a keystone for the success, since this is the only way to execute the large test suites.

We address these challenges in a model-based approach for BtB testing where the test model mainly consists of two parts: [START_REF] Cámara | Evaluation of resilience in self-adaptive systems using probabilistic model-checking[END_REF] the model of the system controlled by the SO mechanism, i.e., the environment model, and (2) the model of the intended behavior of the SO mechanism, i.e., the test model. The latter is based on our concept of the corridor of correct behavior (CCB) [START_REF] Güdemann | A specification and construction paradigm for organic computing systems[END_REF] that describes the intended behavior of the system as a set of constraints. The concept of the CCB is used as part of the test oracle by evaluating the constraints on the current state of the model resp. system [START_REF] Eberhardinger | Towards testing self-organizing, adaptive systems[END_REF].

The model of the system to be controlled by the SO mechanism is used for test case generation as well as for their execution. This is possible due the S# modeling framework used by our approach: With S#, executable model instances can be composed together with a high degree of flexibility in order to test different system configurations. Furthermore, it is possible to integrate the concrete SO mechanism(s) under test into the execution environment provided by S# and to map the mechanism's state back into the model instances for evaluation within S#. The evaluation is based on checks whether the current state matches the constraints made in the model of the intended behavior.

Overall, the following main contributions will be presented: The paper is organized as followed: The next section embeds the approach into our overall testing concept for self-organizing, adaptive systems. After the introduction of the case study (Section 3), Section 4 gives an overview of our S# modeling framework and the BtB testing model. Section 5 describes model of intended behavior of the SO mechanisms. Section 6 shows how test cases are generated and executed. Section 7 evaluates the approach. We consider related work in Section 8 and conclude in Section 9.

The Corridor Enforcing Infrastructure

Our approach for testing self-organizing, adaptive systems (SOAS)-and consequently for testing SO mechanisms-is based on the Corridor Enforcing Infrastructure (CEI) [START_REF] Eberhardinger | Towards testing self-organizing, adaptive systems[END_REF]. The CEI is an architectural pattern for SOAS using regio-central or decentralized feedback loops to monitor and control single components or small groups of components in order to ensure that the system's goals are fulfilled at all times. The CEI implements the concepts and fundamentals of the Restore Invariant Approach (RIA) [START_REF] Güdemann | A specification and construction paradigm for organic computing systems[END_REF]. RIA defines the Corridor of Correct Behavior (CCB), which is described by the system's structural requirements, formalized as constraints. Concerning a self-organizing production cell scenario the CCB is formed by the constraints describing valid configurations of the system. The conjunction of all these constraints is called the invariant (INV ). An exemplary corridor is shown in Fig. 1: The system's state is inside the corridor if INV is satisfied; otherwise, the system's state leaves the corridor, indicated by the flash. In that case, the system has to be reorganized in order to return into the corridor, as shown by the transition with a check mark. A failure occurs if a transition outside of the corridor is taken, like the one marked by a cross, although a transition back into the corridor exists.

The CEI implements the RIA either with centralized or decentralized pairs of monitors and controllers, as proposed by the MAPE cycle [START_REF] Kephart | The vision of autonomic computing[END_REF] or the Observer/Controller (O/C) architecture [START_REF] Richter | Towards a generic observer/controller architecture for organic computing[END_REF]. Figure 2 shows a schematic view of one possible implementation of the CEI based on the O/C architecture where the essential parts are the system under observation and control (SuOC), i.e., single agents or groups of agents; the observer (O), i.e., the component monitoring the state of the SuOC (in-or outside of the CCB) and providing information to the controller; and the controller (C), i.e., the SO algorithms controlling the SuOC. Note that the CEI consists of sets of nested feedback loops controlling the entire system. Figure 2 further sketches the different layers for testing to cope with the complexity of the system: agent, interaction, and system layer.

The reorganization by the controller is performed by one or more SO algorithms resulting in a new system configuration. Such a system configuration has to satisfy the constraints describing a valid organizational structure. The concrete choice of the SO algorithms and their constraints has no impact on our approach. Since the system behaves like a traditional software system inside the CCB, traditional test approaches can be used to ensure the quality of the SuOC. The CEI, by contrast, enables self-organizing and adaptive behavior of the system and demands new concepts for testing to cope with the challenges described in Section 1.

In order to grasp SO mechanisms for testing, we need techniques to stepwise examine the CEI and its mechanisms, covering the following responsibilities of the CEI: correct initiation of a reorganization if and only if a constraint is violated (monitoring infrastructure, R-Detect); calculation of correct system configurations in case of violations (R-Solution); and correct distribution of these configurations within single agents or small groups of agents controlled by the CEI (R-Distribution). In this paper, we focus on revealing SO mechanism failures which relate to (R-Detect) and (R-Solution), extending our approach of isolated testing of SO algorithms presented in [START_REF] Eberhardinger | An approach for isolated testing of self-organization algorithms[END_REF].

O C O C O C O C O C O C O C O C O SuOC C O SuOC C O SuOC C O C Observer Constraint Monitor Controller Self-x-algorithms O SuOC C O SuOC C O SuOC C Agent Layer Interaction Layer System Layer R-Detect R-Solution R-Distribution Figure 2
. Schematic view of one CEI implementation and its different layers for testing (agent, interaction, and system layer) [START_REF] Eberhardinger | An approach for isolated testing of self-organization algorithms[END_REF].

3 Case Study: The Self-Organizing Production Cell

Future production scenarios demand for much more flexibility [START_REF] Elmaraghy | Variety management in manufacturing cyber-physical production systems: Roots, expectations and r&d challenges[END_REF] than today's shop floor design to cope with the trend towards small series production, individualized products and the reuse of production stations for different tasks. This flexibility becomes possible due to the increased automation and data exchange in manufacturing technologies. These future cyber-physical systems will integrate self-organization mechanisms to resolve the tasks of decentralized decision making, to optimize the systems structure, and to autonomously react to component failures at runtime increasing the system's robustness. We envision self-organizing production cells, where the production stations are modern robots equipped with toolboxes and the ability to change their tools whenever necessary (self-awareness). They are connected via mobile platforms (carts) that are able to carry workpieces and to reach robots in any order. Thus, the production cell is able to fulfill any task which corresponds to tools (capabilities) available in the cell. This is possible due to the SO mechanisms that reorganize the carts and robots in a way that the tools are applied to the workpieces in the correct order. Finding a correct allocation of tools to robots and according routes to carts (system configuration) constitutes a constraint satisfaction problem. Any violation of the calculated configuration (represents a state of the system within the CCB) at run-time triggers the SO algorithm calculating and distributing a new system configuration. A tool-supported approach to systematically model and analyze these kind of systems is shown next.

Building the Environment Model of SO Systems

The self-organizing production cell is an instance of the system class of self-organizing resource-flow systems; a metamodel [START_REF] Seebach | How to Design and Implement Self-organising Resource-Flow Systems[END_REF] Our approach is divided into three parts: the first part consists of the S# test model as well as corresponding configuration descriptions (cf. Section 4). The second part is the test platform that instantiates a system configuration as the basis for the test case generation with DCCA; the component fault models represent the test cases that are evaluated (cf. Sections 4 and 6) and provide the test oracles for the observer and controller (cf. Section 5). The third part represents the actual behavior of the SO mechanism which must be mapped to the intended behavior after each execution for evaluation purposes (cf. Section 6).

DCCA Algorithm

System under Test Test Platform S# Test Model

System Model

as drills and screwdrivers that they use on the workpieces. A Task requires a workpiece to be processed by a sequence of tool applications, e.g., by applying the drill, insert, and tighten Capabilities. Therefore, the robots and carts are responsible for processing incoming workpieces in a given sequence of tool applications. The Roles assigned to each robot and cart indicate which tools they apply on the workpieces or which robots the resources are transported between, respectively. The Observer/Controller forms the SO mechanism of the system; it is responsible for reconfiguration in order to compensate for broken tools, blocked routes, or to incorporate new tools, robots, or carts, for instance. The case study is modeled using the S# modeling and analysis framework for safety-critical systems [START_REF] Habermaier | Runtime Model-Based Safety Analysis of Self-Organizing Systems with S#[END_REF]. As its modeling language is based on the C# programming language, the metamodel shown in Section 4 can be directly represented by a set of C# classes, with two additional classes RobotAgent and CartAgent derived from Agent encapsulating the production cell-specific parts of the model. Even though the S# model of the case study is represented by a C# program, it is still a model and not Listing 1. Parts of the S# instantiation code for a configuration of the case study consisting of five workpieces that require the task PDITPC to be carried out on them. Four robots are created with some minor redundancy in available capabilities. The two carts connect all four robots via bidirectional routes. the actual implementation; for instance, it completely abstracts from any distribution concerns, executing all modeled agents locally to simplify modeling and analysis. S# also allows the composition of a model to be automated: Arbitrary C# code can be executed to instantiate system components and to connect them together in order to build up the overall model, thereby providing meta-constructs for model creation. These capabilities are particularly useful for the creation of different system configurations when testing the case study; model instantiation with S# is illustrated by Listing 1.

S# executes the models as regular C# programs, taking care of potential nondeterminism in the models such that all combinations of non-deterministic choices are fully analyzed. It is also possible to spawn additional processes during model checking, enabling the integration of other tools into the models and the analyses: For the case study, for example, a constraint solver is used to model the SO algorithm within the Observer/Controller. Whenever a reconfiguration is required, the S# model encodes the current system configuration for the constraint solver, requests a solution from it, and applies the returned solution back onto itself. [START_REF] Falcone | Runtime verification of component-based systems[END_REF] The Test Model for the Intended Behavior of the SO Mechanisms S# integrates, as shown in Section 4, the complete testing framework, including test cases derivation, test cases execution, as well as test case evaluation and logging. In order to enable the evaluation of test cases, the overall model needs to be extended by the test model. The extension encompasses a definition of the intended behavior of the system under test within the S# model, as shown in the right part of Section 4. Within the BtB testing approach, we propose this one important step: to co-develop the intended behavior of the system and check it against the actual behavior. Thus, the co-development of the intended behavior is used in order to check whether it corresponds to the actual behavior. The intended behavior is modeled in two parts, consisting of (1) a description of valid system states, i.e., the INV of the CCB for the SO mechanism, as well as further constraints concerning the form of the results of the SO algorithms itself and (2) an evaluation mechanism that is able to state whether there is a possible configuration for the current system state in order to spot whether the SO algorithm missed a valid solution.

Valid system states are determined using one of the major advantages of the CCB for testing SOAS: INV is a way to distinguish between correct and incorrect actions of SO mechanisms-as described in Section 2. A failure occurs if a violation of the CCB is not detected (R-Detect), the computed solution does not lead to a system configuration inside the CCB (R-Solution), or a correct solution is distributed incorrectly (R-Distribution). The approach of this paper focuses on the first two aspects. As a basis for the evaluation, the constraints that form the CCB are developed separately-an important step of codevelopment in BtB testing-and integrated into the model. Listing 2 shows how parts of the production cell case study's CCB constraints are specified in the S# model.

The constraints that form the oracle are divided into two parts, one for the observer and one for the controller (cf. Section 4). The observer part describes all violations of the CCB that have to be detected by the observer.The constraints of the observer oracle are evaluated after the observer decided whether to reconfigure or not and the oracle judges this decision. Afterward, the controller might be activated-in case of an activation by the observer-and the result is evaluated by the controller oracle. Note that for both evaluations, the mapping between the actual SO mechanism has to be establish with the test system, i.e., the results need to be interfaced. For the evaluation of the controller a set of the constraints needs to be evaluated that is part of the controller oracle. In most cases there are overlaps between the two constraint sets, however, mostly the set of the controller oracle is a superset of the constraints of the observer oracle, however, it also might be vice versa. The additional constraints in the oracles might be due to the fact that additional requirements are necessary to fully check the results of the different parts of the SO mechanism. In our case study, this is the case for the controller oracle. The additional constraint concern the assigned roles for the robots and carts: they must be connected in the correct order for any task after reorganization so that they are applied the right way (for instance, drill, then insert, then tighten). This constraint would not be checked by the observer, since no environmental influence would change the role definitions; only the tools within the roles are affected, for instance.

The satisfiability check of the oracle focuses on another obligation for the SO algorithm: if a solution for a new system configuration is feasible on the current system instance, the SO algorithm must find it in order to find a valid configuration for the running system. If we do not check that second part of the solution we would neglect faults resulting from too strict restrictions made as a design decision in the development. Indeed, in the BtB testing approach, we aim at revealing such errors. For this purpose, it is necessary to search in the configuration space for possible configuration(s) of the system that fulfill all requirements resp. constraints considered in the previous paragraph. We use a search algorithm that systematically checks every given configuration for validity; if one is found then a solution is possible and the SO algorithm has to find it. Section 5, for Algorithm 1 Checks whether a reconfiguration is possible for a given set of robot and cart agents as well as the tasks to be carried out. for i = 0 to |task.Capabilities| -1 do 8:

A ← {a ∈ m[a ] | a ∈ A ∧ t.Capabilities[i + 1] ∈ a.AvailableCapabilities } 9:
if |A| = 0 then 10:

return false 11:

end if 12:

end for 13: end for 14: return true instance, shows a search algorithm that evaluates whether a reconfiguration is possible for the case study of the production cell: It starts by checking whether all capabilities needed for the tasks that should be applied in the system are available, e.g., if a task requires drilling at least one robot must be able to drill. If that prerequisite is satisfied, the algorithm checks whether the robots with the necessary capabilities are connected by carts such that workpieces can be transported between them in way that the tasks can be fulfilled. Such an algorithm, if one exists at all, might be expensive in time and space. But this is acceptable due to the following facts: the check has to be performed only occasionally during the testing process as it is only executed when no solution is found by the SO algorithm; when the SO algorithm cannot find a solution, the configuration space is small in most cases.

Generating and Executing Test Cases with S#

A necessary prerequisite for deriving and executing test cases is to instantiate the model with a concrete configuration, e.g., the numbers and kinds of robots in the production cell. Within one such configuration the number of different test cases are determined by the different possible environmental events the system has to adapt to. Since the number of different configurations is unbounded, a concrete configuration is chosen for testing. Subsequently, test cases for a chosen configuration are defined by triggering environmental events that are modeled as S# component faults, e.g., a tool breaks, a path for carts get blocked, and so on. All of these events result in reconfigurations, i.e., executions of the SO mechanism. The huge number of configurations and component faults make exhaustive testing impossible, thus, we follow a two-part test selection strategy. d latter adding the concrete observer to a tested SO algorithm.

Test Case Generation for SO Mechanisms

The test strategy we purpose is based on the ideas of virtual commissioning and boundary interior testing. On the one hand, we only consider one concrete configuration and use the concepts of virtual commissioning to check other configurations on demand; on the other hand, the concepts of boundary interior testing are applied to SO mechanisms to find relevant test cases more quickly.

Virtual Commissioning of SOAS Systems for Test Case Reduction

The concept of virtual commissioning is mainly applied in the field of large manufacturing systems where a virtual manufacturing system is built in order to simulate individual manufacturing processes for optimization and validation purposes [START_REF] Lee | Survey on the virtual commissioning of manufacturing systems[END_REF]. Within this virtual environment, the real controller is executed on the virtual plant enabling to test, tune, or initialize it for a specific configuration of the plant. We adopt this concept for the reduction of possible configurations of the system to be tested. The idea is to base the tests on only one configuration, namely, the one which should be rolled out afterward. Indeed, there will be changes at run-time, e.g., new robots are integrated, new tools are added, or tasks change. Before such a change is rolled out to the running system, the model instance must first be updated and the tests have to be re-run on the new instance. Since the change of the current configuration of the system is due to a human intervention-we assume the system not to extend itself by other components or similar-it is possible to run this test-first-deploy-after strategy at run-time. Thus, we select only the configuration for testing that is crucial for the deployment and have the ability to test new configurations on demand. This is possible due to the generic S# test model in which it is easy to instantiate new configurations (cf. Listing 1) and to automatize the testing process.

Boundary Interior Testing for SO Mechanisms For test case selection within one configuration of the system we adopt the concepts of boundary interior testing, where the idea is to select test cases at the boundary of expected behavior changes. The boundaries of SO mechanisms are states of the system where reconfiguration is rarely possible, i.e., where only few solutions are still possible. Reconfigurations, as we consider them, are mainly driven by changing environmental conditions that force the system to reorganize itself. In our test model, we define these changing conditions as component faults of the controlled system such as a robot being unable to apply its tools in the production cell case study. The component faults are part of the S# model.

In order to find the component faults that bring the system to its boundaries, we use Deductive Cause-Consequence Analysis (DCCA). DCCA is a fully automated modelbased analysis techniques integrated into S#, usually used to assess the system's safety by computing all minimal cut sets for a hazard [START_REF] Habermaier | Runtime Model-Based Safety Analysis of Self-Organizing Systems with S#[END_REF]. Minimal cut sets are combinations of component faults that can cause a hazard, characterizing a cause-consequence relationship between component faults (the causes) and the hazard (the consequence): a set of component faults is a cut set for a hazard if and only if there is the possibility that the hazard occurs and before that, at most the faults in the fault set have occurred. DCCA has exponential complexity as it has to check all combinations of component faults. In practice, however, the number of required checks usually is significantly lower, as the cut set property is monotonic with respect to set inclusion. DCCA can also be used to compute the boundaries of SO mechanisms: the hazard is simply defined as the inability for further reconfigurations. To compute the boundaries, the combinations of component faults are checked in order to determine whether such a set does or does not have the potential to cause that hazard. DCCA automatically chooses the next set of component faults to be activated, i.e., the next test case, and executes it.S#'s standard approach for DCCA checks the fault sets by increasing cardinality, thus the approach also includes test cases for inner boundary tests. The concepts of boundary interior testing for SO mechanism is exemplified in Section 6.1. The left box refers to a naïve approach where test cases are selected in a depth-first attempt and the boundaries of the SO mechanisms are not taken into account. That implies that many negative test cases are executed where less faults are expected to be revealed; in our evaluation no fault has been detected by these negative tests. The middle box of Section 6.

Test Case Execution with S#

In order to achieve significant results, we advocate to integrate different parts of the SO mechanism step-wise: first isolate the SO algorithms, which form the controller, and afterward hook up the observer part. That enables to assign possible failures to the different parts, e.g., if a test suite is re-run after it has passed for the SO algorithm with a hooked up observer, the failure is most likely due to a faulty observer. In order to unhook the observer, the controller is triggered after every execution step, causing the system to continuously reconfigure itself. This leads also to a reduction of failure overlapping due to a missing activation of the controller by the observer. Since S# models are fully executable, the generation and selection of test cases, their execution, and their evaluation are automatically performed together. Additionally, it is also possible to manually execute or re-execute given test cases. The integration of S# into Visual Studio lets the development and execution of the test model benefit from the whole tool support of Visual Studio, e.g., the debugger. Thus, it is possible to step through every test case to monitor and control the execution and the state changes, making fault localization and test model development much easier.

Evaluation

For our evaluation-whose implementation is fully available at http://safetysharp. isse.de-we addressed the following four research questions:

R1 Is the proposed approach for testing SO mechanisms applicable to real scenarios?

R2 Is the approach able to reveal failures in SO mechanisms? R3 Do real faults reflect the ideas proposed and exploited for test case generation (i.e., occur faults at the boundaries of the SO mechanism?)?

R4 Does the mechanism for reaching these boundaries outperform a naïve approach?

For the evaluation, we co-developed a SO mechanism for the self-organizing production cell, described in Section 3. However, the test cases and constraints are applicable to the whole system class of self-organizing resource-flow systems and in particular, the concrete implementation of the SO algorithm can be replaced by any other implementation. In the case at hand, we used MiniZinc1 as a constraint modeling language with FlatZinc as the low-level solver. The system constraints have therefore been translated into a MiniZinc model that describes valid configurations for the production cell; the MiniZinc input for a system configuration is shown in Listing 3. Thus, it is possible to feed the SO algorithm with a specification of a task, the number of agents (carts and robots), the capabilities, and the routing table. If satisfiable, the SO algorithm returns a solution that assigns each tool needed for the task to some robot and that routes the carts between the robots accordingly. This SO algorithm has been plugged into S# via an interface that provides the specification of the problem to be solved by the SO algorithm and that parses MiniZinc results. The constraints of the observer of the SO mechanism-originally developed in Java for our implementation of the production cell based on the multi-agent system Jadex2 -have been converted to C# in order to integrate them into the S# model. This completes the integration of the developed SO mechanism into the S# model and shows that real scenarios are realizable with our approach (R1).

For evaluation purposes, we analyzed different configurations (cf. Table 1) of the production cell. The configurations differ in the number of agents (robots and carts), the average number of capabilities per robot, the number of tasks, and the number of routes established by the carts between the robots.

One main achievement of the evaluation is that we were able to reveal the following faults with the implementation of the SO mechanism; each fault is annotated with the responsibility of the SO mechanism where the fault was detected (cf. Section 2): Listing 3. The input model for MiniZinc describing a task, the available capabilities of the robots, as well as the connection matrix based on the carts' routes, corresponding to the configuration instantiated by Listing 1.

F1 The fault affected route handling: the MiniZinc implementation interpreted transitive routes as direct ones. Its computed configurations included direct connections that were not available, e.g.

0 → 2 = 0 → 1 → 2 (R-Solution).
F2 The fault was that the SO algorithm expected the routes to be unidirectional while they were in fact bidirectional. The failure manifested itself as overlooked solutions even though at least one existed (R-Solution).

F3

The fault was a wrong implementation of the interface for the SO algorithm. The interface expected first the capability of a designated agent, but got the first capability of the task assigned to the designated agent (R-Solution).

F4 The fault was a wrong format for the mapping of the solution from the SO algorithm to the system model concerning the pre-and postconditions of a role (R-Distribution). . This fault was detected even though the testing approach was initially not focused on R-Distribution.

F5

The fault was a too narrow restriction in the SO algorithm that did not allow to use intermediate robots that apply no tools since the maximum length of concatenated roles was restricted. Thus, Listing 3 was mistakenly considered to be unsatisfiable instead of returning the following solution, for instance: agents = [START_REF] Cámara | Evaluation of resilience in self-adaptive systems using probabilistic model-checking[END_REF][START_REF] Falcone | Runtime verification of component-based systems[END_REF][START_REF] Elmaraghy | Variety management in manufacturing cyber-physical production systems: Roots, expectations and r&d challenges[END_REF][START_REF] Fredericks | Towards run-time testing of dynamic adaptive systems[END_REF][START_REF] Eberhardinger | Towards testing self-organizing, adaptive systems[END_REF][START_REF] Fredericks | Towards run-time testing of dynamic adaptive systems[END_REF][START_REF] Elmaraghy | Variety management in manufacturing cyber-physical production systems: Roots, expectations and r&d challenges[END_REF][START_REF] Falcone | Runtime verification of component-based systems[END_REF][START_REF] Eberhardinger | An approach for isolated testing of self-organization algorithms[END_REF][START_REF] Falcone | Runtime verification of component-based systems[END_REF][START_REF] Elmaraghy | Variety management in manufacturing cyber-physical production systems: Roots, expectations and r&d challenges[END_REF][START_REF] Fredericks | Towards run-time testing of dynamic adaptive systems[END_REF][START_REF] Eberhardinger | Towards testing self-organizing, adaptive systems[END_REF][START_REF] Eberhardinger | Towards testing self-organizing, adaptive systems[END_REF][START_REF] Fredericks | Towards run-time testing of dynamic adaptive systems[END_REF][START_REF] Elmaraghy | Variety management in manufacturing cyber-physical production systems: Roots, expectations and r&d challenges[END_REF]; workedOn = [1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 4, 5, 0, 6] (R-Solution).

F6

The fault was a missing constraint with the observer, namely the I/O-Consistency constraint checked in the oracle of Listing 2. The failures occurred after activating a component fault that deactivates a cart that is part of the active task (R-Detection).

The faults F3, F4, and F6 have been detected in all investigated configurations. Indeed, F1, F2, and F5 mainly depend on the routing structure used in the configuration, e.g., smaller configurations would not be able to reveal the faults. F6 mainly depends on changing the active robots or carts of a task, since their removal might not be detected and the controller is consequently not activated. All detected faults mainly concern misinterpretation of requirement specifications. The kind of faults that we detected underpins one of the strengths of our approach: the ability to reveal faults which are the result of a misinterpretation of the specification (R2). To answer R3 and R4, we focused on the performance of test case generation and execution, investigating the abilities of the boundary interior testing approach for SO mechanisms. The results concerning the failures revealed, especially F1, F2, and F5, that the failures are more likely occur on the boundaries where SO switches between being possible and impossible; e.g., F1 was revealed when only one possible routing was left to fulfill the task, while F2 was revealed when no more routing is possible for the task. For R4, we used a test case generation algorithm using a depth-first search strategy that systematically explores the input space without respecting the boundaries of SO, unlike our proposed approach. The overall testing times required by the test system to reveal the failures and the number of test cases used is measured in Table 2.

At a first glance, the results indicate that the proposed approach for test case generation does not payoff as expected in most cases. That is mainly an effect of the kinds of faults we detected in the SO mechanisms which are able to be revealed with quite a lot different combinations of component faults and thus detected very early on. However, for F5 the potential of the approach especially for a bit more sophisticated faults is shown. Furthermore, it is even possible to optimize the concepts based on how the DCCA is used for reaching the boundaries. Currently, DCCA is applying a kind of depth-first search towards the states where no reconfiguration is possible anymore. Within this search, DCCA further performs optimizations according to the activation of the component faults based on monotonicity of the cut set property.

Related Work

The approach for testing adaptive system could be clustered into run-time and designtime approaches; both have identified non-determinism and the emergent behavior as the main challenges for testing adaptive systems.

Run-time approaches for testing take up the paradigm of run-time verification [START_REF] Falcone | Runtime verification of component-based systems[END_REF][START_REF] Leucker | A brief account of runtime verification[END_REF]. They shift testing into run-time to be able to observe and test, e.g., the adaptation to new situations. Camara et al. [START_REF] Cámara | Evaluation of resilience in self-adaptive systems using probabilistic model-checking[END_REF] use these concepts to consider fully integrated systems. Their testing approach focuses mainly on testing the non-functional properties of resilience of the adaptive system. The gained information is used as feedback for the running system. A similar approach is taken by Ramirez et al. [START_REF] Ramirez | Automatically exploring how uncertainty impacts behavior of dynamically adaptive systems[END_REF], also focusing on non-functional requirements. The authors use the sampled data from a simulation to calculate a distance to the expected values derived from the goal specification of the system. This information is subsequently used to adapt the system or its requirements proactively. The run-time approaches are limited to tests of the fully integrated system and therefore are faced with problems like error masking which is very likely in such self-healing systems. In our testing approach, by contrast, we benefit from the piecemeal integration of the system for testing. Thus, it is possible to avoid error masking by testing the SO mechanism in an isolated way. Another important difference to the aforementioned work is that we use these techniques for finding failures instead of analyzing the current system state for generating feedback for adaptation. Still, we also use the basic concepts of run-time testing. The CEI allows us to split the evaluation into the three responsibilities of R-Detection, R-Solution, and R-Distribution which in turn enables us to evaluate the runs without the evaluation of complex system states on the system level.

Design-time approaches like [START_REF] Nguyen | Testing Techniques for Software Agents[END_REF][START_REF] Zhang | Model based testing for agent systems[END_REF] test the systems in a classical manner during development. All of these approaches consider some dedicated parts of the system. Consequently, it is not possible to give evidence about the correct functionality of the overall system. Zhang et al. [START_REF] Zhang | Model based testing for agent systems[END_REF] compose their tests towards fully integrated system tests, but they do not consider adaptivity or SO explicitly since they focus on testing the correct execution of plans within multi-agent systems. Nguyen [START_REF] Nguyen | Testing Techniques for Software Agents[END_REF] promotes an approach for a component test suite, but does not consider interactions between or organization of components as it would be necessary for SO.

The evaluation of the test results, i.e., the application of a test oracle for adaptive behavior is only considered by Fredericks et al. [START_REF] Fredericks | Towards run-time testing of dynamic adaptive systems[END_REF] and Nguyen et al. [START_REF] Nguyen | Automated oracles: An empirical study on cost and effectiveness[END_REF]. Both approaches rely on goals reflecting the requirements of the system that are somewhat loosened in order to reflect the ever-changing environment the components have to adapt to: The approaches mitigate the goals with the RELAXed approach or consider soft goals that do not need to hold at all times. Consequently, the decisions of the test oracle are rather fuzzy. In our approach, the definition of correct and incorrect behavior is given by the CCB that enables us to clearly decide whether a failure indeed occured.

Back-to-back testing was initially proposed by Vouk [START_REF] Vouk | Back-to-back testing[END_REF] and describes the concept of the co-development of a test framework and the actual system or mechanisms based on the same requirements, letting the systems compete with each other in order to reveal discrepancies and errors. Back-to-back testing is focused on functional testing of the system with a special attention on the correct interpretation of the actual requirements and their implementation. The assumption made is that two different developers resp. development teams will not make the same mistake twice, i.e., misinterpret or neglect functional requirements, and so the discrepancies between the two systems reveal potential development errors. In [START_REF] Schiendorfer | Back-to-Back Testing a Soft Constraint Model for a Smart Exhibition Space[END_REF], we already showed how BtB testing could be successfully applied to constraint programming, since our basic ideas of testing adaptive, self-organizing system is based on constraining the SO algorithms. This paper extends these concepts from constraint programming to SO mechanisms.

Our approach for BtB testing of SO mechanism is an efficient combination of modelbased techniques using the concepts of BtB testing in order to tackle the challenges of testing SOAS. To our knowledge, there is no approach extending both of these techniques to SO mechanism.

Conclusion & Outlook

We motivated the need for systematic testing of adaptive, self-organizing systems and purposed a systematic approach for BtB testing of SO mechanisms. The concept of BtB testing supports the challenging task of engineering SO mechanisms in a co-development manner and is able to reveal different kinds of faults concerning the functional specification of the system. The evaluation showed the utility of the approach by revealing different faults within a real development endeavor. The model-based approach presented is built upon a model of the system and its intended behavior, with the latter being based on our concepts of the CCB that enables fully automated evaluation of test runs. The test cases to be executed are derived on the basis of the system model; the test case selection strategy is based on ideas of virtual commissioning and boundary interior testing. Test case generation, execution, evaluation, and logging is fully automated and proved to be able to reveal different failures, as shown in the evaluation. The integration in the S# modeling framework allows to use our BtB testing concepts within Visual Studio, enabling model refactoring and debugging, among others.

Future work includes, among other things, the enhancement of heuristics in test case generation, enhancing the fault diagnostics, and integrating the approach into our overall framework for testing SOAS. The heuristics for test case generation should allow to reach the boundaries of SO mechanisms more efficiently. A first concept might be to start with bigger initial sets of component faults, e.g., to activate the component faults for all drills of all robots except of one. This leads, in a first evaluation, to better converge towards the boundaries of SO mechanisms and should reveal failures with less testing effort. Fault diagnostic is already possible in sense that we are able to track faults back to a part of the SO mechanism as well as to a set of activated component faults and a system configuration. However, the non-deterministic behavior of the SO mechanisms is still a challenge that we are going to address in future research. At last, the approach needs to be integrated into an overall approach for testing SOAS to supply a complete framework for testing the class of self-organizing resource flow systems.

Figure 1 .

 1 Figure 1. Schematic state-based view of the corridor of correct behavior; INV is the conjunction of all constraints of the system controlled by the CEI [3].

Figure 4 .

 4 Figure 4. Our approach is divided into three parts: the first part consists of the S# test model as well as corresponding configuration descriptions (cf. Section 4). The second part is the test platform that instantiates a system configuration as the basis for the test case generation with DCCA; the component fault models represent the test cases that are evaluated (cf. Sections 4 and 6) and provide the test oracles for the observer and controller (cf. Section 5). The third part represents the actual behavior of the SO mechanism which must be mapped to the intended behavior after each execution for evaluation purposes (cf. Section 6).

  1 is representing DCCA for boundary interior testing and covers the interiors and boundaries. The right box shows an extension that is currently under development and evaluation where only the boundaries are considered by conducting DCCA with different heuristics for selecting sets of component faults. They optimize the search of the boundaries by selecting component fault sets first where more faults of the same kind are activated and subsumption relations between component faults are exploited. DCCA w/ Heuristics DCCA w/o Heuristics Depth-First Approach no component faults all component faults

Figure 5 .

 5 Figure 5. The three boxes represent different test case generation strategies. The x-axises of the graphic shows different system states for a particular SO mechanism under test that are formed by the possible different configurations and settings of the system under control. The boundaries of the SO mechanism relative to the number of component faults activated is shown by the black line. The idea of boundary interior testing for SO mechanisms is to stay inside and at the boundaries for testing. The left box represents a naïve depth-first search whereas the middle box shows the boundary interior approach with the standard DCCA and the right box it extension by heuristics.

  task =[START_REF] Cámara | Evaluation of resilience in self-adaptive systems using probabilistic model-checking[END_REF][START_REF] Eberhardinger | An approach for isolated testing of self-organization algorithms[END_REF][START_REF] Eberhardinger | Towards testing self-organizing, adaptive systems[END_REF][START_REF] Elmaraghy | Variety management in manufacturing cyber-physical production systems: Roots, expectations and r&d challenges[END_REF][START_REF] Falcone | Runtime verification of component-based systems[END_REF][START_REF] Fredericks | Towards run-time testing of dynamic adaptive systems[END_REF]; noAgents = 6; capabilities = [{1},{3},{4,5,4,2},{5,6},{},{}]; isConnected = [|true,false,false,false,true,false |false,true,false,false,true,false |false,false,true,false,false,true |false,false,false,true,true,true |true,true,false,true,true,false |false,false,true,true,false,true|]

  The pre-/postconditions contained the state of the workpiece in form of the remaining part of the task, e.g., for task [D, I, T ] the precondition contained [D, I, T ] and the postcondition [I, T ] if D had been performed. But the mapping should lead to states of the workpiece representing the part of the task which already had been done, e.g., for task [D, I, T ] the precondition should contain [] and the postcondition [D] if D had been performed (R-Distribution)

  Resources are passed along a set of Agents, each applying certain Capabilities in order to conduct a step towards the completion of the Resource's Task. The Observer/Controller-encompassing the SO mechanism-monitors the Agents and assigns their Roles such that all Resources are eventually fully processed with the correct order of Capability applications. Such a resource flow is specified by the Pre-and PostConditions of all Roles within the system, as well as the inputs and outputs of the Agents that establish their interconnections.

							required capabilities	*
				applied capabilities		*	Resource		*	1	Task	1
	2..*	Capability *		*	available capabilities	*	Agent 1 0..1 inputs	* outputs	1	Observer/Controller * current tasks 0..1
		*	*	capabilities to apply	Role 1..* * allocated roles *	0..1	1 preCondition 1 port	Condition *	1..*
		state								1 postCondition 1
	Figure 3. A UML class diagram giving a simplified overview of the metamodel for self-organizing
	resource-flow systems (according to [18]): System Configuration virtual commissioning copy	S# Instance S# Instance Component Fault Model TCG Evaluation Results	Intended Behavior Observer Oracle Controller Oracle	Mapping	Actual Behavior Observer Controller
								for this system class based on CEI is explained
	by Section 4. The case study maps to the metamodel as follows: The robots and carts
	are Agents monitored by the Observer/Controller. The carts transport workpieces, i.e.,
	Resources, between the robots, which have several switchable tools, i.e., Capabilities, such

  Listing 2. Partial S# model representing a subset of the constraints defined for the oracle.

	agent.Constraints = new List<Func<bool>>() {
	// I/O Consistency
	() => agent.AllocatedRoles.All(role => role.PreCondition.Port == null ||
	agent.Inputs.Contains(role.PreCondition.Port)),
	() => agent.AllocatedRoles.All(role => role.PostCondition.Port == null ||
	agent.Outputs.Contains(role.PostCondition.Port)),
	// Capability Consistency
	() => agent.AllocatedRoles.All(
	role => role.CapabilitiesToApply.All(capability =>
	agent.AvailableCapabilites.Contains(capability))),
	/ * ... * /
	}

Table 1 .

 1 Statistical data concerning the configuration used in the evaluation, the number of test cases generated and executed, the demanded time. Note that all detected faults have been removed and the time is used for complete testing of the interior and boundaries. Note that the runs within our framework are deterministic, i.e., there is no need to consider mean values or standard derivations.

			#capabilities #capabilities			time
	#robots #carts per Robot	per Task	#routes #test cases (in min)
	4	3	2.75	6	6	131,000	570
	3	2	1.67	5	4	49	0.2
	3	2	3.67	5	4	26,763	69.25
	3	2	1.67	5	6	157	0.78
	3	2	1.67	8	4	47	0.38
	5	2	1.6	5	5	1,577	6.88
	3	4	1.67	5	5	369	1.08

Table 2 .

 2 Statistical data comparing boundary-interior testing of SO mechanisms (DCCA w/o heuristics) with a simple depth-first search. The configuration that is compared is the first one of

	Metrics	Boundary-interior		Depth-first
		F1 F2 F3 F4 F5 F6	F1 F2 F3 F4	F5	F6
	#Test Cases 13 15	1	1 1,609 4	10 16	1	1 16,813 5
	Time (in s) 3.12 3.91 < 1 < 1 420 0.96 2.25 3.11 < 1 < 1 7583.33 1.13

Table 1 .

 1

http://www.minizinc.org/

http://www.activecomponents.org/

Acknowledgments. This research is sponsored by the research project Testing Self-Organizing, adaptive Systems (TeSOS) of the German Research Foundation. Additionally, we thank our college Alexander Schiendorfer for his support with MiniZinc.