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