基于QBF的循环不变式构造技术

构造循环不变式是程序验证的核心问题之一。主流的循环不变式构造方法通常假设程序中的变量在无限数域上取值,然而程序执行过程中变量都是用有限长度的位向量来表示,无限数域上的循环不变式在有限数域的程序中可能不再是不变式,反之亦然。针对这一问题,本文给出一种基于QBF求解的构造有限数域上循环不变式的方法。该方法可用于构造类型丰富的不变式,包括线性(或多项式)等式(或不等式)不变式,支持加、减、乘、除、移位、位操作等,允许不变式中出现量词。本文也例证了该方法在程序终止性证明、循环上界分析、程序正确性证明等方面的应用价值。     

基于数据分类的循环不变式自动生成

生成循环不变式是实现程序验证的关键步骤,但人工撰写循环不变式不仅步骤繁琐且容易出错。为此,提出一种基于数据分类的循环不变式生成方法,可直接为C程序的循环语句自动生成循环不变式。该方法生成循环程序的后置条件,并构造其Hoare三元组,通过收集循环程序执行过程中产生的测试数据,并根据其是否满足循环不变式的三个条件进行分类,从而生成循环不变式。所提出的方法在31个基准测试程序上,与目前比较先进的循环不变式生成方法进行比较分析。实验结果表明,所提出的方法不仅能够为C程序自动生成可验证的循环不变式,而且能够为最多的基准测试程序生成有效的循环不变式。     

利用基因表达式编程自动生成循环不变式

描述了利用基因表达式编程自动生成循环不变式的方法。该方法的基本思想是在每一次循环条件变化时记录下程序变量的值,产生相应的跟踪表,然后从跟踪表中获得程序变量之间的函数依赖关系,这种变量之间的依赖关系构成了循环不变式的主要部分。程序变量之间的函数依赖关系的获得是利用基因表达式编程对跟踪表中数据执行符号回归得到。利用VC＋＋实现了基因表达式编程的函数挖掘,并通过一个实例说明了该方法的有效性。     

常用循环摘要的自动生成方法及其应用

采用形式化方法证明软件的正确性是保障软件可靠性的有效方法,而对循环语句的分析与验证是形式化证明中的关键,对循环语句的处理一直是程序分析与验证中的一个难点问题.本文提出使用循环语句修改的内存和这些内存中存放的新值来描述循环语句的执行效果,并将该执行效果定义为循环摘要.同时,本文提出了一种自动生成循环摘要的方法,可以为操作常用数据结构的循环自动生成循环摘要,包含嵌套循环.此外,基于循环摘要,我们可以自动生成循环语句的规约,包括循环不变式、循环的前置条件以及循环的后置条件.我们已经实现了自动生成循环摘要以及循环规约的方法,并将它们集成到验证工具Accumulator中,实验表明,我们的方法可以有效地生成循环摘要,并生成多种类型的规约,从而辅助软件程序的形式化证明,提高验证的自动化程度和效率,减轻验证人员的负担.     

基于DISCOVERER的Petri网不变式自动生成*

在Petri网的验证中,代数不变式起着非常重要的作用。将Petri网建模为半代数变迁系统,提出了自动生成不变式的算法,该不变式有助于更好地分析Petri网可达空间。算法首先将Petri网的不变式假定为一个含参数系统,然后通过求解半代数系统来求解不变式中的参数;最后,基于DISCOVERER和QEPCAD等Maple软件包实现了该算法,并通过实例说明了算法的有效性。     

利用循环不变式理解和开发程序

本文论述了循环不变式及其开发技术和程序设计的联系，并通过实例说明循环不变式在理解和开发程序中的巨大作用。     

基于不变式生成的循环停机性验证

循环的停机性验证是程序验证中的一个难点。程序不变式用来描述程序变量的取值关系,其中线性不变式可以帮助描述程序变量间的线性关系,循环不变式能够有效刻画循环中的变量关系。本文基于线性不变式和多项式循环不变式的生成,将循环的停机性验证转化为求解一个最优化问题,给出了一个实用的程序停机性验证框架。基于该框架可以自动地验证程序的停机性,并给出循环的复杂度上界。实验结果说明了该方法的实用性。     

一种自适应的循环不变式生成方法

基于条件赋值转换和自适应模板生成技术,提出一种自适应的的循环不变式生成方法.该方法在生成过程中综合考虑函数规范、循环本身、循环后操作等信息,有针对性地发现潜在的循环不变式,并在Frama-C平台上实现一个插件looplnv.实验结果表明,与invGen和gin-pink工具相比,loopInv的应用更加有效,可较好地完成多数程序的验证过程.     

含有析取语义循环的不变式生成改进方法

抽象解释为程序不变式的自动化生成提供了通用的框架,但是该框架下的大多数已有数值抽象域只能表达几何上是凸的约束集.因此,对于包含(所对应的约束集是非凸的)析取语义的特殊程序结构,采用传统数值抽象域会导致分析结果不精确.针对显式和隐式含有析取语义的循环结构,提出了基于循环分解和归纳推理的不变式生成改进方法,缓解了抽象解释分析中出现的语义损失问题.实验结果表明:相比已有方法,该方法能为这种包含析取语义的循环结构生成更加精确的不变式,并且有益于一些安全性质的推理.     

循环不变式开发技术研究

高可靠性软件是当今软件开发的热点问题。确保算法程序逻辑结构正确最理想的途径是算法程序的形式化推导和证明,而循环不变式是算法程序形式推导和证明的关键。循环不变式的开发一直是算法程序设计领域中最具挑战性、最富有创造性、也是最困难的问题之一。本文研究了众多现有循环不变式开发方法中较为典型的几种方法,指出了它们的基本原理、技术难点、特点及效果,旨在探寻循环不变式本质特征,从而为研究更简单、有效的生成方法提出指导。     

多元约束混合搜索算法研究

解空间搜索是约束求解的关键环节. 目前较为常用的搜索算法一般是基于二元约束或单一搜索策略设计的. 本文设计了六个基于多元约束的混合搜索算法(BM_GASBJ, BM_GBJ, BM_CBJ, FC_GASBJ, FC_GBJ, FC_CBJ), 它们分别混合同一类搜索策略中不同算法或不同类搜索策略; 分析并给出了不同混合算法的性能差异. 系统测试结果表明混合搜索算法明显提高了解搜索效率和约束求解系统的性能.     

字符串分析研究进展

随着软件应用范围的不断扩大,尤其是数据库软件和Web软件的广泛应用,字符串变量在软件程序中扮演的角色日益重要与此同时,针对字符串变量的程序分析技术——字符串分析,也取得了长足的发展,并在软件工程中的很多领域中得到了成功的应用.字符串分析的基本应用模式是首先使用字符串值分析获得字符串变量的所有可能取值,然后使用字符串约束求解判断这些变量的取值是否满足一定约束,从而对程序进行正确性验证.为了使得字符串分析能够应用在安全分析和软件维护应用中,研究人员对字符串分析进行了扩展,进一步分析字符串变量的数据来源.综述了字符串分析技术的研究进展,提出了字符串分析的问题构型,介绍了这一领域现在的主要研究内容:字符串值分析、字符串约束求解、字符串数据来源分析以及字符串分析在软件工程中的应用.     

A Shape Graph Logic and A Shape System

Analysis and verification of pointer programs are still difficult problems so far. This paper uses a shape graph logic and a shape system to solve these problems in two stages. First, shape graphs at every program point are constructed using an analysis tool. Then, they are used to support the verification of other properties （e.g., orderedness）. Our prototype supports automatic verification of programs manipulating complex data structures such as splay trees, treaps, AVL trees and AA trees, etc. The proposed shape graph logic, as an extension to Hoare logic, uses shape graphs directly as assertions. It can be used in the analysis and verification of programs manipulating mutable data structures. The benefit using shape graphs as assertions is that it is convenient for acquiring the relations between pointers in the verification stage. The proposed shape system requires programmers to provide lightweight shape declarations in recursive structure type declarations. It can help rule out programs that construct shapes deviating from what programmers expect （reflected in shape declarations） in the analysis stage. As a benefit, programmers need not provide specifications （e.g., pre-/post-conditions, loop invariants） about pointers. Moreover, we present a method doing verification in the second stage using traditional Hoare logic rules directly by eliminating aliasing with the aid of shape graphs. Thus, verification conditions could be discharged by general theorem provers.     

基于迁移系统分析的线性混成系统安全验证

混成自动机行为中既包含离散行为又包含连续行为,非常复杂。其安全性验证问题难以解决,即使是线性混成自动机,它的可达性问题也被证明是不可判定的。现有工具大都使用多面体计算来计算线性混成自动机的可达状态空间集,复杂度高,可处理问题规模非常有限。为了避免这类问题,实现了一种新的工具。该工具将线性混成自动机表达为等价的迁移系统,并利用迁移系统上不变式生成相关工作对混成自动机进行验证。实验数据表明,方法有效可行,工具具有良好的性能。     

一种双向求解平行结构类问题的方法

平行结构类问题是一类适于分布式求解的人工智能问题．已有的大多数求解方法均采用预期或目标来指导自底向上的问题求解．但这些预期或目标是以局部问题求解状态为基础的,指导性较弱．尽管有的方法（如改进的ＤＶＭＴ结构）允许高层了解,但未给出明确的求解算法．本文提出一种双向求解平行结构类问题的方法,首先根据全局问题求解状态生成预期,指导自底向上的求解,然后根据新产生的假设来验证和修改预期,并用新的预期重新指导求解．该方法不仅提高了预期的指导性,而且使问题求解更为灵活．     

A Constructive Approach to Solving Geometric Constraint Systems

This paper proposes a constructive approach to solving geometric constraint systems.The approach incorporates graph-based and rule-based approaches, and achieves interactive speed.The paper presents a graph representation of geometric conStraint syStems, and discusses in detailthe algorithm of geometric reasoning based on poinl-cluster reduction. An example is made forillustration.     

分布式问题求解中的妥协策略

基于多agent系统的分布式约束满足(CSP)问题的求解进程依赖于agent间的有效交互。该文针对着色问题(GCP)的分布式求解,提出了agent妥协的概念。通过妥协,两个相邻agent改变了各自原有的局部目标,实现了相邻约束的满足。模拟实验表明,妥协策略有助于提高分布式GCP问题的求解性能。该文还讨论了不同的妥协实现方式对性能的影响。