On Fri, Jan 29, 2021 at 03:39:35PM -0600, Madhavan T. Venkataraman wrote:

On 1/28/21 9:26 AM, Josh Poimboeuf wrote:

quoted

Are we still considering the shadow stack thing?  Just wondering why
we're talking about objtool again.

I think that we are still considering the shadow stack thing. No discussion
has happened. Based on my limited knowledge of shadow stacks, I think that
shadow stacks do not get rid of objtool.

I have a slightly messy implementation for compiler generated functions
which I've not posted yet.

Advantages
==========

The only advantage in shadow stacks that I can see is that stack corruption
will not prevent unwinding from happening (unless the shadow stack gets
corrupted somehow).

One of the high level goals with reliable stacktrace is to determine if
we can trust the results of our unwinding, having a duplicate copy of
the function pointer information in the stack helps with this since we
can check that the normal and shadow stacks agree with each other.  This
means that stack corruption, race conditions or general cleverness would
need to result in the same changes being visible in both copies of the
stack so we're more likely to notice if something goes wrong.

Issues common with frame pointers
=================================

- The compiler has to generate the prolog and epilog. If we cannot trust the
  compiler to generate these for frame pointers, can we trust it to
  generate these for the shadow stack? If we can't, we would need objtool
  anyway.

Adding a static check with objtool will always add a degree of trust
that everything is right, though as Ard noted there's always a risk of
false positives too.  It may, however, be the case that there are enough
other checks that people are comfortable even without and we can I'm
sure find things that objtool misses - objtool doesn't mean we should
ignore other checks we can do.

- The compiler would only generate shadow stack code for C functions.
  For assembly functions, it has to be done by hand. So, objtool has to
  check this anyway, right?

We already have annotations in place that allow us to insert prologues
and eplogues into assembly code so this is less intractible than it
might seem, though there's some faff to consider around early boot.
Even without doing this we can readily detect when the shadow stack
update has not been done and reject traces that have affected funtions.

- Inline assembly in C functions can screw up the shadow stack just like
  it can screw up frame pointers. Again, objtool needs to check.

As I mentioned above they'd need to change both stacks in the same
manner which is of course possible but harder.

Issues unique to shadow stacks
==============================

- Performance hit because of the extra cache and memory footprint. There is
  a paper that says that the performance hit can be as high as 10%. Using
  a parallel shadow stack reduces the hit to about 3.5%. But then again,
  the characteristics for the kernel may be different.

10% definitely seems quite out there for the overhead - of course there
is some overhead but that doesn't seem realistic.

- A separate register has to be reserved for holding the shadow stack
  pointer. The compiler (gcc) has to be changed to not use this register for
  other purposes. And we have to trust that there are no compiler bugs
  in this area. All assembly code that currently uses this register for
  anything needs to be reviewed and potentially changed. This includes
  all inline assembly code. BTW, I believe clang uses x18 for the shadow
  stack pointer register.

Please be aware that we have had shadow call stack support in mainline
since v5.8 when building with clang so if there are correctness problems
then we already have bugs regardless of what happens with reliable stack
trace and live patching.  This is an existing feature which we can use
to improve the robustness of reliable stack trace, it is not something
people are considering doing solely for reliable stack trace.

As you say arm64 uses x18 for the shadow call stack pointer, currently
only clang supports shadow call stacks but I'd be surprised to see GCC
pick up the feature and choose a different register.

Do we have to worry about code that modifies the return address
of a function?

Yes, that's definitely a concern.