Minimize Failing Test Case

[aolszowka]

Forgive me if this functionality is already in FOE; perhaps this should be a request for better documentation.

While 'minimize' is useful for creating a file that has minimal differences between the failing test case and the seed file; a more interesting ability would be to prune the minimal-seed file to the minimum number of bytes required to create the same crash.

I'm currently using FOE to run a fuzzing campaign over a third party compiler using our production code base, with all comments and irrelevant white-space stripped out, as the seed files. FOE has yielded several interesting results with this very rudimentary usage; however when filing a bug report it is not always desirable to publicly post such source files. Furthermore several of the files are long (bad for fuzzing) but are also difficult for the vendor to get to the crux of the issue.

If FOE had the ability to return the minimal number of bytes required to reproduce the same crash, in theory, would result in a fairly targeted version of these source files. In all likely-hood would be unrecognizable from the original source files which would be a bonus as well.

Think of it almost as a "infinite monkeys at keyboards" version of "C-Reduce" (https://embed.cs.utah.edu/creduce/) while not optimal CPU cycles are cheap and the problem space might be reasonable especially because there would be no need to understand the domain. Reading more on their Page it seems like "Delta" (http://delta.tigris.org/ and https://www.st.cs.uni-saarland.de/dd/) is close to what I'd want; I don't see a Windows Port however.

[wdormann]

Hi Ace,

Yeah, we're considering adding this capability for a future version of BFF. Some file types are likely not friendly towards size-wise minimization. For example, a PDF has an XREF section at the end with offsets of parts. Minimization for size could likely change the target app's parsing of the file.

That being said, a trivial implementation of a size reduction could be as simple as going through a file one byte at a time sequentially, dropping the byte, and re-running it through the target app to see if the crash is the same. Optionally, the process could be started over with a successful byte drop to see if a dropped byte could allow a prior byte to be successfully dropped now. But that could significantly increase the number of iterations to come to a size-wise minimum.

If you come up with something yourself, we'd be glad to see your contributions. All of the python pieces are in FOE (or currently BFF, which supports Windows with the development branch) should all be there to implement such a minimizer.

[aolszowka]

@wdormann

That being said, a trivial implementation of a size reduction could be as simple as going through a file one byte at a time sequentially, dropping the byte, and re-running it through the target app to see if the crash is the same.

This was exactly my thought process; I am by no means a Python Guru; but I was going to try to take a stab at it (and contribute back obviously!)

Thank you for the response

[aolszowka]

I took another run at Delta (for another problem related to this same compiler) and there is actually a Python Port of Delta! I followed the guide here: https://www.st.cs.uni-saarland.de/dd/ddusage.php3

The guide was mostly straightforward to use. The biggest hurdles being that it appears that the MyDD and DD modules are written for Python 2.x (which as of this writing you can still get an older release 2.7.x). Straight out of the box it will not work with Python 3. The "commands" module was deprecated/removed from newer versions of 2.x Python so this line had to be changed to use the new "subprocess" module (it would not work out of the box with Windows; kept complaining about the "{" character for some reason). I was able to fumble around (I know absolutely no Python) and get this to work (following the GCC example):

Replace:

# Invoke GCC
(status, output) = commands.getstatusoutput(
    "(ulimit -H -s 256; gcc -c -O input.c) 2>&1")

With:

# Invoke DBL
try:
  output = subprocess.check_output("dbl R:\Delta\input.dbl")
  status = 0
except subprocess.CalledProcessError, e:
  status = e.returncode
  output = e.output

There also seemed to be some need to initialize ‘c’ like so:

c = []

Along with keeping this check:

    if c == []:
      return self.PASS

Otherwise, you would get an assertion failure in the DD Module. Again, I have no idea what I’m doing but it seemed to work for my purposes.

As far as expanding this for use with FOE (I guess BFF for Windows now?) I have not tried my hand at it; I think part of the problem would be ensuring that the crash that is produced is identical. I can imagine scenarios where attempting to reduce the case would produce additional crashes (which may be interesting in their own right).

Other things that seemed to have helped us (might be worth mentioning):

• I run this on a RAM Drive (using the free/open source IMDisk) as this wants to write several very small files; speeds up the process incredibly
• I wondered if this would benefit at all from multithreading, but I did not have the required Python knowledge to understand if this could be improved to take advantage of that (or even if Python can easily be multithreaded)