Removing Uninteresting Bytes in Software Fuzzing

Imagine a world where software fuzzing, the process of mutating bytes in test seeds to uncover hidden and erroneous program behaviors, becomes faster and more effective. A lot depends on the initial seeds, which can significantly dictate the trajectory of a fuzzing campaign, particularly in terms of how long it takes to uncover interesting behaviour in your code. We introduce DIAR, a technique designed to speedup fuzzing campaigns by pinpointing and eliminating those uninteresting bytes in the seeds. Picture this: instead of wasting valuable resources on meaningless mutations in large, bloated seeds, DIAR removes the unnecessary bytes, streamlining the entire process.

In this work, we equipped AFL, a popular fuzzer, with DIAR and examined two critical Linux libraries -- Libxml's xmllint, a tool for parsing xml documents, and Binutil's readelf, an essential debugging and security analysis command-line tool used to display detailed information about ELF (Executable and Linkable Format). Our preliminary results show that AFL+DIAR does not only discover new paths more quickly but also achieves higher coverage overall. This work thus showcases how starting with lean and optimized seeds can lead to faster, more comprehensive fuzzing campaigns -- and DIAR helps you find such seeds.

- These are slides of the talk given at IEEE International Conference on Software Testing Verification and Validation Workshop, ICSTW 2022.

1. Aftab Hussain and Mohammad Amin Alipour
Department of Computer Science
University of Houston


5th International Workshop on the Next Level of Test Automation (NEXTA) 2022
Co-located with the 15th IEEE International Conference on Software Testing, Verification and Validation (ICST) 2022

Removing Uninteresting Bytes in
Software Fuzzing

2. Software Fuzzing?

3. Software Fuzzing?
A Random Software Testing technique.

Found bugs in many software packages.
Regularly used in large software companies.
Popular Fuzzers – AFL, AFL++, honggfuzz, libfuzzer

4. Software Fuzzing
Input Seed
P
Execute
Program P
Coverage Guided
Fuzzer
Mutated
Seeds
Interesting
Seeds

5. Software Fuzzing
Input Seed
P
Execute
Program P
Coverage Guided
Fuzzer
Mutated
Seeds
Interesting
Seeds
Data on discovered paths, branches, lines, crashes.

6. Software Fuzzing
Input Seed
P
Execute
Program P
Coverage Guided
Fuzzer
Mutated
Seeds
Data on discovered paths, branches, lines, crashes.

Fuzzers try to increase the speed of this discovery.
Interesting
Seeds

7. The Problem?

8. Input Seed
The Problem

9. Input Seed
Large number of
uninteresting bytes, which
do not contribute to new
program behaviour when
they are changed.

Example: payload data in a
network protocol
The Problem

10. The Problem
Mutating a lot of uninteresting bytes in a large input seed wastes
fuzzing resources and slows down exploration.

Thus, the seeds we use in fuzzing have a significant impact on
fuzzing performance.

11. Previous Strategies

12. Previous Strategies for improving Fuzzer Performance
Structure-aware fuzzing. Use grammar specifications to generate meaningful
input seeds e.g. Peach, LangFuzz, CSmith, or learn structure of the input while
fuzzing to do so, e.g. Grimoire 2019, Skyfire 2017.

Smart Mutation Scheduling. Probabilistically schedule mutation operators
based on heuristics, e.g. MOPT [25].

Seed Selection. Use different strategies to discard seeds from a
corpus, e.g. by SAT solving seed execution traces for redundant seeds
OPTIMIN [5], and discarding seeds by execution time and file size, e.g.
MINSET [Rebert et al. USENIX Security 2014].

13. Previous Strategies for improving Fuzzer Performance
Structure-aware fuzzing. Use grammar specifications to generate meaningful
input seeds e.g. Peach, LangFuzz, CSmith, or learn structure of the input while
fuzzing to do so, e.g. Grimoire 2019, Skyfire 2017.

Smart Mutation Scheduling. Probabilistically schedule mutation operators
based on heuristics, e.g. MOPT [Lyu et al. USENIX Security 2019].

