Hardware based return pointer encryption

A processor, a method and a computer-readable storage medium for encrypting a return address are provided. The processor comprises hardware logic configured to encrypt an instruction pointer and push the encrypted instruction pointer onto a stack. The logic is further configured to retrieve the encrypted instruction pointer from the stack, decrypt the instruction pointer and redirect execution to the decrypted instruction pointer.

BACKGROUND OF EMBODIMENTS

The embodiments are generally directed to semiconductor devices, and more specifically to microprocessors.

2. Background Art

Buffer overflow attacks represent a substantial security threat for many computer systems. During a buffer overflow attack, a user of a computer application exploits certain vulnerabilities in the code which allows the user to insert data into the call stack region of memory. By injecting data into the stack, the user can cause the computer to execute code that compromises the operation of the system and the security of its data. Some approaches to prevent stack buffer overflow attacks involve compilation techniques or other software based methods. However, these methods may add significant overhead to the performance of software and may require recompilation of existing code.

BRIEF SUMMARY OF EMBODIMENTS

There is a need for approaches to prevent buffer overflow attacks which minimize performance overhead and do not require recompilation of existing code.

A processor, a method and a computer-readable storage medium for encrypting a return address are provided. The processor comprises hardware logic configured to encrypt an instruction pointer and store the encrypted instruction pointer onto a stack. The logic is further configured to retrieve the encrypted instruction pointer from the stack, decrypt the instruction pointer and redirect execution to the decrypted instruction pointer.

DETAILED DESCRIPTION OF EMBODIMENTS

The term “embodiments” does not require that all embodiments include the discussed feature, advantage or mode of operation. Alternate embodiments may be devised without departing from the scope of the disclosure, and well-known elements of the disclosure may not be described in detail or may be omitted so as not to obscure the relevant details. In addition, the terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the disclosure. For example, as used herein, the singular forms “a,” “an” and “the” are intended to include the plural fauns as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises,” “comprising,” “includes” and/or “including,” when used herein, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.

Overview

FIG. 1is a block diagram of an illustrative computer processor operating environment100, according to an embodiment. In one example, operating environment100includes a central processing unit (CPU)102and a memory unit150.

In one example, CPU102is a piece of hardware within a computing device which carries out instructions executing computer programs or applications. CPU102carries out instructions by performing arithmetical, logical and input/output operations specified by computer programs or applications. In an embodiment, CPU102performs control instructions that include decision making code of a computer program or an application.

In one example, memory150is a piece of hardware which stores and loads data in response to electronic signals carrying instructions. Memory150may be volatile and non-volatile memory. Examples of volatile memory include a random access memory (RAM). Volatile memory typically stores data as long as the electronic device receives power. Examples of non-volatile memory include read-only memory, flash memory, ferroelectric RAM (F-RAM), hard disks, floppy disks, magnetic tape, optical discs, etc. Non-volatile memory retains its memory state when the electronic device loses power or is turned off. In an embodiment, memory150can be cache memory contained within CPU102. Cache memory is a smaller and faster memory that stores copies of data from recently accessed memory locations from main memory. In an embodiment, processor102reads data from and writes data to memory150as part of program or application execution.

In one example, CPU102includes a set of registers104, an arithmetic logic unit (ALU)112and a control unit114. In this example, the set of registers104includes general purpose registers106, instruction register108, instruction pointer110and stack pointer111.

In one example, instruction pointer110contains the address of the next instruction to be executed by the CPU. In an embodiment, the normal processor instruction cycle involves the control unit114reading an address from instruction pointer110, fetching an instruction from the address in memory150, and storing the instruction in instruction register108. After an instruction is fetched, the value in the instruction pointer110is automatically increased to point to the next instruction in memory. Control unit114then executes the instruction in instruction register108and proceeds to fetch the next instruction pointed by instruction pointer110.

In one example, stack pointer111contains the address of the call stack. A stack is a data structure which contains elements that are added and removed in a last in, first out (LIFO) fashion. When an element is added on the stack, it is said that the element is “pushed” to the top of the stack. When an element is removed from the stack it is said the element is “popped” from the top of the stack. A stack can be implemented by maintaining an address to the top element of the stack, called a stack pointer, in a CPU register. As elements in the stack pushed or popped, the value of the stack pointer is adjusted accordingly. In an embodiment, the memory address to which each subroutine should return control when it finishes executing is stored on a call stack.

FIG. 2depicts memory contents200of a computer system during an illustrative normal execution of a program code by a processor. In this example, the memory contents include a region of memory210containing program code and a region of memory250containing a call stack.

In one example, program code region210contains instructions that are to be executed by processor102. In an embodiment, program code210contains subroutine A code220, which executes subroutine A and which is stored in subroutine A start address222.

In one example, call stack region250stores a stack data structure containing information regarding the subroutines of a computer program. Stack250keeps track of the memory address to which each subroutine should return control when it finishes executing. Stack pointer register111stores stack pointer226which points to the latest element added to stack250(also known as the “top” of the stack), and enables the CPU to access the data in the stack.

In an embodiment, program code region210contains call instruction212, which calls subroutine A. With reference toFIG. 1, when call instruction212is executed, control unit114stores the start address222of subroutine A into instruction pointer110. Consequently, the CPU will begin execution of subroutine A code220. In addition, when call instruction212is executed, return address214will be pushed onto call stack250, along with arguments and other data necessary for execution of subroutine A code220. Pushing data into the call stack comprises storing the data into call stack region250and updating the address in stack pointer111to point to the top of the call stack.

Subroutine A ends when return instruction224is executed, at which point the control unit114uses stack pointer226to calculate return address214from stack250and place return address214into instruction pointer110, causing the CPU to continue execution of program code210at address214.

FIG. 3depicts memory contents300of a computer system during an illustrative execution of a program code by a processor under a stack buffer overflow attack. In this example, the memory contents include a region of memory310containing program code and a region of memory350containing a call stack.

In one example, program code region310contains instructions that are to be executed by processor102(FIG. 1). In an embodiment, program code310contains a subroutine A code320, which is stored in subroutine start address322. Program code region310contains call instruction312, which calls subroutine A.

In one example, call stack region350contains a stack data structure that has been overwritten by a stack overflow attack. In an embodiment, a stack overflow attack is a type of buffer overflow attack which involves a user of a computer program overwriting data in a call stack350in order to change the return address of a subroutine. Call stack data can be overwritten in numerous ways, as will be understood by those skilled in the relevant arts. In an embodiment, a malicious user exploits a vulnerability in the software code to inject malicious code into the system's memory.

In this example, overwritten call stack region350contains a malicious code352and a malicious code start address354.

Malicious code352can be any code. In an embodiment, malicious code352may be a virus, worm, trojan horse, malware, etc. as will be recognized by those skilled in the relevant arts. For example, it could be code that allows a malicious user to gain control over the computer system. Although in the present embodiment malicious code352is stored in the call stack, it should be understood that malicious code352could be any code stored in any region of memory. Those skilled in the art will recognize numerous possible attacks.

In an embodiment, with reference toFIGS. 1 and 3, a stack overflow attack overwrites the original return address314, which pointed to the instruction after call instruction312, with malicious code start address354. As a result, when subroutine A returns, control unit114will retrieve the malicious code return address354and place it into instruction pointer110, causing the execution of malicious code352.

Return Address Encryption

FIG. 4is a block diagram of an illustrative computer processor operating environment400configured to impede stack overflow attacks, according to an embodiment. In one example, operating environment400includes a central processing unit (CPU)402and a memory unit450.

In an embodiment, CPU402includes a set of registers404, an arithmetic logic unit (ALU)416, a control unit418and an encryption/decryption unit420. In an embodiment, the set of registers404includes general purpose registers406, instruction register408, instruction pointer410, key register412, encryption algorithm register413and enable bit414.

In an embodiment, memory450can be cache memory contained within CPU402.

In one example, encryption/decryption unit420performs encryption and decryption of the return address of a subroutine, as further explained below with reference toFIGS. 5 and 6. Encryption/decryption unit420may comprise logic circuitry configured to perform encryption and decryption operations as described herein. In certain embodiments, encryption/decryption unit420may be located within other components of CPU402, such as ALU416. It will be understood by those skilled in the relevant arts that hardware logic to perform the steps in methods500and600can be included in other sections of the CPU. In an example, encryption/decryption operations may be implemented in microcode which implements instructions, as will be further explained herein.

In one example, key register412may be used by CPU402to store an encryption key to be used in encryption and decryption operations. Encryption algorithm register413may be used by CPU402to store a value that indicates which of various encryption algorithms encryption/decryption unit420will employ. Enable bit414may be used by CPU402to indicate whether encryption should or should not be performed. In an embodiment, CPU402may not include key register412, encryption algorithm register413or enable bit414, and their functionality may be implemented in other registers or regions of memory as will be understood by those skilled in the relevant arts. The functionality of key register412, encryption algorithm register413or enable bit414may be implemented in hardware, software or any combination thereof.

FIG. 5presents a flowchart depicting a method500in accordance with an embodiment. In one example method500is an encryption operation performed by CPU402(FIG. 4) in order to impede stack overflow attacks. It is to be appreciated that not all operations need be performed, or be performed in the order shown. An exemplary embodiment is discussed below, in which method500is performed by the system shown inFIG. 4. This is a non-limiting example.

At step502, CPU402fetches from instruction register408(FIG. 4), which in this example contains a call instruction directing CPU402to execute subroutine A. It should be understood that step502could comprise fetching a different type of instruction, depending on the architecture of CPU402. For example, in an ARM architecture, step502may comprise fetching a branch link instruction.

At step504, CPU402reads the instruction pointer register410(FIG. 4). This value is used as the return address from the call instruction, and corresponds to the memory location from which the CPU will fetch after a return from subroutine A.

At step506, encryption/decryption unit420encrypts the return address. The return address is encrypted using a secret key stored in the CPU hardware, for example, in key register412(FIG. 4).

At step508, CPU402pushes the encrypted return address onto the call stack as the return address of subroutine A.

At this point in method500, CPU402can then proceed with the rest of the steps of a call instruction as otherwise explained herein and as will be understood by those skilled in the relevant arts. Although presented as separate steps, the steps of flowchart500can occur simultaneously or in a different order than illustrated here.

FIG. 6shows a flowchart depicting a method600in accordance with an embodiment. For example, method600is a decryption operation performed by CPU402(FIG. 4) in order to impede stack overflow attacks. It is to be appreciated that not all operations need be performed, or be performed in the order shown. An exemplary embodiment is discussed below, in which method600is performed by the system shown inFIG. 4. This is a non-limiting example.

At step602, CPU402fetches from instruction register408(FIG. 4), which in this example contains a return instruction directing CPU402to return from subroutine A.

At step604, CPU402pops the encrypted return address from the call stack.

At step606, encryption/decryption unit420decrypts the return address using the secret key.

At step608, CPU402continues execution at the return address, proceeding with the rest of the steps of a return instruction as otherwise explained herein and as will be understood by those skilled in the relevant arts.

Methods500and600serve as a protection mechanism against buffer overflow attacks. At step606ofFIG. 6, CPU402will apply the decryption algorithm to the return address. If an attacker has overwritten the encrypted return address in the stack with an unencrypted address to a malicious code, this decryption operation will yield an unintended address. Because the attacker does not know the key used to encrypt the return address, the attacker will be unable to reliably redirect program execution to a desired address. At step608ofFIG. 6, the CPU would then redirect execution to the unintended address in memory. Attempting to execute the contents of an unintended memory location as an instruction would likely cause an error. For example, in a 64-bit mode operating system, it is likely the system will issue a general protection fault, since there is a high probability that the address will not be a valid address. An attacker wanting to reliably redirect execution would need to know the encryption key in order to overwrite a return address with the encrypted value of the address of a malicious code.

The encryption and decryption of the return address can be performed in numerous ways as explained in the following paragraphs, and as will be understood by those skilled in the relevant arts. In an embodiment, CPU402can provide various encryption algorithms that can be selected by setting a value in encryption algorithm register413.

In an embodiment, encryption/decryption unit420uses a bijective mapping operation to encrypt and decrypt a return address. For example, encryption/decryption unit420can perform a bitwise XOR of the return address and the key as the encryption algorithm. In a different embodiment, encryption/decryption unit420performs an XOR of the return address and the key, followed by a left-rotate operation using some bits of the key. In an embodiment, the value of the stack pointer could be used as part of the algorithm. In an embodiment, encryption/decryption unit420may use an advanced encryption algorithm such as, for example, Advanced Encryption Standard (AES).

In an embodiment, the encryption algorithm may be chosen based on considerations specific to a particular implementation, taking into account the tradeoffs of the several algorithms with regards to complexity, security and performance. For example, a system in which security is a very high priority and performance is a low priority might be configured to use AES encryption, while a system with high performance requirements might choose an XOR operation. In an embodiment, the encryption algorithm used could be selected depending on a value, or part of a value, of the stack pointer.

In an embodiment, CPU402can be configured to not perform the encryption and decryption operations described with reference toFIGS. 5 and 6by deactivating this feature. In an embodiment, the encryption/decryption feature is deactivated when enable bit414is set to a particular value. In an embodiment, the encryption/decryption feature is deactivated when the key is set to a particular value. For example, if the encryption algorithm is an XOR of the return address and the key, the encryption/decryption will be deactivated if the key is set to 0, since the XOR will not change the value of the return address.

In an embodiment, the operating system activates or deactivates the encryption/decryption feature of CPU402by, for example, setting or clearing enable bit414. In an embodiment, the encryption/decryption feature is automatically activated and deactivated based on a processor state. For example, the feature may be activated based on the privilege of the current mode of operation.

In an embodiment, methods500and600are performed by hardware logic circuitry, by microcode triggered in response to higher level machine code instructions (e.g., call and return instructions), or by some combination of both as will be understood by those skilled in the relevant arts. Microcode is a low level programmable code, typically contained in read-only memory, which comprises micro-instructions used to implement higher level machine code instructions. For example, a call instruction might be implemented in microcode that performs the micro-instructions: 1) read instruction pointer, 2) encrypt instruction pointer, 3) push instruction pointer onto stack and 4) jump to destination address. A return instruction might be implemented in microcode that performs the micro-instructions: 1) pop top of stack, 2) decrypt instruction pointer and 3) jump to instruction pointer.

In an embodiment, the return address is encrypted and decrypted using symmetric encryption with a single key. The key can be stored in key register412. In one example, the key is accessible to privileged code such as, for example, the operating system. In one example, the key is inaccessible to non-privileged code. In an embodiment, key register412is a model-specific register (MSR) that can only be accessed by privileged instructions, as will be understood by those skilled in the relevant arts.

In an embodiment, an operating system running in computer system400runs multiple processes. Every process shares the CPU by running for an amount of time and then yielding execution to another process. When a process yields the CPU to another process, its state must be preserved to enable restoring the process to its previous point of execution. The state of a process includes the value of registers, including pointers to the call stack for the subroutines that run within the process. The state of every process is saved when yielding the CPU, and is restored before execution of the process resumes. In an embodiment, the encryption key is process-specific and part of the process state. For example, every process running in a system may use a different key to encrypt the return addresses of its subroutines. In an embodiment, when the operating system initiates a new process, the operating system determines an encryption key for the new process and writes it to key register412before running the process. When switching processes, the operating system stores the encryption key as part of the state of the yielding process, and writes the encryption key of the new process before running the process.

FIG. 7depicts memory contents700of a computer system during an illustrative execution of a program code by processor402(FIG. 4) under a stack buffer overflow attack, in accordance with an embodiment. In this example, the memory contents include a region of memory710containing program code, a region of memory750illustrating the contents of the call stack before a buffer overflow attack and a region of memory760illustrating the contents of the call stack after a buffer overflow attack.

In one example, program code region710contains instructions that are to be executed by processor402. In an embodiment, program code710contains a subroutine A code720, which is stored in subroutine start address722. Program code region710contains call instruction712, which calls subroutine A.

In one example, call stack region750stores a stack data structure created by processor402containing information regarding the subroutines of a computer program. As explained above with reference toFIG. 5, CPU402encrypts a return address714of subroutine A and stores encrypted return address716in stack750. When routine A terminates by executing a return instruction724, processor402decrypts return address716and redirects execution to return address714.

In one example, call stack region760contains a stack data structure that has been overwritten by a stack overflow attack. Overwritten call stack region760contains a malicious code762and a malicious code start address764.

In an embodiment, a stack overflow attack overwrites the encrypted return address714with malicious code start address764. However, when subroutine A returns, CPU402(FIG. 4) will retrieve the malicious code start address764and decrypt it as described with reference toFIG. 6above. As a result, CPU402will place the result of the decryption, which will be an unintended address in memory, into instruction pointer410. This will cause CPU402to attempt to execute code from an unintended location718in memory, likely causing some kind of fault such as, for example, a general protection fault. Accordingly, unless an attacker knows the encryption algorithm and key used by CPU402, the attacker will at most be able to cause a general error, but will not be able to redirect execution to malicious code762.

Periodic Encryption Key Change

In an embodiment, an operating system running in computer environment400may want to further increase security by periodically changing the encryption key used by processes running in CPU402(FIG. 4). However, changing the encryption key for a process requires the operating system to change the encrypted return addresses for all subroutines in the process. Otherwise, changing the encryption key would cause all subroutines to return to incorrect memory addresses.

FIG. 8shows a flowchart depicting a method800in accordance with an embodiment. For example, an operating system can perform method800to change the encryption key used by a process, according to an embodiment. It is to be appreciated that not all operations need be performed, or be performed in the order shown. An exemplary embodiment is discussed below, in which method800is performed by the system shown inFIG. 4. This is a non-limiting example.

In one example, the operating system walks a call stack and changes all encrypted return addresses for every subroutine. Every encrypted return address is decrypted with an old key and encrypted with a new key.

At step802, the operating system begins to walk the stack by reading an encrypted return address from the stack. The means of locating return addresses in a stack may depend on the specific operating system and the information the operating system maintains regarding subroutines in a process. In one embodiment, the operating system may determine the location of return addresses by using information regarding the size of each subroutine's stack frame, and using this information to calculate the address of the next return address pointer.

At step804, the encrypted return address is decrypted with the old key.

At step806, the address is encrypted with the new key and placed as corresponding subroutine's return address in the stack.

At step808, the operating system determines whether there are subroutines with encrypted return addresses remaining to be re-encrypted. If at step808no subroutines are left to be examined in the stack, the process ends at step810. Otherwise, the process returns to step802to grab the next encrypted return address from the stack.

The embodiment disclosed with reference toFIG. 8is presented for illustrative purposes, and other embodiments will be envisioned by those skilled in the relevant arts and are intended to be encompassed herein.

An operating system may change the encryption key and re-encrypt the return addresses in numerous ways as will be understood by those skilled in the relevant arts. In an embodiment, operating system performs the re-encryption using traditional CPU instructions. In an embodiment, CPU402supports a re-encrypt instruction that decrypts a memory location with a given key and encrypts it with a new key.

Return Address Tracker Register

With reference toFIG. 4, in certain embodiments, a piece of code inside a subroutine might need to read the value of the return address of the subroutine. For example, certain software libraries (e.g., setjmp, thread libraries), which offer programmers the ability to modify the control flow of subroutine execution, will typically access the return address of the subroutine. However, such a piece of code running in computer system400may be unaware that CPU402performs return address encryption as described in the foregoing discussion. A code reading the return address from the stack in system400will retrieve an encrypted return address, but may treat it as if it was unencrypted and likely cause a program error.

FIG. 9depicts an example of a portion of code which would be incompatible with the operation of CPU402as thus far described. In one example, at step902code900calls a subroutine A and at step904reads the encrypted return address and places it into register EAX.

In an embodiment, the CPU may be configured to keep track of the return address pointer in a special register in order to address problems with software code that reads the return address of a subroutine. By keeping track of the return address pointer, the CPU can decrypt the return address before providing it to the software. This feature avoids the need to program software to take into account return address encryption, which would cause performance overhead and require recompilation of existing code.

Return address tracking is effective because of several properties adhered to by the vast majority of compiled software code, namely: 1) software only reads the current frame's return address, 2) software reads the entire return address pointer, and not just part of it, 3) software does not initiate execution operations as part of reading the return address pointer, and 4) software reads the return address pointer in leaf subroutines (a leaf subroutine is a subroutine that does not call any other subroutines). The return address tracking method described in this embodiment will catch reads of a return address pointer initiated by software that matches these criteria. Because these criteria hold true for the majority of software, the return address tracking mechanism herein described is an effective method of returning an unencrypted return address without the need to modify software.

FIG. 10is a block diagram of an illustrative computer processor operating environment1000configured to impede stack overflow attacks, and further configured to track a return address, according to an embodiment. In the example shown, operating environment1000includes a central processing unit (CPU)1002and a memory unit1050.

In an embodiment, CPU1002includes a set of registers1004, an arithmetic logic unit (ALU)1018, a control unit1020and encryption/decryption unit1022. In an embodiment, the set of registers1004includes general purpose registers1006, instruction register1008, instruction pointer1010, key register1012, enable bit1014and return address tracker register (RAT)1016.

In an embodiment, memory1050can be a cache memory contained within CPU1002.

In one example, CPU1002keeps track of accesses to the return address on the stack and provides the correct unencrypted value in response. In one example, RAT1016stores the address of the stack location containing the return address of the subroutine, as will be further illustrated with reference toFIG. 11. By keeping track of the address in the stack where the return address is located, the CPU can detect attempts by software to read the encrypted return address and provide the unencrypted address instead, as will be further illustrated with reference toFIG. 12.

FIG. 11is a flowchart depicting a process1100according to an embodiment. For example process1100is maintaining the return address in the RAT1016in response to a call instruction. It is to be appreciated that not all operations need be performed, or be performed in the order shown.

At step1102, a CPU fetches a call instruction.

At step1104, the CPU reads the return address from instruction pointer1010.

At step1106, the CPU encrypts the return address.

At step1108, the CPU pushes the encrypted address onto the call stack as the return address for the subroutine.

At step1110, the CPU stores in the RAT the address of the location in the stack containing the return address.

Although presented as separate steps, the steps of flowchart1100can occur simultaneously or in a different order than illustrated here.

FIG. 12is a flowchart illustrating a process1200in accordance with an embodiment. In one example, process1200performs a load while permitting reading a return address of a subroutine executing in CPU1002. It is to be appreciated that not all operations need be performed, or be performed in the order shown.

At step1202, the CPU fetches a load instruction, instructing the CPU to load data from a memory address into a register.

At step1204, the CPU compares the address of the load with the address stored in RAT1016.

If the addresses do not match, the CPU moves to step1206and loads the value from the memory at the load address into the destination register of the load and the load instruction is completed at this point.

If at step1206the addresses match, it means that the instruction was trying to read the return address of the process, which is encrypted. The CPU then moves to step1208and reads the value from the address.

At step1210, the CPU decrypts the value using the key in register1012and encryption/decryption unit1022.

At step1212, the CPU completes the load by loading the decrypted value into the destination register of the load, thereby providing the decrypted return address to the destination register of the load.

Although presented as separate steps, the steps of flowchart1200can occur simultaneously or in a different order than illustrated here.

FIG. 13is a flowchart illustrating a process1300in accordance with an embodiment. For example, process1300is for resetting RAT1016in response to a return instruction. It is to be appreciated that not all operations need be performed, or be performed in the order shown.

At step1302, a CPU fetches a return instruction, instructing the CPU to return from a subroutine.

At step1304, the CPU pops the encrypted return address from the call stack.

At step1306, the CPU decrypts the encrypted return address.

At step1308, the CPU redirects execution to the return address.

At step1310, the CPU sets RAT1016to 0. In an embodiment, 0 is an invalid memory address, which should not cause the CPU to match the load address with the address in RAT1016. Clearing RAT1016to 0 after a subroutine prevents an inadvertent RAT match by a load executing outside of a subroutine.

Setting RAT1016to an invalid address after returning from a subroutine works because, as previously stated, most subroutines that access a return address pointer are leaf subroutines. Therefore, if a subroutine calls another subroutine, the calling subroutine would typically not attempt to access its return address pointer. However, there might be some instances of software in which this property does not hold true. In order to support software in those cases, in an embodiment, the CPU restores the value of RAT1016to the value it had prior to the current subroutine call instead setting RAT1016to an invalid address. If the calling subroutine attempts to load its return address pointer after the called subroutine returns, a RAT match will occur as described in step1206ofFIG. 12, and the decrypted return address would be loaded.

In an embodiment, the CPU can keep track of the previous subroutine's address by calculating the difference between the current stack pointer and the current value of RAT1016. The CPU can store this delta in the stack. In an embodiment, the memory address size of certain applications is larger than the memory word size. For example, in 64-bit applications running on an x86 architecture the upper 16 bits of the return address pointer in the stack are typically not used. Y

In an embodiment, the delta between the current stack pointer and the current value of RAT1016is stored in the upper 16 bits of the return address pointer.

FIG. 14shows the contents of exemplary call stack1400, storing a delta between return address pointers, in an embodiment. Call stack1400includes frame data1402, encrypted return pointer1404and delta1406, associated with a first subroutine. Call stack1400further includes subroutine A data1408, encrypted return pointer1410, and delta1412, associated with a second subroutine A.

When the CPU executes a call instruction, as described with reference toFIG. 11above, at step1108the CPU can calculate the delta1406by calculating the difference between the stack pointer and the value in RAT1016. With reference toFIG. 14, when the CPU calls subroutine A, it can place delta1412in the upper 16 bits of the encrypted return address1410. In an embodiment, the CPU encrypts the delta before placing it in the stack.

When the CPU fetches a return instruction, as described with reference toFIG. 13above, instead of resetting RAT1016to 0 at step1310, the CPU can use the delta to compute the address of the previous return address pointer and restore this address to RAT1016. In an embodiment, when returning from subroutine A at step1310, the CPU subtracts delta1412from the current value of RAT1016and places the result in RAT1016.

In an embodiment, methods1100,1200and1300are performed by hardware logic circuitry, by microcode triggered in response to higher level machine code instructions, or by some combination of both as will be understood by those skilled in the relevant arts.

Modern processors, in order to take advantage of parallel processing capabilities, may execute instructions out of order instead of sequentially. It would be advantageous for a processor to support return address encryption without adding any performance burden to out-of-order execution.

In an embodiment, a processor may try to execute load and store instructions out of order. However, executing a load early may result in loading data that has not yet been modified by a store instruction that occurs logically later in the program sequence. Conversely, executing a load late may result in loading data that has been modified by a store instruction that was executed out of order, but that was supposed to occur logically after the load in the program sequence. Therefore, a processor needs to keep track of the correct data values when performing out-of-order loads. Those skilled in the relevant arts will recognize numerous ways a processor can manage out-of-order instructions.

FIG. 15is a block diagram of an illustrative computer processor operating environment1500configured to perform out-of-order load and stores, according to an embodiment. In this example, operating environment1500includes a central processing unit (CPU)1502and a memory unit1550.

In one example, CPU1502includes a set of registers1504, an ALU1506, a control unit1508, a store queue content-addressable memory (CAM)1510and an encryption/decryption unit1512.

In an embodiment, memory1550can be cache memory contained within CPU1502.

In one example, store queue CAM1510serves as a temporary repository of store instructions that are executed out of order. A content-addressable memory is a special type of memory where the user provides a data word and the memory searches its entire contents to see if that data word is stored anywhere in it. In an embodiment, a processor stores the destination address and data of a store instruction in store queue CAM1510before committing the data to memory1550. When the CPU fetches a load instruction, it searches store queue CAM1510for the address of the load. If the CPU finds a pending store whose address matches the address of the load, the CPU forwards the data value of the store to the destination register of the load. This process is known as “store-to-load forwarding.” Once a store is committed to memory1550, the CPU removes the store entry from store queue CAM1510.

FIG. 16depicts instruction formats for store instructions and load instructions supporting store-to-load forwarding and return address encryption, according to an embodiment. The formats include a store instruction1610, a call/return-type store instruction1620, a load instruction1630and a call/return-type load instruction1640.

In one example, store instruction1610includes a store instruction code1612, a source register1614, and a destination address1616. Store instruction code1612indicates to the CPU that the instruction is a regular store instruction. Source register1614indicates the register that contains the data that is to be stored in memory. Destination address1616indicates the address in memory where the data is to be stored.

In one example, store instruction1620includes a call/return-type store instruction code1622, a source register1624and a destination address1626. When CPU1502fetches a call instruction, it executes a store instruction that stores a subroutine's stack data into a call stack. In an embodiment, such stores would be marked as a call/return type store by using call/return-type store instruction code1622. Any other store instruction would be marked as a regular-type store and use store instruction code1612.

In one example, load instruction1630includes a load instruction code1632, a source address1634, and a destination register1636. Load instruction code1632indicates to the CPU that the instruction is a regular load instruction. Source address1634indicates the memory address that contains the data that is to be loaded into a register. Destination register1636indicates the register where the data is to be loaded.

In one example, load instruction1640includes a call/return-type load instruction, code1642, a source address1644and a destination register1646. When CPU1502fetches a return instruction, it executes a load instruction that loads a subroutine's return address into an instruction pointer. In an embodiment, such loads would be marked as a call/return-type load by using call/return-type load instruction code1642. Any other load instruction would be marked as a regular-type store and use load instruction code1632.

FIG. 17shows a flowchart depicting a method1700in accordance with an embodiment. For example, method1700is a process of completing a load instruction in a processor supporting store-to-load forwarding and return address encryption, according to an embodiment. It is to be appreciated that not all operations need be performed, or be performed in the order shown. An exemplary embodiment is discussed below, in which method1700is performed by the system shown inFIG. 15. This is a non-limiting example.

At step1702, a CPU fetches a load instruction.

At step1704, CPU checks store queue CAM1510to verify if there is a logically prior store that matches the source address of the load. If store queue CAM1510does not contain a matching address, the CPU loads the value from memory1550using the same method explained with reference to memory1050inFIG. 12above, checking if the address matches RAT1016and if so decrypting the value before writing it to the destination register. Otherwise, if at step1704the CPU finds a store with a matching address in store queue CAM1510, the CPU compares the instruction code field to determine the type of the store and the load instructions at step1708. If the types of the instructions match, the CPU performs a store-to-load forward of the data from store queue CAM1510to the destination register of the load, without accessing memory1550.

If the types of the instructions do not match, the CPU blocks the load instruction until the matching store is committed to memory1450, as illustrated in steps1712and1714.

Once the store in store queue CAM1510is committed to memory1550, the CPU loads the value from memory1550at step1716using the same method explained with reference to memory1050inFIG. 12above, checking if the address matches RAT1016and if so decrypting the value before loading it. It should be noted that if the store corresponds to a call instruction, RAT1016will be updated at the time the store is committed to memory1550, in accordance with the method illustrated inFIG. 11. Therefore, after the store commits the CPU can reliably check RAT1016and load the correct value. Although presented as separate steps, the steps of flowchart1700can occur simultaneously or in a different order than illustrated here.

In an embodiment, method1700is performed by hardware logic circuitry, by microcode triggered in response to higher level machine code instructions, or by some combination of both as will be understood by those skilled in the relevant arts.

FIG. 18depicts an exemplary program sequence illustrating the operation of method1700in an embodiment. AlthoughFIG. 18depicts store instructions on the left and load instructions on the right for illustrative purposes, instructions are executed sequentially from top to bottom.

At program step1802, a call instruction is executed, which in turn causes a call/return-type store (of the encrypted return address) to address X to be executed. This call/return-type store instruction can be placed in store queue1510.

At program step1804, a regular-type store to address X+4 is executed. This regular store instruction can be placed in store queue1410.

At program step1806, a regular-type load to address X+4 is executed. The CPU can check store queue1510and match the address X+4 of the load with the previous regular-type store to X+4. Since both are regular-type, the CPU can complete the load by forwarding the store value from store queue1510to the load register.

At program step1808, a call instruction is executed, which in turn causes a call/return-type store (of the encrypted return address) to address X+8 to be executed. This call/return-type store instruction can be placed in store queue1510.

At program step1810, a regular-type load to address X+8 is executed. The CPU can check store queue1410and match the address X+8 of the load with the previous call/return-type store to X+8. However, since the store is a call/return-type store and the load is a regular-type store, the CPU can block the load until the call/return-type store to X+8 commits to memory1550. In this way, the CPU avoids missing a potential RAT1016match and thus forwarding an encrypted return address to the load. Once the call/return-type store to X+8 commits to memory1550, the load can complete by reading the address from memory1550, which can cause a RAT1016match, as described with reference toFIG. 12above. Therefore, the CPU can decrypt the return address before loading it, as described with reference toFIG. 12above.

At program step1812, a regular-type store to X+12 is executed. This regular store instruction can be placed in store queue1510.

At program step1814, a return instruction is executed, which in turn causes a call/return-type load (of the encrypted return address) of X+8 to be executed. The CPU can check store queue1510and match the address X+8 of the load with the previous call-type store to X+8. Since both instructions are of the same call/return type, the CPU can forward the encrypted return address directly from store queue1510to the return. Because the return instruction can decrypt the encrypted return address as described with reference toFIG. 13above, there is no need to check RAT1016or decrypt the address before the load.

