RE: resolveConcreteDispatch() and resolveAbstractDispatch()

["Prof. Laurie HENDREN" <hendren@cs.mcgill.ca>]

Hi Stephen,

Would you like to contribute a fixed version, along with a description
of your decisions?

Of course, the NativeAdjuster design is not ideal.    However, it is fairly
tricky to come up with something more portable,  and whenever new native methods
are added, someone has to figure out their impact and somehow convey
this information to VTA or other analyses that need to know what fields
might be written and what objects might be returned.   It was already
quite painful to build the one version of the NativeAdjuster.

As all members working on Soot are students who are helping to maintain
it as a service to the community using Soot,  it would be most helpful
if others help us to get it working for 1.4 and the new libraries.

Cheers, Laurie


+-------------------------------------------------------------+
| Professor Laurie Hendren, School of Computer Science        |
| McGill University                                           |
| 318 McConnell Engineering Building      tel: (514) 398-7391 |
| 3480 University Street                  fax: (514) 398-3883 |
| Montreal, Quebec H3A 2A7               hendren@cs.mcgill.ca |
| CANADA                  http://www.sable.mcgill.ca/~hendren |
+-------------------------------------------------------------+

On Fri, 26 Apr 2002, Stephen Cheng wrote:

> > > 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
>