article

Empirical evaluation of a new composite approach to the coverage criteria and reachability testing of concurrent programs

Authors:

S. R. S. Souza,

P. S. L. Souza,

M. A. S. Brito,

E. J. ZaluskaAuthors Info & Claims

Software Testing, Verification & Reliability, Volume 25, Issue 3

Pages 310 - 332

https://doi.org/10.1002/stvr.1568

Published: 01 May 2015 Publication History

Abstract

Testing is a key activity to assure the quality of concurrent applications. In recent years, a variety of different mechanisms have been proposed to test concurrent software. However, a persistent problem is the high testing cost because of the large number of different synchronization sequences that must be tested. When structural testing criteria are adopted, a large number of infeasible synchronization sequences is generated, increasing the testing cost. Although the use of reachability testing reduces the number of infeasible combination because only feasible synchronization sequences are generated, many synchronization combinations are also generated, and this again results in a testing cost with exponential behavior. This paper presents a new composite approach that uses reachability testing to guide the selection of the synchronization sequences tests according to a specific structural testing criterion. This new composite approach is empirically evaluated in the context of message-passing concurrent programs developed with MPI. The experimental study evaluates both the cost and effectiveness of proposed composite approach in comparison with traditional reachability testing and structural testing. The results confirm that the use of the new composite approach has advantages for testing of concurrent applications. Copyright © 2015 John Wiley & Sons, Ltd.

References

[1]

Taylor RN, Levine DL, Kelly C. Structural testing of concurrent programs. IEEE Transaction on Software Engineering 1992; Volume 18 Issue 3: pp.206-215.

Digital Library

[2]

Yang CSD. Program-based, structural testing of shared memory parallel programs. Ph.D. Thesis, University of Delaware, 1999.

[3]

Wong WE, Lei Y, Ma X. Effective generation of test sequences for structural testing of concurrent programs. 10th IEEE International Conference on Engineering of Complex Systems ICECCS 2005, Shanghai, China, 2005; pp.539-548.

Digital Library

[4]

Lu S, Jiang W, Zhou Y. A study of interleaving coverage criteria. Proceedings of the ACM SIGSOFT symposium on the foundations of software engineering, ACM, New York, NY, USA, 2007; pp.533-536.

[5]

Robinson-Mallett C, Hierons RM, Poore J, Liggesmeyer P. Using communication coverage criteria and partial model generation to assist software integration testing. Software Quality Control 2008; Volume 16 Issue 2: pp.185-211.

[6]

Takahashi J, Kojima H, Furukawa Z. Coverage based testing for concurrent software. 28th International Conference on Distributed Computing Systems Workshops, Beijing, China, 2008; pp.533-538.

Digital Library

[7]

Edelstein O, Farchi E, Goldin E, Nir Y, Ratsaby G, Ur S. Framework for testing multi-threaded Java programs. Concurrency and Computation: Practice and Experience 2003; Volume 15 Issue 3-5: pp.485-499.

[8]

Farchi E, Nir Y, Ur S. Concurrent bug patterns and how to test them. 17th International Parallel and Distributed Processing Symposium IPDPS 2003 - Workshop on Parallel and Distributed Systems: Testing and debugging, IEEE Computer Society, Nice, France, April 2003; pp.286-293.

[9]

Lei Y, Carver RH. Reachability testing of concurrent programs. IEEE Transactions on Software Engineering 2006; Volume 32 Issue 6: pp.382-403.

Digital Library

[10]

Carver RH, Tai KC. Replay and testing for concurrent programs. IEEE Software 1991; Volume 8 Issue 2: pp.86-74.

[11]

Damodaran-Kamal SK, Francioni JM. Nondeterminacy: Testing and debugging in message passing parallel programs. 3rd ACM/ONR Workshop on Parallel and Distributed Debugging, New York, 1993; pp.118-128.

[12]

Souza SRS, Vergilio SR, Souza PSL, Simao AS, Hausen AC. Structural testing criteria for message-passing parallel programs. Concurrency and Computation: Practice and Experience 2008; Volume 20: pp.1893-1916.

[13]

Sarmanho FS, Souza PSL, Souza SRS, Simao AS. Structural testing for semaphore-based multithread programs. International Conference on Computational Science ICCS 2008, Lecture Notes in Computer Science LNCS, 2008; Volume 5101: pp.337-346.

Digital Library

[14]

