[LLVMdev] Adding diversity for security (and testing)

[John Criswell]

On 8/28/13 4:37 PM, Nick Lewycky wrote:
> On 26 August 2013 11:39, Stephen Crane <sjcrane at uci.edu 
> <mailto:sjcrane at uci.edu>> wrote:
>
>     Greetings LLVM Devs!
>
>     I am a PhD student in the Secure Systems and Software Lab at UC
>     Irvine. We have been working on adding randomness into code generation
>     to create a diverse population of binaries. This diversity prevents
>     code-reuse attacks such as return-oriented-programming (ROP) by
>     denying the attacker information about the exact code layout. ROP has
>     been used is several high-profile recent attacks, and has also been
>     used as a jailbreaking avenue. We believe our transformations would
>     provide a significant security benefit for LLVM users who choose to
>     use diversity. For more details see [1] (although we are currently
>     proposing to upstream only a simplified subset of our work).
>
>     We would like to contribute some of our work back to the community,
>     and are preparing a small patch adding two new features: NOP insertion
>     and schedule randomization. The NOP insertion pass randomly adds NOPs
>     after each MachineInstr according to a command-line
>     parameter. Currently NOP insertion is implemented for X86, and we are
>     adding support for ARM. The schedule randomizer randomly picks a valid
>     instruction to schedule at every point, bypassing the scheduling
>     heuristics. These passes result in a binary which, while slightly
>     slower, is far more secure against code-reuse attacks. In addition,
>     schedule randomization may be useful for randomized compiler and
>     micro-architecture testing.
>
>     We would also include a secure random number generator which links
>     against OpenSSL. This would of course be an optional module disabled
>     by default, but is necessary so the randomization is cryptographically
>     secure and useful in security applications.
>
>     We are in the process of writing test cases and double checking
>     formatting to produce a useful patch, but would like to solicit
>     feedback on our proposed changes before submitting patches for
>     detailed consideration.
>
>
> Thanks. This is really interesting -- it's hard to find good 
> protections against ROP attacks, and this is promising. However, I'm 
> going to start with the "bad news" first. I have a few questions as to 
> whether this is useful for our (llvm's) users in the real world:
>
> 1. I'm concerned about the deployment problem. I realize that being in 
> the compiler means you can transform the program in more exciting 
> ways, but it gives you a much worse deployment story than something 
> which modifies the program on disk like "prelink".
>
> 2. Does this actually fill a gap in our protections? How do we ever 
> get into the situation where the user is able to deploy a ROP attack 
> against us, without tripping asan or ubsan or something caught by our 
> warnings or the static analyzer or any of the other protections 
> offered by clang and llvm? It may suffice that there exists a niche 
> which can't afford the performance penalty from asan or other things, 
> but then we'll need to discuss what the performance impact is.

Tools like asan and ubsan don't detect ever type of problem.  From my 
understanding of asan, it only performs checks on loads and stores and 
delays reuse of virtual address space for memory allocations, so it is 
not guaranteed to catch all use-after-free and array bounds errors.  To 
catch everything, you would need to use a tool like Softbound + CETS.  
Even then, you need to exercise all the program paths which I suspect 
does not happen in practice.

Static analysis tools don't find every possible memory safety bug, 
either.  I believe it's theoretically impossible for them to do so.

Run-time protections are attractive because they can guarantee that some 
bad behavior does not happen in any execution of the program.

>
> 3. Reproducible builds are a must. GCC has a -frandom-seed=text flag 
> and you should use that here too. Given the same random seed, the 
> compiler shall produce the same output.
>
> Ultimately my concern here derives from the fact that I do use clang 
> warnings today and I do use asan and ubsan today. If this 
> ROP-protection were added, I don't immediately see how I would use it. 
> Just being I'm not inside the target audience doesn't mean the target 
> audience doesn't exist, but I am asking for a little justification.
>
> And one issue for us, the llvm developers. If we're going to accept 
> this feature, own it and maintain it, how can we test it? We know how 
> to test for correctness and measure performance, we even understand 
> what protections -fstack-protector or ASAN offer and can write 
> spot-tests for them, but how can we measure the effectiveness of 
> probability-based ROP-protections? We don't need an answer to this 
> right now, but over time we'll be maintaining it, and it seems 
> plausible that we could accept a patch which accidentally diminishes 
> the actual security provided (image us maintaining a random number 
> generator -- it's possible to add a weakness which isn't easily noticed).




>
> There's a "good news" side to this too. Over lunch I talked with one 
> of our security guys, and he's excited. He tells me that diversity for 
> ROP-protection is entirely the way to go, and speculates that it ought 
> to be deployable by other vendors. Furthermore, we expect that 
> rotating the register allocation is going to be especially painful on 
> the exploit authors.

Is there a reason why your security guy thinks that diversity is a 
better protection than control-flow integrity (CFI)?  Recent work on CFI 
[1] indicates that even very conservative call graphs remove nearly all 
gadgets from the list of valid function targets (hence they cannot be 
used).  That implementation has an average overhead of 3.6% and a max 
overhead of 8.6%.  A more flexible implementation [2] that already works 
for LLVM has average overhead of 10%. There's more recent work on CFI 
(including at least one paper that uses LLVM) published this month at 
Usenix Security, but I haven't had time to read it yet.

Control-flow integrity should be effective in stopping ROP attacks, and 
we should be able to deploy it without using inter-procedural analysis 
(although inter-procedural analysis can improve the call graph results 
to make the program even more secure).

I think diversity is a nice thing to have to provide defense in depth, 
but I currently think that CFI will provide the most bang for the buck.

-- John T.

[1] http://www.cs.berkeley.edu/~dawnsong/papers/Oakland2013-CCFIR-CR.pdf
[2] http://www.eecs.harvard.edu/~greg/papers/cfiDataSandboxing.pdf

>
> Looking forward to seeing patches!
>
> Nick
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130829/638e07fe/attachment.html>