Skip to contentSkip to conversation

lib/ts_bm: fix integer overflow in pattern length calculation

PATCH Superseded Josh Law 2 participants 7 messages Mar 8 Library code

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Josh Law

author
#0 lore raw

PATCH v2 1/2 lib/ts_bm: fix integer overflow in pattern length calculation

From: Josh Law <[email protected]>

The ts_bm algorithm computes the required allocation size by multiplying the pattern length by the size of an integer. If the pattern length is sufficiently large, this can overflow the 32-bit unsigned int before it is widened to size_t. This could result in an undersized allocation and a subsequent heap buffer overflow when copying the pattern.

Fix this by explicitly checking that the length does not exceed the maximum safe threshold before calculating the buffer sizes.

---
 lib/ts_bm.c | 3 +++
 1 file changed, 3 insertions(+)
lib/ts_bm.c +3 -0
index eed5967238c5..01ea0a93cf6e 100644
@@ -166,6 +166,9 @@ static struct ts_config *bm_init(const void *pattern, unsigned int len,
 	unsigned int prefix_tbl_len = len * sizeof(unsigned int);
 	size_t priv_size = sizeof(*bm) + len + prefix_tbl_len;
 
+	if (unlikely(len == 0 || len > (UINT_MAX - sizeof(*bm)) / (sizeof(unsigned int) + 1)))
+		return ERR_PTR(-EINVAL);
+
 	conf = alloc_ts_config(priv_size, gfp_mask);
 	if (IS_ERR(conf))
 		return conf;
Signature · 1 line
2.43.0
author
#1 lore raw

PATCH v2 2/2 lib/ts_kmp: fix integer overflow in pattern length calculation

From: Josh Law <[email protected]>

The ts_kmp algorithm computes the required allocation size by multiplying the pattern length by the size of an integer. If the pattern length is sufficiently large, this can overflow the 32-bit unsigned int before it is widened to size_t. This could result in an undersized allocation and a subsequent heap buffer overflow when copying the pattern.

Fix this by explicitly checking that the length does not exceed the maximum safe threshold before calculating the buffer sizes.

---
 lib/ts_kmp.c | 3 +++
 1 file changed, 3 insertions(+)
lib/ts_kmp.c +3 -0
index 5520dc28255a..e07f5e80d076 100644
@@ -97,6 +97,9 @@ static struct ts_config *kmp_init(const void *pattern, unsigned int len,
 	unsigned int prefix_tbl_len = len * sizeof(unsigned int);
 	size_t priv_size = sizeof(*kmp) + len + prefix_tbl_len;
 
+	if (unlikely(len == 0 || len > (UINT_MAX - sizeof(*kmp)) / (sizeof(unsigned int) + 1)))
+		return ERR_PTR(-EINVAL);
+
 	conf = alloc_ts_config(priv_size, gfp_mask);
 	if (IS_ERR(conf))
 		return conf;
Signature · 1 line
2.43.0
maintainer
#2 lore raw
In reply to Josh Law
Quoted 17 lines · On Sun, 8 Mar 2026 18:10:53 +0000 Josh Law <[email protected]> wrote:

From: Josh Law <[email protected]>

The ts_bm algorithm computes the required allocation size by multiplying the pattern length by the size of an integer. If the pattern length is sufficiently large, this can overflow the 32-bit unsigned int before it is widened to size_t. This could result in an undersized allocation and a subsequent heap buffer overflow when copying the pattern.

Fix this by explicitly checking that the length does not exceed the maximum safe threshold before calculating the buffer sizes.

...

lib/ts_bm.c static struct ts_config *bm_init(const void *pattern, unsigned int len, · line 167

Quoted 2 lines
lib/ts_bm.c +0 -0
@@ -166,6 +166,9 @@ static struct ts_config *bm_init(const void *pattern, unsigned int len,
 	unsigned int prefix_tbl_len = len * sizeof(unsigned int);
 	size_t priv_size = sizeof(*bm) + len + prefix_tbl_len;

The above description is referring to this expression?

I think the uints will be promoted to size_t before the addition occurs?

If you're referring to the prefix_tbl_len initialization then yes, overflow could happen.

lib/ts_bm.c static struct ts_config *bm_init(const void *pattern, unsigned int len, · line 170

Quoted 2 lines
lib/ts_bm.c +2 -0
+	if (unlikely(len == 0 || len > (UINT_MAX - sizeof(*bm)) / (sizeof(unsigned int) + 1)))
+		return ERR_PTR(-EINVAL);

Seems odd to perform these (uncommented!) checks after having performed the problematic operations. Something like:

unsigned int prefix_tbl_len;
size_t priv_size;

	/* Explanatory comment goes here */
	/* Can this actually happen? */
	if (unlikely(len == 0))
		return ERR_PTR(-EINVAL);

	/* Explanatory comment goes here */
	if (unlikely(len > (UINT_MAX - sizeof(*bm)) / (sizeof(unsigned int) + 1))
		return ERR_PTR(-EINVAL);
  	prefix_tbl_len = len * sizeof(unsigned int);
  	priv_size = sizeof(*bm) + len + prefix_tbl_len;

Also, please check the various helpers in overflow.h.

author
#3 lore raw

8 Mar 2026 19:55:20 Andrew Morton <[email protected]>:

Quoted 47 lines · On Sun,  8 Mar 2026 18:10:53 +0000 Josh Law <[email protected]> wrote:
Quoted 18 lines

From: Josh Law <[email protected]>

The ts_bm algorithm computes the required allocation size by multiplying the pattern length by the size of an integer. If the pattern length is sufficiently large, this can overflow the 32-bit unsigned int before it is widened to size_t. This could result in an undersized allocation and a subsequent heap buffer overflow when copying the pattern.

Fix this by explicitly checking that the length does not exceed the maximum safe threshold before calculating the buffer sizes.

...

lib/ts_bm.c static struct ts_config *bm_init(const void *pattern, unsigned int len, · line 167

Quoted 2 lines
lib/ts_bm.c +0 -0
@@ -166,6 +166,9 @@ static struct ts_config *bm_init(const void *pattern, unsigned int len,
     unsigned int prefix_tbl_len = len * sizeof(unsigned int);
     size_t priv_size = sizeof(*bm) + len + prefix_tbl_len;

The above description is referring to this expression?

I think the uints will be promoted to size_t before the addition occurs?

If you're referring to the prefix_tbl_len initialization then yes, overflow could happen.

lib/ts_bm.c static struct ts_config *bm_init(const void *pattern, unsigned int len, · line 170

Quoted 2 lines
lib/ts_bm.c +2 -0
+   if (unlikely(len == 0 || len > (UINT_MAX - sizeof(*bm)) / (sizeof(unsigned int) + 1)))
+       return ERR_PTR(-EINVAL);

Seems odd to perform these (uncommented!) checks after having performed the problematic operations.  Something like:

    unsigned int prefix_tbl_len;
    size_t priv_size;

    /* Explanatory comment goes here */
    /* Can this actually happen? */
    if (unlikely(len == 0))
        return ERR_PTR(-EINVAL);

    /* Explanatory comment goes here */
    if (unlikely(len > (UINT_MAX - sizeof(*bm)) / (sizeof(unsigned int) + 1)) return ERR_PTR(-EINVAL);

Quoted 5 lines

    prefix_tbl_len = len * sizeof(unsigned int); priv_size = sizeof(*bm) + len + prefix_tbl_len;

Also, please check the various helpers in overflow.h.

Yeah, I'm fixing that now, I also submitted a couple other patches you may want to have a look at

V/R

Josh law

author
#4 lore raw

8 Mar 2026 20:06:15 Josh Law <[email protected]>:

Quoted 55 lines

8 Mar 2026 19:55:20 Andrew Morton <[email protected]>:

Quoted 47 lines · On Sun,  8 Mar 2026 18:10:53 +0000 Josh Law <[email protected]> wrote:
Quoted 18 lines

From: Josh Law <[email protected]>

The ts_bm algorithm computes the required allocation size by multiplying the pattern length by the size of an integer. If the pattern length is sufficiently large, this can overflow the 32-bit unsigned int before it is widened to size_t. This could result in an undersized allocation and a subsequent heap buffer overflow when copying the pattern.

Fix this by explicitly checking that the length does not exceed the maximum safe threshold before calculating the buffer sizes.

...

lib/ts_bm.c static struct ts_config *bm_init(const void *pattern, unsigned int len, · line 167

Quoted 2 lines
lib/ts_bm.c +0 -0
@@ -166,6 +166,9 @@ static struct ts_config *bm_init(const void *pattern, unsigned int len,
     unsigned int prefix_tbl_len = len * sizeof(unsigned int);
     size_t priv_size = sizeof(*bm) + len + prefix_tbl_len;

The above description is referring to this expression?

I think the uints will be promoted to size_t before the addition occurs?

If you're referring to the prefix_tbl_len initialization then yes, overflow could happen.

lib/ts_bm.c static struct ts_config *bm_init(const void *pattern, unsigned int len, · line 170

Quoted 2 lines
lib/ts_bm.c +2 -0
+   if (unlikely(len == 0 || len > (UINT_MAX - sizeof(*bm)) / (sizeof(unsigned int) + 1)))
+       return ERR_PTR(-EINVAL);

Seems odd to perform these (uncommented!) checks after having performed the problematic operations.  Something like:

    unsigned int prefix_tbl_len;
    size_t priv_size;

    /* Explanatory comment goes here */
    /* Can this actually happen? */
    if (unlikely(len == 0))
        return ERR_PTR(-EINVAL);

    /* Explanatory comment goes here */
    if (unlikely(len > (UINT_MAX - sizeof(*bm)) / (sizeof(unsigned int) + 1)) return ERR_PTR(-EINVAL);

Quoted 5 lines

    prefix_tbl_len = len * sizeof(unsigned int); priv_size = sizeof(*bm) + len + prefix_tbl_len;

Also, please check the various helpers in overflow.h.

Quoted 7 lines

Yeah, I'm fixing that now, I also submitted a couple other patches you may want to have a look at

V/R

Josh law

Oh and also, sorry for bugging, but I have  a maintainers patch I sent, and another one you need to look at,

V/R

Josh law

author
#5 lore raw

PATCH v3 1/2 lib/ts_bm: fix integer overflow in pattern length calculation

In reply to Andrew Morton

From: Josh Law <[email protected]>

Changes in v3:
- move overflow checks before the arithmetic they guard
- add comments explaining the zero-length and size-overflow cases
- use check_mul_overflow() and check_add_overflow() from overflow.h

The ts_bm algorithm stores its good_shift[] table and pattern in a single allocation sized from the pattern length. If the good_shift[] size calculation wraps, the resulting allocation can be too small and subsequent pattern copies can overflow it.

Fix this by rejecting zero-length patterns and by using overflow helpers before calculating the combined allocation size.

---
 lib/ts_bm.c | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)
lib/ts_bm.c +16 -2
index eed5967238c5..676105e84005 100644
@@ -163,8 +163,22 @@ static struct ts_config *bm_init(const void *pattern, unsigned int len,
 	struct ts_config *conf;
 	struct ts_bm *bm;
 	int i;
-	unsigned int prefix_tbl_len = len * sizeof(unsigned int);
-	size_t priv_size = sizeof(*bm) + len + prefix_tbl_len;
+	unsigned int prefix_tbl_len;
+	size_t priv_size;
+
+	/* Zero-length patterns would underflow bm_find()'s initial shift. */
+	if (unlikely(!len))
+		return ERR_PTR(-EINVAL);
+
+	/*
+	 * bm->pattern is stored immediately after the good_shift[] table.
+	 * Reject lengths that would wrap while sizing either region.
+	 */
+	if (unlikely(check_mul_overflow(len, sizeof(*bm->good_shift),
+					&prefix_tbl_len) ||
+		     check_add_overflow(sizeof(*bm), (size_t)len, &priv_size) ||
+		     check_add_overflow(priv_size, prefix_tbl_len, &priv_size)))
+		return ERR_PTR(-EINVAL);
 
 	conf = alloc_ts_config(priv_size, gfp_mask);
 	if (IS_ERR(conf))
Signature · 1 line
2.43.0
author
#6 lore raw

PATCH v3 2/2 lib/ts_kmp: fix integer overflow in pattern length calculation

From: Josh Law <[email protected]>

Changes in v3:
- mirror the ts_bm review fixes for consistency across the series
- move overflow checks before the arithmetic they guard
- add comments and use overflow.h helpers for the allocation math

The ts_kmp algorithm stores its prefix_tbl[] table and pattern in a single allocation sized from the pattern length. If the prefix_tbl[] size calculation wraps, the resulting allocation can be too small and subsequent pattern copies can overflow it.

Fix this by rejecting zero-length patterns and by using overflow helpers before calculating the combined allocation size.

---
 lib/ts_kmp.c | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)
lib/ts_kmp.c +16 -2
index 5520dc28255a..29466c1803c9 100644
@@ -94,8 +94,22 @@ static struct ts_config *kmp_init(const void *pattern, unsigned int len,
 	struct ts_config *conf;
 	struct ts_kmp *kmp;
 	int i;
-	unsigned int prefix_tbl_len = len * sizeof(unsigned int);
-	size_t priv_size = sizeof(*kmp) + len + prefix_tbl_len;
+	unsigned int prefix_tbl_len;
+	size_t priv_size;
+
+	/* Zero-length patterns would make kmp_find() read beyond kmp->pattern. */
+	if (unlikely(!len))
+		return ERR_PTR(-EINVAL);
+
+	/*
+	 * kmp->pattern is stored immediately after the prefix_tbl[] table.
+	 * Reject lengths that would wrap while sizing either region.
+	 */
+	if (unlikely(check_mul_overflow(len, sizeof(*kmp->prefix_tbl),
+					&prefix_tbl_len) ||
+		     check_add_overflow(sizeof(*kmp), (size_t)len, &priv_size) ||
+		     check_add_overflow(priv_size, prefix_tbl_len, &priv_size)))
+		return ERR_PTR(-EINVAL);
 
 	conf = alloc_ts_config(priv_size, gfp_mask);
 	if (IS_ERR(conf))
Signature · 1 line
2.43.0