By debugging it with GDB, you would see:

Effectively, there is a NULL pointer dereference  in the instruction mov (%rdi),%rax. 2. – Melkor Test of GCC (GNU Compiler) 4.8.1

I consider the GCC to be the compiler of excellence. When you type gcc foo.c -o foo, you’re performing all the phases (compilation, linking, etc.); however, if you want only to compile, the -c is necessary, as in gcc -c foo.c, to create the ELF relocatable object foo.o.

Normally, relocations and/or symbols tables are an important part of the .o objects. This is what we are going to fuzz.

Test Case Generation

Inside the templates/ folder, a foo.o file is compiled with the same Makefile to create Melkor, which in turn will be used as a template to create 5000 (default -n option) malformed relocatable files. We instruct Melkor to fuzz the relocations within the file (-R) and the symbol tables (-s) as well:

$./melkor -Rs templates/foo.o

During the fuzzing process, you may see verbose output:

In order to test GCC with every malformed .o object, a command like gcc -o output malformed.o must be executed. To do so automatically, the following arguments are supplied to the testing script:

$./test_fuzzed.sh orcs_foo.o/ “gcc –o output”

You can observe how mature GCC is and how it properly handles every malformed struct, field, size, etc.:

The Bug

Normally, in a Linux system, when a program fails due to memory corruption or an invalid memory dereference, it writes to STDERR the message: “Segmentation fault.” As a quick way to identify if we found bugs in the linker, we can simply look for that message in the output of the testing script (the script already redirected the STDERR of each test case to STDOUT).

$./test_fuzzed.sh orcs_foo.o/ “gcc –o output” | egrep “Testing program|Segmentation fault”

Filtering for only those that ended with a “Segmentation fault,” I saw that 197 of 5000 test cases triggered a bug.

3. – Melkor Test of the Snowman Decompiler v0.0.5

Snowman (http://derevenets.com) is a great native code to C/C++ decompiler for Windows. It’s free and supports PE and ELF formats in x86 and x86-64 architectures.

Test Case Generation

In the previous example, I could have mentioned that after a period of testing, I noticed that some applications properly validated all fields in the initial header and handled the errors. So, in order to fuzz more internal levels, I implemented the following metadata dependencies in Melkor, which shouldn’t be broken:

With these dependencies, it’s possible to corrupt deeper metadata without corrupting structures in higher levels. In the previous GCC example, it’s evident that these dependencies were in place transparently to reach the third and fourth levels of metadata, symbol tables, and relocation tables respectively. For more about dependencies in Melkor, see Melkor Documentation: ELF Metadata Dependencies².

Continuing with Snowman, I created only 200 test cases with fuzzed sections in the Section Header Table (SHT), without touching the ELF header, using the default likelihood of fuzzing rules execution, which is 10%:

$./melkor -S templates/foo -n 200

Fuzzing the Parser

Since snowman.exe runs on Windows machines, I then copied the created test cases to the Windows box where Snowman was loaded and tested each case using win_test_fuzzed.bat as follows:

C:Usersnitr0usDownloads>melkor-v1.0win_test_fuzzed.bat orcs_foo_SHT_snowman snowman-v0.0.5-win-x64snowman.exe

For every opened snowman.exe for which there is no exception, it’s necessary to close the window with the [Alt] + [F4] keyboard combination. Sorry for the inconvenience but I kept the testing scripts as simple as possible.

The Bug

I was lucky on testing day. The second orc triggered an unhandled exception that made Snowman fail:

4. – Melkor Test of GDB (GNU Debugger) 7.8

GDB, the most used debugger in *NIX systems, is another great piece of code.

When you type gdb foo, the necessary ELF data structures and other metadata is parsed and prepared before the debugging process; however, when you execute a program within GDB, some other metadata is parsed.

Test Case Generation

Most applications rely on the SHT to reach more internal metadata; the data and the code itself, etc. As you likely noticed in the previous example and as you’ll see now with GDB, malformed SHTs might crash many applications. So, I created 2000 orcs with fuzzed SHTs:

$./melkor -S templates/foo -n 2000

To see the other examples, GDB, IDA Pro, ldconfig and OpenBSD kernel, please continue reading the white paper at http://www.ioactive.com/pdfs/IOActive_ELF_Parsing_with_Melkor.pdf

Conclusion

Clearly, we would be in error if we assumed that ELF files, due to the age of the format, are free from parsing mistakes; common parsing mistakes are still found.

It would also be a mistake to assume that parsers are just in the OS kernels, readelf or objdump. Many new programs support 32 and 64-bit ELF files, and antivirus engines, debuggers, OS kernels, reverse engineering tools, and even malware may contain ELF parsers.

I hope you have seen from these examples that fuzzing is a very helpful method to identify functional (and security) bugs in your parsers in an automated fashion. An attacker could convert a single crash into an exploitable security bug in certain circumstances or those small crashes could be employed as anti-reversing or anti-infection techniques.

Feel free to fuzz, crash, fix, and/or report the bugs you find to make better software.

Happy fuzzing.

Extract from white paper at IOActive_ELF_Parsing_with_Melkor

Acknowledgments

IOActive, Inc.

References

[1]  Alejandro Hernández. “In the lands of corrupted elves: Breaking ELF software with Melkor fuzzer.”  </wp-content/uploads/2014/11/us-14-Hernandez-Melkor-Slides.pdf>
[2] Melkor Documentation: ELF Metadata Dependencies and Fuzzing Rules. <https://github.com/IOActive/Melkor_ELF_Fuzzer/tree/master/docs>[3] IOActive Security Advisory: OpenBSD  5.5 Local Kernel Panic.<http://www.ioactive.com/pdfs/IOActive_Advisory_OpenBSD_5_5_Local_Kernel_Panic.pdf>