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