Dasarath Weeratunge
Abstract
Concurrency bugs are often due to inadequate synchronization that fail to prevent specific (undesirable) thread interleavings. Such errors, often referred to as Heisenbugs, are difficult to detect, prevent, and repair. In this paper, we present a new technique to increase program robustness against Heisenbugs. We profile correct executions from provided test suites to infer fine-grained atomicity properties. Additional deadlock-free locking is injected into the program to guarantee these properties hold on production runs. Notably, our technique does not rely on witnessing or analyzing erroneous executions. The end result is a scheme that only permits executions which are guaranteed to preserve the atomicity properties derived from the profile. Evaluation results on large, real-world, open-source programs show that our technique can effectively suppress subtle concurrency bugs, with small runtime overheads (typically less than 15%).
- R. Agarwal, L. Wang, and S. D. Stoller. Detecting Potential Deadlocks with Static Analysis and Runtime Monitoring. In PADTAD'05.Google Scholar
- T. Bergan, O. Anderson, J. Devietti, L. Ceze, D. Grossman. CoreDet: A Compiler and Runtime System for Deterministic Multithreaded Execution. In ASPLOS'10. Google ScholarDigital Library
- E. Bodden and K. Havelund. Racer: Effective Race Detection Using AspectJ. In ISSTA'08. Google ScholarDigital Library
- S. Burckhardt, P. Kothari, M. Musuvathi and S. Nagarakatte. A randomized scheduler with probabilistic guarantees of finding bugs. In ASPLOS'10. Google ScholarDigital Library
- M. D. Bond, K. E. Coons and K. S. McKinley. Pacer: Proportional Detection of Data Races. In PLDI'10. Google ScholarDigital Library
- R. Jr. Bocchino, S. Heumann, N. Honarmand, S. V. Adve, V. S. Adve, A. Welc and T. Shpeisman, Safe nondeterminism in a deterministic-by-default parallel language, In POPL'11. Google ScholarDigital Library
- L. Chew and D. Lie, Kivati: fast detection and prevention of atomicity violations, In EuroSys'10. Google ScholarDigital Library
- F. Chen, T. F. Serbanuta, and G. Rosu. JPredictor: A Predictive Runtime Analysis Tool for Java. In ICSE'08. Google ScholarDigital Library
- S. Cherem, T. M. Chilimbi, S. Gulwani. Inferring Locks for Atomic Sections. In PLDI'08. Google ScholarDigital Library
- H. Cui, J. Wu, C. Tsai and J. Yang. Stable Deterministic Multithreading through Schedule Memoization. In OSDI'10. Google ScholarDigital Library
- D. Cunningham, K. Gudka and S. Eisenbach, Keep off the grass: locking the right path for atomicity, In CC'08/ETAPS'08. Google ScholarDigital Library
- P. Diniz and M. Rinard, Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs, In Journal of Parallel and Distributed Computing, 49(1):218--244, 1996, Google ScholarDigital Library
- G. W. Dunlap, D. G. Lucchetti, M. A. Fetterman, and P. M. Chen. Execution Replay of Multiprocessor Virtual Machines. In VEE'08. Google ScholarDigital Library
- M. Emmi, J. S. Fischer, R. Jhala, and R. Majumdar. Lock allocation, In POPL'07. Google ScholarDigital Library
- C. Flanagan and S. N Freund. Atomizer: A Dynamic Atomicity Checker for Multithreaded Programs. In POPL'04. Google ScholarDigital Library
- C. Hammer, J. Dolby, M. Vaziri, and F. Tip. Dynamic Detection of Atomic-Set-Serializability Violations. In ICSE'08. Google ScholarDigital Library
- P. Joshi, M. Naik, K. Sen, and D. Gay. An Effective Dynamic Analysis for Detecting Generalized Deadlocks. In FSE'10. Google ScholarDigital Library
- Z. Jin, L. Song, W. Zhang, S. Lu, and S. B. Liblit, Automated Atomicity-Violation Fixing. In PLDI'11. Google ScholarDigital Library
- S. Lu and S. Park and C. Hu and X. Ma, and W. Jiang and Z. Li and R. Popa, R. and Y. Zhou. MUVI: Automatically Inferring Multi-Variable Access Correlations and Detecting Related Semantic and Concurrency Bugs. In SOSP'07. Google ScholarDigital Library
- S. Lu, S. Park, E. Seo, and Y. Zhou. Learning from Mistakes: A Comprehensive Study on Real-World Concurrency Bug Characteristics. In ASPLOS'08. Google ScholarDigital Library
- B. McCloskey, F. Zhou, D. Gay and E. Brewer. Autolocker: Synchronization Inference for Atomic Sections. In POPL'06. Google ScholarDigital Library
- P. Montesinos, M. Hicks, S. T. King, and J. Torrellas. Capo: A Software-Hardware Interface for Practical Deterministic Multiprocessor Replay. In ASPLOS'09. Google ScholarDigital Library
- M. Musuvathi and S. Qadeer. Fair Stateless Model Checking. In PLDI'08. Google ScholarDigital Library
- R. O'Callahan and J.-D. Choi. Hybrid Dynamic Data Race Detection. In PPoPP'03. Google ScholarDigital Library
- S. Park, S. Lu, and Y. Zhou. CTrigger: Exposing Atomicity Violation Bugs from their Hiding Places. In ASPLOS'09. Google ScholarDigital Library
- P. Pratikakis, J. S. Foster and M. Hicks. LOCKSMITH: Context-Sensitive Correlation Analysis for Race Detection. In PLDI'06. Google ScholarDigital Library
- S. Rajamani, G. Ramalingam, V. P. Ranganath, and K. Vaswani, ISOLATOR: dynamically ensuring isolation in concurrent programs, In ASPLOS'09. Google ScholarDigital Library
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A Dynamic Data Race Detector for Multithreaded Programs. ACM Trans. Comp. Sys., 1997. Google ScholarDigital Library
- M. Vaziri, F. Tip and J. Dolby. Associating Synchronization Constraints with Data in an Object-Oriented Language. In POPL'06. Google ScholarDigital Library
- L. Wang and S. D. Stoller. Accurate and Efficient Runtime Detection of Atomicity Errors in Concurrent Programs. In PPoPP'06. Google ScholarDigital Library
- D. Weeratunge, X. Zhang and S. Jagannathan, Analyzing multicore dumps to facilitate concurrency bug reproduction. In ASPLOS'10. Google ScholarDigital Library
- D. Weeratunge, X. Zhang and S. Jagannathan, Suppressing Concurrency Bugs Using Scheduler Shepherding Feb. 04, 2011, TR-11-002 http://www.cs.purdue.edu/research/technical_reports/2011/TR%2011-002.pdfGoogle Scholar
- J. Wu, H. Cui and J. Yang. Bypassing Races in Live Applications with Execution Filters. In OSDI'10. Google ScholarDigital Library
- M. Xu, R. Bodik, and M. D. Hill. A Serializability Violation Detector for Shared-Memory Server Programs. In PLDI'05. Google ScholarDigital Library
- J. Yu and S. Narayanasamy. A Case for an Interleaving Constrained Shared-Memory Multi-Processor. In ISCA'09. Google ScholarDigital Library
Index Terms
- Accentuating the positive: atomicity inference and enforcement using correct executions
Recommendations
Accentuating the positive: atomicity inference and enforcement using correct executions
OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applicationsConcurrency bugs are often due to inadequate synchronization that fail to prevent specific (undesirable) thread interleavings. Such errors, often referred to as Heisenbugs, are difficult to detect, prevent, and repair. In this paper, we present a new ...
Altruistic locking
Long-lived transactions (LLTs) hold on to database resources for relatively long periods of time, significantly delaying the completion of shorter and more common transactions. To alleviate this problem we propose an extension to two-phase locking, ...
Determinism at Standard-Library Level in TM-Based Applications
Deterministic execution of a multi-threaded application guarantees that threads access shared memory in the same order and the application gives the same output whenever it runs with the same input parameters. Determinism provides repeatability, which ...
Comments