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

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

径能否触发崩溃. 特别的, 为了辅助进行高效环路搜索, 我们结合安卓系统的生命周期管理机制、操作步骤间的依
赖关系对环路进行了不同重要性的标记, 这些重要性将会直接影响它们被选择的先后次序.
但本文中实现方法为局部最优, 约减后的测试序列符合当前粒度抽象构建的程序执行状态跳转图最短路径,
但并非触发程序崩溃绝对最短路径, 当抽象粒度越精细, 此粒度上的状态跳转图更能区分细微操作带来的影响, 这
是在约减序列长度与约减时间的平衡, 我们将是否继续约减至绝对最优以及粒度抽象层次的选择权交给开发者.

3.1 状态跳转图构建
i
,
给定测试序列 T = {e 0 ,e 1 ,...,e i ,...,e n } e i 代表测试序列中的第 个测试事件. 为了对测试序列执行过程中程序
V 为节点集合, 每个
状态的变化进行准确表示, 我们为每个测试序列构建了状态跳转图, 其定义为 G = (V,E) , 其中
节点代表一个应用界面状态, E = {e 0 ,e 1 ,...,e i ,...e n } 为边集合. 状态跳转图中的节点之间可以存在多条边, 并且会
存在环. 在测试序列执行过程中, 我们在每个测试事件后插入监测事件以获得待测应用界面信息, 并通过对界面信
息进行差异分析决定是否有新的节点产生. 在本文中, 我们关注的界面信息包括控件粒度以及页面布局粒度, 在控
件粒度上我们关注页面上控件及其内容、属性的所有变化, 而在页面布局粒度上我们则只关注界面布局结构但忽
略控件具体内容.
v t , 起始节点对应的是待测应用的启动界面, 终止节点则代表
状态跳转图包含了一个起始节点 v s 与终止节点
了程序崩溃状态界面. 给定一个判定函数 test , 我们有 test(T) = X 代表测试序列 T 触发了程序崩溃, 则我们的目标
′ ′ ′ ′ v s 与终止
就变成了寻找状态跳转图中的路径 T , 其满足: 1) T ⊆ T , 即 T 为 T 的子测试序列; 2) T 联通起始节点
′ ′′ ′′ ′ ′′
节点 v t ; 3) 触发程序崩溃, 即 test(T ) = X ; 4) 不存在路径 T 满足 T ⊆ T , 且 test(T ) = X .
此外, 以 Monkey 为代表的自动化测试工具中会有很多随机事件产生, 这些随机事情很多时候并不能真正作
用在页面有效控件上, 针对这一点, 在构建状态跳转图过程中, 我们也即时进行无效事件约减. 在本文中, 我们定义
无效事件为对测试状态转化不产生任何影响的事件, 比如在页面空白区域的点击事件等.

3.2 环路检测

′
在状态跳转图中寻找路径 T 的最直观的做法是直接搜索起始节点 v initial 与终止节点 v crash 之间的最短路径 T s ,
T s 并不能触发程序崩溃, 例如图 1 中序列 e 47 返回事件并没有导致应用程序界面发生
但很多情况下最短路径 (a),
任何变化, 序列 (b) 中 e 113 到 e 115 虽然使得应用程序界面发生了改变, 但这种改变没有在最短路径 T s 上体现出来.
应用设置的改变仅体现在其所在的子路径上, 并没有在最短路径所在的主干路径上体现. 换句话说, 最短路径
T s 无法触发程序崩溃是因为其缺失了某些环路. 在本文中, 我们定义 T s 为平凡最短路径, 我们的目标则是寻找满
足第 3.1 节中给出的 4 个条件的最短路径 T .
′
在本文中, 我们提出了时序一致的最长环路检测算法, 其会在状态跳转图中寻找所有以最短路径 T s 中的节点
T s 中并验证是否
为起止点的环路. 这些检测到的环路在后续测试路径搜索算法中将会作为输入集, 依次被合并到
可以正确触发程序崩溃. 我们的环路检测算法有如下两个特点.
v 上可能存在多条环路, 它们之间的执行顺序直接影响测试程序崩溃与否, 例
1) 事件执行顺序一致性: 在节点
如先有环路对应用程序某内部设置 (例如 language settings) 进行修改, 然后后续环路进行了这些设置影响到的某
些操作, 在它们的共同作用下, 应用程序崩溃. 如果没有对测试序列中的原本执行顺序进行保持, 则无法成功复现
这些崩溃错误;
2) 最长环路检测: 由于环路内容可能还存在一条甚至多条子环路, 若对其依次进行检测并验证是否可触发程
序崩溃, 其平均效率为 O(n) . 我们在检测环路时采用最长环路策略, 在此基础上, 后续测试路径搜索时可以采用二
分方法对最长环路进行迭代验证, 将平均搜索效率降低到 O(log(n)) .
其具体思路如算法 1 所示. 给定状态跳转图 G 、起始节点 v initial 到终止节点 v crash 间的最短路径 T s , 函数
T s 上经过的所有节点, 并检测出所有以此节点为起止状态的所有环路. 为了保持原测试
findLoops 将会遍历路径
start 与第 1 条出
序列中的事件执行顺序, 在检测每个节点上的环路时, 我们获得此节点最后一条入边的事件编号
边的事件编号 end (第 5–8 行), 仅对它们之间的事件进行环路检测. 函数 findNodeLoops 负责检测节点 v 上的所有