BSP: Branch Splitting for Unsolvable Path Hybrid Fuzzing

Hybrid fuzzing leverages the result of the concolic executor for a direct exploration of fuzzing, which has been proven to improve coverage during tests significantly.However, some constraints, such as those related to environments or depending on the host’s status, cannot be solved. Despite many performance optimizations on hybrid fuzzing, we observe that repeatedly constraint solving on unsolvable branches causes significant computational redundancies. This paper focuses on eliminating the unsolvable branches in concolic execution. We propose Branch Splitting for Unsolvable Path Hybrid Fuzzing (BSP), which splits unsolvable branches to achieve higher fuzzing coverage. BSP modifies the target program during concolic execution so that the fuzzer can easily cover initially unsolvable branches. Specifically, it changes the condition of unsolvable branches to constant True (or False), which generates multiple variants of the original program. Then, the fuzzer tests these variants instead. This allows BSP to explore more branches with high performance. The experimental results on real-world programs demonstrate that BSP can explore 46.68% more branches than QSYM.