CIR+CVN: Bridging LLM Semantic Understanding and Petri-Net Verification for Concurrent Programs
2026-04-10 • Programming Languages
Programming LanguagesFormal Languages and Automata Theory
AI summaryⓘ
The authors developed a method to help check and fix concurrent programs using models rather than raw source code, because direct analysis is hard due to complex programming practices. Their approach has a language model create a simplified, clear representation of the program (Cir), which is then converted into a formal Petri net model (Cvn) for thorough analysis. If problems are found, they map the issues back to the model to guide fixes and use checks to make sure repairs don’t remove important behaviors. They tested their method on common concurrency patterns and showed it helps find and fix bugs effectively. This process focuses on verifying the generated model, not the original code itself.
concurrencylarge language modelverificationConcurrency Intermediate RepresentationPetri netdeadlock analysisconcurrent program repairmodel checkingaliasinggoal reachability
Authors
Kaiwen Zhang, Guanjun Liu
Abstract
Recovering concurrency structure directly from source code is difficult because shared-resource identity and protection relations are often obscured by aliasing, ownership, and API-specific idioms. We therefore study a specification-driven, model-first verification architecture for LLM-assisted concurrent program construction. Instead of verifying arbitrary source code, a large language model first synthesizes a verification-oriented concurrency artifact from a natural-language requirement or system specification. The first formalism, the Concurrency Intermediate Representation (Cir), is a statement-level, alias-free model in which shared resources are globally named, protection relations are explicit, and each statement carries a stable identifier. The second formalism, the Concurrency Verification Net (Cvn), is a weighted place/transition Petri net with a finite global store and three-valued guards for data-dependent branching. A validated Cir artifact is translated mechanically to Cvn, explored exhaustively, and any counterexample is mapped back to statement identifiers to guide targeted repair. To reduce the risk of bug-free but behavior-dropping repairs, acceptance additionally applies a lightweight goal-reachability check over designated critical outcomes. We formalize both representations, prove translation-correspondence results for deadlock and signal-loss analysis, define a two-layer checking architecture with 61 static rules and 5 analysis predicates, and evaluate the pipeline on 9 representative bounded-concurrency patterns. The results show that the method supports iterative bug detection and repair on Cir artifacts and that goal reachability helps filter semantically incomplete repairs. The trust boundary of the present work is the generated Cir artifact rather than arbitrary source code.