Reducing the Discard of MBT Test Cases using Distance Functions

  • Thomaz Diniz Federal University of Campina Grande
  • Everton L. G. Alves Federal University of Campina Grande
  • Anderson G. F. Silva Federal University of Campina Grande
  • Wilkerson L. Andrade Federal University of Campina Grande


Model-Based Testing (MBT) is used for generating test suites from system models. However, as software evolves, its models tend to be updated, which often leads to obsolete test cases that are discarded. Test case discard can be very costly since essential data, such as execution history, are lost. In this paper, we investigate the use of distance functions to help to reduce the discard of MBT tests. For that, we ran a series of empirical studies using artifacts from industrial systems, and we analyzed how ten distance functions can classify the impact of MBT-centred use case edits. Our results showed that distance functions are effective for identifying low impact edits that lead to test cases that can be updated with little effort. Moreover, we found the optimal configuration for each distance function. Finally, we ran a case study that showed that, by using distance functions, we could reduce the discard of test cases by 15%.

Palavras-chave: MBT, distance functions, test suite evolution, agile development


Kent Beck and Erich Gamma. 2000. Extreme programming explained: embrace change. addison-wesley professional.

Emanuela Cartaxo, Wilkerson Andrade, Francisco de Oliveira Neto, and Patrícia Machado. 2008. LTS-BT: A tool to generate and select functional test cases for embedded systems. In -. 1540--1544.

William W Cohen, Pradeep Ravikumar, Stephen E Fienberg, et al. 2003. A Comparison of String Distance Metrics for Name-Matching Tasks.. In II Web, Vol. 2003. 73--78.

Ana Emília Victor Barbosa Coutinho, Emanuela Gadelha Cartaxo, and Patrícia Duarte de Lima Machado. 2016. Analysis of distance functions for similarity-based test suite reduction in the context of model-based testing. Software Quality Journal 24, 2 (2016), 407--445.

S. R. Dalal, A. Jain, N. Karunanithi, J. M. Leaton, C. M. Lott, G. C. Patton, and B. M. Horowitz. 1999. Model-based testing in practice. In Proceedings of the 1999 International Conference on Software Engineering (IEEE Cat. No.99CB37002). 285--294.

Fred J. Damerau. 1964. A Technique for Computer Detection and Correction of Spelling Errors. Commun. ACM 7, 3 (March 1964), 171--176.

Xavier De Coster, Charles De Groote, Arnaud Destiné, Pierre Deville, Laurent Lamouline, Thibault Leruitte, and Vincent Nuttin. 1. Mahalanobis distance, Jaro-Winkler distance and nDollar in UsiGesture. (1).

Francisco G de Oliveira Neto, Richard Torkar, and Patrícia DL Machado. 2016. Full modification coverage through automatic similarity-based test case selection. Information and Software Technology 80 (2016), 124--137.

Karim O Elish and Mahmoud O Elish. 2008. Predicting defect-prone software modules using support vector machines. Journal of Systems and Software 81, 5 (2008), 649--660.

Richard W Hamming. 1950. Error detecting and error correcting codes. The Bell system technical journal 29, 2 (1950), 147--160.

Tae Sik Han, Seung-Kyu Ko, and Jaewoo Kang. 2007. Efficient subsequence matching using the longest common subsequence with a dual match index. In International Workshop on Machine Learning and Data Mining in Pattern Recognition. Springer, 585--600.

Jane Huffman Hayes, Alex Dekhtyar, and Senthil Sundaram. 2005. Text mining for software engineering: how analyst feedback impacts final results. In ACM SIGSOFT Software Engineering Notes, Vol. 30. ACM, 1--5.

Anna Huang. 2008. Similarity measures for text document clustering. In Proceedings of the sixth new zealand computer science research student conference (NZCSRSC2008), Christchurch, New Zealand, Vol. 4. 9--56.

J. Itkonen, M. V. Mantyla, and C. Lassenius. 2009. How do testers do it? An exploratory study on manual testing practices. In 2009 3rd International Symposium on Empirical Software Engineering and Measurement. 494--497.

Mika Katara and Antti Kervinen. 2006. Making model-based testing more agile: a use case driven approach. In Haifa Verification Conference. Springer, 219--234.

Grzegorz Kondrak. 2005. N-Gram Similarity and Distance.. In SPIRE (2005-10-31) (Lecture Notes in Computer Science), Mariano P. Consens and Gonzalo Navarro (Eds.), Vol. 3772. Springer, 115--126.

