System and method for secure execution of multiple applications using a single GC heap

BACKGROUND OF THE INVENTION

[0001] 1. Field of the Invention

[0002] The present invention relates generally to computer software. More particularly, the present invention relates to the secure execution of applications in a multi-processing environment.

[0003] 2. Description of the Relevant Art

[0004] The growing popularity of the platform-independent programming language Java™ has brought about an increased need for executing multiple Java™ applications co-located on the same computer. These Java™ applications often expect that the environment in which they are executing will perform automatic garbage collection for efficient memory management. Garbage collection (GC) is a mechanism for managing an area of memory (usually called a heap) in a computer system. The memory heap may be shared by multiple applications which may be executing concurrently. Typically, GC is periodically performed by searching all or part of the memory heap to determine which part of that area (e.g., which data structures or objects) are being used. GC may then “clean up” the portion of the heap which is not being used by preparing it for later use (e.g., freeing it) by the applications. GC is therefore useful for reclaiming unused memory in a manner that is generally automatic and transparent to applications.

[0005] Nevertheless, current approaches towards GC have their drawbacks. For example, the use of a single GC heap among multiple applications is known to have at least three problems. These three areas of concern are discussed as follows.

[0006] The first problem is that GC heap consumption per application cannot be measured efficiently. Thus, GC heap consumption per application cannot be limited efficiently. Limiting GC heap consumption may be an important step in providing a secure application environment. For example, faulty or malicious applications should be prevented from consuming too much of the heap in a secure environment. Because a single heap may be shared by multiple applications, determining how much of the heap is used by each application poses problems. It is usually possible to determine GC space used by each object at object creation and to accumulate per-application heap consumption in this manner. However, after GC takes place, this count is no longer correct. Because of the shared nature of the heap, it is difficult to know how much of the heap is used by each application after GC. One approach might include allocating a flag per object to identify to which application that object belongs. However, this approach requires extra memory and may therefore be unacceptably inefficient in environments like embedded systems where memory is at a premium.

[0007] The second problem is that the aforementioned approach may be vulnerable to denial-of-service attacks. For example, a faulty or malicious application may allocate and discard objects at a high rate. This behavior may cause frequent GCs and may therefore consume a significant amount of system resources such as CPU time. Because a single heap is shared by multiple applications, it is not clear which application is responsible for CPU time consumed by a GC. If time consumed by GCs is ignored and not charged to individual applications, a malicious application may intentionally cause GCs by creating and discarding a great number of objects. This may hinder normal execution of other applications.

[0008] The third problem is vulnerability to a finalizer attack. A malicious application may create and discard an object which has a finalizer that takes a long time to finish or that never terminates. In some environments, such as certain Java™ Virtual Machines (JVMs), finalizers for objects are executed just prior to discarding those objects during GC. Finalizers are typically executed by a single dedicated thread. Therefore, if one finalizer takes a long time to execute or never terminates, finalizers for other objects may be prevented from executing. These other objects may not be properly discarded from the GC heap, and unnecessary memory consumption may result.

[0009] In general, providing one GC heap per application may provide a solution for these problems. However, this solution is memory-hungry. Multiple heaps bind a fixed amount of memory for each application, and it often costly to grow or shrink such heaps. The need for such growth or shrinkage may arise when an application terminates or when a new application begins executing. This approach may therefore tend to consume a large amount of memory, especially if the environment (e.g., the target device or computer system) does not include a Memory Management Unit (MMU). Consequently, this approach is undesirable for a small-footprint or memory-constrained environment such as a consumer or embedded system.

[0010] Therefore, improved systems and methods for secure and efficient execution of multiple applications using a single GC heap are desired.

SUMMARY OF THE INVENTION

[0011] The problems outlined above are in large part solved by various embodiments of a system and method for secure execution of multiple applications using a single GC heap as disclosed herein. The applications may include applets, servlets, operating system services, components, JavaBeans™, or other suitable executable units or programs. “Application” and “program” are herein used synonymously. In one embodiment, the applications are executable in a platform-independent programming environment such as the Java™ environment. In one embodiment, the applications are executable on a single instance of a virtual machine, such as a Java™ Virtual Machine, which is implemented in accordance with a platform-independent virtual machine specification, such as the Java™ Virtual Machine Specification.

