[llvm-readobj] - Do not crash when SHT_HASH table is broken.

[grimar]

Summary

We have scenarios when the logic of --elf-hash-histogram/--hash-symbols/--hash-table
options might crash when given a broken hash table.

This patch adds pre-checks for tables for these 3 options
and provides test cases.

[MaskRay]

Thanks!

llvm/test/tools/llvm-readobj/ELF/hash-histogram.test

116

starts with

llvm/tools/llvm-readobj/ELFDumper.cpp

2619

starts with

I think "Hence the length of a hash table can't be less than 8 bytes." is naturally inferred from the first sentence.

[jhenderson]

llvm/test/tools/llvm-readobj/ELF/hash-histogram.test

116

(Also applies in the other tests)

117

points to data (also applies in other tests)

122

I'd spell out "EOF" in error messages (i.e. "goes past the end of the file"). Same goes below.

152

end of the file

llvm/test/tools/llvm-readobj/ELF/hash-symbols.test

387

end of the file

408

This line probably wants splitting.

llvm/test/tools/llvm-readobj/ELF/hash-table.test

163

All these lines probably want splitting.

[grimar]

• Addressed review comments.

llvm/test/tools/llvm-readobj/ELF/hash-histogram.test

122

Ok. My motivation was to make error messages shorter, but I have no preference and I've expected to get a comment like this too :)

[jhenderson]

LGTM.

llvm/test/tools/llvm-readobj/ELF/hash-histogram.test

## which is the start of PT_LOAD, i.e. the file offset of .hash.
         Value: 0
 DynamicSymbols:
   - Name: foo
 ProgramHeaders:
   - Type:  PT_LOAD
     Sections:
       - Section: .hash
       - Section: .dynamic
