Computer Science ›› 2020, Vol. 47 ›› Issue (10): 315-321.doi: 10.11896/jsjkx.190700079

• Information Security • Previous Articles     Next Articles

Dynamic Hybrid Data Race Detection Algorithm Based on Sampling Technique

LI Meng-ke, ZHENG Qiu-sheng, WANG Lei   

  1. Research Institute of Front Information Technology,Zhongyuan University of Technology,Zhengzhou 450007,ChinaHenan Key Laboratory on Public Opinion Intelligent Analysis,Zhengzhou 450007,China
  • Received:2019-07-10 Revised:2019-12-09 Online:2020-10-15 Published:2020-10-16
  • About author:LI Meng-ke,born in 1996,postgraduate.Her main research interests include high performance computing and so on.
    WANG Lei,born in 1977,professor,master supervisor.His main research interests include research and development of high performance computing and domestic independent and controllable basic software.
  • Supported by:
    National Key Research and Development Project (2016QY07X1503,162300410190)

Abstract: Data race is a major source of concurrency bugs.Numerous static and dynamic program analysis techniques have been proposed to detect data races.However,some of detectors may cause a large detection overhead and some of detectors may miss lots of true races.In this paper,a dynamic hybrid data race detection algorithm AsampleLock is proposed,which is based on the optimized FastTrack algorithm and lock mode.It uses the sampling technique,monitoring the function pairs from concurrent threads running simultaneously at the same time,and obtains memory access pairs that really involve data race through the preliminary data race detection,thereby reducing analysis overhead of race detection.In order to reduce the influence of the algorithm on thread scheduling,AsampleLock adopts nolock-hb relation to judge the concurrency relationship of access events,adopts map to record read and write informations of shared variables,and adopts the locking patterns to perform dynamic data race detection,thereby reducing false positives and false negatives.On the basis of the above methods,this paper implements the prototype system,named AsampleLock,and chooses the Parsec benchmark suite to evaluate the race detectors.Experiments compared to FastTrack algorithm,LiteRace algorithm and Multilock-HB algorithm.The results show that the time overhead of AsampleLock algorithm is reduced by 8% compared with FastTrack algorithm.Compared with LiteRace algorithm and FastTrack algorithm,the data race detection rate of AsampleLock algorithm is increased by 39% and 27%,respectively.

Key words: Multithreaded program, Data race detection, Preliminary data race, Locking patterns

CLC Number: 

  • TP311.53
