MemLock: Memory Usage Guided Fuzzing
Cheng Wen

Haijun Wang∗

Yuekang Li

CSSE, Shenzhen University
Shenzhen, China

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

Nanyang Technological University
Singapore

Shengchao Qin∗

Yang Liu

Zhiwu Xu

SCEDT, Teesside University
Tees Vally, UK

Nanyang Technological University
Singapore

CSSE, Shenzhen University
Shenzhen, China

Hongxu Chen, Xiaofei Xie

Geguang Pu

Ting Liu

Nanyang Technological University
Singapore

East China Normal University
Shanghai, China

Xi’an Jiaotong University
Xi’an, China

Engineering (ICSE ’20), May 23–29, 2020, Seoul, Republic of Korea. ACM, New
York, NY, USA, 13 pages. https://doi.org/10.1145/3377811.3380396

ABSTRACT
Uncontrolled memory consumption is a kind of critical software
security weaknesses. It can also become a security-critical vulnerability when attackers can take control of the input to consume
a large amount of memory and launch a Denial-of-Service attack.
However, detecting such vulnerability is challenging, as the stateof-the-art fuzzing techniques focus on the code coverage but notmemory consumption. To this end, we propose a memory usage
guided fuzzing technique, named MemLock, to generate the excessive memory consumption inputs and trigger uncontrolled memory
consumption bugs. The fuzzing process is guided with memory
consumption information so that our approach is general and does
not require any domain knowledge. We perform a thorough evaluation for MemLock on 14 widely-used real-world programs. Our
experiment results show that MemLock substantially outperforms
the state-of-the-art fuzzing techniques, including AFL, AFLfast,
PerfFuzz, FairFuzz, Angora and QSYM, in discovering memory
consumption bugs. During the experiments, we discovered many
previously unknown memory consumption bugs and received 15
new CVEs.

1

INTRODUCTION

Time and space complexities are two main concerns in software
design and development. If they are not implemented well, unexpected behaviors and even troublesome security issues can happen.
In real-world programs, lots of such security vulnerabilities havebeen found (e.g., [17–23, 74]). For example, if the termination conditions of recursive functions are not implemented correctly, an
infinite number of recursive function calls can occur and thus render the stack memory exhausted. The adversaries can exploit thisvulnerability to launch a Denial-of-Service (DoS) attack with somewell-crafted inputs [18, 21]. Recently, researchers have started to
pay attention to these issues. For example, SlowFuzz [58], PerfFuzz [37] and ReScue [63] are developed to generate pathologicalinputs to stress the time complexity issues (i.e., algorithmic complexity vulnerabilities). However, it still leaves untouched for automatically generating pathological inputs to stress space complexity
issues (namely memory consumption bugs) thus far.
Although a number of works (e.g., the popular fuzzing techniques [11, 28, 45, 61, 84]) have devoted to detecting memory issues,
they mostly focus on memory corruption vulnerabilities such as
buffer overflow and use-after-free. Memory corruption occurs in a
program when the contents of the memory are modified due to some
unexpected program behavior that exceeds the original intentionof the program [65, 67, 72]. When the corrupted memory contents
are used later by the program, it may lead to unexpected behaviors (e.g., program crash). However, memory consumption bugs are
essentially different from memory corruption vulnerabilities. As defined by CWE-400 [49], the software does not properly control the
allocation and maintenance of a limited resource thereby enablingan actor to influence the amount of resources consumed, eventuallyleading to the exhaustion of available resources. To make it explicit,
this paper focuses on three types of memory consumption bugs:
uncontrolled-recursion [52], uncontrolled-memory-allocation [51],and memory leak [50]. Uncontrolled-recursion may exhaust stackmemory when the program does not properly control the amount ofrecursion that takes place. Uncontrolled-memory-allocation refers
to the situation whereby the program allocates memory based on an
untrusted size value, but it does not validate or incorrectly validates

CCS CONCEPTS• Security and privacy → Software security engineering.

KEYWORDS
Fuzz Testing, Software Vulnerability, Memory Consumption
ACM Reference Format:
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 42nd International Conference on Software∗ Corresponding authors: Shengchao Qin and Haijun Wang

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.3380396
1

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

Cheng Wen et al.

struct demangle_component *cplus_demangle_type (struct d_info *di) {class EXIV2API DataBuf {public:3// Constructor with an initial buffer size
explicit DataBuf(long size): pData(new byte[size]), size(size) {}
4
5
...
6
byte* pData; // Pointer to the buffer
7
size_t size; // The current size of the buffer
8 };
1
2

3

// "peek" is a single character extracted from the input directly
char peek = d_peek_char (di);456switch (peek){...
case 'P':
ret = d_make_comp (di,DEMANGLE_COMPONENT_POINTER,
cplus_demangle_type (di), NULL);
break;
case 'C':
...
}
...

7
8
9
10
11
12
13
14
15
16
17
18

9

void Jp2Image::readMetadata() {while (io_->read((byte*)&subBox, sizeof(subBox)) ==,→sizeof(subBox) && subBox.length ) {12
subBox.length = getLong((byte*)&subBox.length, bigEndian);
13
DataBuf data(subBox.length); // Allocation without checking
14
...
15
io_->seek(position - sizeof(box) + box.length, BasicIo::beg);
16
}
17 }
10
11

}

Figure 1: Code Snippet from cp-demangle.c in Binutils v2.31

Figure 2: Code Snippet from jp2image.cpp in Exiv2 v0.26

the size, allowing arbitrary amounts of memory to be consumed.
Moreover, if the software does not track and release allocated memory after it has been used, it causes a memory leak.
Existing detection techniques for memory consumption bugs
usually use domain- or implementation-specific heuristics or rules[15, 24, 46, 70, 79]. For example, Radmin [24] learns and executes
multiple probabilistic finite automata, and then confines the resource usage of target programs to the learned automata and detects resource usage anomalies at their early stages. Thus, theireffectiveness heavily depends on the completeness of heuristics
and rules. To create and maintain such rules requires substantial
manual efforts and expertise. In this paper, we employ the greybox fuzzing [84] technique to develop an automated and generaltechnique to detect memory consumption bugs.
Grey-box fuzzing is one of the most effective techniques to findvulnerabilities [39, 41], which typically adopts the coverage information as guidance to explore different program paths. However,existing grey-box fuzzing techniques are not designed for detecting
memory consumption bugs, because such bugs often depend not
only on the program path but also on some interesting program
states in that path (i.e., amount of memory consumption). For example, the real-world program in Figure 2 allocates the memory atLine 4, however, this memory allocation may fail if no additional
memory can be allocated for use. To detect this bug, the grey-box
fuzzer needs to execute a program path that touches Line 4, as
well as a large value for variable size to exceed the available heap
memory. Existing coverage-based fuzzing techniques can easily
cover Line 4, but it may be difficult to produce test cases that havea large value for variable size.
To address the aforementioned challenges, we present MemLockto enhance grey-box fuzzing to find memory consumption bugs.
MemLock works in two steps. Firstly, MemLock performs the static
analysis, which identifies the statements and operations relevant
to memory consumption. We would qualitatively analyze the callgraph, which determines the stack memory usage, and quantitatively analyze memory usage operations, which determines the heap
memory usage. Besides, we also analyze the control flow graph ofthe program, which provides branch coverage for guiding to explore
different program paths. With the memory consumption analyzed,

MemLock then employs branch coverage as well as memory consumption information to guide the fuzzing process. The branchcoverage information guides to explore different program paths,
and the memory consumption information guides the program
path to consume more and more memory. If an input covers new
branch compared to previous inputs, it is considered as interesting
and added into the seed queue. Besides, although an input has no
new branch coverage, if it leads to more memory consumption, we
also retain it as an interesting input through a novel seed updating scheme. This input can be further mutated so that the newly
generated input leads to more memory consumption. After somemutations, MemLock is expected to generate an input whereby thememory consumption exceeds the available memory.
We have evaluated MemLock’s effectiveness using a set of realworld open source programs. The experiment results show that
MemLock substantially outperforms six state-of-the-art tools (i.e.,
AFL [84], AFLfast [8], PerfFuzz [37], FairFuzz [38], Angora [12] andQSYM [83]), in discovering the memory consumption vulnerabilities. MemLock finds 40.5% more unique crashes and 17.9% more
vulnerabilities, than the second best counterpart. In particular, MemLock can discover a certain memory consumption vulnerability atleast 2.07 times faster than the other baseline fuzzers. Besides, thegenerated test cases in MemLock usually lead to 150 times memory
consumption compared to the other state-of-the-art tools. In addition, we have responsibly disclosed several previously unknown
memory consumption bugs, and received 15 new CVE1 for them,demonstrating MemLock’s effectiveness in practice.
In summary, this paper makes the following contributions:• We present MemLock, the first, to the best of our knowledge,
dedicated fuzzing technique to automatically discover memory
consumption bugs without requiring any domain knowledge.
• We design a new dimension of guidance engine to deeply exploit
the memory consumption in a program path, which is complementary to the coverage guidance.
• We have implemented and evaluated MemLock on various widelyused real-world programs. The experimental results have shownthat MemLock substantially outperforms five state-of-the-art
fuzzing techniques in discovering memory consumption bugs.
1 The Common Vulnerabilities and Exposures (CVE) system provides a reference fortracking publicly known information-security vulnerabilities and exposures.
2

MemLock: Memory Usage Guided Fuzzing

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea• We have discovered 15 security-critical memory consumption
vulnerabilities in widely-used real-world programs, and most ofthese vulnerabilities have been patched by the developers.

Static Analysis

Control Flow
Graph
SourceCodeStatic Analysis

Call Graph

Instrumentation

Instrumented
Program

Memory Usage
Operations

2 OVERVIEW
2.1 Motivating Examples

Seed Selector

We first illustrate the limitations of existing coverage-based greybox fuzzing techniques for detecting memory consumption bugswith two examples summarized from real-world vulnerabilities. We
use the vulnerability CVE-2018-17985 [18] in Figure 1 to demonstrate an uncontrolled-recursion bug and CVE-2018-4868 [19] in
Figure 2 to demonstrate an uncontrolled-memory-allocation bug.
In Figure 1, the function cplus_demangle_type recursively calls
itself in line 12 when the input contains the character ‘P’. The depthof recursion depends on the number of character ‘P’s in the input.
With a sufficiently large recursive depth, the execution would runout of stack memory, causing stack overflow. To trigger a stack
overflow, the fuzzer would need to generate inputs containing alarge number of character ‘P’s.
However, existing coverage-based grey-box fuzzers do not haveenough awareness about the change in recursive depth and solely
use coverage information to retain interesting inputs. Take AFL as
an example, it is aware of repeatedly executed CFG edges [71] but
only in a coarse manner. To be specific, AFL adopts the concept
of “loop bucket” to retain interesting inputs (see Section 3.1). The
loop bucket cannot tell the fine-grained change in recursive depth.
Specially, it does not differentiate the change when the recursive
depth is greater than 255. Nevertheless, this number is still very
far from causing stack exhaustion, which normally requires tens of
thousands of recursive depth.
Therefore, to expose uncontrolled-recursion effectively, grey-box
fuzzers need to have precise awareness about the stack memory
consumption of the target program when executing an input.
Figure 2 demonstrates an uncontrolled-memory-allocation problem in exiv2. At line 11-12, when the program parses a subBox in
readMetadata(), a length is extracted from the user inputs. Thenthe length is fed directly into DataBuf() at line 13. Finally, thisvalue is used as the size of a memory allocation request at line 4.
Note that the program does not check the size before allocating
memory. By carefully handcrafting the input, an adversary canprovide arbitrarily large values for subBox.length, leading to program crash (i.e., std::bad_alloc) or running out of memory. To
trigger this problem, the fuzzer would need to generate inputs witha large subBox.length. For this purpose, the fuzzer needs to collect information about the value of subBox.length to retain theinteresting inputs that can incur a large memory consumption.
However, existing coverage-based grey-box fuzzers lack awareness about the value of subBox.length. Therefore, they cannot effectively generate inputs causing subBox.length to become larger.
Take AFL as an example, let us assume AFL now holds a seed
input a which incurs the subBox.length of 100 and causes thefunction to enter the while at line 11 and eventually return atline 16. After some mutations, AFL may generate another input
b which incurs the subBox.length of 10000 and also causes thefunction to enter the while at line 11 and return at line 16. We canInitial
Seeds

Seed Pool

Proof of
Crashes

Seed Updater

Selected Seed

Seed Mutator

Test Inputs

Executor

BranchCoverage
Feedback
Collector
MemoryConsumption

Fuzzing Loop

Figure 3: The overview of the proposed approach; grey rectangles denote the new features of MemLock.
clearly see that comparing with a, b consumes much more memory and is closer to running out of memory. However, AFL will
discard input b and will not retain it as a seed because b does notbring new branch coverage. Consequently, AFL cannot detect thisuncontrolled-memory-allocation problem effectively.
Therefore, to expose uncontrolled-memory-allocation effectively,
grey-box fuzzers also need to have precise awareness about theamount of consumed heap memory of the target program when
executing an input.

2.2

Approach Overview

Figure 3 shows the workflow of MemLock, which contains two
main components: static analysis and fuzzing loop. In particular,
the static analysis takes the program source code as the input, andgenerates three kinds of information (see Section 3.1): control flow
graph, call graph, and memory usage operations. The static analysis
in MemLock helps to decide where to instrument and what to instrument. The control flow graph information is used to collect thebranch coverage; the call graph information aids to instrument thefunction call entries and returns. Based on the memory usage operation statements, MemLock instruments the locations of memory
allocation and free operations.
Once the program is instrumented, MemLock enters the continuous fuzzing loop to detect memory consumption bugs (seeSection 3.2). Given the initial seeds, MemLock selects a seed s fromthe seed pool. As for the seed s, MemLock generates the new inputs (test cases) using different mutation strategies. MemLock thenruns the generated inputs against the instrumented program, andcollects their memory consumption information (see Section 3.2.1)
and branch coverage information. If the generated seeds consume
more memory or have new branch coverage, they are retained asinteresting seeds. MemLock adds them into the seed pool througha seed updating scheme (see Section 3.2.2). MemLock repeats thisprocess until reaching time or resource budget limits.
Example in Figure 1. We illustrate MemLock using the example in
Figure 1. Suppose the initial value of peek (obtained from function
parameter di by function d_peek_char at Line 5) is ‘a’. This value
is general, unbiased for any special case. Through the coverage
guidance, MemLock generates a new input i 1 that may produce the3

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

Cheng Wen et al.

value ‘P’ for peek as it covers the different branch. When i 1 is further
mutated, it generates i 2 , which may produce four consecutive ‘P’s
for peek (i.e., “PPPP”) in its recursion. Since i 2 has different branchhits in the sense of “loop bucket” from i 1 , it is added into theseed pool. When i 2 is selected for mutation, it generates i 3 thatmay produce five consecutive ‘P’s for peek (i.e., “PPPPP”) in its
recursion. The coverage guidance uses the concept of “loop bucket”,
and considers that i 3 does not offer new branch coverage comparedto i 1 and i 2 . In this case, existing coverage-based grey-box fuzzers
would discard i 3 , and thus miss the chance to generate an input thatcan produce more consecutive ‘P’s. On the other hand, MemLock
introduces memory consumption as the guidance, under which i 3 isconsidered to cause more memory consumption (than i 1 or i 2 ). Thus,
it retains i 3 as an interesting test case, and adds it into the seed pool.
It can further mutate i 3 , and generate inputs that may produce moreconsecutive ‘P’s. After some mutations, MemLock may generate an
input that would produce a sufficiently large number of consecutive‘P’s (i.e., “PPP. . . ”) to run out the stack memory.
Example in Figure 2. For illustration, let us assume that the available heap memory is 10000 bytes. Suppose the initial value of
subBox.length is 100, which is produced from user input at Lines
11-12. At Line 13 in Figure 2, the memory is allocated successfully,
and the program executes the true branch of the while statementat Line 11. Based on the coverage guidance, MemLock performs
the mutation and can generate a new input i 1 that produces alarger value for subBox.length. In this case, we assume the value
is 150. The input i 1 still executes the true branch of the whilestatement, and thus there is no new branch coverage. At this time,
the coverage-based grey-box fuzzers would discard i 1 , therefore
missing the chance to generate an input consuming more memory.
On the other hand, MemLock’s memory consumption guidanceconsiders that i 1 consumes more memory (i.e., 150 > 100), andkeeps it as an interesting input. When i 1 is further mutated, MemLock can generate an input (e.g., len = 250) that consumes morememory. After some mutations, MemLock can generate an input(e.g., len = 11000) that runs out of memory.
Note that we have not elaborated memory leaks separately
as MemLock deals with them in the same way as uncontrolledmemory-allocation, using the same memory usage guidance during
fuzzing.

3.1.1 Control Flow Graph. MemLock collects branch coverage
information in the control flow graph (CFG) of the program to guideprogram path explorations as AFL [84]. It inserts instrumentation
into every branch of the program CFG, assigning a pseudo-unique
ID to every branch. During program execution, the instrumentation
uses an 8-bit counter to keep track of the number of times thata branch has been executed. MemLock groups the hit counts ofeach branch execution into several buckets to denote different
magnitudes2 . Consequently, the branch coverage information in an
executed program path can be defined as follows.
Definition 3.1 (Trace Bits [84]). For an executed program path,its trace bits are represented by an 8-bit array with size 2K , and thevalue of the IDth element is stored in an 8-bit counter (In AFL, K = 16).
The trace bits record the accumulated branches executed in a
program path, and they can represent a program path roughly.
Definition 3.2 (Path-ID). For an executed program path, its
path-ID is the hash value of its trace bits (see Definition 3.1).
3.1.2 Call Graph. In addition to branch coverage, MemLock alsocollects the memory consumption information. One important construct that may cause a large bulk of stack memory consumption is
the recursive function call. When a function call occurs, the program automatically allocates the stack memory for use (e.g., local
variables). On the other hand, when a function call is finished (returned), the program automatically reclaims the allocated stackmemory for reuse. To monitor the stack memory consumption offunction calls, MemLock injects the instrumentation into both theentry and the exit of the function call.
We use ft to denote the length (i.e., consumption) of call stackduring the program execution. This value changes with the execution of the program. When the program execution enters a function,
the value ft is increased by one; likewise, when a function call isreturned, the value ft is decreased by one. In the following, we use
fm to denote the peak value of ft during the program execution.
The value fm thus qualitatively reflect the maximum (stack) memory consumption by recursive function calls during the program
execution. We do not differentiate the memory consumption causedby different functions, because usually the stack memory can be exhausted only under infinite recursive function calls. Thus, we only
need the peak length of call stack to guide MemLock to approachinfinite recursive function calls.
3.1.3 Memory Usage Operations. Memory usage operation statements (e.g. malloc and free) may also contribute to the consumptionof a large bulk of memory. In a program path, the memory operation statements may be affected by the program inputs. When thishappens, it is possible to guide this program path to consume morememory by controlling the program inputs. To this end, MemLock
uses instrumentation to quantitatively obtain the size of the memory operation. Due to the lack of freed memory size in deallocation
statements, MemLock maps them to their corresponding allocation
statements to obtain the size of the freed memory.
In particular, we insert instrumentation into the memory allocation/deallocation functions in the standard libraries, and obtain

3 METHODOLOGY
3.1 Static Analysis
The static analysis in MemLock decides how to instrument the target program. Based on the instrumentation, MemLock collects theguidance information, and then uses it to drive the fuzzing process.
After analyzing the control flow graph, MemLock instruments thetarget program to capture branch (edge) coverage, guiding program
path explorations. Additionally, based on the qualitative and quantitative analysis of call graph and memory usage operations, it also
instruments the target program to collect the memory consumption
information, guiding the fuzzing process towards consuming morememory for each program path. To facilitate the description of our
methodology, we define the following concepts.

2 In AFL, the hit counts of each branch execution are divided into 8 buckets: 1 time, 2times, 3 times, 4-7 times, 8-15 times, 16-31 times, 32-127 times, and 128-255 times [78].
4MemLock: Memory Usage Guided Fuzzing

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea
that MemLock additionally adopts memory consumption guidance
to retain interesting inputs.
The algorithm takes the instrumented program P (see Section 3.1)
and a set of initial seeds T as the inputs, and outputs a set of test
cases S that trigger the memory consumption bugs. The variable
Queue represents the seed pool, and is initialized as the initial seeds
T at Line 2. MemLock first selects an input t from the seed pool
Queue (Line 4), and computes its probability on whether or not tobe mutated at Line 5 (see Section 3.2.1). Upon deciding to mutate
the input t, MemLock assigns the energy (i.e., numChildren) to it atLine 6, which determines the number of children to produce fromt. MemLock uses the same heuristics to determine numChildren
as AFL [84]. It produces more children for inputs that have wider
code coverage or that are discovered later in the fuzzing process. At
Lines 4-17, MemLock mutates the input t to generate numChildren
children, monitors their executions, and determines their affiliations.
MemLock first performs mutation to generate the new input childi(Line 8). At Line 9, MemLock then runs the input childi on the
instrumented program P, and collects its branch coverage (i.e.,
traceBitsi ), function memory consumption (i.e., fm), and operation
memory consumption (i.e., om), respectively.
If the input childi triggers memory consumption bugs (howto determine memory consumption bugs, see Section 4.1), it isadded into the output S (Line 12). Otherwise, MemLock analyzes
its branch coverage and memory consumption (Line 14 and 16). If it
has new branch coverage, it is added into the Queue for the further
mutation (Line 15). In addition, we further analyze its memory consumption. MemLock checks whether childi leads to more memory
consumption based on fmmap[k] and ommap[k] at Line 16. (seeSection 3.2.1). If so, MemLock updates the value of fmmap[k] andommap[k] using the function Update at Line 17 (see Section 3.2.2).
This process is repeated until the given time or resource budget
expires (Lines 3).

Algorithm 1: Memory Usage Guided Fuzzing
input :an instrumented program P, and set of initial seeds T
output : test cases S triggering memory consumption bugs
1

S ← Φ;

2 Queue ← T ;while time and resource budget do not expire dofor each input t in Queue do
5
if with probability FuzzProbt to select t then6
numChildren ← AssiдnEnerдy(t);7
for 0 ≤ i < numChildren do
8childi ← Mutate(t);9(traceBitsi , fmi , omi ) ← Run(childi , P);
10
k = Hash(traceBitsi );11
if it triggers memory consumption bugs then12
S ← S ∪ childi ;
3

4

else
if N ewCov(traceBitsi ) thenQueue ← Queue ∪ childi ;

13
14
15

if N ewMax(fmi , omi ) thenQueue ←
U pdate(childi , fmMap[k], omMap[k]);

16
17

18

return S

its parameters and return value. The reason is that the memory is
allocated by some standard library functions [1, 46], e.g., malloc,
calloc, realloc, and new. On the other hand, the program may also
free the memory using the standard library function such as freeand delete. Even when the program uses a user-customized memory
usage operation function [33], it still relies on standard library functions to operate a larger bulk of memory. Thus, we do not need toconsider the user-customized memory usage operations in practice.
We use ot to denote the amount of memory consumed by memory
operations in a program path. When the program allocates ot ′ bytes
memory, the value ot is increased by ot ′ ; likewise, if it frees ot ′ bytes
memory, the value ot is decreased by ot ′ . In the following, we use theom to represent the peak value of ot during the program execution.
The value om evaluates the memory consumption in a program
path by memory usage operation statements. By using om as theguidance, MemLock can mutate the program inputs and gradually
increase the peak value of memory consumption in a program path.

3.2

3.2.1 Guidance Mechanisms. One of the most important components in the grey-box fuzzing is its guidance mechanism (Lines 14
and 16 in Algorithm 1), which often dominates the capability of
the fuzzing technique in finding bugs [11, 37]. For example, SlowFuzz [58] uses the number of executed instructions as guidance tostress algorithmic complexity vulnerabilities. To find the memory
consumption bugs effectively, MemLock uses branch coverage aswell as memory consumption as the guidance. The branch coverage
information guides MemLock to explore different program paths,
while the memory consumption information can drive MemLock
to focus on program paths with more memory consumption. To
facilitate the description of our memory consumption guidance, we
define the following concepts.

Fuzzing Loop
Definition 3.3 (Maximum Function Memory). Given a pathk and a set I of inputs that all execute k, the maximum function
memory consumption fmmap[k] in k is the maximum peak value ofcall stack, among all the inputs I :Algorithm 1 shows the high-level procedures of MemLock. The
intuition of the algorithm is that, for each input t in the seed pool,
MemLock decides whether to mutate it based on a selection probability. If so, MemLock mutates t and generates a set of child inputs. Then, MemLock runs each child input and monitors their
executions. If a child input has new coverage or consumes morememory (see Definitions 3.3 and 3.4), it is retained as an interesting
input. While this process is similar to the process of traditional
coverage-based grey-box fuzzers (e.g., AFL), the main difference is

fmmap[k] ← max fmi
i ∈I

where fmi represents the peak value of call stack during the executionof input i (see Section 3.1.2).
5

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

Cheng Wen et al.

Path 1

Path 2Path 3

Original Seed Queue

Seed 1

Seed 2

Seed 3

New Path

Seed 1

Seed 2

Seed 3

Seed 4Larger Memory
Consumption

Seed 1

Seed 2

Seed 3

Seed 4

seed with the generated input childi , we well exploit the advantage
of childi as it is better in terms of finding memory consumption
bugs. This seed updating policy ensures MemLock to gradually
improve/increase the overall memory consumption, and it could
avoid getting stuck in local maxima like SlowFuzz [37], and brings
long-term stable improvements.
To tailor for our guidance mechanism, MemLock also optimizes
the seed selection probability (Line 5 in Algorithm 1) for the mutation as follows.

Path 4

Seed 5

Definition 3.7 (Favored Input). An input t is favored for mutation, if t has new branch coverage (i.e. NewCov) or t leads to maximum
memory consumption (i.e., N ewMax).

Figure 4: Dynamic Seed Updating

Definition 3.8 (Selection Probability). An input t is selected
for mutation with the following probability:
1 if t is favored
FuzzProbt =aotherwise

Definition 3.4 (Maximum Operation Memory). Given a pathk and a set I of inputs that all execute k, the maximum operation
memory consumption ommap[k] in k is the maximum peak value ofmemory consumption by memory usage operations, among all the
inputs I :ommap[k] ← max omi

That is, the favored inputs are always selected, and a is theprobability of selecting a non-favored input. In our experiments we
use a = 0.01 like PerfFuzz [37].

i ∈I

where omi denotes the peak value of memory consumed by memory
usage operations during the execution of input i (see Section 3.1.3).

4

Definition 3.5 (NewCov). Given a set I of inputs and an inputt, we say t hits a new coverage, if it either (1) executes a branch thathas not been touched by I ; or (2) hits a branch touched by I but witha different bucket number.

EVALUATION

We have built a prototype of MemLock. Our implementation adds
around 1.6k lines of C/C++ code to the file containing AFL’s core implementation. In particular, the static analysis and instrumentation
components are implemented based on the LLVM framework [36],and the fuzzer engine is implemented based on the AFL-2.52b framework [84]. We have conducted thorough experiments to evaluate
MemLock with a set of real-world programs. More detailed experimental results can be found on our website [48]. With theseexperiments, we aim to answer the following research questions:
RQ1. How capable is MemLock in memory consumption crashdetection?
RQ2. How capable is MemLock in memory consumption realworld vulnerability detection?
RQ3. Do the strategies of MemLock help to trigger memory leaks
with more leakage?
RQ4. Do the strategies of MemLock help to generate inputs withmore memory consumption?

The function N ewCov (Line 14) will check whether a newly
generated input childi hits a new coverage with respect the current
Queue or not. That is, the function N ewCov considers the branchcoverage and guides MemLock to explore different program paths.
Definition 3.6 (NewMax). Given a set I of inputs and an input tthat all execute k, we say t hits a new maximum memory consumption,
if either fmt > fmmap[k] or omt > ommap[k].
The function N ewMax (Line 16) determines whether the input
childi leads to the maximum memory consumption among the current seed set. It actually checks two kinds of memory consumption.
It first determines whether childi leads to the maximum function
memory consumption (see Definition 3.3). It also considers whether
childi leads to the maximum operation memory consumption (seeDefinition 3.4). If the input childi satisfies either of the above twocases, MemLock update the seed queue with childi at Line 17 (seeSection 3.2.2).

4.1

Experiment Setup

Following the suggestions in [35], we conducted the experiments
carefully, to draw conclusions as objective as possible.
Baseline Fuzzers to Compare against. We compare MemLockagainst six state-of-the-art fuzzers, namely AFL [84], AFLfast [8],PerfFuzz [37], FairFuzz [38], Angora [12] and QSYM [83]. The baseline fuzzers are selected based on the following considerations. AFL
is the widely-used coverage-based greybox fuzzer, and selected
as baseline fuzzer in the most work. AFLfast is an advanced variant of AFL, specially equipped with a better power schedule [8].
PerfFuzz [37] is to stress the time complexity issues in the program, while MemLock seeks to detect space complexity issues.
FairFuzz [38] leverages a targeted mutation strategy to execute
towards rare branches. Further, Angora [12] utilizes taint analysis to track information flow, and then uses gradient descent to3.2.2 Dynamic Seed Updating. In order to efficiently support retaining the most interesting input for each path, we propose anovel seed updating scheme. In MemLock, the seed queue is kept
in a linked list, where each node represents a seed that explores
a program path, as shown in Fig. 4. MemLock updates the seed
queue in the following two cases. (1) New Path. If the test input
results in new branch coverage, then it will be added to the seed
queue as a new node, as shown in the second row of Fig. 4. (2)Larger Memory Consumption. If the input, e.g., seed2 in the third
row of Fig. 4, generates an input seed5, which does not result in
new branch coverage, but it leads to larger memory consumption
than the corresponding input. When seed2 and seed5 execute thesame path, seed2 is replaced with seed5. With replacing the original
6

MemLock: Memory Usage Guided Fuzzing

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

break through the hard branches. Lastly, QSYM [83] is a popularsymbolic execution assisted fuzzer. Note that we haven’t selected
MemFuzz [16] as baseline fuzzer, because MemFuzz is not open
source and it resorts to memory accesses (instead of memory consumption). In a word, we selected various kinds of representative
state-of-the-art fuzzers as baseline fuzzers, and they are widelyused to discover vulnerabilities in practice.
Evaluation Benchmarks. We select evaluation benchmarks considering several factors, e.g., popularity, frequency of being tested,development activeness, and functional diversity. Finally, we use
14 widely-used real-world programs, which all contain memory
consumption bugs, to evaluate MemLock, including well-known
development tools (e.g., nm, cxxfilt, readelf ), code processing tools(e.g., nasm, flex, yaml-cpp, mjs), graphics processing libraries (e.g.,
openjpeg, jasper, exiv2), video processing tools (e.g., bento4 andlibming), and data processing libraries (e.g., libsass and yara), etc.
These programs have also been widely tested by existing state-ofthe-art greybox fuzzers [28, 35, 38, 82].
Performance Metrics. To compare against state-of-the-art fuzzers,
the most direct measurement is the capability to find the vulnerabilities. With this regard, we consider both unique bugs and uniquecrashes each fuzzer finds in the fuzzing process. Since MemLock is
to stress the space complexity issues of programs, we also distill
the memory consumption of each seed in the pool.
Configuration Parameters. Since the fuzzers heavily rely on the
random mutation, there could be performance jitter during fuzzing
process. We took two actions to mitigate the randomness caused by
the nature of fuzzing techniques. First, we test each program for alonger time, until the fuzzer reaches a relatively stable state. We runeach fuzzer for 24 hours. Second, we perform each experiment for
5 times, and evaluate their statistical performance. Besides, we run
all the fuzzers with the -d option to skip the deterministic mutation
stage, following the configuration of PerfFuzz [37].
Memory Consumption Bugs. The uncontrolled-recursion bug
usually causes stack-overflow, thus we can directly use AddressSanitizer [62] to detect it. The uncontrolled-memory-allocation bug
consumes a large amount of memory so that the program runsout of the memory. Thus, we can detect it by setting the “allocator_may_return_null” [29] flag of AddressSanitizer. In addition, we
use LeakSanitizer [60] to detect memory leakage.
Experiment Infrastructure. All our experiments have been performed on machines with an Intel (R) Xeon (R) E5-1650 v3 Processor(3.40GHz) and 16GB of RAM under 64-bit Ubuntu LTS 16.04.

4.2

experiments, MemLock performs best in 10 (58.8%) groups of experiments among 7 different fuzzers, as shown in column MemLock. In
total, MemLock finds 2009 unique memory consumption crashes inthe benchmark programs, improving by 59.2%, 70.5%, 76.9%, 98.1%,
40.5% and 66.7% respectively, compared to state-of-the-art fuzzers
AFL, AFLfast, PerfFuzz, FairFuzz, Angora and QSYM. Especially,
MemLock is able to find unique crashes in all benchmark programs,
while other 6 state-of-the-art fuzzers may find no crashes in somebenchmark programs. For example, none of the other 6 state-ofthe-art fuzzers could find any unique crashes in the program flex,
but MemLock was able to find 61 unique crashes within 24 hours.
To better compare different fuzzers, we also use the plots to depict the performance over time in some benchmark programs, as
shown in Figure 5. It shows that MemLock has a steady and strong
growth trend in finding unique crashes, and MemLock is also thefirst fuzzer that reported crashes.
Following Klees’ recommendation [35], we also conduct thestatistic test for the results. The Â12 [68] statistic measures theprobability that one fuzzer (in this case MemLock) outperforms
another fuzzer. The value of Â12 means by what chance the result of
MemLock is better than the competitor, as shown in columns withthe heading Â12 . Further, we apply the Mann-Whitney U -test [2]with a significance level of 0.05 to check the statistical significancedifferences of experimental results. A smaller statistical significancedifference (a.k.a p-value) indicates a more significant difference
between MemLock and the competitor. In Table 1, we mark thecorresponding Â12 values in bold for those with a p-value smaller
than the significance level (0.05) (for simplicity, we do not include
p-values here but they are available at the companion website [48]).
Out of 102 Â12 values in the table, 72 (70.6%) Â12 values exceed theconventionally large effect size (0.71) and are marked in bold. Thus,
we can conclude that MemLock significantly outperforms other 6
state-of-the-art fuzzers in most benchmark programs.
From the analysis of Table 1 and Figure 5, we can positively answer RQ1 that MemLock significantly outperforms the startof-the-art fuzzers in terms of memory consumption crashes
detection.

4.3

Real-world Vulnerability Evaluation (RQ2)

In this section, we compare the capability of MemLock to find realworld known vulnerabilities against baseline fuzzers, as suggested
by Klees [35].
Table 2 shows the statistic results in MemLock as well as other 6different state-of-the-art fuzzers. The benchmark programs totallycontain 34 unique vulnerabilities, out of which MemLock performs
best in the 25 vulnerabilities among other 6 state-of-the-art fuzzers,
as shown in column MemLock. MemLock averagely takes about
5.4 hours to find each unique vulnerability, which is 2.15, 2.15,
2.20, 2.69, 3.76, 2.07 times faster than the state-of-the-art fuzzers
AFL, AFlfast, PerfFuzz, FairFuzz, Angora and QSYM respectively. In
particular, MemLock finds 33 out of 34 unique vulnerabilities within
24 hours, while other fuzzers AFL, AFLfast, PerfFuzz, FairFuzz,
Angora and QSYM only find 26, 28, 20, 17, 6 and 25, respectively.
The three unique vulnerabilities (i.e., issue#106, CVE-2018-18701
and CVE-2019-6293) in mjs, nm and flex can be found only by

Unique Crashes Evaluation (RQ1)

To evaluate the effectiveness of fuzzers, a direct measurement is
the number of unique crashes found by different fuzzers. It is believed that more unique crashes usually indicate higher chances ofcovering more unique vulnerabilities.
Table 1 shows the number of unique crashes, which is caused bymemory consumption vulnerabilities, found by 7 different fuzzers
within 24 hours in the benchmark programs. It is worth noting, we
identify unique crashes related to memory consumption bugs byreproducing the crashes and analyzing their crash stacks. And we
discuss other types of crashes in Section 4.6. Out of the 17 groups of7

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

Cheng Wen et al.

Table 1: Unique Crashes Evaluation
Program

VersionSLoC

mjs [53]
cxxfilt [5]
nm [5]
nasm [54]flex [27]yaml-cpp [80]libsass [43]yara [81]readelf [5]exiv2 [25]openjpeg [55]1.20.1
2.31
2.31
2.14.03
2.6.4
0.6.2
3.5.4
3.5.0
2.28
0.26
2.3.0

40k
1,757k
1,757k
105k
27k
58k
27k
45k
1,844k
84k
243k

Type

UR
UR
UR
UR
UR
UR
UR
UR
UA
UA
UA
UA
bento4 [4]
1.5.1
78k
ML
UA
libming [42]
0.4.8
92k
ML
UA
jasper [32]2.0.1444k
MLTotal Unique Crashes (Improvement)

MemLock#Crashes
114
448
127
132
61
4
23
156
273
10
16
5
145
18
264
3
210
2009

AFL
#Crashes Â12
36 1.00
373 1.00
12 1.00
6 1.000 1.000 1.00
6 1.0034 1.00
104 1.00
11 0.148 0.802 1.0078 1.00
20 0.40336 0.20
2 0.84234 0.08
1262 (+59.2%)

AFLfast#Crashes Â12
31 1.00
304 1.00
21 1.00
4 1.000 1.00
1 1.004 1.0033 1.00
110 1.00
11 0.20
5 1.002 0.9872 1.00
18 0.60
324 0.00
3 0.56235 0.08
1178 (+70.5%)

PerfFuzz#Crashes Â12
88 0.96401 0.88
17 1.00
40 1.00
0 1.003 0.56
23 0.53
65 0.94
54 1.00
6 0.900 1.002 1.0061 1.00
17 0.62324 0.00
0 1.0035 1.00
1136 (+76.9%)

FairFuzz#Crashes Â12
12 1.00
39 1.00
0 1.000 1.000 1.000 1.0011 0.88
13 1.00
181 0.88
15 0.00
7 0.46
1 1.00125 1.00
20 0.20371 0.00
3 0.56
216 0.40
1014 (+98.1%)

Angora#Crashes Â120 1.000 1.000 1.000 1.000 1.000 1.0026 0.25
0 1.000 1.0013 0.160 1.00
189 0.00
290 0.00
3 1.0087 1.00
2 1.00820 0.00
1430 (+40.5%)* UR means the uncontrolled-recursion bug, UA means the uncontrolled-memory-allocation bug, and ML means the memory leak. We highlight the Â

QSYM#Crashes Â12
30 1.00
327 1.00
20 1.00
4 1.000 1.000 1.00
7 1.0031 1.00
114 1.00
8 0.52
5 0.80
1 1.0074 1.00
16 0.80
354 0.00
2 0.92212 0.46
1205 (+66.7%)

12 values in the bold if its

50time (hour)

20

15

5

0

0

Angora
AFLfast
AFL

time (hour)

20

100

openjpeg

QSYM
PerfFuzz
MemLock
FairFuzz

15

150

18
16
14
12
10
8
6
4
2
0

10

Angora
AFLfast
AFL

5

200

readelf

Number of Unique Crashes

250

QSYM
PerfFuzz
MemLock
FairFuzz

0

300

10

time (hour)

Number of Unique Crashes

Angora
AFLfast
AFL

20

nm

15

QSYM
PerfFuzz
MemLock
FairFuzz

5

Number of Unique Crashes

140
120
100
80
60
40
20
0

10

time (hour)

20

15Angora
AFLfast
AFL

0

nasm

10

QSYM
PerfFuzz
MemLock
FairFuzz

5

180
160
140
120
100
80
60
40
20
0

0

Number of Unique Crashes

corresponding Mann-Whitney U test is significant.

Figure 5: The growth trend of unique crashes found in different fuzzers; higher is better

MemLock within 24 hours. Therefore, it is proved that our memoryconsumption guided strategy is very effective in finding memory
consumption bugs.
In addition, we also conduct the statistic test for unique vulnerability evaluation. Out of 204 Â12 values in the table, 139 (68.1%)
Â12 values are bold and exceeding the conventionally large effectsize (0.71). Thus, MemLock significantly outperforms other 6 stateof-the-art fuzzers in finding unique vulnerabilities.
Case Study. To demonstrate the reason behind MemLock’s superiority, we present the case of CVE-2019-6293. It is an uncontrolledrecursion vulnerability in flex, which is a lexical analyzer generator.
The lexical analyzer generated by flex has to provide “beginning”
state and “ending” states. The mark_beginning_as_normal function mark each “beginning” state in a machine as being a “normal”
state, and the “beginning” states are the epsilon closure of the firststate. The mark_beginning_as_normal function would call to itself if there is a state reachable from the first state through epsilon.
We investigate MemLock’s mutation history and identify a key mutation step. The test case triggers the mark_beginning_as_normal
function calling itself for multiple times, through havoc mutation
operation. Then, the recursive depth of this function is multipliedby splice operation, and finally leading to stack-overflow.

More interestingly, MemLock takes only 5.4 hours on average todiscover this vulnerability, while other fuzzers all fail. We can also
see the peak length of call stack of flex in Figure 6. AFL does notretain any seed over 5000 lengths, as those inputs do not increase
coverage. Comparing to AFL, MemLock intentionally keeps seeds
that increase the peak length of call stack, and finally triggering
stack-overflow. This explains the reason why MemLock can findthe vulnerability, while AFL can not detect it in all 5 runs.
New Vulnerabilities MemLock Found. With MemLock, we havediscovered many previously unknown security-critical vulnerabilities. These vulnerabilities were not previously reported. We
informed the maintainers, and Mitre assigned 15 CVEs. Amongthese 15 CVEs, 8 CVEs are uncontrolled-recursion vulnerabilities,
5 are vulnerabilities due to uncontrolled-memory-allocation issues,and 2 are about memory leak vulnerabilities. An attacker mightleverage these vulnerabilities to launch an attack, by providing wellconceived inputs that trigger excessive memory consumption. The
developers actively patched the vulnerabilities with our reports. At
the time of writing, 12 of these vulnerabilities have been patched.
Detailed information on our newly discovered vulnerabilities isavailable on our website [48]. We are confident that MemLock iseffective and viable in practice.
8

MemLock: Memory Usage Guided Fuzzing

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

Table 2: Time to expose real-world vulnerability
ProgramVulnerability

Typeissue#58
UR
issue#106
UR
CVE-2018-9138
UR
CVE-2018-9996
UR
cxxfilt
CVE-2018-17985
UR
CVE-2018-18484
UR
CVE-2018-18700
UR
CVE-2018-12641
UR
CVE-2018-17985
UR
CVE-2018-18484
UR
nm
CVE-2018-18700
UR
CVE-2018-18701
UR
CVE-2019-9070
UR
CVE-2019-9071
UR
CVE-2019-6290
UR
nasm
CVE-2019-6291
UR
flex
CVE-2019-6293
UR
CVE-2019-6292
URyaml-cpp
CVE-2018-20573
UR
CVE-2018-19837
UR
libsass
CVE-2018-20821
UR
CVE-2018-20822
URyara
CVE-2017-9438
UR
readelf
CVE-2017-15996
UA
exiv2
CVE-2018-4868
UA
CVE-2018-20186
UAbento4
CVE-2019-7698
UA
CVE-2019-7581
UA
libming
CVE-2019-7582
UA
issue#155
UA
CVE-2019-6988
UA
openjpeg
CVE-2017-12982
UA
CVE-2016-8886
UA
jasperissue#207
UA
Average Time Usage (Improvement)
Unique Vulnerabilities (Improvement)
mjs

MemLockTime(h)
0.5
13.7
0.3
T/O
0.2
0.2
0.2
2.6
10.4
9.9
9.6
13.9
18.4
12.4
0.9
1.5
5.4
0.4
6.1
1.6
0.1
15.6
0.2
0.2
0.1
0.4
14.6
0.6
0.1
1.4
7.8
4.5
4.1
1.7
5.4
33

AFL
Time(h) Â12
0.3 0.25
T/O 1.00
7.2 1.00
16.5 0.00
1.1 1.00
1 1.001.2 1.00
19.1 1.00
18.2 0.81
16.4 0.84
14.9 0.63
T/O 1.00
15.6 0.56
T/O 0.88
T/O 1.00
9 0.94
T/O 1.00
T/O 1.00
T/O 0.88
13.3 0.88
5.7 1.00
14.3 0.50
0.9 1.00
0.3 0.86
0.1 0.50
0.4 0.50
T/O 1.00
0.8 0.68
0.1 0.50
1 0.3015.1 0.86
11.4 0.72
17 0.88
2.2 0.62
11.6 (2.15×)
26 (+26.9%)

AFLfastTime(h) Â12
0.4 0.25
T/O 1.00
10.1 1.00
T/O 0.50
4.5 1.00
4.5 1.00
4.6 1.00
12.6 1.00
11.9 0.56
17.1 0.84
17.8 0.88
T/O 1.00
13.9 0.44
14 0.69
19 1.00
14 1.00
T/O 1.00
18.4 1.00
T/O 0.84
10.5 0.88
6.5 1.00
19.5 0.56
4.3 1.00
0.2 0.68
0.1 0.50
0.4 0.50
T/O 1.00
1.4 0.80
0.1 0.50
1.3 0.36
11.1 0.84
10 0.60
22.3 1.00
3.6 0.68
11.6 (2.15×)
28 (+17.9%)

PerfFuzz
Time(h) Â12
0.2 0.13
T/O 1.00
0.5 0.81
T/O 0.50
0.2 0.63
0.2 0.63
0.3 0.75
12.2 0.88
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 0.88
9 1.008.7 1.00
T/O 1.00
0.9 0.81
12.4 0.84
1.8 0.63
0.1 0.50
14.6 0.47
0.61 0.91
0.5 0.92
0.1 0.50
0.4 0.50
T/O 1.00
2 0.880.1 0.50
1.4 0.40
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
11.9 (2.20×)
20 (+65.0%)

FairFuzz
Time(h) Â12
0.4 0.25
T/O 1.00
T/O 1.00
T/O 0.50
1.9 1.00
8 1.0012.6 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 0.88
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 0.84
8.5 0.88
9.5 1.00
11.3 0.56
5.3 1.00
0.3 0.68
0.1 0.50
0.4 0.50
T/O 1.00
0.4 0.36
0.1 0.50
1.2 0.42
T/O 1.00
11.9 0.64
10.3 0.52
2.2 0.68
14.5 (2.69×)
17 (+94.1%)

AngoraTime(h) Â12
T/O 1.00
T/O 1.00
T/O 1.00
T/O 0.50
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
0.92 0.00
T/O 1.00
T/O 1.00
0.1
0.5
0.1 0.00
0.5 0.00
T/O 1.00
0.1 0.50
T/O 1.00
T/O 1.00
T/O 1.00
T/O 1.00
15.9 1.00
20.3 (3.76×)
6 (+450.0%)

QSYM
Time(h) Â12
0.3 0.22
T/O 1.00
3.3 1.00
T/O 0.50
1.4 1.00
1.4 1.00
1.4 1.00
12.8 0.88
13.3 0.63
14 0.75
T/O 1.00
T/O 1.00
15.8 0.56
T/O 0.88
17.6 1.00
7.5 1.00
T/O 1.00
T/O 1.00
T/O 0.84
5 0.81
7.4 1.00
10.5 0.44
0.8 1.00
0.3 0.96
0.1 0.50
0.4 0.50
T/O 1.00
1.6 0.80
0.1 0.50
1.6 0.64
15.3 0.81
10 0.50
18.2 0.88
4 0.6411.2 (2.07×)
25 (+32.0%)* UR means the uncontrolled-recursion bug, UA means the uncontrolled-memory-allocation bug. T/O means the fuzzer can’t find this vulnerability throughout 24 hours across 5

repetitions. When we calculate the average time usage, we replace T/O with 24 hours. We highlight the Â12 in the bold if its corresponding Mann-Whitney U test is significant.

from 234% to 3753163%, compared to other baseline fuzzers. This isbecause MemLock tries to maximize each allocation and generates
inputs with high memory consumption. When the memory leakhappens, those memory-consuming inputs will often cause morebytes memory leakage.

From the analysis of Table 2, the case study and new vulnerabilities MemLock found, we can positively answer RQ2
that MemLock significantly outperforms the state-of-the-art
fuzzers in terms of real-world memory consumption vulnerability detection.

4.4

From the results in Table 3, we can answer RQ3 that MemLock
significantly magnifies the memory leakage comparing to
the state-of-the-art fuzzing techniques, due to its memory
consumption guidance.

Memory Leakage Evaluation (RQ3)

Memory leak bugs are a little different from uncontrolled-recursion
and uncontrolled-memory-allocation bugs, because they may notlead to program crashes immediately. Only enough memory isleaked, it would produce Denial-of-Service (DoS) attack, for example, in a long time running programs (e.g., banking service). To
evaluate the effectiveness of fuzzers in finding memory leaks, welook into the number of total bytes leaked during 7 different fuzzers
within 24 hours
Table 3 shows the amount of memory leak (in bytes) identified
by each fuzzer that may occur in different programs. We can seethat MemLock shows an obvious advantage over other baselinefuzzers. The number of bytes leaked is improved (increased) by

4.5

Memory Consumption Evaluation (RQ4)

Since MemLock seeks to generate test inputs that consume more
and more memory. In this experiment, we evaluate the test input distribution according to memory consumption for MemLock,
AFL, AFLfast, PerfFuzz, FairFuzz, Angora and QSYM. A fuzzer thatmaintains a seed pool with a larger proportion of high memory consumption inputs is considered to have a better chance of detecting
memory consumption bugs.
9

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

0# of seeds in seed pool

AFL
AFLfastFairFuzz

103

MemLock
PerfFuzz
QSYM

102
101
100

0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0
amount of consumed heap memory (bytes)1e9

0

AFL
AFLfastFairFuzz

103

MemLock
PerfFuzz
QSYM

102
101
100

103
102
101
0

5000 10000 15000 20000
the peak length of call stack

openjepg

AFL
AFLfastFairFuzz

103

MemLock
PerfFuzz
QSYM

102
101
100

yara

0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0
amount of consumed heap memory (bytes)1e9

AFL
AFLfastFairFuzz

103

MemLock
PerfFuzz
QSYM

102
101
100

5000 10000 15000 20000 25000 30000
the peak length of call stackjasper104

0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0
amount of consumed heap memory (bytes)1e9

MemLock
PerfFuzz
QSYM# of seeds in seed pool

101
100

5000 10000 15000 20000 25000
the peak length of call stack

readelf

104

102

flex

AFL
AFLfastFairFuzz

104

02000 4000 6000 8000 10000
the peak length of call stacklibming104# of seeds in seed pool

100

103

MemLock
PerfFuzz
QSYM# of seeds in seed pool

101

AFL
AFLfastFairFuzz# of seeds in seed pool

102

nasm

# of seeds in seed pool

103

MemLock
PerfFuzz
QSYM# of seeds in seed pool

# of seeds in seed poolnm

AFL
AFLfastFairFuzz

Cheng Wen et al.

103

AFL
AFLfastFairFuzz

MemLock
PerfFuzz
QSYM

102
101
100

0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0
amount of consumed heap memory (bytes)1e9

Figure 6: Seed distribution based on memory consumption. The larger the value on the right side is better.
The results clearly demonstrate the effectiveness of the strategiesof MemLock in generating inputs with high memory consumption.

Table 3: Total Leak Bytes
Programbento4libming

jsaperTool
leakge (Bytes) Improve. p -value Â12
MemLock
52,709,574
AFL
151,862+34609%0.0061 1.00
AFLfast1,233,255+4174%
0.0061 1.00
memory leak PerfFuzz
105,984+49633%0.0061 1.00
FairFuzz
1,910,466+2659%
0.0061 1.00
Angora141,512+37147%0.0060 1.00
QSYM
15,784,847+234%
0.0061 1.00
MemLock
176,320,785
AFL
4,869,594+3521%
0.0061 1.00
AFLfast2,535,212+6855%
0.0061 1.00
memory leak PerfFuzz
47,044,964+257%
0.0061 1.00
FairFuzz
828,742+21176%0.0061 1.00
Angora4,698 +3753163%
0.0060 1.00
QSYM
1,219,093+14363%0.0061 1.00
MemLock 2,372,844,732
AFL
56,018,839+4136%
0.0061 1.00
AFLfast48,403,244+4802%
0.0061 1.00
memory leak PerfFuzz
6,229,898+37988%0.0061 1.00
FairFuzz
56,788,235+4096%
0.0061 1.00
Angora191,907,941+1136%
0.0105 0.98
QSYM
38,244,568+6104%
0.0061 1.00
Type

After analyzing Figure 6, we can answer RQ4 that the strategies of MemLock indeed help to generate inputs with highmemory consumption.

4.6

Discussion

Additional Experiments. The above four groups of experiments
show that MemLock is effective and efficient in finding memory
consumption vulnerabilities. Since MemLock focuses on the spacecomplexity issues, it may fall behind other baseline fuzzers in otherperformance metrics. For example, MemLock intentionally keeps
seeds that increase memory consumption, which may degrade its
capability of identifying other types of vulnerabilities. We havetherefore evaluated the capability of finding other types of crashes.
In the benchmark programs, MemLock, AFL, AFLfast, PerfFuzz,
FairFuzz, Angora and QSYM find 77, 239, 228, 189, 276, 343 and 236
other types of unique crashes, respectively. Moreover, our approach
may also incur some runtime overhead. Therefore, we compare
the code coverage and execution speed for each baseline fuzzer.
In total, the number of executed test inputs in MemLock ranges
from 20% to 84% of those in AFL, AFLfast, FairFuzzer and QSYM.
Among all the fuzzers, PerfFuzz performs the worst likely due tothe fact that it prefers the test inputs that execute long instructions.
Considering the code coverage, MemLock achieves the comparable
code coverage, compared to the fuzzers AFL, AFLfast, FairFuzzer
and QSYM. PerfFuzz still performs the worst among those fuzzers,
and in most cases it only achieves the code coverage from about
60% to 70% of those in other fuzzers. All extra experimental results
and data are available on our website[48] for interested readers.
Threats to Validity. We selected a variant of real-world programs
to show the capabilities of MemLock, and compared it against otherstate-of-the-art fuzzers. However, our benchmarks may still include

Figure 6 shows the input distribution based on memory consumption. In general, we can clearly see that MemLock can generate
more seeds with higher memory consumption. This is because theguidance mechanisms in MemLock help to gradually add more
and more memory consuming inputs into the seed pool. In particular, for the uncontrolled-recursion bugs (nm, nasm, flex andyara), MemLock generates a large number of inputs that hold morethan 30,000 function calls in the call stack, while PerfFuzz generates only a few and AFL/AFLfast can hardly generate inputs
that hold more than 10,000 function calls. The pattern is similar
for uncontrolled-memory-allocation bugs (readelf, openjpeg, jasperand libming). MemLock can generate a considerable amount of
inputs with high memory consumption while the inputs of theother fuzzers concentrate on the low memory consumption region.
10

MemLock: Memory Usage Guided Fuzzing

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

a certain sample bias. Further studies on more real-world programs
can help better evaluate MemLock. Besides, MemLock also suffersfrom the difficulty in breaking through hard comparisons (e.g.,
magic bytes) as most work [7, 11, 28]. Adopting some program
analysis techniques (e.g., symbolic execution) might help mitigate
this threat.

5

usage of functions. Duc-Hiep et al. [15] presents a worst-case memory consumption analysis, which uses symbolic execution to exhaustively unroll loops and compute memory consumption of each
iteration. He et al. [31] and Chin et al. [14] employ static verification
to check a program’s memory usage is within the memory bounds,
while Chin et al. [13] uses static analysis to compute the memory usage bounds for assembly level programs. These approaches
rely on type theory or symbolic execution, thus they often sufferfrom the scalability issue. SMOKE [26] is a path-sensitive memory
leak detector for millions of lines of code. It first uses a scalable
but imprecise analysis to compute a set of candidate memory leakpaths and then verifies the feasibility of the candidates using a more
precise analysis. While SMOKE can demonstrate the existence ofmemory leak, MemLock can generate an input that produces thememory leak.
Dynamic Analysis. Yuku et al. [46] proposes an improved realtime scheduling algorithm to reduce maximal heap memory consumption by controlling multitask scheduling. Different from MemLock, this technique aims at reducing memory consumption by
dynamic online scheduling while MemLock is to find memory consumption bugs. BLEAK [69] is a system to debug memory leaks in
web applications. It leverages the observation that users often repeatedly return to the same visual state. Sustained growth between
round trips is a strong indicator of a memory leak. BLEAK is only
applicable to memory leak of web applications, while MemLock canfind several kinds of memory consumption bugs. Radmin [24] is asystem for early detection of application-level resource exhaustionand starvation attacks. It first learns and executes multiple probabilistic finite automata from its benign executions. It then restricts
the resource usage to the learned automata and detects resource
usage anomalies. Radmin uses some heuristics to detect resource
usage anomalies, while MemLock employs the fuzzing technique toautomatically generate the inputs for memory consumption bugs.

RELATED WORK

Coverage-based Grey-box Fuzzing. Coverage-based grey-box
fuzzing [3, 39, 41, 44, 47, 57, 66] is one of the most effective techniques to find vulnerabilities and bugs, and has attracted a great
deal of attention from both academic and industry. Coverage-based
grey-box fuzzers typically adopt the coverage information to guidedifferent program path explorations. For example, Google has built
an OSS-FUZZ platform [61] by incorporating several state-of-theart coverage-based grey-box fuzzers: libFuzzer [45], honggfuzz [9],AFL [84] and ClusterFuzz [30].
Since a coverage guidance engine is a key component for thegrey-box fuzzers, much effort has been devoted to improve theircoverage. Steelix [40], Vuzzer [59] and REDQUEEN [3] use programstate analysis or taint analysis to penetrate some paths protected bymagic bytes comparisons. QSYM [83], Driller [64] and SAFL [76]equips grey-box fuzzing with a symbolic execution engine to reachdeeper program code. Angora [12] adopts a gradient descent technique to solve path constraints so as to break some hard comparisons. MemFuzz [16] augmenting evolutionary fuzzing by additionally leveraging information about memory accesses (insteadof memory consumption) performed by the target program. ProFuzzer [82], GRIMOIRE [6], Superion [75] and Zest [56] leverage
the knowledge in highly-structured files to generate syntacticallyand semantically valid test inputs, and thus be able to touch deeper
program code. CollAFL [28] proposes a coverage sensitive fuzzing
solution to mitigate the path collisions. FairFuzz [38] leverages
a targeted mutation strategy to execute towards rare branches.
UAFL [73] incorporates typestate properties and information flow
to their fuzzing engine to guide the detection of use-after-freevulnerabilities. Besides, AFLgo [7] and Hawkeye [11] use the distance metrics to execute towards user-specified target sites in the
program. The main difference between MemLock and these stateof-the-art fuzzers is that, MemLock aims at memory consumption
bugs while the others are to find memory corruption vulnerabilities.
Thus, MemLock is orthogonal to these state-of-the-art fuzzers.
Recently, researchers have paid attention to the algorithmic complexity vulnerabilities (i.e., time complexity issues) such as SlowFuzz [58], Singularity [77] and PerfFuzz [37]. They use the numberof executed instructions as the guidance to explore the program
path with a longer path length. In contrast with MemLock, they
stress the time complexity issues while MemLock considers spacecomplexity issues. The space complexity issues have its own uniquecharacteristics, as the amount of memory consumption can increase(e.g., function entry, memory allocation) and decrease (e.g., function
exit, memory free), MemLock takes both of them into consideration.
Static Analysis. Static analysis is also used to analyze memory
consumption [1, 10, 13, 14, 31, 34, 70]. Wang et al. [70] presents a
type-guided worst-case input generation by using automatic amortized resource analysis to derive symbolic bounds on the resource

6

CONCLUSION

In this paper, we propose MemLock, an enhanced grey-box fuzzing
technique to find memory consumption bugs. MemLock employs
both coverage and memory consumption information to guide thefuzzing process. The coverage information guides the explorationof different program paths, while the memory consumption information guides the search for those program paths that exhibit more
and more memory consumption. Our experimental results haveshown that MemLock outperforms state-of-the-art fuzzing techniques (i.e., AFL, AFLfast, PerfFuzz, FairFuzz, Angora and QSYM)
in detecting memory consumption bugs. We also found 15 securitycritical vulnerabilities in some real-world programs. At the time ofwriting, 12 of these vulnerabilities have been patched.

ACKNOWLEDGEMENTS
This work was supported in part by the National Natural Science Foundation of China under Grants No. 61772347, 61836005,
61972260, 61772408, 61721002, Ant Financial Services Group throughAnt Financial Research Program, Guangdong Basic and Applied
Basic Research Foundation under Grant No. 2019A1515011577, National Key R&D Program of China under Grant No. 2018YFB0803501.
11

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

Cheng Wen et al.

REFERENCES[30] Google. 2019. ClusterFuzz. https://google.github.io/clusterfuzz/.
[31] Guanhua He, Shengchao Qin, Chenguang Luo, and Wei-Ngan Chin. 2009.
Memory Usage Verification Using Hip/Sleek. In 7th International Symposium
on Automated Technology for Verification and Analysis (ATVA 2009). 166–181.
https://doi.org/10.1007/978-3-642-04761-9_14[32] Jasper. 2019. Image Processing/Coding Tool Kit. https://www.ece.uvic.ca/~frodo/
jasper/. accessed: 2019-08-01.
[33] Xiangkun Jia, Chao Zhang, Purui Su, Yi Yang, Huafeng Huang, and Dengguo
Feng. 2017. Towards efficient heap overflow discovery. In 26th USENIX Security
Symposium. 989–1006.
[34] Daniel Kästner and Christian Ferdinand. 2014. Proving the absence of stack
overflows. In International Conference on Computer Safety, Reliability, and Security.
Springer, 202–213.
[35] 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.
[36] Chris Lattner and Vikram Adve. 2004. LLVM: A compilation framework forlifelong program analysis & transformation. In Proceedings of the international
symposium on Code generation and optimization: feedback-directed and runtime
optimization. IEEE Computer Society, 75.
[37] 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.
[38] Caroline Lemieux and Koushik Sen. 2018. Fairfuzz: A targeted mutation strategy
for increasing greybox fuzz testing coverage. In Proceedings of the 33rd ACM/IEEEInternational Conference on Automated Software Engineering. ACM, 475–485.
[39] Jun Li, Bodong Zhao, and Chao Zhang. 2018. Fuzzing: a survey. Cybersecurity 1,
1 (2018), 6.
[40] 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. ACM,
627–637.
[41] Hongliang Liang, Xiaoxiao Pei, Xiaodong Jia, Wuwei Shen, and Jian Zhang. 2018.
Fuzzing: State of the art. IEEE Transactions on Reliability 67, 3 (2018), 1199–1218.
[42] Libming. 2019. A library for generating Macromedia Flash files. http://www.
libming.org/. accessed: 2019-08-01.
[43] Libsass. 2019. A C/C++ implementation of a Sass compiler. https://github.com/
sass/libsass. accessed: 2019-08-01.
[44] Xiaolong Liu, Qiang Wei, Qingxian Wang, Zheng Zhao, and Zhongxu Yin. 2018.
CAFA: A Checksum-Aware Fuzzing Assistant Tool for Coverage Improvement.
Security and Communication Networks (2018).
[45] LLVM-Documentation. 2018. libFuzzer - a library for coverage-guided fuzz
testing. http://llvm.org/docs/LibFuzzer.html.
[46] Yuki Machigashira and Akio Nakata. 2018. An Improved LLF Scheduling for
Reducing Maximum Heap Memory Consumption by Considering Laxity Time.
In 2018 International Symposium on Theoretical Aspects of Software Engineering.
IEEE, 144–149.
[47] Valentin JM Manes, HyungSeok Han, Choongwoo Han, Sang Kil Cha, Manuel
Egele, Edward J Schwartz, and Maverick Woo. 2018. Fuzzing: Art, Science, andEngineering. arXiv preprint arXiv:1812.00140 (2018).
[48] MemLock. accessed: 2020-01-01.
MemLock’s Home Page.
https://
icse2020-memlock.github.io/.
[49] MITRE. accessed: 2019. CWE-400: Uncontrolled Resource Consumption. https://cwe.mitre.org/data/definitions/400.html.
[50] MITRE. accessed: 2019. CWE-401: Missing Release of Memory after Effective
Lifetime. https://cwe.mitre.org/data/definitions/401.html.
[51] MITRE. accessed: 2019. CWE-674: Uncontrolled Recursion. https://cwe.mitre.
org/data/definitions/674.html.
[52] MITRE. accessed: 2019. CWE-789: Uncontrolled Memory Allocation. https://cwe.mitre.org/data/definitions/789.html.
[53] mjs. 2019. mjs: Restricted JavaScript engine. https://github.com/cesanta/mjs.
accessed: 2019-08-01.
[54] Nasm. 2019. The Netwide Assembler. https://www.nasm.us. accessed: 2019-08-01.
[55] Openjpeg. 2019. An open-source JPEG 2000 codec written in C language. https://github.com/uclouvain/openjpeg. accessed: 2019-08-01.
[56] Rohan Padhye, Caroline Lemieux, Koushik Sen, Mike Papadakis, and Yves
Le Traon. 2019. Semantic Fuzzing with Zest. In Proceedings of the 28th ACM
SIGSOFT International Symposium on Software Testing and Analysis (ISSTA’19).
[57] Hui Peng, Yan Shoshitaishvili, and Mathias Payer. 2018. T-Fuzz: fuzzing by
program transformation. In 2018 IEEE Symposium on Security and Privacy. IEEE,
697–710.
[58] 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, 2155–2168.
[59] Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida,and Herbert Bos. 2017. Vuzzer: Application-aware evolutionary fuzzing. In[1] Jeppe L Andersen, Mikkel Todberg, Andreas E Dalsgaard, and René Rydhof
Hansen. 2013. Worst-case memory consumption analysis for SCJ. In Proceedings ofthe 11th International Workshop on Java Technologies for Real-time and Embedded
Systems. ACM, 2–10.
[2] Andrea Arcuri and Lionel Briand. 2011. A practical guide for using statistical tests
to assess randomized algorithms in software engineering. In Software Engineering,
2011 33rd International Conference on. IEEE, 1–10.
[3] Cornelius Aschermann, Sergej Schumilo, Tim Blazytko, Robert Gawlik, andThorsten Holz. 2019. REDQUEEN: Fuzzing with Input-to-State Correspondence.
In Proceedings of the Network and Distributed System Security Symposium.
[4] Bento4. 2019. Full-featured MP4 format and MPEG DASH library and tools.
http://www.bento4.com. accessed: 2019-08-01.
[5] GNU binutils. 2019. a collection of binary tools. https://www.gnu.org/software/
binutils/. accessed: 2019-08-01.
[6] Tim Blazytko, Cornelius Aschermann, Moritz Schlögel, Ali Abbasi, Sergej Schumilo, Simon Wörner, and Thorsten Holz. 2019. GRIMOIRE: Synthesizing Structure
while Fuzzing. (2019).
[7] 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, 2329–2344.
[8] Marcel Böhme, Van-Thuan Pham, and Abhik Roychoudhury. 2017. Coveragebased greybox fuzzing as markov chain. IEEE Transactions on Software Engineering(2017).
[9] Maintained by Google. 2018. honggfuzz. http://honggfuzz.com/.
[10] Quentin Carbonneaux, Jan Hoffmann, Tahina Ramananandro, and Zhong Shao.
2014. End-to-end verification of stack-space bounds for C programs. In ACM
SIGPLAN Notices, Vol. 49. ACM, 270–281.
[11] 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, 2095–2108.
[12] Peng Chen and Hao Chen. 2018. Angora: Efficient fuzzing by principled search.
In 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 711–725.
[13] Wei-Ngan Chin, Huu Hai Nguyen, Corneliu Popeea, and Shengchao Qin. 2008.
Analysing memory resource bounds for low-level programs. In the 7th International Symposium on Memory Management, (ISMM 2008). 151–160. https://doi.org/10.1145/1375634.1375656[14] Wei-Ngan Chin, Huu Hai Nguyen, Shengchao Qin, and Martin C. Rinard. 2005.
Memory Usage Verification for OO Programs. In 12th International Symposiumon Static Analysis (SAS 2005). 70–86. https://doi.org/10.1007/11547662_7[15] Duc-Hiep Chu, Joxan Jaffar, and Rasool Maghareh. 2016. Symbolic execution formemory consumption analysis. ACM SIGPLAN Notices 51, 5 (2016), 62–71.
[16] Nicolas Coppik, Oliver Schwahn, and Neeraj Suri. 2019. MemFuzz: Using Memory
Accesses to Guide Fuzzing. In 2019 12th IEEE Conference on Software Testing,
Validation and Verification (ICST). IEEE, 48–58.
[17] CVE-2017-9804. 2017. Available from MITRE. https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2017-9804.
[18] CVE-2018-17985. 2018. Available from MITRE. https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-17985.
[19] CVE-2018-4868. 2019. Available from MITRE. https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-4868.
[20] CVE-2019-6291. 2019. Available from MITRE. https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-6291.
[21] CVE-2019-6292. 2019. Available from MITRE. https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-6292.
[22] CVE-2019-7704. 2019. Available from MITRE. https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2019-7704.
[23] CVE Details. accessed: 2019. The list of Vulnerabilities according to CWE-400:
Uncontrolled Resource Consumption. https://www.cvedetails.com/cwe-details/
400/Uncontrolled-Resource-Consumption-039-Resource-Exhaustion.html.
[24] Mohamed Elsabagh, Daniel Barbará, Dan Fleck, and Angelos Stavrou. 2018. On
early detection of application-level resource exhaustion and starvation. Journalof Systems and Software 137 (2018), 430–447.
[25] Exiv2. 2019. Image metadata library and tools. http://www.exiv2.org/. accessed:
2019-08-01.
[26] Gang Fan, Rongxin Wu, Qingkai Shi, Xiao Xiao, Jinguo Zhou Zhou, and Charles
Zhang. 2019. SMOKE: Scalable Path-Sensitive Memory Leak Detection for Millions of Lines of Code. In Proceedings of the 41st International Conference on
Software Engineering, ICSE, Gothenburg, Sweden.
[27] Flex. 2019. The Fast Lexical Analyzer - scanner generator for lexing in C andC++. https://github.com/westes/flex. accessed: 2019-08-01.
[28] 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, 679–696.
[29] Google. 2018. The list of common sanitizer options. https://github.com/google/
sanitizers/wiki/SanitizerCommonFlags.
12

MemLock: Memory Usage Guided Fuzzing

ICSE ’20, May 23–29, 2020, Seoul, Republic of Korea[73] Haijun Wang, Xiaofei Xie, Yi Li, Cheng Wen, Yang Liu, Shengchao Qin, Hongxu
Chen, and Yulei. Sui. 2020. Typestate-Guided Fuzzer for Discovering Use-afterFree Vulnerabilities. In 2020 IEEE/ACM 42nd International Conference on Software
Engineering. Seoul, South Korea.
[74] 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.
[75] Junjie Wang, Bihuan Chen, Lei Wei, and Yang Liu. 2019. Superion: GrammarAware Greybox Fuzzing. In Proceedings of the 41st International Conference on
Software Engineering, ICSE, Gothenburg, Sweden.
[76] Mingzhe Wang, Jie Liang, Yuanliang Chen, Yu Jiang, Xun Jiao, Han Liu, Xibin
Zhao, and Jiaguang Sun. 2018. SAFL: increasing and accelerating testing coverage with symbolic execution and guided fuzzing. In Proceedings of the 40thInternational Conference on Software Engineering: Companion Proceeedings. ACM,
61–64.
[77] Jiayi Wei, Jia Chen, Yu Feng, Kostas Ferles, and Isil Dillig. 2018. Singularity:
Pattern fuzzing for worst case complexity. In Proceedings of the 2018 26th ACM
Joint Meeting on European Software Engineering Conference and Symposium on
the Foundations of Software Engineering. ACM, 213–223.
[78] Technical whitepaper for afl fuzz. 2019. american fuzzy lop. http://lcamtuf.
coredump.cx/afl/technical_details.txt. accessed: 2019-08-01.
[79] Zhiwu Xu, Cheng Wen, and Shengchao Qin. 2018. State-taint analysis for detecting resource bugs. Science of Computer Programming 162 (2018), 93–109.
[80] yaml cpp. 2019. A YAML parser and emitter in C++. https://github.com/jbeder/
yaml-cpp. accessed: 2019-08-01.
[81] Yara. 2019. The pattern matching swiss knife for malware researchers. http://virustotal.github.io/yara/. accessed: 2019-08-01.
[82] 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 Security and Privacy, 2019 IEEE Symposium
on. IEEE.
[83] 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.
[84] Michal Zalewski. 2017. American Fuzzy Lop 2.52b. http://lcamtuf.coredump.cx/
afl/.

Proceedings of the Network and Distributed System Security Symposium.
[60] Alexey Samsonov and Kostya Serebryany. 2013. New features in addresssanitizer.
(2013).
[61] Kostya Serebryany. 2017. OSS-Fuzz-Google's continuous fuzzing service for open
source software. (2017).
[62] Konstantin Serebryany, Derek Bruening, Alexander Potapenko, and Dmitriy
Vyukov. 2012. AddressSanitizer: A fast address sanity checker. In Presented aspart of the 2012 USENIX Annual Technical Conference. 309–318.
[63] Yuju Shen, Yanyan Jiang, Chang Xu, Ping Yu, Xiaoxing Ma, and Jian Lu. 2018. ReScue: crafting regular expression DoS attacks. In Proceedings of the 33rd ACM/IEEEInternational Conference on Automated Software Engineering. ACM, 225–235.
[64] Nick Stephens, John Grosen, Christopher Salls, Andrew Dutcher, Ruoyu Wang,
Jacopo Corbetta, Yan Shoshitaishvili, Christopher Kruegel, and Giovanni Vigna.
2016. Driller: Augmenting Fuzzing Through Selective Symbolic Execution.. In
NDSS, Vol. 16. 1–16.
[65] Laszlo Szekeres, Mathias Payer, Tao Wei, and Dawn Song. 2013. Sok: Eternal war
in memory. In Security and Privacy, 2013 IEEE Symposium on. IEEE, 48–62.
[66] Ari Takanen, Jared D Demott, Charles Miller, and Atte Kettunen. 2018. Fuzzing
for software security testing and quality assurance. Artech House.
[67] Victor Van der Veen, Lorenzo Cavallaro, Herbert Bos, et al. 2012. Memory errors:
The past, the present, and the future. In International Workshop on Recent Advancesin Intrusion Detection. Springer, 86–106.
[68] András Vargha and Harold D Delaney. 2000. A critique and improvement of
the CL common language effect size statistics of McGraw and Wong. Journal of
Educational and Behavioral Statistics 25, 2 (2000), 101–132.
[69] John Vilk and Emery D Berger. 2018. BLeak: automatically debugging memory
leaks in web applications. In Proceedings of the 39th ACM SIGPLAN Conference on
Programming Language Design and Implementation. ACM, 15–29.
[70] Di Wang and Jan Hoffmann. 2019. Type-Guided Worst-Case Input Generation.
Proceedings of the ACM on Programming Languages (2019).
[71] 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.
[72] 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.

13