程序重构预处理在提高软件模型检测效率中的应用

针对软件模型检测目前很难处理大型程序的问题,提出用程序重构技术对待检的源代码进行预处理,以提高模型检测算法的效率.程序重构将大型程序分解成语义一致的小型过程的集合,由于模型检测算法中过程总结边可单独计算,而且在程序中对某过程的调用可能有多次,这种预处理可以避免状态空间的重复搜索,从而降低模型检测算法在空间和时间上的开销.根据表达程序性质的线性时序逻辑LTL公式的构成,给出了程序重构预处理前后程序语义相等的充分条件;并给定程序和性质公式,用blast作为程序模型检测实验工具,比较程序重构预处理前后blast的运行结果.理论分析和部分程序上的实验表明：程序重构预处理能降低大型程序的模型检测开销,并满足软件模型检测的安全性要求.     

软件模型检测中的抽象模型研究综述

抽象是解决模型检测中状态爆炸问题的一个基本方法.对近年来软件模型检测研究中所提出的一系列抽象模型进行综述.首先以抽象解释为理论框架阐述了抽象软件模型检测的各组成部分.然后根据模型的结构和功能特征,将抽象模型分为3类:1)传统的用于支持自上逼近或者自下逼近的布尔Kripke结构;2)分别对应于3值和4值Kripke结构的Kripke模态迁移系统(Kripke modal transition systems, KMTS)和混合迁移系统(mixed transition system, MixTS),可同时支持自上逼近和自下逼近的抽象;3)具有超迁移关系的广义Kripke模态迁移系统(generalized Kripke modal transition system, GKMTS)和超迁移系统(hyper transition system, HTS),可提供更精确的抽象模型检测;重点分析这些模型的提出原因、相应的逼近关系、最优模型及其局限性以及抽象模型完备性的研究结果.最后,分析了目前关于抽象模型的理论和应用研究中存在的问题,给出进一步研究的方向.     

基于抽象-验证-细化范例的软件模型检测

如何保证软件系统的正确性和可靠性是当前软件开发面临的主要问题之一。模型检测作为一种重要的自动化验证技术在软件的分析与验证中正取得越来越多的成功。本文以微软的SLAM和加州大学伯克利分校的BLAST为例综述性地介绍了基于抽象-验证-细化范例的软件模型检测。     

面向随机模型检验的模型抽象技术

随机模型检验是经典模型检验理论的延伸和推广,由于其结合了经典模型检验算法和线性方程组求解或线性规划算法等,并且运算处理的是关于状态的概率向量而非经典模型检验中的位向量,所以状态爆炸问题在随机模型检验中更为严重.抽象作为缓解状态空间爆炸问题的重要技术之一,已经开始被应用到随机模型检验领域并取得了一定的进展.以面向随机模型检验的模型抽象技术为研究对象,首先给出了模型抽象技术的问题描述,然后按抽象模型构造技术分类归纳了其研究方向及目前的研究进展,最后对比了目前的模型抽象技术及其关系,总结出其还未能给出模型抽象问题的满意答案,并指出了有效解决模型抽象问题未来的研究方向.     

面向源代码的软件模型检测及其实现

模型检测应用于检测软件可靠性具有重要意义.介绍了一种基于谓词抽象和反例引导抽象求精技术对源程序进行建模和验证的模型检测方法,并结合自行研发的Jchecker工具详细介绍了该软件模型检测技术的运作过程和关键算法.     

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

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

基于抽象和组合方法的网络协议验证

由于模型检测存在状态爆炸问题,多主体的网络协议组合模型检测往往难以进行。为了缓解该问题,分析了通信主体数量增加对状态数量的影响,提出了组合式的抽象验证方法。首先根据所需验证的LTL性质,建立各个通信主体的Kripke结构,再对该Kripke结构进行抽象;然后组合抽象模型;最后运用Spin对组合抽象模型进行检验。为验证该方法的有效性,对NSPK协议进行了检测,结果表明,该方法所需的状态空间向量长度、搜索深度、存贮和遍历的状态数都有明显减少,有利于缓解状态爆炸问题。     

