美文网首页软件测试自动化攻防漏洞挖掘
【课程笔记】南大软件分析课程5——过程间分析(课时7)

【课程笔记】南大软件分析课程5——过程间分析(课时7)

作者: bsauce | 来源:发表于2020-05-06 13:29 被阅读0次

    目录:

    1. Motivation
    2. 调用图构建
    3. 过程间控制流分析
    4. 过程间数据流分析

    重点:

    学习如何利用类层级分析来构建调用图;过程间控制流/数据流分析;过程间的常量传播。


    1.Motivation

    问题:过程内的分析未考虑函数调用,导致分析不精确。

    过程间分析:Inter-procedural Analysis,考虑函数调用,又称为全程序分析(Whole Program Analysis),需要构建调用图,加入Call edges和Return edges。


    2.调用图构建

    (1)调用图

    定义:本质是调用边的集合,从调用点(call-sites)到目标函数(target methods / callees)的边。

    示例

    5-2-1-call_graph.png

    应用:是所有过程间分析(跨函数分析)的基础,程序优化,程序理解,程序调试。

    (2)面向对象语言的调用图构造(Java)

    代表性算法:从上往下精度变高,速度变慢,重点分析第1、4个算法。

    • Class hierarchy analysis(CHA)
    • Rapid type analysis(RTA)
    • Variable type analysis(VTA)
    • Pointer analysis(k-CFA)

    Java调用分类

    Static call Special call Virtual call
    指令 invokestatic invokespecial invokeinterface、 invokevirtual
    Receiver objects(返回后赋值的目标对象) ×
    目标函数 Static函数 构造函数、 私有函数、父类的实例函数 其他实例函数
    目标函数个数 1 1 ≥1 (polymorphism多态性)
    何时确定 编译时 编译时 运行时

    Method Dispatch:最难的是Virtual call,其中关键步骤是Method Dispatch,就是找到最终调用的实际函数

    virtual call在程序运行时才能得到,基于2个要素得到:

    1. reciever object的具体类型:c

    2. 调用点的函数签名:m。(通过signature可以唯一确定一个函数)

      1. signature = 函数所在的类 + 函数名 + 描述符
      2. 描述符 = 返回类型 + 参数类型

      简记为C.foo(P, Q, R)


      5-2-2-virtual_call.png

    (3)Method Dispatch(virtual call)

    定义:用Dispatch(c, m)来模拟动态Method Dispatch过程,c表示reciever object,m表示函数签名。

    5-2-3-Method_Dispatch.png

    解释:若该类的非抽象方法(实际可执行的函数主体)中包含和m相同名字、传递/返回参数的m,则直接返回;否则到c的父类中找。

    示例

    5-2-4-Dispatch示例.png

    (4)Class Hirarchy Analysis (CHA) 类层级分析

    目的:根据每个virtual call 的 receiver varible 的声明类型来求解所有可能调用的目标函数。如 A a = ... ; a.foo(); 这个a就是receiver varible,声明类型就是A。假定a可以指向A以及A所有子类对象,CHA的过程就是从A和子类中去找目标函数。

    算法:Resolve(cs)——利用CHA算法找到调用点所有可能的调用目标。

    5-2-5-CHA算法.png

    算法示例

    5-2-6-CHA算法示例.png

    算法应用

    5-2-7-CHA应用.png

    错误:以上b.foo()的调用目标 C.foo()和D.foo()是错误的,因为已经指定了是B类型,所以b.foo()根本不会调用C、D的foo()。因为CHA只考虑声明类型,也就是B,导致准确度下降。多态性就是说,父类可以引用子类的对象,如B b=new C()

    优缺点:CHA优点是速度快,只考虑声明类型,忽略数据流和控制流;缺点是准确度低。

    总结:本类中有同名函数就在本类和子类找,没有就从父类找,接着找父类的子类中的同名函数(CHA分析)。

    (5)利用CHA构造调用图

    算法:遍历每个函数中的每个调用指令,调用CHA的Resolve()找到对应的目标函数和调用边,函数+调用边=调用图。

    5-2-8-调用图构造算法.png

    示例

    5-2-9-调用图算法示例.png

    3.过程间控制流分析

    定义:过程间控制流图ICFG = CFG + (Call edges + Return edges)。

    • Call edges:连接调用点和目标函数入口
    • Return edges:从return语句连到Return site(Call site后面一条语句)

    示例

    5-3-ICFG示例.png

    4.过程间数据流分析

    说明:对ICFG进行数据流分析,没有标准的一套算法。

    对比

    Intraprocedural Interprocecdural
    程序表示 CFG ICFG = CFGs + call & return edges
    转换规则 Node transfer Node transfer + edge transfer

    常量传播数据流分析

    • Node transfer:与过程内分析相同,对每个调用点,将等号左边部分去掉。
    • Call edge transfer:传参
    • Return edge transfer:传返回值

    常量传播示例

    5-4-ICFG常量传播示例.png

    说明:黄色背景边必须有,从b = addOne(a)c=b-3,a通过此边传递,b通过addOne()传递。若a也通过addOne()传递,会额外消耗系统资源。


    参考:

    软件分析笔记:3.过程分析(Interprocedural Analysis)

    相关文章

      网友评论

        本文标题:【课程笔记】南大软件分析课程5——过程间分析(课时7)

        本文链接:https://www.haomeiwen.com/subject/kwzightx.html