获得MC生存模式中所有不可获得物品的一大步——异步方块更新和下落方块替换漏洞

这篇文章是基于coolmann24的文档撰写的:链接

这篇文章讲解了1.12中获取任意方块背后的原理——一种在MC游戏主线程外异步加载区块并且产生链式方块更新的技术。这使得基于下落实体替换的物品获取思路成为可能。


这种异步区块加载的方法,coolmann24已经在一个普通的、没有加MOD的原版Minecraft1.12.2实例中测试过并证实可行。在一个稍微修改过的Minecraft版本中,他成功地用这个技术展示了下落方块交换漏洞(BV1Ev411174f)。他认为这个方法完全可以在纯净原版MC中实现,尽管实践起来可能会有点困难。


由于原文直接翻译可能会过于硬核,普通玩家难以理解,这里我直接基于我自己对于文章的理解+自行翻看1.12.2游戏源码获得的信息重新撰写+魔改了这篇文章,并添加了简单概括的版本。


玩家可以自行选择全文阅读或者只阅读思路概括部分。

 

简单概括版本:

由于Mojang在编写「创建下落实体」的代码中有一点疏漏+下落实体掉落到火把之类的方块上会直接掉落物品,不做额外检查,使得获取各种“不可能获取的方块”成为可能。

 

首先,游戏创建下落实体时,会按照如下顺序执行代码:

    ①先获取当前方块

    ②判断是不是沙子,不是的话直接退出

    ③再次获取当前方块

    ④创建这个方块的下落实体

如果我们想办法在中间插入一条「将当前方块替换为刷怪笼」,那么在中获取的方块就是刷怪笼,在中就会创建刷怪笼的下落实体。落到火把上即可变为刷怪笼掉落物


由于在原本的代码中,没有机会在中间替换掉这个方块,所以必须要利用游戏的第二个线程来实现这步。然而MC是一个基本以单线程为主的游戏,很少会有多线程,经过一番查找之后,Earthcomputer找到了一段关于信标的代码会启用一个新的线程


我们知道在信标上添加染色玻璃会使光柱的颜色发生变化,这段代码就是用来实现这点的。具体的,当我们放置/破坏染色玻璃时,游戏会创建一个新的线程用来检查需不需要变换信标的颜色。其中需要获取染色玻璃下方的方块,并判断是不是信标之类的。


「获取下方方块」时,游戏需要从区块中获取方块信息。所以,思路就是让这个方块所在的区块是一个未加载区块,那么游戏为了获取这个方块的信息就得先加载这个区块。我们想办法让「加载区块」这一步通过世界装饰等方法触发一条更新链,使得原来的沙子变为其他方块(如基岩、刷怪笼),即可完成一手偷天换日。


不过真正困难的点在于,玻璃下方的方块必然和这个玻璃在一个区块,既然你都可以放置/破坏这个染色玻璃了,那么这个区块一定已经被加载了。并且放置/破坏染色玻璃之后很快就会调用新线程,时间间隔太短,不可能先卸载玻璃所在区块,然后再让新线程加载。估计这也是为什么Earthcomputer在视频中说“通过多线程获取基岩几乎是不可能的”。


然而Coolmann想出了解决方法。在MC中,区块是用哈希表(hashmap)存储的,可以通过加载区块,在触发游戏主线程hashmap扩容的同时触发信标线程的「获取方块」函数。这会造成一种双线程竞争冒险的情况。有一定几率能使得信标线程的「获取方块」函数认为玻璃所在的区块还没有被加载(实际已经加载了)。因此,游戏会再次加载玻璃所在区块,我们利用这个重复的区块加载,在信标线程中触发一条更新链,刚好在主线程创建下落实体时替换掉沙子,就可以成功创建非重力方块的下落实体。


深入讲解版本:

接下来是比较硬核的深入讲解,需要具备一定的编程基础知识。


 一、 哈希表(hashmap)是什么

首先由于区块存储用到了哈希表(hashmap),我们基于MC中用于储存已加载区块的hashmap并结合实例讲解一下hashmap是什么。(已经知道的话可以跳过)


 简单地讲,hashmap是一种较高效的数据存储结构,相比其他数据结构,它的查询时间复杂度很低,几乎只有O(1),所以它在海量数据处理中有着广泛应用。


