Typestate-Guided Fuzzer for Discovering Use-after-Free
Vulnerabilities
Haijun Wang

Xiaofei Xie∗Yi Li

Ant Financial Services Group, China& CSSE, Shenzhen University, China

Nanyang Technological University
Singapore

Nanyang Technological University
Singapore

Cheng Wen

Yuekang Li

Yang Liu

CSSE, Shenzhen University
Shenzhen, China

Nanyang Technological University
Singapore

Nanyang Technological University
Singapore
Zhejiang Sci-Tech University, China

Shengchao Qin∗

Hongxu Chen

Yulei Sui

SCEDT, Teesside University
Tees Vally, UK

Nanyang Technological University
Singapore

University of Technology Sydney
Australia

KEYWORDS

ABSTRACT

Fuzzing, Typestate-guided fuzzing, Use-after-Free vulnerabilities

Existing coverage-based fuzzers usually use the individual control
flow graph (CFG) edge coverage to guide the fuzzing process, which
has shown great potential in finding vulnerabilities. However, CFG
edge coverage is not effective in discovering vulnerabilities suchas use-after-free (UaF). This is because, to trigger UaF vulnerabilities, one needs not only to cover individual edges, but also to
traverse some (long) sequence of edges in a particular order, which
is challenging for existing fuzzers. To this end, we propose to model
UaF vulnerabilities as typestate properties, and develop a typestateguided fuzzer, named UAFL, for discovering vulnerabilities violating
typestate properties. Given a typestate property, we first performa static typestate analysis to find operation sequences potentiallyviolating the property. Our fuzzing process is then guided by theoperation sequences in order to progressively generate test cases
triggering property violations. In addition, we also employ an information flow analysis to improve the efficiency of the fuzzing
process. We have performed a thorough evaluation of UAFL on
14 widely-used real-world programs. The experiment results showthat UAFL substantially outperforms the state-of-the-art fuzzers, including AFL, AFLFast, FairFuzz, MOpt, Angora and QSYM, in termsof the time taken to discover vulnerabilities. We have discovered
10 previously unknown vulnerabilities, and received 5 new CVEs.

ACM Reference Format:
Haijun Wang, Xiaofei Xie, Yi Li, Cheng Wen, Yuekang Li, Yang Liu, Shengchao
Qin, Hongxu Chen, and Yulei Sui. 2020. Typestate-Guided Fuzzer for Discovering Use-after-Free Vulnerabilities. In 42nd International Conference on
Software Engineering (ICSE ’20), May 23–29, 2020, Seoul, Republic of Korea.
ACM, New York, NY, USA, 12 pages. https://doi.org/10.1145/3377811.3380386

1

INTRODUCTION

Software defects are pervasive [10] and may be exploited by malicious parties [38]. These software vulnerabilities have become
fundamental threats against the software security. With the development of mitigation techniques [11, 33], many security vulnerabilities such as buffer overflow [12], have become harder to exploit.
An exception is the use-after-free (UaF) vulnerability. There are still
very few mitigation techniques deployed in production environments to defend against UaF vulnerabilities [42]. This has made UaF
a significantly more vulnerable target for exploitation [19, 37, 44].
The UaF vulnerability happens when the memory is accessed after it
has been freed previously, which may cause data corruption [38, 40],
information leaks [19], denial-of-service [7], and arbitrary code execution attacks [5]. According to recent reports [19, 42], about 80%of the UaF vulnerabilities in the NVD database were rated criticalor high in severity. In contrast, only about 50% of the heap buffer
overflow vulnerabilities were considered as high severity.
Compared with other vulnerabilities (e.g., the stack/heap buffer
overflow vulnerability), UaF vulnerabilities are generally consideredmore difficult to detect [19]. The main reason is that, to successfully
trigger a UaF, a sequence of operations need to be executed in
the specific order — first allocating the memory, then terminating
the lifetime of the memory, and finally dereferencing the memory.
These operations may not share locality in the code base, whichmakes the detection much more challenging.
Nevertheless, there exist some automated techniques for detecting and defending against UaF vulnerabilities. Static analysis-based
techniques [30, 42] suffer from false positives, especially when dealing with real-world software systems. This is due to the fact that
how to perform scalable and precise inter-procedural alias analysis

CCS CONCEPTS• Security and privacy → Software security engineering.
∗ Corresponding authors: Shengchao Qin and Xiaofei Xie

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from permissions@acm.org.
ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea© 2020 Association for Computing Machinery.
ACM ISBN 978-1-4503-7121-6/20/05. . . $15.00
https://doi.org/10.1145/3377811.3380386
1

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea

Haijun Wang et al.
1

remains an open problem. Imprecise results from the alias analysis could also affect the effectiveness of some run-time detection
mechanisms, such as FreeSentry [44] and DangNULL [19]. These
techniques monitor the pointers to each memory location and replace them with invalid pointers once the memory is freed. If suchan invalidated pointer is accessed, the program will subsequently
crash, preventing an attacker from exploiting the vulnerability.
On the other hand, dynamic techniques, e.g., greybox fuzzing [18],which less likely produce false positives, have been shown effective
in detecting memory-related vulnerabilities. Specially, AFL [47],libFuzzer [24] and the fuzzing infrastructure ClusterFuzz [17] havediscovered more than 16,000 vulnerabilities in over 160 open source
projects [17, 47]. However, existing techniques are not effective in
detecting UaFs as shown in our experiments (c.f. Section 5.3). Existing coverage-based fuzzers, e.g., AFL [47], usually use the individual
Control Flow Graph (CFG) [36] edge coverage to guide the fuzzing
process. Unfortunately, CFG edge coverage is not so effective in
discovering UaFs. This is because, to trigger UaF vulnerabilities,
one needs not only to cover individual CFG edges, but also to traverse some long sequence of edges in a particular order, which isvery difficult for existing coverage-based fuzzers. For example, thestate-of-the-art grey-box fuzzers MOpt [25] and ProFuzzer [43] discover very few UaF vulnerabilities, according to their experimental
results.
To address this challenge, we propose a typestate-guided fuzzer,
named UAFL, for discovering vulnerabilities violating certain typestate properties. Our insight is that many common vulnerabilities
can be seen as the violation of certain typesate properties. For example, the operation sequence, ⟨malloc → free → use⟩, is a witness ofthe typestate property violation shown in Fig. 3; therefore, it maytrigger the UaF vulnerability. Similarly, ⟨nullify → dereference⟩ is awitness for the null pointer dereferencing. Although our approachis generally applicable to all vulnerabilities which can be modelled
by typestate property violations, we focus on one representative
exemplar, UaF, in this paper. We first perform typestate analysis
to identify operation sequences potentially violating the typestate
properties. We then instrument the operation sequence coverage
into the target program. Based on the information collected fromthe instrumentation, we propose two strategies to improve the effectiveness of the fuzzer: (1) we use the operation sequence coverageas the feedback to guide the test generation to progressively cover
the operation sequences (c.f. Section 4.2), and (2) we deploy an
information flow analysis to infer how test inputs affect the program states (c.f. Section 4.3), and use such information to design anefficient mutation strategy by avoiding unnecessary mutations.
We have implemented UAFL and evaluated it on 14 widely-usedprograms with diverse functionalities. UAFL significantly outperforms AFL [47], AFLFast [4], FairFuzz [21], MOpt [25], Angora [9],QSYM [46]. In particular, UAFL achieves, respectively, a speedupof 3.25×, 3.16×, 2.63×, 3.35×, 6.00×, and 3.80× to detect the vulnerabilities, compared to existing fuzzers AFL, AFLFast, FairFuzz,
MOpt, Angora, and QSYM. Moreover, we have discovered 10 previously unknown UaF vulnerabilities in real-world programs, forthem we have received 5 CVEs. All the new vulnerabilities havebeen confirmed.
The contribution of this work is summarized as follows.

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void main() {char buf[7];read(0, buf, 7)
char* ptr1 = malloc(8);char* ptr2 = malloc(8);if(buf[5] == 'e')
ptr2 = ptr1;
if(buf[3] == 's')if(buf[1] == 'u')free(ptr1);
if(buf[4] == 'e')if(buf[2] == 'r')if(buf[0] == 'f')
ptr2[0] = 'm';...
}Figure 1: An example simplified from UaF(CVE-2018-20623).
• We propose a typestate-guided fuzzer for discovering vulnerabilities violating certain typestate properties. It specifically addresses
the challenge in detecting vulnerabilities triggered by specificsequences of operations (e.g., the UaF vulnerabilities), where weuse operation sequence as guidance to progressively generate
test cases violating the typestate properties.
• We design an effective mutation strategy customized for typestateguided fuzzer and apply quantitative information flow analysis
to help improve the overall performance of fuzzing process.
• We have implemented the proposed techniques as UAFL, and evaluated its effectiveness on a set of popular real-world programs.
UAFL significantly outperforms the state-of-the-art fuzzers. We
have discovered 10 previously unknown UaF vulnerabilities, 5 ofwhich have been published as CVEs.

2

MOTIVATING EXAMPLE

In this section, we give an overview of UAFL with a motivating
example, as shown in Fig. 1. This example is simplified from the realworld program readelf, which contains a UaF vulnerability (i.e., CVE2018-20623). Fig. 2(a) shows its control flow graph (CFG), where
the nodes represent the statements marked with their line numbers.
The UaF vulnerability can be triggered when the statements (Lines4, 7, 10 and 14) are executed temporally. Specifically, the pointerptr 1 points to the memory allocated at Line 4, and then ptr 1 andptr 2 become aliases at Line 7. The memory pointed by ptr 1 (andptr 2) is freed at Line 10, but accessed again at Line 14 by ptr 2.

