public inbox for bzip2-devel@sourceware.org
 help / color / mirror / Atom feed
From: Julian Seward <jseward@acm.org>
To: Federico Mena Quintero <federico@gnome.org>,
	Mark Wielaard <mark@klomp.org>,
	bzip2-devel@sourceware.org
Subject: Re: bzip2 1.0.7 released
Date: Tue, 01 Jan 2019 00:00:00 -0000	[thread overview]
Message-ID: <e73799c0-cb3b-c9f8-84c8-53d028dbe1d5@acm.org> (raw)
In-Reply-To: <8c4d5cf2479253406dacdee122692cc77771afb9.camel@gnome.org>


Mark, Federico,

Thank you both for the analysis.  Here's my Eur 0.02:

I see the following, in the 1.0.6 sources:

* bzlib_private.h:#define BZ_MAX_SELECTORS (2 + (900000 / BZ_G_SIZE))

* compress.c has
    AssertH( nSelectors < 32768 &&
             nSelectors <= (2 + (900000 / BZ_G_SIZE)),
             3003 );

* decompress.c has (well, wants to have)
       if (nSelectors < 1 || nSelectors > BZ_MAX_SELECTORS)

Mark observes this:

 > So it looks like some implementations might add more selectors than
 > necessary. For example lbzip2 seems to use a max of 18000 + 1 + 7.  Which
 > might explain why our 18002 = 2 + (900000 / 50) isn't enough, and why my
 > random increase of 5 seemed to work for the given file.

Seems plausible, except that (18000 + 1 + 7) - (2 + (900000 / 50)) == 6,
not 5.  So we'd have to increase the number by 6, not 5.

IIUC (which I may not), bzip2-1.0.7 is internally self-consistent, in that it
won't create more than 18002 selectors, and it also won't accept more than
18002 selectors.  But some lbzip2 implementations can create up to 18008
selectors (per Mark's comments), and that is what is causing the problem here.

I would propose the following fix for discussion:

* split BZ_MAX_SELECTORS into two different values:

   - BZ_MAX_SELECTORS_ENC = (2 + (900000 / BZ_G_SIZE)) [= 18002], the max
     number of selectors that bzip2 can create ("encode")

   - BZ_MAX_SELECTORS_DEC = BZ_MAX_SELECTORS_ENC + 6 [= 18008], the max number
     of selectors that we'll accept during decoding, and add a comment
     explaining that the difference is due to buggy lbzip2/whatever creating
     more than BZ_MAX_SELECTORS_ENC

* use BZ_MAX_SELECTORS_ENC to dimension the arrays in struct EState

* use BZ_MAX_SELECTORS_DEC to dimension the arrays in struct DState, and
   for the new decompress.c range check

* change the compress.c assertion

    AssertH( nSelectors < 32768 &&
             nSelectors <= (2 + (900000 / BZ_G_SIZE)),
             3003 );

    to actually mention BZ_MAX_SELECTORS_ENC directly, instead of
    (2 + (900000 / BZ_G_SIZE)), [which is embarrassingly lame]

It seems to me to be important to now split BZ_MAX_SELECTORS into these two
parts so as to make it clear to everybody that we're accepting (decompressing)
a slightly larger set of inputs than we create (a la that old saying about
network protocol implementations), so as to tolerate other compressors.

That then leaves the questions:

* Why did it work before?  I suspect Federico's guess that "I think the len
   arrays are still uninitialized and will get filled until later" is correct,
   but I'd need to look more at that.

* How to verify any change?  For whatever fix we arrive at, I'd like to do
   some test runs over big trees of files (several tens of GB) with both
   compressor and decompressor compiled with asan (and/or ubsan), since I
   believe at least asan can detect overruns of the statically sized arrays
   within the EState and DState structs -- V can't.

   Per communication with Federico (which didn't go to Mark, unfortunately), I
   have a C driver program that compresses and decompresses every file in a
   tree and checks it is the same as the original.  But I don't know what the
   copyright status of it is and so I'm not happy to redistribute it (alas).
   We should try to replace it.

   In particular, the three test files in the tarball merely serve to verify
   that the build didn't fail in some obvious way.  They are in no way a
   comprehensive test set.

J

  reply	other threads:[~2019-06-28  6:08 UTC|newest]

Thread overview: 16+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-01-01  0:00 Mark Wielaard
2019-01-01  0:00 ` Mark Wielaard
2019-01-01  0:00   ` Federico Mena Quintero
2019-01-01  0:00   ` Mark Wielaard
2019-01-01  0:00     ` Federico Mena Quintero
2019-01-01  0:00       ` Julian Seward [this message]
2019-01-01  0:00         ` Mark Wielaard
2019-01-01  0:00           ` Alternative nSelectors patch (Was: bzip2 1.0.7 released) Mark Wielaard
2019-01-01  0:00             ` Julian Seward
2019-01-01  0:00               ` Mark Wielaard
2019-01-01  0:00                 ` Mark Wielaard
2019-01-01  0:00           ` bzip2 test suite " Mark Wielaard
2019-01-01  0:00           ` bzip2 1.0.7 released Mark Wielaard
2019-01-01  0:00             ` Federico Mena Quintero
2019-01-01  0:00               ` Mark Wielaard
2019-01-01  0:00   ` Jeffrey Walton

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=e73799c0-cb3b-c9f8-84c8-53d028dbe1d5@acm.org \
    --to=jseward@acm.org \
    --cc=bzip2-devel@sourceware.org \
    --cc=federico@gnome.org \
    --cc=mark@klomp.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).