PaperlayerView exact revision on arXiv

Source-linked AI summary

Angora: Efficient Fuzzing by Principled Search

Peng Chen, Hao Chen

arXiv:1803.01307v2cs.CR

TL;DR

Existing fuzzers trade off input quality against speed: symbolic execution is slow, while random mutation struggles to produce effective inputs. Angora addresses this by solving path constraints without symbolic execution using targeted search techniques, and it outperformed state-of-the-art fuzzers across benchmark and real-world programs. Its evaluation found 103 LAVA-M bugs that the dataset authors could not trigger and 175 new bugs in eight mature open-source programs.

  • Problem

    State-of-the-art fuzzers either produce quality inputs slowly through symbolic execution or run quickly with random mutation but struggle to produce quality inputs.

  • Method

    Angora is a mutation-based fuzzer that increases branch coverage by solving path constraints without symbolic execution using taint tracking, context-sensitive branch counting, gradient descent, and input length exploration.

  • Results

    Angora outperformed other state-of-the-art fuzzers by a wide margin, found 103 LAVA-M bugs the authors could not trigger, and found 175 new bugs in eight mature open-source programs.

  • Takeaways & Limitations

    Angora’s evaluation shows that mutation-based fuzzing can produce high-quality inputs while substantially improving bug discovery and coverage.

  • Takeaways & Limitations

    Context-sensitive branch coverage can dramatically increase the number of unique branches during deep recursion, requiring mitigation in the implementation.

Abstract

from arXiv · show

Fuzzing is a popular technique for finding software bugs. However, the performance of the state-of-the-art fuzzers leaves a lot to be desired. Fuzzers based on symbolic execution produce quality inputs but run slow, while fuzzers based on random mutation run fast but have difficulty producing quality inputs. We propose Angora, a new mutation-based fuzzer that outperforms the state-of-the-art fuzzers by a wide margin. The main goal of Angora is to increase branch coverage by solving path constraints without symbolic execution. To solve path constraints efficiently, we introduce several key techniques: scalable byte-level taint tracking, context-sensitive branch count, search based on gradient descent, and input length exploration. On the LAVA-M data set, Angora found almost all the injected bugs, found more bugs than any other fuzzer that we compared with, and found eight times as many bugs as the second-best fuzzer in the program who. Angora also found 103 bugs that the LAVA authors injected but could not trigger. We also tested Angora on eight popular, mature open source programs. Angora found 6, 52, 29, 40 and 48 new bugs in file, jhead, nm, objdump and size, respectively. We measured the coverage of Angora and evaluated how its key techniques contribute to its impressive performance.

1. Introduction

Angora is a mutation-based fuzzer that solves path constraints without symbolic execution, combining targeted search techniques to improve program-state exploration. It substantially outperformed existing fuzzers on LAVA-M and mature open-source programs.

  • Approach: Angora explores program states by solving path constraints without symbolic execution.It tracks unexplored branches and attempts to solve the constraints associated with them.
  • Key techniques: Context-sensitive branch coverage lets Angora distinguish executions of the same branch in different calling contexts.This can allow more pervasive exploration of program states than AFL’s context-insensitive coverage.
  • Key techniques: Byte-level taint tracking identifies input bytes affecting each path constraint, allowing Angora to mutate only relevant bytes.This substantially reduces the exploration space.
  • Key techniques: Gradient descent searches for inputs satisfying path constraints, while type and shape inference helps handle groups of bytes used as single program values.Input length exploration additionally increases input size when longer inputs may reach new branches.
  • Evaluation: 1541 bugs were found by Angora in who, eight times as many as the second-best fuzzer, Steelix.Angora also found 103 injected bugs that the LAVA authors could not trigger.
  • Evaluation: 6, 52, 29, 40 and 48 new bugs were found in file, jhead, nm, objdump and size, respectively.These results came from tests on eight popular, mature open-source programs.

2. Background: American Fuzzy Lop (AFL)

AFL is a lightweight mutation-based graybox fuzzer that retains inputs reaching new branch states as seeds. Its low-overhead random mutations can nevertheless produce many ineffective inputs.

  • Overview: AFL uses lightweight instrumentation and genetic algorithms to discover test cases likely to trigger new internal program states.As a coverage-based fuzzer, it generates inputs intended to traverse different program paths.
  • Coverage tracking: AFL represents each executed branch as a tuple of the preceding and following basic-block IDs.It records branch execution counts in a per-run path trace table.
  • Coverage tracking: AFL’s global branch coverage table stores an 8-bit vector indicating ranges of execution counts observed across runs.The ranges span from one execution through at least 128 executions.
  • Coverage tracking: AFL heuristically treats an input as reaching a new internal state when it executes a new branch or produces a previously unseen execution-count range.It compares the current path trace table with the global branch coverage table.
  • Mutation: AFL randomly applies bit and byte flips, interesting-value substitutions, arithmetic changes, random byte assignments, block operations, and splicing.These mutations modify individual values or larger input regions.

3. Design

Angora targets unexplored branches by combining context-sensitive coverage with taint-guided, gradient-based constraint solving. Its design addresses discrete inputs, multi-byte values, efficient taint representation, and context-insensitive coverage failures.

  • Fuzzing loop: Angora selects an unexplored branch and searches for an input that executes it, rather than relying on symbolic execution.The fuzzing loop instruments program variants, tracks unexplored branches, and repeatedly mutates inputs associated with sibling branches.
  • Constraint-guided search: Angora mutates only input bytes flowing into a target predicate and treats path constraints as blackbox functions solved with adapted gradient descent.This avoids mutating irrelevant bytes while replacing expensive symbolic execution with directional searches over program executions.
  • Context-sensitive branch count: Context-sensitive coverage distinguishes the same branch executed under different call-stack contexts, exposing internal states that context-insensitive coverage can miss.Angora defines a branch using predecessor and successor block IDs plus a hash of the call stack; this detects the new state in the “01” example.
  • Byte-level taint tracking: The taint representation stores bit vectors in a labeled tree and lookup table, reducing space from O(nl) to O(l · log l) while supporting INSERT, FIND, and UNION.This structure addresses the cost of repeated unions for overlapping taints, where UNION-FIND is inapplicable because vectors are not disjoint.
  • Constraint-guided search: Gradient descent is challenging because fuzzing functions lack analytic gradients and are usually discrete, but it can solve monotonic or convex constraints quickly.The method estimates directional derivatives through perturbed program runs; monotonicity or convexity supports rapid solution finding even for complex analytic forms.
  • Shape and type inference: Shape and type inference groups bytes used together and infers their primitive types so gradient descent operates on program values rather than mismatched individual bytes.Taint analysis groups sequences matching primitive sizes, resolves conflicts using the smallest size, and uses instruction semantics for types.

4. Implementation

Angora’s implementation instruments programs with LLVM and runtime analyses to connect predicates with input bytes, record execution behavior, and support context-sensitive fuzzing. It also includes specialized handling for taint tracking, branch forms, string and array comparisons, and performance optimization.

  • Instrumentation: LLVM instrumentation collects conditional-statement information, links predicates to input byte offsets through taint analysis, records execution traces, supports runtime context, and gathers predicate values.These analyses are performed to support Angora’s mutation and branch-exploration workflow.
  • Taint tracking: Angora extends DataFlowSanitizer for scalable byte-level taint tracking and caches FIND and UNION operations to accelerate it.
  • Branch handling: The implementation translates LLVM switch statements into sequences of if statements so they can be handled as multiple branches.
  • Predicate handling: Angora recognizes libc string and array comparisons in predicates, transforming calls such as strcmp(x, y) into a comparison operator it understands.
  • Implementation scale: Angora is implemented in 4488 lines of Rust and optimized with a fork server and CPU binding.

5. Evaluation

The evaluation compares Angora with state-of-the-art fuzzers on LAVA-M, measures bug-finding behavior, and examines its performance advantages. Angora found substantially more injected bugs than the compared fuzzers, including bugs previously untriggered by LAVA’s authors.

  • Experimental setup: The evaluation used one CPU core per program for comparisons, ran experiments five times, and reported average performance.
  • LAVA-M comparison: 1443 of 2136 injected bugs in who were found by Angora, compared with Steelix’s 194 of 2136 under the stated evaluation setup.Angora found all injected bugs in uniq, base64, and md5sum.
  • LAVA-M comparison: Angora found all bugs in uniq, base64, and md5sum, while Steelix found 7 of 28 in uniq and 28 of 57 in md5sum.AFL found 10 bugs total across all programs.
  • Previously untriggered bugs: Angora found 103 injected bugs that were unlisted because LAVA’s authors could not trigger them while preparing the data set.
  • Explaining the result: Angora’s advantage is attributed to tracking predicate-dependent input offsets and solving constraints with gradient descent instead of relying on directly copied magic bytes.Angora also schedules computation on unexplored-branch path constraints rather than applying the magic-bytes strategy blindly.

5.2. Evaluate Angora on unmodified real world programs

Angora was evaluated on mature, unmodified open-source programs against AFL, measuring crashes and cumulative code coverage over five hours.

  • Evaluation setup and results: Angora outperformed AFL on line coverage, branch coverage, and unique crashes on every tested program.The evaluation used one CPU core for five hours and deduplicated crashes with afl-cmin -C.
  • Evaluation setup and results: 6, 52, 29, 40, and 48 unique crashes were found by Angora in file, jhead, nm, objdump, and size, respectively.AFL found 0, 19, 12, 4, and 6 unique crashes on those programs.
  • Evaluation setup and results: 127.4% and 144.0% were Angora’s improvements over AFL in line and branch coverage, respectively, on jhead.This was the most prominent contrast among the tested programs.
  • Coverage over time: Angora covered more lines and branches than AFL at all times during the five-hour file comparison.The authors attribute its superior coverage to exploring both branches of complicated conditional statements.

5.3. Context-sensitive branch count

Context-sensitive branch counting distinguishes branches reached in different function-call contexts, improving Angora’s exploration and bug-finding performance on file.

  • Performance: 6 bugs were found with context-sensitive branch counting, compared with no bugs without it, on file.The comparison ran Angora separately with context-sensitive and context-insensitive branch counts.
  • Performance: Starting 30 minutes into fuzzing, context-sensitive counting consistently produced greater cumulative line coverage on file.This result was shown in Figure 7.
  • Mechanism: Context-sensitive branch counting distinguishes the same branch across different function-call contexts, allowing Angora to explore more paths.The authors describe this as enabling more pervasive program-state exploration.
  • Implementation impact: Calling-context information creates more unique branches in Angora’s hash table, requiring a larger table to keep collision rates low.The evaluation examined the increase in unique branches on real-world programs.

5.4. Search based on gradient descent

Angora uses gradient descent instead of random mutation or magic bytes to solve path constraints, and it solved more constraints across all tested programs.

  • Comparison: Gradient descent solved more constraints than random mutation and VUzzer’s magic-bytes-plus-random-mutation strategy on every tested program.All three strategies received the same AFL-generated inputs to isolate the search strategy.
  • Comparison: The magic-bytes strategy cannot solve constraints whose values are not copied directly from the input.The variable descsz in Figure 6 is an example of such a constraint.

5.5. Input length exploration

Angora explores input length on demand when path constraints may depend on it, and its strategy produced higher-quality inputs than random length increases.

  • Strategy: Angora increases input length when it observes that a path constraint may depend on length, whereas AFL and related fuzzers increase it randomly.The comparison evaluated increase frequency, useful inputs, and average useful-input length.
  • Results: Angora’s strategy increased input length about two orders of magnitude fewer times than the random strategy.This comparison was conducted over five hours.
  • Results: Angora generated more useful inputs than random length increases in every case except readpng and jhead.It found three fewer useful inputs on readpng, while neither strategy found any on jhead because only image headers are parsed.
  • Results: Angora generated shorter useful inputs on average on every tested program than the random strategy.The authors note that shorter inputs make many programs run faster.
  • Conclusion: The input-length strategy generated higher-quality inputs than the random strategy.This conclusion combines useful-input counts and average lengths.

5.6. Execution speed

Angora’s taint-tracking cost is amortized across repeated executions, keeping instrumented execution near AFL’s speed while supporting constraint-solving evaluation.

  • 5.6. Execution speed: Angora runs taint tracking once per input, then performs many mutations without taint tracking, amortizing the one-time cost.Branch counting dominates instrumented execution time without taint tracking.
  • 5.6. Execution speed: AFL executes inputs at a slightly higher rate than Angora.

6. Related work

Angora extends mutation-based fuzzing with targeted seed selection, byte-level taint tracking, compact taint representation, and gradient-descent constraint solving.

  • 6.1. Prioritize seed inputs: Angora selects seeds whose paths contain conditional statements with unexplored branches, directing exploration toward unsolved program states.This generalizes strategies that prioritize low-frequency or hard-to-reach paths.
  • 6.2. Taint-based fuzzing: Angora’s byte-level taint tracking identifies input offsets flowing into conditional statements and mutates those bytes to satisfy unexplored branches.This supports non-continuous or computed magic-byte patterns beyond values copied directly from inputs.
  • 6.2. Taint-based fuzzing: Angora stores taint labels in a tree-like structure whose size remains constant regardless of the number of input offsets.Shared offsets are stored once, reducing memory consumption for complex patterns.
  • 6.3. Dynamic symbolic execution: Symbolic execution offers semantic insight but faces path explosion and constraint-solving challenges that limit scalability.

7. Conclusion

Angora is a mutation-based fuzzer that combines targeted constraint solving with several analysis and search techniques. It substantially outperformed other state-of-the-art fuzzers across LAVA-M and eight mature open-source programs.

  • 7. Conclusion: Angora combines scalable byte-level taint tracking, context-sensitive branch counting, gradient-descent search, type and shape inference, and input length exploration.
  • 7. Conclusion: Angora found significantly more bugs than other fuzzers on LAVA-M, including 103 bugs the LAVA authors could not trigger.
  • 7. Conclusion: Angora found a total of 175 new bugs in eight popular, mature open-source programs.
Loading 1803.01307v2…