Finite-state models are widely used in software engineering, especially in control systems development. Commonly, in control applications such models are developed manually, hence, keeping them up-to-date requires extra effort. To simplify the maintenance process, an automatic approach may be used, allowing to infer models from behavior examples and temporal properties. As an example of a specific control systems development application we focus on inferring finite-state models of function blocks (FBs) defined by the IEC 61499 international standard for distributed automation systems. In this paper we propose a method for FB model inference from behavior examples, based on reduction to Boolean satisfiability problem (SAT). Additionally, we take into account linear temporal properties using counterexample-guided synthesis. In contrast to existing approaches, suggested method is more efficient and produce minimal finite-state models both in terms of number of states and guard conditions. We also present the developed tool fbSAT which implements the proposed method, and evaluate it in two case studies: inference of a finite-state model of a Pick-and-Place manipulator, and reconstruction of randomly generated automata.
@cite_26 , the method is proposed for inferring an FB model from given execution scenarios by means of translation to the Constraint Satisfaction Problem (CSP). However, has the following restrictions. Guard conditions are generated in form -- corresponding Boolean formulas depend on input variables. Such models do not generalize to unseen data. This is countered by greedy guard conditions minimization, but it does not guarantee the result minimality. @cite_15 is extended with a counterexample prohibition procedure similar to @cite_29 to account for LTL properties. Guard conditions are represented with fixed-size conjunctions of positive negative literals of input variables. The drawback of this approach is that it does not allow constructing models when temporal properties are poorly covered with behavior examples.
@cite_29 @cite_15 @cite_26
2408207366 2898670592 2770374269
Finite-state models, such as finite-state machines (FSMs), aid software engineering in many ways. They are often used in formal verification and also can serve as visual software models. The latter application is associated with the problems of software synthesis and automatic derivation of software models from specification. Smaller synthesized models are more general and are easier to comprehend, yet the problem of minimum FSM identification has received little attention in previous research. This paper presents four exact methods to tackle the problem of minimum FSM identification from a set of test scenarios and a temporal specification represented in linear temporal logic. The methods are implemented as an open-source tool. Three of them are based on translations of the FSM identification problem to SAT or QSAT problem instances. Accounting for temporal properties is done via counterexample prohibition. Counterexamples are either obtained from previously identified FSMs, or based on bounded model checking. The fourth method uses backtracking. The proposed methods are evaluated on several case studies and on a larger number of randomly generated instances of increasing complexity. The results show that the Iterative SAT-based method is the leader among the proposed methods. The methods are also compared with existing inexact approaches, i.e., the ones which do not necessarily identify the minimum FSM, and these comparisons show encouraging results. We developed an algorithm for inferring controller logic for cyber-physical systems (CPS) in the form of a state machine from given execution traces and linear temporal logic formulas. The algorithm implements an iterative counterexample-guided strategy: constraint programming is employed for constructing a minimal state machine from positive and negative traces (counterexamples) while formal verification is used for discovering new counterexamples. The proposed approach extends previous work by (1) considering a more intrinsic model of a state machine making the algorithm applicable to synthesizing CPS controller logic, and (2) using closed-loop verification which allows considering more expressive temporal properties. A method for inferring finite-state models of function blocks from given execution traces based on translation to the constraint satisfaction problem (CSP) is proposed. In contrast to the previous method based on a metaheuristic algorithm, the approach suggested in this paper is exact: it allows to find a solution if it exists or to prove the opposite. The proposed method is evaluated on the example of constructing a finite-state model of a controller for a Pick-and-Place manipulator and is shown to be significantly faster then the metaheuristic algorithm.