程序切片技术在并发程序模型检查中的应用

模型检查技术在硬件和协议设计方面已经取得很大成功,但在软件验证方面仍存在很多困难。其主要问题是如何从源代码中自动抽取验证所要模型并精简其状态空间。文中通过对程序切片技术的研究,来解决并发程序验证的建模问题,包括把验证公式映射到切片准则．并把得到的程序切片转化为验证所需的模型。经程序切片处理后,软件模型检查效率得到提高。     

程序切片技术在并发程序模型检查中的应用

模型检查技术在硬件和协议设计方面已经取得很大成功,但在软件验证方面仍存在很多困难.其主要问题是如何从源代码中自动抽取验证所要模型并精简其状态空间.文中通过对程序切片技术的研究,来解决并发程序验证的建模问题,包括把验证公式映射到切片准则,并把得到的程序切片转化为验证所需的模型.经程序切片处理后,软件模型检查效率得到提高.     

基于多线程Java程序安全行为模型的静态检查对策探析

本文通过参数化扩展上下文无关文法作为其安全相关行为模型的抽象表示,针对Java多线程序研究,总结出了从多线程Java程序自动生成安全相关行为模型的方法,该方法应用到携带模型代码方法的实现框架中,形象的描述了静态检查该模型是否满足安全策略的实现,同时为安全执行非信任多线程Java移动代码提供了有效支持。本文合理的使用静态分析多线程Java程序的措施,来进行相关安全性的检查,从中来考察出多线程Java程序的相关安全行为。     

程序测试与概率检查

本文在分析传统的程序结果检查方法的基础上，介绍了引进随机概率的自我检查／校正程序设计的及其特点。     

多线程Java程序安全行为模型的静态检查方法

多线程作为支持程序结构化和并行化的重要机制,其应用越来越广泛,多线程应用程序的安全性也成为新的研究热点之一.针对Java多线程程序,文中采用参数化扩展上下文无关文法作为其安全相关行为模型的抽象表示,给出了从多线程Java程序自动生成安全相关行为模型的方法,形式地描述了静态检查该模型是否满足安全策略的实现,并应用到携带模型代码方法的实现框架中.该方法为安全执行非信任多线程Java移动代码提供了有效支持.     

SOCKET通信程序模型抽取及可靠性验证

形式化方法是验证并发系统可靠性和安全性的重要手段。对高级语言开发的并发系统自动抽取的模型进行 形式化验证是模型检测技术领域中的一个研究热点。鉴于socket函数调用顺序不正确产生的运行时潜在问题(内存 泄漏、死锁、边界数据丢失等),针对顺序结构的socket程序,通过描述Promcla消息数据结构和通道,构建socket函数 的Promcla模型,定义socket函数到Promcla映射规则,提出socket函数调用序列抽取算法及目标Promcla模型生成 算法,用线性时态逻辑(LTI.)刻画socket函数调用顺序应满足的性质,开发基于SPIN的socket通信程序分析系统。 实验结果表明,该系统能有效检测socket通信程序的运行时潜在问题。     

一个数据拟合模型程序系统

本文给出了十三种常用的数据拟合模型，并以模型预测值与实际观测值的误差的均方最小为标准，设计了从中选择一个最佳数据拟合模型的计算机程序，该系统采用了ＣＡＤ技术，使数据处理工作完全地在计算机执行，避免了纸上工作。     

程序静态分析中的双重模型策略

介绍了描述程序信息的两种模型(EPOM和OSTPM)以及它们之间的联系，并举例介绍了如何利用这两种模型进行程序的静态分析检测。     

用于验证多智能体系统的APTL模型检测器

由于经典的线性时序逻辑表达能力有限,设计并开发了基于交替投影时序逻辑（alternating projection temporal logic,简称APTL）的模型检测工具.根据王海洋等人提出的APTL符号模型检测方法,设计并实现了APTL模型检测器MCMAS_APTL.该工具可用于多智能体系统（multi-agent system,简称MAS）的性质验证.MCMAS_APTL检查MAS是否满足具体性质的过程如下：首先,用解释系统编程语言（interpreted system programming language,简称ISPL）描述要验证的系统IS,用APTL公式P描述要验证的性质;然后,符号化表示系统IS,并将非P转化为范式;最后,计算所有满足非P的路径的起始状态集合.如果得到的状态集合中包含系统的初始状态,则说明系统不满足公式P;反之,则说明系统满足公式P.详细阐述了实现MCMAS_APTL的过程,并且通过验证机器人足球赛的例子展示了MCMAS_APTL的性能.     

