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

## Finding

Two O(n²) defects in Jenkins' dependency graph construction and upstream project resolution. Both patched. Patches ready for upstream review. Jenkins is the dominant CI system in enterprise Java shops; the dependency graph rebuild fires thousands of times daily in large installations.

## The Defects

**jenkins-0001 (PATCHED — LOW):** `DependencyGraph.java:325`

```java
// In DependencyGraph.add() — called per dependency edge:
private List<DependencyGroup> groups = new ArrayList<>();
// ...
for (DependencyGroup g : groups) {
    if (g.matches(from, to)) {  // O(D) — linear scan per add
        g.add(dependency);
        return;
    }
}
groups.add(new DependencyGroup(from, to, dependency));
```

`groups` is `ArrayList<DependencyGroup>`. Linear scan on every `add()` call. With D dependency groups: **O(D²)** total during `rebuildDependencyGraph()`.

**jenkins-0002 (PATCHED — LOW):** `AbstractProject.java:1651`

```java
// In getBuildTriggerUpstreamProjects() — called per upstream project:
public List<AbstractProject> getUpstreamProjects() {
    // ...
    List<Job> childJobs = getChildJobs(ap);  // returns List<Job>
    if (childJobs.contains(this)) {          // O(D) — List.contains() scan
        upstreamProjects.add(ap);
    }
}
```

`getChildJobs()` returns `List<Job>`. `.contains()` is O(D) per call. O(U × D) total where U = upstream projects, D = dependency list size.

## Complexity Proof

**jenkins-0001:** For D dependency groups built during `rebuildDependencyGraph()`:
- Per `add()`: O(D) linear scan
- Total: **O(D²)**

`rebuildDependencyGraph()` is triggered on every job save, rename, delete, and plugin reload. In a Jenkins installation with 500 jobs and complex dependency chains, this fires thousands of times daily.

**jenkins-0002:** For U upstream projects and D dependencies:
- Per upstream check: O(D) `List.contains()` scan
- Total: **O(U × D)**

Fix: `parallel Map<AbstractProject, Map<AbstractProject, DependencyGroup>>` index for O(1) edge lookup; convert `getChildJobs()` result to `HashSet` before `contains()`.

**Measured: 39× speedup at N=80** (unit test).

## Impact

Jenkins is the dominant CI/CD system for enterprise Java development, with millions of installations worldwide. Large Jenkins installations have hundreds to thousands of jobs with complex dependency graphs (upstream/downstream project relationships used for pipeline orchestration).

`rebuildDependencyGraph()` fires on every job configuration change — every time a developer updates a Jenkinsfile, triggers a pipeline reconfiguration, adds/removes dependencies, or renames a job. In large development teams with many developers making changes throughout the day, this runs continuously.

jenkins-0002 affects the `build after other projects are built` trigger resolution — used in pipeline orchestration where one job starts another.

## The Fix

**jenkins-0001:** Replace `ArrayList<DependencyGroup>` linear scan with indexed `Map`:

```java
// Before
for (DependencyGroup g : groups) {
    if (g.matches(from, to)) { ... }  // O(D) scan
}

// After
// CWE-407 fix: Map<AbstractProject, Map<AbstractProject, DependencyGroup>> for O(1) lookup.
private Map<AbstractProject, Map<AbstractProject, DependencyGroup>> groupIndex = new HashMap<>();

DependencyGroup g = groupIndex
    .computeIfAbsent(from, k -> new HashMap<>())
    .get(to);
if (g != null) {
    g.add(dependency);
} else {
    DependencyGroup newGroup = new DependencyGroup(from, to, dependency);
    groupIndex.computeIfAbsent(from, k -> new HashMap<>()).put(to, newGroup);
    groups.add(newGroup);
}
```

**jenkins-0002:** Convert `getChildJobs()` result to `HashSet` before `contains()`:

```java
// Before
if (getChildJobs(ap).contains(this)) { ... }  // List.contains() O(D)

// After
// CWE-407 fix: HashSet for O(1) contains() instead of O(D) List scan.
if (new HashSet<>(getChildJobs(ap)).contains(this)) { ... }
```

## Patch

Fix available: `defects/jenkins/patch/jenkins-0001-0002-depgraph-map-index.patch`

Two-location patch across `DependencyGraph.java` and `AbstractProject.java`.

Unit test: **39× speedup at N=80**. `rebuildDependencyGraph()` growth confirmed: defective quadratic, fixed linear.

## What We Ask

A patch is ready for review.

1. Confirm receipt and assign a JIRA reference (issues.jenkins.io).
2. Assess severity — jenkins-0001 fires on every job save in large installations; D=500 jobs produces D²=250,000 comparisons per rebuild.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Jenkins team in the public disclosure. Preferred acknowledgment format welcome.

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