Rust Miri Bug: Tree Borrows Failing To Catch Aliasing

Rust's Miri and the Tale of Tree Borrows: A Deep Dive into Aliasing Violations

Rust, with its emphasis on memory safety, employs powerful tools like Miri and Stacked Borrows (SB) to detect potential issues. This article delves into a specific bug case where Tree Borrows falter in catching an aliasing violation, while Stacked Borrows successfully identify the problem. We'll explore the intricacies of this scenario, providing insights into Rust's memory model and the ongoing efforts to ensure its robustness.

Understanding the Core Concepts: Miri, Stacked Borrows, and Aliasing

Before we dive into the specifics, let's establish a clear understanding of the key players: Miri is an interpreter for Rust code that checks for undefined behavior. It's like a virtual execution environment that meticulously monitors your code's actions, ensuring they adhere to Rust's strict rules. Stacked Borrows (SB) is a sophisticated memory model implemented within Miri. It tracks the state of memory access, including borrows, mutable references, and raw pointers, to detect violations of Rust's aliasing rules. These rules are fundamental to Rust's safety guarantees; they prevent data races and other memory-related errors.

Aliasing refers to the situation where multiple pointers or references point to the same memory location. While aliasing itself isn't inherently bad, it becomes problematic when these aliases are used to modify the memory in ways that violate Rust's borrowing rules. For instance, having a mutable reference (&mut) and an immutable reference (&) to the same data at the same time is typically forbidden, as it could lead to data corruption.

The Bug Case: pop_front_unsoundness and the Linked List

The bug case in question, pop_front_unsoundness, originates from the linked_list_r4l crate, specifically within its tests. This test is designed to expose potential memory safety issues within a linked list implementation. The test attempts to trigger undefined behavior by concurrently accessing and modifying the linked list from multiple threads. This is a classic recipe for aliasing violations if the linked list's internal logic isn't carefully designed.

The test case works by creating multiple threads, each of which repeatedly pushes a shared node onto a linked list and then attempts to remove the front element. The goal is to induce a situation where the memory is accessed in an unsafe manner, violating the aliasing rules. The core problem arises when multiple threads are operating on the same data structures (in this case, the Arc<Node>). This concurrent access and modification can lead to memory corruption, especially if the linked list implementation doesn't properly handle synchronization.

#[test]
fn pop_front_unsoundness() {
    const N: usize = 1 << 7;

    let data = Arc::new(Node::new(0));

    thread::scope(|s| {
        let mut v_thread = Vec::new();
        for id in 0..1 << 4 {
            let handle = thread::Builder::new()
                .name(id.to_string())
                .spawn_scoped(s, || {
                    let mut list = List::<Arc<Node>>::new();
                    for n in 0..N {
                        list.push_back(data.clone());
                        list.pop_front().unwrap_or_else(|| {
                            panic!("[{n}] This shouldn't happen, because we just push a node.")
                        });
                    }
                });
            v_thread.push(handle);
        }
        drop(v_thread);
    });
}

Stacked Borrows vs. Tree Borrows: A Clash of Memory Models

Here's where the core issue arises: Stacked Borrows successfully identifies the aliasing violation, pinpointing the undefined behavior. The error message clearly indicates that the program is attempting to perform an invalid operation related to memory access. This validation confirms that the implementation of linked list has a concurrency bug. On the other hand, Tree Borrows fails to detect the same violation. This discrepancy highlights a critical difference in the capabilities of these two memory models. Tree Borrows, an alternative approach to memory tracking, doesn't catch the problem that Stacked Borrows identifies.

The difference in detection capabilities stems from how each memory model tracks and enforces aliasing rules. Stacked Borrows meticulously tracks the lifetime and permissions of each memory access, allowing it to detect violations with greater precision. Tree Borrows uses a different approach that may not be as sensitive to the specific patterns of aliasing that occur in this particular test case.

The implications of this discrepancy are significant. It reveals that Tree Borrows has a blind spot, a weakness in its ability to detect certain types of memory safety violations. This underscores the ongoing nature of research and development in Rust's memory model, as researchers continuously strive to improve the accuracy and completeness of these tools.

Diving Deeper: The Error and Its Root Cause

The error reported by Stacked Borrows provides valuable clues about the root cause of the bug. The error message indicates an attempt to retag a memory location for SharedReadWrite permission, but the necessary tag is missing in the borrow stack. This suggests that the code is attempting to create a mutable reference to data that is already being accessed in an unsafe manner, violating the aliasing rules. The backtrace provided in the error message further helps pinpoint the location of the error within the code, making it easier to identify the source of the problem.

The error occurs within the std::ptr::NonNull::<alloc::sync::ArcInner<Node>>::as_ref::<'_> function. This is because multiple threads are trying to access the shared Arc<Node>. This shared access, if not correctly synchronized, leads to the aliasing violation. The fact that the error occurs during the pop_front operation suggests that the linked list's internal logic for handling concurrent access to the head and tail pointers is flawed. The pop_front operation needs to be carefully synchronized to avoid race conditions. If one thread is modifying the linked list while another thread is attempting to read from it, the memory can become corrupted.

The fact that this bug is successfully detected by Stacked Borrows but missed by Tree Borrows is very important, because it shows the advantages of Stacked Borrows and the work is needed to be done in Tree Borrows.

The Path Forward: Improving Rust's Memory Safety

This bug case serves as a valuable learning experience and a catalyst for improving Rust's memory safety guarantees. It highlights the importance of rigorous testing, especially with tools like Miri and Stacked Borrows, to uncover subtle memory safety issues. The fact that this bug was found in the first place showcases the effectiveness of these tools in detecting undefined behavior.

The ongoing work to refine and improve Rust's memory model is critical. Developers are constantly working on better tools and techniques to identify and prevent memory safety issues. This includes improvements to Miri, Stacked Borrows, and other related tools. As these tools evolve, they become more effective at catching subtle bugs, helping developers write safer and more reliable code.

The community plays an important role. By reporting bugs, contributing to discussions, and providing feedback, developers help shape the future of Rust's memory model. The collaborative nature of the Rust community ensures that memory safety remains a top priority.

Conclusion: The Never-Ending Quest for Memory Safety

This bug case is a testament to the ongoing challenges and triumphs in the pursuit of memory safety. While Tree Borrows may have missed the aliasing violation, Stacked Borrows successfully identified the issue, demonstrating the power of these tools. This case underscores the importance of continuous testing, the evolution of memory models, and the collaborative efforts of the Rust community. As Rust continues to evolve, the tools and techniques used to ensure memory safety will continue to improve, making it an even more robust and reliable language for building safe and secure software.

For more in-depth information and discussions on this topic, consider checking out these resources:

• The Rust Unsafe Code Guidelines: https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md