Bug 23011 - Infinite loop in handle_sysv_hash (src/readelf.c)
Summary: Infinite loop in handle_sysv_hash (src/readelf.c)
Alias: None
Product: elfutils
Classification: Unclassified
Component: tools (show other bugs)
Version: unspecified
: P2 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
Depends on:
Reported: 2018-03-28 15:10 UTC by trace probe
Modified: 2018-03-31 12:20 UTC (History)
3 users (show)

See Also:
Last reconfirmed: 2018-03-28 00:00:00

poc for readelf (59 bytes, application/octet-stream)
2018-03-28 15:10 UTC, trace probe

Note You need to log in before you can comment on or make changes to this bug.
Description trace probe 2018-03-28 15:10:11 UTC
Created attachment 10920 [details]
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;
   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
Comment 1 Mark Wielaard 2018-03-28 19:25:16 UTC
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.
Comment 2 Mark Wielaard 2018-03-28 19:32:53 UTC
Proposed fix: https://sourceware.org/ml/elfutils-devel/2018-q1/msg00118.html
Comment 3 Mark Wielaard 2018-03-30 20:44:14 UTC
(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.
    Signed-off-by: Mark Wielaard <mark@klomp.org>

Pushed to master.