Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

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 QI1,2,*(),Jun HE3,*(),Peng WANG1,2,*(),Huayang ZHOU1,*()
1. School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
2. Key Laboratory of Computer Network and Information Integration, Ministry of Education Southeast University, Nanjing 211189, China
3. 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