# Open3D — CWE-407 Disclosure Brief

**Project:** Open3D
**Disclosure date:** 2026-03-27
**Severity:** HIGH
**Speedup:** 37.8× (open3d-0001), 4× (open3d-0002)
**Status:** PATCHED

---

## Finding

Two independent defects in Open3D use `std::find` on growing vectors for repeated set-membership checks in graph connectivity validation and RANSAC sampling. The first (open3d-0001) causes O(V²×E) behavior in pose graph connectivity validation. The second (open3d-0002) was flagged even by a developer comment — "Well, this is slow" — and causes O(S²) RANSAC sample deduplication.

## The Defect(s)

| ID | Location | Pattern | Complexity |
|----|----------|---------|------------|
| open3d-0001 | `cpp/open3d/pipelines/registration/GlobalOptimization.cpp:395` | `std::find` on component vector (V) inside while×edge loops in `ValidatePoseGraphConnectivity` | O(V²×E) |
| open3d-0002 | `cpp/open3d/geometry/PointCloudSegmentation.cpp:39` | `std::find` on growing samples vector in RANSAC rejection loop | O(S²) per RANSAC call × N iterations |

## Complexity Proof

**open3d-0001:** Let V = number of nodes (poses) in the pose graph, E = number of edges (constraints).

`ValidatePoseGraphConnectivity` implements a connectivity check using a union-find-like component vector, but instead of a proper union-find structure it uses `std::find` on the component vector to locate a node's component representative:

```
while (changes_made):            # up to V iterations
    for each edge (u,v) in E:    # E iterations
        std::find(component, u)  # O(V) scan
        std::find(component, v)  # O(V) scan
Total: O(V × E × V) = O(V²×E)
```

With an `unordered_set<int>` per component (or a proper union-find with path compression), each lookup is O(1) amortized: total O(V×E×α(V)) ≈ O(V×E). Measured speedup: 37.8×.

**open3d-0002:** Let S = number of samples drawn per RANSAC iteration, N = number of RANSAC iterations.

`RandomSampler::operator()` draws S unique random indices. To enforce uniqueness it calls `std::find` on the growing `samples` vector before each insertion:

```
Per RANSAC iteration:
  Insert sample 1: find in list of 0 → O(0)
  Insert sample 2: find in list of 1 → O(1)
  ...
  Insert sample S: find in list of S-1 → O(S-1)
  Per iteration: O(S²/2)
Total over N iterations: O(N×S²)
```

With `unordered_set<int>` for dedup tracking: O(N×S). Measured speedup: 4×. The developer comment in the source code — "Well, this is slow" — confirms awareness of the issue without a fix being applied.

## Impact

open3d-0001 affects all users of Open3D's multiway registration and SLAM pipelines that call `GlobalOptimization`. Pose graphs from large 3D reconstruction sessions (hundreds of frames, thousands of loop closure constraints) experience cubic validation time before optimization begins.

open3d-0002 affects all RANSAC-based geometry fitting (plane segmentation, primitive fitting) on point clouds. Since RANSAC runs N iterations, the O(S²) per-iteration overhead is multiplied by N, making large-cloud segmentation disproportionately slow.

## The Fix

**open3d-0001:** Replace the component vector + `std::find` pattern with a proper union-find (`std::unordered_map<int,int>` parent table with path compression and union by rank). Each component lookup and merge becomes O(α(V)) amortized.

**open3d-0002:** Replace the dedup `std::vector` in `RandomSampler` with `std::unordered_set<int>`. Track sampled indices in the set for O(1) rejection; collect results in a separate output vector.

## Patch

```diff
// open3d-0001: GlobalOptimization.cpp
- std::vector<int> component(n_nodes);
- std::iota(component.begin(), component.end(), 0);
- // ... std::find(component.begin(), component.end(), node) ...
+ // Union-Find with path compression
+ std::vector<int> parent(n_nodes);
+ std::iota(parent.begin(), parent.end(), 0);
+ std::function<int(int)> find = [&](int x) {
+     return parent[x] == x ? x : parent[x] = find(parent[x]);
+ };

// open3d-0002: PointCloudSegmentation.cpp
- std::vector<int> samples;
- // "Well, this is slow"
- while (samples.size() < k) {
-     int idx = rng() % n;
-     if (std::find(samples.begin(), samples.end(), idx) == samples.end())
-         samples.push_back(idx);
- }
+ std::unordered_set<int> seen;
+ std::vector<int> samples;
+ samples.reserve(k);
+ while (samples.size() < k) {
+     int idx = rng() % n;
+     if (seen.insert(idx).second)
+         samples.push_back(idx);
+ }
```

## What We Ask

Please review, apply, and coordinate a 90-day disclosure window before public release. Reply to security@undefect.com.

---

*This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com*
