INSIGHTS, NEWS & DISCOVERIES
FROM IOACTIVE RESEARCHERS

Thursday, November 6, 2014

ELF Parsing Bugs by Example with Melkor Fuzzer

By Alejandro Hernandez @nitr0usmx

(Extract from white paper at http://www.ioactive.com/pdfs/IOActive_ELF_Parsing_with_Melkor.pdf )


Too often the development community continues to blindly trust the metadata in Executable and Linking Format (ELF) files. In this paper, Alejandro Hernández walks you through the testing process for seven applications and reveals the bugs that he found. He performed the tests using Melkor, a file format fuzzer he wrote specifically for ELF files.



Introduction

The ELF file format, like any other file format, is an array of bits and bytes interconnected through data structures. When interpreted by an ELF parser, an ELF file makes sense, depending upon the parsing context: runtime (execution view) or static (linking view).

In 1999, ELF was chosen as the standard binary file format for *NIX systems, and now, about 15 years later, we are still in many instances blindly trusting the (meta)data within ELF files, either as executable binaries, shared libraries, or relocation objects. 

However, blind trust is not necessary. Fuzzing tools are available to run proper safety checks for every single untrusted field.

To demonstrate, I tested and found bugs in seven applications using Melkor, a file format fuzzer specifically for ELF files that I developed: 


The following were tested:
  • HT Editor 2.1.0
  • GCC (GNU Compiler) 4.8.1
  • Snowman Decompiler v0.0.5
  • GDB (GNU Debugger) 7.8
  • IDA Pro (Demo version) 6.6.140625
  • OpenBSD 5.5 ldconfig
  • OpenBSD 5.5 Kernel
Most, if not all, of these bugs were reported to the vendors or developers. 

Almost all, if not all, were only crashes (invalid memory dereferences) and I did not validate whether they’re exploitable security bugs. Therefore, please do not expect a working command execution exploit at the end of this white paper.

Melkor is an intuitive and, therefore, easy-to-use fuzzer. To get started, you simply identify:
  • The kind of metadata you want to fuzz 
  • A valid ELF file to use as a template 
  • The number of desired test cases you want to generate (malformed ELF files that I call ‘orcs,’ as shown in my Black Hat Arsenal presentation, slides 51 and 52.1 
  • The likelihood of each fuzzing rule as a percentage
Options supported by Melkor:



For a quiet output, use the -q switch.


1. - Melkor Test of HT Editor 2.1.0

HT (http://hte.sourceforge.net) is my favorite ELF editor. It has parsers for all internal metadata.


Test Case Generation

To start, we’ll fuzz only the ELF header, with a 20% chance of executing each fuzzing rule, to create 1000 test cases:

$./melkor -H templates/foo -l 20 -n 1000



You will find the test cases that are generated in the orcs_foo directory along with a detailed report explaining what was fuzzed internally. 


Fuzzing the Parser

You could perform manually testing by supplying each orc (test case) as a parameter to the HT Editor. However, it would take a long time to test 1000 test cases. 
For that reason, Melkor comes with two testing scripts: 
  • For Linux, test_fuzzed.sh 
  • For Windows systems, win_test_fuzzed.bat
To test the scripts automatically, enter:

$./test_fuzzed.sh orcs_foo/ “ht”

Every time HT Editor opens a valid ELF file, you must press the [F10] key to continue to the next test case.


The Bug

After 22 tries, the test case orc_0023 crashed the HT Editor:



The next step is to identify the cause of the crash by reading the detailed report generated by Melkor:



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:



Fuzzing the Parser

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 Dependencies2.

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:\Users\nitr0us\Downloads>melkor-v1.0\win_test_fuzzed.bat orcs_foo_SHT_snowman\ snowman-v0.0.5-win-x64\snowman.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.

Alejandro Hernández


Acknowledgements

IOActive, Inc.


References

[1]  Alejandro Hernández. “In the lands of corrupted elves: Breaking ELF software with Melkor fuzzer.”  <https://www.blackhat.com/docs/us-14/materials/arsenal/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> 

No comments:

Post a Comment