Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Program Graph Learning for Software Vulnerability Analysis: A Survey

15 minute read

Published:

TL;DR: Finding security bugs used to mean static analysers, fuzzers and symbolic execution; increasingly it means graph learning over program entities. This survey organises the field around four tasks — detection, classification, localisation, repair — all formulated on one object, a typed program graph whose relations carry syntax, control flow, data flow, calls and dependence. It then reviews four method families: graph-based (Devign, ReVeal and successors), multimodal (graphs fused with text, slices and even images — CPG-guided slicing can cut the code an LLM must read by up to 90% while raising F1), LLM-assisted (retrieval-augmented, multi-agent, tool-assisted) and repair (from fix templates to CodeT5-style generators reaching 44% perfect patches). The closing challenge list is the part to remember: interpretability that is correlational rather than causal, cross-language collapse, label noise baked in by fix-commit mining, no standard benchmarks — and a genuinely new frontier, the security of AI-generated code and agent toolchains, where prompts, tool configurations and MCP files become supply-chain attack surfaces that graphs are well placed to model.
Paper: Program Graph Learning for Software Vulnerability Analysis: A Survey
Authors: Tong Yu† (Wuhan University), Junjie Wang† (Wuhan University), Ming Li (Zhejiang Normal University), Yuhang Hu, Junwei Hu, Xiantao Cai (Wuhan University), Wenbin Hu* (Wuhan University), Alessio Borgi (University of Cambridge & Sapienza University of Rome) — †equal contribution, *corresponding author
Journal: Transactions on Graph Intelligence and Network Applications (TGINA), published 9 September 2026 · open-access PDF
First page of the Program Graph Learning for Software Vulnerability Analysis survey
Paper preview: Program Graph Learning for Software Vulnerability Analysis: A Survey (Yu, Wang, Li et al., TGINA 2026).

In plain words: a program is not a string — it is a web of statements that pass values to each other, call each other and gate each other with conditions. Draw that web as a graph and a security bug becomes a pattern in the graph: a tainted value flowing to a dangerous function, a check that should sit on a path and does not. This survey is a field guide to everything built on that observation, from the first graph neural networks over code to today’s LLM agents arguing about whether a function is exploitable.

Why code wants to be a graph

The stakes are not abstract. The survey opens with the numbers: the global average cost of a data breach reached USD 4.88 million in 2024, and Cybersecurity Ventures projected global cybercrime damages of USD 10.5 trillion annually by 2025. One analysis of 348 open-source smart contracts put their maximum total value locked above USD 11.2 billion — code whose bugs are directly convertible into money. And because modern software is assembled from open-source components, a single vulnerability propagates through dependency networks, multiplying both attack surface and remediation cost.

The classical arsenal — static analysis, dynamic analysis, symbolic execution, fuzzing — has well-known failure modes: high false-positive rates, incomplete path coverage, weak modelling of deep program semantics, and limited reasoning across procedure boundaries. The bugs that slip through are precisely the ones that hinge on semantic conditions: a value that is attacker-controllable three calls upstream, a sanitisation check present on one path and absent on its twin.

This is where the graph view earns its place. A token sequence flattens exactly the structure that matters; a program graph keeps it. Control-flow edges reveal execution constraints, data-flow edges reveal value propagation, call edges stitch functions together — the graph mirrors how the program actually behaves, not how it reads.

The graph zoo, in one paragraph. Different parses expose different structure, and they are complementary rather than competing. The AST (abstract syntax tree) captures grammar; the CFG (control-flow graph) captures execution order; the DFG (data-flow graph) captures value propagation; the PDG (program dependence graph) captures which statements genuinely depend on which; and the CPG (code property graph) overlays several of these into one multi-relational structure — the de-facto standard substrate for learned vulnerability detection.
Pipeline from source code and datasets, through parsing tools, to an embedded program graph processed by message passing, feeding detection, classification, localisation and repair tasks
The generic pipeline (paper, Figure 1): source code is parsed into a program graph, nodes receive feature embeddings, message passing propagates information along typed edges, and the resulting representations drive four tasks — detection, classification, localisation and repair.

Four tasks, one formalism

The survey’s first contribution is organisational: every task in the field is a mapping out of the same typed graph. A program entity \(P\) — a function, file or project — becomes

\[ G_P=\big(V,\;\{E_r\}_{r\in R},\;X,\;R\big) \]

with \(V\) the program elements, \(X\) their features, and one edge set \(E_r\) per relation type \(r\) — syntactic, control-flow, data-flow, call, control- and data-dependence. If you have met relational message passing on heterogeneous graphs, this is the same machinery pointed at code: one adjacency matrix \(A_r\) per relation, propagation along all of them.

The four tasks then line up as three mappings of increasing ambition:

