Fix memory unsafety in array_walk()

Fixes bugs #61967, #62607, #69068, #70713.

The primary changes are:
a) Use the ht_iterator mechanism to ensure safety not only if the
   iterated array itself changes, but also if it is replaced (and
   potentially destroyed) entirely. We use the same semantics for
   behavior under modification as foreach-by-reference. In
   particular, we advance to the next element before processing it.
   If the iterated entity is exchanged we iterate the new one from
   the start. If it is not an array/object we warn and abort.
b) Always create a reference to the current value. Previously the
   code kept the value as a non-reference and updated it to the
   reference value produced by the user callback. However this is
   unsafe, as the array may have been reallocated in the meantime,
   so the previous value pointer is no longer value.
c) Around a recursive walk, incref the reference containing the
   array. This ensures that the location where the currently
   iterated value is stored cannot be freed.

One problem I was not able to solve is that we cannot decrement
the apply count if the array is exchanged during a recursive walk.

8 files changed, 208 insertions, 50 deletions

diff --git a/NEWS b/NEWS
index d939bf63fd..89c0485b4f 100644
--- a/NEWS
+++ b/NEWS
@@ -57,6 +57,15 @@ PHP                                                                        NEWS
   . Implemented FR #72653 (SQLite should allow opening with empty filename).
     (cmb)
 
+- Standard:
+  . Fixed bug #61967 (unset array item in array_walk_recursive cause
+    inconsistent array). (Nikita)
+  . Fixed bug #62607 (array_walk_recursive move internal pointer). (Nikita)
+  . Fixed bug #69068 (Exchanging array during array_walk -> memory errors).
+    (Nikita)
+  . Fixed bug #70713 (Use After Free Vulnerability in array_walk()/
+    array_walk_recursive()). (Nikita)
+
 - Streams:
   . Fixed bug #41021 (Problems with the ftps wrapper). (vhuk)
   . Fixed bug #54431 (opendir() does not work with ftps:// wrapper). (vhuk)
diff --git a/ext/standard/array.c b/ext/standard/array.c
index 2e42bba9ea..38e275ae83 100644
--- a/ext/standard/array.c
+++ b/ext/standard/array.c
@@ -1407,11 +1407,15 @@ PHP_FUNCTION(max)
 }
 /* }}} */
 