+
+## Each SHT_HASH section starts from two 32-bit fields: nbucket and nchain.
+## Check we report an error when a DT_HASH value points to a data that has size less than 8 bytes.
+
+# RUN: yaml2obj --docnum=3 %s -o %t3.o
+# RUN: llvm-readelf --elf-hash-histogram %t3.o 2>&1 | FileCheck %s --check-prefix=ERR1 -DFILE=%t3.o
+
+# ERR1: warning: '[[FILE]]': the hash table at offset 0x2b1 goes past the EOF (0x2b8){{$}}
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS64
+  Data:    ELFDATA2LSB
+  Type:    ET_DYN
+  Machine: EM_X86_64
+Sections:
+  - Name:   .hash
+    Type:   SHT_HASH
+    Flags:  [ SHF_ALLOC ]
+    Bucket: [ 0 ]
+    Chain:  [ 0 ]
+  - Name:  .dynamic
+    Type:  SHT_DYNAMIC
+    Flags: [ SHF_WRITE, SHF_ALLOC ]
+    Entries:
+      - Tag:   DT_HASH
+        Value: 0x239
+      - Tag:   DT_NULL
+        Value: 0x0
+DynamicSymbols: []
+ProgramHeaders:
+  - Type:     PT_LOAD
+    FileSize: 0x23a
+    Sections:
+      - Section: .hash
+      - Section: .dynamic
+
+## Check we report a warning when the hash table goes past the end of file.
+
+## Case A.1: the hash table ends right before the EOF. We have a broken nbucket
+##           field that has a value larger than the number of buckets.
+# RUN: yaml2obj --docnum=4 %s -o %t4.1.o -DNBUCKET=0x5d -DNCHAIN=0x1
+# RUN: llvm-readelf --elf-hash-histogram %t4.1.o 2>&1 | FileCheck %s --implicit-check-not={{.}} --allow-empty
+
+## Case A.2: the hash table ends 1 byte past the EOF. We have a broken nbucket
+##           field that has a value larger than the number of buckets.
+# RUN: yaml2obj --docnum=4 %s -o %t4.2.o -DNBUCKET=0x5e -DNCHAIN=0x1
+# RUN: llvm-readelf --elf-hash-histogram %t4.2.o 2>&1 | FileCheck %s --check-prefix=ERR2 -DFILE=%t4.2.o --implicit-check-not="warning:"
+# ERR2: warning: '[[FILE]]': the hash table at offset 0x54 goes past the EOF (0x1d4), nbucket = 94, nchain = 1{{$}}
+
+## Case B.1: the hash table ends right before the EOF. We have a broken nchain
+##           field that has a value larger than the number of chains.
+# RUN: yaml2obj --docnum=4 %s -o %t4.3.o -DNBUCKET=0x1 -DNCHAIN=0x5d
+# RUN: llvm-readelf --elf-hash-histogram %t4.3.o 2>&1 | FileCheck %s --check-prefix=ERR3 -DFILE=%t4.3.o --implicit-check-not="warning:"
+# ERR3: warning: '[[FILE]]': hash table nchain (93) differs from symbol count derived from SHT_DYNSYM section header (1){{$}}
+
+## Case B.2: the hash table ends 1 byte past the EOF. We have a broken nchain
+##           field that has a value larger than the number of chains.
+# RUN: yaml2obj --docnum=4 %s -o %t4.4.o -DNBUCKET=0x1 -DNCHAIN=0x5e
+# RUN: llvm-readelf --elf-hash-histogram %t4.4.o 2>&1 | FileCheck %s --check-prefix=ERR4 -DFILE=%t4.4.o --implicit-check-not="warning:"
+# ERR4: warning: '[[FILE]]': hash table nchain (94) differs from symbol count derived from SHT_DYNSYM section header (1){{$}}
+# ERR4: warning: '[[FILE]]': the hash table at offset 0x54 goes past the EOF (0x1d4), nbucket = 1, nchain = 94{{$}}
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS32
+  Data:    ELFDATA2LSB
+  Type:    ET_DYN
+  Machine: EM_X86_64
+Sections:
+  - Name:    .hash
+    Type:    SHT_HASH
+    Flags:   [ SHF_ALLOC ]
+    Bucket:  [ 0 ]
+    NBucket: [[NBUCKET]]
+    Chain:   [ 0 ]
+    NChain:  [[NCHAIN]]
+  - Name:  .dynamic
+    Type:  SHT_DYNAMIC
+    Flags: [ SHF_WRITE, SHF_ALLOC ]
+    Entries:
+      - Tag:   DT_HASH
+        Value: 0x0
+      - Tag:   DT_NULL
+        Value: 0x0
+DynamicSymbols: []
+ProgramHeaders:
+  - Type: PT_LOAD
+    Sections:
+      - Section: .hash
+      - Section: .dynamic

llvm/test/tools/llvm-readobj/ELF/hash-symbols.test

 DynamicSymbols:
   - Name:    aaa
   - Name:    bbb
 ProgramHeaders:
   - Type:  PT_LOAD
     Sections:
       - Section: .hash
       - Section: .dynamic
