Probabilistic Path Prioritization for Hybrid Fuzzing

Hybrid fuzzing that combines fuzzing and concolic execution has become an advanced technique for software vulnerability detection. Based on the observation that fuzzing and concolic execution are complementary in nature, state-of-the-art hybrid fuzzing systems deploy “optimal concolic testing” and “demand launch” strategies. Although these ideas sound intriguing, we point out several fundamental limitations in them, due to oversimplified assumptions. Further, we propose a novel “discriminative dispatch” strategy and design a probabilistic hybrid fuzzing system to better utilize the capability of concolic execution. In details, we design a Monte Carlo based probabilistic path prioritization model to quantify each path's difficulty and prioritize them for concolic execution. This model treats fuzzing as a random sampling process and calculates each path's probability based on the sampling information. Finally, our model prioritizes and assigns the most difficult paths to concolic execution. We implement a prototype system DigFuzz and evaluate it with two representative datasets and real-world programs. Results show that the concolic execution in DigFuzz outperforms than those in state-of-the-art hybrid fuzzing systems in every major aspect. In particular, the concolic execution in DigFuzz contributes to discovering more vulnerabilities and producing more code coverage on the CQE dataset than the concolic execution in Driller.