Towards systematic and dynamic task allocation for collaborative parallel fuzzing

• Main Authors: Pham, Van-Thuan, Nguyen, Manh-Dung, Ta, Quang-Trung, Murray, Toby, Rubinstein, Benjamin I. P.
• Format: Conference Proceeding
• Language: English
• Subjects: Codes; Computer bugs; Dynamic scheduling; Fuzzing; Heuristic algorithms; Parallel Fuzzing; Partitioning algorithms; Software and its engineering; Software and its engineering > Software creation and management; Software and its engineering > Software creation and management > Software verification and validation; Software and its engineering > Software creation and management > Software verification and validation > Software defect analysis; Software and its engineering > Software creation and management > Software verification and validation > Software defect analysis > Software testing and debugging; Systematics; Vulnerability Discovery
• ISSN: 2643-1572
• DOI: 10.1109/ASE51524.2021.9678810

Parallel coverage-guided greybox fuzzing is the most common setup for vulnerability discovery at scale. However, so far it has received little attention from the research community compared to single-mode fuzzing, leaving open several problems particularly in its task allocation strategies. Current approaches focus on managing micro tasks, at the seed input level, and their task division algorithms are either ad-hoc or static. In this paper, we leverage research on graph partitioning and search algorithms to propose a systematic and dynamic task allocation solution that works at the macro-task level. First, we design an attributed graph to capture both the program structures (e.g., program call graph) and fuzzing information (e.g., branch hit counts, bug discovery probability). Second, our graph partitioning algorithm divides the global program search space into sub-search-spaces. Finally our search algorithm prioritizes these sub-search-spaces (i.e., tasks) and explores them to maximize code coverage and number of bugs found. The results are collected to update the graph and guide further iterations of partitioning and exploration. We implemented a prototype tool called AFLTeam. In our preliminary experiments on well-tested benchmarks, AFLTeam achieved higher code coverage (up to 16.4% branch coverage improvement) compared to the default parallel mode of AFL and discovered 2 zero-day bugs in FFmpeg and JasPer toolkits.