Nanokernel stack border protection


Tidy(ChunHua) Jiang <tidyjiang@...>
 

Hi All,

The nanokernel uses an array as stack memory space, but there is no border protection when push data to the stack. When the array is already full, it will cause array overfow, leading to unpredictable behavior.

Why not add the border protection? When the array is full, it returns an error code to user.

Is it necessary ?

Thanks.


tidyjiang(a)163.com


Boie, Andrew P
 

On Sat, 2016-09-24 at 14:39 +0800, tidyjiang(a)163.com wrote:
Hi All,

The nanokernel uses an array as stack memory space, but there is no
border protection when push data to the stack. When the array is
already full,  it will cause array overfow, leading to unpredictable
behavior. 

Why not add the border protection? When the array is full, it returns
an error code to user. 

Is it necessary ?
How would you propose to implement such a border protection?

Andrew


Tidy(ChunHua) Jiang <tidyjiang@...>
 

Hi Andrew,

Yeah, we can't really implement such function in fact, but we can and just return an error code to user. I think it's better than now.


Thx & Rgds.
Tidy.

At 2016-09-25 18:08:33, "Boie, Andrew P" <andrew.p.boie(a)intel.com> wrote:
On Sat, 2016-09-24 at 14:39 +0800, tidyjiang(a)163.com wrote:
Hi All,

The nanokernel uses an array as stack memory space, but there is no
border protection when push data to the stack. When the array is
already full, it will cause array overfow, leading to unpredictable
behavior.

Why not add the border protection? When the array is full, it returns
an error code to user.

Is it necessary ?
How would you propose to implement such a border protection?

Andrew


Jon Medhurst (Tixy) <tixy@...>
 

On Sun, 2016-09-25 at 10:08 +0000, Boie, Andrew P wrote:
On Sat, 2016-09-24 at 14:39 +0800, tidyjiang(a)163.com wrote:
Hi All,

The nanokernel uses an array as stack memory space, but there is no
border protection when push data to the stack. When the array is
already full, it will cause array overfow, leading to unpredictable
behavior.

Why not add the border protection? When the array is full, it returns
an error code to user.

Is it necessary ?
How would you propose to implement such a border protection?
Use the features provided by the CPU? On ARM Cortex-M, the stack limit
registers PSPLIM and MSPLIM. Presumably other CPUs have similar things.

--
Tixy


D'alton, Alexandre <alexandre.dalton@...>
 

Hi,

FIY, ARC has this implemented (see CONFIG_ARC_STACK_CHECKING)
And it is more than useful !

Regards,
Alex.

-----Original Message-----
From: Jon Medhurst (Tixy) [mailto:tixy(a)linaro.org]
Sent: Monday, September 26, 2016 11:01 AM
To: devel(a)lists.zephyrproject.org
Subject: [devel] Re: Re: Nanokernel stack border protection

On Sun, 2016-09-25 at 10:08 +0000, Boie, Andrew P wrote:
On Sat, 2016-09-24 at 14:39 +0800, tidyjiang(a)163.com wrote:
Hi All,

The nanokernel uses an array as stack memory space, but there is no
border protection when push data to the stack. When the array is
already full, it will cause array overfow, leading to unpredictable
behavior.

Why not add the border protection? When the array is full, it
returns an error code to user.

Is it necessary ?
How would you propose to implement such a border protection?
Use the features provided by the CPU? On ARM Cortex-M, the stack limit
registers PSPLIM and MSPLIM. Presumably other CPUs have similar things.

--
Tixy
---------------------------------------------------------------------
Intel Corporation SAS (French simplified joint stock company)
Registered headquarters: "Les Montalets"- 2, rue de Paris,
92196 Meudon Cedex, France
Registration Number: 302 456 199 R.C.S. NANTERRE
Capital: 4,572,000 Euros

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.


Tidy(ChunHua) Jiang <tidyjiang@...>
 

Un...
I mean the nanokernel’s stack object type, not the system's stack.
Refer https://www.zephyrproject.org/doc/1.5.0/kernel/nanokernel/nanokernel_stacks.html

At 2016-09-26 17:14:52, "D'alton, Alexandre" <alexandre.dalton(a)intel.com> wrote:
Hi,

