Page MenuHomePhabricator

[TySan] A Type Sanitizer (LLVM)
Needs ReviewPublic

Authored by CJ-Johnson on Apr 18 2017, 4:04 PM.

Details

Summary

This patch introduces the LLVM components of a type sanitizer: a sanitizer for type-based aliasing violations.

C/C++ have type-based aliasing rules, and LLVM's optimizer can exploit these given TBAA metadata added by Clang. Roughly, a pointer of given type cannot be used to access an object of a different type (with, of course, certain exceptions). Unfortunately, there's a lot of code in the wild that violates these rules (e.g. for type punning), and such code often must be built with -fno-strict-aliasing. Performance is often sacrificed as a result. Part of the problem is the difficulty of finding TBAA violations. Hopefully, this sanitizer will help.

For each TBAA type-access descriptor, encoded in LLVM's IR using metadata, the corresponding instrumentation pass generates descriptor tables. Thus, for each type (and access descriptor), we have a unique pointer representation. Excepting anonymous-namespace types, these tables are comdat, so the pointer values should be unique across the program. The descriptors refer to other descriptors to form a type aliasing tree (just like LLVM's TBAA metadata does). The instrumentation handles the "fast path" (where the types match exactly and no partial-overlaps are detected), and defers to the runtime to handle all of the more-complicated cases. The runtime, of course, is also responsible for reporting errors when those are detected.

The runtime uses essentially the same shadow memory region as tsan, and we use 8 bytes of shadow memory, the size of the pointer to the type descriptor, for every byte of accessed data in the program. The value 0 is used to represent an unknown type. The value -1 is used to represent an interior byte (a byte that is part of a type, but not the first byte). The instrumentation first checks for an exact match between the type of the current access and the type for that address recorded in the shadow memory. If it matches, it then checks the shadow for the remainder of the bytes in the type to make sure that they're all -1. If not, we call the runtime. If the exact match fails, we next check if the value is 0 (i.e. unknown). If it is, then we check the shadow for the remainder of the byes in the type (to make sure they're all 0). If they're not, we call the runtime. We then set the shadow for the access address and set the shadow for the remaining bytes in the type to -1 (i.e. marking them as interior bytes). If the type indicated by the shadow memory for the access address is neither an exact match nor 0, we call the runtime.

The instrumentation pass inserts calls to the memset intrinsic to set the memory updated by memset, memcpy, and memmove, as well as allocas/byval (and for lifetime.start/end) to reset the shadow memory to reflect that the type is now unknown. The runtime intercepts memset, memcpy, etc. to perform the same function for the library calls.

The runtime essentially repeats these checks, but uses the full TBAA algorithm, just as the compiler does, to determine when two types are permitted to alias. In a situation where access overlap has occurred and aliasing is not permitted, an error is generated.

Clang's TBAA representation currently has a problem representing unions, as demonstrated by the one XFAIL'd test in the runtime patch. We'll update the TBAA representation to fix this, and at the same time, update the sanitizer.

When the sanitizer is active, we disable actually using the TBAA metadata for AA. This way we're less likely to use TBAA to remove memory accesses that we'd like to verify.

