This is an archive of the discontinued LLVM Phabricator instance.

Protection against stack-based memory corruption errors using SafeStack
ClosedPublic

Authored by pcc on Nov 3 2014, 9:35 AM.

Details

Summary

This patch adds the safe stack instrumentation pass to LLVM, which separates the program stack into a safe stack, which stores return addresses, register spills, and local variables that are statically verified to be accessed in a safe way, and the unsafe stack, which stores everything else. Such separation makes it much harder for an attacker to corrupt objects on the safe stack, including function pointers stored in spilled registers and return addresses. You can find more information about the safe stack, as well as other parts of or control-flow hijack protection technique in our OSDI paper on code-pointer integrity (http://dslab.epfl.ch/pubs/cpi.pdf) and our project website (http://levee.epfl.ch).

The overhead of our implementation of the safe stack is very close to zero (0.01% on the Phoronix benchmarks and 0.03% on SPEC2006 CPU on average). This is lower than the overhead of stack cookies, which are supported by LLVM and are commonly used today, yet the security guarantees of the safe stack are strictly stronger than stack cookies. In some cases, the safe stack improves performance due to better cache locality.

Our current implementation of the safe stack is stable and robust, we used it to recompile multiple projects on Linux including Chromium, and we also recompiled the entire FreeBSD user-space system and more than 100 packages. We ran unit tests on the FreeBSD system and many of the packages and observed no errors caused by the safe stack. The safe stack is also fully binary compatible with non-instrumented code and can be applied to parts of a program selectively.

This patch is our implementation of the safe stack on top of the current SVN HEAD of LLVM (r221153). The patches make the following changes:

  • Add the safestack function attribute, similar to the ssp, sspstrong and sspreq attributes.
  • Add the SafeStack instrumentation pass that applies the safe stack to all functions that have the safestack attribute. This pass moves all unsafe local variables to the unsafe stack with a separate stack pointer, whereas all safe variables remain on the regular stack that is managed by LLVM as usual.
  • Invoke the pass as the last stage before code generation (at the same time the existing cookie-based stack protector pass is invoked).
  • Add unit tests for the safe stack.

Diff Detail

Event Timeline

ksvladimir updated this revision to Diff 15714.Nov 3 2014, 9:35 AM
ksvladimir retitled this revision from to Protection against stack-based memory corruption errors using SafeStack.
ksvladimir updated this object.
ksvladimir edited the test plan for this revision. (Show Details)
ksvladimir added a reviewer: theraven.
ksvladimir added a subscriber: Unknown Object (MLST).
colinl added a subscriber: colinl.Nov 3 2014, 10:25 AM
theraven added inline comments.Nov 3 2014, 10:37 AM
lib/CodeGen/SafeStack.cpp
231 ↗(On Diff #15714)

The first check should be F.isIntrinsic(). I'm a bit surprised it's needed though, because intrinsics should never have be definitions in the IR...

237 ↗(On Diff #15714)

It's more likely that functions won't have the safe stack attribute than that they'll start with llvm, so I'd switch the order of this test and the previous one.

287 ↗(On Diff #15714)

The string "llvmunsafe_stack_ptr" appears in (at least) two places, please make it a constant somewhere (ideally somewhere that can be shared with compiler-rt, although that's a bit harder).

329 ↗(On Diff #15714)

unwound

338 ↗(On Diff #15714)

These three shouldn't change between functions. Make them fields and initialise them in the module init code.

392 ↗(On Diff #15714)

We save

lib/Target/X86/X86ISelLowering.cpp
1947 ↗(On Diff #15714)

These look like quite magic numbers - please document where they come from (why does Linux use fs- or gs-relative things depending on whether it's 64-bit, whereas Darwin uses gs-relative addressing all of the time). The isTargetLinux() test looks wrong, as this looks to be something that relates to userland ABI and not to the kernel. What is responsible for setting up the unsafe stack pointer?

kcc added a subscriber: kcc.Nov 3 2014, 3:09 PM

I am curious why you are doing transformations in CodeGen as opposed to LLVM IR?

Note that AddressSanitizer has similar transformation done as an LLVM IR pass (i.e. 'opt', not 'llc')
which makes testing much simpler (IMHO) and not x86-dependent.
See FunctionStackPoisoner::poisonStack in lib/Transforms/Instrumentation/AddressSanitizer.cpp

emaste added a subscriber: emaste.Nov 3 2014, 8:43 PM

Yes, running SafeStack with opt would certainly simplify debugging.
However, we want to apply the SafeStack transformation as the very last
step before code generation, to make sure that it operate on the final
stack layout. Doing so earlier might prevent some other optimizations from
succeeding (as it e.g., complicates the alias analysis, breaks mem2reg
pass, etc.) or might force the SafeStack pass move more objects to the
unsafe stack than necessary (e.g., if the operations on such objects that
the SafeStack considered potentially unsafe are actually later optimized
away). In principle, in some pathological cases, it might even break
correctness, e.g., if the SafeStack decides to keep some object on the
normal stack, but the subsequent optimization or instrumentation passes add
potentially unsafe operations on such objects.

ksvladimir updated this revision to Diff 15775.Nov 4 2014, 11:20 AM

Addresses comments on the previous submission.

You can find the detailed changelog since the previous submission in our repo: https://github.com/cpi-llvm/llvm/commits/safestack-r221153

amanone added a subscriber: amanone.Nov 6 2014, 2:26 AM
abique added a subscriber: abique.Nov 13 2014, 2:05 AM

Simplified safestack public symbol names.

pcc added a subscriber: pcc.Apr 10 2015, 6:52 PM

Just some random observations as I work on refreshing this patch against trunk.

test/CodeGen/X86/safestack.ll
1 ↗(On Diff #16225)

This will become a much more precise IR-level test.

379 ↗(On Diff #16225)

What? This seems like it needs protection to me. The callee could store the integer somewhere, or use inttoptr, or something.

1332 ↗(On Diff #16225)

We don't need 25 separate tests that the pass can check function attributes correctly. Just one is enough.

pcc added inline comments.Apr 10 2015, 7:07 PM
test/CodeGen/X86/safestack.ll
379 ↗(On Diff #16225)

Oh, I see that this is because the function (wrongly) has the readnone attribute. I'll fix the test case.

pcc commandeered this revision.Apr 23 2015, 3:41 PM
pcc added a reviewer: ksvladimir.

After private discussions with Volodymyr and his team at EPFL, I've agreed to take over the SafeStack patches. I'm about to upload a new set of patches that are refreshed against LLVM trunk. The new LLVM patch addresses Kostya's concern by moving the new pass under lib/Transforms and adding IR-level tests.

pcc updated this revision to Diff 24337.Apr 23 2015, 3:44 PM

Refresh, move pass to lib/Transforms

ksvladimir edited edge metadata.Apr 24 2015, 6:00 AM

Peter, thank you for helping with the patches! The updated patches also include minor bugfixes, cleanup and improved documentation. We also prepared a few more patches to submit separately, which enable applying SafeStack to shared libraries, support ucontext API and sigaltstack, and implement some platform-specific performance improvements.

pcc updated this revision to Diff 25096.May 6 2015, 3:43 PM
pcc edited edge metadata.
  • Remove Darwin platform-specific TLS code
kcc added inline comments.May 18 2015, 11:56 AM
include/llvm/Analysis/TargetTransformInfo.h
507 ↗(On Diff #25096)

Do we need this at all?

lib/Transforms/Instrumentation/SafeStack.cpp
257

const variables are named like kUnsafeStackPtrVar

542

Is this tested in any of the unit tests?

test/Transforms/SafeStack/safestack.ll
1 ↗(On Diff #25096)

A comment would be nice.
Explain why you have CHECK and LINUX
Consider splitting this test into several

kcc added inline comments.May 18 2015, 11:56 AM
lib/CodeGen/LLVMBuild.txt
25

why do you need this?

lib/Transforms/Instrumentation/SafeStack.cpp
106
164

does it have to be a module pass?
why not a function pass?

245

here and elsewhere: period after a comment.

250

why int32 here?

253

which of the ways is used where? do we need both?

272

why not just assert?

287

This function is too big. Please split it into as many smaller ones as possible. With comments.

290

const?

329

do you need this comment?

pcc updated this revision to Diff 26082.May 19 2015, 12:39 PM
  • Remove TargetTransformInfo stuff
  • Rename variable
  • Introduce LLVM_FALLTHROUGH macro, start using it in safe stack
  • Make SafeStack a FunctionPass
  • Add periods
  • Fix more comments, remove commented-out code
  • Outline moveStaticAllocasToUnsafeStack
  • Outline moveDynamicAllocasToUnsafeStack
  • Use range for loop
  • Use auto where type is obvious
  • getOrCreateUnsafeStackPtr once
  • Outline findInsts and createStackRestorePoints
  • Fix typo
  • Remove braces
  • Remove LINUX test stuff
  • Split test files
  • Revert whitespace change
include/llvm/Analysis/TargetTransformInfo.h
507 ↗(On Diff #25096)

Removed. We can easily restore this hook if we ever need it.

lib/CodeGen/LLVMBuild.txt
25

Because the CodeGen library now depends on the createSafeStackPass function declared in Instrumentation.

lib/Transforms/Instrumentation/SafeStack.cpp
106

Done, introducing a macro LLVM_FALLTHROUGH in llvm/Support/Compiler.h because of r234788.

164

It can be a function pass; done.

245

Done

250

This code is now gone.

253

The first code path was associated with the getUnsafeStackPtrLocation hook, which is now gone, so I've removed it.

257

Done

272

It is possible to fail these checks with "valid" (modulo the use of reserved identifiers) C translation units. Consider for example the following translation unit which uses __safestack_unsafe_stack_ptr as both a regular and thread-local variable.

void *__safestack_unsafe_stack_ptr = 0;

void f(char *);

void g() {
  char foo[64];
  f(foo);
}

Rather than asserting (or crashing horribly later in non-asserts builds), it would be better to abort early with report_fatal_error.

287

Done

290

Now an enum

329

Removed

542

This is now covered by setjmp.ll and setjmp2.ll.

test/Transforms/SafeStack/safestack.ll
1 ↗(On Diff #25096)

Explain why you have CHECK and LINUX

The latter was testing the non-getUnsafeStackPtrLocation case, which is now the only case; removed.

Consider splitting this test into several

Done

kcc added inline comments.May 19 2015, 3:49 PM
include/llvm/IR/Attributes.h
110

Shouldn't we document it in docs/LangRef.rst?

pcc updated this revision to Diff 26104.May 19 2015, 4:36 PM
  • Document safestack attribute
include/llvm/IR/Attributes.h
110

Done

kcc added inline comments.May 19 2015, 5:24 PM
lib/Transforms/Instrumentation/SafeStack.cpp
543

I am puzzled. Where is UnsafeStackPtr defined?
It should probably be defined at module init time, not here.

pcc updated this revision to Diff 26111.May 19 2015, 5:43 PM
  • Init UnsafeStackPtr at module init time
lib/Transforms/Instrumentation/SafeStack.cpp
543

The global is declared only if we see a function with the safe_stack attribute. I decided that it would be better to define it here rather than at module init time because the latter would cause the global to be declared in every module that the backend sees. This could be problematic if the target does not support thread local variables, for example. (Although now that I've tried it, it does not appear to break any existing tests in check-llvm. Let's just move it to module-init and see what happens.)

MatzeB added a subscriber: MatzeB.May 19 2015, 6:49 PM

Very interesting approach. I am not the right person to approve this patch though, so just some comments:

include/llvm/Support/Compiler.h
32–35 ↗(On Diff #26111)

This should probably go into a separate patch.

include/llvm/Transforms/Instrumentation.h
135–137

Don't repeat method names in documentation comments, this practice is discouraged.

lib/Transforms/Instrumentation/SafeStack.cpp
173

Why is it necessary to have some minimum alignment and why is it 16?

311

Maybe move this declaration down in front of the if that first defines it.

test/Transforms/SafeStack/cast.ll
7–8

I would have expected this to require a protector.

pcc updated this revision to Diff 26116.May 19 2015, 7:50 PM
  • Fix redundant doxygen comment
  • Move variable declaration
include/llvm/Support/Compiler.h
32–35 ↗(On Diff #26111)

r237766

include/llvm/Transforms/Instrumentation.h
135–137

Done

lib/Transforms/Instrumentation/SafeStack.cpp
173

For the same reason that the regular stack has an alignment, e.g. see http://stackoverflow.com/questions/4175281/what-does-it-mean-to-align-the-stack

16 seems like a reasonable upper bound on the alignment of objects that we might expect to appear on the stack on most common targets. We can always change this number later if there is a compelling need to, but at least to start with it's simplest to pick a constant and use it everywhere.

311

Done

test/Transforms/SafeStack/cast.ll
7–8

No. Simply converting a pointer to an integer (or vice versa) cannot leak the address of the safe stack, as the conversion by itself does not cause the address to escape the function. The situation may be different depending on what we do with the converted pointer (e.g. if we store it somewhere), but in this case we are just doing a conversion.

ksvladimir added inline comments.May 19 2015, 10:09 PM
lib/Transforms/Instrumentation/SafeStack.cpp
231

You can do a quick scan over all functions in a Module to check if any of them have Attribute::SafeStack, and only create the UnsafeStackPtr if it is the case. This way, the variable won't be created when -fsanitize=safe-stack is not used. You can also store the result of the scan in a class member variable and exit runOnFunction immediately when safestack is not needed.

pcc added inline comments.May 20 2015, 4:59 PM
lib/Transforms/Instrumentation/SafeStack.cpp
231

Yes, there are many ways we could create the global on demand, but it's simplest to always create it if that works.

jfb added a subscriber: jfb.May 26 2015, 2:58 PM

Some early comments, I haven't finished going through the changes but this should be a good start!

lib/Transforms/IPO/Inliner.cpp
97

Was StackProtectReq simply missing?

It looks like there's a lattice of stack protection mechanisms, but it's not documented AFAICT. Could you document it somewhere?

lib/Transforms/Instrumentation/SafeStack.cpp
12

Add link to safe stack docs.

16

DEBUG_TYPE has to be after includes to avoid nasty ODR violations.

94

I'm assuming that's also true if the GEP is inbounds? Could the comment also state this.

124

"a function that only reads memory nor returns any value" The "nor" seems wrong here.

129

Are there any read-only functions with no return value? I'm not sure that makes much sense, and I don't see a test fo it.

147

Don't you end up seeing uses of alloca through intrinsics such as memset and memcpy? They can be added if needed, but since these two act the same as load/store I'd think that they are safe.

172

Why 16? Could you also document how this is used, and how it takes into account target alignment?

254

This TLS model is for variables in modules that will not be loaded dynamically. This sanitizer can be used in executables, and with shared libraries that don't have safestack, but not with executables that used shared libraries with safestack?

Shouldn't this use GeneralDynamicTLSModel instead?

I'd like a comment that explains the choice.

301

Do the llvm.stacksave/llvm.stackrestore, gcroot, frameaddress intrinsics need to be handled?

pcc updated this revision to Diff 26545.May 26 2015, 4:12 PM
  • Address review comments
lib/Transforms/IPO/Inliner.cpp
97

Was StackProtectReq simply missing?

Previously we never needed to remove StackProtectReq, as it was the highest protection level.

It looks like there's a lattice of stack protection mechanisms, but it's not documented AFAICT. Could you document it somewhere?

The lattice for the ssp* attributes were previously documented in http://llvm.org/docs/LangRef.html#function-attributes . I've added similar documentation for safe_stack.

lib/Transforms/Instrumentation/SafeStack.cpp
12

Done

16

Done

94

Done

124

Fixed

129

Are there any read-only functions with no return value?

void noop() {} ? :)

I don't see a test fo it.

Added.

147

Yes, but let's add support for these intrinsics in a separate change.

172

Documented

254

This TLS model is for variables in modules that will not be loaded dynamically. This sanitizer can be used in executables, and with shared libraries that don't have safestack, but not with executables that used shared libraries with safestack?

Added comment.

It can be used only in executables compiled with safestack (and in principle in DSOs where the executable is compiled with safestack, but we currently forbid this.) In each of these cases, the TLS variable lives in the main executable, so it is safe to use initial-exec. (MSan and DFSan do something similar.)

301

We handle stacksave/stackrestore in SafeStack::moveDynamicAllocasToUnsafeStack.

We don't currently support gcroot, added an error path here.

frameaddress currently has the expected behavior (see clang docs).

pcc updated this revision to Diff 26547.May 26 2015, 4:17 PM
  • clang-format
jfb added a comment.May 29 2015, 9:57 AM

I like the technical approach overall, but the testing strategy worries me. Specifically, this is now at the IR level and I have a hard time convincing myself that the safe stack's location isn't moved to other registers, or stored on the unsafe stack or heap. This isn't just about the current implementation: I worry of breaking safe stack as LLVM gains new features (e.g. GC roots breaks it, adding similar features would silently do the same), or with different runtimes.

The only way I can think of convincing myself is by using binary instrumentation: keep track of safe stack ranges for each thread at runtime, and use QEMU/Pin/Valgrind/... to find any leaks. This will have false positives, but assuming there's no stack-cookie-like leaks then the lack of any warnings would mean that the safe stacks' locations aren't leaking. This tool could be run on the test suite.

I don't want to block checking in safe stack on such a tool, but I would be wary of using it as a security feature without having tested it.

Thoughts?

lib/Transforms/Instrumentation/SafeStack.cpp
129

I asked the wrong question :-)

Are there any read-only functions with no return value which also capture pointers? The example you added looks like what I expected... but I don't get what such a function could do. It seems pretty useless! If so then it doesn't seem worth handling it specially here (why optimize something nobody in their right mind would do?).

147

Sounds good. Could you add a FIXME for this?

341

/* ArraySize= */ nullptr

427

Use alignAddr from MathExtras.h instead.

445

alignAddr

kcc added a comment.May 29 2015, 10:03 AM
In D6094#181007, @jfb wrote:

I like the technical approach overall, but the testing strategy worries me. Specifically, this is now at the IR level and I have a hard time convincing myself that the safe stack's location isn't moved to other registers, or stored on the unsafe stack or heap. This isn't just about the current implementation: I worry of breaking safe stack as LLVM gains new features (e.g. GC roots breaks it, adding similar features would silently do the same), or with different runtimes.

The only way I can think of convincing myself is by using binary instrumentation: keep track of safe stack ranges for each thread at runtime, and use QEMU/Pin/Valgrind/... to find any leaks. This will have false positives, but assuming there's no stack-cookie-like leaks then the lack of any warnings would mean that the safe stacks' locations aren't leaking. This tool could be run on the test suite.

I don't want to block checking in safe stack on such a tool, but I would be wary of using it as a security feature without having tested it.

Thoughts?

Won't it be enough to have full (runnable) tests like another patch (http://reviews.llvm.org/D6096) already has?
We can (and absolutely must!) add more of those tests in subsequent commits.

jfb added a comment.May 29 2015, 10:07 AM
In D6094#181019, @kcc wrote:
In D6094#181007, @jfb wrote:

I like the technical approach overall, but the testing strategy worries me. Specifically, this is now at the IR level and I have a hard time convincing myself that the safe stack's location isn't moved to other registers, or stored on the unsafe stack or heap. This isn't just about the current implementation: I worry of breaking safe stack as LLVM gains new features (e.g. GC roots breaks it, adding similar features would silently do the same), or with different runtimes.

The only way I can think of convincing myself is by using binary instrumentation: keep track of safe stack ranges for each thread at runtime, and use QEMU/Pin/Valgrind/... to find any leaks. This will have false positives, but assuming there's no stack-cookie-like leaks then the lack of any warnings would mean that the safe stacks' locations aren't leaking. This tool could be run on the test suite.

I don't want to block checking in safe stack on such a tool, but I would be wary of using it as a security feature without having tested it.

Thoughts?

Won't it be enough to have full (runnable) tests like another patch (http://reviews.llvm.org/D6096) already has?
We can (and absolutely must!) add more of those tests in subsequent commits.

My concern is that IR may look OK in the tests, but further passes or the ISA-specific lowering could leak the safe stack's location. I'm also not sure small tests cover the entirety of what we'd want to test, especially when we consider what the optimizer can do.

Agreed the tests are useful! I'm just not sure they're sufficient.

kcc added a comment.May 29 2015, 10:23 AM

My concern is that IR may look OK in the tests, but further passes or the ISA-specific lowering could leak the safe stack's location.

Of course. That's why we have full runnable tests.

I'm also not sure small tests cover the entirety of what we'd want to test, especially when we consider what the optimizer can do.

Agree.
I don't see a simple solution here (same for, e.g. CFI instrumentation).
We'd need to ask other experts to try to break this protection.

We may also try building something huge (chromium) and performing static binary code analysis.
That's well outside of what we can do with unit tests..

Agreed the tests are useful! I'm just not sure they're sufficient.

My concern is that IR may look OK in the tests, but further passes or the ISA-specific lowering could leak the safe stack's location.

Please note, that the current patch does not do anything against leakage. The primary issue with preventing leaks is not necessarily the generated machine code, but libraries. For instance, libc definitely leaks the stack pointer in several ways (e.g., setjmp, getcontext, sigset, etc.). The idea is that going forward, we'd fix these in libc and in other low-level libraries, by either eliminating the escaping/dumping of %rsp when that's possible, or by using encryption/PTR_MANGLE (XOR-ing the dumped stack pointer with another secret we control and protect better). This is actually already done for setjmp in glibc, for example.

I was planning to write a static binary verifier at some point, that would make sure that the stack pointer is either not written to memory, or if it is, its written only to the safe stack. Verifying that it's never stored can be done with a pretty simple intra-procedural data-flow analysis on the assembly code. Checking that the stack pointer spilled to the (safe) stack never leaves the (safe) stack is a bit harder, due to aliasing (e.g. push %rsp, then later mov (%rsp-8), %rax; mov %rax, (%rdi)), but it can be done as well. This verifier could be included as machine function pass in the code generator or in the assembler later on.

Laszlo

jfb added a comment.May 29 2015, 3:06 PM

My concern is that IR may look OK in the tests, but further passes or the ISA-specific lowering could leak the safe stack's location.

Please note, that the current patch does not do anything against leakage. The primary issue with preventing leaks is not necessarily the generated machine code, but libraries. For instance, libc definitely leaks the stack pointer in several ways (e.g., setjmp, getcontext, sigset, etc.). The idea is that going forward, we'd fix these in libc and in other low-level libraries, by either eliminating the escaping/dumping of %rsp when that's possible, or by using encryption/PTR_MANGLE (XOR-ing the dumped stack pointer with another secret we control and protect better). This is actually already done for setjmp in glibc, for example.

I was planning to write a static binary verifier at some point, that would make sure that the stack pointer is either not written to memory, or if it is, its written only to the safe stack. Verifying that it's never stored can be done with a pretty simple intra-procedural data-flow analysis on the assembly code. Checking that the stack pointer spilled to the (safe) stack never leaves the (safe) stack is a bit harder, due to aliasing (e.g. push %rsp, then later mov (%rsp-8), %rax; mov %rax, (%rdi)), but it can be done as well. This verifier could be included as machine function pass in the code generator or in the assembler later on.

I think this would be a pretty great addition to the documentation. Expand the caveats section, and document what can be done to fix them.

pcc updated this revision to Diff 26841.May 29 2015, 7:46 PM
  • Address review comments
pcc added inline comments.May 29 2015, 7:48 PM
lib/Transforms/Instrumentation/SafeStack.cpp
129

Good point. I don't think there are, which pretty much makes this test redundant (or at least it ought to be redundant provided that we're inferring attributes correctly). Removed along with the test.

147

Done

341

Done

427

alignAddr takes a pointer; used RoundUpToAlignment.

445

Likewise

Both dynamic and static leaks verifiers are great ideas! In practice, it might also be useful to have a pass that looks for all uses of known ways to leak the stack pointer in the IR, i.e., frameaddr-like intrinsics, gcroot, inline asm that accesses %rsp, etc. This wouldn't be as future proof as binary verifiers, but might be easier to implement and use.

Perhaps sometime in the future the libraries problem will be solved by compiling the libraries with safestack as well, at least on platforms like Android or ChromeOS.

lib/Transforms/Instrumentation/SafeStack.cpp
255

Perhaps it's worth explaining that adding shared libraries support in the future might require adjusting the TLS model for shared libraries.

jfb added a comment.Jun 15 2015, 2:56 AM

Sorry it took me so long to get back to this... With the latest edits this patch lgtm. I've already lgtm'd the clang and compiler-rt patches.

This revision was automatically updated to reflect the committed changes.
jfb added a reviewer: jfb.Sep 13 2015, 6:20 PM