[1]LU S W,ZHOU Y.A study of interleaving co-verage criteria[C]//The 6th Joint Meeting on European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering:Companion Papers.ACM,2007:533-536.
[2]LU S.How to deal with concurrent bugs in multithreaded programs[J].Communication of China Computer Society,2013,9(2):20-27.
[3]LU S,PARK E,SEO,et al.Learning from mistake-s:A compre-hensive study on real world concurrency bug characteristics[C]//Proc. ASPLOS.2008:329-339.
[4]JACKSON J.Nasdaq’s Facebook glitch came from ‘RaceConditions’[EB/OL].[2012-03-24].https://www.computerworld.com/article/2504676/nasdaq-s-facebook-glitch-came-from--race-conditions-.html.
[5]JIMENEZ M,PAPADAKIS M,LE TRAON Y.Vulnerabilityprediction models:A case study on the Linux kernel[C]//2016 IEEE 16th International Working Conference on Source Code Analysis and Manipulation(SCAM).2016:1-10.
[6]ENGLER D,ASHCRAFT K.RacerX:effective,static detection of race conditions and deadlocks[J].ACM SIGOPS Operating Systems Review,2003,37(5):237-252.
[7]VOUNG J,JHALA R,LERNER S.RELAY:Static Race Detection on Millions of Lines of Code[C]//Joint Meeting of the European Software Engineering Conference & the ACM Sigsoft Symposium on the Foundations of Software Engineering.ACM,2007:205-214.
[8]POZNIANSKI E,SCHUSTER A.Efficient On-the-Fly DataRace Detection in Multithreaded C++ Programs[C]//International Parallel & Distributed Processing Symposium.IEEE,2003:179-190.
[9]CORMAC F S N F.FastTrack:Efficient and precise dynamicrace detection[J].ACM SIGPLAN Notices,2009,44(6):121-133.
[10]CAI Y,CHANW K.LOFT:Redundant Synchronization Event Removal for Data Race Detection[C]//IEEE International Symposium on Software Reliability Engineering.IEEE,2011:160-169.
[11]YANG Z,YU Z,SU X,et al.RaceTracker:Effec-tive and efficient detection of data races[C]//2016 17th IEEE/ACIS International Conference on Software Engineering,Artificial Intelligence,Networking and Parallel/Distributed Computing (SNPD).IEEE Computer Society,2016:293-300.
[12]XIE X,XUE J,ZHANG J.Acculock:Accurate and Efficient Detection of Data Races[C]//IEEE/ACM International Sympos-ium on Code Generation & Optimization.IEEE,2011:201-212.
[13]XIE X,XUE J,ZHANG J.Acculock:accurate and efficient de-tection of data races[J].Software:Practice and Experience,2013,43(5):543-576.
[14]YU M,YOO S K,BAED H.SimpleLock:Fast and Accurate Hybrid Data Race Detector[C]//International Conference onPa-rallel & Distributed Computing.IEEE,2014:50-56.
[15]YU M,LEE J,BAE D,et al.AdaptiveLock:Efficient Hybrid Data Race Detection Based on Real-World Locking Patterns[J].International Journal of Parallel Programming,2019,47(7):805-837.
[16]BIENIA C.Thesis:Benchmarking modern multiprocessors[D].Princeton University,2011.
[17]LAMPORT L.Time,clocks,and the orde-ring of events in a distributed system[J].Communications of the ACM,1978,21(7):558-565.
[18]GUO Y,CAI Y,YANG Z.AtexRace:across thread and execution sampling for in house race detection[C]//Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering.ACM,2017:315-325.
[19]MARINO D,MUSUVATHI M,NARAYANASAMY S.LiteRace:effective sampling for lightweight data race detection[C]//ACM Sigplan Notices.ACM,2009:134-143.
[20]BOND M D,COONS K E,MCKINLEY K S.PACER:proportional detection of data races[C]//ACM Sigplan Notices.ACM,2010:255-268.
[21]YU M,BAE D H.SimpleLock+:fast and accurate hybrid data race detection[J].The Computer Journal,2016,59(6):793-809.
[22]LUK C K,COHN R S,MUTH R,et al.Pin:Building Customized Program Analysis Tools with Dynamic Instrumentation[C]//ACM Sigplan Notices.ACM,2005:190-200.
[23]ZHANG Y,LIANG Y N,ZHANG D W,et al.An Effective Approach of Detecting Data Race in Concurrent Programs[J].Journal of Computer Applications,2019,39(1):67-71.
[24]WANG X F.Research on Dynamic Data Race Detection[D].Wuhan:Huazhong University of Science And Technology,2016.
[25]YU J,NARAYANASAMY S,PEREIRA C,et al.Maple:ACoverage-Driven Testing Tool for Multithreaded Programs[C]//Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications.ACM,2012:485-502.
[26]YU M,PARK S M,CHUN I,et al.Experimen-tal Performance Comparison of Dynamic Dat-a RaceDetectionTechniques[J].ETRI Journal,2017,39(1):124-134.
[1] YANG Lu, YU Shou-wen and YAN Jian-feng. Type-2 Fuzzy Logic Based Multi-threaded Data Race Detection [J]. Computer Science, 2017, 44(12): 135-143.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] YANG Yu-qi, ZHANG Guo-an and JIN Xi-long. Dual-cluster-head Routing Protocol Based on Vehicle Density in VANETs[J]. Computer Science, 2018, 45(4): 126 -130 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151 .
[3] ZHANG Jing and ZHU Guo-bin. Hot Topic Discovery Research of Stack Overflow Programming Website Based on CBOW-LDA Topic Model[J]. Computer Science, 2018, 45(4): 208 -214 .
[4] WENG Li-guo, KONG Wei-bin, XIA Min and CHOU Xue-fei. Satellite Imagery Cloud Fraction Based on Deep Extreme Learning Machine[J]. Computer Science, 2018, 45(4): 227 -232 .
[5] LIANG Jun-bin, ZHOU Xiang, WANG Tian and LI Tao-shen. Research Progress on Data Collection in Mobile Low-duty-cycle Wireless Sensor Networks[J]. Computer Science, 2018, 45(4): 19 -24 .
[6] LI Jian-hong, WU Ya-rong and LV Ju-jian. Online Single Image Super-resolution Algorithm Based on Group Sparse Representation[J]. Computer Science, 2018, 45(4): 312 -318 .
[7] HOU Lin-qing, CAI Ying, FAN Yan-fang, XIA Hong-ke. Interest Community Based Message Transmission Scheme in Mobile Social Networks[J]. Computer Science, 2018, 45(6): 105 -110 .
[8] CHEN Jin-yin, XIONG Hui, ZHENG Hai-bin. Parameters Optimization for SVM Based on Particle Swarm Algorithm[J]. Computer Science, 2018, 45(6): 197 -203 .
[9] SHEN Xia-jiong, ZHANG Jun-tao, HAN Dao-jun. Short-term Traffic Flow Prediction Model Based on Gradient Boosting Regression Tree[J]. Computer Science, 2018, 45(6): 222 -227 .
[10] ZHOU Feng, LI Rong-yu. Convolutional Neural Network Model for Text Classification Based on BGRU Pooling[J]. Computer Science, 2018, 45(6): 235 -240 .