白盒安全-常量传播还能这么搞？

引言

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（常量传播）做分析。

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

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

欢迎点击公众号菜单栏"点击进群"，与大佬一同交流技术。

1.介绍

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函数来自定义一些方法行为。这样，就可以模拟诸如字符串格式化等语言特定特性。

2.实现

2.1.常量传播算法

CPG中的ValueEvaluator（常量传播）是通过遍历DFG的方式实现的。

首先看其核心方法evaluate

可以看到，其调用了evaluateInternal方法

evaluateInternal方法针对不同类型的节点做了不同的处理，若不支持的节点类型默认调用cannotEvaluate方法。

显而易见的是，解决问题的整体思路是采用递归的方式，每次递归进去以后，就把当前正在解析的节点加到path属性中，递归的终止条件就是：

`node is Literal<*>   `

也就是递归地进行常量传播，直到遇到常量节点为止，然后直接返回节点的value值

2.2.判定节点是否为常量

2.2.1.VariableDeclaration

VariableDeclaration变量声明节点直接将初始化值initializer作为递归参数传递

tips:这里应该很好理解，一个变量声明的常量值自然就是其初始化赋予的常量值；同时还会传递一个depth+1参数，表示当前递归的深度，这里是为了控制递归的深度，防止影响算法性能

2.2.2.Reference

Reference引用类型的节点，调用handleReference方法

可以看到，在处理引用类型节点时，要先对引用的prevDFG做filter操作，filter操作主要是针对UnaryOperator（++, --），这种情况针对引用节点会构建两条DFG边（可回顾：抽丝剥茧代码属性图CPG-第三弹：CPG中的DFG-2），需要把从reference节点出去的DFG边过滤掉，以减少递归次数。

对prevDFG过滤完后，只处理size为 1 的情况，将prevDFG.first()作为递归参数传递，其他size不为 1 的情况在MultiValueEvaluator中有支持，此处不详细展开讲解，感兴趣的童鞋可以直接撸CPG源码~

2.2.3.UnaryOperator

UnaryOperator一元操作符节点，调用handleUnaryOp方法

可以看到，handleUnaryOp方法关注表达式的输入input，若input为数值类型Number，直接将input作为递归参数传递。

2.2.4.BinaryOperator

BinaryOperator二元操作符，调用handleBinaryOperator方法

handleBinaryOperator方法分别对lhs与rhs求值，然后再调用computeBinaryOpEffect方法，computeBinaryOpEffect方法就是真正地去执行operator，计算表达式的最终值。

2.2.5.SubscriptExpression

SubscriptExpression下标表达式，调用handleSubscriptExpression方法

可以看到，handleSubscriptExpression方法中依次做了如下处理：

initializers为KeyValueExpression时，先对元素进行过滤，然后存储到一个ArrayList中，然后再从这个list中取值（其实现细节不是本节讨论的重点，感兴趣的童鞋可以自行研究源码），然后return
initializers是常量，直接返回其value
表达式的arrayExpression是SubscriptExpression，将其作为递归参数传递

2.2.6.ConditionalExpression

ConditionalExpression三元运算符，调用handleConditionalExpression方法

可以看到handleConditionalExpression方法中只支持condition为BinaryOperator的情况，其分别对lhs与rhs做了常量传播，然后如果二者相等，就返回thenExpression的值，反之，返回elseExpression的值。

很明显，这里的处理是有bug的，试想一下，若condition是一个BinaryOperator，但是其operatorCode是!=，那得到的结果岂不是刚好相反了嘛。先保留这个疑问，后续对其进行验证。

2.2.7.AssignExpression

AssignExpression赋值表达式，调用handleAssignExpression方法

handleAssignExpression方法只支持single value（若是容器相关的赋值操作，只支持容器内只有一个元素的情况）的情况，并且此处只对CompoundAssignment（operatorCode: *=, /=, %=, +=, -=, <<=, >>=, &=, ^=, |=）的赋值做了处理（MultiValueEvaluator中有更完善的支持）。其大致逻辑如下：

先求 lhs 与 rhs 的常量值
再对 lhs 与 rhs做运算操作，返回运算后的值

3.验证

tips:笔者本来是想对第二小节的所有节点类型作一一验证的，但是验证过后，得出一个结论：ValueEvaluator分析能力很low，所以都搬过来也没什么意义。所以就只验证了其是否支持过程间分析，以及上文提到的bug。

3.1.Reference

测试代码：

`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并不是过程间的分析

3.2.ConditionalExpression