JustIce Special Cases

Interface Merge Inconsistency with Sun's Preverifier

Brief Description

Frames stored in JustIce's InstructionContext instances disagree with what Sun's Preverifier produces when a ReferenceType that represents an Interface is merged with one that represents a normal class.

Status

Problem has been understood.

Action Items

1. Try to understand what the difference between cases that require post Exception handler merging and those that don't.
2. Understand cause of merging problem.
3. report bug.
4. implement fix.

Details

The Purifier1, occasionally disagrees with what Sun's preverifier produces because the algorithms are not identical. In an effort to understand these cases, the JustIce Verifier, which is included in the BCEL library, was used as a window into the algorithm in the JVM Specification section 4.9.2, The Bytecode Verifier. JustIce was designed to follow Sun's JVM Specification and it was rumoured that Sun's J2ME preverifier was created by modifying their existing verifier. Consequently, JustIce aught to provide a way to see how Sun's preverifier arrives at certain results. However, modifying JustIce's Verifier to log certain internal operations to the console revealed that there were cases where JustIce disagrees with Sun's preverifier.

One class of these cases is described in the JustIce Exception Handling Issue web page.

The case described here is related to the way that JustIce handles the merging of ReferenceTypes when one of the types represents an Interface. The JustIce LocalVariables.merge(LocalVariables) and OperandStack.merge(OperandStack) methods seem to follow the JVM Specification, section 4.9.2, accurately. In particular, the specification requires:

To merge two operand stacks, the number of values on each stack must be identical. The types of values on the stacks must also be identical, except that differently typed reference values may appear at corresponding places on the two stacks. In this case, the merged operand stack contains a reference to an instance of the first common superclass of the two types. Such a reference type always exists because the type Object is a superclass of all class and interface types. If the operand stacks cannot be merged, verification of the method fails.

To merge two local variable array states, corresponding pairs of local variables are compared. If the two types are not identical, then unless both contain reference values, the verifier records that the local variable contains an unusable value. If both of the pair of local variables contain reference values, the merged state contains a reference to an instance of the first common superclass of the two types.

Under normal circumstances, this merging is required for both the verification and preverification processes to work correctly. However, when a situation arises where a ReferenceType that represents an Interface is merged with a ReferenceType that represents a regualr object, Sun's preverifier produces StackMap entries that are not consistent with the specification above. Instead of producing a merged Type that is the first common superclass of the two Types, as the specification requires, the StackMap entries seem to show that the preverifier is allowing the ReferenceType that represents an Interface object to override the ReferenceType that represents a normal class object.

It is unknown whether this situation represents a hidden bug in the specification, a deliberate variance from the Bytecode Verifier specification in the preverifier, a bug in the preverifier or some other related issue. Nonetheless, it does provide an interesting point of investigation in the understanding of verifiers in general.

All of the cases listed in the Test Cases section, are cases where the Frames that fall through the end of an Exception handler merge with frames from normal execution that reach code after the end of the Exception handler. In some cases where a variable that represents an interface merges with an Exception variable, this causes a difference between what JustIce expects and what Sun's preverifier produces. In cases where the conflict is with a regular class variable, the merging process agrees with the result that Sun's preverifier produces.

Test Cases Exhibiting Issue

Example

ProblemCases.minimalExcessiveMerging method provides a minimal example of this issue and is shown below.

Source Code

321:  public void minimalExcessiveMerging() {
322:    Vector v = new Vector();
323:    try {
324:      Enumeration e = v.elements();
325:    } catch (Exception e) {
326:    }
327:  }

This code doesn't do anything, but it does show a minimal example of code that compiles just fine, but produces results inside of JustIce that are inconsistent with Sun's preverifier.

Bytecode

The following byte code is from the compiled and preverified class file created from the source in the previous section. The StackMap has been reformatted for readability.

public void minimalExcessiveMerging()
Code(max_stack = 2, max_locals = 3, code_length = 18)
0:    new		<java.util.Vector> (23)
3:    dup
4:    invokespecial	java.util.Vector.<init> ()V (24)
7:    astore_1
8:    aload_1
9:    invokevirtual	java.util.Vector.elements ()Ljava/util/Enumeration; (25)
12:   astore_2
13:   goto		#17
16:   astore_2
17:   return

Exception handler(s) =
From	To	Handler	Type
8	13	16	java.lang.Exception(27)

