Locating Vulnerabilities in Binaries via Memory Layout
Recovering
Haijun Wang

Xiaofei Xie∗

Shang-Wei Lin

Shenzhen University
China
Nanyang Technological University
Singapore

Nanyang Technological University
Singapore

Nanyang Technological University
Singapore

Yun LinYuekang Li

Shengchao Qin

National University of Singapore
Singapore

Nanyang Technological University
Singapore

Teesside University
United Kingdom

Yang Liu

Ting Liu

Nanyang Technological University
Singapore

Xi’an Jiaotong University
China

ABSTRACT
Locating vulnerabilities is an important task for security auditing,
exploit writing, and code hardening. However, it is challenging
to locate vulnerabilities in binary code, because most program
semantics (e.g., boundaries of an array) is missing after compilation.
Without program semantics, it is difficult to determine whether amemory access exceeds its valid boundaries in binary code. In thiswork, we propose an approach to locate vulnerabilities based on
memory layout recovery. First, we collect a set of passed executions
and one failed execution. Then, for passed and failed executions, we
restore their program semantics by recovering fine-grained memory
layouts based on the memory addressing model. With the memory
layouts recovered in passed executions as reference, we can locate
vulnerabilities in failed execution by memory layout identificationand comparison. Our experiments show that the proposed approachis effective to locate vulnerabilities on 24 out of 25 DARPA’s CGC
programs (96%), and can effectively classifies 453 program crashes(in 5 Linux programs) into 19 groups based on their root causes.

CCS CONCEPTS• Theory of computation → Program analysis; • Softwareand its engineering → Software reverse engineering.

KEYWORDS
Reverse Engineering; Software Vulnerability; Program Analysis∗ Xiaofei Xie (xfxie@ntu.edu.sg) is the corresponding author.

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.
ESEC/FSE ’19, August 26–30, 2019, Tallinn, Estonia© 2019 Association for Computing Machinery.
ACM ISBN 978-1-4503-5572-8/19/08. . . $15.00
https://doi.org/10.1145/3338906.3338966

ACM Reference Format:
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 27th ACM Joint European
Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE ’19), August 26–30, 2019, Tallinn, Estonia. ACM,
New York, NY, USA, 11 pages. https://doi.org/10.1145/3338906.3338966

1

INTRODUCTION

For memory unsafe languages like C/C++, memory corruption
vulnerability is one of the most severe defects, as it can lead tosoftware crash or even allows adversaries to take full control ofthe software. Buffer overflow is one of the most common memory
corruption vulnerabilities, which is also the focus of this paper.
There have been a number of techniques [1–4] that can locate
buffer overflows, and most of them are in the source code level, such
as AddressSanitizer [1]. However, the source code is not always
available (e.g., closed-source software). Further, the semantics of binary code may be different from its source code [5]. For the purposeof binary security auditing, exploit writing and code hardening, it ishighly significant to locate buffer overflows in binary code directly.
However, it is much more challenging to locate buffer overflows
in the binary code. When the source code is compiled into thebinary, its program semantics is missing, i.e., we are not able toidentify variables of program and their memory boundaries anymore. Without the memory boundaries, locating buffer overflows
in binary code becomes very difficult. Although there have beensome techniques working on the binary code (e.g., Valgrind Memchecks [3]), none of them can locate buffer overflows within thestack/global memory regions (e.g., overflow beyond an array but
still within its resident stack frame) [1]. To address these issues,
recovering the program semantics, i.e., memory boundaries of variables, is necessary to locate buffer overflows in binary code.
In addition, locating vulnerabilities highly benefits triaging program crashes in binaries [6]. It is shown that the same vulnerability
can produce various symptoms, leading to different crashes. For
example, the fuzzing system (e.g., fairfuzz, aflfast and aflgo [7–11])
usually generates a large number of crashes. However, not all ofESEC/FSE ’19, August 26–30, 2019, Tallinn, Estonia

these crashes are unique. Many of them are due to the same vulnerability. If the crashes can be grouped according to their root causes,
it would greatly improve the efficiency of analysis.
Aiming at addressing the above challenges, we propose an approach, based on dynamic execution information, to locate buffer
overflows in binaries. Our approach mainly consists of two parts:
recovering memory layout and locating vulnerabilities.
Recovering Memory Layout. A memory layout represents
the static data structure of a variable in source code, e.g., a data
structure with its members. In our approach, we actually use thedynamic execution information in binary code to restore static data
structure information of variables in source code. First, we identify the relevant addressing instructions for each memory accessin dynamic execution information. Second, we recover a memory
layout for each memory access based on the memory addressing
model. Third, if multiple memory layouts access the same variable,
we merge them into a memory layout, generating a more complete
static data structure for that variable. Compared to existing techniques [12–16], our approach can precisely recover fine-grained
memory layouts of variables (c.f. Section 6.1).
Locating Vulnerabilities. To locate buffer overflows, we needto determine whether the recovered memory layout in failed execution exceeds its valid boundaries. To infer the boundaries, wecollect a failed execution and a set of passed executions. In thispaper, the failed execution means to cause the program crash, while
the passed execution would not. The failed execution is the input
to our approach, and passed executions can be obtained easily fromexisting tools or test suites (c.f. Section 5.2). For passed executions,
we recover their memory layouts (called passed memory layouts),
which are considered as the memory layouts within valid boundaries. For the failed execution, we also recover its memory layouts(called failed memory layouts), which may include memory layouts
exceeding valid boundaries (called vulnerable memory layouts).
With the memory layouts recovered in passed executions as reference, we can locate vulnerable memory layout, i.e., candidate buffer
overflow, in the failed execution by memory layout identificationand comparison (see Section 4).
We have implemented the proposed approach in a prototype
tool, and evaluated its effectiveness in two different aspects: 1) locating vulnerabilities, and 2) triaging program crashes. In locating
vulnerabilities, our approach is effective to locate buffer overflow
vulnerabilities on 24 out of 25 DARPA’s CGC programs (96%). In
triaging experiments, our approach is able to classify the 453 program crashes (in 5 widely used Linux programs) into 19 groups,
while AFL reports 320 unique crashes (groups).
The contributions of this work are summarized as follows:• We formalize a memory addressing model, based on which, together with the dynamic execution information, we propose ageneral approach to precisely recover the static fine-grained hierarchical memory layouts of program variables.
• With the memory layouts recovered in passed executions as
reference, we propose an approach to locate buffer overflows infailed execution by memory layout identification and comparison.
By using fine-grained memory layouts, our approach can locate
buffer overflows within stack, global memory regions, and data
structures in binary code.

H. Wang, X. Xie, S. Lin, Y. Lin, Y. Li, S. Qin, Y. Liu, T. Liu• We implemented the proposed approach and evaluated its effectiveness on binary programs with diverse kinds of vulnerabilities.

2 APPROACH OVERVIEW
2.1 Motivating Example
Fig. 2 (a) shows a program with a buffer overflow vulnerability. If
the input of function test is (1, 4), the program crashes at Line 14.
The buffer overflow is triggered in the loop (Line 11). The variable
ptr → stu[1].name contains three elements, but is assigned withfour elements. As a result, the variable ptr → stu[1].func is overwritten, and the program crashes when Line 14 is executed (where
ptr → stu[1].func is accessed).
After being compiled into binaries, the program semantics is
missing, making it difficult to identify the variables and their boundaries. For example, the variable ptr → stu[1].name and its memory
boundaries (its size is 12 bytes) are missing in binaries. Without
this information, the buffer overflow cannot be identified when it
is written with 16 bytes.

2.2

Overview of our Approach

To address this issue, we propose an approach to locate buffer
overflows in binaries. The overall flow of the proposed approachis shown in Fig. 1. The input to our approach is a set of concrete
execution information (either passed or failed).
The proposed approach consists of four steps. In the first step,
given passed and failed executions, we identify relevant addressing
instructions for each memory access. In the second step, we recover
the memory layout for each memory access. Since one execution
may have multiple memory accesses, we may have more than
one memory layout recovered. If some of the recovered memory
layouts access the same variable, we merge them into one in thethird step. After this step, we have recovered memory layouts foreach execution (either passed or failed). In the fourth step, we use
the memory layouts of passed executions as reference to locate
buffer overflows in the failed execution. In the following, we walkthrough these steps using the motivating example in Fig. 2.
Step 1. We identify relevant addressing instructions for eachmemory access. To access a variable, the program first determines
its memory address. For a memory access instruction, we performa backward taint analysis to identify the relevant instructions used
to compute its memory address. Fig. 2 (b) shows several sets ofidentified instructions. For example, m 6 is a memory access instruction, we perform backward taint analysis and identify the relevant
instructions m 1 . . . m 6 , which correspond to Line 10 in Fig. 2 (a).
Step 2. We recover memory layout based on identified instructions for each memory access. In general, the memory address of avariable is computed by iteratively adding an offset to the addressof its enclosing variable. Based on this iterative process, we identify
the memory blocks (c.f. Definition 1), which represent the enclosed
variables. In addition, we construct their hierarchical structure, andfinally form a memory layout.
For example, consider instructions p1 . . . p6 , which correspond toLine 12 (e.g., ptr → stu[1].name[2] = 41). The recovered memory
layout is L 3 , as shown in Fig. 2 (c), where the red part is the real
memory layout of the variable, and the blue part is the recovered
memory layout (double-headed arrows below indicate memory

Locating Vulnerabilities in Binaries via Memory Layout Recovering
Dynamic execution information
Passed and failed
test cases
Passed and failed
execution information

ESEC/FSE ’19, August 26–30, 2019, Tallinn, Estonia

Static memory layout recovery
1

Identify relevant
instructions

2

Recover memory layout
on single access

3 Merge memory layouts
on multiple accesses

4 Locate vulnerabilities

Reports

Binary program

Figure 1: Overview of our approach0

typedef struct{
int name[3];void (*func)(void);}Stu;
typedef struct{
Stu stu[2];int a;}Info;
static int num = 1;
1: void f(void){
2:
...
3: }
12: ptr->stu[a].name[i] = 41;
4: void test(int a, int b) {5: Info *ptr = (Info*)malloc(sizeof(Info));
6: char *str = (char*)malloc(b);7: for(int i=0; i<b; i++){8:*str = 'a';9:
str = str +1;}
10: ptr->stu[a].func = &f;
11: for (int i=0; i<b; i++)12: ptr->stu[a].name[i] = 41;
13: ptr->stu[a].name[5*num -3] = 42;
14: ptr->stu[a].func();
15:}(a) Source code

Step 1…...
l1: mov -0x3c(%ebp),%eax
l2: movb $0x61,(%eax)
l3: addl $0x1,-0x3c(%ebp)…...
m1: mov -0xc(%ebp),%eax
m2: mov 0x8(%ebp),%edx
m3: shl $0x4,%edx
m4: add %edx,%eax
m5: add $0xc,%eax
m6: movl $0x804843b,(%eax)…...
p1: mov -0xc(%ebp),%eax
p2: mov 0x8(%ebp),%edx
p3: lea 0x0(,%edx,4),%ecx
p4: mov -0x10(%ebp),%edx
p5: add %ecx,%edx
p6: movl $0x29,(%eax,%edx,4)…...
q1: mov 0x804a020,%edx
q2: mov %edx,%eax
q3: shl $0x2,%eax
q4: add %edx,%eax
q5: lea -0x3(%eax),%ecx
q6: mov -0xc(%ebp),%eax
q7: mov 0x8(%ebp),%edx
q8: shl $0x2,%edx
q9: add %ecx,%edx
q10: movl $0x2a,(%eax,%edx,4)…...

Step 2(b) Identified relevant instructions

1

2

3

4
Real memory layout

str[0] str[1] str[2] str[3]Recovered memory layout

L1
12

0

16

28

32

ptr->stu[1]ptr->stu[0]
name
func

name

x1

func

x1+16

28

a

32

Step 3L2
12

0

ptr->stu[0]
name
func

16

24

28

36

32

ptr->stu[1]func

name[0,1] [2]Memory block

36

0

16

24

28

32

Step 4Lp

28 32

Passed memory layout

a

L3

16

0

28 32

overflowLf
120

ptr->stu[0]
name
func

16

24

28

36

32

ptr->stu[1]name[0,1] [2]func

Failed memory layoutaL4(c) Memory layout on single access(d) Merged memory layout(e) Reported root cause

Figure 2: Illustration example for our approach
blocks). Based on identified instructions, we can infer that: thememory address is computed by adding two offsets (16 and 8) to thebase address, and then is written with four bytes. Based on this information, we identify two memory blocks [0, 28] and [16, 28], where
0 represents a relative base address. In addition, we construct theirhierarchical structures. The memory block [16, 28] is enclosed in[0, 28]. The identified memory blocks actually correspond to thevariables in source code. For example, [0, 28] and [16, 28] represents
arrays ptr → stu and ptr → stu[1].name, respectively. The hierarchical structures reflect the enclosing/enclosed relationships ofvariables. The variable ptr → stu[1].name is enclosed in ptr → stu.
Step 3. When multiple memory accesses operate on the same
variable in the executions (e.g., in the unrolled loop), corresponding
recovered memory layouts should be merged. For example, thememory layouts L 2 and L 3 in Fig. 2 (c) represent the same variable,
we merge them into a more complete memory layout Lp , as shownin Fig. 2 (d), which reflects not only the variable ptr → stu[1].func
but also ptr → stu[1].name.
Step 4. With above three steps, we recover memory layouts ofvariables. To locate vulnerabilities, we need to determine whether
the recovered memory layout in failed execution exceeds its valid
boundaries. With the memory layouts recovered in passed executions as reference, we locate buffer overflows in failed execution
by memory layout identification and comparison. For example, werecover a passed memory layout , i.e., test(1,3), and a failed memory
layout , i.e., test(1,4), as shown in Lp and L f of Fig. 2 (d). By memory
layout identification, memory blocks [16, 28] in Lp and [16, 32]
in L f are compared, and [28, 32] (i.e., ptr → stu[1].func) in L f isconsidered to be overflowed, as shown in Fig. 2 (e).
The proposed approach can help users in two scenarios: (1)One wants to disassemble or debug the binary program. With therecovered fine-grained memory layouts as debug symbols, he/she
can interpret some key data structures. (2) One has a binary programcrashed, and he/she wants to figure out whether the crash is due tothe buffer overflow and its root causes.

3

MEMORY LAYOUT RECOVERY

We first formalize a memory addressing model, and then introduce
the memory layout recovery based on memory addressing model.

3.1

Memory Addressing Model

Before a variable is accessed, its memory address needs to be determined first. In binary code, there are usually two addressing modes
for memory access: direct and indirect addressing [12]. In direct
addressing, the address is encoded in the instruction itself, usuallyused to access a scalar variable.
The indirect addressing mode is typically used to access an array or a data structure. Generally, the address is computed by anequation: address = base + (index ∗ scale) + offset, where index represents the index of an array, scale is the size of unit element in thearray, and offset implies the offset calculation for the member of adata structure.
The equation for indirect addressing depends on the hierarchicalstructure of a variable. For example, a data structure may containan array as its member or the element of an array can be a data
structure. Hence, there could be more than one index ∗ scale andoffset. A more general equation is:n
address = base +(index i ∗ scalei ) + offset(1)
i=1

In general, offset may be an optimized value due to the compilation,
i.e., offset = ni=1 offset i , where each offset i corresponds to one

ESEC/FSE ’19, August 26–30, 2019, Tallinn, Estonia

indexi ∗ scalei and offset i ≥ 0. The addressing equation is the key
insight for recovering memory layouts of variables in this paper.
Example 1. Consider ptr → stu[index 1 ].name[index 2 ] in Fig. 2(a),the memory address is calculated by: base +offset 1 +index 1 ∗scale 1 +offset 2 + index 2 ∗ scale 2 , where base = ptr is the base address;
offset 1 = 0 is the offset of stu in data structure ptr ; index1 ∗ scale1
calculates the address of the index 1 th element of stu; offset 2 = 0
is the offset of name in data structure stu[index 1 ]; index 2 ∗ scale 2
calculates the address of the index 2 th element of name.

3.2

Definition of Memory Layout

Definition 1. A memory block m is a tuple (m  ,m  , m), wherem is the start address and m  is the end address. If it represents anarray, m is the size of its unit element; Otherwise, m is zero. We use←→ to denote the size of m.
m
Definition 2. A memory layout L = (m,M,E) is a directed
acyclic graph (DAG), where m is the root memory block, M is a set ofmemory blocks, and E ⊂ M × M is a set of directed edges connecting
memory blocks such that (m 1 ,m 2 ) ∈ E if m 1 ≤ m 2 ∧ m 2 ≤ m 1 .
Definition 3. Given two memory blocks m 1 and m 2 , if m 1 andm 2 represent the same variable, they are the alias memory blocks; if
the variable represented by m 1 is enclosed in that represented by m 2 ,then m 1 is an inner memory block of m 2 .
Specifically, a directed edge (m 1 ,m 2 ) in memory layout L represents
that m 2 is the inner memory block of m 1 . A memory layout actuallyreflects the static hierarchical data structure of a variable (i.e., theenclosing/enclosed relationship).
Theorem 1. Given two memory blocks m 1 and m 2 , if they areintersected (i.e., m 1 < m 2 ∧ m 1 > m 2 ), and 0 < m2 ≤ m1 is true, m 2
is the alias or inner memory block of m 1 .
Theorem 2. Given two memory blocks m 1 and m 2 , if they are←→>mintersected (i.e., m 1 < m 2 ∧m 1 > m 2 ), and 0 < m2 ≤ m1 ∧ m1
2
is true, m 2 is the alias memory block of m 1 .

