【论文分享】FlowMatrix

渗透技巧 2年前 (2022) admin

625 0 0

今天要分享的这篇论文是发表在Security’22的FlowMatrix。

在DIFT（Dynamic Information Flow Tracking）分析过程中，研究人员经常需要进行大量的DIFT查询。例如，在隐式流中，变量间接受到其他变量的影响，在对此类数据流进行分析时，需要使用多个DIFT查询来探测信息流。再例如，在系统配置诊断中，研究人员需要先使用DIFT找到bug，再采用不同的配置文件，检查程序中的多个信息流，来识别错误配置的根本原因和后果。在这种查询式的DIFT应用场景下，需要大量的计算资源支持。软件实现的DIFT通常具有高昂的运行时开销，现有的方法实现高效率的DIFT查询有：将数据流跟踪和程序执行分离并行到其它主机系统、快速路径分析无需插桩的路径、对常用的路径概括数据流等等，但是都没有加速污点传播过程本身。

TaintInduce（NDSS’19）指出污点传播本质上是指令输入如何影响其输出的数据依赖关系。它在程序跟踪中形成线性关系，这种线性关系可以表示为矩阵运算，FlowMatrix使用GPU作为协处理器为交互式DIFT查询操作提供高效支持。

Design

Matrix Representation

以x86指令“or al, bl”为例，它将ebx寄存器中的低8位与eax寄存器中的低8位进行或运算，并将结果存储在eax的低8位中。其中eax寄存器的污点状态取决于原来的eax寄存器和ebx寄存器的污点状态，ebx寄存器的污点状态保持不变，这种数据依赖关系可以被看作是污点状态的线性变换：从指令执行前的污点状态，变化为指令执行后的污点状态。

在该指令中，只考虑第一位的数据流，al和bl的第一个输入位影响al的第一个输出位。相应的DIFT传播规则可写为：

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

考虑所有的输入输出位：

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

因此一条指令Ii的污点规则可以表示为一个n×n的矩阵，作者将这种转移矩阵命名为FlowMatrix：

传播函数F：

从source到sink的信息流传播可以表示为：

【论文分享】FlowMatrix

多条指令的数据依赖关系的概括，可以通过将他们的FlowMatrices依次左乘得到，因此指令序列的数据流可以表示为：

【论文分享】FlowMatrix

作者将DIFT运算表示为矩阵运算，并使用GPU辅助进行高效的矩阵运算。因为大多数FlowMatrix中一个位的数据只流向几个位，因此稀疏度很高。为了节省空间，作者采用稀疏矩阵存储FlowMatrix，仅通过索引和值存储非零元素。

【论文分享】FlowMatrix

Overview

【论文分享】FlowMatrix

上图显示了基于FlowMatrix的离线DIFT查询系统，给定程序执行的trace信息，提供给用户一个交互式命令行界面，用来重复查询从不同的sources到sinks的信息流。

对于直接数据流依赖，DIFT查询系统需要完成以下几个步骤：

step 1：将trace信息加载到数据库；

step 2：构建查询树；

step 3：根据指令生成FlowMatrices；

step 4：DIFT查询；

对于间接数据流和隐式流，FlowMatrix支持额外配置DIFT传播规则，包含以下几个步骤：

step 5：配置额外的数据流依赖；

step 6：重新计算FlowMatrices；

step 7：DIFT查询。

【论文分享】FlowMatrix

Query Tree Construction

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

【论文分享】FlowMatrix

因此，作者在合理的预处理开销和快速的查询响应时间两者之间寻求平衡。作者使用了二叉树的数据结构构建查询树，其叶节点为每条指令的FlowMatrix矩阵，非叶节点为子节点的概括矩阵，查询树都是完全二叉树。基于这一数据结构，预处理（建树）只需要线性时间复杂度和线性空间复杂度，而查询任意区间内的数据流概括都是对数时间复杂度。