静态分析：简介

软件工程的根本挑战之一是复杂性。

帕特里克·汤姆森

源代码、计算机和人之间的关系是复杂的。虽然大多数代码的存在是为了在计算机上运行，但其目的并不仅限于此。它也旨在被阅读和理解。现代软件开发的复杂性与理解代码的努力背道而驰：无法理解的软件无法轻易维护或改进，许多实证研究表明，给定代码库的复杂性与其缺陷率之间存在关联³。理解任何大型代码库都很困难，因此程序员需要并值得拥有每一种有用的工具和技术来帮助他们理解复杂的代码库。

静态程序分析是其中一类工具，它由程序或算法组成，旨在从另一个程序的源代码中提取事实，而无需执行该程序，并且通常作为日常软件开发过程中的一个独立阶段。使用静态程序分析工具（通常简称为静态分析）的软件开发人员有机会使用分析产生的事实来进一步理解、评估和修改相关的代码库。

可以从源代码中提取的事实分为许多不同的类别。例如，旨在发现安全漏洞的静态分析将提取有关程序使用的函数和库的信息，而旨在美化或标准化代码布局的分析将关注语法结构的放置和位置。从代码中提取的其他常见事实包括死代码检测，它指示永远无法到达的代码路径；不安全 API 的使用，例如 C 语言的 gets() 函数；污点分析，它识别和监控可能被恶意数据污染的值的使用；竞争条件检测，它识别由程序执行线程之间的交互产生不正确或不可预测结果的代码模式；以及边界检查，它确保对数组或内存位置的访问落在程序员预期的边界内。

静态分析与动态分析（如 valgrind）不同，后者在程序运行时从中提取事实，也与模型检查不同，后者验证程序单独的外部规范的正确性。动态分析和静态分析通常在许多应用中串联使用。静态分析比动态分析具有一些优势。其中一个优势是，静态分析通常在程序中所有可能的执行分支上运行，而动态分析只能访问当前正在执行的代码路径。然而，反之亦然：动态分析具有关于运行程序内存中数据布局和位置的具体信息，而静态分析则必须猜测给定的语言、编译器、操作系统和计算机架构将如何表示给定的数据。两者之间也存在一定程度的重叠；动态分析和静态分析都可以检测到 C 系列语言中未初始化变量的使用，这是一种常见的编程错误。

静态分析在现代软件工程中无处不在。流行的例子包括安全漏洞扫描器，如 Coverity 和 CodeQL；程序员错误检测工具，如 scan-build，这是 LLVM 项目提供的分析工具，目标是 C、Objective-C、C++ 和 Swift；代码格式化程序，如 Python 的 black 或 Go 的 gofmt；以及面向用户的编辑器工具，如 Rust 的 rust-analyzer。

静态分析的概念也位于其他几个领域的核心。例如，编译器设计本身就是一个活跃的研究领域，但静态分析是编译器作者工具包中的基本构建块，大多数编译器在代码生成前后都会运行许多单独的静态分析。实际上，你可以将编译器从宏观上视为一个静态分析工具，其中生成的事实包括可执行程序以及任何适用的调试信息。然而，静态分析一词通常指的是可以与编译器或构建系统一起使用的外部工具。

静态分析的实践存在一些根本性的限制。一种有用的静态分析，终止分析，关注的是预测给定源代码，该代码最终会完成运行还是无限循环。艾伦·图灵在 1936 年的一项开创性证明⁷ 中指出，没有算法能够确定所有可能的程序输入的这一属性。因此，终止分析以及许多其他可以证明等同于停机问题的程序属性，在其能力方面具有上限。这种分析可以接近完美，但永远无法针对所有可能的输入达到完美。这种限制意味着静态分析通常仅限于产生程序行为的近似值。然而，在实践中，近似值通常可能已足够有用。

历史视角

要讨论静态分析的历史，我们必须区分pass和tool。静态分析 pass 包括对给定代码片段的遍历，从中提取一个或一组事实，而静态分析工具是一个程序，通常与程序执行机制（如解释器或编译器）分开，它使用一个或多个分析 pass 向用户产生一组事实。静态分析 pass 在独立工具出现之前就已作为现有程序的一部分出现。

