VSTTE 2022

14th International Conference on Verified Software: Theories, Tools, and Experiments

October 17-18, 2022, Trento, Italy
Co-located with Formal Methods in Computer-Aided Design 2022 (FMCAD 2022)


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

Overview

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 International 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 2022 edition of VSTTE will be the 14th international conference in the series, and will be co-located with FMCAD 2022 in Trento, Italy.

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, 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.

Paper Submissions

VSTTE 2022 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 at the VSTTE 2022 conference page. Submissions that arrive late, are not in the proper format, or are too long will not be considered. The post-conference proceedings of VSTTE 2022 will be published as a LNCS volume by Springer-Verlag. 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.

Important Dates

Registration

Registration to VSTTE will be part of the FMCAD registration process.

Program

Monday, October 17

8:00-9:00 Registration
Session 1
9:00-10:00 Invited speaker: Aws Albarghouthi
What Can Program Analysis Technology Say About Data Bias?

Abstract: Datasets can be biased due to societal inequities, human biases, under-representation of minorities, etc. Our goal is to prove that models produced by a learning algorithm are robust in their predictions to potential dataset biases. This is a challenging problem: it entails learning models for a large, or even infinite, number of datasets, ensuring that they all produce the same prediction. In this talk, I will show how we can adapt ideas from program analysis to prove robustness of a decision-tree learner on a large, or infinite, number of datasets, certifying that each and every dataset produces the same prediction for a specific test point. We evaluate our approach on datasets that are commonly used in the fairness literature, and demonstrate our approach's viability on a range of bias models.

Bio: Aws Albarghouthi is an associate professor at the University of Wisconsin-Madison. He studies the problems of automated synthesis and verification of programs. He received his PhD from the University of Toronto in 2015. He has received a number of best-paper awards for his work (at FSE, UIST, and FAST), a SIGPLAN research highlight for his PLDI 2020 paper, an NSF CAREER award, a Google Faculty Research Award, multiple Facebook Research Awards, an Amazon Research Award, and a university-wide distinguished teaching award.

10:00-10:30 Suguman Bansal, Giuseppe De Giacomo, Antonio Di Stasio, Yong Li, Moshe Vardi and Shufang Zhu
Compositional Safety LTL Synthesis
10:30-11:00 coffee break
Session 2
11:00-11:30 Iason Marmanis and Viktor Vafeiadis
SMT-based Verification of Persistency Invariants of Px86 Programs
11:30-12:00 Pedro Barroso, Mário Pereira and António Ravara
Leroy and Blazy were right: their memory model soundness proof is automatable
12:00-12:30 Gerhard Schellhorn, Stefan Bodenmüller, Martin Bitterlich and Wolfgang Reif
Separating Separation Logic - Modular Verification of Red-Black Trees
12:30-14:00 lunch break
Session 3
14:00-15:00 Invited speaker: Cezara Dragoi
Reasoning about state machine replication

Abstract: State machine replication protocols are the default mechanism for fault-tolerance in distributed systems. These are asynchronous systems where processes communicate by message passing, where messages may be dropped or delayed, or may processes crashing. Asynchrony and faults make these protocols tricky to reason about and therefore implementations buggy. In this talk we will look into alternatives more simple ways, to reason and develop these systems, inspired from the world of synchronous protocols. The talk presents a formalisation of the relation between synchronous and asynchronous fault-tolerant systems and it’s application in verification and execution environments.

15:00-15:30 Chukri Soueidi and Ylies Falcone
Residual Runtime Verification via Reachability Analysis
15:30-16:00 coffee break
Session 4
16:00-16:30 Nico Naus, Freek Verbeek and Binoy Ravindran
A Formal Semantics for P-Code
16:30-17:00 Cezara Dragoi and Patricio Inzaghi Pronesti
A sequentialization procedure for fault-tolerant protocols
17:00-17:30 Philipp Koerner and Michael Leuschel
Towards Practical Partial Order Reduction for High-Level Formalisms
17:30-18:00 Christopher Chen, Margo Seltzer and Mark Greenstreet
Shellac: a compiler synthesizer for concurrent programs
19:00 Workshop dinner

Tuesday, October 18 (Tutorial day joint with FMCAD)

8:00-9:00 Registration
Session 1
9:00-11:00 Sanjit Seshia
Towards Verified Artificial Intelligence with Scenic and VerifAI

