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 SaracQuantitative Monitoring of Software Abstract 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 NavasAbstract Interpretation of LLVM with a Region-Based Memory Model Abstract (SLIDES) 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 Abstract (SLIDES) 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 Abstract 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 MovagharPartial Order Reduction for Timed Actors Abstract (SLIDES) 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 Abstract (SLIDES) 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 XuUncertainty-Aware Signal Temporal Logic Inference Abstract (SLIDES) 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+ Abstract (SLIDES) 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 YuAnalysis of Autonomous Center line Tracking Neural Networks Abstract (SLIDES) 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)

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.