A Novel Coverage-guided Greybox Fuzzing based on Power Schedule Optimization with Time Complexity

Abstract

Coverage-guided Greybox fuzzing is regarded as a practical approach to detect software vulnerabilities, which targets to expand code coverage as much as possible. A common implementation is to assign more energy to such seeds which find new edges with less execution time. However, solely considering new edges may be less effective because some hard-to-find branches often exist in the complex code of program. Code complexity is one of the key indicators to measure the code security. Compared to the code with simple structure, the program with higher code complexity is more likely to find more branches and cause security problems. In this paper, we propose a novel fuzzing method which further uses code complexity to optimize power schedule process in AFL (American Fuzzy Lop) and AFLFAST (American Fuzzy Lop Fast). The goal of our method is to generate inputs which are more biased toward the code with higher complexity of the program under test. In addition, we conduct a preliminary empirical study under three widely used real-world programs, and the experimental results show that the proposed approach can trigger more crashes as well as improve the coverage discovery.