PaperlayerView exact revision on arXiv

Source-linked AI summary

Shining Light On Shadow Stacks

Nathan Burow, Xinping Zhang, Mathias Payer

arXiv:1811.03165v2cs.CR

TL;DR

Backward-edge control-flow attacks remain insufficiently addressed by existing protections, motivating a systematic study of shadow-stack designs. The paper evaluates mechanisms across performance, compatibility, and security, then proposes and deploys the register-based Shadesmar design in real applications.

  • Problem

    CFI protects forward edges, but backward-edge protections such as stack canaries and safe stacks are easily bypassed by information leaks.

  • Method

    The paper evaluates five shadow-stack mechanisms across performance, compatibility, and security, using SPEC CPU2006 and Phoronix and Apache case studies.

  • Results

    The register-based compact design achieved 5.33% SPEC CPU2006 overhead with the traditional epilogue, reduced to 4.31% with the fault epilogue.

  • Takeaways & Limitations

    The study supports deploying Shadesmar and provides LLVM-7.0.0 implementations of known shadow-stack schemes to aid deployment.

  • Takeaways & Limitations

    Register-based compact shadow stacks can fail when callbacks from unprotected code enter protected code after the shadow-stack pointer has been clobbered.

Abstract

from arXiv · show

Control-Flow Hijacking attacks are the dominant attack vector against C/C++ programs. Control-Flow Integrity (CFI) solutions mitigate these attacks on the forward edge,i.e., indirect calls through function pointers and virtual calls. Protecting the backward edge is left to stack canaries, which are easily bypassed through information leaks. Shadow Stacks are a fully precise mechanism for protecting backwards edges, and should be deployed with CFI mitigations. We present a comprehensive analysis of all possible shadow stack mechanisms along three axes: performance, compatibility, and security. For performance comparisons we use SPEC CPU2006, while security and compatibility are qualitatively analyzed. Based on our study, we renew calls for a shadow stack design that leverages a dedicated register, resulting in low performance overhead, and minimal memory overhead, but sacrifices compatibility. We present case studies of our implementation of such a design, Shadesmar, on Phoronix and Apache to demonstrate the feasibility of dedicating a general purpose register to a security monitor on modern architectures, and the deployability of Shadesmar. Our comprehensive analysis, including detailed case studies for our novel design, allows compiler designers and practitioners to select the correct shadow stack design for different usage scenarios.

I. INTRODUCTION

The paper argues that backward-edge attacks remain insufficiently protected despite CFI deployment, and surveys shadow-stack designs to identify practical protections across performance, compatibility, and security.

  • Stack canaries and safe stacks, the strongest backward-edge protections in mainline compilers, are easily bypassed by information leaks.
  • Return-oriented attacks overwrite return addresses, while increasing CFI adoption makes backward edges an increasingly attractive target.
  • Shadow stacks store return addresses in isolated memory and compare them on return, enforcing a one-to-one mapping between calls and returns.
  • Existing compact and parallel shadow stacks exceed the suggested 5% performance threshold, increase memory use, and complicate threading and exception handling.
  • The study evaluates five mechanisms across performance, compatibility, and security, using SPEC CPU2006 quantitatively and qualitative analysis for features such as threading.
  • The paper proposes Shadesmar, a compact shadow stack using a dedicated register, and evaluates it through Phoronix and Apache case studies.

II. BACKGROUND

The paper frames ROP and stack pivots as attacks that corrupt backward-edge control flow by manipulating return addresses or the stack pointer.

  • The attacker model grants arbitrary memory reads and writes, while assuming DEP and ASLR remain active defenses.
  • The paper targets backward-edge attacks on return addresses; forward-edge attacks and data-only attacks are out of scope.
  • ROP overwrites return addresses so returns redirect execution through attacker-selected executable gadgets.
  • The illustrated ROP payload chains gadgets to move arguments into registers and invoke system("/bin/sh").
  • Stack pivots move the stack pointer to attacker-controlled memory, simplifying ROP payload delivery and potentially bypassing ASLR.

III. SHADOW STACK DESIGN SPACE

