We address the problem of the automated verification of temporal properties of infinite state reactive systems. We present some improvements of a verification method based on the specialization of constraint logic pro...
详细信息
ISBN:
(纸本)9783642205507
We address the problem of the automated verification of temporal properties of infinite state reactive systems. We present some improvements of a verification method based on the specialization of constraint logicprograms (CLP). First, we reformulate the verification method as a two-phase procedure: (1) in the first phase a CLP specification of an infinite state system is specialized with respect to the initial state of the system and the temporal property to be verified, and (2) in the second phase the specialized program is evaluated by using a bottom-up strategy. In this paper we propose some new strategies for performing program specialization during the first phase. We evaluate the effectiveness of these new strategies, as well as that of some old strategies, by presenting the results of experiments performed on several infinite state systems and temporal properties. Finally, we compare the implementation of our specialization-based verification method with various constraint-based model checking tools. the experimental results show that our method is effective and competitive with respect to the methods used in those other tools.
Round-off errors arising from the difference between real numbers and their floating-point representation cause the control flow of conditional floating-point statements to deviate from the ideal flow of the real-numb...
详细信息
ISBN:
(纸本)9783030138387;9783030138370
Round-off errors arising from the difference between real numbers and their floating-point representation cause the control flow of conditional floating-point statements to deviate from the ideal flow of the real-number computation. this problem, which is called test instability, may result in a significant difference between the computation of a floating-point program and the expected output in real arithmetic. In this paper, a formally proven programtransformation is proposed to detect and correct the effects of unstable tests. the output of this transformation is a floating-point programthat is guaranteed to return either the result of the original floating-point program when it can be assured that both its real and its floating-point flows agree or a warning when these flows may diverge. the proposed approach is illustrated withthe transformation of the core computation of a polygon containment algorithm developed at NASA that is used in a geofencing system for unmanned aircraft systems.
Propositional simplification and preprocessing are of key importance in the fields of automated reasoning and theorem proving. We present a novel propositional formula representation able to capture all of its n-ary i...
详细信息
ISBN:
(纸本)9783031712937;9783031712944
Propositional simplification and preprocessing are of key importance in the fields of automated reasoning and theorem proving. We present a novel propositional formula representation able to capture all of its n-ary implication information in a tractable manner. From the exploration of this novel encoding in the form of a directed hypergraph, we derive a novel simplification rule which is guaranteed to be equivalencepreserving, monotonically decreasing in the size of the problem, and capable of deep inference. We are not aware of any such generic preprocessing framework capable of systematically simplifying propositional problems in arbitrary form. Interestingly, our rule effectively generalises and streamlines most of the known equivalence-preserving SAT preprocessing techniques. Additionally, since our problem transformations are domain- and application-independent, they can be used in combination with any propositional-logic-based techniques, including those currently used in automated reasoning, solving and optimisation tools.
the proceedings contain 15 papers. the topics discussed include: on optimising shape-generic array programs using symbolic structural information;index vector elimination-making index vectors affordable;functional-bas...
详细信息
ISBN:
(纸本)9783540741299
the proceedings contain 15 papers. the topics discussed include: on optimising shape-generic array programs using symbolic structural information;index vector elimination-making index vectors affordable;functional-basedsynthesis of a systolic array for GCD computation;comparing alternative evaluation strategies for stream-based parallel functional languages;parallel coordination made explicit in a functional setting;a conference management system based on the iData toolkit;a pattern logic for prompt lazy assertions in Haskell;IVOR,a proof engine;proving program properties specified with subtype marks;uniqueness typing redefined;heuristics for type error discovery and recovery;testing properties of generic functions;worst-case execution times for a purely functional language;and automatic partial inversion of inductively sequential functions.
As part of a platform for computer-assisted verification, we present an intermediate representation of programs that is both language independent and appropriate for the generation of verification conditions. We show ...
详细信息
ISBN:
(纸本)9783319274362;9783319274355
As part of a platform for computer-assisted verification, we present an intermediate representation of programs that is both language independent and appropriate for the generation of verification conditions. We show how many imperative and functional languages can be translated to this generic intermediate representation, and how the generated conditions reflect the axiomatic semantics of the original program. At this representation level, loop invariants and preconditions of recursive functions belonging to the original program are represented by assertions placed at certain edges of a directed graph. the paper defines the generic representation, sketches the transformation algorithms, and describes how the places where the invariants should be placed are computed. Assuming that, either manually or assisted by the platform, the invariants have been settled, it is shown how the verification conditions are generated. A running example illustrates the process.
Randomly generated programs are popular for testing compilers and program analysis tools, with hundreds of bugs in real-world C compilers found by random testing. However, existing random program generators may genera...
详细信息
ISBN:
(纸本)9783319944609;9783319944593
Randomly generated programs are popular for testing compilers and program analysis tools, with hundreds of bugs in real-world C compilers found by random testing. However, existing random program generators may generate large amounts of dead code (computations whose result is never used). this leaves relatively little code to exercise a target compiler's more complex optimizations. To address this shortcoming, we introduce liveness-driven random program generation. In this approach the random program is constructed bottom-up, guided by a simultaneous structural data-flow analysis to ensure that the generator never generates dead code. the algorithm is implemented as a plugin for the Frama-C framework. We evaluate it in comparison to Csmith, the standard random C program generator. Our tool generates programs that compile to more machine code with a more complex instruction mix.
program semantics can often be expressed as a (many-sorted) first-order theory S, and program properties as sentences phi which are intended to hold in the canonical model of such a theory, which is often incomputable...
详细信息
ISBN:
(纸本)9783030138387;9783030138370
program semantics can often be expressed as a (many-sorted) first-order theory S, and program properties as sentences phi which are intended to hold in the canonical model of such a theory, which is often incomputable. Recently, we have shown that properties phi expressed as the existential closure of a boolean combination of atoms can be disproved by just finding a model of S and the negation (sic)phi of phi. Furthermore, this idea works quite well in practice due to the existence of powerful tools for the automatic generation of models for (many-sorted) first-order theories. In this paper we extend our previous results to arbitrary properties, expressed as sentences without any special restriction. Consequently, one can prove a program property. by just finding a model of an appropriate theory (including S and possibly something else) and an appropriate first-order formula related to.. Beyond its possible theoretical interest, we show that our results can also be of practical use in several respects.
We explore a transformational approach to the problem of verifying simple array-manipulating programs. Traditionally, verification of such programs requires intricate analysis machinery to reason with universally quan...
详细信息
ISBN:
(纸本)9783319178226;9783319178219
We explore a transformational approach to the problem of verifying simple array-manipulating programs. Traditionally, verification of such programs requires intricate analysis machinery to reason with universally quantified statements about symbolic array segments, such as "every data item stored in the segment A[i] to A[j] is equal to the corresponding item stored in the segment B[i] to B[j]." We define a simple abstract machine which allows for set-valued variables and we show how to translate programs with array operations to array-free code for this machine. For the purpose of program analysis, the translated program remains faithful to the semantics of array manipulation. based on our implementation in LLVM, we evaluate the approach with respect to its ability to extract useful invariants and the cost in terms of code size.
We propose an automated technique for inferring software contracts from programs that are written in a non-trivial fragment of C, called KernelC, that supports pointer-based structures and heap manipulation. Starting ...
详细信息
ISBN:
(纸本)9783319631394;9783319631387
We propose an automated technique for inferring software contracts from programs that are written in a non-trivial fragment of C, called KernelC, that supports pointer-based structures and heap manipulation. Starting from the semantic definition of KernelC in the K framework, we enrich the symbolic execution facilities recently provided by C with novel capabilities for assertion synthesisthat are based on abstract subsumption. Roughly speaking, we define an abstract symbolic technique that explains the execution of a (modifier) C function by using other (observer) routines in the same program. We implemented our technique in the automated tool KindSpec 2.0, which generates logical axioms that define the precise input/ output behavior of the C routines.
Concolic testing is a popular dynamic validation technique that can be used for both model checking and automatic test case generation. We have recently introduced concolic testing in the context of logicprogramming....
详细信息
ISBN:
(纸本)9783319631394;9783319631387
Concolic testing is a popular dynamic validation technique that can be used for both model checking and automatic test case generation. We have recently introduced concolic testing in the context of logicprogramming. In contrast to previous approaches, the key ingredient in this setting is a technique to generate appropriate run-time goals by considering all possible ways an atom can unify withthe heads of some program clauses. this is called "selective" unification. In this paper, we show that the existing algorithm is not complete and explore different alternatives in order to have a sound and complete algorithm for selective unification.
暂无评论