codeql/javascript/ql/lib/semmle/javascript/Arrays.qll

import javascript
private import semmle.javascript.dataflow.InferredTypes
private import semmle.javascript.dataflow.internal.PreCallGraphStep

/**
 * Classes and predicates for modeling TaintTracking steps for arrays.
 */
module ArrayTaintTracking {
  /**
   * A taint propagating data flow edge caused by the builtin array functions.
   */
  private class ArrayFunctionTaintStep extends TaintTracking::LegacyTaintStep {
    override predicate arrayStep(DataFlow::Node pred, DataFlow::Node succ) {
      arrayFunctionTaintStep(pred, succ, _)
    }
  }

  /**
   * Holds if there is a taint propagating data flow edge from `pred` to `succ` caused by a call `call` to a builtin array functions.
   */
  predicate arrayFunctionTaintStep(DataFlow::Node pred, DataFlow::Node succ, DataFlow::CallNode call) {
    // `array.map(function (elt, i, ary) { ... })`: if `array` is tainted, then so are
    // `elt` and `ary`; similar for `forEach`
    exists(Function f |
      call.getArgument(0).getAFunctionValue(0).getFunction() = f and
      call.(DataFlow::MethodCallNode).getMethodName() = ["map", "forEach"] and
      pred = call.getReceiver() and
      succ = DataFlow::parameterNode(f.getParameter([0, 2]))
    )
    or
    // `array.map` with tainted return value in callback
    exists(DataFlow::FunctionNode f |
      call.(DataFlow::MethodCallNode).getMethodName() = "map" and
      call.getArgument(0) = f and // Require the argument to be a closure to avoid spurious call/return flow
      pred = f.getAReturn() and
      succ = call
    )
    or
    // `array.filter(x => x)` and `array.filter(x => !<something>)` keeps the taint
    // the latter is assumed to filter away only specific values, thus keeping the taint
    call.(DataFlow::MethodCallNode).getMethodName() = "filter" and
    pred = call.getReceiver() and
    succ = call and
    exists(DataFlow::FunctionNode callback, DataFlow::Node param, DataFlow::Node ret |
      callback = call.getArgument(0).getAFunctionValue() and
      param = callback.getParameter(0).getALocalUse() and
      ret = callback.getAReturn()
    |
      param = ret
      or
      ret.asExpr() instanceof LogNotExpr
    )
    or
    // `array.reduce` with tainted value in callback
    // The callback parameters are: (previousValue, currentValue, currentIndex, array)
    call.(DataFlow::MethodCallNode).getMethodName() = "reduce" and
    exists(DataFlow::FunctionNode callback |
      callback = call.getArgument(0) // Require the argument to be a closure to avoid spurious call/return flow
    |
      pred = callback.getAReturn() and
      succ = call
      or
      pred = call.getReceiver() and
      succ = callback.getParameter([1, 3]) // into currentValue or array
      or
      pred = [call.getArgument(1), callback.getAReturn()] and
      succ = callback.getParameter(0) // into previousValue
    )
    or
    // `array.push(e)`, `array.unshift(e)`: if `e` is tainted, then so is `array`.
    pred = call.getAnArgument() and
    succ.(DataFlow::SourceNode).getAMethodCall(["push", "unshift"]) = call
    or
    // `array.push(...e)`, `array.unshift(...e)`: if `e` is tainted, then so is `array`.
    pred = call.getASpreadArgument() and
    // Make sure we handle reflective calls
    succ = call.getReceiver().getALocalSource() and
    call.getCalleeName() = ["push", "unshift"]
    or
    // `array.splice(i, del, e1, e2, ...)`: if any item is tainted, then so is `array`.
    pred = call.getArgument(any(int i | i >= 2)) and
    succ.(DataFlow::SourceNode).getAMethodCall("splice") = call
    or
    // `array.toSpliced(x, y, source())`: if `source()` is tainted, then so is the result of `toSpliced`, but not the original array.
    call.(DataFlow::MethodCallNode).getMethodName() = "toSpliced" and
    pred = call.getArgument(any(int i | i >= 2)) and
    succ = call
    or
    // `array.splice(i, del, ...e)`: if `e` is tainted, then so is `array`.
    pred = call.getASpreadArgument() and
    succ.(DataFlow::SourceNode).getAMethodCall("splice") = call
    or
    // `array.toSpliced(i, del, ...e)`: if `e` is tainted, then so is the result of `toSpliced`, but not the original array.
    pred = call.getASpreadArgument() and
    call.(DataFlow::MethodCallNode).getMethodName() = "toSpliced" and
    succ = call
    or
    // `e = array.pop()`, `e = array.shift()`, or similar: if `array` is tainted, then so is `e`.
    call.(DataFlow::MethodCallNode)
        .calls(pred, ["pop", "shift", "slice", "splice", "at", "toSpliced"]) and
    succ = call
    or
    // `e = Array.from(x)`: if `x` is tainted, then so is `e`.
    call = arrayFromCall() and
    pred = call.getAnArgument() and
    succ = call
    or
    // `e = arr1.concat(arr2, arr3)`: if any of the `arr` is tainted, then so is `e`.
    call.(DataFlow::MethodCallNode).calls(pred, "concat") and
    succ = call
    or
    call.(DataFlow::MethodCallNode).getMethodName() = "concat" and
    succ = call and
    pred = call.getAnArgument()
    or
    // find
    // `e = arr.find(callback)`
    call = arrayFindCall(pred) and
    succ = call
  }
}

/**
 * Classes and predicates for modeling data-flow for arrays.
 */
private module ArrayDataFlow {
  private import DataFlow::PseudoProperties

  /**
   * A step modeling the creation of an Array using the `Array.from(x)` method.
   * The step copies the elements of the argument (set, array, or iterator elements) into the resulting array.
   */
  private class ArrayFrom extends LegacyPreCallGraphStep {
    override predicate loadStoreStep(
      DataFlow::Node pred, DataFlow::SourceNode succ, string fromProp, string toProp
    ) {
      exists(DataFlow::CallNode call |
        call = arrayFromCall() and
        pred = call.getArgument(0) and
        succ = call and
        fromProp = arrayLikeElement() and
        toProp = arrayElement()
      )
    }
  }

  /**
   * A step modeling an array copy where the spread operator is used.
   * The result is essentially array concatenation.
   *
   * Such a step can occur both with the `push` and `unshift` methods, or when creating a new array.
   */
  private class ArrayCopySpread extends LegacyPreCallGraphStep {
    override predicate loadStoreStep(
      DataFlow::Node pred, DataFlow::SourceNode succ, string fromProp, string toProp
    ) {
      fromProp = arrayLikeElement() and
      toProp = arrayElement() and
      (
        exists(DataFlow::MethodCallNode mcn |
          mcn.getMethodName() = ["push", "unshift"] and
          pred = mcn.getASpreadArgument() and
          succ = mcn.getReceiver().getALocalSource()
        )
        or
        pred = succ.(DataFlow::ArrayCreationNode).getASpreadArgument()
      )
    }
  }

  /**
   * A step for storing an element on an array using `arr.push(e)` or `arr.unshift(e)`.
   */
  private class ArrayAppendStep extends LegacyPreCallGraphStep {
    override predicate storeStep(DataFlow::Node element, DataFlow::SourceNode obj, string prop) {
      prop = arrayElement() and
      exists(DataFlow::MethodCallNode call |
        call.getMethodName() = ["push", "unshift"] and
        element = call.getAnArgument() and
        obj.getAMethodCall() = call
      )
    }
  }

  /**
   * A node that reads or writes an element from an array inside a for-loop.
   */
  private class ArrayIndexingAccess extends DataFlow::Node instanceof DataFlow::PropRef {
    ArrayIndexingAccess() {
      TTNumber() =
        unique(InferredType type | type = super.getPropertyNameExpr().flow().analyze().getAType()) and
      exists(VarAccess i, ExprOrVarDecl init |
        i = super.getPropertyNameExpr() and init = any(ForStmt f).getInit()
      |
        i.getVariable().getADefinition() = init or
        i.getVariable().getADefinition().(VariableDeclarator).getDeclStmt() = init
      )
    }
  }

  /**
   * A step for reading/writing an element from an array inside a for-loop.
   * E.g. a read from `foo[i]` to `bar` in `for(var i = 0; i < arr.length; i++) {bar = foo[i]}`.
   */
  private class ArrayIndexingStep extends LegacyPreCallGraphStep {
    override predicate loadStep(DataFlow::Node obj, DataFlow::Node element, string prop) {
      exists(ArrayIndexingAccess access |
        prop = arrayElement() and
        obj = access.(DataFlow::PropRead).getBase() and
        element = access
      )
    }

    override predicate storeStep(DataFlow::Node element, DataFlow::SourceNode obj, string prop) {
      exists(ArrayIndexingAccess access |
        prop = arrayElement() and
        element = access.(DataFlow::PropWrite).getRhs() and
        access = obj.getAPropertyWrite()
      )
    }
  }

  /**
   * A step for retrieving an element from an array using `.pop()`, `.shift()`, or `.at()`.
   * E.g. `array.pop()`.
   */
  private class ArrayPopStep extends LegacyPreCallGraphStep {
    override predicate loadStep(DataFlow::Node obj, DataFlow::Node element, string prop) {
      exists(DataFlow::MethodCallNode call |
        call.getMethodName() = ["pop", "shift", "at"] and
        prop = arrayElement() and
        obj = call.getReceiver() and
        element = call
      )
    }
  }

  /**
   * A step for iterating an array using `map` or `forEach`.
   *
   * Array elements can be loaded from the array `arr` to `e` in e.g: `arr.forEach(e => ...)`.
   *
   * And array elements can be stored into a resulting array using `map(...)`.
   * E.g. in `arr.map(e => foo)`, the resulting array (`arr.map(e => foo)`) will contain the element `foo`.
   *
   * And the second parameter in the callback is the array ifself, so there is a `loadStoreStep` from the array to that second parameter.
   */
  private class ArrayIteration extends LegacyPreCallGraphStep {
    override predicate loadStep(DataFlow::Node obj, DataFlow::Node element, string prop) {
      exists(DataFlow::MethodCallNode call |
        call.getMethodName() = ["map", "forEach"] and
        prop = arrayElement() and
        obj = call.getReceiver() and
        element = call.getCallback(0).getParameter(0)
      )
    }

    override predicate storeStep(DataFlow::Node element, DataFlow::SourceNode obj, string prop) {
      exists(DataFlow::MethodCallNode call |
        call.getMethodName() = "map" and
        prop = arrayElement() and
        element = call.getCallback(0).getAReturn() and
        obj = call
      )
    }

    override predicate loadStoreStep(DataFlow::Node pred, DataFlow::SourceNode succ, string prop) {
      exists(DataFlow::MethodCallNode call |
        call.getMethodName() = ["map", "forEach"] and
        prop = arrayElement() and
        pred = call.getReceiver() and
        succ = call.getCallback(0).getParameter(2)
      )
    }
  }

  /**
   * A step for creating an array and storing the elements in the array.
   */
  private class ArrayCreationStep extends LegacyPreCallGraphStep {
    override predicate storeStep(DataFlow::Node element, DataFlow::SourceNode obj, string prop) {
      exists(DataFlow::ArrayCreationNode array, int i |
        element = array.getElement(i) and
        obj = array and
        prop = arrayElement(i)
      )
    }
  }

  /**
   * A step modeling that `splice` can insert elements into an array.
   * For example in `array.splice(i, del, e1, e2, ...)`: if any item is tainted, then so is `array`
   */
  private class ArraySpliceStep extends LegacyPreCallGraphStep {
    override predicate storeStep(DataFlow::Node element, DataFlow::SourceNode obj, string prop) {
      exists(DataFlow::MethodCallNode call |
        call.getMethodName() = ["splice", "toSpliced"] and
        prop = arrayElement() and
        element = call.getArgument(any(int i | i >= 2)) and
        call = obj.getAMethodCall()
      )
    }

