This is an archive of the discontinued LLVM Phabricator instance.

[HWASan] Ensure RNG is initialized in GenerateRandomTag
ClosedPublic

Authored by morehouse on Nov 2 2021, 1:09 PM.

Details

Summary

Fixes a CHECK-failure caused by glibc's pthread_getattr_np
implementation calling realloc. Essentially, Thread::GenerateRandomTag
gets called during Thread::Init and before Thread::InitRandomState:

HWAddressSanitizer: CHECK failed: hwasan_thread.cpp:134 "((random_buffer_)) != (0)" (0x0, 0x0) (tid=314)
  #0 0x55845475a662 in __hwasan::CheckUnwind()
  #1 0x558454778797 in __sanitizer::CheckFailed(char const*, int, char const*, unsigned long long, unsigned long long)
  #2 0x558454766461 in __hwasan::Thread::GenerateRandomTag(unsigned long)
  #3 0x55845475c58b in __hwasan::HwasanAllocate(__sanitizer::StackTrace*, unsigned long, unsigned long, bool)
  #4 0x55845475c80a in __hwasan::hwasan_realloc(void*, unsigned long, __sanitizer::StackTrace*)
  #5 0x5584547608aa in realloc
  #6 0x7f6f3a3d8c2c in pthread_getattr_np
  #7 0x5584547790dc in __sanitizer::GetThreadStackTopAndBottom(bool, unsigned long*, unsigned long*)
  #8 0x558454779651 in __sanitizer::GetThreadStackAndTls(bool, unsigned long*, unsigned long*, unsigned long*, unsigned long*)
  #9 0x558454761bca in __hwasan::Thread::InitStackAndTls(__hwasan::Thread::InitState const*)
  #10 0x558454761e5c in __hwasan::HwasanThreadList::CreateCurrentThread(__hwasan::Thread::InitState const*)
  #11 0x55845476184f in __hwasan_thread_enter
  #12 0x558454760def in HwasanThreadStartFunc(void*)
  #13 0x7f6f3a3d6fa2 in start_thread
  #14 0x7f6f3a15b4ce in __clone

Also reverts 7a3fb71c3cbdd80666335fa8f6f071b43f0b922a, as it's now
unneeded.

Diff Detail

Event Timeline

morehouse requested review of this revision.Nov 2 2021, 1:09 PM
morehouse created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptNov 2 2021, 1:09 PM
Herald added a subscriber: Restricted Project. · View Herald Transcript

Seems like it's workaround for case protected by CHECK(random_buffer_), why not just remove the CHECK?
another case which this CHECK helps against a bug in xorshift which must not return zero for non-zero input. I don't think this check is important but it can be handled like:

static u32 xorshift(u32 state) {
  u32 old_state = state;
  state ^= state << 13;
  state ^= state >> 17;
  state ^= state << 5;
  CHECK(!old_state || state);
  return state;
}
glider added inline comments.Nov 4 2021, 4:32 AM
compiler-rt/lib/hwasan/hwasan_thread.cpp
45

As I suggested off-list, why cannot we just initialize the RNG lazily on the first use?
Since there actually are early allocations during thread initialization, tagging them won't hurt.

morehouse updated this revision to Diff 384804.Nov 4 2021, 10:38 AM
morehouse marked an inline comment as done.
  • Use lazy init instead.

Seems like it's workaround for case protected by CHECK(random_buffer_), why not just remove the CHECK?
another case which this CHECK helps against a bug in xorshift which must not return zero for non-zero input. I don't think this check is important but it can be handled like:

static u32 xorshift(u32 state) {
  u32 old_state = state;
  state ^= state << 13;
  state ^= state >> 17;
  state ^= state << 5;
  CHECK(!old_state || state);
  return state;
}

GenerateRandomTag will not return until it gets a nonzero tag. The CHECK is there to avoid an infinite loop.

compiler-rt/lib/hwasan/hwasan_thread.cpp
45

Sure, I was trying to avoid an extra check in GenerateRandomTag for the lazy init. But I see your point.

morehouse retitled this revision from [HWASan] Disable tagging until RNG is initialized. to [HWASan] Ensure RNG is initialized in GenerateRandomTag.Nov 4 2021, 11:34 AM
vitalybuka added inline comments.Nov 4 2021, 1:41 PM
compiler-rt/lib/hwasan/hwasan_thread.cpp
30

CHECK_NE(randome_state_, 0)
RandomSeed already guaranties that, but unique_id_ does not, I guess no tests hit that case.
I suspect simple switch to preincrement on line 44 is enough

unique_id_ = ++unique_id;

unrelated but also "static u64 unique_id;" probably should be atomic?