Abstract: Verified artificial intelligence (AI) is the goal of designing AI-based systems that have strong, verified assurances of safety and trustworthiness with respect to mathematically-specified requirements. This goal is particularly important for AI-based autonomous and semi-autonomous systems. In this tutorial, I will describe the main technical challenges for achieving Verified AI, survey some of the existing solutions, and outline some promising directions for future work. In particular, I will present Scenic and VerifAI, two open-source software systems for the formal modeling, design, analysis, and synthesis of systems that include AI and machine learning components. Scenic is a probabilistic programming system for formal modeling and data generation. VerifAI is an algorithmic toolkit supporting a variety of use cases including writing multi-modal system-level specifications, simulation-based verification and testing, automated diagnosis of errors, specification-driven parameter synthesis and retraining, and run-time assurance. The tutorial concepts will be illustrated with examples from the domain of intelligent cyber-physical systems, with a particular focus on deep neural network-based autonomy in transportation systems.

Tutorial participants are encouraged to install Scenic and VerifAI before attending. Here are the links:
Scenic: http://github.com/BerkeleyLearnVerify/Scenic
VerifAI: http://github.com/BerkeleyLearnVerify/VerifAI

Bio: Sanjit A. Seshia is the Cadence Founders Chair Professor in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. His research interests are in formal methods for dependable and secure computing, with a current focus on the areas of cyber-physical systems, computer security, machine learning, and robotics. He has made pioneering contributions to the areas of satisfiability modulo theories, inductive synthesis, and formal methods for robotics and cyber-physical systems (CPS). He is co-author of a widely-used textbook on CPS and has led the development of technologies for CPS education. His awards and honors include a Presidential Early Career Award for Scientists and Engineers (PECASE), an Alfred P. Sloan Research Fellowship, the Frederick Emmons Terman Award for contributions to electrical engineering and computer science education, the IEEE Technical Committee on Cyber-Physical Systems (TCCPS) Mid-Career Award, and the Computer-Aided Verification (CAV) Award. He is a Fellow of the ACM and the IEEE.

11:00-11:30 coffee break
Session 2 (FMCAD tutorial 1)
11:30-12:30 Oded Padon
Verification of Distributed Protocols: Decidable Modeling and Invariant Inference

Abstract: Verification of distributed protocols and systems, where both the number of nodes in the systems and the state-space of each node are unbounded, is a long-standing research goal. In recent years, efforts around the Ivy verification tool have pushed a strategy of modeling distributed protocols and systems in a new way that enables decidable deductive verification, i.e., given a candidate inductive invariant, it is possible to automatically check if it is inductive, and to produce a finite counterexample to induction in case it is not inductive. Complex protocols require quantifiers in both models and their invariants, including forall-exists quantifier alternations. Still, it is possible to obtain decidability by enforcing a stratification structure on quantifier alternations, often achieved using modular decomposition techniques, which are supported by Ivy. Stratified quantifiers lead not only to theoretical decidability, but to reliably good solver performance in practice, which is in contrast to the typical instability of SMT solvers over formulas with complex quantification.

Reliable automation of invariant checking and finite counterexamples open the path to automating invariant inference. An invariant inference algorithm can propose a candidate invariant, automatically check it, and get a finite counterexample that can be used to inform the next candidate. For a complex protocol, this check would typically be performed thousands of times before an invariant is found, so reliable automation of invariant checking is a critical enabler. Recently, several invariant inference algorithms have been developed that can find complex quantified invariants for challenging protocols, including Paxos and some of its most intricate variants.

In the tutorial I will provide an overview of Ivy’s principles and techniques for modeling distributed protocols in a decidable fragment of first-order logic. I will then survey several recently developed invariant inference algorithms for quantified invariants, and present one such algorithm in depth: Primal-Dual Houdini. Primal-Dual Houdini is based on a new mathematical duality, and is obtained by deriving the formal dual of the well-known Houdini algorithm. As a result, Primal-Dual Houdini possesses an interesting formal symmetry between the search for proofs and for counterexamples.

12:30-13:30 lunch break
13:30-14:30 Oded Padon
(second part)
Session 3 (FMCAD tutorial 2)
14:30-15:30 Håkan Hjort
On applying Model Checking in Formal Verification

Use of Hardware model checking in the EDA industry is wide spread and now considered an essential part of verification. While there are many papers, and books, about SAT, SMT and Symbolic model checking, often very little is written about how these methods can be applied. Choices made when modeling systems can have large impacts on applicability and scalability. There is generally no formal semantics defined for the hardware design languages, nor for the intermediate representations in common use. As unsatisfactory as it may be, industry conventions and behaviour exhibited by real hardware have instead been the guides. In this tutorial we will give an overview of some of the steps needed to apply hardware model checking in an EDA tool. We will touch on synthesis, hierarchy flattening, gate lowering, driver resolution, issues with discrete/synchronous time models, feedback loops and environment constraints, input rating and initialisation/reset.

15:30-16:00 coffee break
16:00-17:00 Håkan Hjort
(second part)

Invited Speakers

Invited Tutorial

General Chair

Program Chairs

Program Committee

Previous Editions