Test Selection on Extended Finite State Machines with Provable Guarantees


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.

Share and Cite:

B. Guo and M. Subramaniam, "Test Selection on Extended Finite State Machines with Provable Guarantees," Journal of Software Engineering and Applications, Vol. 6 No. 9, 2013, pp. 500-510. doi: 10.4236/jsea.2013.69060.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] M. J. Harrold and A. Orso, “Retesting Software during Development and Maintenance,” Frontiers of Software Maintenance, Beijing, 28 September-4 October 2008, pp. 99-109.
[2] G. Rothermel and M. J. Harrold, “Analyzing Regression Test Selection Techniques,” IEEE Transactions on Software Engineering, Vol. 22, No. 8, 1996, pp. 529-551. doi:10.1109/32.536955
[3] S. Yoo and M. Harman, “Regression Testing Minimization, Selection, and Prioritization: A Survey,” Software Testing, Verification, and Reliability, Vol. 22, No. 2, 2010, pp. 67-120. doi:10.1002/stvr.430
[4] Y. Chen, R. L. Rrobert and H. Ural, “Regression Test Suite Reduction Using Extended Dependence Analysis,” 4th Workshop on Software Quality Assurance, 2007, pp. 62-69.
[5] B. Korel, L. Tahat and B. Vaysburg, “Model Based Regression Test Reduction Using Dependence Analysis,” International Conference on Software Maintenance, 2002, pp. 214-223.
[6] D. Detlefs, G. Nelson and J. B. Saxe, “Simplify: A Theorem Prover for Program Checking,” Journal of the ACM, 52, 3, 2005, pp. 365-473. doi:10.1145/1066100.1066102
[7] D. Kapur and H. Zhang, “An Overview of Rewrite Rule Laboratory (RRL),” Conference on Rewriting Techniques and Applications, Chapel Hill, 3-5 April 1989, pp. 559-563.
[8] B. Daniel and Z. Pitro, “On Communicating Finite-State Machines,” Journal of the ACM, Vol. 30, No. 2, 1983, pp. 323-342.
[9] D. Lee and M. Yiannakakis, “Principles and Methods of Testing Finite State Machines-Survey,” IEEE Computers, Vol. 84, No. 8, 1996.
[10] M. Subramaniam and P. Chundi, “An Approach to Preserve Protocol Consistency and Executability across Updates,” Conference on Formal Engineering Methods, Seattle, 8-12 December 2004, pp. 341-356.
[11] M. Subramaniam and B. Guo, “A Rewrite-Based Approach for Change Impact Analysis of Communicating Systems Using a Theorem Prover,” Tech Report, Department of Computer Science, University of New Orleans, New Orleans, 2008.
[12] G. Rothermel and M. J. Harrold, “A Safe, Efficient Regression Test Selection Technique,” ACM Transactions on Software Engineering and Methodology, Vol. 6, No. 2, 1997, pp. 173-210.
[13] E. Bringmann and A. Kramer, “Model-Based Testing of Automotive Systems,” Conference on Software Testing, Verification and Validation (ICST’08), Lillehammer, 9-11 April 2008, pp. 485-493.
[14] Y. Chen, R. L. Probert and D. P. Sims, “Specification-Based Regression Test Selection with Risk Analysis,” Conference of the Centre for Advanced Studies on Collaborative Research, 2002.
[15] L.C. Briand, Y. Labiche and S. He, “Automating Regression Test Selection Based on UML Designs,” Information and Software Technology, Vol. 51, No. 1, 2009, pp. 16-30. doi:10.1016/j.infsof.2008.09.010
[16] L. C. Briand, Y. Labiche and G. Soccar, “Automating Impact Analysis and Regression Test Selection Based on UML Designs,” Conference on Software Maintenance, 2002, pp. 252-261.
[17] B. Korel, L. H. Tahat and M. Harman, “Test Prioritization Using System Models,” Conference on Software Maintenance, 26-29 September 2005, pp. 559-568.
[18] B. Vaysburg, L. H. Tahat and B. Korel, “Dependence Analysis in Reduction of Requirement Based Test Suites,” Symptoms on Software Testing and Analysis, Vol. 27, No. 4, 2002, pp. 107-111.
[19] H. Do, S. Elbaum and G. Rothermel, “Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and Its Potential Impact,” Empirical Software Engineering, Vol. 10, No. 4, 2005, pp. 405-435. doi:10.1007/s10664-005-3861-2
[20] S. Weibleder, “Parteg”. http://parteg.sourceforge.net/
[21] E. M. Clarke, O. Grumberg and D. A. Peled, “Model Checking,” MIT Press, Cambridge, 1999.
[22] C. Keum, S. Kang, I. Ko, J. Baik and Y. Choi, “Generating Test Cases for Web Services Using Extended Finite State Machine,” Conference on Testing of Software and Communication Systems, New York, 16-18 May 2006, pp. 103-117.
[23] M. Subramaniam, L. Xiao, B. Guo and Z. Pap, “Approach for Test Selection for EFSMs Using a Prover,” Conference on Testing of Software and Communications Systems, Eindhoven, 2-4 November 2009, pp. 146-162. doi:10.1007/978-3-642-05031-2_10
[24] H. K. N. Leung and L. White, “A Cost Model to Compare Regression Test Strategies,” Conference on Software Maintenance, Sorrento, 15-17 October 1991, pp. 201-208.
[25] J. C. King, “Symbolic Executed and Program Testing,” Communications of the ACM, Vol. 19, No. 7, 1976, pp. 358-394. doi:10.1145/360248.360252

Copyright © 2022 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.