2.1

Existing Coverage-based Fuzzers

Existing coverage-based fuzzers usually utilize the CFG edge coverage to guide the fuzzing process, such as AFL [47]. In this section,
we take AFL for example to illustrate how the CFG edge coverage
is calculated in existing fuzzers. Given a program, AFL needs toidentify the CFG edge (i.e., an edge from one basic block to anotherone). To this end, AFL first generates a random ID for each basic
block of the program. Then, a CFG edge ID is calculated based on
the IDs of two basic blocks. For example, regarding edge A → B,
its ID is calculated: IDA→B = (IDA >> 1) ⊕ IDB , where the shiftoperation >> is to preserve the directionality of the edge such that
the ID of edge A → B is distinguishable from the ID of edge B → A.
A shared memory shared_mem is used to count the hits of anedge. For example, shared_mem[ID A→B ]++ represents that hits ofedge A → B are increased by 1. Actually, the hits of each edge isdivided into 8 buckets: hit 1 time, 2 times, 3 times, 4-7 times, 8-15
2

Typestate-Guided Fuzzer for Discovering Use-after-Free Vulnerabilities

2-5

ptr1 = malloc(8)6‘aaaaaaa’‘aaaseen’‘aurseaa’‘faraeaa’

2-5

2-5

2-5

2-5

2-5

6

6

6

6

6

7
ptr2 = ptr1
8

7
8

8

9

8

8

10
11

12

11
12

13

…

13

…

…

7
8

7

8
9

8
9

free

9
10

11

11
12

…

12

12
13

…

(b) Fuzzing process in AFL

Bug!

10
11

14
use

14
…

Phase1: Typestate Analysis(a) Control flow graph

7

13
14

…

6

12

14
ptr2>@ = ‘m’

6

11
12

13

2-5

6
alias

10
11

12

‘furseen’

2-5

9

10
11

‘auaseen’

2-5

8

……
Discarded9‘aaaseen’malloc79free(ptr1)

11

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea…

…

Phase2: Typestate-Guided Fuzzing(c) Fuzzing process in UAFL

Figure 2: Fuzzing process of AFL and UAFL in the example of Fig. 1.
times, 16-31 times, 32-127 times, and 128-255 times. Given a test
case, AFL generates new test cases by performing mutations on it.
Basically, the new test case is considered as interesting and added
into the test pool for further mutation, if it covers the edges notfound by previous test cases or it touches the new buckets of edges.
Otherwise, this test case is discarded.

2.2

Phase1: Typestate Analysis. Based on the typestate property(e.g., UaF and double-free in Fig. 3), UAFL firstly performs thestatic typestate analysis to capture the operation sequences in the
program, following the temporal relation violating the typestate
property. For example, to discover the UaF vulnerability, UAFL
identifies all operation sequences following the pattern malloc →free → use. As shown in typestate analysis step of Fig. 2(c), we
present the identified operation sequence (i.e., 4 → 7 → 10 →14), which satisfies the UaF pattern. This operation sequence first
performs the memory allocation, then goes through the memory
free, and finally reaches the memory use. It is worth noting that
UAFL also performs the pointer alias analysis, e.g., pointers ptr 1
and ptr 2 may be aliases during the execution.

Limitations of Coverage-based Fuzzers

Existing coverage-based fuzzers usually consider the CFG edge’s
coverage individually, and they are limited to track the coverage of asequence of edges. For example, regarding a path A → B → C, AFL
individually counts the hits of A → B and B → C, but cannot track
the hits of this path. Hence, existing coverage-based fuzzers arechallenging to detect some vulnerabilities (e.g., UaF and double free),which violate the temporal memory safety malloc → free → use.
This can be also specified as a typestate property, as shown in Fig. 3.
We take the program in Fig. 1 as an example, the UaF vulnerability can be triggered if Lines 4 → 7 → 10 → 14 are executed
temporally (i.e., the grey nodes in Fig. 2(a)). Assume the initial seedis ‘aaaaaaa’ and AFL generates three mutants ‘aaaseen’, ‘aurseaa’
and ‘faraeaa’, as shown in Fig. 2(b). These four program paths cover
all the CFG edges, but none of them can trigger the UaF vulnerability. Besides, since all CFG edges have been covered in these four
test cases, their following mutants will be discarded as they cannot
cover new CFG edges.
Considering the edge’s coverage individually (e.g., AFL), it ishighly difficult to generate a test case that can cover 4 → 7 →
10 → 14. We actually ran AFL on this example, and cannot find the
UaF vulnerability within 24 hours.

2.3

Phase2: Typestate-Guided Fuzzing. Guided by the operation
sequences, UAFL generates test cases to progressively execute towards the operation sequences. UAFL first performs the instrumentation based on the identified operation sequences. The objective of
instrumentation is to provide the feedback, which can guide UAFL
to generate test cases that can execute towards the operation sequences. Fig. 2(c) shows the fuzzing process of UAFL. Assume that
UAFL has also generated the test cases of Fig. 2(b) and covered all
CFG edges. With the operation sequence (i.e., 4 → 7 → 10 → 14)
as guidance, UAFL is able to generate new test cases that gradually
cover the (entire) operation sequence. For example, based on test
case ‘aaaseen’, UAFL may generate a test case ‘auaseen’. This test
case is discarded by AFL, since it does not cover new CFG edges
compared to previous test cases ‘aaaseen’ and ‘aurseaa’. However,as it covers edge 7 → 10 of operation sequence (i.e., malloc → free),
UAFL adds it into the test pool for further mutation, By mutating test case ‘auaseen’, UAFL may further generate new test case‘f urseen’, which covers the operation sequence 4 → 7 → 10 → 14
(i.e., malloc → free → use). Thereby, the UaF vulnerability is discovered. We ran UAFL on this example, and discovered the UaF
vulnerability within about 15 minutes.

Our Approach

Motivated by the aforementioned challenge, we propose a typestateguided fuzzer, named UAFL, which aims to detect the vulnerabilities
violating the typestate property. UAFL works in two phases: typestate analysis and typestate-guided fuzzing.
3

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea

3

Haijun Wang et al.

TYPESTATE ANALYSIS

Algorithm 1: Typestate Analysis for Use-After-Free
input : A program P
output : A set of operation sequences S

In this section, we elaborate on the typestate property and how to
identify operation sequences potentially violating the UaF property
with static typestate analysis.

S ← ∅;(S M , M ) ← find_malloc(P );3 foreach (sm , m) ∈ (S M , M ) do
4
A ← cal_alias(m);5
S F ← find_free(A, P );6
SU ← find_use(A, P );7
S ← S ∪ { ⟨sm , s f , su ⟩ |s f ∈ S F ∧ su ∈SU ∧ is_reachable(sm , s f ) ∧ is_reachable(s f , su )};
1
2

3.1

Typestate Properties

To facilitate the illustration, we adopt a simplified programming
language model defined as follows.
Definition 1 (Program [14]). A program is a Stmt defined by
the following context-free grammar,
Stmt ::= Var := Var|

Var := malloc()

Stmt; Stmt|

if (∗) Stmt else Stmt

Label : Stmt|

goto Label|

Var.op()8

return S ;usewhere ∗ denotes a non-deterministic branch, Var are variables whichreference to objects of type T , Op are operations supported by type T .

mallocWe adopt the intuitive notion of a path p through a program P(or P-path): a valid sequence of statements starting at P’s entry. A
program path may contain operations on multiple objects, and we
can extract multiple operation sequences from it, each per object.
The operation sequence for objects is formally defined as follows.

free

dead

use/freeerror

Figure 3: Typestate for use-after-free and double free.
memory is allocated, it is in the live state, and can be accessed afterwards. Once the memory is freed, it becomes dead. Any subsequentuse/free operation on this memory results in an error state. Notice
that, the double-free vulnerability is a special case of UaF. The UaF
detection is to discover test cases that perform the operation sequences
violating typestate property in Fig. 3.
Refer to the example in Fig. 1, a P-path ⟨2 − 5, 6, 7, 8, 9, 10, 11, 12,
13, 14⟩ contains the operation sequence for the memory associatedwith ptr 1: ⟨4, 7, 10, 14⟩, which violates the given typestate property.

Definition 2 (Operation Seqences (OSs) for Objects [14]).
Given a P-path p, U(p) denotes the set of object instances createdduring this execution, and for any object o ∈ U(p), p[o] denotes thesequence of operations performed on o during execution of p.
For example, assume that a P-path is p = ⟨a.malloc(), a.insert(),b.malloc(), b.free(), a.free()⟩, then we have U(p) = {a, b} and p[a] =⟨a.malloc(), a.insert(), a.free()⟩. An operation sequence for a particular object can be checked against a typestate property, which isformally defined as follows.

3.3

Use-after-Free Typestate Analysis

