基于Spin的模型检验研究

来源 :南京大学 | 被引量 : 0次 | 上传用户:bibby_514
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着计算机系统规模和复杂度的不断增加,应用范围的不断扩大,人们对系统正确性的要求也日益提高。模型检验是一种形式验证技术,它的主要思想是构造系统的有限状态模型并穷尽搜索系统的整个状态空间以检验系统模型是否满足特定的性质。由于模型检验能够自动进行,并且在系统不满足性质时给出反例以帮助用户定位错误,它正在受到学术界和工业界越来越多的关注。由于符号化算法、偏序约简和抽象等技术的逐步发展成熟,模型检验技术已经可以处理相当规模的系统状态空间, Spin是一种被广泛应用的成熟的模型检验工具。它采用Promela语言作为系统建模语言和性质描述语言,具有强大的描述检验需求的能力,并且Spin中实现了现有先进的检验技术以确保检验过程的高效率。本文以Spin为基础,研究了检验以时段时序逻辑给出的系统规约和对并发C#程序建模的问题,主要的工作包含以下方面: (1)针对目前在使用时段时序逻辑给出系统规约并进行检验的过程中存在的问题,提出了应当根据性质的直观含义确定其满足关系。我们将时段时序逻辑描述的性质分为两类,分别定义了它们各自的满足关系。进而,我们将这两种满足关系统一为一个更一般性的满足性定义,并以此为根据设计了相应的模型检验算法。使用该算法,我们可以利用已有的模型检验工具来检验以时段时序逻辑形式给出的系统规约。 (2)将上面的模型检验算法实现为基于时段时序逻辑的模型检验工具QRD-Checker。QRDChecker从以时段时序逻辑形式给出的系统规约构造相应的Promela时序声明,用于Spin检验。 (3)研究了从并发C#程序构造检验模型的策略,提出了针对C#程序中对象模型、语言模型和线程模型的翻译模型。C#中的类通过Promela中的用户定义类型建模,静态变量通过全局变量建模;C#中的方法、属性和索引器被内联到Promela程序中;C#中的线程被对应到Promela中的进程,线程间的同步通过同步/异步信道上的消息通信建模。 (4)基于上面的翻译模型实现了并发C#程序的模型抽取工具CSharp2Spin。CSharp2Spin能够自动根据并发C#程序生成相应的Promela模型,Promela模型可以直接用于Spin检验。CSharp2Spin能够处理大部分C#语言中的语法现象,具有一定的实用性。
其他文献
近年来,Internet正以令人难以置信的速度在飞速发展,越来越多的机构、团体和个人在Internet上发布信息、查找信息。虽然Internet上有海量的数据,但由于Web是无结构的、动态的,并
教育资源库是一个庞大的系统,包括大量的媒体素材库、课件库、题库、案例库、附件库等等,其多媒体教育资源种类繁多、形式各异.要有效的进行检索,除了要定义良好的资源库的逻
软件工程发展几十年,各种理论与技术不断涌现,但是各种异构系统之间的集成、规约,即实现软件系统互操作性(interoperability),以便达到领域复用的目的仍是软件面临的重大问题
中国的证券市场成立十几年以来,随着信息化的发展,金融机构积累了大量的原始数据.激增的数据背后隐藏着许多重要的信息,人们可以对其进行更高层次的分析,以便于更好的利用这
科学数据库及其应用系统(简称"科学数据库")是中科院"十五"信息化建设的重大项目,该文讨论的内容就是以此项目为背景的.科学数据库经过二十年的资源积累,现存的海量数据资源
随着信息技术的发展,全球经济一体化的加剧,企业管理正经历一场思想上与技术上的巨大变革.其中,离散企业的采购作为离散企业管理重要的一部分与离散企业供应链重要一环面临着
论文从数据仓库(Data Warehouse)的产生背景及其基本概念、联机分析处理(On_Line Analytical Processing-OLAP)的产生背景及其基本概念、SQL Server 2000体系结构、SQL Serve
数据集成是企业之间或者企业内各部门协同合作的需要.它的目标是实现各个异构数据源之间的数据共享,从而有效的利用资源,提高整个应用系统的性能.目前随着计算机技术特别是计
在计算机科学的许多领域,可满足性问题(SAT)都是一个重要的研究课题。SAT是一个NP完全问题,但在各种领域都需要快速算法来解决规模较大的问题,比如在人工智能中比较突出的规划问
学位