[Bug tools/23011] New: Infinite loop in handle_sysv_hash (src/readelf.c)

[Bug tools/23011] New: Infinite loop in handle_sysv_hash (src/readelf.c)

[traceprobe at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=23011

            Bug ID: 23011
           Summary: Infinite loop in handle_sysv_hash (src/readelf.c)
           Product: elfutils
           Version: unspecified
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tools
          Assignee: unassigned at sourceware dot org
          Reporter: traceprobe at gmail dot com
                CC: elfutils-devel at sourceware dot org
  Target Milestone: ---

Created attachment 10920
  --> https://sourceware.org/bugzilla/attachment.cgi?id=10920&action=edit
poc for readelf

In elfutils version 0.170 and commit afffdff29228db03e2131af577f58a22aec6c1fe,
there is an infinite loop in handle_sysv_hash function of src/readelf.c, which
can be triggered by the POC below.

The issue happens since when processing System V-style hash table, the loop
value could be manipulated by input file. For instance in line 3150, if
chain[1] = 1, the program falls in infinite loop.

   3108 static void
   3109 handle_sysv_hash (Ebl *ebl, Elf_Scn *scn, GElf_Shdr *shdr, size_t
shstrndx)
   3110 {
   ...
   3141   for (Elf32_Word cnt = 0; cnt < nbucket; ++cnt)
   3142     {
   3143       Elf32_Word inner = bucket[cnt];
   3144       while (inner > 0 && inner < nchain)
   3145         {
   3146           ++nsyms;
   3147           if (maxlength < ++lengths[cnt])
   3148             ++maxlength;
   3149 
   3150           inner = chain[inner];
   3151         }
   3152     }

To reproduce the issue, run: ./eu-readelf -a $POC

The full stack trace is:

0x000000000040d78f in handle_sysv_hash (ebl=0x639670, scn=0x639238,
shdr=0x7fffffffdae0, shstrndx=256)
    at /home/test/test/./elfutils/master/src/src/readelf.c:3144
3144          while (inner > 0 && inner < nchain)
(gdb) bt
#0  0x000000000040d78f in handle_sysv_hash (ebl=0x639670, scn=0x639238,
shdr=0x7fffffffdae0, shstrndx=256)
    at /home/test/test/./elfutils/master/src/src/readelf.c:3144
#1  0x000000000040e24c in handle_hash (ebl=0x639670) at
/home/test/test/./elfutils/master/src/src/readelf.c:3360
#2  0x000000000040615d in process_elf_file (dwflmod=0x639340, fd=3) at
/home/test/test/./elfutils/master/src/src/readelf.c:915
#3  0x0000000000405747 in process_dwflmod (dwflmod=0x639340, userdata=0x639350,
name=0x6394e0 "poc/id:000000,src:000294,op:flip1,pos:51.", base=0,
arg=0x7fffffffdd50)
    at /home/test/test/./elfutils/master/src/src/readelf.c:707
#4  0x00007ffff7ba4c96 in dwfl_getmodules (dwfl=0x639000, callback=0x4056a9
<process_dwflmod>, arg=0x7fffffffdd50, offset=0)
    at /home/test/test/./elfutils/master/src/libdwfl/dwfl_getmodules.c:86
#5  0x0000000000405c2d in process_file (fd=3, fname=0x7fffffffe2b9
"poc/id:000000,src:000294,op:flip1,pos:51.", only_one=true)
    at /home/test/test/./elfutils/master/src/src/readelf.c:806
#6  0x000000000040461e in main (argc=3, argv=0x7fffffffdf88) at
/home/test/test/./elfutils/master/src/src/readelf.c:322

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug tools/23011] Infinite loop in handle_sysv_hash (src/readelf.c)

[mark at klomp dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=23011

Mark Wielaard <mark at klomp dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mark at klomp dot org

--- Comment #1 from Mark Wielaard <mark at klomp dot org> ---
ewww nasty. The idea is that the bucket entries point to the (first) symbol for
a particular hash. If that symbol is not the one needed then you look whether
there are other symbols with the same hash value in the chain. There are as
many chain entries as symbols, and for each symbol n, chain[n] is either zero
if there are no other symbols with the same hash, or it is the value of the
next symbol with the same hash (for the last one the chain entry is zero).
There are obviously not supposed to be "loops" in the chain. The easiest to
check would be the limit the number of chains to follow to the number of
symbols, which is equal the total number of chain entries (nchain).

Note that the same could happen in handle_sysv_hash64 which uses the same kind
of  bucket chain loop.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug tools/23011] Infinite loop in handle_sysv_hash (src/readelf.c)

[mark at klomp dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=23011

Mark Wielaard <mark at klomp dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2018-03-28
     Ever confirmed|0                           |1

--- Comment #2 from Mark Wielaard <mark at klomp dot org> ---
Proposed fix: https://sourceware.org/ml/elfutils-devel/2018-q1/msg00118.html

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug tools/23011] Infinite loop in handle_sysv_hash (src/readelf.c)

[mark at klomp dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=23011

Mark Wielaard <mark at klomp dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #3 from Mark Wielaard <mark at klomp dot org> ---
(In reply to Mark Wielaard from comment #2)
> Proposed fix: https://sourceware.org/ml/elfutils-devel/2018-q1/msg00118.html

commit 560145d2b49347e92f4a265c3c3dbcae164ed9df
Author: Mark Wielaard <mark@klomp.org>
Date:   Wed Mar 28 21:27:48 2018 +0200

    readelf: Break sysv[64] symbol hash bucket chain loops.

    The bucket chain should not contain loops. If it does we should mark the
    hash bucket chain as invalid. This is easily checked by noticing when we
    have seen more than the number of chain elements. Which equals the max
    number as symbols in the table.

    https://sourceware.org/bugzilla/show_bug.cgi?id=23011

    Signed-off-by: Mark Wielaard <mark@klomp.org>

Pushed to master.

-- 
You are receiving this mail because:
You are on the CC list for the bug.