ADR-001: Linkset Correlation Algorithm V2

Status: Accepted Date: 2026-01-25 Sprint: SPRINT_20260125_001_Concelier_linkset_correlation_v2

This record explains why Concelier’s advisory linkset correlation moved from the V1 intersection algorithm to the V2 graph-based approach, and the scoring contract that change locks in. Read it before modifying correlation weights, conflict severities, or the linkset confidence model.

Context

The Concelier module’s linkset correlation algorithm determines whether multiple vulnerability observations (from different sources like NVD, GitHub Advisories, vendor feeds) refer to the same underlying vulnerability. The V1 algorithm had several critical failure modes:

  1. Alias intersection transitivity failure: Sources A (CVE-X), B (CVE-X + GHSA-Y), C (GHSA-Y) produced empty intersection despite transitive identity through shared aliases.

  2. Thin source penalty: A source with zero packages collapsed the entire group’s package score to 0, even when other sources shared packages.

  3. False reference conflicts: Zero reference overlap was treated as a conflict rather than neutral evidence.

  4. Uniform conflict penalties: All conflicts applied the same -0.1 penalty regardless of severity.

These issues caused both false negatives (failing to link related advisories) and false positives (emitting spurious conflicts).

Decision

We will replace the V1 intersection-based correlation algorithm with a V2 graph-based approach that:

1. Graph-Based Alias Connectivity

Replace intersection-across-all with union-find graph connectivity. Build a bipartite graph (observation ↔ alias nodes) and compute Largest Connected Component (LCC) ratio.

Rationale: Transitive relationships are naturally captured by graph connectivity. Three sources with partial alias overlap can still achieve high correlation if they form a connected component.

2. Pairwise Package Coverage

Replace intersection-across-all with pairwise coverage scoring. Score is positive when any pair shares a package key, even if some sources have no packages.

Rationale: “Thin” sources (e.g., vendor advisories with only CVE IDs) should not penalize correlation when other sources provide package evidence.

3. Neutral Reference Scoring

Zero reference overlap returns 0.5 (neutral) instead of emitting a conflict. Reserve conflicts for true contradictions.

Rationale: Disjoint reference sets indicate lack of supporting evidence, not contradiction.

4. Typed Conflict Severities

Replace uniform -0.1 penalty with severity-based penalties:

Conflict TypeSeverityPenalty
Distinct CVEs in clusterHard-0.4
Disjoint version rangesHard-0.3
Overlapping divergent rangesSoft-0.05
CVSS/severity mismatchSoft-0.05
Alias inconsistencySoft-0.1
Zero reference overlapNone0

Rationale: Hard conflicts (distinct identities) should heavily penalize confidence. Soft conflicts (metadata differences) may indicate data quality issues but not identity mismatch.

5. Additional Correlation Signals

Add high-discriminative signals:

6. V1/V2 Switchable Interface

Provide ILinksetCorrelationService with configurable version selection to enable gradual rollout and A/B testing.

Consequences

Positive

Negative

Neutral

Implementation

References