okular-0001 — CWE-407: fontReadingGotFont O(F²) list dedup during font extraction

Target: Okular (KDE document viewer, C++/Qt) File: core/document.cpp — DocumentPrivate::fontReadingGotFont Severity: MEDIUM — affects documents with many fonts (academic PDFs, books) Speedup: 6.6x at F=500, 15.5x at F=1000

Defect

DocumentPrivate::fontReadingGotFont is called once per font by FontExtractionThread as it scans each page of our document. To avoid duplicates, it calls:

if (m_fontsCache.indexOf(font) == -1) {
    m_fontsCache.append(font);
    Q_EMIT m_parent->gotFont(font);
}

m_fontsCache is a QList<FontInfo>. indexOf is O(F) where F is our current cache size. Called F times total, this produces O(F²) string comparisons across our full font extraction run.

FontInfo::operator== compares six fields: name, substituteName, type, embedType, file, canBeExtracted. Each comparison walks up to six strings.

For a large PDF with 1000 fonts: ~500,000 equality checks during font loading. At F=1000 our simulation measured 8.7 ms vs 0.6 ms patched — 15.5x overhead.

MOAD Classification

MOAD-0001 (CWE-407, Sedimentary Defect): linear membership check inside a repeated-call hot path. Our indexOf is our list.contains inside our loop.

Fix

Add a parallel QSet<QString> m_fontsCacheKeys in DocumentPrivate. Before appending, compute a composite key from all six equality fields joined with | and check the set in O(1).

// document_p.h: add alongside m_fontsCache
QSet<QString> m_fontsCacheKeys;

// document.cpp: replace indexOf check
const QString key = font.name()
    + QLatin1Char('|') + font.substituteName()
    + QLatin1Char('|') + QString::number(static_cast<int>(font.type()))
    + QLatin1Char('|') + QString::number(static_cast<int>(font.embedType()))
    + QLatin1Char('|') + font.file()
    + QLatin1Char('|') + (font.canBeExtracted() ? QLatin1Char('1') : QLatin1Char('0'));
if (!m_fontsCacheKeys.contains(key)) {
    m_fontsCacheKeys.insert(key);
    m_fontsCache.append(font);
    Q_EMIT m_parent->gotFont(font);
}

Total complexity: O(F) for our full font extraction run.

Other MOADs Scanned

MOAD	Finding
0001 CWE-407	okular-0001 confirmed — fontReadingGotFont O(F²)
0002 Intertangle	`g_fieldCache`/`g_buttonCache` are process-global but keyed by pointer, cleared on ExecutorJS destruction — low risk in practice
0003 Leaked Context	`thread_local std::unordered_set<QString> pool` in `textpage.cpp` — short-string interning pool, grows without bound per worker thread but not request-scoped identity
0004 Logged Secret	No credential logging found. Passwords handled via KWallet, never reach debug output.
0005 Thundering Herd	No unsynchronized cache get+compute+put found. Font thread protected by `userMutex()`.

Patch

patch/okular-0001.patch

Test

test/test_okular_0001.py — PASS (6.6x at F=500, 15.5x at F=1000)

2.9 KiB Raw Permalink Blame History