【论文笔记】DynPTA: Combining Static and Dynamic Analysis for Practical Selective Data Protection

2021-0526-DynPTA

DynPTA: Combining Static and Dynamic Analysis for Practical Selective Data Protection

作者：Tapti Palit, Jarin Firose Moon, Fabian Monrose, Michalis Polychronakis

单位：Stony Brook University, UNC Chapel Hill

会议：S&P 2021

链接：https://www.computer.org/csdl/pds/api/csdl/proceedings/download-article/1t0x9hWW2iI/pdf

Introduction

随着控制流劫持攻击的缓解措施被广泛部署，攻击者逐渐关注针对内存破坏漏洞和信息泄露漏洞的data-only attack。在一定的条件下，通过破坏一些数据仍然能达到劫持控制流的目的。数据泄露同样会带来很大的安全隐患，例如secret server keys、用户隐私信息等。近年来出现的瞬态执行攻击同样可以用于敏感信息的泄露。

虽然各种针对于数据泄露攻击的缓解措施被提出，从保护思路是可以主要分为缓解memory corruption bugs的方案以及选择性的保护部分数据的方案。前者通过memory safety、dataflow integrity等方式消除攻击原语，但是这些方案通常会带来很高的性能开销且unscalable，即很难应用在一些复杂的real-world程序上，而且无法抵御瞬态执行攻击。后者则是通过权限隔离、安全执行环境、沙箱、细粒度内存隔离等方式有选择性的保护程序中的一部分数据。然而这些技术需要对代码进行较大规模的重构，对于较大规模的程序而言是一个挑战。

考虑到选择性保护数据方案的实用性，近年来的一些方案选择让开发者在源代码中对security-critical的变量进行标记，随后在编译时对这些被标记的变量进行保护。具体的有Datashield、Glamdring、Selective in-memory encryption等方案。

为了高准确度（减少插桩带来的开销）、合理的复杂度（能够应用于较大规模程序的分析），作者提出了DynPTA，结合静态程序分析和动态数据流追踪（DFT）技术使得被标记的数据在内存中一直处于加密状态。

作者基于LLVM实现了DynPTA并将其成功应用于Nginx with OpenSSL, Apache Httpd, and OpenVPN等。Nginx with OpenSSL的开销为19.2%，MbedTLS的开销仅为4.1%（13% for in-memory encryption, 35% for DataShield）。作者使用Heartbleed漏洞、Spectre-PHT、Spectre-BTB以测试DynPTA保护的有效性。

作者的贡献如下：

• 提出了一种结合静态分析与动态数据流追踪的方案以提高指针指向分析的扩展性和准确性
• 提出了一种summarization-based context-sensitive的堆建模方式以减少指针分析在分析堆分配使得过估计
• 实现了DynPTA，一个compiler-level保护开发者标记数据机密性的工具。
• 对DynPTA使用较大规模的程序进行了测试，并证明其能够在较低的开销下抵抗内存泄露攻击和瞬态执行攻击。

Background

Pointer Analysis

指针分析是一类特殊的数据流问题，它是其它静态程序分析的基础，但指针使用的灵活性导致了指针分析的复杂性，实际上精确的指针分析是一个不可判定问题，所以实际的指针分析算法都是近似且保守的，须在效率和精度之间进行折衷。在过去的近三十年间，指针分析一直是程序分析领域的研究重点之一，至今仍很活跃。指针分析研究的内容主要集中在分析精度和开销之间的取舍。精度方面，主要指流敏感性（flow-sensitivity）和上下文敏感性（context-sensitivity），一般而言，流敏感分析方法的精度明显好于流不敏感的分析方法，在上下文敏感性上也有同样的特点。

静态指针分析用于分析程序中指针可能指向的内存对象。虽然理论上静态指针分析是sound的，但是由于缺乏运行时信息，会出现over-approximation的现象，即指针的”points-to” set可能会包含运行时永远不会指向的object。

• 概念 {flow, context, path} sensitive
  • flow-sensitive: 流敏感，指令之间的顺序可以判定
  • context-sensitive：上下文敏感，指令所在的上下文可以判定
  • path-sensitive：路径敏感，所走的路径（if/else, …）可判定

在流不敏感的指针分析中，主要分为两类：基于包含的（inclusion-based）指针分析和基于合并的（unification-based）的指针分析。

• 基于包含的指针分析是一种基于约束集（constraint set）求解的流不敏感的指针分析方法。由Andersen与1994年提出，后来称之为Andersen-Style的指针分析。其算法的时间复杂度为$O(n^3)$，其中n指的是程序中参与分析的变量数。
• 基于合并的指针分析是由Steensgaard在1996年提出的，又成为基于等价（equivalence-based）的指针分析，其复杂度接近于线性复杂度。

Andresen’s inclusion-based和Steensgaard’s unification-based算法最常见的指针分析实现方式。算法主要包括两个部分：约束收集和约束求解。

• 约束收集

两者都是编译每一条指令并收集与指针流相关的约束。这些约束包括Addr-of, Copy, Deref, and Assign，对于C程序来说，分别对应的是p := &q, p := q, p := ∗q, and ∗p := q。每种算法都会使用一组解析规则来解决这些约束。

• Andresen’s pointer analysis constraint generation:

  

  int i, j, k;
  int* a = &i;
             // a ⊇ {i}
  int* b = &k;
             // a ⊇ {i}, b ⊇ {k}
  a = &j;
             // a ⊇ {i, j}, b ⊇ {k}
  int** p = &a;
             // a ⊇ {i, j}, b ⊇ {k}, p ⊇ {a}
  int** q = &b;
             // a ⊇ {i, j}, b ⊇ {k}, p ⊇ {a}, q ⊇ {b}
  p = q;
             // a ⊇ {i, j}, b ⊇ {k}, p ⊇ {a}, q ⊇ {b}, p ⊇ q
  int* c = *q;
             // a ⊇ {i, j}, b ⊇ {k}, p ⊇ {a}, q ⊇ {b}, p ⊇ q, c ⊇ *q

• Steensgaard’s pointer analysis constraint generation

  

  

• 约束求解

  • Andresen’s constraint resolution

    Andresen’s分析会为每个指针构建points-to的集合，当发现某一个指针有新的可能指向的对象时，会将这个对象加入到points-to set中，并重新计算所有涉及这个指针的Deref约束。其时间复杂度为$O(n^3)$，因此将其应用于大型程序时会带来较大的时间开销。

    Example：

    

    

  • Steensgaard’s constraint resolution

    

内存对象建模

尽管约束建模的方式会影响分析的速度与准确性，上下文敏感是一种约束建模的方式，其在分析函数调用时会考虑调用上下文关系。对于内存分配函数的wrapper而言，上下文敏感是一个十分关键的问题。对内存分配函数wrapper执行上下文无关的分析将导致所有指向对的指针都指向同一个对象。因此，作者引入了基于摘要的上下文敏感的堆建模方法。

In-memory Data Encryption

指针分析和value flow analysis能为我们提供所有可能访问敏感内存的memory load、store指令的位置。如何对这些敏感内存进行保护有很多的办法：software-based memory safety checks，在内存访问前插入几条指令进行判断，但并不能抵御瞬态执行攻击；hardware-enforced 内存隔离技术能够降低开销，但由于粒度较粗，没有办法用于单个内存对象。

作者选择将敏感数据始终加密存储在内存中，仅将其加载到CPU时对其进行解密。这种方法的优点在于可以抵御瞬态执行攻击，并不需要额外的硬件支持。

Threat Model

