KEVGraph: Exploitation-Aware Dependency Vulnerability Remediation
KEVGraph orders dependency upgrades so CISA KEV fixes precede higher-CVSS vulnerabilities.
KEVGraph is an eight-stage pipeline that turns dependency remediation into a KEV-aware set-cover problem using lockfiles, OSV, and the CISA KEV catalog. On 924 npm repositories covering 1,046 vulnerabilities and five KEV-listed packages, its ILP planner reached AUCCKEV 0.997, fixed the first KEV issue at step one, and needed 417 upgrades. CVSS-first and Dependabot-style ordering deferred that fix to step 18. Maven and PyPI evaluations reached AUCCKEV 0.988 and 1.000, and each plan includes a verifiable certificate for CISA BOD 22-01 checks.
- In the npm corpus, CVSS-first ordering deferred the first KEV fix by 17 upgrades.
- The ILP planner reached AUCCKEV 0.997 and fixed the first KEV at step one.
- It needed 417 upgrades, 15.9 percent fewer than the random mean.
- Results held across 924 npm, 1,200 Maven, and 300 PyPI repositories.
Full article247 words · extracted from arxiv.org · click to collapse
Dependency scanning tools surface hundreds of vulnerabilities but provide no exploitation-aware ordering, leaving practitioners to decide which upgrades to perform first with no principled guidance. The dominant practice, ordering by CVSS severity, is structurally misaligned with active exploitation: in our npm corpus, 186 non-KEV vulnerabilities carry CVSS scores greater than 8, all outranking three CISA Known Exploited Vulnerability (KEV)-listed packages and causing CVSS-first tools to defer the first actively exploited fix by 17 upgrade actions. KEVGraph is an eight-stage pipeline that frames remediation as a KEV-aware set-cover problem: it constructs per-repository dependency graphs from lockfiles, joins them against OSV and the CISA KEV catalogue, and produces a minimum-cardinality upgrade plan ordered to eliminate actively exploited vulnerabilities as early as possible via exact Integer Linear Programming (ILP) or a KEV-aware greedy algorithm. Evaluated on 924 real-world npm repositories (1,046 vulnerabilities, 5 KEV-listed), the ILP planner achieves AUCCKEV = 0.997 versus a random-baseline mean of 0.663 (95 percent CI [0.519, 0.831], n = 30), resolves the first KEV vulnerability at plan step 1, and requires only 417 upgrade actions, 15.9 percent fewer than the random mean of 495.4. CVSS-first and Dependabot-style ordering are strictly dominated: they defer the first KEV fix to step 18 while requiring more actions (419 and 421, respectively). The framework generalises: Maven (1,200 repos) achieves AUCCKEV = 0.988 versus random mean 0.486; PyPI (300 repos) achieves AUCCKEV = 1.000. Each plan is accompanied by a machine-verifiable certificate enabling automated compliance verification under CISA BOD 22-01.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.24164