南京大学软件分析复习笔记

个人应对软件分析2024年期末考试的复习笔记。

参考：

【课程笔记】南大软件分析课程—16课时完整版_南大软件分析课程10——基于datalog的程序分析-CSDN博客

南大软分课程笔记｜01 介绍

https://blog.csdn.net/zhang971105/article/details/109538402

https://blog.csdn.net/panhewu9919/article/details/106007155

软件分析概述

静态分析（Static Analysis）和动态测试（Dynamic Testing）的区别是什么？

静态测试是指测试不运行的部分：只是检查和审阅,如规范测试、软件模型测试、文档测试等。不用执行程序。

动态测试是通常意义上的测试，也就是运行和使用软件。需要构造测试实例、执行程序、分析程序的输出结果。

完全性（Soundness）、正确性（Completeness）、假积极（False Positives）和假消极（False Negatives）分别是什么含义？

• 完全性（Soundness）：真相一定包含在 S 给出的答案中；（范围更广，比较宽松，存在误报）
• 正确性（Completeness）：S 给出的答案一定包含在真相中；（范围更小，比较严格，可能漏报）
• 假积极（False Positives）：实际为 False，预测为 True。
• 假消极（False Negatives）：实际为 True，预测为 False。

一个完美的静态分析给出的答案应当既是对的，也是全的。

sound的结果：over-approximate，牺牲 soundness 会产生漏报 false negatives

complete的结果：under-approximate。牺牲 completeness 会产生误报 false positives

为什么静态分析通常需要尽可能保证完全性？

宁可有误报，也不漏掉一个正确结果。Soundness对编译器优化、程序验证等领域十分重要。

抽象与过近似

在程序中，变量很可能是不确定的（unknown）或非法、未定义（undefined）的。

因此abstract domain包含五类符号：+ − O ⊤ ⊥，其中 ⊤ 表示unknown，⊥ 表示undefined。

Over-approximation 部分的 control flows 则指的是，在实际场景中进行控制流相关的静态分析时，由于无法枚举所有路径，我们通常采用 flow merging（一种over-approximation的方式）来处理。

程序的中间表示

编译器（Compiler）和静态分析器（Static Analyzer）的关系是什么？

编译器会进行编译过程，通常包括词法分析、语法分析、语义分析等过程，最终生成机器码。

静态分析使用的是 Translator 生成的IR进行分析。

三地址码（3-Address Code, 3AC）是什么，它的常用形式有哪些？

三地址码的一个要求是，在一个指令的右边至多只有一个操作符。

例如，对于c = a + b + 3这样的语句，3AC 需要引入一个中间变量来将其变成两个指令：t1 = a + b和c = t1 + 3。

常见形式如下所示：

如何在 IR 的基础上 构建 BasicBlock

控制流分析 Control Flow Graph

控制流图（Control Flow Graph，CFG）是静态分析的基础结构，CFG的每个节点可以是一个3AC，也可以是一个基本块（Basic Block，BB）

BB 指的是一个连续、最长的3AC序列，该序列具有以下特性：

• 控制流只能从该序列的起始指令进入。
• 控制流只能从该序列的最后一条指令退出。

构建BasicBlock

1. 确定3AC序列中的leaders。leaders包括具有以下特性的指令：
   1. 3AC序列中的第一条指令。
   2. 所有有条件跳转或无条件跳转的所有目标指令。
   3. 所有有条件跳转或无条件跳转后面的一条指令。
2. 划分BB。BB包含leader指令及其后面紧邻的所有非leader指令。

简而言之：

BB开头：第一个3AC / goto的目标 /goto的下一个语句

BB结尾：goto语句 / goto的目标的上一个语句

在基块的基础上构建控制流图（Control Flow Graph, CFG）

根据上面的方法，我们就可以构建CFG。特性如下：

• CFG的节点均为BB。
• 从 块A 到 块B 之间有一个有向边，当且仅当”从A到B一个有条件或无条件跳转“，或“B是A后面的紧邻块且A最后一条指令不是无条件跳转”。
• 将原来3AC序列中的所有 “跳转到某指令标签处” 改为 “跳转到某基本块处” 。

数据流分析

may / must

may analysis：输出可能正确的信息（需做over-approximation优化，才能成为Safe-approximation安全的近似，可以有误报-completeness），大多数静态分析都是may analysis

must analysis：输出必须正确的信息（需做under-approximation优化，才能成为Safe-approximation安全的近似，可以有漏报-soundness）

可达性（Reaching Definitions）分析、活跃变量（Live Variables）分析和可用表达式（Avaliable Expressions）分析分别是什么含义？

不同的数据流分析 有 不同的数据抽象表达 和 不同的安全近似策略，如 不同的 转换规则 和 控制流处理。

可达性分析 Reaching Definitions Analysis

p处对变量v的定义在q可达：从p到q有一条路径，而且这条路径上没有其他对v的定义语句。

定义可达性分析可以用来检测源代码中的未定义变量。

活跃变量分析 Live Variable Analysis

变量v在p点是存活的，当且仅当 ：

1. 变量v在p点之后有被使用，
2. 从p点开始到被使用前，过程中不能出现变量v的重定义。

存活变量分析可用于寄存器分配，如果寄存器满了，就需要替换掉不会被用到的变量。

可用表达式分析 Available Expressions Analysis

x op y表达式在p点是可用的，当且仅当：

1. 首先，从entry到 p 的路径要经过x op y的表达式计算。
2. 其次，最后一次使用x op y之后，p点之前，没有重定义操作数x、y。

上述三种数据流分析（Data Flow Analysis）有哪些不同点？又有什么相似的地方？

如何理解数据流分析的迭代算法？数据流分析的迭代算法为什么最后能够终止？

数据流迭代算法，目的是通过迭代计算，最终得到一个稳定的不变的解。其本质是通过不断迭代，直到相邻两次迭代的k-元组值一样，算法结束。

从函数的角度理解迭代算法

$X_i=X_{i+1}=F(X_i)$，我们称满足 X=F(X) 的X是一个不动点（fixed point），并称上述迭代算法到达了一个不动点。

格和全格的定义是什么？

偏序：二元关系 自反性 对称性 传递性

上下界：

定义：给定偏序集(P, )，且有P的子集S⊆P：

• ∀x∈S, x⊑u, 其中u∈P，则u是子集S的上界 （注意，u并不一定属于S集）
• ∀x∈S, l⊑x, 其中l∈P，则l是S的下界

最小上界 lub，最大下界 glb

格的定义：给定一个偏序集 (P,≼) ，∀ a,b∈P，如果a⌊⌋b和a⌈⌉b均存在，那么(P,≼) 称为格。

偏序集中的任意两个元素构成的集合均存在最小上界和最大下界，那么该偏序集就是格。

格上的元素，都能找到其最大下界与最小上界

完全格：对于给定偏序集(P,≼)，它的任意子集S的最小上界 LUB 和最大下界 GLB 都存在，则(P,≼)才能被称为完全格。

如何理解不动点定理？

目标问题：迭代算法一定会停止（到达不动点）吗？

（1）单调性

定义：函数 f: L L，满足 ∀x,y∈L ，x⊑y ⇒ f(x) ⊑ f(y)，则为单调的。

（2）不动点定理

定义：给定一个完全格(L,⊑)，如果 f : L→L 是单调的，并且L有限。

那么我们能得到最小不动点，通过迭代：f(⊥) , f(f(⊥)) , … , f^k(⊥)直到找到最小的一个不动点。

同理我们能得到最大不动点，通过迭代：f(⊤) , f(f(⊤)) , … , f^k(⊤)直到找到最大的一个不动点。

CFG上每个节点的 OUT 都对应一个完全（有限）格L，整个 CFG 上所有节点的OUT就构成了一个乘积格

数据流分析可以视作在格上不断迭代应用transfer functions和meet/join操作。

join function 是单调的，我们的迭代算法一定能达到不动点（问题1），且一定能够到达最小（最大）不动点（问题2）

在最坏情况下，需要经过多少次迭代才能达到不动点：

假设每次迭代只在一个节点OUT对应的格上走了一步。

格的高度是h（格上从top到bottom的最长路径），CFG有 k 个节点，最多需要 i=h∗k 次迭代达到不动点。

使用格来总结可能性分析与必然性分析？

无论是 must 还是 may 分析，都是从unsafe result向safe result方向移动，从准确到不准确。

must 分析在这个乘积格上来看就是不断从⊤Unknown 往下走，越过truth，迭代算法到最大不动点

may分析就是不断从⊥Undef 往上走，越过truth，我们的迭代算法会达到最小不动点。

（1）may分析

以 Reaching Definitions分析为例：

