Assignment 3 - SVF-tools/Software-Security-Analysis GitHub Wiki

Assignment-3 folder layout

Assignment-3/
|-- CPP/
|   |-- AEHelper.cpp
|   |-- AEReporter.cpp
|   |-- AEReporter.h
|   |-- AEState.cpp
|   |-- AEState.h
|   |-- Assignment_3.cpp
|   |-- Assignment_3.h
|   |-- CMakeLists.txt
|   `-- test-ae.cpp
|-- Python/
|   |-- AEHelper.py
|   |-- AEReporter.py
|   |-- AEState.py
|   |-- Assignment_3.py
|   |-- CMakeLists.txt
|   `-- test-ae.py
`-- Tests/
    |-- level-1/
    `-- level-2/

1. Get the latest code template

Before coding, update your local repository:

cd "$HOME/Software-Security-Analysis"
git pull

if you use pysvf, update pysvf

pip install pysvf -U  # or: pip install -U pysvf --force-reinstall

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

2. Assignment tasks

Implement an abstract executor over SVF's interval and address-set domains. The executor must analyse interprocedural control flow, model relevant external APIs, handle branches, loops and recursions, verify assertions, detect buffer overflows and null-pointer dereferences.

• C++: implement and submit Assignment_3.h and Assignment_3.cpp.
• Python: implement and submit Assignment_3.py.
• You may add your own helper functions inside the submitted file(s).
• Treat AEState, AEHelper, AEReporter, the test drivers, and CMake files as supplied infrastructure.

Features 1–4 form the general analysis engine, while Features 5–6 are bug checkers built on top. These are only suggested requirements; additional features may be needed for precise detection. You are strongly encouraged to create your own tests and explore other necessary features to capture true positives and reduce false positives in real-world programs.

The supplied analyse() method starts the analysis. You must complete these five driver entry points (feel free to add your own methods/helpers in the AbstractExecution class):

Entry point	Implementation
handleGlobalNode	Initialise and execute the global ICFG node.
handleFunction	Walk a function's interprocedural WTO components.
handleICFGNode	Build the incoming state, execute statements/calls/checkers, and report whether the post-state changed.
handleICFGCycle	Drive a loop or recursive SCC to a terminating fixpoint.
handleCallSite	Dispatch stubs, external calls, and ordinary callees.
bufOverflowDetection	Detect a buffer overflow on a particular ICFGNode
nullptrDerefDetection	Detect a null deference on a particular ICFGNode

A typical design has handleFunction dispatch WTO components, handleICFGNode run Features 1, 2, 5, and 6, and handleCallSite run Feature 4. Other decompositions are valid if every reachable node and checkpoint is handled.

2.1 Feature 1: Statement transfer functions

What to implement

• Handle AddrStmt, BinaryOPStmt, CmpStmt, LoadStmt, StoreStmt, CopyStmt, GepStmt, PhiStmt, CallPE, RetPE, SelectStmt.
  • In Assignment 3, you are now expected to handle all BinaryOp, not just a subset as in Assignment 2. IntervalValue allows you to pass floats, which get converted internally to BoundedInt.
• Initialise objects and also nullptr (IRGraph::NullPtr) as a null memory address (AddressValue(NullMemAddr)) and distinguish intervals from address sets.

handleGlobalNode should handle global statements. handleICFGNode should run the statement dispatcher for each type of SVF statement on the node.

AE APIs

• C++ APIs for Feature 1
• Python APIs for Feature 1

2.2 Feature 2: Branch feasibility

What to implement

• Merge post-states from feasible predecessor edges.
• For a conditional edge, apply the edge's true/false or switch constraint to an independent copy of the predecessor state.
• Exclude an edge when its condition cannot hold.
• Preserve the function-entry pre-state when no ordinary predecessor state is available.
• Ensure phi operands are taken only from feasible incoming paths.

AE APIs

• C++ APIs for Feature 2
• Python APIs for Feature 2

2.3 Feature 3: Loop and recursion fixpoint

What to implement

• Walk singleton and cycle components in the WTO built with the starter code harness.
• Iterate a cycle until its head state stabilises.
• Use precise iterations first, widening to guarantee termination, then narrowing to recover useful bounds.
• Use the same cycle mechanism for loops and recursive call-graph SCCs.
• Return or compare node-state changes so fixpoint iteration can stop.

Implement the traversal in handleFunction and the fixpoint in handleICFGCycle.

AE APIs

• C++ APIs for Feature 3
• Python APIs for Feature 3

2.4 Feature 4: External-API value summaries

What to implement

• Complete handleCallSite dispatch for assertion/checkpoint stubs, nondeterministic nd/rand, external APIs, ordinary callees, and recursive call sites.
• Model value and memory effects for memcpy, memmove, memset, strcpy, strncpy, strcat, strncat, strlen, wcslen, mem_insert, and str_insert (more if you would like to analyze large-sized programs).
• Propagate call state to the appropriate return node without aliasing mutable Python trace entries.
• Run the relevant checkers for external memory/string operations.
• Handle unknown external effects conservatively.

