[llvm-dev] [RFC] Design of a TBAA sanitizer (original) (raw)

Hal Finkel via llvm-dev llvm-dev at lists.llvm.org
Wed Apr 12 15:49:07 PDT 2017

On 04/12/2017 05:09 AM, Stephen Kell wrote:

A design goal of a TBAA sanitizer is to limit the shadow-memory overhead of the implementation. ASan, for example, uses 1 bit per byte. Here we're hoping to keep the overhead down to 2 bits per byte for the TBAA sanitizing. We might be able to do this, while handling all common types on the fast path, if we use both alignment and type information. Slightly provocative question, but are you sure that byte-scale shadow memory is a good fit? Am I sure? No. But I think that is because I'd like to avoid false positives, and that means dealing with places where we dynamically change the type of part of an allocation (via placement new or whatever). This certainly seems necessary to deal with some C++ containers at least. (Sorry for the delayed response. Short summary is "I agree with you" but wanted to pick some nits/details anyway. :-) Can you elaborate on the C++ containers thing? If it's just std::variant and things like std::any that use alignedstoraget, then see below.

Those are what come to mind (although in general it is legal to partially end the lifetime of an allocated array by placement-newing over parts of it).

The dynamically-changing-types thing seems to work okay in both cases. In my runtime it is possible to change the recorded type of a heap allocation, and to create new types at run time. So there are levers to deal with the "part of an allocation" thing, though it does get a bit ugly. (At present, a bit more engineering is necessary to support this trick for stack objects, e.g. to do placement new on them... but I see no real problem supporting it.) I can see the simplicity benefits of shadow memory, so I'm not arguing too hard against it -- just feeling my way around the issues....

Just so I'm understanding: is this talking about shadowing memory with its "leaf" type only, or with its "top-level" type? So if I have, say, the following usually-64-bit type:

struct compound { int x; float y; } ... would we paint the shadow area with an alternating pattern of int (0110 0110) and floats (0110 1001)? Or would we be using the "all other types" thing since the memory is actually "compound"? I intended to imply that we'd fill with the alternating pattern indicating int and float. Understood. I'm now scratching my head about whether that sacrifices the ability to detect UB where the problematic "access" is of a composite type. Passing a struct to a function is a kind of access that comes to mind. (I'm wavering about "object" versus "subobject", a distinction which I have never properly understood in C11....)

Yea. I'm currently concerned that this compact scheme does not really work because it can't capture the semantics contained in our struct-path TBAA (which is, I believe, equivalent to your point here), which means that we might not catch violations of properties on which the optimizer might otherwise rely.

For pointers, this scheme would consider all pointers to be the same (regardless of pointee type). Doing otherwise would mostly requiring putting pointer-type checking on the slow path (i.e. access via a pointer pointer), and that could add considerable overhead. We might, however, split out function pointers from other pointers. We could provide a compile-time option to control the granularity of pointer-type checks. Aha, the pointers-to-pointers problem. Treating all pointers the same feels like a mistake because, say, aliasing a T* through a void** is frequently done and really quite useful (although technically UB, if I understand correctly; is this exploited in LLVM? I don't know if it is exploited by LLVM, although as I recall, all implementations of posixmemalign and similar functions potentially run afoul of the rules (because they need to store the new pointer as a void* regardless of what it actually is). I think returning a pointer like posixmemalign() does it is okay -- the client just has to declare the written-to pointer as a void*. If they want a different type of pointer, they have to do a cast/assignment after the call. So it's clients that are in danger of UB here... they might use it the sloppy way, by casting a T** to void**. Of course, not doing this gets tedious in some cases, e.g. when calling generic linked-structure routines written in C. I'm not sure how strict we can be here in practice. Currently, AFAIKT, Clang emits TBAA metadata which does not differentiate between pointer types (it calls them all "any pointer"). Interesting -- I should take a look at this (thanks). ), whereas aliasing a T* through an arbitrary S** is probably a bug.

Just for contrast: I'm familiar with this problem, and my way around this comes in a few parts. I check pointer creation (casts) only; checks on pointer use (dereference) are unnecessary. Usually it takes a while before people believe me on this, but the short story is that pointer-creation checks enforce an invariant that no bad-type pointer gets into circulation. So dereferences are always okay (until the first warning, at least; execution can continue after a warning, in a best-effort no-guarantees fashion). This also greatly helps performance. I'm sure this is true, but the problem is that C/C++ don't actually outlaw such pointer casts. As you also mention below, it only becomes a problem if such pointers are used to access an object of some incompatible type. If the sanitizer has false positives then it is not nearly as useful to me, even though the technique you describe might actually find more bugs. Fair point. For what it's worth, I do also care a lot about minimising false positives, and there's a trick I should have mentioned: issuing a "trap pointer" when a bad cast occurs, to delay warnings until it's used. On x86-64 this just means flipping some high-order bits so we get a non-canonical address that can be losslessly converted back to the real address. Trap bits are erased for pointer comparisons, or on casts back to a good type. If a trap pointer is used (definitely a bug!), the segfault handler generates a sensible warning message, decodes the faulting instruction, "de-traps" the relevant pointer in the saved register file, and resumes the program. (This could work a bit better than it currently does; happy to elaborate.)

This makes sense. Thanks for mentioning this.

Thoughts? My high-level thought is the following question. Is the plan fixed on developing a tool specifically for C/C++ effective-type rules, i.e. focused on catching/fixing those particular cases of UB and with the goal of improving user code performance? Or is there any interest in the overlapping but distinct problem of helping users detect and debug bad-pointer problems of a type flavour (i.e. those that are not bounds errors or temporal errors)? My goal is the former, although I certainly believe there is also value in the latter. Understood. Plenty of pointer bugs are not UB... e.g. for any heap allocation ("object without a declared type", in C11-speak) I'm allowed to scribble over it, thereby changing its effective type. It's only UB if I read it with its previous effective type. Yes. But the scribbling itself is fairly likely to be the bug, Agreed. However, there are also legitimate use cases, and implementations of standard types (variant, any, etc.) may actually do this. I agree that there is some risk of false positives here, but I think the range of problematic code is really small and does not include the cases you mention. The core issue is whether type-changing writes should need to be flagged specially in the code somehow, allowing them to be instrumented appropriately, or whether arbitrary writes must be able to silently change effective types. A 100% faithful adherence to standard C does require the latter. However, I don't think C++ std::variant or std::any are examples of code that do this, because they pretty much have to use unions and/or placement new, which are both ways of doing the flagging.

Good point.

I do know some C code that relies on silently type-changing writes. In fact in SPEC CPU2006 alone there are two cases -- one in bzip2, one in lbm. The lbm case is bonkers and really should be a union. In the bzip2 case it is arguably sane; my tentative fix is to add a realloc() on the heap array with a different type but the same size -- basically my hacked-up C version of signalling a "placement new". In general, relying on the "no declared type" property of heap storage is pretty fragile, because code suddenly becomes UB if you refactor it so that a heap object becomes a stack or static object. So asking users to manually suppress these warnings doesn't seem unreasonable to me, just as writing your own memcpy() would do... although no doubt opinions differ. (I admit I haven't tried much C++ or standard-library code yet with my system. Also, for full disclosure: currently I do not have great support for unions... although it errs on the side of avoiding false positives, and I think I've figured out how it can be made to work precisely.)

because programmers rarely want to change the type of an allocation mid-lifetime. Meanwhile, many pointer-type problems are too indirect or complex for the compiler to actually do TBAA-derived optimisation on, leaving little to be gained from the UB/TBAA point of view... but again, plenty from the debugging perspective. I suspect the biggest value of any tool, even if geared specifically towards TBAA, will turn out to be largely in debugging scenarios more general than effective-type UB bugs. My motivation is to help people who are currently forced to build their code with -fno-strict-aliasing figure out what needs to be fixed in their code so they don't need to do that. Thanks for the clarification. This was good feedback. Your work is indeed focused on a slightly different problem. It could be interesting and useful to have both. I will happily agree with this, despite the above nitpicks. :-) And (no obligation but) I'd love to be directed towards any further problematic/awkward code not covered by the above.

Me too :-) - We might find out...

-Hal

Stephen

-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory

More information about the llvm-dev mailing list