stack overflow

[guyharris]

Converted from SourceForge issue 709338, submitted by nobody

static int
count_blocks(p)
struct block *p;
{
    if (p == 0 || isMarked(p))
        return 0;
    Mark(p);
    return count_blocks(JT(p)) + count_blocks(JF(p)) + 1;
}

when the tree is depth enough, some recursion functions will "eat up" the stack.

for example:

tcpdump not host 192.168.0.1 and ... and not host 192.168.0.254 and not host 192.168.1.1 and ... and not host 192.168.10.254

tcpdump is coredump.

[TheRealKeyboardWarrior]

Rediscovered https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=14236&start=200

[TheRealKeyboardWarrior]

@guyharris Morris Traversal instead of recursion? https://www.educative.io/edpresso/what-is-morris-traversal

[mcr]

If I understand this, the "attack" is on the command line, or as input to the libpcap compiler. (The oss-fuzz description was completely useless)

[TheRealKeyboardWarrior]

pcap_compile() -> bpf_optimize() -> opt_init() -> count_blocks()

[guyharris]

... count_blocks()

...which recursively walks the control-flow graph for the program.

Note that it's a DAG, not a tree. I'd have to look some more at the Morris algorithm to see to what extent that's an issue. Nodes are marked to make sure they're not visited more than once (if you do a depth-first traversal, you may traverse end nodes more than once, for example; there may be multiple ways to either match a packet or fail to match a packet, so there may be multiple paths to the two end nodes).