VSTTE 2022

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.

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.

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.

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.

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.