About Articles Book Store Distributed RCE Downloads Event Calendar Forums Live Discussion Reference Library RSS Feeds Search Users What's New


Customize Theme

Flag: Tornado! Hurricane!

 Forums >>  Brainstorms - General  >>  Binary Diffing Heuristics

Topic created on: October 17, 2005 02:25 CDT by pedram .

On the notion of freeware patch analysis tools, Dave Zimmer (dzzie) and I were tossing back and forth some heuristics that could be used for a freeware binary diffing tool he is putting together. I thought I'd share it on the forum for all to contribute/discuss.

First some important background on the seminal heuristics developed by Halvar Flake and implemented in his commercial product Sabre BinDiff. From what I recall reading in Halvar's whitepapers (and Halvar please make any appropriate corrections), his approach can be broken down into: function matching, node matching and instruction matching built on the following heuristics:

Graph Heuristics
Match functions with similar node/edge/call (NEC) call counts. The NEC "trifecta" comes of course from the control-flow graph. The number of calls is used as a heuristic for node matching as well.

Symbolic Name
Match functions that have the same non-trivial (ie: sub_XXXXX) name.

Recursive Functions
Match functions that make recursive calls to other functions that make recursive calls.

String References
Match functions/nodes/instructions with identical string references.

In/Out Degree
Match functions/nodes with similar in/out degree (calls to / calls from)

SPP (Small Prime Product)
This is a genius approach. Match functions/nodes with similar SPP values. SPP is stored as large numeric value and is determined as follows. Apply a unique small prime number to each opcode. SPP = the product of each opcode in the function/node. This is a great heuristic because it is resistant to instruction re-ordering.

Shortest Path to Entry/Exit
Match nodes/instructions based upon the shortest path to the function entry/exit in the case of nodes and the node entry/exit in the case of instructions.

Expanding on this list of heuristics the following ideas were tossed around:

MD5
A straight MD5 of function instructions. The idea is that a straight MD5 may help in matching smaller functions, ex: NEC = 1,1,1.

"Smart" MD5
Take the instruction list, tokenize jumps (ie: convert jump instructions into SIGNED, UNSIGNED or ABSOLUTE), alphanumeric sort it, take the MD5. This approach is roughly similar to SPP.

Push+Call
Expanding on using the number of calls as a heuristic the idea is to also count the number of PUSHes (arguments) to each CALL in an attempt to more accurately match functions/nodes.

API Profile
Match functions/nodes based on the number of API calls they make or more specifically the actual API calls they make.

Constants
Match functions/nodes/instructions based on references to constant values. For example, if two functions uniquely XOR, PUSH, AND etc. a certain constant numeric value then they should be matched/aligned.

Stack Frame Size
Match functions with similar stack frame sizes, ie: similar amount of stack space for local variables.

Spatial Locality
Match functions "closer" to one another with more of a bias. Example. If in binary A we have "exact" matches for function index 20 and 25 to function indexes 30 and 35 in binary B, respectively (ie: A.20 == B.30 and A.25 == B.35), and we are trying to find a match within B for A.26, then we should give more bias for finding a match within B between B.30 and B.35.

None of these heuristics have been tested enough to determine their value. Perhaps others have tried similar approaches and can share their results. Some questions:

- What are your thoughts in regards to the order of these test?
- What are your thoughts in regards to the recursion of these tests? ie: if we have a list of tests 1-5, should we rewind and restart at test 1 every time we make a new match?
- What other interesting heuristics can be used?

-pedram

  rfreeman     October 17, 2005 04:51.45 CDT
In terms of order, it somewhat depends on whether you are utilizing graph heuristics or known symbols. An intelligent hash or even multi-bin accumulators can be used to quickly pass judgement on functions that have not changed. Generally speaking, I'd stick aware from straight CRC32/MD5 (ie. Diffie). However an intelligent hash can still be problematic if several functions are virtually identical. There are some obvious ways to compensate for this, but regardless, they can be considered diminishing returns if two functions were not indended to be identical but are close enough and do not feature interesting elements from an analytical point of view. For my project, I implemented a few of the items Pedram has enumerated, and based its matching strategy on an exclusion/promotion system where each match level supercedes the previous regardless of amount of code deviation. Actually, it can be quite frustrating with SPP when an extra push is introduced or code optimization changes. I'm looking into an optimized reduction algorithm to see if (my implemenation of) SPP can be made more robust.

