Code Coverage - Fuzzing

Question

I have been fuzzing Adobe Reader lately.

One of the issues that I face is Code coverage. How do I determine that I have covered all the basic blocks in Adobe Reader and it's libraries.

Is there any script or tool to find basic blocks of all selected EXE and DLL statically? I mean, I want to get all the Basic Blocks in the corresponding EXE's and libraries.

Currently, I'm using PIN to do so. But, it does not show how many basic blocks I have covered.

My aim is to create a script that will scan the given directory and write all the basic blocks in a file so that I can create a graph and so.

Answer 1

Correct disassembly of an executable is known to be undecidable in the general case (this problem can obviously be related to the famous halting problem of a Turing machine).

So, extracting all the basic blocks of a binary program is a very difficult problem.

Yet, there are several techniques to try to approach a best effort coverage of the instructions. One of the most efficient technique is to use, both, concrete and symbolic exploration of the program. This is what is implemented in the Microsoft Research SAGE tool. See Patrice Godefroid's homepage.

Unfortunately, the SAGE tool is only for Microsoft Research internal use. But, in fact, Patrice Godefroid's first idea is at the origin of many other tools such as:

• KLEE (Testing a Small Function, tutorial);
• Mayhem (see this paper);
• Pintool Memory Fuzzing by Jonathan Salwan (In-Memory fuzzing with Pin and Binary analysis: Concolic execution with Pin and z3, blog posts);
• EGAS a SAGE clone part of the Moflow project and based on the BAP platform;
• FuzzWin by Sébastien Lecomte;
• A Collection of Binary Fuzzers based on this idea;
• Semi-Automated Input Crafting by Symbolic Execution, with an Application to Automatic Key Generator Generation by Rolf Rolles;
• A few blog posts about binary analysis;
• ...

Anyway, there is still plenty of room to implement new tools with better handling of the binary program and with better support. So, feel free to start ! ;-)

Hope this helped.

Answer 2

You can write an IDA script or create an IDA plugin to gather all basic blocks in a program. Sample plugin code to gather all basic blocks can be found in http://www.hexblog.com/ida_pro/files/coverit.zip -

...
// Find all basic blocks in the specified area
static bool gather_basic_blocks(ea_t ea1, ea_t ea2)
{
  show_wait_box("Finding basic blocks");
  ea_t start = BADADDR;
  bool ok = true;
  int cnt = 0;
  while ( true )
  {
    if ( wasBreak() )
    {
      ok = false;
      break;
    }
    if ( ++cnt == 1000 )
    {
      showAddr(ea1);
      cnt = 0;
    }
    if ( start == BADADDR )
    {
      ea1 = nextthat(ea1, ea2, f_isCode, NULL);
      if ( ea1 >= ea2 )
        break;
      start = ea1;
    }
    while ( ea1 < ea2 )
    {
      if ( !ua_ana0(ea1) )
        break;
      ea1 = get_item_end(ea1);
      if ( is_basic_block_end(true) )
        break;
    }
    if ( ea1 != start )
      bbs[start] = ea1 - start; // remember the bb start and size
    if ( !isCode(get_flags_novalue(ea1)) )
      start = BADADDR;
    else
      start = ea1;
  }
  hide_wait_box();
  return ok;
}
...

Answer 3

Binary-level code coverage analysis can be done either statically or dynamically. Static instrumentation can, among other things, offer drastic performance improvements over dynamic tools like Pin. However, it is considered, somewhat traditionally, to be brittle, i.e., it breaks binaries. For example, see the last note on static rewriting in afl-qemu. Hence, dynamic coverage analysis tools like DynamoRIO's drcov are more popular.

That said, this paper (disclosure: first author here), describes bcov, a tool which was able of leveraging static instrumentation while achieving at the same time better transparency in comparison to the popular DBI tools Pin and DynamoRIO. However, this work required an orchestrated effort which combined:

• Probe pruning. Leveraged dominance analysis in order to prune basic blocks that do not offer additional coverage information. This can cut the number of required probes down to 46% of the total number of basic blocks.
• Precise jump table analysis. Imprecision in the recovered control flow graph can cause the instrumented binaries to break. Therefore, recovering the targets of indirect jumps was necessary. This in turn enables the instrumentation of jump table entries.
• Various static instrumentation tricks. Aggressive overwriting of padding bytes and hosting detours in neighboring basic blocks.

The tool bcov supports x86-64 ELF binaries. It can dump a single coverage file at process shutdown. This file contains a static array of booleans indicating the coverage of individual basic blocks. This means that merging (or diffing) coverage data of multiple tests can be done using simple boolean operations on the files themselves without the need to first post-process the data files. This feature improves the efficiency of the fuzzing workflow.

Update

The source code of bcov is now available.