2021-0925-SUTURE
Statically Discovering High-Order Taint Style Vulnerabilities in OS Kernels
作者：Hang Zhang, Weiteng Chen, Yu Hao, Guoren Li, Yizhuo Zhai, Xiaochen Zou, Zhiyun Qian
单位：UC Riverside
会议：CCS 2021
链接：https://www.cs.ucr.edu/~zhiyunq/pub/ccs21_static_high_order.pdf
Introduction
使用静态分析进行漏洞挖掘存在一个众所周知的问题：误报率高，尤其是针对像linux kernel这种代码量较大的系统，这也使得几乎没有误报的动态分析技术如fuzzing等更受欢迎。
大型系统中往往存在一些很复杂的漏洞，从用户输入（taint source）到最终触发敏感操作（taint sink）需要经历一系列的函数调用，作者称这些漏洞为high-order taint style vulnerabilities。
实现一个能够发现high-order vulnerabilities、good coverage, while minimizing false alarms的静态分析工具主要存在两个挑战：1. 分析需要对一个entry函数走过尽可能多的组合（在序列中的调用顺序）2. 足够准确的处理有检查的cross-entry taint flow，否在会带来很多的误报。
作者实现了SUTURE，一个高精度、可扩展的静态分析工具，以发现OS kernel中的high-order taint style vulnerabilities。SUTURE使用了一种summary-based high-order taint flow construction的方法对cross-entry taint flows进行模拟。能够得到高精度的inter-procedural flow-, context-, field-, index-, and opportunistically path-sensitive static taint analysis分析结果。
作者在多个主流Android kernel上使用SUTURE，生成了79个true positive warning groups，其中19个被厂商确认。
Overview
The Motivating Example
Workflow
Static Analysis Design
Positioning
基于Dr. Checker主要的数据结构实现，并作出了诸多改进，作者指出主要特点：1. 支持high-order taint flow construction，2. 数个提升分析精度和准确性的技术
Definitions
Def 0. entry function作为入口函数，在同一模块内没有调用者，由用户或其他模块进行调用（如ioctl）
Summary-Based High-Order Taint Flow Construction
Taint Summary Generation
与之前的taint summary类似，区别在于SUTURE使用这些summaries连接多个top-level entry functions，而不是把caller连接到callee。
因为当指针涉及全局变量时，它可能在任何的entry function中被改变。
High-Order Taint Flow Construction
Global Memory Matching
SUTURE能够处理两种global memory：显示定义的和可以通过全局指针访问的内存。后者处理起来更困难啊。
T3可以连接T1，T3也可以连接T4
Taint Overwrite
Opportunistic Path Sensitivity
众所周知，由于无法感知冲突的路径约束，静态分析可能会分析不可达的路径，从而导致不准确（例如，不可能的污点传播）和效率低（例如，分析不必要的分支）。直接的解决方案时采用path-sensitive的分析方案，但是由于复杂的约束求解和路径爆炸，完全的path-sensitive方案的开销过高。因此作者希望能够尽可能path-sensitive，同时避免过高的开销，因此称为opportunistic path-sensitive analysis。
主要基于两点观察：
- 内核中很大一部分的路径约束很简单，收集并求解这些路径约束可以做大量的剪枝
- 可以以某种形式讲path-sensitive分析结合进flow-sensitive的工作流程中
约束收集比较简单，当分支属于𝑜𝑝 ∈ {==, >, <, ≥, ≤}时，收集约束。作者称可以在17条不可行路径中过滤掉16条路径。
Multi-Source Multi-Sink Pairing
这是作者表示在研究过程中遇到的另一个问题，如果处理不好，会导致points-to、污点的爆炸，并导致大量的误报。常用的指针赋值处理方式如Dr. Checker和SVF中是all to all的，即取并集or双射，但是显然在程序的实际运行中下图中subs和data_subs是对应的。
为了解决这个问题，作者采用“折叠”的方式，使sink和source共享同样的源。
Other Improvements in SUTURE
Memory SSA based Analysis
虽然LLVM IR变量是SSA形式的，但是内存对象却不是，就造成了实现flow-、context-sensitive分析时的困难。
为了解决这个问题，SUTURE实现了一种on-the-fly memory SSA 分析。
Index Sensitivity
处理了常量索引的读取（v=a[2]）
General Language Feature Support
改进了Dr. Checker的结构体嵌套、指针运算
Kernel Code Pattern Handling
加入了基于类型的方法来解决间接调用目标
Multi-Tag Taint Analysis
Vulnerability Discovery And Warning Grouping
Vulnerability Detectors
沿用了Dr.Checker的漏洞检测器
On-Demand Query of Taint Summaries
Warning Grouping
Implementation
- built on top of Dr. Checker
- 15k代码量
- LLVM 9.0
Evaluation
Dataset
Efficacy of SUTURE’s Static Analysis Improvements
Vulnerability Discovery Accuracy
Known High-Order Taint Vulnerabilities
Efficiency
Study of Discovered Vulnerabilities
整数溢出：
OOB：
Conclusion
作者使用了诸多针对于静态分析的优化，实现了十分高精度的静态分析，从而能够发现较复杂的一些漏洞。