# UNDF: UNDF-2026-000000556
## tomcat-0002 — CWE-407: Arrays.merge() ArrayList.contains() O(M×N) in Tribes member deduplication

**File:** `java/org/apache/catalina/tribes/util/Arrays.java`
**Method:** `merge(Member[] m1, Member[] m2)`
**Severity:** MEDIUM
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)

### Defect

`Arrays.merge()` builds a union of two `Member[]` arrays by adding elements of `m2`
into an `ArrayList` seeded with `m1`, guarding duplicates with `list.contains(member)`.
`ArrayList.contains()` is O(N) — it calls `member.equals()` against every element in
the list. The loop runs |m2| times, giving total complexity O(|m1| × |m2|).

```java
// DEFECTIVE — java/org/apache/catalina/tribes/util/Arrays.java:151-162
public static Member[] merge(Member[] m1, Member[] m2) {
    AbsoluteOrder.absoluteOrder(m1);
    AbsoluteOrder.absoluteOrder(m2);
    ArrayList<Member> list = new ArrayList<>(java.util.Arrays.asList(m1));
    for (Member member : m2) {
        if (!list.contains(member)) {   // O(N) scan per iteration → O(M×N) total
            list.add(member);
        }
    }
    Member[] result = list.toArray(new Member[0]);
    AbsoluteOrder.absoluteOrder(result);
    return result;
}
```

`MemberImpl` implements `hashCode()` (host byte sum) and `equals()` (host+port+uniqueId),
so membership in a hash-based set is safe and correct.

### Fix

Replace `ArrayList` with `LinkedHashSet` to make the dedup guard O(1).
Insertion order is not required (the result is re-sorted by `AbsoluteOrder.absoluteOrder`
before return), so `LinkedHashSet` is a safe drop-in.

```java
// FIXED
public static Member[] merge(Member[] m1, Member[] m2) {
    AbsoluteOrder.absoluteOrder(m1);
    AbsoluteOrder.absoluteOrder(m2);
    LinkedHashSet<Member> set = new LinkedHashSet<>(java.util.Arrays.asList(m1));
    for (Member member : m2) {
        set.add(member);   // O(1) — LinkedHashSet.add() is idempotent
    }
    Member[] result = set.toArray(new Member[0]);
    AbsoluteOrder.absoluteOrder(result);
    return result;
}
```

Import to add: `java.util.LinkedHashSet`

### Complexity

| | Before | After |
|---|---|---|
| merge() | O(|m1| × |m2|) | O(|m1| + |m2|) |

### Impact

`merge()` is called in the Tribes clustering layer to union member lists during
cluster topology updates. With N cluster nodes, repeated merges degrade to
O(N²) equality checks. At N=200 nodes (large WildFly/EAP cluster) this
produces a 200× overhead per topology update.

### Patch

```diff
--- a/java/org/apache/catalina/tribes/util/Arrays.java
+++ b/java/org/apache/catalina/tribes/util/Arrays.java
@@ -19,6 +19,7 @@ package org.apache.catalina.tribes.util;
 import java.nio.charset.StandardCharsets;
 import java.util.ArrayList;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.StringTokenizer;

@@ -151,9 +152,8 @@ public class Arrays {
     public static Member[] merge(Member[] m1, Member[] m2) {
         AbsoluteOrder.absoluteOrder(m1);
         AbsoluteOrder.absoluteOrder(m2);
-        ArrayList<Member> list = new ArrayList<>(java.util.Arrays.asList(m1));
+        LinkedHashSet<Member> set = new LinkedHashSet<>(java.util.Arrays.asList(m1));
         for (Member member : m2) {
-            if (!list.contains(member)) {
-                list.add(member);
-            }
+            set.add(member);
         }
-        Member[] result = list.toArray(new Member[0]);
+        Member[] result = set.toArray(new Member[0]);
         AbsoluteOrder.absoluteOrder(result);
         return result;
     }
```