OMR抽象模型

在计算机领域反映现实世界中的事物,离不开有效模型的支持。这个模型一方面是现实世界中具体事物的抽象,另一方面又便于计算机实现。提出的OMR模型反映了现实世界的运行规律,用对象、消息和关系三要素对现实事物进行抽象和描述,是辅助计算机实现的有效工具。为了从形式化和数学化的角度描述OMR模型,又探讨了对象内Petri网和对象间Petri网,从而使OMR模型进一步丰满。     

模型检测中虚假反例检测方法

抽象技术是解决模型检测状态空间爆炸的一种有效方法,但其中一个重大的障碍是对系统的抽象会引入原始系统中本来不存在的行为,即可能会引入虚假反例。因此,需要根据反例对抽象模型进行精化。如何判定一个反例是虚假反例还是真实反例,在抽象精化过程中相当重要。本文根据状态的前驱和后继定义失效状态,给出虚假反例的定义,并基于此提出检测虚假反例的并行算法。     

模型检测在软件测试中的应用

随着计算机软硬件系统日益复杂,如何保证其正确性和可靠性成为日益紧迫的问题。在为此提出的诸多理论和方法中,模型检测（model checking）以其简洁明了和自动化程度高而引人注目。具体介绍了模型检测的一些理论,同时将它应用于具体的软件程序,运用模型检测方法对软件进行测试。从而证明了模型检测方法与测试结合对于软件可靠性和正确性所起的巨大作用。     

模型检测中状态爆炸问题研究综述

模型检测已成为保证软件系统正确性和可靠性的重要手段,但随着软件功能日益强大,其规模和复杂度也越来越大,在模型检测过程中容易产生状态爆炸问题。如何解决模型检测中的状态爆炸,已成为工业界和理论界无法回避的重要课题。系统地综述模型检测领域解决状态爆炸问题的关键技术和主要方法,并提出该领域的最新研究进展与方向。     

模型检测新技术研究

1 引言软件是否可信赖已成为一个国家的经济、国防等系统能否正常运转的关键因素之一,尤其在一些诸如核反应堆控制、航空航天以及铁路调度等安全悠关(safety-critical)领域更是如此。这类系统要求绝对安全可靠,不容半点疏漏,否则将导致灾难性后果。如1996年6月4日,欧洲航天局阿丽亚娜(Ariane)501火箭因为其控制软件的规范和设计错误而导致发射37秒后爆炸。类似的报道屡见不鲜,如何确保这些系统的可靠性成为计算机科学与控制论领域共同关注的一个焦点问题。     

并行软件模型检测

并行化是提高模型检测效率的重要手段。该文研究了基于标号迁移系统的C程序模型检测,提出一种软件模型检测并行化的方法。该方法利用软件模型检测工具模块化验证(MAGIC)的模块化特性对C程序进行组件分解,将各组件均衡地分发到若干计算节点,由节点调用MAGIC完成验证。由于保证节点间只有少量的通信与同步,该方法能达到较好的并行加速比,具有良好的可扩展性。实验结果显示,该方法大幅压缩了检测时间,有利于大规模软件的形式化验证。     

基于特征切片的软件产品线模型检测

特征模型是一种描述软件产品线中共性和可变性特征的通用形式。特征模型象征着所有可能的应用程序配置空间,是实现个性化产品定制的基础。随着软件产品线的规模和复杂程度的增加,如何有效支持以用户需求为基础以及根据特定需求和利益相关者的目标进行个性定制开发是亟待解决的实际问题。提出一种根据用户需求对特征模型进行切片,进一步结合三值逻辑对行为模型进行抽象,最后利用模型检测技术对软件产品线进行验证的方法。实验结果证实了该方法的有效性。