Generally speaking, issues with SPP are less likely to happen with one security patch iteration, though I encourage anybody else writing their own utility to test against increasingly earlier versions. It is quite rewarding to be able to test a xp v.0 vs xp v.2180 DLL and see all of the places that were patched over time with impressive accuracy. That said, SPP can be difficult to utilize if comparing other binaries and not merely Microsoft security patch updates.

I will point out for the casual observer that stack frame size is a tempting heuristic to add, but resist the temptation. For example, a function that relies on preprocessing from another function may have a stack overflow. This overflow may have been resolved by updating the stack size rather than migrating the routine to defensive coding practices.

~Robert

  JCRoberts     October 17, 2005 09:20.36 CDT
Hey Guys,
I seldom (if ever) deal with intentionally obfuscated instruction flows, so if this question is uninformed please pardon the offense. I just don't deal with security stuff or intentionally tricky code.

As for ideas about heuristics, I've always wondered if it would be possible to try tracking the "what" rather than the "how" ?

In other words, try to identify code chunks by what they do to data rather than by how they manipulate the data. In the most simplistic example, if someone tosses a few nops into the instruction flow, it can foil some instruction based identification, yet what the instructions do to the data will remain the same.

What would be the limitations of such an approach?

JCR

  pedram     October 17, 2005 09:52.16 CDT
Robert: Regarding the shortcoming of ESP and hashing checks, no doubt that on their own they are weak heuristics. However, the more tests you have the more chance of coming up with a unique match between binaries no?

JCR: The "what" rather then the "how" approach may be interesting for simple alignment of functions between binaries. After the binaries are aligned however, a "how" approach must be applied to detect the changes incorporated by the security patch to locate the vulnerability.

-pedram

  JCRoberts     October 17, 2005 10:32.46 CDT
Pedram,
If I've understood you correctly, it seems you're talking about static analysis. I'm thinking of dynamic analysis, namely comparing before/after snapshots of the system (i.e. running code).

I'm going on the naive thought that the instructions need to do something and even if the instructions are intentionally obfuscated (malware) or changed (bug fix), the instructions will do something remotely similar to the data/memory/system-state as their previous version.

JCR

  rfreeman     October 17, 2005 16:25.54 CDT
JCR:

Regarding NOPs, these sorts of things are generally considered worthy of exclusion prior to processing as they don't have any bearing on the outcome of the execution.

Dynamic analysis, as I understand what you want to do with it, is very doable, but also requires a *lot* of effort if you want an easy to understand "what". Until mid-April of this year I lead engineering efforts on such a project at a well-known company. However, due to obligations, that is pretty much all I can say.

Pedram:

I don't consider intelligent hashes and SPP to be intrinsicly weak heuristics. In fact, if you were to test them against early versions of BinDiff, you might find that they are less sensitive to structural changes in your target(s). (Note: I do not own or pirate BinDiff.) The point that I am getting at is not to be petty about Halvar's initial efforts, but to say that one technique alone isn't likely to get the best results. It appears that you really need to understand what your needs are (malware, security, anti-piracy, universal, etc.) and then select the best combination of heuristics. Net, if we exclusively consider security patches, then I agree with you, they (smart hash + SPP) can get the job done well most of the time.

  ryanlrussell     October 17, 2005 18:57.37 CDT
A couple of things to keep in mind, for those who haven't been following BinDiff and related tools for a few years:

-You want to line up matching functions, sure
-But really, what you want is the "matching" function, which has changed, because that's the one that contains the fix.

