Multiway Decision Graphs for Automated Hardware Verification

Traditional ROBDD-based methods of automated verification suffer from the drawback that they require a binary representation of the circuit. To overcome this limitation we propose a broader class of decision graphs, called Multiway Decision Graphs (MDGs), of which ROBDDs are a special case. With MDGs, a data value is represented by a single variable of abstract type, rather than by 32 or 64 boolean variables, and a data operation is represented by an uninterpreted function symbol. MDGs are thus much more compact than ROBDDs, and this greatly increases the range of circuits that can be verified. We give algorithms for MDG manipulation, and for implicit state enumeration using MDGs. We have implemented an MDG package and provide experimental results.     

An Abstract Reachability Approach by Combining HOL Induction and Multiway Decision Graphs

In this paper, we provide a necessary infrastructure to define an abstract state exploration in the HOL theorem prover. Our infrastructure is based on a deep embedding of the Multiway Decision Graphs (MDGs) theory in HOL. MDGs generalize Reduced Ordered Binary Decision Diagrams (ROBDDs) to represent and manipulate a subset of first-order logic formulae. The MDGs embedding is based on the logical formulation of an MDG as Directed Formulae (DF). Then, the MDGs operations are defined and the correctness pro...     

Comparative semantics for flow of control in logic programming without logic

We study semantic issues concerning control flow notions in logic programming languages by exploring a two-stage approach. The first considers solely uninterpreted (or schematic) elementary actions, rather than operations such as unification, substitution generation, or refutation. Accordingly, logic is absent at this first stage. We provide a comparative survey of the semantics of a variety of control flow notions in (uninterpreted) logic programming languages including notions such as don't know versus don't care nondeterminism, the cut operator, and/or parallel logic programming, and the commit operator. In all cases considered, we develop operational and denotational models, and prove their equivalence. A central tool both in the definitions and in the equivalence proofs is Banach's theorem on (the uniqueness of) fixed points of contracting functions on complete metric spaces. The second stage of the approach proceeds by interpreting the elementary actions, first as arbitrary state transformations, and next by suitably instantiating the sets of states and of state transformations (and by articulating the way in which a logic program determines a set of recursive procedure declarations). The paper concentrates on the first stage. For the second stage, only a few hints are included. Furthermore, references to papers which supply details for the languages PROLOG and CONCURRENT PROLOG are provided.     

NP-completeness of small conflict set generation for congruence closure

The efficiency of satisfiability modulo theories (SMT) solvers is dependent on the capability of theory reasoners to provide small conflict sets, i.e. small unsatisfiable subsets from unsatisfiable sets of literals. Decision procedures for uninterpreted symbols (i.e. congruence closure algorithms) date back from the very early days of SMT. Nevertheless, to the best of our knowledge, the complexity of generating smallest conflict sets for sets of literals with uninterpreted symbols and equalities had not yet been determined, although the corresponding decision problem was believed to be NP-complete. We provide here an NP-completeness proof, using a simple reduction from SAT.     

Uniform Closures: Order-Theoretically Reconstructing Logic Program Semantics and Abstract Domain Refinements

The notion of uniform closure operator is introduced, and it is shown how this concept surfaces in two different areas of application of abstract interpretation, notably in semantics design for logic programs and in the theory of abstract domain refinements. In logic programming, uniform closures permit generalization, from an order-theoretic perspective, of the standard hierarchy of declarative semantics. In particular, we show how to reconstruct the model-theoretic characterization of the well-known s-semantics using pure order-theoretic concepts only. As far as the systematic refinement operators on abstract domains are concerned, we show that uniform closures capture precisely the property of a refinement of being invertible, namely of admitting a related operator that simplifies as much as possible a given abstract domain of input for that refinement. Exploiting the same argument used to reconstruct the s-semantics of logic programming, we yield a precise relationship between refinements and their inverse operators: we demonstrate that they form an adjunction with respect to a conveniently modified complete order among abstract domains.     

基于SMV的安全协议模型检验

SMV是一个基于线性时态逻辑的符号化模型检验工具。本文利用SMV对Needham-Schroeder公钥协议的简化版本进行了验证，发现了利用消息重放进行的攻击。     

面向未解释程序的合作验证方法

未解释程序的验证问题通常是不可判定的,但是最近有研究发现,存在一类满足coherence性质的未解释程序,其验证问题是可判定的,并且计算复杂度为PSPACE完全的.在这个结果的基础上,一个针对一般未解释程序验证的基于路径抽象的反例抽象精化（CEGAR）框架被提出,并展现了良好的验证效率.即使如此,对未解释程序的验证工作依然需要多次迭代,特别是利用该方法在针对多个程序验证时,不同的程序之间的验证过程是彼此独立的,存在验证开销巨大的问题.本文发现被验证的程序之间较为相似时,不可行路径的抽象模型可以在不同的程序之间复用.因此,本文提出了一个合作验证的框架,收集在验证过程中不可行路径的抽象模型,并在对新程序进行验证时,用已保存的抽象模型对程序进行精化,提前删减一些已验证的程序路径,从而提高验证效率.此外,本文通过对验证过程中的状态信息进行精简,对现有的基于状态等价的路径抽象方法进行优化,以进一步提升其泛化能力.本文对合作验证的框架以及路径抽象的优化方法进行了实现,并在两个具有代表性的程序集上分别取得了2.70x和1.49x的加速.     