    override predicate loadStoreStep(
      DataFlow::Node pred, DataFlow::SourceNode succ, string fromProp, string toProp
    ) {
      fromProp = arrayLikeElement() and
      toProp = arrayElement() and
      // `array.splice(i, del, ...arr)` variant
      exists(DataFlow::MethodCallNode mcn |
        mcn.getMethodName() = ["splice", "toSpliced"] and
        pred = mcn.getASpreadArgument() and
        succ = mcn.getReceiver().getALocalSource()
      )
    }
  }

  /**
   * A step for modeling `concat`.
   * For example in `e = arr1.concat(arr2, arr3)`: if any of the `arr` is tainted, then so is `e`.
   */
  private class ArrayConcatStep extends LegacyPreCallGraphStep {
    override predicate loadStoreStep(DataFlow::Node pred, DataFlow::SourceNode succ, string prop) {
      exists(DataFlow::MethodCallNode call |
        call.getMethodName() = "concat" and
        prop = arrayElement() and
        (pred = call.getReceiver() or pred = call.getAnArgument()) and
        succ = call
      )
    }
  }

  /**
   * A step for modeling that elements from an array `arr` also appear in the result from calling `slice`/`splice`/`filter`/`toSpliced`.
   */
  private class ArraySliceStep extends LegacyPreCallGraphStep {
    override predicate loadStoreStep(DataFlow::Node pred, DataFlow::SourceNode succ, string prop) {
      exists(DataFlow::MethodCallNode call |
        call.getMethodName() = ["slice", "splice", "filter", "toSpliced"] and
        prop = arrayElement() and
        pred = call.getReceiver() and
        succ = call
      )
    }
  }

  /**
   * A step modeling that elements from an array `arr` are received by calling `find`.
   */
  private class ArrayFindStep extends LegacyPreCallGraphStep {
    override predicate loadStep(DataFlow::Node pred, DataFlow::Node succ, string prop) {
      exists(DataFlow::CallNode call |
        call = arrayFindCall(pred) and
        succ = call and
        prop = arrayElement()
      )
    }
  }
}

private import ArrayLibraries

/**
 * Classes and predicates modeling various libraries that work on arrays or array-like structures.
 */
private module ArrayLibraries {
  private import DataFlow::PseudoProperties

  /**
   * Gets a call to `Array.from` or a polyfill implementing the same functionality.
   */
  DataFlow::CallNode arrayFromCall() {
    result = DataFlow::globalVarRef("Array").getAMemberCall("from")
    or
    result = DataFlow::moduleImport("array-from").getACall()
    or
    // Array.prototype.slice.call acts the same as Array.from, and is sometimes used with e.g. the arguments object.
    result =
      DataFlow::globalVarRef("Array")
          .getAPropertyRead("prototype")
          .getAPropertyRead("slice")
          .getAMethodCall("call") and
    result.getNumArgument() = 1
  }

  /**
   * Gets a call to `Array.prototype.find` or `Array.prototype.findLast` or a polyfill implementing the same functionality.
   */
  DataFlow::CallNode arrayFindCall(DataFlow::Node array) {
    result.(DataFlow::MethodCallNode).getMethodName() in ["find", "findLast"] and
    array = result.getReceiver()
    or
    result = DataFlow::moduleImport(["array.prototype.find", "array-find"]).getACall() and
    array = result.getArgument(0)
  }

  /**
   * A taint step through the `arrify` library, or other libraries that (maybe) convert values into arrays.
   */
  private class ArrayifyStep extends TaintTracking::LegacyTaintStep {
    override predicate step(DataFlow::Node pred, DataFlow::Node succ) {
      exists(API::CallNode call | call = API::moduleImport(["arrify", "array-ify"]).getACall() |
        pred = call.getArgument(0) and succ = call
      )
    }
  }

