simple patch: do not instrument functions that only have one basic block. It just pollutes the map. if there is a decision to call that function it is in the callee and therefore covered.

Hi,

I tried you code and read the paper, and I think the optimization is way too aggressive and loosing coverage.

I have compiled a random code and then looked with a disassembler which basic blocks were instrumented and which were not.

instrumented basic blocks with afl-2.52b llvm_mode: 279 instrumented basic blocks with instrim: 76

Thats about only 30%of the blocks being instrumented. That already looks bad, so lets look at a specific example:

In that picture we see 7 basic blocks, the two top blocks coming from yes/no decision branches, and the bottom 3 blocks resulting in the same final basic block.

In the visible 7 basic blocks only one is instrumented. the resulting basic block from the bottom three blocks that is not visible, is also instrumented.

If we now look at the non-instrumented blocks - they are all potentially interesting and should have been instrumented.

Did you just do speed comparisons? Or did you also do coverage comparison? (for this to be effective you have to remove all srandom() calls in afl-fuzz and replace it with a fixed srandom(123) at the start of main() to have the same PRNG results, run it for 1-24 hours and then compare the coverage of lines of code, e.g. with afl-cov)

Please excuse my poor English.

I tried to compile some programs using patched afl-clang-fast. Unfortunately, this error occurred and compiling failed.

error: unable to load plugin '/path/to/instrim/libLLVMInsTrim.so':
'/path/to/instrim/libLLVMInsTrim.so: undefined symbol:
_ZN4llvm24DisableABIBreakingChecksE'

OS is Ubuntu 16.04.2 on x86_64. All prerequisite packages have already been installed (by apt-get), and I've done all steps written in README.

What shoud I do to resolve this error?

The original algorithm will see the empty path as a distinguishable unique path.

For example: In the following CFG, the algorithm will initial the entry with mark (0), then it will find there are 2 mark (0) coming from the predecessors of block D, so it will create a new mark (1). On the exit block, the predecessors are two different marks, so it won't be marked (instrumented).

However, the path of mark (0) is actually an empty path without any mark. Although an empty path is distinguishable with any other paths with marks, the fuzzer won't receive any signal if there is no mark (instrumentation) on a path.

This PR changes the marking algorithm, so it instrument function exit blocks when there is an empty path, which should address the issue #4.

Here are the number of instrumented blocks on libxml2-v2.9.10: | Method | # of instrumented blocks | |------------|--------------------------------| | Full instrumentation | 68932 | Original marking algorithm | 16370 | Marking algorithm with this patch | 17264

It is mentioned in the project paper that the number of inserting blocks of instrim has been reduced a lot compared to afl. I tried to count the number of instrumented blocks, but I didn't find any better tools to make statistics. I checked the source code of instrim, and I didn't seem to see the corresponding statistical method. Could you please tell me how to count the number of marked vertices?

Currently we use the fixed 65536 as map size, which is the default value in AFL config.h. We should include the config.h to make sure both sides have consistent map size.

Thanks for the report from vanhauser-thc

The basic block which writes to the coverage map also has to set the previous location.

There are two issues with how this is implemented in InsTrim:

1. the algorithm for this in afl is:

     index = curr_location ^ (prev_location >> 1);
     map[index]++;

In the InsTrim code the right shift of the prev_location is never performed.

2. the prev_location written is always a specific one and not the one that was actually the path. e.g. EntryBlock / | \ A B C \ | / ExitBlock The writing to the map will happen in the ExitBlock, and the prev_location written will always be the ID of block A, and not depend on which actual path was taken.

In the code this is visible in the following line:

IRB.CreateStore(ConstantInt::get(Int32Ty, genLabel()), OldPrev);

Two fix both issues, in afl++ we removed that CreateStore() and added after IRB.CreateStore(Incr, MapPtrIdx);:

Value *Shr = IRB.CreateLShr(L, One32);
 IRB.CreateStore(Shr, OldPrev)->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));

Note that this also needs a ConstantInt *One32 = ConstantInt::get(Int32Ty, 1); definition after IntegerType *Int32Ty ...

This is an extension to issue #2 - I found out where the loss of coverage is. There seems to be a logic bug that sometimes results in a basic block not being instrumented when it should.

In the following example the if (argc < 2) { BASIC_BLOCK } basic block is not instrumented. Note that is has to be compiled with AFL_DONT_OPTIMIZE: AFL_DONT_OPTIMIZE=1 MARKSET=1 afl-clang-fast -o bug bug.c

#include <stdio.h>
#include <stdlib.h>

void foo(int a) {
  printf("foo\n");
  if (a == 1)
    printf("1\n");
  else
    printf("2\n");
  printf("done\n");
}

void bar() {
  printf("bar\n");
}

int main(int argc, char *argv[]) {
  printf("main\n");
  if (argc < 2) {
    printf("argc<2\n"); // *This is not instrumented*
    return -1;
  } else if (argc > 2)
    printf("argc>2\n");
  else
    printf("argc=2\n");
  printf("ok\n");
  if (argv[1][0] == 'a')
    foo(atoi(argv[1]));
  else
    bar();
  printf("end\n");
  return 0;
}

The disassembly looks like this:

Dump of assembler code for function main:
   0x0000000000401320 <+0>:	push   rbp
   0x0000000000401321 <+1>:	mov    rbp,rsp
   0x0000000000401324 <+4>:	sub    rsp,0x20
   0x0000000000401328 <+8>:	mov    DWORD PTR [rbp-0x4],0x0
   0x000000000040132f <+15>:	mov    DWORD PTR [rbp-0x8],edi
   0x0000000000401332 <+18>:	mov    QWORD PTR [rbp-0x10],rsi
   0x0000000000401336 <+22>:	movabs rdi,0x402017
   0x0000000000401340 <+32>:	mov    al,0x0
   0x0000000000401342 <+34>:	call   0x401080 <printf@plt>
   0x0000000000401347 <+39>:	cmp    DWORD PTR [rbp-0x8],0x2
   0x000000000040134b <+43>:	jge    0x40136e <main+78>
-> HERE begins the non-instrumented basic block
   0x0000000000401351 <+49>:	movabs rdi,0x40201d
   0x000000000040135b <+59>:	mov    al,0x0
   0x000000000040135d <+61>:	call   0x401080 <printf@plt>
   0x0000000000401362 <+66>:	mov    DWORD PTR [rbp-0x4],0xffffffff
   0x0000000000401369 <+73>:	jmp    0x401482 <main+354>
-> HERE it jumps to the end

Decompiled in Ghidra it looks like this:

int main(uint param_1,char** param_2) {
 // remove variable declarations
  printf("main\n");
  if ((int)param_1 < 2) {
    printf("argc<2\n");
    local_c = 0xffffffff;
  } else {
    ...
  }
 return (ulong)local_c;
}