weir/

reachability_witness.rs

//! Reachability witness  -  bridge between the Tier-3 ProgramGraph
//! forward-reach primitive (`vyre_primitives::ifds_reach_step` driven
//! to fixpoint by the caller) and consumer proof-bundle assembly.
//!
//! ## What this module produces
//!
//! Given:
//! - `source_reach`: a per-node reachability bitmask whose bit `n` is
//!   set iff the *specific source named in the `PathSeed`* reaches
//!   node `n` along some IFDS-eligible path. Per-source masks are
//!   required so that a multi-source taint analysis cannot produce a
//!   witness that mixes paths originating from a different source.
//! - `sanitizer_mask`: a per-node bitmask whose bit `n` is set iff
//!   node `n` is a sanitizer for this rule. The walker rejects any
//!   sanitizer-tagged predecessor so a witness that crosses a
//!   sanitizer is never emitted (audit 2026-04-27 finding 2).
//! - the program-graph CSR (edge_offsets / edge_targets /
//!   edge_kind_mask).
//! - a [`PathSeed`] naming the source and sink stmt-ids.
//!
//! [`extract_path`] walks the CFG **backward** from the sink,
//! greedily choosing a reached, non-sanitized predecessor at each
//! step until the source is hit. The resulting ordered statement
//! list is the path proven by the upstream forward-reach analysis.
//!
//! This is the current host witness explainer for already-computed
//! reachability results. It is retained as oracle/projection logic
//! while the production direction remains GPU-resident reachability
//! and witness materialization; new product reachability work should
//! extend the dispatch path instead of growing host-only analysis here.
//!
//! ## Soundness
//!
//! The walk is greedy: it selects ANY reached, non-sanitized
//! predecessor at each step. That gives one valid path, not
//! necessarily the shortest. For consumer proof-bundling needs
//! (showing the user the chain of statements taint flows through),
//! any valid path is sufficient  -  the existence of A path is what
//! the proof asserts.
//!
//! ## Scope of the upstream analysis
//!
//! The caller's bitmasks can come from the Tier-3 forward-reach
//! primitive (`vyre_primitives::graph::ifds_reach_step`) directly, or
//! from the full exploded-supergraph IFDS solver in `weir::ifds_gpu`
//! after converting `(proc, block, fact)` triples with
//! [`exploded_reachability_to_statement_mask`]. Do not feed raw
//! exploded-supergraph node ids into [`extract_path`]; statement ids
//! and exploded node ids are different namespaces.
//!
//! For a `MayUnder` mode that returns the shortest path or all
//! paths, see `vyre_primitives::graph::shortest_path` /
//! `path_reconstruct`  -  those compose on top of `extract_path`'s
//! output if a rule needs more than one witness.

mod bitmask;
mod conversion;
mod graph;
mod path;

pub use conversion::exploded_reachability_to_statement_mask;
pub use graph::{try_prepare_witness_graph, PreparedWitnessGraph};
#[cfg(any(test, feature = "legacy-infallible"))]
pub use graph::prepare_witness_graph;
pub use path::{
    extract_path, extract_path_prepared, extract_paths_prepared, extract_paths_prepared_into,
    PathExtractionRequest, PreparedWitnessBatchStats,
};

#[cfg(test)]
use vyre_primitives::predicate::edge_kind;

#[cfg(test)]
const MAX_PATH_DEPTH: usize = path::MAX_PATH_DEPTH;

#[cfg(test)]
fn bit_is_set(bitmask: &[u32], i: u32) -> bool {
    bitmask::try_bit_is_set(bitmask, i).expect("test witness bitmask query should be addressable")
}

/// Source-and-sink seed for path extraction. Caller supplies
/// the file + byte offsets it identified from rule firing, and we
/// look them up against the CSR.
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct PathSeed {
    /// Repository-relative file containing the source.
    pub source_file: String,
    /// Source stmt-id (index into pg_nodes).
    pub source_node: u32,
    /// Repository-relative file containing the sink.
    pub sink_file: String,
    /// Sink stmt-id.
    pub sink_node: u32,
}

/// One statement on an extracted path. Mirrors what consumer
/// `proof::PathStatement` carries; this type lives in weir so the
/// witness backends can depend on weir without depending on the downstream consumer.
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct ExtractedStatement {
    /// Source-language adapter id (e.g. `"c-c11"`).
    pub adapter: String,
    /// Brief human-readable description (e.g.
    /// `"call to recv at offset 1142"`).
    pub description: String,
    /// Repository-relative file.
    pub file: String,
    /// Statement node id (index into pg_nodes).
    pub node_id: u32,
    /// Byte range start (inclusive).
    pub byte_start: u32,
    /// Byte range end (exclusive).
    pub byte_end: u32,
}

/// The output of `extract_path`  -  the ordered statement list a path
/// traversed, source → sink.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct ExtractedPath {
    /// Path statements in source-to-sink order.
    pub statements: Vec<ExtractedStatement>,
}

