Automated Identification of Libraries from Vulnerability Data

Automated Identification of Libraries from Vulnerability Data

本篇文章于2020年发表在CCF推荐A类会议ICSE（International Conference on Software Engineering）上，作者是来自Veracode的杨辰、安德鲁·桑托萨等人和来自新加坡管理大学的大卫洛夫。

introduction Software Composition Analysis (SCA)

1. 开源库对现代信息基础设施至关重要，现代信息基础设施严重依赖于使用开源依赖编写的软件。 例如：项目管理工具Maven的中央仓库、最大的软件注册表工具Npm，以及Python Package Index即PyPI，Python Package的索引，你需要的Python package基本上都可以从这里找到 然而，与任何软件一样，开源库可能包含安全漏洞。软件成分分析(SCA)自动识别应用程序中使用的依赖项的漏洞版本，以便开发人员可以放心地继续使用开源库。SCA也因而受到了广泛的关注。
2. 如图所示：典型的SCA工作流，SCA通过将检测到的应用程序依赖项与漏洞数据库进行匹配，帮助开发人员发现其应用程序中存在漏洞的库。
   

National Vulnerability Database (NVD)

SCA重要地涉及到一个漏洞监管过程，在这个过程中，安全研究人员用来自不同来源的数据填充漏洞数据库，与此工作最相关的的就是美国国家漏洞数据库（NVD）的数据源。每个NVD条目都包含以下的信息：

1. 唯一的通用漏洞枚举(CVE)标识号，即CVE ids
2. 漏洞描述
3. 对咨询，解决方案和工具的reference
4. 通用平台枚举配置(CPE)，每个CPE配置都是标识一组CPE名称的正则表达式。每个名称依次标识与漏洞相关的信息技术系统、软件或软件包。

Problem

但是，NVD条目里所提供的信息，可能无法明确识别易受攻击的库，如下面例子所述：

1. CVE-2015-7318：该漏洞包含在Plone内容管理系统的Zope2 Python库中，但是，Zope2在文本中以及原始NVD记录中均没有提及。
   
2. CVE-2011-0448：尽管Ruby on Rails活动记录库存在该漏洞，但文本数据和NVD记录中都没有提到它。
   
3. 因此，在SCA漏洞监管过程中，SCA安全研究人员面临的关键挑战是从这些数据中找出哪些库与NVD报告的每个漏洞相关。

The work done in this paper

1. 使用机器学习来计算任何给定CVE id的相关库名的自动预测系统，主要实现了： N V D → P ( L ) NVD rightarrow mathcal{P}(L) NVD→P(L)的功能。

• 这里NVD是NVD中CVE id的集合
• P ( L ) mathcal{P}(L) P(L)是识别库库名的集合

2. 作者为了训练这个机器学习模型，收集了来自NVD的训练数据，并从多年来由安全研究人员手动管理的SCA漏洞数据库中获得了数千条NVD漏洞记录及其库名。机器学习任务本质上是一种极端的多标签文本分类(XMTC)，通常被称为极端的多标签学习(XML)。对于训练和预测，使用的是FastXML算法。
3. 这里简而言之：就是应用FastXML方法将漏洞数据映射到SCA漏洞数据库的具体库名。解决的问题是将一个查询的漏洞与一个库相关联，而这个库的名称在数据中可能甚至没有被提及。
4. 这个系统已经部署在Veracode，作为一个更大的系统的一部分，该系统帮助安全研究人员识别web数据项与漏洞相关的可能性。预测工具被打包为一个web服务，其中的输入是给定CVE id的漏洞描述、其CPE配置及其引用，它用库名的分级列表来响应输入，列表中的每个库名都有一个分数。根据分数，我们可以选择前k个库名。研究人员可以通过网络用户界面获得预测结果，如图所示。
   

Background Software Composition Analysis Vulnerability Curation System

1. 软件成分分析漏洞检测系统（其数据流图(DFD)如下所示）

• 系统的核心是一套预测数据项是否与漏洞相关的堆叠集成模型
• 系统以迭代方式执行，在每次迭代中使用更多和更新的输入数据，每月训练新模型
  • 每次迭代输入系统的数据源包括我们最先介绍的NVD，以及Jira、Bugzilla报告、Github问题、PR和提交，以及电子邮件。
• 首先对互联网上的数据进行清洗，然后在特征提取和选择过程后，利用已有的生产模型对输入数据进行预测，以确定每个数据项是否与漏洞相关。
• 预测的结果将交给安全研究人员团队做出最终决定，从而在SCA漏洞数据库中产生新的条目。然后，新条目用于训练和验证新模型，以便在下一次迭代的生产中使用。
• 基于机器学习的漏洞监控系统的数据流图(DFD)。该系统迭代地改进预测模型，将安全研究人员的标记作为唯一的人工任务。
  

