Test-case prioritization: achievements and challenges

Abstract

Test-case prioritization, proposed at the end of last century, aims to schedule the execution order of test cases so as to improve test effectiveness. In the past years, test-case prioritization has gained much attention, and has significant achievements in five aspects: prioritization algorithms, coverage criteria, measurement, practical concerns involved, and application scenarios. In this article, we will first review the achievements of test-case prioritization from these five aspects and then give our perspectives on its challenges.

Keywords

test-case prioritization / achievements / challenges

References

[1] Wong W E, Horgan J R, London S, Agrawal H. A study of effective regression testing in practice. In: Proceedings of the 8th IEEE International Symposium on Software Reliability Engineering. 1997, 264–274

[2] Rothermel G, Untch R H, Chu C Y, Harrold M J. Test case prioritization: an empirical study. In: Proceedings of the IEEE International Conference on Software Maintenance. 1999, 179–188

[3] Rothermel G, Untch R H, Chu C Y, Harrold M J. Prioritizing test cases for regression testing. IEEE Transactions on Software Engineering, 2001, 27(10): 929–948

[4] Li Z, Harman M, Hierons R M. Search algorithms for regression test case prioritization. IEEE Transactions on Software Engineering, 2007, 33(4): 225–237

[5] Zhang L, Hou S S, Guo C, Xie T, Mei H. Time-aware test-case prioritization using integer linear programming. In: Proceedings of the 18th ACM International Symposium on Software Testing and Analysis. 2009, 213–224

[6] Zhang J, Wang X Y, Hao D, Xie B, Zhang L, Mei H. Asurvey on bugreport analysis. SCIENCE CHINA Information Sciences, 2015, 58(2): 1–24

[7] Zhang L M, Hao D, Zhang L, Rothermel G, Mei H. Bridging the gap between the total and additional test-case prioritization strategies. In: Proceedings of the 35th IEEE International Conference on Software Engineering. 2013, 192–201

[8] Hao D, Zhang L M, Zhang L, Rothermel G, Mei H. A unified test case prioritization approach. ACM Transactions on Software Engineering and Methodology, 2014, 10: 1–31

[9] Jones J A, Harrold M J. Test-suite reduction and prioritization for modified condition/decision coverage. IEEE Transactions on Software Engineering, 2003, 29(3): 195–209

[10] Zhang L M, Zhou J, Hao D, Zhang L, Mei H. Prioritizing JUnit test cases in absence of coverage information. In: Proceedings of the IEEE International Conference on Software Maintenance. 2009, 19–28

[11] Mei H, Hao D, Zhang L M, Zhang L, Zhou J, Rothermel G. A static approach to prioritizing junit test cases. IEEE Transactions on Software Engineering, 2012, 38(6): 1258–1275

[12] Korel B, Tahat L H, Harman M. Test prioritization using system models. In: Proceedings of the 21st IEEE International Conference on Software Maintenance. 2005, 559–568

[13] Korel B, Koutsogiannakis G, Tahat L H. Application of system models in regression test suite prioritization. In: Proceedings of the IEEE International Conference on Software Maintenance. 2008, 247–256

[14] Ding J H, Xu D X. Prioritizing state-based aspect tests. In: Proceedings of the 3rd IEEE International Conference on Software Testing, Verification and Validation. 2010, 265–274

[15] Elbaum S, Malishevsky A G, Rothermel G. Test case prioritization: a family of empirical studies. IEEE Transactions on Software Engineering, 2002, 28(2): 159–182

[16] Ma Z K, Zhao J J. Test case prioritization based on analysis of program structure. In: Proceedings of the 15th Asia-Pacific Software Engineering Conference. 2008, 471–478

[17] Jiang B, Chan W K. Input-based adaptive randomized test case prioritization: a local beam search approach. Journal of Systems and Software, 2015, 105: 91–106

