Re: Coding securely, was Linux (in)security

[Valdis.Kletnieks () vt edu]

On Tue, 28 Oct 2003 19:45:33 PST, Gregory Steuck said:
> > > > > > "Valdis" == Valdis Kletnieks <Valdis.Kletnieks () vt edu> 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....

Attachment: _bin
Description: