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

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

(a) e 47
e 39

e 38
e 48
...
e 1 e 37
s 1 s 5
e 40
e 46 ...
s 0 s 6 s 7
... e 115
(b) e 1 e 5
e 112
e 111
s 7
s 6
e 6 e 7 e 114
s 2 ...
e 116
...
e 123
e 113
s 0 s 1 s 8 s 9 s 10
e 124
图 1 应用 LibreNews 崩溃测试序列

3 方法设计

本文提出了一种基于事件标记的测试序列多粒度约减方法 TREC, 我们将测试序列约减看作满足触发程序崩
溃这个约束条件的最短路径搜索问题, 通过对事件优先级进行标记、在不同粒度上分层次约减等手段不断缩小搜
索空间, 从而提升搜索效率. 方法框架如图 2 所示, 我们首先对程序状态进行细粒度上的抽象, 区分程序控件的细
微变化, 这有利于我们利用相对少的时间对测试序列进行粗略约减, 找到一条不那么短的但是可以触发程序崩溃
的测试序列, 然后我们将程序状态的抽象提升到仅仅考虑页面布局结构, 并对测试序列进一步约减. 在每个粒度的
约减流程中, 我们首先去除了不会对测试界面及程序逻辑产生任何效果的无效事件, 然后构建程序执行过程中的
状态跳转图, 跳转图包含了一个起始节点 (程序启动状态) 与结束节点 (程序崩溃状态), 我们的问题也变成了在状
态跳转图中搜索连接起始节点和结束节点、并且可正确触发程序崩溃的最短路径.

状态跳转图构建 环路检测 环路标记 最短测试路径搜索
环境改变 环路间约减
໭效事件去除 平凡最短路径搜索
:sending Touch (ACTION_DOWN) ള命周期 数据依赖 环路内约减 :sending Touch (ACTION_DOWN)
:sending Touch (ACTION_UP) :sending Touch (ACTION_UP)
:sending Key (ACTION_DOWN) :sending Key (ACTION_DOWN)
:sending Key (ACTION_UP)
:sending Key (ACTION_UP)
:sending Touch (ACTION_DOWN) :sending Touch (ACTION_DOWN)
:sending Touch (ACTION_MOVE)
:sending Touch (ACTION_MOVE)
:sending Touch (ACTION_MOVE) :sending Touch (ACTION_MOVE)
:sending Touch (ACTION_UP)
:sending Touch (ACTION_UP)
:sending Touch (ACTION_DOWN) test(T)= :sending Touch (ACTION_DOWN)
:sending Touch (ACTION_UP)
:sending Touch (ACTION_UP) 2 2 MINOR
:sending Key (ACTION_DOWN) 2 2 :sending Key (ACTION_DOWN)
:sending Key (ACTION_UP) :sending Key (ACTION_UP)
:sending Touch (ACTION_DOWN) 环 :sending Touch (ACTION_DOWN)
:sending Touch (ACTION_MOVE) 1 1 最 1 1 测 :sending Touch (ACTION_MOVE)
:sending Touch (ACTION_MOVE) :sending Touch (ACTION_MOVE)
:sending Touch (ACTION_UP) 状 :sending Touch (ACTION_UP)
:sending Touch (ACTION_DOWN)
:sending Touch (ACTION_DOWN)
:sending Touch (ACTION_UP) 3 3 路 :sending Touch (ACTION_UP)
:sending Key (ACTION_DOWN)
:sending Key (ACTION_DOWN) 长 3 3 试
:sending Key (ACTION_UP) :sending Key (ACTION_UP)
:sending Touch (ACTION_DOWN)
:sending Touch (ACTION_DOWN) 态
:sending Touch (ACTION_MOVE) 6 5 6 5 6 5 重 6 5 :sending Touch (ACTION_MOVE)
:sending Touch (ACTION_MOVE)
:sending Touch (ACTION_MOVE)
:sending Touch (ACTION_UP) 4 跳 4 环 4 4 路 :sending Touch (ACTION_UP)
测试序列 7 8 转 7 8 路 7 8 要 7 8 径 约减后测试序列
性
图 检 NORMAL 标 搜
测 IMPORTANT 记 test(T)=X 索
图 2 测试序列约减框架图 ( 代表控件粒度上的约减流程, 代表页面布局粒度上的约减流程)

为了寻找满足上述条件的最短路径, 我们首先找出单纯连接起始节点和结束节点的平凡最短路径, 并对此路
径进行测试, 如果此路径能正确触发崩溃, 则认为我们找到了正确路径, 否则我们需要进一步搜索. 目前的路径无
法正确触发崩溃的原因是因为其遗漏了某些测试步骤没有执行, 因此, 我们首先对于目前路径上的每个节点, 寻找
以此节点为起始状态与结束状态的环路, 然后按照某些策略挑选环路并将其合并到目前的最短路径, 并测试新路