BDD Based Procedures for a Theory of Equality with Uninterpreted Functions

The logic of equality with uninterpreted functions has been proposed for verifying abstract hardware designs. The ability to perform fast satisfiability checking over this logic is imperative for such verification paradigms to be successful. We present symbolic methods for satisfiability checking for this logic. The first procedure is based on restricting analysis to finite instantiations of the variables. The second procedure directly reasons about equality by introducing Boolean-valued indicator variables for equality. Theoretical and experimental evidence shows the superiority of the second approach.     

Distributed reasoning with ontologies and rules in order-sorted logic programming

Integrating ontologies and rules on the Semantic Web enables software agents to interoperate between them; however, this leads to two problems. First, reasoning services in SWRL (a combination of OWL and RuleML) are not decidable. Second, no studies have focused on distributed reasoning services for integrating ontologies and rules in multiple knowledge bases. In order to address these problems, we consider distributed reasoning services for ontologies and rules with decidable and effective computation. In this paper, we describe multiple order-sorted logic programming that transfers rigid properties from knowledge bases. Our order-sorted logic contains types (rigid sorts), non-rigid sorts, and unary predicates that distinctly express essential sorts, non-essential sorts, and non-sortal properties. We formalize the order-sorted Horn-clause calculus for such properties in a single knowledge base. This calculus is extended by embedding rigid-property derivation for multiple knowledge bases, each of which can transfer rigid-property information from other knowledge bases. In order to enable the reasoning to be effective and decidable, we design a query-answering system that combines order-sorted linear resolution and rigid-property resolution as top-down algorithms.     

Verifying a logic-synthesis algorithm and implementation: a casestudy in software verification

We describe the verification of a logic synthesis tool with the Nuprl proof development system. The logic synthesis tool, Pbs, implements the weak division algorithm. Pbs consists of approximately 1000 lines of code implemented in a functional subset of Standard ML. It is a proven and usable implementation and is an integral part of the Bedroc high level synthesis system. The program was verified by embedding the subset of Standard ML in Nuprl and then verifying the correctness of the implementation of Pbs in the Nuprl logic. The proof required approximately 500 theorems. In the process of verifying Pbs we developed a consistent approach for using a proof development system to reason about functional programs. The approach hides implementation details and uses higher order theorems to structure proofs and aid in abstract reasoning. Our approach is quite general, should be applicable to any higher order proof system, and can aid in the future verification of large software implementations     

Agent逻辑和真假子集语义

理性Agent规约的形式框架通常基于信念、愿望和意图逻辑.为了克服现有的信念、愿望和意图逻辑中存在的问题,为非正规模态算子提供一种合适的语义表示.讨论了理性Agent性态的抽象规约中对语义表示的要求以及现有的信念、愿望和意图逻辑中存在的问题.介绍了作者开发的真假子集语义及其在Agent形式化中的应用.他们的框架使意图的有问题的性质无效.并且证明通过对模型的代数结构施加一定的约束,能获得许多希望的性质.最后对真假子集语义进行了分析.这一切表明真假子集语义为非正规模态算子提供了一种合适的语义表示,是对经典的正规模态算子可能世界语义的一个重要发展,是理性Agent性态的逻辑规约的有力工具,可应用于建立新的合适的Agent逻辑系统.     

ON THE SEMANTICS OF STABLE INHERITANCE REASONING

Inheritance reasoners have traditionally been viewed as argument systems, or algorithms that determine reasonable conclusions by constructing acceptable arguments. While the intended meaning of links in such networks is understood, formal semantic accounts are troublesome, as are semantic accounts of the inference process. We adopt a different perspective, suggesting that links be interpreted as conditional sentences with appropriate truth conditions rather than uninterpreted "reasons." The conditional logic CT4D is used for this purpose. Furthermore, we characterize inference in our networks in terms of preferred (or minimal) models. In the process, we identify some key differences between our account of inference and those based on the notion of inferential distance, specifically with respect to the stability of reasoning. Key words: nonmonotonic reasoning, inheritance hierarchies, minimal models, conditional logic.     

一种用于数据挖掘的二进制挖掘算法

提出了一种用于数据挖掘的二进制挖掘算法,适用于大型数据仓库的挖掘与分析,其基本原理是运用二进制逻辑“与”运算,从其多属性值域中抽取关键信息,形成决策规则。此方法原理简单、挖掘效率高、适应性强,对电力系统的数据挖掘具有重要的作用。     

Control and Cross-Domain Mental Computation: Evidence from Language Breakdown