[0012] The method for sharing a single GC heap among a plurality of applications may include maintaining a root set for each of the applications during their execution. Each root set may include one or more pointers or other references to data structures (e.g., objects) stored in the memory heap. After a garbage collection operation is performed, the root sets may be used to measure one or more resources consumed by each of the applications.

[0013] The root sets may be used to measure heap consumption by associating each data structure in the memory with a particular application based on reachability from the application's root set. A total amount of the heap used by the application may then be determined by summing the memory consumption of each of the data structures associated with the application.

[0014] The root sets may be used to measure CPU time consumption during the GC by determining a total CPU time consumed by the GC, determining a total amount of the memory used by each of the applications (as discussed above), and determining the CPU time consumption for each of the applications by dividing the total time consumed by the GC by the total amount of the memory used by the application. Alternately, the total number of data structures per application may be used instead of the total heap consumption per application.

[0015] In one embodiment, the applications may include a plurality of threads. In this case, an application identifier may be stored with each of the threads belonging to a particular application, and the application identifier may refer to the particular application. In one embodiment, each of the applications may include a finalizer thread. An object finalizer may be executed in the finalizer thread for each application. In this manner, GC-related misbehavior may be limited to GC of the objects of the misbehaving application itself.

[0016] In one embodiment, static fields of some classes may be shared among applications. To prevent the compromising of the GC security measures summarized above, static files may be replicated per application.

BRIEF DESCRIPTION OF THE DRAWINGS

[0017] Other objects and advantages of the invention will become apparent upon reading the following detailed description and upon reference to the accompanying drawings in which:

[0018]FIG. 1 is an illustration of a typical computer system architecture which is suitable for implementing various embodiments.

[0019]FIG. 2 is an illustration of a Java™ Platform architecture which is suitable for implementing various embodiments.

[0020]FIG. 3 is a diagram illustrating secure execution of multiple applications using a single GC heap according to one embodiment.

[0021]FIG. 4 is a flowchart illustrating a method of secure execution of multiple applications using a single GC heap according to one embodiment.

[0022] While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawing and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.

DETAILED DESCRIPTION OF SEVERAL EMBODIMENTS

[0023]FIG. 1: A Typical Computer System

[0024] Turning now to the drawings, FIG. 1 is an illustration of a typical, general-purpose computer system <b>100</b> which is suitable for implementing the system and method for secure execution of multiple applications using a single GC heap as disclosed herein. The computer system <b>100</b> may include at least one central processing unit (CPU) or processor <b>102</b>. The CPU <b>102</b> is coupled to a memory <b>104</b> and a read-only memory (ROM) <b>106</b>. The memory <b>104</b> is representative of various types of possible memory media: for example, hard disk storage, floppy disk storage, removable disk storage, or random access memory (RAM). The terms “memory” and “memory medium” may include an installation medium, e.g., a CD-ROM or floppy disk, a computer system memory such as DRAM, SRAM, EDO RAM, Rambus RAM, etc., or a non-volatile memory such as a magnetic media, e.g., a hard drive, or optical storage. The memory medium may include other types of memory as well, or combinations thereof. In addition, the memory medium may be located in a first computer in which the programs are executed, or may be located in a second different computer which connects to the first computer over a network. In the latter instance, the second computer provides the program instructions to the first computer for execution.

[0025] As shown in FIG. 1, typically the memory <b>104</b> permits two-way access: it is readable and writable. The ROM <b>106</b>, on the other hand, is readable but not writable. The memory <b>104</b> and/or ROM <b>106</b> may store instructions and/or data which implement all or part of the systems and methods described in detail herein, and the memory <b>104</b> and/or ROM <b>106</b> may be utilized to install the instructions and/or data. In various embodiments, the computer system <b>100</b> may take various forms, including a personal computer system, desktop computer, laptop computer, palmtop computer, mainframe computer system, workstation, network appliance, network computer, Internet appliance, personal digital assistant (PDA), embedded device, smart phone, television system, or other suitable device. In general, the term “computer system” can be broadly defined to encompass any device having a processor which executes instructions from a memory medium.

[0026] The CPU <b>102</b> may be coupled to a network <b>108</b>. The network <b>108</b> is representative of various types of possible networks: for example, a local area network (LAN), wide area network (WAN), or the Internet. The systems and methods for secure execution of multiple applications as disclosed herein may therefore be implemented on a plurality of heterogeneous or homogeneous networked computer systems <b>100</b> through one or more networks <b>108</b>. The CPU <b>102</b> may acquire instructions and/or data for implementing the systems and methods for a secure execution of multiple applications using a single GC heap as disclosed herein over the network <b>108</b>.

