阅前声明
在大家的日常开发及办公过程中,或多或少会遇到一些看似棘手的问题,如果纯手动操作可能非常繁琐效率极低。(当然,如果你是一名兼职脚本开发工程师,大概率也难不倒你

)
但是,在你花费半个小时写完一个完美的脚本,正在享受其优雅的运行过程时,耳边传来一句话“不用这么麻烦,我给你个工具一键解决”,此时你的内心是这样的(

%%##%¥……&……%)。感觉自己像个Joker~
所以,为了让大家不当Joker!为了同事间的和睦!为了美好的明天!为了世界和平!

笔者决定,每篇文章文末都会推荐一个提效小工具,若有需要,大家自行下载~
好了,废话不多说,开始今天的正文!
正文开始
众所周知,数据流分析是实现污点分析的一种常用技术。
数据流分析分为过程内的数据流分析与过程间的数据流分析。前者是对一个方法体内的数据流分析,主要是基于CFG分析,不涉及方法调用;后者是基于不同方法间的数据流分析,主要是基于ICFG+CG分析,会涉及方法调用。
一、过程内数据流分析
- CFG的构建
1.1.把程序转换为IR(此处采用3AC)表示
3地址码中的地址可能有如下的几种类型:
名字(Name),包括
用于指示程序位置,方便跳转指令的书写
变量(Variable)
标签(Label)
字面常量(Literal Constant)
编译器生成的临时量(Compiler-Generated Temporary)
每一种指令都有其对应的 3 地址码形式,一些常见的 3 地址码形式如下:(x, y, z是变量的地址)
x = y bop z // bop 是双目操作符(Binary Operator),可以是算数运算符,也可以是逻辑运算符x = uop y // uop 是单目操作符(Unary Operator),可能是取负、按位取反或者类型转换x = ygoto L // goto 是无条件跳转,L 是标签(Label),是标记程序位置的助记符,本质上还是地址ifx goto L //if... goto 是条件跳转ifx rop y goto L // rop 是关系运算符(Relational Operator),运算结果一般为布尔值1.2.找程序的Leader集合L,进而划分Basic Block
程序入口
跳转指令的目标指令
跳转指令的下一条指令
(一个Leader到下一个Leader之前就是一个BB)
1.3.连接Basic Block
程序控制流的产生来源于两个地方:
天然的顺序执行
这是计算系统天然存在的一种控制流
跳转指令
这是人为设计添加的一种控制流
示例
二、过程间数据流分析
1.CG 方法调用图
1.1.Java中的方法调用类型
Static Call:调用静态方法 --> 编译时明确
Special Call:调用构造方法、私有方法、基类实例方法 --> 编译时明确
Virtual Call:调用其他实例方法 -->运行时明确(多态,最常见)
所以在构建方法调用图时,最关键的是要处理好Virtual Call的情况
1.2.CG的构建方法
类层级结构分析(Class Hierarchy Analysis,CHA)
快速类型分析(Rapid Type Analysis,RTA)
变量类型分析(Variable Type Analysis,VTA)
指针分析(Pointer Analysis,k-CFA)
上面的四种方法自上而下精度(Precision)越来越高,但是效率(Efficiency)也越来越低。
本文只关注CHA的方式:
CHA
在方法调用点处,只关注caller的声明类型T及callee的方法签名sig,会把T及其子类中所有与sig匹配的方法都视为可能的目标方法,示例:
classA{voidfoo(){ ... }}classBextendsA{ }classCextendsB{voidfoo(){ ... }}classDextendsB{voidfoo(){ ... }}类层级结构如下:
现有以下代码片段:
voidresolve(){C c = ...;c.foo();A a = ...;a.foo();B b =newB();b.foo();}CHA算法会对于每一个接收变量的声明类型本身及其子类关于调用点处的函数签名进行方法派发的操作,将所有找到的目标方法加入结果之中。因此,结果如下:
Resolve(c.foo()) = {C.foo()}
Resolve(a.foo()) = {A.foo(), C.foo(), D.foo()}
Resolve(b.foo()) = {A.foo(), C.foo(), D.foo()}
我们需要注意一下的是第三个调用点,A.foo()也在其结果之内,因为对于B类本身的方法派发得到的结果是A.foo()
并且,CHA的Resolve算法只关心声明类型,因此new B()其实并没有在算法中发挥作用,从而我们Resolve(b.foo())产生了两个虚假(Spurious)的目标调用C.foo()和D.foo()
CG构建示例:
classA{staticvoidmain(){A.foo();}staticvoidfoo(){A a =newA();a.bar();}voidbar(){C c =newC();c.bar();}}classBextendsA{voidbar(){ }}classCextendsA{voidbar(){if(...) {A.foo();}}voidm(){ }}CHA最终构建的CG如下:
在上述例子当中需要注意的是,虽然A a = new A(),但是解析a.bar()的目标方法时候,依旧会对A以及A的所有子类作Dispatch,故而会有3条从a.bar()出发的边。
最后我们会发现存在一个不可达的方法(Unreachable Method)C.m(),那么这个方法中的代码就是死代码(Dead Code,即在任何情况下控制流都不能到达的代码)。
CHA的应用:IDE中的目标方法提示
2.ICFG 过程间控制流图
2.1.ICFG的构建
ICFG要在CFG基础上添加call Edges(调用边)、return Edges(返回边)
ICFG = CFGs + call & return edges ,连接调用边和返回边的信息可以从调用图中获得。因此,过程间控制流图的精度取决于调用图的精度。
示例:
staticvoidmain(){inta, b, c;a =6;b = addOne(a);c = b -3;b = ten();c = a * b;}staticintaddOne(){inty = x +1;returny;}staticintten(){return10;}构建的ICFG如下:
从上图可以看出,在构建ICFG时,仍然保留了Call-to-return edges(调用点到返回点的边),虽然实际程序运行过程不会走这条边,但是这条边可以传递callee方法不需要的数据,这样就避免了在目标方法中始终维护其不需要的数据,可以提高效率。
提效工具推荐
Beyond Compare(https://beyond-compare.en.softonic.com/download)
该工具提供了丰富的文本/文件夹对比功能,并且还有合并比较等很多骚操作,免费下载使用。
功能有这么多~
用起来没什么难度,这里就不过多介绍啦,想详细了解的童鞋自行下载即可~