想象这样一种情况,你有很多书需要放到一个带有位置编号的书架上。当然最简单的方法就是从第一个空位开始依次一本一本地放下去。然而如果你想要查找名字叫《A》的这本书时,你需要从左到右一个一个看书名,才能找到它,速度太慢。并且书的数量越多,这个速度就越慢。


不过如果你构造这样一个函数F(X),其中X是书名,F(X)直接根据书名的字母做一些神奇的运算,给出它安排好的书架编号。这样你每次放书只需要按照函数给出的编号放,每次拿书只需要再根据书名用函数计算出编号,直接拿即可。大大降低了找书的复杂程度,这就是hashmap的基本思路。


在实际程序中,书架就是你用来存数据的数组,书存放的编号就是数组下标index,用来查找的书名就是key,这个将书名映射到编号的函数就是hash函数,而书中你需要查找的文章就是value。


这个神奇的hash算法会尽可能的让不同key输入后指向不同的位置,即让结果尽可能均匀分布。然而还是有可能会出现两个不同的key指向一个地址的情况。这种情况下,程序会直接将数据顺序存储到下一个空白位置。(还有基于链表结构的hashmap,不过MC中使用的是顺序存储式的,所以就不讲了。具体的,游戏用于储存已加载区块使用的是FastUtil库的it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashmap)


二、MC中的Long2ObjectOpenHashmap存储结构

好的,我们回到MC中的实际情况。在MC中,被加载的区块是存储在hashmap中的,区块的坐标是key,区块的数据是value。

在MC用于储存已加载区块的hashmap中,由key和value构成的数组为其核心数据存储位置,这里我们假设的有一个大小为4的hashmap,key[5]和value[5]是其存储数组,index代表数组下标,如下:


首先,出于性能考虑,hashmap的大小永远会是2的幂。但是我们可以看到这个“大小为4”的hashmap实际上的大小是4+1=5。之所以会多一个元素,是因为MC中使用的hashmap用“key=0”作为key数组的默认值,用来表示当前位置没有存储数据。如果你要存入的数据的key刚好是0(MC中只有区块(0,0)的key=0),那么就会发生混乱。


所以hashmap会对key=0的情况进行特判,并将数据存储在数组最后多出的一位空间上,并单独用一个变量“containsNullKey”作为flag来判断数组中存不存在key=0的项。

insert()中对于key=0的特判


插入区块(0,0)后的效果

所以实际使用中key、value的数组大小永远会是2的幂+1(如17,33,65,129)


三、实际存储/查询hashmap中区块的步骤

假设我们需要将一个区块存入hashmap,具体程序是如何实现的呢?

首先,游戏会将区块32位的X和Z坐标串联起来,组成一个64位的long型数字,作为这个区块的key,如下:

然后,我们需要根据这个key找到其对应的数组中存储位置pos(index)

如果这个key==0,会直接将pos对应到当前hashmap大小n

get()中key=0的特判

如果不为零,这个long型的key会被传入mix函数,对key进行hash

(LONG_PHI = 0x9E3779B97F4A7C15L)

(移位异或是为了确保hashmap较小时结果分布也能比较均匀,这里不做过多展开)


最后这个mix的结果会与当前的掩码mask做「与运算」,计算出该区块存储位置的数组下标pos:

 这里的mask永远是2的幂-1(如15,31,63,127),这样它的二进制就是“00000011111”这种形式的,一串“0”然后一串“1”。mask低位“1”的个数会随着当前数组的大小发生变化。


正如其名称,「掩码」就是把mix后的hash中的高位的“1”都去掉,确保最后的结果pos能够落在当前数组大小的范围内。


计算出key对应的数组下标pos之后,由于存在顺序存储的情况,程序会比对输入的key和数组中该位置的key。如果不相同则让pos+1,直到key相同或数组中key=0(该位置无数据),最后直接进行存取操作即可。


 四、哈希表扩容(rehash)

如果hashmap中的数据过多,不同key被映射到同一个index的概率就会上升,进而影响hashmap的查询效率。所以如果:

hashmap中的元素数量 >= 当前数组大小*(load factor)

