DeepCruiser: Automated Guided Testing for Stateful Deep Learning Systems

简介

论文标题

• DeepCruiser: Automated Guided Testing for Stateful Deep Learning Systems
• DeepCruiser：有状态深度学习系统的自动引导测试
• 2018.12

贡献

• 我们将有状态DL系统形式化为MDP(马尔可夫决策过程)，它能够刻画基于RNN的有状态DL系统的内部状态和动态行为。
• 基于MDP抽象，我们设计了一套专门针对有状态DL系统的测试准则，包括两个状态级准则和三个转换级准则。这是专门为RNN设计的第一组测试标准。
• 我们评估了这些准则在实际ASR应用中的有效性，并证实更精确的抽象可以更好地区分不同的测试序列，生成的测试有助于提高覆盖率，有助于缺陷检测。
• 我们实现了一个覆盖率导向的测试框架DeepCruiser。作为基于音频的DL系统的第一个测试框架，我们还根据背景噪声、音量变化等真实场景的启发，设计了一组针对音频输入的变形变换。实验结果表明，DeepCruiser在生成高覆盖率测试和发现实际ASR系统缺陷方面是有效的。

Automated Speech Recognition (ASR):自动语音识别

1. 将RNN系统对状态和转移同时进行抽象成为一个状态转移模型,这里使用的是MDP模型

2.对转移后的模型定义覆盖标准,这里有两个状态级准则和三个转换级准则

3.对模型应用定义的覆盖标准实施fuzz测试

摘要

深度学习(DL)定义了一种数据驱动的编程范例，该范例根据训练数据自动组成系统决策逻辑。伴随着过去十年的数据爆炸和硬件加速，DL在许多前沿应用中取得了巨大的成功。然而，即使是最先进的DL系统也仍然存在质量和可靠性问题。直到最近，前馈DL系统的测试才取得了一些初步进展，与前馈DL系统相比，递归神经网络(RNN)遵循了一种截然不同的结构设计，通过回路和内部状态实现了时间行为和“记忆”。RNN的这种有状态特性有助于它成功地处理音频、自然语言和视频处理等顺序输入，但也对质量保证提出了新的挑战。

在本文中，我们开始了测试基于RNN的有状态DL系统的第一步。我们将RNN建模为一个抽象的状态转换系统，并在此基础上定义了一套专门用于有状态DL系统的测试覆盖准则。此外，我们还提出了一个自动化测试框架DeepCruiser，它系统地生成大规模的测试，以发现覆盖指导下的有状态DL系统的缺陷。我们在一个最先进的语音到文本DL系统上的深入评估表明，我们的技术在提高有状态DL系统的质量和可靠性方面是有效的。

背景

RNN

与前馈DL系统(如CNN)不同，递归神经网络(RNNs)通过环路实现时间行为，并通过内部状态记忆来考虑过去(或未来)观测的影响。RNN的状态化特性使其在处理顺序输入方面取得了巨大的优势和成功，并使其在当前的音频、自然语言和视频处理等工业应用中占据主导地位，对我们的日常生活产生了巨大的影响。RNN体系结构的简化版本如图1所示。基本RNN是组织成连续迭代(或循环)的神经元状节点的网络。它将待处理的数据流和维护的内部状态向量都作为输入。RNN不是将输入数据作为一个整体来处理，而是在数据到达时处理一小块数据，并在每次迭代时按顺序产生输出并更新状态向量。对于每个单独的输入序列，首先将状态向量初始化为S0(通常是零向量)，并且将来自前一迭代的状态向量传递到下一迭代。在高层，状态向量序列可以被视为记录RNN的底层时间动态的轨迹，从而为网络的整体特征提供见证。

随着回路的设计，RNN上的“消失梯度问题”[29]变得更加严重，其中用于训练反向传播的梯度可能会消失到零，或者随着迭代次数的增加而变得非常大，从而导致模型难以优化。长短期记忆(LSTM)[30]和门控循环单元(GRU)[31]就是为了克服这个问题而设计的。它们的网络结构比图1所示的基本RNN复杂得多，但它们都共享RNN设计的简单基本原则，并实现了用于记忆的状态向量。

Automated Speech Recognition

