Hierarchical block diagrams (HBDs) are at the heart of embedded system design tools, including Simulink. Numerous translations exist from HBDs into languages with formal semantics, amenable to formal verification. However, none of these translations has been proven correct, to our knowledge. We present in this paper the first mechanically proven HBD translation algorithm. The algorithm translates HBDs into an algebra of terms with three basic composition operations (serial, parallel, and feedback). In order to capture various translation strategies resulting in different terms achieving different tradeoffs, the algorithm is nondeterministic. Despite this, we prove its semantic determinacy: for every input HBD, all possible terms that can be generated by the algorithm are semantically equivalent. We apply this result to show how three Simulink translation strategies introduced previously can be formalized as determinizations of the algorithm, and derive that these strategies yield semantically equivalent results (a question left open in previous work). All results are formalized and proved in the Isabelle theorem-prover.
@cite_33: Matlab Simulink is a widely used industrial tool for the development of embedded systems. Many of these systems are safety critical, especially in automotive industries. At the same time, automatic formal verification techniques for Simulink, in particular on model level, are rare and often suffer from scalability issues. In this paper, we present an automatic transformation of discrete-time Matlab Simulink models into the intermediate verification language Boogie. This transformation enables us to use the Boogie verification framework and inductive invariant checking for the automatic formal verification of Matlab Simulink models. Additionally, verification objectives for common error classes are generated automatically. With our approach, we provide an automatic formal verification technique for Matlab Simulink and the most common error classes which scales better than existing techniques in many cases. To demonstrate the practical applicability, we have applied our approach to a number of case studies from the automotive domain.
@cite_48: The tool Matlab Simulink is a numerical simulation environment that is widely used in industry for model-based design. Numerical simulation scales well and can be applied to systems with highly complex dynamics, but it is also inherently incomplete in the sense that critical events or behavior may be overlooked. The application of formal verification techniques to Simulink models could help to overcome this limitation. Set-based verification tools such as SpaceEx use as underlying formalism hybrid automata, which are semantically and structurally different from Simulink models. To address this issue, we are building the tool SL2SX for transforming a subset of the Simulink modeling language into a corresponding SpaceEx model. Our method is designed to preserve the syntactic aspects of a given Simulink diagram: the resulting SpaceEx model shows the same hierarchical structure and preserves the names of components and variables. Placeholders with the correct interface are provided for unsupported Simulink blocks, which can then be translated manually. We illustrate the tool SL2SX and the verification of the transformed models in SpaceEx on two examples provided by the Mathworks example library.
@cite_42: Model Based Development (MBD) using Mathworks tools like Simulink, Stateflow etc. is being pursued in Honeywell for the development of safety critical avionics software. Formal verification techniques are well-known to identify design errors of safety critical systems reducing development cost and time. As of now, formal verification of Simulink design models is being carried out manually resulting in excessive time consumption during the design phase. We present a tool that automatically translates certain Simulink models into input language of a suitable model checker. Formal verification of safety critical avionics components becomes faster and less error prone with this tool. Support is also provided for reverse translation of traces violating requirements (as given by the model checker) into Simulink notation for playback.
@cite_3: Abstract In this paper, a new model-based engineering approach is introduced by bridging MATLAB Simulink with IEC61499 Function Block models. This is achieved by a transformation between the two block-diagram languages. The transformation supported by the developed tools sets the cornerstone of the verification and validation framework for IEC 61499 Function Blocks in closed-loop with the models of the plant. The framework also paves the way to running distributed simulations of complex hybrid (i.e., continuous-discrete) closed-loop plant-controller systems and building complex models using the efficient object instantiation techniques of IEC 61499.
@cite_0: 
@cite_23: We present a method for the translation of a discrete-time fragment of Simulink into the synchronous subset of the BIP language. The translation is fully compositional, that is, it preserves completely the original structure and reveals the minimal control coordination structure needed to perform the correct computation within Simulink models. Additionally, this translation can be seen as providing an alternative operational semantics of Simulink models using BIP. The advantages are twofold. It allows for integration of Simulink models within heterogeneous BIP designs. It enables the use of validation and automatic implementation techniques already available for BIP on Simulink models. The translation is currently implemented in the Simulink2BIP tool. We report several experiments, in particular, we show that the executable code generated from BIP models has comparable runtime performances as the code produced by the Real-Time Workshop on several Simulink models.
@cite_2: We present a method of translating discrete-time Simulink models to Lustre programs. Our method consists of three steps: type inference, clock inference, and hierarchical bottom-up translation. In the process, we explain and formalize the typing and timing mechanisms of Simulink. The method has been implemented in a prototype tool called S2L, which has been used in the context of a European research project to translate two automotive controller models provided by Audi.
@cite_46: Simulink is an industrial de-facto standard for building executable models of embedded systems and their environments, facilitating validation by simulation. Due to the inherent incompleteness of this form of system validation, complementing simulation by formal verification would be desirable. A prerequisite for such an approach is a formal semantics of Simulink's graphical models. In this paper, we show how to encode Simulink diagrams into Hybrid CSP (HCSP), a formal modelling language encoding hybrid system dynamics by means of an extension of CSP. The translation from Simulink to HCSP is fully automatic. We furthermore discuss how to utilize a Hybrid Hoare Logic Prover to verify the translated HCSP models. We demonstrate our approach on a combined scenario originating from the Chinese High-speed Train Control System at Level 3 (CTCS-3).
@cite_10: Simulink has been widely used in industry to model and simulate embedded systems. With the increasing usage of embedded systems in real-time safety-critical situations, Simulink becomes deficient to analyze (timing) requirements with high-level assurance. In this article, we apply Timed Interval Calculus (TIC), a real-time specification language, to complement Simulink with TIC formal verification capability. We elaborately construct TIC library functions to model Simulink library blocks which are used to compose Simulink diagrams. Next, Simulink diagrams are automatically transformed into TIC models which preserve functional and timing aspects. Important requirements such as timing bounded liveness can be precisely specified in TIC for whole diagrams or some components. Lastly, validation of TIC models can be rigorously conducted with a high degree of automation using a generic theorem prover. Our framework can enlarge the design space by representing environment properties to open systems, and handle complex diagrams as the analysis of continuous and discrete behavior is supported.
@cite_12: We develop a semantic translation approach for Simulink diagrams. Simulink is a graphical tool for representing and simulating dynamical systems. We propose a recursive approach for translating a class of Simulink diagrams to input output-extended finite automata (I O-EFA). An I O-EFA model of a Simulink diagram can be used for further analysis such as test generation and formal verification. We show that the translation approach is sound and complete: The input-state-output behavior of an I O-EFA model, as defined in terms of a step-trajectory, preserves the input-state-output behavior of the corresponding Simulink diagram at each sample time (assuming the same integration method for any of the continuous blocks with dynamics).
Several translations from Simulink have been proposed in the literature, including to Hybrid Automata @cite_0 , BIP @cite_23 , NuSMV @cite_42 , Lustre @cite_2 , Boogie @cite_33 , Timed Interval Calculus @cite_10 , Function Blocks @cite_3 , I O Extended Finite Automata @cite_12 , Hybrid CSP @cite_46 , and SpaceEx @cite_48 . It is unclear to what extent these approaches provide formal guarantees on the determinism of the translation. For example, the order in which blocks in the Simulink diagram are processed might a-priori influence the result. Some works fix this order, e.g., @cite_33 computes the control flow graph and translates the model according to this computed order. In contrast, we prove that the results of our algorithm are equivalent for any order. To the best of our knowledge, the abstract translation proposed hereafter for Simulink is the only one formally defined and mechanically proven correct.