홀리 어레이 문제

내가 가장 싫어하는 JavaScript의 "기능"중 하나는 "홀리"배열입니다. 그것이 무엇인지 확실하지 않은 경우 다음을 고려하십시오.

const array = [1, 2, 3];

그것이 "패킹된"배열이라고 불리는 것입니다. 요소는 연속적이며 배열은 하나의 요소 유형( number )으로 구성됩니다.

On the C++ side: when using V8 (aka Node.js), and under the hood, this array is actually stored as PACKED_SMI_ELEMENTS, which is a way to store small integers in memory, and arguably the most efficient out of the myriad of ways V8 will store your arrays.

이제 이 무해한 코드 라인을 고려하십시오.

array.push(3.14); // push a floating point number to the array.

On the C++ side: your array has just been transformed from PACKED_SMI_ELEMENTS (integers) to PACKED_DOUBLE_ELEMENTS(doubles) in memory. It became slightly different, but is still tightly packed and performant. This transformation is irreversible.

JavaScript 쪽에서는 변경된 사항이 없습니다.

다음 단계로 이동:

array.push('Hello world!'); // push a string to the array

On the C++ side: your array has just been irreversibly transformed again. This time from PACKED_DOUBLE_ELEMENTS to PACKED_ELEMENTS. A PACKED_ELEMENTS array can hold any JavaScript value; but has to sacrifice much more memory space to represent itself compared to a SMI or Double array.

이제 다음 코드 줄로 진행하겠습니다.

console.log(array.length); // 5
array[9] = true;
console.log(array.length); // 10

이것은 JavaScript에서 허용됩니다. 맞습니까? 배열의 임의 인덱스에 할당할 수 있으며 배열이 채워집니다. 그렇다면 C++ 측에서는 어떻게 될까요?

On the C++ side: your array has been irreversibly transformed yet again, this time to HOLEY_ELEMENTS. Much, much slower to work with; and you've just made the V8's JIT (Just-In-time compiler) optimisations much harder, as it will be unable to optimise your program to a large extent.

It's worthy of note that calling new Array(n) or Array(n) will always create this type of array and slow down your code.

그런데 왜 여기서 멈추나요? 사탄의 특별한 데이터 구조를 소개하겠습니다.

array[999] = 'HAIL SATAN! ♥'

On the C++ side: your array has just transformed from HOLEY_ELEMENTS to DICTIONARY_ELEMENTS, and you've summoned a demon that can no longer be banished.

Let me quote the V8 source code directly:

  // The "slow" kind.
  DICTIONARY_ELEMENTS,

JavaScript의 관점에서 보면 배열이 방금 사전이 되었습니다. 즉, 일반 개체가 되었습니다. JavaScript 배열의 문자 그대로 최악의 시나리오.

이것이 위험한 이유:

이러한 작업은 자동으로 성공하며 오류를 발생시키지 않습니다.

모든 형태의 루프 기반 열거 또는 직렬화 시도는 서버를 중단시킬 가능성이 높습니다.

배열의 키가 자동으로 문자열로 변환됩니다.

배열은 여전히 ​​객체가 아닌 배열로 직렬화됩니다. ( JSON.stringify는 null s를 사용하여 모든 빈 인덱스를 패딩하려고 합니다.)

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