Shadow-stack mechanisms differ in how they map program-stack returns to protected copies, producing distinct performance, memory, compatibility, and security trade-offs.

  • The design space contains five mechanisms built from compact and parallel shadow stacks, with three compact mapping encodings and two parallel encodings.
  • Parallel direct mapping doubles stack memory usage but provides a simple lookup using a constant offset.
  • Compact indirect mapping uses a separate shadow-stack pointer and allocates space only for return addresses rather than duplicating the program stack.
  • setjmp/longjmp and C++ exception unwinding break perfectly matched calls and returns, creating compatibility differences between mapping approaches.
  • Dedicated registers can make compact mappings as performant as parallel mappings while improving parallel-stack threading compatibility and security.
  • The paper summarizes each mechanism’s qualitative performance, memory, and compatibility trade-offs in Table I.

1) Parallel Shadow Stack Mechanisms:

Parallel shadow stacks trade memory and address-space constraints against efficient access; a dedicated register removes hard-coded offsets and supports thread-local mappings.

  • 1) Parallel Shadow Stack Mechanisms:: Constant-offset parallel shadow stacks require no extra registers or memory accesses but constrain address-space layout for programs with many threads.
  • 1) Parallel Shadow Stack Mechanisms:: Hard-coding the shadow-stack offset in the binary can leak the shadow-stack address to attackers.
  • 1) Parallel Shadow Stack Mechanisms:: A dedicated register stores the parallel-stack offset at runtime, allowing thread-specific offsets and requiring only one update when a thread is created.
  • 2) Compact Shadow Stack Mechanisms:: Compact shadow stacks dereference their shadow-stack pointer in every function prologue and epilogue, making access speed central to performance.
  • 2) Compact Shadow Stack Mechanisms:: Global-memory storage is slow, requires an extra move on x86, and must be thread-local for multithreaded programs.
  • 2) Compact Shadow Stack Mechanisms:: Segment registers improve access speed and support multithreading, while general-purpose registers provide the fastest shadow-pointer storage but reserve one register.

B. Return Address Validation

Shadow stacks validate the program return address against a protected shadow copy, while deployment can instead use the shadow address after validation to prevent control-flow hijacking.

  • Shadow stacks can compare program and shadow return addresses or use the shadow return address after validation.Comparison detects corruption immediately, whereas deployment only requires preventing a corrupted program return address from controlling execution.
  • Each shadow stack mechanism instruments calls and returns to maintain shadow state and validate the return address before control transfer.The implementations place this instrumentation in function prologues and epilogues and include runtime support for setup and unwinding.
  • Figure 5 presents optimizations for shadow stack epilogues.

A. Instrumented Locations

Shadow stack instrumentation is placed primarily in function prologues and epilogues, with additional handling for timing windows, unwinding, threading, and compatibility with unprotected code.

  • Instrumented locations: Function prologues push return addresses, while epilogues pop and validate them before control transfer.Prologue instrumentation protects functions rather than individual call sites and avoids distinguishing protected from unprotected callees.
  • Instrumented locations: The proposed mechanism leaves a small TOCTTOU window between storing and using the return address, but the authors consider exploitation unlikely.The window is only a few cycles because the return address remains cached, although prior work demonstrated viable epilogue attacks against another design.
  • Instrumented locations: Mitigating the TOCTTOU window with a register-passed return address changes the ABI and reduces compatibility with unprotected code.Protected functions called from unprotected code would need special handling, requiring whole-program analysis.
  • Instrumented locations: The epilogue avoids rereading the return address after validation, replacing ret with a pop-and-jump sequence to prevent memory modification between checking and use.
  • Unwinding: Compact shadow stacks instrument longjmp, exceptions, and unwinding by tracking both the return address and stack pointer.The pair uniquely identifies the stack frame, including recursive calls with repeated return addresses.
  • Compatibility: Register-based shadow stacks use a callee-saved register such as r15 to preserve compatibility with unprotected code.Runtime support initializes shadow stacks, hooks setjmp and longjmp, and supports additional threads and libunwind.

C. Shadow Stack Epilogue Optimizations

