C程序内存泄漏智能化检测方法
|
摘要
内存泄漏在采用显式内存管理机制的C语言中是一种常见的代码缺陷,内存泄漏的检测方法目前主要是静态分析与动态检测.动态检测开销大,且高度依赖测试用例;静态分析目前被学术界和工业界广泛应用,但是存在大量误报,需要人工对检测结果进行确认.内存泄漏静态分析的误报通常是由于对指针、分支语句和全局变量分析的不准确性导致的.提出了一种内存泄漏的智能化检测方法,通过使用机器学习算法学习程序特征与内存泄漏之间的相关性,构建机器学习分类器,并应用机器学习分类器进一步提高内存泄漏静态分析的准确性.首先构建机器学习分类器,然后通过静态分析方法构建从内存分配点开始的SparseValueFlowGraph(SVFG),并从中提取内存泄漏相关特征,再使用规则和机器学习分类器进行内存泄漏的检测.实验结果显示,该方法在分析指针、分支语句和全局变量时是有效的,能够提高内存泄漏检测的准确性,降低内存泄漏检测结果的误报.最后,对未来研究的可行性以及面临的挑战进行了展望.
Memory leak is a common code bug for C programs which uses explicit memory management mechanisms. At present, the main detection methods of memory leaks are static analysis and dynamic detection. Dynamic detection has huge overhead and it is highly dependent on test cases. Static analysis is widely used by academic and industry, but there are a large number of false positives, which need to be manually confirmed. Inaccuracy in the analysis of pointers, branch statements, and global variables leads to false positives in static analysis of memory leaks. In this study, an intelligent detection method is proposed for memory leak. By using machine learning algorithms to learn the correlation between program's features and memory leaks, a machine learning classifier is built and applied to improve the accuracy of static analysis of memory leaks. Firstly, a machine learning classifier is trained. Then, the sparse value flow graph(SVFG) starting from allocation should be constructed by using the static analysis, the features related to memory leaks can be extracted from the SVFG. Lastly, the memory leaks are detected by using rules and machine learning classifier. Experimental results show that the proposed method is effective in analyzing pointers, branch statements, and global variables, and can reduce the false positives of memory leak detection. At the end of this paper, the feasibility of future research and the upcoming challenges are presented.
Memory leak is a common code bug for C programs which uses explicit memory management mechanisms. At present, the main detection methods of memory leaks are static analysis and dynamic detection. Dynamic detection has huge overhead and it is highly dependent on test cases. Static analysis is widely used by academic and industry, but there are a large number of false positives, which need to be manually confirmed. Inaccuracy in the analysis of pointers, branch statements, and global variables leads to false positives in static analysis of memory leaks. In this study, an intelligent detection method is proposed for memory leak. By using machine learning algorithms to learn the correlation between program's features and memory leaks, a machine learning classifier is built and applied to improve the accuracy of static analysis of memory leaks. Firstly, a machine learning classifier is trained. Then, the sparse value flow graph(SVFG) starting from allocation should be constructed by using the static analysis, the features related to memory leaks can be extracted from the SVFG. Lastly, the memory leaks are detected by using rules and machine learning classifier. Experimental results show that the proposed method is effective in analyzing pointers, branch statements, and global variables, and can reduce the false positives of memory leak detection. At the end of this paper, the feasibility of future research and the upcoming challenges are presented.
引文
[1]Clause J,Orso A.LEAKPOINT:Pinpointing the causes of memory leaks.In:Proc.of the 32nd ACM/IEEE Int’l Conf.on Software Engineering.New York:ACM Press,2010.515-524.[doi:10.1145/1806799.1806874]
[2]Liu T,Curtsinger C,Berger ED.DoubleTake:Fast and precise error detection via evidence-based dynamic analysis.In:Proc.of the38th Int’l Conf.on Software Engineering.New York:ACM Press,2016.911-922.[doi:10.1145/2884781.2884784]
[3]Jung C,Lee S,Raman E,Pande S.Automated memory leak detection for production use.In:Proc.of the 36th Int’l Conf.on Software Engineering.New York:ACM Press,2014.825-836.[doi:10.1145/2568225.2568311]
[4]Omega:An instant leak detector tool for valgrind.2018.http://www.brainmurders.eclipse.co.uk/omega.html
[5]Hastings R,Joyce B.Purify:Fast detection of memory leaks and access errors.In:Proc.of the Winter USENIX Conf.Berkeley:Usenix Association,1992.125-138.
[6]Nethercote N,Seward J.Valgrind:A framework for heavyweight dynamic binary instrumentation.ACM SIGPLAN Notices,2007,42(6):89-100.[doi:10.1145/1273442.1250746]
[7]Cherem S,Princehouse L,Rugina R.Practical memory leak detection using guarded value-flow analysis.ACM SIGPLAN Notices,2007,42(6):480-491.[doi:10.1145/1273442.1250789]
[8]Sui Y,Ye D,Xue J.Static memory leak detection using full-sparse value-flow analysis.In:Proc.of the 2012 Int’l Symp.on Software Testing and Analysis.New York:ACM Press,2012.254-264.[doi:10.1145/2338965.2336784]
[9]Sui Y,Ye D,Xue J.Detecting memory leaks statically with full-sparse value-flow analysis.IEEE Trans.on Software Engineering,2014,40(2):107-122.[doi:10.1109/TSE.2014.2302311]
[10]Orlovich M,Rugina R.Memory leak analysis by contradiction.In:Proc.of the 13th Int’l Conf.on Static Analysis.Berlin,Heidelberg:Springer-Verlag,2006.405-424.[doi:10.1007/11823230_26]
[11]Ji X,Yang J,Xu J,Feng L,Li X.Interprocedural path-sensitive resource leaks detection for C programs.In:Proc.of the 4th AsiaPacific Symp.on Internetware.New York:ACM Press,2012.1-9.[doi:10.1145/2430475.2430494]
[12]Heine DL,Lam MS.Static detection of leaks in polymorphic containers.In:Proc.of the 28th Int’l Conf.on Software Engineering.New York:ACM Press,2006.252-261.[doi:10.1145/1134285.1134321]
[13]HP fortify.2018.http://www.fortify.net/intro.html
[14]Coverity.The coverity static analysis tools.2018.http://www.coverity.com/
[15]Klocwork.The Klocwork static analysis tool.2018.http://www.klocwork.com/
[16]Steffen B,Knoop J,Rüthing O.The value flow graph:A program representation for optimal program transformations.In:Proc.of the 3rd European Symp.on Programming.Berlin,Heidelberg:Springer-Verlag,1990.389-405.[doi:10.1007/3-540-52592-0_76]
[17]Cortes C,Vapnik V.Support-vector networks.Machine Learning,1995,20(3):273-297.
[18]Breiman L.Random forests.Machine Learning,2001,45(1):5-32.
[19]Safavian SR,Landgrebe D.A survey of decision tree classifier methodology.IEEE Trans.on Systems,Man,and Cybernetics,1991,21(3):660-674.[doi:10.1109/21.97458]
[20]Yan H,Sui Y,Chen S,Xue J.Machine-learning-guided typestate analysis for static use-after-free detection.In:Proc.of the 33rd Annual Computer Security Applications Conf.New York:ACM Press,2017.42-54.[doi:10.1145/3134600.3134620]
[21]Keerthi SS,Lin CJ.Asymptotic behaviors of support vector machines with Gaussian kernel.Neural Computation,2003,15(7):1667-1689.[doi:10.1162/089976603321891855]
[22]LIBSVM-A library for support vector machines.2018.https://www.csie.ntu.edu.tw/~cjlin/libsvm/
[23]Weka.2018.http://www.cs.waikato.ac.nz/~ml/weka/
[24]Siemens.2018.http://sir.unl.edu/
[25]SPEC:Standard performance evaluation corporation.2018.http://www.spec.org
[26]Cai C,Zhang Q,Zuo Z,Nguyen K,Xu G,Su Z.Calling-to-reference context translation via constraint-guided CFL-reachability.In:Proc.of the 39th ACM SIGPLAN Conf.on Programming Language Design and Implementation.New York:ACM Press,2018.196-210.[doi:10.1145/3192366.3192378]
[27]Gao Q,Xiong Y,Mi Y,Zhang L,Yang W,Zhou Z,Xie B,Mei H.Safe memory-leak fixing for C programs.In:Proc.of the 37th Int’l Conf.on Software Engineering,Vol.1.Piscataway:IEEE Press,2015.459-470.[doi:10.1109/ICSE.2015.64]
[28]Yan H,Sui Y,Chen S,Xue J.AutoFix:An automated approach to memory leak fixing on value-flow slices for C programs.ACMSIGAPP Applied Computing Review,2017,16(4):38-50.[doi:10.1145/3040575.3040579]
[29]Alatwi HA,Oh T,Fokoue E,et al.Android malware detection using category-based machine learning classifiers.In:Proc.of the17th Annual Conf.on Information Technology Education.New York:ACM Press,2016.54-59.[doi:10.1145/2978192.2978218]
[30]Nagano Y,Uda R.Static analysis with paragraph vector for malware detection.In:Proc.of the 11th Int’l Conf.on Ubiquitous Information.New York:ACM Press,2017.1-7.[doi:10.1145/3022227.3022306]
[31]Grieco G,Grinblat GL,Uzal L,et al.Toward large-scale vulnerability discovery using machine learning.In:Proc.of the 6th ACMConf.on Data and Application Security and Privacy.New York:ACM Press,2016.85-96.[doi:10.1145/2857705.2857720]
[2]Liu T,Curtsinger C,Berger ED.DoubleTake:Fast and precise error detection via evidence-based dynamic analysis.In:Proc.of the38th Int’l Conf.on Software Engineering.New York:ACM Press,2016.911-922.[doi:10.1145/2884781.2884784]
[3]Jung C,Lee S,Raman E,Pande S.Automated memory leak detection for production use.In:Proc.of the 36th Int’l Conf.on Software Engineering.New York:ACM Press,2014.825-836.[doi:10.1145/2568225.2568311]
[4]Omega:An instant leak detector tool for valgrind.2018.http://www.brainmurders.eclipse.co.uk/omega.html
[5]Hastings R,Joyce B.Purify:Fast detection of memory leaks and access errors.In:Proc.of the Winter USENIX Conf.Berkeley:Usenix Association,1992.125-138.
[6]Nethercote N,Seward J.Valgrind:A framework for heavyweight dynamic binary instrumentation.ACM SIGPLAN Notices,2007,42(6):89-100.[doi:10.1145/1273442.1250746]
[7]Cherem S,Princehouse L,Rugina R.Practical memory leak detection using guarded value-flow analysis.ACM SIGPLAN Notices,2007,42(6):480-491.[doi:10.1145/1273442.1250789]
[8]Sui Y,Ye D,Xue J.Static memory leak detection using full-sparse value-flow analysis.In:Proc.of the 2012 Int’l Symp.on Software Testing and Analysis.New York:ACM Press,2012.254-264.[doi:10.1145/2338965.2336784]
[9]Sui Y,Ye D,Xue J.Detecting memory leaks statically with full-sparse value-flow analysis.IEEE Trans.on Software Engineering,2014,40(2):107-122.[doi:10.1109/TSE.2014.2302311]
[10]Orlovich M,Rugina R.Memory leak analysis by contradiction.In:Proc.of the 13th Int’l Conf.on Static Analysis.Berlin,Heidelberg:Springer-Verlag,2006.405-424.[doi:10.1007/11823230_26]
[11]Ji X,Yang J,Xu J,Feng L,Li X.Interprocedural path-sensitive resource leaks detection for C programs.In:Proc.of the 4th AsiaPacific Symp.on Internetware.New York:ACM Press,2012.1-9.[doi:10.1145/2430475.2430494]
[12]Heine DL,Lam MS.Static detection of leaks in polymorphic containers.In:Proc.of the 28th Int’l Conf.on Software Engineering.New York:ACM Press,2006.252-261.[doi:10.1145/1134285.1134321]
[13]HP fortify.2018.http://www.fortify.net/intro.html
[14]Coverity.The coverity static analysis tools.2018.http://www.coverity.com/
[15]Klocwork.The Klocwork static analysis tool.2018.http://www.klocwork.com/
[16]Steffen B,Knoop J,Rüthing O.The value flow graph:A program representation for optimal program transformations.In:Proc.of the 3rd European Symp.on Programming.Berlin,Heidelberg:Springer-Verlag,1990.389-405.[doi:10.1007/3-540-52592-0_76]
[17]Cortes C,Vapnik V.Support-vector networks.Machine Learning,1995,20(3):273-297.
[18]Breiman L.Random forests.Machine Learning,2001,45(1):5-32.
[19]Safavian SR,Landgrebe D.A survey of decision tree classifier methodology.IEEE Trans.on Systems,Man,and Cybernetics,1991,21(3):660-674.[doi:10.1109/21.97458]
[20]Yan H,Sui Y,Chen S,Xue J.Machine-learning-guided typestate analysis for static use-after-free detection.In:Proc.of the 33rd Annual Computer Security Applications Conf.New York:ACM Press,2017.42-54.[doi:10.1145/3134600.3134620]
[21]Keerthi SS,Lin CJ.Asymptotic behaviors of support vector machines with Gaussian kernel.Neural Computation,2003,15(7):1667-1689.[doi:10.1162/089976603321891855]
[22]LIBSVM-A library for support vector machines.2018.https://www.csie.ntu.edu.tw/~cjlin/libsvm/
[23]Weka.2018.http://www.cs.waikato.ac.nz/~ml/weka/
[24]Siemens.2018.http://sir.unl.edu/
[25]SPEC:Standard performance evaluation corporation.2018.http://www.spec.org
[26]Cai C,Zhang Q,Zuo Z,Nguyen K,Xu G,Su Z.Calling-to-reference context translation via constraint-guided CFL-reachability.In:Proc.of the 39th ACM SIGPLAN Conf.on Programming Language Design and Implementation.New York:ACM Press,2018.196-210.[doi:10.1145/3192366.3192378]
[27]Gao Q,Xiong Y,Mi Y,Zhang L,Yang W,Zhou Z,Xie B,Mei H.Safe memory-leak fixing for C programs.In:Proc.of the 37th Int’l Conf.on Software Engineering,Vol.1.Piscataway:IEEE Press,2015.459-470.[doi:10.1109/ICSE.2015.64]
[28]Yan H,Sui Y,Chen S,Xue J.AutoFix:An automated approach to memory leak fixing on value-flow slices for C programs.ACMSIGAPP Applied Computing Review,2017,16(4):38-50.[doi:10.1145/3040575.3040579]
[29]Alatwi HA,Oh T,Fokoue E,et al.Android malware detection using category-based machine learning classifiers.In:Proc.of the17th Annual Conf.on Information Technology Education.New York:ACM Press,2016.54-59.[doi:10.1145/2978192.2978218]
[30]Nagano Y,Uda R.Static analysis with paragraph vector for malware detection.In:Proc.of the 11th Int’l Conf.on Ubiquitous Information.New York:ACM Press,2017.1-7.[doi:10.1145/3022227.3022306]
[31]Grieco G,Grinblat GL,Uzal L,et al.Toward large-scale vulnerability discovery using machine learning.In:Proc.of the 6th ACMConf.on Data and Application Security and Privacy.New York:ACM Press,2016.85-96.[doi:10.1145/2857705.2857720]
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |