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

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

end 之间的所有出边与入边, 这里我们还需保证入边事件一定发生在出边
环路, 其首先选取节点 v 上落在 start 、
事件之前, 才能检测到环路 (第 14–16 行). 接下来, 依次遍历出边集 E out 与入边集 E in , 得到事件对 (e out ,e in ) , 即可得
到由 e out 到 e in 之间的所有事件组成的最长环路.
算法 1. 环路检测.

G,T s )
1. Function findLoops(
L ← ∅; //待返回的结果环路集合
2.
3. for each event e on path T s do
e 的源节点
4. v s ← e.source; // 事件
5. start ← 0;
v s , v initial then
6. if
7. start ← v s .lastIncomingEvent.id; //获取源节点的入边集中的最大 id
8. end ← e.id;
v s 作为起始及终止节点的环路
9. L v s ← findNodeLoops( G,v s , start,end ; // 检测以
)
10. insert all loops in L v s into L;
11. return L;
12. Function findNodeLoops( G,v, start,end )
L ← ∅; // 待返回的结果环路集合
13.
14. E out ← filter( G.outgoingEvents(v), start,end ; // 选取 id 在 [start,end] 之间的出边
)
15. start ← min( E out ; // 重新设定 start 为所有出边中的最小 id
)
[start,end] 之间的入边
16. E in ← filter( G.incomingEvents(v), start,end ; // 选取 id 在
)
17. for i in [0,E out .size) do // 此处 E out .size 不大于 E in .size
18. e out ← E out .item(i);
19. e in ← E in .item(i);
20. l ← {e k : e out .id ⩽ e k .id ⩽ e in .id}; // 环路 l 包含 e out 到 e in 之间的所有事件
21. insert l into L;
22. return L;

3.3 环路标记
状态跳转图中包含的环路有时候会达到几十甚至上百, 此外, 有时需要在多个环路的共同作用下程序崩溃才
会触发, 因此对所有环路及它们的组合进行验证是一项非常耗时的工作. 在本文中, 我们采用对标记环路重要性的
策略, 将与程序崩溃触发最有关联的环路单独进行标记, 并在后续最短测试路径搜索过程中采用由高到低的方式
依次对不同重要性环路进行搜索, 降低算法开销.
我们将环路分为 3 个层次: 重要环路 (IMPORTANT)、普通环路 (NORMAL)、次要环路 (MINOR). 一条环路的
优先级由此环路中所有事件的最高优先级决定. 其中次要事件主要是与应用逻辑无关的按键操作 (KeyEvent), 比
如调整设备声音大小、屏幕亮度.
在本文中, 我们关注 3 个方面的重要事件, 分别是执行环境改变事件、生命周期相关事件、数据流依赖相关
事件. 其中执行环境改变事件是指改变设备网络状态、位置服务状态、信号状态、电池状态、传感器数据设置
等, 这些事件可直接通过对测试脚本中事件格式解析的方式进行识别.
安卓系统通过返回栈机制管理不同应用的活动, 活动在入栈、出栈过程中伴随了一系列生命周期状态的变
化, 安卓组件需要在生命周期状态改变时调用不同回调函数来对布局、数据、资源进行妥善处理. 安卓中最常见
的 Activity 活动组件提供了 7 个与生命周期管理相关的回调函数, 例如活动创建、暂停、销毁、重启等, 而 Fragment