php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #81399 integer overflow in zend_list_insert
Submitted: 2021-08-30 13:49 UTC Modified: 2021-08-31 09:49 UTC
From: otto dot hollmann at suse dot com Assigned: cmb (profile)
Status: Duplicate Package: Reproducible crash
PHP Version: Irrelevant OS: SLE15-SP2
Private report: No CVE-ID: None
View Add Comment Developer Edit
Welcome! If you don't have a Git account, you can't do anything here.
You can add a comment by following this link or if you reported this bug, you can edit this bug over here.
(description)
Block user comment
Status: Assign to:
Package:
Bug Type:
Summary:
From: otto dot hollmann at suse dot com
New email:
PHP Version: OS:

 

 [2021-08-30 13:49 UTC] otto dot hollmann at suse dot com
Description:
------------
When running phoronix stress tests we observed many segfaults (see below backtrace) which started occurring after few hours/days regardless of the selected test. After many weeks of investigating we have managed to single out the root cause - integer overflow in the 'index' variable in the following function:

ZEND_API zval* ZEND_FASTCALL zend_list_insert(void *ptr, int type)
{
      int index;
      zval zv;

      index = zend_hash_next_free_element(&EG(regular_list));
      if (index == 0) {
            index = 1;
      }
      ZVAL_NEW_RES(&zv, index, ptr, type);
      return zend_hash_index_add_new(&EG(regular_list), index, &zv);
}

Function 'zend_hash_next_free_element' is a simple function returning 'executor_globals.regular_list.nNextFreeElement' which is type zend_long (long int) which is then stored in variable 'index' of type int and later is passed into 'zend_hash_index_add_new' which accepts zend_ulong (unsigned long int). In fact, we are doing following conversion: long int => int => unsigned long int.

The problem occurs when executor_globals.regular_list.nNextFreeElement reaches value 0x80000000 (2147483648), which is stored in index as *negative* value 0x80000000 (-2147483648) and later is passed as 0xffffffff80000000 (18446744071562067968) which somewhere later results in segfault in 'zend_mm_alloc_small'.


Well, this could be easily fixed, but the similar issue occurs on several other places and my question is. Do we want to fix it for those big numbers (long int) or only add some checks to report that something overflowed? Because it would involve huge code changes, increase size of some structures, etc.


Some examples of potential overflow:

static zend_always_inline zval *_zend_hash_index_add_or_update_i(HashTable *ht, zend_ulong h, zval *pData, uint32_t flag)
{
      uint32_t nIndex;
      uint32_t idx;
      Bucket *p;
...
                  }
                  ht->nNextFreeElement = ht->nNumUsed =   h + 1;
//                    ^^ zend_long           ^^ uint32_t  ^^ zend_ulong
                  goto add;
            } else if ((h >> 1) < ht->nTableSize &&
                       (ht->nTableSize >> 1) < ht->nNumOfElements) {
                  zend_hash_packed_grow(ht);
                  goto add_to_packed;

So we need 'nNumUsed' to be type of zend_long, but this change will cause another overflow (in the same function):


            ZEND_HASH_IF_FULL_DO_RESIZE(ht);          /* If the Hash table is full, resize it */
      }

      idx = ht->nNumUsed++;
//              ^^ zend_long
//    ^^ uint32_t
      nIndex = h | ht->nTableMask;
//             ^^ zend_ulong
//    ^^ uint32_t


And this way we can go really deep and make a lot of changes. Also there is a lot of comparison between int and long int which may lead to additional problems.

Test script:
---------------
phoronix-test-suite install cachebench
export TOTAL_LOOP_TIME="10080"
export PTS_CONCURRENT_TEST_RUNS="4"
export PTS_NO_REBOOT_ON_NETWORK_FAILURE="1"
export LIMIT_STRESS_GRAPHICS_TESTS_COUNT="2"
phoronix-test-suite stress-run cachebench


And wait tens of hours/few days (depending on the machine).
However the following hack can be used to reproduce the issue faster (within few minutes):

Zend/zend_list.c:
ZEND_API void zend_init_rsrc_list(void)
{
      zend_hash_init(&EG(regular_list), 8, NULL, list_entry_destructor, 0);
-     EG(regular_list).nNextFreeElement = 0;
+     EG(regular_list).nNextFreeElement = 0x7fff0000;
}

