软件分析

01-Introduction

为什么需要静态分析

• 程序可靠性：例如空指针引用，内存泄露
• 程序安全性：私有信息泄露，注入攻击等等
• 编译优化：Dead code elimination, code motion
• 程序理解：IDE中哪些方法被调用，调用了哪些方法，类型检测

Sound

• 多报，误报，包含Truth

Complete

• 少报，漏报，一定是Truth

useful static analysis

• Compromise soundness (false negatives)
• Compromise completeness (false positives)

大部分静态分析追求sound，不完全准确的静态分析

Soundness的必要性

Soundness is critical to a collection of important (static-analysis) applications such as compiler optimization and program verification

静态分析例子

采用2的结果

静态分析确保soundness，在分析的精度和速度上做一个有效的平衡

静态分析：Abstraction + Over-approximation

Abstraction

• 

Over-approximation

Transfer Function

• In static analysis, transfer functions define how to evaluate different program statements on abstract values
• Transfer functions are defined according to “analysis problem” and the “semantics” of different program statements
• 
• 
  • 静态分析可以得出除零错误和负数索引错误，但静态分析也会产生误报（false positive）

Control Flows

• 

• 在实践中不可能列举出所有的路径，流合并在静态分析中比较被认为是理所当然的

Summary

思考：

• What are the differences between static analysis and (dynamic) testing?
• Understand soundness, completeness, false negatives, and false positives.
• Why soundness is usually required by static analysis?
• How to understand abstraction and over-approximation?

02-Intermediate Representation

Compilers and Static Analyzers

• Lexical Analysis 词法分析，分析合法生成Tokens给下一步继续分析
• Syntax Analysis 语法分析器，转换为抽象语法树
• Semantic Analysis 语义分析，主要是类型检查，生成Decorated AST
• 转换器转化为一种中间表示形式，然后继续生成Machine Code，编译优化是一种静态分析分析技术

AST vs. IR

AST	IR
high-level and closed to grammar structure	low-level and closed to machine code
usually language dependent	usually language independent
suitable for fast type checking	compact and uniform
lack of control flow information	contains control flow information
	usually considered as the basis for static analysis

IR具有语言无关性，可以将多种语言翻译为一种统一的中间格式

IR: Three-Address Code (3AC)

3-Address Code

• 一个指令右侧最多只有一个运算符，例如$t2=a+b+3$不是，$t_1=a+b$和$t_2=t_1+3$是

Why called 3-address?

Each 3AC contains most at 3 addresses

Address can be one of the following:

• 名字: a, b
• 常量: 3
• 编译器生成的变量: t1, t2

Some Common 3AC Forms

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

x, y, z: addresses

bop: binary arithmetic or logical operation

uop: unary operation (minus, negation, casting)

L: a label to represent a program location

rop: relational operator (>, <, ==, >=, <=, etc.)

goto L: unconditional jump if … goto L: conditional jump

3AC in Real Static Analyzer

Soot’s IR is Jimple: typed 3-address code

do-while

method

• invokespecial: call constructor, call superclass methods, call private methods
• invokevirtual: instance methods call (virtual dispatch)
• invokeinterface: cannot optimization, checking interface implementation

• invokestatic: call static methods

  method signature:

• class name: return type method name(parameter1 type, …)

main

Class

静态属性在clinit中初始化

Static Single Assignment (SSA)

SSA中所有赋值都针对具有不同名称的变量名，每个变量都有一个新的定义，每个变量只有一个定义，新名称传播到后续使用

多重的地方出现merge会引入phi-function

• A special merge operator, $\phi$(called phi-function), is introduced to select the values at merge nodes

• $\phi(x_0, x_1)$has the value x0 if the control flow passes through the true part of the conditional and the value x1 otherwise

SSA好处：

• 流信息被间接的合并到唯一的变量名中
  • 可能有助于提供一些更简单的分析，例如，流量不敏感分析通过SSA获得流量敏感分析的部分精度
• 定义和使用更加清晰
  • 要看使用的变量可以直接找定义的地方
  • 一些优化算法更加便利

