Re: CVE-2016-8685 in potrace
Hi Hugo
This is interesting. Some comments below.
On 3 April 2017 at 20:21, Hugo Lefeuvre <hle@debian.org> wrote:
> Hi Ola,
>
> Thanks for your detailed explanations.
>
> Some logging:
>
> static int findnext(potrace_bitmap_t *bm, int *xp, int *yp) {
> FILE *fl = fopen("log", "w");
> fprintf(fl, "Starting test\n");
> fflush(fl);
> int x;
> int y;
> int x0;
>
> x0 = (*xp) & ~(BM_WORDBITS-1);
>
> for (y=*yp; y>=0; y--) {
> for (x=x0; x<bm->w && x>=0; x+=BM_WORDBITS) {
> //fprintf(fl, "x=%d\n", x);
> if (*bm_index(bm, x, y)) {
> fprintf(fl, "Executed *bm_index(bm, x=%d, y=%d)\n", x, y);
> fflush(fl);
> while (!BM_GET(bm, x, y)) {
> fprintf(fl, "Executed !BM_GET(bm, x=%d, y=%d)\n", x, y);
> fflush(fl);
> x++;
> }
> /* found */
> *xp = x;
> *yp = y;
> fclose(fl);
> return 0;
> }
> }
> x0 = 0;
> }
> /* not found */
> fprintf(fl, "Nothing found, exit with x=%d\n", x);
> fclose(fl);
> return 1;
> }
>
> (probably lots of useless fflush-es, but that doesn't matter)
>
> 1) When //fprintf(fl, "x=%d\n", x); is commented, potrace crashes and the log
> file only contains "Starting test".
Interesting.
> 2) If we uncomment it, potraces does not crash anymore and the log file
> contains
>
> Starting test
> x=0
> x=64
> x=128
> ...
> x=2147483584
> Nothing found, exit with x=-2147483648
>
> which is the excepted behavior (right?).
Yes then x has clearly become negative. If the x>= 0 would not have
been there, it would have crashed due to that. I guess the fprintf
function call make sure (in some way unknown to me) that the optimizer
can not optimize away the x>= 0 part. I guess if that (the introduced
x >= 0) is removed, it will crash, right?
> Case 1) is difficult to investigate because each time I try to log x or do
> anything with it, potrace does not crash anymore and everything works perfectly.
>
> Anyway, x seems to become negative which makes (x)/BM_WORDBITS negative and leads
> &bm_scanline(bm, y)[(x)/BM_WORDBITS]) to segfault.
>
> So you're right, it looks like the current issue comes from an erroneous
> optimization of the loop, like if the x>=0 statement would be ignored.
>
> It would probably be interesting to look at the assembly code, but I'm
> not sure it's a good way to spend my hours. :)
I guess not. :-)
>> I think it would be better to have a check to validate if w is too large.
>
> You mean something like that (roughly)
>
> if( bm->w >= INT_MAX - BM_WORDBITS ) {
> return 0;
> }
>
> before the y loop ?
Yes, something like that. I do not think the optimizer can optimize
that statement away. :-)
It may be worth a try. But if that do not solve it I think we can
leave it as a no-dsa as that have already been done for stable (as I
understood it).
>> As a side-note. We probably have a similar issue if something is
>> matched at this very end. Then x++ is done a number of times, and that
>> could also lead to integer overflow. Maybe this is what you see in
>> wheezy?
>
> Let's say bm->w = INT_MAX, x = INT_MAX, y = 1:
>
> BM_GET(bm, x, y) = (bm_safe(bm, x, y) ? BM_UGET(bm, x, y) : 0)) = 0
>
> as
>
> bm_safe(bm, x, y) = (bm_range(x, (bm)->w) && bm_range(y, (bm)->h)) = 0
>
> as
>
> bm_range(x, (bm)->w) = ((int)(x) >= 0 && (int)(x) < (bm->w)) = 0 as x>=bm->w
>
> and
>
> bm_range(y, (bm)->h) = ((int)(y) >= 0 && (int)(y) < (bm->w)) = 1
>
> so I guess
>
> while (!BM_GET(bm, x, y)) {
> x++;
> }
>
> would continue to loop, there would be an integer overflow, and it would
> continue to loop for a long long time, until x becomes positive again...
>
> But no segfault IMO because BM_UGET won't be called if x and y are not
> positive and there's no segfault-prone statement in BM_GET/the loop.
Ok. That sounds like a likely case, yes.
>> Addition of (unsigned):
>> ---------------------------------
>>
>> This is clearly superflous. First of all it will be converted back to
>> (int) as x is an integer. Secondly BM_WORDBITS is
>> 8*(int)sizeof(potrace_word) = 8*(int)sizeof(unsigned long) and that is
>> definitely a positive number always.
>>
>> I think this is definitely optimized away, if it ever had a meaning.
>
> +1
:-)
Best regards
// Ola
> Cheers,
> Hugo
>
> --
> Hugo Lefeuvre (hle) | www.owl.eu.com
> 4096/ ACB7 B67F 197F 9B32 1533 431C AC90 AC3E C524 065E
--
--- Inguza Technology AB --- MSc in Information Technology ----
/ ola@inguza.com Folkebogatan 26 \
| opal@debian.org 654 68 KARLSTAD |
| http://inguza.com/ Mobile: +46 (0)70-332 1551 |
\ gpg/f.p.: 7090 A92B 18FE 7994 0C36 4FE4 18A1 B1CF 0FE5 3DD9 /
---------------------------------------------------------------
Reply to: