OTA: An Operation-oriented Time Allocation Strategy for Greybox Fuzzing

Coverage-based greybox fuzzing (CGF) has been widely studied and commonly used for software vulnerability detection. Existing CGF fuzzers fairly allocate execution time for each mutation operation to generate test cases. However, the fair-time-allocation strategy is revealed to be inefficient by our significant experimental observation that different operations have heterogeneous effectiveness on coverage. Those ineffective operations with vast test cases thus occupy the majority of limited runtime, reducing the opportunities for effective operations to explore more paths and find potential vulnerabilities. In this paper, we propose a novel operation-oriented time allocation strategy OTA, which dynamically allocates operation execution time in real time to cope with the effectiveness variation per operation. OTA has three distinguishing advantages: (1) the execution time per operation is novelly initialized on demand and program-dependent; (2) the execution time for each operation is dynamically weighted by its real-time effectiveness on exploring new coverage; (3) the determination of the execution time per operation is well controlled to achieve a quick convergence. Extensive experiments based on real-world programs and the LAVA-M dataset have been conducted to evaluate the path discovery and vulnerability detection abilities of OTA, which substantially outperforms 5 state-of-the-art fuzzers. In addition, OTA exposes 18 previously unknown vulnerabilities in 6 well-tested programs with 13 confirmed with new CVE IDs.