今天为大家推荐的论文是来自新加坡国立大学Curiosity Reserach Group投稿的,关于动态污点分析(DIFT)的最新工作 FlowMatrix: GPU-Assisted Information-Flow Analysis through Matrix-Based Representation,目前该工作已经发表于USENIX Security 2022。
研究背景
了解程序执行过程中的信息流是进行许多高级系统诊断和攻击响应的基础。常用技术之一便是动态信息流追踪(DIFT,又名动态污点分析),用户通过追踪程序执行中的数据流,来实现入侵检测、敏感数据泄露检测、系统配置诊断等。
现有方法若要支撑高效率的DIFT查询,有两种不同的思路:一种思路是加大算力,使用服务器集群,录制执行后、分布式分段回放(OSDI’16)。集群,这一土豪的需求,制约了这一技术的推广普及。另一种思路是加速DIFT本身,如将污点传播逻辑分离至另一线程(CCS’13, Security’15)、分析无需插装的路径(Micro’06, RAID’19)、对常访问的执行路径概括数据流(PLDI’10)等。这些方法大体思路是在减少插装和污点传播逻辑的调用,但并未真正加速污点传播这一过程的本身。究其根本,现有技术都是使用高级语言,为每一条机器指令,量身定制了由if和for组成的污点传播规则。而这样的代码,很难被进一步简化,或是提炼成为一种公式规则。
作者将这样的转移矩阵
数据依赖关系概括
根据线性代数运算的结合律,不必先进行矩阵与向量间的运算,可以先进行矩阵之间的乘法:
因而可以总结出,多条指令的数据依赖关系的概括,可以通过将他们的FlowMatrices依次左乘得到。
因此,在项目中,作者使用了GPU进行FlowMatrix相关的运算,以获得显著的性能提升。
在论文中,作者还提出了针对用户使用过程中,因间接数据流而导致under-tainting情况的解决方案。允许用户自由地为选定的指令,配置不同的传播策略。限于篇幅,这部分内容请参考原论文。
速度性能 和使用了同样的污点传播规则的CPU实现的工具相比,基于GPU的FlowMatrix在污点传播时平均能获得5倍的速度性能提升。
而对于大部分的场景而言,一个查询请求都可以在0.5秒内得到结果。
吞吐量 作为一款DIFT查询工具,其数据流的吞吐量性能显得尤为重要。具体而言,平均FlowMatrix的查询系统一秒内可以处理约5百万的数据流。
由于篇幅关系,其他方面的实验评估(如性能瓶颈分析、扩展性研究、案例分析等)在此略去,大家可以阅读原文。
附录:程序数据流中的线性关系
考虑指令“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]的线性映射。因此,单个比特的数据流可被抽象为以下表达:
若将以上线性关系扩展至整个输出状态空间,则可得到方程组:
这一方程组完整地描述了每条指令的从其执行前的输入空间,到执行后的输出空间的线性映射。已知线性映射可以被写作,系数矩阵乘以列向量,得到一个新的列向量的形式。作者将w从这样的线性方程组中取出,构成系数矩阵:
作者将这类矩阵定名为FlowMatrix,表示了从输入空间到输出空间的转移矩阵,即为指令的污点传播关系。
代码链接:
个人主页:https://mimicji.github.io/
https://www.comp.nus.edu.sg/~liangzk/
原文始发于微信公众号(安全研究GoSSIP):G.O.S.S.I.P 阅读推荐 2022-09-06 FlowMatris
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论