This is an archive of the discontinued LLVM Phabricator instance.

[hwasan] optionally right-align heap allocations
ClosedPublic

Authored by kcc on Oct 26 2018, 6:16 PM.

Details

Summary

... so that we can find intra-granule buffer overflows.
The default is still to always align left.
It remains to be seen wether we can enable this mode at scale.

Diff Detail

Repository
rL LLVM

Event Timeline

kcc created this revision.Oct 26 2018, 6:16 PM
Herald added subscribers: Restricted Project, delcypher, kubamracek. · View Herald TranscriptOct 26 2018, 6:16 PM
dvyukov added inline comments.
lib/hwasan/hwasan_allocator.cc
136 ↗(On Diff #171384)

Shouldn't we also look at user-requested alignment here? It looks like we only satisfy natural alignment.

test/hwasan/TestCases/heap-buffer-overflow.c
28 ↗(On Diff #171384)

This won't catch regressions as it will be happy with 8 in all cases.

31 ↗(On Diff #171384)

Ditto.

34 ↗(On Diff #171384)

Ditto.

eugenis added inline comments.Oct 29 2018, 1:28 PM
lib/hwasan/hwasan_allocator.cc
136 ↗(On Diff #171384)

Yeah, at least for calls like posix_memalign.

This mode will break some things anyway, ex.:
struct S {

int count;
char name[0];

};

When allocated with malloc(sizeof(S) + count) the size will not be a multiple of alignment, so "count" will be misaligned. That's why this mode can not be on by default. Let's hope it is not a common case.

139 ↗(On Diff #171384)

Use named constants, like kHandleSignalYes.

140 ↗(On Diff #171384)

This is not very random - entire region will have the same bit, so long running programs are likely to be stuck in either direction.

Use HwasanThread::random_buffer_ instead?

dvyukov added inline comments.Oct 29 2018, 1:39 PM
lib/hwasan/hwasan_allocator.cc
136 ↗(On Diff #171384)

Why will not respecting alignment argument help? That's the alignment that we ensure in normal mode.

kcc updated this revision to Diff 171804.Oct 30 2018, 2:49 PM

use the pointer tag's bit as a source of randmness.
split the test lines for right and left alignment.

kcc updated this revision to Diff 171808.Oct 30 2018, 2:55 PM

use a named constant (kRightAlignAlways) instead of just '2' when checking the malloc_align_right flag.

kcc added inline comments.Oct 30 2018, 2:58 PM
lib/hwasan/hwasan_allocator.cc
136 ↗(On Diff #171384)

I've changed the code so that it respects alignment > 16.
Respecting smaller alignment is harder because the implecit alignment requirement for malloc is 16
(it's a bit more complicated than that, actually, I don't think the standard actually tells what the alignment is,
it just tells that it should be sufficient for any builtin type)

This mode is unlikely to be enabled by default in its current form.
For we can only tell what modifications will be needed once we try.

139 ↗(On Diff #171384)

done

140 ↗(On Diff #171384)

Changed to use a bit of the tag, that is random (unless, of course, we disable random tags via a flag)

test/hwasan/TestCases/heap-buffer-overflow.c
28 ↗(On Diff #171384)

done

31 ↗(On Diff #171384)

done

34 ↗(On Diff #171384)

done

kcc added a comment.Oct 30 2018, 3:00 PM

BTW, electric fence has EF_ALIGNMENT=1 (to set alignment to 1) and people have been using it for decades,
so this approach is not entirely unheard of.

dvyukov added inline comments.Oct 31 2018, 1:15 AM
lib/hwasan/hwasan_allocator.cc
136 ↗(On Diff #171384)

Strictly saying this can be handled in standard-conforming way for C++.
We need to enable -faligned-allocation to get C++17 alignment-aware operator new:
https://en.cppreference.com/w/cpp/memory/new/operator_new
And then pass -fnew-alignment=1 which will force compiler to call operator new with explicit alignment always.
This results in:

      int *volatile p1 = new int;
400614:       bf 04 00 00 00          mov    $0x4,%edi
400619:       be 04 00 00 00          mov    $0x4,%esi
40061e:       e8 ed fe ff ff          callq  400510 <operator new(unsigned long, std::align_val_t)@plt>
400623:       48 89 44 24 08          mov    %rax,0x8(%rsp)
      short *volatile p2 = new short[2];
400628:       bf 04 00 00 00          mov    $0x4,%edi
40062d:       be 02 00 00 00          mov    $0x2,%esi
400632:       e8 c9 fe ff ff          callq  400500 <operator new[](unsigned long, std::align_val_t)@plt>
400637:       48 89 44 24 10          mov    %rax,0x10(%rsp)
kcc added a comment.Nov 2 2018, 3:59 PM

Atomic operations on aarch64 require alignment, so this approach will break whenever the code does something like
struct Foo{

AtomiWord a;  // used by atomic instructions 
char vla[0];

}
all other loads/stores seem to work (see "B2.5.2 Alignment of data accesses" in https://static.docs.arm.com/ddi0487/da/DDI0487D_a_armv8_arm.pdf)

so far I've found one such place (std::string implementation in libstdc++, which uses a ref counting string).
I've also tried several benchmarks from fuzzer-test-suite with hwasan and right-alignment.
Those that don't use std::string just work, so I think we still have a chance to get away with this on aarch64,
although we may require some code modifications to avoid the situation above.

kcc added a comment.Nov 7 2018, 2:20 PM

One more case: https://github.com/google/re2/blob/master/re2/dfa.cc#L758
Here, again, we have a 8-byte object accessed atomically
and the size of the allocation is not necessary divisible by 8 (68 in my this case)

const int kStateCacheOverhead = 40;

int nnext = prog_->bytemap_range() + 1;  // + 1 for kByteEndText slot
int mem = sizeof(State) + nnext*sizeof(std::atomic<State*>) +
          ninst*sizeof(int);
if (mem_budget_ < mem + kStateCacheOverhead) {
  mem_budget_ = -1;
  return NULL;
}
mem_budget_ -= mem + kStateCacheOverhead;

This particular case is easy to fix by aligning mem by sizeof(void*)

kcc updated this revision to Diff 174263.Nov 15 2018, 11:50 AM

Added two more modes for malloc_align_right to allow 8-byte alignment
(randomly or always).
Extended comments, added one more test.

PTAL

eugenis added inline comments.Nov 15 2018, 3:08 PM
lib/hwasan/hwasan_allocator.cc
92 ↗(On Diff #174263)

CHECK that the flag has a valid value

272 ↗(On Diff #174263)

if right_aligned, check that it is not more than one granule apart

kcc updated this revision to Diff 174313.Nov 15 2018, 6:23 PM

addressed comments.

PTAL

kcc added inline comments.Nov 15 2018, 6:23 PM
lib/hwasan/hwasan_allocator.cc
92 ↗(On Diff #174263)

done

272 ↗(On Diff #174263)

done

This revision is now accepted and ready to land.Nov 16 2018, 11:13 AM
This revision was automatically updated to reflect the committed changes.
This revision was automatically updated to reflect the committed changes.