VSTTE21

VSTTE 2021

13th Working Conference on Verified Software: Theories, Tools, and Experiments

October 18-19, 2021
Co-located with Formal Methods in Computer-Aided Design 2021 (FMCAD 2021)

Submissions | Important Dates | Registration | Program | Invited Speakers | Program Chairs
Program Committee  |  Previous Editions  |  Talks

VSTTE and FMCAD are co-organising the online conference this year. The connection details have been communicated to all registered members by e-mail from the FMCAD'21 chairs. If you are registered but have not received the connection details, kindly contact the VSTTE organisers via vstte2021@googlegroups.com.

Overview

News: VSTTE 2021 will take place as an online meeting.

The goal of the VSTTE conference series is to advance the state of the art in the science and technology of software verification, through the interaction of theory development, tool evolution, and experimental validation. The Verified Software Initiative (VSI), spearheaded by Tony Hoare and Jayadev Misra, is an ambitious research program for making large-scale verified software a practical reality. The Working Conference on Verified Software: Theories, Tools and Experiments (VSTTE) is the main forum for advancing the initiative. VSTTE brings together experts spanning the spectrum of software verification in order to foster international collaboration on the critical research challenges. The theoretical work includes semantic foundations and logics for specification and verification, and verification algorithms and methodologies. The tools cover specification and annotation languages, program analyzers, model checkers, interactive verifiers and proof checkers, automated theorem provers and SAT/SMT solvers, and integrated verification environments. The experimental work drives the research agenda for theory and tools by taking on significant specification/verification exercises covering hardware, operating systems, compilers, computer security, parallel computing, and cyber-physical systems. The 2021 edition of VSTTE will be the 13th working conference in the series, and will be co-located with FMCAD 2021 at the Yale University, Connecticut, USA. We welcome submissions describing significant advances in the production of verified software, i.e., software that has been proved to meet its functional specifications. Submissions of theoretical, practical, and experimental contributions are equally encouraged, including those that focus on specific problems or problem domains. We are especially interested in submissions describing large-scale verification efforts that involve collaboration, theory unification, tool integration, and formalized domain knowledge. We also welcome papers describing novel experiments and case studies evaluating verification techniques and technologies. Topics of interest for this conference include, but are not limited to, education, requirements modeling, specification languages, specification/verification/certification case studies, formal calculi, software design methods, automatic code generation, refinement methodologies, compositional analysis, verification tools (e.g., static analysis, dynamic analysis, model checking, theorem proving, satisfiability), tool integration, benchmarks, challenge problems, and integrated verification environments. Work on diverse verification technologies, e.g., static analysis, dynamic analysis, model checking, theorem proving, satisfiability, is particularly encouraged.

Paper Submissions

VSTTE 2021 will accept both long (limited to 16 pages, excluding references) and short (limited to 10 pages, excluding references) paper submissions. Short submissions also cover Verification Pearls describing an elegant proof or proof technique. Submitted research papers and system descriptions must be original and not submitted for publication elsewhere. Submissions of theoretical, practical, and experimental contributions are equally encouraged, including those that focus on specific problems or problem domains. Papers will be submitted via EasyChair. Submissions that arrive late, are not in the proper format, or are too long will not be considered. The post-conference proceedings of VSTTE 2021 will be published by Springer-Verlag in the LNCS series. Authors of accepted papers will be requested to sign a form transferring copyright of their contribution to Springer-Verlag. The use of LaTeX and the Springer LNCS class files is strongly encouraged.

Program

All times are in the US eastern zone (EST)

Monday, October 18


EST Session 1: Invited talk (Chair: Natasha Sharygina )
10:00 - 10:45 Tom Henzinger (IST Austria), joint work with Ege Sarac
Quantitative Monitoring of Software

We present a framework for the online black-box monitoring of quantitative properties such as response time. Our monitors are not necessarily finite-state, and they may approximate the monitored properties. This allows for a rich spectrum of cost-precision trade-offs in monitoring.
10:45 - 11:00 ☕
EST Session 2 (Chair: Grigory Fedyukovich)
11:00 - 11:30 Arie Gurfinkel and Jorge Navas
Abstract Interpretation of LLVM with a Region-Based Memory Model

Static analysis of low-level programs (C or LLVM) requires modeling memory. To strike a good balance between precision and performance, most static analyzers rely on the C memory model in which a pointer is a numerical offset within a memory object. Finite partitioning of the address space is a common abstraction. For instance, the allocation-site abstraction creates partitions by merging all objects created at the same allocation sites. The recency abstraction refines the allocation-site abstraction by distinguishing the most recent allocated memory object from the previous ones. Unfortunately, these abstractions are not often precise enough to infer invariants that are expressed over the contents of dynamically allocated data-structures such as linked lists. In those cases, more expensive abstractions such as shapes that consider connectivity patterns between memory locations are often used.
Instead of resorting to more expensive memory abstractions, we propose a new memory model, called region-based memory model (RBMM). RBMM is a refinement of the C memory model in which pointers have an extra component called regions. Thus, a memory object can spawn multiple regions which can greatly limit aliasing since regions are pairwise disjoint. Since RBMM requires that each memory instruction refers explicitly to a region, we first present a new intermediate representation (IR) based on regions which is the input of our abstract interpreter. Second, we show how abstractions such as allocation-site and recency can be easily adapted to RBMM. Third, we implemented RBMM in the Crab library and evaluated it on widely-used C projects.
11:30 - 12:00 Matteo Cimini 
A Calculus for Multi-Language Operational Semantics

We present $\lambda^{L}$, a statically typed lambda-calculus with languages as first-class citizens. In $\lambda^{L}$, not only languages can be defined and used to execute programs, they also can be bound to variables, passed to functions, and returned by functions, among other operations. Moreover, code of different languages can safely interact thanks to pre- and post-conditions that are checked at run-time.
We provide a type system and an operational semantics for $\lambda^{L}$. We observe that Milner's type safety is too strong a property in this context, as programmers may intentionally execute unsafe languages. We then identify a type safety theorem that is specific to the domain of multi-language programming, and we prove that $\lambda^{L}$ satisfies this theorem.
12:00 - 12:30 🍽
EST Session 3: Invited talk (Chair: Roderick Bloem)
12:30 - 13:15 Michael Whalen 
Reasoning about the Security and Robustness of Amazon Web Services

Formal methods have been successfully applied in domains such as microprocessor hardware design and aerospace. However, despite 50 years of research and development, we have not seen wide adoption of formal methods for large and complex systems such as web services, industrial automation, or enterprise support software. One of the key difficulties when proving security, safety, and robustness of these systems is the problem of finding the models of system architectures necessary for analysis. Additionally, the size of the potential user community and the business value typically does not justify the creation of scalable and easy-to-use tools for formal verification. With the cloud, much of this has changed. Descriptions of cloud services provide accurate models in the form of computer-readable contracts. These contracts establish and govern how the system behaves and in many cases these models are amenable to formal analysis at scale. Most importantly, since those models are used by a large user community, it is now economically feasible to build the tools needed to verify those models. In this talk, we discuss the trend of constructing practical and scalable cloud-based formal methods at Amazon Web Services and how they can easily be used by customers – sometimes with just one-click.
EST Session 4 (Chairs: Antti Hyvärinen, after break:Yakir Vizel)
13:15 - 13:45 Maryam Bagheri, Marjan Sirjani, Ehsan Khamespanah, Hossein Hojjat, and Ali Movaghar
Partial Order Reduction for Timed Actors

We propose a compositional approach for the Partial Order Reduction (POR) in the state space generation of asynchronous timed actors. We define the concept of independent actors as the actors that do not send messages to a common actor. The approach avoids exploring unnecessary interleaving of executions of independent actors. It performs on a component-based model where actors from different components, except for the actors on borders, are independent. To alleviate the effect of the cross-border messages, we enforce a delay condition, ensuring that an actor introduces a delay in its execution before sending a message across the border of its component. Within each logical time unit, our technique generates the state space of each individual component by taking its received messages into account. It then composes the state spaces of all components. We prove that our POR approach preserves the properties defined on timed states (states where the only outgoing transition shows the progress of time). We generate the state space of a case study in the domain of air traffic control systems based on the proposed POR. The results on our benchmarks illustrate that our POR method, on average, reduces the time and memory consumption by 76 and 34 percent, respectively.
13:45 - 14:15 Claire Dross and Johannes Kanig
Making Proofs of Floating-Point Programs Accessible to Regular Developers

Formal verification of floating-point computations remains a challenge for the software engineer. Automated, specialized tools can handle floating-point computations well, but struggle with other types of data or memory reasoning. Specialized tools based on proof assistants are very powerful, but require a high degree of expertise. General-purpose tools for deductive verification of programs have added support for floating-point computations in recent years, but often the proved properties are limited to verifying ranges or absence of special values such as NaN or Infinity. Proofs of more complex properties, such as bounds on rounding errors, are generally reserved to experts and often require the use of either a proof assistant or a specialized solver as a backend.
In this article, we show how generic deductive verification tools based on general-purpose SMT solvers can be used to verify different kinds of properties on floating point computations up to bounds on rounding errors. The demonstration is done on a computation of a weighted average using floating-point numbers, using an approach which is heavily based on auto-active verification. We use the general-purpose tool SPARK for formal verification of Ada programs based on the SMT solvers Alt-Ergo, CVC4, and Z3 but it can in principle be carried out in other similar languages and tools such as Frama-C or KeY.
14:15 - 14:30 ☕
14:30 - 15:00 Nasim Baharisangari, Jean-Raphaël Gaglione, Daniel Neider, Ufuk Topcu, and Zhe Xu
Uncertainty-Aware Signal Temporal Logic Inference

Temporal logic inference is the process of extracting formal descriptions of system behaviors from data in the form of temporal logic formulas. The existing temporal logic inference methods mostly neglect uncertainties in the data, which results in the limited applicability of such methods in real-world deployments. In this paper, we first investigate the uncertainties associated with trajectories of a system and represent such uncertainties in the form of interval trajectories. We then propose two uncertainty-aware signal temporal logic (STL) inference approaches to classify the undesired behaviors and desired behaviors of a system. Instead of classifying finitely many trajectories, we classify infinitely many trajectories within the interval trajectories. In the first approach, we incorporate robust semantics of STL formulas with respect to an interval trajectory to quantify the margin at which an STL formula is satisfied or violated by the interval trajectory. The second approach relies on the first learning algorithm and exploits the decision trees to infer STL formulas to classify behaviors of a given system. The proposed approaches also work for non-separable data by optimizing the worst-case robustness margin in inferring an STL formula. Finally, we evaluate the performance of the proposed algorithms in two case studies, where the proposed algorithms show reductions in the computation time by up to four orders of magnitude, while the worst-case robustness margins are improved by up to 330% in comparison with the sampling-based baseline algorithms.
15:00 - 15:30 Smruti Padhy and Joe Stubbs
Designing and Proving Properties of the Abaco Autoscaler Using TLA+

The Abaco (Actor Based Containers) platform is an open-source software system funded by the National Science Foundation and hosted at the Texas Advanced Computing Center, providing national-scale functions-as-a-service to the research computing community. Abaco utilizes the Actor Model of concurrent computation, where computational primitives, referred to as actors, execute in response to messages sent to the actor's inbox. In this paper, we use formal methods to analyze Abaco and create an improved design that corrects a race condition in one of its critical subsystems. More precisely, we present a specification of an updated version of the autoscaler subsystem of Abaco, responsible for automatically scaling the number of worker processes associated with an actor based on the actor's inbox size, using TLA+, a formal specification language for modeling concurrent systems. We analyze the new design using both the TLC model checker and the TLAPS proof system. We include results of our use of TLC for manually checking safety and liveness properties for some small state spaces, and we provide proofs in TLAPS of all safety properties. To the best of our knowledge, our work is the first analysis of a large, real-world production software system with open-source code, openly available TLA+ specification, and complete TLAPS proofs of all key safety properties.
15:30 - 16:00 Ismet Burak Kadron, Divya Gopinath, Corina S. Pasareanu, and Huafeng Yu
Analysis of Autonomous Center line Tracking Neural Networks

Deep neural networks have gained widespread usage in a number of applications. However, limitations such as lack of explainability and robustness inhibit building trust in their behavior, which is crucial in safety critical applications such as autonomous driving. Therefore, techniques which aid in understanding and providing guarantees for neural network behavior are the need of the hour. In this paper, we present a case study applying a recently proposed technique, Prophecy, to analyze the behavior of a neural network model, provided by our industry partner and used for autonomous guiding of airplanes on taxi runways. This regression model takes as input an image of the runway and produces two outputs, cross-track error and heading error, which represent the position of the plane relative to the center line. We use the Prophecy tool to extract neuron activation patterns for the correctness and safety properties of the model. We show the use of these patterns to identify features of the input that explain correct and incorrect behavior. We also use the patterns to provide guarantees of consistent behavior. We explore a novel idea of using sequences of images (instead of single images) to obtain good explanations and identify regions of consistent behavior.
EST Beer session (bring your own beer) 🍻
16:00 - 16:30 Discussion session:

In "The Verified Software Initiative: A Manifesto", Hoare, Misra, Leavens, and Shankar write: "We envision a world in which computer programmers make no more mistakes than other professionals, a world in which computer programs are always the most reliable components of any system or device." The initiative was launched in 2015 and set to run until 2030.
Topics to discuss:
- How far along are we towards realizing this vision?
- What was the greatest contribution in the last 5-10 years?
- What was the greatest setback?
- What do we need to change in order to make this vision a reality?



Tuesday, October 19 (Joint VSTTE/FMCAD Turorials)

EST Session 1 (Chair: Roderick Bloem)
11:00 - 12:15 Frits Vaandrager
Active Automata Learning: from L* to L#

In this tutorial on active automata learning algorithms, I will start with the famous L* algorithm proposed by Dana Angluin in 1987, and explain how this algorithm approximates the Nerode congruence by means of refinement. Next, I will present a brief overview of the various improvements of the L^* algorithm that have been proposed over the years. Finally, I will introduce L#, a new and simple approach to active automata learning. Instead of focusing on equivalence of observations, like the L* algorithm and its descendants, L# takes a different perspective: it tries to establish apartness, a constructive form of inequality.
12:15 - 12:25 🍽
EST Session 2
12:25 - 13:40 Viktor Kuncak
Stainless Verification System Tutorial

Stainless ( https://stainless.epfl.ch ) is an open-source tool for verifying and finding errors in programs written in the Scala programming language. This tutorial will not assume any knowledge of Scala. It aims to get first-time users started with verification tasks by introducing the language, providing modelling and verification tips, and giving a glimpse of the tool's inner workings (encoding into functional programs, function unfolding, and using theories of satisfiability modulo theory solvers Z3 and CVC4).
Stainless (and its predecessor, Leon) has been developed primarily in the EPFL's Laboratory for Automated Reasoning and Analysis in the period from 2011-2021. Its core specification and implementation language are typed recursive higher-order functional programs (imperative programs are also supported by automated translation to their functional semantics). Stainless can verify that functions are correct for all inputs with respect to provided preconditions and postconditions, it can prove that functions terminate (with optionally provided termination measure functions), and it can provide counter-examples to safety properties. Stainless enables users to write code that is both executed and verified using the same source files. Users can compile programs using the Scala compiler and run them on the JVM. For programs that adhere to certain discipline, users can generate source code in a small fragment of C and then use standard C compilers.
Github
13:40 - 14:10 ☕
EST Session 3
14:10 - 15:25 Rayna Dimitrova
Reactive Synthesis Beyond Realizability

The automatic synthesis of reactive systems from high-level specifications is a highly attractive and increasingly viable alternative to manual system design, with applications in a number of domains such as robotic motion planning, control of autonomous systems, and development of communication protocols. The idea of asking the system designer to describe what the system should do instead of how exactly it does it, holds a great promise. However, providing the right formal specification of the desired behaviour of a system is a challenging task in itself. In practice it often happens that the system designer provides a specification that is unrealizable, that is, there is no implementation that satisfies it. Such situations typically arise because the desired behavior represents a trade-off between multiple conflicting requirements, or because crucial assumptions about the environment in which the system will execute are missing. Addressing such scenarios necessitates a shift towards synthesis algorithms that utilize quantitative measures of system correctness. In this tutorial I will discuss two recent advances in this research direction.
First, I will talk about the maximum realizability problem, where the input to the synthesis algorithm consists of a hard specification which must be satisfied by the synthesized system, and soft specifications which describe other desired, possibly prioritized properties, whose violation is acceptable. I will present a synthesis algorithm that maximizes a quantitative value associated with the soft specifications, while guaranteeing the satisfaction of the hard specification. In the second half of the tutorial I will present algorithms for synthesis in bounded environments, where a bound is associated with the sequences of input values produced by the environment. More concretely, these sequences consists of an initial prefix followed by a finite sequence repeated infinitely often, and satisfy the constraint that the sum of the lengths of the initial prefix and the loop does not exceed a given bound. I will also discuss the synthesis of approximate implementations from unrealizable specifications, which are guaranteed to satisfy the specification on at least a specified portion of the bounded-size input sequences. I will conclude by outlining some of the open avenues and challenges in quantitative synthesis from temporal logic specifications.
15:25 - 15:35 ☕
EST Session 4 (Chair: Natasha Sharygina)
15:35 - 16:50 Matteo Maffei
Formal Methods for the Security Analysis of Smart Contracts

Smart contracts consist of distributed programs built over a blockchain and they are emerging as a disruptive paradigm to perform distributed computations in a secure and efficient way. Given their nature, however, program flaws may lead to dramatic financial losses and can be hard to fix. This motivates the need for formal methods that can provide smart contract developers with correctness and security guarantees, ideally automating the verification task.
This tutorial introduces the semantic foundations of smart contracts and reviews the state-of-the-art in the field, focusing in particular on the automated, sound, static analysis of Ethereum smart contracts. We will highlight the strengths and drawbacks of different methods, suggesting open challenges that can stimulate new research strands. Finally, we will overview eThor, an automated static analysis tool that we recently developed based on rigorous semantic foundations.

Important Dates

  • Abstract submission:  July 10, 2021  July 24, 2021 (AoE)
  • Paper submission:  July 17, 2021  July 24, 2021 (AoE)
  • Notification of presentation acceptance:  September 1, 2021   September 8, 2021
  • Camera-ready for post-conference proceedings: (TBA)

Registration

Registration to VSTTE is part of the FMCAD 2021 process.

Invited Speakers

General Chair

Program Chairs

Program Committee

Previous Editions

Talks


Stainless Verification System Tutorial
Viktor Kunčak
[ video ]


Active Automata Learning: from L* to L#
Frits Vaandrager
[ video ]
Making Proofs of Floating-Point Programs Accessible to Regular Developers
Claire Dross
[ video ]
Analysis of Autonomous Center line Tracking Neural Networks
Corina S. Pasareanu
[ video ]
Partial Order Reduction for Timed Actors
Maryam Bagheri
[ video ]
Uncertainty-Aware Signal Temporal Logic Inference
Nasim Baharisangari
[ video ]
Designing and Proving Properties of the Abaco Autoscaler Using TLA+
Smruti Padhy
[ video ]