Username   Password       Forgot your password?  Forgot your username? 

 

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

                  1. 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
                  2. 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
                  3. 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
                  4. 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
                  5. 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
                  6. 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
                  7. 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
                  8. 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
                  9. 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
                  10. 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
                  11. 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
                  12. A. Einarsson and J. D. Nielsen, “A Survivor’s Guide to Java Program Analysis with Soot,” Notes from Department of Computer Science, 2008
                  13. 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
                  14. 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
                  15. 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
                  16. 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
                  17. 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
                  18. 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
                  19. 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
                  20. M. Weiser, “Program Slicing,” IEEE Transactions on Software Engineering, Vol. SE-10, No. 4, pp. 352-357, July 1984
                  21. 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
                  22. 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
                  23. 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
                  24. 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
                  25. 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.Get Free Adobe Reader

                                  Attachments:
                                  Download this file (IJPE-2018-11-14.pdf)IJPE-2018-11-14.pdf[SRD: Static Data Race Detection for Concurrent Programs]659 Kb
                                   
                                  This site uses encryption for transmitting your passwords. ratmilwebsolutions.com