【论文分享】libdft

今天要分享的这篇文章是发表在VEE’12的libdft，一个开源的软件实现的动态污点分析工具。

动态污点分析（DTA）的背景知识和相关论文分享：TaintInduce、FineDIFT、SelectiveTaint、GreyOne、ARMHEx。

Data Tracking

csum和data存在直接的数据流依赖，authorized和phash存在间接的控制流依赖（隐式流）。libdft支持多进程多线程的byte级别的分析粒度，提供1-byte或者1-bit的tag大小，不考虑隐式流问题，忽略EFLAGS寄存器，不包括浮点指令。

Data Sources

libdft基于Intel Pin动态二进制插桩（DBI）工具构建。program instructions、function calls和system calls可以被作为sources或者sinks。

Tag Storage

mem_bitmap用于存储1-bit tag大小对应的内存的tag，采用固定size直接映射的结构，避免复杂的管理和访问，3 GB的内存空间需要384 MB的内存。具体地说，vaddr的高29位被用作index，低3位用作offset，tval = mem_bitmap[vaddr >> 3] & (MASK << (vaddr & 0x7))，通过设置MASK为0x1、0x3、0xf可以分别得到单个byte、word、double word的tags。

tseg用于存储1-byte tag大小对应的内存的tag，采用动态分配的结构。当显式地调用mmap、mremap、brk、shmat或者隐式地load image，libdft分配一块同样大小的内存。STAB用于映射vaddr对应tseg中的字节，对于3 GB的内存空间和4 KB的页表，STAB需要3 MB的内存。为了方便，libdft要求与相邻内存页匹配的tseg也是相邻的。vaddr的高20位被用作index，taddr = vaddr + STAB[vaddr >> 12]。

Optimizations

fast_vcpu 如果将每个线程的vcpu存储在一个由Pin分配的虚拟线程id索引的全局数组中，因为可以从多个线程同时访问该数组，因此需要加锁以在创建新线程时安全地扩展。此外，检索vcpu需要额外的指令（即数组查找）。因此libdft利用Pin的临时寄存器来存储指向每个线程的vcpu的指针。每次创建新线程时，libdft分配一个新的vcpu，但是不将其添加到数组中，而是将其地址保存在临时寄存器中，分析程序接收指向vcpu的寄存器作为参数。好处是避免了加锁和额外的数组索引操作，但是需要更多的寄存器溢出（保存/恢复寄存器的内容到内存）。

fast_rep 部分x86指令（MOVS、STOS、LODS）可以通过REP前缀重复执行。为了插入分析代码，Pin将它们视为包含无前缀指令的隐式循环。因为以REP 为前缀的指令被转换为循环，并且tag传播在循环内执行，因此引入了额外的开销。每次重复使用的有效地址 (EA) 取决于前一次重复使用的EA以及EFLAGS寄存器中DF位的值：EA = EAprev ± {1, 2, 4}。libdft利用这一观察将部分分析代码移出循环。

huge_tlb 由于tag传播代码和应用程序指令交错执行，内存访问分散在应用程序和影子内存之间，从而导致大量的TLB miss。libdft通过使用mmap的MAP_HUGETLB选项分配mem_bitmap和STAB时使用4 MB（启用PAE的话最大为2 MB）大小的页面，来减少TLB miss。

tmap_col 代码段和很多数据（常量、不可变对象、专用共享内存段）都是写保护的，因此，当采用1-byte tag时，libdft将与写保护内存区域相对应的tag存储折叠，从而减少内存开销。libdft使用mmap分配了一个特殊页面，当映射/分配新的写保护页面时，使用映射到特殊页面的加数更新相应的STAB条目。此外，还需要显式地处理mprotect，以处理稍后或临时映射为可写的写保护页面。

Evaluation

论文分别使用了Web和数据库DB服务器、命令行和网络工具、Web浏览器和SPEC CPU 2000基准测试程序来进行性能评估。

命令行和网络工具，libdft-bit产生了1.14x-6x（平均3.65x）的延迟，libdft-byte产生了1.20x-6.03x（平均3.72x）的延迟，仅Pin就会产生1.17x的延迟。

Web服务器，1Gbps网络，libdft产生的延迟不超过2.04x。

MySQL上libdft平均产生了3.36x的延迟。