llvm dev - Oct 2012 - [LLVMdev] [PROPOSAL] Adding support for -fstack-protector-strong

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

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

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.
>
> 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
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Oct 2, 2012, at 11:52 AM, John Criswell <criswell at 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

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

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