Test architectures for distributed testing

Testing architectures

In the context of OSI standardization, ISO and ITU developed a methodology for testing implementations of standardized communication protocols (here is an overview). This includes possible testing architectures, a language for specifying test cases (called TTCN), and the definition of information required to characterize implementation properties that must be known for apply a standardized test suite.

The most important test architetures for protocol testing are the following:

1. Local test architecture: The tester has direct access to all interfaces - upper interface and lower interface of the Implementation under Test (IUT)
2. Distributed architecture: An "upper tester" interacts at the upper interface (directly), and a separate lower tester accesses the lower interface through the underlying communication medium.
3. Remote architecture: There is only a lower tester (the upper interface is used by the next-higher system layer)

In the case of local testing, it is assume that there is a tester that interfaces at the same time the upper and lower interfaces. This is what we assumed in the previous chapter on state machine testing.

The test coordination, shown in the first two architectures, means that the upper tester (UT) and lower tester (LT) communicate with one another in order to determine in which order the inputs at the different interfaces are applied, and in which order the observed outputs appeared at the different interfaces. The determination of the order of output assumes a common real-time clock of both testers - which is often unrealistic for the distributed test architecture (but not a problem for local testing).

The remote test architecture does not test the interactions at the upper interface of the protocol implementation. This is clearly an incomplete testing approach. However, certain protocol definitions (e.g. the original specification of TCP) do not talk explicitly about the service provided by the protocol to the user - I think this is a flaw. In the remote test architecture, it is assumed that there is a "standard" user process interacting with the protocol implementation at the upper interface.

Test architecture for embedded testing (general case)

The following diagram shows a quite general situation where the IUT is accessible by the tester only through some intermediate functionality, called "context" in this diagram (this is discussed in the paper Fault models for testing in context ( A. Petrenko, N. Yevtushenko and G. v. Bochmann ), in Proc. IFIP symposium FORTE-PSTV'96, Formal Description Techniques IX, R. Gotzhein and J. Bredereke, Chapman and Hall, 1996, pp. 163-178). One assumes that the specification of the behavior of the context is known and that this context is correctly implemented. The interactions of the IUT are only visible indirectly, through the interactions of the tester with the context. The following questions arise:

• What aspects of the behavior of the IUT can be verified in this architecture ?
• What input should be applied to the context (that is, what test suite should be used ?) and under what conditions indicate the outputs of the context a fault in the IUT ?

Synchronizable test cases - definitions

In the following, we consider the distributed test method without test coordination. We follow the arguments of our paper on distributed testing (Test generation with respect to distributed interfaces ( G. Luo, R. Dssouli, G. v. Bochmann, P. Ventakaram and A. Ghedamsi ), Computer Standards and Interfaces 16 (1994), pp.119-132)

The first paper that talked about problems related to distributed testing was our paper of 1984 (Synchronization and specification issues in protocol testing ( B. Sarikaya and G. v. Bochmann ), IEEE Trans. on Comm., COM-32, No.4 (April 1984), pp. 389-395; russian translation: Express Information (overview of western publications), Information Transfer, 1985, no. 28), which included the following definitions:

Synchronizable sequence: A sequence to two transitions is synchronizable if the input for the second transition comes over an interface over which there was an input or output during the first transition.

• If a sequence is not synchronizable then the local tester that is responsible for producing the input for the second transition does not know when to produce this input (since it does not know when the first transition was executed).

Non-synchronizable transition: A transition t to a state s is non-synchronizable if for each transition t' leaving state s, the sequence t.t' is not synchronizable.

• A state machine that has a non-synchronizable transition is called intrinsically non-synchronizable, since any test sequence that checks the next state of that transition will have synchronization problems.

The above definitions have been generalized in our paper on distributed testing where an arbitrary number of interfaces is assumed and each transition may have several outputs, possibly over different interfaces. See example below.

Definition (synchronizable sequence for transitions with multiple outputs): A sequence of two transitions is synchronizable if the input for the second transition comes over an interface over which there was an input or output during the first transition.

Note: This definition reads the same as above for transitions with a single output, but the possibility of several outputs gives rise to many more possible faults. Individual outputs may not only be wrong, they may also appear at the wrong interface, or not occur at all, or there may be some additional outputs. This leads to problems of fault coverage (to be discussed below).

Deriving synchronizable test cases - fault coverage

Definition: A test case is synchronizable if all pairs of successive transitions invoked on the specification are synchronizable sequences.

When using the distributed testing architecture, one would like to use synchronizable test cases. Questions:

• How could one adapt the test derivation methods discussed in the previous chapter (for the local test architecture) in order to obtain synchronizable test cases ?
  • The proposed approaches suggest to modify the existing test derivation algorithms such that the next transition is always chosen such that the test case remains synchronizable.
    • Clearly, this is not possible if the specification is intrinsically non-synchronizable.
  • It has been shown that the algorithmic complexity of deriving a ynchronizable test suite is explonential in the size of the state machine (while the algorithms discussed in the previous chapter are polynamial).
• What kind of fault coverage guarantee can one obtain with synchronizable test suites ? - In general, there are less guarantees than for the test derivation algorithms for the local testing architecture. In particular, see the following examples:
  • A synchronized transition tour does not guarantee the detection of all output faults - in particular, so-called output shifting faults are sometimes not detected. Below is an example (on the left the specification, on the right a faulty implementation which produces the b at the first interface (port 1) later than the specification.

    

  • A heuristic to derive a a test case that checks for possible output-shifting faults was suggested in our paper on distributed testing and goes as follows: (a) Derive a synchronizable test case; (b) identify possible output-shifting faults of an implementation related to the transitions in the test case that would not be detected by the test case; (c) add an extensions to the test case to verify the absense of each of these output-shifting faults. An example is given below

  

  • Some output faults cannot be detected at all in the distributed architecture. Below is an example of a specification where the dashed transition has the output f, and where an implementation has a simple output fault for this transition: producing the output g. A test input sequence a.b.c could detect this fault if this input leads to the execution of the transition sequence t1, t2, t3. However, since the input c is applied at the interface L, while the other inputs are applied at the interface U, other transition execution orders may occur (nondeterministicallly due to the lack of coordination between the two testers at the two interfaces). For instance t4, t6, t7 or t1, t5, t7. If the latter two sequences of transitions are executed, the output fault will not be detected because the faulty transition will not be executed. - Note: With coordination between the testers at the two interfaces, this nondeterminism can be eliminated and the fault can be detected. In this example, the transition sequence t2, t3 is not synchronizable - there is actually no test sequence involving t3 that is synchronizable - therefore we have this problem of detecting the output fault in this transition.

    

  • Another way of dealing with the nondeterminism introduced by the distributed architecture is to adopt the general conformance testing approach for nondeterministic implementations. If the specification is nondeterministic, the implementation may be so as well. If for a given input sequence, there are several possible transition execution sequences (with possibly different outputs), then one wants to cover all these execution sequences in order to detect any fault that may reside in one of these sequences. Because of the nondeterministic nature of the specification, it is in general difficult to control the IUT in such a way as to constrain the execution into a specific transition sequence. A solution often proposed for this problem is to apply the test sequence many times, hoping that, by chance, all the different possible transition sequences will be exercised.

Created: November 20, 2014