Taint analysis significantly enhances the capacity of fuzzing to navigate intricate constraints and delve into the state spaces of the target program. However, practical scenarios involving taint analysis-assisted fuzzers with the common parallel mode still have limitations in terms of overall throughput. These limitations primarily stem from redundant taint analyses and mutations among different fuzzer instances. In this paper, we propose Dodrio, a framework that parallelizes taint analysis based fuzzing. The main idea is to schedule fuzzing tasks in a balanced way by exploiting real-time global state, thereby minimizing redundancy and enabling all instances to function as a cohesive unit. It consists of two modules: real-time synchronization and load-balanced task dispatch. Real-time synchronization updates global states among all instances by utilizing dual global coverage bitmaps to reduce data race. Based on the global state, load-balanced task dispatch efficiently allocates different tasks to different instances, thereby minimizing redundant behaviors and maximizing the utilization of computing resources.

We evaluated Dodrio on real-world programs both in Google’s fuzzer-test-suite and FuzzBench against AFL’s classical parallel mode, PAFL, and Ye’s PAFL on parallelizing two taint analysis based fuzzer FairFuzz and PATA. The results show that Dodrio achieved an average speedup of 123%–398% in covering basic blocks in 24-hour fuzzing compared to others. Based on the speedup, Dodrio found 5%–16% more basic blocks. We also assessed the scalability of Dodrio. With the same resources, the coverage improvement increases from 4% to 35% when the number of instances in parallel (i.e., CPU cores) increases from 4 to 64, compared to the classical parallel mode.