Page 113 - 《软件学报》2025年第5期

郝蕊 等: 基于事件标记的多粒度结合安卓测试序列约减 2013

′ ′
15. T ← T s + reduce( G,T base ,L );
changes
′
16. return T ;
level ← level +1; // 此重要性层次空间内, 未能搜索到最短测试路径
′
′
17.
18. continue;
L,level ); // 获取当前重要性层次上的所有环路
′
19. L changes ← filterLoops(
20. L ′ ← L ′ + ddmin( T base ,L changes ,2 ); // 对当前重要性层次上的所有环路进行约减
changes changes
′ ′
21. T base ← T s + filterLoopsGreaterThan( L,level ) +L ;
changes
′ test(T base ) = X then
22. if level = IMPORTANT and
′ ′ ); // 成功搜索到最短路径
23. T ← T s + reduce( G,T base ,L
changes
′
24. return T ;
′
′
25. level ← level +1;
G.longestPath; // 路径搜索失败, 返回原测试路径
26. return
算法 2 中第 8–25 行代码在重要性层次 level 上对环路集 L 进行约减, 其中变量 level 指示当前搜索重要性层
′
′
次, 变量 L ′ 保存了所有更低重要性的已经约减成功的必要环路, 函数 filterLoopsGreaterThan( L,level ) 则返回
changes
′
所有更高重要性的环路, 这两种环路在当前层次 level 上无需进行约减. 在进行约减时, 算法首先生成所有可保持
原样的环路集合, 其由平凡最短路径 T s 、更高层次环路、低层次必要环路组成, 定义为基础测试路径 (第 11 行),
′
若此基础测试路径无法正确触发程序崩溃, 则说明当前层次环路中存在必要环路, 算法将获取重要性为 level 的所
有环路进行约减 (由函数 ddmin 完成), 并将约减后的结果更新到 L ′ 中, 然后进行下一层次的搜索 (第 19–
changes
25 行). 若此基础测试路径可正确触发程序崩溃, 则说明当前层次环路均为冗余环路, 此时我们进一步对将所有更
高重要性层次的环路也去除并检测能否正确触发程序崩溃, 如果可以, 则说明所有更高层次的环路也均为冗余环
路, 可直接将目前获得的最短路径返回 (第 12–16 行), 否则, 继续进行下一层次的搜索 (第 17, 18 行).
算法 3 中的函数 ddmin( T base ,L,k ) 利用分治策略 [15] 对环路集 L 进行约减 (第 1–13 行), 前提为 test(T base ) , X
L 后可以触发. 其约减的基本思路
但 test(T base + L) = X , 即基础测试路径 T base 无法触发程序崩溃, 但合并上环路集
i 份子环路集可以成功触发程序崩溃, 则将其作为函数 ddmin 的输
为将环路集 L 均分为 k 份依次进行验证, 假设第
入继续进行分治 (第 4–7 行), 若第 i 份子环路集均无法触发程序崩溃, 则对它的补集进行验证、分治 (第 8–10 行).
若划分后所有子环路集、子环路补集均无法触发程序崩溃, 则增大划分粒度后继续约减, 直至粒度超过环路集 L
中包含的环路数量或环路集 L 中包含环路数量过少无法划分.
算法 3. 环路分治约减.
1. Function ddmin( T base ,L,k )
L.size = 1 then // 无法进行约减, 直接返回
2. if L.size = 0 or
3. return L;
4. for i in [0,k) do
5. L ∆i ← calPartition( L,i ; // 获取 L 的 k 均分后的第 i 个子环路集
)
6. if test(T base + L ∆i ) = X then
T base ,L ∆i ,2 ; // 对子环路集继续约减
7. return ddmin( )
8. L ∇i ← L − calPartition( L,i ; // 获取第 i 个子环路集补集
)
test(T base + L ∇i ) = X then
9. if
10. return ddmin( T base ,L ∇i ,max(k −1,2) ; // 对子环路集补集继续约减
)
11. if k < L.size then