Suspicious use of signed arithmetic leads to negative index crash
ClosedPublic

Authored by marten on Sep 23 2018, 7:13 PM.

Details

Summary

The card deck is shuffled in shuffled() (in dealer.cpp) using a random number generator that, according to the comments above, is identical to the Freecell one. I'm not familiar with the details of the Windows implementation, but the kpat implementation uses bitwise operators on signed values which according to the C11 standard (quoted at https://wiki.sei.cmu.edu/confluence/display/c/INT13-C.+Use+bitwise+operators+only+on+unsigned+operands) can give implementation defined results.

What I have observed when recompiling kpat recently (possibly after a switch to GCC 7.3.0) is the 'seed' value after a few iterations of the loop becoming negative due to integer overflow. Then 'rand' also becomes negative (despite the '& 0x7fff'!), 'rand % i' again is negative and the result.swap() below segfaults.

Changing the type of the 'seed' variable to unsigned appears to avoid the problem, although I don't know whether this will be incompatible with the Freecell implementation.

Test Plan

Run kpat without this change, select and deal a new game. A segfault will regularly occur at the result.swap() line.
Build and run kpat with this change, there is no segfault and the game is dealt correctly.

Diff Detail

Repository
R410 KPatience
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
marten created this revision.Sep 23 2018, 7:13 PM
Restricted Application added a subscriber: kde-games-devel. · View Herald TranscriptSep 23 2018, 7:13 PM
marten requested review of this revision.Sep 23 2018, 7:13 PM
fabiank accepted this revision.Oct 10 2018, 6:36 AM

Thanks for the patch. I can't reproduce the crash, but I agree with you that this is UB and should be fixed. I don't think that this changes how the RNG works, but even if it would, not crashing is more important.

This revision is now accepted and ready to land.Oct 10 2018, 6:36 AM
marten edited the summary of this revision. (Show Details)Oct 10 2018, 7:32 AM
This revision was automatically updated to reflect the committed changes.

Perhaps use the RNG code from https://fc-solve.shlomifish.org/faq.html#what_are_ms_deals which can handle up to 2**33 deal indices. Furthermore, does this code have unit tests?

fabiank added a comment.EditedOct 10 2018, 9:35 AM

Unfortunately, there are no unit tests at all, as there is a rather tight coupling of UI code and game logic. The RNG could however be tested in isolation. Though I'm not sure how one could test whether it behaves the same as Microsoft ones.