Chapter 5.2. Alias Analysis

Alias analysis determines whether two program places (variable references, raw pointers, or their fields) point to the same memory allocation at a given program point. The task is challenging, with various options that balance precision and cost, including flow sensitivity, field sensitivity, and path sensitivity. RAPx provides two complementary approaches:

  • MOP (Meet-Over-all-Paths): Path-sensitive enumeration with path reachability filtering, field-sensitive, context-insensitive.
  • MFP (Maximum Fixed Point): A lattice-based dataflow analysis using the rustc_mir_dataflow framework, path-insensitive but efficient for complex control flow.

Both approaches implement the AliasAnalysis trait, which defines a uniform query interface.

5.2.1 AliasAnalysis Trait

RAPx provides the AliasAnalysis trait for alias analysis. The trait enables users to query the aliases among the arguments and return value of a function based on the function DefId, or the aliases of all functions as an FxHashMap. Developers can implement the trait based on their needs.

#![allow(unused)]
fn main() {
pub trait AliasAnalysis: Analysis {
    fn get_fn_alias(&self, def_id: DefId) -> Option<FnAliasPairs>;
    fn get_all_fn_alias(&self) -> FnAliasMap;
    fn get_local_fn_alias(&self) -> FnAliasMap;
}
}

The alias analysis result for each function is stored as FnAliasPairs, containing a HashSet of AliasPair instances:

#![allow(unused)]
fn main() {
pub struct FnAliasPairs {
    arg_size: usize,
    alias_set: HashSet<AliasPair>,
}

pub struct AliasPair {
    pub left_local: usize,       // parameter id; return value is `0`
    pub lhs_fields: Vec<usize>,  // field-sensitive: sequence of field numbers
    pub right_local: usize,
    pub rhs_fields: Vec<usize>,
}
}

Each AliasPair records an alias relationship between two program places, expressed as (parameter_id.field_seq, parameter_id.field_seq). The return value is assigned index 0, and function parameters use indices 1, 2, ..., arg_count. For example, (0, 1.1) means the return value aliases with the second field of the first parameter.

5.2.2 MOP-Based Alias Analysis

The MOP-based alias analysis achieves path sensitivity by enumerating distinct CFG paths and performing alias checks independently on each path, then merging results. The implementation lives at rapx/src/analysis/alias_analysis/default/.

5.2.2.1 Architecture: AliasGraph

The central data structure is AliasGraph, which wraps a PathGraph and layers alias-specific state on top:

#![allow(unused)]
fn main() {
pub struct AliasGraph<'tcx> {
    pub path_graph: PathGraph<'tcx>,
    pub constants: FxHashMap<usize, usize>,
    pub visit_times: usize,
    pub values: Vec<Value>,
    pub block_facts: Vec<AliasBlockFacts<'tcx>>,
    pub alias_sets: Vec<FxHashSet<usize>>,
    pub ret_alias: MopFnAliasPairs,
    pub arg_size: usize,
    pub span: Span,
}
}

Key fields:

  • path_graph: The PathGraph providing CFG topology, SCC decomposition, and path reachability filtering.
  • values: Heap-allocated nodes representing program places (locals and their field projections). Each Value records the originating MIR local, drop properties (may_drop, need_drop), a kind (RawPtr, Ref, etc.), and optional father information for field projections.
  • block_facts: Per-block assignments and constant values extracted from MIR. Each AliasBlockFacts contains Assignment records (Copy, Move, InitBox, Variant) and ConstValue records.
  • alias_sets: A flat vector of alias equivalence classes, each represented as an FxHashSet<usize>. Membership lookup uses linear scan over sets (distinct from the union-find structure used in MFP).
  • ret_alias: The accumulated alias results for the function (MOP version with drop metadata).

5.2.2.2 Path-Sensitive Analysis via PathGraph Integration

The MOP analysis integrates with PathGraph for path-sensitive traversal. The overall flow in AliasGraph is:

  1. AliasGraph::new() creates a PathGraph for the function and initializes values from MIR locals with drop and type information.
  2. For each MIR basic block, AliasGraph extracts AliasBlockFacts — assignments (_1 = copy _2, _1 = move _2, _1 = &_2, _1 = &raw _2), aggregate initializations (tuples, structs decomposed field-by-field for field sensitivity), and constant values.
  3. find_scc() delegates to PathGraph::find_scc(), reusing the same SCC tree decomposition and top-down traversal strategy.
  4. process_function_paths() walks each enumerated path block-by-block. For each block, it calls:
    • alias_bb(): Processes intra-block assignments — copies values from right-hand to left-hand sides, syncs field aliases, and propagates father aliases.
    • alias_bbcall(): Handles call terminators — looks up the callee's alias summary, maps formal parameters to actual arguments, and merges the callee's alias relationships into the caller's alias sets.
  5. After processing all paths, merge_results() collects alias pairs among function parameters and the return value, performs alias compression (field truncation and containment merging), and stores the result in ret_alias.

The path sensitivity is achieved by processing each PathGraph-enumerated path independently: process_function_paths() maintains path-local alias_sets and values state, resetting between paths. The reachability filtering from PathGraph prunes infeasible paths early via check_segment_reachability_with().

5.2.2.3 Feature: Path Reachability Filtering

The MOP-based alias analysis enumerates structurally distinct CFG paths. However, correlated branch conditions on the same discriminant can make certain combinations unreachable — for example, taking the First branch of a match after having already taken the Second branch on the same Selector. PathGraph provides check_segment_reachability_with() to prune such infeasible paths during enumeration, using the discriminant constraint tracking described in Section 5.1.2.3.

For example:

#![allow(unused)]
fn main() {
enum Selector { First, Second }

fn foo<'a>(x: &'a i32, y: &'a i32, choice: Selector) -> &'a i32 {
    let a = match choice {
        Selector::First => x,
        Selector::Second => y,
    };
    match choice {
        Selector::First => a,
        Selector::Second => x,
    }
}
}
  • Without path filtering: 4 paths, merged result {(0,1), (0,2)} — incorrectly suggests the return value may alias y.
  • With path filtering: 2 reachable paths, result {(0,1)} — correctly excludes the impossible y alias.

5.2.2.4 SCC Handling via PathGraph

A major challenge for path-sensitive analysis lies in the presence of strongly connected components (SCCs), since loops may induce an unbounded number of execution paths. The alias analysis addresses this by leveraging the SCC tree decomposition and path enumeration infrastructure provided by the Path Analysis module. Key observations specific to alias analysis:

  • Traversing the same loop path once or multiple times does not change the resulting alias relationships — aliases are determined by value flow, not by iteration count.
  • The top-down recursive SCC traversal enables propagating outer context constraints (e.g., discriminant values established before loop entry) into inner SCCs, pruning unreachable paths early.

The MOP analysis uses postfix_repeat = 0 (each distinct SCC segment appears once) by default, which is sufficient for alias relationships that are idempotent under loop iteration.

In the following, we use a concrete example to demonstrate how path-sensitive SCC handling enables precise alias discovery.

#![allow(unused)]
fn main() {
enum Selector { First, Second }

// Expected alias analysis result: (0, 1) (0, 2)
fn foo(x: *mut i32, y: *mut i32, choice: Selector) -> *mut i32 {
    let mut r = x;
    let mut q = x;

    unsafe {
        while *r > 0 {
            let mut p = match choice {
                Selector::First => y,
                Selector::Second => x,
            };

            loop {
                r = q;
                q = match choice {
                    Selector::First => x,
                    Selector::Second => p,
                };
                *q -= 1;
                if *r <= 1 { break; }
                q = y;
            }

            if *r == 0 { break; }
        }
    }

    r
}
}

The annotated MIR for this function contains approximately 27 basic blocks. The SCC tree has two levels: the outer SCC is dominated by the block checking *r > 0, and a nested inner SCC dominated by the block entering the loop { ... }.

We enumerate paths through the SCC tree in a recursive, top-down manner. A path segment between two occurrences of the same dominator is worth exploring only if it introduces at least one previously unvisited node. For instance, the segment 7 → 8 → 10 → ... → 7 followed by 7 → 9 → 10 → ... → 7 is valuable because the second repetition introduces block 9, which may lead to new alias relationships.