FIY, ARC has this implemented (see CONFIG_ARC_STACK_CHECKING)
And it is more than useful !

Regards,
Alex.

-----Original Message-----
From: Jon Medhurst (Tixy) [mailto:tixy(a)linaro.org]
Sent: Monday, September 26, 2016 11:01 AM
To: devel(a)lists.zephyrproject.org
Subject: [devel] Re: Re: Nanokernel stack border protection

On Sun, 2016-09-25 at 10:08 +0000, Boie, Andrew P wrote:
On Sat, 2016-09-24 at 14:39 +0800, tidyjiang(a)163.com wrote:
Hi All,

The nanokernel uses an array as stack memory space, but there is no
border protection when push data to the stack. When the array is
already full, it will cause array overfow, leading to unpredictable
behavior.

Why not add the border protection? When the array is full, it
returns an error code to user.

Is it necessary ?
How would you propose to implement such a border protection?
Use the features provided by the CPU? On ARM Cortex-M, the stack limit
registers PSPLIM and MSPLIM. Presumably other CPUs have similar things.

--
Tixy
---------------------------------------------------------------------
Intel Corporation SAS (French simplified joint stock company)
Registered headquarters: "Les Montalets"- 2, rue de Paris,
92196 Meudon Cedex, France
Registration Number: 302 456 199 R.C.S. NANTERRE
Capital: 4,572,000 Euros

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.


Benjamin Walsh <benjamin.walsh@...>
 

On Mon, Sep 26, 2016 at 05:34:55PM +0800, Tidy(ChunHua) Jiang wrote:
Un...
I mean the nanokernel’s stack object type, not the system's stack.
"stack" is such an overloaded term. :-)

FYI, the unified kernel version k_stack_push() has an __ASSERT() that
checks the limit.

The approach we are taking for kernel APIs is: if it's a user error, use
an __ASSERT(); otherwise, return an error code.

Pushing more than the limit on a stack object is considered a user
error.

Refer https://www.zephyrproject.org/doc/1.5.0/kernel/nanokernel/nanokernel_stacks.html

At 2016-09-26 17:14:52, "D'alton, Alexandre" <alexandre.dalton(a)intel.com> wrote:
Hi,

FIY, ARC has this implemented (see CONFIG_ARC_STACK_CHECKING)
And it is more than useful !

Regards,
Alex.

-----Original Message-----
From: Jon Medhurst (Tixy) [mailto:tixy(a)linaro.org]
Sent: Monday, September 26, 2016 11:01 AM
To: devel(a)lists.zephyrproject.org
Subject: [devel] Re: Re: Nanokernel stack border protection

On Sun, 2016-09-25 at 10:08 +0000, Boie, Andrew P wrote:
On Sat, 2016-09-24 at 14:39 +0800, tidyjiang(a)163.com wrote:
Hi All,

The nanokernel uses an array as stack memory space, but there is no
border protection when push data to the stack. When the array is
already full, it will cause array overfow, leading to unpredictable
behavior.

Why not add the border protection? When the array is full, it
returns an error code to user.

Is it necessary ?
How would you propose to implement such a border protection?
Use the features provided by the CPU? On ARM Cortex-M, the stack limit
registers PSPLIM and MSPLIM. Presumably other CPUs have similar things.

--
Tixy
---------------------------------------------------------------------
Intel Corporation SAS (French simplified joint stock company)
Registered headquarters: "Les Montalets"- 2, rue de Paris,
92196 Meudon Cedex, France
Registration Number: 302 456 199 R.C.S. NANTERRE
Capital: 4,572,000 Euros

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
--
Benjamin Walsh, SMTS
Wind River Rocket
www.windriver.com
Zephyr kernel maintainer
www.zephyrproject.org


Boie, Andrew P
 

How do you propose to implement returning an error code to the user? This isn't the heap...

Andrew

From: Tidy(ChunHua) Jiang [mailto:tidyjiang(a)163.com]
Sent: Sunday, September 25, 2016 3:32 AM
To: Boie, Andrew P <andrew.p.boie(a)intel.com>
Cc: devel(a)lists.zephyrproject.org
Subject: Re:Re: [devel] Nanokernel stack border protection

Hi Andrew,

Yeah, we can't really implement such function in fact, but we can and just return an error code to user. I think it's better than now.

