SPLASH Workshop/Symposium Events 2022
2022 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity (SPLASH Events 2022)
Powered by
Conference Publishing Consulting

8th ACM SIGPLAN International Workshop on Formal Techniques for Safety-Critical Systems (FTSCS 2022), December 7, 2022, Auckland, New Zealand

FTSCS 2022 – Proceedings

Contents - Abstracts - Authors

8th ACM SIGPLAN International Workshop on Formal Techniques for Safety-Critical Systems (FTSCS 2022)

Frontmatter

Title Page


Welcome from the Chairs
This volume contains the proceedings of the Eighth ACM SIGPLAN International Workshop on Formal Techniques for Safety-Critical Systems (FTSCS 2022), held in Auckland, New Zealand, on December 7, 2022, as a satellite event of SPLASH 2022: The ACM SIGPLAN Conference on Systems, Programming, Languages, and Applications: Software for Humanity.
The aim of this workshop is to bring together researchers and engineers who are interested in the application of formal and semi-formal methods to improve the quality of safety-critical computer systems. FTSCS strives to promote research and development of formal methods and tools for industrial applications, and is particularly interested in industrial applications of formal methods.

Invited Talk

Cooperative Verification: Towards Reliable Safety-Critical Systems (Invited Talk)
Dirk BeyerORCID logo
(LMU Munich, Germany)
Cooperative verification is an approach in which several verifiers help each other solving the verification problem by sharing artifacts about the verification process. There are many verification tools available, but the power of combining them is not yet fully leveraged. The problem is that in order to use verifiers 'off-the-shelf', we need clear interfaces to invoke the tools and to pass information. Part of the interfacing problem is to define standard artifacts to be exchanged between verifiers. We explain a few recent approaches for cooperative combinations and also give a brief overview of CoVeriTeam, a tool for composing verification systems from existing off-the-shelf components.

Publisher's Version

Time and State

Rewriting Logic Semantics and Symbolic Analysis for Parametric Timed Automata
Jaime Arias ORCID logo, Kyungmin Bae ORCID logo, Carlos Olarte ORCID logo, Peter Csaba ÖlveczkyORCID logo, Laure Petrucci ORCID logo, and Fredrik Rømming ORCID logo
(CNRS, France; LIPN, France; Université Sorbonne Paris Nord, France; Pohang University of Science and Technology, South Korea; University of Oslo, Norway)
This paper presents a rewriting logic semantics for parametric timed automata (PTAs) and shows that symbolic reachability analysis using Maude-with-SMT is sound and complete for the PTA reachability problem. We then refine standard Maude-with-SMT reachability analysis so that the analysis terminates when the symbolic state space of the PTA is finite. We show how we can synthesize parameters with our methods, and compare their performance with Imitator, a state-of-the-art tool for PTAs. The practical contributions are two-fold: providing new analysis methods for PTAs---e.g. allowing more general state properties in queries and supporting reachability analysis combined with user-defined execution strategies---not supported by Imitator, and developing symbolic analysis methods for real-time rewrite theories.

Publisher's Version
Q: A Sound Verification Framework for Statecharts and Their Implementations
Samuel D. PollardORCID logo, Robert C. Armstrong ORCID logo, John Bender ORCID logo, Geoffrey C. Hulette ORCID logo, Raheel S. Mahmood ORCID logo, Karla Morris ORCID logo, Blake C. Rawlings ORCID logo, and Jon M. Aytac ORCID logo
(Sandia National Laboratories, USA)
We present Q Framework: a verification framework used at Sandia National Laboratories. Q is a collection of tools used to verify safety and correctness properties of high-consequence embedded systems and captures the structure and compositionality of system specifications written with state machines in order to prove system-level properties about their implementations. Q consists of two main workflows: 1) compilation of temporal properties and state machine models (such as those made with Stateflow) into SMV models and 2) generation of ACSL specifications for the C code implementation of the state machine models. These together prove a refinement relation between the state machine model and its C code implementation, with proofs of properties checked by NuSMV (for SMV models) and Frama-C (for ACSL specifications).

Publisher's Version Info
strategFTO: Untimed Control for Timed Opacity
Étienne AndréORCID logo, Shapagat Bolat ORCID logo, Engel Lefaucheux ORCID logo, and Dylan Marinho ORCID logo
(Université Sorbonne Paris Nord, France; LIPN, France; CNRS, France; Université de Lorraine, France; Inria, France; LORIA, France)
We introduce a prototype tool strategFTO addressing the verification of a security property in critical software. We consider a recent definition of timed opacity where an attacker aims to deduce some secret while having access only to the total execution time. The system, here modelled by timed automata, is deemed opaque if for any execution time, there are either no corresponding runs, or both public and private corresponding runs. We focus on the untimed control problem: exhibiting a controller, ie a set of allowed actions, such that the system restricted to those actions is fully timed-opaque. We first show that this problem is not more complex than the full timed opacity problem, and then we propose an algorithm, implemented and evaluated in practice.

Publisher's Version Info

Distributed and Embedded Systems

Symbolic Reachability Analysis of Distributed Systems using Narrowing and Heuristic Search
Byeongjee Kang ORCID logo and Kyungmin Bae ORCID logo
(POSTECH, South Korea)
A concurrent system specified as a rewrite theory can be symbolically analyzed using narrowing-based reachability analysis. Narrowing-based approaches have been applied to formally analyze cryptographic protocols and parameterized protocols. However, existing narrowing-based techniques, based on a breadth-first-search strategy, cannot deal with generic distributed systems with objects and messages due to the symbolic state-space explosion problem. This paper proposes a heuristic search approach for narrowing-based reachability analysis to guide the search for counterexamples involving a small number of objects. As a result, our method can effectively find a counterexample if an error state is reachable. We demonstrate the effectiveness of our technique using a nontrivial distributed consensus algorithm.

Publisher's Version Info
Proving Memory Access Violations in Isabelle/HOL
Sharar Ahmadi ORCID logo, Brijesh Dongol ORCID logo, and Matt Griffin ORCID logo
(University of Surrey, UK)
Security-critical applications often rely on memory isolation mechanisms to ensure integrity of critical data (e.g., keys) and program instructions (e.g., implementing an attestation protocol). These include software-based security microvisor (SµV) or hardware-based (e.g., TrustLite or SMART). Here, we must guarantee that none of the assembly-level instructions corresponding to a program violate the imposed memory access restrictions. We demonstrate our approach on two architectures (SµV and TrustLite) on which remote attestation protocols are implemented. We extend an approach based on the Binary Analysis Platform (BAP) to generate compiled assembly for a given C program, which is translated to an assembly intermediate language (BIL) and ultimately to Isabelle/HOL theories. In our extension, we develop an adversary model and define conformance predicates imposed by an architecture. We generate a set of programs covering all possible cases in which an assembly-level instruction attempts to violate at least one of the conformance predicates. This shows that the memory access restriction of both SµV and TrustLite are dynamically maintained. Moreover, we introduce conformance predicates for assembly-level instructions that can change the control flow, which improve TrustLite’s memory protection unit.

Publisher's Version Published Artifact Artifacts Available
Bounded Model Checking of PLC ST Programs using Rewriting Modulo SMT
Jaeseo Lee ORCID logo, Sangki Kim ORCID logo, and Kyungmin Bae ORCID logo
(POSTECH, South Korea)
A programmable logic controller (PLC) is widely used in industrial control systems, and Structured text (ST) is an imperative language to develop PLC programs. Because of its safety-critical nature, formally analyzing PLC programs is important, and a rewriting-based formal semantics of ST has been proposed for this purpose. This paper presents a bounded model checking technique for PLC ST programs based on the rewriting-based semantics. We apply rewriting modulo SMT to symbolically analyze LTL properties of ST programs with respect to sequences of (possibly infinite) inputs and outputs. We have demonstrated the effectiveness of our approach using a traffic light case study.

Publisher's Version Info

Applications of Formal Methods

Synchronous Programming and Refinement Types in Robotics: From Verification to Implementation
Jiawei Chen ORCID logo, José Luiz Vargas de Mendonça ORCID logo, Shayan Jalili ORCID logo, Bereket Ayele ORCID logo, Bereket Ngussie Bekele ORCID logo, Zhemin Qu ORCID logo, Pranjal Sharma ORCID logo, Tigist Shiferaw ORCID logo, Yicheng Zhang ORCID logo, and Jean-Baptiste Jeannin ORCID logo
(University of Michigan at Ann Arbor, USA; Addis Ababa Institute of Technology, Ethiopia)
Robots and other cyber-physical systems are held to high standards of safety and reliability, and thus one must be confident in the correctness of their software. Formal verification can provide such confidence, but programming languages that lend themselves well to verification often do not produce executable code, and languages that are executable do not typically have precise enough formal semantics. We present MARVeLus, a stream-based approach to combining verification and execution in a synchronous programming language that allows formal guarantees to be made about implementation-level source code. We then demonstrate the end-to-end process of developing a safe robotics application, from modeling and verification to implementation and execution.

Publisher's Version
Formal Probabilistic Risk Assessment of a Nuclear Power Plant
Mohamed Abdelghany ORCID logo and Sofiène Tahar ORCID logo
(Concordia University, Canada)
Functional Block Diagrams (FBD) are commonly used as a graphical representation for probabilistic risk assessment in a wide range of complex engineering applications. An FBD models the stochastic behavior and cascading dependencies of system components or subsystems. Within FBD-based safety analysis, Event Trees (ET) dependability modeling techniques are typically used to associate all possible risk events to each subsystem. In this paper, we conduct the formal modeling and probabilistic risk assessment of a nuclear power plant in the HOL4 theorem prover. Using an FBD modeling in HOL4 of the nuclear Boiling Water Reactor (BWR), we formally determine all possible classes of accident events that can occur in the BWR. We compare our formal analysis in HOL4 with those obtained analytically and by simulation using Matlab and the specialized Isograph tool. Experimental results showed the superiority of our approach in terms of scalability, expressiveness, accuracy and CPU time.

Publisher's Version
Modelling a Blockchain for Smart Contract Verification using DeepSEA
Daniel Britten ORCID logo and Steve Reeves ORCID logo
(University of Waikato, New Zealand)
To create trustworthy programs, the 'gold standard' is specifications at a high-enough level to clearly correspond to the informal specifications, and also a refinement proof linking these high-level specifications down to, in our case, executable bytecode. The DeepSEA system demonstrates how this can be done, in the context of smart contracts on the Ethereum blockchain. A key component of this is the model of the blockchain on which the smart contracts reside. When doing proofs in DeepSEA, it is critical to have such a model, which allows for the writing of specifications at a high-level clearly corresponding to informal specifications. A candidate model for doing so and its usefulness for carrying out proofs is discussed in this paper.

Publisher's Version Info

proc time: 3