Debian Bug report logs - #270070
zlib1g: valgrind reports error in zlib

version graph

Package: zlib1g; Maintainer for zlib1g is Mark Brown <broonie@debian.org>; Source for zlib1g is src:zlib (PTS, buildd, popcon).

Reported by: Jason Dorje Short <jdorje@users.sourceforge.net>

Date: Sun, 5 Sep 2004 10:03:01 UTC

Severity: normal

Found in version 1:1.2.1.1-7

Fixed in version zlib/1:1.2.1.2-1

Done: Mark Brown <broonie@debian.org>

Bug is archived. No further changes may be made.

Forwarded to zlib@gzip.org

Toggle useless messages

View this report as an mbox folder, status mbox, maintainer mbox


Report forwarded to debian-bugs-dist@lists.debian.org, Mark Brown <broonie@debian.org>:
Bug#270070; Package zlib1g. (full text, mbox, link).


Acknowledgement sent to Jason Dorje Short <jdorje@users.sourceforge.net>:
New Bug report received and forwarded. Copy sent to Mark Brown <broonie@debian.org>. (full text, mbox, link).


Message #5 received at submit@bugs.debian.org (full text, mbox, reply):

From: Jason Dorje Short <jdorje@users.sourceforge.net>
To: Debian Bug Tracking System <submit@bugs.debian.org>
Subject: zlib1g: valgrind reports error in zlib
Date: Sun, 05 Sep 2004 05:49:42 -0400
Package: zlib1g
Version: 1:1.2.1.1-7
Severity: normal

I was using valgrind to debug my program (apt-cache show valgrind), and 
I got an error within zlib.  At first I assumed this was a (minor) error 
in my program, but after thorougly checking the data being sent to 
compress I convinced myself that it was all correct.

Valgrind couldn't tell me where in zlib the error was, until I compiled 
zlib myself (from apt-get source) and linked to it statically.  Then I 
got:

==21336==    at 0x8138002: longest_match (deflate.c:966)
==21336==    by 0x8137AEF: deflate_slow (deflate.c:1422)
==21336==    by 0x81365BF: deflate (deflate.c:630)
==21336==    by 0x8134353: compress2 (compress.c:49)
==21336==    by 0x80C8C9E: send_packet_data (packets.c:160)
==21336==    by 0x80D3AD4: send_packet_chat_msg_100 (packets_gen.c:4621)
==21336==    by 0x80D3CA1: send_packet_chat_msg (packets_gen.c:4676)
==21336==    by 0x8086455: vnotify_conn_ex (plrhand.c:1212)
==21336==    by 0x80864AD: notify_conn (plrhand.c:1236)
==21336==    by 0x806BBF7: establish_new_connection (connecthand.c:94)
==21336==    by 0x806C7C3: handle_login_request (connecthand.c:351)
==21336==    by 0x804F47B: handle_packet_input (srv_main.c:892)
==21336==    by 0x80A50A0: sniff_packets (sernet.c:616)
==21336==    by 0x8050701: srv_loop (srv_main.c:1606)
==21336==    by 0x80505FE: srv_main (srv_main.c:1565)
==21336==    by 0x804A289: main (civserver.c:170)

where the first three lines are within zlib.  When I attached the 
debugger to it I got for a backtrace

#0  0x08138002 in longest_match (s=0x1bbc15c0, cur_match=92) at 
deflate.c:966
#1  0x08137af0 in deflate_slow (s=0x1bbc15c0, flush=4) at deflate.c:1422
#2  0x081365c0 in deflate (strm=0x52bf9400, flush=4) at deflate.c:630

declate.c has at line 966:

        do {
        } while (*++scan == *++match && *++scan == *++match &&
                 *++scan == *++match && *++scan == *++match &&
                 *++scan == *++match && *++scan == *++match &&
                 *++scan == *++match && *++scan == *++match &&
                 scan < strend);

however I think this code reads beyond the length of the buffer.  In 
this case the buffer is 97 bytes long, but (scan - s->window) is 97 when 
this happens.  However (strend - s->window) is 351.  From up above

    register Bytef *strend = s->window + s->strstart + MAX_MATCH;

where MAX_MATCH is 258 and (s->strstart - s->window) == 93.

