fuzz: make FuzzedDataProvider usage deterministic

martinus commented at 2:24 pm on December 9, 2023: contributor

There exist many usages of fuzzed_data_provider where it is evaluated directly in the function call. Unfortunately, the order of evaluation of function arguments is unspecified, and a simple example shows that it can differ e.g. between clang++ and g++: https://godbolt.org/z/jooMezWWY

When the evaluation order is not consistent, the same fuzzing/random input will produce different output, which is bad for coverage/reproducibility. This PR fixes all these cases I have found where unspecified evaluation order could be a problem.

Finding these has been manual work; I grepped the sourcecode for these patterns, and looked at each usage individually. So there is a chance I missed some.

fuzzed_data_provider
.Consume
>Consume
.rand

I first discovered this in #29013 (review). Note that there is a possibility that due to this fix the evaluation order is now different in many cases than when the fuzzing corpus has been created. If that is the case, the fuzzing corpus will have worse coverage than before.

Update: In list-initialization the order of evaluation is well defined, so e.g. usages in initializer_list or constructors that use {...} is ok.

DrahtBot commented at 2:24 pm on December 9, 2023: 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	vasild, ismaelsadeeq, achow101

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#29436 (net: call Select with reachable networks in ThreadOpenConnections by brunoerg)
#16545 (refactor: Implement missing error checking for ArgsManager flags by ryanofsky)

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.

fanquake requested review from dergoegge on Dec 9, 2023

ismaelsadeeq commented at 4:15 pm on December 9, 2023: member

Concept ACK

fuzz: make FuzzedDataProvider usage deterministic

There exist many usages of `fuzzed_data_provider` where it is evaluated directly in the function call.
Unfortunately, the order of evaluation of function arguments is unspecified. This means it can differ
between compilers/version/optimization levels etc. But when the evaluation order changes, the same
fuzzing input will produce different output, which is bad for coverage/reproducibility.

This PR fixes all these cases where by moving multiple calls to `fuzzed_data_provider` out of the
function arguments.

01960c53c7

martinus force-pushed on Dec 9, 2023

martinus renamed this:
~~fuzz/util: make FuzzedDataProvider & FastRandomContext usage deterministic~~
fuzz/util: make FuzzedDataProvider usage deterministic
on Dec 9, 2023

martinus renamed this:
~~fuzz/util: make FuzzedDataProvider usage deterministic~~
fuzz: make FuzzedDataProvider usage deterministic
on Dec 9, 2023

DrahtBot added the label Tests on Dec 9, 2023

martinus commented at 6:34 pm on December 9, 2023: contributor

I updated my PR by removing the changes that I did in initializer-lists. These were not necessary, evaluation order in these is well defined.

dergoegge commented at 11:58 am on December 11, 2023: member

Nice find!

I am wondering if this is worth it at this point, since we only fuzz with llvm based compilers. If we had infrastructure that was fuzzing with gcc (e.g. compiling with afl++’s afl-g++-fast) then this would clearly make sense. I think if we are going to care about this, we should also add a gcc fuzz CI job and have a linter (maybe a custom clang-tidy plugin?) that checks for dependence on evaluation order (which would probably be a good idea in any case).

martinus commented at 5:07 pm on December 11, 2023: contributor

I am wondering if this is worth it at this point, since we only fuzz with llvm based compilers.

I don’t know how stable the ordering is for llvm. If it stays like that it’s not a big deal I’d say, but it might change in future versions or with optimization levels?

As for stability with other compilers, in a different project I’m working on we run the fuzzing targets with the minimized corpus as unit tests, and this is done in the CI on all platforms. If that would make sense for bitcoin too, then the ordering becomes important again

dergoegge commented at 2:32 pm on December 12, 2023: member

I don’t know how stable the ordering is for llvm. If it stays like that it’s not a big deal I’d say, but it might change in future versions or with optimization levels?

Good point, I guess since the spec is unspecified they have the right to change it but I would still be surprised if they do. I’m not sure if there is a trivial way to check if they ever have.

in a different project I’m working on we run the fuzzing targets with the minimized corpus as unit tests, and this is done in the CI on all platforms

We do that too but only on linux and macos while compiling with clang. If we extend this to more platforms/compilers, we should have some kind of linter otherwise this is gonna be hard to maintain.

in src/test/fuzz/crypto.cpp:50 in 01960c53c7

45@@ -44,7 +46,9 @@ FUZZ_TARGET(crypto)
46                 if (fuzzed_data_provider.ConsumeBool()) {
47                     data = ConsumeRandomLengthByteVector(fuzzed_data_provider);
48                     if (data.empty()) {
49-                        data.resize(fuzzed_data_provider.ConsumeIntegralInRange<size_t>(1, 4096), fuzzed_data_provider.ConsumeIntegral<uint8_t>());
50+                        auto new_size = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(1, 4096);
51+                        auto x = fuzzed_data_provider.ConsumeIntegral<uint8_t>();

ismaelsadeeq commented at 1:32 pm on December 18, 2023:

Nit: use descriptive variable names for more clarity instead of single letters

 0diff --git a/src/test/fuzz/crypto.cpp b/src/test/fuzz/crypto.cpp
 1index aa478277e35..2fa2b109e55 100644
 2--- a/src/test/fuzz/crypto.cpp
 3+++ b/src/test/fuzz/crypto.cpp
 4@@ -23,8 +23,8 @@ FUZZ_TARGET(crypto)
 5   std::vector<uint8_t> data = ConsumeRandomLengthByteVector(fuzzed_data_provider);
 6   if (data.empty()) {
 7       auto new_size = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(1, 4096);
 8-        auto x = fuzzed_data_provider.ConsumeIntegral<uint8_t>();
 9-        data.resize(new_size, x);
10+        auto default_byte_value = fuzzed_data_provider.ConsumeIntegral<uint8_t>();
11+        data.resize(new_size, default_byte_value);
12   }
13
14   CHash160 hash160;
15@@ -47,8 +47,8 @@ FUZZ_TARGET(crypto)
16                   data = ConsumeRandomLengthByteVector(fuzzed_data_provider);
17                   if (data.empty()) {
18                       auto new_size = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(1, 4096);
19-                        auto x = fuzzed_data_provider.ConsumeIntegral<uint8_t>();
20-                        data.resize(new_size, x);
21+                        auto default_byte_value = fuzzed_data_provider.ConsumeIntegral<uint8_t>();
22+                        data.resize(new_size, default_byte_value);
23                   }
24               }
25
26diff --git a/src/test/fuzz/cuckoocache.cpp b/src/test/fuzz/cuckoocache.cpp
27index f8a5bde3e6f..7fb7568c2bb 100644
28--- a/src/test/fuzz/cuckoocache.cpp
29+++ b/src/test/fuzz/cuckoocache.cpp
30@@ -41,7 +41,7 @@ FUZZ_TARGET(cuckoocache)
31       if (fuzzed_data_provider.ConsumeBool()) {
32           cuckoo_cache.insert(fuzzed_data_provider.ConsumeBool());
33       } else {
34-            auto e = fuzzed_data_provider.ConsumeBool();
35+            auto element = fuzzed_data_provider.ConsumeBool();
36           auto erase = fuzzed_data_provider.ConsumeBool();
37           cuckoo_cache.contains(e, erase);
38       }
39diff --git a/src/test/fuzz/prevector.cpp b/src/test/fuzz/prevector.cpp
40index 76f2d31c4ec..42a2d409426 100644
41--- a/src/test/fuzz/prevector.cpp
42+++ b/src/test/fuzz/prevector.cpp
43@@ -263,7 +263,7 @@ FUZZ_TARGET(prevector)
44           test.clear();
45           break;
46       case 10: {
47-            auto n = prov.ConsumeIntegralInRange<size_t>(0, 32767);
48+            auto num_elements = prov.ConsumeIntegralInRange<size_t>(0, 32767);
49           auto value = prov.ConsumeIntegral<int>();
50           test.assign(n, value);
51       } break;

ismaelsadeeq commented at 1:35 pm on December 18, 2023: member

Good point, I guess since the spec is unspecified they have the right to change it but I would still be surprised if they do. I’m not sure if there is a trivial way to check if they ever have.

The order of evaluation issue is a characteristic of the C++ language standard. While the LLVM compiler might have a consistent order of evaluation, but generally compiler behavior could change, maybe we should not use the current LLVM behavior as validation for this but rather refer to the overall language standard, since it might change?

+1

we should have some kind of linter

While I agree that manually handling this is not easy to do, as I try searching some left out FuzzDataProvider undeterministic usages, I could not find any but that does not mean there isn’t, as I might miss some.

But overall I think this might be good intermediate steps towards ensuring that there are no usages of fuzzed_data_provider evaluated directly in function calls.

Might also be worth adding a note for this in https://github.com/bitcoin/bitcoin/blob/master/doc/developer-notes.md in a fuzzing section to caution against future addtions like #29013 (review).

Note that there is a possibility that due to this fix the evaluation order is now different in many cases than when the fuzzing corpus has been created. If that is the case, the fuzzing corpus will have worse coverage than before.

I dont think this will happen since since we only fuzz with llvm based compilers?

Looks good to me, just a single nit

in src/wallet/test/fuzz/coinselection.cpp:114 in 01960c53c7

110@@ -111,7 +111,7 @@ FUZZ_TARGET(coinselection)
111     GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);
112 
113     for (const OutputGroup& group : group_all) {
114-        const CoinEligibilityFilter filter(fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<uint64_t>());
115+        const CoinEligibilityFilter filter{fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<uint64_t>()};

ismaelsadeeq commented at 1:37 pm on December 18, 2023:

This is okay since the standard is left-to-right evaluation order for initializer-clauses within an initializer-list?

martinus commented at 10:52 am on December 22, 2023:

yes, order in initializer clauses are defined: https://eel.is/c++draft/dcl.init.list#4

martinus commented at 10:51 am on December 22, 2023: contributor

I actually found a way to get the compiler to produce a warning for these cases, but it is a bit tricky and has limitations: https://godbolt.org/z/GfzseM4q3

 0#include <iostream>
 1
 2class FuzzedDataProvider {
 3    static inline size_t m_unsequenced_warning_producer = 0;
 4public:
 5    bool ConsumeBool(size_t unused = ++m_unsequenced_warning_producer);
 6};
 7
 8void bar(bool, bool, bool);
 9
10int main() {
11    FuzzedDataProvider fdb;
12    bar(fdb.ConsumeBool(), fdb.ConsumeBool(), fdb.ConsumeBool());
13}

With gcc (but not clang) this produces a -Wsequence-point warning:

0<source>: In function 'int main()':
1<source>:13:62: warning: operation on 'FuzzedDataProvider::m_unsequenced_warning_producer' may be undefined [-Wsequence-point]
2   13 |     bar(fdb.ConsumeBool(), fdb.ConsumeBool(), fdb.ConsumeBool());
3      |                                               ~~~~~~~~~~~~~~~^~
4<source>:13:62: warning: operation on 'FuzzedDataProvider::m_unsequenced_warning_producer' may be undefined [-Wsequence-point]
5Compiler returned: 0

How it works:

Add a static counter variable to `FuzzedDataProvider
Add a default argument that uses ++ for the counter

That way a -Wsequence-point warning is triggered. This is also triggered for initializer lists, and gcc man page has some arguments why that is so.

in src/test/fuzz/system.cpp:54 in 01960c53c7

51             },
52             [&] {
53-                args_manager.ForceSetArg(fuzzed_data_provider.ConsumeRandomLengthString(16), fuzzed_data_provider.ConsumeRandomLengthString(16));
54+                auto str_arg = fuzzed_data_provider.ConsumeRandomLengthString(16);
55+                auto str_value = fuzzed_data_provider.ConsumeRandomLengthString(16);
56+                args_manager.ForceSetArg(str_arg, str_value);

maflcko commented at 1:41 pm on January 13, 2024:

nit: Obviously this is fine here, but in a function call where a copy was previously elided and now is not, due to a missing std::move, this can make code perform worse.

maflcko commented at 1:44 pm on January 13, 2024: member

I hacked together a quick clang-query, but it will catch too many false positives, so I guess hardcoding a list of class names and only checking those is a better alternative?

0match expr(anyOf(cxxConstructExpr(unless(isListInitialization())).bind("ctor"),callExpr().bind("fun")),
1allOf(hasDescendant(cxxMemberCallExpr(
2    unless(hasDeclaration(cxxMethodDecl(isConst()))),
3    callee(cxxMethodDecl(hasParent(recordDecl().bind("rd1"))))
4).bind("mc1")),
5hasDescendant(cxxMemberCallExpr(
6    unless(equalsBoundNode("mc1")),
7    callee(cxxMethodDecl(hasParent(recordDecl(equalsBoundNode("rd1")))))
8).bind("mc2"))
9))

https://godbolt.org/z/5Wb3Y3bzP

DrahtBot added the label CI failed on Jan 16, 2024

in src/test/fuzz/addrman.cpp:271 in 01960c53c7

268+                auto time_penalty = std::chrono::seconds{ConsumeTime(fuzzed_data_provider, 0, 100000000)};
269+                addr_man.Add(addresses, net_addr, time_penalty);
270             },
271             [&] {
272-                addr_man.Good(ConsumeService(fuzzed_data_provider), NodeSeconds{std::chrono::seconds{ConsumeTime(fuzzed_data_provider)}});
273+                auto addr = ConsumeService(fuzzed_data_provider);

vasild commented at 4:30 pm on January 17, 2024:

nit: all these variables can be const

in src/test/fuzz/addrman.cpp:298 in 01960c53c7

303-        /*max_addresses=*/fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, 4096),
304-        /*max_pct=*/fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, 4096),
305-        network,
306-        /*filtered=*/fuzzed_data_provider.ConsumeBool());
307+    auto max_addresses = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, 4096);
308+    auto max_pct = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, 4096);

vasild commented at 4:43 pm on January 17, 2024:

Unrelated to this PR, out of scope, but passing max_pct greater than 100 is pointless. AddrManImpl::GetAddr_() will behave as if 100 is passed. In addition to being useless and confusing this skews the input towards 100. That is, it will treat > 97% of the possibilities as 100 ((4097-100)/4097*100 = 97.6%).

in src/test/fuzz/connman.cpp:89 in 01960c53c7

89-                    /*max_addresses=*/fuzzed_data_provider.ConsumeIntegral<size_t>(),
90-                    /*max_pct=*/fuzzed_data_provider.ConsumeIntegral<size_t>(),
91-                    /*network=*/std::nullopt,
92-                    /*filtered=*/fuzzed_data_provider.ConsumeBool());
93+                auto max_addresses = fuzzed_data_provider.ConsumeIntegral<size_t>();
94+                auto max_pct = fuzzed_data_provider.ConsumeIntegral<size_t>();

vasild commented at 4:46 pm on January 17, 2024:

ditto and even worse because the range here is 0..2^64-1

vasild approved

vasild commented at 4:58 pm on January 17, 2024: contributor

ACK 01960c53c7d71c70792abe19413315768dc2275a

I think it is worth improving this even if currently we only fuzz with clang and even if clang has not changed orders before or due to compilation flags - this may happen in the future.

A clang-tidy plugin to enforce this would be nice but I do not see its absence as a blocker for this PR.

DrahtBot requested review from ismaelsadeeq on Jan 17, 2024

ismaelsadeeq approved

ismaelsadeeq commented at 12:17 pm on January 18, 2024: member

ACK 01960c53c7d71c70792abe19413315768dc2275a

DrahtBot commented at 0:38 am on June 13, 2024: contributor

🤔 There hasn’t been much activity lately and the CI seems to be failing.

If no one reviewed the current pull request by commit hash, a rebase can be considered. While the CI failure may be a false positive, the CI hasn’t been running for some time, so there may be a real issue hiding as well. A rebase triggers the latest CI and makes sure that no silent merge conflicts have snuck in.

vasild commented at 1:48 pm on June 20, 2024: contributor

Has two ACKs, @TheCharlatan, maybe you want to take a look at this since you :+1:’ed the OP.

maflcko commented at 7:06 am on July 26, 2024: member

Now that std::shuffle is used (https://github.com/bitcoin/bitcoin/pull/30396#issuecomment-2219886162), there is another possible point where a fuzz target is deterministic but behaves different based on the build context (stdlib, compiler, …).

(Not sure what to do, if anything, I just wanted to provide more context)

achow101 commented at 6:53 pm on September 4, 2024: member

ACK 01960c53c7d71c70792abe19413315768dc2275a

achow101 merged this on Sep 4, 2024

achow101 closed this on Sep 4, 2024

TheCharlatan referenced this in commit 69282950aa on Sep 16, 2024

TheCharlatan referenced this in commit dfe0cd4ec5 on Sep 16, 2024

martinus deleted the branch on Sep 19, 2024

fuzz: make FuzzedDataProvider usage deterministic #29043

Code Coverage

Reviews

Conflicts