adventures in bug hunting

If you enjoy this article, subscribe (via RSS or e-mail) and follow me on twitter.

the setup

So, you have some sort of OSX app. Maybe it’s Twitter.app, TweetDeck, or something else that has a secret stored inside the binary. You want to extract this secret, maybe because you want to impersonate the official client of a service or maybe just because you want to see if you can hack the gibson.

I don’t actually really care about Twitter clients, personally. I just wanted to see if I could rip the OAuth token out of some official clients and how long it would take me.

strings, MITM, objdump, gdb, et al.

Not surprisingly, there are many different ways to rip data out of a binary. You can use strings to dump printable strings, play with mitmproxy, or simply reverse engineer the binary by reading objdump (or GDB or whatever) output. I’ve used all of these methods before with great success when attempting to hack the planet, but I had an idea for something a little bit more interesting that can be easily reused.

what happens at a low level

Turns out that, at least at a low level, usually malloc/calloc/whatever and free end up getting called to allocate and deallocate memory regions used by applications. Sure, some apps only use static memory, other apps are built in languages that have a custom allocator, but there are enough apps out there that after you peel away the various candy coated layers of abstraction just end up calling malloc and free provided in the libc on their system provided by the vendor.

So, I assumed that TweetDeck, Twitter.app, and everyone else would be doing something like this underneath all the fancy frameworks:

/* psuedo code, obviously */
buf = malloc(N);
memcpy(buf, "secretkey", strlen("secretkey"));
/* some functions that talk to the api server and do other stuff */
free(buf);

malloc shims

Many malloc implementations provide an interface for the user to create custom shim functions to execute in place of the system-provided malloc/calloc/realloc/free functions. These shim interfaces are useful for many reasons, including but not limited to memory profilers, leak checkers, and other useful debugging tools.

abuse

What if I abuse malloc’s shim interface on OSX and provide a free function that prints the contents of every buffer it is supposed to free before actually freeing it?

shim code

About 50 lines of horrible C code (also available here.):

void (*real_free)(malloc_zone_t *zone, void *ptr);
void (*real_free_definite_size)(malloc_zone_t *zone, void *ptr, size_t size);

void my_free(malloc_zone_t *zone, void *ptr)
{
  char *tmp = ptr;
  char tmp_buf[1025] = {0};
  size_t total = 0;

  /* lol its fine */
  while (*tmp != '\0') {
    tmp_buf[total] = *tmp;
    total++;
    if (total == 1024)
      break;
    tmp++;
  }

  malloc_printf("%s\n", tmp_buf);
  real_free(zone, ptr);
}

void my_free_definite_size(malloc_zone_t *zone, void *ptr, size_t size)
{
  char tmp_buf[1024] = {0};

  if (size < 1024) {
    memcpy(tmp_buf, ptr, size);
  } else {
    memcpy(tmp_buf, ptr, 1023);
  }

  malloc_printf("%s\n", tmp_buf);
  real_free_definite_size(zone, ptr, size);
}

void __attribute__((constructor)) my_init() {
  malloc_zone_t *zone = malloc_default_zone();

  /* save the addresses of the REAL free functions */
  real_free = zone->free;
  real_free_definite_size = zone->free_definite_size;

  /* replace there with my shims */
  zone->free_definite_size = my_free_definite_size;
  zone->free = my_free;
}

insertion

All you have to do is build a dylib of the above C code and insert it like this:

% DYLD_INSERT_LIBRARIES="mallshim.dylib" /Applications/Twitter.app/Contents/MacOS/Twitter

And, boom. A lot of strings will get printed out, so you should use grep to help sift through the output.

output

Let’s see what happens if we insert this little guy into TweetDeck and Twitter.app:

Twitter.app

% DYLD_INSERT_LIBRARIES="mallshim.dylib" /Applications/Twitter.app/Contents/MacOS/Twitter 2>&1| egrep -i "oauth_token|oauth_consumer|oauth_timestamp|oauth_nonce" --color=auto

(I censored out some of the good stuff)

TweetDeck

