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
方法
handleBinaryOperator
方法分别对lhs
与rhs
求值,然后再调用computeBinaryOpEffect
方法,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
方法
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的使用
点击公众号底部菜单栏"点击进群",加笔者好友(备注****进群)