共查询到20条相似文献,搜索用时 31 毫秒
1.
Scott Uk-Jin Lee Gillian Dobbie Jing Sun Lindsay Groves 《Formal Methods in System Design》2010,37(1):1-60
The wide adoption of semistructured data has created a growing need for effective ways to ensure the correctness of its organization.
One effective way to achieve this goal is through formal specification and automated verification. This paper presents a theorem
proving approach towards verifying that a particular design or organization of semistructured data is correct. We formally
specify the semantics of the Object Relationship Attribute data model for Semistructured Data (ORA-SS) modeling notation and
its correctness criteria for semistructured data normalization using the Prototype Verification System (PVS). The result is
that effective verification on semistructured data models and their normalization can be carried out using the PVS theorem
prover. 相似文献
2.
This paper distinguishes several different approaches to organising a weakest pre-condition (WP) calculus in a theorem prover. The implementation of two of these approaches for Java within the LOOP project is described. This involves the WP-infrastructures in the higher order logic of the theorem prover PVS, together with associated rules and strategies for automatically proving JML specifications for Java implementations. The soundness of all WP-rules has been proven on the basis of the underlying Java semantics. These WP-calculi are integrated with the existing Hoare logic, and together form a verification toolkit in PVS: typically one uses Hoare logic rules to break a large verification task up into smaller parts that can be handled automatically by one of the WP-strategies. 相似文献
3.
Ben L. Di Vito 《International Journal on Software Tools for Technology Transfer (STTT)》2000,3(1):20-31
We describe an approach and experimental results in the application of mechanized theorem proving to software requirements
analysis. Serving as the test article was the embedded controller for SAFER, a backpack propulsion system used as a rescue
device by NASA astronauts. SAFER requirements were previously formalized using the prototype verification system (PVS) during
a NASA pilot project in formal methods, details of which appear in a NASA guidebook. This paper focuses on the formulation
and proof of properties for the SAFER requirements model. To test the prospects for deductive requirements analysis, we used
the PVS theorem prover to explore the upper limits of proof automation. A set of property classes was identified, with matching
proof schemes later devised. After developing several PVS proof strategies (essentially prover macros), we obtained fully
automatic proofs of 42 model properties. These results demonstrate how customized prover strategies can be used to automate
moderate-complexity theorem proving for state machine models. 相似文献
4.
Josh Newell Linna Pang David Tremaine Alan Wassyng Mark Lawford 《Journal of Automated Reasoning》2018,60(1):63-84
The trip computers for the two reactor shutdown systems of the Ontario Power Generation (OPG) Darlington Nuclear Power Generating Station are being refurbished due to hardware obsolescence. For one of the systems, the general purpose computer originally used is being replaced by a programmable logic controller (PLC). The trip computer application software has been rewritten using function block diagrams (FBDs), a commonly used PLC programming language defined in the IEC 61131-3 standard. The replacement project’s quality assurance program requires that formal verification be performed to compare the FBDs against a formal software requirements specification written using tabular expressions (TEs). The PVS theorem proving tool is used in formal verification. Custom tools developed for OPG are used to translate TEs and FBDs into PVS code. In this paper, we present a method to rigorously translate the graphical FBD language to a mathematical model in PVS using an abstract syntax to represent the FBD constructs. We use an example from the replacement project to demonstrate the use of the model to translate a FBD module into a PVS specification. We then extend that example to demonstrate the method’s applicability to a Simulink-based design. 相似文献
5.
Uppaal是一种对实时系统模型进行建模和验证的工具,PVS(Prototype Verification System)是开发和分析形式化规格说明的原型证明系统。介绍了Uppaal2PVS翻译器的设计与实现,给出了一种将用Uppaal生成的时间自动机规格说明翻译成PVS文件的方法,从而将模型检查问题转换成了定理证明问题,解决了潜在的状态空间爆炸问题。最后给出了一个实例。 相似文献
6.
TAME: Using PVS strategies for special-purpose theorem proving 总被引:3,自引:0,他引:3
Myla Archer 《Annals of Mathematics and Artificial Intelligence》2000,29(1-4):139-181
7.
Formal specification combined with mechanical verification is a promising approach for achieving the extremely high levels of assurance required of safety-critical digital systems. However, many questions remain regarding their use in practice: Can these techniques scale up to industrial systems, where are they likely to be useful, and how should industry go about incorporating them into practice? This paper discusses a project undertaken to answer some of these questions, the formal verification of the microcode in the AAMP5 microprocessor. This project consisted of formally specifying in the PVS language a Rockwell proprietary microprocessor at both the instruction-set and register-transfer levels and using the PVS theorem prover to show the microcode correctly implemented the instruction-level specification for a representative subset of instructions. Notable aspects of this project include the use of a formal specification language by practicing hardware and software engineers, the integration of traditional inspections with formal specifications, and the use of a mechanical theorem prover to verify a portion of a commercial, pipelined microprocessor that was not explicitly designed for formal verification. 相似文献
8.
V. I. Shelekhov 《Automatic Control and Computer Sciences》2011,45(7):421-427
Deductive verification and synthesis of binary addition programs are carried out on the base of the rules of proving the correctness
for statements of the predicate programming language P. The paper presents key fragments of verification and synthesis of
the programs for the Ripple carry, Carry look-ahead and Ling adders. The correctness conditions of the programs were translated
into the specification language of the PVS verification system. The proof is found to be a tedious procedure as compared with
the ordinary programming. However, for program synthesis, the development of theories and proofs on PVS are easier and faster
than for program verification. 相似文献
9.
10.
Abstractions are important in specifying and proving properties of complex systems. To prove that a given automaton implements an abstract specification automaton, one must first find the correct abstraction relation between the states of the automata, and then show that this relation is preserved by all corresponding action sequences of the two automata. This paper describes tool support based on the PVS theorem prover that can help users accomplish the second task, in other words, in proving a candidate abstraction relation correct. This tool support relies on a clean and uniform technique for defining abstraction properties relating automata that uses library theories for defining abstraction relations and templates for specifying automata and abstraction theorems. The paper then describes how the templates and theories allow development of generic, high level PVS strategies that aid in the mechanization of abstraction proofs. These strategies first set up the standard subgoals for the abstraction proofs and then execute the standard initial proof steps for these subgoals, thus making the process of proving abstraction properties in PVS more automated. With suitable supplementary strategies to implement the “natural” proof steps needed to complete the proofs of any of the standard subgoals remaining to be proved, the abstraction proof strategies can form part of a set of mechanized proof steps that can be used interactively to translate high level proof sketches into PVS proofs. Using timed I/O automata examples taken from the literature, this paper illustrates use of the templates, theories, and strategies described to specify and prove two types of abstraction property: refinement and forward simulation. 相似文献
11.
Faced with the challenge of designing correct circuits, the research community has been applying alternative verification methodologies istead of only traditional methods like ad hoc simulation. The best choice among alternatives like tautology checking, symbolic simulation, and theorem proving depends very theorem proving is best applicable, one is faced with the problem of choosing a formalism. This article compares the proof assistant HOL and the theorem-prover Boyer-Moore based on a practical experience with both systems in order to verify a combinatorial and parameterized hardware module from the CATHEDRAL II Silicon Compiler library. Although the comparison is based on a specific application, the general features, advantages, and drawbacks of both systems are discussed, with consideration given to the verification of other kinds of circuits. 相似文献
12.
为采用定理证明的方法对并发及交互式系统进行验证,研究了有穷论域下有穷时间一阶投影时序逻辑(projection temporal logic,简称PTL)的一个完备公理系统.在介绍PTL的语法、语义并给出公理系统后,提出了PTL公式的正则形(normal form,简称NF)和正则图(normal form graph,简称NFG).基于NF给出了NFG的构造算法,并利用NFG可描述公式模型的性质证明PTL公式的可满足性判定定理和公理系统的完备性.最后,结合实例展示了PTL及其公理系统在系统验证中的应用.结果表明,基于PTL的定理证明方法可方便用于并发系统的建模与验证. 相似文献
13.
Sven Beyer Christian Jacobi Daniel Kröning Dirk Leinenbach Wolfgang J. Paul 《International Journal on Software Tools for Technology Transfer (STTT)》2006,8(4-5):411-430
In the verified architecture microprocessor (VAMP) project we have designed, functionally verified, and synthesized a processor
with full DLX instruction set, delayed branch, Tomasulo scheduler, maskable nested precise interrupts, pipelined fully IEEE
compatible dual precision floating point unit with variable latency, and separate instruction and data caches. The verification
has been carried out in the theorem proving system PVS. The processor has been implemented on a Xilinx FPGA.
A shorter version of this article with the title “Instantiating uninterpreted functional units and memory system: functional
verification of the VAMP” appeared in [8]. The work reported here was done while all the authors were with Saarland University. 相似文献
14.
In this paper we report on the results of a sophisticated and substantial use of PVS to establish a recent result in operational semantics. The result we establish is a context lemma for operational equivalence for very wide class of programming languages, known as the CIU theorem. The proof uses the annotated holes technique to represent contexts and compute with them. Thus this paper demonstrates that that it is possible to use PVS as a tool in the development of modern operational techniques, and a productive tool at that. The process of formalizing the CIU theorem revealed several gaps in published proof. The proof of the CIU theorem in PVS took approximately six months to develop. The actual machine checked proof involves the proving of around one thousand facts, and takes PVS slightly less than three hours of CPU time running on a Linux machine configured with 2 GBytes of main memory and four 550 MHz Xeon PIII processors. 相似文献
15.
In presenting specifications and specification properties to a theorem prover, there is a tension between convenience for the user and convenience for the theorem prover. A choice of specification formulation that is most natural to a user may not be the ideal formulation for reasoning about that specification in a theorem prover. However, when the theorem prover is being integrated into a system development framework, a desirable goal of the integration is to make use of the theorem prover as easy as possible for the user. In such a context, it is possible to have the best of both worlds: specifications that are natural for a system developer to write in the language of the development framework, and representations of these specifications that are well matched to the reasoning techniques provided in the prover. In a tactic-based prover, these reasoning techniques include the use of tactics (or strategies) that can rely on certain structural elements in the theorem prover's representation of specifications. This paper illustrates how translation techniques used in integrating PVS into the TIOA (Timed Input/Output Automata) system development framework produce PVS specifications structured to support development of PVS strategies that implement reasoning steps appropriate for proving TIOA specification properties. 相似文献
16.
This paper presents a formal executable semantics of object-oriented models. We made it possible to conduct both simulation
and theorem proving on the semantics by implementing it within the expressive intersection of the functional programming language
ML and the theorem prover HOL. In this paper, we present the definition and implementation of the semantics. We also present
a prototype verification tool ObjectLogic which supports simulation and theorem proving on the semantics. As a case study,
we show the verification of a practical firewall system. 相似文献
17.
We present a formal verification method for concurrent systems. The technique is to show a correspondence between state machines representing an implementation and specification behavior. The correspondence is called asimulation relation, and is particularly well suited for theorem provers. Since the method does not rely on enumerating all the states, it can be applied to systems with an infinite or unknown number of states. The method is illustrated by proving the correctness of a particularly subtle example that is likely to be of increasing importance: a directory based multiprocessor cache protocol. The proof is carried out using the HOL (higher-order logic) theorem prover. 相似文献
18.
操作系统安全验证形式化分析框架 总被引:1,自引:0,他引:1
结合当前形式化验证方法的特点和操作系统安全模型情况,本文提出了这些方法在操作系统安全分析中的应用。结合传统定理证明方法的优势,将模型检验方法纳入形式化安全分析体系当中,并分别提出了在安全分析中的应用情况。将用定理证明用于从模型到规则的分析,模型检验从实现中抽取模型,用于从实现到规则的分析。 相似文献
19.
定理证明是目前主流的形式化验证方法,拥有强大的抽象和逻辑表达能力,且不存在状态空间爆炸问题,可用于有穷和无穷状态系统,但其不能完全自动化,并且要求用户掌握较强的数学知识.含索引式的命题投影时序逻辑(PPTL)是一种具有完全正则表达能力,并且包含LTL的时序逻辑,具有较强的建模和性质描述能力.目前,一个可靠完备的含索引式的PPTL公理系统已被构建,然而基于该公理系统的定理证明尚未得到良好工具的支持,存在证明自动化程度较低以及证明冗长易错的问题.鉴于此,首先设计了支持索引式的PPTL定理证明器的实现框架,包括公理系统的形式化与交互式定理证明;然后,在Coq中形式化定义了含索引式的PPTL公式、公理与推理规则,完成了框架中公理系统的实现;最后,通过两个实例的交互式证明验证了该定理证明器的可用性. 相似文献
20.
超长整数的运算是现代密码系统的应用基础,运算的正确性关系到密码系统的应用价值。为了验证超长整数算法的设计与需求目标之间的一致性,利用原型验证工具PVS对算法的正确性进行了证明。在介绍了超长整数的加法和减法算法并分析了其设计思想之后,给出了超长整数及其算法的形式规范,通过把算法需要满足的性质描述为定理,将算法的一致性验证问题转化为逻辑定理证明的问题,在PVS定理证明器上完成了相关定理的证明,从而表明这些算法是满足设计需求的。 相似文献