函数调用图(Call Graph),以下简称调用图,可以展示计算机程序中函数之间的关系。每一个节点是一个函数,每一个边(f, g)表示函数f调用函数g。调用图的示例图如下:
函数调用图可以由动态程序分析产生(动态函数调用图),也可以由静态程序分析产生(静态函数调用图)。动态函数调用图是程序执行过程的记录,可能是性能分析工具所输出的。动态函数调用图可以准确的描述这次程序执行时,各函数之间的关系。但会遗漏这次没有执行到的代码。静态函数调用图则是设法表示所有可能执行情形下,所有函数之间的关系。准确的静态函数调用图是不可判定问题,因此函数调用图上有所有函数之间的调用关系,有可能其中有一些调用是永远不会执行到的。
函数调用图可以解决许多问题,特别是在软件开发的过程中。例如理解代码结构、识别依赖关系、检测循环调用、代码重构、分析代码复杂性等。
调用图在代码安全检测方面也可以发挥重要作用,例如:
漏洞分析:通过调用图,可以分析代码中的函数调用关系,帮助发现潜在的漏洞点,比如未经验证的输入、不安全的数据传输等。
安全策略分析:通过调用图,可以了解代码中的安全策略实现情况,比如权限控制、加密算法的使用等,从而评估代码的安全性并提出改进建议。
恶意代码检测:调用图可以用于识别潜在的恶意代码,比如恶意程序可能会调用系统敏感函数或进行不当的文件访问操作,通过调用图可以更容易地发现这些恶意行为。
代码修改分析:通过调用图可以分析修改的代码对于其它部分带来的影响。
基于Android的一些特性,下面介绍调用图可以帮助检测的一些问题。
浏览器或者WebView中可以通过JsBridge接口向网页暴露一些内部方法。假如这些内部方法存在敏感操作,并且被攻击者进行恶意使用,将产生安全问题。基于调用图的检测技术,可以获取包含特定注解的JsBridge函数列表,并针对这些函数建立自上而下的调用图,并查找其中是否存在危险函数的调用。
构建的JsBridge接口向网页暴露风险方法的调用示例如下:
[0]#XXX:streamDownloadApp(JS函数)
[1]# YYY:openAdDeepLink
[2]# ZZZ:onInterceptResult
……
[10]# XXX:startDownload
[11]# WWW:startDownload(危险方法)
通过该技术的应用,可以首先排查出全部向网页暴露风险方法的JsBridge接口,并进行逐个分析,可对于风险接口进行修改处理,并将正常接口加入白名单。然后,定期对代码进行扫描比对,对于新增的暴露风险方法的JsBridge接口进行管控。
Android服务、广播接收器、ContentProvider等组件,如果将它们设置为可导出且未进行权限控制,并且在其内部函数没有对调用方进行校验,那么这些组件就存在对外暴露的风险。如果这些组件中包含敏感操作,那么任意第三方应用都可以调用这些敏感函数。
下图为一个具体案例:
该案例为某个模块的Service组件可导出且未做权限控制,在binder中有可以修改通知提示音的方法。导致任意三方APP可以进行修改通知提示音的敏感操作。
对于这类问题,可以构建暴露组件实现方法的函数调用图,包含全部的子层调用函数。然后遍历函数调用图,如果调用了敏感的系统函数,且之前不存在校验调用者身份的方法,则报出风险。
对于APP中的WebView,通常应该只允许加载特定域名的网页,如果没有进行域名校验,则有可能导致被加载一个恶意的URL,从而造成XSS攻击或者敏感信息泄露等风险。
对于这类问题的检查思路与方法:
扫描代码中的WebView组件的使用
构建WebView组件各个方法的函数调用图
判断loadUrl()之前,或者shouldOverrideUrlLoading()函数中没有调用域名合法校验的函数,则报出风险。
使用调用图可以帮助检索项目中无法调用到的死代码(Dead Code,即在任何情况下都不能到达的代码)。随着软件功能的复杂性不断增加,加上大型项目可能参与人员众多,导致在持续开发迭代的过程中,一些历史代码不会再被调用到,从而形成了死代码。这些代码如果不及时清理,将使得软件的体积不断增长。如下图中的C.m()方法。
使用函数调用图进行死代码检索和处理的过程如下:
① 生成函数调用图:首先,通过静态代码分析工具或自定义脚本来分析项目的源代码,提取出函数之间的调用关系,然后构建函数调用图。在函数调用图中,每个函数都是图中的一个节点,函数之间的调用关系则是图中的边。
② 标记无法调用到的函数:生成调用图后,就可以通过遍历图的节点来找出无法被其他函数调用到的函数。这些函数节点表示了潜在的死代码,因为它们不会被其他代码所使用。
③ 标记死代码:将这些无法调用到的函数标记为死代码。这些代码可能是项目中的遗留代码、无效代码或者错误代码,需要进一步的审查和处理。
④ 清理死代码:可以根据项目的实际情况来决定是否删除、注释掉或者进行其他处理。
对于大型Android项目,模块内部的调用和相互依赖的情况会比较复杂。很多开发人员修改一块老代码时,不是很清楚它是否会对其他模块产生影响。这时候许多人的做法是单纯测一下自己开发的功能,没问题就行了。最终可能导致对于单个功能的上线或者BUG修复,往往造成与之关联的功能出现问题。
通过调用图技术,可以给出修改的函数的上下游调用方的信息,或者追溯到用户可以控制的输入内容。品质测试或者安全测试人员可以针对这些有变化的内容进行针对性的测试,提升测试效率和测试用例的覆盖度。
通过函数改动追溯到Activity的示意图如下:
现有一些工具具备调用图的生成能力,主要定位于开发过程中的辅助使用。例如:
① IntelliJ IDEA提供了显示调用指定Java方法向上的完整调用链的功能,可以通过“Navigate -> Call Hierarchy”菜单使用;Eclipse等其它开发工具也提供了相似的功能。如下图所示:
② 使用Doxygen+GraphViz生成调用图
生成的调用图如下图所示:
此外,像Understand工具、Call Graph插件等都可以生成调用图。
但以上工具要么需要针对每个方法进行手工处理,或者不支持对方法进行过滤或者其他扩展功能。因此,为了达到使用调用图进行代码安全检测的目的,下面介绍一下具体的实践方法。
获取调用图的关键就是代码中函数的调用关系,假如直接从java源文件开始解析,难度会显著提高。我们可以借助编译器对于代码的理解能力来进行辅助。因此,我们需要先将源代码项目进行编译,生成编译的中间文件.class,然后对中间文件.class和.jar的内容进行字节码分析。
Apache BCEL(Byte Code Engineering Library)是一个用于操作Java字节码的开源Java类库,它被广泛应用于Java字节码的动态生成、修改和分析领域,比如在字节码增强、AOP(面向切面编程)、反编译、代码混淆等方面都有应用。它允许开发人员通过程序化的方式来分析、修改和创建Java字节码。BCEL库提供了丰富的API,使得开发人员可以轻松地读取、修改和生成Java字节码,这为动态生成和修改Java类文件提供了便利。
对于Java字节码分析,我们主要关注下面几个方法调用的指令:
invokevirtual、invokeinterface、invokespecial、invokestatic、invokedynamic
invokevirtual指令:用于调用对象的实例方法,根据对象的实际类型进行分派(虚方法分派),支持多态。这也是Java语言中最常见的方法分派方式。
invokeinterface指令:用于调用接口方法,它会在运行时搜索由特定对象所实现的这个接口方法,并找出适合的方法进行调用。
invokespecial指令:用于调用一些需要特殊处理的实例方法,包括实例初始化方法(构造器)、私有方法和父类方法。这些方法都是静态类型绑定的,不会在调用时进行动态派发。
invokestatic指令:用于调用命名类中的类方法(static方法)。这是静态绑定的。
invokedynamic指令:调用动态绑定的方法,这个是JDK 1.7后新加入的指令。用于在运行时动态解析出调用点限定符所引用的方法,并执行该方法。前面4条调用指令的分派逻辑都固化在java虚拟机内部,而invokedynamic指令的分派逻辑是由用户所设定的引导方法决定的。
通过对这些方法调用的指令内容进行解析,就可以得到单个函数调用其它函数的关系,基于这个基本的调用关系,就可以进一步生成调用图。
通过3.1中的步骤,我们可以得到单个函数调用其它函数的数据,如下图所示:
为了便于后续的查询和关联,需要把每个孤立的单个函数调用其它函数的数据记录到数据库中。为了便于关联,每个函数需要具有唯一的ID。可以采用图数据库或者其它关系型数据库来存储单个函数之间的调用关系。
在本步骤中,需要把上一步离散的单个函数调用关系根据需要串成完整的调用图,如下图所示:
在这个过程中,可以使用广度优先算法或者深度优先算法来生成调用图。
对于广度优先算法,首先需要明确起始的函数A,然后通过查询获取函数A调用所有其它子层函数的数据(函数B、函数C、函数D),最后再逐个遍历子层函数调用的下一层函数(函数E、函数F)。即先生成A->B/C/D,再生成B->E/F,再生成C->F。
对于深度优先算法,首先需要明确起始的函数A,然后通过查询获取函数A调用的单个子层函数(函数B),然后继续查询子层函数调用的下一层的单个函数(函数E),直到遍历完所有的数据。即先生成A->B->E,再生成A->B->F,再生成A->C->F,再生成A->D。
对于生成的调用图,需要有格式进行记录。假如函数对应的调用关系如下图:
则对于指定方法向下完整调用图可以记录如下:
[0]#SrcClass.srcfunc()
[1]# [SrcClass:15] ClassA1.funcA1()
[2]# [ClassA1:27] ClassA2a.funcA2a()
[2]# [ClassA1:59] ClassA2b.funcA2b()
[3]# [ClassA2b:39] ClassA3.funcA3()
[1]# [SrcClass:17] ClassB1.funcB1()
[1]# [SrcClass:23] ClassC1.funcC1()
[2]# [ClassC1:75] ClassC2.funcC2()
由于实际的大型项目函数调用会非常复杂,因此采用文本的形式可以直观的反应多层的函数调用情况。
除了生成指定方法向下完整调用图之外,还可以根据需要生成指定方法向上的调用图,原理类似,只是把调用关系交换一下。
根据3.3节生成完整调用图之后,就可以根据实际需要对调用图进行分析,进行代码安全检测。
下面就“2.1通过 JsBridge接口向网页暴露的风险方法检测”的案例讲下如何进行分析。主要步骤如下:
① 排查出全部向网页暴露风险方法的JsBridge接口。可以在源代码中批量搜索@ JavascriptInterface注解,或者在字节码中查找该注解的函数。
② 对于第1步中筛选出的各个函数,生成指定方法向下的完整调用图。
③ 对各个完整调用图进行查找操作,查询是否有调用到危险函数。
④ 如果查找到危险函数的调用,则输出从JsBridge接口到危险函数的调用栈明细信息。
⑤ 支持白名单的功能,对于调用图中存在危险解除特征、白名单豁免检测特征等结果进行排除。
问题1:通过编译生成的中间文件进行调用图构建,可能存在遗漏的问题
本文中的方法是提取编译生成所有的.class和.jar的内容,对于未获取到的第三方SDK有可能存在遗漏。同时,对于重名的.class文件需要妥善处理,因为编译可能同时生成了Debug版和Release版的内容。
问题2:由于Java语言的灵活性,可能导致部分函数调用链的缺失,主要有如下场景需要重点考虑
① 接口与实现类方法
假如存在接口Interface1,及其实现类Impl1,若在某个类Class1中引入了接口Interface1,实际为实现类Impl1的实例,在其方法Class1.func1()中调用了Interface1.fi()方法;
② Runnable实现类线程调用
假如f1()方法中使用内部匿名类形式的Runnable实现类在线程中执行操作,在线程中执行了f2()方法,如下所示:
private void f1() {
new Thread(new Runnable() {
@Override
public void run() {
f2();
}
}).start();
}
③ Callable实现类线程调用
与Runnable实现类线程调用情况类似。
④ Thread子类线程调用
与Runnable实现类线程调用情况类似。
⑤ lambda表达式(含线程调用等)
假如f1()方法中使用lambda表达式的形式在线程中执行操作,在线程中执行了f2()方法,如下所示:
private void f1() {
new Thread(() -> f2()).start();
}
⑥ Stream调用
在使用Stream时,通过xxx::func方式调用方法,需要重点考虑。如以下示例中,当前方法调用当前类的map2()、filter2(),及TestDto1类的getStr()方法的调用。
list.stream().map(this::map2).filter(this::filter2).collect(Collectors.toList());
list.stream().map(TestDto1::getStr).collect(Collectors.toList());
⑦ 父类调用子类的实现方法
假如存在抽象父类Abstract1,及其非抽象子类ChildImpl1,若在某个类Class1中引入了抽象父类Abstract1,实际为子类ChildImpl1的实例,在其方法Class1.func1()中调用了Abstract1.fa()方法;
⑧ 子类调用父类的实现方法
假如存在抽象父类Abstract1,及其非抽象子类ChildImpl1,若在ChildImpl1.fc1()方法中调用了父类Abstract1实现的方法fi();
问题3:函数循环调用的问题
静态函数调用图是对函数调用进行静态分析,当函数中存在分支时,可能部分函数在一定情况下调用不到。而根据静态分析生成调用图时,则有可能存在循环调用的情况。如下图所示:
函数G可能再次调用函数B,生成调用图时则可能造成了循环。因此需要对这种循环调用的情况进行识别,以免生成调用图失败。
此外,对于大型项目可能存在更深层次的循环调用,因此需要控制整个调用图最大的遍历深度。否则可能造成生成调用图耗时过长或者占用空间过大不利于进一步分析。
问题4:生成的调用图可能包含很多不关注的类和方法
当生成指定方法向下的完整调用链是为了人工分析代码结构时,若包含了所有的方法调用链,则会有很多不重要的代码产生干扰,例如数据序列化/反序列化操作(JSON等格式)、日期操作、注解/枚举/常量/异常/日期相关类操作、Java对象默认方法调用、日志打印等。
因此,在生成调用图时,需要排除不关注的类和方法。下面是一些常见的排除项:
java.lang
java.util
org.json
android.text.TextUtils
com.alibaba.fastjson
com.google.gson
okio.Buffer
当检测到调用的类以上述字符串开头时,则不再进一步向下生成进一步的调用。
本文围绕函数调用图的构建,详细分析了调用图可以解决的问题。然后具体阐述了调用图的构建方法和在代码安全检测中的应用。通过调用图分析技术,可以发现基于语法树进行代码安全分析中不能发现的问题,支持更加复杂场景的检测。
[1] 《函数调用图》https://en.wikipedia.org/wiki/Call_graph
[2] 《Doxygen终于可以正确生成函数调用图了》https://whatacold.io/zh-cn/blog/2021-02-16-doxygen-cpp-correct-callgraphs/
[3] 《Windows平台使用Doxygen+GraphViz生成函数调用关系图》https://mxy.cool/2019032530847/
[4] 《过程间分析》https://static-analysis.cuijiacai.com/05-inter/#_5-2-%E8%B0%83%E7%94%A8%E5%9B%BE%E7%9A%84%E6%9E%84%E5%BB%BA
[5] 《方法调用指令与方法返回指令》https://segmentfault.com/a/1190000039908525
[6] 《java-all-call-graph项目》https://github.com/Adrninistrator/java-all-call-graph
[7] 《java-callgraph2项目》https://github.com/Adrninistrator/java-callgraph2
[8] 《代码影响范围工具探索》https://juejin.cn/post/7190188739597959224
[9] 《Source code hierarchy》https://www.jetbrains.com/help/idea/viewing-structure-and-hierarchy-of-the-source-code.html