fuzz: focused process_messages fuzz harness with swarm testing

[agroce]

(attn @MarcoFalke and @practicalswift)

Looking at process_messages, it seems that msg_type is an arbitrary string (up to max length), not fixed to the NetMsgTypes in protocol.cpp. The fuzzer or a dictionary has to produce valid strings; given the coverage, this obviously often succeeds. But the code looks to drop an invalid type message pretty definitively, so would it be sensible to build a more efficient fuzzer that does a nondeterministic choice of a valid NetMsgType?

If so, it also opens up a version of the process_messages harness that does swarm testing, repeatedly hitting certain message types and omitting others, which can be very helpful sometimes (see https://www.cs.utah.edu/~regehr/papers/swarm12.pdf -- this is used a lot now in compiler testing, and in Apple's FoundationDB testing approach).

I'd like to tackle this, but want to make sure the concept make sense, of

1) focusing on valid types only 2) applying swarm

I'll also see about a translator to take the valid-messages-only inputs from the process_messages corpus and turn them into this kind of thing. Initially they won't add coverage, but (some) fuzzers will have an easier time exploring this version, and I'm hoping swarm will be useful.

As a side issue, the harness now uses a bool to choose arbitrary # of messages to try. Apparently repeating deep IS useful for state/coverage, since I checked and a large number of the corpus inputs get to depth 10 or deeper.

[maflcko]

a nondeterministic choice of a valid NetMsgType

Wait, I thought fuzzing ought to be deterministic? Have you seen the process_message_$type fuzz targets? I am regularly cross-pollinating their inputs with the other targets. (https://github.com/bitcoin-core/qa-assets/commit/3368bee6bd327f74cd43eda78593091b9e44cff3)

As a side issue, the harness now uses a bool to choose arbitrary # of messages to try.

I didn't get the issue. Is there an alternative version that is preferable?

I'll also see about a translator to take the valid-messages-only inputs from the process_messages corpus and turn them into this kind of thing. Initially they won't add coverage, but (some) fuzzers will have an easier time exploring this version, and I'm hoping swarm will be useful.

Interesting. Generally I think today's fuzz engines aren't smart enough to track coverage of stateful applications sufficiently. I believe one of the greatest risks of our regular "delete non-reduced inputs" task (https://github.com/bitcoin-core/qa-assets/pull/64) is that it deletes supposedly redundant inputs (presumably from the same "swarm") that exercise the state machine in ways that no other input does. I guess -use_value_profile helped a bit for libFuzzer (and it's counterparts for afl), but a coverage metric that includes state is still an open research question.

[agroce]

Sorry -- I just meant it translates the bytes from the input stream into a choice from the message types.

I saw the $type ones, but they won't mix & match, right? Though cross-pollination could be about as good...

[maflcko]

I saw the $type ones, but they won't mix & match, right? Though cross-pollination could be about as good...

I am also running with uniform input crossover, which should mix and match them eventually.

[agroce]

I think that basing the reduction on -use_value_profile=1 does give some protection here, and I'm fairly confident that fuzzing based on the smaller of two inputs with identical coverage is usually better (and there has to be some limit to corpus for effective fuzzing), but yes, the lack of a solid coverage metric is a problem.

I see, it's possible by putting all this "in process" we can get more out of the fuzzer's heuristics, but what you're doing will certainly approximate some of this. I think I'll still code it up and then export back to the original format, to see if we get any surprising coverage gains from this.

As to the bool -- it just requires the fuzzer to figure out that if it wants longer runs, it needs to have that turn out non-zero. Now, guess it being "non-zero" gives a huge bitwise bias towards longer runs, up to the length, so it works out ok. But if it was based on the final bit or something, constructing longer sequences would be tough (as it is, it's fairly hard to make a short sequence, unless you just don't generate many bytes). Not an issue here. I tend to construct these to choose a length in an initial choice, from a range, but doing this, with "zeros when no more fuzz data" seems to be just as good, or maybe better in some ways.

[agroce]

@MarcoFalke should the commands in process_messages inputs always be null-terminated strings? it looks like they should, but some inputs have odd things like getaddr( in the data. I suppose just a fuzzer near-miss?

[agroce]

I can reverse engineer it, but if I want to write an integer in bytes to be read by 'ConsumeIntegralInRange` as on line 60 of https://github.com/agroce/bitcoin/blob/process_message_focused/src/test/fuzz/process_messages_focused.cpp, what byte count and format do I need to use? 4 bytes (it grabs an int if the start range type is int?), little endian?

[maflcko]

Now, guess it being "non-zero" gives a huge bitwise bias towards longer runs

It only uses 1 bit of the byte. So assuming uniform bytes, there shouldn't be a bias.

// Reads one byte and returns a bool, or false when no data remains.
inline bool FuzzedDataProvider::ConsumeBool() {
  return 1 & ConsumeIntegral<uint8_t>();
}

if I want to write an integer in bytes to be read by 'ConsumeIntegralInRange`

You can use fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(0, 22). Regardless of what type you use, it will only grab one byte (because one byte is enough to cover the full range).

[agroce]

Am I correct in interpreting this code and comment:

https://github.com/bitcoin/bitcoin/blob/7ebc4c668968da084d7258b32c5f3b2aceefc232/src/test/fuzz/FuzzedDataProvider.h#L216-L227

as saying bytes for integer ranges are somehow not read from the stream in order, but pulled from a separate "section" at the end of the fuzz input?

[agroce]

... so if I want to write code to "translate" an existing process_messages input into my form, I need to

1) detect valid type strings and remove them from the binary data 2) append a byte with the proper index at the end of the fuzz input, to be pulled off (this won't quite work if other ranges are read in the meantime, though, so I'll need to inspect for that...)

[maflcko]

Yes, your reading of that comment seems correct. Fuzz input translation is non-trivial for most cases. See also #20837 .

I think one way to achieve your desired translation is to implement a "FuzzedDataSerializer" (the inverse of the FuzzedDataProvider), then re-implement process_messages to (only) parse the old format and at the same time write the new format.

An alternative would be to just run fuzzing from scratch (maybe seeded with the process_messages inputs).

[agroce]

Actually, I think I may "cheat" and just use ConsumeByte to index into the message types, which should be easy to implement a "good enough" translator. I think separation makes sense for lengths, but my bytes are just a compressed version of the string, so in-stream for fuzzer to change seems maybe better anyway.

[agroce]

I started on the parse-and-write this morning, but getting the details right with my need to dump in swarm config is annoying, I'll try Bytes first.

[agroce]

I won't do a PR until I see if this is actually useful, but I have a swarmed/indexed process_messages fuzzer up and running now, and looks like the conversion of old corpus maybe worked at least "ok"

[agroce]

https://github.com/agroce/bitcoin/blob/process_message_focused/src/test/fuzz/process_messages_focused.cpp

[agroce]

(the conversion was very partial, since it doesn't yet have a way to deal with invalid messages in the stream, they simply throw everything off, but 2000+ of the 10K corpus did survive as useful)

[agroce]

I have one run just gaining coverage going on it, and one with full sanitizers in case this is helpful in bug finding.

[chinggg]

@agroce Thanks for your paper Looking for Lacunae in Bitcoin Core’s Fuzzing Efforts. If you have any progress in swarm fuzzing, please let me know. I can try it when adding fuzz target for orphan transaction handling.

[willcl-ark]

Closing this as it has not had any activity in a while. If you are interested in continuing discussion on this, or you feel that it is sufficiently important, please leave a comment so that it can be reopened.