Variable strength combinatorial testing of concurrent programs

Abstract

Reachability testing is an important approach to testing concurrent programs. It generates and exercises synchronization sequences automatically and on-the-fly without saving any test history. Existing reachability testing can be classified into exhaustive and t-way testing. Exhaustive testing is impractical in many cases while t-way testing may decrease the capability of fault detection in some cases. In this paper, we present a variable strength reachability testing strategy, which adopts the dynamic framework of reachability testing and uses a variable strength combinatorial strategy. Different parameter groups are provided with different covering strength. Variable strength testing covers no t-way combinations but the necessary combinations of parameters having mutual interactions in a concurrent program. It is more reasonable than t-way testing because uniform interactions between parameters do not often exist in concurrent systems. We propose a merging algorithmthat implements the variable strength combinatorial testing strategy and conduct our experiment on several concurrent programs. The experimental results indicate that our variable strength reachability testing reaches a good tradeoff between the effectiveness and efficiency. It can keep the same capability of fault detection as exhaustive reachability testing while substantially reducing the number of synchronization sequences and decreasing the execution time in most cases.

Keywords

software testing / variable strength combinato-rial testing / concurrency testing / reachability testing

References

[1] Burns A, Wellings A. Real–Time systems and programming languages. Addison Wesley Longman, 2001.

[2] Edelstein O, Farchi E, Nir Y, Ratsaby G, Ur S. Multithreaded Java program test generation. Journal of IBM Systems, 2002, 41(1): 111–125

[3] Yang C, Souter A L, Pollock L L. All–du–Path coverage for parallel programs. In: Proceedings of International Symposium on Software Testing and Analysis. 1998, 153–162

[4] Taylor R N, Levine D L, Kelly C D. Structural testing of concurrent programs. IEEE Transactions on Software Engineering, 1992, 18(3): 206–214

[5] Flanagan C, Godefroid P. Dynamic partial order reduction for model checking software. In: Proceedings of the 32nd Symposium on Principles of Programming Languages. 2005, 110–121

[6] Hwang G H, Tai K C, Huang T L. Reachability testing: an approach to testing concurrent software. International Journal on Software Engineering and Knowledge Engineering, 1995, 5(4): 493–510

[7] Lei Y, Carver R H. Reachability testing of concurrent programs. IEEE Transactions on Software and Engineering, 2006, 32(6): 382–403

[8] Carver R H, Lei Y. A class library for implementing, testing, and debugging concurrent programs. International Journal on Software Tools for Technology Transfer, 2010, 12(1): 69–88

[9] Lei Y, Carver R H, Kacker R, Kung D. A combinatorial testing strategy for concurrent programs. Journal of Software Testing, Verification, and Reliability, 2007, 17(4): 207–225

[10] Carver R, Lei Y. Distributed reachability testing. Concurrency and Computation: Practice and Experience, 2010, 22(18): 2445–2466

[11] Kuhn D R,Wallace D R. Software fault interaction and implication for software testing. IEEE Transactions on Software Engineering, 2004, 30(6): 1–4

[12] Nie C, Leung H. A survey of combinatorial testing. ACM Computing Surveys, 2011, 43(2): 11: 1–29

[13] Nanda M G, Ramesh S. Inter–procedural slicing of multithreaded programs with applications to Java. ACM Transactions on Programming Language Systems, 2006, 28(6): 1088–1144

[14] Wang Z Y, Qian J, Chen L, Xu B W. Generating variable strength combinatorial test suite with one–test–at–a–time. Chinese Journals of Computers, 2013, 35(12): 2542–2552

[15] Wang Z. Combinatorial test case generation and prioritization. Dissertation for the Doctoral Degree. Nanjing: Southeast University, 2009

[16] Ricart G, Agrawala A K. An optimal algorithm for mutual exclusion in computer networks. Communications of the ACM, 1981, 24(1): 9–17

[17] Magee J, Kramer J. Concurrency State models and Java programs. John Wiley & Sons, 2006

[18] Gligoric M, Zhang L, Pereira C, Pokam G. Selective mutation testing for concurrent code. In: Proceedings of International Symposium on Software Testing and Analysis. 2013, 224–234

[19] Lu S, Park S, Seo E, Zhou Y Y. Learning from mistakes: a comprehensive study on real world concurrency bug characteristics. In: Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems. 2008

[20] Just R, Jalali D, Inozemtseva L, Ernst M D, Holmes R, Fraser G. Are mutants a valid substitute for real faults in software testing? In: Proceedings of International Symposium on Foundations of Software Engineering. 2014, 654–665

[21] Yang R D, Chung C G. A path analysis approach to concurrent program testing. Information and Software Technology, 1992, 34(1): 43–56

[22] Yang C, Souter A L, Pollock L L. All–du–path coverage for parallel programs. In: Proceedings of International Symposium on Software Testing and Analysis. 1998, 53–162

[23] Taylor R N, Levine D L, Kelly C D. Structural testing of concurrent programs. IEEE Transactions on Software Engineering, 1992, 18(3): 206–214

[24] Godefroid P, Peled D, Staskauskas M. Using partial–order methods in the formal validation of industrial concurrent programs. IEEE Transactions on Software Engineering, 1996, 22(7): 496–507

[25] Souza S R S, Souza P S L, Machado M, Camillo M, Simão A, Zaluska E. Using coverage and reachability testing to improve concurrent program testing quality. In: Proceedings of the 23th International Conference on Software Engineering and Knowledge Engineering. 2011: 207–212

[26] Cohen M B, Gibbons P B, Mugridge W B, Colbourn C J, Collofello J S. Variable strength interaction testing of components. In: Proceedings of the 27th Annual International Computer Software and Applications Conference. 2003: 413–418

[27] Schroeder P J. Black–box test reduction using input–output analysis. Dissertation for the Doctoral Degree. Chicago: Illinois Institute of Technology, 2001

[28] Czerwonka J. Pairwise testing in real world: practical extensions to test case generator. In: Proceedings of the 24th Pacific Northwest Software Quality Conference. 2006: 419–430

[29] Sen K. Race directed random testing of concurrent programs. In: Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation. 2008, 11–21

[30] Huang J, Zhang C. Persuasive prediction of concurrency access anomalies. In: Proceedings of the 2011 International Symposium on Software Testing and Analysis. 2011, 144–154

[31] Flanagan C, Freund S N. RedCard: redundant check elimination for dynamic race detectors. In: Proceedings of the 2013 European Conference on Object-Oriented Programming. 2013, 255–279

[32] Huang J, Meredith P O, Rosu G. Maximal sound predictive race detection with control flow abstraction. In: Proceedings of the 2014 Conference on Programming Language Design and Implementation. 2014, 337–348

[33] Cai Y, Cao L. Effective and precise dynamic detection of hidden races for java programs. In: Proceedings of the 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering. 2015: 450–460

[34] Park S, Vuduc R W, Harrold M J. Falcon: fault localization in concurrent programs. In: Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering. 2010, 245–254

[35] Cai Y, Chan W K. Lock trace reduction for multithreaded programs. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(12): 2407–2417

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg