程序分析

自动化处理检查程序性能、正确性、安全性的过程

程序分析

程序分析（Program Analysis）是一种旨在自动化处理计算机程序，以确认或发现程序如性能、正确性、安全性等特性的技术。[0]其主要应用于错误检测、性能优化和安全性分析等领域。[2]程序分析涵盖了多种方法，其中动态程序分析方法在程序运行时进行分析，深入挖掘程序的执行路径和行为特征；[3]而静态程序分析方法则在编译阶段提前对程序进行分析和检测，以发现潜在的问题和漏洞。[7]这两种方法目前被广泛应用，它们通过控制流分析[1]、数据流分析[5]、过程间分析[8]、符号执行[4]、污点分析等关键技术，揭示程序内在的运行机制和潜在的安全隐患。[5]除此之外，还有形式化方法和混合方法，丰富了程序分析的技术体系。[7]

程序分析（Program Analysis）是一种旨在自动化处理计算机程序，以确认或发现程序如性能、正确性、安全性等特性的技术。[1]其主要应用于错误检测、性能优化和安全性分析等领域。[3]

程序分析涵盖了多种方法，其中动态程序分析方法在程序运行时进行分析，深入挖掘程序的执行路径和行为特征；[4]而静态程序分析方法则在编译阶段提前对程序进行分析和检测，以发现潜在的问题和漏洞。[8]这两种方法目前被广泛应用，它们通过控制流分析[2]、数据流分析[6]、过程间分析[9]、符号执行[5]、污点分析等关键技术，揭示程序内在的运行机制和潜在的安全隐患。[6]除此之外，还有形式化方法和混合方法，丰富了程序分析的技术体系。[8]

经过多年的发展，程序分析已成为剖析复杂软件系统、提高软件质量的重要手段。针对不同的软件形态，已经发展出众多程序分析技术，并开发出高效率的自动化分析工具，[6]如在移动应用开发中，程序分析可被用于多线程程序的并发缺陷检测，帮助开发者发现并解决潜在的安全隐患和性能问题。[10]随着软件应用范围的拓展和对软件可靠性要求的提高，程序分析在软件开发和维护过程中也发挥着作用。[11][12]

早期程序分析方法

20世纪50年代至70年代，静态分析方法的出现标志着程序分析早期阶段的开始。John Backus（约翰·巴克斯）和Peter Naur（彼得·诺尔）等代表人主要依赖于静态分析方法，在编译时或运行前对程序代码进行分析，以发现潜在的错误和漏洞。Backus在1957年发表了《The FORTRAN Automatic Coding System》[13]，这标志着高级程序设计语言FORTRAN的诞生；而Naur在1960年发表了《Revised Report on the Algorithmic Language ALGOL 60》[14]，成为ALGOL 60的主要设计者之一。这些静态分析方法包括语法分析、类型检查和控制流分析等。[14]

形式化方法的兴起

在20世纪70年代至80年代，形式化方法开始受到重视。Tony Hoare（托尼·霍尔）和Edsger W. Dijkstra（艾兹格·迪科斯彻）等代表人主要贡献了形式化方法的发展。Hoare在1969年发表了《An Axiomatic Basis for Computer Programming》[15]，提出了著名的Hoare逻辑，为程序验证领域奠定了基础；而Dijkstra在1965年发表了《Cooperating Sequential Processes》[16]，探索了并发程序设计的基础理论。形式化方法是一种基于数学模型的程序分析技术，旨在证明程序的正确性或指出程序中的错误。这些方法包括模型检查、定理证明和抽象解释等。[16]

符号执行与数据流分析的出现

20世纪80年代至90年代见证了符号执行和数据流分析技术的发展。James C. King（詹姆斯·金）和François Bourdoncle（弗朗索瓦·布尔东克勒）等代表人主要贡献了这一时期的研究。King在1976年发表了《Symbolic Execution and Program Testing》[17]，开创了符号执行技术的先河；而Bourdoncle则在1993年发表了《Efficient chaotic iteration strategies with widenings》[18]，推动了数据流分析技术的发展。符号执行是一种静态分析技术，用于模拟程序执行路径并发现潜在的错误和漏洞。数据流分析则用于分析程序中数据的流动情况，发现数据依赖性和未初始化变量等问题。[18]

动态分析技术的发展

随着20世纪90年代至今，动态分析技术开始受到关注。Barton P. Miller（巴顿·米勒）和Robert DeLine（罗伯特·德林）等代表人成为了该领域的贡献者。Miller等人在1995年发表了《Fuzz Revisited: A Re-examination of the Reliability of UNIX Utilities and Services》[19]，推动了动态程序分析技术的发展；而Benjamin Livshits等人在2017年发表了《Enabling Defensive Programming with Optimistic Dynamic Analysis》，为动态检查器的开发提供了基础。动态分析技术通过捕获程序的实际执行信息，在程序执行时进行分析和优化。它可以用于性能分析、内存泄漏检测、安全漏洞检测等领域。[20]

特点

被分析对象的多样性：程序分析对象包括源代码和二进制可执行代码，且程序规模差异巨大。[8]程序性质的多样性：不同类型程序关注的性质各异，如C程序可能关注指针问题、内存泄漏等，而嵌入式系统可能更关注中断处理等问题。[8]明确的目的性：程序分析有明确的目的，可用于发现代码中的错误、提升代码质量或改进程序性能等。[21]方法和技术的多样性：包括静态分析、动态分析、符号执行和数据流分析等，以适应不同需求和情境。[22]更高级方法的涌现：如模型检查、抽象解释和符号执行，提供更为精确和深入的分析结果。[22]上下文的敏感性：考虑到代码的上下文环境对程序分析的重要性，提高了分析的精度和可靠性。[23]良好的可扩展性：随着软件规模和复杂度的增加，程序分析需要具备良好的可扩展性，以处理大型代码库和复杂程序结构。[24]一定程度的交互性：程序分析工具通常具有一定程度的交互性，使用户能够调整参数、查看结果并进行进一步的探索和优化，提高了分析的效率和效果。[25]

动态程序分析

动态程序分析是一种在运行目标程序时进行的分析技术。在目标程序结束运行后，动态分析生成一个包含程序行为信息的概要文件。其主要优点在于能够产生详细且准确的信息。为了提高代码覆盖率，通常需要多次运行目标程序，并采用不同的输入和路径[26]。动态符号执行和动态污点分析是动态程序分析的两种常见技术。由于动态分析需要实际运行被测试程序，因此其分析开销较大。此外，动态分析只能对已执行的程序代码进行分析，无法分析尚未执行的代码，因此提高代码覆盖率是动态分析技术的重要挑战。[27]尽管如此，动态分析的最大优势在于能够获取程序运行时的信息，因此具有较高的准确性。[4]

静态程序分析

静态程序分析是一种在编译期间对代码进行检查的技术，它利用数据流和控制流等信息，在不运行目标程序的情况下进行分析和检测。大多数现代编译器能够自动进行静态分析，其优点在于能够在运行程序之前指出代码的潜在问题，减少调试次数并节省时间。[28]然而，由于缺乏运行时信息，静态分析的准确性可能不佳，可能会产生大量误报。现代IDE工具利用静态分析来检测代码中的潜在问题，如空指针、内存泄漏和死代码，以提高代码质量并节省调试时间。[4]相较于动态分析，静态分析能够确保对代码的100%覆盖率，尽早发现和解决潜在错误，提高软件的可靠性和稳定性。[27][26]

错误检测

程序分析技术在错误检测方面起到关键作用，有助于开发人员识别代码中的潜在缺陷和错误。通过静态分析，在代码编译之前可以发现诸如逻辑错误、未初始化的变量、内存泄漏等问题。同时，动态分析技术能够实时捕捉程序错误，如数组越界、空指针引用等，帮助开发人员及时定位和修复这些问题。[10]

性能分析

在性能分析方面，程序分析技术可以帮助开发人员分析代码的执行效率。通过性能剖析工具，识别出程序中执行最频繁的代码段（热点），从而针对性地进行优化，提高程序的执行效率。此外，程序分析还可以帮助开发人员分析内存使用情况，发现内存泄漏和不必要的内存占用，进一步优化内存管理，提升程序的性能。[6]

安全性分析

在安全性分析方面，静态程序分析技术可以检测代码中潜在的安全漏洞，如缓冲区溢出、SQL注入等。同时，动态分析技术可以监控程序的运行时行为，发现潜在的安全风险。这些分析技术能够帮助开发人员在软件开发过程中及时发现并解决安全问题，提高软件的安全性和可靠性。[6]

代码质量分析

在代码质量分析方面，着眼于评估和提升代码的可读性、可维护性、性能和安全性等关键指标，是程序分析中的重要环节。代码质量分析通过系统性的检查和评估，帮助开发团队发现潜在的问题，并制定改进方案以提高代码的质量水平。例如重构技术可以帮助开发者改进代码的可读性和可维护性，进而提高软件项目的质量。[29]

函数级分析

