Flowstitch
核心思想是对数据流进行分析，将本来不想干的数据流通过缝合技术使其想干，从而造成数据泄露或者提权。思路很好，但是具体的实现途径没有理解到位，需要多研读。
1. Abstract
问题：控制流劫持方法变得困难，而攻击目标的非控制流数据不需要转移控制流。但没有系统化的方法根据内存错误自动构造数据。
方法：开发了data-flow stitching，系统的发现将程序中的数据流加入到面向数据的利用方法。
结果：FLOWSTITCH自动构造了16个未知的和3个已知的面向数据点攻击。所有自动构造的利用都遵循CFI和DEP约束。19个中10个可以在ASLR机制下运行。所构建的利用可能造成重大损害，如敏感信息(如密码和加密密钥)的泄露和特权的升级。
2. Introduction
内存错误利用中，攻击者通常寻找机会执行任意恶意代码。这样的攻击一般情况下回劫持程序的控制流，包含代码劫持和代码重用，但可以通过control-flow integrity(CFI)、data execution prevention(DEP)和address space layout randomization(ASLR)机制进行防御。
除了面向控制流的攻击之外，还有面向数据流的攻击，文章称之为data-oriented attacks。可以给程序数据做手脚或者造成程序泄露隐私数据。面向数据流的攻击可以躲过DEP、CFI和ASLR的防御。但目前没有一个系统化的方法来证明面向数据流攻击的能力。
本文研究了根据给定的内存缺陷自动构造面向数据流利用的方法。根据一个新的概念data-flow stitching，开发了一个新的方法，能够面向数据流攻击。核心理念在于stitch，通过将已有的数据流路径进行缝合，利用内存错误，从而形成新的数据流路径。Data-flow stitch连接两个或者更多的不相邻数据流路径，从而攻击者可以将一个隐私数据写入公共的输出中。
问题：目标是通过面向数据流的攻击检测一个程序是否可利用，如果能，则自动生成面向数据流的利用。本文旨在提供一个能够与动态发现bug的工具集相结合的利用生成的工具集。
相对于面向控制流的攻击，面向数据流的攻击更难以实现，即使攻击者在攻击后也不能执行他们的恶意代码。虽然程序中有着丰富的内存数据，但这些数据间如何互相影响从而造成缺陷是难以发现的。主要挑战在于庞大的内存状态空间中进行搜索，从而展现出一个新的数据序列，例如数据泄露或者提权。另一个额外的挑战是地址随机化ASLR，它使得绝对地址值无法使用。
方法：我们开发了一种方法来优先搜索需要单个新边或新数据流路径中少量新边的data-flow stitch。也开发了一个工具用于解决对内存布局了解较少时带来的挑战。为了修剪搜索空间，使用符号执行根据新的数据流路径对路径约束进行建模，然后使用求解器检测可行性。
FLOWSTITCH方法将一个有内存错误的脆弱性程序作为输入，动态二进制分析来构造信息流图，输出面向数据流的利用，从而造成隐私数据泄露或者修改敏感数据。
结果：通过实验可以验证该方法的可行性。在评估中，发现多重数据流利用通常由一个脆弱点造成。在8个真实的脆弱性程序中，FLOWSTITCH自动构造了19个面向数据流的利用，16个是未知的。所在构造的利用点都违背了内存安全，但是完全遵循CFI约束。在静态数据流图中没有创造新的边。所有的攻击都在DEP保护措施打开的情况下，10个攻击在ASLR的约束下也能攻击。目前主流的面向数据流的攻击只是增加了一个新的数据流边，但本文发现的7个利用只有在数据流图中添加多个数据流边时才可行，这表明了自动构建技术的有效性。
贡献：
- 提出data-flow stitching概念，并开发了一个新的方法，通过在应用程序中将内存错误组成良性数据流，系统化的构造面向数据的攻击
- 构建了一种面向数据流的攻击方法，FLOWSTITCH。可以直接操作Windows和Linux的二进制。
- 本文表明构造面向数据流的攻击是可行的，并提供了一个方法来绕过控制流防御机制。
3. Evaluation
3.1 Efficacy in Exploit Generation
如Table2中所示，用到的程序来自不同的分类，从而确保FLOWSTITCH可以处理不同的脆弱性。7个程序是服务器程序包含HTTP和FTP服务器，这些是远程攻击的主要目标。另一个是sudo程序。细节如table3所示。
FLOWSTITCH生成了19个面向数据流的攻击。其中7个使用了多边缝合。由多边缝合产生的大量新的面向数据的攻击凸显了系统方法在管理复杂性和识别新的面向数据的攻击方面的重要性。
有10种攻击可以在ASLR的约束下进行，在10种攻击中，2种攻击重用堆栈上的随机地址，8种攻击破坏确定性内存区域的数据。我们注意到，安全敏感的数据，比如配置选项，通常在C程序中表示为一个全局变量，驻留在.bss段中。这突出了当前ASLR实现的局限性，它随机化了堆栈和堆地址，而不是.bss段
3.2 Reduction in Search Space
如table3所示，SSHD程序中，在源数据流中有776个节点包含哈希root密码的过程，56个节点引导数据输出。最终有43456种组合，经过优化，可以将可能性降到194中，缩减比例达到224倍
3.3 Performance
table4展示了路径生成和数据流收集(Slicing)的时间。trace generaion time包含了执行未记录的指令的时间。一般10分钟内生成。Slicing的时间较多，一般占有20%-87%的时间。目前slicer基于BAP IL文件，以后可能会使用并行工具进行优化。
4. Limit
文中没有明确介绍该方法的局限性
5. Method
5.1 Problem Definition
5.1.1 Motivating Example
这是一段服务端的示例代码，加载私钥和client建立HTTPS连接。14行有个栈溢出漏洞。然而脆弱函数的栈上并没有明显的安全敏感非控制数据。
为了创建一个面向数据的攻击，我们分析程序在正常输入下执行的数据流模式，其中至少包含两个数据流:一个流涉及到由名为privKey的指针指向的敏感私钥，另一个流涉及到由名为reqFile的指针指向的输入文件名，后者被写入程序的公共输出。在正常情况下，两条数据流是没有交集的，但我们可以构造特定的内存，从而将私钥写入公共的输出空间。具体来说，攻击者利用缓冲区溢出进行攻击，破坏指针reqFile，使其指向私钥。这强制程序将私钥复制到第16行sprintf函数中的输出缓冲区，然后程序将输出缓冲区发送到第17行客户机。此时，攻击不会改变控制流，并且执行与正常过程相同的执行路径。
这个例子很好的解释了面向数据流的攻击，通过操纵正常的数据流而不改变它的控制流。现实世界的程序要复杂得多，而且通常只能使用二进制形式。为这样的程序构造面向数据的攻击是一项具有挑战性的任务，我们在这项工作中处理。
5.1.2 Objectives & Thread Model
本文旨在开发一个通过缝合数据流的面向数据流攻击的技术。这个攻击会导致如下几种结果：
- G1：数据泄露
- 密码或者私钥
- 随机值
- G2：提权
- 系统调用参数
- 设定配置
威胁模型：假设执行环境中部署了各种防御机制用于抵御控制流劫持。所有的不确定性系统生成的值对于攻击者来说都是秘密的。
5.1.3 问题定义
为了构造面向数据流的利用，本文引入了一个新的概念two-dimensional data-flow(2D-DFG)，表示给定程序中数据流的两个维度：内存地址和执行时间。2D-DFG是一个有向图，用 G = { V , E } G=\{V,E\} G={V,E}表示。V表示一个变量，在address-time空间种用 ( a , t ) (a,t) (a,t)表示，a是变量的地址，t是创建变量时的执行时间。address包含内存地址和寄存器名字，execution time表示为程序执行轨迹中的指令计数器。 E E E记为 ( v ′ , v ) (v',v) (v′,v)，v’指向v，表示节点v‘和v之间的数据依赖。即v的值或者地址源自v’。所以，2D-DFG也可以表示指针变量和被指变量之间的指向关系。每个变量都有一个值(value)属性，记为 v . v a l u e v.value v.value。
当一条指令在execution time t写入address a，就创建一个新的点 v = ( a , t ) v=(a,t) v=(a,t)。如果一条指令将v’作为源操作数，并将v作为目标操作数，则会创建一个新的数据边(v‘， v)。因此一条指令可以创建多个节点。2D-DFG是根据具体的输入在执行时创建的有向数据流图，而不是静态分析中的静态数据流图。Figure1就是Code1对应的2D-DFG图。
之后定义data-flow stitching的核心问题。对于有内存错误的程序，将如下参数作为输入：一个源自正常程序执行的2D-DFG图G，memory error influence I I I，两个点 v s v_s vs(source)和 v T v_T vT(target)。在上述例子中， v S v_S vS是私钥的buffer， v T v_T vT是公共输出buffer。我们的目标是生成一个新的2D-DFG图 G ′ = { V ′ , E ′ } G'=\{V', E'\} G′={V′,E′}， V ′ V' V′和 E ′ E' E′由内存错误利用造成， G ′ G' G′包含从 v S v_S vS到 v T v_T vT的数据流路径。令 E ‾ = E ′ − E \overline{E} = E'-E E=E′−E是边集的差， V ‾ = V ′ − V \overline{V}=V'-V V=V′−V为点集的差。 E ‾ \overline{E} E就是我们需要产生的新的边。
memory error influence I I I表示可以通过内存错误写入的内存位置的集合，是一系列节点的集合。因此我们必须选择 V ‾ \overline{V} V中 I I I的子集。为了实现G1，本文将带有秘密信息的变量作为源节点，带有公共输出的变量作为目标节点。为了实现G2，原节点是攻击者控制的变量，目标节点是强调安全的变量，例如系统调用的参数。一个成功的面向数据的攻击应该额外满足如下两个要求：
- R1：可利用的输入满足程序路径约束，能够到达内存错误，创建新的边，从而继续执行到达创建 v T v_T vT的指令
- R2：在利用中被执行的指令必须满足静态控制流图
5.1.4 Key Technique & Challenges
Data-flow stitch关键点在于如何查找新的边集 E ‾ \overline{E} E，加入到 G ′ G' G′中，那么这就增加了从 v S v_S vS到 v T v_T vT新的数据流路径。对于 e d g e ( x , y ) ∈ E ‾ edge(x,y)\in \overline{E} edge(x,y)∈E，x依赖于 v S v_S vS，y依赖于 v T v_T vT。我们将包含与 v S v_S vS相关的节点的子图作为源，包含与 v T v_T vT相关的节点的子图作为目标。对于每个节点对 ( x , y ) (x,y) (x,y)，x位于源中，y位于目标中，该工具检测x和y之间是否有一条memory error influence I I I产生的 E ‾ \overline{E} E中的边。顶点x和y可以直接包含在 I I I中，也可以通过破坏它们在 I I I中的指针而通过一系列边连接起来。如果我们改变了写x的地址，或者改变了读y的地址，x的值就会流向y。如果这样，我们称 ( x , y ) (x,y) (x,y)为stitch edge，x是stitch source，y是stitch target。为了发现2D-DFG中的data-flow stitching。面临如下挑战：
- C1：巨大的搜索空间
- C2：不了解内存布局
2D-DFG只捕获执行中的数据依赖关系，将控制依赖关系和程序沿执行路径施加的任何条件约束抽象出来。为了满足R1和R2，还有另一个挑战：
- C3：复杂程序点路径约束
5.2 Data-flow Stitching
5.2.1 Basic Stitching Technique
一个基本的面向数据流的攻击在新的边集 E ‾ \overline{E} E中增加了一条边。我们称这个为single-edge stitch。为了寻找single-edge stitch，我们通过利用influence set I I I来修剪搜索空间。influence set I I I包含能够被内存错误影响的节点。对于目标中的节点，攻击者仅能够影响与 I I I有交集的节点。
3个观察到的点：
- 寄存器节点能够被忽略，因为内存错误不能改变他们。
- 节点必须在内存错误前被定义，在内存错误后读出
- 在内存地址维度，节点地址应该属于 I I I的内存区域
StitchAlgo1，首先获取目标流 TDFlow，它只考虑数据边。对于目标流中满足要求的每个顶点v，我们将内存错误顶点到v的边添加到 E ‾ \overline{E} E中，作为一种可能的解决方案。在算法中，将搜索空间简化为，在发生破坏时，源流中的活动变量与目标流和 I I I交集中顶点的笛卡尔积。
5.2.2 Advanced Stitching Technique
Single-edge stitch 是基本方法，用于创建一条新边。Advanced data-flow stitch技术创建 E ‾ \overline{E} E中的多条边的路径。multi-edge能够通过多种方式生成。首先攻击者可以多次利用Single-edge stitch方法来生成multi-edge stitch。另一个是pointer stitch，这使得修改的节点在之后会成为源流是的节点或者目标流中的节点。由于指针决定了stitch源或stitch目标的地址，因此破坏指针会引入两种不同的边:一条边用于新的“指向”关系，另一条边用于被更改的数据流。
对于Code2中的代码示例，Figure4是多边stitch的示意图。灰色边增加了一个新的指向信息，黑色虚线边将新的变量写入参数。
StitchAlgo-2用于发现使用pointer stitching的multi-edge利用。基本原理：检查源流和目标流中的节点，是否被2D-DFG中另一个节点指向，该工具选择这样一个节点进行构造。这样的节点对于源流和目标流是不一样的。如果v是目标流，那么我们需要找一条边 ( v ′ , v ) (v',v) (v′,v)，v’是一个指针节点，我们将vp指向源流中的节点vs，这样就能创建一条新的边 ( v s , v ) (vs,v) (vs,v)。如果v在源流中，那么我们需要找一条边 ( v , v ′ ) (v,v') (v,v′)，v‘是一个指针节点，改变vp，指向目标流中的一个节点vt，从而创建一条新的边 ( v , v t ) (v,vt) (v,vt)。
同时也要考虑stitching 点的活跃性。例如当它被用于写入到目标节点时应该承载着有效的源数据。一旦选择好指针节点，那么最后一步就是利用内存错误将值写入。
该方法利用活跃分析和memory error influence I来缩减搜索空间。也就是说如果memory corruption发生在t1之前，那么stitch边中用到的节点在t1之前就必须是活跃的，如果memory corruption
发生在t1之后，那么stitch边中用到的节点在t1之后就必须是活的。此外，也要将节点约束在
I
I
Ivs 。我们将选自源流的节点成为
R
−
s
e
t
R-set
R−set，将选自目标流中的节点称为
W
−
s
e
t
W-set
W−set。此时可以将搜索空间降为
R
−
s
e
t
R-set
R−set和
W
−
s
e
t
W-set
W−set的笛卡尔积。
R
−
s
e
t
=
V
(
S
r
c
F
l
o
w
)
∩
I
,
W
−
s
e
t
=
V
(
T
g
t
F
l
o
w
)
∩
I
∣
S
S
n
a
v
i
e
∣
=
∣
V
(
S
r
c
F
l
o
w
∣
×
∣
V
(
T
g
t
F
l
o
w
)
∣
∣
S
S
p
o
i
n
t
e
r
−
s
t
i
t
c
h
∣
=
∣
R
−
s
e
t
∣
×
∣
W
−
s
e
t
∣
R-set = V(SrcFlow)\cap I, W-set = V(TgtFlow)\cap I \\ |SS_{navie}|=|V(SrcFlow|\times |V(TgtFlow)| \\ |SS_{pointer-stitch}|=|R-set|\times |W-set|
R−set=V(SrcFlow)∩I,W−set=V(TgtFlow)∩I∣SSnavie∣=∣V(SrcFlow∣×∣V(TgtFlow)∣∣SSpointer−stitch∣=∣R−set∣×∣W−set∣
Pointer stitch与指针的层次结构相符合。对于二级指针stitch，可以构造一个指针vp2，指向vp，可以将vp当做目标节点，另一个指针vp’作为源节点，这样就可以再次利用StitchAlgo-2算法，StitchAlog-2算法可以重复利用，从而实现搜索多级stitch。而且对于每一级之间的stitch可以使用其他single-edge stitch算法。
5.2.3 Challenge from ASLR
ASLR给面向数据流的攻击带来了巨大的挑战，本文提出来两种方法来解决这个挑战：其一是用确定性地址stitch，其二是地址重用技术。
Stitching With Deterministic Address
当关键安全数据存储在确定性地址，这样的数据不受ASLR的影响。
当前ASLR实现将很大一部分程序数据留在确定性内存区域。例如，在编译Linux二进制文件时通常不使用“-pie”选项，从而导致确定的内存区域。Table1显示了Ubuntu12.04中确定性内存区域的大小。
对这些确定性地址进行stitch操作是极其有用的。
Stitching By Address Reuse
大量随机地址位于内存中，利用这一特性来实现绕过ASLR。
两种地址重用类型：partial address reuse和complete address reuse。
- Partial Address Reuse：相对地址中，基址是相同的，攻击者可以计算出相对地址。另一方面，指令点内存地址通常也是基址+偏移量，可以控制偏移量，重用随机的基址，指向源节点或者目标节点。
- Complete Address Reuse：由于寄存器资源限制，变量的地址一般保存在内存地址中。如果可以获得保存在内存中的地址，则攻击者可以重用随机化的点的地址来绕过ASLR。
对于部分地址重用，内存错误利用破坏变量偏移量，而对于完全地址重用，内存错误利用可以从内存中检索地址。我们的方法使内存错误影响 I I I与源流和目标流相交。然后，我们从新的源流和新的目标流中搜索来识别匹配的指令，从这些指令中我们可以用上面讨论的方法通过地址重用来构建stitch。
5.3 The FLOWSTITCH System
error-exhibitiing input和benign input应该是程序执行相同的路径，直到内存错误指令，使得error-exhibition input造成crash。
FLOWSTITCH构建面向数据流的攻击共5步：
- 对给定的程序生成执行路径，对begnign input生成begnign trace，对error-exhibition input生成eror-exhibiting trace。
- 根据error-exhibiting trace确定内存错误的影响，生成到达内存错误的约束
- 使用begnign trace进行数据流分析和安全敏感数据识别
- 从安全敏感数据流中选择要进行stitch的数据
- 检查新边的可行性，验证并利用，最终输出面向数据流的攻击
符号执行工具(BAP, SAGE)用于找begnign input和error-exhibition input输入对
5.3.1 Memory Error Influence Analysis
FLOWSTITCH使用error-exhibiting trace分析内存错误的影响 I I I，主要包含两个方面：
- 时间影响：内存错误发生的时间
- 空间影响：可以写入的内存范围
FLOWSTITCH还需要找指令解引用地址来自error-exhibiting input，这些指令称为memory error instructions。在这些指令之前结束或者在他们之前开始的数据流不受内存错误的影响。
使用符号执行工具来确定空间影响。满足约束的点地址集和解引用的地址位于内存错误的指令构成空间影响。
5.3.2 Security-Sensitive Data Identification
四种类型的数据是感兴趣的：输入数据、输出数据、程序秘密信息、权利标志。
在生成trace时执行污点分析，将输入数据作为外部污染源，从而找到相关的输入数据。
能够输出信息的函数参数就是输出数据。
我们将程序秘密标志和权限标志分为两类：程序相关的数据和通用数据。
对于程序相关数据可以通过用户指定来进行查找。例如安全标志。
对于通用数据，使用如下的方法来进行推断：系统调用参数、配置数据、随机数据
确定性内存区的明确：检查二进制中运行时不会随机化的内存区，如果不是位置无关的，则所有的数据段都是确定性内存区。FLOWSTITCH扫描begnign trace来找到所有的将数据写入确定性内存区的内存写指令，从而确定哪些数据被存储在确定性存储区。
5.3.3 Stitching Candidate Selection
首先尝试单边stitch技术，当single-edge stitch搜索空间耗尽，再进行multi-edge stitch。
先考虑对确定性地址进行stitch，再进行地址重用
5.3.4 Candidate Filtering
为了克服C3，通过下面的约束来检查每个stitch edge的可行性，称之为stitchability constraint：
- 路径条件到达内存错误指令
- 路径条件继续到达目标流
- 控制数据的完整性
FLOWSTITCH使用符号执行工具生成stitchability constraint。约束作为输入被发送到SMT求解器。如果求解器不能找到任何满足约束的输入，FLOWSTITCH选择下一个候选stitch edge。如果存在，则输入将是用于执行路径的见证输入，以显示面向数据的攻击。
符号约束可能不是完全的，它可能允许产生不同路径的输入。
5.4 Implemention
- Trace Generation：利用BAP提供的Pintraces工具，Pintraces是一个Pin工具，使用动态二进制插桩来记录执行状态。
- Data Flow Generation：污点分析方法找到数据流。为了生成安全敏感数据的数据流，FLOWSTITCH对begnign trace执行前向和后向切片，定位所有相关指令。
- Constraint Generation and Solving：stitchability constraint 包含path constraints，influence constraints和CFI constraint三种。使用BAP生成公式来找path constraints和influence constraints。对于控制流完整性约束，实现了一个方法来对trace进行搜索，找到所有的
jmp和ret指令。控制流完整性要求在运行时，不能被内存错误修改包含控制流信息的内存区。
6. Problem(myself)
对于这个方法还没有完全理解：
- 2D-DFG图具体是如何构建的，后续分析都是基于2D-DFG进行的，那么这个图的完整性以及准确性又是如何验证的
- 文中提到的内存和指令是如何联系到一块的，如何根据指令确定内存区
- Memory Error Influence Analysis还是没理解到是什么
- 文章对于思路的介绍偏多，实际与实现相关的介绍偏少