QTEP: quality-aware test case prioritization

ABSTRACT

Test case prioritization (TCP) is a practical activity in software testing for exposing faults earlier. Researchers have proposed many TCP techniques to reorder test cases. Among them, coverage-based TCPs have been widely investigated. Specifically, coverage-based TCP approaches leverage coverage information between source code and test cases, i.e., static code coverage and dynamic code coverage, to schedule test cases. Existing coverage-based TCP techniques mainly focus on maximizing coverage while often do not consider the likely distribution of faults in source code. However, software faults are not often equally distributed in source code, e.g., around 80% faults are located in about 20% source code. Intuitively, test cases that cover the faulty source code should have higher priorities, since they are more likely to find faults.

In this paper, we present a quality-aware test case prioritization technique, QTEP, to address the limitation of existing coverage-based TCP algorithms. In QTEP, we leverage code inspection techniques, i.e., a typical statistic defect prediction model and a typical static bug finder, to detect fault-prone source code and then adapt existing coverage-based TCP algorithms by considering the weighted source code in terms of fault-proneness. Our evaluation with 16 variant QTEP techniques on 33 different versions of 7 open source Java projects shows that QTEP could improve existing coverage-based TCP techniques for both regression and new test cases. Specifically, the improvement of the best variant of QTEP for regression test cases could be up to 15.0% and on average 7.6%, and for all test cases (both regression and new test cases), the improvement could be up to 10.0% and on average 5.0%.

References

