Re: Decompilers or comparison tools

Alexander S.Klenin <>
28 Sep 1997 23:15:33 -0400

          From comp.compilers

Related articles
Decompilers or comparison tools (Narinder Singh) (1997-09-23)
Re: Decompilers or comparison tools (Gary H. Merrill) (1997-09-24)
Re: Decompilers or comparison tools (1997-09-27)
Re: Decompilers or comparison tools (Alexander S.Klenin) (1997-09-28)
Re: Decompilers or comparison tools (Cristina Cifuentes) (1998-03-18)
| List of all articles for this month |

From: Alexander S.Klenin <>
Newsgroups: comp.compilers
Date: 28 Sep 1997 23:15:33 -0400
Organization: TOO Kern
References: 97-09-106
Keywords: disassemble

Narinder Singh wrote:
> > I am looking for either a decompiler for MS-DOS EXE's to C or BASIC, or a
> > tool that will allow me to compare two object code files reporting the
> > similarities or the differences. Does such a tool exist? if so where can I
> > find it?

Well, at least one MS-DOS EXE-to-C decompiler does exist, although I
don't think it will help much in your case. It is a tool called
INVADER written by some Russian hackers. It recognizes code patterns
generated by Borland Pascal and Borland C/C++ for DOS compilers (which
is not too hard, because those compilers are very weak in optimizing
code). Prior to that, INVADER takes effort to decompress/decrypt EXE
file in order to get original compiler output.

As one can suggest from the name, the main purpose of INVADER is
cracking, so it is NOT documented in any form and NOT available from
any public networks except maybe Fidonet/Russia. Yet it definitely
does work ;-)

> I know of at least one binary file comparator, but it is a proprietary
> internal product of a previous employer. A true binary comparator
> that reports minimal differences (e.g., shortest edit path) is *much*
> more challenging than a comparator for text files (at least three of
> which I have written). I won't begin to go into the details, but the
> general problem is *very* thorny. Nonetheless, it would really be
> nice to have such a tool, and you could make quite a name for yourself
> by creating one. While from time to time I've wanted one myself, I've
> never had the energy or sufficient motivation to pursue this lofty
> goal.
> However, for anyone interested, I can at least provide a pointer to
> how you may get on this road to madness. It turns out (surprise) that
> the problem reduces to that of comparing arbitrary strings. And this
> problem is of rather intense interest in molecular biology (all those
> hideous protein sequences, you know). So there is quite a bit of
> literature on it, and a wealth of algorithms (each of which has its
> own strengths and weaknesses). As a starting point, then, take a look
> at Dan Gusfield's "Algorithms on Strings, Trees, and Sequences:
> computer science and computational biology", Cambridge University
> Press, 1997. Note that a lot of the problems facing computational
> biologists in this arena can be ignored if the goal is simply (??!!) a
> minimal differencing binary file comparator, since in such an
> application you don't need to worry about approximate matching and can
> be perfectly happy with exact matching techniques. That makes it much
> simpler (uh huh).

If we agree to reduce binary-file comparision problem to an abritrary-
string comparision problem (which may be not quite what we want),
the there is a simple dynamic-programming algorithm, which produces
a shortest sequence of one-character "insert" and "delete" operations
needed to convert string A into B.
It takes O(length(A)*length(B)) time and O(max(length(A),length(B)) space.
I don't know if that algo is in the book you mentioned, but it
is rather easy to figure out anyway.

> Of course, this leaves aside the issue that when you compare objects
> at the bit or byte level, the results may be a bit [no pun intended]
> difficult to interpret without some sort of context. If what you
> *really* want to do is to compare in some intelligible way the program
> content or structure of files you *know* to be EXE files, you might
> instead want to use what you know about the structure of such files to
> write an intelligent comparison tool that would yield perhaps more
> useful results.

Yes, now *this* problem is a really thorny one. I think some sort
of AI may be required to produce a true meaningful results.



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.