3.3

Memory Layout Recovery on Single
Memory Access

Memory layouts are recovered based on memory addressing model.
For the direct addressing, the recovered memory layout contains
only one memory block m, i.e., the accessed memory block, and its
unit element size is zero (i.e., m = 0). For the indirect addressing,the memory layout is recovered based on the following four steps:
3.3.1 Identifying Relevant Instructions. We first identify the relevant instructions, which compute the address for the memory
access. To achieve this goal, we perform a backward taint analysis,
in which the memory access instruction is regarded as the sink. Different from traditional taint analysis, we only propagate the taints
among the registers (not including registers esp and ebp), since
the memory address is computed by registers [17]. For example,
in Fig. 2(b) Line m 6 is a memory access instruction. Based on thetaint propagation among registers, we continue to identify Linesm 1 − m 5 . At Lines m 1 and m 2 , we stop the taint propagation as
their source operands are memory, not registers. As a result, theidentified addressing instructions are Lines m 1 -m 6 .

H. Wang, X. Xie, S. Lin, Y. Lin, Y. Li, S. Qin, Y. Liu, T. Liu

Algorithm 1: GenerateLayout


input : addr ess = base + n
i =1 (index i ∗ scal e i ) + offset
output : a memory layout L = (m, M, E )n1 Let offset =i x i , where x i represents offseti and x i ≥ 0;
2 start ←− base;
3 end ←− addr ess + sizeof (accessed memory) ;4 if ∀1 ≤ i ≤ n: index i ∗scal e i ≥ 0 then5M ←− ∅, E ←− ∅ ;6for i = 1 : n do
7start ←− start + x i ;8
m i ←− (start, end, scal e i );9M ←− M ∪ {m i } ;10
if i ≥ 2 then11E ←− E ∪ (m i −1, m i ) ;12
13

start ←− start + index i ∗scal e i ;m ←− m 1 ;else
15
m ←− (start, end , 0) ;16
M ←− {m }, E ←− ∅ ;1417return L ;3.3.2 Recovering Addressing Equation. After identifying relevant
instructions, we recover the addressing equation, based on the address calculation in identified instructions, in the form of Equation 1.
For example, we identify instructions (Lines m 1 -m 6 ) in Fig. 2(b),where Line m 6 is a memory access instruction. At Line m 1 , it stores
the address pointed by ptr to register eax, which is the base address.
At Line m 2 , it stores the value of variable a to register edx, which isindex 1 . Then, index 1 is multiplied by 16 at Line m 3 , and thus scale 1
is 16. At Line m 4 , it adds index 1 ∗scale 1 to the base address. At Linem 5 , it adds offset (i.e., 0xc) to compute the memory address. Thus,
the recovered addressing equation is: eax + (edx ∗ 16) + 12.
3.3.3 Optimizing Addressing Equation. The addressing equation
is optimized as follows: 1) Sorting n terms indexi ∗ scalei basedon the descending order of scalei for i ∈ {1, . . . ,n}. 2) Merging
some terms of index i ∗ scalei if possible. For two adjacent terms
index i ∗ scalei and index i+1 ∗ scalei+1 (1 ≤ i < n), if scalei <index i+1 ∗ scalei+1 , they are merged into one term index ∗ scale,where scale = gcd(scalei ,scalei+1 ) (i.e., greatest common divisor) and index = (index i ∗ scalei + index i+1 ∗ scalei+1 )/scale.
In fact, these two terms are used together to access the samearray. For example, the equation for array access int a[2p + q]
is recovered as: base +p ∗ (2 ∗ sizeof (int)) + q ∗ sizeof (int), wherep ∗ (2 ∗ sizeof (int)) and q ∗ sizeof (int) are used together to accessan array. Hence, they should be merged.
3.3.4 Recovering Memory Layout. Based on the optimized addressing equation, we recover the memory layout in Algorithm 1. It takes
the addressing equation as input, and outputs a recovered memory
layout. As described in Section 3.1, offset in the equation may be
an optimized value. Thus, at Line 1 we introduce the parameter x i
to represent each possible offseti . We recover the memory layout
based on two cases: (1) if every index i ∗ scalei in the equation isgreater than or equal to zero, the memory layout can be recovered
normally (Lines 4–13). We iteratively identify the memory blocks
and construct their hierarchical structure (Lines 6–12). In this loop,Locating Vulnerabilities in Binaries via Memory Layout Recovering

we first compute the start address of a memory block by adding
the offset x i (Line 7). Then, we recover this memory block mi atLine 8, and its unit size is scalei . At Line 11, we add a directed edge(mi−1 , mi ). Last, we calculate the address of the index i th element
and continue to recover the next memory block (Line 12). (2) If there
is an index i ∗scalei that is negative (i.e., index i is negative), it may
be used to access an array with other index j ∗scale j together. For
example, in ptr → stu[a].name[5 ∗ num − 3], -3 (i.e., index i ) is used
to access array name with 5 ∗ num (i.e., index j ) together. However,
we cannot determine whether a or 5 ∗ num is used to access anarray together. In this case, we adopt a conservative strategy to
only recover the largest memory block (Line 15).
Example 2. In Fig. 2(a), we assume that the address pointed
by pointer ptr is 0 and the value of variable a is 1. Based on Linesm 1 −m 6 in Fig. 2(b), we can recover an equation: 0+1∗16+12. We use
x 1 and x 2 to represent the optimized offsets, i.e., x 1 +x 2 = 12. Basedon Line 8 of Algorithm 1, a memory block (x 1 , 32, 16) is identified.
Hence, we recover a memory layout, as L 2 in Fig. 2(c). For Lines
q 1 − q 10 , we recover an equation: 0 + 1 ∗ 20 + 1 ∗ 16 + (−3 ∗ 4). Since
index 3 ∗ scale 3 (i.e., −3 ∗ 4) is negative, we only recover the largest
memory block (0, 28, 0), as L 4 in Fig. 2(c).

3.4

Memory Layout Recovery on Multiple
Memory Accesses

When multiple memory accesses operate on the same variable (e.g.,in the unrolled loop), corresponding recovered memory layouts
should be merged to generate a more complete one. Notice thatmultiple memory accesses could happen in the same or different
executions. It is non-trivial to infer which memory layouts can bemerged because their concrete memory addresses cannot be used asa unique identification. Hence, we first index the memory layouts
to make their memory addresses in a relative coordinate system sothat we can determine whether they can be merged.
3.4.1 Indexing Memory Layout. Assume that the address space of aprogram consists of several non-overlapping memory-regions [12,18]: stack, heap, and global, which correspond to functions, heapallocation statements and global/static variables, respectively. Specifically, each function has a memory-region, i.e., its stack frame; oneheap-allocation statement has a memory-region; the data section isa memory-region including global/static variables. Hence, the concrete memory address can be indexed by a pair: (memory-region,
offset). The indexing process is described as follows:• For variable a which is a local variable in a function f (stackmemory), we index its memory address by the pair ( f , &a − fp),
where f represents the memory region associated with f , &a is
the concrete memory address of a, and fp is the frame pointer off (e.g., register ebp).
• For variable a which is an enclosed variable (e.g., the member ofa data structure) in heap memory allocated at statement s, we
index its memory address by the pair (s, &a − ptr (s)), where s represents the memory region associated with the heap-allocation
statement s, &a is the concrete memory address of a, and ptr (s)is the base address of memory allocated at statement s.
• For variable a which is a global/static variable in global memory,
we index its memory address by the pair (д, &a − ds), where д is

ESEC/FSE ’19, August 26–30, 2019, Tallinn, Estonia

Algorithm 2: MergeLayout
input : memory layouts L 1 =(m 1 ,M 1 ,E 1 ) and L 2 =(m 2 ,M 2 ,E 2 )output : merged memory layout L =(m , M , E )if m 1 < m 2 ∧ m 1 > m 2 then2L ←− MergeBlock(L 1, L 2 );3
L ←− UpdateLayout(L ) ;4
return L ;15else return NIL ;the memory region associated with data section (often denoted.data in binary code), &a is the concrete memory address of a,and ds is the base address of data section.
After indexing, the addresses of memory layouts are in the same
coordinate, i.e., they are relative to the beginning of a memoryregion. Hence, we can merge the memory layouts.
3.4.2 Merging Memory Layouts. Given two memory layouts L 1 andL 2 , we merge them based on two cases, as shown in Algorithm 2.
The first case is that their root memory blocks m 1 and m 2 areintersected (Line 1). We first merge the root memory blocks of
L 1 and L 2 by MergeBlock (i.e., Algorithm 3), and construct a newmemory layout L . Then, we continue to merge the children of L
by UpdateLayout (i.e., Algorithm 5). The second case is that m 1
and m 2 are not intersected. They represent different variables, andcannot be merged. Next, we introduce the merging in the first case.
Algorithm 3 introduces how to merge root memory blocks m 1
and m 2 of L 1 and L 2 . At Line 1, it makes sure that m
2 ≤ m1 is true.
Thus, m 2 is the alias or inner memory block of m 1 (c.f. Theorem 1).
At Lines 2-3, it merges m 1 and m 2 as a new memory block m , andconstructs a new memory layout L . Then, it determines whether
m 2 is the inner memory block of m by DetermineLevel (i.e., Algorithm 4). If so, m 2 is added as the inner memory block of m(Line 6). Otherwise, m 2 and m are alias memory blocks, or theirrelationship cannot be determined. It adds the inner memory blocks(i.e., children) of m 2 as the inner memory blocks of m (Lines 8-10),
and deletes m 2 (Line 11). Note that, when the relationship between
m 2 and m cannot be determined, the algorithm ignores the casethat m 2 is the inner memory block of m . As a result, it may lose
some precision but is still correct. If the unit size of m 2 is zero, theunit size of m is updated as zero (Line 12).
Given two memory blocks m 1 and m 2 such that m
2 ≤ m1 (c.f.
Algorithm 3), Algorithm 4 determines whether m 2 is the alias or
inner memory block of m 1 . At Lines 1-3, it decides that m 2 is thealias memory block of m 1 (c.f. Theorem 2). If it cannot determine
m 2 is the alias memory block of m 1 , we consider the inner memory
block mc of m 1 at Lines 5-11. It first checks whether m 2 and mc
are intersected (Line 6). Then, it checks whether m2 ≤ mc is true(Line 7). If so, m 2 is the alias or inner memory layout of mc (c.f.
Theorem 1). Based on transitivity, m 2 is the inner block of m 1 . At
Line 10, it checks whether m 2 is the alias block of mc (c.f. Theorem 2).
If so, m 2 is also the inner block of m 1 based on transitivity.
3.4.3 Update Memory Layout. Algorithm 5 iteratively merges submemory layouts by a queue Q. The input is a memory layout L andthe output is an updated one L . For the memory block mq , it first
identifies two sub-memory layouts L 1 and L 2 (Line 6-7). If their root
memory blocks m 1 and m 2 are intersected (Line 8), we merge them

ESEC/FSE ’19, August 26–30, 2019, Tallinn, Estonia

H. Wang, X. Xie, S. Lin, Y. Lin, Y. Li, S. Qin, Y. Liu, T. Liu

Algorithm 3: MergeBlock

Algorithm 5: UpdateLayout

input : memory layouts L 1 =(m 1 ,M 1 ,E 1 ) and L 2 =(m 2 ,M 2 ,E 2 )output : merged memory layout L =(m , M , E )1 if 0 < m
1 < m2 then swap(L 1 , L 2 ) ;2 (m , M , E ) ←− (m 1, M 1 ∪ M 2, E 1 ∪ E 2 );  ) ←− (min(m  , m  ), max (m  , m  ), m
3 (m , m , m
1
2
1
2 1 );
4 st atus ←− DetermineLevel(m , m 2 );5 if m 2 is the inner memory block of m in st atus then6E ←− E ∪ {(m , m 2 ) };input : memory layout L = (m, M, E )output : updated memory layout L = (m, M , E )

7
8
9
10
11
12
13

else
foreach mc ∈ Child (m 2 ) doE ←− E \ {(m 2, mc ) } ;E ←− E ∪ {(m , mc ) } ;M ←− M \ {m 2 };if m
2 == 0 then m ←− 0 ;return L ;Algorithm 4: DetermineLevel
input : memory blocks m 1 and m 2
output : determining relationship between m 1 and m 2
1 if m1  0 and m
2  0 then
←
→>m
2
if m
1 then2
3
return m 2 is alias memory block of m 1 ;
4
5
6
7
8
9

2

foreach mc ∈ Child (mq ) do
Q .ENQUEUE(mc ) ;

15
16
17

return L ;L2

m1(x,32,16)

L3m2(0,28,16)

Lpm'(0,32,16)

else
foreach mc ∈ Child (m 1 ) do
if mc < m 2 and mc > m 2 thenif m
2 ≤ mc thenreturn m 2 is inner memory block of m 1 ;
else

10
11

12

L ←− L ;Let Q be an empty queue ;3 Q .ENQUEUE(m) ;4 while Q is not empty do5mq ←− Q .DEQUEUE() ;6
foreach (m 1, m 2 ) s .t . m 1, m 2 ∈ Child (mq ) do
7
Let L 1 = (m 1, M 1, E 1 ) and L 2 = (m 2, M 2, E 2 ) be two sub
layouts of L , whose roots are m 1 and m 2 ;8
if m 1 < m 2 and m 1 > m 2 then9
L 3 : (m 3, M 3, E 3 ) ←− MergeBlock(L 1, L 2 ) ;10
M ←− M \ (M 1 ∪ M 2 ) ∪ M 3 ;11
E ←− E \ (E 1 ∪ E 2 ) ∪ E 3 ;12
E ←− E \ {(mq , m 1 ), (mq , m 2 ) }∪{(mq , m 3 ) } ;13
L ←− UpdateLayout(L );14
return L ;
1

←
→>m
if m
2 thencreturn m 2 is inner block of m 1 ;return it is unknown

to construct a new memory layout L 3 by MergeBlock (Line 9). At
Lines 10-12, it replaces L 1 and L 2 with L 3 . Since the memory layout
is updated, we continue to update L by UpdateLayout (Line 13).
If sub-memory layouts of mq cannot be merged, it adds childrenof mq into Q (Lines 15-16) and continues to merge the children
iteratively. If there is no merging between any two sub memory
layouts, the algorithm terminates.
Example 3. Fig. 3 shows the process of merging two memory
layouts, which correspond to L 2 and L 3 in Fig. 2(c). We can infer thatm 1 (x 1 , 32, 16) and m 2 (0, 28, 16) are intersected, where 0 ≤ x 1 ≤ 12,←→ = 28. Based on Lines 1-3 in Algorithm 4, mm
1 = m2 = 16 and m
2
1
and m 2 are the alias memory blocks. Hence, they are merged asm =(0, 32, 16), and m 3 is added as the inner memory block of m .
3.4.4 Merging for Pointer Arithmetics. The pointer arithmetic generally yields a new pointer that still points the same memory allocation [4]. Multiple memory accesses by dereferencing these pointers
can lead to many memory layouts, which cannot be merged with
Algorithm 2 (because they are not intersected). However, thesememory layouts belong to the same memory allocation and shouldbe merged together. To improve the precision, we merge them
together as follows:m3(16,28,4)

m3(16,28,4)

Figure 3: Example to illustrate merging memory layouts.
Given such two memory layouts L 1 = (m 1 ,M 1 ,E 1 ) and L 2 =(m 2 ,M 2 ,E 2 ), they are merged into a new memory layout L 3 =(m 3 ,M 3 ,E 3 ), where m 3 = (min(m 1 ,m 2 ),max (m 1 ,m 2 ), 0), M 3 =M 1 ∪ M 2 ∪ {m 3 } and E 3 = E 1 ∪ E 2 ∪ {(m 3 ,m 1 ), (m 3 ,m 2 )}.
Example 4. In Fig. 2(b), Lines l 1 − l 3 are executed four times (inthe unrolled loop), and we recover four memory layouts, whichcannot be merged with Algorithm 2. Due to the pointer arithmetics,
these four memory layouts are then merged as L 1 in Fig. 2(c).

4LOCATING VULNERABILITIESIn this section, we introduce how to locate buffer overflow vulnerabilities by leveraging recovered memory layouts.

4.1

Locating Vulnerabilities

A buffer overflow occurs when dereferencing a pointer that goesout of the bounds of its pointed object. To locate the buffer overflow,
we collect a set of passed executions and a failed execution. With
the fine-grained memory layouts recovered in passed executions
as reference, the vulnerable memory layout in failed execution canbe identified by memory layout identification and comparison.
Note that the size of a memory block may not be fixed as we introduce the parameters in Algorithm 1 (i.e., x i at Line 1). To locate thebuffer overflow, we adopt a conservative strategy to determine theirvalues: let the size of the passed memory layout be the maximum
and the size of the failed memory layout be the minimum. Specifically, in a memory layout L = (m,M,E), the size of each memory
block mi ∈ M is: end − (base+ · · · + (x i−1 +index i−1 ∗scalei−1 ) +x i )Locating Vulnerabilities in Binaries via Memory Layout Recovering

ESEC/FSE ’19, August 26–30, 2019, Tallinn, Estonia

Algorithm 6: CompareLayout

4.2

input : memory layouts L 1 =(m 1 ,M 1 ,E 1 ) and L 2 =(m 2 ,M 2 ,E 2 )output : determining the buffer overflow

Passed executions may only cover partial program behaviors. Thus,
the passed memory layout may also be under-approximated. Locating vulnerabilities by comparing failed memory layout with underapproximated memory layout may introduce false positives. For
this problem, we reduce false positives based on two accompanying
phenomena: data corruption or abnormal memory address [19],which increase the confidence of our results.

Let Q 1 be an empty queue ;Q 1 .ENQUEUE(m 1 ) ;3 while Q 1 is not empty do
4m 1 ←− Q 1 .DEQUEUE() ;5
if m 1 == 0 then6
if m 1 < m 2 < m 1 or m 1 < m 2 < m 1 then7
return find buffer overflow
1
2

8
9
10
11
12
13
14
15
16
17

18
19
20

else
Let Q 2 be an empty queue ;Q 2 .ENQUEUE(m 2 ) ;while Q 2 is not empty dom 2 ←− Q 2 .DEQUEUE() ;if m 1 < m 2 < m 1 or m 1 < m 2 < m 1 thenif m 1 is alias or inner block of m 2 thenreturn find buffer overflow
foreach mc ∈ Child (m 2 ) do
Q 2 .ENQUEUE(mc ) ;foreach mc ∈ Child (m 1 ) do
Q 1 .ENQUEUE(mc ) ;return not find buffer overflow(c.f. Algorithm 1). For the passed memory layout, we make the sizeof each mi ∈ M maximum, i.e., (∀1 ≤ i < n : xi = 0) ∧ xn = offset.
For the failed memory layout, we make the size of each mi ∈M
minimum, i.e., x1 = offset ∧ (∀1 < i ≤ n : xi = 0).
Algorithm 6 shows how to locate the buffer overflow. It takes afailed memory layout L 1 and a passed memory layout L 2 as inputs.
Its intuition is as follows: for each memory block m 1 of L 1 , if m 1 isthe alias or inner memory block of some memory block m 2 of L 2 ,and m 1 is beyond m 2 , then it is a candidate buffer overflow.
At Line 5, it checks whether m
1 is zero. If so, it cannot determine
the relationship between m 1 and m 2 . Thus, it only compares m 1
with the root memory block m 2 of L 2 . If m 1 is beyond m 2 (Line 6),
there is a candidate buffer overflow in m 1 . At Line 9-17, it checks
m 1 with each memory block m 2 of L 2 . If m 1 is beyond m 2 (Line 13),
the algorithm checks the relationship between m 1 and m 2 . If m 1 isthe alias or inner memory block of m 2 (Line 14), there is a candidate
buffer overflow in m 1 .
Notice that, for the heap memory whose size is controlled by
inputs, its memory layout is not fixed with different inputs. Although we recover the maximum memory range after merging, it
still cannot be used to locate vulnerabilities. For example, in thestatement p = malloc (input ), if the maximum value of input inpassed test cases is 5, we recover a memory block whose size is 5
bytes (the maximum). If the value of input in the failed test case is10, we recover a memory block whose size is 10 bytes. Comparing
these two memory blocks introduces a false positive. In this case,we dynamically record the memory range of allocated memory, notto index and merge their memory layouts. To locate vulnerabilities, we check whether the used memory is beyond the allocatedmemory, which is the same as Valgrind Memcheck [3].

False Positive Reduction

4.2.1 Data Dependence Mismatch. Buffer overflow typically incurs
data corruption (overflowed by another data) [19]. Data corruption
can lead to data dependence mismatch, describing a data dependence that is not supposed to exist in the code. For example, inFig. 2(a), assume that the value of variable b is 4. The program
executes four times at Line 12. As a result, the value of variable
ptr → stu[a].func is corrupted by ptr → stu[a].name. At Line 14, it
uses ptr → stu[a].func. Thus, there is a data dependence between
Lines 12 and 14, which does not exist in the code. Hence, a data dependence mismatch occurs. To increase the confidence, we report abuffer overflow vulnerability only if it conducts a data dependencemismatch as well.
To obtain data dependence relations that do exist in the code, we
use dynamic analysis as in work [19, 20]. We execute a set of passed
test cases, and compute data dependence relations. Similarly, we
also compute the data dependence relations in the failed execution.
If a data dependence relation only occurs in failed execution but
not in any passed execution, there is a data dependence mismatch.
4.2.2 Abnormal Memory Address. When the buffer is overflowed
too much, it may reach an memory address that cannot be accessed(e.g., unallocated memory). This situation is considered as an abnormal memory address access. Usually, an abnormal memory accessdirectly leads to a program crash. Thus, if a buffer overflow leads
to an abnormal memory address access, it is a true buffer overflow.

5

EVALUATION

We have implemented a prototype tool for our approach, and evaluated its effectiveness. All the experiments are performed on the
32-bit Linux system with 3.5 GHz Intel Xeon E5 CPU and 8 GB
RAM. Since our memory addressing model is general, our approach
can be easily extended to 64-bit system.

5.1

Experiment Setup

We selected 25 binary programs from the benchmarks of DARPA’s
CGC [21], which is a competition to automatically detect vulnerabilities. Instead of contrived simple situations, they approximate
real vulnerabilities with enough complexities and diversities, ideal
for evaluating our approach [19]. However, not all programs are
selected because: 1) they run under DARPA DECREE, while our toolruns on the Linux system. Although the team TrailofBits has migrated them into Linux system, not all of them are reproducible [22];2) we only consider the buffer overflow, the programs with othertypes (e.g., null pointer dereference and use after free) are out of ourconsideration. In addition, we selected four binary programs objdump, readelf, ld and c++filt from binutils (about 690k LoC), which
are widely used in fuzzing system [10, 11], and one binary program
tiff2bw from libtiff (about 100k LoC). In these five programs, weESEC/FSE ’19, August 26–30, 2019, Tallinn, Estonia

