Abstract
The reality of multi-core hardware has made concurrent programs pervasive. Unfortunately, writing correct concurrent programs is difficult. Atomicity violation, which is caused by concurrently executing code unexpectedly violating the atomicity of a code segment, is one of the most common concurrency errors. However, atomicity violations are hard to find using traditional testing and debugging techniques.
This paper presents a hybrid approach that integrates static and dynamic analyses to attack this problem. We first perform static analysis to obtain summaries of synchronizations and accesses to shared variables. The static summaries are then instantiated with runtime values during dynamic executions to speculatively approximate the behaviors of branches that are not taken. Compared to dynamic analysis, the hybrid approach is able to detect atomicity violations in unexecuted parts of the code. Compared to static analysis, the hybrid approach produces fewer false alarms. We implemented this hybrid analysis in a tool called HAVE that detects atomicity violations in multi-threaded Java programs. Experiments on several benchmarks and real-world applications demonstrate promising results.
The work was supported in part by Wyoming NASA Space Grant Consortium, NASA Grant NNG05G165H, Wyoming NASA EPSCoR, NASA Grant NCC5-578, NSF CCF-0811287, CNS-0831298, CNS-0627447, CCF-0613913, and CNS-0509230.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agarwal, R., Sasturkar, A., Wang, L., Stoller, S.D.: Optimized run-time race detection and atomicity checking using partial discovered types. In: Proc. 20th IEEE/ACM International Conference on Automated Software Engineering (ASE) (November 2005)
Agarwal, R., Wang, L., Stoller, S.D.: Detecting potential deadlocks with static analysis and runtime monitoring. In: Ur, S., Bin, E., Wolfsthal, Y. (eds.) HVC 2005. LNCS, vol. 3875, pp. 191–207. Springer, Heidelberg (2006)
Chen, F., Serbanuta, T.F., Rosu, G.: jPredictor: a predictive runtime analysis tool for Java. In: Proc. 30th International Conference on Software Engineering (ICSE), pp. 221–230. ACM, New York (2008)
Farzan, A., Madhusudan, P.: Monitoring atomicity in concurrent programs. In: Gupta, A., Malik, S. (eds.) CAV 2008. LNCS, vol. 5123, pp. 52–65. Springer, Heidelberg (2008)
Flanagan, C.: Verifying commit-atomicity using model-checking. In: Graf, S., Mounier, L. (eds.) SPIN 2004. LNCS, vol. 2989, pp. 252–266. Springer, Heidelberg (2004)
Flanagan, C., Freund, S.N.: Atomizer: A dynamic atomicity checker for multithreaded programs. In: Proc. ACM Symposium on Principles of Programming Languages (POPL), pp. 256–267 (2004)
Flanagan, C., Freund, S.N., Qadeer, S.: Exploiting purity for atomicity 31(4) (April 2005)
Flanagan, C., Freund, S.N., Yi, J.: Velodrome: a sound and complete dynamic atomicity checker for multithreaded programs. In: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation (PLDI). ACM, New York (2008)
Flanagan, C., Qadeer, S.: A type and effect system for atomicity. In: Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) (2003)
Hatcliff, J., Robby, Dwyer, M.B.: Verifying atomicity specifications for concurrent object-oriented software using model-checking. In: Steffen, B., Levi, G. (eds.) VMCAI 2004. LNCS, vol. 2937, pp. 175–190. Springer, Heidelberg (2004)
Jigsaw, version 2.2.4, http://www.w3c.org
Lu, S., Tucek, J., Qin, F., Zhou, Y.: AVIO: detecting atomicity violations via access interleaving invariants. In: Twelfth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) (2006)
Park, C.-S., Sen, K.: Randomized active atomicity violation detection in concurrent programs. In: Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering (FSE), pp. 135–145. ACM, New York (2008)
Sasturkar, A., Agarwal, R., Wang, L., Stoller, S.D.: Automated type-based analysis of data races and atomicity. In: Proc. ACM SIGPLAN 2005 Symposium on Principles and Practice of Parallel Programming (PPoPP) (June 2005)
von Praun, C., Gross, T.R.: Object race detection. SIGPLAN Notices 36(11), 70–82 (2001)
von Praun, C., Gross, T.R.: Static detection of atomicity violations in object-oriented programs. Journal of Object Technology 3(6) (June 2004)
Wang, L., Stoller, S.D.: Run-time analysis for atomicity. In: Third Workshop on Runtime Verification (RV 2003), vol. 89(2) (2003)
Wang, L., Stoller, S.D.: Static analysis of atomicity for programs with non-blocking synchronization. In: Proc. ACM SIGPLAN 2005 Symposium on Principles and Practice of Parallel Programming (PPoPP) (June 2005)
Wang, L., Stoller, S.D.: Accurate and efficient runtime detection of atomicity errors in concurrent programs. In: Proc. ACM SIGPLAN 2006 Symposium on Principles and Practice of Parallel Programming (PPoPP). ACM Press, New York (2006)
Wang, L., Stoller, S.D.: Runtime analysis of atomicity for multi-threaded programs. Transactions on Software Engineering 32(2), 93–110 (2006)
Xu, M., Bodik, R., Hill, M.D.: A serializability violation detector for shared-memory server programs. In: Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, Q., Wang, L., Yang, Z., Stoller, S.D. (2009). HAVE: Detecting Atomicity Violations via Integrated Dynamic and Static Analysis. In: Chechik, M., Wirsing, M. (eds) Fundamental Approaches to Software Engineering. FASE 2009. Lecture Notes in Computer Science, vol 5503. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00593-0_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-00593-0_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00592-3
Online ISBN: 978-3-642-00593-0
eBook Packages: Computer ScienceComputer Science (R0)