NPC：基于深度神经网络决策逻辑的神经元路径覆盖

NPC：基于深度神经网络决策逻辑的神经元路径覆盖｜技术进展
2023-3-31 16:21:52 Author: mp.weixin.qq.com(查看原文) 阅读量:10 收藏

基本信息

原文名称 NPC: Neuron Path Coverage via Characterizing Decision Logic of Deep Neural Networks

原文作者 XIAOFEI XIE、TIANLIN LI、JIAN WANG、LEI MA、QING GUO、FELIX JUEFEI-XU、YANG LIU

原文链接 https://arxiv.org/abs/2203.12915

发表期刊 ACM Transactions on Software Engineering and Methodology (TOSEM), 2022

一、引言

深度学习在很多领域已经产生了诸多应用，如：图片分类、语音识别等。然而，在实际环境尤其是重要领域中，神经网络的性能和质量需要系统性地测试来验证。借鉴传统软件的经验，目前提出了多种结构化覆盖度量，以期衡量深度神经网络的充分性。可是由于神经网络天然的黑盒特性，这些现有的结构化度量缺少可解释性的原理支撑，且其于神经网络决策逻辑间的关系不明。此外，最近的研究揭露在结构化度量和神经网络缺陷检测能力之间不存在相关性，需要重新思考一个更合适的度量指标。

本文基于DNN决策逻辑提出了一种可解释性的度量指标。参考传统程序测试中的控制流图，本文基于DNN决策逻辑提取了决策图，决策图中的一条路径即代表DNN中的一种决策逻辑。同时，本文从控制流和数据流两个角度对DNN决策图进行分析，并提出了两种路径覆盖指标。路径覆盖率越高，探索到的DNN决策逻辑也就越多。通过大量实验证明：1.决策图中的路径可有效代表DNN中的决策逻辑。2.本文提出的覆盖度量可区分对抗样本集和自然样本集，且与输出公正性强相关。

二、概述

研究目标

本篇文章聚焦分类神经网络的测试，分类器为 $f:x\rightarrow y$ ， $X$ 是初始输入空间， $Y$ 是类别。

本文创新点

设计 Neuron Path Coverage-NPC，可解释性强、能够很好地体现DNN的决策结构。

基于Layer-Wise Relevance Propagation机器学习解释技术提取DNN中的关键决策路径(Critical Decision Paths-CDPS)，然后对CDP进行类内聚类和路径合并得到抽象路径Abstract CDP，依此构建DNN的决策图。

基于决策图，从控制流和数据流两个角度，提出了两种DNN决策图覆盖度量基于结构的覆盖（Structure-based Neuron Path Coverage-SNPC）、基于激活值的覆盖（Activation-based Neuron Path Coverage-ANPC）。路径指标之间的关系如下图1所示。

针对本文研究设计了综合且详细的实验方案，以评估所提出的关键路径、覆盖度量的有效性。

图1 路径指标关系图

三、本文详细工作

文章详细工作框架图如图2所示。其中各个部分的详细内容如下：

为每一个训练集中的样本提取CDP。提取出来的CDP代表模型学习到的决策逻辑。

对给定的初始输入，会计算初始输入提取的CDP 与之前在训练样本中提取的CDP 之间的距离，以此作为覆盖度量。

计算与所有样本的CDP之间的距离代价过大，为了提高效率，对训练样本的CDP进行聚类和抽象。具有相似决策逻辑的样本可能具有相似的CDP。对于具有相同类别的样本，将其CDP分为了k 簇，具有相似决策路径的样本会被聚类到同一个簇中。比如黄猫和黄猫、棕猫和棕猫。

对于簇中的CDP聚合为一个抽象CDP，这个抽象CDP就代表了该簇中所有样本的决策路径。

最终基于抽象CDP，提出了基于距离的覆盖度量，用来衡量测试在多大程度上覆盖了一个新的决策路径。具体来讲，首先会提取给定输入的抽象CDP；计算新的CDP和相应簇的抽象CDP之间相似性；考虑抽象CDP中神经元的激活值，并计算输入样本与簇中样本(沿CDP)激活向量之间的距离。最后，综合考虑相似度/距离，并且将相似度/距离分为 m个buckets，计算多少个buckets的得到了覆盖。

图2 本文工作总览图

四、 Layer-Wise Relevance Propagation

LRP 是一种机器学习解释性技术，为输入特征赋予不同的分数—相关性，该分数表明对应特征对模型最终预测结果的贡献度。基本的理念可以理解为要找出单个像素对图片分类结果的贡献度。详细的LRP计算过程可以阅读参考文献^[1]。

预测函数 $f(x)$ 可以被拆解为初始输入中各个维度相关性分数之和。其中 $R_d>0$ 说明该像素点对预测结果起到了正向作用，反之则起到了负面作用。然后可以将相关性分数做成热力图的方式，以体现出哪些像素位置对模型分类的结果起到了多大正向作用。假定分类器可以被拆解为不同网络层的计算。这些网络层可以是从图像中提取特征的部分，也可以是根据特征进行分类运算的部分。

（一）相关性分数的计算

具体来讲，分类器 $f$ 在类别 $y$ 上输出 $g_f(x)$ ，LRP按照如下公式1计算初始输入中各个维度的相关性分数：

其中 $R_i^{l_1}$ 代表层 $l_1$ 的输入的维度 $i$ 的相关性分数。相关性分数之和等于分类器 $f$ 在类别 $y$ 上的输出 $g_f(x)$ 。当 $R_i^{l_1}<0$ 时代表维度 $i$ 对模型预测结果起到了负向作用，反之则起到了正向作用。

各层之间的相关性分数可以通过层与层之间反向传播（从 $l_n$ 到 $l_1$ ）计算，如公式2所示。

其中 $R_i^l$ 即位于层 $l$ 的神经元 $i$ 的相关性分数。相关性分数的计算从输出层 $l_n$ 的神经元 $y$ 开始，一直到输入层 $l_1$ 的所有神经元。在每一层中，所有神经元相关性分数之和等于 $g_f(x)$ 。详细来讲，相关性分数可以通过如下公式3计算：

其中 $R_j^{(l_{m+1})}$ 代表在层 $l_{m+1}$ 的神经元 $j$ 的相关性分数， $R_{i\leftarrow j}^{(l_m,l_{m+1})}$ 代表层 $l_{m + 1}$ 神经元 $j$ 传递给层 $l_m$ 神经元 $i$ 的相关性分数，其中神经元 $i$ 的输出是神经元 $j$ 的输入。

下图3中展示了LRP的计算过程，左半部分分类器将图片识别为狗。为了解释为什么分类器将图片识别为狗，LRP从输出层开始计算相关性分数，最终输入层输入向量中的每一维度的相关性分数都可以被计算得出。图3中不同的颜色代表不同的相关性分数，红色越深的代表相关性分数越大。

图3 LRP总体概述图

五、关键决策路径 Critical Decision Path-CDP

根据 LRP 计算出来各层各个神经元的相关性分数，基于这些相关性分数，定义 $Critical Decision Path (CDP)$ 。CDP是关键神经元的集合(由在各层中相关性分数较大(大于设定阈值)的神经元组成)。

CDP定义：如公式4所示，初始输入 $x$ ，DNN $f$ 包含 $n$ 层。定义 $a-CDP$ 为神经元的集合 $p = < s_{1}{,s}_{2},\ldots{,s}_{n - 1} >$ ，其中 $s_i$ 是在层 $l$ 中有最大相关性分数的神经元的集合。 $a$ 负责控制每层挑选的神经元的个数，其值越小，挑选的神经元数目也就越少。

图4 关键路径示意图

如图4所示，黄色路径和红色路径分别代表猫和狗的决策路径。通过实验发现，相似的初始(都是猫)输入趋向于拥有相似的CDP而不同输入(一个是猫一个是狗)则拥有不同的CDP。

由于一层中可能出现多个关键神经元，会使用𝑎来控制挑选更为重要的，𝑎的值越小挑选的神经元的个数也就越少。没有被选为CDP的神经元被称为 Non-Critical-Decision Path(NCDP)。其中CDP 宽度 = 每层中被选为CDP神经元的比例

对于不同的输入，CDP宽度会不同，即使是拥有相同的参数a。

对于每一个输入而言，挑选的 CDP 需要对预测产生较大的影响，与此同时NCDP产生的影响要尽可能的小。只有宽度尽可能的小，CDP 才能精准的代表不同的决策逻辑。

实验证明，合适宽度的CDP可以更好地揭示不同的预测过程。即预测为同一类别的输入具有相似的CDP，反之则具有不同的CDP。

六、路径抽象

（一）聚类

Intra-Class Path Clustering，将所有神经元的状态组成一个向量，如果该神经元包含在CDP里面，标记为1，否则标记为0。然后使用𝐾-Means clustering把具有相同预测结果的CDP分为 $k$ 簇，如 $C_j^y$ （分类为 $y$ 的第 $j$ 簇）。

（二）路径聚合

对于每一个簇中的CDP，将采用路径聚合的方式聚合为一个抽象的CDP。用聚合后的抽象CDP来代表这个簇的决策逻辑。

具体来说，对于 $C_j^y$ （分类为 $y$ 的第 $j$ 簇），计算一个抽象CDP $\hat{p}=<\hat{s_1},\hat{s_2},...,\hat{s_{n-1}}>$ 。通过合并CDP中每一层中包含的神经元： $\forall i\in{\{1,...,n-1\}}:\hat{S_i}=U_{x\in{C_j^y}}S_i^x$ 对于每一个神经元 $t\in\hat{S_i}$ ，可以这样计算权重：

$w_t=\frac{\lvert\{x|x\in C_j^y\wedge t\in s_i^x\} \rvert}{\lvert C_j^y\rvert}$ , $s_i^x$ 是输入 $x$ 对应CDP的第 $i$ 层神经元的集合。这里 $w_t$ 的值为包含神经元 $t$ 的CDP所占的比例。

$w_t$ 的值越大，认为该神经元越重要。因此，又提出了参数 $\beta$ 来筛选高于阈值的神经元，抽象CDP 即变为了 ${\hat{p}}_{\beta} = < {\hat{s}}_{1,\beta},{\hat{s}}_{2,\beta},\ldots,{\hat{s}}_{n - 1,\beta} >$ ，其中 ${~~\hat{s}}_{i,\beta} = \left\{ t \middle| {t \in \hat{s}~ \land ~w_{t} >\beta} \right\}$ 。

（三）决策图

定义分类器 $f$ 决策图 $G$ 为抽象CDP的集合 $G = \left\{ {~\left( {{\hat{p}}_{\beta}^{1,1},\ldots,{\hat{p}}_{\beta}^{1,k}} \right),\ldots,\left( {{\hat{p}}_{\beta}^{n,1},\ldots,{\hat{p}}_{\beta}^{n,k}} \right)} \right\}$ ，其中 $n$ 是总的分类数， $k$ 是每个类别聚类的簇数， $\hat p_\beta^{i,j}$ 代表 $i$ 类的第 $j$ 簇所聚合的抽象CDP。

七、 神经元路径覆盖

从控制流角度：基于结构的神经元路径覆盖Structure-based Neuron Path Coverage SNPC

从数据流角度：基于激活值的神经元路径覆盖Activation-based Neuron Path Coverage ANPC

（一）基于结构的神经元路径覆盖

Structure-based Neuron Path Coverage SNPC

假设输入 $x$ 对应的CDP为 $p_{x}$ ，首先要根据预测的结果 $f(x)$ 来判断 $x$ 所对应的簇。 $G_{f(x)} = \left\{ {{\hat{p}}_{\beta}^{f{(x)},1},\ldots,{\hat{p}}_{\beta}^{f{(x)},k}} \right\}$ 是分类器 $f$ 对应的决策图。

计算 ${~p}_{x}$ 与 $G_{f(x)}$ 中各个抽象路径的相似度，来代表输入 $x$ 与现有抽象CDP之间的差异。

将相似度分为多个 buckets，计算覆盖了多少个buckets ---覆盖率。

具体来讲，现在有两个路径 $p_{x}$ 和 $\hat{p}$ ，一层一层的计算相似度。对于层 $l$ 来讲，相似度为： $~~J_{p_{x}^{l},{\hat{p}}_{~}^{l}} = ~\frac{s_{l}^{x} \cap ~{{\hat{s}}_{l}}_{~}^{~}}{s_{l}^{x}\bigcup{{\hat{s}}_{l}}_{~}^{~}}$ ，其中 $s_{l}^{x}$ 和 ${{\hat{s}}_{l}}_{~}^{~}$ 是 $p_{x}$ 和 $p$ 中第 $l$ 层的神经元。

然后把整个相似度的空间分为 $m$ 个相等的buckets。 $B = \left\{ {b_{1},\ldots,b_{m}} \right\}$ 对于输入 $x$ 和抽象CDP $\hat{p}$ 来讲，第 $l$ 层覆盖的bucket为

对于一个给定的测试集来讲，其 $Structure - based~Neuron~Path~Coverage$ 的定义如图5所示：

图5 SNPC计算公式

SNPC越高，就意味着DNN中更多的逻辑被探索到了。然而SNPC只考虑了控制流，对于某些样本来讲可能还是过于粗糙。为了更精细化，又提出了数据流角度考虑的基于激活值的神经元路径覆盖Activation-based Neuron Path 。

（二）基于激活值的神经元路径覆盖

Activation−based Neuron Path Coverage ANPC

