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.
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.
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.
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.
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.
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.
> 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.
> 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
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.
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.
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.
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.
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.
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!
This 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!
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.
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.
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.
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.
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.
> 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.
> 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
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.
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...
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.
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 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?
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.
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