|
 ABSTRACT
We present a novel approach to dynamic datarace detection for multithreaded object-oriented programs. Past techniques for on-the-fly datarace detection either sacrificed precision for performance, leading to many false positive datarace reports, or maintained precision but incurred significant overheads in the range of 3x to 30x. In contrast, our approach results in very few false positives and runtime overhead in the 13% to 42% range, making it both efficient and precise. This performance improvement is the result of a unique combination of complementary static and dynamic optimization techniques.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
1
|
|
| |
2
|
B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
|
| |
3
|
David F. Bacon , Robert E. Strom , Ashis Tarafdar, Guava: a dialect of Java without data races, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.382-400, October 2000, Minneapolis, Minnesota, United States
|
| |
4
|
Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
|
| |
5
|
Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.35-46, November 01-05, 1999, Denver, Colorado, United States
|
| |
6
|
Chandrasekhar Boyapati , Martin Rinard, A parameterized type system for race-free Java programs, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.56-69, October 14-18, 2001, Tampa Bay, FL, USA
|
| |
7
|
|
| |
8
|
Guang-Ien Cheng , Mingdong Feng , Charles E. Leiserson , Keith H. Randall , Andrew F. Stark, Detecting data races in Cilk programs that use locks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.298-309, June 28-July 02, 1998, Puerto Vallarta, Mexico
[doi> 10.1145/277651.277696]
|
| |
9
|
|
| |
10
|
Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
|
| |
11
|
J.-D. Choi, A. Loginov, and V. Sarkar. Static datarace analysis for multithreaded object-oriented programs. Technical report, IBM Research, 2001. Report RC22146; www.research.ibm.com/jalapeno/dejavu/
|
| |
12
|
|
| |
13
|
M. Christiaens and K. De Bosschere. TRaDe, a topological approach to on-the-fly race detection in java programs. Proceedings of the Java Virtual Machine Rsearch and Technology Symposium (JVM'01), April 2001
|
| |
14
|
|
| |
15
|
|
| |
16
|
|
| |
17
|
KL Group, 260 King Street East, Toronto, Ontario, Canada. Getting Started with JProbe
|
| |
18
|
Kuck & Associates, Inc., 1906 Fox Drive, Champaign, IL 61820-7345, USA. AssureJ User's Manual, 2.0 Edition, March 1999
|
| |
19
|
|
| |
20
|
|
| |
21
|
Christoph von Praun , Thomas R. Gross, Object race detection, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.70-82, October 14-18, 2001, Tampa Bay, FL, USA
|
| |
22
|
|
| |
23
|
|
| |
24
|
|
| |
25
|
|
| |
26
|
|
| |
27
|
N. Sterling. Warlock: A static data race analysis tool. In USENIX Winter Technical Conference, pages 97--106, 1993
|
CITED BY 72
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pin Zhou , Feng Qin , Wei Liu , Yuanyuan Zhou , Josep Torrellas, iWatcher: Simple, General Architectural Support for Software Debugging, IEEE Micro, v.24 n.6, p.50-56, November 2004
|
|
|
Darrell Reimer , Edith Schonberg , Kavitha Srinivas , Harini Srinivasan , Julian Dolby , Aaron Kershenbaum , Larry Koved, Validating structural properties of nested objects, Companion to the 19th annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 24-28, 2004, Vancouver, BC, CANADA
|
|
|
|
|
|
|
|
|
Amit Sasturkar , Rahul Agarwal , Liqiang Wang , Scott D. Stoller, Automated type-based analysis of data races and atomicity, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rahul Agarwal , Amit Sasturkar , Liqiang Wang , Scott D. Stoller, Optimized run-time race detection and atomicity checking using partial discovered types, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA
|
|
|
|
|
|
|
|
|
|
|
|
Brian Demsky , Michael D. Ernst , Philip J. Guo , Stephen McCamant , Jeff H. Perkins , Martin Rinard, Inference and enforcement of data structure consistency specifications, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA
|
|
|
R. Shetty , M. Kharbutli , Y. Solihin , M. Prvulovic, HeapMon: a helper-thread approach to programmable, automatic, and low-overhead memory bug detection, IBM Journal of Research and Development, v.50 n.2/3, p.261-275, March 2006
|
|
|
|
|
|
|
|
|
Paul Sack , Brian E. Bliss , Zhiqiang Ma , Paul Petersen , Josep Torrellas, Accurate and efficient filtering for the Intel thread checker race detector, Proceedings of the 1st workshop on Architectural and system support for improving software dependability, p.34-41, October 21-21, 2006, San Jose, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Shivali Agarwal , Rajkishore Barik , Vivek Sarkar , Rudrapatna K. Shyamasundar, May-happen-in-parallel analysis of X10 programs, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
|
|
|
Zhenmin Li , Shan Lu , Suvda Myagmar , Yuanyuan Zhou, CP-Miner: a tool for finding copy-paste and related bugs in operating system code, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.20-20, December 06-08, 2004, San Francisco, CA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Zdeněk Letko , Tomáš Vojnar , Bohuslav Křena, AtomRace: data race and atomicity violation detector and healer, Proceedings of the 6th workshop on Parallel and distributed systems: testing, analysis, and debugging, p.1-10, July 20-21, 2008, Seattle, Washington
|
|
|
|
|
|
|
|
|
|
|
|
Shan Lu , Soyeon Park , Chongfeng Hu , Xiao Ma , Weihang Jiang , Zhenmin Li , Raluca A. Popa , Yuanyuan Zhou, MUVI: automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
INDEX TERMS
Primary Classification:
D.
Software
D.1
PROGRAMMING TECHNIQUES
D.1.3
Concurrent Programming
Additional Classification:
D.
Software
D.1
PROGRAMMING TECHNIQUES
D.1.5
Object-oriented Programming
D.2
SOFTWARE ENGINEERING
D.2.5
Testing and Debugging
General Terms:
Experimentation,
Languages,
Measurement,
Performance
Keywords:
dataraces,
debugging,
multithreaded programming,
object-oriented programming,
parallel programs,
race conditions,
static-dynamic co-analysis,
synchronization
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf