【论文分享】FlowMatrix

渗透技巧 2个月前 admin
157 0 0
今天要分享的这篇论文是发表在Security’22的FlowMatrix。
【论文分享】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寄存器的污点状态保持不变,这种数据依赖关系可以被看作是污点状态的线性变换:从指令执行前的污点状态,变化为指令执行后的污点状态。
【论文分享】FlowMatrix在该指令中,只考虑第一位的数据流,al和bl的第一个输入位影响al的第一个输出位。相应的DIFT传播规则可写为:
【论文分享】FlowMatrix
在布尔空间下可被表示为:
【论文分享】FlowMatrix
考虑所有的输入输出位:
【论文分享】FlowMatrix其中,Si表示指令执行前的状态空间,Si+1表示指令执行后的状态空间,wj,i取值为0或1,表示是否存在从第j个比特到第i个比特的数据流关系。
因此一条指令Ii的污点规则可以表示为一个n×n的矩阵,作者将这种转移矩阵命名为FlowMatrix
【论文分享】FlowMatrix

传播函数F:

【论文分享】FlowMatrix
从source到sink的信息流传播可以表示为:

【论文分享】FlowMatrix

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

【论文分享】FlowMatrix

【论文分享】FlowMatrix

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

【论文分享】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

【论文分享】FlowMatrix

Query Tree Construction 

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

【论文分享】FlowMatrix

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

Evaluation

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

【论文分享】FlowMatrix

【论文分享】FlowMatrix

Performance:和使用了同样的污点传播规则的基于CPU的DIFT工具相比,基于GPU的FlowMatrix在污点传播时平均性能提升5倍。

【论文分享】FlowMatrix

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

【论文分享】FlowMatrix

Throughput:基于FlowMatrix的DIFT查询系统平均一秒内可以处理约5百万的数据流。这一数值高于libdft三个数量级,和128核的JetStream达到了相同的水平。

【论文分享】FlowMatrix

【论文分享】FlowMatrix


最后,一些DIFT相关工作的论文分享:

TaintInduceFineDIFTSelectiveTaintGreyOne、ARMHEx



【论文分享】FlowMatrix

点击下方链接,获取论文原文






原文始发于微信公众号(COMPASS Lab):【论文分享】FlowMatrix

版权声明:admin 发表于 2022年10月2日 下午6:49。
转载请注明:【论文分享】FlowMatrix | CTF导航

相关文章

暂无评论

暂无评论...