看到一篇不错的文章，利用数据挖掘的方法提取程序源代码中隐藏的规则，然后利用此规则进行检测其它代码是否存在违规行为，违反规则的则表示存在相应的漏洞。虽然论文是2005年的，但个人还是觉得思路非常的好。

摘要

       程序通常遵循许多隐式编程规则，其中大多数规则太繁琐，无法由程序员记录。当这些规则被不了解或忘记它们的程序员违反时，可以很容易地引入缺陷。因此，非常希望有工具来自动提取这些规则并自动检测违规。以前在这方面的工作集中在简单的基于函数对的编程规则上，并且还需要程序员提供规则模板。

      本文提出了一种称为PR-Miner的通用方法，它使用称为频繁项集挖掘的数据挖掘技术，从用C等工业编程语言编写的大型软件代码中有效地提取隐式编程规则，这需要程序员很少的努力，也没有软件先验知识。受益于频繁的项集挖掘，PR-Miner可以提取一般形式的编程规则（不受任何固定规则模板的约束），该规则可以包含各种类型的多个程序元素，例如函数，变量和数据类型。此外，我们还提出了一种有效的算法来自动检测提取的编程规则的违规，这是错误的强烈指示。

       我们使用大型软件代码（包括Linux，PostgreSQL Server和Apache HTTP Server）进行评估，每个代码具有84K-3M代码行，表明PR-Miner可以在2分钟内有效地提取数千种通用编程规则并检测违规。此外，PR-Miner已经检测到许多违反提取规则的行为。在PR-Miner报告的前60个违规行为中，有16个已被确认为最新版Linux中的错误，PostgreSQL中有6个，Apache中有1个。其中大多数违反了包含2个以上元素的复杂编程规则，因此以前的工具很难检测到。我们报告了这些错误，目前正由开发人员修复。

3. PR-Miner

       PR-Miner有两个主要功能：自动提取隐式编程规则，并自动检测违反提取的编程规则。 PR-Miner的流程图如图5所示。本节首先概述PR-Miner，然后介绍PR-Miner如何从源代码中自动提取编程规则，以及如何检测规则违规并修剪误报。

图5：PR-Miner的流程图

3.1概述

       PR-Miner在自动规则提取中的高级思想是通过查找在源代码中经常一起使用的元素来找到元素之间的关联（例如，函数，变量，数据类型）。例如，在Linux中调用spin_lock_irqsave和spin_unlock_irqrestore会在同一函数中一起出现超过3600次，这表明在spin_lock_irqsave之后spin_unlock_irqrestore很可能是一个隐式编程规则。通过识别在源代码中频繁使用哪些元素，可以将这种相关元素视为具有相对高置信度的编程规则。当然，正如引言中所描述的，这种高级想法的天真实现是不可行的，因为它需要检查所有可能的元素组合。

为了有效地找到程序元素相关性，PR-Miner通过首先解析软件源代码将问题转换为频繁项集挖掘问题，如图5所示。每个程序元素被散列为数字，然后函数定义被映射到项集（一组数字），作为一行写入项目集数据库。结果，整个程序被转换为包含许多项集的数据库。通过使用频繁项集挖掘算法（如FPclose）挖掘此数据库，我们可以找到多次出现的频繁子项集。然后可以使用这些频繁的子项集来推断编程规则。

对于由挖掘算法发现的频繁子项集，我们将相应程序元素的集合称为编程模式，表示程序元素是相关的并且经常一起使用。例如，FPclose可以发现{spin_locak_irqsave, spin_unlock_irqrestoreg }是个编程模式，因为它出现在Linux源代码中超过3600次。

       请注意，编程模式与编程规则不同。例如，上述模式可能会导致以下一个或两个编程规则：

       第一条规则说每当程序调用spin_locak_irqsave时，它也应该调用spin_unlock_irqrestoreg，而第二条规则说每当程序调用spin_unlock_irqrestoreg时，它也应该调用spin_locak_irqsave。这两个是不同的规则，并不是所有的规则都是肯定的，即使模式已经多次出现。

       因此，在使用频繁项集挖掘技术提取编程模式之后，PR-Miner需要从提取的模式生成编程规则。规则生成过程的主要思想是查找包含左侧项目但不包含右侧项目的案例数量。例如，在上面的例子中，我们需要找出spin_locak_irqsave出现的情况，但是spin_unlock_irqrestoreg没有，反之亦然。在生成编程规则之后，PR-Miner将它们存储在规范文件中，以便程序员可以检查它们，并在以后将它们用作引用。第3.3节详细描述了规则生成过程。

生成编程规则后，PR-Miner会自动检测源代码中的违规。它还会自动修剪报告中的误报和违规行为排名，以便程序员只需要检查排名最高的违规行为。违规检测过程基于这样的想法，即在大多数情况下通常遵循编程规则，并且仅在一小部分情况下发生违规。 3.4节更详细地描述了检测过程。

       使用封闭的频繁项集挖掘算法（如FPclose）为PR-Miner提供了以下几个好处：（1）通用性。封闭频繁项集挖掘算法不限制频繁子项集中的项数，也不需要任何规则模板。

       此外，频繁子项目集中的项目不一定在支持项目集中相邻，即它们可以彼此远离。 （2）时间效率。诸如FPclose之类的数据挖掘算法通常非常有效，因为它们尽可能地通过消除冗余计算来努力避免扫描数据太多次。此外，由于FPclose仅生成封闭的频繁项集，因此可以避免生成指数数量的子项集。 （3）空间效率。从封闭的频繁子项集中，我们可以找到封闭的规则，包含相同支持的许多其他规则的规则。取项目集数据库D = {{a, b c, d, e}, {a, b, d, e, f}, {a. b. d. g}, {a, c, h, i}}在第2节中描述为例。 FPclose找到一个封闭的频繁子集{a, b, d}：3。从已封闭的频繁子项集中，我们可以得到以下6个关闭规则的支持数是3：

       其他规则归入上述封闭规则。例如，第一个封闭规则包含置信度为75％的子规则{a}->{b}。使用封闭规则不仅可以节省空间，还可以显着减少程序员需要检查或引用的规则数量。此外，它还加快了违规检测过程（参见第3.4节）。

3.2提取编程模式

3.2.1解析源代码

       解析源代码的主要目的是构建一个项集数据库，以便将编程模式提取问题转换为频繁项集挖掘问题。 PR-Miner通过使用修改后的GCC编译器[25]作为解析器将每个函数定义转换为一组数字来实现此目的。 PR-Miner的当前原型仅适用于C，但可以通过替换GCC前端轻松扩展到其他编程语言。

为了将源代码转换为itemset数据库，我们需要解决以下问题：（1）如何解析源代码？ （2）源代码中的哪些元素应该被转换？（3）如何用数字表示元素？

       为了解析源代码，PR-Miner首先使用GCC前端来获得中间表示。中间表示存储在树数据结构中，每个节点表示源代码中的各种类型的元素，包括标识符名称，数据类型名称，关键字，运算符，控制结构等。为了将函数转换为项集，PR-Miner遍历此函数的表示树，并将每个所选元素散列为数字。通过组合函数中所有选定元素的哈希值，此函数将映射到项集。然后，所有函数的项集构造项集数据库，以输入到挖掘算法FPclose。将函数而不是基本块转换为项集的原因是大多数编程规则通常发生在函数的范围内。当然，一些规则可以跨越多个功能。但是，挖掘这些规则要困难得多，因为它需要更深入的程序间分析，因此提取这些规则仍然是我们未来的工作。

       并非中间表示中的每个程序元素都被转换为数字，因为某些元素会导致噪声。例如，关键字和简单数据类型（如int）几乎出现在每个函数中。它们不太可能导致有趣的编程规则。此外，将它们包含在项目集中将明显增加频繁项集挖掘的计算。因此，PR-Miner不会将这些元素散列为数字。

       此外，涉及局部变量的相同编程规则可以在不同的代码段使用不同的变量名。例如，在图4所示的示例中，对同一函数scsi_host_alloc调用的返回值可以分配给不同的局部变量，例如host和scsi_host。如果我们将它们分成不同的数字，则可能会错过规则。为了捕获这种类型的规则，我们需要使用这些局部变量的共同特征（例如它们的数据类型）来表示它们，以便它们仍然在项目集数据库中被散列为相同的数字。例如，图2中代码段中的局部变量class_ref由其数据类型Relation的散列值表示，而不是其名称class_ref。

       将标识符散列到数字时的另一个问题是名称冲突。具有相同名称的不同类型的标识符将被散列到相同的数字，从而在生成的频繁子项集中导致误报。为了消除这种名称冲突，PR-Miner将不同类型的标识符散列为不同的值。为此，PR-Miner首先根据其类型为每个标识符名称添加前缀，然后将带前缀的名称散列为数字。例如，对锁定的函数调用将以“F-”为前缀，然后对与“F-lock”对应的数字进行哈希处理，而具有相同名称锁定的全局变量将以“G-”作为前缀并且为哈希到对应于“G-lock”的数字。

       类似地，不同的记录结构可以对其字段使用相同的名称，这在大型软件中很常见。例如，名称“next”和“prev”通常用作许多不同结构中的字段名称。这种名称冲突会导致频繁子项集的误报。为了区分相同名称但在不同记录结构中的字段，PR-Miner将相关记录类型附加到每个字段名称。例如，记录类型树和列表中的下一个字段分别被视为“D-tree.R-next”和“D-list.R-next”，因此可以将它们分成不同的数字以避免冲突。

PR-Miner使用的散列函数是“hashpjw”[2]，因其低冲突率而被选择。我们的实验表明，它的碰撞率足够低，可以进行频繁的子项集挖掘。此外，如果需要无冲突映射，我们可以首先解析整个源代码，以便我们可以为所有可能的标识符创建符号表，然后根据索引到符号表将元素转换为数字。由于需要再传递一次源代码并且我们的散列方法已经具有较低的冲突率，因此我们不使用此方法。

表1显示了PR-Miner如何将函数转换为项集。在解析源代码，对所选元素进行前缀和散列后，PR-Miner将函数twa probe的定义转换为项集{92,39,41,68,56,36，... }。

表1：解析函数的示例。选择源代码中的斜体标识符进行分析。它们以第二列中所示的类型为前缀。然后将每个预处理的标识符散列为数字。为简单起见，仅显示散列值的最后两位数字。

3.2.2编程模式的挖掘

      在PR-Miner解析源代码并生成项集数据库之后，它将封闭的频繁项集挖掘算法FPclose应用于数据库以查找关闭的频繁子项集。正如我们在第2节中所描述的那样，如果一组数字在任何项目集中一起出现超过指定阈值数量（最小支持）的次数，则该子项目集被认为是频繁的。让我们考虑表1中所示的示例。为简单起见，我们将这三个函数表示为add，alloc和scan。子项集{39,68,36,92}出现在从Linux代码转换的项目集数据库中的总共27个项目集中。假设最小支持度设置为15. FPclose将找到一个频繁的子项集{39,68,36,92}，支持度为27，这意味着使用相应的函数alloc，add和scan，以及数据类型Scsi_Host一起27次。因此，这四个元素彼此相关，从而作为编程模式输出，然后用于在下一步骤中生成编程规则。

       由于FPclose仅生成支持大于其超级项集支持的封闭频繁项集，因此它不会生成具有相同支持的冗余子模式。在上面的例子中，{39,68,36}也是一个频繁的子项集。然而，由于它没有闭合，即它被包含在具有相同支持度27的超级项目集{39,68,36,92}中，所以我们不需要输出它。

仅知道封闭的编程模式及其支持值（即模式发生的次数）是不够的。如果我们还记录每个提取的模式发生的函数，那对程序员来说会更有帮助。稍后在违规检测中也需要这样的信息，以便知道哪个功能违反了提取的规则。不幸的是，原始算法FPclose和任何其他频繁项集挖掘算法并非完全符合我们的目的。它们仅输出每个已发现模式的支持值，但不输出其支持项集。因此，我们通过在挖掘过程中维护支持项集来增强FPclose来解决这个问题。在上面的例子中，PR-Miner输出闭合的频繁子项集{39,68,36,92}，其中支持项集对应于包含该编程模式的27个函数。

3.3生成编程规则

       正如我们在3.1节中简要解释的那样，仅提取编程模式是不够的，因为模式可能会导致许多不同的规则。因此，我们还需要根据条件概率从模式生成规则。

3.3.1 naive方法

       从提取的模式生成编程规则的一种简单方法是将每个封闭的频繁子项集中的项分成两部分，然后计算置信度。换句话说，从闭合的频繁子项集I中，我们可以计算每个可能的关联规则X->Y的置信度，其中X和Y是I [1,15]的子集。这种规则的支持度等于I的支持度，而规则的置信度是条件概率，即支持（I）/支持（X），其中支持（X）是子项集出现在项集数据库中的次数，也等于包含X的任何已关闭的频繁项目集的最大支持。基本上，置信度表示如果X出现，则Y发生的可能性的条件概率。置信度小于指定阈值（例如90％）的规则被修剪。其余的规则输出到规范文件中以供程序员检查和引用。

       让我们再考虑一下上面的例子。在PR-Miner找到编程模式{alloc，add，scan，Scsi_Hostg}。通过这种模式，naive方法可以通过将这三个函数和数据类型分成两个子集来生成14种不同的可能规则，例如{add} -> {alloc，scan，Scsi_Host}和{add，alloc} -> {scan，Scsi_Host}等等。所有这些规则的支持度都为27。从FPclose发现的编程模式中，我们知道对{add}的支持度是37，对{add}->{alloc }的支持是29。因此，这两条规则的置信度分别为27 /37 = 72.9％和27 /29 = 93.1％。其他12条规则的置信度也可以类似地计算。因此，如果我们将置信度阈值设置为90％，则第一个规则{add} -> {alloc，scan，Scsi_Host}被修剪，而第二个规则被输出。

       native方法的最大问题是它需要检查每个挖掘模式的所有可能规则。一个具有k个元素的编程模式可以生成最多（2k-2）个规则，这对长模式来说是不切实际的。例如，我们的评估大型软件代码显示一些编程模式由20多个元素组成。 因此，使用这种native方法从模式生成规则在时间和空间都是是低效的。

3.3.2生成封闭规则

       PR-Miner不仅仅检查挖掘模式中的所有可能的编程规则，而是检查封闭规则。正如我们在3.1节中解释的那样，仅生成封闭规则就足够了，因为其他规则被封闭规则包含在内。为了进一步减少输出规则的数量并加速生成以及违规检测过程，PR-Miner以浓缩格式存储封闭规则。形式上，封闭的频繁子项集I的压缩格式是：

       其中C1… Cm是I的子集，其支持度（s1 … sm）与I不同。显然，s1 … sm都比s大。这种压缩格式可以表示从I导出的所有封闭规则，并且可以容易地计算它们的置信度。对于从I导出的闭合规则X-> Y，如果X等于Ci（即支持度大于I的I的子集），则规则的置信度为s / si;否则，该规则的置信度是100％。

例如，假设FPclose提取两个封闭的频繁子集：{a}：4和{a; b; d}：3。浓缩格式表示从{a，b，d}派生的所有封闭规则是

       它明确地表达了规则{a} -> {b，d}置信度3/4 = 75％，并且还推断出任何其他5个封闭规则，例如{a，b} –> {d}置信度为100％。现在，规则生成问题变成了如何找出支持度si大于s的所有子集Ci。由于Ci的支持度大于s，它表示Ci应该包含在另一个封闭的频繁子项集中（基于闭合频繁子项集的定义）。由于Ci可以包括多个其他封闭的频繁子项集，PR-Miner需要找到具有最大支持度的那个。

       为了实现这一目标，PR-Miner使用了一个聪明的想法，将此问题转换回频繁的子项集挖掘。换句话说，PR-Miner再次使用FPclose从FPclose第一次传递生成的频繁子项集中查找公共子集。这样做将找到在第一遍中生成的闭合频繁子项集中的所有公共子集。设CommonSub表示FPclose第二遍生成的所有公共子集。如果CommonSub中包含I的子集Ci，我们可以立即找出Ci的哪个超级项集具有最大支持度。基于封闭频繁子项集的定义，该超级项集的支持度必须等于Ci的支持度。我们可以通过矛盾轻松证明这一点（由于空间限制，证据被省略）。注意，我们需要的基本操作是计算每对闭合频繁子项集的公共子集。因此，我们可以在最小支持度为2的闭合频繁子项集上再次应用频繁项集挖掘算法。我们的算法CLOSEDRULES用于生成浓缩格式的闭合规则如图6所示。

