Analysis pass Wiki — STIMSMITH

Definition

An analysis pass is the unit of analysis in the Mishegos differential-fuzzing tool. A pass groups together a set of language-agnostic filters that operate on decoder cohort data so that, when chained, they surface a particular class of disagreement between the decoders under test (e.g., libbfd, capstone, zydis, xed). Passes are modeled conceptually after LLVM passes: they are configurable, ordered compositions of small, composable transformations over a common input/output stream.

Structure

A pass is defined by a name and an ordered list of filter identifiers. Passes are stored in the YAML file ./src/analysis/passes.yml. The example below defines the pass same-size-different-decodings, which locates instruction candidates that every worker decoder agrees on in length, but that one or more decoders decode differently:

# Find inputs that all workers agree are one size, but one or more
# decodes differently.
same-size-different-decodings:
- filter-any-failure
- filter-ndecoded-different
- filter-same-effects
- minimize-input
- normalize

The pass is therefore a sequence of filter applications: each filter reads cohorts from STDIN and conditionally writes them to STDOUT, so the next filter in the pass sees only the survivors of the previous one.

Filter composition and ordering

Within a pass, filters may be arranged in two ways:

Dependency graph — filters declare what they need from upstream filters and are topologically scheduled.
Performance heuristics — filters are sorted so that the most expensive or highest-volume filters (e.g., filter-ndecoded-different) run first, reducing the working set for the remaining, cheaper filters.

Individual filters are small Ruby scripts that parse JSON cohorts, apply a predicate or transform, and either drop or rewrite the cohort. A representative filter, filter-ndecoded-different, is shown below:

require "json"

STDERR.puts "[+] pass: filter-ndecoded-different"

count = 0
STDIN.each_line do |line|
  result = JSON.parse line, symbolize_names: true
  outputs_ndecoded = result[:outputs].map { |o| o[:ndecoded] }

  if outputs_ndecoded.uniq.size > 1
    count += 1
    next
  end

  STDOUT.puts result.to_json
end

STDERR.puts "[+] pass: filter-ndecoded-different done: #{count} filtered"

Mutating vs. filtering filters

Passes may mix two kinds of filters:

Filtering filters drop cohorts that do not match their criterion, narrowing the candidate set at each stage.
Mutating filters rewrite the cohort in place. For example, minimize-input truncates the instruction candidate to the longest ndecoded field reported by any decoder, and normalize strips incidental whitespace so subsequent assembly-level diffing is meaningful.

Execution

Passes are launched as a whole through the Mishegos analysis command-line. Each filter logs its progress to STDERR (prefixed with [+] pass: <name>), and the surviving cohorts from the final filter are the pass's output. These outputs can be visualized with the companion tool mishmat, which renders the discrepancies as an HTML table indexed by instruction candidate and per-decoder column:

mishmat -l 10000 < /tmp/mishegos.sd > /tmp/mishegos.sd.html

The -l flag caps the number of rows rendered into the HTML table, which is useful when a pass surfaces a very large number of disagreements.

Example findings produced by passes

Passes defined in passes.yml are the mechanism by which Mishegos produces concrete bug classes such as:

outright decoding failures that prevent downstream tooling or analyst workflows,
size disagreements between decoders,
component discrepancies that mask the recovered control-flow graph, and
semantic differences (e.g., Capstone silently mis-decoding operands or missing instructions entirely).

Relationship to other Mishegos concepts

The pass is the executable object; passes.yml is the declaration of available passes.
An analysis filter is the atomic unit of work; it is PART_OF an analysis pass.
Passes operate on cohort output streamed from prior fuzzing/decoder stages, and they in turn emit cohort output that downstream passes, mishmat, or manual review can consume.

Analysis pass