Page MenuHomePhabricator

[GwpAsan] Introduce GWP-ASan.
AbandonedPublic

Authored by hctim on Apr 11 2019, 5:33 PM.

Details

Summary

This patch introduces GWP-ASan, a sampled allocator framework that assists in finding use-after-free and heap-buffer-overflows bugs in production environments.

GWP-ASan supplements a traditional allocator (e.g. Scudo), and chooses random allocations to 'sample'. These sampled allocations are placed into a special guarded pool, which is based upon the traditional 'Electric Fence Malloc Debugger'. We surround the allocation with inaccessible pages, such that buffer under/overflows trap on the page fault. We also mark the allocation's page as inaccessible on free, meaning that any use-after-free bugs also cause a page fault trap, which we capture. For more implementation details, please see docs/GWPASan.rst.

Please note that this patch is quite large. The patchset contains the basic functionality of GWP-ASan (stack trace dumping and other debug information will be added shortly), the unit tests, and allocator shims into Scudo. This allows any code compiled with -fsanitize=scudo to have GWP-ASan enabled-by-default (including the unit tests). I've tried to slice out as much as possible for follow up patches but there isn't much left here to carve off.

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
morehouse added inline comments.May 1 2019, 2:21 PM
compiler-rt/lib/gwp_asan/guarded_pool_allocator_posix.cpp
77
compiler-rt/test/gwp_asan/num_usable_slots.cpp
60 ↗(On Diff #197637)

I'm not sure what a better test is but this isn't always true (e.g. the allocator could actually take back that page if all the allocations on it are gone.) These tests could test stronger assertions and be simpler if there was a __gwp_asan_pointer_is_mine() or something like that.

12 ↗(On Diff #197200)

We test +1 case but not the -1 case.

compiler-rt/test/gwp_asan/thread_contention_with_release.cpp
32 ↗(On Diff #197637)

*Ptr may not be 0 if we fall through to regular malloc() (either here or on the realloc call below), perhaps we should risk running this test on normal malloc()/realloc() sometimes and have NumAllocsTotal fully deplete the free list instead?

72 ↗(On Diff #197637)

I'm not sure I understand this logic: 1) what std::set? (the std::vector<std::thread>?) 2) we should be able to consume more than the total number of guarded allocations if we wanted right since it would just fall back to normal malloc?

llvm/docs/GwpAsan.rst
153

Replace NumUsableGuardedPages

160

Ditto

hctim updated this revision to Diff 198048.May 3 2019, 10:55 AM
hctim marked 25 inline comments as done.
  • Updated with Vlad's and Matt's comments.
compiler-rt/CMakeLists.txt
281 ↗(On Diff #195942)

I've changed this flag to not exist any more, as it's synonymous with COMPILER_RT_GWP_ASAN_ENABLED anyway.

@cryptoad and I have confirmed offline that always-built on supported platforms is okay :)

compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp
183

I think the major reason for me is that it may be a use case to have a guarded pool with only a single slot for short-lived processes on memory-constrained devices. We're planning on process sampling as well for Android, and it may be useful to service short-lived processes with a single allocation instead of disabling it completely.

compiler-rt/lib/gwp_asan/guarded_pool_allocator.h
26

Yep, updated documentation to reflect this.

163

Gotcha. ssize_t is POSIX-only (see Windows docs) so I've made it return kInvalidSlotID instead.

compiler-rt/lib/gwp_asan/guarded_pool_allocator_posix.cpp
77

Done with some slight modifications. If the previous handler was SIG_IGN, we die as we'll constantly restart on the memory error and repeatedly spam GWP-ASan output. This also aligns with the exit behaviour of DOUBLE_FREE/INVALID_FREE and that of SIGSEGV-delivered errors.

We also don't explicitly handle SIG_DFL, as the fallthrough should call the default signal handler just fine.

compiler-rt/lib/gwp_asan/options.inc
29

The error checking is done in the flag parser, but I've also added explicit checking in init() as well.

compiler-rt/test/gwp_asan/num_usable_slots.cpp
60 ↗(On Diff #197637)

Changed it to use the same mechanism from above to detect if it's in the pool.

I think the current assumption is strong enough, but may be broken if atoi() or alloca() changes to call malloc (unlikely), or if a shared library calls malloc() during dynamic loading. WDYT?

Edit: On further thought, this also will spuriously pass if the implementing allocator uses the page immediately after the allocation pool to back the allocation. I've added interface definitions and started a cleanup so that we can exercise the allocator internals directly.

12 ↗(On Diff #197200)

I'm confused why we would need to test the -1 case (assuming that -1 means NumIterations == MaxSimultaneousAllocations - 1), given that NumIterations == MSA provide this coverage. Is my assumption correct?

compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp
427

nullptr

432

if (!gwp_asan::SingletonPtr) return; to match the other functions?

compiler-rt/test/gwp_asan/no_reuse_ahead_of_time.cpp
35 ↗(On Diff #198048)

Why does anything need to care about initializing the GPA ahead of time for anything other than allocate? The underlying methods should return the correct values. And even for allocate() we can get around this edge case by doing allocate(PageSize+1).

compiler-rt/test/gwp_asan/num_usable_slots.cpp
60 ↗(On Diff #197637)

If we want to be safe, because I can definitely see runtimes hitting malloc() before main()in normal code paths, we could make SampleRate high and use the GPA allocate directly for this test.

12 ↗(On Diff #197200)

This looks fine as is.

compiler-rt/test/gwp_asan/pattern_malloc_free.cpp
1 ↗(On Diff #198048)

I would collapse the pattern_* tests into two tests:

  1. Test that malloc, calloc, realloc, new, new[] all satisfy pointerismine
  2. And then this test.

Less code and should have equal coverage.

compiler-rt/test/gwp_asan/reuse_quarantine.cpp
8 ↗(On Diff #198048)

Maybe delete the 1/2 cases (will fail on runtimes that call malloc before main() and just call it with some other higher value that should always work like 32.

compiler-rt/lib/gwp_asan/guarded_pool_allocator.cpp
432

I suppose it could also be assert(gwp_asan::SingletonPtr) since it's never correct to reach this function with an uninitialized GPA.

hctim marked 10 inline comments as done.May 6 2019, 11:11 AM
hctim added inline comments.
compiler-rt/test/gwp_asan/no_reuse_ahead_of_time.cpp
35 ↗(On Diff #198048)

These helper funcs call through the singleton ptr, which is nullptr until init(). Calling pointerIsMine() (for example) would access (nullptr)->GuardedPagePool.

I like the maximumAllocSize() + 1. At the moment, GPA::maximumAllocSize()doesn't rely on any data members, but is still UB to call with a nullptr instance. I think I'll do this but with an arbritrarily large allocation and leave a note for me to update it when we support multipage slots.

compiler-rt/test/gwp_asan/reuse_quarantine.cpp
8 ↗(On Diff #198048)

I've instead rewrote it so that it exercises the allocator directly with no sampling, so that we avoid this issue. LGTY?

hctim updated this revision to Diff 198313.May 6 2019, 11:11 AM
hctim marked 2 inline comments as done.
  • Updated from Vlad's comments.
vlad.tsyrklevich accepted this revision.May 6 2019, 1:11 PM
vlad.tsyrklevich added inline comments.
compiler-rt/test/gwp_asan/no_reuse_ahead_of_time.cpp
35 ↗(On Diff #198048)

But that's not true, all of the __gwp_asan_* functions fail gracefully if initialization hasn't occurred (except for deallocate which is never valid to call when uninitialized), e.g. pointer_is_mine would just return false. We do need initialization for the allocate() case so it works as expected, and I'm fine with wrapping all of the gwp_asan_* functions for consistency with allocate(), but I think we should only call maybeInit in the allocate case to make it explicit that that is the only one that needs it (and if that changes we can get rid of it and use the underlying methods directly.)

compiler-rt/test/gwp_asan/reuse_quarantine.cpp
8 ↗(On Diff #198048)

Looks good.

This revision is now accepted and ready to land.May 6 2019, 1:11 PM
morehouse added inline comments.May 6 2019, 6:22 PM
compiler-rt/include/sanitizer/gwp_asan_interface.h
1 ↗(On Diff #198313)

I think I missed something. What is the purpose of these functions?

compiler-rt/lib/gwp_asan/guarded_pool_allocator_posix.cpp
75

I'm not opposed to ignoring SIG_IGN, but this should be documented somewhere.

77

I am skeptical that calling SIG_DFL() will work.

SIG_DFL is not a function address.

https://en.cppreference.com/w/cpp/utility/program/SIG_strategies

compiler-rt/lib/gwp_asan/gwp_asan_interface_internal.h
1 ↗(On Diff #198313)

Why do we want this?

compiler-rt/lib/gwp_asan/random.cpp
18

Looks like initialization of these globals could happen after the first call to getRandom.

compiler-rt/lib/scudo/scudo_allocator.cpp
305

Could you just post the assembly? Preferably a before/after of this fastpath change.

The CFG is confusing for me to read.

hctim marked 15 inline comments as done.May 7 2019, 12:46 PM
hctim added inline comments.
compiler-rt/include/sanitizer/gwp_asan_interface.h
1 ↗(On Diff #198313)

See comment in compiler-rt/lib/gwp_asan/gwp_asan_interface_internal.h.

compiler-rt/lib/gwp_asan/guarded_pool_allocator_posix.cpp
75

Documented in GwpAsan.rst and options.inc.

77

Surprisingly, it worked on my machine. Have changed to ensure this works everywhere.

compiler-rt/lib/gwp_asan/gwp_asan_interface_internal.h
1 ↗(On Diff #198313)

To allow us to exercise the allocator directly for testing. The comments in compiler-rt/test/gwp_asan/num_usable_slots.cpp has some more context, but the summary is:

  1. Allows us to be precise with exactly which allocations are sampled (important, for example, in tests/num_usable_slots.cpp where if a library calls malloc() during its init, we will break. Also, in the thread_contention* tests, we want to be certain that we are exercising the sampled allocator, rather than potentially falling back to the system allocator.
  2. Allows us to test directly against the interface whether something is sampled through __gwp_asan_pointer_is_mine(), avoiding relying on implementation specific assumptions. In tests/num_usable_slots.cpp, we were previously relying on left-to-right sequential usage of the sampled slots to determine whether an allocation was sampled. We then had no method to determine whether an allocation was not sampled, as the system allocator may place the unsampled allocation in the page directly after the guarded pool, leading us to spurious failure.
compiler-rt/lib/scudo/scudo_allocator.cpp
305

before, after the changes

compiler-rt/test/gwp_asan/no_reuse_ahead_of_time.cpp
35 ↗(On Diff #198048)

My mistake. They don't cause error, but they don't return correct values until init has taken place.

We also need init support for maximumAllocationSize() from interface_test.cpp and interface_test_failures.cpp with their current implementation. We could add explicit initialisation by caling a dummy __internal::allocate() / deallocate() in these specific tests. (And, I guess thread_contention_with_release.cpp as well if we can't make the strong guarantee that std::vector<std::thread>::emplace_back() always calls the system allocator.)

It seems to make the interface a lot less prone to test implementation errors. Happy to change if if you feel strongly about this, but apart from performance of the tests, I don't see what we gain (especially when scudo::allocate always does a once-init check as well through initThreadMaybe()).

hctim updated this revision to Diff 198512.May 7 2019, 12:46 PM
hctim marked 6 inline comments as done.
  • Matt's comments.
hctim marked an inline comment as done.May 7 2019, 12:47 PM
hctim added inline comments.
compiler-rt/lib/scudo/scudo_allocator.cpp
305
morehouse added inline comments.May 7 2019, 4:50 PM
compiler-rt/lib/gwp_asan/gwp_asan_interface_internal.h
1 ↗(On Diff #198313)

Can we just write unit tests, like we have in Google3 and Chrome GWP-ASans, Scudo, and every sanitizer? Then we don't need these interfaces.

morehouse added inline comments.May 8 2019, 9:07 AM
compiler-rt/lib/gwp_asan/guarded_pool_allocator.h
98

The assembly you posted for this function looks way too slow. Is it actually optimized with -O2?

  • The fast path (counter > 1) has *two* branches that check if NextSampleCounter's TLS init function has run and one actual call to the TLS init function. Ouch! We shouldn't need these.
    • Maybe we need to make the counter function-local or use __thread instead of thread_local.
  • The counter decrement of NextSampleCounter requires 4 instructions? Load TLS offset from global, read TLS, increment, write TLS. Yikes. For reference, TCMalloc does this operation in 1 instruction.
  • The + 1 operation on the NextSampleCounter == 0 branch is done with a mov-add, rather than an lea.

Again, please triple-check that the binary you compiled is actually optimized. Make sure it is compiled with clang++ -O2 ....

One thing I also just realized is that by explicitly setting TLS model to initial-exec we prevent dlopen() dynamic loading, I don't have a problem with that but just wanted to make sure @cryptoad was aware.

compiler-rt/lib/gwp_asan/gwp_asan_interface_internal.h
1 ↗(On Diff #198313)

That is the way to go, I suggested this approach at first forgetting that there are non-lit tests.

What does GWP stand for?

hctim marked 4 inline comments as done.May 10 2019, 2:19 PM
hctim added inline comments.
compiler-rt/lib/gwp_asan/guarded_pool_allocator.h
98

As per offline discussion, declaring NextSampleCounter with __thread instead of thread_local fixed this. Also added a note in definitions.h.

hctim updated this revision to Diff 199083.May 10 2019, 2:19 PM
hctim marked an inline comment as done.
  • Updated tests to use unittests rather than expose a public interface and exercise that. Minor perf improvements to shouldSample().
Herald added a project: Restricted Project. · View Herald TranscriptMay 10 2019, 2:19 PM
Herald added a subscriber: cfe-commits. · View Herald Transcript
hctim added a comment.May 10 2019, 2:24 PM

What does GWP stand for?

Google Wide Profiling.

We use the name GWP-ASan, even though it's "technically neither GWP nor ASan", but because it describes well what the outcome is (sampled allocations with memory detection capabilities). It also mirrors the name used for the identical mechanism implemented in Chromium.

This diff is helpful to get an overall idea of how things fit together, but it is very difficult to review thoroughly. Let's start splicing off pieces for individual review.

I suggest:

  • Individual reviews for each prereq (mutex, random, etc.)
  • Review for base GPA + unit tests
  • Review for "optional" options parsing, etc.
  • Review for documentation
  • Review for Scudo integration + e2e tests

Submitting this in pieces (especially the Scudo integration) will also make things simpler if we need to revert something.

compiler-rt/lib/gwp_asan/guarded_pool_allocator.h
98

What is the assembly now?

jfb added a comment.May 14 2019, 4:54 PM

What does GWP stand for?

Google Wide Profiling.

We use the name GWP-ASan, even though it's "technically neither GWP nor ASan", but because it describes well what the outcome is (sampled allocations with memory detection capabilities). It also mirrors the name used for the identical mechanism implemented in Chromium.

Hello I'm here to bikeshed, and this is a terrible name for an LLVM project. Or super appropriate because LLVM itself is a terrible name? In any case, backronym it to something else, or rename it. Thanks!

Ha, I think it matches LLVM perfectly :)
G, of course, stands for "Galaxy".

hctim added a comment.May 14 2019, 6:20 PM
In D60593#1502266, @jfb wrote:

Hello I'm here to bikeshed, and this is a terrible name for an LLVM project. Or super appropriate because LLVM itself is a terrible name? In any case, backronym it to something else, or rename it. Thanks!

Also see GwpAsan.rst:

It informally is a recursive acronym, "GWP-ASan Will Provide Allocation SANity".

hctim abandoned this revision.Jun 28 2019, 3:27 PM

Abandoned as this was merged in small chunks.