Buffer overflow in `GetBoundsEdge`

[zear]

Whenever GetBoundsEdge gets called with a particular combination of plane1/plane2 values, the pos->v and edge->v vectors end up accessed at out-of-bounds indices. In one particular situation, when edge points to memory allocated at the start of a stack frame, this kicks up stack smashing protection and terminates the program.

Analysis

GetBoundsEdge was written with an assumption that d1 and d2 will always yield different digits in range [0..2]: https://github.com/dethrace-labs/dethrace/blob/48b70bb8ff08dae10b00d285a9cc6e6b24a1eeac/src/DETHRACE/common/car.c#L3884-L3885

As such, the value of d3 is then calculated as the remaining digit in said range: https://github.com/dethrace-labs/dethrace/blob/48b70bb8ff08dae10b00d285a9cc6e6b24a1eeac/src/DETHRACE/common/car.c#L3899

However, in practice this function is sometimes called with plane1/plane2 values that produce the same value as result of the & operation. After extensive testing, I observed two such cases:

1. plane1 = 5, plane2 = 1, producing:

   d0 = 0;
   d1 = 0;
   d2 = 3;

2. plane1 = 5, plane2 = 5, producing:

   d0 = 0;
   d1 = 0;
   d2 = 3;

In both cases d2 is used to incorrectly access pos->v[3] and edge->v[3], outside boundaries of those those two arrays. Moreover, pos->v[1]/edge->v[1] is never overwritten and will be left with old values.

This is practice, but in theory we could also have combinations of plane1/plane2 that produce:

d0 = 1;
d1 = 1;
d2 = 1;

d0 = 2;
d1 = 2;
d2 = -1;

d0 = 3;
d1 = 3;
d2 = -3;

I can't tell whether OG also receives the reproduced combinations of plane values, or if the bug is hiding somewhere in Dethrace's calculation of those variables (which would be LineBoxColl). Someone with more experience at debugging DOS/Windows programs would need to check those out-of-bound accesses in OG blobs at runtime.

To mitigate the buffer overflow, we could simply do:

if (d2 > 2)
    return 1;

If this is an OG bug, then that would put us on par with the OG. But I think we should further debug this issue and see if two planes with matching vector indices are legal, and if so, if we can somehow derive what is supposed to happen with the other vector values.

Steps to reproduce

There is no easy way to reproduce this bug (it might require multiple attempts), however I found this method to yield somewhat consistent results:

1. Select a strong car (e.g. Police APC)
2. Launch the "Fridge Racer" track
3. Pick up speed and mow down the row of safety posts located to the right of the start position (marked in blue below). It seems to create best results when in the process the car also collides with the lamp post.

This might require several minutes to reproduce, so make sure to have a debugger session running.

[madebr]

I hooked GetBoundsEdge of the OG Carma95.exe (Splat Pack edition) and instrumented it as follows

static int(__cdecl*original_GetBoundsEdge)(br_vector3 *, br_vector3 *, br_bounds *, int, int, br_vector3 *, br_vector3 *, br_vector3 *, int) = (int(__cdecl*)(br_vector3 *, br_vector3 *, br_bounds *, int, int, br_vector3 *, br_vector3 *, br_vector3 *, int))0x0048551f;
CARM95_HOOK_FUNCTION(original_GetBoundsEdge, GetBoundsEdge)
int __cdecl GetBoundsEdge(br_vector3 *pos, br_vector3 *edge, br_bounds *pB, int plane1, int plane2, br_vector3 *a, br_vector3 *b, br_vector3 *c, int flag) {
    static unsigned plane_counts[4][4];
    static unsigned total_count = 0;

    // Verify plane1 and plane2 won't cause buffer overflow.
    if (plane1 == 0 || plane2 == 0) {
        abort();
    }
    plane_counts[(plane1 - 1) & 3][(plane2 - 1) & 3] += 1;
    total_count += 1;

    if ((total_count % 100) == 0) {
        printf("GetBoundsEdge: count = %u\n", total_count);
        printf("GetBoundsEdge:             plane1\n");
        printf("GetBoundsEdge: plane2 |   1   |   2   |   3   |   4   |\n");
        printf("GetBoundsEdge: =======+=======+=======+=======+=======+\n");
        printf("GetBoundsEdge:    1   | %5u | %5u | %5u | %5u |\n", plane_counts[0][0], plane_counts[1][0], plane_counts[2][0], plane_counts[3][0]);
        printf("GetBoundsEdge:    2   | %5u | %5u | %5u | %5u |\n", plane_counts[0][1], plane_counts[1][1], plane_counts[2][1], plane_counts[3][1]);
        printf("GetBoundsEdge:    3   | %5u | %5u | %5u | %5u |\n", plane_counts[0][2], plane_counts[1][2], plane_counts[2][2], plane_counts[3][2]);
        printf("GetBoundsEdge:    4   | %5u | %5u | %5u | %5u |\n", plane_counts[0][3], plane_counts[1][3], plane_counts[2][3], plane_counts[3][3]);
        printf("GetBoundsEdge:");
    }

    return original_GetBoundsEdge(pos, edge, pB, plane1, plane2, a, b, c, flag);
}

It prints the following table:

GetBoundsEdge:GetBoundsEdge: count = 13200
GetBoundsEdge:             plane1
GetBoundsEdge: plane2 |   1   |   2   |   3   |   4   |
GetBoundsEdge: =======+=======+=======+=======+=======+
GetBoundsEdge:    1   |     8 |   187 |    71 |     0 |
GetBoundsEdge:    2   |  7346 |     0 |  1575 |     0 |
GetBoundsEdge:    3   |   950 |  3062 |     1 |     0 |
GetBoundsEdge:    4   |     0 |     0 |     0 |     0 |

So cases where plane1 == plane2 also happen in OG, albeit seldomly. I could create the case where plane1 == plane2 == 3 only once. The game temporarily locked up, and the car ot damaged severely.

[zear]

Thanks! I also managed to hook up CARMA95.EXE into a debugger via wine:

winedbg --gdb CARMA95.EXE
b *0x48553c if (*(int *)($ebp - 0x1c) == *(int *)($ebp - 0x20))

This let me to catch the following case:

plane1 == 3
plane2 == 7
d0 == 2
d1 == 2
d2 == -1 (I presume)

Here's the full log:

Wine-gdb> p (*(int *)($ebp - 0x1c) == *(int *)($ebp - 0x20))
$29 = 1
Wine-gdb> p *(int *)($ebp - 0x1c)
$30 = 2
Wine-gdb> p *(int *)($ebp - 0x20)
$31 = 2
Wine-gdb> p *(int *)($ebp + 0x14)
$32 = 3
Wine-gdb> p *(int *)($ebp + 0x18)
$33 = 7

Edit: This is the result of the above case:

Geometry of that lamp post is embedded in the road barrier and any attempt to touch it results with the framerate severely dropping, similar to @madebr's report. No more plane1 == plane2 coming from it, though.

[zear]

To mitigate the crashes, I propose a temporary workaround, until the root cause is understood better:

    d1 = (plane1 - 1) & 3;
    d2 = (plane2 - 1) & 3;
#if defined(DETHRACE_FIX_BUGS)
    if (d1 == d2) {
        d2 = (d2 + 1) % 3;
    }
#endif

This way we make sure that d1, d2 and d3 all stay at different values and no buffer under/overflow is possible. I tested the above workaround and no wonky physics were observed whenever d1 == d2 edge case has been triggered.

[MastaG]

Just out of curiosity, were you able to address this issue?

[madebr]

This has not yet been addressed.

[MastaG]

Check, because I've tried to reproduce it with the same car, but couldn't get it to crash.

[zear]

Proper fix for this issue requires the understanding of collision planes in terms of 3d geometry. I failed to fully comprehend this concept and currently have no time to work on this issue. Feel free to take over.

The workaround proposed in https://github.com/dethrace-labs/dethrace/issues/296#issuecomment-1448476592 simply guarantees that there are no out-of-bound accesses, but it might cause the wrong planes to intersect.

[b-kurczynski]

Hi, maybe this would help somehow.

I asked copilot about LineBoxColl() function and below is the most useful explanation I got:

Analyzing the provided code snippet from the LineBoxColl() function, we can identify the conditions under which it returns specific values and what those values represent. The function appears to be part of a collision detection system, possibly determining the point of collision between a ray and an axis-aligned bounding box (AABB).

• Return Value 8: This is returned if the starting point of the ray (o) is inside the bounding box. The condition for this is checked before the provided code snippet.
• Return Value 0: This value is returned in two scenarios:
  • If the ray direction component (dir.v[i]) is parallel to the plane being checked (quad[i] == 2 || dir.v[i] == 0.0) and no valid collision point is found within the segment of the ray being considered (cp[which_plane] < 0.0 || cp[which_plane] > 1.0).
  • If the calculated hit point (pHit_point->v[i]) is outside the bounding box (pB->min.v[i] to pB->max.v[i]) for any dimension that is not the collision plane.
• Other Return Values: The function calculates a return value based on the plane of collision and the quadrant of that plane where the collision occurs. This is done using the formula which_plane + 4 * quad[which_plane] + 1. Given that which_plane is determined by iterating over three dimensions (0, 1, 2) and quad[which_plane] can theoretically be any integer (but typically, in the context of AABB, it would be 0 or 1 indicating the side of the plane the ray hits), the possible return values from this part of the function can vary widely. However, without specific bounds on quad[which_plane], we can only speculate on the range of values. Assuming quad[which_plane] is either 0 or 1 (which is common in AABB collision detection for indicating whether the collision is with the "start" or "end" side of the box in that dimension):
  • For which_plane = 0, return values can be 1 or 5.
  • For which_plane = 1, return values can be 2 or 6.
  • For which_plane = 2, return values can be 3 or 7.

[...]

Other explanation was that this is a variant of Slab method collision detection.

Now if we align the measurements maderb did here with above explanation it's perfectly visible why 4 does not occur in the measurements - it's a valid result. Another 99% accurate assumption is that plane 1 is parallel to plane 5, plane 2 to plane 6 and plane 3 to plane 7.