XML and FastXML

1. XML：XML(自然语言处理中的XMTC)是对具有多个标签的输入数据进行分类的问题。（极端多标签学习）其目的是学习一个分类器，该分类器可以从一个非常大的标签集中自动识别出最相关的数据点。

• 先前所提的问题在这里可以看做是XML的一个实例
• XML与普通的多标签学习(ML)不同，因为XML的标签数量非常多
• XML也不同于多类分类，多类分类的目标是用单个标签来标记每个数据项

2. XML任务目前主要的挑战

• 严重的数据稀疏性：大多数标签只有很少的训练实例，这使得很难可靠地学习标签之间的依赖模式。
• 计算成本：独立多类分类器的训练和测试(即，二元相关性(BR)方法)的成本都是令人望而却步的，因为标签的数量很大，可能达到数百万。

3. 主流的XML分类算法

• 嵌入方法：执行压缩以降低标签向量空间的维度。这类方法有WSABIE、SLEEC、AnnexML。虽然根据公开测试来看，SLEEC在LSHTC4（LSHTC4是使用维基百科数据集进行文本分类的大规模基准测试）上的性能优于作者所用的FastXML算法，但是在基于嵌入的方法中，模型的训练成本可能很高，即使对于小的嵌入维度，预测也可能很慢，因为它需要将预测解压缩到原始向量空间中的标签。此外，由于数据稀疏性，训练标签矩阵是低秩的关键假设在几乎所有现实世界应用中都被违反。这需要在压缩过程中严重丢失信息。
• 深度学习方法：虽然深度学习的方法被证明是有竞争力的，但是这个任务只有大约7000多个标记数据项，这不足以进行深度学习。
• 基于树的方法：输入或标签空间被安排在树层次结构中，其中根通常表示整个数据集。基于树的方法通常比基于嵌入的方法性能更好，因此我们的工作基于最先进的基于树的算法FastXML，它被证明比MLRF或LPSR具有更少的训练成本，并且经常被认为是与其他方法相比较的最先进的方法。

Input Data Data Sources

1. 这里用于模型训练的数据来自两个来源：NVD和SCA库漏洞数据库。从NVD中获取漏洞数据，并从SCA漏洞数据库中获取库名称，用于构建将NVD数据映射到库名称的训练数据集，即实现之前所提的映射函数。
2. 训练输入是带标签的数据 d t r a i n d_{train} dtrain​ 的有限集，是N对向量 { ( x ⃗ i , y ⃗ i ) i = 1 N } left{left(vec{x}_{i}, vec{y}_{i}right)_{i=1}^{N}right} {(x i​,y ​i​)i=1N​}的集合，其中 x ⃗ i ∈ X ⃗ vec{x}_{i}invec{X} x i​∈X 是输入数据项的特征向量， y ⃗ i ∈ Y ⃗ vec{y}_{i}invec{Y} y ​i​∈Y 是长度 ∣ L ∣ |L| ∣L∣ 的标签向量。L是一个标签集，对于给定的L的一个子集D，通过一个指代函数 1 D i : L → { 0 , 1 } 1_{D}^{i}: L rightarrow{0,1} 1Di​:L→{0,1} 来定义 y ⃗ i j = 1 D i ( L j ) vec{y}_{i j}=1_{D}^{i}left(L_{j}right) y ​ij​=1Di​(Lj​)。因此对于可能存在多个值的 j ( 1 ≤ j ≤ ∣ L ∣ ) j(1le jle|L|) j(1≤j≤∣L∣) ，当且仅当输入的 x ⃗ i vec{x}_{i} x i​ 被标记有库名 L j L_j Lj​ 时， y ⃗ i j = 1 vec{y}_{i j}=1 y ​ij​=1 。

• 实例：对于CVE-2015-7318， x ⃗ i vec{x}_{i} x i​ 代表了如图所示输入文本的矢量化
• y ⃗ i vec{y}_{i} y ​i​ 则是对库名的集合 D = { z o p e 2 , p l o n e } D={{zope2,plone}} D={zope2,plone} 进行编码
• 最后当且仅当 j j j 是 z o p e 2   o r   p l o n e zope2 or plone zope2 or plone 在标识库库名集合L中的索引时， y ⃗ i j = 1 vec{y}_{i j}=1 y ​ij​=1 。

3. 训练集