• 考虑memory disclosure和允许攻击者在用户空间任意地址读的data leakage vulnerabilities
• 针对修改数据、corruption attack不再考虑范围内
• 攻击者没办法进行任意代码执行，寄存器中的机密数据是安全的
• 只考虑用户空间的应用程序，假设攻击者无法破坏内核代码和数据
• 考虑Spectre-type和Meltdown-type的瞬态执行攻击
• 敏感数据潜在的隐式泄露不在考虑范围内（时间侧信道）

核心思想：利用静态分析保证所有可能的敏感内存访问都被覆盖，利用动态分析确定是否确实是敏感内存访问以避免过高的开销。

Example

举一个例子来说明DynPTA对敏感数据保护的优势，指针ptr1可能指向的内存对象为pts(ptr1) := {mem1, mem2, mem3, mem4}，pts(ptr2) := {mem3, mem4}。

如果仅以来静态分析的结果，则如（b）所示。虽然理论上只需要对真正的敏感内存mem4进行加解密，但是由于没办法确定ptr1、ptr2运行时指向的内存对象是否敏感，即ptr1、ptr2可能指向敏感内存对象，故只能将ptr1、ptr2指向的所有内存对象均当作是敏感内存对象来处理。对ptr1、ptr2所指向的内存对象进行写入/读取时均需要进行加/解密。从而导致开销急剧上升。

通过借助动态数据流追踪技术，DnyPTA可以确定ptr1、ptr2指向的是否为敏感内存对象，因此可以选择性的加/解密：当ptr1、ptr2指向敏感内存对象时进行加解密，否则正常读取写入。

Design

DynPTA分析的主要流程为：

• 通过开发者的标注，识别出初始敏感内存对象集合
• 使用Steensgaard’s指针分析算法并结合上下文敏感堆建模方式确定访问敏感内存的内存操作指令集合
• 对内存操作指令进行进一步分析，以找出从初始敏感内存对象到其他变量的value flow
• 对上述识别出的可能操作敏感内存的指令进行插桩，以在运行时通过DFT判断其是否读/写敏感数据，若为敏感数据，则在使用前对其进行加/解密。

Sensitive Object Identification

• DynPTA要求开发者在敏感指针初始化（赋值/指向新的object）时调用mark_sensitive()以对该指针进行标记。对于敏感变量而言，则需要在其定义时调用mark_sensitive()。

  

随后DynPTA会对这些annotations进行处理，以识别出所有的敏感对象，并使用DFT在运行时传递”sensitive”的label。

Summarization-based Context-sensitive Heap Modeling

大多数指针分析的实现都对Libc的内存分配进行了建模。例如p=malloc(…)代表一个object被malloc分配并传递到p。在存在内存分配函数的wrapper的情况下，会导致堆变得context-insensitive。因为Libc会返回的object仅会流向wrapper返回的一个指针，但该指针却流向所有的callsite。如Fig.3(a)所示。

因此，作者设计了一个基于摘要、上下文敏感的对堆进行建模的方法。主要分为：

• Memory Allocation Wrapper Identification，通过wrapper的特征（调用malloc，做一些额外的检查，把指针返回出去）识别wrapper。具体实现：通过LLVM提供的过程内Andersen’s指针分析（LLVM CFLAAAnders）以确定是否返回从函数内部新分配内存的指针。因为是过程内分析，故可以使用更准确、开销更高的Andersen算法。
• Memory Allocation Wrapper Summarization，对每个wrapper进行过程内分析，得到参数与返回值的指向关系，即“分配一个新的object，并返回它的引用”。对于CRYPTO_malloc，即返回对一个新的object的引用（FIg.3 b）。

Pointer and Value Flow Analysis

在完成上下文敏感的堆建模后，作者使用Steensgaard’s unification-based pointer analysis algorithm对程序中所有指针和内存对象进行分析。首先分析程序中的每一条指令并收集对应的约束条件，随后使用Steensgaard算法中的约束解析规则进行求解，从而为程序中的每个指针确定其指向内存对象的集合。

单纯保护初始敏感变量集合是不够的，敏感数据可能会propagate到其他内存对象上（sensitive sink sites）。为了防止潜在的信息泄漏，DynPTA进行了static value flow analysis以识别所有的sensitive sink site。

DynPTA将追踪direct and indirect value flows。

• direct value flow指的是从敏感内存对象load开始分析，并将最后store到的内存对象标记是敏感的，并递归寻找所有的direct value flow。
• indirect value flow指的是从一个may sensitive的内存对象中load出数据，因为静态分析精度不足，没有办法确定其是否真的是一个敏感对象。DynPTA会将他们全部收集起来，交给动态污点分析决定。因此DynPTA通过Steensgaard的分析结果，收集到的indirect value flow是所有sensitive value flow的超集。

Scoped Dynamic Data Flow Tracking

由于静态分析固有的和value flow analysis中存在的overapproximation，DynPTA使用scoped byte-level dynamic data flow tracking。通过shadow memory标记被追踪的内存对象，在每一个object被标记成敏感时初始化其对应的label，并通过DFT进行propagate，在指针进行解引用时对label进行轻量级的查找以确定其是否为sensitive object。（写入/读取sensitive object时进行加解密）

在free、和function return时清除sensitive object防止泄露。

作者表示，Steensgaard分析结果存在较大的过估计，约15%的内存操作都需要进行label lookup，但实际上只有1-5%的内存访问是sensitive的，需要进行AES加解密。

In-memory Data Protection using Encryption

使用AES-128-ECB模式，通过AES-NI、预计算轮密钥存在xmm0-xmm15以提高性能。

Implementation

基于LLVM 7.0，使用Gold Linker的link time optimization（LTO），导入除Glibc之外的所有用到的库进行分析，为常见的Glibc函数（memcpy、memcmp、strcpy）定义了规则。

Steensgaard’s Analysis

作者在SVF上实现了Steensgaard’s pointer analysis，每个约束只用处理一次，因此几乎是线性时间开销O(n)。

Performance Evaluation

使用八个应用程序进行实验，对其中的敏感数据进行了手动标注。实验环境为Intel Core i7-6700 CPU and 32 GB of RAM, running Ubuntu 19.10 and Linux kernel 5.3.0-40.

为Scoped DFT所添加的代码数量：

插桩的内存操作指令所占的比例：

作者使用Pin来记录有多少内存访问需要label lookup、有多少需要进行AES加解密。作者表示如果去掉Scoped DFT，所有可能敏感内存访问均需要进行AES加解密，开销会急剧上升（MbedTLS 4.1%→56%）

Runtime overhead: ApacheBench 执行五轮10000个请求，每轮请求文件大小递增（4KB-1MB），发现nginx并不会随着文件大小而增大开销。MbedTLS开销为4%，前者工作中DataShield为35%，in-memory encryption[33]为13%。

作者还对扩大保护范围所带来的开销进行了实验：

Security Evaluation

Heartbleed

使用Nginx+OpenSSL v1.0.1f进行实验，验证PoC exploit，发现每次私钥泄露时，总是密文。

Spectre

使用Spectre-PHT和Spectre-BTB的PoC，将其中的秘密字符串设置为敏感数据，验证exploit，发现其每次加载到缓存中均为其密文形式。

Conclusion

• DynPTA结合静态和动态分析，对内存泄露和瞬态执行攻击提供了切实有效的防御。（粗粒度&细粒度）
• Pointer Analysis

refs:

• 指针分析概述： http://cjc.ict.ac.cn/quanwenjiansuo/2011-7/ccm.pdf
• 指针分析： https://en.wikipedia.org/wiki/Pointer_analysis
• Andresen’s： https://blog.csdn.net/qq_43391414/article/details/110954280
• Steensgaard’s： https://blog.csdn.net/qq_43391414/article/details/111046505
• Andresen’s： https://blog.csdn.net/dashuniuniu/article/details/78704741
• Heap Abstractions for Static Analysis： https://arxiv.org/pdf/1403.4910.pdf