[18] Li S H, Bian N W, Chen Z Y, You D J, He Y C. A simulation study on some search algorithms for regression test case prioritization. In: Proceedings of the 10th IEEE International Conference on Quality Software. 2010, 72–81

[19] Hao D, Zhang L, Zang L, Wang Y B, Wu X X, Xie T. To be optimal or not in test-case prioritization. IEEE Transactions on Software Engineering, 2015

[20] Elbaum S, Malishevsky A, Rothermel G. Incorporating varying test costs and fault severities into test case prioritization. In: Proceedings of the 23rd International Conference on Software Engineering. 2001, 329–338

[21] Qu X, Cohen M B, Woolf K M. Combinatorial interaction regression testing: a study of test case generation and prioritization. In: Proceedings of the IEEE International Conference on Software Maintenance. 2007, 255–264

[22] Walcott K R, Soffa M L, Kapfhammer G M, Roos R S. Time-aware test suite prioritization. In: Proceedings of the 2006 ACM International Symposium on Software Testing and Analysis. 2006, 1–12

[23] Alspaugh S, Walcott K R, Belanich M, Kapfhammer G M, Soffa M L. Efficient time-aware prioritization with knapsack solvers. In: Proceedings of the 1st ACM International Workshop on Empirical Assessment of Software Engineering Languages and Technologies. 2007, 17–31

[24] Suri B, Singhal S. Analyzing test case selection & prioritization using ACO. ACM SIGSOFT Software Engineering Notes, 2011, 36(6): 1–5

[25] Do H, Mirarab S, Tahvildari L, Rothermel G. The effects of time constraints on test case prioritization: a series of controlled experiments. IEEE Transactions on Software Engineering, 2010, 36(5): 593–617

[26] Park H, Ryu H, Baik J. Historical value-based approach for costcognizant test case prioritization to improve the effectiveness of regression testing. In: Proceedings of the 2nd IEEE International Conference on Secure System Integration and Reliability Improvement. 2008, 39–46

[27] Zhang X F, Nie C H, Xu B W, Qu B. Test case prioritization based on varying testing requirement priorities and test case costs. In: Proceedings of the 7th IEEE International Conference on Quality Software. 2007, 15–24

[28] Srivastava A, Thiagarajan J. Effectively prioritizing tests in development environment. ACM SIGSOFT Software Engineering Notes, 2002, 27(4): 97–106

[29] Hao D, Zhao X, Zhang L. Adaptive test-case prioritization guided by output inspection. In: Proceedings of the 37th IEEE Annual Computer Software and Applications Conference. 2013, 169–179

[30] Lou Y L, Hao D, Zhang L. Mutation-based test-case prioritization in software evolution. In: Proceedings of the 26th IEEE International Symposium on Software Reliability Engineering. 2015, 46–57

[31] Chen J J, Bai Y W, Hao D, Xiong Y F, Zhang H Y, Zhang L, Xie B. A text-vector based approach to test case prioritization. In: Proceedings of the IEEE International Conference on Software Testing, Verificationa and Validation. 2016, 266–277

[32] Thomas S W, Hemmati H, Hassan A E, Blostein D. Static test case prioritization using topic models. Empirical Software Engineering, 2014, 19(1): 182–212

[33] Elbaum S, Malishevsky A G, Rothermel G. Prioritizing test cases for regression testing. In: Proceedings of the 2000 ACM SIGSOFT International Symposium on Software Testing and Analysis. 2000, 102–112

[34] Wong W E, Horgan J R, London S, Agrawal H. A study of effective regression testing in practice. In: Proceedings of the 8th IEEE International Symposium on Software Reliability Engineering. 1997, 230–238

[35] Jones J A, Harrold M J. Test-suite reduction and prioritization for modified condition/decision coverage. IEEE Transactions on Software Engineering, 2003, 29(3): 195–209

[36] Fang C R, Chen Z Y, Wu K, Zhao Z H. Similarity-based test case prioritization using ordered sequences of program entities. Software Quality Journal, 2014, 22(2): 335–361

