引言

书接上文，本节内容继续讲解CPG中其余节点的DFG构建过程~

这么分节的原因主要是考虑到了大家可能会产生阅读疲劳，俗话说：时间要花在刀刃上，所以把重头戏要放在每个小节的开头，这样更有利于大家的学习~（读者内心OS：我哭死 手动狗头）

读后有收获的同学可以给公众号点点关注，非常感谢~ 文中有错误的地方欢迎大家评论区指正。同时也欢迎大家将自己的想法发布在评论区，总而言之，大家畅所欲言~

OK，正文开始~

9.Reference

Reference类（引用类）在源码中的注释如下：

An expression, which refers to something which is declared, e.g. a variable. For example, the expression a = b, which itself is an AssignExpression, contains two References, one for the variable a and one for variable b, which have been previously been declared.

解释：

Reference是一个表达式，它指向已被声明的事物（如变量）。

例如，表达式 a = b（本身是一个AssignExpression）包含了两个References，分别引用先前已被声明的变量 a 和变量 b。

Reference（引用）关注的字段：

• refersTo: Declaration: 变量或符号的声明
• access: AccessValues: 确定值是被读取或写入还是 两者兼有

这是DFG中最为复杂的一个概念。CPG需要区分由DFGPass生成的DFG边和由ControlFlowSensitiveDFGPass生成的DFG边。

9.1.DFGPass的DFG构建

DFGPass根据对变量的访问生成非常简单的边，具体如下：

• 读取值：数据流从引用声明处流向表达式

• 写入值：数据流从表达式流向引用声明处

• 读取+写入值：以上两条边都有

关于以上DFG边的设计，还处于不稳定的状态，官网给出了如下解释：

This mostly serves one purpose: The current function pointer resolution requires such flows. Once the respective passes are redesigned, we may want to update this.

The ControlFlowSensitiveDFGPass completely changes this behavior and accounts for the data flows which differ depending on the program's control flow (e.g., different assignments to a variable in an if and else branch, ...).

大致意思如下：

这一设计主要是为满足一个特定目标：当前函数指针解析机制需要有这样的数据流处理。一旦相应的Pass阶段重新设计，CPG可能需要对此进行更新。

ControlFlowSensitiveDFGPass 有不同的处理方式，考虑到了程序控制流对数据流的影响（例如，在 if 和 else 分支中对一个变量的不同赋值，...）。

9.1.1.验证边

为了看起来简洁一点（避免引起阅读疲劳~），此处三条边验证使用一套测试代码（若读者想做同样的测试，请在测试不同的边时注释掉其余代码，避免造成干扰），测试代码如下：

package com.cpg.dfg;

public class TestReference {
    public static void main(String[] args) {
        String a = "a";
        readA(a);  // read access of a
        a = "";  // write access of a
        a += "b";  // read and write access of a
    }
    private static void readA(String a) {
        System.out.println("read access of " + a);
    }
}

• 读取值 验证：refersTo --> Reference

• 写入值 验证：Reference --> refersTo

也可以这么看~

• 读取+写入值 验证： refersTo --> Reference & Reference --> refersTo

refersTo --> Reference

Reference --> refersTo

9.2.ControlFlowSensitiveDFGPass的DFG构建

由上文可知，ControlFlowSensitiveDFGPass 这一Pass是为了实现路径敏感（path sensitive）

接下来，我们来看看ControlFlowSensitiveDFGPass是怎么构建DFG，从而实现path sensitive的

ControlFlowSensitiveDFGPass的DFG构建有如下五步：

9.2.1.第一步

• 首先，它会清除 VariableDeclaration 与其 Reference 之间的所有边。实际上，它会清除函数中所有 VariableDeclaration 的所有进入和出去的 DFG 边。这包括initializer，但这个边会立即恢复。

9.2.2.第二步

• 对于一个引用（Reference）的所有读取处，它会收集对该变量的所有潜在前置赋值，并将这些赋值加入到输入的数据流图（DFG）边中。这是通过逆向遍历 EOG（Evaluation Order Graph）来完成的，直到为每个可能的路径找到对变量的第一次赋值。

EOG(Evaluation Order Graph)的简要介绍：EOG是在将代码初步翻译到CPG后，作为AST节点之间的边构建的。EOG的目的是追踪代码执行的顺序，与CFG类似，其在更细粒度上区分表达式和子表达式的求值顺序；并且EOG是过程内的概念。

以上看不懂没关系，让笔者用简单易懂的话来解释！

大白话解释：比如我在某个方法中对一个变量引用a做了读取操作（如：Object b = a; // 对a进行了读取）,那么现在就要逆序遍历EOG，找到在该语句之前所有对引用a的写入处，然后对所有的写入节点连接一条边：

a的写入节点 --> a的读取节点

9.2.3.第三步

• 如果程序中使用"++"或"--"对变量进行递增或递减操作，该语句的数据流来自对变量的前一次写入操作，并流向该语句的输入（即变量引用）。CPG将递增或递减后的值回写到该引用，并视 lhs 为对变量的“写入”操作。

​ tips：这可能引入循环，并且看起来像是分支结构。在后续的 Pass/Analyses 阶段需要谨慎处理！

9.2.4.第四步

• 对于诸如 +=、-=、*=、/= 等复合赋值运算符，数据流会从该表达式左侧引用的最近一次写操作流入lhs,然后，lhs 流向整个表达式。同时，rhs 也会流向整个表达式（如果是读取操作，这部分会单独处理）。最后，数据流回写到 lhs，并标记为对变量的最后一次写操作。

​ tips：这可能引入循环，并且看起来像是分支结构。在后续的 Pass/Analyses 阶段需要谨慎处理！

9.2.5.第五步

• 如果变量被赋值（例如：var = rhs 这样的二元运算符赋值操作），那么，rhs 的值会流入当前变量。这被视为一次写操作。

9.2.6.验证第一步中的边

测试代码：(以下验证过程共用该测试代码)

package com.cpg.dfg;

public class TestReferenceCFS {
    // ControlFlowSensitiveDFGPass test case
    public static void main(String[] args) {
        int a = 1;
        String str = "init";  // str initializer
        if (a > 0) {
            str = "a";  // str 赋值
        }
        else {
            str = "b";  // str 赋值
        }
        System.out.println(str);  // read access of str
        a = 2;  // write access of a
        a = 3;  // write access of a
        a++;  // write access of a
        System.out.println(a); // read access of a
        a += 1;  // write access of a
        System.out.println(a); // read access of a
    }
}

• initializer --> VariableDeclaration

下图中的reference是测试代码中第14行的 str (引用读取处) System.out.println(str); // read access of str

9.2.7.验证第二步中的边

• reference读取前的所有reference写入处 --> 当前reference

下图中的reference是测试代码中第14行的 str (引用读取处)

System.out.println(str); // read access of str

9.2.8.验证第三步中的边

• DFG1: last write access of refersTo --> reference

  • (可参考9.2.3.第三步中的DFG构件图，debug时的reference相当于图中的input节点)

  • 下图中的 reference 是 第17行的 a引用

    a++; // write access of a

• DFG2: reference --> UnaryOperator

• DFG3: UnaryOperator --> reference

• DFG4: reference --> next read access of refersTo (当前引用指向下一次引用读取处)

9.2.9.验证第四步中的边

分析：通过观察对比第三步和第四步的边，可以发现，在构建DFG2这条边时多引入了一条 rhs --> BinaryOperator 的边，其他的都一样。

可以这么理解：实现对a的递增有两种写法（不仅限于）：

1.a++;

2.a += 1;

这两种方式的区别无非就是，第二种比第一种多了一个右操作数(rhs)，所以，在构建DFG时要把rhs相关的边也加进去

基于上述思考，只需验证一条边即可，其他边与第三步中同理：

