neato mode=ipsep with a node in two clusters: C underflows ntoplevel and aborts on a SIZE_MAX allocation; the port draws the graph

Kind

Upstream C behaviour

Severity

high

Engine

neato

Category

error-path

Cases

1

Seeds

12208

Tracking

GitHub issuewon't fix

Labels

fuzzengine:neatoupstream-cwontfixcrash

With mode=ipsep, neato builds a cluster map that counts the nodes outside every top-level cluster as agnnodes(g) minus one per (cluster, member) pair. A node that belongs to two non-nested clusters is subtracted twice, so the unsigned count wraps to SIZE_MAX, and gv_calloc(SIZE_MAX, 8) makes C exit with status 1 and no output. The port computes the top-level node list directly (nodes not assigned to any cluster), so it never wraps, and it renders the graph with exit status 0.

Reproducer

graph "G" {
layout=neato;
mode="ipsep";
subgraph "cluster_0" {
"n1" -- "n4";
}
subgraph "cluster_1" {
"n1" [];
}
}

GVBINDIR=<pango-free plugins> dot -Kneato -Tsvg repro.gv   # C Graphviz 16.1.0
graphviz-pure -Kneato -Tsvg repro.gv                             # port

C output vs port

C stderr:
-integer overflow when trying to allocate 18446744073709551615 * 8 bytes
-[exit status 1]   (no stdout)
port:
+[exit status 0]   (a complete SVG with both clusters)

Root cause

C: lib/neatogen/neatoinit.c:206 starts cdata.ntoplevel = agnnodes_z(g), neatoinit.c:231 decrements it once per cluster member (duplicates included), neatoinit.c:236 allocates gv_calloc(cdata.ntoplevel, sizeof(size_t)); the overflow check in gv_calloc prints the message and exits.

Port: crates/graphviz-pure-layout/src/neatogen/cola.rs:21-47 (cluster_map) builds toplevel with a filter over an assigned bitmap, so a doubly assigned node is simply not top level.

The port could match C by emitting the same message and exiting 1 when the C count would wrap, but that would mean copying an upstream overflow bug. Recommend wontfix; mention it in the C bugs ledger.

Cases

1 fuzz case, seeds 12208. Each regenerates byte for byte with python3 -I scripts/fuzz-gen.py --seed N (checked for all of them).

Files

tests/fuzz-open/024-neato-ipsep-node-in-two-clusters-size-max-alloc

C and the port

OverprintSide by sideBlinkPixel diffSource diff

Comparing…

Magenta plate

100%

C onlyport onlyboth: in register

c.stderr

integer overflow when trying to allocate 18446744073709551615 * 8 bytes

[exit status 1]

rust.stderr

[exit status 0]

Reproduce

repro.gv

graph "G" {
layout=neato;
mode="ipsep";
subgraph "cluster_0" {
"n1" -- "n4";
}
subgraph "cluster_1" {
"n1" [];
}
}

cmd.txt

C:    GVBINDIR=<pango-free plugins> dot -Kneato -Tsvg repro.gv
port: graphviz-pure -Kneato -Tsvg repro.gv

cases.txt

r2/diff/s12208.gv seed=12208

Files: c.stderr, c.svg, cases.txt, cmd.txt, repro.gv, rust.stderr, rust.svg. Source: tests/fuzz-open/024-neato-ipsep-node-in-two-clusters-size-max-alloc.

All open issues