书接上文,本节内容继续讲解CPG中其余节点的DFG构建过程~
这么分节的原因主要是考虑到了大家可能会产生阅读疲劳,俗话说:时间要花在刀刃上,所以把重头戏要放在每个小节的开头,这样更有利于大家的学习~(读者内心OS:我哭死,怎么会有这么用心的作者!)hiahiahia~
读后有收获的同学可以点个赞哦,要是能关注一下公众号就更好啦
大家的鼓励是笔者硬肝技术的动力!非常感谢大家文中有错误的地方欢迎大家私信/评论区指正。同时也欢迎大家将自己的想法发布在评论区,希望大家能够畅所欲言,共同进步~
欢迎点击公众号菜单栏"点击进群",与大佬一同交流技术。
OK,正文开始~
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边。
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 分支中对一个变量的不同赋值,...)。
为了看起来简洁一点(避免引起阅读疲劳~),此处三条边验证使用一套测试代码(若读者想做同样的测试,请在测试不同的边时注释掉其余代码,避免造成干扰),测试代码如下:
`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
由上文可知,ControlFlowSensitiveDFGPass 这一Pass是为了实现路径敏感(path sensitive)
接下来,我们来看看ControlFlowSensitiveDFGPass是怎么构建DFG,从而实现path sensitive的
ControlFlowSensitiveDFGPass的DFG构建有如下五步:
VariableDeclaration
与其 Reference
之间的所有边。实际上,它会清除函数中所有 VariableDeclaration
的所有进入和出去的 DFG 边。这包括initializer,但这个边会立即恢复。EOG(Evaluation Order Graph)的简要介绍:EOG是在将代码初步翻译到CPG后,作为AST节点之间的边构建的。EOG的目的是追踪代码执行的顺序,与CFG类似,其在更细粒度上区分表达式和子表达式的求值顺序;并且EOG是过程内的概念。
以上看不懂没关系,让笔者用简单易懂的话来解释!
大白话解释:比如我在某个方法中对一个变量引用a做了读取操作(如:
Object b = a; // 对a进行了读取
),那么现在就要逆序遍历EOG,找到在该语句之前最后一次对引用a
的写入处,然后对该写入节点连接一条边:a的写入节点 --> a的读取节点
++
"或"--
"对变量进行递增或递减操作,该语句的数据流来自对变量的前一次写入操作,并流向该语句的输入(即变量引用)。CPG将递增或递减后的值回写到该引用,并视 lhs
为对变量的“写入”操作。tips:这可能引入循环,并且看起来像是分支结构。在后续的 Pass/Analyses 阶段需要谨慎处理!
+=
、-=
、*=
、/=
等复合赋值运算符,数据流会从该表达式左侧引用的最近一次写操作流入lhs,然后,lhs 流向整个表达式。同时,rhs 也会流向整个表达式(如果是读取操作,这部分会单独处理)。最后,数据流回写到 lhs,并标记为对变量的最后一次写操作。tips:这可能引入循环,并且看起来像是分支结构。在后续的 Pass/Analyses 阶段需要谨慎处理!
var = rhs
这样的二元运算符赋值操作),那么,rhs 的值会流入当前变量。这被视为一次写操作。测试代码:(以下验证过程共用该测试代码)
`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 } } `
下图中的reference是测试代码中第14行的 str (引用读取处) System.out.println(str); // read access of str
下图中的reference是测试代码中第14行的 str (引用读取处)
System.out.println(str); // read access of str
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 (当前引用指向下一次引用读取处)
分析:通过观察对比第三步和第四步的边,可以发现,在构建DFG2这条边时多引入了一条 rhs --> BinaryOperator 的边,其他的都一样。
可以这么理解:实现对a的递增有两种写法(不仅限于):
1.
a++;
2.
a += 1;
这两种方式的区别无非就是,第二种比第一种**多了一个右操作数(rhs)**,所以,在构建DFG时要把rhs相关的边也加进去
基于上述思考,只需验证一条边即可,其他边与第三步中同理:
a+=1; // write access of a
)下图中的assignExpression是测试代码中的第16行 a = 3; // write access of a
DFG: lhs --> next read access of reference (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,冥冥之中,笔者感觉到,这跟之前文章 抽丝剥茧代码属性图CPG-第二弹:CPG中的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++中这种特殊语法而引入的边,所以,这条边就不继续往下验证啦,感兴趣的同学可以自行验证~
成员表达式(MemberExpression)关注以下字段:
base: Expression
: 被访问字段所属的对象表达式(如:MyObject.field
,其中base
就是MyObject
)
refersTo: Declaration?
: 被访问字段的声明,如果源码中未实现相应的类,则该字段为null
成员表达式(MemberExpression)代表对对象字段的访问,并通过 base
属性 对 Reference
类进行了扩展。
其继承关系如下:
如果相应类的实现可用(refersTo
不为null
),其处理方式与Reference
一致。如果refersTo
字段为null
,则base
会流向该MemberExpression
。
由上文可知,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字段 } } `
表达式列表(ExpressionList)关注以下字段:
expressions: List<Statement>
数据流从最后一个语句(statement
)流向ExpressionList
测试代码:
`package com.cpg.dfg; import java.util.Arrays; import java.util.List; public class TestExpressionList { public static void main(String[] args) { List<String> ls = Arrays.asList(args); int i, j = 0; for (i = 1, j = 1; i < ls.size(); i++) { // i = 1, j = 1 就是一个ExpressionList System.out.println(ls.get(i)); } } } `
可以看到 expressions
字段中包含两个AssignExpression
最后一个AssignExpression 流向了 ExpressionList
第一个AssignExpression 没有流向 ExpressionList
初始化列表表达式(InitializerListExpression)关注以下字段:
initializers: List<Expression>
: 初始化时赋的值数据流从initializers
流向InitializerListExpression
测试代码:
`package com.cpg.dfg; public class TestInitializerListExpression { public static void main(String[] args) { int[] a = new int[] {1,2}; // InitializerListExpression } } `
initializers
中存放了初始化值 1 和 2
1 和 2 都流向了 InitializerListExpression
键值表达式(KeyValueExpression)关注以下字段:
value: Expression
: 被赋的值value
流向 `KeyValueExpression
Java搞不出测试样例,继续看源码注释:
Represents a key / value pair, often found in languages that allow associative arrays or objects, such as Python, Golang or JavaScript.
Most often used in combination with an InitializerListExpression to represent the creation of an array.
翻译:
表示键/值对,常见于支持关联数组或对象的语言,如Python、Golang或JavaScript中。通常与InitializerListExpression一起使用,以表示创建数组的操作。
OK,与Java无关 ==
与我无瓜
lambda表达式关注以下字段:
function: FunctionDeclaration
: lambda声明处数据流从function
流向LambdaExpression
测试代码:
`package com.cpg.dfg; public class TestLambdaExpression { public static void main(String[] args) { Thread thread = new Thread(() -> System.out.println("I am SASTing!")); // LambdaExpression thread.start(); } } `
一元操作符(UnaryOperator)关注以下字段:
input: Expression
: 表达式的输入
operatorCode: String
: 表达式的运算符(Stirng类型)
DFG构建方式如下:
tips:CPG必须保证DFG构建的先后顺序,否则数据流会混乱~
当operator为 ++
或 --
时,DFG的构建与9.2.3中一致,故不再验证
operator != '++' & operator != '--' 的情况
测试代码:
`package com.cpg.dfg; public class TestUnaryOperatorExpression { public static void main(String[] args) { int b = 2; b = 1; // last write access of b int a = -b; // UnaryOperatorExpression System.out.println(a); } } `
DFG1: last write of refersTo --> input
DFG2: input --> UnaryOperator
返回语句(ReturnStatement)关注以下字段:
returnValue: Expression
: 返回值数据流从返回值流向整个语句
测试代码:
`package com.cpg.dfg; public class TestReturnStatement { public String getName() { return "SASTing"; // ReturnStatement } } `
重点掌握最常见的引用类(Reference
)的DFG构建过程(控制流敏感/不敏感)
refersTo!=null
时,MemberExpression
与Reference
的构建方法一致
LKY_OfficeTools(https://github.com/OdysseusYuan/LKY\_OfficeTools)
一键自动化 下载、安装、激活 Office 的利器。绿色、开源、安全、无毒。
可自动识别不同的操作系统架构,自动下载适配版本的 Office
正版激活模式,不会篡改任何系统文件
github 6.9k star
有需要的小伙伴可以转github详细了解~
CPG中的DFG构建-3(DFG收尾~)
文中的测试样例已同步****github仓库,欢迎大家多多star,仓库地址如下:
https://github.com/HaHarden/CPGPractise
进群方式:
1. 扫码进群
2. 点击公众号底部菜单栏"点击进群",加笔者好友(备注****进群)