fuzz: Add process_messages harness

MarcoFalke commented at 2:31 am on April 4, 2020: member

MarcoFalke force-pushed on Apr 4, 2020

fanquake added the label Tests on Apr 4, 2020

DrahtBot commented at 6:46 am on April 4, 2020: member

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#18470 (net: Make stale tip check time type-safe, extend test by MarcoFalke)

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.

practicalswift commented at 5:27 pm on April 4, 2020: contributor

Concept ACK

Very nice fuzzing harness! Keep them coming! :)

MarcoFalke force-pushed on Apr 4, 2020

fuzz: Add process_messages harness fa6a008434

MarcoFalke force-pushed on Apr 5, 2020

practicalswift commented at 8:25 pm on April 6, 2020: contributor

Tested ACK fa6a00843447d53a5708ea3a629b9150cfe58be2

Thanks for adding a very nice harness!

MarcoFalke commented at 8:26 pm on April 6, 2020: member

Thanks for testing. Did you find the CVE after re-introducing it?

practicalswift commented at 8:31 am on April 8, 2020: contributor

@MarcoFalke

Yes :)

Live demo:

 0$ mkdir -p process_messages/
 1$ src/test/fuzz/process_messages process_messages/
 2…
 3bloom.cpp:45:69: runtime error: division by zero
 4SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior bloom.cpp:45:69 in
 5AddressSanitizer:DEADLYSIGNAL
 6=================================================================
 7==17357==ERROR: AddressSanitizer: FPE on unknown address 0x55b551298dca (pc 0x55b551298dca bp 0x7ffd02f6f890 sp 0x7ffd02f6f860 T0)
 8    [#0](/bitcoin-bitcoin/0/) 0x55b551298dca in CBloomFilter::Hash(unsigned int, std::vector<unsigned char, std::allocator<unsigned char> > const&) const src/bloom.cpp:45:69
 9    [#1](/bitcoin-bitcoin/1/) 0x55b551298b69 in CBloomFilter::insert(std::vector<unsigned char, std::allocator<unsigned char> > const&) src/bloom.cpp:54:31
10    [#2](/bitcoin-bitcoin/2/) 0x55b550a820c6 in ProcessMessage(CNode*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, CDataStream&, long, CChainParams const&, CTxMemPool&, CConnman*, BanMan*, std::atomic<bool> const&) src/net_processing.cpp:3183:45
11    [#3](/bitcoin-bitcoin/3/) 0x55b550abd122 in PeerLogicValidation::ProcessMessages(CNode*, std::atomic<bool>&) src/net_processing.cpp:3359:16
12    [#4](/bitcoin-bitcoin/4/) 0x55b550ac0f25 in non-virtual thunk to PeerLogicValidation::ProcessMessages(CNode*, std::atomic<bool>&) src/net_processing.cpp
13    [#5](/bitcoin-bitcoin/5/) 0x55b550907f01 in ConnmanTestMsg::ProcessMessagesOnce(CNode&) src/./test/util/net.h:26:56
14    [#6](/bitcoin-bitcoin/6/) 0x55b550904ecf in test_one_input(std::vector<unsigned char, std::allocator<unsigned char> > const&) src/test/fuzz/process_messages.cpp:69:21
15…
16$ xxd -p < ./crash-55a890a083dbb4291c5dbc367a58651d02854d86
17697665726163ffff006e5757a860a80d5d5c6966696c7465726164640061
18fc010000000064645757575757a8a8b661a85ca866696c7465726c6f6164
1900bb000500000000d08cff00000000613000ad000000005c6966696c7465
2072616464031561b800fc40636d7063ffffffffffffff325c6966696c7465
21726164640061fc00a8e0a87800000000000000ffff4100ff67cb59570d41
224141fffedf4141415ca8a5a85a006ea5a8a865a867e5cb79570d5c57572f
23a8a5ffff00ff020d5ca8a8a8a8a8696e76a8a86464
24$ strings ./crash-55a890a083dbb4291c5dbc367a58651d02854d86
25iverac
26]\ifilteradd
27ddWWWWW
28filterload
29\ifilteradd
30[@cmpc](/bitcoin-bitcoin/contributor/cmpc/)
312\ifilteradd
32AAA\
33\WW/

MarcoFalke commented at 4:15 pm on April 8, 2020: member

Going to go ahead and merge this. If someone has feedback or questions, you are welcome to leave them here.

MarcoFalke merged this on Apr 8, 2020

MarcoFalke closed this on Apr 8, 2020

MarcoFalke deleted the branch on Apr 8, 2020

in src/test/fuzz/process_messages.cpp:57 in fa6a008434

52+
53+        connman.AddTestNode(p2p_node);
54+    }
55+
56+    while (fuzzed_data_provider.ConsumeBool()) {
57+        const std::string random_message_type{fuzzed_data_provider.ConsumeBytesAsString(CMessageHeader::COMMAND_SIZE).c_str()};

robot-visions commented at 5:22 am on April 12, 2020:

Could the fuzzer check “interesting” cases more quickly by choosing a random but valid command, instead of generating a random string of length COMMAND_SIZE?

MarcoFalke commented at 12:21 pm on April 12, 2020:

Good question. I think there is a trade-off here between giving the fuzz engine as much freedom to explore as possible at a potentially slight cost of performance (citation needed, giving more freedom could also increase efficiency).

Your suggestion would involve enumerating all netmessage types in an array and then having the fuzz engine pick one from it. This is possible, but as soon as you add a new message type, the developed seeds (inputs) render invalid and need to be adjusted. Readjusting the seeds should not be an issue for the fuzz engine, but it has to be done.

Apart from the above slight inconvenience of having to readjust the seeds on every added (or removed) message type, there is also an issue that the enumeration could accidentally miss one message type. On top, Bitcoin Core ignores unknown message types, and I’d say we want to test this code path as well. (Have at least one unknown message type generated by the fuzzer). This can also be fixed by adding an unknown message type to the fixed array the fuzz engine can pick from. E.g. “foobarfoo”.

Moreover, we might also want to test for slight modifications of the same message type and see if they affect behavior in any way. For example b"filteradd\x01add" vs b"filteradd\x02". Those two should never be treated as a valid command and obviously shouldn’t crash Bitcoin Core. There should be unit and maybe other fuzz tests in place to check this, but I think allowing the fuzz engine in this test more freedom can’t hurt.

Finally, while I don’t know the internals of fuzz engines, I believe they are really smart and quick about figuring out “interesting” strings that appear in the source code. If I had to guess what the performance penalty was of allowing any message type as opposed to limiting it to a fixed set of types, I’d presume it is an unnoticeable difference, maybe slight slow down or possibly a slight speed up even. A benchmark might help here.

I tried a few other presumed performance improvements while writing the test and surprisingly I found that writing the least code, simplest code, while allowing the fuzz engine the most freedom was also the fastest way to find the CVE.

robot-visions commented at 8:12 pm on April 12, 2020:

Thanks for the really thorough explanation! That tradeoff / your decision makes sense to me, especially since I didn’t know that fuzz engines might do better than “just generate random strings”.

mzumsande commented at 0:19 am on April 15, 2020:

I agree as well that the merged version makes sense, but just out of interest I ran both versions (PR and a version which samples an array with all NetMsgTypes currently defined in protocol.cpp ) in parallel with libfuzzer and it was the altered version which found the reintroduced CVE first after 2.3M iterations / 2 hours, while the PR version hadn’t found it after 10M tries. I found it interesting that while the cov metric was similar between the runs, the ft metric of the fuzzer was consistently higher for the array version throughout the run.

Although this was just sample size 1, so finding the CVE might have just been a lucky mutation in the fuzzer algorithm…

MarcoFalke commented at 0:53 am on April 15, 2020:

How many workers did you run in parallel?

mzumsande commented at 1:16 am on April 15, 2020:

Just 1 for each version.

MarcoFalke commented at 1:23 am on April 15, 2020:

This sounds like a promising speed-up. I wouldn’t object either having this one replaced or a new fuzz target with the array version.

mzumsande commented at 1:33 am on April 15, 2020:

I’ll do some more runs tomorrow, maybe I was just lucky. I don’t have a good feeling for the variance of runtimes yet.

MarcoFalke commented at 1:44 am on April 15, 2020:

I saw it vary by a factor or 5 or 10 in my tests last week, so it could very well be just noise

robot-visions commented at 5:36 am on April 12, 2020: contributor

ACK fa6a008.

This looks extremely useful, thanks for adding! I was also able to reproduce the CVE:

0bloom.cpp:45:69: runtime error: division by zero
1SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior bloom.cpp:45:69 in 
2AddressSanitizer:DEADLYSIGNAL
3=================================================================
4==56684==ERROR: AddressSanitizer: FPE on unknown address 0x00010a4a031e (pc 0x00010a4a031e bp 0x7ffee63a2d60 sp 0x7ffee63a2d30 T0)
5    [#0](/bitcoin-bitcoin/0/) 0x10a4a031e in CBloomFilter::Hash(unsigned int, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) const bloom.cpp:45
6    [#1](/bitcoin-bitcoin/1/) 0x10a49ffeb in CBloomFilter::insert(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) bloom.cpp:52
7    [#2](/bitcoin-bitcoin/2/) 0x109c1d4f8 in ProcessMessage(CNode*, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&, CDataStream&, long long, CChainParams const&, CTxMemPool&, CConnman*, BanMan*, std::__1::atomic<bool> const&) net_processing.cpp:3183
8    [#3](/bitcoin-bitcoin/3/) 0x109c5d928 in PeerLogicValidation::ProcessMessages(CNode*, std::__1::atomic<bool>&) net_processing.cpp:3359
9    [#4](/bitcoin-bitcoin/4/) 0x10985b7a9 in test_one_input(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) process_messages.cpp:70

sidhujag referenced this in commit 5062b38fbd on Apr 13, 2020

narula commented at 4:18 pm on April 22, 2020: contributor

As a data point, I was able to reproduce the CVE. It took about ~5-6 hours running 16 jobs.

 0bloom.cpp:45:69: runtime error: division by zero
 1SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior bloom.cpp:45:69 in 
 2AddressSanitizer:DEADLYSIGNAL
 3=================================================================
 4==40871==ERROR: AddressSanitizer: FPE on unknown address 0x55931bfc0b75 (pc 0x55931bfc0b75 bp 0x7ffc03d58840 sp 0x7ffc03d58810 T0)
 5    [#0](/bitcoin-bitcoin/0/) 0x55931bfc0b74  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x2526b74)
 6    [#1](/bitcoin-bitcoin/1/) 0x55931bfbb90b  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x252190b)
 7    [#2](/bitcoin-bitcoin/2/) 0x55931b823465  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x1d89465)
 8    [#3](/bitcoin-bitcoin/3/) 0x55931b8528f1  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x1db88f1)
 9    [#4](/bitcoin-bitcoin/4/) 0x55931b855d15  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x1dbbd15)
10    [#5](/bitcoin-bitcoin/5/) 0x55931b687ea4  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x1bedea4)
11    [#6](/bitcoin-bitcoin/6/) 0x55931b684453  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x1bea453)
12    [#7](/bitcoin-bitcoin/7/) 0x55931c85a94f  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x2dc094f)
13    [#8](/bitcoin-bitcoin/8/) 0x55931b562ce7  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x1ac8ce7)
14    [#9](/bitcoin-bitcoin/9/) 0x55931b56d554  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x1ad3554)
15    [#10](/bitcoin-bitcoin/10/) 0x55931b56ebbf  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x1ad4bbf)
16    [#11](/bitcoin-bitcoin/11/) 0x55931b55df7c  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x1ac3f7c)
17    [#12](/bitcoin-bitcoin/12/) 0x55931b5427d2  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x1aa87d2)
18    [#13](/bitcoin-bitcoin/13/) 0x7f81d6280b96  (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
19    [#14](/bitcoin-bitcoin/14/) 0x55931b550e99  (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x1ab6e99)
20
21AddressSanitizer can not provide additional info.
22SUMMARY: AddressSanitizer: FPE (/home/neha/src/bitcoin/src/test/fuzz/process_messages+0x2526b74) 
23==40871==ABORTING
24MS: 2 ChangeByte-CrossOver-; base unit: 369297d2ec45713fa6113836603e63a500a2403c
25artifact_prefix='./'; Test unit written to ./crash-b8f6aae14715726dbd88ef4a5b383e1b50c0fa46

jasonbcox referenced this in commit a9c2983523 on Nov 13, 2020

deadalnix referenced this in commit fe8f6ac7e2 on Dec 9, 2020

DrahtBot locked this on Feb 15, 2022

in src/test/fuzz/process_messages.cpp:36 in fa6a008434

31+
32+void test_one_input(const std::vector<uint8_t>& buffer)
33+{
34+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
35+
36+    ConnmanTestMsg& connman = *(ConnmanTestMsg*)g_setup->m_node.connman.get();

sipa commented at 8:27 pm on February 17, 2022:

I’m pretty sure this is UB. You can’t cast to a subclass of the actually created object, even if it adds no fields or member functions.

MarcoFalke commented at 7:06 am on February 18, 2022:

Good find, further discussion in #24373

(Obviously I was testing the review process to see how long it would take to find out)

fuzz: Add process_messages harness #18521

Conflicts