research-article

Structural Testing of Concurrent Programs

Authors:

Richard N. Taylor,

David L. Levine,

Cheryl D. KellyAuthors Info & Claims

IEEE Transactions on Software Engineering, Volume 18, Issue 3

Pages 206 - 215

https://doi.org/10.1109/32.126769

Published: 01 March 1992 Publication History

Abstract

Although structural testing techniques are among the weakest available with regard to developing confidence in sequential programs, they are not without merit. The authors extend the notion of structural testing criteria to concurrent programs and propose a hierarchy of supporting structural testing techniques. Coverage criteria described include concurrency state coverage, state transition coverage and synchronization coverage. Requisite support tools include a static concurrency analyzer and either a program transformation system or a powerful run-time monitor. Also helpful is a controllable run-time scheduler. The techniques proposed are suitable for Ada or CSP-like languages. Best results are obtained for programs having only static naming of tasking objects.

References

[1]

{1} R. N. Taylor and C. D. Kelly, "Structural testing of concurrent programs," in Proc. Workshop on Software Test. (Banff, AB, Canada), July 1986, pp. 164-169.

[2]

{2} W. R. Adrion, M. A. Branstad, and J. C. Cherniavsky, "Validation, verification, and testing of computer software," ACM Comput. Surveys, vol. 14, pp. 159-192, June 1982.

Digital Library

[3]

{3} W. E. Howden, "A survey of dynamic analysis methods," in Tutorial: Software Testing and Validation Techniques, 2nd ed., E. Miller and W. Howden, Eds. Los Alamitos, CA: IEEE Computer Soc. Press, 1981, pp. 209-231.

[4]

{4} L. A. Clarke, A. Podgurski, D. J. Richardson, and S. J. Zeil, "A comparison of data flow path selection criteria," in Proc. 8th Int. Conf. on Software Eng. (London), Aug. 1985, pp. 244-251.

Digital Library

[5]

{5} E. J. Weyuker, "The cost of data flow testing: an empirical study," IEEE Trans. Software Eng., vol. 16, pp. 121-128, Feb. 1990.

Digital Library

[6]

{6} L. A. Clarke, D. J. Richardson, and S. J. Zeil, "TEAM: a support environment for testing, evaluation, and analysis," in Proc. ACM SIGSOFT '88: 3rd Symp. on Software Development Environ., Nov. 1988, pp. 153-162.

Digital Library

[7]

{7} K. R. Apt, "A static analysis of CSP programs," in Proc. Workshop on Program Logic (Pittsburgh, PA), June 1983.

Digital Library

[8]

{8} R. N. Taylor, "A general-purpose algorithm for analyzing concurrent programs," Commun. ACM, vol. 26, pp. 362-376, May 1983.

Digital Library

[9]

{9} S. M. German, D. P. Helmbold, and D. C. Luckham, "Monitoring for deadlocks in Ada tasking," in Proc. AdaTEC Conf. on Ada (Arlington, VA), pp. 10-25, Oct. 1982.

Digital Library

[10]

{10} J. L. Peterson, "Petri nets," ACM Comput. Surveys, vol. 9, pp. 223-252, Sept. 1977.

Digital Library

[11]

{11} M. Young, R. N. Taylor, K. Forester, and D. Brodbeck, "Integrated concurrency analysis in a software development environment," in Proc. 3rd Workshop on Software Test., Analysis, and Verification (Key West, FL), Dec. 1989, pp. 200-209.

Digital Library

[12]

{12} R. K. Keller, M. Cameron, R. N. Taylor, and D. B. Troup, "User interface development and software environments: the Chiron-1 system," in Proc. 13th Int. Conf. on Software Eng. (Austin, TX), May 1991, pp. 208-218.

Digital Library

[13]

{13} D. L. Long and L. A. Clarke, "Task interaction graphs for concurrency analysis," in Proc. 11th Int. Conf. on Software Eng. (Pittsburgh, PA), May 1989.

Digital Library

[14]

{14} G. K. Wampler, "Static concurrency analysis of Ada programs," Master's thesis, Univ. California, Irvine, 1985.

[15]

{15} D. S. Rosenblum, "A methodology for the design of Ada transformation tools in a DIANA environment," IEEE Software, vol. 2, pp. 24-33, Mar. 1985.

Digital Library

[16]

{16} J. Gait, "A probe effect in concurrent programs," Software - Practice and Experience, vol. 16, pp. 225-233, Mar. 1986.

Digital Library

[17]

{17} R. N. Taylor, "Analysis of concurrent software by cooperative application of static and dynamic techniques," in Software Validation, H.-L. Hausen, Ed. Amsterdam: North-Holland, 1984, pp. 127-137.

Digital Library

[18]

{18} L. A. Clarke, "A system to generate test data and symbolically execute programs," IEEE Trans. Software Eng., vol. SE-2, pp. 215-222, Sept. 1976.

Digital Library

[19]

{19} W. E. Howden, "Symbolic testing and the DISSECT symbolic evaluation system," IEEE Trans. Software Eng., vol. SE-3, pp. 266-278, July 1977.

Digital Library

[20]

{20} A. F. Brindle, R. N. Taylor, and D. F. Martin, "A debugger for Ada tasking," IEEE Trans. Software Eng., vol. 15, pp. 293-304, Mar. 1989.

Digital Library

[21]

{21} K. C. Tai, R. H. Carver, and E. E. Obaid, "Debugging concurrent Ada programs by deterministic execution," IEEE Trans. Software Eng., vol. 17, pp. 45-63, Jan. 1991.

