[PATCH v2 1/2] libfdt: prevent integer overflow in fdt_next_tag

[PATCH v2 1/2] libfdt: prevent integer overflow in fdt_next_tag

[Tadeusz Struk]

Since fdt_next_tag() in a public API function all input parameters,
including the fdt blob should not be trusted. It is possible to forge
a blob with invalid property length that will cause integer overflow
during offset calculation. To prevent that, validate the property length
read from the blob before doing calculations.

Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
--
v2:
* Use len local variable to avoid multiple calls to fdt32_to_cpu(*lenp)
* Add can_assume(VALID_DTB) to the new checks
---
 libfdt/fdt.c | 18 +++++++++++++-----
 1 file changed, 13 insertions(+), 5 deletions(-)

diff --git a/libfdt/fdt.c b/libfdt/fdt.c
index 90a39e8..b7c202a 100644
--- a/libfdt/fdt.c
+++ b/libfdt/fdt.c
@@ -162,7 +162,7 @@ const void *fdt_offset_ptr(const void *fdt, int offset, unsigned int len)
 uint32_t fdt_next_tag(const void *fdt, int startoffset, int *nextoffset)
 {
 	const fdt32_t *tagp, *lenp;
-	uint32_t tag;
+	uint32_t tag, len;
 	int offset = startoffset;
 	const char *p;
 
@@ -188,12 +188,20 @@ uint32_t fdt_next_tag(const void *fdt, int startoffset, int *nextoffset)
 		lenp = fdt_offset_ptr(fdt, offset, sizeof(*lenp));
 		if (!can_assume(VALID_DTB) && !lenp)
 			return FDT_END; /* premature end */
+
+		len = fdt32_to_cpu(*lenp);
+		if (!can_assume(VALID_DTB) && INT_MAX <= len)
+			return FDT_END; /* premature end */
+
 		/* skip-name offset, length and value */
-		offset += sizeof(struct fdt_property) - FDT_TAGSIZE
-			+ fdt32_to_cpu(*lenp);
+		offset += sizeof(struct fdt_property) - FDT_TAGSIZE + len;
+
+		if (!can_assume(VALID_DTB) && offset < 0)
+			return FDT_END; /* premature end */
+
 		if (!can_assume(LATEST) &&
-		    fdt_version(fdt) < 0x10 && fdt32_to_cpu(*lenp) >= 8 &&
-		    ((offset - fdt32_to_cpu(*lenp)) % 8) != 0)
+		    fdt_version(fdt) < 0x10 && len >= 8 &&
+		    ((offset - len) % 8) != 0)
 			offset += 4;
 		break;
 
-- 
2.37.3

[PATCH v2 2/2] libfdt: tests: add get_next_tag_invalid_prop_len

[Tadeusz Struk]

Add a new test get_next_tag_invalid_prop_len, which covers
fdt_next_tag(), when it is passed an corrupted blob, with
invalid property len values.

Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
---
 tests/.gitignore                      |  1 +
 tests/Makefile.tests                  |  2 +-
 tests/get_next_tag_invalid_prop_len.c | 65 +++++++++++++++++++++++++++
 tests/meson.build                     |  1 +
 tests/run_tests.sh                    |  1 +
 5 files changed, 69 insertions(+), 1 deletion(-)
 create mode 100644 tests/get_next_tag_invalid_prop_len.c

diff --git a/tests/.gitignore b/tests/.gitignore
index 03bdde2..3376ed9 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -74,3 +74,4 @@ tmp.*
 /truncated_memrsv
 /utilfdt_test
 /value-labels
+/get_next_tag_invalid_prop_len
diff --git a/tests/Makefile.tests b/tests/Makefile.tests
index 2d36c5d..2c5b4c9 100644
--- a/tests/Makefile.tests
+++ b/tests/Makefile.tests
@@ -4,7 +4,7 @@ LIB_TESTS_L = get_mem_rsv \
 	get_path supernode_atdepth_offset parent_offset \
 	node_offset_by_prop_value node_offset_by_phandle \
 	node_check_compatible node_offset_by_compatible \
-	get_alias \
+	get_alias get_next_tag_invalid_prop_len \
 	char_literal \
 	sized_cells \
 	notfound \
