David A. Wheeler's Blog

Tue, 07 Apr 2015

Heartbleed found with american fuzzy lop (afl) and Address Sanitizer (ASan)

Big news in security vulnerability research: Hanno Böck found Heartbleed using american fuzzy lop (afl) and Address Sanitizer (ASan) - and in only 6 hours of execution time.

This means that software developers should seriously consider using a more-advanced fuzzer, such as american fuzzy lop (afl), along with Address Sanitizer (ASan) (an option in both the LLVM/clang and gcc compilers), whenever you write in C, C++, Objective-C, or in other circumstances that are not memory-safe. In particular, seriously consider doing this if your program is exposed to the internet or it processes data sent via the internet (practically all programs meet this criteria nowadays). I had speculated that this combination could have found Heartbleed in my essay on Heartbleed, but this confirmation is really important. Here I will summarize what’s going on (using the capitalization conventions of the various tool developers).

The american fuzzy lop (afl) program created by Michal Zalewski is a surprisingly effective fuzzer. A fuzzer is simply a tool that sends lots of semi-random inputs into a program and to detect gross problems (typically a crash). Fuzzers do not know what the exact correct answers are, but because they do not, they can try out more inputs than systems that know the exact correct answers. But afl is smarter than most fuzzers; instead of just sending random inputs, afl tracks which branches are taken in a program. Even more interestingly, afl even tracks how often different branches are taken when running a program (that is especially unusual). Then, when afl creates new inputs, it prefers to create them based on inputs that have produced different counts on at least some branches. This evolutionary approach, using both branch coverage and the number of times a branch is used, is remarkably effective. Simple dumb random fuzzers can only perform relatively shallow tests; getting any depth has required more complex approaches such as detailed descriptions of the required format (the approach used by so-called “smart” fuzzers) and/or white-box constraint solving (such as fuzzgrind or Microsoft’s SAGE). It’s not at all clear that afl eliminates the value of these other fuzzing approaches; I can see combining their approaches. However, afl is clearly getting far better results than simple dumb fuzzers that just send random values. Indeed, the afl of today is getting remarkably deep coverage for a fuzzer. For example, the post Pulling JPEGs out of thin air shows how afl was able to start with only the text “hello” (a hideously bad starting point) and still automatically figure out how to create valid JPEG files.

However, while afl is really good at creating inputs, it can only detect problems if they lead to a crash; vulnerabilities like Heartbleed do not normally cause a crash. That’s where Address Sanitizer (ASan) comes in. Address Sanitizer turns many memory access errors, including nearly all out-of-bounds accesses, double-free, and use-after-free, into a crash. ASan was originally created by Konstantin Serebryany, Derek Bruening, Alexander Potapenko, and Dmitry Vyukov. ASan is amazing all by itself, and the combination is even better. The fuzzer afl is good at creating inputs, and ASan is good at turning problems into something that afl can detect. Both are available at no cost as Free/ libre/ open source software (FLOSS), so anyone can try them out, see how they work, and even make improvements.

Normally afl can only fuzz file inputs, but Heartbleed could only be triggered by network access. This is no big deal; Hanno describes in his article how to wrap up network programs so they can be fuzzed by file fuzzers.

Sometimes afl and ASan do not work well together today on 64-bit systems. This has to do with some technical limitations involving memory use; on 64-bit systems ASan reserves (but does not use) a lot of memory. This is not necessarily a killer; in many cases you can use them together anyway (as Hanno did). More importantly, this problem is about to go away. Recently I co-authored (along with Sam Hakim) a tool we call afl-limit-memory; it uses Linux cgroups to eliminate the problem so that you can always combine afl and ASan (at least on Linux). We have already submitted the code to the afl project leader, and we hope it will become part of afl soon. So this is already a disappearing problem.

There are lots of interesting related resources. If you want to learn about fuzzing more generally, some books you might want to read are Fuzzing: Brute Force Vulnerability Discovery by Sutton, Greene, and Amini and Fuzzing for Software Security Testing and Quality Assurance (Artech House Information Security and Privacy) by Takanen, DeMott, and Miller. My class materials for secure software design and programming, #9 (analysis tools), also cover fuzzing (and are freely available). The Fuzzing Project led by Hanno is an effort to encourate the use of fuzzing to improving the state of free software security, and includes some tutorials on how to do it. The paper AddressSanitizer: A Fast Address Sanity Checker is an excellent explanation of how ASan works. My essay How to Prevent the next Heartbleed discusses many different approaches that would, or would not, have detected Heartbleed.

I do not think that fuzzers (or any dynamic technique) completely replace static analysis approaches such as source code weakness analyzers. Various tools, including dynamic tools like fuzzers and static tools like source code weakness analyzers, are valuable complements for finding vulnerabilities before the attackers do.

path: /security | Current Weblog | permanent link to this entry