Page MenuHomePhabricator

[hwasan] Do not instrument accesses to uninteresting allocas.
ClosedPublic

Authored by fmayer on Aug 20 2021, 5:03 AM.

Details

Summary

This leads to a statistically significant improvement when using -hwasan-instrument-stack=0: https://bit.ly/3AZUIKI.
When enabling stack instrumentation, the data appears gets better but not statistically significantly so. This is consistent
with the very moderate improvements I have seen for stack safety otherwise, so I expect it to improve when the underlying
issue of that is resolved.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
fmayer updated this revision to Diff 368055.Aug 23 2021, 3:22 AM

add test

fmayer updated this revision to Diff 368113.Aug 23 2021, 8:10 AM

allow to control strictness of alloc matching

fmayer updated this revision to Diff 368118.Aug 23 2021, 8:21 AM

remove comment

fmayer published this revision for review.Aug 23 2021, 8:23 AM
fmayer added a reviewer: eugenis.
Herald added a project: Restricted Project. · View Herald TranscriptAug 23 2021, 8:23 AM
fmayer updated this revision to Diff 368120.Aug 23 2021, 8:40 AM

simplify code

I don't like the new flag. If we want this as a mitigation, IMHO it's a bad idea to allow overflows from stack. Even constant sized ones. Well, maybe reasonably small constant overflows are ok.

Consider adopting AddressSanitizer::isSafeAccess instead.

In face, isSafeAccess seems pretty limited. Surely ScalarEvolution (similar to how it is used in StackSafetyAnalysis) can capture more cases, including a non-constant offset that can be proven to be within range?

fmayer updated this revision to Diff 370554.Sep 3 2021, 5:23 AM

rework to address comment

fmayer added a comment.Sep 3 2021, 5:24 AM

In face, isSafeAccess seems pretty limited. Surely ScalarEvolution (similar to how it is used in StackSafetyAnalysis) can capture more cases, including a non-constant offset that can be proven to be within range?

Done. PTAL.

What I do right now is not emit any checks when we can we disable stack instrumentation and we can trace back an operation to an alloca. While we could potentially overflow towards other regions, I think it is not unexpected that we do not catch this if stack instrumentation is disabled. What do you think?

This is pretty cool, I thought it would be more complicated.

This change needs comprehensive tests in llvm/test/Analysis/StackSafetyAnalysis. Update the print() method to show safe/unsafe instructions (or maybe only list known safe instruction).

What if an instruction may access either stack or heap?

i32 *p = flag ? p_heap_i16 : &stack_i32;
*p = 42;

The analysis will say "safe" because it is only scanning from the stack roots.
This should probably be fixed in hwasan by tracking the underlying alloca.

fmayer updated this revision to Diff 370869.Sep 6 2021, 2:38 AM

handle stores that might or might not use an alloca

fmayer added a comment.Sep 6 2021, 2:38 AM

What if an instruction may access either stack or heap?

i32 *p = flag ? p_heap_i16 : &stack_i32;
*p = 42;

The analysis will say "safe" because it is only scanning from the stack roots.
This should probably be fixed in hwasan by tracking the underlying alloca.

Ah yes, I did handle this but then accidentally lost that when I refactored around some stuff. Put that back and added an IR test.

fmayer updated this revision to Diff 370870.Sep 6 2021, 2:43 AM

don't use argument in select test

fmayer added a comment.EditedSep 6 2021, 5:56 AM

What if an instruction may access either stack or heap?

i32 *p = flag ? p_heap_i16 : &stack_i32;
*p = 42;

The analysis will say "safe" because it is only scanning from the stack roots.
This should probably be fixed in hwasan by tracking the underlying alloca.

Ah yes, I did handle this but then accidentally lost that when I refactored around some stuff. Put that back and added an IR test.

Thinking again I remembered why I removed the explicit case for this during the refactoring: in this case, SCEV will not be able to calculate an in-range offset between the operant of the store and the alloca, so it will not be judged a safe access

fmayer updated this revision to Diff 370948.Sep 6 2021, 11:51 AM

add tests for stack safety analysis

fmayer added a comment.EditedSep 7 2021, 7:25 AM

EDIT: I ran pdfium benchmarks and had some results here, but I spoke too early and need to run some more.

@vitalybuka

Ideas for more analysis tests:

  • unsafe alloca with a mix of safe and unsafe accesses
  • memcpy that is safe on one side and unsafe on the other. Either between two allocas, or within the same (memmove?). Or between alloca and non-stack memory.

What if an instruction may access either stack or heap?

i32 *p = flag ? p_heap_i16 : &stack_i32;
*p = 42;

The analysis will say "safe" because it is only scanning from the stack roots.
This should probably be fixed in hwasan by tracking the underlying alloca.

Ah yes, I did handle this but then accidentally lost that when I refactored around some stuff. Put that back and added an IR test.

Thinking again I remembered why I removed the explicit case for this during the refactoring: in this case, SCEV will not be able to calculate an in-range offset between the operant of the store and the alloca, so it will not be judged a safe access

Right, of course. Any reachable instruction we would require to be *always* within the alloca range.

llvm/lib/Analysis/StackSafetyAnalysis.cpp
836 ↗(On Diff #370961)

This affect compilation time and memory. Ideally we would not do it if the client can not use this info (ex. MTE).

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp
787

if (findAllocaForValue(Ptr)) return true;

fmayer updated this revision to Diff 371276.Sep 8 2021, 1:45 AM

address comment

fmayer updated this revision to Diff 371279.Sep 8 2021, 1:55 AM
fmayer marked an inline comment as done.

remove unnecessary check

fmayer updated this revision to Diff 371342.Sep 8 2021, 8:17 AM

only calculate address information when needed.

fmayer marked an inline comment as done.Sep 8 2021, 8:17 AM
fmayer updated this revision to Diff 371347.Sep 8 2021, 8:31 AM

revert unneeded change

fmayer updated this revision to Diff 371382.Sep 8 2021, 10:03 AM

clang format

still missing test cases for combinations of mixed safe/unsafe accesses

llvm/include/llvm/Analysis/StackSafetyAnalysis.h
69 ↗(On Diff #371382)

you want either DenseMap or SmallPtrSet here. std::map is unnecessarily ordered, logarithmic, and wastes memory

vitalybuka added inline comments.Sep 8 2021, 1:59 PM
llvm/include/llvm/Analysis/StackSafetyAnalysis.h
67 ↗(On Diff #371382)

why do we need bool if missing instruction is equivalent to false?
std::set?

67 ↗(On Diff #371382)

just std::map<const Instruction *, bool>Accesses;

InfoTy in unique_ptr to avoid exposing it into the header.

69 ↗(On Diff #371382)

std set/map seems fine
class is movable, DenseMap or SmallPtrSet don't support efficient move.

69 ↗(On Diff #371382)

I don't see value in ::getAccesses when accessIsSafe can access the field.

llvm/lib/Analysis/StackSafetyAnalysis.cpp
136–139 ↗(On Diff #371382)

Less boilerplate this way:
auto Ins = Accesses.emplace(I, R);
Then use Ins.first and Ins.second where needed.

141–143 ↗(On Diff #371382)

the point of <it, bool> result that you can update if insert failed and avoid the second lookup

455 ↗(On Diff #371382)

may I ask you to extract two NFC patches which you can land without review:

  1. break -> return !US.Range.isFullSet(); I assume no tests need updates.
  2. Wrap updateRange into trivial:
void addRange(I, R) {
   // the rest you will add in D108457
   updateRange(R);
 }

I assume also not tests should be affected.

813 ↗(On Diff #371382)

this is a separate NFC patch

826 ↗(On Diff #371382)

so we lazily construct this on the request
if so I am pretty sure we can have sorted std::vector<Instruction*> Accesses for free;
and accessIsSafe can use std::binary_search and it will be faster then map/set lookups.

836 ↗(On Diff #370961)

I am a little bit skeptical that we can measure a difference. I'd rather keep it simple.

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp
290

HWAsan and related tests should be in a separate patch

fmayer updated this revision to Diff 371581.Sep 9 2021, 6:48 AM
fmayer marked 9 inline comments as done.

split change

fmayer added a comment.Sep 9 2021, 6:49 AM

I split the stack safety change to D109503 and added more tests to that.

llvm/include/llvm/Analysis/StackSafetyAnalysis.h
67 ↗(On Diff #371382)

While I build this up, there are two cases:

the instruction hadn't been considered yet
the instruction was considered but wasn't safe.
This allows to conveniently keep them apart.

67 ↗(On Diff #371382)

I reverted to calculating this in getInfo and putting it into the InfoTy.

@eugenis is that okay?

llvm/lib/Analysis/StackSafetyAnalysis.cpp
141–143 ↗(On Diff #371382)

That doesn't work, because it's not move constructible (I think, I don't fully remember what exactly it complained about when I did that).

455 ↗(On Diff #371382)

Actually no one looks at the return value, so I just made it void.

836 ↗(On Diff #370961)

I reverted it to what it was before for simplicity. We can change it again later if it becomes a problem.

fmayer updated this revision to Diff 371583.Sep 9 2021, 7:06 AM

remove unnecessary check (again)

eugenis accepted this revision.Sep 9 2021, 1:27 PM

LGTM

llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp
786

I'm still on the fence about this. A stack pointer can be used to access heap if the offset is attacker controlled, but that sounds a bit exotic.

But let's land it like this for now.

One thing I'd like to explore is applying the same SCEV computation as in StackSafetyAnalysis and excluding instrumentation for anything with offset provably within 32 bits or less - that should be reasonably common (indices are often int, not long) and safe (heap is unlikely to be within 4Gb from stack on 64-bit).

This revision is now accepted and ready to land.Sep 9 2021, 1:27 PM
fmayer marked an inline comment as done.Sep 10 2021, 8:12 AM