Path Testing in Distributed Systems

Path testing is a well established technique for selecting test cases. A path is a set of logically contiguous statements that is executed when a specific input set is used, such as the following:

 S₁; if(cond1) S₂ else S₃

There are the paths S₁, S₂ and S₁, S₃. Other control structures introduce new paths and may result in an indeterminate number of paths or, worse still, an infinite number of paths.

Coverage is measured by computing the percentage of paths that have been exercised by a test case. Executing 100% of the paths in a program provides complete code coverage although it may not detect defects related to the computation environment. Of course, this is difficult to achieve when there are an infinite number of paths. Alternatives include only measuring the branches out of selection statements, or if and case statements that have been covered. This does not cover the combinations of a branch from one control structure to another.

Another definition for a path is to link the place where a variable is given a value (a def) with all those places where the variable is used (a use). Covering all def-use pairs constitutes complete path coverage. Other types of significant attributes of the code can be used to define a "path." For example, branch testing, as previously mentioned, is defining paths that are based on the decision statements in the program.

For distributed systems, Richard Carver and K. C. Tai [CaTa98] have identified a definition of a path that results in effective coverage. First, we provide a couple of definitions:

SYN-event: A SYN-event is any action that involves the synchronization of two threads. The spawning of one thread by another is one example of a SYN-event.

SYN-sequence: SYN-sequence is a sequence of SYN-events that will occur in a specified order. This is one type of path through the program code.

The idea is to design test cases that correspond to SYN-sequences. For example, when a program begins execution, a single thread is operating. When it spawns a second thread, that is a SYN-event. In the simple case, each thread carries out simple computations. Eventually, the two threads join and the program terminates. This is a single SYN-sequence since any single input data set causes both threads to execute. The basic or "main" thread does not count in the number of paths since it executes regardless of the data set.

Figure 8.1 illustrates the interactions between several objects. The BricklesView object is the main thread of the program. It creates the second thread that is devoted to the Timer. The Puck and Paddle objects are controlled on the main thread. The tick() message from the Timer object to the Puck and Paddle objects are points of synchronization and thus SYN-events. The SYN-sequences of interest run from the creation of the Timer to its destruction. In this case there are an infinite number of SYN-paths because the Timer simply keeps sending tick() messages until it is destroyed. The create, destroy, and start and stop messages are SYN-events. Analysis of these events leads to the following SYN-paths that should be executed by test cases:

create the timer, it runs until the game is over, the timer is destroyed
create the timer, it runs for a while, it is stopped, it is started, the game is over, the timer is destroyed
create the timer, it runs for a while, it is stopped, the user destroys the game, and the timer is destroyed
create the timer, it runs for a while, it is stopped, it is started, the timer is stopped and started three times, the game is over, the timer is destroyed

Figure 8.1. An activity diagram of multiple threads

graphics/08fig01.gif

Our experience and research has shown that this technique of SYN-paths identifies defects that are related mainly to synchronization defects. Use of this analysis technique does not replace the need to use conventional path testing techniques to find defects unrelated to synchronization errors.

Now that we have looked at an example, let's analyze the types of events in an object-oriented language that might qualify as SYN-events.

Creation and destruction of an object that represents a thread.
Creation and destruction of an object that encapsulates a thread.
Sending of a message from an object on one thread to an object on another thread.
One object controls another by putting it to sleep or waking it up.

The tester should trace paths from one of these events to another. Even if there are multiple paths through control statements from one SYN-event to the other, only one path needs to be covered to give SYN-path coverage. Exactly where these events occur depends partially on where the threads are located.

An object that has its own thread should receive thorough testing as a class (with all of its aggregated attributes) before being interacted with other objects. In Figure 8.2, we show selected portions of the TimerTester. In particular we include a few test cases. The Timer instance had been working in the context of the completed game for a short time when it was class tested. A problem was found that allowed the timer to start but it never stopped! The pause() method set a Boolean attribute so that no further ticks were sent out, but the thread was not halted so it continued to use system resources. This was only found when the absence of ticks was tested rather than their presence.

Figure 8.2. Selected `TimerTester` code

graphics/08fig02.gif

Objects on Threads and Threads in Objects

There are only a few basic models for threads in object-oriented programs. An object has its own personal thread or it is visited by the active thread as necessary. Usually most programs will have examples of each approach. The Timer class from the Java implementation of Brickles is an example of the object owning its own thread. All of the other objects share the "main" thread. An object that owns a thread also indicates when it can be interrupted by other threads. In either design, there must be a mechanism that prevents multiple threads from operating in the same modifier method at the same time.

In the code in Figure 8.2, the test object registers with the timer to receive the tick() message. This is possible because the TimerTester class implements the TimeObservable interface. A test case like this one can be easily constructed because the test object receives the event or message directly rather than having to create a surrogate object that receives the message and then informs the test object.

Thread Models

The "motto" of Java is "Write Once Run Anywhere." The reality is "Write Once Run Anywhere after Testing Everywhere." A particular example is the differences in behavior of Java threads among operating systems. The test suite of any Java program that creates threads should include tests on multiple operating systems chosen for its different behavior. Using a Windows version, Sun Unix and Mac OS give a cross section; however, variants of Unix and even different models of workstations with different options installed may give different results.

Running the applet version of Brickles on a Windows machine and a Sun workstation results in different behaviors, some correct and some not. The thread for the Timer does not necessarily release control of the processor to allow the display to be updated.

Design for Testability #2

After our discussion about testing threads, you should notice that Timer implements the TimeObservable interface.

Design Rule: In Java, with single inheritance, the root of every inheritance hierarchy should be an interface.

This allows the test harness, which must inherit from a tester parent class to also implement the interface. This is often useful as in the case for TimerTester, which needs to register itself with the OUT. This is the Java equivalent of the long time C++ design rule that the base class for any hierarchy should be abstract.

Design for Testability #3

It is not obvious from the code used in TimerTester, but the Timer class is very difficult to test. This is due to the following statement:

 OUT = new Timer(new BricklesView());

The parameter to the constructor, BricklesView, requires most of the classes in the application: BricklesGame, ArcadeGamePiece, StationaryObject, MovableObject, Puck, Paddle, and Brick. These classes must be in the compiler's path before it can be constructed even though the reason those classes are aggregated into BricklesView has nothing to do with the actions of the time.

Design Rule: Wherever possible define a default constructor that can be used during unit testing without requiring dependencies on a large number of other classes. The default constructor need not be public.

In some cases, creating a default constructor in the class to be tested is a good design decision. In some cases it is not. With Timer, this was not possible because the Timer implementation assumes it has a reference to a BricklesView object and aborts its main loop when that reference is null. Since this object is a parameter to the only constructor, it is a reasonable precondition that the reference is not null.