Higher-Order Function (HOF) Taint Analysis - PR Documentation

Overview

This PR introduces comprehensive support for tracking taint through higher-order functions (HOFs) in opengrep's cross-function taint analysis.
Problem: Before this PR, taint analysis could not track data flow through HOF calls like:

let userInput = getSource();
let results = [userInput].map(x => x);  // Taint was lost here
sink(results[0]);  // Not detected as a vulnerability

Solution: We now model HOF behavior with ToSinkInCall effects that represent "call this callback with tainted data", combined with a call graph that tracks both direct calls and HOF callbacks for proper analysis ordering.

Architecture Changes

1. Path-Based Function Identification (fn_id)

File: src/tainting/Shape_and_sig.ml:695-710

Before:

type fn_id = { class_name : IL.name option; name : IL.name option }

After:

type fn_id = IL.name option list

Why: The old structure couldn't represent nested functions. The new path-based representation supports arbitrary nesting:

• [None; Some "foo"] - Top-level function foo
• [Some "MyClass"; Some "method"] - Method in a class
• [None; Some "outer"; Some "inner"] - Nested function inner inside outer
• [Some "Class"; Some "method"; Some "_tmp"] - Lambda inside a class method

Helper functions added:

let make_fn_id_with_class class_name method_name = [Some class_name; Some method_name]
let make_fn_id_no_class name = [None; Some name]
let show_fn_id fn_id = ... (* e.g., "MyClass::method::nested" *)
let get_fn_name fn_id = ... (* Extract last element *)

2. Builtin Signature Database

New File: src/tainting/Builtin_models.ml (471 lines)

