Random forest instruction level detection model for data race in multithreaded programs

SUN Jiaze; YANG Jiawei; YANG Zijiang

doi:10.16511/j.cnki.qhdxxb.2020.22.002

PDF(1931 KB)

Journal of Tsinghua University(Science and Technology) ›› 2020, Vol. 60 ›› Issue (10) : 804-813. DOI: 10.16511/j.cnki.qhdxxb.2020.22.002

SPECIAL SECTION: FAULT TOLERANT COMPUTING

Random forest instruction level detection model for data race in multithreaded programs

{{article.zuoZhe_EN}}

Author information +

History +

Abstract

Data race is a typical concurrency bug in multithreaded programs. Data race is difficult to detect due to the uncertain interleaving in multithreaded programs. A random forest instruction level data race detection model is developed for multithread programs using five attributes to identify the data race features. Firstly, data race detection at the instruction level is based on the happens-before relationship and the lockset algorithm. At the same time, the assembly source code is used to eliminate implicit synchronization pairs. Then, the analysis results from the happens-before relationship and the lockset algorithm are used to train a random forest detection model for multithreaded program data race detection. This data race detection tool for multithreaded programs, AIRaceTest, is implemented on Pin. The model is trained with the results of the multithreaded program instrumentation in GitHub as a sample set. The model accuracy reaches 92.1%. Test results on the classic multithreaded programs, Google data-race-test and Parsec benchmark 3.1, show that the false positives are reduced by about 10.6% and the false negatives are reduced by about 12.3% compared with Eraser, Djit+and Thread Sanitizer. For a large number of threads, the time overhead is reduced by 41.8% while the memory overhead is reduced by 22.4%.

Key words

data race / concurrency bug / random forest / implicit synchronization pairs

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

SUN Jiaze, YANG Jiawei, YANG Zijiang. Random forest instruction level detection model for data race in multithreaded programs[J]. Journal of Tsinghua University(Science and Technology). 2020, 60(10): 804-813 https://doi.org/10.16511/j.cnki.qhdxxb.2020.22.002

References

[1] NETZER R H B, MILLER B P. What are race conditions? Some issues and formalizations[J]. ACM Letters on Programming Languages and Systems, 1992, 1(1):74-88.
[2] VON PRAUN C, GROSS T R. Static detection of atomicity violations in object-oriented programs[J]. Journal of Object Technology, 2004, 3(2):1-12.
[3] ENGLER D, ASHCRAFT K. RacerX:Effective, static detection of race conditions and deadlocks[J]. ACM SIGOPS Operating Systems Review, 2003, 37(5):237-252.
[4] LU S, PARK S, SEO E, et al. Learning from mistakes:A comprehensive study on real world concurrency bug characteristics[J]. ACM SIGARCH Computer Architecture News, 2008, 36(1):329-339.
[5] DINNING A, SCHONBERG E. An empirical comparison of monitoring algorithms for access anomaly detection[C]//Proceedings of the 2nd ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming. Seattle, USA, 1990.
[6] PERKOVIC D, KELEHER P J. Online data-race detection via coherency guarantees[C]//Proceedings of the 2nd USENIX Symposium on Operating Systems Design and Implementation. Seattle, USA, 1996:47-57.
[7] LAMPORT L. Time, clocks, and the ordering of events in a distributed system[J]. Communications of the ACM, 1978, 21(7):558-565.
[8] SAVAGE S, BURROWS M, NELSON G, et al. Eraser:A dynamic data race detector for multithreaded programs[J]. ACM Transactions on Computer Systems (TOCS), 1997, 15(4):391-411.
[9] POZNIANSKY E, SCHUSTER A. Efficient on-the-fly data race detection in multithreaded C++ programs[C]//Proceedings International Parallel and Distributed Processing Symposium. Nice, France, 2003.
[10] PRATIKAKIS P, FOSTER J S, HICKS M. LOCKSMITH:Context-sensitive correlation analysis for race detection[C]//Proceedings of the 27th ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation. Ottawa, Canada, 2006:320-331.
[11] VOUNG J W, JHALA R, LERNER S. RELAY:Static race detection on millions of lines of code[C]//Proceedings of the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering. Dubrovnik, Croatia, 2007:205-214.
[12] SEREBRYANY K, ISKHODZHANOV T. ThreadSanitizer:Data race detection in practice[C]//Proceedings of the Workshop on Binary Instrumentation and Applications. New York, USA, 2009:62-71.
[13] YANG Z, YU Z, SU X H, et al. RaceTracker:Effective and efficient detection of data races[C]//Proceedings of the 17th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD). Shanghai, China, 2016.
[14] GUO Y, CAI Y, YANG Z J. AtexRace:Across thread and execution sampling for in-house race detection[C]//Proceedings of the 11th Joint Meeting on Foundations of Software Engineering. Paderborn, Germany, 2017:315-325.
[15] BREIMAN L. Random forests[J]. Machine Learning, 2001, 45(1):5-32.
[16] JANNESARI A, TICHY W F. Library-independent data race detection[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(10):2606-2616.
[17] XIONG W W, PARK S, ZHANG J Q, et al. Ad hoc synchronization considered harmful[C]//Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation. Vancouver, Canada, 2010.
[18] 禹振, 苏小红, 齐鹏, 等. 基于未来锁集的死锁规避[J]. 计算机研究与发展, 2017, 54(2):428-445. YU Z, SU X H, QI P, et al. Deadlock avoiding based on future lockset[J]. Computer Research and Development, 2017, 54(2):428-445. (in Chinese)
[19] BIENIA C. Benchmarking modern multiprocessors[D]. Princeton, USA:Princeton University, 2011.