Assignment 1 - SVF-tools/Software-Security-Analysis GitHub Wiki
Assignment-1 folder layout
$tree Assignment-1
├── Assignment-1.cpp
├── Assignment-1.h
├── CMakeLists.txt
├── SrcSnk.txt
└── Tests
├── CMakeLists.txt
├── test.cpp
└── testcases
└── icfg
├── test1.c
├── test1.ll
├── test2.c
└── test2.ll
└── pta
├── test1.c
├── test1.ll
├── test2.c
└── test2.ll
├── test3.c
└── test3.ll
├── test4.c
└── test4.ll
└── taint
├── test1.c
├── test1.ll
├── test2.c
└── test2.ll
1. Get the latest Assignment-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 each assignment.
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. Assignment 1 coding task
- Implement the following methods of class ICFGTraversal and AndersenPTA in Assignment-1.cpp by using some SVF APIs here.
| Function | Description | Marks |
|---|---|---|
readSrcSnkFromFile |
Identify sources and sinks by parsing APIs in SrcSnk.txt for reachability analysis |
20% |
reachability |
Context-sensitive reachability analysis on the ICFG | 30% |
solveWorklist |
Field-sensitive inclusion-based points-to analysis (Andersen's analysis) | 30% |
aliasCheck |
Check aliases of the two variables at source and sink. Two variables are aliases if their points-to sets have at least one overlapping element. | 20% |
- Tainted Information Flow:
Given a tainted source v1@src (variable v1 at program point src), we say that a sink v2@snk is also tainted if both the following conditions satisfy: (1) src reaches snk on the ICFG via context-sensitive reachability analysis, and (2) pts(v1) ∩ pts(v2) ≠ ∅ inferred by Andersen's field-sensitive analysis. Note that in this assignment, v1 is the return value when calling a source function, and v2 is any argument of the sink function.
- Tips for implementing reachability and solveWorklist.
The implementation of reachability differs from the one in Lab-Exercise-1 in that the paths collected need to be feasible in terms of context sensitivity (calls and returns ICFGNodes must match on each program path). The implementation of solveWorklist also differs from the one in Lab-Exercise-1 by following an additional field-sensitive rule, which distinguishes fields of each struct but is array-insensitive (treating all elements of an array as one object). Please refer to this API to obtain a field object (getGepObjVar) given a struct object and a field index. The constraint solving stops until a fixed point is reached (i.e., no new COPY edges are added and the points-to sets are unchanged). No particular order when resolving edges is needed when performing the constraint solving.
| 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) |
| q = &p->fld | q <--GEP, fld-- p | for each o ∈ pts(p) : pts(q) = pts(q) ∪ {o.fld} | for each o in p's points-to set, add o's field object o.fld into q's points-to set |
- To test your implementation (sanity checks)
Use control + ~ to open a terminal in VSCode and then type the below command line
| Your implementation | ctest command line |
|---|---|
| Your reachability analysis | ctest -R ass1-icfg -VV |
| Your points-to analysis | ctest -R ass1-pta -VV |
| Your taint analysis | ctest -R ass1-taint -VV |
| The entire Assignment-1 | ctest -R ass1 -VV |
- Debugging tips for ICFG.
Add -dump-icfg as an extra option of -icfg for your ass1 executable when debugging your reachability implementation. This will dump ICFG into a dot file to view in VSCode.
- Debugging tips for ConstraintGraph and points-to sets.
Add -print-pts as an extra option of -pta for your ass1 executable when debugging your solveWorklist implementation and you could print out the final points-to set of each node to validate your MAYALIAS and NOALIAS results. You could also use -print-constraint-graph to print out the final constraint graph (edges and nodes) or -dump-constraint-graph to dump it into a dot file to view in VSCode. Retrieve a variable's points-to set, perform union operations or print out the points-to set using these APIs
| Constraint Edge | Corresponding Color in Dot graphs (PAG and ConstraintGraph) |
|---|---|
| ADDR | Green |
| COPY | Black or (dashed arrow for interprocedural COPY edges) |
| LOAD | Red |
| STORE | Blue |
| GEP | Purple |
- Upload Assignment-1.cpp to UNSW WebCMS for your submission.
Your implementation will be evaluated against our 10 internal tests. You will get the full marks if your code can pass them all. Our internal tests are private. Here, we only provided a handful test cases under Assignment-1/Tests/testcases. You are encouraged to add more test cases by yourself to validate the correctness of your implementation.
- You will be working on Assignment-1.cpp only and there is NO need to modify other files under the Assignment-1 folder
3. Configuration && debugging
3.1 launch.json
To enable debugging and running, switch your executable by setting the program and args fields as described here or follow the below screenshot.
3.2 Debug your code
From Configure-IDE, we know how to set breakpoint, debug and watch the variables.
If we want to check more complicated data structures like ICFG, ConstraintGraph and Point-to Sets. Please read the following instructions.
Debugging for ICFG
As per debugging-tips-for-icfg
Debugging for ConstraintGraph and points-to-sets
As per debugging-tips-for-constraintgraph-and-points-to-sets
