[Soot-list] Instrumenting exceptional edges in CFG

[Nate Deisinger]

Hi folks,

I've been working with Soot the past few months to get a Java 
implementation of the Ball-Larus path profiling algorithm up and 
running.  Without going into too much detail, the algorithm requires 
placing increments to a path counter along certain edges in the 
program's CFG.  While I'm most of the way there, I'm running into 
trouble handling exceptional control flow.

In my model, every basic block of the program that is in a try block is 
considered to have an edge to the blocks which potentially catch it.  
(Per the way Jimple handles exceptions, this also implies catch blocks 
have edges to finally blocks.)  Under Ball-Larus, it's very common to 
need to increment our path on one of these edges to a catch/finally block.

My original idea was to redirect the traps to a new block of code which 
increments the path counter appropriately and then jumps to the original 
catch block.  The Jimple for such code looks like this:

------------------------------------

[...]

      label1:
         nop;
         e := @caughtexception;
         temp$4 = <java.lang.System: java.io.PrintStream out>;
         virtualinvoke temp$4.<java.io.PrintStream: void 
println(java.lang.String)>("ArrayIndexOutOfBoundsException!");
         nop;
         goto label3;

[...]

      label5:
         nop;
         _____BL_temporary_long = basicTry__PT_holder.<PathTrace: long 
recentPath>;
         _____BL_temporary_long = _____BL_temporary_long + 1L;
         basicTry__PT_holder.<PathTrace: long recentPath> = 
_____BL_temporary_long;
         goto label1;

[...]

catch java.lang.ArrayIndexOutOfBoundsException from label0 to label1 
with label5;

------------------------------------

Where originally it would be "catch 
java.lang.ArrayIndexOutOfBoundsException from label0 to label1 with 
label1", and label5's code would not exist.

Unfortunately, doing so causes bytecode generation to fail, as negative 
stack height is attained while generating Jasmin:

------------------------------------
Caused by: java.lang.RuntimeException: Negative Stack height has been 
attained in :<SuperSimpleTry: void basicTry(java.lang.String[])>
StackHeight: -1
At instruction:store.r e
Block:
Block 1:
[preds: 4 ] [succs: 2 ]
nop;
store.r e;
staticget <java.lang.System: java.io.PrintStream out>;
store.r temp$4;
load.r temp$4;
push "ArrayIndexOutOfBoundsException!";
virtualinvoke <java.io.PrintStream: void println(java.lang.String)>;
nop;
goto nop;


Method: basicTry
<SuperSimpleTry: void basicTry(java.lang.String[])>
     at soot.baf.JasminClass.calculateStackHeight(JasminClass.java:1887)
     at soot.baf.JasminClass.calculateStackHeight(JasminClass.java:1915)
     at soot.baf.JasminClass.calculateStackHeight(JasminClass.java:1915)
     at soot.baf.JasminClass.emitMethodBody(JasminClass.java:322)
     at soot.AbstractJasminClass.emitMethod(AbstractJasminClass.java:697)
     at soot.AbstractJasminClass.<init>(AbstractJasminClass.java:576)
     at soot.baf.JasminClass.<init>(JasminClass.java:92)
     at soot.PackManager.writeClass(PackManager.java:878)
     at soot.PackManager.writeOutput(PackManager.java:475)
     at soot.PackManager.writeOutput(PackManager.java:400)
     at soot.Main.run(Main.java:199)
     at soot.Main.main(Main.java:141)
     at MyMain.main(MyMain.java:79)
------------------------------------

My guess is that jumps remove exceptions from the stack for whatever 
reason, causing the later store to e to fail, but that's just a guess.

Does anyone have any suggestions for getting around this issue? 
Unfortunately, I can't add the instrument code to the beginning of the 
catch block, as multiple paths may lead to the same catch block (and 
thus have different instrumentation values).

I'm aware one option would be to make a copy of each catch block for 
each instrumentation value, but I'd prefer not to do that (it would be 
messy keeping the CFG straight, and significantly bloat the classfile).

Thanks very much,
Nate