CN108491694A - A kind of method of dynamic randomization defence Cache attacks - Google Patents

Abstract

The invention belongs to computer system security fields, and in particular to be directed to Cache attack patterns FLUSH+RELOAD, it is proposed that a kind of defence method of the system level based on dynamic randomization can repeat randomization code, stack, heap.It is based on Sharing Memory Realization that Cache, which attacks FLUSH+RELOAD, and process is as shown in Figure 1.The method of the present invention includes：In terms of code randomization, code, refinement randomization granularity are randomized as unit of function；In terms of stack randomization, by filling the size in space, filling the position in space and being randomized the abundant randomization for being designed to ensure that stack at moment；In terms of heap randomization, the distribution of heap space is no longer regular when a kind of new heap space randomized technique being used to make operation.This method being capable of dynamic randomization defence Cache attacks.

Description

A method of dynamic randomization to defend against Cache attack

technical field

The invention belongs to the field of computer system security, and in particular relates to a method for dynamic randomization defense against Cache attacks.

Background technique

With the development of network technology, people have paid more and more attention to computer security. Various security vulnerabilities such as system intrusion, information theft, and viruses will cause great losses to individuals and society. In recent years, researchers have proposed a way to use the physical information leaked during the operation of cryptographic equipment, such as electromagnetic radiation, power, time, etc., as a channel for cryptographic analysis, and this attack method is called side-channel attack, also known as Side channel attack. Cache attack is a side-channel attack that seriously threatens system security, and involves mainstream computer systems in various fields such as servers, desktops, and embedded systems. At present, side-channel attacks based on Last-level cache (LLC) have the characteristics of high bandwidth and low noise. At the same time, because the last-level cache is inclusive and multi-core sharing, it can be realized without interrupting the program. Or a specific Cache line to attack. In this environment, Cache attacks are on the rise and the attack techniques used by attackers are more "sophisticated". With the large-scale popularization of cloud services and virtualization, Cache attacks will be more lethal in the future. At the same time, cache attacks are gradually penetrating into our daily applications, such as extending to the trusted environment of smartphones, posing a great threat to the security of the operating system.

The cache structure of modern CPUs is generally divided into three layers, which are L1, L2 and L3 caches. L1cache is occupied by each core separately and is the closest to the CPU. It has the smallest capacity and the fastest speed. It is generally divided into Data Cache (data cache ) and Instruction Cache (instruction cache). The L2cache is larger and slower. Generally, each core has an independent L2cache. L3cache is the largest level in the three-level cache, and it is also the slowest level. Generally, it is shared by all cores in multi-core CPUs. When the CPU starts executing a task, it first goes to L1 to find the data it needs, then to L2, and then to L3. If it exists (hit), the data is directly returned without going through the memory; if it does not exist (failure), the corresponding data in the memory is first loaded into the cache, and then returned to the processor.

To facilitate the description of the attack process, the following are some basic definitions of operating system-related content:

Shared memory: A very efficient way to share and pass data between two running processes. The memory shared between different processes is usually the same piece of physical memory. Processes can map the same shared memory into their own address space. There is a memory optimization mechanism in the operating system: for a shared library, the operating system will map the same piece of physical memory storing the library into the address space of each application.

mmaps: It is a memory mapping function that enables processes to share memory by mapping the same ordinary file.

So far, there are mainly four cache attack methods: FLUSH+RELOAD, EVICT+RELOAD, PRIME+PROBE, and FLUSH+FLUSH. Among them, FLUSH+RELOAD is implemented based on shared memory and is divided into three stages. The process is shown in Figure 1. In the Flush phase, the target process and the attacker process share pages, that is, the attacker induces the target process to apply the memory mapping function mmaps to the target executable program, allowing it to enter the virtual address space of the attacker process. Complete memory sharing of mapped files. The attacker process then monitors a particular cache line and wipes its contents from the cache. The Wait phase waits for the victim to access the shared memory, and then, in the Reload phase, the attacker reloads a specific shared memory block. If in the Wait stage, the target process accesses the specified memory block, then this memory space will be recorded in the Cache, because accessing the data in the Cache is very fast, so the reloading process in the Reload stage only takes a short time. Otherwise, if the target process does not access the specified memory space, the attacker needs to obtain data from the main memory, because accessing data in the main memory is very slow, so it takes more time in the Reload phase. Therefore, the attacker can determine whether the victim accessed a specific memory block during the observation period based on the length of the secondary access. This method allows an attacker to determine which specific instructions were used and which data was accessed by the target program.

