java-topology/whitepaper/outreach/thunderbird-0004.md

Thunderbird — CWE-407 Disclosure Brief (thunderbird-0004)

2026-04-13 · Patch available — awaiting upstream merge

Finding

One O(n²) defect in Thunderbird's IMAP UID state management. Linear Contains()/IndexOf() scans on a sorted UID array bypass the binary search already used elsewhere in the same file. Patched.

The Defects

thunderbird-0004 (PATCHED — HIGH): mailnews/imap/src/nsImapFlagAndUidState.cpp

// HasMessage() — linear scan on sorted array:
*result = fUids.Contains(uid);  // O(N) linear scan

// GetMessageFlagsByUid() — linear scan on sorted array:
int32_t ndx = (int32_t)fUids.IndexOf(uid);  // O(N) linear scan

The fUids array is maintained in sorted order. GetMessageFlagsFromUID() already uses IndexOfFirstElementGt() (binary search) correctly, but HasMessage() uses Contains() (linear) and GetMessageFlagsByUid() uses IndexOf() (linear) on the same sorted array.

Complexity Proof

thunderbird-0004: At N=50,000 UIDs:

• Defective: ~50,000 comparisons per call (linear scan)
• Fixed: ~16 comparisons per call (binary search)
• 500× overhead at N=50,000. Called per-message during IMAP folder sync.

Impact

This is HIGH severity. These functions fire per-message during IMAP folder synchronization. A folder with 50,000 messages triggers 50,000 linear scans through a 50,000-element sorted array, producing O(N²) total work during sync. Large enterprise mailboxes routinely contain tens of thousands of messages.

The Fix

thunderbird-0004: Use binary search (IndexOfFirstElementGt) already available in the same file:

// Before — O(N) per call
*result = fUids.Contains(uid);

// After — O(log N) per call
int32_t ndx = (int32_t)fUids.IndexOfFirstElementGt(uid) - 1;
*result = (ndx >= 0 && fUids[ndx] == uid);

Patch

Fix available: defects/thunderbird-0004/patch/thunderbird-0004_nsImapFlagAndUidState_Contains_linear_on_sorted.patch

Single-file patch in mailnews/imap/src/nsImapFlagAndUidState.cpp.

What We Ask

A patch is ready for review.

1. Confirm receipt and assign a Bugzilla reference (bugzilla.mozilla.org).
2. Assess severity — fires per-message during IMAP sync on large folders.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Thunderbird team in the public disclosure. Preferred acknowledgment format welcome.

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