Detect uint64 overflow in config_parse_units()

changed milestone to %Tor: 0.4.3.x-final

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

(If you want to work on this, wait until #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 #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 #30893 (moved) and #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, #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

Trac:
Status: needs_revision to needs_review

Just missing a floating point check, and some floating-point tests.

Trac:
Status: needs_review to needs_revision

Replying to teor:

Just missing a floating point check, and some floating-point tests.

Thank you for your suggestions Teor.

Updated with a couple floating point tests. But probably not ok, see edit.

Edit: I think I will need some more time to read about integer representation of floating point numbers in order to understand why I'm choosing a particular number for the test and avoid just trying out numbers.

Trac:
Username: guigom

Hi Teor.

I've updated the PR with a couple of tests, one that fails the double check and one that passes double but fails int check.

Reasoning:

// Fails double check // 15000000.5 TB fails double check as its a greater floating number than (double)INT64_MAX

// Passes double check but fails int check //
8388608.1 TB passes double check because it falls in the same value as (double)INT64_MAX (which is 2^63^), but will fail the int check because (uint64_t)d, which is 2^63^, is strictly greater than 2^63^-1 (INT64_MAX)

Trac:
Username: guigom

Looks good to me, but I'd like someone else to also do a review,

Trac:
Status: needs_revision to merge_ready
Actualpoints: N/A to 0.2

Looks good to me too. It just needs some documentation updates and (I think) a sign check.

Trac:
Status: merge_ready to needs_revision

Replying to nickm:

Looks good to me too. It just needs some documentation updates and (I think) a sign check.

Which documentation specifically? torrc options in the man page?

About the sign check (if I understand correctly, checking if possitive), is this because tor_parse_double does not indeed use the min parameter? Wouldn't the bit sign for negative numbers end up giving a uint representation greater than INT64_MAX thus failing the uint check?

double
tor_parse_double(const char *s, double min, double max, int *ok, char **next)
{
  char *endptr;
  double r;

  errno = 0;
  r = strtod(s, &endptr);
  CHECK_STRTOX_RESULT();
}

Trac:
Username: guigom

Err, sorry -- I mentioned the sign check and the documentation on the pull request, but I forgot to say so here.

(See the comments on the PR for more information)

Replying to nickm:

(See the comments on the PR for more information)

Hi Nick. I've looked in the PR and found no comments from you. Just checking that I'm not missing anything. Thank you in advance!

Trac:
Username: guigom

Oh no! It looks like I didn't hit the "submit review" button. I'm sorry about that; can you see the comments now?

No problem! I can see the comments now :-)

Trac:
Username: guigom

Is this ready for another review?

Yes! Sorry that I forgot to mention it here. Updated yesterday.

Trac:
Username: guigom

We need to fail on negative multipliers, because the function returns an unsigned integer. I've added a suggestion on the pull request.

Once that is applied, I think we can merge, but I'd like nickm to do a final review before we merge,

Trac:
Keywords: easy overflow deleted, easy overflow extra-review added
Reviewer: teor to teor, nickm

Replying to teor:

We need to fail on negative multipliers, because the function returns an unsigned integer. I've added a suggestion on the pull request.

Once that is applied, I think we can merge, but I'd like nickm to do a final review before we merge,

I've submitted the change and added a negative float test so everything is covered.

Trac:
Username: guigom

Hi! I haven't received any update for two weeks and just wanted to check on this, knowing its low priority.

Thanks Teor and Nick for your time and suggestions.

Trac:
Username: guigom

Trac:
Status: needs_revision to needs_review

Sorry for the delay! This looks good now. I've merged, with some light grammar edits in 3d1a7d7dd7e10b.

Trac:
Resolution: N/A to fixed
Status: needs_review to closed

closed

added 1h 36m of time spent

moved to tpo/core/tor#30920 (closed)

Detect uint64 overflow in config_parse_units()

Child items 0

Activity