llvm dev - Sep 2013 - [LLVMdev] Adding diversity for security (and testing)

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

On Aug 29, 2013, at 3:29 PM, Stephen Crane <sjcrane at uci.edu>
wrote:
> 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.
I also find the prelink approach interesting, particularly if the OS is already
doing prelinking.   The idea is that the compiler always generates one binary,
but it makes a record of permutation that could be made at prelink time.  For
instance, register r5 is restored in the epilog, but  it is only used in three
other instructions, so prelinking could switch them all to use r6.  Or here is
how to slide a block of code within a function.  The end result of these
recorded potential randomizations is to alter the ROP gadget.

This would allow you to generate one golden binary and release it, then on each
machine where it is installed, the prelinking would apply some random
permutations to the code.  You get your diversity across machines, but only need
to ship one binary.

-Nick

On 29 August 2013 15:29, Stephen Crane <sjcrane at uci.edu> wrote:
> 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.

Okay, I've been thinking about what I wanted answered here, and I've
decided that what I want to know is too complex for this discussion. It
boils down to: given we have all the power of clang and llvm for very
complex analysis, both static and dynamic, why is randomizing the best we
can do? Can't we somehow use all that static and dynamic analysis to shrink
the problem down to something we can solve more cleverly than randomizing
the program across a lot of axes, such as proving (or arranging for)
certain properties which reduce how much we need to randomize, etc? And if
not *why can't we*? It's that last part which I think is hardest to
answer,
so I've decided I'll leave this to the security-trained folks -- if they
think this is the right approach, they're probably right.

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.
>
I really like the idea of verifying that ROP gadgets work across different
variants. Even if it doesn't fit in the regression test suite, it should be
set up as an integration test.

The other three areas you identified largely fit in the regression suite.
Thanks!

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.

Fantastic!

Nick
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130909/332543af/attachment.html>

On 9/9/13 5:24 PM, Nick Lewycky wrote:
> [snip].
>
>
>     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.
>
>
> Okay, I've been thinking about what I wanted answered here, and
I've
> decided that what I want to know is too complex for this discussion. 
> It boils down to: given we have all the power of clang and llvm for 
> very complex analysis, both static and dynamic, why is randomizing the 
> best we can do? Can't we somehow use all that static and dynamic 
> analysis to shrink the problem down to something we can solve more 
> cleverly than randomizing the program across a lot of axes, such as 
> proving (or arranging for) certain properties which reduce how much we 
> need to randomize, etc? And if not *why can't we*? It's that last
part
> which I think is hardest to answer, so I've decided I'll leave this
to
> the security-trained folks -- if they think this is the right 
> approach, they're probably right.
You are right that, with LLVM and Clang's facilities, we can do better.  
However, in my opinion, the cost of many of these solutions is still too 
high (both in terms of development cost and run-time performance) for 
industry to accept them.  I am also of the opinion that many people do 
not understand the options that are available, partially because the 
work on the subject is spread across 4 different communities (compiler, 
operating systems, security, and software engineering).

Automatic, very strong memory safety guarantees are hard to enforce on 
existing C code with good efficiency.  It can be done, but it requires 
sophisticated analyses (e.g., type-inferencing, whole-program points-to 
analysis) and, therefore, requires a decent level of expertise and 
incurs significant developer cost.  Industry is also very picky about 
run-time performance; Vikram and I were told once by a bay-area company 
that they would only use a security solution if it added 0% run-time 
overhead.  Such performance goals will kill just about any solution.

Enforcing a weaker property like control-flow integrity looks very 
promising both in terms of development cost,  performance overhead, and 
security.  I'm not sure why it doesn't get more attention. Perhaps no 
one is yet willing to work out the remaining compatibility issues with 
native code libraries, or maybe industry wants someone else to build an 
open-source implementation first before committing to further 
development, or maybe people simply are unaware of what it is.  I'm 
curious to know.

If you're interested in knowing more about the topic, take a look at the 
Memory Safety Menagerie at http://sva.cs.illinois.edu/menagerie.  I need 
to update it since a few new papers have come out, but it provides a 
good number of papers on the subject (including quite a few that use LLVM).

My two cents.

-- John T.

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130910/73b075bf/attachment.html>