[llvm-readobj] - Fix possible crashes related to dumping gnu hash symbols.

[grimar]

Summary

It fixes possible scenarios when we crash/assert with --hash-symbols when
dumping an invalid GNU hash table which has a broken value in the buckets array.

This fixes a crash reported in comments for
https://bugs.llvm.org/show_bug.cgi?id=47681

[jhenderson]

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

662

It's not clear from this comment what is causing the attempt to read past the end of file. Please could you clarify.

672–673

679–680

Surely we should be diagnosing the attempt to read using an invalid dynamic symbol index in the first place, so that we don't see semi-random warnings?

691

Ditto.

llvm/tools/llvm-readobj/ELFDumper.cpp

4088

Perhaps this - "length" implies the number of entries in the array, whereas "size" could mean either that or the total size taken up by the array (e.g. 4 times the length, if the elements are 4 bytes in size each).

[grimar]

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

679–680

I am not sure honestly. Currently our logic is that we can't get here when there is no SHT_DYNSYM section,
because we take the size of the dynamic symbol table from there and there is no other way to get it.
I.e. there is no dynamic tag for that, so in case when we e.g. don't have a .hash table to infer the size,
we will never be able to dump symbols currently and we return earlier:

void GNUStyle<ELFT>::printGnuHashTableSymbols(const Elf_GnuHash &GnuHash) {
  StringRef StringTable = this->dumper().getDynamicStringTable();
  if (StringTable.empty())
    return;

  Elf_Sym_Range DynSyms = this->dumper().dynamic_symbols();
  const Elf_Sym *FirstSym = DynSyms.empty() ? nullptr : &DynSyms[0];
  if (!FirstSym) {
    Optional<DynRegionInfo> DynSymRegion = this->dumper().getDynSymRegion();
    this->reportUniqueWarning(createError(
        Twine("unable to print symbols for the .gnu.hash table: the "
              "dynamic symbol table ") +
        (DynSymRegion ? "is empty" : "was not found")));
    return;
  }
....

At the same time I think loaders have no any checks (i.e. they don't try to use the size from SHT_DYNSYM) and will try to use a dynamic symbol found via DT_SYMTAB only. In this case it might probably be useful to try to dump symbols here,
even if they are invalid to reveal what loaders see on their side? Perhaps worth showing an additional warning, saying that we think/found that an index is invalid though. And we can also probably change the code shown above to allow us to pass when DynSymRegion.Addr != 0 (i.e. when we found a DT_SYMTAB, but no SHT_DYNSYM and the address is within the file).

If not, we can probably just skip symbols with invalid indices, just like you've suggested.

What do you think?

[uweigand]

I think the handling of the GNU hash table is actually already fully correct. The crash (or error message when using this patch) is simply a side effect of the fact that size of the DynSymRegion was clobbered here (near the end of ELFDumper<ELFT>::parseDynamicTable()):

DynSymRegion->Size = HashTable->nchain * DynSymRegion->EntSize;

This in turn is because HashTable->nchain (like all of HashTable) is just incorrect on s390x at the moment, as discussed in https://bugs.llvm.org/show_bug.cgi?id=47681

[jhenderson]

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

679–680

Ah, I forgot that the dynsym has no size in the dynamic table (that's still dumb, but oh well). I think if we have information implying the index looks broken, due to other information (e.g. the section header), we should at least warn that this is probably not correct. I think the warning would be more than enough to say something is a bit bogus. I also think that means we don't need to try to dump invalid index symbols if we know they are bogus (why would a user care what the loader sees if they know that whatever it is is bad - in such situations they'd need to fix the source of the bad index).

I'm a little struggling to follow the full details of your comment though. so I may be misunderstanding your points/questions.

[uweigand]

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

679–680

As I said in my comment yesterday, in this particular executable we do have the correct size of dynsym from the section table -- it's just that this (correct) size is later replaced by (incorrect) information derived from the .hash section.

[grimar]

In D88561#2304127, @uweigand wrote:

I think the handling of the GNU hash table is actually already fully correct. The crash (or error message when using this patch) is simply a side effect of the fact that size of the DynSymRegion was clobbered here (near the end of ELFDumper<ELFT>::parseDynamicTable()):

DynSymRegion->Size = HashTable->nchain * DynSymRegion->EntSize;

This in turn is because HashTable->nchain (like all of HashTable) is just incorrect on s390x at the moment, as discussed in https://bugs.llvm.org/show_bug.cgi?id=47681

That is true for you executable. But this patch fixes a bit different case. Here I am creating the .gnu.hash table with a broken value in the buckets array.
Currently with the test case provided we crash an all platforms at the same place where your executable crashes too.
So with this patch we fix the crash, but not the reason of PR47681, which is s390x specific.

[grimar]

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

679–680

I'm a little struggling to follow the full details of your comment though. so I may be misunderstanding your points/questions.

Nope. You got me right. I'll update the patch to report a warning and will stop printing a bogus symbol.

[uweigand]

In D88561#2305598, @grimar wrote:

In D88561#2304127, @uweigand wrote:

I think the handling of the GNU hash table is actually already fully correct. The crash (or error message when using this patch) is simply a side effect of the fact that size of the DynSymRegion was clobbered here (near the end of ELFDumper<ELFT>::parseDynamicTable()):

DynSymRegion->Size = HashTable->nchain * DynSymRegion->EntSize;

This in turn is because HashTable->nchain (like all of HashTable) is just incorrect on s390x at the moment, as discussed in https://bugs.llvm.org/show_bug.cgi?id=47681

That is true for you executable. But this patch fixes a bit different case. Here I am creating the .gnu.hash table with a broken value in the buckets array.
Currently with the test case provided we crash an all platforms at the same place where your executable crashes too.
So with this patch we fix the crash, but not the reason of PR47681, which is s390x specific.

I see. In this case this patch doesn't really address PR47681, but only replaces a crash with wrong output ... Still preferable to not crash, but of course we still need to fix the root cause (at the least, by ignoring the .hash section if the entry size doesn't match).

[grimar]

In D88561#2305660, @uweigand wrote:

I see. In this case this patch doesn't really address PR47681, but only replaces a crash with wrong output ... Still preferable to not crash, but of course we still need to fix the root cause (at the least, by ignoring the .hash section if the entry size doesn't match).

The fix for PR47681 (s390 specific) is independent from the crash (all platforms), so it should be fixed separatelly.
I am going to prepare a follow-up to fix the PR47681 after landing this.

[uweigand]

In D88561#2305667, @grimar wrote:

In D88561#2305660, @uweigand wrote:

I see. In this case this patch doesn't really address PR47681, but only replaces a crash with wrong output ... Still preferable to not crash, but of course we still need to fix the root cause (at the least, by ignoring the .hash section if the entry size doesn't match).

The fix for PR47681 (s390 specific) is independent from the crash (all platforms), so it should be fixed separatelly.
I'll am going to prepare a follow-up to fix the PR47681 after landing this.

Thanks!

[grimar]

• Update implementation (validate the symbol index and related changes and simplifications).

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

662

I've updated implementation and had to rework all test cases. Now there are no cases when we try read past the EOF - or at least I can't imagine an input for that atm.

llvm/tools/llvm-readobj/ELFDumper.cpp

4088

This place is gone.

[jhenderson]

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

723

724

llvm/tools/llvm-readobj/ELFDumper.cpp

2748

4061

4073–4074

I'm not sure I understand what 'Values' here is referring to. Is it the hash values, or something else? Either way, there needs to be more context here.

[grimar]

• Addressed review comments.

[jhenderson]

Looks good aside from a possible broken test.

llvm/test/tools/llvm-readobj/ELF/gnuhash.test

128 ↗

(On Diff #296443)

This test looks like it might need updating?

[grimar]

llvm/test/tools/llvm-readobj/ELF/gnuhash.test

128 ↗

(On Diff #296443)

This message comes from a different place,
for LLVM style we show it when fail to dump Values:

void ELFDumper<ELFT>::printGnuHashTable() {
.....

  Expected<ArrayRef<Elf_Word>> Chains =
      getGnuHashTableChains<ELFT>(DynSymRegion, GnuHashTable);
  if (!Chains) {
    reportUniqueWarning(
        createError("unable to dump 'Values' for the SHT_GNU_HASH "
                    "section: " +
                    toString(Chains.takeError())));
    return;
  }

  W.printHexList("Values", *Chains);

I.e. it is unrelated to this patch, I think I just copypasted this error previously.
And for this particular place it seems that mentioning 'Values' in the message is reasonable.

[jhenderson]

llvm/test/tools/llvm-readobj/ELF/gnuhash.test

128 ↗

(On Diff #296443)

Okay (but I don't think 'Values' makes sense - values of what?)

[grimar]

llvm/test/tools/llvm-readobj/ELF/gnuhash.test

128 ↗

(On Diff #296443)

An example of normal output is:

GnuHashTable {
  Num Buckets: 3
  First Hashed Symbol Index: 1
  Num Mask Words: 2
  Shift Count: 2
  Bloom Filter: [0x3, 0x4]
  Buckets: [5, 6, 7]
  Values: [0x8, 0x9, 0xA, 0xB]
}

I.e. Values refers to the field that was expected to be dumped, but was not because of an error.

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

- Name:  .dynsym
     Size:  0
 ProgramHeaders:
   - Type:  PT_LOAD
     Flags: [ PF_R, PF_X ]
     Sections:
       - Section: .gnu.hash
       - Section: .dynamic
       - Section: .dynstr
+
+## In this case we have a broken value in the hash buckets array. Normally it contains an
+## index into the dynamic symbol table and also is used to get a hash value from the hash values array.
+
+## Case A: a hashed symbol can't be read, because of reading past the EOF attempt.
+# RUN: yaml2obj --docnum=11 -DVALUE=0x17 %s -o %t11.past.eof.so
+# RUN: llvm-readelf --hash-symbols %t11.past.eof.so 2>&1 | \
+# RUN:   FileCheck %s -DFILE=%t11.past.eof.so --check-prefix=BUCKET-PAST-EOF
+
+# BUCKET-PAST-EOF:      Symbol table of .gnu.hash for image:
+# BUCKET-PAST-EOF-NEXT:   Num Buc:    Value          Size   Type   Bind Vis      Ndx Name
+# BUCKET-PAST-EOF-NEXT: warning: '[[FILE]]': unable to print hashed symbol with index 23: reading from 0xc0 goes past the end of the file (0x2f0)
+# BUCKET-PAST-EOF-NOT:  {{.}}
+
+## Case B.1: a hash value entry can't be read because we have a broken value in the hash buckets array and trying to read
+##         a data past the end of the hash values array. The VALUE used is equal to the value from the case A minus 1.
+# RUN: yaml2obj --docnum=11 -DVALUE=0x16 %s -o %t11.value1.so
+# RUN: llvm-readelf --hash-symbols %t11.value1.so 2>&1 | \
+# RUN:   FileCheck %s -DFILE=%t11.value1.so --check-prefix=BUCKET-READ-VALUE-A
+
+# BUCKET-READ-VALUE-A:      Num Buc:    Value          Size   Type   Bind Vis      Ndx Name
+## Note: we are trying to dump a dynamic symbol using a wrong index and so reading some arbitrary data as symbol data.
+##       That is why the following warning is reported.
+# BUCKET-READ-VALUE-A-NEXT: warning: '[[FILE]]': st_name (0x36) is past the end of the string table of size 0x5
+# BUCKET-READ-VALUE-A-NEXT:    22   1: 0000000000000000     1 NOTYPE  LOCAL  DEFAULT UND <?>
+# BUCKET-READ-VALUE-A-NEXT: warning: '[[FILE]]': unable to read the hash value: index (22) goes past the end of the hash values array of size 2
+
+## Case B.2: the same as B.1, but now the value is equal to the size of the hash values array.
+# RUN: yaml2obj --docnum=11 -DVALUE=0x2 %s -o %t11.value2.so
+# RUN: llvm-readelf --hash-symbols %t11.value2.so 2>&1 | \
+# RUN:   FileCheck %s -DFILE=%t11.value2.so --check-prefix=BUCKET-READ-VALUE-B
+
+# BUCKET-READ-VALUE-B:      Num Buc:    Value          Size   Type   Bind Vis      Ndx Name
+## Note: we are trying to dump a dynamic symbol using a wrong index and so reading some arbitrary data as symbol data.
+##       That is why the following warning is reported.
+# BUCKET-READ-VALUE-B-NEXT: warning: '[[FILE]]': st_name (0x6f6f6600) is past the end of the string table of size 0x5
+# BUCKET-READ-VALUE-B-NEXT:     2   1: 2e007274736e7964 3314769694139775332 NOTYPE LOCAL DEFAULT 11776 <?>
+# BUCKET-READ-VALUE-B-NEXT: warning: '[[FILE]]': unable to read the hash value: index (2) goes past the end of the hash values array of size 2
+
+--- !ELF
+FileHeader:
+  Class: ELFCLASS64
+  Data:  ELFDATA2LSB
+  Type:  ET_DYN
+Sections:
+  - Name:  .gnu.hash
+    Type:  SHT_GNU_HASH
+    Flags: [ SHF_ALLOC ]
+    Link:  .dynsym
+    Header:
+      SymNdx: 0x0
+      Shift2: 0x0
+    BloomFilter: [ 0x0 ]
+    HashBuckets: [ 0x0, [[VALUE]] ]
+    HashValues:  [ 0x0 ]
+  - Name:  .dynamic
+    Type:  SHT_DYNAMIC
+    Flags: [ SHF_ALLOC ]
+    Link:  .dynstr
+    Entries:
+      - Tag:   DT_GNU_HASH
+        Value: 0x0
+      - Tag:   DT_NULL
+        Value: 0x0
+DynamicSymbols:
+  - Name:    foo
+    Binding: STB_GLOBAL
+ProgramHeaders:
+  - Type:  PT_LOAD
+    Flags: [ PF_R, PF_X ]
+    Sections:
+      - Section: .gnu.hash
+      - Section: .dynamic

llvm/tools/llvm-readobj/ELFDumper.cpp

getGnuHashTableChains(Optional<DynRegionInfo> DynSymRegion,
   // vector (or no values at all). It happens because the value of symndx is not
   // important for dynamic loaders when the GNU hash table is empty. They just
   // skip the whole object during symbol lookup. In such cases, the symndx value
   // is irrelevant and we should not report a warning.
   ArrayRef<typename ELFT::Word> Buckets = GnuHashTable->buckets();
   if (!llvm::all_of(Buckets, [](typename ELFT::Word V) { return V == 0; }))
     return createError("the first hashed symbol index (" +
                        Twine(GnuHashTable->symndx) +
                        ") is larger than the number of dynamic symbols (" +
                        Twine(NumSyms) + ")");
   // There is no way to represent an array of (dynamic symbols count - symndx)
   // length.
   return ArrayRef<typename ELFT::Word>();
 }
 
 template <typename ELFT>
 void ELFDumper<ELFT>::printGnuHashTable() {
if (!FirstSym) {
     Optional<DynRegionInfo> DynSymRegion = this->dumper().getDynSymRegion();
     this->reportUniqueWarning(createError(
         Twine("unable to print symbols for the .gnu.hash table: the "
               "dynamic symbol table ") +
         (DynSymRegion ? "is empty" : "was not found")));
     return;
   }
 
+  auto GetSymbol = [&](uint64_t SymIndex) -> const Elf_Sym * {
+    uint64_t SymOffset =
+        reinterpret_cast<const uint8_t *>(FirstSym) - this->Obj.base();
+    if (SymOffset + (SymIndex + 1) * sizeof(Elf_Sym) <= this->Obj.getBufSize())
+      return FirstSym + SymIndex;
+    this->reportUniqueWarning(createError(
+        "unable to print hashed symbol with index " + Twine(SymIndex) +
+        ": reading from 0x" + Twine::utohexstr(SymOffset) +
+        " goes past the end of the file (0x" +
+        Twine::utohexstr(this->Obj.getBufSize()) + ")"));
+    return nullptr;
+  };
+
   ArrayRef<Elf_Word> Buckets = GnuHash.buckets();
   for (uint32_t Buc = 0; Buc < GnuHash.nbuckets; Buc++) {
     if (Buckets[Buc] == ELF::STN_UNDEF)
       continue;
     uint32_t Index = Buckets[Buc];
     uint32_t GnuHashable = Index - GnuHash.symndx;
     // Print whole chain
     while (true) {
       uint32_t SymIndex = Index++;
-      printHashedSymbol(FirstSym + SymIndex, SymIndex, StringTable, Buc);
-      // Chain ends at symbol with stopper bit
-      if ((GnuHash.values(DynSyms.size())[GnuHashable++] & 1) == 1)
+      if (const Elf_Sym *Sym = GetSymbol(SymIndex))
+        printHashedSymbol(Sym, SymIndex, StringTable, Buc);
+      else
+        break;
+
+      // Chain ends at symbol with stopper bit.
+      ArrayRef<Elf_Word> Values = GnuHash.values(DynSyms.size());
+      if (GnuHashable >= Values.size()) {
+        this->reportUniqueWarning(createError(
+            "unable to read the hash value: index (" + Twine(GnuHashable) +
+            ") goes past the end of the hash values array of size " +
+            Twine(Values.size())));
+        break;
+      }
+
+      if ((Values[GnuHashable++] & 1) == 1)
         break;
     }
   }
 }
 
 template <class ELFT> void GNUStyle<ELFT>::printHashSymbols() {
   if (const Elf_Hash *SysVHash = this->dumper().getHashTable()) {
     OS << "\n Symbol table of .hash for image:\n";