Seed Selection. Use different strategies to discard seeds from a
corpus, e.g. by SAT solving seed execution traces for redundant seeds
OPTIMIN [5], and discarding seeds by execution time and file size, e.g.
MINSET [Rebert et al. USENIX Security 2014].

14. Previous Strategies for improving Fuzzer Performance
Structure-aware fuzzing. Use grammar specifications to generate meaningful
input seeds e.g. Peach, LangFuzz, CSmith, or learn structure of the input while
fuzzing to do so, e.g. Grimoire 2019, Skyfire 2017.

Smart Mutation Scheduling. Probabilistically schedule mutation operators
based on heuristics, e.g. MOPT [Lyu et al. USENIX Security 2019].

Seed Selection. Use different strategies to discard seeds from a corpus, e.g. by
SAT solving seed execution traces for redundant seeds (OPTIMIN [Herrera et al.
ISSTA 2021]), and discarding seeds by execution time and file size, e.g.
MINSET [Rebert et al. USENIX Security 2014].

15. Can removing uninteresting bytes
from seeds improve fuzzing
performance?

16. DIAR

17. DIAR
Reduces the size of a seed by removing uninteresting bytes, while
maintaining a certain level of coverage.

Customizable – allows users to set a time budget for reduction and set
the maximum allowable loss of test coverage.

18. The Core of DIAR:

Delta Debugging

19. DIAR uses delta debugging (DD) [Zeller, Hildebrandt TSE 2002]:







In DIAR, we modify DD to perform inadequate reduction [Alipour et al.
ASE 2016], where the reduced seed preserves a % of the coverage of
the original seed, set by the Coverage Similarity constraint, along with
some other constraints.


The Core of DIAR
DD Module
O
P
Program
Original
seed R
Reduced seed
(Preserves coverage of the
Original Seed in P)

20. The Core of DIAR | Delta Debugging
Say we want to reduce S0,
Coverage Similarity Constraint = x%
S0
Covers a set
of lines L

21. The Core of DIAR | Delta Debugging
S0
Covers a set
of lines L
Covers > x% of L
Say we want to reduce S0,
Coverage Similarity Constraint = x%
S1

22. The Core of DIAR | Delta Debugging
S0
Covers a set
of lines L
Covers > x% of L
Say we want to reduce S0,
Coverage Similarity Constraint = x%
S1
S2
Covers < x% of L

23. The Core of DIAR | Delta Debugging
S0
Covers a set
of lines L
Covers > x% of L
Say we want to reduce S0,
Coverage Similarity Constraint = x%
S1
S2
Covers < x% of L
X

24. The Core of DIAR | Delta Debugging
S0
R
Covers a set
of lines L
Covers > x% of L
Say we want to reduce S0,
Coverage Similarity Constraint = x%
S1
S2
Covers < x% of L
X
Covers > x% of L
A 1-minimal seed
(reducing it any further will cause
it lose the property constraint)

25. The Core of DIAR | Delta Debugging
(A modified version of the Delta Debugging algorithm in Zeller and Hilderbrant, “Simplifying and Isolating
Failure-Inducing Inputs”, TSE 28(2), 2002.)

26. DIAR Architecture

27. O
T
Target binary
Original seed
DIAR Architecture
DIAR

28. O O
T
Target binary
Original seed
.
.
.
Delta Debugging
Component
1. Generate
chunks
Chunks (or deltas)
DIAR Architecture
DIAR

29. O O
T
Target binary
Original seed
.
.
.
Delta Debugging
Component
1. Generate
chunks
Chunks (or deltas)
User-defined
Constraints
DIAR Architecture
DIAR

30. O O
T
Target binary
Original seed
T.
.
.
Delta Debugging
Component
1. Generate
chunks
2. Execute
generated seed
on target
Generated
seeds
Chunks (or deltas)
User-defined
Constraints
DIAR Architecture
DIAR

31. O O
T
Target binary
Original seed
T.
.
.
Delta Debugging
Component
1. Generate
chunks
2. Execute
generated seed
on target
3. Analyze generated
coverage data
Generated
seeds
Chunks (or deltas)
User-defined
Constraints
DIAR Architecture
DIAR

