Context-Free Property Oriented Fuzzing

Fuzzing is effective for finding software bugs. However, the bugs specified in context-free properties are difficult for the existing fuzzers. These bugs are triggered when the program execution contains specific sequences of operations, e.g., push and pop operations on the stack, and locking and unlocking operations on the lock. As far as we know, existing approaches do not support fuzzing for non-regular context-free properties, which are more expressive and can be used to specify bugs in many scenarios.

This paper proposes a general runtime monitoring-based fuzzing framework for the bugs expressed as context-free properties. We propose two algorithms to improve fuzzing's effectiveness and efficiency with respect to the context-free property. The algorithm for preserving input mutants leverages the state transition information of the property's monitors. The other algorithm for mutating the input seed combines control flow information with state transition information to prioritize the different parts of the input. We have implemented our framework CFPOFuzz for C/C++ programs. The results of the extensive experiments on real-world C/C++ programs indicate our method's effectiveness and efficiency. Compared with coverage-oriented fuzzing, our method achieves 3.83x speedups for