Kevgraph orders software fixes to stop real exploits faster
KEVGraph: Exploitation-Aware Dependency Vulnerability Remediation
Cryptography and Security
Summary
Many tools find lots of security problems in software but don't tell users which ones hackers actually use most often. The authors show that popular ways to pick fixes, like sorting by severity scores, can delay fixing the most dangerous problems. They created Kevgraph, a system that looks at software dependencies and known actively exploited vulnerabilities to plan the smallest number of upgrades that remove those dangerous bugs early. Testing on thousands of real projects showed Kevgraph can fix real threats much faster and with fewer updates than current methods.
What this means in practice
- •For software development teams: Generate upgrade plans that prioritize fixing actively exploited vulnerabilities early within project dependency graphs.
- •For devops security engineers: Automate verification of compliance with CISA BOD 22-01 by producing machine-verifiable certificates of vulnerability remediation.
Authors
Daniel Okumu Omondi
Abstract
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.