Thx & Rgds.
Tidy.
At 2016-09-25 18:08:33, "Boie, Andrew P" <andrew.p.boie(a)intel.com<mailto:andrew.p.boie(a)intel.com>> wrote:

On Sat, 2016-09-24 at 14:39 +0800, tidyjiang(a)163.com<mailto:tidyjiang(a)163.com> wrote:
Hi All,
The nanokernel uses an array as stack memory space, but there is no
border protection when push data to the stack. When the array is
already full, it will cause array overfow, leading to unpredictable
behavior.
Why not add the border protection? When the array is full, it returns
an error code to user.
Is it necessary ?
How would you propose to implement such a border protection?
Andrew


Benjamin Walsh <benjamin.walsh@...>
 

On Mon, Sep 26, 2016 at 10:01:14AM +0100, Jon Medhurst (Tixy) wrote:
On Sun, 2016-09-25 at 10:08 +0000, Boie, Andrew P wrote:
On Sat, 2016-09-24 at 14:39 +0800, tidyjiang(a)163.com wrote:
Hi All,

The nanokernel uses an array as stack memory space, but there is no
border protection when push data to the stack. When the array is
already full, it will cause array overfow, leading to unpredictable
behavior.

Why not add the border protection? When the array is full, it returns
an error code to user.

Is it necessary ?
How would you propose to implement such a border protection?
Use the features provided by the CPU? On ARM Cortex-M, the stack limit
registers PSPLIM and MSPLIM. Presumably other CPUs have similar things.
Is this a new thing on ARMv8-M ? I don't remember seeing this on
ARMv7-M and I cannot find it in the ref. manual either (DDI0403E.b).


Boie, Andrew P
 

On Mon, 2016-09-26 at 10:01 +0100, Jon Medhurst (Tixy) wrote:
How would you propose to implement such a border protection?
Use the features provided by the CPU? On ARM Cortex-M, the stack
limit
registers PSPLIM and MSPLIM. Presumably other CPUs have similar
things.
This is cool, I think we should implement this for ARM targets. I will
file a user story.

Thinking out loud for x86:
If I understand correctly, push/pop operations work on whatever memory
segment is in SS. At the moment it's just the flat data segment.

I am not completely sure, but we might be able to use dedicated per-
thread stack segments, which would generate an exception if the bounds
are exceeded.

It's hard to find stuff on this Googling around since much of what is
written on this topic that I can find is more concerned with buffer
overflow protection and not exceeding the bounds of fixed-size stacks.

- We could define stack segments in the GDT for the set of known
threads, and set them when the threads are created. _Swap() would have
to be modified to additionally track SS when switching context.

- The struct tcs would need to be moved elsewhere as it currently lives
in the lower addresses of its thread's stack.

- We would need some black magic in how threads are created in
code...probably something like how IRQ_CONNECT() works, which looks
like a function call but populates the IDT, creates an assembly stub,
etc. We could do something similar to create the stack segments.

- In the generated assembly by GCC, it looks like when it references
data pushed on the stack (local variables, function arguments, etc) it
doesn't put any segment selector in the code, so its all in terms of
DS. I am not sure how to get the compiler to express all stack memory
references with SS, and whether there are any performance implications
of doing this.

The last point may be a dealbreaker, I am not sure. I'm digging through
the GCC manual to hopefully understand this better.

Andrew


Boie, Andrew P
 

On Mon, 2016-09-26 at 16:49 +0000, Boie, Andrew P wrote:
How do you propose to implement returning an error code to the user?
This isn’t the heap…
Disregard, this landed directly in my inbox, we're actually talking
about kernel LIFOs.

We could add checking to LIFOs, but this adds additional overhead. For
LIFO use-cases where we always know how deep we will be going, it's not
necessary.

I am unsure on whether that additional overhead is OK in the final
cost/benefit analysis, but I thought I would at least point it out.
It might be better to have a data structure built on top of LIFOs which
adds this tracking, and not modify the base data structure. 

Andrew


Boie, Andrew P
 

On Mon, 2016-09-26 at 17:33 +0000, Boie, Andrew P wrote:
- In the generated assembly by GCC, it looks like when it references
data pushed on the stack (local variables, function arguments, etc)
it
doesn't put any segment selector in the code, so its all in terms of
DS. I am not sure how to get the compiler to express all stack memory
references with SS, and whether there are any performance
implications
of doing this.

