Repository: bitcoin/bitcoin
File: src/test/fuzz/cluster_linearize.cpp (C++)

Code before:
        }
        assert(mask_shifted == 0);
        return subset;
    };

    /** Read any set of transactions from the provider (including unused positions). */
    auto set_fn = [&]() {
        auto range = (uint64_t{1} << sim.size()) - 1;
        const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
        TestBitSet set;
        for (DepGraphIndex i = 0; i < sim.size(); ++i) {
            if ((mask >> i) & 1) {
                set.Set(i);
            }
        }
        return set;
    };

    /** Propagate ancestor information in sim. */
    auto anc_update_fn = [&]() {
        while (true) {
            bool updates{false};
            for (DepGraphIndex chl = 0; chl < sim.size(); ++chl) {
                if (!sim[chl].has_value()) continue;
                for (auto par : sim[chl]->second) {
                    if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
                        sim[chl]->second |= sim[par]->second;
                        updates = true;
                    }
                }
            }
            if (!updates) break;
        }
    };

    /** Compare the state of transaction i in the simulation with the real one. */
    auto check_fn = [&](DepGraphIndex i) {
        // Compare used positions.
        assert(real.Positions()[i] == sim[i].has_value());
        if (sim[i].has_value()) {
            // Compare feerate.
            assert(real.FeeRate(i) == sim[i]->first);
            // Compare ancestors (note that SanityCheck verifies correspondence between ancestors
            // and descendants, so we can restrict ourselves to ancestors here).
            assert(real.Ancestors(i) == sim[i]->second);
        }
    };

    LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) {
        uint8_t command = provider.ConsumeIntegral<uint8_t>();
        if (num_tx_sim == 0 || ((command % 3) <= 0 && num_tx_sim < TestBitSet::Size())) {

Review comment (bug):
This doesn't mean mask is non-zero if non-empty, if that is the goal. Also, if it isn't, IntSan will notify about it:

```
echo 'AQAAAID+/v7+/v7+/n8=' | base64 --decode > /tmp/f.crash

UBSAN_OPTIONS="suppressions=$(pwd)/test/sanitizer_suppressions/ubsan:print_stacktrace=1:halt_on_error=1:report_error_type=1" FUZZ=clusterlin_ancestor_finder ./bld/bin/fuzz  -runs=1 /tmp/f.crash
```

```
INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 1905069321
INFO: Loaded 1 modules   (588821 inline 8-bit counters): 588821 [0x595f7228d4c8, 0x595f7231d0dd), 
INFO: Loaded 1 PC tables (588821 PCs): 588821 [0x595f7231d0e0,0x595f72c19230), 
./bld/bin/fuzz: Running 1 inputs 1 time(s) each.
Running: /tmp/f.crash
/root/fuzz_dir_yosan/scratch/fuzz_gen/code/src/test/fuzz/cluster_linearize.cpp:307:10: runtime error: unsigned integer overflow: 18446744073709551615 + 1 cannot be represented in type 'uint64_t' (aka 'unsigned long')
    #0 0x595f6f1275b0 in bitset_detail::IntBitSet<unsigned int> (anonymous namespace)::ReadTopologicalSet<bitset_detail::IntBitSet<unsigned int>>(cluster_linearize::DepGraph<bitset_detail::IntBitSet<unsigned int>> const&, bitset_detail::IntBitSet<unsigned int> const&, SpanReader&, bool) /root/fuzz_dir_yosan/scratch/fuzz_gen/code/bld/src/test/fuzz/./test/fuzz/cluster_linearize.cpp:307:10
    #1 0x595f6f1258e7 in clusterlin_ancestor_finder_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>) /root/fuzz_dir_yosan/scratch/fuzz_gen/code/bld/src/test/fuzz/./test/fuzz/cluster_linearize.cpp:758:24
    #2 0x595f6f79af21 in std::function<void (std::span<unsigned char const, 18446744073709551615ul>)>::operator()(std::span<unsigned char const, 18446744073709551615ul>) const /usr/lib/gcc/x86_64-linux-gnu/13/../../../../include/c++/13/bits/std_function.h:591:9
    #3 0x595f6f79af21 in test_one_input(std::span<unsigned char const, 18446744073709551615ul>) /root/fuzz_dir_yosan/scratch/fuzz_gen/code/bld/src/test/fuzz/util/./test/fuzz/fuzz.cpp:88:5
    #4 0x595f6f79af21 in LLVMFuzzerTestOneInput /root/fuzz_dir_yosan/scratch/fuzz_gen/code/bld/src/test/fuzz/util/./test/fuzz/fuzz.cpp:216:5
    #5 0x595f6ee6d9ef in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) (/root/fuzz_dir_yosan/scratch/fuzz_gen/code/bld/bin/fuzz+0x1a749ef) (BuildId: f97b222457dad4832e8ea607046fa79bfdcf7f64)
    #6 0x595f6ee554a3 in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) (/root/fuzz_dir_yosan/scratch/fuzz_gen/code/bld/bin/fuzz+0x1a5c4a3) (BuildId: f97b222457dad4832e8ea607046fa79bfdcf7f64)
    #7 0x595f6ee5b761 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) (/root/fuzz_dir_yosan/scratch/fuzz_gen/code/bld/bin/fuzz+0x1a62761) (BuildId: f97b222457dad4832e8ea607046fa79bfdcf7f64)
    #8 0x595f6ee87ca6 in main (/root/fuzz_dir_yosan/scratch/fuzz_gen/code/bld/bin/fuzz+0x1a8eca6) (BuildId: f97b222457dad4832e8ea607046fa79bfdcf7f64)
    #9 0x7fe88682a1c9  (/lib/x86_64-linux-gnu/libc.so.6+0x2a1c9) (BuildId: 282c2c16e7b6600b0b22ea0c99010d2795752b5f)
    #10 0x7fe88682a28a in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2a28a) (BuildId: 282c2c16e7b6600b0b22ea0c99010d2795752b5f)
    #11 0x595f6ee4fe94 in _start (/root/fuzz_dir_yosan/scratch/fuzz_gen/code/bld/bin/fuzz+0x1a56e94) (BuildId: f97b222457dad4832e8ea607046fa79bfdcf7f64)

SUMMARY: UndefinedBehaviorSanitizer: unsigned-integer-overflow /root/fuzz_dir_yosan/scratch/fuzz_gen/code/src/test/fuzz/cluster_linearize.cpp:307:10 


Code after:
void MakeConnected(DepGraph<BS>& depgraph)
{
    auto todo = depgraph.Positions();
    auto comp = depgraph.FindConnectedComponent(todo);
    Assume(depgraph.IsConnected(comp));
    todo -= comp;
    while (todo.Any()) {
        auto nextcomp = depgraph.FindConnectedComponent(todo);
        Assume(depgraph.IsConnected(nextcomp));
        depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
        todo -= nextcomp;
        comp = nextcomp;
    }
}

/** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
template<typename SetType>
SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader, bool non_empty)
{
    // Read a bitmask from the fuzzing input. Add 1 if non_empty, so the mask is definitely not
    // zero in that case.
    uint64_t mask{0};
    try {
        reader >> VARINT(mask);
    } catch(const std::ios_base::failure&) {}
    mask += non_empty;

    SetType ret;
    for (auto i : todo) {
        if (!ret[i]) {
            if (mask & 1) ret |= depgraph.Ancestors(i);
            mask >>= 1;
        }
    }
    ret &= todo;

    // While mask starts off non-zero if non_empty is true, it is still possible that all its low
    // bits are 0, and ret ends up being empty. As a last resort, use the in-todo ancestry of the
    // first todo position.
    if (non_empty && ret.None()) {
        Assume(todo.Any());
        ret = depgraph.Ancestors(todo.First()) & todo;
        Assume(ret.Any());
    }
    return ret;
}

/** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */
template<typename BS>
std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
{