At present, the defense measures proposed for the cache attack FLUSH+RELOAD, such as deleting the clflush instruction, disabling shared memory, and using fully associative address mapping between cache and main memory, are not satisfactory. Therefore, the present invention proposes a dynamic randomization system to fully randomize the code, stack, and heap, so as to invalidate the information obtained by the attacker as much as possible.

Contents of the invention

Aiming at the Cache attack mode FLUSH+RELOAD, the present invention proposes a system-level defense method based on dynamic randomization, which can dynamically randomize program functions, stack frames and heaps.

The address space of a process consists of: objects generated by ELF's Executable File and Shared Object File: code segments, static data segments, dynamic shared libraries, etc., and dynamic objects: heaps and stacks generated and changed at runtime. The overall randomization of objects with a relatively large address space is called base address randomization, while the randomization of finer-grained address space objects, such as individual functions and stack frames in a code segment, has a stronger randomization effect.

The current address space randomization technology (address space randomization) is to make the layout of the process virtual space in a random position, so as to reduce the possibility of being attacked. This scheme has too large randomization granularity, low randomness, and only Can randomize defects such as virtual addresses. By refining the randomization granularity, postponing the randomization moment to runtime, and randomizing the physical address, the defects of the existing randomization schemes are eliminated.

The method enhances the defense capability from three aspects: first, for the problem of coarse randomization granularity, the code randomization of the present invention takes function as the granularity, and stack space randomization takes function stack frame as the unit. Second, considering the randomization time problem, one of the characteristics of the current randomization mechanism is that when the system starts, the randomization will take effect, and we postpone the randomization time until each function is running. The closer the timing of randomization is to the runtime, the better the random effect can be obtained. However, to randomize an address space object at runtime, it is first necessary to analyze how the object is referenced in the address space. For the address space object heap and stack that are only established at runtime, the references therein are all made through absolute addresses. If the location of these objects is moved at runtime, these references need to be modified. In the implementation, the system uses a migration table to record this information, making this randomization feasible. Third, randomize physical addresses to reduce the likelihood of an attacker successfully guessing spatial locations.

Here are some basic definitions of this randomization system:

Symbol table: In a compiled program, the symbol table is used to store attribute information about identifiers that appear in the programming language.

Constructor: It is a method that is mainly used to initialize the object when creating the object, that is, to assign values to the object member variables. The compiler generally provides a default constructor, but this default constructor does not take parameters.

libc: It is the ANSI C function library under Linux. ANSI C is the basic C language function library, including the most basic library functions of the C language.

Constructor: It is used to perform initialization when creating an object. When an object is created, the system will perform default initialization for the instance of this object. If you want to change this default initialization, you can implement it through a custom constructor.

Stack frame: The CPU dynamically allocates memory in units of functions. Every time a sub-function is called, a certain space will be allocated in the stack to store its operation information. This space is called the stack frame of the function. The stack frame of a function usually includes: function parameters, return address, base address register (previous frame pointer) of the previous function, local variables, etc.

Bitmap: It is a simple vector of a single Bit, and each Bit corresponds to a word of memory or a specific size.

The dynamic randomization system can run on x86, x86_64 and PowerPC architectures, most of the implementation details are the same. The system can efficiently repeat the randomized code, stack, and heap, so that when the attacker reloads the data in the shared memory during the Reload phase, the spatial position of the data has changed. The final effect is shown in Figure 2. The specific design Details include the following:

1. Code randomization

This method uses function as the granularity to randomize the code, which is reflected in the following four aspects: First, the function uses functions such as malloc, calloc, and realloc to allocate memory randomly on the heap. Second, each conversion function has a migration table, which contains some migration information, followed by the function code. At the same time, the migration table does not exist in the binary form compiled by the system, but is created at runtime. Therefore, the attacker wants to use the migration table as a breach point, and the method of obtaining function-related address information is invalid. Third, because the size of the function is not specified in the symbol table of the program, the system uses the address of the next function to determine the end point of the current function. Fourth, functions refer to adjacent offset tables by using relative offsets. This means that two randomly placed copies of the same function will not share the same migration table. The above four points make the function address impossible to guess during the running of the program. The randomization process is shown in Figure 3, including:

(1) Initialization phase. At compile time, the dynamic randomization system replaces the libc constructor of the operating system module with its own constructor. At startup, the constructor registers the functions and constructors of the module from the original program, and then executes the rewritten constructor for initialization. The main function defined when the system is running rewrites the beginning of each relocation function with a breakpoint, that is, a trap instruction is placed at the beginning of each function to trigger the work of the migration table. When the trap function is called , it migrates on demand, as shown in (a) in Figure 3.

(2) Function migration stage. Each randomization function has an adjacent migration table, the contents of which are pointers to all referenced global variables and functions, as shown in (b) in Figure 3. When the trap function executes, the dynamic randomization system receives a SIGTRAP signal at runtime and migrates the function. This process is divided into the following three stages:

1) The system applies for a large enough memory block from the code heap, and copies the main part of the function to it.

2) Correspondingly, the migration table of the function is also migrated to a new location. The system migrates the function to a new location by replacing the trap instruction with a jump instruction, which is equivalent to rewriting the original base address of the function.

3) The system adds the function at the new location to the active function set, and the function at the old location becomes invalid.

(3) Repeat the randomization progress stage. As shown in (c) in Figure 3. The system randomizes the function again every fixed time period, the default is 500ms. When this time expires, the system places a trap instruction at the beginning of each active function and restarts the randomization process when the next trap instruction executes.

(4) Repeat the randomization completion phase. When the trap function is executed, the system puts the memory used by the active function into a collection, and then traverses the stack. In the active function collection, if an object inside is pointed to by the return address on the stack, then the object will be Marked, and the unmarked objects in the collection will be released to the heap, for example, the ex3' function memory is released as shown in (d) in Figure 3, and the remaining functions such as ex1' will be released once they are not on the stack. Will be released after some future randomization process. Any subsequent calls to the function ex1 will point to the new location of the migration function ex1″.

2. Stack randomization

The traditional stack generates adjacent stack frames sequentially with the call of the function, in which the position of the return address is constant. Therefore, there is still a similarity in the program for a long time, which has the risk of being broken, as shown in Figure 4 ( a) as shown. In response to this defect, this system enables the stack frame layout randomization strategy when the function is called, and adds a random size padding space to the stack during the frame initialization stage, so that the position of each return address is random and uncertain, and then Enables programs to obtain randomness between function cycles. The size of the padding space, the position of the padding space, and the randomization time all ensure sufficient randomization of the stack.

(1) The size of the random filling space of the stack. Because the Linux system requires that the stack pointer SP is 32-bit aligned, the size of the random space cannot be unlimited, it should be an integer multiple of 4, and the value range can be {4,8,...,4i,...,N }, the upper limit is N=4096 bytes, and the value should be randomly selected within the range in combination with the stack space size of the thread set in the Linux system.

(2) The position where the stack randomly fills the space. During runtime, the system periodically fills the safe buffer area with a random byte size during each re-randomization, before the function parameters. When running randomization of stack space, when the stack buffer index overflows, it will roll back to the first buffer index position, which leads to the possibility that the function may reuse a random stack safe buffer multiple times during repeated randomization area, which brings uncertainty to the attacker's positioning of the stack frame.

(3) Randomize the moment. The closer this time point is to the running time, the better randomization effect the system can achieve. Existing defense strategies either implement randomized layout before the program runs or when the process starts, both of which have certain defects. The dynamic randomization system delays the randomization moment until each function is running, so that the stack frame layout of each function is different each time it is run, and it is difficult for an attacker to obtain stack frame layout information from it.

(4) The stack fills the space randomly. When the system is running, every time a function is called, the dynamic randomization system fills a space of random size between two stack frames, which acts like a safety buffer. As shown in Figure 4(b). The process is as follows:

1) The system moves the stack before each function call, and the size is the index byte loaded by the function multiplied by the stack alignment standard 16 required on the x86_64 architecture.

2) Positioning parameter push instruction.

3) Add the code to the area to be filled.

4) Finally, the function parameters are pushed onto the stack.

This approach has no effect on how function parameters and local variables are accessed. Because if the padding area is placed between the frame pointer and the local variable, then the frame pointer plus the size of the padding area needs to be used as an offset before accessing the local variable.

3. Heap randomization

The present invention uses a new heap space randomization technique to make the distribution of the heap space no longer regular during operation. The dynamic randomization system employs two size-isolated allocators. The system was originally implemented with a DieHard allocator, which is a bitmap-based randomization allocator.

(1) Unlike traditional allocators, DieHard allocators do not use recently freed memory as subsequent allocation resources. The famous Use-After-Free security hole occurs when a program attempts to access memory that has been previously freed. Although the system's base allocator is more efficient than the DieHard allocator, the former is less randomized than the latter. Therefore, it is more reasonable to choose DieHard dispenser.

(2) The working principle of heap randomization is shown in Figure 5. The dynamic randomization system randomizes the heap by wrapping the basic allocator in the shuffling layer, and the shuffling layer is composed of array pointers with a size of N. heap of objects. In order to achieve sufficient randomization, the size N of the shuffling layer must be large enough, but too large N will also increase the overhead. Therefore, we finally choose N=256 as a compromise consideration. The malloc function is responsible for generating a random index, removing the index object corresponding to the shuffling layer, and replacing it with a basic heap object. Similarly, the free function generates a random index and releases the corresponding index object to the basic heap. In the heap space, after the initialization of the array in the shuffling layer is completed by calling malloc in the basic allocator, the array uses the shuffling algorithm to randomize the array: first call the malloc function in the shuffling layer, and then allocate The malloc function is used in the device to obtain a new object p and a random index i, where i∈[0, N], and exchange the array element corresponding to the index with p, and return the exchanged pointer object. The same is true for the shuffling principle of the free function.

Description of drawings

Figure 1: Schematic diagram of Flush+Reload attack

Figure 2: Effect diagram of defense against Flush+Reload attack

Figure 3: Code Randomization Diagram

Figure 4: Stack Randomization Diagram

Figure 5: Heap Randomization Diagram

Detailed ways

The hardware environment of the present invention is mainly a PC host. Among them, the CPU of the PC host is Intel(R) Core(TM) i5-4590, 3.30GHz, the memory is 8GB RAM, and the 64-bit operating system.

The software implementation of the present invention takes Ubuntu 14.04 as a platform, and is developed using C++ language. The GCC version is 4.6, the Llvm and Clang versions are 3.1, and the Dragonegg plugin version is 3.1.

The operation is mainly divided into two parts. The first part is to launch a Cache attack on a specific application, and the second part is to build a dynamic randomization system to defend against it.

1. Cache attack

(1) Flush: The attacker evicts a shared Cache line from the Cache.

(2) Wait: Schedule the target process to access the shared memory and update the Cache.

(3) Reload: The attacker reloads the memory block evicted in the Flush phase, and measures and records the loading time of a specific Cache line. The Cache line accessed by a specific application is speculated based on the difference in time information between a cache hit and a cache invalidation.

In the cache attack process, take the Flush+Reload attack as an example. Its key pseudocode is as follows:

The system threshold in the above pseudo code is the number of cycles measured according to the standardization in advance, and needs to be set according to the evaluation results of the system. The lower the threshold, the lower the false positive of the final statistical data. After several measurements, the number of cycles obtained in this experimental environment is around 125. At the same time, in order to ensure more accurate results, the number of encryption times should also be set reasonably. In the experiment, setting it to 10000 is enough to show the time difference between cache invalidation and cache hit.

2. Defense against Cache attacks

(1) The following is the pseudocode of the key part of defending against Cache attacks:

(2) Code randomization is mainly reflected in the continuous migration of function positions. The pseudo code is as follows:

(3) Stack randomization pseudocode:

(4) Heap randomization pseudocode:

Claims (5)

1. The realization method of dynamic randomization defense Cache attack is characterized in that the implementation steps are: (1) Randomize the code with the function as the granularity, and make the function address become unpredictable during the continuous migration and repeated randomization process of the function; (2) Enable the stack frame layout randomization strategy when the function is called, and add a padding space of random size to the stack during the frame initialization phase; (3) In terms of heap randomization, by wrapping the basic allocator in the shuffling layer, the distribution of the heap space at runtime is no longer regular. 2. the realization method of dynamic randomization defense Cache attack according to claim 1, it is characterized in that this method can be granularity randomization code with function: (1) In the initialization phase, a trap instruction is placed at the beginning of each function to trigger the work of the migration table; (2) In the function migration phase, when the trap function is executed, the dynamic randomization system receives a SIGTRAP signal at runtime and migrates the function; (3) The system repeats the randomization function every fixed time period; (4) After repeated randomization is completed, the memory is freed. 3. the realization method of dynamic randomization defense Cache attack according to claim 1, it is characterized in that this method can control the size of stack filling space, the position of filling space and the moment of randomization: (1) According to the requirements of the Linux system, the stack pointer alignment standard and the size of the stack space of the thread set in the Linux system are randomly selected within the range; (2) During operation, the system periodically fills the safety buffer area with a random byte size during each re-randomization, and the filled area is located in front of the function parameters; (3) Delay the randomization time until each function is running, so that the stack frame layout of each function is different every time it is running. 4. the realization method of dynamic randomization defense Cache attack according to claim 1, it is characterized in that this method has used a kind of new heap space address distribution mode: (1) Call the memory allocation function in the basic heap to initialize the shuffling layer; (2) Use the memory allocation function in the basic allocator to generate a random index i; (3) The array element in the shuffling layer corresponding to the above index is exchanged with the object p in the basic heap, and the exchanged pointer object is returned; (4) The memory release function is responsible for generating a random index and releasing the corresponding index object into the basic heap. 5. the realization method of dynamic randomization defense Cache attack according to claim 1 is characterized in that this method can adopt control variable method, repeats randomization code, stack, heap separately.