原创 SASTing 2024-04-28 08:30 上海
CPG是如何通过遍历DFG的方式实现常量传播的,虽然其能力有限,但是对我们如何使用DFG有参考意义。
CPG中DFG(Data Flow Graph)的构建已经讲述完毕了,大家可能会有个疑惑,为什么要如此长篇大论地介绍DFG,有这个必要吗?答案是肯定的,原因如下:
- DFG(Data Flow Graph)是程序分析的基础,在任何程序分析框架中都是非常重要的,其很大程度上影响分析结果的精度,CPG中当然也不例外
- CPG框架通过遍历DFG的方式解决了很多通用型分析,如 ValueEvaluator 、 Out of Bound Check 、 Null Pointer Check 等
所以,为了趁热打铁,让大家对DFG的运用更加熟练,本文就针对CPG框架中自带的基于DFG实现的
ValueEvaluator
(常量传播)做分析。
读后有收获的同学可以点个赞哦
,要是能关注一下公众号就更好啦
\~大家的鼓励是笔者硬肝技术的动力!
非常感谢大家\~

文中有错误的地方欢迎大家私信/评论区指正。同时也欢迎大家将自己的想法发布在评论区,希望大家能够畅所欲言,共同进步\~
欢迎点击公众号菜单栏"点击进群",与大佬一同交流技术。
ValueEvaluator
值求解器,此处可以理解为
The value evaluator tries to evaluate the (constant) value of an Expression basically by following DFG edges until we reach a Literal. It also evaluates simple binary operations, such as arithmetic operations, as well as simple string concatenations.
The result can be retrieved in two ways:
- The result of the resolve function is a JVM object which represents the constant value
- Furthermore, after the execution of evaluateInternal, the latest evaluation path can be retrieved in the path property of the evaluator.
It contains some advanced mechanics such as resolution of values of arrays, if they contain literal values. Furthermore, its behaviour can be adjusted by implementing the cannotEvaluate function, which is called when the default behaviour would not be able to resolve the value. This way, language specific features such as string formatting can be modelled.
解释:
ValueEvaluator
通过沿DFG边跟踪,直至抵达Literal(字面量,也就是常量),来计算
Expression
的值。它还能处理简单的二元操作,如算术运算,以及简单的字符串连接。
获取计算结果有两种方式:
- resolve 方法返回一个代表该常量值的JVM对象
- 在 evaluateInternal 方法执行后,可以通过 evaluator 的 path 属性获取到当前求值路径
另外,
ValueEvaluator
还包含一些高级机制,例如:可以解析数组的常量值。此外,若解析常量失败,可以通过实现
cannotEvaluate
函数来自定义一些方法行为。这样,就可以模拟诸如字符串格式化等语言特定特性。
CPG中的
ValueEvaluator
(常量传播)是通过遍历DFG的方式实现的。
首先看其核心方法
evaluate
可以看到,其调用了
evaluateInternal
方法
evaluateInternal
方法针对不同类型的节点做了不同的处理,若不支持的节点类型默认调用
cannotEvaluate
方法。
显而易见的是,解决问题的整体思路是采用递归的方式,每次递归进去以后,就把当前正在解析的节点加到
path
属性中,递归的终止条件就是:
node is Literal\<*>
也就是递归地进行常量传播,直到遇到常量节点为止,然后直接返回节点的
value
值
VariableDeclaration
变量声明节点直接将初始化值
initializer
作为递归参数传递
tips:这里应该很好理解,一个变量声明的常量值自然就是其初始化赋予的常量值;同时还会传递一个
depth+1
参数,表示当前递归的深度,这里是为了控制递归的深度,防止影响算法性能
Reference
引用类型的节点,调用
handleReference
方法
可以看到,在处理引用类型节点时,要先对引用的
prevDFG
做
filter
操作,
filter
操作主要是针对
UnaryOperator
(
++
, --
),这种情况针对引用节点会构建两条DFG边(可回顾:抽丝剥茧代码属性图CPG-第三弹:CPG中的DFG-2),需要把从
reference
节点出去的DFG边过滤掉,以减少递归次数。
对
prevDFG
过滤完后,只处理
size
为 1 的情况,将
prevDFG.first()
作为递归参数传递,其他
size
不为 1 的情况在
MultiValueEvaluator
中有支持,此处不详细展开讲解,感兴趣的童鞋可以直接撸CPG源码\~
UnaryOperator
一元操作符节点,调用
handleUnaryOp
方法
可以看到,
handleUnaryOp
方法关注表达式的输入
input
,若
input
为数值类型
Number
,直接将
input
作为递归参数传递。
BinaryOperator
二元操作符,调用
handleBinaryOperator
方法
lhs
与
rhs
求值,然后再调用
computeBinaryOpEffect
方法,
operator
,计算表达式的最终值。
SubscriptExpression
下标表达式,调用
handleSubscriptExpression
方法
可以看到,
handleSubscriptExpression
方法中依次做了如下处理:
- initializers 为 KeyValueExpression 时,先对元素进行过滤,然后存储到一个 ArrayList 中,然后再从这个list中取值(其实现细节不是本节讨论的重点,感兴趣的童鞋可以自行研究源码),然后 return
- initializers 是常量,直接返回其 value
- 表达式 的 arrayExpression 是 SubscriptExpression ,将其作为递归参数传递
ConditionalExpression
handleConditionalExpression
方法
可以看到
handleConditionalExpression
方法中只支持
condition
为
BinaryOperator
的情况,其分别对
lhs
与
rhs
做了常量传播,然后如果二者相等,就返回
thenExpression
的值,反之,返回
elseExpression
的值。
很明显,这里的处理是有bug的,试想一下,若
condition
是一个
BinaryOperator
,但是其
operatorCode
是
!=
,那得到的结果岂不是刚好相反了嘛。先保留这个疑问,后续对其进行验证。
AssignExpression
赋值表达式,调用
handleAssignExpression
方法
single value
(若是容器相关的赋值操作,只支持容器内只有一个元素的情况)的情况,并且此处只对
CompoundAssignment
(
operatorCode: *=, /=, %=, +=, -=, \<\<=, >>=, &=, ^=, |=
)的赋值做了处理(
MultiValueEvaluator
中有更完善的支持)。其大致逻辑如下:
- 先求 lhs 与 rhs 的常量值
- 再对 lhs 与 rhs 做运算操作,返回运算后的值
tips:笔者本来是想对第二小节的所有节点类型作一一验证的,但是验证过后,得出一个结论:
ValueEvaluator
分析能力很low,所以都搬过来也没什么意义。所以就只验证了其是否支持过程间分析,以及上文提到的bug。
测试代码:
package com.cpg.dfg.analyze.valueevaluator;public class TestReference { // interprocedural test case public void test() { int a = 1; a = getA(a); System.out.println(a); } public int getA(int a) { a++; return a; }}
测试结果如下:
可以看到,涉及方法调用时,无法分析出常量值,所以CPG自带的
ValueEvaluator
并不是过程间的分析
package com.cpg.dfg.analyze;public class TestValueEvaluator { public void test() { int a = 1; a = a != 1 ? 2 : a; // there is a bug when ValueEvaluator run System.out.println(a); // the value of a is 2,it's error.It should be 1 }}
果然有bug,第7行输出
a
时,常量追踪的结果是
2
,而不是
1
,正好相反,跟笔者上文推测的结论是一致的
- CPG自带的 ValueEvaluator 的常量传播能力很有限
- CPG自带的 ValueEvaluator 是过程内的分析
- ConditionalExpression 的处理有bug
- 慎用CPG自带的 ValueEvaluator ,但是若需要使用DFG做checker开发时,可以借鉴 ValueEvaluator 中对DFG的使用
点击公众号底部菜单栏"点击进群",加笔者好友(备注进群)