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 symbols. In particular, the empty word, denoted by \varepsilon , has length zero. 2.2 Linear Temporal Logic (LTL) The logic LTL [ 67 ] is the de facto standard for reasoning about executions, or sequences of events, of reactive systems. Typically, specific events in a system are abstracted using a set \mathcal{P} of propositions, which represent events or properties of interest in the system under consideration. A system execution is then modeled by a word over the alphabet \Sigma=2^{\mathcal{P}} , capturing the propositions that hold true at specific time points along the system’s execution. Given a set \mathcal{P} of propositions, the syntax of LTL formulas is defined inductively using the grammar \varphi\coloneqq p\in\mathcal{P}\mid\lnot\varphi\mid\varphi\lor\varphi\mid\lX\varphi\mid\varphi\lU\varphi, where \lnot (not) and \lor (or) are Boolean operators, while \lX (neXt) and \lU (Until) are so-called future-time temporal operators. Several derived Boolean operators, including \land (conjunction) and \rightarrow (implication), as well as temporal operators, such as \lF (Eventually), \lG (Always), \lW (Weak Until), and \lR (Release), are often added as syntactic sugar. Additionally, some works also incorporate past-time temporal operators, including \lP (Previously) and \lS (Since), which are past-time analogs of \lX and \lU , respectively. To define the semantics of LTL, one usually uses a “model relation”, denoted by \models , which captures when the suffix of a word w\in(2^{\mathcal{P}})^{\omega} starting at a position i\in\mathbb{N} satisfies an LTL formula \varphi . Formally, this relation is given as follows: \displaystyle\hskip 99.58464ptw,i\models p \displaystyle\text{ if and only if }p\in w[i] \displaystyle w,i\models\neg\varphi \displaystyle\text{ if and only if }w,i\not\models\varphi \displaystyle w,i\models\varphi_{1}\lor\varphi_{2} \displaystyle\text{ if and only if }w,i\models\varphi_{1}\text{ or }w,i\models\varphi_{2} \displaystyle w,i\models\lX\varphi \displaystyle\text{ if and only if }w,i+1\models\varphi \displaystyle w,i\models\varphi_{1}\lU\varphi_{2} \displaystyle\text{ if and only if }w,j\models\varphi_{2}\text{ for some $i\leq j$ and} \displaystyle\hskip 28.45274ptw,k\models\varphi_{1}\text{ for each $i\leq k0 , the goal is to learn an LTL formula \varphi that satisfies the following three conditions: (i) each w\in P satisfies \varphi , (ii) \varphi has size at most n , and (iii) there exists no other formula with the former two properties that implies \varphi . To tackle this problem, Roy et al. employ a counterexample-guided inductive synthesis loop [ 1 ] , which leverages negative examples to guide the learning algorithm towards a most specific LTL formula. In each iteration of the loop, the authors utilize one of the aforementioned SAT-based methods to construct a consistent LTL formula. This formula is then analyzed, and if necessary, used to generate a new negative example that directs the search towards a more specific formula. This iterative process continues until no formulas more specific than the current formula can be found, at which point the algorithm terminates. Chou et al. [ 22 ] propose learning LTL formulas from positive examples of high-dimensional data. They rely on domain specific non-convex cost functions involving the positive examples and LTL formulas to ensure that the prospective formula tightly describes the examples. To search for the prospective formula, they provide a joint encoding of the cost functions and the syntax DAG of LTL formulas using Mixed Integer Linear Programming (MILP). They rely on the MILP solver IPOPT [ 80 ] for their implementation. 5 Enumeration-Based Approaches The constraint-based approaches discussed in Section 4 provide a systematic method for learning arbitrary LTL formulas. However, the performance of these approaches is limited by the capabilities of the underlying solvers. The search techniques typically employed in the solvers are not optimized for learning LTL formulas, thus often leading to bottlenecks in scalability. As a result, recent works have started exploring alternative search strategies that are tailored to navigate through the search space of LTL formulas efficiently. These approaches search through relevant/interesting LTL formulas in a more targeted manner that results in scalability, typically at the expense of the minimality of the learned formulas. A prominent example of this approach is Scarlet, a tool developed by Raha et al. [ 69 , 70 ] that detects and accumulates common temporal patterns in a given sample. For instance, analyzing a sample consisting of a positive word u=\{p\}\{p\}\{q\}\{p\}\{r\}\{p\} and a negative word v=\{p\}\{p\}\{r\}\{p\}\{q\} , Scarlet extracts the formula \lF(q\wedge\lF(r)) , which captures the order in which the propositions q and r appear. By employing dynamic programming, the tool identifies a large number of such patterns, which are then translated into a simple yet expressive LTL fragment named directed LTL. Scarlet then combines a suitable selection of directed LTL formulas to construct a consistent formula using a novel procedure called Boolean subset cover. Unlike constraint-based approaches, Scarlet’s search strategy integrates syntax and semantics computations in a single, unified process, resulting in a more efficient and effective method for learning LTL formulas. Another notable example is the highly parallelized algorithm developed by Valizadeh et al. [ 78 ] , which is designed to leverage the processing power of Graphics Processing Units (GPUs). Their approach comprises two pivotal procedures: relaxed unique checks (RUCs) and divide and conquer (D&C). The RUCs procedure performs a bottom-up search through the syntax of LTL formulas, eliminating redundant formulas that exhibit the same behavior on the given sample. Since this procedure is resource-intensive, it cannot be easily extended to large samples. To mitigate this, the D&C procedure partitions the sample into smaller, manageable subsets on which RUCs can be applied in parallel. The resulting formulas can then be combined using Boolean combinations to generate one consistent LTL formula. Internally, Valizadeh et al.’s approach employs bit-vectors to encode the semantics of LTL formulas, which can be highly efficiently implemented on GPUs. By exploiting the parallel processing capabilities of GPUs, the authors achieve a significant speedup, making their approach perhaps the most scalable one of all. Ghiorzi et al. [ 36 ] propose a range of heuristics to expedite the enumeration of LTL formulas. Inspired by Riener [ 73 ] , the authors first employ an enumeration strategy based on partial DAGs to navigate the search space quickly. Then, they utilize LTL rewrite rules to eliminate equivalent and redundant formulas, leveraging rules such as \varphi\wedge\neg\varphi\equiv\mathit{false} and \neg\lF\varphi\equiv\lG(\neg\varphi) . Additionally, the authors efficiently eliminate tautologies and contradictions by alternately checking the satisfaction of enumerated LTL formulas on positive and negative examples. 6 Neural Network-Based Approaches Recent research also focuses on leveraging the optimized training capabilities of neural networks to achieve scalability in the LTL learning process. However, due to the inherent uncertainty of neural network training, these approaches lack theoretical guarantees regarding the consistency of the learned LTL formulas. Nonetheless, they can produce reasonably good LTL formulas from large, typically noisy datasets. The current approaches specifically exploit Graph Neural Networks (GNNs) [ 42 ] to learn LTL formulas. GNNs are a powerful neural architecture that learns vector representations of vertex and edge features, typically called embeddings. More formally, GNNs define a message-passing process between vertices in a graph, where each vertex aggregates information from its neighbors to update its own representation. This process is repeated several times, allowing the model to learn complex patterns and relationships between vertex and edge features. The critical insight to understanding the connection of LTL and GNNs is to view a word w=a_{1}a_{2}\dots a_{n} as a linear graph v_{1}\rightarrow v_{2}\dots\rightarrow v_{n} with n nodes. This representation allows associating a feature vector x_{i} to each node v_{i} that tracks the satisfaction of the different subformulas of a prospective LTL formula \varphi when evaluated at the i -position of an example (see the definition of the model relation on Page 4). By leveraging message passing, the satisfaction of the entire formula \varphi can be computed by aggregating the feature vectors of nodes v_{j} with j>i according to the semantics of LTL. Luo et al. [ 56 ] built upon the insight of representing words as linear graphs to train a GNN on a sample \mathcal{S}=(P,N) . Subsequently, the authors use the learned network weights to extract an LTL formula that closely approximates the behavior of the GNN on the given sample. Although Luo et al.’s work pioneered the use of GNNs for learning LTL formulas, it suffers from the limitation that the extracted LTL formula might accurately capture the behavior of the trained GNN. Wan et al. [ 81 ] address this shortcoming by introducing an enhanced architecture. In particular, the authors devise a faithful encoding of the LTL semantics within the GNN architecture, achieved through parametric constraints on the network weights. This innovative encoding ensures that a consistent LTL formula can always be reliably extracted from the trained GNN. 7 Other Settings Our discussion thus far has centered around the classical passive learning problem for LTL as defined in Definition 1 . However, several variants of this problem have been explored, each presenting unique challenges. In this section, we discuss three such extensions, highlighting their distinct characteristics and proposed solutions. 7.1 Mining LTL based on Templates A key property of Definition 1 is that it makes no restrictions on the syntactic structure of an LTL formula as long as this formula is consistent with the given sample. In practice, however, users sometimes want to incorporate domain knowledge into the learning process or must confine the solutions to specific LTL fragments. Unfortunately, the methods discussed in Sections 4 to 6 do not offer this level of fine-grained control and, thus, cannot be applied in such situations. To address this limitation, researchers have proposed methods that allow users to provide a partial formula, typically referred to as a template or sketch, where parts can be omitted (typically indicated by a question mark). In this framework, the task of a learning algorithm is then to infer the missing part of a template (or sketch) so that the completed formula is consistent with a given set of examples. Notable examples operating in this setting are the methods by Lemieux et al. [ 51 ] and Lutz et al. [ 57 ] . The former approach considers templates, called property types , in which question marks serve as placeholders for missing propositions. By contrast, the latter approach introduces so-called sketches in which placeholders can represent missing operators and even entire subformulas. For example, Li et al. [ 52 ] have developed a method to mine LTL specifications in the GR(1) fragment of LTL, using templates that include \lG\lF? , \lG(?\rightarrow\lX?) , and others. Similarly, Shah et al. [ 77 ] have focused on conjunctive LTL formulas built from a limited set of typical temporal properties collected by Dwyer et al. [ 27 ] . Another notable example is the work by Kim et al. [ 46 ] , which considers a set of interpretable LTL templates originating in software system development and seeks to infer formulas robust to noise in the input data. 7.2 Mining LTL from Natural Language One of the significant barriers to adopting temporal logic in practice is the limited expertise of practitioners and engineers in this area [ 44 , 40 ] . As a result, they often prefer to specify their requirements in natural language, which is more intuitive and accessible to them. Several research efforts have focused on bridging this gap by automatically extracting LTL formulas from natural language descriptions. Early approaches [ 30 , 50 , 64 , 37 , 39 ] achieved this by efficiently parsing English sentences to translate them into LTL and other temporal logic formulas. The advent of data-driven techniques has led to the development of neural-network-based methods [ 65 , 41 , 21 ] that rely on human-labeled pairs of natural language descriptions and corresponding logic formulas. More recently, researchers have begun to leverage the impressive natural language understanding capabilities of Large Language Models to enhance the translation capabilities further [ 25 , 66 , 54 , 31 ] , offering promise for more effective and efficient property specification. 7.3 Logics beyond LTL The widespread adoption of continuous-time logics, such as Signal Temporal Logic (STL), in the context of cyber-physical systems has spawned a significant body of research focused on learning specifications in STL. In fact, a comprehensive survey by Bartocci et al. [ 9 ] is dedicated entirely to this problem. Most of these works concentrate on learning formulas with a specific syntactic structure [ 13 , 14 ] or identifying time intervals for given STL formulas [ 4 , 49 , 48 ] . A handful of works also tackle the more general passive learning problem, where the goal is to learn STL formulas of arbitrary structure [ 59 , 63 ] . In addition to linear-time properties, there exist several works focusing on learning branching-time properties in Computation Tree Logic (CTL). For instance, Chan [ 20 ] addresses the problem of completing simple CTL templates, while Wasylkowski and Zeller [ 82 ] investigate inferring operational preconditions for Java methods in CTL. Recent research by Pommellet et al. [ 68 ] and Bordais et al. [ 16 ] demonstrate that constraint-based techniques can be used to learn not only CTL but also Alternating-time Temporal Logics (ATL), which extends CTL for multi-agent systems. Apart from LTL, STL and CTL, there is also research on learning formulas in other temporal logics, such as Metric Temporal Logic (MTL) [ 71 ] , and the Property Specification Language (PSL) [ 74 ] . 8 Conclusion This survey provides a comprehensive overview of the diverse research efforts focused on learning specifications in temporal logic, with a particular emphasis on Linear Temporal Logic. We systematically compared and contrasted these works based on their search strategies to navigate the vast space of possible formulas. Some approaches leverage off-the-shelf solvers, while others propose customized enumeration techniques or exploit advances in deep learning to facilitate the learning process. By synthesizing the strengths and limitations of these approaches, we aim to provide a roadmap for future research in this exciting and rapidly evolving field. Acknowledgements. Rajarshi Roy acknowledges partial funding by the ERC under the European Union’s Horizon 2020 research and innovation programme (grant agreement No.834115, FUN2MODEL) and Daniel Neider acknowledges funding by Deutsche Forschungsgemeinschaft (DFG) (grant number 459419731).