feefrac: avoid integer overflow in temporary

sipa commented at 5:59 pm on April 17, 2025: member

In FeeFrac::Div(__int128 n, int32_t d, bool round_down) in src/util/feefrac.h, the following line computes the result:

0        return quot + (mod > 0) - (mod && round_down);

The function can only be called under conditions where the result is in range, and thus doesn’t involve any integer overflow. However, the intermediary result computed by just quot + (mod > 0) may still overflow if it’s going to be corrected by the - (mod && round_down) that follows.

Fix this by balancing the two correction steps with each other first:

0        return quot + ((mod > 0) - (mod && round_down));

Fixes #32294.

DrahtBot commented at 5:59 pm on April 17, 2025: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32300.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	l0rinc, maflcko, achow101
Stale ACK	1440000bytes

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

maflcko commented at 6:06 pm on April 17, 2025: member

the intermediary result computed by just quot + (mod > 0) may still overflow if it’s going to be corrected by the - (mod && round_down) that follows.

How will it be corrected if rounding up?

sipa commented at 6:08 pm on April 17, 2025: member

How will it be corrected if rounding up?

In that case, quot + (mod > 0) cannot overflow (if it did, the result isn’t in range of int64_t, and the function would not be allowed to be called).

1440000bytes commented at 6:13 pm on April 17, 2025: none

ACK https://github.com/bitcoin/bitcoin/pull/32300/commits/6dd574444598240d2622e06e402548312123e5ef

Code and motivation looks good. I couldn’t find any instance of such changes to introduce bug.

maflcko commented at 6:16 pm on April 17, 2025: member

review ACK 6dd574444598240d2622e06e402548312123e5ef

in src/util/feefrac.h:99 in 6dd5744445 outdated

 95@@ -96,7 +96,7 @@ struct FeeFrac
 96         int64_t quot = n / d;
 97         int32_t mod = n % d;
 98         // Correct result if the / operator above rounded in the wrong direction.
 99-        return quot + (mod > 0) - (mod && round_down);
100+        return quot + ((mod > 0) - (mod && round_down));

l0rinc commented at 6:17 pm on April 17, 2025:

The new code:

0quot + ((mod > 0) - (mod && round_down));

Compiles to

0test    eax, eax
1setne   al
2setg    bl
3movzx   eax, al
4and     eax, ecx
5*sub     ebx, eax*
6movsx   rbx, ebx
7*add     rbx, rdx*

(- before +)

while the old one:

0quot + (mod > 0) - (mod && round_down);

Compiles to

0test    eax, eax
1setg    bl
2*add     rbx, rcx*
3test    eax, eax
4setne   al
5movzx   eax, al
6and     rax, rdx
7*sub     rbx, rax*

(+ before -)

The original suggestion also had the subtraction first: #30535 (review)

sipa commented at 6:47 pm on April 17, 2025:

I don’t think the compiled result matters, because mathematically, both the old and new code are identical (for any input for which the code is well defined). Both assembly listings are correct compilations of both source code versions.

Also, I think that just quot - (mod && round_down) + (mod > 0) would suffer from an identical but opposite problem: if quot is the minimum valid int64_t, and both (mod && round_down) and (mod > 0) are true, you’d get an underflow.

l0rinc commented at 6:57 pm on April 17, 2025:

Given that this tricked most of us, would it make sense to cover it with unit tests which demonstrate the behavior difference before/after?

sipa commented at 6:59 pm on April 17, 2025:

Yeah I think that makes sense, so we don’t have to rely on the fuzz corpus.

l0rinc commented at 7:54 pm on April 17, 2025:

The simplest way I could find is to call it directly (not sure what the fuzzer did, don’t have access):

 0BOOST_AUTO_TEST_CASE(feefrac_div_round_down_overflow)
 1{
 2#ifdef __SIZEOF_INT128__
 3    constexpr auto divisor{2};
 4    constexpr auto expected_result{std::numeric_limits<int64_t>::max()};
 5    constexpr auto overflow_numerator{__int128{expected_result} * divisor + 1};
 6    BOOST_CHECK_EQUAL(FeeFrac::Div(overflow_numerator, divisor, /*round_down=*/true), expected_result);
 7#else
 8    BOOST_TEST_MESSAGE("Skipped");
 9#endif
10}

Which fails before the change with:

cmake -B build -DCMAKE_BUILD_TYPE=Debug && cmake –build build -j$(nproc) && build/bin/test_bitcoin –run_test=‘feefrac_tests/feefrac_div_round_down_overflow’ … Running 1 test case… Trace/BPT trap: 5

maflcko commented at 8:07 pm on April 17, 2025:

(not sure what the fuzzer did, don’t have access):

The issue I created includes the base64 encoded file that the fuzz engine on oss-fuzz produced

sipa commented at 9:21 pm on April 17, 2025:

I have added this in the unit tests:

0    // Test for integer overflow issue (https://github.com/bitcoin/bitcoin/issues/32294)
1    BOOST_CHECK_EQUAL(FeeFrac{0x7ffffffdfffffffb, 0x7ffffffd}.EvaluateFeeDown(0x7fffffff), 0x7fffffffffffffff);

l0rinc commented at 9:34 pm on April 17, 2025:

0BOOST_CHECK_EQUAL((FeeFrac{0x7ffffffdfffffffb, 0x7ffffffd}.EvaluateFeeDown(0x7fffffff)), 0x7fffffffffffffff);

This works for me in simple Debug mode (with extra parentheses). Before the fix this also fails with the following (built without sanitizers, doesn’t fail in Release mode):

cmake -B build -DCMAKE_BUILD_TYPE=Debug && cmake –build build -j$(nproc) && time build/bin/test_bitcoin –run_test=‘feefrac_tests/feefrac_operators’ … Running 1 test case… zsh: trace trap

maflcko commented at 6:21 am on April 18, 2025:

Before the fix this also fails with the following (built without sanitizers, doesn’t fail in Release mode):

That’s -ftrapv, added in 2643fa50869f22672cbc72ac497d9c30234075b8

l0rinc approved

l0rinc commented at 6:43 pm on April 17, 2025: contributor

ACK 6dd574444598240d2622e06e402548312123e5ef

If you think it’s useful, we could hard code the behavior via a unit test based on the fuzz finding

sipa force-pushed on Apr 17, 2025

feefrac: avoid integer overflow in temporary 5cb1241814

sipa force-pushed on Apr 17, 2025

DrahtBot added the label CI failed on Apr 17, 2025

DrahtBot commented at 9:37 pm on April 17, 2025: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/40754617437

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

l0rinc commented at 9:38 pm on April 17, 2025: contributor

Tested ACK 5cb1241814b9c541c5e5e8daadbbea595f2960ae

DrahtBot requested review from 1440000bytes on Apr 17, 2025

DrahtBot requested review from maflcko on Apr 17, 2025

DrahtBot removed the label CI failed on Apr 18, 2025

maflcko commented at 6:22 am on April 18, 2025: member

lgtm ACK 5cb1241814b9c541c5e5e8daadbbea595f2960ae

achow101 commented at 10:24 pm on April 18, 2025: member

ACK 5cb1241814b9c541c5e5e8daadbbea595f2960ae

achow101 merged this on Apr 18, 2025

achow101 closed this on Apr 18, 2025

feefrac: avoid integer overflow in temporary #32300

Code Coverage & Benchmarks

Reviews