Multi-Pass Analyzer

Work on this exercise locally

This web app is a reference guide — you can read instructions, browse starter code, and view tests here. To actually complete the exercise, you need to work in your local development environment.

1Clone the repo: git clone https://github.com/weihaoqu/program-analysis-bootcamp-student

2Edit the starter file in your editor (VS Code, Vim, etc.) — replace failwith "TODO" with your implementation.

3Run the tests: dune runtest modules/module6-tools-integration/exercises/multi-pass-analyzer

4. Exercise 3: Multi-Pass Analyzer (20 tests)

Goal: Compose safety (sign domain) and taint analysis into independent passes, then run, merge, and partition their findings.

Time: ~30 minutes

File to edit: exercises/multi-pass-analyzer/starter/multi_pass.ml

Also provided (do not edit):

sign_domain.ml -- complete sign abstract domain
taint_domain.ml -- complete taint abstract domain
finding_types.ml -- unified finding types with helpers
sample_programs.ml -- test programs (div-by-zero, taint-to-sink, etc.)

Dependencies: abstract_domains, shared_ast

What to implement (in order)

#	Function	Hint
1	`make_safety_pass ()`	Create an `analysis_pass` named `"safety"` with category `Safety`. Use `MakeEnv(Sign_domain)` for the environment. Evaluate expressions with sign arithmetic. Detect `BinOp(Div, _, denom)` where divisor is `Zero` (High severity) or `Top` (Medium severity).
2	`make_taint_pass ()`	Create an `analysis_pass` named `"taint"` with category `Security`. Use `MakeEnv(Taint_domain)` for the environment. Hardcode sources/sinks/sanitizers (listed in the docstring). Check sink calls for tainted arguments, emitting Critical severity findings.
3	`run_pass pass prog`	Simply call `pass.run prog`
4	`run_all_passes passes prog`	Run each pass and concatenate all findings
5	`merge_findings findings_list`	Flatten the list of lists, then sort by severity (highest first)
6	`partition_by_pass findings`	Group findings by `pass_name`, preserving first-seen order of pass names. Return `(pass_name, findings) list`.
7	`default_passes ()`	Return `[make_safety_pass (); make_taint_pass ()]`

Hardcoded sources, sinks, and sanitizers for the taint pass

Sources:    get_param, read_cookie, read_input, read_file, get_header
Sinks:      (exec_query, sql-injection), (send_response, xss),
            (exec_cmd, command-injection), (open_file, path-traversal)
Sanitizers: escape_sql, html_encode, shell_escape, validate_path

Run tests

dune runtest modules/module6-tools-integration/exercises/multi-pass-analyzer/

Starter output (all 20 tests error):

EEEEEEEEEEEEEEEEEEEE

Hints:

You need to create SignEnv and TaintEnv modules using the MakeEnv functor from Abstract_domains.Abstract_env. Wrap the domain in a struct that satisfies ABSTRACT_DOMAIN:

module SignEnv = Abstract_domains.Abstract_env.MakeEnv (struct
  type t = Sign_domain.sign
  let bottom = Sign_domain.bottom
  let top = Sign_domain.top
  let join = Sign_domain.join
  (* ... etc ... *)
end)

For the safety pass, write a recursive eval_sign and transfer_sign inside make_safety_pass. Initialize function parameters to Sign_domain.Top.
For the taint pass, write a recursive eval_taint and transfer_taint. Literal values are Untainted, source calls return Tainted, sanitizer calls return Untainted.
While loops need a fixpoint with widening (same pattern as Module 4).

Starter Files

starter

Test Files

tests

starter/finding_types.ml

Read-only

Loading editor...

Work on this exercise locally

1Clone the repo: git clone https://github.com/weihaoqu/program-analysis-bootcamp-student

2Edit the starter file in your editor (VS Code, Vim, etc.) — replace failwith "TODO" with your implementation.

3Run the tests: dune runtest modules/module6-tools-integration/exercises/multi-pass-analyzer