load factor默认为0.75

就会触发rehash,将当前数组大小调整为原来的两倍。

同理如果小于3/16也会触发rehash缩小数组大小为当前的1/2。

这是google上的一张rehash示意图,展示的是一个大小为4的hashmap扩容为大小为8时的效果。这个并不能准确表示MC中使用的Long2ObjectOpenHashmap的rehash的实际效果,不过可以作为一个不错的参考。



五、「创建下落实体」中的漏洞

好的,基础知识都讲完了,终于可以进入正题了,一切都要从这段代码讲起:

上面的代码是从EarthComputer的视频里“借”来的相关的游戏伪代码。在一个方块执行创造它的掉落方块实体(falling block entity,比如说落沙实体)的计划刻事件时,游戏会检查一下,确保这个方块还在原处。不过在决定到底创建哪种掉落方块实体之前,游戏会再一次从世界上获取这个方块。这个「两次获取方块」的操作使得这段代码可以被加以利用。


如果我们能在这个方块获取完成后(即第一个“block =get from world”后),游戏重新获取这个方块之前,把这个方块替换掉,我们就能够创建任何方块的掉落方块实体,而不仅仅是沙子、沙砾、混凝土粉末等。


当掉落方块实体被摧毁后(比如落在一个火把上),它们(几乎)都会以它们的物品形式掉落,使得我们可以获得许多生存中通常无法获得的方块,比如基岩、刷怪笼等。


然而在这段代码中,并没有可以替换方块的机会,所以唯一的方法只能是利用多线程。


六、染色玻璃多线程

经过大佬们的一番查找,他们找到了一段可以利用的多线程代码——染色玻璃使信标变色的相关代码,如下:

当你放置、破坏染色玻璃时,这个方法updateColorAsync会被调用,用来检查是否需要将信标的光柱变色。其中将一个Runnable提交到名为DOWNLOADER_EXECUTOR的线程池。这就是我们要找的多线程了。


如果我们能在主线程运行到创建下落实体时,在这个线程中将沙子替换为其他方块就可以获取其他方块的下落实体,从而获取其物品形式。


注意这个getBlockState函数,如果这个玻璃所在区块没有被加载,为了获取玻璃下方的方块,查看它是否是信标,游戏会加载这个区块。(原版生存猪笼的视频中也用到了这个技巧:BV1Xx411y75P)我们再利用这个加载触发更新链替换掉沙子就可以了。


然而问题在于如果这个玻璃已经能够被放置/破坏的话,这个区块就已经被加载了。并且这里的新线程调用是紧跟在放置/破坏染色玻璃之后的,并且破坏玻璃所在阶段离区块卸载阶段较远,也就是说先卸载玻璃所在区块,然后再让新线程加载它基本是行不通的。


事实上coolmann24以及其他一些人都对这个方法进行了充分的尝试,不断调整这个Runnable的延时/时序,尝试在所有的getBlockState执行完之前把玻璃所在区块卸载掉,然而都失败了。


七、用多线程爆破hashmap

所以,我们现在的目标只有一个,就是让getBlockState函数认为玻璃所在区块未加载,让它加载区块。能加载区块才有可能替换沙子方块。


由于MC中使用的Long2ObjectOpenHashmap是不支持异步操作的,coolmann注意到了可以利用多线程漏洞,让游戏错误地认为玻璃所在区块没有被加载。


重点来了,我们再回过头来,看一下rehash的代码:

这段代码会生成新的两倍/一半大小(+1)的key以及value数组,并在最后将hashmap的key和value指向新的数组。


而当玻璃/信标线程中调用getBlockState时,游戏会调用hashmap的get函数来获取这个区块:

我们想象这样一种情况,首先我们在主线程中,通过放置/破坏染色玻璃调用updateColorAsync函数。然后紧接着,还是在主线程中,我们通过方块更新加载一个新的区块。我们假设在此之前,在一个大小为256(+1)的hashmap中,192个区块已经被加载了。当我们加载一个新区块时(从文件中取出一个区块或者生成一个新的),刚好是第193个区块。这个区块会被hashmap的put方法放入hashmap并触发哈希表扩容(rehash)。如果我们的延时控制的合适,由于hashmap没有异步保护,主线程在rehash的时候,刚好信标线程在调用hashmap的get函数。