Attribute(s) =
	StackMap(
		(
			offset=16,
			locals={
				(type=Object, class=com.markcrocker.purifier.testcases.ProblemCases),
				(type=Object, class=java.util.Vector)
			},
			stack items={
				(type=Object, class=java.lang.Exception)
			}
		),
		(
			offset=17,
			locals={
				(type=Object, class=com.markcrocker.purifier.testcases.ProblemCases),
				(type=Object, class=java.util.Vector),
				(type=Object, class=java.util.Enumeration)
			}
		)
	)

Data Flow Analysis

In this case, everthing agrees until the very last instruction. Normal execution (ie: non-exceptional) jumps from offset 13 to 17 due to the goto #17 instruction at offset 13. The outgoing Frame at that point is:

DEBUG: Investigating instruction   13: goto[167](3) -> return
DEBUG:  Frame going into normal successor,   17: return[177](1) is:
Local Variables:
0: com.markcrocker.purifier.testcases.ProblemCases
1: java.util.Vector
2: java.util.Enumeration
OperandStack:
Slots used: 0 MaxStack: 2.

This is as expected and in agreement with the StackMapEntry at offset 17. Inside of the Exception handler, at offset 16, the astore_2 instruction has an outgoing Frame of:

DEBUG: Investigating instruction   16: astore_2[77](1)
DEBUG:  Frame going into normal successor,   17: return[177](1) is:
Local Variables:
0: com.markcrocker.purifier.testcases.ProblemCases
1: java.util.Vector
2: java.lang.Exception
OperandStack:
Slots used: 0 MaxStack: 2.

This is consistent with running astore_2 on the incoming Frame given by the StackMapEntry at offset 16. This is the only instruction in the Exception handler and it falls through to the return instruction at offset 17. However, this conflicts with the other incoming Frame from the goto instruction's outgoing Frame (see above). LocalVariables slot 2 is resolved by the merging mechanism, which decides that the only common super class for java.lang.Exception and java.util.Enumeration is java.lang.Object. So, the Pass3bVerifier ends up with a merged incoming Frame at the return instruction of:

DEBUG: Instruction   17: return[177](1)
DEBUG:  inFrame is:
Local Variables:
0: com.markcrocker.purifier.testcases.ProblemCases
1: java.util.Vector
2: java.lang.Object
OperandStack:
Slots used: 0 MaxStack: 2.

Although this seems to agree with the specification, it disagrees with the StackMapEntry for offset 17 because slot 2 contains a java.lang.Object instead of a java.util.Enumeration. In most cases, this merging is what is expected, but becase the invokevirtual instruction at offset 9 returns a java.util.Enumeration, which is an interface, Sun's preverifier treats this case differently and expects slot 2 to hold a java.util.Enumeration instead of a java.lang.Object. Clearly the merging process in the preverifier allows the Enumeration Interface to override the Exception rather than trying to find the nearest common superclass.

Counter Example

ProblemCases.minimalRequiresPostExceptionMerge method provides a minimal counter example of this issue and is shown below.

Source Code

330:  public void minimalRequiresPostExceptionMerge() {
331:    Vector v = new Vector();
332:    try {
333:      String s = v.toString();
334:    } catch (Exception e) {
335:    }
336:  }

Bytecode

public void minimalRequiresPostExceptionMerge()
Code(max_stack = 2, max_locals = 3, code_length = 18)
0:    new		<java.util.Vector> (23)
3:    dup
4:    invokespecial	java.util.Vector.<init> ()V (24)
7:    astore_1
8:    aload_1
9:    invokevirtual	java.util.Vector.toString ()Ljava/lang/String; (28)
12:   astore_2
13:   goto		#17
16:   astore_2
17:   return

Exception handler(s) =
From	To	Handler	Type
8	13	16	java.lang.Exception(27)

Attribute(s) =
	StackMap(
		(
			offset=16,
			locals={
				(type=Object, class=com.markcrocker.purifier.testcases.ProblemCases),
				(type=Object, class=java.util.Vector)
			},
			stack items={
				(type=Object, class=java.lang.Exception)
			}
		),
		(
			offset=17,
			locals={
				(type=Object, class=com.markcrocker.purifier.testcases.ProblemCases),
				(type=Object, class=java.util.Vector),
				(type=Object, class=java.lang.Object)
			}
		)
	)

Data Flow Analysis

This case is virtually identical to the previous example except that this time, the invokevirtual at offset 9 returns an object of type java.lang.String instead of an Interface of type java.util.Enumeration. In this case, Sun's preverifier agrees with JustIce and expects that the merging of Frames should produce a type of java.lang.Object for slot 2 of the LocalVariables array.

Solutions

The merge methods in the JustIce LocalVariables and OperandStack classes could be modified to give preference to Interfaces when merging with regular objects.

Back to Developer's Guide   Purifier Home Page