Re: [Xen-devel] [PATCH 16/22] libelf: check loops for running away

[Ian Jackson <Ian.Jackson@xxxxxxxxxxxxx>]

Andrew Cooper writes ("Re: [PATCH 16/22] libelf: check loops for running away"):
> On 07/06/13 19:27, Ian Jackson wrote:
> > @@ -233,6 +234,12 @@ static unsigned elf_xen_parse_notes(struct elf_binary 
> > *elf,
> >            ELF_HANDLE_PTRVAL(note) < parms->elf_note_end;
> >            note = elf_note_next(elf, note) )
> >      {
> > +        if ( *total_note_count >= ELF_MAX_TOTAL_NOTE_COUNT )
> > +        {
> > +            elf_mark_broken(elf, "too many ELF notes");
> > +            break;
> > +        }
> > +        (*total_note_count)++;
> >          note_name = elf_note_name(elf, note);
> >          if ( note_name == NULL )
> >              continue;
> 
> elf_note_name() will currently actually return note->desc if namesz is 0
> or overflows.

Why is this a security problem ?  The security principle in this code
is that a malformed ELF may cause these pseudopointers, counts, etc.,
to have arbitrary values; we avert the bad consequences at the time of
dereference or loop iteration.

> Confusingly, the reference I am using
> (http://www.skyfree.org/linux/references/ELF_Format.pdf) indicates that
> namesz = 0 and name[0]='\0' is reserved for system use, yet in
> contradition to the statement that padding is only required if
> necessary.  The arguably more-real libelf from elf-utils appears to
> ignore the edge case listed above.

I'm not sure what your point is.  Do you think I am introducing a
regression ?  I intend that my code has the same behaviour as before,
for ELFs not involving out of range accesses.

> Unfortunately, it appears that very little in this loop is resilient to
> stupidly-large namesz or descsz. the note_name == NULL check looks to do
> the wrong thing if there "note" points to a malformed note.

If note points to a malformed note then either elf_note_name returns
some "const char*" pointer which is safe to pass to strcmp (although
perhaps not the string the ELF image author intended), or NULL.  In
both of these cases I think the subsequent code does nothing wrong.

The possibility of out-of-control loop iteration is averted by
checking for "*total_note_count >= ELF_MAX_TOTAL_NOTE_COUNT".

> > @@ -149,6 +158,9 @@ ELF_HANDLE_DECL(elf_shdr) elf_shdr_by_name(struct 
> > elf_binary *elf, const char *n
> >      for ( i = 0; i < count; i++ )
> >      {
> >          shdr = elf_shdr_by_index(elf, i);
> > +        if ( !elf_access_ok(elf, ELF_HANDLE_PTRVAL(shdr), 1) )
> > +            /* input has an insane section header count field */
> > +            break;
> 
> It occurs to me here that elf_access_ok appears to checks the range
> [&shdr, &shdr+1] (&shdr relative to start of elf).

Yes.

> Should this not be be elf_access_ok(elf, ELF_HANDLE_PTRVAL(shdr), sizeof
> *shdr) ?

No, it doesn't matter.  The purpose is simply to terminate the loop
early if we start to walk off the end of the input image.  Otherwise
a bad ELF might cause this loop to carry on for 2^32 iterations, as
all the wild psuedopointer dereference attempts would simply be
disregarded (and for reads, give 0).

> > @@ -327,7 +344,14 @@ ELF_HANDLE_DECL(elf_note) elf_note_next(struct 
> > elf_binary *elf, ELF_HANDLE_DECL(
> >      unsigned namesz = (elf_uval(elf, note, namesz) + 3) & ~3;
> >      unsigned descsz = (elf_uval(elf, note, descsz) + 3) & ~3;
> >
> > -    return ELF_MAKE_HANDLE(elf_note, ELF_HANDLE_PTRVAL(note) + 
> > elf_size(elf, note) + namesz + descsz);
> > +    elf_ptrval ptrval = ELF_HANDLE_PTRVAL(note)
> > +        + elf_size(elf, note) + namesz + descsz;
> > +
> > +    if ( ( ptrval <= ELF_HANDLE_PTRVAL(note) || /* wrapped or stuck */
> > +           !elf_access_ok(elf, ELF_HANDLE_PTRVAL(note), 1) ) )
> > +        ptrval = ELF_MAX_PTRVAL; /* terminate caller's loop */
> > +
> > +    return ELF_MAKE_HANDLE(elf_note, ptrval);
> 
> The ptrval check is still suscpetable to a double overflow from
> slightly-larger-than-half-UINT_MAX namesz and descsz.  Also, the
> rounding up at the top is susceptible to overflow.

All these overflows are perfectly fine.  We don't care whether the
values are sane or not.

The purpose of the check is to ensure that callers which use
elf_note_next in a loop terminate within a reasonable time.  The
callers all
  * in the loop increment clause, use elf_note_next to replace
    their previous pointer with a new one
  * in the loop termination clause, compare the pointer with the
    end of the notes section, and loop only if it is strictly less.

The checks are indeed sufficient to ensure that the loop is making
forward progress.  There are the following cases:

 (i) ptrval > ELF_HANDLE_PTRVAL && elf_access_ok().  I.e. the new
    ptrval is strictly greater than the previous value, and the
    previous value was within the image.  This can only happen a
    finite number of times, at most N+1 where N is the size of the
    input image plus the output image plus the xdest area (all
    measured in bytes), because each time we succeed with this test we
    "use up" at least one possible psuedopointer value pointing to an
    accessible byte.

 (ii) Otherwise.  In this case we return ELF_MAX_PTRVAL.
    ELF_MAX_PTRVAL is not strictly less than any possible
    pseudopointer value so the caller's loop will terminate.

> > +#define ELF_MAX_STRING_LENGTH 4096
> > +#define ELF_MAX_TOTAL_NOTE_COUNT 65536
> > +
> 
> With a view to stupidly-long elf notes, should probably have
> ELF_MAX_NOTE_{NAME,DESC}_LENGTH here.

Why ?

Ian.

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel