深圳在线制作网站,wordpress显示当前位置,推广软文案例,优改网logo设计要验证现实状态机模型B和理想状态机模型A的相似性#xff0c;以及B中各个状态迁移的正确性#xff0c;核心问题在于如何判断被测对象所处的状态。围绕这一问题发展出来的种种技术#xff0c;就成为了基于有限状态机的测试方法中的关键部分。
本篇我们继续讨论这些关键技术。…要验证现实状态机模型B和理想状态机模型A的相似性以及B中各个状态迁移的正确性核心问题在于如何判断被测对象所处的状态。围绕这一问题发展出来的种种技术就成为了基于有限状态机的测试方法中的关键部分。
本篇我们继续讨论这些关键技术。 7. 复位序列 严格来说自适应区分序列并不是一个输入序列而是一棵决策树。例如对于图7所示状态机A 图7 其自适应区分序列如图8所示 图8 决策过程如下
(1) 首先尝试给A输入a。如果输出是0说明初始状态可能是s1、s3或s5当前状态可能是s2对应初始状态s1、s4对应初始状态s3或s6对应初始状态s5
(2) 然后输入a输出必然为1当前状态可能是s3对应初始状态s1、s5对应初始状态s3或s1对应初始状态s5
(3) 然后输入b输出必然为0当前状态可能是s4对应初始状态s1、s6对应初始状态s3或s1对应初始状态s5
(4) 然后输入a (4.1) 如果输出为0则当前状态只能是s2对应初始状态s5这就找到了一个叶节点说明状态机的初始状态是s5。也就是说当输入序列aaba对应的输出是0100的时候就能识别出状态机的初始状态是s5 (4.2) 如果输出为1则当前状态可能是s5对应初始状态s1或s1对应初始状态s3。 (4.3) 继续输入b输出必然为0当前状态可能是s6对应初始状态s1或s1对应初始状态s3。 (4.4) 继续输入a (4.4.1) 如果输出为1则当前状态只能是s1对应初始状态s1。也就是说当输入序列aababa对应的输出是010101的时候就能识别出状态机的初始状态是s1 (4.4.2) 如果输出为0则当前状态只能是s2对应初始状态s3。也就是说当输入序列aababa对应的输出是010100的时候就能识别出状态机的初始状态是s3。
最初输入a的时候如果输出是1则进入决策树的右侧分支后续过程和左侧分支类似。
并非所有最简状态机都存在自适应区分序列。比如图6所示的最简状态机就不存在自适应区分序列因为决策树既不能从输入a开始也不能从输入b开始。 图6 一个状态机有可能并不存在预设区分序列但却存在自适应区分序列。图7所示状态机就是这样的一个例子。 图7
假设这个状态机存在预设区分序列那么预设区分序列只能从a开始因为初始状态和当前状态的可能集合都是{s1, s2, s3, s4, s5, s6}如果从b开始就会让当前可能状态s1、s2、s6发生归并。而输入a之后初始状态区分和当前状态区分都是这时下一个输入字符是什么呢仍然只能是a因为一旦输入b就会让当前可能状态集合{s2,s4,s6}中发生归并。连续输入两个a之后初始状态区分为并没有实现进一步的区分。后续输入更多字符的情况也是类似的。因此这个状态机不存在预设区分序列。
如果一个输入a不会导致当前可能状态集合C发生归并我们称输入a对C而言是“有效”的也就是说都有或。在自适应区分序列的输入决策过程中每一步所面对的当前可能状态集合都是唯一确定的每一步输入都只需要对这个集合是有效的。而预设区分序列的工作过程中由于缺少输出的反馈信息每一步所面对的当前可能状态集合有多个每一步输入必须对所有这些集合都是有效的。这就是为什么有的状态机存在自适应区分序列却不存在预设区分序列的原因。
仍然以图7所示状态机为例来说明判定自适应区分序列是否存在的方法。
输入第一个a之后当前状态区分为其中包括两个当前可能状态集合。对第一个集合{s1,s3,s5}而言输入b是有效的且输入b之后s1仍然在该集合中s3和s5则会迁移到第二个集合中。这样当前状态区分就更新为中包括三个当前可能状态集合对第三个集合{s2,s4,s6}而言输入a是有效的且输入a之后s2和s4会迁移到第二个集合中s6则会迁移到第一个集合中。这样当前状态区分就更新为中包括四个当前可能状态集合对第二个集合{s3,s5}而言输入b是有效的且输入b之后s3会迁移到第三个集合中s4则会迁移到第四个集合中。这样当前状态区分就更新为中包括五个当前可能状态集合对第四个集合{s2,s4}而言输入a和b都是有效的。如果输入bs2会迁移到第一个集合中s4则会迁移到第三个集合中。这样当前状态区分就更新为。至此每一个当前可能状态集合中都只有一个状态这时我们就能确定自适应区分序列是存在的。
显然如果理想模型A存在自适应区分序列那么其任一状态都存在唯一输入输出序列。但反之不然。假定其状态si的唯一输入输出序列是xi那么该状态的划分集可以取为{xi}。由于自适应区分序列是从唯一的根节点生长出来的决策树任意两个状态的区分序列都会有共同的前缀所以是划分序列簇由此也可知唯一输入输出序列不能用于构造划分序列簇因为不同状态的唯一输入输出序列不一定有共同的前缀。因此可以利用每个状态自己的唯一输入输出序列验证现实模型B与A的状态相似性以及B是否正确实现了每个迁移。
仍然以图1所示状态机A为例 图1 其自适应区分序列如图9所示 图9
则状态s1的唯一输入输出序列x1ab状态s2的唯一输入输出序列x2a状态s3的唯一输入输出序列x3ab。以下输入序列可以从初始状态s1开始遍历A的所有状态最终回到s1并验证B与A的相似性 实际上验证各个状态和迁移的输入序列中经常存在冗余比如两个输入序列是完全相同的或者一个输入序列是另一个输入序列的前缀。去除这些冗余检查序列就可以得到简化。看另一个例子假设A如图10所示 图10
A的自适应区分序列如图11所示 图11
则状态s1的唯一输入输出序列x1bb状态s2的唯一输入输出序列x2b状态s3的唯一输入输出序列x3bbb状态s4的唯一输入输出序列x4bbb。同时假设B具备重置能力重置输入字符为r。则如下一组输入序列可以分别验证s1、s2、s3、s4在B中存在对应的相似状态
{rbb, rbb, rabbb, rbbbbb}
如下一组输入序列可以验证各个迁移的正确性
{rbb, rbbbbb, rbbabbb, rbbaab, rabbb, raab, rabbb, rbab, rbbbbbb}
合并这些输入序列中的重复或互相包含的部分最终得到检查序列为raabrabbbrbabrbbabbbrbbbbbb 8. 识别序列
为了验证B与A相似我们需要针对A的每一个状态si测试其划分集Zi中的每一个输入序列确认B的输出是否与A相同。假定Zi中有两个输入序列z1和z2那么我们就需要先让B进入某个状态si然后给B输入z1再让B回到si最后给B输入z2。如果这个过程中B的输出都跟A相同那么si就与si相似。但问题是如果B不能输出状态消息也没有重置能力甚至不存在区分序列那么如何确保输入z1之后B能回到si呢
这时候我们还有一种办法就是利用“识别序列”。
仍然以如图1所示状态机A为例 图1
我们的目标是验证A的状态s1与B中某个状态相似。已知s1的划分集是{a, b}。设B的初始状态是q0给B输入aaa使B的状态依次迁移至q1、q2、q3并且观察到对应输出为000。由于B最多只有3个不同的状态一致性测试的基本假设q0~q3中必然有两个状态是相同的假设这两个状态是qi和qji≠3且j≠3。因为B进入qi和qj之后收到的输入都是a所以这两个状态各自的后继状态qi1和qj1也是相同的。以此类推可知最后一个状态q3也必然与q0~q2中某个状态qk相同。既然当B处于qk状态时输入a对应的输出是0那么在B处于q3状态时输入a对应的输出也必然是0。因此我们只需要测试当B处于q3状态时给B输入b的情况。如果这时B的输出是1我们就足以断定B的状态q3与A的状态s1相似。因此aaab就是状态s1的识别序列。如果给B输入aaab对应的输出是0001那么输入aaa之后B的状态就是与s1相似的状态s1’。
如果A有n个状态状态si的划分集Zi{z1,z2}设则序列是状态si的识别序列。
不失一般性设A的状态si的划分集即是说可以让A从si状态先迁移到状态再回到si状态。定义如下输入序列 则序列是状态si的识别序列。如果这个序列测试通过了我们就可以断定B在输入之后进入的状态与A的si状态是相似的。
设状态si的识别序列是且则如下序列可以验证B是否与A相似 如何利用识别序列验证迁移的正确性呢既然可以确保让B进入与si相似的状态在B的输出与A相符的前提下那么对于迁移的验证我们就可以先利用让B进入然后给B输入a验证输出是否为0继而使用的划分集验证后继状态是否为。
