Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Systematic Assessment of Fuzzers using Mutation...

Systematic Assessment of Fuzzers using Mutation Analysis

USENIX Security 2023

Rahul Gopinath

August 11, 2023
Tweet

More Decks by Rahul Gopinath

Other Decks in Research

Transcript

  1. Systematic Assessment of Fuzzers using Mutation Analysis Philipp Görz1 @[email protected]

    Björn Mathis1 @bjrnmath Keno Hassler1 Emre Güler2 @emrexgueler Thorsten Holz1 @thorstenholz Andreas Zeller1 @andreaszeller Rahul Gopinath3 @[email protected] 1 CISPA Helmholtz Center for Information Security, Germany 2 Ruhr-University Bochum, Germany 3 University of Sydney, Australia
  2. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults <Approach>

    3 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  3. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults 5

    USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  4. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    5 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  5. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ 5 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  6. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — 5 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  7. Evaluating Fuzzers - Finding New Bugs? https://www.cve.org/ 6 USENIX —

    Systematic Assessment of Fuzzers using Mutation Analysis
  8. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — 7 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  9. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs 7 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  10. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ 7 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  11. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ 7 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  12. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ 7 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  13. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — 7 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  14. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — 9 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  15. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — Known Bugs 9 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  16. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — Known Bugs ✔ 9 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  17. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — Known Bugs ✔ ✘ 9 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  18. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — Known Bugs ✔ ✘ ✘ 9 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  19. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — Known Bugs ✔ ✘ ✘ ✔ 9 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  20. Mutation Testing / Mutation Analysis Fuzzing Your Test Suite 10

    USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  21. Mutation Testing / Mutation Analysis unsigned int len = message_length(msg);

    if (len < MAX_BUF_LEN) { copy_message(msg); } else { // Invalid length , handle error } 11 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  22. Mutation Testing / Mutation Analysis ① unsigned int len =

    message_length(msg); if (len < MAX_BUF_LEN) { copy_message(msg); } else { // Invalid length , handle error } 12 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  23. Mutation Testing / Mutation Analysis ① unsigned int len =

    message_length(msg); if (len ② < >= MAX_BUF_LEN) { copy_message(msg); } else { // Invalid length , handle error } 13 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  24. Mutation Testing / Mutation Analysis ① unsigned int len =

    message_length(msg); if (len ② < >= MAX_BUF_LEN ③ + 16) { copy_message(msg); } else { // Invalid length , handle error } 14 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  25. Mutation Testing / Mutation Analysis ① unsigned int len =

    message_length(msg); if (len ② < >= MAX_BUF_LEN ③ + 16) { copy_message(msg); } else { // Invalid length , handle error } ✔
  26. Mutation Testing / Mutation Analysis ① unsigned int len =

    message_length(msg); if (len ② < >= MAX_BUF_LEN ③ + 16) { copy_message(msg); } else { // Invalid length , handle error } ✔
  27. Mutation Testing / Mutation Analysis ① unsigned int len =

    message_length(msg); if (len ② < >= MAX_BUF_LEN ③ + 16) { copy_message(msg); } else { // Invalid length , handle error } ✔ ✘
  28. Mutation Testing / Mutation Analysis ① unsigned int len =

    message_length(msg); if (len ② < >= MAX_BUF_LEN ③ + 16) { copy_message(msg); } else { // Invalid length , handle error } ✔ ✘
  29. Mutation Testing / Mutation Analysis ① unsigned int len =

    message_length(msg); if (len ② < >= MAX_BUF_LEN ③ + 16) { copy_message(msg); } else { // Invalid length , handle error } ✔ ✘ ✔
  30. Mutation Testing / Mutation Analysis ① unsigned int len =

    message_length(msg); if (len ② < >= MAX_BUF_LEN ③ + 16) { copy_message(msg); } else { // Invalid length , handle error } ✔ ✘ ✔ ? 14 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  31. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — Known Bugs ✔ ✘ ✘ ✔ 15 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  32. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — Known Bugs ✔ ✘ ✘ ✔ Mutation Testing 15 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  33. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — Known Bugs ✔ ✘ ✘ ✔ Mutation Testing ✔ 15 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  34. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — Known Bugs ✔ ✘ ✘ ✔ Mutation Testing ✔ ✔ 15 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  35. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — Known Bugs ✔ ✘ ✘ ✔ Mutation Testing ✔ ✔ ✔ 15 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  36. Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage

    ✔ — — — New Bugs ✘ ✘ ✔ — Known Bugs ✔ ✘ ✘ ✔ Mutation Testing ✔ ✔ ✔ ✘ 15 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  37. What’s the Problem? • Computationally Expensive! • Mutation Testing: Execute

    Test Generator (Fuzzer) for each Mutation 16 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  38. What’s the Problem? • Computationally Expensive! • Mutation Testing: Execute

    Test Generator (Fuzzer) for each Mutation • Fuzzing: The More Executions the Better 16 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  39. Contributions • Reduce Computational Costs • Split Phases 17 USENIX

    — Systematic Assessment of Fuzzers using Mutation Analysis
  40. Contributions • Reduce Computational Costs • Split Phases • Coverage

    Fuzzing 17 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  41. Contributions • Reduce Computational Costs • Split Phases • Coverage

    Fuzzing • Mutation Fuzzing 17 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  42. Contributions • Reduce Computational Costs • Split Phases • Coverage

    Fuzzing • Mutation Fuzzing • Supermutants 17 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  43. Contributions • Reduce Computational Costs • Split Phases • Coverage

    Fuzzing • Mutation Fuzzing • Supermutants • Evaluate Multiple Mutations with one Fuzzing Run 17 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  44. Contributions • Reduce Computational Costs • Split Phases • Coverage

    Fuzzing • Mutation Fuzzing • Supermutants • Evaluate Multiple Mutations with one Fuzzing Run • Mutation Operators 17 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  45. Contributions • Reduce Computational Costs • Split Phases • Coverage

    Fuzzing • Mutation Fuzzing • Supermutants • Evaluate Multiple Mutations with one Fuzzing Run • Mutation Operators • Traditional Operators 17 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  46. Contributions • Reduce Computational Costs • Split Phases • Coverage

    Fuzzing • Mutation Fuzzing • Supermutants • Evaluate Multiple Mutations with one Fuzzing Run • Mutation Operators • Traditional Operators • Security Specific Operators 17 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  47. Results • Coverage Accounts for most Mutants Detected 18 USENIX

    — Systematic Assessment of Fuzzers using Mutation Analysis
  48. Results • Coverage Accounts for most Mutants Detected • ASAN

    Moderately Increases Number of Killed Mutants 18 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  49. Results • Coverage Accounts for most Mutants Detected • ASAN

    Moderately Increases Number of Killed Mutants • Mutations are Coupled to Real Faults 18 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  50. Mutation Testing / Mutation Analysis Fuzzing Your Test Suite 10

    USENIX — Systematic Assessment of Fuzzers using Mutation Analysis Evaluating Fuzzers Com parable Unbiased Custom Subjects Guaranteed Faults Coverage ✔ — — — New Bugs ✘ ✘ ✔ — Known Bugs ✔ ✘ ✘ ✔ Mutation Testing ✔ ✔ ✔ ✘ 12 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis Contributions • Reduce Computational Costs • Split Phases • Coverage Fuzzing • Mutation Fuzzing • Supermutants • Evaluate Multiple Mutations with one Fuzzing Run • Mutation Operators • Traditional Operators • Security Specific Operators 14 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis Code Code is Publicly Available! Interested? Talk to Us! SBFT’24?! github.com/CISPA-SysSec/mua_fuzzer_bench 20 USENIX — Systematic Assessment of Fuzzers using Mutation Analysis
  51. Systematic Assessment of Fuzzers using Mutation Analysis Philipp Görz1 @[email protected]

    Björn Mathis1 @bjrnmath Keno Hassler1 Emre Güler2 @emrexgueler Thorsten Holz1 @thorstenholz Andreas Zeller1 @andreaszeller Rahul Gopinath3 @[email protected] 1 CISPA Helmholtz Center for Information Security, Germany 2 Ruhr-University Bochum, Germany 3 University of Sydney, Australia
  52. Compilation Procedure Mutator Base Compiler Unmutated Executable Mutated Executable Fuzzer

    Compiler Subject (bitcode file) Instrumented Mutated Exectuable Mutation Finder Location Executable Mutation IDs Mutation IDs for a Supermutant Result of Subject Result of Supermutant Supermutant (bitcode file)
  53. Checking Procedure Benchmark Manager Crashing Input Mutation killed? Seeds Unmutated

    Executable Mutated Executable Fuzzer(s) Mutation covered? Instrumented Mutated Exectuable 1. Check if Seeds (after Phase I) already kill mutation(s) 4. Check if found Crashing Input kills Mutant Run input to check that crash does not happen in unmutated executable Run input to check if crash can be confirmed 3. Fuzz using the fuzzer respective executable Run input to get covered mutations 2. Use Seeds to start Fuzzer (each Fuzzer is initialized with their respective seeds after Phase I)
  54. ASan Percentages 2.7% 24.7% 24.7% 0.0% 5.5% 21.9% 21.9% 0.0%

    5.6% 21.1% 21.1% 0.0% 16.2% 32.3% 32.3% 1.8% 16.3% 32.1% 32.1% 1.8% 18.0% 31.5% 31.5% 0.9% 7.0% 22.2% 22.2% 0.6% 7.5% 21.9% 21.9% 0.5% 7.5% 22.4% 22.4% 0.6% 6.7% 23.3% 23.3% 3.0% 7.4% 25.0% 25.0% 2.5% 7.3% 25.4% 25.4% 2.0% 12.4% 18.4% 18.4% 0.6% 12.6% 18.3% 18.3% 0.6% 12.1% 18.5% 18.5% 0.6% 10.4% 35.8% 35.8% 1.7% 10.4% 35.0% 35.0% 1.8% 10.0% 35.4% 35.4% 1.2% 3.7% 17.1% 17.1% 2.9% 3.6% 17.2% 17.2% 3.0% 3.0% 16.8% 16.8% 1.1% cares_name cares_parse_reply curl guetzli libevent re2 woff2_new aflpp honggfuzz libfuzzer default asan default asan default asan default asan default asan default asan default asan 0% 10% 20% 30% 40% 0% 10% 20% 30% 40% 0% 10% 20% 30% 40% Percentage of Covered Mutations that are Killed Found By asan default both
  55. Supermutants Computational Reduction Subject #Mutants #Supermutants Factor Curl 29,118 5,804

    5.02 Guetzli 22,961 13,040 1.76 Woff2 (New) 40,914 5,930 6.90 Cares (Name) 4,822 550 8.77 Cares (Parse Reply) 4,822 1,288 3.74 libevent 17,234 864 19.95 re2 21,407 9,670 2.21 Sum 141,278 37,146 3.80
  56. Wallclock Time CPU (Years) 4 Servers (Days) Seed Collection 1.99

    3.50 Default 14.37 25.22 Seed + Default 16.36 28.72 ASAN 15.16 26.61 24 Hours Runs 7.42 13.02 Sum 38.95 Years 68.34 Days Four servers: Intel Xeon Gold 6230R CPU (52 cores) and 188 GB RAM. Note that evaluating a single fuzzer takes 4.09 CPU years with our chosen subjects ("Seed + Default" / #Fuzzers).
  57. 24 Hour Runs Prog Total AFL AFL++ libFuzzer Honggfuzz re2

    104 0 0 0 0 Woff2 (New) 104 0 0 0 1 Curl 104 0 0 1 0 Guetzli 104 0 0 0 1 Libevent 104 0 0 0 0 Cares (Name) 66 0 0 0 0 Cares (Parse Reply) 104 0 0 0 0 Mutants killed during 24 hour runs on 104 stubborn mutants for each subject using ASAN.
  58. Not Independent Mutants Program afl aflpp honggfuzz libfuzzer Curl 4,850

    5,836 4,851 3,852 Guetzli 10 24 16 0 Libevent 0 2 0 0 re2 39 66 37 47 Woff2 (New) 26 46 56 48 Cares (Name) 4 0 0 0 Cares (Parse Reply) 2 4 4 0 Number of mutants that were covered together with other mutants (i.e., mutants wrongly thought independent).