RE: gzip use of memcpy

[Alain Magloire]

Bonjour,

  Our tester (Yuxi) was proposing something along this line to check for
overlapping.

===email from yuxi===
We could do a smart checking here:
Unsigned int delta = w > d ? w -d : d -w;
        if (delta >= e)         /* (this test assumes unsigned
comparison) */
        {
          memcpy(slide + w, slide + d, e);
          w += e;
          d += e;
        }
        else                      /* do it slow to avoid memcpy()
overlap */

=========

Comments?


> -----Original Message-----
> From: Jim Meyering [mailto:address@hidden
> Sent: Sunday, January 10, 2010 4:58 PM
> To: Alain Magloire
> Cc: address@hidden
> Subject: Re: gzip use of memcpy
> 
> Alain Magloire wrote:
> >> > Index: inflate.c
> >> ...
> >> >          if (w - d >= e)
> >> >          {
> >> > -          memcpy(slide + w, slide + d, e);
> >> > +          memmove(slide + w, slide + d, e);
> >>
> >> Can you give sample values of w, d and e for which this change
> >> makes a difference?  Doesn't the preceding (w - d >= e) guard
> >> ensure that the source and destination buffers never overlap?
> >>
> >
> > According to our tester:
> >
> > The w==16316
> >     d==16322
> >     w-d == -6  // <-- Unsigned
> >
> > The bad file is an attachment; you could override the memcpy(3)
> > implementation with one checking for overlap for example.
> 
> Thank you!
> In the patch below, I've improved the guard, so as to retain the use
> of memcpy, when possible, since the following loop is essentially
memcopy.
> (still incomplete: I have to write a NEWS entry)
> 
> I was able to cook up a simple input file that triggers the erroneous
> memcpy in pre-patched code, and that is the memcpy-abuse test below.
> 
> However, I also wanted to demonstrate an actual failure
> that evokes the crc-error diagnostic using a simple input.
> Using your suggestion (a reverse-memcpy) and the sample input,
> I see this error:
> 
>     ./gzip -cd sella1.tar.gz > k
>     gzip: sella1.tar.gz: invalid compressed data--crc error
> 
> However, I've been unable to prepare another test.
> Perhaps because a losing .gz file must be created on
> a non-"Unix" system?
> 
>     $ file sella1.tar.gz
>     sella1.tar.gz: gzip compressed data, was "Suedtirol - Sella
> Ronda.tar",\
>     from FAT filesystem (MS-DOS, OS/2, NT), last modified: \
>     Thu Dec 10 15:13:15 2009
> 
> Even when I simply uncompress and recompress that same file (on
> Linux/GNU), the result does not provoke the failure.
> 
> 
> From 541bbd26d604494f51581ddde047b3f497a9fde5 Mon Sep 17 00:00:00 2001
> From: Jim Meyering <address@hidden>
> Date: Sun, 10 Jan 2010 20:53:10 +0100
> Subject: [PATCH] gzip -d would fail with a CRC error...
> 
> for some inputs, and some memcpy implementations.
> The inputs appear to have to have been compressed
> "from FAT filesystem (MS-DOS, OS/2, NT)", since the
> sole reproducer no longer evokes a CRC error when
> uncompressed and recompressed on a GNU/Linux system,
> and using a reverse-memcpy on over 100,000 inputs on
> a GNU/Linux system did not turn up another reproducer.
> * inflate.c (inflate_codes): Don't call memcpy with overlapping
regions.
> Properly detect when source and destination overlap.
> * tests/memcpy-abuse: New test, to trigger misbehavior.
> * Makefile.am (TESTS): Add it.
> Reported by Alain Magloire in
> http://thread.gmane.org/gmane.comp.gnu.gzip.bugs/307
> ---
>  Makefile.am        |    1 +
>  inflate.c          |    2 +-
>  tests/memcpy-abuse |   40 ++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 42 insertions(+), 1 deletions(-)
>  create mode 100644 tests/memcpy-abuse
> 
> diff --git a/Makefile.am b/Makefile.am
> index c0cd415..67dc18b 100644
> --- a/Makefile.am
> +++ b/Makefile.am
> @@ -104,6 +104,7 @@ check-local: $(FILES_TO_CHECK) $(bin_PROGRAMS)
> gzip.doc.gz
>       @echo 'Test succeeded.'
> 
>  TESTS =                                              \
> +  tests/memcpy-abuse                         \
>    tests/trailing-nul                         \
>    tests/zdiff                                        \
>    tests/zgrep-f
> diff --git a/inflate.c b/inflate.c
> index affab37..5b68314 100644
> --- a/inflate.c
> +++ b/inflate.c
> @@ -589,7 +589,7 @@ int bl, bd;             /* number of bits decoded
by
> tl[] and td[] */
>        do {
>          n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n
:
> e);
>  #if !defined(NOMEMCPY) && !defined(DEBUG)
> -        if (w - d >= e)         /* (this test assumes unsigned
> comparison) */
> +        if (d < w && w - d >= e)
>          {
>            memcpy(slide + w, slide + d, e);
>            w += e;
> diff --git a/tests/memcpy-abuse b/tests/memcpy-abuse
> new file mode 100644
> index 0000000..8f2abd5
> --- /dev/null
> +++ b/tests/memcpy-abuse
> @@ -0,0 +1,40 @@
> +#!/bin/sh
> +# Before gzip-1.4, this the use of memcpy in inflate_codes could
> +# mistakenly operate on overlapping regions.  Exercise that code.
> +
> +# Copyright (C) 2010 Free Software Foundation, Inc.
> +
> +# This program is free software: you can redistribute it and/or
modify
> +# it under the terms of the GNU General Public License as published
by
> +# the Free Software Foundation, either version 3 of the License, or
> +# (at your option) any later version.
> +
> +# This program is distributed in the hope that it will be useful,
> +# but WITHOUT ANY WARRANTY; without even the implied warranty of
> +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> +# GNU General Public License for more details.
> +
> +# You should have received a copy of the GNU General Public License
> +# along with this program.  If not, see
<http://www.gnu.org/licenses/>.
> +# limit so don't run it by default.
> +
> +if test "$VERBOSE" = yes; then
> +  set -x
> +  gzip --version
> +fi
> +
> +: ${srcdir=.}
> +. "$srcdir/tests/init.sh"; path_prepend_ .
> +
> +# The input must be larger than 32KiB and slightly
> +# less uniform than e.g., all zeros.
> +printf wxy%032767d 0 | tee in | gzip > in.gz || framework_failure
> +
> +fail=0
> +
> +# Before the fix, this would call memcpy with overlapping regions.
> +gzip -dc in.gz > out || fail=1
> +
> +compare in out || fail=1
> +
> +Exit $fail
> --
> 1.6.6.439.gaf68f