【课程笔记】南大软件分析课程2——IR

Tattoo

发布日期: 2020-07-08 13:04:54 浏览量: 87
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

最近在看“静态分析”技术相关的文章,看到这个系列的笔记和视频教程,感觉介绍得很好,通俗易懂,而且还比较详细,故转载分享,同时也备份保留下,方便自己今后阅读。(PS:建议大家一边看笔记,一边看视频,加深理解)
原作者:bsauce
原文链接:https://www.jianshu.com/p/acb73f72cf46

首先非常感谢南京大学李樾谭添老师的无私分享,之前学习程序分析是看的北大熊英飞老师的ppt,但是很多地方没看懂,正如李樾老师所说的那样,熊英飞老师的授课涵盖非常广,不听课只看ppt的话,理解起来还是很有难度的。但李樾老师的视频就讲解的非常易懂,示例都是精心挑选的,所以墙裂推荐。

推送门南大课件 南大视频课程 北大课件


目录

  1. 编译器和静态分析的关系
  2. AST vs IR
  3. IR:3-地址代码(3AC)
  4. 实际静态分析器的3AC—Soot(Java)
  5. SSA-静态单赋值
  6. 基本块(BB)
  7. 控制流图(CFG)

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

源码->(Scanner - 词法Lexical分析-Regular Expression)->(Parser- 语法Syntax分析-Context-Free Grammar), 生成AST ->(Type Checker - 语义Semantic分析 - Attribute Grammar),生成 Decorated AST -> Translator,生成IR,进行静态分析 -> Code Generator

2.AST vs IR

  • AST :高级,更接近于语法结构,依赖于语言种类,适用于快速类型检查,缺少控制流信息

  • IR:低级,更接近于机器码,不依赖语言种类,压缩且简洁,包含控制流信息。是静态分析的基础

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

  1. // 最多1个操作符
  2. a+b+3 -> t1 = a+b
  3. t2 = t1+3
  4. Address
  5. Name:ab
  6. Constant: 3
  7. 编译器的临时变量:t1t2

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

Soot-常用的Java静态分析框架

  1. // java IR(Jimple)基本知识
  2. invokespecialcall constructor, call superclass methods, call private methods
  3. invokevirtual: instance methods call (virtual dispatch)
  4. invokeinterface: cannot optimization, checking interface implementation
  5. invokestation:call static methods
  6. Java 7: invokedynamic -> Java static typing, dynamic language runs on JVM
  7. method signature: class name, return type, method name(parameter1 type, parameter2 type)

5.SSA-静态单赋值

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

优点:唯一的变量名可以间接体现程序流信息,简化分析过程;清楚的Define-Use信息。

缺点:引入很多变量和phi-function;转换为机器码时效率变低(引入很多拷贝操作)。

6.基本块(BB)

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

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

我的想法:对于下1条指令,若该指令不是入口,则可以加入;若该指令有多个出口,则停止加入,否则继续判断下一条指令。

7.控制流图(CFG)

控制流边:基本块A的结尾有跳转指令跳转到基本块B;原始指令序列中,B紧跟着A,且A的结尾不是无条件跳转。

添加Entry / Exit:没有块跳转到该块 / 没有跳转到其他块。

上传的附件

发送私信

人生最好的三个词:久别重逢,失而复得,虚惊一场

93
文章数
34
评论数
最近文章
eject