Given the typestate property of UaF vulnerability, UAFL performs
the static typestate analysis to identify the operation sequences
violating this property. Algorithm 1 shows the basic idea, whichtakes as the input a program P and outputs a set of operation
sequences S violating the property.
For the program P, UAFL first finds all memory allocation statements S M (Line 2), where M is a set of memory objects allocatedat S M . For each memory object m allocated at sm (Line 3), UAFL
calculates all the aliased pointers A that all point to the memory
object m, with the pointer alias analysis [30, 32] (Line 4). Then,
UAFL identifies all memory free statements that free the memory
object m by an aliased pointer in A (Line 5). Following the sameway, UAFL finds all memory use statements (Line 6). Finally, the operation sequence ⟨sm , s f , su ⟩ is added into output S (Line 7), where
sm allocates the memory, s f frees the memory which is reachable
from sm , and su uses the memory which is reachable from s f .
Notice that, UAFL adopts the path-insensitive reachability analysis to perform typestate analysis, and may produce false positives.
Thus, some operation sequences identified in S may not violate thetypestate property. Furthermore, we employ the fuzzing techniquethat will confirm whether they actually violate the property.

Definition 3 (Typestate Property [15]). A typestate property
P is a finite state automaton P = (Σ, Q, δ, init, Q \ {err }), whereΣ is the alphabet of observable operations, Q is the set of states, δis the transition function mapping a state and an operation to a
successor state, init ∈ Q is a distinguished initial state, err ∈ Q is adistinguished error state such that for every σ ∈ Σ, δ (err, σ ) = err ,and all states in Q \ {err } are accepting states.
We say that q ′ is the successor of a state q on operation op when
δ (q, op) = q ′ . Given a sequence of operations α = ⟨op0, . . . , opn ⟩,we write α ∈ P when α is accepted by P, and we write α < P
when α is not accepted by P.
Typestate Analysis. Regarding typestate properties, a set of observable operations accepted by the automaton, are valid traces. On
the other hand, a set of operation sequences not accepted by theautomaton, represent invalid traces which potentially violate typestate properties. Intuitively, vulnerabilities triggered by a sequenceof operations can be captured by typestate properties. Given a typestate property P, the typestate analysis problem for P is to determine
whether there exists a path p such that ∃o ∈ U(p) : p[o] < P.

3.2

live

Example 1. In Fig. 1, two memory objects pointed by pointers ptr 1
and ptr 2 are allocated at Lines 4 and 5. Regarding ptr 1, we identify thealiased pointer ptr 2 at Line 9. Then, the memory is freed at Line 10 by
ptr 1. Lastly, Line 14 accesses the memory again by the aliased pointerptr 2. Since Line 10 is reachable from Line 4 and Line 14 is reachable

Use-After-Free Detection Problem

In this paper, we focus on detecting the UaF vulnerability, andFig. 3 illustrates its typestate property. The alphabet for this problem consists of three operations, Σ = {malloc, free, use}. When the4Typestate-Guided Fuzzer for Discovering Use-after-Free Vulnerabilities

Source Code
Typestate
Property

Initial Seeds

Typestate Analysis
StaticAnalysis

Test
Pool

Operation
Sequences

Seed
Preservation

Seed
Selection

Seed

Power
Schedule

Fuzzing Loop

Operation Sequence
Instrumentation
Information Flow
Instrumentation

Operation Sequence
Coverage

Enegy

Adaptive
Mutation

Input-to-State
Relation

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea

Instrumentation

Algorithm 2: UAFL Instrumentation

Instrumented
Programinput : a program P , and a set of operation sequences S
output : an instrumented program P ′let OP_mem, OPE_mem and IFA_mem be shared memory;foreach ⟨s 0 , . . . , s n ⟩ ∈ S do
3⟨b0 , . . . , bm ⟩ ← BB_OP( ⟨s 0 , . . . , s n ⟩);4
foreach bi ∈ ⟨b0 , . . . , bm ⟩ do5
insert OP_mem[IDbi ] ← 1 into bi ;1
Execution

2
New
Seeds
Information
Flow Analysis

6
7

Figure 4: Workflow of typestate-guided fuzzing.
from Line 12, we identify an operation sequence 4 → 10 → 14. To be
more precise, if the memory free and use statements use the aliased
pointers, we incorporate the alias statement into the sequence. As aresult, we obtain the sequence 4 → 7 → 10 → 14 (c.f. Fig. 2(a)),
which violates the property of UaF.

8
9
10
11
12
13

14

4

TYPESTATE-GUIDED FUZZING
15

Given the operation sequences (OSs) identified by the static typestate analysis, we perform OS-guided instrumentation to steer the
fuzzing process, which can generate test cases to progressively
cover the type-state statement sequences at runtime. UAFL mainly
proposes two strategies to improve the effectiveness of the fuzzer.

16

4.2

insert OPE_mem[tID ⊕ IDbc j ] ++ into bc j ;let c j be comparison instruction cmp a, b;
insert IFA_mem[IDbc j ] ← a-b into bc j ;Instrumentation

Algorithm 2 presents the details of our instrumentation. The inputs of the algorithm are a program P and a set of identified OSs
S. The output is the instrumented program P ′ . From a high level,
the instrumentation mainly includes three steps: 1) use the sharedmemory OP_mem[] to record whether the operation statementsin the OSs are executed; 2) use the shared memory OPE_mem[] torecord whether the OS edges are covered; and 3) use the sharedmemory IFA_mem to record the values of variables in the comparison instructions for the future information flow analysis (Line 1).
It is worth noting, all elements of the three shared memory arrays
are initialized as zero before each execution.
The instrumentation is conducted on the basic block, for eachOS ⟨s 0, . . . , sn ⟩ we first get its basic block sequence ⟨b0, . . . , bm ⟩(Line 3). Note that the length of the basic block sequence may beless than the original OS, as some statements may belong to thesame basic block. Regarding each bi in the sequence, we instrument
it with OP_mem[IDbi ] ← 1 (Line 5), representing whether bi is
executed or not. The IDbi is the ID of basic block bi (c.f. Section 2.1).
In the second step, we perform the instrumentation to record thecoverage of OSs. Notice that, the OS is different from the P-path(c.f. Section 3.1). Specifically, an OS edge may need to execute asequence of CFG edges in P-path. For example, in Fig. 2(c), to cover
the OS edge 7 → 10, it needs to execute the CFG edges 8 → 9 and
9 → 10. Therefore, it is highly difficult to cover the OS edge directly.
Instead, we should first cover edge 8 → 9, and then 9 → 10.
To provide the fine-grained guidance for covering the OS edge,
we consider its dominated basic blocks. For example, regarding 7 →10 in Fig. 2(c), the parent basic blocks at Lines 8 and 9 in Fig. 1 areits dominated basic blocks. In particular, for each bi in the sequence,
UAFL analyzes the conditional statements Ci between bi−1 and bi ,bi is control-dependent on Ci (Line 7). For each statement c j ∈ Ci ,UAFL gets its parent basic block bc j (Line 9), and instruments bc j(1) We propose the OS-guided mechanism, which can guide UAFL
to generate test cases progressively covering the OSs. For example, to cover the sequence 4 → 7 → 10 → 14 in Fig. 2, UAFL
gradually generates the test cases to cover 4 → 7, 4 → 7 → 10,
and 4 → 7 → 10 → 14 in turn.
(2) With the guidance developed, we still require an equipped mutation strategy to coordinate it. UAFL utilizes an information
flow analysis to build the relationship between the input andvariables in the program. Based on the relationship, UAFL adaptively mutates the input to change the states of variables. Take
the program in Fig. 1 for example, the second and fourth bytes
of input buf are relevant to Lines 8 and 9, and UAFL mutates
them to generate a test case that can execute Line 10.

4.1

foreach bi ∈ ⟨b1 , . . . , bm ⟩ do
let C i be a set of conditional statements between bi −1 andbi , and bi is control-dependent on C i ;foreach c j ∈ C i dolet bc j be parent basic block of c j ;tID ← 0;
for 0 ≤ k < i do
if OP_mem[IDbk ] == 1 thentID ← tID ⊕ IDbk ;Fuzzing Workflow

Fig. 4 presents the fuzzing workflow. After identifying the OSs
by typestate analysis, we instrument OS-guided information into
the program. To achieve the two proposed strategies, we perform
two kinds of instrumentation: operation sequence instrumentationand information flow instrumentation (c.f. Section 4.2). During the
fuzzing loop, UAFL first selects a test case (i.e., the seed) from thetest pool (c.f. Section 4.4). UAFL then measures the quality of thisseed, and assigns an energy to it with the power scheduling strategy(c.f. Section 4.5). Next, we adopt the adaptive mutation strategy tomutate this seed and generate new seeds. The information flow
analysis is used to produce an adaptive mutation strategy (c.f. Section 4.3). After the new seeds are generated, UAFL checks whether
there is new OS coverage by running them. If so, the new seeds
are considered interesting and added into the test pool for further
mutation.
5

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea

Haijun Wang et al.

