|
From: Mark A. <ma...@al...> - 2005-05-30 19:23:46
|
On May 30, 2005, at 12:26 AM, Julian Seward wrote:
> Mark, could you explain how the use of uninitialised values from memory
> is made safe here? I'm looking at this
>
> do {
> } while (*++scan == *++match && *++scan == *++match &&
> *++scan == *++match && *++scan == *++match &&
> *++scan == *++match && *++scan == *++match &&
> *++scan == *++match && *++scan == *++match &&
> scan < strend);
>
> and it's not clear how scan can be moved forward some indeterminate
> amount based on garbage in memory and yet the deflate result is
> well-defined.
The output of the loop is where the first mismatch is (scan). If
uninitialized data is accessed in the process, then all of the
initialized data matched, and maybe some of the uninitialized data as
well. Later the length of the match is truncated to the length of the
initialized data, so it doesn't matter how far into the uninitialized
data the loop progressed.
This line limits nice_match to be no longer than the uninitialized data:
if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
This line exits the longest match search loop if a match that long is
found (or longer if some uninitialized data matched):
if (len >= nice_match) break;
And these lines return a match length limited to the length of the
initialized data:
if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
return s->lookahead;
> An ideal outcome is that Mark explains how this behaviour
> is safe in zlib. I can then look at Memcheck's instrumentation
> phase to determine if/how it is possible to avoid these
> reports.
valgrind would have to be pretty smart to figure out what s->lookahead
means, trace the values of nice_match, len, and best_len, and figure
out from all that that the uninitialized data didn't affect the return
value. The only semi-reasonable automatic process I could imagine
would be for valgrind to set the first unintialized byte to all 256
values, run the code each time, and see that the returned value is not
affected (as well as all the side effects of the routine on the state
structure). Then if another uninitialized byte is accessed, which it
will be for one of the previous uninitialized byte values, do that all
over again, and so on. Good luck.
mark
|