H. Wang, X. Xie, S. Lin, Y. Lin, Y. Li, S. Qin, Y. Liu, T. Liu

Table 1: Experimental results on programs from DARPA’s Cyber Grand Challenge

Sample_Shipgame

Stack

ValveChecks

Stack

10

2

5,242

104,726

Bloomy_Sunday
The_Longest_Road
Thermal_Controller_v2

Stack
Stack
Stack

192
298
83

1
1
1

786,145
343,992
64,752642,941
344,668
66,291XStore

Stack

290

1

995,805

997,222

Casino_Games
Palindrom
CableGrind

Stack
Stack
Stack

603
61
818

2
1
1

192,211106,087
17,240182,209
5,262
18,336stack_vm

Heap

168

1

177,047

1,104,414

Street_map_service
humaninterface

Heap
Heap

630
533

1
1

1,121,017
509,169

714,785509,618

AIS-Lite

Heap

368

1

41,06933,904matrices_for_salecotton_swab_arithmetic
LMS

Heap
Heap
Heap

34
1065
147

1
1
1

170,680
2,192
26,7106,564
2,052
22,425

BudgIT

Heap

222

1

169,483

9,502

PKK_Steganography
ASCII_Content_Serveelectronictrading

Heap
Heap
Internal

184
277
90

1
1
2

182,333
1,377,145
595,381

114,543
489,714
10,800SCUBA_Dive_Logging

Internal699

2706,641

83,424

CGC_Planet_Mark_
Language_Parser

Internal583

6

999,709131,256

Square_Rabbit
TAINTEDLOVE
stream_vm

GlobalGlobalGlobal

593
52
136

1
1
1

2,917,848
201,339
101,184

837,835
100,849
100,145

Vulnerable
Memory Layout
No. Status
1 Under
1 Under
2 Complete
1 Complete
1 Under
1 Under
1 Under
2 Under
1 Under
1 Complete
1 Under
1 Under
2 Under
3 Complete
1 Complete
1 Complete
1 Under
2 Complete
1 Complete
1 Complete
1 Complete
1 Under
2 Complete
1 Complete
1 Complete
1 Under
1 Under
2 Under
3 Under
1 Under
2 Under
3 Under
4 Under
1 Complete
1 Under
1 Complete

Total
Avg.

4
–

8,756
350

34
1.4

11,831,264
473,251

6,665,987
266,639

36
–

Name

Passed Inputs

Type

Trace Length#Total620#Select
1#Passed20,843#Failed32,502

generated 453 program crashes, which constitute real-world benchmarks. The 25 CGC programs show the diversities of vulnerabilities,
and the 5 real-world programs show the scalability of our approach.

5.2

Experiment Design

In the experiments, we use the fuzzing system [7–11] to generate thepassed test cases and use the dynamic binary analysis framework
Pin [23] to collect the dynamic execution information. In general,
AFL generates a large number of passed test cases with different
code coverage. For efficiency, we select the passed test cases byadopting additional coverage strategy [24]. It selects the next passed
test case, which covers more codes that are covered by the failed
test case but not covered by already-selected passed test cases,
until vulnerabilities are located. Due to the lack of ground truthin our experiments, we manually validate the results. In total, we
manually check 478 program crashes in 30 programs and theirrecovered memory layouts.

