抽丝剥茧代码属性图CPG-第二弹：CPG中的DFG-1

阅前声明：文末彩蛋（每期都有哦~）

开源仓库

=======

文中的测试样例已同步****github仓库，欢迎大家多多star，仓库地址如下：

https://github.com/HaHarden/CPGPractise

引言

读后有收获的同学可以点个赞哦，要是能关注一下公众号就更好啦大家的鼓励是笔者硬肝技术的动力！非常感谢大家

文中有错误的地方欢迎大家评论区指正。同时也欢迎大家将自己的想法发布在评论区，希望大家能够畅所欲言，共同进步~

上期内容已经介绍了CPG的基本概念以及其运行逻辑，建议没有学习的童鞋转战抽丝剥茧代码属性图CPG-第一弹：CPG介绍学习~

• CPG github地址：https://github.com/Fraunhofer-AISEC/cpg

• 官网：https://fraunhofer-aisec.github.io/cpg/

我们知道，CPG包含的数据量是相当庞大的，CPG几乎把静态分析可用的图都拿过来了，把这些图都封装到一个数据结构超图（super graphic）中，最终构成了一个看起来非常复杂的代码属性图，我们不仅可以从CPG上拿到基本的代码结构信息、控制流信息，甚至，我们可以拿来做数据流分析、污点分析等等，真是妙哉！

本节内容主要讲CPG中的DFG（Data Flow Graphic）

DFG是以节点间的边构建而成的。每个节点都有一组输入数据流（prevDFG）和输出数据流（nextDFG）。不同类型的节点构建数据流的方法也是不一样的。

接下来，我们看看不同类型的节点都是怎么构建DFG边的。

在构建DFG时CPG将节点共分为22种类型，再加上笔者会对每种类型的DFG构建过程一一验证，所以内容会比较多，因此DFG的构建分三篇文章发布~

1.CallExpression

CallExpression 用来表示方法调用，主要关注以下两个字段：

• invokes: List<FunctionDeclaration>: 存储被调用的方法

• arguments: List<Expression>: 方法调用的实参

CPG将被调方法分为两种类型：

• 被调用的方法在源码中已经实现（CPG可以对其进行分析），这种情况invokes不为空

• 被调用的方法在源码中没有实现（如：调用第三方库函数），这种情况invokes为空

1.1.Known function

对于invokes列表中的每个方法，会构建两条数据流边：

• 边1：CallExpression的实参流向被调用方法的形参的边

• 边2：被调用方法的声明流向CallExpression的边

此处与我之前写的文章"SAST-数据流分析方法-理论"讲的ICFG的构建方法类似，笔者认为这种基础性质的东西还是有必要掌握的，建议对ICFG构建不熟悉的同学点链接再学习一下~

1.1.1.验证边1

测试代码：

`package com.cpg.dfg;      public class TestCallExpression {       public static void main() {           int a, b, c;           a = 6;           b = addOne(a);  // CallExpression           c = b - 3;           b = ten();  // CallExpression           c = a * b;       }          static int addOne(int x) {           int y = x + 1;           return y;       }          static int ten() {           return 10;       }   }   `

CPG翻译后的结果是TranslationResult，在后续的文章CPG参数介绍中会详细介绍这个类型的各个字段，莫慌，现在先跟着笔者的节奏走~

• 验证实参是否流向了被调方法的形参

`translationResult.calls   // calls方法获取源码中所有的方法调用表达式   `

可以看到，结果与源码是对应的，好，我们接着往下走，看看真实的DFG边是不是像上文说的那样构建的~

tips：可能细心的同学会发现两个调用表达式的类型不是CallExpression，而是MemberCallExpression，这里给大家讲一下，cpg的CallExpression有两个子类，一个是MemberCallExpression，另一个是ConstructExpression，如下图，见名知意，此处不多解释~

我们现在看第一个CallExpression

`translationResult.calls[0].arguments  // arguments方法获取调用表达式的所有实参   `

可以看到，确实有一个实参a，那我们再来看a的nextDFG是不是流向了addOne方法的形参处

事实证明，确实有一条实参argument流向被调方法addOne形参的边。

1.1.2.验证边2

• 验证被调方法声明是否流向CallExpression

`translationResult.calls[0].prevDFG  // 获取第一个CallExpression的前一个DFG边   `

可以看到，确实有一条被调方法addOne的声明处流向CallExpression的边

1.2.Unknown function

• 边1：所有实参流向CallExpression的边

• 边2：base（也就是caller）流向CallExpression的边

老样子，上代码！开启debug大法

测试代码：

`package com.cpg;      import org.apache.shiro.util.StringUtils;      public class TestUnknownFunction {       public static void main() {           String str = "hello cpg";           boolean has = StringUtils.hasText("cpg");  // CallExpression （第三方库函数）       }   }   `

1.2.1.验证边1

• 验证实参是否流向CallExpression

`translationResult.calls[0].arguments[0].nextDFG   `

可以看到，确实有实参流向CallExpression的边

1.2.2.验证边2

• 验证base（caller）是否流向CallExpression

`translationResult.calls[0].prevDFG  // 获取所有流向CallExpression的节点   `

可以看到，流向CallExpression的所有DFG中，第二个是实参，第一个就是所谓的base，也就是第三方库的caller。

所以，确实有一条base（caller）流向CallEXpression的边

tips：若读者也要做类似的测试，一定要记得关闭CPG自带的方法推断功能（inferFunctions），否则不会得到以上结果（方法推断功能会将Unknown Function做虚拟化操作，至于如何关闭此处就不详细解释了，防止造成误导，后续的CPG使用文章中会详细介绍）。

OK，目前为止，CallExpression的DFG构建过程已经验证完成，后续的其他类型的节点的验证过程直接贴图了，不再赘述，大家直接看图就OK~

2.CastExpression

CastExpression（类型强转表达式）关注以下字段：

• expression: Expression: 需要进行类型转换的表达式（也就是被转换的对象）

构建一条DFG边：

• expression字段（被转换的对象）流向CastExpression

2.1.验证边

• expression字段  --> CastExpression

测试代码：

`package com.cpg.dfg;      public class TestCastExpression {       public static void main(String[] args) {           Object o = getMyObject(1);           if (o instanceof MyObject) {               MyObject myObject = (MyObject) o;  //(MyObject) o 是一个 CastExpression               System.out.println(myObject);           }       }          private static Object getMyObject(int a) {           if (a > 0) {               return new MyObject();           }           else {               return new Object();           }       }       static class MyObject {          }   }   `

该示例中第7行(MyObject) o就是一个CastExpression，那么他的expression字段就是o

构建的这条边就是 o --> CastExpression

debug验证结果如下：

3.AssignExpression

AssignExpression就是赋值表达式，其关注以下两个字段：

• lhs: List<Expression>: 赋值语句的所有左表达式

• rhs: List<Expression>: 赋值语句的所有右表达式

3.1.Normal assignment

赋值操作符为等号 operatorCode: =

• 边1：rhs 流向 lhs 的边

• 边2：rhs 流向 AssignExpression的边 （赋值操作的AST父节点不是Block时会加这条边）

如果lhs由多个变量（或元组）组成，CPG会尝试根据索引拆分rhs。如果无法拆分，则整个rhs会流向lhs中的所有变量

如果 lhs 与 rhs 的长度相等：

3.1.1.验证边1

• rhs 流向 lhs 的边

测试代码如下：

`package com.cpg.dfg;      public class TestAssignExpression {       public static void main(String[] args) {           // Normal assignment           MyObject o1 = new MyObject();           MyObject o2 = new MyObject();           o1 = o2;  // AssignExpression           System.out.println(o1);           // Compound assignment           int a = 1;           a += 1;  // AssignExpression           System.out.println(a);       }          static class MyObject{}   }   `

tips：此处使用CPG提供的访问者模式，自定义Visitor找translateResult中的AssignExpression，要注意的是一定要开启CPG提供的 DFGPass（并同时开启SymbolResolver、EvaluationOrderGraphPass、TypeHierarchyResolver、TypeResolver，因为Pass之间有依赖关系）

可以看到，确实有一条 rhs 流向 lhs 的边

3.1.2.验证边2

• rhs 流向 AssignExpression的边 （赋值操作的AST父节点不是Block时会加这条边）

在某些编程语言中，子表达式中可以存在赋值操作（例如 a + (b=1)，我们现在只关注CPG分析java代码，所以，此处偷个小懒，就不验证啦，感兴趣的同学可以自行验证~

3.2.Compound assignment

赋值操作符为其他符号 operatorCode: *=, /=, %=, +=, -=, <<=, >>=, &=, ^=, |=

• 边1：lhs 和 rhs 流向二元运算表达式

• 边2：二元运算表达式流向 lhs

CPG必须确保前两项操作在最后一项操作之前完成

3.2.1.验证边1

• lhs 和 rhs 流向二元运算表达式

测试代码同3.1.1

• rhs流向二元运算表达式

• lhs流向二元运算表达式（先忽略第二条边，此处验证了有lhs流向二元运算表表达式的边即可）

3.2.2.验证边2

• 二元运算表达式流向 lhs

