Looks like the lix fall distance can overflow its int variable?

[ccexplore]

Github issue #397: Overflowing phyus and fall distance



Playing Minim's current LSC lix level, featuring lixes that can fall forever thanks to vertical wrapping of the level, it suddenly dawned on me that a value that might grow arbitrarily large is a red flag in programming.

And look at the source code seems to confirm my suspicions--pixelsFallen doesn't seem to be bounds-checked in any way, so with an infinite-falling setup, I think it's possible for it to overflow and wrap around, unless D handles integer arithmetic differently than most languages.  In particular, there'd be a large range of negative values it can wrap around to that would effectively grant the lix immunity from splatting for quite a range of falling distances.

Please take a look at the code and/or maybe even test it out, and see if you agree with my conclusion here or not.

I'm not going to exploit this bug for the LSC even if it turns out to be real.

[Forestidia86]

I remember having a similiar question concerning physics updates as well.

If you are right that there is a theoretical possibility to overflow, it would be indeed unclean. But is it viable that this happens in real play?

pixelsFallen is int. Which seems to be 32 signed bits (i.e. 2^31 on the positive numbers) and terminal velocity seems 8 pixels per phyu (i.e. about 2^28 phyus for wraparound?).
Would really someone like to produce and watch such a replay, although replay editing and verifier could be a means? Nevertheless good point.

[namida]

Does Lix have any reason to keep track of the fall distance once it's reached splat height, rather than just knowing "splat height has been reached"? If not, it should cap at this point.

NL should do the same. While NL lacks wrap, an infinite fall is instead possible there by use of teleporters.

[ccexplore]

It just occurred to me that time itself (eg. phyus counter) might also overflow, although I haven't checked the lix source code on that.  Depending on details of implementation, you might conceivably end up with cases where replay would actually fail, because moves may need to occur at times sufficiently beyond the overflow value for time, causing a much smaller and thereby incorrect time value to be recorded in the replay for the action, which likely would prevent the action from being played back at the intended time.

Of course, since the fall speed is higher than 1 per phyus, fall distance overflow would occur quite a bit sooner than time itself might overflow, so I don't think time overflow can impact all solutions that try to exploit fall distance overflow.  And it only affects options like use of replay verifier anyway.

I don't remember how fast turbo speed is on lix, but it's probable that even at that speed, it'd still be considered impractical to work through the 2^28 phyus needed to achieve fall distance overflow.  At least not without modding lix to, say, do a version of turbo speed that truly runs as fast as hardware allows.

Use of 64-bit instead of 32-bit variables would likely also put overflow exploits squarely into the realm of impracticality, ignoring mods that try to perform smarter handling of carrying out large number of phyus.  And like namida said, for fall distance overflow, capping the fall distance to some maximum value at least as high as the splat height should suffice, as the (intended) physics should not be sensitive to the exact fall distance value once it goes beyond splat height.

[namida]

I don't remember how fast turbo speed is on lix, but it's probable that even at that speed, it'd still be considered impractical to work through the 2^28 phyus needed to achieve fall distance overflow.  At least not without modding lix to, say, do a version of turbo speed that truly runs as fast as hardware allows.

Frameskips would help here. NL has an advantage here: You can define an arbitrary length frameskip hotkey. If you wanted to, you could define a frameskip for 715827882 frames, which should be just enough to trigger the bug (maybe give or take one frame). Of course, it would still take ages to process. I opened Wimpy 28 "Get up, up, up!" from Lemmings Plus I, which is a very small level with few lemmings. I assigned a hotkey for 1,000,000 frames forward. It took about 1 minute 19 seconds to process this skip. That would mean nearly 16 hours to process the number of frameskips needed for the fall to become non-fatal. You could assign such a hotkey and leave it running overnight - and you could use a PC that's more powerful than mine to save some time here too.

By comparison, Lix cannot (as far as I know) do arbitrary frameskips, so you'd need to be manually doing max-length skips repeatedly. You could perhaps write a script that does it instead. Lix also has high-resolution physics (NL offers high-resolution graphics, but physics remain low-res, and so this has very little impact on the duration of the skip - the above test took an extra 3 seconds in high-res mode). On the flipside, Lix is much more efficient than NL at running physics updates, and needs less updates before the overflow occurs. Still, I'm going to guess we'd be looking at at least a few hours in the best case scenario, so this is pretty impractical for anything but the craziest of challenge solutions.

In either case, you could also custom-write a replay file that makes use of this without actually executing the solution yourself - but you've still got that wait to actually verify it. (Most likely, this will be quicker than actual in-game replaying on both engines. Not 100% sure for Lix, but NL does replay checks much faster than in-game replay playback, even when using frameskips.) And if it fails, you have no idea what actually went wrong, most likely.

[Simon]

Yes, it's an overflow bug in Lix. Good find, yes, Forestidia had the idea before, too.

It should be patched for 0.10.0, whenever that comes, as namida suggests, fallers that have achieved splat fall distance should remain splat-prone until the end of the fall.

In D, signed ints are defined to overflow by two's complement like an unsigned int, and only during interpretation treat the most significant bit as a sign bit. (In C and C++, signed int overflow would be undefined, even though implementations on contemporary machines often treat them like D has to.)

-- Simon

[ccexplore]

Have you also consider what to do for possible overflow of time/phyus counter?  Perhaps bump it to 64-bit to make it exponentially more impractical?  Maybe actually stop physics update altogether if time ever went high enough to about to overflow?  Or just ignore it, safe in the knowledge that it is (probably?) not exploitable solution-wise and just a theoretical nuisance affecting replays?

(In C and C++, signed int overflow would be undefined, even though implementations on contemporary machines often treat them like D has to.)

As I recall, leaving it as undefined also permits certain kinds of optimizations (particularly around loops) to be more broadly applicable, as leaving overflow behaviors as undefined basically allows compiler writers to assume it cannot happen for purpose of applying such optimizations (because even if it does happen, any resulting behavior by the resulting optimized code is permissible, even behaviors that would be completely baffling to someone looking at the source code).

[Simon]

64-bit physics updates would be a physics change because the binary networking protocol hardcodes 32 bits for this field.

But yes, it's sound to upgrade phyus to 64-bit or to stop physics at at 2^31 - 1. The stop is sounder game-design-wise but sadder mathematically.

-- Simon

[Forestidia86]

Couldn't the game count as lost if you reach the phyus limit without reaching the save requirement? Regularly you would never reach it anyways. (Although verifying a replay with a number out of limits already gives a Fail-T. In case there is no other assignment beforehand, even for won replays as well. Have forgotten why though.)

The problem is what happens with an edited replay that has a higher phyu number for an assignment? Maybe give an error message to the user that the replay is out of limits?