Efficient increasing of the mutation score during model-based test suite generation

A. Kolchin, S. Potiyenko, T. Weigert


The purpose of the method is to increase the sensitivity of an automatically generated test suite to mutations of a model. Unlike existing methods for generating test scenarios that use the mutational approach to assess the resulting test set, the proposed method analyzes the possibility of detecting mutations on the fly, in the process of analyzing the model’s behavior space, by adding of special coverage goals. Two types of mutants manifestation are considered: deviations in the behavior of paths for (weak case) and in the observed output (strong case). A new algorithm is proposed for efficient search of a path with observable effect of a mutation.

Problems in programming 2020; 2-3: 331-340


testing; model checking; mutation testing

Full Text:



Dssouli R., et al. Testing the control-flow, data-flow, and time aspects of communication systems: a survey. Adv. Comput. 2017. 107.

Р. 95–155.

Inozemtseva L., Holmes R. Coverage is not strongly correlated with test suite effectiveness. In: Proceedings of ACM ICSE. P. 435–445 (2015). http://doi.org/10.1145/2568225.2568271

Chekam T., et. al. An empirical study on mutation, statement and branch coverage fault revelation that avoids unreliable

clean program assumption. In: IEEE-ACM 39th International Conference on Software Engineering, 12 p. (2017).


Gay G., Staats M., Whalen M., Heimdahl M. The risks of coverage-directed test case generation. IEEE Trans. Softw. Eng. 41. P. 803–819. (2015).

Heimdahl M., Devaraj G. Specification test coverage adequacy criteria = specification test generation inadequacy criteria? In: IEEE Computer Society, HASE. P. 178–186. (2004).

Morell L.J. A theory of fault-based testing. IEEE Trans. Softw. Eng. 16(8). P. 844–857. (1990). https://doi.org/10.1109/32.57623

Jia Y., Harman M. An Analysis and Survey of the Development of Mutation Testing. IEEE Trans. Softw. Eng. 37(5). P. 1–31. (2010).

Papadakis M. at al. Mutation Testing Advances: An Analysis and Survey. (2019) Advances in Computers, Vol. 112. Elsevier. P. 275 – 378. https://doi.org/10.1016/bs.adcom.2018.03.015

Volkov V., et al. A survey of systematic methods for code-based test data generation. Artif. Intell. 2. P. 71–85 (2017) .

Fraser G., Arcuri A. 1600 faults in 100 projects: automatically finding faults while achieving high coverage with Evosuite. Empir. Softw. Eng. 20(3). P. 611–639. (2015).

Choi Y.M., Lim D.J. Model‐Based Test Suite Generation Using Mutation Analysis for Fault Localization (2019). Appl. Sci. 9(17). P. 34–92. https://doi.org/10.3390/app9173492

Chekam T. at al. Killing Stubborn Mutants with Symbolic Execution. arXiv:2001.02941. 20 p. (2020).

Hessel A., Petterson P. A global algorithm for model-based test suite generation. Electr. Notes Theor. Comp. Sci. (2007). Vol. 190. P. 47–59.

Weigert T. at al. Generating Test Suites to Validate Legacy Systems. Lecture Notes in Computer Science (2019). Vol. 11753. P. 3–23. https:/doi.org/10.1007/978-3-030-30690-8_1

Kolchin A. A novel algorithm for attacking path explosion in model-based test generation for data flow coverage. Proc. of IEEE 1st Int. Conf. on System Analysis and Intelligent Computing, SAIC. (2018). P. 226–231. https://doi.org/10.1109/SAIC.2018.8516824

DeMillo Richard A. and A. Jefferson Offutt. 1991. Constraint-Based Automatic Test Data Generation. IEEE Trans. Software Eng. 17, 9 (1991). P. 900–910. https://doi.org/10.1109/32.92910

Boonstoppel P., Cadar C., Engler D. RWset: attacking path explosion in constraint-based test generation. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS. Vol. 4963. P. 351–366. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78800-3 27

Beyer D., Dangl M. SMT-based Software Model Checking: An Experimental Comparison of Four Algorithms. VSTTE 2016: Verified Software. Theories, Tools, and Experiments. (2016). P. 181–198.

DeMillo R.A., Lipton R.J., and Sayward F.G. Hints on Test Data Selection: Help for the Practicing Programmer. Computer. Vol. 11, N 4.

P. 34–41. (1978).

Meng Y., Gay G., Whalen M. Ensuring the Observability of Structural Test Obligations. IEEE Transactions on Software Engineering (Early Access). (2019). https://doi.org/10.1109/tse.2018.2869146

Li N., Offut J. An experimental comparison of four unit test criteria: mutation, edge-pair, all-uses and prime path coverage. In: IEEE International Conference on Software Testing, Verification and Validation. P. 220–229. (2009). http://doi.org/10.1109/ICSTW.2009.30

Budd T.A. Mutation Analysis of Program Test Data. PhD Thesis, Yale University, New Haven, Connecticut, 1980.

Hong H., Ural H. Dependence testing: extending data flow testing with control dependence. LNCS. Vol. 3502. (2005). P. 23–39. doi>10.1007/11430230_3

Ntafos S. On required element testing. IEEE Trans. Software Eng. Vol. 10, N 6. P. 795–803. (1984).

Letichevsky A.A. Algebraic Interaction Theory and Cyber-Physical Systems. Journal of Automation and Information Sciences. Vol. 49.

P. 1–19. (2017). https://doi.org/10.1615/JAutomatInfScien.v49.i9.10

Tallam S., Gupta N. A concept analysis inspired greedy algorithm for test suite minimization. ACM Softw. Eng. Notes 31(1). P. 35–42. (2006). https://doi.org/10.1145/1108768.1108802

Namin A., Andrews J. The influence of size and coverage on test suite effectiveness. In Proc. of Int. Symp. on Softw. Testing. P. 57–68. (2009). http://doi.org/10.1145/1572272.1572280

Kolchin A., Potiyenko Weigert. Challenges for automated, model-based test scenario generation. Communications in Computer and Information Science. (2019). Vol. 1078. P. 182–194.

Guba A., et al. A method for business logic extraction from legacy COBOL code of industrial systems. In: Proceedings of the 10th International Conference on Programming UkrPROG2016, CEUR-WS. Vol. 1631. P. 17–25. (2016).


  • There are currently no refbacks.