What is Formal Verification without Specifications? A Survey on mining LTL Specifications
Daniel Neider, Rajarshi Roy · 2025
Read What is Formal Verification without Specifications? A Survey on mining LTL Specifications by Daniel Neider, Rajarshi Roy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16274.txt.
Introduction
Daniel Neider and Rajarshi Roy survey ways to learn formal specs from examples in a 2025 paper. Formal checks prove that a system acts as it should, but they need a spec written in exact logic. Writing that spec by hand is slow and prone to error. New work mines specs from sample runs of good and bad behavior. The survey homes in on one logic, Linear Temporal Logic, the standard tongue for specs of reacting systems.
The authors list recent mining methods and set them side by side. Methods draw on tools as wide as rule solvers, neural nets, and step-by-step search. Each fits a distinct set of needs and sample types. The survey maps those fits so working teams can pick a sound route. It closes a gap for staff who must check systems but lack a ready spec.
Catalog record
| CREATOR | Daniel Neider, Rajarshi Roy |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-16274
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
What is Formal Verification without Specifications? A Survey on mining LTL Specifications Daniel Neider, Rajarshi Roy Abstract Virtually all verification techniques using formal methods rely on the availability of a formal specification, which describes the design requirements precisely. However, formulating specifications remains a manual task that is notoriously challenging and error-prone. To address this bottleneck in formal verification, recent research has thus focussed on automatically generating specifications for formal verification from examples of (desired and undesired) system behavior. In this survey, we list and compare recent advances in mining specifications in Linear Temporal Logic (LTL), the de facto standard specification language for reactive systems. Several approaches have been designed for learning LTL formulas, which address different aspects and settings of specification design. Moreover, the approaches rely on a diverse range of techniques such as constraint solving, neural network training, enumerative search, etc. We survey the current state-of-the-art techniques and compare them for the convenience of the formal methods practitioners. TU Dortmund University, Dortmund, Germany, Center for Trustworthy Data Science and Security, University Alliance Ruhr, Dortmund, Germany Department of Computer Science, University of Oxford, Oxford, UK {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752¡/concept_id¿ ¡concept_desc¿Theory of computation¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation keywords Temporal logic, Passive learning † † runningtitle: A Survey on mining LTL Specifications † † runningauthor: D. Neider, R. Roy † † copyright: Daniel Neider and Rajarshi Roy † † relatedversion: Full version for published article [ 61 ] 1 Introduction Formal methods refer to the discipline of computer science that employs mathematically rigorous techniques to ensure the safe behavior of software, hardware, and cyber-physical systems. There have been countless success stories of formal methods, ranging over several application domains such as communication systems [ 28 , 55 ] , railway transportation [ 5 , 6 ] , aerospace [ 33 , 24 ] , and operating systems [ 79 , 47 ] , to name but a few. We refer the reader to the exceptional textbook by Baier and Katoen [ 7 ] for a comprehensive introduction. However, there is an important catch with verification techniques: they assume the availability of functional and usable specifications that precisely describe the design requirements. This assumption is often unrealistic as designing specifications, which had been primarily a manual task, proves not only to be tedious but also error-prone. Consequently, the availability of formal specifications is widely regarded as a major bottleneck in formal methods [ 2 , 11 , 76 ] . To overcome this limitation, recent efforts have focused on developing methods that can automatically generate specifications from examples of desired and undesired system behavior. Notably, a significant body of research has emerged that concentrates on learning specifications in Linear Temporal Logic (LTL). This focus on LTL is due to its dual benefits: mathematical precision and interpretability. The latter has recently become of increasing interest as it facilitates the application of LTL beyond formal verification to areas such as reinforcement learning, planning, and other AI-related domains [ 53 , 18 , 43 , 17 ] . This survey provides a comprehensive overview of the diverse body of work focused on learning LTL specifications. In the past decade, researchers have tackled this task from multiple perspectives, spanning various settings and methodologies. As summarized in Table 1 , these efforts can be differentiated based on their learning setup, methodology, and the guarantees they provide, offering a nuanced understanding of the field. We specifically focus on approaches addressing the passive learning problem , where the objective is to learn concise LTL formulas that accurately capture user-provided examples of a system’s behavior. These examples typically consist of two categories: positive (desirable) and negative (undesirable) system behaviors. However, in many practical scenarios, it is unrealistic to assume the availability of perfectly labeled examples for both classes. Real-world data is often noisy, making it challenging to accurately classify the data. Furthermore, in many safety-critical domains, such as autonomous vehicles and medical devices, obtaining negative examples may be infeasible or even risky (potentially harming humans). As a result, some approaches have explored less conventional settings, including noisy data and scenarios where only positive examples are available. The approaches summarized in Table 1 share a common thread: they employ search strategies to navigate the space of possible LTL formulas, although these strategies differ substantially in their methodology. Some approaches leverage off-the-shelf constraint solvers (e.g., SAT and SMT solvers) by carefully encoding the learning problem in propositional or first-order logic, while others employ specialized enumeration techniques tailored to the task. A third category of approaches harnesses advances in deep learning to identify promising LTL formulas. As a result, the search strategies, considered LTL fragments, and theoretical guarantees vary substantially. The remainder of this paper compares and contrasts the underlying principles of the aforementioned approaches, categorized into three distinct groups based on their search strategies. These categories comprise constraint-based, enumeration-based, and neural-network-based methods, which will be explored in Sections 4 , 5 , and 6 , respectively. Section 2 provides the required background on LTL and the learning problem we consider. Table 1 : Comparison of Related Works and Their Features. ‘Pos’ and ‘Neg’ refer to positive and negative examples, respectively; ‘SAT’, ‘MaxSAT’, ‘MILP’ refer to satisfiability, maximum satisfiability, and mixed-integer linear programming, respectively. Work Primary techniques LTL Fragments Classification Input Data Guarantees Neider and Gavran [ 60 ] , Riener [ 73 ] SAT full LTL perfect Pos+Neg sound, complete, minimal Camacho and Mcllraith [ 19 ] SAT full LTL perfect Pos+Neg sound, complete, minimal Raha et al. [ 69 ] enumerative search, dynamic programming comb. of directed LTL perfect/noisy Pos+Neg sound Arif et al. [ 3 ] Syntax-Guided Synthesis past-time LTL perfect Pos+Neg sound, complete, minimal Gaglione et al. [ 32 ] MaxSAT full LTL noisy Pos+Neg sound, complete, minimal Chou et al. [ 22 ] MILP, counterexample-guided full LTL perfect Pos only sound, complete Ghiorzi et al. [ 36 ] enumerative search full LTL perfect Pos+Neg sound, complete, minimal Ielo et al. [ 45 ] Answer Set Programming full LTL perfect Pos+Neg sound, complete, minimal Roy et al. [ 75 ] SAT, counterexample-guided full LTL perfect Pos only sound, complete, language minimal Valizadeh et al. [ 78 ] enumerative search, GPU acceleration full LTL perfect/noisy Pos+Neg sound Luo et al. [ 56 ] Graph Neural Network full LTL noisy Pos+Neg No Wan et al. [ 81 ] Graph Neural Network full LTL noisy Pos+Neg No 2 Preliminaries 2.1 System Executions and Words Informal methods, executions or trajectories of systems are typically formalized as sequences of symbols from a finite non-empty set \Sigma , known as alphabet. We refer to such sequences as words over \Sigma . A word w=a_{0}a_{1}\dots , where a_{i}\in\Sigma , can be either finite or infinite, depending on whether the execution it represents is finite or infinite. The set of infinite words over \Sigma is denoted by \Sigma^{\omega} , while the set of finite words is denoted by \Sigma^{*} . Given a word w=a_{1}a_{2}\dots in \Sigma^{\ast} or \Sigma^{\omega} , we let w[i]\coloneqq a_{i} denote symbol of w at position i and w[i:]\coloneqq a_{i}a_{i+1}\dots the suffix starting from the starting from position i . The length |w| of a word w is the number of its