From: Michal Zalewski [lcamtuf@coredump.cx] Sent: Wednesday, March 27, 2002 3:32 PM To: mixter@2xs.co.il Cc: vuln-dev@securityfocus.com Subject: Re: Re New Binary Bruteforcing Method Discovered 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 <>-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/