From C to machine code

Start with the program#

We spend the whole semester on one small C file. Here is the function this week is about, in the form its author wrote it:

value[0] = input + 0x01010101u;
value[1] = input + 0x02020202u;
value[2] = input + 0x03030303u;
value[3] = input + 0x04040404u;
value[4] = input + 0x05050505u;
value[5] = input + 0x06060606u;
value[6] = input + 0x07070707u;
value[7] = input + 0x08080808u;

Eight array slots, each getting the argument plus a different constant. Later in the same function each slot is XORed with 0x12345678, then has 0x1337 added, then has 0x1111 subtracted, and finally all eight are XORed together into the return value. No loops, no branches, no calls. You could work out what it returns on paper.

That is the whole point of it. Everything this course shows you happens to a function you could have written in a first-year lab.

“Frozen” is doing real work in that table. Because the source was fixed before anything was built from it, no difference between two of this course’s binaries can be a difference in the program. When the machine code changes, something changed it — and that is the only explanation available. You will not get that luxury on real software.

The compiler’s own version#

A compiler does not go straight from C to machine code. It first rewrites the program into an intermediate representation — a form that is still structured and typed, but much closer to what a machine does. Clang’s is called LLVM IR, and it is the thing every obfuscator in this course except one acts on.

Before you read any: four words.

Now the same two source lines, as the compiler restated them:

value[0] = input + 0x01010101u;
value[1] = input + 0x02020202u;

  %2 = alloca i32, align 4
  %3 = alloca [8 x i32], align 16
  store i32 %0, ptr %2, align 4
  %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
  %7 = load i32, ptr %2, align 4
  %8 = add i32 %7, 33686018
  %9 = getelementptr inbounds [8 x i32], ptr %3, i64 0, i64 1
  store volatile i32 %8, ptr %9, align 4
  %10 = load i32, ptr %2, align 4

What the machine actually gets#

One more step down. The back end turns IR into instructions for a specific processor — choosing which machine instruction implements each IR operation, a step called instruction selection — and a disassembler turns the resulting bytes back into something readable.

Four more words, then the listing.

0000000140001030 <demo_substitution>:
140001030: 48 83 ec 28                 	subq	$0x28, %rsp
140001034: 89 4c 24 24                 	movl	%ecx, 0x24(%rsp)
140001038: 8b 44 24 24                 	movl	0x24(%rsp), %eax
14000103c: 05 01 01 01 01              	addl	$0x1010101, %eax        # imm = 0x1010101
140001041: 89 04 24                    	movl	%eax, (%rsp)
140001044: 8b 44 24 24                 	movl	0x24(%rsp), %eax
140001048: 05 02 02 02 02              	addl	$0x2020202, %eax        # imm = 0x2020202
14000104d: 89 44 24 04                 	movl	%eax, 0x4(%rsp)
140001051: 8b 44 24 24                 	movl	0x24(%rsp), %eax

Each site is three instructions: reload the argument from the stack, add the constant, store it back into the slot. Notice 05 01 01 01 01 — that is add eax, 0x01010101, with the constant you wrote sitting in the instruction stream, backwards.

That is the first useful fact about machine code for an analyst. Constants are landmarks. They are how you find the same computation again after somebody has rearranged everything around it.

The fourth description, and the last two words#

There is one more way to describe this function, and it is the one the second half of the course lives in.

demo_substitution has no branches at all, so its control-flow graph is a single basic block with nothing pointing out of it. That is unusual and it is why this week starts here: with the graph out of the way, the only thing that can change between two versions of this function is the arithmetic.

From week 6 the reverse is true — the arithmetic barely moves and the graph explodes. Holding those two apart is most of the skill.

The counts do not agree, and that is the point#

The same function, measured three ways in the retained build matrix:

LLVM IR instructions in the clean target

155LLVM IR instructions in the clean targetshowcase_matrix_v1 — O0 comparison table

x64 machine instructions in the same function

115x64 machine instructions in the same functionshowcase_matrix_v1 — O0 comparison table

bytes of machine code, first byte to last

467bytes of machine code, first byte to lastshowcase_matrix_v1 — O0 comparison table

machine instructions for the same function at -O1

51machine instructions for the same function at -O1optimization_survival.md

One function; four numbers, all correct. The IR count is higher than the machine count because IR spells out addressing that one x64 instruction does for free. The -O1 count is less than half the -O0 count because at -O0 the compiler reloads the argument from the stack for every single site, and at -O1 it stops bothering.

This is the measurement discipline the rest of the course depends on. Whenever you meet a number about a program, three questions come before believing it: which representation, which counting convention, and against which comparator at which optimisation level.

Where an obfuscator can get in#

You now have all four descriptions, which means you can be told the shape of the whole course. An obfuscator picks one of them to change:

The last column is the one to hold on to. A source-level transformation has to survive the entire compiler after it; an IR-level transformation has to survive the back end; a post-link transformation has no optimiser after it at all. In week 5 we will find that this difference decides whether some transformations exist in the final binary at all.

What a disassembler shows you#

Use the left pane. Find the eight add instructions and the eight xor 12345678h, and notice that they are as regular on screen as they were in the source. A clean -O0 build is nearly a transliteration of the C, which is exactly why it makes a usable comparator and a poor model of real software.

Studio: find a constant, then follow its meaning#

Working from the four files below, and nothing else:

1. Pick one of the eight XOR sites. Locate it in the C, in the IR, and in the disassembly. Write down the line or address of each.
2. Say what the compiler added around it that the author did not write, and why each addition is there. The grey boxes above are enough to answer this.
3. demo_substitution contains more than twenty-four operations. Twenty-four of them are the repeated sites the corpus was designed around; the rest are setup and the final reduction. Mark which is which, and say how you decided.
4. One sentence, to be repeated all semester: what would have to be true for my answer to step 1 to be wrong?

Bring the answers to step 3 and step 4. Step 3 is where people disagree, and the disagreement is the useful part — the corpus documentation says “twenty-four sites” and does not mean “twenty-four instructions”.

• showcase.cthe frozen source, all six functions12 kB
• demo_substitution.llclean LLVM IR for this week's function7 kB
• demo_substitution_disassembly.txtclean x64 disassembly of the same function8 kB
• run_stdout.txtwhat the clean executable prints — the six canonical answers141 B