How rulest's
own selection stage turns a huge pool of candidate rules into a small ruleset that actually
maximizes distinct password recovery — instead of just summing individual rule scores — and
why this consistently beats plain frequency ranking at every budget size.
Sorting candidate rules by raw GPU frequency and taking the top-N is the obvious first
approach, but it optimizes the wrong quantity. Two high-frequency rules can crack almost
the same subset of the target list — keeping both wastes budget that a lower-frequency,
but orthogonal, rule would have spent far better. What actually matters for a
ruleset of size k is not the sum of individual scores, but the size of the
union of everything those k rules recover.
That's a classic set-cover problem: each rule r defines a set
C(r) of the distinct target words it actually cracks, and the goal is to choose
a budget-sized collection of rules whose combined C(r) sets cover as much of
the target universe as possible. Set cover is NP-hard to solve exactly, but the coverage
function is submodular — each additional rule can only add as much or less
than it would have earlier, never more — which is exactly the property that makes a
simple greedy strategy provably close to optimal (within a factor of
1 − 1/e, roughly 63%, of the true best selection).
Every candidate rule is dispatched to the GPU against the full base wordlist using a
fast bloom-filter kernel. This cheaply flags which (rule, base_word)
pairs are probably a hit, without paying the cost of exact string
verification on the entire candidate pool up front.
Bloom filters admit false positives, and a set-cover objective is only meaningful if its universe is the thing actually being maximized. So every bloom-positive pair is re-run through an exact verification kernel, and only outputs that literally match a real target-wordlist entry are kept. This removes bloom false positives before they can distort the optimization.
Each verified hit is mapped to an integer ID in the deduplicated target-word universe, so a rule's coverage is "which distinct target words does this rule actually recover" — not "which base words happened to trigger a bloom hit." This is the same distinction that separates a meaningful cover objective from a proxy that can be gamed.
Each GPU batch's coverage rows are written straight to a coverage store and dropped
from memory immediately after — the full {rule: hits} matrix is never
assembled at once. Below a size threshold this store is a plain in-memory dict (zero
overhead); above it, it's disk-backed, so candidate pools that don't fit in RAM at all
remain usable instead of forcing a smaller run.
The textbook greedy algorithm repeatedly scans every remaining candidate, recomputes
its marginal gain against the current covered set, and picks the best one — then
repeats from scratch. That's O(rules × budget) evaluations, which is
fine at a few thousand candidates but becomes the bottleneck well before 100k, let
alone the 1.7M-candidate pools this pipeline routinely evaluates.
The Cost-Effective Lazy Forward selection algorithm exploits submodularity directly: since a rule's marginal gain can only shrink (never grow) as more of the target universe gets covered, a rule whose gain was already computed doesn't need to be rescanned — it only needs to be re-checked if it reaches the top of a priority queue. Each step pops the current best candidate off a heap, recomputes its gain against the up-to-date covered set, and either accepts it immediately (if it's still the best) or re-inserts it at its corrected priority and pops again.
The covered set is tracked as a single numpy boolean array over the target-word
universe, updated in place with fancy indexing, rather than as Python
set() unions. At 150k–1.7M candidates this avoids repeated hashing and
boxed-integer churn, keeping each marginal-gain check a cheap array operation instead
of an object-heavy one.
Selection continues until either the requested rule budget is reached, or no
remaining candidate adds any new coverage at all (saturation). An optional cost term
(gain / depth^α) can bias the search toward shorter, cheaper rule chains
among candidates with similar marginal gain — pure marginal-coverage greedy is the
α = 0 default.
After greedy selection, an optional local-search pass tries swapping each selected rule for a promising unselected one, accepting the swap only if it strictly increases total recovery. This nudges the result slightly past greedy's own local optimum at very low extra cost, since only a residual candidate pool — not the full candidate set — needs to be re-scored.
CELF is one stage inside the main rulest pipeline
(rulest/selection.py), run right after candidate generation
(token-strip / genetic / chain-building) via --select-mode greedy.
evaluate_full_coverage() streams GPU batches into a
CoverageStore — a Mapping[str, np.ndarray[int32]] that's
a plain dict (InMemoryCoverageStore) below
SELECTION_DISK_THRESHOLD candidates, or a SQLite-backed store with a
512-entry LRU cache above it — and select_rules_by_marginal_coverage()
then runs the CELF heap against whichever store it got, never caring which one.
--select-budgets cuts several prefix files from one greedy ordering
without re-running coverage eval. --local-search hands the CELF output
to local_search_improve() for the optional 1-swap pass (up to
--local-search-swaps attempts over a
--local-search-pool-sized residual pool, refreshed every
--local-search-refresh stale passes). --select-cost-alpha
biases ties toward shorter chains; --exact-recovery just adds reporting,
since greedy coverage is already exact.
Frequency ranking asks "how many hits does this rule get on its own?" Greedy CELF asks
"how many new passwords does this rule recover that nothing already selected
recovers?" Those are different questions, and at every budget size the second one is the
one that actually determines how many unique passwords a ruleset of size k
will crack. The practical result is a ruleset that reaches a given coverage percentage with
dramatically fewer rules — or reaches a much higher coverage percentage at the same rule
count — than a frequency-sorted list ever can, because frequency ranking has no mechanism
to notice or penalize redundancy between rules.
Python's built-in heapq only knows how to be a min-heap — it
always hands you back the smallest item first. CELF wants the opposite: the rule
with the biggest possible remaining gain. The trick is to store every candidate's
bound as a negative number, (-gain, rule_index). The biggest
gain becomes the most negative number, which is exactly what a min-heap pops first — so a
min-heap storing negated scores behaves like a max-heap of gains, without needing a
separate max-heap implementation. The second item in the tuple, rule_index,
is just there to break ties the same way every time (lower index wins).
Every candidate's first number isn't a guess — it's its exact score against the whole target list, computed once in an upfront GPU pass. Because coverage is submodular (a rule can only recover fewer new words later, never more, once other rules have already covered part of the list), that first score is guaranteed to be the most that rule could ever still be worth. It's a safe-to-trust ceiling, not a real-time estimate.
Picking each rule then works like this: pop the top of the heap, and actually recompute its gain against what's been covered so far. If no other rule left in the heap could possibly beat that number — because even their best-case ceiling is lower — that rule is the correct pick, full stop, no need to check anyone else. If some other rule's ceiling could still win, recompute a small batch of those too, keep whichever came out on top, and drop the rest back into the heap with their freshly tightened (and now lower) ceilings. Rules that turn out to add nothing are thrown away for good. Most of the heap is never touched in a given round — that's what makes CELF fast: it skips rescoring every candidate it can already prove loses, while still picking exactly the same rule plain greedy would have picked.
Single-run results on base = hashmob.mini, target = hashmob.medium.
Each pair below holds ruleset size fixed and compares greedy CELF selection against plain
frequency ranking.
| Ruleset | Cover | Size | Efficiency |
|---|---|---|---|
| rulest.greedy.150000.rule | 36.12% | 150,000 | 0.2408 |
| rulest.freq.150000.rule | 28.02% | 150,000 | 0.1868 |
| rulest.greedy.50000.rule | 29.78% | 50,000 | 0.5956 |
| rulest.freq.50000.rule | 20.25% | 50,000 | 0.4050 |
| rulest.greedy.25000.rule | 24.91% | 25,000 | 0.9964 |
| rulest.freq.25000.rule | 15.99% | 25,000 | 0.6396 |
| rulest.greedy.10000.rule | 19.71% | 10,000 | 1.971 |
| rulest.freq.10000.rule | 11.44% | 10,000 | 1.144 |
| rulest.greedy.1500.rule | 10.45% | 1,500 | 6.9667 |
| rulest.freq.1500.rule | 4.61% | 1,500 | 3.0733 |
| rulest.greedy.250.rule | 5.06% | 250 | 20.24 |
| rulest.freq.250.rule | 1.73% | 250 | 6.92 |
| rulest.greedy.64.rule | 2.10% | 64 | 32.8125 |
| rulest.freq.64.rule | 0.88% | 64 | 13.75 |
Below SELECTION_DISK_THRESHOLD candidates, coverage is kept in
InMemoryCoverageStore — a plain dict, zero overhead. Above it,
CoverageStore (SQLite + a 512-entry LRU cache in front of point
lookups) takes over so pools far larger than available RAM stay usable; point
lookups cost roughly one order of magnitude more, negligible next to the
GPU-bound evaluation phase it follows.
A fixed budget stops selection at exactly k rules. Leaving it unset runs to
saturation — every rule that can still add coverage gets added, useful for finding the
practical ceiling of a candidate pool before picking a production budget.
Raising cost_alpha above 0 divides marginal gain by chain depth raised to
that power, nudging ties toward shorter, cheaper rules — useful when hashcat runtime per
candidate matters as much as raw coverage.
Raw GPU frequency is accepted as a tie-breaker input but has no effect on final ordering — the heap's own tuple comparison already decides ties deterministically by rule string, independent of any pre-sort.