基于二型模糊逻辑的多线程数据竞争检测方法研究

doi:10.11896/j.issn.1002-137X.2017.12.027

摘要/Abstract

摘要： 多线程机制以其诸多优势在程序开发中被广泛使用,然而随着多线程软件规模的增长,程序中潜存着许多并发缺陷,最常见的并发缺陷是数据竞争和死锁。目前,针对这些并发缺陷的检测手段都无法处理线程时序的不确定性,无法处理运行时环境对线程时序的影响,同时也不能计算这些并发缺陷发生的概率并根据概率生成其处理优先级。针对以上问题,提出了一种基于二型模糊逻辑的多线程数据竞争检测方法。该方法将传统的多线程时序分析和缺陷检测方法作为预处理,考虑程序运行时环境因素对线程时序的影响,利用二型模糊逻辑和隐马尔科夫模型对待检测程序建模,计算待检测程序在某一系统负载下的时序概率,并根据时序概率生成时序缺陷处理优先级列表供软件开发人员参考。

关键词: 二型模糊逻辑,隐马尔科夫模型,数据竞争检测

Abstract: Multi-threaded mechanism has been widely used in software development because of its advantages.However,with the growth of program scales,there are plenty of potential parallel defects in multi-threaded programs.The most common parallel defects are data race and deadlock.However,none of the traditional defect detection methods take into account the uncertainty of time sequence analysis and run-time environment.And it is hard to calculate the probability of parallel defects to generate a priority order list based on the probability.To solve these problems,we proposed a data race detection method based on type-2 fuzzy logic.This method considers the influence of run-time environment factors,and uses the traditional parallel defects detection methods as pre-processing step.Then it builds a time sequence analysis model for the target program based on type-2 fuzzy logic and hidden Markov model.It can calculate the probability of all the potential defects,then generates a priority order list for software developers to deal with defects and allocate resources.

Key words: Type-2 fuzzy logic,Hidden Markov model,Data race detection

杨璐,余守文,严建峰. 基于二型模糊逻辑的多线程数据竞争检测方法研究[J]. 计算机科学, 2017, 44(12): 135-143. https://doi.org/10.11896/j.issn.1002-137X.2017.12.027

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. https://doi.org/10.11896/j.issn.1002-137X.2017.12.027

参考文献