[0027] Through an input/output bus <b>110</b>, the CPU <b>102</b> may also coupled to one or more input/output devices that may include, but are not limited to, video monitors or other displays, track balls, mice, keyboards, microphones, touch-sensitive displays, magnetic or paper tape readers, tablets, styluses, voice recognizers, handwriting recognizers, printers, plotters, scanners, and any other devices for input and/or output. The CPU <b>102</b> may acquire instructions and/or data for implementing the systems and methods for secure execution of multiple applications as disclosed herein through the input/output bus <b>110</b>.

[0028] The computer system <b>100</b> is operable to execute one or more computer programs. The computer programs may comprise operating system or other system software, application software, utility software, Java™ applets, and/or any other sequence of instructions. Typically, an operating system performs basic tasks such as recognizing input from the keyboard, sending output to the display screen, keeping track of files and directories on the disk, and controlling peripheral devices such as disk drives and printers. Application software runs on top of the operating system and provides additional functionality. Because applications take advantage of services offered by operating systems, and because operating systems differ in the services they offer and in the way they offer the services, an application must usually be designed to run on a particular operating system. The computer programs are stored in a memory medium or storage medium such as the memory <b>104</b> and/or ROM <b>106</b>, or they may be provided to the CPU <b>102</b> through the network <b>108</b> or I/O bus <b>110</b>.

[0029] In one embodiment, the computer programs executable by the computer system <b>100</b> may be implemented in the Java™ Language. The Java™ Language is described in <i>The Java Language Specification </i>by Gosling, Joy, and Steele (Addison-Wesley, ISBN 0-201-63451-1), which is incorporated herein by reference. A general discussion of the Java™ Language follows. The Java™ Language is an object-oriented programming language. In an object-oriented programming language, data and related methods can be grouped together or encapsulated to form an entity known as an object. All objects in an object-oriented programming system belong to a class, which can be thought of as a category of like objects which describes the characteristics of those objects. Each object is created as an instance of the class by a program. The objects may therefore be said to have been instantiated from the class. The class sets out variables and methods for objects which belong to that class. The definition of the class does not itself create any objects. The class may define initial values for its variables, and it normally defines the methods associated with the class (i.e., includes the program code which is executed when a method is invoked.) The class may thereby provide all of the program code which will be used by objects in the class, hence maximizing re-use of code which is shared by objects in the class.

[0030]FIG. 2: The Java™ Platform

[0031] The Java™ Platform which utilizes the object-oriented Java™ Language is a software platform for delivering and running the same applications on a plurality of different operating systems and hardware platforms. As will be described in further detail below, the Java™ Platform includes system-dependent portions and system-independent portions, and therefore the Java™ Platform may be thought of as having multiple embodiments. The Java™ Platform sits on top of these other platforms, in a layer of software above the operating system and above the hardware. FIG. 2 is an illustration of the Java™ Platform and the relationships between the elements thereof in one embodiment. The Java™ Platform has two basic parts: the Java™ Virtual Machine <b>222</b>, and the Java™ Application Programming Interface (Java™ API). The Java™ API may be thought of as comprising multiple application programming interfaces (APIs). While each underlying platform has its own implementation of the Java™ Virtual Machine <b>222</b>, there is only one Virtual Machine specification. The Java™ Virtual Machine specification is described in <i>The Java Virtual Machine Specification </i>by Lindholm and Yellin (Addison-Wesley, ISBN 0-201-63452-X), which is incorporated herein by reference. By allowing the Java™ applications <b>236</b> to execute on the same Virtual Machine <b>222</b> across many different underlying computing platforms, the Java™ Platform can provide a standard, uniform programming interface which allows Java™ applications <b>236</b> to run on any hardware on which the Java™ Platform has been implemented. The Java™ Platform is therefore designed to provide a “write once, run anywhere” capability.

