formal-verification - 检查分支是否被执行

Question

程序可以从 START 分支到 LEFT 或 RIGHT 分支。如何检查 LEFT 分支的执行路径和 RIGHT 分支的另一个执行路径？

------------------------------ MODULE WFBranch ------------------------------

VARIABLE state

START == "start"
LEFT == "left"
RIGHT == "right"

Init == state = START

Next ==
    \/  /\ state = START
        /\  \/ state' = LEFT
            \/ state' = RIGHT
    \/  /\ state \in {LEFT, RIGHT}
        /\ state' = START

Spec ==
    /\ Init
    /\ [][Next]_<<state>>
    /\ WF_<<state>>(Next) \* Avoid stuttering at start

(*
This passes, but it does not ensure that there exist different paths covering both
branches - e.g. state might never be LEFT.
*)
CheckEventualStates == \/ (state = START) ~> (state = RIGHT)
                       \/ (state = START) ~> (state = LEFT)

=============================================================================

Answer 1

在完全一般的情况下，没有办法检查每个状态，至少有一个行为最终达到它。这是因为 TLA+ 基于 线性时序逻辑 ，它没有表达在多种不同行为之间存在的属性的方法。

根据具体情况，有时您可以制作替代品。例如，我们可以写

Left == 
  /\ state = START
  /\ state' = LEFT

Right ==
  /\ state = START
  /\ state' = RIGHT

Next ==
    \/  /\ state = START
        /\  \/ Left
            \/ Right
    \/  /\ state \in {LEFT, RIGHT}
        /\ state' = START

然后你可以检查有两个分支

CheckEventualStates ==
    /\ <>(ENABLED Left)
    /\ <>(ENABLED Right)