[37] Mei L, Chan W K, Tse T H. Data flow testing of service-oriented workflow applications. In: Proceedings of the 30th ACM/IEEE International Conference on Software Engineering. 2008, 371–380

[38] Voas J M. PIE: a dynamic failure-based technique. IEEE Transactions on Software Engineering, 1992, 18(8): 717–727

[39] Do H, Rothermel G. On the use of mutation faults in empirical assessments of test case prioritization techniques. IEEE Transactions on Software Engineering, 2006, 32(9): 733–752

[40] Chen T Y, Lau M E, Yu Y T. MUMCUT: a fault-based stategy for testing boolean specifications. In: Proceedings of the 6th Asia Pacific Software Engineering Conference. 1999, 606–613

[41] Chen Z Y, Chen T Y, Xu B W. A revisit of fault class hierachies in general boolean specifications. ACM Transactions on Software Engineering and Methodology (TOSEM), 2011, 20(3): 13

[42] Fang C R, Chen Z Y, Xu B W. Comparing logic coverage criteria on test case prioritization. SCIENCE CHINA Information Sciences, 2012, 55(12): 2826–2840

[43] Reeves C R. Modern Heuristic Techniques for Combinatorial Problems. Oxford: Blackwell Scientific Publications, 1993

[44] Saha R K, Zhang L M, Khurshid S, Perry D E. REPiR: an information retrieval based approach for regression test prioritization. In: Proceedings of the 37th IEEE International Conference on Software Engineering. 2015, 268–279

[45] Tonella P, Avesani P, Susi A. Using the case-based ranking methodology for test case prioritization. In: Proceedings of the 22nd IEEE International Conference on Software Maintenance. 2006, 123–133

[46] Arafeen M J, Do H. Test case prioritization using requirements based clustering. In: Proceeding of the 6th IEEE International Conference on Software Testing, Verification and Validation. 2013, 312–321

[47] Do H, Rothermel G. An empirical study of regression testing techniques incorporating context and lifetime factors and improved costbenefit models. In: Proceedings of the 14th ACM SIGSOFT International Symposium on Foundations of Software Engineering. 2006, 141–151

[48] Do H, Rothermel G. Using sensitivity analysis to create simplified economic models for regression testing. In: Proceedings of the 2008 ACM International Symposium on Software Testing and Analysis. 2008, 51–62

[49] Kim J M, Porter A. A history-based test prioritization technique for regression testing in resource constrained environments. In: Proceedings of the 24th IEEE International Conference on Software Engineering. 2002, 119–129

[50] Huang Y C, Peng K L, Huang C Y. A history-based cost-cognizant test case prioritization technique in regression testing. Journal of Systems and Software, 2012, 85(3): 626–637

[51] Hou S S, Zhang L, Xie T, Sun J. Quota-constrained test-case prioritization for regression testing of service-centric systems. In: Proceedings of the IEEE International Conference on Software Maintenance. 2008, 257–266

[52] Do H, Rothermel G, Kinneer A. Prioritizing JUnit test cases: an empirical assessment and cost-benefits analysis. Empirical Software Engineering, 2006, 11(1): 33–70

[53] Do H, Rothermel G. A controlled experiment assessing test case prioritization techniques via mutation faults. In: Proceedings of the 21st IEEE International Conference on Software Maintenance. 2005, 411–420

[54] Do H, Mirarab S, Tahvildari L, Rothermel G. An empirical study of the effect of time constraints on the cost-benefits of regression testing. In: Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of Software Engineering. 2008, 71–82

[55] Lu Y F, Lou Y L, Chen S Y, Zhang L M, Hao D, Zhou Y F, Zhang L. How does regression test prioritization perform in real-world software evolution? In: Proceedings of the 38th International Conference on Software Engineering. 2016

RIGHTS & PERMISSIONS

2016 Higher Education Press and Springer-Verlag Berlin Heidelberg