Stack clearing device and method

[0002] None.

[0003] This invention was not developed in conjunction with any Federally sponsored contract.

[0004] Not applicable.

[0005] 1. Field of the Invention

[0006] This invention pertains to the arts of computer program technologies, program execution methods, and multitask program management techniques. More particularly, this invention relates to program stack management for computer program operating systems and computer program compilers.

[0007] 2. Description of the Related Art

[0008] A computer program process may “call” another process or subroutine to be executed on the same or by the same processor which is executing the “calling” process. When the “call” operation or instruction is executed, the execution of the “calling” process is halted at the point of the “call” instruction, and the “called” process or subroutine is initialized and executed.

[0009] In order to allow the “called” process or subroutine to fully utilize all or part of the processor's computing resources, including the processor's registers, and in order to preserve the context of the “calling” process, a program stack is used. A stack in a computer system is a data structure disposed in a computer-readable memory which dynamically stores variable and processor state information between process calls and returns.

[0010] The stack has a “first-in-last-out” (“FILO”) structure. As data is placed into it, or “pushed onto the stack”, older data is pushed further into the structure. As shown in FIG. 1, a processor (1) has a bi-directional data bus (3) to the stack memory (2). Often, the stack memory and bi-directional data bus is integrated into the processor microchip itself.

[0011] At the assembly language level, most processors have a “push” operation which will copy data from a processor register or memory location to the top of the stack, and will adjust the top-of-stack pointer appropriately. Conversely, a “pop” operation will copy data from the top of the stack into a processor register or memory location, and will adjust the top-of-stack pointer. Some processors implement the stack in an incrementing address fashion, such that “pushes” result in increases in the stack pointer value, and “pops” result in decreases in the stack pointer value. Other processors may take the opposite approach, but achieve identical functionality, including adding data to the bottom of the stack rather than the top of stack. These variations of conventions for stack handling and construction are well understood in the art.

[0012] When the processor executes a “call” operation, an automatic “push” of the contents of the program counter register is made, thereby storing the return address of the calling process on the stack. When the called operation or subroutine executes a “return” operation, an automatic “pop” of the top of the stack contents is made to the program counter, which restores the program counter to the return address of the calling process or routine.

[0013] When a function call is made from a high-level language (“HLL”), such as “C”, the compiler generates assembly language representing the higher-level statements in the HLL to implement the source code into assembly code. When a function or routine call includes arguments to be passed to and returned from the function or routine, the compiler injects not only the assembly “call” opcode into the assembly language, but also a block of code to store the argument values on the stack, as well. This block or sequence of assembly language instructions may include several “pushes”, or special write or store operations, to the stack. Also, in typical HLL compilers, the processor context may be stored on the stack as part of the function or subroutine call operation. The context of the processor typically includes volatile processor register values, such as interrupt control registers, indirect addressing registers and other control registers. A processor-specific example of a volatile register which is stored as part of the context save is the ECX register of an Intel x86 processor.

[0014] When a subroutine is initialized as the result of a “call” operation, it typically sets up a local stack frame for data variables which are local to the subroutine. These local variables are usually addressed by an offset from the beginning of the local stack frame, commonly stored in a “base” register, such as BP or EBP on an Intel x86 processor. In addition, sometimes temporary or transient values are stored on the stack dynamically within the subroutine, rather than including them as part of the local stack frame.

[0015] As shown in FIG. 2, if executing Process A (20) calls Process B, the return address and context of the processor for Process A is pushed (21) onto the stack, and the pointer for the top of the stack is moved to the “top” of the memory containing the Process A context data (203). Further, space is created on the “top” of the stack for Process B's local variables and the top of stack is adjusted (204). Execution of Process B then takes place (22), until Process B calls Process C. At this time, the processor pushes the processor context onto the stack for Process B's current state (23), and moves the top of stack pointer appropriately (205) then the top of stack is adjusted to make room for process C's local variables (206) to make room for Process C's local variables.

