💻 computer science

Compute-Budgeted Exploitability Evidence Graphs for Prospective Vulnerability Triage

This paper introduces a leakage-safe evaluation protocol and reproducible evidence certificates for prospective vulnerability triage, demonstrating that compute-budgeted evidence selection significantly improves recall over severity-only baselines while revealing that naive evaluation splits and semantic relevance alone can drastically inflate exploitability predictions.

Original authors: Faruk Alpay, Taylan Alpay

Published 2026-06-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Faruk Alpay, Taylan Alpay

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a firefighter in charge of a massive city with thousands of burning buildings (vulnerabilities). You only have enough water (computing power) to put out a few fires today. Your job is to decide which buildings are actually going to burn down the whole neighborhood and which ones are just smoking a little.

This paper is about building a better, fairer, and cheaper way to make those decisions without tricking yourself.

Here is the breakdown of their approach using simple analogies:

1. The Problem: Cheating with "Hindsight"

Most computer security programs try to predict which vulnerabilities will be attacked. The authors say these programs are often cheating.

The Analogy: Imagine a sports betting system that predicts who will win a game. If the system is allowed to look at the final score before making its prediction, it will look incredibly accurate. But that's not prediction; that's just reading the newspaper the next day.

In the security world, once a vulnerability is exploited (attacked), people start talking about it, writing code, and posting warnings. If a computer model is trained on these "post-attack" conversations to predict the attack, it is leaking the future. It's like the sports bettor looking at the scoreboard. The authors found that if you don't stop this "cheating," your model looks 8.5 times better than it actually is.

2. The Solution: The "Time-Travel" Rule

To fix this, the authors created a strict rule: The "Decision Time."

The Analogy: Think of a judge in a courtroom. The judge can only use evidence that was presented before the gavel banged. They cannot use evidence that appears after the trial is over.

The authors set a specific "Decision Time" for every vulnerability. Their computer model is only allowed to look at public information (like news reports, hacker forum posts, or code fixes) that existed before that specific time. If a piece of evidence appeared even one second after the decision time, the model must ignore it. This ensures the model is truly predicting the future, not just reading the past.

3. The "Budget" and the "Certificate"

The authors also realized that security teams don't have infinite time to read every single document.

The Analogy:

The Budget: Imagine you are a detective with a strict rule: you can only read two files per case before making a decision. The authors' system is designed to pick the best two files out of thousands to make the most accurate guess. They found that reading just two documents is almost as good as reading sixty-four. This makes the process very cheap and fast.
The Certificate: In the real world, if a security expert says, "This building is dangerous," they need to show their work. The authors' system attaches a "receipt" or certificate to every risk score. This receipt lists exactly which two (or few) documents the computer read to make that decision. It proves the computer didn't cheat and allows a human to double-check the logic.

4. A Surprising Discovery: "Smarter" Isn't Always Better

The authors tried using a very advanced, complex AI (called a "cross-encoder reranker") to sort the documents.

The Analogy: Imagine you are looking for a needle in a haystack. You have a super-smart robot that can understand the meaning of every piece of hay. You think this robot will find the needle faster.
However, the authors found that this smart robot actually made things worse. Why? Because the robot got distracted by documents that sounded like the vulnerability but didn't actually prove it was being attacked. It was like the robot reading a news article about "fire" and thinking it was about the specific building on fire, when it was actually just a story about a candle.

The simple, fast method that just looked for the most relevant documents worked better than the complex, "smart" one.

5. The Bottom Line

The paper concludes that:

Don't cheat: If you let your model see the future (post-exploit chatter), your results are fake.
Keep it simple: You don't need to read thousands of documents; picking a few high-quality ones is enough.
Show your work: Every risk score should come with a "receipt" showing exactly what evidence was used, so humans can trust and verify the decision.

By following these rules, security teams can prioritize their limited resources on the threats that are actually about to happen, without wasting time on false alarms or cheating models.

Technical Summary: Compute-Budgeted Exploitability Evidence Graphs for Prospective Vulnerability Triage

Problem Statement
Defenders face a critical resource constraint: the volume of newly disclosed vulnerabilities (CVEs) far exceeds the capacity for prompt remediation. While severity scores like CVSS communicate technical impact, they correlate weakly with actual exploitation in the wild, leading to inefficient patching prioritization. Existing data-driven forecasting methods, such as the Exploit Prediction Scoring System (EPSS), aim to predict near-term exploitation but often suffer from a fundamental evaluation flaw: temporal leakage.

