TITLE:
Test Selection on Extended Finite State Machines with Provable Guarantees
AUTHORS:
Bo Guo, Mahadevan Subramaniam
KEYWORDS:
Formal Methods; Model-Based Software Testing; Regression Testing; Extended Finite State Machines
JOURNAL NAME:
Journal of Software Engineering and Applications,
Vol.6 No.9,
September
20,
2013
ABSTRACT:
Building
high confidence regression test suites to validate new system versions is a
challenging problem. A modelbased approach to build a regression test suite
from a given test suite is described. The generated test suite includes every
test that will traverse a change performed to produce the new version, and
consists of only such tests to reduce the testing costs. Finite state machines
extended with typed variables (EFSMs) are used to model systems and system
changes are mapped to EFSM transition changes adding/deleting/replacing EFSM
transitions and states. Tests are a sequence of input and expected output
messages with concrete parameter values over the supported data types. An invariant
is formulated to characterize tests whose runtime behavior can be accurately
predicted by analyzing their descriptions along with the model. Incremental
procedures to efficiently evaluate the invariant and to select tests for regression
are developed. Overlaps among the test descriptions are exploited to extend the
approach to simultaneously select multiple tests to reduce the test selection
costs. Effectiveness of the approach is demonstrated by applying it to several
protocols, Web services, and model programs extracted from a popular testing
benchmark. Our experimental results show that the proposed approach is
economical for regression test selection in all these examples. For all these
examples, the proposed approach is able to identify all tests exercising
changes more efficiently than brute-force symbolic evaluation.