courgette/description.html

   1 <h1>Courgette Internals</h1>
   2
   3 <h2>Patch Generation</h2>
   4
   5 <p><img src="generation.png" alt="Patch Generation" title="" /></p>
   6
   7 <ul>
   8 <li><p>courgette_tool.cc:GenerateEnsemblePatch kicks off the patch
   9 generation by calling ensemble_create.cc:GenerateEnsemblePatch</p></li>
  10 <li><p>The files are read in by in courgette:SourceStream objects</p></li>
  11 <li><p>ensemble_create.cc:GenerateEnsemblePatch uses FindGenerators, which
  12 uses MakeGenerator to create
  13 patch_generator_x86_32.h:PatchGeneratorX86_32 classes.</p></li>
  14 <li><p>PatchGeneratorX86_32's Transform method transforms the input file
  15 using Courgette's core techniques that make the bsdiff delta
  16 smaller.  The steps it takes are the following:</p>
  17
  18 <ul>
  19 <li><p><em>disassemble</em> the old and new binaries into AssemblyProgram
  20 objects,</p></li>
  21 <li><p><em>adjust</em> the new AssemblyProgram object, and</p></li>
  22 <li><p><em>encode</em> the AssemblyProgram object back into raw bytes.</p></li>
  23 </ul></li>
  24 </ul>
  25
  26 <h3>Disassemble</h3>
  27
  28 <ul>
  29 <li><p>The input is a pointer to a buffer containing the raw bytes of the
  30 input file.</p></li>
  31 <li><p>Disassembly converts certain machine instructions that reference
  32 addresses to Courgette instructions.  It is not actually
  33 disassembly, but this is the term the code-base uses.  Specifically,
  34 it detects instructions that use absolute addresses given by the
  35 binary file's relocation table, and relative addresses used in
  36 relative branches.</p></li>
  37 <li><p>Done by disassemble:ParseDetectedExecutable, which selects the
  38 appropriate Disassembler subclass by looking at the binary file's
  39 headers.</p>
  40
  41 <ul>
  42 <li><p>disassembler_win32_x86.h defines the PE/COFF x86 disassembler</p></li>
  43 <li><p>disassembler_elf_32_x86.h defines the ELF 32-bit x86 disassembler</p></li>
  44 </ul></li>
  45 <li><p>The Disassembler replaces the relocation table with a Courgette
  46 instruction that can regenerate the relocation table.</p></li>
  47 <li><p>The Disassembler builds a list of addresses referenced by the
  48 machine code, numbering each one.</p></li>
  49 <li><p>The Disassembler replaces and address used in machine instructions
  50 with its index number.</p></li>
  51 <li><p>The output is an assembly_program.h:AssemblyProgram class, which
  52 contains a list of instructions, machine or Courgette, and a mapping
  53 of indices to actual addresses.</p></li>
  54 </ul>
  55
  56 <h3>Adjust</h3>
  57
  58 <ul>
  59 <li><p>This step takes the AssemblyProgram for the old file and reassigns
  60 the indices that map to actual addresses.  It is performed by
  61 adjustment_method.cc:Adjust().</p></li>
  62 <li><p>The goal is the match the indices from the old program to the new
  63 program as closely as possible.</p></li>
  64 <li><p>When matched correctly, machine instructions that jump to the
  65 function in both the new and old binary will look the same to
  66 bsdiff, even the function is located in a different part of the
  67 binary.</p></li>
  68 </ul>
  69
  70 <h3>Encode</h3>
  71
  72 <ul>
  73 <li><p>This step takes an AssemblyProgram object and encodes both the
  74 instructions and the mapping of indices to addresses as byte
  75 vectors.  This format can be written to a file directly, and is also
  76 more appropriate for bsdiffing.  It is done by
  77 AssemblyProgram.Encode().</p></li>
  78 <li><p>encoded_program.h:EncodedProgram defines the binary format and a
  79 WriteTo method that writes to a file.</p></li>
  80 </ul>
  81
  82 <h3>bsdiff</h3>
  83
  84 <ul>
  85 <li>simple_delta.c:GenerateSimpleDelta</li>
  86 </ul>
  87
  88 <h2>Patch Application</h2>
  89
  90 <p><img src="application.png" alt="Patch Application" title="" /></p>
  91
  92 <ul>
  93 <li><p>courgette_tool.cc:ApplyEnsemblePatch kicks off the patch generation
  94 by calling ensemble_apply.cc:ApplyEnsemblePatch</p></li>
  95 <li><p>ensemble_create.cc:ApplyEnsemblePatch, reads and verifies the
  96 patch's header, then calls the overloaded version of
  97 ensemble_create.cc:ApplyEnsemblePatch.</p></li>
  98 <li><p>The patch is read into an ensemble<em>apply.cc:EnsemblePatchApplication
  99 object, which generates a set of patcher</em>x86<em>32.h:PatcherX86</em>32
 100 objects for the sections in the patch.</p></li>
 101 <li><p>The original file is disassembled and encoded via a call
 102 EnsemblePatchApplication.TransformUp, which in turn call
 103 patcher<em>x86</em>32.h:PatcherX86_32.Transform.</p></li>
 104 <li><p>The transformed file is then bspatched via
 105 EnsemblePatchApplication.SubpatchTransformedElements, which calls
 106 EnsemblePatchApplication.SubpatchStreamSets, which calls
 107 simple_delta.cc:ApplySimpleDelta, Courgette's built-in
 108 implementation of bspatch.</p></li>
 109 <li><p>Finally, EnsemblePatchApplication.TransformDown assembles, i.e.,
 110 reverses the encoding and disassembly, on the patched binary data.
 111 This is done by calling PatcherX86<em>32.Reform, which in turn calls
 112 the global function encoded</em>program.cc:Assemble, which calls
 113 EncodedProgram.AssembleTo.</p></li>
 114 </ul>
 115
 116 <h2>Glossary</h2>
 117
 118 <p><strong>Adjust</strong>: Reassign address indices in the new program to match more
 119   closely those from the old.</p>
 120
 121 <p><strong>Assembly program</strong>: The output of <em>disassembly</em>.  Contains a list of
 122   <em>Courgette instructions</em> and an index of branch target addresses.</p>
 123
 124 <p><strong>Assemble</strong>: Convert an <em>assembly program</em> back into an object file
 125   by evaluating the <em>Courgette instructions</em> and leaving the machine
 126   instructions in place.</p>
 127
 128 <p><strong>Courgette instruction</strong>: Replaces machine instructions in the
 129   program.  Courgette instructions replace branches with an index to
 130   the target addresses and replace part of the relocation table.</p>
 131
 132 <p><strong>Disassembler</strong>: Takes a binary file and produces an <em>assembly
 133   program</em>.</p>
 134
 135 <p><strong>Encode</strong>: Convert an <em>assembly program</em> into an <em>encoded program</em> by
 136   serializing its data structures into byte vectors more appropriate
 137   for storage in a file.</p>
 138
 139 <p><strong>Encoded Program</strong>: The output of encoding.</p>
 140
 141 <p><strong>Ensemble</strong>: A Courgette-style patch containing sections for the list
 142   of branch addresses, the encoded program.  It supports patching
 143   multiple object files at once.</p>
 144
 145 <p><strong>Opcode</strong>: The number corresponding to either a machine or <em>Courgette
 146   instruction</em>.</p>