SSA的坏处：

• 会引入太多变量和phi-function
• May introduce inefficiency problem when translating to machine code (due to copy operations)

Basic Blocks (BB)

BB是最大的一串连续three-address instructions满足以下特征：

• 只能从开始处（block的第一条指令）进入
• 出口是最后一条指令

• 一个jump的目标只能成为block的入口，即第一条语句
• 指令中有jump只能成为block的出口，即最后一条语句

一个栗子：

• 先找到第一条指令（1）是leader
• 其次jump的target是leader，（3）（7）（12）
• 跳转指令的下一条是leader，（5）（11）（12）
• 然后补充leader间的指令

Control Flow Graphs (CFG)

• Usually refer to building Control Flow Graph (CFG)

• CFG serves as the basic structure for static analysis

• The node in CFG can be an individual 3-address instruction, or (usually) a Basic Block (BB)

在A和B之间添加边

• 有有条件或无条件的跳转从A的结束到B的开始
• 在正常的指令执行顺序中B紧接着A并且A的最后一条指令不是无条件的跳转

（有条件的jump有两个出口)

Summary

• The relation between compilers and static analyzers

• Understand 3AC and its common forms

• How to build basic blocks on top of IR
• How to construct control flow graphs on top of BBs?

03- Data Flow Analysis - Applications I

Overview of Data Flow Analysis

Preliminaries of Data Flow Analysis

输入输出状态

• Each execution of an IR statement transforms an input state to a new output state
• The input (output) state is associated with the program point before (after) the statement

In each data-flow analysis application, we associate with every program point a data-flow value that represents an abstraction of the set of all possible program states that can be observed for that point.

Data-flow analysis is to find a solution to a set of safe-approximationdirected constraints on the IN[s]’s and OUT[s]’s, for all statements s.

• constraints based on semantics of statements (transfer functions)
• constraints based on the flows of control

正向分析

反向分析

Reaching Definitions Analysis

Reaching Definitions

A definition d at program point p reaches a point q if there is a path from p to q such that d is not “killed” along that path

• A definition of a variable v is a statement that assigns a value to v

• Translated as: definition of variable v at program point p reaches point q if there is a path from p to q such that no new definition of v appears on that path

  

• Reaching definitions can be used to detect possible undefined variables. e.g., introduce a dummy definition for each variable v at the entry of CFG, and if the dummy definition of v reaches a point p where v is used, then v may be used before definition (as undefined reaches v)

Understanding Reaching Definitions

Data Flow Values/Facts

• The definitions of all the variables in a program

• Can be represented by bit vectors

  

• Transfer Function

  

  

• Control Flow

  

Reaching Definitions Analysis算法

A definition d at program point p reaches a point q if there is a path from p to q such that d is not “killed” along that path

为什么算法可以停止

Live Variables Analysis

活跃变量分析告诉我们变量v的值在程序的p点之后是否会被使用到

Live variables analysis tells whether the value of variable v at program point p could be used along some path in CFG starting at p. If so, v is live at p; otherwise, v is dead at p.

Available Expressions Analysis

An expression x op y is available at program point p if (1) all paths from the entry to p must pass through the evaluation of x op y, and (2) after the last evaluation of x op y, there is no redefinition of x or y

总结

06 Data Flow Analysis - Foundations 2

Constant Propagation

简单的来说可以看作将常量传播到使用了这个常量的地方去，可以用常量替换原来的变量

07 Interprocedural Analysis

Java中的方法调用

A signature：作为一个方法的标签

定义函数Dispatch(c, m)来计算程序运行时的方法的指派

Class Hierarchy Analysis* (CHA)

A a = ...

a.foo();

这样的a.foo()被称为一个call site

Resolve(cs)接收一个call site cs 作为参数，求解目标方法

优点：快

缺点：不准确

通常用于IDE中

Call Graph Construction

Interprocedural Data-Flow Analysis

• Node transfer
  • Call nodes: identity
  • Other nodes: same as intraprocedural constant propagation
• Edge transfer
  • Normal edges: identity
  • Call-to-return edges: kill the value of LHS variable of the call site, propagate values of other local variables
  • Call edges: pass argument values
  • Return edges: pass return values

总结

• How to build call graph via class hierarchy analysis
• Concept of interprocedural control-flow graph
• Concept of interprocedural data-flow analysis
• Interprocedural constant propagation

08 Pointer Analysis

Introduction

一个变量可以指向程序中的哪些对象

may-analysis

• Computes an over-approximation of the set of objects that a pointer can point to, i.e., we ask “a pointer may point to which objects?”

• 指针分析（pointer analysis）：指针指向哪个对象

• 别名分析（alias analysis）：程序中的指针是否会指向相同对象

别名分析的结果可以从指针分析推导出来

Key

Multiple factors affect the precision and efficiency of the system

Heap Abstraction

如何对堆内存进行建模

• 需要一个技术保证指针分析可以被终止

Allocation-Site Abstraction

用一个创建点的抽象对象来表示具体对象

（代码中有几个new就有几个抽象对象）

Context Sensitivity

如何对调用上下文进行建模

• 上下文敏感：区分不同上下文，分开分析不同上下文情况

• 上下文不敏感：merge所有上下文，分析一次

Flow Sensitivity

如何对程序的控制流进行建模

• 控制流敏感：尊重执行循序
• 控制流不敏感：忽略控制流顺序，看作一堆无序语句

对于Java来说，没有明显的研究表明不敏感劣与敏感，所以Java中主要采用不敏感

Analysis Scope

分析程序的哪些部分

• 全部指针
• 需求驱动：满足特定的应用

Concerned Statements

我们只关注 pointer-affecting statements

Java中的指针

• Local variable: x
• Static field: C.f
  • 类似于Local variable
• Instance field: x.f
• Array element: array[i]
  • 数组的建模完后类似于Instance field

Pointer-Affecting Statements

• New x = new T()
• Assign x = y
• Store x.f = y
• Load y = x.f
• Call r = x.k(a, …)
  • static call
  • special call
  • virtual call

Summary

• What is pointer analysis?
• Understand the key factors of pointer analysis
• Understand what we analyze in pointer analysis

09 Pointer Analysis Foundations (I)

Rules

• Variables: x, y ∈ V
• Fields: f, g ∈ F
• Objects: $ o_i, o_j$ ∈ O
• Instance fields: $o{i}.f, o{j}.g$ ∈ O × F
• Pointers: Pointer = V ⋃ (O × F)
• Points-to relations: pt = Pointer → 𝒫(O)

静态字段

数组索引

用$o_i[*]$表示一个指向数组中所有对象的指针

静态方法

Pointer analysis as solving a system of inclusion constrains for pointers

基本思想：

• 使用图连接相关联的指针
• 当pt(x)改变，传播改变的部分给x的后继

PFG

有向图表示对象在指针间的流动关系

• Nodes: Pointer = V ⋃ (O × F)

  A node n represents a variable or a field of an abstract object

• Edges: Pointer × Pointer

  An edge 𝑥 → 𝑦 means that the objects pointed by pointer 𝑥 may flow to (and also be pointed to by) pointer y

实现指针分析的两步

• 构建PFG
• 在实现的PFG上传播指针信息

两部分互相依赖的

在指针分析的过程中PFG在动态更新

Alogrithms

Worklist（WL）

• Worklist contains the points-to information to be processed
  • WL ⊆
• 每个worklist里面存的是一对，n是指针，pts是一个指向的集合，表示pts应该被传播到pt(n)

总结

• Understand pointer analysis rules

• Understand pointer flow graph

• Understand pointer analysis algorithms

10 Pointer Analysis Foundations (II)

Method Call

• Inter-procedural pointer analysis requires call graph

不同于CHA，我们通过指针分析来构建call graph，比CHA更加准确，更加准确的call graph对指针分析具有正反馈

在指针分析中构建call graph

• on-the-fly call graph construction

Rule:Call

• Dispatch($o_j$,k): resolves the virtual dispatch of k on $o_j$ to a target method (based on type of $o_j$)
• $m_{this}$: this variable of m
• $m_{pj}$: the j-th parameter of m
• $m_{ret}$: the variable that holds the return value of m

解析出x指向的类传给this

为什么从x到this不连一条边

会多传

• 也不能通过过滤的方式来将A中的this指向的new B和new C去除，因为指向是合理的，当x发生改变时会将改变传到this上，所以A中的this无法通过过滤的方式去除不精确的this，会指向多个。

Interprocedural Pointer Analysis

• AddReachable(m)

  

• ProcessCall(x,$o_i$)

  

总结

• Understand pointer analysis rule for method call
• Understand inter-procedural pointer analysis algorithm
• Understand on-the-fly call graph construction

11 Pointer Analysis - Context Sensitivity I

————提升指针分析精度最有效的技术

上下不敏感分析为什么不准

• 在动态执行中一个方法可能执行多次，在不同的上下文中方法的变量可能指向不同的对象，但是在上下文不敏感分析中这些对象都混在一起不加以区分，在传播中可能产生假的数据流

上下文敏感分析

• 区分不同上下文以提高精度

Cloning-Based Context Sensitivity

• 打上标记

Context-Sensitive Heap

• 对抽象的对象也需要加上上下文

  The most common choice is to inherit contexts from the method where the object is allocated

• 获得粒度更小的堆抽象

Rules

Rule:Call

如果有许多上下文，只会传给$c^t$这个上下文下的$m_{this}$，实参传给特定上下文的形参

总结

• Concept of context sensitivity (C.S.)
• Concept of context-sensitive heap (C.S. heap)
• Why C.S. and C.S. heap improve precision
• Context-sensitive pointer analysis rules

Pointer Analysis Context Sensitivity (II)

带有上下文的PFG，每个node带有上下文信息

Algorithm

AddReachable()

AddEdge()

Propagate()

ProcessCall()

变体

三种上下文敏感的具体技术

• Call-site sensitivity
• Object sensitivity
• Type sensitivity

Call-Site sensitivity

每个上下文由一串调用链组成，在每个调用点处，将调用点加入到调用者的上下文中作为被调用者的上下文

k-Limiting Context Abstraction

• 在递归调用中，可能会产生无穷的调用链
• 实际中可能会产生非常复杂的山下文

为了解决上面两个问题，我们可以限制上下文的长度小与等于k，称为k-Limiting Context Abstraction

对于方法的上下文和堆的上下文k值可能不一定

实际上是取调用者调用链的最后k-1个加上本次的调用点构成长度为k的调用链作为被调用者的上下文信息

Object sensitivity

每个上下文由一串抽象对象组成

At a method call, use the receiver object with its heap context as callee context

在每个调用点处，用调用者的上下文加上这一点处调用者的抽象对象对象

Type sensitivity

基于对象敏感技术，是对象敏感技术粗粒度的抽象，在相同的k下，效果不好于对象敏感技术

Intype($o_i$)表示$o_3$所在的类

call-site vs. object

有可能call-site更准确也有可能object更准确

理论上两者之间的精度是没有办法比较的，但对于java这样的oo语言来说，总的来说object效果更好

Call-Site vs. Object vs. Type Sensitivity

• In general
  • Precision: object > type > call-site
  • Efficiency: type > object > call-site

总结

• Algorithm for context-sensitive pointer analysis
• Common context sensitivity variants
• Differences and relationship among common context sensitivity variants

Static Analysis for Security

信息流问题的两个例子

• 注入错误
• 信息确实

Information Flow Security

访问控制

• 检查有没有相应的权限
• 但不知道信息被给出后是如何被访问的

信息流分析

• 跟踪信息流如何在程序中如何流动
• 考虑信息如何传播

A practical system needs both access and flow control to satisfy all security requirements.

信息流：如果变量x中的信息传递到了变量y中，就存在一个信息流x$\rightarrow$y

