[Fonc] Teaching computers about themselves (or mapping casual data relationships to execution)

[Joe Gorse]

Greetings,

I am looking for references related to the mapping of causal relationships
between the execution of discrete machine instructions and the data,
particularly for the identification of the boundaries in the input data for
altering control flow.

I have just started a brief search and came across the notion of Generate,
Test and Debug
<http://link.springer.com/chapter/10.1007%2F978-3-642-77927-5_5>. It seems
vaguely related though I am not sure that I am getting the terminology
correct.

The idea is to inform the computer enough about its own capabilities, in
terms of read/write/branch operations, that it can statically infer the
execution flow of the binary blob and the data inputs which can alter the
control flow (and ultimately the data outputs).

In any circumstance in which the internal models for the performance are
insufficient to predict the next state, the code piece may be executed
under varying input circumstances via simulator/virtualization/baremetal to
map and characterize what sort of data boundaries exist for the control
flow. This method could also be used initially to map the hardware
capabilities to the software representation.

The value, which I hope is becoming apparent, would be more informative
debugging and eventually developing & debugging simultaneously.

So if anyone has any good references or thoughts related to this, I would
love to hear from you.

Cheers,
Joe Gorse

C: 440-552-0730
LI: Joe Gorse <http://www.linkedin.com/pub/joe-gorse/7/12/397>

[Reinout Heeck]

Post by Joe Gorse
Greetings,
I am looking for references related to the mapping of causal relationships between the execution of discrete machine instructions and the data, particularly for the identification of the boundaries in the input data for altering control flow.

You may want to look into KLEE. It tries to find every possible path through the code and where this runs into obvious bugs it will generate example input data to reach/reproduce such a bug.

The ‘mapping’ you mention is done in the form of ‘path constraints’ in KLEE, these are constraints on the input data that limit execution to a single control flow path.

http://llvm.org/pubs/2008-12-OSDI-KLEE.html

Post by Joe Gorse
We present a new symbolic execution tool, KLEE, capable of automatically generating tests that achieve high coverage on a diverse set of complex and environmentally-intensive programs. We used KLEE to thoroughly check all 89 stand-alone programs in the GNU COREUTILS utility suite, which form the core user-level environment installed on millions of Unix systems, and arguably are the single most heavily tested set of open-source programs in existence. KLEE-generated tests achieve high line coverage — on average over 90% per tool (median: over 94%) — and significantly beat the coverage of the developers' own hand-written test suites. When we did the same for 75 equivalent tools in the BUSYBOX embedded system suite, results were even better, including 100% coverage on 31 of them. We also used KLEE as a bug finding tool, applying it to 452 applications (over 430K total lines of code), where it found 56 serious bugs, including three in COREUTILS that had been missed for over 15 years. Finally, we used KLEE to cross-check purportedly identical BUSY-BOX and COREUTILS utilities, finding functional correctness errors and a myriad of inconsistencies.

I’m sure more recent work can be found by now, KLEE just happens to have stuck in my memory :-)


Reinout Heeck
————

[frank]

Post by Reinout Heeck

Post by Joe Gorse
We present a new symbolic execution tool, KLEE, capable of automatically generating tests that achieve high coverage on a diverse set of complex and environmentally-intensive programs. We used KLEE to thoroughly check all 89 stand-alone programs in the GNU COREUTILS utility suite, which form the core user-level environment installed on millions of Unix systems, and arguably are the single most heavily tested set of open-source programs in existence. KLEE-generated tests achieve high line coverage — on average over 90% per tool (median: over 94%) — and significantly beat the coverage of the developers' own hand-written test suites. When we did the same for 75 equivalent tools in the BUSYBOX embedded system suite, results were even better, including 100% coverage on 31 of them. We also used KLEE as a bug finding tool, applying it to 452 applications (over 430K total lines of code), where it found 56 serious bugs, including three in COREUTILS that had been missed for over 15 years. Finally, we used KLEE to cross-check purportedly identical BUSY-BOX and COREUTILS utilities, finding functional correctness errors and a myriad of inconsistencies.

I’m sure more recent work can be found by now, KLEE just happens to have stuck in my memory :-)

Sounds like fuzzing to me!

State of the art there would probably be American Fuzzy Lop (AFL).

http://lcamtuf.coredump.cx/afl/

Regards, Frank