angr.analyses.decompiler.pattern_match.align

Fuzzy common-substring discovery over a token stream.

The algorithm is sparse local self-alignment, the BLAST/MUMmer family:

  1. Seed – index every k-gram of the token stream. Buckets whose multiplicity exceeds max_seed_multiplicity are masked out; without this low-complexity filter, ubiquitous tokens generate a quadratic number of seed pairs. Optional winnowing (Schleimer et al., SIGMOD’03) keeps only the minimum hash in each window of window consecutive k-grams, which thins the seed set while still guaranteeing that any exact match of length >= k + window - 1 produces a seed.

  2. Chain – every seed pair (i, j) votes for diagonal d = j - i. Per diagonal the seed positions are cut into runs separated by more than max_gap, and runs on nearby diagonals are fused only when they really overlap (see _merge_diagonals()).

  3. Align – each candidate is refined by a banded Smith-Waterman with affine gaps over the substitution model, yielding exact boundaries and an identity ratio. The band absorbs indels, so a repeat whose seeds landed on two diagonals is still recovered as a single match.

  4. Cluster – surviving alignments are merged into groups of >= 2 occurrences by union-find over overlapping intervals, then de-overlapped by a weight-maximizing interval-scheduling pass.

Everything here is pure: it operates on lists of integer token ids and knows nothing about angr. finder supplies the ids.

class angr.analyses.decompiler.pattern_match.align.Interval

Bases: object

A half-open token range [start, end).

start: int
end: int
overlaps(other)
Return type:

bool

Parameters:

other (Interval)

overlap_len(other)
Return type:

int

Parameters:

other (Interval)

__init__(start, end)
Parameters:
Return type:

None

class angr.analyses.decompiler.pattern_match.align.Alignment

Bases: object

One fuzzy match between two token ranges.

a: Interval
b: Interval
score: float
matched: int
columns: int
property identity: float
__init__(a, b, score, matched, columns)
Parameters:
Return type:

None

class angr.analyses.decompiler.pattern_match.align.PatternCluster

Bases: object

A group of occurrences of one fuzzy pattern.

occurrences: list[Interval]
score: float
identity: float
alignments: list[Alignment]
property size: int
property savings: float

every occurrence but one disappears.

Type:

Tokens removed by outlining

spans()
Return type:

list[Interval]

__init__(occurrences, score, identity, alignments=<factory>)
Parameters:
Return type:

None

class angr.analyses.decompiler.pattern_match.align.AlignParams

Bases: object

Knobs for the whole pipeline.

k: int = 4
window: int = 0
max_seed_multiplicity: int = 80
min_anchors: int = 4
max_gap: int = 30
band: int = 16
pad: int = 40
match: float = 3.0
klass_match: float = 1.0
mismatch: float = -2.0
gap_open: float = -4.0
gap_extend: float = -1.0
min_score: float = 40.0
min_identity: float = 0.5
min_size: int = 8
min_occurrences: int = 2
max_candidates: int = 4000
overlap_ratio: float = 0.5
allow_tandem: bool = False
min_votes: int = 5

a diagonal needs this many statements of the template voting for it to be aligned, or a quarter of the template’s concrete statements if that is fewer, so small templates are never pruned

Type:

template search

__init__(k=4, window=0, max_seed_multiplicity=80, min_anchors=4, max_gap=30, band=16, pad=40, match=3.0, klass_match=1.0, mismatch=-2.0, gap_open=-4.0, gap_extend=-1.0, min_score=40.0, min_identity=0.5, min_size=8, min_occurrences=2, max_candidates=4000, overlap_ratio=0.5, allow_tandem=False, min_votes=5)
Parameters:
Return type:

None

class angr.analyses.decompiler.pattern_match.align.ScoreModel

Bases: object

Substitution score between two shape ids.

__init__(klass_of_shape, params, glue=frozenset({}))
Parameters:
glue

control glue between blocks, which neither makes two stretches of code alike nor keeps them apart

Type:

shape ids of unconditional jumps

angr.analyses.decompiler.pattern_match.align.find_seeds(ids, params, segment=None, glue=frozenset({}))

k-gram index, low-complexity-masked and optionally winnowed. With segment, a k-gram that crosses from one segment into another is not a seed; nor is one made of unconditional jumps alone.

Return type:

dict[tuple[int, ...], list[int]]

Parameters:
angr.analyses.decompiler.pattern_match.align.chain_seeds(buckets, params, segment=None)

Group seed pairs by diagonal and cut them into colinear runs. With segment, a run also ends where either copy would cross into another segment.

Returns (diagonal, start, end, anchors) candidates, where [start, end) is the range in the first (lower-index) copy.

Return type:

list[tuple[int, int, int, int]]

Parameters:
angr.analyses.decompiler.pattern_match.align.banded_sw(ids, a0, a1, b0, b1, band, score, params, checkpoint=None)

Banded local alignment with affine gaps, restricted to |i - j| <= band.

Two unconditional jumps (score.glue) lined up score nothing, and such a column counts toward neither the matched columns nor the columns. Skipping one is free when the statements after it on both sides are equal, and costs the usual gap otherwise: free skips everywhere let an alignment run on from one copy into the next, since reverse post-order often places copies side by side.

Return type:

Alignment | None

Parameters:
angr.analyses.decompiler.pattern_match.align.refine_candidates(ids, candidates, score, params, checkpoint=None, segment=None)

Run banded Smith-Waterman on every chained candidate and keep the good ones. With segment, each copy’s window is clipped to the segment its seed lies in.

Return type:

list[Alignment]

Parameters:
angr.analyses.decompiler.pattern_match.align.cluster_alignments(alignments, params)

Merge pairwise alignments into groups of >= min_occurrences occurrences.

Alignments are clustered separately per length class (powers of two). Clustered together, a long alignment that runs through several neighbouring copies absorbed the short alignments of each copy: its interval replaced theirs, and one family came out with a few long occurrences instead of many short ones.

Return type:

list[PatternCluster]

Parameters:
angr.analyses.decompiler.pattern_match.align.select_disjoint(clusters, overlap_ratio=0.25)

Greedily pick the highest-savings clusters whose occurrences do not collide.

Repeat finding legitimately reports the same code at several granularities (the whole inlined region, and the hot loop inside it). Outlining needs one decision per token, so callers that want to rewrite the graph take this subset while keeping the full list for reporting.

Return type:

list[PatternCluster]

Parameters:
angr.analyses.decompiler.pattern_match.align.discover(ids, klass_of_shape, params=None, checkpoint=None, segment=None, glue=frozenset({}))

Full pipeline: seed -> chain -> align -> cluster. checkpoint is called from the alignment loops, where the time goes; see priority.Checkpoint. segment gives each token a segment number that no occurrence may cross out of, and glue the shape ids of unconditional jumps, which score nothing and cost nothing to skip.

Return type:

list[PatternCluster]

Parameters: