12 ms·

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

162 points by spyc 2y ago

hughw 2y ago
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.
- deleted 2y ago
  [deleted]
- Etheryte 2y ago
  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.
  - MattPalmer1086 2y ago
    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.
    - spyc 2y ago
      Correct.
    - Etheryte 2y ago
      I did not mention memory once anywhere in my comment?
      - BalinKing 2y ago
        I think "space" (i.e. in "run out of space before you can terminate") is most naturally interpreted as referring to memory.
        kazinator 2y ago
        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.
        jraph 2y ago
        Not necessarily. If you are computing an aggregation for instance, if your computation is recursive and not tail call optimized, it may overflow the stack but the fixed version will not use additional memory for each iteration. Otherwise, indeed stack is memory, but the memory in general is usually way less limited than the stack and also running out of memory doesn't have the same security implications as overflowing an unprotected stack. And, unless you manage to encode everything in the stack, your iterative version will probably take the same amount of memory as your non-optimized recursive version, minus the space used for the stack.
        MattPalmer1086 2y ago
        True, I'd just tend to call exceeding the stack limit a stack overflow, rather than the more generic running out of space.
      - kazinator 2y ago
        Someone who doesn't believe that stack is "space" will not believe that it's "memory" either. :)
        hughw 2y ago
        Tail call optimization uses no stack at all
    - pajko 2y ago
      Exactly. A stack overflow caused by recursion more likely converts to an endless loop. Nothing saves a bad code design.
  - ndriscoll 2y ago
    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.
- spyc 2y ago
  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.
  - deleted 2y ago
    [deleted]
  - fc417fc802 2y ago
    That really depends. Segmented stack makes it equivalent to heap. Heap might or might not fail gracefully. If the OS permits overcommit and you've mapped a large region, then an arbitrary process on the machine could trigger the OOM when writing to a supposedly allocated (but not previously written) piece of memory. 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.
baggy_trough 2y ago
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.
- maxbond 2y ago
  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.
- fpoling 2y ago
  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.
- spyc 2y ago
  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.
  - iforgotpassword 2y ago
    Sure if it's indirect I agree it will get messy fast with a dozen functions suddenly needing to handle an additional parameter, but unrelated to that... I'd really like to know who needs recursion for this that's deeper than 3 or 4 levels. What's the use case? Such xml surely would be unreadable and unwritable to humans, but if it's used as some form of exchange format between systems, what would that be? How would it end up with such deeply nested entities? It sounds like something you deliberately implement that way to show how "smart" you are, but not "hey that seems the reasonable thing to do here". This makes me wonder: does any of the popular xml libs have a sort of safe mode, where custom entities and similar features are disabled, those schema urls ignored, and namespaces just flattened (and whatever else I forgot or don't even know about)? You know for when I know I only need to parse simple xml files that should contain a couple plain tags and attributes, and want to reduce attack surface.
mightybyte 2y ago
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.
- timewizard 2y ago
  Using recursive techniques to parse potentially hostile inputs kills.
  - fc417fc802 2y ago
    Parsing anything from a potential adversary needs to account for failure. Unbounded recursion is secure (ie fails safely) if the compiler is working properly. 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.
    - shadowgovt 2y ago
      Guarding against unbounded recursion requires both compiler support and runtime environment support: you have to use enough resources to handle legitimate queries, but small enough memory constraints that a "query of death" doesn't kill nodes that are expensive to reactivate. Even then, by their very nature queries-of-death are usually hard to detect and a much simpler solution is something you can do in the static space, such as put an arbitrary hard-bound on recursion depth far below your resource constraints so you can fail the query without losing the whole processing node. 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.
jasonthorsness 2y ago
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-recursion.html https://clang.llvm.org/extra/clang-tidy/checks/misc/no-recur...
- pcwalton 2y ago
  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.)
  - LegionMammal978 2y ago
    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.
    - PhilipRoman 2y ago
      You could probably restrict function pointer values with something like this: if(fptr == x || fptr == y) __builtin_unreachable() Or... if(fptr != z && fptr != w) __builtin_unreachable() But I'm not sure how well today's compilers can take advantage of this. You'd need a strict mode, where any function pointer is assumed to be the worst case. At that point might as well go for a real proof assistant
preinheimer 2y ago
I think this was a really brave call for help from the writer. They needed help and they asked for it, from strangers!
- spyc 2y ago
  Thank you!
BradSwain 2y ago
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-white-paper https://resources.trailofbits.com/input-driven-recursion-whi...
- spyc 2y ago
  Thanks for sharing that research!
groos 2y ago
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.
- kcolford 2y ago
  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.
  - kazinator 2y ago
    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.
- dataflow 2y ago
  >> 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.
noelwelsh 2y ago
> 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.
- mhitza 2y ago
  > 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.
  - digibeet 2y ago
    Ah, I find myself in similar waters. In your experience does the [@@tailcal] annotation not cover enough of the cases?
    - mhitza 2y ago
      I'm aware of the tailcall annotation but I didn't have to rely on it yet. For me the benefit of picking up OCaml is that I can do imperative constructs on a first pass (mutation and for loops), and refactor it after to pure code, when needed.
  - noelwelsh 2y ago
    Agreed, and this is why some languages have annotations that ask the compiler to check a function is indeed tail recursive. However I don't think that is the case in Expat. If the algorithm is tail recursive, but accidentally not expressed in that way, its a simple (but perhaps tedious to manually apply) program transform to express it in a way that does not consume unbounded memory (heap or stack). From the scant details on the fix in the article it appears the parsing algorithm itself was completely changed. ("The third variant "Parameter entities" reuses ... the same mechanism of delayed interpretation.") If this is the case the issue is not recursion, as the original parsing algorithm would consume unbounded resources no matter how it was expressed in C.
kelseyfrog 2y ago
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.
- TZubiri 2y ago
  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?
  - kelseyfrog 2y ago
    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.
    - TZubiri 2y ago
      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.
      - ndriscoll 2y ago
        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.
TZubiri 2y ago
https://en.wikipedia.org/wiki/Tragedy_of_the_commons 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 https://en.wikipedia.org/wiki/Free-rider_problem This seems like a much more specific name for the problem
- deleted 2y ago
  [deleted]
sherburt3 2y ago
> Please leave recursion to math and keep it out of (in particular C) software: it kills and will kill again. Consider my jimmies rustled
- deleted 2y ago
  [deleted]
bahorn 2y ago
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.
thayne 2y ago
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.
- deleted 2y ago
  [deleted]
whatever1 2y ago
I don’t understand the obsession of people with recursion. Sure it’s a cute math trick, it makes you feel smart, but it is an undebuggable mess with a ton of gotchas that lead to stack overflows. Let the math to the math guys who never ship a product.
- vkazanov 2y ago
  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.
- toolslive 2y ago
  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".
- darkamaul 2y ago
  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.
- mort96 2y ago
  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.
mrkeen 2y ago
Yet another article linking to the '10 rules of safety critical development' as a way to bash recursion. If you're going to cite this, at least make sure you're not allocating any memory after startup.
DonHopkins 2y ago
There's a wonderful DDJ interview with James Clark (author of expat and developer many other open source sgml and xml standards and tools like Relax/NG, and even horrible ones like XSLT ;) called "A Triumph of Simplicity: James Clark on Markup Languages and XML", in which he explains how a standard has failed if everyone just uses the reference implementation, because the point of a standard is to be crisp and simple enough that many different implementations can interoperate perfectly. A Triumph of Simplicity: James Clark on Markup Languages and XML: https://www.drdobbs.com/a-triumph-of-simplicity-james-clark-on-m/184404686 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 https://news.ycombinator.com/item?id=16226209 >Reading documents from 20 years ago is a mixed bag. Links usually fail horribly, which was something Xanadu was trying to solve, but I'm not convinced they could have solved it so well that 20-year-old links would still actually work in practice. [...] >In the ideal world we would all be using s-expressions and Lisp, but now XML and JSON fill the need of language-independent data formats. >Not trying to defend XSLT (which I find to be a mixed bag), but you're aware that it's precursor was DSSSL (Scheme), with pretty much a one-to-one correspondence of language constructs and symbol names, aren't you? >The mighty programmer James Clark wrote the de-facto reference SGML parser and DSSSL implementation, was technical lead of the XML working group, and also helped design and implement XSLT and XPath (not to mention expat, Trex / RELAX NG, etc)! It was totally flexible and incredibly powerful, but massively complicated, and you had to know scheme, which blew a lot of people's minds. But the major factor that killed SGML and DSSSL was the emergence of HTML, XML and XSLT, which were orders of magnitude simpler. James Clark: http://www.jclark.com/ http://www.jclark.com/ https://en.wikipedia.org/wiki/James_Clark_(programmer) https://en.wikipedia.org/wiki/James_Clark_(programmer)
mmsc 2y ago
Great article! Is the code or technique used to fix this easily available somewhere?
- hannob 2y ago
  Here's the relevant pull request: https://github.com/libexpat/libexpat/pull/973 https://github.com/libexpat/libexpat/pull/973
DonHopkins 2y ago
I hope the term "deyodawgification" enters the pantheon of elegant code purification terms of art, alongside the classics like "degotofying", "deCOMtamination", and "outparamdelling". https://knowyourmeme.com/memes/xzibit-yo-dawg https://knowyourmeme.com/memes/xzibit-yo-dawg https://wiki.mozilla.org/Gecko:DeCOMtamination_Algorithm https://wiki.mozilla.org/Gecko:DeCOMtamination_Algorithm https://bugzilla.mozilla.org/show_bug.cgi?id=455943 https://bugzilla.mozilla.org/show_bug.cgi?id=455943 https://news.ycombinator.com/item?id=22708241 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...
- ggambetta 2y ago
  DTDetox
- immibis 2y ago
  "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.
kibwen 2y ago
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. This obviously places a lot of limits on language design, but in return you get a statically-guaranteed upper bound on memory usage, plus weirdo stuff like the ability to hand out references to local data in functions that have already returned (which remains valid as long as you don't call the function again, which I think should be possible to enforce via a borrow checker).
- Someone 2y ago
  > 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.
  - layer8 2y ago
    I don’t think that “call stack” implies “contiguous memory”, or “what the operating system might think of a process call stack”, so a linked list would still qualify as a call stack. While the C standard doesn’t use the word “stack”, it explicitly requires support for recursive function calls, and the related semantics it specifies with regard to automatic storage duration effectively describe a stack.
    - Someone 2y ago
      If you want to ignore such implementation details, you’re basically saying you want to see a language that doesn’t allow recursion, or maybe even one that allows recursion, but only in such a way that the compiler can compute the maximum amount of memory needed for activation records. 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.
duped 2y ago
If we had standardized growable call stacks then this wouldn't happen
- ajross 2y ago
  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.
  - BradSwain 2y ago
    > while stack clashing was considered and is a theoretical possibility — denial of service was considered to be the realistic impact. 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.
    - ajross 2y ago
      > And the stack is (usually) tiny 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).
damnitbuilds 2y ago
How awful. Did anyone call The Recurse Center? https://news.ycombinator.com/item?id=43361773 https://news.ycombinator.com/item?id=43361773
deleted 2y ago
[deleted]

162 points by spyc 2y ago

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.

deleted 2y ago
[deleted]
Etheryte 2y ago
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.
- MattPalmer1086 2y ago
  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.
  - spyc 2y ago
    Correct.
  - Etheryte 2y ago
    I did not mention memory once anywhere in my comment?
    - BalinKing 2y ago
      I think "space" (i.e. in "run out of space before you can terminate") is most naturally interpreted as referring to memory.
      - kazinator 2y ago
        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.
        jraph 2y ago
        Not necessarily. If you are computing an aggregation for instance, if your computation is recursive and not tail call optimized, it may overflow the stack but the fixed version will not use additional memory for each iteration. Otherwise, indeed stack is memory, but the memory in general is usually way less limited than the stack and also running out of memory doesn't have the same security implications as overflowing an unprotected stack. And, unless you manage to encode everything in the stack, your iterative version will probably take the same amount of memory as your non-optimized recursive version, minus the space used for the stack.
        MattPalmer1086 2y ago
        True, I'd just tend to call exceeding the stack limit a stack overflow, rather than the more generic running out of space.
    - kazinator 2y ago
      Someone who doesn't believe that stack is "space" will not believe that it's "memory" either. :)
      - hughw 2y ago
        Tail call optimization uses no stack at all
  - pajko 2y ago
    Exactly. A stack overflow caused by recursion more likely converts to an endless loop. Nothing saves a bad code design.
- ndriscoll 2y ago
  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.
spyc 2y ago
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.
- deleted 2y ago
  [deleted]
- fc417fc802 2y ago
  That really depends. Segmented stack makes it equivalent to heap. Heap might or might not fail gracefully. If the OS permits overcommit and you've mapped a large region, then an arbitrary process on the machine could trigger the OOM when writing to a supposedly allocated (but not previously written) piece of memory. 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.

baggy_trough 2y ago

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.

maxbond 2y ago
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.
fpoling 2y ago
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.
spyc 2y ago
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.
- iforgotpassword 2y ago
  Sure if it's indirect I agree it will get messy fast with a dozen functions suddenly needing to handle an additional parameter, but unrelated to that... I'd really like to know who needs recursion for this that's deeper than 3 or 4 levels. What's the use case? Such xml surely would be unreadable and unwritable to humans, but if it's used as some form of exchange format between systems, what would that be? How would it end up with such deeply nested entities? It sounds like something you deliberately implement that way to show how "smart" you are, but not "hey that seems the reasonable thing to do here". This makes me wonder: does any of the popular xml libs have a sort of safe mode, where custom entities and similar features are disabled, those schema urls ignored, and namespaces just flattened (and whatever else I forgot or don't even know about)? You know for when I know I only need to parse simple xml files that should contain a couple plain tags and attributes, and want to reduce attack surface.

mightybyte 2y ago

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.

timewizard 2y ago
Using recursive techniques to parse potentially hostile inputs kills.
- fc417fc802 2y ago
  Parsing anything from a potential adversary needs to account for failure. Unbounded recursion is secure (ie fails safely) if the compiler is working properly. 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.
  - shadowgovt 2y ago
    Guarding against unbounded recursion requires both compiler support and runtime environment support: you have to use enough resources to handle legitimate queries, but small enough memory constraints that a "query of death" doesn't kill nodes that are expensive to reactivate. Even then, by their very nature queries-of-death are usually hard to detect and a much simpler solution is something you can do in the static space, such as put an arbitrary hard-bound on recursion depth far below your resource constraints so you can fail the query without losing the whole processing node. 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.

jasonthorsness 2y ago

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-recursion.html https://clang.llvm.org/extra/clang-tidy/checks/misc/no-recur...

pcwalton 2y ago
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.)
- LegionMammal978 2y ago
  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.
  - PhilipRoman 2y ago
    You could probably restrict function pointer values with something like this: if(fptr == x || fptr == y) __builtin_unreachable() Or... if(fptr != z && fptr != w) __builtin_unreachable() But I'm not sure how well today's compilers can take advantage of this. You'd need a strict mode, where any function pointer is assumed to be the worst case. At that point might as well go for a real proof assistant

preinheimer 2y ago

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

spyc 2y ago
Thank you!

BradSwain 2y ago

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-white-paper https://resources.trailofbits.com/input-driven-recursion-whi...

spyc 2y ago
Thanks for sharing that research!

groos 2y ago

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.

kcolford 2y ago
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.
- kazinator 2y ago
  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.
dataflow 2y ago
>> 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.

noelwelsh 2y ago

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

mhitza 2y ago
> 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.
- digibeet 2y ago
  Ah, I find myself in similar waters. In your experience does the [@@tailcal] annotation not cover enough of the cases?
  - mhitza 2y ago
    I'm aware of the tailcall annotation but I didn't have to rely on it yet. For me the benefit of picking up OCaml is that I can do imperative constructs on a first pass (mutation and for loops), and refactor it after to pure code, when needed.
- noelwelsh 2y ago
  Agreed, and this is why some languages have annotations that ask the compiler to check a function is indeed tail recursive. However I don't think that is the case in Expat. If the algorithm is tail recursive, but accidentally not expressed in that way, its a simple (but perhaps tedious to manually apply) program transform to express it in a way that does not consume unbounded memory (heap or stack). From the scant details on the fix in the article it appears the parsing algorithm itself was completely changed. ("The third variant "Parameter entities" reuses ... the same mechanism of delayed interpretation.") If this is the case the issue is not recursion, as the original parsing algorithm would consume unbounded resources no matter how it was expressed in C.

kelseyfrog 2y ago

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.

TZubiri 2y ago
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?
- kelseyfrog 2y ago
  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.
  - TZubiri 2y ago
    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.
    - ndriscoll 2y ago
      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.

TZubiri 2y ago

https://en.wikipedia.org/wiki/Tragedy_of_the_commons 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 https://en.wikipedia.org/wiki/Free-rider_problem This seems like a much more specific name for the problem

deleted 2y ago
[deleted]

sherburt3 2y ago

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

deleted 2y ago
[deleted]

bahorn 2y ago

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.

thayne 2y ago

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.

deleted 2y ago
[deleted]

whatever1 2y ago

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

vkazanov 2y ago
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.
toolslive 2y ago
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".
darkamaul 2y ago
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.
mort96 2y ago
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.

mrkeen 2y ago

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

DonHopkins 2y ago

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

mmsc 2y ago

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

hannob 2y ago
Here's the relevant pull request: https://github.com/libexpat/libexpat/pull/973 https://github.com/libexpat/libexpat/pull/973

DonHopkins 2y ago

I hope the term "deyodawgification" enters the pantheon of elegant code purification terms of art, alongside the classics like "degotofying", "deCOMtamination", and "outparamdelling". https://knowyourmeme.com/memes/xzibit-yo-dawg https://knowyourmeme.com/memes/xzibit-yo-dawg https://wiki.mozilla.org/Gecko:DeCOMtamination_Algorithm https://wiki.mozilla.org/Gecko:DeCOMtamination_Algorithm https://bugzilla.mozilla.org/show_bug.cgi?id=455943 https://bugzilla.mozilla.org/show_bug.cgi?id=455943 https://news.ycombinator.com/item?id=22708241 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...

ggambetta 2y ago
DTDetox
immibis 2y ago
"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.

kibwen 2y ago

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. This obviously places a lot of limits on language design, but in return you get a statically-guaranteed upper bound on memory usage, plus weirdo stuff like the ability to hand out references to local data in functions that have already returned (which remains valid as long as you don't call the function again, which I think should be possible to enforce via a borrow checker).

Someone 2y ago
> 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.
- layer8 2y ago
  I don’t think that “call stack” implies “contiguous memory”, or “what the operating system might think of a process call stack”, so a linked list would still qualify as a call stack. While the C standard doesn’t use the word “stack”, it explicitly requires support for recursive function calls, and the related semantics it specifies with regard to automatic storage duration effectively describe a stack.
  - Someone 2y ago
    If you want to ignore such implementation details, you’re basically saying you want to see a language that doesn’t allow recursion, or maybe even one that allows recursion, but only in such a way that the compiler can compute the maximum amount of memory needed for activation records. 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.

duped 2y ago

If we had standardized growable call stacks then this wouldn't happen

ajross 2y ago
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.
- BradSwain 2y ago
  > while stack clashing was considered and is a theoretical possibility — denial of service was considered to be the realistic impact. 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.
  - ajross 2y ago
    > And the stack is (usually) tiny 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).

damnitbuilds 2y ago

How awful. Did anyone call The Recurse Center? https://news.ycombinator.com/item?id=43361773 https://news.ycombinator.com/item?id=43361773

deleted 2y ago

[deleted]