Digital Library

[22]

{22} T. J. LeBlanc and J. M. Mellor-Crummey, "Debugging parallel programs with instant replay," IEEE Trans. Computers, vol. C-36, pp. 471-482, Apr. 1987.

Digital Library

[23]

{23} S. N. Weiss, "A formal framework for the study of concurrent program testing," in Proc. 2nd Workshop on Software Test., Analysis, and Verification (Banff, AB, Can.), July 1988, pp. 106-113.

[24]

{24} S. Morasca and M. Pezzè, "Using high-level Petri nets for testing concurrent and real-time systems," in Real-Time Systems: Theory and Applications. New York: Elsevier Science, 1990, pp. 119-131.

[25]

{25} W. J. Yeh and M. Young, "Compositional reachability analysis using process algebra," in Proc. Symp. on Software Test., Analysis, and Verification (TAV4), (Victoria, BC, Can.), Oct. 1991, pp. 49-59.

Digital Library

[26]

{26} R. N. Taylor et al., "Foundations for the Arcadia environment architecture," in Proc. ACM SIGSOFT '88: 3rd Symp. on Software Development Environ. (Boston), Nov. 1988, pp. 1-13.

Digital Library

Cited By

Huo YLi YSu YHe PXie ZLyu MBissyandé TKlein JBird CSarro F(2023)AutoLog: A Log Sequence Synthesis Framework for Anomaly DetectionProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00133(497-509)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00133
Marsso LMateescu RSerwe W(2020)Automated Transition Coverage in Behavioural Conformance TestingTesting Software and Systems10.1007/978-3-030-64881-7_14(219-235)Online publication date: 9-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64881-7_14
Wang ZZhao YLiu SSun JChen XLin HZimmermann TLawall JMarinov D(2019)MAP-CoverageProceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2019.00073(722-734)Online publication date: 10-Nov-2019
https://dl.acm.org/doi/10.1109/ASE.2019.00073
Show More Cited By

Index Terms

Structural Testing of Concurrent Programs
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
  2. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages

Recommendations

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 ...
Saturation-based testing of concurrent programs
ESEC/FSE '09: Proceedings of the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering

Coverage measures help to determine whether a test suite exercises a program adequately according to a testing criterion. Many existing measures, however, are defined over coverage domains that cannot be precisely calculated, rendering them of limited ...
Replay and Testing for Concurrent Programs

Attention is given to the problems that arise during the testing and debugging cycle of concurrent programs because of their nondeterministic execution behavior, whereby multiple executions of a concurrent program with the same input may exercise ...

Reviews

Reviewer: Bruce M. McMillin

The title indicates that this paper provides test set generation for concurrent programs. The work is much more basic than this, however, and focuses on the problem of structural determination for test set generation. In this framework, the paper contributes to an understanding of how various coverage criteria can be subsumed through a static analysis treatment. The paper is good at stating the limitations of the approach of structural testing; the reader should be aware that this paper does not propose a solution to the complete problem of concurrent program testing, just a basic portion of it. Much follow-up work will be necessary to apply the concept.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Software Engineering

IEEE Transactions on Software Engineering Volume 18, Issue 3

March 1992

88 pages

ISSN:0098-5589

Editor:
Victor R. Basili
Univ. of Maryland, College Park, MD

Issue’s Table of Contents

Copyright © Copyright © 1992 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 March 1992

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

69
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

Huo YLi YSu YHe PXie ZLyu MBissyandé TKlein JBird CSarro F(2023)AutoLog: A Log Sequence Synthesis Framework for Anomaly DetectionProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00133(497-509)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00133
Marsso LMateescu RSerwe W(2020)Automated Transition Coverage in Behavioural Conformance TestingTesting Software and Systems10.1007/978-3-030-64881-7_14(219-235)Online publication date: 9-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-64881-7_14
Wang ZZhao YLiu SSun JChen XLin HZimmermann TLawall JMarinov D(2019)MAP-CoverageProceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2019.00073(722-734)Online publication date: 10-Nov-2019
https://dl.acm.org/doi/10.1109/ASE.2019.00073
Bianchi FMargara APezze M(2018)A Survey of Recent Trends in Testing Concurrent Software SystemsIEEE Transactions on Software Engineering10.1109/TSE.2017.270708944:8(747-783)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TSE.2017.2707089
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
Abdelrasoul MRosu GDi Penta MNguyen T(2017)Promoting secondary orders of event pairs in randomized scheduling using a randomized strideProceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering10.5555/3155562.3155655(741-752)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.5555/3155562.3155655
Choudhary ALu SPradel MUchitel SOrso ARobillard M(2017)Efficient detection of thread safety violations via coverage-guided generation of concurrent testsProceedings of the 39th International Conference on Software Engineering10.1109/ICSE.2017.32(266-277)Online publication date: 20-May-2017
https://dl.acm.org/doi/10.1109/ICSE.2017.32
Qi XHe JWang PZhou H(2016)Variable strength combinatorial testing of concurrent programsFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-5096-310:4(631-643)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s11704-016-5096-3
Arora VBhatia RSingh M(2016)A systematic review of approaches for testing concurrent programsConcurrency and Computation: Practice & Experience10.1002/cpe.371128:5(1572-1611)Online publication date: 10-Apr-2016
https://dl.acm.org/doi/10.1002/cpe.3711
Azadi Marand EAzadi Marand EChallenger M(2015)DSML4CPComputer Languages, Systems and Structures10.1016/j.cl.2015.09.00244:PC(319-341)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.cl.2015.09.002
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents