Recursion kills: The story behind CVE-2024-8176 in libexpat(blog.hartwork.org) |
Recursion kills: The story behind CVE-2024-8176 in libexpat(blog.hartwork.org) |
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:
Deadlocksmithing, JSONcology, YAMLectomy, XMLimination, DeDTDification, DeXMLEntitification, ExCDATAration, AntiPOJOification, SOAPerfluousness Scrubbing, WSDLectomy, Delogorrhea, DeK8ification, HelmholtzianRechartification, DevOpsDevangelicalism, FactoryFactoryDefactoringDefactoring, Antiquasimonolithicmicrofragmentedmacrodecontainerizationarianism...
There's definitely an advantage with this idea, but also some downsides. While you have a guaranteed upper bound on memory usage, it's completely static and actually going to be worse than doing the equivalent on the stack. Suppose you have 100 functions that each need 100 bytes of scratch space. Statically allocating everything like you describe means you need 10KB of memory reserved. But suppose there is one main function, and the rest are helper functions, and the main function calls each helper function one at time and the helper functions don't call anything. With the static approach, you still need 10KB. With the stack-based approach, you only need 200 bytes (the stack space for the main function, and the stack space for the helper function it is currently calling). Another advantage to the stack-based approach is due to caching. In the static approach, whether or not a function's scratch space is in the cache or not depends on how often that function is called. But in the stack-based approach, the top of the stack is almost always in the L1 cache, giving a speed boost to functions, even when they are not called frequently.
That said, I do think it is an interesting idea that is worth exploring.
This is not necessarily the case: if you statically analyze the call graph, you may be able to prove that two functions will never be live at the same time, and thus reuse memory regions for their local variables: https://github.com/llvm-mos/llvm-mos/blob/main/llvm/lib/Targ...
Of course, recursion, function pointers, and dynamic linking will defeat (or at least complicate) this scheme.
But I don't understand the appeal. Many algorithms and data structures are most naturally expressed with recursion. Not allowing it forces the programmer to create and maintain their own manual stack data structures which brings us to square one in terms of statically-guaranteed upper bound on memory usage since they can grow indefinitely. At best, stack overflow errors will be replaced by array out of bounds errors which is the exact same thing anyway. In fact, it will be even worse: Manual stack implementation will come with its own complexity and source of bugs.
[1] https://en.wikipedia.org/wiki/Action!_(programming_language)
Chicken Scheme fits the bill. While it doesn't eschew the notation of a call stack, it turns it on its ear.
In Chicken Scheme
1. All objects are allocated on the stack. Strings, conses, symbols, lexical environments, ...
2. Functions do not return. Everything is compiled to C which uses continuation passing style. What looks like returning in the Scheme source code is a continuation call: the parent function passes a continuation, and so the function return invokes that and runs that lambda.
3. Because functions do not return and everything is allocated from the stack, the stack grows voraciously. When it hits a certain limit, a kind of ephemeral garbage collection takes place: all objects that have been allocated on the stack which are still live are transferred to the heap. Then ... the stack pointer is rewound.
Essentially, the C stack has become a bump allocator in a kind of generational GC.
The old FORTRAN and COBOL language versions were like this.
In ancient FORTRAN programs, the programmer typically computed a maximum possible size for the data and allocated statically in the main program one or more work arrays corresponding to that maximum size, which were either placed in a COMMON block of global variables or they were passed as arguments to the invoked functions and subroutines.
In the functions or subroutines, the work arrays were typically partitioned by allocating in them various local variables.
Overall, this approach was more reliable, because there were no risks of exceeding the memory limits, but it was much more tedious for the programmer, because the worst cases for memory usage had to be accurately predicted.
Well, most importantly, it fixated the program's limits. Got a bigger machine and wanted to tackle greater data-sets? You're out of luck, if you didn't have the source code. Old Unix programs were often like that. It were the GNU counterparts which often did away with such arbitrary limits allowing systems to grow and the software to stay relevant.
The C programming language supports this with the static keyword. Further calls may overwrite the pointed data. I have played with allocating fixed-size data in static locals, but I always found that allocating in the caller does the same job better. For example, compare strerror() with strerror_s(). (A sensible strerror implementation should return a pointer to static immutable data, but the Standard doesn't specify it.)
A procedural language can achieve a statically bounded call stack by restricting self recursion, mutual recursion, and function pointers. I struggle to imagine how a language without a call stack could perform differently or better.
Technically, I don’t know any language whose spec mentions the notion of a call stack. For example, it’s perfectly OK for a conforming C compiler to use a linked list of dynamically allocated activation records (from a standards view point; users of such an implementation may have different opinions)
A conforming C compiler also could choose to only use a call stack for functions that take part in recursive calls or that may get called by multiple threads.
> 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't call the function again, which I think should be possible to enforce via a borrow checker).
If you add multi-threading (something that is almost a must have for languages on powerful CPUs nowadays), I don’t think that’s easy to do.
What about statically determining a fixed number of activation records at compile time? Similar in spirit to security focused languages that require loops to have a statically determined finite bound in order to successfully compile.
As to lifetime after returning, do you really hate continuations that much?
Sure, it may be useful to represent a function's local storage as a first-class concept, and then allow users to instantiate copies of the function at will, if they're willing to allocate more storage themselves, thereby allowing users to either precisely limit the number of instances of a function or otherwise use dynamic allocation to manually reimplement a callstack if they so choose.
> As to lifetime after returning, do you really hate continuations that much?
This is a language that forbids recursion, the functional programmers have already run screaming for the exits. :P
I'd suspect it makes sense in an embedded bare-metal environment where you know all the data structures you might ever have in circulation at once. This sometimes ties into things like explicitly unchanging data as "this can be allocated to ROM" to tightly manage the limited RAM.
(be warned that the old site links are slow, one has to wait for the unarchiving to run, or something.)
Welcome to the old 8-bit C compilers.
Everything was statically allocated so no recursion. The downside is that you can only have a single thread of execution.
It would be interesting to see what that would look like if extended to multiple threads (they would have to be defined/allocated at compile time).
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...
I got to write some exploits for some recently, very fun bug class to exploit.
https://clang.llvm.org/extra/clang-tidy/checks/misc/no-recur...
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 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:
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.
What's missing from this picture is that recursion schemes are not only useful for lists and other sequential things like arrays, vecs, iterators etc, but also for trees and other data types with richer structure. There's some types implementing map here and there (like Rust's Option, which implements map and filter as if it were a list containing 0 or 1 element), but the generic abstraction of "types that have a map operation" for example (the thing Haskell calls Functor) would be really useful to enter mainstream programming some day.
Now, about the more complex recursion schemes: many have too much cognitive weight to be useful. So often a direct recursion will be simpler and easier to understand. But sure, it would be cool if people were more familiar with things like hylomorphisms and such (even if by other name - folds may also be called catamorphisms but nobody calls them that)
I think that the "overton window" of programming constructs is slowly but surely moving towards the more theoretical aspects of functional programming though. So maybe in some decades this stuff will be so familiar that using them won't make code hard to follow.
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?
You cannot org change yourself out of all technical problems.
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.
You don't have stack frame overhead, you can nest arbitrarily, they'll always be more performant. You can peek into the stack to do things recursive functions can't. The optimizer is better at helping you with loops, memoization just becomes a normal cash of intermediate results.
But tools like libexpat are often used in embedded contexts, in 32 bit memory spaces, that don't have that freedom. So it's a relatively serious bug regardless.
The problem to me is that recursive functions should be a special case in the ABI, where a compiler can insert a prelude to the callsite to grow/segment the stack if needed. This is a hard problem once you have references to things on the stack, so I can understand why most ecosystems don't do it - but that doesn't mean it can't be done.
What I'm saying is that stack allocation is still dynamic memory management and in systems where its critical to avoid OOM conditions because of unbounded dynamic memory management you need code with O(1) memory complexity, and that includes the stack. A common mistake I've seen people make is assume that pushing onto the stack isn't memory allocation. It's just cheap memory allocation that can sometimes be assumed to be free, in this case and many others that's a bad assumption.
If you're going to cite this, at least make sure you're not allocating any memory after startup.
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
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 point of tail recursion is that it can be converted into a loop instead of actually recursing.
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.
Presumably you configure resource limits in production but that just means the "correct" process gets unexpectedly killed instead of an arbitrary one.
Code handling arbitrary input needs to carefully limit resource usage. There's no avoiding it.
Consider my jimmies rustled
Let the math to the math guys who never ship a product.
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.
PS: It's not one single function, not direct but indirect recursion.
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 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.
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.
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.
Sounds like a design issue in particular language implementations rather than a problem with the programming technique.
fn recurse (tree) :
for child in tree.children :
recurse(child)
fn recurse(tree, acc = Nil) :
tree.children match
case Cons(head, tail) => recurse(head, tail++acc)
case Nil => acc match
case Cons(head, tail) => recurse(head, tail)
case Nil => ()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
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.
Not every recursion can be transformed into tail recursion. If it's not simply tail recursion (which is the high level language compiler way of implementing the old tried and true assembly language optimization technique of making the last function call be a JMP instead of a JSR followed by an RTS, that I learned from WOZ's Apple ][ 6502 monitor ROM code), you still have to manage the state somewhere. There ain't no such thing as a free lunch.
And if not on the C stack, then it has to be somewhere else, like another stack or linked list, and then you still have to apply your own limits to keep it from being unlimited, so you're back where you started (but in a Sisyphusly tail call recursive way, you still have to solve the problem again).
https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule
>Greenspun's tenth rule of programming "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."
Of course you can always just pass a recursion depth limit parameter down the recursion and stop when it expires, even letting the caller decide how deep a recursion they want to permit, which is easier and safer than using malloc or cons or std::vector to roll your own stack.
Or the compiler could even do that for you, but you still have to figure out how to gracefully bottom out...
So if "Exception Handling" is hopefully failing upward, then "Depthception Handling" is hopelessly failing downward!
Depthception Handling is the vertical reflection of Exception Handling, with "implicit depth" recursion depth passing, like C++'s "implicit this" but deeper, not to be confused with the orthogonal "continuation passing" / "halt passing" dichotomy (passing HALT and CATCHFIRE instructions around but promising to never call them except in fatal emergencies):
"try" / "catch" = An active attempt to solve things.
"giveup" / "bottom" = Passive resignation to inevitability.
"throw" is an emergency exit UP.
"drop" is an emergency slide DOWN.
"try" => "giveup" introduces a futile attempt at unbounded recursion.
"catch" => "bottom" declares a bottoming out handler after a function signature, to guard its body below.
"throw" => "drop" immediately bottoms out from any depth!
fn doomed_recursion()
bottom { println!("Too deep, I give up."); }
{
giveup {
if going_too_deep() {
drop;
}
doomed_recursion();
}
}
fn deep_trouble(depth: Depth)
bottom { println!("I reached depth {} and surrendered.", depth); }
{
giveup depth {
if depth > 10 {
drop;
}
deep_trouble(depth++);
}
}Ok, every recursion in a language that supports programmer-managed state can be transformed into a tail recursion. That still means any recursion in all serious programming languages and most joke programming languages too.
In many contexts, regular process failure is still a vulnerability.
And the stack is (usually) tiny compared to other resources. It doesn't take that many nested calls to get to the bottom of the stack. At least compared to trying to exhaust the heap or keep the CPU busy long enough to cause DoS.
> 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.
>> 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.
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.
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;
}
If recursion traverses an exponentially sized abstract space, it can chew up a lot of processing time before going anywhere near the protective limit.
But the API should have limits. For example, respond 413 Payload Too Large if the request is beyond any normal size for that API. Document the limits to API users. You now have an upper bound of how much nesting can be in the user input.
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.
[1] https://www.researchgate.net/publication/220477862_The_Power...
[2] https://www.qualys.com/2017/06/19/stack-clash/stack-clash.tx...
>> 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.
[1]: https://blog.llvm.org/posts/2021-01-05-stack-clash-protectio...
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).
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.
As to DoS, without looking at the code I'm unclear why various approaches to bounding resource consumption wouldn't have worked. I assume something specific to this library and how it is used must have prevented the obvious approaches. Still, not an issue in the general case.
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.
Re-writing recursive algorithms to be non-recursive typically requires less obvious code, where you make your own ad-hoc stack to keep track of where you are; essentially implementing the call stack manually.
In contexts where DoS or stack smashing is a concern because the input is attacker-controlled, it's often way easier to add a depth parameter and error at a certain depth than to rewrite the naturally recursive algorithm into iterative style. But tree structures are so naturally recursive that it's easy to end up with accidental unbounded recursion in complex real-world situations.
You can manage memory and compute budget so that your cute algo does not go rogue. On top of that very often you don’t have to explore the entire tree, and there is custom logic at each step to decide whether you want to proceed or not with exploration.
Example: depth-first tree walking algorithms. Implicit stack makes it trivial to express as recursion.
It is not smart, or special, or something.
The secret is to check at every step that there is no "he's his own grandpa" loops in the user's tree, where (s)he inadvertently makes one of a person's descendants, also his ancestor. This happens sometimes because re-using the same names can cause confusion.
Recursion is like magic :o)
I don't think we should ban recursions altogether, but remember that there exist associated risks, and consider them.
You just make a call graph where the nodes are functions and directed edges indicate which function calls which. Without recursion function pointers and the like you can compute this exactly and this forms a DAG. Each node is given a weight, which is the amount of local memory that function needs. Start at the entry point function, and compute the longest distance path (using the node weight).
(Fortran programmers are probably wondering how alternate ENTRY statements worked; yes, they had to allocate a word before the ENTRY, and copy whatever jump instruction was placed there by the hardware into the main subroutine's jump word, so that RETURN or END would work for all entry points. Recursive languages like Pascal had to copy that word to and from the stack. Reentrant code had to avoid using the return jump instruction entirely.)
In a language that doesn’t allow recursion, using a call stack still can make sense for the implementation because it allows reuse of memory for local variables between functions that do not call each other, directly or indirectly.
But then, you’re giving up “plus weirdo stuff like the ability to hand out references to local data in functions that have already returned”, although, thinking of it, static analysis could make those locals survive by manipulating the stack pointer (if you have the caller allocate and, reallocate the locals of the called function, the caller can postpone that reallocation if it wants to access the locals of the called function). I’m not sure that weirdo stuff is worth the effort, though. It’s just a weird way to return multiple values from a function.
This is sort of amusingly backwards. On embedded systems where I live, stacks are huge. Thread stacks of 4-16k are routinely the largest single objects the kernel sees in Zephyr. And yes, lots of RTOS apps disallow recursion (Zephyr doesn't, but does gate its use in the core system behind build-time config that can be turned off) because in that world it's hard to provide the guarantees you can get with a 64 bit mmu environment.
But if you are on a modern 64 bit OS, no: stacks are enormous. Many megabytes of mapping is routine. Obviously that's not all going to be faulted in, and most threads won't ever use more than a few kilobytes. But the region reserved for recursive use is extremely large, and unlikely to overflow except in a well-crafted deliberate attack (and even then it generally requires a few bugs in the code; most recursive algorithms are bounded by e.g. maximum tree height or something that is O(logN) and thus can't overflow).
In the general case though, recursion can be tricky to think through, the stack is small, and malicious inputs can be very creative.
This doesn't make sense as a comment, regardless of the the particular conclusion.
To be precise; with precision:
In C (and IIUC now Python, too), a stack frame is created for each function call (unless tail call optimization is applied by the compiler).
To avoid creating an unnecessary stack frame for each recursive function call, instead create a collections.deque and add traversed nodes to the beginning or end enqueued for processing in a loop within one non-recursive function.
Is Tail Call Optimization faster than collections.deque in a loop in one function scope stack frame?
Functional programming with bananas, lenses, envelopes and barbed wire [pdf] (1991) - https://news.ycombinator.com/item?id=31152801 - April 2022 (28 comments)
Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire - https://news.ycombinator.com/item?id=24056901 - Aug 2020 (18 comments)
Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire (1991) [pdf] - https://news.ycombinator.com/item?id=9080933 - Feb 2015 (2 comments)
Functional programming with bananas, lenses, envelopes and barbed wire - https://news.ycombinator.com/item?id=6195603 - Aug 2013 (1 comment)
A lot of people were using GOTO because they wanted (for example) do-while or switch-case, or because they wanted to box up their code into self-contained functional units, but the 8k ROM BASIC they were working with didn't have proper tooling to implement it.
Most modern languages support enough of those features that people aren't simulating them through GOTOs. Recursion schemes have not hit that level of availability and general awareness.
Going back several levels of parents, I note the mention of Haskell-- it feels like the functional programming world does a lot of heavy lifting on new language theory, but it tends to remain cloistered there for decades until people figure out how to bolt it into something that looks more like Algol or C than Lisp.
You say this like these are fundamentally separable things? I find this comment deeply confusing. Every single real software stack ever has a layer where the sausage gets made so to speak.
What is the outdated programming practice at fault here?
Google protobuffers have buried deep within at least their C++ parser an arbitrary hard limit for nesting depth (I think it may be 32). It's annoying when you hit it, but it's there for a reason.
I feel like this is similar in spirit to saying "guarding against infinite loops requires both ...".
Where resource consumption is concerned, as you pointed out you can track that manually. Presumably you have to do that anyway, since the iterative case will also need to give up and fail the task at some point.
I really don't see where recursion itself introduces an issue here. I guess if you expect to pass through a great many nodes that don't otherwise trigger resource allocation except for the stack frame, and the compiler can't optimize the activation records away, it could be problematic. That's pretty specific though. Is that really the case for a typical parser?
The stack frame also holds local variables. It's not just a return address. If your function requires 3 local variables then each call requires 3 stack slots.
There's no realistic technology stack out there that does what you want.
Growable stacks have been around for decades, it's far away from research language territory.
The real benefit is not to handle the worst case/OOM condition that a big enough callstack gives you. It's to make the default stack size much, much smaller for the common case where you don't need it at all (or want to shrink it later). Growable stacks use less memory on average than your typical embedded device because they can start in the dozens of bytes, instead of requiring kilo/mega bytes of stack space (allocated, not just reserved). It's kinda the only way you can make a runtime scale to millions of concurrent call stacks.
Go now copies stacks, and Rust only has segments if you deliberately box up a recursive call.
And it gets more complex when there's a bunch of state that requires you to save the stack frame in your explicit stack.
If the language runtime has growable stacks you're just making the code more complex.
You are incorrect about tail recursion (look at continuation-passing style; it transforms any program to tail recursive form) but you are getting at the core of the issue here. 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.
In other words, you can shift memory usage from the stack to the heap, but if a client can give you an unbounded amount of memory consuming work you are screwed either way. Ultimately the problem has nothing to do with recursion.
But you're right, that's what I'm getting at. Recursion is an inherent semantic and whether you make the stack explicit or implicit doesn't get rid of memory allocation problems. I said in another comment that stack allocation is still dynamic memory management, it's just something many people take for granted.
Altough, technically my "solution" would work for making it tail calls anyways, by replacing the looping part with tail calls. But I digrees
Sure, in toy examples. But you can't actually do this in a nontrivial codebase that wasn't written to support it from the ground up.
> 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.
Everything is easy when you don't spend 5 minutes thinking about the possible problems with it, much less actually implement the idea you're proposing.
> But you can't actually do this in a nontrivial codebase that wasn't written to support it from the ground up.
In the case where this is considered critical for whatever reason, you absolutely could have a somewhat overzealous detector that failed the compilation if triggered. It doesn't need to support every last edge case. You would then address this just as you would any other compiler error - by remediating the failures one by one.
If management doesn't want to pay you to do that then perhaps the requirement of "absolutely no recursion ever" wasn't actually so critical.
From an architectural standpoint, the main challenge is layering everything properly so you don't have any circular dependencies, even in untaken branches. Again, how hard this is to achieve depends on the original design, but it's not like circular-dependency-avoidance is something that no one's done before.
That's still overly optimistic when you're talking about something that no-one's ever done.
> You would then address this just as you would any other compiler error - by remediating the failures one by one.
And what do you do in the meantime? Or when you can't see how to fix one of the cases? When a new feature introduces an error, you don't push out the new feature until you can fix the error, possibly never. When a compiler upgrade introduces an error all over your codebase (that you can't fix with something like a one-liner regex), you turn it off (in the best case you turn it into a warning that you then maybe gradually fix), and if you can't turn it off you don't do the compiler upgrade.
if(fptr == x || fptr == y)
__builtin_unreachable()
if(fptr != z && fptr != w)
__builtin_unreachable()
enum { CALL_Z, CALL_W };
int call_z_or_w(int which, int arg) {
switch (which) {
case CALL_Z: return z(arg);
case CALL_W: return w(arg);
default: __builtin_unreachable();
}
}
def fib(n, acc1 = 0, acc2 = 1) =
n match
case 0 => 0
case 1 => acc2
case _ => fib(n-1, acc2, acc1+acc2)
"Programs can be automatically transformed ... to CPS. ... Every call in CPS is a tail call"
At least start with a rigorous, well-specified, robust, high-performance, complete implementation of Common Lisp, if you're going to recurse infinitely.
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.
For this particular CVE? I'm not clear. Possibly none. The writeup didn't provide sufficient detail and I haven't bothered to wade through the code. There may well be a reason recursion won't work here but it certainly isn't general.
I'd be curious to know in this case why resource limits couldn't be enforced for the recursive implementation but could be for the iterative one.
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.
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 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.
> Careless recursion in C... is obviously bad
> 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.
Doing it all in your VM/runtime, so you can bail the computation with an exception, is more challenging.
Is forking a new process on each call to a recursive function practical?
And hence the "kinda" in async Rust. While boxed futures can be thought of as a segmented stack the literal callstack is not, which can still give you a stack overflow with a bunch of nested poll() calls.
Depends on what you specifically mean by "growable": when a goroutine runs out of stack space, a new one that's larger (iirc double sized) is created, the old one is copied into it, and then execution can resume.
I can see the argument both ways.
> which can still give you a stack overflow
For sure.
The issue is either:
* whatever the parser is doing is already trivially 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.
Either way it is not the fault of recursion.
The whole point of the article is about the dangers of unbounded recursion, because of its resulting unbounded memory allocation, no matter at what level or by whom that recursion is implemented.
Yes, the unbounded memory allocation is the fault of recursion, even if you're implementing the recursion yourself with dynamic memory allocations, via malloc, std::vector, dynamically allocating continuations to pass with CONS, or whatever. It's still recursion, and still unbounded dynamic memory allocation, and still dangerous.
If the ALGORITHM requires recursion that can't be optimized away as tail recursion, then it requires memory allocation. You HAVE to store the state SOMEWHERE. You can't take the recursion and unbounded memory allocation requirement out of the algorithm by using a different language, compiler, or writing it in assembly language. It's still a recursive ALGORITHM no matter how you or the compiler chose to implement it.
It's so ironic that I have to explain this so many times, because you keep recursing every time and trying to blame the problem on something else other than recursion, when it's coming from the ALGORITHM not the IMPLEMENTATION or the programmer's ability, and it's an essential part of that algorithm.
You're just playing a recursive game of whack-a-mole trying to erroneously shift responsibility away from recursion onto something else, or writing checks from one bank account and depositing them in another bank account to pay the credit card bill you used to fill another bank account you wrote checks on to pay yet another credit card bill, just to defer having to pay your first credit card bill. And you can't shoot somebody and get away with it by declaring "people don't kill people, guns kill people". Recursion kills -- the title of the article!
Yes I know you can keep recursing infinitely trying to blame something else each time than recursion, but the only time you're going to bottom out and stop recursing is when you realize that recursive algorithms that can't be simplified to tail call recursion always require memory allocation, and unless you explicitly bound them with some limit, they require unbounded memory allocation, because there is STILL no such thing as a free lunch, and continuations are not magic unicorns.
Continuation passing is NOT some magic bullet that can automatically optimize any program so it doesn't need to allocate memory for non-tail recursion. You STILL have to allocate the continuations, they don't come from nowhere, they consume memory too. So triumphantly bringing it up as if it solves the problem or indemnifies recursion from blame is a non sequitur.
It's no comfort to the user that the program they're running exploded because the programmer chose to use malloc or explicit continuation passing, instead of the built-in compiler support for recursion. Recursion is still to blame, and it comes from the ALGORITHM not the IMPLEMENTATION.
When an algorithm requires x bytes of memory for a given input it shouldn't matter whether a given implementation of that algorithm uses x bytes of implicit stack from recursion, x bytes of heap allocated with malloc, or something else; however unfortunately in various poor programming language implementations this does make a big difference, such as the case described in the article. The problem is not recursion nor the algorithm, the problem is the poor implementation of recursion in their C compiler, and as such it can be avoided by expressing the same algorithm without that C recursion (which is trivial). Even in the unlikely event that such an expression exhausted available memory (implausible), it would not be a security issue.
So every recursion in a language that supports programmer-managed state and memory allocation can be transformed into a tail recursion. That still means any recursion in all serious programming languages and most joke programming languages too.
Please explain how your hand rolled implementation of recursion using malloc is better than every C compiler's. Show us the code! Have you opened an issue on GCC or Clang so they can fix their buggy C compilers with your brilliant secure ground-breaking memory-less law-of-thermodynamics-defying recursion algorithm? There may be a Turing Award in it for you!
Because I don't use "the" stack and thus don't have stack overflows.
> Have you opened an issue on GCC or Clang so they can fix their buggy C compilers with your brilliant secure ground-breaking memory-less law-of-thermodynamics-defying recursion algorithm? There may be a Turing Award in it for you!
Of course not, it's just trading stack for heap like you can find in any basic CS textbook. But the heap can generally safely grow bigger than the stack and "overflowing" the heap is not a security vulnerability (you do check the return value of malloc, right?). Again, this is the opposite of Turing Award territory, it's all CS 101 stuff.
GCC and Clang prioritise performing well on microbenchmarks over making it practical to implement programs without security vulnerabilities. This is also sadly well known.