PL and Static Analysis（程序设计语言与静态分析）

关系图：

	Programming Languages（程序设计语言）
Theory（理论）	Environment（环境）	Application（应用）
Language design（语言设计，主要是语法规则与词法规则）	Compilers（编译器设计）	Program analysis（程序分析，主要是静态分析）
Type system（类型系统）	Runtime system（运行时系统架构）	Program verification（程序验证：证明程序无误）
Semantics and logics（语义规则与逻辑结构）	… …	Program synthesis（程序合成）
… …		… …

Why We Learn Static Analysis?（为什么需要静态分析）

背景：过去几十年程序设计语言的核心几乎没变，但是程序变得越来越大，越来越复杂

挑战：如何在大规模程序下，保证程序的可靠性，安全性。

应用实例：

• program reliability（程序可靠性）：null pointer dereference（空指针引用），memory leak（内存泄露)
• program security（程序安全）：injection attack（注入式攻击），private information leak（隐私信息泄露）
• compiler optimization（编译器优化）：dead code elimination（死代码删除），code motion（代码移动）
• program understanding（代码理解）：IDE call hierarchy（IDE 中的层次调用结构）type indication（类型提示）

附加值：更加深入理解编程语言的语法，语义；自然而然地写出更高效，安全，可靠的程序

What is Static Analysis?（什么是静态分析）

静态分析：分析程序 P，推断其行为，在运行 P 之前判断 P 是否满足某些属性（这些属性就是一些复杂的程序行为，如是否造成内存泄露，是否存在并行程序的内存竞争等）

现实：不幸的是，根据莱斯定理，没有这样的方法来确定 P 是否满足这些属性，即给出确切的答案:是或否。人话就是：没有完美的静态分析，能够使得这些不那么简单的性质（能够直接判断。

莱斯定理：一个程序中任何不平凡的属性都是不可决定的

理解不平凡属性：

• 如果一个属性不被任何正则语言所满足，或者被所有正则语言所满足，那么这个属性就是平凡的;否则它是非平凡的
• 简单来说就是：比较看起来没那么简单就能判断出来的性质

完美的程序静态分析：sound 且 complete（就是 Truth）

sound：也即 overapproximate，所有问题都报出来了，但是存在误报

complete：也即 underapproximate，报出来的问题是真实存在的，但是有漏报

有用的静态程序分析：妥协一方（现实中大部分都运行误报，即满足 sound）

妥协 sound：即满足 complete，造成一定漏报

妥协 complete：即满足 sound，造成一定误报

为什么选择满足 sound

• 对于编译器优化和程序验证等重要(静态分析)应用程序的集合来说，可靠性（soundness,宁可错杀三千，不放过一人）是至关重要的。
• 允许误报，不允许漏报对于改 bug 更加友好，对于程序运行更加友好

Static Analysis Features and Examples（静态分析特征与案例）

两种静态分析：

• may analysis：即考虑程序运行时的所有路径，保证 sound
• must analysis：输出的信息必须为真，保证 complete

may analysis：要实现 abstraction 和 over-approximation 两个部分

栗子：

问题：判断程序中所有变量的符号（+，-，0），用于检测数组索引（不为负），判断除 0

abstraction：（不关心具体值，而是抽象成一种特性）

over-approximation：定义转换函数和控制流汇合方法

• 在静态分析中，转移函数定义了如何评估抽象值上的不同程序语句。
• 转移函数是根据 “要分析的问题 “和不同程序语句的 “语义 “来定义的。
• 转换函数示例：

• 控制流示例：

重点问题

1.静态分析和动态测试有什么区别？

静态分析：

1. 静态分析可以应用于不同级别的代码，包括源代码、字节码和二进制代码。它可以在编译时、构建时或持续集成过程中执行。
2. 静态分析工具使用各种技术和算法来检查代码，例如语法分析、数据流分析、控制流分析、符号执行等。
3. 静态分析可以检测各种问题，包括潜在的编码错误（如空指针引用、数组越界）、代码质量问题（如复杂度、重复代码）、安全漏洞（如注入攻击、XSS）等。
4. 静态分析可以帮助开发人员提高代码质量、减少错误和缺陷，并提供更好的可维护性和可读性。
5. 静态分析也可用于代码规范检查，以确保代码符合特定的编码标准和最佳实践。

动态测试：

1. 动态测试是在运行时执行的，通过实际运行软件并观察其行为来验证系统的功能和性能。
2. 动态测试需要设计测试用例，包括正常情况下的输入、边界条件、异常情况等，以覆盖不同的执行路径和场景。
3. 动态测试可以检测到运行时错误、异常行为、性能问题以及与预期行为不符的功能问题。
4. 动态测试可以使用各种工具和框架来自动化测试过程，并生成测试报告和覆盖率分析。
5. 动态测试可以采用不同的技术，包括单元测试、集成测试、系统测试、回归测试等，以确保软件的正确性和稳定性。

静态分析和动态测试都是重要的软件质量保证技术，它们在不同的阶段和层面上发挥作用。静态分析可以在代码编写和构建过程中发现问题，而动态测试则在实际运行时验证系统的行为。综合使用这两种技术可以提高软件的可靠性、安全性和性能，并降低错误和缺陷的风险。

2.如何理解 soundness, completeness, false negatives, and false positives

1. 完备性（Soundness）：

   • 完备性是静态分析工具的重要属性，它衡量工具是否能够找到所有实际存在的问题。
   • 一个完备的静态分析工具不会漏报任何实际存在的问题，因此它具有较低的假阴性率。
   • 完备性的提高需要使用更精确的分析技术和算法，以尽可能覆盖所有代码路径和可能的问题。

2. 准确性（Completeness）：

   • 准确性是静态分析工具的另一个关键属性，它衡量工具报告问题的可信度和准确性。
   • 一个准确的静态分析工具尽量避免误报，并将其假阳性率保持较低。
   • 提高准确性需要在分析过程中应用更精确的算法和规则，并通过验证和测试来验证工具的结果。

3. 假阴性（False Negatives）：

   • 假阴性是指实际上存在的问题，但静态分析工具未能检测到的情况。
   • 假阴性可能会导致未发现的错误和潜在的安全漏洞，因此它们是完备性的关键衡量指标。
   • 减少假阴性需要改进静态分析算法、增强规则集、提高代码覆盖率等措施。

4. 假阳性（False Positives）：

   • 假阳性是指静态分析工具错误地将实际上不存在问题的代码标记为问题。
   • 假阳性可能会导致开发人员的困惑和误导，并浪费时间和资源。
   • 减少假阳性需要改进算法、调整规则和过滤策略，以提高准确性和可靠性。

评估静态分析工具的性能和结果可靠性时，需要考虑完备性和准确性，以及假阴性和假阳性。一个理想的静态分析工具应该具有较高的完备性和准确性，以最大程度地减少假阴性和假阳性的出现。这样的工具可以帮助开发人员找到更多的问题，并提供可信的结果，从而提高代码质量和软件的可靠性。

3.为什么静态分析通常都要保证 soundness

1. 发现潜在问题：完备性是静态分析工具的核心目标之一。通过保证完备性，工具能够尽可能地发现代码中的潜在问题和缺陷。这包括识别潜在的错误、漏洞和安全风险等。完备性的提高有助于尽早发现并解决这些问题，从而提高软件的质量和安全性。

2. 避免遗漏问题：如果静态分析工具不具备完备性，可能会导致一些问题被遗漏。这些未被检测到的问题可能会在软件运行时引发错误，导致功能故障、安全漏洞或性能问题等。通过保证完备性，可以最大程度地减少遗漏问题的风险，并提高软件的可靠性和稳定性。

3. 提高开发效率：完备性有助于减少开发人员的工作量和时间成本。通过使用完备的静态分析工具，开发人员可以更快速地找到和修复代码中的问题，而不必手动进行全面的代码审查。这提高了开发效率，并有助于及早解决潜在的问题。

4. 信任和可靠性：保证完备性增强了静态分析工具的信任和可靠性。开发人员可以更有信心地依赖工具的结果，并将其作为他们开发流程中的重要参考。可靠的分析工具有助于建立对工具的信任，并提高开发人员对其结果的可靠性。

尽管保证完备性是重要的，但在实践中，完全消除假阳性（false positives）是非常困难的。因此，静态分析工具通常也需要在准确性（completeness）方面进行权衡，以尽量减少假阳性的数量，同时保持较高的完备性。这样可以提供开发人员可信赖、有价值的结果，帮助他们改善代码质量和软件的可靠性。

4.怎么理解 abstraction 和 over-approximation

1. 抽象化（Abstraction）：

   • 抽象化是将复杂的程序语义简化为更简单、更抽象的表示形式的过程。它通过忽略或合并程序的某些细节，以便更有效地进行静态分析。
   • 抽象化的目标是在保持足够准确性的同时，减少分析的复杂性和计算成本。
   • 在静态分析中，常见的抽象化技术包括符号执行、抽象解释和模型检测等。

2. 过近似（Over-approximation）：

   • 过近似是一种分析技术，它在分析过程中对程序行为进行保守估计，即假设可能发生的所有情况都会发生。这样可以确保不会漏掉任何潜在的错误或缺陷。
   • 过近似的结果可能是一种保守的近似，可能会导致更多的假阳性（误报），但可以保证分析的完备性。
   • 过近似常用于静态分析中的数据流分析、程序验证和漏洞检测等领域。

3. 传输函数（Transfer functions）：

   • 传输函数描述了静态分析中从一个程序语句到另一个程序语句的信息传递和转换过程。它定义了程序的抽象状态如何在程序执行时变化。
   • 传输函数通常是通过对程序语句进行抽象化和近似来定义的。它们根据输入语句的抽象状态计算出输出语句的抽象状态。
   • 传输函数是静态分析中重要的组成部分，用于捕获程序语句之间的控制和数据依赖关系。

4. 控制流（Control flows）：

   • 控制流描述了程序在执行过程中的各个分支和路径。它定义了程序语句的执行顺序和条件跳转。
   • 在静态分析中，控制流用于构建程序的模型，以便进行路径覆盖和错误检测。
   • 控制流图（Control flow graph）是一种常用的表示方式，它以图的形式展示了程序的各个分支和路径，便于静态分析的建模和处理。

在静态分析中，抽象化和过近似是为了处理复杂性和提高分析效率的重要技术。通过抽象化，可以将程序语义简化为更易分析的形式，同时通过过近似可以保证分析的完备性。传输函数和控制流则提供了描述程序行为和语句之间关系的工具，帮助进行静态分析的建模和推理。