[Pixman] [PATCH] Trying to reproduce bug #97938

[Alessandro Vesely]

Hi Siarhei,

On Thu 06/Oct/2016 06:13:01 +0200 Siarhei Siamashka wrote:
> On Wed,  5 Oct 2016 20:25:51 +0200 Alessandro Vesely wrote:
>> See https://bugs.freedesktop.org/show_bug.cgi?id=97938
>
> By the way, I forgot to ask it in bugzilla. How was this
> problem discovered in the first place? Did you use some
> static analysis tool? Or maybe had an application crash?

The last one of those two.  More detail below.

> Now the main remaining question is whether the stress-test is
> providing sufficient coverage and whether the problematic code
> parts are getting visited. To do some experiments with it, I used
> the following patch:
>
> [...]
> +	    /* Simulate integer overflow (truncate intermediate result to NBITS bits) */
> +	    #define NBITS 15
> +	    #define XBITS (32 - NBITS)
> +	    row1 = (uint8_t *)bits->bits + ((int32_t)((bits->rowstride * 4 * y1) << XBITS) >> XBITS);

FWIW, I tried a somewhat similar approach, albeit very different in purpose and 
range.  I brutishly appended a few '0's after that '4', so as to get a crash 
somewhere.  I got:

FAIL: rotate-test
FAIL: alphamap
FAIL: filter-reduction-test
FAIL: glyph-test
FAIL: stress-test
FAIL: cover-test
FAIL: blitters-test
FAIL: affine-test
FAIL: scaling-test

Then I went on trying to modify rotate-test in order to produce a crash against 
the pristine code.  I failed, also because I'm not at all familiar with pixman. 
  Rather than perseverate that way with alphamep, since I still had my 
test.svg, an 800K A0 poster, I reproduced the crash under gdb/inkscape and then 
copied and pasted the values of the parameters from the nearest external 
caller.  That's how I assembled large-test.

> The idea is that testing 32-bit overflows is a PITA because we need
> really huge images.

Agreed.  The test I sent is different from the existing ones in that it doesn't 
randomize the parameters, and only runs once.

> But the code can be changed to simulate overflows with any arbitrary number
> of bits (which are defined by the NBITS constant). If I set NBITS to 16 or
> more, then the pixman tests still pass.

Hm...  I don't think I'm with you.  The program is not actually doing anything 
wrong, from a logical point of view.  Addition in C doesn't endure the usual 
arithmetical properties.  For example, addition is not always the inverse of 
subtraction.  Paraphrasing the standard, I'd say:

     The size of [ bits->rowstride * 4 * y1 ] is implementation-defined, and
     its type (a signed integer type) is ptrdiff_t defined in the <stddef.h>
     header.  If [ that expression ] is not representable in an object of that
     type, the behavior is undefined.

> If I reduce NBITS to 15, then I get exactly the 'stress-test' crashing:
>[...]
> ../test-driver: line 107:  3527 Segmentation fault      "$@" > $log_file 2>&1
> FAIL: stress-test

Undefined behavior?

> If I further reduce NBITS to 11, then I get some other tests failing:
> [...]
> FAIL: affine-test
> FAIL: scaling-test

You report no crash this time.  Perhaps those tests use images larger than 0x7ff/4.

> A tricky part here is that the stress-test crash disappeared too. This
> can be explained by the fact that the offsets become smaller and wrong
> memory accesses still hit some mapped memory inside of heap.

Can be, albeit not within the same object.  At the crash point I found:

(gdb) p 32 - 15
$7 = 17  // XBITS

(gdb) p /x bits->rowstride * 4 *(-1127207664 - 65536/2)  // y1 optimized out
$14 = 0xb87b13c0
(gdb) p /x ((bits->rowstride * 4 *(-1127207664 - 65536/2)) << 17)>> 17
$15 = 0x13c0
(gdb) p /x ((bits->rowstride * 4 *(-1127207664 - 65536/2)) << 21)>> 21
$16 = 0x3c0

(gdb) p /x malloc_usable_size(image)
$19 = 0x108

We'd need extra machinery to ensure proper memory fences...

> Anyway, the affected problematic code from 'pixman-fast-path.c' is
> already covered by the stress-test and this is good.

You may well be right, but to prove NBITS simulation results in a correct 
coverage seems to me to be way more difficult than groping for the idiom and 
replace it with better one.  As implied above, it is not quite possible to even 
/prove/ that ptrdiff_t would be the correct cast, since language design mimics 
arithmetic principles rather than rigorously develop its own logic.

> We surely can use a separate test for it. But extending the
> existing 'stress-test' is probably a better idea in general.
>
> Once we have the test suite adjusted, we are expected to find
> most of the bugs of this kind and also safeguard against them
> in the future.
>
> What do you think?

I'm neutral on using a separate test vs adding to stress-test.  I attach a 
patch assuming yesterday's test file just because I had the diff at hand.

It also fixes a line in utils.c, needed for large images.  Would that be called 
a meta-bug?

Ciao
Ale
-------------- next part --------------
From dc88ea33a62b8334fbb7370c20ae32c9c950361c Mon Sep 17 00:00:00 2001
From: Alessandro Vesely <vesely at tana.it>
Date: Thu, 6 Oct 2016 13:42:58 +0200
Subject: [PATCH 2/2] still using "strange" large-test, modified test/utils.c

Signed-off-by: Alessandro Vesely <vesely at tana.it>
---
 test/Makefile.sources | 1 +
 test/utils.c          | 2 +-
 2 files changed, 2 insertions(+), 1 deletion(-)

diff --git a/test/Makefile.sources b/test/Makefile.sources
index 0a56231..971fc1a 100644
--- a/test/Makefile.sources
+++ b/test/Makefile.sources
@@ -1,5 +1,6 @@
 # Tests (sorted by expected completion time)
 TESTPROGRAMS =			      \
+	large-test		      \
 	oob-test		      \
 	infinite-loop		      \
 	trap-crasher		      \
diff --git a/test/utils.c b/test/utils.c
index f8e42a5..b6fe6fa 100644
--- a/test/utils.c
+++ b/test/utils.c
@@ -228,7 +228,7 @@ compute_crc32_for_image_internal (uint32_t        crc32,
      */
     image_endian_swap (img);
 
-    return compute_crc32 (crc32, data, stride * height);
+    return compute_crc32 (crc32, data, (size_t)stride * (size_t)height);
 }
 
 uint32_t
-- 
2.1.4