Connects information flow to security

• 将变量分为不同的安全等级
• 指定不同等级间的流动策略

Noninterference policy*

• 高密级的变量不能对低密级的信息有影响
• 不应该通过观察低密级的变量推断出高密级的信息

Confidentiality and Integrity

Confidentiality

• Prevent secret information from being leaked

Integrity

• Prevent untrusted information from corrupting (trusted) critical information
  防止被污染
• To ensure the correctness, completeness, and consistency of data

保密性从L写到H

完整性从H写到L

Explicit Flows and Covert Channels

显示流

隐式流：可能发生在控制流信息被秘密信息影响，可以反推出一些秘密信息

隐藏信道：信道利用一个机制，机制的本意不是传递信息，则被称为隐藏信道

显示流一般来说比隐式流承载着更多的信息

Taint Analysis

Sources of tainted data is called sources. In practice, tainted data usually come from the return values of some methods (regarded as sources)

Taint analysis tracks how tainted data flow through the program and observes if they can flow to locations of interest (called sinks). In practice, sinks are usually some sensitive methods

• Treats tainted data as (artificial) objects
• Treats sources as allocation sites (of tainted data)
• Leverages pointer analysis to propagate tainted data

总结

• Concept of information flow security
• Confidentiality and integrity
• Explicit flows and covert channels
• Use taint analysis to detect unwanted information flow

Lab:lemon:

死代码检测

从程序中去除死代码是一种常见的编译优化策略

死代码指的是程序中不可达的（unreachable）代码（即不会被执行的代码），或者是执行结果永远不会被其他计算过程用到的代码。去除死代码可以在不影响程序输出的前提下简化程序、提高效率。在本次作业中，我们只关注两种死代码：不可达代码（unreachable code）和无用赋值（dead assignment）

不可到达代码

控制流不可到达代码：不存在从程序入口到达某一段代码的控制路径，例如在返回语句return之后的代码是不可到达的

• 检测方法：从方法入口开始，遍历CFG并标记可达语句，当遍历结束时，那些没有被标记的语句就是控制流不可到达的

分支不可到达代码：对于一个 if 语句，如果它的条件值（通过常量传播得知）是一个常数，那么无论程序怎么执行，它两个分支中的其中一个分支都不会被走到。这样的分支被称为不可达分支，该分支下的代码也是不可到达的，被称为分支不可到达代码

对于一个switch语句，如果他的条件值是一个常数，那么不符合条件值的case分支就可能是不可到达的

无用赋值

一个局部变量在一条语句中被赋值，但再也没有被该语句后面的语句读取，这样的变量和语句分别被称为无用变量（dead variable，与活跃变量 live variable 相对）和无用赋值。无用赋值不会影响程序的输出，因而可以被去除。

• 检测方法：预先对被检测代码施用活跃变量分析，对于一个赋值语句，如果它等号左侧的变量是一个无用变量，那么我们可以把它标记为一个无用赋值

Tips

• 通过pascal.taie.analysis.graph.cfg.Edge中的getKind()得知边的种类
  • 四类：IF_TRUE、IF_FALSE、SWITCH_CASE、SWITCH_DEFAULT
• 如何找到后继节点：CFG.getOutEdgesof()
• 可以使用 ConstantPropagation.evaluate() 来计算 if 和 switch 语句的条件值

类层次结构分析与过程间常量传播

实现基于CHA的调用图构造器

实现过程间常量传播分析

过程间常量传播

在过程间数据流分析中，为了计算一个节点的 IN fact，我们需要先对该节点的前驱的 OUT fact 应用 edge transfer，然后把得到结果 meet 进该节点的 IN fact。

我们定义了 transferEdge(edge, fact) 函数来实现 edge transfer

即将计算In fact的转换函数调整为

$IN[B]= \underset{P\,a\,predecessor \, of \, B}{ \cup} transferEdge(P \rightarrow B, OUT[P])$

tansfer edge分为以下四类来处理：

• Normal edge
  恒等函数transferEdge(edge, fact) = fact