H (x |y, Vx , Vy ) denotes the conditional information entropy of variable x given the distribution of variable y:
H (x |y, Vx , Vy ) = −Σy j ∈Vy P(y = y j )(3)∗[Σx i ∈Vx P(x = x i |y = y j )loд2 P(x = x i |y = y j )]Algorithm 3: Mutation Probability Calculation
input : an program input x [m], and variables bv [n] at n
instructions
output : mutation probability prob[n]foreach i ∈ {0, . . . , m − 1} do
X = ∅, Y = ∅;3
foreach j ∈ {0, . . . , k } do4x ′ ← mutate(x [i]);5bv′ ← evaluate(x ′ , bv );6
X ← X ∪ {x ′ [i]};7Y ← Y ∪ {bv′ };Algorithm 3 mainly includes two steps. First, we compute theinformation flow strength between each byte of the input andvariables (i.e., a − b) in the target comparison instructions (Lines 18). The higher the information flow strength, the stronger thisbyte influences the values of the variables. Then, we assign higher
mutation possibility for these bytes of the input, as they are more
likely to change the values of target instructions (Lines 9-12).
The inputs of the algorithm consist of the array x[m] that is am-bytes program input and the array bv [n] that includes variables
in n comparison instructions, (i.e., a − b in cmp a, b). Its output is
an array prob that contains the mutation probability for each byte
of input x. For each byte of the input x (Line 1), we compute its
information flow strength to each variable in bv .
We use X and Y to store the sampling values for each byte ofx and each variable of bv (Line 2). We mutate each byte of x (i.e.,x[i]) with k times (Line 3) and get k values for each variable of bv .
Specifically, after each mutation, we get a new mutant x ′ (Line 4).
By running x ′ (Line 5), we can evaluate the values of variables
bv (c.f. IFA_mem[] at Line 16 in Algorithm 2). After generating
k samples, we compute the information flow strength between
x[i] and each variable of bv (Line 8). Notice that, for each x[i], we
compute n information flow strength values, and the maximum
value is considered as the information flow strength of x[i] (Line 8).
Based on the information flow strength, we calculate the mutation probability for each byte of input (i.e. x[i]) by the normalization(Line 9-12). Intuitively, if there is strong information flow between
x[i] and the program variables, it has a larger mutation probability.

1

2

8

E(x [i]) ← max j ∈{0, . . .,n−1} IFStrength(x [i], bv [j], X , Y [j]);minE ← min(E(x [0]), . . . E(x [m − 1]));
10 max E ← max (E(x [0]), . . . E(x [m − 1]));
11 foreach i ∈ {0, . . . , m − 1} do
E(x [i ])−minE12
pr ob[i] ← max
E−minE ;9with OPE_mem[tID ⊕ IDbc j ]++ (Line 14). Specifically, the variabletID is used to represent the execution information of ⟨b0, . . . , bi−1 ⟩(Lines 10-13). If bk is executed (i.e., OP_mem[IDbk ] == 1 at Line 12),
its ID is embedded into tID (Line 13). As a result, tID can be used to
guide the execution process toward bc j . tID would have a different
value when a new basic block bk ∈ ⟨b0, . . . , bi−1 ⟩ is executed. Thus,
the instrumentation can guide the fuzzing process to gradually
cover the operation sequences, named operation sequence feedback.
In the third step, we preform the information flow instrumentation to conduct information flow analysis. We assume that the conditional statement is a comparison instruction (e.g., cmp a, b). UAFL
records the values of a−b by instrumenting IFA_mem[IDbc j ] ← a-b
in the basic block bc j (Line 16).
Example 2. Given the OS edge 7 → 10 in Fig. 2(c), we assume
the basic block sequence is b7 → b10 and their IDs are IDb7 andIDb10 . When b7 is executed, we instrument b10 with OPE_mem[IDb7 ⊕IDb10 ]++. Otherwise, the instrumentation OPE_mem[IDb10 ]++ is inserted into b10 . Thereby, our instrumentation can differentiate whether
b7 is executed or not once we reach b10 at runtime.

4.3

Example 3. In Fig. 1, given an input buf=‘aaaaaaa’, assume thetarget instruction is buf[3] ==‘s’ at Line 8, we consider the information flow strength between the bytes of input (i.e., bu f [3] and bu f [6])and the variable (bu f [3]−‘s’) at Line 8. Assume each byte is mutatedwith 10 times (i.e., k = 10 in Algorithm 3), then we figure out the
information flow strength: 3.3 for buf[3] and 0 for buf[6]. It suggeststhat there is a strong information flow between bu f [3] and the condition at Line 8. To cover this branch (i,e, bu f [3] ==‘s’), we will assign
more mutations on buf[3].

Information Flow Analysis based Mutation

With the OSs and their dominated basic blocks identified, the nextchallenge is to find a way to perform the mutations so that the OSs
can be covered quickly. For an instruction cmp a, b, the basic idea isthat: we first identify which part of the input can change the valuesof a − b, then we can focus the resource on mutating this part ofthe input until its condition is satisfied. We adopt an information
flow analysis to identify the relationship between the input and theprogram variables in the comparison instructions.
Information Flow Strength. We follow the information flow
definition in [26], and compute the information flow strength fromvariable x to variable y as follows:
IFStrength(x, y, Vx , Vy ) = H (x, Vx ) − H (x |y, Vx , Vy )(1)where Vx and Vy are the value domains of variables x and y, respectively. H (x, Vx ) denotes the information entropy measuring
the uncertainty of variable x.
H (x, Vx ) = −Σx i ∈Vx P(x = x i )loд2 P(x = x i )
(2)

4.4

Seed Selection

The seed selection step is to select the next test case from the test
pool such that it is more likely to cover the target OSs with somemutations on the selected test case. Motivated by the technique [8],UAFL provides a three-tiered queue, which classifies the generated
seeds into different categories based on their scores. The seeds
in the top-tiered queue have the highest priority, followed by thesecond-tiered, and finally the lowest-tiered.
These three tiers are designed based on the OS edge (e.g, 7 → 10
and 10 → 14 in Fig. 2) and CFG edge coverage (e.g., 8 → 9 and
9 → 10). Specifically, given a newly generated seed, (1) if it covers a
new OS edge, we add it into the top-tiered queue, (2) if it covers a
new CFG edge, we add it into the second-tiered queue, otherwise(3) the seed is added into the lowest-tiered queue. Intuitively, UAFL
6

Typestate-Guided Fuzzer for Discovering Use-after-Free Vulnerabilities

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea

favors the seeds that cover new OS edges, since it has more chances
to cover the target OS. If the seed does not cover any new OS edge
but covers a new CFG edge, which are control-dependent on thestatements of the OS (refer to Line 7 in Algorithm 2), it still makes
a small step towards covering the whole OS.

5.1.1 Baseline Fuzzers. To evaluate the effectiveness of UAFL, weselect 6 representative state-of-the-art fuzzers, which incorporate
diverse advanced techniques to improve the effectiveness of fuzzing.
(1) AFL [47] is the most popular baseline fuzzer, which is studiedin most coverage-based fuzzers.
(2) AFLFast [4] is an advanced variant of AFL with a better powerscheduling that was incorporated into the later versions of AFL.
(3) FairFuzz [21] monitors the program executions, and computes
the key patterns inside a seed to reach rare CFG edges.
(4) MOpt [25] adopts a customized Particle Swarm Optimization(PSO) algorithm to schedule the mutation operations, whichenables more efficient discovery of vulnerabilities.
(5) Angora [9] utilizes taint analysis to track information flow, andthen uses gradient descent to break through the hard branches.
(6) QSYM [46] is an effective symbolic execution assisted fuzzer.

Example 4. In Fig 2, a newly generated test case, which covers the
new OS edge 7 → 10, is prioritized in the top-tiered queue since it iscloser to cover the target OSs. However, if it does not cover 7 → 10
but CFG edge 8 → 9, it is also added into the second-tiered queue as
it executes towards to 7 → 10.

4.5Power Scheduling

The power scheduling concerns about how many mutation chances
are assigned to the given test case. A test case that has more chances
to cover OSs with mutations should be assigned with more energy.
Existing coverage-based fuzzers (e.g., AFL) usually calculate theenergy for the selected test case as follows [23]:enerдy(i) = allocate_enerдy(qi )where i is the seed and qi is the quality of the seed, depending on
the execution time, branch edge coverage, creation time and so on.
UAFL considers the OS edge coverage and updates the existing
power scheduling as follows:#c_OSe)enerдy(i) ′ = enerдy(i) ∗ (1 +#t_OSewhere #t_OSe represents the total number of OS edges, and #c_OSe
denotes the number of OS edges that are covered by seed i. Intuitively, the number of covered OS edges implies how close the seeds
are to OSs. Thus, UAFL assigns higher energy to seeds closer to
OSs for them to have more chances to cover more OS edges with
mutations.

55.1.2 Benchmark Programs. We consider the benchmark programswith the following factors: frequency of being tested in related
work, popularity of being used by end users, and their functionality
diversities. Finally, we select 14 widely-used programs as our benchmark, including the well-known development tools (e.g., readelf 2.28,
readelf 2.31), code processing tools (e.g., mjs, Mini XML, GNU cflow,nasm), graphics processing libraries (e.g., ImageMagick, jpegoptim),compression tools (e.g., lrzip and openh264), data processing libraries (e.g., libpff and liblouis), an encryption key management
tool (e.g., boringssl) and a Satisfiability Modulo Theories solver (e.g.,boolector). For each program, we select the version that includes
the UaF vulnerabilities (c.f. Column Version in Table 1).
5.1.3 Configuration Parameters. The effectiveness of fuzzers heavily replies on the random mutations, thus there may be performancedeviation in the evaluation. Following Klees’s suggestions in [18],we take three actions to mitigate performance deviation. First, wetest each program for a longer time, until the fuzzer reaches a relatively stable state. In the paper, we run each fuzzer for 24 hours.
Second, we perform each experiment for 8 times, and evaluate theirstatistical performance. Third, for the initial seeds, if the programs
provide the sample seed inputs, we use them as the initial seeds.
Otherwise, we randomly download some input files from the internet, according to the required input file formats. All the initial seeds
can be found in our website [34]. All our experiments have been
performed on machines with an Intel(R) Xeon(R) CPU E5-1650 v4(3.60GHz) and 16GB of RAM under 64-bit Ubuntu LTS 18.04.