-static int php_array_walk(HashTable *target_hash, zval *userdata, int recursive) /* {{{ */
+static int php_array_walk(zval *array, zval *userdata, int recursive) /* {{{ */
 {
 	zval args[3],		/* Arguments to userland function */
 		 retval,		/* Return value - unused */
 		 *zv;
+	HashTable *target_hash = HASH_OF(array);
+	HashPosition pos;
+	uint32_t ht_iter;
+	int result = SUCCESS;
 
 	/* Set up known arguments */
 	ZVAL_UNDEF(&args[1]);
@@ -1424,89 +1428,112 @@ static int php_array_walk(HashTable *target_hash, zval *userdata, int recursive)
 	BG(array_walk_fci).params = args;
 	BG(array_walk_fci).no_separation = 0;
 
+	zend_hash_internal_pointer_reset_ex(target_hash, &pos);
+	ht_iter = zend_hash_iterator_add(target_hash, pos);
+
 	/* Iterate through hash */
-	zend_hash_internal_pointer_reset(target_hash);
-	while (!EG(exception) && (zv = zend_hash_get_current_data(target_hash)) != NULL) {
+	do {
+		/* Retrieve value */
+		zv = zend_hash_get_current_data_ex(target_hash, &pos);
+		if (zv == NULL) {
+			break;
+		}
+
+		/* Skip undefined indirect elements */
 		if (Z_TYPE_P(zv) == IS_INDIRECT) {
 			zv = Z_INDIRECT_P(zv);
 			if (Z_TYPE_P(zv) == IS_UNDEF) {
-				zend_hash_move_forward(target_hash);
+				zend_hash_move_forward_ex(target_hash, &pos);
 				continue;
 			}
 		}
-		if (recursive &&
-		    (Z_TYPE_P(zv) == IS_ARRAY ||
-		     (Z_ISREF_P(zv) && Z_TYPE_P(Z_REFVAL_P(zv)) == IS_ARRAY))) {
+
+		/* Ensure the value is a reference. Otherwise the location of the value may be freed. */
+		ZVAL_MAKE_REF(zv);
+
+		/* Retrieve key */
+		zend_hash_get_current_key_zval_ex(target_hash, &args[1], &pos);
+
+		/* Move to next element already now -- this mirrors the approach used by foreach
+		 * and ensures proper behavior with regard to modifications. */
+		zend_hash_move_forward_ex(target_hash, &pos);
+
+		/* Back up hash position, as it may change */
+		EG(ht_iterators)[ht_iter].pos = pos;
+
+		if (recursive && Z_TYPE_P(Z_REFVAL_P(zv)) == IS_ARRAY) {
 			HashTable *thash;
 			zend_fcall_info orig_array_walk_fci;
 			zend_fcall_info_cache orig_array_walk_fci_cache;
+			zval ref;
+			ZVAL_COPY_VALUE(&ref, zv);
 
 			ZVAL_DEREF(zv);
 			SEPARATE_ARRAY(zv);
 			thash = Z_ARRVAL_P(zv);
 			if (thash->u.v.nApplyCount > 1) {
 				php_error_docref(NULL, E_WARNING, "recursion detected");
-				if (userdata) {
-					zval_ptr_dtor(&args[2]);
-				}
-				return 0;
+				result = FAILURE;
+				break;
 			}
 
 			/* backup the fcall info and cache */
 			orig_array_walk_fci = BG(array_walk_fci);
 			orig_array_walk_fci_cache = BG(array_walk_fci_cache);
 
+			Z_ADDREF(ref);
 			thash->u.v.nApplyCount++;
-			php_array_walk(thash, userdata, recursive);
-			thash->u.v.nApplyCount--;
+			result = php_array_walk(zv, userdata, recursive);
+			if (Z_TYPE_P(Z_REFVAL(ref)) == IS_ARRAY && thash == Z_ARRVAL_P(Z_REFVAL(ref))) {
+				/* If the hashtable changed in the meantime, we'll "leak" this apply count
+				 * increment -- our reference to thash is no longer valid. */
+				thash->u.v.nApplyCount--;
+			}
+			zval_ptr_dtor(&ref);
 
 			/* restore the fcall info and cache */
 			BG(array_walk_fci) = orig_array_walk_fci;
 			BG(array_walk_fci_cache) = orig_array_walk_fci_cache;
 		} else {
-			int was_ref = Z_ISREF_P(zv);
-
 			ZVAL_COPY(&args[0], zv);
 
-			/* Allocate space for key */
-			zend_hash_get_current_key_zval(target_hash, &args[1]);
-
 			/* Call the userland function */
-			if (zend_call_function(&BG(array_walk_fci), &BG(array_walk_fci_cache)) == SUCCESS) {
-				if (!was_ref && Z_ISREF(args[0])) {
-					/* copy reference back */
-					zval garbage;
-					if (Z_REFCOUNT(args[0]) == 1) {
-						ZVAL_UNREF(&args[0]);
-					}
-					ZVAL_COPY_VALUE(&garbage, zv);
-					ZVAL_COPY_VALUE(zv, &args[0]);
-					zval_ptr_dtor(&garbage);
-				} else {
-					zval_ptr_dtor(&args[0]);
-				}
+			result = zend_call_function(&BG(array_walk_fci), &BG(array_walk_fci_cache));
+			if (result == SUCCESS) {
 				zval_ptr_dtor(&retval);
-			} else {
-				zval_ptr_dtor(&args[0]);
-				if (Z_TYPE(args[1]) != IS_UNDEF) {
-					zval_ptr_dtor(&args[1]);
-					ZVAL_UNDEF(&args[1]);
-				}
-				break;
 			}
+
+			zval_ptr_dtor(&args[0]);
 		}
 
 		if (Z_TYPE(args[1]) != IS_UNDEF) {
 			zval_ptr_dtor(&args[1]);
 			ZVAL_UNDEF(&args[1]);
 		}
-		zend_hash_move_forward(target_hash);
-	}
+
+		if (result == FAILURE) {
+			break;
+		}
+
+		/* Reload array and position -- both may have changed */
+		if (Z_TYPE_P(array) == IS_ARRAY) {
+			pos = zend_hash_iterator_pos_ex(ht_iter, array);
+			target_hash = Z_ARRVAL_P(array);
+		} else if (Z_TYPE_P(array) == IS_OBJECT) {
+			target_hash = Z_OBJPROP_P(array);
+			pos = zend_hash_iterator_pos(ht_iter, target_hash);
+		} else {
+			php_error_docref(NULL, E_WARNING, "Iterated value is no longer an array or object");
+			result = FAILURE;
+			break;
+		}
+	} while (!EG(exception));
 
 	if (userdata) {
 		zval_ptr_dtor(&args[2]);
 	}
-	return 0;
+	zend_hash_iterator_del(ht_iter);
+	return result;
 }
 /* }}} */
 
@@ -1514,7 +1541,7 @@ static int php_array_walk(HashTable *target_hash, zval *userdata, int recursive)
    Apply a user function to every member of an array */
 PHP_FUNCTION(array_walk)
 {
-	HashTable *array;
+	zval *array;
 	zval *userdata = NULL;
 	zend_fcall_info orig_array_walk_fci;
 	zend_fcall_info_cache orig_array_walk_fci_cache;
@@ -1523,14 +1550,14 @@ PHP_FUNCTION(array_walk)
 	orig_array_walk_fci_cache = BG(array_walk_fci_cache);
 
 #ifndef FAST_ZPP
-	if (zend_parse_parameters(ZEND_NUM_ARGS(), "H/f|z/", &array, &BG(array_walk_fci), &BG(array_walk_fci_cache), &userdata) == FAILURE) {
+	if (zend_parse_parameters(ZEND_NUM_ARGS(), "A/f|z/", &array, &BG(array_walk_fci), &BG(array_walk_fci_cache), &userdata) == FAILURE) {
 		BG(array_walk_fci) = orig_array_walk_fci;
 		BG(array_walk_fci_cache) = orig_array_walk_fci_cache;
 		return;
 	}
 #else
 	ZEND_PARSE_PARAMETERS_START(2, 3)
-		Z_PARAM_ARRAY_OR_OBJECT_HT_EX(array, 0, 1)
+		Z_PARAM_ARRAY_OR_OBJECT_EX(array, 0, 1)
 		Z_PARAM_FUNC(BG(array_walk_fci), BG(array_walk_fci_cache))
 		Z_PARAM_OPTIONAL
 		Z_PARAM_ZVAL_EX(userdata, 0, 1)
@@ -1552,7 +1579,7 @@ PHP_FUNCTION(array_walk)
    Apply a user function recursively to every member of an array */
 PHP_FUNCTION(array_walk_recursive)
 {
-	HashTable *array;
+	zval *array;
 	zval *userdata = NULL;
 	zend_fcall_info orig_array_walk_fci;
 	zend_fcall_info_cache orig_array_walk_fci_cache;
@@ -1560,7 +1587,7 @@ PHP_FUNCTION(array_walk_recursive)
 	orig_array_walk_fci = BG(array_walk_fci);
 	orig_array_walk_fci_cache = BG(array_walk_fci_cache);
 
-	if (zend_parse_parameters(ZEND_NUM_ARGS(), "H/f|z/", &array, &BG(array_walk_fci), &BG(array_walk_fci_cache), &userdata) == FAILURE) {
+	if (zend_parse_parameters(ZEND_NUM_ARGS(), "A/f|z/", &array, &BG(array_walk_fci), &BG(array_walk_fci_cache), &userdata) == FAILURE) {
 		BG(array_walk_fci) = orig_array_walk_fci;
 		BG(array_walk_fci_cache) = orig_array_walk_fci_cache;
 		return;
diff --git a/ext/standard/tests/array/bug61730.phpt b/ext/standard/tests/array/bug61730.phpt
index 0fe9f22212..0761fee774 100644
--- a/ext/standard/tests/array/bug61730.phpt
+++ b/ext/standard/tests/array/bug61730.phpt
@@ -28,10 +28,9 @@ array_walk(
 print_r($myArray);
 --EXPECT--
 int(0)
-int(4)
-int(8)
+int(3)
+int(6)
+int(9)
 Array
 (
-    [3] => 1
-    [7] => 1
 )
diff --git a/ext/standard/tests/array/bug61967.phpt b/ext/standard/tests/array/bug61967.phpt
new file mode 100644
index 0000000000..7fc65c8d90
--- /dev/null
+++ b/ext/standard/tests/array/bug61967.phpt
@@ -0,0 +1,25 @@
+--TEST--
+Bug #61967: unset array item in array_walk_recursive cause inconsistent array
+--FILE--
+<?php
+$arr = array(
+    range(1, 5),
+    range(1, 5),
+    range(1, 5),
+    range(1, 5),
+    range(1, 5),
+);
+
+array_walk_recursive($arr,
+    function (&$value, $key) use(&$arr) {
+        var_dump($key);
+        unset($arr[$key]);
+    }
+);
+?>
+--EXPECT--
+int(0)
+int(1)
+int(2)
+int(3)
+int(4)
diff --git a/ext/standard/tests/array/bug62607.phpt b/ext/standard/tests/array/bug62607.phpt
new file mode 100644
index 0000000000..d9d529d2cf
--- /dev/null
+++ b/ext/standard/tests/array/bug62607.phpt
@@ -0,0 +1,12 @@
+--TEST--
+Bug #62607: array_walk_recursive move internal pointer
+--FILE--
+<?php
+$arr = array('a'=>'b');
+echo 'Before -> '.current($arr).PHP_EOL;
+array_walk_recursive($arr, function(&$val){});
+echo 'After -> '.current($arr);
+?>
+--EXPECT--
+Before -> b
+After -> b
diff --git a/ext/standard/tests/array/bug69068.phpt b/ext/standard/tests/array/bug69068.phpt
new file mode 100644
index 0000000000..e87b759db0
--- /dev/null
+++ b/ext/standard/tests/array/bug69068.phpt
@@ -0,0 +1,26 @@
+--TEST--
+Bug #69068: Exchanging array during array_walk -> memory errors
+--FILE--
+<?php
+
+$array = [1, 2, 3];
+array_walk($array, function($value, $key) {
+    var_dump($value);
+    if ($value == 2) {
+        $GLOBALS['array'] = [4, 5];
+    }
+});
+var_dump($array);
+
+?>
+--EXPECT--
+int(1)
+int(2)
+int(4)
+int(5)
+array(2) {
+  [0]=>
+  int(4)
+  [1]=>
+  int(5)
+}
diff --git a/ext/standard/tests/array/bug69068_2.phpt b/ext/standard/tests/array/bug69068_2.phpt
new file mode 100644
index 0000000000..ce3e3650a3
--- /dev/null
+++ b/ext/standard/tests/array/bug69068_2.phpt
@@ -0,0 +1,34 @@
+--TEST--
+Bug #69068: Exchanging array during array_walk -> memory errors (variation)
+--FILE--
+<?php
+
+$array = [1, 2, 3];
+$array2 = [4, 5];
+array_walk($array, function(&$value, $key) use ($array2) {
+    var_dump($value);
+    if ($value == 2) {
+        $GLOBALS['array'] = $array2;
+    }
+    $value *= 10;
+});
+var_dump($array, $array2);
+
+?>
+--EXPECT--
+int(1)
+int(2)
+int(4)
+int(5)
+array(2) {
+  [0]=>
+  int(40)
+  [1]=>
+  int(50)
+}
+array(2) {
+  [0]=>
+  int(4)
+  [1]=>
+  int(5)
+}
diff --git a/ext/standard/tests/array/bug70713.phpt b/ext/standard/tests/array/bug70713.phpt
new file mode 100644
index 0000000000..4e2792ab4b
--- /dev/null
+++ b/ext/standard/tests/array/bug70713.phpt
@@ -0,0 +1,26 @@
+--TEST--
+Bug #70713: Use After Free Vulnerability in array_walk()/array_walk_recursive()
+--FILE--
+<?php
+
+class obj
+{
+	function __tostring()
+	{
+		global $arr;
+		
+		$arr = 1;
+		for ($i = 0; $i < 5; $i++) {
+			$v[$i] = 'hi'.$i;
+		}
+		
+		return 'hi';
+	}
+}
+
+$arr = array('string' => new obj);
+array_walk_recursive($arr, 'settype');
+
+?>
+--EXPECTF--
+Warning: array_walk_recursive(): Iterated value is no longer an array or object in %s on line %d