• rhs --> BinaryOperator (图中的assignExpression就是第19行 a+=1; // write access of a)

9.2.10.验证第五步中的边

• DFG: rhs --> lhs

下图中的assignExpression是测试代码中的第16行 a = 3; // write access of a

• DFG: lhs --> next read access of rederence (17行 a++; 包含a的读取和写入)

• DFG2: lhs --> BinaryOperator

验证之前，先来看看源码对 BinaryOperator 类的解释（为什么要看解释呢，因为笔者搞半天都没找到这条边，555~，是什么原因导致的呢，最终还是被我发现了！）

A binary operation expression, such as "a + b". It consists of a left hand expression (lhs), a right hand expression (rhs) and an operatorCode.

Note: For assignments, i.e., using an = or +=, etc. the AssignExpression MUST be used.

翻译：

一个二元操作表达式，比如 "a + b"。它由左操作数（lhs）、右操作数（rhs）以及运算符代码组成。 注意：对于赋值操作，即使用 = 或 += 等，必须使用 AssignExpression。

由此可以看出，当我们代码中使用 =操作符时，CPG会认为是一个AssignExpression，冥冥之中，笔者感觉到，这跟之前DFG-1中3.1.2（加链接，待修改）中提到的语法特性有关：有的语言支持 rhs 是一个赋值表达式的情况，这条边会不会就是为了处理这种代码情况呢？好，我们接着往下看，看看AssignExpression的源码解释：

Represents an assignment of a group of expressions (in the simplest case: one) from the right hand side to the left-hand side.

This is intentionally modelled as an expression, since some languages support using the resulting value of an assignment as an expression. For example C++ allows the following:

int a;

int b = (a = 1);

In this example, the type of the AssignExpression is an int.

However, since not all languages support this model, we explicitly introduce the usedAsExpression. When this property is set to true (it defaults to false), we model a dataflow from the (first) rhs to the AssignExpression itself.

翻译过来是这样子的：

AssignExpression表示将一组表达式（最简单的情况下为一个表达式）从右操作数赋值给左操作数的操作。 有意将其建模为一个表达式，因为在某些语言中支持将赋值表达式的结果当作普通表达式使用。例如，在cpp中允许如下操作：

int a;
int b = (a = 1);

在这个例子中，AssignExpression的类型为int。 然而，并非所有语言都支持这种模型，所以我们专门引入了usedAsExpression属性。当该属性设置为true（默认为false），我们就模拟了一条从（首个）右操作数到AssignExpression自身的数据流。

原因终于找到啦，这是为了适配C++中这种特殊语法而引入的边，所以，这条边就不继续往下验证啦，感兴趣的同学可以自行验证~

10.MemberExpression

成员表达式（MemberExpression）关注以下字段：

• base: Expression: 被访问字段所属的对象表达式（如：MyObject.field，其中base就是MyObject）
• refersTo: Declaration?: 被访问字段的声明，如果源码中未实现相应的类，则该字段为null

成员表达式（MemberExpression）代表对对象字段的访问，并通过 base 属性 对 Reference 类进行了扩展。

其继承关系如下：

如果相应类的实现可用（refersTo不为null），其处理方式与Reference一致。如果refersTo字段为null，则base会流向该MemberExpression。

10.1.验证边

由上文可知，MemberExpression是Reference的子类，若其refersTo字段不为null，那么其处理方式与Reference一致，所以此处我们只验证refersTo为null的情况。

测试代码：

package com.cpg.dfg;

public class TestMemberExpression {
    // refersTo == null  test case
    public static void main(String[] args) {
        System.out.println(ClassWithoutNameField.name);  // ClassWithoutNameField.name是一个MemberExpression，base就是ClassWithoutNameField
    }
    static class ClassWithoutNameField {
        // 该类没有name字段
    }
}

• base --> MemberExpression

总结

• 重点掌握最常见的引用类(Reference)的DFG构建过程（控制流敏感/不敏感）
• refersTo!=null时，MemberExpression与Reference的构建方法一致

github仓库

• github.com/HaHarden/CP…
• github.com/HaHarden/Be…