A practical analysis of ROP attacks

UGP Report

Author: Ayush Bansal (Student ID: 160177)
Advisor: Dr. Debadatta Mishra

Department of Computer Science and Engineering
Indian Institute of Technology, Kanpur

April 27, 2019

## Abstract

Control Flow Hijacking attacks have posed a serious threat to the security of
applications for a long time where an attacker can damage the control Flow
Integrity of the program and execute arbitrary code. These attacks can be
performed by injecting code in the program’s memory or reusing already
existing code in the program (also known as Code-Reuse Attacks). Code-Reuse
Attacks in the form of Return-into-libc Attacks or Return-Oriented Programming
Attacks are said to be Turing Complete, providing a guarantee that there will
always exist code segments (also called ROP gadgets) within a binary allowing
an attacker to perform any kind of function by building a suitable ROP chain
(chain of ROP gadgets).

Our goal is to study different techniques of performing ROP Attacks and find
the difficulties encountered to perform such attacks. For this purpose, we
have designed an automated tool which works on 64-bit systems and generates a
ROP chain from ROP gadgets to execute arbitrary system calls.

###### Contents

  1. 1 Introduction
  2. 2 Background
    1. 2.1 Performing a Control Flow Hijacking Attack
    2. 2.2 Mitigations
    3. 2.3 The x86_64 Architecture
      1. 2.3.1 Registers
      2. 2.3.2 Memory Management
      3. 2.3.3 Function Calls
  3. 3 Design
    1. 3.1 Inputs
    2. 3.2 Important points in algorithm
    3. 3.3 Algorithm
      1. 3.3.1 Retrieval of Gadgets
      2. 3.3.2 Transformation of Gadgets
      3. 3.3.3 Construction of ROP chain
  4. 4 Evaluation
  5. 5 Related Work
  6. 6 Conclusion/Future Work

##  1 Introduction

Security community has faced the problem of malicious code execution for a
long time. The attacker gaining access can steal sensitive data or hijack an
application’s execution. Although, the attacker needs to divert the
application’s control flow to execute a code of his choosing. If the attacker
is successful, the program can be used for arbitrary purposes, such as
attacking other systems or applications.

A problem which persists while preventing these attacks is, one cannot
accurately predict whether a particular execution will be benign or not. For a
long time, people have concentrated on preventing the introduction and
execution of new malicious code. The techniques used for preventing these
attacks roughly fall into two categories, attempting to guarantee the control
flow integrity in existing programs (e.g., type-safe languages, stack cookies,
XFI [UE06]), and attempting to isolate malicious code that has been introduced
into the system (e.g. W$\oplus$X, memory tainting). The execution of injected
code can be prevented using W$\oplus$X (Writable/Executable) or DEP (Data
Execution Prevention) [SA04]

Our discussion will be on a category of control flow hijacking attacks which
do not require any code injection by the attacker, yet can induce arbitrary
behaviour in the targeted system, namely Code-Reuse attacks. In said attacks,
fragments of existing code present in the program’s address space (gadgets)
are linked together to perform malicious execution. Since the code being
executed is in the executable (code) region of the program’s address space,
DEP or other techniques will no longer be viable. Aforementioned gadgets can
be put together in an order resulting in consecutive execution to perform an
arbitrary function.

Many techniques have been introduced that allow putting gadgets together
resulting in consecutive execution. The most widespread one is called Return-
Oriented Programming (ROP) [RR12], [Sha07a]. Another one is called Jump-
Oriented Programming (JOP) [TB11], [SC10], [JWM12], which not used popularly
as it is difficult to facilitate a deeper comprehension of code-reuse-attacks
using this technique. ROP makes use of code snippets which end in a ret
instruction which is just like a pop rip instruction.

Many tools are available for finding ROP gadgets in an executable file, our
tool retrieves gadgets using ROPgadget tool by Jonathan Salwan [Sal11]. This
tool retrieves ROP gadgets upto an arbitrary maximum depth from an executable.
The gadgets thus obtained can be chained together to perform arbitrary
computation.

Research done in this area during the last decade and more has suggested that
ROP is Turing Complete [RR12], [Sha07a], i.e. it is in theory possible to use
ROP gadgets to construct any arbitrary program. In fact, ROP has been shown to
be Turing Complete on several platforms [Kor09], [RR12], [Sha07a]. This
statement implies that any shellcode an attacker wants to execute in a regular
code injection attack, he/she can also create using ROP, thus bypassing DEP
and making ROP extremely dangerous.

Creating a program using ROP is, however, complex, cumbersome, and requires a
lot of manual labour and attention to detail. In regard of this problem, we
have designed a tool to analyze the binary input file and create a suitable
ROP chain, thus automating the process of program creation using ROP.

During the course of our discussion, we pick a system architecture. We work
with binaries on x86_64 architecture - specifically, the Standard C Library on
Linux 64-bit systems. The reasons behind this choice are:

  * •

It is one of the most widely used architecture in current computer systems.

  * •

The x86_64 architecture uses registers for parameters during system call and
function call sequences, this makes finding a suitable ROP gadget chain more
challenging.

We infer from our experience that any sufficiently large body of executable
code on any architecture and operating system will feature sequences that
allow the construction of similar gadgets.

Our goals regarding this analysis are:

  1. 1.

Identify the issues, encountered while creating a program using ROP, which
make it complex and cumbersome to work with. Later work on solutions of these
issues.

  2. 2.

Since ROP attacks are said to be Turing Complete, we want to automate the
process of generating a program using ROP.

  3. 3.

Verify the Turing Completeness property of Return-Oriented programming.

Our contributions:

  * •

Designed an efficient scheme for transforming gadgets into a sequence of
simple equations.

  * •

Designed an algorithm to output a permutation of ROP gadgets executing an
arbitrary program.

  * •

Extended the functionality of the ROPgadget tool to produce a ROP chain along
with the list of gadgets.

##  2 Background

In this section, our discussion will be on ways of performing a control flow
hijacking attack, then we will move on to implications of Return-Oriented
programming on DEP and present day systems. Lastly, we will discuss the x86_64
architecture.

###  2.1 Performing a Control Flow Hijacking Attack

Consider an attacker who has discovered a vulnerability in an application and
wants to exploit it. Exploitation, here, means subverting the application’s
control flow so that the application performs attacker-directed actions with
its permissions or credentials. One of the most famous such vulnerability
class is the stack bufferoverflow [One96], other famous classes of such type
are buffer overflows on the heap i.e. heap overflow [Des00], [Ano01], [Kae01],
integer overflows [Zal01], [Hor02], [Ble02], and format string vulnerabilities
[ST01], [GR01].

To complete the objective, the attacker must (1) subvert the program’s control
flow from its original course, and (2) redirect the program’s execution to the
code of his/her choosing. To complete task (1), attacker can perform the
traditional stack-smashing attack (e.g. stack buffer overflow) and overwrite
the return address of the function on the stack, so it points to code of
his/her choosing rather than to the caller function. Here, other techniques
may also be used such as frame-pointer overwriting [Klo99]. The attacker can
complete task (2) by injecting code into the program’s memory; the modified
return address should be pointed to this code. Usually the injected code is
shellcode, whether or not it spawns a shell.

We will restrict our attention to the second task mentioned above. This task
is becomes difficult by modifying the memory layout of the program by making
the stack non-executable, thus preventing code injection by stack-smashing
attacks. Even more better and complete defense (W$\oplus$X) ensures that no
memory location in a program is marked both writable (W) and executable (X)
[Tea03b]. Due to code injection defenses, attackers moved on to reusing code
already present in the exectuable (code) region of program’s memory. Thus, in
principle any available code, either from the program’s text segment or from a
library to which it linked could be used. However, The standard C library
(libc) was the usual target since it contained almost every UNIX program
necessary, these attacks were thus named Return-into-libc attacks. The
attacker can cause a series of functions to be invoked, one after the other by
carefully setting up the stack.

Generalizing Return-into-libc attacks, Return-oriented programming technique
was used to allow arbitrary (Turing complete) computation [RR12], without
calling any functions explicitly.

###  2.2 Mitigations

We briefly discuss mitigations against memory error exploitation and their
effects on Return-Oriented programming. Stack-Guard [CC98] and ProPolice
[HE01] are some of the techniques which prevent traditional stack-smashing
attacks: preventing subversion of a program’s control flow with typical buffer
overflows on the stack, these defenses are good but there are known
circumvention methods [BK00]. Bounds Checking [PA09] is also a good mitigation
technique which fights the problem of memory corruption at its root and tries
to prevent buffer overflows. However, stack smashing is not necessary for
performing a Return-oriented attack.

Address-space layout randomization (ASLR) [Tea03a] is another relevant and
widely used mitigation technique. Any attack which requires the knowledge of
addresses in the program’s memory space is defeated by ASLR-except for brute
force search [HS04], partial address overwrites [Dur02], and information
disclosure [Bla10]. This mitigation technique applies to both code injection
and code reuse attacks equally well. Assuming effective ASLR, the presence or
absence of DEP is irrelevant.

Shadow Stack [THD15] is another mitigation technique to ensure correct
execution of the program. The concept used is to have an area of memory where
backup copies of all return addresses are stored, upon returning from a
function, the return address stored on the stack is compared to the one on top
of the shadow stack (should be identical in case of correct program
execution). Using a shadow stack battles ROP attacks, because attacker would
have to overwrite both the return addresses on the stack and the one on the
shadow stack (typically protected). A problem which persists with this
technique is that it only protects return addresses, hence does not provide
protection against JOP attacks. Intel’s Control-flow Enforcement Technology
(CET) [Int16a] is an example of this.

Finally, control-flow integrity [UE06], [MA09] systems can provably prevent a
program’s control-flow from being hijacked. They classify indirect control-
flow instructions and indirect control-flow targets into groups and enforce
policies so indirect call-sites match the possible targets. This drastically
reduces the number of available gadgets but still there are many attacks which
can be bypassed.

###  2.3 The x86_64 Architecture

We will introduce basics of the x86_64 architecture [Int16b] to aid us later
in our discussion We will cover registers, management of stack and heap and
function calls. x86_64 instructions are of variable size (depending on the
instruction) which can be useful in performing ROP attacks.

####  2.3.1 Registers

Registers are used to perform faster computation, x86_64 has 16 general
purpose registers each of which is 64 bit long, but it is possible to use
lower 32 or 16 bits, lower/higher 8 bits of a register. Using lower bits only
of a register also decreases the size of the instruction it is used in, such
as using lower 32 bits instead of 64 bits can reduce the size of x86_64
instruction by 2 bytes. The set of general purpose registers is as follows:

Registers rip, namely program counter and rflags, namely collection of flags
are special registers in x86_64 and are responsible for program-flow and
storing information about results of previous operations respectively.

####  2.3.2 Memory Management

Memory can be allocated statically using the stack, it is very fast and
handled automatically, but space is limited; or can be allocated dynamically
using heap, it is slightly slower than static memory allocation, but has no
limits on size, though the programmer has to manage memory.

Stack is a small area of memory used by functions to temporarily store
information, local variables etc. Two registers namely rsp (stack pointer) and
rbp (base or frame pointer) are used to manage stack. After each push
operation, stack grows and rsp is moved down (as stack grows from higher to
lower addresses) to point to the top of the stack; after each pop operation,
stack shrinks and rsp is moved up to point to the top of the updated stack.

Heap does not have a fixed size, it can grow arbitrary large, but it is not
managed automatically by the hardware, heap management is done in software by
operating system.

####  2.3.3 Function Calls

A function call is initiated using the call instruction, however, it requires
the program flow to return to the calling function, namely the caller, once
the called function, namely the callee, has finished. The steps showing the
working of a function call are:

  1. 1.

Caller sets up parameters in registers and stack (if number of parameters is
large) that need to be passed in accordance of the calling convention (first
six arguments go in rdi, rsi, rdx, rcx, r8, r9, rest on stack).

  2. 2.

The call instruction pushes the return address on the stack and sets rip to
the target address.

  3. 3.

Callee pushes rbp on the stack and creates a new stack frame for itself by
setting rbp to rsp.

  4. 4.

The callee reserves some space on the stack by decreasing rsp and remaining
instructions in the callee execute.

  5. 5.

Callee sets the stack back to the way it was by setting rsp to rbp and pops
into rbp, restoring the original value of rbp which was stored earlier.

  6. 6.

The ret instruction loads the value rsp points to into rip, it will be the
return address stored earlier, this instruction is just like pop rip
instruction.

  7. 7.

If parameters were passed on the stack, the callee cleans up the stack also by
increasing rsp.

##  3 Design

In this section, we will discuss the working of our tool, algorithm of how it
uses the gadgets retrieved from an x86_64 executable file to build a ROP chain
of gadgets executing some arbitrary function. This process is completed in 3
steps:

  * •

First step is to fetch all the ROP Gadgets from the binary upto a maximum
depth.

  * •

Next, process each gadget and convert it into a sequence of simpler
mathematical equations and divide the gadgets into 2 categories; (1) gadgets
whose result does not depend on any initial state of registers, (2) gadgets
whose result depend on initial state of registers.

  * •

Finally, compute a permutation of gadgets which is essentially the required
ROP chain of gadgets.

###  3.1 Inputs

The tool takes 2 inputs:

  * •

Executable file: User has to provide some x86_64 binary file, the only
restriction is that it should not reference any dynamic libraries, all the
libraries required for the binary must be statically linked. The reason for
static linking is that we will process the binary for gadgets, all the binary
code should be available to use, if the linking is dynamic then this will not
be the case.

  * •

Program: User provides a program formatted as one or more series of system
calls that he wants to execute, with arbitrary arguments, such as "exit(1)",
write(1, "hello, world", 12) etc.

###  3.2 Important points in algorithm

While developing the algorithm, we have taken certain assumptions and
determined some important results regarding gadgets, they are the following:

  * •

Assumption: Memory instructions are ignored. The reason behind this assumption
is while performing static analysis of binary, one cannot deterministically
find the value stored in some memory address because it is dynamic, thus it
can’t always be dealt with during static analysis.

  * •

In all the gadgets used for analysis, the sequence of instructions should such
that each push or stack pointer decrement instruction should have a
corresponding pop or stack pointer increment function. If this is not followed
and in case the stack has further grown during the execution of gadget, then
at the time of ret instruction, the stack pointer won’t be pointing to next
gadget, thus, jumping to next gadget will not be possible since it leads to a
recursive problem.

###  3.3 Algorithm

In this subsection, we will discuss the 3 steps of the algorithm in detail.

We will illustrate the algorithm using an example of echo binary from GNU
Coreutils 8.1 for ROP gadgets and use the gadgets retrieved from it to execute
mprotect system call with arbitrary arguments.

####  3.3.1 Retrieval of Gadgets

To retrieve ROP gadgets from an executable file, we use a tool called
ROPGadget [Sal11], this tool is useful in fetching and searching for gadgets
in binaries on different platforms. It retrieves all ROP Gadgets upto certain
depth and gives us gadgets in x86_64 assembly code format along with the
offset address inside the binary. For illustrating the output received at this
step, we will show some of the gadgets which will be used in later steps, we
will assign gadget serial numbers for easy reference.

No | Offset | Gadget Instructions
---|---|---
1 | 0x00000000000054cf | mov edx,eax; add rsp, 8; ret
2 | 0x0000000000005011 | mov eax, 0x1; ret
3 | 0x00000000000026d0 | mov eax, 0xa; ret
4 | 0x00000000000022fe | pop rdi; ret
5 | 0x00000000000022fc | pop rsi; pop r15; ret

####  3.3.2 Transformation of Gadgets

The next step is to process each gadget retrieved from the binary and
transform it into a sequence of simple mathematical equations to make the
computation easier, these equations will be used later in this step to
classify gadgets into 2 categories as described earlier in this section.

From Step 1, we will get all the gadgets in x86_64 assembly code format, using
the knowledge of x86_64 architecture, we will convert each instruction of a
gadget to a simple equation, thus each gadget will form a sequence of
equations.

The conversion scheme for different x86_64 instructions will be as follows:

  * •

Data Movement Instructions: instructions like mov, push and pop.

    * –

mov instruction
mov dest, src $\rightarrow$ dest = src
mov dest, const $\rightarrow$ dest = const

    * –

push and pop instructions
We will discuss these instructions later in detail.

  * •

Arithematic & Logic instructions: instructions performing basic arithematic
and logical operations.

    * –

add/sub/and/or/xor instructions
op dest, src $\rightarrow$ dest = dest op src
op dest, const $\rightarrow$ dest = dest op const

    * –

inc/dec/neg/not instructions
op dest $\rightarrow$ dest = op dest

    * –

imul instruction
imul dest $\rightarrow$ rdx:rax = rax * dest (rdx used in case of overflow)
imul dest, src $\rightarrow$ dest = dest * src
imul dest, src, const $\rightarrow$ dest = src * const

    * –

idiv instruction
idiv dest $\rightarrow$ rax = rdx:rax / dest; and rdx = rdx:rax % dest
The values of rax and rdx are quotient and remainder respectively.

    * –

shl/shr/sal/sar/ror/rol instructions (shift and rotate)
op dest, const $\rightarrow$ dest = dest op const
op dest, cl $\rightarrow$ dest = dest op cl (cl is lower 8 bits of RCX
register)

  * •

Exchange instructions: instructions which exchange the values of operands.

    * –

xchg instruction
xchg dest, src $\rightarrow$ temp = dest; dest = src; src = temp
Basically we exchange the contents of dest and src registers.

    * –

xadd dest, src $\rightarrow$ temp = src + dest; src = dest; dest = temp
In addition to exchange of values, sum is placed in dest.

Push and Pop Instructions
While processing a gadget, we will maintain a stack (separate for each) which
will be used to imitate the stack changes during the execution of the gadget,
the push and pop instructions within a gadget will be condensed into equations
using this imitated stack only. An important thing to note here is that, if
there is a pop instruction without a corresponding push instruction, then the
value will be retrieved from stack which is under our control, thus the value
can be set arbitrarily (represented by * in equation). An example of this is
as follows:

Gadgets |  Sequence of Equations
---|---
pop rax; push rbx; pop rdx; pop rcx; ret |  rax = *; rdx = rbx; rcx = *
push r15; push r14; pop rax; push r13; pop rbx; pop rcx; pop rdx; ret |  rax = r14; rbx = r13; rcx = r15; rdx = *

The algorithm for transformation of gadgets will be as follows:

Algorithm 1 Transform Gadget

1:procedure transformGadget(Gadget $\mathcal{G}$)$\triangleright$ Takes gadget
as input

2: s $\leftarrow$ new Stack() $\triangleright$ Initialize stack for gadget
execution

3: for all inst $i\in\mathcal{G}.inst$ do

4: if $i$ is a "ret" inst then

5: if s.empty $\neq$ true then

6: $\mathcal{G}.equations\leftarrow[]$

7: return false$\triangleright$ Gadget can’t be used

8: end if

9: return true

10: else if $i$ is a “push reg" inst then

11: s.push(reg)

12: else if $i$ is a “pop reg" inst then

13: if s.empty == true then

14: $\mathcal{G}$.add_equation(reg = *)$\triangleright$ Stack is under our
control

15: else

16: $tmpreg\leftarrow$ s.pop()

17: $\mathcal{G}$.add_equation(reg = tmpreg)

18: end if

19: else

20: $e\leftarrow$ convert_inst($i$)$\triangleright$ Convert according to
defined rules

21: $\mathcal{G}$.add_equation($e$)

22: end if

23: end for

24:end procedure

An important point to be noted here is that, during building a sequence of
equations, we try to remove redundant calculations, this means that if a
sequence of equations such as "rax = 0; rbx = rax + 10;" occurs, then we
flatten the equations into "rax = 0; rbx = 10;".

After transformation of gadgets into simple equations, the gadgets will be
classified into 2 categories, based on their dependence on previous values of
registers. This classification can be performed trivially by checking if the
RHS of any equation in the sequence involves a register argument.

The algorithm for classification of gadgets will be as follows:

Algorithm 2 Classify Gadget

1:procedure classifyGadget(Gadget $\mathcal{G}$)$\triangleright$ Takes gadget
as input

2: for all equations $e\in\mathcal{G}.equations$ do

3: if RHS has a register argument $a_{r}$ then

4: return Category 2$\triangleright$ Dependent on initial state

5: end if

6: end for

7: return Category 1$\triangleright$ Independent of initial state

8:end procedure

Performing the 2nd step on our example will give us following sequence of
equations for each of the gadgets, simultaneously classifying gadgets into the
2 categories:

Gadgets | Sequence of Equations
---|---
Category 1 Gadgets
mov eax, 0x1; ret | eax = 1
mov eax, 0xa; ret | eax = 10
pop rdi; ret | rdi = *
pop rsi; pop r15; ret | rsi = *; r15 = *
Category 2 Gadgets
mov edx,eax; add rsp, 8; ret | edx = eax; rsp = rsp + 8

####  3.3.3 Construction of ROP chain

At this point, we have 2 classes of gadgets, one which depend on initial
values of some registers and other one which do not. These gadgets are in the
form of simple mathematical equations. Now, our goal is to generate a chain of
gadgets which executes the program (system call) we desire.

We will denote our goal, which is execution of a system call with arbitrary
arguments, as a required objective state of registers before making the
syscall. For our example, the objective state will be as follows:

rax = 10; rdi = addr; rsi = length; rdx = 1

We will process the first category of gadgets (having no dependence)
separately, this processing step is performed mainly for 2 reasons:

  * •

We can have all the possible states of registers which do not depend on any
initial state, i.e. all of these states can be generated and used as an
initial state for any gadget which depends on some initial state.

  * •

Processing of these gadgets is easy, and most of the binaries have such
diverse gadgets that only using these gadgets can achieve the objective state,
without even having to process the 2nd category of gadgets.

For each register involved in “objective_state", we will maintain a list of
permutations which result in the required value of that register. The
algorithm for Permuting over category 1 gadgets will be as follows:

Algorithm 3 Permutation1

1:procedure Permutation-1(Gadget $g\in\mathcal{G}_{c1}$)$\triangleright$ Takes
Category 1 gadgets as input

2: for all permutations $p$ of gadgets $g\in\mathcal{G}_{c1}$ do

3: save_distinct_state($p$)$\triangleright$ Save state only if it doesn’t
exist before

4: end for

5: for all reg $r\in\text{objective\\_state.registers}$ do

6: for all distinct permutations $p$ including $r$ (from saved states) do

7: if $p.\text{state.r.val}==\text{r.val}$ then

8: r.permutations.append($p$)

9: end if

10: end for

11: end for

12:end procedure

After processing the first category of gadgets, we have the set of states
which can be used as an initial state at any point of time for the 2nd
category of gadgets. We will now process 2nd category of gadgets only for
those registers whose values are not set from the 1st category of gadgets.

