Stack grows infinitely due to a bug in private method dispatch of JPF on Java 11

[quadhier]

I recently encountered a strange problem that caused JPF (java-10-gradle branch) running on Java 11 to hang. I did some diagnosis work and present my analysis below.

A Description of the Problem

Recently, I used JPF to run a Java program but found that it seemed to hang. I reduced the program and traced the execution of JPF. I found that the root cause is a bug in the private method dispatch of invokevirtual implementation. Since using invokevirtual to call private method is a mechanism introduced in Java 11 (see JEP 181: Nest-Based Access Control), this bug seems to only exist in branches that supports Java 11 (I work on java-10-gradle branch).

System Information

$ git branch
* java-10-gradle
$ uname -op
x86_64 GNU/Linux
$ java -version
openjdk 11.0.18 2023-01-17
OpenJDK Runtime Environment (build 11.0.18+10-post-Ubuntu-0ubuntu122.04)
OpenJDK 64-Bit Server VM (build 11.0.18+10-post-Ubuntu-0ubuntu122.04, mixed mode, sharing)

Steps to Reproduce

1. Create a file of the path jpf-core/src/examples/PrivateMethodDispatch.java with the following content.

/*  L1 */ public class PrivateMethodDispatch {
/*  L2 */
/*  L3 */   private void foo() {
/*  L4 */     System.out.println("entered PrivateMethodDispatch::foo");
/*  L5 */     new Other().foo();
/*  L6 */   }
/*  L7 */
/*  L8 */   public static void main (String[] args) {
/*  L9 */     new PrivateMethodDispatch().foo();
/* L10 */   }
/* L11 */ }
/* L12 */
/* L13 */ class Other {
/* L14 */   public void foo() {
/* L15 */     System.out.println("entered Other::foo");
/* L16 */   }
/* L17 */ }

2. build the jpf-core project

$ ./gradlew clean buildJars

3. Run PrivateMethodDispatch

$ cd ./bin
$ ./jpf PrivateMethodDispatch

Expected Ouput

...
entered PrivateMethodDispatch::foo
entered Other::foo

====================================================== results
no errors detected

====================================================== statistics
...

Actual Output

...
entered PrivateMethodDispatch::foo
entered PrivateMethodDispatch::foo
entered PrivateMethodDispatch::foo
entered PrivateMethodDispatch::foo
entered PrivateMethodDispatch::foo
entered PrivateMethodDispatch::foo
entered PrivateMethodDispatch::foo
entered PrivateMethodDispatch::foo
entered PrivateMethodDispatch::foo
entered PrivateMethodDispatch::foo
... (infinitely print "entered PrivateMethodDispatch::foo")
...

Bug Diagnosis

The execution of bytecode invokevirtual is implemented in the execute() method of the class VirtualInvocation. The execute() method calls getInvokedMethod(ThreadInfo ti, int objRef) to resolve the callee method, just as the below code shows.

jpf-core/src/main/gov/nasa/jpf/jvm/bytecode/VirtualInvocation.java

Lines 94 to 98 in 5665054

	try {
	callee = getInvokedMethod(ti, objRef);
	} catch (ClassChangeException ccx){
	return ti.createAndThrowException("java.lang.IncompatibleClassChangeError", ccx.getMessage());
	}

In the implementation of getInvokedMethod(ThreadInfo ti, int objRef), it first decides if the callee is a private method. The code below shows how it does this.

jpf-core/src/main/gov/nasa/jpf/jvm/bytecode/VirtualInvocation.java

