More Web Proxy on the site http://driver.im/

research-article

Towards a better collaboration of static and dynamic analyses for testing concurrent programs

Authors:

Steve MacDonaldAuthors Info & Claims

PADTAD '08: Proceedings of the 6th workshop on Parallel and distributed systems: testing, analysis, and debugging

Article No.: 8, Pages 1 - 9

https://doi.org/10.1145/1390841.1390849

Published: 20 July 2008 Publication History

Abstract

Testing concurrent programs remains a difficult task due to the non-deterministic nature of concurrent executions. Many approaches have been proposed to combine static and dynamic analysis to reduce the complexity of uncovering potential concurrency bugs. However, the existing collaboration schemes only provide a limited mechanism for exchanging relevant information between the two analyses. For example, alias information only flows from the static analysis module to the dynamic analysis module at the beginning of the dynamic analysis. Therefore, we cannot fully exploit the advantages of each type of analysis. Motivated by this observation, in this paper we present a new testing technique which enables a tighter collaboration between static analysis and dynamic analysis. In this collaboration scheme, static analysis and dynamic analysis interact iteratively throughout the whole testing process. Static analysis uses coarse-grained analysis to guide the dynamic analysis to concentrate on the relevant search space, while dynamic analysis collects concrete runtime information during the guided exploration. The runtime information provided by the dynamic analysis helps the static analysis to refine its coarse-grained analysis and provides better guidance on dynamic analysis. Currently, our implementation consists of a static analysis module based on Soot and a dynamic analysis module based on JPF (Java PathFinder).

References

[1]

M. Abadi, C. Flanagan, and S. N. Freund. Types for safe locking: Static race detection for Java. ACM Transactions on Programming Languages and Systems, 28(2):207--255, 2006.

Digital Library

[2]

R. Agarwal, A. Sasturkar, L. Wang, and S. D. Stoller. Optimized run-time race detection and atomicity checking using partial discovered types. In Proc. 20th IEEE/ACM International Conference on Automated Software Engineering, pages 233--242, 2005.

Digital Library

[3]

M. Biberstein, E. Farchi, and S. Ur. Choosing among alternative pasts. In Proc. 17th International Symposium on Parallel and Distributed Processing, page 289.1, 2003.

Digital Library

[4]

M. Biberstein, E. Farchi, and S. Ur. Fidgeting to the point of no return. In Proc. 18th International Parallel and Distributed Processing Symposium, page 266b, 2004.

[5]

G. Brat and W. Visser. Combining static analysis and model checking for software analysis. In Proc. 16th IEEE International Conference on Automated Software Engineering, pages 262--269, 2001.

Digital Library

[6]

J. Chen and S. MacDonald. Testing concurrent programs using value schedules. In Proc. 22nd IEEE/ACM International Conference on Automated Software Engineering, pages 313--322, 2007.

Digital Library

[7]

J. Chen and S. MacDonald. Incremental testing of concurrent programs using value schedules. Submitted to 23rd IEEE/ACM International Conference on Automated Software Engineering, 2008.

Digital Library

[8]

S. Copty and S. Ur. Multi-threaded testing with AOP is easy, and it finds bugs!. In Proc. 11th International Euro-Par Conference, volume 3648 of Lecture Notes in Computer Science, pages 740--749. Springer-Verlag, 2005.

Digital Library

[9]

B. Dufour, B. G. Ryder, and G. Sevitsky. Blended analysis for performance understanding of framework-based applications. In Proc. 2007 International Symposium on Software Testing and Analysis, pages 118--128, 2007.

Digital Library

[10]

D. Engler and K. Ashcraft. Racerx: Effective, static detection of race conditions and deadlocks. In Proc. 19th ACM Symposium on Operating Systems Principles, pages 237--252, 2003.

Digital Library

[11]

Y. Eytani, K. Havelund, S. D. Stoller, and S. Ur. Towards a framework and a benchmark for testing tools for multi-threaded programs. Concurrency and Computation: Practice and Experience, 19(3):267--279, 2007.

Digital Library

[12]

P. Godefroid. Model checking for programming languages using VeriSoft. In Proc. 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 174--186, 1997.

Digital Library

[13]

S. MacDonald, J. Chen, and D. Novillo. Choosing among alternative futures. In Haifa Verification Conference, volume 3875 of Lecture Notes in Computer Science, pages 247--264. Springer-Verlag, 2005.

Digital Library

[14]

M. Naik and A. Aiken. Conditional must not aliasing for static race detection. In Proc. 34th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 327--338, 2007.

Digital Library

[15]

M. Naik, A. Aiken, and J. Whaley. Effective static race detection for Java. In Proc. ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation, pages 308--319, 2006.

Digital Library

[16]

R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. In Proc. 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 167--178, 2003.

Digital Library

[17]

G. Ramalingam. Context-sensitive synchronization-sensitive analysis is undecidable. ACM Transactions on Programming Languages and Systems, 22(2):416--430, 2000.

Digital Library

[18]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multi-threaded programs. In Proc. 16th ACM Symposium on Operating Systems Principles, pages 27--37, 1997.

Digital Library

[19]

R. N. Taylor. Complexity of analyzing the synchronization structure of concurrent programs. Acta Informatica, 19(1):57--84, 1983.

Digital Library

[20]

R. Vallée-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Co. Soot - a Java bytecode optimization framework. In Proc. 1999 Conference of the Centre for Advanced Studies on Collaborative Research, pages 125--135, 1999.

Digital Library

[21]

W. Visser, K. Havelund, G. Brat, S. Park, and F. Lerda. Model checking programs. Automated Software Engineering, 10(2):203--232, 2003.

Digital Library

[22]

Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: Efficient detection of data race conditions via adaptive tracking. In Proc. 20th ACM Symposium on Operating Systems Principles, pages 221--234, 2005.

Digital Library

Cited By

Wang PLu KLi GZhou X(2019)DFTrackerFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-6383-813:2(247-263)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s11704-016-6383-8
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
Elberzhager FMünch JNha V(2012)A systematic mapping study on the combination of static and dynamic quality assurance techniquesInformation and Software Technology10.1016/j.infsof.2011.06.00354:1(1-15)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1016/j.infsof.2011.06.003
Show More Cited By

Index Terms

Towards a better collaboration of static and dynamic analyses for testing 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

Combined Static and Dynamic Analysis

Static analysis is usually faster than dynamic analysis but less precise. Therefore it is often desirable to retain information from static analysis for run-time verification, or to compare the results of both techniques. However, this requires writing ...
Static and Dynamic Analysis: Better Together
Programming Languages and Systems
Abstract
Static analysis and dynamic analysis have dual properties. Static analysis has high coverage, but is imprecise, and produces false alarms. Dynamic analysis has low coverage, but has high precision. We present lessons learned from three different ...
Race directed random testing of concurrent programs
PLDI '08

Bugs in multi-threaded programs often arise due to data races. Numerous static and dynamic program analysis techniques have been proposed to detect data races. We propose a novel randomized dynamic analysis technique that utilizes potential data race ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PADTAD '08: Proceedings of the 6th workshop on Parallel and distributed systems: testing, analysis, and debugging

July 2008

78 pages

ISBN:9781605580524

DOI:10.1145/1390841

General Chair:
Shmuel Ur
IBM Haifa Research Center

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ISSTA '08

Sponsor:

SIGSOFT

ISSTA '08: International Symposium on Software Testing and Analysis

July 20 - 21, 2008

Washington, Seattle

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
359
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)2

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang PLu KLi GZhou X(2019)DFTrackerFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-6383-813:2(247-263)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s11704-016-6383-8
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
Elberzhager FMünch JNha V(2012)A systematic mapping study on the combination of static and dynamic quality assurance techniquesInformation and Software Technology10.1016/j.infsof.2011.06.00354:1(1-15)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1016/j.infsof.2011.06.003
Souza SBrito MSilva RSouza PZaluska ELourenço JFarchi E(2011)Research in concurrent software testingProceedings of the Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging10.1145/2002962.2002964(1-5)Online publication date: 17-Jul-2011
https://dl.acm.org/doi/10.1145/2002962.2002964
Křena BLetko ZVojnar TUr SLourenco J(2010)A platform for search-based testing of concurrent softwareProceedings of the 8th Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging10.1145/1866210.1866215(48-58)Online publication date: 13-Jul-2010
https://dl.acm.org/doi/10.1145/1866210.1866215
Wu MZhou BShi WSpyratos NKapetanios ETraina AChbeir RBadr Y(2009)A self-adaptive test framework for concurrent programsProceedings of the International Conference on Management of Emergent Digital EcoSystems10.1145/1643823.1643911(456-457)Online publication date: 27-Oct-2009
https://dl.acm.org/doi/10.1145/1643823.1643911

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents