知识卡片
用层次自动机刻画顺序图
(SPIN 的特点与整体验证流程见旧卡“SPIN验证与EHA”。)
为什么只看执行视图:要验证正确性、安全性等时态属性,与之相关的是对象之间的动态交互,所以针对执行架构视图(UML 顺序图)分析;顺序图中基于详细设计的元素(并发与并行的区别、消息属性、对象类型)对架构无意义,直接忽略。约束假定已用 LTL 写在约束文件中——自然语言约束到 LTL 的自动转换难以实现。
为什么不用一个 DFA:把整个顺序图描述成一个确定有限自动机会过于复杂,状态转移相互关联,对演化的表述能力很差。
扩展层次自动机 EHA: - 整个顺序图是一个层次自动机,每个对象是一个串行自动机,用树形结构(组合函数 ρ)关联; - 禁止串行自动机之间的状态转换,只允许自动机内部转移——大大降低状态间关联的复杂度; - 把事件触发时的动作从转移中剥离,放进目标状态的活动里,每个状态最多一个活动、每个转移最多一个触发事件,方便描述演化; - 发送消息对应状态活动,接收消息对应转移的触发事件;par 片段用外链子层次自动机表示并行,loop、alt、break 等生成相应控制流。
映射到 Promela:根自动机中的状态对应进程(Actor 对应 init 进程),事件对应消息通道,状态活动和转移条件对应消息发送与接收。架构模型没有变量定义与使用,因为架构设计只描述对象间交互。
启示:选形式模型时,除了能不能验证,还要看它能否让“改一处”只影响模型的一处——这是演化验证可行的前提。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
然而将整个顺序图作为一个确定有限自动机(DFA)的形式化描述方法使得自动机过于复杂,而状态之间的转移相互关联,使得在演化方面的表述能力非常差。
参考来源
- 位置:《软件架构理论与实践》第14章《第14章 软件架构形式化验证》14.4.2 基于SPIN的验证过程;14.4.3 架构模型(扩展层次自动机)(源文件:extracted/软件架构理论与实践/_epub-src/OEBPS/text00115.html,来源项目 book-sources)
- 结论依据:第14章基于SPIN的验证只分析执行视图的顺序图,因为单一DFA过于复杂且难以表达演化,所以用扩展层次自动机:每个对象为一个串行自动机,用树形结构关联并禁止跨自动机转移,动作放入状态活动,par用子层次自动机表示,再映射为Promela的进程、通道和消息。
- 原始内容:然而将整个顺序图作为一个确定有限自动机(DFA)的形式化描述方法使得自动机过于复杂,而状态之间的转移相互关联,使得在演化方面的表述能力非常差。