Generating Test Input with Deep Reinforcement Learning 论文笔记
摘要
Searchbased Software Testing (SBST)使用metaheuristic algorithms（元启发式算法）自动生成测试数据。元启发式算法是基于 fitness function返回值不断试错的方法，这与强化学习的过程很相似。本文研究在SBST中用rf的方法代替人工设计的元启发式算法，我们把被测软件（SUT）改写为强化学习环境。同时，我们提出了一种新型的SBST框架，它将SUT扩展到环境中。我们训练了一个double dqn ，研究发现我们的方法可以100%覆盖分支。
1. 引言
SBST在自动生成测试数据方面很有效，尤其是structural coverage,许多元启发式算法已经被应用，如hill climbing, simulated
annealing,evolutionary algorithms。
本文使用DDQN来对接收数字输入的分支预测进行训练和测试，这是rl第一次应用于SBST。
本文的贡献是：
（1）本文设计了GunPowder，这个平台既能运行待测程序（software under test），也能用适应度函数（fitness value）按照给定的结构测试标准计算结果。
（2）用rl的算法代替了人工设计的元启发式算法，并进行了一个小的研究验证了本文的方法
2.背景知识
2.1 强化学习
介绍了MDP，Q-learning，DQN
本文使用了Double DQN (DDQN)
2.2 GunPowder
对一般插桩（instrumentation）和分析的要求如下：
（1）插入SUT根据结构测试标准测量
（2）根据生成出的input运行SUT
（3）计算fitness value
本文提出的GunPowder是一个针对C语言的通用测试数据生成的框架，用python编写
2.2.1 框架
Gunpowder包含三部分：instrumentation, execution, and ftness evaluation
instrumentation使用Clang front-end from LLVM framework
2.2.2 Fitness Function
方法级别 A ，分支距离 ∆，当SUT中的一个node被运行时，一条轨迹记录
被存入 T(X)
，其中p是一系列被运行的node，Ci是node的谓词
当运行SUT时，GunPowder也分析控制结构。根据分析，我们可以得到任何目标分支的期望运行路径。通过比较实际运行的轨迹T和期望轨迹
，然后计算有多少个node没有出现在T中，这个数量被赋予给方法级别A的输入X。同时发散的node
可以通过比较T和
得出。轨迹记录
中的
被赋值到输入 X的分支距离∆。A和∆的结合被当做fitness value返回。
3. QTIP--使用Q-learning生成测试数据
3.1 把SBST转化成rf问题
3.1.1 状态和动作
t时刻的状态：，
是t时刻的输入向量，在每个时刻，agent提供一个候选的输入向量。
对输入向量X，定义动作空间：
其中是输入向量X的第i个元素，因为对于输入向量中的每一个元素本文定义了两种操作，所以动作空间是输入向量长度的两倍。
作为可行性研究，本文将输入限制为数字。但是本文认为输入扩展为其他的格式也是可以的。
3.1.2 部分可观测性
上述设计中有一个固有的限制：agent只能观测到搜索轨迹的部分。例如爬上算法中，有一个小的记忆机制，能够存储之前的fitness value。但是本文的agent不能获得之前的state.本文假设搜索轨迹的信息能够提高agent的表现。
为了验证这个假设，本文提出了一个替代设计：包含了部分观测的fitness value。t时刻的观测如下：
m是记忆的大小，即窗口大小。我们训练了一个窗口大小是200和一个不含窗口的agent，具体记过见5.4.
3.1.3 奖励
SBST和本文的目标都是最小化fitness value。当agent降低fitness value时本文奖励agent。在t时刻奖励是：
其中
3.2 GunPowder的OpenAi Gym兼容性
GunPowder实现了OpenAi Env中的reset和step。
在QTIP环境中，step方法执行对应于当前输入向量的给定动作的操作。随后，它使用修改过的输入运行SUT并计算fitness value。如果agent使用完了所有的budgets或者覆盖了目标分支，episode结束。
4. 实验
4.1 研究问题
本文尝试回答以下问题：
（1）有效性：Qtip agent平均的结构覆盖率是多少？
（2）未见过的结构：agent能覆盖训练时未见过的结构吗？
（3）未见过的输入范围：agent能覆盖训练时未见过的输入范围吗？
4.2 训练
我们使用DDQN算法来训练QTip来覆盖基本的二元关系运算符，=，！=，<，<=，>，> >，以及一元逻辑否定 ！我们的训练程序包含一系列的if，每个if 含有一个关系操作符，所有的分支都不嵌套，因此approach level A接近0。目标函数接收2个int参数，，范围是【-128,128】
在每个episode，随机选择一个分支，agent的action预算是2000
4.3 神经网络结构
3个全连接层，4个**层
更新网络的速度是
使用Adam优化算法，batch的大小是32，学习速率是：，
4.4 Subjects
本文的训练函数是分支不嵌套且包含基本的谓词，训练后使用GCD（最大公因数）EXP（指数）和IGUANA中的Remainder
5. 结果
5.1 有效性
我们计算每100episode agent覆盖分支的数量，训练了5700个episode，用时5h44min
我们比较了agent和随机搜索的有效性，两者都能覆盖分支，但是agent尝试的次数更多
5.2 未见过的结构
选择了三个函数，尝试了30次，平均能66%的分支覆盖率，不如随机搜索好。
人工检测发现所有未覆盖的分支都是嵌套分支，因为训练时没有这样的情况，所有approach level A一直是0。我们希望在未来利用这个部分
5.3 未见过的输入范围
加大了数据输入的范围，结果基本一致
5.4 状态窗口
加入了200的窗口后比较很有效果
6. THREATS TO VALIDITY
内部有效性的威胁包含工具使用的证确性，keras-rl GunPowder
外部威胁包含：实验规模
7. 相关工作
Search based test data generation早年已经有了很多研究