]> granicus.if.org Git - graphviz/commit
neatogen: fix out of bounds write when exceeding estimated edges
authorMatthew Fernandez <matthew.fernandez@gmail.com>
Tue, 15 Nov 2022 04:16:48 +0000 (20:16 -0800)
committerMatthew Fernandez <matthew.fernandez@gmail.com>
Thu, 17 Nov 2022 04:03:13 +0000 (20:03 -0800)
commitfc465488e1e62fe5ef879b379a07ef272431f400
tree554553549588ff6fdb0ebea6255658a56839824f
parent220485aa66f4d14f9c5230aaaba8986779778cc0
neatogen: fix out of bounds write when exceeding estimated edges

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