🍃使用 Tree-sitter 构建 PHP 代码控制流图 (CFG)

type
status
date
slug
summary
tags
category
icon
password
AI summary
notion image

引言

在程序分析和编译器优化中，控制流图（Control Flow Graph, CFG） 是一种重要的数据结构。它用于表示程序的执行流程，帮助分析代码的可达性、优化代码执行路径，甚至用于静态分析工具来检测潜在的错误或漏洞。
在本文中，我们将通过具体的代码实现，探讨如何使用 Tree-Sitter 解析 PHP 代码的 抽象语法树（AST），并基于 AST 构建 控制流图（CFG）。
💡
什么是控制流图？
控制流图（CFG）是一种有向图，其中：
  • 节点（Node） 代表程序中的基本块（Basic Block），具有单一的入口点和单一的出口点，在块内不会发生分支或跳转。
  • 边（Edge） 代表控制流的转移方向。例如，从一个语句顺序执行到下一个语句，或者条件判断后根据条件结果转移到不同的分支。
一个简易版的控制流图如下：
在这个示例中， if (x > 0) 语句会导致程序执行路径的分叉，形成两个不同的执行流。

如何从 AST 构建 CFG？

在深入代码细节之前，我们首先需要理解如何从 AST 构建 CFG。AST 表示了代码的语法结构，但它更侧重于代码的层次结构和语法成分，而非执行流程。而 CFG 则专注于描述程序的控制流路径，即代码执行的顺序和分支。
💡
  • AST 是一种树状结构，节点间的关系主要是父子关系，难以直接体现代码的执行顺序和跳转关系。例如，if 语句在 AST 中只是一个节点，其条件和分支代码块是其子节点，但 AST 本身不直接表达 "如果条件成立，执行哪个分支，否则执行哪个分支" 的控制流信息。
  • CFG 使用图结构，节点代表基本代码块或语句，有向边代表控制流的转移。这种图结构能够清晰地表达代码的执行路径、分支、循环等控制流信息，更适合进行程序分析。

从 AST 构建 CFG 的基本步骤和原理

从 AST 构建 CFG 的过程，本质上是一个 AST 节点的遍历和转换过程。我们需要遍历 AST，识别出对控制流有影响的语句节点，并将它们转换为 CFG 中的节点，并根据语句的控制流语义添加 CFG 边。以下是构建过程中的一些关键步骤和原理：
  1. AST 节点遍历： 通常采用深度优先遍历的方式遍历 AST。这样可以按照代码的逻辑顺序访问到各个语句节点。
  1. 识别控制流语句： 在遍历过程中，我们需要识别出 AST 中代表控制流语句的节点类型：
    1. 条件和分支语句:
        • if_statement - 条件分支
        • switch_statement - 多路分支
    2. 循环语句:
        • while_statement - while循环
        • do_statement - do-while循环
        • for_statement - for循环
        • foreach_statement - foreach循环
    3. 跳转语句:
        • goto_statement - 无条件跳转
        • continue_statement - 继续下一次循环
        • break_statement - 跳出循环
        • return_statement - 函数返回
    4. 异常处理:
        • try_statement - 异常捕获和处理
    5. 程序终止:
        • exit_statement - 程序退出
    6. 复合语句:
        • compound_statement - 包含多条语句的代码块，会影响控制流的嵌套结构
  1. 创建 CFG 节点： 对于每个识别出的控制流语句节点，我们需要在 CFG 中创建一个对应的CFG 节点。这个 CFG 节点通常会包含以下信息：
      • 节点 ID： 用于唯一标识 CFG 节点。通常可以使用 AST 节点的 ID 或生成新的唯一 ID。
      • 节点类型： 表示 CFG 节点对应的语句类型，例如 if_statement 等。
      • 节点文本： 可选地包含节点对应的源代码文本。
      • 其他属性： 例如是否是分支节点等，可以根据具体需求添加。
  1. 🌟添加 CFG 边🌟： 根据不同语句的控制流语义，在 CFG 节点之间添加有向边，表示控制流的转移方向。添加边的关键在于理解每种语句的执行逻辑：
🔥
总结：AST 到 CFG 的转换是一个语义理解和图构建的过程。我们需要理解不同 AST 节点代表的语句的控制流语义，并将其转换为 CFG 图的节点和边，最终得到能够清晰表达程序控制流的图结构。

代码概览：基于 Tree-sitter 的 PHP CFG 构建器

📢
本文的代码实现，参考了一个开源项目中基于 C 语言的 CFG 构建方法，也有些逻辑处理是个人的见解，所以可能会有逻辑错误的实现。
代码的实现主要包括两部分，AST 的构建、遍历，CFG 的构建。所以代码可以组织为两个模块：
  • ast_parser: 负责使用 Tree-sitter 解析 PHP 代码，并提供查询 AST 节点的功能。它能够识别 PHP 代码中的函数定义、各种语句类型，并提取节点的关键属性。
  • cfg_builder : 专注于 CFG 的构建，它递归遍历 AST，根据不同的语句类型生成 CFG 的节点和边。

构建 AST

在 Python 中实现 AST 的构建还是比较简单的，直接使用 tree_sitter_language_pack 库就行：
这样，我们就得到了输入 code 的完整 AST。在构建 CFG 时，实现的是基于 function 粒度的，所以我们还需要把输入代码中所有的 function 提取出来，可以定义一个辅助函数，用于从 AST 中提取指定类型的 node：
💡
为什么这样处理？ 函数是代码的基本模块。为每个函数构建独立的 CFG 是常见的做法，便于函数级别的分析和理解。函数体内的控制流逻辑与外部代码隔离，后续可以通过函数调用图(Call Graph, CG)连接函数 CFG 和调用点 CFG。
有了 query 函数，我们就可以传入 root_node 递归获取所有的 function node：
准备好这些基本输入之后，就可以着手构建 CFG 了。

构建 CFG

在整个构建 CFG 的过程中，我们需要维护每个代码块或语句的入口节点 (in_nodes) 和 出口节点 (out_nodes)。
  • 入口节点 (in_nodes)： 表示控制流进入当前代码块或语句的入口边集合。
  • 出口节点 (out_nodes)： 表示控制流从当前代码块或语句出去的出口边集合。
通过 in_nodes和 out_nodes的传递和连接，可以将各个语句的 CFG 片段组合成完整的函数或程序的 CFG。下面是需要使用的数据结构：
  1. NodeInfo: dict[str, str | int | bool | list[tuple[int, int]]]
      2. NodeInfo 类型用于存储 CFG 中每个节点的详细信息。它是一个字典，包含以下键值对：
      • "id": str - 节点的唯一标识符。通常基于 Tree-sitter AST 节点的 ID 生成，确保每个 CFG 节点都有唯一的身份，方便在图中引用和查找。
      • "type": str - 节点代表的 AST 节点类型。例如，"if_statement"、"function_definition"、"expression_statement" 等。这有助于理解 CFG 节点在代码中的语义角色。
      • "start": tuple[int, int] - 节点代码在源文件中的起始位置，表示为 (行号, 列号) 的元组。方便将 CFG 节点映射回源代码，进行代码定位和分析。
      • "end": tuple[int, int] - 节点代码在源文件中的结束位置，同样表示为 (行号, 列号) 的元组。与 "start" 配合使用，可以精确定位节点对应的代码范围。
      • "is_branch": bool - 标识节点是否为分支节点。例如，if 语句、while 循环等条件判断语句对应的节点会被标记为 True，表示控制流在此处会发生分支。
      • "text": str - 节点对应的源代码文本。存储了节点代表的代码片段的文本内容，使 CFG 节点更易于理解和调试。
      示例： 一个 if_statement 节点的 NodeInfo 可能如下所示：
  1. Nodes: list[tuple[NodeInfo, str]]
      2. Nodes 类型用于表示 一组 CFG 节点及其相关的边标签。它是一个列表，列表中的每个元素都是一个元组。
      • tuple[NodeInfo, str] - 表示一个 CFG 节点以及与其关联的边标签。
        • 第一个元素 NodeInfo: CFG 节点的 NodeInfo 对象，包含了节点的详细信息。
        • 第二个元素 str: 边标签。在 create_cfg 函数中，Nodes 通常作为 in_nodes 参数传递，表示 控制流进入当前节点的入口来源。边标签用于区分不同的入口路径。
      示例： create_cfg 函数的 in_nodes 参数可能是一个 Nodes 列表，如下所示：
  1. Edges: list[tuple[str, str]]
      2. Edges 类型用于表示 一组 CFG 边。它是一个列表，列表中的每个元素都是一个元组，代表一条边。
      • tuple[str, str] - 表示一条 CFG 边，元组包含两个字符串：
        • 第一个 str: parent_id (父节点 ID) - 边的起始节点的 ID。表示控制流从哪个节点流出。
        • 第二个 str: label (边标签) - 边的标签，用于区分不同类型的控制流转移。例如：
          • "" (空字符串): 表示顺序执行的边，没有特殊条件。
          • "True": 表示条件为真时执行的分支。例如，if 语句的 True 分支边。
          • "False": 表示条件为假时执行的分支。例如，if 语句的 False 分支边。
          • "Exception": 表示异常处理的边。例如，try 块到 catch 块的异常边。
          • "case <value>" 或 "default": 用于 switch 语句的 case 分支边，标签为对应的 case 值或 "default"。
      示例： 一个节点的 Edges 列表可能如下所示，表示该节点有两条入边：
  1. CFG_GRAPH: list[tuple[NodeInfo, Edges]]
      2. CFG_GRAPH 类型用于表示 完整的控制流图 (CFG)。它是一个列表，列表中的每个元素都是一个元组。
      • tuple[NodeInfo, Edges] - 表示 CFG 中的一个节点及其所有入边。
        • 第一个元素 NodeInfo: CFG 节点的 NodeInfo 对象，包含了节点的详细信息。
        • 第二个元素 Edges: Edges 对象，即该节点的所有入边列表。
      示例： 一个 CFG_GRAPH 可能如下所示，表示一个包含三个节点的 CFG：
      其中 node_info_A、node_info_B、node_info_C 分别是节点 A、B、C 的 NodeInfo 对象，"A_ID" 和 "B_ID" 分别是节点 A 和 B 的 ID。
💡
NodeInfo 封装了节点的属性信息，Edges 和 Nodes 用于表示边的集合，而 CFG_GRAPH 则将节点和边组织在一起，构成完整的 CFG 图的列表表示形式。
之后我们需要实现一个函数，它接收一个 Tree-sitter 节点 node 和一个 in_nodes 列表作为输入，输出构建的 CFG_GRAPH 以及当前节点处理后的 out_nodes。函数内部需要识别和处理不同的 statement，创建相应的 CFG 节点和相互连接边。所以，解析来开始最重要的部分~

函数定义 (function_definition)

  • 创建函数节点：首先为函数定义创建一个 CFG 节点，并将其添加到 CFG 列表中。函数的入口节点没有入边，因此入边列表为空 []。
  • 递归处理函数体：获取函数体的 body 节点，并递归调用处理函数体内的语句。函数体的入口边指向函数定义的节点。
  • 返回结果：函数定义的 CFG 片段由函数节点和函数体 CFG 片段组成。函数定义本身没有出口节点，因此返回空的 out_nodes 列表 []。

复合语句块 (compound_statement)

  • 顺序处理子语句：compound_statement 代表代码块( 被{ 和 } 包裹的)，例如函数体、循环体、if 语句块等。它包含一系列顺序执行的子语句。
  • 迭代处理子节点：遍历 compound_statement 的子节点，跳过花括号 {}。
  • 递归调用：对每个子节点递归调用 handle_node 处理。
  • 关键：控制流传递 in_nodes 会在循环中被更新为上一个子语句的 out_nodes。这意味着前一个语句的出口节点会成为下一个语句的入口节点，保证了代码块内语句的顺序执行。
compound_statement 体现了代码的顺序执行流程。通过迭代处理子语句并传递 in_nodes 和 out_nodes，可以正确地将代码块内的语句连接成线性的控制流路径。

if 语句 (if_statement)

  • 创建 if 条件节点：为 if 语句创建一个 CFG 节点，表示条件判断。其入边来自 in_nodes。
  • 处理 if 主体 (True 分支)：递归调用 handle_node 处理 if 语句的 body (即 if 条件成立时执行的代码块)。body 的入口边指向 if 条件节点，并标记为 "True" 分支。
  • 处理 else 或 else if 分支 (False 分支)：
    • 如果存在 alternative (即 else 或 else if 语句)，则递归调用 handle_node 处理 alternative。alternative 的入口边也指向 if 条件节点，并标记为 "False" 分支。
    • 如果只有 if 没有 else，则 if 条件不成立时的控制流直接跳过 if 主体，到达 if 语句之后的代码。
  • 合并出口节点：if 语句的出口节点是 if 主体 (True 分支) 的出口节点和 else/else if 分支 (False 分支，如果存在) 的出口节点的并集。如果只有 if，则出口节点是 if 主体的出口节点和 if 条件节点本身的 "False" 分支出口 (代表条件不成立时直接跳过 if 块)。
💡
if 语句引入了条件分支，控制流根据条件表达式的结果选择不同的执行路径。通过为 if 条件创建节点，并为 True 和 False 分支分别递归处理，清晰地表示了这种分支结构。标记 "True" 和 "False" 边可以区分不同的控制流路径。

else_if_clause 和 else_clause

else_if_clause 和 else_clause 的 body 实际上是一个 if_statement 节点，因此，直接递归调用自身处理它们的 body 节点，并将 in_nodes 原样传递下去。

循环语句 (while_statement, for_statement, foreach_statement)

  • 创建循环条件/迭代节点：为循环语句 (例如 while, for, foreach) 创建一个 CFG 节点，表示循环的条件判断或迭代过程。其入边来自 in_nodes。
  • 处理循环体 (True 分支)：递归处理循环的 body (循环体代码块)。body 的入口边指向循环条件/迭代节点，并标记为 "True" 分支 (表示条件成立，进入循环体)。
  • 循环边： 将循环体 body 的出口节点连接回循环条件/迭代节点，形成循环的回路。这表示循环体执行完毕后，控制流会再次回到循环条件判断处。
  • 处理 break 语句：break 语句会跳出循环。找到循环体内的所有 break 节点，并将它们作为循环语句的出口节点之一。
  • 处理 continue 语句：continue 语句会跳过当前循环迭代的剩余部分，直接进入下一次迭代。找到循环体内的所有 continue 节点，并将它们连接到循环条件/迭代节点，表示控制流回到循环开始处。
  • 循环出口节点：循环语句的出口节点包括：
    • False 分支： 当循环条件不成立时，控制流会跳出循环。用从循环条件/迭代节点出发的 "False" 边表示。
    • break 语句出口： 循环体内的 break 语句也会导致跳出循环，break 语句本身也作为循环的出口节点。
🔥
所以，整体的入边有三种情况：
  1. 循环主体的前一个 statement，也就是 in_nodes
  1. 循环内部的 continue，控制流回到循环开始处
  1. 循环主体的最后一条语句，形成循环的回路
notion image
💡
循环语句引入了重复执行的代码块。通过创建循环条件/迭代节点、处理循环体、添加循环边、处理 break 和 continue 语句，完整地表示了循环结构的控制流。循环边和 break/continue 边的处理是构建正确循环 CFG 的关键。

do_statement (do-while 循环)

do_statement (do-while 循环) 与 while_statement 等循环类似，但它是先执行循环体，再判断循环条件。因此，处理逻辑也类似，但入口边和循环边的连接方式有所不同：
  • 循环体入口：do_statement 的入口边实际上指向的是循环体的第一条语句 (或循环条件节点，如果循环体为空)。
  • 循环边：循环体的出口节点连接到 do_statement 的条件节点，形成循环回路。
  • 其他处理 (循环条件节点创建、break/continue 处理、出口节点) 与 while_statement 等循环类似。可能还需要注意的是 continue 节点执行之后，跳转到的是 do while 的条件节点
💡
关键区别： do-while 循环至少执行一次循环体，而 while 等循环可能一次都不执行。CFG 构建需要体现这种差异，主要体现在入口边和循环边的连接上。

switch_statement (switch 语句)

 
💡
switch_statement 的处理逻辑与 if_statement 类似，但有一些关键区别：
  • switch 语句的控制流是基于 case 语句的匹配，而不是 if-else 的条件判断。
  • case 语句的执行可能会贯穿多个 case（如果没有 break）。
  • break 语句会跳出 switch 语句，而 default 语句是可选的。
switch_statement 根据条件表达式的值，跳转到不同的 case 分支执行。处理逻辑如下：
  • 创建 switch 节点：为 switch 语句创建 CFG 节点。
  • 遍历 case 分支：迭代处理 switch 语句 body 中的每个 case 和 default 分支。
    • case 节点：为每个 case 分支创建一个 CFG 节点。case 节点的入边来自 switch 节点胡或上一个 case 语句的 out_nodes（如果没有 break），将 switch 语句到 case 语句的边标记为 case_name (或 "default" 对于 default 分支)。
    • case 语句块处理：递归调用处理每个 case 分支的代码块。case 语句块的入口边指向 case 节点。
  • break 语句处理：case 分支通常以 break 语句结束，跳出 switch 语句。找到每个 case 分支中的 break 节点，并将它们作为 switch 语句的出口节点之一。
  • switch 语句出口节点：switch 语句的出口节点包括所有 case 分支中的 break 语句的出口节点，以及最后一个 case 或者 default 的出口节点。
notion image
1. for case_node in body.children[1:-1] 为什么要指定 body.children 范围为 [1:-1]？
body 是 switch_statement 的 body 部分，通常是一个 {} 包裹的 case 语句块。例如：
在 AST 解析树中，body.children 可能包含：
  • children[0] 是 {（大括号的起始）。
  • children[-1] 是 }（大括号的结束）。
  • children[1:-1] 才是真正的 case 语句块。
