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

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

基于循环不变式的循环结构教学研究

以梳理程序设计基础课程教学存在的问题为出发点,围绕循环结构教学内容,分析了逻辑思维和计算思维能力培养的必要性。文章从计算思维、逻辑思维、信息与数据的关系等方面剖析了循环结构教学内容的教学要点,设计了以循环不变式为基础的循环结构教学过程及其训练方法,经实践证明可有效地培养学生的逻辑思维和计算思维能力。

循环不变式开发新策略及其应用

循环不变式体现了循环程序的本质特征,在算法程序的开发、证明和推导中具有十分重要的作用。而传统的循环不变式开发策略并没有很好地解决循环不变式开发难的问题。文章在阐述现有策略局限性的基础上,详细阐述了刻画循环不变式本质特征的新定义及基于此定义的开发循环不变式的新策略,并通过三个典型的实例,对开发新策略的具体应用作了比较深入的探索。

非线性循环不变式的自动生成

提出了一个自动生成非线性循环不变式的算法。循环不变式可以表示成一个带参数的多项式的形式,根据断言的归纳特性,将循环不变式的生成问题转变成一个约束求解问题,这个约束求解问题的每个解对应于一个循环不变式,如果约束求解问题仅有零解,则说明不存在该参数多项式形式的循环不变式。该算法在Maple中得到了实现,并通过一些实例说明了该算法的有效性。

循环不变式开发技术研究

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

PAR方法和循环不变式的范畴语义

范畴论对理解程序规约及程序设计和正确性证明十分有用。PAR方法则是建立在严格的数学基础之上的一种统一的算法程序设计方法。循环不变式在循环算法程序的设计中至关重要。使用格理论和范畴论作为工具对PAR方法建立一个理论框架,并对其用范畴论的概念加以解释,从而使得PAR有更强的理论基础。在此基础上引入不动点原理深入刻划循环不变式的含义,循环不变式可以表示为谓词泛函的最小不动点,并从范畴论的角度解释该过程。

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

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

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

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

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

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

充分发挥循环不变式在程序设计课程教学中的作用

提高学生的程序阅读和理解能力是程序设计课程教学的主要目标之一。循环不变式体现了算法程序的本质特征,它在阅读和理解算法程序过程中具有十分重要的指导意义。文章通过具体实例详细说明了循环不变式在程序设计课程教学中的作用。

程序正确性证明及循环不变式的寻找方法

重点讨论了与程序验证相关的问题 ,并结合已有的求取循环不变式的方法给出了求已知循环程序的循环不变式的原则。

从集合论的角度分析循环不变式

Dijkstra-Gries提出了五种循环不变式的开发技术,薛锦云教授另外又给循环不变式作为迭代算子的定义,本文从集合论的角度来看循环不变式.

关于求已知do循环不变式的一个方法及for循环的WP的定义

对确定性do循环,利用其WP求出循环不变式.给出了for循环的话义定义.

基于遗传规划寻找循环不变式的方法

描述了一种产生循环不变式主要部分的方法。该方法的基本思想是在每一次循环条件变化时记录下程序变量的值,生成相应的跟踪表,从跟踪表中获得程序变量之间的函数关系构成循环不变式的主要部分。程序变量之间的函数关系则利用遗传规划对跟踪表中数据执行符号回归得到。

试论循环不变式和囿界函数在循环研制中的地位和作用

详尽分析了循环不变式和囿界函数在循环研制中的地位和作用,并讨论了其构造方法。

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

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

用Dixon结式产生非线性循环不变式

针对循环程序的部分正确性问题,在代数变迁系统理论基础上,结合约束理论提出了一种用Dixon结式生成循环不变式的算法。首先,程序被转换成代数变迁系统,再根据代数变迁关系和不变式模板构造一个多项式组,计算此多项式组的Dixon结式可以得到关于模板变量的约束,最后对该约束系统求解就得到该模板形式的程序不变式。经实例分析,该算法应用于单路径和多路径程序均是有效的。

一类单元赋值语句型循环不变式的开发方法研究

依据现有循环不变式的定义和开发策略,阐述了一类单元赋值语句型循环不变式开发方法,同时使用Dijkstra最弱前置谓词方法确认了循环不变式的正确性.最后通过典型实例来说明该方法的应用.

用daikon发现循环不变式

随着软件行业的深入发展,软件存在的问题与日俱增,程序正确性受到了广泛的关注,形式化方法是解决程序正确性的基本途径,而发现程序循环不变式是证明程序正确性的关键。本文介绍了循环不变式的基本概念以及计算不变式的基本方法;用JAVA重写了Siemens的replace C程序,并以JAVA和C两种语言的replace程序为例,对不变式动态探测工具daikon进行了深入的实验研究,试验结果揭示了daikon在探测循环语句不变式方面的不足,依此提出了改进daikon探测循环不变式的措施。

2类数列问题循环不变式开发策略研究与应用

该文通过对组合数学中Catalan数列问题和Fibonacci数列问题进行深入研究,利用归纳推理、组合数学中的加法和乘法原理等方法得到问题求解函数,使用变量记录算法求解过程中子问题的解,并约束循环变量的变化范围,获得问题求解算法的循环不变式,由此得到了2类数列问题循环不变式的统一开发策略.以二叉树的形态数问题和阶梯问题为例,利用所提策略开发循环不变式,并基于循环不变式展示了这2类数列问题算法程序的形式化推导过程.