So you need to handle both situations to some degree.  Well, to be fair, on a tight patch, you can manually look through the few leftover straggler functions, and match them by hand.  But if you're trying to diff something that way between XP SP1 and SP2, good luck.

Also, since often you're talking about Microsoft binaries, don't forget the low-hanging fruit: .pdb files.  If you have the symbols, then you've trivially solved the matching problem, and now you really want the changed functions.

  dzzie     November 15, 2005 07:24.41 CST
was able to get a public release time slotted before end of year for the one i was working on.

I mostly need a tool like this for malcode re so tool has been primarily tested under these circumstances.

initial release is primarily based on simple function matching/profiling mechanisms. Quite usable for malcode, may develop the mechanisms out further if needed.

http://www.idefense.com/iia/labs-prereleases.php?show=3

  darko     November 15, 2005 13:58.31 CST
http://www.idefense.com/iia/labs-prereleases.php?show=3

Requires a login to download.

  dzzie     November 15, 2005 15:32.44 CST
yeah releases have to go through a pre-release thing now, public release next month, but project in the pipeline now

  Sellmi     November 24, 2005 13:47.30 CST
is there any draft about ida database file format ???

thanks a lot

  randori82     December 14, 2005 18:24.16 CST
http://www.idefense.com/iia/labs-prereleases.php?show=3
Public Release: 12.16.05

Is that still going to get released this friday?

  dzzie     December 15, 2005 11:22.23 CST
yup we are still planning on releasing it the 16th (tomorrow)

  dnix   December 16, 2005 16:18.01 CST
funny I compiled the released IDAcompare plugin for 4.9 and the debug version works , but the release build doesnt , in fact it seem to ask for the name of the debug version

  dzzie     December 16, 2005 18:28.20 CST
I may have not set the release configuration build options. Building it on a fresh system i had to tweak some workspace settings to system build paths etc. I tested both release and debug builds for 4.7 and both worked, but getting it to compile took some workspace tweaks. I will see about updating the workspace file and add a notes file

  darko     December 17, 2005 02:43.14 CST
I managed to recompile the plugin with VS2005 and release version for IDA 4.9

It is working fine.

Darko

  dnix   December 17, 2005 13:05.45 CST
New version of IDAcaompare compiled fine for 4.9 , however I sometimes seem to get an Access Violation at 0x12D103E in mod IDA_Compare.plw read of address 00000000.This seems to happen on closing down IDA , In fact I have to kill IDA , or else cant close it .Btw great plugin

  dnix   December 17, 2005 13:18.30 CST
mmmm, debug version doesnt exhibit the access violation on closing IDA

  dzzie     December 17, 2005 15:05.27 CST
i have gotten the crash on close sometimes, thought i had it beat with the CPlugin class terminate code..There are 2 global VB classes defined in the plugin..I bet it is one of them trying to tear down

  randori82     December 18, 2005 01:42.39 CST
any chance in making a scriptable interface to pass parameters from an idc script? (http://home.arcor.de/idapalace/plugins/example4.zip) could help in batch analysis if it could auto-generate the mdb's for manual analysis.  just a thought, this works great and it's great to see a non-commercial solid bindiff'ish tool out there.  thanks man.

  darko     December 18, 2005 03:58.41 CST
To avoid access vioaltion modify term as follows:

void idaapi term(void)
{
   try
   {
      if ( IDisp )
      {
         IDisp->Release();
      }
   }
   catch ( ... )
   {
   };

   CoUninitialize();
}

  warmwolf     December 18, 2005 08:39.12 CST
IDA_compare ,when I  click "save cmopare snap1",they will tread awry,show

  dzzie     December 18, 2005 09:19.48 CST
thanks am glad the company allows me to share it :)

darko will add that check to the src, i thought the try block might cover that possibility maybe some more stuff goign on behind the scenes with the COM thing, added some more preventive code to CPLugin too. I wonder if its safe to call CoUnitilize from a plugin. Havent got that crash in quite some time here on 4.7

