Week 03 · Block I Representation

Instruction substitution

The oldest trick in the book, applied to twenty-four sites, and largely undone by the compiler backend before anyone tried to analyse it.

Block I · RepresentationStudio 10 March 2027Shape: Side-by-side diff

If the obfuscator expanded every single addition, why can I still see additions in the machine code?

Instruction substitution replaces an operation with a longer sequence that computes the same value. For addition, one of the classic identities is

a + b   ≡   (a + k) + b − k        for any k, modulo 2³²

which is true for every k, costs two extra instructions, and means nothing to a reader who spots the cancelling constant. That is the whole technique. The interesting question is what happens to it on the way to the executable.

One site, before and after

Week 1 introduced SSA — every value named once and never reassigned. That property is what makes the next listing readable: to find out what a pass did, follow the chain of names backwards from whatever gets stored.

clean IR — site 0

one add

  %4 = load i32, ptr %2, align 4
  %5 = add i32 %4, 16843009
  %6 = getelementptr inbounds [8 x i32], ptr %3, i64 0, i64 0
  store volatile i32 %5, ptr %6, align 16

lines 5–8 of 158open demo_substitution.ll(7 kB)

substituted IR — the same site

the identity, with k = 115893687

  %4 = load i32, ptr %2, align 4
  %5 = add i32 %4, 115893687
  %6 = add i32 %5, 16843009
  %7 = sub i32 %6, 115893687
  %8 = add i32 %4, 16843009
  %9 = getelementptr inbounds [8 x i32], ptr %3, i64 0, i64 0
  store volatile i32 %7, ptr %9, align 16

lines 5–11 of 340open target_function.ll(12 kB)

%5 adds the cancelling constant, %6 adds the real one, %7 subtracts the cancelling constant back out, and %7 is what gets stored. Note %8: the pass also emitted the original add i32 %4, 16843009 and then never used it. The unsubstituted operation is sitting right there in the IR as dead code.

Two things follow immediately. First, k is different at every site — the next one uses −2076646197, the one after that uses a zero-subtract form entirely — so pattern-matching one template does not find the others. Second, the dead %8 tells you the pass works by adding a substituted computation beside the original rather than by editing it in place. Which raises the obvious question about what the backend does with a value nobody reads.

The same site, in the executable

substituted x64 — demo_substitution at RVA 0x1070

sites 0, 1 and 2

0000000140001070 <demo_substitution>:
140001070: 48 83 ec 28                 	sub	rsp, 0x28
140001074: 89 4c 24 24                 	mov	dword ptr [rsp + 0x24], ecx
140001078: 8b 44 24 24                 	mov	eax, dword ptr [rsp + 0x24]
14000107c: 05 b7 65 e8 06              	add	eax, 0x6e865b7
140001081: 05 01 01 01 01              	add	eax, 0x1010101
140001086: 2d b7 65 e8 06              	sub	eax, 0x6e865b7
14000108b: 89 04 24                    	mov	dword ptr [rsp], eax
14000108e: 8b 44 24 24                 	mov	eax, dword ptr [rsp + 0x24]
140001092: 2d cb e4 38 84              	sub	eax, 0x8438e4cb
140001097: 05 02 02 02 02              	add	eax, 0x2020202
14000109c: 05 cb e4 38 84              	add	eax, 0x8438e4cb
1400010a1: 89 44 24 04                 	mov	dword ptr [rsp + 0x4], eax
1400010a5: 8b 44 24 24                 	mov	eax, dword ptr [rsp + 0x24]
1400010a9: 31 c9                       	xor	ecx, ecx
1400010ab: 81 e9 03 03 03 03           	sub	ecx, 0x3030303

lines 6–21 of 317open demo_substitution_disassembly.txt(18 kB)

The dead operation is gone: instruction selection dropped it, at -O0, without being asked. What survived is the three-instruction identity — add the cancelling constant, add the real one, sub the cancelling constant — and 0x1010101 is still sitting in plain sight in the middle of it.

Site 2 used a different template: xor ecx, ecx then sub ecx, 0x3030303 then sub eax, ecx, which is “subtract the negation”, and again the real constant is visible.

Coverage, diversity and survival are three things

The retained study measures all three separately, and they disagree.

intended sites expanded in OLLVM SUB's O0 IR: 24 / 24intended sites expanded in OLLVM SUB's O0 IRshowcase_matrix_v1.md
distinct IR template shapes used across those sites (2 XOR, 4 ADD, 3 SUB): 9distinct IR template shapes used across those sites (2 XOR, 4 ADD, 3 SUB)showcase_matrix_v1.md
native instructions in the target, clean to substituted, at O0: 115 → 311native instructions in the target, clean to substituted, at O0selected_metrics.md
intended native operations recognisable again at O1 and above: 24 / 24intended native operations recognisable again at O1 and aboveoptimization_survival.md

Coverage is how many sites the pass touched: all of them, here. Template diversity is how many distinct shapes it used: nine, which is more than one and far fewer than twenty-four. Survival is what is left in the machine code, and this is where it falls apart — the post-pass IR keeps its expanded trees at every optimisation level, and the backend selects native immediate operations for all twenty-four target sites from -O1 onward.

The same three measurements on the other two LLVM-family implementations make the point harder to dismiss:

one implementation transformed XOR 2/8, ADD 4/8 and SUB 6/8 at -O0 — its pass is probabilistic — and by -O1 its measured target is identical to the clean target. Complete loss of the requested treatment.
another transformed XOR 8/8, ADD 8/8 but SUB only 3/8, kept structurally non-native IR at -O1 and above, and still had the backend select native immediate operations for every target site.

Table 03

Arithmetic: complexity can shrink or survive

Optimization acts on the obfuscated program before we inspect its machine code.

Treatment	At O0	At higher optimization	Main lesson
OLLVM SUB	24 IR sites transformed; native XOR/SUB recognizable	WEAKENEDO1+: all 24 native operations reappear	Large IR trees need not survive code generation.
Hikari SUB	Partial coverage; 213 native instructions	REMOVEDO1+: measured target matches clean	Coverage and optimization survival are different.
Polaris SUB	XOR 8/8; ADD 8/8; SUB 3/8 transformed	WEAKENEDO1+: native operations recognizable	Classic SUB is not the stronger MBA treatment.
Tigress EncodeArithmetic	426 native instructions	PERSISTS/Ox: 226 vs 106 clean	Exact same generated C; substantial complexity remains.

IR expansion, native instruction count and semantic difficulty are different measurements.

Target: demo_substitution. Tigress uses MSVC /Ox (recorded as O3); the 106-instruction clean is also /Ox.Open the original lecture figure (SVG)

What the analyst sees

A disassembler diff. The left pane is a regular repeating pattern of add and xor instructions with the immediates 0x1010101 upward and 12345678h. The right pane is longer and irregular, containing add and sub pairs with large cancelling constants, xor ecx ecx, negations, and the original small immediates still visible among them. — Now use both panes. On the right, find the cancelling constants, then find the real ones among them. The technique’s actual cost to an analyst is not difficulty — it is volume, plus the nagging possibility that one of the expansions is not an identity after all.
analysis view — not correctness evidencedemo_substitution1_2.jpg — open for full resolution

This establishes

Classic substitution expanded all 24 intended sites in this specimen's O0 IR, using nine distinct template shapes, and grew the native target from 115 to 311 instructions.
The pass emits the substituted computation alongside the original, which the backend then drops as dead — visible in the retained IR and absent from the retained disassembly.
From -O1 onward, instruction selection recovers all 24 intended native operations for this target, while the post-pass IR keeps its expanded trees.

This does not establish

That IR expansion produces hard machine code. Here it mostly did not, and that is the week's finding.
That a simplifier recovered anything. Nothing was simplified this week — the compiler did it, before any analysis ran.
That these coverage fractions transfer to another program, another seed or another build of the same compiler. The pass in one implementation is probabilistic.
That 311 versus 115 instructions is a measure of difficulty rather than of size.

Templates and coverage from showcase_matrix_v1.mdSurvival from optimization_survival.mdMetric definitions from selected_metrics.md

Studio: follow one operation through the pair

Take one ADD site and one XOR site. For each:

Write the identity the pass used, as algebra, and check it holds modulo 2³².
Find the site in the substituted IR and in the substituted disassembly. Note which IR values are dead.
Say what the backend did between those two files.
Then find the same site in the -O1 metrics and say what is left.

Then the part that carries the marks: write two sentences about what you have established, one of which begins “this does not show that”. A1 is published now and is built from exactly this exercise on a pair you have not seen.

demo_substitution.llclean O0 IR — the comparator7 kB
target_function.llpost-pass substituted IR, all 24 sites12 kB
demo_substitution_disassembly.txtclean x64, AT&T order8 kB
demo_substitution_disassembly.txtsubstituted x64, Intel order18 kB
msynth_validation.mdthe arithmetic study this week's site classifications come from31 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 expand `a + b` into an identity that uses a third constant and cancels it
you can read a four-line SSA chain and say which value is stored
you have week 1's annotated XOR site written down

Instruction substitution

One site, before and after#

The same site, in the executable#

Coverage, diversity and survival are three things#