Recursion kills: The story behind CVE-2024-8176 in libexpat (opens in new tab)

"Soft lock picking" was the title of a YouTube series about strange ways out of impossible save files (soft locks, as opposed to hard locks where the game freezes) in video games.

DTDetox

Thank you!

There's prior art in this, very very old prior art. If you check out the first volume of The Art of Computer Programming, it uses a fictitious architecture called MIX. I understand that while it was fictitious, it was made to be similar enough to contemporary architectures. In it there are no special stack manipulation instructions, because there is no first-class notion of a stack! Functions used global variables for their scratch space. To call a function you would just jump to that address. Of course that function needed to know where to jump back to when complete. To do that, before jumping, the caller would WRITE THE RETURN ADDRESS TO THE JUMP INSTRUCTION AT THE END OF THE FUNCTION. This seems kind of insane in the modern day (function calls requiring self-modifying code!) but it meant you could implement functions without needing even a single extra word of storage space, and all you really gave up was recursion. I believe the original Fortran and some other older languages were originally implemented this way.

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.

As others have pointed out, that's pretty much how things originally started. A more recent example I remember is the Action! programming language for Atari 8-bit computers[1], an Algol descendent for 6502 with static activation frames.

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)

> I'm interested in examining the idea of a programming language that eschews the notion of a callstack

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.

That programming language exists.

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.

>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).

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.

> I'm interested in examining the idea of a programming language that eschews the notion of a callstack

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.

> single fixed activation record per function

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?

Does it require a new language, or could it be enforced by simple discipline or linting?

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.

related thoughts perhaps? http://lambda-the-ultimate.org/node/5555

(be warned that the old site links are slow, one has to wait for the unarchiving to run, or something.)

> I'm interested in examining the idea of a programming language that eschews the notion of a callstack and returns to having a single fixed activation record per function.

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).

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.

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.

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.

It's not ambitious enough. This 'solution' would be someone else's problem to be avoided at all cost.

Thanks for sharing that research!

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.)

Note, mainstream programming already has widespread use of a bunch of recursion schemes, like map, filter, and fold (also called reduce). It's generally accepted that using map and filter leads to code much easier to understand and modify. Fold is a tiny bit more complicated but generally speaking it is worth it, but there is still some room for specialized folds like a "sum" operation to make code simpler. (map and filter are also special cases of folds, but that's not an interesting observation)

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.

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?

> 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. 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

    fn recurse (tree) :
        for child in tree.children :
            recurse(child)

how do you make this tail recursive?

> 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

>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.

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();
      }
  }

And you can even bind the depth for explicit depth monitoring and control:

  fn deep_trouble(depth: Depth)
  bottom { println!("I reached depth {} and surrendered.", depth); }
  {
      giveup depth {
          if depth > 10 {
              drop;
          }
          deep_trouble(depth++);
      }
  }

The fact that call depth is finite should basically kill the use of recursion in every codebase in favor of an explicit stack data structure. They're better in every way except as a way to confuse new CS students by hiding the very much lack of magic that underpins them.

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.

We did. All "big" OSes have runtimes that put stacks in isolated (and very large) areas, with a guaranteed guard region at the bottom. An attack on stack bounds in Linux or Windows or OS X requires a very large depth, and will end with a regular process failure (a segfault, basically) and not a memory corruption bug.

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.

Here's the relevant pull request: https://github.com/libexpat/libexpat/pull/973

>> 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.

> 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.

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.

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...

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.

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.

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.

I use recursion a fair bit just because it's the easiest solution that requires the least thought. If I have a tree structure from e.g a JSON parser, or a directory tree, or an HTML node tree, what more debuggable options are there, realistically?

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.

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.

If your data structures are recursive, it makes sense your algorithms are too. It makes the code tidy and simpler to reason about. Plenty of times your code becomes "obviously correct".

I write a genealogy app (family history). Recursion is the foundation of the code, and permeates everywhere. The call stack can go 200 deep or more (~4,000 yrs). The code has been successfully running on millions of desktops for thirty years, and has never caused a crash or infinite loop because of recursion.

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)

Recursions are super useful for dealing with certain data types, notably nested grammar parsing. Sure, it has gotcha, but that can be extremely readable.

I don't think we should ban recursions altogether, but remember that there exist associated risks, and consider them.

The alternative is just recursion with more steps