Holodeck

Since I interned at M.I.T Lincoln Lab in the summer of 2016, I’ve been working on an extension project of the work I did there. While it’s still not finished, it’s a pretty big chunk of work that deserves to be on this website somewhere :)

In short, Holodeck is a platform to help in the process of “rehosting” embedded devices inside QEMU.

Its main selling points are:

1. Automatically detecting the type of device being talked to over MMIO during kernel initialization
2. Providing a nice framework for researchers to augment it’s automated capabilities and implement full hardware definitions

Ok so that’s a lot of words. Breaking it down:

1. Device Detection

When any kernel starts up, it communicates with devices that it knows should exist according to the kernel build configuration (and/or arguments passed to it at startup). These are typically very low-level things like the interrupt controller, UART/serial comms, timers, power management, etc.

In the case of Linux, these devices are defined in a Device Tree Blob (DTB) and/or in baked-in kernel modules. Either way, probing functions end up getting called which look to see if the device(s) are online, and may then kick off an init routine to bring up the device(s) and register with the appropriate kernel subsystem.

Side-stepping for a second, Linux (and all other generic/cross-platform kernels) have an interesting principle which we’ll use here in a minute to our advantage. Low-level common subsystems (like UART) often have an hour-glass like shape to their call traces. A diagram should help explain:

-------   <-- Many callers
\     /
 \   /
  \ /
   |  <-- "Funnels down" to a single callsite
  / \
 /   \
/     \
-------  <-- Hardware-specific routines

Take for example UART. Most interactions with the UART don’t even say they’re going to a UART (printk usually ends up going out the UART during early boot). This (+other functions) go through a series of reductions, eventually leading to a single function (probably uart_write), which then dispatches out to device specific routines.

Now, back to Holodeck. We use this design “feature” by finding and looking for the functions in the middle of the hour-glass - the lowest-level yet still device-agnostic function that does something we want to hook. Then, when a new MMIO region is accessed, we go through the callstack looking for one of these functions. If we find one, we can infer the type of device that the memory region belongs to.

As a concrete example, uart_register_driver is a function we look for in Holodeck. Whenever we see accesses to a region of memory not marked previously, we look through the kernel callstack and if we see uart_register_driver we infer that the memory region is MMIO for a UART device.

Device Register Detection

With device type data, we can implement generic patterns to try and identify what each address does in the device’s memory region. For example, if we see a bunch of read accesses in a row before anything else has happened in that region, we might be able to guess that the address being read is some kind of status, and the kernel is spin-looping on a bit to flip to denote that the device is online. We can then try different bit patterns to identify exactly what bit denotes the device being ready, or if we fail to find a single bit, we could turn to a symbolic execution engine to find a satisfying value that would let the kernel continue.

When all else fails

At the end of the day, Holodeck’s main goal is to get the device emulated in QEMU as much as it can. This means we need to get as far into the kernel as possible. So if we just cannot find a way to get past a specific function, we NOP it out, and continue walking up the callstack NOPing things out until something works.

While crude, this is super effective and surprisingly doesn’t break things often… until it decides to patch out panic() :)

2. Being Useful

At the end of the day, the methods described above won’t be able to find everything, and definitely can’t figure out what unknown things are doing like a reverse-engineer can. Because of this, Holodeck also tries to make it easier to manually debug the boot process by making all of the data it collects easily available in Python objects.

And it exposes a lot of data.

You can get the complete kernel call stack during any given memory access, ask Holodeck to try responding to a memory read in a specific way to see what happens, etc. etc.

You can even do tests in parallel!

Conclusion

Holodeck still isn’t ready for release, but I’m hoping to work on it more this coming fall and get a paper out of it. Either way, the code will be released by winter, paper or not.