>Hello? Hi. >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. True. I would add that the final execution path, the most critical behavior of all, and also the most difficult to evaluate in a dynamic system, is whether the subject is to be hostile or not. That is much harder to determine than whether a number is prime or not. However, what does that have to do with pinpointing vulnerabilities? Vulnerabilities are not about how a process is to behave, but based on what information - and its integrity - it is to behave. Predictable behavior, in the context of security analysis, only gives you the ability to increase granularity. It is not a requirement for any security analysis. I do not see, then, how vulnerabilities are linked to execution paths. An application does not become vulnerable simply because it took execution path A instead of path B. It was already vulnerable in first place because it based its decision on untrustworthy information. >Basically, there are two main problems with formal analysis - identifying >the potential vulnerability (which requires a formal model of accepted or >unacceptable behavior), "first problem to getting something is knowing what you want" >and determining whether it can be an actual risk >(which can be reduced to the halting problem, pretty much). Risk must be determined by trust, not behavior. Then it's not a problem anymore. >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? No. And not really interested in knowing. The integrity of my process comes to rely entirely on that function whose output is unknown. You trust it? I would not. In a security setting, that would be the exact thing I would consider a vulnerability in my integrity model. >Do you know what would be the implication of having a "yes" >answer to this question? Lie. >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. Most likely been done already. In the 70's. At the time when information security was a science. >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 - Notion of 'exploitable bug', as seen on this mailing list, is ridiculous itself. I guess all concepts derived inherit from the property. >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, _________________________________________________________________ Send and receive Hotmail on your mobile device: http://mobile.msn.com
This archive was generated by hypermail 2b30 : Thu Mar 28 2002 - 08:17:12 PST