CS201J: Problem Set 6: Assembling Java

University of Virginia, Department of Computer Science
CS201J: Engineering Software, Fall 2003

Problem Set 6: Nibbling at Byte Codes Out: Tuesday, 11 November 2003
Due: Tuesday, 25 November 2003

Collaboration Policy - Read Carefully
For this problem set, you may either work alone and turn in a problem set with just your name on it, or work with one other student of your choice. If you work with a partner, you and your partner should turn in one assignment with both of your names on it.
Regardless of whether you work alone or with a partner, you are encouraged to discuss this assignment with other students in the class and ask and provide help in useful ways. You may consult any outside resources you wish including books, papers, web sites and people. If you use resources other than the class materials, indicate what you used along with your answer.
Purpose

Understand how Java class files encode Java programs
Understand the difference between overloading and overriding methods
See how the Java VM bytecode verifier provides type safety, and how it could be violated without it
Consider the implications of voting machines programmed using a language that does not provide type safety to democracy.
On all previous assignments, you used a Java compiler to compile source code in the Java programming language into Java byte codes (the .class file). You didn't need to examine the class file itself, but just ran the byte codes using the Java virtual machine.

Directions:

Download this file to your machine: ps6.zip
Save it to c:\localdata as you did with Problem Set 5.
Log into your Home Directory.
Open Eclipse by selecting Start | SEAS | Java Apps | Eclipse 2.1 | Eclipse CS201J (from the Windows Start menu)
Inside Eclipse (as with Problem Set 5):

Click on File | New | Project
Select the default option: Java->Java Project
Type in ps5 as the project name and click Finish.
Click Yes when Eclipse asks you if you want to switch to the Java perspective
Then, in Eclipse's Package Explorer, right click on ps6 and select Import.
Select Zip file as the import source.
Type c:\localdata\ps6.zip into the "From zip file" box. Hit tab. Then click Finish.

Now, set up your project to run ESC/Java on the source code files.

Click on Project | Properties.
Click Ok.

Java Byte Codes
Consider the simple Java method add (defined in Simple.java):
public class Simple {
  static int add (int x, int y) {
     return x + y;
  }