Using postfix_repeat = 0 (each distinct segment appears once), the inner SCC produces 10 structurally distinct paths. The path 7-9-10-21-24-11-20-25-19-13-7-9-10-21-24-11-20-25-19-26 effectively detects the alias relationship between r and y. In contrast, a straightforward DFS-based traversal fails to detect this alias relationship.

The alias analysis adopts a recursive, top-down strategy that propagates accumulated path constraints from outer SCCs inward. When reaching an inner SCC, constraints from the outer context determine which of the enumerated paths are reachable. For each reachable path, the inner SCC subsequence is concatenated with the outer SCC path, and alias analysis continues along the resulting trace.

5.2.2.5 Inter-Procedural Alias Resolution

When encountering a function call in the MIR, alias_bbcall() resolves aliases across function boundaries:

  1. Checks fn_map for an existing callee summary. If found, uses it directly.
  2. If not found, recursively creates a new AliasGraph for the callee, runs find_scc() and process_function_paths(), caches the result, and uses it.
  3. A recursion_set tracks functions currently being analyzed to prevent infinite recursion in the case of mutually recursive functions. If the callee is already in the recursion_set, it is conservatively skipped.
  4. handle_fn_alias() maps callee-formal positions to caller-actual value indices, constructing field projections on-the-fly if the callee's alias references fields not yet materialized in the caller's value graph.

5.2.2.6 Feature: Field Sensitivity

The MOP analysis is field-sensitive — it tracks aliases at the level of struct/tuple fields. This is achieved through:

  • Value projection: Each struct field access creates a Value node with father pointing to the parent value and the field index. The projection() method recursively descends through ProjectionElem::Field, creating field nodes on demand. ProjectionElem::Deref is skipped without materialising a new node, so multi-level pointer aliases are not tracked.
  • sync_field_alias(): When two values are aliased, their corresponding fields are also aliased recursively (up to MAX_FIELD_DEPTH = 10). The total number of value nodes per path is also bounded by MAX_VALUES_PER_PATH = 1000.
  • sync_father_alias(): When a value is aliased, all aliases of its parent receive corresponding field projections, enabling transitive field-level aliasing.
  • Alias compression: After path traversal, compress_aliases() performs field truncation (collapsing multi-level field projections to the first level) and containment merging (removing redundant sub-field aliases when a coarser alias already captures the relationship).

For example:

#![allow(unused)]
fn main() {
struct Point { x: i32, y: i32 }

fn foo(p1: &Point) -> &i32 {
    &p1.y
}
}

The result is (0, 1.1) — the return value aliases with field 1 (y) of the first parameter.

5.2.2.7 Key Steps of the MOP Algorithm

#![allow(unused)]
fn main() {
let mut alias_graph = AliasGraph::new(tcx, def_id);
alias_graph.find_scc();
alias_graph.process_function_paths(&mut fn_map, &mut recursion_set);
let result = alias_graph.ret_alias; // MopFnAliasPairs
}
  1. Create AliasGraph wrapping a PathGraph, extract MIR locals into values, and extract per-block AliasBlockFacts from MIR statements and terminators.
  2. Delegate to PathGraph::find_scc() for hierarchical SCC tree construction.
  3. process_function_paths() walks each path, calling alias_bb() and alias_bbcall() per block, building alias_sets along the way, then merge_results() extracts and compresses the final alias pairs.

Reference

The MOP alias analysis is based on our SafeDrop paper, published in TOSEM:

@article{cui2023safedrop,
  title={SafeDrop: Detecting memory deallocation bugs of rust programs via static data-flow analysis},
  author={Mohan Cui, Chengjun Chen, Hui Xu, and Yangfan Zhou},
  journal={ACM Transactions on Software Engineering and Methodology},
  volume={32}, number={4}, pages={1--21}, year={2023},
  publisher={ACM New York, NY, USA}
}

5.2.3 MFP-Based Alias Analysis

In addition to the MOP approach, RAPx provides an alternative alias analysis implementation based on the MFP (Maximum Fixed Point) framework. The MFP analysis is built on Rust compiler's rustc_mir_dataflow infrastructure, which provides a general-purpose monotone dataflow analysis framework. The implementation lives at rapx/src/analysis/alias_analysis/mfp/.

5.2.3.1 Overview

The MFP approach differs fundamentally from MOP in its analysis strategy:

  • Path insensitivity: Unlike MOP, which explicitly enumerates and analyzes individual execution paths, MFP merges information from all paths at control-flow join points. This means MFP does not track path-specific constraints (e.g., the value of a discriminant variable across branches).

  • Flow sensitivity: Both approaches are flow-sensitive, tracking how alias relationships evolve along the control flow. However, MFP uses a worklist-based fixed-point iteration over the CFG, while MOP performs explicit path enumeration via PathGraph.

  • Precision trade-offs: MFP may produce more conservative (over-approximate) results compared to MOP due to path insensitivity, but it can be more efficient for functions with complex control flow where path enumeration becomes expensive.

Example: Path Insensitivity in MFP

#![allow(unused)]
fn main() {
enum Selector { First, Second }

fn foo<'a>(x: &'a i32, y: &'a i32, choice: Selector) -> &'a i32 {
    let a = match choice {
        Selector::First => x,
        Selector::Second => y,
    };
    match choice {
        Selector::First => a,
        Selector::Second => x,
    }
}
}

MOP Analysis (Path-Sensitive):

  • Path 1: choice = First → a = x → returns a (i.e., x) → alias (0, 1)
  • Path 2: choice = Second → a = y → returns x → alias (0, 1)
  • Result: {(0, 1)} (return value aliases only with parameter x)

MFP Analysis (Path-Insensitive):

  • After the first match: a may alias with either x or y
  • At the second match, both branches are considered reachable:
    • Branch First: returns a, which may be x or y → aliases (0, 1) and (0, 2)
    • Branch Second: returns x → alias (0, 1)
  • Join at the merge point: {(0, 1), (0, 2)} (return value may alias with both x and y)
  • Result: {(0, 1), (0, 2)} (includes spurious alias with parameter y)

The key difference is that MFP loses the correlation between the two match statements, leading to a spurious alias (0, 2) that MOP correctly excludes.

The MFP alias analyzer is implemented in the MfpAliasAnalyzer struct, which also implements the AliasAnalysis trait. Like the MOP approach, MFP analysis is field-sensitive and context-insensitive, supporting inter-procedural analysis through function summaries.

5.2.3.2 Lattice Design

The MFP approach models alias relationships using a lattice-based abstract domain built on the Union-Find (disjoint-set) data structure.

Abstract Domain

The abstract domain AliasDomain represents alias relationships among program places:

#![allow(unused)]
fn main() {
pub struct AliasDomain {
    parent: Vec<usize>,   // Parent array for Union-Find
    rank: Vec<usize>,     // Rank for union-by-rank optimization
}
}

Each place in the program is assigned a unique index, and the Union-Find structure tracks equivalence classes of aliased places. Two places are considered aliased if they belong to the same equivalence class (i.e., they have the same root).

Lattice Structure

The AliasDomain forms a join semi-lattice:

  • Bottom (⊥): The initial state where no aliases exist. Each place is in its own equivalence class: parent[i] = i.
  • Partial Order (⊑): Domain D₁ ⊑ D₂ if every alias pair in D₁ is also present in D₂.
  • Join Operation (⊔): D₁ ⊔ D₂ produces a domain containing all alias relationships from both, implemented by extracting all alias pairs from one domain and unioning them in the other.

Monotonicity and Convergence

The lattice design ensures monotonicity: transfer functions always produce domains that are higher in the lattice. Combined with the finite height of the lattice (bounded by the number of possible alias pairs), the fixed-point iteration is guaranteed to converge.

Union-Find operations: find (O(α(n)) amortized), union (O(α(n)) amortized), where α(n) is the inverse Ackermann function.

5.2.3.3 Transfer Functions

The MFP analysis defines transfer functions for each type of MIR statement and terminator using a Kill-Gen pattern.

Kill-Gen Pattern

For an assignment lv = ...:

  1. Kill: Remove all existing aliases involving lv and its field projections. Implemented via remove_aliases_with_prefix().
  2. Gen: Establish new alias relationships based on the right-hand side.

Assignment: lv = rv

For Copy or Move assignments:

  • Kill lv and all field projections.
  • If rv is a place: union lv with rv, then sync_fields recursively.

Reference Creation: lv = &rv or lv = &raw rv

Creates an alias between the reference lv and the referent rv:

  • Kill old aliases of lv.
  • Union lv with rv, sync fields.