图6：从第3.2节中解释的第一步开始，从封闭的频繁项集中生成浓缩格式的闭合规则R.密切频繁挖掘算法FPCLOSE以项目集数据库和最小支持阈值作为输入，输出封闭的频繁子项集，每个子项集有三个字段<Fi; si; Ei>，其中Fi是频繁项集本身，si是它的支持度，Ei其支持项集的索引，Ei按升序排序。同样，<F’i，s’i，E’i>具有相同的含义，但是由FPCLOSE的第二遍（第2行）生成到由所有封闭的频繁子项集组成的数据库，即{Fi|i = 1，2，…n}。

       我从FPclose（第1行）开采的项目集，以便它可以快速定位频繁项目集，并对任何公共子项目提供最大支持。在第2行中，它调用FPclose，最小支持为2，以找出I中的所有公共子项集C.对于每个公共子项集Ci（第3行），CLOSEDRULES将其支持度插入到相应的压缩格式规则，如下所示。 E’i包括I中所有Ci支持项集的索引。第一个支持项集Ii1对Ci具有最大支持，因为E’ i中的所有索引都是根据其对应项集的支持进行排序的。对于其他支持项集Ii1（第5行），如果其支持sij小于si1（第6行），则将Ci插入到闭合频繁项集Ii1的规则的子集中。这样，只有一次传递，它可以将Ci插入到所有规则中，这些规则是Ci的超级项集，但支持次数小于Ci。

       CLOSEDRULES在空间和时间方面比naive算法执行得更好，因为它不需要检查从提取的编程模式生成的所有可能的规则。

       通过在对应于提取的编程模式的封闭频繁子项集上调用CLOSEDRULES，PR-Miner以数字表示的压缩格式获得封闭规则，然后将封闭规则映射回编程规则并将它们存储到规范中文件。然后，程序员可以验证编程规则，以便以后他们可以将它们用作规范，并且新程序员在开始编码时可以读取它们以避免错误。

由于PR-Miner基于事件提取编程规则，如果某些元素仅在源代码中巧合地多次出现在一起，则可能会引入一些误报。但是，具有更大支持的规则可以更加可信。因此，PR-Miner根据支持对规则进行排名：程序员可以检查排名在前100或500中的那些规则。此外，正如我们早期解释的那样，对置信度低于指定阈值（例如90％）的规则进行了修剪。此外，还可以应用其他一些排序方法，如在Engler等人的工作[8]中为不同元素赋予权重。

3.4检测违规到提取的规则

       根据上一步生成的编程规则，PR-Miner可以通过检测对这些规则的违规来发现潜在的错误。主要思想是编程规则通常适用于大多数情况，违规仅偶尔发生。以图4中PR-Miner检测到的潜在错误为例。对scan的函数调用应遵循编程规则随后调用alloc和add。此规则在Linux中出现27次，但有2个案例违反此规则，因为缺少扫描。

如图5所示，PR-Miner首先检测违反提取的编程规则，然后使用过程间分析修剪错误违规，最后在错误报告中对违规进行排序。

3.4.1检测违规行为

       为了检测对编程规则的违反，naive方法是生成所有可能的编程规则，然后逐个检查源代码。正如我们在3.3节中讨论的那样，需要检查指数数量的规则。幸运的是，没有必要检查所有编程规则。

首先，如果规则的置信度较低，则已在规则生成步骤中对其进行了修剪。换句话说，如果置信度阈值为t，则丢弃置信度小于t的任何规则。其次，如果规则具有100％的置信度，则表明该规则没有违规。因此，我们只需要在范围内自信地检查规则[t,100％）。

       违规检测过程的主要思想很简单。例如，如果一个规则{a，b} -> {d}的支持数为100和{a，b}有101的支持数，101个案例中只有一个违规情况含有{a，b}但不含{d}，表示此案例违反了规则{a，b} -> {d}。换句话说，这种情况可能是一个bug。但如果{a，b}有200的支持，规则{a，b} -> {d}将被修剪，因为它的置信度只有50％。

由于PR-Miner以精简格式存储生成的编程规则，明确指出哪些规则具有小于100％但大于指定阈值t的置信度，因此我们可以轻松地确定哪些规则具有违规。更有效的是，PR-Miner在通过调用CLOSEDRULES生成编程规则时在同一进程中检测到违规，如图6所示。为此，PR-Miner计算了规则F’I ->（Fij - F’i）的置信度在第5行的循环为c = sij / si1。如果t≤c<1，则表示存在违反此规则的情况。通过比较封闭的频繁子项集Ii1和Iij的支持项集，可以容易地计算出违规，如下所述。Fi1包含公共子项集F’i，但它不包含（Fij - F’i）。这意味着Ei1中的一些支持项集违反了规则F'I - >（Fij - F'i）。另一方面，该规则由Fij的支持项集Eij支持。因此，在Ei1中但不在Eij中的项目集违反了此规则，因此项目集的相应功能违反了编程规则。

3.4.2修剪虚假违规行为

       如果编程规则中的元素跨越多个函数，则上述违规检测可能导致误报。原因是PR-Miner仅使用过程内分析来检测违规，因为如第3.2节所述，数据库中的每个项目集都对应于一个函数定义。假设在一个带有函数对（lock和unlock）规则的示例中，在函数F在内部调用unlock，但是lock没有。相反，F调用另一个函数try_lock来调用lock。如果没有过程间分析，PR-Miner会报告F包含违反缺失lock的情况，即使F在其被调用者中包含lock。

图7：检查修剪错误违规的调用路径

       为了修剪上述违规行为，PR-Miner执行程序间检查。它首先检查每个包含违规的函数的被调用者路径。对于函数F中每次违反规则X->Y，PR-Miner检查每个项yÎ Y是否在F调用的函数F1….Fn中。如图7（a）所示，通过检查被调用者F1调用的函数，我们可以更深入地跟随在函数F中F1…. Fn调用的调用路径。如果缺少的项目在任何调用路径中，则是误报。为了提高时间效率，PR-Miner限制了检查深度。由于PR-Miner在第3.2.1节中描述的每个函数定义中输出所有函数调用，因此在检查期间很容易遵循调用路径。

除了调用者之外，PR-Miner还会检查被调用者以修复误报。在上面的示例中，函数try_lock中也存在违规，因为lock处于try_lock中，但unlock不在其中。为了修剪这种误报，PR-Miner还会检查遗失的条目是否在调用者函数的路径中，如图7（b）所示。为了向后检查调用路径，PR-Miner维护每个函数F的调用者列表，该函数由调用F的函数的索引组成。如果函数F的缺失项在其所有调用者的路径中，则是误报。

3.4.3排名和报告错误

       在PR-Miner检测到规则违规并修剪误报后，它会对所有剩余的违规进行排名并将其报告给程序员。

PR-Miner根据违规规则的置信度对违规行为进行排名。由于函数可能包含多个违规，PRMiner将所有相同函数的违规一起分组，并且具有最高置信度的违规被指定为违规函数的置信度。违规函数的置信度可以被认为是函数存在错误的可能性。在当前版本的PR-Miner中，它只是根据置信度对错误进行排名。由于多个函数可能具有相同的违规，因此这些函数中的潜在错误密切相关。因此，这里可以使用一些其他高级排名方案，如相关性排名[17]，以进一步提高我们的排名功能的准确性，这仍然是我们未来的工作。

[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法