关键词: AFL, 多摇臂赌博机, 探索-利用, 汤普森采样

Abstract:

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 AFL-EE 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.

Key words: AFL, multi-armed bandit, exploration-exploitation, thompson sampling