EVALUATION

We have implemented the static typestate analysis on top of an interprocedural static value-flow analysis tool called SVF [32], which
is able to perform scalable and precise interprocedural dependence
analysis for C and C++ programs. This part takes about 4000 lines of
C/C++ code. In the instrumentation component, we have designed
three bulks of shared memory that tracks the execution information.
The instrumentation consists of about 2000 lines of C/C++ code.
The fuzzing engine is implemented based on the AFL version 2.51b,
where we have implemented the information flow analysis based
mutation. We added about 1000 lines of C/C++ codes into this part.

5.1

5.2

Static Typestate Analysis Statistics (RQ1)

In Table 1, we present the static typestate analysis results for benchmark programs. The first three columns denote the basic information of programs, including program names, their versions, andlines of code. We can see that the chosen programs have high diversities in terms of program size, from 2k to 1,781k lines of code.
Column T_BB lists the number of total basic blocks in the program. Column BBUAF presents the number of basic blocks in OSs,
which may violate the UaF typestate property. Specifically, UAFL
instruments 19.2% of the basic blocks on average, to provide operation sequence feedback. Column BBIF denotes the number ofbasic blocks in which we perform the information flow instrumentation. To calculate the information flow strength, UAFL performs

Evaluation Setup

In the experiments, we aim to answer the following questions:
RQ1 - What is the effectiveness of the static typestate analysis for
UaF vulnerabilities?
RQ2 - How effective is UAFL in discovering UaF vulnerabilities?
RQ3 - How effective are the two strategies in UAFL, i.e., operation
sequence feedback and information flow based mutation?
RQ4 - How is the code coverage relevant to UaF vulnerabilities?
Following Klees’s suggestions in [18], we conduct a large-scale
experiment and compare UAFL with state-of-the-art fuzzers.
7

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea

Haijun Wang et al.

Table 1: Static Typestate Analysis Results
Programreadelf
readelf
jpegoptim
liblouis
lrzipMini XMLboringssl
GNU cflow
Boolector
openh264
libpffmjs
ImageMagick
nasm
Avg.

Version
2.28
2.31
1.45
3.2.0
0.631
2.12
—
1.6
3.0.0
1.8.0
—
1.20.1
7.0.8
2.14
-

LoC
1,781k
1,758k
2k
53k
19k
15k
162k
50k
141k
143k
125k
40k
485k
101k
348k

T_BB
16,967
19,973
634
2,957
9,356
4,237
22,547
5,095
26,866
12,735
18,5694,937
31,19013,965
13,573BBUAF
2,681 (15.8%)
3,647 (18.2%)
36 (5.7%)
486 (16.4%)
1,051 (11.2%)
890 (21.0%)
3,701 (16.4%)
1,402 (27.5%)
11,511 (42.8%)
2,090 (16.4%)
6,371 (34.3%)
546 (11.0%)
1,573 (5.0%)
3,812 (27.2%)
2,842 (19.2%)

BBIF
1,103 (6.5%)
1,555 (7.8%)
28 (4.4%)
190 (6.4%)
467 (5.0%)
788 (18.6%)
3,265 (14.4%)751 (14.7%)
9,031 (33.6%)
927 (7.3%)
6,041 (32.5%)343 (6.9%)
1,336 (4.3%)
3,390 (24.2%)
2,087 (13.3%)

BBFree
91
98
5
8
6
10
32
33
4
1
60
16
3
2
26

#OS
41,605130,102
44
422
313
486
84,0694330
28,586
1,219
20,865
1,143
55,8773,357
26,601

T(s)
262
508
1
18
150
44
2,005
30
2,387
1,127
122
24
2,185
2,210
1,148

Table 2: Time to Expose Uaf Vulnerabilities in 8 State-of-the-Art Fuzzers
ProgramVulnerabilities

readelf-2.28
readelf-2.31
jpegoptim
liblouis
lrzipMini XMLboringssl
GNU cflow
Boolector
openh264
libpffmjs
ImageMagick
nasm

*
*

CVE-2017-6966
CVE-2018-20623
CVE-2018-11416
CVE-2017-13741
CVE-2018-11496
CVE-2018-20592
Google Test-suit
uaf-issue-1
uaf-issue-2
uaf-issue-3
uaf-issue-4
uaf-issue-5
uaf-issue-6
CVE-2018-19216
CVE-2018-20535
Missed Vulnerabilities
Avg. Time Usage
UAFL’s Speedup
UAFLN oI F ’s Speedup

UAFL
0.59
0.10
0.09
1.11
0.01
0.38
0.33
1.80
0.83
8.17
1.39
1.21
6.29
2.59
17.03
0
2.79 + 0.32——

Time Usage to Expose the Vulnerabilities (hours)
UAFLN oI F
AFL AFLFast FairFuzz MOpt Angora
1.32
6.09
1.43
0.68
3.61
T/O
0.10
0.10
0.10
T/O
0.10
0.02
0.10
0.59
0.88
1.08
1.49
T/O
1.81 15.81
T/O
6.96
17.38
T/O
0.01
0.01
0.01
0.01
0.01
0.01
0.93
1.28
2.59
0.54
16.7
T/O
1.06
T/O
T/O
4.67
7.62
–
12.21 23.29
T/O
20.02
T/O
T/O
0.97
1.09
0.82
0.39
1.66
–
13.00 15.80
11.15
8.17
15.39
T/O
1.39
4.21
4.11
3.98
4.35
T/O
1.23
3.10
3.02
1.45
4.6
T/O
13.92
T/O
T/O
T/O
T/O
T/O
4.69
8.32
3.45
2.86
11.46
2.75
T/O
T/O
T/O
T/O
T/O
T/O
1
3
5
3
3
10
5.12 + 0.32 10.11
9.84
8.18
10.42
18.67
1.75× 3.25×
3.16×
2.63× 3.35×
6.00×— 1.86×
1.81×
1.50× 1.92×
3.43×

QSYM
6.20
0.10
1.95
13.42
0.01
18.99
T/O
T/O
1.16
18.45
4.98
6.71
T/O
9.64
T/O
4
11.84
3.80×
2.18×

T/O means the fuzzer cannot discover vulnerabilities within 24 hours across 8 runs. When we calculate the average time usage, we replace T/O with 24 hours.
Angora does not work on the programs boringssl and Boolector, denoted by ‘-’, because it throws the exceptions during the instrumentation.

the instrumentation on an average of 13.3% of basic blocks. The
experiment results show that, with less instrumentation (total 32.5%
in both operation sequence and information flow instrumentation),
UAFL can concentrate more power and energy on the OSs which
may violate the typestate property of UaF.
Column BBFree shows the number of static memory-free instructions. Column #OS presents the number of operation sequences
identified by static typestate analysis. It reports on average 26, 601
OSs in each program. Since UAFL adopts the path-insensitive reachability analysis, it produces too many false positives. Thus, weemploy the fuzzing to confirm whether these OSs really trigger UaF
vulnerabilities. In the last column T (s), we list the time overhead forstatic typestate analysis. In all programs, UAFL requires less than
one hour, i.e., avg. 1, 148s (0.32 hour), to conduct the static typestate

analysis. Compared to the long time fuzzing process (e.g., 24 hours),
the time overhead for static typestate analysis is acceptable.
RQ1: The results show that the time overhead incurred in
the static typestate analysis of UAFL is acceptable, with anaverage of 1,148s (0.32 hour). On average, 19.2% and 13.3%
of basic blocks are instrumented, respectively, for operation
sequence feedback and information flow analysis.

5.3

Vulnerability Detection Results (RQ2)

As suggested by Klees [18], the vulnerabilities found are ideal tomeasure the effectiveness of fuzzers. We evaluate the fuzzers withthe time used for discovering UaF vulnerabilities.
8Typestate-Guided Fuzzer for Discovering Use-after-Free Vulnerabilities

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea

cflow
480

FairFuzz
Angora
AFLfast
AFL

20

15

5

10

UAFLNoIF
UAFL
QSYM
MOpt

time (hour)boringssl

1800

20

15

10

5

500
475
450
425
400
375
350
325
300

UAFLNoIF
UAFL
QSYM
MOpt

FairFuzz
Angora
AFLfast
AFL

time (hour)

200# OS Edgetime (hour)

15

time (hour)

FairFuzz
Angora
AFLfastAFL

FairFuzz
AFLfastAFL

readelf 2.28

10

15

10

5

0

UAFLNoIF
UAFL
QSYM
MOpt

UAFLNoIF
UAFL
QSYM
MOpt

1000

20

170
160
150
140
130
120

1200

5

time (hour)

FairFuzz
Angora
AFLfast
AFL

1400

20

15

10

5

UAFLNoIF
UAFL
QSYM
MOpt

# OS Edge

1600

liblouis# OS Edge

440
420

nasm

2900
2800
2700
2600
2500
2400
2300
2200
2100

0

# OS Edgetime (hour)

FairFuzz
Angora
AFLfast
AFL

0

5

0

250

15

UAFLNoIF
UAFL
QSYM
MOpt

460

20

300

# OS Edge

350

10# OS Edge

400

