Lab Exercise 1 - SVF-tools/Software-Security-Analysis GitHub Wiki

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.

width=600px

2. Lab-Exercise-1 coding task

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 -VV and ensure all tests pass without assertions in test.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.

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).

3. Configuration && debugging

For C++, please refer to this section.

For Python, please refer to this section.

4. More information

For C++, please refer to this section.

For Python, please refer to this section.

5. Implementation hints

  • Points-to sets
    • To read
      • C++: getPts
      • Python: get_pts
    • To write
      • C++: unionPts, addPts
      • Python: union_pts, add_pts
  • Edges/instructions
    • To read
      • C++: getOutEdges, getInEdges
      • Python: get_out_edges, get_in_edges
    • To write
      • C++: addEdge
      • Python: add_edge
  • Worklist
    • C++: pushIntoWorklist, popFromWorklist
    • Python: push_into_worklist, pop_from_worklist
  • You are implementing this in CGraph; you have direct access to its fields
  • Some interfaces operate on node IDs (like the worklist methods) and some operate on pointers to node objects (like some of the points-to set methods)
  • Beware of unintentionally modifying references to data structures!
  • Adding to the worklist is conditional in the main loop, if you are adding to it unconditionally, you may be doing something wrong