5 ms·

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 k

by 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.
- rendaw 2y ago
  I might not entirely understand, but >> denial of service was considered to be the realistic impact is in the article as justification for why this has low criticality and therefore isn't subject to the 90 day disclosure timeline. I.e. it's _limiting_ the predicted impact. I assumed GP was referring to the other more critical risk, stack clashing, which I guess could lead to RCE? not being an issue on modern OS's.
  - dataflow 2y ago
    The article basically said: "Letting your get killed this way would practically lead to DoS attacks (a security issue), therefore [conclusion]." The response was basically: "Actually, on modern OSes, your application gets killed, unlike on embedded systems. Therefore, [opposite conclusion]." This doesn't make sense as a comment, regardless of the the particular conclusion.
BradSwain 2y ago
> 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.
- kazinator 2y ago
  You can fairly easily recurse with a context argument in which you maintain a depth count. int recursive_fun(rec_context *ctx, ...) { int res = 0; if (++ctx->depth > REC_LIMIT) return ERROR_RECURSION_LIMIT; ... res = recursive_fun(ctx, ...); out: ctx->depth--; return res; } However, a problem with recursion might be something other than the maximum depth reached. If recursion traverses an exponentially sized abstract space, it can chew up a lot of processing time before going anywhere near the protective limit.
  - knome 2y ago
    Which is why it's reasonable to have configurable limits for both processing space and time in anything handling untrusted data.
    - kazinator 2y ago
      Unixes give us that. You have to fork the computation to have it contained in its own process, whose run-time, virtual memory limit, and stack depth you can control. Doing it all in your VM/runtime, so you can bail the computation with an exception, is more challenging.
      - BradSwain 2y ago
        > Unixes give us that. You have to fork the computation to have it contained in its own process Is forking a new process on each call to a recursive function practical?
spyc 2y ago
"Quickly kill the process" is still a denial of service security problem.
skupig 2y ago
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).
deleted 2y ago
[deleted]

by groos 2y ago

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.

rendaw 2y ago
I might not entirely understand, but >> denial of service was considered to be the realistic impact is in the article as justification for why this has low criticality and therefore isn't subject to the 90 day disclosure timeline. I.e. it's _limiting_ the predicted impact. I assumed GP was referring to the other more critical risk, stack clashing, which I guess could lead to RCE? not being an issue on modern OS's.
- dataflow 2y ago
  The article basically said: "Letting your get killed this way would practically lead to DoS attacks (a security issue), therefore [conclusion]." The response was basically: "Actually, on modern OSes, your application gets killed, unlike on embedded systems. Therefore, [opposite conclusion]." This doesn't make sense as a comment, regardless of the the particular conclusion.

BradSwain 2y ago

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

kazinator 2y ago
You can fairly easily recurse with a context argument in which you maintain a depth count. int recursive_fun(rec_context *ctx, ...) { int res = 0; if (++ctx->depth > REC_LIMIT) return ERROR_RECURSION_LIMIT; ... res = recursive_fun(ctx, ...); out: ctx->depth--; return res; } However, a problem with recursion might be something other than the maximum depth reached. If recursion traverses an exponentially sized abstract space, it can chew up a lot of processing time before going anywhere near the protective limit.
- knome 2y ago
  Which is why it's reasonable to have configurable limits for both processing space and time in anything handling untrusted data.
  - kazinator 2y ago
    Unixes give us that. You have to fork the computation to have it contained in its own process, whose run-time, virtual memory limit, and stack depth you can control. Doing it all in your VM/runtime, so you can bail the computation with an exception, is more challenging.
    - BradSwain 2y ago
      > Unixes give us that. You have to fork the computation to have it contained in its own process Is forking a new process on each call to a recursive function practical?

spyc 2y ago

"Quickly kill the process" is still a denial of service security problem.

skupig 2y ago

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

deleted 2y ago

[deleted]