# 另一种静态分析框架——IFDS

## CFL-Reachability and IFDS

• Meet/Join
• Transfer function
• Bottom/Top

IFDS是一种分析框架，在这种框架下，分析的数据流是满足CFL-Reachability这一性质的。

1. 1.
Feasible and Realizable Paths
2. 2.
CFL-Reachability
3. 3.
Overview of IFDS
4. 4.
Supergraph and Flow Functions
5. 5.
Exploded Supergraph and Tabulation Algorithm
6. 6.
Understanding the Distributivity of IFDS

## Feasible and Realizable Paths

Example

The paths in which “returns” are matched with corresponding “calls”.
• Realizable paths may not be executable, but unrealizable paths must not be executable.
• 可以把executable/feasible path看作realizable path的真子集
• Our goal is to recognize realizable paths so that we could avoid polluting analysis results along unrealizable paths.
• 这个问题和括号匹配问题本质上是一样的。
• 如果你是计算机系大一的学生，或许会想到用stack来做括号匹配问题。
• 而如果你刚刚修过计算理论课程，你应该能够想起来使用上下文无关文法能够很好地识别一个匹配的括号串(Balanced-Parenthesis Problem)。

## CFL-Reachability

A path is considered to connect two nodes A and B, or B is reachable from A, only if the concatenation of the labels on the edges of the path is a word in a specified context-free language.

• 终结符(nonterminal)
• 非终结符(terminal)
• 空串符号
$\epsilon$
• （最左/最右）推导
• 正则文法/上下文无关文法和图灵机之间计算表达能力的差异

$(_1$
$)_1$
，而其他的边则是字符串中的e。

## Overview of IFDS

“Precise Interprocedural Dataflow Analysis via Graph Reachability”
--Thomas Reps, Susan Horwitz, and Mooly Sagiv, POPL’95

• Path Function
• Path function for path p, denoted as
$pf_p$
, is a composition of flow functions for all edges (sometimes nodes) on p
• 可以理解按照顺序，先后应用一条path上edge/node的transfer function:
• Meet-Over-All-Paths(MOP)
• For each node n, MOP n provides a “meet-over-all-paths” solution where Paths(start, n) denotes the set of paths in CFG from the start node to n.
• 即对所有的开始点start，都以bottom作为path function的输入，并在终点n处对所有的结果做meet操作。
• Meet-Over-All-Realizable-Paths(MRP)
• For each node n, MRP n provides a “meet-over-all-realizable-paths” solution where RPaths(start, n) denotes the set of realizable paths (the path’s word is in the language L(realizable)) from the start node to n.
• 在前者概念的基础上限制Meet的对象为Realizable-Path

## Supergraph and Flow Functions

### Design Flow Functions

For each node n ∈ N*, determine the set of variables that may be uninitialized before execution reaches n.

#### lambda expression

$\lambda$

• 函数以x作为输入参数
• 函数返回值为x+1
• 调用函数时传入的参数为3

#### Example of Flow Functions

$Ret_p$

image-20201231194247160

## Exploded Supergraph and Tabulation Algorithm

### Build Exploded Supergraph

Flow Function对应着二元关系。

1. 1.
输出和输入完全一致
2. 2.
无论输入为什么，输出都包含a
3. 3.
输出一定不包含a，且一定包含b，其他变量（这里是c）则保持不变
4. 4.
如果输入包含a，则输出一定包含b；否则一定不包含b

### Tabulation Algorithm

$O(ED^3)$

## Understanding the Distributivity of IFDS

$\forall(x,y). f(x\cdot y)=f(x)\cdot f(y)$
• 这样的要求使得我们无法用IFDS来做常量传播(constant propagation)和指针分析(pointer analysis)
• 换句话说，在IFDS中，我们可以表达逻辑或，但无法表达逻辑与
• 更广泛地说，如果我们需要考虑多个输入来决定输出，那么由于Distributivity性质没有被满足，无法用IFDS来解决

Note: If we want to obtain alias information in IFDS, say alias(x,y), to produce correct outputs, we need to consider multiple input data facts, x and y, which cannot be done in standard IFDS as flow functions handle input facts independently (one fact per time). Thus pointer analysis is non-distributive.

### Key Points

• Understand CFL-Reachability
• Understand the basic idea of IFDS
• 大概知道有几个阶段即可
• Understand what problems can be solved by IFDS