Making KASAN compatible with VMAP_STACK

Making KASAN compatible with VMAP_STACK

[Andy Lutomirski]

Hi all-

It would be really nice to make KASAN compatible with VMAP_STACK.
Both are valuable memory debugging features, and the fact that you
can't use both is disappointing.

As far as I know, there are only two problems:

1. The KASAN shadow population code is a mess, and adding *anything*
to the KASAN shadow requires magical, fragile incantations.  It should
be cleaned up so that ranges can be easily populated without needing
to very carefully align things, call helpers in the right order, etc.
The core KASAN code should figure it out by itself.

2. The vmalloc area is potentially extremely large.  It might be
necessary to have a way to *depopulate* shadow space when stacks get
freed or, more generally, when vmap areas are freed.  Ideally KASAN
would integrate with the core vmalloc/vmap code and it would Just Work
(tm).  And, as a bonus, we'd get proper KASAN protection of vmalloced
memory.

Any volunteers to fix this?

--Andy

Re: Making KASAN compatible with VMAP_STACK

[Dmitry Vyukov]

On Sun, Jul 22, 2018 at 7:52 PM, Andy Lutomirski <luto@kernel.org> wrote:
> Hi all-
>
> It would be really nice to make KASAN compatible with VMAP_STACK.
> Both are valuable memory debugging features, and the fact that you
> can't use both is disappointing.
>
> As far as I know, there are only two problems:
>
> 1. The KASAN shadow population code is a mess, and adding *anything*
> to the KASAN shadow requires magical, fragile incantations.  It should
> be cleaned up so that ranges can be easily populated without needing
> to very carefully align things, call helpers in the right order, etc.
> The core KASAN code should figure it out by itself.
>
> 2. The vmalloc area is potentially extremely large.  It might be
> necessary to have a way to *depopulate* shadow space when stacks get
> freed or, more generally, when vmap areas are freed.  Ideally KASAN
> would integrate with the core vmalloc/vmap code and it would Just Work
> (tm).  And, as a bonus, we'd get proper KASAN protection of vmalloced
> memory.
>
> Any volunteers to fix this?

Hi Andy,

I understand that having most configs as orthogonal settings that can
be enabled independently is generally good in intself, but I would
like to understand what does VMAP_STACK add on top of KASAN in terms
of debugging capabilities?

Re: Making KASAN compatible with VMAP_STACK

[Mark Rutland]

On Mon, Jul 23, 2018 at 09:40:36AM +0200, Dmitry Vyukov wrote:
> On Sun, Jul 22, 2018 at 7:52 PM, Andy Lutomirski <luto@kernel.org> wrote:
> > Hi all-
> >
> > It would be really nice to make KASAN compatible with VMAP_STACK.
> > Both are valuable memory debugging features, and the fact that you
> > can't use both is disappointing.
> >
> > As far as I know, there are only two problems:
> >
> > 1. The KASAN shadow population code is a mess, and adding *anything*
> > to the KASAN shadow requires magical, fragile incantations.  It should
> > be cleaned up so that ranges can be easily populated without needing
> > to very carefully align things, call helpers in the right order, etc.
> > The core KASAN code should figure it out by itself.
> >
> > 2. The vmalloc area is potentially extremely large.  It might be
> > necessary to have a way to *depopulate* shadow space when stacks get
> > freed or, more generally, when vmap areas are freed.  Ideally KASAN
> > would integrate with the core vmalloc/vmap code and it would Just Work
> > (tm).  And, as a bonus, we'd get proper KASAN protection of vmalloced
> > memory.
> >
> > Any volunteers to fix this?
> 
> Hi Andy,
> 
> I understand that having most configs as orthogonal settings that can
> be enabled independently is generally good in intself, but I would
> like to understand what does VMAP_STACK add on top of KASAN in terms
> of debugging capabilities?

VMAP_STACK makes it possible to detect stack overflows reliably at the
point of overflow.

KASAN can't handle this reliably, even if it detects that an access is
out of the stack bounds, since handling this requires stack space.
Depending on a number of factors, this may be reported, might result in
recursive exceptions, etc.

I assume we must populate shadow  for vmalloc regions today, but I guess
that just shares the zero shadow?

Thanks,
Mark.

Re: Making KASAN compatible with VMAP_STACK

[Dmitry Vyukov]

On Mon, Jul 23, 2018 at 1:18 PM, Mark Rutland <mark.rutland@arm.com> wrote:
> On Mon, Jul 23, 2018 at 09:40:36AM +0200, Dmitry Vyukov wrote:
>> On Sun, Jul 22, 2018 at 7:52 PM, Andy Lutomirski <luto@kernel.org> wrote:
>> > Hi all-
>> >
>> > It would be really nice to make KASAN compatible with VMAP_STACK.
>> > Both are valuable memory debugging features, and the fact that you
>> > can't use both is disappointing.
>> >
>> > As far as I know, there are only two problems:
>> >
>> > 1. The KASAN shadow population code is a mess, and adding *anything*
>> > to the KASAN shadow requires magical, fragile incantations.  It should
>> > be cleaned up so that ranges can be easily populated without needing
>> > to very carefully align things, call helpers in the right order, etc.
>> > The core KASAN code should figure it out by itself.
>> >
>> > 2. The vmalloc area is potentially extremely large.  It might be
>> > necessary to have a way to *depopulate* shadow space when stacks get
>> > freed or, more generally, when vmap areas are freed.  Ideally KASAN
>> > would integrate with the core vmalloc/vmap code and it would Just Work
>> > (tm).  And, as a bonus, we'd get proper KASAN protection of vmalloced
>> > memory.
>> >
>> > Any volunteers to fix this?
>>
>> Hi Andy,
>>
>> I understand that having most configs as orthogonal settings that can
>> be enabled independently is generally good in intself, but I would
>> like to understand what does VMAP_STACK add on top of KASAN in terms
>> of debugging capabilities?
>
> VMAP_STACK makes it possible to detect stack overflows reliably at the
> point of overflow.
>
> KASAN can't handle this reliably, even if it detects that an access is
> out of the stack bounds, since handling this requires stack space.
> Depending on a number of factors, this may be reported, might result in
> recursive exceptions, etc.

Interesting. Does VMAP_STACK detect task_struct smashing today? As far
as I remember, the first version didn't.
As an orthogonal measure we could add KASAN redzone between stack and
task_struct, and make KASAN instrumentation detect when the new frame
hits this redzone. We bump stack order under KASAN significantly, so
adding, say 128 byte redzone should not be a problem. Does it make any
sense?

Re: Making KASAN compatible with VMAP_STACK

[Mark Rutland]

On Mon, Jul 23, 2018 at 01:55:49PM +0200, Dmitry Vyukov wrote:
> On Mon, Jul 23, 2018 at 1:18 PM, Mark Rutland <mark.rutland@arm.com> wrote:
> > On Mon, Jul 23, 2018 at 09:40:36AM +0200, Dmitry Vyukov wrote:
> >> On Sun, Jul 22, 2018 at 7:52 PM, Andy Lutomirski <luto@kernel.org> wrote:
> >> > Hi all-
> >> >
> >> > It would be really nice to make KASAN compatible with VMAP_STACK.
> >> > Both are valuable memory debugging features, and the fact that you
> >> > can't use both is disappointing.
> >> >
> >> > As far as I know, there are only two problems:
> >> >
> >> > 1. The KASAN shadow population code is a mess, and adding *anything*
> >> > to the KASAN shadow requires magical, fragile incantations.  It should
> >> > be cleaned up so that ranges can be easily populated without needing
> >> > to very carefully align things, call helpers in the right order, etc.
> >> > The core KASAN code should figure it out by itself.
> >> >
> >> > 2. The vmalloc area is potentially extremely large.  It might be
> >> > necessary to have a way to *depopulate* shadow space when stacks get
> >> > freed or, more generally, when vmap areas are freed.  Ideally KASAN
> >> > would integrate with the core vmalloc/vmap code and it would Just Work
> >> > (tm).  And, as a bonus, we'd get proper KASAN protection of vmalloced
> >> > memory.
> >> >
> >> > Any volunteers to fix this?
> >>
> >> Hi Andy,
> >>
> >> I understand that having most configs as orthogonal settings that can
> >> be enabled independently is generally good in intself, but I would
> >> like to understand what does VMAP_STACK add on top of KASAN in terms
> >> of debugging capabilities?
> >
> > VMAP_STACK makes it possible to detect stack overflows reliably at the
> > point of overflow.
> >
> > KASAN can't handle this reliably, even if it detects that an access is
> > out of the stack bounds, since handling this requires stack space.
> > Depending on a number of factors, this may be reported, might result in
> > recursive exceptions, etc.
> 
> Interesting. Does VMAP_STACK detect task_struct smashing today? As far
> as I remember, the first version didn't.

I assume you mean thread_info? Both arm64 and x86 moved the thread_info
out of the stack region by moving it into task_struct, which has always
been allocated separately. So thread_info smashing by stack overflow is
not possible.

Regardless of VMAP_STACK, the stack region is purely stack on arm64 and
x86.

> As an orthogonal measure we could add KASAN redzone between stack and
> task_struct, and make KASAN instrumentation detect when the new frame
> hits this redzone. We bump stack order under KASAN significantly, so
> adding, say 128 byte redzone should not be a problem. Does it make any
> sense?

I don't think this is necessary since the two are allocated separately.

Thanks,
Mark.

Re: Making KASAN compatible with VMAP_STACK

[Dmitry Vyukov]

On Mon, Jul 23, 2018 at 2:42 PM, Mark Rutland <mark.rutland@arm.com> wrote:
>> >> > Hi all-
>> >> >
>> >> > It would be really nice to make KASAN compatible with VMAP_STACK.
>> >> > Both are valuable memory debugging features, and the fact that you
>> >> > can't use both is disappointing.
>> >> >
>> >> > As far as I know, there are only two problems:
>> >> >
>> >> > 1. The KASAN shadow population code is a mess, and adding *anything*
>> >> > to the KASAN shadow requires magical, fragile incantations.  It should
>> >> > be cleaned up so that ranges can be easily populated without needing
>> >> > to very carefully align things, call helpers in the right order, etc.
>> >> > The core KASAN code should figure it out by itself.
>> >> >
>> >> > 2. The vmalloc area is potentially extremely large.  It might be
>> >> > necessary to have a way to *depopulate* shadow space when stacks get
>> >> > freed or, more generally, when vmap areas are freed.  Ideally KASAN
>> >> > would integrate with the core vmalloc/vmap code and it would Just Work
>> >> > (tm).  And, as a bonus, we'd get proper KASAN protection of vmalloced
>> >> > memory.
>> >> >
>> >> > Any volunteers to fix this?
>> >>
>> >> Hi Andy,
>> >>
>> >> I understand that having most configs as orthogonal settings that can
>> >> be enabled independently is generally good in intself, but I would
>> >> like to understand what does VMAP_STACK add on top of KASAN in terms
>> >> of debugging capabilities?
>> >
>> > VMAP_STACK makes it possible to detect stack overflows reliably at the
>> > point of overflow.
>> >
>> > KASAN can't handle this reliably, even if it detects that an access is
>> > out of the stack bounds, since handling this requires stack space.
>> > Depending on a number of factors, this may be reported, might result in
>> > recursive exceptions, etc.
>>
>> Interesting. Does VMAP_STACK detect task_struct smashing today? As far
>> as I remember, the first version didn't.
>
> I assume you mean thread_info? Both arm64 and x86 moved the thread_info
> out of the stack region by moving it into task_struct, which has always
> been allocated separately. So thread_info smashing by stack overflow is
> not possible.
>
> Regardless of VMAP_STACK, the stack region is purely stack on arm64 and
> x86.
>
>> As an orthogonal measure we could add KASAN redzone between stack and
>> task_struct, and make KASAN instrumentation detect when the new frame
>> hits this redzone. We bump stack order under KASAN significantly, so
>> adding, say 128 byte redzone should not be a problem. Does it make any
>> sense?
>
> I don't think this is necessary since the two are allocated separately.


