java-topology/whitepaper/outreach/amarok.md

Amarok — CWE-407 Disclosure Brief

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

Finding

Two O(n²) defects in Amarok's playlist system: one in the track queue navigator and one in the grouping proxy model. Both patched. Patches ready for upstream review.

The Defects

amarok-0001 (PATCHED — MEDIUM): src/playlist/navigators/TrackNavigator.cpp:44

// In queueIds() — fires when user queues selected tracks:
if( !m_queue.contains( id ) )  // QQueue::contains() — O(Q) linear scan
    m_queue.enqueue( id );

m_queue is QQueue<quint64>. contains() is a linear scan over the underlying QList. When queueing N tracks into a queue of size Q, total cost reaches O(N×Q). Additionally, slotRowsAboutToBeRemoved() calls m_queue.removeAll() in a loop over removed rows — O(R×Q).

amarok-0002 (PATCHED — MEDIUM): src/browsers/playlistbrowser/QtGroupingProxy.cpp:514

// In mapFromSource() — fires per item during model refresh:
QMapIterator<quint32, QList<int>> iterator( m_groupMap );
while( iterator.hasNext() ) {
    iterator.next();
    if( iterator.value().contains( sourceRow ) )  // O(S) per group
    { groupRow = iterator.key(); break; }
}

Maps a source row to a proxy index by iterating all groups and calling QList::contains(sourceRow) on each — O(G×S) where G = group count, S = average group size. Called per-item during model refresh. modelRowsRemoved() and modelRowsAboutToBeRemoved() have similar nested linear scans.

Complexity Proof

amarok-0001: At Q=1,000, N=1,000:

• Defective: 999 + 998 + ... ≈ 500,000 comparisons to queue 1,000 tracks
• Fixed: 1,000 comparisons (QSet shadow)
• ~250× op reduction. Fires on every queue operation.

amarok-0002: At G=50 groups, S=100 items per group:

• Defective: 50 × 100 = 5,000 comparisons per mapFromSource() call
• Fixed: 1 hash lookup per call (QHash reverse map)
• ~50× op reduction per model refresh.

Impact

Amarok is a music player with deep playlist management, grouping, and queue features. Users with large music collections (thousands of tracks) who queue selections or use grouped playlist views hit both paths regularly. amarok-0001 fires on every batch-queue operation; amarok-0002 fires during every playlist model refresh when grouping is active.

The Fix

amarok-0001: Add QSet<quint64> m_queueSet as a shadow index alongside m_queue:

// Before
if( !m_queue.contains( id ) )
    m_queue.enqueue( id );

// After
// CWE-407 fix: QSet shadow for O(1) contains() instead of O(Q) QQueue scan.
if( !m_queueSet.contains( id ) )
{
    m_queue.enqueue( id );
    m_queueSet.insert( id );
}

amarok-0002: Add QHash<int, quint32> m_sourceRowToGroup reverse map:

// Before
QMapIterator<quint32, QList<int>> iterator( m_groupMap );
while( iterator.hasNext() ) { ... iterator.value().contains( sourceRow ) ... }

// After
// CWE-407 fix: reverse map for O(1) source-row-to-group lookup.
int groupRow = m_sourceRowToGroup.value( sourceRow, -1 );

Patch

Fix available: defects/amarok/patch/amarok-0001-tracknavigator-queue-contains.patch and defects/amarok/patch/amarok-0002-qtgroupingproxy-groupmap-indexof.patch

Two-file patch across TrackNavigator.cpp/.h and QtGroupingProxy.cpp/.h.

amarok-0001: ~250× speedup at Q=1,000, N=1,000. amarok-0002: ~50× speedup at G=50, S=100.

What We Ask

A patch is ready for review.

1. Confirm receipt and assign an issue reference (KDE/amarok).
2. Assess severity — amarok-0001 fires on every batch-queue operation; amarok-0002 fires on every grouped playlist refresh.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Amarok team in the public disclosure. Preferred acknowledgment format welcome.

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