tokio — CWE-407 Disclosure Brief

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

Finding

One O(n²) defect in tokio-util's AnyDelimiterCodec. The decode() method uses Vec<u8>::contains() — an O(D) scan — for every byte of input, causing O(n×D) overhead per decoded frame. Patch ready for upstream review.

The Defects

tokio-0001 (PATCHED — HIGH): tokio-util/src/codec/any_delimiter_codec.rs

// AnyDelimiterCodec::decode() — per byte of input:
fn decode(&mut self, buf: &mut BytesMut) -> Result<...> {
    for (i, b) in buf.iter().enumerate() {
        if self.seek_delimiters.contains(b) {  // O(D) Vec<u8> scan per byte
            ...
        }
    }
}
// O(n×D) total — n bytes × D delimiters

Vec<u8>::contains(b) performs O(D) linear scan for every byte of input. For n bytes and D delimiters: O(n × D) per decode call. Measured ratio: 16×.

Complexity Proof

For n=1000 bytes, D=16 delimiters:

O(n×D) = 16,000 comparisons per decode
Fixed: 256-entry [bool; 256] lookup table → O(n) per decode
16× measured ratio.

Impact

All tokio-util users using AnyDelimiterCodec — a codec for parsing protocols with multiple possible delimiter bytes (custom TCP protocols, multi-character line endings, binary protocols). Every byte of every frame decoded goes through this path. High-throughput tokio applications (network servers, protocol parsers) maximize n×D. tokio is the dominant async runtime for Rust; tokio-util is its companion utility library.

The Fix

Replace Vec<u8>::contains() with a 256-entry boolean lookup table:

// Before
if self.seek_delimiters.contains(b) {  // O(D) Vec scan per byte

// After
// CWE-407 fix: 256-entry lookup table for O(1) per byte instead of O(D) Vec scan.
struct AnyDelimiterCodec {
    delimiter_table: [bool; 256],  // pre-built from seek_delimiters
    ...
}
if self.delimiter_table[*b as usize] {  // O(1) table lookup

Patch

defects/tokio/patch/tokio-0001-any-delimiter-codec-table.patch

What We Ask

Confirm receipt and assign a GitHub Security Advisory or issue reference.
Validate the patch against your codec and delimiter test suite.
Assess CVE eligibility — fires on every byte decoded with AnyDelimiterCodec.
Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.

2.4 KiB Raw Permalink Blame History Unescape Escape