南京大学软件分析笔记

Introduction

sound&complete问题，sound代表“正确的我都说了”，complete代表“我说的都是正确的”。sound会造成高误报（False Positive），complete会造成高漏报（False Negative）。在实践中，偏向选择一个sound的结果，也就是宁可误报，也要把所有漏洞都报出来。

在确保soundness的前提下，尽可能靠近truth。达到精度和速度的平衡。

Intermediate Representation

compilers and static analyzers

从source code 到 machine code流程

	步骤	环节	工具	结果
1	Scanner	Lexical Analysis	Regular Expression	Tokens
2	Parser	Syntax Analysis	Context-Free Grammer	AST
3	Type Checker	Semantic Analysis	Attribute Grammer	Decorated AST
4	Translator	Static Analysis（e.g., code optimization）	/	IR
5	Code generator	/	/	MachineCode

context-free grammar: 上下文非敏感文法，对语言文法的表达能力很弱于上下文敏感语法，但对于编程语言来说已经够用了

context-sensitive grammer：上下文敏感文法，对语言文法的表达能力很强，适合人类语言的表达

IR之前叫前端，IR之后叫后端

AST vs 三地址码（Three Address Code）

	层级	语言相关	控制流	应用领域
AST	高级，与语法更近	相关	缺少控制流	做简单的类型检查
3AC	低级，与机器码更近	无关	包含控制流信息	压缩且通用

三地址码：命令右侧只能有一个操作符，比如T2=a+b+3;=>T1=a+b;T2=T1+3

常见3AC形式

x = y bop z
x = uop y
x = y
goto L
if x goto L
if x rop y goto L

x,y,z: address
bop: 二进制算数符或逻辑操作符
uop: 一元操作符（unary opeartion）(minus, negation, casting)
L: 表达程序位置的一个标签
rop: 比较操作符（>,<,==,>=,<=,etc.）
goto L: 无条件跳转unconditional jump
if...goto L: conditional jump

3AC real static analyzer: soot

jvm四种方法调用

invokespecial: call constructor, call superclass methods, call private methods
invokevirutal: instance methods call (virtual dispatch)
invokeinterface: cannot optimization, cheching interface implementation
invokestatic: call static methods

java 7: invokedynamic -> Java static typing, dynamic language runs on JVM

method signaturebao'han: classname, return type, method name(parameter1 type, parameter 2 type)

static single assignment (SSA)

Basic blocks

Control Flow Graph