Google's Address-sanitizer: a fast memory error detector (10x valgrind) | Hacker News Reader

Google's Address-sanitizer: a fast memory error detector (10x valgrind)

code.google.com

122 pointsalecco25 comments

The linked page is probably not the best place to familiarize yourself with the tool, comparison page would be a better start, especially for those who worked with other memory-checking tools: http://code.google.com/p/address-sanitizer/wiki/ComparisonOf...

The tool does not detect uninitialized memory reads, and memory leaks are not in yet. However, if they claims about speed (only 2x slowdown) are true, this is huge.

Comparing this to Valgrind is comparing apples to oranges. On is compiled in (and there are plenty of better comparisons such as ef) and the other runs on any pre-compiled binary. Some Valgrind modules might be slow, but you can run them after the fact which is powerful. You don't have to tinker with build systems or compile flags.

As mynegation links above:

http://code.google.com/p/address-sanitizer/wiki/ComparisonOf...

Yea, this is more comparable to eFence(3)

neat! I almost accidentally implemented this when making an implementation of this paper/technique: http://www.cs.umd.edu/~mwh/papers/martin10ownership.html

I bet they used llvm to do this? it would be childs play to do this in llvm ...

the downside to this technique is that you can only instrument / inspect code that you compile, so if you have any third party code that you link against, and that code results in memory errors, you have problems. you always do have third party code, like the C runtime. you can get around this though by having the source for the runtime and recompiling it with your instrumentation added.

you CAN recompile the runtime on windows (they ship it to you in a ready-to-build way as part of visual studio), but there are a lot of other libraries that they don't do that for (advapi, com, rpc, etc). I guess it's fortunate for chromium that they can run these tests on the linux codebase and have the windows codebase/build pick up the improvements made for free ...

also, if you're willing to insert some annotations into the code that you are instrumenting you can perform race condition detection with lower overhead. but konstantin already wrote a DBI extension that does race condition detection without requiring annotations (ahem, most of the time) so I guess that is low on his to-do list...

Yes, it uses a modified clang binary with which you compile your program.

I don't really see the disadvantage of not being able to debug within in the runtime. The class of errors this analyzer is meant to adress is stuff like use after free, out of bounds access, and use after return. If your runtime is doing those then a) you have bigger problems, b) you wouldn't be able to fix it anyway without the source.

the libraries functions can do an out of bounds access, for example: char a[16]; memset(a, 0, 100);

and as I understand their implementation, this won't be found because they instrument loads and stores in code that their clang compiles. the compiled code will look like: push off a push 0 push 100 call memset

there are two options that I see: 1. compile the runtime with the instrumentation 2. assemble a massive list of functions which you know to de-reference pointers they take as arguments and then hope that list is somewhat representative / comprehensive

Indeed, asan will generally miss bugs in third party libraries which are not compiled. But for memset and a few other popular libc functions asan has interceptors, so in your example the bug could be reported. Currently, when dealing with memset, asan analyzes only the first and the last accessed byte, so in your example a[99] should be inside a redzone, otherwise the bug may still be missed. For heap, asan uses 128 byte redzones by default, but for stack -- redzones are only 32-byte.

The Chromium Project is using ASAN:

http://www.chromium.org/developers/testing/addresssanitizer

Yeah, the Googlers that developed ASAN approached Chrome security this past summer. We'd previously avoided similar tools on our fuzzing cluster due to unsatisfactory performance. We've been running ASAN on the cluster since then, and the results have been really impressive. It's helped find dozens of security bugs, many of which would have been missed through our previous means.

About a month ago the infrastructure team also added an ASAN bot to the waterfall, and I think the stability team was experimenting with it before the rest of us. So, ASAN has had a pretty big uptake in the Chromium project.

Justin, this is awesome news. A question:

Have you guys started isolating any patterns to the bugs you missed pre-ASAN? What were your fuzzers (for instance) failing to do? Are there specific kinds of code paths (things buried in specific state transitions, things that were timing specific) that you couldn't catch without this level of instrumentation?

If you knew then what you knew now, short of implementing ASAN, how would you change your fuzzing cluster?