\[ \underbrace{h_\theta\big(X,\{A_r\}\big)\to c}_{\text{detection / classification}} \qquad \underbrace{g_\theta(G_P)\to s\in\{0,1\}^{n}}_{\text{localisation (per line)}} \qquad \underbrace{r_\theta(G_P,c,S)\to \Delta,\;\; P'=\mathrm{Apply}(P,\Delta)}_{\text{repair (patch generation)}} \]

Detection is the binary special case of classification (\(c=0\) benign, otherwise a CWE category). Localisation predicts which of the \(n\) physical source lines are implicated. Repair is the end of the ladder: generate edit operations \(\Delta\) — insert the missing check, replace the unsafe call, sanitise the tainted flow — whose application removes the vulnerability while preserving what the program was for. Read graph-theoretically, a repair is an edit that breaks the vulnerability-triggering dependence chain.

Four families of methods

The survey reviews the methods in four families, and the arc across them is the field’s recent history in miniature.

FamilyRepresentative methodsWhat it addsWhat it costs
Graph-basedDevign, ReVeal, ReGVD, IVDetectExplicit structure; GNNs over AST/CFG/DFG/CPGGraph construction time; mostly intra-procedural
MultimodalMGVD, GRACE, LLMxCPG, Vul-LMGNNsFuses graphs with text, slices, images, LLM contextAlignment overhead; redundant or noisy modalities
LLM-assistedVul-RAG, ProveRAG, VulTrial, Agent4VulExternal security knowledge; multi-step reasoningSensitive to retrieval quality; hallucination
RepairSimFix, TBar, VulRepair, ChatRepair, InferFixFrom flagging bugs to generating validated patchesDepends on templates, donors, tests, analysis quality

Graph-based methods established the substrate. Devign fused AST, CFG, DFG and the token sequence into one composite graph; ReVeal moved to code property graphs and, importantly, to realistic imbalanced data; ReGVD went the other way, building cheap token co-occurrence graphs to dodge the construction cost of full program analysis. The trade running through the whole family: richer graphs carry richer semantics and cost more to build — a real constraint at repository scale.

Multimodal methods accept that no single view suffices. MGVD’s three-channel fusion of AST, PDG and text lifts F1 by roughly 10 points over single-view baselines. Two results stand out for where the field is heading. GRACE injects graph structure into LLM prompts alongside retrieved demonstrations and reports F1 gains of at least 28.65% — structure helping a language model, not competing with it. LLMxCPG uses the CPG to slice the program first, cutting the code the LLM must read by 67.84–90.93% while improving F1 by 15–40%: the graph as a relevance filter for an expensive reasoner.

LLM-assisted methods make the language model the reasoning engine and vary what evidence reaches it. Retrieval-augmented approaches (Vul-RAG, ProveRAG, VulInstruct) feed it vulnerability knowledge, historical cases and CWE descriptions — ProveRAG adding provenance tracking and self-critique to keep conclusions supported. The multi-agent line is the most entertaining to read and addresses a real failure mode, one-sided judgement: VulTrial literally stages a courtroom, with agents arguing for and against a vulnerability finding before a verdict; Agent4Vul plugs GNN-derived structural features into the agent loop.

Repair methods close the loop. The lineage runs from donor-code and template approaches (SimFix, TBar) through mined fix patterns, to neural generators — VulRepair’s CodeT5-style model reaches 44% perfect predictions on 8,482 real-world vulnerability fixes, repairing 745 of 1,706 real vulnerabilities — and on to LLM-era systems that fold in feedback: ChatRepair converses with failing tests, InferFix grounds prompts in static-analysis reports, VulDebugger lets an agent compare expected against actual runtime state. The direction of travel is consistent: away from unconstrained generation, towards evidence-grounded, validation-aware patching.

The quiet thesis of the survey. The LLM wave did not retire program graphs — it repurposed them. In the strongest recent systems the graph no longer competes with the language model as an encoder; it disciplines it: selecting what the model reads (CPG-guided slicing), structuring what it is told (graph-aware prompts), and checking what it claims (static-analysis evidence, dependence-chain validation). Structure supplies the guarantees, the LLM supplies the reasoning.

The toolbox: datasets, parsers, frameworks

A survey is also a shopping list, and Section 4 of the paper is the field’s most complete one.

Datasets split along a line that matters more than size: synthetic versus real. NIST’s SARD and the derived Juliet suite inject over a hundred CWE types into clean code — broad coverage, but easier than reality. Real-world sets mined from Git history (BigVul, CVEFixes, ReposVul) supply scale and patch context, with a caveat the survey is blunt about: they label code by fix-commit diffs, and not everything a fix touches is the vulnerability, nor is everything it leaves alone benign. That caveat returns with force in the challenges below.

Graph construction tools set the ceiling on everything downstream — a model cannot reason over structure the parser never extracted. Joern is the standard integrated CPG builder (AST + CFG + PDG + DFG across ten-plus languages); CodeQL turns program graphs into a queryable relational model, beloved of variant analysis; Tree-sitter and ANTLR handle fast AST construction; LLVM and Frama-C serve C/C++ with high-precision flow graphs; WALA and Soot cover the Java ecosystem; Slither is purpose-built for Solidity contracts.

Frameworks round out the pipeline: graph learning libraries, Transformer stacks, LLM inference engines and RAG infrastructure, composed into end-to-end vulnerability-analysis systems.

Five open problems — and the new one

The survey closes with five challenges, and they interlock: fixing one in isolation tends to founder on the others.

  1. Interpretability is correlational, not causal. Explainers highlight where the model attends — salient nodes, attributed subgraphs — but an exploitable bug is a causal story: attacker-controlled data reaching a sink because a check is missing on a path. The survey argues for program-semantics-level explanations: minimal vulnerability-evidence subgraphs, cross-validated against static analysis, symbolic execution and taint tracking. From “where the model looks” to “why the bug exists”.
  2. Cross-language generalisation collapses. Models trained on one language learn its surface statistics — syntax shapes, API idioms — rather than language-agnostic vulnerability semantics, and fall over on unseen languages. Unified graph schemas and multilingual pretraining are the proposed way out.
  3. Label noise is structural. The fix-commit labelling shortcut teaches models patch patterns and project style instead of vulnerability semantics. The remedy is finer-grained supervision: vulnerable lines, critical variables, source-to-sink paths, verifiable test cases.
  4. No standard benchmark. Inconsistent subsets, splits and filters make results incomparable, and evaluation fixates on function-level binary accuracy while localisation quality, explanation faithfulness and repair effectiveness go unmeasured.
  5. AI-generated code and agents change the threat model. This is the challenge that reads like a dispatch from this year rather than a literature review. When agents read repositories, invoke tools, install dependencies and submit patches, vulnerabilities stop being purely human coding mistakes: generation bias, prompt contamination, unsafe tool invocation, dependency pollution, configuration hijacking. Prompt templates, context files, tool declarations and MCP configurations become supply-chain attack surfaces.
The security perimeter has moved. The survey's sharpest observation is that agent-driven development lifts security from the code-fragment level to the whole model–prompt–tool–configuration–environment–supply-chain stack — and that graphs remain the right tool for the enlarged problem. Alongside ASTs and CPGs for the code itself, it proposes modelling the agent's behaviour: action-sequence graphs, tool-invocation graphs, permission-access graphs, configuration-dependence graphs, supply-chain propagation graphs. Program dependence plus agent behaviour, one graph-driven governance loop.

Where this sits in the cybersecurity story

This post opens the Cybersecurity book, and a survey is the right doorway: one paper that shows the whole field through a single lens. The machinery comes from the GNN book — typed edges, relational message passing, graph-level readouts, the heterogeneous-graph toolkit — but the security domain supplies what benchmarks rarely do: relations with fixed, auditable semantics. A data-flow edge is not a learned similarity; it is a fact about the program, checkable by a compiler. That is why the structure survives the LLM era here more visibly than in most application domains: when your evidence must ultimately convince a security engineer, edges that mean something beat attention weights that merely light up.

It is also, candidly, a review — the contribution is the map, not a new model. But the map includes the first systematic framing I know of for graph-driven agentic software security, and that section alone is worth the read for anyone building with coding agents today.

✅ Key Takeaways

  • Vulnerability analysis is now a graph learning problem over typed program graphs \(G_P=(V,\{E_r\},X,R)\), with four tasks — detection, classification, localisation, repair — as mappings of increasing ambition out of the same object.
  • The graph representations are complementary, not competing: AST for syntax, CFG for execution order, DFG for value flow, PDG for dependence, CPG as the multi-relational overlay that became the field's standard substrate.
  • Across four method families the role of the graph has shifted: from encoder substrate (Devign, ReVeal) to discipline for LLMs — slicing their input (LLMxCPG: up to 90% less code, higher F1), structuring their prompts (GRACE: ≥28.65% F1 gain), and grounding their claims.
  • Repair closes the loop, from fix templates to neural generators (VulRepair: 44% perfect patches) to validation-aware LLM agents — the trend is evidence-grounded patching, not free generation.
  • The ecosystem is mature enough to build on: SARD/Juliet and BigVul/CVEFixes/ReposVul for data (mind the fix-commit label noise), Joern and CodeQL for graph construction.
  • Five interlocking open problems, the newest being agentic security: prompts, tool declarations and MCP configurations as supply-chain attack surfaces — with agent-behaviour graphs proposed as the analysis substrate.

References

You May Also Enjoy

The Standard Library Modules Worth Knowing Before You pip install

8 minute read

Published:

Python ships with a counter, a queue, a memoiser, a CLI parser, a test framework’s smaller cousin, and a JSON-safe date library already installed, most of what people reach for a package to solve is one import away.

Files and Context Managers: Why with Is Not Optional

9 minute read

Published:

A file object that falls out of scope without with does get closed eventually, but ‘eventually’ means whenever the garbage collector gets around to it, which is not a promise any program handling more than a handful of files can live with.

Errors and Exceptions: EAFP, the Hierarchy, and Reading a Traceback

9 minute read

Published:

Exceptions in Python are not exceptional. They are a normal control-flow mechanism that the language leans on so heavily that the idiomatic style is to try the operation and handle the failure, rather than check first, which is faster, shorter, and free of race conditions.