因此，body.children[1:-1] 过滤掉了 {}，只遍历 case 和 default 语句。
2. index 和 case_name 的作用是什么？
  • case_name：用于存储 case 语句的匹配值。例如：
      • 这里 case_name = "1"，用于标记 switch 语句到 case 语句的边。
  • index：用于确定 case 语句的第一条执行语句的索引。例如：
      • 在 AST 解析树中：
    • case 关键字是 children[0]。
    • 1（匹配值）是 children[1]。
    • :（冒号）是 children[2]。
    • doSomething(); 是 children[3]（第一条执行语句）。
      • 因此，index = 3，表示 case 语句的第一条执行语句的索引。
      对于 default 语句：
    • default 关键字是 children[0]。
    • :（冒号）是 children[1]。
    • handleDefault(); 是 children[2]（第一条执行语句）。
      • 因此，index = 2。
      这就是为什么 case 语句的 index = 3，而 default 语句的 index = 2。
总结
代码片段
case_name
index
说明
case 1:
"1"
3
case 语句的第一条执行语句在 children[3]
default:
"default"
2
default 语句的第一条执行语句在 children[2]
这样可以确保 case 和 default 语句的第一条执行语句被正确解析，并加入 CFG 结构。

goto_statement (goto 语句)

goto_statement 用于无条件跳转到代码中标记的标签位置 (labeled_statement)。处理逻辑如下：
  • 创建 goto 节点：为 goto 语句创建 CFG 节点。
  • 连接到标签位置：查找 goto 语句跳转的目标标签 (labeled_statement)。如果找到标签，则创建从 goto 节点到标签节点的边。
notion image
 
💡
goto 语句直接改变控制流的执行路径。通过创建 goto 节点并连接到目标标签节点，表示了 goto 语句的跳转行为。

return_statement, break_statement, continue_statement, exit_statement

这些语句都代表了程序控制流的终止或转移：
  • return_statement: 函数返回。
  • break_statement: 跳出循环或 switch 语句。
  • continue_statement: 跳过当前循环迭代的剩余部分。
  • exit_statement: 程序退出。
对于这些语句，处理逻辑相对简单：
  • 创建语句节点：为每种语句创建 CFG 节点。
  • 出口节点为空：这些语句通常是控制流的终点 (例如 return 和 exit) 或转移点 (例如 break 和 continue)，它们本身没有后继节点 (在当前函数或代码块的 CFG 中)。因此，它们的 out_nodes 返回为空 []。控制流的转移目标 (例如 break 跳出的循环的后继节点) 在处理包含这些语句的结构 (例如循环、switch、函数) 时已经确定好了。

普通语句

对于其他没有特殊控制流含义的普通语句 (例如赋值语句、函数调用语句等)，处理逻辑如下：
  • 创建语句节点：为普通语句创建 CFG 节点。
  • 顺序连接：将当前语句节点连接到 in_nodes，形成顺序执行的控制流路径。
  • 出口节点：当前语句节点本身作为出口节点，传递给下一个语句作为 in_nodes。
💡
普通语句是代码的基本组成部分，它们按照代码的顺序依次执行。通过创建节点并顺序连接，表示了这种基本的顺序控制流。

待处理 ⚠️

对于影响程序控制流执行的，还有 try catch 、 throw statement 等， 目前对于 try catch 语句的处理还是有些问题，因为 try 的主体里可能有 throw 语句，这样会立刻跳转到匹配的 catch 上，所以有个匹配连接 exception 的问题。

总结

总而言之，CFG 构建的核心思想是：
  1. 递归遍历 AST: 从根节点开始，递归地处理 AST 的每个节点。
  1. 语句类型判断: 根据节点的类型 (node.type)，判断当前节点代表的语句类型。
  1. 分类型处理: 针对不同的语句类型，采用不同的逻辑来构建 CFG 节点和边，以准确地表示该语句的控制流语义。
  1. 控制流传递: 通过 in_nodes 和 out_nodes 参数，在递归调用之间传递控制流信息，保证 CFG 的连贯性和正确性。
  1. 特殊语句处理: 重点处理具有特殊控制流含义的语句，例如条件分支 (if, switch)、循环 (while, for, do)、跳转 (goto, break, continue, return, throw)、异常处理 (try-catch-finally) 等。

感谢

特别感谢 https://github.com/rebibabo/INVEST 项目提供的思路和相关代码实现，让整个 PHP 的实现过程变得容易许多，同时通过该项目也学到了很多知识~
（就是项目的代码组织不是特别好，一个文件中的代码太长了 🫢，所以感谢 cursor 帮我梳理代码😂，后面写 PHP 的版本时，重构为模块化的了）
 
 
Loading...

© huhu 2023-2025