If you haven’t already, install the Slicing Toolbox plugin into Eclipse.

Smart View Interactions

The Slicing Toolbox provides Atlas Smart Views for creating and viewing slice results. First, navigate to Atlas > Open Smart View. In the Smart View selection window select either the Control Dependence Slice or Data Dependence Slice, or Program Dependence Slice.

In the source editor, select a program statement and the Smart View will automatically update with the resulting CDG, DDG, or PDG slice. The nearest source statement will be used as the slicing criteria.

Optionally, multiple slicing criteria can be selected by pressing the Shift key and selecting each slicing criterion. For CDG slices one or more Control Flow nodes must be selected as the slicing criteria. For DDG and PDG slices one or more Data Flow nodes must be selected as the slicing criteria.

Dependence Graph Factory

The Slicing Toolbox can be integrated into other client analyses. The easiest way to create a dependence graph is to use the DependenceGraph.Factory class. Let’s use the factory to create dependence graphs and some of the intermediate computations for the simple program example shown below.

The factory creates an intra-procedural dependence graph for a given method.

GraphElement method = ...

First we create the Control Dependence Graph (CDG).

ControlDependenceGraph cdg = DependenceGraph.Factory.buildCDG(method);

The CDG is constructed using the Ferrante, Ottenstein, and Warren (FOW) algorithm, which augments the Control Flow Graph (CFG) with a master entry and exit node. An “augmentation” node is added with an edge to both the master entry and exit nodes.

show(cdg.getAugmentedControlFlowGraph())

Using the augmented CFG a forward dominance analysis (post-dominance) is performed.

show(cdg.getForwardDominanceTree())

show(cdg.getGraph())

For each edge (X -> Y) in augmented CFG, we find the nodes in the forward dominance tree from Y to the least common ancestor (LCA) of X and Y. We include LCA if LCA is X and exclude LCA if LCA is not X. For the resulting set of nodes, we add a control dependence edge from X to the node.

DataDependenceGraph ddg = DependenceGraph.Factory.buildDDG(method);

The DDG is computed by adding data dependence edges to statements that contain data flow nodes with a data flow dependence. Atlas provides the defintion-use chain by leveraging a static single assignment form.

show(ddg.getGraph())

The Program Dependence Graph (PDG) is created by combining the Control Dependence Graph and Data Dependence Graph (CDG union DDG).

ProgramDependenceGraph pdg = DependenceGraph.Factory.buildPDG(method);
show(pdg.getGraph())

Impact Analysis

While a reverse program slice shows what was relevant to compute the values of the selected data flow nodes (slicing criteria), a forward program slice shows what would be impacted if a data flow node value is changed.

Taint Analysis (Program Chopping)

By intersecting the forward program slice with respect to one criteria (source) and the reverse program slice with respect to another criteria (sink) we can determine if one variable taints another in the program. A taint analysis could be used to address the implicit data flow example shown below.