格蕾丝·霍珀海军上将 1952 年的开创性论文《计算机教育》规定了编译器需要访问的一组事实，以便正确生成代码²。类型推断算法的首次开发是在 1958 年；这些程序既能够检查程序中值的声明类型，又能够反过来推断没有显式声明的值的类型。接下来的十年见证了优化编译器内分析 pass 的研究涌入；RCA 实验室 1965 年的一篇论文概述了一种编写程序的方法，该程序“将检查任何其他程序，并对其执行简化，这些简化可以仅从参数程序的格式中检测到，而无需了解它将做什么”⁶。

今天的静态分析工具的概念，作为与编译器或解释器分离的阶段被调用，在 20 世纪 70 年代现代软件开发技术的兴起期间发展起来。最早流行的分析工具之一是 Stephen C. Johnson 于 1978 年编写并在 1979 年发布的 Version 7 Unix 中公开发布的 lint，它检查 C 程序中的错误。那个时代的 C 编译器执行的正确性检查远少于现代编译器，并且 lint 引入了几种持久流行的分析，例如关于可疑类型转换、不可移植的结构以及未使用或未初始化变量的警告——尽管如今这些警告通常是 C 编译器本身的一部分。

虽然 lint 填补了一个重要的空白并得到广泛使用，但它很容易发出误报结果，这需要程序员使用旨在抑制警告的辅助信息来注释他们的程序。Lint 被证明非常有影响力，以至于它的名字被赋予了许多编程语言中的一整类工具——linters。

与此同时，静态分析受到了计算机科学理论导向分支的关注。Patrick 和 Radhia Cousot 在 1977 年 SIGPLAN 会议上发表的一篇论文中介绍了抽象解释背后的理论，为静态分析提供了一种正式的数学方法¹。抽象解释形式化了程序行为近似的概念：停机问题以及可以简化为停机问题的许多其他问题是不可计算的，这意味着行为近似是唯一可行的前进道路。

抽象解释方法允许分析考虑问题中控制流的所有可能分支，并详细说明如何将程序每个部分的近似行为组合成整个程序的近似行为。抽象解释在实践中被证明是一种极其有用的方法；许多后续的分析工具都建立在抽象解释之上，并且它仍然是一个活跃的研究领域。

随着时间的推移，静态分析成为许多软件开发方法的基本组成部分。静态分析工具最突出的用户之一是 NASA（美国国家航空航天局）。其软件工程与保障手册，一份确立有时甚至强制执行软件开发过程各个方面的文件，在其最早的版本中确立了 NASA 软件必须接受可用分析工具的静态分析⁴。本手册确立了静态分析是项目经理和相关工程部门的基本责任。开发安全关键软件（如航空电子软件或医疗设备固件）的公司热情地采用了静态分析；诸如 MISRA C 之类的编码标准，这是一套流行的指南，用于开发由汽车工业软件可靠性协会开发的 C 语言安全关键嵌入式系统，强制使用此类工具。

实现和开发

正如 lint 针对 C 语言一样，大多数现实世界的静态分析工具都针对单一语言或语言系列，因为语言之间的语法和语义差异很大。语言的功能对任何相关分析工具的行为和要求都有巨大的影响；例如，针对支持字符串运行时代码评估 (eval()) 的语言（如 JavaScript 和 Python）的工具必须考虑到这些功能。Python 的全面漏洞扫描器会在遇到在不受信任的用户输入上调用 eval() 的代码路径时警告程序员。在没有 eval() 的语言中，程序员无需考虑这一点。相反，针对高级语言的分析不需要考虑低级内存访问的风险。

有很多方法可以将静态分析引入代码库。最流行的方法包括与 VCS（版本控制软件）集成，如 Git；许多 VCS 服务（免费或商业）都提供了一个平台来集成静态分析工具，以便在新代码推送到存储库时按需执行分析。静态分析工具还与 CI（持续集成）服务集成，这些服务管理在添加或删除代码时构建和打包软件的过程。大多数 CI 服务允许其用户指定，如果分析工具报告意外结果，则应使他们的构建过程失败。想要编写自己的静态分析的用户通常会为现有的分析框架编写扩展；例如，scan-build 提供了一个 API，使最终用户能够hook到 LLVM 的内部流程中，并利用 LLVM 丰富的工具来遍历和分析程序的语法树。

值得注意的是，静态分析及其相关语言之间的交互是双向的；随着分析的演变，它们推动了编译器和相关工具的开发。现代的一个例子是 Swift 编程语言的开发。Swift 的前身 Objective-C 最初使用一种内存管理风格，即手动引用计数，这要求程序员指定给定对象的内存应何时持久化（“retain”），以及何时应放弃（“release”）。这个过程容易出错；因此，与 Clang 编译器相关的静态分析项目引入了检查程序员是否正确插入了 retain 和 release 的能力。