+
+## Each SHT_HASH section starts from two 32-bit fields: nbucket and nchain.
+## Check we report an error when a DT_HASH value points to a data that has size less than 8 bytes.
+
+# RUN: yaml2obj --docnum=6 %s -o %t6.o
+# RUN: llvm-readelf --hash-symbols %t6.o 2>&1 | FileCheck %s --check-prefix=ERR1 -DFILE=%t6.o
+
+# ERR1: warning: '[[FILE]]': the hash table at offset 0x2b1 goes past the EOF (0x2b8){{$}}
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS64
+  Data:    ELFDATA2LSB
+  Type:    ET_DYN
+  Machine: EM_X86_64
+Sections:
+  - Name:   .hash
+    Type:   SHT_HASH
+    Flags:  [ SHF_ALLOC ]
+    Bucket: [ 0 ]
+    Chain:  [ 0 ]
+  - Name:  .dynamic
+    Type:  SHT_DYNAMIC
+    Flags: [ SHF_WRITE, SHF_ALLOC ]
+    Entries:
+      - Tag:   DT_HASH
+        Value: 0x239
+      - Tag:   DT_NULL
+        Value: 0x0
+DynamicSymbols: []
+ProgramHeaders:
+  - Type:     PT_LOAD
+    FileSize: 0x23a
+    Sections:
+      - Section: .hash
+      - Section: .dynamic
+
+## Check we report a warning when the hash table goes past the end of file.
+
+## Case A.1: the hash table ends right before the EOF. We have a broken nbucket
+##           field that has a value larger than the number of buckets.
+# RUN: yaml2obj --docnum=7 %s -o %t7.1.o -DNBUCKET=0x5d -DNCHAIN=0x1
+# RUN: llvm-readelf --hash-symbols %t7.1.o 2>&1 | FileCheck %s --check-prefix=NOERR1
+# NOERR1:            Symbol table of .hash for image:
+# NOERR1-NEXT:         Num Buc:    Value  Size   Type   Bind Vis      Ndx Name
+# NOERR1-NEXT-EMPTY:
+
+## Case A.2: the hash table ends 1 byte past the EOF. We have a broken nbucket
+##           field that has a value larger than the number of buckets.
+# RUN: yaml2obj --docnum=7 %s -o %t7.2.o -DNBUCKET=0x5e -DNCHAIN=0x1
+# RUN: llvm-readelf --hash-symbols %t7.2.o 2>&1 | FileCheck %s --check-prefix=ERR2 -DFILE=%t7.2.o
+# ERR2:      Symbol table of .hash for image:
+# ERR2-NEXT: warning: '[[FILE]]': the hash table at offset 0x54 goes past the EOF (0x1d4), nbucket = 94, nchain = 1{{$}}
+# ERR2-NOT:  {{.}}
+
+## Case B.1: the hash table ends right before the EOF. We have a broken nchain
+##           field that has a value larger than the number of chains.
+# RUN: yaml2obj --docnum=7 %s -o %t7.3.o -DNBUCKET=0x1 -DNCHAIN=0x5d
+# RUN: llvm-readelf --hash-symbols %t7.3.o 2>&1 | FileCheck %s --implicit-check-not="warning:" --check-prefix=NOERR2 -DFILE=%t7.3.o
+# NOERR2:      warning: '[[FILE]]': hash table nchain (93) differs from symbol count derived from SHT_DYNSYM section header (1)
+# NOERR2:      Symbol table of .hash for image:
+# NOERR2-NEXT: Num Buc: Value Size Type Bind Vis Ndx Name
+# NOERR2-NOT:  {{.}}
+
+## Case B.2: the hash table ends 1 byte past the EOF. We have a broken nchain
+##           field that has a value larger than the number of chains.
+# RUN: yaml2obj --docnum=7 %s -o %t7.4.o -DNBUCKET=0x1 -DNCHAIN=0x5e
+# RUN: llvm-readelf --hash-symbols %t7.4.o 2>&1 | FileCheck %s --check-prefix=ERR3 -DFILE=%t7.4.o
+# ERR3:      Symbol table of .hash for image:
+# ERR3-NEXT: warning: '[[FILE]]': the hash table at offset 0x54 goes past the EOF (0x1d4), nbucket = 1, nchain = 94{{$}}
+# ERR3-NOT:  {{.}}
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS32
+  Data:    ELFDATA2LSB
+  Type:    ET_DYN
+  Machine: EM_X86_64
+Sections:
+  - Name:    .hash
+    Type:    SHT_HASH
+    Flags:   [ SHF_ALLOC ]
+    Bucket:  [ 0 ]
+    NBucket: [[NBUCKET]]
+    Chain:   [ 0 ]
+    NChain:  [[NCHAIN]]
+  - Name:  .dynamic
+    Type:  SHT_DYNAMIC
+    Flags: [ SHF_WRITE, SHF_ALLOC ]
+    Entries:
+      - Tag:   DT_HASH
+        Value: 0x0
+      - Tag:   DT_NULL
+        Value: 0x0
+DynamicSymbols: []
+ProgramHeaders:
+  - Type: PT_LOAD
+    Sections:
+      - Section: .hash
+      - Section: .dynamic

llvm/test/tools/llvm-readobj/ELF/hash-table.test

