Number: 1520
Title: Segmentation fault in make_regular_edge() in dotsplines.c:1448
Submitter: Josep M. Perez
Date: Mon Nov 17 20:48:29 2008
Subsys: Dot
Version: 2.20.3
System: *-*-
Severity: major
Problem:
Running the following command causes a segfault in dot:

dot -Tps -v -Gnslimit=0.1 patata5.dot

I've recompiled the Debian package without optimization and with debugging turned on. Gdb gives the following backtrace:


#0  0xb7ce0c33 in make_regular_edge (sp=0xbfddc094, P=0x9777b30, edges=0x8c1f4c8, ind=3505, cnt=1, et=8) at dotsplines.c:1448
#1  0xb7cdcba2 in _dot_splines (g=0x88e68a8, normalize=1) at dotsplines.c:396
#2  0xb7cdcdac in dot_splines (g=0x88e68a8) at dotsplines.c:448
#3  0xb7cd25ce in dot_layout (g=0x88e68a8) at dotinit.c:212
#4  0xb7f366dd in gvLayoutJobs (gvc=0x88d97b0, g=0x88e68a8) at gvlayout.c:69
#5  0x08048a3f in main (argc=5, argv=0xbfddc384) at dot.c:180

Running the command inside valgrind causes a read error:


==9030== Invalid read of size 4
==9030==    at 0x46D9C33: make_regular_edge (dotsplines.c:1448)
==9030==    by 0x46D5BA1: _dot_splines (dotsplines.c:396)
==9030==    by 0x46D5DAB: dot_splines (dotsplines.c:448)
==9030==    by 0x46CB5CD: dot_layout (dotinit.c:212)
==9030==    by 0x405D6DC: gvLayoutJobs (gvlayout.c:69)
==9030==    by 0x8048A3E: main (dot.c:180)
==9030==  Address 0x36c is not stack'd, malloc'd or (recently) free'd

The relevant code lines are:


1447                for (i = 0; i < pn; i++)
1448                    points[pointn++] = ps[i];

At the time it crashes ps=0x318, pointn=1153 and i=10. Looks like the points array is not big enough and is overlapping the memory used for storing the address of ps:


(gdb) print &ps
$3 = (point **) 0xbeb06128
(gdb) print &points[pointn-1]
$4 = (point *) 0xbeb06124

BTW, sizeof(point)=8, so the previous iteration actually overwrites the ps variable.
Input file: b1520.dot
Comments:
Reported via Debian: 505436@bugs.debian.org

[gordon.smith] I just found a similar one in Windows (I compile all of dot into a single DLL called "libagraph")....

Looks like the abort call is a bit "aggressive"?

Dot file is attached.

Gordon.


Stack Trace:
> >	msvcr90d.dll!_NMSG_WRITE(int rterrnum=10)  Line 198	C
 	msvcr90d.dll!abort()  Line 59 + 0x7 bytes	C
 	libagraph.dll!triangulate(pointnlink_t * * pnlps=0x08b70438, int
pnln=14)  Line 310 + 0x8 bytes	C
 	libagraph.dll!triangulate(pointnlink_t * * pnlps=0x08b70438, int
pnln=15)  Line 306 + 0x10 bytes	C
 	libagraph.dll!triangulate(pointnlink_t * * pnlps=0x08b70438, int
pnln=16)  Line 306 + 0x10 bytes	C
 	libagraph.dll!Pshortestpath(Ppoly_t * polyp=0x073fcad0, Pxy_t *
eps=0x073fca7c, Ppoly_t * output=0x073fcac0)  Line 166 + 0x12 bytes	C
 	libagraph.dll!_routesplines(path * pp=0x0a0d94f8, int *
npoints=0x073fcdac, int polyline=0)  Line 421 + 0x11 bytes	C
 	libagraph.dll!routesplines(path * pp=0x0a0d94f8, int *
npoints=0x073fcdac)  Line 533 + 0xf bytes	C
 	libagraph.dll!make_flat_labeled_edge(spline_info_t * sp=0x073fdd40,
path * P=0x0a0d94f8, Agedge_t * e=0x09fb1b38, int et=8)  Line 1072 + 0x16
bytes	C
 	libagraph.dll!make_flat_edge(spline_info_t * sp=0x073fdd40, path *
P=0x0a0d94f8, Agedge_t * * edges=0x0b0a70d0, int ind=0, int cnt=1, int et=8)
Line 1183 + 0x18 bytes	C
 	libagraph.dll!_dot_splines(Agraph_t * g=0x03922ed8, int normalize=1)
Line 388 + 0x29 bytes	C
 	libagraph.dll!dot_splines(Agraph_t * g=0x03922ed8)  Line 452 + 0xb
bytes	C
 	libagraph.dll!dot_layout(Agraph_t * g=0x03922ed8)  Line 273 + 0x9
bytes	C
 	libagraph.dll!gvLayoutJobs(GVC_s * gvc=0x08bc2fb8, Agraph_t *
g=0x03922ed8)  Line 87 + 0xd bytes	C
 	libagraph.dll!gvLayout(GVC_s * gvc=0x08bc2fb8, Agraph_t *
g=0x03922ed8, const char * engine=0x06b5eecc)  Line 71 + 0xd bytes	C
 	libagraph.dll!DoLayout(const char * layout=0x06b5eecc, const char *
mem=0x09eef440, const char * out=0x03961c88, const char * format=0x073febf8,
const char * scale=0x073fefb0)  Line 88 + 0x14 bytes	C++

Owner: *
Status: *