CVE-2016-6874: Other (NVD-CWE-Other)
value: The array_*_recursive functions in Facebook HHVM before 3.15.0 allows attackers to have unspecified impact via unknown vectors, related to recursion.
CWE description: NVD is only using a subset of CWE for mapping instead of the entire CWE, and the weakness type is not covered by that subset.
CVSS v3 base score: 9.8
Published: 2017-02-17T17:59Z
Repository: https://github.com/facebook/hhvm
Language: PHP
Files changed: hphp/runtime/ext/array/ext_array.cpp, hphp/test/slow/array_functions/self_recursive.php, hphp/test/slow/array_functions/self_recursive.php.expectf
Commit date: 2016-08-01 15:46:22 -0700
Commit message: Fix recursion checks in array_*_recursive

Summary:
array_merge_recursive and array_replace_recursive do recursion checks,
but use the fact that normal arrays can't contain cycles except
through references to avoid most of the checking.

Unfortunately the $GLOBALS array is special, and /can/ contain cycles
without references, and ProxyArrays could potentially do the same (via
an as-yet unimplemented extension).

Reviewed By: mxw

Differential Revision: D3622612

fbshipit-source-id: ed90b747096a05919a80c4793e2a2b7c57584d56

Diff: diff --git a/hphp/runtime/ext/array/ext_array.cpp b/hphp/runtime/ext/array/ext_array.cpp
index 8c922af6bb2..d702c9831c6 100644
--- a/hphp/runtime/ext/array/ext_array.cpp
+++ b/hphp/runtime/ext/array/ext_array.cpp
@@ -377,18 +377,21 @@ Variant HHVM_FUNCTION(array_keys, int64_t argc,
 
 static void php_array_merge(Array &arr1, const Array& arr2) {
   arr1.merge(arr2);
 }
 
+static bool couldRecur(const Variant& v, const Array& arr) {
+  return v.isReferenced() ||
+    arr.get()->kind() == ArrayData::kGlobalsKind ||
+    arr.get()->kind() == ArrayData::kProxyKind;
+}
+
 static void php_array_merge_recursive(PointerSet &seen, bool check,
                                       Array &arr1, const Array& arr2) {
-  if (check) {
-    if (seen.find((void*)arr1.get()) != seen.end()) {
-      raise_warning("array_merge_recursive(): recursion detected");
-      return;
-    }
-    seen.insert((void*)arr1.get());
+  if (check && !seen.insert((void*)arr1.get()).second) {
+    raise_warning("array_merge_recursive(): recursion detected");
+    return;
   }
 
   for (ArrayIter iter(arr2); iter; ++iter) {
     Variant key(iter.first());
     const Variant& value(iter.secondRef());
@@ -397,11 +400,13 @@ static void php_array_merge_recursive(PointerSet &seen, bool check,
     } else if (arr1.exists(key, true)) {
       // There is no need to do toKey() conversion, for a key that is already
       // in the array.
       Variant &v = arr1.lvalAt(key, AccessFlags::Key);
       auto subarr1 = v.toArray().copy();
-      php_array_merge_recursive(seen, v.isReferenced(), subarr1,
+      php_array_merge_recursive(seen,
+                                couldRecur(v, subarr1),
+                                subarr1,
                                 value.toArray());
       v.unset(); // avoid contamination of the value that was strongly bound
       v = subarr1;
     } else {
       arr1.setWithRef(key, value, true);
@@ -564,28 +569,34 @@ static void php_array_replace(Array &arr1, const Array& arr2) {
   }
 }
 
 static void php_array_replace_recursive(PointerSet &seen, bool check,
                                         Array &arr1, const Array& arr2) {
-  if (check) {
-    if (seen.find((void*)arr1.get()) != seen.end()) {
-      raise_warning("array_replace_recursive(): recursion detected");
-      return;
-    }
-    seen.insert((void*)arr1.get());
+  if (arr1.get() == arr2.get()) {
+    // This is an optimization, but it also avoids an assert in
+    // setWithRef (Variant::setWithRef asserts that its source
+    // and destination are not the same).
+    // If the arrays are self recursive, this does change the behavior
+    // slightly - it skips the "recursion detected" warning.
+    return;
+  }
+
+  if (check && !seen.insert((void*)arr1.get()).second) {
+    raise_warning("array_replace_recursive(): recursion detected");
+    return;
   }
 
   for (ArrayIter iter(arr2); iter; ++iter) {
     Variant key = iter.first();
     const Variant& value = iter.secondRef();
     if (arr1.exists(key, true) && value.isArray()) {
       Variant &v = arr1.lvalAt(key, AccessFlags::Key);
       if (v.isArray()) {
         Array subarr1 = v.toArray();
         const ArrNR& arr_value = value.toArrNR();
-        php_array_replace_recursive(seen, v.isReferenced(), subarr1,
-                                    arr_value);
+        php_array_replace_recursive(seen, couldRecur(v, subarr1),
+                                    subarr1, arr_value);
         v = subarr1;
       } else {
         arr1.set(key, value, true);
       }
     } else {
diff --git a/hphp/test/slow/array_functions/self_recursive.php b/hphp/test/slow/array_functions/self_recursive.php
new file mode 100644
index 00000000000..09920767439
--- /dev/null
+++ b/hphp/test/slow/array_functions/self_recursive.php
@@ -0,0 +1,20 @@
+<?php
+
+function test($g) {
+  $GLOBALS['g'] = $GLOBALS;
+
+  array_replace_recursive($GLOBALS, $g);
+
+  $GLOBALS['g'] = $GLOBALS;
+  array_merge_recursive($GLOBALS, $g);
+}
+
+function main() {
+  $a = array();
+  $a['g'] = &$a;
+
+  test($a);
+  test($GLOBALS);
+}
+
+main();
diff --git a/hphp/test/slow/array_functions/self_recursive.php.expectf b/hphp/test/slow/array_functions/self_recursive.php.expectf
new file mode 100644
index 00000000000..0a3eff14b49
--- /dev/null
+++ b/hphp/test/slow/array_functions/self_recursive.php.expectf
@@ -0,0 +1,12 @@
+
+Warning: array_replace_recursive(): recursion detected in %s/test/slow/array_functions/self_recursive.php on line 6
+
+Warning: array_merge_recursive(): recursion detected in %s/test/slow/array_functions/self_recursive.php on line 9
+
+Warning: array_merge_recursive(): recursion detected in %s/test/slow/array_functions/self_recursive.php on line 9
+
+Warning: array_merge_recursive(): recursion detected in %s/test/slow/array_functions/self_recursive.php on line 9
+
+Warning: array_merge_recursive(): recursion detected in %s/test/slow/array_functions/self_recursive.php on line 9
+
+Warning: array_merge_recursive(): recursion detected in %s/test/slow/array_functions/self_recursive.php on line 9

Vulnerable code:   if (check) {
    if (seen.find((void*)arr1.get()) != seen.end()) {
      raise_warning("array_merge_recursive(): recursion detected");
      return;
    }
    seen.insert((void*)arr1.get());
      php_array_merge_recursive(seen, v.isReferenced(), subarr1,
  if (check) {
    if (seen.find((void*)arr1.get()) != seen.end()) {
      raise_warning("array_replace_recursive(): recursion detected");
      return;
    }
    seen.insert((void*)arr1.get());
        php_array_replace_recursive(seen, v.isReferenced(), subarr1,
                                    arr_value);
Fixed code: static bool couldRecur(const Variant& v, const Array& arr) {
  return v.isReferenced() ||
    arr.get()->kind() == ArrayData::kGlobalsKind ||
    arr.get()->kind() == ArrayData::kProxyKind;
}

  if (check && !seen.insert((void*)arr1.get()).second) {
    raise_warning("array_merge_recursive(): recursion detected");
    return;
      php_array_merge_recursive(seen,
                                couldRecur(v, subarr1),
                                subarr1,
  if (arr1.get() == arr2.get()) {
    // This is an optimization, but it also avoids an assert in
    // setWithRef (Variant::setWithRef asserts that its source
    // and destination are not the same).
    // If the arrays are self recursive, this does change the behavior
    // slightly - it skips the "recursion detected" warning.
    return;
  }

  if (check && !seen.insert((void*)arr1.get()).second) {
    raise_warning("array_replace_recursive(): recursion detected");
    return;
        php_array_replace_recursive(seen, couldRecur(v, subarr1),
                                    subarr1, arr_value);
<?php

function test($g) {
  $GLOBALS['g'] = $GLOBALS;

  array_replace_recursive($GLOBALS, $g);

  $GLOBALS['g'] = $GLOBALS;
  array_merge_recursive($GLOBALS, $g);
}

function main() {
  $a = array();
  $a['g'] = &$a;

  test($a);
  test($GLOBALS);
}

main();

Warning: array_replace_recursive(): recursion detected in %s/test/slow/array_functions/self_recursive.php on line 6

Warning: array_merge_recursive(): recursion detected in %s/test/slow/array_functions/self_recursive.php on line 9

Warning: array_merge_recursive(): recursion detected in %s/test/slow/array_functions/self_recursive.php on line 9

Warning: array_merge_recursive(): recursion detected in %s/test/slow/array_functions/self_recursive.php on line 9

Warning: array_merge_recursive(): recursion detected in %s/test/slow/array_functions/self_recursive.php on line 9

Warning: array_merge_recursive(): recursion detected in %s/test/slow/array_functions/self_recursive.php on line 9