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, Stephen Crane Secure Systems and Software Lab UC Irvine [1] A. Homescu, S. Neisius, P. Larsen, S. Brunthaler, and M. Franz; “Profile-guided Automated Software Diversity,” in 2013 International Symposium on Code Generation and Optimization (CGO 2013), Shenzhen, China; February 2013.
Hi Stephen,> 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). >I think that this is very interesting and I would like LLVM to have a "randomness” feature. I think that it is useful for other aspects of security as well.> 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.Okay.> 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. >Which scheduler did you modify ? The plan is to disable the SelectionDAG scheduler and move to the MI Scheduler soon. Also, have you looked at randomizing register-allocation ?> 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.I am not sure why you need this feature. You can provide LLVM with a SEED value that can be controlled from the command line. A wrapper (such as a build-script) can control this value.> > 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.Please make sure that the LLVM nightly test suite passes with randomization enabled.> > Thanks, > Stephen Crane > Secure Systems and Software Lab > UC Irvine > > > [1] A. Homescu, S. Neisius, P. Larsen, S. Brunthaler, and M. Franz; > “Profile-guided Automated Software Diversity,” in 2013 International > Symposium on Code Generation and Optimization (CGO 2013), Shenzhen, > China; February 2013. > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Hi Nadav, Thanks for your interest! On 08/26/2013 11:51 AM, Nadav Rotem wrote:> Which scheduler did you modify ? The plan is to disable the > SelectionDAG scheduler and move to the MI Scheduler soon. Also, have > you looked at randomizing register-allocation ?Yes, we modified the SelectionDAG scheduler. This was before the MI scheduler was around, but we will look into porting our ideas over to the new scheduler. Register allocation randomization is in fact another of our existing transformations. We thought we would propose just a few simple transforms initially, but we can certainly include register randomization as well if there is enough interest.>> 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. > I am not sure why you need this feature. You can provide LLVM with a SEED value that can be controlled from the command line. A wrapper (such as a build-script) can control this value.We do in fact seed the RNG with a command line parameter (we reuse the -frandom-seed param that gcc implemented). However, we need some reproducible, cryptographically secure source of randomness for the each random decision made during our transformations. We have found that the system randomness (/dev/random) is insufficient for this purpose since reproducible builds (given the secret seed) are preferable. The only way to provide this reproducible stream of randomness is to have a process-specific RNG, which we implement on top of OpenSSL for simplicity.> Please make sure that the LLVM nightly test suite passes with > randomization enabled.Of course. Our patched version currently passes the existing test suite on x86_64, and after adding additional tests we will certainly make sure that the final patch passes the latest test suite. Thanks, Stephen
On Aug 26, 2013, at 11:39 AM, Stephen Crane <sjcrane at uci.edu> wrote:> 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.How is the "diverse population" of binaries generated and delivered? The tradition software development model is to qualify one “golden master” which is then duplicated to all customers. -Nick
> > 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. > > I am not sure why you need this feature. You can provide LLVM with a > SEED value that can be controlled from the command line. A wrapper (such > as a build-script) can control this value.(disclaimer: I was a member of Stephen's research group and worked on this project.) To my knowledge, the pseudorandom number generator in LLVM is not cryptographically secure. In this use case, the intent is to make it difficult to get the random number seed or the generator's state at any point in the random number stream by looking at the output. If the state of the generator can be compromised, then an attacker can predict the output of the generator by playing it forward. If an attacker can play the generator forward, then the attacker can reproduce the rest of the executable, including the randomized components that are no longer random to the attacker. Reproducing the executable means that diversification isn't going to work because the attacker can plan around it. For reproducibility, such as for debugging, a pure software generator is a good idea. This also prevents blocking read operations in the generator, slowing down the compiler. Software generators can be optimized for speed. These are reasons to avoid /dev/random et al. Personally, I think it is necessary to go for the strongest random number generator possible. Cryptographically secure pseudorandom number generators have good properties that make them resistant to compromise. In the case of the generator I think Stephen is proposing -- a generator based on running AES-128 in Counter Mode and described in one of NIST's documents -- the security comes from strong crypto building blocks, while still suitable for embedding in a compiler. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130826/5464f79f/attachment.html>
Stephen Checkoway
2013-Aug-27 05:16 UTC
[LLVMdev] Adding diversity for security (and testing)
On Aug 26, 2013, at 2:39 PM, Stephen Crane <sjcrane at uci.edu> wrote:> 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.Putting on my security hat (as opposed to my lurking-on-compiler-mailing-lists hat), note that artificial software heterogeneity doesn't actually prevent ROP, it makes it harder in a qualitatively similar way to ASLR. With ASLR, the attacker needs to discover a single memory address in order to construct a return-oriented program. What you're proposing requires reading out more of the address space. A recent paper at Oakland proposed a "just-in-time code reuse" attack that repeatedly uses a memory disclosure and JITs an attack based on the results [1]. So while it does make the attackers job harder, it doesn't prevent such attacks. 1. Kevin Z. Snow, Fabian Monrose, Lucas Davi, Alexandra Dmitrienko, Christopher Liebchen, and Ahmad-Reza Sadeghi. Just-In-Time Code Resule: On the Effectiveness of Find-Grained Address Space Layout Randomization. In Proceedings of the IEEE Symposium on Security and Privacy ("Oakland") 2013. <http://cs.unc.edu/~fabian/papers/oakland2013.pdf> -- Stephen Checkoway
Hi Nick, On 08/26/2013 02:01 PM, Nick Kledzik wrote:> How is the "diverse population" of binaries generated and delivered? > The tradition software development model is to qualify one “golden > master” which is then duplicated to all customers. -NickYes indeed. Adding diversity at compilation requires that the code producer create a population of variants. However, by introducing diversity at compile-time, we have much greater freedom in transforming the end result with lower performance impact. In addition, producing variants during distribution allows the distributor to use diversity to provide a certain amount of watermarking and protection against client-side tampering (jailbreaking, etc). We initially forsee that this could be especially used where security was of the utmost concern. Open-source end users often have the option of compiling from source, and could create their own diversified versions, especially for criticial services. We think this would be an ideal situation to begin adopting diversity for security. Of course, in the testing use-case, creating various versions is fairly trivial. These versions could then be compared for testing for micro-architectural and compiler corner cases, as well as performance. Finally, for wide-spread adoption, we are currently researching ways to cache the bulk of the compilation effort and create many variants for distribution in a cost-effective manner using cloud compilation. In addition, error reporting can be normalized with knowledge of the secret random seed by regeneration of the particular binary. Hope this helps to explain our ideas in more clarity. - stephen
On 08/26/2013 10:16 PM, Stephen Checkoway wrote:> Putting on my security hat (as opposed to my > lurking-on-compiler-mailing-lists hat), note that artificial software > heterogeneity doesn't actually prevent ROP, it makes it harder in a > qualitatively similar way to ASLR. With ASLR, the attacker needs to > discover a single memory address in order to construct a > return-oriented program. What you're proposing requires reading out > more of the address space. A recent paper at Oakland proposed a > "just-in-time code reuse" attack that repeatedly uses a memory > disclosure and JITs an attack based on the results [1]. So while it > does make the attackers job harder, it doesn't prevent such attacks. > 1. Kevin Z. Snow, Fabian Monrose, Lucas Davi, Alexandra Dmitrienko, > Christopher Liebchen, and Ahmad-Reza Sadeghi. Just-In-Time Code > Resule: On the Effectiveness of Find-Grained Address Space Layout > Randomization. In Proceedings of the IEEE Symposium on Security and > Privacy ("Oakland") 2013. > <http://cs.unc.edu/~fabian/papers/oakland2013.pdf>Hi Stephen, Great to see a fellow security researcher lurking on this list as well! You raise a very valid point here. I quite agree that diversity is not guaranteed to prevent ROP. Very sorry -- I wasn't as careful in my original wording as I certainly should have been. In practice, we believe introducing variation significantly raises the bar for attackers, which is a big step in the right direction. For many applications this may be more than sufficient. However, diversity may not be good enough for all applications, particularly in the presence of possible remote memory disclosures. - stephen
On 26 August 2013 11:39, Stephen Crane <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. 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. Looking forward to seeing patches! Nick -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130828/f3b8eea5/attachment.html>
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>
On 08/28/2013 02:37 PM, Nick Lewycky wrote:> 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".Yes, definitely. Deployment is an issue which users will need to consider when deciding whether to use compiler-based diversity. However there are certainly use-cases which could benefit, especially in small deployments. Additionally, the benefits may outweigh the increase in deployment costs for larger deployments.> 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.Briefly looking at ASAN again, I saw a performance penalty of 2x mentioned. Diversity could act as both defense in depth, and as a lower-impact defense for performance critical code.> 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.Completely agree, and that's exactly what we have done.> 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).Unfortunately testing for security is a difficult problem. We have currently been evaluating our work by comparing a population of randomized variants to make sure that no gadgets are the same across variants. While this is reasonable for research evaluation, I'm not sure that would be practical (or useful) for the compiler test suite. To prevent regressions, I think the test suite will need to test at least 3 major areas: making sure that RNG results are consistent and deterministic, testing that NOPs are actually inserted and scheduling decisions randomized, and verifying that different seeds result in entirely different binaries with approximately equal amounts of diversifications. Speaking of maintenance, we plan to continue work on this in our lab. We can certainly maintain these features at least for the next year and a half, and possibly longer.> 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.As mentioned, we have an implementation of register randomization, although it will require some reworking to be ready for prime-time. We can definitely look into getting that polished. - stephen