Variable strength combinatorial testing of concurrent programs

doi:10.1007/s11704-016-5096-3

Front. Comput. Sci.

2016, Vol. 10

Issue (4) : 631-643 https://doi.org/10.1007/s11704-016-5096-3

RESEARCH ARTICLE

Variable strength combinatorial testing of concurrent programs

Xiaofang QI^1,^2,^*(

),Jun HE^3,^*(

),Peng WANG^1,^2,^*(

),Huayang ZHOU^1,^*(

)

¹. School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
². Key Laboratory of Computer Network and Information Integration, Ministry of Education Southeast University, Nanjing 211189, China
³. NARI Relays Electric Cooperation, Nanjing 211102, China

Download: PDF(468 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Xiaofang QI,Jun HE,Peng WANG,Huayang ZHOU

Just Accepted Date: 26 February 2016 Online First Date: 01 June 2016 Issue Date: 06 July 2016

Cite this article:

Xiaofang QI,Jun HE,Peng WANG, et al. Variable strength combinatorial testing of concurrent programs[J]. Front. Comput. Sci., 2016, 10(4): 631-643.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-5096-3
https://academic.hep.com.cn/fcs/EN/Y2016/V10/I4/631

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 https://doi.org/10.1147/sj.411.0111
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 https://doi.org/10.1145/271771.271804
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 https://doi.org/10.1109/32.126769
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 https://doi.org/10.1145/1040305.1040315
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 https://doi.org/10.1142/S0218194095000241
7	Lei Y, Carver R H. Reachability testing of concurrent programs. IEEE Transactions on Software and Engineering, 2006, 32(6): 382–403 https://doi.org/10.1109/TSE.2006.56
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 https://doi.org/10.1007/s10009-009-0102-9
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 https://doi.org/10.1002/stvr.369
10	Carver R, Lei Y. Distributed reachability testing. Concurrency and Computation: Practice and Experience, 2010, 22(18): 2445–2466 https://doi.org/10.1002/cpe.1573
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 https://doi.org/10.1109/TSE.2004.24
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 https://doi.org/10.1145/1186632.1186636
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 https://doi.org/10.1145/358527.358537
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 https://doi.org/10.1145/2483760.2483773
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 https://doi.org/10.1145/1346281.1346323
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 https://doi.org/10.1145/2635868.2635929
21	Yang R D, Chung C G. A path analysis approach to concurrent program testing. Information and Software Technology, 1992, 34(1): 43–56 https://doi.org/10.1016/0950-5849(92)90093-5
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 https://doi.org/10.1145/271771.271804
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 https://doi.org/10.1109/32.126769
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 https://doi.org/10.1109/32.538606
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 https://doi.org/10.1109/cmpsac.2003.1245373
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 https://doi.org/10.1145/1375581.1375584
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 https://doi.org/10.1145/2001420.2001438
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 https://doi.org/10.1007/978-3-642-39038-8_11
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 https://doi.org/10.1145/2666356.2594315
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 https://doi.org/10.1145/2786805.2786839
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 https://doi.org/10.1145/1806799.1806838
35	Cai Y, Chan W K. Lock trace reduction for multithreaded programs. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(12): 2407–2417 https://doi.org/10.1109/TPDS.2013.13

[1]

FCS-0631-15096-HYZ_suppl_1

Download

[1]	Priyanka CHAWLA,Inderveer CHANA,Ajay RANA. A novel strategy for automatic test data generation using soft computing technique[J]. Front. Comput. Sci., 2015, 9(3): 346-363.
[2]	Yan ZHANG,Dunwei GONG. Generating test data for both paths coverage and faults detection using genetic algorithms: multi-path case[J]. Front. Comput. Sci., 2014, 8(5): 726-740.
[3]	Chang-ai SUN,Zuoyi WANG,Guan WANG. A property-based testing framework for encryption programs[J]. Front. Comput. Sci., 2014, 8(3): 478-489.
[4]	Dunwei GONG, Yan ZHANG. Generating test data for both path coverage and fault detection using genetic algorithms[J]. Front Comput Sci, 2013, 7(6): 822-837.

Viewed

Full text

Abstract

Cited

Shared

Discussed