Lab Exercise 1

Lab-Exercise-1 folder layout

% tree
├── CMakeLists.txt
├── CPP
│   ├── GraphAlgorithm.cpp
│   ├── GraphAlgorithm.h
│   └── test.cpp
└── Python
    └── GraphTraversal.ipynb

1. Get the latest Lab-Exercise-1 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 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.

2. Lab-Exercise-1 coding task

• Implement the following methods of class GraphAlgorithm in either:
  • GraphAlgorithm.cpp (recommended)
  • GraphAlgorithm.ipynb

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%

• Hints for implementing solveWorklist. 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).

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 -VV and ensure all tests pass without assertions in test.cpp
  • For Python: Execute each module individually in GraphTraversal.ipynb
• Upload GraphAlgorithm.cpp(or GraphTraversal.ipynb if you use python) to UNSW WebCMS for your submission when you are finished with this lab. 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 only and there is NO need to modify other files under the Lab-Exercise-1 folder(For Python, please refer to the more detailed instructions in GraphTraversal.ipynb)

3. Configuration && debugging

For C++, please refer to this section(recommended)
For Python, Please refer to this section

4.More information

For C++, please refer to this section(recommended)
For Python, Please refer to this section