I hope the term "deyodawgification" enters the pantheon of elegant code purification terms of art, alongside the classics like "degotofying", "deCOMtamination", and "outparamdelling".
There'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:
That warning doesn't ensure that there's no recursion, as the caveats point out. Indeed, it's trivial to show that ensuring there's no recursion is impossible as long as you have function pointers. (This is also why languages that claim to be working on a solution to prevent recursion statically are going to fail.)
In general, analysis becomes impossible when you have function pointers produced and used all over the place. But that doesn't have to be the case if the program is written deliberately to avoid the impossible cases. E.g., if you can separate the set of functions into "functions that (indirectly) are exported or have their address taken" and "functions that (indirectly) invoke a function pointer", then you know that there can't be any recursion through function pointers. Basically just a form of escape analysis.
And if you're writing your own language, you can just have explicit 'colored' functions (and corresponding pointers), and enforce that the call graph between different colors has no cycles, and no function invokes a pointer of its own color. Generics would get a bit messy, but it's still far from impossible.
You could probably restrict function pointer values with something like this:
if(fptr == x || fptr == y)
__builtin_unreachable()
Or...
if(fptr != z && fptr != w)
__builtin_unreachable()
But I'm not sure how well today's compilers can take advantage of this. You'd need a strict mode, where any function pointer is assumed to be the worst case. At that point might as well go for a real proof assistant
A colleague and I spent some time last year looking for DoS vulnerabilities caused by recursing on user input [1].
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.
We mostly looked at Java projects. It is interesting to see a C vulnerability from around the same time.
It would be cool to see a larger study on how common this issue is across different programming languages.
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).
I got to write some exploits for some recently, very fun bug class to exploit.
There'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/NG, and even horrible ones like XSLT ;) called "A Triumph of Simplicity: James Clark on Markup Languages and XML", 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.
A Triumph of Simplicity: James Clark on Markup Languages and XML:
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:
>Reading documents from 20 years ago is a mixed bag. Links usually fail horribly, which was something Xanadu was trying to solve, but I'm not convinced they could have solved it so well that 20-year-old links would still actually work in practice. [...]
>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.
>Not trying to defend XSLT (which I find to be a mixed bag), but you're aware that it's precursor was DSSSL (Scheme), with pretty much a one-to-one correspondence of language constructs and symbol names, aren't you?
>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 / 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'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.
> Please leave recursion to math and keep it out of (in particular C) software: it kills and will kill again.
This is just nonsense. The issue is doing an unbounded amount of resource consuming work. Don't do an unbounded amount of resource consuming work, regardless of whether that work is expressed in a recursive or iterative form.
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's really not the language construct that is the issue here.
> 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)
A computer can chug through millions of loop iterations. I don't think tail recursion will ever result in heap exhaustion. But a stack overflow can be caused with tens of thousands of nested calls, which is tiny in comparison.
Recursion based stack overflow issues are easier to exploit because modern computer's stack space is much smaller relative to other resources.
> Any recursive function can be transformed into a tail recursive form, exchanging stack allocation for heap allocation.
You know, I got spoiled by Haskell, doing recursion everywhere without a care, and all I had to think was the evaluation order (when things blew up). Now that I'm doing some OCaml, I have to stop and think "am I writing a tail recursive function". It's easy to write multiple levels of recursion and lose track if you're writing a tail recursive function that the compiler will optimize.
I think recursions are really easy to make unbounded by mistake. Maybe not so much as for loops and off by ones.
Agreed, and this is why some languages have annotations that ask the compiler to check a function is indeed tail recursive.
However I don't think that is the case in Expat. If the algorithm is tail recursive, but accidentally not expressed in that way, its a simple (but perhaps tedious to manually apply) program transform to express it in a way that does not consume unbounded memory (heap or stack). From the scant details on the fix in the article it appears the parsing algorithm itself was completely changed. ("The third variant "Parameter entities" reuses ... the same mechanism of delayed interpretation.") If this is the case the issue is not recursion, as the original parsing algorithm would consume unbounded resources no matter how it was expressed in C.
> Any recursive function can be transformed into a tail recursive form, exchanging stack allocation for heap allocation.
Can't all recursive functions be transformed to stack-based algorithms? And then, generally, isn't there a flatter resource consumption curve for stack-based algorithms, unless the language supports tail recursion?
E.g. Python has sys.getrecursionlimit() == 1000 by default, RecursionError, collections.deque; and "Performance of the Python 3.14 tail-call interpreter":
https://news.ycombinator.com/item?id=43317592
> Can't all recursive functions be transformed to stack-based algorithms?
Yes, you can explicitly manage the stack. You still consume memory at the same rate, but now it is a heap-allocated stack that is programmatically controlled, instead of a stack-allocated stack that is automatically controlled.
The issue is either:
* whatever the parser is doing is already tail recursive, but not expressed in C in a way that doesn't consume stack. In this case it's trivial, but perhaps tedious, to convert it to a form that doesn't use unbounded resources.
* whatever the parser is doing uses the intermediate results of the recursion, and hence is not trivially tail recursive. In this case any reformulation of the algorithm using different language constructs will continue to use unbounded resources, just heap instead of stack.
It's not clear how the issue was fixed. The only description in the blog post is "It used the same mechanism of delayed interpretation" which suggests they didn't translate the existing algorithm to a different form, but changed the algorithm itself to a different algorithm. (It reads like they went from eager to lazy evaluation.)
Either way, it's not recursion itself that is the problem.
Two things come to mind:
- Maximum stack depth greatly varies between targets. If you wanted to support a recursion depth of, say, 50, that may already be too much for some of the hardware this library needs to be able to run on, so the original problem still exists.
- This would be add an arbitrary limit to the parsing capabilities of the library. Stack space is very limited to begin with compared to heap space, So any solution that remains recursive would probably require a limit way lower than a heap-based solution could offer.
Or just take the limit as an argument so developers can adjust it based on the platform. Python also has a recursion limit but you can change it if you need to.
Depth is easy to miss when the parser calls a lot of functions that call each other and that have vastly different stack usage.
A more reliable check is to compare an address of a thing on the stack at api boundary with the current address of things on the stack. SpiderMonkey, the JS engine in Firefox, used something like that in past to stop run-away recursion or at least to switch to slower algorithms with bounded stack usage.
That idea works in general but causes false positives: No artificial limit you pick is "right" and the false positives can be avoided by getting rid of the recursion altogether.
PS: It's not one single function, not direct but indirect recursion.
Sure if it's indirect I agree it will get messy fast with a dozen functions suddenly needing to handle an additional parameter, but unrelated to that... I'd really like to know who needs recursion for this that's deeper than 3 or 4 levels. What's the use case? Such xml surely would be unreadable and unwritable to humans, but if it's used as some form of exchange format between systems, what would that be? How would it end up with such deeply nested entities? It sounds like something you deliberately implement that way to show how "smart" you are, but not "hey that seems the reasonable thing to do here".
This makes me wonder: does any of the popular xml libs have a sort of safe mode, where custom entities and similar features are disabled, those schema urls ignored, and namespaces just flattened (and whatever else I forgot or don't even know about)? You know for when I know I only need to parse simple xml files that should contain a couple plain tags and attributes, and want to reduce attack surface.
You can think of this as having two base cases, your normal success case and an error case. You could use metaprogramming to do this semi-automatically, like a decorator that took a maximum depth and checked it before calling your inner function.
Explicit recursion is as harmful as goto. We already have a solution - they're called recursion schemes[1].
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.
1. No citation because linking to a blog post containing Haskell is proving my point.
You throw goto around like it's some revolutionary change that we don't use gotos. Djikstra's paper was like 70 years ago and it was released like immediately after languages were being born.
Recursion schemes are at least as old as "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" (1991), which is closer to "Go To Statement Considered Harmful" (1968, so 23 years) than it is to today (34 years). Recursion schemes aren't at all new either.
It is silly to make an overly broad statement about recursion killing. On modern "hosted" 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'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'd argue going the non-recursive route with explicit stacks would result in bugs elsewhere because the code becomes hard to reason about.
>> denial of service was considered to be the realistic impact
> It is silly to make an overly broad statement about recursion killing. On modern "hosted" OSes, there are safeguards about stack overflows, which will quickly kill your process.
>> denial of service was considered to be the realistic impact
is in the article as justification for why this has low criticality and therefore isn't subject to the 90 day disclosure timeline. I.e. it's _limiting_ the predicted impact.
I assumed GP was referring to the other more critical risk, stack clashing, which I guess could lead to RCE? not being an issue on modern OS's.
The article basically said: "Letting your get killed this way would practically lead to DoS attacks (a security issue), therefore [conclusion]." The response was basically: "Actually, on modern OSes, your application gets killed, unlike on embedded systems. Therefore, [opposite conclusion]."
This doesn't make sense as a comment, regardless of the the particular conclusion.
You can fairly easily recurse with a context argument in which you maintain a depth count.
int recursive_fun(rec_context *ctx, ...)
{
int res = 0;
if (++ctx->depth > REC_LIMIT)
return ERROR_RECURSION_LIMIT;
...
res = recursive_fun(ctx, ...);
out:
ctx->depth--;
return res;
}
However, a problem with recursion might be something other than the maximum depth reached.
If recursion traverses an exponentially sized abstract space, it can chew up a lot of processing time before going anywhere near the protective limit.
The other problem, especially for libraries, is that they don't know either the overall stack size nor the size of a single stack frame (the former is specified when linking the executable, the latter is an implementation detail and subject to optimizer's trickery).
Many "fixes" for recursion effectively re-implement it, but do so with their own data structures that are equivalent to the stack (as originally used) but have precise definitions and therefore can be controlled wrt resources used.
If all the recursive code is under your control (no external libs at the bottom, or, worse, trips through external libs and back into recursion), you can make some generous estimate of the upper bound of a stack frame.
If the OS provides ample stack space, you can inquire about the limit, and subtract a safety margin from that to create your own soft limit that you can test against in the recursion.
Another way is to be absolutely restrictive, rather than track the limit. Create some test cases representing the worst recursive cases you're willing to handle (and document as such). Empirically measure their stack use. Multiply that by 1.5 and use that as the stack check limit.
On startup you can check that this soft limit is not too close to the real one and diagnose the situation.
If your soft limit is many megabytes away from the real one, you're not likely to hit the real one, unless something really stupid happens, like alloca, or a call into some code you don't control that goes rampant.
The submitted article, by the way, could use more nuance like this. Careless recursion in C, without reasoning about the consequences (what happens for certain inputs) is obviously bad, not recursion itself.
Keeping the focus specifically on this bug: Do you think it was "careless recursion" in libexpat? That library was started in 1997, and the recursion bug wasn't found until 2022.
> Another way is to be absolutely restrictive, rather than track the limit. Create some test cases representing the worst recursive cases you're willing to handle (and document as such). Empirically measure their stack use. Multiply that by 1.5 and use that as the stack check limit.
We look forward to your patches for libexpat to add new unit tests.
Unixes give us that. You have to fork the computation to have it contained in its own process, whose run-time, virtual memory limit, and stack depth you can control.
Doing it all in your VM/runtime, so you can bail the computation with an exception, is more challenging.
There's still not much reason to recurse using the program's own call stack rather than having your own stack structure that can live in dynamic memory and be handled in a context-appropriate way (e.g. returning an error at some depth limit rather than being killed by the OS).
Recursive parsing of CFGs is only better when they're LL grammars, but LR grammars (which are the most common grammar used in programming languages) are definitely better with an explicit stack due to the repeated way the state machine needs to run. You might be able to do a nicer LALR parser recursively but I personally haven't seen one.
Deeply nested instances of right-recursive rules will blow the stack. If the LARL parser has an unlimited stack due to dynamic allocation, that will perpetrate a DOS.
Table-driven LALR(1) with an explicit stack does not make the recursion issue go away. The tooling may provide built-in handling for it which translates excessive depth into a syntax error.
Recursive parsing using the native stack can take steps to protect itself, like by keeping track of the depth, and bailing upon hitting a limit.
Techniques involving obtaining the stack pointer (or close estimate thereof), and comparing it to a limit, are also possible.
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's like saying "malloc kills" 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.
Did you see the article references [1][2] from 2006 and 2017 that already argue that recursion is a security problem? It's not new just not well-known.
>> 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's like saying "malloc kills" in the title of an article about a heap overflow bug.
Let's see what the article[1] you cited says:
Rule 3: Do not use dynamic memory allocation after initialization.
Rationale: This rule appears in most coding guidelines for safety-critical software. The reason is simple: Memory allocators, such as malloc, and garbage collectors often have unpredictable behavior that can significantly impact performance.
If you think recursion is a known security problem, do you also think using the heap is a known security problem?
Recursion per se isn't an issue; unbounded stack use is. If you either know your input size is bounded (e.g. it's not user-generated) or use tail-recursion (which should get compiled to a loop), it's fine.
If your algorithm does unbounded heap allocations instead, you're still going to get oomkilled. The actual vulnerability is not enforcing request resource limits. Things like xml bombs can then exacerbate this by expanding a highly compressed request (so a small amount of attacker work can generate a large amount of receiver work).
Arguably, Stack Clash is just a compiler bug--recursive code shouldn't be able to jump the guard pages. This was fixed in Clang in 2021 [1], in GCC even earlier, and in MSVC earlier than that.
The problem, in practice, is the limit for malloc on most systems is a few GB, while the default stack size on windows is 1MB, a stupidly small size.
I love recursion, so I will spawn a thread to do it in with a decent sized stack, but it’s very easy to break if you use defaults, and the defaults are configured differently in every OS.
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.
Please leave recursion to math and keep it out of (in particular C) software: it kills and will kill again.
Is the whole (tail-recursion optimized) Lisp language family subject to DOS? Just check that you terminate at some point, right? "Recursion kills" is just too broad and not helpful.
The whole point of this CVE is what do you do when the input you're parsing is so large that you run out of space before you can terminate. Tail recursion helps in the sense that the issue will happen later, but it isn't a fix when we're talking about arbitrary data like an XML parser.
My apologies, I interpreted "running out of space" as meaning running out of memory, rather than meaning overflowing the stack.
The tail recursion part isn't right though. If it isn't optimised into a loop, then tail recursion makes no difference at all, you will overflow the stack just as rapidly, not later. If it is optimised into a loop, then you will not overflow the stack at all.
An algorithm that uses an amount of stack proportional to the input N is said to require O(N) space. If it is rewritten to explicitly allocate the storage instead of using stack, it still uses O(N) space.
Not necessarily. If you are computing an aggregation for instance, if your computation is recursive and not tail call optimized, it may overflow the stack but the fixed version will not use additional memory for each iteration.
Otherwise, indeed stack is memory, but the memory in general is usually way less limited than the stack and also running out of memory doesn't have the same security implications as overflowing an unprotected stack.
And, unless you manage to encode everything in the stack, your iterative version will probably take the same amount of memory as your non-optimized recursive version, minus the space used for the stack.
Reasonable compilers translate tail-recursive functions into loops/jumps, so the stack does not grow. Tail recursion is easier to do in a garbage collected functional language though (e.g. if you need to use continuation passing).
Even in C, the recursive solution is usually simpler, so it makes sense to use it for unit tests to validate the more manual solution.
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.
Let the math to the math guys who never ship a product.
Programmers like recursion because some algorithms are much, much more pleasant to write this way. Others are easier to write iteratively. Both are easy to do wrong.
Example: depth-first tree walking algorithms. Implicit stack makes it trivial to express as recursion.
Great article! Is the code or technique used to fix this easily available somewhere?
I hope the term "deyodawgification" enters the pantheon of elegant code purification terms of art, alongside the classics like "degotofying", "deCOMtamination", and "outparamdelling".
https://knowyourmeme.com/memes/xzibit-yo-dawg
https://wiki.mozilla.org/Gecko:DeCOMtamination_Algorithm
https://bugzilla.mozilla.org/show_bug.cgi?id=455943
https://news.ycombinator.com/item?id=22708241
Who knows (or can invent) any other good ones:
JDONcology, YAMLectomy, AntiPOJOification, SOAPerfluousness Scrubbing, WSDLectomy, DeDTDification, DeXMLEntification, FactoryFactoryDefactoringDefactoring, DeK8fication, HelmholtzianRechartification, DevOpsDevangelicalism, Quasimonolithicmicrofragmentedmacrocontainerization...
DTDetox
There'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:
https://clang.llvm.org/extra/clang-tidy/checks/misc/no-recur...
That warning doesn't ensure that there's no recursion, as the caveats point out. Indeed, it's trivial to show that ensuring there's no recursion is impossible as long as you have function pointers. (This is also why languages that claim to be working on a solution to prevent recursion statically are going to fail.)
In general, analysis becomes impossible when you have function pointers produced and used all over the place. But that doesn't have to be the case if the program is written deliberately to avoid the impossible cases. E.g., if you can separate the set of functions into "functions that (indirectly) are exported or have their address taken" and "functions that (indirectly) invoke a function pointer", then you know that there can't be any recursion through function pointers. Basically just a form of escape analysis.
And if you're writing your own language, you can just have explicit 'colored' functions (and corresponding pointers), and enforce that the call graph between different colors has no cycles, and no function invokes a pointer of its own color. Generics would get a bit messy, but it's still far from impossible.
You could probably restrict function pointer values with something like this:
Or... But I'm not sure how well today's compilers can take advantage of this. You'd need a strict mode, where any function pointer is assumed to be the worst case. At that point might as well go for a real proof assistantThis is a neat bug!
A colleague and I spent some time last year looking for DoS vulnerabilities caused by recursing on user input [1].
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.
We mostly looked at Java projects. It is interesting to see a C vulnerability from around the same time.
It would be cool to see a larger study on how common this issue is across different programming languages.
[1]: https://resources.trailofbits.com/input-driven-recursion-whi...
Thanks for sharing that research!
I think this was a really brave call for help from the writer. They needed help and they asked for it, from strangers!
Thank you!
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).
I got to write some exploits for some recently, very fun bug class to exploit.
There'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/NG, and even horrible ones like XSLT ;) called "A Triumph of Simplicity: James Clark on Markup Languages and XML", 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.
A Triumph of Simplicity: James Clark on Markup Languages and XML:
https://www.drdobbs.com/a-triumph-of-simplicity-james-clark-...
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:
https://news.ycombinator.com/item?id=16226209
>Reading documents from 20 years ago is a mixed bag. Links usually fail horribly, which was something Xanadu was trying to solve, but I'm not convinced they could have solved it so well that 20-year-old links would still actually work in practice. [...]
>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. >Not trying to defend XSLT (which I find to be a mixed bag), but you're aware that it's precursor was DSSSL (Scheme), with pretty much a one-to-one correspondence of language constructs and symbol names, aren't you?
>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 / 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'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.
James Clark:
http://www.jclark.com/
https://en.wikipedia.org/wiki/James_Clark_(programmer)
Yet another article linking to the '10 rules of safety critical development' as a way to bash recursion.
If you're going to cite this, at least make sure you're not allocating any memory after startup.
> Please leave recursion to math and keep it out of (in particular C) software: it kills and will kill again.
This is just nonsense. The issue is doing an unbounded amount of resource consuming work. Don't do an unbounded amount of resource consuming work, regardless of whether that work is expressed in a recursive or iterative form.
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's really not the language construct that is the issue here.
> 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)
A computer can chug through millions of loop iterations. I don't think tail recursion will ever result in heap exhaustion. But a stack overflow can be caused with tens of thousands of nested calls, which is tiny in comparison.
Recursion based stack overflow issues are easier to exploit because modern computer's stack space is much smaller relative to other resources.
> Any recursive function can be transformed into a tail recursive form, exchanging stack allocation for heap allocation.
You know, I got spoiled by Haskell, doing recursion everywhere without a care, and all I had to think was the evaluation order (when things blew up). Now that I'm doing some OCaml, I have to stop and think "am I writing a tail recursive function". It's easy to write multiple levels of recursion and lose track if you're writing a tail recursive function that the compiler will optimize.
I think recursions are really easy to make unbounded by mistake. Maybe not so much as for loops and off by ones.
Agreed, and this is why some languages have annotations that ask the compiler to check a function is indeed tail recursive.
However I don't think that is the case in Expat. If the algorithm is tail recursive, but accidentally not expressed in that way, its a simple (but perhaps tedious to manually apply) program transform to express it in a way that does not consume unbounded memory (heap or stack). From the scant details on the fix in the article it appears the parsing algorithm itself was completely changed. ("The third variant "Parameter entities" reuses ... the same mechanism of delayed interpretation.") If this is the case the issue is not recursion, as the original parsing algorithm would consume unbounded resources no matter how it was expressed in C.
Ah, I find myself in similar waters. In your experience does the [@@tailcal] annotation not cover enough of the cases?
> Any recursive function can be transformed into a tail recursive form, exchanging stack allocation for heap allocation.
Can't all recursive functions be transformed to stack-based algorithms? And then, generally, isn't there a flatter resource consumption curve for stack-based algorithms, unless the language supports tail recursion?
E.g. Python has sys.getrecursionlimit() == 1000 by default, RecursionError, collections.deque; and "Performance of the Python 3.14 tail-call interpreter": https://news.ycombinator.com/item?id=43317592
> Can't all recursive functions be transformed to stack-based algorithms?
Yes, you can explicitly manage the stack. You still consume memory at the same rate, but now it is a heap-allocated stack that is programmatically controlled, instead of a stack-allocated stack that is automatically controlled.
The issue is either:
* whatever the parser is doing is already tail recursive, but not expressed in C in a way that doesn't consume stack. In this case it's trivial, but perhaps tedious, to convert it to a form that doesn't use unbounded resources.
* whatever the parser is doing uses the intermediate results of the recursion, and hence is not trivially tail recursive. In this case any reformulation of the algorithm using different language constructs will continue to use unbounded resources, just heap instead of stack.
It's not clear how the issue was fixed. The only description in the blog post is "It used the same mechanism of delayed interpretation" which suggests they didn't translate the existing algorithm to a different form, but changed the algorithm itself to a different algorithm. (It reads like they went from eager to lazy evaluation.)
Either way, it's not recursion itself that is the problem.
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.
Two things come to mind: - Maximum stack depth greatly varies between targets. If you wanted to support a recursion depth of, say, 50, that may already be too much for some of the hardware this library needs to be able to run on, so the original problem still exists. - This would be add an arbitrary limit to the parsing capabilities of the library. Stack space is very limited to begin with compared to heap space, So any solution that remains recursive would probably require a limit way lower than a heap-based solution could offer.
Or just take the limit as an argument so developers can adjust it based on the platform. Python also has a recursion limit but you can change it if you need to.
Depth is easy to miss when the parser calls a lot of functions that call each other and that have vastly different stack usage.
A more reliable check is to compare an address of a thing on the stack at api boundary with the current address of things on the stack. SpiderMonkey, the JS engine in Firefox, used something like that in past to stop run-away recursion or at least to switch to slower algorithms with bounded stack usage.
It's not ambitious enough. This 'solution' would be someone else's problem to be avoided at all cost.
That idea works in general but causes false positives: No artificial limit you pick is "right" and the false positives can be avoided by getting rid of the recursion altogether.
PS: It's not one single function, not direct but indirect recursion.
Sure if it's indirect I agree it will get messy fast with a dozen functions suddenly needing to handle an additional parameter, but unrelated to that... I'd really like to know who needs recursion for this that's deeper than 3 or 4 levels. What's the use case? Such xml surely would be unreadable and unwritable to humans, but if it's used as some form of exchange format between systems, what would that be? How would it end up with such deeply nested entities? It sounds like something you deliberately implement that way to show how "smart" you are, but not "hey that seems the reasonable thing to do here".
This makes me wonder: does any of the popular xml libs have a sort of safe mode, where custom entities and similar features are disabled, those schema urls ignored, and namespaces just flattened (and whatever else I forgot or don't even know about)? You know for when I know I only need to parse simple xml files that should contain a couple plain tags and attributes, and want to reduce attack surface.
You can think of this as having two base cases, your normal success case and an error case. You could use metaprogramming to do this semi-automatically, like a decorator that took a maximum depth and checked it before calling your inner function.
Explicit recursion is as harmful as goto. We already have a solution - they're called recursion schemes[1].
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.
1. No citation because linking to a blog post containing Haskell is proving my point.
I think focusing on the technicals is missing the forest for the trees.
Security vulnerabilities and limitations of languages are an inevitability. You won't fix them all, you will always find faults in code.
Now are we not seeing the structural problem with these organizations?
And yet we don't use goto today because of the bugs and we're phasing out manual memory management for the same reason.
You cannot org change yourself out of all technical problems.
You throw goto around like it's some revolutionary change that we don't use gotos. Djikstra's paper was like 70 years ago and it was released like immediately after languages were being born.
Recursion schemes are at least as old as "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" (1991), which is closer to "Go To Statement Considered Harmful" (1968, so 23 years) than it is to today (34 years). Recursion schemes aren't at all new either.
It is silly to make an overly broad statement about recursion killing. On modern "hosted" 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'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'd argue going the non-recursive route with explicit stacks would result in bugs elsewhere because the code becomes hard to reason about.
>> denial of service was considered to be the realistic impact
> It is silly to make an overly broad statement about recursion killing. On modern "hosted" OSes, there are safeguards about stack overflows, which will quickly kill your process.
Something doesn't make sense here.
I might not entirely understand, but
>> denial of service was considered to be the realistic impact
is in the article as justification for why this has low criticality and therefore isn't subject to the 90 day disclosure timeline. I.e. it's _limiting_ the predicted impact.
I assumed GP was referring to the other more critical risk, stack clashing, which I guess could lead to RCE? not being an issue on modern OS's.
The article basically said: "Letting your get killed this way would practically lead to DoS attacks (a security issue), therefore [conclusion]." The response was basically: "Actually, on modern OSes, your application gets killed, unlike on embedded systems. Therefore, [opposite conclusion]."
This doesn't make sense as a comment, regardless of the the particular conclusion.
> On modern "hosted" OSes, there are safeguards about stack overflows, which will quickly kill your process.
There are lots of contexts where a processing being killed is bad.
Sending a deeply nested JSON object as part of a request to some API should not crash the server that handles the request.
In contexts where availability matters, recursing on user supplied input is dangerous.
You can fairly easily recurse with a context argument in which you maintain a depth count.
However, a problem with recursion might be something other than the maximum depth reached.If recursion traverses an exponentially sized abstract space, it can chew up a lot of processing time before going anywhere near the protective limit.
The other problem, especially for libraries, is that they don't know either the overall stack size nor the size of a single stack frame (the former is specified when linking the executable, the latter is an implementation detail and subject to optimizer's trickery).
Many "fixes" for recursion effectively re-implement it, but do so with their own data structures that are equivalent to the stack (as originally used) but have precise definitions and therefore can be controlled wrt resources used.
If all the recursive code is under your control (no external libs at the bottom, or, worse, trips through external libs and back into recursion), you can make some generous estimate of the upper bound of a stack frame.
If the OS provides ample stack space, you can inquire about the limit, and subtract a safety margin from that to create your own soft limit that you can test against in the recursion.
Another way is to be absolutely restrictive, rather than track the limit. Create some test cases representing the worst recursive cases you're willing to handle (and document as such). Empirically measure their stack use. Multiply that by 1.5 and use that as the stack check limit.
On startup you can check that this soft limit is not too close to the real one and diagnose the situation.
If your soft limit is many megabytes away from the real one, you're not likely to hit the real one, unless something really stupid happens, like alloca, or a call into some code you don't control that goes rampant.
The submitted article, by the way, could use more nuance like this. Careless recursion in C, without reasoning about the consequences (what happens for certain inputs) is obviously bad, not recursion itself.
Which is why it's reasonable to have configurable limits for both processing space and time in anything handling untrusted data.
Unixes give us that. You have to fork the computation to have it contained in its own process, whose run-time, virtual memory limit, and stack depth you can control.
Doing it all in your VM/runtime, so you can bail the computation with an exception, is more challenging.
There's still not much reason to recurse using the program's own call stack rather than having your own stack structure that can live in dynamic memory and be handled in a context-appropriate way (e.g. returning an error at some depth limit rather than being killed by the OS).
"Quickly kill the process" is still a denial of service security problem.
Recursive parsing of CFGs is only better when they're LL grammars, but LR grammars (which are the most common grammar used in programming languages) are definitely better with an explicit stack due to the repeated way the state machine needs to run. You might be able to do a nicer LALR parser recursively but I personally haven't seen one.
Deeply nested instances of right-recursive rules will blow the stack. If the LARL parser has an unlimited stack due to dynamic allocation, that will perpetrate a DOS.
Table-driven LALR(1) with an explicit stack does not make the recursion issue go away. The tooling may provide built-in handling for it which translates excessive depth into a syntax error.
Recursive parsing using the native stack can take steps to protect itself, like by keeping track of the depth, and bailing upon hitting a limit.
Techniques involving obtaining the stack pointer (or close estimate thereof), and comparing it to a limit, are also possible.
https://en.wikipedia.org/wiki/Tragedy_of_the_commons
It's crazy how most companies just mindlessly fish in the commons and cannot even respond to whoever produces the common good.
Shoutouts to the 2 companies that responded by sharing resources (money or engineer time) when asked to.
Shame that the other 40 companies basically get to enjoy the benefits while playing the clueless fool.
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.
EDIT: https://en.wikipedia.org/wiki/Free-rider_problem
This seems like a much more specific name for the problem
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's like saying "malloc kills" 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.
Did you see the article references [1][2] from 2006 and 2017 that already argue that recursion is a security problem? It's not new just not well-known.
[1] https://www.researchgate.net/publication/220477862_The_Power...
[2] https://www.qualys.com/2017/06/19/stack-clash/stack-clash.tx...
You might be agreeing without realising it.
>> 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's like saying "malloc kills" in the title of an article about a heap overflow bug.
Let's see what the article[1] you cited says:
If you think recursion is a known security problem, do you also think using the heap is a known security problem?Recursion per se isn't an issue; unbounded stack use is. If you either know your input size is bounded (e.g. it's not user-generated) or use tail-recursion (which should get compiled to a loop), it's fine.
If your algorithm does unbounded heap allocations instead, you're still going to get oomkilled. The actual vulnerability is not enforcing request resource limits. Things like xml bombs can then exacerbate this by expanding a highly compressed request (so a small amount of attacker work can generate a large amount of receiver work).
Arguably, Stack Clash is just a compiler bug--recursive code shouldn't be able to jump the guard pages. This was fixed in Clang in 2021 [1], in GCC even earlier, and in MSVC earlier than that.
[1]: https://blog.llvm.org/posts/2021-01-05-stack-clash-protectio...
The problem, in practice, is the limit for malloc on most systems is a few GB, while the default stack size on windows is 1MB, a stupidly small size.
I love recursion, so I will spawn a thread to do it in with a decent sized stack, but it’s very easy to break if you use defaults, and the defaults are configured differently in every OS.
Using recursive techniques to parse potentially hostile inputs kills.
Nobody should use recursion in production code, period.
And no, it's not like malloc. If you don't understand why then you definitely shouldn't be putting recursive calls in your codebase.
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.
Please leave recursion to math and keep it out of (in particular C) software: it kills and will kill again.
Is the whole (tail-recursion optimized) Lisp language family subject to DOS? Just check that you terminate at some point, right? "Recursion kills" is just too broad and not helpful.
The whole point of this CVE is what do you do when the input you're parsing is so large that you run out of space before you can terminate. Tail recursion helps in the sense that the issue will happen later, but it isn't a fix when we're talking about arbitrary data like an XML parser.
No, this CVE is explicitly about recursive calls overflowing the stack, not running out of memory on large inputs.
The point of tail recursion is that it can be converted into a loop instead of actually recursing.
Exactly. A stack overflow caused by recursion more likely converts to an endless loop. Nothing saves a bad code design.
I did not mention memory once anywhere in my comment?
My apologies, I interpreted "running out of space" as meaning running out of memory, rather than meaning overflowing the stack.
The tail recursion part isn't right though. If it isn't optimised into a loop, then tail recursion makes no difference at all, you will overflow the stack just as rapidly, not later. If it is optimised into a loop, then you will not overflow the stack at all.
Someone who doesn't believe that stack is "space" will not believe that it's "memory" either. :)
Tail call optimization uses no stack at all
I think "space" (i.e. in "run out of space before you can terminate") is most naturally interpreted as referring to memory.
Stack is memory!
An algorithm that uses an amount of stack proportional to the input N is said to require O(N) space. If it is rewritten to explicitly allocate the storage instead of using stack, it still uses O(N) space.
Not necessarily. If you are computing an aggregation for instance, if your computation is recursive and not tail call optimized, it may overflow the stack but the fixed version will not use additional memory for each iteration.
Otherwise, indeed stack is memory, but the memory in general is usually way less limited than the stack and also running out of memory doesn't have the same security implications as overflowing an unprotected stack.
And, unless you manage to encode everything in the stack, your iterative version will probably take the same amount of memory as your non-optimized recursive version, minus the space used for the stack.
True, I'd just tend to call exceeding the stack limit a stack overflow, rather than the more generic running out of space.
Correct.
Reasonable compilers translate tail-recursive functions into loops/jumps, so the stack does not grow. Tail recursion is easier to do in a garbage collected functional language though (e.g. if you need to use continuation passing).
Even in C, the recursive solution is usually simpler, so it makes sense to use it for unit tests to validate the more manual solution.
The point of termination is beyond stack overflow here, that's the problem. And unlike heap, stack does not tell you gently that it's running out.
> Please leave recursion to math and keep it out of (in particular C) software: it kills and will kill again.
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.
Let the math to the math guys who never ship a product.
Programmers like recursion because some algorithms are much, much more pleasant to write this way. Others are easier to write iteratively. Both are easy to do wrong.
Example: depth-first tree walking algorithms. Implicit stack makes it trivial to express as recursion.
It is not smart, or special, or something.