[PATCH] libdw: Add overflow checking to __libdw_form_val_len.

[PATCH] libdw: Add overflow checking to __libdw_form_val_len.

[Mark Wielaard]

[-- Attachment #1: Type: text/plain, Size: 9532 bytes --]

This solves a couple of crashers reported by Alexander.

This will probably have some performance impact, but I haven't measured
it yet. It would be good to have some performance tests. We also need
some overflow check for leb128 reading.

Josh, which tests did you use last time when you did the performance
improvements of this code? I am afraid I won't be able to keep it as fast,
but it would be good to know how much this slows things down.

Pass endp as argument to __libdw_form_val_len and check we don't read
beyond the end of expected data and don't return lengths that would
overflow.

Signed-off-by: Mark Wielaard <mjw@redhat.com>
---
 libdw/ChangeLog         | 10 ++++++++++
 libdw/dwarf_child.c     |  7 ++++---
 libdw/dwarf_getattrs.c  | 13 +++++++------
 libdw/dwarf_getmacros.c |  8 ++++++--
 libdw/libdwP.h          | 22 ++++++++++++++++------
 libdw/libdw_form.c      | 47 +++++++++++++++++++++++++++++++++--------------
 6 files changed, 76 insertions(+), 31 deletions(-)

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index bab02e5..8786d7f 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,13 @@
+2014-12-04  Mark Wielaard  <mjw@redhat.com>
+
+	* libdwP.h (__libdw_form_val_compute_len): Add endp argument.
+	(__libdw_form_val_len): Likewise and check len doesn't overflow.
+	* libdw_form.c (__libdw_form_val_compute_len): Likewise.
+	* dwarf_child.c (__libdw_find_attr): Call __libdw_form_val_len
+	with endp.
+	* dwarf_getattrs.c (dwarf_getattrs): Likewise.
+	* dwarf_getmacros.c (read_macros): Likewise and check for errors.
+
 2014-11-27  Mark Wielaard  <mjw@redhat.com>
 
 	* Makefile.am (libdw.so): Use textrel_check.
diff --git a/libdw/dwarf_child.c b/libdw/dwarf_child.c
index 1d3a337..fa31600 100644
--- a/libdw/dwarf_child.c
+++ b/libdw/dwarf_child.c
@@ -1,5 +1,5 @@
 /* Return child of current DIE.
-   Copyright (C) 2003-2011 Red Hat, Inc.
+   Copyright (C) 2003-2011, 2014 Red Hat, Inc.
    This file is part of elfutils.
    Written by Ulrich Drepper <drepper@redhat.com>, 2003.
 
@@ -104,7 +104,8 @@ __libdw_find_attr (Dwarf_Die *die, unsigned int search_name,
       /* Skip over the rest of this attribute (if there is any).  */
       if (attr_form != 0)
 	{
-	  size_t len = __libdw_form_val_len (dbg, die->cu, attr_form, readp);
+	  size_t len = __libdw_form_val_len (dbg, die->cu, attr_form, readp,
+					     endp);
 
 	  if (unlikely (len == (size_t) -1l))
 	    {
@@ -112,7 +113,7 @@ __libdw_find_attr (Dwarf_Die *die, unsigned int search_name,
 	      break;
 	    }
 
-	  // XXX We need better boundary checks.
+	  // __libdw_form_val_len will have done a bounds check.
 	  readp += len;
 	}
     }
diff --git a/libdw/dwarf_getattrs.c b/libdw/dwarf_getattrs.c
index 82eb3f8..627a851 100644
--- a/libdw/dwarf_getattrs.c
+++ b/libdw/dwarf_getattrs.c
@@ -1,5 +1,5 @@
 /* Get attributes of the DIE.
-   Copyright (C) 2004, 2005, 2008, 2009 Red Hat, Inc.
+   Copyright (C) 2004, 2005, 2008, 2009, 2014 Red Hat, Inc.
    This file is part of elfutils.
    Written by Ulrich Drepper <drepper@redhat.com>, 2004.
 
@@ -67,12 +67,13 @@ dwarf_getattrs (Dwarf_Die *die, int (*callback) (Dwarf_Attribute *, void *),
 
   /* Go over the list of attributes.  */
   Dwarf *dbg = die->cu->dbg;
+  const unsigned char *endp;
+  endp = ((const unsigned char *) dbg->sectiondata[IDX_debug_abbrev]->d_buf
+	  + dbg->sectiondata[IDX_debug_abbrev]->d_size);
   while (1)
     {
       /* Are we still in bounds?  */
-      if (unlikely (attrp
-		    >= ((unsigned char *) dbg->sectiondata[IDX_debug_abbrev]->d_buf
-			+ dbg->sectiondata[IDX_debug_abbrev]->d_size)))
+      if (unlikely (attrp >= endp))
 	goto invalid_dwarf;
 
       /* Get attribute name and form.  */
@@ -111,13 +112,13 @@ dwarf_getattrs (Dwarf_Die *die, int (*callback) (Dwarf_Attribute *, void *),
       if (attr.form != 0)
 	{
 	  size_t len = __libdw_form_val_len (dbg, die->cu, attr.form,
-					     die_addr);
+					     die_addr, endp);
 
 	  if (unlikely (len == (size_t) -1l))
 	    /* Something wrong with the file.  */
 	    return -1l;
 
-	  // XXX We need better boundary checks.
+	  // __libdw_form_val_len will have done a bounds check.
 	  die_addr += len;
 	}
     }
diff --git a/libdw/dwarf_getmacros.c b/libdw/dwarf_getmacros.c
index 8d9d78b..76f9de0 100644
--- a/libdw/dwarf_getmacros.c
+++ b/libdw/dwarf_getmacros.c
@@ -367,8 +367,12 @@ read_macros (Dwarf *dbg, int sec_index,
 	  attributes[i].valp = (void *) readp;
 	  attributes[i].cu = &fake_cu;
 
-	  readp += __libdw_form_val_len (dbg, &fake_cu,
-					 proto->forms[i], readp);
+	  size_t len = __libdw_form_val_len (dbg, &fake_cu,
+					     proto->forms[i], readp, endp);
+	  if (len == (size_t) -1)
+	    return -1;
+
+	  readp += len;
 	}
 
       Dwarf_Macro macro = {
diff --git a/libdw/libdwP.h b/libdw/libdwP.h
index 5ccb13c..351c5b4 100644
--- a/libdw/libdwP.h
+++ b/libdw/libdwP.h
@@ -458,14 +458,16 @@ extern Dwarf_Abbrev *__libdw_getabbrev (Dwarf *dbg, struct Dwarf_CU *cu,
 /* Helper functions for form handling.  */
 extern size_t __libdw_form_val_compute_len (Dwarf *dbg, struct Dwarf_CU *cu,
 					    unsigned int form,
-					    const unsigned char *valp)
-     __nonnull_attribute__ (1, 2, 4) internal_function;
+					    const unsigned char *valp,
+					    const unsigned char *endp)
+     __nonnull_attribute__ (1, 2, 4, 5) internal_function;
 
 /* Find the length of a form attribute.  */
 static inline size_t
-__nonnull_attribute__ (1, 2, 4)
+__nonnull_attribute__ (1, 2, 4, 5)
 __libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu,
-		      unsigned int form, const unsigned char *valp)
+		      unsigned int form, const unsigned char *valp,
+		      const unsigned char *endp)
 {
   /* Small lookup table of forms with fixed lengths.  Absent indexes are
      initialized 0, so any truly desired 0 is set to 0x80 and masked.  */
@@ -483,11 +485,19 @@ __libdw_form_val_len (Dwarf *dbg, struct Dwarf_CU *cu,
     {
       uint8_t len = form_lengths[form];
       if (len != 0)
-	return len & 0x7f; /* Mask to allow 0x80 -> 0.  */
+	{
+	  len &= 0x7f; /* Mask to allow 0x80 -> 0.  */
+	  if (unlikely (len > (size_t) (endp - valp)))
+	    {
+	      __libdw_seterrno (DWARF_E_INVALID_DWARF);
+	      return -1;
+	    }
+	  return len;
+	}
     }
 
   /* Other forms require some computation.  */
-  return __libdw_form_val_compute_len (dbg, cu, form, valp);
+  return __libdw_form_val_compute_len (dbg, cu, form, valp, endp);
 }
 
 /* Helper function for DW_FORM_ref* handling.  */
diff --git a/libdw/libdw_form.c b/libdw/libdw_form.c
index 5350556..65ac7de 100644
--- a/libdw/libdw_form.c
+++ b/libdw/libdw_form.c
@@ -1,5 +1,5 @@
 /* Helper functions for form handling.
-   Copyright (C) 2003-2009 Red Hat, Inc.
+   Copyright (C) 2003-2009, 2014 Red Hat, Inc.
    This file is part of elfutils.
    Written by Ulrich Drepper <drepper@redhat.com>, 2003.
 
@@ -40,9 +40,10 @@
 size_t
 internal_function
 __libdw_form_val_compute_len (Dwarf *dbg, struct Dwarf_CU *cu,
-			      unsigned int form, const unsigned char *valp)
+			      unsigned int form, const unsigned char *valp,
+			      const unsigned char *endp)
 {
-  const unsigned char *saved;
+  const unsigned char *startp = valp;
   Dwarf_Word u128;
   size_t result;
 
@@ -66,49 +67,67 @@ __libdw_form_val_compute_len (Dwarf *dbg, struct Dwarf_CU *cu,
       break;
 
     case DW_FORM_block1:
+      if (unlikely ((size_t) (endp - startp) < 1))
+	goto invalid;
       result = *valp + 1;
       break;
 
     case DW_FORM_block2:
+      if (unlikely ((size_t) (endp - startp) < 2))
+	goto invalid;
       result = read_2ubyte_unaligned (dbg, valp) + 2;
       break;
 
     case DW_FORM_block4:
+      if (unlikely ((size_t) (endp - startp) < 4))
+	goto invalid;
       result = read_4ubyte_unaligned (dbg, valp) + 4;
       break;
 
     case DW_FORM_block:
     case DW_FORM_exprloc:
-      saved = valp;
+      // XXX overflow check
       get_uleb128 (u128, valp);
-      result = u128 + (valp - saved);
+      result = u128 + (valp - startp);
       break;
 
     case DW_FORM_string:
-      result = strlen ((char *) valp) + 1;
-      break;
+      {
+	const unsigned char *endstrp = memchr (valp, '\0',
+					       (size_t) (endp - startp));
+	if (unlikely (endstrp == NULL))
+	  goto invalid;
+	result = (size_t) (endstrp - startp) + 1;
+	break;
+      }
 
     case DW_FORM_sdata:
     case DW_FORM_udata:
     case DW_FORM_ref_udata:
-      saved = valp;
+      // XXX overflow check
       get_uleb128 (u128, valp);
-      result = valp - saved;
+      result = valp - startp;
       break;
 
     case DW_FORM_indirect:
-      saved = valp;
       get_uleb128 (u128, valp);
       // XXX Is this really correct?
-      result = __libdw_form_val_len (dbg, cu, u128, valp);
+      result = __libdw_form_val_len (dbg, cu, u128, valp, endp);
       if (result != (size_t) -1)
-	result += valp - saved;
+	result += valp - startp;
+      else
+        return (size_t) -1;
       break;
 
     default:
+      goto invalid;
+    }
+
+  if (unlikely (result > (size_t) (endp - startp)))
+    {
+    invalid:
       __libdw_seterrno (DWARF_E_INVALID_DWARF);
-      result = (size_t) -1l;
-      break;
+      result = (size_t) -1;
     }
 
   return result;
-- 
1.8.3.1

Re: [PATCH] libdw: Add overflow checking to __libdw_form_val_len.

[Mark Wielaard]

[-- Attachment #1: Type: text/plain, Size: 790 bytes --]

On Tue, 2014-12-09 at 18:44 -0800, Josh Stone wrote:
> Ok, well my former optimizations went into 0.158.  Here are some quick
> runs of "varlocs -k >/dev/null" on kernel-3.17.4-301.fc21.x86_64:
> 
> 0.157	96.00user 0.12system 1:36.08elapsed
> 0.158	70.22user 0.12system 1:10.32elapsed
> 0.159	71.40user 0.11system 1:11.48elapsed
> 0.160	73.24user 0.12system 1:13.33elapsed
> master	77.65user 0.10system 1:17.72elapsed
> patched	77.87user 0.10system 1:17.93elapsed
> 
> So each release has ceded a bit of performance, but this particular
> patch isn't much of an issue.  Correctness trumps performance anyway.

Thanks for all the testing (and for your patches trying to get our
performance back). I have now pushed this overflow checking patch to
master.

Cheers,

Mark

Re: [PATCH] libdw: Add overflow checking to __libdw_form_val_len.

[Josh Stone]

[-- Attachment #1: Type: text/plain, Size: 1781 bytes --]

On 12/07/2014 05:23 PM, Petr Machata wrote:
> Josh Stone <jistone@redhat.com> writes:
> 
>> I'll see if I can grab that old kernel debuginfo to do a more direct
>> comparison.
> 
> You could grab the old code and compare that.  If you're still in the
> 80's, it's the data, not the code.

Ok, well my former optimizations went into 0.158.  Here are some quick
runs of "varlocs -k >/dev/null" on kernel-3.17.4-301.fc21.x86_64:

0.157	96.00user 0.12system 1:36.08elapsed
0.158	70.22user 0.12system 1:10.32elapsed
0.159	71.40user 0.11system 1:11.48elapsed
0.160	73.24user 0.12system 1:13.33elapsed
master	77.65user 0.10system 1:17.72elapsed
patched	77.87user 0.10system 1:17.93elapsed

So each release has ceded a bit of performance, but this particular
patch isn't much of an issue.  Correctness trumps performance anyway.


For fun, here are the counts from dwgrep -e 'entry attribute form':

3.11.9-300.fc20.x86_64/vmlinux:
2       DW_FORM_block2
252     DW_FORM_block1
24975   DW_FORM_data4
182227  DW_FORM_data8
259701  DW_FORM_sdata
330195  DW_FORM_addr
387491  DW_FORM_sec_offset
537586  DW_FORM_exprloc
558135  DW_FORM_string
1397719 DW_FORM_flag_present
3353170 DW_FORM_data2
5220907 DW_FORM_strp
9263689 DW_FORM_ref4
13543053        DW_FORM_data1

3.17.4-301.fc21.x86_64/vmlinux:
2       DW_FORM_block2
256     DW_FORM_block1
26740   DW_FORM_data4
112315  DW_FORM_exprloc
197526  DW_FORM_data8
213497  DW_FORM_sec_offset
340039  DW_FORM_sdata
358462  DW_FORM_addr
641163  DW_FORM_string
1578298 DW_FORM_flag_present
3857598 DW_FORM_data2
6023993 DW_FORM_strp
10463444        DW_FORM_ref4
15532042        DW_FORM_data1

Also .text size grew from 10082549 to 11513127.

So it's all bigger, but roughly proportional.

Re: [PATCH] libdw: Add overflow checking to __libdw_form_val_len.

[Petr Machata]

[-- Attachment #1: Type: text/plain, Size: 256 bytes --]

Josh Stone <jistone@redhat.com> writes:

> I'll see if I can grab that old kernel debuginfo to do a more direct
> comparison.

You could grab the old code and compare that.  If you're still in the
80's, it's the data, not the code.

Thanks,
Petr

Re: [PATCH] libdw: Add overflow checking to __libdw_form_val_len.

[Josh Stone]

[-- Attachment #1: Type: text/plain, Size: 1268 bytes --]

On 12/04/2014 01:00 PM, Mark Wielaard wrote:
> This solves a couple of crashers reported by Alexander.
> 
> This will probably have some performance impact, but I haven't measured
> it yet. It would be good to have some performance tests. We also need
> some overflow check for leb128 reading.
> 
> Josh, which tests did you use last time when you did the performance
> improvements of this code? I am afraid I won't be able to keep it as fast,
> but it would be good to know how much this slows things down.

I couldn't remember, but I found my original intro:
https://lists.fedorahosted.org/pipermail/elfutils-devel/2013-December/003549.html

So the numbers I reported were with "tests/varlocs -k >/dev/null".

The good news is that your patch is barely slower, 81.64s -> 82.34s.
That's almost noise, but it's consistently a little slower over several
attempts.  That's to be expected with more checks though.

The bad news is that these numbers in the 80s are back in the
neighborhood of where I was before those optimization patches.  That's
not an apples-to-apples comparison, since I'm now on F21 gcc and kernel,
but that's still a lot to slip back. :(

I'll see if I can grab that old kernel debuginfo to do a more direct
comparison.