Stack overflow protection/detection

[Johannes Schlatow]

Hi all,

I guess you are familiar with the problem of stack overflows in multi-threaded
components. I already encountered a bunch of weird errors that were hard to
track down until I remembered that it could simply be caused by a too small stack.

I know that Genode's policy is to use single-threaded components. Occasionally,
however, one needs additional threads, especially when using 3rd party
libraries.

Stack overflows are not only very annoying and time consuming but can (imo) also be
mitigated rather easily. I therefore think it would be worth implementing
a protection or detection mechanism for this in Genode.

The "problem" here is actually the `Stack_allocator` which places the stacks of
the component threads consecutively in memory. I.e. if one thread exceeds its
allocated stack area, it likely corrupts the stack of another thread (of the
same component).

Hence, one could improve the `Stack_allocator` so that it keeps a guard page
between the stacks in order to cause a page fault on any stack overflow. This
comes at the cost of a slightly increased complexity and possibly also an
increased memory consumption (because it requires a second-level translation
table).

Alternatively, I can imagine a kernel-level (base-hw) approach which uses
canaries at the top of each stack. Every time the kernel switches to a user
thread, it checks whether the canary is still alive. If not, another thread's
stack must have overflowed. Of course, this method is only reliable if we can
assume that every memory word on the stack will be initialised (preferably
sequentially).

Note that I'm not eager to implement these techniques in the near future.
Nevertheless, I thought it would be great to start a discussion and collect
comments and additional ideas.

Looking forward to your feedback!

Cheers
Johannes

------------------------------------------------------------------------------

[Norman Feske]

Hi Johannes,

I'm afraid that you misinterpreted the role of the "stack allocator".
Stacks are actually not allocated consecutively but within a sparsely
populated area (called stack area) within the component's virtual memory
space.

We introduced the current stack allocation scheme back in Genode 10.02:


http://genode.org/documentation/release-notes/10.02#New_thread-context_management

In short, the stack allocator is used to allocate slots within the stack
area, that hosts all the stacks. Each slot is 1 MiB of virtual memory,
aligned to a 1 MiB boundary. The actual stack (typically just a few KiB)
is placed within the slot but most of the slot remains unpopulated.
Consequently, guard pages are already in place - plenty of them.

The only thing that changed since 10.02 is the naming. I removed the
notion of the "thread context area" earlier this year and just speak of
"stack area" instead. This was done to simplify the terminology used
within the framework's implementation.

Post by Johannes Schlatow
Stack overflows are not only very annoying and time consuming but can (imo) also be
mitigated rather easily. I therefore think it would be worth implementing
a protection or detection mechanism for this in Genode.

Usually, when a stack overflows, you get a message indicating that an
unresolvable page fault has occurred with the virtual-memory range of
the stack area. On base-linux, the address can be found in the dmesg
output. On the other kernels, core's pager prints a message (mostly
accompanied with something like "invalid signal-context capability").

I doubt that stack corruptions were the reason for the trouble you
observed. I can vividly remember nerve-wracking bug hunting sessions
prior version 10.02 that were caused by stack overflows corrupting
adjacent memory, but this hasn't been an issue since then.

Post by Johannes Schlatow
Alternatively, I can imagine a kernel-level (base-hw) approach which uses
canaries at the top of each stack. Every time the kernel switches to a user
thread, it checks whether the canary is still alive. If not, another thread's
stack must have overflowed. Of course, this method is only reliable if we can
assume that every memory word on the stack will be initialised (preferably
sequentially).

Stack canaries are actually a good idea, which we will investigate in
the near future - but not to counter stack overflows but as a protection
measure against deliberate stack-smashing attacks.

Cheers
Norman
--
Dr.-Ing. Norman Feske
Genode Labs

http://www.genode-labs.com · http://genode.org

Genode Labs GmbH · Amtsgericht Dresden · HRB 28424 · Sitz Dresden
Geschäftsführer: Dr.-Ing. Norman Feske, Christian Helmuth

------------------------------------------------------------------------------

[Johannes Schlatow]

Norman, thanks a lot for the clarification!

I must admit that I only had a rather brief look at the existing code.

You explanation still leaves me puzzled with one little question though:
Where does the "invalid signal-context capability" come from? I
actually noticed that a couple of times in the past and was wondering
what's causing this.

On Tue, 30 Aug 2016 20:53:34 +0200

Post by Norman Feske
Hi Johannes,
I'm afraid that you misinterpreted the role of the "stack allocator".
Stacks are actually not allocated consecutively but within a sparsely
populated area (called stack area) within the component's virtual
memory space.
http://genode.org/documentation/release-notes/10.02#New_thread-context_management
In short, the stack allocator is used to allocate slots within the
stack area, that hosts all the stacks. Each slot is 1 MiB of virtual
memory, aligned to a 1 MiB boundary. The actual stack (typically just
a few KiB) is placed within the slot but most of the slot remains
unpopulated. Consequently, guard pages are already in place - plenty
of them.
The only thing that changed since 10.02 is the naming. I removed the
notion of the "thread context area" earlier this year and just speak
of "stack area" instead. This was done to simplify the terminology
used within the framework's implementation.

Post by Johannes Schlatow
Stack overflows are not only very annoying and time consuming but
can (imo) also be mitigated rather easily. I therefore think it
would be worth implementing a protection or detection mechanism for
this in Genode.

Usually, when a stack overflows, you get a message indicating that an
unresolvable page fault has occurred with the virtual-memory range of
the stack area. On base-linux, the address can be found in the dmesg
output. On the other kernels, core's pager prints a message (mostly
accompanied with something like "invalid signal-context capability").
I doubt that stack corruptions were the reason for the trouble you
observed. I can vividly remember nerve-wracking bug hunting sessions
prior version 10.02 that were caused by stack overflows corrupting
adjacent memory, but this hasn't been an issue since then.

Post by Johannes Schlatow
Alternatively, I can imagine a kernel-level (base-hw) approach
which uses canaries at the top of each stack. Every time the kernel
switches to a user thread, it checks whether the canary is still
alive. If not, another thread's stack must have overflowed. Of
course, this method is only reliable if we can assume that every
memory word on the stack will be initialised (preferably
sequentially).

Stack canaries are actually a good idea, which we will investigate in
the near future - but not to counter stack overflows but as a
protection measure against deliberate stack-smashing attacks.
Cheers
Norman

------------------------------------------------------------------------------

[Stefan Kalkowski]

Hi Johannes,

Post by Johannes Schlatow
Norman, thanks a lot for the clarification!
I must admit that I only had a rather brief look at the existing code.
Where does the "invalid signal-context capability" come from? I
actually noticed that a couple of times in the past and was wondering
what's causing this.

"invalid signal-context capability" is printed when someone used an
invalid capability (e.g., not set signal handler) to submit a signal. It
can be printed for many reasons. Typically you can see it when a fault
in the thread context area cannot be resolved.

I was wondering: which kernel are you using right now? Because I also
stumbled across the problem that on top of certain kernels (e.g., Fiasco
old, Pistachio, SeL4...) we do not print an error message when a
page-fault cannot be resolved within a managed region-map area (e.g.,
within the thread context area). I will open an issue for this on github.

Regards
Stefan

Post by Johannes Schlatow
On Tue, 30 Aug 2016 20:53:34 +0200

Post by Norman Feske
Hi Johannes,
I'm afraid that you misinterpreted the role of the "stack allocator".
Stacks are actually not allocated consecutively but within a sparsely
populated area (called stack area) within the component's virtual
memory space.
http://genode.org/documentation/release-notes/10.02#New_thread-context_management
In short, the stack allocator is used to allocate slots within the
stack area, that hosts all the stacks. Each slot is 1 MiB of virtual
memory, aligned to a 1 MiB boundary. The actual stack (typically just
a few KiB) is placed within the slot but most of the slot remains
unpopulated. Consequently, guard pages are already in place - plenty
of them.
The only thing that changed since 10.02 is the naming. I removed the
notion of the "thread context area" earlier this year and just speak
of "stack area" instead. This was done to simplify the terminology
used within the framework's implementation.

Post by Johannes Schlatow
Stack overflows are not only very annoying and time consuming but
can (imo) also be mitigated rather easily. I therefore think it
would be worth implementing a protection or detection mechanism for
this in Genode.

Usually, when a stack overflows, you get a message indicating that an
unresolvable page fault has occurred with the virtual-memory range of
the stack area. On base-linux, the address can be found in the dmesg
output. On the other kernels, core's pager prints a message (mostly
accompanied with something like "invalid signal-context capability").
I doubt that stack corruptions were the reason for the trouble you
observed. I can vividly remember nerve-wracking bug hunting sessions
prior version 10.02 that were caused by stack overflows corrupting
adjacent memory, but this hasn't been an issue since then.

Post by Johannes Schlatow
Alternatively, I can imagine a kernel-level (base-hw) approach
which uses canaries at the top of each stack. Every time the kernel
switches to a user thread, it checks whether the canary is still
alive. If not, another thread's stack must have overflowed. Of
course, this method is only reliable if we can assume that every
memory word on the stack will be initialised (preferably
sequentially).

Stack canaries are actually a good idea, which we will investigate in
the near future - but not to counter stack overflows but as a
protection measure against deliberate stack-smashing attacks.
Cheers
Norman

------------------------------------------------------------------------------
_______________________________________________
genode-main mailing list
https://lists.sourceforge.net/lists/listinfo/genode-main

[Johannes Schlatow]

Hi Stefan,

unfortunately, I cannot reproduce the problem as it was some time ago and I don't remember the exact situation.

On Wed, 31 Aug 2016 13:15:44 +0200

Post by Norman Feske
Hi Johannes,

Post by Johannes Schlatow
Norman, thanks a lot for the clarification!
I must admit that I only had a rather brief look at the existing code.
Where does the "invalid signal-context capability" come from? I
actually noticed that a couple of times in the past and was wondering
what's causing this.

"invalid signal-context capability" is printed when someone used an
invalid capability (e.g., not set signal handler) to submit a signal. It
can be printed for many reasons. Typically you can see it when a fault
in the thread context area cannot be resolved.
I was wondering: which kernel are you using right now? Because I also
stumbled across the problem that on top of certain kernels (e.g., Fiasco
old, Pistachio, SeL4...) we do not print an error message when a
page-fault cannot be resolved within a managed region-map area (e.g.,
within the thread context area). I will open an issue for this on github.
Regards
Stefan

Post by Johannes Schlatow
On Tue, 30 Aug 2016 20:53:34 +0200

Post by Norman Feske
Hi Johannes,
I'm afraid that you misinterpreted the role of the "stack allocator".
Stacks are actually not allocated consecutively but within a sparsely
populated area (called stack area) within the component's virtual
memory space.
http://genode.org/documentation/release-notes/10.02#New_thread-context_management
In short, the stack allocator is used to allocate slots within the
stack area, that hosts all the stacks. Each slot is 1 MiB of virtual
memory, aligned to a 1 MiB boundary. The actual stack (typically just
a few KiB) is placed within the slot but most of the slot remains
unpopulated. Consequently, guard pages are already in place - plenty
of them.
The only thing that changed since 10.02 is the naming. I removed the
notion of the "thread context area" earlier this year and just speak
of "stack area" instead. This was done to simplify the terminology
used within the framework's implementation.

Post by Johannes Schlatow
Stack overflows are not only very annoying and time consuming but
can (imo) also be mitigated rather easily. I therefore think it
would be worth implementing a protection or detection mechanism for
this in Genode.

Usually, when a stack overflows, you get a message indicating that an
unresolvable page fault has occurred with the virtual-memory range of
the stack area. On base-linux, the address can be found in the dmesg
output. On the other kernels, core's pager prints a message (mostly
accompanied with something like "invalid signal-context capability").
I doubt that stack corruptions were the reason for the trouble you
observed. I can vividly remember nerve-wracking bug hunting sessions
prior version 10.02 that were caused by stack overflows corrupting
adjacent memory, but this hasn't been an issue since then.

Post by Johannes Schlatow
Alternatively, I can imagine a kernel-level (base-hw) approach
which uses canaries at the top of each stack. Every time the kernel
switches to a user thread, it checks whether the canary is still
alive. If not, another thread's stack must have overflowed. Of
course, this method is only reliable if we can assume that every
memory word on the stack will be initialised (preferably
sequentially).

Stack canaries are actually a good idea, which we will investigate in
the near future - but not to counter stack overflows but as a
protection measure against deliberate stack-smashing attacks.
Cheers
Norman

------------------------------------------------------------------------------
_______________________________________________
genode-main mailing list
https://lists.sourceforge.net/lists/listinfo/genode-main

--
Johannes Schlatow, M.Sc.

IDA, Institute of Computer and Network Engineering
Technische Universität Braunschweig
Hans-Sommer-Str. 66
38106 Braunschweig - Germany

Phone [phone] - 9668

www.ida.ing.tu-bs.de
***@ida.ing.tu-bs.de

------------------------------------------------------------------------------