RE: resolveConcreteDispatch() and resolveAbstractDispatch()

["Stephen Cheng" <stephen.cheng@btinternet.com>]

> > My question is: if the superclass c implements a method of
> signature with a
> > private attribute, doesn't this algorithm returns a false positive? It
> > should throw a run-time exception but doesn't appear to do so.
>
> Giving the private method as a possible target should be safe, because
> it is may-call (rather than must-call) information that we are
> reporting. Certainly we could remove the private methods to improve
> precision, but then we would have to check whether the call site is in
> the same class as the target.
I believe additional constraints must be placed on resolveXxxDispatch() for
the result to be useful. I will leave this discussion till later in this
post.

> A concern would be that a private method could mask a public method
> declared in a superclass. This is definitely disallowed in the Java
> language, but if I make it happen anyway in bytecode, you are correct
> that the JVM skips over the private method and finds the public one.
> However, I don't see the VM spec specify this anywhere. Also, I can't
> imagine even a non-Java compiler ever producing such bytecode.
The behaviour is actually defined in the JVM Specification section on
InvokeVirtual. The possible permutations of method overshadowing and the
resultant behaviour are really mind-boggling. However even though that the
classes file cannot be generated by the JavaC they are still legal. The
class files pass the verifier and therefore must be correctly processed by
Soot, if Soot aspires to be the compiler-independent experimental platform.

> My question: how are you getting code with a private method overriding a
> public one?
I am experimenting with the Java access control mechanism by modifying class
files.

> Summary: This situation cannot happen with code produced by javac. The
> VM spec does not specify how it should be handled. Soot's assumptions
> are different than those of the VM. Fixing it is slightly messy (when
> you consider both private and package access).
Java VM spec does define how it should be handled, and so we should make
sure Soot complies to the specification. I checked JDK 1.4.0 JVM - it
definitely complies with JVM Spec 2nd edition on the behaviour of
InvokeVirtual and InvokeInterface, and InvokeSpecial.

> An alternative solution would be to have Soot continue up the hierarchy
> whenever it finds a non-public target to make sure that it is not hiding
> a public target. If it is, then Soot would give an error saying that
> this ambiguous situation has been encountered.
The basic problem of the current implementation of resolveXxxDispatch() is
that it totally ignores the access control visibility. The solution should
be to correctly model the behaviour defined in the JVM spec by adding
visibility checks in resolveXxxDispatch().


I understand that resolveXxxDispatch() is embodying a may-call analysis.
However additional constraints must be placed on resolveXxxDispatch() for
them to have any value. IMO if resolveXxxDispatch returns() one or more
methods, in run-time the method call must be resolved into one of these
returned methods. The method call should never be resolved in run-time into
a method not in the result set, or fails to resolve at all.

If there is a chance that the method call would fail to resolve to a
concrete method in run-time, resolveXxxDispatch() must return a result as
such, to stop dependent analysis wrongly relying on the result.

I will give you an example to show why there must be this additional
constraint:

Lets consider the following scenario:
resolveConcreteDispatch() return a single false-positive, when it should
have thrown an exception signalling there is no concrete dispatch.

SiteMethodBinder or SiteInliner looks at the result of
resolveConcreteDispatch() and decides to directly bound to the returned
false-positive (hey there is only one in the result set). As a result the
program semantics has been corrupted by the incorrect implementation of
resolveConcreteDispatch().

The original program would have a different semantics: it would have thrown
a link-time or run-time exception (I believe this would be VM dependent).

I agree that this particular example is a bit theoretical, as you had
pointed out, javac could not have produced such a set of class files.
However as I understood Soot is aiming to be the experimental platform for
any java byte code, including those produced by non-java compilers and code
generators. In any case, I can construct an equivalent practical example
using package private methods.


I am halfway through a first pass analysis of the VTA and CHA implementation
and here is my list of observations. As I am still relatively new to Soot no
doubt some of these comments are biased by my expectations ;-) so please
correct me:

1.	resolveSpecialDispatch() codes the wrong logic.
resolveSpecialDispatch() should resolve to a superclass method (according to
the JVM spec) if:
- The ACC_SUPER flag is set for teh current class (Soot assumes that the
ACC_FLAG is on always)
- The class of resolved method is a superclass of the current class
- The resolved method is not an initialisation method

In its current implementation, resolveSpecialDispatch() would quite happily
resolve to a method in the class itself under this set of circumstances. No
analysis is relying on resolveSpecialDispatch() at the moment.

See JVM Specification on InvokeSpecial for more information.

2.	resolveAbstractDispatch() trips up on abstract classes implementing an
interface. When resolveAbstractDispatch() is called to resolve a method of
an interface, it collects the set of classes implementing the interface,
including those classes that are abstract. It will then call
resolveConcreteDispatch() on every single of these classes. However
resolveConcreteDispatch() fails on partially implemented abstract classes
and it will throw an exception if the method in question is not actually
implemented. This bug trips up whole-program optimisation on JDK 1.4.0
rt.jar.

3.	resolveConcreteDispatch() may return false-positive on private methods.
Lets say Class A implements private method doSomething(). Class B extends
Class A. A resolveConcreteDispatch() on class B and method B.doSomething()
would incorrectly return A.doSomething() - a private method that could never
be reached. This can lead to incorrect optimised code produced by WPO under
theoretical circumstances. See previous sections.

4.	resolveConcreteDispatch() may return wrong result (not just false
positive) on package private (default) methods. Consider the following
scenario:

class Package1.ClassA {
 void  doSomething(){};
}

class Package2.Class B extends Package1.ClassA {
 void  doSomething(){};
}

Now if we have a code fragment like
Package1.ClassA instance = new Package2.ClassB();
instance.doSomething();

In run-time (in according to JVM spec) Sun 1.4.0 JVM resolves method call to
ClassA.doSomething(). The current implementation of
resolveConcreteDispatch() would return ClassB.doSomething(). This is because
it ignores package visibility and just work on package signature (without
considering access control attributes).

This can lead to incorrect optimised code produced by WPO under practical
circumstances.

5.	VTA relies on VTANativeAdjuster. VTANativeAdjuster appears to code
additional method call relationships between a native method caller and a
callee method. IMO this as an unsound design since VTANativeAdjuster is
highly dependent on a particular implementation of the java library.

6.	VTA analysis relies on the reachability analysis (see MethodCallGraph) to
calculate the reaching types. However I do not believe reachability analysis
is producing the full set of reachable methods under every circumstances, as
it is using a fixed set of entry methods (see MethodCallGraph.initialise()).
It is for example not catering for J2ME CLDC entry methods, or J2SE
serialisation entry methods. This will in turn affect dependent optimisation
such as SiteInliner and SiteMethodBinder. IMO this is an unsound design as
it makes (likely incorrect) assumptions about the Java application being
optimised. In fact until the set of entry methods is exposed to the
command-line, we cannot do VTA based analysis/optimisations on J2ME, RTJ,
and any J2SE applications that employs serialisation/RMI.

I think we need to do quite a lot of work before whole program optimisation
reaches production quality. I hope this post helps getting us there. I like
the basic architecture of Soot, and I thank you Sable people for a work well
done.

Regards,
Stephen Cheng