Lab Exercise 1
% tree
├── CMakeLists.txt
├── CPP
│ ├── GraphAlgorithm.cpp
│ ├── GraphAlgorithm.h
│ └── test.cpp
└── Python
└── GraphTraversal.ipynb
* 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 coding.
If git pull fails due to the conflict with your local changes, type git stash to store your current code in a temporal branch and type git pull again. If you want to retrieve your code back, type git stash pop.
Implement the following methods of class GraphAlgorithm in either:
| Function | Description | Marks |
|---|---|---|
reachability |
DFS to traverse and record each path from src to dst (each node appear at most once on each path) |
50% |
solveWorklist |
Constraint solving to mimic Andersen’s inclusion-based points-to analysis | 50% |
| C-like form | Constraint form | Solving rule | Explaination |
|---|---|---|---|
p = &o |
p <--ADDR-- o | pts(p) = pts(p) ∪ {o} | add o into p's points-to set |
q = p |
q <--COPY-- p | pts(q) = pts(q) ∪ pts(p) | union p's points-to set into q's one |
q = *p |
q <--LOAD-- p | for each o ∈ pts(p) : add q <--COPY-- o | for each o in p's points-to set, add a COPY edge from o to q (if it is not on the graph) |
*p = q |
p <--STORE-- q | for each o ∈ pts(p) : add o <--COPY-- q | for each o in p's points-to set, add a COPY edge from q to o (if it is not on the graph) |
To test your implementation:
- For C++: Run
ctest -R lab1 -VVand ensure all tests pass without assertions intest.cpp - For Python: Execute each module individually in
GraphAlgorithm.ipynb
Upload GraphAlgorithm.cpp(or GraphTraversal.ipynb if you use Python) to UNSW WebCMS for your submission when you are finished with this lab.
You can also use the give command (available on CSE servers). A guide to submitting your labs/assignments using give can be found here.
Your implementation will be evaluated against our internal tests. You will get the full marks if your code can pass them all. Unfortunately, internal tests are private. Here, we only provided two test cases in test.cpp. It does NOT mean that your solution is correct, even if you pass these two tests. You are encouraged to add more test cases by yourself to validate the correctness of your implementation.
*You will be working on GraphAlgorithm.cpp or GraphTraversal.ipynb only, and there is NO need to modify other files under the Lab-Exercise-1 folder.
Each node on the CGraph represents a pointer and getPts retrieves the points-to set of a node. The implementation requires iterative solving based on the following rules by (1) propagating points-to sets among nodes on CGraph, and (2) adding new COPY edges until a fixed point is reached (i.e., no new copy edges are added). Note that the graph will become larger with newly added COPY edges once the solving reaches the convergence (no need to delete those edges at the end).
For C++, please refer to this section.
For Python, please refer to this section.
For C++, please refer to this section.
For Python, please refer to this section.