1. 2017. Major. (2017). http://mutation-testing.org/ 2017. QTEP. (2017). http://asset.uwaterloo.ca/qtep/ 2017. Understand. (2017). https://scitools.com 2017. WALA. (2017). https://github.com/wala/WALA
2. James H Andrews, Lionel C Briand, and Yvan Labiche. Is mutation an appropriate tool for testing experiments?. In ICSE’05. 402–411.
3. James H Andrews, Lionel C Briand, Yvan Labiche, and Akbar Siami Namin. 2006. Using mutation analysis for assessing and comparing testing coverage criteria. TSE’06 (2006), 608–624.
4. Md Junaid Arafeen and Hyunsook Do. Test case prioritization using requirements-based clustering. In ICST’13. 312–321.
5. Andrea Arcuri and Lionel Briand. A practical guide for using statistical tests to assess randomized algorithms in software engineering. In ICSE’11. 1–10.
6. Nathaniel Ayewah, David Hovemeyer, J David Morgenthaler, John Penix, and William Pugh. 2008. Using static analysis to find bugs. Software, IEEE 25, 5 (2008), 22–29.
7. Thomas Ball. 1998. On the limit of control flow analysis for regression test selection. ACM SIGSOFT Software Engineering Notes 23, 2 (1998), 134–142.
8. Jennifer Black, Emanuel Melachrinoudis, and David Kaeli. Bi-criteria models for all-uses test suite reduction. In ICSE’04. 106–115.
9. Benjamin Busjaeger and Tao Xie. Learning for test prioritization: an industrial case study. In FSE’16. 975–980.
10. Ryan Carlson, Hyunsook Do, and Anne Denton. A clustering approach to improving test case prioritization: An industrial case study. In ICSM’11. 382–391.
11. Kaner Cem. Improving the Maintainability of Automated Test Suites. In QW’97.
12. Ray-Yaung Chang, Andy Podgurski, and Jiong Yang. Finding what’s not there: a new approach to revealing neglected conditions in software. In ISSTA’07. 163– 173.
13. Junjie Chen, Yanwei Bai, Dan Hao, Yingfei Xiong, Hongyu Zhang, and Bing Xie. Learning to prioritize test programs for compiler testing. In ICSE’17. 700–711.
14. Junjie Chen, Yanwei Bai, Dan Hao, Yingfei Xiong, Hongyu Zhang, Lu Zhang, and Bing Xie. Test case prioritization for compilers: A text-vector based approach. In ICST’16. 266–277.
15. Shyam R Chidamber and Chris F Kemerer. 1994. A Metrics Suite for Object Oriented Design. TSE’94 20, 6 (1994), 476–493.
16. Hyunsook Do and Gregg Rothermel. A controlled experiment assessing test case prioritization techniques via mutation faults. In ICSM’05. 411–420.
17. Hyunsook Do, Gregg Rothermel, and Alex Kinneer. Empirical studies of test case prioritization in a JUnit testing environment. In ISSRE’04. 113–124.
18. Fernando Brito e Abreu and Rogério Carapuça. 1994. Candidate metrics for object-oriented software within a taxonomy framework. JSS’94 26, 1 (1994), 87–96.
19. Sebastian Elbaum, Alexey Malishevsky, and Gregg Rothermel. Incorporating varying test costs and fault severities into test case prioritization. In ICSE’01. 329–338.
20. Sebastian Elbaum, Gregg Rothermel, and John Penix. Techniques for improving regression testing in continuous integration development environments. In FSE’14. 235–245.
21. Dawson Engler and Ken Ashcraft. 2003. RacerX: effective, static detection of race conditions and deadlocks. In ACM SIGOPS Operating Systems Review. 237–252.
22. Dawson Engler, David Yu Chen, Seth Hallem, Andy Chou, and Benjamin Chelf. Bugs as deviant behavior: A general approach to inferring errors in systems code. 57–72 pages.
23. Emelie Engstrom, Per Runeson, and Greger Wikstrand. An empirical evaluation of regression testing based on fix-cache recommendations. In ICST’10. 75–78.
24. Milos Gligoric, Lamyaa Eloussi, and Darko Marinov. Practical regression test selection with dynamic file dependencies. In ISSTA’15. 211–222.
25. Maurice H Halstead. 1977. Elements of Software Science (Operating and programming systems series). Elsevier Science Inc.
26. Rachel Harrison, Steve J Counsell, and Reuben V Nithi. 1998. An evaluation of the MOOD set of object-oriented software metrics. TSE’98 24, 6 (1998), 491–496.
27. Ahmed E Hassan. Predicting faults using the complexity of code changes. In ICSE’09. 78–88.
28. Christopher Henard, Mike Papadakis, Mark Harman, Yue Jia, and Yves Le Traon. Comparing white-box and black-box test prioritization. In ICSE’16. 523–534.
29. Charitha Hettiarachchi, Hyunsook Do, and Byoungju Choi. Effective regression testing using requirements and risks. In SERE’14. 157–166.
30. David Hovemeyer and William Pugh. 2004. Finding bugs is easy. ACM Sigplan Notices 39, 12 (2004), 92–106.
31. Vilas Jagannath, Qingzhou Luo, and Darko Marinov. Change-aware preemption prioritization. In ISSTA’11. 133–143.
32. Bo Jiang and WK Chan. Bypassing code coverage approximation limitations via effective input-based randomized test case prioritization. In COMPSAC’13. 190–199.
33. Bo Jiang, Zhenyu Zhang, Wing Kwong Chan, and TH Tse. Adaptive random test case prioritization. In ASE’09. 233–244.
34. Tian Jiang, Lin Tan, and Sunghun Kim. Personalized defect prediction. In ASE’13. 279–289.
35. Nenad Jovanovic, Christopher Kruegel, and Engin Kirda. Pixy: A static analysis tool for detecting web application vulnerabilities. In S&P’06. 6.
36. René Just, Darioush Jalali, Laura Inozemtseva, Michael D Ernst, Reid Holmes, and Gordon Fraser. Are mutants a valid substitute for real faults in software testing?. In FSE’14. 654–665.
37. Mijung Kim, Jaechang Nam, Jaehyuk Yeon, Soonhwang Choi, and Sunghun Kim. REMI: defect prediction for efficient API testing. In FSE’15. 990–993.
38. Sunghun Kim, Thomas Zimmermann, E James Whitehead Jr, and Andreas Zeller. Predicting faults from cached history. In ICSE’07. 489–498.
39. Mohsen Laali, Huai Liu, Margaret Hamilton, Maria Spichkova, and Heinz W Schmidt. 2016. Test Case Prioritization Using Online Fault Detection Information. In 21th Ada-Europe International Conference on Reliable Software Technologies. 78–93.
40. Zheng Li, Mark Harman, and Robert M Hierons. 2007. Search algorithms for regression test case prioritization. TSE’07 33, 4 (2007), 225–237.
41. Zhenmin Li and Yuanyuan Zhou. PR-Miner: Automatically Extracting Implicit Programming Rules and Detecting Violations in Large Software Code. In FSE’05. 306–315.
42. Myron Lipow. 1982. Number of faults per line of code. TSE’82 4 (1982), 437–439.
43. Yafeng Lu, Yiling Lou, Shiyang Cheng, Lingming Zhang, Dan Hao, Yangfan Zhou, and Lu Zhang. How does regression test prioritization perform in real-world software evolution?. In ICSE’16. 535–546.
44. Qi Luo, Kevin Moran, and Denys Poshyvanyk. A large-scale empirical comparison of static and dynamic test case prioritization techniques. In FSE’16. 559–570.
45. Thomas J McCabe. 1976. A complexity measure. TSE’76 4 (1976), 308–320.
46. Hong Mei, Dan Hao, Lingming Zhang, Lu Zhang, Ji Zhou, and Gregg Rothermel. 2012. A static approach to prioritizing junit test cases. TSE’12 38, 6 (2012), 1258–1275.
47. Tim Menzies, Zach Milton, Burak Turhan, Bojan Cukic, Yue Jiang, and Ayşe Bener. 2010. Defect prediction from static code features: current results, limitations, new approaches. Automated Software Engineering 17, 4 (2010), 375–407.
48. Breno Miranda and Antonia Bertolino. Does code coverage provide a good stopping rule for operational profile based testing?. In AST’16. 22–28.
49. Breno Miranda and Antonia Bertolino. 2016. Scope-aided test prioritization, selection and minimization for software reuse. JSS’16 (2016), 1–22.
50. S Mirarab and L Tahvildari. 2007. A Prioritization Approach for Software Test Cases on Bayesian Networks. FASE’07 (2007), 4422–0276.
51. Glenford J Myers, Corey Sandler, and Tom Badgett. 2011. The art of software testing.
52. Nachiappan Nagappan, Thomas Ball, and Andreas Zeller. Mining metrics to predict component failures. In ICSE’06. 452–461.
53. Jaechang Nam and Sunghun Kim. CLAMI: Defect Prediction on Unlabeled Datasets. In ASE’15. 452–463.
54. Tung Thanh Nguyen, Hoan Anh Nguyen, Nam H Pham, Jafar M Al-Kofahi, and Tien N Nguyen. Graph-based mining of multiple object usage patterns. In FSE’09. 383–392.
55. Tanzeem Bin Noor and Hadi Hemmati. A similarity-based approach for test case prioritization using historical failure data. In ISSRE’15. 58–68.
56. Thomas J Ostrand and Elaine J Weyuker. The distribution of faults in a large industrial software system. In FSE’07. 55–64.
57. Thomas J Ostrand, Elaine J Weyuker, and Robert M Bell. 2005. Predicting the location and number of faults in large software systems. TSE’05 31, 4 (2005), 340–355.
58. Foyzur Rahman, Sameer Khatri, Earl T Barr, and Premkumar Devanbu. Comparing static bug finders and statistical prediction. In ICSE’14. 424–434.
59. Gregg Rothermel and Mary Jean Harrold. 1997. A safe, efficient regression test selection technique. TOSEM 6, 2 (1997), 173–210.
60. Gregg Rothermel, Roland H Untch, Chengyun Chu, and Mary Jean Harrold. 1999. Test case prioritization: An empirical study. In ICSM’99. 179–188.
61. Gregg Rothermel, Roland H Untch, Chengyun Chu, and Mary Jean Harrold. 2011. Prioritizing test cases for regression testing. TSE’11 27, 10 (2011), 929–948.
62. Ripon K Saha, Lingming Zhang, Sarfraz Khurshid, and Dewayne E Perry. An information retrieval approach for regression test prioritization based on program changes. In ICSE’15. 268–279.
63. August Shi, Alex Gyori, Milos Gligoric, Andrey Zaytsev, and Darko Marinov. Balancing trade-offs in test-suite reduction. In FSE’14. 246–256.
64. August Shi, Tifany Yung, Alex Gyori, and Darko Marinov. Comparing and combining test-suite reduction and regression test selection. In FSE’15. 237–247.
65. Md Saeed Siddik and Kazi Sakib. RDCC: An effective test case prioritization framework using software requirements, design and source code collaboration. In ICCIT’14. 75–80.
66. Amitabh Srivastava and Jay Thiagarajan. 2002. Effectively prioritizing tests in development environment. In ACM SIGSOFT Software Engineering Notes. 97–106. ESEC/FSE’17, September 4–8, 2017, Paderborn, Germany Song Wang, Jaechang Nam, Lin Tan
67. Lin Tan, Ding Yuan, Gopal Krishna, and Yuanyuan Zhou. /* iComment: Bugs or bad comments?*. In SOSP’07. 145–158.
68. Ming Tan, Lin Tan, Sashank Dara, and Caleb Mayeux. Online defect prediction for imbalanced data. In ICSE’15. 99–108.
69. Xinye Tang, Song Wang, and Ke Mao. Will This Bug-Fixing Change Break Regression Testing?. In ESEM’15. 1–10.
70. Stephen W Thomas, Hadi Hemmati, Ahmed E Hassan, and Dorothea Blostein. 2014. Static test case prioritization using topic models. EMSE’14 19, 1 (2014), 182–212.
71. Paolo Tonella, Paolo Avesani, and Angelo Susi. Using the case-based ranking methodology for test case prioritization. In ICSM’06. 123–133.
72. Sujata Varun Kumar and Mohit Kumar. 2010. Test Case Prioritization Using Fault Severity. IJCST’10 1, 1 (2010).
73. Song Wang, Devin Chollak, Dana Movshovitz-Attias, and Lin Tan. Bugram: Bug detection with n-gram language models. In ASE’16. 708–719.
74. Song Wang, Taiyue Liu, and Lin Tan. Automatically learning semantic features for defect prediction. In ICSE’16. 297–308.
75. Andrzej Wasylkowski, Andreas Zeller, and Christian Lindig. Detecting object usage anomalies. In FSE’07. 35–44.
76. Elaine J Weyuker, Thomas J Ostrand, and Robert M Bell. Using developer information as a factor for fault prediction. In PROMISE’07. 8.
77. Thomas H Wonnacott and Ronald J Wonnacott. 1972. Introductory statistics. Vol. 19690.
78. Shin Yoo and Mark Harman. 2012. Regression testing minimization, selection and prioritization: a survey. STVR’12 22, 2 (2012), 67–120.
79. Shin Yoo, Mark Harman, and David Clark. 2013. Fault localization prioritization: Comparing information-theoretic and coverage-based approaches. TOSEM’13 22, 3 (2013), 19.
80. Shin Yoo, Robert Nilsson, and Mark Harman. Faster fault finding at Google using multi objective regression test optimisation. In FSE’11.
81. Yuen Tak Yu and Man Fai Lau. 2012. Fault-based test suite prioritization for specification-based testing. IST’12 54, 2 (2012), 179–202.
82. Feng Zhang, Audris Mockus, Iman Keivanloo, and Ying Zou. Towards building a universal defect prediction model. In MSR’14. 182–191.
83. Feng Zhang, Quan Zheng, Ying Zou, and Ahmed E Hassan. Cross-project defect prediction using a connectivity-based unsupervised classifier. In ICSE’16. 309– 320.
84. Lingming Zhang, Dan Hao, Lu Zhang, Gregg Rothermel, and Hong Mei. Bridging the gap between the total and additional test-case prioritization strategies. In ICSE’13. 192–201.
85. Lingming Zhang, Miryung Kim, and Sarfraz Khurshid. FaultTracer: a change impact and regression fault analysis tool for evolving Java programs. In FSE’12. 40.
86. Lingming Zhang, Darko Marinov, Lu Zhang, and Sarfraz Khurshid. An empirical study of junit test-suite reduction. In ISSRE’11. 170–179.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

  • Software organization and properties

    • Software functional properties

      • Formal methods

        • Automated static analysis