软件模型检测新技术研究

软件模型检测以其潜在的商业价值一直为学术界和工业界关注．本文通过剖析模型检测工具SLAM，探讨软件模型检测的机理、方法及若干核心技术，并总结出软件模型检测的一些新策略．     

软件并行开发控制模型及其CASE系统

提出了软件并行开发控制模型CCM;设计了一个支持它的基于Petri网的计算机辅助软件工程系统CCM-CASE。并给出了CCM模型及其语言表示的形式定义;介绍了CCM-CASE的系统结构;讨论了在CCM-CASE系统支持下的并行控制技术。     

模型检测技术在软件并行缺陷检测中的应用

多线程并行运行的软件在提高性能的同时,其交互的组合随着程序规模增大变得更为复杂,给软件的设计与验证带来了挑战.本文从常见的并行缺陷入手,提出使用模型检测的方法对其进行检测和分析,实践表明,使用该方法可有效检测此类并行缺陷.     

一种软件模型检测方法及其原型系统

Microsoft Research.Zin项目

MOPS:an Infrastructure for Examining Security Properties of Software

程序分析技术 2005

基于符号模型检测方法的应对规划系统 2006

>>更多...     

一个基于Petri网的软件并行开发控制模型

软件开发活动的并行化是缩短软件开发周期、加快软件开发速度的有效途径。本文提出了一个基于Ｐｅｔｒｉ网的支持软件并行开发的并行控制模型ＣＣＭ及其构造方法，从而为实现软件并行开发的有效控制和开发相应的ＣＡＳＥ系统奠定了基础。     

软件项目管理中的并行主体模型

软件项目管理中普遍存在开发效率低下,工期拖延的情况。利用并行工程的概念,采用智能主体的技术,提出并行主体模型来仿真软件开发的过程,为智能决策提供支持,还分析了利用该工具实施软件开发中需要注意的要点。     

软件模型检测中的抽象

软件模型检测对保证软件的正确性和可靠性具有十分重要的意义，而抽象是减轻模型检测中状态爆炸问题最重要的技术之一。本文综述当前广泛应用于软件模型检测中的抽象技术，介绍了该领域的进展及研究方向。     

基于双格的软件产品线模型检测

软件产品线在保留每个产品的可变性前提下通过最大化产品间的共性实现资源的再利用,从而提高生产效率和节约生产成本。近年来,基于特征的状态迁移系统应用于软件产品线的建模和验证中。然而现有的方法不能很好地支持软件产品线中存在的信息不确定和不一致的情况。为此,首先提出一种基于双格的特征迁移系统,用于软件产品线的行为建模,采用投影的方法定义产品的行为模型;然后采用动作计算树逻辑描述系统的时序属性,并且给出它在新系统上的语义,用于支持基于双格的模型检测;最后,采用多值模型检测工具χchek对方法的有效性进行实验分析。     

并行推理机及其基本软件综述

本文简要介绍FGCS计划的总体框架、PIM机及其基本软件。FGCS原型系统的核心是并行推理系统,包括并行推理机PIM和它的操作系统PIMOS。知识库管理系统(KBMS)建立在并行推理系统上,并与PIMOS共同构成FGCS原型系统的基本软件。在此基础上,开发出约束逻辑程序设计语言的LP(Language Processor)、并行定理证明器、自然语言处理系统等高级知识程序设计软件,以支持有力的推理和知识处理。为评估PIM和探索知识处理的新领域,研制了几个实验性应用系统。总之,有关PIM的成果和基本软件远远超过了FGCS计划的初始研究目标。     

Parallel Assignments in Software Model Checking

In this paper we investigate how formal software verification systems can be improved by utilising parallel assignment in weakest precondition computations.We begin with an introduction to modern software verification systems. Specifically, we review the method in which software abstractions are built using counterexample-guided abstraction refinement (CEGAR). The classical NP-complete parallel assignment problem is first posed, and then an additional restriction is added to create a special case in which the problem is tractable with an O(n²) algorithm. The parallel assignment problem is then discussed in the context of weakest precondition computations. In this special situation where statements can be assumed to execute truly concurrently, we show that any sequence of simple assignment statements without function calls can be transformed into an equivalent parallel assignment block.Results of compressing assignment statements into a parallel form with this algorithm are presented for a wide variety of software applications. The proposed algorithms were implemented in the ComFoRT reasoning framework [J. Ivers and N. Sharygina. Overview of ComFoRT: A model checking reasoning framework. Technical Report CMU/SEI-2004-TN-018, Carnegie Mellon Software Engineering Institute, 2004] and used to measure the improvement in the verification of real software systems. This improvement in time proved to be significant for many classes of software.     

Software Model Checking: The VeriSoft Approach

