[LLVMdev] [PROPOSAL] Adding support for -fstack-protector-strong

[Magee, Josh]

Hello,

I plan to implement "Stack Smashing Protection - Strong" support in LLVM.
Below is a description of this feature and an overview of the implementation
plan. I have divided up the implementation into stages that can be delivered
incrementally.

I'm looking for any feedback (suggestions, requests, etc) before I actually
begin the work.

Thank you!
Josh


======================================
Stack-protector-strong support in LLVM
======================================

Introduction
------------
Stack Smashing Protection (SSP) aims to protect against buffer overflow attacks
by placing a 'canary' value on the stack that is validated upon exiting a
function.

LLVM currently supports SSP. Specifically it supports two modes:
-fstack-protector-all
- enables stack protectors for all functions
-fstack-protector
- Uses a heuristic to apply stack protectors only to functions that need it
- The heuristic checks for:
character arrays >= SSP_BUFFER_SIZE (default:8-bytes)
aggregates containing arrays >= SSP_BUFFER_SIZE *
alloca >= SSP_BUFFER_SIZE, or variable-sized alloca

These two options/modes are analogous to the options/modes supported by GCC.

* Note, there have been relatively recent commits to LLVM trunk improve the
state of SSP (e.g., checking for aggregates).


A short proposal was made to add a new SSP option to GCC: -fstack-protector-strong. [1]
Note, I am not the original author of the proposal. I just want to add it to LLVM :-).
Briefly, this option aims to enable heuristics that provide stronger protection
than -fstack-protector, but avoid the overkill of -fstack-protector-all. This
option has been accepted into the Google branch of GCC and presumably will
make its way into mainline GCC eventually.

The remainder of this documents discusses stack-protector-strong and presents
the proposed implementation work needed to support it in LLVM.

Requirements
------------
The requirements of -fstack-protector-strong are:
A) Stack protectors should be enabled for functions when:
1) An address of a local variable is taken in such a way as to expose the
address of a stack location.
- Example: the address of a local on the RHS of an assignment, the
address of a local passed into function.
- Note, source level addr-of expressions could be eliminated during
optimization, in which case they would not expose a stack address.
2) There is an array, regardless of type or size.
3) There is an aggregate which contains an array, regardless of array type or size.

B) The stack should be laid out such that:
1) Larger arrays and arrays nested in aggregates are closest to the stack guard.
2) Smaller arrays and arrays nested in aggregates are second closet to the stack guard.
3) Variables that have their address taken are third closet to the stack guard.
4) Scalars and pointers are furthest away from the stack guard.


The original proposal [1] lists an additional requirement that stack protectors
should be enabled for functions that have register local variables. This
requirement seems like it must be an error in the original proposal because it
does not make any sense. Register-keyword specified variables have no special
effect on CodeGen (the only effect is that the compiler will error if you
attempt to take an address-of such a variable.) If this was intended to refer
to variables that can be kept entirely in registers for their lifetime then
protectors are also not needed since such a variable would not expose any stack
address. In fact, the GCC patch does not implement this either, see [2].


Implementation
--------------
The bulk of the work required for stack-protector-strong is already implemented
for the existing stack-protector support.
The proposed work is:
1 Adding a new IR attribute "sspstrong":
ssp - SSP on, use basic heuristic
sspstrong - SSP on, use strong heuristic
sspreq - SSP on, required for function
- Note, I am proposing the IR attribute because it fits nicely into the
existing structure. An alternative choice would be to add a new CodeGen
option that would cause ssp-specified functions to be analyzed using the
strong heuristic. I prefer the attribute because it allows for finer
granularity (i.e., you could have one CU with both ssp and sspstrong
specified functions.
- Initially, sspstrong would work the same as sspreq. Once the "strong"
heuristic is implemented, then it would be used for sspstrong.

2 Adding the necessary command line switches to Clang:
- -fstack-protector-strong
- (-cc1) -stack-protector=n
0 = disabled
1 = ssp
2 = sspstrong [new]
3 = sspreq
- Logically, placing sspstrong at index 2 seems most appropriate.
However, it could be placed at 3 to avoid redefining the existing
semantics that 2 == sspreq.


3 Add Clang SSP attributes.
- Clang-level attributes that match the IR attributes and allow ssp,
sspstrong, and sspreq to be specified on a function-by-function basis.
- Already implemented privately for ssp and sspreq. Only sspstrong would
need to be added. Ultimately all attributes would be contributed to the
community.

4 Implement 'strong' heuristic in CodeGen/StackProtector.cpp
- Mostly relaxing checks in current StackProtector pass. For example, when
strong attribute is present, relax rules requiring arrays of char type,
ssp-buffer-size, etc.
- Add analysis to check for taking the address of local variables.
- Make the IR attribute 'sspstrong' to enable this heuristic.

5 Implement finer data layout rules.
- Most support is already there (e.g., large objects assigned before small
objects). What is needed is to extend the existing code to allow finer
granularity and distinction between different SSP-triggering objects.
- Some minor refactoring desired. For example, in
CodeGen/SelectionDAG/FunctionLoweringInfo.cpp, there are checks for
determining if an object would trigger a stack protectr (MayNeedSP). These
checks are inconsistent with the checks in StackProtector. Both of these spots
should use a common (i.e., same) check.

6) Updating/adding documentation.


