This is an archive of the discontinued LLVM Phabricator instance.

Add graph centrality based seed scheduler: K-Scheduler (IEEE S&P22) for LibFuzzer.
Needs ReviewPublic

Authored by Dongdongshe on Jun 8 2022, 1:09 PM.

Details

Summary

K-Scheduler is a novel seed scheduler for LibFuzzer which can greatly improve LibFuzzer performance over the default seed scheduler entropic.
IEEE S&P 2022 paper link: https://arxiv.org/abs/2203.12064
Github repo: https://github.com/Dongdongshe/K-Scheduler
Intuition behind: Good seeds can reach more number of unvisited nodes and bad seeds can reach fewer number of unvisited nodes.
General idea: We approximate the potential code coverage gain (i.e., the number of reachable and unvisited nodes) for each seed using graph centrality scores. Then, we prioritize the seed with higher potential code coverage gain.
One minute video explanation: https://www.youtube.com/watch?v=VVZZpQiIsm4
Our original implementation is on llvm-11.0.1. We port K-Scheduler to llvm-14.0.0 and evaluate it on 8 programs. The results show consistent improvement as llvm-11.0.1.
Please check our evaluation result plot over 24 hours for 10 runs and corresponding reproduction package (including binaries and seed corpus) at https://github.com/Dongdongshe/K-Scheduler_llvm14_Benchmark

Diff Detail

Event Timeline

Dongdongshe created this revision.Jun 8 2022, 1:09 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 8 2022, 1:09 PM
Herald added a subscriber: Enna1. · View Herald Transcript

Add a graph centrality-based seed scheduler (K-Scheduler, IEEE S&P22) for LibFuzzer to improve fuzzing performance.

K-Scheduler: a novel seed scheduler for LibFuzzer which can greatly improve LibFuzzer performance over the default seed scheduler entropic.
IEEE S&P 2022 paper link: https://arxiv.org/abs/2203.12064
Github repo: https://github.com/Dongdongshe/K-Scheduler
Intuition behind: Good seeds can reach more number of unvisited nodes and bad seeds can reach fewer number of unvisited nodes.
General idea: We approximate the potential code coverage gain (i.e., the number of reachable and unvisited nodes) for each seed through the graph centrality scores. Then, we prioritize the seed with higher potential code coverage gain.
One minute video explanation: https://www.youtube.com/watch?v=VVZZpQiIsm4
Our original implementation is on llvm-11.0.1. We port K-Scheduler to llvm-14.0.0 and evaluate it on 8 programs. The results show consistent improvement as llvm-11.0.1.
Please check our evaluation result plot over 24 hours for 10 runs and corresponding reproduction package (including binaries and seed corpus) at https://github.com/Dongdongshe/K-Scheduler_llvm14_Benchmark

Dongdongshe edited the summary of this revision. (Show Details)Jun 10 2022, 9:13 PM

K-Scheduler is a novel seed scheduler for LibFuzzer which can greatly improve LibFuzzer performance over the default seed scheduler entropic.
IEEE S&P 2022 paper link: https://arxiv.org/abs/2203.12064
Github repo: https://github.com/Dongdongshe/K-Scheduler
Intuition behind: Good seeds can reach more number of unvisited nodes and bad seeds can reach fewer number of unvisited nodes.
General idea: We approximate the potential code coverage gain (i.e., the number of reachable and unvisited nodes) for each seed using graph centrality scores. Then, we prioritize the seed with higher potential code coverage gain.
One minute video explanation: https://www.youtube.com/watch?v=VVZZpQiIsm4
Our original implementation is on llvm-11.0.1. We port K-Scheduler to llvm-14.0.0 and evaluate it on 8 programs. The results show consistent improvement as llvm-11.0.1.
Please check our evaluation result plot over 24 hours for 10 runs and corresponding reproduction package (including binaries and seed corpus) at https://github.com/Dongdongshe/K-Scheduler_llvm14_Benchmark

Dongdongshe published this revision for review.Jun 10 2022, 9:24 PM
Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptJun 10 2022, 9:24 PM
Herald added subscribers: llvm-commits, Restricted Project. · View Herald Transcript
Dongdongshe retitled this revision from Add graph centrality based seed scheduler: K-Scheduler (IEEE S&P22). to Add graph centrality based seed scheduler: K-Scheduler (IEEE S&P22) for LibFuzzer..Jun 19 2022, 4:43 PM

Ping