AE APIs

• C++ APIs for Feature 4
• Python APIs for Feature 4

2.5 Feature 5: Buffer-overflow checker

What to implement

• Identify the pointer, access length, base object, and accumulated byte offset for each relevant memory access.
• Check both lower and upper bounds when they are known.
• Cover direct load/store/GEP accesses and external memory/string operations.
• Treat unknown or black-hole objects conservatively instead of inventing a precise size.
• Report each real unsafe access with reportBufOverflow(node) and avoid duplicate false alarms on safe accesses.

The supplied task hook is bufOverflowDetection. Invoke it for ordinary ICFG nodes and from the external-call path where appropriate.

AE APIs

• C++ APIs for Feature 5
• Python APIs for Feature 5

2.6 Feature 6: Null-pointer-dereference checker

What to implement

• Inspect pointers dereferenced by load, store, GEP, and relevant external operations.
• Preserve and recognise explicit null values.
• Treat null and freed addresses as unsafe; handle black-hole/unknown addresses conservatively.
• Report the actual unsafe dereference with reportNullDeref(node).
• Avoid reports when branch feasibility has established that the pointer is non-null.

The supplied task hook is nullptrDerefDetection. Invoke it for ordinary nodes and from the external-call path where appropriate.

AE APIs

• C++ APIs for Feature 6
• Python APIs for Feature 6

3. How your work is assessed

Assignment 3 is worth 30 points. Public examples are provided for development, but they are not the complete marking suite. Additional hidden cases are used; their count, distribution, and per-case weights are not published.

3.1 Marking and internal levels of test cases

Level	Points	What is assessed
Level 1	10	Individual abstract-execution features, including the six tasks above.
Level 2	10	End-to-end analysis of active real-program fixtures: target reporting, report precision, and successful completion.
Level 3	10	Large-program execution, target detection, and report precision.

Marking based on true and false positives

• For testcases in Level 1, you must correctly identify the bug in the program (the true positive), and that bug only. If your program detects anything else (false positives), then you will get 0 for that testcase.

• For testcases in Level 2, false positives no longer immediately cause you to get a 0. Instead, each false positive will incur a 20% penalty of the mark for that testcase, up to a final mark of 0 for that testcase. As before, you must identify the true positive.

• For testcases in Level 3, we set a threshold of false positives - you are allowed up to 5 false positives with no deductions in mark. Each false positive beyond the threshold will incur a 10% penalty for that testcase, up to a final mark of 0 for that testcase. As before, you must identify the true positive.

Dry run

• Level 1: We provide several small, feature-focused public examples are provided under Tests/level-1/. Marking also includes examples that cover the 6 features in the spec.
• Level 2: We provide one example that uses the external library curl under Tests/level-2/. Marking also includes additional, medium-sized programs.
• Level 3: No public test is provided. Marking uses larger programs.

Timeout

We set a timeout. That is to say, performance does matter. This should be of no concern for level 1 (hitting the timeout would indicate an infinite loop, for example), but may matter for larger tests. The timeout is generous.

3.2 Marking harness and implementation requirements

Marking does not compare arbitrary text printed by your implementation. Instead, it uses the supplied harness and reporter:

• svf_assert and svf_assert_eq inspect the abstract state at the call site. Every assertion call must be reached and validated.
• SAFE_* and UNSAFE_* calls are checker checkpoints. Your call-site dispatch must invoke handleCheckpointStubs to record reachability and then invoke the matching bufOverflowDetection or nullptrDerefDetection checker. At an UNSAFE_* checkpoint, the checker must create the matching bug kind at that checkpoint's ICFGNode; at a SAFE_* checkpoint, it must not create that bug kind.
• Bug checkers must use reportBufOverflow(node) and reportNullDeref(node) with the actual unsafe ICFGNode. The supplied helper routes each call to the matching bug kind; calling the appropriate function is all your checker needs to report the bug. The supplied reporter preserves the bug kind, node ID, source location, and diagnostic.
• Real-program marking matches the reporter's source locations against target locations and counts additional reports as false positives.

Preserve the supplied AEState, AEHelper, AEReporter, drivers, and build files. Your implementation must:

• maintain preAbsTrace and postAbsTrace in C++, or pre_abs_trace and post_abs_trace in Python, using AEState values;
• route the ground-truth stubs as described above; and
• use the supplied reporting APIs.

The grader provides fresh copies of this infrastructure and builds them with your submitted Assignment_3.cpp and Assignment_3.h, or Assignment_3.py.

For the public-case commands and expected results, see Assignment-3/Tests/README.md and Assignment-3/Tests/GRADING.md in the student repository.

4. Run and submit

Run tests

• C++: running tests
• Python: running tests

Upload your solution

Submit from the directory containing your implementation. File names are exact and case-sensitive.

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 files are required. You may resubmit before the deadline; only the latest accepted submission is marked. See Uploading submissions using give for details.

Language-specific submission notes:

• C++: submitting your work
• Python: submitting your work

5. Configuration and debugging

• C++: configuration and debugging
• Python: configuration and debugging