• f N V D : N V D → X ⃗ f_{NVD}:NVDrightarrow vec{X} fNVD​:NVD→X ， N V D NVD NVD 是 C V E   i d s CVE ids CVE ids 的集合， X ⃗ vec{X} X 是所有输入的特征向量集合。
• f S C A : N V D → P ( L ) f_{SCA}:NVDrightarrowmathcal{P}(L) fSCA​:NVD→P(L)，是将NVD中的CVE ID映射到库名称子集的函数 。
• f N V D − S C A : X ⃗ → P ( L ) f_{NVD-SCA}:vec{X}rightarrowmathcal{P}(L) fNVD−SCA​:X →P(L)，直接将输入的特征向量，映射到库名集。
• 所以最后定义了这样一个训练集： { ( x ⃗ , y ⃗ ) ∣ D = f N V D − S C A ( x ⃗ ) ∧ ( ∀ 1 ≤ j ≤ ∣ L ∣ ⋅ y ⃗ j = 1 D ( L j ) ) } left{(vec{x}, vec{y}) mid D=f_{N V D-S C A}(vec{x}) wedgeleft(forall 1 leq j leq|L| cdot vec{y} j=1_{D}left(L_{j}right)right)right} {(x ,y ​)∣D=fNVD−SCA​(x )∧(∀1≤j≤∣L∣⋅y ​j=1D​(Lj​))}

Data Cleaning

在使用收集的数据进行模型训练之前，需要做一些清理。主要执行以下三个步骤:

1. 基本清洁程序：删除了除感叹号和问号之外的非字母数字字符，并展开了撇号，Python的处理过程如下图所示
   
   Python中的基本数据清理转换为输出。在这里，re.sub将其第三个参数文本中与其第一个参数正则表达式匹配的任何子字符串替换为其第二个参数。
2. 删除数据收集系统可以使用NLTK Python包自动识别的非名词单词。仅使用名词已被发现对bug分配建议有效。对非名词过滤实际上提高了模型的性能。
   
   Python中的名词删除将In转换为Out。这里使用NLTK包，其中word_tokenize拆分成它包含的单词，pos_tag标记列表中的每个单词。这里包括NLTK标记的所有单词，其中NN、NNP、NNS或NNPS表示名词。
3. 删除了超过30%的NVD漏洞数据中出现的单词，因为这些是常用单词，这很可能无助于识别库名称。这些不仅是停用的单词，还包括出现在大多数NVD条目中的“安全”这样的单词。这样的词语会降低性能，因为它们不特定于特定的CVE或一组库。这个步骤利用 scikit-learn 0.20的CountVectorizer完成。

Feature Engineering and Selection

从每个NVD条目中，作者选择description、CPE配置和references来训练模型。其它特征比如数据格式、版本、时间戳和日期等管理数据不太可能帮助识别库名称。

1. CPE配置是预测相关库名称的重要特征，因为每个库名称都由非常接近库坐标的vendor name和product name组成。
2. CPE格式有不同的版本，这里只考虑撰写本文时的最新版本2.3。
3. 对于给定的NVD漏洞条目，可以有多个CPE配置。我们从每个配置中提取vendor name和product name，并将这两个名称作为一个文本单元处理。如下面这个例子所示：

到这里，可能会有人倾向于简单的使用“vendor name product name”来匹配包含漏洞的库，但是其实有两个问题：

1. CPE配置无法识别所有相关的库，也就是说这样直接去匹配的话不够全面，这样就会降低reacll的值
2. CPE配置不识别最相关的库，CPE中未指定的其它库也可能具有更高的相关性，这样就会降低精度。

Matchers

1. 最初，作者将所有选定的NVD条目功能(包括描述、CPE配置和引用)组合到单个文本中。然而，测试显示，对于某些条目，即使描述或CPE配置包含库的确切坐标1或坐标2，当在预测中使用时，模型无法将特征向量映射到相应的库名称。这导致在CPE配置中使用product name来搜索所有匹配库坐标，并将这些匹配坐标用作另一个输入特性。对于一个库，如果它有一个coordinate2，我们调用coordinate2作为该库的模块名，或者我们认为coordinate1就是这样的。
2. CPE配置中的产品名称与模块名称相似，有时甚至相同。为了从指定的product name中提取更多信息，我们搜索SCA漏洞数据库中的所有库条目，以查找模块名称与CPE配置中的product name相同的条目。然后，我们将这个库的名称(coordinate1 coordinate2)添加到我们的输入文本数据中，称为匹配器。
3. 这里也会有人会倾向于直接用匹配器来匹配漏洞和库，但是其存在的问题和单独使用CPE配置是一样的。

Core Approach

1. FastXML 算法产生一个模型: train ⁡ Fast  X M L : ( X ⃗ → in ⁡ Y ⃗ ) → ( X ⃗ → Q → ∣ L ∣ ) operatorname{train}_{text {Fast } X M L}:(vec{X} stackrel{operatorname{in}}{rightarrow} vec{Y}) rightarrowleft(vec{X} rightarrow overrightarrow{mathbb{Q}}^{|L|}right) trainFast XML​:(X →inY )→(X →Q ​∣L∣)

