关键词:
形式化方法
模型检查
形式规约验证
摘要:
形式化方法利用数学符号和形式化语言准确描述系统行为和属性,能够为软件系统提供严格的分析和验证,在过去的几十年间取得了显著的进步。然而,形式验证技术在实际应用中面临着诸多困难,其中最突出的问题之一是状态空间爆炸,这限制了模型检查等技术的有效应用。为了解决这一问题,多年来形式验证领域一直在致力于探索验证算法与优化方法,以提高验证效率。
本文着眼于安全与活性两类性质的形式化验证问题,致力于解决模型检查等关键验证技术面对状态空间爆炸时的挑战,其中,安全性质关注系统的稳定性和不变性,而活性性质则关注系统的活跃性和事件发生性质。
本文着重讨论了三个形式化领域内这两类性质验证问题上的验证技术研究,包括安全和活性性质的模型检查问题,以及需求工程中的边界条件识别问题。根据这些问题的特征以及相关研究的现状,本文提出了一系列新颖的算法和优化方法,旨在帮助克服这些形式化方法在实际应用中遇到的挑战,从而推动形式化方法在软件工程中的应用和发展,具体研究内容如下:
1、对于安全性质模型检查问题,本文提出了基于启发式的引理搜索引导优化方法,以改进安全性质模型检查算法的性能。针对安全性质模型检查中的算法原理,定义了一种新的引理类型,提出了相关理论并根据理论提出了基于启发式的搜索方法。通过引入新的启发式搜索策略,能够更有效地构造算法的证明序列,提高模型检查的效率,为解决大规模系统的验证问题提供了新的思路和技术支持。实验评估显示,本文提出的启发式可以有效且显著提升现有验证工具的性能,同时进一步分析证实,算法性能的提升和本文提出的引理搜索效率相关。
2、对于活性性质模型检查问题,提出了一种新的基于SAT的符号化验证算法,用以高效率验证活性性质模型检查问题。针对活性性质模型检查问题的特征,本文引入了名为rlive的新算法,将问题转化为一系列安全性质模型检查问题,通过递归的方式深度优先地搜索反例,并在回溯时逐步约束输入系统,有效地搜索活性问题的解空间。理论证明和实验评估表明,该算法在正确性和性能方面均优于现有的活性检查算法,具有更高的效率和可扩展性。
3、对于面向目标需求工程中的边界条件识别问题,完善了该问题的理论基础,揭示其本质为安全性质验证问题,提出了基于安全性质验证的边界条件搜索算法。通过观察现有方法以及基于语法构造方法的边界条件求解结果特征,本文发现了现有问题定义的不足,在完善理论的同时,提出了强边界条件的概念,证明其本质为安全性质验证问题,另外设计了基于安全性质验证的边界条件搜索算法Semantic BC。实验结果显示,相比于其它方法,Semantic BC算法能够普遍更高效地搜索出边界条件,并且能提供更高质量的边界条件,为系统设计提供了更好的指导和支持,从而提高系统规约的可靠性。