Note that the appropriate regression tests (updating existing tests and adding
new ones) will be included with each stage.


Conclusion
----------
stack-protector-strong support builds upon the existing stack protector
implementation in LLVM. The primary implementation changes will be extending
analysis to meet the strong requirements and fine tuning the stack layout. The
most visible change will be the addition of a new IR attribute: sspstrong.


References
----------
[1] Original Proposal: https://docs.google.com/a/google.com/document/d/1xXBH6rRZue4f296vGt9YQcuLVQHeE516stHwt8M9xyU/edit?hl=en_US&ndplr=1&pli=1
[2] Code Review for patch to GCC implenting -fstack-protector-strong: http://codereview.appspot.com/5461043

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[David Chisnall]

On 2 Oct 2012, at 03:26, Magee, Josh wrote:

> 1) An address of a local variable is taken in such a way as to expose the
> address of a stack location.
> - Example: the address of a local on the RHS of an assignment, the
> address of a local passed into function.

This sounds like something that would be triggered for any function containing a block, even if the block doesn't do anything that is potentially unsafe. It also sounds like it would be triggered for a lot of C++ function s that allocates an object on the stack and call methods on them. Is it possible to tighten up the heuristic slightly so that this isn't the case? For blocks, in particular, you always have the IR for the block invoke function available in the compilation unit where you are creating the block (on the stack) and so you can potentially verify at compile time whether it is doing anything unsafe to any of the bound variables.

David

[John Criswell]

On 10/1/12 9:26 PM, Magee, Josh wrote:
> Hello,
>
> I plan to implement "Stack Smashing Protection - Strong" support in LLVM.
> Below is a description of this feature and an overview of the implementation
> plan. I have divided up the implementation into stages that can be delivered
> incrementally.
>
> I'm looking for any feedback (suggestions, requests, etc) before I actually
> begin the work.

If you're looking for a project to learn about LLVM and Clang, then I
think this is a great project. If the LLVM /Clang community wants this
feature so that it is feature-compatible with GCC, then I think
including this feature into LLVM/Clang makes sense.

