java-topology/docs/tickets/simplex-chat-0002-block-members-elem-linear-scan.md

simplex-chat-0002: APIBlockMembersForAll elem linear scan over member ID list

Target: simplex-chat/simplex-chat File: src/Simplex/Chat/Library/Commands.hs Lines: 2389, 2394 Severity: HIGH CWE: CWE-407 (Inefficient Algorithmic Complexity)

Description

APIBlockMembersForAll calls foldr' over all group members. For each member it tests groupMemberId \elem` memberIdswherememberIds :: NonEmpty GroupMemberId` — a plain list. O(M × K) per block/unblock command.

Same root cause as simplex-chat-0001. APIRemoveMembers already uses S.fromList + S.member (line 2428); block and role-change were missed.

Code

-- DEFECTIVE (lines 2389, 2394)
      selfSelected GroupInfo {membership} = elem (groupMemberId' membership) memberIds
      ...
            | groupMemberId `elem` memberIds =

Fix

      let gmIdSet = S.fromList (L.toList memberIds)
      selfSelected GroupInfo {membership} = S.member (groupMemberId' membership) gmIdSet
      ...
            | groupMemberId `S.member` gmIdSet =

Complexity

Before	After
O(M × K) per command	O(M + K) per command

Patch

defects/simplex-chat/patch/simplex-chat-0002.patch