Verification by state-space exploration, also often referred to as model checking, is an effective method for analyzing the correctness of concurrent reactive systems (for instance, communication protocols). Unfortunately, traditional model checking is restricted to the verification of properties of models, i.e., abstractions, of concurrent systems.We discuss in this paper how model checking can be extended to analyze arbitrary software, such as implementations of communication protocols written in programming languages like C or C++. We then introduce a search technique that is suitable for exploring the state spaces of such systems. This algorithm has been implemented in VeriSoft, a tool for systematically exploring the state spaces of systems composed of several concurrent processes executing arbitrary code.During the past five years, VeriSoft has been applied successfully for analyzing several software products developed in Lucent Technologies, and has also been licensed to hundreds of users in industry and academia. We discuss applications, strengths and limitations of VeriSoft, and compare it to other approaches to software model checking, analysis and testing.     

Parallel Model Checking Large-Scale Genetic Regulatory Networks with DiVinE

Studies of cells in silico can greatly reduce the need for expensive and prolonged laboratory experimentation. The use of model checking for the analysis of biological networks has attracted much attention recently. One of the practical limitations is the size of the model. In the paper we report on parallel model checking of genetic regulatory network using the model-checker DiVinE. The approach can check linear time properties on large networks.     

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

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

Transactions for Software Model Checking

This paper presents a software model checking algorithm that combats state explosion by decomposing each thread's execution into a sequence of transactions that execute atomically. Our algorithm infers transactions using the theory of reduction, and supports both left and right movers, thus yielding larger transactions and fewer context switches than previous methods. Our approach uses access predicates to support a wide variety of synchronization mechanisms. In addition, we automatically infer these predicates for programs that use lock-based synchronization.     

一种面向软件行为和多视点的需求模型验证方法

软件需求分析是软件开发生命周期中最重要的步骤之一.模型驱动的需求分析方法将需求模型作为需求规格说明的补充,从一个或多个角度对非形式化的需求信息进行正确性验证以发现需求规格中的不一致和不完整性等.本文在一种新型的,基于软件行为和多视点的需求建模方法基础上,依据其构造特点,提出需求模型的分析以及验证方法.该方法主要通过构造模型待验证性质的行为时序逻辑规约,以需求模型对应的有穷状态迁移系统为基础,结合On-The-Fly的方法验证性质规约是否语义满足该状态迁移系统.此外,从命题抽象的角度对该验证方法进行优化.针对该方法实现了模型验证工具原型.     

基于模型检验的软件安全静态分析研究

软件安全静态分析是检测软件安全漏洞的一种手段。本文在总结现有的软件安全静态分析方法的基础上，将在硬件设计领域得到成功应用的模型检验方法引入到软件产品的检验中，给出了一种基于自动机理论的检测软件安全的模型检验方法，阐述了其原理和工作流程，并用实例进行了验证说明。     

以状态子集为中心的并行模型检测算法

以线性时序逻辑LTL（Linear Temporal Logic）模型检测算法为研究对象,提出以状态子集为中心的并行模型检测算法.针对传统单机多核算法同步开销大的缺点,新算法充分利用状态子集的稠密特性动态调度任务,从而降低同步开销,提高算法并行度.本文基于轻量级单机图计算框架Ligra,结合检测过程中状态子集的特性,设计并实现新的在线（on-the-fly）模型检测算法.与现有算法相比,在模型检测的效率上可以提升20-30%,具有高扩展性特征.     

基本并行进程活性的限界模型检测

基本并行进程是一个用于描述和分析并发程序的模型,是Petri网的一个重要子类.EG逻辑是一种在Hennessy-MilnerLogic的基础上增加EG算子的分支时间逻辑,其中的AF算子表示从当前的状态出发性质最终会被满足,因此EG逻辑是能够表达活性的逻辑.然而,基于基本并行进程的EG逻辑的模型检测问题是不可判定的.由此,提出了基本并行进程上EG逻辑的限界模型检测方法.首先给出了基本并行进程上EG逻辑的限界语义,然后采用基于约束的方法,将基本并行进程上EG逻辑的限界模型检测问题转化为线性整数算术公式的可满足性问题,最后利用SMT求解器进行求解.     

Load Balancing Parallel Explicit State Model Checking

This paper first identifies some of the key concerns about the techniques and algorithms developed for parallel model checking; specifically, the inherent problem with load balancing and large queue sizes resultant in a static partition algorithm. This paper then presents a load balancing algorithm to improve the run time performance in distributed model checking, reduce maximum queue size, and reduce the number of states expanded before error discovery. The load balancing algorithm is based on generalized dimension exchange (GDE). This paper presents an empirical analysis of the GDE based load balancing algorithm on three different supercomputing architectures—distributed memory clusters, Networks of Workstations (NOW) and shared memory machines. The analysis shows increased speedup, lower maximum queue sizes and fewer total states explored before error discovery on each of the architectures. Finally, this paper presents a study of the communication overhead incurred by using the load balancing algorithm, which although significant, does not offset performance gains.