  /**
   * Gets a call to a library that copies the elements of an array into another array.
   * E.g. `array-union` that creates a union of multiple arrays, or `array-uniq` that creates an array with unique elements.
   */
  DataFlow::CallNode arrayCopyCall(DataFlow::Node array) {
    result = DataFlow::moduleImport(["array-union", "array-uniq", "uniq"]).getACall() and
    array = result.getAnArgument()
  }

  /**
   * A taint step for a library that copies the elements of an array into another array.
   */
  private class ArrayCopyTaint extends TaintTracking::LegacyTaintStep {
    override predicate step(DataFlow::Node pred, DataFlow::Node succ) {
      exists(DataFlow::CallNode call |
        call = arrayCopyCall(pred) and
        succ = call
      )
    }
  }

  /**
   * A loadStoreStep for a library that copies the elements of an array into another array.
   */
  private class ArrayCopyLoadStore extends LegacyPreCallGraphStep {
    override predicate loadStoreStep(DataFlow::Node pred, DataFlow::SourceNode succ, string prop) {
      exists(DataFlow::CallNode call |
        call = arrayCopyCall(pred) and
        succ = call and
        prop = arrayElement()
      )
    }
  }

  /**
   * A taint step through a call to `Array.prototype.flat` or a polyfill implementing array flattening.
   */
  private class ArrayFlatStep extends TaintTracking::LegacyTaintStep {
    override predicate step(DataFlow::Node pred, DataFlow::Node succ) {
      exists(DataFlow::CallNode call | succ = call |
        call.(DataFlow::MethodCallNode).getMethodName() = "flat" and
        pred = call.getReceiver()
        or
        call =
          API::moduleImport(["array-flatten", "arr-flatten", "flatten", "array.prototype.flat"])
              .getACall() and
        pred = call.getAnArgument()
      )
    }
  }

  /**
   * A taint propagating data flow edge arising from in-place array manipulation operations.
   * The methods return the pointer to `this` array as well.
   */
  private class ArrayInPlaceManipulationTaintStep extends TaintTracking::SharedTaintStep {
    override predicate heapStep(DataFlow::Node pred, DataFlow::Node succ) {
      exists(DataFlow::MethodCallNode call |
        call.getMethodName() in ["sort", "reverse"] and
        pred = call.getReceiver() and
        succ = call
      )
    }
  }

  /**
   * A taint propagating data flow edge arising from array transformation operations
   * that return a new array instead of modifying the original array in place.
   */
  private class ImmutableArrayTransformStep extends TaintTracking::SharedTaintStep {
    override predicate heapStep(DataFlow::Node pred, DataFlow::Node succ) {
      exists(DataFlow::MethodCallNode call |
        call.getMethodName() in ["toSorted", "toReversed", "with"] and
        pred = call.getReceiver() and
        succ = call
      )
    }
  }

  /**
   * Defines a data flow step that tracks the flow of data through callback functions in arrays.
   */
  private class ArrayCallBackDataFlowStep extends PreCallGraphStep {
    override predicate loadStep(DataFlow::Node obj, DataFlow::Node element, string prop) {
      exists(DataFlow::MethodCallNode call |
        call.getMethodName() = ["findLast", "find", "findLastIndex"] and
        prop = arrayLikeElement() and
        obj = call.getReceiver() and
        element = call.getCallback(0).getParameter(0)
      )
    }
  }

  /**
   * This step models the propagation of data from the array to the callback function's parameter.
   */
  private class ArrayCallBackDataTaintStep extends TaintTracking::SharedTaintStep {
    override predicate step(DataFlow::Node obj, DataFlow::Node element) {
      exists(DataFlow::MethodCallNode call |
        call.getMethodName() = ["findLast", "find", "findLastIndex"] and
        obj = call.getReceiver() and
        element = call.getCallback(0).getParameter(0)
      )
    }
  }
}