# UNDF: UNDF-2026-000000708
# nmap-0002 — nmap.cc merge_port_lists O(N²) ping-port dedup

## Ecosystem
nmap (C++)

## Severity
MEDIUM — startup/pre-scan, not per-packet, but triggered by user-provided port lists

## Location
`nmap.cc`
- `insert_port_into_merge_list` (~line 329): O(N) linear scan per insertion
- `merge_port_lists` (~line 343): calls `insert_port_into_merge_list` N1+N2 times
- `validate_scan_lists` (~line 419): calls `merge_port_lists` to combine SYN+ACK ping port lists

## Description

When `-PS` (SYN ping) and `-PA` (ACK ping) are both used with explicit port lists
(e.g. `nmap -PS1-65535 -PA1-65535 target`), `validate_scan_lists` calls
`merge_port_lists(syn_ping_ports, count1, ack_ping_ports, count2, ...)` to
produce a deduplicated combined list.

`insert_port_into_merge_list` performs a full O(N) linear scan on each call:

```c
static void insert_port_into_merge_list(unsigned short *mlist,
                                        int *merged_port_count,
                                        unsigned short p) {
  int i;
  // make sure the port isn't already in the list
  for (i = 0; i < *merged_port_count; i++) {   // O(N)
    if (mlist[i] == p) {
      return;
    }
  }
  mlist[*merged_port_count] = p;
  (*merged_port_count)++;
}
```

`merge_port_lists` calls this function (count1 + count2) times, so the total
cost is O((count1 + count2)²). With count1 = count2 = 65535 this is ~8.5 billion
operations (port values are uint16_t, max 65535).

## Fix

Use `std::unordered_set<uint16_t>` for O(1) membership test:

```cpp
--- a/nmap.cc
+++ b/nmap.cc
@@ -329,15 +329,6 @@
-static void insert_port_into_merge_list(unsigned short *mlist,
-                                        int *merged_port_count,
-                                        unsigned short p) {
-  int i;
-  // make sure the port isn't already in the list
-  for (i = 0; i < *merged_port_count; i++) {
-    if (mlist[i] == p) {
-      return;
-    }
-  }
-  mlist[*merged_port_count] = p;
-  (*merged_port_count)++;
-}
-
 static unsigned short *merge_port_lists(unsigned short *port_list1, int count1,
                                         unsigned short *port_list2, int count2,
                                         int *merged_port_count) {
-  int i;
-  unsigned short *merged_port_list = NULL;
-
-  *merged_port_count = 0;
-
-  merged_port_list =
-    (unsigned short *) safe_zalloc((count1 + count2) * sizeof(unsigned short));
-
-  for (i = 0; i < count1; i++) {
-    insert_port_into_merge_list(merged_port_list,
-                                merged_port_count,
-                                port_list1[i]);
-  }
-  for (i = 0; i < count2; i++) {
-    insert_port_into_merge_list(merged_port_list,
-                                merged_port_count,
-                                port_list2[i]);
-  }
+  std::unordered_set<uint16_t> seen;
+  seen.reserve(count1 + count2);
+  for (int i = 0; i < count1; i++) seen.insert(port_list1[i]);
+  for (int i = 0; i < count2; i++) seen.insert(port_list2[i]);
+
+  *merged_port_count = (int)seen.size();
+  unsigned short *merged_port_list =
+    (unsigned short *) safe_zalloc(seen.size() * sizeof(unsigned short));
+  int j = 0;
+  for (uint16_t p : seen) merged_port_list[j++] = p;
```

## Complexity

| Variant | Cost |
|---------|------|
| Before  | O((N1+N2)²) — up to ~8.5B ops at 65535+65535 |
| After   | O(N1+N2) — ~131K ops |
| Speedup | ~65000× at maximum port range |

## Notes
- `validate_scan_lists` is called once per scan invocation from `nmap_main`
- The defect only triggers when both `-PS` and `-PA` (or other overlapping
  ping probe types) are used with large port ranges
- The fix preserves all existing semantics; note that port order may change
  (iteration order of `unordered_set` is not guaranteed) but the code that
  consumes the merged list (`syn_ping_ports`) does not depend on order
