Abstract:
Systems, methods, and media for testing software patches are provided. The methods include: injecting a software patch into a program; determining a portion of the program modified by the software patch; concurrently executing a first instance of the portion of the program prior to modification by the software patch and a second instance of the portion of the program that has been modified by the software patch; obtaining a first outcome of the first instance and a second outcome of the second instance; comparing the first outcome and the second outcome with a policy associated with the program; and determining whether the software patch has executed correctly based at least in part on the comparison.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a continuation of U.S. patent application Ser. No. 12/302,811, filed Nov. 28, 2008, which is the U.S. National Phase Application under 35 U.S.C. §371 of International Application No. PCT/US2007/012812, filed May 31, 2007, which claims the benefit of U.S. Provisional Patent Application No. 60/809,936, filed May 31, 2006, which are hereby incorporated by reference herein in their entireties. 
     
    
     TECHNICAL FIELD 
       [0002]    The disclosed subject matter relates to systems, methods, and media for testing software patches. 
       BACKGROUND 
       [0003]    Despite decades of research and development efforts for, and the resulting improvement in, software reliability, software defects still account for many system failures. Moreover, methods for retroactively dealing with software defects, such as software patches, can often introduce latent and/or new defects. 
         [0004]    The problem is further exacerbated by the burgeoning popularity of service oriented computing (SOC) systems, such as online commerce, e-mail, Internet Protocol (IP) telephony, and grid computing, and the availability requirements accompanying such systems. In order to update SOC systems to fix existing software defects and vulnerabilities, system administrators need to strike a careful balance between bringing a system down for installing updates and keeping the system available for processing service requests. 
         [0005]    Unfortunately, most SOC systems are long-running servers that amass considerable operational state data and, therefore, the option of launching another machine to test the effects of software patch(es) is limited. 
         [0006]    System administrators can test software patches on a non-production machine and mirror the resulting traffic to the corresponding production system. Because the machines are disjoint, however, there are some drawbacks. First, comparison of two or more mirrored machines requires some level of cross-system synchronization, which, in turn, adds considerable overhead. Second, when dealing with encrypted traffic, a proxy would need to be employed, thereby adding complexity and causing performance degradation. 
       SUMMARY 
       [0007]    Systems, methods, and media for testing software patches are provided. In some embodiments, methods for testing software patches are provided. The methods include: injecting a software patch into a program; running multiple instances of a part of the program containing the software patch; obtaining outcomes of the multiple instances; and determining, using the outcomes, whether the software patch executes correctly. 
         [0008]    In some embodiments, computer-readable media containing computer-executable instructions that, when executed by a processor, cause the processor to perform a method for testing software patches, are provided. This method includes: injecting a software patch into a program; running multiple instances of a part of the program containing the software patch; obtaining outcomes of the multiple instances; and determining whether, using the outcomes, the software patch executes correctly. 
         [0009]    In some embodiments, systems for testing software patches are provided. The systems include: elements for injecting a software patch into a program; elements for running multiple instances of a part of the program containing the software patch; elements for obtaining outcomes of the multiple instances; and elements for determining, using the outcomes, whether the software patch executes correctly. 
         [0010]    In some embodiments, systems for testing software patches are provided. The systems include: an execution environment capable of injecting a software patch into a program and running multiple instances of a part of the program containing the software patch; and a supervision component capable of obtaining outcomes of the multiple instances and determining, using the outcomes, whether the software patch executes correctly. 
         [0011]    Systems, methods, and media for testing software patches are provided. In some embodiments, methods for testing software patches are provided. The methods include: injecting a software patch into a program; determining a portion of the program modified by the software patch; concurrently executing a first instance of the portion of the program prior to modification by the software patch and a second instance of the portion of the program that has been modified by the software patch; obtaining a first outcome of the first instance and a second outcome of the second instance; comparing the first outcome and the second outcome with a policy associated with the program; and determining whether the software patch has executed correctly based at least in part on the comparison. 
         [0012]    In some embodiments, methods for testing software patches are provided. The methods include: injecting a first software patch and a second software patch into a program; determining a portion of the program modified by the first software patch and the second software patch; concurrently executing a first instance of the portion of the program that has been modified by the first software patch and a second instance of the portion of the program that has been modified by the software patch; obtaining a first outcome of the first instance and a second outcome of the second instance; comparing the first outcome and the second outcome with a policy associated with the program; determining which of the first software patch and the second software patch executed correctly based at least in part on the comparison; and terminating at least one of the first software patch and the second software patch based on the determination. 
         [0013]    In some embodiments, systems for testing software patches are provided. The systems include a hardware processor that is configured to: inject a software patch into a program; determine a portion of the program modified by the software patch; concurrently execute a first instance of the portion of the program prior to modification by the software patch and a second instance of the portion of the program that has been modified by the software patch; obtain a first outcome of the first instance and a second outcome of the second instance; compare the first outcome and the second outcome with a policy associated with the program; and determine whether the software patch has executed correctly based at least in part on the comparison. 
         [0014]    In some embodiments, systems for testing software patches are provided. The systems include a hardware processor that is configured to: inject a first software patch and a second software patch into a program; determine a portion of the program modified by the first software patch and the second software patch; concurrently execute a first instance of the portion of the program that has been modified by the first software patch and a second instance of the portion of the program that has been modified by the software patch; obtain a first outcome of the first instance and a second outcome of the second instance; compare the first outcome and the second outcome with a policy associated with the program; determine which of the first software patch and the second software patch executed correctly based at least in part on the comparison; and terminate at least one of the first software patch and the second software patch based on the determination. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0015]      FIG. 1  is a schematic diagram of a system for testing software patches in accordance with some embodiments of the disclosed subject matter. 
           [0016]      FIG. 2  is a simple illustration of a method for testing software patches in accordance with some embodiments of the disclosed subject matter. 
           [0017]      FIG. 3  is an illustrative diagram for injecting software patches into a program in accordance with some embodiments of the disclosed subject matter. 
           [0018]      FIG. 4  is an illustrative diagram of a process for testing software patches for a running service in accordance with some embodiments of the disclosed subject matter. 
       
    
    
     DETAILED DESCRIPTION 
       [0019]    Systems, methods, and media for testing software patches are provided. In some embodiments of the disclosed subject matter, systems, methods, and media are provided for testing software patches inserted into programs in a production machine, such as a production server, prior to system deployment. In some embodiments, software patches are injected while the programs are executing. 
         [0020]    In some embodiments, a binary software patch can be injected into a program, such as a server application, using binary injection techniques so that when an instance of the program reaches targeted program segment(s), multiple instances of the program will be spawned to run the targeted program segment(s) either in parallel or in sequence. In some embodiments, multiple software patches are injected into a program. The output of the multiple instances can then be used to determine whether the patch(es) execute correctly. In some embodiments, software patches are injected while the program is executing. In some embodiments, a validation mechanism of a software patch is also injected along with the software patch. 
         [0021]    In some embodiments, an emulator, such as a virtual machine, is used to run multiple instances of the targeted segment(s) of the program. For example, the multiple instances can run in the emulator either in sequence or in parallel. The emulator, containing a set of logic for supervising running instances, can determine whether an exception indicating a failure is raised while each instance is executed. The emulator can also record the modifications made by each instance to the program memory and keep track of input and/or output transactions that each instance makes. In some embodiments, the emulator is injected into the program using an application programming interface (API) for runtime code patching. 
         [0022]    In some embodiments, an operating system kernel is used to run multiple instances of the targeted segment(s) of the program. For example, the multiple instances can run in sequence or in parallel using a set of kernel functions, referred to as system calls, that can access and modify the memory space of the program. For instance, kernel functions can insert a software patch into the program, spawn and run multiple instances of the program to execute the targeted segment(s), detect and catch exceptions thrown by the multiple instances, and record program state changes. 
         [0023]    Referring to  FIG. 1 , a system  100  includes a dynamic patch execution environment  102 , a program  104  that needs to be updated, a patch  106 , a detection component  108 , and a supervision component  110 . 
         [0024]    Dynamic patch execution environment  102  can be a library of application program interfaces (API) for runtime code patching, such as Dyninst, or various other suitable runtime program instrumentation tools. The API can, for example, attach to program  104 , create a new bit of code, and insert the new code into program  104 . 
         [0025]    Program  104  can continue execution while being modified and, therefore, program  104  does not need to be re-compiled, re-linked, and/or restarted. For instance, the next time the modified program executes the block of code that has been modified, the new code is executed in addition to, or in lieu of, the original code. The API can also change subroutine calls or remove them from program  104 . 
         [0026]    The API can make modifications to both the code and data of program  104 . For example, the API can be used by a programmer, a user, or a system administrator. For instance, a programmer can insert instrumentation code during the development of a software application for subsequent patch testing. 
         [0027]    Dynamic patch execution environment  102  can provide an environment in which patch  106  can be applied to multiple service instances of program  104 . In some embodiments, patch  106  is inserted into program  104  and an instance of program  104  is run such that the part of program  104  containing patch  106  is executed multiple times within the same execution of program  104 . In some embodiments, multiple instances of the part of program  104  containing patch  106  are run in parallel. 
         [0028]    Program  104  can be a software application in a system, such as an SOC system. Program  104  also can be various other suitable programs that require high availability and/or frequent runtime updates or modifications. 
         [0029]    Patch  106  can be a simple logic defect fix, a software update designed to close a vulnerability loophole, and/or any other suitable fix or update. In some embodiments, patch  106  is used to test implementation of new computing techniques. For example, an instance of the implementation of a controversial, unproven computing technique can be tested by placing the implementation into patch  106 . 
         [0030]    Detection component  108  can detect and examine software exceptions thrown by the multiple instances of the part of program  104  containing patch  106 . Supervision component  110  can obtain outcomes of the multiple instances. It can also determine whether patch  106  executes correctly using the outcomes of the multiple instances. Supervision component  110  can be invoked whenever all of the multiple instances reach predefined points in their execution or when software exceptions are detected by detection component  108 . Both detection component  108  and supervision component  110  can be a shared library that can be injected at specific locations in program  104 . 
         [0031]    Referring to  FIG. 2 , a method  200  tests software patches to determine whether the software patches execute correctly. 
         [0032]    As shown, at  202 , a software patch, such as patch  106 , is injected into a program, such as program  104 . In some embodiments, a runtime instrumentation injection technique is employed. For example, Dyninst API can be used to inject instrumentation code into an active server application, such as a financial transaction server. For instance, Dyninst API can be used to insert instrumentation code, referred to as instrumentation trampolines, that can point to the different versions of the software patch under test. Dyninst API also can be used to insert instrumentation trampolines that can point to the instrumentation code that can examine and compare the output of the software patch. 
         [0033]    At  204 , multiple instances of a part of the program containing the software patch are run. In some embodiments, one or more execution threads are created and a function or a procedure is copied into the execution threads, in order for the execution threads to run the function or procedure in parallel. In some embodiments, the execution threads are created and run such that they do not interfere with one another (i.e., each thread is oblivious of the presence of other threads). 
         [0034]    Suppose, for example, a software patch is inserted to modify the logic of a function in the program. When the program execution reaches the function, one or more execution threads can be created. The function can be then copied onto each of the execution threads such that the execution threads can execute the function. 
         [0035]    At  206 , it is determined whether an exception is thrown by any of the multiple instances of the part of the program. In some embodiments, a separate module, such as detection component  108 , is used to catch exceptions thrown by the multiple instances. 
         [0036]    If an exception thrown by one of the multiple instances is detected at  206 , the outcomes of the multiple instances are obtained at  208 . For example, the outcomes of the multiple instances can be one or more characteristics indicative of the end-state of the execution of the multiple instances. In some embodiments, for instance, memory traces of each of the multiple instances are used as the outcomes of the multiple instances. For example, allocation and de-allocation (i.e., deletion) of memory blocks at the library/system call level can be tracked to fingerprint the execution of each multiple instances. 
         [0037]    In some embodiments, input/output (I/O) transactions are used as the outcomes of the multiple instances. For example, a file system view can be duplicated to be attached to each instance of the part of the program. The file system view for each instance of the program can then be compared later to find any inconsistencies. In some embodiments, the program&#39;s external behavior(s) are used as the outcomes of the multiple instances. For example, information printed or displayed on a display screen can be used as the outcomes. 
         [0038]    In some embodiments, the multiple instances are stopped before obtaining the outcomes when an exception is thrown. In some embodiments, only the program instance that has thrown an exception is stopped while the remaining instances of the program continue running In some embodiments, the exception is handled to recover the excepted instance of the program from the failure causing the exception. In some embodiments, detection component  108  handles the exception to recover the excepted instance of the program. 
         [0039]    In some embodiments, the multiple instances are run one instance at a time in sequence. An instance of the part of the program, for example, can run first and its outcome, such as the resulting program state, can be saved before rolling back the program state to run the next instance. Once the program state is restored, the next instance of the program can run and the same process can repeat for subsequent instances. In some embodiments, each saved program state can be used to determine whether the part of the program containing the software patch executes correctly. In some embodiments, the process of running multiple instances is stopped once an instance of the program runs without raising an exception. 
         [0040]    If, however, no exception is detected at  206 , it is further determined at  212  whether all of the multiple instances of the program have reached a predefined synchronization point. For example, the predefined synchronization point can be the end of the software patch injected at  202 . If it is determined at  212  that all of the multiple instances of the program have not reached the synchronization point yet, then  206  is repeated. If, however, it is determined at  212  that all of the multiple instances of the program have all reached the synchronization point, then the outcomes of the multiple instances are obtained at  208 . 
         [0041]    At  210 , it is determined using the outcomes whether the software patch executes correctly. In some embodiments, determining the correctness of the software patch execution is based primarily on policy. For example, a correct base instance or observed normal operation can define the measure of correctness of the software patch execution in a program, such as program  104 . Suppose, for instance, network routers are periodically retrofitted with vulnerability patches. If it is observed that the network routers operate normally after the patches have been inserted, it can be concluded that the patches execute correctly. 
         [0042]    In some embodiments, variations from well-defined invariants and specifications of the program state resulting from execution of the multiple instances can define the measure of correctness of the software patch execution in the program. For example, values returned from one or more functions invoked by the multiple instances can be checked against predefined correct return values from the functions. 
         [0043]    Referring to  FIG. 3 , a diagram  300  illustrates a graphical example of injecting software patches into a program using Dyninst API. 
         [0044]    To instrument a point in a program  302 , one or more instructions in program  302  can be relocated and replaced with a jump to a base trampoline  304 . Base trampoline  304  can be used to modify the original code of program  302  such that the original code can branch into the newly generated code. Base trampoline  304  contains a jump to a mini-trampoline  306  and contains space for the relocated instructions from original program  302 . 
         [0045]    Mini-trampoline  306  contains the instructions for performing the desired functionality stored in a patch  308  as well as for saving and restoring the state information of program  302 , such as the register values and the program counter. For example, mini-trampoline  306  can call an existing function or run a snippet of code that has been created and inserted into program  302  using Dyninst API. 
         [0046]    In some embodiments, more than one mini-trampoline  306  can be inserted at the same point in program  302 . For example, multiple mini-trampolines  306  can be chained together such that the end of one mini-trampoline  306  can branch to the start of the next mini-trampoline  306 , and the last mini-trampoline  306  can branch back to base trampoline  304 , which, in turn, can branch back to program  302 . 
         [0047]    Turning to  FIG. 4 , a diagram of an example  400  of a process for testing software patches for a running service is shown in accordance with some embodiments of the disclosed subject matter. As illustrated, the service can be replicated and multiple instances can proceed concurrently in an execution environment until an event is generated. At that point, all running instances can reach a consensus on the “correct” execution. 
         [0048]    In some embodiments, the process may be implemented by an execution component and a decision component. In some embodiments, the voting component can be implemented as a shared library that can be injected at one or more suitable locations of the program. In some embodiments, the execution component can be invoked at function foo( ) allowing for the simultaneous deployment of two patches or two versions of a patch (or any suitable number of patches). At that time, two more instances of the service can be created. In some embodiments, execution can continue normally for all instances until a predefined point in the execution is reached or an exception is raised. 
         [0049]    In some embodiments, for example, one or more synchronization points can be defined dynamically and serve the purpose of detecting execution and state divergence. In such an example, at a synchronization point, all of the outcomes of the executions can be automatically compared and appropriate action can be taken according to the policy described above. Additionally or alternatively, if an exception is raised, the execution of all concurrent threads can be stopped. The states of the threads can then be compared. In some embodiments, if one of the patched executions is determined to be correct, all of the executions can be terminated. 
         [0050]    Although the invention has been described and illustrated in the foregoing illustrative embodiments, it is understood that the present disclosure has been made only by way of example, and that numerous changes in the details of implementation of the invention can be made without departing from the spirit and scope of the invention, which is only limited by the claims which follow. Features of the disclosed embodiments can be combined and rearranged in various ways.