[1] KIM K,YAVUZ K T,SANDERS B.Precise Data Race Detection in a Relaxed Memory Model Using Heuristic-Based Model Checking[C]∥Proceedings of the 24th IEEE/ACM InternationalConference on Automated Software Engineering (ASE2009).IEEE Computer Society,2009:495-499.
[2] AGARWAL R,STOLLER S.Run-Time Detection of Potential Deadlocks for Programs with Locks,Semaphores,and Condition Variables[C]∥Proceedings of the 4th Workshop on Parallel and Distributed Systems:Testing and Debugging (PADTAD2006).ACM,2006:51-60.
[3] JOSHI P,NAIK M,SEN K,et al.An Effective Dynamic Analysis for Detecting Generalized Deadlocks[C]∥Proceedings of the 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE2010).ACM,2010:327-336.
[4] HENZINGER T,JHALA R,MAJUMDAR R.Race Checkingby Context Inference[C]∥Proceedings of the 25th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI2004).ACM,2004:1-13.
[5] FLANAGAN C,LEINO K,LILLBRIDGE M,et al.Extended Static Checking for Java[C]∥Proceedings of the 23rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI2002).ACM,2002:234-245.
[6] NAIK M,PARK C S,SEN K,et al.Effective Static Deadlock Detection[C]∥Proceedings of the 31st IEEE International Conference on Software Engineering (ICSE2009).IEEE Computer Society,2009:386-396.
[7] MATSAKIS N,GROSS T.A Time-Aware Type System for Data-Race Protection and Guaranteed Initialization[C]∥Procee-dings of the 25th ACM International Conference on Object Orien-ted Programming,Systems,Languages and Applications (OOPSLA2010),2010.ACM,2010:634-651.
[8] KAHOLN V,YANG Y,SANKARANARAYANAN S,et al.Fast and Accurate Static Data-Race Detection for Concurrent Programs[C]∥Proceedings of the 19th International Conference on Computer Aided Verification (CAV2007),2007.Heidelberg:Springer Berlin,2007:226-239.
[9] VOUNG J,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,2007.ACM,2007:205-214.
[10] PRATIKAKIS P,FOSTER J,HICKS M.Locksmith:Practical Static Race Detection for C[J].ACM Transactions on Programming Languages and Systems (TOPLAS),2011,33(1):1-55.
[11] TERAUCHI T.Checking Race Freedom via Linear Program-ming[C]∥Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI2008).ACM,2008:1-10.
[12] KAHLON V,SINHA N,KRUUS E,et al.Static Data Race Detection for Concurrent Programs with Asynchronous Calls[C]∥Proceedings of the 7th joint meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering,2009.ACM,2009:13-22.
[13] CHUGH R,VOUNG J,JHALA R,et al.Dataflow Analysis for Concurrent Programs via Datarace Detection[C]∥Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI2008).ACM,2008:316-326.
[14] MARINO D,MUSUVATHI M,NARAYANSAMY S.Lite-Race:Effective Sampling for Lightweight Data-Race Detection[C]∥Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation(PLDI 2009).ACM,2009:134-143.
[15] FLANAGAN C,FREUND S.Atomizer:A Dynamic Atomicity Checker For Multithreaded Programs[J].Science of Computer Programming,2008,71(2):89-109.
[16] POZNIANSKY E,SCHUSTER A.MultiRace:Efficient On-the-Fly Data Race Detection in Multithreaded C++ Programs[J].Concurrency and Computation:Practice and Experience,2007,19(3):327-340.
[17] ELMAS T,QADEER S,TASIRAN S.Goldilocks:A Race and Transaction-Aware Java Runtime[C]∥Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI2007).ACM,2007:245-255.
[18] FLANAGAN C,FREUND S.FastTrack:Efficient and Precise Dynamic Race Detection[C]∥Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI2009).ACM,2009:121-133.
[19] BOND M,COONS K,MCKINLEY K.PACER:ProportionalDetection of Data Races[C]∥Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI2010).ACM,2010:255-268.
[20] TIAN C,NAGARAJAN V,GUPTA R,et al.Dynamic recognition of synchronization operations for improved data race detection[C]∥Proceedings of the 2008 International Symposium on Software Testing and Analysis,2008.ACM,2008:143-154.
[21] LI D,SRISA-AN W,DWYER M.SOS:Saving Time in Dynamic Race Detection with Stationary Analysis[C]∥Proceedings of the 26th ACM International Conference on Object Oriented Programming,Systems,Languages and Applications(OOPSLA 2011).ACM,2011:35-50.
[22] CHOI J D,LEE K,LOGINOV A,et al.Efficient and Precise Datarace Detection for Multithreaded Object-Oriented Programs[C]∥Proceedings of the 23rd ACM SIGPLAN Conference on Programming Language Design and Implementation(PLDI 2002).ACM,2002:258-269.
[23] NISHIYAMA H.Detecting Data Races using Dynamic Escape Analysis based on Read Barrier[C]∥Proceedings of the 3rd Virtual Machine Research and Technology Symposium,2004.USENIX Association,2004:10-10.
[24] JOSHI P,NAIK M,PARK C S,et al.CalFuzzer:An Extensible Active Testing Framework for Concurrent Programs[C]∥Proceedings of the 21st International Conference on Computer Aided Verification (CAV2009).Heidelberg:Springer Berlin,2009:675-681.
[25] JOSHI P,PARK C S,SEN K,et al.A Randomized Dynamic Program Analysis Technique for Detecting Real Deadlocks[C]∥Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI2009).ACM,2009:110-120.
[26] SEN K.Race Directed Random Testing of Concurrent Programs[C]∥Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2008).ACM,2008:11-21.
[27] MUSUVATHI M,QADEER S,BALL T,et al.Finding andReproducing Heisenbugs in Concurrent Programs[C]∥Procee-dings of the 8th USENIX Conference on Operating Systems Design and Implementation (OSDI 2008).USENIX Association,2008:267-280.
[28] CHEN F,SERBANUTA T,ROSU G.jPredictor:A Predictive Runtime Analysis Tool for Java[C]∥Proceedings of the 30th International Conference on Software Engineering (ICSE2008).ACM,2008:221-230.
[29] SMARAGDAKIS Y,EVANS J,SADOWSKI C,et al.SoundPredictive Race Detection in Polynomial Time[C]∥Proceedings of the 39th annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL2012).ACM,2012:387-400.
[30] BODDEN E,HAVELUND K.Aspect-Oriented Race Detection in Java[J].IEEE Transactions on Software Engineering,2010,36(4):509-527.
[31] ZENG J,XIE L,LIU Z Q.Type-2 fuzzy Gaussian Mixture Mo-dels[J].Pattern Recognition,2008,41(12):3636-3643.
[32] ZENG J,LIU Z Q.Type-2 Fuzzy Markov Random Fields and Their Application to Handwritten Chinese Character Recognition[J].IEEE Transactions on Fuzzy Systems,2008,16(3):747-760.
[33] KONG D G,TAN X B,XI H S,et al.Hidden Markov Model for Multi-Thread Programs Time Sequence Analysis[J].Journal of Software,2010,21(3):461-472.(in Chinese) 孔德光,谭小彬,奚宏生,等.多线程程序时序分析的隐Markov模型[J].软件学报,2010,21(3):461-472.
[34] WENG D,YANG L,LIU Q,et al.Type-2 Fuzzy Logic Based Deadlock Detection[J].International Journal of Digital Content Technology and its Applications,2012,6(1):429-438.
[35] STAMP M.A revealing introduction to hidden markov models[J].Leee Assp Magruine,2004,1(24):258-261.
[36] KLIR G,CLAIR U,YUAN B.Fuzzy Set Theory:Foundationsand Applications[M].Prentice Hall,1997.
[37] MENDEL J,JHON R,LIU F.Interval Type-2 Fuzzy Logic Systems Made Simple[J].IEEE Transactions on Fuzzy Systems,2006,14(6):808-821.
[38] MENDEL J.Advances in Type-2 Fuzzy Sets and Systems[J].Information Sciences,2007,177(1):84-110.
[39] WU D R,MENDEL J.Uncertainty Measures for Interval Type-2Fuzzy Sets[J].Information Sciences,2007,177(23):5378-5393.
[40] MENDEL J.Type-2 Fuzzy Sets and Systems:an Overview[J].IEEE Computational Intelligence Magazine,2007,2(1):20-29.
[41] WENG D L.Research for Type-2 Fuzzy Logic Based Deadlock and Data Race Detection[D].Shuzhou:Soochow University,2012.(in Chinese) 翁东良.基于二型模糊逻辑的死锁与数据竞争检测方法研究[D].苏州:苏州大学,2012.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed