Patent Description:
<CIT> describes a method of controlling execution of a computer program. The method comprises the following runtime steps: parsing code to identify one or more indirect branches; creating a branch ID data structure that maps an indirect branch location to a branch ID, which is the indirect branch's equivalence class ID; creating a target ID data structure that maps a code address to a target ID, which is an equivalence class ID to which the address belongs; and prior to execution of an indirect branch including a return instruction located at an address: obtaining the branch ID associated with the return address from the branch ID data structure; obtaining the target ID associated with an actual return address for the indirect branch from the target ID data structure; and comparing the branch ID and the target ID.

Solutions to buffer overflow protection provided herein improve upon prior buffer overflow techniques. Aspects provide a software-based buffer overflow solution that has limited memory and processing overhead. Aspects can include maintaining a first address space comprising a plurality of disjoint heap memory allocations, a second, different address space dedicated to storing a bit map defining tag values of the first address space, and a third, different address space dedicated to storing instructions of a software application that, when executed by processing circuitry cause the processing circuitry to perform operations for buffer overflow protection. The operations can include, responsive to a memory write operation that includes writing data to the heap, identifying a first tag value, in the bit map, associated with a first address of the memory write operation in the bit map. The operations can include comparing, for each address after the first address affected by the memory write operation, respective tag values to the identified first tag value. The operations can further include halting execution of the application if any of the respective tag values do not match the first tag value. The bit map can be maintained such that immediately adjacent heap memory allocations are associated with different tag values. Thus, if a tag mismatch occurs, that means the write operation has overflowed to a different buffer.

A method, device, or machine-readable medium for software-based buffer overflow protection can perform operations including responsive to a memory write operation to write data to a heap of a memory, identifying a first tag value associated with a first address of the memory write operation in the bit map, for each address after the first address affected by the memory write operation, respective tag values in a bit map of the memory to the identified first tag value, and halting execution of the application if any of the respective tag values do not match the first tag value. The method, device, or machine-readable medium can further include maintaining by a runtime environment, the bit map (i) sets tag values, in the bit map, for all addresses in the heap memory allocation to the first tag value, and (ii) sets tag values, in the bit map, for a heap memory allocation immediately adjacent to the heap memory allocation, to a second, different tag value.

The method, device, or machine-readable medium can further include, wherein each of the tag values are a single bit. The method, device, or machine-readable medium can further include, wherein the addresses of each minimum memory allocation by the runtime environment include equal tag values associated therewith. The method, device, or machine-readable medium can further include, wherein the runtime stores only a single bit tag value in the bit map for each minimum memory allocation.

The method, device, or machine-readable medium can further include, wherein the write operation is memcpy. The method, device, or machine-readable medium can further include, wherein the operations further comprise, loading and comparing tag values to the first tag value interleaved with data being written such that both comparing and writing happen in parallel. The method, device, or machine-readable medium can further include, wherein multiple tag values are loaded with a single load operation and all of the multiple tag values are compared at once using a single compare.

The method, device, or machine-readable medium can further include storing heap metadata in line with the heap allocation, the heap metadata stored immediately before a heap allocation in the first address space and associated with a different tag value in the bit map than a corresponding heap allocation. The method, device, or machine-readable medium can further include storing heap metadata out of line with the heap allocation.

In the following description, reference is made to the accompanying drawings that form a part hereof, and in which is shown by way of illustration specific embodiments which may be practiced.

These embodiments are described in sufficient detail to enable those skilled in the art to practice the embodiments. It is to be understood that other embodiments may be utilized and that structural, logical, and/or electrical changes may be made without departing from the scope of the embodiments. The following description of embodiments is, therefore, not to be taken in a limited sense, and the scope of the embodiments is defined by the appended claims.

<FIG> illustrates, by way of example, a diagram of an embodiment of a compute device <NUM> with buffer overflow protection. The compute device <NUM> as illustrated includes a runtime environment <NUM>, an application <NUM>, processing circuitry <NUM>, a heap <NUM>, and a bit map <NUM>. The runtime environment <NUM> can facilitate application <NUM> access to the processing circuitry <NUM>. The processing circuitry <NUM> can include hardware that interfaces between the runtime environment <NUM> and the one or more memory devices that include the heap <NUM> and the bit map <NUM>.

The runtime environment <NUM> includes the operating system (OS), a library for programming language support, or other components for managing the heap <NUM> and the bit map <NUM>. The runtime environment manages memory of the application <NUM>, how the application <NUM> accesses variables, and how the application <NUM> interfaces with the OS. The runtime environment <NUM> can perform garbage collection, manage one or more threads, or handle other dynamic features of a programming language.

The application <NUM> is software designed to help people perform an activity. Depending on the activity for which it was designed, an application can manipulate a visual display, text, number, audio, graphic, or a combination thereof. The application <NUM> is typically implemented by processing circuitry <NUM> executing instructions that implement operations <NUM> of the application <NUM>. The operations <NUM> can include a memory write operation <NUM>. In performing a memory write operation <NUM>, the runtime environment <NUM> allocates address space of a memory, referred to as a heap, to hold the data of the write operation <NUM>. Sometimes the memory write operation <NUM> attempts to write to more address space than is allocated to the application <NUM> for the write operation <NUM>. This causes some address space beyond that which was allocated to be overwritten. This is called a buffer overflow. Note that "buffer" in "buffer overflow" means an allocated space of memory. A location in memory that can be allocated for random access is a part of what is called a "heap".

An attacker can exploit a buffer overflow to cause the application <NUM> to perform operations beyond those intended by the developer or user. By intelligently populating the data in the overflow (memory space outside of the allocated space), an attacker can take control of the application <NUM> to cause it to perform operations desired by the attacker.

Others have attempted to address the buffer overflow problem in a variety of ways. Each of the solutions has its own drawbacks.

Hardware memory tagging is currently supported by advanced reduced instruction set computer (RISC) machines (ARM) central processing units (CPUs). In hardware memory tagging, the OS sets up a bit map in which each disjoint <NUM> bits of the bit map data is assigned to <NUM> bytes of a physical address space. Then, when heap allocations are made, the heap allocator chooses a <NUM> bit tag value and places that tag in all bit map locations that correspond to the heap allocation being made and the tag is encoded into an address pointer into the heap. When memory accesses occur, the CPU verifies that the tag encoded into the pointer matches the tags in the bit map for that allocation. If it does not match, then an exception is thrown that indicates the buffer overflow is thrown and the buffer overflow is detected. Hardware memory tagging is not compatible with <NUM>-bit OS because there are not enough free bits in the pointer to implement the hardware memory tagging and there are different problems implementing hardware memory tagging in a <NUM>-bit OS. Another solution is page heap from Microsoft Corporation of Redmond, Washington. Page heap allocates a guard page after each memory allocation leading to memory waste. When a write tries to access the guard page, a permissions exception is thrown and the buffer overflow is detected. Another solution is provided by an address sanitizer (ASAN), which is an opensource memory checking tool. ASAN determines which memory locations are being written to by a write instruction and individually verifies that each memory location is a part of the same allocation before performing a heap write operation. ASAN has a performance degradation that increases linearly with a size of a memcpy.

The solutions provided herein are sometimes called "software memory tagging". Software memory tagging does not use bits of the address pointer as in the hardware memory tagging solution and is compatible with <NUM>-bit and <NUM>-bit software. Software memory tagging solutions consume less heap memory than page heap and, for the most part, the heap layout and density is generally unaffected. Further, instead of checking whether all addresses of a write operation are associated with a same heap allocation up front, software memory tagging enables performance of heap allocation checks in line with a write operation. Software memory tagging has a fixed-cost to compute where in the bit map <NUM> the corresponding tags of the heap <NUM> addresses being written are stored. However, as a size of the amount of data being written increases, the overhead of the tag checking in software memory tagging, as a percentage overhead of total cost approaches zero. For example, consider a memcpy (memory copy) write operation that copies data from one location in memory to another location in memory. For a memcpy of about <NUM> bytes, the overhead is under <NUM>%. For sizes in more typical ranges of <NUM>-<NUM> bytes, the overhead is around <NUM>%.

Operations <NUM> are one or more instructions executed by the processing circuitry <NUM> in performing the functionality of the application <NUM>. The operations <NUM> can include memory write operations <NUM>. A memory write operation <NUM> is an operation that loads data to a memory address in the heap <NUM>. Examples of write operations include memcpy, load, put, among others. A write operation can include read instructions, data manipulation instructions (e.g., shift, multiply, add, concatenate, subtract, divide, among others) as long as the operation includes a write instruction. Memcpy is an example of a write operation that reads data from a first location and loads the data into a second location.

The processing circuitry <NUM> includes the hardware on which the runtime environment <NUM> operates. The processing circuitry <NUM> can include one or more electric or electronic components configured to provide functionality of the compute device <NUM>. The electric or electronic components can include one or more resistors, transistors, capacitors, diodes, inductors, switches, oscillators, amplifiers, power supplies, regulators, analog to digital converters, digital to analog converters, multiplexers, logic gates (e.g., AND, OR, XOR, negate, buffer, or a combination thereof), processing units (e.g., application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), central processing units (CPUs), graphics processing units (GPUs), or the like), memories, or the like.

The heap <NUM> is a portion of memory that is dedicated for allocation to the application <NUM> or another application executing on the compute device <NUM>. The runtime environment <NUM> can manage the heap <NUM>. Managing the heap <NUM> can include allocating memory to the application <NUM>. An allocation <NUM> of memory can have a minimum size. In some current OS implementations, the minimum amount of memory that can be allocated is <NUM> bytes. Other minimum memory allocations are possible, and <NUM> bytes is merely an example.

The bit map <NUM> can include data that provides a high level snapshot of the state of the heap <NUM>. The bit map <NUM> can be managed by the runtime environment <NUM>. Each bit in the bit map <NUM> can represent a specified amount of data in the heap <NUM>. Each single bit in the bit map <NUM> can, for example, represent the minimum memory allocation, which can be <NUM> bytes.

The bit map <NUM> can be structured such that respective bits corresponding to a new memory allocation (with maximum size constrained by a write operation) are all equal to the same value. The bit map <NUM> can be further structured such that all prior allocations immediately adjacent to the new memory allocation (a memory allocation immediately prior if there is one and immediately after the memory allocation if there is one) in the heap <NUM> are associated with respective bits in the bit map <NUM> that are not equal to the respective bits of the new memory allocation. This is illustrated in and discussed in more detail regarding <FIG>.

The allocation <NUM> is a section of memory that the runtime environment <NUM> has allowed the application <NUM> to access in performing its operations <NUM>. The allocation <NUM> has a minimum memory size that is constrained by a minimum allocation that can be performed by the runtime environment <NUM>. As previously discussed, this can be <NUM> bytes. The allocation <NUM> has a maximum memory size that is constrained by a maximum amount of data that can be written to the heap <NUM> using the write operation <NUM> or can be constrained by the programming of the runtime environment <NUM>.

<FIG> illustrates, by way of example, a diagram of an embodiment of a bit map <NUM> mapping of the heap <NUM>. The heap <NUM> includes individual memory addresses <NUM>. The compute device <NUM> can store a specified amount of data (e.g., typical amounts of data are <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, or <NUM> bits) at the memory location corresponding to the address. The runtime environment <NUM> can associate a specified number of addresses <NUM> with an individual tag value (represented by tag <NUM><NUM>). The tag value can be a single bit, such that the value of the tag <NUM> is either "<NUM>" or "<NUM>". Keeping the tag value to a single bit can help minimize an amount of memory required to store the bit map <NUM>. The tag values are used for buffer overflow protection.

As previously suggested, a number (one or greater) of the addresses <NUM> can be represented by a single tag <NUM>. The number of addresses <NUM> can correspond to the minimum memory allocation that the runtime environment <NUM> can make. The allocations <NUM> span multiple addresses that represent an example of the minimum memory allocation. The minimum memory allocation can be <NUM> bytes and <NUM> bit of bitmap data can correspond to <NUM> bytes.

If the runtime environment <NUM> allocates more than the minimum memory allocation in a single allocation, the tags of both of those minimum memory allocations can have their corresponding tag values (the value assigned to the tag <NUM>) set to the same value. <FIG> illustrates a specific bit map mapping that includes multiple minimum memory allocations <NUM> allocated in a single allocation.

<FIG> illustrates, by way of example, a diagram of an embodiment of a specific bit map 116A mapping of the heap <NUM>. Note that a reference number with a suffix is a specific instance of the component that corresponds to the reference number without the suffix. Thus, the bit map 116A is a specific instance of the general bit map <NUM>.

The illustrated heap <NUM> includes a memory allocation <NUM> that spans four minimum memory allocations <NUM>. This is a simple, non-limiting example. To allow for buffer overflow detection, each tag value corresponding to an address immediately before (tag value <NUM>) and immediately after (tag value <NUM>) the address(es) of the allocation <NUM> can be set, by the runtime environment <NUM>, to a different tag value <NUM>, <NUM> ("<NUM>" in this example) than a tag value ("<NUM>" in this example) 332A, 332B, 332C, 332D corresponding to the addresses of the allocation <NUM>. With this configuration, the processing circuitry <NUM> can (i) identify a tag value 332A corresponding to a first address of the write operation <NUM> and (ii) compare tag values 332B-332D corresponding to the rest of addresses of the write operation <NUM> to the identified tag value 332A. If the tag values 332A and one of 332B-332D are not equal, then a buffer overflow will occur if the write operation is allowed to complete. To stop the buffer overflow, the processing circuitry <NUM> or the runtime environment <NUM> can halt, pause, or terminate execution of the application <NUM>.

<FIG> illustrates, by way of example, a diagram of an embodiment of a heap 114B that includes metadata 440A, 440B stored in line with data of respective allocations 330A, 330B and a corresponding bit map 116B. In line means that the metadata 440A, 440B is placed in the heap 114B immediately prior to the allocation 330A, 330B that the metadata 440A, 440B represents. The metadata 440A, 440B is sometimes called a block header. The metadata 440A, 440B includes data regarding the respective allocation 330A, 330B. The metadata 440A, 440B can include a starting address, a size of the allocation (e.g., in terms of bits or bytes, number of addresses, number of minimum memory allocations, starting and ending address, or the like), permissions for accessing the allocation (e.g., indicating an application that has permissions to access the allocation 330A, 330B), whether the allocation is free or allocated, or a combination thereof. The metadata can be used by the processing circuitry <NUM> or runtime environment <NUM> to determine a size of a given allocation.

Note that the first and last minimum memory allocations (sometimes called blocks) can be left unallocated (free). Respective tag values in the bit map <NUM> associated with the first and last blocks can be managed such that they are not equal to tag values associated with immediately adjacent allocations. Whether a portion of the heap <NUM> has been allocated can be managed by the runtime environment <NUM> in a page table. The page table is a data structure used by the runtime environment <NUM> that maps between virtual and physical addresses. Each entry in the page table can include a bit indicating whether the corresponding address is allocated or not.

<FIG> illustrates, by way of example, a diagram of an embodiment of a heap 114C without inline metadata. The metadata for the heap 114C can be stored in an allocation 330A, 330B, 330C, 330D, it just is not required to store the metadata for a given allocation in an immediately prior allocation. The software memory tagging of embodiments is equally to applicable to the heap 114B with metadata 440A, 440B, 440C inline as well as not inline as in the heap 114C.

In an embodiment with inline metadata 440A-440C, the corresponding bit map 116B can include a different tag value for all metadata 440A-440C allocations than is used for all data allocations 330A-330C. In an embodiment with metadata that is not inline, a metadata allocation can have a same or different tag value in the bit map 116C as a corresponding data allocation.

<FIG> illustrates, by way of example, a diagram of a method <NUM> for software-based buffer overflow protection. The method <NUM> as illustrated includes responsive to a memory write operation to write data to a heap of a memory, identifying a first tag value associated with a first address of the memory write operation in the bit map, at operation <NUM>; comparing, for each address after the first address affected by the memory write operation, respective tag values in a bit map of the memory to the identified first tag value, at operation <NUM>; and halting execution of the application if any of the respective tag values do not match the first tag value, at operation <NUM>.

The method <NUM> can further include maintaining by a runtime environment, the bit map (i) sets tag values, in the bit map, for all addresses in the heap memory allocation to the first tag value, and (ii) sets tag values, in the bit map, for a heap memory allocation immediately adjacent to the heap memory allocation, to a second, different tag value. The method <NUM> can further include, wherein each of the tag values are a single bit. The method <NUM> can further include, wherein the addresses of each minimum memory allocation by the runtime environment include equal tag values associated therewith. The method <NUM> can further include, wherein the runtime stores only a single bit tag value in the bit map for each minimum memory allocation.

The method <NUM> can further include, wherein the write operation is memcpy. The method <NUM> can further include, wherein the operations further comprise, loading and comparing tag values to the first tag value interleaved with data being written such that both comparing and writing happen in parallel. The method <NUM> can further include, wherein multiple tag values are loaded with a single load operation and all of the multiple tag values are compared at once using a single compare. The method <NUM> can further include storing heap metadata in line with the heap allocation, the heap metadata stored immediately before a heap allocation in the first address space and associated with a different tag value in the bit map than a corresponding heap allocation. The method <NUM> can further include storing heap metadata out of line with the heap allocation.

<FIG> illustrates, by way of example, a block diagram of an embodiment of a machine <NUM> (e.g., a computer system) to implement one or more embodiments. The machine <NUM> can implement a technique for software-based buffer overflow protection. The compute device <NUM>, runtime environment <NUM>, processing circuitry <NUM>, or a component thereof can include one or more of the components of the machine <NUM>. One or more of the compute device <NUM>, application <NUM>, runtime environment <NUM>, processing circuitry <NUM>, heap <NUM>, bit map <NUM>, method <NUM>, or a component or operation thereof can be implemented, at least in part, using a component of the machine <NUM>. One example machine <NUM> (in the form of a computer), may include a processing unit <NUM>, memory <NUM>, removable storage <NUM>, and non-removable storage <NUM>. Although the example computing device is illustrated and described as machine <NUM>, the computing device may be in different forms in different embodiments. For example, the computing device may instead be a smartphone, a tablet, smartwatch, or other computing device including the same or similar elements as illustrated and described regarding <FIG>. Devices such as smartphones, tablets, and smartwatches are generally collectively referred to as mobile devices. Further, although the various data storage elements are illustrated as part of the machine <NUM>, the storage may also or alternatively include cloud-based storage accessible via a network, such as the Internet.

Memory <NUM> may include volatile memory <NUM> and non-volatile memory <NUM>. The machine <NUM> may include - or have access to a computing environment that includes - a variety of computer-readable media, such as volatile memory <NUM> and non-volatile memory <NUM>, removable storage <NUM> and non-removable storage <NUM>. Computer storage includes random access memory (RAM), read only memory (ROM), erasable programmable read-only memory (EPROM) & electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technologies, compact disc read-only memory (CD ROM), Digital Versatile Disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices capable of storing computer-readable instructions for execution to perform functions described herein.

The machine <NUM> may include or have access to a computing environment that includes input <NUM>, output <NUM>, and a communication connection <NUM>. Output <NUM> may include a display device, such as a touchscreen, that also may serve as an input device. The input <NUM> may include one or more of a touchscreen, touchpad, mouse, keyboard, camera, one or more device-specific buttons, one or more sensors integrated within or coupled via wired or wireless data connections to the machine <NUM>, and other input devices. The computer may operate in a networked environment using a communication connection to connect to one or more remote computers, such as database servers, including cloud-based servers and storage. The remote computer may include a personal computer (PC), server, router, network PC, a peer device or other common network node, or the like. The communication connection may include a Local Area Network (LAN), a Wide Area Network (WAN), cellular, Institute of Electrical and Electronics Engineers (IEEE) <NUM> (Wi-Fi), Bluetooth, or other networks.

Computer-readable instructions stored on a computer-readable storage device are executable by the processing unit <NUM> (sometimes called processing circuitry) of the machine <NUM>. A hard drive, CD-ROM, and RAM are some examples of articles including a non-transitory computer-readable medium such as a storage device. For example, a computer program <NUM> may be used to cause processing unit <NUM> to perform one or more methods or algorithms described herein.

The operations, functions, or algorithms described herein may be implemented in software in some embodiments. The software may include computer executable instructions stored on computer or other machine-readable media or storage device, such as one or more non-transitory memories (e.g., a non-transitory machine-readable medium) or other type of hardware based storage devices, either local or networked. Further, such functions may correspond to subsystems, which may be software, hardware, firmware, or a combination thereof. Multiple functions may be performed in one or more subsystems as desired, and the embodiments described are merely examples. The software may be executed on a digital signal processor, ASIC, microprocessor, central processing unit (CPU), graphics processing unit (GPU), field programmable gate array (FPGA), or other type of processor operating on a computer system, such as a personal computer, server or other computer system, turning such computer system into a specifically programmed machine. The functions or algorithms may be implemented using processing circuitry, such as may include electric and/or electronic components (e.g., one or more transistors, resistors, capacitors, inductors, amplifiers, modulators, demodulators, antennas, radios, regulators, diodes, oscillators, multiplexers, logic gates, buffers, caches, memories, GPUs, CPUs, field programmable gate arrays (FPGAs), or the like).

Claim 1:
A compute device (<NUM>) with buffer overflow protection, the compute device (<NUM>) comprising:
processing circuitry (<NUM>);
a memory (<NUM>) coupled to the processing circuitry (<NUM>), the memory (<NUM>) comprising a first address space storing a heap (<NUM>) comprising a plurality of disjoint heap memory allocations, a second, different address space storing a bit map (<NUM>) defining tag values of the first address space, and a third, different address space storing instructions of a software application (<NUM>) that, when executed by the processing circuitry (<NUM>) cause the processing circuitry (<NUM>) to perform operations comprising:
responsive to a memory write operation to write data to the heap, identify a first tag value associated with a first address of the memory write operation in the bit map (<NUM>);
compare, for each address of the memory write operation after the first address affected by the memory write operation, respective tag values to the identified first tag value (<NUM>); and
halt execution of the application if any of the respective tag values do not match the first tag value (<NUM>).