Hey Tom. We haven't really tracked the difference in what ASAN finds. If I had to ballpark it I'd say that ASAN wins significantly more than half of the time--meaning a given repro faults under ASAN but not under an uninstrumented build. And for a bit more context, the vast majority of the bugs we deal with are use-after-free issues, which is something that ASAN really excels at detecting and clearly reporting.

In terms of process, our scaled out fuzzing is rapidly evolving anyway. So, I think it was early enough that our approach wouldn't have changed too much. It's more that ASAN has enabled us to move faster, with fewer resources. And the improved turnaround time has significantly reduced the number of bugs that get past trunk.

If you want, I can put you in touch with the guys on my team doing the real work on the fuzzing cluster (I've been assisting in only an advisory capacity). They're also planning on doing a Chromium blog post on the project soon, so you could wait for that if you prefer.

This is not Google's project from what I see.

Also its just another version of electric fence which existed ever since I started debugging code. Correct me if I am wrong.

> Also its just another version of electric fence which existed ever since I started debugging code. Correct me if I am wrong.

I was about to say the same thing (though comparing it to Mungwall and Enforcer on AmigaOS), but then I read through it in more detail. There are significant differences:

Electric Fence/Mungwall/Enforcer type systems rely on one or both of poisoning and using the MMU to trap accesses. But the MMU approach only works fast if you only trap access to unallocated pages, not if you try to trap every access. That's where the comparison to Valgrind comes in - Valgrind checks every memory access precisely. But it's ridiculously slow.

So you get immediate feedback for accesses to unallocated pages from the simpler tools, and very quickly, since it's no slower than any other memory access through the MMU, except when there's a hit. Tools like this may or may not try to be more precise by trapping accesses to partially allocated pages, but if they do, performance drops dramatically.

Then they can trap writes to poisoned areas where they don't trap reads by running checks for magic values at specific times - typically at least on free() and program exit. The problem with this is that it won't pinpoint where the write happened, and it won't catch reads of unallocated memory.

But this tool inlines code during compilation that checks every dereferencing of every pointer, as far as I understand, by maintaining a lookup table that says whether or not a specific byte is allocated or not. The upside is that they can be as precise as Valgrind.

Oh. Thanks for the clarification.

I've worked with the team that built it, so I can verify that ASAN is definitely a Google project. Also, some other people have posted comments to links that verify the association.

As for the electric fence comparison, ASANs strengths are that it provides more detailed reports and detects more types of errors, but is still very fast. For example, ASAN will detect stack and global boundary violations, whereas electric fence will not.

Where is the "10x valgrind" bit claimed? I don't see how that's possible, given that valgrind is already about 20x slower than native and this is quite clearly going more than 2x work vs. a native load. Actually it seems to be doing pretty much the same stuff. What are the actual advantages?

TinyCC does this (was supposedly similar slowdown) <http://bellard.org/tcc/tcc-doc.html#SEC21>; - but it's C only. Still, one of the coolest projects around.

This looks great! Is there a similar project for memory leak detection in Java? I know that Java is using a virtual machine and is not supposed to have memory leaks, but we have some code that uses external libraries and our HEAP becomes consumed within 1-2 days.

There are leaks, and then there are "leaks". Memory that you have allocated and no longer have a reference to is a leak. Memory that you have a reference to but have stopped having use for is a "leak". It is hard to build tools to detect "leaks" because you don't know if the programmer intended to have a boundlessly growing collection or if it was an accident.

Have jvisualvm and jconsole been of any help? Those are two tools I wish I'd been introduced to when I first started programming in Java.

yourkit, is a wonderful tool. It's commercial but you should be able to get a trial license.

I don't see any reference that this is a Google project, but interesting nonetheless.

The presentation (http://code.google.com/p/address-sanitizer/downloads/detail?...) has a Google logo, and 1 of the 2 names (Konstantin Serebryany) has a linkedin profile with Google in his current work (http://ru.linkedin.com/in/serebryany).

http://blog.1024cores.net/2011/11/addresssanitizer-etc.html

He works at Google's Moscow office:

http://blog.1024cores.net/2011/08/relacy-race-detector-24-an...

Reply on news.ycombinator.com