Figure 5: Code coverage relevant to operation sequences.
By comparing the results, it shows that UAFLN oI F is still better
than other fuzzers in most cases. For example, UAFLN oI F averagely takes 5.12 hours to discover each vulnerability, achieving the
speedups of 1.86×, 1.81×, 1.50×, 1.91×, 3.43×, and 2.18× over otherfuzzers, respectively. Similarly, the statistical test also shows that
UAFLN oI F is more effective in most cases. The results demonstrate
the effectiveness of the operation sequence feedback.
By comparing the results of UAFL and UAFLN oI F , we find that
UAFL performs better than UAFLN oI F in each program. Specifically,
UAFL achieves 1.75× improvement over UAFLN oI F . It is worth
noting, UAFLN oI F cannot find the UaF (i.e., CVE-2018-20535) in the
program nasm within 24 hours. However, with the information flow
based mutation incorporated, UAFL can discover the vulnerability
with 17.03 hours. The results demonstrate the effectiveness of theinformation flow based mutation.

Statistical Test. To mitigate the randomness, we conducted the statistical test for the experiment results. The Vargha-Delaney statistic(Â12 ) is a non-parametric measure of effect size, and usually used
to measure the randomized algorithms [3]. Given the time usage
in UAFL and other fuzzers, the Â12 statistic measures the probability that UAFL performs better than others. Moreover, we alsouse Mann-Whitney U to measure the statistical significance of performance gain. When it is significant, we mark the Â12 values inbold. In the column Â12 (UAFL) of Table 3, we can see that UAFL
significantly performs better than other fuzzers in most cases.
RQ2: From Tables 2 and 3, UAFL performs significantly better
than other fuzzers in most cases. UAFL achieves a speedup of
3.25×, 3.16×, 2.63×, 3.35×, 6.00×, and 3.80×, compared to AFL,
AFLFast, FairFuzz, MOpt, Angora, and QSYM, respectively.

5.4

mjs

450

0

Table 2 shows the time usage to discover the unique UaF vulnerability. The first two columns list the program names, and thevulnerability ID. The following columns presents the results for eachfuzzer. Compared to state-of-the-arts fuzzers (e.g., AFL, AFLFast,
FairFuzz, MOpt, Angora, and QSYM), UAFL takes much less time(i.e., avg. 2.79 hours) while others need about 10 hours. Even if thetime overhead (i.e., avg. 0.32 hours) in static typestate analysis isadded, UAFL is still more effective than others. Row UAFL’s Speedup
shows the average speedup achieved by UAFL: a speedup of 3.25×,
3.16×, 2.63×, 3.35×, 6.00×, and 3.80× respectively, compared withthe other fuzzers.
For shallow vulnerabilities (e.g., readelf-2.31, lrzip), all fuzzers
work well; but for deep/hard vulnerabilities, e.g., liblouis, GNU cflow,
and ImageMagick, UAFL performs much better than the others. For
example, UAFL takes about 1.80 hours to discover UaF in GNU
cflow, while other fuzzers almost spend about 20 hours.
In addition, of the 15 vulnerabilities, UAFL performs the bestin 13 (86.7%) vulnerabilities. In the program readelf-2.31, Angora
performs the best, and FairFuzz achieves the best performancein Boolector. A close investigation reveals the reason behind isthat these fuzzers’ objectives coincidentally fit with the UaF. For
example, FairFuzz aims to cover rare CFG edges and the memoryfree statement in Boolector is under such rare CFG edges. Thus,
FairFuzz has high chance to detect the UaF after covering the freestatement. Different with other tools, UAFL is designed based on
the typestate properties. Hence, UAFL performs more stably, andachieves better performance for most programs.
Row Missed Vulnerabilities shows the number of UaF vulnerabilities which cannot be discovered by each fuzzer. AFL, AFLFast,
FairFuzz, MOpt, Angora and QSYM missed 3, 5, 3, 3, 10, and 4
vulnerabilities within 24 hours, respectively.

RQ3: The two strategies used in UAFL are both effective. The
comparative results between UAFLN oI F and other tools show
the effectiveness of operation sequence feedback. The comparative results between UAFL and UAFLN oI F show the contribution of the information flow analysis based mutation.

Evaluation of the Strategies (RQ3)

UAFL mainly adopts the operation sequence feedback and information flow analysis based mutation strategies to enhance thecapability of UaF detection. To evaluate the effectiveness of eachstrategy, we configure a new fuzzer UAFLN oI F , which only incorporates operation sequence feedback strategy but not the information
flow analysis. The experiment results of UAFLN oI F is shown under
the column UAFLN oI F in Table 2 and Â12 (UAFLN oI F ) in Table 3.

5.5

Code Coverage (RQ4)

Although there is no fundamental connection between maximizing
code coverage and finding more vulnerabilities [18], the generalefficacy of grey-box fuzzers over black-box ones means the certain
correlation. It is believed that the code coverage makes sense as asecondary measure for the effectiveness of fuzzers. In this section,
9

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea

Haijun Wang et al.

Table 3: Statistical Test for Time-to-Exposure UaF Vulnerabilities
ProgramVulnerability

readelf
readelf
jpegoptim
liblouis
lrzipMini XMLboringssl
GNU cflow
Boolector
openh264
libpffmjs
ImageMagick

CVE-2017-6966
CVE-2018-20623
CVE-2018-11416
CVE-2017-13741
CVE-2018-11496
CVE-2018-20592
Google Test-suit
uaf-issue-1
uaf-issue-2
uaf-issue-3
uaf-issue-4
uaf-issue-5
uaf-issue-6
CVE-2018-19216
nasm
CVE-2018-20535
Significant better (A12 > 0.71, bold)* We highlight the Â

AFL
0.906
0.500
0.995
0.828
0.500
0.968
1.000
1.000
0.720
0.937
1.000
0.980
1.000
0.960
1.000
11/15

AFLFast
0.898
0.500
1.000
0.937
0.500
1.000
1.000
1.000
1.000
0.781
1.000
0.980
1.000
0.600
1.000
12/15

Â12 (UAFL)
FairFuzz MOpt
1.000
0.609
0.500
0.500
1.000
1.000
0.851
1.000
0.500
0.500
0.812
1.000
1.000
1.000
1.000
1.000
0.030
0.880
0.150
1.000
1.000
1.000
0.590
1.000
1.000
1.000
0.560
0.920
1.000
1.000
9/15
12/15

Angora
1.000
0.000
1.000
1.000
0.500
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
0.600
1.000
12/15

AFL
0.796
0.500
0.995
0.875
0.500
0.617
1.000
0.937
0.620
0.687
1.000
0.880
1.000
0.800
0.500
9/15

AFLFast
0.546
0.500
1.0
0.937
0.500
0.929
1.000
0.968
1.000
0.359
1.000
0.890
1.000
0.319
0.500
9/15

Â12 (UAFL N oI F )FairFuzz MOpt
1.000
0.453
0.500
0.500
1.000
1.000
0.867
1.000
0.500
0.500
0.750
0.781
0.828
1.000
0.609
0.968
0.020
0.820
0.031
0.640
1.000
1.000
0.604
0.987
1.000
1.000
0.280
0.840
0.500
0.500
7/15
9/15

Angora
1.000
0.000
1.000
1.000
0.500
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
0.280
0.500
11/15

QSYM
0.828
0.500
1.000
0.968
0.500
0.781
1.000
1.000
0.720
0.875
1.000
0.987
1.000
0.800
0.500
10/15

12 in the bold if its corresponding Mann-Whitney U test is significant.

we only calculate the code coverage identified by the typestate
analysis because 1) only they can help find the UaF vulnerabilities;
and 2) the coverage can measure how close the generated test cases
are to UaF vulnerabilities, thus can signify the quality of generated
test cases. We evaluate the code coverage in UAFL, UAFLN oI F , AFL,
AFLFast, FairFuzz, MOpt, Angora, and QSYM. We only show here
the results for 6 programs in which the UaF vulnerabilities are hardto detect, the rest can be found from our website [34].
Fig. 5 presents the code coverage achieved by 8 state-of-the-art
fuzzers. In the early stage, all 8 fuzzers show the similar code coverage growth. As the time goes on, the code coverage in UAFL and
UAFLN oI F grows faster than the other 6 fuzzers. At the end of 24hours, UAFL and UAFLN oI F almost achieve the best code coverageamong all eight fuzzers. The code coverage also reflects why UAFL
and UAFLN oI F perform better in discovering vulnerabilities thanothers, as shown in Table 2. For other fuzzers, the results in AFL,
AFLFast, MOpt, Angora, and QSYM are close to each other. FairFuzz
averagely performs better than the other 5 fuzzers. After investigating the fuzzing process in FairFuzz, we find that some edges
in OSs of UaF are rarely covered, which is in accordance with thetarget of FairFuzz. Although FairFuzz can cover some rare edges
individually, it is still challenging to cover the whole operation
sequences. Hence, it is less effective to discover UaF than UAFL.
Another example is program readelf-2.28, where Angora achieves
the best code coverage. However, Angora does not discover the UaF
vulnerability as shown in Table 2. This is because Angora covers
only individual edges but not the sequences.

to identify operation sequences violating the typestate property,
and then focuses its resource on these sequences, imposing lesspower for exercising other parts of the program. Thus, UAFL iscomplementary to existing coverage-based fuzzers to find the vulnerabilities that violate the typestate property.
One threat to validity is that, it may cause a certain sample bias
when selecting programs to evaluate the capabilities of UAFL indiscovering UaFs. To address this issue, we have selected a wide
range of real-world programs, which have different functionalities
and are frequently used in others’ work. In addition, each experiment is conducted 8 times to mitigate the randomness factor. Dueto the unique characteristics of UaF (i.e., malloc → free → use), we
believe that the real-world UaF vulnerabilities found by UAFL arerepresentative.

