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

      本文提出了一种称为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个以上元素的复杂编程规则，因此以前的工具很难检测到。我们报告了这些错误，目前正由开发人员修复。

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

图5：PR-Miner的流程图

       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节）。

       解析源代码的主要目的是构建一个项集数据库，以便将编程模式提取问题转换为频繁项集挖掘问题。 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：解析函数的示例。选择源代码中的斜体标识符进行分析。它们以第二列中所示的类型为前缀。然后将每个预处理的标识符散列为数字。为简单起见，仅显示散列值的最后两位数字。

      在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个函数。

[招生]系统0day安全班，企业级设备固件漏洞挖掘，Linux平台漏洞挖掘！