Yeah 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.

YAML is acutally trivially compatible with this exploit, in a sense, though the result is not particularly disastrous with Psych.

    lol1: &lol1
      "lol"
    lol2: &lol2
      [*lol1,*lol1,*lol1,*lol1,*lol1,*lol1,*lol1,*lol1,*lol1,*lol1]
    lol3: &lol3
      [*lol2,*lol2,*lol2,*lol2,*lol2,*lol2,*lol2,*lol2,*lol2,*lol2]
    lol4: &lol4
      [*lol3,*lol3,*lol3,*lol3,*lol3,*lol3,*lol3,*lol3,*lol3,*lol3]
    lol5: &lol5
      [*lol4,*lol4,*lol4,*lol4,*lol4,*lol4,*lol4,*lol4,*lol4,*lol4]
    lol6: &lol6
      [*lol5,*lol5,*lol5,*lol5,*lol5,*lol5,*lol5,*lol5,*lol5,*lol5]
    lol7: &lol7
      [*lol6,*lol6,*lol6,*lol6,*lol6,*lol6,*lol6,*lol6,*lol6,*lol6]
    lol8: &lol8
      [*lol7,*lol7,*lol7,*lol7,*lol7,*lol7,*lol7,*lol7,*lol7,*lol7]
    lol9: &lol9
      [*lol8,*lol8,*lol8,*lol8,*lol8,*lol8,*lol8,*lol8,*lol8,*lol8]

In YAML, this is 9 objects in memory, one of them is a scalar, the other 8 are arrays of size 10 that happen to be pointers to the other objects. Not very big at all... much less than 1k. It's not even interesting since YAML competently serializes graphs that are far more complex. Lots of reasons to trash YAML, this isn't one of them.

As aardvark179 noted, a usage concern with YAML is more with how an unguarded application might fail to check for serialized graph cycles.

That makes sense. I tested this in a REPL that tried to pretty-print the result.

> Lots of reasons to trash YAML, this isn't one of them.

Is there a list of these reasons? Apart from graph cycles, I have only come across some gotchas (e.g. using "yes" without quotes in a translation file).

That is probably not affected, as it's not necessary that each copy of lol1 inside lol2 actually be a copy. They could simply all be references to the same node.

In fact, I don't even think that is legal for them to be copies, as this is the means by which YAML allows circular data structures to be represented.

They'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.

It'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)

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.

I suppose that how safe a grammar is to parse depends on whether or not there are language constructs that can generate exponential growths of memory usage, how much memory you have available for the task, and whether or not it can even be parsed at all.

It seems like the only way to totally secure an automated system against this kind of attack is to have a limit on parser memory usage and CPU cycles, and reject input when the parser breaks any of these limits.

JSON: {{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{... and so on.

It isn't exponential, no, but you're quite likely to still crash something if the receiver was not programmed to handle that.

If I'm not mistaken, the memory load even is linear. You could protect yourself by just setting a maximum size limit for the buffer.

For the curious: http://en.wikipedia.org/wiki/Fork_bomb

Looks like an interesting emoticon.