CSE647: Testing and Verification Project (ver. 9 Nov, 15:00) Due 5 Dec 2000 Scott Stoller This document describes two projects, each intended for a team of 2 students. I prefer that different teams work on different projects. The overarching goal is to transform a multiprocess Java system into an "equivalent" system containing a single process. For example, suppose the original system contains a process with 1 thread theta1 and a process with 2 threads, theta2 and theta3. The transformed system contains 1 process with 3 threads, each of which behaves like one of the original threads. This transformation seems useful for some aspects of conventional testing as well as model checking. Assume that the original system allows all processes to run on the same host. Assume that the options to the Java run-time system (including those specified in environment variables, such as CLASSPATH) are the same for all processes, except that some servers might need options -Djava.rmi.server.codebase=... -Djava.security.policy=... These options are ignored by our transformed program; we assume that the rmiregistry is able to find all necessary stub classes, and that all RMIs performed by the program are permitted by the security policy. Assume that the application does not dynamically create processes (e.g., with java.lang.Runtime). Assume that the user supplies a file, called the mainClasses file, of the form javaOptions class_1 rmiServerOptions_1 args_1 class_2 rmiServerOptions_2 args_2 ... such that the original system can be executed by a shell script that reads the file and, for each triple of lines "class_i rmiServerOptions_i args_i", executes "java javaOptions rmiServerOptions_i class_i args_i &". Lines starting with // are ignored. Blank lines are not ignored. The javaOptions, rmiServerOptions_i, and args_i lines may be blank. The rmiregistry is assumed to be running; the mainClasses file does not contain the command used to run the rmiregistry. The transformation modifies the program so that the threads from each process have their own copy of static variables of user-defined classes. For now, the transformation does NOT provide multiple copies of static fields of classes in the Java API. Assume that this does not affect the application (checking this automatically would be difficult). The transformation does not require source code and hence could provide multiple copies of most static variables of Java API classes, but some such static variables, such as java.lang.System.{in,out,err}, would require special treatment. It is probably easier to implement this transformation on bytecode than source code. Bytecode has a simple linear structure; source code has a complicated recursive structure. If a good implementation of parsing and type inference is available, then implementing this transformation on source code might be OK. The JavaClass API makes manipulation of class files relatively painless. It is installed in /home/facfs1/stoller/public/JavaClass. The transformation is decomposed into two steps, which are separate projects. Step 2 can be developed and tested independently of step 1, by manually writing some programs of the kind produced by step 1. NOTE: What follows is a *rough draft* of a design. Be on the lookout for errors, inconsistencies, and unnecessary complications. ---------------------------------------------------------------------- Step 1. Merge processes. Transform the program so that all threads of the original system run in the same process. Step 1.1. Create a class Driver with a main function that reads the mainClasses file and, for each triple of lines "class_i rmiServerOptions_i args_i", creates a thread that invokes the main function of class_i with arguments args_i. How to implement this? Approach 1. Use reflection. Advantage: easier to implement, because the code of Driver.main is independent of the contents of the mainClasses file. Disadvantage: model checkers for Java probably don't support reflection, so use approach 2. Approach 2. Generate code for Driver.main based on the contents of the mainClasses file. Disadvantage: slightly harder to implement. Advantage: does not require support for reflection. Driver.main creates a new ThreadGroup (named "main") for each process. Each of these "main" ThreadGroups has the system thread group as its parent. For example, in Driver, declare public static ThreadGroup systemThreadGroup = Thread.currentThread().getThreadGroup().getParent(); public static void main(String[] args) { ... mainThreadGroup = new ThreadGroup(systemThreadGroup, "main"); ... } Assume that differences in the numbers of Threads and ThreadGroups do not affect the application. For example, assume the application does not count (using getParent and enumerate) or estimate (using getParent and activeCount) the total number of active threads in the JVM. In the transformed system but not the original system, the main thread groups have the same parent; assume this does not affect the application; this assumption seems reasonable, because ThreadGroup is not serializable, so ThreadGroups in different processes cannot be compared directly. Step 1.2. Create multiple copies of the static variables, one copy per process in the original system. There are two orthogonal design decisions: Static dispatch vs. dynamic dispatch. With static dispatch, code for methods that directly or indirectly access static fields or static synchronized methods are copied, with one copy per process (of the original system). The code for process i has "hard-wired" accesses to the appropriate static fields and locks. With dynamic dispatch, there is (in general) only one copy of the code, which (at run-time) determines the process number of the current thread and uses it to access the appropriate static fields and locks. Multiple classes vs. arrays. With multiple classes, a class C_i is created for each process i; C_i declares the same static fields, synchronized static methods, and method as C. With arrays, class C is modified so that each static field v of type T is replaced with a static field v of type T[]; process i accesses v[i]. Similarly, an array of objects to use as locks for synchronized static methods is inserted in C. Static dispatch has less run-time overhead, but copying code seems awkward, so we use dynamic dispatch. The arrays approach combines more nicely with dynamic dispatch, because the dynamic dispatch can be implemented as an array access rather than a switch statement, so hereafter we use arrays. Modify C to have an array of values for each static variable and an array of objects used as locks for synchronized static methods. The Driver class should contain a static field "public final int numProc" that is initialized to the number of processes (this value is easily obtained from the mainClasses file). More specifically, for each static field v of C with type T, change the type of v to be "`T`[]" (backquotes indicate that T is a metavariable here), and insert in C a new field static Object[] lockForStaticMethods; Initialization requires some care. We need to modify code in C. and in methods called by C. to allocate and then initialize the array for each static variable. This requires modifying C. in place. A (static or instance) method m called by C. might also be called from other places, so we create a copy of m, named `m`clinit, and modify the copy, leaving the original method m unchanged (at this point). Most programs do not have clinit methods that invoke other methods, so the amount of copying is typically negligible. For each class C with a static field or static synchronized method, rename () to clinit(int i)V, and create a new method: C. { int i; lock = new Object[Driver.numProc]; for (i=0;i is transformed as follows. todo = {C.clinit(int procNum)V} done = empty while (!todo.empty()) { remove a method m(params)T from todo insert m in done if (m is C.clinit(int procNum)V) then update m in place (as follows) else create a new method named `m`clinit(params, int procNum)T and update the new method (as follows). replace each instruction getstatic C.v with getstatic `C`.`v` // push array ref onto operand stack iload procNum `t`aload // t depends on type T of C.v: i for int, a for address, etc. replace each instruction putstatic C.v with iload procNum swap // ref,val,index => ref,index,val `t`astore // t depends on type T of C.v: i for int, a for address, etc. for each instruction invoke* C1.m1(params1)T1 if the instruction is not of the form invokespecial C1. then replace the instruction with invoke* `C1`.`m1`clinit(params1,int procNum)T1 if (!done.contains(m) && !todo.contains(m)) todo.add(m); } Now consider the transformation for all other code, i.e., code not in and not called by C.. For each synchronized static method C.m(params) with return type T, replace the definition of C.m with // the "synchronized" attribute of m is removed static `T` `m`(`params`, int i) { synchronized (lockForStaticMethods[i]) { `body of C.m` } } To generate bytecode for this method from the bytecode for m, insert at the beginning of the method code to load lockForStaticMethods[i] onto the operand stack followed by a monitorenter instruction, insert a monitorexit before each return instruction, insert an exception handler that does monitorenter and re-throws the exception, and append an entry to the exception table that covers all lines of m (except the new exception handler), catches all exceptions (i.e., type is ANY), and has the new exception handler as its target. Processes are numbered according to their position in the mainClasses file. Dynamic dispatch for static fields requires efficiently determining the process number for the current thread. Here are two approaches. Hash table. Driver.main initializes a hash table that maps "main" ThreadGroups to process numbers. Each access to a static field and each invocation of a static method requires a hash table lookup, which is relatively expensive. Extend Thread. Create a class java.lang.Thread1 that extends Thread. Replace every occurrence of java.lang.Thread in the original application (including occurrences in "extends" clauses) with java.lang.Thread1. package java.lang; class Thread1 extends Thread { int procNum; ... } For each constructor Thread.(params), create a constructor Thread1.(params) that initializes procNum and then invokes Thread.(params). (This can be generated as bytecode, or generated as Java source and compiled). For the "main" threads created by Driver.main, the procNum of the thread is set directly, based on the position of the corresponding class in the mainClasses file. Every non-"main" thread has the same procNum as its parent thread, so procNum is initialized as follows (in the new constructor): procNum = ((Thread1)System.currentThread()).procNum; The "extend Thread" approach is clearly more efficient and hence preferable, though we need to assume that the application does not use reflection in a way that detects the changes. In every method m (except those related to ), after each instruction getstatic C.v, insert invokestatic System.currentThread()Ljava.lang.Thread; checkcast java.lang.Thread1 getstatic Thread1.procNum `t`aload // t is determined from T: t=i for integer, etc. replace each instruction putstatic C.v with invokestatic System.currentThread()Ljava.lang.Thread; checkcast java.lang.Thread1 getstatic Thread1.procNum swap // ref,val,index => ref,index,val `t`astore // t is determined from T: t=i for integer, etc. for each instruction invokestatic C.m(params)T such that C.m is synchronized, immediately before the instruction, insert invokestatic System.currentThread()Ljava.lang.Thread; checkcast java.lang.Thread1 getstatic Thread1.procNum Here's an optimization (implement it if time permits). Static analysis can easily determine an upper bound on the set of static variables and synchronized static methods accessed by each process, by looking for getstatic and putstatic bytecodes in methods reachable from the process's main method in the call graph. If a static variable is accessed by at most one process, don't replace it with an array, etc. If at most one process invokes the synchronized static methods of a class, leave unchanged those methods and the instructions that invoke them. Process Termination. A call to System.exit should terminate only the threads in the same process. To identify those threads, we could modify the constructor of Thread1 to insert "this" in a list of threads of the current process. However, there does not seem to be a simple way to terminate those threads. So, we assume that the application calls System.exit only when all other threads in the same process have terminated or are permanentaly blocked. Then System.exit terminates only the current thread. Blocking the thread permanently by waiting on some (new) object might keep objects alive longer than necessary. Thread.stop invokes a native method (and is deprecated). We introduce a method that works like Thread.stop but does not invoke a native method. Specifically, we introduce a method that throws java.lang.ThreadDeath, which the application should not catch. To be careful, we could check that no exception table entries explicitly catch ThreadDeath; entries that catch ANY are fine, assuming the associated exception handler merely does monitorexit and re-throw the exception. In short, we replace "invokestatic System.exit(I)V" with "invokestatic Driver.exit(I)V", defined by public static void exit(int status) { // assume all other threads from the same process have terminated // or are permanently blocked. throw new java.lang.ThreadDeath(); } Assume that the application does not use reflection in a way that detects the changes to class definitions. Assume that the original class files do not contain symbolic references to classes or members of classes created by the transformation (for example, if an original class file contains a reference to a non-existent field such as C.lockForStaticMethods or Thread.procNum, it would cause a run-time exception, indicating that the requested member does not exist; in the transformed program, that exception would not occur). Assume that each class initializer C. has side-effects only on the static variables of C and objects reachable (when the class initializer returns) only from static variables of C; thus, class initializers should not throw uncaught exceptions, read from standard input, produce output, invoke Thread.start, etc. This ensures that equivalent results are obtained by executing the class initializer at any time before the first access to a static variable of C by code not in and not called by C.. The Java Language Specification requires that a class be loaded and its initializer executed exactly when the class is first accessed. In our transformed program, a class initializer might be executed later (because "new C" instructions are not modified by our transformation) or earlier (because one process might use class C earlier than the other processes, and the transformed program executes the class initializer for all processes at once). To make the transformed program checkable using Dill and Park's system, we need to localize communication (see step 2). To make the transformed program checkable using JPF, we can either localize communication, or modify JVM^JPF so that it identifies remote invocations and implements them correctly (by copying the arguments and return value, etc.). The latter is more efficient (less interpretive overhead), but compatibility with other Java model checkers is more important. Communication failures. (Work on this after other aspects of the transformation have been completed and debugged.) There should be an option that lets the user decide whether to inject a specified subset of the exceptions representing communication failures. For communication using RMI, this includes exceptions that extend java.io.IOException thrown during serialization or unserialization, and exceptions that extend java.rmi.RemoteException (recall that each method of a remote interface must list java.rmi.RemoteException in its throws clause). The above transformation is intended to work correctly even if these exceptions occur spontaneously. ---------------------------------------------------------------------- Step 2. Localize communication. In other words, replace inter-process communication with intra-process communication. This is necessary because current model checkers for Java do not support the native methods used for inter-process communication (e.g., RMI uses ObjectOutputStream.writeObject and ObjectInputStream.readObject, which invoke native methods of java.lang.Class and java.lang.reflect.*, and uses sockets for the actual communication). For RMI, the basic idea is to replace remote invocations with local invocations. For sockets, the basic idea is to replace socket operations with operations on buffers. Hereafter we consider only RMI. For simplicity, assume that the system does not use java.rmi.activation.Activatable; this is easily checked by looking for references to java.rmi.activation.Activatable. Relaxing this assumption should be straightforward. The semantics of (local) method invocation is call-by-value for primitive data, and call-by-reference for remote references and local ("ordinary") references. The semantics of RMI is call-by-value for primitive data, call-by-reference for remote references, and call-by-value (i.e., copy) for local references. The copying is achieved by serializing and then unserializing the objects. In all cases, the semantics for passing return values is the same as for passing arguments. For details on parameter passing, section 2.6 of the RMI Specification. http://java.sun.com/products/jdk/1.2/docs/guide/rmi/spec/rmiTOC.doc.html For details on object serialization, see http://java.sun.com/j2se/1.3/docs/guide/serialization/index.html You should read the Object Serialization Specification and RMI Specification, though you don't need to memorize the details. The code for object serialization is available by doing /usr/bin/jar xvf /usr/local/pkg/jdk/src.jar src/java/io For example, the code in ObjectOutputStream.java that deals with serialization of objects is relevant (serialziation of classes is not necessary in our simulation of RMI). Serialization preserves the shape of the object graph reachable from the parameters. For example, if arg1 is a hash table that contains an entry with key o1, and arg2 is a linked list that contains o1, then after copying the arguments, the same (new) object o2 (a copy of o1) must appear in both the hash table and the linked list. To simulate RMI, we must distinguish local and remote references, and introduce code that performs appropriate copying. Like rmic, we generate stub classes. A reference r is a remote reference iff it points to an instance of a stub class. To check this easily, we introduce an interface StubInterface (which declares one method, described below), and let all stub classes implement StubInterface. Then (r instanceof StubInterface) is true iff r is a remote reference. Which thread should execute a remote invocation? The JVM automatically creates threads in the "system" ThreadGroup (i.e., the parent group of the group of the thread that runs the main method) to execute remote invocations. (For efficiency, the JVM maintains a pool of threads and re-uses them.) We could easily create a new thread to execute each remote invocation, but this would be inefficient. Re-using threads is possible but would require some effort. The easiest approach is to let the calling thread execute the remote invocation. We assume that the application does not detect this difference. For each class C that implements java.rmi.Remote (i.e., java.rmi.Remote or an interface that extends java.rmi.Remote appears in the "implements" clause of C or a superclass of C), the stub class C_Stub implements StubInterface and the interfaces implemented by C, contains an instance field localObj with type C, and defines a wrapper for every method declared or inherited by C. Calls to the simulated RMI registry return instances of stub classes. A method C_Stub.m copies appropriate parts of its arguments, invokes localObj.m(...), copies appropriate parts of the return value, and returns. Note: It is not sufficient to have a stub class for each remote interface, because an object may implement multiple remote interfaces, and the rmi registry would not know which stub class to use when constructing the return value of a lookup. The transformation should keep track of which classes are serializable, and the transformed program should throw java.io.NotSerializableException and java.io.InvalidClassException when appropriate. (I recommend adding this check after other aspects of the transformation are working.) Serialization can be customized by classes that declare writeObject and readObject, implement Externalizable, etc. (see the Object Serialization Specification for details). For now, check that the application does not perform such customizations; if it does, abort the transformation. In which classes should we insert the code that does the copying? In class C. The code that copies an instance of C is inserted in class C. Advantage: virtual method dispatch finds the appropriate copy method. Disadvantage: modifying the original classes is undesirable for Java API classes and is potentially visible to applications. Not in class C. The code that copies an instance of C is inserted in some class other than C; e.g., code for copying all relevant classes is collected into a class Copier. Use Object.getClass and Class.getName to determine the class of the object, and use a big switch statement to invoke the appropriate copy method. Advantage: no modifications to original classes. Disadvantage: Java model checkers might not support these two native methods. Could simulate those native methods by inserting a getClassName method in the original classes, but then the advantage of this approach is lost. A "remote interface" is an interface that extends java.rmi.Remote. A class C is "possibly directly serialized" if (i) C is serializable and (ii) there exists a class or interface C1 such that (ii-a) C is a subclass of (possibly equal to) C1, or C implements C1, and (ii-b) C1 is a parameter type or return type of some method in some remote interface. C is "possibly serialized" if (i) C is possibly directly serialized, or (ii) there exists a possibly serialized class C1 with an instance field of type C2 such that C extends or implements C2. The semantics of serialization+unserialization of an instance of C is that the new instance of C is created without invoking the constructor of C or of the serializable superclasses of C (if any); however, the constructor of the "lowest" non-serializable superclass of C (e.g., java.lang.Object) is invoked. The native method java.lang.Object.clone might not be available, so we create a constructor for C that has no side-effects. For concreteness, use "int" for the types of all the parameters of these side-effect-free constructors, and use zeroes as their arguments. For each possibly serialized class C1, for each superclass C of C1 (including C==C1), if (C is serializable) { if C.getSuperClass() is serializable then insert in C a new constructor public C(int i_1, ..., int i_n) { super(args1); } else insert in C a new constructor public C(int i_1, ..., int i_n) { super(); } }; where n is chosen so that the new constructor has a different signature than existing constructors of C, C1 is the direct superclass of C, n1 is the number of arguments of the side-effect-free constructor created in class C1, and args1 is a sequence of n1 zeroes. In bytecode, super() is "aload_0" "invokespecial `C1`.()" In bytecode, super(args1) is "aload_0" "iconst_0" repeated n1 times "invokespecial `C1`.(`I^n1`)" where I^n1 represents n occurrences of "I". (Of course, if C already has a constructor with this body, then we could use that constructor instead of creating a new one, but then we need to keep track of it, so don't bother.) For each class C that is possibly serialized, insert in C the definition of method copyRMI generated by generateCopyMethod(C). The code outside of quotes is executed at transformation time. The generated code is in quotes, with backquotes used to enclose expressions that should be replaced with their value at transformation time. The map passed to the copy method maps each object that has already been copied to the copy. generateCopyMethod(C) { "public `C` copyRMI(HashMap map) {" "Object o = map.get(this);" "if (o != null) return (`C`)o;" // number of zeroes in next statement equals number of parameters // of constructor inserted in C. "`C` x = new `C`(0,...0);" // it is important to update the map before any new calls to copyRMI. "map.put(this, x);" for each instance field 'Type f' declared or inherited by C { / if f is inherited by C from a class C1 that is not serializable, // then x.f should be initialized by the no-argument constructor // indirectly called by the invocation of new C(0,..,0), so we // generate no code here for such fields. if (!(f is inherited by C from a class C1 that is not serializable)) { // value of x.f is obtained from this.f if (Type is a primitive type) { "x.f = this.f" } else { "Type thisf = this.f;" "if ((thisf == null) || (thisf instanceof java.rmi.Remote))" " { x.f = thisf; }" "else {" if (Type is an array type) { copyArray(Type, "thisf", "x."+f, idx) } else { " x.f = thisf.copyRMI(map);" } "}" // end: !((thisf==null) ...) } } // end: if (!(f is inherited ...)) } "}" } // copyArray is executed at transformation time. it generates code that // allocates a new array of type T, assigns that array to variable dest, and // copies the contents of array of type T bound to variable src into the new // array. idx is the name of the variable to be declared and used as a loop // index. the name of the variable containing the map from old objects to // copies is assumed to be "map". copyArray(T,src,dest,idx) { eltType = T.getElementType(); // for now, don't handle multi-dimensional arrays, // though they cause no special difficulties. if (eltType is an array type) assert(false); "if (`src`==null) `dest`=null;" "else {" " int `idx`;" " `dest` = new `eltType`[`src`.length];" " map.put(`src`,`dest`);" " for (`idx`=0; `idx`<`src`.length; `idx`++) {" if (eltType is a primitive type) " `dest`[`idx`] = `src`[`idx`];" else { " srcidx = `src`[`idx`];" " if ((srcidx==null) || (srcidx instanceof java.rmi.Remote))" " { `dest`[`idx`] = srcidx; }" " else `dest`[`idx`] = `src`[`idx`].copyRMI(map);" } " }" // end: for (`idx`=0; ...) "}" // end: !(`src`==null) } For each class C that implements java.rmi.Remote, a class C_Stub is created (in the same package as C). As mentioned above, C_stub implements StubInterface and the interfaces implemented by C (including java.rmi.Remote), and contains one instance field localObj with type C. C_Stub also defines a constructor public C_Stub(C o) { localObj = o; } For each method "accessMod rType m(T_1 p_1, ..., T_n p_n)" declared or inherited by C, C_Stub contains the method definition generated by generateWrapper(accessMod, rType, m, [T_1, p_1, ..., T_n, p_n]). generateWrapper(accessMod, rType, m, [T_1, p_1, ..., T_n, p_n]) { "`accessMod` `rType` `m`(`T_1` `p_1`, ..., `T_n` `p_n`) {" " map = new HashMap();" for each parameter T_i p_i of C.m { // dest contains a variable name formed by prepending "v" onto the name // of p_i. This variable name is also denoted by, e.g., "... v`p_i` ...". dest = "v"+p_i; "`Type` `dest`;" if (T_i is a primitive type) "`dest` = `p_i`;" else { if (T_i is an array type) { copyArray(T_i,p_i,dest,idx) } else "`dest` = ((`p_i`==null) || `p_i` instanceof java.rmi.Remote) ? `p_i` : `p_i`.copyRMI(map);" } } if (rType is void) "localObj.m(vars);" else { // the invocation in the next statement compiles to an invokeinterface // instruction if (rType is a primitive type) "return localObj.`m`(v`p_1`,...,v`p_n`);" else { "`rType` r = localObj.`m`(v`p_1`,...,v`p_n`);" "map = new HashMap();" if (rType is an array type) { "`rType` r1;" copyArray(rType,r,r1,idx1) "return r1;" } else { "return ((r==null) || r instanceof java.rmi.Remote) ? r : r.copyRMI(map);" } } } "}" // end: method `C`_Stub.m } As an optimization (which you do not need to implement), if static analysis shows that C.m does not update any part of its arguments or store a reference to any part of its arguments in variables or fields that are live after the invocation returns, then copying the arguments is unnecessary. Similarly, static analysis can be used to identify cases in which copying the return value is unnecessary. In invokestatic instructions, methods of java.rmi.Naming are replaced with methods of Driver with the same names; for example, java.rmi.Naming.bind is replaced with Driver.bind. For the (simulated) registry to create a stub of the appropriate class for an exported object o, the class of o must be determined. In the absence of reflection, the easiest approach is to use virtual method dispatch. For each class C that implements java.rmi.Remote, insert in C the method definition public Remote createStub() { return new C_stub(this); } For convenience, we declare this method in StubInterface, mentioned above. public interface StubInterface { public Remote createStub(); } The rmi registry is simulated by inserting the following definitions in Driver. private TreeMap rmiRegistryMap = new TreeMap(); public static void bind(String name, Remote obj) throws AlreadyBoundException, MalformedURLException, RemoteException { if (rmiRegistryMap.containsKey(name)) throw new AlreadyBoundException(); rmiRegistryMap.put(name,obj); } public static void rebind(String name, Remote obj) throws MalformedURLException, RemoteException { rmiRegistryMap.put(name,obj); } public static void unbind(String name, Remote obj) throws MalformedURLException, RemoteException { rmiRegistryMap.remove(name); } public static Remote lookup(String name) throws NotBoundException, MalformedURLException, RemoteException { Remote r = rmiRegistryMap.get(name); if (r==null) throw new NotBoundException(); return ((StubInterface)r).createStub(); } public static String[] list(String name) throws MalformedURLException, RemoteException { // for now, we don't support this method. assert(false); return null; }