Actual result:
--------------
#0  zend_mm_alloc_small (bin_num=2, heap=0x7fa409000040) at /root/php-src/Zend/zend_alloc.c:1256
#1  _emalloc_24 () at /root/php-src/Zend/zend_alloc.c:2468
#2  0x00000000006c376a in zend_list_insert (ptr=ptr@entry=0x7fa408a4b380, type=2) at /root/php-src/Zend/zend_list.c:41
#3  0x00000000006c3829 in zend_register_resource (rsrc_pointer=rsrc_pointer@entry=0x7fa408a4b380, rsrc_type=<optimized out>) at /root/php-src/Zend/zend_list.c:90
#4  0x00000000006628ff in _php_stream_alloc (ops=ops@entry=0x1402a20 <php_stream_stdio_ops>, abstract=0x7fa408da8240, persistent_id=persistent_id@entry=0x0, mode=0xfd5f48 "r") at /root/php-src/main/streams streams.c:312
#5  0x00000000006680f7 in _php_stream_fopen_from_fd_int (fd=<optimized out>, mode=<optimized out>, persistent_id=persistent_id@entry=0x0) at /root/php-src/main/streams/plain_wrapper.c:190
#6  0x000000000066974b in _php_stream_fopen_from_fd (fd=<optimized out>, mode=<optimized out>, persistent_id=persistent_id@entry=0x0) at /root/php-src/main/streams/plain_wrapper.c:276
#7  0x0000000000637bdb in zif_proc_open (execute_data=<optimized out>, return_value=0x7fa40901d510) at /root/php-src/ext/standard/proc_open.c:1284
#8  0x000000000071370c in ZEND_DO_ICALL_SPEC_RETVAL_USED_HANDLER () at /root/php-src/Zend/zend_vm_execute.h:1296
#9  execute_ex (ex=0x7fa409000040) at /root/php-src/Zend/zend_vm_execute.h:54659
#10 0x00000000006a2a3a in zend_call_function (fci=0x7fa409123c60, fci@entry=0x7ffea595c270, fci_cache=fci_cache@entry=0x7ffea595c250) at /root/php-src/Zend/zend_execute_API.c:885
#11 0x00000000006a2ddd in zend_call_known_function (fn=0x7fa4091be928, object=object@entry=0x7fa409002780, called_scope=<optimized out>, retval_ptr=retval_ptr@entry=0x7fa40901cff0, param_count=param_count@entry=1, params=params@entry=0x7ffea595c2d0, named_params=0x0) at /root/php-src/Zend/zend_execute_API.c:959
#12 0x0000000000734659 in zend_call_known_instance_method (params=0x7ffea595c2d0, param_count=1, retval_ptr=0x7fa40901cff0, object=0x7fa409002780, fn=<optimized out>) at /root/php-src/Zend/zend_API.h:666
#13 zend_call_known_instance_method_with_1_params (param=0x7ffea595c2d0, retval_ptr=0x7fa40901cff0, object=0x7fa409002780, fn=<optimized out>) at /root/php-src/Zend/zend_API.h:678
#14 zend_std_call_getter (zobj=zobj@entry=0x7fa409002780, prop_name=prop_name@entry=0x7fa408f0f258, retval=retval@entry=0x7fa40901cff0) at /root/php-src/Zend/zend_object_handlers.c:197
#15 0x00000000007361aa in zend_std_read_property (zobj=0x7fa409002780, name=0x7fa408f0f258, type=0, cache_slot=<optimized out>, rv=0x7fa40901cff0) at /root/php-src/Zend/zend_object_handlers.c:660
#16 0x00000000006d2a64 in ZEND_FETCH_OBJ_R_SPEC_TMPVAR_CONST_HANDLER () at /root/php-src/Zend/zend_vm_execute.h:15391
#17 0x0000000000712fd1 in execute_ex (ex=0x7fa409000040) at /root/php-src/Zend/zend_vm_execute.h:56242
#18 0x000000000071a594 in zend_execute (op_array=0x7fa40908c100, return_value=0x0) at /root/php-src/Zend/zend_vm_execute.h:59014
#19 0x00000000006b0124 in zend_execute_scripts (type=type@entry=8, retval=retval@entry=0x0, file_count=file_count@entry=3) at /root/php-src/Zend/zend.c:1789
#20 0x000000000064e8d9 in php_execute_script (primary_file=primary_file@entry=0x7ffea595e930) at /root/php-src/main/main.c:2505
#21 0x00000000007874e1 in do_cli (argc=4, argv=0x2a6fad0) at /root/php-src/sapi/cli/php_cli.c:965
#22 0x000000000044803b in main (argc=4, argv=0x2a6fad0) at /root/php-src/sapi/cli/php_cli.c:1366

(gdb) p heap->free_slot
$1 =  {0x7fa408ad7d48, 0x7fa408f13b60, 0x7fa408e7ede000, 0x7fa408d6a8e0, 0x7fa408d897d0,
       0x7fa408a2f660, 0x7fa408da5930, 0x7fa408b773c0, 0x7fa408affe60, 0x7fa408af9480,
       0x7fa409087e00, 0x7fa408b1ee80, 0x7fa408afd000, 0x7fa408da8540, 0x7fa408a4ba80,
       0x7fa408a93200, 0x7fa408d789c0, 0x7fa408fc0580, 0x7fa4090f3c40, 0x7fa408d18000,
       0x7fa408fe3200, 0x7fa408845600, 0x7fa408b8a380, 0x7fa408b89000, 0x7fa408801500,
       0x7fa408d4d000, 0x7fa408b24800, 0x7fa40908e800, 0x7fa408d27400, 0x7fa408d2d400}

(gdb) p/x executor_globals.regular_list.nNextFreeElement
$2 = 0x80000000

You can notice, that the address in heap on index bin_num=2 is shifted and obviously can not be accessed in function:
static zend_always_inline void *zend_mm_alloc_small(zend_mm_heap *heap, int bin_num ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
{
...
                zend_mm_free_slot *p = heap->free_slot[bin_num];
                heap->free_slot[bin_num] = p->next_free_slot;

Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2021-08-30 14:02 UTC] cmb@php.net
-Status: Open +Status: Duplicate -Assigned To: +Assigned To: cmb
 [2021-08-30 14:02 UTC] cmb@php.net
Yes, known issue (see bug #47396).  The proper solution is to get
rid of resources altogether, what is work in progress.
 [2021-08-30 14:17 UTC] nikic@php.net
It would make sense to me to at least throw a fatal error if the resource ID space overflows. That seems a lot better than simply crashing.

Expanding the resource space should largely be a matter of using zend_long in zend_resource. Changes to the hash table implementation are not required -- the places you indicated are fine (one deals with packed hashes only, and the other one is just a hash that can be truncated). This is principally a viable change (though not for any stable branches).
 [2021-08-30 14:33 UTC] nikic@php.net
I've opened https://github.com/php/php-src/pull/7428 for throwing the error.
 [2021-08-31 09:42 UTC] otto dot hollmann at suse dot com
Thank you for your opinion and pointing on duplicate bug. I agree, that it should be somehow fixed. But what about simply declare 'index' as zend_long? Function '_zend_hash_index_add_or_update_i' already accepts zend_ulong and this change seems to resolve original phoronix segfault (The test successfully finished after one week without any crash or error).
Here is my pull request: https://github.com/php/php-src/pull/7437

And if '_zend_hash_index_add_or_update_i' can not deal with zend_long, the exception should be there, because this function can be called from many others functions. Or am I wrong?
 [2021-08-31 09:49 UTC] nikic@php.net
Changing int -> zend_long in just that place will allow the resource to be successfully created. However, the zend_resource structure stores the resource ID as an int, which means that it will be truncated there, and code inspecting resource IDs will misbehave (as the ID now points to a different or non-existent resource).

I've submitted https://github.com/php/php-src/pull/7436 to change the type in zend_resource, but this is an ABI breaking change, and as such not eligible for stable releases.
 
PHP Copyright © 2001-2021 The PHP Group
All rights reserved.
Last updated: Thu Oct 28 17:03:35 2021 UTC