考虑抽象CDP神经元的输出值，然后计算两个CDP输出值组成的向量之间的距离。

将距离分为m个buckets，计算覆盖了多少个buckets---覆盖率。

给定了一个输入 $x$ 和一个簇 $j$ ，首先挑选簇 $j$ 中距离 $x$ 最近的样本，也就是跟 $x$ 有最大相似度的样本 $x^{'}$ 。

计算 $x$ 的CDP 和 $x^{'}$ 对应的抽象CDP输出值组成的向量之间的距离。距离越大，输入 $x$ 探索的不同决策逻辑也就越多。

对于输入 $x$ 来讲，用 $A\left( x,{\hat{p}}^{l} \right)$ 来代表抽象路径 $\hat{p}~$ 第 $l$ 层中激活神经元的输出值组成的向量。那么在第 $l$ 层，输入 $x$ 和 $x^{'}$ 的距离被定义为：

引进一个上界 $U$ ，将距离空间 $\lbrack 0,U\rbrack$ 分为m个buckets： $B = \left\{ {b_{1},\ldots,b_{m}} \right\}$ 。对于输入 $x$ 和抽象CDP $\hat{p}$ 来讲，第 $l$ 层覆盖的bucket为

对于一个测试集，基于激活值的神经元路径覆盖Activation-based Neuron Path Coverage的定义如下图6所示：

图6 ANPC计算公式

从定义上看，SNPC是根据路径相似度计算的距离，而ANPC是通过神经元的激活值计算的距离。

八、实验部分

（一）CDP是否体现DNN决策

实验方法

通过消除掉CDP中神经元的值，观察预测结果是否发生改变。

两个预期

当CDP中神经元的值被消除时，预测结果发生极大的改变。

当NCDP中神经元的值被消除时，预测结果受到的影响程度很小。

评价指标

inconsistency rate: $\frac{\left\{ x \middle| x \in X~{\bigwedge~}~f(x)~ \neq {~f}_{m}(x) \right\}}{|X|}$

X是整个测试集； $f(x)$ 是模型 $f$ 正常分类的结果；

$f_{m}(x)$ 是消除CDP或者NCDP中神经元的值后，模型 $f$ 的预测结果。

表1 消除CDP和NCDP中神经元后的平均宽度和不一致率

𝛼 的值越小，每层中被挑选为CDP的神经元的数目也就越少。

Inc.C 是消除CDP中神经元后的不一致性。

Inc.NC是消除NCDP中神经元后的不一致性

表2 消除CDP中不同权重比例的神经元后的平均不一致率

此外本文还考虑到了Width的影响。Width代表的每层神经元中被挑选为CDP的平均比例。

表3 类内和类间CDP的平均相似度

Intra 是同类中CDP的平均相似度。

Inter 是类间CDP的平均相似度。

随着width的增加，平均相似度也在增加，如果CDP太宽了，会导致两个输入之间的差异性减少。如果CDP太窄了，可能会遗漏掉一些重要神经元。

结论

CDP在模型的预测过程中起到了关键作用，而NCDP没有。CDP跟模型内部的决策逻辑高度相关。

（二）路径抽象的有效性

和第一个实验类似，同样将抽象CDP/NCDP中的神经元消除，然后观察inconsistency的变化。

对于每一个包含一组训练样本𝑋的聚类，可以根据𝑋的所有CDP计算出它的抽象CDP。为了评估路径抽象的精度，对于每个输入𝑥∈𝑋，我们消除了相同的抽象CDP中的神经元，并评估平均不一致率。

路径抽象的效果接近于不抽象的效果，且可以减少大量计算量。

表4 消除抽象CDP和抽象NCDP中神经元后的平均宽度和不一致率

Inc.C 是消除抽象CDP中神经元后的不一致性。K是分类的簇数

Inc.NC是消除抽象NCDP中神经元后的不一致性。 𝛽 神经元的权重阈值

同一类的样本可能具有不同的决策逻辑，通过路径抽象，可以区分这些差异。

表5 聚类/不聚类的平均相似度

#Clus 是聚类的簇总数

#Intra_Cla 同一类别中CDP的平均相似度，没有聚类

#Inter_Cla 不同类别中CDP的平均相似度，没有聚类

#Intra_Clus 相同簇中CDP的平均相似度

#Inter_Clus 同一类中不同簇的CDP的平均相似度

结论

通过聚合每一个簇中的CDP，抽象CDP对于预测过程依然具有重要作用。此外，抽象CDP可以区分不同决策逻辑，在同一个簇中的输入有相似的决策路径，在同一类的不同簇中有不同的决策行为。

（三）缺陷检测的敏感程度

样本集构建

任意挑选1000个在测试集中的良性样本，将其中相同的部分按照相同大小替代为自然错误的样本，或者对抗样本。

错误率设置为1%，2%， 3%， 5%， 7%， 10%

评价指标

对于每一个测试集𝑠∈𝑆，计算它的覆盖范围改变与最初的测试集S0相比，关于覆盖准则𝐶𝑜𝑣,即Δ={𝐶𝑜𝑣(𝑠)−𝐶𝑜𝑣(𝑠0)|𝑠∈𝑆}。对于每一个𝑠∈𝑆，将覆盖率的变化归一化如下:

Baseline

• Neuron Coverage (NC）

• 𝑘-Multisection Neuron Coverage (KMNC)

• Neuron Boundary Coverage (NBC)

• Likelihood-based Surprise Coverage (LSC)

• Distance-based Surprise Coverage (DSC)

• Importance-Driven Coverage (IDC)

当引入更多的错误的时候，覆盖率总体呈增加趋势。

图7 覆盖率变化图

结论

总的来说，ANPC和SNPC对不同的错误比其他覆盖标准更敏感。不同的覆盖标准可以达到相似的增长趋势，说明它们之间存在一定的相关性。

（四）NPC是否与输出公正性相关？

随意挑选了两个不同大小 size 100/500 的种子测试集。

基于这两个种子测试集，采用了Fabrice Harel-Canada等人^[2]的方法，产生了一些新的样本加入到测试集中。

对于测试集，计算覆盖率与输出公正性之间的关联性-皮尔逊积矩相关系数。

计算输出公正性。

表6 覆盖度量和输出公正性的相关性

结论

总体而言，ANPC和SNPC与输出公正性呈正相关。模型和测试集的大小会影响相关性。

（五）NPC的效率问题

因为提取训练集的CDP和抽象CDP可以离线操作，所以只比较了计算覆盖率的部分。总体而言SNPC和ANPC的计算开销大于其他对比指标，但计算开销总体在可接受范围内。

表7 时间开销

九、总结

本文设计 Neuron Path Coverage-NPC，可解释性强、能够很好地体现DNN的决策结构。基于Layer-Wise Relevance Propagation机器学习解释技术提取DNN中的关键决策路径(Critical Decision Paths-CDPS)，然后对CDP进行类内聚类和路径合并得到抽象路径Abstract CDP，依此构建DNN的决策图。然后根据基于决策图，从控制流和数据流两个角度，提出了两种DNN决策图覆盖度量Structure-based Neuron Path Coverage-SNPC、Activation-based Neuron Path Coverage-ANPC，并针对本文研究设计了综合且详细的实验方案，以评估所提出的关键路径、覆盖度量的有效性。思路总结如图8所示：

图8 本文思路总结

参考文献

[1]

S. Bach, A. Binder, G. Montavon, F. Klauschen, K.-R. Müller, and W. Samek, “On Pixel-Wise Explanations for Non-Linear Classifier Decisions by Layer-Wise Relevance Propagation,” PLoS ONE, vol. 10, no. 7, p. e0130140, Jul. 2015, doi: 10.1371/journal.pone.0130140.

[2]

Fabrice Harel-Canada, Lingxiao Wang, Muhammad Ali Gulzar, Quanquan Gu, and Miryung Kim. 2020. Is Neuron Coverage a Meaningful Measure for Testing Deep Neural Networks?. In Proceedings of the 28th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ACM.

[3]

T. Li, J. Wang, L. Ma, Q. Guo, F. Juefei-Xu, and Y. Liu, “NPC: Neuron Path Coverage via Characterizing Decision Logic of Deep Neural Networks.” arXiv, Mar. 26, 2022. Accessed: Mar. 06, 2023. [Online]. Available: http://arxiv.org/abs/2203.12915

[4]

Y. Liu, P. Yang, P. Jia, Z. He, and H. Luo, “MalFuzz: Coverage-guided fuzzing on deep learning-based malware classification model,” PLoS ONE, vol. 17, no. 9, p. e0273804, Sep. 2022, doi: 10.1371/journal.pone.0273804.

文章来源: https://mp.weixin.qq.com/s?__biz=MzU1NTEzODc3MQ==&mid=2247485116&idx=1&sn=bead9147accf9135b20a99e4af97ef73&chksm=fbd9ad00ccae2416bb20dd11e1dfbb8a684b057e860234eb600e9bb89b8baf3b2ff813839316&scene=58&subscene=0#rd
如有侵权请联系:admin#unsafe.sh