Researchers develop framework to convert code into comparable graph structures for verification reuse

A team of researchers has created a systematic approach to transform imperative programs and their annotations into machine-readable graph structures that can reveal similarities across different codebases. The work addresses a fundamental challenge in formal verification: reusing proven correctness proofs and specifications across multiple programs.

The Problem of Specification Reuse#

Formal verification—proving that software meets its specification—is time-consuming and expensive. If one team has already verified similar code, their work should ideally be reusable by others. However, this requires being able to identify which programs are structurally and semantically alike, a task complicated by the diversity of programming languages, annotation styles, and implementation details.

How the Pipeline Works#

The researchers developed a unified pipeline that converts code written in different languages into a common graph representation. Their approach combines two complementary techniques:

• Syntactic analysis: Parsing code into abstract syntax trees to capture its structure
• Semantic embeddings: Using pre-trained AI models—specifically SentenceTransformer and CodeBERT—to encode the meaning of code elements

The result is a typed, attributed graph where nodes and edges represent both the structural relationships between program elements and their semantic content.

Scope and Results#

The experiments covered multiple languages and annotation frameworks:

• C with ACSL (Annotated C Specification Language)
• Java with JML (Java Modeling Language)
• Dafny programs

Across these diverse datasets, the pipeline consistently produced comparable graph representations, demonstrating that the method generalizes across different programming paradigms and specification styles.

Implications for Verification#

This foundational work sets the stage for the next phase: approximate graph matching algorithms that could automatically identify similar programs and their corresponding specifications. If successful, such matching could dramatically accelerate verification efforts by allowing teams to adapt and reuse formal proofs across projects, ultimately making rigorous software guarantees more accessible and cost-effective.