On Mon, Jul 17, 2006 at 05:48:59PM -0400, [EMAIL PROTECTED] wrote: > 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, but are still largely theoretical. 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 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. 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. 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. -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