Evaluating String Distance Metrics for Reducing Automatically Generated Test Suites
Pages 171 - 181
Abstract
Regression test suites can have a large number of test cases, especially automatically generated ones, and tend to grow in size, making it costly to run the entire test suite. Test suite reduction aims to eliminate some test cases to reduce the test suite size and therefore reduce the cost of running it. In this paper, string distances on the text of the test cases are used as measures of similarity for reduction. A practical benefit of using string distance is that there is no need to run the test cases: the test suite source code is the only requirement, making the approach fast. We reduce test suites generated from Randoop and EvoSuite; two well-known test generation tools of Java programs. We implemented a string-based similarity reduction and compared it against random reduction. In the experiments, mutation scores using reduced test suites based on maximising string dissimilarity of test cases were higher than those for random reduction in over 70% of the test suites generated. Also, the results showed that test suites generated by Randoop can be drastically reduced in one case by 99% using the string-based similarity reduction approach while maintaining the fault-finding capabilities of the original test suite. Finally, on average, the normalised compression distance was found to be the best similarity metric choice in terms of fault-detection.
References
[1]
R. Beena and S. Sarala. 2014. Multi objective test case minimization collaborated with clustering and minimal hitting set. Journal of Theoretical and Applied Information Technology 69, 1 (2014), 200--210.
[2]
M. Biagiola, A. Stocco, F. Ricca, and P. Tonella. 2019. Diversity-based web test generation. In Proceedings of the Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 142--153.
[3]
P. MS Bueno, W E. Wong, and M. Jino. 2007. Improving random test sets using the diversity oriented test data generation. In Proceedings of the 2nd international workshop on Random testing: co-located with the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE 2007). 10--17.
[4]
E. G Cartaxo, P. D. L. Machado, and F. G. O. Neto. 2011. On the use of a similarity function for test case selection in the context of model-based testing. Software Testing, Verification and Reliability 21, 2 (2011), 75--100.
[5]
E. G Cartaxo, F. G. O. Neto, and P. D. L. Machado. 2007. Automated test case selection based on a similarity function. In Jahrestagung der Gesellschaft für Informatik, Informatik trifft Logistik, Vol. P-110. 399--404.
[6]
J. Chen, X. Shen, and T. Menzies. 2019. Building very small test suites (with SNAP).
[7]
J. Chen, X. Shen, and T. Menzies. 2021. Faster SAT Solving for Software with Repeated Structures (with Case Studies on Software Test Suite Minimization).
[8]
N. Chetouane, F. Wotawa, H. Felbinger, and M. Nica. 2020. On using k-means clustering for test suite reduction. In Workshop on Testing: Academia-Industry Collaboration, Practice and Research Techniques (TAIC PART). 380--385.
[9]
I. Ciupa, A. Leitner, M. Oriol, and B. Meyer. 2008. ARTOO: adaptive random testing for object-oriented software. In Proceedings of the International conference on Software engineering. 71--80.
[10]
A. V. B. Coutinho, E. G. Cartaxo, and P. D. L. Machado. 2013. Test suite reduction based on similarity of test cases. In 7st Brazilian workshop on systematic and automated software testing---CBSoft, Vol. 2013.
[11]
A. V. B. Coutinho, E. G. Cartaxo, and P. D. L. 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.
[12]
C. Coviello, S. Romano, and G. Scanniello. 2018. An empirical study of inadequate and adequate test suite reduction approaches. In Proceedings of the International symposium on empirical software engineering and measurement. 1--10.
[13]
C. Coviello, S. Romano, G. Scanniello, A. Marchetto, G. Antoniol, and A. Corazza. 2018. Clustering support for inadequate test suite reduction. In International Conference on Software Analysis, Evolution and Reengineering (SANER). 95--105.
[14]
E. Cruciani, B. Miranda, R. Verdecchia, and A. Bertolino. 2019. Scalable approaches for test suite reduction. In International Conference on Software Engineering (ICSE). 419--429.
[15]
I. T. Elgendy. 2024. Replication package. https://github.com/islamelgendy/Diversity-test-suite-reduction/tree/main. [Online; accessed 15-Janurary-2024].
[16]
I. T. Elgendy, R. M. Hierons, and P. McMinn. 2023. A Survey of the Metrics, Uses, and Subjects of Diversity-Based Techniques in Software Testing. arXiv:2311.09714
[17]
R. Feldt, S. Poulding, D. Clark, and S. Yoo. 2016. Test set diameter: Quantifying the diversity of sets of test cases. In IEEE International Conference on Software Testing, Verification and Validation (ICST). 223--233.
[18]
R. Feldt, R. Torkar, T. Gorschek, and W. Afzal. 2008. Searching for cognitively diverse tests: Towards universal test diversity metrics. In International Conference on Software Testing Verification and Validation Workshop. IEEE, 178--186.
[19]
G. Fraser and A. Arcuri. 2011. Evosuite: automatic test suite generation for object-oriented software. In Proceedings of the SIGSOFT symposium and the European conference on Foundations of software engineering. 416--419.
[20]
G. Fraser and A. Zeller. 2011. Mutation-driven generation of unit tests and oracles. IEEE Transactions on Software Engineering 38, 2 (2011), 278--292.
[21]
A. Haghighatkhah, M. Mäntylä, M. Oivo, and P. Kuvaja. 2018. Test prioritization in continuous integration environments. Journal of Systems and Software 146 (2018), 80--98.
[22]
R. W. Hamming. 1950. Error detecting and error correcting codes. The Bell system technical journal 29, 2 (1950), 147--160.
[23]
H. Hemmati, A. Arcuri, and L. Briand. 2013. Achieving scalable model-based testing through test case diversity. ACM Transactions on Software Engineering and Methodology (TOSEM) 22, 1 (2013), 1--42.
[24]
C. Henard, M. Papadakis, M. Harman, Y. Jia, and Y. Le Traon. 2016. Comparing white-box and black-box test prioritization. In International Conference on Software Engineering (ICSE). 523--534.
[25]
A. Ibias, M. Núñez, and R. M Hierons. 2021. Using mutual information to test from Finite State Machines: Test suite selection. Information and Software Technology 132 (2021), 106498.
[26]
R. Just, D. Jalali, and M. D Ernst. 2014. Defects4J: A database of existing faults to enable controlled testing studies for Java programs. In Proceedings of the International Symposium on Software Testing and Analysis. 437--440.
[27]
Y. Ledru, A. Petrenko, S. Boroday, and N. Mandran. 2012. Prioritizing test cases with string distances. Automated Software Engineering 19, 1 (2012), 65--95.
[28]
V. I. Levenshtein. 1966. Binary codes capable of correcting deletions, insertions, and reversals. 10, 8 (1966), 707--710.
[29]
M. Li, X0 Chen, X. Li, B. Ma, and P. MB Vitányi. 2004. The similarity metric. IEEE transactions on Information Theory 50, 12 (2004), 3250--3264.
[30]
M. Li and P. Vitányi. 1997. An introduction to Kolmogorov complexity and its applications. Vol. 3. Citeseer.
[31]
B. Miranda, E. Cruciani, R. Verdecchia, and A. Bertolino. 2018. FAST approaches to scalable similarity-based test case prioritization. In International Conference on Software Engineering (ICSE). 222--232.
[32]
C. Pacheco and M. D Ernst. 2007. Randoop: feedback-directed random testing for Java. In Companion to the SIGPLAN conference on Object-oriented programming systems and applications companion. 815--816.
[33]
A. Vargha and H. D. Delaney. 2000. A critique and improvement of the CL common language effect size statistics of McGraw and Wong. Journal of Educational and Behavioral Statistics 25, 2 (2000), 101--132.
[34]
Markos Viggiato, Dale Paas, Chris Buzon, and Cor-Paul Bezemer. 2023. Identifying similar test cases that are specified in natural language. Transactions on Software Engineering 49, 3 (2023), 1027--1043.
[35]
X. Wang, S. Jiang, P. Gao, X. Ju, R. Wang, and Y. Zhang. 2017. Cost-effective testing based fault localization with distance based test-suite reduction. Science China Information Sciences 60, 9 (2017), 1--15.
[36]
X. Xie, P. Yin, and S. Chen. 2022. Boosting the Revealing of Detected Violations in Deep Learning Testing: A Diversity-Guided Method. In International Conference on Automated Software Engineering. 1--13.
[37]
S. Yoo and M. Harman. 2012. Regression testing minimization, selection and prioritization: a survey. Software testing, verification and reliability 22, 2 (2012), 67--120.
Index Terms
- Evaluating String Distance Metrics for Reducing Automatically Generated Test Suites
Recommendations
Efficient Reduction of Model-Based Generated Test Suites through Test Case Pair Prioritization
MODEVVA '10: Proceedings of the 2010 Workshop on Model-Driven Engineering, Verification, and ValidationDuring the development and maintenance of software, test suites often reach a size that exceeds the costs allocated for test suite execution. In such a case, the test suite needs to be reduced. Many papers are dedicated to the problem of test suite ...
Empirically evaluating Greedy-based test suite reduction methods at different levels of test suite complexity
Test suite reduction is an important approach that decreases the cost of regression testing. A test suite reduction technique operates based on the relationship between the test cases in the regression test suite and the test requirements in the program ...
Achieving Effective Test Suites for Reactive Systems using Specification Mining and Test Suite Reduction Techniques
Failures in reactive embedded systems are often unacceptable. Moreover, effective testing of such systems to detect potential critical failures is a difficult task.
We present an automated black box test suite generation technique for reactive systems. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2024
235 pages
ISBN:9798400705885
DOI:10.1145/3644032
- Chair:
- Francesca Lonetti,
- Proceedings Chair:
- Antonio Guerriero,
- Program Chair:
- Mehrdad Saadatmand,
- Program Co-chairs:
- Christof J. Budnik,
- Jenny Li
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 10 June 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
AST '24
Sponsor:
AST '24: 5th ACM/IEEE International Conference on Automation of Software Test (AST 2024)
April 15 - 16, 2024
Lisbon, Portugal
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 50Total Downloads
- Downloads (Last 12 months)50
- Downloads (Last 6 weeks)6
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in