Standard library HOFs (like Array.map, filter, Python's map()) don't have user-defined signatures. This module provides built-in models.

Key concept: ToSinkInCall effect represents "call a callback with tainted data":

Effect.ToSinkInCall {
  callee = <callback expression>;
  arg = { name = "callback"; index = 0 };  (* Which param is the callback *)
  args_taints = [tainted_data];            (* What data to pass *)
}

Three signature patterns:

1. MethodHOF - arr.map(callback): Passes this (the array) to the callback

   (* Signature models: callback receives BThis (the receiver) *)
   let this_taint = Taint.{ orig = Var { base = BThis; offset = [] }; tokens = [] }

2. FunctionHOF - map(callback, data): Passes one parameter to another

   (* Signature models: callback receives data from another parameter *)
   let data_param_taint = Taint.{ orig = Var { base = BArg data_arg; offset = [] }; ... }

3. ReturningFunctionHOF - Ruby's arr.map returns a function that takes a block

   (* Returns Shape.Fun with nested signature for deferred callback *)
   let return_effect = Effect.ToReturn {
     data_taints = this_taint_set;
     data_shape = Shape.Fun returned_fun_sig;  (* The function shape *)
     ...
   }

Supported languages and functions (get_hof_configs):

3. Labeled Call Graph with HOF Edges

File: src/tainting/Function_call_graph.ml (major rewrite, +869 lines)

Before: Simple graph FuncGraph = Persistent.Digraph.Concrete(FuncVertex)

After: Labeled imperative graph with edge metadata:

type call_edge = {
  callee_fn_id : fn_id;   (* Full path of callee *)
  call_site : Tok.t;      (* Token at the call site *)
}

module FuncGraph = Graph.Imperative.Digraph.ConcreteLabeled(FuncVertex)(...)

Why labeled edges:

• Multiple calls to the same function from different sites need to be distinguished
• The call site token allows signature instantiation to find the correct callee
• HOF callbacks need different edges than regular calls

Key functions:

1. identify_callee - Resolves a call expression to its fn_id:

   • Checks nested functions in the same scope first
   • Then class methods
   • Then top-level functions
   • Handles this.method(), obj.method(), qualified names

2. extract_calls - Extracts all (fn_id, call_site_tok) pairs from a function body

3. extract_hof_callbacks - Extracts HOF callback edges:

   • Uses Builtin_models.get_hof_configs to know which methods are HOFs
   • Detects user-defined HOFs via detect_user_hof
   • Creates special HOF edges with fake tokens like <hof_callback:foo>

4. detect_user_hof - Checks if a function calls any of its parameters:

   let detect_user_hof (fdef : G.function_definition) : (string * int) list

4. Graph Reachability Optimization

New File: src/tainting/Graph_functor.ml (132 lines)

For large codebases, analyzing every function is expensive. This module computes the minimal subgraph needed for a specific rule.

Key function: nearest_common_descendant_subgraph

(* Subgraph containing all paths from sources to sinks *)
val nearest_common_descendant_subgraph : graph -> vertex -> vertex -> graph

Algorithm:

1. Compute forward-reachable sets from source functions (R1) and sink functions (R2)
2. Intersect to get functions reachable from both (R1 ∩ R2)
3. Find minimal SCCs in intersection (handles cycles from mutual recursion)
4. Reverse BFS from minima to include all ancestors

Usage in Match_tainting_mode.ml:

let source_functions = find_functions_containing_ranges ast source_ranges in
let sink_functions = find_functions_containing_ranges ast sink_ranges in
let relevant_graph = compute_relevant_subgraph call_graph source_functions sink_functions in

5. Parent Path Visitor

File: src/analyzing/Visit_function_defs.ml (+167 lines)

New visitor: visitor_with_parent_path tracks the full path to each function during AST traversal.

class visitor_with_parent_path = object
  val parent_path : IL.name option list ref = ref []
  (* Tracks: [class; outer_func; inner_func; ...] *)
end

val fold_with_parent_path :
  ('acc -> G.entity option -> IL.name option list -> G.function_definition -> 'acc)
  -> 'acc -> G.program -> 'acc

Why: The old fold_with_class_context only tracked class names. For nested functions, we need the full path to build correct fn_ids.

6. ToSinkInCall Effect

File: src/tainting/Sig_inst.ml:38-48, 876-1107

New effect type added to signature instantiation:

type call_effect =
  | ToReturn of Effect.taints_to_return
  | ToSink of Effect.taints_to_sink
  | ToLval of Taint.taints * IL.name * Taint.offset list
  | ToSinkInCall of {       (* NEW *)
      callee : IL.exp;
      arg : Taint.arg;
      args_taints : Effect.args_taints;
    }

Instantiation logic (simplified):

1. When encountering ToSinkInCall effect during signature instantiation:
2. Look up the callback's signature (from lval_env shape, or via lookup_sig)
3. Instantiate the callback with the provided args_taints
4. If no signature found, preserve the effect for later resolution
5. Add depth limiting to prevent infinite recursion on recursive HOFs

Key change: instantiate_function_signature now takes optional lookup_sig and depth parameters:

let rec instantiate_function_signature lval_env taint_sig
    ~callee ~args args_taints
    ?(lookup_sig : (IL.exp -> int -> Signature.t option) option)
    ?(depth : int = 0) () : call_effects option

7. Signature Lookup via Call Graph

File: src/tainting/Dataflow_tainting.ml:667-730

New function queries the call graph to resolve function calls:

let lookup_callee_from_graph graph caller_fn_id call_tok : fn_id option =
  (* Find edge with matching call_site token *)
  all_edges
  |> List.find_opt (fun edge ->
      Int.equal (Tok.compare label.call_site call_tok) 0)
  |> Option.map (fun edge -> label.callee_fn_id)

Lookup order:

1. Check call graph for edge with matching call site token
2. If found, use the pre-computed callee_fn_id from the edge label
3. Fall back to direct name lookup
4. Fall back to builtin signature database

8. Ruby Class Method Fix

File: languages/ruby/generic/ruby_to_generic.ml:794-815

Bug: Ruby class methods (def self.method_name) were being parsed with empty entity names, causing all class methods to collapse into a single node.

Before:

| SingletonM e ->
    let e = expr e in
    let ent = G.basic_entity ("", fake t "") in  (* Empty name! *)
    ...

After:

| SingletonM e ->
    let method_id =
      match e with
      | DotAccess (_, _, mn) -> (
          match method_name mn with
          | Left id -> id
          | Right _ -> ("", fake t ""))
      | ScopedId (Scope (_, _, SM mn)) -> ...
      | _ -> ("", fake t "")
    in
    let e = expr e in
    let ent = G.basic_entity method_id in  (* Correct name! *)
    ...

Impact: Call graph now correctly shows Service.default_integration and Service.closest_group_integration as separate nodes instead of both being Service..

9. Parameter Shape for HOF Detection

File: src/tainting/Taint_signature_extractor.ml:123-214

Parameters now get Shape.Arg shape instead of just taints:

let add_param_to_env il_lval taint_set taint_arg env =
  let param_shape = Shape.Arg taint_arg in
  Taint_lval_env.add_lval_shape il_lval taint_set param_shape env

Why: When a parameter is used as a callback in a HOF call, we need to know it's an "argument" to create proper ToSinkInCall effects. The Arg shape carries the parameter's index.

10. Match_tainting_mode Integration

File: src/engine/Match_tainting_mode.ml (+343 lines of changes)

Major refactoring to use the new infrastructure:

1. Shared call graph: Computed once per file, shared across rules

   let shared_call_graph_opt =
     if taint_intrafile then
       Some (Function_call_graph.build_call_graph ~lang ~object_mappings ast)
     else None

2. Relevant subgraph optimization:

   let source_functions = find_functions_containing_ranges ast source_ranges in
   let sink_functions = find_functions_containing_ranges ast sink_ranges in
   let relevant_graph = compute_relevant_subgraph call_graph source_functions sink_functions in

3. Topological ordering for analysis:

   let analysis_order = Topo.fold (fun fn acc -> fn :: acc) relevant_graph [] |> List.rev

4. Kotlin trailing lambda support: Functions with lambda as last parameter get signatures extracted at arity and arity-1:

   if Lang.equal lang Lang.Kotlin && arity >= 2 then
     let last_param_is_lambda = ... in
     if last_param_is_lambda then
       extract_signature_with_file_context ~arity:(arity - 1) ...

Data Flow Example

Consider this TypeScript code:

function source() { return tainted; }
function sink(x) { /* dangerous */ }
function process(items) {
  return items.map(x => transform(x));
}
function transform(x) { return x; }

let data = [source()];
let result = process(data);
sink(result[0]);

Analysis flow:

1. Build call graph:

   <toplevel> --calls--> source (at source() call)
   <toplevel> --calls--> process (at process(data) call)
   <toplevel> --calls--> sink (at sink(...) call)
   process --calls--> transform (via map HOF callback edge)
   

2. Compute relevant subgraph: Functions between source and sink

3. Topological order: transform, process, <toplevel> (leaves first)

4. Extract signatures:

   • transform: ToReturn { data_taints = {Arg(x, 0)} } (returns its input)
   • process:
     • map builtin has ToSinkInCall { callee = callback, args_taints = [BThis] }
     • When lambda x => transform(x) is analyzed, we look up transform's signature
     • Result: ToReturn { data_taints = {Arg(items, 0)} } (returns transformed items)

5. Instantiate at call sites:

   • process(data) where data is tainted from source()
   • Substitute Arg(items, 0) → taint from data
   • Result flows to sink(result[0]) → FINDING!

Test Coverage

New test files (17 languages):

• test_hof_comprehensive_*.{js,ts,py,rb,java,kt,scala,swift,cs,rs,lua,php,go,cpp,c,julia,ex}

Each test covers:

1. Basic HOF taint propagation (map, filter, forEach)
2. Chained HOFs (arr.map(...).filter(...))
3. Reduce with accumulator
4. Nested callbacks
5. User-defined HOFs (functions that call their parameters)
6. Cross-function taint through HOFs

Configuration

No new configuration options. HOF support is automatically enabled when taint_intrafile is true.

Performance Considerations

1. Call graph is shared: Computed once per file, reused across all rules
2. Subgraph optimization: Only functions on paths between sources and sinks are analyzed
3. Depth limiting: Recursive HOF instantiation is limited by taint_MAX_VISITS_PER_NODE
4. Builtin signatures are pre-computed: Language-specific HOF models are created once

Benchmark Script

A benchmark script is provided at benchmark_taint.sh for comparing OpenGrep vs Semgrep taint analysis performance:

# Usage
./benchmark_taint.sh [--no-semgrep] <yaml_file_or_dir> <target_file_or_dir> [num_runs] [sha1] [sha2] ...

# Examples
./benchmark_taint.sh rules/sqli.yaml target_repo/ 3
./benchmark_taint.sh --no-semgrep rules/ target_repo/ 5
./benchmark_taint.sh rules/ target_repo/ 3 main abc123  # Compare current vs main vs abc123

Options:

• --no-semgrep: Skip Semgrep benchmarks (useful when Semgrep is not installed or for quick OpenGrep-only tests)
• num_runs: Number of runs to average (default: 3)
• sha1, sha2, ...: Git commits/branches to compare (will checkout, compile, and benchmark each)

Output: Summary table with findings count and timing (avg ± std) for each configuration