The last point may be a dealbreaker, I am not sure. I'm digging
through
the GCC manual to hopefully understand this better.
Yeah it's probably a dealbreaker. In C you can take the address of some
stack variable and pass it to another function, stack references seem
to really need to be on the data segment. Oh well.

I think I have to conclude that this kind of stack bounds checking
isn't possible on x86 at least in C code.

Andrew


Benjamin Walsh <benjamin.walsh@...>
 

On Mon, Sep 26, 2016 at 05:44:45PM +0000, Boie, Andrew P wrote:
On Mon, 2016-09-26 at 16:49 +0000, Boie, Andrew P wrote:
How do you propose to implement returning an error code to the user?
This isn’t the heap…
Disregard, this landed directly in my inbox, we're actually talking
about kernel LIFOs.

We could add checking to LIFOs, but this adds additional overhead. For
LIFO use-cases where we always know how deep we will be going, it's not
necessary.

I am unsure on whether that additional overhead is OK in the final
cost/benefit analysis, but I thought I would at least point it out.
It might be better to have a data structure built on top of LIFOs which
adds this tracking, and not modify the base data structure. 
Kernel LIFOs are unbounded, since they are lists. He's actually talking
about nanokernel stack objects, which are bounded.

Like I said in a previous response, there is an __ASSERT() in the
unified kernel on k_stack_push() now.


Mariusz Okrój <mariusz.okroj at intel.com...>
 

Stack boundary check can be implemented on x86 using paging mechanism (MMU). The only thing that need to be done is to separate stacks with non-mapped pages. So if the upper boundary of stack is reached (ESP goes into non-mapped page) then the PF exception is generated.

The only constraint of this solution is that stacks need to be aligned to 4kB.

Mariusz


Jon Medhurst (Tixy) <tixy@...>
 

On Mon, 2016-09-26 at 13:28 -0400, Benjamin Walsh wrote:
On Mon, Sep 26, 2016 at 10:01:14AM +0100, Jon Medhurst (Tixy) wrote:
[...]
Use the features provided by the CPU? On ARM Cortex-M, the stack limit
registers PSPLIM and MSPLIM. Presumably other CPUs have similar things.
Is this a new thing on ARMv8-M ? I don't remember seeing this on
ARMv7-M and I cannot find it in the ref. manual either (DDI0403E.b).
I think you're right, I only see it in the v8m ARM ARM (DDI0553A.b).

--
Tixy


Benjamin Walsh <benjamin.walsh@...>
 

On Mon, Sep 26, 2016 at 09:48:17PM +0000, Mariusz Okrój wrote:
Stack boundary check can be implemented on x86 using paging mechanism
(MMU). The only thing that need to be done is to separate stacks with
non-mapped pages. So if the upper boundary of stack is reached (ESP
goes into non-mapped page) then the PF exception is generated.

The only constraint of this solution is that stacks need to be aligned
to 4kB.
The problem with this is that it's not a general practical solution for
Zephyr, where stacks can be much smaller than 4K. And that's without
counting the 8K overhead of the page directory and page table. When you
have a system with 8K of RAM, this doesn't work...


LeMay, Michael <michael.lemay@...>
 

