Go forward in time to March 2015.
Another bug that showed up through fuzz-testing in librsvg was due to an overflow during integer multiplication.
SVG supports using a convolution matrix for its pixel-based filters. Within the feConvolveMatrix element, one can use the order attribute to specify the size of the convolution matrix. This is usually a small value, like 3 or 5. But what did fuzz-testing generate?
<feConvolveMatrix order="65536">
That would be an evil, slow convolution matrix in itself, but in librsvg it caused trouble not because of its size, but because C sucks.
The code had something like this:
struct _RsvgFilterPrimitiveConvolveMatrix { ... double *KernelMatrix; ... gint orderx, ordery; ... };
The values for the convolution matrix are stored in KernelMatrix, which is just a flattened rectangular array of orderx × ordery elements.
The code tries to be careful in ensuring that the array with the convolution matrix is of the correct size. In the code below, filter->orderx and filter->ordery have both been set to the dimensions of the array, in this case, both 65536:
guint listlen = 0; ... if ((value = rsvg_property_bag_lookup (atts, "kernelMatrix"))) filter->KernelMatrix = rsvg_css_parse_number_list (value, &listlen); ... if ((gint) listlen != filter->orderx * filter->ordery) filter->orderx = filter->ordery = 0;
Here, the code first parses the kernelMatrix number list and stores its length in listlen. Later, it compares listlen to orderx * ordery to see if KernelMatrix array has the correct length. Both filter->orderx and ordery are of type int. Later, the code iterates through the values in the filter>KernelMatrix when doing the convolution, and doesn't touch anything if orderx or ordery are zero. Effectively, when those values are zero it means that the array is not to be touched at all — maybe because the SVG is invalid, as in this case.
But in the bug, the orderx and ordery are not being sanitized to be zero; they remain at 65536, and the KernelMatrix gets accessed incorrectly as a result. Let's see what happens when you mutiply 65536 by itself with ints.
(gdb) p (int) 65536 * (int) 65536 $1 = 0
Well, of course — the result doesn't fit in 32-bit ints. Let's use 64-bit ints instead:
(gdb) p (long long) 65536 * 65536 $2 = 4294967296
Which is what one expects.
What is happening with C? We'll go back to the faulty code and get a disassembly (I recompiled this without optimizations so the code is easy):
$ objdump --disassemble --source .libs/librsvg_2_la-rsvg-filter.o ... if ((gint) listlen != filter->orderx * filter->ordery) 4018: 8b 45 cc mov -0x34(%rbp),%eax 401b: 89 c2 mov %eax,%edx %edx = listlen 401d: 48 8b 45 d8 mov -0x28(%rbp),%rax 4021: 8b 88 a8 00 00 00 mov 0xa8(%rax),%ecx %ecx = filter->orderx 4027: 48 8b 45 d8 mov -0x28(%rbp),%rax 402b: 8b 80 ac 00 00 00 mov 0xac(%rax),%eax %eax = filter->ordery 4031: 0f af c1 imul %ecx,%eax 4034: 39 c2 cmp %eax,%edx 4036: 74 22 je 405a <rsvg_filter_primitive_convolve_matrix_set_atts+0x4c6> filter->orderx = filter->ordery = 0; 4038: 48 8b 45 d8 mov -0x28(%rbp),%rax 403c: c7 80 ac 00 00 00 00 movl $0x0,0xac(%rax) 4043: 00 00 00 4046: 48 8b 45 d8 mov -0x28(%rbp),%rax 404a: 8b 90 ac 00 00 00 mov 0xac(%rax),%edx 4050: 48 8b 45 d8 mov -0x28(%rbp),%rax 4054: 89 90 a8 00 00 00 mov %edx,0xa8(%rax)
The highligted lines do the multiplication of filter->orderx * filter->ordery and the comparison against listlen. The imul operation overflows and gives us 0 as a result, which is of course wrong.
Let's look at the overflow in slow motion. We'll set a breakpoint in the offending line, disassemble, and look at each instruction.
Breakpoint 3, rsvg_filter_primitive_convolve_matrix_set_atts (self=0x69dc50, ctx=0x7b80d0, atts=0x83f980) at rsvg-filter.c:1276 1276 if ((gint) listlen != filter->orderx * filter->ordery) (gdb) set disassemble-next-line 1 (gdb) stepi ... (gdb) stepi 0x00007ffff7baf055 1276 if ((gint) listlen != filter->orderx * filter->ordery) 0x00007ffff7baf03c <rsvg_filter_primitive_convolve_matrix_set_atts+1156>: 8b 45 cc mov -0x34(%rbp),%eax 0x00007ffff7baf03f <rsvg_filter_primitive_convolve_matrix_set_atts+1159>: 89 c2 mov %eax,%edx 0x00007ffff7baf041 <rsvg_filter_primitive_convolve_matrix_set_atts+1161>: 48 8b 45 d8 mov -0x28(%rbp),%rax 0x00007ffff7baf045 <rsvg_filter_primitive_convolve_matrix_set_atts+1165>: 8b 88 a8 00 00 00 mov 0xa8(%rax),%ecx 0x00007ffff7baf04b <rsvg_filter_primitive_convolve_matrix_set_atts+1171>: 48 8b 45 d8 mov -0x28(%rbp),%rax 0x00007ffff7baf04f <rsvg_filter_primitive_convolve_matrix_set_atts+1175>: 8b 80 ac 00 00 00 mov 0xac(%rax),%eax => 0x00007ffff7baf055 <rsvg_filter_primitive_convolve_matrix_set_atts+1181>: 0f af c1 imul %ecx,%eax 0x00007ffff7baf058 <rsvg_filter_primitive_convolve_matrix_set_atts+1184>: 39 c2 cmp %eax,%edx 0x00007ffff7baf05a <rsvg_filter_primitive_convolve_matrix_set_atts+1186>: 74 22 je 0x7ffff7baf07e <rsvg_filter_primitive_convolve_matrix_set_atts+1222> (gdb) info registers rax 0x10000 65536 rbx 0x69dc50 6937680 rcx 0x10000 65536 rdx 0x0 0 ... eflags 0x206 [ PF IF ]
Okay! So, right there, the code is about to do the multiplication. Both eax and ecx, which are 32-bit registers, have 65536 in them — you can see the 64-bit "big" registers that contain them in rax and rcx.
Type "stepi" and the multiplication gets executed:
(gdb) stepi 0x00007ffff7baf058 1276 if ((gint) listlen != filter->orderx * filter->ordery) 0x00007ffff7baf03c <rsvg_filter_primitive_convolve_matrix_set_atts+1156>: 8b 45 cc mov -0x34(%rbp),%eax 0x00007ffff7baf03f <rsvg_filter_primitive_convolve_matrix_set_atts+1159>: 89 c2 mov %eax,%edx 0x00007ffff7baf041 <rsvg_filter_primitive_convolve_matrix_set_atts+1161>: 48 8b 45 d8 mov -0x28(%rbp),%rax 0x00007ffff7baf045 <rsvg_filter_primitive_convolve_matrix_set_atts+1165>: 8b 88 a8 00 00 00 mov 0xa8(%rax),%ecx 0x00007ffff7baf04b <rsvg_filter_primitive_convolve_matrix_set_atts+1171>: 48 8b 45 d8 mov -0x28(%rbp),%rax 0x00007ffff7baf04f <rsvg_filter_primitive_convolve_matrix_set_atts+1175>: 8b 80 ac 00 00 00 mov 0xac(%rax),%eax 0x00007ffff7baf055 <rsvg_filter_primitive_convolve_matrix_set_atts+1181>: 0f af c1 imul %ecx,%eax => 0x00007ffff7baf058 <rsvg_filter_primitive_convolve_matrix_set_atts+1184>: 39 c2 cmp %eax,%edx 0x00007ffff7baf05a <rsvg_filter_primitive_convolve_matrix_set_atts+1186>: 74 22 je 0x7ffff7baf07e <rsvg_filter_primitive_convolve_matrix_set_atts+1222> (gdb) info registers rax 0x0 0 rbx 0x69dc50 6937680 rcx 0x10000 65536 rdx 0x0 0 eflags 0xa07 [ CF PF IF OF ]
Kaboom. The register eax (inside rax) now is 0, which is the (wrong) result of the multiplication. But look at the flags! There is a big fat OF flag, the overflow flag! The processor knows! And it tries to tell us... with a single bit... that the C language doesn't bother to check!
(The solution in the code, at least for now, is simple enough — use gint64 for the actual operations so the values fit. It should probably set a reasonable limit for the size of convolution matrices, too.)
So, could anything do better?
Scheme uses exact arithmetic if possible, so (* MAXLONG MAXLONG) doesn't overflow, but gives you a bignum without you doing anything special. Subsequent code may go into the slow case for bignums when it happens to use that value, but at least you won't get garbage.
I think Python does the same, at least for integer values (Scheme goes further and uses exact arithmetic for all rational numbers, not just integers).
C# lets you use checked operations, which will throw an exception if something overflows. This is not the default — the default is "everything gets clipped to the operand size", like in C. I'm not sure if this is a mistake or not. The rest of the language has very nice safety properties, and it lets you "go fast" if you know what you are doing. Operations that overflow by default, with opt-in safety, seem contrary to this philosophy. On the other hand, the language will protect you if you try to do something stupid like accessing an array element with a negative index (... that you got from an overflowed operation), so maybe it's not that bad in the end.
I'm taking over the maintainership of librsvg.
I've been fixing a few crashers, and the code is interesting, so I'll blog a bit about the bugs. It's rather peculiar how people's mindset has changed from the time when "feeding an invalid file leads to a crash" was just considered garbage-in, garbage-out — to the present time, when a crasher on invalid data is "OMG a government agency surely is going to write malicious vector images to pwn you every way it can".
Atte Kettunen of the Oulu University Secure Programming Group has been doing fuzz-testing on librsvg, and this is producing very interesting results. Check out their fuzz-testing tools! My next blog posts will be about the bugs in librsvg and why C is a shitty language for userland code.
librsvg bug #703102 - out of bounds memory access
In librsvg bug 703102 we get an SVG that starts with
<svg version="1.1" baseProfile="basic" id="svg-root" width="100%" height="100%" viewBox="0 170141183460469231731687303715884105727 480 360"
The bounding box is obviously invalid, and the code crashed in this function:
static void rsvg_alpha_blt (cairo_surface_t *src, gint srcx, gint srcy, gint srcwidth, gint srcheight, cairo_surface_t *dst, gint dstx, gint dsty)
This is a fairly typical function for "take a rectangle from this cairo_surface_t and composite it over this other cairo_surface_t".
The function used to start with some code to clip the coordinates to the actual surfaces... but it was broken. Eventually the loops that iterate through the pixels in the destination region would go past the bounds of the allocated buffers.
I replaced the broken clipping code with something similar to our venerable gdk_rectangle_intersect(), and the bug went away.
The ubiquitous pattern to access rectangular image buffers is, "give me a pointer to the start of the pixels", then "give me the rowstride, i.e. the length of each line in bytes".
The code has to be careful to not go past the bounds of buffers. Things get complicated when you have two images with different dimensions, or different rowstrides — lots of variables to keep track of.
A civilized language would let you access the byte arrays for the pixel data, but it would not let you access past their bounds. It would halt the program if you do buffer[-5] or buffer[BIGNUM].
C doesn't give a fuck. C gives you a buffer overrun:
Go backward in time to January 2015.
Federico Mena-Quintero <federico@gnome.org> Fri 2015/Feb/06 17:38:44 CST