Học từ Facebook #74: Parser query kiểu PHP chống prototype pollution

Backend của Facebook viết bằng PHP (nay là Hack), và PHP có một quy ước đọc query string rất tiện: user[name]=An&user[tags][]=js&user[tags][]=css thành mảng lồng nhau ['user' => ['name' => 'An', 'tags' => ['js', 'css']]]. Phía client phải nói cùng "ngôn ngữ" đó, cả chiều ghi (gửi form, gọi API) lẫn chiều đọc (đọc lại tham số trên URL).

Chiều đọc là chỗ nguy hiểm. Chỉ cần viết obj[key] = obj[key] || {} trong một vòng lặp, query ?__proto__[isAdmin]=1 sẽ gắn isAdmin vào Object.prototype, và mọi object trong trang bỗng có isAdmin. Đây là prototype pollution, lớp lỗi đã có CVE ở qs, jquery.extend, lodash.merge, minimist…

▶ Mở demo toàn màn hình ↗ · Sửa code trên StackBlitz ↗ · Xem source trên GitHub ↗

#Prototype pollution trong ba dòng

const node = {};
node['__proto__'] = node['__proto__'] || {}; // __proto__ là accessor trả về Object.prototype
node['__proto__']['isAdmin'] = '1';           // ghi thẳng lên Object.prototype
({}).isAdmin; // '1'

__proto__ không phải key bình thường: trên mọi object kế thừa Object.prototype, đọc obj.__proto__ trả về chính prototype. Đường thứ hai là constructor[prototype][isAdmin]: obj.constructor là hàm Object, Object.prototype là prototype. Một parser ngây thơ đi theo chuỗi key mà không hỏi "key này có phải của chính object không" sẽ đi thẳng lên prototype.

Hậu quả tuỳ code xung quanh: if (user.isAdmin) thành đúng với mọi user, options.url có giá trị mặc định do kẻ tấn công chọn, template engine chèn chuỗi vào HTML (XSS). Demo chạy bản ngây thơ trên một prototype "hộp cát" riêng, nên trang không bị nhiễm thật, nhưng bạn thấy rõ một object mới tạo đã có isAdmin.

#Facebook làm thế nào?

PHPQuerySerializer (bundle 1.js, bản sao trong 22.js) có serialize và deserialize.

#serialize

Đi đệ quy object, ghép tiền tố a[b][c]. null thành key không có =, undefined bị bỏ. Mã hoá bằng encodeURIComponent nhưng đổi %5B và %5D về [ ] cho URL dễ đọc. Hàm này không có rủi ro gì đặc biệt.

#deserialize

Đọc từng cặp sau khi split('&'). Trước khi tách, toàn chuỗi được đổi %5B, %5D thành [, ]. Mỗi cặp khớp regex:

/^([-_\w]+)((?:\[[-_\w]*\])+)=?(.*)/

• Không khớp (key thường, hoặc key có ký tự ngoài [-_\w] trong ngoặc): gán phẳng out[decode(key)] = decode(value).
• Khớp: tách phần ngoặc thành danh sách key, rồi đi xuống từng cấp.

Ở mỗi cấp, key qua một hàm ánh xạ: "hasOwnProperty" và "__proto__" thành "🝖", tức ký tự U+1F756 (🝖, một ký hiệu giả kim; dễ nhầm với emoji đùi gà 🍖 U+1F356). Chọn ký tự này vì gần như không ai đặt tên tham số như vậy, nên dữ liệu vẫn giữ được (không bị vứt), chỉ không còn nguy hiểm.

Lớp thứ hai: trước khi đi vào node[k], code kiểm tra Object.prototype.hasOwnProperty.call(node, k). Chưa có thì tạo mới: key tiếp theo là 1–3 chữ số (/^\d{1,3}$/) hoặc rỗng thì tạo mảng, còn lại tạo object. constructor không phải thuộc tính riêng của {}, nên constructor[prototype][x]=1 tạo ra một object con tên constructor, không chạm vào hàm Object.

Lớp thứ ba, ít ai để ý: sau khi gán node[k] = next, code kiểm tra node[k] !== next. Module không chạy ở strict mode, nên gán thuộc tính lên một chuỗi không ném lỗi mà chỉ không có tác dụng; phép so sánh này bắt đúng trường hợp đó, ví dụ a=1&a[b][c]=2. Nhưng nhánh này return cả kết quả, không chỉ bỏ cặp hiện tại: a=1&a[b][c]=2&z=3 cho ra { a: '1' }, z mất luôn.

Có một nhánh nữa không được bảo vệ: ô rỗng [] ở giữa đường dẫn (a[][y]) gọi thẳng node.push(...). Nếu node lúc đó là object (vì trước đó đã có a[x]=1) thì push không tồn tại và hàm ném TypeError. Một URL như ?a[x]=1&a[][y]=2 đủ để làm hỏng đoạn code đọc query, trừ khi người gọi bọc try/catch. Hai nút "Gán lên chuỗi" và "[] giữa object" trong demo dựng lại cả hai trường hợp (bằng bản mô phỏng trong querySerializerFbStyle.ts, viết lại theo logic đã giải mã, không phải mã của Meta).

#Tại sao giới hạn 3 chữ số?

a[99999999]=x với một parser coi mọi số là chỉ số mảng sẽ tạo một mảng thưa dài 100 triệu. Bản thân mảng thưa rẻ, nhưng code phía sau forEach, JSON.stringify, map qua nó thì không: JSON.stringify in ra 100 triệu null. Giới hạn 3 chữ số (≤ 999) biến chỉ số lớn thành key object, chặn kiểu DoS này. Thư viện qs có option tương tự: arrayLimit mặc định 20.

flowchart TD
  A["cặp key=value"] --> B{"khớp regex có ngoặc?"}
  B -- không --> C["out[key] = value (phẳng)"]
  B -- có --> D["tách thành danh sách key"]
  D --> E["key là __proto__ hoặc hasOwnProperty?"]
  E -- có --> F["đổi thành U+1F756"]
  E -- không --> G{"node có thuộc tính riêng k?"}
  F --> G
  G -- không --> H{"key sau là 1-3 chữ số hoặc rỗng?"}
  H -- có --> I["node[k] = mảng"]
  H -- không --> J["node[k] = object"]
  G -- có --> K["đi xuống node[k]"]
  I --> K
  J --> K

#Viết lại

Bản viết lại đi đường khác: thay vì đổi tên key nguy hiểm, nó làm cho không có prototype nào để làm bẩn. Mọi object tạo ra bằng Object.create(null): không có __proto__ accessor, không có constructor. Thêm vào đó, cặp nào có một đoạn key là __proto__, constructor hoặc prototype thì bỏ hẳn, vì dữ liệu đó gần như chắc chắn là tấn công và giữ lại chỉ làm code phía sau khó đoán.

export function parseQuery(query: string, options: ParseOptions = {}): QueryObject {
  const { maxArrayIndex = 999, maxDepth = 20, maxPairs = 1000 } = options;
  const root = newObject();
  const pairs = query.replace(/^\?/, '').split('&').filter(Boolean).slice(0, maxPairs);

  for (const pair of pairs) {
    const eq = pair.indexOf('=');
    // khác bản gốc: giải mã key TRƯỚC khi tách ngoặc, nên `a%5Bb%5D` và `a[b]` như nhau
    const rawKey = decode(eq === -1 ? pair : pair.slice(0, eq));
    const value = eq === -1 ? null : decode(pair.slice(eq + 1));
    const path = splitKey(rawKey) ?? [rawKey];
    if (path.length - 1 > maxDepth || path.some((p) => DANGEROUS.has(p))) continue;

    // `parent[key]` của bước hiện tại; cần giữ cả parent để có thể thay mảng bằng object
    let parent: QueryObject | QueryValue[] = root;
    const resolved: string[] = []; // key thật đã đi qua (ô `[]` đã đổi thành chỉ số)
    for (let i = 0; i < path.length; i++) {
      const isLast = i === path.length - 1;
      let key = path[i];
      if (Array.isArray(parent) && key !== '' && !isIndex(key, maxArrayIndex)) {
        // mảng gặp key chữ hoặc chỉ số quá lớn: đổi container cha thành object
        const converted = toObject(parent);
        replaceChild(root, resolved, converted);
        parent = converted;
      }
      if (key === '') {
        if (!Array.isArray(parent)) key = String(Object.keys(parent).length);
        else key = String(parent.length);
      }
      const container = parent as Record<string, QueryValue>;
      resolved.push(key);
      if (isLast) {
        container[key] = value;
        break;
      }
      const next = path[i + 1];
      const existing = container[key];
      if (existing === undefined || existing === null || typeof existing === 'string') {
        container[key] = next === '' || isIndex(next, maxArrayIndex) ? [] : newObject();
      }
      parent = container[key] as QueryObject | QueryValue[];
    }
  }
  return root;
}

/**
 * Query string kiểu PHP (`a[b][]=1&a[b][]=2`) ↔ object lồng nhau, an toàn với
 * prototype pollution (ý tưởng từ PHPQuerySerializer của Facebook).
 *
 * Bản gốc đổi key nguy hiểm (`__proto__`, `hasOwnProperty`) thành một ký tự "lính canh"
 * và chỉ đi vào key là thuộc tính riêng (hasOwnProperty). Bản này làm chặt hơn:
 *  - mọi object tạo ra đều không có prototype (Object.create(null))
 *  - bỏ hẳn cặp key/value nếu đường dẫn chứa `__proto__`, `constructor`, `prototype`
 *  - giới hạn chỉ số mảng, độ sâu và số cặp để chống input lớn bất thường
 */

export type QueryValue = string | null | QueryValue[] | { [key: string]: QueryValue };
export type QueryObject = { [key: string]: QueryValue };

const DANGEROUS = new Set(['__proto__', 'constructor', 'prototype']);

export interface ParseOptions {
  /** chỉ số lớn hơn thì coi như key của object (bản gốc: tối đa 3 chữ số = 999) */
  maxArrayIndex?: number;
  /** số cấp `[...]` tối đa của một key */
  maxDepth?: number;
  /** số cặp key=value tối đa được đọc */
  maxPairs?: number;
}

const newObject = (): QueryObject => Object.create(null);

function decode(part: string): string {
  try {
    return decodeURIComponent(part.replace(/\+/g, ' '));
  } catch {
    return part; // chuỗi % hỏng: giữ nguyên thay vì ném lỗi
  }
}

/** Tách `a[b][][c]` thành ['a', 'b', '', 'c']; trả null nếu dấu ngoặc lệch. */
export function splitKey(key: string): string[] | null {
  const m = /^([^[\]]+)((?:\[[^[\]]*\])*)$/.exec(key);
  if (!m) return null;
  const parts = [m[1]];
  for (const seg of m[2].matchAll(/\[([^[\]]*)\]/g)) parts.push(seg[1]);
  return parts;
}

const isIndex = (key: string, max: number) => /^\d+$/.test(key) && Number(key) <= max;

/** Mảng nhận một key không phải chỉ số hợp lệ: chuyển thành object, giữ phần tử cũ. */
function toObject(arr: QueryValue[]): QueryObject {
  const obj = newObject();
  arr.forEach((v, i) => {
    obj[String(i)] = v;
  });
  return obj;
}