5.3

Experimental Results

We evaluated the effectiveness of our approach in three aspects:
1) recovering memory layouts, 2) locating vulnerabilities, and 3)
triaging program crashes.

15+21
–

Buffer Overflow

Plus Accompanying

Time(s)

#Ins
2
1
1
2
3
5
1
3
1
6
1
1
1
1
3
1
3
2
1
1
2
2
2
1
1
2
3
2
1
3
5
3
6
1
1
1

Root

×




×




×




×




×




×
×

×
×
×
×




Mismatch/Abnormal
M
–
M+A
M+A
M+A
M
–
M+A
M+A
M
M+A
–
A
M
M
M
–
M
A
A
M
–
A
A
A
M
–
–
M
–
–
–
–
A
A
A

#Ins
1
0
1
1
1
3
0
1
1
4
1
0
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
0
1
0
0
0
0
1
1
1

Root

–




–




–




–




–




–
–

–
–
–
–




Select
349

76
3.04

25+11
–

25+11
–

30
1.2

25+0
–

Locate
50

6

51

119
168
52

147
110
104

163

387

390
31
432

143
48
46

95

378

468
279

240
244

203

47

18
544
81

54
37
58

123

72

102
174
49

178
551
186

477

303

612

1,432

484
29
67

605
73
76

5,515
221

5,620
225

5.3.1 Recovering Memory Layout. Table 1 shows the experimental
results on recovering memory layouts. Column Name lists the program names. In column Passed Inputs, the heading #Total lists thetotal number of generated passed test cases, and #Select shows thenumber of selected passed test cases. The details of generation/selection of passed test cases can refer to Section 5.2. Column Trace
Length lists the number of instructions in the execution, where#Passed and #Failed represent the average numbers of instructions
in selected passed executions and failed execution, respectively.
Since a program may contain more than one vulnerable memory
layout, in column Vulnerable Memory Layout, the heading No. lists
each of them. For example, there are three vulnerable memory
layouts in the program stack_vm.
The heading Status shows the status of recovered passed memory layout, which is used for comparison to identify the vulnerable
memory layout. It indicates whether the passed memory layout represents the hierarchical structure of variables, where Under meansthat we under-approximately recover the memory layout, and Complete means that we recover its complete memory layouts. Noticethat we got a large number of passed memory layouts recovered inpassed executions. We manually check and report only 36 of them(column Status) because: 1) the number of recovered memory layouts is too large to manually check all; 2) these 36 memory layouts

Locating Vulnerabilities in Binaries via Memory Layout Recovering

are compared to identify vulnerable memory layouts and we needto check its status (under-approximated or complete).
Summary. Among the reported 36 passed memory layouts, 15
memory layouts are completely recovered (i.e., the recovered static
hierarchical data structures for variables are the same with theirstatic hierarchical data structures in source code) and 21 are underapproximately recovered (e.g., some internal data structures of variables are not recovered). Memory layouts are under-approximately
recovered because some elements of array or members of data
structure are not accessed in the executions. That is, our approachachieves 100 % success rate to recover memory layouts that arecovered in the executions. Despite the under-approximate memory layout recovery, they are still useful to locate buffer overflow
vulnerabilities, which is shown in the following experiments.

