Recursion kills: The story behind CVE-2024-8176 in libexpat

I hope the term &quot;deyodawgification&quot; enters the pantheon of elegant code purification terms of art, alongside the classics like &quot;degotofying&quot;, &quot;deCOMtamination&quot;, and &quot;outparamdelling&quot;.<p><a href="https:&#x2F;&#x2F;knowyourmeme.com&#x2F;memes&#x2F;xzibit-yo-dawg" rel="nofollow">https:&#x2F;&#x2F;knowyourmeme.com&#x2F;memes&#x2F;xzibit-yo-dawg</a><p><a href="https:&#x2F;&#x2F;wiki.mozilla.org&#x2F;Gecko:DeCOMtamination_Algorithm" rel="nofollow">https:&#x2F;&#x2F;wiki.mozilla.org&#x2F;Gecko:DeCOMtamination_Algorithm</a><p><a href="https:&#x2F;&#x2F;bugzilla.mozilla.org&#x2F;show_bug.cgi?id=455943" rel="nofollow">https:&#x2F;&#x2F;bugzilla.mozilla.org&#x2F;show_bug.cgi?id=455943</a><p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=22708241">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=22708241</a><p>Who knows (or can invent) any other good ones:<p>Deadlocksmithing, JSONcology, YAMLectomy, XMLimination, DeDTDification, DeXMLEntitification, ExCDATAration, AntiPOJOification, SOAPerfluousness Scrubbing, WSDLectomy, Delogorrhea, DeK8ification, HelmholtzianRechartification, DevOpsDevangelicalism, FactoryFactoryDefactoringDefactoring, Antiquasimonolithicmicrofragmentedmacrodecontainerizationarianism...

I think this was a really brave call for help from the writer. They needed help and they asked for it, from strangers!

I&#x27;m interested in examining the idea of a programming language that eschews the notion of a callstack and returns to having a single fixed activation record per function. This obviously places a lot of limits on language design, but in return you get a statically-guaranteed upper bound on memory usage, plus weirdo stuff like the ability to hand out references to local data in functions that have already returned (which remains valid as long as you don&#x27;t call the function again, which I think should be possible to enforce via a borrow checker).

I wonder what would be wrong with changing the recursive function to take a depth and then bailing out if the depth is too big.

This is a neat bug!<p>A colleague and I spent some time last year looking for DoS vulnerabilities caused by recursing on user input [1].<p>TL;DR: With CodeQL and some manual review, we found several issues resulting in two assigned CVEs, a rustsec advisory, and a handful of fixes implemented in various projects.<p>We mostly looked at Java projects. It is interesting to see a C vulnerability from around the same time.<p>It would be cool to see a larger study on how common this issue is across different programming languages.<p>[1]: <a href="https:&#x2F;&#x2F;resources.trailofbits.com&#x2F;input-driven-recursion-white-paper" rel="nofollow">https:&#x2F;&#x2F;resources.trailofbits.com&#x2F;input-driven-recursion-whi...</a>

Stack Clashing is pretty neat, something you should really pay attention to in embedded spaces (its often exploitable in UEFI land as most EDK2 builds lack guard pages).<p>I got to write some exploits for some recently, very fun bug class to exploit.

There&#x27;s a useful clang-tidy function to warn on this, for when you want to ensure there is no recursion lurking anywhere in a large codebase sensitive to stack overflow issues:<p><a href="https:&#x2F;&#x2F;clang.llvm.org&#x2F;extra&#x2F;clang-tidy&#x2F;checks&#x2F;misc&#x2F;no-recursion.html" rel="nofollow">https:&#x2F;&#x2F;clang.llvm.org&#x2F;extra&#x2F;clang-tidy&#x2F;checks&#x2F;misc&#x2F;no-recur...</a>

There&#x27;s a wonderful DDJ interview with James Clark (author of expat and developer many other open source sgml and xml standards and tools like Relax&#x2F;NG, and even horrible ones like XSLT ;) called &quot;A Triumph of Simplicity: James Clark on Markup Languages and XML&quot;, in which he explains how a standard has failed if everyone just uses the reference implementation, because the point of a standard is to be crisp and simple enough that many different implementations can interoperate perfectly.<p>A Triumph of Simplicity: James Clark on Markup Languages and XML:<p><a href="https:&#x2F;&#x2F;www.drdobbs.com&#x2F;a-triumph-of-simplicity-james-clark-on-m&#x2F;184404686" rel="nofollow">https:&#x2F;&#x2F;www.drdobbs.com&#x2F;a-triumph-of-simplicity-james-clark-...</a><p>I wrote more about his work in this discussion thread about Ted Nelson on What Modern Programmers Can Learn from the Past, and reading documents from 20 years ago:<p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=16226209">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=16226209</a><p>&gt;Reading documents from 20 years ago is a mixed bag. Links usually fail horribly, which was something Xanadu was trying to solve, but I&#x27;m not convinced they could have solved it so well that 20-year-old links would still actually work in practice. [...]<p>&gt;In the ideal world we would all be using s-expressions and Lisp, but now XML and JSON fill the need of language-independent data formats. &gt;Not trying to defend XSLT (which I find to be a mixed bag), but you&#x27;re aware that it&#x27;s precursor was DSSSL (Scheme), with pretty much a one-to-one correspondence of language constructs and symbol names, aren&#x27;t you?<p>&gt;The mighty programmer James Clark wrote the de-facto reference SGML parser and DSSSL implementation, was technical lead of the XML working group, and also helped design and implement XSLT and XPath (not to mention expat, Trex &#x2F; RELAX NG, etc)! It was totally flexible and incredibly powerful, but massively complicated, and you had to know scheme, which blew a lot of people&#x27;s minds. But the major factor that killed SGML and DSSSL was the emergence of HTML, XML and XSLT, which were orders of magnitude simpler.<p>James Clark:<p><a href="http:&#x2F;&#x2F;www.jclark.com&#x2F;" rel="nofollow">http:&#x2F;&#x2F;www.jclark.com&#x2F;</a><p><a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;James_Clark_(programmer)" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;James_Clark_(programmer)</a>

Explicit recursion is as harmful as goto. We already <i>have</i> a solution - they&#x27;re called recursion schemes[1].<p>Using recursion schemes is analogous to using structured programming rather than just constructing loops and branches out of gotos. The problem is the functional programming community got there first and the names are the equivalent of FactoryFactoryFactory and going to be a turn off to normal programmers even though the concepts are dead simple.<p>1. No citation because linking to a blog post containing Haskell is proving my point.

&gt; Please leave recursion to math and keep it out of (in particular C) software: it kills and will kill again.<p>This is just nonsense. The issue is doing an unbounded amount of resource consuming work. Don&#x27;t do an unbounded amount of resource consuming work, regardless of whether that work is expressed in a recursive or iterative form.<p>Any recursive function can be transformed into a tail recursive form, exchanging stack allocation for heap allocation. And any tail recursive program can be transformed into a loop (a trampoline). It&#x27;s really not the language construct that is the issue here.

If we had standardized growable call stacks then this wouldn&#x27;t happen

Great article! Is the code or technique used to fix this easily available somewhere?

Yet another article linking to the &#x27;10 rules of safety critical development&#x27; as a way to bash recursion.<p>If you&#x27;re going to cite this, at least make sure you&#x27;re not allocating any memory after startup.

How awful. Did anyone call The Recurse Center?<p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=43361773">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=43361773</a>

<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Tragedy_of_the_commons" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Tragedy_of_the_commons</a><p>It&#x27;s crazy how most companies just mindlessly fish in the commons and cannot even respond to whoever produces the common good.<p>Shoutouts to the 2 companies that responded by sharing resources (money or engineer time) when asked to.<p>Shame that the other 40 companies basically get to enjoy the benefits while playing the clueless fool.<p>Hopefully these 2 companies find a competitive advantage in being supply chain aware. No sympathy to the rest of the companies if they get hacked.<p>EDIT: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Free-rider_problem" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Free-rider_problem</a><p>This seems like a much more specific name for the problem

It is silly to make an overly broad statement about recursion killing. On modern &quot;hosted&quot; OSes, there are safeguards about stack overflows, which will quickly kill your process. This _can_ be a problem on embedded systems with limited memory management facilities (e.g., hw with no MMUs) and I do understand that the library author can&#x27;t control where the library is used, and in fact some safety critical systems require a maximum stack depth guarantee which rules out recursion. However, some problems, especially parsing CFGs, are inherently recursive in nature and I&#x27;d argue going the non-recursive route with explicit stacks would result in bugs elsewhere because the code becomes hard to reason about.

I would argue that the title is misleading and overly alarmist here. This particular bug may have involved recursion and a stack overflow, but that&#x27;s like saying &quot;malloc kills&quot; in the title of an article about a heap overflow bug. The existence of stack overflow bugs does not imply that recursion is bad any more than the existence of heap overflow bugs implies that malloc is bad. Recursion and malloc are tools that both have pretty well understood resource limitations, and one must take those limitations into account when employing those tools.

<i>Please leave recursion to math and keep it out of (in particular C) software: it kills and will kill again.</i><p>Is the whole (tail-recursion optimized) Lisp language family subject to DOS? Just check that you terminate at some point, right? &quot;Recursion kills&quot; is just too broad and not helpful.

I think the hate on recursion is too strong. For one thing, some languages have tail call optimization, which can turn recursion into a loop without using up the stack. For another, recursion can be bounded, so that if a malicious document tries to use a lot of recursion, it just results in an error reporting the recursion was too deep.

&gt; Please leave recursion to math and keep it out of (in particular C) software: it kills and will kill again.<p>Consider my jimmies rustled

I don’t understand the obsession of people with recursion. Sure it’s a cute math trick, it makes you feel smart, but it is an undebuggable mess with a ton of gotchas that lead to stack overflows.<p>Let the math to the math guys who never ship a product.