Re: Re New Binary Bruteforcing Method Discovered

[Michal Zalewski <lcamtuf () coredump cx>]

On Wed, 27 Mar 2002 mixter () 2xs co il wrote:

> I'm a bit surprised to see this technique is known... I called this
> technique shared library interception and first implemented it
> this January.

Hmm, maybe I am wrong, but "shared library interception" sounds like
hooking, say, getenv() to try to detect certain overflows and such, while
this guy's code does not seem to do anything with shared libraries or
interception. Instead, it seems to dig the binary for potentially
interesting variable names or option lists stored in .rodata (don't want
to lie, I didn't examine this code very carefully, can even turn out to be
a trojan ;-). So I think you are making this claim - "this is my
technique" - somewhat too early. Unless I am terribly mistaken, but the
name seems to be pretty self-explanatory.

As to your code, which you haven't described very well, I guess you used
one of two methods: hook things like getenv() and return excessive amounts
of data to trigger SEGVS, or hook getenv(), sprintf(), etc to simply
report problems. I've seen both methods in use for years, but I can be
wrong, will wait for your tool to be released.

> > Pardon me?=) Finally solved this nasty halting problem?
>
> Oh, this is a known problem as well? :) Well, pressing CTRL+C usually
> does the trick. Then again, of course you can write a little program to
> enumerate processes in the group of the shell process running the
> library interception tests, then check their activity time and send them
> appropriate signals to continue when they stall...

Hello? I think you do not really understand what I was trying to say - try
'Turing "halting problem"' in google.com. Nowadays, the analysis of all
possible execution paths for any given program (for example to find an
answer whether certain code will be executed or not, and in what order - a
critical issue for static, automated detection of dynamic vulnerabilities)
is excessively time consuming and completely not feasible in most cases.

There are certain specific cases when this is not true, and certain very
limited scopes we can accurately examine (some applications do - e.g.
compilers try to elliminate dead code, some source code audit applications
look for potentially vulnerable patterns and apply certain heuristic
algorithms to decrease the number of false positives, etc). But there's no
way to universally predict the behavior of a complex application.
Basically, there are two main problems with formal analysis - identifying
the potential vulnerability (which requires a formal model of accepted or
unacceptable behavior), and determining whether it can be an actual risk
(which can be reduced to the halting problem, pretty much).

Example: there is a program that is checking whether some <<insert your
favorite big number here>>-digit number is actually a prime. If so, it
enables you to exploit a buffer overflow (let's just say "enter endless
loop"), if not, it simply dies with some error message ("stop"). It would
take the program 10 years to check this prime. It uses the best prime
checking algorithm we know at this point. Do you know a way to tell
whether the program will stop or not (will be vulnerable or not) without
actually wasting ten years (or comparable amount of time) on your computer
to check it? Do you know what would be the implication of having a "yes"
answer to this question?

And that's not all - our "endless loop" condition is pretty clear in this
particular case, but sometimes it is not that trivial. Think about
authentication bypassing, etc. There needs to be a model of an erratic
behavior for this particular program, and the model itself must be
designed without flaws, which is not trivial. But I am not gonna argue
here - it is certainly doable and being done - it is just expensive, time
consuming and prone to problems.

Knowing the way to solve the halting problem for infinite Turing machines
in finite time would very likely enable us to perform this analysis for
finite machines in no time (and have dramatic implications not only for
computer security).

That is why I find the claim "finds all exploitable bugs" is at least
ridiculous - it implies that both problems were solved. It can find "some
potential bugs caused by certain command-line and environment variables
interaction", but not "all exploitable bugs in the application".

Regards,
-- 
_____________________________________________________
Michal Zalewski [lcamtuf () bos bindview com] [security]
[http://lcamtuf.coredump.cx] <=-=> bash$ :(){ :|:&};:
=-=> Did you know that clones never use mirrors? <=-=
          http://lcamtuf.coredump.cx/photo/