Dead simple DTA tool using Frida

Binary analysis
bkwg
February 27, 2021

Introduction

For a school project, we had to do “something related to security using Python“. Because I was going through this book (which by the way is strongly recommended if you’re interested in binary analysis), we decided to build a set of tools and one of them was a dynamic taint analysis (DTA) program.

This subject is well explained in the aforementioned book and plenty of resources are available online (I’ve listed some at the end of this post) if you want to learn more about it.

Getting into the thing

The idea was to learn the principles of dynamic taint analysis (DTA). DTA can be used to do several things such as:

  • Fuzzing
  • Vulnerability detection
  • Malware analysis
  • …

At 10,000 feet, DTA is about keeping track of some data, along program execution. What data do we want to track? Typically, user inputs. How do we track data? Generally, DTA relies on dynamic binary instrumentation (DBI) tools such as Intel PIN, QBDI, DynamoRIO or Frida (the one we will be using).

To put DTA in place, three things are necessary:

  1. A taint source
    This is the point from which we want to track data.
  2. A taint sink
    This is where we want to check is the data is tainted or not (typically before an execve, or any sensitive routine).
  3. A taint propagation policy
    This represents how we are going to taint the data during the program execution. The taint propagation policy is characterized by several things for example:
    1. The taint granularity.
      Taint granularity is the unit of data that we will use: do we want to keep a taint for every bit? every byte? every quadword?
    2. The taint colors.
      We can choose to keep track of data using a single taint: data is either tainted or not. But we can add more complexity by adding several “colors”. This can help determine the origin of (from a taint source) each unit of data (and if some data was mixed, etc..). For example:
      • taint(byte) == 0x20? Then data is coming from recv.
      • taint(byte) == 0x4? Then data comes from a malloc.

In our case, we chose to detect two vulnerabilities, double frees and format strings vulnerabilities. For that we implemented a very simple DTA tool.

Implementation

Frida is a dynamic binary instrumentation tool which enables one to write code in JS that gets injected in a chosen process. Under the hood, the script gets interpreted by a JS engine (currently QuickJS).

As we said in the previous section we have to choose 3 components:

  1. Taint sources
    Our taint sources will be fgets and free.
  2. Taint sinks
    Our taint sinks will be printf and free (yes, free is also a taint sink: we will taint free’d bytes and we will check if any byte comes tainted to this same function).
  3. Taint policy
    1. We will taint every bytes returned by our taint sources.
    2. Depending on if the bytes were issued from fgets or free, we will use 2 colors:
      1. TAINT_WRITTEN = 0x1
      2. TAINT_FREED = 0x2
    3. After a malloc we clear the TAINT_FREED tainted bytes.

As we can see the taint policy is very simple and as we will see in the last part, it comes at a cost.

Let’s describe the program.

Interceptor.attach(Module.findExportByName(null, "printf"), {
    onEnter: function(args) {
        var str_ptr = new NativePointer(args[0]);
        var str     = str_ptr.readCString();
        var str_len = str.length;
        var data = "printf" + ":" + str_ptr + ":" + str_len
        send(data);
    }
});

In the code above we are using the attach method of the Interceptor class which basically enables one to bind a callback to a call to the specified function: here we are attaching a callback to every call to printf.

Interceptor.attach(Module.findExportByName(null, "fgets"), {
    onEnter: function(args) {
        var str_ptr = new NativePointer(args[0]);
        var fd      = args[2];
        var count   = args[1];
    },
   onLeave: function(retval) {
        var ptr = new NativePointer(retval);
        var data = "fgets" + ":" + ptr + ":" + ptr.readCString().length;
        send(data);
   }
});
var malloc_size = 0;
Interceptor.attach(Module.findExportByName(null, "malloc"), {
    onEnter: function(args) {
        malloc_size = args[0];
    },
   onLeave: function(retval) {
        var ptr = new NativePointer(retval);
        var data = "malloc" + ":" + ptr + ":" + malloc_size;
        send(data);
   }
});

