llvm dev - Nov 2015 - How to prevent registers from spilling?

Hi all,

I've been trying to figure out if there is a feasible way to prevent values
from ever spilling from registers to the stack. I've looked for code or
documentation on how to do this but haven't found anything, apologies if
this has already been done.

Recent security research has shown that protection schemes such as CFI
(that might otherwise be secure) are undermined by sensitive values
spilling to the stack. When security-critical values spill from registers
to the stack, they can be read and overwritten by an attacker with
arbitrary memory read or write capabilities. See "Losing Control" from
CCS
2015 for more details on this sort of attack:
https://www.ics.uci.edu/~perl/ccs15_stackdefiler.pdf

I think it would be great if we could allow values or at least virtual regs
to be tagged as "security-sensitive" and disallow spilling of these
values
across their lifetime. I expect that the best way to do this would be to
start at the virtual register level and push support up to IR values as
well if and only if machine IR turns out to be insufficient.

Is this a good idea? Does something to support register pinning already
exist? I'm unfortunately not familiar enough with the register allocators
to know how to best support this, although I'm willing to give it a try if
people can point me in the right direction.

Thanks,
Stephen
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151102/df93d380/attachment.html>

On Tue, Nov 3, 2015 at 6:24 AM, Stephen Crane via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Hi all,
>
> I've been trying to figure out if there is a feasible way to prevent
values
> from ever spilling from registers to the stack. I've looked for code or
> documentation on how to do this but haven't found anything, apologies
if
> this has already been done.
>
> Recent security research has shown that protection schemes such as CFI
(that
> might otherwise be secure) are undermined by sensitive values spilling to
> the stack. When security-critical values spill from registers to the stack,
> they can be read and overwritten by an attacker with arbitrary memory read
> or write capabilities. See "Losing Control" from CCS 2015 for
more details
> on this sort of attack:
https://www.ics.uci.edu/~perl/ccs15_stackdefiler.pdf
>
> I think it would be great if we could allow values or at least virtual regs
> to be tagged as "security-sensitive" and disallow spilling of
these values
> across their lifetime. I expect that the best way to do this would be to
> start at the virtual register level and push support up to IR values as
well
> if and only if machine IR turns out to be insufficient.
>
> Is this a good idea? Does something to support register pinning already
> exist? I'm unfortunately not familiar enough with the register
allocators to
> know how to best support this, although I'm willing to give it a try if
> people can point me in the right direction.
I don't a real answer for you, but my 1st idea is that it would be an
attribute you could apply to a variable. How you *force* that to never
spill on the backend is an entirely different issue. You'd basically
force a split on a certain variable under certain conditions - would
it be possible - (why not) Unless I'm missing something it would be
hell to schedule though..

There's use cases in HPC and GPGPU codes which may benefit from
something similar, but for different reasons. (Some really hot
variable that you never want spilled for example)

That breaks the whole IR idea of using alloca to allocate/denote space for local
variables, and then optimize those
into SSA values when optimization proves that is OK.

Also, for a lot of things, that attribute is simply impossible to implement. 
Any value that is live across a call needs to be spilled to memory.
You cannot put an unspillable value in a callee preserved register, because you
cannot know whether the callee may save that or not.
And if it is in a caller-save register, then the caller has to spill it if it is
live across a call.

Kevin B. Smith

-----Original Message-----
From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of C
Bergström via llvm-dev
Sent: Monday, November 02, 2015 3:30 PM
To: Stephen Crane
Cc: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] How to prevent registers from spilling?

On Tue, Nov 3, 2015 at 6:24 AM, Stephen Crane via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Hi all,
>
> I've been trying to figure out if there is a feasible way to prevent
values
> from ever spilling from registers to the stack. I've looked for code or
> documentation on how to do this but haven't found anything, apologies
if
> this has already been done.
>
> Recent security research has shown that protection schemes such as CFI
(that
> might otherwise be secure) are undermined by sensitive values spilling to
> the stack. When security-critical values spill from registers to the stack,
> they can be read and overwritten by an attacker with arbitrary memory read
> or write capabilities. See "Losing Control" from CCS 2015 for
more details
> on this sort of attack:
https://www.ics.uci.edu/~perl/ccs15_stackdefiler.pdf
>
> I think it would be great if we could allow values or at least virtual regs
> to be tagged as "security-sensitive" and disallow spilling of
these values
> across their lifetime. I expect that the best way to do this would be to
> start at the virtual register level and push support up to IR values as
well
> if and only if machine IR turns out to be insufficient.
>
> Is this a good idea? Does something to support register pinning already
> exist? I'm unfortunately not familiar enough with the register
allocators to
> know how to best support this, although I'm willing to give it a try if
> people can point me in the right direction.
I don't a real answer for you, but my 1st idea is that it would be an
attribute you could apply to a variable. How you *force* that to never
spill on the backend is an entirely different issue. You'd basically
force a split on a certain variable under certain conditions - would
it be possible - (why not) Unless I'm missing something it would be
hell to schedule though..

