full-disclosure - Coding securely, was Linux (in)security

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <200310291005.h9TA5g43020802@turing-police.cc.vt.edu>
From: Valdis.Kletnieks at vt.edu (Valdis.Kletnieks@...edu)
Subject: Coding securely, was Linux (in)security 

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 226 bytes
Desc: not available
Url : http://lists.grok.org.uk/pipermail/full-disclosure/attachments/20031029/cfe5f976/attachment.bin