数据流分析：非正式介绍¶
摘要¶
本文以非正式的方式介绍了数据流分析。目的是让读者直观地了解其工作原理，并展示其如何应用于各种重构和错误查找问题。
数据流分析是一种成熟的技术；它在许多论文、书籍和视频中都有描述。如果您想了解更多关于本文中提到的概念的正式或更深入的解释，请参考以下资源。
数据流分析¶
数据流分析的用途¶
数据流分析是一种静态分析技术，它可以证明关于程序或其片段的事实。它可以对程序中的所有路径做出结论，同时考虑控制流并扩展到大型程序。基本思想是通过控制流图（CFG）的边传播关于程序的事实，直到达到不动点。
示例问题和一种特殊解决方案¶
我们想在讨论一个例子的时候解释数据流分析。让我们假设我们想跟踪程序中一个整型变量的可能值。以下是如何一个人注释代码
void Example(int n) {
int x = 0;
// x is {0}
if (n > 0) {
x = 5;
// x is {5}
} else {
x = 42;
// x is {42}
}
// x is {5; 42}
print(x);
}
我们使用整数集来表示x的可能值。局部变量在语句之间具有明确的值，因此我们在语句之间的程序点上用可能值的集合进行注释。
以下是如何得出这些注释。将一个常量赋值给x使我们能够得出结论，即x只能有一个值。当来自“then”和“else”分支的控制流汇合时，x可以具有任一值。
抽象代数提供了一个很好的形式化模型，可以模拟这种结构，即格。一个并半格是一个偏序集，其中任何两个元素都具有一个最小上界（称为并）。
join(a, b) ⩾ a and join(a, b) ⩾ b and join(x, x) = x
对于这个问题，我们将使用整数子集的格，以集合包含关系作为排序，以集合并集作为并。
格通常以哈斯图的形式直观地表示。以下是我们用于跟踪整数子集的格的哈斯图
在格中计算并对应于在它的哈斯图中找到两个节点之间的最近公共祖先（LCA）。关于针对 DAG 有效实现 LCA 查询的文献很多，但是 Efficient Implementation of Lattice Operations (1989) (CiteSeerX，doi) 描述了一种特别适合于程序化实现的方案。
太多信息和“顶”值¶
让我们尝试在修改循环中修改x的函数中找到x的可能值集
void ExampleOfInfiniteSets() {
int x = 0; // x is {0}
while (condition()) {
x += 1; // x is {0; 1; 2; …}
}
print(x); // x is {0; 1; 2; …}
}
我们有一个问题：x可以具有大于零的任何值；如果程序在数学整数上运行，那将是一个无限集。在 C++ 中，int 受INT_MAX限制，因此从技术上讲我们有一个集{0; 1; …; INT_MAX}，它仍然非常大。
为了使我们的分析在计算上可行，我们必须限制我们跟踪的信息量。在这种情况下，例如，我们可以任意地将集合的大小限制为 3 个元素。如果在某个程序点，x具有超过 3 个可能的值，那么我们停止跟踪该程序点处的特定值。相反，我们用符号⊤（根据抽象代数中的约定发音为“顶”）来表示x的可能值。
void ExampleOfTopWithALoop() {
int x = 0; // x is {0}
while (condition()) {
x += 1; // x is ⊤
}
print(x); // x is ⊤
}
语句“在这个程序点，x的可能值是⊤”的理解是“在这个程序点，x可以具有任何值，因为我们有太多信息，或者信息冲突”。
请注意，即使没有循环，我们也可以获得超过 3 个可能的值
void ExampleOfTopWithoutLoops(int n) {
int x = 0; // x is {0}
switch(n) {
case 0: x = 1; break; // x is {1}
case 1: x = 9; break; // x is {9}
case 2: x = 7; break; // x is {7}
default: x = 3; break; // x is {3}
}
// x is ⊤
}
未初始化的变量和“底”值¶
当x被声明但未初始化时，它没有可能的值。我们用符号⊥（发音为“底”）来表示此事实。
void ExampleOfBottom() {
int x; // x is ⊥
x = 42; // x is {42}
print(x);
}
请注意，使用从未初始化的变量读取的值在 C++ 中是未定义的行为。通常，编译器和静态分析工具可以假设未定义的行为不会发生。我们只有在实现专门尝试查找未初始化读取的检查器时，才必须对未初始化的变量进行建模。在本例中，我们仅展示如何对未初始化的变量进行建模，以演示“底”的概念及其如何应用于可能值分析。我们将在下面的部分中描述一种用于查找未初始化读取的分析方法。
一个用于跟踪具体值集的实用格¶
考虑到上面涵盖的所有特殊情况，我们可以组合一个格，该格可以在实践中用来跟踪整型变量的可能值。此格表示具有 1、2 或 3 个元素的整数集，以及顶和底。以下是一个哈斯图
形式化¶
让我们考虑一个稍微复杂一点的例子，并思考如何以算法方式计算可能的值集。
void Example(int n) {
int x; // x is ⊥
if (n > 0) {
if (n == 42) {
x = 44; // x is {44}
} else {
x = 5; // x is {5}
}
print(x); // x is {44; 5}
} else {
x = n; // x is ⊤
}
print(x); // x is ⊤
}
作为人类，我们了解程序文本中的控制流。我们利用对控制流的理解来查找两个流汇合的程序点。从形式上讲，控制流由 CFG（控制流图）表示
我们可以通过 CFG 传播可能的值集来计算它们
当
x被声明但未初始化时，其可能值为{}。空集在此格中扮演⊥的角色。当
x被赋值一个具体值时，其可能值集仅包含该特定值。当
x被赋值一些未知值时，它可以具有任何值。我们用⊤来表示此事实。当两个控制流路径汇合时，我们计算传入值的集合并集（将元素数量限制为 3，将更大的集合表示为
⊤）。
可能的值集受以下因素影响
语句，例如赋值。
控制流中的汇合，例如出现在“if”语句末尾的汇合。
**语句的影响**由正式称为转移函数的内容建模。转移函数接受两个参数：语句和x在先前程序点处的状态。它生成x在下一个程序点处的状态。例如，赋值的转移函数忽略先前程序点处的状态
// GIVEN: x is {42; 44}
x = 0;
// CONCLUSION: x is {0}
对于+的转移函数，对每个集合成员执行算术运算
// GIVEN: x is {42, 44}
x = x + 100;
// CONCLUSION: x is {142, 144}
**控制流的影响**通过加入来自所有可能的先前程序点的信息来建模。
if (...) {
...
// GIVEN: x is {42}
} else {
...
// GIVEN: x is {44}
}
// CONCLUSION: x is {42; 44}
// GIVEN: x is {42}
while (...) {
...
// GIVEN: x is {44}
}
// CONCLUSION: {42; 44}
我们标记为“给定”的谓词通常称为前置条件，而结论称为后置条件。
在 CFG 方面，我们加入来自所有前驱基本块的信息。
将所有内容放在一起，为了对基本块的影响进行建模，我们计算
out = transfer(basic_block, join(in_1, in_2, ..., in_n))
（请注意，还有其他方法可以编写此方程，从而产生更高精度的分析结果。诀窍是继续分别探索执行路径，并将合并推迟到以后。但是，我们不会在此处讨论这些变体。）
为了对程序中的所有路径做出结论，我们在所有基本块上重复此计算，直到达到不动点。换句话说，我们不断地通过 CFG 传播信息，直到计算出的值集停止变化。
如果格具有有限的高度，并且转移函数是单调的，则该算法保证会终止。算法的每次迭代只能将计算出的值更改为格中更大的值。在最坏的情况下，所有计算出的值都变为⊤，这并不是很有用，但至少分析在此时会终止，因为它不能更改任何值。
不动点迭代可以通过仅重新处理在先前迭代中其输入之一发生了变化的基本块来优化。这通常使用工作列表队列来实现。通过这种优化，时间复杂度变为O(m * |L|)，其中m是 CFG 中基本块的数量，|L|是分析使用的格的大小。
符号执行：一个非常简短的非正式介绍¶
符号值¶
在之前的例子中，我们试图找出变量可以取什么值，分析必须以一个具体的值作为种子。如果程序中没有具体值的赋值呢？我们仍然可以通过象征性地表示未知的输入值，并将结果计算为符号表达式来推导出一些有趣的信息。
void PrintAbs(int x) {
int result;
if (x >= 0) {
result = x; // result is {x}
} else {
result = -x; // result is {-x}
}
print(result); // result is {x; -x}
}
我们不能说打印了哪个具体的值，但我们知道它是 x 或 -x。
数据流分析是抽象解释的一种实例，它不规定格和转移函数应该如何设计，只规定了分析收敛的必要条件。然而，我们可以使用符号执行的想法来指导我们对格和转移函数的设计：格值可以是符号表达式，转移函数可以从表示参数的符号表达式构造更复杂的符号表达式。参见 这个 StackOverflow 讨论，以进一步比较抽象解释和符号执行。
流程条件¶
人类可以对之前的例子说，当 x >= 0 时，函数返回 x，当 x < 0 时，返回 -x。我们可以通过跟踪流程条件以编程方式得出这个结论。流程条件是一个根据程序状态编写的谓词，它在特定程序点总是成立的，无论导致该语句的执行路径如何。例如，在评估 result = x 之前的程序点的流程条件是 x >= 0。
如果我们将格增强为一组值和谓词的配对，数据流分析将计算以下值
void PrintAbs(int x) {
int result;
if (x >= 0) {
// Flow condition: x >= 0.
result = x; // result is {x if x >= 0}
} else {
// Flow condition: x < 0.
result = -x; // result is {-x if x < 0}
}
print(result); // result is {x if x >= 0; -x if x < 0}
}
当然，在有循环的程序中，流程条件的符号表达式可能会无限制地增长。一个实用的静态分析系统必须控制这种增长，以保持符号表示的可管理性和确保数据流分析终止。例如，它可以使用约束求解器来修剪不可能的流程条件，或者它可以抽象它们，在它们的符号表示超过某个阈值后，就会失去精度。这与我们必须将计算的可能值集合的大小限制为 3 个元素类似。
符号指针¶
这种方法被证明在对指针值建模方面特别有用，因为我们不关心具体的地址，而只是想给一个内存位置一个唯一的标识符。
void ExampleOfSymbolicPointers(bool b) {
int x = 0; // x is {0}
int* ptr = &x; // x is {0} ptr is {&x}
if (b) {
*ptr = 42; // x is {42} ptr is {&x}
}
print(x); // x is {0; 42} ptr is {&x}
}
示例：查找输出参数¶
让我们来探索数据流分析如何帮助解决 Clang 中难以用其他工具解决的问题。
问题描述¶
输出参数是指针或引用类型的函数参数，其指针所指向的内容被函数完全覆盖，并且在覆盖之前不会被读取。它们在 C++11 之前的代码中很常见，因为缺少移动语义。在现代 C++ 中，输出参数是不符合习惯用法的，而是使用返回值。
想象一下，我们希望将输出参数重构为返回值，以使旧代码现代化。第一步是通过静态分析识别重构候选者。
例如，在下面的代码片段中，指针 c 是一个输出参数
struct Customer {
int account_id;
std::string name;
}
void GetCustomer(Customer *c) {
c->account_id = ...;
if (...) {
c->name = ...;
} else {
c->name = ...;
}
}
我们希望将这段代码重构为
Customer GetCustomer() {
Customer c;
c.account_id = ...;
if (...) {
c.name = ...;
} else {
c.name = ...;
}
return c;
}
然而，在下面的函数中，参数 c 不是一个输出参数，因为它的字段 name 不会在函数中的所有路径上被覆盖。
void GetCustomer(Customer *c) {
c->account_id = ...;
if (...) {
c->name = ...;
}
}
代码也不能在覆盖之前读取参数的值
void GetCustomer(Customer *c) {
use(c->account_id);
c->name = ...;
c->account_id = ...;
}
转义指针的函数也会阻止重构
Customer* kGlobalCustomer;
void GetCustomer(Customer *c) {
c->name = ...;
c->account_id = ...;
kGlobalCustomer = c;
}
为了识别一个重构候选函数，我们需要做以下事情
查找一个具有非 const 指针或引用参数的函数。
查找该函数的定义。
证明函数在返回之前，在所有路径上完全覆盖了指针指向的内容。
证明函数只在覆盖指针指向的内容之后读取它。
证明函数不会将指针持久化到函数返回后仍然活动的某个数据结构中。
候选函数的所有使用点也必须满足一些要求，例如，函数参数不别名，用户没有获取函数的地址等等。让我们将验证使用点条件视为一个独立的静态分析问题。
格设计¶
为了分析函数体，我们可以使用一个格，它由正常状态和失败状态组成。正常状态描述了我们确定没有发生阻止重构的行为的程序点。正常状态跟踪所有在从函数入口到相应程序点的每条路径上已知被覆盖的参数成员字段。失败状态累积观察到的违规行为（不安全的读取和指针转义），这些违规行为会阻止重构。
在格的部分序中，失败状态与正常状态相比更大，这保证了它们在与正常状态连接时“获胜”。失败状态之间的顺序由累积的违规行为集合上的包含关系决定（格的 ⩽ 是违规行为集合上的 ⊆）。正常状态之间的顺序由被覆盖的参数成员字段集合上的反向包含关系决定（格的 ⩽ 是被覆盖的字段集合上的 ⊇）。
为了确定一个语句是读取还是写入一个字段，我们可以实现对 DeclRefExpr、LValueToRValue 转换、指针解除引用运算符和 MemberExpr 的符号评估。
使用数据流结果来识别输出参数¶
让我们来看看如何使用数据流分析来识别输出参数。当数据流算法在函数的退出基本块中计算出一个正常状态，其中所有字段都被证明已覆盖时，可以安全地进行重构。
struct Customer {
int account_id;
std::string name;
};
void GetCustomer(Customer* c) {
// Overwritten: {}
c->account_id = ...; // Overwritten: {c->account_id}
if (...) {
c->name = ...; // Overwritten: {c->account_id, c->name}
} else {
c->name = ...; // Overwritten: {c->account_id, c->name}
}
// Overwritten: {c->account_id, c->name}
}
当数据流算法计算出一个正常状态，但并非所有字段都被证明已覆盖时，我们无法进行重构。
void target(bool b, Customer* c) {
// Overwritten: {}
if (b) {
c->account_id = 42; // Overwritten: {c->account_id}
} else {
c->name = "Konrad"; // Overwritten: {c->name}
}
// Overwritten: {}
}
同样，当数据流算法计算出一个失败状态时，我们也无法进行重构。
Customer* kGlobalCustomer;
void GetCustomer(Customer* c) {
// Overwritten: {}
c->account_id = ...; // Overwritten: {c->account_id}
if (...) {
print(c->name); // Unsafe read
} else {
kGlobalCustomer = c; // Pointer escape
}
// Unsafe read, Pointer escape
}
示例：查找死存储¶
假设我们想要找到冗余的存储，因为它们可能表明存在潜在的错误。
x = GetX();
x = GetY();
对 x 的第一个存储从未被读取，可能存在错误。
死存储分析的实现与输出参数分析非常相似：我们需要跟踪存储和加载，并找到从未被读取的存储。
活性分析是这个想法的推广，它经常被用来回答许多相关的问题，例如
查找死存储，
查找未初始化的变量，
查找释放内存的最佳点，
找出移动一个对象是否安全。
示例：确定性初始化¶
确定性初始化证明了在读取时，变量被明确地初始化。如果我们发现一个变量在未初始化时被读取，那么我们就会发出警告。
void Init() {
int x; // x is uninitialized
if (cond()) {
x = 10; // x is initialized
} else {
x = 20; // x is initialized
}
print(x); // x is initialized
}
void Uninit() {
int x; // x is uninitialized
if (cond()) {
x = 10; // x is initialized
}
print(x); // x is maybe uninitialized, x is being read, report a bug.
}
为此，我们可以使用一个格，它以从变量声明到初始化状态的映射形式出现；每个初始化状态由以下格表示
格元素也可以捕捉到导致我们到达相应程序点的分支的源位置。诊断将使用这些信息向用户显示一个有问题的代码路径示例。
示例：将原始指针重构为 unique_ptr¶
现代习惯用法的 C++ 使用智能指针来表达内存所有权，但在 C++11 之前的代码中，人们经常会发现拥有堆内存块的原始指针。
想象一下，我们想要将拥有内存的原始指针重构为 unique_ptr。解决这个问题有多种数据流分析方法，让我们来看看其中一种。
例如，我们希望重构以下使用原始指针的代码
void UniqueOwnership1() {
int *pi = new int;
if (...) {
Borrow(pi);
delete pi;
} else {
TakeOwnership(pi);
}
}
为使用 unique_ptr 的代码
void UniqueOwnership1() {
auto pi = std::make_unique<int>();
if (...) {
Borrow(pi.get());
} else {
TakeOwnership(pi.release());
}
}
这个问题可以用格来解决，格的形式是从值声明到指针状态的映射
如果在函数退出时，pi 为 Compatible，则可以进行重构。
void UniqueOwnership1() {
int *pi; // pi is Compatible
pi = new int; // pi is Defined
if (...) {
Borrow(pi); // pi is Defined
delete pi; // pi is Compatible
} else {
TakeOwnership(pi); // pi is Compatible
}
// pi is Compatible
}
让我们来看一个原始指针拥有两个不同内存块的例子
void UniqueOwnership2() {
int *pi = new int; // pi is Defined
Borrow(pi);
delete pi; // pi is Compatible
if (smth) {
pi = new int; // pi is Defined
Borrow(pi);
delete pi; // pi is Compatible
}
// pi is Compatible
}
它可以被重构为使用 unique_ptr，如下所示
void UniqueOwnership2() {
auto pi = make_unique<int>();
Borrow(pi);
if (smth) {
pi = make_unique<int>();
Borrow(pi);
}
}
在以下示例中，原始指针在所有权被转移后用于访问堆对象。
void UniqueOwnership3() {
int *pi = new int; // pi is Defined
if (...) {
Borrow(pi);
delete pi; // pi is Compatible
} else {
vector<unique_ptr<int>> v = {std::unique_ptr(pi)}; // pi is Compatible
print(*pi);
use(v);
}
// pi is Compatible
}
我们可以将这段代码重构为使用 unique_ptr，但是我们需要引入一个非拥有指针变量，因为我们不能使用已移动的 unique_ptr 来访问该对象
void UniqueOwnership3() {
std::unique_ptr<int> pi = std::make_unique<int>();
if (...) {
Borrow(pi);
} else {
int *pi_non_owning = pi.get();
vector<unique_ptr<int>> v = {std::move(pi)};
print(*pi_non_owning);
use(v);
}
}
如果原始代码没有在函数的末尾调用 delete，那么我们的重构可能会改变我们运行析构函数和释放内存的点。具体来说，如果在 delete 之后有一些用户代码，那么将对象的生存期延长到函数结束可能会比必要的时间更长地保持锁，引入内存开销等等。
一个解决方案是始终用调用 reset() 来替换 delete，然后执行另一个分析，删除不必要的 reset() 调用。
void AddedMemoryOverhead() {
HugeObject *ho = new HugeObject();
use(ho);
delete ho; // Release the large amount of memory quickly.
LongRunningFunction();
}
这种分析将拒绝重构混合了借用指针值和唯一所有权的代码。在下面的代码中，GetPtr() 返回一个借用指针，它被赋值给 pi。然后，pi 用于持有唯一拥有的指针。我们不区分这两种赋值，我们希望每个赋值都与一个相应的接收器配对；否则，我们将指针转换为 Conflicting 状态，就像在这个例子中一样。
void ConflictingOwnership() {
int *pi; // pi is Compatible
pi = GetPtr(); // pi is Defined
Borrow(pi); // pi is Defined
pi = new int; // pi is Conflicting
Borrow(pi);
delete pi;
// pi is Conflicting
}
我们仍然可以通过在代码中找到 pi 可能处于兼容状态的最大范围来处理这种情况，并且只重构该部分。
void ConflictingOwnership() {
int *pi;
pi = GetPtr();
Borrow(pi);
std::unique_ptr<int> pi_unique = std::make_unique<int>();
Borrow(pi_unique.get());
}
示例：查找冗余分支条件¶
在下面的代码中，不应该在外部和内部的“if”语句中都检查 b1。 这段代码很可能存在错误。
int F(bool b1, bool b2) {
if (b1) {
f();
if (b1 && b2) { // Check `b1` again -- unnecessary!
g();
}
}
}
使用 AST 匹配器（bugprone-redundant-branch-condition）在 ClangTidy 中已经实现了可以从语法上找到这种模式的检查器。
为了使用数据流分析框架实现它，如果分支条件的任何部分被流条件暗示，我们可以产生一个警告。
int F(bool b1, bool b2) {
// Flow condition: true.
if (b1) {
// Flow condition: b1.
f();
if (b1 && b2) { // `b1` is implied by the flow condition.
g();
}
}
}
一种检查这种含义的方法是使用 SAT 求解器。如果没有 SAT 求解器，我们可以将流条件保留在 CNF 形式中，然后很容易检查含义。
示例：查找未经检查的 std::optional 解包¶
只有当 optional::has_value() 为 true 时，调用 optional::value() 才有效。 我们想要证明，当执行 x.value() 时，流条件暗示 x.has_value()。
在下面的示例中，x.value() 是安全访问的，因为它被 x.has_value() 检查所保护。
void Example(std::optional<int> &x) {
if (x.has_value()) {
use(x.value());
}
}
进入 if 分支时，我们推断出 x.has_value() 被流条件暗示。
void Example(std::optional<int> x) {
// Flow condition: true.
if (x.has_value()) {
// Flow condition: x.has_value() == true.
use(x.value());
}
// Flow condition: true.
}
我们还需要证明 x 在检查和值访问之间没有被修改。 x 的修改可能是非常微妙的。
void F(std::optional<int> &x);
void Example(std::optional<int> &x) {
if (x.has_value()) {
// Flow condition: x.has_value() == true.
unknown_function(x); // may change x.
// Flow condition: true.
use(x.value());
}
}
示例：查找 A/B 实验标志后面的死代码¶
查找死代码是数据流分析的典型应用。
A/B 实验的未使用标志隐藏了死代码。但是，这种死代码对编译器是不可见的，因为标志可以在任何时候被打开。
我们可以制作一个删除实验标志的工具。 用户告诉我们他们想要删除哪个标志，我们假设它的值是一个给定的常量。
例如，用户可以使用该工具从以下代码中删除 example_flag
DEFINE_FLAG(std::string, example_flag, "", "A sample flag.");
void Example() {
bool x = GetFlag(FLAGS_example_flag).empty();
f();
if (x) {
g();
} else {
h();
}
}
该工具将简化代码为
void Example() {
f();
g();
}
我们可以用经典的常量传播格结合符号求值来解决这个问题。
示例：查找关联容器的低效用法¶
现实世界中的代码经常意外地在关联容器中执行重复查找。
map<int, Employee> xs;
xs[42]->name = "...";
xs[42]->title = "...";
为了找到上面的低效，我们可以使用可用表达式分析来理解 m[42] 被评估了两次。
map<int, Employee> xs;
Employee &e = xs[42];
e->name = "...";
e->title = "...";
我们也可以跟踪流条件中的 m.contains() 检查，以查找冗余检查，如以下示例所示。
std::map<int, Employee> xs;
if (!xs.contains(42)) {
xs.insert({42, someEmployee});
}
示例：重构彼此隐式转换的类型¶
将一种强类型重构为另一种类型很困难，但编译器可以提供帮助：一旦你重构了对该类型的某个引用，编译器将用类型不匹配错误标记该信息流入的其他地方。 不幸的是，当你重构彼此隐式转换的类型时，这种策略不起作用，例如，用 int64_t 替换 int32_t。
假设我们想要将用户 ID 从 32 位整数更改为 64 位整数。 换句话说，我们需要找到所有被用户 ID 污染的整数。 我们可以使用数据流分析来实现污点分析。
void UseUser(int32_t user_id) {
int32_t id = user_id;
// Variable `id` is tainted with a user ID.
...
}
污点分析非常适合这个问题，因为程序很少根据用户 ID 分支，几乎肯定不会执行任何计算（如算术运算）。