函数级分析聚焦于单个函数或方法的内部结构和实现细节，以评估其功能性、性能和可维护性等方面。其主要用于检查函数的输入输出关系、执行逻辑、异常处理、资源利用情况等，以确保函数功能正确、性能高效和易于维护。[30][31]

模块级分析

模块级分析关注于软件系统中的模块或组件，评估其与其他模块之间的交互、接口设计、内部结构和功能完整性等方面。其旨在确保模块之间的协作顺畅、接口稳定、功能完整，并通过优化模块间的通信和依赖关系，提高系统的可扩展性和可维护性。[32]

系统级分析

系统级分析从整体角度考虑软件系统，评估系统的架构设计、性能特征、安全性和可用性等方面。其通过分析系统的整体结构和行为，发现系统级别的问题和潜在风险，制定综合的优化方案，确保系统的稳定运行和满足用户需求。[30][33]

手工分析

手工分析是一种依赖于人工经验和专业知识的过程，通过人工阅读、检查和评估源代码或软件系统来发现问题、优化性能或改进质量。[34]手工分析具有灵活性，能够根据特定的需求和目标进行定制和调整，然而，它需要耗费大量时间和人力。通常手工分析用于对关键代码部分、特定功能模块或复杂问题进行深入分析和诊断，以辅助自动化分析，发现自动化工具无法捕捉的问题或特定需求。[32]

自动化分析

自动化分析利用计算机程序和工具对源代码或软件系统进行自动化检测、评估和处理。自动化分析工具能够在短时间内对大量代码进行分析，提高分析效率，同时具有一致性。[35]然而，自动化分析工具可能无法覆盖所有情况，有些复杂问题仍需要人工介入。自动化分析广泛应用于代码质量评估、静态程序分析、性能测试、安全漏洞扫描等方面，帮助发现潜在问题、优化代码结构、提高性能和安全性。[36]

静态程序分析

过程间分析

过程间分析（inter-procedural analysis，IPA) 指的是在对程序进行静态分析时，考虑程序中各个函数之间的关系和相互影响。它是一个多步的过程，是LT分析过程中的重要部分，也是一个跨模块的分析过程。跨模块的优化功能实现最早在1987年(Link time optimization -MIPS)，后来相继出现了过程间分析和转换，动态链接程序的优化(IPA+LTO)。[9][37]

数据流分析

数据流分析是关键的程序分析技术，用于追踪控制流图中的程序状态信息传播，以预测运行时各点可能的状态。它采用抽象的格结构来表示状态集合，并通过单调转移函数更新状态。此分析可前向或后向执行，映射状态信息的流动方向，依据控制流图的多分支交汇点确定程序状态。[6]

在编译器优化中，数据流分析被用于常数传播、部分冗余消除等任务，通过迭代至固定点的方法来实现，避免了复杂算法的需求。[26]它主要应用于过程内分析，而过程间分析则通过函数摘要实现。[6]作为静态分析技术的一个应用，数据流分析对软件工程和编译优化至关重要。[4]

污点分析

污点分析可用于跟踪分析程序中污点数据流动。它通过监控程序内部的数据流向和分析数据监控，检测可能存在的敏感数据泄露或危险操作等违反数据完整性和保密性的安全漏洞。污点分析通常结合了上下文敏感的别名分析和多源绑定技术，以准确地检测Java程序中的漏洞。其核心目标在于对污点传播路径进行分析，利用程序依赖信息来跟踪污点数据在程序中的传播路径，以发现可能的安全风险。[38]

污点分析是一种静态分析方法，通过分析源代码或二进制代码的结构和属性来推断程序的行为，而无需实际运行程序。在污点分析中，结合了别名分析和多源绑定技术，这些技术都是静态分析的一部分。[26][38]

污点分析过程图
污点分析过程图

抽象解释

抽象解释是一种通用理论，用于对程序语义进行可靠的抽象或近似。它提供了一个框架，保证了构建的程序分析的终止性和可靠性，同时考虑了所有的程序行为。通过对程序语义进行不同程度的抽象，在分析精度和计算效率之间取得权衡。利用抽象解释，可以提高程序分析的效率和准确性。[6]

静态分析是通过分析程序的源代码或二进制代码的结构和属性来推断程序的行为。抽象解释通常作为一种通用理论，在静态分析的背景下进行应用。[6][26]

静态符号执行

静态符号执行是一种精确的程序分析技术，利用符号化输入模拟程序执行。当遇到条件语句时，程序会根据分支情况分叉执行，并将分支条件作为当前路径的路径条件。它通过调用 SAT/SMT 求解器，判断程序执行路径的可行性，支持自动测试、缺陷查找等软件验证活动。[6]

静态程序切片

静态程序切片技术是一种分析程序代码的方法，通过将程序分解并提取特定的语句序列来满足分析人员的需求。它基于指令的控制流和数据流，分析指令的执行序列以及数据的产生、复制、传递和消失过程，最终生成所需的代码片段。[39]

动态程序分析

动态符号执行

动态符号执行是一种新兴的软件漏洞检测方法，结合具体执行和符号执行。它通过在程序真实运行中收集路径约束来判断需要符号执行的代码，并生成新的输入来测试程序。监控程序执行状态，发现异常可能表示漏洞，进一步分析异常确认漏洞类型。[6][5]

动态程序切片

动态程序切片技术是一项重要的软件分析技术。其已广泛应用于程序调试、软件测试、软件维护和错误定位等任务。主要分为基于前向计算和基于后向分析两种方法。前向计算方法根据兴趣点动态依赖节点计算切片，需要维护节点的切片信息。后向分析方法通过回溯动态依赖关系找到兴趣点的直接和间接依赖节点集合生成切片。这两种方法都需要维护大量中间信息，产生动态依赖关系。[40]

混合方法分析

混合方法是程序分析领域中的一种方法论，它结合了静态分析和动态分析两种技术手段。[4]静态分析在编译期间对程序进行分析，但有时难以捕捉到程序的全部行为；动态分析在程序运行时收集信息，但覆盖率可能有限。混合方法将这两种分析技术结合起来，提高了程序分析的全面性和准确性。[26]

控制流分析

控制流分析是程序分析领域的重要技术，用于理解程序的执行流程。在控制流分析中，主要方法包括利用必经点找到环和区间分析。前者利用必经点找到程序中的环，随后对环进行解释优化。这种方法适用于使用迭代数据流分析的优化器或对子程序中环感兴趣的分析。后者包括分析子程序的整体结构，将其分解为区间（interval）[注1]。区间的嵌套结构构成一棵树，称为控制树，用于数据流分析。[2]

在控制流分析中，静态分析方法主要包括利用必经点找到环以及区间分析，而动态分析方法则是在程序运行时收集控制流信息。[2]结合静态分析和动态分析方法可以更全面地理解和优化程序的控制流程。[26]

形式化方法分析

形式化方法是一种采用数学方法的系统设计与验证方法，旨在建立对复杂计算机系统严格的语法和语义规范。它在计算机硬件设计、软件系统构造、控制系统模型设计与分析等领域得到广泛应用，以提高系统的安全性和可靠性。该方法还在新兴领域如深度学习、区块链、量子计算等得到逐步应用。形式化方法通过严格的数学基础和形式验证，能够证明程序不存在某类 bug，但其实际应用受到数学证明难度大以及代码求解量大的限制。[4]

程序分析方法优点缺点
静态程序分析在编译期间进行，无需运行程序，提前发现潜在问题，减少调试次数和节省时间。[26]
可被现代编译器能够自动进行，提高代码质量和开发效率。[27]
可利用上下文准确地检测程序中的漏洞，提高代码的安全性。[38]
利用抽象解释进行可靠的程序语义抽象，保证分析的终止性，防止分析陷入死循环。[6][26]
在考虑所有程序行为的同时，通过不同程度的抽象，权衡了分析的精度和计算效率。[6]		由于缺乏运行时信息，可能会产生大量误报，导致准确性不佳。[26]
通常受限于程序的结构，可能无法捕捉到所有的行为和路径，从而影响分析的全面性和准确性。[26]
需要权衡精度和效率，可能会因为过高或过低的抽象粒度而导致分析结果的不准确性或计算效率低下。[6][26]
动态程序分析在运行目标程序时可生成详细的程序行为信息。[4]
能够获取程序运行时的信息，具有较高的准确性。[26]
结合了具体执行和符号执行，用于发现软件漏洞。[5]		由于需要实际运行被测试程序，开销较大。[6]
无法分析尚未执行的代码。[5]
为提高代码覆盖率，通常需要多次运行目标程序，并采用不同的输入和路径。[40]
需要维护大量的中间信息，包括动态依赖关系，导致分析过程复杂。[39][40]
混合方法将静态分析和动态分析结合，弥补了它们各自的不足，使得程序分析更加全面和准确。[26]
能够更全面地理解和优化程序的控制流程，提高程序的性能和可靠性。[26]		由于需要进行静态分析和动态分析，并结合它们的结果，程序分析的复杂度、成本较高。[2]
静态分析和动态分析得到的结果可能存在信息不一致的情况，故需要进行合理的处理和权衡。[2][26]
形式化方法采用严格的数学方法建立系统的语法和语义规范，帮助提高系统的安全性和可靠性。[4]
通过进行形式验证，证明程序在某些方面不存在特定类型的错误或缺陷，提高程序的质量，适用范围广泛。[4]		需要严格的数学基础和形式化验证，其中的数学证明难度较大，需要专业的知识和技能进行处理。[4]
在实际应用中，需要处理大量的代码求解，增加分析的复杂度和成本，限制使用场景[4]

