孔阵列问题
JavaScript 中我最讨厌的“特性”之一就是“空数组”。如果你不确定这是什么，请看以下示例：
const array = [1, 2, 3];
这就是所谓的“压缩”数组。元素是连续的，并且数组由一种元素类型组成：number。
在 C++ 方面：当使用 V8（又名 Node.js）时，在底层，该数组实际上存储为
PACKED_SMI_ELEMENTS，这是一种在内存中存储小整数的方法，可以说是 V8 存储数组的众多方法中最有效的。
现在来看这行看似无害的代码：
array.push(3.14); // push a floating point number to the array.
PACKED_SMI_ELEMENTS在 C++ 端：你的数组刚刚在内存中从整数类型转换为PACKED_DOUBLE_ELEMENTS双精度浮点数类型。它发生了一些变化，但仍然保持紧凑的内存占用和良好的性能。这种转换是不可逆的。
JavaScript 方面没有任何变化。
接下来进入下一步：
array.push('Hello world!'); // push a string to the array
在 C++ 端：你的数组刚刚又一次被不可逆地转换了。这次是从
PACKED_DOUBLE_ELEMENTS`T` 数组转换为 `T` 数组PACKED_ELEMENTS。`T`PACKED_ELEMENTS数组可以存储任何 JavaScript 值；但与 SMI 或 Double 数组相比，它需要占用更多的内存空间来表示自身。
现在让我们继续执行下一行代码：
console.log(array.length); // 5
array[9] = true;
console.log(array.length); // 10
这在 JavaScript 中是允许的，对吧？你可以给数组中的任意索引赋值，数组就会被填充。那么在 C++ 端会发生什么呢？
在 C++ 端：你的数组又一次被不可逆地改变了，这次变成了
HOLEY_ELEMENTS。操作起来要慢得多；而且你也让 V8 的 JIT（即时编译器）优化变得更加困难，因为它将无法在很大程度上优化你的程序。值得注意的是，调用
new Array(n)`or`Array(n)总是会创建这种类型的数组，从而降低代码运行速度。
但为什么要止步于此呢？让我来介绍一下撒旦的特殊数据结构：
array[999] = 'HAIL SATAN! ♥'
在 C++ 端：你的数组刚刚从 变成了
HOLEY_ELEMENTS，DICTIONARY_ELEMENTS你召唤了一个无法再被驱逐的恶魔。让我直接引用V8的源代码：
// The "slow" kind. DICTIONARY_ELEMENTS,
从 JavaScript 的角度来看：你的数组变成了字典，或者换句话说：变成了一个普通对象。这是JavaScript 数组最糟糕的情况。
为什么这样做很危险：
- 这样的操作会悄无声息地完成，绝不会报错。
- 任何基于循环的枚举或序列化尝试都极有可能导致服务器崩溃。
- 数组的键将被自动转换为字符串。
- 数组仍将序列化为数组，而不是对象。（
JSON.stringify将尝试使用nulls 填充所有空索引） Array.isArray(array)DICTIONARY_ELEMENTS对于数组，将返回 true 。
如果你尝试调用JSON.stringify上面的数组，你会得到这样的结果：
[1,2,3,3.14,"Hello world!",null,null,null,null,true,null,null,null,null,null,null,null,null,null,null,null,null,null,...,null,null,null,null,"HAIL SATAN! ♥"]
这可能会被用来对付你：
以下是一个使用 Express 来操作待办事项列表的 REST API 示例：
// Naïve example of holey array potential vulnerability
class Todos {
constructor(username, items) {
this.username = username;
this.items = items || Todos.load(username);
}
// add a new todo
add(todo) {
this.items.push(todo);
return this.items.length - 1;
}
// update an existing todo
update(index, todo) {
// index is expected to be an integer
// we're making the mistake of accepting an arbitrary/unbounded index here though
// this operation will succeed silently, and node won't throw any errors with a huge index.
// e.g. if an attacker passes 10000000, the program won't crash or show signs of instability, the array will silently become "DICTIONARY_ELEMENTS".
this.items[index] = todo;
return index;
}
remove(index) {
return this.items.splice(index, 1);
}
// another common case:
// you're keeping a list of todos and want to give the user the ability to reorder items.
swap(i1, i2) {
const temp = this.items[i1];
this.items[i1] = this.items[i2];
this.items[i2] = temp;
}
// load a list of the user's previously saved todos
// we’re not using a database for simplicity’s sake
static load(username) {
const userPath = path.join('data', this.username + '.json');
if (fs.existsSync(userPath) {
return JSON.parse(fs.readFileSync(userPath, 'utf8'));
}
return [];
}
// this saves the array back to disk as JSON when the request is ending
// holey/dictionary arrays with absurd indices will pad empty ranges with `null`.
// this could result a multi-gigabyte file if passed a holey/dictionary array with a big enough (sparse) index in them. Most likely we’ll run out of memory first because the resulting string will be too big.
save() {
fs.writeFileSync(path.join('data', this.username + '.json'), JSON.stringify(this.items));
}
}
app.use((req, res, next) => {
// initialise/load previous todos
req.todos = req.todos || new Todos(req.session.username);
next();
});
// add new todo
app.post('/todos/new', (req, res, next) => {
if (req.body.payload)
res.json({ index: req.todos.add(req.body.payload) });
else
res.status(500).json({ error: 'empty input' });
});
/// update existing todo (vulnerable to unbound indices!)
app.post('/todos/:idx/update', (req, res, next) => {
if (req.body.payload)
res.json(req.todos.update(parseInt(req.params.idx, 10), req.body.payload));
else
res.status(500).json({ error: 'empty input' });
});
…
// save current todo list after request
// a better idea is to override res.end() via a thunk though.
app.use((req, res, next) => {
next();
req.todos.save();
});
以下是一个恶意请求示例：POST /todos/10000000/update payload="hi"
现在内存中存在一个看不见的问题（包含 10000000 个元素的字典数组），当请求结束时，它会尝试写入一个巨大的 JSON 文件，或者服务器会因为尝试将数组序列化为字符串而耗尽内存。
有关V8内部结构的更多信息，请参阅：
https://v8project.blogspot.com/2017/09/elements-kinds-in-v8.html
https://v8project.blogspot.com/2017/08/fast-properties.html