本帖最后由 kokoa_kira 于 2022-8-19 13:15 编辑
异步方块更新和落沙替换漏洞——获得Minectraft生存模式中所有[1]不可获得物品的一大步[2]
By coolmann24 8/27/20
以下是从 EarthComputer [4] 的视频里借来的相关的伪代码： 在一个方块执行创建它的掉落实体的计划刻事件时，游戏会检查一下，确保这个方块还在原处。不过在决定到底创建哪种掉落方块实体之前，游戏会再一次从世界上获取这个方块。如果我们能在检查这个方块完成后（即“if block is sand”后），游戏重新获取这个方块之前，把这个方块替换掉，我们就能够创建任何方块的掉落方块实体，而不仅仅是沙子、沙砾、混凝土粉末等。当掉落方块实体被摧毁后（比如落在一个火把上），它们都 [5]会以它们的物品形式掉落，使得我们可以获得许多生存中通常无法获得的方块，比如基岩、刷怪笼等。 EarthComputer 提到也许可以靠多线程来达到这一目的，但是这样的成功率小到几乎不可能。 这里我会介绍一种在 Minecraft 游戏主线程外异步加载区块并且产生链式方块更新的技术。这使得我们可以在游戏主线程外的另一个线程改变世界上的方块，并创造竞态条件（ https://en.wikipedia.org/wiki/Race_condition），这样从主线程的角度看，基于代码的执行时间，我们能在任意时间点改变世界上的方块。这种异步区块加载的方法已经在一个普通的、没有加模组的原版 Minecraft 1.12.2 实例中测试过并证实可行 [6]，在一个稍微修改过的 Minecraft 版本中，我成功地用这个技术展示了落沙替换漏洞。我看不出有什么明显的因素能阻碍我们在没有修改过的 Minecraft 中使用这种方法实现落沙替换，尽管在实践起来这可能会有点困难。 但首先，我们需要谈一谈平行宇宙。
Minecraft 将加载过的区块储存在一个 hash map [7]（ https://en.wikipedia.org/wiki/Hash_table）中。 这个地图的键是通过将该区块的X轴的32位整数和Z轴的32位整数组合成一个64位含符号的整数来创建的。 在 Java 中，这个64位的整数是一个原始类型，被称为 long。Minecraft 采用了FastUtil [8] 这个库来实现这个hash map，其中有个特别的方法叫做 Long2ObjectOpenHashmap [9] （it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashmap）。Long2ObjectOpenHashmap 是一个经典的开放 hash map 实现方法。但是它也不支持多线程。
这是从谷歌上找到的 rehash 的例子。从这张图上我们并不能确切地知道 Long2ObjectOpenHashmap 干了什么。 一个 rehash 的实例可以是 Long2ObjectOpenHashMap 有(>13)/17个元素，它将 rehash 到 33 的大小 [11]
Hash map 中最后一个位置是为一种特殊情况保留的，即当键值等于零时。在 Minecraft 中，这对应着区块(0, 0)。键数组中的默认值是零，所以如果零键没有被明确地单独管理，可能会发生不正确的键匹配。简单来讲，这意味着零键+值被明确地存储在其相应数组的最终索引中。如果目前的大小是 33，那么它的零基索引 [12]则是 32。 当 hash map 加载时，键将用以下函数来生成地图索引 [13]，这在FastUtil中被称为“mix”。 请注意，哈希结果是一个 64 位的数字，这个数字可能大得无法被 hash map 装下（也可能是负整数太小）。这也就是为什么 Long2ObjectOpenHashmap 维护了一个叫做掩码 [14]的部分，它的值等于地图容量减去 2 （15， 31，63，127…）。 这些数字共同拥有一个独特的属性：它们都是二的幂减一，作为二进制的数字，它们的前导位 [15] （MSB [16]）是零，所有的后导位 [17] （LSB [18]）是 1。这是很有用的一个东西，它使得 key 与 mask 按位与运算（ https://en.wikipedia.org/wiki/Bitwise_operation）能够获得小于等于数组大小 -1 的数组下标（[0-15],[0-31]...）。这也使得带掩码进行的 按位与操作不能访问储存零的键/值数组中的最终索引。
我们先撇开 Long2ObjectOpenHashmap 不谈， Minecraft 中有一个多线程代码的入口。当一个染色玻璃块在世界中被放置或破坏时，一段特殊的代码将会被执行，这与更新信标光束有关。
这个名为 updateColorAsync 的方法被调用，一个 Runnable 被提交到一个名为 DOWNLOADER_EXECUTOR 的线程池。因此，这个 Runnable 将在 Minecraft 游戏主线程之外执行。如果我们能以某种方式在这个执行线程中加载一个区块，我们将能够生成一个异步方块更新链 [19]使我们最终能够执行落沙替换。这就是为什么要注意对 getBlockState 的调用。如果一个区块没有被加载（这和 Long2ObjectOpenHashmap 无关），并且对 getBlockState 的调用被执行，那么游戏将加载该区块。这种技术被用于生成猪的刷怪笼中（ https://www.youtube.com/watch?v=cVvB53sWETg）。唯一的问题是，这个 runnable 将（几乎总是）在它被提交后立即执行，而 getBlockState 的调用只在彩色玻璃被放置或移除后立即执行，所以这个区块必须已经被加载。尽管我和其他人想尽办法尝试了修改这个线程的执行延迟/时间，以尝试在这个 Runnable 与它所有的 getBlockState 被调用完之前以任何方式在主线程卸载这个区块。然而这些尝试都失败了。但是谢天谢地，实际上我们根本不需要卸载这些区块。
回到 Long2ObjectOpenHashmap 上来。下面是 hash map rehash 的源码。
代码生成新的键和值数组，更新后的数组大小为 2x 或 1/2x(+1)，将现有数组中的所有元素 rehash 到它们。在最后，引用的方法被更新以重定向它们。 当染色玻璃/信标线程进行 getBlockState 调用时，它执行了对 Long2ObjectOpenHashmap 的 get(Iong) 方法的调用（用 chunk key ）。下面是 get(long)的源代码。
想象一下这样的场景：在主线程上，我们通过移除一个染色玻璃块来启动对 updateColorAsync 的调用，紧接着，仍然在主线程上，一个方块更新引起了区块加载。假设我们有 192 个加载了 256（+1）容量的 hash map。在从文件中加载或生成一个新的区块（第 193 个）后，这个区块试图通过 put() 调用放置在地图中，并导致地图需要 rehash （>3/4）容量到512（+1）。如果做得对的话，由于没有提供同步保护，在执行信标线程的 get() 调用的同一时刻，这个对 rehash 的调用将在游戏主线程中执行。让我们仔细看看这些代码片断中的一些片段。 rehash:
Get:
试着回忆一下我们之前关于掩码的讨论。在我们的 rehash 方案中，掩码从十进制的 255，二进制的…00011111111，到十进制的 511，二进制的…00011111111。另外注意这里，掩码在键和值数组的引用之前被更新。在 Get 开始时，本地键引用被分配给当时的成员键引用，所以它仍然会有旧的键数组，而不是来自 Rehash 的新键数组。想一想在 Rehash 中掩码被重新分配后的确切时刻。现在 maxFill() 正在主线程中执行。看看现在的 get() 片段。假设我们现在在 beacon 线程中对key[]进行访问，mask 被更新为 Rehash 的新值，但 key[] 没有被更新。与哈希键的按位与运算被执行，从右边开始的第八位以前是被屏蔽的，现在不是了，我们访问旧键数组之外的元素，得到 ArrayIndexOutOfBoundsException…线程终止了，没有其他事情发生。 除了它没有。我们删除染色玻璃的那个区块的哈希键的最后几位刚好等于 100000000。这意味着这个键以前是用旧的掩码值指向雩索引的，但现在用新的掩码指向 256 索引。还记得需键的特殊情况吗？旧的键数组实际容量为 257，使 256 成为有效的索引！
信标线程在索引 256 处看到的键值是 0，因为那里没有存储任何区块（我们的区块实际上存储在索引 0 处[也可能是由于碰撞导致的其他地方]）。“哦，这个区块没有被加载，因为这里啥也冇！。我需要加载这个区块。” 即使该区块已经被加载，信标线程要么从文件中加载该块，要么生成一个新区块。让我们假设该块处于这样一种状态，即世界装饰被调用。我们可以很容易地从这个区块的世界装饰中引导出一个方块的更新链。最终，执行一个落沙替换。
在测试中，我能够相当可靠地执行这种异步区块加载技术，考虑到它需要如此严格的竞态条件，大约有>5%的成功率。无论如何，这确实需要大量的其他要求和我创造的理想化条件，我不会在这里讨论。我将很快发布一个更深入的解释视频，详细介绍你在我的预告视频中看到的内容。 如果你感到好奇，在预告中，异步加载是完全合法的，但我在修改过的 Minecraft 版本的每个线程中，在特定的时间添加了一些间隙，以确保单独的落沙替换竞赛条件可靠地发生。那次录像 [20]是第一次成功进行的落沙替换（尽管有上述的“骗局”）。
[7] map就是用于存储键值对（<key,value>）的集合类，也可以说是一组键值对的映射（数学概念）。注意，我这里说的只是map的概念，是为了通俗易懂，面试时候方便记忆，但是你自己一定要明白，在java中map是一个接口，是和collection接口同一等级的集合根接口。map就是用于存储键值对（<key,value>）的集合类，也可以说是一组键值对的映射（数学概念）。注意，我这里说的只是map的概念，是为了通俗易懂，面试时候方便记忆，但是你自己一定要明白，在java中map是一个接口，是和collection接口同一等级的集合根接口。
[8] fastutilfastutil是扩展了Java标准集合框架（Map、List、Set；HashMap、ArrayList、HashSet）的类库，提供了特殊类型的map、set、list和queue；fastutil能够提供更小的内存占用，更快的存取速度；我们使用fastutil提供的集合类，来替代自己平时使用的JDK的原生的Map、List、Set，好处在于fastutil集合类，可以减小内存的占用，并且在进行集合的遍历、根据索引（或者key）获取元素的值和设置元素的值的时候，提供更快的存取速度；fastutil也提供了64位的array、set和list，以及高性能快速的，以及实用的IO类，来处理二进制和文本类型的文件。
[10] “负载系数”原文为“Load factor”。
[11] “一个散列的实例可以是Long2ObjectOpenHashMap有(>13)/17个元素，它将rehash到33的大小”原句为“An example rehash could be Long2ObjectOpenHashMap having (>13)/17 elements and it rehashing to a size of 33.”。
[12] “零基索引”原文为“zero-based index”。
[13] “键将用以下函数来生成地图索引”原文为“key will be hashed with the following hash function to generate a map index”。
[15] “前导位”原文为“leading bits”。
[16] MSB是Most Significant Bit的缩写，指最高有效位。在二进制数中，MSB是最高加权位。与十进制数字中最左边的一位类似。通常，MSB位于二进制数的最左侧，LSB位于二进制数的最右侧。
[17] “后导位”原文为“trailing bits”。
[18] LSB是Least Significant Bit的缩写，指最低有效位。对于一个给定的数据串（整数），如二进制的1001或者十进制351，其最低有效位就是拥有最小单位数值的那一位。比如二进制1001的最右一位，拥有数值1，在该整数中代表最低位，该位的值可以决定整数是奇数（为1）还是偶数（为0）。十进制数同理。
[19] “异步方块更新链”原文为“asynchronous block update chain”。
翻译: kokoa_kira@Fishing Craft 校对: P31pr@Fishing Craft
参考资料
| 
发表于 2022-8-10 16:01:08
提升卡
观察者
楼主
粤公网安备 44200002445329号 | 由 木韩网络 提供云服务 | GMT+8, 2024-4-29 11:57