[llvm-dwarfdump] - Fix array out of bounds access crash.

[grimar]

Summary

I faced random crash in llvm-dwarfdump, which was randomly reproducable.
It happens because llvm-dwarfdump can access array out of bounds when DWARF
parsers tries to get children DIEs which are absent because of corrupted .debug_data.

Problem is in a following method:

DWARFDie getFirstChild() const {
  if (isValid() && Die->hasChildren())
    return DWARFDie(U, Die + 1);
  return DWARFDie();
}

Here new DWARFDie is created, but there is no checks that Die + 1
is a valid memory, because Die is a simple pointer. Though
it is possible for Die + 1 to point on garbage data and testcase provided
shows that.

I suggest to wrap Die into ArrayRef, what allows to do all the necessary safety checks.

[aprantl]

include/llvm/DebugInfo/DWARF/DWARFDie.h

45

Can you add a comment explaining why the Die member is an array and what the bounds of the array are representing? I assume that the last member of the array is the last children of the DIE?

tools/llvm-dwarfdump/llvm-dwarfdump.cpp

284 ↗

(On Diff #119859)

why does this break the iterator?

[dblaikie]

include/llvm/DebugInfo/DWARF/DWARFDie.h

53

This is probably better written as:

return &Die[0]

Though I guess this returns a pointer because it can be/is called on invalid DWARFDies? (in which case the above code would be invalid - and maybe we should assert that this isn't called on invalid DWARFDies? & maybe have it return a reference instead of a pointer if that's possible)

111

This is probably incorrect - in the sense that it'll produce a DWARFDie that has a longer array that contains more than its own children.

Imagine this tree of DIEs:

A
  B
  C

If you ask A for its first child, you'd get a DWARFDie containing {B, C} and then if you asked B for its first child, you could end up with C - even though C is a sibling of B, not a child.

I guess that bug already existed, but still...

lib/DebugInfo/DWARF/DWARFDie.cpp

504

Probably worth being consistent about using either Die.front() or Die[0] across this change. I'm not too fussed about which, really. I guess I lean slightly towards front(), though accept it's more verbose..

lib/DebugInfo/DWARF/DWARFUnit.cpp

428

I'd probably write DieArray.data() + I as &DieArray[I] - assuming I is in bounds?

[grimar]

Thanks everyone for comments ! I plan to address them tomorrow, few quick answers are below.

include/llvm/DebugInfo/DWARF/DWARFDie.h

45

No, last member is the las DIE of unit, just like in original code.
I'll revisit this place. May be we can just have array of children here.

111

you'd get a DWARFDie containing {B, C} and then if you asked B for its first child, you could end up with C

It should not happen. Because Die[0].hasChildren() takes information about children from abbreviation table,
so for that case it will not find DW_CHILDREN_yes there and will return empty DWARFDie as expected.

I'll try to improve this place though.

tools/llvm-dwarfdump/llvm-dwarfdump.cpp

284 ↗

(On Diff #119859)

It does not break it.
Problem is that CU->dies() iterates over array of DWARFDebugInfoEntry.
Previous code just used pointer as argument:

DWARFDie Die = {CU.get(), &Entry};

But now I need to pass ArrayRef of them to DWARFDie constructor, I need to find array size
or take DWARFDie that is already exist.

[grimar]

• Reimplemented in a much simpler and less error-prone way.

[aprantl]

Out of curiosity: does llvm-dwarfdump --verify fail on your testcase?

[grimar]

In D39185#905240, @aprantl wrote:

Out of curiosity: does llvm-dwarfdump --verify fail on your testcase?

Yes, it complains:

Verifying .debug_abbrev...
Verifying .debug_info Unit Header Chain...
error: Units[1] - start offset: 0x00000020
note: The length for this unit is too large for the .debug_info provided.
note: The 16 bit unit header version is not valid.
note: The address size is unsupported.
Verifying .debug_info references...
Errors detected.
warning: DWARF compile unit extends beyond its bounds cu 0x00000000 at 0x0000002
1'
warning: DWARF compile unit extends beyond its bounds cu 0x00000000 at 0x0000002
1'

[aprantl]

In D39185#905246, @grimar wrote:

In D39185#905240, @aprantl wrote:

Out of curiosity: does llvm-dwarfdump --verify fail on your testcase?

Yes, it complains:

Awesome!

Verifying .debug_abbrev...
Verifying .debug_info Unit Header Chain...
error: Units[1] - start offset: 0x00000020
note: The length for this unit is too large for the .debug_info provided.
note: The 16 bit unit header version is not valid.
note: The address size is unsupported.
Verifying .debug_info references...
Errors detected.
warning: DWARF compile unit extends beyond its bounds cu 0x00000000 at 0x0000002
1'
warning: DWARF compile unit extends beyond its bounds cu 0x00000000 at 0x0000002
1'

Uh.. that means we either have a bug in our DWARF backend or in the Verifier (probably the Verifier). That also needs to be fixed at some point :-)

include/llvm/DebugInfo/DWARF/DWARFDie.h

 /// is relative to the compile/type unit. Prior to this class the DWARFUnit and
 /// the DWARFDebugInfoEntry was passed around separately and there was the
 /// possibility for error if the wrong DWARFUnit was used to extract a unit
 /// relative offset. This class helps to ensure that this doesn't happen and
 /// also simplifies the attribute extraction calls by not having to specify the
 /// DWARFUnit for each call.
 class DWARFDie {
   DWARFUnit *U = nullptr;
   const DWARFDebugInfoEntry *Die = nullptr;
 
 public:
   DWARFDie() = default;
   DWARFDie(DWARFUnit *Unit, const DWARFDebugInfoEntry * D) : U(Unit), Die(D) {}
 
   bool isValid() const { return U && Die; }
   explicit operator bool() const { return isValid(); }
   const DWARFDebugInfoEntry *getDebugInfoEntry() const { return Die; }
   DWARFUnit *getDwarfUnit() const { return U; }
 
   /// Get the abbreviation declaration for this DIE.
   ///
   /// \returns the abbreviation declaration or NULL for null tags.
   const DWARFAbbreviationDeclaration *getAbbreviationDeclarationPtr() const {
     assert(isValid() && "must check validity prior to calling");
     return Die->getAbbreviationDeclarationPtr();
public:
   /// \returns a valid DWARFDie instance if this object has a sibling or an
   /// invalid DWARFDie instance if it doesn't.
   DWARFDie getSibling() const;
 
   /// Get the first child of this DIE object.
   ///
   /// \returns a valid DWARFDie instance if this object has children or an
   /// invalid DWARFDie instance if it doesn't.
-  DWARFDie getFirstChild() const {
-    if (isValid() && Die->hasChildren())
-      return DWARFDie(U, Die + 1);
-    return DWARFDie();
-  }
+  DWARFDie getFirstChild() const;
 
   /// Dump the DIE and all of its attributes to the supplied stream.
   ///
   /// \param OS the stream to use for output.
   /// \param indent the number of characters to indent each line that is output.
   void dump(raw_ostream &OS, unsigned indent = 0,
             DIDumpOptions DumpOpts = DIDumpOptions()) const;
 

include/llvm/DebugInfo/DWARF/DWARFUnit.h

public:
   /// \brief Return the DIE object at the given index.
   DWARFDie getDIEAtIndex(unsigned Index) {
     assert(Index < DieArray.size());
     return DWARFDie(this, &DieArray[Index]);
   }
 
   DWARFDie getParent(const DWARFDebugInfoEntry *Die);
   DWARFDie getSibling(const DWARFDebugInfoEntry *Die);
+  DWARFDie getFirstChild(const DWARFDebugInfoEntry *Die);
 
   /// \brief Return the DIE object for a given offset inside the
   /// unit's DIE vector.
   ///
   /// The unit needs to have its DIEs extracted for this method to work.
   DWARFDie getDIEForOffset(uint32_t Offset) {
     extractDIEsIfNeeded(false);
     assert(!DieArray.empty());

lib/DebugInfo/DWARF/DWARFDie.cpp

if (debug_info_data.isValidOffset(offset)) {
     }
   }
 }
 
 LLVM_DUMP_METHOD void DWARFDie::dump() const { dump(llvm::errs(), 0); }
 
 DWARFDie DWARFDie::getParent() const {
   if (isValid())
     return U->getParent(Die);
   return DWARFDie();
 }
 
 DWARFDie DWARFDie::getSibling() const {
   if (isValid())
     return U->getSibling(Die);
   return DWARFDie();
 }
 
+DWARFDie DWARFDie::getFirstChild() const {
+  if (isValid())
+    return U->getFirstChild(Die);
+  return DWARFDie();
+}
+
 iterator_range<DWARFDie::attribute_iterator> DWARFDie::attributes() const {
   return make_range(attribute_iterator(*this, false),
                     attribute_iterator(*this, true));
 }
 
 DWARFDie::attribute_iterator::attribute_iterator(DWARFDie D, bool End)
     : Die(D), AttrValue(0), Index(0) {
   auto AbbrDecl = Die.getAbbreviationDeclarationPtr();

lib/DebugInfo/DWARF/DWARFUnit.cpp

if (Depth == 0)
     return DWARFDie();
   // Depth of 1 always means parent is the compile/type unit.
   if (Depth == 1)
     return getUnitDIE();
   // Look for previous DIE with a depth that is one less than the Die's depth.
   const uint32_t ParentDepth = Depth - 1;
   for (uint32_t I = getDIEIndex(Die) - 1; I > 0; --I) {
     if (DieArray[I].getDepth() == ParentDepth)
       return DWARFDie(this, &DieArray[I]);
   }
   return DWARFDie();
 }
 
 DWARFDie DWARFUnit::getSibling(const DWARFDebugInfoEntry *Die) {
   if (!Die)
     return DWARFDie();
   uint32_t Depth = Die->getDepth();
   // Unit DIEs always have a depth of zero and never have siblings.
   if (Depth == 0)
     return DWARFDie();
   // NULL DIEs don't have siblings.
   if (Die->getAbbreviationDeclarationPtr() == nullptr)
     return DWARFDie();
   
   // Find the next DIE whose depth is the same as the Die's depth.
   for (size_t I = getDIEIndex(Die) + 1, EndIdx = DieArray.size(); I < EndIdx;
        ++I) {
     if (DieArray[I].getDepth() == Depth)
       return DWARFDie(this, &DieArray[I]);
   }
   return DWARFDie();
 }
 
+DWARFDie DWARFUnit::getFirstChild(const DWARFDebugInfoEntry *Die) {
+  if (!Die->hasChildren())
+    return DWARFDie();
+
+  // We do not want access out of bounds when parsing corrupted debug data.
+  size_t I = getDIEIndex(Die) + 1;
+  if (I >= DieArray.size())
+    return DWARFDie();
+  return DWARFDie(this, &DieArray[I]);
+}
+
 const DWARFAbbreviationDeclarationSet *DWARFUnit::getAbbreviations() const {
   if (!Abbrevs)
     Abbrevs = Abbrev->getAbbreviationDeclarationSet(AbbrOffset);
   return Abbrevs;
 }

test/tools/llvm-dwarfdump/X86/verify_debug_info2.s

+# RUN: llvm-mc %s -filetype obj -triple=i686-pc-linux -o %t
+# RUN: not llvm-dwarfdump -v -verify %t 2>&1 | FileCheck %s
+# CHECK: The length for this unit is too large for the .debug_info provided.
+
+## Check we do not crash when trying to parse truncated .debug_info.
+.section  .debug_info,"",@progbits
+  .long 0x1c
+  .value  0x4
+  .long  .Ldebug_abbrev0
+  .byte  0x4
+
+  .uleb128 0x1 # DW_TAG_compile_unit [1] *
+  .long  0     # DW_AT_producer [DW_FORM_strp] ( .debug_str[0x00000000] = "test")
+  .byte  0x4   # DW_AT_language [DW_FORM_data1] (DW_LANG_C_plus_plus)
+  .long  0     # DW_AT_name [DW_FORM_strp] ( .debug_str[0x00000000] = "test")
+  .long  0     # DW_AT_comp_dir [DW_FORM_strp] ( .debug_str[0x00000000] = "test")
+  .long  0     # DW_AT_low_pc [DW_FORM_addr] (0x0000000000000000)
+  .long  0     # DW_AT_high_pc [DW_FORM_data4] (0x00000000)
+
+.section  .debug_abbrev,"",@progbits
+.Ldebug_abbrev0:
+  .uleb128 0x1
+  .uleb128 0x11 # DW_TAG_compile_unit, DW_CHILDREN_yes
+  .byte  0x1
+  .uleb128 0x25 # DW_AT_producer, DW_FORM_strp
+  .uleb128 0xe
+  .uleb128 0x13 # DW_AT_language, DW_FORM_data1
+  .uleb128 0xb
+  .uleb128 0x3  # DW_AT_name, DW_FORM_strp
+  .uleb128 0xe
+  .uleb128 0x1b # DW_AT_comp_dir, DW_FORM_strp
+  .uleb128 0xe
+  .uleb128 0x11 # DW_AT_low_pc, DW_FORM_addr
+  .uleb128 0x1
+  .uleb128 0x12 # DW_AT_high_pc, DW_FORM_data4
+  .uleb128 0x6
+  .byte  0
+  .byte  0
+  .byte  0
+
+.section .debug_str,"MS",@progbits,1
+.string "test"