fuzz: Improve stability for txorphan and mini_miner harnesses #30306

pull dergoegge wants to merge 1 commits into bitcoin:master from dergoegge:2024-06-itercomp-stab changing 2 files +2 −2

dergoegge commented at 9:17 AM on June 19, 2024: member

See #29018.

Stability for txorphan is now >90%. mini_miner needs further investigation, stability still low (although slightly improved by this PR) at ~62%.

Don't use iterator addresses in IteratorComparator

The addresses of the iterator values are non-deterministic (i.e. they
depend on where the values were allocated). This causes stability issues
when fuzzing (e.g. in the `txorphan` and `mini_miner` harnesses), due
the orders (derived from IteratorComparator) not being deterministic.

Improve stability by comparing the first element in the iterator value
pair instead of using the the value addresses.

e009bf681c

DrahtBot commented at 9:17 AM on June 19, 2024: contributor



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



Code Coverage

For detailed information about the code coverage, see the test coverage report.



Reviews

See the guideline for information on the review process.

Type Reviewers

ACK marcofleon, glozow

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.
DrahtBot added the label Tests on Jun 19, 2024
in src/node/mini_miner.h:66 in e009bf681c
```
  62 | @@ -63,7 +63,7 @@ struct IteratorComparator
  63 |      template<typename I>
  64 |      bool operator()(const I& a, const I& b) const
  65 |      {
  66 | -        return &(*a) < &(*b);
  67 | +        return a->first < b->first;
```
maflcko commented at 9:47 AM on June 19, 2024:

Can you explain this a bit more? IIUC the entries/iterators are pushed into a vector, so the order should be deterministic, no? If not, maybe the order should be made deterministic? Otherwise, the hot-loop may of calculating the ancestor set may take a longer time due to having to compare more memory (pointer vs uint256)?
dergoegge commented at 10:04 AM on June 19, 2024:

For both MiniMiner and TxOrphange, IteratorComparator is used for a std::set that holds iterators into a std::map. I don't know how std::map allocates memory internally but it doesn't seem to be one continuous vector.

The stability for txorphan definitely goes up by this change:

master: http://bitcoind-fuzz.dergoegge.de:8000/bitcoin/harnesses/txorphan/stats.txt

PR: http://bitcoind-fuzz.dergoegge.de:8000/bitcoin-itercomp/harnesses/txorphan/stats.txt

(the first column indicates afll+'s stability metric, these links will stop working at some point)
maflcko commented at 10:12 AM on June 19, 2024:

Ah sorry. I was confused by std::vector<MockEntryMap::iterator> m_entries;, but the iterator isn't into the vector, but into the map itself. Discussion can be closed.

maflcko commented at 10:14 AM on June 19, 2024:

(the first column indicates afll+'s stability metric, these links will stop working at some point)

Nice. If you don't mind, could share the steps to create the stats.txt file?

dergoegge commented at 10:23 AM on June 19, 2024:

It's part of the output from my fuzzing setup, which is closed source atm.

However, measuring stability is easily possible by just running afll++.
in src/txorphanage.h:95 in e009bf681c
```
  91 | @@ -92,7 +92,7 @@ class TxOrphanage {
  92 |          template<typename I>
  93 |          bool operator()(const I& a, const I& b) const
  94 |          {
  95 | -            return &(*a) < &(*b);
  96 | +            return a->first < b->first;
```
maflcko commented at 9:53 AM on June 19, 2024:

I wonder if the set could just be made a vector, because duplicates shouldn't happen?

dergoegge commented at 10:21 AM on June 19, 2024:

Maybe but this sounds like more effort than I wanted to spend on this.

I don't think the comparison change here is gonna have any noticeable impact on performance tbh. In most cases the first 8 byte of the txids are already gonna differ, so the performance should be similar to comparing the pointers (assuming 8 byte addresses) most of the time.
maflcko commented at 9:53 AM on June 19, 2024: member

left some questions
marcofleon commented at 12:20 PM on June 20, 2024: contributor

Tested ACK e009bf681c0e38a6451afa594ba3c7c8861f61c3. Using afl++, stability for txorphan went from 82% to ~94% and for mini_miner it went from 84% to 97%. I ran them both using the corpora in qa-assets.
glozow commented at 7:45 AM on July 1, 2024: member

utACK e009bf681c0e38a6451afa594ba3c7c8861f61c3

Didn't check stability, but using txid seems fine.
fanquake merged this on Jul 1, 2024
fanquake closed this on Jul 1, 2024
Fabcien referenced this in commit 0fafd7b709 on Jul 19, 2024
roqqit referenced this in commit 0d319003dd on Aug 1, 2024
bitcoin locked this on Jul 1, 2025

Type	Reviewers
ACK	marcofleon, glozow

Contributors

Labels

Linked (view graph)

#29018 fuzz: Fix stability, determinism issues

fuzz: Improve stability for txorphan and mini_miner harnesses #30306

Code Coverage

Reviews