russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
150 lines
3.7 KiB
ReStructuredText
150 lines
3.7 KiB
ReStructuredText
rustc — CWE-407 Analysis
|
|
=========================
|
|
|
|
.. contents:: :local:
|
|
|
|
Overview
|
|
--------
|
|
|
|
``rustc`` is the Rust compiler. It performs exhaustiveness checking for match expressions,
|
|
trait specialization graph construction, and type inference. Two CWE-407 defect sites were
|
|
found in the middle-end compiler passes. Both are unpatched.
|
|
|
|
Defect Sites
|
|
------------
|
|
|
|
rustc-0001
|
|
~~~~~~~~~~
|
|
|
|
**File:** ``compiler/rustc_middle/src/ty/inhabited_predicate.rs:109,127``
|
|
|
|
**Pattern:**
|
|
|
|
.. code-block:: rust
|
|
|
|
// Match exhaustiveness — SmallVec membership test during inhabited-predicate DFS
|
|
fn visit_inhabited(
|
|
&self,
|
|
tcx: TyCtxt<'tcx>,
|
|
stack: &mut SmallVec<[Ty<'tcx>; 4]>,
|
|
) -> InhabitedPredicate<'tcx> {
|
|
if stack.contains(&self) { // O(d) — SmallVec::contains is linear scan
|
|
return InhabitedPredicate::True;
|
|
}
|
|
stack.push(self);
|
|
// ... recurse
|
|
stack.pop();
|
|
}
|
|
|
|
**Why this is O(n):** ``SmallVec::contains`` is a linear scan regardless of the SmallVec
|
|
being stack- or heap-allocated; called once per recursive frame.
|
|
|
|
**Complexity:** ``O(d²)`` where d = recursion depth (number of types on the stack)
|
|
|
|
**Patch:**
|
|
|
|
.. code-block:: rust
|
|
|
|
use rustc_data_structures::fx::FxHashSet;
|
|
|
|
fn visit_inhabited(
|
|
&self,
|
|
tcx: TyCtxt<'tcx>,
|
|
stack: &mut FxHashSet<Ty<'tcx>>,
|
|
) -> InhabitedPredicate<'tcx> {
|
|
if !stack.insert(self) { // O(1) — insert returns false if already present
|
|
return InhabitedPredicate::True;
|
|
}
|
|
// ... recurse
|
|
stack.remove(&self);
|
|
}
|
|
|
|
**Data structure change:** ``SmallVec<[Ty; 4]>`` + ``contains`` → ``FxHashSet<Ty>`` + ``insert``
|
|
|
|
**Status:** Unpatched
|
|
|
|
Benchmark Results
|
|
-----------------
|
|
|
|
.. TODO: benchmark pending patch
|
|
|
|
Complexity Proof
|
|
----------------
|
|
|
|
Let d = recursion depth. ``SmallVec::contains`` scans up to d elements: O(d) per call, O(d²)
|
|
total. ``FxHashSet::insert`` returns a boolean indicating first insertion: O(1), O(d) total.
|
|
QED.
|
|
|
|
References
|
|
----------
|
|
|
|
* Defect ticket: ``tools/tickets/defects/rustc-0001.md``
|
|
|
|
rustc-0002
|
|
~~~~~~~~~~
|
|
|
|
**File:** ``compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs:69``
|
|
|
|
**Pattern:**
|
|
|
|
.. code-block:: rust
|
|
|
|
// Specialization graph construction — Vec::position for node lookup
|
|
fn ancestors(
|
|
tcx: TyCtxt<'tcx>,
|
|
trait_def_id: DefId,
|
|
start: DefId,
|
|
) -> Ancestors<'tcx> {
|
|
let mut visited: Vec<DefId> = Vec::new();
|
|
// ...
|
|
loop {
|
|
if visited.iter().position(|&v| v == current).is_some() {
|
|
// cycle detected — O(V) per check
|
|
break;
|
|
}
|
|
visited.push(current);
|
|
// ...
|
|
}
|
|
}
|
|
|
|
**Why this is O(n):** ``Vec::position`` is a linear scan; called on every iteration of the
|
|
specialization-graph traversal loop.
|
|
|
|
**Complexity:** ``O(V²)`` where V = number of specialization ancestors
|
|
|
|
**Patch:**
|
|
|
|
.. code-block:: rust
|
|
|
|
use rustc_data_structures::fx::FxHashSet;
|
|
|
|
fn ancestors(...) -> Ancestors<'tcx> {
|
|
let mut visited: FxHashSet<DefId> = FxHashSet::default();
|
|
loop {
|
|
if !visited.insert(current) { // O(1)
|
|
break;
|
|
}
|
|
// ...
|
|
}
|
|
}
|
|
|
|
**Data structure change:** ``Vec<DefId>`` + ``position`` → ``FxHashSet<DefId>`` + ``insert``
|
|
|
|
**Status:** Unpatched
|
|
|
|
Benchmark Results
|
|
-----------------
|
|
|
|
.. TODO: benchmark pending patch
|
|
|
|
Complexity Proof
|
|
----------------
|
|
|
|
Let V = specialization ancestors. Each iteration calls ``Vec::position`` on a vec of up to V
|
|
elements: O(V). With V iterations: O(V²). ``FxHashSet::insert`` is O(1) amortized: O(V) total.
|
|
QED.
|
|
|
|
References
|
|
----------
|
|
|
|
* Defect ticket: ``tools/tickets/defects/rustc-0002.md``
|