这种管理可以检查正确性的事实促使人们意识到，Objective-C 内存管理的全部内容都可以由编译器自动化。这一洞察力促使 ARC（自动引用计数）的引入，为一种具有正式内存管理策略的语言（即 Swift 本身）铺平了道路，在该语言中，内存管理通常是完全自动化的。同样，描述类型推断分析的文献启发了 ML 语言系列的发展，并帮助将类型推断引入到缺乏类型推断的语言中，例如 C++。

现代实践

静态分析以多种方式体现在编程实践中。最直接的分析方法涉及最终用户在其本地机器上运行分析。许多流行的文本编辑器和 IDE（集成开发环境）自动集成静态分析工具，在程序员开发软件时直接向他们提供分析反馈。

如前所述，CI 和 VCS 服务通常提供钩子，将静态分析集成到开发和构建过程中。然而，许多静态分析是不可见的。毕竟，编译器本身就是一种静态分析，由数十个单独的分析 pass 构建而成，产生计算机可执行的工件。甚至文本编辑器也执行自己的分析。语法高亮几乎在所有编辑器中都很常见，它是一种静态分析，可以产生关于程序中使用的标识符和关键字的语义角色的信息。此外，开发期间使用的大部分软件都经过静态分析，直至操作系统，甚至可能是 CPU 的微代码。

并非所有分析在实践中都是可行的。代码库越大，解析和遍历所需的时间就越长；此外，许多静态分析在执行它们所需的空间或时间方面计算成本很高——通常是二次方，有时甚至是三次方。因此，静态分析和被分析的代码库之间存在一场军备竞赛。随着代码库变得越来越大，程序员需要更复杂和高效的分析。

程序员采用静态分析工具的一个障碍——也许是最重要的障碍——是要求人类改变他们的行为以解决发现的问题和出现的警告。自 lint 时代以来，程序员一直在努力消除与给定分析的误报结果相关的警告；补救措施通常包括在代码中插入“魔法注释”，依靠给定的分析工具来扫描并适当地禁用相应的警告。然而，手动插入这些指令可能很乏味，程序员通常会选择不使用产生过多误报的静态分析工具。

同样，漏报（例如未检测到的安全漏洞）可能会给程序员对代码正确性的毫无根据的信心。程序员可以通过仔细配置给定的工具来解决误报；漏报更难发现，但可以通过串联使用多个静态分析工具来降低风险。此外，分析可能会检测到在理论上有效但在实践中是良性的问题，例如违反了 C 语言中对命名标识符的众多繁琐限制。

展望未来

现代静态分析工具提供了对代码库的强大而具体的见解。例如，Linux 内核团队开发了 Coccinelle，这是一个用于搜索、分析和重写 C 源代码的强大工具；由于 Linux 内核包含超过 2700 万行代码，因此静态分析工具对于查找错误和在其众多库和模块中进行自动化更改至关重要。另一个针对 C 系列语言的工具是 Clang scan-build，它附带了许多有用的分析，并为程序员提供了编写自己的分析的 API。

基于云的工具（如 LGTM.com）与现有的构建和发布流程集成，并跨多种编程语言工作。与静态分析相关的高级协议也已经出现。语言服务器协议是一组通用定义，用于标准化分析工具与 Emacs 和 VS Code 等文本编辑器交互的方式，确保分析工具可以与其选择的工具无关地集成到程序员的工作流程中；同样，SARIF（静态分析结果交换格式）为静态分析工具产生的输出提供了一个标准。

针对检测安全漏洞的静态分析子领域继续吸引工业界和研究界的关注。随着安全漏洞的后果变得越来越严重，静态分析的效用也在增加。诸如 Spectre (CVE-2017-5753) 之类的漏洞暴露了与计算机 CPU 内的推测执行相关的安全缺陷，促使人们开发专门用于检测该类别漏洞的分析工具。许多分析工具都利用 CVE（常见漏洞和暴露）和 CWE（常见弱点枚举）数据库中的特定漏洞和反模式。

软件工程的根本挑战之一是复杂性。大型软件产品是有史以来最复杂的人类努力之一。更增加这一负担的是其短暂的历史——人类构建软件的时间只有短短 50 年，而建筑或医学等其他领域则有数千年的历史。