var freed_ptr;
Interceptor.attach(Module.findExportByName(null, "free"), {
    onEnter: function(args) {
        freed_ptr = args[0];
        var data = "free" + ":" + freed_ptr + ":" + "0";
        send(data);
    }
});

We do exactly the same thing for fgets, malloc and free.

The send function enables us to communicate with the “debugger”, which is in fact our main Python program. Here we are transmitting information following this format: “function:address_of_pointer:length_of_data“.

Now let’s have a look at the main code:

code = open("scr.js", "r").read()

pid = frida.spawn([sys.argv[1]])
session = frida.attach(pid)
script = session.create_script(code)

script.on("message", on_message)
script.load()

In the code above we are launching the executable given as argument (the target program) and injecting the JS code detailed previously.

We are also creating a callback, on_message, which will be called every time a Frida message, will be received from the injected JS code.

def on_message(message, data):
    if (message["type"] == "error"):
        print(message["stack"])
        return
    elif (message["type"] == "send"):
        #if (message["payload"] == "abort"):
        #    print("Aborting program")
        #    frida.kill(pid)
        source    = message["payload"].split(":")[0]
        address   = int(message["payload"].split(":")[1], 16)
        length    = int(message["payload"].split(":")[2], 16)

        # If the string length is 0
        # Preparation of subsequent routines
        if (length == 0): length = 1

        if (source == "fgets"):
            taint_data(address, length, TAINT_WRITTEN)
        elif (source == "printf"):
            if (check_taint(address, length, TAINT_WRITTEN)):
                die("FORMAT STRING", _addr=address, _len=length)
        elif (source == "malloc"):
            untaint_data(address, length, TAINT_FREED)
        elif (source == "free"):
            if (check_taint(address, length, TAINT_FREED)):
                die("DOUBLE FREE", _addr=address, _len=length)
            else:
                taint_data(address, length, TAINT_FREED)
        elif (source == "read"):
            taint_data(address, length, TAINT_WRITTEN)

Here, if we are receiving a “send” message type, we extract the “:” separated information. Then depending on the function that was at the origin, three paths can be followed:

  1. taint_data
TAINT_WRITTEN   = 0x1
TAINT_FREED     = 0x2

shadow_memory = {}

def taint_data(address, length, taint):
    print("[+] Tainting (%d): 0x%x - 0x%x (%d bytes)"\
        % (taint, address, address + length - 1, length))

    addr = address
    while (addr < (address + length)):
        try:
            shadow_memory[addr] ^= taint
        except KeyError:
            shadow_memory[addr] = taint
        addr += 1
    return

The taint propagation is very simple: for every bytes of the data we create a “shadow byte” which is its alter ego in a “shadow memory”.

If the byte is not already tracked in the shadow memory then the taint is copied. If the shadow byte exists then we xor it with the taint.

def untaint_data(address, length, taint):
    print("[+] Untainting: 0x%x - 0x%x (%d bytes)"\
        % (address, address + length - 1, length))

    addr = address
    while (addr < (address + length)):
        try:
            shadow_memory[addr] &= ~taint
        except KeyError:
            addr = addr # wasn't tainted, nop
        addr += 1
    return

The untaint_data routine is pretty simple: we are just setting at 0 the bits encoding the taint.

2. check_taint

This is where we are checking that our taint sinks are processing sane data. We are checking if a byte that is going to be transmitted is tainted by comparing its shadow byte to the taint given as argument. If it is the case True is returned. 

def check_taint(address, length, taint):
    print("[+] Checking taint: 0x%x - 0x%x (%d bytes)"\
        % (address, address + length - 1, length))
    addr = address
    while (addr < (address + length)):
        try:
            tag = shadow_memory[addr]
            if (tag & taint):
                return True
                break;
        except KeyError:
            addr = addr # nop

        addr += 1
    return False

3. die

def die(msg, **kwargs):
     address = kwargs.get("_addr", None)
     length = kwargs.get("_len", None)
     print("\n>>>>> %s VULN DETECTED !!!!!" % msg)
     print(">>>>> DETECTED HERE ---> 0x%x" % address)

Like the name indicates, we could have stop the execution there but instead, when a tainted data is being processed, we just print a message.

Application on simple cases

Following is an example of a vulnerable program.

int main()
{
    int secret_num = 0x8badf00d;
    void* m = malloc(20);
    char name[64] = {0};
    read(0, name, 64);
    printf("Hello ");
    printf(name);   // String format vuln
    printf("! You'll never get my secret!\n");
    printf(name);   // String format vuln
    free(m);
    free(m);        // double free
    m = malloc(20);
    free(m);        // NOT double free
    free(m);        // double free
    return 0;
}

We can see that several lines present vulnerabilities: 8, 10, 12 and 15. So the program should show us 4 vulnerabilities:

And indeed, our program detects the 4 vulnerabilities.

And for the sake of it, here is a last example:

#include <stdio.h>
#include <stdlib.h>

static char g_name[50];

static char* g_a92 = "plugged in\n";

void hi_printf(void) {
    printf("hi printf !\n");
}

void hi_puts(void) {
    puts("hi puts !");
}

void read_name(void) {
    fgets(g_name, 50, stdin);
}

int main(int argc, char* argv[]) {

    // Not detected, as not influenced by user input
    printf(g_name);
    printf(g_a92);

    hi_puts();
    hi_printf();

    read_name();                  // Tainting the g_name buffer


    printf("Make this cheese %d\n", 92);
    printf("--> %s\n", g_name);   // Nothing detected because it is not vulnerable
    puts("Triggering the vuln !");
    printf(g_name);               // Vulnerable

    void* p = malloc(10);
    free((char*)p + 0);
    free(p);

    return 0;
}

We can see that 1 format string is detected, and 1 double is also detected.
Mission accomplished… Not so fast !

Serious bottlenecks

Our implementation is so naive that for example this code is bypassing our detection mechanism:

unsigned int secret = 0xdeadbeef;

void handle_failure(char *buf) {
  char msg[100];
  snprintf(msg, sizeof(msg), "Invalid Password! %s\n", buf);
  printf(msg);
}

int main(int argc, char *argv[])
{
  setreuid(geteuid(), geteuid());
  setvbuf(stdout, NULL, _IONBF, 0);
  setvbuf(stdin, NULL, _IONBF, 0);

  int tmp = secret;

  char buf[100];
  printf("IOLI Crackme Level 0x00\n");
  printf("Password:");

  fgets(buf, sizeof(buf), stdin);

  if (!strcmp(buf, "250382\n")) {
    printf("Password OK :)\n");
  } else {
    handle_failure(buf);
  }

  if (tmp != secret) {
    puts("The secret is modified!\n");
  }

  return 0;
}

In this code, we taint successfully the user buffer ‘buf’. But we can’t detect the vulnerability… Why? If we look at line 5 we can see that the string is copied into another one via snprintf. And because in our taint policy we do not track bytes at instruction level, we lose the tail here…

– Well, but then why not telling Frida to hook every snprintf calls, as we did with the others?

We could have indeed. But this method of having small pieces of code that work only with very specific cases is really not a good approach. For each special case you need to implement a special treatment… erh things can become cumbersome real quick.

What we’ve done here is a really simplified DTA tool. Indeed, a robust tool keeps track of every chunk of data (depending on the taint granularity) across ALL (or nearly all) possible instructions of the targeted architecture (for example libDFT uses a “virtual CPU” to keep track of data even in registers). This means that for instructions like mov, add, sub, etc, we should had put in place a proper taint propagation policy. For example:

  • For each mov instructions, the taint is simply propagated to the destination operand
  • But for xor, for every similar byte in the operands, the taint is removed.
  • …

Lastly, because we used Frida as the DBI tool, our implementation is really slow. It could have been much faster if we used a library relying on a compiled language.

To go further

binary analysisdynamic taint analysisfrida

Join the ConversationLeave a reply

Your email address will not be published. Required fields are marked *

Comment*

Name*

Website

Save my name, email, and website in this browser for the next time I comment