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

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