java-topology/defects/sequelize/unit/test_sequelize_cwe407.js

/**
 * CWE-407 unit tests for Sequelize.
 *
 * sequelize-0001: bulkInsertQuery allAttributes list → Set
 *   File: packages/core/src/abstract-dialect/query-generator.js line 351
 *   Pattern: `if (!allAttributes.includes(key)) allAttributes.push(key)`
 *   inside `for (fieldValueHash of fieldValueHashes) { forOwn(...) }` — the
 *   outer loop iterates rows, the inner iterates columns, and includes() scans
 *   allAttributes (which grows). O(rows * cols^2) total.
 *
 * sequelize-0002: _expandIncludeAllElement all.includes() inside nested for loop
 *   File: packages/core/src/model.js line 519
 *   Pattern: inner `for (type_ of types) { if (!all.includes(type_)) }`
 *   where `all` is the outer loop's array and grows as types are spliced in.
 *   O(|types| * |all|^2) worst case during include-type expansion.
 */

const { performance } = require('perf_hooks');

// ---------------------------------------------------------------------------
// sequelize-0001: bulkInsertQuery allAttributes dedup cost
// ---------------------------------------------------------------------------

function bulkInsertDedupDefective(nRows, nCols) {
  // Simulate: for each row, for each key, check allAttributes.includes(key)
  const allAttributes = [];
  for (let r = 0; r < nRows; r++) {
    for (let c = 0; c < nCols; c++) {
      const key = `col_${c}`;
      if (!allAttributes.includes(key)) {
        allAttributes.push(key);
      }
    }
  }
  return allAttributes.length;
}

function bulkInsertDedupFixed(nRows, nCols) {
  // Fixed: Set for O(1) membership
  const allAttributesSet = new Set();
  const allAttributes = [];
  for (let r = 0; r < nRows; r++) {
    for (let c = 0; c < nCols; c++) {
      const key = `col_${c}`;
      if (!allAttributesSet.has(key)) {
        allAttributesSet.add(key);
        allAttributes.push(key);
      }
    }
  }
  return allAttributes.length;
}

function testBulkInsertListSlowerThanSet() {
  const nRows = 200;
  const nCols = 300; // 200*300 = 60K inner iterations, includes() scans up to 300 each time

  let t0 = performance.now();
  for (let i = 0; i < 10; i++) bulkInsertDedupDefective(nRows, nCols);
  const listTime = performance.now() - t0;

  t0 = performance.now();
  for (let i = 0; i < 10; i++) bulkInsertDedupFixed(nRows, nCols);
  const setTime = performance.now() - t0;

  const ratio = listTime / setTime;
  if (ratio < 5) {
    throw new Error(
      `Expected defective (list) to be >=5x slower than fixed (set) at rows=${nRows} cols=${nCols}, ` +
      `got ratio=${ratio.toFixed(1)} (list=${listTime.toFixed(1)}ms, set=${setTime.toFixed(1)}ms)`
    );
  }
  console.log(`sequelize-0001 timing PASS  ratio=${ratio.toFixed(1)}x  (list=${listTime.toFixed(1)}ms set=${setTime.toFixed(1)}ms)`);
}

function testBulkInsertSameResult() {
  for (const [nRows, nCols] of [[1, 1], [5, 10], [100, 50]]) {
    const a = bulkInsertDedupDefective(nRows, nCols);
    const b = bulkInsertDedupFixed(nRows, nCols);
    if (a !== b) {
      throw new Error(`Results differ at rows=${nRows} cols=${nCols}: defective=${a} fixed=${b}`);
    }
  }
  console.log('sequelize-0001 correctness PASS');
}

// ---------------------------------------------------------------------------
// sequelize-0002: _expandIncludeAllElement all.includes() dedup
// ---------------------------------------------------------------------------

function expandIncludeAllDefective(nTypes) {
  // all starts as ['One', 'Has', 'Many', ...] — simulate the expansion loop
  // that splices type placeholders and does all.includes(type_) to dedup
  let all = Array.from({ length: nTypes }, (_, i) => `TypeAlias_${i}`);
  // Inner expansion: for each item, add expanded sub-types checking includes
  const expanded = [];
  for (let i = 0; i < all.length; i++) {
    const subTypes = [`ConcreteA_${i}`, `ConcreteB_${i}`];
    for (const type_ of subTypes) {
      if (!all.includes(type_)) {  // O(|all|) each time
        all.unshift(type_);
        i++;
        expanded.push(type_);
      }
    }
  }
  return expanded.length;
}

function expandIncludeAllFixed(nTypes) {
  let all = Array.from({ length: nTypes }, (_, i) => `TypeAlias_${i}`);
  const allSet = new Set(all);
  const expanded = [];
  for (let i = 0; i < all.length; i++) {
    const subTypes = [`ConcreteA_${i}`, `ConcreteB_${i}`];
    for (const type_ of subTypes) {
      if (!allSet.has(type_)) {
        all.unshift(type_);
        allSet.add(type_);
        i++;
        expanded.push(type_);
      }
    }
  }
  return expanded.length;
}

function testExpandIncludeAllListSlowerThanSet() {
  const nTypes = 400;

  let t0 = performance.now();
  for (let i = 0; i < 20; i++) expandIncludeAllDefective(nTypes);
  const listTime = performance.now() - t0;

  t0 = performance.now();
  for (let i = 0; i < 20; i++) expandIncludeAllFixed(nTypes);
  const setTime = performance.now() - t0;

  const ratio = listTime / setTime;
  if (ratio < 3) {
    throw new Error(
      `Expected defective to be >=3x slower than fixed at nTypes=${nTypes}, ` +
      `got ratio=${ratio.toFixed(1)} (list=${listTime.toFixed(1)}ms, set=${setTime.toFixed(1)}ms)`
    );
  }
  console.log(`sequelize-0002 timing PASS  ratio=${ratio.toFixed(1)}x  (list=${listTime.toFixed(1)}ms set=${setTime.toFixed(1)}ms)`);
}

function testExpandIncludeAllSameResult() {
  for (const n of [1, 5, 20, 50]) {
    const a = expandIncludeAllDefective(n);
    const b = expandIncludeAllFixed(n);
    if (a !== b) {
      throw new Error(`Results differ at nTypes=${n}: defective=${a} fixed=${b}`);
    }
  }
  console.log('sequelize-0002 correctness PASS');
}

// ---------------------------------------------------------------------------
// Run
// ---------------------------------------------------------------------------

testBulkInsertListSlowerThanSet();
testBulkInsertSameResult();
testExpandIncludeAllListSlowerThanSet();
testExpandIncludeAllSameResult();