Fuzz: Add process_messages harness (
tests) Apr 15, 2020
The PR branch HEAD was fa6a0084 at the time of this review club meeting.
A few weeks ago,
we looked at how fuzzing can find consensus bugs, such as money printing (brrr̅). This
week we will use fuzzing to find a remote crasher.
BIP 37 describes a way to filter transaction relay
by bloom filters. For the purposes of this pull request we will only need to know the different message types it
introduces and how the Bitcoin Core node processes them.
CVE-2013-5700 was a vulnerability
that could crash a node by merely sending two P2P messages.
Bitcoin core has
documentation on how to compile with AFL and libFuzzer on
Linux. Other fuzz engines and operating systems might
work, but are currently undocumented.
CNode is the data structure to represent a connection in Bitcoin
CConnman is the connection manager in Bitcoin Core. A thread
to handle messages from connections is created at startup. This is often referred to as the “main” thread in Bitcoin
Core, taking care of message processing and validation. See
The pull request we are looking at this week is extending CConnman for testing purposes with several features:
Adding and removing nodes directly (without having to create a socket)
Push a serialized message onto a nodes’ receive buffer
The fuzz test itself does mainly two things for each fuzz input or fuzz seed:
Add a random amount of test nodes (the number of nodes is read from the fuzz input)
Pick a random peer and send some random bytes as a message from this peer, i.e. put the bytes into the receive
buffer of this peer
Repeat the last step
Did you review the PRs?
Concept ACK, approach ACK, tested ACK, or
(Don’t forget to put your PR review on GitHub.)
How would a remote node crash a Bitcoin Core node that is vulnerable to the attack? What steps would it need to take
and what messages would it send?
How was the vulnerability fixed?
CNode are bloom filters for transaction relay filtering stored?
Where are bloom filter messages handled by Bitcoin Core?
Based on the previous questions, how would a fuzz test for Bitcoin Core exploit this vulnerability? What are the
steps needed on a high level to achieve this setup?
What patch needs to be applied to current Bitcoin Core to reintroduce the vulnerability?
Did you get fuzzing to run on your machine? If not, what issues did you run into?
Did you find the crash?
1 12:59 <MarcoFalke> #startmeeting
2 13:00 <MarcoFalke> hi everyone
6 13:00 <michaelfolkson> hi
11 13:01 <robot-visions> hi
12 13:01 <MarcoFalke> Reminder that you are welcome to ask questions. Don't ask to ask. We are all here to learn (including myself)
16 13:01 <MarcoFalke> To get started, did you get a chance to review the pull request or take a look at it?
18 13:02 <robot-visions> (y) reviewed
20 13:02 <vasild> y, briefly
25 13:02 <theStack> n (still occupied with #17860)
27 13:03 <michaelfolkson> Took a look at it yes. Trying to learn more about fuzz testing generally so I can better understand where we are going with it.
28 13:03 <MarcoFalke> ok, so to get started with the net_processing vulnerability in the bloom filter that the fuzz tests is trying to find. What are the messages a remote node needs to send?
30 13:04 <MarcoFalke> michaelfolkson: Good to hear. I am hosting this club to get everyone introduced to fuzzing :)
31 13:04 <MarcoFalke> robot-visions: Correct
32 13:04 <MarcoFalke> Did anyone come up with alternative ways to trigger the vulnerability?
34 13:05 <robot-visions> Is it necessary to send the second `filteradd`, or is it enough to just wait for an `inv` from elsewhere?
35 13:05 <jonatack> michaelfolkson: you'll find the PR description most helpful :p
36 13:05 <michaelfolkson> Yup that was good too ;)
37 13:06 <MarcoFalke> robot-visions: Anything that eventually calls CBloomFilter::Hash should crash the node
38 13:07 <robot-visions> Thanks MarkoFalke! Makes sense.
39 13:07 <MarcoFalke> So I believe waiting for the node to process a transaction either from itself or from another peer should also hit the crash
40 13:07 <MarcoFalke> How was this vulnerability fixed?
41 13:07 <michaelfolkson> So practicalswift and robot-visions were able to trigger it. They triggered it in different ways?
42 13:08 <MarcoFalke> michaelfolkson: I haven't looked at their fuzz inputs, but we can do that later
43 13:08 <michaelfolkson> Ok
44 13:08 <MarcoFalke> (If they share them)
46 13:10 <lightlike> It was fixed covertly, by adding a UpdateEmptyFull() function that is processed on filterload (net_processing) an sets isFull if the underlaying array is empty. Filteradd will not insert anything if isFull is set
47 13:10 <theStack> is there plans to commit certain fuzz inputs into the repository? (or is that already the case?)
48 13:10 <MarcoFalke> theStack: They are located in bitcoin-core/qa-assets on GitHub
49 13:11 <theStack> MarcoFalke: ah, i see. tend to forget that there are also other repos outside of bitcoin/bitcoin ;-)
50 13:11 <MarcoFalke> robot-visions: lightlike: Correct
51 13:12 <lightlike> I understand why it was fixed this way back then, but wouldn't it make sense to do something more obvious today (like also check for zero in Hash()?)
52 13:12 <theStack> i was quite fascinated by this covert fix. i can imagine is it really hard to fix something but needing to pretend doing something different
53 13:12 <theStack> lightlike: the point is, if you do it in an obvious way, the vulnerability becomes public and is exploited
54 13:13 <chanho> I think the question is, should the covert fix be removed and updated with a proper fix, e.g. check for zero division?
55 13:13 <lightlike> theStack: yes, I understand, but my question referred to today where basically all nodes are no longer vulnerable
56 13:14 <MarcoFalke> I think theStack has a good point. If the fix for this trivial exploit is a one-line patch, it might make it easy for bad players to exploit it
57 13:15 <theStack> chanho: lightlike: to my understanding, it could be removed and done in a simpler way
58 13:16 <jnewbery> lightlike chanho: I agree that after some time has passed (perhaps a couple of years) these covert fixes should be cleared up and made public. Leaving them in goes against the goal of having the code as clear and straightforward as possible.
59 13:17 <MarcoFalke> I haven't thought about this question upfront, but I think even today the patch would look similar.
60 13:17 <jnewbery> to be fair, I don't think they're left in this way on purpose. I expect the person who fixes it probably just forgets and it's not their priority after two years
61 13:18 <MarcoFalke> But let's not talk about how the code can be cleaned up today and focus on fuzzing :)
62 13:18 <MarcoFalke> All we need to know about the vulnerability for now is how it was triggered and how it was fixed
64 13:19 <MarcoFalke> michaelfolkson: Anyone can generate them, but we'll cover this in the second half of the meeting
65 13:19 <michaelfolkson> Ok sorry :)
66 13:19 <MarcoFalke> no worries
67 13:19 <MarcoFalke> Let's take a look at the structure of Bitcoin Core. Where in CNode are the bloom filters stored?
68 13:20 <robot-visions> I think it's in `CNode->m_tx_relay->pfilter`
69 13:20 <MarcoFalke> Right
70 13:20 <theStack> robot-visions: +1
71 13:20 <MarcoFalke> And where are bloom filter messages handled?
72 13:21 <theStack> net_processing.cpp, directly in the huge ProcessMessage() function
73 13:21 <robot-visions> theStack: (y)
74 13:23 <MarcoFalke> A fuzzing harness needs an entry point, and to execute the bloomfilter code, it needs to call into the ProcessMessage function
75 13:24 <MarcoFalke> Does anyone have questions about the structure of the fuzzing harness?
76 13:25 <MarcoFalke> Pretty much what it does is, (1) create a few CNode (with the bloomfilters initialized), then (2) pretend they are sending random messages by passing them into the ProcessMessage function
77 13:26 <sipa> jnewbery: an alternative is (in general) not removing covert fixes (because touching the code again introduces risks of its own), but still documenting them in the code
78 13:26 <andrewtoth> What is the purpose of having a random number of nodes created? Is it because it affects what they do with the messages if they have different number of peers?
79 13:27 <michaelfolkson> I suppose you are receiving different numbers of messages depending on how many peers you have
80 13:28 <MarcoFalke> sipa: Good point . I've done something for the money printing bug in #17080
81 13:29 <theStack> If a constant number of nodes were be sufficient, could that CNode creation code move into initialize()? Or is there any other reason it has to be created again and again for each input?
82 13:29 <theStack> s/were be/were/
83 13:29 <MarcoFalke> andrewtoth: Good question. The purpose of the fuzz test was to be more than just a test to find the bloomfilter bug. It should also test other parts of the code like transaction relay, which has a lot of state
84 13:30 <lightlike> theStack: I believe the service flags are fuzzed too, so maybe that is the reason?
85 13:30 <MarcoFalke> Unfortunately, the current fuzzer can not test transaction relay because messages are constructed from something that looks like a random stream
86 13:31 <theStack> lightlike: you are right, there are numerous other properties that are fuzzed
87 13:31 <MarcoFalke> lightlike: Jup, I tried to be as permissive as possible. Give the fuzz test as much space to search as possible.
88 13:31 <andrewtoth> MarcoFalke: so to test transaction relay, a separate harness that uses the fuzz inputs to generate different relay messages needs to be built?
89 13:32 <lightlike> I noticed that the fuzzer needs quite some of tries (>10k) until it gets to the ProcessMessage part the first time
90 13:32 <sipa> MarcoFalke: a special fuzzregtest mode that disables signature validation?
91 13:32 <MarcoFalke> andrewtoth: In theory the fuzz engine could figure out how to construct transactions. All it has to do is guess the inputs correctly
92 13:32 <MarcoFalke> sipa: It needs to guess the hash of the input
93 13:33 <MarcoFalke> Which has low probability assuming the best you can do is random guesses
94 13:33 <jnewbery> sipa: (re removing covert fixes) yes. I think it depends on context (riskiness of change vs benefit of clarifying code to match intent)
95 13:34 <andrewtoth> So a harness which better guides the fuzzer would be more efficient for tx relay
96 13:34 <sipa> MarcoFalke: oh, right
97 13:34 <MarcoFalke> However, modern fuzz engines do a lot better on many things than just random guesses. For example, they can extract strings easily
98 13:35 <MarcoFalke> You can see that when running the fuzzer. In a few seconds it has already guessed some of the message types
99 13:35 <MarcoFalke> andrewtoth: Yes
100 13:35 <MarcoFalke> I am still thinking what the best way is to achieve this
101 13:35 <sipa> right, because the coverage guiding can observe the characters being compared against
102 13:35 <sipa> this wouldn't be the case for a hash comparison
103 13:36 <theStack> MarcoFalke: would you count both libfuzzer and AFL to the category of "modern fuzz engines"? or are there better ones (commercial or anything)?
104 13:36 <MarcoFalke> sipa: Yes. I don't know how fuzz engines work, but I could also imagine that it might dump the binary and see if there are any strings in it.
105 13:37 <sipa> MarcoFalke: i believe not
106 13:37 <MarcoFalke> (Not sure if you can even inspect your own binary with C++)
107 13:38 <MarcoFalke> theStack: I have only tried the two
108 13:38 <lightlike> I thought it is some kind of genetic algorithm that tries to optimize code coverage and performs all kind of mutations.
109 13:38 <MarcoFalke> So did anyone find the crasher? What patch did you have to apply to re-introduce the vulnerability?
110 13:38 <michaelfolkson> theStack: For fuzzing open source projects, libFuzzer and AFL were modern in 2017
111 13:39 <robot-visions> To re-introduce the vulnerability: It suffices to remove the `if (isFull) return` check at the beginning of `CBloomFilter::insert`
112 13:39 <lightlike> I noticed the fuzzer finds easy messages ("inv") much faster than longer ones ("filterload")
113 13:40 <MarcoFalke> For me the first thing it found was -dropmessagetest
114 13:40 <nehan_> i'm running the fuzzer but it doesn't seem to be showing me which messages it's using:
115 13:40 <MarcoFalke> Which is a command line flag, ouch
116 13:40 <lightlike> nehan: i grepped the corpus directory for the strings to see if they were found yet
117 13:41 <MarcoFalke> nehan_: If you use libfuzzer, sometimes it will tell you in the stdout lines which "dictionary" words were added or removed
118 13:41 <MarcoFalke> It is also possible to inspect the input directory directly
119 13:41 <sipa> MarcoFalke: are you familiar with the -dict optionm
121 13:41 <MarcoFalke> Though, be warned if you use cat to redirect a fuzz input to your terminal
122 13:41 <nehan_> lightlike: thanks
123 13:41 <nehan_> MarcoFalke: I'm wondering if I didn't compile something correctly, I only seem to have symbols:
124 13:41 <nehan_> #868056 REDUCE cov: 17995 ft: 84042 corp: 1298/1621Kb exec/s: 446 rss: 510Mb L: 3483/4096 MS: 4 InsertByte-InsertByte-InsertRepeatedBytes-EraseBytes-
125 13:42 <MarcoFalke> sipa: no, is that an option to libfuzzer?
126 13:42 <sipa> nehan_: it lists the mutations it is applying to existing seeds
127 13:42 <MarcoFalke> nehan_: It shows it only rarely for me
128 13:42 <sipa> nehan_: if it finds a crash, it will create a file with the input that causes the crash
129 13:43 <sipa> MarcoFalke: yeah, to tell it about strings that are likely relevant to your fuzzer
130 13:43 <jonatack> nehan_: i'm seeing the same, and occasionally there's a message at the end of the line
131 13:43 <jonatack> 371324REDUCE cov: 14900 ft: 65908 corp: 907/963Kb exec/s: 388 rss: 534Mb L: 2020/4096 MS: 5 CMP-ChangeBinInt-InsertRepeatedBytes-InsertRepeatedBytes-EraseBytes- DE: "verack"-
132 13:43 <MarcoFalke> sipa: Ah, so I could pass in the utxo set as a dict?
133 13:44 <MarcoFalke> jonatack: Thanks, that is what I meant
134 13:44 <sipa> MarcoFalke: well for that you could also just manually create a seed
135 13:44 <jonatack> nehan_: (good question)
136 13:44 <sipa> i believe DE is in fact it using a dictionary word
137 13:44 <nehan_> i've been running for an hour or so and it has created 1330 files. All of those can't be crashes?
138 13:44 <sipa> nehan_: only if they're called crash-XXXXX
139 13:45 <nehan_> sipa: ah, thanks. let me go learn more about libfuzzer...
140 13:45 <MarcoFalke> If you inspect the seeds manually with cat, please pass in `cat --show-nonprinting`, otherwise it might execute arbitary code in your terminal
141 13:45 <sipa> the files you usually see are the seeds
142 13:46 <sipa> they're the input that maximize coverage (of code and of "features")
143 13:46 <nehan_> how long did it take folks to find the crash?
144 13:46 <MarcoFalke> To run the fuzz harness can supply a folder where to put the seeds: ./src/test/fuzz/process_messages ./where/to/put/the/seeds
145 13:46 <MarcoFalke> And then `cat --show-nonprinting ./where/to/put/the/seeds/000fff...`
146 13:47 <MarcoFalke> nehan_: Good question. I am also interesed in that.
147 13:47 <lightlike> I noticed if I stop the fuzzer (Ctrl+C) and start it again with the same seed dir, the coverage will be significantly lower than before, as if it didn't reload all the work done before. Does anyone know why this is the case? (I thought the seeds would be updated after each try)
148 13:48 <MarcoFalke> I think the fastest I got was 600k, but with 9 workers in parallel, so I am not sure if that counts because you can't compare it against a single worker. (The libfuzzer workers work together on the same seed corpus)
149 13:49 <jonatack> I'm still running it, will comment in the PR when it crashes
150 13:49 <sipa> lightlike: as in the "cov" number is lower?
151 13:49 <sipa> that'd surprise me
152 13:49 <lightlike> sipa: yes, cov and ft
153 13:49 <MarcoFalke> lightlike: Good question. I believe it is because of "adjacant" coverage. Bitcoin core runs a lot of threads (like the stale tip check in the scheduler), and those are not included in the coverage if you start afresh
155 13:50 <MarcoFalke> Which is unfortunate, but I don't know how to "fix"
156 13:50 <sipa> could be the result of non-deterministic behavior
157 13:50 <MarcoFalke> sipa: Or that of course
158 13:50 <sipa> if the fuzzed binary uses randomness anywhere, fuzzing is less.efficient
159 13:50 <MarcoFalke> I think my greatest fear would be to find a crasher and then try to reproduce it with the same seed and it wouldn't crash because of non-determinism
160 13:51 <MarcoFalke> deterministic randomness is fine (as long as it is derived by the fuzz engine)
161 13:51 <lightlike> I didn't find the bug after 10M steps and stoppped, but found it after 2.2 million steps with a version in which I replaced the MsgType Fuzzing with an array of all known Messages, for which then only the index is fuzzed.
162 13:52 <MarcoFalke> Did anyone run into issues while fuzzing or setting up the fuzzer?
163 13:52 <emzy> The fuzzing is deterministic? So generated by a pseudorandom number generator?
164 13:53 <robot-visions> MarkoFalke: I was able to get things work by following the "macOS hints for libFuzzer", but I had to remove the `--disable-asm` flag when running `./configure`
165 13:53 <robot-visions> Marco* (sorry)
166 13:53 <MarcoFalke> emzy: I think the fuzz engine picks a random seed at the beginning, but it might be possible to make even the fuzzing deterministic
168 13:54 <sipa> you can pick the rng seed
169 13:54 <MarcoFalke> robot-visions: Is that wrong in our docs? It could help others if you amend that note there
170 13:56 <MarcoFalke> sipa: Correct, for libfuzzer you can pick the internal starting seed
171 13:56 <theStack> MarcoFalke: i had a linking issue with the http_request fuzz test, which used internal libevent functions (evhttp_parse_firstline_) that were named slightly different on my libevent -- could fix it locally though, will open an issue later
172 13:56 <MarcoFalke> theStack: Does Bitcoin Core compile fine without libFuzzer?
173 13:57 <theStack> MarcoFalke: yes it does
175 13:58 <nehan_> i had an unused variable warning in test/fuzz/locale.cpp:59
178 13:58 <andrewtoth> nehan_ same
179 13:58 <robot-visions> MarcoFalke: I think the docs are reasonable right now. It says (1) "you may need to run `--disable-asm` to avoid errors, and (2) "here's what worked on our setup (which included `--disable-asm`)". It doesn't say you *must* use that flag.
180 13:59 <MarcoFalke> nehan_: Good point. The warning is caused because a fuzz test was modified. To not invalidate existing seeds, the fuzz harness still needs to consume the same bytes it did previously, but now they are unused. I think this can be fixed by prefixing the line with (void)
181 13:59 <nehan_> MarcoFalke: interesting!
182 14:00 <MarcoFalke> #endmeeting
183 14:00 <MarcoFalke> Thanks everyone!
184 14:00 <robot-visions> Thanks!
185 14:00 <vasild> Thanks!
186 14:00 <theStack> thanks for hosting!
187 14:00 <nehan_> thanks!
188 14:00 <jonatack> or passing -help=1 ... e.g. src/test/fuzz/process_messages -help=1
190 14:00 <jonatack> thanks MarcoFalke!
191 14:01 <lightlike> thanks!
192 14:01 <nehan_> i've never done any fuzzing before so this was cool
193 14:02 <andrewtoth> Thanks MarcoFalke!
194 14:03 <jnewbery> thanks MarcoFalke. Great Review Club!
195 14:03 <michaelfolkson> You going to hang around for a bit MarcoFalke or you need to go?
197 14:04 <theStack> to shortly bring up the subject of remaining covert fixes again: it can be confusing to code readers if it remains. E.g. it led to the issue #16886 and its fix PR #16922 (the latter one by me), both made in the wrong assumption that the point of the empty/full flags were optimization, as we didn't know about the covert fix
198 14:04 <jonatack> theStack: the meeting log for that session begins with us trying to get fuzz/test_runner.py to work :)
199 14:05 <robot-visions> On a similar note to what theStack mentioned, would it make sense to now consider a peer "misbehaving" if they send an empty bloom filter?
200 14:05 <theStack> jonatack: awesome -- though from my side it was more of a conclusion that i don't need the fuzz test_runner ;)
202 14:07 <theStack> robot-visions: personally i think that would be fine, don't know though how strict BIP37 is interpreted -- it afair only defines an upper filter size limit, but not a lower limit
203 14:08 <theStack> robot-visions: on the other hand i wouldn't know the point of an empty filter
204 14:09 <theStack> jonatack: yes i also think that a short explanation with CVE number mentioning would be more appropriate
205 14:12 <jonatack> robot-visions: interesting question
206 14:13 <lightlike> theStack: I found it interesting that I didn't find any detailed description on how to crash the node using the CVE apart from the one in your PR. Did you find any, or did you just figure it out yourself?
207 14:17 <theStack> lightlike: i was also wondering the same. the only information i got was that it is triggered by a division by zero. then i inspected the CBloomFilter class for divisions, and since the class is not that large i could figure it out quite fast
209 14:19 <andrewtoth> I think the exploit is not described in detail anywhere conspicuous intentially
210 14:19 <andrewtoth> *intentionally
211 14:19 <sipa> at the time, it was certainly intentionally
212 14:19 <sipa> though it should be documented now
213 14:20 <andrewtoth> sipa: +1
214 14:20 <lightlike> andrewtoth: I thought that whenever the CVE is published (in the wiki/mailing list) everything will be made public.
215 14:21 <sipa> lightlike: it's a very ad-hoc process really
216 14:23 <robot-visions> Thanks again everyone! I haven't seen fuzzing before, it's really interesting. Hope to see you at a future session.
217 14:23 <theStack> interestingly enough there still seem to be listening nodes that are vulnerable to this (looking at the user agents on bitnodes.io)
218 14:24 <emzy> Also altcoins may be on old versions.
219 14:25 <sipa> theStack: there are still nodes with code from 2013? :s
220 14:25 <emzy> But i think there was enought time to update for both.
221 14:27 <MarcoFalke> I think the issue with making CVEs public is mostly people forgetting about them
223 14:28 <MarcoFalke> Obviously you can't make them public on the first day they are discovered, and if the time has passed to make them public, they might be forgotten about
224 14:29 <theStack> sipa: well according to that site five nodes still are on 0.8.x
225 14:29 <theStack> x >= 5 though... this CVE was fixed in 0.8.4, so they are at least not vulnerable to this
226 14:30 <lightlike> I'd guess the finder would like attribution - even if there are no bounties, finding a CVE in core seems like something to be proud of.
227 14:31 <lightlike> at least if they are not a regular
228 14:32 <MarcoFalke> Everyone who reports an issue to the security email of Bitcoin Core will get mentioned in the release notes of the release that fixed it
230 14:40 <sipa> that's my guess
231 14:44 <lightlike> Internally to the fuzzer, there is also "PersAutoDict" that you see in the output: "Persistent dictionary modified by the fuzzer, consists entries that led to successfull discoveries in the past mutations."
232 15:01 <jonatack> yes, in the mutation operations output, e.g. MS: 3 ChangeBit-PersAutoDict-EraseBytes- DE: "\xdf\...
233 15:02 <jonatack> lightlike: thanks, what doc are you quoting from?
234 15:03 <lightlike> jonatack: I googled for PersAutoDict, and this is a code comment from libfuzzer
236 15:09 <jonatack> lightlike: thanks -- the code confirms that DE is for Dictionary Entry too