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

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

[Josh Law]

From: Josh Law <objecting@objecting.org>

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.

Signed-off-by: Josh Law <objecting@objecting.org>
---
 lib/ts_kmp.c | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)

diff --git a/lib/ts_kmp.c b/lib/ts_kmp.c
index 5520dc28255a..29466c1803c9 100644
--- a/lib/ts_kmp.c
+++ b/lib/ts_kmp.c
@@ -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))
-- 
2.43.0

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

[Josh Law]

From: Josh Law <objecting@objecting.org>

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.

Signed-off-by: Josh Law <objecting@objecting.org>
---
 lib/ts_bm.c | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)

diff --git a/lib/ts_bm.c b/lib/ts_bm.c
index eed5967238c5..676105e84005 100644
--- a/lib/ts_bm.c
+++ b/lib/ts_bm.c
@@ -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))
-- 
2.43.0

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

[Josh Law]

From: Josh Law <objecting@objecting.org>

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.

Signed-off-by: Josh Law <objecting@objecting.org>
---
 lib/ts_kmp.c | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)

diff --git a/lib/ts_kmp.c b/lib/ts_kmp.c
index 5520dc28255a..29466c1803c9 100644
--- a/lib/ts_kmp.c
+++ b/lib/ts_kmp.c
@@ -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))
-- 
2.43.0