Enforcing Java Run-Time Properties Using Bytecode
`Rewriting
`
`Algis Rudys and Dan S. Wallach
`
`Rice University, Houston, TX 77005, USA
`(arudys|dwallach)@cs.rice.edu
`
`Abstract. Bytecode rewriting is a portable way of altering Java’s behavior by
`changing Java classes themselves as they are loaded. This mechanism allows us
`to modify the semantics of Java while making no changes to the Java virtual
`machine itself. While this gives us portability and power, there are numerous
`pitfalls, mostly stemming from the limitations imposed upon Java bytecode by
`the Java virtual machine. We reflect on our experience building three security
`systems with bytecode rewriting, presenting observations on where we succeeded
`and failed, as well as observing areas where future JVMs might present improved
`interfaces to Java bytecode rewriting systems.
`
`1 Introduction
`
`Bytecode rewriting presents the opportunity to change the execution semantics of Java
`programs. A wide range of possible applications have been discussed in the literature,
`ranging from the addition of performance counters, to the support of orthogonal persis-
`tence, agent migration, and new security semantics. Perhaps the strongest argument in
`favor of bytecode rewriting is its portability: changes made exclusively at the bytecode
`level can be moved with little effort from one Java virtual machine (JVM) to another, so
`long as the transformed code still complies to the JVM specification [1]. An additional
`benefit is that code added by bytecode rewriting can still be optimized by the underlying
`JVM.
`JVMs load Java classes from disk or elsewhere through “class loaders,” invoked as
`part of Java’s dynamic linking mechanism. Bytecode rewriting is typically implemented
`either by statically rewriting Java classes to disk, or through dynamically rewriting
`classes as they are requested by a class loader. This process is illustrated in Figure 1.
`In this paper, we describe three systems which we have built that use bytecode
`rewriting to add security semantics to the JVM. S AFKASI [2] is a bytecode rewriting-
`based implementation of stack inspection by security-passing style. Soft termination [3]
`is a system for safely terminating Java codelets.1 Finally, transactional rollback [4] is
`a system for undoing the side-effects of a terminated codelet, leaving the system in a
`consistent state suitable for, among other thing, restarting terminated codelets.
`
`1 The term “codelet” is also used in artificial intelligence, numerical processing, XML tag pro-
`cessing, and PDA software, all with slightly different meanings. When we say “codelet,” we
`refer to a small program meant to be executed in conjunction with or as an internal component
`of a larger program.
`
`PALO ALTO NETWORKS Exhibit 1023 Page 1
`
`

`
`(1) Executing class Foo
`
`public class Foo {
`Bar b;
`
`}
`
`(2) Undefined
`Reference to Bar
`
`(6) Class is
`loaded
`
`public class Bar {
`. . .
`
`}
`
`ClassLoader {
`. . .
`
`}
`
`(4) Fetches
`Bar class
`from
`filesystem
`
`(3) Calls
`class loader
`
`Bar.class
`
`JVM
`
`(5) Class loader
`loads Bar class
`into JVM
`
`(4a) Bytecode Transformer
`Rewrites Bar class
`
`ByteCode Transformer {
`. . .
`
`}
`
`Fig. 1. How a Java bytecode transformation changes the process of loading a class. If an already
`loaded class, Foo, uses an as yet undefined class Bar (either accesses a static member or creates
`an instance) (1), the JVM traps the undefined reference to Bar (2), and sends a request for the
`class loader to load the class (3). The class loader fetches the class file (Bar.class) from the
`filesystem (4). In standard Java, the input class is then loaded into the JVM (5). In a bytecode
`rewriting system, the bytecode transformer is first invoked to transform the class (4a). In either
`case, the class is now loaded in the JVM (6).
`
`Java bytecode rewriting has been applied in far too many other systems to provide
`a comprehensive list here. We cite related projects in order to discuss the breadth of the
`use of the technique.
`
`Access Control. By intercepting or wrapping calls to potentially dangerous Java meth-
`ods, systems by Pandey and Hashii [5], Erlingsson and Schneider [6], and Chander et
`al. [7] can apply desired security policies to arbitrary codelets without requiring these
`policies to be built directly into the Java system code, as done with Java’s built-in secu-
`rity system.
`
`J-Kernel [8] and J-SEAL2 [9] both focus
`Resource Management and Accounting.
`primarily on isolation of codelets. Bytecode rewriting is used to prevent codelets from
`interfering in each others’ operations. JRes [10] focuses more on resource accounting;
`bytecode rewriting is used to instrument memory allocation and object finalization sites.
`
`Optimization. Cream [11] and BLOAT (Bytecode-Level Optimization and Analysis
`Tool) [12] are examples of systems which employ Java bytecode rewriting for the pur-
`pose of optimization. Cream uses side-effect analysis, and performs a number of stan-
`dard optimizations, including dead code elimination and loop-invariant code motion.
`BLOAT uses Static Single Assignment form (SSA) [13] to implement these and several
`other optimizations.
`
`PALO ALTO NETWORKS Exhibit 1023 Page 2
`
`

`
`Profiling. BIT (Bytecode Instrumenting Tool) [14] is a system which allows the
`user to build Java instrumenting tools. The instrumentation itself is done via bytecode
`rewriting. Other generic bytecode transformation frameworks, such as JOIE [15] and
`Soot [16], also have hooks to instrument Java code for profiling.
`
`Other Semantics. Sakamoto et al. [17] describe a system for thread migration imple-
`mented using bytecode rewriting. Marquez et al. [18] describe a persistent system im-
`plemented in Java entirely using bytecode transformations at class load time. Notably,
`Marquez et al. also describe a framework for automatically applying bytecode trans-
`formations, although the status of this framework is unclear. Kava [19] is a reflective
`extension to Java. That is, it allows for run-time modification and dynamic execution of
`Java classes and methods.
`All of these systems could also be implemented with customized JVMs (and many
`such customized JVMs have been built). Of course, fully custom JVMs can outperform
`JVMs with semantics “bolted on” via bytecode rewriting because changes can be made
`to layers of the system that are not exposed to the bytecode, such as how methods are
`dispatched, or how memory is laid out. The price of building custom JVMs is the loss
`of portability.
`Code rewriting techniques apply equally to other languages. One of the earliest im-
`plementations of code rewriting was Informer [20], which, to provide security guaran-
`tees, applied transformations to modules written in any language and running in kernel
`space. In particular, the transformations discussed in this paper could be applied to
`add similar semantics to other type-safe languages like Lisp and ML as well as such
`typed intermediate representations as Microsoft’s Common Language Infrastructure
`and typed assembly languages.
`A number of issues arise in the course of implementing a bytecode rewriting sys-
`tem. In this paper, we describe our experiences in implementing three such system in
`Section 2. Section 3 discusses JVM design issues that we encountered when building
`our systems. Section 4 discusses optimizations we used to improve the performance
`impact of our systems. Finally, we present our conclusions in Section 5.
`
`2 Bytecode Rewriting Implementations
`
`This paper reflects on lessons learned in the implementation of three security systems
`built with Java bytecode rewriting. The first, S AFKASI [2], uses bytecode rewriting to
`transform a program into a style where security context information is passed as an
`argument to every method invocation. Soft termination [3] is a system for safely ter-
`minating Java codelets by trapping backward branches and other conditions that might
`cause a codelet to loop indefinitely. Transactional rollback [4], intended to be used in
`conjunction with soft termination, allows the system to undo any side-effects made to
`the system’s state as a result of the codelet’s execution, returning the system to a known
`stable state.
`
`PALO ALTO NETWORKS Exhibit 1023 Page 3
`
`