On Mon, 2016-09-26 at 17:33 +0000, Boie, Andrew P wrote:
...
Yeah it's probably a dealbreaker. In C you can take the address of some stack variable and pass it to another function, stack references seem to really need to be on the data segment. Oh well. I think I have to conclude that this kind of stack bounds checking isn't possible on x86 at least in C code.
This is possible on x86 with C. I already have it working for Contiki OS with an enhanced version of LLVM/Clang. It relies in part on the LLVM SafeStack pass that defines a separate "unsafe stack" for allocations that the compiler is unable to verify are accessed safely (http://clang.llvm.org/docs/SafeStack.html). So, only stack allocations that the compiler verifies are accessed safely are placed on the main/safe stack. I developed a patch for Contiki OS to place tight bounds around the safe stack in SS. I configured CS, DS, ES, FS, and GS to not overlap with SS, and I placed the unsafe stack in DS. I dealt with the challenge of handling stack references passed between functions by modifying the SafeStack pass to move all allocations used in that way to the unsafe stack (https://reviews.llvm.org/D17094). The compiler can then assume that no pointers to the safe stack are passed as function arguments. Safe stack pointers are only generated locally, within the same function that uses those pointers. There are some exceptions to this, like variadic argument lists, but those are handled specially. Based on the assumption that safe stack pointers are all generated and used within a function, I developed a new compiler pass that tracks the flow of safe stack pointers within a function (https://reviews.llvm.org/D17095, https://reviews.llvm.org/D17092). It adds segment override prefixes as necessary to direct memory accesses to the appropriate segments.


LeMay, Michael <michael.lemay@...>
 

On Mon, 2016-09-26 at 17:33 +0000, Boie, Andrew P wrote:
...
Yeah it's probably a dealbreaker. In C you can take the address of some stack variable and pass it to another function, stack references seem to really need to be on the data segment. Oh well. I think I have to conclude that this kind of stack bounds checking isn't possible on x86 at least in C code.
This is possible on x86 with C. I already have it working for Contiki OS with an enhanced version of LLVM/Clang. It relies in part on the LLVM SafeStack pass that defines a separate "unsafe stack" for allocations that the compiler is unable to verify are accessed safely (http://clang.llvm.org/docs/SafeStack.html). So, only stack allocations that the compiler verifies are accessed safely are placed on the main/safe stack. I developed a patch for Contiki OS to place tight bounds around the safe stack in SS. I configured CS, DS, ES, FS, and GS to not overlap with SS, and I placed the unsafe stack in DS. I dealt with the challenge of handling stack references passed between functions by modifying the SafeStack pass to move all allocations used in that way to the unsafe stack (https://reviews.llvm.org/D17094). The compiler can then assume that no pointers to the safe stack are passed as function arguments. Safe stack pointers are only generated locally, within the same function that uses those pointers. There are some exceptions to this, like variadic argument lists, but those are handled specially. Based on the assumption that safe stack pointers are all generated and used within a function, I developed a new compiler pass that tracks the flow of safe stack pointers within a function (https://reviews.llvm.org/D17095, https://reviews.llvm.org/D17092). It adds segment override prefixes as necessary to direct memory accesses to the appropriate segments.


LeMay, Michael <michael.lemay@...>
 

Of course, this wouldn't necessarily catch all stack overflows, specifically those on the unsafe stack.

-----Original Message-----
From: LeMay, Michael [mailto:michael.lemay(a)intel.com]
Sent: Friday, September 30, 2016 15:02
To: devel(a)lists.zephyrproject.org
Subject: [devel] Re: Re: Re: Re: Re: Nanokernel stack border protection

On Mon, 2016-09-26 at 17:33 +0000, Boie, Andrew P wrote:
...
Yeah it's probably a dealbreaker. In C you can take the address of some stack
variable and pass it to another function, stack references seem to really need to
be on the data segment. Oh well. I think I have to conclude that this kind of
stack bounds checking isn't possible on x86 at least in C code.

This is possible on x86 with C. I already have it working for Contiki OS with an
enhanced version of LLVM/Clang. It relies in part on the LLVM SafeStack pass
that defines a separate "unsafe stack" for allocations that the compiler is unable
to verify are accessed safely (http://clang.llvm.org/docs/SafeStack.html). So,
only stack allocations that the compiler verifies are accessed safely are placed
on the main/safe stack. I developed a patch for Contiki OS to place tight bounds
around the safe stack in SS. I configured CS, DS, ES, FS, and GS to not overlap
with SS, and I placed the unsafe stack in DS. I dealt with the challenge of
handling stack references passed between functions by modifying the SafeStack
pass to move all allocations used in that way to the unsafe stack
(https://reviews.llvm.org/D17094). The compiler can then assume that no
pointers to the safe stack are passed as function arguments. Safe stack pointers
are only generated locally, within the same function that uses those pointers.
There are some exceptions to this, like variadic argument lists, but those are
handled specially. Based on the assumption that safe stack pointers are all
generated and used within a function, I developed a new compiler pass that
tracks the flow of safe stack pointers within a function
(https://reviews.llvm.org/D17095, https://reviews.llvm.org/D17092). It adds
segment override prefixes as necessary to direct memory accesses to the
appropriate segments.