GraphQL security: cost, authorisation and exposure

// A small GraphQL engine, enough to show what a client can ask for. It reads the GraphQL language (operations, fields,
// aliases, arguments and nested selections; no fragments, variables or directives), measures a document, and runs it against a
// library of 5 authors with 10 books each. Every field resolved on one object counts as one resolver call. The weak server runs
// every document it receives. The fixed server measures a document first and refuses one that is too deep or has too many aliases.

function tokenize(text) {
  const tokens = [];
  const re = /[ \t\r\n,]+|#[^\n]*|([{}():])|(-?\d+)|("(?:[^"\\]|\\.)*")|([_A-Za-z][_0-9A-Za-z]*)/gy;
  let pos = 0;
  while (pos < text.length) {
    re.lastIndex = pos;
    const m = re.exec(text);
    if (!m) throw new Error(`syntax error at character ${pos}`);
    pos = re.lastIndex;
    if (m[1]) tokens.push(m[1]);
    else if (m[2] !== undefined) tokens.push({ int: Number(m[2]) });
    else if (m[3] !== undefined) tokens.push({ str: JSON.parse(m[3]) });
    else if (m[4] !== undefined) tokens.push({ name: m[4] });
  }
  return tokens;
}

function parse(text) {
  const t = tokenize(text);
  let i = 0;
  const at = (p) => t[i] === p;
  const expect = (p) => {
    if (t[i] !== p) throw new Error(`expected ${p}`);
    i += 1;
  };
  const name = () => {
    const x = t[i];
    if (!x || x.name === undefined) throw new Error('expected a name');
    i += 1;
    return x.name;
  };
  const value = () => {
    const x = t[i];
    i += 1;
    if (x && x.int !== undefined) return x.int;
    if (x && x.str !== undefined) return x.str;
    if (x && x.name !== undefined) return x.name === 'true' ? true : x.name === 'false' ? false : x.name;
    throw new Error('expected a value');
  };
  const selection = () => {
    expect('{');
    const fields = [];
    while (!at('}')) fields.push(field());
    expect('}');
    if (fields.length === 0) throw new Error('empty selection');
    return fields;
  };
  const field = () => {
    let alias = null;
    let fieldName = name();
    if (at(':')) {
      i += 1;
      alias = fieldName;
      fieldName = name();
    }
    const args = {};
    if (at('(')) {
      i += 1;
      while (!at(')')) {
        const key = name();
        expect(':');
        args[key] = value();
      }
      expect(')');
    }
    return { alias, name: fieldName, args, selection: at('{') ? selection() : [] };
  };
  const operations = [];
  while (i < t.length) {
    let type = 'query';
    if (t[i] && (t[i].name === 'query' || t[i].name === 'mutation')) {
      type = t[i].name;
      i += 1;
      if (t[i] && t[i].name !== undefined) i += 1; // the operation's name
    }
    operations.push({ type, selection: selection() });
  }
  return operations;
}

// How big a document is: its depth, its fields and its aliases, from the parsed form, before anything runs.
function measure(selection, depth = 1) {
  const m = { depth, fields: 0, aliases: 0 };
  for (const f of selection) {
    const child = f.selection.length ? measure(f.selection, depth + 1) : { depth, fields: 0, aliases: 0 };
    m.depth = Math.max(m.depth, child.depth);
    m.fields += 1 + child.fields;
    m.aliases += (f.alias ? 1 : 0) + child.aliases;
  }
  return m;
}

const AUTHORS = Array.from({ length: 5 }, (_, a) => ({ id: `a${a + 1}`, name: `Author ${a + 1}` }));
const BOOKS = AUTHORS.flatMap((author, a) => Array.from({ length: 10 }, (_, b) => ({ id: `b${a + 1}-${b + 1}`, title: `Book ${a + 1}.${b + 1}`, authorId: author.id })));
const BOOKS_OF = new Map(AUTHORS.map((author) => [author.id, BOOKS.filter((book) => book.authorId === author.id)]));
const AUTHOR_OF = new Map(AUTHORS.map((author) => [author.id, author]));
const RESOLVERS = {
  Query: { authors: (_, args) => AUTHORS.slice(0, args.first ?? AUTHORS.length), author: (_, args) => AUTHOR_OF.get(args.id) ?? null },
  Author: { id: (o) => o.id, name: (o) => o.name, books: (o, args) => BOOKS_OF.get(o.id).slice(0, args.first ?? 10) },
  Book: { id: (o) => o.id, title: (o) => o.title, author: (o) => AUTHOR_OF.get(o.authorId) },
};
const RETURNS = { 'Query.authors': 'Author', 'Query.author': 'Author', 'Author.books': 'Book', 'Book.author': 'Author' };

function execute(selection, type, parent, stats) {
  for (const f of selection) {
    stats.calls += 1;
    const resolver = Object.hasOwn(RESOLVERS[type], f.name) ? RESOLVERS[type][f.name] : undefined; // own fields only: not "constructor"
    if (!resolver) throw new Error(`Cannot query field "${f.name}" on type "${type}"`);
    const value = resolver(parent, f.args);
    const childType = RETURNS[`${type}.${f.name}`];
    if (!childType) continue;
    for (const item of Array.isArray(value) ? value : [value]) if (item) execute(f.selection, childType, item, stats);
  }
}

const LIMITS = { maxDepth: 6, maxAliases: 10 };
function weakServer(text) {
  const stats = { calls: 0 };
  for (const op of parse(text)) execute(op.selection, 'Query', null, stats);
  return `ran, ${String(stats.calls).replace(/\B(?=(\d{3})+(?!\d))/g, ',')} resolver calls`;
}
function fixedServer(text) {
  const ops = parse(text);
  for (const op of ops) {
    const m = measure(op.selection);
    if (m.depth > LIMITS.maxDepth) return `refused: depth ${m.depth} is above ${LIMITS.maxDepth}`;
    if (m.aliases > LIMITS.maxAliases) return `refused: ${m.aliases} aliases are above ${LIMITS.maxAliases}`;
  }
  return weakServer(text);
}

const documents = [
  ['a dashboard of 3 authors', '{ authors(first: 3) { name books(first: 5) { title } } }'],
  ['a profile page', '{ author(id: "a1") { name books { title author { name } } } }'],
  ['a cycle, nine levels deep', '{ authors { books { author { books { author { books { author { books { title } } } } } } } } }'],
  ['the same list 100 times', `{ ${Array.from({ length: 100 }, (_, n) => `l${n + 1}: authors { books { author { name } } }`).join(' ')} }`],
];

console.log(`${'document'.padEnd(28)}${'bytes'.padStart(6)}${'depth'.padStart(7)}${'aliases'.padStart(9)}   ${'weak server'.padEnd(28)}fixed server`);
for (const [label, text] of documents) {
  const m = measure(parse(text)[0].selection);
  console.log(`${label.padEnd(28)}${String(text.length).padStart(6)}${String(m.depth).padStart(7)}${String(m.aliases).padStart(9)}   ${weakServer(text).padEnd(28)}${fixedServer(text)}`);
}

document                     bytes  depth  aliases   weak server                 fixed server
a dashboard of 3 authors        56      3        0   ran, 22 resolver calls      ran, 22 resolver calls
a profile page                  61      4        0   ran, 33 resolver calls      ran, 33 resolver calls
a cycle, nine levels deep       94      9        0   ran, 61,106 resolver calls  refused: depth 9 is above 6
the same list 100 times       4295      4      100   ran, 10,600 resolver calls  refused: 100 aliases are above 10