For each register whose value is not reached the final state by a permutation
of gadgets from category 1, we will start picking gadgets from category 2,
each distinct permutation of category 2 will be evaluated on the basis of what
initial state will result in a required final state, if the initial state is
achievable, then save the current permutation for the register. During this
permutation, we will form a sequential structure from the permutation of
category 2 gadgets whose root will be finally a category 1 gadget which will
signify the initial state that when combined with remaining elements (category
2 gadgets) produces the required result. The algorithm for permuting over
category 2 gadgets will be as follows:

Algorithm 4 Permutation2

1:procedure Permutation-2(Gadget
$g_{1}\in\mathcal{G}_{c1},g_{2}\in\mathcal{G}_{c2}$)

2: for all Register $r\in\text{final\\_states.registers}$ (if still not set)
do

3: Permute over Category 2 Gadgets involving $r$ in LHS and find out what
initial state does each permutation require to reach final_state.

4: if initial state is achievable then

5: Save the current permutation for the current register.

6: end if

7: end for

8:end procedure

After we have achieved the final state required for making the function call
or system call (in our case), we will set the stack as required by the program
and output the generated final stack to the user.

The stack layout for our example will be as follows:

Gadget # 3
---
dummy value (rsp+8)
Gadget # 1
Gadget # 2
dummy value (r15)
length (= rsi)
Gadget # 5
addr (= rdi)
Gadget # 4

First gadget to be executed in the above stack will be Gadget # 4 since stack
grows downwards. At the top of the stack we can make a call to the gadget
which performs a syscall.

##  4 Evaluation

For evaluating our tool, we have tested our tool against 35 binaries from GNU
Coreutils 8.1. For testing of all the binaries, we kept the maximum depth of
ROP Gadget as 10 bytes, if we increase the depth we will get more gadgets
having no effect on current gadgets. The exhaustive list of binaries with the
total number of ROP gadgets retrieved is shown in the graph below.

From the retrieved list of gadgets, the number of gadgets used for analysis,
i.e. gadgets which were transformed into sequence of equations to be processed
later are is shown in the graph below.

Figure 1: Total number of gadgets fetched from the binary

The numbers of category 1 and category 2 in binaries are shown in graph below.

Figure 2: Total number of gadgets fetched from the binary

For each of the programs the length of ROP chain generated for executing the
same syscall mprotect remains almost same. The reason behind above result is
that each binary has a high amount of pop and mov instructions which sets the
final state for most of the required registers.

##  5 Related Work

As we discussed earlier, the technique of return-to-libc attacks does not rely
on code injection, it redirects the control flow of the program to one or more
functions found in the standard library (standard C library in case of Linux),
allowing the attacker to compromise the target program. Later research [MT11]
has also shown that these sets of gadgets are Turing Complete when the target
binaries are using the standard C library.

The first introduced return-to-libc attacks used entire library functions as
the basic elements of the attack code (i.e. a gadget consisted of the entire
library function, not just a fragment). Krahmer [Kra05] uses small snippets of
code from inside libraries or the program itself, instead of using the entire
functions, these snippets were called borrowed code chunks, each chunk was
responsible for transferring the execution to the next chunk. Shacham [Sha07b]
formalizes these attacks and shows that Turing-Completeness is possible even
if the C library of Linux system is used, he created chunks ending in a ret
instruction, our so-called ROP gadgets. There was also some follow up work in
RISC architectures [EB08], [LD10], [Kor09], pop/jmp paired instructions and
Jump-oriented programming [TB11].

The first ROP paper [Sha07b] describes a hand-picked set of gadgets. The
arrangement or presence of certain gadgets may depend on compilers or
compilation options. Shacham, in the original paper uses combinations of
complex gadgets to implement arithmetic operations and branching.

There were more efforts focussed on automated construction of valid and
Turing-complete sets of gadgets [RH09], [TD10], [EJS11], [Sol10]. These tools
usually worked with small programs written in some specific format, taking
gadgets out of an input binary and generating a suitable chain of gadgets
implementing the program.

Most of the approaches faced a significant problem of matching gadgets to
execute some arbitrary program, most of them limit the gadgets to a few
instructions [RH09] . They only use their limited set of gadgets for each
required operations. Another implementation [TD10] reduces each gadget to an
expression tree which captures the gadget’s behaviour. Another one [EJS11]
identifies the semantics of a gadget by using a semantic analysis on
postconditions, then a similar tree-based approach to match the semantics to
the behavior of the code. An other approach [Sol10] uses a SMT solver to re-
write each gadget as a series of binary functions of the input bits, each
function corresponds to an output bit, thus, the problem reduces to matching
boolean functions between the gadgets and the target code.

##  6 Conclusion/Future Work