图2展示了端到端ASR系统的一般工作流程，其中分别突出显示了培训和预测过程。这两个过程共享相同的特征提取模块，其中将原始音频转换为数字特征(例如，梅尔倒谱系数(MFCC)特征)。在训练阶段，特征向量和文本转录被直接馈送到基于RNN的模型中，跳过用于语音分析的声学模型。在预测方面，该流水线由特征提取模块、基于RNN的翻译模块和基于语言模型的校正模块三个主要部分组成。通常，语言模型是从外部提供的，不需要培训。首先将音频转换为数字特征向量，然后将其传递给DNN模型以获得初始转录，该初始转录可由语言模型进一步细化或校正。例如，在图2中，字符序列中的拼写错误很容易纠正。

覆盖率制导的测试框架DeepCruiser综述

图3总结了我们方法的工作流程，包括RNN的抽象模型构建，在RNN模型上定义的覆盖标准，以及生成RNN缺陷和漏洞检测测试的覆盖指导的自动化测试框架。

抽象模型构建模块将训练好的RNN作为输入，通过剖析分析其内部运行时行为。分析的质量在很大程度上取决于使用的输入数据。分析输入的理想选择是训练数据(或其中的一部分)，它们最能反映训练的RNN模型的内部动态。具体地说，对每个输入序列进行简档以导出轨迹，即RNN序列状态向量。在分析了所有提供的输入之后，我们将获得一组跟踪，这些跟踪描述RNN访问的主要状态和采取的转换。

在实践中，RNN的内部状态空间和训练数据支持的踪迹数量往往超出了我们的分析能力。因此，我们对状态和轨迹进行抽象，得到一个能够反映训练网络全局特征的抽象模型。在状态层面，我们应用主成分分析(PCA)[34]来降低向量的维数，并保留前k个主要成分。对于k个维度中的每一个，我们进一步将它们划分成m个相等的间隔。在转换层，我们根据状态抽象将具体的转换合并为抽象的转换。我们还考虑了不同输入下不同转换的频率，有效地导出了训练后的RNN的马尔可夫决策过程(MDP)[35]模型。

在抽象模型的基础上，设计了五个覆盖准则，以便于RNN的系统测试

两个state-level coverage criteria

• basic state coverage (BSCov)
• k-step state boundary coverage (k-SBCov)

三个transition-level criteria

• basic transition coverage (BTCov)
• input space coverage (ISCov)
• weighted input coverage (WICov)

测试框架的设计目的是利用上述标准来促进基于RNN的系统的缺陷发现。使用选定的覆盖标准，测试过程从一组初始种子(实际ASR测试场景下的一些音频)开始，即种子库。然后，在每一次迭代中，我们基于启发式算法选择一个音频，并通过应用一定的变换从它生成一个突变体。如果产生的突变体触发了一些缺陷，例如，转录显示与预期有很大的差异，那么它就被标记为失败的测试。否则，我们检查突变体是否相对于所选标准提高了测试覆盖率，如果是，则将其包括在种子池中。

递归神经网络的状态转移建模

RNN模型本质上是有状态的[36]。在这一部分中，我们形式化RNN的内部状态和状态转换，并描述用于捕获训练的RNN模型的全局特征的抽象模型。

RNN内部状态和状态转换

在[37]的基础上，我们将神经网络抽象地表示为一个可微的参数化函数$f(\cdot) .$f(⋅).。RNN的输入是序列$\mathbf{x} \in \mathcal{X}^{N},$x∈XN, 其中$\mathcal{X}$X是输入域，$N$N是序列的长度。设$x_{i} \in \mathcal{X}$xi​∈X是该序列的第i个元素。然后，当将$x$x传递到RNN中时，它保持状态向量$s \in \mathcal{S}^{N}$s∈SN，其中$s_{0}=0$s0​=0 并且$\left(s_{i+1}, y_{i}\right)=f\left(s_{i}, x_{i}\right),$(si+1​,yi​)=f(si​,xi​),，其中S是隐藏状态的域，$s_{i} \in \mathcal{S}$si​∈S 是RNN在第i次迭代时的隐藏状态，并且 $y_{i} \in \mathcal{O}$yi​∈O是在该步骤的对应输出。我们用$s_{i}^{d}$sid​来表示状态向量 $s_{i}$si​的d维。

自然，每个输入序列$x$x 诱导有限的状态转换序列$t$t ，我们将其定义为 trace。迹$t$t中的第i个元素(由 $t_{i},$ti​,表示)是在接受输入$x_{i}$xi​并产生输出 $y_{i}$yi​ 之后从$s_{i}$si​ 到$s_{i+1}$si+1​的过渡。有限状态换能器(FST)[38]可用于更紧凑地表示轨迹集合[39]，如下所定义。

定义1.Fst是一个元组(S，X，O，I，F，δ)，使得S是非空的有限状态集合，X是输入字母表，O是输出字母表，I⊆S是初始状态集，F⊆S是最终状态集，δ⊆S×X×O×S是转换关系。

例如，图4示出表示两个轨迹的简单FST，即$s0s1s2s3$s0s1s2s3和$s0s1s2's3$s0s1s2′s3，其中s0是初始状态，s3是最终状态。第一道采用输入序列x0x1x2并发出输出序列y0y1y2；第二道采用输入序列$x_{0} x_{1}^{\prime} x_{2}$x0​x1′​x2​并发出输出序列$y_{0} y_{1}^{\prime} y_{2}$y0​y1′​y2​。

抽象状态转换模型

训练RNN时启用的状态和轨迹的数量可能很大。为了有效地捕捉大量输入序列所触发的行为，更好地捕捉训练网络的全局特征，本文引入了一种抽象的状态转移模型。抽象模型过度逼近RNN的观测轨迹，与原始模型相比，状态和跃迁的集合要少得多。抽象也是可配置的-可以在模型的大小和精度之间进行折衷，以便抽象模型仍然能够维护特定分析任务的输入序列的有用信息。为了得到训练后的RNN的抽象模型，我们同时对状态和转换进行抽象。

状态抽象。每个当前状态$s_{i}$si​被表示为一个向量$\left(s_{i}^{1}, \ldots, s_{i}^{m}\right)$(si1​,…,sim​)，通常是高维的(即，m可以是很大的数字)。直观地说，抽象状态代表了一组在空间上接近的具体状态。为了获得这样的状态抽象，我们首先应用主成分分析(PCA)[34]对具体的状态进行正交变换-找到最能区分给定状态向量的前k个主成分(即轴)，而忽略它们在其他成分上的差异。这有效地将所有具体状态投影到所选择的k维分量基上。

然后，我们将新的k维空间分成$m^{k}$mk个规则网格[40]，使得每个轴上有m个等长的区间：其中$e_{i}^{d}$eid​表示d维上的第i个区间，$l b_{d}$lbd​和$u b_{d}$ubd​分别表示d维上所有状态向量的下界和上界。这样，落入同一网格的所有具体状态$s_{i}$si​ 被映射到相同的抽象状态：$\hat{s}=\left\{s_{i} | s_{i}^{1} \in e_{-}^{1} \wedge \cdots \wedge s_{i}^{k} \in e_{-}^{k}\right\} .$s^={si​∣si1​∈e−1​∧⋯∧sik​∈e−k​}.。我们将所有抽象状态的集合表示为$\hat{\mathcal{S}}$S^。值得注意的是，状态抽象的精度可以很容易地通过调整参数k和m来配置。

状态s_i是每个维度的第i个状态值所组成的向量,状态向量有m个,每个有k维

想象成一个矩阵,有m列,k行,这个就是一列

k相当于降维,m相当于离散化,本质上是为了减少计算

设$j=I^{d}(\hat{s})$j=Id(s^) 是在d维上 $\hat{s}$s^ 的索引 使得对于所有$s \in \hat{s}, s^{d}$s∈s^,sd 落在 $e_{j}^{d}(0 \leq j<m) .$ejd​(0≤j<m).对于任意两个抽象状态 $\hat{s}$s^ 和 $\hat{s}^{\prime},$s^′, 我们将它们的距离定义为:
$\operatorname{Dist}\left(\hat{s}, \hat{s}^{\prime}\right)=\Sigma_{d=1}^{k}\left|I^{d}(\hat{s})-I^{d}\left(\hat{s}^{\prime}\right)\right|$Dist(s^,s^′)=Σd=1k​∣∣​Id(s^)−Id(s^′)∣∣​
这个定义也可以推广到包括超出上下限的空间。

就是两列状态向量,逐对计算状态下标的差值并求和,记作距离

转换抽象。一旦计算出状态抽象，就可以将两个具体状态之间的具体转换映射为抽象转换的一部分。抽象转换表示一组共享相同源和目标抽象状态的具体转换,换句话说，在两个抽象状态$\hat{s}$s^和$\hat{s}^{\prime}$s^′之间存在抽象转换当且仅当$s$s和$s^{\prime}$s′ 之间存在具体转换，使得$s \in \hat{s} \wedge s^{\prime} \in \hat{s}^{\prime}$s∈s^∧s′∈s^′ 所有抽象转移的集合表示为$\hat{\delta} \subseteq \hat{\mathcal{S}} \times \hat{\mathcal{S}}$δ^⊆S^×S^。

例如，图5a描绘了三条具体轨迹，即t1、t2和t3，其中状态被示为点，而转换是连接点的有向边。以虚线绘制的网格表示抽象状态，即$\hat{s}_{0}, \hat{s}_{1}, \hat{s}_{2},$s^0​,s^1​,s^2​, 和 $\hat{s}_{3},$s^3​,，每个状态都映射到相应网格内的一组具体状态。因此，抽象转换集是$\left\{\left(\hat{s}_{0}, \hat{s}_{1}\right),\left(\hat{s}_{1}, \hat{s}_{0}\right),\left(\hat{s}_{1}, \hat{s}_{1}\right),\left(\hat{s}_{1}, \hat{s}_{2}\right),\left(\hat{s}_{1}, \hat{s}_{3}\right),\left(\hat{s}_{3}, \hat{s}_{3}\right)\right\}${(s^0​,s^1​),(s^1​,s^0​),(s^1​,s^1​),(s^1​,s^2​),(s^1​,s^3​),(s^3​,s^3​)}。

原本的转换是线,抽象转换是格子,比如抽象s0->s1,就看s0格子中有没有点连接到s1格子中的点

将训练好的RNN表示为马尔可夫决策过程

训练集中的每个输入序列产生RNN模型的具体踪迹。抽象状态转换模型捕获从训练数据(或其代表性部分)启用的所有具体轨迹以及尚未启用的其他潜在轨迹。由于状态和转换抽象的定义方式，所得到的抽象模型表示训练的RNN模型的观察行为的过度近似和泛化。

为了考虑不同输入下抽象转移的可能性，我们用转移概率和非确定性选择来扩充抽象模型，有效地使其成为一个无成本的马尔可夫决策过程(MDP)[35]。

定义2.MDP是元组$(\hat{\mathcal{S}}, I, \hat{\mathcal{T}}),$(S^,I,T^),其中$\hat{\mathcal{S}}$S^是抽象状态集合，I是初始状态集合，$\hat{\mathcal{T}}: \hat{\mathcal{S}} \times \hat{\mathcal{X}} \mapsto \operatorname{Dist}(\hat{\mathcal{S}})$T^:S^×X^↦Dist(S^)是转移概率函数，使得$\hat{\mathcal{X}}$X^表示(抽象)输入空间，Dist( $\hat{\mathcal{S}}$S^ )是抽象状态集合上的离散概率分布集合。

状态$\hat{s}$s^处的选择空间由在该状态下启用的一组输入$\hat{\mathcal{X}}(\hat{s})$X^(s^)给出，其抽象方式与状态相同。我们写$\operatorname{Pr}_{\hat{x}}\left(\hat{s}, \hat{s}^{\prime}\right)$Prx^​(s^,s^′)来表示在给定具有输入 $\hat{x}$x^的当前状态 $\hat{s}$s^ 的情况下访问 $\hat{s}^{\prime}$s^′ 的条件概率，使得$\Sigma_{\hat{s}^{\prime} \in \hat{\mathcal{S}}} \operatorname{Pr}_{\hat{x}}\left(\hat{s}, \hat{s}^{\prime}\right)=1$Σs^′∈S^​Prx^​(s^,s^′)=1。我们将转移概率定义为在给定输入$\hat{x}$x^从$\hat{s}$s^ 到 $\hat{s}^{\prime}$s^′ 的所有传出具体转移的数目,即

类似于HMM中的状态转移矩阵,并以频率估计概率
$\operatorname{Pr}_{\hat{x}}\left(\hat{s}, \hat{s}^{\prime}\right)=\frac{\left|\left\{\left(s, s^{\prime}, x\right) | s \in \hat{s} \wedge x \in \hat{x} \wedge s^{\prime} \in \hat{s}^{\prime}\right\}\right|}{\left|\left\{\left(s,_{-}, x\right) | s \in \hat{s} \wedge x \in \hat{x}\right\}\right|}$Prx^​(s^,s^′)=∣{(s,−​,x)∣s∈s^∧x∈x^}∣∣{(s,s′,x)∣s∈s^∧x∈x^∧s′∈s^′}∣​
例如，图5b将图5a中的具体跟踪的抽象状态转换模型显示为MDP。抽象转换用它们的转换概率进行标记。例如，由于$\hat{s}_{0}$s^0​ 处的所有传出转换在$\hat{s}_{1}$s^1​中结束，因此从$\hat{s}_{0}$s^0​到$\hat{s}_{1}$s^1​的转换概率为1。$\hat{s}_{1}$s^1​有两种输入选择，即$\hat{\mathcal{X}}\left(\hat{s}_{1}\right)=$X^(s^1​)=$\left\{\hat{x}, \hat{x}^{\prime}\right\} .${x^,x^′}.当 $\hat{s}_{1}$s^1​ 处的给定输入为$\hat{x}$x^,时，转移概率计算为$\operatorname{Pr}_{\hat{x}}\left(\hat{s}_{1}, \hat{s}_{2}\right)=\frac{1}{2}$Prx^​(s^1​,s^2​)=21​ 和 $\operatorname{Pr}_{\hat{x}}\left(\hat{s}_{1}, \hat{s}_{3}\right)=\frac{1}{2}$Prx^​(s^1​,s^3​)=21​。当输入为$\hat{x}^{\prime}$x^′ 时，计算类似。

如示例所示，通过首先将状态和转移抽象应用于一组具体轨迹，然后计算每个抽象状态下每个输入的转移概率分布，来构建MDP模型。抽象步骤的时间复杂度取决于具体踪迹的数量，而计算转移概率的复杂度仅取决于抽象转移的数量。

有状态递归神经网络的覆盖准则

受传统软件测试的启发，提出了一套基于抽象状态转移模型的RNNs测试覆盖准则。RNN复盖标准的目标是测量测试数据在执行已训练行为和未见行为时的完整性和彻底性。状态和转换抽象被设计为分别反映特定时间点的内部网络配置以及网络随时间的时间行为。因此，为了最大限度地发现有状态神经网络中的缺陷，应该结合基于状态抽象和转移抽象的覆盖标准来系统地生成全面和多样化的测试用例集。

设$M=(\hat{\mathcal{S}}, I, \hat{\mathcal{T}})$M=(S^,I,T^) 是表示为mdp的训练后的rnn的抽象模型。设$T=\left\{\mathbf{x}_{0}, \ldots, \mathbf{x}_{n}\right\}$T={x0​,…,xn​} 是一组测试输入序列。我们定义了T的状态级state-level和转换级transition-level覆盖，以衡量T分别对M的状态和转换进行了多广泛的操作。

State-Level Coverage Criteria

状态覆盖标准侧重于RNN的内部状态。抽象状态集$\hat{\mathcal{S}}$S^表示从训练数据(或其代表部分)获得的访问状态的空间泛化，其被称为主功能区域[19]。测试数据应广泛覆盖主要功能区域，以验证训练的行为，并充分覆盖角例区域，以发现看不见的行为中的缺陷

Basic State Coverage。在给定RNN抽象模型M和一组测试输入T的情况下，基本状态覆盖度量T在训练时访问的主要功能区域的覆盖程度。为了量化这一点，我们比较了训练输入和测试输入访问的抽象状态集，分别由$\hat{\mathcal{S}}_{M}$S^M​ 和 $\hat{\mathcal{S}}_{T}$S^T​表示。然后，基本状态覆盖由训练和测试输入访问的抽象状态的数量相对于训练输入访问的状态的数量给出：
$\operatorname{BSCov}(T, M)=\frac{\left|\hat{\mathcal{S}}_{T} \cap \hat{\mathcal{S}}_{M}\right|}{\left|\hat{\mathcal{S}}_{M}\right|}$BSCov(T,M)=∣∣∣​S^M​∣∣∣​∣∣∣​S^T​∩S^M​∣∣∣​​
k-Step State Boundary Coverage 测试数据还可以触发在训练期间从未访问过的新状态。k步状态边界覆盖衡量角例区域被测试输入T覆盖的情况。角例区域 $\hat{\mathcal{S}}_{M^{c}}$S^Mc​是$\hat{\mathcal{S}}_{M}$S^M​之外的抽象状态的集合，其与$\hat{\mathcal{S}}_{M}$S^M​中的任何状态的距离都不为零。然后，可以将 $\hat{\mathcal{S}}_{M^{c}}$S^Mc​形状记忆中心进一步划分为不同的边界区域，这些边界区域由它们到 $\hat{\mathcal{S}}_{M^{c}}形$S^Mc​形状记忆中心的距离来定义。例如，k步边界区域$\hat{\mathcal{S}}_{M^{c}}(k)$S^Mc​(k)包含与$\hat{\mathcal{S}}_{M},$S^M​,具有最小距离k的所有抽象状态，或者更正式地，$\hat{\mathcal{S}}_{M^{c}}(k)=\left\{\hat{s} \in \hat{\mathcal{S}}_{M^{c}} | \min _{\hat{s}^{\prime} \in \hat{\mathcal{S}}_{M}} \operatorname{Dist}\left(\hat{s}, \hat{s}^{\prime}\right)=k\right\}$S^Mc​(k)={s^∈S^Mc​∣mins^′∈S^M​​Dist(s^,s^′)=k}

