Add the -fsanitize=shadow-call-stack flag

[vlad.tsyrklevich]

Summary

Add support for the -fsanitize=shadow-call-stack flag which causes clang
to add ShadowCallStack attribute to functions compiled with that flag
enabled.

[pcc]

LGTM

Please add a test for the driver functionality.

[vlad.tsyrklevich]

• Add Driver tests

[kcc]

[didn't look at the code yet, just at the docs]

Please add a docs section describing how to handle leaf functions.
If they are not handled yet, no need to change the implementation in these pathches -- ok to do it later.

docs/ShadowCallStack.rst

14 ↗

(On Diff #139554)

prologue/epilogue?
(it's your native tongue, not mine, though)

20 ↗

(On Diff #139554)

Provide short comparison with RFG (more instructions, less memory, same racy attack)

38 ↗

(On Diff #139554)

link to wikipedia maybe?

41 ↗

(On Diff #139554)

... due to return branch predictor (or some such)

47 ↗

(On Diff #139554)

Say something about attacks that first try to discover the secret location of the shadow call stack.
side channels, thread spaying, whatever you have.

74 ↗

(On Diff #139554)

Please add a section that shows the assembly for the following example:

int foo() {
   return bar() + 1;
}

[kcc]

please also add a short comparison with Intel CET.

[vlad.tsyrklevich]

• Address Kostya's documentation feedback

[kcc]

LGTM modulo prolog vs prlogue and epilog vs epilogue

https://en.wiktionary.org/wiki/epilog says these are alternative spellings, so up to you.

docs/ShadowCallStack.rst

14 ↗

(On Diff #139554)

PTAL

[vlad.tsyrklevich]

docs/ShadowCallStack.rst

14 ↗

(On Diff #139554)

Forgot to submit this comment: It's used both ways across LLVM but I chose to go with this one just because that's how the PrologEpilogInserter pass wrote it.

[vlad.tsyrklevich]

• Small test, doc updates

[MaskRay]

cfe/trunk/test/Driver/sanitizer-ld.c

563

sanitizer-ld.c is for linker option tests. This merely checks incompatibility of compile flags and fsanitize.c may be more suitable.

cfe/trunk/docs/ShadowCallStack.rst

+===============
+ShadowCallStack
+===============
+
+.. contents::
+   :local:
+
+Introduction
+============
+
+ShadowCallStack is an **experimental** instrumentation pass, currently only
+implemented for x86_64, that protects programs against return address
+overwrites (e.g. stack buffer overflows.) It works by saving a function's return
+address to a separately allocated 'shadow call stack' in the function prolog and
+checking the return address on the stack against the shadow call stack in the
+function epilog.
+
+Comparison
+----------
+
+To optimize for memory consumption and cache locality, the shadow call stack
+stores an index followed by an array of return addresses. This is in contrast
+to other schemes, like :doc:`SafeStack`, that mirror the entire stack and
+trade-off consuming more memory for shorter function prologs and epilogs with
+fewer memory accesses. Similarly, `Return Flow Guard`_ consumes more memory with
+shorter function prologs and epilogs than ShadowCallStack but suffers from the
+same race conditions (see `Security`_). Intel `Control-flow Enforcement Technology`_
+(CET) is a proposed hardware extension that would add native support to
+use a shadow stack to store/check return addresses at call/return time. It
+would not suffer from race conditions at calls and returns and not incur the
+overhead of function instrumentation, but it does require operating system
+support.
+
+.. _`Return Flow Guard`: https://xlab.tencent.com/en/2016/11/02/return-flow-guard/
+.. _`Control-flow Enforcement Technology`: https://software.intel.com/sites/default/files/managed/4d/2a/control-flow-enforcement-technology-preview.pdf
+
+Compatibility
+-------------
+
+ShadowCallStack currently only supports x86_64. A runtime is not currently
+provided in compiler-rt so one must be provided by the compiled application.
+
+Security
+========
+
+ShadowCallStack is intended to be a stronger alternative to
+``-fstack-protector``. It protects from non-linear overflows and arbitrary
+memory writes to the return address slot; however, similarly to
+``-fstack-protector`` this protection suffers from race conditions because of
+the call-return semantics on x86_64. There is a short race between the call
+instruction and the first instruction in the function that reads the return
+address where an attacker could overwrite the return address and bypass
+ShadowCallStack. Similarly, there is a time-of-check-to-time-of-use race in the
+function epilog where an attacker could overwrite the return address after it
+has been checked and before it has been returned to. Modifying the call-return
+semantics to fix this on x86_64 would incur an unacceptable performance overhead
+due to return branch prediction.
+
+The instrumentation makes use of the ``gs`` segment register to reference the
+shadow call stack meaning that references to the shadow call stack do not have
+to be stored in memory. This makes it possible to implement a runtime that
+avoids exposing the address of the shadow call stack to attackers that can read
+arbitrary memory. However, attackers could still try to exploit side channels
+exposed by the operating system `[1]`_ `[2]`_ or processor `[3]`_ to discover
+the address of the shadow call stack.
+
+.. _`[1]`: https://eyalitkin.wordpress.com/2017/09/01/cartography-lighting-up-the-shadows/
+.. _`[2]`: https://www.blackhat.com/docs/eu-16/materials/eu-16-Goktas-Bypassing-Clangs-SafeStack.pdf
+.. _`[3]`: https://www.vusec.net/projects/anc/
+
+Leaf functions are optimized to store the return address in a free register
+and avoid writing to the shadow call stack if a register is available. Very
+short leaf functions are uninstrumented if their execution is judged to be
+shorter than the race condition window intrinsic to the instrumentation.
+
+Usage
+=====
+
+To enable ShadowCallStack, just pass the ``-fsanitize=shadow-call-stack`` flag
+to both compile and link command lines.
+
+Low-level API
+-------------
+
+``__has_feature(shadow_call_stack)``
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+In some cases one may need to execute different code depending on whether
+ShadowCallStack is enabled. The macro ``__has_feature(shadow_call_stack)`` can
+be used for this purpose.
+
+.. code-block:: c
+
+    #if defined(__has_feature)
+    #  if __has_feature(shadow_call_stack)
+    // code that builds only under ShadowCallStack
+    #  endif
+    #endif
+
+``__attribute__((no_sanitize("shadow-call-stack")))``
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Use ``__attribute__((no_sanitize("shadow-call-stack")))`` on a function
+declaration to specify that the shadow call stack instrumentation should not be
+applied to that function, even if enabled globally.
+
+Example
+=======
+
+The following example code:
+
+.. code-block:: c++
+
+    int foo() {
+      return bar() + 1;
+    }
+
+Generates the following x86_64 assembly when compiled with ``-O2``:
+
+.. code-block:: gas
+
+    push   %rax
+    callq  foo
+    add    $0x1,%eax
+    pop    %rcx
+    retq
+
+Adding ``-fsanitize=shadow-call-stack`` would output the following:
+
+.. code-block:: gas
+
+    mov    (%rsp),%r10
+    xor    %r11,%r11
+    addq   $0x8,%gs:(%r11)
+    mov    %gs:(%r11),%r11
+    mov    %r10,%gs:(%r11)
+    push   %rax
+    callq  foo
+    add    $0x1,%eax
+    pop    %rcx
+    xor    %r11,%r11
+    mov    %gs:(%r11),%r10
+    mov    %gs:(%r10),%r10
+    subq   $0x8,%gs:(%r11)
+    cmp    %r10,(%rsp)
+    jne    trap
+    retq
+
+    trap:
+    ud2

cfe/trunk/docs/index.rst

.. toctree::
    DataFlowSanitizer
    LeakSanitizer
    SanitizerCoverage
    SanitizerStats
    SanitizerSpecialCaseList
    ControlFlowIntegrity
    LTOVisibility
    SafeStack
+   ShadowCallStack
    SourceBasedCodeCoverage
    Modules
    MSVCCompatibility
    OpenMPSupport
    ThinLTO
    CommandGuide/index
    FAQ
 

cfe/trunk/include/clang/Basic/Sanitizers.def

 SANITIZER("cfi-vcall", CFIVCall)
 SANITIZER_GROUP("cfi", CFI,
                 CFIDerivedCast | CFIICall | CFIUnrelatedCast | CFINVCall |
                 CFIVCall)
 
 // Safe Stack
 SANITIZER("safe-stack", SafeStack)
 
+// Shadow Call Stack
+SANITIZER("shadow-call-stack", ShadowCallStack)
+
 // -fsanitize=undefined includes all the sanitizers which have low overhead, no
 // ABI or address space layout implications, and only catch undefined behavior.
 SANITIZER_GROUP("undefined", Undefined,
                 Alignment | Bool | Builtin | ArrayBounds | Enum |
                     FloatCastOverflow | FloatDivideByZero |
                     IntegerDivideByZero | NonnullAttribute | Null | ObjectSize |
                     PointerOverflow | Return | ReturnsNonnullAttribute | Shift |
                     SignedIntegerOverflow | Unreachable | VLABound | Function |

cfe/trunk/lib/CodeGen/CGDeclCXX.cpp

llvm::Function *CodeGenModule::CreateGlobalInitOrDestructFunction(
   if (getLangOpts().Sanitize.has(SanitizerKind::Memory) &&
       !isInSanitizerBlacklist(SanitizerKind::Memory, Fn, Loc))
     Fn->addFnAttr(llvm::Attribute::SanitizeMemory);
 
   if (getLangOpts().Sanitize.has(SanitizerKind::SafeStack) &&
       !isInSanitizerBlacklist(SanitizerKind::SafeStack, Fn, Loc))
     Fn->addFnAttr(llvm::Attribute::SafeStack);
 
+  if (getLangOpts().Sanitize.has(SanitizerKind::ShadowCallStack) &&
+      !isInSanitizerBlacklist(SanitizerKind::ShadowCallStack, Fn, Loc))
+    Fn->addFnAttr(llvm::Attribute::ShadowCallStack);
+
   return Fn;
 }
 
 /// Create a global pointer to a function that will initialize a global
 /// variable.  The user has requested that this pointer be emitted in a specific
 /// section.
 void CodeGenModule::EmitPointerToInitFunc(const VarDecl *D,
                                           llvm::GlobalVariable *GV,

cfe/trunk/lib/CodeGen/CodeGenFunction.cpp

#undef SANITIZER
   if (SanOpts.hasOneOf(SanitizerKind::HWAddress))
     Fn->addFnAttr(llvm::Attribute::SanitizeHWAddress);
   if (SanOpts.has(SanitizerKind::Thread))
     Fn->addFnAttr(llvm::Attribute::SanitizeThread);
   if (SanOpts.has(SanitizerKind::Memory))
     Fn->addFnAttr(llvm::Attribute::SanitizeMemory);
   if (SanOpts.has(SanitizerKind::SafeStack))
     Fn->addFnAttr(llvm::Attribute::SafeStack);
+  if (SanOpts.has(SanitizerKind::ShadowCallStack))
+    Fn->addFnAttr(llvm::Attribute::ShadowCallStack);
 
   // Apply fuzzing attribute to the function.
   if (SanOpts.hasOneOf(SanitizerKind::Fuzzer | SanitizerKind::FuzzerNoLink))
     Fn->addFnAttr(llvm::Attribute::OptForFuzzing);
 
   // Ignore TSan memory acesses from within ObjC/ObjC++ dealloc, initialize,
   // .cxx_destruct, __destroy_helper_block_ and all of their calees at run time.
   if (SanOpts.has(SanitizerKind::Thread)) {

cfe/trunk/lib/Driver/SanitizerArgs.cpp

std::pair<SanitizerMask, SanitizerMask> IncompatibleGroups[] = {
       std::make_pair(Leak, Thread | Memory),
       std::make_pair(KernelAddress, Address | Leak | Thread | Memory),
       std::make_pair(HWAddress, Address | Thread | Memory | KernelAddress),
       std::make_pair(Efficiency, Address | HWAddress | Leak | Thread | Memory |
                                      KernelAddress),
       std::make_pair(Scudo, Address | HWAddress | Leak | Thread | Memory |
                                 KernelAddress | Efficiency),
       std::make_pair(SafeStack, Address | HWAddress | Leak | Thread | Memory |
-                                    KernelAddress | Efficiency)};
+                                    KernelAddress | Efficiency),
+      std::make_pair(ShadowCallStack, Address | HWAddress | Leak | Thread |
+                                          Memory | KernelAddress | Efficiency |
+                                          SafeStack)};
 
   // Enable toolchain specific default sanitizers if not explicitly disabled.
   SanitizerMask Default = TC.getDefaultSanitizers() & ~AllRemove;
 
   // Disable default sanitizers that are incompatible with explicitly requested
   // ones.
   for (auto G : IncompatibleGroups) {
     SanitizerMask Group = G.first;

cfe/trunk/lib/Driver/ToolChain.cpp

SanitizerMask Res = (Undefined & ~Vptr & ~Function) | (CFI & ~CFIICall) |
                       LocalBounds;
   if (getTriple().getArch() == llvm::Triple::x86 ||
       getTriple().getArch() == llvm::Triple::x86_64 ||
       getTriple().getArch() == llvm::Triple::arm ||
       getTriple().getArch() == llvm::Triple::aarch64 ||
       getTriple().getArch() == llvm::Triple::wasm32 ||
       getTriple().getArch() == llvm::Triple::wasm64)
     Res |= CFIICall;
+  if (getTriple().getArch() == llvm::Triple::x86_64)
+    Res |= ShadowCallStack;
   return Res;
 }
 
 void ToolChain::AddCudaIncludeArgs(const ArgList &DriverArgs,
                                    ArgStringList &CC1Args) const {}
 
 void ToolChain::AddIAMCUIncludeArgs(const ArgList &DriverArgs,
                                     ArgStringList &CC1Args) const {}

cfe/trunk/lib/Lex/PPMacroExpansion.cpp

return llvm::StringSwitch<bool>(Feature)
       .Case("is_sealed", LangOpts.CPlusPlus && LangOpts.MicrosoftExt)
       .Case("is_trivial", LangOpts.CPlusPlus)
       .Case("is_trivially_assignable", LangOpts.CPlusPlus)
       .Case("is_trivially_constructible", LangOpts.CPlusPlus)
       .Case("is_trivially_copyable", LangOpts.CPlusPlus)
       .Case("is_union", LangOpts.CPlusPlus)
       .Case("modules", LangOpts.Modules)
       .Case("safe_stack", LangOpts.Sanitize.has(SanitizerKind::SafeStack))
+      .Case("shadow_call_stack",
+            LangOpts.Sanitize.has(SanitizerKind::ShadowCallStack))
       .Case("tls", PP.getTargetInfo().isTLSSupported())
       .Case("underlying_type", LangOpts.CPlusPlus)
       .Default(false);
 }
 
 /// HasExtension - Return true if we recognize and implement the feature
 /// specified by the identifier, either as an extension or a standard language
 /// feature.

cfe/trunk/test/CodeGen/shadowcallstack-attr.c

+// RUN: %clang_cc1 -triple x86_64-linux-unknown -emit-llvm -o - %s -fsanitize=shadow-call-stack | FileCheck -check-prefix=UNBLACKLISTED %s
+
+// RUN: %clang_cc1 -D ATTR -triple x86_64-linux-unknown -emit-llvm -o - %s -fsanitize=shadow-call-stack | FileCheck -check-prefix=BLACKLISTED %s
+
+// RUN: echo -e "[shadow-call-stack]\nfun:foo" > %t
+// RUN: %clang_cc1 -fsanitize-blacklist=%t -triple x86_64-linux-unknown -emit-llvm -o - %s -fsanitize=shadow-call-stack | FileCheck -check-prefix=BLACKLISTED %s
+
+#ifdef ATTR
+__attribute__((no_sanitize("shadow-call-stack")))
+#endif
+int foo(int *a) { return *a; }
+
+// CHECK: define i32 @foo(i32* %a)
+
+// BLACKLISTED-NOT: attributes {{.*}}shadowcallstack{{.*}}
+// UNBLACKLISTED: attributes {{.*}}shadowcallstack{{.*}}

cfe/trunk/test/Driver/sanitizer-ld.c

 // CHECK-SAFESTACK-LINUX: "{{(.*[^-.0-9A-Z_a-z])?}}ld{{(.exe)?}}"
 // CHECK-SAFESTACK-LINUX-NOT: "-lc"
 // CHECK-SAFESTACK-LINUX-NOT: whole-archive
 // CHECK-SAFESTACK-LINUX: libclang_rt.safestack-x86_64.a"
 // CHECK-SAFESTACK-LINUX: "-u" "__safestack_init"
 // CHECK-SAFESTACK-LINUX: "-lpthread"
 // CHECK-SAFESTACK-LINUX: "-ldl"
 
+// RUN: %clang -fsanitize=shadow-call-stack %s -### -o %t.o 2>&1 \
+// RUN:     -target x86_64-unknown-linux -fuse-ld=ld \
+// RUN:   | FileCheck --check-prefix=CHECK-SHADOWCALLSTACK-LINUX-X86-64 %s
+// CHECK-SHADOWCALLSTACK-LINUX-X86-64-NOT: error:
+
+// RUN: %clang -fsanitize=shadow-call-stack %s -### -o %t.o 2>&1 \
+// RUN:     -target x86-unknown-linux -fuse-ld=ld \
+// RUN:   | FileCheck --check-prefix=CHECK-SHADOWCALLSTACK-LINUX-X86 %s
+// CHECK-SHADOWCALLSTACK-LINUX-X86: error: unsupported option '-fsanitize=shadow-call-stack' for target 'x86-unknown-linux'
+
+// RUN: %clang -fsanitize=shadow-call-stack %s -### -o %t.o 2>&1 \
+// RUN:     -fsanitize=safe-stack -target x86_64-unknown-linux -fuse-ld=ld \
+// RUN:   | FileCheck --check-prefix=CHECK-SHADOWCALLSTACK-SAFESTACK %s
+// CHECK-SHADOWCALLSTACK-SAFESTACK: error: invalid argument '-fsanitize=shadow-call-stack' not allowed with '-fsanitize=safe-stack'
+
 // RUN: %clang -fsanitize=cfi -fsanitize-stats %s -### -o %t.o 2>&1 \
 // RUN:     -target x86_64-unknown-linux -fuse-ld=ld \
 // RUN:     --sysroot=%S/Inputs/basic_linux_tree \
 // RUN:   | FileCheck --check-prefix=CHECK-CFI-STATS-LINUX %s
 // CHECK-CFI-STATS-LINUX: "{{.*}}ld{{(.exe)?}}"
 // CHECK-CFI-STATS-LINUX: "--whole-archive" "{{[^"]*}}libclang_rt.stats_client-x86_64.a" "--no-whole-archive"
 // CHECK-CFI-STATS-LINUX-NOT: "--whole-archive"
 // CHECK-CFI-STATS-LINUX: "{{[^"]*}}libclang_rt.stats-x86_64.a"