Lines 153 to 164 in 5665054

	public MethodInfo getInvokedMethod (ThreadInfo ti, int objRef) {
	if (objRef != MJIEnv.NULL) {
	//First check if the method to be called is private
	ClassInfo privateCi = ti.getPC().getMethodInfo().getClassInfo();
	MethodInfo privateMi = privateCi.getMethod(mname, false);
	if (privateMi != null && privateMi.isPrivate()) {
	invokedMethod = privateMi;
	lastCalleeCi = privateCi;
	return invokedMethod;
	}

The catch is that, in the line 157 above, it gets the class that declares the method that invokevirtual bytecode resides in and takes it wrongly as the class that declares the invokevirtual's callee method!

Then the magic happens, if the method that invokevirtual bytecode resides in (namely, caller method) is private AND has the same name as the callee method of this invokevirtual bytecode, this caller method (which is PrivateMethodDispatch::foo in the above example) will be returned by getInvokedMethod(ThreadInfo ti, int objRef) and be executed again. Then the buggy invokevirtual bytecode in that caller is executed again, the same thing happens forever.

Note that this only happens if the aforementioned two conditions are satisfied. Otherwise, the execution of getInvokedMethod(ThreadInfo ti, int objRef) falls through to the below execution process, which happens to be able to dispatch the private method correctly. (I'm not sure if this dispatch is totally correct as I don't check it with JVMS 11 strictly, but this implementation does work in most cases. :P)

A Tentative Fix

Dispatch the private method to the class that declares the invokevirtual's callee method instead of the class that declares the method that invokevirtual resides in.

--- a/src/main/gov/nasa/jpf/jvm/bytecode/VirtualInvocation.java
+++ b/src/main/gov/nasa/jpf/jvm/bytecode/VirtualInvocation.java
@@ -154,7 +154,7 @@ public abstract class VirtualInvocation extends InstanceInvocation {

     if (objRef != MJIEnv.NULL) {
       //First check if the method to be called is private
-      ClassInfo privateCi = ti.getPC().getMethodInfo().getClassInfo();
+      ClassInfo privateCi = ti.getClassInfo(objRef);
       MethodInfo privateMi = privateCi.getMethod(mname, false);
       if (privateMi != null && privateMi.isPrivate()) {
         invokedMethod = privateMi;

[cyrille-artho]

Thanks, please create a pull request with your new test and the fix against this issue, and I will gladly accept it.
I have tried this now on my computer, and I can reproduce the bug, and I agree with your assessment.

[quadhier]

Thanks for your review and sorry for late response.

After further investigation, I find my tentative fix has some flaws as it causes some other test cases to fail. I have figured out another fix and will create a PR ASAP.

[cyrille-artho]

Thanks! Could you please also create a PR against the master branch (on Java 8), as the unit tests on that branch all pass, so it is easier to see that the patch does not break anything else?

…

On Fri, Apr 14, 2023 at 5:43 AM Daohan Qu ***@***.***> wrote: Thanks for your review and sorry for late response. After further investigation, I find my tentative fix has some flaws as it causes some other test cases to fail. I have figured out another fix and will create a PR ASAP. — Reply to this email directly, view it on GitHub <#348 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABXV4R2ORV4HLMVDJZGIH3LXBDBXTANCNFSM6AAAAAAWPVAKZ4> . You are receiving this because you commented.Message ID: ***@***.***>

-- Regards, Cyrille Artho

[quadhier]

I'm afraid that this patch might not apply to master branch (JPF on Java 8).

This bug resides in using invokevirtual to call private instance method, which might not happen on Java 8, according to JVMS 8. It says that invokespecial is used to call private instance method. IMHO, JPF on Java 8 needs to conform to JVMS 8.

Using invokevirtual to call private instance method is a mechanism introduced in Java 11, according to JEP 181. It says

With the change to the access rules, and with suitable adjustments to byte code rules, we can allow simplified rules for generating invocation bytecodes:

• invokespecial for private nestmate constructors,
• invokevirtual for private non-interface, nestmate instance methods,
• invokeinterface for private interface, nestmate instance methods; and
• invokestatic for private nestmate, static methods

This relaxes the existing constraint that private interface methods must be invoked using invokespecial (JVMS 6.5) and more generally allows invokevirtual to be used for private method invocation, rather than adding to the complex usage rules surrounding invokespecial.

If the patch is applied to JPF on Java 8, the tests still pass because there is no such bytecode pattern (call private instance method using invokevirtual) to trigger that code path.

I have checked the GitHub workflow log, it seems that those 13 failures are the same as before (mentioned in #274).

[cyrille-artho]

Ah yes, of course. I'll run the CI locally then to have a baseline to compare the result to.

…

On Fri, Apr 14, 2023 at 10:36 AM Daohan Qu ***@***.***> wrote: I'm afraid that this patch might not apply to master branch (JPF on Java 8). This bug resides in using invokevirtual to call private instance method, which might not happen on Java 8, according to JVMS 8. It says that invokespecial is used to call private instance method <https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html#jvms-6.5.invokespecial>. IMHO, JPF on Java 8 needs to conform to JVMS 8. Using invokevirtual to call private instance method is a mechanism introduced in Java 11, according to JEP 181 <https://openjdk.org/jeps/181>. It says With the change to the access rules, and with suitable adjustments to byte code rules, we can allow simplified rules for generating invocation bytecodes: - invokespecial for private nestmate constructors, - invokevirtual for private non-interface, nestmate instance methods, - invokeinterface for private interface, nestmate instance methods; and - invokestatic for private nestmate, static methods This relaxes the existing constraint that private interface methods must be invoked using invokespecial (JVMS 6.5) and more generally *allows invokevirtual to be used for private method invocation*, rather than adding to the complex usage rules surrounding invokespecial. If the patch is applied to JPF on Java 8, the tests still pass because there is no such bytecode pattern (call private instance method using invokevirtual) to trigger that code path. I have checked the GitHub workflow log, it seems that those 13 failures are the same as before (mentioned in #274 <#274>). — Reply to this email directly, view it on GitHub <#348 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABXV4RZA7RTI47RWOIHKACLXBEEBVANCNFSM6AAAAAAWPVAKZ4> . You are receiving this because you commented.Message ID: ***@***.***>

-- Regards, Cyrille Artho