Cheat sheets

Binary Analysis Tools from Scratch

Read ELF and Mach-O, decode x86-64, build the CFG, lift to C and prove it. Python stdlib only.

  • Concepts and terms
  • Tasks and commands
  • Annotated code
  • Diagrams
  • Comparisons
  • Troubleshooting
  • Questions and tips

Source

From bytes to checked C#

bytesfunction bytesinstructionsC textstoreObject fileledger.c builtby clangprocessELF readersections,symbols, relaprocessDecoderREX, ModRM, SIBprocessCFGblocks,dominatorsprocessLifterIR, flagsvariableprocessSSAphi, renameprocessSimplifysubstitute, deadcodemodelStructureif, while, dowhilebytesfunction bytesinstructionsC textstoreObject fileledger.c built by clangprocessELF readersections, symbols, relaprocessDecoderREX, ModRM, SIBprocessCFGblocks, dominatorsprocessLifterIR, flags variableprocessSSAphi, renameprocessSimplifysubstitute, dead codemodelStructureif, while, do while

Read an object in Python#

from main import ElfFile, MachOFile, FIXTURES
elf = ElfFile.from_path(FIXTURES / "ledger-x86_64-O1.o")
elf.header.e_shoff, elf.header.e_shnum0x428 and 11 headers
elf.function_span("percent_change")16 bytes at 0x40
elf.function_bytes("percent_change")85 ff 74 09 ...
elf.relocations_for(".text")3 R_X86_64_PC32 records
elf.file_offset_map()3 gaps of alignment
tiny = ElfFile.from_path(FIXTURES / "tiny-x86_64")
tiny.address_to_file_offset(0x4000b0)0xb0 through PT_LOAD
macho = MachOFile.from_path(FIXTURES / "ledger-arm64-O1.o")
macho.function_span("_percent_change")24 bytes at 648

Failures and fixes#

SymptomCauseFix
"percent_change is at 0"st_value used as a file offsetUse sh_offset + st_value - sh_addr, here 0x40
"grade is 48 bytes"Padding 66 90 counted as codest_size is 46. Padding belongs to no symbol
"the table starts at 0x10"Addend read as the target offsetAdd the 4 bytes to the instruction end: 0x14
A plausible listing over a data tableLinear sweep decodes data as codeDescent from the symbol claims no data byte
"jmp rax" and dead blocksIndirect jump with no tableRead targets from .rela.rodata and the bounds check
Decompiler reports a third parameteridivl writes %rdx and the return width is a guessRead before write on an argument register is a parameter

The two projects#

Factorbinary-inspectormini-decompiler
BuildsStatic inspector for ELF, PE/COFF, Mach-ODecompiler for an x86-64 subset
InputELF64 object, COFF object, PE32+ image, Mach-O 64ELF64 ET_REL object built by clang
OutputJSON report, HTML byte map, build diffStructured C and report.json
Runpython3 cli.py inspect <file> --json report.jsonpython3 -m minidec verify <object> --source <source>
CheckFunction starts scored with precision and recallMasked bytes and a behaviour grid
Exit2 with error: <message> on a bad file0 on pass or behaviour-only, else 1

Project commands#

CommandWhat it does
python3 scripts/project_test.py <project> --init learning-artifacts/<project>Makes the workspace. Stage 1 fails on purpose
python3 scripts/project_test.py <project> --all --path learning-artifacts/<project> --strictRuns the cumulative grader
python3 cli.py inspect <stripped> --truth <unstripped> --html report.htmlScores function starts against the unstripped build
python3 cli.py diff <old> <new> --json diff.jsonSection growth, moved symbols, changed imports
python3 -m minidec decompile <object> --ir --no-division-idiomsShows IR and SSA, keeps the magic multiply
python3 -m minidec verify <object> --source <source> --opt O1 --out <dir>Recompiles, compares bytes, runs the grid

Run the lessons#

CommandWhat it does
python3 code/main.py (32)Header, sections, symbols, relocations, map
python3 code/main.py <object> (32)Reads one file. Picks ELF or Mach-O
python3 code/main.py (33)One JSON report for every fixture
python3 code/main.py disasm <object>Listing with relocation targets
python3 code/main.py cfg <object> <function>Analysis of one function
python3 code/main.py (34)IR, SSA, pseudocode next to Ghidra
python3 -m unittest discover -s code/tests -vTest suite of lessons 32 and 34
python3 code/tests/test_main.pyTest suite of lesson 33

ELF64 record formats#

TaskCode
Header after e_ident, offset 16"<HHIQQQIHHHHHH"
Section header, 64 bytes<IIQQQQIIQQ
Symbol, 24 bytes<IBBHQQ
Rela record, 24 bytes<QQq
Program header, 56 bytes<IIQQQQQQ
Symbol index of r_infoELF64_R_SYM(i) is i >> 32
Type of r_infoELF64_R_TYPE(i) is i & 0xffffffff
Mach-O symbol, 16 bytesnlist_64 has no size field

Address arithmetic#

Function bytes
file offset is sh_offset + st_value - sh_addr. Length is st_size.
R_X86_64_PC32
the linker writes S + A - P into the field.
R_X86_64_64
S + A. R_X86_64_PLT32: L + A - P.
RIP target
addend plus 4. .rodata+0x10 on a lea means .rodata+0x14.
PT_LOAD
file offset is p_offset + (address - p_vaddr).
Mach-O size
next symbol in the same section minus this one.
Divide by 10
0x66666667 with shift 34. The error 6 is at most 8.

Sweep or descent: grade at -O0#

FactorLinear sweepRecursive descentDescent with table
Instructions342533
Blocks938
Edges7211
Failuredata decoded as codestops at jmpq *%raxnothing
Use it fororacle agreementwhich bytes runthe full CFG

Analyze a new object#

1Oraclecompare the decoder with llvm-objdump -d first.2Descentwalk from every function symbol. Readunresolved.3Tablesmatch the table idiom and its relocation foreach indirect jump.4Bytesbytes that only the sweep claims are padding ordata.5CFGbuild it with recovered tables. Each back edgeis a loop.

Instruction to IR#

CommandWhat it does
testl %edi, %ediflags = test(edi, edi)
je 0xdif je(flags) goto 0xd else goto 0x4
xorl %eax, %eaxeax = 0
cltdedx = signfill(eax)
movslq %edi, %raxrax = sext64(edi)
sarq $0x22, %rcxrcx = rcx >>s 34
pushq %rbp and frame movesnothing, frame bookkeeping
retqreturn rax

Questions#

Why does the oracle agree with the sweep on the trap?
llvm-objdump is a linear sweep too.
When is an edge a back edge?
Its target dominates its source. It marks a loop.
Why do while in total at -O1?
The header is also the block with the back edge.
Why no jump table in grade at -O1?
Every case returns a constant. A value table replaced the jumps.
Does a behaviour pass prove equivalence?
No. It covers the declared grid on one host.