export function parseQuery(query: string, options: ParseOptions = {}): QueryObject {
  const { maxArrayIndex = 999, maxDepth = 20, maxPairs = 1000 } = options;
  const root = newObject();
  const pairs = query.replace(/^\?/, '').split('&').filter(Boolean).slice(0, maxPairs);

  for (const pair of pairs) {
    const eq = pair.indexOf('=');
    // khác bản gốc: giải mã key TRƯỚC khi tách ngoặc, nên `a%5Bb%5D` và `a[b]` như nhau
    const rawKey = decode(eq === -1 ? pair : pair.slice(0, eq));
    const value = eq === -1 ? null : decode(pair.slice(eq + 1));
    const path = splitKey(rawKey) ?? [rawKey];
    if (path.length - 1 > maxDepth || path.some((p) => DANGEROUS.has(p))) continue;

    // `parent[key]` của bước hiện tại; cần giữ cả parent để có thể thay mảng bằng object
    let parent: QueryObject | QueryValue[] = root;
    const resolved: string[] = []; // key thật đã đi qua (ô `[]` đã đổi thành chỉ số)
    for (let i = 0; i < path.length; i++) {
      const isLast = i === path.length - 1;
      let key = path[i];
      if (Array.isArray(parent) && key !== '' && !isIndex(key, maxArrayIndex)) {
        // mảng gặp key chữ hoặc chỉ số quá lớn: đổi container cha thành object
        const converted = toObject(parent);
        replaceChild(root, resolved, converted);
        parent = converted;
      }
      if (key === '') {
        if (!Array.isArray(parent)) key = String(Object.keys(parent).length);
        else key = String(parent.length);
      }
      const container = parent as Record<string, QueryValue>;
      resolved.push(key);
      if (isLast) {
        container[key] = value;
        break;
      }
      const next = path[i + 1];
      const existing = container[key];
      if (existing === undefined || existing === null || typeof existing === 'string') {
        container[key] = next === '' || isIndex(next, maxArrayIndex) ? [] : newObject();
      }
      parent = container[key] as QueryObject | QueryValue[];
    }
  }
  return root;
}

/** Thay container tại `path` (tính từ root) bằng `value`. */
function replaceChild(root: QueryObject, path: string[], value: QueryValue) {
  let node: Record<string, QueryValue> = root;
  for (let i = 0; i < path.length - 1; i++) node = node[path[i]] as Record<string, QueryValue>;
  node[path[path.length - 1]] = value;
}

/** Mã hoá giống bản gốc: encodeURIComponent nhưng giữ nguyên `[` `]` cho dễ đọc. */
export function encodeComponent(s: string): string {
  return encodeURIComponent(s).replace(/%5B/g, '[').replace(/%5D/g, ']');
}

export function serializeQuery(data: Record<string, unknown>): string {
  const out: string[] = [];
  const walk = (prefix: string, value: unknown) => {
    if (value === undefined) return;
    if (value === null) {
      out.push(encodeComponent(prefix));
    } else if (Array.isArray(value)) {
      value.forEach((v, i) => walk(`${prefix}[${i}]`, v));
    } else if (typeof value === 'object') {
      for (const [k, v] of Object.entries(value)) walk(`${prefix}[${k}]`, v);
    } else {
      out.push(`${encodeComponent(prefix)}=${encodeComponent(String(value))}`);
    }
  };
  for (const [k, v] of Object.entries(data)) walk(k, v);
  return out.join('&');
}

/** JSON hoá object không prototype (JSON.stringify xử lý được, chỉ cần sắp key cho dễ so). */
export function toJSON(value: QueryValue): string {
  return JSON.stringify(value, null, 2);
}

#Đi qua code

• splitKey dùng regex ^([^[\]]+)((?:\[[^[\]]*\])*)$: tên gốc không chứa ngoặc, theo sau là các cụm [...]. Ngoặc lệch (a[b, a]b[) trả null và cặp đó được giữ phẳng nguyên key.
• Giải mã key trước khi tách, nên a%5Bb%20c%5D và a[b c] cho cùng một kết quả. Bản gốc chỉ đổi %5B/%5D rồi đòi ký tự trong ngoặc khớp [-_\w], nên b%20c (có dấu cách) rơi về nhánh phẳng.
• Kiểm tra DANGEROUS trên cả đường dẫn trước khi đi xuống. Nhờ object không prototype, kể cả quên kiểm tra thì root['__proto__'] cũng chỉ là một key bình thường; kiểm tra là lớp thứ hai.
• Mảng gặp key chữ (a[]=x&a[k]=y) hoặc chỉ số quá maxArrayIndex: toObject đổi mảng thành object giữ nguyên phần tử cũ, replaceChild thay vào chỗ của nó trong cây. resolved ghi lại key thật đã đi qua (ô [] đã đổi thành chỉ số) để replaceChild tìm đúng chỗ.
• Giá trị cũ là chuỗi (a=1&a[b]=2): bị thay bằng container mới, các cặp sau vẫn được đọc. Muốn giữ giá trị đầu thì continue ở đây; điều quan trọng là không dừng cả hàm và không ném lỗi.
• Ô [] giữa đường dẫn khi container là object: dùng Object.keys(parent).length làm key mới thay vì gọi push.
• maxPairs, maxDepth chặn input lớn bất thường: một query 1MB với 100.000 cặp, hay một key lồng 10.000 cấp.

Khác bản gốc:

• Object không prototype thay cho ký tự lính canh.
• Bỏ cặp nguy hiểm thay vì đổi tên.
• Giải mã key trước khi tách ngoặc, và chấp nhận mọi ký tự trong ngoặc.
• Có giới hạn số cặp và độ sâu.
• Không trả sớm, không ném lỗi với input lệch kiểu.

#Tại sao không làm cách khác?

• Chỉ chặn __proto__: quên constructor.prototype là lỗi kinh điển. Bản vá đầu tiên của nhiều thư viện chỉ chặn __proto__ rồi phải phát hành bản vá thứ hai.
• Object.freeze(Object.prototype) ở đầu trang: chặn được mọi kiểu pollution, nhưng có thể làm hỏng thư viện bên thứ ba vẫn gán vào prototype (polyfill). Là lớp phòng thủ tốt cho ứng dụng mới, khó áp dụng cho trang cũ như facebook.com.
• Map thay cho object: an toàn tuyệt đối, nhưng code nhận kết quả phải đổi hết obj.a.b thành map.get('a').get('b'), và JSON.stringify không in Map. Object không prototype giữ được cú pháp quen thuộc.
• URLSearchParams: an toàn vì không lồng nhau, nhưng không hiểu a[b][]. Nếu backend của bạn không cần quy ước PHP thì đây là lựa chọn đúng.

#Edge case và cạm bẫy

• Object không prototype không có method: result.hasOwnProperty('a') ném TypeError, String(result) cũng vậy. Dùng Object.hasOwn(result, 'a'), 'a' in result. JSON.stringify và Object.keys vẫn chạy bình thường.
• So sánh trong test: toEqual của Vitest/Jest có thể báo khác nhau giữa object thường và object không prototype. Đi qua JSON.parse(JSON.stringify(x)) trước khi so.
• Thứ tự key số: object JavaScript luôn đưa key là số nguyên lên đầu theo thứ tự tăng. Mảng bị đổi thành object vẫn giữ thứ tự đúng, nhưng key chữ thì luôn đứng sau key số.
• + trong query là dấu cách (quy ước form). decodeURIComponent không đổi +, nên phải replace(/\+/g, ' ') trước.
• % hỏng (a=%E0%A4%A): decodeURIComponent ném URIError. Bản viết lại giữ nguyên chuỗi gốc; đừng để một tham số hỏng làm sập cả trang.

#Dùng trong dự án

import { parseQuery, serializeQuery } from './querySerializer';

// đọc filter phức tạp từ URL: ?filter[status][]=open&filter[owner]=me&page=2
const params = parseQuery(location.search);
const filter = params.filter as Record<string, unknown> | undefined;

// gửi form tới backend PHP/Laravel/Rails (cùng quy ước a[b][])
await fetch('/api/search', {
  method: 'POST',
  headers: { 'content-type': 'application/x-www-form-urlencoded' },
  body: serializeQuery({ filter: { status: ['open', 'pending'], owner: 'me' }, page: 2 }),
});

Rails và Laravel đọc cùng quy ước a[b][], nên serializeQuery dùng được cho cả hai.

#Kiểm thử

import { expect, it } from 'vitest';
import { parseQuery, serializeQuery } from './querySerializer';
import { makeSandboxProto, parseFbStyle, parseNaive } from '../demos/querySerializerFbStyle';

it('lồng nhau kiểu PHP', () => {
  const q = parseQuery('user[name]=An&user[tags][]=a&user[tags][]=b&page=2');
  expect(JSON.parse(JSON.stringify(q))).toEqual({ user: { name: 'An', tags: ['a', 'b'] }, page: '2' });
});

it('bỏ cặp có __proto__/constructor', () => {
  const q = parseQuery('__proto__[isAdmin]=1&constructor[prototype][x]=1&ok=1');
  expect(Object.keys(q)).toEqual(['ok']);
  expect(({} as any).isAdmin).toBeUndefined();
});

it('chỉ số quá lớn biến mảng thành object', () => {
  const q = parseQuery('a[]=x&a[99999999]=y') as any;
  expect(Array.isArray(q.a)).toBe(false);
  expect(q.a['0']).toBe('x');
  expect(q.a['99999999']).toBe('y');
});

it('key mã hoá %5B giống key thường', () => {
  expect(JSON.stringify(parseQuery('a%5Bb%20c%5D=1'))).toBe(JSON.stringify(parseQuery('a[b c]=1')));
});

it('round-trip', () => {
  const data = { a: { b: ['1', '2'] }, c: 'x y' };
  expect(JSON.parse(JSON.stringify(parseQuery(serializeQuery(data))))).toEqual(data);
});

it('bản kiểu FB: key nguy hiểm thành U+1F756, key có ký tự lạ trong ngoặc thì không lồng', () => {
  const fb = parseFbStyle('__proto__[x]=1&a%5Bb%20c%5D=1');
  expect(Object.keys(fb)).toContain('\u{1F756}');
  expect(fb['a[b c]']).toBe('1');
});

it('bản ngây thơ làm bẩn prototype hộp cát', () => {
  const proto = makeSandboxProto();
  parseNaive('__proto__[isAdmin]=yes', proto);
  expect((Object.create(proto) as any).isAdmin).toBe('yes');
  expect(({} as any).isAdmin).toBeUndefined();
});

it('bản kiểu FB: gán lên chuỗi thì trả sớm, [] giữa object thì ném lỗi', () => {
  expect(parseFbStyle('a=1&a[b][c]=2&z=3')).toEqual({ a: '1' });
  expect(() => parseFbStyle('a[x]=1&a[][y]=2')).toThrow(TypeError);
  expect(JSON.parse(JSON.stringify(parseQuery('a[x]=1&a[][y]=2')))).toEqual({ a: { x: '1', '1': { y: '2' } } });
});

#So với thư viện và chuẩn web

• qs (thư viện query string phổ biến nhất trên npm, dùng trong Express): cùng quy ước a[b][], có arrayLimit (mặc định 20), depth (mặc định 5), parameterLimit (1000), và mặc định bỏ key trùng tên thuộc tính của Object.prototype (allowPrototypes: false). Option plainObjects: true cho kết quả là object không prototype, giống bản viết lại. qs từng có CVE prototype pollution (CVE-2017-1000048, CVE-2022-24999).
• URLSearchParams: chuẩn web, phẳng, an toàn, không hiểu ngoặc. Object.fromEntries(new URLSearchParams(q)) tạo object thường; key __proto__ thành một thuộc tính riêng tên __proto__ (vì fromEntries định nghĩa thuộc tính chứ không gán), không làm bẩn Object.prototype.
• Object.hasOwn, structuredClone và Object.create(null) là ba công cụ chuẩn đáng dùng khi tự viết hàm merge/parse. Node.js còn có cờ --disable-proto=throw để tắt hẳn accessor __proto__.

Bài này thuộc series Học từ mã nguồn Facebook (106 bài, đọc theo thứ tự).

Code + demo: examples/facebook-patterns · Mở trên StackBlitz