SafeDrop

What is SafeDrop?

Rust is an emerging programming language that aims to prevent memory-safety bugs. However, the current design of Rust also brings side effects, which may increase the risk of memory-safety issues. In particular, it employs OBRM (ownership-based resource management) and enforces automatic deallocation of unused resources without the garbage collector. It may therefore falsely deallocate reclaimed memory and lead to use-after-free or double-free issues.

We study the problem of invalid memory deallocation and propose SafeDrop, a static path-sensitive data-flow analysis approach to detect such bugs. Our approach analyzes each API of a Rust crate iteratively by traversing the control-flow graph and extracting all aliases of each data-flow. To guarantee precision and scalability, we leverage a modified Tarjan algorithm to achieve scalable path-sensitive analysis, and a cache-based strategy to achieve efficient inter-procedural analysis.

Our experiment results show that our approach can successfully detect all existing CVEs of such issues with a limited number of false positives. The analysis overhead ranges from 1.0% to 110.7% in comparison with the original compilation time. We further apply our tool to several real-world Rust crates and find 8 Rust crates involved with invalid memory deallocation issues.

How SafeDrop works?

This section will demonstrate the execution process of SafeDrop using a test case, linking the detection process to the main code of SafeDrop.

POC

For the test case, we chose the same PoC as in the paper to facilitate user understanding and testing:

fn genvec() -> Vec<u8> {
    let mut s = String::from("a_tmp_string");
    let ptr = s.as_mut_ptr();
    let v;
    unsafe {
        v = Vec::from_raw_parts(ptr, s.len(), s.len());
    }
        // mem:: forgets); // do not drop s
        // otherwise, s is dropped before return
        return v;
}
fn main() {
    let v = genvec();
    // use v -> use after free
    // drop v before return →> double free
}

SafeDrop Query

First, in the RAP backend, we embedded a Query in the compiler called SafeDrop.

This Query can be enabled through a command line parameter in the frontend, located in the file compiler/rustc_interface/src/passes.rs:

#![allow(unused)]
fn main() {
if env::var_os("RUSTC_BOOTSTRAP").is_none() && env::var_os("SAFEDROP").is_some() {
        sess.time("safedrop_check", || { tcx.hir().par_body_owners(|def_id| tcx.ensure().safedrop_check(def_id));});
}
}

The environment variable "SAFEDROP" is set by the front end, while "RUSTC_BOOTSTRAP" is used to prevent calling this query during Rustc's bootstrap process. It should only be used when analyzing third-party programs.

We have inserted the query code into compiler/rustc_mir_transform/src/lib.rs. This query's function body is called whenever Rust analyzes each function.

#![allow(unused)]
fn main() {
fn safedrop_check<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> () {
    if let Some(_other) = tcx.hir().body_const_context(def_id.expect_local()){
        return;
    }
    if tcx.is_mir_available(def_id) {
        rap_info!("{:?}", def_id);
        let body = tcx.optimized_mir(def_id);
        let mut func_map = FuncMap::new();
        let mut safedrop_graph = SafeDropGraph::new(&body, tcx, def_id);
        safedrop_graph.solve_scc();
        safedrop_graph.safedrop_check(0, tcx, &mut func_map);
        if safedrop_graph.visit_times <= 10000{ safedrop_graph.output_warning(); }
        else{ rap_error!("SafeDrop: Over_visited: {:?}", def_id); }
    }
}
}

Data Structure

For SafeDrop, the data structure SafeDropGraph<'tcx> maintains the context of the analysis results.

Our analyzer constructs an instance for each analyzed function, the definition is provided as follows:

#![allow(unused)]
fn main() {
pub struct SafeDropGraph<'tcx>{
    pub def_id: DefId,
    pub span: Span,
    // contains all varibles (including fields) as nodes.
    pub nodes: Vec<Node>,
    // contains all blocks in the CFG
    pub blocks: Vec<BlockNode<'tcx>>,
    pub arg_size: usize, 
    // we shrink a SCC into a node and use a father node to represent the SCC.
    pub father_block: Vec<usize>,
    // record the constant value during safedrop checking.
    pub constant_bool: FxHashMap<usize, usize>,
    // used for tarjan algorithmn.
    pub count: usize,
    // contains the return results for inter-procedure analysis.
    pub return_results: ReturnResults,
    // used for filtering duplicate alias assignments in return results.
    pub return_set: FxHashSet<(usize, usize)>,
    // record the information of bugs for the function.
    pub bug_records: BugRecords,
    // a threhold to avoid path explosion.
    pub visit_times: usize
}
}

Next, we will mainly discuss several important functions of SafeDropGraph<'tcx>. It is evident that the processing logic in the query is quite simple, with two key methods: solve_scc and safedrop_check.

Graph Traversal

#![allow(unused)]
fn main() {
    safedrop_graph.solve_scc();
    safedrop_graph.safedrop_check(0, tcx, &mut func_map);
}

Rust Analysis Platform