基于探索-利用模型优化AFL变异的方法
|
摘要
模糊测试是通过不断生成不同的输入来测试程序从而发现并识别安全漏洞,已经广泛应用于漏洞挖掘中。目前灰盒模糊测试是最流行的模糊测试策略,它将轻量级代码插桩与数据反馈驱动相结合,以生成新的程序输入。AFL(American Fuzzy Lop)是一种卓越的灰盒模糊测试工具,其以高效的forkserver执行、可靠的遗传算法和多种的变异策略著称,但其变异策略主要采样随机变异,存在较大的盲目性。文章提出了一种运用强化学习的方法来优化变异的策略,以多摇臂赌博机问题为模型,记录不同变异方式产生的输入在目标程序中的执行效果,利用探索-利用算法自适应地学习变异操作结果的概率分布情况,智能地进行变异操作策略调整,提升AFL的模糊测试性能。文章选择汤普森采样为优化算法设计实现了AFL-EE模糊测试工具,并对5类常用的文件类程序进行了验证测试,实验表明该方法能自动调整变异操作策略,有效地产生覆盖率高的测试输入,方法可行、额外资源消耗较小,总体上优于AFL工具。
Fuzzing is to detect and identify security vulnerabilities by generating different input continuously. It has been widely used in vulnerability discovery. At present, gray-box fuzzy testing is the most popular fuzzing strategy. It combines lightweight code instrumentation with data feedback driver to generate new program input. AFL is an excellent grey-box fuzzing test tool. It is famous for its efficient forkserver execution, reliable genetic algorithm and a variety of mutation strategies. However, its mutation strategy mainly sampled random mutation, which has great blindness. In this paper, a method of reinforcement learning is proposed to optimize mutation strategy. Taking Multi-Armed Bandit problem as a model, the execution effect of input generated by different mutation modes in the target program is recorded. The probabilistic distribution of mutation operation results is adaptively learned byExploration-Exploitation algorithm, and mutation operation strategy is intelligently adjusted to improve the fuzzing performance of AFL. According to the above principles, Thompson sampling is chosen as the optimization algorithm to design and implement AFLEE fuzzing tool. Five kinds of common file programs are tested and verified. Experiments show that the method can automatically adjust the mutation operation strategy and effectively generate test input with high coverage. The method is feasible and has less additional resource consumption. It is superior to the original AFL in general.
Fuzzing is to detect and identify security vulnerabilities by generating different input continuously. It has been widely used in vulnerability discovery. At present, gray-box fuzzy testing is the most popular fuzzing strategy. It combines lightweight code instrumentation with data feedback driver to generate new program input. AFL is an excellent grey-box fuzzing test tool. It is famous for its efficient forkserver execution, reliable genetic algorithm and a variety of mutation strategies. However, its mutation strategy mainly sampled random mutation, which has great blindness. In this paper, a method of reinforcement learning is proposed to optimize mutation strategy. Taking Multi-Armed Bandit problem as a model, the execution effect of input generated by different mutation modes in the target program is recorded. The probabilistic distribution of mutation operation results is adaptively learned byExploration-Exploitation algorithm, and mutation operation strategy is intelligently adjusted to improve the fuzzing performance of AFL. According to the above principles, Thompson sampling is chosen as the optimization algorithm to design and implement AFLEE fuzzing tool. Five kinds of common file programs are tested and verified. Experiments show that the method can automatically adjust the mutation operation strategy and effectively generate test input with high coverage. The method is feasible and has less additional resource consumption. It is superior to the original AFL in general.
引文
[1] SHI ji, ZENG Zhaolong, YANG Congbao, et al. Fuzzingtest Technology Overview[J]. Netinfo Security, 2014, 14(3):87-91.史记,曾昭龙,杨从保,等.Fuzzing测试技术综述[J].信息网络安全,2014,14(3):87-91.
[2] ZHANG Xiong, LI Zhoujun. Overview of Fuzzing Test Technology[J].Computer Science, 2016, 43(5):1-8, 26.张雄,李舟军.模糊测试技术研究综述[J].计算机科学,2016,43(5):1-8,26.
[3] FENG Jizhou, TIAN Minghui. Research and Consideration of Software Potential Security Defect Test Cases[J]. Netinfo Security, 2015,15(6):85-90.冯济舟,田明辉.软件潜在安全性缺陷测试案例的研究及思考[J].信息网络安全,2015,15(6):85-90.
[4] ZOU Quanchen, ZHANG Tao, WU Runpu, et al. From Automation to Intelligence:Advances in Software Vulnerability Mining Technology[J]. Journal of Tsinghua University(Natural Science Edition),2018, 58(12):1079-1094.邹权臣,张涛,吴润浦,等.从自动化到智能化:软件漏洞挖掘技术进展[J].清华大学学报(自然科学版),2018,58(12):1079-1094.
[5] ZHANG Lei, CUI Yong, LIU Jing, et al. Application of Machine Learning in Cyberspace Security Research[J]. Journal of Computer Science, 2018, 41(9):1943-1975.张蕾,崔勇,刘静,等.机器学习在网络空间安全研究中的应用[J].计算机学报,2018,41(9):1943-1975.
[6] WANG Xiaqing, HU Changzhen, MA Rui, et al. A Review of Key Technologies of Binary Program Vulnerability Mining[J].Netinfo Security, 2017, 17(8):1-13.王夏菁,胡昌振,马锐,等.二进制程序漏洞挖掘关键技术研究综述[J].信息网络安全,2017,17(8):1-13.
[7] LI Tong, HUANG Xuan, HUANG Rui. Test Case Generation Method in Fuzzing Test[J]. Computer System Application, 2015, 24(4):139-143.李彤,黄轩,黄睿.模糊测试中测试用例生成方法[J].计算机系统应用,2015,24(4):139-143.
[8] B?HME M, PHAM V T, NGUYEN M D, et al. Directed Greybox Fuzzing[C]//ACM. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, October30-November 3, 2017, Dallas, Texas, USA. New York:ACM, 2017:2329-2344.
[9] GODEFROID P, LEVIN M Y, MOLNAR D A. Automated Whitebox Fuzz Testing[EB/OL]. https://www.eecs.northwestern.edu/~robby/courses/395-495-2017-winter/ndss2008.pdf, 2008-7-15.
[10] GODEFROID P, LEVIN M Y, MOLNAR D. SAGE:Whitebox Fuzzing for Security Testing[J]. Communications of the ACM, 2012,55(3):40-44.
[11] HUGO Gascon, CHRISTIAN W, FABIAN Y, et al. Pulsar:Stateful Black-Box Fuzzing of Proprietary Network Protocols[C]//Spring. 11th EAI International Conference, SecureComm 2015, October 26-29, 2015,Dallas, TX, USA. Berlin:Spring, 2015:330-347.
[12] YAN Fei. Research on Web Application Vulnerability Mining Based on Genetic Algorithms and Fuzzing Technology[J]. Information Communication, 2018, 18(9):61-62.闫飞.基于遗传算法和Fuzzing技术的Web应用漏洞挖掘研究[J].信息通信,2018,18(9):61-62.
[13] MICHAL Z. AFL Technical Details[EB/OL]. http://lcamtuf.coredump.cx/afl/technical_details.txt, 2017-7-15.
[14] HO Simai, JINYujia, WANG Hua, et al. Overview of Online Learning Methods:Thompson Sampling and Other Methods[J]. Journal of Operational Research, 2017, 21(4):84-102.何斯迈,金羽佳,王华,等.在线学习方法综述:汤普森抽样和其他方法[J].运筹学学报,2017,21(4):84-102.
[15] ZHOU Zhi-Hua. Machine Learning[M]. Beijing:Tsinghua University Press, 2016(in Chinese).周志华.机器学习[M].北京:清华大学出版社,2016.
[16] CHAPELLE O, LI L. An Empirical Evaluation of Thompson Sampling[EB/OL]. http://papers.nips.cc/paper/4321-an-empiricalevaluation-of-thompson-sampling.pdf, 2011-11-5.
[17] AGRAWAL S, GOYAL N. Analysis of Thompson Sampling for the Multi-armed Bandit Problem[EB/OL]. http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf, 2012-11-5.
[18] ZHANG Yao, ZHANG Chaorong, LIN Teng, et al. Design and Implementation of Binary Code Test Coverage Evaluation System[J].Command Information System and Technology, 2015, 6(6):13-17.张垚,张超容,林腾,等.二进制代码测试覆盖率评估系统设计与实现[J].指挥信息系统与技术,2015,6(6):13-17.
[2] ZHANG Xiong, LI Zhoujun. Overview of Fuzzing Test Technology[J].Computer Science, 2016, 43(5):1-8, 26.张雄,李舟军.模糊测试技术研究综述[J].计算机科学,2016,43(5):1-8,26.
[3] FENG Jizhou, TIAN Minghui. Research and Consideration of Software Potential Security Defect Test Cases[J]. Netinfo Security, 2015,15(6):85-90.冯济舟,田明辉.软件潜在安全性缺陷测试案例的研究及思考[J].信息网络安全,2015,15(6):85-90.
[4] ZOU Quanchen, ZHANG Tao, WU Runpu, et al. From Automation to Intelligence:Advances in Software Vulnerability Mining Technology[J]. Journal of Tsinghua University(Natural Science Edition),2018, 58(12):1079-1094.邹权臣,张涛,吴润浦,等.从自动化到智能化:软件漏洞挖掘技术进展[J].清华大学学报(自然科学版),2018,58(12):1079-1094.
[5] ZHANG Lei, CUI Yong, LIU Jing, et al. Application of Machine Learning in Cyberspace Security Research[J]. Journal of Computer Science, 2018, 41(9):1943-1975.张蕾,崔勇,刘静,等.机器学习在网络空间安全研究中的应用[J].计算机学报,2018,41(9):1943-1975.
[6] WANG Xiaqing, HU Changzhen, MA Rui, et al. A Review of Key Technologies of Binary Program Vulnerability Mining[J].Netinfo Security, 2017, 17(8):1-13.王夏菁,胡昌振,马锐,等.二进制程序漏洞挖掘关键技术研究综述[J].信息网络安全,2017,17(8):1-13.
[7] LI Tong, HUANG Xuan, HUANG Rui. Test Case Generation Method in Fuzzing Test[J]. Computer System Application, 2015, 24(4):139-143.李彤,黄轩,黄睿.模糊测试中测试用例生成方法[J].计算机系统应用,2015,24(4):139-143.
[8] B?HME M, PHAM V T, NGUYEN M D, et al. Directed Greybox Fuzzing[C]//ACM. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, October30-November 3, 2017, Dallas, Texas, USA. New York:ACM, 2017:2329-2344.
[9] GODEFROID P, LEVIN M Y, MOLNAR D A. Automated Whitebox Fuzz Testing[EB/OL]. https://www.eecs.northwestern.edu/~robby/courses/395-495-2017-winter/ndss2008.pdf, 2008-7-15.
[10] GODEFROID P, LEVIN M Y, MOLNAR D. SAGE:Whitebox Fuzzing for Security Testing[J]. Communications of the ACM, 2012,55(3):40-44.
[11] HUGO Gascon, CHRISTIAN W, FABIAN Y, et al. Pulsar:Stateful Black-Box Fuzzing of Proprietary Network Protocols[C]//Spring. 11th EAI International Conference, SecureComm 2015, October 26-29, 2015,Dallas, TX, USA. Berlin:Spring, 2015:330-347.
[12] YAN Fei. Research on Web Application Vulnerability Mining Based on Genetic Algorithms and Fuzzing Technology[J]. Information Communication, 2018, 18(9):61-62.闫飞.基于遗传算法和Fuzzing技术的Web应用漏洞挖掘研究[J].信息通信,2018,18(9):61-62.
[13] MICHAL Z. AFL Technical Details[EB/OL]. http://lcamtuf.coredump.cx/afl/technical_details.txt, 2017-7-15.
[14] HO Simai, JINYujia, WANG Hua, et al. Overview of Online Learning Methods:Thompson Sampling and Other Methods[J]. Journal of Operational Research, 2017, 21(4):84-102.何斯迈,金羽佳,王华,等.在线学习方法综述:汤普森抽样和其他方法[J].运筹学学报,2017,21(4):84-102.
[15] ZHOU Zhi-Hua. Machine Learning[M]. Beijing:Tsinghua University Press, 2016(in Chinese).周志华.机器学习[M].北京:清华大学出版社,2016.
[16] CHAPELLE O, LI L. An Empirical Evaluation of Thompson Sampling[EB/OL]. http://papers.nips.cc/paper/4321-an-empiricalevaluation-of-thompson-sampling.pdf, 2011-11-5.
[17] AGRAWAL S, GOYAL N. Analysis of Thompson Sampling for the Multi-armed Bandit Problem[EB/OL]. http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf, 2012-11-5.
[18] ZHANG Yao, ZHANG Chaorong, LIN Teng, et al. Design and Implementation of Binary Code Test Coverage Evaluation System[J].Command Information System and Technology, 2015, 6(6):13-17.张垚,张超容,林腾,等.二进制代码测试覆盖率评估系统设计与实现[J].指挥信息系统与技术,2015,6(6):13-17.