At program step1816, a regular-type store to address X+8 is executed. This regular store instruction can be placed in store queue1510.

At program step1818, a regular-type load to address X+8 is executed. The CPU can check store queue1510and match the address X+8 of the load with the previous regular-type store to X+8. Since both are regular-type, the CPU can complete the load by forwarding the store value from store queue1510to the load register.

State Preservation Across Interrupts and Exceptions

In an embodiment, the processor may receive an interrupt or a processor generated exception. An interrupt is a signal or instruction to the processor that indicates an event which requires immediate attention. An exception is an anomalous or exceptional situation occurring during the execution of a program and which requires special handling such as, for example, a page fault. A processor receiving an interrupt or exception signal must save the state of the subroutine onto the stack and service the interrupt or exception by calling an interrupt or exception handler. Once the interrupt or exception is serviced, the CPU must then restore the state of the interrupted subroutine before continuing its execution.

FIG. 19shows a flowchart depicting a method1900in accordance with an embodiment. For example, method1900is process of preserving a state of a return address tracker register, e.g., RAT1016(FIG. 10) across an interrupt. It should be understood that the same concepts are equally applicable to an exception. It is to be appreciated that not all operations need be performed, or be performed in the order shown. An exemplary embodiment is discussed below, in which method1900is performed by the system shown inFIG. 15. This is a non-limiting example.

At step1902a CPU receives an interrupt signal.

At step1904, the CPU pushes value in RAT1016onto the call stack.

At step1906, the CPU services the interrupt by executing an interrupt handler subroutine.

Although presented as separate steps, the steps of flowchart1900can occur simultaneously or in a different order than illustrated here.

FIG. 20shows a flowchart depicting a method2000in accordance with an embodiment. For example, method2000is a process of restoring a state of return address tracker register, e.g., RAT1016, after an interrupt is serviced. It should be understood that the same concepts are equally applicable to an exception. It is to be appreciated that not all operations need be performed, or be performed in the order shown. An exemplary embodiment is discussed below, in which method2000is performed by the system shown inFIG. 15. This is a non-limiting example.

At step2002, a CPU fetches a return from interrupt instruction.

At step2004, the CPU pops the value of a RAT from the call stack and loads the value into RAT1016.

At step2006, the CPU returns from the interrupt and resumes execution of the interrupted program code.

Although presented as separate steps, the steps of flowchart2000can occur simultaneously or in a different order than illustrated here.

In an embodiment, methods1900and2000are performed by hardware logic circuitry, by microcode triggered in response to higher level machine code instructions, or by some combination of both as will be understood by those skilled in the relevant arts. In an embodiment, the value of RAT1016is made accessible to an operating system. When servicing an interrupt or exception, the operating system may save the state of the value of RAT1016and restore it across the interrupt or exception.

Embodiments can be accomplished, for example, through the use of general-programming languages (such as C or C++), hardware-description languages (HDL) including Verilog HDL, VHDL, Altera HDL (AHDL) and so on, other available programming and/or schematic-capture tools (such as circuit-capture tools), or hardware level instructions implementing higher-level machine code instructions (e.g., microcode). The program code can be disposed in any known computer-readable medium including semiconductor, magnetic disk, or optical disk (such as CD-ROM, DVD-ROM). As such, the code can be transmitted over communication networks including the Internet and internets. It is understood that the functions accomplished and/or structure provided by the systems and techniques described above can be represented in a core (such as a CPU core and/or a GPU core) that is embodied in program code and may be transformed to hardware as part of the production of integrated circuits.

In this document, the terms “computer program medium” and “computer-usable medium” are used to generally refer to media such as a removable storage unit or a hard disk drive. Computer program medium and computer-usable medium can also refer to memories, such as system memory and graphics memory which can be memory semiconductors (e.g., DRAMs, etc.). These computer program products are means for providing software to a computer system.

The embodiments are also directed to computer program products comprising software stored on any computer-usable medium. Such software, when executed in one or more data processing devices, causes a data processing device(s) to operate as described herein or, as noted above, allows for the synthesis and/or manufacture of computing devices (e.g., ASICs, or processors) to perform embodiments described herein. Embodiments employ any computer-usable or -readable medium, and any computer-usable or -readable storage medium known now or in the future. Examples of computer-usable or computer-readable mediums include, but are not limited to, primary storage devices (e.g., any type of random access memory or read-only memory), secondary storage devices (e.g., hard drives, floppy disks, CD ROMS, ZIP disks, tapes, magnetic storage devices, optical storage devices, MEMS, nano-technological storage devices, etc.), and communication mediums (e.g., wired and wireless communications networks, local area networks, wide area networks, intranets, etc.).

The breadth and scope of the embodiments should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.