<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 11, 2017 at 1:25 PM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
On April 11, 2017 at 11:55:12 AM, Kostya Serebryany via llvm-dev<br>
<span class="">(<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>) wrote:<br>
> Evgeniy and I recently discussed something similar for detecting bad casts<br>
> (code named: TypeSanitizer).<br>
> The approach with the shadow memory looked attractive at the first glance,<br>
> but then we've drowned in details.<br>
><br>
> Specifically for TBAA, I had another idea, not involving shadow memory.<br>
> Consider LLVM queries MayAlias(P1, P2) and the result is false, i.e. we<br>
> think that P1 and P2 point to disjoint memory regions.<br>
> Then we insert a run-time check that intervals [P1,sizeof(*P1)) and<br>
> [P2,sizeof(*P2)) don't intersect.<br>
><br>
> For functions with a reasonable number of pointer pairs where MayAlias(P1,<br>
> P2)==false we could insert checks for all such pairs.<br>
<br>
</span>I'm not very clear on how this will fit into TBAA -- I don't think<br>
TBAA decides aliasing relation between pointers, but it decides<br>
aliasing relation between accesses (!tbaa metadata only exists on<br>
accesses).<br></blockquote><div><br></div><div>of course, but accesses are done via pointers, and if TBAA queries MayAlias(AccessViaP1, AccessViaP2)</div><div>there should (??) be a point in the IR where both P1 and P2 exist together and can be compared. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
This means, at least in LLVM IR, you have to account for cases like:<br>
<br>
if (A)<br>
  *(int *)ptr = 20;<br>
if (B)<br>
  float f = *(float *)ptr;<br>
<br>
where ptr does not have a type (according to TBAA), but you want to<br>
crash the program if both A and B are true.<br>
<span class="HOEnZb"><font color="#888888"><br>
-- Sanjoy<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
> For larger functions -- only for those pairs where the optimizer actually<br>
> queried MayAlias(P1, P2).<br>
><br>
> --kcc<br>
><br>
><br>
> On Tue, Apr 11, 2017 at 3:49 AM, Hal Finkel via llvm-dev <<br>
> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
><br>
> ><br>
> > On 04/11/2017 03:46 AM, Andrey Bokhanko wrote:<br>
> ><br>
> > Hal,<br>
> ><br>
> > To clarify, my example meant to illustrate that for memory references to<br>
> > structures' fields you have to keep a user-defined type, even for one byte<br>
> > accesses. C++ allows references to "initial member sequence" using pointers<br>
> > to structures of different types. And yes, there are programs in the wild<br>
> > that rely on this (don't remember details... this was from previous life).<br>
> ><br>
> > Another thing to consider -- what about memset / memcpy / etc that<br>
> > inherently rely on type punning? If not inlined, they don't present<br>
> > problems for an optimizer -- probably shouldn't be considered as aliasing<br>
> > rules violation?<br>
> ><br>
> ><br>
> > Good point. You (likely) wouldn't want to compile your memcpy / memset /<br>
> > etc. implementations with the TBAA sanitizer enabled (or we'd need to<br>
> > provide an attribute to disable it for certain functions). If they only use<br>
> > char* themselves, then it's fine, but if not, that's implementation magic.<br>
> > However, memset, etc. does need to be able to 'unset' the type of memory<br>
> > and memcpy needs to be able to copy types (at least for PODs). The<br>
> > sanitizer would need to hook them for that purpose.<br>
> ><br>
> > -Hal<br>
> ><br>
> ><br>
> ><br>
> > Yours,<br>
> > Andrey<br>
> > ===<br>
> > Compiler Architect<br>
> > NXP<br>
> ><br>
> ><br>
</div></div><div class="HOEnZb"><div class="h5">> > On Tue, Apr 11, 2017 at 12:05 AM, Hal Finkel wrote:<br>
> ><br>
> >><br>
> >> On 04/10/2017 09:55 AM, Andrey Bokhanko wrote:<br>
> >><br>
> >> Hi Hal,<br>
> >><br>
> >> I wonder how your solution will handle the following?<br>
> >><br>
> >> struct {<br>
> >> int s1_f1;<br>
> >> float s1_f2;<br>
> >> int s1_f3;<br>
> >> float s1_f4;<br>
> >> } S1;<br>
> >><br>
> >> struct {<br>
> >> int s2_f1;<br>
> >> float s2_f2;<br>
> >> int *s2_f3; // to add some interest, suppose that sizeof(int) ==<br>
> >> sizeof(int *)<br>
> >> float s2_f4;<br>
> >> } S2;<br>
> >><br>
> >> S1 *s1; S2 *s2;<br>
> >> ...<br>
> >> s2 = (S1*)s1;<br>
> >> s2->s2_f1 = 0; // allowed<br>
> >> s2->s2_f2 = 0; // allowed<br>
> >> s2->s2_f3 = 0; // not allowed<br>
> >> s2->s2_f4 = 0; // not allowed<br>
> >><br>
> >> Also, when you plan to set types for allocated memory?<br>
> >><br>
> >><br>
> >> The most-general thing seems to be to set the types along with a store.<br>
> >> As a result, the proposed scheme would not find a fault with the code<br>
> >> above, but would complain if anyone actually later read S1.s1_f3.<br>
> >><br>
> >> If we want to catch these kinds of problems directly we'd need to have<br>
> >> the compiler insert code when the type is constructed to mark the types,<br>
> >> and then we'd need to check those types around stores. This also sounds<br>
> >> like a useful enhancement (although somewhat more complicated to implement).<br>
> >><br>
> >> What types will be set for memory allocated by a malloc call?<br>
> >><br>
> >><br>
> >> Memory would be untyped (or of unknown type) when allocated.<br>
> >><br>
> >> Thanks again,<br>
> >> Hal<br>
> >><br>
> >><br>
> >><br>
> >> Yours,<br>
> >> Andrey<br>
> >><br>
> >><br>
> >> On Tue, Apr 4, 2017 at 10:13 PM, Hal Finkel via llvm-dev <<br>
> >> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
> >><br>
> >>> Hi everyone,<br>
> >>><br>
> >>> At EuroLLVM, Chandler and I chatted about the design for a potential<br>
> >>> TBAA sanitizer. Here's my attempt to summarize:<br>
> >>><br>
> >>> C/C++ have type-based aliasing rules, and LLVM's optimizer can exploit<br>
> >>> these given TBAA metadata added by Clang. Roughly, a pointer of given type<br>
> >>> cannot be used to access an object of a different type (with, of course,<br>
> >>> certain exceptions). Unfortunately, there's a lot of code in the wild that<br>
> >>> violates these rules (e.g. for type punning), and such code often must be<br>
> >>> built with -fno-strict-aliasing. Performance is often sacrificed as a<br>
> >>> result. Part of the problem is the difficulty of finding TBAA violations. A<br>
> >>> sanitizer would help.<br>
> >>><br>
> >>> A design goal of a TBAA sanitizer is to limit the shadow-memory overhead<br>
> >>> of the implementation. ASan, for example, uses 1 bit per byte. Here we're<br>
> >>> hoping to keep the overhead down to 2 bits per byte for the TBAA<br>
> >>> sanitizing. We might be able to do this, while handling all common types on<br>
> >>> the fast path, if we use both alignment and type information. When<br>
> >>> accessing data of B bytes, 2*B bits of shadow memory can be used. Thus,<br>
> >>> we'll get 2 bits for a one-byte type, 4 bits for a two-byte type, etc.<br>
> >>> Moreover, we need appropriate holes in the encoding space so that no type<br>
> >>> has a shadow encoding that overlaps with an aligned part of a larger type's<br>
> >>> encoding.<br>
> >>> For example, we need to detect:<br>
> >>><br>
> >>> double f = ...; return *(int*) &f; // We should catch this.<br>
> >>><br>
> >>> We might use the following encoding. The idea is that the common case,<br>
> >>> for which we need a reasonable fast path, is that type types are exactly<br>
> >>> equal. For this case, we want a simple comparison of the shadow type<br>
> >>> encodings to be sufficient to validate the access. For cases where the<br>
> >>> encodings don't match (and isn't zero to indicate an unknown type), or for<br>
> >>> which there is no direct encoding for the access type, a slow path must be<br>
> >>> used. All of this assumes that we're validating the the pointer alignment<br>
> >>> first, and then checking the type encodings.<br>
> >>><br>
> >>> 1 Byte:<br>
> >>> 00 = 0 = unknown type<br>
> >>> 01 = 1 = hole<br>
> >>> 10 = 2 = hole<br>
> >>> 11 = 3 = all one-byte types (slow path, see note later on this)<br>
> >>><br>
> >>> 2 Bytes:<br>
> >>> 0000 = 0 = unknown type<br>
> >>> 0101 = 5 = short<br>
> >>> 0110 = 6 = hole (A)<br>
> >>> 0111 = 7 = wchar_t (under some ABIs)<br>
> >>> 1001 = 9 = hole (B)<br>
> >>> 1010 = 10 = hole (C)<br>
> >>> 1011 = 11 = char16_t<br>
> >>> 1111 = 15 = all other types (slow path)<br>
> >>><br>
> >>> It is important here to have wchar_t have a direct encoding here because<br>
> >>> wchar_t is two bytes on Windows, and moreover, wchar_t is very commonly<br>
> >>> used on Windows. The partial encoding overlap of wchar_t (i.e. 0111) with<br>
> >>> the 11 one-byte-type encoding works because 11 always indicates a slow-path<br>
> >>> check.<br>
> >>><br>
> >>> 4 Bytes:<br>
> >>> 0000 0000 = 0 = unknown type<br>
> >>> A A = int<br>
> >>> A B = float<br>
> >>> B A = pointer (under some ABIs)<br>
> >>> B B = long (under some ABIs)<br>
> >>> A 1111 = wchar_t (under some ABIs)<br>
> >>> B 1111 = char32_t<br>
> >>> A C = hole (D)<br>
> >>> C A = hole (E)<br>
> >>> B C = hole (F)<br>
> >>> C B = hole (G)<br>
> >>> C C = hole (H)<br>
> >>> 1111 1111 = 255 = all other types (slow path)<br>
> >>><br>
> >>> 8 Bytes:<br>
> >>> 0000 0000 0000 0000 = 0 = unknown type<br>
> >>> D D = double<br>
> >>> D E = long (under some ABIs)<br>
> >>> E D = long long (under some ABIs)<br>
> >>> E E = long double (under some ABIs)<br>
> >>> D F = pointer (under some ABIs)<br>
> >>> F D = hole (I)<br>
> >>> E F = hole (J)<br>
> >>> F E = hole<br>
> >>> F F = hole<br>
> >>> ...<br>
> >>> 1111 1111 1111 1111 = 65535 = all other types<br>
> >>><br>
> >>> 16 Bytes:<br>
> >>> 0 = unknown type<br>
> >>> | | = __int128_t<br>
> >>> I J = long long (under some ABIs)<br>
> >>> J I = long double (under some ABIs)<br>
> >>> J J = hole<br>
> >>> ...<br>
> >>> -1 = all other types<br>
> >>><br>
> >>> For pointers, this scheme would consider all pointers to be the same<br>
> >>> (regardless of pointee type). Doing otherwise would mostly requiring<br>
> >>> putting pointer-type checking on the slow path (i.e. access via a pointer<br>
> >>> pointer), and that could add considerable overhead. We might, however,<br>
> >>> split out function pointers from other pointers. We could provide a<br>
> >>> compile-time option to control the granularity of pointer-type checks.<br>
> >>><br>
> >>> Builtin vector types for which the vector element type has a direct<br>
> >>> encoding also naturally have a direct encoding (the concatenation of the<br>
> >>> encoding for the element type).<br>
> >>><br>
> >>> Obviously the fact that we have no fast-path encodings for one-byte<br>
> >>> types could be problematic. Note however that:<br>
> >>><br>
> >>> 1. If a larger type is being used to access a smaller type (plus more),<br>
> >>> the encodings won't match, so we always end up on the slow path.<br>
> >>><br>
> >>> 2. If the access type is a one-byte type, we would want to validate<br>
> >>> quickly. However, most common one-byte types are universally aliasing (i.e.<br>
> >>> not subject to TBAA violations). Specifically, for C/C++, pointers to char,<br>
> >>> unsigned char, signed char (C only), and std::byte, can be used to access<br>
> >>> any part of any type. That leaves signed char (C++ only), bool/_Bool, and<br>
> >>> enums with a [signed/unsigned] char base type (C++ only, std::byte<br>
> >>> exempted) as pointee types we might wish to validate. We'd always need to<br>
> >>> fall back to the slow path to validate these. We could provide a<br>
> >>> compile-time option to disable such one-byte access checking if necessary.<br>
> >>><br>
> >>> How would the slow path work? First, the code needs to find the<br>
> >>> beginning of the allocation. It can do this by scanning backwards in the<br>
> >>> ASan shadow memory. Once located, we'll read a pointer to a<br>
> >>> type-description structure from that "red zone" location. For dynamic<br>
> >>> allocations, ASan's allocator will ensure such a space for the pointer<br>
> >>> exists. For static allocations and globals, the compiler will ensure it<br>
> >>> exists. The compiler will make sure that all constructors locate this field<br>
> >>> and fill it in. Destructors can clear it. If two of these<br>
> >>> type-description-structure pointers are equal, then we can conclude that<br>
> >>> the types are equal. If not, then we need to interpret the structure. The<br>
> >>> pointer itself might be to an interval map (to deal with arrays, placement<br>
> >>> new, etc. - we can use the low bit of the pointer to differentiate between<br>
> >>> an actual type-description structure and an interval map), and the leaves<br>
> >>> of the interval map point to actual type-description structures. The<br>
> >>> type-description structure is an array of (offset, type) pairs, where the<br>
> >>> type field is also a type-description-structure pointer. The<br>
> >>> type-description structures themselves are comdat globals emitted in each<br>
> >>> relevant translation unit, where the comdat key is formed using the mangled<br>
> >>> type name (and size, etc.), and pointers to these symbols are then used to<br>
> >>> identify the types.<br>
> >>><br>
> >>> Thoughts?<br>
> >>><br>
> >>> Thanks again,<br>
> >>> Hal<br>
> >>><br>
> >>> --<br>
> >>> Hal Finkel<br>
> >>> Lead, Compiler Technology and Programming Languages<br>
> >>> Leadership Computing Facility<br>
> >>> Argonne National Laboratory<br>
> >>><br>
> >>> ______________________________<wbr>_________________<br>
> >>> LLVM Developers mailing list<br>
> >>> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
> >>> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
> >>><br>
> >><br>
> >><br>
> >> --<br>
> >> Hal Finkel<br>
> >> Lead, Compiler Technology and Programming Languages<br>
> >> Leadership Computing Facility<br>
> >> Argonne National Laboratory<br>
> >><br>
> >><br>
> ><br>
> > --<br>
> > Hal Finkel<br>
> > Lead, Compiler Technology and Programming Languages<br>
> > Leadership Computing Facility<br>
> > Argonne National Laboratory<br>
> ><br>
> ><br>
> > ______________________________<wbr>_________________<br>
> > LLVM Developers mailing list<br>
> > <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
> > <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
> ><br>
> ><br>
> ______________________________<wbr>_________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
><br>
</div></div></blockquote></div><br></div></div>