This paper uses the notion of control from programming languages to look at the organization of mental code. Data for the analysis comes principally from language breakdown. The paper first outlines the well known distinction between logic and control in algorithms and argues that the same distinction holds in mental code. Discussion then focuses mainly on control—the management of data flow—and shows that a variety of language disorders affect either the logic component of the mental algorithms for language (e.g., Specific Language Impairment) or the control component (e.g., Williams syndrome and Turner syndrome). A comparative study of the loss of morphology in Williams syndrome and Specific Language Impairment reinforces the logic/control split as an accurate guide to the explanation of linguistic behavior in these disorders. The data, moreover, are not accountable to sheer performance factors, but to the way the disorders disrupt the structure of mental algorithms. The paper closes with a discussion of how control and the management of cross-domain computation fit into recent theories of modular mental architecture and proposals about the explicitness of representations and their availability to working memory.     

A Model Checking-based Method for Verifying Web Application Design

Development of Web Applications (WA) needs new methods, techniques and tools to support an engineered project during all the phases of its life cycle. To ensure the reliability of WA it is important they be validated and verified at early design phase. We use Model Checking techniques to perform automated verification of the UML design of a WA.We propose a mathematical model of a WA partitioning the usual Kripke structure into windows, links, pages and actions. Then we specify properties to be checked in a temporal logic, Computation Tree Logic (CTL). Verification is performed adapting the SMV model checker to our formalism. An implemented system that embeds the SMV verifier automatically parses the XMI output of UML tool and builds the SMV model to be verified with respect to specifications. Results of verification proved the benefits of the method.     

VB过程蓝图

ＶＢ过程蓝图是一种面向Ｖｉｓｕａｌ　Ｂａｓｉｃ语言的程序处理逻辑图表化表示法。这种工程化表示法支持 逻辑和实现两个层次的程序抽象表示,是一种简单实用、容易理解、结构良好的程序设计工具。文中 给出ＶＢ过程蓝图的形式化模型,抽象逻辑结构图的图形表示方法,以及程序设计的基本过程。     

Knowledge-Driven versus Data-Driven Logics

The starting point of this work is the gap between two distinct traditions in information engineering: knowledge representation and data-driven modelling. The first tradition emphasizes logic as a tool for representing beliefs held by an agent. The second tradition claims that the main source of knowledge is made of observed data, and generally does not use logic as a modelling tool. However, the emergence of fuzzy logic has blurred the boundaries between these two traditions by putting forward fuzzy rules as a Janus-faced tool that may represent knowledge, as well as approximate non-linear functions representing data. This paper lays bare logical foundations of data-driven reasoning whereby a set of formulas is understood as a set of observed facts rather than a set of beliefs. Several representation frameworks are considered from this point of view: classical logic, possibility theory, belief functions, epistemic logic, fuzzy rule-based systems. Mamdani's fuzzy rules are recovered as belonging to the data-driven view. In possibility theory a third set-function, different from possibility and necessity plays a key role in the data-driven view, and corresponds to a particular modality in epistemic logic. A bi-modal logic system is presented which handles both beliefs and observations, and for which a completeness theorem is given. Lastly, our results may shed new light in deontic logic and allow for a distinction between explicit and implicit permission that standard deontic modal logics do not often emphasize.     

Formal semantics,modular specification,and symbolic verification of product-line behaviour

Formal techniques for specifying and verifying Software Product Lines (SPL) are actively studied. While the foundations of this domain recently made significant progress with the introduction of Featured Transition Systems (FTSs) and associated algorithms, SPL model checking still faces the well-known state explosion problem. Moreover, there is a need for high-level specification languages usable in industry. We address the state explosion problem by applying the principles of symbolic model checking to FTS-based verification of SPLs. In order to specify properties on specific products only, we extend the temporal logic CTL with feature quantifiers. Next, we show how SPL behaviour can be specified with fSMV, a variant of SMV, the specification language of the industry-strength model checker NuSMV. fSMV is a feature-oriented extension of SMV originally introduced by Plath and Ryan. We prove that fSMV and FTSs are expressively equivalent. Finally, we connect these results to a NuSMV extension we developed for verifying SPLs against CTL properties.     

Logics for Classes of Boolean Monoids

This paper presents the algebraic and Kripke modelsoundness and completeness ofa logic over Boolean monoids. An additional axiom added to thelogic will cause the resulting monoid models to be representable as monoidsof relations. A star operator, interpreted as reflexive, transitiveclosure, is conservatively added to the logic. The star operator isa relative modal operator, i.e., one that is defined in terms ofanother modal operator. A further example, relative possibility,of this type of operator is given. A separate axiom,antilogism, added to the logic causes the Kripke models to support acollection of abstract topological uniformities which become concretewhen the Kripke models are dual to monoids of relations. The machineryfor the star operator is shownto be a recasting of Scott-Montague neighborhood models. An interpretationof the Kripke frames and properties thereof is presented in terms ofcertain CMOS transister networks and some circuit transformation equivalences.The worlds of the Kripke frame are wires and the Kripke relation is a specializedCMOS pass transistor network.