• Call-to-return dege

  对于方法调用x=m(...)，edge transfer函数会吧等号左侧变量和它的值从fact中kill掉，而对于等号左侧没有变量的调用x(...)，edge transfer与Normal edge一样是一个恒等函数

• Call edge

  edge transfer会将实参在调用点中的值传递给被调用函数的形参。即从调用点的out fact中获取实参的值，然后返回一个新的fact，这个fact把形参映射到它对应的实参的值

  举个例子，在图 1 里，transferEdge(2→4, {a=6}) = {x=6}。此时，edge transfer 函数的返回值应该仅包含被调用函数的形参的值（比如图 1 里，addOne() 的 x）。

• Return edge

  edge transfer函数将被调用方法的返回值传递给调用点等号左侧的变量。即从被调用方法的exit节点的OUT fact中获取返回值（可能有多个），然后返回一个将调用点等号左侧的变量映射到返回值的fact

  举个例子，在图1中，transferEdge(6→3, {x=6,y=7}) = {b=7}。此时，edge transfer 函数返回的结果应该仅包含调用点等号左侧变量的值（例如图1在第三条语句处的b）。如果该调用点等号左侧没有变量，那么 edge transfer 函数仅会返回一个空 fact

Tips

• 初始化过程中，过程间求解器需要初始化程序中国所有的IN/OUT fact，但仅需要对ICFG的entry方法的entry节点设置boundary fact，其它方法的entry节点和非entry节点的初始fact是一样的
• 实现transf的时候不要修改源节点的OUT
• 对于调用点，在之前的过程内常量传播中我们对于类似于x=A.foo()这样的语句作x=NAC处理，但在过程间常量传播中我们在这一点处先不将x添加到outfact中，而是在下一语句出根据调用返回值来判断x

非上下文敏感指针分析

上下文敏感的指针分析

Alias-Aware的过程间常量传播

别名：一个内存中的数据位置可以通过不同的符号名来访问，这些指向内存中的同一位置的不同符号互为别名

• 如果变量 x 和 y 指向相同的对象，那么 x.f 和 y.f 这两个字段访问构成了别名，因为它们实际上指向同一个字段
• 如果变量 a 和 b 指向同一个数组，并且 i 和 j 有相同的值，那么 a[i] 和 b[j] 这两个数组访问构成了别名，因为它们实际上指向同一个数组中的同一个位置。
• 在Java中静态字段不需要考虑别名的存在

在类层次分析与过程间常量传播的基础之上，当分析实例字段的 load 语句时（设该语句为 L），我们找到所有对这一实例字段（以及其别名）进行修改的 store 语句，并将这些语句要 store 的值 meet 之后赋给 L 等号左侧的变量

计算别名：对任意两个实例字段的访问（设为 x.f 和 y.f），如果它们的 base 变量的指针集（points-to set）有交集（即 x 和 y 的指针集有交集），那么我们认为对这两个实例字段的访问（x.f 和 y.f）互为别名

污点分析

修改后的source和sink规则

Sources是二元组 的集合，其中m表示一个被视作source的方法的签名，而u是该方法返回的污点对象的类型

$t^u_l$表示一个污点对象，其中u是这个对象的类型，l表示创建这个对象的调用点

污点传播

三种污点传播的方式

• Base-to-result: 如果 receiver object（由 base 指向）被污染了，那么该方法调用的返回值也会被污染。StringBuilder.toString() 是这样一类方法
• Arg-to-base: 如果某个特定的参数被污染了，那么 receiver object（由 base 指向）也会被污染。StringBuilder.append(String) 是这样一类方法
• Arg-to-result: 如果某个特定的参数被污染了，那么该方法调用的返回值也会被污染。String.concat(String) 是这样一类方法

为了处理污点传播，为污点分析定义了一种新的输入，叫做TaintTranfers，是又四元组<m,from,to,u>构成的集合

• m: 会引发污点传播的方法
• from: 污点会从from
• to: 传到to中
• u: 传播后污点的类型

三种分析规则