Tools and Algorithms for the Construction and Analysis of Systems : 22nd International Conference, TACAS 2016, Held As Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Eindhoven, The Netherlands, April 2-8, 2016, Proc

This Book Constitutes The Proceedings Of The 22nd International Conference On Tools And Algorithms For The Construction And Analysis Of Systems, Tacas 2016, Which Took Place In Eindhoven, The Netherlands, In April 2016, Held As Part Of The European Joint Conferences On Theory And Practice Of Software, Etaps 2016. The 44 Full Papers Presented In This Volume Were Carefully Reviewed And Selected From 175 Submissions. They Were Organized In Topical Sections Named: Abstraction And Verification; Probabilistic And Stochastic Systems; Synthesis; Tool Papers; Concurrency; Tool Demos; Languages And Automata; Security; Optimization; And Competition On Software Verification – Sv-comp. Robots At The Edge Of The Cloud -- Finding Recurrent Sets With Backward Analysis And Trace Partitioning -- Tactics For The Dafny Program Verifier -- Synthesizing Ranking Functions From Bits And Pieces -- Abstraction Refinement And Antichains For Trace Inclusion Of Infinite State Systems -- Probabilistic And Stochastic Systems Efficient Syntax-driven Lumping Of Differential Equations -- Faster Statistical Model Checking For Unbounded Temporal Properties -- Safety-constrained Reinforcement Learning For Mdps -- Safety Verification Of Continuous-space Pure Jump Markov Processes -- Abstract Learning Frameworks For Synthesis -- Synthesizing Piece-wise Functions By Learning Classifiers -- An Automaton Learning Approach To Solving Safety Games Over Infinite Graphs -- Uncertainty Propagation Using Probabilistic Affine Forms And Concentration Of Measure Inequalities -- Online And Compositional Learning Of Controllers With Application To Floor Heating --^ Deductive Proofs Of Almost Sure Persistence And Recurrence Properties -- Probabilistic Ctl* : The Deductive Way -- Parametric Runtime Verification Of C Programs -- Coqoon: An Ide For Interactive Proof Development In Coq -- Multi-core Symbolic Bisimulation Minimization -- Advances In Symbolic Probabilistic Model Checking With Prism -- Prism-psy: Precise Gpu-accelerated Parameter Synthesis For Stochastic Systems -- T2: Temporal Property Verification -- Rtd-finder: A Tool For Compositional Verification Of Real-time Component-based Systems -- Tct: Tyrolean Complexity Tool -- Integrated Environment For Diagnosing Verification Errors -- Jdart: A Dynamic Symbolic Analysis Framework -- Diagnostic Information For Control-flow Analysis Of Workflow Graphs -- Approaching The Coverability Problem Continuously -- On Atomicity In Presence Of Non-atomic Writes -- Formalizing And Checking Thread Refinement For Data-race-free Execution Models -- The Xsap Safety Analysis Platform --^ Fact: A Probabilistic Model Checker For Formal Verification With Confidence Intervals -- Prdk: Protocol Programming With Automata -- Dlc: Compiling A Concurrent System Formal Specification To A Distributed Implementation -- Prism-games 2.0: A Tool For Multi-objective Strategy Synthesis For Stochastic Games -- Cerberus: Automated Synthesis Of Enforcement Mechanisms For Security-sensitive Business Processes -- Developing & Debugging Proof Strategies By Tinkering -- V2c - A Verilog To C Translator Tool -- Parameterized Compositional Model Checking -- An O(m Log N) Algorithm For Stuttering Equivalence And Branching Bisimulation -- Interpolants In Nonlinear Theories Over The Reals -- Ptime Computation Of Transitive Closures Of Octagonal Relations -- Verification Of Linear Controller Software -- Partial Order Reduction For Event-driven Multi-threaded Programs -- Acceleration In Multi-pushdown Systems -- Reduction Of Nondeterministic Tree Automata --^ Online Timed Pattern Matching Using Derivatives -- Hybridization Based Cegar For Hybrid Automata With Affine Dynamics -- Complementing Semi-deterministic Buechi Automata -- Reasoning About Information Flow Security Of Separation Kernels With Channel-based Communication -- Some Complexity Results For Stateful Network Verification -- Characteristic Formulae For Session Types -- Bit-vector Optimization -- Runtime Monitoring With Union-find Structures -- Competition On Software Verification: Sv-comp -- Reliable And Reproducible Competition Results With Benchexec And Witnesses (report On Sv-comp 2016). Edited By Marsha Chechik, Jean-françois Raskin. Front Matter....Pages I-XIX Front Matter....Pages 1-1 Robots at the Edge of the Cloud....Pages 3-13 Front Matter....Pages 15-15 Finding Recurrent Sets with Backward Analysis and Trace Partitioning....Pages 17-35 Tactics for the Dafny Program Verifier....Pages 36-53 Synthesizing Ranking Functions from Bits and Pieces....Pages 54-70 Abstraction Refinement and Antichains for Trace Inclusion of Infinite State Systems....Pages 71-89 Front Matter....Pages 91-91 Efficient Syntax-Driven Lumping of Differential Equations....Pages 93-111 Faster Statistical Model Checking for Unbounded Temporal Properties....Pages 112-129 Safety-Constrained Reinforcement Learning for MDPs....Pages 130-146 Safety Verification of Continuous-Space Pure Jump Markov Processes....Pages 147-163 Front Matter....Pages 165-165 Abstract Learning Frameworks for Synthesis....Pages 167-185 Synthesizing Piece-Wise Functions by Learning Classifiers....Pages 186-203 An Automaton Learning Approach to Solving Safety Games over Infinite Graphs....Pages 204-221 Front Matter....Pages 223-223 Uncertainty Propagation Using Probabilistic Affine Forms and Concentration of Measure Inequalities....Pages 225-243 Online and Compositional Learning of Controllers with Application to Floor Heating....Pages 244-259 Deductive Proofs of Almost Sure Persistence and Recurrence Properties....Pages 260-279 Front Matter....Pages 280-296 Parametric Runtime Verification of C Programs....Pages 297-297 Coqoon....Pages 299-315 Multi-core Symbolic Bisimulation Minimisation....Pages 316-331 Advances in Symbolic Probabilistic Model Checking with PRISM....Pages 332-348 Front Matter....Pages 349-366 PRISM-PSY: Precise GPU-Accelerated Parameter Synthesis for Stochastic Systems....Pages 297-297 Front Matter....Pages 367-384 RTD-Finder: A Tool for Compositional Verification of Real-Time Component-Based Systems....Pages 385-385 TcT: Tyrolean Complexity Tool....Pages 387-393 Integrated Environment for Diagnosing Verification Errors....Pages 394-406 JDart: A Dynamic Symbolic Analysis Framework....Pages 407-423 Front Matter....Pages 424-441 Diagnostic Information for Control-Flow Analysis of Workflow Graphs (a.k.a. Free-Choice Workflow Nets)....Pages 442-459 Approaching the Coverability Problem Continuously....Pages 461-461 On Atomicity in Presence of Non-atomic Writes....Pages 463-479 Formalizing and Checking Thread Refinement for Data-Race-Free Execution Models....Pages 480-496 Front Matter....Pages 497-514 The xSAP Safety Analysis Platform....Pages 515-530 FACT: A Probabilistic Model Checker for Formal Verification with Confidence Intervals....Pages 531-531 PrDK: Protocol Programming with Automata....Pages 533-539 DLC: Compiling a Concurrent System Formal Specification to a Distributed Implementation....Pages 540-546 PRISM-Games 2.0: A Tool for Multi-objective Strategy Synthesis for Stochastic Games....Pages 547-552 Cerberus: Automated Synthesis of Enforcement Mechanisms for Security-Sensitive Business Processes....Pages 553-559 Developing and Debugging Proof Strategies by Tinkering....Pages 560-566 v2c – A Verilog to C Translator....Pages 567-572 Front Matter....Pages 573-579 Parameterized Compositional Model Checking....Pages 580-586 Front Matter....Pages 587-587 Interpolants in Nonlinear Theories Over the Reals....Pages 589-606 Front Matter....Pages 607-624 PTIME Computation of Transitive Closures of Octagonal Relations....Pages 587-587 Scalable Verification of Linear Controller Software....Pages 625-641 Partial Order Reduction for Event-Driven Multi-threaded Programs....Pages 643-643 Acceleration in Multi-PushDown Systems....Pages 645-661 Front Matter....Pages 662-679 Reduction of Nondeterministic Tree Automata....Pages 680-697 Online Timed Pattern Matching Using Derivatives....Pages 698-714 Hybridization Based CEGAR for Hybrid Automata with Affine Dynamics....Pages 715-715 Complementing Semi-deterministic Büchi Automata....Pages 717-735 Front Matter....Pages 736-751 Reasoning About Information Flow Security of Separation Kernels with Channel-Based Communication....Pages 752-769 Some Complexity Results for Stateful Network Verification....Pages 770-787 Front Matter....Pages 789-789 Characteristic Formulae for Session Types....Pages 791-810 Bit-Vector Optimization....Pages 811-830 Runtime Monitoring with Union-Find Structures....Pages 831-831 Front Matter....Pages 833-850 Reliable and Reproducible Competition Results with BenchExec and Witnesses (Report on SV-COMP 2016)....Pages 851-867 2LS for Program Analysis....Pages 868-884 CIVL: Applying a General Concurrency Verification Framework to C/Pthreads Programs (Competition Contribution)....Pages 885-885 CPA-RefSel: CPAchecker with Refinement Selection....Pages 887-904 Front Matter....Pages 905-907 Run Forester, Run Backwards!....Pages 908-911 LCTD: Tests-Guided Proofs for C Programs on LLVM....Pages 912-915 LPI: Software Verification with Local Policy Iteration....Pages 916-919 Hunting Memory Bugs in C Programs with Map2Check....Pages 920-922 MU-CSeq 0.4: Individual Memory Location Unwindings....Pages 885-885 Optimized PredatorHP and the SV-COMP Heap and Memory Safety Benchmark....Pages 923-926 Symbiotic 3: New Slicer and Error-Witness Generation....Pages 927-929 Ultimate Automizer with Two-track Proofs....Pages 930-933 Vienna Verification Tool: IC3 for Parallel Software....Pages 934-937 Back Matter....Pages 938-941 ....Pages 942-945