工具平台

程序分析的工具平台是用于执行各种程序分析任务的软件工具集合。这些工具平台通常提供了一系列功能，包括静态分析、动态分析、代码审查等。它们旨在帮助开发人员发现和解决软件中的错误、优化代码、改进性能等。[7][41][42]

程序分析的主要工具平台如下表：

工具用途适用代码类型平台logoSonarQube[43]开源的代码工具，用于提升代码质量支持多种语言[44]Gerrit[45]开源的代码审查工具，支持代码审查工作流程的管理包括但不限于Java、C/C++、Python等[7]PMD[46]开源的代码工具，用于代码静态分析可用于 Java、JavaScript、Apex 等[41]FindBugs[47]开源的代码静态分析工具，用于查找常见的编程错误用于Java[48]Cppcheck[49]开源的代码静态分析工具，用于发现代码中的缺陷用于C/C++ [50][51]Valgrind[52]开源的代码动态程序分析工具集，用于检测内存泄漏、错误使用内存等问题用于Linux[42]GDB (GNU Debugger)[53]开源的代码工具，用于调试程序并进行动态分析的工具主要用于C、C++等[54]VisualVM[55]开源的代码性能分析工具，用于分析内存主要用于Java [54]

展望及挑战

未来，程序分析将继续发挥重要作用，成为剖析复杂软件系统和提高软件质量的关键手段。随着软件工程、程序设计语言、操作系统、信息安全等领域的不断发展，对程序分析的需求将愈发增加。经过多年的发展，程序分析已取得了长足的进步，研究人员将程序语言理论与编译、人工智能、数据处理等技术相结合，开发了众多高效的自动化分析工具，为软件缺陷和漏洞的发现提供了重要帮助。然而，当前的程序分析技术仍面临一系列挑战，如准确性和可扩展性等方面的问题。另外，随着新型软件形态的出现，如智能合约和深度学习等，也需要全新的程序分析技术来应对挑战。因此，未来的程序分析将需要不断创新和进步，以满足不断变化的软件应用需求，提高软件开发和维护过程中的效率和可靠性。[6]

参考资料 55

  1. 参考 1
  2. 参考 2
  3. 参考 3
  4. 参考 4
  5. 参考 5
  6. 参考 6
  7. 参考 7
  8. 参考 8
  9. Interprocedural analysis (IPA) — IBM
  10. 参考 10
  11. 参考 11
  12. 中国学科发展战略·软件科学与工程 — 中国科学院学部
  13. 参考 13
  14. 参考 14
  15. 参考 15
  16. 参考 16
  17. 参考 17
  18. 参考 18
  19. 参考 19
  20. 参考 20
  21. https://www.semanticscholar.org/paper/Precise-interprocedural-dataflow-analysis-via-graph-Reps-Horwitz/91728fca6699c2e4cadc38f629cc9f8d416db154
  22. 参考 22
  23. 参考 23
  24. 参考 24
  25. 参考 25
  26. 参考 26
  27. 参考 27
  28. 参考 28
  29. 参考 29
  30. 微认证：鲲鹏软件性能调优实践 — 华为云
  31. 参考 31
  32. 参考 32
  33. 参考 33
  34. 参考 34
  35. 参考 35
  36. 参考 36
  37. 编译优化之 - 过程间优化(IPA/IPO)入门 — CSDN
  38. 参考 38
  39. 参考 39
  40. 参考 40
  41. 参考 41
  42. 参考 42
  43. SonarQube — sonarqube
  44. 参考 44
  45. Gerrit
  46. PMD — PMD:
  47. FindBugs
  48. 参考 48
  49. Cppcheck
  50. 静态分析工具Cppcheck在Windows上的使用 — CSDN
  51. CppCheck代码静态检查 - 实操总结 — CSDN
  52. Valgrind
  53. GDB (GNU Debugger) — GDB
  54. 参考 54
  55. VisualVM

注释

  1. 可嵌套的（nested）区域
广告位：底部（ad-bottom）—— 请到中台「公共区块」编辑此内容