1. 从 开始， 表示所有定义都不可达，是不安全的结果（因为这个分析的应用目的是为了查错，查看变量是否需要初始化。首先在Entry中给每个变量一个假定义，标记所有变量为都为未初始化状态，表示所有的假定义都无法到达，说明所有变量在中间都进行了赋值，那就不需要对任何变量进行初始化，这是不安全的，可能导致未初始化错误）。
2. 表示所有Entry中的假定义都可达，从查错角度来说，需要对每个变量都进行初始化，非常安全！但是这句话没有用，我都要初始化的话还做这个分析干嘛？
3. Truth：表明最准确的验证结果，假设{a,c}是truth，那么包括其以上的都是safe的，以下的都是unsafe，就是上图的阴影和非阴影。

1. 从 到 ，得到的最小不动点最准确，离Truth最近。上面还有多个不动点，越往上越不准。

（2）must分析

以available expressions分析为例：

1. 从开始，表示所有表达式可用。如果用在表达式计算优化中，那么有很多已经被重定义的表达式也被优化了（实际上不能被优化），那么该优化就是错误的，不安全！
2. 表示没有表达式可用，都不需要优化，很安全！但没有用。
3. 从到，就是从不安全到安全，存在一个Truth，代表准确的结果。
4. 从到，达到一个最大不动点，离truth最近的最优解。

迭代算法转化到lattice上，may/must分析分别初始化为最小值和最大值，最后求最小上界/最大下界。

迭代算法提供的解决方案与 MOP 相比而言精确度如何

MOP准确性：有些路径不会被执行，所以不准确；若路径包含循环，或者路径爆炸，所以实操性不高，只能作为理论的一种衡量方式。

Meet-Over-All-Paths（MOP）。

我们定义P为从Entry到某个语句Si的某一条路径（可能还会有别的路径），转换函数FP是从Entry到Si经过的所有的转换函数（fS1, … ,fSi−1）构成的复合转换函数，那么有：

MOP 在每条路径末尾计算数据流的值，然后将它们 join/meet起来，寻找它们的 lub / glb。

MOP可能是不精确的。有些路径不会被执行，所以不准确；若路径包含循环，或者路径爆炸，所以实操性不高

即 $IN = F(X.Y), MOP=F(X).F(Y)$

迭代算法的精确度小于等于MOP

当转换函数F 具有分配性（distributive）时，MOP=Ours，两者精确度才相同。

常量传播（Constant Propagation）分析

问题描述：在程序点p处的变量x，判断x是否一定指向常量值。

类别：must分析，因为要考虑经过p点所有路径上，x的值必须都一样，才算作一定指向常量。

表示：CFG每个节点的OUT是pair（x, v）的集合，表示变量x是否指向常数v。

数据流分析框架（D, L, F）

（1）D：forward更直观

（2）L：lattice

变量值域：所有实数。must分析，所以是UNDEF未定义（unsafe）， 是NAC非常量（safe）。

meet操作：must分析， 。在每个路径汇聚点PC，对流入的所有变量进行meet操作，但并非常见的交和并，所以不满足分配律。

• NAC v = NAC
• UNDEF v = v 未初始化的变量不是我们分析的目标。
• c v = ? （ c c = c c1 c2 =NAC ）

（3）F转换函数

