SRD: Static Data Race Detection for Concurrent Programs
Volume 14, Number 11, November 2018, pp. 2683-2691 DOI: 10.23940/ijpe.18.11.p14.26832691
Yang Zhang, Yanan Liang, and Dongwen Zhang
School of Information Science and Technology, Hebei University of Science and Technology, Shijiazhuang, 050000, China
(Submitted on August 10, 2018; Revised on September 12, 2018; Accepted on October 11, 2018)
Abstract:
Data race probably occurs when many threads concurrently access the same memory location and at least one is a write thread. Data race detection suffers from false negatives and false positives. How to detect data race and avoid false negatives and false positives has become a hot topic. This paper proposes a static data race detection methodology to eliminate false negatives and false positives. We use Soot to conduct intra-thread and inter-thread analysis. Our data race detection focuses on variable access events that are collected from call graphs. Several program analysis technologies, such as alias variable analysis, alias lock analysis, happens-before analysis, constraint graph, and slicing analysis, are used to improve the coverage and precision of the detection results. In the experimentation, several benchmarks, such as raytracer, sor, and mergesort, have been selected to evaluate our methodology. Experimental results show that SRD can not only eliminate fake races but also identify potential races. Furthermore, SRD can detect more positive races than the existing tool RVPredict.
References: 25
- R. H. B. Netzer and B. P. Miller, “What Are Race Conditions? Some Issues and Formalizations,” ACM LOPLAS, Vol. 1, No. 1, pp. 74-88, January 1992
- X. H. Su, Z. Yu, T. T. Wang, and P. J. Ma, “A Survey on Exposing, Detecting and Avoiding Concurrency Bugs,” Chinese Journal of Computers, Vol. 38, No. 11, pp. 2215-2233, November 2015
- P. Chatarasi, J. Shirako, M. Kong, and V. Sarkar, “An Extended Polyhedral Model for SPMD Programs and Its Use in Static Data Race Detection,” in Proceedings of Languages and Compilers for Parallel Computing (LCPC), pp. 106-120, Rochester, New York, USA, 2017
- D. Engler and K. Ashcraft, “RacerX: Effective, Static Detection of Race Conditions and Deadlocks,” in Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP ’03), pp. 237-252, New York, USA, 2003
- V. Kahlon, S. Sankaranarayanan, and A. Gupta, “Static Analysis for Concurrent Programs with Applications to Data Race Detection,” International Journal on Software Tools for Technology Transfer, Vol. 15, No. 4, pp. 321-336, August 2013
- V. Kahlon, Y. Yang, S. Sankaranarayanan, and A. Gupta, “Fast and Accurate Static Data-Race Detection for Concurrent Programs,” in Proceedings of International Conference on Computer Aided Verification, Springer, Vol. 4590, pp. 226-239, 2007
- N. Yoshiura and W. Wei, “Static Data Race Detection for Java Programs with Dynamic Class Loading,” in Proceedings of Internet and Distributed Computing Systems (IDCS), pp. 161-173, Calabria, Italy, 2014
- L. Effinger-Dean, B. Lucia, L. Ceze, G. Dan, and H. J. Boehm, “IFRit: Interference-Free Regions for Dynamic Data-Race Detection,” ACM SIGPLAN Notices, Vol. 47, No. 10, pp. 467-484, October 2012
- E. Pozniansky and A. Schuster, “MultiRace: Efficient On-the-Fly Data Race Detection in Multithreaded C++ Programs,” Concurrency & Computation-Practice & Experience, Vol. 19, No. 3, pp. 327-340, 2007
- T. Zhang, D. Lee, and C. Jung, “TxRace: Efficient Data Race Detection Using Commodity Hardware Transactional Memory,” ACM SIGPLAN Notices, Vol. 51, No. 4, pp. 159-173, April 2016
- Y. Zhang and Y. Y. Hao, “Incremental Detection of Data Race for Java Programs,” Journal of Xi’an Jiaotong University, Vol. 43, No. 8, pp. 22-27, August 2009
- A. Einarsson and J. D. Nielsen, “A Survivor’s Guide to Java Program Analysis with Soot,” Notes from Department of Computer Science, 2008
- R. Valléerai, P. Co, E. Gagnon, L. Hendren, and P. Lam, “Soot - a Java Byte Code Optimization Framework,” Masters Abstracts International, pp. 214-224, 2010
- L. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System,” Communications of the ACM, Vol. 21, No. 7, pp. 558-565, 2008
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson, “Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs,” ACM SIGOPS Operating Systems Review, Vol. 31, No. 5, pp. 27-37, 1997
- K. Serebryany and T. Iskhodzhanov, “ThreadSanitizer - Data Race Detection in Practice,” in Proceedings of the Workshop on Binary Instrumentation and Applications (WBIA), pp. 62-71, New York, USA, 2009
- X. Xie and J. Xue, “Acculock: Accurate and Efficient Detection of Data Races,” Software: Practice and Experience, Vol. 43, No. 5, pp. 543-576, 2013
- M. Yu and D. H. Bae, “SimpleLock+: Fast and Accurate Hybrid Data Race Detector,” Computer Journal, Vol. 59, No. 6, pp. 793-809, June 2016
- P. Wu, Y. Y. Chen, and J. Zhang. “Static Data-Race Detection for Multithread Programs,” Journal of Computer Research & Development, Vol. 43, No. 2, pp. 329-335, February 2006
- M. Weiser, “Program Slicing,” IEEE Transactions on Software Engineering, Vol. SE-10, No. 4, pp. 352-357, July 1984
- L. A. Smith, J. M. Bull, and J. Obdrizalek, “A Parallel Java Grande Benchmark Suite,” in Proceedings of ACM/IEEE Conference of Supercomputing (SC’01), pp. 6, Denver, CO, USA, 2001
- E. Farchi, Y. Nir, and S. Ur, “Concurrent Bug Patterns and How to Test Them,” in Proceedings of International Symposium on Parallel and Distributed Processing, pp. 286-287, Washington, DC, USA, 2003
- J. Huang, P. O. Meredith, and G. Rosu, “Maximal Sound Predictive Race Detection with Control Flow Abstraction,” in Proceedings of ACM SIGPLAN Conference on Programming Language Design & Implementation (PLDI’14), pp. 337-348, Edinburgh, UK, 2014
- A. Jannesari, K. Bao, and W. F. Tichy, “Helgrind+: An Efficient Dynamic Race Detector,” in Proceedings of IEEE International Symposium on Parallel and Distributed Processing, pp. 1-13, Washington, DC, USA, 2009
- J. D. Choi, A. Loginov, and V. Sarkar, “Static Data Race Analysis for Multithreaded Object-Oriented Programs,” IBM Research Division Thomas J Watson Research Centre, Vol. 30, No. 2, pp. 150-156, 2001
Please note : You will need Adobe Acrobat viewer to view the full articles.
Attachments:
IJPE-2018-11-14.pdf | [SRD: Static Data Race Detection for Concurrent Programs] | 659 Kb |
|