bunzip2 failure

Denys Vlasenko vda.linux at googlemail.com
Sat Jun 28 18:18:22 UTC 2008


On Saturday 28 June 2008 08:10, Rob Landley wrote:
> > I see. Someone (you or Manuel) optimized variable bitfield reading
> > by reading ahead and changing limit[] format a bit. It's there where bug
> > was hiding. Sometimes limit was ending up being 0xffffffff. Which is ok
> > if you look at it as an unsigned, but it was signed.
> 
> A) limit is a pointer to an array.  I suspect you mean one of the entries in 
> limit was winding up 0xffffffff?

Yes.

> B) That should never happen, I want to know why.
> 
> > Did you receive my mail with a fix? The patch explains that in more
> > details. --
> 
> My response to "that shouldn't happen" was based on your patch, but now I'm 
> tracing through the program to see what it's actually getting and doing with 
> the data...
> 
> (This isn't the first way I've found to drive bunzip nuts by the way.  A 

Yep. I am amazed how small decompress_unlzma.c in comparison is.

> previous way applied to the original bunzip2, they fixed it in 1.0.3 I think.  
> There was also an integer overflow found by the gentoo security guys.  But 
> I'd like to know _why_ the data's off the deep end.)
> 
> Ha!  Found the bug.  The fix you sent just masks the symptom.
> 
> The failure happens in huffman coding group #4 of your test file.  Basically 
> huffman coding hit a pathological case and is not helping at all here; every 
> huffman coded symbol takes exactly 8 bits to encode.  Might as well not do 
> huffman coding at all then.  It's a crazily balanced fluke huffman tree, 
> which is why we didn't see it before, but that's not the bug.
> 
> The bug occurs in the following loop:
> 
>         // Count symbols coded for at each bit length
>         for (ii = 0; ii < symCount; ii++) temp[length[ii]]++;
> 
> symCount is 256, and length[ii] for each entry from 0 through 255 is always 8.  
> This means that temp[8] gets incremented 256 times.  And the problem is that 
> temp[] is an array of unsigned char, and temp[8] wraps back to 0.
> 
> Later on, limit[maxLen] = pp+temp[maxLen]-1; looks like it should set limit[8] 
> to 255, and instead it sets it to -1.  Which is where you saw the bug.

Yes.

> The correct fix is to bump temp[] up to at least a short.  Yeah, it'll eat a 
> bit more stack, but MAX_HUFCODE_BITS is only 20.  Bumping it all the way to 
> an unsigned int would make arm systems noticeably less uncomfortable, they 
> hate doing math with smaller than int values, the compiler has to output mask 
> and shift code to do it, bloats the binary and slows stuff down a lot.  (It's 
> an int in my current struct group_data in toybox anyway, no idea what the 
> busybox version is using.)

Just "unsigned" is ok, yes.

> Here's a whitespace damaged cut and paste of a patch that fixed it for toybox:
> 
> diff -r 93223118c813 lib/bunzip.c
> --- a/lib/bunzip.c      Thu Jun 26 22:48:43 2008 -0500
> +++ b/lib/bunzip.c      Sat Jun 28 01:03:06 2008 -0500
> @@ -204,7 +204,8 @@
>         // literal symbols, plus two run symbols (RUNA, RUNB)
>         symCount = bd->symTotal+2;
>         for (jj=0; jj<bd->groupCount; jj++) {
> -               unsigned char length[MAX_SYMBOLS], temp[MAX_HUFCODE_BITS+1];
> +               unsigned char length[MAX_SYMBOLS];
> +               unsigned temp[MAX_HUFCODE_BITS+1];
>                 int minLen, maxLen, pp;
> 

Thanks for excellent analysis! I applied this fix to busybox svn
and 1.11.0 patches.

BTW, is Firmware Linux capable of producing a bootable system for blackfin?
If not, do you want me to try fixing that?
--
vda



More information about the busybox mailing list