On Tue, 28 Oct 2003 19:45:33 PST, Gregory Steuck said: > >>>>> "Valdis" == Valdis Kletnieks <[EMAIL PROTECTED]> writes: > > Valdis> All programming languages that are Turing-complete > Valdis> (basically, anything that has a conditional loop) are prone > Valdis> to the Turing Halting Problem. > > Valdis> In other words, you can't prevent DoS-via-infinite-loop > Valdis> based on input. > > You still can manage the problem by imposing CPU limits. This is what > multiuser systems have been doing for decades with varying degrees of > success.
The question was whether a *programming language* can be so designed. On a theoretical basis - if a programming language is Turing-complete, and it contains features claimed to *prevent* infinite loops, then the compiler for said language would have to be able to solve the Halting Problem. Consider that if a program could infloop, it would be illegal, and conversely, all legal programs are guaranteed to not infloop - so the compiler has to be able to tell if it's possible for the input program to infloop. You're imposing said CPU (or stack size, or whatever) limits because you can't do so from within the language itself. Think about it - if your CPU limit trips, it's exactly *because* the language wasn't able to guarantee that a given user input wouldn't infinite loop. You're cleaning up after a language failure at that point. Looked at another way - if you're imposing CPU limits, then you're still vulnerable to a DoS - I can just re-invoke whatever it was and burn ANOTHER 30 seconds of your CPU. The only way you can beat *that* is if you set the CPU limit so low that my cost to re-launch is higher than your cost up to the point you pull the plug....
pgp00000.pgp
Description: PGP signature