We presented our tool which takes as input a binary and a program in the form
of system calls, gets a list of ROP gadgets present in the binary upto a
certain maximum depth (can be set arbitrarily) and uses these gadgets to build
a ROP chain of gadgets which can be used to execute the program using already
existing code in the program’s memory space. The gadgets were converted to a
set of equations which can be evaluated mathematically and using these
equations, it can be found which gadgets depend on some initial state of
registers and which ones do not. Thus, using this info we figure out a
suitable permutation of gadgets which will satisfy a final state for executing
the code that we desire.

This tool was designed based on the principles of ROP and x86_64 architecture,
its purpose is to tackle the problems that a user faces when developing a
program using ROP and in turn automate this process so that user does not have
to devote a lot of his/her time in finding gadgets and placing them in
suitable order. The purpose of this tool is also to verify that ROP gadgets
are Turing Complete, for which we take an arbitrary binary from user and try
to find gadgets only from that by static linking libraries (if any used).

Our approach is not a very efficient one, since the time taken in finding
suitable ROP chain of gadgets for a large binary can take a long time. We plan
to make the tool more efficient by introducing caching techniques and
extending the tool in multiple dimensions i.e. the computation involving
gadgets which do not depend on each other should be done in parallel, not in
sequential manner.

Our design currently assumes various mitigation techniques such as ASLR,
shadow stack and others are disabled and our focus is only on finding a
suitable ROP chain of gadgets which executes a given program by reusing the
code available in the binary. In future, we can expand the design of the tool
to include attacks against commonly used mitigation techniques, so even if any
of the mitigation techniques are present, a suitable ROP attack can still be
performed.

We currently don’t support building chains using Jump-Oriented programming
technique but we can retrieve JOP gadgets, in future, we would integrate JOP,
so that the chain of gadgets generated might take advantage of both JOP and
ROP, because now-a-days there are mitigation techniques which prevent ROP
attacks but they do not work well with JOP attacks.

In future, we plan to test our tool against many more benchmarks to improve
its quality and thus fulfill our goals of finding difficulties and fixing them
by completing an automated tool which can produce a suitable ROP chain of
gadgets for any program with any binary as input, thus verifying that ROP is
indeed Turing Complete.

