Courgette meets a dangerous (Red) Bend [LWN.net]

Courgette meets a dangerous (Red) Bend

Posted Nov 12, 2009 12:23 UTC (Thu) by forthy (guest, #1525)
In reply to: Courgette meets a dangerous (Red) Bend by sfink
Parent article: Courgette meets a dangerous (Red) Bend

To me, a maybe non-infringing technique is fairly obvious. The real problem is that your program is something like this:

labela:
...
call labelc
...
labelb:
...
insert new code here
...
delete code there
...
labelc:
...
jump labela
...
call labelb

When you insert or delete code, the jumps/calls over these insertions and deletions change deltas. So what do you need to do? Your binary diff already tells you where to insert and delete code, i.e. where you change the size of the whole thing. So keep track of that, and adjust all the jump/call offsets according to the size change map. No need to convert something into symbols and back - just search for instructions 0xE8, 0xE9, check to which region the following address points to, and adjust accordingly to insertion and deletion.

So the algorithm is in total:

Scan the instructions and write zero into the address fields of jumps and calls into a copy of both executables
Make a binary diff between the executables where jumps and calls are nulled out
Apply the patch+adjust jumps and calls on the original binary, creating another temporary copy
binary diff this temporary copy with the new executable

For x86/x64, marking the jumps and calls requires some limited disassembler (to determine instruction boundaries), for RISC architectures, it's even easier. The idea why I think this might be non- together, and not as individual symbols. This is not obvious from the patent claim, and it might have actual down-sides (e.g. if your patch replaces calls to function a with calls to function b, the symbolic version can compress that effectively, while my algorithm won't).

(Log in to post comments)