Skip to main content
Top

Tools and Algorithms for the Construction and Analysis of Systems

28th International Conference, TACAS 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Munich, Germany, April 2–7, 2022, Proceedings, Part I

  • Open Access
  • 2022
  • Open Access
  • Book

About this book

This open access book constitutes the proceedings of the 28th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2022, which was held during April 2-7, 2022, in Munich, Germany, as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022.

The 46 full papers and 4 short papers presented in this volume were carefully reviewed and selected from 159 submissions. The proceedings also contain 16 tool papers of the affiliated competition SV-Comp and 1 paper consisting of the competition report.

TACAS is a forum for researchers, developers, and users interested in rigorously based tools and algorithms for the construction and analysis of systems. The conference aims to bridge the gaps between different communities with this common interest and to support them in their quest to improve the utility, reliability, exibility, and efficiency of tools and algorithms for building computer-controlled systems.

Table of Contents

Next
  • current Page 1
  • 2
  1. Synthesis

    1. Frontmatter

    2. HOLL: Program Synthesis for Higher Order Logic Locking

      • Open Access
      Gourav Takhar, Ramesh Karri, Christian Pilato, Subhajit Roy
      The chapter discusses the threat of counterfeiting and piracy in the semiconductor industry and introduces Higher Order Logic Locking (HOLL) as a solution. HOLL hides a higher-order relation instead of a sequence of independent key bits, making it more secure against attacks like the SAT attack. The authors propose a new attack, SynthAttack, to evaluate the security of HOLL and demonstrate its effectiveness. The chapter also covers the implementation and optimization of HOLL, highlighting its low overhead and resistance to existing attacks.
      Download PDF-version
    3. The Complexity of LTL Rational Synthesis

      • Open Access
      Orna Kupferman, Noam Shenwald
      The chapter delves into the complexity of LTL rational synthesis, a process that automatically constructs reactive systems to meet their specifications even in rational environments. It builds on earlier work to tighten upper bounds for settings with three or more players and concurrent games. The complexity analysis is parametric, considering the game graph, objectives of system components, and objectives of environment components. The study generalizes rational synthesis by combining cooperative and non-cooperative approaches, extending the complexity analysis to this broader definition. Notably, it introduces algorithms that reduce rational synthesis to the nonemptiness problem of tree automata, providing a detailed and nuanced understanding of the computational challenges involved.
      Download PDF-version
    4. Synthesis of Compact Strategies for Coordination Programs

      • Open Access
      Kedar S. Namjoshi, Nisarg Patel
      The chapter 'Synthesis of Compact Strategies for Coordination Programs' by Kedar S. Namjoshi and Nisarg Patel addresses the crucial issue of synthesizing coordination strategies that are guaranteed not to initiate unnecessary actions in multi-agent settings like IoT and robotics. Current methods may produce strategies that issue useless actions, making coordination an attractive target for automated program synthesis. The authors formalize the notion of 'compactness' and propose a solution that transforms a given temporal logic specification using automata-theoretic constructions to incorporate a notion of minimality. The central result is that the winning strategies for the transformed specification are precisely the compact strategies for the original. This allows the application of known synthesis methods to produce compact strategies. The chapter reports on prototype implementations and experiments that demonstrate the feasibility and effectiveness of the proposed methods. It also discusses the relationship to quantitative synthesis and presents approximation methods to handle the complexity of synthesizing compact strategies. The work brings attention to the need for compactness in program synthesis and provides a precise formulation and practical algorithms to achieve it.
      Download PDF-version
    5. ZDD Boolean Synthesis

      • Open Access
      Yi Lin, Lucas M. Tabajara, Moshe Y. Vardi
      The chapter discusses the application of Zero-Suppressed Binary Decision Diagrams (ZDDs) in boolean synthesis, a process crucial for electronic circuits and computing. It compares ZDDs with Binary Decision Diagrams (BDDs), demonstrating that ZDDs can offer more compact representations and faster compilation times. The authors present a full investigation comparing the sizes and performance of ZDDs and BDDs, focusing on realizability, witness construction, and end-to-end synthesis. Experimental results show that while neither approach dominates across all benchmarks, ZDDs excel in certain scalable families of formulas. This makes the chapter a valuable resource for researchers and practitioners in boolean logic and circuit design, offering insights into the potential of ZDDs as a complementary tool in boolean synthesis.
      Download PDF-version
  2. Verification

    1. Frontmatter

    2. Comparative Verification of the Digital Library of Mathematical Functions and Computer Algebra Systems

      • Open Access
      André Greiner-Petter, Howard S. Cohl, Abdou Youssef, Moritz Schubotz, Avi Trost, Rajen Dey, Akiko Aizawa, Bela Gipp
      The chapter focuses on the comparison and verification of the Digital Library of Mathematical Functions (DLMF) and two general-purpose computer algebra systems (CAS), Maple and Mathematica. The authors introduce a novel approach to translate mathematical expressions from the DLMF to these CAS using their previously developed tool, LACAST. The study highlights the challenges and solutions in translating mathematical expressions, particularly focusing on the semantic ambiguity of mathematical notations. The authors address issues related to the translation of sums, products, integrals, limits, and differentiations, thereby enhancing the reliability and coverage of the translations. The paper also provides an in-depth evaluation of the DLMF using both symbolic and numeric evaluations in Maple and Mathematica. The results demonstrate the feasibility and limitations of the translation approach, showcasing the potential for improving and verifying digital mathematical libraries and CAS. The chapter concludes with the provision of open access to all translations and the source code of LACAST, making it a valuable resource for researchers and practitioners in the field.
      Download PDF-version
    3. Verifying Fortran Programs with CIVL

      • Open Access
      Wenhao Wu, Jan Hückelheim, Paul D. Hovland, Stephen F. Siegel
      The chapter discusses the extension of the CIVL verification framework to handle Fortran programs, a language widely used in computational science and high-performance computing. The extension allows CIVL to directly consume Fortran source files, supporting features like array slicing and reshaping, and finding program violations specific to Fortran. The authors demonstrate the tool's effectiveness on a verification benchmark suite and real-world application kernels, showcasing its ability to verify functional correctness properties and detect defects. The chapter also highlights the challenges of preserving defects during translation and the importance of static analysis in the verification process.
      Download PDF-version
    4. NORMA: a tool for the analysis of Relay-based Railway Interlocking Systems

      • Open Access
      Arturo Amendola, Anna Becchi, Roberto Cavada, Alessandro Cimatti, Andrea Ferrando, Lorenzo Pilati, Giuseppe Scaglione, Alberto Tacchella, Marco Zamboni
      The chapter introduces Norma, a tool designed to analyze Relay-based Railway Interlocking Systems (RRIS). Developed with funding from the Italian Railway Network, Norma supports the reverse engineering and migration of legacy RRIS to modern computer-based systems. It features a graphical modeling interface with over 200 configurable components, and uses formal verification techniques to provide syntactic and semantic checks, simulation, and property extraction. Norma's internal representation is translated into highly optimized Timed nuXmv models, enabling efficient verification and analysis. The tool has been experimentally evaluated on real-world RRIS schematics, demonstrating its effectiveness in supporting modelers and reducing verification times. Norma's unique approach to component-based modeling and its integration of powerful reasoning capabilities make it a standout tool in the field.
      Download PDF-version
    5. Efficient Neural Network Analysis with Sum-of-Infeasibilities

      • Open Access
      Haoze Wu, Aleksandar Zeljić, Guy Katz, Clark Barrett
      The chapter introduces a novel method for analyzing neural network verification queries using the Sum-of-Infeasibilities (SoI) technique. Inspired by methods in convex optimization, the SoI function measures the error in the activation functions and guides the search for satisfying assignments in a convex relaxation of the network. The authors propose DeepSoI, a stochastic procedure that minimizes the SoI using Markov chain Monte Carlo sampling, and demonstrate its integration into a complete verification procedure. The chapter highlights the benefits of the SoI-based approach through extensive experimental evaluation, showing significant performance improvements over existing methods. Additionally, the authors present an interesting use case for improving the perturbation bounds found by adversarial attack algorithms.
      Download PDF-version
  3. Blockchain

    1. Frontmatter

    2. Formal Verification of the Ethereum 2.0 Beacon Chain

      • Open Access
      Franck Cassez, Joanne Fuller, Aditya Asgaonkar
      The chapter 'Formal Verification of the Ethereum 2.0 Beacon Chain' by Franck Cassez, Joanne Fuller, and Aditya Asgaonkar delves into the formal verification of the Ethereum 2.0 Beacon Chain, a pivotal component of the new Proof-of-Stake Ethereum network. The authors detail their methodology using the verification-friendly language Dafny to verify the absence of runtime errors in the reference implementation. They uncovered several issues, proposed verified fixes, and synthesized functional correctness specifications. The chapter highlights the importance of formal verification in ensuring the safety and reliability of the Beacon Chain, which manages a vast amount of assets and is crucial for the Ethereum 2.0 ecosystem. The authors also discuss the challenges and lessons learned during the verification process, providing valuable insights into the practical application of formal methods in blockchain technology.
      Download PDF-version
    3. Fast and Reliable Formal Verification of Smart Contracts with the Move Prover

      • Open Access
      David Dill, Wolfgang Grieskamp, Junkil Park, Shaz Qadeer, Meng Xu, Emma Zhong
      The Move Prover (MVP) is a formal verification tool designed for smart contracts written in the Move programming language, which is used in the Diem blockchain. The chapter discusses the challenges and solutions in making MVP fast and reliable, including an alias-free memory model, fine-grained invariant checking, and monomorphization. These improvements have significantly reduced verification times and timeouts, making MVP practical for routine use by developers. The chapter also explores the design of MVP and its specification language, which supports expressive specifications and invariants. The Move Prover has been successfully applied to verify large parts of the Diem framework and is integrated into the continuous integration process, ensuring the reliability of smart contracts.
      Download PDF-version
    4. A Max-SMT Superoptimizer for EVM handling Memory and Storage

      • Open Access
      Elvira Albert, Pablo Gordillo, Alejandro Hernández-Cerezo, Albert Rubio
      The chapter introduces GASOLv2, a superoptimizer for Ethereum smart contracts that optimizes both gas consumption and byte-size. It leverages a Max-SMT approach to handle memory and storage operations, addressing challenges that were previously left unresolved. The tool is designed to work with the Solidity compiler solc and has shown significant improvements in optimization. The chapter discusses the architecture and components of GASOLv2, including the synthesis of stack and memory specifications, simplification rules, and the use of a Max-SMT solver for optimization. The authors present experimental results demonstrating the effectiveness of GASOLv2 in achieving substantial gains in gas consumption and byte-size optimization. The chapter also highlights the practical implications of handling memory operations in superoptimization and the potential for further improvements in the field.
      Download PDF-version
  4. Grammatical Inference

    1. Frontmatter

    2. A New Approach for Active Automata Learning Based on Apartness

      • Open Access
      Frits Vaandrager, Bharat Garhewal, Jurriaan Rot, Thorsten Wißmann
      The chapter introduces a new method for active automata learning called L#, which focuses on establishing apartness rather than equivalence of observations. This approach simplifies the learning process by directly operating on an observation tree, avoiding the need for auxiliary data structures like observation tables. The L# algorithm has the same asymptotic query and symbol complexities as the best existing learning algorithms but integrates adaptive distinguishing sequences to boost performance. Experiments with a prototype implementation suggest that L# is competitive with highly optimized algorithms. The chapter also discusses related work, including other approaches to active automata learning and the integration of conformance testing techniques to enhance learning efficiency.
      Download PDF-version
    3. Learning Realtime One-Counter Automata

      • Open Access
      Véronique Bruyère, Guillermo A. Pérez, Gaëtan Staquet
      The chapter introduces a novel algorithm for learning realtime one-counter automata, which are more expressive models than finite-state automata. The algorithm extends Angluin’s L∗ algorithm by incorporating counter value and partial equivalence queries, enabling it to handle more complex systems. The authors prove that their algorithm runs in exponential time and space, and they evaluate it through experiments on random benchmarks and a use case involving JSON-stream validation. The chapter also discusses the challenges and future work in refining the algorithm and its applications.
      Download PDF-version
    4. Scalable Anytime Algorithms for Learning Fragments of Linear Temporal Logic

      • Open Access
      Ritam Raha, Rajarshi Roy, Nathanaël Fijalkow, Daniel Neider
      The chapter introduces a novel algorithm for learning formulas in fragments of Linear Temporal Logic (LTL) without the U-operator, addressing the scalability and computational resource issues of existing methods. The algorithm is anytime, meaning it can produce separating formulas even if it times out, and it uses a combination of directed formulas and Boolean combinations to construct these formulas efficiently. The authors demonstrate the algorithm's effectiveness and scalability through empirical evaluations, showing that it outperforms existing tools in both speed and the size of formulas it can learn. The chapter also discusses the theoretical guarantees of the algorithm and its potential for future extensions to full LTL.
      Download PDF-version
    5. Learning Model Checking and the Kernel Trick for Signal Temporal Logic on Stochastic Processes

      • Open Access
      Luca Bortolussi, Giuseppe Maria Gallo, Jan Křetínský, Laura Nenzi
      The chapter discusses the application of the kernel trick to Signal Temporal Logic (STL) formulae, enabling efficient learning and prediction of formula satisfaction on stochastic processes. The authors introduce a kernel function for STL that allows for the circumvention of manual feature extraction, demonstrating the high precision and computational efficiency of their approach. The chapter also provides a theoretical analysis with a PAC bound, ensuring the close-to-optimal performance of their predictor. The authors evaluate their method through experiments and showcase its practical applicability to various stochastic processes and real-world formulae.
      Download PDF-version
Next
  • current Page 1
  • 2
Title
Tools and Algorithms for the Construction and Analysis of Systems
Editors
Dr. Dana Fisman
Grigore Rosu
Copyright Year
2022
Electronic ISBN
978-3-030-99524-9
Print ISBN
978-3-030-99523-2
DOI
https://doi.org/10.1007/978-3-030-99524-9

Accessibility information for this book is coming soon. We're working to make it available as quickly as possible. Thank you for your patience.

Premium Partner

    Image Credits
    Neuer Inhalt/© ITandMEDIA, Nagarro GmbH/© Nagarro GmbH, AvePoint Deutschland GmbH/© AvePoint Deutschland GmbH, AFB Gemeinnützige GmbH/© AFB Gemeinnützige GmbH, USU GmbH/© USU GmbH, Ferrari electronic AG/© Ferrari electronic AG