description.html 6.0 KB

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