Aggregate Construction: lv = (op₁, op₂, ...)

For tuples and structs, each field is handled individually for field sensitivity:

  • Kill lv and all its fields.
  • For each field i: union lv.i with operand[i], sync fields.

Field Synchronization

When two places are aliased, their corresponding fields are also aliased recursively (up to MAX_SYNC_DEPTH = 3). The sync_fields function iterates over common field indices (0..16) and unions matching fields.

Function Calls: ret = f(args)

  1. Kill: Remove aliases for the return place ret.
  2. Gen: Apply the callee's function summary: map formal parameter indices to actual argument place indices, union the return place with the corresponding argument.

5.2.3.4 Intraprocedural Analysis

The intraprocedural analysis is implemented by FnAliasAnalyzer, which implements rustc_mir_dataflow::Analysis.

PlaceInfo: Field-Sensitive Place Management

PlaceInfo tracks all program places and their properties:

#![allow(unused)]
fn main() {
pub struct PlaceInfo<'tcx> {
    place_to_index: FxHashMap<PlaceId, usize>,
    index_to_place: Vec<PlaceId>,
    may_drop: Vec<bool>,
    need_drop: Vec<bool>,
    num_places: usize,
}
}

Places are represented by the recursive PlaceId:

#![allow(unused)]
fn main() {
pub enum PlaceId {
    Local(usize),                        // A local variable
    Field { base: Box<PlaceId>, field_idx: usize },  // A field projection
}
}

This enables precise tracking of aliases at the field level. During initialization, PlaceInfo::build recursively creates field projections for struct and tuple types, bounded by MAX_FIELD_DEPTH = 5 and MAX_DEREF_DEPTH = 3.

Fixed-Point Iteration

The dataflow analysis uses the standard worklist algorithm:

  • OUT[B] = F_B(IN[B]): Output state = transfer function applied to input.
  • IN[B] = ⊔_{P ∈ pred(B)} OUT[P]: Input state = join of all predecessor outputs.

Iteration continues until a fixed point is reached (no block's output changes).

5.2.3.5 Interprocedural Analysis

The MFP approach achieves inter-procedural precision through function summaries and global fixed-point iteration.

Function Summaries

A function summary captures alias relationships between parameters and the return value as a set of AliasPair instances. Since aliases may be connected through temporary variables, summary extraction performs a transitive closure to identify all parameter-return alias relationships.

The extracted candidates are normalized and filtered:

  • Self-aliases (0, 0) are removed.
  • Prefix-subsumed aliases are removed (e.g., (0, 1) subsumes (0.0, 1.0)).

Global Fixed-Point Iteration

The interprocedural analysis operates in three phases:

  1. Starting from local crate functions, recursively traverse call sites to collect all reachable function DefIds.

  2. All reachable functions start with empty summaries (⊥ or FnAliasPairs::new(arg_count)).

  3. Iterate to fixed point (up to MAX_ITERATIONS = 10):

    • Sync current summaries to shared storage.
    • Re-analyze each function with the latest callee summaries.
    • If no summary changes, convergence is reached.

This outer iteration ensures that when analyzing a function f that calls g, the analysis uses the most up-to-date summary of g.

5.2.4 Quick Usage Guide

# MOP-based alias analysis (default)
cargo rapx analyze alias

# MFP-based alias analysis
cargo rapx analyze alias --mfp

Example output for MOP:

Checking alias_mop_field...
21:50:18|RAP|INFO|: Alias found in Some("::foo"): {(0,1.1),(0,1.0)}
21:50:18|RAP|INFO|: Alias found in Some("::boxed::{impl#0}::new"): {(0.0,1)}

To use analysis results in code:

#![allow(unused)]
fn main() {
// MOP-based approach
let mut alias_analysis = AliasAnalyzer::new(tcx);
alias_analysis.run();
let result = alias_analysis.get_local_fn_alias();
rap_info!("{}", FnAliasMapWrapper(result));
}

#![allow(unused)]
fn main() {
// MFP-based approach
let mut analyzer = MfpAliasAnalyzer::new(tcx);
analyzer.run();
let alias = analyzer.get_local_fn_alias();
rap_info!("{}", FnAliasMapWrapper(alias));
}