Re: gzip use of memcpy

[Jim Meyering]

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