# UNDF: UNDF-2026-000000453
# lldb-0001 — SerializedBreakpointMatchesNames O(B×N²) vector scan

**Severity:** MEDIUM
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)
**File:** `lldb/source/Breakpoint/Breakpoint.cpp` (line 222)
**Caller:** `lldb/source/Target/Target.cpp:CreateBreakpointsFromFile` (line 1266)
**Repo:** https://github.com/llvm/llvm-project

## Defect

`Breakpoint::SerializedBreakpointMatchesNames` receives a `std::vector<std::string> &names` filter list and checks each serialized breakpoint's name array against it using `llvm::is_contained`, which performs a linear scan of the vector.

```cpp
// lldb/source/Breakpoint/Breakpoint.cpp:242-248
size_t num_names = names_array->GetSize();

for (size_t i = 0; i < num_names; i++) {          // O(N_bp) per breakpoint
  std::optional<llvm::StringRef> maybe_name =
      names_array->GetItemAtIndexAsString(i);
  if (maybe_name && llvm::is_contained(names, *maybe_name))  // O(F) scan
    return true;
}
```

Called from `Target::CreateBreakpointsFromFile`:

```cpp
// lldb/source/Target/Target.cpp:1293-1307
for (size_t i = 0; i < num_bkpts; i++) {          // O(B)
  ...
  if (num_names &&
      !Breakpoint::SerializedBreakpointMatchesNames(bkpt_data_sp, names))
    continue;
  ...
}
```

**Total complexity:** O(B × N_bp × F) where:
- B = breakpoints in the JSON file
- N_bp = names on each serialized breakpoint
- F = size of the filter `names` vector

When restoring a large session (B=500 breakpoints, each with N_bp=20 names, F=50 filter names), this is 500 × 20 × 50 = 500,000 string comparisons instead of 500 × 20 = 10,000 with a hash set.

## Fix

Convert the `names` parameter from `std::vector<std::string>` to `llvm::StringSet<>` (or `std::unordered_set<std::string>`) before calling `SerializedBreakpointMatchesNames`, or accept a set directly.

```cpp
// Fixed: convert once before the loop in CreateBreakpointsFromFile
llvm::StringSet<> names_set(names.begin(), names.end());
// Then pass names_set to SerializedBreakpointMatchesNames
// Inside: names_set.count(*maybe_name) → O(1)
```

## Complexity

| Scenario | Before | After |
|----------|--------|-------|
| B=500, N_bp=20, F=50 | 500K string compares | 10K string compares |
| B=1000, N_bp=10, F=100 | 1M string compares | 10K string compares |

**Speedup at B=500, N_bp=20, F=50:** ~50x op-count reduction (ratio = F).