[0032] Developers may use the Java™ Language and Java™ APIs to write source code for Java™-powered applications <b>236</b>. A developer compiles the source code only once to the Java™ Platform, rather than to the machine language of an underlying system. Java™ programs compile to bytecodes which are machine instructions for the Java™ Virtual Machine <b>222</b>. A program written in the Java™ Language compiles to a bytecode file which can run wherever the Java™ Platform is present, on any underlying operating system and on any hardware. In other words, the same Java™ application can run on any computing platform that is running the Java™ Platform. Essentially, therefore, Java™ applications <b>236</b> are expressed in one form of machine language and are translated by software in the Java™ Platform to another form of machine language which is executable on a particular underlying computer system.

[0033] The Java™ Virtual Machine <b>222</b> is implemented in accordance with a specification for a “soft” computer which can be implemented in software or hardware. As used herein, a “virtual machine” is generally a self-contained operating environment that behaves as if it were a separate computer. As shown in FIG. 2, in one embodiment, the Java™ Virtual Machine <b>222</b> is implemented in a software layer. Various implementations of the Java™ Virtual Machine <b>222</b> can run on a variety of different computing platforms: for example, on a browser <b>214</b> sitting on top of an operating system (OS) <b>212</b><i>a </i>on top of hardware <b>210</b><i>a; </i>on a desktop operating system <b>212</b><i>b </i>on top of hardware <b>210</b><i>b; </i>on a smaller operating system <b>212</b><i>c </i>on top of hardware <b>210</b><i>c; </i>or on the JavaOS operating system <b>218</b> on top of hardware <b>210</b><i>d. </i>Computer hardware <b>210</b><i>a, </i><b>210</b><i>b, </i><b>210</b><i>c, </i>and <b>210</b><i>d </i>may comprise different hardware platforms. JavaOS <b>218</b> is an operating system that is optimized to run on a variety of computing and consumer platforms. The JavaOS <b>218</b> operating environment provides a runtime specifically tuned to run applications written in the Java™ Language directly on computer hardware without requiring another operating system.

[0034] The Java™ API or APIs form a standard interface to Java™ applications <b>236</b>, regardless of the underlying operating system or hardware. The Java™ API or APIs specify a set of programming interfaces between Java™ applications <b>236</b> and the Java™ Virtual Machine <b>222</b>. The Java™ Base API <b>226</b> provides the basic language, utility, I/O, network, GUI, and applet services. The Java™ Base API <b>226</b> is typically present anywhere the Java™ Platform is present. The Java™ Base Classes <b>224</b> are the implementation of the Java™ Base API <b>226</b>. The Java™ Standard Extension API <b>230</b> provides additional capabilities beyond the Java™ Base API <b>226</b>. The Java™ Standard Extension Classes <b>228</b> are the implementation of the Java™ Standard Extension API <b>230</b>. Other APIs in addition to the Java™ Base API <b>226</b> and Java™ Standard Extension API <b>230</b> can be provided by the application or underlying operating system. A particular Java™ environment may include additional APIs <b>234</b> and the classes <b>232</b> which implement them. Each API is organized by groups or sets. Each of the API sets can be implemented as one or more packages or namespaces. Each package groups together a set of classes and interfaces that define a set of related data, constructors, and methods, as is well known in the art of object-oriented programming.

[0035] The porting interface <b>220</b> lies below the Java™ Virtual Machine <b>222</b> and on top of the different operating systems <b>212</b><i>b, </i><b>212</b><i>c, </i>and <b>218</b> and browser <b>214</b>. The porting interface <b>220</b> is platform-independent. However, the associated adapters <b>216</b><i>a, </i><b>216</b><i>b, </i>and <b>216</b><i>c </i>are platform-dependent. The porting interface <b>220</b> and adapters <b>216</b><i>a, </i><b>216</b><i>b, </i>and <b>216</b><i>c </i>enable the Java™ Virtual Machine <b>222</b> to be easily ported to new computing platforms without being completely rewritten. The Java™ Virtual Machine <b>222</b>, the porting interface <b>220</b>, the adapters <b>216</b><i>a, </i><b>216</b><i>b, </i>and <b>216</b><i>c, </i>the JavaOS <b>218</b>, and other similar pieces of software on top of the operating systems <b>212</b><i>a, </i><b>212</b><i>b, </i>and <b>212</b><i>c </i>may, individually or in combination, act as means for translating the machine language of Java™ applications <b>236</b>, APIs <b>226</b> and <b>230</b>, and Classes <b>224</b> and <b>228</b> into a different machine language which is directly executable on the underlying hardware.