Joseph B Kruskal. 1983. An overview of sequence comparison: Time warps, string edits, and macromolecules. SIAM review 25, 2 (1983), 201--237.

Divya Kumar and KK Mishra. 2016. The Impacts of Test Automation on Software's Cost, Quality and Time to Market. Procedia Computer Science 79 (2016), 8--15.

Vladimir Iosifovich Levenshtein. 1966. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady 10, 8 (feb 1966), 707--710. Doklady Akademii Nauk SSSR, V163 No4 845-848 1965.

Jiaheng Lu, Chunbin Lin, Wei Wang, Chen Li, and Haiyong Wang. 2013. String similarity measures and joins with synonyms. Proceedings of the ACM SIGMOD International Conference on Management of Data, 373--384.

Andre Hasudungan Lubis, Ali Ikhwan, and Phak Len Eh Kan. 2018. Combination of levenshtein distance and rabin-karp to improve the accuracy of document equivalence level. International Journal of Engineering & Technology 7, 2.27 (2018), 17--21.

Mehdi Mirzaaghaei. 2011. Automatic test suite evolution. In Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering. ACM, 396--399.

Dalton N.Jorge, Patrícia Machado, Everton L. G. Alves, and Wilkerson Andrade. 2017. CLARET - Central Artifact for Requirements Engineering and Model-Based Testing. / In Proceedings of the 24th Tools Session / 8th Brazilian Conference on Software: Theory and Practice. Fortaleza, CE, BR, 41--48.. In -.

Dalton N. Jorge, Patrícia Machado, Everton L. G. Alves, and Wilkerson Andrade. 2018. Integrating Requirements Specification and Model-Based Testing in Agile Development. 336--346.

Nachiappan Nagappan, Brendan Murphy, and Victor Basili. 2008. The influence of organizational structure on software quality. In 2008 ACM/IEEE 30th International Conference on Software Engineering. IEEE, 521--530.

Sidney Nogueira, Emanuela Cartaxo, Dante Torres, Eduardo Aranha, and Rafael Marques. 2007. Model based test generation: An industrial experience. In 1st Brazilian Workshop on Systematic and Automated Software Testing.

Teruo Okuda, Eiichi Tanaka, and Tamotsu Kasai. 1976. A method for the correction of garbled words based on the Levenshtein metric. IEEE Trans. Comput. 100, 2 (1976), 172--178.

Leandro Sales Pinto, Saurabh Sinha, and Alessandro Orso. 2012. Understanding myths and realities of test-suite evolution. In Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering. ACM, 33.

Roger Pressman. 2005. Software Engineering: A Practitioner's Approach (6 ed.). McGraw-Hill, Inc., New York, NY, USA.

Thomas A Runkler and James C Bezdek. 2000. Automatic keyword extraction with relational clustering and Levenshtein distances. In Ninth IEEE International Conference on Fuzzy Systems. FUZZ-IEEE 2000 (Cat. No. 00CH37063), Vol. 2. IEEE, 636--640.

Todd Sedano, Paul Ralph, and Cécile Péraire. 2017. Software Development Waste. In -.

Anderson G.F. Silva, Wilkerson L. Andrade, and Everton L.G. Alves. 2018. A Study on the Impact of Model Evolution in MBT Suites. In Proceedings of the III Brazilian Symposium on Systematic and Automated Software Testing (SAST '18). ACM, New York, NY, USA, 49--56.

Thorvald Sørensen. 1948. A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on Danish commons. Biol. Skr. 5 (1948), 1--34.

Jeff Sutherland and JJ Sutherland. 2014. Scrum: the art of doing twice the work in half the time. Currency.

Jan Tretmans. 2008. Model based testing with labelled transition systems. In Formal methods and testing. Springer, 1--38.

Mark Utting and Bruno Legeard. 2007. Practical Model-Based Testing: A Tools Approach. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
Como Citar

Selecione um Formato
DINIZ, Thomaz; ALVES, Everton L. G.; SILVA, Anderson G. F.; ANDRADE, Wilkerson L.. Reducing the Discard of MBT Test Cases using Distance Functions. In: SIMPÓSIO BRASILEIRO DE ENGENHARIA DE SOFTWARE (SBES), 33. , 2019, Salvador. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 .