This is an automated email from the ASF dual-hosted git repository. reshke pushed a commit to branch backport_cve in repository https://gitbox.apache.org/repos/asf/cloudberry.git
commit 6f39b92151044b5450d11376398dedad1216b4e1 Author: Nathan Bossart <[email protected]> AuthorDate: Mon Aug 10 06:38:24 2026 -0700 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 <[email protected]> Reviewed-by: Dean Rasheed <[email protected]> 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 3195e1ec3c8..aeab031a2ed 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 0b4bb9be57e..c1d55f823d7 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 9a84c8d0fc4..c060d73706e 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,13 +78,16 @@ varstr_levenshtein(const char *source, int slen, { int m, n; - int *prev; - int *curr; + int64 *prev; + int64 *curr; int *s_char_len = NULL; int 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 @@ -115,9 +118,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 @@ -147,20 +150,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 @@ -174,12 +177,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 @@ -211,7 +214,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; /* @@ -219,12 +222,12 @@ varstr_levenshtein(const char *source, int slen, * t, we must perform i deletions. */ for (int 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; int i; @@ -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 1f8fcd1f406..b7f1fa33014 100644 --- a/src/backend/utils/adt/varlena.c +++ b/src/backend/utils/adt/varlena.c @@ -6094,6 +6094,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 --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