k-Step State Boundary Coverage被定义为测试输入在距离$\hat{\mathcal{S}}_{M}$S^M​至多k步的边界区域中访问的状态的比率：
$k \text { -SBCOV }(T, M)=\frac{\left|\hat{\mathcal{S}}_{T} \cap \bigcup_{i=1}^{k} \hat{\mathcal{S}}_{M^{c}}(i)\right|}{\left|\bigcup_{i=1}^{k} \hat{\mathcal{S}}_{M^{c}}(i)\right|}$k -SBCOV (T,M)=∣∣∣​⋃i=1k​S^Mc​(i)∣∣∣​∣∣∣​S^T​∩⋃i=1k​S^Mc​(i)∣∣∣​​
没出现在训练集的状态向量叫做边角区域,边角区域的向量和训练集向量的最小距离为k

Transition-Level Coverage Criteria

状态级覆盖指示RNN的内部状态被执行的程度，但它不反映在连续时间步中状态之间发生转换的不同方式。转换层复盖标准针对的是由不同输入序列**的抽象转换，较高的转换复盖率表明，输入更足以触发不同的时间动态行为。

Basic Transition Coverage 为了量化转换覆盖率，我们比较了在训练和测试阶段进行的抽象转换，分别写为$\hat{\delta}_{M} \text { 和 } \hat{\delta}_{T}$δ^M​ 和 δ^T​。然后，通过以下方式给出基本过渡覆盖范围：
$\mathrm{BTCov}(T, M)=\frac{\left|\hat{\delta}_{T} \cap \hat{\delta}_{M}\right|}{\left|\hat{\delta}_{M}\right|}$BTCov(T,M)=∣∣∣​δ^M​∣∣∣​∣∣∣​δ^T​∩δ^M​∣∣∣​​
basic transition coverage 包括basic state coverage。换言之，对于任何抽象模型M，每个测试输入T满足关于M的基本转换覆盖，也满足基本状态覆盖。

Input Space Coverage

抽象状态$\hat{s}$s^处的输入空间被给出为$\hat{\mathcal{X}}_{\hat{s}}$X^s^​，其表示在训练时在$\hat{s}$s^处接受的抽象输入的集合.测试输入尽可能覆盖每个状态的输入空间，以练习不同的后续转换.更正式地说，假设$\hat{s}$s^处的训练和测试数据的输入空间分别为$\hat{\mathcal{X}}_{M}(\hat{s})$X^M​(s^)和$\hat{\mathcal{X}}_{T}(\hat{s})$X^T​(s^)。则输入空间覆盖率定义为：
$\operatorname{ISCOV}(T, M)=\frac{\sum_{\hat{s} \in \hat{\mathcal{S}}_{T} \cap \hat{\mathcal{S}}_{M}}\left|\hat{\mathcal{X}}_{T}(\hat{s})\right|}{\sum_{\hat{s} \in \hat{\mathcal{S}}_{M}}\left|\hat{\mathcal{X}}_{M}(\hat{s})\right|}$ISCOV(T,M)=∑s^∈S^M​​∣∣∣​X^M​(s^)∣∣∣​∑s^∈S^T​∩S^M​​∣∣∣​X^T​(s^)∣∣∣​​
请注意，输入空间覆盖与基本转换覆盖是不可比的-实现输入覆盖不能保证转换覆盖，反之亦然。

每个状态对应的输入的个数

Weighted Input Coverage

我们的抽象模型还编码了给定特定输入(在训练期间观察到)的不同转换的频率。越频繁触发的转移具有更高的转移概率，这由转移概率函数$\hat{\mathcal{T}}$T^给出。加权输入覆盖不仅考虑某一状态下的不同选择，而且还考虑在选择特定输入时可能的后续转换的范围。更正式地说，它被定义为：