DYLD_INSERT_LIBRARIES="mallshim.dylib" /Applications/TweetDeck.app/Contents/MacOS/TweetDeck -psn_0_12827707 2>&1 | egrep -i "oauth_token|oauth_consumer|oauth_timestamp|oauth_nonce" --color=auto

arms race

There isn’t much the app can do about this sort of hack. I mean, sure, the app could zero memory the memory before freeing it. But, then I’ll just use GDB or a hexeditor or whatever to disable the call to memcpy. So on and so forth.

If you ship a binary to a person’s computer and that binary has a secret embedded in it, that secret will eventually be discovered.

other apps

What other interesting strings fall out of OSX apps you use everyday?

If you enjoyed this article, subscribe (via RSS or e-mail) and follow me on twitter.

If you enjoy this article, subscribe (via RSS or e-mail) and follow me on twitter.

Computer science

I have a computer science degree, but I like hacking low level systems code and very rarely ever actually do any real computer science. That said, I was reminded about this cool proof by my old college buddy Dan. I decided to share it and possibly motivate myself to dust off some old computer science knowledge that is going to waste as I crawl through the Linux garbage dump. If you’ve never seen it before, maybe this will be interesting.

I’m going to assume you don’t know anything about math, so let’s start with….

Natural numbers

Let’s define the set of natural numbers to be all whole numbers starting from 1. So, the set of natural numbers is: 1, 2, 3, 4, 5, …. off into infinity.

Bijection

A bijection is a mathematical function that maps input values to output values such that all input values map to a unique output value and there are no leftovers.

this is a bijection:

This is not a bijection:

Anything that has a bijection with the natural numbers can be called countably infinite. That’s it. Not too bad.

Cantor’s diagonal argument

So, on to the cool part, thanks to my dogg Cantor.

Imagine you have an infinite sequence called . We can number the elements of with the natural numbers, starting at 1:

Now, imagine that each element of S is an infinitely long binary string. So, for example, maybe your is the infinite string of 0s, like this:

And maybe your is the infinite binary string of alternating 1′s and 0′s, like this:

And so on, until we’ve mapped every natural number to an infinitely long binary string.

Imagine a new string, call it , that we construct by “walking” diagonally down our sequence of infinite binary strings, starting with the first element of and picking the opposite bit, such that the ‘th element of is the reverse of the ‘th element of .

an example

Imagine our set looks like this:

Then our would look like this:

, by construction, can not exist in our infinite sequence . If did exist as (let’s just say) the 3rd element of , then the 3rd bit of and the 3rd bit of would be the same, which is not possible with the construction outlined above.

Thus, is an infinite binary string we have created that exists outside of our infinite sequence . However, we’ve already mapped all the natural numbers to elements in and yet there is at least one more binary string (our ) that doesn’t have a natural number paired with it.

So it follows that the infinite set of all infinite binary strings (which would include, at least, and our ) is larger than the countably infinite set of natural numbers and so we say it is uncountably infinite.

Next time…

I’ll try to show that the real numbers are uncountable and probably regret using a binary string representation to show that it is possible to construct a set that is not countable.

If you enjoyed this article, subscribe (via RSS or e-mail) and follow me on twitter.

If you enjoy this article, subscribe (via RSS or e-mail) and follow me on twitter.

tl;dr

This post describes the relatively undocumented API for debuggers (or other low level programs) that can be used to enumerate the existing threads in a process and receive asynchronous notifications when threads are created or destroyed. This API also provides asynchronous notifications of other interesting thread-related events and feels very similar to the interface exposed by libdl for notifying debuggers when libraries are loaded dynamically at run time.

amd64 and gnu syntax

As usual, everything below refers to amd64 unless otherwise noted. Also, all assembly is in AT&T syntax.

software breakpoints

It’s important to begin first by examining how software breakpoints work. We’ll see shortly why this is important, but for now just trust me.

A debugger sets a software breakpoint by using the ptrace system call to write a special instruction into a target process’ address space. That instruction raises software interrupt #3 which is defined as the Breakpoint Exception in the Intel 64 Architecture Developers Manual.¹ When this interrupt is raised, the processor undergoes a privilege level change and calls a function specified by the kernel to handle the exception.

