基于分离逻辑的并行程序性质验证方法

随着多核多线程并行执行方式的普及,并行程序形式化验证的需求日显突出.并行程序验证中执行流程的不确定性使验证的内容与目标的关系难以确定,且从并行程序直接进行性质验证会导致验证规模大.为此,提出一种基于分离逻辑的新的验证方法.该方法根据分离逻辑的程序语义描述兼有解释语义和公理语义的特点,从验证的性质出发,把要验证的性质式转换成并行语句序列的逻辑组合式,并进行整理和化简;然后,利用分离逻辑公理系统对语句序列进行验证,用验证了的断言集来求出性质的真值.实例进一步说明,此方法更有效,同时也简化了验证的规模.     

Logic Programs with Ordered Disjunction

Logic programs with ordered disjunction (LPODs) contain a new connective which allows representing alternative, ranked options for problem solutions in the heads of rules: A × B intuitively means that if possible A , but if A is not possible, then at least B . The semantics of logic programs with ordered disjunction is based on a preference relation on answer sets. We show how LPODs can be implemented using answer set solvers for normal programs. The implementation is based on a generator, which produces candidate answer sets and a tester which checks whether a given candidate is maximally preferred and produces a better candidate if it is not. We also discuss the complexity of reasoning tasks based on LPODs and possible applications.     

VST-Floyd: A Separation Logic Tool to Verify Correctness of C Programs

The Verified Software Toolchain builds foundational machine-checked proofs of the functional correctness of C programs. Its program logic, Verifiable C, is a shallowly embedded higher-order separation Hoare logic which is proved sound in Coq with respect to the operational semantics of CompCert Clight. This paper introduces VST-Floyd, a verification assistant which offers a set of semiautomatic tactics helping users build functional correctness proofs for C programs using Verifiable C.     

Updating Epistemic Logic Programs

We consider the problem of updating non-monotonic knowledgebases represented by epistemic logic programs where disjunctiveinformation and notions of knowledge and belief can be explicitlyexpressed. We propose a formulation for epistemic logic programupdate based on a principle called minimal change and maximalcoherence. The central feature of our approach is that duringan update or a sequence of updates, contradictory informationis removed on a basis of minimal change under the semanticsof epistemic logic programs and then coherent information ismaximally retained in the update result. Through various updatescenarios, we show that our approach provides both semanticand syntactic characterizations for an update problem. We alsoinvestigate essential semantic properties of epistemic logicprogram update.     

Strict completion of Logic Programs

The paper presents a new approach to the problem of completeness of the SLDNF-resolution. We propose a different reference theory that we call strict completion. This new concept of completion (comp^*(P)) is based on a program transformation that given any program transforms it into a strict one (with the same computational behaviour) and the usual notion of program completion. We consider it a reasonable reference theory to discuss program semantics and completeness results. The standard 2-valued logic is used. The new comp^*(P) is always consistent and the completeness of all allowed programs and goals w.r.t. comp^*(P) is proved.     

逻辑程序的事实维护

事实是逻辑程序的重要组成部分,事实维护影响着整个逻辑程序的一致性和完整性,并能够促进和完善规则维护。论文在分析了人工进行维护操作的弊端后,对事实维护中可能出现的情况进行分类分析,提出了事实维护系统的框架,重点描述了预警检测子系统所扮演的核心作用。     

Bounded Nondeterminism of Logic Programs

We introduce the notion of bounded nondeterminism for logic programs and queries. A program and a query have bounded nondeterminism if there are finitely many refutations for them via any selection rule. We offer a declarative characterization of the class of programs and queries that have bounded nondeterminism by defining bounded programs and queries. The characterization is provided in terms of Herbrand interpretations and level mappings, in the style of existing characterizations of universal termination. A direct application of the theoretical framework is concerned with the automatic generation of a terminating control. We present a transformational approach that given a bounded program and a bounded query yields a terminating program and query with the same set of refutations. Concerning the issue of automating the approach, by means of an example we sketch how an automatic method for proving left termination can be adapted to the purpose of inferring boundedness. Such an adaption reveals that the method does not scale up to medium/large sized programs due to scarce modularity of the required proof obligations. We provide then a modular refinement of boundedness for the significant class of well-moded programs and queries.     

Weak Updates and Separation Logic

