russell@unturf.com
a7b08c7e05
solang-0001: add_external_functions emits_events Vec::contains O(F×E²) MEDIUM src/sema/external_functions.rs:93-103 — dedup accumulator Vec uses linear scan for each event per function; fix: IndexSet (already a dependency) for O(1) dedup tor/bitcoin/transmission/libtorrent/solc: CLEAN markers added after full scan Tor: nodes_have_common_family_id F=1-3 IDs, O(N×F²) ≈ O(9N), not scalable issue Bitcoin: TxGraph/sets throughout, no linear scan in hot paths Transmission: bitfields for piece tracking, sorted binary search for string table libtorrent: sorted vectors with lower_bound, DHT uses binary search on results solc: unordered_set/set throughout OverrideChecker, SMTEncoder, FunctionCallGraph
17 lines
1.4 KiB
Markdown
17 lines
1.4 KiB
Markdown
# CLEAN — Bitcoin Core
|
|
Scanned 2026-03-29 for CWE-407 (algorithmic complexity: O(N²) linear membership tests, O(2^D) diamond recursion).
|
|
|
|
## Scope
|
|
- `src/txmempool.cpp` / `src/txmempool.h` — mempool ancestor/descendant tracking
|
|
- `src/node/mini_miner.cpp` — MiniMiner block template builder
|
|
- `src/policy/packages.cpp` — package deduplication
|
|
- `src/net.cpp` — peer connection tracking
|
|
|
|
## Findings
|
|
- **Mempool ancestor/descendant tracking** — uses `CTxGraph::GetAncestors`/`GetDescendants` backed by `std::set` and hash maps (O(log N) per lookup). CLEAN.
|
|
- **`MiniMiner::DeleteAncestorPackage`** — `std::find` on `m_entries` vector to locate an ancestor before erase. `m_entries` is a sorted vector used purely for O(N log N) re-sort each iteration; the O(|ancestors|) find per removal is dominated by the O(E log E) sort already on that path. `m_entries_by_txid` (hash map) handles fast txid lookup. Effective complexity is O(E log E) per iteration. Not a scalable O(N²). CLEAN.
|
|
- **`policy/packages.cpp`** — uses `std::unordered_set<COutPoint>` for input dedup. CLEAN.
|
|
- **`net.cpp` `m_onion_binds`** — constant-size list (number of configured bind addresses). CLEAN.
|
|
- **Address management** — uses bucket-based hash tables throughout. CLEAN.
|
|
|
|
**Result: No actionable CWE-407 defects. Bitcoin Core uses hash-based sets and sorted structures for all scalable membership tests.**
|