5.3.2 Locating Vulnerabilities. Table 1 also shows the results oflocating buffer overflow vulnerabilities. There are multiple types ofbuffer overflow vulnerabilities in the programs, as shown in column
Type. The symbols Stack, Heap, Global represent stack, heap, andglobal buffer overflow, respectively. In addition, we consider anotherspecial type of buffer overflow: overflow within a data structure, as
indicated by Internal. In binary code, Valgrind Memcheck [3] cannot
locate buffer overflows within stack, global memory regions, anddata structures [1]. Valgrind’s extension SGCheck tries to locate
stack buffer overflows, however, it still needs debug information.
Even in source code, AddressSanitizer [1] cannot detect the buffer
overflow within the data structures as well.
Column Buffer Overflow shows whether the vulnerable memory
layouts are the root causes of crash. Since one vulnerable memory
layout may be overflowed at different instructions, the heading #Ins
represents the number of instructions producing buffer overflows invulnerable memory layouts. The heading Root shows whether it isa real buffer overflow. Our approach may report false positives. To
reduce them, we adopt two strategies: data dependence mismatch(denoted by M) and abnormal memory address (denoted by A) inthe column Plus Accompanying.
After our investigation, we found that the false positives are
generated in two cases: (1) Some instructions do lead to the buffer
overflow, but do not lead to the crash. For example, in the program Sample_Shipgame, there are 2 instructions leading to a buffer
overflow. However, one is assigned with ‘\0’, and it is not the root
cause of crash. This can be eliminated by our strategies, and thus
the number of instructions is reduced from 2 (#Ins in Buffer Overflow) to 1 (#Ins in Plus Accompanying). (2) Some instructions indeed
do not produce the buffer overflow. For example, in the program
CGC_Planet_Mark_Language_Parser, all the false positives are reduced (#Ins in Plus Accompanying).
Since our approach requires passed and failed executions, its
effectiveness depends on the test cases. For example, in program
CGC_Planet_Markup_Language_Parser, our approach fails to locate buffer overflow vulnerabilities. This is because the program
contains many special checks in the markup language parser, andAFL does not generate passed test cases to cover the data structure
overflowed (i.e., struct City). Since our approach does not recover
the memory layout of struct City in passed executions, we fails to
locate its buffer overflow in failed execution.

ESEC/FSE ’19, August 26–30, 2019, Tallinn, Estonia

Table 2: Triage Program Crash on five real-world programsNameobjdump-2.26
readelf-2.28
ld-2.24
c++filt-2.26
tiff2bw-3.9.7

Test Cases#passed #failed
1,475
73
1,780
119
1,274
117
1,861
23
1,846
121

Trace Length#Passed#Failed166,802
235,657
162,662
68,0881,504,274 1,334,977
17,7084567
1,131,200 1,102,423

AFL

Our Approach

59
69
90
18
84

4 (61, 8, 3, 1)
3 (102, 15, 2)
6 (45, 28, 12, 12, 3, 1)
3 (21, 1, 1)
3 (111, 6, 4)

Column Time shows the time overhead. The heading Select shows
the time for selecting passed test cases, while Locate for locating
buffer overflow vulnerabilities (including recovering memory layouts, computing data dependencies, and locating vulnerabilities).
Summary. Our experimental programs include 4 types of vulnerabilities (Column Type): 9 stack buffer overflows, 10 heap buffer
overflows, 3 internal data structure overflows, 3 global memory
buffer overflows, which show the diversity of vulnerabilities. For
each vulnerable memory layout, we locate 3.04 instructions on
average. In the beginning, we reports 25 true positives and 11 false
positives (Root in Buffer Overflow). After applying the proposed
elimination strategies, 25 errors are confirmed, and all of 11 false
positives are eliminated (Root in Plus Accompanying). The averagetime for selecting passed test cases and locating vulnerabilities are
221 and 225 seconds. The results show that our approach is effective
to locate buffer overflow vulnerabilities.
5.3.3 Triage Program Crashes. As described in Section 1, triaging
program crashes is very important in the program analysis and debugging. In the experiments, we use the fuzzing system to generate
a number of program crashes, many of which are caused by thesame vulnerability but AFL is not able to distinguish them. Our
approach can help to triage program crashes based on the root
causes of vulnerabilities.
Since multiple instructions may lead to the same vulnerable
memory layout (e.g., #Ins in Buffer Overflow), we decided to use
a more coarse-grained granularity, i.e., we use functions where
blamed instructions reside as blamed functions. Thus, in our experiment, we identify the root causes based on vulnerable memory
layouts and blamed functions [6].
Table 2 shows the results of five real-world programs with total
453 program crashes. Column Name shows the program name.
Column Test Cases lists the number of test cases, where #Passed
and #Failed represent the number of passed and failed test cases,
respectively. Column Trace Length lists the average number of
instructions in the execution. The last two columns show the resultsof triaging program crashes.
Summary. Column AFL lists the number of unique programcrashes triaged by AFL. Column Our Approach shows triaging results of our approach, where the first number is the number ofgroups, and the numbers in the brackets represent the numberof crashes in each group. For example, 4(61, 8, 3, 1) represents 73
crashes are classified into 4 groups, which include 61, 8, 3 and 1
crashes, respectively. We manually check the crashes for all groups
and confirm that our triaging results are correct. Compared to AFL,
our approach helps to reduce the number of unique program crashes
significantly. Thus, it can save manual resources for analyzing them.
There are 16 crashes that are not grouped in program ld-2.24, as
our approach fails to locate their vulnerabilities. We look closely

ESEC/FSE ’19, August 26–30, 2019, Tallinn, Estonia

into this program, and these 16 crashes are due to the null pointerdereference, which is out of the scope of this work.

5.4

Threats to Validity

If the passed executions do not cover the root causes, our approachcannot recover their memory layouts and fails to locate vulnerabilities. As the alternative solutions, the existing test suite [25–28],
symbolic execution [29–37], and other test case generation techniques can also be used in our approach to obtain high-quality test
cases. Since our approach is not to pursue high code coverage, thesetechniques are orthogonal to our approach.
The passed test cases may only access partial elements of a variable (e.g., array and struct), and thus the recovered memory layouts
are under-approximated. In this case, our approach may produce
false positives in locating buffer overflow vulnerabilities. For thisissue, we propose two conservative strategies (c.f.Section 4.2) toeliminate false positives. The evaluation results show that our reduction strategies are effective.

6 RELATED WORK
6.1 Reverse Engineering
Reverse engineering of data structures is an active area in binary
code analysis [38–42]. Thomas and Gogul [12] also proposed an
approach to recover memory ranges of variables in binary code. Its
main difference from ours is that they recover memory information
using static analysis (value-set analysis), while we use dynamic
execution information. Our results are under-approximated andtheirs are over-approximated. Our under-approximated memory
layout introduces less false negatives and false positives in locating
buffer overflow vulnerabilities. Built on the work [12], Brumley etal. developed TIE [13], which recovers the memory informationof data structures and their types. TIE has the same limitations aswork [12] when used for locating buffer overflow vulnerabilities.
Lin et al. proposed Rewards [14], the reverse engineering ofdata structures using dynamic analysis. It infers the types of data
structures based on arguments of well-known functions, and werecover memory layouts based on the memory addressing model.
Hence, Rewards only recovers a small portion of data structures [15],and our approach is more general for data structures.
Slowinska et al. developed Howard [15, 16], which is the closest
work to ours. However, there are still two main differences. The firstis that Howard may miss internal layouts of data structures in somecases. Howard [15] only records a base pointer for each memory
access. It may miss the internal layouts in the case where memory
address is computed based on multiple base addresses. Take thememory access at Line 12 in Fig 2 for example, Howard considers its
base pointer is ptr. However, its memory address is computed basedon ptr, stu and name. Hence, Howard misses the internal layouts.
The second difference is that Howard detects arrays which areaccessed in loops while our approach can recover arrays generally
based on the memory addressing model. Thus, our approach ismore general to recover the fine-grained layouts of data structures.
In addition, some loop analysis and summarization techniques [43–45] can be further applied to improve the memory layout recovery
on the variables inside the loop.

H. Wang, X. Xie, S. Lin, Y. Lin, Y. Li, S. Qin, Y. Liu, T. Liu

6.2

Locating Vulnerabilities

Source code analysis. There has been lots of work aiming at locating vulnerabilities in source code (e.g.,[46–49]). AddressSanitizer [1]is a widely used tool in practice. It instruments a program, inserts
undefined memory (i.e., redzones) between the objects and detects
an access to the undefined memory. DieHard [46] and its successor
DieHarder [47] populate newly allocated memory and freed memory with magic values. They also add redzones around the allocatedmemory region to detect the spatial errors. The tools SoftBound [2],
CETS [4] and LowFat [48, 49] keep track of per-pointer capability
and checks capability when accessing an object.
Although these techniques can also locate buffer overflows, they
are applicable to different scenarios (i.e., source code vs. binarycode). Since the source code is not always available, our approach
is applicable to more scenarios. In addition, some source code based
techniques do not recognize the internal structures of data structures, such as AddressSanitizer. Hence, they cannot locate internal
overflow within a data structure. Since our approach recovers finegrained memory layouts of variables, this is not an issue anymore.
Binary code analysis. Locating vulnerabilities in binary code
has also been widely studied [50–55]. Valgrind Memchecks [3]uses the valid value bit and address bit in shadow memory to capture reading undefined memory and out-of-bounds access. Besides,
Valgrind’s extension SGCheck also wants to locate stack buffer
overflows, however, it still needs the help of debug information. Dr.
Memory [52] is similar to Valgrind Memchecks in many ways. It isfurther equipped with a multi-threaded binary translation system.
Purify [53] shadows every byte of memory with a two-bit value that
encodes one of three states: unaddressable, writable, and readable.
These techniques locate heap buffer overflow without false positives, which is achieved by our approach as well. Due to the lackof program semantics in binary code, it is very difficult to identify
the boundaries of variables in stack and global memory regions.
Thus, none of these techniques can locate buffer overflow within
the stack and global memory regions [1].

7

CONCLUSION

In this work, we propose an approach to locate buffer overflows inbinaries. We first recover the memory layouts based on memory
addressing model together with dynamic execution information.
The recovered memory layouts actually represent the hierarchicalstructure of variables in source code. Then, based on recovered
memory layouts we locate buffer overflows. In future, we would
like to further apply the memory layout recovery on more applications, e.g., use after free, diagnose the bottleneck of memory
consumption.

ACKNOWLEDGMENT
This research was supported (in part) by Natural Science Foundation of China (Grant No. 61772347, 61632015, 61772408, U1766215,
61833015), the National Research Foundation, Prime Ministers Office, Singapore under its National Cybersecurity R&D Program(Award No. NRF2018NCR-NCR005-0001), National Satellite of Excellence in Trustworthy Software System (Award No. NRF2018NCRNSOE003-0001) administered bythe National Cybersecurity R&D
Directorate.

Locating Vulnerabilities in Binaries via Memory Layout Recovering

REFERENCES[1] K. Serebryany, D. Bruening, A. Potapenko, and D. Vyukov, “Addresssanitizer: A
fast address sanity checker.” in USENIX Annual Technical Conference, 2012, pp.
309–318.
[2] S. Nagarakatte, J. Zhao, M. M. Martin, and S. Zdancewic, “Softbound: Highly
compatible and complete spatial memory safety for c,” ACM Sigplan Notices,
vol. 44, no. 6, pp. 245–258, 2009.
[3] N. Nethercote and J. Seward, “Valgrind: a framework for heavyweight dynamic
binary instrumentation,” in ACM Sigplan notices, vol. 42, no. 6. ACM, 2007, pp.
89–100.
[4] S. Nagarakatte, J. Zhao, M. M. Martin, and S. Zdancewic, “Cets: compiler enforced
temporal safety for c,” in ACM Sigplan Notices, vol. 45, no. 8. ACM, 2010, pp.
31–40.
[5] X. Meng and B. P. Miller, “Binary code is not easy,” in Proceedings of the 25th
International Symposium on Software Testing and Analysis. ACM, 2016, pp.
24–35.
[6] W. Cui, M. Peinado, S. K. Cha, Y. Fratantonio, and V. P. Kemerlis, “Retracer:
Triaging crashes by reverse execution from partial memory dumps,” in Proceedingsof the 38th International Conference on Software Engineering. ACM, 2016, pp.
820–831.
[7] AFL, “American fuzzy lop. http://lcamtuf.coredump.cx/afl/.”[8] C. Lemieux, R. Padhye, K. Sen, and D. Song, “Perffuzz: automatically generating pathological inputs,” in Proceedings of the 27th ACM SIGSOFT International
Symposium on Software Testing and Analysis. ACM, 2018, pp. 254–265.
[9] C. Lemieux and K. Sen, “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, 2018, pp. 475–485.
[10] M. Böhme, V.-T. Pham, M.-D. Nguyen, and A. Roychoudhury, “Directed greybox
fuzzing,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer andCommunications Security. ACM, 2017, pp. 2329–2344.
[11] M. Böhme, V.-T. Pham, and A. Roychoudhury, “Coverage-based greybox fuzzing
as markov chain,” in Proceedings of the 2016 ACM SIGSAC Conference on Computerand Communications Security. ACM, 2016, pp. 1032–1043.
[12] G. Balakrishnan and T. Reps, “Analyzing memory accesses in x86 executables,”in International conference on compiler construction. Springer, 2004, pp. 5–23.
[13] J. Lee, T. Avgerinos, and D. Brumley, “Tie: Principled reverse engineering of types
in binary programs,” 2011.
[14] Z. Lin, X. Zhang, and D. Xu, “Automatic reverse engineering of data structuresfrom binary execution,” in Proceedings of the 11th Annual Information Security
Symposium. CERIAS-Purdue University, 2010, p. 5.
[15] A. Slowinska, T. Stancescu, and H. Bos, “Howard: A dynamic excavator for reverse
engineering data structures.” in Proceedings of the Network and Distributed System
Security Symposium , year=2011, organization=Citeseer.
[16] ——, “Body armor for binaries: Preventing buffer overflows without recompilation.” in USENIX Annual Technical Conference, 2012, pp. 125–137.
[17] J. Devietti, C. Blundell, M. M. Martin, and S. Zdancewic, “Hardbound: architectural support for spatial safety of the c programming language,” ACM SIGARCH
Computer Architecture News, vol. 36, no. 1, pp. 103–114, 2008.
[18] W. N. Sumner and X. Zhang, “Memory indexing: canonicalizing addresses acrossexecutions,” in Proceedings of the eighteenth ACM SIGSOFT international symposium on Foundations of software engineering. ACM, 2010, pp. 217–226.
[19] Y. Chen, M. Khandaker, and Z. Wang, “Pinpointing vulnerabilities,” in Proceedingsof the 2017 ACM on Asia Conference on Computer and Communications Security.
ACM, 2017, pp. 334–345.
[20] H. Wang, T. Liu, X. Guan, C. Shen, Q. Zheng, and Z. Yang, “Dependence guided
symbolic execution,” IEEE Transactions on Software Engineering, vol. 43, no. 3, pp.
252–271, 2016.
[21] DARPA,“Cybergrandchallenge
repository.
https://github.com/cybergrandchallenge/.”[22] Y. Li, B. Chen, M. Chandramohan, S.-W. Lin, Y. Liu, and A. Tiu, “Steelix: programstate based binary fuzzing,” in Proceedings of the 2017 11th Joint Meeting on
Foundations of Software Engineering. ACM, 2017, pp. 627–637.
[23] C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J.
Reddi, and K. Hazelwood, “Pin: building customized program analysis tools withdynamic instrumentation,” in Acm sigplan notices, vol. 40, no. 6. ACM, 2005, pp.
190–200.
[24] Y. Lu, Y. Lou, S. Cheng, L. Zhang, D. Hao, Y. Zhou, and L. Zhang, “How does
regression test prioritization perform in real-world software evolution?” in 2016
IEEE/ACM 38th International Conference on Software Engineering. IEEE, 2016,
pp. 535–546.
[25] D. Hao, L. Zhang, L. Zang, Y. Wang, X. Wu, and T. Xie, “To be optimal or not in
test-case prioritization,” IEEE Transactions on Software Engineering, vol. 42, no. 5,
pp. 490–505, 2016.
[26] L. Zhang, D. Hao, L. Zhang, G. Rothermel, and H. Mei, “Bridging the gap between
the total and additional test-case prioritization strategies,” in Proceedings of the2013 International Conference on Software Engineering. IEEE Press, 2013, pp.
192–201.

ESEC/FSE ’19, August 26–30, 2019, Tallinn, Estonia[27] S. A. Khalek and S. Khurshid, “Efficiently running test suites using abstract undo
operations,” in 2011 IEEE 22nd International Symposium on Software Reliability
Engineering. IEEE, 2011, pp. 110–119.
[28] W. Masri and F. A. Zaraket, “Coverage-based software testing: Beyond basic test
requirements,” in Advances in Computers. Elsevier, 2016, vol. 103, pp. 79–142.
[29] A. Filieri, C. S. Păsăreanu, and W. Visser, “Reliability analysis in symbolic
pathfinder,” in 2013 35th International Conference on Software Engineering. IEEE,
2013, pp. 622–631.
[30] S. Person, G. Yang, N. Rungta, and S. Khurshid, “Directed incremental symbolic
execution,” in Acm Sigplan Notices, vol. 46, no. 6. ACM, 2011, pp. 504–515.
[31] J. H. Siddiqui and S. Khurshid, “Staged symbolic execution,” in Proceedings of the27th Annual ACM Symposium on Applied Computing. ACM, 2012, pp. 1339–1346.
[32] Y. Li, Z. Su, L. Wang, and X. Li, “Steering symbolic execution to less traveled
paths,” in ACM SigPlan Notices, vol. 48, no. 10. ACM, 2013, pp. 19–32.
[33] T. Xie, N. Tillmann, J. de Halleux, and W. Schulte, “Fitness-guided path exploration in dynamic symbolic execution,” in IEEE/IFIP International Conference on
Dependable Systems & Networks. Citeseer, 2009, pp. 359–368.
[34] B. C. Parrino, J. P. Galeotti, D. Garbervetsky, and M. F. Frias, “Tacoflow: optimizing
sat program verification using dataflow analysis,” Software & Systems Modeling,
vol. 14, no. 1, pp. 45–63, 2015.
[35] C. Cadar, D. Dunbar, D. R. Engler et al., “Klee: Unassisted and automatic generationof high-coverage tests for complex systems programs.” in USENIX Symposium on
Operating Systems Design and Implementation, vol. 8, 2008, pp. 209–224.
[36] W. Visser, C. S. Pasareanu, and S. Khurshid, “Test input generation with java
pathfinder,” ACM SIGSOFT Software Engineering Notes, vol. 29, no. 4, pp. 97–107,
2004.
[37] S. Anand, C. S. Păsăreanu, and W. Visser, “Jpf–se: A symbolic execution extension
to java pathfinder,” in International Conference on Tools and Algorithms for theConstruction and Analysis of Systems. Springer, 2007, pp. 134–138.
[38] G. Balakrishnan and T. Reps, “Divine: Discovering variables in executables,” inInternational Workshop on Verification, Model Checking, and Abstract Interpretation.
Springer, 2007, pp. 1–28.
[39] A. Cozzie, F. Stratton, H. Xue, and S. T. King, “Digging for data structures.” in
USENIX Symposium on Operating Systems Design and Implementation, vol. 8, 2008,
pp. 255–266.
[40] E. Dolgova and A. Chernov, “Automatic reconstruction of data types in thedecompilation problem,” Programming and Computer Software, vol. 35, no. 2, pp.
105–119, 2009.
[41] X. Chen, A. Slowinska, D. Andriesse, H. Bos, and C. Giuffrida, “Stackarmor:
Comprehensive protection from stack-based memory error vulnerabilities forbinaries.” in Proceedings of the Network and Distributed System Security Symposium.
Citeseer, 2015.
[42] V. Braberman, D. Garbervetsky, S. Hym, and S. Yovine, “Summary-based inferenceof quantitative bounds of live heap objects,” Science of Computer Programming,
vol. 92, pp. 56–84, 2014.
[43] X. Xie, B. Chen, Y. Liu, W. Le, and X. Li, “Proteus: computing disjunctive loopsummary via path dependency analysis,” in Proceedings of the 2016 24th ACM
SIGSOFT International Symposium on Foundations of Software Engineering. ACM,
2016, pp. 61–72.
[44] X. Xie, B. Chen, L. Zou, Y. Liu, W. Le, and X. Li, “Automatic loop summarization
via path dependency analysis,” IEEE Transactions on Software Engineering, 2018.
[45] X. Xie, Y. Liu, W. Le, X. Li, and H. Chen, “S-looper: Automatic summarization for
multipath string loops,” in Proceedings of the 2015 International Symposium on
Software Testing and Analysis. ACM, 2015, pp. 188–198.
[46] E. D. Berger and B. G. Zorn, “Diehard: probabilistic memory safety for unsafe
languages,” in Acm sigplan notices, vol. 41, no. 6. ACM, 2006, pp. 158–168.
[47] G. Novark and E. D. Berger, “Dieharder: securing the heap,” in Proceedings of the
17th ACM conference on Computer and communications security. ACM, 2010, pp.
573–584.
[48] G. J. Duck and R. H. Yap, “Heap bounds protection with low fat pointers,” inProceedings of the 25th International Conference on Compiler Construction. ACM,
2016, pp. 132–142.
[49] G. J. Duck, R. H. Yap, and L. Cavallaro, “Stack bounds protection with low fat
pointers,” in Symposium on Network and Distributed System Security, 2017.
[50] D. Andriesse, X. Chen, V. van der Veen, A. Slowinska, and H. Bos, “An in-depth
analysis of disassembly on full-scale x86/x64 binaries.” in USENIX Security Symposium, 2016, pp. 583–600.
[51] F. Peng, Z. Deng, X. Zhang, D. Xu, Z. Lin, and Z. Su, “X-force: Force-executing
binary programs for security applications.” in USENIX Security Symposium, 2014,
pp. 829–844.
[52] D. Bruening and Q. Zhao, “Practical memory checking with dr. memory,” in Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation
and Optimization. IEEE Computer Society, 2011, pp. 213–223.
[53] R. Hastings and B. Joyce, “Purify: Fast detection of memory leaks and accesserrors,” in Proceedings of the 1992 USENIX Conference. Citeseer, 1991.
[54] Intel, “Intel inspector. https://software.intel.com/en-us/intel-inspector-xe/.”[55] Oracle,“Sunmemoryerror
discoverytool.
https://docs.oracle.com/cd/e18659_01/html/821-1784/gentextid-302.html.”