【论文分享】硬件追踪隐式流IFTU

今天要分享的这篇文章是发表在ICCAD'16的IFTU（Implicit Flow Tracking Unit），硬件辅助追踪隐式信息流。

Background

显式信息流有直接的数据依赖关系（譬如赋值语句）。与之相对地，隐式信息流间接依赖控制流（譬如if语句）。动态污点分析DIFT（Dynamic information flow tracking）被广泛应用于敏感信息泄漏检测，如果不考虑隐式流会产生欠污染（under-tainting）问题，进而导致漏报。

回顾之前解决隐式流问题的研究工作。软件实现的动态污点分析工具：Egele等人对运行时遇到的所有条件分支指令，如果有至少一个源操作数被污染，那么就会为分支内的所有指令的目的操作数标记污点；DTA++进一步地有选择地对部分条件分支指令追踪隐式流。但是因为需要插桩大量的额外代码，性能明显降低（譬如DTA++1.5X性能开销）。硬件辅助的动态污点分析工具：RIFLE利用二进制重写将由于条件跳转产生的隐式信息流转换为显式污点传播，但是因为依赖于为追踪显式流设计的硬件，因此需要额外的代码转换将隐式流转换为显式流而导致性能严重降低；GLIFT和Leases在门级追踪信息流，但是需要重新设计硬件。

这篇论文提出了一种用于隐式流追踪的专用硬件单元IFTU，可以以合理的面积开销（4.5 KB内存和28.18% LUTs，其中5.7%用于隐式流追踪）和低性能开销（3%）有效地追踪隐式流和显式流。

Algorithm

为了处理隐式流，除了污点标记，额外引入了tPC（program counter tag）标记控制流路径是否受到污染数据的影响。下表显示了SPARC架构上包含tPC的污点传播规则。

这里需要解决两个问题：一是程序分析每个条件分支的范围；二是分支没有执行的路径同样有可能会导致信息泄漏，需要额外传播tPC。

上图(c)显示了论文中传播tPC的机制。作者维护了一个tPC的栈，用于在每个嵌套分支保存和恢复tPC的值。在条件分支之前将当前tPC值入栈，然后当需要清除tPC时，只需用从出栈覆盖当前的tPC值。对于一些复杂的情况，例如下图(a)中，假设当前控制流路径为(1)-(3)-(4)，如果按照原有的算法，tPC出栈的次数会大于入栈的次数，因此需要如下图(b)中所示插入一个冗余的push操作的基本块。

此外，对于循环，如下图(a)所示，执行循环中的基本块(3)会进行多次push操作，但是只会在跳出循环的基本块(4)进行一次pop操作。因此，作者只在循环的入口处进行一次push操作。

对于条件分支中没有被执行的路径，因为攻击者很难通过内存推断隐式流，因此作者只考虑需要额外标记污点的寄存器。如下图所示，考虑基本块(1)，D表示定义寄存器的基本块，浅灰色表示至少和一个D基本块相连的基本块，深灰色表示可达D基本块的基本块。算法从基本块(1)开始进行深度优先搜索，如果遇到深灰色的基本块，则对基本块(1)到当前基本块（即基本块(5)）的边的目的寄存器标记污点。作者利用LLVM编译器对源代码进行插桩。

完整的算法如下图所示：

Architecture

如上图所示，IFTU作为一个单独的加速器，利用CDI（Core Debug Interface）获取指令的执行信息，包括指令地址、进程ID、内存访问指令的地址/值、分支类型/源地址/目标地址，异常和特权模式信息等。

Evaluation

面积开销和性能开销：

论文原文链接：A Hardware-based Technique for Efficient Implicit Information Flow Tracking https://hongcezh.people.ust.hk/publication/iccad16/iccad16.pdf

参考文献

1. Egele, Manuel, et al. "Dynamic spyware analysis." USENIX Security. 2007.
2. Kang, Min Gyung, et al. "Dta++: dynamic taint analysis with targeted control-flow propagation." NDSS. 2011.
3. M. Tiwari, et al. "Execution leases: A hardware-supported mechanism for enforcing strong non-interference." MICRO. 2009.
4. M. Tiwari, et al. "Complete information flow tracking from the gates up." ACM Sigplan Notices. 2009.
5. N. Vachharajani, et al. "Rifle: An architectural framework for user-centric information-flow security." MICRO. 2004.