# Nmap — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

One O(P×K) defect in Nmap's service detection engine. `ServiceProbe::portIsProbable()` uses `std::find` over a `std::vector<u16>` of probable ports on every probe selection call during version scanning. For P probes and K probable ports per probe: **O(P×K)** total per scanned port. Fix: `unordered_set<u16>`. Patched. Measured ratio: 9×.

## The Defects

**nmap-0001 (PATCHED — HIGH):** `service_scan.cc`

```cpp
// ServiceProbe::portIsProbable() — called from nextProbe() per probe per scanned port:
bool ServiceProbe::portIsProbable(u16 portno) const {
    return std::find(probableports.begin(), probableports.end(), portno)
           != probableports.end();
    // O(K) std::vector<u16> scan per call
}

// nextProbe() — selects next probe for a port:
for (int i = 0; i < numprobes; i++) {       // O(P) probes
    if (probes[i]->portIsProbable(portno)) { // O(K) per probe → O(P×K) total
        return probes[i];
    }
}
```

`portIsProbable()` performs `std::find` over `probableports` — a `std::vector<u16>` of K probable port numbers — on every probe evaluation in `nextProbe()`. `nextProbe()` is called for each of P probes per scanned service port. Total: **O(P × K) per scanned port**. Fix: replace `std::vector<u16>` with `std::unordered_set<u16>` → O(1) `count()` per call. **Measured ratio: 9×.**

## Complexity Proof

Let P = number of service probes evaluated per port (nmap-service-probes defines ~150+ probes), K = number of probable port entries per probe (varies; typically 5–50 for well-known service probes), S = number of scanned ports per scan session.

- Defective: `std::find` O(K) per `portIsProbable()` call; called P times per port in `nextProbe()`.
  - Per port: O(P × K) comparisons.
  - Per scan: O(S × P × K) total.
- Fixed: `std::unordered_set<u16>` with O(1) `count()`.
  - Per port: O(P) calls each O(1) → O(P) per port.
  - Per scan: O(S × P) total.
  - Speedup per port: O(K).

At K=9 probable ports per probe (measured configuration): defective=9× more comparisons than fixed. **9× measured ratio.**

At K=50 (large probe with many probable ports, e.g., HTTP/HTTPS probes): **50× reduction.**

The `probableports` vector is constructed at parse time from `nmap-service-probes` and never mutated at runtime — it is an ideal candidate for a one-time hash set construction.

## Impact

All users running `nmap -sV` (service/version detection) — one of the most common Nmap invocations for network reconnaissance, asset inventory, and vulnerability scanning. Service detection probes are evaluated for every open port discovered in TCP/UDP scans. In a typical /24 subnet scan with service detection (`nmap -sV 192.168.1.0/24`), thousands of ports are evaluated, each triggering the O(P×K) probe selection loop.

The defect is worst for large nmap-service-probes files (custom enterprise probe databases) where both P and K are large.

## The Fix

Change `probableports` from `std::vector<u16>` to `std::unordered_set<u16>` in the `ServiceProbe` class:

```cpp
// Before
std::vector<u16> probableports;  // O(K) std::find scan per portIsProbable()

bool ServiceProbe::portIsProbable(u16 portno) const {
    return std::find(probableports.begin(), probableports.end(), portno)
           != probableports.end();  // O(K) — CWE-407
}

// After
// CWE-407 fix: unordered_set<u16> for O(1) membership test instead of O(K) std::find.
std::unordered_set<u16> probableports;

bool ServiceProbe::portIsProbable(u16 portno) const {
    return probableports.count(portno) != 0;  // O(1) amortized
}
```

No functional change. `probableports` is populated at parse time from `nmap-service-probes` and read-only during scanning — the hash set build cost is paid once at startup.

## Patch

`defects/nmap/patch/nmap-0001-service-probe-ports-unordered-set.patch`

## What We Ask

1. Confirm receipt and assign a security advisory reference (nmap/nmap).
2. Validate the patch against the service detection regression test suite.
3. Assess CVE eligibility — nmap-0001 affects every `-sV` scan invocation; large probe databases amplify the impact.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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