4.BinaryOperator

BinaryOperator（二元运算符），关注以下字段：

• operatorCode: String: 操作符

• lhs: Expression: 左表达式

• rhs: Expression: 右表达式

CPG将运算符分为三类：

• 赋值运算，

• 带有计算的赋值运算

• 纯计算运算

CPG会添加以下边：

• lhs 和 rhs 都会流入到二元运算符表达式中

4.1.验证边

测试代码：

`package com.cpg.dfg;      public class TestBinaryOperator {       public static void main(String[] args) {           int a = 1;           int b = 2;           boolean flag = a > b;  // a > b 就是一个 BinaryOperator       }   }   `

• lhs 和 rhs 都会流入到二元运算符表达式中

lhs 流向 BinaryOperator

rhs 流向 BinaryOperator

5.NewArrayExpression

NewArrayExpression（New数组表达式）关注以下字段：

• initializer: Expression: 数组的初始化值

DFG构建一条边：

• initializer（数组初始化值）流向 NewArrayExpression

5.1.验证边

测试代码：

`package com.cpg.dfg;      public class TestNewArrayExpression {       public static void main(String[] args) {           int[] array = new int[]{1,2,3};  // new int[]{1,2,3} 就是一个 NewArrayExpression       }   }   `

可以看到，确实有initializer（数组初始化值）流向 NewArrayExpression的边

6.NewExpression

new表达式关注以下字段：

• initializer: Expression: 表达式的初始化值

DFG构建一条边：

• initializer流向整个NewExpression

6.1.验证边

测试代码：

`package com.cpg.dfg;      public class TestNewExpression {       public static void main(String[] args) {           MyObject o = new MyObject("cpg");  // new MyObject("cpg") 就是一个 NewExpression       }       static class MyObject {           String name;              public MyObject(String name) {               this.name = name;           }       }   }   `

initializer流向整个NewExpression的边

7.SubscriptExpression

SubscriptExpression（下标表达式）关注以下两个字段：

• arrayExpression: Expression: 被访问的数组

• subscriptExpression: Expression: 被访问的索引

构建一条DFG边：

• arrayExpression（被访问的数组）流向SubscriptExpression，不会区分数组的下标

由此我们可以推断出CPG在处理数组相关的数据流时，将数组看作一个整体去处理，也就是说，若CPG在Pass阶段对数组不做特殊处理，那么其在处理数组容器时是域不敏感的（若观点有误可以评论区/私信指正）

7.1.验证边

测试代码：

`package com.cpg.dfg;      public class TestSubscriptExpression {       public static void main(String[] args) {           String a = args[0];  // args[0]是一个 SubscriptExpression       }   }   `

arrayExpression字段就是 args数组

有一条args数组流向SubscriptExpression的边

8.ConditionalExpression

ConditionalExpression（三元运算符表达式）主要关注以下字段：

• condition: Expression: 被执行的条件

• thenExpression: Expression: 条件成立时要执行的表达式

• elseExpression: Expression: 条件不成立时要执行的表达式

DFG构建两条边：

• thenExpr流向ConditionalExpression

• elseExpression流向ConditionalExpression

tips：此处将thenExpr和elseExpression都流向了ConditionalExpression，所以若CPG在Pass阶段不对三元运算符的数据流做特殊处理，那么CPG在处理三元运算符时是路径不敏感的（若观点有误可以评论区/私信指正）

8.1.验证边1

测试代码：

`package com.cpg.dfg;      public class TestConditionalExpression {       public static void main(String[] args) {           int b = 2;           int a = 1;           a = a==b ? 1 : 2;  // ConditionalExpression       }   }   `

• thenExpr流向ConditionalExpression的边

8.2.验证边2

测试代码同8.1

• elseExpression流向ConditionalExpression的边

总节

• 除AssignExpression的Normal assignment外，其他类型的表达式都至少有一条流向当前Expression的边

• 在构建DFG时，CPG对于数组容器 SubscriptExpression的处理是域不敏感的（参考 7.SubscriptExpression）

• 在构建DFG时，CPG对三元操作符ConditionalExpression的处理是路径不敏感的（参考 8.ConditionalExpression）

提效工具推荐

Snipaste（https://www.snipaste.com/）

Snipaste 是一个简单但强大的贴图工具，同时也可以执行截屏、标注等功能。其支持包括但不限于以下功能：

• 取色器

• 放大镜

• 画笔标注

• 贴图

取色器使用如图，大家有需要的点击官网链接下载即可~

下期预告

CPG 中的 DFG 构建-2

下节重点介绍**引用类型（Reference）**的 DFG 边的构建过程