Data-Oriented Programming

Posted on Edited on In

Introduction

Control-flow hijacking attacks are the predominant category of memory exploits today. In response, numerous principled defenses which aim to ensure legal control flow has been proposed.

A natural question is to analyze the limits of protection offered by control-flow defenses, and the remaining capabilities of the adversary. Control-flow defenses aim to ensure the execution of the program stay legitimate, by protecting the integrity of the control plane memory of by directly checking the targets of control transfers. However, the data plane of memory can offer an additional source of advantage for adversaries (e.g., non-control data attacks).

In this paper, we show that non-control data attacks with rich expressiveness can be crafted using systematic construction techniques. The key idea in our contribution is to find data-oriented gadgets. then we find gadget dispatchers which are fragment of logic that chain together disjoint gadgets in an arbitrary sequence.

Problem

Non-control Data Attacks

Non-control data attacks tamper with or leak security-sensitive memory, which is not directly used in control-flow transfer instruction. The attack payloads, however, exhibit limited expressiveness, such as writing a target variable of choice or leaking contents of a sensitive memory region. Such simple payloads can enable privilege escalation and sensitive data-leakage attacks.

However, non-control data attacks cannot divert the control flow to arbitrary location, unlike ROP attacks, the expressiveness is believed to be very limited.

Example

In fact, non-control data attacks can offer rich exploits from common vulnerabilities.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct server{ int * cur_max, total, typ;} *srv;
int connect_limit = MAX_CONN; int *size, *type;
char buf[MAXLEN];
size = &buf[8]; type = &buf[12];
...
while (connect_limit--) {
  readData(socketfd, buf);        // stack bof
  if (*type == NONE)  break;      
  if (*type == STREAM) {          // condition
    * size = * (srv -> cur_max);  // dereference
  } else {
    srv -> typ = * type;          // assignment
    srv -> total += * size;       // addition
  }
...
}

This code does not invoke any security-critical functions in its benign control-flow, and the vulnerability just corrupts a handful of local variables.

The assignment, dereference and the addition operation can be considered as data-oriented gadgets. The loop structure is called gadget dispatchers.

Data-Oriented Programming

DOP Overview

The key is to manipulate non-control data such the executed instructions do the attacker’s bidding. In order to give a concrete and systematic construction, we define a simple mini-language called MINDOP with a virtual instruction set and virtual register operands, in which payload we can specific.

The MINDOP language has 6 kinds of virtual instructions, each operating on virtual register operands. Each virtual operation is simulated by real x86 instruction sequences available in the vulnerable program, which we call data-oriented gadgets. The control structure allows chaining of gadgets, and the x86 code sequences that simulate the virtual control operations are referred to as gadget dispatchers. None of the gadgets or dispatchers modify any code-pointers or violate CFI in the real program execution.

Semantics Instructions in C Data-Oriented Gadgets in DOP
arithmetic/logical a op b *p op *q
assignment a = b *p = *q
load a = *b *p = **q
store *a = b **p = *q
jump goto L vpc = &input
conditional jump if a goto L vpc = &input if *p

Data-Oriented Gadgets

Virtual operations in MINDOP are simulated using concrete x86 instruction sequences in the vulnerable program execution. Such instruction sequences or gadgets read inputs from and write output to memory locations which simulate virtual register operands in MINDOP. Gadgets is within the legitimate CFG of the program, therefore, between two gadgets there maybe several uninteresting instructions which out of the attacker’s control.

Conceptually, a data-oriented gadget simulates three logical micro-operations: the load micro-operation, the intended virtual operation’s semantics, which are different for each gadget, and the final store micro-operation.

C code srv -> total += *size
ASM Code 1. mov (%esi), %ebx  // load micro-op
2. mov 0x4(%edi), %eax  // load micro-op
3. add %ebx, %eax  // addition
4. mov %eax, 0x4(%edi)  //store micro-op

Data-oriented gadgets are similar to code gadgets employed in return-oriented programming or in jump-oriented programming. However, there are two differences between data-oriented gadgets and code gadgets. First, data-oriented gadgets require to deliver operation result with memory. Second, data-oriented gadgets must execute in at least one legitimate control flow, and need not execute immediately one after another.

Simulating Arithmetic Operations. With addition over arbitrary values, it is possible to simulate multiplication efficiently if the language supports conditional jumps. MINDOP supports conditional jumps which allow to check if a value is smaller / greater than a constant. This can help us to compute the bit-decomposition of a finite-size integer. With bit-decomposition, simulating a multiplication a * b reduces to the efficient shift-and-add procedure, adding a to itself in each step conditional on the bits in b.

