← 返回列表

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

单站 CodeAnalyzer Ultra 发布 Sun, 28 Apr 2024 08:30:00 +0800 入库 2026-11-18T16:38:03

原创 SASTing 2024-04-28 08:30 上海

CPG是如何通过遍历DFG的方式实现常量传播的,虽然其能力有限,但是对我们如何使用DFG有参考意义。

CPG中DFG(Data Flow Graph)的构建已经讲述完毕了,大家可能会有个疑惑,为什么要如此长篇大论地介绍DFG,有这个必要吗?答案是肯定的,原因如下:

所以,为了趁热打铁,让大家对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:

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

的值。它还能处理简单的二元操作,如算术运算,以及简单的字符串连接。
获取计算结果有两种方式:

另外,
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

方法中依次做了如下处理:

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

,正好相反,跟笔者上文推测的结论是一致的

点击公众号底部菜单栏"点击进群",加笔者好友(备注进群)

原文链接:https://mp.weixin.qq.com/s?__biz=MzkxNzY3MjE1NA==&mid=2247484259&idx=1&sn=128b706a657ae769cc584d9b16715cf2