diff --git a/tests/get_next_tag_invalid_prop_len.c b/tests/get_next_tag_invalid_prop_len.c
new file mode 100644
index 0000000..c02f6a3
--- /dev/null
+++ b/tests/get_next_tag_invalid_prop_len.c
@@ -0,0 +1,65 @@
+// SPDX-License-Identifier: LGPL-2.1-or-later
+/*
+ * libfdt - Flat Device Tree manipulation
+ *	Testcase for fdt_next_tag()
+ */
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <stdint.h>
+
+#include <libfdt.h>
+#include "tests.h"
+#include "testdata.h"
+
+int main(int argc, char *argv[])
+{
+	struct fdt_header *hdr;
+	struct fdt_property *prp;
+	void *fdt;
+	int size, nextoff = 0;
+	uint32_t tag;
+
+	test_init(argc, argv);
+	size = sizeof(*hdr) + sizeof(*prp) + 256;
+	fdt = calloc(1, size);
+	if (!fdt)
+		FAIL("Can't allocate memory");
+
+	hdr = fdt;
+	prp = (struct fdt_property *)(((char *) fdt) + sizeof(*hdr));
+	fdt_set_magic(fdt, FDT_MAGIC);
+	fdt_set_totalsize(fdt, size);
+	fdt_set_version(fdt, 0x10);
+	prp->tag = cpu_to_fdt32(FDT_PROP);
+	prp->len = cpu_to_fdt32(256);
+	prp->nameoff = 0;
+
+	tag = fdt_next_tag(fdt, sizeof(*hdr), &nextoff);
+	if (tag != FDT_PROP)
+		FAIL("Invalid tag %X", tag);
+
+	if (nextoff != size)
+		FAIL("Invalid next_offset");
+
+	/* int overflow case */
+	prp->len = cpu_to_fdt32(0xFFFFFFFA);
+	tag = fdt_next_tag(fdt, sizeof(*hdr), &nextoff);
+	if (tag != FDT_END)
+		FAIL("Invalid tag, expected premature end");
+
+	if (nextoff != -FDT_ERR_BADSTRUCTURE)
+		FAIL("Invalid nextoff, expected error FDT_ERR_BADSTRUCTURE");
+
+	/* negative offset case */
+	prp->len = cpu_to_fdt32(0x7FFFFFFA);
+	tag = fdt_next_tag(fdt, sizeof(*hdr), &nextoff);
+	if (tag != FDT_END)
+		FAIL("Invalid tag, expected premature end");
+
+	if (nextoff != -FDT_ERR_BADSTRUCTURE)
+		FAIL("Invalid nextoff, expected error FDT_ERR_BADSTRUCTURE");
+
+	free(fdt);
+	PASS();
+}
diff --git a/tests/meson.build b/tests/meson.build
index 4ac154a..29a42dd 100644
--- a/tests/meson.build
+++ b/tests/meson.build
@@ -47,6 +47,7 @@ tests = [
   'get_path',
   'get_phandle',
   'get_prop_offset',
+  'get_next_tag_invalid_prop_len',
   'getprop',
   'incbin',
   'integer-expressions',
diff --git a/tests/run_tests.sh b/tests/run_tests.sh
index 244df8a..397b9cf 100755
--- a/tests/run_tests.sh
+++ b/tests/run_tests.sh
@@ -346,6 +346,7 @@ tree1_tests () {
     run_test get_prop_offset $TREE
     run_test get_phandle $TREE
     run_test get_path $TREE
+    run_test get_next_tag_invalid_prop_len $TREE #TREE not really needed
     run_test supernode_atdepth_offset $TREE
     run_test parent_offset $TREE
     run_test node_offset_by_prop_value $TREE
-- 
2.37.3

Re: [PATCH v2 1/2] libfdt: prevent integer overflow in fdt_next_tag

[David Gibson]

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

On Fri, Sep 30, 2022 at 08:20:03AM -0700, Tadeusz Struk wrote:
> Since fdt_next_tag() in a public API function all input parameters,
> including the fdt blob should not be trusted. It is possible to forge
> a blob with invalid property length that will cause integer overflow
> during offset calculation. To prevent that, validate the property length
> read from the blob before doing calculations.

So.. yes, there can be an integer overflow here.  I think the actual
damage it can cause is strongly mitigated by the fact that we should
only ever use the result of that overflow via fdt_offset_ptr(), which
will safely reject a bad offset.

> Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>

> v2:
> * Use len local variable to avoid multiple calls to fdt32_to_cpu(*lenp)
> * Add can_assume(VALID_DTB) to the new checks

>  libfdt/fdt.c | 18 +++++++++++++-----
>  1 file changed, 13 insertions(+), 5 deletions(-)
> 
> diff --git a/libfdt/fdt.c b/libfdt/fdt.c
> index 90a39e8..b7c202a 100644
> --- a/libfdt/fdt.c
> +++ b/libfdt/fdt.c
> @@ -162,7 +162,7 @@ const void *fdt_offset_ptr(const void *fdt, int offset, unsigned int len)
>  uint32_t fdt_next_tag(const void *fdt, int startoffset, int *nextoffset)
>  {
>  	const fdt32_t *tagp, *lenp;
> -	uint32_t tag;
> +	uint32_t tag, len;
>  	int offset = startoffset;
>  	const char *p;
>  
> @@ -188,12 +188,20 @@ uint32_t fdt_next_tag(const void *fdt, int startoffset, int *nextoffset)
>  		lenp = fdt_offset_ptr(fdt, offset, sizeof(*lenp));
>  		if (!can_assume(VALID_DTB) && !lenp)
>  			return FDT_END; /* premature end */
> +
> +		len = fdt32_to_cpu(*lenp);
> +		if (!can_assume(VALID_DTB) && INT_MAX <= len)

This check is redundant with the one below, isn't it?

> +			return FDT_END; /* premature end */
> +
>  		/* skip-name offset, length and value */
> -		offset += sizeof(struct fdt_property) - FDT_TAGSIZE
> -			+ fdt32_to_cpu(*lenp);
> +		offset += sizeof(struct fdt_property) - FDT_TAGSIZE + len;
> +
> +		if (!can_assume(VALID_DTB) && offset < 0)
> +			return FDT_END; /* premature end */

Hmmm.. so, signed integer overflow is actually undefined behaviour in
C, so checking for offset < 0 after the addition isn't actually a safe
way to check for overflow.  To safely check for overflow, I believe
you need to check that the *unsigned* sum of offset and len is greater
than or equal to offset (*unsigned* integer overflow is defined to
wrap as you'd expect for 2s complement arithmetic).  Actually given
the constraints we've put on offsets in general, we need to check that
that unsigned sum is both greater than offset and less than INT_MAX.

>  		if (!can_assume(LATEST) &&
> -		    fdt_version(fdt) < 0x10 && fdt32_to_cpu(*lenp) >= 8 &&
> -		    ((offset - fdt32_to_cpu(*lenp)) % 8) != 0)
> +		    fdt_version(fdt) < 0x10 && len >= 8 &&
> +		    ((offset - len) % 8) != 0)
>  			offset += 4;
>  		break;

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v2 2/2] libfdt: tests: add get_next_tag_invalid_prop_len

[David Gibson]

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

On Fri, Sep 30, 2022 at 08:20:04AM -0700, Tadeusz Struk wrote:
> Add a new test get_next_tag_invalid_prop_len, which covers
> fdt_next_tag(), when it is passed an corrupted blob, with
> invalid property len values.
> 
> Signed-off-by: Tadeusz Struk <tadeusz.struk@linaro.org>
> ---
>  tests/.gitignore                      |  1 +
>  tests/Makefile.tests                  |  2 +-
>  tests/get_next_tag_invalid_prop_len.c | 65 +++++++++++++++++++++++++++
>  tests/meson.build                     |  1 +
>  tests/run_tests.sh                    |  1 +
>  5 files changed, 69 insertions(+), 1 deletion(-)
>  create mode 100644 tests/get_next_tag_invalid_prop_len.c
> 
> diff --git a/tests/.gitignore b/tests/.gitignore
> index 03bdde2..3376ed9 100644
> --- a/tests/.gitignore
> +++ b/tests/.gitignore
> @@ -74,3 +74,4 @@ tmp.*
>  /truncated_memrsv
>  /utilfdt_test
>  /value-labels
> +/get_next_tag_invalid_prop_len
> diff --git a/tests/Makefile.tests b/tests/Makefile.tests
> index 2d36c5d..2c5b4c9 100644
> --- a/tests/Makefile.tests
> +++ b/tests/Makefile.tests
> @@ -4,7 +4,7 @@ LIB_TESTS_L = get_mem_rsv \
>  	get_path supernode_atdepth_offset parent_offset \
>  	node_offset_by_prop_value node_offset_by_phandle \
>  	node_check_compatible node_offset_by_compatible \
> -	get_alias \
> +	get_alias get_next_tag_invalid_prop_len \
>  	char_literal \
>  	sized_cells \
>  	notfound \
> diff --git a/tests/get_next_tag_invalid_prop_len.c b/tests/get_next_tag_invalid_prop_len.c
> new file mode 100644
> index 0000000..c02f6a3
> --- /dev/null
> +++ b/tests/get_next_tag_invalid_prop_len.c
> @@ -0,0 +1,65 @@
> +// SPDX-License-Identifier: LGPL-2.1-or-later
> +/*
> + * libfdt - Flat Device Tree manipulation
> + *	Testcase for fdt_next_tag()
> + */
> +#include <stdlib.h>
> +#include <stdio.h>
> +#include <string.h>
> +#include <stdint.h>
> +
> +#include <libfdt.h>
> +#include "tests.h"
> +#include "testdata.h"
> +
> +int main(int argc, char *argv[])
> +{
> +	struct fdt_header *hdr;
> +	struct fdt_property *prp;
> +	void *fdt;
> +	int size, nextoff = 0;
> +	uint32_t tag;
> +
> +	test_init(argc, argv);
> +	size = sizeof(*hdr) + sizeof(*prp) + 256;
> +	fdt = calloc(1, size);
> +	if (!fdt)
> +		FAIL("Can't allocate memory");
> +
> +	hdr = fdt;
> +	prp = (struct fdt_property *)(((char *) fdt) + sizeof(*hdr));
> +	fdt_set_magic(fdt, FDT_MAGIC);
> +	fdt_set_totalsize(fdt, size);
> +	fdt_set_version(fdt, 0x10);
> +	prp->tag = cpu_to_fdt32(FDT_PROP);
> +	prp->len = cpu_to_fdt32(256);
> +	prp->nameoff = 0;

The dtb you're constructing here isn't a valid dtb, even before you
corrupt the property lengths: it doesn't have valid offsets to the
blocks, and you have no BEGIN_NODE tag for the root node.  That means
that in order to test the specific thing you want to test, you're
relying on *very* detailed knowledge of exactly how the code under
test works and what it does and doesn't check, which makes the test
unnecessarily fragile.

I'd really suggest building the initial tree with the fdt_sw functions
- or even more declaratively in trees.S - before corrupting it to test
the actual overflow condition.

> +	tag = fdt_next_tag(fdt, sizeof(*hdr), &nextoff);
> +	if (tag != FDT_PROP)
> +		FAIL("Invalid tag %X", tag);
> +
> +	if (nextoff != size)
> +		FAIL("Invalid next_offset");
> +
> +	/* int overflow case */
> +	prp->len = cpu_to_fdt32(0xFFFFFFFA);
> +	tag = fdt_next_tag(fdt, sizeof(*hdr), &nextoff);
> +	if (tag != FDT_END)
> +		FAIL("Invalid tag, expected premature end");
> +
> +	if (nextoff != -FDT_ERR_BADSTRUCTURE)
> +		FAIL("Invalid nextoff, expected error FDT_ERR_BADSTRUCTURE");
> +
> +	/* negative offset case */

Is there actually any meaningful difference between the "int overflow"
and "negative offset" cases?

> +	prp->len = cpu_to_fdt32(0x7FFFFFFA);
> +	tag = fdt_next_tag(fdt, sizeof(*hdr), &nextoff);
> +	if (tag != FDT_END)
> +		FAIL("Invalid tag, expected premature end");


> +	if (nextoff != -FDT_ERR_BADSTRUCTURE)
> +		FAIL("Invalid nextoff, expected error FDT_ERR_BADSTRUCTURE");
> +
> +	free(fdt);
> +	PASS();
> +}
> diff --git a/tests/meson.build b/tests/meson.build
> index 4ac154a..29a42dd 100644
> --- a/tests/meson.build
> +++ b/tests/meson.build
> @@ -47,6 +47,7 @@ tests = [
>    'get_path',
>    'get_phandle',
>    'get_prop_offset',
> +  'get_next_tag_invalid_prop_len',
>    'getprop',
>    'incbin',
>    'integer-expressions',
> diff --git a/tests/run_tests.sh b/tests/run_tests.sh
> index 244df8a..397b9cf 100755
> --- a/tests/run_tests.sh
> +++ b/tests/run_tests.sh
> @@ -346,6 +346,7 @@ tree1_tests () {
>      run_test get_prop_offset $TREE
>      run_test get_phandle $TREE
>      run_test get_path $TREE
> +    run_test get_next_tag_invalid_prop_len $TREE #TREE not really needed

This doesn't belong with tree1_tests() since it has nothing to do with
test_tree1.  It should go under the "Specific bug tests" comment
instead.  Also, since you're not using a passed in tree blob, you
should modify the test code not to expect one.

>      run_test supernode_atdepth_offset $TREE
>      run_test parent_offset $TREE
>      run_test node_offset_by_prop_value $TREE

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v2 1/2] libfdt: prevent integer overflow in fdt_next_tag

[Tadeusz Struk]

Hi David,
On 10/4/22 00:06, David Gibson wrote:
> On Fri, Sep 30, 2022 at 08:20:03AM -0700, Tadeusz Struk wrote:
>> Since fdt_next_tag() in a public API function all input parameters,
>> including the fdt blob should not be trusted. It is possible to forge
>> a blob with invalid property length that will cause integer overflow
>> during offset calculation. To prevent that, validate the property length
>> read from the blob before doing calculations.
> So.. yes, there can be an integer overflow here.  I think the actual
> damage it can cause is strongly mitigated by the fact that we should
> only ever use the result of that overflow via fdt_offset_ptr(), which
> will safely reject a bad offset.
> 
>> Signed-off-by: Tadeusz Struk<tadeusz.struk@linaro.org>
>> v2:
>> * Use len local variable to avoid multiple calls to fdt32_to_cpu(*lenp)
>> * Add can_assume(VALID_DTB) to the new checks
>>   libfdt/fdt.c | 18 +++++++++++++-----
>>   1 file changed, 13 insertions(+), 5 deletions(-)
>>
>> diff --git a/libfdt/fdt.c b/libfdt/fdt.c
>> index 90a39e8..b7c202a 100644
>> --- a/libfdt/fdt.c
>> +++ b/libfdt/fdt.c
>> @@ -162,7 +162,7 @@ const void *fdt_offset_ptr(const void *fdt, int offset, unsigned int len)
>>   uint32_t fdt_next_tag(const void *fdt, int startoffset, int *nextoffset)
>>   {
>>   	const fdt32_t *tagp, *lenp;
>> -	uint32_t tag;
>> +	uint32_t tag, len;
>>   	int offset = startoffset;
>>   	const char *p;
>>   
>> @@ -188,12 +188,20 @@ uint32_t fdt_next_tag(const void *fdt, int startoffset, int *nextoffset)
>>   		lenp = fdt_offset_ptr(fdt, offset, sizeof(*lenp));
>>   		if (!can_assume(VALID_DTB) && !lenp)
>>   			return FDT_END; /* premature end */
>> +
>> +		len = fdt32_to_cpu(*lenp);
>> +		if (!can_assume(VALID_DTB) && INT_MAX <= len)
> This check is redundant with the one below, isn't it?
> 
>> +			return FDT_END; /* premature end */
>> +
>>   		/* skip-name offset, length and value */
>> -		offset += sizeof(struct fdt_property) - FDT_TAGSIZE
>> -			+ fdt32_to_cpu(*lenp);
>> +		offset += sizeof(struct fdt_property) - FDT_TAGSIZE + len;
>> +
>> +		if (!can_assume(VALID_DTB) && offset < 0)
>> +			return FDT_END; /* premature end */
> Hmmm.. so, signed integer overflow is actually undefined behaviour in
> C, so checking for offset < 0 after the addition isn't actually a safe
> way to check for overflow.  To safely check for overflow, I believe
> you need to check that the*unsigned*  sum of offset and len is greater
> than or equal to offset (*unsigned*  integer overflow is defined to
> wrap as you'd expect for 2s complement arithmetic).  Actually given
> the constraints we've put on offsets in general, we need to check that
> that unsigned sum is both greater than offset and less than INT_MAX.
  
Thanks for feedback. I will change the logic to only work on unsigned
integers. I will also update the unit tests according to your suggestions.

-- 
Thanks,
Tadeusz