ES-SDG traversal limitations interfere with PPDG traversal limitations

The traversal of the PPDG and the traversal of the ES-SDG conflict, specifically the following rules:

• PPDG: do not traverse control dependence arcs whose target is a pseudo-predicate that is not the slicing criterion.
• ES-SDG: do not traverse any arcs whose target has only been included in the slice via conditional control dependency.

The PPDG works by making some transitive dependencies direct, and then restricting the transitivity of some nodes (w.r.t. control dependency, data dependency is unaffected). This feature is stopped by the restriction placed by the ES-SDG, as it limits traversal on pseudo-predicate nodes. The result are cases like the following control dependencies:

graph LR
 id1["Enter f()"]
 id1 --> catch --CC1--> SC

Where the catch node is included in the slice via unconditional control dependencies. The Enter node will not be included. Due to the ES-SDG restriction, the starting element is not reached.

A possible solution, which has been implemented is the following:

1. Obtain the set of unconditional control dependency arcs of a given PPDG: CD_{PPDG}.
2. Create and build an APDG with the same ACFG as its basis, then obtain its set of control dependency arcs: CD_{APDG}.
3. For each arc in the set difference CD_{PPDG} \setminus CD_{APDG}, mark it as "PPDG exclusive".
4. When slicing, modify the aforementioned ES-SDG rule to: do not traverse arcs whose target has only been included in the slice via conditional control dependency; unless the arc is an unconditional control dependency and exclusive to the PPDG.

Example

Program Carlos2.java from the tests at dinsa, line 14; the graph produced is shown below. The try and method enter is not reached.

graph-ESSDG.pdf

A simpler example can be obtained with version 807845d9, and the following program:

class A {
	public static void main(String[] args) {
		try {
			throw new RuntimeException();
		} catch (IllegalArgumentException e) {}
		int SC = 42;
	}
}