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

2014 软件学报 2025 年第 36 卷第 5 期

)
12. return ddmin( T base ,L,min(L.size,2k) ; // 增大划分粒度
13. return L changes ;
L 中的环路均为最长环路 (参见第 3.2 节), 对算法 2 中搜索到的必要环路, 我们还需对其进一
由于最初环路集
步约减以去除它上面存在的冗余子环路, 具体思路如算法 4 所示. 算法依次遍历环路集 L 中的所有环路, 并检测其
是否包含子环路, 若不包含子环路, 则直接返回 (第 4–6 行), 否则利用 reduceLoop 函数对其进一步约减 (第 7–9 行).
函数 reduceLoop 对环路 l 进行约减, 其利用 Dijkstra 最短路径算法获得环路 l 中的最短路径并进行验证, 若其可以
正确触发程序崩溃, 则将其视为约减结果返回 (第 14–16 行), 否则同样利用 ddmin 函数对环路 l 中存在的所有子环
路集进行分治约减 (第 17 行), 直至环路中不存在子环路 (第 12, 13 行) 或前后两次约减的结果相同 (第 18, 19 行).

算法 4. 环路内约减.

1. Function reduce( G,T base ,L )
′
2. L ← ∅; // 约减后的路径集
3. for path l in L do
4. if l doesn’t contain inner loop do
L ; // 当前环路无子环路, 无需约减
′
5. insert l into
6. continue;
′ T base + L−l,l ); // 对当前环路进行进一步约减
7. l ← reduceLoop(G,
′ ′ test 函数验证效率
8. replace l of L with l ; // 用约减后的路径 l 更新 L , 提升后续
′ L ;
′
9. insert l into
′
10. return L ;
11. Function reduceLoop( G,T base ,l )
12. if l doesn’t contain inner loop do
l; // 当前环路无子环路, 无需约减
13. return
14. l s ← shortestPath( l ); // 获取当前环路上起点到终止点之间的最短路径
test(T base +l s ) = X then
15. if
16. return l s ; // 当前环路约减成功, 返回
l ← l s +ddmin(T base +l s ,findLoops(G,l s ),2); // 检测当前环路中的所有子环路集, 并对其进行约减
′
17.
′
18. if l .length = l.length then
l ; // 当前环路已经约减成功, 返回
′
19. return
′
20. return reduceLoop( G,T base ,l ); // 对环路进行迭代约减
值得说明的是, 安卓测试序列执行非常耗时, 而在约减算法中则会反复对中间搜索到的测试路径进行执行以
便验证是否可触发程序崩溃, 因此, 在算法实现过程中, 我们还进行了中间测试结果的缓存, 包括每次进行验证的
路径及其验证结果, 避免了相同路径的多次执行, 提升搜索效率.
此外, 以上说明的是在控件粒度上的测试路径搜索, 对于页面布局结构粒度的测试路径搜索, 由于其输入数
据 (即控件粒度约减后的测试序列) 已经体现了测试事件标记优先级的作用, 因此, 我们仅进行了简单的环路分治
约减 (算法 3 中 ddmin 函数) 及环路内约减 (算法 4 中 reduce 函数).

4 实验分析

4.1 实验数据
为了获取测试数据, 我们采用与 Monkey 相同的随机测试策略, Monkey 是安卓系统内部提供的测试工具, 被很