## References

  * [Ano01] Anonymous.  Once upon a free(). . . .  Phrack Magazine 57, 2001.
  * [BK00] Bulba and Kil3r.  Bypassing StackGuard and StackShield.  Phrack Magazine 56, 2000.
  * [Bla10] Dionysus Blazakis.  Interpreter exploitation.  Proceedings of WOOT 2010, H. Shacham and C. Miller, Eds. USENIX, 2010.
  * [Ble02] Blexim.  Basic integer overflows.  Phrack Magazine 60, 2002.
  * [CC98] Dave Maier Jonathan Walpole Peat Bakke SteveBeattie Aaron Grier Perry Wagle Qian Zhang Crispan Cowan, Calton Pu.  StackGuard: Automatic detection and prevention of buffer-overflow attacks.  Proceedings of USENIX Security 1998, pages 63–78, 1998.
  * [Des00] Solar Designer.  Jpeg com marker processing vulnerability in netscape browsers.  https://www.openwall.com/articles/JPEG-COM-Marker-Vulnerability, 2000.
  * [Dur02] Tyler Durden.  Bypassing PaX ASLR protection.  Phrack Magazine 59, 2002.
  * [EB08] Hovav Shacham Stefan Savage Erik Buchanan, Ryan Roemer.  When good instructions go bad: generalizing return-oriented programming to RISC.  Proceedings of the 15th ACM Conference on Computer and Communications Security, pages 27–38, 2008.
  * [EJS11] David Brumley Edward J. Schwartz, Thanassis Avgerinos.  Q: Exploit Hardening Made Easy.  Proceedings of the 20th USENIX Security Symposium (2011), USENIX Association, 2011.
  * [GR01] Gera and Riq.  Advances in format string exploiting.  Phrack Magazine 59, 2001.
  * [HE01] Kunikazu Yoda Hiroaki Etoh.  ProPolice: Improved stack-smashing attack detection.  2001\.
  * [Hor02] Oded Horovitz.  Big loop integer protection.  Phrack Magazine 60, 2002.
  * [HS04] Ben Pfaff Eu-Jin Goh Nagendra Modadugu Dan Boneh Hovav Shacham, Matthew Page.  On the effectiveness of address-space randomization.  Proceedings of CCS 2004, page 298–307, 2004.
  * [Int16a] Intel.  Control-flow enforcement technology preview.  2016\.
  * [Int16b] Intel.  Intel 64 and IA-32 Architectures Software Developer’s Manual.  2016\.
  * [JWM12] Dong-Young Lee Tai-Myoung Chung Jae-Won Min, Sung-Min Jung.  Jump oriented programming on windows platform (on the x86).  Lecture Notes in Computer Science, 7335:376–390, 2012.
  * [Kae01] Michel Kaempf.  Vudo malloc tricks.  Phrack Magazine 57, 2001.
  * [Klo99] Klog.  The frame pointer overwrite.  Phrack Magazine 55, 1999.
  * [Kor09] Tim Kornau.  Return oriented programming for the arm architecture.  Master’s thesis, RuhrUniversität Bochum, 2009.
  * [Kra05] Sebastian Krahmer.  x86-64 buffer overflow exploits and the borrowed code chunks exploitation technique.  Online, 2005.
  * [LD10] Ahmad-reza Sadeghi-Marcel Winandy Lucas Davi, Ra Dmitrienko.  Return-oriented programming without returns on ARM.  System Security Lab, Ruhr University Bochum, Germany, 2010.
  * [MA09] Úlfar Erlingsson Jay Ligatti Martín Abadi, Mihai Budiu.  Control-flow integrity principles, implementations, and applications.  ACM Trans. Info. & System Security 13, 2009.
  * [MT11] Tyler Bletsch Xuxian Jiang Vincent Freeh-Peng Ning Minh Tran, Mark Etheridge.  On the Expressiveness of Return-into-libc Attacks.  Proceedings of the 14th International Symposium on Recent Advances in Intrusion Detection, 2011.
  * [One96] Aleph One.  Smashing the stack for fun and profit.  Phrack, 7, 1996.
  * [PA09] Miguel Castro Steven Hand Periklis Akritidis, Manuel Costa.  Baggy bounds checking: An efficient and backwards-compatible defense against out-of-bounds errors.  18th USENIX Security Symposium, Montreal, Canada, August 10-14, 2009, Proceedings, pages 51–66, 2009.
  * [RH09] Felix C. Freiling Ralf Hund, Thorsten Holz.  Return-Oriented Rootkits: Bypassing Kernel Code Integrity Protection Mechanisms.  Proceedings of the 18th USENIX Security Symposium, pages 383–398, 2009.
  * [RR12] Hovav Shacham Stefan Savage Ryan Roemer, Erik Buchanan.  Return-oriented programming: Systems, languages, and applications.  ACM Trans. Inf. Syst. Secur., 2012.
  * [SA04] Vincent Abella Starr Andersen.  Changes to Functionality in Microsoft Windows XP Service Pack 2.  page Part 3, April, 2004.
  * [Sal11] Jonathan Salwan.  Ropgadget.  https://github.com/JonathanSalwan/ROPgadget, 2011.
  * [SC10] Alexandra Dmitrienko Ahmad-Reza Sadeghi Hovav Shacham Marcel Winandy Stephen Checkoway, Lucas Davi.  Return-oriented programming without returns.  Proceedings of the 17th ACM Conference on Computer and communications security, CCS ’10, page 559–572, 2010.
  * [Sha07a] Hovav Shacham.  m. The geometry of innocent flesh on the bone: return-into-libc without function calls (on the x86).  Proceedings of the 14th ACM Conference on Computer and communications security, CCS ’07, page 552–561, 2007.
  * [Sha07b] Hovav Shacham.  The Geometry of Innocent Flesh on the Bone: Return-into-libc without Function Calls (on the x86).  Proceedings of the 14th ACM Conference on Computer and Communications Security, pages 552–561, 2007.
  * [Sol10] Pablo Sole.  Hanging on a ROPe.  ekoParty Security Conference, 2010.
  * [ST01] Scut and Team Teso.  Exploiting format string vulnerabilities.  2001\.
  * [TB11] Vince W. Freeh-Zhenkai Liang Tyler Bletsch, Xuxian Jiang.  Jump-oriented programming: a new class of code-reuse attack.  Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security, pages 30–40, 2011.
  * [TD10] Ralf-Philipp Weinmann Thomas Dullien, Tim Kornau.  A framework for automated architecture-independent gadget search.  Proceedings of the 4th USENIX conference on Offensive technologies, 2010.
  * [Tea03a] PaX Team.  PaX address space layout randomization.  2003\.
  * [Tea03b] PaX Team.  PaX non-executable pages design & implementation.  2003\.
  * [THD15] David Wagner Thurston H.Y. Dang, Petros Maniatis.  The performance cost of shadow stacks and stack canaries.  Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, ASIA CCS ’15, page 555–566, 2015.
  * [UE06] Michael Vrable Mihai Budiu George C. Necula Ulfar Erlingsson, Martin Abadi.  XFI: Software Guards for System Address Spaces.  Proceedings of OSDI 2006, pages 75–88, 2006.
  * [Zal01] Michal Zalewski.  Remote vulnerability in SSH daemon CRC32 compression attack detector.  2001\.