| > I was recently looking at some code to do regular expression | > matching, when it occurred to me that one can produce fairly small | > regular expressions that require huge amounts of space and time. | > There's nothing in the slightest bit illegal about such regexp's - | > it's just inherent in regular expressions that such things exist. | | Yeah... the set of regular languages is big. And, some have pretty | pathological FSM representations. | | > In addition, the kinds of resources that you can exhaust this way is | > broader than you'd first guess. Memory is obvious; overrunning a | > thread stack is perhaps less so. ... How about file descriptors? | > File space? Available transmission capacity for a variety of kinds | > of connections? | > | | One place to look is capability systems. They're more flexible and | should have all the features you want, Capability systems I've seen have Boolean capabilities. I agree that one could, in principle, extend the notion to include resource limits - but that adds complexity.
| but are still largely | theoretical. ...for an interesting notion of "still". Capability systems have been around for 30 years. They've been implemented repeatedly. But they haven't actually succeeded in any meaningful sense anywhere. The problem doesn't seem to be capabilities as such - it's the management of them, which is way too complex. Great research area.... BTW, as an example of the additional complexity in going from binary capabilities to resource limits: If I have a capability, I may or may not be able to grant it to another actor (keeping it for myself as well); and I may or may not be able to *transfer* it to another actor. With resources, can I have to split my resources with, say, the subprocesses I create? Can I start them with the same resources I have? Can I pool mine with theirs? If I have to split them, is there some way of moving the resources around later? (VMS has OS-enforced resources, and has different catagories of them along these lines. It's been too long and I don't even remember the catagories or examples for certain, but things like "total memory used" are pooled, others are split, and yet others are simply copied.) There's a recent research programming language whose name escapes me at the moment that fully integrates capabilities with the language itself. Nice work - it was used in a demo of a multi-level secure Web browser or some such thing recently. What I don't recall is whether they do resource control as well. | http://en.wikipedia.org/wiki/Capability-based_security | | | That said, every decent Unix system I'm aware of has ulimit, which you | can use to restrict virtual memory allocations, total open files, etc: | | nash @ quack% ulimit -a | ... | virtual memory (kbytes, -v) unlimited | | nash @ quack% ulimit -v 1024 # just 1M RAM, this'll be fun :-) | | nash @ quack% ( find * ) | find: error while loading shared libraries: libc.so.6: failed to map | segment from shared object: Cannot allocate memory ...missing the point entirely. Take a multithreaded server. Apply a strict ulimit. Voila - simple denial of service attack: It's now easy for any thread to exhaust available VM, crashing the entire application. Thanks, but no thanks. | | Alternately, you can implement your own allocator library for your | application and then impose per-thread limits using that library. How | you do that is going to depend alot on the language. Obviously, there | are lots for C/C++ floating around. (a) Who said anything about per-*thread* limits? (b) Even if it is a per-thread limit, what happens when memory is transfered from thread to thread; (c) having been there ... you grossly underestimate the difficulty of "implement[ing] your own allocator library", at least if performance matters to you. | http://en.wikipedia.org/wiki/Memory_allocation | | In Java, you don't get nice knobs on Objects and Threads, but you get | several nice knobs on the VM itself: -Xm, -XM, etc. The moral equivalent of ulimit. | Other high level | languages have similar problems to Java. I.e., how do you abstract the | "size" of a thing when you don't give access to memory as a flat byte | array? Well, you can do lots of fun things using LIFO queues, or LRU | caches, and so forth. There are performance impacts to consider, but | they you can often tweak things so it sucks primarily for the abuser. | | None of these is really that hard to implement. So, do we really need | new theory for this? Dunno. One's mileage does vary. Well, based on what you've proposed ... yes, we're seriously lacking in both theory and implementation. -- Jerry | -nash | | -- | | "the lyf so short, the craft so long to lerne." | - Geoffrey Chaucer | _______________________________________________ Secure Coding mailing list (SC-L) SC-L@securecoding.org List information, subscriptions, etc - http://krvw.com/mailman/listinfo/sc-l List charter available at - http://www.securecoding.org/list/charter.php