From 2039ffa5b2b7464a85ff826e99c16bea0596f6fa Mon Sep 17 00:00:00 2001 From: Matthew Fernandez Date: Sun, 2 Aug 2020 09:37:49 -0700 Subject: [PATCH] fix segfault with large edge weights When passed a large edge weight, e.g. 1073741824, an integer overflow would occur when calculating virtual weights. This would go on to cause a segfault as calculations were increasingly thrown off by negative values. This change detects when an overflow will occur and exits. Calling exit() from within a deeply nested library function like this is not good practice, but we don't have a better alternative right now. The call chain involves gvLayout() whose interface to the plugins inherently has no way of reporting failure. Fixes #1783. --- CHANGELOG.md | 1 + lib/dotgen/mincross.c | 11 +++++++++++ rtest/1783.dot | 5 +++++ rtest/test_regression.py | 18 ++++++++++++++++++ 4 files changed, 35 insertions(+) create mode 100644 rtest/1783.dot diff --git a/CHANGELOG.md b/CHANGELOG.md index bd176a26e..8c2d875e3 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -17,6 +17,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - x11 back end segfaults if display is unavailable #1776 - Repeated file read gives different results with libcgraph #1767 - typo in cmd/gvpr/lib/clustg #1781 +- Segfault in dot #1783 ## [2.44.1] - 2020-06-29 diff --git a/lib/dotgen/mincross.c b/lib/dotgen/mincross.c index c0a106142..19214747a 100644 --- a/lib/dotgen/mincross.c +++ b/lib/dotgen/mincross.c @@ -19,7 +19,10 @@ * because mincross may compare nodes in different clusters. */ +#include #include "dot.h" +#include +#include /* #define DEBUG */ #define MARK(v) (ND_mark(v)) @@ -1899,6 +1902,14 @@ void virtual_weight(edge_t * e) { int t; t = table[endpoint_class(agtail(e))][endpoint_class(aghead(e))]; + + /* check whether the upcoming computation will overflow */ + assert(t >= 0); + if (INT_MAX / t < ED_weight(e)) { + agerr(AGERR, "overflow when calculating virtual weight of edge\n"); + exit(EXIT_FAILURE); + } + ED_weight(e) *= t; } diff --git a/rtest/1783.dot b/rtest/1783.dot new file mode 100644 index 000000000..20665cf6b --- /dev/null +++ b/rtest/1783.dot @@ -0,0 +1,5 @@ +digraph code { +edge [weight=1073741824]; + "1" -> "0"; +} + diff --git a/rtest/test_regression.py b/rtest/test_regression.py index b8cb1ff37..75f6757d0 100644 --- a/rtest/test_regression.py +++ b/rtest/test_regression.py @@ -2,6 +2,7 @@ import atexit import pytest import platform import shutil +import signal import subprocess import os import re @@ -228,3 +229,20 @@ def test_1767(): 'cluster_1 contains 1 nodes\n' \ 'cluster_2 contains 3 nodes\n' \ 'cluster_3 contains 3 nodes\n' + +def test_1783(): + ''' + Graphviz should not segfault when passed large edge weights + https://gitlab.com/graphviz/graphviz/-/issues/1783 + ''' + + # locate our associated test case in this directory + input = os.path.join(os.path.dirname(__file__), '1783.dot') + assert os.path.exists(input), 'unexpectedly missing test case' + + # run Graphviz with this input + ret = subprocess.call(['dot', '-Tsvg', '-o', os.devnull, input]) + + assert ret != 0, 'Graphviz accepted illegal edge weight' + + assert ret != -signal.SIGSEGV, 'Graphviz segfaulted' -- 2.40.0