32. DIAR Architecture
O O
T
Target binary
Original seed
T.
.
.
Delta Debugging
Component
1. Generate
chunks
2. Execute
generated seed
on target
3. Analyze generated
coverage data
Generated
seeds
R
4. Returns a 1-minimal seed
satisfying user-defined
constraints.
Chunks (or deltas)
User-defined
Constraints
DIAR

33. Experiments

34. Experimental Setup
Test Subjects

xmllint (from libxml2)
readelf (from binutils)


Fuzzing Campaigns

Each test subject was fuzzed with AFL for 24 hours with the original seed and the reduced seed.

Each fuzzing campaign was repeated 3 times.

In total, 6 fuzzing sessions were performed for each test subject.

35. Path Coverage
Results
AFL found significantly more paths with the DIAR reduced seed (almost four times as many) with readelf.

Fuzzing with the original seed seemed to suffer more stagnation.

36. Seed Reduction
Results
DIAR can reduce a seed by more than 80% in under 5 minutes, retaining at least
75% coverage similarity with the coverage of the original seed.

37. Results
Lines and Branches
Covered

38. Results
Lines and Branches
Covered
Fuzzing campaigns with the reduced seed covered more lines and branches for readelf.

39. Results
Lines and Branches
Covered
Fuzzing campaigns with the reduced seed covered more lines and branches for readelf.

40. Crashes Found
Results

41. Crashes Found
Results
Fuzzing campaigns with the reduced seed found more crashes for readelf.

42. Seed Reduction
Results
The readelf seed has a significantly high number of uninteresting bytes, e.g. bytes
in data/text section in the ELF binary seed, that were removed.

43. Seed Reduction
Results
The xmllint seed had a relatively lesser number of uninteresting bytes, and also
there may have been a loss of some important bytes in the inadequate reduction
process.

44. Takeaways

45. More crashes found.
Fuzzing with the DIAR-reduced seed found more crashes (with readelf).

More paths discovered.
Fuzzing with a DIAR-reduced seed yielded significantly higher number
of paths (with readelf).

The more the uninteresting bytes, the better.
A seed that has more uninteresting bytes seems to benefit more from DIAR.

Preserve 100% coverage for small seeds.
When seeds are very small, adequate reduction may be used instead. t

.
Takeaways from the Experiments

46. More crashes found.
Fuzzing with the DIAR-reduced seed found more crashes (with readelf).

More paths discovered.
Fuzzing with a DIAR-reduced seed yielded significantly higher number
of paths (with readelf).

The more the uninteresting bytes, the better.
A seed that has more uninteresting bytes seems to benefit more from DIAR.

Preserve 100% coverage for small seeds.
When seeds are very small, adequate reduction may be used instead. t


Takeaways from the Experiments

47. More crashes found.
Fuzzing with the DIAR-reduced seed found more crashes (with readelf).

More paths discovered.
Fuzzing with a DIAR-reduced seed yielded significantly higher number
of paths (with readelf).

The more uninteresting bytes, the better.
A seed that has more uninteresting bytes seems to benefit more from DIAR.

Preserve 100% coverage for small seeds.
When seeds are very small, adequate reduction may be used instead. t


Takeaways from the Experiments

48. More crashes found.
Fuzzing with the DIAR-reduced seed found more crashes (with readelf).

More paths discovered.
Fuzzing with a DIAR-reduced seed yielded significantly higher number
of paths (with readelf).

The more uninteresting bytes, the better.
A seed that has more uninteresting bytes seems to benefit more from DIAR.

Preserve 100% coverage for small seeds.
When seeds are very small, adequate reduction may be used instead. t


Takeaways from the Experiments

49. Concluding Remarks

50. DIAR Architecture

51. Input Seed
Large number of uninteresting
bytes, which do not contribute
to new program behaviour
when they are changed.

Example: payload data in a
network protocol
DIAR Architecture

52. Crashes Found Paths Found
Input Seed
Large number of uninteresting
bytes, which do not contribute
to new program behaviour
when they are changed.

Example: payload data in a
network protocol
DIAR Architecture

53. Crashes Found Paths Found
Input Seed
Large number of uninteresting
bytes, which do not contribute
to new program behaviour
when they are changed.

Example: payload data in a
network protocol
DIAR Architecture
Thank You