Separation logic provides a simple but powerful technique for reasoning about low-level imperative programs that use shared data structures. Unfortunately, separation logic supports only “strong updates,” in which mutation to a heap location is safe only if a unique reference is owned. This limits the applicability of separation logic when reasoning about the interaction between many high-level languages (e.g., ML, Java, C#) and low-level ones since the high-level languages do not support strong updates. Instead, they adopt the discipline of “weak updates,” in which there is a global “heap type” to enforce the invariant of type-preserving heap updates. We present SL ^w , a logic that extends separation logic with reference types and elegantly reasons about the interaction between strong and weak updates. We describe a semantic framework for reference types, which is used to prove the soundness of SL ^w . Finally, we show how to extend SL ^w with concurrency.     

描述逻辑程序系统的设计与实现

Eiter等人为语义网提出的回答集程序和描述逻辑相结合的描述逻辑程序,获得了本体上的非单调表达和推理能力。王以松等人证明了描述逻辑程序的完备化和环公式可以精确刻画描述逻辑程序的回答集。在此基础上,进一步证明了若完备化公式的模型不是回答集则一定存在终止环公式反例,它们是多项式时间可计算的。设计并实现了借助SAT求解器MiniSAT以及描述逻辑推理机RacerPro计算描述逻辑强回答集的原型DLP_SAT。实验结果表明,该原型能有效地计算一些熟知的描述逻辑程序的强回答集。     

带函数析取逻辑程序的无基集及其应用

基于回答集（也称稳定模型）语义的带函数析取逻辑程序是一种重要的知识表示和推理方法。由于判定一个析取逻辑程序是否有回答集是困难的（Σ2完全的）,目前还没有有效的方法来计算带函数析取逻辑程序的回答集,主要原因之一是检查一个集合是否是回答集是coNP完全的。提出了带函数析取逻辑程序无基集（unfounded sets）的概念,发现了空无基集（unfounded-free sets）与稳定模型之间的一一对应关系,在此基础上,证明了一个逻辑程序的模型是该程序的稳定模型当且仅当它们对应的一个命题公式是不可满足的,从而在理论上为计算带函数析取逻辑程序的回答集提供了一种有效的途径。     

时序逻辑程序的模型检测

时序逻辑程序的形式化验证对提高程序的正确性具有重要意义。以投影时序逻辑的可执行子集、框架投影时序逻辑语言Framed Tempura为研究对象,使用命题投影时序逻辑描述Framed Tempura程序的性质,将程序p和性质Ф统一表示在投影时序逻辑中,模型检测需要判定p→Ф是否有效,可转化为判定p∧Ф是否不可满足,这可以通过构造p∧Ф的正则图加以解决。最后,给出了Framed Tempura程序的模型检测实例。     

Unfolding-based Improvements on Fuzzy Logic Programs

Unfolding is a semantics-preserving program transformation technique that consists in the expansion of subexpressions of a program using their own definitions. In this paper we define two unfolding-based transformation rules that extend the classical definition of the unfolding rule (for pure logic programs) to a fuzzy logic setting. We use a fuzzy variant of Prolog where each program clause can be interpreted under a different (fuzzy) logic. We adapt the concept of a computation rule, a mapping that selects the subexpression of a goal involved in a computation step, and we prove the independence of the computation rule. We also define a basic transformation system and we demonstrate its strong correctness, that is, original and transformed programs compute the same fuzzy computed answers. Finally, we prove that our transformation rules always produce an improvement in the efficiency of the residual program, by reducing the length of successful Fuzzy SLD-derivations.     

一种面向非干扰的线程程序逻辑

目前,针对线程信息流的验证研究主要着重于时间信道.然而,由于线程程序中线程控制原语存在函数副作用,对此类原语的不恰当调用亦可引起非法信息流,有意或无意地破坏程序的非干扰属性.因此,提出以验证线程程序信息流为目的依赖逻辑,其可表达线程程序的数据流、控制流以及线程控制函数的副作用,推理程序变量和线程标识符之间的依赖关系,进而判定是否存在高机密性变量对低机密性变量的干扰.     

Semantic Forcing in Disjunctive Logic Programs

We propose a semantics for disjunctive logic programs, based on the single notion of forcing. We show that the semantics properly extends, in a natural way, previous approaches. A fixpoint characterization is also provided. We also take a closer look at the relationship between disjunctive logic programs and disjunctive-free logic programs. We present certain criteria under which a disjunctive program is semantically equivalent with its disjunctive-free (shifted) version.