Opened 5 months ago

Closed 25 hours ago

#30920 closed defect (fixed)

Detect uint64 overflow in config_parse_units()

Reported by: nickm Owned by:
Priority: Low Milestone: Tor: 0.4.3.x-final
Component: Core Tor/Tor Version:
Severity: Minor Keywords: easy overflow extra-review
Cc: Actual Points: 0.2
Parent ID: Points:
Reviewer: teor, nickm Sponsor:

Description

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.

Child Tickets

Change History (38)

comment:1 Changed 5 months ago by nickm

Keywords: easy overflow added

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

comment:2 Changed 5 months ago by teor

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.)

comment:3 Changed 5 months ago by guigom

I would like to volunteer on this one once #30864 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.

comment:4 Changed 5 months ago by teor

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

comment:5 in reply to:  4 Changed 5 months ago by guigom

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!

comment:6 Changed 5 months ago by 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?

comment:7 in reply to:  6 ; Changed 5 months ago by teor

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 and #30864.

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.

comment:8 in reply to:  7 Changed 4 months ago by guigom

Replying to teor:

Hi teor, #30864 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?

comment:9 Changed 4 months ago by 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.

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.

comment:10 in reply to:  9 ; Changed 8 weeks ago by 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.

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.

comment:11 in reply to:  10 ; Changed 8 weeks ago by teor

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.

comment:12 in reply to:  11 ; Changed 8 weeks ago by 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

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.

comment:13 in reply to:  12 ; Changed 8 weeks ago by teor

Milestone: Tor: 0.4.2.x-finalTor: 0.4.3.x-final

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 263 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.

comment:14 in reply to:  13 Changed 8 weeks ago by guigom

comment:15 Changed 8 weeks ago by 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.

Last edited 8 weeks ago by guigom (previous) (diff)

comment:16 in reply to:  15 ; Changed 7 weeks ago by teor

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 231 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.)

comment:17 Changed 7 weeks ago by teor

Reviewer: teor
Status: newneeds_revision

comment:18 in reply to:  16 Changed 4 weeks ago by guigom

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.

Last edited 4 weeks ago by guigom (previous) (diff)

comment:19 Changed 4 weeks ago by nickm

Status: needs_revisionneeds_review

comment:20 Changed 4 weeks ago by teor

Status: needs_reviewneeds_revision

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

comment:21 in reply to:  20 Changed 4 weeks ago by guigom

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.

Last edited 4 weeks ago by guigom (previous) (diff)

comment:22 Changed 4 weeks ago by 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 263), but will fail the int check because (uint64_t)d, which is 263, is strictly greater than 263-1 (INT64_MAX)

Last edited 4 weeks ago by guigom (previous) (diff)

comment:23 Changed 4 weeks ago by teor

Actual Points: 0.2
Status: needs_revisionmerge_ready

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

comment:24 Changed 4 weeks ago by nickm

Status: merge_readyneeds_revision

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

comment:25 in reply to:  24 Changed 4 weeks ago by guigom

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();
}

comment:26 Changed 4 weeks ago by nickm

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

comment:27 Changed 4 weeks ago by nickm

(See the comments on the PR for more information)

comment:28 in reply to:  27 Changed 4 weeks ago by guigom

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!

comment:29 Changed 4 weeks ago by nickm

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

comment:30 Changed 4 weeks ago by guigom

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

comment:31 Changed 2 weeks ago by teor

Is this ready for another review?

comment:32 Changed 2 weeks ago by guigom

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

comment:33 Changed 2 weeks ago by teor

Keywords: extra-review added
Reviewer: teorteor, nickm

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,

comment:34 in reply to:  33 Changed 2 weeks ago by guigom

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.

comment:35 Changed 31 hours ago by 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.

comment:36 Changed 29 hours ago by nickm

Status: needs_revisionneeds_review

comment:37 Changed 25 hours ago by nickm

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

comment:38 Changed 25 hours ago by nickm

Resolution: fixed
Status: needs_reviewclosed
Note: See TracTickets for help on using tickets.