基於滯留點分類增進並行模糊測試效率

並行模糊測試 (Parallel Fuzzing) 透過同時執行多個模糊測試實例,並實作種子 (能夠增加程式碼覆蓋率的輸入) 同步機制,使不同的模糊測試實例能夠分享彼此產生出的種子,以硬體支援的方式增加模糊測試的效率。本論文基於 EnFuzz 的研究基礎,闡述整合多種類型的模糊測試工具 (Fuzzer) 時可能會遭遇到的兩個問題以及對應的解決方法。EnFuzz 基於並行模糊測試的概念整合多種類型的模糊測試工具,藉以增加通過一系列複雜條件判斷式的機率。然而,我們發現 EnFuzz 因為無法辨別模糊測試工具對於複雜條件判斷式通過狀況的傾向,所以必須隨時並行地執行所有被整合的模糊測試工具,此舉將會產生 1. 對條件判斷式使用不適當的模糊測試工具、2. 繁冗的變異,這兩種現象均會在模糊測試的過程中造成計算資源的浪費。因此,我們提出兩種可緩和此種現象的方法:1. 基於滯留點 (在模糊測試的過程中,需要較多時間才能被通過的條件判斷式) 分類對模糊測試工具作排序、2. 刪減模糊測試種子佇列。實驗結果顯示,在根據滯留點分類對模糊測試工具作排序的部份,我們對 re2 及 Json 進行四小時的模糊測試,可分別改善 14% 及 11% 的效能,在刪減模糊測試種子佇列的部份,相較於其他模糊測試工具,我們平均增加了 4% 的覆蓋率。這些改善使得在並行模糊測試的過程中動態分配計算資源成為可能。

關鍵字

並行模糊測試；種子同步機制；整合式模糊測試工具；基本塊分類；佇列刪減

並列摘要

Parallel fuzzing runs multiple fuzzing instances simultaneously and implements a mechanism to synchronize seeds (input that will gain code coverage) among them. As different fuzzing instances can share the seeds generated by each other, parallel fuzzing increases the efficiency of fuzzing via hardware support. Based on the research of EnFuzz, this paper identifies two problems that might be encountered when we integrate various types of fuzzers. EnFuzz integrates various types of fuzzers based on the concept of parallel fuzzing to increase the probability of passing a series of complex comparison instructions. However, we found that since EnFuzz does not identify the tendency of each fuzzer to pass a complex comparison instruction, all integrated fuzzers must be executed in parallel during the entire fuzzing process, which will result in 1. using inappropriate fuzzers for comparison instructions, and 2. redundant mutations, both wasting computing resources in the fuzzing process. Therefore, we propose two methods to mitigate this phenomenon: 1. ranking fuzzers for each stuck edge (comparison instructions that require long time to be passed during the fuzzing process) based on stuck-edge classification, and 2. trimming seed queue of fuzzing. The experiment results show that we can achieve good accuracy in ranking fuzzers for each stuck edge, which improves performance by 14% and 11% in the four-hour fuzzing process of re2 and Json respectively. In trimming seed queue of fuzzing, we have an average 4% increase in code coverage compared to other fuzzers. Our enhancements make it possible to dynamically allocate computing resources during parallel fuzzing.

並列關鍵字

parallel fuzzing ； seed synchronization mechanism ； integrated fuzzer ； basic block classification ； queue trimming

參考文獻

[1] american fuzzy lop - a securityoriented fuzzer. https://lcamtuf.coredump.cx/afl/.

Google Scholar

[2] C. Lemieux and K. Sen. FairFuzz: A Targeted Mutation Strategy for Increasing Greybox Fuzz Testing Coverage. ASE ’18: Proceedings of the 2018 33rd ACM/IEEE International Conference on Automated Software Engineering, pages 475–485, 2018.