135–136
if (!random_buffer_) {
  EnsureRandomStateInited();
compiler-rt/lib/hwasan/hwasan_thread.h
98

we don't need it. initialized random_state_ can not be 0, or CHECK(random_buffer_); will fail

morehouse updated this revision to Diff 385100.Nov 5 2021, 9:28 AM
morehouse marked 3 inline comments as done.
  • Remove random_state_inited_.
  • Make unique_id atomic.
  • Move initialization check to cold path.
compiler-rt/lib/hwasan/hwasan_thread.cpp
30

Preincrement causes other issues, since it makes thread numbers start at 1 instead of 0. But we can add 1 to unique_id_ here instead.

Side note: this causes some false negatives in aliasing mode since it changes tags by 1 (and we only have 3 bits entropy). I've tweaked a few tests to avoid the false negatives.

135–136

Done. But then we also need to call EnsureRandomStateInited for the random_tags=false case below.

vitalybuka added inline comments.Nov 5 2021, 10:15 AM
compiler-rt/lib/hwasan/hwasan_thread.cpp
143

this makes random state [unique_id_ + 1, max_int], maybe it's OK
probably cleaner is to threat random_state_ as a trivial counter:

{ 
  // Remove Ensure here
  tag = (++random_state_ + unique_id_) & tag_mask;
}

and now Init can be simplified to

//random_state_ = flags()->random_tags ? RandomSeed() : unique_id_ + 1;
if (flags()->random_tags)
   random_state_ = RandomSeed();
else
  do nothing
vitalybuka added inline comments.Nov 5 2021, 10:19 AM
compiler-rt/lib/hwasan/hwasan.cpp
348

I guess we don't need these calls now?

compiler-rt/lib/hwasan/hwasan_fuchsia.cpp
133

I guess we don't need these calls now?

compiler-rt/lib/hwasan/hwasan_thread.cpp
143
//random_state_ = flags()->random_tags ? RandomSeed() : unique_id_ + 1;
if (flags()->random_tags)
   random_state_ = RandomSeed();
else
  do nothing

or even to if we remove other calls

{
random_state_ = RandomSeed()
}
morehouse marked 2 inline comments as done.Nov 5 2021, 11:40 AM
morehouse added inline comments.
compiler-rt/lib/hwasan/hwasan.cpp
348

InitRandomState also initializes stack ring buffer. We need that inited even if no heap allocs have happened yet.

compiler-rt/lib/hwasan/hwasan_thread.cpp
143

This causes a problem: the stack ring buffer may never be initialized since GenerateRandomTag increments random_state_, therefore causing EnsureRandomStateInited to do nothing when it is called later.

vitalybuka accepted this revision.Nov 5 2021, 1:13 PM
vitalybuka added inline comments.
compiler-rt/lib/hwasan/hwasan_thread.cpp
144

maybe not worth it, random_state_ is u64, so I overflow is not an issue
I assume "tag_mask + 1" is power of 2

This revision is now accepted and ready to land.Nov 5 2021, 1:13 PM
morehouse updated this revision to Diff 385181.Nov 5 2021, 1:56 PM
morehouse marked an inline comment as done.
  • Fix potential issue on random_state_ overflow.
compiler-rt/lib/hwasan/hwasan_thread.cpp
144

It's actually u32.

Applied your suggestion.

vitalybuka added inline comments.Nov 5 2021, 3:33 PM
compiler-rt/lib/hwasan/hwasan_thread.cpp
144

Ouch, looked at random_state_ in wrong file

vitalybuka accepted this revision.Nov 5 2021, 3:33 PM
glider added inline comments.Nov 8 2021, 1:03 AM
compiler-rt/lib/hwasan/hwasan_thread.cpp
135–136

I think it should be okay to random_buffer_ to become zero after generating the next random number (maybe not for xorshift, but quite possible for other RNG implementations that may replace it someday).
Instead of reserving some value, can we just use a separate boolean flag indicating that the RNG is initialized?

compiler-rt/test/hwasan/TestCases/heap-buffer-overflow-into.c
5

Are these changes related to RNG? If not, please split them away to a separate patch.

compiler-rt/test/hwasan/TestCases/heap-buffer-overflow.c
10

Ditto.

morehouse updated this revision to Diff 385492.Nov 8 2021, 7:28 AM
morehouse marked 3 inline comments as done.
  • Reintroduce random_state_inited_ flag
compiler-rt/lib/hwasan/hwasan_thread.cpp
135–136

I agree. The random_state_ == 0 trick seems more complexity/maintenance burden than it's worth. The bool flag won't take up any extra memory anyway, since it fits in alignment padding.

I've reintroduced the inited flag.

This revision was automatically updated to reflect the committed changes.