加权输入覆盖率强于基本转移覆盖率和输入空间覆盖率。

覆盖率制导的测试框架

在本节中，我们将介绍覆盖率指导的测试框架。我们首先描述了一组专门针对音频信号的变形变换(6.1节)，然后提出了一种基于突变的测试生成算法，该算法以第5节提出的覆盖标准为指导。

音频信号的变形变换

ASR执行从音频语音到相应自然语言文本的一般转换，通常被期望对具有不同音量、速度和语音特征的语音进行适当的工作。此外，这些语音音频信号可能与来自环境声音而不是绝缘良好的接收器的噪声混合。受这些实际场景的启发，我们推导出了一组模拟环境干扰的变换算子。总括而言，它们可分为四类：

• Volume-related transformations (VRT): ChangeV olume, LowPassFilter, HighPassFil-
  ter.
• Speed-related transformations (SRT): PitchShift, ChangeSpeed.
• Clearness-related transformations (CRT): AddWhiteNoise, ExtractHarmonic
• Unaffected transformations (UAT): DRC, Trim.

类别VRT、SRT和CRT分别影响音频信号的音量、速度和清晰度；而类别UAT包含既不影响它们，但仍对语音信号进行微小改变的变换。表1对转换进行了总结，并进行了简要描述

对于缺陷检测，我们的目标是生成人类听起来正常但被ASR错误转录的音频。通过不同的变换集合，可以对音频进行变异以生成新的音频，其中可能有一个会在训练的网络中触发新的踪迹，并导致ASR中的潜在缺陷。然而，具有显著扰动的剧烈变换可能导致即使是人类也无法识别的音频。例如，音量可能会变得太低或频率可能会变得太高。为了生成合适的缺陷触发候选，我们应用有约束的转换，以确保音频种子和相应的突变体对人类来说听起来是相同的。满足上述要求的变换算子称为保持变形关系[41]，我们称它们为变形变换。现在，我们提出了一种策略来执行DeepCruiser所做的转换，同时最大限度地保留其转换前后的音频文本信息

一般来说，音量、速度和清晰度变换在单独应用并控制在一定程度上时，不会对音频语义产生影响。然而，当音频输入a0用一系列变换(例如，a0、→a1、.。。。，→ai)，则音频由于累积失真而不能被人类很好地识别的可能性较高。我们提出了一种策略来保守地选择用于在转换前后产生人类无法区分的缺陷候选的转换：

(1)我们仔细设置参数以确保单步变换(关于音量、速度或清晰度)不违反变形关系(即，人的听觉不受影响)；以及

(2)通过变换序列T之后的种子突变而产生的音频被限制为通过变换$t \in S \cup U A T$t∈S∪UAT进行突变，使得$(\{t\} \cup S) \cap T=\emptyset$({t}∪S)∩T=∅，其中$S \in\{V R, S R T, C R T\}$S∈{VR,SRT,CRT}。直观地说，这些约束确保通过最多一次改变种子输入的音量、速度或清晰度来产生突变体。如果不满足此约束，则不会进一步转换音频

覆盖率制导的测试

算法1给出了测试具有各种可配置反馈的基于RNN的DL系统的一般步骤。DeepCruiser的输入包括初始种子I和基于RNN的深度学习系统R，输出是覆盖率较高的回归测试和未正确处理的失败测试。初始测试队列仅包含初始种子。对于每一次，DeepCruiser从测试队列中选择一个输入a(即语音音频)。基于已经选择的a的变换，DeepCruiser随机选取一个变换t(c.f.。第6.1节)。如果在变形关系约束下不允许选择进一步的转换(即，t=NULL)，DeepCruiser将从队列中选择下一个输入。对于拾取的变换t，随机参数被拾取。DeepCruiser将生成转换为t的新音频a0，并与深度学习系统R进行转换，如果预测结果与原始种子不一致，则会将a0添加到失败的测试中。对于ASR中的音频，我们通过检查单词/字符错误率(W/CER)是否超过某个阈值来判定测试失败。如果变异的测试不是失败的测试，并且增加了总体覆盖率，DeepCruiser会将其添加到测试队列中，并更新测试队列中的测试覆盖率。

评估

RQ1：当处理不同的输入时，抽象模型能区分RNN的内部行为吗？不同抽象配置的区别有多精确？

RQ2：建议的标准与RNN的错误行为之间有关联吗？