6

RELATED WORK

We discuss some closely related work in the following topic areas.
Typestate Analysis. Typestate analysis is a widely used techniquein formal verification [13–15]. However, as proved by Field et al., thetypestate verification problem becomes NP-hard for programs withmaximum aliasing width of three and aliasing depth of two [14].
This limits the practical usefulness of typestate verification on large
programs. To tackle this problem, Hua et al. introduced machinelearning-guided typestate analysis for static UaF detection [41]. Theyleverage machine learning techniques to reduce the overhead oftypestate analysis, making it scalable to large-size programs. Chenet al. [45, 48] proposed a regular property guided symbolic execution to verify whether there is a path in the program satisfying
the given property. These techniques are different from UAFL in
two ways: (1) they employ symbolic execution while we enhance
the fuzzing technique; and (2) they identify only a program pathsatisfying the property while we find all possible program paths
violating the property. These works bring insights for UAFL, andwe provide another approach to applying typestate analysis byincorporating it into fuzzing.
Use-After-Free Run-time Protection. Since UaF vulnerabilities
are highly exploitable [40], many works are proposed to protect
the program via early detection of UaF [5, 19, 35, 44]. Most of theseworks eliminate UaF vulnerabilities by capturing the existence of
dangling pointers and disposing. This is because dangling pointers
are the hotbed for UaF vulnerabilities. For example, in [19], a pointer

RQ4: Compared to other fuzzers, UAFL and UAFLN oI F
achieve better code coverage relevant to UaF vulnerability,
which also explains why UAFL and UAFLN oI F are more effective in discovering UaF vulnerabilities.

5.6

QSYM
0.968
0.500
1.000
0.984
0.500
1.000
1.000
1.000
0.780
1.000
1.000
1.000
1.000
0.800
1.000
12/15

Discussion and Threat to Validity

This paper evaluates our proposed typestate-guided fuzzer for detecting UaF vulnerabilities. Due to the high expressiveness of typestate property, our approach can be extended to detect other typesof vulnerabilities. For example, we can extend UAFL to detect APImisuse [2], e.g., file read/write operations by customizing the typestate property. On the other hand, UAFL adopts the typestate analysis
10Typestate-Guided Fuzzer for Discovering Use-after-Free Vulnerabilities

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea

is nullified once the corresponding memory is freed. This effectively
turns the UaF bug into a null-pointer dereference, which is muchless harmful. These works are orthogonal to UAFL as they focus on
capturing and monitoring the UaF behaviors while UAFL focuseson discovering and triggering UaF vulnerabilities.
Use-After-Free Static Detection. Besides the dynamic approach
proposed in this paper, researchers also proposed several static
approaches for UaF discovery [30, 41, 42]. These approaches rely
heavily on pointer analysis, which bears a dilemma in nature. The
dilemma is that we need to sacrifice a lot of scalability in exchange
of a small amount of increment in precision and the result canstill suffer from high false positives. Comparing with these static
approaches, UAFL strikes a balance by having no false positive(every UaF found is associated with a proof-of-crash input) as wellas good scalability (only light-weight static analysis is needed andthe rest is handled by the dynamic part).
Greybox Fuzzing. Recently, lots of greybox fuzzing techniques
have been proposed to detect various types of bugs [1, 4, 6, 9, 16, 21–
23, 25, 28, 29, 31, 46]. These techniques either enhance the different
components of the greybox fuzzer [4, 16, 21–23, 25] or combine greybox fuzzing with other techniques such as static analysis [23, 29],
symbolic execution [31, 46], or taint analysis [9, 28]. These techniques are general purpose techniques which are not designed todetect a specific type of bugs with more effectiveness. With theexperiments in Section 5, it is demonstrated that UAFL can substantially outperform these general purpose fuzzers in UaF detection.
Besides the general purpose greybox fuzzers, there are also directed
greybox fuzzers to quickly reach target locations [3, 8]. Comparing
with the directed fuzzers, UAFL does not require prior knowledge
about the locations of UaF bugs for reaching and detection. Other
than the general purpose and directed greybox fuzzers, researchers
also proposed fuzzing techniques for finding specific types of bugs,
such as slowfuzz [27], perffuzz [20], MemLock [39]. However, noneof them is designed for UaF bugs and to the best of our knowledge, UAFL is the first greybox fuzzer specialized in detecting UaF
vulnerabilities.

7

Prime Ministers Office, Singapore under its National Cybersecurity R&D Program (Award No. NRF2018NCR-NCR005-0001), theSingapore National Research Foundation under NCR Award Number NRF2018NCR-NSOE004-0001, and Australia Research Council(Grant No. DP200101328).

