Step 0: finding the definition of alloca

Question 0.0:Find the definition of the alloca macro and the name of the function that it expands to

import cpp

from Macro alloca
where alloca.getName() = "alloca"
select alloca, "alloca macro"

Step 1: finding the calls to alloca and filtering out small allocation sizes

Question 1.0: Find all the calls to alloca

import cpp

from FunctionCall alloca
where alloca.getTarget().getName() = "__builtin_alloca"
select alloca, "call to alloca"

Question 1.1: Filter out results which are safe because the allocation size is small

import cpp
import semmle.code.cpp.rangeanalysis.SimpleRangeAnalysis

from FunctionCall alloca, Expr sizeArg
where
  alloca.getTarget().getName() = "__builtin_alloca" and
  sizeArg = alloca.getArgument(0) and
  (lowerBound(sizeArg) < 0 or 65536 <= upperBound(sizeArg))
select alloca, "call to alloca"

Step 2: filtering out calls that are guarded by __libc_use_alloca

Question 2.0: Find all calls to __libc_use_alloca

import cpp
import semmle.code.cpp.rangeanalysis.SimpleRangeAnalysis

from FunctionCall call
where call.getTarget().getName() = "__libc_use_alloca"
select call, "call to __libc_use_alloca"

Question 2.1: Find all guard conditions where the condition is a call to __libc_use_alloca

import cpp
import semmle.code.cpp.rangeanalysis.SimpleRangeAnalysis
import semmle.code.cpp.controlflow.Guards

from GuardCondition guard
where guard.(FunctionCall).getTarget().getName() = "__libc_use_alloca"
select guard, "__libc_use_alloca guard"

Question 2.2: Enhance your query to find more guard conditions, using local dataflow

import cpp
import semmle.code.cpp.rangeanalysis.SimpleRangeAnalysis
import semmle.code.cpp.controlflow.Guards
import semmle.code.cpp.dataflow.DataFlow

from DataFlow::Node source, DataFlow::Node sink
where
  source.asExpr().(FunctionCall).getTarget().getName() = "__libc_use_alloca" and
  sink.asExpr() instanceof GuardCondition and
  DataFlow::localFlow(source, sink)
select sink, "__libc_use_alloca guard"

Question 2.3: Enhance your query to find more guard conditions

import cpp
import semmle.code.cpp.rangeanalysis.SimpleRangeAnalysis
import semmle.code.cpp.controlflow.Guards
import semmle.code.cpp.dataflow.DataFlow

DataFlow::Node use_alloca() {
  result.asExpr().(FunctionCall).getTarget().getName() = "__libc_use_alloca"
  or
  result.asExpr().(FunctionCall).getTarget().getName() = "__builtin_expect" and
  result.asExpr().(FunctionCall).getArgument(0) = use_alloca().asExpr()
  or
  DataFlow::localFlow(use_alloca(), result)
}
from GuardCondition guard
where guard = use_alloca().asExpr()
select guard, "__libc_use_alloca guard"

Question 2.4: Enhance your query so that it can also handle negations

import cpp
import semmle.code.cpp.rangeanalysis.SimpleRangeAnalysis
import semmle.code.cpp.controlflow.Guards
import semmle.code.cpp.dataflow.DataFlow

DataFlow::Node use_alloca(boolean branch) {
  result.asExpr().(FunctionCall).getTarget().getName() = "__libc_use_alloca" and
  branch = true
  or
  result.asExpr().(FunctionCall).getTarget().getName() = "__builtin_expect" and
  result.asExpr().(FunctionCall).getArgument(0) = use_alloca(branch).asExpr()
  or
  DataFlow::localFlow(use_alloca(branch), result)
  or
  result.asExpr().(NotExpr).getOperand() = use_alloca(branch.booleanNot()).asExpr()
}
from GuardCondition guard, boolean branch
where guard = use_alloca(branch).asExpr()
select guard, "__libc_use_alloca guard"

Question 2.5: Find calls to alloca that are safe because they are guarded by a call to __libc_use_alloca

import cpp
import semmle.code.cpp.rangeanalysis.SimpleRangeAnalysis
import semmle.code.cpp.controlflow.Guards
import semmle.code.cpp.dataflow.DataFlow

DataFlow::Node use_alloca(boolean branch) {
  result.asExpr().(FunctionCall).getTarget().getName() = "__libc_use_alloca" and
  branch = true
  or
  result.asExpr().(FunctionCall).getTarget().getName() = "__builtin_expect" and
  result.asExpr().(FunctionCall).getArgument(0) = use_alloca(branch).asExpr()
  or
  DataFlow::localFlow(use_alloca(branch), result)
  or
  result.asExpr().(NotExpr).getOperand() = use_alloca(branch.booleanNot()).asExpr()
}
from GuardCondition guard, BasicBlock block, boolean branch, FunctionCall alloca
where
  guard = use_alloca(branch).asExpr() and
  guard.controls(block, branch) and
  alloca.getTarget().getName() = "__builtin_alloca" and
  block.contains(alloca)
