PHP 8.5.7 `levenshtein()` signed-integer overflow

Description

The levenshtein() function calculates the Levenshtein distance between two strings, optionally accepting custom costs for insertion, replacement, and deletion operations. In PHP 8.5.7, the implementation lacks proper bounds checking for these cost parameters. When exceptionally large values (such as PHP_INT_MAX) are provided, the arithmetic operations within the reference_levdist() function in ext/standard/levenshtein.c result in a signed-integer overflow. This triggers undefined behavior in C and causes the function to return a negative distance, which is mathematically invalid.

Proof of concept

<?php
/*
 * levenshtein() signed-integer overflow
 * File:  ext/standard/levenshtein.c  reference_levdist()  lines 47, 50, 53-58
 *
 * The user-supplied costs (cost_ins / cost_rep / cost_del, all zend_long) are
 * added with NO overflow check, e.g.:
 *     p1[i2]  = i2 * cost_ins;        // line 47
 *     p2[0]   = p1[0] + cost_del;     // line 50
 *     c1      = p1[i2 + 1] + cost_del;// line 54   <-- PHP_INT_MAX + PHP_INT_MAX
 *     c2      = p2[i2] + cost_ins;    // line 58
 *
 * Result: signed overflow (undefined behaviour in C) producing a
 * NEGATIVE edit distance, a value that is mathematically impossible.
 */
var_dump(levenshtein('a',   'b',   PHP_INT_MAX, PHP_INT_MAX, PHP_INT_MAX)); // int(-2)  (should be PHP_INT_MAX)
var_dump(levenshtein('a',   'abc', PHP_INT_MAX, PHP_INT_MAX, PHP_INT_MAX)); // int(-4)
var_dump(levenshtein('a',   'b',   PHP_INT_MAX, 0,           PHP_INT_MAX)); // int(-2)
echo "All three distances are negative => signed overflow (expected >= 0).\n";

Impact

The primary risk associated with this vulnerability is an application logic flaw. Applications that rely on the levenshtein() function to determine string similarity or calculate distance metrics might fail to handle negative returns properly (for instance, treating a negative number as < threshold). This can result in unexpected behavior, incorrect data processing, or bypasses in business logic. Since it involves integer overflow producing a negative result rather than a memory corruption issue, the scope is generally limited to logic disruption rather than arbitrary code execution.

Solution

To effectively address this issue, bounds checking should be implemented either on the cost parameters at the start of the function, or during intermediate calculations. Utilizing safe arithmetic macros provided by the Zend Engine can prevent the integer overflow constraints from being violated:

// Example: Adding overflow safeguards in ext/standard/levenshtein.c
if (UNEXPECTED(ZEND_SIGNED_ADD_OVERFLOWS(p1[i2 + 1], cost_del))) {
    php_error_docref(NULL, E_WARNING, "Levenshtein distance calculation caused an integer overflow");
    // Handle error, e.g., return -1 or cap
}

An alternative and proactive measure is to restrict the inputs for cost_ins, cost_rep, and cost_del before computing the distance, ensuring that they wouldn't exceed ZEND_LONG_MAX when scaled relative to the strings' lengths.