Souza SRS, Souza PSL, Machado MCC, Camillo MS, Simao AS, Zaluska E. Using coverage and reachability testing to improve concurrent program testing quality. 23rd International Conference on Software Engineering and Knowledge Engineering SEKE 2011, Eden Roc Renaissance Miami Beach, United States, 2011; pp.207-212.

[15]

Wohlin C, Runeson P, Höst M, Ohlsson MC, Regnell B, Wesslén A 2012. Experimentation in Software Engineering Kluwer Academic Publishers Norwel Springer; 2012 edition June 17, 2012: MA, USA,.

[16]

Hwang GH, Tai K, Huang T. Reachability testing: an approach to testing concurrent software. International Journal of Software Engineering and Knowledge Engineering 1995; Volume 5: pp.493-510.

[17]

Souza PSL, Souza SRS, Zaluska E. Structural testing for message-passing concurrent programs: an extended test model. Concurrency and Computation: Practice and Experience 2012. to appear in print.

[18]

Rapps S, Weyuker EJ. Selecting software test data using data flow information. IEEE Transaction Software Engineering 1985; Volume 11 Issue 4: pp.367-375.

Digital Library

[19]

Hausen AC, Verglio SR, Souza SRS, Souza PSL, Simao AS. A tool for structural testing of MPI programs. 8th IEEE Latin-American Test Workshop LATW 2007, Cuzco, Peru, 2007; pp.1-6.

[20]

Bonetti DanielRF, Delbem ACB, Travieso G, Souza PSL. Optimizing van der waals calculi using cell-lists and MPI. IEEE Congress on Evolutionary Computation, IEEE, Barcelona, Spain, 2010; pp.1-7.

[21]

Quinn MJ. Parallel computing: Theory and practice 2nd. edn. McGraw-Hill: New York, 1994.

[22]

Grama A, Karypis G, Kumar V, Gupta A. Introduction to Parallel Computing Addison-Wesley Longman Publishing Co., Inc.: Boston, MA, USA, 2003.

[23]

Krawczyk H, Wiszniewski B. Classification of software defects in parallel programs. Technical Report 2, Faculty of Electronics, Technical University of Gdansk: Poland, 1994.

[24]

DeSouza J, Kuhn B, deSupinski BR, Samofalov V, Zheltov S, Bratanov S. Automated, scalable debugging of mpi programs with intel message checker. SE-HPCS'05, ACM, New York, NY, USA, 2005; pp.78-82.

[25]

DeMillo RA, Lipton RJ, Sayward FG. Hints on test data selection: Help for the practicing programmer. Computer April 1978, Volume 11 Issue 4: pp.34-41.

Digital Library

[26]

Andrews JH, Briand LC, Labiche Y. Is mutation an appropriate tool for testing experiments. In Proceedings of the 27th International Conference on Software Engineering ICSEŠ05, St Louis, 2005; pp.15-21.

[27]

Artho C, Biere A, Honiden S. Enforcer - efficient failure injection. Lecture Notes in Computer Science LNCS 2006; Volume 4085: pp.412-427.

[28]

Chen Q, Wang L, Yang Z, Stoller SD. Have: detecting atomicity violations via integrated dynamic and static analysis. Lecture Notes in Computer Science LNCS 2009; Volume 5503: pp.425-439.

[29]

Chen J. Guided testing of concurrent programs using value schedules. Ph.D. Thesis, University of Waterloo, 2009.

[30]

Christakis M, Sagonas K. Detection of asynchronous message passing errors using static analysis. Lecture Notes in Computer Science LNCS 2011; Volume 6539: pp.5-18.

[31]

Ball T, Burckhardt S, Coons KE, Musuvathi M, Qadeer S. Preemption sealing for efficient concurrency testing. Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2010; Volume 6015: pp.420-434.

[32]

Dantas A. Improving developers' confidence in test results of multi-threaded systems: avoiding early and late assertions. Conference on Object-Oriented Programming Systems, Languages, and Applications OOPSLA, Orlando, Florida, 2008; pp.899-900.

[33]

Dantas A, Gaudencio M, Brasileiro F, Cirne W. Obtaining trustworthy test results in multi-threaded systems. Federal University of Campina Grande, Brazil, 2007.

[34]

Emmi M, Qadeer S, RakamariA Z. Delay-bounded scheduling. ACM SIGPLAN Notices POPL 2011 2011; Volume 46 Issue 1: pp.411-422.

[35]

Yu J, Narayanasamy S. A case for an interleaving constrained shared-memory multi-processor. 36th Annual International Symposium on Computer Architecture ISCA 2009, ACM, New York, United States, 2009; pp.325-336.

Digital Library

[36]

