The Experts below are selected from a list of 63069 Experts worldwide ranked by ideXlab platform
Jeffrey S. Foster - One of the best experts on this subject based on the ideXlab platform.
-
Template-based Program Verification and Program synthesis
International Journal on Software Tools for Technology Transfer, 2012Co-Authors: Saurabh Srivastava, Sumit Gulwani, Jeffrey S. FosterAbstract:Program Verification is the task of automatically generating proofs for a Program’s compliance with a given specification. Program synthesis is the task of automatically generating a Program that meets a given specification. Both Program Verification and Program synthesis can be viewed as search problems, for proofs and Programs, respectively. For these search problems, we present approaches based on user-provided insights in the form of templates. Templates are hints about the syntactic forms of the invariants and Programs, and help guide the search for solutions. We show how to reduce the template-based search problem to satisfiability solving, which permits the use of off-the-shelf solvers to efficiently explore the search space. Template-based approaches have allowed us to verify and synthesize Programs outside the abilities of previous verifiers and synthesizers. Our approach can verify and synthesize difficult algorithmic textbook Programs (e.g., sorting and dynamic Programming-based algorithms) and difficult arithmetic Programs.
-
from Program Verification to Program synthesis
Symposium on Principles of Programming Languages, 2010Co-Authors: Saurabh Srivastava, Sumit Gulwani, Jeffrey S. FosterAbstract:This paper describes a novel technique for the synthesis of imperative Programs. Automated Program synthesis has the potential to make Programming and the design of systems easier by allowing Programs to be specified at a higher-level than executable code. In our approach, which we call proof-theoretic synthesis, the user provides an input-output functional specification, a description of the atomic operations in the Programming language, and a specification of the synthesized Program's looping structure, allowed stack space, and bound on usage of certain operations. Our technique synthesizes a Program, if there exists one, that meets the input-output specification and uses only the given resources. The insight behind our approach is to interpret Program synthesis as generalized Program Verification, which allows us to bring Verification tools and techniques to Program synthesis. Our synthesis algorithm works by creating a Program with unknown statements, guards, inductive invariants, and ranking functions. It then generates constraints that relate the unknowns and enforces three kinds of requirements: partial correctness, loop termination, and well-formedness conditions on Program guards. We formalize the requirements that Program Verification tools must meet to solve these constraint and use tools from prior work as our synthesizers. We demonstrate the feasibility of the proposed approach by synthesizing Programs in three different domains: arithmetic, sorting, and dynamic Programming. Using Verification tools that we previously built in the VS3 project we are able to synthesize Programs for complicated arithmetic algorithms including Strassen's matrix multiplication and Bresenham's line drawing; several sorting algorithms; and several dynamic Programming algorithms. For these Programs, the median time for synthesis is 14 seconds, and the ratio of synthesis to Verification time ranges between 1x to 92x (with an median of 7x), illustrating the potential of the approach.
Keiichi Watanabe - One of the best experts on this subject based on the ideXlab platform.
-
higher order Program Verification via hfl model checking
European Symposium on Programming, 2018Co-Authors: Naoki Kobayashi, Takeshi Tsukada, Keiichi WatanabeAbstract:There are two kinds of higher-order extensions of model checking: HORS model checking and HFL model checking. Whilst the former has been applied to automated Verification of higher-order functional Programs, applications of the latter have not been well studied. In the present paper, we show that various Verification problems for functional Programs, including may/must-reachability, trace properties, and linear-time temporal properties (and their negations), can be naturally reduced to (extended) HFL model checking. The reductions yield a sound and complete logical characterization of those Program properties. Compared with the previous approaches based on HORS model checking, our approach provides a more uniform, streamlined method for higher-order Program Verification.
Naoki Kobayashi - One of the best experts on this subject based on the ideXlab platform.
-
on average case hardness of higher order model checking
5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020), 2020Co-Authors: Yoshiki Nakamura, Kazuyuki Asada, Naoki Kobayashi, Ryoma Sinya, Takeshi TsukadaAbstract:We study a mixture between the average case and worst case complexities of higher-order model checking, the problem of deciding whether the tree generated by a given λ Y-term (or equivalently, a higher-order recursion scheme) satisfies the property expressed by a given tree automaton. Higher-order model checking has recently been studied extensively in the context of higher-order Program Verification. Although the worst-case complexity of the problem is k-EXPTIME complete for order-k terms, various higher-order model checkers have been developed that run efficiently for typical inputs, and Program Verification tools have been constructed on top of them. One may, therefore, hope that higher-order model checking can be solved efficiently in the average case, despite the worst-case complexity. We provide a negative result, by showing that, under certain assumptions, for almost every term, the higher-order model checking problem specialized for the term is k-EXPTIME hard with respect to the size of automata. The proof is based on a novel intersection type system that characterizes terms that do not contain any useless subterms.
-
higher order Program Verification via hfl model checking
European Symposium on Programming, 2018Co-Authors: Naoki Kobayashi, Takeshi Tsukada, Keiichi WatanabeAbstract:There are two kinds of higher-order extensions of model checking: HORS model checking and HFL model checking. Whilst the former has been applied to automated Verification of higher-order functional Programs, applications of the latter have not been well studied. In the present paper, we show that various Verification problems for functional Programs, including may/must-reachability, trace properties, and linear-time temporal properties (and their negations), can be naturally reduced to (extended) HFL model checking. The reductions yield a sound and complete logical characterization of those Program properties. Compared with the previous approaches based on HORS model checking, our approach provides a more uniform, streamlined method for higher-order Program Verification.
-
higher order multi parameter tree transducers and recursion schemes for Program Verification
Symposium on Principles of Programming Languages, 2010Co-Authors: Naoki Kobayashi, Naoshi Tabuchi, Hiroshi UnnoAbstract:We introduce higher-order, multi-parameter, tree transducers (HMTTs, for short), which are kinds of higher-order tree transducers that take input trees and output a (possibly infinite) tree. We study the problem of checking whether the tree generated by a given HMTT conforms to a given output specification, provided that the input trees conform to input specifications (where both input/output specifications are regular tree languages). HMTTs subsume higher-order recursion schemes and ordinary tree transducers, so that their Verification has a number of potential applications to Verification of functional Programs using recursive data structures, including resource usage Verification, string analysis, and exact type-checking of XML-processing Programs. We propose a sound but incomplete Verification algorithm for the HMTT Verification problem: the algorithm reduces the Verification problem to a model-checking problem for higher-order recursion schemes extended with finite data domains, and then uses (an extension of)Kobayashi's algorithm for model-checking recursion schemes. While the algorithm is incomplete (indeed, as we show in the paper, the Verification problem is undecidable in general), it is sound and complete for a subclass of HMTTs called linear HMTTs . We have applied our HMTT Verification algorithm to various Program Verification problems and obtained promising results.
Saurabh Srivastava - One of the best experts on this subject based on the ideXlab platform.
-
Template-based Program Verification and Program synthesis
International Journal on Software Tools for Technology Transfer, 2012Co-Authors: Saurabh Srivastava, Sumit Gulwani, Jeffrey S. FosterAbstract:Program Verification is the task of automatically generating proofs for a Program’s compliance with a given specification. Program synthesis is the task of automatically generating a Program that meets a given specification. Both Program Verification and Program synthesis can be viewed as search problems, for proofs and Programs, respectively. For these search problems, we present approaches based on user-provided insights in the form of templates. Templates are hints about the syntactic forms of the invariants and Programs, and help guide the search for solutions. We show how to reduce the template-based search problem to satisfiability solving, which permits the use of off-the-shelf solvers to efficiently explore the search space. Template-based approaches have allowed us to verify and synthesize Programs outside the abilities of previous verifiers and synthesizers. Our approach can verify and synthesize difficult algorithmic textbook Programs (e.g., sorting and dynamic Programming-based algorithms) and difficult arithmetic Programs.
-
from Program Verification to Program synthesis
Symposium on Principles of Programming Languages, 2010Co-Authors: Saurabh Srivastava, Sumit Gulwani, Jeffrey S. FosterAbstract:This paper describes a novel technique for the synthesis of imperative Programs. Automated Program synthesis has the potential to make Programming and the design of systems easier by allowing Programs to be specified at a higher-level than executable code. In our approach, which we call proof-theoretic synthesis, the user provides an input-output functional specification, a description of the atomic operations in the Programming language, and a specification of the synthesized Program's looping structure, allowed stack space, and bound on usage of certain operations. Our technique synthesizes a Program, if there exists one, that meets the input-output specification and uses only the given resources. The insight behind our approach is to interpret Program synthesis as generalized Program Verification, which allows us to bring Verification tools and techniques to Program synthesis. Our synthesis algorithm works by creating a Program with unknown statements, guards, inductive invariants, and ranking functions. It then generates constraints that relate the unknowns and enforces three kinds of requirements: partial correctness, loop termination, and well-formedness conditions on Program guards. We formalize the requirements that Program Verification tools must meet to solve these constraint and use tools from prior work as our synthesizers. We demonstrate the feasibility of the proposed approach by synthesizing Programs in three different domains: arithmetic, sorting, and dynamic Programming. Using Verification tools that we previously built in the VS3 project we are able to synthesize Programs for complicated arithmetic algorithms including Strassen's matrix multiplication and Bresenham's line drawing; several sorting algorithms; and several dynamic Programming algorithms. For these Programs, the median time for synthesis is 14 seconds, and the ratio of synthesis to Verification time ranges between 1x to 92x (with an median of 7x), illustrating the potential of the approach.
-
Program Verification using templates over predicate abstraction
Programming Language Design and Implementation, 2009Co-Authors: Saurabh Srivastava, Sumit GulwaniAbstract:We address the problem of automatically generating invariants with quantified and boolean structure for proving the validity of given assertions or generating pre-conditions under which the assertions are valid. We present three novel algorithms, having different strengths, that combine template and predicate abstraction based formalisms to discover required sophisticated Program invariants using SMT solvers. Two of these algorithms use an iterative approach to compute fixed-points (one computes a least fixed-point and the other computes a greatest fixed-point), while the third algorithm uses a constraint based approach to encode the fixed-point. The key idea in all these algorithms is to reduce the problem of invariant discovery to that of finding optimal solutions for unknowns (over conjunctions of some predicates from a given set) in a template formula such that the formula is valid. Preliminary experiments using our implementation of these algorithms show encouraging results over a benchmark of small but complicated Programs. Our algorithms can verify Program properties that, to our knowledge, have not been automatically verified before. In particular, our algorithms can generate full correctness proofs for sorting algorithms (which requires nested universally-existentially quantified invariants) and can also generate preconditions required to establish worst-case upper bounds of sorting algorithms. Furthermore, for the case of previously considered properties, in particular sortedness in sorting algorithms, our algorithms take less time than reported by previous techniques.
Bernhard Beckert - One of the best experts on this subject based on the ideXlab platform.
-
an introduction to voting rule Verification
Trends in Computational Social Choice. Ed by.: Ulle Endriss, 2017Co-Authors: Bernhard Beckert, Thorsten Bormer, Rajeev Gore, Michael Kirsten, Carsten SchurmannAbstract:We give an introduction to deductive Verification methods that can be used to formally prove that voting rules and their implementations satisfy specified properties and conform to the desired democratic principles. In the first part of the paper we explain the basic principles: We describe how first-order logic with theories can be used to formalise the desired properties. We explain the difference between (1) proving that one set of properties implies another property, (2) proving that a voting rule implementation has a certain property, and (3) proving that a voting rule implementation is a refinement of an executable specification. And we explain the different technologies: (1) SMT-based testing, (2) bounded Program Verification, (3) relational Program Verification, and (4) symmetry breaking. In this first part of the paper, we also explain the difference between verifying functional and relational properties (such as symmetries). In the second part, we present case studies, including (1) the specification and Verification of semantic properties for an STV rule used for electing the board of trustees for a major international conference and (2) the deduction-based computation of election margins for the Danish national parliamentary elections.
-
a metric for testing Program Verification systems
Tests and Proofs, 2013Co-Authors: Bernhard Beckert, Thorsten Bormer, Markus WagnerAbstract:The correctness of Program Verification systems is of great importance, and it needs to be checked and demonstrated to users and certification agencies. One of the contributing factors to the correctness of the whole Verification system is the correctness of the background axiomatization, respectively the correctness of calculus rules. In this paper, we examine how testing Verification systems is able to provide evidence for the correctness of the rule base or the axiomatization. For this, we present a new coverage criterion called axiomatization coverage, which allows us to judge the quality of existing test suites for Verification systems. We evaluate this coverage criterion at two Verification tools using the test suites provided by each tool.
-
dynamic logic with trace semantics
Conference on Automated Deduction, 2013Co-Authors: Bernhard Beckert, Daniel BrunsAbstract:Dynamic logic is an established instrument for Program Verification and for reasoning about the semantics of Programs and Programming languages. In this paper, we define an extension of dynamic logic, called Dynamic Trace Logic (DTL), which combines the expressiveness of Program logics such as dynamic logic with that of temporal logic. And we present a sound and relatively complete sequent calculus for proving validity of DTL formulae. Due to its expressiveness, DTL can serve as a basis for proving functional and information-flow properties in concurrent Programs, among other applications.
-
practical aspects of automated deduction for Program Verification
Künstliche Intelligenz, 2010Co-Authors: Wolfgang Ahrendt, Martin Giese, Bernhard Beckert, Philipp RümmerAbstract:Software is vital for modern society. It is used in many safety- or security-critical applications, where a high degree of correctness is desirable. Over the last years, technologies for the formal specification and Verification of software—using logic-based specification languages and automated deduction—have matured and can be expected to complement and partly replace traditional software engineering methods in the future. Program Verification is an increasingly important application area for automated deduction. The field has outgrown the area of academic case studies, and industry is showing serious interest. This article describes the aspects of automated deduction that are important for Program Verification in practise, and it gives an overview of the reasoning mechanisms, the methodology, and the architecture of modern Program Verification systems.
-
dynamic logic with non rigid functions a basis for object oriented Program Verification
Lecture Notes in Computer Science, 2006Co-Authors: Bernhard Beckert, Andre PlatzerAbstract:We introduce a dynamic logic that is enriched by non-rigid functions, i.e., functions that may change their value from state to state (during Program execution), and we present a (relatively) complete sequent calculus for this logic. In conjunction with dynamically typed object enumerators, non-rigid functions allow to embed notions of object-orientation in dynamic logic, thereby forming a basis for Verification of object-oriented Programs. A semantical generalisation of substitutions, called state update, which we add to the logic, constitutes the central technical device for dealing with object aliasing during function modification. With these few extensions, our dynamic logic captures the essential aspects of the complex Verification system KeY and, hence, constitutes a foundation for object-oriented Verification with the principles of reasoning that underly the successful KeY case studies.
