7 ms·
Billion laughs
- alexrbarlow 14y agoI have to say, i love this, crazy, for a language that is really for transferring data. I guess you could do this with YAML too?
- aardvark179 14y agoTo pull this particular style of trick you require a schema definition that allows for one object to be expanded into a whole set of objects, and for the resulting data structure to be a tree rather than a simply a rooted directed graph. I don't know YAML well but I believe if you tried this trick with something like alias nodes then you would end up with a lol9 node with ten separate connections to a single lol8 node with ten separate connections to a single lol7 node and so on. This would not produce the same problem in the parser, though might trigger problems in whatever processed the resulting graph.
- clarkevans 14y agoThat's definitely correct: Since you can produce cycles in YAML (it's deliberate choice), programs which don't check for graph cycles and blindly go about traversing a serialized graph are subject to DDOS.
- mbq 14y agoTo some extent every protocol which does not transfer message and payload size on a fixed offset in header can be called "crazy" as being vulnerable to all the problems with live parsing, terminators and unpredictable memory requirements.
- clarkevans 14y agoI don't think so. YAML by itself doesn't have any entity expansion or include capabilities -- you'd have to rely on extensions or something else that isn't on by default. The reference (alias/anchor) mechanism just rebuild the serialized graph, so there's no expansion going on there. That said, I'm sure there are quite possible implementation issues, like most software.
- deleted 14y ago[deleted]
- deleted 14y ago[deleted]
- astrojams 14y agoIt isn't obvious at first glance that this small xml file actually expands to billion "lols". You really have to give the bad guys credit for ingenuity.
- tisme 14y ago:(){ :|: & };: Even simple bash scripts can do weird things like this. And that's a lot smaller.
- tlrobinson 14y agoFor the curious: http://en.wikipedia.org/wiki/Fork_bomb http://en.wikipedia.org/wiki/Fork_bomb
- chubot 14y agoYeah but there's a HUGE difference: bash is intended to be a turing complete language, while XML is a data format. It's trivial to use infinite resources if you can execute arbitary code. It shouldn't be possible to use resources exponential to the input size for just PARSING (not doing anything else with) XML. This is a great example of why you want to use simple serialization formats like JSON. It's the same reason I never liked YAML. The spec and implementations are just way too big. There's got to be something hiding in there like this.
- tisme 14y agoThey're all classes of the same problem: hard to check for resource consumption from apparently innocent input. #define s, any kind of macro system they all suffer from this, as soon as you are allowed to define an entity referencing another defined entity you have a bomb on board.
- chubot 14y agoIt's not really the same. If bash had a separate parse step (which isn't too hard to imagine), you could parse a fork bomb without any trouble. Executing it is what's dangerous. A better analogy would be a language where you can't even parse it without executing arbitrary code (Perl is probably a good example: http://www.perlmonks.org/?node_id=663393 http://www.perlmonks.org/?node_id=663393) Python AFAICT is quite safe to parse. It's not a common distinction because you normally parse stuff to execute it, and executing can do much worse things, of course. But where it might come into play is if you wanted to write a cloud service accepts arbitrary code and just does static analysis on python or bash. What kind of security would you need? It's a design flaw in the format itself -- in this case, XML. A fork bomb is not a flaw in the design of bash.
- caseydurfee 14y agoIs there a legitimate use case for being able to recursively define entities like that?
- lukeschlather 14y agoI don't see any recursion. Recursion would be an infinite loop and presumably a good parser would catch that.
- zurn 14y agoNo. Recursion can terminate and still be called recursion. (news.yc used to be a Lisp hangout)
- 3rd3 14y agoNot sure if you could abort an recursion in XML.
- Nitramp 14y agoIf you read the OP carefully, you'll see he's quite aware of the terminology. There really isn't any recursion in that XML snippet, none of the entities refers to itself, directly or transitively. If there was, the file would be invalid and the error probably caught by the parser before dying from memory exhaustion. There's no way to terminate recursion in XML entities.
- halter73 14y agoLook again. There's no actual recursion going on. It's fairly trivial to identify recursion in DTD entities.
- lmm 14y agoRather than nitpicking the terminology, can we answer the actual question: is there any legitimate use case for defining an entity in terms of another entity?
- ilcavero 14y agoso, how do I protect myself against this?
- praptak 14y agoAssign a limited memory pool to the parser, it's in the article.
- davyjones 14y agoMost of the xml libraries already have the fix.
- Evbn 14y agoUse a parser or data structure that doesn't duplicate identical objects. Functional programming wins here.
- Nitramp 14y agoYou might, but the expansion happens on a level that might be really hard to implement if you want to keep XML semantics. E.g. in the DOM API, each element has its own identity - you can't collapse identical objects (or you could, but the objects generated this way aren't identical, they have different parent nodes for example).
- sltkr 14y agoThat's hardly a fool-proof solution, because you still end up with a document that's has a very large logical size (even if you represent it in a very compact way in memory) and any non-trivial operation on the resulting string that needs to evaluate it on a character-by-character basis (e.g. a substring search) will still take "forever" to complete.
- njharman 14y agoStop using XML.
- deleted 14y ago[deleted]
- wtallis 14y agoSo, how much memory would a real-world parser actually consume given this file? I'd try it, but I had to RMA my workstation's motherboard yesterday, leaving me with a machine that only has 3GB, which is the obvious minimum for a full expansion. But I could imagine an XML parser might use UCS-2 internally, inflating this to 6GB. Or, some parsers might be clever and not attempt a full expansion.
- ghshephard 14y agoYou could try using an iteration that only required 300 MB for a full expansion...
- zurn 14y agoSo you're asking how much memory this resoource exhaustion attack consumes when you run it. Each line in the WP examaple amplifies by a factor of 10. It has 9 lines. It's 10e9. That's a billion times 3, which is just enough to 32-bit virtual memory space in common operating systems. Of course the XML implementation could be smart and short-circuit this while preserving the semantics.
- dbaupp 14y agoI think you mean 10^9 = 1e9 rather than 10e9. (And the parent actually mentioned the 3 GB minimum, I think it was essentially asking how much extra memory a real world XML parser uses.)
- irishcoffee 14y agoNope, 10e8 is what you're both looking for, as 1^9 is.. 1.
- dguido 14y agoProbably should rename this to "billion reposts." Can we move beyond this simple issue and discuss more complicated aspects of security on HN?
- dguido 14y agoFine, you guys asked for it. https://news.ycombinator.com/item?id=259458 https://news.ycombinator.com/item?id=259458 https://news.ycombinator.com/item?id=3859853 https://news.ycombinator.com/item?id=3859853 https://news.ycombinator.com/item?id=1674911 https://news.ycombinator.com/item?id=1674911 https://news.ycombinator.com/item?id=301296 https://news.ycombinator.com/item?id=301296 https://news.ycombinator.com/item?id=4619344 https://news.ycombinator.com/item?id=4619344 People that exploit these kinds of things continue to innovate, but HN seems to be stuck with XSS, SQLi, and malformed XML.
- daeken 14y agoWhile I'm all with you on talking about advanced security, the reality is that most people here don't understand basic security. I think talking about the low-hanging fruit is important -- everyone has to start somewhere. And as always, if you want to see more advanced security stuff, post it! I'll upvote it for sure. Edit: This does make me think that I've been meaning to write a blog post about a security issue I discovered for about 6 months now. Time to do that.
- wglb 14y agoWhich he did: http://news.ycombinator.com/item?id=4678309 http://news.ycombinator.com/item?id=4678309. This is a tale in which cody pretty much ends up owning ccbill.
- ezequiel-garzon 14y agoPlease consider that none of those posts with any comments in them took place within the last two years. And "sadly" gets created just to tell people to read more books. Sad indeed... EDIT: HN seems to be stuck with XSS, SQLi, and malformed XML HN is not a person: half of today's HN didn't exist two years ago [1]. [1] http://blog.rjmetrics.com/surprising-hacker-news-data-analysis/ http://blog.rjmetrics.com/surprising-hacker-news-data-analys...
- 055static 14y agoThis doesn't work with my sed-based XML parsers. :(