YugabyteDB — CWE-407 Disclosure Brief

2026-03-27 · Patch available — awaiting upstream merge

Finding

One O(D×M×T) cubic defect in YugabyteDB's CDC stream management. The defect is in master/xrepl_catalog_manager.cc — the hot path for Change Data Capture stream setup and validation. Patched. Patch ready for upstream review.

The Defect

yugabyte-0001 (PATCHED — HIGH): master/xrepl_catalog_manager.cc:793

// Inside CDC stream loop — iterating D streams, M tables per stream:
// table_id is a protobuf repeated field (linear scan semantics)
auto it = std::find(stream.table_id().begin(), stream.table_id().end(), table_id);

std::find on a protobuf repeated string field performs an O(T) linear scan for each (stream, table) pair. The call sits inside a nested loop: for each of D CDC streams, for each of M tables in the master catalog, check T table IDs in the stream's protobuf field. O(D × M × T) cubic per catalog operation. At D=66 streams, M=tables, T=tables: 66× measured ratio.

Complexity Proof

Let:

D = number of CDC streams
M = number of tables in the master catalog
T = number of table IDs registered per CDC stream (T ≈ M in full-catalog CDC)

For each of D streams, the outer loop iterates M tables. For each table, std::find scans T entries in the protobuf repeated field:

Cost: D × M × T comparisons
When T ≈ M (all tables under CDC): D × M² — cubic in catalog size
Fixed (unordered_set<string> built once per stream): D × M comparisons — linear per stream, quadratic total

At D=66, M=100, T=100: defective=660,000 comparisons, fixed=10,000. Measured ratio: 66×.

This is a cubic defect (D×M×T) that becomes quadratic in M when T scales with M, and the 66× ratio was measured at a modest catalog size. Larger deployments with hundreds of tables compound the cost multiplicatively.

Impact

Every YugabyteDB deployment using CDC (Change Data Capture) for replication, audit logging, or downstream streaming hits this path during stream creation, validation, and catalog operations. YugabyteDB CDC is used in production for PostgreSQL-compatible change streaming to Kafka, Debezium, and custom consumers. Catalog operations involving CDC streams are invoked at stream creation time and during master leader failover, when all streams are re-validated. Clusters with many tables and many CDC streams hit the cubic worst case.

The Fix

yugabyte-0001: Build an unordered_set<string> from each stream's table IDs before the inner loop:

// Before
auto it = std::find(stream.table_id().begin(), stream.table_id().end(), table_id);
if (it == stream.table_id().end()) { ... }

// After
// CWE-407 fix: build unordered_set once per stream for O(1) lookup instead of O(T) std::find.
std::unordered_set<std::string> stream_table_ids(
    stream.table_id().begin(), stream.table_id().end());
if (stream_table_ids.count(table_id) == 0) { ... }

The set is constructed once per stream (O(T)) and all M table lookups within that stream's iteration are O(1). Total: O(D×(T+M)) instead of O(D×M×T).

Patch

Fix available: defects/yugabyte/patch/yugabyte-0001-xrepl-catalog-hashset.patch

Single-location change in master/xrepl_catalog_manager.cc. No behavioral change — set membership semantics match the existing linear scan exactly.

What We Ask

Confirm receipt and assign a GitHub issue or security advisory reference.
Validate the patch against CDC stream creation and catalog revalidation tests.
Coordinate a disclosure date — we are targeting 90 days from first contact.
We will credit the YugabyteDB team in the public disclosure. Preferred acknowledgment format welcome.

Contact: security@undefect.com. This brief is confidential until coordinated disclosure.

This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com

3.9 KiB Raw Permalink Blame History Unescape Escape