[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Tightening Exception-based Control flow graph
Laurie Hendren wrote:
Could you please give us a concrete example of what you are doing
and why you are doing it. John Jorgensen was working on
improving our exception edges in Soot and we would like to see how
(or if) that relates to his work.
I am dealing with Control flow graphs of Java programs for programming analyses such as object flow analysis and
transformations such as program slicing. In the due course I have found the exception edges in Jimple lacking in precision
and previous solution addresses an issue to improve precision of exception information captured in Jimple.
Consider the following class, it's byte code, and modified jimple representation. The language semantics requires that the
monitor statements complete before return on exceptional edges. This is ensure by the compiler while compiling the language
to bytecodes and the compiled bytecode does a pretty good job taking into consideration the execution rules associated with an
exception table. "If a region is covered by two exception handler, then the one encountered first in the exception table will
handle the exception." So region 27-40 in the byte code will be "handled" at 49. However, everything in region 22-27 and
40-42 will be "handled" at 62. However, this is not the case in Jimple. The region 27-40 is indicated as being trapped by 49
and 62 which is incorrect. Tt is an overapproximation which is harmless at the level of CFG. However, for an analysis that
tries to detect the monitors in a program this flaw makes calculation unnecessarily complicated. To some extent this is also
compounded by the fact that Soot does not differentiate between exceptional and non-exceptional edges. Nevertheless, all this
complication will cease if the CFG is constructed such that it mirrors the dynamic control flow and not the static control
flow in the program. The way to do this is by trying to realize the execution rules of the JVM.
On the same note, I wanted to know if soot was extended in a considerable way, would Sable group be willing to accept the
changes and merge it into their main branch providing the contributor write access to the repository? Or would the
contributor have to maintain a separate branch of Soot from there on? The reason for this question is that Soot is a
singleton instance-based solution at this point. However, it would be more suitable for it to not be so in the light of
destructive program transformations. As I am working on one such transformation I am evaluating if I should expend effort on
modifying Soot to fulfill my needs.
waiting for reply,
- Venkatesh
---- CODE ----
public class Sync03 {
public static void main(String[] S) {
Object o = new Object();
int i = 0;
synchronized(o) {
synchronized(p) {
if (i == 0) {
return;
}
}
}
}
}
public static void main(java.lang.String[]);
Code:
0: new #2; //class Object
3: dup
4: invokespecial #1; //Method java/lang/Object."<init>":()V
7: astore_1
8: new #3; //class String
11: dup
12: ldc #4; //String
14: invokespecial #5; //Method java/lang/String."<init>":(Ljava/lang/String;)V
17: astore_2
18: aload_1
19: dup
20: astore_3
21: monitorenter
22: aload_2
23: dup
24: astore 4
26: monitorenter
27: ldc #6; //String as
29: ldc #7; //String sa
31: invokevirtual #8; //Method java/lang/String.equals:(Ljava/lang/Object;)Z
34: ifeq 43
37: aload 4
39: monitorexit
40: aload_3
41: monitorexit
42: return
43: aload 4
45: monitorexit
46: goto 57
49: astore 5
51: aload 4
53: monitorexit
54: aload 5
56: athrow
57: aload_3
58: monitorexit
59: goto 69
62: astore 6
64: aload_3
65: monitorexit
66: aload 6
68: athrow
69: return
Exception table:
from to target type
27 40 49 any
43 46 49 any
49 54 49 any
22 42 62 any
43 59 62 any
62 66 62 any
}
public static void main(java.lang.String[])
{
java.lang.String[] r0;
java.lang.Object $r1, r2, r4;
java.lang.String r3, r5, $r8, $r11;
java.lang.Throwable r6, r7, $r12, $r13;
boolean $z0;
r0 := @parameter0: java.lang.String[];
$r1 = new java.lang.Object;
specialinvoke $r1.<java.lang.Object: void <init>()>();
r2 = $r1;
$r8 = new java.lang.String;
specialinvoke $r8.<java.lang.String: void <init>(java.lang.String)>("");
r3 = $r8;
r4 = r2;
entermonitor r2;
label0:
r5 = r3;
entermonitor r3;
label1:
$r11 = "as";
$z0 = virtualinvoke $r11.<java.lang.String: boolean equals(java.lang.Object)>("sa");
if $z0 == 0 goto label4;
exitmonitor r5;
label2:
exitmonitor r4;
label3:
return;
label4:
exitmonitor r5;
label5:
goto label9;
label6:
$r12 := @caughtexception;
label7:
r6 = $r12;
exitmonitor r5;
label8:
throw r6;
label9:
exitmonitor r4;
label10:
goto label14;
label11:
$r13 := @caughtexception;
label12:
r7 = $r13;
exitmonitor r4;
label13:
throw r7;
label14:
return;
catch java.lang.Throwable from label1 to label2 with label6;
catch java.lang.Throwable from label4 to label5 with label6;
catch java.lang.Throwable from label7 to label8 with label6;
catch java.lang.Throwable from label0 to label1 with label11;
catch java.lang.Throwable from label2 to label3 with label11;
catch java.lang.Throwable from label5 to label7 with label11;
catch java.lang.Throwable from label8 to label10 with label11;
catch java.lang.Throwable from label12 to label13 with label11;
}
Thanks, Laurie
+----------------------------------------------------------------+
| Laurie Hendren, Professor, Computer Science, McGill University |
| Visiting Fellow, Oxford University Computing Laboratory, |
| Wolfson Building, Parks Road tel: +44 1865 283551 (abroad) |
| Oxford, UK OX1 3QD 01865 283551 (inside UK) |
| hendren@cs.mcgill.ca http://www.sable.mcgill.ca/~hendren |
+----------------------------------------------------------------+
On Fri, 12 Sep 2003, Venkatesh Prasad Ranganath wrote:
Hi,
While using locking constructs the compiler creates over-approximate exceptions regions to ensure safe release of locks. This
injects incorrect control flow into the Jimple graphs that consider exceptions. The following code will ensure that the
control flow via exceptions in Jimple graphs closely mimics the dynamic control flow in the method.
The method can be added to JimpleMethodSource and called in JimpleMethodSource.getBody() to fix the body after it has been
constructed from the class file rather than each application trying to massage the body upon retrieval.
void processBody(body) {
Jimple jimple = Jimple.v();
Chain traps = body.getTraps();
Chain units = body.getUnits();
List t = new ArrayList(traps);
for(int i = 0; i < t.size(); i++) {
Trap enclosedTrap = (Trap)t.get(i);
SootClass exception = enclosedTrap.getException();
Stmt enclosedBeginStmt = (Stmt)enclosedTrap.getBeginUnit();
Stmt enclosedEndStmt = (Stmt)enclosedTrap.getEndUnit();
Stmt enclosedHandlerStmt = (Stmt)enclosedTrap.getHandlerUnit();
for(int j = 0; j < t.size(); j++) {
Trap enclosingTrap = (Trap)t.get(j);
Stmt enclosingBeginStmt = (Stmt)enclosingTrap.getBeginUnit();
Stmt enclosingEndStmt = (Stmt)enclosingTrap.getEndUnit();
if (enclosedTrap != enclosingTrap && exception.equals(enclosingTrap.getException())) {
if (enclosedBeginStmt == enclosingBeginStmt
&& units.follows(enclosingEndStmt, enclosedEndStmt)
&& units.follows(enclosedEndStmt, enclosingBeginStmt)
) {
enclosingTrap.setBeginUnit(enclosedEndStmt);
} else if (enclosedEndStmt == enclosingEndStmt
&& units.follows(enclosedBeginStmt, enclosingBeginStmt)
&& units.follows(enclosingEndStmt, enclosedBeginStmt)) {
enclosingTrap.setEndUnit(enclosedBeginStmt);
} else if (units.follows(enclosedBeginStmt, enclosingBeginStmt)
&& units.follows(enclosingEndStmt, enclosedBeginStmt)
&& units.follows(enclosingEndStmt, enclosedEndStmt)
&& units.follows(enclosedEndStmt, enclosingBeginStmt)) {
enclosingTrap.setEndUnit(enclosedBeginStmt);
Trap newTrap = jimple.newTrap(enclosingTrap.getException(), enclosedEndStmt, enclosingEndStmt,
enclosingTrap.getHandlerUnit());
traps.insertAfter(newTrap, enclosingTrap);
t.add(j + 1, newTrap);
}
}
}
}
}
--
Venkatesh Prasad Ranganath,
Dept. Computing and Information Science,
Kansas State University, US.
web: http://www.cis.ksu.edu/~rvprasad