Nurit Dor, Michael Rodeh, Mooly Sagiv · 2015
Erroneous string manipulations are a major source of soft-ware defects in C programs yielding vulnerabilities which are exploited by software viruses. We present C String Static Verifyer (CSSV), a tool that statically uncovers all string manipulation errors. Being a conservative tool, it reports all such errors at the expense of sometimes generating false alarms. Fortunately, only a small number of false alarms are reported, thereby proving that statically reducing software vulnerability is achievable. CSSV handles large programs by analyzing each procedure separately. To this end procedure contracts are allowed which are verified by the tool. We implemented a CSSV prototype and used it to ver-ify the absence of errors in real code from EADS Airbus. When applied to another commonly used string intensive application, CSSV uncovered real bugs with very few false alarms.
Cited by 0
Pratiksha Thaker, Danny Tarlow, Marc Brockschmidt et al. · 2017
We present an algorithm for specifying and sampling from distributions over programs via a perturb-max approximation. Prior work is generally limited to sampling from priors over program syntax (for example, assigning lower probability to longer programs). We demonstrate a simple modification to our sampling algorithm that allows interpolation between such syntactic priors and priors over semantics (that is, the behavior of the program on its inputs, or the set of class labels when the program is viewed as a statistical model).
Cited by 0
Roberto Giacobazzi, Francesco Ranzato · Lecture notes in computer science · 1996
Cited by 10Open access
Daejun Park · IDEALS (University of Illinois Urbana-Champaign) · 2019
We present language-independent formal methods that are parameterized by the operational semantics of languages. We provide the theory, implementation, and extensive evaluation of the language-parametric formal methods. Specifically, we consider two formal analyses: program verification and program equivalence.\nFirst, we propose a novel notion of bisimulation, which we call cut-bisimulation, allowing the two programs to semantically synchronize at relevant "cut" points, but to evolve independently otherwise. Employing the cut-bisimulation, we develop a language-independent equivalence checking algorithm, parameterized by the input and output language semantics, to prove equivalence of programs written in possibly different languages. We implement the algorithm in the K framework, yielding the first language-parametric program equivalence checker.\nTo demonstrate the practical feasibility of the language-parametric formal methods, we instantiate a language-independent deductive program verifier by plugging-in four real-world language semantics, C, Java, JavaScript, and Ethereum Virtual Machine (EVM), and use them to verify full functional correctness of challenging heap-manipulating programs and high-profile commercial smart contracts. In particular, to the best of our knowledge, the JavaScript and EVM verifiers are the first deductive program verifier for these languages.
Cited by 0Open access
Karl Lermer, Colin Fidge, Ian J. Hayes · Electronic Notes in Theoretical Computer Science · 2003
This paper provides the syntax and semantics for a systematic approach to the problem of analysing control-flow paths in computer programs. We give an abstract syntax and a partial correctness semantics for program control-flow paths as a generic model for path analysis and constraint derivation. This approach is formally based on a predicate transformer semantics over a boolean-valued predicate space and an abstract command language. The notions of a command, dead commands, the entry and exit conditions of a command and the inverse of a command are formally defined and investigated on the base of the semantics. A notion of command refinement is introduced capturing the abstraction process in program development from specification to implementation with partial correctness. Furthermore, command-reduction theorems and characterisations for command refinement are derived using the underlying semantics. Finally we verify the equivalence of weakest liberal precondition and strongest postcondition semantics for program commands in terms of the ordering relation they define on the command language. The approach is generic in that it is applicable to any program language that can be supplied with a predicate transformer semantics.
Cited by 6Open access
Ernest G. Manes, Michael A. Arbib · 1986
Cited by 227
Gries, David, Dijkstra, Edsger W, Scholten, Carel S · CERN Document Server (European Organization for Nuclear Research) · 1990
Cited by 0
Sampath, P. · OpenGrey (Institut de l'Information Scientifique et Technique) · 2000
Cited by 0Open access
Guy McCusker · 2008
Game semantics is a way of characterizing programming languages and logical calculi intensionally by interpreting proofs or programs as strategies for interacting with the environment; this process of interaction can be thought of as playing a two-person game. Games can capture precisely the behaviour of higher-order programs in sequential languages, in a fashion which is very difficult or impossible for traditional forms of denotational semantics. This precision can be expressed formally via the properties of full abstraction, full completeness or universality. A remarkable feature of game semantics is its flexibility: games have been used to give fully abstract or fully complete models not only of logics such as linear logic [3] and functional languages such as PCF [1, 12, 38], but also languages with powerful imperative features such as references (state) [4, 2], continuations [32] and exceptions [13]. By contrast, in domain theory programs are modelled extensionally using sets (with certain order-theoretic structure) and functions (preserving that structure). Domains have formed the basis for much research in denotational semantics by virtue of their conceptual simplicity, and now form a wide-ranging mathematical theory. The search for order-theoretic characterizations of higher-order sequentiality has led to the development of several candidate notions, such as stability [5] and strong stability [6], and was arguably the driving force behind most work in denotational semantics for some years. However, a significant obstacle to the use of domains to reason about programming languages has been a lack of accurate models of imperative and concurrent features of the sort provided by game semantics. A possible basis for connecting the intensional world of games with the extensional world of domains was the remarkable observation of Cartwright and Felleisen [8] \n \n
Cited by 0
Andrew M. Pitts · Lecture notes in computer science · 2002
Cited by 58
Pradeep Kumar Punnam · OhioLink ETD Center (Ohio Library and Information Network) · 2008
Cited by 0Open access
Shan-Jon Chao, Barrett R. Bryant · ACM SIGPLAN Notices · 1988
The denotational semantics approach to formal specification of programming languages contain s detailed information for the implementation of that language, unlike the axiomatic semantics approach . This feature makes the denotational semantics approach more flexible than the operational approach in it s not having any specific abstract machine . A compiler can be systematically constructed from the formal denotational semantics specification by applying the function of the specification to the source program . This is called a compile-evaluate approach for denotational semantics or compiler generation . Compile r generation addresses the issue of proving compiler correctness . This paper describes how to apply denotational semantics to program analysis, specifically cod e optimization, and to the parallel implementation of sequential imperative languages . In considering cod e optimization, the object code derived from the denotational semantics specification is a set of denotations which we claim can be further optimized by partial evaluation . Partial evaluation [5] of a subject progra m evaluates that program with respect to only a portion of its input parameters, resulting in a residua l program . By definition, running the residual program on any remaining input yields the same result a s running the original subject program on all of its input . >From this point of view then, partial evaluatio n is nothing but a special case of program transformation for the purpose of optimization . Partial evaluatio n performs those simplification steps which are not dependent on execution-time values . To determine whic h simplifications to perform, we make an expression unfrozen if it can be simplified before execution-time . A frozen expression may not be simplified . Declarations, environments, and store algebras are all mad e unfrozen resulting in more efficient code . Code optimization on declarations, type checking, constant folding , and inline function expansion will be carried out .
Cited by 4Open access
Irène Guessarian · Theoretical Computer Science · 1979
Cited by 12
Muskens Reinhard, Reinhard Muskens · 2016
Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights.? Users may download and print one copy of any publication from the public portal for the purpose of private study or research? You may not further distribute the material or use it for any profit-making activity or commercial gain? You may freely distribute the URL identifying the publication in the public portal Take down policy If you believe that this document breaches copyright, please contact us providing details, and we will remove access to the work immediately and investigate your claim.
Cited by 0
Thomas Reps, Wuu Yang · Minds at UW (University of Wisconsin) · 1988
... This paper concerns the relationship between the execution behavior of a program and the execution behavior of its slices. Our main results are those stated as the Slicing Theorem and the Termination Theorem. The Slicing Theorem demonstrates that a slice captures a portion of a program's behavior in the sense that, for any initial state on which the program halts, the program and the slice compute the same sequence of values for each element of the slice. The Termination Theorem demonstrates that if a program is decomposed into (two or more) slices, the program halts on any state for which all the slices halt. These
Cited by 31Open access
Egon Börger · Science of Computer Programming · 1994
Cited by 8
Jidesh Soudamini · OhioLink ETD Center (Ohio Library and Information Network) · 2006
Cited by 0Open access
Andrew M. Pitts · 2000
Cited by 10
Yifeng Chen · Lecture notes in computer science · 2013
Cited by 0
Brian Monahan · Science of Computer Programming · 1991
Cited by 38