The Experts below are selected from a list of 327 Experts worldwide ranked by ideXlab platform
K. Rustan M. Leino - One of the best experts on this subject based on the ideXlab platform.
-
Weakest-Precondition of unstructured programs
ACM SIGSOFT Software Engineering Notes, 2006Co-Authors: Mike Barnett, K. Rustan M. LeinoAbstract:Program verification systems typically transform a program into a logical expression which is then fed to a theorem prover. The logical expression represents the Weakest Precondition of the program relative to its specification; when (and if!) the theorem prover is able to prove the expression, then the program is considered correct. Computing such a logical expression for an imperative, structured program is straightforward, although there are issues having to do with loops and the efficiency both of the computation and of the complexity of the formula with respect to the theorem prover. This paper presents a novel approach for computing the Weakest Precondition of an unstructured program that is sound even in the presence of loops. The computation is efficient and the resulting logical expression provides more leeway for the theorem prover efficiently to attack the proof.
-
PASTE - Weakest-Precondition of unstructured programs
The 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering - PASTE '05, 2005Co-Authors: Mike Barnett, K. Rustan M. LeinoAbstract:Program verification systems typically transform a program into a logical expression which is then fed to a theorem prover. The logical expression represents the Weakest Precondition of the program relative to its specification; when (and if!) the theorem prover is able to prove the expression, then the program is considered correct. Computing such a logical expression for an imperative, structured program is straightforward, although there are issues having to do with loops and the efficiency both of the computation and of the complexity of the formula with respect to the theorem prover. This paper presents a novel approach for computing the Weakest Precondition of an unstructured program that is sound even in the presence of loops. The computation is efficient and the resulting logical expression provides more leeway for the theorem prover efficiently to attack the proof.
-
Efficient Weakest Preconditions
Information Processing Letters, 2005Co-Authors: K. Rustan M. LeinoAbstract:Desired computer-program properties can be described by logical formulas called verification conditions. Different mathematically-equivalent forms of these verification conditions can have a great impact on the performance of an automatic theorem prover that tries to discharge them. This paper presents a simple Weakest-Precondition understanding of the ESC/Java technique for generating verification conditions. This new understanding of the technique spotlights the program property that makes the technique work.
-
PROCOMET - Semantics of Exceptions
1994Co-Authors: K. Rustan M. Leino, Jan L. A. Van De SnepscheutAbstract:We describe a trace semantics of exceptions and then derive a Weakest Precondition semantics. A program that contains exceptions terminates in one of two possible ways (if it terminates at all): either it terminates exceptionally or it terminates normally. We will therefore consider Weakest Preconditions that are functions of two postconditions. As a preparation we study aribitrary functions of two arguments, and their compositions.
Anup Bandyopadhyay - One of the best experts on this subject based on the ideXlab platform.
-
Weakest Precondition based modelling and verification of a class of concurrent systems
2010Co-Authors: Anup BandyopadhyayAbstract:A Weakest Precondition based modelling and verification technique for a class of concurrent systems is proposed. A system in this class is defined by a set of non-terminating interactive sequential processes. The constituent processes are allowed to include both if-then-else and terminating while-do type control structures. The properties of the system are verified by proving the invariance of logical formulae. The technique is illustrated by considering Dekker's two process mutual exclusion algorithm as an example.
-
Weakest Precondition based verification tool that models spatial ordering
ACM SIGSOFT Software Engineering Notes, 2008Co-Authors: Anup BandyopadhyayAbstract:Weakest Precondition based method for specification and verification of geographically distributed system is described. For this purpose spatial predicates have been defined. A distributed mutual exclusion algorithm is proposed and is used to illustrate this verification tool.
-
Some investigations on deadlock freedom issues of a cyclically connected system using Dijkstra's Weakest Precondition calculus
ACM SIGPLAN Notices, 2007Co-Authors: Jayasri Banerjee, Anup Bandyopadhyay, Ajit K. MandalAbstract:Weakest Precondition calculus is used to specify a system implemented by a cyclic interconnection of sequential processes. From this specification a predicate is derived that describes the deadlock freedom property of the system. Invariance of the predicate is proved from the specification.
-
Application of Dijkstra's Weakest Precondition calculus to Dining Philosophers problem
ACM SIGSOFT Software Engineering Notes, 2007Co-Authors: Jayasri Banerjee, Anup Bandyopadhyay, Ajit K. MandalAbstract:Dijkstra's Weakest Precondition calculus is used to model the well known Dining Philosophers problem. Process and state definitions are done in such a manner that only the deadlock property of the system is highlighted. Care has been taken to choose the proper details such that it is not too elaborate to obscure the requirements also not be too abstract to mask the actual analytical needs. State transition rules specify the system behavior. Intuitive reasoning as well as formal technique has been applied to get the deadlock condition. Two well known solutions are specified and proved. The proof technique being analytical, its complexity does not depend on the size of the problem. The second solution requires an event ordering and therefore a temporal ordering predicate has been used to prove its correctness.
-
Modeling fairness and starvation in concurrent systems
ACM SIGSOFT Software Engineering Notes, 2007Co-Authors: Anup BandyopadhyayAbstract:Standard temporal logic is augmented and a new temporal quantifier viz., never is defined. This augmented logic is integrated in Dijkstra's Weakest Precondition calculus. Definitions for fairness and starvation for concurrent systems in terms of Weakest Precondition are presented. According to the existing concept fairness for a transition rule asserts that if a rule remains continuously enabled (weak fairness) or repeatedly enabled (strong fairness), then it must be executed., where in the proposed definition fairness is related to the permission for execution where starvation relies upon actual execution. This definition is used to prove fairness of a given concurrent system. Through different examples it is shown that fairness is not the only prerequisite for starvation freedom. Available techniques use 'leads to' operator that forecasts system behavior where the proposed proof technique moves backward in time.
Runyao Duan - One of the best experts on this subject based on the ideXlab platform.
-
Commutativity of quantum Weakest Preconditions
Information Processing Letters, 2007Co-Authors: Mingsheng Ying, Yuan Feng, Jianxin Chen, Runyao DuanAbstract:The notion of quantum Weakest Precondition was introduced by D'Hondt and P. Panangaden [E. D'Hondt, P. Panangaden, Quantum Weakest Preconditions, Mathematical Structures in Computer Science 16 (2006) 429-451], and they presented a representation of Weakest Precondition of a quantum program in the operator-sum form. In this Letter, we give an intrinsic characterization of the Weakest Precondition of a quantum program given in a system-environment model. Furthermore, some sufficient conditions for commutativity of quantum Weakest Preconditions are presented.
-
Proof rules for purely quantum programs
arXiv: Programming Languages, 2005Co-Authors: Yuan Feng, Runyao Duan, Mingsheng YingAbstract:AbstractWe apply the notion of quantumpredicate proposed by D’Hondt and Panangaden to analyzea purely quantum language fragment which describes the quantum part of a future quantumcomputer in Knill’s architecture. The denotational semantics, Weakest Precondition semantics,and Weakest liberal Precondition semantics of this language fragment are introduced. To helpreasoning about quantum programs involving quantum loops, we extend proof rules for classicalprobabilistic programs to our purely quantum programs. 1 Introduction The theory of quantum computing has attracted considerable research efforts in the past twentyyears. Benefiting from the possibility of superposition of different states and the linearity of quantumoperations, quantum computing may provide considerable speedup over its classical analogue [15, 6,7]. The existing quantum algorithms, however, are described at a very low level: they are usuallyrepresented as quantum circuits. A few works have been done in developing quantum programminglanguages which identify and promote high-level abstractions. Knill [8] moved the first step byoutlining a set of basic principles for writing quantum pseudo-code; while the first actual quantumprogramming language is due to Omer [12]. After that, Sanders and Zuliani [13], Bettelli et¨ al. [1],and Selinger [14] also proposed various quantum languages each having different features.The standard Weakest Precondition calculus [4] and its probabilistic extension [11] have beensuccessful in reasoning about the correctness and even the rigorous derivation of classical programs.This success motivates us to develop analogous tools for quantum programs. Sanders and Zuliani[13] have provided for their qGCL a stepwise refinement mechanics. The approach, however, isclassical in the sense that they treated quantum programs as special cases of probabilistic programs.As a consequence, known results about probabilistic Weakest Precondition calculus can be applieddirectly to quantum programs. Indeed, Butler and Hartel [2] have used it to reason about Grover’salgorithm.The first step towards really quantum Weakest Precondition calculus was made by D’Hondt andPanangaden [3]. They proposed the brilliant idea that we can treat an observable, mathematicallydescribed by a Hermitian matrix, as the quantum analogue of ‘predicate’. The elegant dualitybetween state-transformer semantics and the Weakest Precondition semantics of quantum programswas then proven to hold in a more direct way.In this paper, we apply the ideas in [3] to analyze a purely quantum language fragment describingthe quantum part of a potential quantum computer in Knill’s architecture [8]. The syntax followsSelinger’s style but we consider only purely quantum data. We introduce the denotational semantics
Jose Monteiro - One of the best experts on this subject based on the ideXlab platform.
-
VMCAI - Weakest Precondition Synthesis for Compiler Optimizations
Lecture Notes in Computer Science, 2014Co-Authors: Nuno P Lopes, Jose MonteiroAbstract:Compiler optimizations play an increasingly important role in code generation. This is especially true with the advent of resourcelimited mobile devices. We rely on compiler optimizations to improve performance, reduce code size, and reduce power consumption of our programs. Despite being a mature field, compiler optimizations are still designed and implemented by hand, and usually without providing any guarantee of correctness. In addition to devising the code transformations, designers and implementers have to come up with an analysis that determines in which cases the optimization can be safely applied. In other words, the optimization designer has to specify a Precondition that ensures that the optimization is semantics-preserving. However, devising Preconditions for optimizations by hand is a non-trivial task. It is easy to specify a Precondition that, although correct, is too restrictive, and therefore misses some optimization opportunities. In this paper, we propose, to the best of our knowledge, the first algorithm for the automatic synthesis of Preconditions for compiler optimizations. The synthesized Preconditions are provably correct by construction, and they are guaranteed to be the Weakest in the Precondition language that we consider. We implemented the proposed technique in a tool named PSyCO. We present examples of Preconditions synthesized by PSyCO, as well as the results of running PSyCO on a set of optimizations.
-
Weakest Precondition synthesis for compiler optimizations
Verification Model Checking and Abstract Interpretation, 2014Co-Authors: Nuno P Lopes, Jose MonteiroAbstract:Compiler optimizations play an increasingly important role in code generation. This is especially true with the advent of resourcelimited mobile devices. We rely on compiler optimizations to improve performance, reduce code size, and reduce power consumption of our programs. Despite being a mature field, compiler optimizations are still designed and implemented by hand, and usually without providing any guarantee of correctness. In addition to devising the code transformations, designers and implementers have to come up with an analysis that determines in which cases the optimization can be safely applied. In other words, the optimization designer has to specify a Precondition that ensures that the optimization is semantics-preserving. However, devising Preconditions for optimizations by hand is a non-trivial task. It is easy to specify a Precondition that, although correct, is too restrictive, and therefore misses some optimization opportunities. In this paper, we propose, to the best of our knowledge, the first algorithm for the automatic synthesis of Preconditions for compiler optimizations. The synthesized Preconditions are provably correct by construction, and they are guaranteed to be the Weakest in the Precondition language that we consider. We implemented the proposed technique in a tool named PSyCO. We present examples of Preconditions synthesized by PSyCO, as well as the results of running PSyCO on a set of optimizations.
Ana Cavalcanti - One of the best experts on this subject based on the ideXlab platform.
-
Refactoring Towards a Layered Architecture
Electronic Notes in Theoretical Computer Science, 2005Co-Authors: Márcio Cornélio, Ana Cavalcanti, Augusto SampaioAbstract:In this paper we present how refactoring of object-oriented programs can be accomplished by using formal refinement. Our approach is based on the use of refactoring rules designed for a sequential object-oriented language of refinement (rool) similar to Java. We define a strategy that aims at structuring programs according to a layered architecture that involves the application of refactoring rules, object-oriented programming laws, and data and algorithm refinement. As the laws are proved in a Weakest Precondition semantics of rool, correctness of refactoring is ensured by construction.
-
A Weakest Precondition Semantics for Circus
2002Co-Authors: Ana Cavalcanti, Jim WoodcockAbstract:Circus is a combination of Z and CSP; its chief distinguishing feature is the inclusion of the ideas of the refinement calculus. Our main objective is the definition of refinement methods for concurrent programs. The original semantic model for Circus is Hoare and He's unifying theories of programming. In this paper, we present an equivalent semantics based on predicate transformers. With this new model, we provide a more adequate basis for the formalisation of refinement and verification condition generating rules. Furthermore, this new framework makes it possible to include logical variables and angelic nondeterminism in Circus. The consistency of the relational and predicate transformer models gives us confidence in their accuracy.
-
A Weakest Precondition semantics for refinement of object-oriented programs
IEEE Transactions on Software Engineering, 2000Co-Authors: Ana Cavalcanti, David A. NaumannAbstract:We define a predicate-transformer semantics for an object oriented language that includes specification constructs from refinement calculi. The language includes recursive classes, visibility control, dynamic binding, and recursive methods. Using the semantics, we formulate notions of refinement. Such results are a first step toward a refinement calculus.
-
a Weakest Precondition semantics for an object oriented language of refinement
Formal Methods, 1999Co-Authors: Ana Cavalcanti, David A. NaumannAbstract:We define a predicate-transformer semantics for an object-oriented language that includes specification constructs from refinement calculi. The language includes recursive classes, visibility control, dynamic binding, and recursive methods. Using the semantics, we formulate notions of refinement. Such results are a first step towards a refinement calculus.
-
A Weakest Precondition Semantics for Z
The Computer Journal, 1998Co-Authors: Ana Cavalcanti, Jim WoodcockAbstract:The lack of a method for developing programs from Z specifications is a widely recognized difficulty. In response to this problem, different approaches to the integration of Z with a refinement calculus have been proposed. These programming techniques are promising, but as far as we know, have not been formalized. Since they are based on refinement calculi formalized in terms of Weakest Preconditions, the definition of a Weakest Precondition semantics for Z is a significant contribution to the solution of this problem. In this paper, we actually construct a Weakest Precondition semantics from a relational semantics proposed by the Z standards panel. The construction provides reassurance as to the adequacy of the resulting semantics definition and additionally establishes an isomorphism between Weakest Preconditions and relations. Compositional formulations for the Weakest Precondition of some schema calculus expressions are provided.
