java-topology/whitepaper/outreach/scribus.md

Scribus — CWE-407 Disclosure Brief

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

Finding

Four O(n²) defects in Scribus across the style system, pattern collection, multi-select operations, and file saving. All patched. All use QList::contains() or QStringList::contains() inside loops — O(n) linear scan where QSet or QMap::contains() gives O(1) or O(log n).

The Defects

scribus-0001 (PATCHED — MEDIUM): scribus/scribusdoc.cpp:1198

// In getSortedStyleList — fires on style reorder/display:
if (!retList.contains(i))  // QList<int>::contains — O(N) per style
    retList.append(i);

Four identical functions (getSortedStyleList, getSortedCharStyleList, getSortedTableStyleList, getSortedCellStyleList) walk the style parent chain and accumulate indices using QList::contains() for dedup. O(N²) where N = style count. Additionally, inner while-loops walk up the parent chain with retList2.contains(pp) — O(depth²) per style.

scribus-0002 (PATCHED — MEDIUM): scribus/scribusdoc.cpp:3933

// In getUsedPatterns — fires on document save and export:
if (!results.contains(currItem->pattern()))  // QStringList::contains — O(R)
    results.append(currItem->pattern());

Pattern collection iterates all page items (I) checking results.contains(pattern) — O(R) where R = accumulated results. With 3 pattern names per item (fill, stroke, mask), total is O(3IR). Same pattern in getUsedPatternsSelection(), getUsedPatternsHelper(), and getPatternDependencyList().

scribus-0003 (PATCHED — MEDIUM): scribus/selection.cpp:194

// In Selection::addItems — fires on rubber-band select, Select All:
if (m_SelList.contains(item))  // QList<QPointer<PageItem>>::contains — O(M)
    continue;

Multi-select operations check each item against the existing selection with QList::contains(). O(N*M) where N = items to add, M = existing selection.

scribus-0004 (PATCHED — MEDIUM): scribus/plugins/fileloader/scribus{150,170,171}format/*_save.cpp

// In writeStyles — fires on every file save:
QList<QString> names = lists.charStyleNames();  // QMap::keys() → QList
if (!names.contains(charStyle.name()))  // QList::contains — O(N)
    continue;

Six sites across three file format savers (scribus150, scribus170, scribus171) convert QMap keys to QList then use QList::contains() for filtering. O(S²) per save where S = style count. The underlying QMap already supports O(log N) contains().

Complexity Proof

scribus-0001: At N=500 paragraph styles:

• Defective: 500 × 499 / 2 = ~125,000 linear scans
• Fixed: 500 hash lookups (QSet)
• ~250× speedup. Multiply by 4 for all style types.

scribus-0002: At I=2000 items, R=200 patterns:

• Defective: 3 × 2000 × 200 = 1,200,000 string comparisons
• Fixed: 3 × 2000 × 1 = 6,000 hash lookups
• ~200× speedup.

scribus-0003: At N=5000 items to add, M=2000 existing:

• Defective: 5000 × 2000 = 10,000,000 comparisons
• Fixed: 5000 × 1 = 5,000 hash lookups
• ~2000× speedup.

scribus-0004: At S=500 styles per save:

• Defective: 500 × 500 = 250,000 linear scans (× 6 sites)
• Fixed: 500 × log(500) ≈ 4,500 map lookups (× 6 sites)
• ~55× speedup per site.

Impact

Scribus serves the open-source desktop publishing community — book designers, magazine layouts, technical documentation, and print production. Professional template documents commonly carry 500+ paragraph and character styles inherited from house style guides. The style sorting defects (0001) and save filtering defects (0004) fire on every document load and save respectively. The pattern collection defect (0002) fires during export — the critical production step. The selection defect (0003) fires on every rubber-band select and Select All in complex layouts.

Long-form publishing workflows (books with hundreds of pages and inherited style hierarchies) compound all four defects: open document (0001), select objects (0003), export to PDF (0002), save (0004).

The Fix

scribus-0001: Add QSet<int> companion for O(1) dedup:

// Before
if (!retList.contains(i))
    retList.append(i);

// After
QSet<int> retSet;
if (!retSet.contains(i)) {
    retList.append(i);
    retSet.insert(i);
}

scribus-0002: Add QSet<QString> companion for O(1) pattern dedup:

QSet<QString> resultSet;
if (!resultSet.contains(currItem->pattern())) {
    results.append(currItem->pattern());
    resultSet.insert(currItem->pattern());
}

scribus-0003: Build QSet<PageItem*> before the add loop:

QSet<PageItem*> existing;
for (int i = 0; i < m_SelList.count(); ++i)
    existing.insert(m_SelList.at(i).data());
if (existing.contains(item)) continue;

scribus-0004: Use the existing QMap directly instead of converting to QList:

// Before
QList<QString> names = lists.charStyleNames();
if (!names.contains(charStyle.name()))

// After — O(log N) QMap lookup, no QList allocation
if (!lists.charStyles().contains(charStyle.name()))

Patch

Fixes available: defects/scribus/patch/scribus-0001-0004-*.patch

Four patches across scribusdoc.cpp (8 function sites), selection.cpp, and scribus{150,170,171}format_save.cpp (6 sites).

scribus-0001: 250× speedup at 500 styles. scribus-0002: 200× at 2000 items. scribus-0003: 2000× at 5000 items. scribus-0004: 55× per save at 500 styles.

What We Ask

Patches are ready for review.

1. Confirm receipt and assign a GitLab issue reference (scribusproject/scribus).
2. Assess severity — scribus-0004 fires on every file save; scribus-0001 fires on every document load.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Scribus team in the public disclosure. Preferred acknowledgment format welcome.

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