Unbounded recursion in XMLNode::DeepClone results in stack overflow

[cleeus]

trafficstars

The XMLNode::DeepClone member function does an unbounded recursion.

Even though XMLNode::ParseDeep enforces a limit on the recursion using the XMLDocument::DepthTracker:

XMLDocument::DepthTracker tracker(_document);
if (_document->Error())
	return 0;

this limit can later be exceeded by manipulation of the XML tree (e.g. inserting subtrees). If a suitably deep XML tree is then ::DeepClone()-ed a stack overflow can happen.

[cleeus]

There also seem to be other recursive operations that will suffer from the same problem. I found:

• XMLNode::~XMLNode->XMLNode::DeleteChildren->XMLNode::DeleteChild->XMLNode::DeleteNode->XMLNode::~XMLNode
• XMLElement::Accept->XMLElement::Accept

I have seen this before in XML handling code. There basically are two remediations: a) limit recursion depth and gracefully fail with an error b) implement iterative depth-first graph traversal with state tracking on a heap-allocated data structure

From my experience b) is a little bit more complicated to implement but also provides a good performance improvement (function call overhead can be eliminated in iterative functions).

[cleeus]

I wrote a few simple repro test cases to illustrate the problem. These tests currently all crash with a stack overflow. Can I get a comment if this is considered a defect?

https://github.com/cleeus/tinyxml2/commit/82310de580d9dfe9d4030082ead07799765a53a2

[leethomason]

Definitely a bug - and a good find!