Bug 21994

Summary: Hang in process_version_sections with ent.vd_next = 0 and aux.vda_next = 0
Product: binutils Reporter: Mạnh <Imdb95>
Component: binutilsAssignee: Alan Modra <amodra>
Status: RESOLVED FIXED    
Severity: normal CC: amodra
Priority: P2    
Version: 2.29   
Target Milestone: ---   
Host: Target:
Build: Last reconfirmed: 2017-08-25 00:00:00
Attachments: Crafted elf file used to trigger the bug

Description Mạnh 2017-08-23 14:47:00 UTC 
Created attachment 10360 [details]
Crafted elf file used to trigger the bug

Hello,
I found this bug when fuzzing readelf with afl-fuzz.
==========Reproduce==========
Trigger the bug:
manh@manh-VirtualBox:~/Fuzzing/afl/binutils$ ./build-binutils-2.29-ggdb/bin/readelf -a readelf_hang.elf 
==========Actual Result==========
The program readelf hangs for a very long time, printing repeated outputs.
manh@manh-VirtualBox:~/Fuzzing/afl/binutils$ ./build-binutils-2.29-ggdb/bin/readelf -a readelf_hang_slave_id00.elf 
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 04 00 00 00 00 00 00 00 00 
  Class:                             ELF64
......................
  0x0070: Parent 19320, name index: 0
  0x0070: Parent 19321, name index: 0
  0x0070: Parent 19322, name index: 0
  0x0070: Parent 19323, name index: 0
  0x0070: Parent 19324, name index: 0
  0x0070: Parent 19325, name index: 0
  0x0070: Parent 19326, name index: 0
  0x0070: Parent 19327, name index: 0
  0x0070: Parent 19328, name index: 0
......................
==========Build Date & Hardware==========
Version: binutils 2.29 (https://ftp.gnu.org/gnu/binutils/binutils-2.29.tar.gz)
Compilation on Ubuntu 16.04:
manh@manh-VirtualBox:~/Fuzzing/afl/binutils/binutils-2.29$ uname -a
Linux manh-VirtualBox 4.4.0-91-generic #114-Ubuntu SMP Tue Aug 8 11:56:56 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
manh@manh-VirtualBox:~/Fuzzing/afl/binutils/binutils-2.29$ sudo ./configure --prefix=`pwd`/../build-binutils-2.29-ggdb CC="gcc" CXX="g++" CFLAGS="-ldl -Wno-error -ggdb -O0" CXXFLAGS="-ldl -Wno-error -ggdb -O0" && sudo make && sudo make install
==========Additional Information==========
Detailed analysis of the bug:
Within the loop starting at readelf.c:10236, if aux.vda_next = 0, the loop iterates (ent.vd_cnt-1) times. And within the outter loop (starting at readelf.c:10183), ent.vn_next can be zero, so idx never increases (idx += ent.vd_next), and the loop iterates cnt times. So the complexity of the two nested loops if O(cnt*ent.vd_cnt), which makes the program hangs.
==========Suggestion for Patching==========
Just check if aux.vda_next = 0 and if ent.vn_next = 0.
Cheers,
  Manh
Comment 1 Sourceware Commits 2017-08-25 06:35:15 UTC 
The master branch has been updated by Alan Modra <amodra@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=1445030f313d9b251a6a27c8bdf52197520396e2

commit 1445030f313d9b251a6a27c8bdf52197520396e2
Author: Alan Modra <amodra@gmail.com>
Date:   Fri Aug 25 11:41:06 2017 +0930

    PR21994, readelf looping on verdefs
    
    	PR 21994
    	* readelf.c (process_version_sections <SHT_GNU_verdef>): Check
    	vd_aux and vda_next for sanity.  Delete "end".  Correct overflow
    	checks.
    	(process_version_sections <SHT_GNU_verneed>): Correct overflow
    	check.  Don't report invalid vna_next on overflow.  Do report
    	invalid vna_next on size less than aux info.
Comment 2 Alan Modra 2017-08-25 12:05:02 UTC 
Fixed
Comment 3 Sourceware Commits 2017-09-05 14:33:26 UTC 
The binutils-2_29-branch branch has been updated by Nick Clifton <nickc@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=64aa1246572306b72dc479b46d13ff749b0c3236

commit 64aa1246572306b72dc479b46d13ff749b0c3236
Author: Nick Clifton <nickc@redhat.com>
Date:   Tue Sep 5 15:32:04 2017 +0100

    Import patches from mainline to fix minor binutils bugs:
    
    	PR 21861
    	* winduni.c (codepages): Use cp1252 for codepage 0.
    
    	PR 21813
    	* rddbg.c (read_symbol_stabs_debugging_info): Check for an empty
    	string whilst concatenating symbol names.
    
    	PR 21909
    	* prdbg.c (pr_int_type): Increase size of local string buffer.
    	(pr_float_type): Likewise.
    	(pr_bool_type): Likewise.
    
    	PR 21820
    	* readelf.c (dump_section_as_strings): Do not fail if the section
    	was empty.
    	(dump_section_as_bytes): Likewise.
    
    	PR 21990
    	* readelf.c (process_version_sections <SHT_GNU_verneed>): Check
    	for invalid vn_next field before adding to idx.  Use unsigned
    	long for index vars.  Move index checks.
    	<SHT_GNU_verdef>: Likewise for vd_next.
    
    	PR 21994
    	* readelf.c (process_version_sections <SHT_GNU_verdef>): Check
    	vd_aux and vda_next for sanity.  Delete "end".  Correct overflow
    	checks.
    	(process_version_sections <SHT_GNU_verneed>): Correct overflow
    	check.  Don't report invalid vna_next on overflow.  Do report
    	invalid vna_next on size less than aux info.