南大《软件分析》课程笔记——Intermediate Representation
阅读原文时间:2023年07月10日阅读:2

南大《软件分析》——Intermediate Representation

@(静态分析)

  1. 编译器和静态分析的关系

  2. AST vs IR

  3. IR:3-地址代码(3AC)

  4. 实际静态分析器的3AC—Soot(Java)

  5. SSA-静态单赋值

  6. 基本块(BB)

  7. 控制流图(CFG)

中间表示形式IR(通常是三地址码)之后进行静态分析,优化,检查。

IR是提供给静态分析程序的基础。

编译基本流程

  • 词法分析
  • 语法分析
  • 语义分析
  • 中间代码生成
  • 代码优化
  • 代码生成

AST

IR

更高级,接近语法结构

更底层,接近汇编

依赖语言

不依赖语言

适用于快速类型检查

压缩简洁

缺乏控制流信息

包含控制流信息

通常认为IR是静态分析的基础

三地址码(3-Address Code)

中间表示形式,右侧最多只有一个操作符

  • Address:

    • Name:a、b
    • Constant: 3
    • 编译器的临时变量:t1、t2

Soot

https://github.com/Sable/soot

https://github.com/Sable/soot/wiki/Tutorials

最常用的Java静态分析框架

invokespecial: call constructor, call superclass methods, call private methods
invokevitual: instance methods call(virual dispath)
invokeinterface: cannot optimization, checking interface implementation
invokestatic: call static methods

Java7: invokedynamic -> Java static typing , dynamic language runs on JVM #让动态语言在JVM上运行

method signature: class name : return type method name(parameter1 parameter2)

给每一个定义变量一个新的命名,传递到接下来的使用当中,每个变量有一个定义(赋值的目标变量)。

每一个变量都有自己的定义

merge的地方会使用Phi funciton

优点:

  • 程序流信息可以间接包含进独一无二的变量名。通过SSA,流不敏感分析方法可以获得部分流敏感分析方法所带来的精度。
  • Define- and-Use清晰明显

缺点:

  • 引入的变量和Phi function过多
  • 转换为机器码时效率变低(引入很多拷贝操作)

只有1个开头入口和1个结尾出口的最长连续的3-地址指令序列。

识别基本块的算法:首先确定入口指令,第一条指令是入口;任何跳转指令的目标地址是入口;任何跟在跳转指令之后的指令是入口。然后构造基本块,任何基本块包含1个入口指令和其接下来的指令。

基本块作为节点

添边规则:

  • A的结尾有跳转指令到B
  • 原始指令序列中,B紧跟着A,且A的结尾不是无条件跳转。

将原本的语句变为BB再变成CFG

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章