谓词抽象技术研究

随着软、硬件系统规模和功能的不断扩充,状态空间爆炸问题严重影响了模型检验的进一步发展与应用,成为验证大规模系统的瓶颈.谓词抽象是解决状态空间爆炸的最有效方法之一,近年来得到迅速发展.介绍了谓词抽象的基本算法并比较了不同的求解支持工具;重点分析了反例指导的抽象求精和基于插值的抽象求精原理;分析了产生新谓词的各种方法的优、缺点;最后指出了谓词抽象技术进一步发展所面临的挑战和发展方向.     

基于逻辑一致性判定的广义不透明谓词检测方法

不透明谓词是一类轻量级的代码混淆方法,能以单向的执行复杂度对抗程序的逆向分析。广义不透明谓词扩展狭义不透明谓词的值恒定属性至逻辑恒定属性,已经应用于部分恶意代码中以提升抗查杀能力。为消除不透明谓词对程序恶意性判定的影响,以广义不透明谓词后趋依赖的属性为依据,结合逻辑恒定判定,提出了基于逻辑一致性的广义不透明谓词检测方法。通过静态分析提取谓词前置条件约束、后趋逻辑约束和谓词判定表达式,以相交基本块搜寻初筛谓词,并依据约束求解方法判定广义不透明谓词。构造原型系统并进行测试,结果表明该方法能精准高效地检测出恶意代码中的不透明谓词。     

谓词抽象技术中循环反例的解决方法研究

为了解决谓词抽象技术面临的程序中循环体的每次迭代都至少需要一个谓词来实现的难题,提出了一个两阶段的不完全判定过程,用来对一个包含循环的反例进行可行性模拟.通过给出的循环探测算法来从抽象模型中提取出包含循环的反例,并用循环迭代的数量作为参数来确定模拟实例.实验结果表明,该方法在典型的缓冲溢出实例中的表现优于传统的抽象求精方法.     

RTL数据通路模拟矢量自动生成方法研究与实现

针对已有的RTL数据通路模拟矢量自动生成方法的不足,提出一种利用约束逻辑编辑(CLP)自动生成数据通路模拟矢量的新方法．该方法首先对给定的Verilog RTL描述采用程序切片进行设计化简,然后对化简后的结果基于位向量算术原理生成CLP约束,并利用CLP求解器GProlog进行约束求解,最终生成满足输出要求的模拟矢量．该方法约束求解速度快,生成的约束是统一的,得到的模拟矢量较完备,能满足模拟验证的要求．实验结果表明,文中方法是一种高效的RTL数据通路模拟矢量自动生成方法．     

针对Java语言中间形式的谓词抽象算法

谓词抽象是解决软件模型检查中状态空间爆炸的最有效方法之一,针对Java语言面向对象的特性,描述了一种对Java程序语言中间形式的谓词抽象算法,该算法将Java程序抽象成为布尔程序,抽象过程中处理的Java数据结构包括:赋值语句、条件语句、类对象引用、成员方法和方法调用等.用一个Java程序实例说明了该算法的抽象过程和结果.     

基于K-模拟的抽象

尽管近年来模型检测取得了很大的进步,但是对于大系统的验证能力依然有限。在众多的状态减少和压缩技术中,抽象技术是最有效的方法之一。本文给出了基于K-模拟的抽象的高效算法,并证明了在线性时序逻辑框架下抽象的可靠性和完备性。     

基于谓词逻辑的设计模式描述方法

设计模式描述了面向对象软件设计过程中不断重复发生的问题以及这些问题的解决方案,强调系统的复用性,帮助人们做出有利于系统复用的选择,因此设计模式也可看成是对软件开发者的分析与设计知识的记录、提炼和表示,谓词逻辑是一种形式语言系统,具有精确、无二义性以及容易为计算机理解和操作等特点.采用了谓词逻辑来形式化描述设计模式,以实现对设计模式精确的形式化描述,并给出了具体的实例分析.     

RTL级模拟矢量自动生成设计化简方法研究

提出一种Verilog程序切片算法,给出了该算法的正确性证明的理论框架;并利用提出的Verilog程序切片算法对Verilog RTL级设计进行化简,实现模拟矢量自动生成状态化简目的,实验结果表明：该算法对状态化简效果非常明显,可以有效地解决状态空间爆炸问题。     

基于Verilog的顺序状态逻辑FSM的设计与仿真

以顺序状态逻辑有限状态机的设计为例,简要介绍了用Verilog语言进行集成电路设计的一般过程,并在ModelSim和DC环境下成功地进行了仿真和综合。     

基于抽象和搜索空间划分的安全性判定方法

为满足访问控制策略安全性快速判定的要求,提出一种基于谓词抽象和验证空间划分的访问控制策略状态空间约减方法,将在访问控制策略原始状态机模型上的安全性分析工作转移到包含较少状态的抽象模型上,并进一步划分抽象模型的验证空间,以提高效率.理论分析和实验数据均表明,其安全性分析所需的时间和空间都得到有效约减.与传统方法相比,它具有速度更快、自动化程度更高等优点.     

SC-PROLOG解释系统中的约束逻辑程序设计方法

约束逻辑程序设计（ＣＬＰ）方法是提高ＰＲＯＬＯＧ语言效率的一种崭新方法，本文针对ＳＣ┐ＰＲＯＬＯＧ解释系统的实现介绍其相应设计思想，从域变量含义入手，提出了域及约束的存储方法以及约束机制的实现算法，是对逻辑设计方法研究的一点体会     

Reasoning about Solids Using Constraint Logic Programming

The embedding of constraint satisfaction on the domain of discourse into a rule-based programming paradigm like logic programming provides a powerful reasoning tool. We present an application in spatial reasoning that uses this combination to produce a clear, concise, yet very expressive system through its ability to manipulate partial information. Three-dimensional solid objects in constructive solid geometry representation are manipulated, and their spatial relationship with one another, points, or regions is reasoned about. The language used to develop this application is QUAD-CLP(), an experimental constraint logic programming language of our own design, which is equipped with a solver for quadratic and linear arithmetic constraints over the reals.     

Using Constraint Logic Programming to Analyze theChronology in ``A Rose for Emily''''

William Faulkner's non-chronological story tellingstyle has long been a challenge to critics and apuzzle to beginning literature students. ``A Rose forEmily,' one of Faulkner's most frequently anthologizedstories, exemplifies the complexity of Faulkner'streatment of time. In this paper, we apply aconstraint-based problem solving method to an analysisof the chronology of ``A Rose for Emily.' Constraintlogic programming is a declarative programminglanguage paradigm that solves problems by enforcingconstraints among variables. CLP's ability to sortnumeric variables that do not yet have definite valuesmakes it possible to sort the events of ``A Rose forEmily' with only fragmented and relative timeinformation. In attempting to sort the events of thestory, we find an inconsistency in the temporalreferences scattered throughout the narrative. Afterremoving this inconsistency, we are able to compareour chronology with earlier ones and discuss thethematic relevance of Faulkner's nonlinear plots.     

一种可扩展型CLP系统的统一建模方法

约束推理是人工智能中主要组成部分之一,可以解决实际优化调度和规划过程中的约束求解问题。这里在解释了约束逻辑程序设计的原理和过程基础上,打破封闭式约束逻辑程序设计系统,从软件工程上采用统一建模语言,提出一种新的开放的可扩展型约束逻辑程序设计结构系统。为实现可扩展的约束推理搜索系统,引进UML建模语言中用例图、类图和协作图。在建模基础上详细说明了可扩展约束逻辑程序设计中数学模型,搜索引擎和搜索驱动三者间的关系以及它们内部的工作内容。最后在描述系统结构后,提出了可扩展的内容。根据扩展因素,外界为满足更多的需要可扩展本系统的约束过滤器。     

模型检验中抽象技术研究综述

在模型检验中,抽象技术是解决状态空间爆炸问题的有效方法之一。论文描述了模型检验对抽象模型的基本要求,给出了抽象模型的定义及其评价指标,对抽象技术和自动化的抽象精化技术的主要方法及其研究进展作了比较深入、全面的综述,并讨论了抽象技术今后的发展方向。     

Constraint Logic Programming and Integer Programming approaches and their collaboration in solving an assignment scheduling problem

Generalised Assignment Problems (GAP), traditionally solved by Integer Programming techniques, are addressed in the light of current Constraint Programming methods. A scheduling application from manufacturing, based on a modified GAP, is used to examine the performance of each technique under a variety of problem characteristics. Experimental evidence showed that, for a set of assignment problems, Constraint Logic Programming (CLP) performed consistently better than Integer Programming (IP). Analysis of the CLP and IP processes identified ways in which the search was effective. The insight gained from the analysis led to an Integer Programming approach with significantly improved performance. Finally, the issue of collaboration between the two contrasting approaches is examined with respect to ways in which the solvers can be combined in an effective manner.     

一个命题投影时序逻辑符号模型检测器

现有模型检测工具的形式化规范语言,如计算树逻辑(computation tree logic,简称CTL)和线性时序逻辑(linear temporal logic,简称LTL)等的描述能力不足,无法验证ω正则性质.提出了一个命题投影时序逻辑(propositional projection temporal logic,简称PPTL)符号模型检测工具——PLSMC(PPTL symbolic model checker)的设计与实现过程.该工具基于著名的符号模型检测系统NuSMV,实现了PPTL的符号模型检测算法.PLSMC的规范语言PPTL具有完全正则表达能力,这使得定性性质和定量性质均可被验证.此外,PLSMC可以有效地缓解模型检测工具中容易发生的状态空间爆炸问题.最后,利用PLSMC对铁路公路交叉道口护栏控制系统的安全性质和周期性性质进行验证.实验结果表明,PPTL符号模型检测工具扩充了NuSMV系统的验证能力,使得时间敏感、并发性和周期性等实时性质可以被描述和验证.