FMCAD 2022: FORMAL METHODS IN COMPUTER-AIDED DESIGN
PROGRAM FOR TUESDAY, OCTOBER 18TH
Days:
next day
all days

View: session overviewtalk overview

09:00-11:00 Session 2: VSTTE Tutorial

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.

11:30-12:30 Session 4: FMCAD Tutorial 1 (part 1)

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.

13:30-14:30 Session 6: FMCAD Tutorial 1 (part 2)

Oded Padon. Verification of Distributed Protocols: Decidable Modeling and Invariant Inference

14:30-15:30 Session 7: FMCAD Tutorial 2 (part 1)

Håkan Hjort. On applying Model Checking in Formal Verification

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

16:00-17:00 Session 9: FMCAD Tutorial 2 (part 2)

Håkan Hjort. On applying Model Checking in Formal Verification

18:00-20:00 FMCAD reception

Welcome reception at the Grand Hotel Trento