[0036]FIGS. 3 and 4: Secure Execution of Multiple Applications Using a Single GC Heap

[0037]FIGS. 3 and 4 illustrate one approach towards secure execution of multiple applications according to one embodiment. In one embodiment, a GC root set may be maintained in memory for each application. GC heap consumption for an application may be measured based on the reachability of objects in the GC heap from that application's root set. The number of alive objects per application may then be counted after GC based on the number of reachable objects from each application's root set. This approach may solve the first problem identified in the Description of the Relevant Art by permitting the measurement of GC heap consumption per application. In other embodiments, the methods described herein may be performed upon data structures rather than objects, such as in a programming environment that is not object-oriented.

[0038] An executing program (such as a Java™ program) may include a set of threads. Threads provide a way to achieve multi-tasking in a single processing space. If an application desires to run animations and play music while scrolling the page and downloading a text file from a server, for example, then multithreading provides fast, lightweight concurrency within a single process space. Threads are sometimes referred to as lightweight processes or execution contexts. Each of the threads may be actively executing a set of methods (one method having called the next). Each of these methods may have arguments or local variables that are references to objects. These references are said to belong to a “root set” of references that are immediately accessible to the program. Other references in the root set may include, for example, static reference variables defined in loaded classes and references registered through the Java™ Native Interface (JNI) API.

[0039]FIG. 3 shows a heap <b>340</b> and a series of per-application root sets <b>330</b>, <b>332</b>, and <b>334</b>. In one embodiment, all objects referenced by a root set of references are said to be reachable and are not to be collected during a GC. Also, those objects may include references to still other objects, which are also reachable, and so on. Collectively, these objects (both directly and indirectly reachable by a root set) are shown in FIG. 3 as reachable objects <b>320</b> for the root sets <b>330</b>, <b>332</b>, and <b>334</b>. All other objects on the heap may be considered unreachable, and all unreachable objects <b>310</b> may be eligible for garbage collection. If an unreachable object has a finalizer method, arrangements may be made for the object's finalizer to be called. Unreachable objects with no finalizers and objects whose finalizers have been called may simply be reclaimed during garbage collection.

[0040]FIG. 4 is a flowchart illustrating a method of secure execution of multiple applications using a single GC heap according to one embodiment. In <b>402</b>, a GC root set may be maintained in a memory for each application as discussed with reference to FIG. 3. Each root set may include one or more pointers to data structures (e.g., objects) that have been created in memory (usually in a part of the memory called a “heap” or “GC heap”) for the applications. In one embodiment, an application may include multiple threads. To assist in keeping track of a GC root set per application, an application identifier (application ID) may be associated with each thread belonging to the application. In one embodiment, this may be performed by adding a field to each thread and storing the proper application ID in the field. In another embodiment, a ThreadGroup feature of the Java™ Language may be used to keep track of all the threads of an application.

[0041] In <b>404</b>, a garbage collection operation may be performed on the memory. The garbage collection operation may include determining which of the data structures is in use and then reclaiming data structures that are not in use.

[0042] In <b>406</b>, the root sets may be used to measure the resource consumption for each of the plurality of applications. For example, the amount of memory (i.e., in the GC heap) consumed by each application may be determined by linking data structures in the memory to a particular application based on the reachability of those data structures from the application's root set. In one embodiment, CPU time for a garbage collection operation (GC) may be charged to applications by dividing up the entire time taken based on the GC by freed heap size or number of freed objects for each application.

[0043] In some cases, certain data structures (such as objects) may not be reachable from the ordinary GC root sets even though they are in use. To prevent their unwanted reclamation during GC, these data structures may be registered with an appropriate application ID prior to GC. During GC, these data structures may be linked to the appropriate application as described in <b>406</b>.

[0044] The following pseudo-code is provided as an example of one embodiment of the approach illustrated by FIGS. 3 and 4. <tables id="TABLE-US-00001" num="1"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="21PT" align="left" /><colspec colname="2" colwidth="196PT" align="left" /><thead><row><entry /></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>S[ ]</entry><entry>:= global counters to accumulate sizes of all the objects used</entry></row><row><entry /><entry>on a per-application basis</entry></row><row><entry>N[ ]</entry><entry>:= global counters to count the number of objects reachable on</entry></row><row><entry /><entry>a per-application basis</entry></row><row><entry>FQ[ ]</entry><entry>:= global finalization queue in which to keep finalizable</entry></row><row><entry /><entry>objects on a per-application basis</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217PT" align="left" /><tbody valign="top"><row><entry>mark - pointers</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>a[ ] := all the applications</entry></row><row><entry /><entry>for each application b in a[ ]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>set 0 to S[b]</entry></row><row><entry /><entry>set 0 to N[b]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="21PT" align="left" /><colspec colname="2" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>t[ ]:=</entry><entry>all the threads belonging to the target</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>application b</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>for each thread u in t[ ]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>p[ ] := all the object pointers in the stack</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="84PT" align="left" /><colspec colname="1" colwidth="133PT" align="left" /><tbody valign="top"><row><entry /><entry>frames of u</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>for each pointer q in [p]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="84PT" align="left" /><colspec colname="1" colwidth="133PT" align="left" /><tbody valign="top"><row><entry /><entry>if q is not marked yet</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="105PT" align="left" /><colspec colname="1" colwidth="112PT" align="left" /><tbody valign="top"><row><entry /><entry>do mark-recursively (q, b)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="84PT" align="left" /><colspec colname="1" colwidth="133PT" align="left" /><tbody valign="top"><row><entry /><entry>fi</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>rof</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>rof</entry></row><row><entry /><entry>r[ ] := all the registered objects associated with</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>application b</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>for each object s in r[ ]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>if s is not marked yet</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="84PT" align="left" /><colspec colname="1" colwidth="133PT" align="left" /><tbody valign="top"><row><entry /><entry>do mark-recursively (s, b)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>fi</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>rof</entry></row><row><entry /><entry>for each object o in FQ[b]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>if o is not marked yet</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="84PT" align="left" /><colspec colname="1" colwidth="133PT" align="left" /><tbody valign="top"><row><entry /><entry>do mark-recursively (o, b)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>fi</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>rof</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>rof</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217PT" align="left" /><tbody valign="top"><row><entry>mark-recursively (object q, application b)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>mark q</entry></row><row><entry /><entry>increment S[b] by the size of q</entry></row><row><entry /><entry>increment N[b] by 1</entry></row><row><entry /><entry>r[ ] := Object pointers in the object q</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>If q is a class object and has replicated static</entry></row><row><entry /><entry>fields per-application, include replicated static</entry></row><row><entry /><entry>fields for the target application (b) only</entry></row><row><entry /><entry>for each pointer v in r[ ]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>if v is not marked yet</entry></row><row><entry /><entry>do mark-recursively (v, b)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>fi</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217PT" align="left" /><tbody valign="top"><row><entry>rof</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

[0045] In one embodiment, CPU time for a GC may be charged to applications by dividing up the entire time taken based on the GC by freed heap size or number of freed objects for each application. As described with reference to FIGS. 3 and 4, a GC root set may be maintained for each application. Objects may be linked to an application based on reachability from each application's root set. This approach may solve the second problem identified in the Description of the Relevant Art by making each application responsible for a reasonable proportion of time consumed by the GC. The following pseudo-code is provided as an example of one embodiment of this approach.

[0046] C[ ]:=global counters to accumulate time consumption on a per-application basis <tables id="TABLE-US-00002" num="2"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217PT" align="left" /><thead><row><entry /></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>start-GC</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>s := start time of GC</entry></row><row><entry /><entry>Sbefore[ ] := copy of all of S[ ]</entry></row><row><entry /><entry>Nbefore[ ] := copy of all of N[ ]</entry></row><row><entry /><entry>do GC (may perform the above-discussed procedure for mark-</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>pointers)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>e := end time of GC</entry></row><row><entry /><entry>d := e − s (elapsed time in CPU time)</entry></row><row><entry /><entry>Sdiff[ ] := Sbefore[ ] − S[ ]</entry></row><row><entry /><entry>Ndiff [ ] := Nbefore[ ] − N[ ]</entry></row><row><entry /><entry>if sum of Sdiff is not 0</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>a[ ] := all the applications</entry></row><row><entry /><entry>for each application b in a[ ]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>C[b] := (d * Sdiff[b] / (sum of Sdiff[ ])</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>rof</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>fi</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

[0047] In another embodiment, the line “if sum of Sdiff is not 0” may be replaced by “if sum of Ndiff is not 0”, and the line “C[b]:=(d*Sdiff[b])/(sum of Sdiff [ ])” may be replaced by “C[b]:=(d*Ndiff[b])/(sum of Ndiff[ ])”.

