Introduction to insertOnEdge in Soot -- Arpith K

Summary
- Specified by
- Parameters
Introduction
Usage
Code
Future Work

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.

This API available in Soot’s

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 Chain
point_src - the source point of an edge in CFG
point_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 performing insertBefore(toInsert, target). All jumps to target is redirected to toInsert
insertOnEdge(toInsert, source, null)
Doing this is same as performing insertAfter(toInsert, source)
insertOnEdge(toInsert, source, target)
This adds an instrumentation in a manner such that the resulting CFG of the program will contain toInsert on an edge that is defined by source and target.
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.

Introduction to insertOnEdge in Soot

Table Of Contents