From fc465488e1e62fe5ef879b379a07ef272431f400 Mon Sep 17 00:00:00 2001 From: Matthew Fernandez Date: Mon, 14 Nov 2022 20:16:48 -0800 Subject: [PATCH] neatogen: fix out of bounds write when exceeding estimated edges MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit The `edgei` allocation in `mkTriGraph` was wrong. This code was written prior to Git history, and it is not obvious how the calculation for how many edges to allocate was arrived at. My educated guess is that the `+ 2` was intended to account for the maximum number of final appended edges (the maximum trip count of the trailing loop in this function), except that is 3 not 2. Bumping this to 3 indeed bypasses the ASan failure in #42. Rather than just make that equally error prone adjustment, this commit stops estimating the edge count upfront at all and instead allocates edges per-node on-demand. The prior code was allocating edges for all nodes as a contiguous array. Each node would then be given an offset pointer into this array. Apart from the problem described above, this meant all nodes apart from the last one could overflow their edge count, silently corrupting their neighbor’s edges, in a way undetectable by ASan. This refactoring gives each node distinct memory for its edges. But this means we needed to introduce a node count (`nnodes`) to the trigraph and free each of these separate allocations when destructing the trigraph. This also required passing in original edge counts to `resetGraph`. Previously the code would detect an edge that needed to be removed by a node’s edges running up against its neighbor’s. Obviously this was subject to the above described bugs which could cause false negatives in this test, leading to even further compounding data corruption. Fixing this unfortunately only yields yet another ASan crash (below). This will be addressed in an upcoming commit. WRITE of size 16 at 0x613000001860 thread T0 #0 0x7f5b44579e80 in genroute lib/neatogen/multispline.c:869 #1 0x7f5b4457f53d in makeMultiSpline lib/neatogen/multispline.c:1311 #2 0x7f5b4452ac4d in _spline_edges lib/neatogen/neatosplines.c:632 #3 0x7f5b4452b4c8 in splineEdges lib/neatogen/neatosplines.c:729 #4 0x7f5b4452b5a6 in spline_edges1 lib/neatogen/neatosplines.c:742 #5 0x7f5b4452b658 in spline_edges0 lib/neatogen/neatosplines.c:771 #6 0x7f5b4451154d in init_nop lib/neatogen/neatoinit.c:597 #7 0x7f5b44516ac9 in neato_layout lib/neatogen/neatoinit.c:1407 #8 0x7f5b488a847f (/tmp/tmp.jiRlFO5wtW/lib+0x8647f) #9 0x55ddbc8126dc in main graphviz/cmd/dot/dot.c:89 #10 0x7f5b485e2d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58 #11 0x7f5b485e2e3f in __libc_start_main_impl ../csu/libc-start.c:392 #12 0x55ddbc812344 in _start (bin/dot+0x1344) It should be clear from the above that the code here has a very error prone structure. (1) Estimating how much memory is required upfront with non-trivial calculations and (2) allocating a block of memory that is then partitioned out to clients trusted not to run into each other, effectively creates a scenario where bugs are undetectable by memory safety tools and easily compound one another. In future the other allocations in this file should be rewritten to avoid this structure too. Gitlab: #42 --- lib/neatogen/multispline.c | 56 ++++++++++++++++++-------------------- 1 file changed, 27 insertions(+), 29 deletions(-) diff --git a/lib/neatogen/multispline.c b/lib/neatogen/multispline.c index de1087d39..cd3f9dbab 100644 --- a/lib/neatogen/multispline.c +++ b/lib/neatogen/multispline.c @@ -8,6 +8,7 @@ * Contributors: Details at https://graphviz.org *************************************************************************/ +#include #include #include #include @@ -407,8 +408,9 @@ typedef struct { typedef struct { tnode *nodes; + size_t nnodes; // number of nodes tedge *edges; - int nedges; /* no. of edges; no. of nodes is stored in router_t */ + int nedges; // number of edges } tgraph; struct router_s { @@ -486,21 +488,6 @@ static int *mkTriIndices(surface_t * sf) return tris; } -/* degT: - * Given a pointer to an array of 3 integers, return - * the number not equal to -1 - */ -static int degT(int *ip) -{ - ip++; - if (*ip++ == -1) - return 1; - if (*ip == -1) - return 2; - else - return 3; -} - /* sharedEdge: * Returns a pair of integer (x,y), x < y, where x and y are the * indices of the two vertices of the shared edge. @@ -551,7 +538,11 @@ static void addTriEdge(tgraph *g, int t, int h, ipair seg) { ep->dist = DIST(tp->ctr, hp->ctr); ep->seg = seg; + tp->edges = gv_recalloc(tp->edges, tp->ne, tp->ne + 1, + sizeof(tp->edges[0])); tp->edges[tp->ne++] = g->nedges; + hp->edges = gv_recalloc(hp->edges, hp->ne, hp->ne + 1, + sizeof(hp->edges[0])); hp->edges[hp->ne++] = g->nedges; g->nedges++; @@ -559,7 +550,9 @@ static void addTriEdge(tgraph *g, int t, int h, ipair seg) { static void freeTriGraph(tgraph * tg) { - free(tg->nodes->edges); + for (size_t i = 0; i < tg->nnodes; ++i) { + free(tg->nodes[i].edges); + } free(tg->nodes); free(tg->edges); free(tg); @@ -574,7 +567,6 @@ static tgraph *mkTriGraph(surface_t * sf, int maxv, pointf * pts) tgraph *g; tnode *np; int j, i, ne = 0; - int *edgei; int *jp; /* ne is twice no. of edges */ @@ -585,29 +577,28 @@ static tgraph *mkTriGraph(surface_t * sf, int maxv, pointf * pts) g = GNEW(tgraph); /* plus 2 for nodes added as endpoints of an edge */ - g->nodes = N_GNEW(sf->nfaces + 2, tnode); + g->nnodes = sf->nfaces + 2; + g->nodes = N_GNEW(g->nnodes, tnode); /* allow 1 possible extra edge per triangle, plus * obstacles can have at most maxv triangles touching */ - edgei = N_GNEW(sf->nfaces + ne + 2 * maxv, int); g->edges = N_GNEW(ne/2 + 2 * maxv, tedge); g->nedges = 0; for (i = 0; i < sf->nfaces; i++) { np = g->nodes + i; np->ne = 0; - np->edges = edgei; + np->edges = NULL; np->ctr = triCenter(pts, sf->faces + 3 * i); - edgei += degT(sf->neigh + 3 * i) + 1; } /* initialize variable nodes */ np = g->nodes + i; np->ne = 0; - np->edges = edgei; + np->edges = NULL; np++; np->ne = 0; - np->edges = edgei + maxv; + np->edges = NULL; for (i = 0; i < sf->nfaces; i++) { np = g->nodes + i; @@ -1179,14 +1170,13 @@ static tripoly_t *mkPoly(router_t * rtr, int *dad, int s, int t, /* resetGraph: * Remove edges and nodes added for current edge routing */ -static void resetGraph(tgraph * g, int ncnt, int ecnt) -{ +static void resetGraph(tgraph *g, int ncnt, int ecnt, + int *original_edge_count) { int i; tnode *np = g->nodes; g->nedges = ecnt; for (i = 0; i < ncnt; i++) { - if (np->edges + np->ne == (np + 1)->edges) - np->ne--; + np->ne = original_edge_count[i]; np++; } } @@ -1288,6 +1278,13 @@ int makeMultiSpline(edge_t* e, router_t * rtr, int doPolyline) { PQVTYPE *vals; int ret; + // record the number of edges in each node, so we can drop the added ones + // later + int *original_edge_count = gv_calloc(rtr->tg->nnodes, + sizeof(original_edge_count[0])); + for (size_t i = 0; i < rtr->tg->nnodes; ++i) + original_edge_count[i] = rtr->tg->nodes[i].ne; + /* Add endpoints to triangle graph */ addEndpoint(rtr, t_p, t, t_id, ED_tail_port(e).side); addEndpoint(rtr, h_p, h, h_id, ED_head_port(e).side); @@ -1318,6 +1315,7 @@ int makeMultiSpline(edge_t* e, router_t * rtr, int doPolyline) { } else ret = -1; - resetGraph(rtr->tg, rtr->tn, ecnt); + resetGraph(rtr->tg, rtr->tn, ecnt, original_edge_count); + free(original_edge_count); return ret; } -- 2.40.0