From eda8bd0fc07df35c9ad7de5b698bb717b063e7af Mon Sep 17 00:00:00 2001 From: Richard Smith Date: Thu, 25 Oct 2012 02:07:02 +0000 Subject: -fcatch-undefined-behavior checking for appropriate vptr value: library side. git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@166660 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/ubsan/CMakeLists.txt | 2 + lib/ubsan/lit_tests/TypeCheck/vptr.cpp | 74 ++++++++++++ lib/ubsan/ubsan_handlers.cc | 11 +- lib/ubsan/ubsan_handlers_cxx.cc | 49 ++++++++ lib/ubsan/ubsan_handlers_cxx.h | 36 ++++++ lib/ubsan/ubsan_type_hash.cc | 200 +++++++++++++++++++++++++++++++++ lib/ubsan/ubsan_type_hash.h | 29 +++++ 7 files changed, 397 insertions(+), 4 deletions(-) create mode 100644 lib/ubsan/lit_tests/TypeCheck/vptr.cpp create mode 100644 lib/ubsan/ubsan_handlers_cxx.cc create mode 100644 lib/ubsan/ubsan_handlers_cxx.h create mode 100644 lib/ubsan/ubsan_type_hash.cc create mode 100644 lib/ubsan/ubsan_type_hash.h diff --git a/lib/ubsan/CMakeLists.txt b/lib/ubsan/CMakeLists.txt index fa6393f84..616e0650c 100644 --- a/lib/ubsan/CMakeLists.txt +++ b/lib/ubsan/CMakeLists.txt @@ -3,6 +3,8 @@ set(UBSAN_SOURCES ubsan_diag.cc ubsan_handlers.cc + ubsan_handlers_cxx.cc + ubsan_type_hash.cc ubsan_value.cc ) diff --git a/lib/ubsan/lit_tests/TypeCheck/vptr.cpp b/lib/ubsan/lit_tests/TypeCheck/vptr.cpp new file mode 100644 index 000000000..c8e2820f1 --- /dev/null +++ b/lib/ubsan/lit_tests/TypeCheck/vptr.cpp @@ -0,0 +1,74 @@ +// RUN: %clang -ccc-cxx -fcatch-undefined-behavior %s -O3 -o %t +// RUN: %t rT && %t mT && %t fT +// RUN: %t rU && %t mU && %t fU +// RUN: %t rS 2>&1 | FileCheck %s --check-prefix=CHECK-REFERENCE +// RUN: %t mS 2>&1 | FileCheck %s --check-prefix=CHECK-MEMBER +// RUN: %t fS 2>&1 | FileCheck %s --check-prefix=CHECK-MEMFUN +// RUN: %t rV 2>&1 | FileCheck %s --check-prefix=CHECK-REFERENCE +// RUN: %t mV 2>&1 | FileCheck %s --check-prefix=CHECK-MEMBER +// RUN: %t fV 2>&1 | FileCheck %s --check-prefix=CHECK-MEMFUN + +struct S { + S() : a(0) {} + ~S() {} + int a; + int f() { return 0; } + virtual int v() { return 0; } +}; + +struct T : S { + T() : b(0) {} + int b; + int g() { return 0; } + virtual int v() { return 1; } +}; + +struct U : S, T { virtual int v() { return 2; } }; + +int main(int, char **argv) { + T t; + (void)t.a; + (void)t.b; + (void)t.f(); + (void)t.g(); + (void)t.v(); + (void)t.S::v(); + + U u; + (void)u.T::a; + (void)u.b; + (void)u.T::f(); + (void)u.g(); + (void)u.v(); + (void)u.T::v(); + (void)((T&)u).S::v(); + + T *p = 0; + switch (argv[1][1]) { + case 'S': + p = reinterpret_cast(new S); + break; + case 'T': + p = new T; + break; + case 'U': + p = new U; + break; + case 'V': + p = reinterpret_cast(new U); + break; + } + + switch (argv[1][0]) { + case 'r': + // CHECK-REFERENCE: vptr.cpp:65:13: fatal error: reference binding to address 0x{{[0-9a-f]*}} which does not point to an object of type 'T' + {T &r = *p;} + break; + case 'm': + // CHECK-MEMBER: vptr.cpp:69:15: fatal error: member access within address 0x{{[0-9a-f]*}} which does not point to an object of type 'T' + return p->b; + case 'f': + // CHECK-MEMFUN: vptr.cpp:72:12: fatal error: member call on address 0x{{[0-9a-f]*}} which does not point to an object of type 'T' + return p->g(); + } +} diff --git a/lib/ubsan/ubsan_handlers.cc b/lib/ubsan/ubsan_handlers.cc index 2cb12c459..ae0f1f6c3 100644 --- a/lib/ubsan/ubsan_handlers.cc +++ b/lib/ubsan/ubsan_handlers.cc @@ -1,4 +1,4 @@ -//===-- ubsan_report.cc ---------------------------------------------------===// +//===-- ubsan_handlers.cc -------------------------------------------------===// // // The LLVM Compiler Infrastructure // @@ -31,12 +31,15 @@ NORETURN void __sanitizer::CheckFailed(const char *File, int Line, Die(); } -void __ubsan::__ubsan_handle_type_mismatch(TypeMismatchData *Data, - ValueHandle Pointer) { +namespace __ubsan { const char *TypeCheckKinds[] = { "load of", "store to", "reference binding to", "member access within", - "member call on" + "member call on", "constructor call on" }; +} + +void __ubsan::__ubsan_handle_type_mismatch(TypeMismatchData *Data, + ValueHandle Pointer) { if (!Pointer) Diag(Data->Loc, "%0 null pointer of type %1") << TypeCheckKinds[Data->TypeCheckKind] << Data->Type; diff --git a/lib/ubsan/ubsan_handlers_cxx.cc b/lib/ubsan/ubsan_handlers_cxx.cc new file mode 100644 index 000000000..e0d3442e8 --- /dev/null +++ b/lib/ubsan/ubsan_handlers_cxx.cc @@ -0,0 +1,49 @@ +//===-- ubsan_handlers_cxx.cc ---------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Error logging entry points for the UBSan runtime, which are only used for C++ +// compilations. This file is permitted to use language features which require +// linking against a C++ ABI library. +// +//===----------------------------------------------------------------------===// + +#include "ubsan_handlers_cxx.h" +#include "ubsan_diag.h" +#include "ubsan_type_hash.h" + +#include "sanitizer_common/sanitizer_common.h" + +using namespace __sanitizer; +using namespace __ubsan; + +namespace __ubsan { + extern const char *TypeCheckKinds[]; +} + +void __ubsan::__ubsan_handle_dynamic_type_cache_miss( + DynamicTypeCacheMissData *Data, ValueHandle Pointer, ValueHandle Hash) { + if (checkDynamicType((void*)Pointer, Data->TypeInfo, Hash)) + // Just a cache miss. The type matches after all. + return; + + Diag(Data->Loc, "%0 address %1 which does not point to an object of type %2") + << TypeCheckKinds[Data->TypeCheckKind] << (void*)Pointer << Data->Type; + // FIXME: If possible, say what type it actually points to. Produce a note + // pointing out the vptr: + // lib/VMCore/Instructions.cpp:2020:10: fatal error: member call on address + // 0xb7a4440 which does not point to an object of type + // 'llvm::OverflowingBinaryOperator' + // return cast(this)->hasNoSignedWrap(); + // ^ + // 0xb7a4440: note: object is of type 'llvm::BinaryOperator' + // 00 00 00 00 e0 f7 c5 09 00 00 00 00 20 00 00 00 + // ^~~~~~~~~~~ + // vptr for 'llvm::BinaryOperator' + Die(); +} diff --git a/lib/ubsan/ubsan_handlers_cxx.h b/lib/ubsan/ubsan_handlers_cxx.h new file mode 100644 index 000000000..8192e6527 --- /dev/null +++ b/lib/ubsan/ubsan_handlers_cxx.h @@ -0,0 +1,36 @@ +//===-- ubsan_handlers_cxx.h ------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Entry points to the runtime library for Clang's undefined behavior sanitizer, +// for C++-specific checks. This code is not linked into C binaries. +// +//===----------------------------------------------------------------------===// +#ifndef UBSAN_HANDLERS_CXX_H +#define UBSAN_HANDLERS_CXX_H + +#include "ubsan_value.h" + +namespace __ubsan { + +struct DynamicTypeCacheMissData { + SourceLocation Loc; + const TypeDescriptor &Type; + void *TypeInfo; + unsigned char TypeCheckKind; +}; + +/// \brief Handle a runtime type check failure, caused by an incorrect vptr. +/// When this handler is called, all we know is that the type was not in the +/// cache; this does not necessarily imply the existence of a bug. +extern "C" void __ubsan_handle_dynamic_type_cache_miss( + DynamicTypeCacheMissData *Data, ValueHandle Pointer, ValueHandle Hash); + +} + +#endif // UBSAN_HANDLERS_H diff --git a/lib/ubsan/ubsan_type_hash.cc b/lib/ubsan/ubsan_type_hash.cc new file mode 100644 index 000000000..6d0443692 --- /dev/null +++ b/lib/ubsan/ubsan_type_hash.cc @@ -0,0 +1,200 @@ +//===-- ubsan_type_hash.cc ------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Implementation of a hash table for fast checking of inheritance +// relationships. This file is only linked into C++ compilations, and is +// permitted to use language features which require a C++ ABI library. +// +//===----------------------------------------------------------------------===// + +#include "ubsan_type_hash.h" + +#include "sanitizer_common/sanitizer_common.h" + +// The following are intended to be binary compatible with the definitions +// given in the Itanium ABI. We make no attempt to be ODR-compatible with +// those definitions, since existing ABI implementations aren't. + +namespace std { + class type_info { + public: + virtual ~type_info(); + private: + const char *__type_name; + }; +} + +namespace __cxxabiv1 { + +/// Type info for classes with no bases, and base class for type info for +/// classes with bases. +class __class_type_info : public std::type_info { + virtual ~__class_type_info(); +}; + +/// Type info for classes with simple single public inheritance. +class __si_class_type_info : public __class_type_info { +public: + virtual ~__si_class_type_info(); + + const __class_type_info *__base_type; +}; + +class __base_class_type_info { +public: + const __class_type_info *__base_type; + long __offset_flags; + + enum __offset_flags_masks { + __virtual_mask = 0x1, + __public_mask = 0x2, + __offset_shift = 8 + }; +}; + +/// Type info for classes with multiple, virtual, or non-public inheritance. +class __vmi_class_type_info : public __class_type_info { +public: + virtual ~__vmi_class_type_info(); + + unsigned int flags; + unsigned int base_count; + __base_class_type_info base_info[1]; +}; + +} + +namespace abi = __cxxabiv1; + +// We implement a simple two-level cache for type-checking results. For each +// (vptr,type) pair, a hash is computed. This hash is assumed to be globally +// unique; if it collides, we will get false negatives, but: +// * such a collision would have to occur on the *first* bad access, +// * the probability of such a collision is low (and for a 64-bit target, is +// negligible), and +// * the vptr, and thus the hash, can be affected by ASLR, so multiple runs +// give better coverage. +// +// The first caching layer is a small hash table with no chaining; buckets are +// reused as needed. The second caching layer is a large hash table with open +// chaining. We can freely evict from either layer since this is just a cache. +// +// FIXME: Make these hash table accesses thread-safe. The races here are benign +// (worst-case, we could miss a bug or see a slowdown) but we should +// avoid upsetting race detectors. + +// Find a bucket to store the given value in. +static __ubsan::HashValue *getTypeCacheHashTableBucket(__ubsan::HashValue V) { + static const unsigned HashTableSize = 65537; + static __ubsan::HashValue __ubsan_vptr_hash_set[HashTableSize] = { 1 }; + + unsigned Probe = V & 65535; + for (int Tries = 5; Tries; --Tries) { + if (!__ubsan_vptr_hash_set[Probe] || __ubsan_vptr_hash_set[Probe] == V) + return &__ubsan_vptr_hash_set[Probe]; + Probe += ((V >> 16) & 65535) + 1; + if (Probe >= HashTableSize) + Probe -= HashTableSize; + } + // FIXME: Pick a random entry from the probe sequence to evict rather than + // just taking the first. + return &__ubsan_vptr_hash_set[V]; +} + +// A cache of recently-checked hashes. Mini hash table with "random" evictions. +// The bottom 7 bits of the hash are used as the key. +static const unsigned CacheSize = 128; +extern "C" __ubsan::HashValue __ubsan_vptr_type_cache[CacheSize] = { 1 }; + +/// \brief Determine whether \p Derived has a \p Base base class subobject at +/// offset \p Offset. +static bool isDerivedFromAtOffset(const abi::__class_type_info *Derived, + const abi::__class_type_info *Base, + sptr Offset) { + if (Derived == Base) + return Offset == 0; + + if (const abi::__si_class_type_info *SI = + dynamic_cast(Derived)) + return isDerivedFromAtOffset(SI->__base_type, Base, Offset); + + const abi::__vmi_class_type_info *VTI = + dynamic_cast(Derived); + if (!VTI) + // No base class subobjects. + return false; + + // Look for a zero-offset base class which is derived from \p Base. + for (unsigned int base = 0; base != VTI->base_count; ++base) { + // FIXME: Curtail the recursion if this base can't possibly contain the + // given offset. + sptr OffsetHere = VTI->base_info[base].__offset_flags >> + abi::__base_class_type_info::__offset_shift; + if (VTI->base_info[base].__offset_flags & + abi::__base_class_type_info::__virtual_mask) + // For now, just punt on virtual bases and say 'yes'. + // FIXME: OffsetHere is the offset in the vtable of the virtual base + // offset. Read the vbase offset out of the vtable and use it. + return true; + if (isDerivedFromAtOffset(VTI->base_info[base].__base_type, + Base, Offset - OffsetHere)) + return true; + } + + return false; +} + +namespace { + +struct VtablePrefix { + /// The offset from the vptr to the start of the most-derived object. + /// This should never be greater than zero, and will usually be exactly + /// zero. + sptr Offset; + /// The type_info object describing the most-derived class type. + std::type_info *TypeInfo; +}; +VtablePrefix *getVtablePrefix(void *Object) { + VtablePrefix **Ptr = reinterpret_cast(Object); + return *Ptr - 1; +} + +} + +bool __ubsan::checkDynamicType(void *Object, void *Type, HashValue Hash) { + // A crash anywhere within this function probably means the vptr is corrupted. + // FIXME: Perform these checks more cautiously. + + // Check whether this is something we've evicted from the cache. + HashValue *Bucket = getTypeCacheHashTableBucket(Hash); + if (*Bucket == Hash) { + __ubsan_vptr_type_cache[Hash % CacheSize] = Hash; + return true; + } + + VtablePrefix *Vtable = getVtablePrefix(Object); + if (Vtable + 1 == 0 || Vtable->Offset > 0) + // This can't possibly be a valid vtable. + return false; + + // Check that this is actually a type_info object for a class type. + abi::__class_type_info *Derived = + dynamic_cast(Vtable->TypeInfo); + if (!Derived) + return false; + + abi::__class_type_info *Base = (abi::__class_type_info*)Type; + if (!isDerivedFromAtOffset(Derived, Base, -Vtable->Offset)) + return false; + + // Success. Cache this result. + __ubsan_vptr_type_cache[Hash % CacheSize] = Hash; + *Bucket = Hash; + return true; +} diff --git a/lib/ubsan/ubsan_type_hash.h b/lib/ubsan/ubsan_type_hash.h new file mode 100644 index 000000000..982ebdfbc --- /dev/null +++ b/lib/ubsan/ubsan_type_hash.h @@ -0,0 +1,29 @@ +//===-- ubsan_type_hash.h ---------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Hashing of types for Clang's undefined behavior checker. +// +//===----------------------------------------------------------------------===// +#ifndef UBSAN_TYPE_HASH_H +#define UBSAN_TYPE_HASH_H + +#include "sanitizer_common/sanitizer_common.h" + +namespace __ubsan { + +typedef uptr HashValue; + +/// \brief Check whether the dynamic type of \p Object has a \p Type subobject +/// at offset 0. +/// \return \c true if the type matches, \c false if not. +bool checkDynamicType(void *Object, void *Type, HashValue CacheSlot); + +} // namespace __ubsan + +#endif // UBSAN_TYPE_HASH_H -- cgit v1.2.1