fuzz: keep coins_view fuzzers within caller contracts#34655
fuzz: keep coins_view fuzzers within caller contracts#34655achow101 merged 4 commits intobitcoin:masterfrom
coins_view fuzzers within caller contracts#34655Conversation
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. ReviewsSee the guideline for information on the review process.
If your review is incorrectly listed, please copy-paste ConflictsReviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first. |
| expected_code_path = true; | ||
| const bool check_for_overwrite{transaction.IsCoinBase() || fuzzed_data_provider.ConsumeBool() || [&] { | ||
| for (uint32_t i{0}; i < transaction.vout.size(); ++i) { | ||
| if (coins_view_cache.PeekCoin(COutPoint{transaction.GetHash(), i})) return true; |
There was a problem hiding this comment.
It's slightly unfortunate that this requires correctness of PeekCoin in order for the test to be meaningful; ideally the fuzzing harness itself knows whether it's a potential overwrite. However, since coinscache_sim already uses such an approach, this seems fine here.
There was a problem hiding this comment.
Yes, added
bitcoin/src/test/fuzz/coinscache_sim.cpp
Lines 312 to 317 in 67c0d17
Introduce `TrySub(T&, U)` which subtracts an unsigned integral `U` from an unsigned integral `T`, returning `false` on underflow.
Use with `Assume(TrySub(...))` at coins cache accounting decrement sites so invariant violations fail immediately rather than silently wrapping.
Co-authored-by: MarcoFalke <*~=`'#}+{/-|&$^[email protected]>
Co-authored-by: Pieter Wuille <[email protected]>
In validation, `AddCoins(check_for_overwrite=false)` is only used after BIP30 has already ensured the transaction does not overwrite any unspent outputs in the UTXO view. The coins view fuzz target can call `AddCoins` with arbitrary txids, so using the `check_for_overwrite=false` fast path on non-coinbase transactions may violate the `AddCoin` caller contract and trigger logic errors. Only use `check_for_overwrite=false` when we have first confirmed that none of the outputs are currently unspent. Otherwise, fall back to `check_for_overwrite=true` so `AddCoins` determines overwrites via the view.
The coins view fuzzer can call `AddCoin` with `possible_overwrite=false` for an outpoint that already exists unspent in the view, which violates the `AddCoin` caller contract. Derive `possible_overwrite` from `PeekCoin` so `possible_overwrite=false` is only used when the outpoint is absent. This matches the approach used by the `coinscache_sim` fuzzer, which derives the overwrite flag from simulated state.
Modify fuzzer logic to avoid setting `FRESH` for an outpoint that already exists unspent in the parent view, and ensure `FRESH` implies `DIRTY`. This keeps cursor invariants realistic and lets `BatchWrite` failures expose real bugs without resetting state.
l0rinc
force-pushed
the
l0rinc/coins_view_fuzzer_cleanup
branch
from
a8e6c5f to
3281824
Compare
| } | ||
|
|
||
| template <std::unsigned_integral T, std::unsigned_integral U> | ||
| [[nodiscard]] constexpr bool TrySub(T& i, const U j) noexcept |
There was a problem hiding this comment.
Very nitty, but:
- I think the name is slightly misleading, as there is no reason why subtracting would ever fail on an unsigned type, so it is not clear what is being "tried". The name should suggest that it avoids wraparound.
- It's unfortunate that this has a runtime impact even outside fuzzing. It's obviously fine within the context of this PR (nothing in it is that performance critical), but in that context just
Assume(x >= y); x -= y;is fine too. If we're introducing this as a new generic utility function that's usable anywhere, I thinkbool ret = i >= T{j}; i -= T{j}; return ret;is nicer, because in contexts where the return value is ignored, it is exactly equivalent to just a subtraction, and may be optimized to it.
There was a problem hiding this comment.
no reason why subtracting would ever fail on an unsigned type
TrySub is meant as "try to subtract without wraparound": if i < j, it leaves i unchanged (hence the Try prefix) and returns false, so callers can act.
It's unfortunate that this has a runtime impact even outside fuzzing
I think bool ret = i >= T{j}; i -= T{j}; return ret; is nicer, because in contexts where the return value is ignored, it is exactly equivalent to just a subtraction
Do we want to be exactly equivalent though?
The current cheap branching prevents the accounting counters from wrapping, so even if accounting is wrong elsewhere, the values stay closer to what we expect.
I have tried a few variants to see the effect of the change (plain subtraction vs return + internal Assume vs mutating TrySub + caller Assume with [[unlikely]]), see https://godbolt.org/z/nf9nT9Mjj
Details
Both compilers emit the same single subtract (plus the bool zero-extend in the bool case).
For example, GCC:
sub_return_size:
sub QWORD PTR [rdi], rsi
retand for bool:
sub_return_bool:
movzx esi, sil
sub QWORD PTR [rdi], rsi
retSo return + internal Assume has zero codegen cost in non-abort builds, and adding [[unlikely]] doesn't seem to change anything there either.
Result 2: Only the mutating TrySub variant changes semantics (avoids wrap), and it necessarily adds a branch. [[unlikely]] didn't change codegen here either.
GCC (size_t case):
sub_trysub_size:
mov rax, QWORD PTR [rdi]
cmp rax, rsi
jb .Lskip
sub rax, rsi
mov QWORD PTR [rdi], rax
.Lskip:
retclang emits the same idea, just as sub then jb then store:
sub_trysub_size:
mov rax, qword ptr [rdi]
sub rax, rsi
jb .Lskip
mov qword ptr [rdi], rax
.Lskip:
ret…and the sub_trysub_unlikely_* versions were identical to sub_trysub_* for both compilers (so [[unlikely]] doesn't seem to buy anything here either; the cold path is already the taken jump).
Note: I have experimented a bit with __builtin_sub_overflow(), it does change GCC codegen slighly to the same sub; jb shape clang already emits (removing the explicit cmp), but I’m not sure it’s an actual win, so I’ll leave it for a follow-up.
There was a problem hiding this comment.
(this is all very nitty, and no reason to hold up this PR)
TrySub is meant as "try to subtract without wraparound": if i < j, it leaves i unchanged (hence the Try prefix) and returns false, so callers can act.
Yes, I understand what it does. My point is that this is not clear from the name "TrySub", because it doesn't suggest anything about avoiding wrapping (which is perfectly well-defined behavior on unsigned types).
Do we want to be exactly equivalent though?
If our assumptions are wrong, I don't think we care about what actually happens to the m_dirty_count value, it's going to be meaningless regardless. So I would suggest using whatever is fastest, and I'm guessing that x -= y; is faster than if (x >= y) x -= y;.
|
ACK 3281824 |
andrewtoth
left a comment
andrewtoth
left a comment
There was a problem hiding this comment.
ACK 3281824
Fuzzed coins_view_overlay overnight with no issues.
| } | ||
| // Avoid setting FRESH for an outpoint that already exists unspent in the parent view. | ||
| bool fresh{!coins_view_cache.PeekCoin(random_out_point) && fuzzed_data_provider.ConsumeBool()}; | ||
| bool dirty{fresh || fuzzed_data_provider.ConsumeBool()}; |
There was a problem hiding this comment.
nit: I think this is backwards. fresh is dependent on dirty, not vice versa. See 797fcc4.
I also don't think this change to dirty is relevant to the fix here. We only need to gate fresh on PeekCoin. The exception being thrown is not relevant to FRESH-but-not-DIRTY. It's actually reducing coverage here.
There was a problem hiding this comment.
I don't have the capacity at the moment to react to this in detail.
Is this important to do it here, or do you think we can tackle it independently in #33018?
There was a problem hiding this comment.
This isn't a blocker. The change here fixes the linked issue.
6 participants
Problem
This is an alternative approach to #34647, fixes #34645.
Fix
First, add
CheckedSuband use it for decrements ofm_dirty_countandcachedCoinsUsage, so unsigned underflows turn into immediate failures instead of silently wrapping and only failing later.Assertion `j <= i' failed.
The coins view fuzz targets can call
AddCoin/AddCoinsand constructBatchWritecursors in ways that violateCCoinsViewCachecaller contracts. These invalid states can triggerBatchWritestd::logic_errorand can desync dirty-entry accounting (caught byAssume(m_dirty_count == 0)currently).Make the fuzzer avoid generating invalid states instead of catching and resetting:
AddCoin’spossible_overwritefromPeekCoin, sopossible_overwrite=falseis only used when the outpoint is absent - similarly tobitcoin/src/test/fuzz/coinscache_sim.cpp
Lines 312 to 317 in 67c0d17
AddCoins(check=false)when we have confirmed the txid has no unspent outputs; otherwise fall back tocheck=truesoAddCoinsdetermines overwrites via the view.CoinsViewCacheCursor, avoid settingFRESHwhen the parent already has an unspent coin, and ensureFRESHimpliesDIRTY.Fuzzing
The original error could be reproduced in ~10 minutes using
coins_view_overlay. I ran thecoins_view,coins_view_db,coins_view_overlay, andcoinscache_simfuzzers for this PR overnight and they didn't fail anymore.