Software QA FYI - SQAFYI

Efficient Methods for Interoperability Testing Using Event Sequences

By: D. Richard Kuhn,James M. Higdon,James F. Lawrence,Raghu N. Kacker,Yu Lei

Abstract. Many software testing problems involve sequences of events. The methods described in this paper were motivated by testing needs of mission critical systems that may accept multiple communication or sensor inputs and generate output to several communication links and other interfaces, where it is important to test the order in which events occur. Using combinatorial methods makes it possible to test sequences of events using significantly fewer tests than previous procedures.

For many types of software, the sequence of events is an important consideration [1, 2]. For example, graphical user interfaces may present the user with a large number of options that include both order-independent (e.g., choosing items) and orderdependent selections (such as final selection of items, quantity, and payment information). The software should work correctly, or issue an appropriate error message, regardless of the order of events selected by the user. A number of test approaches have been devised for these problems, including graph-covering, syntax-based, and finite-state machine methods [3, 4, 5]. In testing such software, the critical condition for triggering failures often is whether or not a particular event has occurred prior to a second one, not necessarily if they are back to back. This situation reflects the fact that in many cases, a particular state must be reached before a particular failure can be triggered. For example, a failure might occur when connecting device A only if device B is already connected, or only if devices B and C were both already connected. The methods described in this paper were developed to address testing problems of this nature, using combinatorial methods to provide efficient testing. Sequence covering arrays, as defined here, ensure that every t events from a set of n (n > t) will be tested in every possible tway order, possibly with interleaving events among each subset of t events.

We define a sequence covering array, SCA(N, S, t) as an N x S matrix where entries are from a finite set S of s symbols, such that every t-way permutation of symbols from S occurs in at least one row and each row is a permutation of the s symbols [6]. The t symbols in the permutation are not required to be adjacent. That is, for every t-way arrangement of symbols x1, x2, ..., xt, the regular expression .*x1.*x2.*xt.* matches at least one row in the array.

Example 1
We may have a component of a factory automation system that uses certain devices interacting with a control program. We want to test the events defined in Table 1. There are 6! = 720 possible sequences for these six events, and the system should respond correctly and safely no matter the order in which they occur. Operators may be instructed to use a particular order, but mistakes are inevitable, and should not result in injury to users or compromise the operation. Because setup, connections, and operation of this component are manual, each test can take a considerable amount of time. It is not uncommon for systemlevel tests such as this to take hours to execute, monitor, and complete. We want to test this system as thoroughly as possible, but time and budget constraints do not allow for testing all possible sequences, so we will test all 3-event sequences.

Full article...

Other Resource

... to read more articles, visit

Efficient Methods for Interoperability Testing Using Event Sequences