Setting up a scenario for testing protocols

But there are more efficient ways to tackle the problem. For example, automatically translating the graphical scenarios into commands for the software presents a seamless path from the user to the developer. This improves productivity during debugging. Analysis software can then be used to translate the debug log messages into the corresponding MSCs, thus providing visibility for any problems with the implementation.

Our approach consists of two major steps. In the first, we represent a test case as an MSC and then translate the test case's commands, mentioned graphically as messages in the MSC, into the detailed commands of the NS simulator, a discrete event simulator aimed at networking research. Thus, typically hundreds of lines of network simulatorcommands are generated from a two-page MSC without the test case writer's having to know the details of these commands.

In the second step, after running NS simulation, we automatically analyze the simulation output trace to find correspondences with the message sequence of the MSC to determine the messages in the MSC that have actually been observed during the simulation. If any of the output messages do not have a correspondence in the simulation output trace, those messages are annotated in the MSC and the tester/debugger can take appropriate action. Thus, the tester is freed of the burden of scanning through the huge trace files to determine whether the test case has run correctly or not. An additional advantage of this technique is the validation of regression test cases for real-time systems. Here, usually the time of run and the time between events change from one execution to another because of the randomness of the event scheduling, so the validation of a run is not the simple comparison of "gold result" files but an elaborate verification of the sequence of events. The sequence of events to be checked for is also dependent on the test case; among the mass of log messages, only a few are relevant. By mapping the output log messages to the MSC of the test case, our technique verifies the sequence of events and thus validates the regression test cases.

The protocol expert first defines the usage scenarios in the syntax of MSCs. This is a very domain knowledge-intensive task, and requires a complete understanding of the protocol and its domain. These diagrams contain both the test pattern that focuses on the specific feature being tested as well as the expected response from the system. A graphical user interface (GUI) captures these diagrams, infers associations between objects (for example, a horizontal arrow intersecting with two vertical lines indicates that the former is a message flowing between the latter two time axes), and stores them in a textual format. This format represents the geometrical objects (locations of each item) as well as the communication objects (messages, time axes, constraints and so on) and their associations. The GUI is built with the Tcl/Tk toolset and provides a canvas where the MSC picture is drawn

The MSC has two types of messages: those that are sent from the external world — the testbench — and those that are generated internally from the objects of the design under test. The NS translator translates the former class of messages into NS commands, and this script file is fed into NS for simulation.

The output of NS is a log of data and messages generated during simulation. This log consists of two parts: an internal representation that is used by (Network Animator) NAM for the animation of the protocol, and a user-defined part (explicitly encoded within the protocol model) that is a trace of the message events that were generated during simulation.

The test suite of a protocol consists of a set of test cases, possibly grouped together under a hierarchy of directories based on the common features being tested. Each test case consists of two parts: the network attributes and the MSCs. The correspondence between the nodes of the text file and the objects of the MSC are by the names of the nodes.

The network attributes file consists of the following pieces of information: (1) For each node: name, whether it is a master or slave, inquiry scan offset and number of responses, and (2) for each link: name, the nodes connected by it, the application running on it and length of link.

Each MSC consists of several network objects or processes. These processes have time axes associated with them. Arrows between two vertical lines represent the passing of a message from the source process to the destination process. Rectangles crossing over the time axes indicate other MSCs.

MSCs depict the sequence of messages. For our purpose we also had to specify the state changes and activities being performed. These state changes and actions are depicted by their post conditions, in the syntax of MSC conditions.

The translation to the simulator script is one of the two major steps of our framework. The network attributes and the MSCs are interpreted by the translator and converted to the corresponding NS script. The NS scripts are written in the Tcl syntax. The commands of the script can be grouped into two categories: setup commands and event commands. The setup commands are used to initialize the simulator and to describe the network under consideration; the event commands correspond to the external messages of the MSC and form the last part of the Tcl scripts generated by the translator. All the external messages specified in the MSC are interpreted as event commands by the translator. The user must thus ensure that the support for any new command has been provided in the simulator model before specifying it in the MSC as a message.

Trace analysis is used to map the log messages from the output log file onto the messages of the test case's MSC, thereby showing up any unintended differences. The analysis consists of filtering out irrelevant messages and validating the sequence. A simulation trace is expected to place in sequential order the partial order shown in the MSC. Hence, the log sequence has to be verified to be one of the many possible sequential orders of the MSC.

For this purpose, we first represent the messages of the MSC as a message flow graph (MFG). The nodes of the MFG are the start and end events of the messages of the MSC. In our application, we are not so much interested in these events as in the messages themselves. Hence, we reduce the MFG by merging the start and end event nodes for each message. In this reduced MFG the number of nodes is exactly half that of an MFG, and the only edges are that of the "next message" formed by the union of the "next event" edges of the merged nodes.

The algorithm to check whether a message sequence corresponds to the partial order in an MSC is similar to the algorithm used to place a partial order in sequence, except that the selection of the next node in the partial order is not done randomly (or LIFO or FIFO), but is done based on whether it is the next node in the trace. Hence, the complexity of sequence-matching algorithm is linear in the number of messages.

Timers and timing attributes can be used by an MSC to define timing constraints. These constraints can specify the maximum or minimum period between two events, or they can specify the exact time at which a message should be received or sent. Timers can be set and their timeouts can be used to initiate specific events.

These constraints are expected to be satisfied by the execution trace, so the trace has to be validated for such timing features too. After the sequence of messages is validated, the validation of the timing constraints is a fairly easy task: Each message in the trace has a time stamp on it, and now a check is made to see whether the constraints of the MSC are satisfied.

The overall method is a technique for using MSCs for testing protocol implementations. Although MSCs are frequently used to specify use scenarios for protocols, the lack of software support prevent them from being directly used as test cases for the protocol's implementation. Our technique for automatically translating the MSCs into the test case's code allows the reuse of the "scenario" MSCs as test cases. The method also features technique for analyzing the output trace file and back-annotation of the output messages into the original test case, thus providing a correspondence between what should have happened and what has actually happened.

This article is based on excerpts taken from ESC class # 520, Scenario testing of protocols.