Skip to content

Assignment 3

Jump to bottom
Yulei Sui edited this page Jun 7, 2026 · 52 revisions

Assignment-3 folder layout

../Assignment-3/
|-- CPP
|   |-- Assignment_3.h     # <-- the file you implement and submit
|   |-- Assignment_3.cpp   # <-- the file you implement and submit
|   |-- AEHelper.cpp       # harness: WTO + stub / checkpoint dispatch +
|   |                      #          abstract-state helpers + validator
|   |-- AEReporter.h/.cpp  # harness: bug accumulation + JSON / coverage summary
|   |-- test-ae.cpp        # test driver (do not modify)
|   `-- CMakeLists.txt
|-- Python
|   |-- Assignment_3.py    # <-- the ONLY file you implement
|   |-- AEHelper.py        # harness: WTO + stub / checkpoint dispatch +
|   |                      #          abstract-state helpers + validator
|   |-- AEReporter.py      # harness: bug accumulation + JSON / coverage summary
|   |-- test-ae.py         # test driver (do not modify)
|   `-- CMakeLists.txt
`-- Tests
    |-- stmt.c          stmt.ll
    |-- buf_overflow.c  buf_overflow.ll
    `-- null_deref.c    null_deref.ll

1. Get the latest code template

* Before coding, please type cd $HOME/Software-Security-Analysis and git pull in your terminal to make sure you always have the latest version of the code template before each assignment.

Make sure your IDE/debug configuration runs the ass3 target before coding. See Configure IDE for setup details.

2. Assignment 3 task

In this assignment you implement an abstract executor that analyses a program over the interval + address-set abstract domain and finds two classes of memory-safety bugs: buffer overflows and null-pointer dereferences.

  • For the C++ implementation, you need to complete your assignment in two files, Assignment_3.h and Assignment_3.cpp, and submit both files via WebCMS or give.
  • For the Python implementation, you need to complete your assignment in Assignment_3.py and submit that file.

The harness is split into two side files that you should treat as read-only:

  • AEHelper.cpp / AEHelper.py — interprocedural WTO construction, sub-dispatch for the svf_assert / SAFE_* / UNSAFE_* stubs, the external-API whitelist (isExternalCallForAssignment), the abstract-state helpers that wrap the underlying AbstractInterpretation singleton (getAbsValue / updateAbsValue / loadValue / storeValue / GEP / alloca-size helpers), and the assertion-coverage validator (ensureAllAssertsValidated).
  • AEReporter.h / AEReporter.cpp / AEReporter.py — bug accumulation, per-kind reporting, and the JSON / coverage summary emitted to the grader.

Assignment_3 itself ships a small analysis driver (runOnModule / analyse / reportBufOverflow / reportNullDeref) that is already wired up so you can run the binary from day one. Everything else in the file is yours to write.

The work falls into three groups. The first is the general analysis engine — the abstract state, the reasoning, and the library-call models that everything else relies on. The other two are the bug checkers that sit on top of it. Build them in that order: until the engine tracks values with some precision, the checkers have nothing reliable to reason about.

The subsections below describe what each part is responsible for — not how to implement it. The contract of each method, and the APIs you may call, are documented in the header comments above the method in Assignment_3.cpp / Assignment_3.py and in the abstract-execution API reference.

Where your work plugs in

The harness only calls into five entry points on AbstractExecution. Four are pre-declared driver hooks (handleGlobalNode, handleFunction, handleICFGNode, handleICFGCycle); the fifth is handleCallSite, the call-node dispatcher. How you internally route the six tasks below into those five entry points is your design choice — a typical layering has the per-statement work happen inside handleICFGNode, the loop / recursion fixpoint inside handleICFGCycle, and the external-API summaries inside handleCallSite.

For the rest of the six tasks (statement transfer, branch refinement, external-API summaries, the two bug checkers), the parent AbstractExecution ships no-op virtual hooks named updateAbsState, mergeStatesFromPredecessors, updateStateOnExtCall, bufOverflowDetection, nullptrDerefDetection. Override any of them on your subclass if you want your handleCallSite to drive into your code automatically; otherwise you are free to invent your own method names and call them yourself from handleICFGNode / handleICFGCycle.

2.1 General analysis engine

This is the core of the abstract executor: it walks the program over the interval + address-set domain and keeps, for every variable, an abstract value (an interval for a number, a set of memory addresses for a pointer). It has four responsibilities:

  • Statement transfer functions — the rules for how a single statement updates the abstract state: assignment and casts, arithmetic, writing and reading through a pointer, pointer arithmetic, and merging values that arrive from different predecessors. Everything downstream reads the state these produce, so imprecision here propagates everywhere. Typically lives inside handleICFGNode.
  • Branch refinement — a condition tells you something about each of its outgoing edges; this uses that to narrow the state flowing into each successor and to drop edges whose condition can never hold. It sets the precision ceiling of both checkers: too little refinement raises false alarms on safe code, too aggressive pruning hides real bugs. Typically lives inside handleICFGNode.
  • Cycle and recursion fixpoint — a loop body, or a recursive function re-entered through its own call/return edge, forms a cycle; this drives such a cycle to a fixpoint that terminates while still yielding useful bounds. The harness builds the cycles for you, and loops and recursion are handled by the same routine — you do not write separate recursion code. Typically lives inside handleICFGCycle.
  • External-API value summaries — library calls (the memcpy / memmove / memset / strcpy / strncpy / strcat / strncat / strlen / wcslen family, plus the assignment-specific mem_insert / str_insert stubs) have no body the analysis can see, so each needs a summary of its effect: propagate the values it writes, and expose the pointers and length it touches so the checkers below can judge it. Calls you do not model are handled conservatively. Typically lives inside handleCallSite.

2.2 Buffer-overflow checker

The first bug checker. Its job is to decide, from the abstract state, whether a memory access can reach outside the bounds of the object it belongs to — past the end of an array, or before its start — and to report it at the real access site. This builds directly on the engine: it needs the object a pointer refers to, how far into that object the access lands, and how many bytes it touches — all of which §2.1 is responsible for producing.

2.3 Null-pointer-dereference checker

The second bug checker. Its job is to decide whether a pointer that is about to be read or written may be null (or otherwise invalid), and to report it at the real dereference site. For this to work, "null" has to be tracked as a real abstract value that survives as it flows through the program — which is exactly what the engine in §2.1 is responsible for. Like the overflow checker, it must fire on genuinely unsafe dereferences without flagging pointers that have been established as safe.

The header comments above each method describe its contract, and the abstract-execution API reference lists the available helpers.

  • C++: implement the methods of AbstractExecution declared in Assignment_3.h in Assignment_3.cpp. Reach the abstract state only through the helpers exposed on AbstractExecution (getAbsValue / updateAbsValue / loadValue / storeValue / getGepObjAddrs / getGepElementIndex / getGepByteOffset / getAllocaInstByteSize / getAbsStateFromTrace); their contracts live in Assignment_3.h.
  • Python: implement the methods of Assignment3 (subclass of AbstractExecution) in Assignment_3.py; the harness is split across AEHelper.py (driver / dispatch / abstract-state helpers / validator) and AEReporter.py (bug accumulation + summary).

3. How your work is assessed

The autograder scores end-to-end behaviour of your analyzer on a suite of test programs, not isolated points per method — so the analysis engine and the checkers have to work together.

The suite ranges from small, single-purpose programs up to larger, real-world C code. Broadly, it exercises:

  • whether your abstract state stays precise enough to prove the intended property on programs that are safe, and
  • whether your checkers actually catch the intended bug on programs that are unsafe, without flooding safe code with false alarms.

A good submission is judged on the balance of true positives, false positives, running time, and how much of each program it manages to analyse. A few sample programs (stmt, buf_overflow, null_deref under Tests/) are provided so you can do a quick local sanity check while you develop; the programs used for marking are not shipped with the template and are deliberately more varied.

The harness also includes a coverage check: every ground-truth stub call site (svf_assert, svf_assert_eq, the SAFE_* / UNSAFE_* checkpoint stubs) must be reached by your analysis. If your control-flow logic skips a stub call site, ensureAllAssertsValidated (in AEHelper) will trip an assertion at the end of analyse().

Run Tests

Upload Your Solution

Submit with give on a CSE machine, from the directory containing your file(s). File names are exact and case-sensitive — do not rename, zip, or add other files.

Language Command
C++ give cs6131 ass3 Assignment_3.cpp Assignment_3.h
Python give cs6131 ass3 Assignment_3.py

A successful submission reports Your submission is ACCEPTED.. For C++, both Assignment_3.cpp and Assignment_3.h are required — submitting the .cpp without its .h is rejected with all accept groups fail. You may resubmit any number of times before the deadline; only your latest accepted submission is marked. See Uploading submissions using give for details.

Language-specific notes:

4. Configuration and Debugging

Clone this wiki locally