Kamil A, Yelick K. Enforcing textual alignment of collectives using dynamic checks. Lecture Notes in Computer Science LNCS 2010; Volume 5898: pp.368-382.

[37]

Rungta N, Mercer EG. A meta heuristic for effectively detecting concurrency errors. Lecture Notes in Computer Science LNCS 2009; Volume 5394: pp.23-37.

[38]

Gligoric M, Jagannath V, Marinov D. Mutmut: Efficient exploration for mutation testing of multithreaded code. Third International Conference on Software Testing, Verification and Validation ICST, Paris, France, 2010; pp.55-64.

Digital Library

[39]

Sen A, Abadir MS. Coverage metrics for verification of concurrent systemc designs using mutation testing. IEEE International High Level Design Validation and Test Workshop HLDVT, Anaheim, CA, United States, 2010; pp.75-81.

[40]

Jagannath V, Gligoric M, Lauterburg S, Marinov D, Agha G. Mutation operators for actor systems. 3rd International Conference on Software Testing, Verification and Validation Workshops ICSTW 2010, Paris, France, 2010; pp.157-162.

Digital Library

[41]

Yang Y, Chen X, Gopalakrishnan G. Inspect: a runtime model checker for multithreaded C programs. University of Utah, USA, 2008.

[42]

Li J, Hei D, Yan L. Correctness analysis based on testing and checking for OpenMP programs. ChinaGrid Annual Conference ChinaGrid 09, Beijing, China, 2009; pp.210-215.

Digital Library

[43]

Musuvathi M, Qadeer S. Fair stateless model checking. Programming Language Design and Implementation PLDI 08, Tucson, Arizona, United States, 2008; pp.362-371.

[44]

Yang Z, Sakallah K. SMT-based Symbolic Model Checking for Multi-threaded Programs. Princeton: NJ, 2008.

[45]

Aichernig B, Griesmayer A, Schlatte R, Stam A. Modeling and testing multi-threaded asynchronous systems with Creol. Electronic Notes in Theoretical Computer Science 2009; Volume 243: pp.3-14.

[46]

Aichernig BK, Griesmayer A, Johnsen EB, Schlatte R, Stam A. Conformance testing of distributed concurrent systems with executable designs. Lecture Notes in Computer Science LNCS 2009; Volume 5751: pp.61-81.

[47]

Takahashi J, Kojima H, Furukawa Z. Coverage based testing for concurrent software. 28th International Conference on Distributed Computing Systems Workshops ICDCS 2008, Beijing, China, 2008; pp.533-538.

Digital Library

[48]

Sherman E, Dwyer MB, Elbaum S. Saturation-based testing of concurrent programs. 7th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering ESEC/FSE 2009, ACM, New York, United States, 2009; pp.53-62.

Digital Library

[49]

Yang RD, Chung CG. Path analysis testing of concurrent programs. Information and Software Technology 1992; Volume 34 Issue 1: pp.43-56.

[50]

Yang RD, Chung CG. The analysis of infeasible concurrent paths of concurrent Ada programs. Fourteenth Annual International Computer Software and Applications Conference COMPSAC 1990, Chicago, Illinois, 1990; pp.424-429.

[51]

Yang RD, Chung CG. A path analysis approach to concurrent program testing. International Phoenix Conference on Computers and Communications, Scottsdale, Arizona, 1990; pp.425-432.

[52]

Koppol PV, Tai KC. An incremental approach to structural testing of concurrent software. ACM Sigsoft International Symposium on Software Testing and Analysis ISSTA 1996, ACM, New York, United States, 1996; pp.14-23.

Digital Library

[53]

Koppol PV, Carver RH, Tai KC. Incremental integration testing of concurrent programs. IEEE Transactions on Software Engineering 2002; Volume 28 Issue 6: pp.607-623.

Digital Library

[54]

Kojima H, Kakuda Y, Takahashi J, Ohta T. A model for concurrent states and its coverage criteria. International Symposium on Autonomous Decentralized Systems ISADS 2009, Athens, Greece, 2009; pp.1-6.

[55]

Krawczyk H, Wiszniewski B. A method for determining testing scenarios for parallel and distributed software. Technical University of Gdansk, Poland, 1996.

[56]

Katayama T, Furukawa Z, Ushijima K. Event interactions graph for test-case generations of concurrent programs. Asia Pacific Software Engineering Conference, Brisbane, Queensland, Australia, 1995; pp.29-37.

[57]