There's use cases in HPC and GPGPU codes which may benefit from
something similar, but for different reasons. (Some really hot
variable that you never want spilled for example)
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

There are plenty of compilers which allow you to specify that a certain
callee-save register is dedicated to holding a particular variable within a
particular function or compilation unit. GCC, for example (register int
*foo asm ("r12");), or ARM Ltd's compiler.

This doesn't prevent some other library code that you call from temporarily
saving and restoring that register.

Usually that is fine for correctness purposes (if you don't have callbacks
anyway), but it defeats your purpose.

GCC also has the -ffixed-reg command line option to prevent generated code
from using that register at all.


On Tue, Nov 3, 2015 at 2:24 AM, Stephen Crane via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi all,
>
> I've been trying to figure out if there is a feasible way to prevent
> values from ever spilling from registers to the stack. I've looked for
code
> or documentation on how to do this but haven't found anything,
apologies if
> this has already been done.
>
> Recent security research has shown that protection schemes such as CFI
> (that might otherwise be secure) are undermined by sensitive values
> spilling to the stack. When security-critical values spill from registers
> to the stack, they can be read and overwritten by an attacker with
> arbitrary memory read or write capabilities. See "Losing Control"
from CCS
> 2015 for more details on this sort of attack:
> https://www.ics.uci.edu/~perl/ccs15_stackdefiler.pdf
>
> I think it would be great if we could allow values or at least virtual
> regs to be tagged as "security-sensitive" and disallow spilling
of these
> values across their lifetime. I expect that the best way to do this would
> be to start at the virtual register level and push support up to IR values
> as well if and only if machine IR turns out to be insufficient.
>
> Is this a good idea? Does something to support register pinning already
> exist? I'm unfortunately not familiar enough with the register
allocators
> to know how to best support this, although I'm willing to give it a try
if
> people can point me in the right direction.
>
> Thanks,
> Stephen
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151103/9e5fe6ac/attachment.html>

Hi Stephen,

On 2 Nov 2015, at 23:24, Stephen Crane via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> I've been trying to figure out if there is a feasible way to prevent
values from ever spilling from registers to the stack. I've looked for code
or documentation on how to do this but haven't found anything, apologies if
this has already been done.
> 
> Recent security research has shown that protection schemes such as CFI
(that might otherwise be secure) are undermined by sensitive values spilling to
the stack. When security-critical values spill from registers to the stack, they
can be read and overwritten by an attacker with arbitrary memory read or write
capabilities. See "Losing Control" from CCS 2015 for more details on
this sort of attack: https://www.ics.uci.edu/~perl/ccs15_stackdefiler.pdf
> 
> I think it would be great if we could allow values or at least virtual regs
to be tagged as "security-sensitive" and disallow spilling of these
values across their lifetime. I expect that the best way to do this would be to
start at the virtual register level and push support up to IR values as well if
and only if machine IR turns out to be insufficient.
> 
> Is this a good idea? Does something to support register pinning already
exist? I'm unfortunately not familiar enough with the register allocators to
know how to best support this, although I'm willing to give it a try if
people can point me in the right direction.
I implemented something like this for MIPS a couple of years ago.  A few things:

- Marking variables doesn’t make sense.  You don’t know what temporaries will
exist that are derived from that variable and can allow an attacker to
materialise it.  You really want to mark functions as sensitive.

- Preventing spills does not actually buy you anything.  A lot of recent attacks
exploit signal handlers.  If you can deliver a signal in the middle of the
sensitive code then all of its registers are spilled in the ucontext.  You need
to also modify the kernel to zero this region of the stack after signal
delivery, at the very least, and also ideally use separate signal stacks with
different page table mappings.  I seem to recall that this was a possible attack
vector for your Oakland paper too, as it will allow unmasking the PC.

- Preventing spills won’t work if you’re not in a leaf function, as you don’t
know if the callee will will spill callee-save registers that you’ve put your
temporaries in.

The approach that I used made the compiler zero all spill slots in the return
path and added a warning if you called a non-sensitive function from a sensitive
function and stored zero in all temporary registers and unused argument
registers.  This is something that you can do entirely in the back end, as long
as you have a list of sensitive functions.  Other projects got in the way and I
never had time to do a proper security evaluation, but the approach seemed sane
to the cryptographers that I discussed it with.

David