ICSE'22-Learning Probabilistic Models for Static Analysis Alarms

摘要

我们提出了 BayeSmith，一个用于自动学习静态分析警报概率模型的通用框架。最近提出了几种概率推理技术，它们结合了对语义事实的外部反馈，从而减少了用户的警报检查负担。然而，这些方法基本上仅限于具有预定义结构的模型，因此无法学习或将有关分析的知识从一个程序转移到另一个程序。此外，这些概率模型通常会积极地从外部反馈中泛化并错误地抑制真正的错误。为了解决这些问题，我们提出了学习概率模型的结构和权重的 BayeSmith。BayeSmith 从一个初始模型和一组带有错误标签的训练程序开始，改进了模型，以根据反馈有效地优先考虑真正的错误。我们通过对一组 C 程序的两个静态分析来评估该方法。我们证明了学习模型显着提高了三个最先进的概率推理系统的性能。

引言

为了应对准确性和警报相关性的挑战，已经为静态程序分析器提出了各种概率程序推理机制。此类系统最初使用基础分析报告目标程序中的一组警报，并根据概率模型计算每个警报的概率。然后，他们通过结合来自各种来源（如用户 [23、39、50]、程序的旧版本 [15] 或动态分析结果 [5]）对语义事实的外部反馈，对静态分析警报进行优先级排序。收到响应后，他们会根据反馈进行概括，并根据剩余警报与用户检查的警报的相关性确定其优先级。通过迅速将注意力集中在目标程序中的真正错误上，这些系统实现了静态分析器可用性的显着改进。

尽管他们在实验上取得了成功，但之前的大部分研究都集中在推理问题上，而不是学习上。现有的基于概率推理的方法（例如警报排名 [5,15,39]）仅使用标准方法（例如期望最大化算法 [20]）学习有限形式的可转移知识（例如将权重分配给基础概率模型）。然而，在我们的观察中，学习能力从根本上受限于概率模型的底层结构。

在本文中，我们提出了一个用于学习静态分析警报的概率模型的通用框架，该框架适用于各种概率推理系统 [5, 15, 39]。底层系统最初从警报的推导结构构建贝叶斯网络，并使用诱导的置信度值对警报进行优先级排序。当用户检查警报并报告他们的发现时，此排名会反复更新。理想情况下，这些响应应始终提高真正错误的置信度分数并减少误报的置信度分数。然而，在实践中，由于底层抽象和模型恢复期间造成的近似，他们经常错误地将错误警报优先于真正的错误。我们的目标是提高概率模型的准确性并减轻这些错误泛化事件的影响。给定一组带有错误标签的训练程序，我们学习产生准确贝叶斯网络模型的逻辑规则，以减少用户交互的数量，直到发现所有真正的警报。

请注意，我们的问题（即学习）与以前的论文 [5, 15, 39] 中解决的问题（即推理）根本不同。学习和推理是 AI/ML 研究中的互补问题，尤其是对于贝叶斯网络。现有的仅关注由一组固定的手写规则生成的贝叶斯概率模型的推断。相反，我们阐明了学习贝叶斯模型的能力，该模型可以显着提高多个实例的性能。

我们的方法基于两个关键思想：（1）反馈导向和（2）语法导向的细化。我们首先使用一组初始规则构建贝叶斯网络，并使用给定的标记数据集评估交互式警报优先级的质量。通过观察结果，我们捕捉到对一个警报的响应错误地泛化到其他警报并降低整体排名质量的时刻。对于这种情况，我们的学习算法改进了生成贝叶斯网络不准确部分的规则。细化以程序语法为指导，并通过添加直接源自目标语言语法的语法特征将标记警报的更详细上下文编码到规则中。

我们已经在一个名为 BayeSmith 的工具中实例化了这种方法，并在一套广泛使用的 C 程序上评估了它的有效性，每个程序包含 5-112 KLOC，并对 C 进行两次分析：缓冲区溢出错误的间隔分析和格式字符串的污点分析和整数溢出错误。我们使用三个最先进的概率程序推理系统来衡量 BayeSmith 的有效性，每个系统都包含来自用户的反馈 [39]、程序的先前版本 [15] 和动态分析结果 [5]。BayeSmith 的学习规则将手动设计模型的现有系统的性能分别显着提高了 30.7%、54.3% 和 20.3%。

本文做出以下贡献：

1. 我们提出了一个从数据中学习用于静态分析警报的概率模型的框架。
2. 我们提出了一种反馈导向算法，通过减少错误的泛化事件来学习概率模型。
3. 我们使用两个最先进的静态分析器评估我们的方法，并展示了在一套 C 程序上的三个概率程序推理系统的显着改进。

概述

通过 Datalog 进行近似静态分析

贝叶斯警报排名系统

错误泛化问题

学习贝叶斯网络

预赛

程序分析和句法特征

贝叶斯警报优先级

学习框架

目标

规则细化

学习算法

实验评估

设置

有效概率模型

减少错误泛化

学习算法的鲁棒性

可扩展性

限制和机会

本节确定了我们方法的局限性和未来工作的挑战。首先，BayeSmith 需要现有分析规则形式的背景知识。我们展示了一套基于稀疏分析框架的 def-use 关系规则 [36] 是一个合理的起点。虽然在一大类分析中使用了 def-use 关系[16、44、49]，但可能还有其他分析需要分析设计者根据不同的背景知识推导出初始规则。为了应对这一挑战，我们计划设计一种无需背景知识的纯数据驱动合成算法。其次，BayeSmith 只考虑可能无法准确反映更深层次语义方面的语法引导细化。对于未来的工作，我们计划开发一种考虑抽象域和语义特征的细化算法。最后，BayeSmith 假设了一个理想的用户交互模型，其中用户总是对排名靠前的警报给出正确的反馈。但是，用户可能会犯错误、给出部分反馈或诊断任意警报。因此，开发更先进的交互模型也是我们未来工作的重要方向。

相关工作

结论

我们提出了 BayeSmith，一个用于贝叶斯警报排名系统的通用学习框架。BayeSmith 通过学习底层概率模型的结构，从根本上提高了用户引导程序推理系统（user-guided program reasoning systems）的质量。BayeSmith 通过最小化从模拟用户与标记数据的交互中观察到的错误概括的影响来学习准确的贝叶斯网络。在两个实例分析的实验中，我们证明了学习规则的有效性以及在用户报警检查负担方面的显着改善。

致谢