• Q → ∣ L ∣ overrightarrow{mathbb{Q}}^{|L|} Q ​∣L∣是标签长度|L|的有理向量定义域
• 将其与我们之前所得的数据集做为输入则可得到模型： train ⁡ Fast  X M L ( d train  ) operatorname{train}_{text {Fast } X M L}left(d_{text {train }}right) trainFast XML​(dtrain ​)

2. 我们的目标是使用FastXML算法进行预测，在例子中就是库识别。

• 当NVD是CVE ids的集合；L是库名集合； Q mathbb{Q} Q是有理数集合时，库名识别函数可以定义如下： i d e n t i f y Fast  X M L : N V D → ( L → Q ) identify_{text {Fast } X M L}: N V D rightarrow(L rightarrow mathbb{Q}) identifyFast XML​:NVD→(L→Q)
• 因为L的有限性， L → Q L rightarrow mathbb{Q} L→Q也是有限的，这里先定义一个函数： τ : Q → ∣ L ∣ → ( L → Q ) tau: overrightarrow{mathbb{Q}}^{|L|} rightarrow(L rightarrow mathbb{Q}) τ:Q ​∣L∣→(L→Q)，它将长度为|L|的有限有理向量转换为函数： L → Q L rightarrow mathbb{Q} L→Q，具体实现为： τ ( r ⃗ ) = { ( L j , r ⃗ j ) ∣ 1 ≤ j ≤ ∣ L ∣ } . tau(vec{r})=left{left(L_{j}, vec{r}_{j}right)|1 leq j leq| L midright} . τ(r )={(Lj​,r j​)∣1≤j≤∣L∣}.

3. 利用函数 τ tau τ,库名识别函数则为： i d e n t i f y Fast  X M L ( identify_{text {Fast } X M L}( identifyFast XML​( id ) = τ ( )=tauleft(right. )=τ( train Fast  X M L ( d train  ) ( f N V D ( i d ) ) ) left._{text {Fast } X M L}left(d_{text {train }}right)left(f_{N V D}(i d)right)right) Fast XML​(dtrain ​)(fNVD​(id)))
4. 最后对结果进行排序即可

Experiments Research Questions

作者对设计的各个方面进行了实验，并展示了性能结果。主要通过实验来回答以下研究问题:

• RQ1 ：What is the performance of using matchers alone as input?
  （单独使用匹配器输入有什么表现？）
• RQ2 ：Does adding description, CPE configurations, and references of NVD entries improve the model performance?（添加NVD条目的description、CPE配置和references是否会提高模型性能？）
• RQ3 ：Do non-noun and frequent-words removal improve model performance?|
  （非名词性和频繁词移除会提高模型性能吗？）
• RQ4 ：What is the number of the FastXML trees that results in the best performance?
  获得最佳性能的FastXML树的数量是多少？

Using Matchers only

匹配器可以单独用于预测。我们执行一个实验来确定当输入中只包含匹配器时的性能。结果如表所示。很容易看到RQ1的答案，当输入中只包含匹配器时，预测性能较低，平均F1@k仅为0.41。

Experiments with Data Cleaning

1. 用实验来评测数据清洗对模型性能的影响。表中显示了k = 1和3时的精度@k、召回率@k、F1@k结果，以及训练和验证时间(使用75%和25%的标记数据)。当我们比较两张表时，我们可以肯定地回答RQ2，增加描述、CPE配置和NVD条目的引用确实提高了模型性能。比较表5的最小0.50平均值1@k和表4的平均F1@k 0.41，我们得到平均F1 @ k的最小改善为21.95%。
2. 表5中表现最好的是非名词性和30%频繁词删除的配置。我们在生产中使用这种配置。这里我们肯定地回答RQ3:非名词去除和频繁词去除提高了预测性能。虽然我们可以观察到我们的生产配置的平均F1@k分数与其他配置相比差异不大，但非名词和频繁单词的移除仍然减少了训练和验证时间。

Experiments with Tree Sizes

FastXML使用树，其中每一棵树都代表特征空间上的不同层次。我们进行了一个实验，在32、64和128之间改变树的数量，并将结果总结在表6中。我们还包括分别对75%和25%的标记数据进行训练和验证的时间测量结果。对于RQ4，我们确认导致最佳性能的FastXML树的数量是128。但是，64和128之间的平均F1@k的差异非常小，由于64棵树的配置只需要一半的训练时间，我们将其用于我们的系统。

Conclusion and Future Work

预测NVD CVE条目的相关库是SCA产品的重要一步，以节省识别易受攻击库的人工研究工作。本文介绍了一个自动执行数据收集、特征工程、模型训练、验证和预测及其实验评估的系统的设计和实现。我们的问题是将NVD条目映射到库名是XML的一个实例。我们的系统基于基于树的FastXML 方法，该方法解决了XML问题。目前，我们不采用深度学习，因为我们标记的数据量目前还不够大。在未来的工作中，如果有更多的数据，可以尝试深度学习的方法。