并发程序中数据竞争检测方法
|
摘要
针对数据竞争检测过程中的误报和漏报问题,提出一种静态数据竞争检测方法。首先,使用控制流分析自动构造线程内和线程间函数调用图;然后,收集线程内变量访问事件信息,定义竞争产生条件并分析检测出所有可能的竞争;其次,为了提高检测的准确率,进行别名变量和别名锁的分析降低漏报和误报;最后,通过控制流分析来抽象访问事件之间的时序关系,并结合程序切片技术对访问事件的发生序关系进行判断,以此避免因忽略线程交互带来的误报。依据该方法,使用Java语言在Soot软件分析框架下实现了一个数据竞争检测工具。在实验中,对JGF和IBM Contest基准测试套件中的raytracer和airline等程序进行数据竞争检测,并与目前已有的数据竞争检测算法和工具(HB算法和RVPredict)进行对比。实验结果表明,与HB算法和RVPredict工具相比,该方法检测到的数据竞争总数分别增加了81%和16%,数据竞争检测的准确率分别提升了约14%和19%,有效地避免了数据竞争检测中的漏报和误报现象。
Aiming at the problems of false positive and false negatives in data race detection, a novel static data race detection approach was proposed. Firstly, intra-thread and inter-thread function call graphs were automatically constructed via control flow analysis. Secondly, the information of variable-access events within thread were collected, and possible races were detected based on the defined data race conditions. Then, in order to improve the detection accuracy, alias variables and alias locks were analyzed to reduce false negatives and false positives, respectively. Finally, the sequential relationship between access events was abstracted through control flow analysis, and program slicing was used to determine the happens-before relationship of access events, thereby reducing false positives caused by ignoring thread interactions. A data race detection tool was implemented by Java and Soot framework based on this approach. In the experimentation, several benchmarks from JGF and IBM Contest benchmark suites, such as raytracer and airline, were selected for evaluation, and the results were compared with existing data race detection algorithm and tool( HB( Happens-Before) and RVPredict). The experimental results show that, compared with algorithm HB and tool RVPredict, total number of data races detected by the proposed approach are increased by 81% and 16% respectively, the accuracy of this approach for data race detection are respectively increased by14% and 19%, which effectively avoids false negatives and false positives.
Aiming at the problems of false positive and false negatives in data race detection, a novel static data race detection approach was proposed. Firstly, intra-thread and inter-thread function call graphs were automatically constructed via control flow analysis. Secondly, the information of variable-access events within thread were collected, and possible races were detected based on the defined data race conditions. Then, in order to improve the detection accuracy, alias variables and alias locks were analyzed to reduce false negatives and false positives, respectively. Finally, the sequential relationship between access events was abstracted through control flow analysis, and program slicing was used to determine the happens-before relationship of access events, thereby reducing false positives caused by ignoring thread interactions. A data race detection tool was implemented by Java and Soot framework based on this approach. In the experimentation, several benchmarks from JGF and IBM Contest benchmark suites, such as raytracer and airline, were selected for evaluation, and the results were compared with existing data race detection algorithm and tool( HB( Happens-Before) and RVPredict). The experimental results show that, compared with algorithm HB and tool RVPredict, total number of data races detected by the proposed approach are increased by 81% and 16% respectively, the accuracy of this approach for data race detection are respectively increased by14% and 19%, which effectively avoids false negatives and false positives.
引文
[1]YANG J, JIANG B, CHAN W K. Hist Lock+:precise memory access maintenance without lockset comparison for complete hybrid data race detection[J]. IEEE Transactions on Reliability, 2018,68(3):786-801.
[2]禹振,杨振,苏小红,等.多线程程序数据竞争检测和验证方法研究综述![J].智能计算机与应用,2017,7(3):123-126.(YU Z,YANG Z, SU X H, et al. A survey on methods of data race detection and verification on multithreaded program[J]. Intelligent Computer&Applications, 2017, 7(3):123-126.)
[3]苏小红,禹振,王甜甜,等.并发缺陷暴露、检测与规避研究综述[J].计算机学报,2015,38(11):2215-2233.(SU X H, YU Z,WANG T T, et al. A survey on exposing, detecting and avoiding concurrency bugs[J]. Chinese Journal of Computers, 2015, 38(11):2215-2233.)
[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, 44(3):11-21.
[5]吴俞伯,郭俊霞,李征,等.基于并发程序数据竞争故障的变异策略[J].计算机应用,2016,36(11):3170-3177.(WU Y B, GUO J X, LI Z, et al. Mutation strategy based on concurrent program data racing fault[J]. Journal of Computer Applications, 2016, 36(11):3170-3177.)
[6]张昱,郝允允. Java程序数据竞争的增量式检测[J].西安交通大学学报,2009,43(8):22-27.(ZHANG Y, HAO Y Y. Incremental detection of data race for Java programs[J]. Journal of Xi'an JiaoTong University, 2009, 43(8):22-27.)
[7]POZNIANSKY E, SCHUSTER A. MultiRace:efficient on-the-fly data race detection in multithreaded C++programs[J]. Concurrency&Computation Practice&Experience, 2007, 19(3):327-340.
[8]FLANAGAN C, FREUND S N. Fast Track:efficient and precise dynamic race detection[C]//Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation. New York:ACM, 2009:121-133.
[9]CAI Y, CHAN W K. LOFT:redundant synchronization event removal for data race detection[C]//Proceedings of the 2011 IEEE22nd International Symposium on Software Reliability Engineering.Washington, DC:IEEE Computer Society, 2011:160-169.
[10]SAVAGE S, BURROWS M, NELSON G, et al. Eraser:a dynamic data race detector for multi-threaded programs[J]. ACM Transactions on Computer Systems, 1997, 31(5):27-37.
[11]XIE X, XUE J. ACCULOCK:accurate and efficient detection of data races[J]. Software Practice&Experience, 2013, 43(5):543-576.
[12]ENGLER D, ASHCRAFT K. Racer X:effective, static detection of race conditions and deadlocks[C]//SOSP'03:Proceedings of the19th ACM Symposium on Operating Systems Principles. New York:ACM, 2003:237-252.
[13]PRATIKAKIS P, FOSTER J S, HICKS M. LOCKSMITH:contextsensitive correlation analysis for race detection[J]. ACM SIGPLAN Notices, 2006, 41(6):320-331.
[14]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. New York:ACM, 2007:205-214.
[15]LAM P, VERBRUGGE C, POMINVILLE P, et al. Soot(poster session):a Java bytecode optimization and annotation framework[C]//OOPSLA'00:Proceedings of the 2000 Conference on Object-Oriented Programming, Systems, Languages, and Applications. New York:ACM, 2000:113-114.
[16]LAMPORT L. Time, clocks, and the ordering of events in a distributed system[J]. Communications of the ACM, 2008, 21(7):558-565.
[17]HUANG J, MEREDITH P O, ROSU G. Maximal sound predictive race detection with control flow abstraction[J]. ACM SIGPLAN Notices, 2014, 49(6):337-348.
[18]CHOI J D, LOGINOV A, SARKAR V. Static datarace analysis for multithreaded object-oriented programs[R]. Yorktown Heights,NY:IBM Research Division, 2001:1-18.
[19]吴萍,陈意云,张健.多线程程序数据竞争的静态检测[J].计算机研究与发展,2006,43(2):329-335.(WU P, CHEN Y Y,ZHANG J. Static data-race detection for multithread programs[J].Journal of Computer Research and Development, 2006, 43(2):329-335.)
[20]LIU P, TRIPP O, ZHANG X. IPA:improving predictive analysis with pointer analysis[C]//Proceedings of the 2016 International Symposium on Software Testing and Analysis. New York:ACM,2016:59-69.
[21]WEISER M. Program slicing[J]. IEEE Transactions on Software Engineering, 1984, SE-10(4):352-357.
[22]SMITH L A, BULL J M, OBDRIZALEK J. A parallel Java grande benchmark suite[C]//Proceedings of the 2001 ACM/IEEE Conference of Supercomputing. Piscataway, NJ:IEEE, 2001:8-8.
[23]FARCHI E, NIR Y, UR S. Concurrent bug patterns and how to test them[C]//Proceedings of the 2003 International Symposium on Parallel and Distributed Processing. Washington, DC:IEEE Computer Society, 2003:286-296.
[2]禹振,杨振,苏小红,等.多线程程序数据竞争检测和验证方法研究综述![J].智能计算机与应用,2017,7(3):123-126.(YU Z,YANG Z, SU X H, et al. A survey on methods of data race detection and verification on multithreaded program[J]. Intelligent Computer&Applications, 2017, 7(3):123-126.)
[3]苏小红,禹振,王甜甜,等.并发缺陷暴露、检测与规避研究综述[J].计算机学报,2015,38(11):2215-2233.(SU X H, YU Z,WANG T T, et al. A survey on exposing, detecting and avoiding concurrency bugs[J]. Chinese Journal of Computers, 2015, 38(11):2215-2233.)
[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, 44(3):11-21.
[5]吴俞伯,郭俊霞,李征,等.基于并发程序数据竞争故障的变异策略[J].计算机应用,2016,36(11):3170-3177.(WU Y B, GUO J X, LI Z, et al. Mutation strategy based on concurrent program data racing fault[J]. Journal of Computer Applications, 2016, 36(11):3170-3177.)
[6]张昱,郝允允. Java程序数据竞争的增量式检测[J].西安交通大学学报,2009,43(8):22-27.(ZHANG Y, HAO Y Y. Incremental detection of data race for Java programs[J]. Journal of Xi'an JiaoTong University, 2009, 43(8):22-27.)
[7]POZNIANSKY E, SCHUSTER A. MultiRace:efficient on-the-fly data race detection in multithreaded C++programs[J]. Concurrency&Computation Practice&Experience, 2007, 19(3):327-340.
[8]FLANAGAN C, FREUND S N. Fast Track:efficient and precise dynamic race detection[C]//Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation. New York:ACM, 2009:121-133.
[9]CAI Y, CHAN W K. LOFT:redundant synchronization event removal for data race detection[C]//Proceedings of the 2011 IEEE22nd International Symposium on Software Reliability Engineering.Washington, DC:IEEE Computer Society, 2011:160-169.
[10]SAVAGE S, BURROWS M, NELSON G, et al. Eraser:a dynamic data race detector for multi-threaded programs[J]. ACM Transactions on Computer Systems, 1997, 31(5):27-37.
[11]XIE X, XUE J. ACCULOCK:accurate and efficient detection of data races[J]. Software Practice&Experience, 2013, 43(5):543-576.
[12]ENGLER D, ASHCRAFT K. Racer X:effective, static detection of race conditions and deadlocks[C]//SOSP'03:Proceedings of the19th ACM Symposium on Operating Systems Principles. New York:ACM, 2003:237-252.
[13]PRATIKAKIS P, FOSTER J S, HICKS M. LOCKSMITH:contextsensitive correlation analysis for race detection[J]. ACM SIGPLAN Notices, 2006, 41(6):320-331.
[14]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. New York:ACM, 2007:205-214.
[15]LAM P, VERBRUGGE C, POMINVILLE P, et al. Soot(poster session):a Java bytecode optimization and annotation framework[C]//OOPSLA'00:Proceedings of the 2000 Conference on Object-Oriented Programming, Systems, Languages, and Applications. New York:ACM, 2000:113-114.
[16]LAMPORT L. Time, clocks, and the ordering of events in a distributed system[J]. Communications of the ACM, 2008, 21(7):558-565.
[17]HUANG J, MEREDITH P O, ROSU G. Maximal sound predictive race detection with control flow abstraction[J]. ACM SIGPLAN Notices, 2014, 49(6):337-348.
[18]CHOI J D, LOGINOV A, SARKAR V. Static datarace analysis for multithreaded object-oriented programs[R]. Yorktown Heights,NY:IBM Research Division, 2001:1-18.
[19]吴萍,陈意云,张健.多线程程序数据竞争的静态检测[J].计算机研究与发展,2006,43(2):329-335.(WU P, CHEN Y Y,ZHANG J. Static data-race detection for multithread programs[J].Journal of Computer Research and Development, 2006, 43(2):329-335.)
[20]LIU P, TRIPP O, ZHANG X. IPA:improving predictive analysis with pointer analysis[C]//Proceedings of the 2016 International Symposium on Software Testing and Analysis. New York:ACM,2016:59-69.
[21]WEISER M. Program slicing[J]. IEEE Transactions on Software Engineering, 1984, SE-10(4):352-357.
[22]SMITH L A, BULL J M, OBDRIZALEK J. A parallel Java grande benchmark suite[C]//Proceedings of the 2001 ACM/IEEE Conference of Supercomputing. Piscataway, NJ:IEEE, 2001:8-8.
[23]FARCHI E, NIR Y, UR S. Concurrent bug patterns and how to test them[C]//Proceedings of the 2003 International Symposium on Parallel and Distributed Processing. Washington, DC:IEEE Computer Society, 2003:286-296.