Table of Contents

  1. 论文要解决的问题
    1. Rust
    2. Unsafe Rust
  2. 论文的解决方法
    1. 三种常见 Bug
      1. Panic 安全 Bug
      2. 高阶不变式 Bug
      3. Send/Sync Bug
    2. 两个分析算法
      1. 算法1: 不安全的数据流检查器
      2. 算法2: Send/Sync 检查器
  3. 评估
    1. 发现多少新 Bug
    2. 和其他方法的比较
    3. 准确率
  4. 不足
  5. 相关工作
  6. 进一步工作
  7. 参考资料
[posts]

Rudra 论文阅读

December 10, 2023

这篇文章介绍了 Rudra, 一个 Rust 编程语言的代码静态分析工具. 它可以检查代码中的内存安全错误. 它效率很高, 可以在六个小时内扫描几万个软件包. 在这个静态分析工具刚刚提出的时候, 它发现了两百多个内存安全问题, 其中许多问题都是比较难找的 Bug.

论文要解决的问题

Rust

Rust 是一个比较新的编程语言. 为什么要使用 Rust 呢? 因为内存安全. 动态分配内存是编程中非常常见的需求. 写个动态数组就已经在堆上分配内存了. 在 C 语言中, 分配内存造成的错误比比皆是, 例如空指针错误, 释放后使用等等. 一旦发生内存错误, 程序通常就进入不可恢复的故障状态, 十分严重. 靠人工审查代码无法杜绝内存安全问题, 因为它的复杂度太高了, 不论经验多么丰富的程序员都没有办法写出完美的代码. 需要一些自动的手段来保证内存是安全的. 这方面最常用的技术是垃圾回收. 网页上的 Javascript, 人生苦短我用 Python, 还有 Java 都是垃圾回收语言. 在这些编程语言中, 运行时环境自动检查变量的生命周期, 回收不再被使用的内存. 但是垃圾回收并不是解决一切问题的灵丹妙药. 除了性能开销之外, 垃圾回收最大的问题是难以控制. 在性能比较重要的应用程序中, 例如浏览器, 数据库, 操作系统, 用户往往希望手动管理资源, 因此垃圾回收在这种情况下不是一个很好的选择. 既要内存安全, 又不要垃圾回收, 在 Rust 之前还没有这种情景的解决方案.

借鉴在内存管理方面的优秀工程实践, Rust 总结出几条可以自动执行的规则(所有权, 借用, 别名异或可变), 交给编译器来施行. 有了这些规则, 使用 Rust 写的程序只要能通过编译, 就一定没有内存错误.

Unsafe Rust

凡事都有例外(除了这句话), Rust 也不例外. 安全的 Rust 无法应付以下几种常见的情况:

为了支持这些操作, Rust 提供了 Unsafe 功能, 在由 Unsafe 包裹的语句块中, 程序员可以解引用裸指针, 调用其他语言的函数等等. 像这样:

1
2
3
4
5
6
7
8
9
let mut num = 5;

let r1 = &num as *const i32;
let r2 = &mut num as *mut i32;

unsafe {
    println!("r1 is: {}", *r1);
    println!("r2 is: {}", *r2);
}

unsafe 将 Rust 划分成了两个子集: Safe Rust 和 Unsafe Rust. Safe Rust 可以确保完全没有内存安全问题, 但是一切 Safe Rust 都依赖于一些 Unsafe Rust, 而编译器无法承诺 Unsafe 的安全性. 因此, Unsafe Rust 的安全问题成为整个 Rust 内存安全的瓶颈, 其安全威胁也就更大.

来自 GaTech 的这些研究者在这篇文章中想要解决的, 就是 Rust 在 Unsafe 语句块中的内存安全隐患.

论文的解决方法

在这篇论文中, 研究者识别了 Unsafe Rust 中的三种漏洞模式, 然后提出了两种新的算法来解决它们.

三种常见 Bug

Panic 安全 Bug

Panic 是 Rust 中提供的一个宏, 用于在程序发生严重故障的时候直接中止程序. 其运行方式有些类似于 C++ 的异常. Panic 发生之后, 程序会一层层展开函数调用栈, 然后把控制权移交给程序的 Panic 处理器.

Panic 无法预测, 因此很难处理与之有关的 Bug. 程序的任何一次函数调用都有可能引发 Panic. 在 Panic 之后, 程序会从原本的执行路线离开. 原本的执行路线中也许本该执行一些 Unsafe 代码, 这些 Unsafe 代码用来确保整个函数是安全的. 但是这些代码被跳过, 因此程序会发生内存错误.

高阶不变式 Bug

泛型函数是现代编程语言中的重要特性. 使用泛型的时候往往要限制这函数只能适用于某些类型. 例如一个泛型的 print 函数只能打印支持打印的类型. 但我们在使用泛型函数的时候, 有时会不经意使用那些类型不满足的条件. 例如下面这个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
fn join<T>(array: &[T], sep: &str) -> String
where T: Convert<str>
{
    // code that handles array.len() == 0 or 1
    // ...

    let len = sep.len() * (array.len() - 1) + array.iter().map(|s| s.convert().len()).sum();
    let mut result = String::with_capacity(len);
    unsafe {
        // contains uninitialized bytes
        let mut buf = result.get_unchecked_mut(..len);
        buf.copy_and_advance(array[0].convert());
        for s in &array[1..] {
            buf.copy_and_advance(sep);
            buf.copy_and_advance(s.convert());
        }
        result.set_len(len);
        return result;
    }
}

这是一个类似于 Python Join 的函数, array 中的字符串会用 sep 连接起来.

这里只要求 T 可以转换为字符串, 但是实际上代码中做了更多的假设. 它要求 T 连续转换为字符串两次的结果一样. 通常来说这个条件都是满足的, 但不能排除一些恶意的代码两次转换为字符串的长度不同. 这样的话, 上面的这段程序在第一次调用字符串转换的函数, 获得字符串长度. 第二次调用字符串长度, 完成实际的复制. 复制的长度和分配的长度也许会不一样大, 这使代码出现内存安全问题.

Send/Sync Bug

Rust 用两个 trait Send 和 Sync 来处理并发安全问题. 实现 Send 的类型可以被复制到其他线程中, 实现 Sync 的类型可以被多个线程同时访问. 通常原始类型和派生类型都可以由编译器自动实现这两个 trait, 但是当涉及到同步原语(如 Mutex, RWLock)的时候, 这些 trait 的使用就会出现问题.

两个分析算法

Rudra 是一个静态分析工具. 它分析源代码的结构本身, 不需要运行原本的程序. 它分析的对象是 Rust 源代码的两个中间表示(分别为 HIR 和 MIR). Rudra 在 Rust 编译器中插入了两个新的分析流程, 运行自己的算法, 并最终生成一份报告.

算法1: 不安全的数据流检查器

这个算法的主要思路很简单. 其核心就是寻找不可立得的泛型函数. 它遍历所有涉及不安全操作的函数基本块, 在其中寻找函数调用点. 如果在一个基本块中找到不可立得的泛型函数, 那么这个基本块被认为存在安全隐患.

什么叫不可立得的泛型函数呢? 以上面那段代码为例, 一个类型 T 能否转换为字符串, 在实现 join 这个泛型函数的时候是不知道的. 它依赖于用户提供的一个函数, 将类型 T 转换为字符串. 既然如此, 这个用户提供的函数就是可疑的. 所以, 如果一个不安全块中存在不可立得的函数调用, 是值得我们加倍小心的.

算法2: Send/Sync 检查器

这个检查器通过一些启发式来判断类型 T 的代数数据类型(ADT)所需实现的 trait.

它有三个启发式:

评估

发现多少新 Bug

Rudra 消耗资源很少, 因为不需要实际生成例子和运行代码. 所以, 研究团队在 Rust 包管理器当时所有的四万个包上都跑了一遍, 发现了 264 个未知的内存安全漏洞.

和其他方法的比较

准确率

准确率不是很高.

不足

  1. 只能发现几类内存安全错误, 但这本来也就是没办法的事情.

  2. 假阳性很高, 高准确度模式下有 50%, 低准确度更是高达 80%.

  3. Bug 只是被发现, 没有详细的报告, 不知道错在哪里. 需要人为甄别.

相关工作

  1. Rust 的形式化方法和验证.

  2. 理解 unsafe rust.

  3. 大规模漏洞挖掘工具.

进一步工作

idk.

参考资料

[1] The Rust Programming Language

[2] RUDRA: Finding Memory Safety Bugs in Rust at the Ecosystem Scale