fuzz: Add HeadersSyncState target #26662

dergoegge commented at 2:38 PM on December 8, 2022: member

This adds a fuzz target for the HeadersSyncState class.

I am unsure how well this is able to cover the logic since it is just processing unserialized CBlockHeaders straight from the fuzz input (headers are sometimes made continuous). However, it does manage to get to the redownload phase so i thought it is better then not having fuzzing at all.

It would also be nice to fuzz the p2p logic that is using HeadersSyncState (e.g. TryLowWorkHeadersSync, IsContinuationOfLowWorkHeadersSync) but that likely requires some more work (refactoring👻).

DrahtBot commented at 2:38 PM on December 8, 2022: contributor

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

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	mzumsande

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 Dec 8, 2022

in src/Makefile.test.include:339 in 707d60d9b4 outdated

 335 | @@ -336,6 +336,7 @@ test_fuzz_fuzz_SOURCES = \
 336 |   test/fuzz/tx_pool.cpp \
 337 |   test/fuzz/txorphan.cpp \
 338 |   test/fuzz/txrequest.cpp \
 339 | + test/fuzz/headerssync.cpp \

maflcko commented at 2:49 PM on December 8, 2022:

sort :ghost: ?

in src/test/fuzz/headerssync.cpp:14 in 707d60d9b4 outdated

   9 | +
  10 | +#include <vector>
  11 | +
  12 | +static void initialize_headers_sync_state_fuzz()
  13 | +{
  14 | +    SelectParams("main");

maflcko commented at 2:50 PM on December 8, 2022:

Could use the string constant?

in src/test/fuzz/headerssync.cpp:80 in 707d60d9b4 outdated

  41 | +        std::vector<CBlockHeader> headers;
  42 | +
  43 | +        // Consume headers from fuzzer or maybe replay headers if we got to the
  44 | +        // redownload phase.
  45 | +        if (presync || fuzzed_data_provider.ConsumeBool()) {
  46 | +            auto deser_headers = ConsumeDeserializable<std::vector<CBlockHeader>>(fuzzed_data_provider);

maflcko commented at 2:55 PM on December 8, 2022:

Seems impossible that this produces even a single valid header, because the engine can't guess the prevblock hash, no?

dergoegge commented at 3:36 PM on December 8, 2022:

Good point, fixed it up to be able to create continuous headers.

dergoegge force-pushed on Dec 8, 2022

maflcko commented at 3:54 PM on December 8, 2022: member

Note: If you create a pull request with inputs against qa-assets, Drahty can create a coverage report

dergoegge force-pushed on Dec 8, 2022

DrahtBot commented at 8:10 AM on December 9, 2022: contributor

https://drahtbot.space/host_reports/DrahtBot/reports/coverage_fuzz/monotree/229d5c201b5528fd/fuzz.coverage/index.html

in src/test/fuzz/headerssync.cpp:15 in 229d5c201b outdated

  10 | +
  11 | +#include <vector>
  12 | +
  13 | +static void initialize_headers_sync_state_fuzz()
  14 | +{
  15 | +    SelectParams(CBaseChainParams::MAIN);

maflcko commented at 8:13 AM on December 9, 2022:

Why not use a no-log context?

dergoegge force-pushed on Dec 9, 2022

dergoegge commented at 11:28 AM on December 9, 2022: member

Thanks for the reviews @MarcoFalke and coverage report @DrahtBot !

I think the coverage this is achieving looks decent, considering the corpus in https://github.com/bitcoin-core/qa-assets/pull/99 is the result of only ~20min of fuzzing.

in src/test/fuzz/headerssync.cpp:87 in 1f70ea0278 outdated

  72 | +
  73 | +            if (fuzzed_data_provider.ConsumeBool()) {
  74 | +                MakeHeadersContinuous(genesis_header, all_headers, *deser_headers);
  75 | +            }
  76 | +
  77 | +            headers.swap(*deser_headers);

sipa commented at 8:50 PM on December 9, 2022:

Nit: headers = std::move(*deser_headers); is equivalent and matches intent better.

in src/test/fuzz/headerssync.cpp:100 in 1f70ea0278 outdated

  83 | +
  84 | +        if (headers.empty()) return;
  85 | +        auto result = headers_sync.ProcessNextHeaders(headers, fuzzed_data_provider.ConsumeBool());
  86 | +        requested_more = result.request_more;
  87 | +
  88 | +        if (result.request_more) {

sipa commented at 9:13 PM on December 9, 2022:

It'd be a bit easier to follow if instead of this conditional there were a if (!result.request_more) break;. The requested_more variable can then also go away, as it'd always be true any time it's checked. Lastly, it'd make it more obvious that redownloaded_it is always initialized in iterations after the first.

sipa commented at 9:52 PM on December 9, 2022: member

Found a crash, haven't investigated yet:

$ base64 <crash-00084111cf9bbbf1300a3f3d3882d81c76da5f00 
8gAAHAEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAMBgAIAAAAAAAAAAngAAAAAAAAAIAP//
AAAACAAAAAsAAPlyAAAAAAAAAF0AALQtAAAAAQAxAAAAxv///xAAAAD5/wAAAAAA//8AHUQAwsPC
wuLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwgAAAAAAAE0AugAAAjIAXFsBpFuUlJSUlJSUlJSU
lJSUlJSUlJSUlJSUlJSUlJSUlJSUlECUlJSUlJSUlJSUlJSUlJSUlJSU////OP///wAAAFv5/wAA
AAAA//8AHUQADwD+//0AAADoXKOjo1uj76Nbo6Ojo6Ojo6Mpo6Sjo6PJXR//////////PnCjo9yg
o6Ojo6OjoA==

in src/test/fuzz/headerssync.cpp:81 in 1f70ea0278 outdated

  76 | +
  77 | +            headers.swap(*deser_headers);
  78 | +        } else {
  79 | +            auto end_it{redownloaded_it + fuzzed_data_provider.ConsumeIntegralInRange<int>(0, all_headers.size())};
  80 | +            headers.insert(headers.cend(), redownloaded_it, end_it);
  81 | +            redownloaded_it = end_it;

dergoegge commented at 12:29 PM on December 10, 2022:

@sipa Thanks for the crash input! Luckily, this crash is caused by a bug in the fuzz target, not HeadersSyncState.

There is a buffer overflow happening here because this might attempt to copy too much from all_headers (i.e. end_it points past the actual end of all_headers).

dergoegge force-pushed on Dec 10, 2022

sipa commented at 3:29 PM on December 10, 2022: member

@dergoegge Good, I assumed it was related to faulty iterator manipulation in the fuzz test.

Ultratrde101 approved

bitcoin deleted a comment on Dec 11, 2022

dergoegge force-pushed on Dec 12, 2022

mzumsande commented at 7:54 PM on December 12, 2022: contributor

Concept ACK

It's unfortunate that runs are non-deterministic: a given seed can lead to different behavior and also coverage will vary from run to run, because m_commit_offset is generated randomly with each instantiation of HeadersSyncState by calling GetRand. Would it be worth it to refactor HeadersSyncState so that this can be made deterministic for the purpose of fuzzing?

dergoegge commented at 8:07 PM on December 12, 2022: member

Would it be worth it to refactor HeadersSyncState so that this can be made deterministic for the purpose of fuzzing?

Good catch! Yes I think that would be absolutely worth it. For now we could maybe just flip g_mock_deterministic_tests to true?

mzumsande commented at 8:19 PM on December 12, 2022: contributor

For now we could maybe just flip g_mock_deterministic_tests to true?

Yes, that would make it deterministic (m_commit_offset = 118), but would make it hard for the fuzzer to cover the next_height % HEADER_COMMITMENT_PERIOD == m_commit_offset branch - the fuzz test would need to create a lot of headers for that. Ideally we'd like to make it fuzzable so that smaller values are possible.

dergoegge force-pushed on Dec 12, 2022

[headerssync] Make m_commit_offset protected 53552affca

[fuzz] Add HeadersSyncState target 3153e7d779

dergoegge force-pushed on Dec 12, 2022

dergoegge commented at 9:10 PM on December 12, 2022: member

Added a commit that refactors HeaderSyncState so that we can set m_commit_offset while fuzzing.

dergoegge requested review from maflcko on Jan 26, 2023

dergoegge removed review request from maflcko on Jan 26, 2023

dergoegge requested review from mzumsande on Jan 26, 2023

mzumsande commented at 7:41 PM on April 10, 2023: contributor

ACK 3153e7d779ac284f86e433af033d63f13f361b6f

I reviewed the fuzzing code and let the fuzzer run for a while with no crashes. I also verified that it does reach most of the code in headerssync.cpp.

maflcko commented at 9:13 AM on April 11, 2023: member

concept ack

fanquake merged this on Apr 11, 2023

fanquake closed this on Apr 11, 2023

sidhujag referenced this in commit 803a076461 on Apr 12, 2023

bitcoin locked this on Apr 10, 2024

sipa commented at 5:03 PM on September 16, 2024: member

Apparently I never submitted this feedback. Maybe useful for follow-ups.