The only conclusion I can come to is that this piece of code simply 
doesn't check buffer overflow.  It will happily keep on reading 
characters up to 258 bytes after the end of the buffer.  This seems like 
a fairly major bug - although in almost all cases it is safe to read 
those bytes (the program won't crash from doing it), and the chance of 
the match that is found being inaccurate is quite low.  Nonetheless I 
imagine this is guaranteed to break zlib for certain inputs (if you want 
I will try to find one).

-jason

-- System Information:
Debian Release: 3.1
  APT prefers unstable
  APT policy: (500, 'unstable')
Architecture: i386 (i686)
Kernel: Linux 2.6.8-1-686
Locale: LANG=en_US, LC_CTYPE=en_US

Versions of packages zlib1g depends on:
ii  libc6                       2.3.2.ds1-16 GNU C Library: Shared libraries an

-- no debconf information



Information forwarded to debian-bugs-dist@lists.debian.org, Mark Brown <broonie@debian.org>:
Bug#270070; Package zlib1g. (full text, mbox, link).


Acknowledgement sent to Jason Dorje Short <jdorje@users.sf.net>:
Extra info received and forwarded to list. Copy sent to Mark Brown <broonie@debian.org>. (full text, mbox, link).


Message #10 received at 270070@bugs.debian.org (full text, mbox, reply):

From: Jason Dorje Short <jdorje@users.sf.net>
To: 270070@bugs.debian.org
Subject: Re: Bug#270070: Acknowledgement (zlib1g: valgrind reports error in zlib)
Date: Sun, 05 Sep 2004 06:28:35 -0400
[Message part 1 (text/plain, inline)]
Here is a program that allows the bug to be reproduced.


[jdorje@devon:~]$ gcc -Wall zlib-bug.c /usr/lib/libz.a && ./a.out
Compressing 1 bytes out of an uncompressed buffer of 1:
  Uncompressed: 1.  Compressed: 1.
Compressing 1 bytes out of an uncompressed buffer of 1000:
  Uncompressed: 1.  Compressed: 9.

Compressing 10 bytes out of an uncompressed buffer of 10:
  Uncompressed: 10.  Compressed: 10.
Compressing 10 bytes out of an uncompressed buffer of 1000:
  Uncompressed: 10.  Compressed: 11.

Compressing 100 bytes out of an uncompressed buffer of 100:
  Uncompressed: 100.  Compressed: 12.
Compressing 100 bytes out of an uncompressed buffer of 10000:
  Uncompressed: 100.  Compressed: 12.


If I have 1 byte uncompressed, this may compress differently depending 
on what data follows that byte.  In the case of the first call, I have 
100 bytes of 1's but I only compress the first 1 byte of it.  In the 
first case the second byte (the first byte after the end of the data I'm 
compressing) is 0.  In the second case the following bytes are all 1's. 
 So in the second case zlib determines a very large match and ends up 
doing very poorly.

The next two cases show less severe indications of the same problem.  In 
the second case it just causes a slight problem.  In the third case 
there is no visible difference in the output but zlib is still reading 
beyond the buffer it is given.  You can see this in the results of 
valgrind, also attached and taken from

  (valgrind --num-callers=50 ./a.out) >valgrind-output 2>&1

-jason
[zlib-bug.c (text/x-csrc, inline)]
#include <zlib.h>

#include <assert.h>
#include <string.h>
#include <stdio.h>

/*
 * Compress "size" bytes of data.  A buffer of size "bufsz" is used.  Each
 * byte in the buffer is set to 1.  The intent is to show that even if the
 * first "size" bytes are equal, compression may differ based on the bytes
 * after that (which zlib shouldn't be looking at).
 *
 */
void do_compress(int size, int bufsz)
{
  char uncompressed[bufsz + 1];
  long int uncompressed_sz = size, compressed_sz = bufsz;
  char compressed[compressed_sz];

  assert(bufsz >= size);
  memset(uncompressed, 1, sizeof(uncompressed));
  uncompressed[bufsz] = 0; /* Make sure it's terminated. */
  compress2(compressed, &compressed_sz, uncompressed, uncompressed_sz, -1);

  printf("Compressing %d bytes out of an uncompressed buffer of %d:\n",
	 size, bufsz);
  printf("  Uncompressed: %ld.  Compressed: %ld.\n",
	 uncompressed_sz, compressed_sz);
}

int main(void)
{
  do_compress(1, 1);
  do_compress(1, 1000);

  printf("\n");
  do_compress(10, 10);
  do_compress(10, 1000);

  /* This one actually does work. */
  printf("\n");
  do_compress(100, 100);
  do_compress(100, 10000);

  return 0;
}
[valgrind-output (text/plain, inline)]
==21976== Memcheck, a memory error detector for x86-linux.
==21976== Copyright (C) 2002-2004, and GNU GPL'd, by Julian Seward et al.
==21976== Using valgrind-2.2.0, a program supervision framework for x86-linux.
==21976== Copyright (C) 2000-2004, and GNU GPL'd, by Julian Seward et al.
==21976== For more details, rerun with: -v
==21976== 
==21976== Conditional jump or move depends on uninitialised value(s)
==21976==    at 0x804AD3E: _tr_flush_block (trees.c:934)
==21976==    by 0x804A4AA: deflate_slow (deflate.c:1499)
==21976==    by 0x8048EAF: deflate (deflate.c:630)
==21976==    by 0x80486A3: compress2 (compress.c:49)
==21976==    by 0x8048541: do_compress (in /home/jdorje/a.out)
==21976==    by 0x80485AF: main (in /home/jdorje/a.out)
==21976== 
==21976== Conditional jump or move depends on uninitialised value(s)
==21976==    at 0x804A916: longest_match (deflate.c:966)
==21976==    by 0x804A3DF: deflate_slow (deflate.c:1422)
==21976==    by 0x8048EAF: deflate (deflate.c:630)
==21976==    by 0x80486A3: compress2 (compress.c:49)
==21976==    by 0x8048541: do_compress (in /home/jdorje/a.out)
==21976==    by 0x80485CE: main (in /home/jdorje/a.out)
==21976== 
==21976== Conditional jump or move depends on uninitialised value(s)
==21976==    at 0x804A89C: longest_match (deflate.c:949)
==21976==    by 0x804A3DF: deflate_slow (deflate.c:1422)
==21976==    by 0x8048EAF: deflate (deflate.c:630)
==21976==    by 0x80486A3: compress2 (compress.c:49)
==21976==    by 0x8048541: do_compress (in /home/jdorje/a.out)
==21976==    by 0x80485CE: main (in /home/jdorje/a.out)
==21976== 
==21976== Conditional jump or move depends on uninitialised value(s)
==21976==    at 0x804A8CC: longest_match (deflate.c:996)
==21976==    by 0x804A3DF: deflate_slow (deflate.c:1422)
==21976==    by 0x8048EAF: deflate (deflate.c:630)
==21976==    by 0x80486A3: compress2 (compress.c:49)
==21976==    by 0x8048541: do_compress (in /home/jdorje/a.out)
==21976==    by 0x80485CE: main (in /home/jdorje/a.out)
==21976== 
==21976== Conditional jump or move depends on uninitialised value(s)
==21976==    at 0x804A928: longest_match (deflate.c:966)
==21976==    by 0x804A3DF: deflate_slow (deflate.c:1422)
==21976==    by 0x8048EAF: deflate (deflate.c:630)
==21976==    by 0x80486A3: compress2 (compress.c:49)
==21976==    by 0x8048541: do_compress (in /home/jdorje/a.out)
==21976==    by 0x80485FF: main (in /home/jdorje/a.out)
Compressing 1 bytes out of an uncompressed buffer of 1:
  Uncompressed: 1.  Compressed: 1.
Compressing 1 bytes out of an uncompressed buffer of 1000:
  Uncompressed: 1.  Compressed: 9.

Compressing 10 bytes out of an uncompressed buffer of 10:
  Uncompressed: 10.  Compressed: 10.
Compressing 10 bytes out of an uncompressed buffer of 1000:
  Uncompressed: 10.  Compressed: 11.

Compressing 100 bytes out of an uncompressed buffer of 100:
  Uncompressed: 100.  Compressed: 12.
Compressing 100 bytes out of an uncompressed buffer of 10000:
  Uncompressed: 100.  Compressed: 12.
==21976== 
==21976== ERROR SUMMARY: 15 errors from 5 contexts (suppressed: 11 from 1)
==21976== malloc/free: in use at exit: 0 bytes in 0 blocks.
==21976== malloc/free: 30 allocs, 30 frees, 1607760 bytes allocated.
==21976== For a detailed leak analysis,  rerun with: --leak-check=yes
==21976== For counts of detected errors, rerun with: -v

Information forwarded to debian-bugs-dist@lists.debian.org:
Bug#270070; Package zlib1g. (full text, mbox, link).


Acknowledgement sent to Mark Brown <broonie@debian.org>:
Extra info received and forwarded to list. (full text, mbox, link).


Message #15 received at 270070@bugs.debian.org (full text, mbox, reply):

From: Mark Brown <broonie@debian.org>
To: Jason Dorje Short <jdorje@users.sf.net>, 270070@bugs.debian.org
Subject: Re: Bug#270070: Acknowledgement (zlib1g: valgrind reports error in zlib)
Date: Sun, 5 Sep 2004 13:38:54 +0100
On Sun, Sep 05, 2004 at 06:28:35AM -0400, Jason Dorje Short wrote:

> If I have 1 byte uncompressed, this may compress differently depending 
> on what data follows that byte.  In the case of the first call, I have 
> 100 bytes of 1's but I only compress the first 1 byte of it.  In the 
> first case the second byte (the first byte after the end of the data I'm 
> compressing) is 0.  In the second case the following bytes are all 1's. 
>  So in the second case zlib determines a very large match and ends up 
> doing very poorly.

That's not actually what's going on with the varying output sizes.
compress2() requires that the output buffer be at least
compressBound(sourceLen).  In the cases where you're supplying one byte
and ten byte buffers compress2() is actually returning an error
Z_BUF_ERROR and not modifying the supplied buffer length.

Not that that does anything at all about the original problem.

-- 
"You grabbed my hand and we fell into it, like a daydream - or a fever."



Information forwarded to debian-bugs-dist@lists.debian.org, Mark Brown <broonie@debian.org>:
Bug#270070; Package zlib1g. (full text, mbox, link).


Acknowledgement sent to Jason Dorje Short <jdorje@users.sf.net>:
Extra info received and forwarded to list. Copy sent to Mark Brown <broonie@debian.org>. (full text, mbox, link).


Message #20 received at 270070@bugs.debian.org (full text, mbox, reply):

From: Jason Dorje Short <jdorje@users.sf.net>
To: 270070@bugs.debian.org
Subject: Re: Bug#270070: Acknowledgement (zlib1g: valgrind reports error in zlib)
Date: Sun, 05 Sep 2004 13:44:39 -0400
Mark Brown wrote:
> On Sun, Sep 05, 2004 at 06:28:35AM -0400, Jason Dorje Short wrote:
> 
>>If I have 1 byte uncompressed, this may compress differently depending 
>>on what data follows that byte.  In the case of the first call, I have 
>>100 bytes of 1's but I only compress the first 1 byte of it.  In the 
>>first case the second byte (the first byte after the end of the data I'm 
>>compressing) is 0.  In the second case the following bytes are all 1's. 
>> So in the second case zlib determines a very large match and ends up 
>>doing very poorly.
> 
> 
> That's not actually what's going on with the varying output sizes.
> compress2() requires that the output buffer be at least
> compressBound(sourceLen).  In the cases where you're supplying one byte
> and ten byte buffers compress2() is actually returning an error
> Z_BUF_ERROR and not modifying the supplied buffer length.
> 
> Not that that does anything at all about the original problem.

Yeah, see my later reply.

My fear is that since there seem to be no side effects of this bug, you 
guys will think it's a feature :-).  This code seems to be pretty 
closely optimized, and it might be hard to add a bounds check without 
slowing it down.  But not only does that make my debugging efforts 
harder, it will probably cause a segfault (invalid memory access) for 
some user at some point in the future.

jason



Information forwarded to debian-bugs-dist@lists.debian.org:
Bug#270070; Package zlib1g. (full text, mbox, link).


Acknowledgement sent to Mark Brown <broonie@debian.org>:
Extra info received and forwarded to list. (full text, mbox, link).


Message #25 received at 270070@bugs.debian.org (full text, mbox, reply):

From: Mark Brown <broonie@debian.org>
To: Jason Dorje Short <jdorje@users.sf.net>, 270070@bugs.debian.org
Subject: Re: Bug#270070: Acknowledgement (zlib1g: valgrind reports error in zlib)
Date: Sun, 5 Sep 2004 21:05:02 +0100
On Sun, Sep 05, 2004 at 01:44:39PM -0400, Jason Dorje Short wrote:

> Yeah, see my later reply.

I don't appear to have seen that?  There were only two messages I saw
prior to this one and I was replying to the second.

> My fear is that since there seem to be no side effects of this bug, you 
> guys will think it's a feature :-).  This code seems to be pretty 

No, it's definately a bug.  The bounds checking is mostly rolled out of
the main loop but it should be there.

-- 
"You grabbed my hand and we fell into it, like a daydream - or a fever."



Information forwarded to debian-bugs-dist@lists.debian.org, Mark Brown <broonie@debian.org>:
Bug#270070; Package zlib1g. (full text, mbox, link).


Acknowledgement sent to Jason Dorje Short <jdorje@users.sf.net>:
Extra info received and forwarded to list. Copy sent to Mark Brown <broonie@debian.org>. (full text, mbox, link).


Message #30 received at 270070@bugs.debian.org (full text, mbox, reply):

From: Jason Dorje Short <jdorje@users.sf.net>
To: 270070@bugs.debian.org
Subject: Re: Bug#270070: Acknowledgement (zlib1g: valgrind reports error in zlib)
Date: Sun, 05 Sep 2004 16:38:05 -0400
Mark Brown wrote:
> On Sun, Sep 05, 2004 at 01:44:39PM -0400, Jason Dorje Short wrote:
> 
> 
>>Yeah, see my later reply.
> 
> 
> I don't appear to have seen that?  There were only two messages I saw
> prior to this one and I was replying to the second.

Looks like I sent it to the wrong address.

Of course the compressed size was 1 because the compression buffer was 
of size 1.

jason




-------- Original Message --------
Subject: Re: Bug#270070: Info received
Date: Sun, 05 Sep 2004 06:46:01 -0400
From: Jason Dorje Short <jdorje@users.sf.net>
To: Debian Bug Tracking System <owner@bugs.debian.org>
References: <413AEA53.2060302@users.sf.net> 
<handler.270070.B270070.109438012720291.ackinfo@bugs.debian.org>

I am partially mistaken.  The differences in compressed sizes in my demo
program are because the compressed buffer is limited in the program.
However the memory errors are real.

jason



Reply sent to 270070@bugs.debian.org:
You have marked Bug as forwarded. (full text, mbox, link).


Message #33 received at 270070-forwarded@bugs.debian.org (full text, mbox, reply):

From: Mark Brown <broonie@sirena.org.uk>
To: zlib@gzip.org
Cc: 270070-forwarded@bugs.debian.org
Subject: Uninitialised memory reads in zlib
Date: Sun, 5 Sep 2004 23:07:14 +0100
[Message part 1 (text/plain, inline)]
The enclosed bug report was submitted against the Debian zlib package,
reporting some accesses to uninitialised memory discovered using
valgrind.  One of them was a simple case of not initialising the data
type in deflateInit2_() and is fixed with the following patch:

diff -urN zlib-1.2.1.1.orig/deflate.c zlib-data_type/deflate.c
--- zlib-1.2.1.1.orig/deflate.c	2003-11-12 16:48:21.000000000 +0000
+++ zlib-data_type/deflate.c	2004-09-05 14:04:20.076723997 +0100
@@ -372,6 +372,7 @@
     s = (deflate_state *)strm->state;
     s->pending = 0;
     s->pending_out = s->pending_buf;
+    s->data_type = Z_UNKNOWN;
 
     if (s->wrap < 0) {
         s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */

The others concern the handling of end of stream conditions in the
deflate implementations: longest_match() winds up looking beyond the end
of data while looking for a match (though I *think* it never reads
beyond the end of the window).  Both the unrolled comparison loop or the
checks for match[best_len] can look beyond the end of the input data.

I've not yet been able to decide if this is actually a problem or if the
results will be ignored but I've no more time to look at this today so
felt it was safer to forward this on to you at this point.

Note that the submitter was initially confused by the buffer size
requirements for compress().

-- 
"You grabbed my hand and we fell into it, like a daydream - or a fever."
[Message part 2 (message/rfc822, inline)]
From: Jason Dorje Short <jdorje@users.sf.net>
To: 270070@bugs.debian.org
Subject: Bug#270070: Acknowledgement (zlib1g: valgrind reports error in zlib)
Date: Sun, 05 Sep 2004 06:28:35 -0400
[Message part 3 (text/plain, inline)]
Here is a program that allows the bug to be reproduced.


[jdorje@devon:~]$ gcc -Wall zlib-bug.c /usr/lib/libz.a && ./a.out
Compressing 1 bytes out of an uncompressed buffer of 1:
  Uncompressed: 1.  Compressed: 1.
Compressing 1 bytes out of an uncompressed buffer of 1000:
  Uncompressed: 1.  Compressed: 9.

Compressing 10 bytes out of an uncompressed buffer of 10:
  Uncompressed: 10.  Compressed: 10.
Compressing 10 bytes out of an uncompressed buffer of 1000:
  Uncompressed: 10.  Compressed: 11.

Compressing 100 bytes out of an uncompressed buffer of 100:
  Uncompressed: 100.  Compressed: 12.
Compressing 100 bytes out of an uncompressed buffer of 10000:
  Uncompressed: 100.  Compressed: 12.


If I have 1 byte uncompressed, this may compress differently depending 
on what data follows that byte.  In the case of the first call, I have 
100 bytes of 1's but I only compress the first 1 byte of it.  In the 
first case the second byte (the first byte after the end of the data I'm 
compressing) is 0.  In the second case the following bytes are all 1's. 
 So in the second case zlib determines a very large match and ends up 
doing very poorly.

The next two cases show less severe indications of the same problem.  In 
the second case it just causes a slight problem.  In the third case 
there is no visible difference in the output but zlib is still reading 
beyond the buffer it is given.  You can see this in the results of 
valgrind, also attached and taken from

  (valgrind --num-callers=50 ./a.out) >valgrind-output 2>&1

-jason
[zlib-bug.c (text/x-csrc, inline)]
#include <zlib.h>

#include <assert.h>
#include <string.h>
#include <stdio.h>

/*
 * Compress "size" bytes of data.  A buffer of size "bufsz" is used.  Each
 * byte in the buffer is set to 1.  The intent is to show that even if the
 * first "size" bytes are equal, compression may differ based on the bytes
 * after that (which zlib shouldn't be looking at).
 *
 */
void do_compress(int size, int bufsz)
{
  char uncompressed[bufsz + 1];
  long int uncompressed_sz = size, compressed_sz = bufsz;
  char compressed[compressed_sz];

  assert(bufsz >= size);
  memset(uncompressed, 1, sizeof(uncompressed));
  uncompressed[bufsz] = 0; /* Make sure it's terminated. */
  compress2(compressed, &compressed_sz, uncompressed, uncompressed_sz, -1);

  printf("Compressing %d bytes out of an uncompressed buffer of %d:\n",
	 size, bufsz);
  printf("  Uncompressed: %ld.  Compressed: %ld.\n",
	 uncompressed_sz, compressed_sz);
}

int main(void)
{
  do_compress(1, 1);
  do_compress(1, 1000);

  printf("\n");
  do_compress(10, 10);
  do_compress(10, 1000);

  /* This one actually does work. */
  printf("\n");
  do_compress(100, 100);
  do_compress(100, 10000);

  return 0;
}
[valgrind-output (text/plain, inline)]
==21976== Memcheck, a memory error detector for x86-linux.
==21976== Copyright (C) 2002-2004, and GNU GPL'd, by Julian Seward et al.
==21976== Using valgrind-2.2.0, a program supervision framework for x86-linux.
==21976== Copyright (C) 2000-2004, and GNU GPL'd, by Julian Seward et al.
==21976== For more details, rerun with: -v
==21976== 
==21976== Conditional jump or move depends on uninitialised value(s)
==21976==    at 0x804AD3E: _tr_flush_block (trees.c:934)
==21976==    by 0x804A4AA: deflate_slow (deflate.c:1499)
==21976==    by 0x8048EAF: deflate (deflate.c:630)
==21976==    by 0x80486A3: compress2 (compress.c:49)
==21976==    by 0x8048541: do_compress (in /home/jdorje/a.out)
==21976==    by 0x80485AF: main (in /home/jdorje/a.out)
==21976== 
==21976== Conditional jump or move depends on uninitialised value(s)
==21976==    at 0x804A916: longest_match (deflate.c:966)
==21976==    by 0x804A3DF: deflate_slow (deflate.c:1422)
==21976==    by 0x8048EAF: deflate (deflate.c:630)
==21976==    by 0x80486A3: compress2 (compress.c:49)
==21976==    by 0x8048541: do_compress (in /home/jdorje/a.out)
==21976==    by 0x80485CE: main (in /home/jdorje/a.out)
==21976== 
==21976== Conditional jump or move depends on uninitialised value(s)
==21976==    at 0x804A89C: longest_match (deflate.c:949)
==21976==    by 0x804A3DF: deflate_slow (deflate.c:1422)
==21976==    by 0x8048EAF: deflate (deflate.c:630)
==21976==    by 0x80486A3: compress2 (compress.c:49)
==21976==    by 0x8048541: do_compress (in /home/jdorje/a.out)
==21976==    by 0x80485CE: main (in /home/jdorje/a.out)
==21976== 
==21976== Conditional jump or move depends on uninitialised value(s)
==21976==    at 0x804A8CC: longest_match (deflate.c:996)
==21976==    by 0x804A3DF: deflate_slow (deflate.c:1422)
==21976==    by 0x8048EAF: deflate (deflate.c:630)
==21976==    by 0x80486A3: compress2 (compress.c:49)
==21976==    by 0x8048541: do_compress (in /home/jdorje/a.out)
==21976==    by 0x80485CE: main (in /home/jdorje/a.out)
==21976== 
==21976== Conditional jump or move depends on uninitialised value(s)
==21976==    at 0x804A928: longest_match (deflate.c:966)
==21976==    by 0x804A3DF: deflate_slow (deflate.c:1422)
==21976==    by 0x8048EAF: deflate (deflate.c:630)
==21976==    by 0x80486A3: compress2 (compress.c:49)
==21976==    by 0x8048541: do_compress (in /home/jdorje/a.out)
==21976==    by 0x80485FF: main (in /home/jdorje/a.out)
Compressing 1 bytes out of an uncompressed buffer of 1:
  Uncompressed: 1.  Compressed: 1.
Compressing 1 bytes out of an uncompressed buffer of 1000:
  Uncompressed: 1.  Compressed: 9.

Compressing 10 bytes out of an uncompressed buffer of 10:
  Uncompressed: 10.  Compressed: 10.
Compressing 10 bytes out of an uncompressed buffer of 1000:
  Uncompressed: 10.  Compressed: 11.

Compressing 100 bytes out of an uncompressed buffer of 100:
  Uncompressed: 100.  Compressed: 12.
Compressing 100 bytes out of an uncompressed buffer of 10000:
  Uncompressed: 100.  Compressed: 12.
==21976== 
==21976== ERROR SUMMARY: 15 errors from 5 contexts (suppressed: 11 from 1)
==21976== malloc/free: in use at exit: 0 bytes in 0 blocks.
==21976== malloc/free: 30 allocs, 30 frees, 1607760 bytes allocated.
==21976== For a detailed leak analysis,  rerun with: --leak-check=yes
==21976== For counts of detected errors, rerun with: -v
[Message part 6 (message/rfc822, inline)]
From: Jason Dorje Short <jdorje@users.sf.net>
To: 270070@bugs.debian.org
Subject: Bug#270070: Acknowledgement (zlib1g: valgrind reports error in zlib)
Date: Sun, 05 Sep 2004 13:44:39 -0400
Mark Brown wrote:
> On Sun, Sep 05, 2004 at 06:28:35AM -0400, Jason Dorje Short wrote:
> 
>>If I have 1 byte uncompressed, this may compress differently depending 
>>on what data follows that byte.  In the case of the first call, I have 
>>100 bytes of 1's but I only compress the first 1 byte of it.  In the 
>>first case the second byte (the first byte after the end of the data I'm 
>>compressing) is 0.  In the second case the following bytes are all 1's. 
>> So in the second case zlib determines a very large match and ends up 
>>doing very poorly.
> 
> 
> That's not actually what's going on with the varying output sizes.
> compress2() requires that the output buffer be at least
> compressBound(sourceLen).  In the cases where you're supplying one byte
> and ten byte buffers compress2() is actually returning an error
> Z_BUF_ERROR and not modifying the supplied buffer length.
> 
> Not that that does anything at all about the original problem.

Yeah, see my later reply.

My fear is that since there seem to be no side effects of this bug, you 
guys will think it's a feature :-).  This code seems to be pretty 
closely optimized, and it might be hard to add a bounds check without 
slowing it down.  But not only does that make my debugging efforts 
harder, it will probably cause a segfault (invalid memory access) for 
some user at some point in the future.

jason

[Message part 7 (message/rfc822, inline)]
From: Jason Dorje Short <jdorje@users.sf.net>
To: 270070@bugs.debian.org
Subject: Bug#270070: Acknowledgement (zlib1g: valgrind reports error in zlib)
Date: Sun, 05 Sep 2004 16:38:05 -0400
Mark Brown wrote:
> On Sun, Sep 05, 2004 at 01:44:39PM -0400, Jason Dorje Short wrote:
> 
> 
>>Yeah, see my later reply.
> 
> 
> I don't appear to have seen that?  There were only two messages I saw
> prior to this one and I was replying to the second.

Looks like I sent it to the wrong address.

Of course the compressed size was 1 because the compression buffer was 
of size 1.

jason




-------- Original Message --------
Subject: Re: Bug#270070: Info received
Date: Sun, 05 Sep 2004 06:46:01 -0400
From: Jason Dorje Short <jdorje@users.sf.net>
To: Debian Bug Tracking System <owner@bugs.debian.org>
References: <413AEA53.2060302@users.sf.net> 
<handler.270070.B270070.109438012720291.ackinfo@bugs.debian.org>

I am partially mistaken.  The differences in compressed sizes in my demo
program are because the compressed buffer is limited in the program.
However the memory errors are real.

jason

[Message part 8 (message/rfc822, inline)]
From: Jason Dorje Short <jdorje@users.sourceforge.net>
To: Debian Bug Tracking System <submit@bugs.debian.org>
Subject: Bug#270070: zlib1g: valgrind reports error in zlib
Date: Sun, 05 Sep 2004 05:49:42 -0400
Package: zlib1g
Version: 1:1.2.1.1-7
Severity: normal

I was using valgrind to debug my program (apt-cache show valgrind), and 
I got an error within zlib.  At first I assumed this was a (minor) error 
in my program, but after thorougly checking the data being sent to 
compress I convinced myself that it was all correct.

Valgrind couldn't tell me where in zlib the error was, until I compiled 
zlib myself (from apt-get source) and linked to it statically.  Then I 
got:

==21336==    at 0x8138002: longest_match (deflate.c:966)
==21336==    by 0x8137AEF: deflate_slow (deflate.c:1422)
==21336==    by 0x81365BF: deflate (deflate.c:630)
==21336==    by 0x8134353: compress2 (compress.c:49)
==21336==    by 0x80C8C9E: send_packet_data (packets.c:160)
==21336==    by 0x80D3AD4: send_packet_chat_msg_100 (packets_gen.c:4621)
==21336==    by 0x80D3CA1: send_packet_chat_msg (packets_gen.c:4676)
==21336==    by 0x8086455: vnotify_conn_ex (plrhand.c:1212)
==21336==    by 0x80864AD: notify_conn (plrhand.c:1236)
==21336==    by 0x806BBF7: establish_new_connection (connecthand.c:94)
==21336==    by 0x806C7C3: handle_login_request (connecthand.c:351)
==21336==    by 0x804F47B: handle_packet_input (srv_main.c:892)
==21336==    by 0x80A50A0: sniff_packets (sernet.c:616)
==21336==    by 0x8050701: srv_loop (srv_main.c:1606)
==21336==    by 0x80505FE: srv_main (srv_main.c:1565)
==21336==    by 0x804A289: main (civserver.c:170)

where the first three lines are within zlib.  When I attached the 
debugger to it I got for a backtrace

#0  0x08138002 in longest_match (s=0x1bbc15c0, cur_match=92) at 
deflate.c:966
#1  0x08137af0 in deflate_slow (s=0x1bbc15c0, flush=4) at deflate.c:1422
#2  0x081365c0 in deflate (strm=0x52bf9400, flush=4) at deflate.c:630

declate.c has at line 966:

        do {
        } while (*++scan == *++match && *++scan == *++match &&
                 *++scan == *++match && *++scan == *++match &&
                 *++scan == *++match && *++scan == *++match &&
                 *++scan == *++match && *++scan == *++match &&
                 scan < strend);

however I think this code reads beyond the length of the buffer.  In 
this case the buffer is 97 bytes long, but (scan - s->window) is 97 when 
this happens.  However (strend - s->window) is 351.  From up above

    register Bytef *strend = s->window + s->strstart + MAX_MATCH;

where MAX_MATCH is 258 and (s->strstart - s->window) == 93.

The only conclusion I can come to is that this piece of code simply 
doesn't check buffer overflow.  It will happily keep on reading 
characters up to 258 bytes after the end of the buffer.  This seems like 
a fairly major bug - although in almost all cases it is safe to read 
those bytes (the program won't crash from doing it), and the chance of 
the match that is found being inaccurate is quite low.  Nonetheless I 
imagine this is guaranteed to break zlib for certain inputs (if you want 
I will try to find one).

-jason

-- System Information:
Debian Release: 3.1
  APT prefers unstable
  APT policy: (500, 'unstable')
Architecture: i386 (i686)
Kernel: Linux 2.6.8-1-686
Locale: LANG=en_US, LC_CTYPE=en_US

Versions of packages zlib1g depends on:
ii  libc6                       2.3.2.ds1-16 GNU C Library: Shared libraries an

-- no debconf information


Information forwarded to debian-bugs-dist@lists.debian.org, Mark Brown <broonie@debian.org>:
Bug#270070; Package zlib1g. (full text, mbox, link).


Acknowledgement sent to Mark Adler <madler@alumni.caltech.edu>:
Extra info received and forwarded to list. Copy sent to Mark Brown <broonie@debian.org>. (full text, mbox, link).


Message #38 received at 270070@bugs.debian.org (full text, mbox, reply):

From: Mark Adler <madler@alumni.caltech.edu>
To: 270070@bugs.debian.org
Cc: jloup@gzip.org
Subject: Re: Uninitialised memory reads in zlib
Date: Sun, 5 Sep 2004 21:36:36 -0700
On Sep 5, 2004, at 3:07 PM, Mark Brown wrote:
> One of them was a simple case of not initialising the data
> type in deflateInit2_() and is fixed with the following patch:

This has already been fixed in a pre-release version of zlib.

> The others concern the handling of end of stream conditions in the
> deflate implementations: longest_match() winds up looking beyond the 
> end
> of data while looking for a match (though I *think* it never reads
> beyond the end of the window).  Both the unrolled comparison loop or 
> the
> checks for match[best_len] can look beyond the end of the input data.

I went through that in detail about a year or two ago and concluded 
that it was not a problem, and furthermore could not even cause 
indeterminism in the result of deflating.  It was intentional in the 
design to improve speed.

mark




Information forwarded to debian-bugs-dist@lists.debian.org, Mark Brown <broonie@debian.org>:
Bug#270070; Package zlib1g. (full text, mbox, link).


Acknowledgement sent to 270070@bugs.debian.org:
Extra info received and forwarded to list. Copy sent to Mark Brown <broonie@debian.org>. (full text, mbox, link).


Message #43 received at 270070@bugs.debian.org (full text, mbox, reply):

From: Mark Brown <broonie@debian.org>
To: Mark Adler <madler@alumni.caltech.edu>, 270070@bugs.debian.org
Subject: Re: Bug#270070: Uninitialised memory reads in zlib
Date: Mon, 6 Sep 2004 10:22:52 +0100
On Sun, Sep 05, 2004 at 09:36:36PM -0700, Mark Adler wrote:

> I went through that in detail about a year or two ago and concluded 
> that it was not a problem, and furthermore could not even cause 
> indeterminism in the result of deflating.  It was intentional in the 
> design to improve speed.

Yeah, I'd got as far as deciding that the deflate itself was fine and
ignored the result.  My only remaining concern was that it may be
possible to read beyond the end of the window (which could potentially
cause trouble if there's no memory mapped there).

-- 
"You grabbed my hand and we fell into it, like a daydream - or a fever."



Information forwarded to debian-bugs-dist@lists.debian.org, Mark Brown <broonie@debian.org>:
Bug#270070; Package zlib1g. (full text, mbox, link).


Acknowledgement sent to Mark Adler <madler@alumni.caltech.edu>:
Extra info received and forwarded to list. Copy sent to Mark Brown <broonie@debian.org>. (full text, mbox, link).


Message #48 received at 270070@bugs.debian.org (full text, mbox, reply):

From: Mark Adler <madler@alumni.caltech.edu>
To: 270070@bugs.debian.org
Subject: Re: Bug#270070: Uninitialised memory reads in zlib
Date: Mon, 6 Sep 2004 09:24:27 -0700
On Sep 6, 2004, at 2:22 AM, Mark Brown wrote:
> Yeah, I'd got as far as deciding that the deflate itself was fine and
> ignored the result.  My only remaining concern was that it may be
> possible to read beyond the end of the window (which could potentially
> cause trouble if there's no memory mapped there).

No, deflate will not read past the allocated memory.  For reference, I 
have copied an earlier posting below.

mark


From: madler@alumni.caltech.edu (Mark Adler)
Newsgroups: comp.compression
Subject: Re: zlib-1.2.1 valgrind warnings
References: <30cb2c4.0402221727.708815cf@posting.google.com>
NNTP-Posting-Host: 24.205.59.68
Message-ID: <7ab39013.0402240513.1cbfc3bf@posting.google.com>

bybell@rocketmail.com (Anthony J Bybell) wrote in message 
news:<30cb2c4.0402221727.708815cf@posting.google.com>...
> These might have impact on function.

They don't.  Comments below.

> ==31634==    at 0x8056FB8: longest_match (deflate.c:952)
> ==31634==    at 0x8057084: longest_match (deflate.c:966)

Those are intentional.  For speed, a string comparison loop checks for
the end of the string only every eight byte comparisons, and so can go
past the end.  The comparisons are within allocated memory, and
matches past the end are not used.  So there is no impact on function.

> ==31634==    at 0x805B1C2: _tr_flush_block (trees.c:934)

This one was interesting.  I found that the data_type variable in the
zlib stream structure has never been set in all these years that zlib
has been out there, and no one has ever noticed!  zlib.h says:
"deflate() may update data_type if it can make a good guess about the
input data type (Z_ASCII or Z_BINARY)."  Fortunately it says "may",
since it never has.  The bug is that there is another data_type in an
internal structure that is set, but that is never copied back to the
user-supplied structure.  Furthermore, that internal copy is never
initialized, hence the valgrind error.  This bug will be fixed in the
next version of zlib.  In all versions of zlib, data_type in the
user-supplied strucure is properly initialized to Z_UNKNOWN.

In any case, not setting data_type based on the input is permitted by
the interface description in zlib.h, and so no harm, no foul.  The
guess about binary vs. ascii has no effect whatsover on the
compression.

By the way, these valgrind warnings are only showing up now in zlib
1.2.1 because previous versions of zlib (1.1.4 and earlier) defaulted
to calloc() for memory allocation, but zlib 1.2.1 now defaults to
malloc() in most cases for better speed.  calloc() initializes
allocated memory to zero, but malloc() does not.

mark




Information forwarded to debian-bugs-dist@lists.debian.org:
Bug#270070; Package zlib1g. (full text, mbox, link).


Acknowledgement sent to Mark Brown <broonie@debian.org>:
Extra info received and forwarded to list. (full text, mbox, link).


Message #53 received at 270070@bugs.debian.org (full text, mbox, reply):

From: Mark Brown <broonie@debian.org>
To: Mark Adler <madler@alumni.caltech.edu>, 270070@bugs.debian.org
Subject: Re: Bug#270070: Uninitialised memory reads in zlib
Date: Mon, 6 Sep 2004 17:44:53 +0100
On Mon, Sep 06, 2004 at 09:24:27AM -0700, Mark Adler wrote:

> No, deflate will not read past the allocated memory.  For reference, I 
> have copied an earlier posting below.

OK, I'll believe you :) .  It would probably be worth getting this added
to valgrind's default ignore list in order to avoid extra worries.

-- 
"You grabbed my hand and we fell into it, like a daydream - or a fever."



Reply sent to Mark Brown <broonie@debian.org>:
You have taken responsibility. (full text, mbox, link).


Notification sent to Jason Dorje Short <jdorje@users.sourceforge.net>:
Bug acknowledged by developer. (full text, mbox, link).


Message #58 received at 270070-close@bugs.debian.org (full text, mbox, reply):

From: Mark Brown <broonie@debian.org>
To: 270070-close@bugs.debian.org
Subject: Bug#270070: fixed in zlib 1:1.2.1.2-1
Date: Mon, 13 Sep 2004 11:32:35 -0400
Source: zlib
Source-Version: 1:1.2.1.2-1

We believe that the bug you reported is fixed in the latest version of
zlib, which is due to be installed in the Debian FTP archive:

zlib-bin_1.2.1.2-1_i386.deb
  to pool/main/z/zlib/zlib-bin_1.2.1.2-1_i386.deb
zlib1g-dev_1.2.1.2-1_i386.deb
  to pool/main/z/zlib/zlib1g-dev_1.2.1.2-1_i386.deb
zlib1g-udeb_1.2.1.2-1_i386.udeb
  to pool/main/z/zlib/zlib1g-udeb_1.2.1.2-1_i386.udeb
zlib1g_1.2.1.2-1_i386.deb
  to pool/main/z/zlib/zlib1g_1.2.1.2-1_i386.deb
zlib_1.2.1.2-1.diff.gz
  to pool/main/z/zlib/zlib_1.2.1.2-1.diff.gz
zlib_1.2.1.2-1.dsc
  to pool/main/z/zlib/zlib_1.2.1.2-1.dsc
zlib_1.2.1.2.orig.tar.gz
  to pool/main/z/zlib/zlib_1.2.1.2.orig.tar.gz



A summary of the changes between this version and the previous one is
attached.

Thank you for reporting the bug, which will now be closed.  If you
have further comments please address them to 270070@bugs.debian.org,
and the maintainer will reopen the bug report if appropriate.

Debian distribution maintenance software
pp.
Mark Brown <broonie@debian.org> (supplier of updated zlib package)

(This message was generated automatically at their request; if you
believe that there is a problem with it please contact the archive
administrators by mailing ftpmaster@debian.org)


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Format: 1.7
Date: Sat, 11 Sep 2004 10:59:41 +0100
Source: zlib
Binary: zlib1g-dev zlib1g lib64z1-dev lib64z1 zlib1g-udeb zlib-bin
Architecture: source i386
Version: 1:1.2.1.2-1
Distribution: unstable
Urgency: low
Maintainer: Mark Brown <broonie@debian.org>
Changed-By: Mark Brown <broonie@debian.org>
Description: 
 zlib-bin   - compression library - sample programs
 zlib1g     - compression library - runtime
 zlib1g-dev - compression library - development
 zlib1g-udeb - compression library - runtime for Debian installer (udeb)
Closes: 258087 270070
Changes: 
 zlib (1:1.2.1.2-1) unstable; urgency=low
 .
   * New upstream release.
   * Upstream now includes patch improving error reporting when gzio is used on
     empty files (closes: #258087).
   * Upstream have fixed a valgrind warning.  Other valgrind warnings remain
     but have been analysed and found safe - uninitialised memory is read from
     a buffer allocated by zlib during deflate but bounds checking is
     subsequently performed and the output unaffected (closes: #270070).
Files: 
 b6f6a9424638523bf54be14dee4661a7 679 libs optional zlib_1.2.1.2-1.dsc
 dbe38e0ac57a7a47a18af9ff0bcbda83 356912 libs optional zlib_1.2.1.2.orig.tar.gz
 87918bb6028ed0845460a44ceb123ea2 13887 libs optional zlib_1.2.1.2-1.diff.gz
 cf0cdd819196cd831942e82caf145816 38370 debian-installer optional zlib1g-udeb_1.2.1.2-1_i386.udeb
 1e9ab9e690c7f2d374f54ff6ce5acce8 62654 libs required zlib1g_1.2.1.2-1_i386.deb
 f5f3dd64c97be033962e823261ad87be 414216 libdevel optional zlib1g-dev_1.2.1.2-1_i386.deb
 b366d6e4f1188e84dbff9d8744aa6453 25448 utils optional zlib-bin_1.2.1.2-1_i386.deb
package-type: udeb

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)

iD8DBQFBQs5zJ2Vo11xhU60RAu4bAJ9JEnm6egzRlDT7eAlMwp4M+P0sMQCdHNWO
/4QOswTAYWxe+obRVfkp0pY=
=zVTH
-----END PGP SIGNATURE-----




Send a report that this bug log contains spam.


Debian bug tracking system administrator <owner@bugs.debian.org>. Last modified: Wed Sep 6 03:50:13 2023; Machine Name: buxtehude

Debian Bug tracking system

Debbugs is free software and licensed under the terms of the GNU Public License version 2. The current version can be obtained from https://bugs.debian.org/debbugs-source/.

Copyright © 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson, 2005-2017 Don Armstrong, and many other contributors.