Standard exploit-prediction studies frequently feed models with public evidence (advisories, proof-of-concept code, hacker discourse) that becomes available after a vulnerability has already been exploited. This "leaks the future" into the training or evaluation data, artificially inflating model performance metrics. The paper argues that without a strict temporal protocol, evaluation measures hindsight rather than foresight, rendering reported accuracy misleading for prospective triage.

Methodology
The authors propose a leakage-safe prospective triage protocol that treats vulnerability prioritization as a constrained selection problem under a fixed compute budget.

Temporal Evidence Graph: Public evidence is organized as a temporal graph linking CVEs to heterogeneous, timestamped documents (NVD advisories, exploit archives, fix commits, and hacker-community discourse).
Decision Time and Admissibility: For each CVE, a decision time $\tau(v)$ is fixed (publication time + observation window $\Delta$ ). The protocol strictly admits only evidence documents with timestamps $ts(e) \leq \tau(v)$ . This ensures the model cannot access signals generated by the exploitation event itself.
Budgeted Selection: Instead of processing all available text, the system selects a limited number of evidence documents ( $B$ $B$ ) per CVE.
- A bi-encoder (E5-style) generates embeddings for CVE descriptions and evidence documents.
- A laminar matroid constraint governs selection: a global budget $B$ limits the total documents, while per-layer caps $\kappa$ ensure diversity across source types (e.g., preventing a certificate from being dominated by a single channel like NVD text).
- Selection is performed greedily based on similarity scores, which is proven to be optimal for this modular objective.
Risk Scoring and Certification: A calibrated logistic model aggregates features (severity, CWE-conditioned priors, and statistics of the selected evidence) to produce a risk score. Crucially, every score is paired with an auditable evidence certificate that explicitly lists the supporting signals, their timestamps, and source layers, allowing defenders to contest the ranking.
Ablation of Rerankers: The study evaluates a strong cross-encoder reranker but finds it counterproductive. While it improves semantic relevance, it tends to surface advisory restatements of the CVE description rather than distinct exploitation signals, thereby lowering prospective recall.

Key Results
Evaluated on 12,012 prospective CVEs against 457 known exploited positives (CISA KEV) and EPSS-high targets:

Leakage Penalty: A naive evaluation using random splits and unfiltered evidence inflates prospective recall@50 by 8.5× (0.044 vs. 0.005) and EPSS-high recall by 5.0×. This demonstrates that standard evaluation protocols hide massive temporal leakage.
Budget Efficiency: The proposed budgeted selection raises leakage-safe prospective recall@50 from a severity-only baseline of 0.010 to 0.026 (a 150% relative gain).
Diminishing Returns: The value of additional evidence saturates rapidly. A budget of only 2 evidence documents per CVE captures nearly all the value available up to a budget of 64, indicating that triage is "cheap" and relies on a few high-signal documents rather than deep scanning.
Reranker Impact: Adding a cross-encoder reranker decreased prospective recall to 0.016, confirming that semantic relevance to a CVE description is not a proxy for exploitation evidence.
Compute Economy: The bi-encoder selection path processes CVEs in ~0.0068 seconds, recovering approximately 1,197 top-ranked positives per GPU-hour (normalized).

Significance and Contributions
The paper's primary contribution is methodological rather than purely architectural. It establishes that the evaluation protocol is the dominant factor in exploitability prediction, not the ranking model itself.

Leakage-Safe Protocol: The authors provide a construction that eliminates temporal leakage by design, quantifying the "leakage penalty" that naive protocols silently incur.
Auditable Certificates: By attaching evidence certificates to risk scores, the work transforms a scalar prediction into a contestable security claim. This allows defenders to verify that a score is driven by corroborating signals across independent layers (e.g., official advisories + community discourse) rather than a single manipulated channel.
Cost-Effective Triage: The study demonstrates that high-value triage does not require massive compute budgets or complex reranking; a small, diverse set of pre-decision evidence is sufficient to outperform severity-based baselines significantly.

The authors conclude that future work should focus on authenticating evidence against adversarial seeding and refining the observation window $\Delta$ against operational patch deadlines, rather than simply scaling model complexity.