模型检验综述

在软硬件验证里,模型检验是一个重要手段,至今它已经形成一个庞大的方法论体系。现在我们把模型检验内容从标准方法、抽象解释方法、综合方法3个范畴加以介绍,旨在形成人们对模型检验总的印象,从而全面理解和掌握模型检验各个方法的精神实质和具体情况,有助于将这些方法运用到实际软硬件验证中并从中受到启发,以便进一步发展模型检验理论或开发模型检验新的方法和工具。     

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

现有模型检测工具的形式化规范语言,如计算树逻辑(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系统的验证能力,使得时间敏感、并发性和周期性等实时性质可以被描述和验证.     

一种自动化模型检测ANSI-C程序的实用方法

模型检测是一种验证有限状态系统的时序逻辑属性的形式化方法。为了利用模型检测技术,通常的办法是手工构建一个抽象模型,然而这个方法存在一些不足,如成本过高、易引入建模错误等。本文提出了一种自动化模型检测ANSI-C程序的方法,并开发了模型提取工具C2Spin,它能够分析ANSI-C源代码,并生成对应的PROMELA验证模型,从而显著降低了建模的开销。利用C2Spin,模型检测工具SPIN可以自动地检测使用C语言编写的应用程序中的多种错误,如死锁等。在初步实验中,依靠C2Spin生成的模型,我们发现了SPIN4.3.0的一个语义错误,以及Holzmann对两个经典互斥算法的实现程序中的活锁错误。这些结果表明,C2Spin能够帮助人们更加快速有效地测试C程序。     

并发程序的切片模型检验方法

提出了一种对并发程序进行切片以缩减模型检验状态空间的方法，首先针对并发程序中的同步与通信定义了一组依赖关系，包括并发分支与接合．非确定性，信道，共享变量等特征，对于从要验证的时态逻辑性质中提取的关于多个程序点的切片标准，文中给出算法根据相应的依赖关系通过不动点运算得到并发程序切片，可以证明得到的切片与原程序对于该性质具有相同的可满足性。     

MMC: the Mono Model Checker

The Mono Model Checker (mmc) is a software model checker for cil bytecode programs. mmc has been developed on the Mono platform. mmc is able to detect deadlocks and assertion violations in cil programs. The design of mmc is inspired by the Java PathFinder (jpf), a model checker for Java programs. The performance of mmc is comparable to jpf. This paper introduces mmc and presents its main architectural characteristics.     

一种基于模型检验程序分析技术的前端工具研究

提出了一种用模型检验技术对程序进行分析的方法,其主要思想是将C/C++源代码转换为与控制流图等价的Kripke结构,用CTL公式描述待验证的源程序性质,使用NuSMV模型检验工具实施具体的程序分析。基于这一思想,设计并实现了一个自动将C/C++源代码转换为NuSMV输入的工具。所做的实验验证表明,该方法能够有效地对程序进行分析。     

时序逻辑程序的模型检测

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

Verifying Multi-agent Programs by Model Checking

This paper gives an overview of our recent work on an approach to verifying multi-agent programs. We automatically translate multi-agent systems programmed in the logic-based agent-oriented programming language AgentSpeak into either Promela or Java, and then use the associated Spin and JPF model checkers to verify the resulting systems. We also describe the simplified BDI logical language that is used to write the properties we want the systems to satisfy. The approach is illustrated by means of a simple case study.     

多核模型检测工具CTAV的实现与优化

在计算机计算能力大大增强的时代,为了提高对时间自动机进行空性检测的效率,进一步高效利用多核处理器的优势,研究了利用Büchi自动机的多核空性判定算法改造CTAV,使它成为一款时间自动机模型关于线性时序逻辑的多核模型检测工具,从而提高模型检测的效率.通过对符号化状态之间包含关系的研究,利用这种状态之间的包含关系更快的找到接收路径并避免不必要的状态展开,实现了多核模型检测算法的优化,对比了一些常见模型的验证数据,取得了更好的效果.