Static Analysis Headaches

I am very interested in the static analysis of binaries. Mainly because theres no one way to do it. Theres no correct or incorrect way of analyzing compiler generated code - especially without running it. In fact most techniques only work with certain compiler constructs and function behaviors. I think thats why even today there are very few tools that do it well.

I started coding static analysis tools a few years ago and have steadily been rewriting and testing pieces of one in particular over and over again that analyzes x86 ELF objects. (Yes I will eventually release it in some form). I have run into many pitfalls during its design, specifically emulating the x86 without too much overhead. Obviously I don't care to emulate every single instruction in every combination, thats not only pointless but it would take forever. There are only certain parts of the execution process I am interested in. That includes what the stack looks like, register contents, variable types, and how they all tie together. For example a programmer might say sizeof(var) - and the size of that variable is determined at runtime. Now lets suppose that size argument is used as a length argument to a function like memcpy. I can't be too sure if the call is vulnerable or not because I don't know exactly what var is or how big it is. Sometimes educated guesses must be made. For example does var get assigned a value from a packet? Is it a command line argument? When you can't execute the binary, you have to make certain assumptions, and just hope they are correct.

And sometimes, you do know certain things about the variables. I thought it might be a nice write up to show how a tool of mine evaluated a specific vulnerable call to memcpy(). This is one very non-scientific way of finding variable objects in the code and assigning them attributes such as 'size'. Another 'assumption' I had to make.

Heres a function foo():

...
80483de push %ebp
  | Symbol: [foo @ 080483de]
  | Xref: (0x80483de -> [0x080483cb call 0x80483de])

80483df mov %esp,%ebp
80483e1 sub $0x18,%esp
80483e4 mov $0x8049640,%edx
80483e9 mov $0x80,%eax
80483ee mov %eax,0x8(%esp)
80483f2 movl $0x0,0x4(%esp)
80483fa mov %edx,(%esp)
80483fd call 0x80482d4
   | Symbol: [memset @ plt]
   | Analysis:
   | EAX 0x00000080 EBX 0x00000000
   | ECX 0x00000000 EDX 0x08049640
   |       | Symbol: [0x8049640 buf1 @ .bss]
   | Analysis:
   | memset() argument indicates sizeof(0x08049640)=0x80(128 bytes)

8048402 mov 0x8(%ebp),%eax
8048405 add $0x4,%eax
8048408 mov (%eax),%eax
804840a mov $0x8049640,%ecx
   | Symbol: [0x8049640 buf1 @ .bss]

804840f mov %eax,%edx
8048411 mov $0x100,%eax
8048416 mov %eax,0x8(%esp)
804841a mov %edx,0x4(%esp)
804841e mov %ecx,(%esp)
8048421 call 0x80482f4
   | Symbol: [memcpy @ plt]
   | Analysis:
   | EAX 0x00000100 EBX 0x00000000
   | ECX 0x08049640 EDX 0x00000000
   |     | Symbol: [0x8049640 buf1 @ .bss]
   | Analysis:
   | memcpy() argument indicates buffer overflow at 0x08049640 by (0x80) bytes [!]

8048426 mov $0x0,%eax
804842b leave
804842c ret
...

During its first past on the object code a size value was stored and assigned to the static object at 0x08049640 based on the arguments to memset(). This is obviously not a fool proof way of knowing what the object at 0x08049640 is or what its true size is, however at the very least it should be the objects minimum size. Its probably a global struct that contains some variables or a static character array, but its impossible for it to figure that out with any degree of certainty at this point. Following the memset() call there was a call to memcpy(), based on the prior observation I am able to determine auto-magically that there is a potential buffer overflow.

Obviously I am not the only person to use this method - as its a very simple concept and easy to implement. And certainly won't catch more complex bugs that require the interaction of many functions.

This requires several passes are made over the binary before any output to the user can occur. My first and second passes gather all symbol, relocation, and cross reference data, followed by function analysis routines. The third pass contains mostly output plugins that make all of the data accessible for display.

Blogspot has a way of jumbling up my text, not to mention its not really formatted nicely to begin with. The vulnerability analysis plugin has lots of 'hint strings' that are basically triggered by the occurence of specific instructions plus a combination of pre-existing knowledge about the static data objects and code that has already been evaluated in previous passes. For now it works on smaller programs. Despite being written in straight C, it can sometimes take awhile to crunch all of this on a large binary like Firefox (and most of the time produces absolute nonsense). The end goal is to have an effcient tool that can process and accurately report on a larger binary.