[PATCH] libdw: check memory access in get_(u|s)leb128

[PATCH] libdw: check memory access in get_(u|s)leb128

[vvvvvv]

From: Aleksei Vetrov <vvvvvv@google.com>

__libdw_get_uleb128 and __libdw_get_sleb128 should check if addrp has
already reached the end before unrolling the first step. It is done by
moving __libdw_max_len to the beginning of the function, which already
has all the checks.

Signed-off-by: Aleksei Vetrov <vvvvvv@google.com>
---
 libdw/memory-access.h | 10 ++++++----
 tests/leb128.c        | 29 ++++++++++++++++++++++++++++-
 2 files changed, 34 insertions(+), 5 deletions(-)

diff --git a/libdw/memory-access.h b/libdw/memory-access.h
index fca4129a..1cac6af3 100644
--- a/libdw/memory-access.h
+++ b/libdw/memory-access.h
@@ -72,13 +72,14 @@ __libdw_max_len_sleb128 (const unsigned char *addr, const unsigned char *end)
 static inline uint64_t
 __libdw_get_uleb128 (const unsigned char **addrp, const unsigned char *end)
 {
+  const size_t max = __libdw_max_len_uleb128 (*addrp, end);
   uint64_t acc = 0;
 
   /* Unroll the first step to help the compiler optimize
      for the common single-byte case.  */
-  get_uleb128_step (acc, *addrp, 0);
+  if (likely (max > 0))
+    get_uleb128_step (acc, *addrp, 0);
 
-  const size_t max = __libdw_max_len_uleb128 (*addrp - 1, end);
   for (size_t i = 1; i < max; ++i)
     get_uleb128_step (acc, *addrp, i);
   /* Other implementations set VALUE to UINT_MAX in this
@@ -124,6 +125,7 @@ __libdw_get_uleb128_unchecked (const unsigned char **addrp)
 static inline int64_t
 __libdw_get_sleb128 (const unsigned char **addrp, const unsigned char *end)
 {
+  const size_t max = __libdw_max_len_sleb128 (*addrp, end);
   /* Do the work in an unsigned type, but use implementation-defined
      behavior to cast to signed on return.  This avoids some undefined
      behavior when shifting.  */
@@ -131,9 +133,9 @@ __libdw_get_sleb128 (const unsigned char **addrp, const unsigned char *end)
 
   /* Unroll the first step to help the compiler optimize
      for the common single-byte case.  */
-  get_sleb128_step (acc, *addrp, 0);
+  if (likely (max > 0))
+    get_sleb128_step (acc, *addrp, 0);
 
-  const size_t max = __libdw_max_len_sleb128 (*addrp - 1, end);
   for (size_t i = 1; i < max; ++i)
     get_sleb128_step (acc, *addrp, i);
   if (*addrp == end)
diff --git a/tests/leb128.c b/tests/leb128.c
index 47b57c0d..03090d80 100644
--- a/tests/leb128.c
+++ b/tests/leb128.c
@@ -117,6 +117,19 @@ test_sleb (void)
   return OK;
 }
 
+static int
+test_sleb_safety (void)
+{
+  const int64_t expected_error = INT64_MAX;
+  int64_t value;
+  const unsigned char *test = NULL;
+  get_sleb128 (value, test, test);
+  if (value != expected_error)
+    return FAIL;
+
+  return OK;
+}
+
 static int
 test_one_uleb (const unsigned char *data, size_t len, uint64_t expect)
 {
@@ -166,8 +179,22 @@ test_uleb (void)
   return OK;
 }
 
+static int
+test_uleb_safety (void)
+{
+  const uint64_t expected_error = UINT64_MAX;
+  uint64_t value;
+  const unsigned char *test = NULL;
+  get_uleb128 (value, test, test);
+  if (value != expected_error)
+    return FAIL;
+
+  return OK;
+}
+
 int
 main (void)
 {
-  return test_sleb () || test_uleb ();
+  return test_sleb () || test_sleb_safety () || test_uleb ()
+	 || test_uleb_safety ();
 }
-- 
2.39.1.405.gd4c25cc71f-goog

Re: [PATCH] libdw: check memory access in get_(u|s)leb128

[Mark Wielaard]

Hi Aleksei,

On Wed, Jan 25, 2023 at 04:05:30PM +0000, Aleksei Vetrov via Elfutils-devel wrote:
> From: Aleksei Vetrov <vvvvvv@google.com>
> 
> __libdw_get_uleb128 and __libdw_get_sleb128 should check if addrp has
> already reached the end before unrolling the first step. It is done by
> moving __libdw_max_len to the beginning of the function, which already
> has all the checks.

I understand why you might want to add these extra safeguards. But
when the bounds checking and unrolling for get_uleb128/get_sleb128 was
introduced the idea was that they should only be called with addrp <
endp. Precisely so at least one byte could be read without needing to
bounds check.

See the following commits:

commit 7a053473c7bedd22e3db39c444a4cd8f97eace25
Author: Mark Wielaard <mjw@redhat.com>
Date:   Sun Dec 14 21:48:23 2014 +0100

    libdw: Add get_uleb128 and get_sleb128 bounds checking.
    
    Both get_uleb128 and get_sleb128 now take an end pointer to prevent
    reading too much data. Adjust all callers to provide the end pointer.
    
    There are still two exceptions. "Raw" dwarf_getabbrevattr and
    read_encoded_valued don't have a end pointer associated yet.
    They will have to be provided in the future.
    
    Signed-off-by: Mark Wielaard <mjw@redhat.com>

commit 54662f13d14d59d44943543c48bdb21d50dd008d
Author: Josh Stone <jistone@redhat.com>
Date:   Mon Dec 15 12:18:25 2014 -0800

    libdw: pre-compute leb128 loop limits
    
    Signed-off-by: Josh Stone <jistone@redhat.com>

commit 1b5477ddf360af0f6262c6f15a590448b4e1a65a
Author: Mark Wielaard <mjw@redhat.com>
Date:   Tue Dec 16 10:53:22 2014 +0100

    libdw: Unroll the first get_sleb128 step to help the compiler optimize.
    
    The common case is a single-byte. So no extra (max len) calculation is
    necessary then.
    
    Signed-off-by: Mark Wielaard <mjw@redhat.com>

Now this was 8 years ago and might have been too optimistic. Maybe we
missed some checks? Did you actually find situations where these
functions were called with addrp >= endp?

It turns out that get_[su]leb128 dominates some operations and really
does have to be as fast as possible. So I do like to know what the
impact is of this change.

Thanks,

Mark

Re: [PATCH] libdw: check memory access in get_(u|s)leb128

[Aleksei Vetrov]

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

Hi Mark,

> Did you actually find situations where these functions were called with
addrp
> >= endp?

Yes, for example libdw/libdw_form.c:91:7.

> It turns out that get_[su]leb128 dominates some operations and really does
> have to be as fast as possible. So I do like to know what the impact is of
> this change.

This patch just moves __libdw_max_len_uleb128 to the beginning of the
function
and adds only one new if. So hopefully it shouldn't affect performance at
all.

Re: [PATCH] libdw: check memory access in get_(u|s)leb128

[Mark Wielaard]

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

Hi Aleksei,

On Tue, 2023-02-07 at 16:17 +0000, Aleksei Vetrov wrote:
> > Did you actually find situations where these functions were called
> > with addrp
> > > = endp?
> 
> Yes, for example libdw/libdw_form.c:91:7.
> 

Urgh. There are actually 3 places in that function that need a guard.
Then I started reviewing all the library code and came up with more
than 10 other places that had a guard missing (see attached). I'll
clean this up and also audit elflint.c and readelf.c and submit a
proper patch for that.

> > It turns out that get_[su]leb128 dominates some operations and really does
> > have to be as fast as possible. So I do like to know what the impact is of
> > this change.
> 
> This patch just moves __libdw_max_len_uleb128 to the beginning of the function
> and adds only one new if. So hopefully it shouldn't affect performance at all.

Yeah. At first I thought it might be unnecessary because we already
have this check in the calling code. But given that I quickly found 10+
places were that wasn't true I don't feel very confident about that
now...

Then I thought maybe we can just remove the calling code checks and
simply always check like you are proposing. But the checks are slightly
different. The caller guards signal bad data errors, while yours are
hardening checks that make sure no invalid data is read. It is better
to have both. Even if it might slow down the code.

I'll finish the audit of readelf.c and elflint.c and see if adding both
those checks and your hardening checks don't pessimize the code too
much. Hopefully it won't and we can just add all the extra checks.

Cheers,

Mark

[-- Attachment #2: get-leb128-guard.patch --]
[-- Type: text/x-patch, Size: 5655 bytes --]

diff --git a/libdw/cfi.c b/libdw/cfi.c
index 6d08ca90..a7174405 100644
--- a/libdw/cfi.c
+++ b/libdw/cfi.c
@@ -239,6 +239,7 @@ execute_cfi (Dwarf_CFI *cache,
 
 	case DW_CFA_offset_extended_sf:
 	  get_uleb128 (operand, program, end);
+	  cfi_assert (program < end);
 	  get_sleb128 (sf_offset, program, end);
 	offset_extended_sf:
 	  offset = sf_offset * cie->data_alignment_factor;
@@ -294,6 +295,7 @@ execute_cfi (Dwarf_CFI *cache,
 	  get_uleb128 (regno, program, end);
 	  /* DW_FORM_block is a ULEB128 length followed by that many bytes.  */
 	  offset = program - (const uint8_t *) cache->data->d.d_buf;
+	  cfi_assert (program < end);
 	  get_uleb128 (operand, program, end);
 	  cfi_assert (operand <= (Dwarf_Word) (end - program));
 	  program += operand;
diff --git a/libdw/dwarf_child.c b/libdw/dwarf_child.c
index c8c8bb61..96a0d608 100644
--- a/libdw/dwarf_child.c
+++ b/libdw/dwarf_child.c
@@ -73,10 +73,13 @@ __libdw_find_attr (Dwarf_Die *die, unsigned int search_name,
 
       if (attr_form == DW_FORM_indirect)
 	{
+	  if (readp >= endp)
+	    goto invalid;
 	  get_uleb128 (attr_form, readp, endp);
 	  if (attr_form == DW_FORM_indirect ||
 	      attr_form == DW_FORM_implicit_const)
 	    {
+	    invalid:
 	      __libdw_seterrno (DWARF_E_INVALID_DWARF);
 	      return NULL;
 	    }
diff --git a/libdw/dwarf_frame_register.c b/libdw/dwarf_frame_register.c
index bcf3fa03..a6b7c4c1 100644
--- a/libdw/dwarf_frame_register.c
+++ b/libdw/dwarf_frame_register.c
@@ -100,6 +100,11 @@ dwarf_frame_register (Dwarf_Frame *fs, int regno, Dwarf_Op ops_mem[3],
 	const uint8_t *p = fs->cache->data->d.d_buf + reg->value;
 	const uint8_t *end = (fs->cache->data->d.d_buf
 			      + fs->cache->data->d.d_size);
+	if (p >= end)
+	  {
+	    __libdw_seterrno (DWARF_E_INVALID_DWARF);
+	    return -1;
+	  }
 	get_uleb128 (block.length, p, end);
 	block.data = (void *) p;
 
diff --git a/libdw/dwarf_getabbrev.c b/libdw/dwarf_getabbrev.c
index 13bee493..5b02333f 100644
--- a/libdw/dwarf_getabbrev.c
+++ b/libdw/dwarf_getabbrev.c
@@ -77,6 +77,7 @@ __libdw_getabbrev (Dwarf *dbg, struct Dwarf_CU *cu, Dwarf_Off offset,
 			      + dbg->sectiondata[IDX_debug_abbrev]->d_size);
   const unsigned char *start_abbrevp = abbrevp;
   unsigned int code;
+  // We start off with abbrevp at offset, which is checked above.
   get_uleb128 (code, abbrevp, end);
 
   /* Check whether this code is already in the hash table.  */
diff --git a/libdw/dwarf_getlocation.c b/libdw/dwarf_getlocation.c
index d0d78163..4e8c047b 100644
--- a/libdw/dwarf_getlocation.c
+++ b/libdw/dwarf_getlocation.c
@@ -545,7 +545,7 @@ __libdw_intern_expression (Dwarf *dbg, bool other_byte_order,
 	case DW_OP_deref_type:
 	case DW_OP_GNU_deref_type:
 	case DW_OP_xderef_type:
-	  if (unlikely (data + 1 >= end_data))
+	  if (unlikely (data + 2 >= end_data))
 	    goto invalid;
 	  newloc->number = *data++;
 	  get_uleb128 (newloc->number2, data, end_data);
diff --git a/libdw/dwarf_getsrclines.c b/libdw/dwarf_getsrclines.c
index 2c1d7a40..df003c5f 100644
--- a/libdw/dwarf_getsrclines.c
+++ b/libdw/dwarf_getsrclines.c
@@ -572,6 +572,8 @@ read_srclines (Dwarf *dbg,
 	goto invalid_data;
 
       size_t nfiles;
+      if ((size_t) (lineendp - linep) < 1)
+	goto invalid_data;
       get_uleb128 (nfiles, linep, lineendp);
 
       if (nforms == 0 && nfiles != 0)
diff --git a/libdw/encoded-value.h b/libdw/encoded-value.h
index d4e01924..4566ef96 100644
--- a/libdw/encoded-value.h
+++ b/libdw/encoded-value.h
@@ -196,10 +196,14 @@ read_encoded_value (const Dwarf_CFI *cache, uint8_t encoding,
       break;
 
     case DW_EH_PE_uleb128:
+      if (*p >= endp)
+	goto invalid_data;
       get_uleb128 (value, *p, endp);
       break;
 
     case DW_EH_PE_sleb128:
+      if (*p >= endp)
+	goto invalid_data;
       get_sleb128 (value, *p, endp);
       break;
 
diff --git a/libdw/fde.c b/libdw/fde.c
index f5f6fbe1..73d551b6 100644
--- a/libdw/fde.c
+++ b/libdw/fde.c
@@ -104,9 +104,12 @@ intern_fde (Dwarf_CFI *cache, const Dwarf_FDE *entry)
       /* The CIE augmentation says the FDE has a DW_FORM_block
 	 before its actual instruction stream.  */
       Dwarf_Word len;
+      if (fde->instructions >= fde->instructions_end)
+	goto invalid;
       get_uleb128 (len, fde->instructions, fde->instructions_end);
       if ((Dwarf_Word) (fde->instructions_end - fde->instructions) < len)
 	{
+	invalid:
 	  free (fde);
 	  __libdw_seterrno (DWARF_E_INVALID_DWARF);
 	  return NULL;
diff --git a/libdw/libdw_form.c b/libdw/libdw_form.c
index c83dfb39..40045440 100644
--- a/libdw/libdw_form.c
+++ b/libdw/libdw_form.c
@@ -88,6 +88,8 @@ __libdw_form_val_compute_len (struct Dwarf_CU *cu, unsigned int form,
 
     case DW_FORM_block:
     case DW_FORM_exprloc:
+      if (valp >= endp)
+       goto invalid;
       get_uleb128 (u128, valp, endp);
       result = u128 + (valp - startp);
       break;
@@ -111,6 +113,8 @@ __libdw_form_val_compute_len (struct Dwarf_CU *cu, unsigned int form,
     case DW_FORM_strx:
     case DW_FORM_GNU_addr_index:
     case DW_FORM_GNU_str_index:
+      if (valp >= endp)
+       goto invalid;
       get_uleb128 (u128, valp, endp);
       result = valp - startp;
       break;
@@ -119,6 +123,8 @@ __libdw_form_val_compute_len (struct Dwarf_CU *cu, unsigned int form,
       /* The amount of data to skip in the DIE is the size of the actual
 	 FORM data (which is __libdw_form_val_len) plus the size of the
 	 uleb128 encoding that FORM (which is valp - startp).  */
+      if (valp >= endp)
+	goto invalid;
       get_uleb128 (u128, valp, endp);
       if (*valp == DW_FORM_indirect || *valp == DW_FORM_implicit_const)
 	return (size_t) -1;

Re: [PATCH] libdw: check memory access in get_(u|s)leb128

[Mark Wielaard]

Hi Aleksei,

On Wed, Jan 25, 2023 at 04:05:30PM +0000, Aleksei Vetrov via Elfutils-devel wrote:
> From: Aleksei Vetrov <vvvvvv@google.com>
> 
> __libdw_get_uleb128 and __libdw_get_sleb128 should check if addrp has
> already reached the end before unrolling the first step. It is done by
> moving __libdw_max_len to the beginning of the function, which already
> has all the checks.

I did some performance tests and couldn't find any significant change.
Even with my other extra checks added in libdw and readelf.

One question about the sleb128 case though:

>  static inline int64_t
>  __libdw_get_sleb128 (const unsigned char **addrp, const unsigned char *end)
>  {
> +  const size_t max = __libdw_max_len_sleb128 (*addrp, end);
>    /* Do the work in an unsigned type, but use implementation-defined
>       behavior to cast to signed on return.  This avoids some undefined
>       behavior when shifting.  */
> @@ -131,9 +133,9 @@ __libdw_get_sleb128 (const unsigned char **addrp, const unsigned char *end)
>  
>    /* Unroll the first step to help the compiler optimize
>       for the common single-byte case.  */
> -  get_sleb128_step (acc, *addrp, 0);
> +  if (likely (max > 0))
> +    get_sleb128_step (acc, *addrp, 0);
>  
> -  const size_t max = __libdw_max_len_sleb128 (*addrp - 1, end);
>    for (size_t i = 1; i < max; ++i)
>      get_sleb128_step (acc, *addrp, i);
>    if (*addrp == end)

But what about the case where *addrp > end?
After this code we will do:

  /* There might be one extra byte.  */
  unsigned char b = **addrp;
  ++*addrp;

So I think we want to catch that too.  Easiest imho seems to move (and
invert) the max check immediately after calculating max:

diff --git a/libdw/memory-access.h b/libdw/memory-access.h
index 1cac6af3..72348623 100644
--- a/libdw/memory-access.h
+++ b/libdw/memory-access.h
@@ -126,6 +126,9 @@ static inline int64_t
 __libdw_get_sleb128 (const unsigned char **addrp, const unsigned char *end)
 {
   const size_t max = __libdw_max_len_sleb128 (*addrp, end);
+  if (unlikely (max == 0))
+    return INT64_MAX;
+
   /* Do the work in an unsigned type, but use implementation-defined
      behavior to cast to signed on return.  This avoids some undefined
      behavior when shifting.  */
@@ -133,8 +136,7 @@ __libdw_get_sleb128 (const unsigned char **addrp, const unsigned char *end)
 
   /* Unroll the first step to help the compiler optimize
      for the common single-byte case.  */
-  if (likely (max > 0))
-    get_sleb128_step (acc, *addrp, 0);
+  get_sleb128_step (acc, *addrp, 0);
 
   for (size_t i = 1; i < max; ++i)
     get_sleb128_step (acc, *addrp, i);

Cheers,

Mark

Re: [PATCH] libdw: check memory access in get_(u|s)leb128

[Aleksei Vetrov]

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

Hi Mark,

On Sat, Feb 11, 2023 at 11:43 PM Mark Wielaard <mark@klomp.org> wrote:
> After this code we will do:
>
>   /* There might be one extra byte.  */
>   unsigned char b = **addrp;
>   ++*addrp;
>
> So I think we want to catch that too.  Easiest imho seems to move (and
> invert) the max check immediately after calculating max.

Thanks for finding this! Sounds good and I'm going to do this also in
uleb128 for consistency. Sending updated patch in reply.

[PATCH v2] libdw: check memory access in get_(u|s)leb128

[vvvvvv]

From: Aleksei Vetrov <vvvvvv@google.com>

__libdw_get_uleb128 and __libdw_get_sleb128 should check if addrp has
already reached the end before unrolling the first step. It is done by
moving __libdw_max_len to the beginning of the function, which can
notice, that addrp is beyond the end. Then we just check the result of
this function.

Signed-off-by: Aleksei Vetrov <vvvvvv@google.com>
---
 libdw/memory-access.h | 10 ++++++++--
 tests/leb128.c        | 29 ++++++++++++++++++++++++++++-
 2 files changed, 36 insertions(+), 3 deletions(-)

diff --git a/libdw/memory-access.h b/libdw/memory-access.h
index fca4129a..6d79343c 100644
--- a/libdw/memory-access.h
+++ b/libdw/memory-access.h
@@ -72,13 +72,16 @@ __libdw_max_len_sleb128 (const unsigned char *addr, const unsigned char *end)
 static inline uint64_t
 __libdw_get_uleb128 (const unsigned char **addrp, const unsigned char *end)
 {
+  const size_t max = __libdw_max_len_uleb128 (*addrp, end);
+  if (unlikely (max == 0))
+    return UINT64_MAX;
+
   uint64_t acc = 0;
 
   /* Unroll the first step to help the compiler optimize
      for the common single-byte case.  */
   get_uleb128_step (acc, *addrp, 0);
 
-  const size_t max = __libdw_max_len_uleb128 (*addrp - 1, end);
   for (size_t i = 1; i < max; ++i)
     get_uleb128_step (acc, *addrp, i);
   /* Other implementations set VALUE to UINT_MAX in this
@@ -124,6 +127,10 @@ __libdw_get_uleb128_unchecked (const unsigned char **addrp)
 static inline int64_t
 __libdw_get_sleb128 (const unsigned char **addrp, const unsigned char *end)
 {
+  const size_t max = __libdw_max_len_sleb128 (*addrp, end);
+  if (unlikely (max == 0))
+    return INT64_MAX;
+
   /* Do the work in an unsigned type, but use implementation-defined
      behavior to cast to signed on return.  This avoids some undefined
      behavior when shifting.  */
@@ -133,7 +140,6 @@ __libdw_get_sleb128 (const unsigned char **addrp, const unsigned char *end)
      for the common single-byte case.  */
   get_sleb128_step (acc, *addrp, 0);
 
-  const size_t max = __libdw_max_len_sleb128 (*addrp - 1, end);
   for (size_t i = 1; i < max; ++i)
     get_sleb128_step (acc, *addrp, i);
   if (*addrp == end)
diff --git a/tests/leb128.c b/tests/leb128.c
index 47b57c0d..03090d80 100644
--- a/tests/leb128.c
+++ b/tests/leb128.c
@@ -117,6 +117,19 @@ test_sleb (void)
   return OK;
 }
 
+static int
+test_sleb_safety (void)
+{
+  const int64_t expected_error = INT64_MAX;
+  int64_t value;
+  const unsigned char *test = NULL;
+  get_sleb128 (value, test, test);
+  if (value != expected_error)
+    return FAIL;
+
+  return OK;
+}
+
 static int
 test_one_uleb (const unsigned char *data, size_t len, uint64_t expect)
 {
@@ -166,8 +179,22 @@ test_uleb (void)
   return OK;
 }
 
+static int
+test_uleb_safety (void)
+{
+  const uint64_t expected_error = UINT64_MAX;
+  uint64_t value;
+  const unsigned char *test = NULL;
+  get_uleb128 (value, test, test);
+  if (value != expected_error)
+    return FAIL;
+
+  return OK;
+}
+
 int
 main (void)
 {
-  return test_sleb () || test_uleb ();
+  return test_sleb () || test_sleb_safety () || test_uleb ()
+	 || test_uleb_safety ();
 }
-- 
2.39.1.581.gbfd45094c4-goog

Re: [PATCH v2] libdw: check memory access in get_(u|s)leb128

[Mark Wielaard]

Hi Aleksei,

On Mon, 2023-02-13 at 20:10 +0000, Aleksei Vetrov via Elfutils-devel
wrote:
> __libdw_get_uleb128 and __libdw_get_sleb128 should check if addrp has
> already reached the end before unrolling the first step. It is done by
> moving __libdw_max_len to the beginning of the function, which can
> notice, that addrp is beyond the end. Then we just check the result of
> this function.

This looks good. And I couldn't measure any meaningful performance
difference. Pushed.

Even though this now catches all calls that have start >= end, I'll
also push my other patch to add extra guards in the callers of
get_(u|s)leb128, because that does provide us with better error
messages.

Thanks,

Mark