![](https://csdnimg.cn/release/download_crawler_static/10306474/bg3.jpg)
Algorithm 1 Angora’s fuzzing loop. Each while loop has a
budget (maximum allowed number of iterations)
1: function FUZZ(program, seeds)
2: Instrument program in two versions: program
nt
(no taint tracking) and program
t
(with taint tracking).
3: branches ← empty hash table Key: an
unexplored branch b. Value: the input that explored b’s
sibling branch.
4: for all input ∈ seeds do
5: path ← Run program
t
(input)
6: for all unexplored branch b on path do
7: branches[b] ← input
8: end for
9: end for
10: while branches 6= ∅ do
11: Select b from branches
12: while b is still unexplored do
13: Mutate branches[b] to get a new input
input
0
(Algorithm 5)
14: Run program
nt
(input
0
)
15: if input
0
explored new branches then
16: path
0
← Run program
t
(input
0
)
17: for all unexplored branch b
0
on path
0
do
18: branches[b
0
] ← input
0
19: end for
20: end if
21: if b was explored then
22: branches ← branches − {b}
23: end if
24: end while
25: end while
26: end function
we ought to consider these four bytes as a single
argument to the function instead of as four independent
arguments. To achieve this goal, we need to infer which
bytes in the input are used collectively as a single value
and what the type of the value is (Section 3.5).
• It would be inadequate to only mutate bytes in the
input. Some bugs are triggered only after the input is
longer than a threshold, but this creates a dilemma on
deciding the length of the input. If the input is too
short, it may not trigger certain bugs. But if the input
is too long, the program may run too slow. Most fuzzers
change the length of inputs using ad hoc approaches.
By contrast, Angora instruments the program with code
that detects when a longer input may explore new
branches and that determines the minimum required
length (Section 3.6).
Figure 1 shows a diagram of the steps in fuzzing a con-
ditional statement. The program in Figure 2 demonstrates
these steps in action.
• Byte-level taint tracking: When fuzzing the conditional
statement on Line 2, using byte-level taint tracking,
Angora determines that bytes 1024–1031 flow into this
expression, so it mutates these bytes only.
• Search algorithm based on gradient descent: Angora
needs to find inputs that run both branches of the
conditional statement on Line 2, respectively. Angora
treats the expression in the conditional statement as
a function f(x) over the input x, and uses gradient
descent to find two inputs x and x
0
such that f(x) > 0
and f(x
0
) ≤ 0.
• Shape and type inference: f(x) is a function over the
vector x. During gradient descent, Angora computes
the partial derivative of f over each component of x
separately, so it must determine each component and
its type. On Line 2, Angora determines that x consists
of two components each consisting of four bytes in the
input and having the type 32-bit signed integer.
• Input length exploration: main will not call foo unless
the input has at least 1032 bytes. Instead of blindly
trying longer inputs, we instrument common functions
that read from input and determine if longer input
would explore new states. For example, if the initial
input is shorter than 1024 bytes, then the conditional
statement on Line 12 will execute the true branch.
Since the return value of fread is compared with
1024, Angora knows that only inputs at least 1024
bytes long will explore the false branch. Similarly, the
instrumentation on Lines 16 and 19 instructs Angora
to extend the input to at least 1032 bytes to execute the
function foo.
3.2. Context-sensitive branch count
Section 2 describes AFL’s branch coverage table. Its
design has several advantages. First, it is space efficient. The
number of branches is linear in the size of the program.
Second, using ranges to count branch execution provides
good heuristics on whether a different execution count indi-
cates new internal state of the program. When the execution
count is small (e.g., less than four), any change in the count
is significant. However, when the execution count is large
(e.g., greater than 32), a change has to be large enough to
be considered significant.
But this design has a limitation. Because AFL’s branches
are context-insensitive, they fail to distinguish the executions
of the same branch in different contexts, which may over-
look new internal states of the program. Figure 3 illustrates
this problem. Consider the coverage of the branch on Line 3.
During the first run, the program takes the input “10”. When
it calls f() on Line 19, it executes the true branch on
Line 4. Later, when it calls f() on Line 21, it executes
the false branch on Line 10. Since AFL’s definition of
branch is context-insensitive, it thinks that both branches
have executed. Later, when the program takes a new input
“01”, AFL thinks that this input triggers no new internal
state, since both the branches on Line 4 and 10 executed
in the previous run. But in fact this new input triggers a
new internal state, as it will cause crash on Line 6 when
input[2]==1.
We incorporate context into the definition of branches.
We define a branch as a tuple (l
prev
, l
cur
, context), where