VLAs and security

VLAs and security

[Uecker, Martin]

I do not agree that VLAs are generally bad for security.
I think the opposite is true. A VLA with the right size
allows the compiler to automatically perform or insert
meaningful bounds checks, while a fixed upper bound does not.


For example:

char buf[N];
buf[n] = 1;

Here, a compiler / analysis tool can for  n < N  using
static analysis or insert a run-time check.

Replacing this with

char buf[MAX_SIZE]

hides the information about the true upper bound
from automatic tools.

Limiting the stack usage can also be achieved in
the following way:

assert(N <= MAX_SIZE)
char buf[N];


Of course, having predictable stack usage might be more 
important in the kernel and might be a good argument
to still prefer the constant bound.

But loosing the tighter bounds is clearly a disadvantage
with respect to security that one should keep it mind.


Best,
Martin

Re: VLAs and security

[Kees Cook]

On Sun, Sep 2, 2018 at 1:08 AM, Uecker, Martin
<Martin.Uecker@med.uni-goettingen.de> wrote:
> I do not agree that VLAs are generally bad for security.
> I think the opposite is true. A VLA with the right size
> allows the compiler to automatically perform or insert
> meaningful bounds checks, while a fixed upper bound does not.

While I see what you mean, the trouble is that the compiler has no
idea what the upper bounds of the _available_ stack is. This means
that a large VLA might allow code to read/write beyond the stack
allocation, which also bypasses the "standard" stack buffer overflow
checks. Additionally, VLAs bypass the existing stack-size checks we've
added to the kernel.

> For example:
>
> char buf[N];
> buf[n] = 1;
>
> Here, a compiler / analysis tool can for  n < N  using
> static analysis or insert a run-time check.
>
> Replacing this with
>
> char buf[MAX_SIZE]
>
> hides the information about the true upper bound
> from automatic tools.

