[langsec-discuss] CodePhage

Andrew munin at mimisbrunnr.net
Mon Jul 13 13:05:16 UTC 2015


Their paper is here:
http://people.csail.mit.edu/fanl/papers/codephage-pldi2015.pdf

A related paper on a system to automatically find the bugs to repair is
here: http://dspace.mit.edu/openaccess-disseminate/1721.1/96155

One frustrating thing about this paper (that is true though for almost
all work done on native mode programs) is that the abstract leads with

"...CP works with binary donors with no need for source code or
symbolic information..."

yet further in...

"To find the values, CP uses the debugging information from the
recipient binary to identify the local and global variables available
at that candidate insertion point."

So much for "binaries", but this is just a pet peeve of mine, it doesn't
detract from the core awesomeness of the work...

After skimming the papers the overall idea seems to be to start from an
input into a binary program that makes it crash, and some set of unit
test cases that don't make the program crash. The overall hypothesis I
think is that "the fix for this crash has already been written and we
just need to find it." To find it, the system uses the crashing and
non-crashing inputs to explore other "related" programs.

Once the system identifies a function / code snippet that is equal to
the original, buggy code snippet, mod the absence of the bug in the
original code snippet, they copy and paste the newly discovered code
into the old binary. Then do stuff to make the newly stitched binary
actually work, then home free.

This is good if you have some code or programs lying around that you can
assume have already been fixed or are otherwise good. Of course, if you
have those programs, why aren't you running them, and why don't you just
run those programs wholesale instead of borrowing them one function at a
time into the old program?

The answer to that question is CodePhage can figure out, by measuring
the "symbolic effect" of regions of code, which code in some donor
application does what is needed in the buggy application, where the
original, human, author did not. For example, if you are writing some
program to process and render JPEG and you write some part of an image
library by hand due to ignorance of the image processing library API (or
a deficiency in the image processing API that you are using forces you
to write this code yourself), then CodePhage will detect that what you
have written is "identical modulo bugs" to the code in the API and copy
the API code into your program.

One advantage this system has is that the types of errors they evaluated
the system on (OOB pointer, div by zero, integer overflow) are all (I
think) pretty "local" problems, and the "contract violation" describing
the failure sort of writes itself (there is no moralizing about whether
or not an OOB access is 'correct' or not, uh, usually). You could sum up
one of these bugs in an instruction trace of a few hundred instructions.
It would probably take some enhanced cleverness to do the same for UAF.

One thing that I think is an interesting follow up to read after reading
the CodePhage papers (their bug finding paper is cool too) is the
infrastructure behind "symbolic diff." The CodePhage authors wrote their
own, I think, but if you wanted to do something similar you could start
here: http://research.microsoft.com/en-us/projects/symdiff/

On 07/12/2015 10:08 PM, dan at geer.org wrote:
> Anyone here got an explanation or an analysis of CodePhage?
> 
> One reference
> https://newsoffice.mit.edu/2015/automatic-code-bug-repair-0629
> 
> --dan
> 
> _______________________________________________
> langsec-discuss mailing list
> langsec-discuss at mail.langsec.org
> https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss
> 


More information about the langsec-discuss mailing list