OUT[s] = gen U (IN[s] - {(x, _})

输出 = BB中新被赋值的 U 输入 - BB中相关变量值已经不是f常量的部分。

对所有的赋值语句进行分析（不是赋值语句则不管，用val(x)表示x指向的值）：

（4）性质：不满足分配律

可以发现，MOP更准确。F(XY) F(X) F(Y)，但是是单调的。

Worklist算法

本质：对迭代算法进行优化，采用队列来存储需要处理的基本块，减少大量的冗余的计算。

过程间分析 Inter-procedural Analysis

过程间分析：Inter-procedural Analysis，考虑函数调用，又称为全程序分析（Whole Program Analysis），需要构建调用图，加入Call edges和Return edges。

如何通过类层级结构分析（Class Hierarchy Analysis, CHA）来构建调用图（Call Graph）

算法：遍历每个函数中的每个调用指令，调用CHA的Resolve()找到对应的目标函数和调用边，函数+调用边=调用图。

示例：

过程间控制流分析 ICFG

定义：过程间控制流图ICFG = CFG + (Call edges + Return edges)。

• Call edges：连接调用点和目标函数入口
• Return edges：从return语句连到Return site（Call site后面一条语句）

示例：

过程间数据流分析 IDFA

说明：对ICFG进行数据流分析，没有标准的一套算法。

对比：

常量传播数据流分析：

• Node transfer：与过程内分析相同，对每个调用点，将等号左边部分去掉。
• Call edge transfer：传参
• Return edge transfer：传返回值

常量传播示例：

说明：黄色背景边必须有，从b = addOne(a)到c=b-3，a通过此边传递，b通过addOne()传递。若a也通过addOne()传递，会额外消耗系统资源。

指针分析

什么是指针分析（Pointer Analysis）

目标：分析程序指针可以指向哪些内存。对于Java等面向对象语言，主要分析指针指向哪个对象。

说明：指针分析属于may analysis，分析的结果是某指针所有可能指向哪些对象，是个over-approximation集合。

示例：面向对象语言中的指针指向问题。对于setB()函数，this指向new A()，因为是调用者是a.setB()；setB()中的b是x传过来的，所以b指向new B()，A.b指向 new B()。

指针分析的关键因素 key factors

指标：精度（precision）& 效率（efficiency）。

影响因素：本课程，我们主要分析分配点的堆抽象技术、上下文敏感/不敏感、流不敏感、全程序分析。

Allocation-Site原理：将动态对象抽象成它们的创建点（Allocation-Site），来表示在该点创建的所有动态对象。Allocation-Site个数是有限的。

示例：循环创建了3个对象，我们用O2来抽象表示这3个动态对象。

（1）堆抽象（内存建模）

问题：程序动态执行时，堆对象个数理论上是无穷无尽的，但静态分析无法处理这个问题。所以为保证指针分析可以终止，我们采用堆抽象技术，将无穷的具体对象抽象成有限的抽象对象。也即，将有共性的对象抽象成1个静态对象，从而限制静态分析对象的个数。

我们只学习Allocation-Site技术，最常见也最常被使用。

Allocation-Site原理：将动态对象抽象成它们的创建点（Allocation-Site），来表示在该点创建的所有动态对象。Allocation-Site个数是有限的。

示例：循环创建了3个对象，我们用O2来抽象表示这3个动态对象。

（2）上下文敏感 Context Sensitivity

问题：考虑是否区分不同call-site对同一函数的调用。

• Context-sensitive：根据某函数调用上下文的不同，多次分析同一函数。

• Context-insensitive：每个函数只分析一次。

  

（3）流敏感 Flow Sensitivity

问题：考虑语句顺序（控制流）的影响 vs 把程序当做无序语句的集合。

方法：流敏感会在每个程序点都保存一份指针指向关系映射，而流不敏感则对整个程序保存一份指向关系映射。

说明：目前流敏感对Java提升不大，不过在C中很有效，本课程分析的是Java，所以重点讨论流不敏感技术。

指针分析示例：

（4）分析范围 Analysis Scope

问题：分析程序的哪一部分？

• Whole-program 全程序：分析全程序的指向关系。
• Demand-driven 需求驱动：只分析影响特定域的指针的指向关系。

指针分析的过程中具体都分析些什么

哪些语句会影响指针指向，那就只分析这些语句。

Java指针类型：

1. Local variable: x
2. Static field: C.f （有时称为全局变量）——不分析
3. Instance field: x.f （对象的field）
4. Array element: array[i] ——不分析，因为静态分析无法确定下标，所以将array中所有成员映射到一个field中，等价于Instance field，所以不重复分析。

影响指针指向的语句：

1. New: x = new T()
2. Assign：x = y
3. Store： x.f = y
4. Load： y = x.f
5. Call： r = x.k(a,…)
   • Static call： C.foo()
   • Special call： super.foo() / x.() / this.privateFoo()
   • Virtual call：x.foo()

指针分析的规则（Pointer Analysis Rules）是什么？

前4种语句：New / Assign / Store / Load。

指针分析的域和相应的记法：变量/函数/对象/实例域/指针，用pt表示程序中的指向关系（映射）。

规则：采用推导形式，横线上面是条件，横线下面是结论。

• New：创建对象，将new T()对应的对象oi加入到x的指针集。

• Assign：将y的指针集加入到x对应的指针集。

• Store：让oi的field指向oj。

• Load：Store的反操作。

  

如何理解指针流图（Pointer Flow Graph）？

问题：当一个指针的指向集发生变化，必须更新与它相关的其他指针。如何表示这种传递关系？PFG。

PFG：用指针流图PFG来表示指针之间的关系，PFG是有向图。

• Nodes：Pointer = V U (O x F) 节点n表示一个变量或抽象对象的域。
• Edges：Pointer X Pointer 边x -> y 表示指针x指向的对象may会流入指针y。

Edges添加规则：根据程序语句 + 对应的规则。

指针分析算法（Pointer Analysis Algorithms）的基本过程是什么？

【课程笔记】南大软件分析课程7——指针分析基础（课时9/10） - 简书

过程内PTA算法

如何理解方法调用（Method Call）中指针分析的规则？

怎样理解过程间的指针分析算法（Inter-procedural Pointer Analysis Algorithm）？

call

call语句规则：主要分为4步。

1. 找目标函数m：Dispatch(oi, k)——找出pt(x)，也即oi类型对象中的k函数。
2. receiver object：把x指向的对象（pt(x)）传到m函数的this变量，即mthis
3. 传参数：pt(aj), 1<=j<=n 传给m函数，即p(mpj), 1<=j<=n。**建立PFG边**，a1->mp1，…，an->mpn。
4. 传返回值：pt(mret)传给pt(r)。建立PFG边，r<-mret。

问题：为什么PFG中不添加x->mthis边？因为mthis只和自己这个对象相关，而可能有pt(x)={new A, new B, new C}，指定对象的x只流向对应的对象，是无法跨对象传递的。

（2）过程间PTA算法

问题：由于指针分析和CG构造互相影响，所以每次迭代只分析可达的函数和语句。然后不断发现和分析新的可达函数。

可达示例：

算法：黄色背景的代码是和过程内分析不同的地方。

即时调用图构建（On-the-fly Call Graph Construction）的含义是什么？

上下文敏感（Context Sensitivity, C.S.）是什么？

概念：

• call-site sensitivity (call-string)：根据调用点位置的不同来区分上下文，3：id(n1) / 4：id(n2)。
• Cloning-Based Context Sensitivity：每种上下文对应一个节点，标记调用者行数。克隆多少数据，后面会讨论。

上下文敏感堆（C.S. Heap）是什么？

堆抽象上下文不敏感：如果不区分8 X x = new X();调用的堆抽象的上下文，导致只有1个o8.f，把两个上下文调用产生的o8.f指向集合都合并了，得出了o8.f的错误指向的结果。

堆抽象上下文敏感：用不同的调用者来区分堆抽象，如3:o8、4:o8是不同的堆抽象。所以说，既要根据上下文的不同来区分局部变量，也要区分堆抽象，例如：3:p是给变量加上下文，3:o8是给堆抽象加上下文。

为什么 C.S. 和 C.S. Heap 能够提高分析精度？

上下文敏感的指针分析有哪些规则？

标记：根据调用者的行数来区分不同上下文，只要区分了函数、变量、堆对象，就能够区分实例域、上下文敏感的指针（变量+对象域）。C—上下文（暂时用调用点的行数表示），O—对象，F—对象中的域。

规则：跟之前区别不大，只是增加了个上下文标记，注意load表示和之前有区别。

如何理解上下文敏感的指针分析算法（Algorithm for Context-sensitive Pointer Analysis）？

常见的上下文敏感性变体（Context Sensitivity Variants）有哪些？

• Call-Site Sensitivity

• Object Sensitivity

  • 用抽象对象（由对象allocation sites表示）列表来构成上下文，而非call sites构成。

• Type Sensitivity

  • 使用包含allocation site的“类型”和堆上下文作为callee object。

常见的几种上下文变体之间的差别和联系是什么？

准确性来说，object > type > call-site。

就效率来说，type > object > call-site。

静态分析与安全

信息流安全（Information Flow Security）的概念是什么？

访问控制：关注信息访问。

信息流安全：关注信息传播。

信息流：x->y表示x的值流向y。

信息等级：对不同变量进行分级，即安全等级，H-高密级，L-低密级。

安全策略：非干涉策略，高密级变量H的信息不能影响（流向）低密级变量L。

如何理解机密性（Confidentiality）与完整性（Integrity）？

机密性—信息泄露，读保护；

完整性—信息篡改，写保护。

完整性错误类型：命令注入、SQL注入、XSS攻击、… 。都属于注入错误。

完整性更宽泛的定义：准确性、完整性、一致性。准确性表示关键数据不被不可信数据破坏；完整性表示系统存储了所有的数据；一致性表示发送的数据和接收的数据是一致的。

什么是显式流（Explicit）和隐蔽信道（Covert Channels）？

显示流：直接的数值传递。由于显示流能泄露更多信息，所以本课程关注显示流的信息泄露。

隐式信息流—侧信道：程序可能会以一些意想不到的方式泄露数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// Eg1 隐式流
if (secret_H < 0) 
  public_L = 1; 
else Public_L = 0;
// Eg2 终止信道
while(secret_H < 0) { ... };
// Eg3 时间信道
if (secret_H < 0)
  for (int i = 0; i< 1000000; ++i) { ... };
// Eg4 异常
if (secret_H < 0)
  throw new Exception("...");
// Eg5 如果访问数组越界，则可以推断secret可以为负数
int sa_H[] = getSecretArray();
sa_H[secret_H] = 0;

covert channels：信道指的是传递信息的机制，原本目的不是为了传递信息的信道。

如何使用污点分析（Taint Analysis）来检测不想要的信息流？

基于 Datalog 的程序分析

Datalog 语言的基本语法和语义是什么？

Datalog（Data + Logic）：是声明式逻辑编程语言，可读性强，最初用于数据库。现在可用于程序分析、大数据、云计算。特点—没有副作用、没有控制流、没有函数、非图灵完备（精简了许多功能）。

(1）Data（谓词、原子）

谓词Predicate：看作一系列陈述的集合，陈述某事情是不是事实（真假）。如Age，表示一些人的年龄。

事实fact：特定值的组合。Eg，(“Xiaoming”, 18)。

原子Atom：P(X1, X2, ... , Xn)。P表示谓词名，Xi表示参数（又叫term，可以是变量或常量）。Eg，Age("Xiaoming", 18) == true ；Age("Alan", 23) == false。

（2）Logic（Rule）

Rule：表示逻辑推导规则，若Body都为true，则Head为true。H <- B1, B2, ... ,Bn。H是Head，Bi是Body。

Eg，Adult(person) <- Age(person, age), age >= 18。

Rule要求：规则中的值要有限，如A(x) <- B(y), x > y；规则不能有悖论，如A(x) <- B(x), !A(x)。

Datalog中逻辑或：A或B都可推导出C，可写成C<-A. C<-B或者C<-A;B。

Datalog中逻辑非：!B(...)。

（3）Datalog谓词分类

• EDB（extensional database）外延数据库：谓词需预先定义，关系不可变，可被当做输入。
• IDB（intensional database）内涵数据库：谓词是根据规则建立的，关系是根据规则推导的，可被看作是是输出。

说明：H <- B1, B2, ... ,Bn，H只能是IDB，Bi可以是EDB或IDB。

递归性：Datalog支持递归，也即能够推导出自身。Eg，Reach(from, to) <- Edge(from, to)；Reach(from, to) <- Reach(from, node), Edge(node, to)。

（4）Datalog程序运行

Datalog程序运行：输入EDB+rules到Datalog引擎，输出IDB。

常用Datalog引擎——LogicBlox, Soufflé, XSB, Datomic, Flora-2。

Datalog程序性质：单调性、终止性。

如何用 Datalog 来实现指针分析？

EDB：程序句法上可获得的指针相关信息。如New / Assign / Store / Load语句。V-变量，F-域，O-对象。

• New(x: V,o: O) <- i: x = new T()
• Assign(x : V, y : V) <- x=y
• Store(x : V, f : F, y : V) <- x.f = y
• Load(y : V, x : V, f : F) <- y = x.f

IDB：指针分析结果。

• VarPointsTo(v: V, o : O) ，如VarPointsTo(x,oi)表示oi ∈ 𝑝𝑡(𝑥)
• FieldPointsTo(oi : O, f: V, oj : O) ，如FieldsPointsTo(𝑜i, 𝑓, 𝑜j)表示𝑜j ∈ 𝑝𝑡(𝑜i.𝑓)

Rules：指针分析规则（与之前相同）。先分析上下文不敏感。

（2）上下文不敏感PTA示例

步骤：其实指令处理顺序不固定。

1. 首先将EDB（指令）表示成表格数据形式。
2. 处理New指令
3. 处理Assign指令
4. 处理Store指令
5. 处理Load指令

（3）上下文敏感—全程序指针分析

call指令规则：S—指令，M—方法。共3条rule。

1. 首先找到调用的目标函数m，传递this指针。

   

2. 传递参数

   

   10-3-4-call规则2.png

3. 传返回值

   

全程序指针分析：引入程序入口函数m。

如何用 Datalog 来实现污点分析？

EDB谓词-输入：

• Source(m : M) ——产生污点源的函数
• Sink(m : M) ——sink函数
• Taint(l : S, t : T) ——关联某callsite l和它产生的污点数据t

IDB谓词-输出：

• TaintFlow(t : T, m : M) ——表示污点数据t会流向sink函数m

规则：处理source和sink函数。