postgres.git / summary / log / commit / refs
commit 9505175f2a782bb63acd11d8d473a0ccedb719ea
Author: Nathan Bossart <nathan@postgresql.org>
Commit: Noah Misch <noah@leadboat.com>
Date: Mon Aug 10 13:38:36 2026 +0000
Avoid overflow in Levenshtein distance calculations.
levenshtein() and levenshtein_less_equal() let the caller specify
the insertion, deletion, and substitution costs, and
fuzzystrmatch's corresponding SQL functions accept any 32-bit
integer for each. Since the distances are calculated with 32-bit
arithmetic, large costs can cause overflows, thereby producing
nonsensical results. Certain inputs to levenshtein_less_equal()
can even cause out-of-bounds writes. To fix, use 64-bit arithmetic
instead, and error whenever the final result won't fit in the
returned 32-bit integer.
We may want to teach these functions to reject negative costs, too,
but that didn't seem appropriate for a security fix, and therefore
it is left as a future exercise.
Reported-by: Ben Morris in collaboration with Claude and Anthropic Research
Author: Nathan Bossart <nathandbossart@gmail.com>
Reviewed-by: Dean Rasheed <dean.a.rasheed@gmail.com>
Security: CVE-2026-15742
Backpatch-through: 14
contrib/fuzzystrmatch/expected/fuzzystrmatch.out | 14 ++++
contrib/fuzzystrmatch/sql/fuzzystrmatch.sql | 3 +
src/backend/utils/adt/levenshtein.c | 89 ++++++++++++------------
src/backend/utils/adt/varlena.c | 14 ++++
4 files changed, 77 insertions(+), 43 deletions(-)
diff --git a/contrib/fuzzystrmatch/expected/fuzzystrmatch.out b/contrib/fuzzystrmatch/expected/fuzzystrmatch.out
index 2827e81eb47..ed6a6b91b4a 100644
--- a/contrib/fuzzystrmatch/expected/fuzzystrmatch.out
+++ b/contrib/fuzzystrmatch/expected/fuzzystrmatch.out
@@ -41,6 +41,14 @@ SELECT levenshtein('GUMBO', 'GAMBOL', 2, 1, 1);
3
(1 row)
+SELECT levenshtein('GUMBO', 'GAMBOL', 1, 1, 2000000000);
+ levenshtein
+-------------
+ 3
+(1 row)
+
+SELECT levenshtein('GUMBO', 'GAMBOL', 2000000000, 2000000000, 2000000000);
+ERROR: levenshtein distance out of range
SELECT levenshtein_less_equal('extensive', 'exhaustive', 2);
levenshtein_less_equal
------------------------
@@ -53,6 +61,12 @@ SELECT levenshtein_less_equal('extensive', 'exhaustive', 4);
4
(1 row)
+SELECT levenshtein_less_equal('aaa', 'aaaaa', 1073741824, 0, 1073741824, 10);
+ levenshtein_less_equal
+------------------------
+ 11
+(1 row)
+
SELECT metaphone('GUMBO', 4);
metaphone
-----------
diff --git a/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql b/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql
index 1d0e2197fbe..c86d925701f 100644
--- a/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql
+++ b/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql
@@ -11,8 +11,11 @@ SELECT soundex(''), difference('', '');
SELECT levenshtein('GUMBO', 'GAMBOL');
SELECT levenshtein('GUMBO', 'GAMBOL', 2, 1, 1);
+SELECT levenshtein('GUMBO', 'GAMBOL', 1, 1, 2000000000);
+SELECT levenshtein('GUMBO', 'GAMBOL', 2000000000, 2000000000, 2000000000);
SELECT levenshtein_less_equal('extensive', 'exhaustive', 2);
SELECT levenshtein_less_equal('extensive', 'exhaustive', 4);
+SELECT levenshtein_less_equal('aaa', 'aaaaa', 1073741824, 0, 1073741824, 10);
SELECT metaphone('GUMBO', 4);
diff --git a/src/backend/utils/adt/levenshtein.c b/src/backend/utils/adt/levenshtein.c
index 38d4f580d01..a116f1b3502 100644
--- a/src/backend/utils/adt/levenshtein.c
+++ b/src/backend/utils/adt/levenshtein.c
@@ -9,7 +9,7 @@
* Levenshtein distance with custom costings, and (2) Levenshtein distance with
* custom costings and a "max" value above which exact distances are not
* interesting. Before the inclusion, we rely on the presence of the inline
- * function rest_of_char_same().
+ * functions rest_of_char_same() and levenshtein_result().
*
* Written based on a description of the algorithm by Michael Gilleland found
* at http://www.merriampark.com/ld.htm. Also looked at levenshtein.c in the
@@ -78,14 +78,17 @@ varstr_levenshtein(const char *source, int slen,
{
int m,
n;
- int *prev;
- int *curr;
+ int64 *prev;
+ int64 *curr;
int *s_char_len = NULL;
int i,
j;
const char *y;
const char *send = source + slen;
const char *tend = target + tlen;
+ int64 ins_c_64 = ins_c;
+ int64 del_c_64 = del_c;
+ int64 sub_c_64 = sub_c;
/*
* For varstr_levenshtein_less_equal, we have real variables called
@@ -116,9 +119,9 @@ varstr_levenshtein(const char *source, int slen,
* into an empty s with m deletions.
*/
if (!m)
- return n * ins_c;
+ return levenshtein_result(n * ins_c_64);
if (!n)
- return m * del_c;
+ return levenshtein_result(m * del_c_64);
/*
* For security concerns, restrict excessive CPU+RAM usage. (This
@@ -148,20 +151,20 @@ varstr_levenshtein(const char *source, int slen,
*/
if (max_d >= 0)
{
- int min_theo_d; /* Theoretical minimum distance. */
- int max_theo_d; /* Theoretical maximum distance. */
+ int64 min_theo_d; /* Theoretical minimum distance. */
+ int64 max_theo_d; /* Theoretical maximum distance. */
int net_inserts = n - m;
min_theo_d = net_inserts < 0 ?
- -net_inserts * del_c : net_inserts * ins_c;
+ -net_inserts * del_c_64 : net_inserts * ins_c_64;
if (min_theo_d > max_d)
- return max_d + 1;
- if (ins_c + del_c < sub_c)
- sub_c = ins_c + del_c;
- max_theo_d = min_theo_d + sub_c * Min(m, n);
+ return levenshtein_result((int64) max_d + 1);
+ if (ins_c_64 + del_c_64 < sub_c_64)
+ sub_c_64 = ins_c_64 + del_c_64;
+ max_theo_d = min_theo_d + sub_c_64 * Min(m, n);
if (max_d >= max_theo_d)
max_d = -1;
- else if (ins_c + del_c > 0)
+ else if (ins_c_64 + del_c_64 > 0)
{
/*
* Figure out how much of the first row of the notional matrix we
@@ -175,12 +178,12 @@ varstr_levenshtein(const char *source, int slen,
* column n - m. If we do start further right, the best-case
* total cost increases by ins_c + del_c for each move right.
*/
- int slack_d = max_d - min_theo_d;
+ int64 slack_d = max_d - min_theo_d;
int best_column = net_inserts < 0 ? -net_inserts : 0;
+ int64 tmp;
- stop_column = best_column + (slack_d / (ins_c + del_c)) + 1;
- if (stop_column > m)
- stop_column = m + 1;
+ tmp = best_column + (slack_d / (ins_c_64 + del_c_64)) + 1;
+ stop_column = Min(tmp, m + 1);
}
}
#endif
@@ -212,7 +215,7 @@ varstr_levenshtein(const char *source, int slen,
++n;
/* Previous and current rows of notional array. */
- prev = (int *) palloc(2 * m * sizeof(int));
+ prev = (int64 *) palloc(2 * m * sizeof(int64));
curr = prev + m;
/*
@@ -220,12 +223,12 @@ varstr_levenshtein(const char *source, int slen,
* t, we must perform i deletions.
*/
for (i = START_COLUMN; i < STOP_COLUMN; i++)
- prev[i] = i * del_c;
+ prev[i] = i * del_c_64;
/* Loop through rows of the notional array */
for (y = target, j = 1; j < n; j++)
{
- int *temp;
+ int64 *temp;
const char *x = source;
int y_char_len = n != tlen + 1 ? pg_mblen_range(y, tend) : 1;
@@ -239,7 +242,7 @@ varstr_levenshtein(const char *source, int slen,
*/
if (stop_column < m)
{
- prev[stop_column] = max_d + 1;
+ prev[stop_column] = (int64) max_d + 1;
++stop_column;
}
@@ -251,13 +254,13 @@ varstr_levenshtein(const char *source, int slen,
*/
if (start_column == 0)
{
- curr[0] = j * ins_c;
+ curr[0] = j * ins_c_64;
i = 1;
}
else
i = start_column;
#else
- curr[0] = j * ins_c;
+ curr[0] = j * ins_c_64;
i = 1;
#endif
@@ -272,9 +275,9 @@ varstr_levenshtein(const char *source, int slen,
{
for (; i < STOP_COLUMN; i++)
{
- int ins;
- int del;
- int sub;
+ int64 ins;
+ int64 del;
+ int64 sub;
int x_char_len = s_char_len[i - 1];
/*
@@ -286,14 +289,14 @@ varstr_levenshtein(const char *source, int slen,
* get past that test, then we compare the lengths and the
* remaining bytes.
*/
- ins = prev[i] + ins_c;
- del = curr[i - 1] + del_c;
+ ins = prev[i] + ins_c_64;
+ del = curr[i - 1] + del_c_64;
if (x[x_char_len - 1] == y[y_char_len - 1]
&& x_char_len == y_char_len &&
(x_char_len == 1 || rest_of_char_same(x, y, x_char_len)))
sub = prev[i - 1];
else
- sub = prev[i - 1] + sub_c;
+ sub = prev[i - 1] + sub_c_64;
/* Take the one with minimum cost. */
curr[i] = Min(ins, del);
@@ -307,14 +310,14 @@ varstr_levenshtein(const char *source, int slen,
{
for (; i < STOP_COLUMN; i++)
{
- int ins;
- int del;
- int sub;
+ int64 ins;
+ int64 del;
+ int64 sub;
/* Calculate costs for insertion, deletion, and substitution. */
- ins = prev[i] + ins_c;
- del = curr[i - 1] + del_c;
- sub = prev[i - 1] + ((*x == *y) ? 0 : sub_c);
+ ins = prev[i] + ins_c_64;
+ del = curr[i - 1] + del_c_64;
+ sub = prev[i - 1] + ((*x == *y) ? 0 : sub_c_64);
/* Take the one with minimum cost. */
curr[i] = Min(ins, del);
@@ -360,8 +363,8 @@ varstr_levenshtein(const char *source, int slen,
int ii = stop_column - 1;
int net_inserts = ii - zp;
- if (prev[ii] + (net_inserts > 0 ? net_inserts * ins_c :
- -net_inserts * del_c) <= max_d)
+ if (prev[ii] + (net_inserts > 0 ? net_inserts * ins_c_64 :
+ -net_inserts * del_c_64) <= max_d)
break;
stop_column--;
}
@@ -372,8 +375,8 @@ varstr_levenshtein(const char *source, int slen,
int net_inserts = start_column - zp;
if (prev[start_column] +
- (net_inserts > 0 ? net_inserts * ins_c :
- -net_inserts * del_c) <= max_d)
+ (net_inserts > 0 ? net_inserts * ins_c_64 :
+ -net_inserts * del_c_64) <= max_d)
break;
/*
@@ -381,8 +384,8 @@ varstr_levenshtein(const char *source, int slen,
* there's nothing here that could confuse any future
* iteration of the outer loop.
*/
- prev[start_column] = max_d + 1;
- curr[start_column] = max_d + 1;
+ prev[start_column] = (int64) max_d + 1;
+ curr[start_column] = (int64) max_d + 1;
if (start_column != 0)
source += (s_char_len != NULL) ? s_char_len[start_column - 1] : 1;
start_column++;
@@ -390,7 +393,7 @@ varstr_levenshtein(const char *source, int slen,
/* If they cross, we're going to exceed the bound. */
if (start_column >= stop_column)
- return max_d + 1;
+ return levenshtein_result((int64) max_d + 1);
}
#endif
}
@@ -399,5 +402,5 @@ varstr_levenshtein(const char *source, int slen,
* Because the final value was swapped from the previous row to the
* current row, that's where we'll find it.
*/
- return prev[m - 1];
+ return levenshtein_result(prev[m - 1]);
}
diff --git a/src/backend/utils/adt/varlena.c b/src/backend/utils/adt/varlena.c
index 4d334e9314e..b4d1f65a20e 100644
--- a/src/backend/utils/adt/varlena.c
+++ b/src/backend/utils/adt/varlena.c
@@ -6265,6 +6265,20 @@ rest_of_char_same(const char *s1, const char *s2, int len)
return true;
}
+/*
+ * Helper function for checking return value of Levenshtein distance functions.
+ * We calculate it as an int64, but the distance functions return an int32.
+ */
+static inline int
+levenshtein_result(int64 res)
+{
+ if (unlikely(res < PG_INT32_MIN || res > PG_INT32_MAX))
+ ereport(ERROR,
+ (errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+ errmsg("levenshtein distance out of range")));
+ return res;
+}
+
/* Expand each Levenshtein distance variant */
#include "levenshtein.c"
#define LEVENSHTEIN_LESS_EQUAL
[parent: 1f49beef271e]