[0016] When Process C completes its execution, it will typically execute a “return” operation, which causes the processor to move the top of stack pointer down to Process B's area (202), and to “pop” or read the processor register values from the stack area for Process B (25). The register values are restored to B's state, and the software for Process B is resumed execution (22) from the point of the “call” operation in Process B's instruction code. When Process B completes its execution, a similar “return” operation is made, the top of stack pointer is moved downward (202), and the context for Process A is restored (26) so that Process A's execution (20) can resume and the point of the “call” instruction in Process A's code. This type of general stack operation is well known within the art.

[0017] It well known within the art that the stack can be implemented in computer memory in linear, contiguous memory space, or it may be implemented as a distributed linked list of sections of memory space, while still providing the same functionality as described supra. Additionally, some computer systems “push” data onto the stack in incrementing address values (which results in “pops” decreasing the address values), while other systems “push” data onto the stack in decrementing address values (and “pops” increase the address value). Further, systems which run operating systems may contain the stack management functionality in operating system modules in order to free the application software from stack management, which in simpler systems, stack management may be handled directly by the application software modules. These variations of the pointer management do not affect the FILO operation of the stack, and are merely alternate implementations of the same structure.

[0018] Upon closer examination of this type of stack management process, a potential operation and security problem is apparent. When an application starts execution, the memory used for the stack segment is typically initialized to all zeros. However, after some period of execution, there is stale or non-zero data on the unused portion of the stack Table 1 shows a example calling sequence to be used to illustrate the problem.

[0019] In this example, if Proc A calls Proc B, which then calls Proc C, which then returns to Proc B, and which then returns to Proc A, there is stale information on the unused portion of the stack, such as the return address where Proc A called Proc B, the return address where Proc B called Proc C, any passed in parameters, some local (stack) data variables, etc.

[0020] This is problematic in three ways. First, this may represent a data security issue. After returning from a procedure call, even a call to a procedure in a dynamically linked library, all of the local data variables still exist on the stack. If the called procedure has done any sort of password decryption, built any filenames, etc., there is a potential for this information to be exposed to other processes because the data is still available in the memory.

[0021] Second, the stale data may present confusing trace information when analyzing local variables for program debug and diagnosis. When analyzing trace data where stack snapshots have been taken, or when debugging an application, it is not always clear if the local data variables contain stale data from a previous call, or have actually been initialized by the procedure.

[0022] Third, when analyzing the call-chain for system debug, the stale data may present misleading information. After some period of execution, it is not uncommon to have a developer attempt to determine the sequence of procedures which have called to get the application to the current point of execution. If the compiler saves and restores a base stack pointer (EBP or BP on the Intel X86 platform), then the developer can trace backwards using the base stack pointer. However, some compilers use special optimization (e.g. Visual Age's Optilink calling convention) which do not save/restore the base stack pointer. Also, some assembler language procedures do not save/restore the base stack pointer. If a procedure of this type has been called, then the base stack pointer chain on the stack is broken, and the developer cannot follow the call-chain back to the origin. In this case, the developer will typically perform the time-consuming process of dumping the stack and tediously analyze the stack in the hopes of reconstructing the call-chain. This is both time-consuming and not always successful, particularly in the case of circular or recursive calls (A calls B which calls A), or multiple branches leading to the same node (A calls B which calls C, but A can also call C directly).

[0023] Therefore, there is a need in the art for a method which reduces the likelihood that potentially sensitive data in not residually present in computer stack memory following the execution of a software process. Further, there exists a need in the art for a method which provides accurate and clear data and call-sequence evidence in stack memory to aid in effective program development and system operation debugging and diagnosis.

[0024] The following detailed description when taken in conjunction with the figures presented herein present a complete description of the present invention.

[0025] FIG. 1 shows the prior art relationship of central processing units and stack memory.

[0026] FIG. 2 illustrates the typical process of stack management related to program “call” and “return” operations.

[0027] FIG. 3 shows the general process of compiling, assembling, linking and otherwise producing executable code from source code.

[0028] The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of a preferred embodiment of the invention, as illustrated in the accompanying drawings wherein like reference numbers represent like parts of the invention.

[0029] The invention employs a method which automatically re-initializes the memory used as stack space for a particular process or routine when the memory space is no longer needed by the process or routine. The preferred embodiment utilizes a compiler switch which directs the compiler to inject code (i.e. a “memset” operation) just before the “return” operation of each procedure, in order to re-initialize the stack space which the procedure previously used. This can be done via either intrinsic functions or executable code “in-lining” (e.g. adding a block of executable code into the procedure). Following the “call” operation of the calling routine or process, the compiler injects executable code which re-initializes the stack space which was used to pass the parameters to the called procedure, and which stored the return address to the calling procedure.

[0030] The preferred embodiment of the invention is to realize the stack clearing and re-initialization method as a switch to a software compiler. Prior to starting the compile process, a software designer may elect to have the stack clearing and re-initialization code automatically injected into his or her code by setting an option, or “switch”, in the compiler command file. Compilers often have many switches available to the user for various code execution time optimization options, memory usage and compactness options, and security and privilege options. In an alternate embodiment, the compile option may be implemented as a “#pragma” compiler directive, which allows the software designer to designate specific procedures, modules, or areas of code for which he wishes the stack clearing code to be injected.

[0031] In the preferred embodiment, the default value used to re-initialize the stack space is binary b′0, however, other values may be specified by the switch parameters.

[0032] Through having the stack clearing code injected into the application software by the compiler, application program data security will be maintained because local variables used by sensitive procedures will be overwritten before the procedure returns. Additionally, analysis of the local data variables when analyzing trace data or debugging is eased because they will not contain stale data. Further, analysis of call chain or call sequence is enhanced because only the return addresses in the direct call chain will be on the left stack.

[0033] Turning to TABLE 2, a procedure named VMFreeMem is shown. The procedure includes passed parameters, or arguments, followed by local variable declarations, then executable code (“. . . ”), concluded by a “return” operation. For this example, assembly code compatible with an Intel X86 processor is shown, but it is equally applicable to any microprocessor available in the art. This procedure represents a procedure which leaves stale data on the stack following execution of the return operation, exhibiting the primary problem in the art today.

[0034] TABLE 3 shows an example of code to be modified including the point at which the compiler prior to the return operation. Generally, as most software modules proceed, there are statements to set up the stack frame, followed by actual functional code of the module, concluded with a series of operations to return the stack pointer (in this case several “pops”) to its initial position before executing the “return” operation. Therefore, the code insertion point for the stack clearing method is located just prior to the actual “return” operation, as shown. When returning from the procedure call to VMFreeMem, both the local variables and any data resulting from intermediate pushes and pops during the execution of the called procedure are zeroed-out or re-initialized by the invention. Also, the return address and the parameters that have been pushed are re-initialized or cleared.

[0035] No specific tag or marking in the code is necessary in the preferred embodiment for the insertion point to be recognized. Rather, if the compiler switch is set or if a #pragma is specified, the compiler will search and find all “return” instances, and perform the code insertion.

[0036] Depending on the size of the stack frame to be cleaned, there are two approaches in the preferred embodiment. For a large stack frame, TABLE 4 shows the sequence of operations of the injected code, which uses a “repeat store” operation to clear the stack frame which was used by the procedure. This is most efficient for large stack frames such as stack frames in which large arrays have been stored. For smaller stack frames, a series of simple “move” operations is used to clean the stack frame, as shown in TABLE 5. This is more efficiently executed if the block of stack memory to be cleared is relatively small. The instructions used in TABLES 4 and 5 are carefully chosen because none of them effect the processor flags. If any instructions which modify processor flags are used, the flag states must be saved and restored by the cleaning process, which is less efficient. In certain processors, however, the method may not be implementable without using instructions which modify the processor flags. In such a case, the flag status must be saved and restored appropriately.

[0037] The method shown in TABLE 4 essentially saves the contents of the critical registers used for the procedure to pass back the return parameters to the calling procedure, then calculates the number of words on the stack to overwrite (the stack frame size), executes a “repeat store” operation to overwrite the value of zero (or other clearing value) in the stack frame, and restores the return procedure parameters to the registers and stack. When this code is injected as shown in TABLE 3, it is immediately followed by the “return” operation” leaving the returned parameters in the correct locations for the calling procedure to find and use, but leaving the rest of the stack frame cleaned and free of residual data.

[0038] As shown in TABLE 5, the process for cleaning a small stack frame is essentially the same as the process for cleaning a large stack frame, first saving the contents of the volatile registers which contain the called procedure's return parameters, overwriting the stack frame contents, and then restoring the contents of the volatile registers. However, in this case, a series of simple “move” operations are employed to achieve the overwriting function instead of a “repeat store” operation.

[0039] Turning to FIG. 3, the fundamental compiler and assembler process is shown. High-level source code (30), such as “C” code, is compiled (31) by initially performing syntactical analysis, converting the source code to a standardized or tokenized format, processing any compiler directives, expanding any macros (32), including assembly and other library routines (34) as indicated by the code, and generating an intermediate representation of the code, such as an object file. The compiling process is controlled by various compiler controls (36), such as a “make file” for compiling “C” code and command-line options to the compiling invocation. In the final phase, the various modules of code which are in intermediate form are “assembled” and “linked” (33) to create a run-time image of executable binary code (35) for a specific processor. This general process is followed by most compilers for most languages, and is well understood in the art.

[0040] In the preferred embodiment, the compiler is modified to include the inventive method to insert the stack cleaning code during the early phases of processing the HLL source into intermediate or assembly language form. This has several advantages. First, as all HLL is processed through this state, it allows the invention to be utilized on a wider array of source languages. Second, as assembly code is much more efficient than compiled HLL, the system performance impact of the code insertions is minimized by including the cleaning code as assembly code instead of HLL code or an HLL macro. However, in systems where run-time performance is not a primary concern, the cleaning code can be implemented as macro insertions in HLL. Therefore, the preferred embodiment process of compiling has the following steps:

[0041] (a) perform syntactical analysis on source code;

[0042] (b) convert source code to standard format;

[0043] (c) include library functions and expand macros as indicated by the source code;

[0044] (d) if global stack cleaning switch is selected, perform the following steps for all code, otherwise, perform the following steps for code surrounded by a enable-disable pair of compiler directives:

[0045] (1) scan code for “return” operations;

[0046] (2) for each “return” operation, calculate stack frame size used by examining arguments passed into and returned by the module, module local variable and transient data usage, processor context storage from the calling routine, and any other push and pop operations;

[0047] (3) for large stack frame sizes, insert code just prior to the “return” operation to save volatile registers and return parameters, to overwrite stack frame memory area using a repeated writing operation, and to restore volatile register values.

[0048] (4) for small stack frame sizes, insert code just prior to the “return” operation to save volatile registers and return parameters, to overwrite stack frame memory area using a multiple writing operations, and to restore volatile register values.

[0049] (5) scan code for “call” operations, and for each “call” operation, inject code following the “call” operation which re-initializes the stack space used to pass arguments to and receive returned arguments from the called routine, and to re-initialized the stack memory used to store the return address used by the called routine to return to the calling routine;

[0050] (e) produce intermediate code;

[0051] (f) assemble, link the intermediate code into executable code; and

[0052] (g) output the executable code to a computer-readable medium.

[0053] For step (d), the preferred embodiment includes four types of compiler controls: a global control, a per-procedure control, an enable-disable pair, and a command line option. If a global control, such as:

[0054] #pragma stack_clean_all

[0055] is included in the compiler control file, all software will be processed and modified to include the stack cleaning method where applicable.

[0056] If a per-procedure control, such as:

[0057] #pragma stack_clean_next_procedure

[0058] is included in the compiler control file, only the code of the following procedure will be processed and modified to include the stack cleaning method where applicable.

[0059] If a compiler directive enable-disable control pair, such as:

[0060] is included in the source code, then only code located between the control pair will be processed and modified to include the stack cleaning method where applicable.

[0061] Alternatively, the global control can be set to enable the insertion of the stack cleaning code by a command line parameter upon invocation of the compiler, such as:

[0062] make control_file_name_clean_stack_all

[0063] It will be understood from the foregoing description that various modifications and changes may be made in the preferred embodiment of the present invention without departing from its true spirit, such as the use of alternate programming methodologies or languages, alternate microprocessor architectures, and software development tool sets. It is intended that this description is for purposes of illustration only and should not be construed in a limiting sense. The scope of this invention should be limited only by the language of the following claims.