Computer Aided Verification

This volume contains the proceedings of the 22nd International Conference on Computer-Aided Veri?cation (CAV) held in Edinburgh, UK, July 15 19 2010. CAV is dedicated to the advancement of the theory and practice of comput- assistedformalanalysismethods forsoftwareandhardwaresystems.Theconf- ence covers the spectrum from theoretical results to concrete applications, with an emphasis on practical veri?cation tools and the algorithms and techniques that are needed for their implementation. We received 145 submissions: 101 submissions of regular papers and 44 s- missions of tool papers. These submissions went through a meticulous review process;eachsubmissionwasreviewedbyatleast 4,andonaverage4.2 Program Committee members. Authors had the opportunity to respond to the initial - views during an author response period. This helped the Program Committee members to select 51 papers: 34 regular papers and 17 tool papers. In addition to the accepted papers, the program also included: Five invited talks: Policy Monitoring in First-Order Temporal Logic, by David Basin (ETH Zurich) Retro?tting Legacy Code for Security, by Somesh Jha (University of Wisconsin-Madison) Induction, Invariants, and Abstraction, by Deepak Kapur (University of New Mexico) Quantitative Information Flow: From Theory to Practice? by Pasquale Malacaria (Queen Mary University) and Memory Management in Concurrent Algorithms, by Maged Michael (IBM) Four invited tutorials: ABC: An Academic Industrial-Strength Veri?cation Tool, by Robert Brayton (University of California, Berkeley) SoftwareModelChecking,byKennethMcMillan(CadenceBerkeleyLabs) There s Plenty of Room at the Bottom: Analyzing and Verifying Machine Code, by Thomas Reps (University of Wisconsin-Madison) and

State-of-the-art research

Invited Talks.- Policy Monitoring in First-Order Temporal Logic.- Retrofitting Legacy Code for Security.- Quantitative Information Flow: From Theory to Practice?.- Memory Management in Concurrent Algorithms.- Invited Tutorials.- ABC: An Academic Industrial-Strength Verification Tool.- There's Plenty of Room at the Bottom: Analyzing and Verifying Machine Code.- Constraint Solving for Program Verification: Theory and Practice by Example.- Session 1. Software Model Checking.- Invariant Synthesis for Programs Manipulating Lists with Unbounded Data.- Termination Analysis with Compositional Transition Invariants.- Lazy Annotation for Program Testing and Verification.- The Static Driver Verifier Research Platform.- Dsolve: Safety Verification via Liquid Types.- Contessa: Concurrency Testing Augmented with Symbolic Analysis.- Session 2. Model Checking and Automata.- Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing.- Efficient Emptiness Check for Timed Büchi Automata.- Session 3. Tools.- Merit: An Interpolating Model-Checker.- Breach, A Toolbox for Verification and Parameter Synthesis of Hybrid Systems.- Jtlv: A Framework for Developing Verification Algorithms.- Petruchio: From Dynamic Networks to Nets.- Session 4. Counter and Hybrid Systems Verification.- Synthesis of Quantized Feedback Control Software for Discrete Time Linear Hybrid Systems.- Safety Verification for Probabilistic Hybrid Systems.- A Logical Product Approach to Zonotope Intersection.- Fast Acceleration of Ultimately Periodic Relations.- An Abstraction-Refinement Approach to Verification of Artificial Neural Networks.- Session 5. Memory Consistency.- Fences in Weak Memory Models.- Generating Litmus Tests for Contrasting Memory Consistency Models.- Session 6. Verification of Hardware and Low Level Code.- Directed Proof Generation for Machine Code.- Verifying Low-Level Implementations of High-Level Datatypes.- Automatic Generation of Inductive Invariants from High-LevelMicroarchitectural Models of Communication Fabrics.- Efficient Reachability Analysis of Büchi Pushdown Systems for Hardware/Software Co-verification.- Session 7. Tools.- LTSmin: Distributed and Symbolic Reachability.- libalf: The Automata Learning Framework.- Session 8. Synthesis.- Symbolic Bounded Synthesis.- Measuring and Synthesizing Systems in Probabilistic Environments.- Achieving Distributed Control through Model Checking.- Robustness in the Presence of Liveness.- RATSY - A New Requirements Analysis Tool with Synthesis.- Comfusy: A Tool for Complete Functional Synthesis.- Session 9. Concurrent Program Verification I.- Universal Causality Graphs: A Precise Happens-Before Model for Detecting Bugs in Concurrent Programs.- Automatically Proving Linearizability.- Model Checking of Linearizability of Concurrent List Implementations.- Local Verification of Global Invariants in Concurrent Programs.- Abstract Analysis of Symbolic Executions.- Session 10. Compositional Reasoning.- Automated Assume-Guarantee Reasoning through Implicit Learning.- Learning Component Interfaces with May and Must Abstractions.- A Dash of Fairness for Compositional Reasoning.- SPLIT: A Compositional LTL Verifier.- Session 11. Tools.- A Model Checker for AADL.- PESSOA: A Tool for Embedded Controller Synthesis.- Session 12. Decision Procedures.- On Array Theory of Bounded Elements.- Quantifier Elimination by Lazy Model Enumeration.- Session 13. Concurrent Program Verification II.- Bounded Underapproximations.- Global Reachability in Bounded Phase Multi-stack Pushdown Systems.- Model-Checking Parameterized Concurrent Programs Using Linear Interfaces.- Dynamic Cutoff Detection in Parameterized Concurrent Programs.- Session 14. Tools.- PARAM: A Model Checker for Parametric Markov Models.- Gist: A Solver for Probabilistic Games.- A NuSMV Extension for Graded-CTL Model Checking.