Graph-ESBMC-PLC: Formal Verification of Graphical PLCopen XML Ladder Diagram Programs Using SMT-Based Model Checking

2021-08-12 · Source: cs.CL updates on arXiv.org · Field: Technology & Digital — Software Development & Engineering, Robotics & Autonomous Systems, Artificial Intelligence & Machine Learning · Depth: Expert, extended

Summary

Graph-ESBMC-PLC extends the ESBMC-PLC formal verifier to support graphical PLCopen XML Ladder Diagram (LD) programs, addressing a critical gap where previous versions produced vacuous verification results. This extension introduces a Depth-First Search (DFS)-based resolver that accurately interprets the localId/refLocalId connection graph of graphical LD. It extracts rung paths as Boolean conjunctions of contacts and implements a three-tier I/O inference scheme for variable classification. A crucial design ensures SET coils are processed before RESET coils, aligning with IEC 61131-3 scan-cycle semantics. The implementation involved adding 274 lines of C++ code without modifying the existing ESBMC backend. Validation on 3 graphical LD programs from CONTROLLINO/OpenPLC Editor exports demonstrated successful generation of full GOTO Intermediate Representation (IR), with all programs verifying SAFE at k=2 in under 70 ms. The system also maintained zero regressions across 11 textual LD benchmarks.

Key takeaway

For automation engineers developing safety-critical systems with graphical Ladder Diagram programs, Graph-ESBMC-PLC provides a robust formal verification solution. You can now confidently use exports from tools like CONTROLLINO or OpenPLC Editor, obtaining sound safety proofs in under a second, where previous methods failed. Be aware that programs heavily relying on timer or trigger function blocks may still require future resolver extensions for full semantic preservation.

Key insights

Graph-ESBMC-PLC enables sound formal verification of graphical PLCopen XML Ladder Diagrams by resolving their connection graphs.

Principles

• Graphical LD logic is a directed graph of connections.
• Coil execution order is critical for latching semantics.
• I/O classification ensures sound verification.

Method

A DFS-based resolver traverses the localId/refLocalId graph from leftPowerRail to coils, extracting rung paths. It orders coils by rightPowerRail sequence and applies three-tier I/O inference.

In practice

• Use DFS to reconstruct logic from connection graphs.
• Prioritize SET coils over RESET coils in scan cycle.
• Classify I/O variables for accurate model checking.

Topics

• PLCopen XML
• Ladder Diagram
• Formal Verification
• SMT Model Checking
• ESBMC
• Depth-First Search

Code references

• CONTROLLINO-PLC/OpenPLC_examples
• esbmc/esbmc
• jubnzv/iec-checker

Best for: AI Scientist, Research Scientist, Automation Engineer

Related on AIssential

• ESBMC-PLC: Formal Verification of IEC 61131-3 Ladder Diagram Programs Using SMT-Based Model Checking — ESBMC-PLC enables formal verification of IEC 61131-3 ladder diagram programs using SMT-based model checking.
• Automating Geometry-Intensive Compliance Checking in BIM: Graph-Based Semantic Reasoning Framework — SGR-BIM uses a graph-driven framework to automate geometry-intensive BIM compliance checks, improving accuracy and interpretability.
• PhaseNet++: Phase-Aware Frequency-Domain Anomaly Detection for Industrial Control Systems via Phase Coherence Graphs — Phase information, often discarded, offers a complementary and powerful modality for ICS anomaly detection.
• I Built an AI That Modernizes Legacy COBOL — And Then Made It Prove Its Own Work — Separating correctness (compiler theory) from intent (LLM semantics) is key to reliable legacy code modernization.
• Typed Component Algebras for Simulated Annealing and Markov-Chain Monte Carlo — Decomposing SA/MCMC into a typed component algebra enables modular improvements and verifiable correctness.
• Reasoning about concurrent loops and recursion with rely-guarantee rules — Mechanically verified rely-guarantee rules enable compositional reasoning for concurrent loops and recursion without assuming atomic expression evaluation.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.CL updates on arXiv.org.