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

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

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.

0
/ / Recommend

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jsjkx.com/EN/10.11896/j.issn.1002-137X.2017.12.027

https://www.jsjkx.com/EN/Y2017/V44/I12/135

References

[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

Comments

Recommended 0

No Suggested Reading articles found!

Type-2 Fuzzy Logic Based Multi-threaded Data Race Detection

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 0

Metrics

Comments

Recommended 0