[llvm-dev] [RFC] Using segmentation to harden SafeStack

[LeMay, Michael via llvm-dev]

Hi,

SafeStack currently relies on address randomization to protect the safe stack.  If the location of a safe stack is somehow revealed and a corrupted pointer references it, then a safe stack can be corrupted.  The creators of SafeStack envisioned the possibility of using X86 segmentation to further harden SafeStack against such corruption (see the comment near the top of compiler-rt/lib/safestack/safestack.cc), and implementing that is the topic of this RFC.

If the lowest base address of any safe stack is A, then by setting the limit of DS and ES to an address B < A memory operands with an effective segment of DS or ES will be prevented from accessing any safe stack.  This is just one example of a memory layout that does not permit access to any safe stack through DS or ES; others are possible.  Instructions that require access to a safe stack can use an effective segment of SS for the relevant memory operands.  Several instructions implicitly access SS by default, such as PUSH, POP, CALL, and RET.  This is also the case for memory operands that use SP/ESP or BP/EBP as a base register.  Other instructions implicitly access DS or ES by default, which may result in crashes if they are used with pointers to a safe stack.

I developed a new MachineFunctionPass, X86FixupSeparateStack (http://reviews.llvm.org/D17095), that adds segment override prefixes or updates segment registers in X86-32 code to use the appropriate effective segment for each memory operand.  It is enabled by the separate-stack-seg feature (http://reviews.llvm.org/D17092).  The pass assumes that only ESP points to the safe stack at the start of each function.  The pass tracks the flow of addresses derived from ESP to other registers throughout the function to determine whether any given memory operand refers to the safe stack.  It assumes that only specific types of instructions (LEA32r, MOV32rr, ADD32ri8, ADD32ri) are used to compute pointers to the safe stack.  It also attempts to track the flow of addresses through register spills and fills.  The pass performs a single pass over each instruction in each basic block, recording information about the flow of safe stack addresses through registers and memory for each basic block.  At every point where one basic block invokes another basic block that has already been processed by the pass, the pass verifies that the current state of each register and frame slot is consistent with the requirements of the basic block being invoked.  The pass errors out if it detects any inconsistency, since the pass requires that each memory operand must either access a safe stack or data outside of any safe stack.  This is to support memory layouts that use a different base address for DS/ES vs. SS.  A possible alternative if the same base address is used for all of those segments is for the pass to cause any memory operand that may access both types of data to use an effective segment of SS.  However, such an approach may introduce additional risks by increasing the number of memory operands that can access safe stacks.  It may also require more than a single pass through some basic blocks.  The typical reason that a memory operand needs to support referring both to a stack address and a non-stack address at different times is to allow a single function to manipulate both stack data and non-stack data depending on what arguments it has received.  The transformation described next eliminates this complexity.

The X86FixupSeparateStack pass performs only intra-procedural analysis, so it cannot determine whether its arguments are pointers into the safe stack.  Thus, it relies on the SafeStack pass to move any allocations to the unsafe stack whose addresses are passed as arguments to functions or to intrinsics (http://reviews.llvm.org/D17094).  An exception to this is variadic arguments, which are passed on the safe stack.  I added support for address space #258 to refer to SS (http://reviews.llvm.org/D17093), and I modified Clang to use that address space for variadic argument handling when the separate-stack-seg feature is enabled (http://reviews.llvm.org/D17092).  The X86FixupSeparateStack pass can attempt to determine whether an instruction that writes a safe stack pointer to memory is for the purpose of variadic argument handling (i.e. to implement va_start or va_arg).  It tracks updates to ESP and watches for simple types of address computations based on LEA32r of the form used to implement variadic argument handling.  However, some instances of variadic argument handling use more complex types of address computations than the pass can currently detect.  Another limitation is that the pass assumes that a limited set of instruction types is used to update ESP.  The pass tracks ESP updates to help it detect stack pointer computations pointing to variadic argument locations.  If the heuristic is not able to determine that an instruction that writes a safe stack pointer to memory is for the purpose of variadic argument handling, then the pass errors out.  This is to help detect instances where the pass is unable to track safe stack pointers across stores and loads.  Two flags are available for suppressing this error.  The first suppresses it only in functions that contain va_start, and the second suppresses it unconditionally.  This more permissive option is useful for certain files that perform low-level stack pointer manipulations in the C library, segmentation-enabled SafeStack runtime library, and dynamic linker.

Runtime support is needed for the following:
 - Setting the limit of DS and ES appropriately, e.g. as described above.
 - Allocating all safe stacks above that limit.
 - Allocating unsafe stacks.
These basic requirements generate several other requirements, but that is a topic for the mailing list for the relevant runtime.  In particular, I have developed patches to musl libc that satisfy these requirements on Linux, and I plan to submit them after my LLVM patches are accepted.  I will at least point out that my patches add support for applying SafeStack to DSOs and to almost all code in the dynamic linker and C library themselves.  In fact, they essentially necessitate that SafeStack be applied so extensively, since otherwise memory operands in a library that refer to an incorrect segment may cause crashes.  I will propose storing the unsafe stack pointer in the thread control block in musl libc, so I added support for that to LLVM (http://reviews.llvm.org/D19762).  Some of the functions in these libraries may need to be invoked both before and after threading has been initialized, so I added support for compiling functions to dynamically handle both modes by dynamically checking whether a single-threaded unsafe stack pointer should be used (http://reviews.llvm.org/D19761, http://reviews.llvm.org/D19853).  The default SafeStack runtime in compiler-rt does not provide this level of runtime support, so I prevent it from being automatically linked when the separate-stack-seg feature is enabled (http://reviews.llvm.org/D19170).

I submitted patches to enable SafeStack for single-threaded Contiki OS on X86 (https://github.com/contiki-os/contiki/pull/1642).  This required adding support for storing the unsafe stack pointer in a regular global variable on Contiki OS (http://reviews.llvm.org/D19852, http://reviews.llvm.org/D19854).  This is a foundation for another patch that I have prepared (but not yet submitted) to enable segmentation-hardened SafeStack for Contiki OS.  Those patches use different bases for DS/ES vs. SS, demonstrating that these LLVM patches can support such memory models.

Comments appreciated.

Thanks,
Michael