As a note, this implementation does not use the compressed shadow-memory scheme discussed previously (http://lists.llvm.org/pipermail/llvm-dev/2017-April/111766.html). That scheme would not handle the struct-path (i.e. structure offset) information that our TBAA represents. I expect we'll want to further work on compressing the shadow-memory representation, but I think it makes sense to do that as follow-up work.

Diff Detail

Event Timeline

hfinkel created this revision.Apr 18 2017, 4:04 PM

As a note: As follow-up work, we might want to extend Clang to add TBAA metadata to allocas and lifetime.start intrinsics so that the instrumentation pass can mark the types of memory upon declaration/construction instead of only upon first access.

pcc added a subscriber: pcc.Apr 19 2017, 10:05 AM
hfinkel updated this revision to Diff 96139.Apr 21 2017, 7:21 AM
hfinkel retitled this revision from [TBAASan] A TBAA Sanitizer (LLVM) to [TySan] A Type Sanitizer (LLVM).
hfinkel edited the summary of this revision. (Show Details)

Rename TBAASanitizer -> TypeSanitizer

hfinkel updated this revision to Diff 96265.Apr 21 2017, 5:18 PM

Mark the types of globals in a generated ctor-called function. memcpy/memmove should do the corresponding thing for the type shadow data.

hfinkel updated this revision to Diff 117620.Oct 3 2017, 8:43 PM

Rebased.

CJ-Johnson commandeered this revision.Jan 2 2020, 8:09 AM
CJ-Johnson added a reviewer: hfinkel.
CJ-Johnson added a subscriber: CJ-Johnson.

After discussing things with Hal, I'm going to take over these diffs and try to update them to the new pass manager :)

jgorbe added a subscriber: jgorbe.Jun 18 2020, 6:29 PM

Hello to everyone following along! My apologies for the lack of activity; I should have made a comment sooner.

Back in December/January I was exploring working on TySan (met with Hal and Richard, in addition to rebasing the diffs). After digging into the problem space, it became clear that it's not something I could prioritize over other works. Since that time, nothing has changed on my end, so I don't expect to continue working on this.

If anyone is interested in picking this up, I would be thrilled! - CJ

fhahn added a subscriber: fhahn.Jul 16 2020, 5:32 AM

Hello to everyone following along! My apologies for the lack of activity; I should have made a comment sooner.

Back in December/January I was exploring working on TySan (met with Hal and Richard, in addition to rebasing the diffs). After digging into the problem space, it became clear that it's not something I could prioritize over other works. Since that time, nothing has changed on my end, so I don't expect to continue working on this.

If anyone is interested in picking this up, I would be thrilled! - CJ

Thanks for looking into the patch! If there's any insight you found that could be helpful, it might be useful to whomever looks at this in the future if it could be recorded somewhere.

@fhahn We don't currently enable -fstrict-aliasing at Google. I was exploring what it would take for us to get strict-aliasing clean. Unfortunately, after running some of our internal benchmarks, I found that there was little to no performance benefit.

In addition, running internal tests showed no failures, implying that the behavior had gone unchanged (at least for the unit tests I ran, which was not an insignificant amount). That being the case, it's conceivable that some cases are not being caught in the optimizer, though I'm not familiar enough with it to say for sure, nor do I have specific re-pro examples. I was simply trying to see "is this something we can turn on?" and was unable to find a benefit for doing so at this time.

I would love for someone to take a look at TySan and TBAA optimization in LLVM!

aganea added a subscriber: aganea.Jun 3 2021, 2:25 PM
Enna1 added a subscriber: Enna1.Oct 11 2021, 3:44 AM
fhahn updated this revision to Diff 418960.Mar 29 2022, 12:45 PM

I would love for someone to take a look at TySan and TBAA optimization in LLVM!

I was able to rebase the patch & also port the pass to the new pass manager. There's still a test failure, but I plan to resolve that soon as well.

Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptMar 29 2022, 12:45 PM
MaskRay added a subscriber: MaskRay.Jun 5 2022, 3:26 PM
MaskRay added inline comments.
llvm/include/llvm/IR/Attributes.td
339
llvm/include/llvm/InitializePasses.h
449 ↗(On Diff #418960)

Remove the legacy pass

llvm/lib/Transforms/Instrumentation/TypeSanitizer.cpp
208

static const char LUT[] = ...

215

excess blank line

489

ditto everywhere

llvm/test/Instrumentation/TypeSanitizer/basic.ll
2

Switch to opaque pointers (https://llvm.org/docs/OpaquePointers.html)

353

ditto everywhere

fhahn updated this revision to Diff 434425.Jun 6 2022, 4:18 AM

Address latest comments. Also remove calls to deprecated getPointerElementType, remove legacy pass, update test to use opqaue pointers.

fhahn updated this revision to Diff 435507.Jun 9 2022, 4:58 AM

Only set comdat for globals for ELF, append to globals array.

fhahn updated this revision to Diff 440262.Jun 27 2022, 9:25 AM

Rebased, fixed some crashes exposed when using it on llvm-test-suite. With this version, check-tysan (tests from D32197) pass on macOS.