Katayama T, Furukawa Z, Ushijima K. A method for structural testing of Ada concurrent programs using the event interactions graph. Asia-Pacific Software Engineering Conference, Seoul, South Korea, 1996; pp.355-364.

[58]

Katayama T, Furukawa Z, Ushijima K. Design and implementation of test-case generation for concurrent programs. Asia Pacific Software Engineering Conference, Taipei, Taiwan, ROC, 1998; pp.262-269.

[59]

Liang Y, Li S, Zhang H, Han C. Timing-sequence testing of parallel programs. Journal of Computer Science and Technology 2000; Volume 15 Issue 1: pp.94-95.

[60]

Lu S, Jiang W, Zhou Y. A study of interleaving coverage criteria. 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering ESEC/FSE 2007, ACM, New York, United States, 2007; pp.533-536.

[61]

Kundu S, Ganai MK, Wang C. Contessa: Concurrency testing augmented with symbolic analysis. Lecture Notes in Computer Science LNCS 2010; Volume 6174: pp.127-131.

[62]

Rungta N, Mercer EG, Visser W. Efficient testing of concurrent programs with abstraction-guided symbolic execution. Lecture Notes in Computer Science LNCS 2009; Volume 5578: pp.174-191.

[63]

Tai KC, Reachability testing of asynchronous message-passing programs. In 8th International Conference on Engineering of Complex Computer Systems ICECCS 2002, Greenbelt MD ed. IEEE Computer Society: USA, 2002; pp.35-46.

[64]

Lei Y, Carver RH, Kacker R, Kung D. A combinatorial testing strategy for concurrent programs. Software Testing Verification and Reliability 2007; Volume 17 Issue 4: pp.207-225.

[65]

Carver RH, Lei Y. A general model for reachability testing of concurrent programs. Lecture Notes in Computer Science LNCS 2004; Volume 3308: pp.76-98.

[66]

Carver RH, Lei Y. Distributed reachability testing of concurrent programs. Concurrency and Computation: Practice and Experience 2010; Volume 22 Issue 18: pp.2445-2466.

[67]

Lei Y, Carver R. Reachability testing of semaphore-based programs. 28th International Computer Software and Applications Conference COMPSAC 2004, Volume 1, Hong Kong, China, 2004; pp.312-317.

[68]

Li SQ, Chen HY, Sun YX. A framework of reachability testing for Java multithread programs. IEEE International Conference on Systems, Man and Cybernetics, Volume 3, 2004; pp.2730-2734.

[69]

Carver RH, Lei Y. A stateful approach to testing monitors in multithreaded programs. IEEE 12th International Symposium on High-Assurance Systems Engineering HASE, San Jose, CA, United States, 2010; pp.54-63.

Digital Library

[70]

Wei W, Wu Y, Lejun Z, Lin G. Testing path generation algorithm with network performance constraints for nondeterministic parallel programs. pp.6. Seventh International Conference on Web-Age Information Management Workshops WAIM 2006, Hong Kong, China, 2006.

[71]

Nagarakatte S, Burckhardt S, Martin MM, Musuvathi M. Multicore acceleration of priority-based schedulers for concurrency bug detection. Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, <bookSeriesTitle>PLDI '12</bookSeriesTitle>, Beijing, China, 2012; pp.543-554.

Digital Library

[72]

Hong S, Ahn J, Park S, Kim M, Harrold MJ. Testing concurrent programs to achieve high synchronization coverage. Proceedings of the International Symposium on Software Testing and Analysis ISSTA2012, 2012; pp.210-220.

Digital Library

[73]

Ding Z, Zhang K, Hu J. A rigorous approach towards test case generation. Information Sciences 2008; Volume 178 Issue 21: pp.4057-4079.

[74]

Tan RP, Nagpal P, Miller S. Automated black box testing tool for a parallel programming library. 2nd International Conference on Software Testing, Verification, and Validation ICST 2009, Denver, Colorado, United States, 2009; pp.307-316.

Digital Library

[75]

Xiaoan B, Na Z, Zuohua D. Test case generation of concurrent programs based on event graph. 5th International Joint Conference on INC, IMS, and IDC NCM 2009, Seoul, Korea, 2009; pp.143-149.

[76]

Souza SRS, Brito MAS, Silva RA, Souza PSL, Zaluska E. Research in concurrent software testing: A systematic review. Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging PADTAD 2011, in Conjunction with International Symposium on Software Testing and Analysis ISSTA 2011, Toronto, ON, Canada, 2011; pp.1-5.

Digital Library

[77]

