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

[Hal Finkel via llvm-dev]

Hi again,

While not using the compressed shadow representation discussed here, 
mostly because it can't handle the struct-path (offset) information in 
our TBAA, I've posted patches for an initial TBAA sanitizer implementation:

https://reviews.llvm.org/D32197 (Runtime)
https://reviews.llvm.org/D32198 (LLVM)
https://reviews.llvm.org/D32199 (Clang)

Please try it out / review / etc.

  -Hal

On 04/04/2017 03:13 PM, Hal Finkel 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