Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Rewrite OverflowSafeInt to avoid undefined behaviour #8285

Closed
wants to merge 8 commits into from

Conversation

techgeeknz
Copy link
Contributor

@techgeeknz techgeeknz commented Jul 30, 2020

The current implementation of OverflowSafeInt does not handle the maximally-negative boundary condition very well. This rewrite uses an unsigned type to calculate and represent absolute values, to avoid invoking undefined behaviours such as abs(INT64_MIN) < 0 and -INT64_MIN == INT64_MIN. Fixes #8284.

@nielsmh
Copy link
Contributor

nielsmh commented Jul 30, 2020

I don't think the regression test suite exercises OverflowSafeInt as it is. I can't think of a good way to do that without major changes to the test, but it's probably worth setting as a goal.

@techgeeknz
Copy link
Contributor Author

I'm willing to write tests for it, if somebody can point me in the direction of the documentation for the test suite. Presumably, these make use of the squirrel API in some shape or form?

@nielsmh
Copy link
Contributor

nielsmh commented Jul 30, 2020

Is there any documentation for the tests at all? It works by loading a specific savegame with an AI script, the AI script then does various actions and writes various values to logging. After executing for a number of game ticks the game exits, and the console output is compared to an expected output.

So there's three parts to potentially modify: The AI script to add/change behaviours to exercise. The expected output if the expected behaviour changes. The savegame if some basic premises need to be changed. (Changing the savegame is probably rather risky.)

@techgeeknz
Copy link
Contributor Author

Nope. I'm not touching that with a 10-foot barge pole 😎.

@LordAro
Copy link
Member

LordAro commented Jul 30, 2020

Yeah, it would be difficult to get close to over/underflow testing with the AI scripts anyway - certainly extremely time consuming (talking hours) and not something that's feasible for regression tests

@techgeeknz
Copy link
Contributor Author

I guess the code is nowhere near modular enough for a TDD design with dependency injection to ever be feasible?

@techgeeknz
Copy link
Contributor Author

With e97dd52, the only instances of OverflowSafeInt are via the OverflowSafeInt32 and OverflowSafeInt64 typedefs. Would there be any objection to simplifying the template to use std::numeric_limits<T> instead of (the impression of) freely-selectable saturation limits?
My concern is that the current implementation assumes that T_MIN is negative and T_MAX is positive, and that both are of similar magnitude (whereas the previous implementation assumed that T_MIN == -T_MAX); and with user-selected limits, that assumption may be invalid. At the very least, we could enforce that the type parameter is a signed integer type.

@JGRennison
Copy link
Contributor

Ideally this check would just be a static_assert, but that is probably asking a bit much when targeting C++11.

A command line switch which ran some unit-style tests, output any required log messages, and then exited with the appropriate exit code would be a simple/automatable way to test things like this which don't require a full game state.

@LordAro
Copy link
Member

LordAro commented Jul 30, 2020

Go for it, don't see why not

@LordAro
Copy link
Member

LordAro commented Jul 30, 2020

Can't say I'm a fan of a "command line switch" solution to doing unit tests - I don't really want test code in the actual "game", as it were.

A separate executable that actually runs/tests the non-side-effecty bits that you actually can run unit tests on should be the preferred solution.

@techgeeknz
Copy link
Contributor Author

A separate executable that actually runs/tests the non-side-effecty bits that you actually can run unit tests on should be the preferred solution.

If said executable could (optionally) be built and run during the compilation process; that would be even better 😄

@LordAro
Copy link
Member

LordAro commented Jul 30, 2020

For really simple stuff, static_assert/assert_compile should be preferred, of course

src/core/overflowsafe_type.hpp Outdated Show resolved Hide resolved
src/core/overflowsafe_type.hpp Outdated Show resolved Hide resolved
src/core/overflowsafe_type.hpp Outdated Show resolved Hide resolved
src/core/overflowsafe_type.hpp Outdated Show resolved Hide resolved
src/core/overflowsafe_type.hpp Outdated Show resolved Hide resolved
@James103
Copy link
Contributor

James103 commented Aug 5, 2020

Yeah, it would be difficult to get close to over/underflow testing with the AI scripts anyway - certainly extremely time consuming (talking hours) and not something that's feasible for regression tests

Could a specific regression test (with different savegame and AI scripts) be prepared just to test for those boundary conditions, where the AI company's money is hacked to be near INT64_MIN?

@techgeeknz techgeeknz force-pushed the overflow_safe_int branch 15 times, most recently from cd05c4e to e7b43bf Compare August 24, 2020 00:21
@techgeeknz
Copy link
Contributor Author

techgeeknz commented Aug 24, 2020

There are two issues that I cannot seem to resolve:

  1. Why does the regression test fail with what looks like a bunch of off-by-one errors when I implement a templated constructor that accepts any integral type?
  2. Just what exactly is MSVC's problem? Why does it choke so badly on this?

@techgeeknz techgeeknz force-pushed the overflow_safe_int branch 3 times, most recently from 1927bc2 to c2b660c Compare September 1, 2020 02:31
@techgeeknz techgeeknz force-pushed the overflow_safe_int branch 2 times, most recently from 8ffc8bf to 48f6b22 Compare September 1, 2020 08:25
@LordAro
Copy link
Member

LordAro commented Sep 1, 2020

I feel like the changes in this PR have gone a bit "out of scope". Can you explain the RawValue additions? Why is operator() not sufficient?

@techgeeknz
Copy link
Contributor Author

techgeeknz commented Sep 1, 2020

I feel like the changes in this PR have gone a bit "out of scope". Can you explain the RawValue additions? Why is operator() not sufficient?

Good question. By requiring explicit typecasting from OverflowSafeInt to regular overflow-unsafe integrals, I was able to uncover a number of bugs and potential problems that were introduced by unintentional implicit typecasts to overflow-unsafe integers.

I had originally intended to use explicit operator T () for this purpose, but it soon became evident that the type to be cast is often not readily apparent from the context in which it is used. Perhaps a better method name will suggest itself?

Having said that, a templated explicit typecast to integral might be plausible; as it seems reasonable that, in situations where it makes sense to cast away from OverflowSafeInt, the data type required for the correct result should be obvious.

src/script/squirrel_helper.hpp Outdated Show resolved Hide resolved
src/script/squirrel_helper.hpp Outdated Show resolved Hide resolved
This fixes, unmasks, and generally avoids a whole class of bugs where
an `OverflowSafeInt` is implicitly typecast to a regular int and used
in calculations.
Allow copy-construction of OverflowSafeInt from any overflow-safe
or non-overflow-safe integral value.

Allow comparison to any overflow-safe or non-overflow-safe integral
to produce correct results.

Allow mixed arithmetic with other overflow-safe or non-overflow-safe
integrals with sensible automatic promotion or widening.
@techgeeknz
Copy link
Contributor Author

Now that the program actually compiles under MSVC and the regression tests pass, I'm more than happy to address any concerns you may have with the RawValue() method and any other code quality issues.

Allow OverflowSafeInt to be explicitly typecast to any integral
type. The value is clamped to fit within the range of the target
integral type.
@techgeeknz
Copy link
Contributor Author

Having said that, a templated explicit typecast to integral might be plausible; as it seems reasonable that, in situations where it makes sense to cast away from OverflowSafeInt, the data type required for the correct result should be obvious.

Hmm, I'm not convinced this is better. What are your thoughts, @LordAro?

@techgeeknz techgeeknz marked this pull request as draft September 2, 2020 06:31
@techgeeknz
Copy link
Contributor Author

techgeeknz commented Sep 8, 2020

@LordAro would you be more comfortable if I were to separate the bugfixes for the implicit typecasts into a supplimentary pull request; given that it's something that probably should be fixed but leaving them out won't make anything more broken than it already is?

@TrueBrain TrueBrain added needs review: C++ Review requested from a C++ expert candidate: needs considering This Pull Request needs more opinions size: large This Pull Request is large in size; review will take a while labels Dec 14, 2020
@TrueBrain TrueBrain added candidate: yes This Pull Request is a candidate for being merged work: needs more work This Pull Request needs more work before it can be accepted and removed candidate: needs considering This Pull Request needs more opinions needs review: C++ Review requested from a C++ expert labels Dec 29, 2020
@James103
Copy link
Contributor

James103 commented Jul 5, 2021

Is this PR still relevant? The money underflow exploit described in #8284 is fixed in JGRPP 0.42.0 but not in master as of commit 513641f.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
candidate: yes This Pull Request is a candidate for being merged size: large This Pull Request is large in size; review will take a while work: needs more work This Pull Request needs more work before it can be accepted
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Negating or taking absolute values of maximally-negative OverflowSafeInt may result in undefined behaviour
6 participants