Chung CM, Shih TK, Wang YH, Lin WC, Kou YF. Task decomposition testing and metrics for concurrent programs. Fifth International Symposium on Software Reliability Engineering ISSRE 1996, White Plains, NY, 1996; pp.122-130.

[78]

Yang CS, Souter AL, Pollock LL. All-du-path coverage for parallel programs. International Symposium on Software Testing and Analysis ISSTA 1998, <bookSeriesTitle>ACM-Software Engineering Notes</bookSeriesTitle>, Clearwater Beach, Florida, United States, 1998; pp.153-162.

Digital Library

[79]

Yang CSD, Pollock LL. All-uses testing of shared memory parallel programs. Software Testing, Verification and Reliability STVR 2003; Volume 13 Issue 1: pp.3-24.

[80]

Tasiran S, Keremoğlu ME, Muşlu K. Location pairs: a test coverage metric for shared-memory concurrent programs. Empirical Software Engineering June 2012; Volume 17 Issue 3: pp.129-165.

[81]

Edelstein O, Farchi E, Nir Y, Ratsaby G, Ur S. Multithreaded Java program test generation. IBM System Journal 2002; Volume 41 Issue 1: pp.111-125.

[82]

Yu Jie, Narayanasamy S, Pereira C, Pokam G. Maple: a coverage-driven testing tool for multithreaded programs. Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, <bookSeriesTitle>OOPSLA '12</bookSeriesTitle>, Tucson, Arizona, USA, 2012; pp.485-502.

[83]

Gong X, Wang Y, Zhou Y, Li B. On testing multi-threaded Java programs. Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing SNPD 2007, Volume 1, Qingdao, China, 2007; pp.702-706.

[84]

Hwang GH, Lin HY, Lin SY, Lin CS. Statement-coverage testing for nondeterministic concurrent programs. Sixth International Symposium on Theoretical Aspects of Software Engineering TASE2012, Beijing, China, 2012; pp.263-266.

Digital Library

[85]

Ratsaby G, Sterin B, Ur S. Improvements in coverability analysis. Proceedings of the International Symposium of Formal Methods Europe on Formal Methods - Getting IT Right, <bookSeriesTitle>FME '02</bookSeriesTitle>, Springer-Verlag, London, UK, UK, 2002; pp.41-56.

Digital Library

Cited By

Carver RLei Y(2018)Stateless techniques for generating global and local test oracles for message-passing concurrent programsJournal of Systems and Software10.1016/j.jss.2017.11.026136:C(237-265)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.jss.2017.11.026
Melo SSouza SSarmanho FSouza P(2018)Contributions for the structural testing of multithreaded programsSoftware Quality Journal10.1007/s11219-017-9376-426:3(921-959)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11219-017-9376-4

Empirical evaluation of a new composite approach to the coverage criteria and reachability testing of concurrent programs
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis

Recommendations

Test-Case Generation for Concurrent Programs with the Testing Criteria Using Interaction Sequences
APSEC '99: Proceedings of the Sixth Asia Pacific Software Engineering Conference

Test-cases play an important roll for high quality of software testing. Inadequate test-cases may cause bugs remaining after testing. Overlapped test-cases lead to the increases in testing costs. This paper proposes a test-case generation method with ...
A Method for Structural Testing of Ada Concurrent Programs Using the Event Interactions Graph
APSEC '96: Proceedings of the Third Asia-Pacific Software Engineering Conference

Software testing generally proceeds as follows: generating test-cases, selecting test-data, executing a test target program, inspecting execution result and evaluating whether testing has already been sufficient or not yet. As for methods for structural ...
Incremental Integration Testing of Concurrent Programs

We present a method for selecting test sequences for concurrent programs from labeled transitions systems (LTS). A common approach to selecting test sequences from a set of LTSs is to derive a global LTS, called the reachability graph, and then force ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Software Testing, Verification & Reliability

Software Testing, Verification & Reliability Volume 25, Issue 3

May 2015

168 pages

ISSN:0960-0833

EISSN:1099-1689

Issue’s Table of Contents

Publisher

John Wiley and Sons Ltd.

United Kingdom

Publication History

Published: 01 May 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Carver RLei Y(2018)Stateless techniques for generating global and local test oracles for message-passing concurrent programsJournal of Systems and Software10.1016/j.jss.2017.11.026136:C(237-265)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.jss.2017.11.026
Melo SSouza SSarmanho FSouza P(2018)Contributions for the structural testing of multithreaded programsSoftware Quality Journal10.1007/s11219-017-9376-426:3(921-959)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11219-017-9376-4

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents