Detect uint64 overflow in config_parse_units()

The config_parse_units function uses 64-bit arithmetic, but does not detect 64-bit overflow. This means that values like "20000000 TB", which should be rejected, are instead mis-parsed.

Since this function is only used for configuration parsing, it's not a huge issue, but it should be simple enough to resolve this.

Found while working on 30893.

changed milestone to %Tor: 0.4.3.x-final in legacy/trac

added actualpoints::0.2 in Legacy / Trac component::core tor/tor in Legacy / Trac easy in Legacy / Trac extra-review in Legacy / Trac milestone::Tor: 0.4.3.x-final in Legacy / Trac overflow in Legacy / Trac priority::low in Legacy / Trac resolution::fixed in Legacy / Trac reviewer::nickm in Legacy / Trac reviewer::teor in Legacy / Trac severity::minor in Legacy / Trac status::closed in Legacy / Trac type::defect in Legacy / Trac labels

(If you want to work on this, wait until legacy/trac#30864 (moved) is merged -- that branch moves all this code and adds some unit tests.)

Trac:
Keywords: N/A deleted, easy overflow added

It would be great to have a generic 64-bit multiplication overflow function in: https://gitweb.torproject.org/tor.git/tree/src/lib/intmath/muldiv.c

It should look like the overflow checking function in: https://gitweb.torproject.org/tor.git/tree/src/lib/intmath/addsub.c

But with a note that division is expensive on some platforms. (Which doesn't matter for a once-off config parse.)

I would like to volunteer on this one once legacy/trac#30864 (moved) is merged, if possible.

Here is a code snippet for the overflow check multiplication. (Assuming a and b values are correct)

uint64_t
tor_mul_u64_nowrap(uint64_t a, uint64_t b)
{
  if (PREDICT_UNLIKELY(UINT64_MAX / a < b)) {
   return UINT64_MAX;
  } else {
    return a*b;
  }
}

Adding the function header in muldiv.h too.

Trac:
Username: guigom

Thanks for offering to help out. That code looks good.

We'll also need some unit tests.

Do you use git? We accept pull requests on GitHub, or send us the URL of your git repository.

If you can add a changes file, that would also be helpful: https://gitweb.torproject.org/tor.git/tree/doc/HACKING/CodingStandards.md#n95

Replying to teor:

Thanks for offering to help out. That code looks good.

Thank you.

We'll also need some unit tests.

I will be reading https://gitweb.torproject.org/tor.git/tree/doc/HACKING/WritingTests.md first as I need to understand how to properly implement unit test for the tor project.

Do you use git? We accept pull requests on GitHub, or send us the URL of your git repository.

I'll post the link to the PR once submitted.

If you can add a changes file, that would also be helpful: https://gitweb.torproject.org/tor.git/tree/doc/HACKING/CodingStandards.md#n95

Sure!

Trac:
Username: guigom

Is the unit test expected to be inside test_confparse.c testing config_parse_units() ?

Or create a separate test file that just tests the new multiplication in, for example, test_muldiv.c

Or both?

Trac:
Username: guigom

Replying to guigom:

Is the unit test expected to be inside test_confparse.c testing config_parse_units() ?

I think Nick will do that test in legacy/trac#30893 (moved) and legacy/trac#30864 (moved).

Or create a separate test file that just tests the new multiplication in, for example, test_muldiv.c

Just the new function is fine.

The addsub tests are in test_util.c, so the muldiv tests can go in there as well.

Replying to teor:

Hi teor, legacy/trac#30864 (moved) has been merged and I have a couple of questions.

Nick added a couple of commented out tests in which it is expected for config_parse_memunit (and thus config_parse_units) to return 0 instead of UINT64_MAX when detecting 64-bit overflow.

// tt_u64_op(config_parse_memunit("20000000 TB", &ok), OP_EQ, 0);
// tt_assert(!ok);

Is this the expected behavior, or should it fallback to UINT64_MAX?

---

In case of using the nowrap mul function inside unitparse.c:config_parse_units

make check-includes tells that it is forbidden to include muldiv.h inside unitparse.c

Should lib/intmath/*.h be appended to confmgt .may_include?

Trac:
Username: guigom

Is this the expected behavior, or should it fallback to UINT64_MAX?

I think that's a better behavior for config_parse_memunit(). In the case of config_parse_memunit(), it's better that the user be told about the problem than to have us silently ignore their request.

Should lib/intmath/*.h be appended to confmgt .may_include?

Yes, that's fine. The purpose of .may_include is to make sure that low-level modules don't include headers from high-level modules, and lib/intmath is a nice low-level module.

First of all, sorry for the late reply

Replying to nickm:

Is this the expected behavior, or should it fallback to UINT64_MAX?

I think that's a better behavior for config_parse_memunit(). In the case of config_parse_memunit(), it's better that the user be told about the problem than to have us silently ignore their request.

Understood, in that case is it ok to detect overflow inside config_parse_memunit() by check if nowrap_multiplication yielded UINTMAX_64? It seems quite strange in my opinion to specify such value explicitly.

In addition to that I'm not sure if float multiplication should be handled as well or this ticket should just focus on unsigned integer.

Trac:
Username: guigom

Replying to guigom:

First of all, sorry for the late reply

Replying to nickm:

Is this the expected behavior, or should it fallback to UINT64_MAX?

I think that's a better behavior for config_parse_memunit(). In the case of config_parse_memunit(), it's better that the user be told about the problem than to have us silently ignore their request.

Understood, in that case is it ok to detect overflow inside config_parse_memunit() by check if nowrap_multiplication yielded UINTMAX_64? It seems quite strange in my opinion to specify such value explicitly.

Maybe we should fail on anything larger than SSIZE_T_MAX? (SSIZE_T_MAX is half the maximum possible memory size.)

In addition to that I'm not sure if float multiplication should be handled as well or this ticket should just focus on unsigned integer.

No, we don't have any critical code that uses float multiplication.

I haven't opened a PR yet but my branch for this ticket is in [https://github.com/JMGuisadoG/tor/tree/ticket30920]

• Commit adding the u64_nowrap_mul & tests: [https://github.com/JMGuisadoG/tor/commit/4dd5b593636a9f5944ca2069d1c22c2b4b03d335]

• Commit adding the check for overflow inside mem_parse_units & enabling tests: [https://github.com/JMGuisadoG/tor/commit/1ac4b346131fa0f49a5218553cd5d98affb82a76]

Replying to teor:

Maybe we should fail on anything larger than SSIZE_T_MAX? (SSIZE_T_MAX is half the maximum possible memory size.)

What the reason for checking half the maximum size?.

If that's a go and there's no problem with the code above I can change the if statement accordingly.

Trac:
Username: guigom

Replying to guigom:

I haven't opened a PR yet but my branch for this ticket is in [https://github.com/JMGuisadoG/tor/tree/ticket30920]

• Commit adding the u64_nowrap_mul & tests: [https://github.com/JMGuisadoG/tor/commit/4dd5b593636a9f5944ca2069d1c22c2b4b03d335]

• Commit adding the check for overflow inside mem_parse_units & enabling tests: [https://github.com/JMGuisadoG/tor/commit/1ac4b346131fa0f49a5218553cd5d98affb82a76]

Thanks!

Replying to teor:

Maybe we should fail on anything larger than SSIZE_T_MAX? (SSIZE_T_MAX is half the maximum possible memory size.)

What the reason for checking half the maximum size?.

In general, it helps us avoid underflows and other mistakes as well.

In this case, there's just no reason to expect that values over 2^63^ are valid.

If that's a go and there's no problem with the code above I can change the if statement accordingly.

Sure, feel free to put in a pull request, and someone will review it in the next week.

Trac:
Milestone: Tor: 0.4.2.x-final to Tor: 0.4.3.x-final

Leaving the PR link here: https://github.com/torproject/tor/pull/1338

Trac:
Username: guigom

The SSIZE_MAX part may be interfering with 64bit arithmetic in 32bit machines as seen in this error in AppVeyor build.

[https://ci.appveyor.com/project/torproject/tor/builds/27495711/job/049andnqliomgw0u#L6029]

Tomorrow (CEST) I'll test with UINT64_MAX.

Trac:
Username: guigom

Replying to guigom:

The SSIZE_MAX part may be interfering with 64bit arithmetic in 32bit machines as seen in this error in AppVeyor build.

[https://ci.appveyor.com/project/torproject/tor/builds/27495711/job/049andnqliomgw0u#L6029]

Tomorrow (CEST) I'll test with UINT64_MAX.

You're right, SSIZE_MAX is 2^31^ on 32-bit platforms, which would be a valid value for bandwidth on 32-bit machines. And memory on machines that allow processes to take up more than 2 GB.

Let's check that the value is less than INT64_MAX? And let's check the result of the float multiplication, before we cast it to a uint64_t. (We want to use a value that's significantly lower than UINT64_MAX, so that floating point calculations can't change the result.)

Trac:
Reviewer: N/A to teor
Status: new to needs_revision

I've updated the PR.

Replying to teor:

Let's check that the value is less than INT64_MAX? And let's check the result of the float multiplication, before we cast it to a uint64_t. (We want to use a value that's significantly lower than UINT64_MAX, so that floating point calculations can't change the result.)

Not sure if I got it right, waiting for an OK because I ended up writing the same block for the float as the uint case.

INT64_MAX use_float before casting check: [https://github.com/torproject/tor/pull/1338/commits/f3808a76af437747385c719a877f214284d88067#diff-3ae70660df167ed2300a9455223be6a9R149]

Sorry this is taking this much time. It's been hard finding some free time lately, sorry for any inconvenience.

EDIT: Seems normal float parse tests are failing. I'll have a look. EDIT2: Fix pushed. Waiting for build test to finish.

Trac:
Username: guigom