*36c3 prerol music*
Herald: So, the next talk for this afternoon is about high speed binary
fuzzing. We have two researchers that will be presenting the product of their latest
work, which is a framework for static binary rewriting. Our speakers are—the
first one is a computer science master's student at EPFL and the second one is a
security researcher and assistant professor at EPFL. Please give a big round
of applause to Nspace and gannimo.
*Applause*
gannimo (Mathias Payer): Thanks for the introduction. It's a pleasure to be here,
as always. We're going to talk about different ways to speed up your fuzzing
and to find different kinds of vulnerabilities or to tweak your binaries
in somewhat unintended ways. I'm Mathias Payer or I go by gannimo on Twitter and I
am an assistant professor at EPFL working on different forms of software security:
fuzzing sanitization, but also different kinds of mitigations. And Matteo over
there is working on his master's thesis on different forms of binary rewriting for
the kernel. And today we're going to take you on a journey on how to actually
develop very fast and very efficient binary rewriting mechanisms that allow you
to do unintended modifications to the binaries and allow you to explore
different kinds of unintended features in binaries. So about this talk. What we
discovered or the reason why we set out on this journey was that fuzzing binaries is
really, really hard. There's very few tools in user space. There's—it's
extremely hard to set it up and it's extremely hard to set it up in a
performant way. The setup is complex. You have to compile different tools. You have
to modify it. And the results are not really that satisfactory. As soon as you
move to the kernel, fuzzing binaries in a kernel is even harder. There's no tooling
whatsoever, there's very few users actually working with binary code in the
kernel or modifying binary code, and it's just a nightmare to work with. So what we
are presenting today is a new approach that allows you to instrument any form of
binary code or modern binary code based on static rewriting, which gives you full
native performance. You only pay for the instrumentation that you add, and you can
do very heavyweight transformations on top of it. The picture, if you look at the
modern system, let's say we are looking at a modern setup. Let's say you're looking
at cat pictures in your browser: Chrome plus the kernel plus the libc plus the
graphical user interface together clog up at about 100 million lines of code.
Instrumenting all of this for some form of security analysis is a nightmare,
especially along this large stack of software. There's quite a bit of different
compilers involved. There's different linkers. It may be compiled on a different
system, with different settings and so on. And then getting your instrumentation
across all of this is pretty much impossible and extremely hard to work
with. And we want to enable you to select those different parts that you're actually
interested in. Modify those and then focus your fuzzing or analysis approaches on
those small subsets of the code, giving you a much better and stronger capability
to test the systems that you're, or those parts of the system that you're really,
really interested in. Who's worked on fuzzing before? Quick show of hands. Wow,
that's a bunch of you. Do you use AFL? Yeah, most of you, AFL. Libfuzzer? Cool,
about 10, 15 percent libfuzzer, 30 percent fuzzing, and AFL. There's a quite good
knowledge of fuzzing, so I'm not going to spend too much time on fuzzing, but for
those that haven't really run their fuzzing campaigns yet, it's a very simple
software testing technique. You're effectively taking a binary, let's say
Chrome, as a target and you're running this in some form of execution
environment. And fuzzing then consists of some form of input generation that creates
new test cases, throws them at your program and sees—and checks what is
happening with your program. And either everything is OK, and your code is being
executed, and your input—the program terminates, everything is fine, or you
have a bug report. If you have a bug report, you can use this. Find the
vulnerability, maybe develop a PoC and then come up with some form of either
exploit or patch or anything else. Right. So this is pretty much fuzzing in a in a
nutshell. How do you get fuzzing to be effective? How can you cover large source
bases, complex code, and complex environment? Well, there's a couple of
simple steps that you can take. And let's walk quickly through effective fuzzing
101. Well, first, you want to be able to create test cases that actually trigger
bugs. And this is a very, very complicated, complicated part. And we need
to have some notion of the inputs that a program accepts. And we need to have some
notion of how we can explore different parts of the program, right? Different
parts of functionality. Well, on one hand, we could have a developer write all the
test cases by hand, but this would be kind of boring. It would also require a lot of
human effort in creating these different inputs and so on. So coverage guided
fuzzing has evolved as a very simple way to guide the fuzzing process, leveraging
the information on which parts of the code have been executed by simply tracing the
individual path through the program based on the execution flow. So we can—the
fuzzer can use this feedback to then modify the inputs that are being thrown at
the fuzzing process. The second step is the fuzzer must be able to detect bugs. If
you've ever looked at a memory corruption, if you're just writing one byte after the
end of a buffer, it's highly likely that your software is not going to crash. But
it's still a bug, and it may still be exploitable based on the underlying
conditions. So we want to be able to detect violations as soon as they happen,
for example, based on on some form of sanitization that we add, some form of
instrumentation that we add to the to the binary, that then tells us, hey, there's a
violation of the memory safety property, and we terminate the application right
away as a feedback to the fuzzer. Third, but the—and last but not least: Speed is
key, right? For if you're running a fuzzing campaign, you have a fixed
resource budget. You have a couple of cores, and you want to run for 24 hours,
48 hours, a couple of days. But in any way, whatever your constraints are, you
have a fixed amount of instructions that you can actually execute. And you have to
decide, am I spending my instructions on generating new inputs, tracking
constraints, finding bugs, running sanitization or executing the program? And
you need to find a balance between all of them, as it is a zero sum game. You have a
fixed amount of resources and you're trying to make the best with these
resources. So any overhead is slowing you down. And again, this becomes an
optimization problem. How can you most effectively use the resources that you
have available? As we are fuzzing with source code, it's quite easy to actually
leverage existing mechanisms, and we add all that instrumentation at compile time.
We take source code, we pipe it through the compiler and modern compiler
platforms, allow you to instrument and add little code snippets during the
compilation process that then carry out all these tasks that are useful for
fuzzing. For example, modern compilers can add short snippets of code for coverage
tracking that will record which parts of the code that you have executed, or for
sanitization which record and check every single memory access if it is safe or not.
And then when you're running the instrumented binary, everything is fine
and you can detect the policy violations as you go along. Now if you would have
source code for everything, this would be amazing. But it's often not the case,
right? We may be able on Linux to cover a large part of the protocol stack by
focusing only on source-code-based approaches. But there may be applications
where no source code is available. If we move to Android or other mobile systems,
there's many drivers that are not available as open source or just available
as binary blobs, or the full software stack may be closed-source and we only get
the binaries. And we still want to find vulnerabilities in these complex software
stacks that span hundreds of millions of lines of code in a very efficient way. The
only solution to cover this part of massive code base is to actually rewrite
and focus on binaries. A very simple approach could be black box fuzzing, but
this is—this doesn't really get you anywhere because you don't get any
feedback; you don't get any information if you're triggering bugs. So one simple
approach, and this is the approach that is most dominantly used today, is to rewrite
the program or the binary dynamically. So you're taking the binary and during
execution you use some form of dynamic binary instrumentation based on Pin, angr,
or some other binary rewriting tool and translate the targeted runtime, adding
this binary instrumentation on top of it as you're executing it. It's simple, it's
straightforward, but it comes at a terrible performance cost of ten to a
hundred x slow down, which is not really effective. And you're spending all your
cores and your cycles on just executing the binary instrumentation. So we don't
really want to do this and we want to have something that's more effective than that.
So what we are focusing on is to do static rewriting. It involves a much more complex
analysis as we are rewriting the binary before it is being executed, and we have
to recover all of the control flow, all of the different mechanisms, but it results
in a much better performance. And we can get more bang for our buck. So why is
static rewriting so challenging? Well, first, simply adding code will break the
target. So if you are disassembling this piece of code here, which is a simple loop
that loads data, decrements the registers, and then jumps if you're not at the end of
the array and keeps iterating through this array. Now, as you look at the jump-not-
zero instruction, the last instruction of the snippet, it is a relative offset. So
it jumps backward seven bytes. Which is nice if you just execute the code as is.
But as soon as you want to insert new code, you change the offsets in the
program, and you're modifying all these different offsets. And simply adding new
code somewhere in between will break the target. So a core feature that we need to
enforce, or core property that we need to enforce, is that we must find all the
references and properly adjust them, both relative offsets and absolute offsets as
well. Getting a single one wrong will break everything. What makes this problem
really, really hard is that if you're looking at the binary, a byte is a byte,
right? There's no way for us to distinguish between scalars and
references, and in fact they are indistinguishable. Getting a single
reference wrong breaks the target and would introduce arbitrary crashes. So we
have to come up with ways that allow us to distinguish between the two. So for
example, if you have this code here, it takes a value and stores it somewhere on
the stack. This could come from two different kind of high-level constructs.
On one hand, it could be taking the address of a function and storing this
function address somewhere and in a stack variable. Or it could be just storing a
scalar in a stack variable. And these two are indistinguishable, and rewriting them,
as soon as we add new code, the offsets will change. If it is a function, we would
have to modify the value; if it is a scalar, we have to keep the same value. So
how can we come up with a way that allows us to distinguish between the two and
rewrite binaries by recovering this missing information? So let us take—let me
take you or let us take you on a journey towards instrumenting binaries in the
kernel. This is what we aim for. We'll start with the simple case of
instrumenting binaries in user land, talk about different kinds of coverage guided
fuzzing and what kind of instrumentation we can add, what kind of sanitization we
can add, and then focusing on taking it all together and applying it to kernel
binaries to see what what will fall out of it. Let's start with instrumenting
binaries first. I will now talk a little bit about RetroWrite, our mechanism and
our tool that enables static binary instrumentation by symbolizing existing
binaries. So we recover the information and we translate relative offsets and
absolute offsets into actual labels that are added to the assembly file. The
instrumentation can then work on the recovered assembly file, which can then be
reassembled into a binary that can then be executed for fuzzing. We implement
coverage tracking and binary address sanitizer on top of this, leveraging
abstraction as we go forward. The key to enabling this kind of binary rewriting is
position-independent code. And position- independent code has become the de-facto
standard for any code that is being executed on a modern system. And it
effectively says that it is code that can be loaded at any arbitrary address in your
address space as you are executing binaries. It is essential and a
requirement if you want to have address space layout randomization or if you want
to use shared libraries, which de facto you want to use in all these different
systems. So since a couple of years, all the code that you're executing on your
phones, on your desktops, on your laptops is position-independent code. And the idea
between the position-independent code is that you can load it anywhere in your
address space and you can therefore not use any hard-coded static addresses and
you have to inform the system of relocations or pick relative
addresses—to—on how the system can relocate these different mechanisms. On
x86_64, position-independent code leverages addressing that is relative to
the instruction pointer. So for example, it uses the current instruction pointer
and then a relative offset to that instruction pointer to reference global
variables, other functions and so on. And this is a very easy way for us to
distinguish references from constants, especially in PIE binaries. If it is RIP-
relative, it is a reference; everything else is a constant. And we can build our
translation algorithm and our translation mechanism based on this fundamental
finding to remove any form of heuristic that is needed by focusing especially on
position-independent code. So we're supporting position-independent code; we
are—we don't support non-position- independent code, but we give you the
guarantee that we can rewrite all the different code that is out there. So
symbolization works as follows: If you have the little bit of code on the lower
right, symbolization replaces first all the references with assembler labels. So
look at the call instruction and the jump- not-zero instruction; the call instruction
references an absolute address and the jump-not-zero instruction jumps backward
relative 15 bytes. So by focusing on these relative jumps and calls, we can replace
them with actual labels and rewrite the binary as follows: so we're calling a
function, replacing it with the actual label, and for the jump-not-zero we are
inserting an actual label in the assembly code and adding a backward reference. For
PC-relative addresses, for example the data load, we can then replace it with the
name of the actual data that we have recovered, and we can then add all the
different relocations and use that as auxiliary information on top of it. After
these three steps, we can insert any new code in between, and can therefore add
different forms of instrumentations or run some more higher-level analysis on top of
it, and then reassemble the file for fuzzing or coverage-guided tracking,
address sanitization or whatever else you want to do. I will now hand over to
Matteo, who will cover coverage-guided fuzzing and sanitization and then
instrumenting the binaries in the kernel. Go ahead.
Nspace (Matteo Rizzo): So, now that we have this really nice framework to rewrite
binaries, one of the things that we want to add to actually get the fuzzing is this
coverage-tracking instrumentation. So coverage-guided fuzzing is a way, a
method, for—to let the fuzzer discover interesting inputs, an interesting path to
the target by itself. So the basic idea is that the fuzzer will track coverage—the
parts of the programs that are covered by different inputs by inserting some kind of
instrumentation. So, for example, here we have this target program that checks if
the input contains the string "PNG" at the beginning, and if it does, then it does
something interesting, otherwise it just bails out and fails. So if we track the
part of the programs that each input executes, the fuzzer can figure out that
an input that contains "P" will have discovered a different path through the
program than input that doesn't contain it. And then so on it can, one byte at a
time, discover that this program expects this magic sequence "PNG" at the start of
the input. So the way that the fuzzer does this is that every time a new input
discovers a new path though the target, it is considered interesting and added to a
corpus of interesting inputs. And every time the fuzzer needs to generate a new
input, it will select something from the corpus, mutate it randomly, and then use
it as the new input. So this is like a—this is, like, conceptually pretty
simple, but in practice it works really well and it really lets the fuzzer
discover the format that the target expects in an unsupervised way. So as an
example, this is an experiment that was run by the author of AFL—AFL is the fuzzer
that sort of popularized this technique—where he was fuzzing a JPEG-
parsing library, starting from a corpus that only contained the string "hello". So
now clearly "hello" is not a valid JPEG image and so—but still, like, the fuzzer
was still able to find—to discover the correct format. So after a while it
started generating some grayscale images, on the top left, and as it generated more
and more inputs, it started generating more interesting images, such as some
grayscale gradients, and later on even some color images. So as you can see, this
really works, and it allows us to fuzz a program without really teaching the fuzzer
how the input should look like. So that's it for coverage-guided fuzzing. Now we'll
talk a bit about sanitizations. As a reminder, the core idea behind
sanitization is that just looking for crashes is likely to miss some of the
bugs. So, for example, if you have this out-of-bounds one-byte read, that will
probably not crash the target, but you would still like to catch it because it
could be used for an info leak, for example. So one of the most popular
sanitizers is Address Sanitizer. So Address Sanitizer will instrument all the
memory accesses in your program and check for memory corruption, which—so, memory
corruption is a pretty dangerous class of bugs that unfortunately still plagues C
and C++ programs and unsafe languages in general. And ASan tries to catch it by
instrumenting the target. It is very popular; it has been used to find
thousands of bugs in complex software like Chrome and Linux, and even though it has,
like, a bit of a slowdown—like about 2x—it is still really popular because it lets
you find many, many more bugs. So how does it work? The basic idea is that ASan will
insert some special regions of memory called 'red zones' around every object in
memory. So we have a small example here where we declare a 4-byte array on the
stack. So ASan will allocate the array "buf" and then add a red zone before it
and a red zone after it. Whenever the program accesses the red zones, it is
terminated with a security violation. So the instrumentation just prints a bug
report and then crashes the target. This is very useful for detecting, for example,
buffer overflows or underflows and many other kinds of bugs such as use-after-free
and so on. So, as an example here, we are trying to copy 5 bytes into a 4-byte
buffer, and ASan will check each of the accesses one by one. And when it sees that
the last byte writes to a red zone, it detects the violation and crashes the
program. So this is good for us because this bug might have not been found by
simply looking for crashes, but it's definitely found if we use ASan. So this
is something we want for fuzzing. So now that we've covered—briefly covered ASan we
can talk about instrumenting binaries in the kernel. So Mathias left us with
RetroWrite, and with RetroWrite we can add both coverage tracking and ASan to
binaries. So the simple—it's a really simple idea: now that we can rewrite this
binary and add instructions wherever we want, we can implement both coverage
tracking and ASan. In order to implement coverage tracking, we simply have to
identify the start of every basic block and add a little piece of instrumentation
at the start of the basic block that tells the fuzzer 'hey, we've reached this part
of the program'—'hey, we've reached this other part of the program'. Then the
fuzzer can figure out whether that's a new part or not. ASan is also, like, you know,
it's also somewhat—it can also be implemented in this way by finding all
memory accesses, and then linking with libASan. libASan is a sort of runtime for
ASan that takes care of inserting the red zones and instrument—and adding, you know,
like, keeping around all the metadata that ASan needs to know where the red zones
are, and detecting whether a memory access is invalid. So, how can we apply all of
this in the kernel? Well, first of all, fuzzing the kernel is not as easy as
fuzzing some userspace program. There's some issues here. So first of all, there's
crash handling. So whenever you're fuzzing a userspace program, you expect crashes,
well, because that's what we're after. And if a userspace program crashes, then the
US simply terminates the crash gracefully. And so the fuzzer can detect this, and
save the input as a crashing input, and so on. And this is all fine. But when you're
fuzzing the kernel, so—if you were fuzzing the kernel of the machine that you were
using for fuzzing, after a while, the machine would just go down. Because, after
all, the kernel runs the machine, and if it starts misbehaving, then all of it can
go wrong. And more importantly, you can lose your crashes, because the if the
machine crashes, then the state of the fuzzer is lost and you have no idea what
your crashing input was. So what most kernel fuzzers have to do is that they
resort to some kind of VM to keep the system stable. So they fuzz the kernel in
a VM and then run the fuzzing agent outside the VM. On top of that is tooling.
So, if you want to fuzz a user space program, you can just download AFL or use
libfuzzer; there's plenty of tutorials online, it's really easy to set up and
just, like—compile your program, you start fuzzing and you're good to go. If you want
to fuzz the kernel, it's already much more complicated. So, for example, if you want
to fuzz Linux with, say, syzkaller, which is a popular kernel fuzzer, you have to
compile the kernel, you have to use a special config that supports syzkaller,
you have way less guides available than for userspace fuzzing, and in general it's
just much more complex and less intuitive than just fuzzing userspace. And lastly,
we have the issue of determinism. So in general, if you have a single threaded
userspace program, unless it uses some kind of random number generator, it is
more or less deterministic. There's nothing that affects the execution of the
program. But—and this is really nice if you want to try to reproduce a test case,
because if you have a non-deterministic test case, then it's really hard to know
whether this is really a crash or if it's just something that you should ignore, and
in the kernel this is even harder, because you don't only have concurrency, like
multi-processing, you also have interrupts. So interrupts can happen at any time, and
if one time you got an interrupt while executing your test case and the second
time you didn't, then maybe it only crashes one time - you don't really know,
it's not pretty. And so again, we have several approaches to fuzzing
binaries in the kernel. First one is to do black box fuzzing. We don't really
like this because it doesn't find much, especially in something complex
like a kernel. Approach 1 is to use dynamic translation,
so, use something like QEMU or—you name it. This works, and
people have used it successfully; the problem is that it is really, really,
really slow. Like, we're talking about 10x-plus overhead. And as we said before,
the more iterations, the more test cases you can execute in the same amount of
time, the better, because you find more bugs. And on top of that, there's no
currently available sanitizer for kernel binaries that works—is based on
this approach. So in userspace you have something like valgrind; in the kernel,
you don't have anything, at least that we know of. There is another approach, which
is to use Intel Processor Trace. This has been, like—there's been some research
papers on this recently, and this is nice because it allows you to collect coverage
at nearly zero overhead. It's, like, really fast, but the problem is that it
requires hardware support, so it requires a fairly new x86 CPU, and if you want to
fuzz something on ARM, say, like, your Android driver, or if you want to use an
older CPU, then you're out of luck. And what's worse, you cannot really use it for
sanitization, or at least not the kind of sanitization that ASan does, because it
just traces the execution; it doesn't allow you to do checks on memory accesses.
So Approach 3, which is what we will use, is static rewriting. So, we had this very
nice framework for rewriting userspace binaries, and then we asked ourselves, can
we make this work in the kernel? So we took the system, the original RetroWrite,
we modified it, we implemented support for Linux modules, and... it works! So we have
implemented it—we have used it to fuzz some kernel modules, and it really shows
that this approach doesn't only work for userspace; it can also be applied to the
kernel. So as for some implementation, the nice thing about kernel modules is that
they're always position independent. So you cannot have position—like, fixed-
position kernel modules because Linux just doesn't allow it. So we sort of get that
for free, which is nice. And Linux modules are also a special class of ELF files,
which means that the format is—even though it's not the same as userspace binaries,
it's still somewhat similar, so we didn't have to change the symbolizer that much,
which is also nice. And we implemented symbolization with this, and we used it to
implement both code coverage and binary ASan for kernel binary modules. So for
coverage: The idea behind the whole RetroWrite project was that we wanted to
integrate with existing tools. So existing fuzzing tools. We didn't want to force our
users to write their own fuzzer that is compatible with RetroWrite. So for—in
userspace we had AFL-style coverage tracking, and binary ASan which is
compatible with source-based ASan, and we wanted to follow the same principle in the
kernel. So it turns out that Linux has this built-in coverage-tracking framework
called kCov that is used by several popular kernel fuzzers like syzkaller, and
we wanted to use it ourselves. So we designed our coverage instrumentation so
that it integrates with kCov. The downside is that you need to compile the kernel
with kCov, but then again, Linux is open source, so you can sort of always do that;
the kernel usually—it's usually not the kernel, it is a binary blob, but it's
usually only the modules. So that's just still fine. And the way you do this is—the
way you implement kCov for binary modules is that you just have to find the start of
every basic block, and add a call to some function that then stores the collected
coverage. So here's an example: we have a short snippet of code with three basic
blocks, and all we have to do is add a call to "trace_pc" to the start of the
basic block. "trace_pc" is a function that is part of the main kernel image that then
collects this coverage and makes it available to a userspace fuzzing agent. So
this is all really easy and it works. And let's now see how we implemented binary
ASan. So as I mentioned before, when we instrument the program with binary ASan in
userspace we link with libASan, which takes care of setting up the metadata,
takes care of putting the red zones around our allocations, and so on. So we had to
do something similar in the kernel; of course, you cannot link with libASan in
the kernel, because that doesn't work, but what we can do instead is, again, compile
the kernel with kASan support. So this instruments the allocator, kmalloc, to add
the red zones; it allocates space for the metadata, it keeps this metadata around,
does this all for us, which is really nice. And again, the big advantage of
using this approach is that we can integrate seamlessly with a kASan-
instrumented kernel and with fuzzers that rely on kASan such as syzkaller. So we see
this as more of a plus than, like, a limitation. And how do you implement ASan?
Well, you have to find every memory access and instrument it to check the—to check
whether this is accessing a red zone. And if it does then you just call this bug
report function that produces a stack trace, a bug report, and crashes the
kernel, so that the fuzzer can detect it. Again, this is compatible with source-
based kASan, so we're happy. We can simply load the rewritten module with added
instrumentation into a kernel, as long as you have compiled the kernel with the
right flags, and we can use a standard kernel fuzzer. Here for the—our
evaluation, we used syzkaller, a popular kernel fuzzer by some folks at Google, and
it worked really well. So we've finally reached the end of our journey, and now we
wanted to present some experiments we did to see if this really works. So for
userspace, we wanted to compare the performance of our binary ASan with
source-based ASan and with existing solutions that also work on binaries. So
for userspace, you can use valgrind memcheck. It's a memory sanitizer that is
based on binary translation and dynamic binary translation and works on binaries.
We compared it with source ASan and RetroWrite ASan on the SPEC CPU benchmark
and saw how fast it was. And for the kernel we decided to fuzz some file
systems and some drivers with syzkaller using both source-based KASan and kCov and
kRetroWrite-based KASan and kCov. So these are our results for userspace. So the red
bar is valgrind. We can see that the execution time of valgrind is the highest.
It is really, really slow—like, 3, 10, 30x overhead, way too slow for fuzzing. Then
in green, we have our binary ASan, which is, like, already a large improvement. In
orange we have source-based ASan. And then finally in blue we have the original code
without any instrumentation whatsoever. So we can see that source-based ASan has,
like, 2x or 3x overhead, and binary ASan is a bit higher, like, a bit less
efficient, but still somewhat close. So that's for userspace, and for the kernel,
we—these are some preliminary results, so, this is, like—I'm doing this work as part
of my master's thesis, and so I'm still, like, running the evaluation. Here we can
see that the overhead is already, like, a bit lower. So the reason for this is that
SPEC is a pure CPU benchmark; it doesn't interact with the system that much. And so
any instrumentation that you add is going to massively slow down, or, like,
considerably slow down the execution. By contrast, when you fuzz a file system with
syzkaller, not only every test case has to go from the high—the host to the guest and
then do multiple syscalls and so on, but also every system call has to go through
several layers of abstraction before it gets to the actual file system. And all
these—like, all of this takes a lot of time, and so in practice the overhead of
our instrumentation seems to be pretty reasonable. So, since we know that you
like demos, we've prepared a small demo of kRetroWrite. So. Let's see. Yep. Okay. All
right, so we've prepared a small kernel module. And this module is just, like,
really simple; it contains a vulnerability, and what it does is that it
creates a character device. So if you're not familiar with this, a character device
is like a fake file that is exposed by a kernel driver and that it can read to and
write from. And instead of going to a file, the data that you read—that you, in
this case, write to the fake file—goes to the driver and is handled by this demo
write function. So as we can see, this function allocates a buffer, a 16-byte
buffer on the heap, and then copies some data into it, and then it checks if the
data contains the string "1337". If it does, then it accesses the buffer out of
bounds; you can see "alloc[16]" and the buffer is sixteen bytes; this is an out-
of-bounds read by one byte. And if it doesn't then it just accesses the buffer
in bounds, which is fine, and it's not a vulnerability. So we can compile this
driver. OK, um... OK, and then so we have our module, and then we will instrument it
using kRetroWrite. So, instrument... Yes, please. OK. Right. So kRetroWrite did some
processing, and it produced an instrumented module with ASan or kASan and
a symbolized assembly file. We can actually have a look at the symbolized
assembly file to see what it looks like. Yes. Yes. OK. So, is this big enough?
Yeah... As you can see, so—we can actually see here the ASan instrumentation. Ah,
shouldn't—yeah. So, we—this is the ASan instrumentation. The original code loads
some data from this address. And as you can see, the ASan instrumentation first
computes the actual address, and then does some checking—basically, this is checking
some metadata that ASan stores to check if the address is in a red zone or not, and
then if the fail check fails, then it calls this ASan report which produces a
stack trace and crashes the kernel. So this is fine. We can actually even look at
the disassembly of both modules, so... object dump and then demo... Ah, nope. OK,
so on the left, we have the original module without any instrumentation; on the
right, we have the module instrumented with ASan. So as you can see, the original
module has "push r13" and then has this memory load here; on the right in the
instrumented module, kRetroWrite inserted the ASan instrumentation. So the original
load is still down here, but between that, between the first instruction and this
instruction, we have—now have the kASan instrumentation that does our check. So
this is all fine. Now we can actually test it and see what it does. So we can—we will
boot a very simple, a very minimal Linux system, and try to target the
vulnerability first with the non- instrumented module and then with the
instrumented module. And we can—we will see that in the—with the non-instrumented
module, the kernel will not crash, but with the instrumented module it will crash
and produce a bug report. So. Let's see. Yeah, this is a QEMU VM, I have no idea
why it's taking so long to boot. I'll blame the the demo gods not being kind to
us. Yeah, I guess we just have to wait. OK. So. All right, so we loaded the
module. We will see that it has created a fake file character device in /dev/demo.
Yep. We can write this file. Yep. So this will—this accesses the array in bounds,
and so this is fine. Then what we can also do is write "1337" to it so it will access
the array out of bounds. So this is the non instrumented module, so this will not
crash. It will just print some garbage value. Okay, that's it. Now we can load
the instrumented module instead... and do the same experiment again. All right. We
can see that /dev/demo is still here. So the module still works. Let's try to write
"1234" into it. This, again, doesn't crash. But when we try to write "1337",
this will produce a bug report. *applause*
So this has quite a lot of information. We
can see, like, the—where the memory was allocated, there's a stack trace for that;
it wasn't freed, so there's no stack trace for the free. And we see that the cache
size of the memory, like, it was a 16-byte allocation. We can see the shape of the
memory. We see that these two zeros means that there's two 8-byte chunks of valid
memory. And then these "fc fc fc" is the—are the red zones that I was talking
about before. All right, so that's it for the demo. We will switch back to our
presentation now. So... hope you enjoyed it.
gannimo: Cool. So after applying this to a demo module, we also wanted to see what
happens if we apply this to a real file system. After a couple of hours we
were—when we came back and checked on the results, we saw a couple of issues popping
up, including a nice set of use-after-free reads, a set of use-after-free writes, and
we checked the bug reports and we saw a whole bunch of Linux kernel issues popping
up one after the other in this nondescript module that we fuzzed. We're in the
process of reporting it. This will take some time until it is fixed; that's why
you see the blurry lines. But as you see, there's still quite a bit of opportunity
in the Linux kernel where you can apply different forms of targeted fuzzing into
different modules, leverage these modules on top of a kASan instrumented kernel and
then leveraging this as part of your fuzzing toolchain to find interesting
kernel 0days that... yeah. You can then develop further, or report, or do whatever
you want with them. Now, we've shown you how you can take existing binary-only
modules, think different binary-only drivers, or even existing modules where
you don't want to instrument a full set of the Linux kernel, but only focus fuzzing
and exploration on a small different—small limited piece of code and then do security
tests on those. We've shown you how we can do coverage-based tracking and address
sanitization. But this is also up to you on what kind of other instrumentation you
want. Like this is just a tool, a framework that allows you to do arbitrary
forms of instrumentation. So we've taken you on a journey from instrumenting
binaries over coverage-guided fuzzing and sanitization to instrumenting modules in
the kernel and then finding crashes in the kernel. Let me wrap up the talk. So, this
is one of the the fun pieces of work that we do in the hexhive lab at EPFL. So if
you're looking for postdoc opportunities or if you're thinking about a PhD, come
talk to us. We're always hiring. The tools will be released as open source. A large
chunk of the userspace work is already open source. We're working on a set of
additional demos and so on so that you can get started faster, leveraging the
different existing instrumentation that is already out there. The userspace work is
already available. The kernel work will be available in a couple of weeks. This
allows you to instrument real-world binaries for fuzzing, leveraging existing
transformations for coverage tracking to enable fast and effective fuzzing and
memory checking to detect the actual bugs that exist there. The key takeaway from
this talk is that RetroWrite and kRetroWrite enables static binary
rewriting at zero instrumentation cost. We take the limitation of focusing only on
position-independent code, which is not a real implementation, but we get the
advantage of being able to symbolize without actually relying on heuristics, so
we can even symbolize large, complex source—large, complex applications and
effectively rewrite those aspects and then you can focus fuzzing on these parts.
Another point I want to mention is that this enables you to reuse existing tooling
so you can take a binary blob, instrument it, and then reuse, for example, Address
Sanitizer or existing fuzzing tools, as it integrates really, really nice. As I said,
all the code is open source. Check it out. Try it. Let us know if it breaks. We're
happy to fix. We are committed to open source. And let us know if there are any
questions. Thank you. *applause*
Herald: So, thanks, guys, for an interesting talk. We have some time for
questions, so we have microphones along the aisles. We'll start from question from
microphone number two. Q: Hi. Thanks for your talk and for the
demo. I'm not sure about the use-case you showed for the kernel RetroWrite. 'Cause
you're usually interested in fuzzing binary in kernelspace when you don't have
source code for the kernel. For example, for IoT or Android and so on. But you just
reuse the kCov and kASan in the kernel, and you never have the kernel in IoT or
Android which is compiled with that. So are you—do you have any plans to binary
instrument the kernel itself, not the modules?
Nspace: So we thought about that. I think that there's some additional problems that
we would have to solve in order to be able to instrument the full kernel. So other
than the fact that it gives us compatibility with, like, existing tools,
the reason why we decided to go with compiling the kernel with kASan and kCov
is that building the, like—you would you have to, like, think about it. You
have to instrument the memory allocator to add red zones, which is, like, already
somewhat complex. You have to instrument the exception handlers to catch, like, any
faults that the instrumentation detects. You would have to, like, set up some
memory for the ASan shadow. So this is, like—I think you should be able to do it,
but it would require a lot of additional work. So this is, like—this was like four
months' thesis. So we decided to start small and prove that it works in
the kernel for modules, and then leave it to future work to actually extend it to
the full kernel. Also, like, I think for Android—so in the case of Linux, the
kernel is GPL, right, so if the manufacturers ships a custom kernel, they
have to release the source code, right? Q: They never do.
Nspace: They never—well, that's a different issue. Right?
gannimo: Right. Q: So that's why I ask, because I don't
see how it just can be used in the real world.
gannimo: Well, let me try to put this into perspective a little bit as well. Right.
So there's the—what we did so far is we leveraged existing tools, like kASan or
kCov, and integrated into these existing tools. Now, doing heap-based allocation is
fairly simple and replacing those with additional red zones—that instrumentation
you can carry out fairly well by focusing on the different allocators. Second to
that, simply oopsing the kernel and printing the stack trace is also fairly
straightforward. So it's not a lot of additional effort. So it is—it involves
some engineering effort to port this to non-kASan-compiled kernels. But we think
it is very feasible. In the interest of time, we focused on kASan-enabled kernels,
so that some form of ASan is already enabled. But yeah, this is additional
engineering effort. But there is also a community out there that can help us with
these kind of changes. So kRetroWrite and RetroWrite themselves are the binary
rewriting platform that allow you to turn a binary into an assembly file that you
can then instrument and run different passes on top of it. So another pass would
be a full ASan pass or kASan pass that somebody could add and then contribute
back to the community. Q: Yeah, it would be really useful.
Thanks. gannimo: Cool.
Angel: Next question from the Internet. Q: Yes, there is a question regarding the
slide on the SPEC CPU benchmark. The second or third graph from the right had
an instrumented version that was faster than the original program. Why is that?
gannimo: Cache effect. Thank you. Angel: Microphone number one.
Q: Thank you. Thank you for presentation. I have question: how many architecture do
you support, and if you have support more, what then?
gannimo: x86_64. Q: Okay. So no plans for ARM or MIPS,
or...? gannimo: Oh, there are plans.
Q: Okay. Nspace: Right, so—
gannimo: Right. Again, there's a finite amount of time. We focused on the
technology. ARM is high up on the list. If somebody is interested in working on it
and contributing, we're happy to hear from it. Our list of targets is ARM first and
then maybe something else. But I think with x86_64 and ARM we've covered a
majority of the interesting platforms. Q: And second question, did you try to
fuzz any real closed-source program? Because as I understand from presentation,
you fuzz, like, just file system, what we can compile and fuzz with syzkaller like
in the past. Nspace: So for the evaluation, we wanted
to be able to compare between the source- based instrumentation and the binary-based
instrumentation, so we focused mostly on open-source filesystem and drivers because
then we could instrument them with a compiler. We haven't yet tried, but this
is, like, also pretty high up on the list. We wanted to try to find some closed-
source drivers—there's lots of them, like for GPUs or anything—and we'll give it a
try and find some 0days, perhaps. Q: Yes, but with syzkaller, you still have
a problem. You have to write rules, like, dictionaries. I mean, you have to
understand the format, have to communicate with the driver.
Nspace: Yeah, right But there's, for example, closed-source file systems that
we are looking at. Q: Okay. Thinking.
Herald: Number two. Q: Hi. Thank you for your talk. So I don't
know if there are any kCov- or kASan- equivalent solution to Windows, but I was
wondering if you tried, or are you planning to do it on Windows, the
framework? Because I know it might be challenging because of the driver
signature enforcement and PatchGuard, but I wondered if you tried or thought about
it. gannimo: Yes, we thought about it and we
decided against it. Windows is incredibly hard and we are academics. The research I
do in my lab, or we do in my research lab, focuses on predominantly open-source
software and empowers open-source software. Doing full support for Microsoft
Windows is somewhat out of scope. If somebody wants to port these tools, we are
happy to hear it and work with these people. But it's a lot of additional
engineering effort, versus very additional—very low additional research
value, so we'll have to find some form of compromise. And, like, if you would be
willing to fund us, we would go ahead. But it's—yeah, it's a cost question.
Q: And you're referring both to kernel and user space, right?
gannimo: Yeah. Q: Okay. Thank you.
Herald: Number five. Q: Hi, thanks for the talk. This seems
most interesting if you're looking for vulnerabilities in closed source kernel
modules, but not giving it too much thought, it seems it's really trivial to
prevent this if you're writing a closed source module.
gannimo: Well, how would you prevent this? Q: Well, for starters, you would just take
a difference between the address of two functions. That's not gonna be IP
relative, so... Nspace: Right. So we explicitly—like, even
in the original RetroWrite paper—we explicitly decided to not try to deal with
obfuscated code, or code that is purposefully trying to defeat this kind of
rewriting. Because, like, the assumption is that first of all, there are techniques
to, like, deobfuscate code or remove these, like, checks in some way, but this
is, like, sort of orthogonal work. And at the same time, I guess most drivers are
not really compiled with the sort of obfuscation; they're just, like, you know,
they're compiled with a regular compiler. But yeah, of course, this is, like, a
limitation. gannimo: They're likely stripped, but not
necessarily obfuscated. At least from what we've seen when we looked at binary-only
drivers. Herald: Microphone number two.
Q: How do you decide where to place the red zones? From what I heard, you talked
about instrumenting the allocators, but, well, there are a lot of variables on the
stack, so how do you deal with those? gannimo: Oh, yeah, that's actually super
cool. I refer to some extent to the paper that is on the GitHub repo as well. If you
think about it, modern compilers use canaries for buffers. Are you aware of
stack canaries—how stack canaries work? So, stack canaries—like, if the compiler
sees there's a buffer that may be overflown, it places a stack canary
between the buffer and any other data. What we use is we—as part of our analysis
tool, we find these stack canaries, remove the code that does the stack canary, and
use this space to place our red zones. So we actually hack the stack in areas,
remove that code, and add ASan red zones into the empty stack canaries that are now
there. It's actually a super cool optimization because we piggyback on what
kind of work the compiler already did for us before, and we can then leverage that
to gain additional benefits and protect the stack as well.
Q: Thanks. Angel: Another question from the Internet.
Q: Yes. Did you consider lifting the binary code to LLVM IR instead of
generating assembler source? gannimo: Yes. *laughter* But, so—a little
bit longer answer. Yes, we did consider that. Yes, it would be super nice to lift
to LLVM IR. We've actually looked into this. It's incredibly hard. It's
incredibly complex. There's no direct mapping between the machine code
equivalent and the LLVM IR. You would still need to recover all the types. So
it's like this magic dream that you recover full LLVM IR, then do heavyweight
transformations on top of it. But this is incredibly hard because if you compile
down from LLVM IR to machine code, you lose a massive amount of information. You
would have to find a way to recover all of that information, which is pretty much
impossible and undecidable for many cases. So for example, just as a note, we only
recover control flow and we only desymbolize control flow. For data
references—we don't support instrumentation of data references yet
because there's still an undecidable problem that we are facing with. I can
talk more about this offline, or there is a note in the paper as well. So this is
just a small problem. Only if you're lifting to assembly files. If you're
lifting to LLVM IR, you would have to do full end-to-end type recovery, which is
massively more complicated. Yes, it would be super nice. Unfortunately, it is
undecidable and really, really hard. So you can come up with some heuristics, but
there is no solution that will do this in—that will be correct 100 percent of the
time. Angel: We'll take one more question from
microphone number six. Q: Thank you for your talk. What kind of
disassemblers did you use for RetroWrite, and did you have problems with the wrong
disassembly? And if so, how did you handle it?
Nspace: So, RetroWrite—so we used Capstone for the disassembly.
gannimo: An amazing tool, by the way. Nspace: Yeah. So the idea is that, like,
we need some kind of—some information about where the functions are. So for the
kernel modules, this is actually fine because kernel modules come with this sort
of information because the kernel needs it, to build stack traces, for example.
For userspace binaries, this is somewhat less common, but you can use another tool
to try to do function identification. And we do, like—sort of, like, disassemble the
entire function. So we have run into some issues with, like—in AT&T syntax, because
like we wanted to use gas, GNU's assembler, for, for...
gannimo: Reassembling. Nspace: Reassembly, yeah. And some
instructions are a lot—you can express the same, like, two different instructions,
like five-byte NOP and six-byte NOP, using the same string of, like, text—a mnemonic,
an operand string. But the problem is that, like, the kernel doesn't like it and
crashes. This took me like two days to debug.
gannimo: So the kernel uses dynamic binary patching when it runs, at runtime, and it
uses fixed offsets, so if you replace a five-byte NOP with a six-byte NOP or vice
versa, your offsets change and your kernel just blows up in your face.
Q: So it was kind of a case-on-case basis where you saw the errors coming out of the
disassembly and you had to fix it? Nspace: So sorry, can you repeat the
question? Q: Like, for example, if you—if some
instruction is not supported by the disassembler, so you saw that it crashed,
that there's something wrong, and then you fix it by hand?
Nspace: Yeah, well, if we saw that there was a problem with it, this—like, I don't
recall having any unknown instructions in the dissasembler. I don't think I've ever
had a problem with that. But yeah, this was a lot of, like, you know, engineering
work. gannimo: So let me repeat. The problem was
not a bug in the disassembler, but an issue with the instruction format—that the
same mnemonic can be translated into two different instructions, one of which was
five bytes long, the other one was six bytes long. Both used the exact same
mnemonic. Right, so this was an issue with assembly encoding.
Q: But you had no problems with unsupported instructions which couldn't be
disassembled? Nspace: No, no. Not as far as I know, at
least. Angel: We have one more minute, so a very
short question from microphone number two. Q: Does it work? Ah. Is your binary
instrumentation equally powerful as kernel address space... I mean, kASan? So, does
it detect all the memory corruptions on stack, heap and globals?
gannimo: No globals. But heap—it does all of them on the heap. There's some slight
variation on the stack because we have to piggyback on the canary stuff. As I
mentioned quickly before, there is no reflowing and full recovery of data
layouts. So to get anything on the stack, we have to piggyback on existing compiler
extensions like stack canaries. But—so we don't support intra-object overflows on
the stack. But we do leverage the stack in areas to get some stack benefits, which
is, I don't know, 90, 95 percent there because the stack canaries are pretty
good. For heap, we get the same precision. For globals, we have very limited support.
Q: Thanks. Angel: So that's all the time we have for
this talk. You can find the speakers, I think, afterwards offline. Please give
them a big round of applause for an interesting talk.
*applause*
*36c3 postrol music*
Subtitles created by c3subtitles.de in the year 2021. Join, and help us!