RQ3：DeepCruiser在生成高覆盖率测试方面有多有效？

RQ4：在基于RNN的ASR系统中，DeepCruiser对缺陷检测有多大用处？

Datasets. DeepSpeech-0.3.0

RQ1：抽象模型精度评估

为了量化两个输入之间的相似度，我们采用了Jaccard指数来度量它们的覆盖相似度。
$\mathrm{J}_{\mathrm{M}}(x, y)=\frac{\left|\hat{\mathcal{S}}_{x} \cap \hat{\mathcal{S}}_{y}\right|}{\left|\hat{\mathcal{S}}_{x} \cup \hat{\mathcal{S}}_{y}\right|}$JM​(x,y)=∣∣∣​S^x​∪S^y​∣∣∣​∣∣∣​S^x​∩S^y​∣∣∣​​

RQ2：测试标准与RNN错误行为之间的相关性

一般来说，相对WER较高的测试用例往往具有较低的Jaccard指数，这意味着它们与原始种子输入的相似度较低。抽象模型越细粒度，这种现象就越明显。直观地说，通过增加状态覆盖率，我们可以生成更多具有较低Jaccard指数的数据。因此，试图增加状态的覆盖提供了更多的可能性来检测RNN的更多错误行为。

RQ3：DeepCruiser提高覆盖范围的有效性

RQ4：错误行为检测

相关工作

DNN测试 常见覆盖准则更适合前馈神经网络结构，即使它们通过展开部分适用于RNN。文献[23]中报告的实验结果表明，神经元覆盖在CNN上有效，但在RNN上用于指导测试用例生成时，效果并不理想。这表明RNN不是简单的CNN折叠，现有的标准可能不太适合RNN。目前，还缺乏专门为RNN设计的定制测试标准，能够捕捉RNN的状态性，衡量测试工作的彻底性。

RNN的抽象。为了理解RNN的内部动力学，已经提出了许多方法来建模RNN，通常是以有限状态自动机(FSA)的形式。FSA显式地表示内部状态转换，因此可以用来解释嵌入在RNN中的底层决策规则。在这一意义上，MDP具有类似的属性，并且它还捕获不同输入下的状态转移分布，使其成为更精确的模型。从RNN构造FSA需要两个步骤：(1)实值数值向量上的状态空间划分；(2)基于划分的自动机构造。目前已经提出了各种划分策略和自动机构造算法。Omlin和Giles[53]提出将状态向量的每个维度划分为相等的间隔，从而将状态空间划分为规则网格。非监督分类算法也被应用于状态空间划分。例如，在[54-56]中研究了k-均值及其变体。Weiss等人。[24]设计了一种动态创建分区的算法，其中采用一个带有RBF核的支持向量机分类器来将多个状态向量从原始分区中分离出来。最近的研究[24，55，56]更多地集中在LSTM和GRU上，表明同样的抽象技术也适用于RNN变体。当应用于包括自然语言处理和语音识别在内的真实任务时，训练的RNN模型的状态空间可能非常大。这使得可伸缩性成为k-means和内核算法等分区技术的问题。因此，我们采用了便宜得多的区间抽象法，而且我们还可以从它在精度调整方面的灵活性中获益。

24.G. Weiss, Y . Goldberg, and E. Yahav, “Extracting automata from recurrent neural networks
using queries and counterexamples,” arXiv preprint arXiv:1711.09576, 2017.

53.C. W. Omlin and C. L. Giles, “Extraction of rules from discrete-time recurrent neural networks,”
Neural networks, vol. 9, no. 1, pp. 41–52, 1996.

54.A. L. Cechin, D. R. P . Simon, and K. Stertz, “State Automata Extraction from Recurrent
Neural Nets Using k-Means and Fuzzy Clustering,” in Proceedings of the XXIII International
Conference of the Chilean Computer Science Society, 2003, p. 73.

55.Q. Wang, K. Zhang, A. G. Ororbia, II, X. Xing, X. Liu, and C. L. Giles,
“An empirical evaluation of rule extraction from recurrent neural networks,” Neural
Comput., vol. 30, no. 9, pp. 2568–2591, Sep. 2018. [Online]. Available: https:
//doi-org.ezlibproxy1.ntu.edu.sg/10.1162/neco_a_01111

56.B.-J. Hou and Z.-H. Zhou, “Learning with Interpretable Structure from RNN,” oct 2018.
[Online]. Available: http://arxiv.org/abs/1810.10708