最重要的是，随着新平台、操作系统和编程语言的出现，软件生产机制每年都变得更加复杂。工业软件的复杂性通常增长速度超过其作者管理这种复杂性的能力，这一事实是软件工程和计算机科学作为学科所面临的核心挑战之一。在这场战斗中，我们拥有的武器寥寥无几，但静态分析是最有效的武器之一，对开发工作和缺陷率的众多元分析证明了这一点⁵。

就像计算机科学中的许多事物一样，静态分析的效用是自指的：为了编写可靠的程序，我们还必须为我们的程序编写程序。但这并非悖论。静态分析工具，尽管其理论和实践可能很复杂，但它们将使我们以及未来的工程师能够克服这一挑战，并产生我们从业者应得的知识和见解。

参考文献

1. Cousot, P., Cousot, R. 1977. 抽象解释：通过构造或逼近不动点对程序进行静态分析的统一格模型。载于第四届 SIGPLAN-SIGACT 程序设计原理研讨会会议记录，加利福尼亚州洛杉矶，238-252 页。纽约州纽约：出版社； https://dl.acm.org/doi/10.1145/512950.512973。

2. Hopper, Adm. G. M. 1988. 计算机教育。计算机历史年鉴 9(3-4), 271-281; https://dl.acm.org/doi/10.1109/MAHC.1987.10032。

3. Kemerer, C. F. 1995. 软件复杂性和软件维护：实证研究综述。软件工程年鉴 1(1), 1-22。

4. NASA 首席工程师办公室。2011. 软件工程与保障手册。美国国家航空航天局。SWE-135。 https://swehb.nasa.gov/display/SWEHBVC。

5. Nichols, W. R., Jr. 2020. 开发期间静态分析的成本和收益。arXiv:2003.03001; https://ui.adsabs.harvard.edu/abs/2020arXiv200303001N。

6. Nievergelt, J. 1965. 关于计算机程序的自动简化。通讯 8(6), 366-370; https://doi.org/10.1145/364955.364963。

7. Turing, A. M. 1937. 论可计算数，及其在判定问题中的应用。伦敦数学学会会刊 s2-42(1), 230-265; https://doi.org/10.1112/plms/s2-42.1.230。

帕特里克·汤姆森是 GitHub Inc. 的高级工程师，致力于全球最大的代码语料库的静态分析。他住在纽约市。

最初发表于 Queue vol. 19, no. 4—
在数字图书馆中评论本文

更多相关文章

凯瑟琳·海耶斯，大卫·马龙 - 质疑评估非加密哈希函数的标准
虽然加密和非加密哈希函数无处不在，但在它们的设计方式上似乎存在差距。加密哈希存在许多由各种安全要求驱动的标准，但在非加密方面，存在一定程度的民俗，尽管哈希函数历史悠久，但尚未得到充分探索。虽然针对真实世界数据集的均匀分布很有意义，但在面对具有特定模式的数据集时，这可能是一个挑战。

妮可·福斯格伦、埃里尼·卡利亚姆瓦库、阿比·野田、米凯拉·格雷勒、布莱恩·豪克、玛格丽特-安妮·斯托里 - DevEx 在行动
随着领导者寻求在财政紧缩和人工智能等变革性技术的背景下优化软件交付，DevEx（开发者体验）在许多软件组织中越来越受到关注。技术领导者凭直觉接受良好的开发者体验可以提高软件交付效率和开发者幸福感。然而，在许多组织中，旨在改善 DevEx 的拟议倡议和投资难以获得支持，因为业务利益相关者质疑改进的价值主张。

若昂·瓦拉乔、安东尼奥·特里戈、米格尔·阿尔梅达 - 低代码开发生产力
本文旨在通过展示使用基于代码、低代码和极端低代码技术进行的实验室实验结果，研究生产力差异，从而为该主题提供新的见解。低代码技术已清楚地显示出更高的生产力水平，为低代码在短期/中期内主导软件开发主流提供了强有力的论据。本文报告了程序和协议、结果、局限性和未来研究的机会。

伊瓦尔·雅各布森、阿里斯泰尔·科伯恩 - 用例至关重要
虽然软件行业是一个快节奏且令人兴奋的世界，其中不断开发新的工具、技术和技术来为商业和社会服务，但它也很健忘。在其快速前进的匆忙中，它容易受到时尚的 whims，并且可能会忘记或忽略已证实的解决其面临的一些永恒问题的方法。用例最早于 1986 年引入，后来广受欢迎，就是这些经过验证的解决方案之一。