Week 11 · Block IV Limits

Lifting machine code back to LLVM IR

One tool, one afternoon, two verdicts. Sixty-eight verifier-clean LLVM modules, one of which miscomputes 3,917 of 4,118 inputs — and the fold that did it is four operators long.

Block IV · LimitsStudio 19 May 2027Shape: Two verdicts, one tool

The lifted IR verifies, recompiles and is smaller than the machine code. Is it right?

Lifting runs the pipeline backwards. Take a compiled function, translate each instruction into an intermediate representation with defined semantics, and you have something an optimiser can simplify, a solver can reason about, and a person can read.

It is the most appealing idea in the field, and week 11 exists because of what that appeal does to your judgement.

The study

totals.json — the whole lifting study

read line 3 against line 8

{
  "cases": 17,
  "verified_modules": 68,
  "recompiled_modules": 68,
  "executed_stages": 51,
  "passing_runtime_stages": 47,
  "failing_runtime_stages": 4,
  "passing_cases": 13,
  "failing_cases": 1,
  "total_lift_runtime_vectors": 218334
}

11 linesopen totals.json(256 B)

Seventeen functions lifted. Four stage variants each, so sixty-eight modules, and every one of the sixty-eight passed the LLVM verifier and recompiled. Fifty-one stages were actually executed against test vectors — 218,334 vectors in total — and forty-seven passed.

Thirteen cases passed under their documented runtime contracts. One case failed. Two bogus-control-flow lifts were never executed as lifts, because they contained unknown helper calls and memory accesses with no safe contract to run them under; and the post-link lane stayed static-only, because nothing it produced ran in the first place.

Note what “68 verified modules” is a fact about. It is a fact about well-formedness.

Four stages, two paths

The stage names matter, because reading them as one chain leads to a wrong conclusion about where a bug came from.

The four retained stages

two alternative paths from R, not one chain

Stage	What it is
R	the raw lift — which already performs folding of its own
R2	R, plus ordinary LLVM `-O2`
M	R, plus the lifter’s own internal optimiser
M2	M, plus ordinary LLVM `-O2`

Stage definitions from mergen_validation.md

So there are two branches from R — R → R2 and R → M → M2 — and they are alternatives, not a four-step sequence. If a defect is present in R, it is present before either branch, and neither ordinary optimisation nor the lifter’s own can be blamed for introducing it or expected to remove it.

The case that passes

That is a genuine success and worth being precise about. An earlier expression-extraction attempt on this same function gave up: it hit a 20,000-node AST occurrence guard at 25,384 occurrences. The lifter produced a compact, executable whole-function representation of it in 47 milliseconds. Different tools, different representations, and this one scaled where the other did not.

And then read the residue. M still contains 372 arithmetic and Boolean instructions where the clean build’s equivalent is a short scalar expression. Some constants are recognisable; hundreds of multiply, add and Boolean operations with coefficients are not. This is successful lifting with runnable partial simplification — not MBA elimination, and not recovered source.

One detail to head off a misreading: M2 contains thirteen call instructions, and they are LLVM vector-reduction intrinsics introduced by vectorisation, not unresolved calls into the original binary.

The case that does not

the record

same count at every stage

      "stage": "raw",
      "cases": 4118,
      "mismatches": 3917,
      "first_mismatches": [
        {
          "index": 0,
          "x": 0,
          "y": 0,
          "expected": 134756360,
          "actual": 0
        },
        {
          "index": 1,
          "x": 1,

lines 15–28 of 606open semantic_result.json(12 kB)

what the lift produced

the shape is the bug

  %0 = trunc i64 %RCX to i32
  %1 = icmp eq i32 %0, -16843009
  %2 = icmp eq i32 %0, -33686018
  %3 = icmp eq i32 %0, -50529027
  %4 = icmp eq i32 %0, -67372036
  %5 = icmp eq i32 %0, -84215045
  %6 = icmp eq i32 %0, -101058054
  %7 = icmp eq i32 %0, -117901063
  %8 = icmp eq i32 %0, -134744072
  %lola = select i1 %3, i32 305420446, i32 -305419347
  %lola.1 = select i1 %5, i32 305420446, i32 -305419347
  %lola.2 = select i1 %6, i32 305420446, i32 -305419347
  %lola.3 = select i1 %8, i32 305420446, i32 -305419347
  %lol = select i1 %1, i32 -1970176605, i32 1970179728
  %lol.1 = select i1 %2, i32 -1970176605, i32 1970179728
  %realxor = xor i32 %lol, %lol.1
  %realxor.1 = xor i32 %realxor, -1
  %realand = and i32 %lola, %realxor.1
  %lol.2 = select i1 %3, i32 -305421535, i32 305418258
  %realand.1 = and i32 %realxor, %lol.2
  %realor = or i32 %realand, %realand.1
  %lol.3 = select i1 %4, i32 -2001409476, i32 2001410319

lines 7–28 of 54open internal_O2.ll(3 kB)

At x = 0 the function should return 0x08083808. The lift returns 0. Then look at the IR: eight icmp eq comparisons of the argument against eight specific constants, feeding a cascade of select instructions. A function that adds constants to its argument has become a function that asks whether its argument is one of eight particular values.

Forty-five instructions. Smaller than the machine code, readable, verifier clean, and wrong for 95% of its inputs.

Where it came from

The cause is identifiable in the lifter’s source without patching anything. Its operand utilities fold

(~A & B) | (A & C)   →   select(A, C, B)

when the known-bits extrema of A are zero and all-ones. That is a legitimate rewrite when A really is a mask that is either all-zeros or all-ones. But an unconstrained integer also has those extrema, and having them does not make A a mask.

A = 0 or A = −1

fold is sound

Which is the case the rewrite was written for, and it is common in compiled comparison code.

Reading: A is a genuine mask; select is exactly equivalent.

A = 1, B = 0, C = 2

fold is wrong

(~1 & 0) | (1 & 2) is 0 | 0 = 0. select(1 ≠ 0, 2, 0) is 2.

Reading: Bitwise gives 0; the select gives 2. One counterexample, three small integers.

The emitted %selectEZ… values and the propagated select chain in the IR above are consistent with exactly that fold. Three points of discipline about that sentence:

It is a diagnosis, not a repair. No fix was applied and no retest was run, so this is a strongly supported explanation and not a verified one.
The obfuscator is not at fault. The native binary passes all 4,118 vectors. The error appears only in the lift.
LLVM is not at fault. R already fails. Ordinary -O2 did not introduce this and could not have removed it — an optimiser preserves the semantics of the IR it is given, including wrong semantics.

lifted modules verifier-clean and recompilable: 68 / 68lifted modules verifier-clean and recompilabletotals.json
of 17 cases with passing runtime outcomes under their contracts: 13of 17 cases with passing runtime outcomes under their contractstotals.json
inputs miscomputed by the failing case, at all four stages: 3,917 / 4,118inputs miscomputed by the failing case, at all four stagessemantic_result.json
operators in the fold that caused it: 4operators in the fold that caused itmergen_validation.md

A structural aside worth having

The same lifter was pointed at both a flattened function and the working unflattened rewrite of it from week 10:

lifted from the flattened original

the dispatcher survives into the IR

; ModuleID = 'E:\Workspace\seeing_through_obfuscation\results\deobfuscation\mergen\fla\ollvm_original\lift\output.ll'
source_filename = "lifter_module"

; Function Attrs: nofree norecurse nosync nounwind memory(none)
define i64 @main(i64 %RAX, i64 %RCX, i64 %RDX, i64 %RBX, i64 %RSP, i64 %RBP, i64 %RSI, i64 %RDI, i64 %R8, i64 %R9, i64 %R10, i64 %R11, i64 %R12, i64 %R13, i64 %R14, i64 %R15, ptr nocapture readnone %EIP, ptr nocapture readnone %memory, i128 %XMM0, i128 %XMM1, i128 %XMM2, i128 %XMM3, i128 %XMM4, i128 %XMM5, i128 %XMM6, i128 %XMM7, i128 %XMM8, i128 %XMM9, i128 %XMM10, i128 %XMM11, i128 %XMM12, i128 %XMM13, i128 %XMM14, i128 %XMM15) local_unnamed_addr #0 {
entry:
  %0 = trunc i64 %RCX to i32
  %realand = and i32 %0, 1
  %zeroflag25.not = icmp eq i32 %realand, 0
  %lol = select i1 %zeroflag25.not, i32 605478433, i32 -1606921101
  br label %bb1

bb1:                                              ; preds = %bb1.backedge, %entry
  %stackmemory719.sroa.33.0 = phi i32 [ undef, %entry ], [ %stackmemory719.sroa.33.0.be, %bb1.backedge ]

lines 1–14 of 132open internal_O2.ll(8 kB)

lifted from the unflattened rewrite

no dispatcher to lift

; ModuleID = 'E:\Workspace\seeing_through_obfuscation\results\deobfuscation\mergen\fla\ollvm_unflattened\lift\output.ll'
source_filename = "lifter_module"

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none)
define i64 @main(i64 %RAX, i64 %RCX, i64 %RDX, i64 %RBX, i64 %RSP, i64 %RBP, i64 %RSI, i64 %RDI, i64 %R8, i64 %R9, i64 %R10, i64 %R11, i64 %R12, i64 %R13, i64 %R14, i64 %R15, ptr nocapture readnone %EIP, ptr nocapture readnone %memory, i128 %XMM0, i128 %XMM1, i128 %XMM2, i128 %XMM3, i128 %XMM4, i128 %XMM5, i128 %XMM6, i128 %XMM7, i128 %XMM8, i128 %XMM9, i128 %XMM10, i128 %XMM11, i128 %XMM12, i128 %XMM13, i128 %XMM14, i128 %XMM15) local_unnamed_addr #0 {
entry:
  %0 = trunc i64 %RCX to i32
  %realand = and i32 %0, 1
  %zeroflag1 = icmp eq i32 %realand, 0
  br i1 %zeroflag1, label %bb1, label %bb2

bb1:                                              ; preds = %entry
  %realand.1 = and i32 %0, 256
  %zeroflag10 = icmp eq i32 %realand.1, 0

lines 1–14 of 88open internal_O2.ll(4 kB)

Lifting does not undo flattening — the state machine is faithfully represented, because that is what the machine code does. Structural recovery has to happen at the binary level, before or instead of lifting. The two outputs are alternative representations of two different binaries, not a before-and-after of one deobfuscation.

Table 06

What does each deobfuscator actually produce?

Expression recovery, a branch proof, LLVM IR and a rewritten PE are different outputs.

Workflow	Input / idea	Delivered result	Boundary to remember
msynth AST/oracle	Extracted expression; rewrite / match	Simpler expression	No rewritten PE in this study.
SiMBA	Algebraic MBA simplification	Simpler expression	Partial reduction is not full recovery.
Synthesizer	Search for a small expression	Candidate expression	Accept only after equivalence proof.
ollvm-unflattener	Discover states; recover successors	Rewritten PE or failure	A produced PE can have wrong semantics.
Triton DSE/SMT	Symbolic branch conditions	Proof / witness	Analysis itself does not patch the PE.
Proof-driven rewriter	Consume proofs and exact bytes	Patched PE	Predicates and dead bytes can remain.
Mergen	Lift x64 instructions	LLVM IR	Valid IR can silently miscompute.
Ordinary LLVM O2	Optimize retained or lifted IR	Optimized IR	Cannot repair an unsound lift.

Ask two questions: what representation was recovered, and how was its correctness checked?

PE = Windows Portable Executable. The Mergen test harness is not a rewritten original PE.Open the original lecture figure (SVG)

This establishes

All 68 lifted modules across 17 cases were verifier-clean and recompilable, and 13 of the 17 cases had passing runtime outcomes under their documented contracts.
The MBA case matches all 4,118 vectors at every stage while retaining substantial residual arithmetic — 372 arithmetic and Boolean instructions in the internal stage.
The substitution case miscomputes 3,917 of 4,118 inputs at all four stages, with the defect already present in the raw lift, and its native input passes.
An unsound (~A & B) | (A & C) to select fold, justified by known-bits extrema, is consistent with the emitted IR and is refuted by A = 1, B = 0, C = 2.

This does not establish

That the lifter is unusable. Thirteen of seventeen cases passed, and one of them scaled where a different extractor had given up.
That the fold has been confirmed as the cause. It was diagnosed from the source and the emitted IR; no fix was applied and no retest was run.
That ordinary LLVM optimisation caused or could repair the failure. The raw lift is already wrong.
That any of this produced a rewritten original executable. It did not — the recompiled validation harness is a different artefact.
That the passing 4,118 vectors prove equivalence. Side-effect equivalence was explicitly not claimed, and the record says so.

Lifting study: mergen_validation.mdTotals: totals.json

Studio: two verdicts from one tool

Draw the two stage paths. Then say, for the failing case, which stage the defect is in and what that rules out.
In the failing IR, find the eight icmp eq comparisons and say what the original function did with those eight constants. Explain in one sentence how a chain of additions became a chain of equality tests.
Evaluate (~A & B) | (A & C) and select(A, C, B) for A = 1, B = 0, C = 2. Then find a second counterexample of your own.
For the passing case, compare the four instruction counts and the residual arithmetic. Write the sentence that correctly reports it — including what it did not recover.
Then the capstone rehearsal. For each of the two cases, name the level the claim was validated at, and the level it was not.

totals.json17 cases, 68 modules, 51 executed stages, 218,334 vectors256 B
semantic_result.jsonthe failing case: per-stage mismatch counts and the first mismatches12 kB
raw_O2.llthe raw lift plus ordinary O2 — already wrong4 kB
internal_O2.ll45 instructions, verifier clean, wrong3 kB
semantic_result.jsonthe passing case: 4,118 vectors at each stage, zero mismatches920 B
ir_metrics.json6,689 → 386 → 375 → 359, with operator histograms5 kB
internal_O2.llthe passing lift's IR — note what is still in it18 kB
cases.jsonall 17 cases: stages, contracts, and why two were not executed39 kB
mergen_validation.mdthe study, including the source-level diagnosis of the fold32 kB

Come to the studio with

The studio assumes you have done these. Each is written so you can tell whether you have, without asking.

you can read LLVM IR with `select`, `icmp` and bitwise operators
you can evaluate `(~A & B) | (A & C)` for small values of A, B and C
you have week 10's verdict on the incorrect rewrite written down

Lifting machine code back to LLVM IR

The study#

Four stages, two paths#

The case that passes#

The case that does not#

Where it came from#

A structural aside worth having#