Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
# TFM
- [TFM](#tfm)
- [Introduction](#introduction)
- [Quick start](#quick-start)
- [Build a graph](#build-a-graph)
- [Slice a program](#slice-a-program)
- [Structure](#structure)
- [Summary](#summary)
- [Current state](#current-state)
- [Graphs](#graphs)
- [Statements covered](#statements-covered)
- [To do list](#to-do-list)
- [SDG](#sdg)
- [General](#general)
- [Code samples](#code-samples)
- [Build a CFG from a program](#build-a-cfg-from-a-program)
- [Get a slice of the PDG of a program](#get-a-slice-of-the-pdg-of-a-program)
- [Workflow](#workflow)
## Introduction
The main goal of this work is to develop a Java slicer. This is done by building a System Dependence Graph of the program being sliced
## Quick start
### Build a graph
Find `Main` class (`tfm/exec`), modify static fields of the class (the program being analyzed, the graph to build, etc.) and execute it. You will find the output in `tfm/out` as a png image
### Slice a program
Find `Slice` class (`tfm/slicing`), set the program path and execute. The sliced program will be in `tfm/out`
## Structure
Graphs are built using a library called `graphlib`, located in `lib/graphlib.jar`. This library is old and has some issues I had to fix...
The main class is the `Graph` class, which extends from `graphlib`'s `Graph` class. This class includes some behaviour fixes, and some general interest methods (like `toString`, `toGraphvizRepresentation`, etc.)
Every graph has a set of nodes and arrows. `GraphNode` and `Arc` classes are used to represent them respectively.
A set of visitors is implemented for many things, such as graph building, data dependence building, etc... (available in `tfm/visitors`)
A bunch of programs are written in `tfm/programs`, you can write more there.
Some naive testing is implemented in the `tfm/validation` folder. Currently, a PDG can be compared with a program to check their equality.
Some util methods are available in `tfm/utils` (such as AST utils, logger, etc.)
Forget about the `tfm/scopes` folder, it was an idea I had to discard and it has to be deleted.
### Summary
- Graphs (`tfm/graphs`)
- CFGGraph
- PDGGraph
- SDGGraph
- Nodes (`tfm/nodes`)
- ~~CFGNode, PDGNode, SDGNode~~ (_Deprecated_)
- GraphNode
- MethodCallNode (_idk if this is necessary, maybe it can be deleted_)
- Arcs (`tfm/arcs`)
- ControlFlowArc
- DataDependencyArc
- ControlDependencyArc
- Visitors (`tfm/visitors`)
- CFGBuilder
- ~~PDGVisitor~~ (_Deprecated, it was an intent to build a PDG with no CFG needed_)
- PDGBuilder
- ControlDependencyBuilder
- DataDependencyBuilder
- SDGBuilder (_Probably deprecated_)
- NewSDGBuilder -**Work in progress**-
- MethodCallReplacerVisitor (_Replaces method call nodes with in and out variable nodes_) -**Work in progress**-
## Current state
### Graphs
- CFG: Done!
- PDG: Done!
- SDG: PDGs are built for each method
### Statements covered
- Expressions (ExpressionStmt)
- If (IfStmt)
- While, DoWhile (WhileStmt, DoStmt)
- For, Foreach (ForStmt, ForeachStmt)
- Switch (SwitchStmt, SwitchEntryStmt)
- Break (BreakStmt)
- Continue (ContinueStmt)
## To do list
### SDG
- Replace method call nodes with in and out variables nodes and build arrows for them
- Build summary arrows
### General
- Switch to a (much) better graph library like [JGraphT](https://jgrapht.org/). It also supports graph visualization
- Performance review
- Make a test suite (test graph building, slicing, etc.)
- Add support to more Java language features (lambdas, etc.)
## Code samples
### Build a CFG from a program
```java
public CFGGraph buildCFG(File programFile) {
JavaParser.getStaticConfiguration().setAttributeComments(false); // Always disable comments, just in case
Node astRoot = JavaParser.parse(programFile);
return Graphs.CFG.fromASTNode(astRoot); // Creates a new graph representing the program
}
```
### Get a slice of the PDG of a program
```java
public PDGGraph getSlice(File program, SlicingCriterion slicingCriterion) {
JavaParser.getStaticConfiguration().setAttributeComments(false); // Always disable comments, just in case
Node astRoot = JavaParser.parse(programFile);
PDGGraph pdgGraph = Graphs.PDG.fromASTNode(astRoot);
return pdgGraph.slice(slicingCriterion);
}
```
## Workflow
- Branches:
- `master` (only for stable versions)
- `develop` (main branch)
- `<issue number>`
1. Discover a new feature/fix
2. Open an issue describing it and assign it
4. Create a new branch from `develop` with the same name as the issue number (e.g. for issue #12 the new branch is called `12`)
5. Write the solution to the issue
6. Once resolved, open a pull request from the issue branch to `develop` branch
7. Finally, when pull request is merged, remove branch