让我们仔细看一下关键的代码片段。

Rehash:

Get:

我们来回忆一下刚才讲过的mask,在我们的这个例子中,mask会从二进制的255(...000,1111,1111)变成511(...001,1111,1111)从而将mix后的二进制多滤出一位。


注意rehash中会先更新mask,再更新key和value。而在get中,程序会先将当前hashmap的key给到函数中的局部变量key。所以这个key还是rehash前的老数组的。如果恰好在mask被赋予新值后,我们调用了Get这段代码,那么掩码mask会多滤出一位二进制,但是数组key用的还是原来的数组。所以这会造成数组越界并得到一个ArrayIndexOutOfBoundsException数组越界异常,然后就没有然后了.....


除非它刚好没有越界,如果经过mix的key值的二进制的低位刚好是“1,0000,0000”。那么在mask变更前,mask只有8个“1”,由于它后八位是“0”,它刚好是被存储在hashmap数组的0号位置上。而在mask更新为9个“1”之后,第九位的“1”被滤出来,让这个数变成了256。还记得hashmap对于key=0的特殊处理吗?为了处理key=0,数组大小会是2的幂+1,这使得这个下标没有越界,并且直接就对应到了老key数组的最后一号元素,也就是key=0的位置上!!


因为get函数获取的key=0,程序便认为这个区块没有被加载,从而尝试加载。虽然这个区块已经被加载了,信标线程还是会从保存的文件中获取它,或者生成一个新的区块。而如果这个区块刚好在可以触发世界装饰的状态,我们就可以利用这个加载,触发世界装饰,造成一条更新链,替换掉沙子方块。


八、附加信息

 coolmann利用这个方法做了一些测试,这个区块加载方法在>5%的尝试中是可用的,考虑到造成这个冲突需要的时序非常苛刻,这个数字已经不错了。然而在他的测试中还需要一些其他的前提,以及理想化的条件。他会在之后发布视频讲解他的预告视频中的一些细节。


在他的预告视频中(BV1Ev411174f),异步区块加载这部分是完全原版实现的,不过替换下落实体这部分是在合适的时机,在每个线程的代码加入了一些sleep实现的。并且这段预告视频是第一次成功实现下落实体替换的视频(在上述“作弊”的前提下)。


九、一些猜测

原文中并没有详细讲解这个区块加载是如何触发世界装饰和更新链的,由于玻璃区块已经加载,不好满足2x2区块第一次同时加载的触发世界装饰条件。我猜测可能还是需要利用区块保存抑制,让磁盘中没有这个区块,从而在信标线程再次加载区块时重新生成区块,触发世界装饰,然后在怼到BUD铁轨上面之类的。


十、高版本的更改

1.13给加载/保存/运算区块的方法加了线程同步锁,并且1.13无法再控制世界生成;1.14后区块机制被重写,信标线程部分代码被删除。这一系列的因素使得本文所述手段极有可能在高版本中无法使用。


总流程图:

最后附上我做的流程图,希望能够帮助大家比较清晰地理解整个时序过程

参考资料

【1】1.12.2 forge源码:

http://files.minecraftforge.net/maven/net/minecraftforge/forge/index_1.12.2.html

(阅读源码方法可以看教程:BV1w441197V5

【2】1.12 MCP源码:

http://www.modcoderpack.com

【3】Java HashMap工作原理及实现:

https://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/

【4】Long2ObjectOpenHashmap文档

http://fastutil.di.unimi.it/docs/it/unimi/dsi/fastutil/longs/Long2ObjectOpenHashMap.html

【5】竞争冒险现象https://baike.baidu.com/item/%E7%AB%9E%E4%BA%89%E5%86%92%E9%99%A9/1501348?fr=aladdin

https://zh.wikipedia.org/wiki/%E7%AB%B6%E7%88%AD%E5%8D%B1%E5%AE%B3


原文:coolmann24

研究&重新撰写:hiback

感谢LXYan的部分翻译

感谢Fallen_Breath的校对

本文为我原创

本文禁止转载或摘编

-- --
  • 投诉或建议
评论