基于遗传算法的二进制程序模糊测试方法

Fuzz testing for binary program based on genetic algorithm

针对当前二进制程序模糊测试中基于变异生成的测试数据的执行路径重复率高导致代码覆盖率低的问题,提出基于遗传算法的二进制程序模糊测试方法.该方法将测试数据转换为遗传算法中的个体,利用Quick Emulator对二进制程序进行插桩以获取程序执行路径,使用基于程序执行路径的适应度函数指导遗传算法中的进化过程,使生成的测试数据能够覆盖更多的程序执行路径.实验结果表明,该方法在相同时间内达到的代码覆盖率平均比模糊测试工具American Fuzzy Lop(AFL)高25.4%.同时,该方法在漏洞挖掘实验中发现了测试程序中的所有崩溃漏洞并且其效率至少比AFL提高10%.该方法能够用于提高模糊测试的漏洞挖掘效率.

A genetic algorithm-based fuzz testing method for binary program was proposed aiming at the low code coverage problem caused by high execution path repetition rate of the test data generated from mutation in binary program fuzz testing.The method transformed test data to individuals in genetic algorithm.Quick Emulator was used to instrument a binary program for extracting program execution path.The evolution process in genetic algorithm was guided by an execution-path-based fitness function,so that the generated test data could cover more program execution paths.Experimental results show that the average code coverage of the method is 25.4% higher than fuzzing tool American Fuzzy Lop（AFL）within the same time.The method can detect all crashes in vulnerability detection experiment and the efficiency is at least 10% higher than AFL.The method is helpful for improving the efficiency of fuzz testing.