REFERENCES[1] Cornelius Aschermann, Sergej Schumilo, Tim Blazytko, Robert Gawlik, andThorsten Holz. 2019. REDQUEEN: Fuzzing with Input-to-State Correspondence.
In 26th Annual Network and Distributed System Security Symposium (NDSS’19).
The Internet Society, San Diego, CA USA, 1–15.
[2] SungGyeong Bae, Hyunghun Cho, Inho Lim, and Sukyoung Ryu. 2014. SAFEWAPI: web API misuse detector for web applications. In Proceedings of the 22nd
ACM SIGSOFT International Symposium on Foundations of Software Engineering.
ACM, 507–517.
[3] Marcel Böhme, Van-Thuan Pham, Manh-Dung Nguyen, and Abhik Roychoudhury. 2017. Directed Greybox Fuzzing. In Proceedings of the 2017 ACM SIGSAC
Conference on Computer and Communications Security. ACM Press, 2329–2344.
[4] Marcel Böhme, Van-Thuan Pham, and Abhik Roychoudhury. 2016. Coveragebased Greybox Fuzzing As Markov Chain. In Proceedings of the 2016 ACM SIGSAC
Conference on Computer and Communications Security. ACM Press, 1032–1043.
[5] Juan Caballero, Gustavo Grieco, Mark Marron, and Antonio Nappa. 2012. Undangle: early detection of dangling pointers in use-after-free and double-freevulnerabilities. In Proceedings of the 2012 International Symposium on Software
Testing and Analysis. ACM, 133–143.
[6] Hongxu Chen, Yuekang Li, Bihuan Chen, Yinxing Xue, and Yang Liu. 2018. FOT:
A Versatile, Configurable, Extensible Fuzzing Framework (FSE ’18 tool demo).
[7] Haogang Chen, Yandong Mao, Xi Wang, Dong Zhou, Nickolai Zeldovich, andM Frans Kaashoek. 2011. Linux kernel vulnerabilities: State-of-the-art defenses
and open problems. In Proceedings of the Second Asia-Pacific Workshop on Systems.
ACM, 5.
[8] Hongxu Chen, Yinxing Xue, Yuekang Li, Bihuan Chen, Xiaofei Xie, Xiuheng Wu,
and Yang Liu. 2018. Hawkeye: Towards a Desired Directed Grey-box Fuzzer. In
Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications
Security. ACM, New York, NY, USA, 2095–2108.
[9] Peng Chen and Hao Chen. 2018. Angora: Efficient fuzzing by principled search.
In 2018 IEEE Symposium on Security and Privacy. IEEE, 711–725.
[10] Yaohui Chen, Peng Li, Jun Xu, Shengjian Guo, Rundong Zhou, Yulong Zhang
Zhang, Tao Wei, and Long Lu. 2020. SAVIOR: Towards Bug-Driven Hybrid
Testing. In 2020 IEEE Symposium on Security and Privacy. IEEE.
[11] Mauro Conti, Stephen Crane, Lucas Davi, Michael Franz, Per Larsen, Marco
Negro, Christopher Liebchen, Mohaned Qunaibit, and Ahmad-Reza Sadeghi.
2015. Losing control: On the effectiveness of control-flow integrity under stackattacks. In Proceedings of the 22nd ACM SIGSAC Conference on Computer andCommunications Security. ACM, 952–963.
[12] Crispan Cowan, Calton Pu, Dave Maier, Jonathan Walpole, Peat Bakke, Steve
Beattie, Aaron Grier, Perry Wagle, Qian Zhang, and Heather Hinton. 1998. Stackguard: Automatic adaptive detection and prevention of buffer-overflow attacks..
In USENIX Security Symposium, Vol. 98. San Antonio, TX, 63–78.
[13] Ankush Das, Shuvendu K. Lahiri, Akash Lal, and Yi Li. 2015. Angelic Verification: Precise Verification Modulo Unknowns. In Proceedings of 27th International
Conference on Computer Aided Verification. San Francisco, CA, USA, 324–342.
[14] John Field, Deepak Goyal, G. Ramalingam, and Eran Yahav. 2003. Typestate
Verification: Abstraction Techniques and Complexity Results. In Static Analysis,
Radhia Cousot (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 439–462.
[15] Stephen Fink, Eran Yahav, Nurit Dor, G. Ramalingam, and Emmanuel Geay. 2006.
Effective Typestate Verification in the Presence of Aliasing. In Proceedings of the2006 International Symposium on Software Testing and Analysis. ACM, 133–144.
[16] Shuitao Gan, Chao Zhang, Xiaojun Qin, Xuwen Tu, Kang Li, Zhongyu Pei, andZuoning Chen. 2018. CollAFL: Path Sensitive Fuzzing. In 2018 IEEE Symposium
on Security and Privacy. IEEE Press, 1–12.
[17] Google Inc. 2019. ClusterFuzz. https://google.github.io/clusterfuzz/[18] George Klees, Andrew Ruef, Benji Cooper, Shiyi Wei, and Michael Hicks. 2018.
Evaluating Fuzz Testing. In Proceedings of the 2018 ACM SIGSAC Conference on
Computer and Communications Security. ACM, 2123–2138.
[19] Byoungyoung Lee, Chengyu Song, Yeongjin Jang, Tielei Wang, Taesoo Kim,
Long Lu, and Wenke Lee. 2015. Preventing Use-after-free with Dangling Pointers
Nullification. In 22nd Annual Network and Distributed System Security Symposium.
[20] Caroline Lemieux, Rohan Padhye, Koushik Sen, and Dawn Song. 2018. PerfFuzz:
Automatically Generating Pathological Inputs. In Proceedings of the 27th ACM
SIGSOFT International Symposium on Software Testing and Analysis. ACM, 254–265.
[21] Caroline Lemieux and Koushik Sen. 2018. FairFuzz: A Targeted Mutation Strategy for Increasing Greybox Fuzz Testing Coverage. In Proceedings of the 33rd
ACM/IEEE International Conference on Automated Software Engineering. ACM,

CONCLUSION

In this paper, we propose a typestate-guided fuzzer UAFL for discovering vulnerabilities violating typestate properties, e.g. UaF vulnerabilities. We first employ a typestate analysis to extract operation
sequences violating a given typestate property, which are then used
to guide the fuzzing process to generate test cases progressively
towards these operation sequences. We also adopt information
flow analysis to guide the mutation process to improve the efficiency of the fuzzing process. Our experimental results have shownthat UAFL substantially outperforms the state-of-the-art fuzzers,
including AFL, AFLFast, FairFuzz, MOpt, Angora and QSYM, indiscovering UaF vulnerabilities.

ACKNOWLEDGMENTS
This work was supported in part by Ant Financial Services Groupthrough Ant Financial Research Program, the National Natural Science Foundation of China (Grant No. 61772347,61836005, 61972260),
Singapore Ministry of Education Academic Research Fund Tier 1(Award No. 2018-T1-002-069), the National Research Foundation,
11

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea

Haijun Wang et al.

475–485.
[22] Yuekang Li, Bihuan Chen, Mahinthan Chandramohan, Shang-Wei Lin, Yang Liu,and Alwen Tiu. 2017. Steelix: Program-state Based Binary Fuzzing. In Proceedingsof the 2017 11th Joint Meeting on Foundations of Software Engineering (ESEC/FSE
2017). ACM, New York, NY, USA, 627–637. https://doi.org/10.1145/3106237.
3106295[23] Yuekang Li, Yinxing Xue, Hongxu Chen, Xiuheng Wu, Cen Zhang, Xiaofei Xie,
Haijun Wang, and Yang Liu. 2019. Cerebro: Context-aware Adaptive Fuzzing
for Effective Vulnerability Detection. In 27th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering.
Tallinn, Estonia.
[24] LLVM. 2015. libFuzzer. https://llvm.org/docs/LibFuzzer.html[25] Chenyang Lyu, Shouling Ji, Chao Zhang, Yuwei Li, Wei-Han Lee, Yu Song, andRaheem Beyah. 2019. MOpt: Optimized Mutation Scheduling for Fuzzers. In 28th
USENIX Security Symposium. 1949–1966.
[26] Wes Masri and Andy Podgurski. 2009. Measuring the strength of information
flows in programs. ACM Transactions on Software Engineering and Methodology(TOSEM) 19, 2 (2009), 5.
[27] Theofilos Petsios, Jason Zhao, Angelos D. Keromytis, and Suman Jana. 2017.
SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity
Vulnerabilities. In Proceedings of the 2017 ACM SIGSAC Conference on Computerand Communications Security. ACM, New York, NY, USA, 2155–2168.
[28] Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida, andHerbert Bos. 2017. VUzzer: Application-aware Evolutionary Fuzzing. In NDSS.
https://www.vusec.net/download/?t=papers/vuzzer_ndss17.pdf[29] Bhargava Shastry, Markus Leutner, Tobias Fiebig, Kashyap Thimmaraju, Fabian
Yamaguchi, Konrad Rieck, Stefan Schmid, Jean-Pierre Seifert, and Anja Feldmann.
2017. Static program analysis as a fuzzing aid. In International Symposium on
Research in Attacks, Intrusions, and Defenses. Springer, 26–47.
[30] Qingkai Shi, Xiao Xiao, Rongxin Wu, Jinguo Zhou, Gang Fan, and Charles Zhang.
2018. Pinpoint: Fast and precise sparse value flow analysis for million lines ofcode. In ACM SIGPLAN Notices, Vol. 53. ACM, 693–706.
[31] Nick Stephens, John Grosen, Christopher Salls, Andrew Dutcher, Ruoyu Wang,
Jacopo Corbetta, Yan Shoshitaishvili, Christopher Krügel, and Giovanni Vigna.
2016. Driller: Augmenting Fuzzing Through Selective Symbolic Execution. In
NDSS.
[32] Yulei Sui and Jingling Xue. 2016. SVF: interprocedural static value-flow analysis in
LLVM. In Proceedings of the 25th international conference on compiler construction.
ACM, 265–266.
[33] Laszlo Szekeres, Mathias Payer, Tao Wei, and Dawn Song. 2013. Sok: Eternal war
in memory. In 2013 IEEE Symposium on Security and Privacy. IEEE, 48–62.
[34] UAFL. 2019. Additoinal experiment results. https://sites.google.com/view/uafl/[35] Erik Van Der Kouwe, Vinod Nigade, and Cristiano Giuffrida. 2017. Dangsan:
Scalable use-after-free detection. In Proceedings of the Twelfth European Conference

on Computer Systems. ACM, 405–419.
[36] Haijun Wang, Yun Lin, Zijiang Yang, Jun Sun, Yang Liu, Jin Song Dong, Qinghua
Zheng, and Ting Liu. 2019. Explaining Regressions via Alignment Slicing andMending. IEEE Transactions on Software Engineering (2019), 1–1.
[37] Haijun Wang, Ting Liu, Xiaohong Guan, Chao Shen, Qinghua Zheng, and Zijiang
Yang. 2016. Dependence guided symbolic execution. IEEE Transactions on Software
Engineering 43, 3 (2016), 252–271.
[38] Haijun Wang, Xiaofei Xie, Shang-Wei Lin, Yun Lin, Yuekang Li, Shengchao Qin,
Yang Liu, and Ting Liu. 2019. Locating vulnerabilities in binaries via memory
layout recovering. In Proceedings of the 2019 27th ACM Joint Meeting on European
Software Engineering Conference and Symposium on the Foundations of Software
Engineering. 718–728.
[39] Cheng Wen, Haijun Wang, Yuekang Li, Shengchao Qin, Yang Liu, Zhiwu Xu,
Hongxu Chen, Xiaofei Xie, Geguang Pu, and Ting Liu. 2020. MemLock: Memory Usage Guided Fuzzing. In 2020 IEEE/ACM 42nd International Conference on
Software Engineering. Seoul, South Korea.
[40] Wen Xu, Juanru Li, Junliang Shu, Wenbo Yang, Tianyi Xie, Yuanyuan Zhang,and Dawu Gu. 2015. From collision to exploitation: Unleashing use-after-freevulnerabilities in linux kernel. In Proceedings of the 22nd ACM SIGSAC Conference
on Computer and Communications Security. ACM, 414–425.
[41] Hua Yan, Yulei Sui, Shiping Chen, and Jingling Xue. 2017. Machine-LearningGuided Typestate Analysis for Static Use-After-Free Detection. In Proceedings ofthe 33rd Annual Computer Security Applications Conference. 42–54.
[42] Hua Yan, Yulei Sui, Shiping Chen, and Jingling Xue. 2018. Spatio-temporalcontext reduction: A pointer-analysis-based static approach for detecting useafter-free vulnerabilities. In 2018 IEEE/ACM 40th International Conference on
Software Engineering. IEEE, 327–337.
[43] Wei You, Xueqiang Wang, Shiqing Ma, Jianjun Huang, Xiangyu Zhang, XiaoFeng
Wang, and Bin Liang. 2019. Profuzzer: On-the-fly input type probing for betterzero-day vulnerability discovery. In 2019 IEEE Symposium on Security and Privacy.
IEEE.
[44] Yves Younan. 2015. FreeSentry: protecting against use-after-free vulnerabilities
due to dangling pointers. In 22nd Annual Network and Distributed System Security
Symposiu.
[45] H. Yu, Z. Chen, J. Wang, Z. Su, and W. Dong. 2018. Symbolic Verification ofRegular Properties. In 2018 IEEE/ACM 40th International Conference on Software
Engineering. 871–881.
[46] Insu Yun, Sangho Lee, Meng Xu, Yeongjin Jang, and Taesoo Kim. 2018. QSYM: A
practical concolic execution engine tailored for hybrid fuzzing. In 27th USENIX
Security Symposium. 745–761.
[47] Michal Zalewski. 2014. American Fuzzy Lop. http://lcamtuf.coredump.cx/afl/[48] Yufeng Zhang, Zhenbang Chen, Ji Wang, Wei Dong, and Zhiming Liu. 2015.
Regular property guided dynamic symbolic execution. In Proceedings of the 37th
International Conference on Software Engineering-Volume 1. IEEE Press, 643–653.

12