ProgramHeaders:
   - Type: PT_LOAD
     Sections:
       - Section: .hash
       - Section: .dynamic
   - Type: PT_DYNAMIC
     VAddr: 0x1010
     Sections:
       - Section: .dynamic
+
+## Each SHT_HASH section starts from two 32-bit fields: nbucket and nchain.
+## Check we report an error when a DT_HASH value points to a data that has size less than 8 bytes.
+
+# RUN: yaml2obj --docnum=4 %s -o %t4.o
+# RUN: llvm-readelf --hash-table %t4.o 2>&1 | FileCheck %s --check-prefix=ERR1 -DFILE=%t4.o
+# RUN: llvm-readobj --hash-table %t4.o 2>&1 | FileCheck %s --check-prefix=ERR1 -DFILE=%t4.o
+
+# ERR1:      HashTable {
+# ERR1-NEXT:  warning: '[[FILE]]': the hash table at offset 0x2b1 goes past the EOF (0x2b8){{$}}
+# ERR1-NEXT: }
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS64
+  Data:    ELFDATA2LSB
+  Type:    ET_DYN
+  Machine: EM_X86_64
+Sections:
+  - Name:   .hash
+    Type:   SHT_HASH
+    Flags:  [ SHF_ALLOC ]
+    Bucket: [ 0 ]
+    Chain:  [ 0 ]
+  - Name:  .dynamic
+    Type:  SHT_DYNAMIC
+    Flags: [ SHF_WRITE, SHF_ALLOC ]
+    Entries:
+      - Tag:   DT_HASH
+        Value: 0x239
+      - Tag:   DT_NULL
+        Value: 0x0
+DynamicSymbols: []
+ProgramHeaders:
+  - Type:     PT_LOAD
+    FileSize: 0x23a
+    Sections:
+      - Section: .hash
+      - Section: .dynamic
+
+## Check we report a warning when the hash table goes past the end of file.
+
+## Case A.1: the hash table ends right before the EOF. We have a broken nbucket
+##           field that has a value larger than the number of buckets.
+# RUN: yaml2obj --docnum=5 %s -o %t5.1.o -DNBUCKET=0x5d -DNCHAIN=0x1
+# RUN: llvm-readelf --hash-table %t5.1.o 2>&1 | FileCheck %s --check-prefix=NOERR1 --implicit-check-not="warning:"
+# RUN: llvm-readobj --hash-table %t5.1.o 2>&1 | FileCheck %s --check-prefix=NOERR1 --implicit-check-not="warning:"
+
+# NOERR1:      HashTable {
+# NOERR1-NEXT:  Num Buckets: 93
+# NOERR1-NEXT:  Num Chains: 1
+## Here we would dump the rest of the file as buckets array because we have a broken nbucket field.
+## No need to check what we dump, we only want to test that we have no unexpected warnings/crashes.
+# NOERR1-NEXT:  Buckets:
+# NOERR1-NEXT:  Chains: [0]
+# NOERR1-NEXT: }
+
+## Case A.2: the hash table ends 1 byte past the EOF. We have a broken nbucket
+##           field that has a value larger than the number of buckets.
+# RUN: yaml2obj --docnum=5 %s -o %t5.2.o -DNBUCKET=0x5e -DNCHAIN=0x1
+# RUN: llvm-readelf --hash-table %t5.2.o 2>&1 | FileCheck %s --check-prefix=ERR2 -DFILE=%t5.2.o --implicit-check-not="warning:"
+# RUN: llvm-readobj --hash-table %t5.2.o 2>&1 | FileCheck %s --check-prefix=ERR2 -DFILE=%t5.2.o --implicit-check-not="warning:"
+
+# ERR2:      HashTable {
+# ERR2-NEXT:  warning: '[[FILE]]': the hash table at offset 0x54 goes past the EOF (0x1d4), nbucket = 94, nchain = 1{{$}}
+# ERR2-NEXT: }
+
+## Case B.1: the hash table ends right before the EOF. We have a broken nchain
+##           field that has a value larger than the number of chains.
+# RUN: yaml2obj --docnum=5 %s -o %t5.3.o -DNBUCKET=0x1 -DNCHAIN=0x5d
+# RUN: llvm-readelf --hash-table %t5.3.o 2>&1 | FileCheck %s --check-prefix=NOERR2 -DFILE=%t5.3.o --implicit-check-not="warning:"
+# RUN: llvm-readobj --hash-table %t5.3.o 2>&1 | FileCheck %s --check-prefix=NOERR2 -DFILE=%t5.3.o --implicit-check-not="warning:"
+
+# NOERR2:      warning: '[[FILE]]': hash table nchain (93) differs from symbol count derived from SHT_DYNSYM section header (1)
+# NOERR2:      HashTable {
+# NOERR2-NEXT:   Num Buckets: 1
+# NOERR2-NEXT:   Num Chains: 93
+# NOERR2-NEXT:   Buckets: [0]
+## Here we would dump the rest of the file as chain array because we have a broken nchain field.
+## No need to check what we dump, we only want to test that we have no unexpected warnings/crashes.
+# NOERR2-NEXT:   Chains:
+# NOERR2-NEXT: }
+
+## Case B.2: the hash table ends 1 byte past the EOF. We have a broken nchain
+##           field that has a value larger than the number of chains.
+# RUN: yaml2obj --docnum=5 %s -o %t5.4.o -DNBUCKET=0x1 -DNCHAIN=0x5e
+# RUN: llvm-readelf --hash-table %t5.4.o 2>&1 | FileCheck %s --check-prefix=ERR3 -DFILE=%t5.4.o --implicit-check-not="warning:"
+# RUN: llvm-readobj --hash-table %t5.4.o 2>&1 | FileCheck %s --check-prefix=ERR3 -DFILE=%t5.4.o --implicit-check-not="warning:"
+
+# ERR3:      warning: '[[FILE]]': hash table nchain (94) differs from symbol count derived from SHT_DYNSYM section header (1)
+# ERR3:      HashTable {
+# ERR3-NEXT:  warning: '[[FILE]]': the hash table at offset 0x54 goes past the EOF (0x1d4), nbucket = 1, nchain = 94{{$}}
+# ERR3-NEXT: }
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS32
+  Data:    ELFDATA2LSB
+  Type:    ET_DYN
+  Machine: EM_X86_64
+Sections:
+  - Name:    .hash
+    Type:    SHT_HASH
+    Flags:   [ SHF_ALLOC ]
+    Bucket:  [ 0 ]
+    NBucket: [[NBUCKET]]
+    Chain:   [ 0 ]
+    NChain:  [[NCHAIN]]
+  - Name:  .dynamic
+    Type:  SHT_DYNAMIC
+    Flags: [ SHF_WRITE, SHF_ALLOC ]
+    Entries:
+      - Tag:   DT_HASH
+        Value: 0x0
+      - Tag:   DT_NULL
+        Value: 0x0
+DynamicSymbols: []
+ProgramHeaders:
+  - Type: PT_LOAD
+    Sections:
+      - Section: .hash
+      - Section: .dynamic

llvm/tools/llvm-readobj/ELFDumper.cpp

if (Entry.d_tag == ELF::DT_NEEDED)
       Libs.push_back(getDynamicString(Entry.d_un.d_val));
 
   llvm::sort(Libs);
 
   for (const std::string &L : Libs)
     W.startLine() << L << "\n";
 }
 
+template <class ELFT>
+static bool checkHashTable(const ELFFile<ELFT> *Obj,
+                           const typename ELFT::Hash *H, StringRef FileName) {
+  auto WarnAndReturn = [&](uint64_t Off, const Twine &Msg = "") {
+    reportWarning(createError("the hash table at offset 0x" +
+                              Twine::utohexstr(Off) + " goes past the EOF (0x" +
+                              Twine::utohexstr(Obj->getBufSize()) + ")" + Msg),
+                  FileName);
+    return false;
+  };
+
+  // Each SHT_HASH section starts from two 32-bit fields: nbucket and nchain.
+  // Hence the length of a hash table can't be less than 8 bytes.
+  const unsigned HeaderSize = 2 * sizeof(typename ELFT::Word);
+  const uint64_t SecOffset = (const uint8_t *)H - Obj->base();
+  if (Obj->getBufSize() - SecOffset < HeaderSize)
+    return WarnAndReturn(SecOffset);
+
+  if (Obj->getBufSize() - SecOffset - HeaderSize <
+      ((uint64_t)H->nbucket + H->nchain) * sizeof(typename ELFT::Word))
+    return WarnAndReturn(SecOffset, ", nbucket = " + Twine(H->nbucket) +
+                                        ", nchain = " + Twine(H->nchain));
+  return true;
+}
+
 template <typename ELFT> void ELFDumper<ELFT>::printHashTable() {
   DictScope D(W, "HashTable");
-  if (!HashTable)
+  if (!HashTable ||
+      !checkHashTable(ObjF->getELFFile(), HashTable, ObjF->getFileName()))
     return;
   W.printNumber("Num Buckets", HashTable->nbucket);
   W.printNumber("Num Chains", HashTable->nchain);
   W.printList("Buckets", HashTable->buckets());
   W.printList("Chains", HashTable->chains());
 }
 
 template <typename ELFT> void ELFDumper<ELFT>::printGnuHashTable() {

 }
 
 template <class ELFT> void GNUStyle<ELFT>::printHashSymbols(const ELFO *Obj) {
   if (this->dumper()->getDynamicStringTable().empty())
     return;
   auto StringTable = this->dumper()->getDynamicStringTable();
   auto DynSyms = this->dumper()->dynamic_symbols();
 
-  // Try printing .hash
-  if (auto SysVHash = this->dumper()->getHashTable()) {
-    OS << "\n Symbol table of .hash for image:\n";
+  auto PrintHashTable = [&](const Elf_Hash *SysVHash) {
     if (ELFT::Is64Bits)
       OS << "  Num Buc:    Value          Size   Type   Bind Vis      Ndx Name";
     else
       OS << "  Num Buc:    Value  Size   Type   Bind Vis      Ndx Name";
     OS << "\n";
 
     auto Buckets = SysVHash->buckets();
     auto Chains = SysVHash->chains();
for (uint32_t Buc = 0; Buc < SysVHash->nbucket; Buc++) {
               this->FileName);
           break;
         }
 
         printHashedSymbol(Obj, &DynSyms[0], Ch, StringTable, Buc);
         Visited[Ch] = true;
       }
     }
+  };
+
+  if (const Elf_Hash *SysVHash = this->dumper()->getHashTable()) {
+    OS << "\n Symbol table of .hash for image:\n";
+    if (checkHashTable(Obj, SysVHash, this->FileName))
+      PrintHashTable(SysVHash);
   }
 
   // Try printing .gnu.hash
   if (auto GnuHash = this->dumper()->getGnuHashTable()) {
     OS << "\n Symbol table of .gnu.hash for image:\n";
     if (ELFT::Is64Bits)
       OS << "  Num Buc:    Value          Size   Type   Bind Vis      Ndx Name";
     else

 // Hash histogram shows  statistics of how efficient the hash was for the
 // dynamic symbol table. The table shows number of hash buckets for different
 // lengths of chains as absolute number and percentage of the total buckets.
 // Additionally cumulative coverage of symbols for each set of buckets.
 template <class ELFT>
 void GNUStyle<ELFT>::printHashHistogram(const ELFFile<ELFT> *Obj) {
   // Print histogram for .hash section
   if (const Elf_Hash *HashTable = this->dumper()->getHashTable()) {
+    if (!checkHashTable(Obj, HashTable, this->FileName))
+      return;
+
     size_t NBucket = HashTable->nbucket;
     size_t NChain = HashTable->nchain;
     ArrayRef<Elf_Word> Buckets = HashTable->buckets();
     ArrayRef<Elf_Word> Chains = HashTable->chains();
     size_t TotalSyms = 0;
     // If hash table is correct, we have at least chains with 0 length
     size_t MaxChain = 1;
     size_t CumulativeNonZero = 0;