TFM
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. 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
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
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>
-
- Discover a new feature/fix
- Open an issue describing it and assign it
- Create a new branch from
develop
with the same name as the issue number (e.g. for issue #12 the new branch is called12
) - Write the solution to the issue
- Once resolved, open a pull request from the issue branch to
develop
branch - Finally, when pull request is merged, remove branch