Quadratic entity decoding DoS vector

[bucklereed]

In #103 I wrote that character entities are safe, which is sort of true: compared to the exponential 'billion laughs' attack, they are! But there's still the possibility for a malicious document to consume a quadratic amount of memory compared to its input size by defining a large entity and then referencing it a large number of times:

Prelude Text.XML> parseText def "<!DOCTYPE foo [<!ENTITY A \"aaaaaaaaaa\" >]><foo>&A;&A;&A;&A;&A;&A;&A;&A;&A;&A;</foo>"
Right (Document {documentPrologue = Prologue {prologueBefore = [], prologueDoctype = Just (Doctype {doctypeName = "foo", doctypeID = Nothing}), prologueAfter = []}, documentRoot = Element {elementName = Name {nameLocalName = "foo", nameNamespace = Nothing, namePrefix = Nothing}, elementAttributes = fromList [], elementNodes = [NodeContent "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"]}, documentEpilogue = []})

(You may wish to read the result as screaming at the shambling horror at the dark corners of DTDs.)

There is already a defence against this: refuse to do any entity substitution, either by setting psDecodeEntities appropriately or by using Text.XML.Unresolved. If this is declared to be Good Enough, Text.XML's parsing functions will need warnings on them about this DoS vector and that they therefore should not be used on untrusted input without setting psDecodeEntities.

[bucklereed]

The above comment's wrong: handling internal entities is done entirely in the parser. Even using Text.XML.Unresolved, or even the streaming interface directly, there's currently no way around this.

Or, in other words, currently xml-conduit really shouldn't be used for parsing untrusted data unless you like having all your memory eaten...

[jgm]

I believe this is mitigated by #161, which allows you to set a limit on the size of an entity expansion.
(You can set this to a small number if you really want to avoid this kind of thing.)