  static public void main () {
     System.out.println ("result: " + add (2, 3));
  }
}
After compiling Simple.java (in Eclipse), we can use D-Java to view the Simple.class file produced. Start a DOS command shell by selecting Run from the Windows Start menu and entering cmd. Then cd to the directory containing your project code. Run D-Java Simple.class to see the bytecodes in Simple.class. You should see something like this (the add method code is bold):
public synchronized class Simple extends Object
{

Method public void ()
>> max_stack=1, max_locals=1 <<
    0 aload_0
    1 invokenonvirtual #9 ():void>
    4 return
Line number table:
    pc   line
     0      1
Local variable table:
  start length   slot
     0      5      0  this:Simple

Method static int add(int,int)
>> max_stack=2, max_locals=2 <<
    0 iload_0
    1 iload_1
    2 iadd
    3 ireturn
Line number table:
    pc   line
     0      3
Local variable table:
  start length   slot
     0      4      0  x:int
     0      4      1  y:int

Method public static void main()
   ... code for main method here
The first instruction, iload_0 pushes the int value stored in location 0 onto the stack. The first parameter, x, is stored in location 0, so after the iload_0 the top of the stack contains the value of the x parameter. The second instruction iload_1 pushes the int value stored in location 1 onto the stack. After this, the top two values on the stack are
         value of y
         value of x
The next instruction, iadd requires that the stack contains two int values. It pops those values off the stack, and pushes their sum. After the iadd instruction, the top of the stack is x + y.
Note that even though Simple.java does not contain a constructor, the Java compiler has produced one in the class file. The void <init>() method is the default constructor that takes no parameters. It loads the this object on the stack (using aload_0), and then invokes the superclass constructor. Since we did not use extends in the class definition, it inherits from Object.
At the end of this document, there is a specification of a subset of the Java byte code instruction set.
1. (10) Suppose the stack in initially empty and the local variable table is:
      slot   type   value
         0   int    1
         1   int    2
What value will be on top of the stack after executing the instructions below?
       iload_0
       iload_0
       iload_0
       iadd
       iload_1
       iadd
       iadd
Jasmin
Jasmin is an assembler for Java bytecodes. Unlike a compiler which does complex translations, and assembler just does simple transformations. For example, in the actual class file everything is just bits.
For example, in the actual class file iload_0 is represented by 00011010 (instruction 26). The assembler converts the iload_0 instruction to 00011010 to save you the trouble of looking up and entering the actual bits.
If you run D-Java -o jasmin class, D-Java will output the Jasmin assembly file for class. To run D-Java start a DOS command shell by selecting "Run" from the "Start" menu, and entering "cmd" as the program name. In the DOS shell enter
J:
cd J:\cs201j\ps6
to change the working directory to the PS6 directory.
The file Simple.j is the Jasmin assembly file created by running
    D-Java -o jasmin Simple.class > Simple.j
Modify Simple.j so instead of pushing both x and y on the stack before the iadd instruction, it only pushes x.
Run jasmin Simple.j to produce a new class file, and then run java Simple. If your modification was correct, you should obtain a verification error like this:
Execption in thread "main" java.lang.VerifyError: (class: Simple, method:
add, signature: (II)I) Unable to pop operand off and empty stack
Normally, if a class does not pass the bytecode verifier, the virtual machine will not execute it. However, you can run java with the -noverify option to turn off bytecode verification.
Run java -noverify Simple.
2. (10) Turn in your modifications and the output from java -noverify Simple. Explain as much as you can about why you get the result you did. (You are not expected to be able to explain why you get the exact result you did, but the more you can explain about what happened, the better.)
Calling Methods
Consider the IntValue.java program below:
public class IntValue {
	private int x;

	IntValue(int x) {
		this.x = x;
	}

	public int getValue() {
		return x;
	}

	public boolean equals(IntValue v) {
		return x == v.getValue();
	}

	static public void main(String args[]) {
		IntValue a = new IntValue(10);
		IntValue b = new IntValue(10);
		Object c = new IntValue(10);

		if (a.equals(b)) {
			System.out.println("a and b are equivalent");
		} else {
			System.out.println("a and b are not equivalent");
		}

		if (a.equals(c)) {
			System.out.println("a and c are equivalent");
		} else {
			System.out.println("a and c are not equivalent");
		}

		if (c.equals(a)) {
			System.out.println("c and a are equivalent");
		} else {
			System.out.println("c and a are not equivalent");
		}
	}
}
Running java IntValue produces:
a and b are equivalent
a and c are not equivalent
c and a are not equivalent
Look at the class file the compiler produced for IntValue.java. The Java-D output is below:
.method public static main([Ljava/lang/String;)V
Label1:
    new IntValue
    dup
    bipush 10
    invokenonvirtual IntValue/(I)V
    astore_1
.line 18
.var 1 is a LIntValue; from Label2 to Label11
Label2:
    new IntValue
    dup
    bipush 10
    invokenonvirtual IntValue/(I)V
    astore_2
.line 19
.var 2 is b LIntValue; from Label3 to Label11
Label3:
    new IntValue
    dup
    bipush 10
    invokenonvirtual IntValue/(I)V
    astore_3
.line 21
.var 3 is c Ljava/lang/Object; from Label4 to Label11
Label4:
    aload_1
    aload_2
    invokevirtual IntValue/equals(LIntValue;)Z
    ifeq Label5
.line 22
    getstatic java/lang/System/out Ljava/io/PrintStream;
    ldc "a and b are equivalent"
    invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
    goto Label6
.line 24
Label5:
    getstatic java/lang/System/out Ljava/io/PrintStream;
    ldc "a and b are not equivalent"
    invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
.line 27
Label6:
    aload_1
    aload_3
    invokevirtual java/lang/Object/equals(Ljava/lang/Object;)Z
    ifeq Label7
.line 28
    getstatic java/lang/System/out Ljava/io/PrintStream;
    ldc "a and c are equivalent"
    invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
    goto Label8
.line 30
Label7:
    getstatic java/lang/System/out Ljava/io/PrintStream;
    ldc "a and c are not equivalent"
    invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
.line 33
Label8:
    aload_3
    aload_1
    invokevirtual java/lang/Object/equals(Ljava/lang/Object;)Z
    ifeq Label9
.line 34
    getstatic java/lang/System/out Ljava/io/PrintStream;
    ldc "c and a are equivalent"
    invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
    goto Label10
.line 36
Label9:
    getstatic java/lang/System/out Ljava/io/PrintStream;
    ldc "c and a are not equivalent"
    invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
.line 38
Label10:
    return
3. (10) Explain why the value of the a.equals(b) is different from the value of a.equals(c) and c.equals(a) even though each value holds an object created using new IntValue (10). A good explanation will explain why the Java compiler produces calls to different methods for the first and second calls to equals.
4. (10) Modify IntValue.j so the second and third calls to equals are the same as the first (just cut and paste the invokevirtual IntValue/equals(LIntValue;)Z to replace the other two calls. Run jasmin to produce a new class file, and java IntValue to observe the result. Explain why you get the result you do? A exceptional explanation will also explain why there is no verification error for this code.
Violating Type Safety
With the Java programming language and the standard Java compiler, all programs we produce are type safe. This means we cannot treat Objects and integers, or integers as Objects. We cannot use operations of one datatype on a value that is not a subtype of the datatype.
By producing byte codes directly, however, we can violate type safety. For example, consider these instructions:
      iconst 12 // push the int constant 12 on the stack
      invokevirtual java/lang/Object/equals(Ljava/lang/Object;)Z<
These instructions attempt to invoke the Object equals method on the integer value 12. Of course, this makes no sense — we cannot invoke methods on primitive types.
For the remaining questions, your task is to violate type safety to help Mooch steal the Dog Catcher election. LiveMeek was impressed with your performance on Exam 1, and has hired you to produce a fancy animation at the end of the election to impress the testers so much so they won't bother to check if the results are correct.
Before printing out the election results, their code will call CompleteElection.displayAnimation(). Mooch has asked you to create an implemention of CompleteElection.displayAnimation that will set Spot's vote total to 0. (Of course, we know no UVa student would ever do anything so heinous as fix an election, but this is just an exercise.)
LiveMeek assumes it is safe to hire you to implement CompleteElection, since the sensitive ElectionResults object will not be visible inside the CompleteElection class. You know, however, that they will turn off the bytecode verifier when they run the election.
5. (10) To tamper with the election, you will need to find out where the ElectionResults object e is stored in memory. Where is e stored? (Explain how you found out, and include the code you used.)
Hint: You may want to start by modifying the Election.java to do:
   int i = 3;
   System.out.println(i);
before the call to CompleteElection.displayAnimation(). Then use D-Java to generate the corresponding Jasmin assembly code, and figure out how to modify it to find out the location of e.
6. (20) Modify CompleteElection.j to obtain a reference to the election object.
7. (30) Finish your implementation of displayAnimation to change Spot's vote total to 0. If you are sucessful, running
   java -noverify Election
(on the original Election class) will produce:
The dog catcher is: Muffy
Your code may assume that the "Dog Catcher" office is always the first office in the election, and "Spot" is always the first candidate for the office.
Your solution should not require making any changes to any class besides CompleteElection. To develop your solution, you will probably want to make changes to other classes, though, so you can use to Java compiler to generate byte codes similar to those you will need to use in your solution.
If you can change the election results only by changing CompleteElection.j without requiring the -noverify flag (or doing any physical damage to the ITC lab machines!), that is worth 200 bonus points.
Java Byte Code Instructions
A subset of the Java byte code instruction set is specified below. For a complete specification, see The Java^TM Virtual Machine Specification.
iload_0
   REQUIRES: Variable location 0 contains an int.
   EFFECTS: Pushes the value in location 0 on the top of the stack.
                 stack_post = push (stack_pre, value in location 0)

iload_1
   REQUIRES: Variable location 1 contains an int.
   EFFECTS: Pushes the value in location 0 on the top of the stack.
                 stack_post = push (stack_pre, value in location 1)

iadd
   REQUIRES: The top two locations on the stack contain int
      values.
   EFFECTS: Pops the top two values from the stack, and pushes their
     sum.  
     If stack_pre = [ a, b, c, d, ... ] then stack_post = [ a + b, c, d ... ]

ireturn
   REQUIRES: The top of the stack contains an int.
   EFFECTS: Pops an int from the top of the stack and pushes it onto the operand 
     stack of the invoker; everything else on the operand stack is discarded.

istore
   REQUIRES: The top of the stack contains an int.
   EFFECTS: Pops an int off of the stack and stores it in local variable , 
     where  is 0, 1, 2, or 3.

ifeq <label>
   REQUIRES: The top of the stack contains an int.
   EFFECTS: Pops an int from the top of the stack.  If int = 0, jump to the 
     code located at <label>, otherwise continue with the next instruction after ifeq.

dup
   REQUIRES: The top of the stack contains a string.
   EFFECTS: Pops a string from the top of the stack and then pushes the string 
     back onto the stack twice, making a duplication of the string.

invokevirtual <method-spec>
   REQUIRES: <method-spec> is a method specification token made up of a class 
     name, such as IntValue, a method name, such as equals, and a descriptor, 
     such as (Ljava/lang/Object;)Z.
   EFFECTS: Used to invoke all methods except interface methods, static methods, 
     and special cases, which are handled by invokeinterface, invokestatic, and 
     invokespecial.

invokeinterface <method-spec> <n>
   REQUIRES: <method-spec> is a method specification token made up of an interface 
     name, a method name, and a descriptor, and  is an interger in the range 0-255.
   EFFECTS: Invokes a method declared within a Java interface.

invokestatic <method-spec>
   REQUIRES: <method-spec> is a method specification token made up of a class name, 
     such as IntValue, a method name, such as equals, and a descriptor, such as 
     (Ljava/lang/Object;)Z.
   EFFECTS: Calls a static method.

aload_<n>
   REQUIRES: <n> is a valid local variable 0, 1, 2, or 3 in the current frame. 
   EFFECTS: Retrieves an object reference held in the local variable 0, 1, 2, or 
     3 and pushes it onto the stack.

ldc <value>
   REQUIRES: <value> is an integer, float, or a literal (quoted string).
   EFFECTS: Pushes <value> onto the stack.

goto <label>
   REQUIRES: <label> is a label name assigned to one location in a method.
   EFFECTS: jumps to the instructions beginning at <label>.

getstatic <field-spec> <descriptor>
   REQUIRES: <field-spec> contains a class name and a fieldname and <descriptor> 
     is the Java type descriptor for the field, such as Ljava/io/PrintStream.  The 
     top of the stack contains a reference to an object.
   EFFECTS: Pops a reference to an object from the stack, retrieves the value of 
     <field-spec> from the reference, and pushes the value onto the operand stack.

return
   REQUIRES: nothing
   EFFECTS: Returns from a method whose return type is void; all items on the current 
     method?s operand stack are then discarded.

new <class>
   REQUIRES: <class> is the name of the class to use (java/lang/Object).
   EFFECTS: creates instances of objects by determining the size in bytes of instances 
     of the class and allocating sufficient memory for them.  Field of the instance are 
     initialized to 0 or null and a reference to the new object is pushed onto the stack.
Credits: This problem set was developed for UVA CS 201J Fall 2003 by Mike Peck, Katie Winstanley, and David Evans.

University of Virginia
Department of Computer Science
CS 201J: Engineering Software

Sponsored by the
National Science Foundation

cs201j-staff@cs.virginia.edu