While this may be true for some tools, I don't agree VLAs are better
in general. For example, the compiler actually knows the upper bound
at build time now, and things like the printf format size checks and
CONFIG_FORTIFY_SOURCE are now able to produce compile-time warnings
(since "sizeof(buf)" isn't a runtime value). With a VLA, this is
hidden from those tools, and detection depends on runtime analysis.

It should be noted that VLAs are also slow[1], so removing them not
only improves robustness but also improves performance.

> Limiting the stack usage can also be achieved in
> the following way:
>
> assert(N <= MAX_SIZE)
> char buf[N];

If you look through the various VLA removals that have been landing,
there is a common pattern of performing these checks where it might be
possible for an "n" to be larger than the fixed size. (Many removals
can be compile-time checked as callers are usually just in a specific
range -- it's not really a "runtime" size that was changing, since all
callers used different but hard-coded sizes.)

char buf[N];
...
if (WARN_ON(n > N))
    return -EINVAL;
...

> Of course, having predictable stack usage might be more
> important in the kernel and might be a good argument
> to still prefer the constant bound.

Between improved compile-time checking, faster runtime performance,
and improved robustness against stack exhaustion, I strongly believe
the kernel to be better off with VLAs entirely removed. And we are
close: only 6 remain (out of the 115 I counted in v4.15).

> But loosing the tighter bounds is clearly a disadvantage
> with respect to security that one should keep it mind.

Yes: without VLAs, stack array usage is reduced to "standard" stack
buffer overflow concerns. Removing the VLA doesn't introduce a new
risk: we already had to worry about fixed-size arrays. Removing VLAs
means we don't have to worry about the VLA-specific risks anymore.

-Kees

[1] https://git.kernel.org/linus/02361bc77888

-- 
Kees Cook
Pixel Security

Re: VLAs and security

[Uecker, Martin]

Am Sonntag, den 02.09.2018, 10:40 -0700 schrieb Kees Cook:
> On Sun, Sep 2, 2018 at 1:08 AM, Uecker, Martin
> <Martin.Uecker@med.uni-goettingen.de> wrote:
> > I do not agree that VLAs are generally bad for security.
> > I think the opposite is true. A VLA with the right size
> > allows the compiler to automatically perform or insert
> > meaningful bounds checks, while a fixed upper bound does not.
> 
> While I see what you mean, the trouble is that the compiler has no
> idea what the upper bounds of the _available_ stack is. This means
> that a large VLA might allow code to read/write beyond the stack
> allocation, which also bypasses the "standard" stack buffer overflow
> checks. Additionally, VLAs bypass the existing stack-size checks we've
> added to the kernel.

Limiting the size of the VLA should be sufficient to avoid this.

I don't know about your specific stack-size checks
in the kernel, but for general programming, the full solution
is for the compiler to probe the stack when growing.

But I was not talking about the bounds of the stack, but of the
array itself.

> > For example:
> > 
> > char buf[N];
> > buf[n] = 1;
> > 
> > Here, a compiler / analysis tool can for  n < N  using
> > static analysis or insert a run-time check.
> > 
> > Replacing this with
> > 
> > char buf[MAX_SIZE]
> > 
> > hides the information about the true upper bound
> > from automatic tools.
> 
> While this may be true for some tools, I don't agree VLAs are better
> in general. For example, the compiler actually knows the upper bound
> at build time now, and things like the printf format size checks and
> CONFIG_FORTIFY_SOURCE are now able to produce compile-time warnings
> (since "sizeof(buf)" isn't a runtime value). With a VLA, this is
> hidden from those tools, and detection depends on runtime analysis.

If the correct bound is actually a constant and the array
only ends up being a VLA for some random reason, I fully agree.

But if the true bound is smaller, then IMHO it is really bad advise
to tell programmers to use

char buf[MAX_SIZE]

instead of something like

assert(N <= MAX_SIZE); 
char buf[N]

because then errors of the form 

buf[n] = 1

with N < n < MAX_SIZE can not be detected anymore. Also the
code usually ends up being less readable, which is also a clear
disadvantage in my opinion.


> It should be noted that VLAs are also slow[1], so removing them not
> only improves robustness but also improves performance.

I have to admit that I am always a bit skeptical if somebody makes
generic claims such as "VLAs are slow" and then cites only a
single example. But I am not too surprised if compilers produce
crappy code for VLAs and that this can hurt performance in some
examples. But compared to dynamic allocation VLAs should be much
faster. They also reduce stack usage compared to always allocating
array with a fixed maximum size on the stack.

> > Of course, having predictable stack usage might be more
> > important in the kernel and might be a good argument
> > to still prefer the constant bound.
> 
> Between improved compile-time checking, faster runtime performance,
> and improved robustness against stack exhaustion, I strongly believe
> the kernel to be better off with VLAs entirely removed. And we are
> close: only 6 remain (out of the 115 I counted in v4.15).

Looking at some of the patches, I would say it is not 
clear to me that this is alway an improvement.

> > But loosing the tighter bounds is clearly a disadvantage
> > with respect to security that one should keep it mind.
> 
> Yes: without VLAs, stack array usage is reduced to "standard" stack
> buffer overflow concerns. Removing the VLA doesn't introduce a new
> risk: we already had to worry about fixed-size arrays. Removing VLAsalways
> means we don't have to worry about the VLA-specific risks anymore.

It introduces the new risk that certain logic error can
not be detected anymore by static analysis or run-time bounds
checking.

Best,
Martin

Re: VLAs and security

[Linus Torvalds]

On Mon, Sep 3, 2018 at 12:40 AM Uecker, Martin
<Martin.Uecker@med.uni-goettingen.de> wrote:
>
> But if the true bound is smaller, then IMHO it is really bad advise
> to tell programmers to use
>
> char buf[MAX_SIZE]
>
> instead of something like
>
> assert(N <= MAX_SIZE);
> char buf[N]

No.

First off, we don't use asserts in the kernel. Not acceptable. You
handle errors, you don't crash.

Secondly, the compiler is usually very stupid, and will generate
horrible code for VLA's.

Third, there's no guarantee that the compiler will actually even
realize that the size is limited, and guarantee that it won't screw up
the stack.

So no. VLA's are not acceptable in the kernel. Don't do them. We're
getting rid of them.

               Linus

Re: VLAs and security

[Uecker, Martin]

Am Montag, den 03.09.2018, 14:28 -0700 schrieb Linus Torvalds:
> On Mon, Sep 3, 2018 at 12:40 AM Uecker, Martin
> <Martin.Uecker@med.uni-goettingen.de> wrote:
> > 
> > But if the true bound is smaller, then IMHO it is really bad advise
> > to tell programmers to use
> > 
> > char buf[MAX_SIZE]
> > 
> > instead of something like
> > 
> > assert(N <= MAX_SIZE);
> > char buf[N]
> 
> No.
> 
> First off, we don't use asserts in the kernel. Not acceptable. You
> handle errors, you don't crash.

Ofcourse. But this is unrelated to my point.

> Secondly, the compiler is usually very stupid, and will generate
> horrible code for VLA's.
> 
> Third, there's no guarantee that the compiler will actually even
> realize that the size is limited, and guarantee that it won't screw up
> the stack.

If this is about the quality of the generated code, ok. 

I just don't buy the idea that removing precise type-based
information about the size of objects from the source code
is good long-term strategy for improving security.

> So no. VLA's are not acceptable in the kernel. Don't do them. We're
> getting rid of them.

All right then.

Martin

Re: VLAs and security

[Dmitry Vyukov]

On Tue, Sep 4, 2018 at 8:27 AM, Uecker, Martin
<Martin.Uecker@med.uni-goettingen.de> wrote:
> Am Montag, den 03.09.2018, 14:28 -0700 schrieb Linus Torvalds:
>> On Mon, Sep 3, 2018 at 12:40 AM Uecker, Martin
>> <Martin.Uecker@med.uni-goettingen.de> wrote:
>> >
>> > But if the true bound is smaller, then IMHO it is really bad advise
>> > to tell programmers to use
>> >
>> > char buf[MAX_SIZE]
>> >
>> > instead of something like
>> >
>> > assert(N <= MAX_SIZE);
>> > char buf[N]
>>
>> No.
>>
>> First off, we don't use asserts in the kernel. Not acceptable. You
>> handle errors, you don't crash.
>
> Ofcourse. But this is unrelated to my point.
>
>> Secondly, the compiler is usually very stupid, and will generate
>> horrible code for VLA's.
>>
>> Third, there's no guarantee that the compiler will actually even
>> realize that the size is limited, and guarantee that it won't screw up
>> the stack.
>
> If this is about the quality of the generated code, ok.
>
> I just don't buy the idea that removing precise type-based
> information about the size of objects from the source code
> is good long-term strategy for improving security.
>
>> So no. VLA's are not acceptable in the kernel. Don't do them. We're
>> getting rid of them.
>
> All right then.

Hi Martin,

Compiler and KASAN should still be able to do checking against the
static array size.
If you mean that there is some smaller dynamic logical bound n (<N)
and we are not supposed to use memory beyond that, then KMSAN [1] can
detect uses of the uninitialized part of the array. So we have some
coverage on the checking side too.

[1] https://github.com/google/kmsan#kmsan-kernelmemorysanitizer

Re: VLAs and security

[Uecker, Martin]

Am Dienstag, den 04.09.2018, 10:00 +0200 schrieb Dmitry Vyukov:
> On Tue, Sep 4, 2018 at 8:27 AM, Uecker, Martin
> <Martin.Uecker@med.uni-goettingen.de> wrote:
> > Am Montag, den 03.09.2018, 14:28 -0700 schrieb Linus Torvalds:


Hi Dmitry,

> Compiler and KASAN should still be able to do checking against the
> static array size.

...and it is probably true that this is currently more useful
than the limited amount of checking compilers can do for VLAs.

> If you mean that there is some smaller dynamic logical bound n (<N)
> and we are not supposed to use memory beyond that, 

Yes, this is what I mean. 

My concern is that this dynamic bound is valuable information
which was put there by programmers by hand and I believe that
this information can not always be recovered automatically
by static analysis. So by removing VLAs from the source tree,
this information ist lost.

> then KMSAN [1] can
> detect uses of the uninitialized part of the array. So we have some
> coverage on the checking side too.
> 
> [1] https://github.com/google/kmsan#kmsan-kernelmemorysanitizer

But detecting reads of uninitialized parts can detect only some
of the errors which could be detected with precise bounds.
It can not detect out-of-bounds writes (which still fall into
the larger fixed-size array) and it does not detect out-of-bounds
reads (which still fall into the larger fixed-size array) if
the larger fixed-size array was completely initialized
before for some reason.

Martin

Re: VLAs and security

[Dmitry Vyukov]

On Tue, Sep 4, 2018 at 8:22 PM, Uecker, Martin
<Martin.Uecker@med.uni-goettingen.de> wrote:
> Am Dienstag, den 04.09.2018, 10:00 +0200 schrieb Dmitry Vyukov:
>> On Tue, Sep 4, 2018 at 8:27 AM, Uecker, Martin
>> <Martin.Uecker@med.uni-goettingen.de> wrote:
>> > Am Montag, den 03.09.2018, 14:28 -0700 schrieb Linus Torvalds:
>
>
> Hi Dmitry,
>
>> Compiler and KASAN should still be able to do checking against the
>> static array size.
>
> ...and it is probably true that this is currently more useful
> than the limited amount of checking compilers can do for VLAs.
>
>> If you mean that there is some smaller dynamic logical bound n (<N)
>> and we are not supposed to use memory beyond that,
>
> Yes, this is what I mean.
>
> My concern is that this dynamic bound is valuable information
> which was put there by programmers by hand and I believe that
> this information can not always be recovered automatically
> by static analysis. So by removing VLAs from the source tree,
> this information ist lost.
>
>> then KMSAN [1] can
>> detect uses of the uninitialized part of the array. So we have some
>> coverage on the checking side too.
>>
>> [1] https://github.com/google/kmsan#kmsan-kernelmemorysanitizer
>
> But detecting reads of uninitialized parts can detect only some
> of the errors which could be detected with precise bounds.
> It can not detect out-of-bounds writes (which still fall into
> the larger fixed-size array) and it does not detect out-of-bounds
> reads (which still fall into the larger fixed-size array) if
> the larger fixed-size array was completely initialized
> before for some reason.

Well, I agree maybe it harms checking ability to some degree. But it's
always tradeoffs all way down. And in the end nothing can safe from
logical bugs (well, except for unit tests). With VLA one give a right
bound but the use wrong bytes in the buffer, or simply give a wrong
bound.