select block, "safe call to __builtin_alloca"

Step 3: Combine steps 1 and 2 to filter out safe calls

import cpp
import semmle.code.cpp.rangeanalysis.SimpleRangeAnalysis
import semmle.code.cpp.controlflow.Guards
import semmle.code.cpp.dataflow.DataFlow

DataFlow::Node use_alloca(boolean branch) {
  result.asExpr().(FunctionCall).getTarget().getName() = "__libc_use_alloca" and
  branch = true
  or
  result.asExpr().(FunctionCall).getTarget().getName() = "__builtin_expect" and
  result.asExpr().(FunctionCall).getArgument(0) = use_alloca(branch).asExpr()
  or
  DataFlow::localFlow(use_alloca(branch), result)
  or
  result.asExpr().(NotExpr).getOperand() = use_alloca(branch.booleanNot()).asExpr()
}
predicate guarded_alloca(FunctionCall alloca) {
  exists(GuardCondition guard, BasicBlock block, boolean branch |
    guard = use_alloca(branch).asExpr() and
    guard.controls(block, branch) and
    block.contains(alloca)
  )
}
from FunctionCall alloca, Expr sizeArg
where
  alloca.getTarget().getName() = "__builtin_alloca" and
  sizeArg = alloca.getArgument(0) and
  (lowerBound(sizeArg) < 0 or 65536 <= upperBound(sizeArg)) and
  not guarded_alloca(alloca)
select alloca, "call to alloca"

Step 4: Taint tracking

Question 4.0: Find calls to fopen

import cpp

from FunctionCall call
where call.getTarget().getName().matches("%fopen")
select call, "call to fopen"

Question 4.1: Write a taint tracking query. The source should be a call to fopen and the sink should be the size argument of an unsafe call to alloca

import cpp
import semmle.code.cpp.rangeanalysis.SimpleRangeAnalysis
import semmle.code.cpp.dataflow.TaintTracking
import semmle.code.cpp.models.interfaces.DataFlow
import semmle.code.cpp.controlflow.Guards
import DataFlow::PathGraph

// Track taint through `__strnlen`.
class StrlenFunction extends DataFlowFunction {
  StrlenFunction() { this.getName().matches("%str%len%") }

  override predicate hasDataFlow(FunctionInput i, FunctionOutput o) {
    i.isInParameter(0) and o.isOutReturnValue()
  }
}

// Track taint through `__getdelim`.
class GetDelimFunction extends DataFlowFunction {
  GetDelimFunction() { this.getName().matches("%get%delim%") }

  override predicate hasDataFlow(FunctionInput i, FunctionOutput o) {
    i.isInParameter(3) and o.isOutParameterPointer(0)
  }
}

DataFlow::Node use_alloca(boolean branch) {
  result.asExpr().(FunctionCall).getTarget().getName() = "__libc_use_alloca" and
  branch = true
  or
  result.asExpr().(FunctionCall).getTarget().getName() = "__builtin_expect" and
  result.asExpr().(FunctionCall).getArgument(0) = use_alloca(branch).asExpr()
  or
  DataFlow::localFlow(use_alloca(branch), result)
  or
  result.asExpr().(NotExpr).getOperand() = use_alloca(branch.booleanNot()).asExpr()
}

predicate guarded_alloca(FunctionCall alloca) {
  exists(GuardCondition guard, BasicBlock block, boolean branch |
    guard = use_alloca(branch).asExpr() and
    guard.controls(block, branch) and
    block.contains(alloca)
  )
}

class Config extends TaintTracking::Configuration {
  Config() { this = "fopen_to_alloca_taint" }

  override predicate isSource(DataFlow::Node source) {
    source.asExpr().(FunctionCall).getTarget().getName().regexpMatch(".*fopen")
  }

  override predicate isSink(DataFlow::Node sink) {
    exists(FunctionCall alloca, Expr sizeArg |
      alloca.getTarget().getName() = "__builtin_alloca" and
      sizeArg = alloca.getArgument(0) and
      (lowerBound(sizeArg) < 0 or 65536 <= upperBound(sizeArg)) and
      not guarded_alloca(alloca) and
      sink.asExpr() = sizeArg
    )
  }
}

from Config cfg, DataFlow::PathNode source, DataFlow::PathNode sink
where cfg.hasFlowPath(source, sink)
select sink, source, sink, "fopen flows to alloca"