Towards Predicting Multi-Vulnerability Attack Chains in Software Supply Chains from Software Bill of Materials Graphs

1. Problem Statement

Current software supply chain security analysis relies heavily on Software Bill of Materials (SBOMs) and vulnerability scanners (e.g., Snyk, Trivy). However, these tools typically treat vulnerabilities as independent records (per-CVE), scoring them in isolation using metrics like CVSS or EPSS.

This approach fails to address a critical failure mode: cascaded attacks. In real-world scenarios, multiple vulnerabilities across different components often interact through dependency structures to create an exploitation path that is far more dangerous than the sum of its parts.

• The Gap: Static scanners report lists of vulnerable components but do not infer cross-component chains or the "chaining" of weaknesses (e.g., a low-severity issue in a library enabling a high-severity exploit in the main application).
• The Need: A shift from "scoring each CVE" to "learning interaction patterns constrained by the dependency graph" to predict multi-vulnerability attack chains.

2. Methodology

The authors propose a novel SBOM-driven graph-learning approach that models the supply chain as a heterogeneous graph rather than a flat list. The pipeline consists of four key steps:

A. Graph Construction (Evidence Graph)

The system converts vulnerability-enriched CycloneDX SBOMs into a heterogeneous graph (Knowledge Graph) with three node types and typed edges:

• Nodes:
  1. Components: Software packages/dependencies.
  2. CVEs: Known vulnerabilities.
  3. CWEs: Common Weakness Enumerations (planned for future implementation).
• Edges:
  • DEPENDS_ON: Between components (derived from SBOM).
  • HAS_VULNERABILITY: From components to CVEs (derived from scanner output).
  • HAS_CWE: From CVEs to CWEs (currently absent in the prototype due to pipeline limitations).
• Features: Nodes are enriched with metadata such as CVSS scores, severity indicators, dependency depth (direct vs. transitive), and software licenses.

B. Component Feasibility Check (HGAT Model)

To validate that the graph structure carries useful signals, the authors employ a Heterogeneous Graph Attention Network (HGAT).

• Task: Binary classification to determine if a component is associated with at least one known CVE (has-any-CVE).
• Mechanism: The HGAT uses an attention mechanism to weigh different edge types (dependencies vs. vulnerability links) differently, aggregating neighbor information.
• Purpose: This serves as a feasibility check and an ablation study to prove that dependency structure is necessary for accurate inference.

C. Cascade Discovery (MLP Link Prediction)

To address the scarcity of documented multi-vulnerability chains, the problem is reframed as CVE-pair link prediction.

• Task: Predict whether two distinct CVEs are likely to be co-exploited in a chained scenario.
• Model: A lightweight Multi-Layer Perceptron (MLP).
• Input Features: A 22-dimensional vector per CVE pair, including:
  • Per-CVE features: CVSS score, severity, year, exploitation status, reference count, CWE count (from NVD metadata).
  • Interaction features: CVSS difference, CVSS product, year gap, and a "both-exploited" indicator.
• Training Data: A seed set of 35 documented attack chains (extracted from public advisories and incident reports) yielding positive pairs, balanced against negative pairs (2:1 ratio).

D. Projection and Inspection

Predicted high-risk CVE pairs are projected back onto the SBOM dependency subgraphs. This allows analysts to visualize the specific components involved in a potential chain and prioritize triage.

3. Key Contributions

1. Novel Pipeline: A pipeline that converts CycloneDX SBOMs into heterogeneous graphs with typed nodes and edges, enabling relational reasoning over supply chains.
2. Feasibility Study: A demonstration that dependency structures carry learnable signals beyond local metadata, validated via an ablation study on the HGAT model.
3. Cascade Predictor: An MLP-based model that successfully learns a "co-exploitation prior" from scarce data, generating ranked candidate links for multi-step attack chains.
4. Analyst Workflow: A proposed inspection protocol that maps documented attack chains to SBOM subgraphs, supporting error analysis and top-$k$ evaluation.

4. Experimental Results

The models were evaluated on 200 real-world Python SBOMs from the Wild SBOMs dataset and a seed set of 35 documented attack chains.

• HGAT (Component Classification):
  • Accuracy: 91.03%
  • F1-Score: 74.02%
  • Ablation Impact: When DEPENDS_ON edges were masked (removed), the model's Recall dropped to 0.00%, proving that the model relies heavily on the relational dependency structure rather than just node-level metadata.
• MLP (CVE-Pair Prediction):
  • ROC-AUC: 0.93
  • Significance: The model clearly distinguishes between pairs of CVEs that are part of a documented chain and random non-chain pairs, despite the limited training data.

5. Significance and Future Work

Significance:
This work represents a paradigm shift in supply chain security, moving from static, isolated vulnerability scoring to dynamic, graph-based reasoning. It demonstrates that even with limited data on specific attack chains, machine learning can infer interaction patterns that static tools miss, potentially identifying critical risks that appear benign in isolation.

Future Work:

• End-to-End Integration: Connecting the HGAT embeddings directly into the MLP cascade predictor (currently they operate on disjoint data).
• Chain Assembly: Moving from pair prediction to assembling full multi-step attack chains.
• Data Expansion: Expanding the corpus of documented chains and implementing chain-level/temporal splits to better measure generalization.
• Schema Extension: Re-enabling CWE extraction to model weakness-type co-occurrence.
• Format Support: Extending ingestion to SPDX formats and ecosystems beyond Python.
• LLM Baselines: Evaluating Large Language Models (e.g., ReAct) as a complementary approach for reasoning over SBOM graphs.