The exception handler in the kernel executes to deliver the SIGTRAP signal to the process. However, if a debugger is attached to a process with ptrace, all signals are first delivered to the debugger. In the case of SIGTRAP, the debugger can examine the list of breakpoints set by the user and take the appropriate action (draw a UI, update the console, or whatever).

The debugger finishes up by masking this signal from the process it is attached to, preventing that process from being killed (most processes will not have a signal handler for SIGTRAP).

In practice most binaries generated by compilers will not have this instruction; it is up to the debugger to write this instruction into the process’ address space during runtime. If you are so inclined, you can raise interrupt #3 via inline assembly or by calling an assembly stub yourself. Many debuggers will catch this signal and trigger an update of some form in the UI.

All that said, this is what the instruction looks like when disassembled:

int 0x03

You may find it useful to check out an earlier and more in-depth article I wrote a while ago about signal handling.

Enumerating threads when first attaching

When a debugger first attaches to a program the program has an unknown number of threads that must be enumerated. glibc exposes a straightforward API for this called td_ta_thr_iter2 found in glibc at nptl_db/td_ta_thr_iter.c. This function takes a callback as one of its arguments. The callback is called once per thread and is passed a handle to an object describing each thread in the process.

We can see the code in GDB³ which uses this API to hand over a callback which will be hit to enumerate the existing threads in a process:

static int
find_new_threads_once (struct thread_db_info *info, int iteration,
      				   td_err_e *errp)
{
  volatile struct gdb_exception except;
  struct callback_data data;
  td_err_e err = TD_ERR;

  data.info = info;
  data.new_threads = 0;

  TRY_CATCH (except, RETURN_MASK_ERROR)
    {
      /* Iterate over all user-space threads to discover new threads.  */
      err = info->td_ta_thr_iter_p (info->thread_agent,
	   			find_new_threads_callback,
	   			&data,
	   			TD_THR_ANY_STATE,
	   			TD_THR_LOWEST_PRIORITY,
	   			TD_SIGNO_MASK,
	   			TD_THR_ANY_USER_FLAGS);
    }
  /* ... */

That’s pretty straightforward, but there are some hairy race conditions, as we can see in this code snippet from thread_db_find_new_threads_2 which calls find_new_threads_once:

if (until_no_new)
  {
    /* Require 4 successive iterations which do not find any new threads.
 	The 4 is a heuristic: there is an inherent race here, and I have
 	seen that 2 iterations in a row are not always sufficient to
 	"capture" all threads.  */
    for (i = 0, loop = 0; loop < 4; ++i, ++loop)
 	if (find_new_threads_once (info, i, NULL) != 0)
 	  /* Found some new threads.  Restart the loop from beginning.»·*/
 	  loop = -1;
  }

It's fiiiiiiiiiinnnneeee.

Now, on to the more interesting interface that is, IMHO, much less straightforward.

Notification of thread create and destroy

A debugger can also gather thread create and destroy events through an interesting asynchronous interface. Let's go step by step and see how a debugger can listen for create and destroy events.

Enable event notification

First, process wide event notification has to be enabled. This API looks very much like some pieces of the signal API. First we have to create a set of events of we care about (from GDB⁴ ):

static void
enable_thread_event_reporting (void)
{
  td_thr_events_t events;
  td_err_e err;

  /* ... */

  /* Set the process wide mask saying which events we're interested in.  */
  td_event_emptyset (&events);
  td_event_addset (&events, TD_CREATE);

  /* ... */

  td_event_addset (&events, TD_DEATH);
  
  /* NB: the following is just a pointer to the function td_ta_set_event on linux */
  err = info->td_ta_set_event_p (info->thread_agent, &events);

The above code adds TD_CREATE and TD_DEATH to the (empty) set of events that GDB wants to get notifications about. Then the event mask is handed over to glibc with a call to the function td_ta_set_event, which just happens to be stored in a function pointer named td_ta_set_event_p in GDB.

Set asynchronous notification breakpoints

The next step is interesting.

The debugger must use an API to get the addresses of a functions that will be called whenever a thread is created or destroyed. The debugger will then set a software breakpoint at those addresses. When the program creates a thread or a thread is killed the breakpoint will be triggered and the debugger can walk the thread list and update its internal state that describes the threads in the process.

This API is td_ta_event_addr. Let's check out how GDB uses this API. This code is from the same function as above, but happens after the code shown above:

static void
enable_thread_event_reporting (void)
{

	/* ... code above here ... */

	/* Delete previous thread event breakpoints, if any.  */
	remove_thread_event_breakpoints ();
	info->td_create_bp_addr = 0;
	info->td_death_bp_addr = 0;
	
	/* Set up the thread creation event.  */
	err = enable_thread_event (TD_CREATE, &info->td_create_bp_addr);
	
	/* ... */

	/* Set up the thread death event.  */
	err = enable_thread_event (TD_DEATH, &info->td_death_bp_addr);

GDB's helper function enable_thread_event is pretty straightforward:

static td_err_e
enable_thread_event (int event, CORE_ADDR *bp)
{
  td_notify_t notify;
  td_err_e err;
  struct thread_db_info *info;

  info = get_thread_db_info (GET_PID (inferior_ptid));

  /* Access an lwp we know is stopped.  */
  info->proc_handle.ptid = inferior_ptid;

  /* Get the breakpoint address for thread EVENT.  */
  err = info->td_ta_event_addr_p (info->thread_agent, event, &notify);
  /* ... */

  /* Set up the breakpoint.  */
  gdb_assert (exec_bfd);
  (*bp) = (gdbarch_convert_from_func_ptr_addr
		  (target_gdbarch,
		   /* Do proper sign extension for the target.  */
		   (bfd_get_sign_extend_vma (exec_bfd) > 0
		    ? (CORE_ADDR) (intptr_t) notify.u.bptaddr
		    : (CORE_ADDR) (uintptr_t) notify.u.bptaddr),
		   &current_target));

  create_thread_event_breakpoint (target_gdbarch, *bp);

  return TD_OK;
}

So, GDB stores the addresses of the functions that get called on TD_CREATE and TD_DEATH in td_create_bp_addr and td_death_bp_addr, respectively and sets breakpoints on these addresses in enable_thread_event.

Check if the event has been triggered and drain the event queue

Next time a thread is stopped because a breakpoint has been hit, the debugger needs to check if the breakpoint occurred on an address that is associated with the registered events. If so, the thread event queue needs to be drained with a call to td_ta_event_getmsg and the thread's information can be retrieved with a call to td_thr_get_info .

GDB does all this in a function called check_event:

/* Check if PID is currently stopped at the location of a thread event
   breakpoint location.  If it is, read the event message and act upon
   the event.  */

static void
check_event (ptid_t ptid)
{
  /* ... */
  td_event_msg_t msg;
  td_thrinfo_t ti;
  td_err_e err;
  CORE_ADDR stop_pc;
  int loop = 0;
  struct thread_db_info *info;

  info = get_thread_db_info (GET_PID (ptid));

  /* Bail out early if we're not at a thread event breakpoint.  */
  stop_pc =  /* ... */
  if (stop_pc != info->td_create_bp_addr
      && stop_pc != info->td_death_bp_addr)
    return;

  /* Access an lwp we know is stopped.  */
  info->proc_handle.ptid = ptid;

  /* ... */

  /* If we are at a create breakpoint, we do not know what new lwp
     was created and cannot specifically locate the event message for it.
     We have to call td_ta_event_getmsg() to get
     the latest message.  Since we have no way of correlating whether
     the event message we get back corresponds to our breakpoint, we must
     loop and read all event messages, processing them appropriately.
     This guarantees we will process the correct message before continuing
     from the breakpoint.

     Currently, death events are not enabled.  If they are enabled,
     the death event can use the td_thr_event_getmsg() interface to
     get the message specifically for that lwp and avoid looping
     below.  */

  loop = 1;

  do
    {
      err = info->td_ta_event_getmsg_p (info->thread_agent, &msg);
	  /* ... */
	
      err = info->td_thr_get_info_p (msg.th_p, &ti);
	  /* ... */

      ptid = ptid_build (GET_PID (ptid), ti.ti_lid, 0);

      switch (msg.event)
		{
		case TD_CREATE:
		  /* Call attach_thread whether or not we already know about a
		     thread with this thread ID.  */
		  attach_thread (ptid, msg.th_p, &ti);
		
		  break;
		
		case TD_DEATH:
		
		  if (!in_thread_list (ptid))
		    error (_("Spurious thread death event."));
		
		  detach_thread (ptid);
		
		  break;
		
		default:
		  error (_("Spurious thread event."));
		}
    }
  while (loop);
}

And that is how GDB finds out about existing threads and gets notified about new threads being created or existing threads dying. This asynchronous breakpoint interface is very similar to the interface exposed by libdl that I described briefly toward the end of a blog post I wrote a while ago.

Notifications for other interesting events

Other interesting events are supported by the API but are currently not implemented in glibc, but a motivated programmer could build a shim which implements these events. Doing so would allow you to build some very interesting visualization applications for lock contention and scheduling:

/* Events reportable by the thread implementation.  */
typedef enum
{
  TD_ALL_EVENTS,			/* Pseudo-event number.  */
  TD_EVENT_NONE = TD_ALL_EVENTS, 	/* Depends on context.  */
  TD_READY,				/* Is executable now. */
  TD_SLEEP,				/* Blocked in a synchronization obj.  */
  TD_SWITCHTO,				/* Now assigned to a process.  */
  TD_SWITCHFROM,			/* Not anymore assigned to a process.  */
  TD_LOCK_TRY,				/* Trying to get an unavailable lock.  */
  TD_CATCHSIG,				/* Signal posted to the thread.  */
  TD_IDLE,				/* Process getting idle.  */
  TD_CREATE,				/* New thread created.  */
  TD_DEATH,				/* Thread terminated.  */
  TD_PREEMPT,				/* Preempted.  */
  TD_PRI_INHERIT,			/* Inherited elevated priority.  */
  TD_REAP,				/* Reaped.  */
  TD_CONCURRENCY,			/* Number of processes changing.  */
  TD_TIMEOUT,				/* Conditional variable wait timed out.  */
  TD_MIN_EVENT_NUM = TD_READY,
  TD_MAX_EVENT_NUM = TD_TIMEOUT,
  TD_EVENTS_ENABLE = 31		/* Event reporting enabled.  */
} td_event_e;

Take my shovel and flashlight and go look around

Check the reference section below which has links to some of the source file mentioned above. Also, be sure to check out the header file:

/usr/include/thread_db.h

That header lists the exported functions from glibc as well as the various flags and types necessary for interacting with this interface.

Conclusion

• Debuggers have really interesting ways of interacting with lower level system libraries.
• Comments found tucked away in these pits of despair are pretty amazing.
• Don't be scared. Grab a shovel and see what other interesting things you can dig up in glibc or elsewhere.

If you enjoyed this article, subscribe (via RSS or e-mail) and follow me on twitter.

References

1. Intel 64 Architecture Developers Manual Volume 3A 6-31 [↩]
2. glibc/nptl_db/td_ta_thr_iter.c [↩]
3. gdb/linux-thread-db.c [↩]
4. gdb/linux-thread-db.c [↩]

If you enjoy this article, subscribe (via RSS or e-mail) and follow me on twitter.

tl;dr

This post is going to explain a serious design flaw of the object system used in MRI/REE/YARV. This flaw causes seemingly random segfaults and other hard to track corruption. One popular incarnation of this bug is the “rake aborted! not in gzip format.”

theme song

This blog post was inspired by one of my favorite Papoose verses. If you don’t listen to this while reading, you probably won’t understand what I’m talking about: get in the zone.

rake aborted! not in gzip format
[BUG] Segmentation fault

If you’ve seen either of these error messages you are hitting a fundamental flaw of the object model in MRI/YARV. An example of a fix for a single instance of this bug can be seen in this patch. Let’s examine this specific patch so that we can gain some understanding of the general case.

FACT: What you are about to read is absolutely not a compiler bug.

A small, but important piece of background information

The amd64 ABI¹ states that some registers are caller saved, while others are callee saved. In particular, the register rax is caller saved. The callee will overwrite the value in this register to store its return value for the caller so if the caller cares about what is stored in this register, it must be copied prior to a function call.

stare into the abyss part 1

Let’s look at the C code for gzfile_read_raw_ensure WITHOUT the fix from above:

#define zstream_append_input2(z,v)\
    zstream_append_input((z), (Bytef*)RSTRING_PTR(v), RSTRING_LEN(v))

static int
gzfile_read_raw_ensure(struct gzfile *gz, int size)
{
    VALUE str;

    while (NIL_P(gz->z.input) || RSTRING_LEN(gz->z.input) < size) {
	str = gzfile_read_raw(gz);
	if (NIL_P(str)) return Qfalse;
	zstream_append_input2(&gz->z, str);
    }
    return Qtrue;
}

It looks relatively sane at first glance, but to understand this bug we’ll need to examine the assembly generated for this thing. I’m going to rearrange the assembly a bit to make it easier to follow and add few comments a long the way.

First, the code begins by setting the stage:

  push   %rbp
  movslq %esi,%rbp    # sign extend "size" into rbp
  push   %rbx
  mov    %rdi,%rbx    # rbx = gz
  sub    $0x8,%rsp    # make room on the stack for "str"

The above is pretty basic. It is your typical amd64 prologue. After things are all setup, it is time to enter into the while loop in the C code above:

  jmp    1180  # JUMP IN to the loop

Next comes the NIL_P(gz->z.input) portion of the while-loop condition:

  mov    0x18(%rbx),%rax    # rax = gz->z.input
  cmp    $0x4,%rax          # in Ruby, nil is represented as 4.
  je     1190 [gzfile_read_raw_ensure+0x30]  # if gz->z.input is nil, enter the loop

Now the RSTRING_LEN(gz->z.input) < size portion:

  cmp    %rbp,0x10(%rax)        # compare size and gz->z.input->len
  jge    11b0 [gzfile_read_raw_ensure+0x50]  # jump out of loop
                                             # if  gz->z.input->len is >= size

Next comes the call to gzfile_read_raw and the NIL_P(str) check. If this check fails, the code just falls through and exits the loop:

 mov    %rbx,%rdi            # rdi = gz, rdi holds the first argument to a function.
 callq  1090 [gzfile_read_raw]  # call gzfile_read_raw
 cmp    $0x4,%rax   # compare return value (%rax) to nil
 jne    1170 [gzfile_read_raw_ensure+0x10] # if it is NOT nil jump to the good stuff

The return value of gzfile_read_raw_ensure (an address of a ruby object) is stored in rax.

And finally, the good stuff. The call to zstream_append_input:

  mov    0x10(%rax),%rdx # RSTRING_LEN(v) as 3rd arg
  mov    0x18(%rax),%rsi # RSTRING_PTR(v) as 2nd arg
  mov    %rbx,%rdi       # set gz->z as the 1st arg
  callq  10e0 [zstream_append_input]  # let it rip

Note that the arguments to zstream_append_input are moved into registers by offsetting from rax and that when the call to zstream_append occurs, the ruby object returned from gzfile_read_raw_ensure is still stored in rax and not written to it's slot on the stack because the extra write is unnecessary.

stare into the abyss part 2

Aright, so the patch changes the zstream_append_input2 macro to this:

#define zstream_append_input2(z,v)\
    RB_GC_GUARD(v),\
    zstream_append_input((z), (Bytef*)RSTRING_PTR(v), RSTRING_LEN(v))

And, RB_GC_GUARD is defined as:

#define RB_GC_GUARD_PTR(ptr) \
    __extension__ ({volatile VALUE *rb_gc_guarded_ptr = (ptr); rb_gc_guarded_ptr;})

#define RB_GC_GUARD(v) (*RB_GC_GUARD_PTR(&(v)))

That code is just a hack to mark the memory location holding v with the volatile type qualifier. This tells the compiler that memory backing v acts in ways that the compiler is too stupid to understand, so the compiler must ensure that reads and writes to this location are not optimized out.

A common usage of this qualifier is for memory mapped registers. Reads from memory mapped registers should not be optimized away since a hardware device may update the value stored at that location. The compiler wouldn't know when these updates could happen so it must make sure to re-read the value from this memory location when it is needed. Similarly, writes to memory mapped registers may modify the state of a hardware device and should not be optimized away.

Most of the code generated with the patch applied is the same as without except for a few slight differences before zstream_append_input is called. Let's take a look:

  mov    %rax,-0x18(%rbp)    # write str to the stack 
  mov    -0x18(%rbp),%rax    # read the value in str back to rax
  mov    0x10(%rcx),%rdx      # RSTRING_LEN(v)
  mov    0x18(%rcx),%rsi       # RSTRING_PTR(v)
  mov    %rbx,%rdi                # z
  callq  1f60 [_zstream_append_input]

The key difference is that the return value of gz_file_read_raw is written back to it's memory location (which, in this case, happens to be on the stack and is called str).

the bug

The bug is triggered because:

1. The address of the ruby object str is stored in a caller saved register, rax.
2. The callee (zstream_append_input) does not save the value of rax (it is not required to) and rax is overwritten in the function, leaving no references to the ruby object returned by gzfile_read_raw.
3. The callee (zstream_append_input) eventually calls rb_newobj. rb_newobj may trigger a GC run, if there are no available objects on the freelist.
4. The GC run finds the object returned by gzfile_read_raw but sees no references to it and frees the memory associated with it.
5. The freed object is used as it were it were valid, and memory corruption occurs causing the VM to explode.

The patch prevents this bug from happening because:

1. The address of the ruby object str is stored in a caller saved register, rax.
2. The volatile type qualifier causes the compiler to generate code which writes the return value back into it's memory location on the stack.
3. The callee (zstream_append_input) eventually calls rb_newobj. rb_newobj may trigger a GC run, if there are no available objects on the freelist.
4. The GC run finds the object returned by gzfile_read_raw and finds a reference to it and therefore does not free it.
5. Everyone is happy.

The general case

Given valid C code, gcc will generate machine instructions that correctly do what you want. Of course, there are bugs in gcc just like any other piece of software. The problem in this case is not gcc. The problem is that the object and garbage collection implementations in REE/MRI/YARV are not valid C code, so it is not possible for gcc to generate machine instructions that do the right thing. In other words, Ruby's object and GC implementations are breaking their contract with gcc.

The end result is the need for shit like RB_GC_GUARD in REE/MRI/YARV and also in Ruby gems to selectively paper over valid gcc optimizations. Having an API that might cause the Ruby VM to fucking explode unless you proactively mark things with RB_GC_GUARD is not on the path of least resistance toward building a maintainable, safe, and performant system. Very few people out there know that the volatile type qualifier exists, let alone what it does. Essentially, this means that authors of Ruby gems must understand how GC works in the VM to prevent their gems from causing GC to break the universe.

That is fucking beyond stupid.

How to detect this bug class

This could be detected by building a simple static analysis tool. You won't catch 100% of cases, and you will definitely have false positives, but it is better than nothing. Something like this should work:

1. Build a call digraph of the VM and/or the set of gems you care about.
2. Find all paths leading to the rb_newobj sink.
3. Find all paths which call rb_newobj, but do not save rax prior to making another function call which is also on a path to rb_newobj.
4. The functions found are very likely to be causing corruption. A human will need to examine the found cases to weed out false positives and to fix the code.

If you have found yourself wondering who the fuck would write such a test? it is important for you to note that rtld in Linux does not save the SSE registers (which are supposed to be caller saved) prior to entering the fixup function, however to ensure that such an optimization does not cause the fucking universe to come crashing down, a test ships with the code to run objdump after building the binary. The objdump output is then grepped for any instructions which might modify the SSE registers. As long as no one touches the SSE registers, there is no need to save and restore them.

If Ruby's object and GC subsystems want to prevent the universe from exploding, it must supply an equivalent test to ensure that corruption is impossible.

Conclusion

• MRI/YARV/REE are inherently fatally flawed.
• I'm never writing another Ruby-related blog post.
• I'm not a Ruby programmer.

No comments

I'm taking a page from the book of coda and disabling comments. If you got something to say, write a blog post.

If you enjoyed this article, subscribe (via RSS or e-mail) and follow me on twitter.

References

1. System V Application Binary Interface: AMD64 Architecture Processor Supplement [↩]