作者:
刘俏威
关键词:
SPIN ； Promela ； 模型检测 ； 分支界限
摘要:
随着计算机软硬件系统日益复杂,如何保证其正确性和可靠性成为日益紧迫的问题。确保这些系统的可靠性成为计算机科学领域中重要研究领域。为此提出的诸多方法和理论中,模型检测以其简洁明了和自动化程度高而倍受注目。模型检测是一种重要的形式化自动验证技术,此技术的成功应用归功于有效验证工具的开发和支持。SPIN是一种著名的分析验证并发系统逻辑一致性的模型检测工具。模型检测的瓶颈问题是状态爆炸问题,如何以使用精简方式描述系统,避免因为模型复杂而引起状态爆炸是一个值得研究的方向。 本文在阐述SPIN模型检测形式化分析机理及线性时态逻辑LTL性质的基础上,详细分析了基于SPIN的系统建模语言Promela中的并发进程、通道操作、基本数据结构及其功能,设计了模型检测求解离散化问题的方法——通过Promela建立模型,在描述系统属性(性质)中运用分支界限技术,验证过程中LTL公式动态变化,旨在减少模型状态空间,提高搜索效率,实例分析验证了此方法的正确性;同时采用了启发式策略优化模型,即根据SPIN模型检测深度优先搜索的原则,通过静态分析和动态分析方法优化模型,实验结果分析表明SPIN不但可以验证所求解系统模型的正确性,还可以寻找模型的最优解。
在线下载