Is the co-pilot itself performance-sensitive? [LWN.net]

Is the co-pilot itself performance-sensitive?

Posted Sep 22, 2024 19:10 UTC (Sun) by rweikusat2 (subscriber, #117920)
In reply to: Is the co-pilot itself performance-sensitive? by geofft
Parent article: pcp: pmcd network daemon review (SUSE Security Team Blog)

You'll have to appreciate the irony that the SUSE fix for this issue has undefined behaviour.

- if (vindex < 0 || vindex > pdulen) {
+ if (vindex < 0 || (char *)&pdubuf[vindex] >= pduend) {

The first (original line) is the wrong comparison. It's wrong because vindex is used to index an array of __mPDU (32 bit with current definition) and not bytes. Correct code would be

if (vindex < 0 || vindex > pdulen / sizeof(__pmPDU)) {

The SUSE fix calculates the address the array element at position vindex would correspond to and compares that with the end of the received data. The expression

pdubuf[vindex]

is defined to be identical to

*(pdubuf + vindex)

6.5.6|8 states that, for such an addition

If both the pointer operand and the result point to elements of the same array object, or one past
the last element of the array object, the evaluation shall not produce an overflow; otherwise, the
behavior is undefined.

The behaviour of the SUSE code is thus undefined in case vindex is actually out of bounds by more than one.

:-)

Is the co-pilot itself performance-sensitive?

Posted Sep 22, 2024 22:43 UTC (Sun) by NYKevin (subscriber, #129325) [Link] (1 responses)

One wonders whether a sufficiently aggressive compiler will decide to translate the "fixed" version into (something equivalent to) this:

if(vindex < 0 || (char *)&pdubuf[vindex] == pduend) {

As far as I can tell, that's a legal optimization under the as-if rule, since you're allowed to assume that we never construct a pointer more than one past the end (even if it is not dereferenced).

Of course, in order for that to happen, the compiler would have to know that pduend is the actual end of the array, and not just some random pointer within the array. Maybe the compiler they tested it on is not smart enough to figure that out yet, and this will bite us all again in a few more years. The compiler would also need to somehow conclude that == is faster than >=, which strikes me as unlikely, but it can sometimes be difficult to tell what the compiler will do with a given piece of code under multiple optimization passes.

(For those less familiar with C's arcane UB rules: &foo[bar] expands to &*(foo + bar), and the standard explicitly specifies that &* cancels out and no dereference takes place. So we can't remove the whole comparison entirely - it is legal to construct a pointer exactly one past the end with an expression like that, and so the compiler is required to emit code which at least checks for such a pointer.)

Is the co-pilot itself performance-sensitive?

Posted Sep 22, 2024 22:45 UTC (Sun) by NYKevin (subscriber, #129325) [Link]

> For those less familiar with C's arcane UB rules: &foo[bar] expands to &*(foo + bar), and the standard explicitly specifies that &* cancels out and no dereference takes place. So we can't remove the whole comparison entirely - it is legal to construct a pointer exactly one past the end with an expression like that, and so the compiler is required to emit code which at least checks for such a pointer.

Side note: If the compiler can prove that the pointer can't be exactly one past the end (e.g. if it can prove that vindex is odd and the array is of even length, or vice-versa), then it may indeed omit the entire check, which I suspect is where problems might plausibly arise.

Is the co-pilot itself performance-sensitive?

Posted Sep 23, 2024 0:24 UTC (Mon) by ms-tg (subscriber, #89231) [Link] (4 responses)

Thanks so much for this:

> You'll have to appreciate the irony that the SUSE fix for this issue has undefined behaviour.
> - if (vindex < 0 || vindex > pdulen) {
> + if (vindex < 0 || (char *)&pdubuf[vindex] >= pduend) {
>
> The first (original line) is the wrong comparison. > It's wrong because vindex is used to index an array of __mPDU (32 bit with current definition) and not bytes. Correct code would be
>
> if (vindex < 0 || vindex > pdulen / sizeof(__pmPDU)) {

Question: is it worth someone making a tiny PR with this change and the explanation above?

Is the co-pilot itself performance-sensitive?

Posted Sep 23, 2024 2:03 UTC (Mon) by viro (subscriber, #7872) [Link] (2 responses)

>> if (vindex < 0 || vindex > pdulen / sizeof(__pmPDU)) {

> Question: is it worth someone making a tiny PR with this change and the explanation above?

Wouldn't vindex equal to pdulen / sizeof(....) end up with off-by-one?

Is the co-pilot itself performance-sensitive?

Posted Sep 23, 2024 9:12 UTC (Mon) by rweikusat2 (subscriber, #117920) [Link] (1 responses)

It would. The best way to express this without errors is probably

if (vindex < 0 || vindex >= pdulen / sizeof(*pdubuf)) {

as this uses the actual type of the array element, whatever it is.

Is the co-pilot itself performance-sensitive?

Posted Sep 23, 2024 9:25 UTC (Mon) by rweikusat2 (subscriber, #117920) [Link]

Additional remark: Assuming that pdubuf if either an array of __pmPDU or a pointer to __pmPDU, the expressions

pdubuf[0]

and

*pdubuf

are semantically identical.

Is the co-pilot itself performance-sensitive?

Posted Sep 23, 2024 11:07 UTC (Mon) by rweikusat2 (subscriber, #117920) [Link]

I don't use this program. Because of this, I can't test any changes to it and because of that, I won't make any as code which hasn't been tested likely doesn't work, anyway. :-)

In theory, ie, it will likely be impossible to hit this in practice, the

&pdubuf[vindex]

could also trigger a pointer wraparound at the end of the address space and the >= test could thus fail because the code is really equivalent to

(char *)pdubuf + vindex * sizeof(*pdubuf)

The multiplication which opens up the path to a possible overflow isn't visible when using index-notation but the actual address calculation will have to employ it nevertheless.

Undefined behaviour

Posted Oct 8, 2024 9:47 UTC (Tue) by mgerstner (guest, #164735) [Link] (1 responses)

> You'll have to appreciate the irony that the SUSE fix for this issue has undefined behaviour.
>
> - if (vindex < 0 || vindex > pdulen) {
> + if (vindex < 0 || (char *)&pdubuf[vindex] >= pduend) {

I agree that this is formally undefined behaviour. Note that this is not specifically a SUSE authored patch, though, it has been authored by PCP upstream. There are a lot more such constructs found in the PCP codebase, and I actually recommended to upstream to refactor the protocol processing on a larger scale, because it is hard to read, partly confusing and error prone.

Undefined behaviour

Posted Oct 9, 2024 0:25 UTC (Wed) by viro (subscriber, #7872) [Link]

It's more than formally undefined behaviour; it's a very real bug on any architecture where you might get pdubuf close to the top of address space. If (uintptr_t)pdubuf > (uintptr_t)( -sizeof(pdubuf[0]) * vindex), you are likely to end up with code that will cheerfully calculate an address well below pdubuf itself, let alone pduend.

I hadn't seen the function in question, but if pdubuf elements are more than single-byte (as they appear to be, from the context) and vindex is signed 32bit, _any_ address on 32bit architecture is vulnerable to that.

You might get away with that in case if vindex is 16bit and you know that e.g. userland addresses are guaranteed to be under 4G-32K*sizeof, but such warranties are brittle - while for i386 Linux userland this is normally promised (the upper 1G is used by the kernel), just run that 32bit program on amd64 box with 32bit emulation enabled (default for a lot of amd64 configs) and you suddenly can see addresses very close to the top of 32bit space.

There's a good reason why you are not allowed to take pointers to array elements beyond just after the object, and it's not anything exotic as it is in case of quite a few UB. This one really bites on bog-standard architectures, without insane optimizers, etc.
If their codebase really has a lot of such examples, well... welcome to Dave Bowman code review moment. As in, "it goes on forever - oh my God - it's full of s<garbled><transmission terminated>"...