/// Structured validation failures for witness-graph CSR preparation.
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub enum PrepareWitnessGraphError {
    /// `edge_offsets` was not exactly `node_count + 1` entries.
    InvalidOffsetCount {
        /// Actual offset entries.
        offsets: usize,
        /// Required offset entries.
        expected: usize,
    },
    /// `node_count + 1` overflowed the host index type.
    OffsetCountOverflow {
        /// Number of graph nodes.
        nodes: usize,
    },
    /// `edge_targets` and `edge_kind_mask` did not both match final offset.
    EdgeArrayLengthMismatch {
        /// Number of target entries.
        targets: usize,
        /// Number of edge-kind entries.
        kinds: usize,
    },
    /// A CSR edge count or edge offset could not be represented by the host
    /// index type while preparing the reverse witness graph.
    EdgeCountOverflow {
        /// Edge count or edge offset that overflowed host indexing.
        edges: usize,
    },
    /// CSR offsets did not start at zero.
    NonZeroInitialOffset {
        /// Supplied first offset.
        first: u32,
    },
    /// CSR offsets decreased between adjacent rows.
    NonMonotonicOffsets {
        /// Source row whose start exceeded its end.
        source: usize,
        /// Row start offset.
        start: usize,
        /// Row end offset.
        end: usize,
    },
    /// A row end exceeded the final declared edge count.
    OffsetExceedsEdgeCount {
        /// Offset index that exceeded the edge count.
        offset_index: usize,
        /// Offset value.
        offset: usize,
        /// Declared edge count.
        edges: usize,
    },
    /// Reverse CSR edge count overflowed while preparing predecessor rows.
    ReverseEdgeCountOverflow {
        /// Destination node whose incoming edge count overflowed.
        node: usize,
    },
    /// Final CSR offset did not match the supplied edge arrays.
    TerminalOffsetMismatch {
        /// Final offset value.
        terminal: usize,
        /// Supplied edge count.
        edges: usize,
    },
    /// An edge target named a node outside the graph.
    TargetOutOfBounds {
        /// Edge index.
        edge_index: usize,
        /// Target node id.
        target: u32,
        /// Valid node count.
        node_count: u32,
    },
}

/// Distinguishable failure modes for [`extract_path`]. The launch's
/// proof-assembly code maps each variant to a different finding-class
/// outcome; collapsing every error into `None` (the prior shape) hid
/// the depth-overrun case from the caller.
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub enum PathError {
    /// The IFDS analysis did not reach one of the endpoints; no path
    /// exists. Caller should keep the finding at Class 3 (heuristic).
    NoPath,
    /// A reached, non-sanitized predecessor existed at every step but
    /// the chain exceeded `MAX_PATH_DEPTH` before reaching the
    /// source. The partial chain (sink-first, length =
    /// `MAX_PATH_DEPTH`) is returned for diagnostics. Callers must
    /// treat this as an analysis-capacity failure and rerun with a
    /// larger witness budget; returning a downgraded finding would
    /// hide an incomplete proof.
    DepthExceeded {
        /// Sink-first list of statement ids walked before bailing.
        partial_chain: Vec<u32>,
    },
    /// `seed.source_node` or `seed.sink_node` is out of bounds for
    /// the supplied `pg_node_attrs` slice. Returned instead of
    /// panicking on `visited[current]` (audit finding 5).
    NodeOutOfBounds {
        /// The offending node id.
        node: u32,
        /// The valid range upper bound.
        node_count: u32,
    },
    /// The supplied program-graph CSR is malformed. Witness extraction must
    /// fail instead of silently dropping edges, edge kinds, or out-of-range
    /// targets because that can manufacture a proof path that the GPU analysis
    /// did not actually establish.
    MalformedGraph {
        /// Structured reason for the malformed CSR.
        reason: PrepareWitnessGraphError,
        /// Actionable diagnostic describing the malformed CSR field.
        fix: String,
    },
    /// Host staging memory for witness extraction could not be reserved.
    /// Callers must treat this as an analysis-capacity failure, not as proof
    /// that no vulnerable path exists.
    ResourceExhausted {
        /// Staging field whose allocation failed.
        field: String,
        /// Actionable diagnostic describing how to reduce or shard the load.
        fix: String,
    },
}

impl PartialEq<PrepareWitnessGraphError> for PathError {
    fn eq(&self, other: &PrepareWitnessGraphError) -> bool {
        matches!(self, Self::MalformedGraph { reason, .. } if reason == other)
    }
}

/// Distinguishable failures when converting exploded IFDS reachability
/// into the statement-id bitmask consumed by [`extract_path`].
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub enum ExplodedDecodeError {
    /// `blocks_per_proc` was zero, so `(proc, block)` cannot be flattened.
    InvalidShape,
    /// The decoded `(proc, block)` slot was not present in `block_to_statement`.
    BlockOutOfBounds {
        /// Decoded procedure id.
        proc_id: u32,
        /// Decoded block id.
        block_id: u32,
        /// Flattened block slot requested.
        slot: u32,
        /// Number of block slots supplied.
        slot_count: u32,
    },
    /// The block map named a statement outside the caller's statement table.
    StatementOutOfBounds {
        /// Statement id read from `block_to_statement`.
        statement: u32,
        /// Valid statement count.
        statement_count: u32,
    },
}

/// Per-node byte-range and file-index attributes that a consumer
/// pipeline emits alongside the CSR. Lives in this module because
/// path reconstruction is the consumer of these attributes.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct NodeAttr {
    /// Byte range start (inclusive).
    pub byte_start: u32,
    /// Byte range end (exclusive).
    pub byte_end: u32,
    /// Index into the file table.
    pub file_idx: u32,
}

#[cfg(test)]
#[path = "reachability_witness_graph_validation_tests.rs"]
mod reachability_witness_graph_validation_tests;

#[cfg(test)]
#[path = "reachability_witness_tests.rs"]
mod reachability_witness_tests;