Simulating Assignment Operations. In MINDOP, assignment gadgets read data from one memory location and directly write to another memory location, e.g., load -> move -> store.

Simulating Dereference (Load/Store) Operations. In data-oriented programming. registers are simulated by memory, therefore the memory dereference is simulated by two memory dereferences.

Gadget Dispatcher

Various gadgets can be chained sequentially by gadget dispatchers to enable recursive computation. Gadget dispatchers are sequences of x86 instructions that equip attackers with the ability to repeat gadget invocations and, for each invocation, to selectively activate specific gadgets.

Each iteration executes a subset of gadgets using outputs from gadgets in the previous iteration, which done by change the load address if iteration i+1 to the store addresses of iteration i. Additionally, the selector’s behavior is controlled by attackers through the memory error. The corruption is done in a way that it enables only the gadgets of the attacker’s choice. These gadgets take as input the outputs of the previous round’s gadget by selectively corrupting operand pointers. The remaining gadgets may still get executed, but their inputs and outputs are set up such that they behave like NOPs.

An interactive attack means attacker can prepare the memory state at the start of loop iteration i in a way that the desired gadget works as required and other gadgets operate on unused memory.

Another class of DOP attacks are non-interactive, whereby the attacker provides the entire malicious input as a single data transmission. In such a scenario, all the memory setup and conditions for deciding loop termination and selective gadget activation need to be encoded in a single malicious payload. To support such attacks, MINDOP has two virtual operations that enable conditional chaining of operations, or virtual jumps. The basic idea is as follows: the attacker provides the memory configuration Mj necessary for each gadget j to be selectively executed in a particular iteration in the input payload. In addition, it keeps a pointer called virtual PC which points to the desired configuration Mj at the start of each iteration. It suffices to corrupt only the virtual PC, so that the program execution in that iteration operates on the configuration Mj. To decide how to switch to Mk in the next instruction, MINDOP provides virtual operations that set the virtual PC, conditionally or unconditionally.

Simulating Jump Operations. The key here is to identify a suitable variable to implement a virtual PC which can be corrupted in each loop iteration. To simulate an unconditional jump, attackers just prepare the memory configuration to trigger another operation gadget (e.g., addition, assignment) to change the value of the virtual PC.

DOP Attack Construction

Challenges

Though the concept of data-oriented programming is intuitive, it is challenging to construct data-oriented attacks in real-world programs:

  • Data-oriented gadget identification. We use static analysis as an aid in identifying these gadgets.

  • Gadget dispatcher identification. Our gadget dispatcher requires a loop with various gadgets and a selector controlled by the memory error. But it is possible to have the selector and gadgets inside the functions called from loop body.

  • Data-oriented gadget stitching. The reachability of gadgets depends on concrete memory errors. We need to find malicious input that makes the program execute selected gadgets with the expected addresses and order.

Gadget Identification

A useful data-oriented gadget needs to satisfy the following requirements:

  • MINDOP semantics. It should have instructions for the load micro-operation, the store micro-operation, and others simulating semantics of MINDOP.
  • Gadget internal order. The three micro-operations should appear in the load-operation-store order, and this correct order should show up in at least one legitimate control flow.
1
2
3
4
5
6
7
8
9
10
11
12
13
Input:  G:- the vulnerable program
Output: S:- data-oriented gadget set

S = ∅;
FuncSet = getFuncSet(G)
foreach f ∈ FuncSet do
    cfg = getCFG(f)
    for instr = getNextInstr(cfg) do
        if isMemStore(instr) then
            gadget = getBackwardSlice(instr, f)
            input = getInput(gadget)
            if isMemLoad(input) then
                S = S ∪ {gadget}

We compile the program source code into LLVM intermediate representation (IR) and perform our analysis on LLVM IR. Our analysis iterates through all functions in the program. We treat each store instruction in the function as a store micro-operation of a new potential gadget. Then our analysis uses a backward data-flow analysis to identify the definitions of the operands in the store instruction. The generated data-flow contains the instructions that derive the operands, like loaded from memory or calculated from registers.

Gadget Classification. We classify data-oriented gadgets into different categories based on their semantics and computed variables. Gadgets with the same semantics are functional-equivalent to simulate one MINDOP operation. There are no function call gadgets in data-oriented programming, as it does not change the control data. Based on the computed variables, we further classify gadgets into three categories: global gadget, function-parameter gadget and local gadget.

Dispatcher Identification

We use static analysis on LLVM IR for the initial pharse of dispatcher identification. Since loops are necessary for attackers to repeatedly connect gadgets, we first identify all possible loops in the program. For each loop, we scan the instructions in the loop body to find interesting gadgets. For function calls within the loop, we step into functions through the call graph and iterate through all instruction inside.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input: G:- the vulnerable program
Output: D:- gadget dispatcher set

D = ∅;
FuncSet = getFuncSet(G)
foreach f ∈ FuncSet do
    foreach loop = getLoop(f) do
        loop.gadgets = ∅
        foreach instr = getNextInstr(loop) do
            if isMemStore(instr) then
                loop.gadgets ∪= getGadget(instr)
            else if isCall(instr) then
                target = getTarget(instr)
                loop.gadgets ∪= getGadget(target)
        if loop.gadgets != ∅ then
            D = D ∪ {loop}

The second phase of dispatchers identification correlates the identified dispatcher candidates with a known memory error. In this phase, we use a static-dynamic approach to provide identification results with varying degrees of coverage and precision. We mark a loop as reachable if it enfolds the given memory error.

Attack Construction

For a given concrete memory error, the available gadgets and dispatchers rely on the location of the vulnerable code in the program, while the stitchability of gadgets depends on the corruptibility of the memory error. To connect two disjoint data-oriented gadgets, attackers should have the control over the address in the load micro-operation of the second gadget or the address in the store micro-operation of the first gadget.

  1. Gadget preparation (semi-automated). Given a memory error, we locate the vulnerable function from the source code. Then we identify the gadget dispatchers that enfold the vulnerable code and collect data-oriented gadgets.

  2. Exploit chain construction (Manual). We take the expected malicious MINDOP program as input.

  3. Stichability verification (Manual). We feed concrete input to the program to trigger memory errors to connect expected gadgets.

Evaluation

Feasibility of DOP

We study 9 applications and measure how many x86 gadgets in these programs can simulate MINDOP operations. We aim to evaluate the following four aspects in our analysis:

  • Empirically justify the choice of operations in MINDOP based on the prevalence of x86 gadgets.
  • Study the distribution of various types of gadgets based on the scope of input operands.
  • Measure the reachability of these x86 gadgets in concrete executions in presence of an exploitable memory corruption.
  • Verify if the memory error (in the public CVEs) have the capability to control the input operands and activate the gadgets in concrete executions.

Gadgets classification. We classify data-oriented gadgets into three categories based on the scope of the operands, such as global gadgets, function-parameter gadgets and hybrid gadgets

Execution reachability from memory errors. We run the vulnerable program with given CVE PoC to get dynamic function call trace, including the vulnerable function. From function call trace, we identify the function invoked by the vulnerable function during the execution. The gadgets inside the invoked function and enfolding loops are the reachable gadgets from the dispatcher.

Turing-Complete examples

ProFTPD is a file server and it’s 1.2-1.3 versions have a stack-based buffer overflow vulnerability in the sreplace function.

1
2
3
4
5
6
7
8
9
10
11
12
13
char *sreplace(char *s, ...) {
    char *src; *cp, **mptr, **rptr;
    char *marr[33], *rarr[33];
    char buf[PR_TUNABLE_PATH_MAX] = {'0'};
    src = s; cp = buf; mptr = marr; rptr = rarr;
    ...
    while (*src) {
        for (; *mptr; mptr++, rptr++) {
            sstrncpy(cp, *rptr, blen - strlen(pbuf));
        }
    }
}
/*memory error & assignment*/
  • Conditional assignment operation. We use the sstrncpy function to simulate an assignment which moves data from on arbitrary location to another. In the first iteration of the while loop, the memory error corrupts the variable cp and the content of the array rarr. So in the next iteration, both the source and the target of the string copy sstrncpy are controlled by the attacker. This way, the attacks simulate a assignment operation which is conditional because the attacker can corrupt src.
1
2
3
4
5
6
7
8
9
int pr_display_file(...) {
    ...
    outs = sreplace(p, buf, ..., "%V", main_server -> ServerName,);
    pr_response_send_raw("%s-%s", code, outs);
}

void pr_response_send_raw(const chat *fmt, ...) {
    vsnprintf(resp_buf, size, fmt, msg);
}
  • Dereference operations(Load/Store). The load operations takes two memory addresser as input(p and q) and performs operation *p == ** q. We decompose the operation into two sub-operations: * ptmp = * q and * p = * tmp, such that the ptmp is the address of tmp. We use the assignment gadgets to move data from resp_buf to &ServerName as the first dereference. Then we use the fuction pr_display_file, which reads the contents of ServerName to the buffer resp_buf as the second dereference. These two dereference from MINDOP load operation *resp_buf = ** resp_buf.
1
2
3
MODRET xfer_log_retr(cmd_rec *cmd) {
    session.total_bytes_out += session.xfer.total_bytes;
}
  • Addition operation. The structure session is a global variable and hence all the operands of this gadget are under attacker’s control. To achieve an addition operation on arbitrary memory locations, we use the MINDOP assignment operation to load operands from desired source locations to the session structure, perform the addition, and then move the result to the desired destination location.
1
2
3
4
5
6
7
8
9
10
11
12
void cmd_loop( server)rec * server, conn_t *c) {
    while (True) {
        pr_netio_telnet_gets(buf, ..);
        cmd = make_ftp_cmd(buf, ...);
        pr_cmd_dispatch(cmd);
    }
}

char * pr_netio_telnet_gets(char * buf, ...) {
    while (* pbuf -> current != '\n' && toread > 0)
        * buf++ = * pbuf -> current++;
}
  • (Conditional) jump operation. pbuf -> current is a pointer to next command in the input, thus forming a virtual PC for attacker’s MINDOP program. By corrupting pbuf -> current, the attacker can select a particular input that invokes a specific MINDOP operation. We use assignment operation to conditionally update virtual PC, thus simulating a conditional jump operation.

Wireshark is a widely used network packet analyzer and its versions before 1.80 have a stack-based buffer overflow vulnerability. The buffer pd in function packet_list_dissect_and_cache_record accepts frame data from a mpeg trace file. If the attacker sends a malicious trace file containing a large frame, the frame data overflows the buffer. This is used to overwrite variables col, cinfo, and parameter packet_list with malicious input.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void packet_list_dissect_and_cache_record (PacketList * packet_list, ...) {
    gint col; column_info * cinfo;
    guint8 pd[WTAP_MAX_PACKET_SIZE];    // vul buf
    // memory error function
    cf_read_frame_r(..., fdata, ..., pd);
    packet_list_change_record(packet_list, ..., col, cinfo);
}

void packet_list_change_record(PacketList * packet_list, ..., gint col, column_info * cinfo) {
    record = packet_list -> physical_rows[row];
    record -> col_text[col] = (gchar * )cinfo -> col_data[col];

    if (!record-> col_text_len[col])
        ++packet_list -> const_strings;
}

void gtk_tree_view_column_cell_set_cell_data(...) {
    for (cell_list = tree_column -> cell_list; cell_list;
         cell_list = cell_list -> next) {
             ...
             // finally calls vulnerable function
             show_cell_data_func();
         }
}

  • Assignment operation. Line record -> col_text[col] = (gchar * )cinfo -> col_data[col]; shows the gadget. The attacker corrupts record and cinfo to point to controllable memory location.

  • Dereference operation(Load / Store). To simulate a load operation, the attacker corrupts record->col_text and cinfo. To simulate a store operation, the attacker can change the value of record and cinfo->col_data.

  • Conditional addition operation. if (!record-> col_text_len[col]) and ++packet_list -> const_strings; if the attacker corrupts packet_list, she can invoke it to perform add operation on the target location.

  • Conditional jump operation. The memory error is triggered by the file read, and the program maintains a file position indicator in the FILE structure. The attacker can change the file position indicator which serves as a virtual PC.

To chain a large number of gadgets together, we identify a gadget dispatcher from the parent function gtk_tree_view_column_cell_set_cell_data. In the first invocation of the memory error, the attacker uses the assignment operation to corrupt the loop condition cell_list, and points it to a fake linked-list in the malicious payload, making it an infinite loop.

Why are expressive payload useful

Bypassing Randomization Defenses. We show how to defeat ASLR with DOP without leaking any addresses to the network. As a real example, consider the vulnerable ProFTPD server, which internally uses OpenSSL for authentication. Our goal is to leak the server’s OpenSSL private key. We found that the private key has a chain of 8 pointers pointing the private key buffer.

The key idea is to use a short MINDOP virtual program that starts from the base pointer (of known location) and dereference it 7 times within the server’s memory to correctly determine the randomized location of the private key. Once we have the private key buffer’s address, we simply replace an address used by a public output function, causing it to leak the private data to the network.