I see. Thanks.

So current KASAN failure mode would be silently smashing whatever page
happens to be after the stack. If so, I guess combining it with
VMAP_STACK would be useful, in particular, to prevent random assorted
crashes coming out of syzbot.

But I think I am not well qualified to actually do this.

Re: Making KASAN compatible with VMAP_STACK

[Dmitry Vyukov]

On Mon, Jul 23, 2018 at 2:51 PM Dmitry Vyukov <dvyukov@google.com> wrote:
>
> On Mon, Jul 23, 2018 at 2:42 PM, Mark Rutland <mark.rutland@arm.com> wrote:
> >> >> > Hi all-
> >> >> >
> >> >> > It would be really nice to make KASAN compatible with VMAP_STACK.
> >> >> > Both are valuable memory debugging features, and the fact that you
> >> >> > can't use both is disappointing.
> >> >> >
> >> >> > As far as I know, there are only two problems:
> >> >> >
> >> >> > 1. The KASAN shadow population code is a mess, and adding *anything*
> >> >> > to the KASAN shadow requires magical, fragile incantations.  It should
> >> >> > be cleaned up so that ranges can be easily populated without needing
> >> >> > to very carefully align things, call helpers in the right order, etc.
> >> >> > The core KASAN code should figure it out by itself.
> >> >> >
> >> >> > 2. The vmalloc area is potentially extremely large.  It might be
> >> >> > necessary to have a way to *depopulate* shadow space when stacks get
> >> >> > freed or, more generally, when vmap areas are freed.  Ideally KASAN
> >> >> > would integrate with the core vmalloc/vmap code and it would Just Work
> >> >> > (tm).  And, as a bonus, we'd get proper KASAN protection of vmalloced
> >> >> > memory.
> >> >> >
> >> >> > Any volunteers to fix this?
> >> >>
> >> >> Hi Andy,
> >> >>
> >> >> I understand that having most configs as orthogonal settings that can
> >> >> be enabled independently is generally good in intself, but I would
> >> >> like to understand what does VMAP_STACK add on top of KASAN in terms
> >> >> of debugging capabilities?
> >> >
> >> > VMAP_STACK makes it possible to detect stack overflows reliably at the
> >> > point of overflow.
> >> >
> >> > KASAN can't handle this reliably, even if it detects that an access is
> >> > out of the stack bounds, since handling this requires stack space.
> >> > Depending on a number of factors, this may be reported, might result in
> >> > recursive exceptions, etc.
> >>
> >> Interesting. Does VMAP_STACK detect task_struct smashing today? As far
> >> as I remember, the first version didn't.
> >
> > I assume you mean thread_info? Both arm64 and x86 moved the thread_info
> > out of the stack region by moving it into task_struct, which has always
> > been allocated separately. So thread_info smashing by stack overflow is
> > not possible.
> >
> > Regardless of VMAP_STACK, the stack region is purely stack on arm64 and
> > x86.
> >
> >> As an orthogonal measure we could add KASAN redzone between stack and
> >> task_struct, and make KASAN instrumentation detect when the new frame
> >> hits this redzone. We bump stack order under KASAN significantly, so
> >> adding, say 128 byte redzone should not be a problem. Does it make any
> >> sense?
> >
> > I don't think this is necessary since the two are allocated separately.
>
>
> I see. Thanks.
>
> So current KASAN failure mode would be silently smashing whatever page
> happens to be after the stack. If so, I guess combining it with
> VMAP_STACK would be useful, in particular, to prevent random assorted
> crashes coming out of syzbot.
>
> But I think I am not well qualified to actually do this.

A stack overflow just fired in:
https://groups.google.com/forum/#!topic/syzkaller-bugs/HoRZMT92WKk
on incoming network packet parsing (!). Was detected as some "innocent
WARNING" in rcu subsystem.

I filed https://bugzilla.kernel.org/show_bug.cgi?id=202009 to track
KASAN+VMAP_STACK.