lib/ts_bm: fix integer overflow in pattern length calculation
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
@@ -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
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
@@ -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
Andrew Morton
maintainerQuoted 17 lines · On Sun, 8 Mar 2026 18:10:53 +0000 Josh Law <[email protected]> wrote:
From: Josh Law <[email protected]>
The
ts_bmalgorithm 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 tosize_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.
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_bmalgorithm 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 tosize_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_tbefore the addition occurs?If you're referring to the
prefix_tbl_leninitialization 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_tpriv_size;/* Explanatory comment goes here */
/* Can this actually happen? */
if (unlikely(len == 0))
returnERR_PTR(-EINVAL);/* Explanatory comment goes here */
if (unlikely(len > (UINT_MAX - sizeof(*bm)) / (sizeof(unsigned int) + 1))returnERR_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
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_bmalgorithm 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 tosize_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_tbefore the addition occurs?If you're referring to the
prefix_tbl_leninitialization 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_tpriv_size;/* Explanatory comment goes here */
/* Can this actually happen? */
if (unlikely(len == 0))
returnERR_PTR(-EINVAL);/* Explanatory comment goes here */
if (unlikely(len > (UINT_MAX - sizeof(*bm)) / (sizeof(unsigned int) + 1))returnERR_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
PATCH v3 1/2 lib/ts_bm: fix integer overflow in pattern length calculation
In reply to Andrew MortonFrom: 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
@@ -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
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
@@ -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