`
`2.1 SAFKASI
`
`SAFKASI [2] (the security architecture formerly known as stack inspection), is an im-
`plementation of Java’s stack inspection architecture [21] using Java bytecode rewriting.
`SAFKASI is based on security-passing style, a redesign of stack-inspection which prov-
`ably maintains the security properties of stack-inspection, improves optimizability and
`asymptotic complexity, and can be reasoned about using standard belief logics.
`Stack inspection is a mechanism for performing access control on security-sensitive
`operations. Each stack frame is annotated with the security context of that stack frame.
`Stack inspection checks for privilege to perform a sensitive operations by inspecting
`the call stack of the caller. Starting at the caller and walking down, if it first reaches
`a frame that does not have permission to perform the operation, it indicates failure. If
`it first reaches a frame that has permission to perform the operation and has explicitly
`granted permission, the operation is allowed. Otherwise, the default action is taken as
`defined by the JVM.
`With security-passing style, instead of storing the security context in the stack, the
`security context is passed as an additional parameter to all methods. This optimizes
`security checks by avoiding the linear cost of iterating over the call stack.
`SAFKASI is implemented by passing an additional parameter to every method in
`the system. This parameter is the security context. It is modified by the says operator,
`which is used by a class to explicitly grant its permission for some future operation. The
`stack-inspection check simply checks this context for the appropriate permission.
`
`Performance. SAFKASI was tested using the NaturalBridge BulletTrain Java Compiler,
`which compiles Java source to native binary code [22]. With CPU-bound benchmarks,
`SAFKASI-transformed programs executed 15 to 30% slower than equivalent stack in-
`specting programs.
`
`2.2 Soft Termination
`
`Soft termination [3] is a technique for safely terminating codelets. The basis for soft
`termination is that the codelet doesn’t need to terminate immediately, as long as it is
`guaranteed to eventually terminate. We implemented soft termination by first adding a
`termination flag field to each class. We then instrumented each method, preceding all
`backward branches with termination checks to prevent infinite loops and beginning all
`methods with termination checks to prevent infinite recursion.
`The termination check simply checks the class’s termination flag. If set, a Java ex-
`ception is thrown. The codelet is free to catch the exception, and resume. However, the
`next time a backward branch or method call is encountered, the exception is thrown
`anew. Using this mechanism, we can prove that the codelet is guaranteed to terminate
`in finite time.
`Soft termination distinguishes between system code and user code (that is, codelets).
`System code should not be interrupted, even if the associated codelet has been marked
`for termination. Codelets are rewritten by the transformer, while system code is not
`touched. This result can be achieved by performing the transformation in the Java class
`
`PALO ALTO NETWORKS Exhibit 1023 Page 4
`
`

`
`loader. Since the system classes and codelets are naturally loaded by different class
`loaders, the separation becomes natural.
`Blocking calls are also addressed in our system. Blocking calls are method calls,
`most commonly input/output calls, which wait for a response before returning. We
`wanted to guarantee that a codelet could not use blocking calls to bypass termination.
`The Thread.interrupt() method allows us to force blocking method calls to re-
`turn.
`To determine which threads to interrupt, we wrap blocking calls with code to let the
`soft termination system know that a particular thread is entering or leaving a blocking
`call. This code also uses Java’s stack inspection primitives to determine whether the
`code is blocking on behalf of a codelet or on behalf of the system code. Only threads
`blocking on a codelet’s behalf are interrupted.
`
`Performance We implemented this system and measured the performance when run-
`ning on Sun Microsystems Java 2, version 1.2.1 build 4. The worst results, of a simple
`infinite loop, was 100% overhead. In the real-world applications tested, the overhead
`was up to 25% for loop-intensive benchmarks, and up to 7% for the less loop-intensive
`benchmarks.
`
`2.3 Transactional Rollback
`
`Transactional rollback [4] was designed to complement soft termination in a resource
`management system. Soft termination guarantees that system state is never left incon-
`sistent by a codelet’s untimely termination. However, the same guarantee is not made
`about a codelet’s persistent state. Any inconsistencies in this state could destabilize
`other running codelets as well as complicate restarting a terminated codelet.
`We solve this problem by keeping track of all changes made by a codelet, and if
`the codelet is terminated, the changes are undone. Each codelet is run in the context of
`a transaction to avoid data conflicts. We implement transactional rollback by first du-
`plicating each method in all classes (including system classes). The duplicate methods
`take an additional argument, the current transaction.
`In the duplicate methods, all field and array accesses (that is, field gets and puts
`and array loads and stores) are preceded with lock requests by the transaction on the
`appropriate object. Method calls are also rewritten to pass the transaction parameter
`along. A number of fields are added to a class to maintain a class’s backups and lock
`state for the class.
`If the code is not running in a transaction, the methods called are for the most part
`exactly the original methods. This allows us to limit the performance impact to code
`running in a transaction.
`
`Performance We implemented this system and measured the performance when run-
`ning on Sun Microsystems Java 2, version 1.3 for Linux. The overhead of the transaction
`system ranged from 6 to 23(cid:2). The major component in this overhead was in managing
`array locks.
`
`PALO ALTO NETWORKS Exhibit 1023 Page 5
`
`

`
`3 JVM Design Issues
`
`Bytecode rewriting is inherently different from language run-time system customiza-
`tion. Bytecode rewriting results in classes that are run inside a standard Java virtual
`machine. These classes treat the JVM as a black box; functionality internal to the JVM
`cannot be altered. Rewritten classes must be valid bytecode, according to the virtual
`machine specification [1]. However, because codelets might be malicious, we cannot
`assume that the code we receive as input was generated by valid Java source, and so
`cannot necessarily use the Java Language Specification [23] for guidance.
`Table 1 summarizes our bytecode rewriting implementations and associated wish
`list items.
`
`3.1 JVM Internals
`
`The basic distinction of bytecode rewriting as opposed to language run-time system
`customization is that with bytecode rewriting, operating on JVM internals is not possi-
`ble.
`
`Class Reloading Once classes are loaded into the JVM, they can neither be unloaded
`nor reloaded. Likewise, one cannot control when a class’s static initializer will be called
`or when dead objects’ finalizers will be invoked. Java version 1.4 includes a feature in its
`debugger architecture called HotSwap, which allows classes to be reloaded 2. Existing
`activation records continue to run with code from the original version of the class.
`Also, the new class’s static initializer is not run again, and new fields added to existing
`classes will be null or zero. This new feature was not available when we were building
`our systems, and would have been a welcome addition, despite its limitations.
`
`Memory Management One of the features on our “wishlist” is the addition of hooks
`into the JVM’s memory system. Had we been able to exploit the garbage collector’s
`safe point traps, our soft termination system could have performed periodic checks with
`more flexibility and lower overhead than trapping backward branches. Also, by modi-
`fying the garbage collector, we might have been able to enforce memory usage policies
`that are more robust than those used in JRes [10] and J-SEAL2 [9], which assume that
`whoever allocated a block of memory should be responsible for “paying” for that mem-
`ory. We implemented exactly such a mechanism to account for memory usage in IBM’s
`RVM [24] by modifying the RVM’s garbage collector [25]. New pluggable garbage col-
`lection systems for Java, such as GCTk [26], may allow us to implement such features
`without requiring changes to the underlying JVM. In addition, the Real-time Specifica-
`tion for Java3 allows programs to create individual memory regions treated differently
`by the garbage collector and select from which region memory is allocated.
`
`2 See
`http://java.sun.com/j2se/1.4/docs/guide/jpda/enhancements.
`html for more information.
`3 See http://www.rtj.org/ for more information.
`
`PALO ALTO NETWORKS Exhibit 1023 Page 6
`
`

`
`Added
`Fields
`
`Modified
`Methods
`
`SAFKASI
`
`Soft Termination
`
`(cid:15) Security principal
`
`(cid:15) Termination flag
`
`(cid:15) Added security con-
`text parameter to each
`method
`(cid:15) Added security con-
`text parameter to all
`method invocations
`(cid:15) Add Security-passing
`style security checks
`(cid:15) Added stub methods
`for upcalls
`
`(cid:15) Added safe point-like
`termination checks on
`backward
`branches
`and method calls
`(cid:15) Wrapped
`block-
`ing calls to register
`with
`soft
`termina-
`tion system to allow
`interrupting
`
`Added
`Classes
`
`JVM Issues
`
`(cid:15) Closed world
`(cid:15) System classes
`(cid:15) Native methods
`(cid:15) Bootstrapping
`
`(cid:15) Wrapping subclass for
`class with blocking
`native methods
`
`(cid:15) Synchronization
`(cid:15) Blocking calls
`
`Transactional
`Rollback
`(cid:15) Lock state
`(cid:15) Class backup
`
`each
`
`(cid:15) Duplicated
`method
`(cid:15) Added transaction pa-
`rameter to each dupli-
`cated method
`(cid:15) Added
`transaction
`parameter
`to
`each
`method
`invocation
`from
`duplicated
`methods
`(cid:15) Instrumented field and
`array accesses within
`methods
`(cid:15) Added code in origi-
`nal methods to detect
`transactional context
`
`for
`classes
`(cid:15) Added
`and
`instance
`static
`of
`backups
`each
`existing class
`
`(cid:15) System classes
`(cid:15) Native methods
`(cid:15) Bootstrapping
`(cid:15) Synchronization
`
`(cid:15) Arrays
`
`Wish List
`Items
`
`(cid:15) Class file reloading
`
`(cid:15) Synchronization inter-
`face
`(cid:15) Garbage collector in-
`terface
`
`(cid:15) Synchronization inter-
`face
`(cid:15) Access to array imple-
`mentation
`
`Table 1. This table summarizes the three systems based on bytecode rewriting. It describes the
`transformations to Java bytecode, JVM-related issues, and items on the JVM wish list inspired
`by that particular project.
`
`PALO ALTO NETWORKS Exhibit 1023 Page 7
`
`

`
`Threads Thread scheduling is another black box subsystem of the Java virtual ma-
`chine. No mechanism is provided for either replacing the thread scheduler or fine-
`tuning how threads are scheduled; the only interface provided is the Thread.
`setPriority() method. The Real-time Specification for Java does allow for re-
`placing the thread scheduler, but has only recently been finalized.
`
`Native Methods Native methods, while not strictly part of the JVM, are also treated as
`black boxes. We cannot control where a native method might go, and how that native
`method might behave. Native methods might perform arbitrary computations and are
`not necessarily guaranteed to return in a timely fashion (e.g., I/O routines might block
`indefinitely while they wait for data to arrive).
`Furthermore, we have no control over up-calls from native methods back to the
`Java classes which we do control. In particular, we have no access to the Java Native
`Interface (JNI) calls used by native methods to interface with Java. If we could intercept
`these calls, then we could transform native methods to see a view of the Java classes
`consistent with what the Java classes themselves see after being transformed. Since that
`is not an option with current JVMs, we have adopted a number of strategies to cope
`with native methods, described in Section 3.3.
`Note that certain JVMs implemented in Java, such as BulletTrain and IBM’s
`RVM [24], use fewer native methods than JVMs implemented in machine code. The
`tradeoff is that they have more methods which are not native but are treated specially by
`the JVM. In our bytecode transformations, these methods need to be treated the same as
`standard native methods. See Section 3.3 for details on such special methods and how
`we handled them.
`
`3.2 “Local” Java Semantics
`
`The flexibility of Java bytecode is both its benefit and its curse. A bytecode rewriting
`system must deal with every feature in the bytecode. We first deal with “local” features,
`which is to say, aspects of the Java bytecode where an individual class or method can
`be rewritten without needing any knowledge of how other classes in the JVM might
`interoperate with it.
`
`Constructors Constructors have two properties which set them apart from normal
`methods. First, no operations, whether initialization or otherwise, can be performed
`until either the super-class constructor or a same-class constructor has been called, al-
`though arguments to a super-class constructor may be legally computed. This presented
`a problem in the soft termination system.
`Soft termination is designed to check the value of the termination flag at the begin-
`ning of every method, including constructors, but inserting this check into a constructor
`results in a verifier error. Instead, the best we can do is to check for termination im-
`mediately following the call to the super-class constructor. As a result, we may not
`be able to terminate a loop constructed with constructors that recursively invoke other
`constructors before calling their super-class constructor.
`
`PALO ALTO NETWORKS Exhibit 1023 Page 8
`
`

`
`Transactional rollback requires every object to be locked before it can be modified.
`Normally, this is accomplished with the addition of a specialized lock instance to every
`object instance. However, while an object is being constructed, this lock instance will
`be null. To address this, we needed to add checks everywhere an object is accessed to
`check whether its lock instance is null, slowing down all locking code to handle this
`special case.
`
`Exceptions Exceptions (and errors) can introduce implicit or asynchronous con-
`trol flows into a Java method. Asynchronous exceptions,
`induced by calls to
`Thread.stop(), can occur literally anywhere, and at any time. For this reason,
`among other reasons, Sun has deprecated the method. Implicit exceptions typically oc-
`cur as a side-effect of a program error, such as a NullPointerException or the
`various arithmetic errors. Here, the control flow edge from the potentially faulty opera-
`tion to the construction and throwing of an exception does not appear explicitly in the
`Java bytecode.
`This caused problems for S AFKASI, which needs to pass its security context as
`a parameter to the exception constructors. The only available choices were to either
`save the security context in thread-local storage or to give up and pass no context.
`Using thread-local storage is expensive, requiring a hash table operation on every store,
`and the exception constructors for Java’s implicit exceptions appear to never perform
`security critical operations. As a result, SAFKASI gives up, allowing these constructors
`to be invoked with no security context, and letting them start over as if there was no call
`stack before them.
`We also observe that, in Java bytecode, an exception handling block (that is, a try-
`catch block) is represented as offsets delimiting the try block and the offset for the
`start of the catch block. The JVM specification requires that the catch block start
`strictly after the try block ends. That is, an exception-handler cannot handle its own
`exceptions. However, Sun’s JVM does not enforce this restriction.
`This can be used by a malicious codelet to evade a soft termination signal. The
`exception handler acts as a backward-branch; when an exception is thrown in the ex-
`ception handler, control passes to an earlier point in the text of the program. If this
`exception always occurs, like the termination signal of soft termination, the result will
`be an infinite loop. We solved the problem by having the soft termination system detect
`and reject such exception-handling blocks.
`
`Arrays Transactional rollback needs to be able to save backup copies of all objects
`before they are written. For most classes, we can create “backup” fields for every orig-
`inal field in the class. Assigning the backup to refer to the original object is sufficient
`to preserve the original value of the backup. However, for arrays, this no longer works;
`there is no place in the array to store a reference to the array’s backup. Our solution
`is to maintain a global hash table that maps arrays to their backups. For each array,
`the backup array must be the same size as the original. Creating this backup requires
`copying the whole array. For codelets that make extensive use of arrays, whether large
`or small, this creates a significant overhead.
`
`PALO ALTO NETWORKS Exhibit 1023 Page 9
`
`

`
`Our preferred solution would be for Java to have a mechanism to let us add our own
`field to all arrays. Java’s arrays already track their length; we want one more reference
`that we can use transparently to the Java application.
`
`Threads Threads can be thought of as a special case of native methods which make
`up-calls to Java code (in this case, during thread initialization, the up-call happens to
`be on a new thread while control returns to the original thread). In both S AFKASI and
`transactional rollback, we needed state computed in the parent thread to be sent to
`the child thread. This was performed by modifying java.lang.Thread to have
`an additional field where the parent thread can store context information in the child
`thread. This context is consulted when the child’s run() method is invoked by the
`thread run-time system. Since threads are implemented in Java, this modification can
`be performed as part of the bytecode-rewriting process.
`Another important issue with threads is controlling them when they block. Blocking
`can be caused by synchronization primitives (see below) or by native methods, which
`might not return right away. Luckily, all of the JVM’s methods which might block will
`respond to calls to Thread.interrupt(), causing the formerly blocked thread to
`immediately throw an exception and canceling the operation that was previously under-
`way. We used this mechanism with soft termination to signal blocking threads that we
`wished to kill.
`However, in implementing soft termination, we found that some mechanism was
`still needed to determine which thread is blocking, and whether it was blocking on be-
`half of system code (which should not be interrupted) or on behalf of a codelet (which
`we want to interrupt). We chose to wrap blocking methods with code to register the cur-
`rent thread with the soft termination system as blocking before the call, and unregister
`it afterward. We use Java’s stack inspection mechanism to determine the context of the
`blocking call (system versus codelet). The soft termination system could now interrupt
`blocking threads as necessary.
`
`Synchronization The semantics of Java’s monitorenter and monitorexit
`bytecode instructions and synchronized method modifier cannot be changed
`through bytecode rewriting. When a deadlock occurs in Sun’s JDK, the only way to
`recover is by restarting the JVM. The JDK 1.4 debugging architecture provides a mech-
`anism to address this (a debugger is allowed to forcibly pop activation records from a
`thread’s stack), which might be useful to clean up after deadlock. This can similarly be
`used to terminate threads that are in a deadlock situation.
`Another issue which soft termination had to deal with was the exact semantics of the
`monitorenter and monitorexit bytecodes, which acquire and release system
`locks, respectively. If these calls are not properly balanced, it becomes possible to lock
`a monitor in such a way that terminating the codelet will not cause the monitor to be
`released. Despite the fact that neither the JVM nor the Java language specifications
`allow such construction, current JVM bytecode verifiers accept such programs. Our
`soft termination system did not attempt to deal with this problem.
`
`PALO ALTO NETWORKS Exhibit 1023 Page 10
`
`

`
`Verification We have seen several cases where our own code had to effectively extend
`the Java bytecode verifier in order to guarantee correctness of our system. We saw these
`issues with Java’s synchronization and exception features. We also saw cases where
`Java’s verifier got in the way of perfectly sound program transformations, particularly
`with regard to the restrictions on how Java’s constructors invoke their super-class con-
`structors.
`Ideally, the Java bytecode verifier should be disentangled from the current class
`loading system to stand on its own. This would simplify the addition of new checks to
`the verifier, such as checks for undesirable exception and synchronization behavior, and
`it would make it easier to remove checks that, at least in our context, are unnecessary,
`such as the super-class constructor checks. Furthermore, a modular Java bytecode veri-
`fier would be quite useful to our systems as a mechanism for checking our input before
`we rewrite it, allowing us to make stronger assumptions about the quality of our input
`and reducing the opportunity for carefully crafted codelets to trick a code rewriting sys-
`tem into mistakenly outputting a rewritten codelet with more privilege than it should
`have been given.
`
`3.3 “Global” Java Semantics
`
`In many cases, particularly when we consider changes that effect the method signa-
`tures advertised by a class, we must consider how our changes interact with other Java
`classes, with native code, and even with classes that may not have been loaded into the
`system yet.
`
`“Special” Methods and Classes Every JVM has certain methods and classes which are
`special in some way. Sun’s JVM, for example, doesn’t allow the rewriter to add fields
`to java.lang.Class or java.lang.Object. The NaturalBridge Java system is
`even more restrictive, as it is implemented, itself, in Java, and has many “special” Java
`classes that provide the necessary machinery to implement language internals. Calls to
`these (privileged) classes are quietly replaced with the (dangerous) primitive operations
`that they represent. Changes to these classes are simply ignored.
`If a global transformation could be applied to all Java classes in a consistent way,
`such as the security-passing style transformation of S AFKASI, then the resulting sys-
`tem would be perfectly self-consistent. However, once special methods and classes are
`added, everything becomes more difficult. Now, the system must keep a list of special
`classes and methods and treat calls to them as special cases.
`For SAFKASI, this meant that we could not pass our security context as an addi-
`tional argument to all methods. Instead, we used thread-local storage to temporarily
`hold the security context, and then called the original, special method. If that method
`just returned, then everything would continue as normal. If that method were to make a
`call to another Java method, then it would be using the original Java method signatures,
`without the additional argument for passing security contexts.
`To support this, we were forced to add wrapper methods for every method in the
`system. These wrappers existed solely to receive calls from special methods, fetch
`the security context from the thread-local storage, and then invoke the proper target
`
`PALO ALTO NETWORKS Exhibit 1023 Page 11
`
`

`
`method. Luckily, this wrapper technique proved to be quite general. It also supports
`native method up-calls and Java reflection (although we never tried to hack Java re-
`flection such that it would see all the classes as if they had never been rewritten). By
`pairing wrappers, one to convert from security-passing style methods to special meth-
`ods, and one to convert from regular methods back to security-passing style methods on
`up-calls from special code, we were able to maintain the illusion that the whole system
`supported security-passing style calling conventions. We used the same strategy in our
`transactional rollback system to manage the transactional state, normally passed as an
`additional argument to all methods.
`
`Inheritance Java’s class inheritance is also a complicating factor in global transforma-
`tions. When a subc