G.O.S.S.I.P 阅读推荐 2023-10-16 LLM 时代的程序分析漫游指南

大语言模型（LLM）的热度依旧，今天我们要给大家推荐的这篇论文 The Hitchhiker’s Guide to Program Analysis: A Journey with Large Language Models 来自 UC Riverside 的钱志云老师研究组（当然钱老师也是我们的“G.O.S.S.I.P和朋友”系列^_^），这篇论文系统性地讨论了如何结合 LLM 和静态程序分析技术，从而实现更好的漏洞检测。

作者用他们的前序研究工作 UBITect: A Precise and Scalable Method to Detect Use-before-Initialization Bugs in Linux Kernel 中的一些研究问题来引出本文。首先说一下 UBITect 这项研究，它是一项 pre-LLM 时代的研究（2020年 FSE 会议论文），用来检测 Linux 内核中的 Use Before Initialization（UBI）这种类型的代码缺陷，可以认为是静态程序分析领域在这个特定领域的 state-of-the-art 工具。但是，下面的这个极为简单的例子就是 UBITect 所不能很好处理的：

如果你学过 C 语言的一些高级特性（当然，如果没记错的话，例子里面这部分内容在经典的 K&R 版本的《C程序设计语言》里面其实就介绍过，并不能算是“高级”的特性了），就会对可变参数列表这种特定的传参方式不会感到太陌生，可是程序分析工具却“不懂”这种知识，对上面例子中的第3行代码的这种初始化方式无法准确建模，因此会导致误报（以为 a、b、c、d 没有初始化就会被使用）。

这个（误报）例子里面最大的问题，是程序分析工具在处理 sscanf 的时候，不懂 va_start 的调用语义，如果要给它拔高一点的话，那就可以总结为两点：

1. 程序分析工具缺乏“知识”：对于一些领域知识，程序分析工具显然需要人工进行建模，但是在各种程序分析和漏洞检测任务中，这种建模的需求太多了，专家忙不过来。

2. 程序分析工具搜索策略不够“聪明”：很多程序分析的“原教旨主义者”（嗯，说的就是我们遇到的一些学术会议的审稿人）认为各种程序分析任务都可以通过穷搜索解决，这种想法就和“RSA只要硬算就能分解完”一样天真烂漫——真实世界里面到处都是复杂到让程序分析工具内存需求爆炸的点，硬算是不现实的，关于如何解决这一点可以去看看 AlphaGo 的思路。

所幸的是，LLM 的横空出世能够帮助我们在程序分析中解决很多问题，拿底下这个例子来说，只要分析的时候能够“理解”第4行的init函数和第6行的use函数（当然不能用经典的数据流分析方法来套用），就能快速检测出 UBI 问题是否存在：

作者在本文中把 UBITect 和 LLM 结合起来，设计了 LLift 工具。对于前面提到的那个涉及可变参数的例子，LLift 工具会按照如下的处理方式来分析。首先是利用 LLM 完成三个任务：1）识别所有的 initializer （这个例子中就是 sscanf）并分析其特性；2）根据 initializer 的特性，构建 post-constraint 约束条件；3）给 initializer 定性（是一定会初始化变量，还是有可能初始化变量）。在（LLM）完成这些分析后，剩下的工作就交给程序分析引擎来做了。

如果想偷懒不想关心技术细节，那么只要看看下面这个流程图，你大概就能 get 到 LLift 工具设计的中心思想了。

当然，这个技术路线只是非常笼统的总结，具体实现里面有很多挑战需要去解决：首先，大语言模型并不是那么“懂”程序分析的套路，需要去“教会它”如何按照程序分析的需求来输出相关格式的信息（例如程序分析所需要的约束条件）；其次，目前的 LLM 模型一次只能输入有限的 token，还要开发一套输入方法让 LLM 去处理海量代码；最后，在实际分析中还要考虑 LLM 众所周知的“胡说八道”特性（hallucination and stochasticity），避免在分析中引入错误的信息。欲知作者如何实现，还需要我们的读者自己花点功夫，把论文的第四章好好消化吸收一下。

最后来看看实验，作者把 UBITect 论文中的实验结果拿出来进行了复测，当时 UBITect 有一个很大的问题——初始分析的误报偏高。如果只使用 UBITect 的第一步静态分析，会报告大概14万个问题，而 UBITect 依赖符号执行来进一步检查这些问题，却只能处理其中的60%，剩余的40%会因为程序分析的各种问题（比如复杂度太高）而无法处理。在本文中，LLift 工具对之前报告的问题中随机抽取的1000个实例（Linux v4.14内核）进行了复测，仅仅报告了26个问题，而其中就有13个得到了确认，这个报告的数量和准确率是非常适合在生产过程中给一线开发人员来使用的。

在 LLM 时代，一个很有意思的特点是大家会把对 LLM 进行“调教”的 prompt 指令也放出来，本文的相关内容可以在下面的网站上检索到：

https://sites.google.com/view/llift-open/prompt

---

论文：https://arxiv.org/abs/2308.00245

原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2023-10-16 LLM 时代的程序分析漫游指南