[0048] In one embodiment, finalizer threads may be assigned to each application. Object finalizers may be executed for the finalizer thread for the appropriate application. This approach may solve the third problem identified in the Description of the Relevant Art by limiting GC-related misbehavior to GC of the objects of the misbehaving application itself. The following pseudo-code is provided as an example of one embodiment of this approach. In one embodiment, new-object may be executed when the system creates a new object. Find-executable-finalizer may be executed during the GC. Each application may start a new thread which executes finalizer-loop. <tables id="TABLE-US-00003" num="3"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217PT" align="left" /><thead><row><entry /></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>new-object(class c, size s)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>t := current thread ID</entry></row><row><entry /><entry>a := application ID of thread t</entry></row><row><entry /><entry>o := allocate memory area of size s for a new object o of</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>class c</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>increment S[a] by s</entry></row><row><entry /><entry>increment N[a] by 1</entry></row><row><entry /><entry>if c has finalizer</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>put (o and a) in the has-finalizer queue</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>fi</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217PT" align="left" /><tbody valign="top"><row><entry>FQ[ ] := global finalization queue in which to keep finalizable</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>objects on a per-application basis</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217PT" align="left" /><tbody valign="top"><row><entry>find-application-finalizer</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>f[ ] := all the objects in the has-finalizer queue</entry></row><row><entry /><entry>for each object o in f[ ]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>if o is not marked</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>remove (o and a) from the has-finalizer queue</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="84PT" align="left" /><colspec colname="1" colwidth="133PT" align="left" /><tbody valign="top"><row><entry /><entry>and put o in FQ[a]</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>fi</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>rof</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217PT" align="left" /><tbody valign="top"><row><entry>finalizer-loop</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>while JVM is running</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>a := application ID of this finalizer thread</entry></row><row><entry /><entry>get an object o from finalization queue FQ[a]</entry></row><row><entry /><entry>execute finalizer of o</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>elihw</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

[0049] In one embodiment, static fields of some classes may be shared among applications. To prevent the compromising of the GC security measures summarized above, static fields that would otherwise be shared between applications may be maintained on a per-application basis. The plurality of applications may utilize one or more “original” classes. In other words, the original classes may be shared by a plurality of applications. In one embodiment, new classes may be created to replace the original classes in order to isolate the execution of the applications, such that different applications cannot typically access the same static fields. In one embodiment, only one copy of each original class is maintained, regardless of how many applications utilize it. Classes may be transparently and automatically modified, so that each application has a separate copy of its static fields. In one embodiment, one or more static fields are extracted from one or more original classes utilized by any of the plurality of applications, wherein each of the one or more original classes includes at least one static field. In one embodiment, a separate copy of the one or more static fields is created for each of the plurality of applications, wherein each of the separate copies corresponds to one of the plurality of applications. Creating the separate copy of the one or more static fields may include creating a static field class which includes instance fields corresponding to the one or more static fields, wherein each instance of the static field class corresponds to one of the plurality of applications. In one embodiment, one or more access methods for the one or more static fields may be created. The access methods are operable to access the corresponding separate copy of the one or more static fields based upon the identity of the utilizing or calling application. Creating access methods for the one or more static fields may include creating a single access methods class for each original class which includes the access methods for accessing the extracted fields from the original class. In one embodiment, the method for isolating the execution of the applications is transparent to the utilizing applications. In various embodiments, the extraction of the static fields, creation of the separate copies of the static fields, and creation of the access methods may be performed at run-time or at compilation, and at the source level or the bytecode level.

[0050] Various embodiments may further include receiving or storing instructions and/or data implemented in accordance with the foregoing description upon a carrier medium. Suitable carrier media may include storage media or memory media such as magnetic or optical media, e.g., disk or CD-ROM, as well as transmission media or signals such as electrical, electromagnetic, or digital signals, conveyed via a communication medium such as network <b>108</b> and/or a wireless link.

[0051] While the present invention has been described with reference to particular embodiments, it will be understood that the embodiments are illustrated and that the invention scope is not so limited. Any variations, modifications, additions and improvements to the embodiments described are possible. These variations, modifications, additions and improvements may fall within the scope of the invention as detailed within the following claims.