A Mechanized Proof Environment for the Convenient Computations Proof Method

A mechanized verification environment made up of theories over the deductive mechanized theorem prover PVS is presented, which allows taking advantage of the convenient computations method. This method reduces the conceptual difficulty of proving a given property for all the possible computations of a system by separating two different concerns: (1) proving that special convenient computations satisfy the property, and (2) proving that every computation is related to a convenient one by a relation which preserves the property. The approach is especially appropriate for applications in which the first concern is trivial once the second has been shown, e.g., where the specification itself is that every computation reduces to a convenient one. Two examples are the serializability of transactions in distributed databases, and sequential consistency of distributed shared memories. To reduce the repetition of effort, a clear separation is made between infrastructural theories to be supplied as a proof environment PVS library to users, and the specification and proof of particular examples. The provided infrastructure formally defines the method in its most general way. It also defines a computation model and a reduction relation—the equivalence of computations that differ only in the order of finitely many independent operations. One way to prove that this relation holds between every computation and some convenient one involves the definition of a measure function from computations into a well-founded set. Two possible default measures, which can be applied in many cases, are also defined in the infrastructure, along with useful lemmas that assist in their usage. We show how the proof environment can be used, by a step-by-step explanation of an application example.     

Predicate Synthesis for Correcting Faulty Conjectures: The Proof Planning Paradigm

The synthesis of programs as well as other synthetic tasks often end up with an unprovable, partially false conjecture. A successful subsequent synthesis attempt depends on determining why the conjecture is faulty and how it can be corrected. Hence, it is highly desirable to have an automated means for detecting and correcting faulty conjectures.We introduce a method for patching faulty conjectures. The method is based on abduction and performs its task during an attempt to prove a given conjecture. On input X. G(X), the method builds a definition for a corrective predicate, P(X), such that X. P(X) G(X) is a theorem. The synthesis of a corrective predicate is guided by the constructive principle of formulae as types, relating inference with computation.We take the construction of a corrective predicate as a program transformation task. The method consists of a collection of construction commands. A construction command is a small program that makes use of one or more program editing commands, geared towards building recursive, equational procedures.A synthesised corrective predicate is guaranteed to be correct, turning a faulty conjecture into a theorem. Whether conditional or not, it will be well-defined. If recursive, it will also be terminating.Our method is amenable to mechanisation, but careful search guidance is required for making a productive use of the failure of a proof. A failed proof attempt quickly yields a huge, possibly infinite, deduction tree, giving rise to exponentially many abductive explanations. We suggest that a proof planning approach can structure the task of correcting a formula in such a way as to allow significant automation, while dramatically restricting the search space.     

基于半信任模型的无收据的电子投票

利用同态EIGamal加密、门限EIGamal加密和同指数知识证明等技术,给出了一种无收据的电子投票方案．该方案同时保证了选票的秘密性、广义可验证性和公平性．与以前协议不同的是,所提的方案基于半信任模型,即投票者不必无条件地信任所谓的“可信赖第三方”．文中首先给出了“半信任”的定义,然后证明了所提方案在半信任模型下该方案仍然满足无收据性,从而防止了选举中的“选票买卖”、“强迫选举”等犯罪行为．     

A Graph Abstract Machine Describing Event Structure Composition

Event structures, Game Semantics strategies and Linear Logic proof-nets arise in different domains (concurrency, semantics, proof-theory) but can all be described by means of directed acyclic graphs (dag's). They are all equipped with a specific notion of composition, interaction or normalization.We report on-going work, aiming to investigate the common dynamics which seems to underly these different structures.In this paper we focus on confusion free event structures on one side, and linear strategies [Jean-Yves Girard. Locus solum. Mathematical Structures in Computer Science, 11:301–506, 2001, C. Faggian and F. Maurel. Ludics nets, a game model of concurrent interaction. In Proc. of LICS'05 (Logic in Computer Science). IEEE Computer Society Press, 2005] on the other side. We introduce an abstract machine which is based on (and generalizes) strategies interaction; it processes labelled dag's, and provides a common presentation of the composition at work in these different settings.     

动态存储管理安全验证的Coq实现

随着软件规模和复杂度的日益提升,软件安全的问题变得越来越严峻,同时有越来越多的研究工作集中在高可信软件的开发上 .由于类型系统表达能力的不足,现有的研究不触及底层软件的验证 .由于Hoare逻辑更好的表达能力,采用Hoare逻辑风格的推理,在汇编语言级别,使用Coq形式化与定理证明工具可以实现一个经过安全验证的动态存储管理函数库,这是程序验证技术一次有意义的实践 .实践表明,程序验证技术可以应用到高可信软件的开发上 .     

Design and formal proof of a new optimal image segmentation program with hypermaps

This article presents the design of a new functional 2D image segmentation algorithm by cell merging in a subdivision, its proof of total correctness, and the derivation of an optimal imperative program. The planar subdivisions are modeled by hypermaps. The formal specifications of hypermaps and segmentation are developed in the Calculus of Inductive Constructions. The proofs are assisted by the Coq system. The final program is written in C.     

食品的防霉腐包装设计

食品的卫生与营养是食品包装技术要解决的问题.从食品霉腐的因素、食品包装的要求和食品的防霉腐包装设计3个方面出发,阐述了食品防霉腐包装设计的方法,希能为包装设计者提供参考.     

某发射机调制器的改进设计

本文介绍某型号发射机调制器与高压电源单元在抗打火及维修性方面的改进设计.