[發明專利]一種基于復合依賴關系覆蓋準則的EFSM測試方法

有效

• 申請號: 201810363831.3
• 申請日: 2018-04-22
• 公開（公告）號: CN108536606B
• 公開（公告）日: 2021-01-19
• 發明（設計）人: 李征;史晶晶
• 申請（專利權）人: 北京化工大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 沈波

1.一種基于復合依賴關系覆蓋準則的EFSM模型測試方法，其特征在于：EFSM模型上的依賴關系分為控制依賴關系和數據依賴關系；本測試方法包括復合依賴遷移對集合生成、遷移對沖突關系檢測及移除和測試路徑生成三個核心部分：

第一、復合依賴遷移對集合生成：在EFSM模型中依據模型的終止性選擇新型的控制依賴關系，生成復合依賴遷移對集合；

第二、遷移對沖突關系檢測及移除：對復合依賴遷移對集合中兩個遷移上的變量進行分析，將條件沖突的遷移對從復合依賴遷移對集合中移除；

第三、測試路徑生成：利用深度優先遍歷的方法來生成滿足復合依賴關系覆蓋準則的測試路徑集，在路徑生成過程中，提出四條路徑生成規則；

在EFSM模型中依據模型的終止性選擇新型的控制依賴關系，生成復合依賴遷移對集合，具體為：

根據EFSM模型的非終止性和非確定性，將控制依賴分為非終止敏感控制依賴、非終止不敏感控制依賴，其中非終止敏感控制依賴適用于終止EFSM模型，非終止不敏感控制依賴適用于非終止模型，需要根據具體情況選擇合適的控制依賴關系；

依據控制依賴和數據依賴的關系生成的依賴遷移對之間存在交集，同時兩者又是非互相包含的，據此提出復合依賴關系覆蓋準則的定義：

首先定義Pair_TS為序列TS的所有遷移對：給定非空序列TS＝＜t₁,...,t_n＞，其中，t_i是EFSM M中的遷移，n表示遷移序號數，i表示第i個遷移序號；如果Pair_TS＝{(t_i,t_j)|1≤i,j≤n}，則稱Pair_TS為序列TS的所有遷移對，j表示第j個遷移序號；接著定義復合依賴關系覆蓋準則：假定EFSM M的遷移集合為T＝{t_i|1≤i≤n}，控制依賴對集合為表示控制依賴關系；數據依賴對集合為集合A＝{TS_i|i∈N}為M中所有遷移序列的集合，表示數據依賴關系；若存在集合A_M＝{TS_l|l∈N}，使得則稱A_M為M的復合依賴關系覆蓋；表示空集；N表示遷移序列序號數，l表示第l條遷移序列序號；

依據定義提出復合依賴遷移對集合的生成方法：首先根據模型的終止性選擇對應的控制依賴關系計算控制依賴對和數據依賴對，并最終生成復合依賴遷移對集合；

對復合依賴遷移對集合中兩個遷移上的變量進行分析，將條件沖突的遷移對從復合依賴遷移對集合中移除，具體為：

由于在路徑生成時會對條件沖突對進行判斷，若復合依賴對集合中存在沖突遷移對，相對應的路徑無法覆蓋到該沖突遷移對；因此對復合依賴遷移對集合中的每個依賴對之間進行沖突判斷，若某對依賴對之間存在沖突，就將這對依賴對從依賴關系對集合中移除，最后剩下的非沖突依賴對組成復合非沖突依賴對集合；

測試路徑生成部分中利用深度優先遍歷的方法來生成滿足復合依賴關系覆蓋準則的測試路徑集，在路徑生成過程中，提出四條路徑生成規則，具體為：

路徑生成采用深度優先遍歷的算法，在算法中將滿足復合依賴關系覆蓋準則作為路徑生成的停止準則，提出四條路徑生成規則；

規則1：如果路徑中存在條件沖突，那這條路徑就不會被加入到路徑集合中；

規則2：在選擇后繼遷移時，選擇路徑中出現次數最少的后繼遷移加入路徑中；

規則3：對于非終止模型，對于控制陷落中的每個節點賦予一定的終止概率使其有可能在控制陷落中的任一節點終止；

規則4：對于控制依賴對，生成的測試路徑僅需覆蓋控制依賴對；對于數據依賴對，需要對路徑中具有數據依賴的兩個遷移之間的遷移進行變量分析，從而決定該數據依賴對能否被覆蓋。