BSFuzz: Branch-State Guided Hybrid Fuzzing

Hybrid fuzzing is an automated software testing approach that synchronizes test cases between the fuzzer and the concolic executor to improve performance. The concolic executor solves path constraints to direct the fuzzer to explore the uncovered path. Despite many performance optimizations for hybrid fuzzing, we observe that the concolic executor often repeatedly performs constraint solving on branches with unsolvable constraints and branches covered by multiple test cases. This can cause significant computational redundancies. To be efficient, we propose BSFuzz, which keeps tracking the coverage state and solving state in a lightweight branch state map. BSFuzz synchronizes the current coverage state of all test cases from the fuzzer's queue with the concolic executor in a timely manner to reduce constraint solving for high-frequency branches. It also records the branch-solving state during the concolic execution to reduce repeated solving of unsolvable branches. Guided by the coverage state and historical solving state, BSFuzz can efficiently discover and solve more branches. The experimental results with real-world programs demonstrate that BSFuzz can effectively increase the speed of the concolic executor and improve branch coverage.