The paper replaces expensive shadow-stack return-address comparisons with equality-focused epilogue optimizations and evaluates hardware mechanisms for protecting runtime metadata.

  • Epilogue optimizations: Full comparison is unnecessary because shadow-stack validation only requires testing whether the two return addresses are equal.The authors target the compare-and-branch cost that can cause pipeline stalls.
  • Epilogue optimizations: XORing the program and shadow return addresses produces zero bits for matching positions, and popcnt equals zero only when the addresses match.
  • Epilogue optimizations: The fault and last-byte-in-page methods use the MMU to turn a nonzero popcnt into a protection fault.The fault method shifts the six-bit popcnt into high address bits, creating a non-canonical address when the count is nonzero.
  • Hardware integrity: Hardware integrity mechanisms should be assessed by performance and by the number of concurrent protected code regions they support.
  • Hardware integrity: MPK encodes access privileges per thread, whereas MPX encodes them in instructions and therefore applies permissions per executed code.
  • Hardware integrity: Figure 6 presents MPK page-permission toggling.
  • Hardware integrity: The paper calls for a hardware, code-centric ISA extension supporting multiple secure regions with minimal code changes.The proposed direction adapts the thread-centric state-of-the-art mechanism while targeting greater flexibility.

A. Thread Centric Solutions

Thread-centric mechanisms protect shadow-stack memory by changing page permissions, with MPK providing efficient per-thread toggling while information hiding and SFI impose weaker security or higher overhead.

  • Thread-centric solutions: Thread-centric solutions change permissions on protected pages to create and end a privileged region for shadow-stack writes.The traditional mprotect mechanism is expensive because it enters the kernel, walks page tables, and enables writes for all threads.
  • Thread-centric solutions: MPK assigns one of sixteen keys to each page and uses a per-thread register plus wrpkru to disable reads or writes for selected keys.This provides per-thread protected regions and avoids mprotect’s TOCTTOU problem.
  • Thread-centric solutions: MPK’s wrpkru instruction requires edx and ecx to be zero, so functions with more than two arguments must preserve those registers.
  • Code-centric solutions: Information hiding adds no overhead but offers minimal security because attacks against ASLR and related randomization defenses can expose protected pointers.The paper recommends against information hiding for shadow-stack protection.
  • Code-centric solutions: SFI provides secure intra-process isolation but incurs 7% isolation overhead and can limit addressable memory to 4GB on x86.The paper therefore argues for a more flexible hardware mechanism.
  • Code-centric solutions: MPX uses bounds registers and checks to restrict unprivileged writes to unprotected memory regions.The paper reports this segmentation approach as surprisingly performant.

C. Privileged Move

The paper proposes hardware-enforced, code-centric privileged memory moves to protect runtime metadata with less overhead than repeatedly changing thread permissions. It also examines deployment boundaries, compiler interactions, architecture differences, and compatibility costs of shadow-stack designs.

  • C. Privileged Move: Privileged moves encode permitted memory regions in the instruction, avoiding MPK’s thread-centric permission toggling for security-monitor writes.The proposed mechanism reuses page-table checks but derives permissions from the instruction rather than thread-local state.
  • C. Privileged Move: A single privileged move instruction could make runtime-metadata policies practical for shadow stacks, type safety, use-after-free protection, and partial function-pointer memory safety.The paper identifies runtime metadata protection as a bottleneck for these policies.
  • Tail Call Optimizations: Tail-call optimization keeps shadow stacks synchronized by executing the normal shadow-stack epilogue before jumping directly to the callee.Fault epilogues use LBP for tail calls because these transfers lack a jump through the return address.
  • Mobile Architectures: ARM’s link register permits prologue instrumentation without a potential TOCTTOU window, although the paper’s epilogue optimizations remain x86-specific.The x86 specificity comes from reliance on the popcnt instruction.
  • RSP as Shadow Stack Pointer: Using RSP as the shadow-stack pointer could halve the overhead attributed to replacing return with pop; jmp, but would require extensive compatibility changes.The design would remove push and pop, require linker wrappers, and affect assembly, libraries, threading, kernel support, and stack initialization.
  • Assembly Files: Register-based shadow stacks leave assembly files uninstrumented, allowing r15 use and requiring future engineering work for broader assembly support.The current treatment makes assembly code an unprotected region.

VII. EVALUATION

