Satish Narayanasamy
ABSTRACT
Many concurrency bugs in multi-threaded programs are due to dataraces. There have been many efforts to develop static and dynamic mechanisms to automatically find the data races. Most of the prior work has focused on finding the data races and eliminating the false positives.
In this paper, we instead focus on a dynamic analysis technique to automatically classify the data races into two categories - the dataraces that are potentially benign and the data races that are potentially harmful. A harmful data race is a real bug that needs to be fixed. This classification is needed to focus the triaging effort on those data races that are potentially harmful. Without prioritizing the data races we have found that there are too many data races to triage. Our second focus is to automatically provide to the developer a reproducible scenario of the data race, which allows the developer to understand the different effects of a harmful data race on a program's execution.
To achieve the above, we record a multi-threaded program's execution in a replay log. The replay log is used to replay the multi-threaded program, and during replay we find the data races using a happens-before based algorithm. To automatically classify if a data race that we find is potentially benign or potentially harmful, were play the execution twice for a given data race - one for each possible order between the conflicting memory operations. If the two replays for the two orders produce the same result, then we classify the data race to be potentially benign. We discuss our experiences in using our replay based dynamic data race checker on several Microsoft applications.
- S. V. Adve, M. D. Hill, B. P. Miller, and R. H. B. Netzer. Detecting data races on weak memory systems. In ISCA '91: Proceedings of the 18th Annual International Symposium on Computer architecture, 1991. Google Scholar
Digital Library
- R. Agarwal, A. Sasturkar, L. Wang, and S. D. Stoller. Optimized runtime race detection and atomicity checking using partial discovered types. In In Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering, pages 233--242, 2005. Google ScholarDigital Library
- S. Bhansali, W. Chen, S. de Jong, A. Edwards, and M. Drinic. Framework for instruction-level tracing and analysis of programs. In Second International Conference on Virtual Execution Environments, June 2006. Google ScholarDigital Library
- C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: Preventing data races and deadlocks. In Object-Oriented Programming Systems, Languages, and Applications, 2002. Google ScholarDigital Library
- J. D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Effcient and precise datarace detection for multithreaded object-oriented programs. In PLDI '02: Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, pages 258--269, New York, NY, USA, 2002. ACM Press. Google ScholarDigital Library
- J. D. Choi, B. P. Miller, and R. H. B. Netzer. Techniques for debugging parallel programs with flowback analysis. ACM Transactions on Programming Languages and Systems, 13(4):491--530, 1991. Google ScholarDigital Library
- J. D. Choi and S. L. Min. Race frontier: reproducing data races in parallel-program debugging. In PPOPP '91: Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 145--154, 1991. Google ScholarDigital Library
- J. M. Crummey. On-the-fly detection of data races for programs with nested fork-join parallelism. In Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on Supercomputing, pages 24--33, 1991. Google ScholarDigital Library
- D. L. Detlefs, P. A. Martin, M. Moir, and Jr. G. L. Steele. Lockfree reference counting. In PODC '01: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, pages 190--199, 2001. Google ScholarDigital Library
- A. Dinning and E. Schonberg. An empirical comparison of monitoring algorithms for access anomaly detection. In PPOPP '90: Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, pages 1--10, 1990. Google ScholarDigital Library
- A. Dinning and E. Schonberg. Detecting access anomalies in programs with critical sections. In PADD '91: Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, pages 85--96, 1991. Google ScholarDigital Library
- T. Elmas, S. Tasiran, and S. Qadeer. Vyrd: verifying concurrent programs by runtime refinement-violation detection. In PLDI, 2005. Google ScholarDigital Library
- D. Engler and K. Ashcraft. Racerx: effective, static detection of race conditions and deadlocks. In SOSP '03: Proceedings of the nineteenth ACM symposium on Operating systems principles, pages 237--252, 2003. Google ScholarDigital Library
- C. Flanagan and S. N. Freund. Type-based race detection for java. In PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, pages 219--232, 2000. Google ScholarDigital Library
- T. A. Henzinger, R. Jhala, and R. Majumdar. Race checking by context inference. In PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pages 1--13, 2004. Google ScholarDigital Library
- M. Hicks, J. S. Foster, and P. Pratikakis. Inferring locking for atomic sections. In Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT), June 2006.Google Scholar
- L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558--565, 1978. Google ScholarDigital Library
- S. Lu, J. Tucek, F. Qin, and Y. Zhou. Avio: detecting atomicity violations via access interleaving invariants. In ASPLOS-XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, pages 37--48, 2006. Google ScholarDigital Library
- S. L. Min and J.-D. Choi. An efficient cache-based access anomaly detection scheme. In Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating System (ASPLOS), pages 235--244, 1991. Google ScholarDigital Library
- M. Naik, A. Aiken, and J. Whaley. Effective static race detection for java. In PLDI '06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, pages 308--319, 2006. Google ScholarDigital Library
- R. H. B. Netzer. Optimal tracing and replay for debugging shared memory parallel programs. In Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging, pages 1--11, 1993. Google ScholarDigital Library
- H. Nishiyama. Detecting data races using dynamic escape analysis based on read barrier. Third Virtual Machine Research & Technology Symposium, pages 127--138, May 2004. Google ScholarDigital Library
- R. O'Callahan and J. D. Choi. Hybrid dynamic data race detection. In PPoPP '03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 167--178, 2003. Google ScholarDigital Library
- D. Perkovic and P. J. Keleher. Online data-race detection via coherency guarantees. In OSDI, pages 47--57, 1996. Google ScholarDigital Library
- E. Pozniansky and A. Schuster. Efficient on-the-fly data race detection in multithreaded c++ programs. In PPoPP '03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 179--190, 2003. Google ScholarDigital Library
- P. Pratikakis, J. S. Foster, and M. Hicks. Locksmith: context-sensitive correlation analysis for race detection. In PLDI '06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, pages 320--331, 2006. Google ScholarDigital Library
- M. Prvulovic and J. Torrelas. Reenact: Using thread-level speculation mechanisms to debug data races in multithreaded codes. In 30th Annual International Symposium on Computer Architecture, San Diego, CA, June 2003. Google ScholarDigital Library
- S. Qadeer and D. Wu. Kiss: keep it simple and sequential. In PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pages 14--24, 2004. Google ScholarDigital Library
- B. Richards and J. R. Larus. Protocol based data race detection. In Proceedings of the SIGMETRICS Symposium on Parallel and Distributed Tools, pages 40--47. ACM Press, 1998. Google ScholarDigital Library
- M. Ronsse and K. de Bosschere. Recplay: A fully integrated practical record/replay system. ACM Transactions on Computer Systems, 17(2):133--152, 5 1999. Google ScholarDigital Library
- M. Ronsse and K. de Bosschere. Non-intrusive on-the-fly data race detection using execution replay. In Proceedings of Automated and Algorithmic Debugging, Nov 2000.Google Scholar
- A. Sasturkar, R. Agarwal, L. Wang, and S. D. Stoller. Automated type-based analysis of data races and atomicity. In PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 83--94, 2005. Google ScholarDigital Library
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems, 15(4):391--411, 1997. Google ScholarDigital Library
- E. Schonberg. On-the-fly detection of access anomalies. In Proceedings of the ACM SIGPLAN'89 Conference on Programming Language Design and Implementation (PLDI), 1989. Google ScholarDigital Library
- N. Sterling. Warlock - a static data race analysis tool. In Proceedings of the USENIX Winter Technical Conference, pages 97--106, 1993.Google Scholar
- C. von Praun and T. R. Gross. Object race detection. In OOPSLA'01: Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, pages 70--82, 2001. Google ScholarDigital Library
- M. Xu, R. Bodik, and M. D. Hill. A serializability violation detector for shared-memory server programs. In ACM SIGPLAN 2005 Conference on Programming Language Design and Implementation (PLDI), 2005. Google ScholarDigital Library
- Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: efficient detection of data race conditions via adaptive tracking. In SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles, pages 221--234, 2005. Google ScholarDigital Library
Index Terms
- Automatically classifying benign and harmful data races using replay analysis
Recommendations
Data races vs. data race bugs: telling the difference with portend
ASPLOS '12Even though most data races are harmless, the harmful ones are at the heart of some of the worst concurrency bugs. Alas, spotting just the harmful data races in programs is like finding a needle in a haystack: 76%-90% of the true data races reported by ...
Automatically classifying benign and harmful data races using replay analysis
Proceedings of the 2007 PLDI conferenceMany concurrency bugs in multi-threaded programs are due to dataraces. There have been many efforts to develop static and dynamic mechanisms to automatically find the data races. Most of the prior work has focused on finding the data races and ...
Detecting harmful data races through parallel verification
Data races widely exist in concurrent programs and the harmful races have caused severe failures. To detect the harmful races, previous tools verify all the races, identifying the harmful ones. However, efficiency is affected when there are a large ...
Comments