Introduction to insertOnEdge in Soot
Table Of Contents
Summary
insertOnEdge
adds instrumentation(s) to the Chain in a manner such that the resulting CFG of the program will contain toInsert
on an edge that is defined by point_source
and point_target
.
Class patchingChain <E extends Unit>
</a>
public void insertOnEdge(E toInsert, E point_src, E point_tgt)
public void insertOnEdge(List<E> toInsert, E point_src, E point_tgt)
public void insertOnEdge(Chain<E> toInsert, E point_src, E point_tgt)
Specified by
insertOnEdge
in interface Chain<E extends Unit>
Parameters
toInsert
- the instrumentation to be added in the Chainpoint_src
- the source point of an edge in CFGpoint_tgt
- the target point of an edge in CFG
Introduction
The insertOnEdge
API correctly adds instructions (toInsert
) to the target program (Body
) on an edge. In a Control Flow Graph, such a directed edge would be represented by a source point (point_src
) and a target unit (point_tgt
).
Without this API, instrumenting certain edges can prove difficult and time consuming to the user.
Consider the following if condition:
if (x!=40) { //unit1
x=40; //unit2
}
x = x + 2; //unit3
The control flow graph for the above code is as follows:
Assume that the user wishes to instrument all three edges with a statement toInsert
.
-
Edge 1: Can be instrumented using
body.getUnits().insertAfter(toInsert, Unit1)
-
Edge 2: Can be instrumented using
body.getUnits().insertBeforeNoRedirect(toInsert, Unit3)
-
Edge 3: ????
None of the APIs previously available enables a user to easily instrument only the false branch (Edge 3). Neither insertBefore unit3
nor insertAfter unit1
will work. Using insertBefore unit3
will cause the instrumentation to be executed no matter which branch the program takes.
This is where insertOnEdge comes in. The 3rd edge can be instrumented by simply using body.getUnits().insertOnEdge(toInsert, Unit1, Unit3);
In fact, insertOnEdge can be used on all three edges. This further reduces the user’s work.
body.getUnits().insertOnEdge(toInsert, Unit1, Unit2);
body.getUnits().insertOnEdge(toInsert, Unit2, Unit3);
body.getUnits().insertOnEdge(toInsert, Unit1, Unit3);
Usage
-
insertOnEdge(toInsert, null, target)
Doing this is same as performinginsertBefore(toInsert, target)
. All jumps totarget
is redirected totoInsert
-
insertOnEdge(toInsert, source, null)
Doing this is same as performinginsertAfter(toInsert, source)
-
insertOnEdge(toInsert, source, target)
This adds an instrumentation in a manner such that the resulting CFG of the program will containtoInsert
on an edge that is defined bysource
andtarget
.
insertOnEdge
will throw RuntimeException if such an edge does not exist in the program’s CFG. -
insertOnEdge(toInsert, null, null)
Just don’t do this.insertOnEdge
will throw a RuntimeException.
Code
You could read the following code to go into the nitty-gritties of insertOnEdge. (View code on GitHub):
/** | |
* Inserts instrumentation in a manner such that the resulting control flow | |
* graph (CFG) of the program will contain <code>toInsert</code> on an edge | |
* that is defined by <code>point_source</code> and <code>point_target</code>. | |
* | |
* @param toInsert the instrumentation to be added in the Chain | |
* @param point_src the source point of an edge in CFG | |
* @param point_tgt the target point of an edge | |
*/ | |
public void insertOnEdge(E toInsert, E point_src, E point_tgt) { | |
if (toInsert == null) | |
throw new RuntimeException("Bad idea! You tried to insert " + "a null object into a Chain!"); | |
if (map.containsKey(toInsert)) | |
throw new RuntimeException("Chain already contains object."); | |
// Insert 'toInsert' before 'target' point in chain if the source point is null | |
if (point_src == null && point_tgt != null) { | |
((Unit) point_tgt).redirectJumpsToThisTo((Unit) toInsert); | |
insertBefore(toInsert, point_tgt); | |
return; | |
} | |
// Insert 'toInsert' after 'source' point in chain if the target point is null | |
if (point_src != null && point_tgt == null) { | |
insertAfter(toInsert, point_src); | |
return; | |
} | |
// Throw an exception if both source and target is null | |
if (point_src == null && point_tgt == null) { | |
throw new RuntimeException("insertOnEdge failed! Both source and target points are null"); | |
} | |
// If target is right after the source in the Chain | |
// 1- Redirect all jumps (if any) from 'source' to 'target', to 'toInsert' | |
// (source->target) ==> (source->toInsert) | |
// 2- Insert 'toInsert' after 'source' in Chain | |
if (getSuccOf(point_src) == point_tgt) { | |
List<UnitBox> boxes = ((Unit) point_src).getUnitBoxes(); | |
for (UnitBox box : boxes) { | |
if (box.getUnit() == point_tgt) { | |
box.setUnit((Unit) toInsert); | |
} | |
} | |
insertAfter(toInsert, point_src); | |
return; | |
} | |
// If the target is not right after the source in chain then, | |
// 1- Redirect all jumps (if any) from 'source' to 'target', to 'toInsert' | |
// (source->target) ==> (source->toInsert) | |
// 1.1- if there are no jumps from source to target, then such an edge does not exist. Throw an exception. | |
// 2- Insert 'toInsert' before 'target' in Chain | |
// 3- If required, add a 'goto target' statement so that no other edge executes 'toInsert' | |
boolean validEdgeFound = false; | |
E originalPred = getPredOf(point_tgt); | |
List<UnitBox> boxes = ((Unit) point_src).getUnitBoxes(); | |
for (UnitBox box : boxes) { | |
if (box.getUnit() == point_tgt) { | |
if (point_src instanceof GotoStmt) { | |
box.setUnit((Unit) toInsert); | |
insertAfter(toInsert, point_src); | |
E goto_unit = (E) new JGotoStmt((Unit) point_tgt); | |
insertAfter(goto_unit, toInsert); | |
return; | |
} | |
box.setUnit((Unit) toInsert); | |
validEdgeFound = true; | |
} | |
} | |
if (validEdgeFound) { | |
insertBefore(toInsert, point_tgt); | |
if (originalPred != point_src) { | |
if (originalPred instanceof GotoStmt) | |
return; | |
E goto_unit = (E) new JGotoStmt((Unit) point_tgt); | |
insertBefore(goto_unit, (E) toInsert); | |
} | |
return; | |
} | |
// In certain scenarios, the above code can add extra 'goto' units on a different edge | |
// So, an edge [src --> tgt] becomes [src -> goto tgt -> tgt]. | |
// When this happens, the original edge [src -> tgt] ceases to exist. | |
// The following code handles such scenarios. | |
if (getSuccOf(point_src) instanceof GotoStmt) { | |
if (((Unit) getSuccOf(point_src)).getUnitBoxes().get(0).getUnit() == point_tgt) { | |
((Unit) getSuccOf(point_src)).redirectJumpsToThisTo((Unit) toInsert); | |
insertBefore(toInsert, getSuccOf(point_src)); | |
return; | |
} | |
} | |
// If the control reaches this point, it means that an edge [stc -> tgt] as specified by user does not exist and is thus invalid | |
// Return an exception. | |
throw new RuntimeException( | |
"insertOnEdge failed! No such edge found. The edge on which you want to insert an instrumentation is invalid."); | |
} |
Future Work
- At the time of writing, this work is tested and known to work on Jimple code. Shimple intermediate representation is not supported.
- Exception edges cannot be instrumented using this method.
PS: The insertOnEdge feature was added to the Soot repository with this pull request: Feature/insert on edge #583
Have any suggestions or questions that you want answered? Feel free to contact me or use the comment section below.