G.O.S.S.I.P 阅读推荐 2022-09-06 FlowMatris

今天为大家推荐的论文是来自新加坡国立大学Curiosity Reserach Group投稿的，关于动态污点分析（DIFT）的最新工作 FlowMatrix: GPU-Assisted Information-Flow Analysis through Matrix-Based Representation，目前该工作已经发表于USENIX Security 2022。

研究背景

了解程序执行过程中的信息流是进行许多高级系统诊断和攻击响应的基础。常用技术之一便是动态信息流追踪（DIFT，又名动态污点分析），用户通过追踪程序执行中的数据流，来实现入侵检测、敏感数据泄露检测、系统配置诊断等。

在日常安全分析的场景下，当研究人员在数据流分析时，需要结合之前的分析，频繁地更改数据流追踪的起点（source）和终点（sink），以达到最终的分析目的。譬如在系统配置诊断的场景下，研究人员或许会需要先使用DIFT找到bug，再使用同一技术对bug产生的配置文件进行溯源，最后再次执行DIFT分析该配置错误对全局造成的影响。作者将这样对于同一程序执行的过程，重复多次地执行不同起点终点的DIFT任务，称之为DIFT查询。

尽管是同一程序，现有技术需要研究人员对每一次数据流分析执行一次全新的动态信息流追踪。然而，DIFT素来有着高昂的运行开销，能达到4倍至8倍之多。这使得DIFT查询变得非常困难：研究人员每一次提出一个新的查询需求时，都不得不等待数分钟乃至数十分钟之久。

现有方法若要支撑高效率的DIFT查询，有两种不同的思路：一种思路是加大算力，使用服务器集群，录制执行后、分布式分段回放（OSDI’16）。集群，这一土豪的需求，制约了这一技术的推广普及。另一种思路是加速DIFT本身，如将污点传播逻辑分离至另一线程（CCS’13, Security’15）、分析无需插装的路径（Micro’06, RAID’19）、对常访问的执行路径概括数据流（PLDI’10）等。这些方法大体思路是在减少插装和污点传播逻辑的调用，但并未真正加速污点传播这一过程的本身。究其根本，现有技术都是使用高级语言，为每一条机器指令，量身定制了由if和for组成的污点传播规则。而这样的代码，很难被进一步简化，或是提炼成为一种公式规则。

方法介绍

数据流中的线性关系

在NDSS 2019的TaintInduce工作中发现了污点传播规则本质上是数据依赖关系的一种表示形式。以一条简单的“or al, bl”x86指令为例，下图展示了这条指令的数据依赖关系，亦是其污点传播规则：这一指令执行后，al寄存器的值来源于旧的al和bl两者；而bl寄存器则保有其原本数据。

指令or al, bl的数据流关系

而这样的数据依赖关系，实际上可以被看作是一个污点状态的线性变换：从指令执行前的寄存器污点状态，变化为指令执行后的污点状态（内存亦是如此）。而线性变换，可以被写作转移矩阵  乘以原本向量空间  （执行前状态），得到新的向量空间  （执行后状态）:

  

作者将这样的转移矩阵  ，命名为FlowMatrix，其由01组成、描述了比特之间是否存在数据流依赖。关于这一部分更为细节的带公式推导，请参见最后的附录部分。下图给出了“or al, bl”的FlowMatrix示例：

指令or al, bl的FlowMatrix

至此，作者定义了一条指令执行时的基于矩阵表达形式的全新污点传播规则。

数据依赖关系概括

考虑当有两条指令时，FlowMatrix方法下的污点传播规则可以被写作：

  

根据线性代数运算的结合律，不必先进行矩阵与向量间的运算，可以先进行矩阵之间的乘法：

  

不难发现，乘积矩阵将会是向量空间  到向量空间  的转移矩阵，其概括了两条指令中的数据依赖关系（污点传播规则）。

因而可以总结出，多条指令的数据依赖关系的概括，可以通过将他们的FlowMatrices依次左乘得到。

GPU硬件加速

FlowMatrix相关的运算实为大量的矩阵运算，而普通的CPU 并不擅长处理此类运算。

GPU作为目前炙手可热的硬件设备，常用于机器学习等任务中，非常擅长并行任务，比如说，矩阵乘法~

因此，在项目中，作者使用了GPU进行FlowMatrix相关的运算，以获得显著的性能提升。

高效离线DIFT查询

目前，作者提出了新的支持概括的数据流关系矩阵FlowMatrix，有了GPU辅助，如何支撑高效率的DIFT查询仍是未知数。

具体来说，若是如同传统的顺序传播的DIFT技术，在每次收到查询请求时，对source和sink之间进行污点传播，仍存在每次查询响应时间过长的问题；若是提前预处理所有可能的合法查询，则需要预处理的内容过多，带来不必要的存储开销和高额的预处理运算开销。

因此，谋求一个解决方案，平衡预处理开销和查询响应时长二者，显得尤为重要。基于离线程序执行指令记录，作者提出了一个基于线段树的数据结构，其叶节点为每条指令的FlowMatrix矩阵，非叶节点为子节点的概括矩阵。

这一数据结构，预处理（建树）只需要线性时间复杂度和线性空间复杂度，而查询任意区间内的数据流概括都是对数时间复杂度。基于这一数据结构，实现了一个交互式命令行DIFT查询框架。

在论文中，作者还提出了针对用户使用过程中，因间接数据流而导致under-tainting情况的解决方案。允许用户自由地为选定的指令，配置不同的传播策略。限于篇幅，这部分内容请参考原论文。

实验评估

作者选取了不同类型的15个CVE和7个常见的应用，记录了它们指令执行记录作为数据集。

速度性能 和使用了同样的污点传播规则的CPU实现的工具相比，基于GPU的FlowMatrix在污点传播时平均能获得5倍的速度性能提升。

而对于大部分的场景而言，一个查询请求都可以在0.5秒内得到结果。

吞吐量 作为一款DIFT查询工具，其数据流的吞吐量性能显得尤为重要。具体而言，平均FlowMatrix的查询系统一秒内可以处理约5百万的数据流。

而这一数值，高于其他污点分析工具诸如libDft三个数量级；和基于128个CPU核心的JetStream服务器集群DIFT查询解决方案，也达到了不相上下的水平。

由于篇幅关系，其他方面的实验评估（如性能瓶颈分析、扩展性研究、案例分析等）在此略去，大家可以阅读原文。

附录：程序数据流中的线性关系

考虑指令“or al, bl”，作者暂且只关注al寄存器中第一位的数据流，其可被写为：

al[1]←al[1], bl[1]

其在布尔空间下可被表示为：

al[1]=al[1]+bl[1]

添上其他无数据流的比特：

al[1]=1*al[1]+0*al[2]+0*al[3]+…+0*al[8]+1*bl[1]+0*bl[2]+…+0*bl[8]

而上述等式实际上描述了，从al和bl两寄存器的输入状态空间，到al[1]的线性映射。因此，单个比特的数据流可被抽象为以下表达：

  

  表示指令执行前的状态空间，  表示指令执行后的状态空间，  ,i取值为0或1表示是否存在从第j个比特到第i个比特的数据流关系。

若将以上线性关系扩展至整个输出状态空间，则可得到方程组：

这一方程组完整地描述了每条指令的从其执行前的输入空间，到执行后的输出空间的线性映射。已知线性映射可以被写作，系数矩阵乘以列向量，得到一个新的列向量的形式。作者将w从这样的线性方程组中取出，构成系数矩阵：

作者将这类矩阵定名为FlowMatrix，表示了从输入空间到输出空间的转移矩阵，即为指令的污点传播关系。

论文链接：https://www.usenix.org/system/files/sec22-ji.pdf

代码链接：

https://github.com/mimicji/FlowMatrix

---

投稿作者介绍：

季凯航 新加坡国立大学

新加坡国立大学在读博士，目前主要方向为二进制代码分析和系统日志分析，相关研究成果发表在国际顶级会议USENIX Security, NDSS, ISSTA上。

个人主页：https://mimicji.github.io/

---

如果对 Curiosity Research Group 感兴趣，梁振凯老师也在招收系统安全方向的博士生和博士后，详细信息可以参考梁老师个人主页：

https://www.comp.nus.edu.sg/~liangzk/

原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2022-09-06 FlowMatris