If you want to protect applications from attack, then I think there are
far more productive and interesting things to work on than stack
protectors. Stack protectors are really a hack and, at best, only
protect against a single kind of attack (and with buffer overread
attacks, I'm not even sure if they do that very well). Even if they
work against stack buffer overflows, stack protectors don't protect the
application from heap overflows, invalid free attacks, dangling pointer
attacks, and non-control data attacks.

The fastest countermeasure that I think is worth looking at is Control
Flow Integrity (CFI); CFI adds checks to return instructions and
indirect jumps to ensure that they're jumping to a valid target
address. As far as I know, there's no control-hijack attack that works
against it, although non-control data attacks are still possible. The
fastest CFI implementation at present has an average overhead of 7.74%
on 32-bit x86, and by using a very conservative callgraph, you can use
it without whole program analysis. I've got the LLVM implementation
from the authors at LeHigh and am updating the code for x86_64 and LLVM
3.1 for use in one of my research projects. If you're interested in the
code, I can ask them if they'd be willing to release the code as
open-source.

Optimizations for memory safety tools like ASan, SAFECode, and SoftBound
would be even better since they also stop non-control data attacks.
Getting good performance out of them is difficult, though, and depending
on what sorts of overhead you're willing to tolerate, getting good
performance is still an open research question.

You might want to check out the memory safety menagerie
(http://sva.cs.illinois.edu/menagerie). It has lots of papers on
various techniques and optimizations for those techniques. You might
find something that will give you the security you want at the
performance you need.

In short, I think working on something that provides more comprehensive
protection is better than working on a partial hack.

My two (maybe four?) cents.

-- John T.

[Stephen Checkoway]

On Oct 2, 2012, at 11:52 AM, John Criswell <cris...@illinois.edu> wrote:

> (and with buffer overread attacks, I'm not even sure if they do that very well).

Indeed. For a homework assignment, I had my students perform a buffer overflow on the stack that overwrote the stack canary and still exploit an admittedly trivial target program.

--
Stephen Checkoway

[Robinson, Paul]

David Chisnall wrote:
>On 2 Oct 2012, at 03:26, Magee, Josh wrote:
>
>> 1) An address of a local variable is taken in such a way as to expose the
>> address of a stack location.
>> - Example: the address of a local on the RHS of an assignment, the
>> address of a local passed into function.
>

> It also sounds like it would be triggered for a lot of C++ function s that
> allocates an object on the stack and call methods on them. Is it possible
> to tighten up the heuristic slightly so that this isn't the case?

I don't see any inherent difference (for this purpose) between
void foo() {
int x;
someFunc(&x);
}
and
void foo() {
SomeClass x;
x.someNonStaticMethod();
}
It's just that C++ is so good at obscuring the details. Granted there is
no & operator in the second case, but the address of the stack-local object
is available to the called method without any hijinks, just like the address
of the stack-local variable is available to someFunc in the first case.

--paulr

[Magee, Josh]

At 1349295623 seconds past the Epoch, Robinson, Paul wrote:
> David Chisnall wrote:
> >On 2 Oct 2012, at 03:26, Magee, Josh wrote:
> >
> >> 1) An address of a local variable is taken in such a way as to expose the
> >> address of a stack location.
> >> - Example: the address of a local on the RHS of an assignment, the
> >> address of a local passed into function.
> >
> > It also sounds like it would be triggered for a lot of C++ function s that
> > allocates an object on the stack and call methods on them. Is it possible
> > to tighten up the heuristic slightly so that this isn't the case?
>
> I don't see any inherent difference (for this purpose) between
> void foo() {
> int x;
> someFunc(&x);
> }
> and
> void foo() {
> SomeClass x;
> x.someNonStaticMethod();
> }
> It's just that C++ is so good at obscuring the details. Granted there is
> no & operator in the second case, but the address of the stack-local object
> is available to the called method without any hijinks, just like the address
> of the stack-local variable is available to someFunc in the first case.

Right, in both cases a stack address is exposed. Both usages are so
common place that this will end up triggering protectors for a lot of
functions. In cases where the IR of the called function/method is
available, then it sounds reasonable to verify whether the callee
actually does anything "unsafe" with the address before triggering a
protector.

I'm not especially familiar with Blocks, but given that the IR is
always available then it makes sense to tighten up the heuristic
for Blocks first. After that it could be improved/tweaked for methods.

I think once the initial strong heuristic is in place, then we can
improve/tweak it as desired to accommodate these issues.

- Josh

[Magee, Josh]

At 1349203977 seconds past the Epoch, John Criswell wrote:
> If you're looking for a project to learn about LLVM and Clang, then I
> think this is a great project. If the LLVM /Clang community wants this
> feature so that it is feature-compatible with GCC, then I think
> including this feature into LLVM/Clang makes sense.

Yes, this is one reason - it seems like a reasonable project to get more
involved with the LLVM and Clang community. The other reason is that
this feature has been requested by developers at my place-of-work.

>
> If you want to protect applications from attack, then I think there are
> far more productive and interesting things to work on than stack
> protectors. Stack protectors are really a hack and, at best, only
> protect against a single kind of attack (and with buffer overread
> attacks, I'm not even sure if they do that very well). Even if they
> work against stack buffer overflows, stack protectors don't protect the
> application from heap overflows, invalid free attacks, dangling pointer
> attacks, and non-control data attacks.

I agree: Stack protectors only protect against one very specific kind of attack.

>
> The fastest countermeasure that I think is worth looking at is Control
> Flow Integrity (CFI); CFI adds checks to return instructions and
> indirect jumps to ensure that they're jumping to a valid target
> address. As far as I know, there's no control-hijack attack that works
> against it, although non-control data attacks are still possible. The
> fastest CFI implementation at present has an average overhead of 7.74%
> on 32-bit x86, and by using a very conservative callgraph, you can use
> it without whole program analysis. I've got the LLVM implementation
> from the authors at LeHigh and am updating the code for x86_64 and LLVM
> 3.1 for use in one of my research projects. If you're interested in the
> code, I can ask them if they'd be willing to release the code as
> open-source.

This sounds quite interesting - I'll definitely do some investigation into CFI.
If the authors are willing to release the source code as open-source
that would be great.

> Optimizations for memory safety tools like ASan, SAFECode, and SoftBound
> would be even better since they also stop non-control data attacks.
> Getting good performance out of them is difficult, though, and depending
> on what sorts of overhead you're willing to tolerate, getting good
> performance is still an open research question.
>
> You might want to check out the memory safety menagerie
> (http://sva.cs.illinois.edu/menagerie). It has lots of papers on
> various techniques and optimizations for those techniques. You might
> find something that will give you the security you want at the
> performance you need.
>
> In short, I think working on something that provides more comprehensive
> protection is better than working on a partial hack.
>
> My two (maybe four?) cents.

Thanks for the input. I agree that there are better security techniques
and countermeasures than SSP. At the end of the day SSP-strong is still
something I want to implement. Still, you have given me some food for
thought and a number of interesting tools and techniques to explore.

- Josh