CVE-2019-6293: Stack Comsumption Problem Caused By the mark_beginning_as_normal Function Making Recursive Calls to Itself · Issue #414 · westes/flex

We can directly look at the snippet code of nfa.c to see if it is possible to have infinite recursion. Intuitively, in some cases, function mark_beginning_as_normal shows the behavior of recursive calls.

void    mark_beginning_as_normal (int mach) {
    switch (state_type[mach]) {
    case STATE_NORMAL:
        /* Oh, we've already visited here. */
        return;

    case STATE_TRAILING_CONTEXT:
        state_type[mach] = STATE_NORMAL;

        if (transchar[mach] == SYM_EPSILON) {
            if (trans1[mach] != NO_TRANSITION)
                mark_beginning_as_normal (trans1[mach]);

            if (trans2[mach] != NO_TRANSITION)
                mark_beginning_as_normal (trans2[mach]);
        }
        break;
    
    }
}

This is simply running out of stack space. You can make the number of recursions go up by 11,000 or so by dynamically allocating variables instead of using stack space, but at the end of the day, you can work around this (for this test case) by doing:

ulimit -s 4096

Of course, a much larger (deeper) YAML file will still make it crash. You can thus, make it happen far faster by doing:

ulimit -s 256

The crash does not seem to happen due to any buffer overflows or memory corruption; it’s simply the kernel saying "you’re out of stack space, please die". One simple way to avoid the crash itself is to do a depth-check of the tree and compare it to some value related to the stack size returned and produce an error if the values are way out of whack.

A more complicated solution would involve removing recursion, which looks like it would not be a trivial fix.