带参并发系统的模型检测

来源 :中国科学院软件研究所 | 被引量 : 0次 | 上传用户:yiyu
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
带参并发系统实际包含~族并发系统实例,其中以一个(或多个)参数表示每个系统实例的规模,比如实例系统中并发执行的进程个数或数据域的大小。带参模型检测的任务是验证对任意的参数数值,所有的系统实例都满足所期望的性质。本文研究带参并发系统的模型检测方法和技术。   一般来说,带参系统的参数不仅代表进程个数,也可以是通信缓冲区容量、数据域大小、数据通路宽度等。然而迄今为止,该领域的绝大多数研究都针对前者类型的参数,而往往忽视数据方面的参数。本文中,我们提出基于带符号迁移图的复合型带参网络协议建模框架。系统表示为顺序结构的“结点进程”的并发复合,彼此通过“信道进程”进行通讯;性质以一种嵌套谓词等式系形式的一阶μ演算表达;进而相应扩展由实验室自主开发的传值进程模型检测工具,对于数据带参的并发系统给出有效的验证方法,并且对于一些典型的带参系统作出实例研究。出乎意料的是,在GERMAN2004协议的缓存一致性已经被其他研究者证明正确的情况下,我们却发现了它在于数据一致性方面的一个严重错误,并予以更正。进一步,应用我们检测工具中所实现的“数据无关”技术,我们有效推广了研究结论,证明了对于任意大小的数据域.修改后的GERMAN协议仍然保证满足数据一致性要求。   环境抽象的方法将计数抽象的思想借鉴到谓词抽象的技术中,对于控制带参的并发系统给出一般性验证框架。然而该方法具有相当高的复杂度;对于很多实际应用的系统而言,所构造的抽象系统规模仍然超出常用模型检测工具所能处理的范围。为了克服这个困难,我们提出了状态聚类方法,在局部可达性分析的基础上,通过对系统表达式的分析把全部可达的局部状态分组成为少数几个状态簇。在进行状态聚类的启发式算法中,我们采用了先分裂后聚合的策略,即在识别出不同类的具有代表性的状态配置后,再将类似的状态尽可能合并到同一个状态簇。这样局部状态被相应划分成为若干等价类,每个类以一个单元状态为代表。然后我们在系统描述的层次上,通过程序重写的方式直接构造生成对应的抽象系统。实例研究显示,状态聚类方法通常能够将抽象节点的大小缩减约3个数量级。   参数抽象作为带参系统的安全性性质验证的另外一个有效方法,其最困难之处在于找到合适的辅助不变量,用以进行卫加强以精化抽象模型。针对这个问题,作者提出一种启发式的方法,通过在参考模型中计算自动产生辅助不变量。利用这一技术,我们将参数截断的思想应用于处理环境抽象中依赖于参数类型的复杂变量,使得环境抽象在状态聚类后得到进一步优化。我们有效结合了参数抽象与环境抽象技术,显著降低了抽象系统状态空间规模,从而极大节省了模型检测的内存开销;并且由于抽象中的每个步骤都以现行的模型检测工具辅助计算,整个验证过程可以机械化完成,不需要过多的人工介入。作为示范,对于工业应用的复杂的缓存一致性协议FLASH,我们在保留了其中最为著名的“三跳”事务处理的情况下,验证了缓存一致性和数据一致性。据我们所知,这是首次这样工业实用的复杂协议能够同时在控制方面和数据方面在如此的精度上得到成功验证。
其他文献
政府信息检索系统作为政府信息公开平台的重要组成部分,对于用户从大量信息中.准确查找所需信息起到关键作用,然而现有政府信息检索系统存在两个主要问题:一是系统采用的基于关
移动代理技术是未来网络计算的一种新模式,特别适合于电子商务领域。其安全性是制约移动代理技术能否广泛应用的重要因素,数据完整性是其中的一个关键问题。   移动代理数据
资源发现技术是根据给定的资源描述,在网络中自动找到相应资源的技术,该技术能够智能地满足网络中应用和指挥任务执行时对资源信息的需求,并且能够为资源的管理和监控提供一定支
网络应用系统已经成为我们日常工作中的重要组成部分,因此各个单位的应用系统数目也在不断增加,而对这些系统的权限进行统一管理也成为了新的需求。   现在已经出现了很多的
随着Internet的发展,越来越多的软件系统运行和部署在网络环境上,软件形态逐渐由确定性目标转变为动态性目标,由基于实体驱动向基于协同驱动发展.软件系统越来越强调根据需求的
卫星网络是一个由不同轨道上多种类型的卫星组成的系统,按照空间信息资源的最大有效综合利用原则,互通互连、有机构成的智能化体系。随着这种新型网络系统的产生和应用,卫星自身
随着人工智能理论和计算机网络技术的迅速发展,近几年来基于网络的智能计算机辅助教学系统研究也不断兴起,基于网络的智能计算机辅助教学系统是一个涉及教育学、计算机科学、心
可用性技术是提高计算机系统在发生故障情况下持续运转能力的有效手段。操作系统作为计算机的管理者,其可用性是整个系统的核心。运行在复杂环境中的嵌入式系统对可靠性、实时
在计算机图形学领域,阴影的绘制一直是一个热点的研究内容,它对增强场景的真实感有着非常重要的意义。完全物理正确的柔和阴影绘制通常需要耗费大量的时间,于是研究者们提出了各
随着半导体行业的飞速发展,集成电路规模的不断提高,系统芯片SoC(System on Chip)技术已逐渐成为集成电路技术的主流。在芯片设计流程中,验证是其中最复杂、最耗时的环节,而复杂