How rule_ranker's
celf_recompute_gpu.py
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).
load_cracked_universe() reads the target/cracked-password file and
hashes every line with FNV-1a-64
(fast_fnv1a_hash_64), then dedups to a sorted array of unique
fingerprints — with an on-disk fingerprint cache so a re-run against the same
cracked file skips re-hashing entirely. There is no bloom filter anywhere in this
tool; that two-stage prefilter/verify split is specific to the rulest
pipeline, not rule_ranker.
Those fingerprints are built into a GPU-resident open-addressing table
(_build_open_addressing_table, ≤50% load factor, SplitMix64 slot
distribution) once per run. A word is "covered" when its FNV-1a-64 fingerprint
lands in an occupied table slot — coverage is tracked by hash-table slot,
not by a deduplicated integer target-word ID as in rulest. The
project's own docs are explicit that this is a hash table in the ordinary
birthday-bound sense, not a cryptographic or string-exact guarantee.
Every candidate rule is run once against the full (not-yet-covered) wordlist on the GPU and its hit count against the hash table is accumulated with a single atomic counter per rule — not a per-rule array of which words it hit. That count is this rule's monotone upper bound for every later round, since coverage can only shrink from here.
Per the module's own docstring: "nothing shaped (n_rules × cracked_universe) is
ever allocated, in RAM or on disk." There is no size threshold that switches
between an in-memory dict and a disk-backed store — that distinction belongs to
rulest's CoverageStore. Here the only persistent state
between rounds is the active bitmap (which hash-table slots are still
uncovered) and each rule's current upper bound; every gain is recomputed from the
wordlist on demand rather than looked up.
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 million-candidate pools shown in the real run further down this page.
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 lives entirely on the GPU as active_g — a uint32
bitmap over hash-table slots, cleared in place by
apply_and_clear_kernel / clear_recorded_slots_kernel once
a winner is chosen. (This differs from rulest, which tracks its
covered set as a numpy boolean array in host memory with fancy indexing.) The host
only reads active back — via remaining_active_count() — to
report totals; every marginal-gain check happens on-device against the live bitmap.
Selection continues until either the requested --budget is reached, or
the best remaining candidate's gain drops to zero (saturation — no rule left adds
any new coverage). Unlike rulest's selector, this implementation takes
no cost-alpha parameter: there's no depth-based bias toward shorter chains here, and
no optional 1-swap local-search pass after selection — what CELF picks is the final
output.
celf_recompute_gpu.py is a standalone post-processing tool: it takes a
ranker CSV or a plain .rule file already produced by ranker.py
and re-selects it against a target cracked-password list. It never stores a coverage row
for any rule at all, not even one. A single streaming pass computes each rule's exact
full-target score once as a monotone upper bound; after that, every round re-scores
candidates live on the GPU against a shrinking active bitmap, using a GPU
open-addressing hash table for membership tests instead of a per-hit binary search.
Peak state is just O(n_rules) + O(cracked_universe bits): the
active bitmap, the per-rule upper-bound array, and the heap — no dict, no
SQLite file, no coverage matrix in any form. The RANKER_GREEDY_RESCORE_BATCH
env var (default 32) controls how many speculative contenders get rescored together per
round; RANKER_GREEDY_PROFILE=1 logs total rescore counts at the end.
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.
k scored rules out of a stream, unrelated to CELF) uses a plain min-heap
capped at size k — add freely until it's full, then swap in a new entry only
when it beats the current worst one. Simpler than CELF's version because nothing ever needs
to be recomputed, but the same min-heap-as-a-ceiling idea.
Real run, rule_ranker — recompute-GPU + heap path: 1M candidate rules — taken from the
top-scored output of a previous rank run and fed into postprocess/CELF — selected down to a
150,000-rule budget against a 57.2M-entry cracked universe
(hashmob.large.found), with the initial heap built from
hashmob.mini.found upper bounds on an RTX 3060Ti. No coverage matrix was ever
allocated in RAM or on disk; memory stayed at roughly O(n_rules) + O(universe bits)
throughout.
| Stage | Detail |
|---|---|
| Hash table build | 72.5s (vectorized, one-time) |
| Upper-bound pass | 977 batches in 1:55 (8.49 batch/s) |
| Greedy selection | 150,000 rules in 11:49 — avg. 167.3 rules/s |
| Coverage achieved | 35,760,483 / 57,238,127 cracked — 62.47% |
celf_recompute_gpu.py keeps no coverage rows anywhere — not a dict,
not SQLite. Only the active bitmap, each rule's upper bound, and the
heap are kept between rounds; every gain is recomputed live on the GPU instead of
looked up.
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.
RANKER_GREEDY_RESCORE_BATCH (default 32, capped at the rule batch size)
controls how many heap contenders get rescored together once the seed candidate's
bound is beaten — fewer means less speculative GPU work, more means fewer kernel
launches per round.
Heap entries are (-gain, rule_index), where rule_index is a
rule's position in the input list — so equal-gain ties go to whichever rule came
first in --rules-file / --ranking-csv order, deterministically,
with no separate tie-break rule needed. (This differs from rulest, whose
heap entries carry the rule string itself and so tie-break lexicographically.)