[llvm-dev] [RFC] Design of a TBAA sanitizer

[Andrey Bokhanko via llvm-dev]

Hi Hal,

I wonder how your solution will handle the following?

struct {
  int s1_f1;
  float s1_f2;
  int s1_f3;
  float s1_f4;
} S1;

struct {
  int s2_f1;
  float s2_f2;
  int *s2_f3; // to add some interest, suppose that sizeof(int) ==
sizeof(int *)
  float s2_f4;
} S2;

S1 *s1; S2 *s2;
...
s2 = (S1*)s1;
s2->s2_f1 = 0; // allowed
s2->s2_f2 = 0; // allowed
s2->s2_f3 = 0; // not allowed
s2->s2_f4 = 0; // not allowed

Also, when you plan to set types for allocated memory? What types will be
set for memory allocated by a malloc call?

Yours,
Andrey


On Tue, Apr 4, 2017 at 10:13 PM, Hal Finkel via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> Hi everyone,
>
> At EuroLLVM, Chandler and I chatted about the design for a potential TBAA
> sanitizer. Here's my attempt to summarize:
>
> 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. A
> sanitizer would help.
>
> 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. When
> accessing data of B bytes, 2*B bits of shadow memory can be used. Thus,
> we'll get 2 bits for a one-byte type, 4 bits for a two-byte type, etc.
> Moreover, we need appropriate holes in the encoding space so that no type
> has a shadow encoding that overlaps with an aligned part of a larger type's
> encoding.
> For example, we need to detect:
>
>   double f = ...; return *(int*) &f; // We should catch this.
>
> We might use the following encoding. The idea is that the common case, for
> which we need a reasonable fast path, is that type types are exactly equal.
> For this case, we want a simple comparison of the shadow type encodings to
> be sufficient to validate the access. For cases where the encodings don't
> match (and isn't zero to indicate an unknown type), or for which there is
> no direct encoding for the access type, a slow path must be used. All of
> this assumes that we're validating the the pointer alignment first, and
> then checking the type encodings.
>
> 1 Byte:
> 00 = 0  = unknown type
> 01 = 1 = hole
> 10 = 2 = hole
> 11 = 3  = all one-byte types (slow path, see note later on this)
>
> 2 Bytes:
> 0000 = 0 = unknown type
> 0101 = 5 = short
> 0110 = 6 = hole (A)
> 0111 = 7 = wchar_t (under some ABIs)
> 1001 = 9 = hole (B)
> 1010 = 10 = hole (C)
> 1011 = 11 = char16_t
> 1111 = 15 = all other types (slow path)
>
> It is important here to have wchar_t have a direct encoding here because
> wchar_t is two bytes on Windows, and moreover, wchar_t is very commonly
> used on Windows. The partial encoding overlap of wchar_t (i.e. 0111) with
> the 11 one-byte-type encoding works because 11 always indicates a slow-path
> check.
>
> 4 Bytes:
> 0000 0000 = 0 = unknown type
> A A = int
> A B = float
> B A  = pointer (under some ABIs)
> B B = long (under some ABIs)
> A 1111 = wchar_t (under some ABIs)
> B 1111 = char32_t
> A C = hole (D)
> C A = hole (E)
> B C = hole (F)
> C B = hole (G)
> C C = hole (H)
> 1111 1111 = 255 = all other types (slow path)
>
> 8 Bytes:
> 0000 0000 0000 0000 = 0 = unknown type
> D D = double
> D E = long (under some ABIs)
> E D = long long (under some ABIs)
> E E = long double (under some ABIs)
> D F = pointer (under some ABIs)
> F D = hole (I)
> E F = hole (J)
> F E = hole
> F F = hole
> ...
> 1111 1111 1111 1111 = 65535 = all other types
>
> 16 Bytes:
> 0 = unknown type
> | | = __int128_t
> I J = long long (under some ABIs)
> J I = long double (under some ABIs)
> J J = hole
> ...
> -1 = all other types
>
> 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.
>
> Builtin vector types for which the vector element type has a direct
> encoding also naturally have a direct encoding (the concatenation of the
> encoding for the element type).
>
> Obviously the fact that we have no fast-path encodings for one-byte types
> could be problematic. Note however that:
>
>  1. If a larger type is being used to access a smaller type (plus more),
> the encodings won't match, so we always end up on the slow path.
>
>  2. If the access type is a one-byte type, we would want to validate
> quickly. However, most common one-byte types are universally aliasing (i.e.
> not subject to TBAA violations). Specifically, for C/C++, pointers to char,
> unsigned char, signed char (C only), and std::byte, can be used to access
> any part of any type. That leaves signed char (C++ only), bool/_Bool, and
> enums with a [signed/unsigned] char base type (C++ only, std::byte
> exempted) as pointee types we might wish to validate. We'd always need to
> fall back to the slow path to validate these. We could provide a
> compile-time option to disable such one-byte access checking if necessary.
>
> How would the slow path work? First, the code needs to find the beginning
> of the allocation. It can do this by scanning backwards in the ASan shadow
> memory. Once located, we'll read a pointer to a type-description structure
> from that "red zone" location. For dynamic allocations, ASan's allocator
> will ensure such a space for the pointer exists. For static allocations and
> globals, the compiler will ensure it exists. The compiler will make sure
> that all constructors locate this field and fill it in. Destructors can
> clear it. If two of these type-description-structure pointers are equal,
> then we can conclude that the types are equal. If not, then we need to
> interpret the structure. The pointer itself might be to an interval map (to
> deal with arrays, placement new, etc. - we can use the low bit of the
> pointer to differentiate between an actual type-description structure and
> an interval map), and the leaves of the interval map point to actual
> type-description structures. The type-description structure is an array of
> (offset, type) pairs, where the type field is also a
> type-description-structure pointer. The type-description structures
> themselves are comdat globals emitted in each relevant translation unit,
> where the comdat key is formed using the mangled type name (and size,
> etc.), and pointers to these symbols are then used to identify the types.
>
> Thoughts?
>
> Thanks again,
> Hal
>
> --
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170410/ebd4806f/attachment.html>