The evaluation compares five shadow stack implementations and tests epilogue optimizations and shadow stack integrity mechanisms. It finds that compact register-based designs offer the strongest performance results, while MPX- and MPK-based isolation impose substantial overhead.

  • Evaluation scope: The evaluation covers five shadow stack implementations, epilogue optimizations, and three mechanisms for protecting shadow stack integrity.The experiments use SPEC CPU2006 and separately evaluate performance, optimization effects, and integrity-protection costs.
  • Design comparison: 5.78% overhead for parallel constant-offset and 5.33% for compact register shadow stacks are within measurement noise, weakening the performance case for parallel designs’ greater memory use.The register-based parallel design reaches 7.10% overhead, while compact and parallel designs have similar code-size impacts of 15.57% and 14.88%.
  • Epilogue optimizations: 4.31% overhead for the fault epilogue and 4.44% for the LBP epilogue improve on the traditional cmp-based epilogue’s 5.33%.The fault epilogue is marginally faster and avoids the additional guard pages required by LBP.
  • Epilogue optimizations: 3.65% overhead using the shadow return address without comparison is the paper’s recommended deployment configuration.The authors recommend the fault-based epilogue for vulnerability discovery settings such as testing and fuzzing.
  • Integrity protection: 4.31% overhead for information hiding compares with 12.12% for MPX-based isolation and 61.18% for MPK-based isolation.The MPX and MPK overheads are judged unacceptable for deployment; MPX also increases code size by 41.67%, versus 21.24% for MPK.

B. Shadesmar Case Studies

The Shadesmar case studies assess desktop and server workloads using Phoronix and Apache. They report low overhead across most Phoronix benchmarks and no performance impact for the evaluated I/O-bound Apache workloads.

  • Case-study design: Shadesmar is evaluated on ten Phoronix workloads and Apache throughput using representative desktop and server scenarios.The Apache experiments use 70KB HTML and 1.4MB image files, with throughput measured using the standard ab tool.
  • Deployment feasibility: The case studies show that dedicating one general-purpose register for shadow stacks is feasible on modern 64-bit architectures.The paper connects this feasibility claim to low observed performance impact in desktop and server workloads.
  • Phoronix: Less than 2% overhead occurs for eight of ten Phoronix benchmarks, with five within 1% and two within measurement noise of zero.SQLite is the only benchmark reported as having high overhead.
  • Apache: Shadesmar has no impact on Apache performance for the evaluated I/O-bound workloads, with overhead nonexistent at eight concurrent connections.The reported overhead decreases as connection count and file size increase.

VIII. RELATED WORK

Related work on code-reuse defenses spans offensive attack studies, forward-edge CFI, and backward-edge shadow stacks. Shadow stack implementations divide primarily into binary-translation and compiler-based approaches.

  • Research areas: Prior code-reuse research covers attack evaluation, forward-edge CFI defenses, and backward-edge shadow stack defenses.The paper positions shadow stacks as the backward-edge counterpart to CFI’s forward-edge protection.
  • Code-reuse attacks: Code-reuse attacks expanded from return-oriented programming to indirect control-flow transfers, JIT-compiled code, and counterfeit object-oriented programming.The related work describes the attack surface as broader than returns alone.
  • Control-Flow Integrity: CFI uses static analysis to approximate a control-flow graph and enforces at runtime that transitions remain within that graph.Subsequent work removed whole-program-analysis requirements and specialized CFI for C++ virtual calls.
  • Alternative defenses: Forward-edge alternatives include Code Pointer Integrity, Safe Stacks, and CFIXX, which protect code pointers, selected stack contents, or virtual-table pointers.These approaches differ in the objects or stack regions they isolate and protect.
  • Shadow stacks: Shadow stack research includes binary-translation solutions and compiler-based solutions with differing instrumentation and policy goals.Binary approaches may add trampolines or combine shadow stacks with CFI or Intel Process Trace.

IX. CONCLUSION

The paper studies shadow stacks across performance, compatibility, and security, then recommends Shadesmar as a deployable register-based design. Its case studies report low overhead for most Phoronix benchmarks and no Apache performance impact, while its isolation analysis finds current hardware mechanisms impractical for intra-process protection.

  • Conclusions: The study evaluates shadow stack designs across performance, compatibility, and security, and recommends Shadesmar for deployment.Shadesmar is a register-based compact shadow stack compatible with required C/C++ paradigms.
  • Case studies: Apache shows no performance impact for real workloads, while Phoronix shows less than 2% overhead for eight of ten benchmarks.These results support the feasibility of dedicating a general-purpose register to shadow stacks.
  • Isolation: The study finds that no existing hardware mechanism is usable in practice for intra-process address-space isolation and proposes a code-centric mechanism.The proposed mechanism targets security monitors that require mutable metadata.
  • Deployment trade-offs: The design study reports low performance and memory overhead for shadow stacks while examining their broader deployment trade-offs.The conclusion frames these findings as support for selecting shadow stack designs according to usage scenarios.
Loading 1811.03165v2…