Re: [PATCH v2 03/11] unwind: Introduce SFrame user space unwinding

[Steven Rostedt]

On Wed, 02 Oct 2024 10:18:21 +0200
Florian Weimer <fweimer@xxxxxxxxxx> wrote:
> 
> I don't quite understand, sorry.
> 
> Doing a binary search on an unordered table fails to find some entries
> that could be discovered by a linear scan.  But an attacker could just
> as well use an incomplete table from the start.  So assuming an ordered
> table seems rather unlikely to introduce additional problems.  (Given
> the lack of a formal threat model, it's impossible to make more precise
> claims in either direction.)

Basically, the idea is if anything is out of place, scrap the entire
process. An unordered table can give unpredictable results, that could be
used latter as a gadget. If the kernel expects a sorted table and it ends
up not being sorted, it should automatically flag it as corrupt and stop
all processing.

The kernel doesn't need to scan the entire table each time to see if it is
sorted, that would kill the point of it being sorted in the first place.
But it can check that the values merge towards a correct answer. All it
needs to do is keep track of the current highest and lowest values, and if
it finds something outside that range, it should abort immediately.

The effort needed to validate is very low, so it should be done.

-- Steve