warmwolf unfortunately i have heard of that error before. One of our Chinese analysts had the same thing happen to him occasionally. It looked like for some reason single quotes in the disassembled text were not being escaped properly by the VB Replace function when the record was trying to be inserted into the database. I was never able to reproduce it here, he said sometimes it happened for him sometimes not for same samples..Maybe i will install extended charset codepage as default and try debugging more.

randori82 i will check out the idc integration sample

thanks for the feedback guys.

  dnix   December 26, 2005 05:40.18 CST
Any updates made to IDACompare ? since last post

  dnix   December 26, 2005 17:19.43 CST
Would be usefull if one could sort the columns in unmatched by size or by name in matched etc

  dnix   December 26, 2005 18:57.23 CST
or find matched functions by name especailly when one has renamed a few

  dzzie     December 26, 2005 19:23.21 CST
hi,

no updates lately had big pre-holiday rush on some other work. Looked at idc integration, probably wont get to for quite some time, tool probably still needs manual attention at key points for best results. Next area of attention should probably be expanding matching engine, however other projects beckon atm so not sure when.

  randori82     December 29, 2005 02:25.41 CST
a bit of an asside, but when disassembling (mostly ms), i try to use symbols as much as possible.  however, i get adverse results when using pdb/dbg for diffing.  sometimes i get more matches, sometimes i get less.  is there a general rule of thumb out there for symbol usage when diffing?  of course, i wouldn't want to have any false negatives, so i'd rather be on the safe side.  just wondering what other people think.

  dzzie     December 29, 2005 18:20.37 CST
never tried dsm with symbols in testing for idacompare, right now the api profiling code records any call ds: format calls to skip internal subs, that check could be loosened might help with symbol names applied but would require recompile of the exe

  nsaxx     March 7, 2006 21:43.14 CST
I've been working on this sort of thing independantly for a few weeks now. I did have the idea though of taking these heuristics and constructing a type of neural network to assess the effectiveness (and adjust the weightings) of each type of heuristic.

It would obviously require you to know the results in advance in order to train the ann.

This may obviously yield useful relationships between each heuristic.

I'm not sure how effective this would be, but it was an interesting idea i thought.

I assume you're using these heuristics in a yes/no binary fashion. Fuzzy matching / partial matching could be quite effective i think.

This could all be a bunch of BS but i thought i'd contribute my two cents.

Note: Registration is required to post to the forums.

There are 31,320 total registered users.


Recently Created Topics
[help] Unpacking VMP...
Mar/12
Reverse Engineering ...
Jul/06
hi!
Jul/01
let 'IDAPython' impo...
Sep/24
set 'IDAPython' as t...
Sep/24
GuessType return une...
Sep/20
About retrieving the...
Sep/07
How to find specific...
Aug/15
How to get data depe...
Jul/07
Identify RVA data in...
May/06


Recent Forum Posts
Finding the procedur...
rolEYder
Question about debbu...
rolEYder
Identify RVA data in...
sohlow
let 'IDAPython' impo...
sohlow
How to find specific...
hackgreti
Problem with ollydbg
sh3dow
How can I write olly...
sh3dow
New LoadMAP plugin v...
mefisto...
Intel pin in loaded ...
djnemo
OOP_RE tool available?
Bl4ckm4n


Recent Blog Entries
halsten
Mar/14
Breaking IonCUBE VM
oleavr
Oct/24
Anatomy of a code tracer
hasherezade
Sep/24
IAT Patcher - new tool for ...
oleavr
Aug/27
CryptoShark: code tracer ba...
oleavr
Jun/25
Build a debugger in 5 minutes
More ...


Recent Blog Comments
nieo on:
Mar/22
IAT Patcher - new tool for ...
djnemo on:
Nov/17
Kernel debugger vs user mod...
acel on:
Nov/14
Kernel debugger vs user mod...
pedram on:
Dec/21
frida.github.io: scriptable...
capadleman on:
Jun/19
Using NtCreateThreadEx for ...
More ...


Imagery
SoySauce Blueprint
Jun 6, 2008

[+] expand

View Gallery (11) / Submit