CN108197035A - A kind of method for detecting memory boundary overflow error - Google Patents

Abstract

The invention provides a method for detecting memory boundary overflow errors, which belongs to the field of computers. Using a regular method of storing objects, it is convenient to obtain and store the boundary information of the object; realize a more efficient and smaller boundary table, store the logarithm of the object allocation boundary size; judge the binary of the logarithm of the address pointed to by the pointer The value of the pointer is used to determine whether the pointer overflows; through the loop checking optimization method with a weaker premise as the core, the pointer overflowing the boundary can be found in advance, and the detection efficiency can be improved. The invention supports efficient checking of memory overflow errors of C language and C++ language programs, can solve all space memory safety problems, and effectively improves software reliability.

Description

A Method of Detecting Memory Boundary Overflow Errors

technical field

The invention relates to a method for detecting memory boundary overflow errors, which belongs to the field of computers.

Background technique

In daily life, all kinds of software are being integrated into our daily life at an unprecedented speed. And software has become an indispensable part of the operation of the whole society. Key industries such as banking, communication, education, transportation, and even the nuclear industry are using software to promote the development of industries and society. However, the size and complexity of our software systems have grown exponentially in recent years, and this trend will not stop in the future. As society becomes more and more dependent on software, software failures can bring huge losses to commercial systems, even safety-critical systems. Therefore, software reliability is becoming an important aspect that cannot be ignored in the development of the software industry.

Software reliability refers to the probability that software will keep running without failure in a specific environment and within a specific period of time, and software reliability engineering refers to the use of some engineering technologies to develop and maintain software systems, so that the reliability of these systems can be quantified evaluation of. According to the cycle of error generation, four main aspects of improving the reliability of software systems can be summarized: error prevention and error avoidance through specification development; error detection and removal through verification and confirmation technology; redundancy design to make system services in error The requirements are still met in the event of occurrence; the existence of errors, the possibility of future failures, and the impact of failures are predicted through software reliability models. Among them, software verification technology has always been an important aspect of research. Existing software verification technologies mainly include the following types, static analysis, model checking, and software testing.

Static analysis refers to finding possible errors through type inference, data flow analysis, and constraint analysis. The advantage is that errors can be found in the early stage of system development, but it will also bring a large number of false positives and negative negatives; model detection passes The analysis of the software structure transforms the system into a finite state space model, and verifies its completeness by using an algorithm. The advantage is that model checking is provable, but the disadvantage is that formal verification will cause the problem of state space explosion, and verification takes a long time And there will be a certain gap between the behavior of the model and the actual behavior of the system; software testing refers to designing test cases and running the program on this basis to observe the behavior and results of the program. The advantage is that it realizes test case management and execution. The disadvantage of automation is that test cases cannot achieve full coverage, and errors will be missed. In addition, the description of the verification nature is directly defined, which cannot be automatically generated through formal expression, which limits the ability of verification.

Different from the aforementioned four verification technologies that are mainly used in the software development process, runtime verification is a technology that performs property analysis and verification during the actual software running stage. As a newly proposed lightweight verification technology, it can realize Real-time monitoring of software operation to verify whether the software conforms to or violates a given correctness attribute is of great significance for improving the reliability of software. Runtime verification is a combination of runtime monitoring technology and formal specification technology. It obtains real-time status by monitoring the software running process, avoids the state space explosion and complexity problems caused by formal verification in model checking, and takes into account the actual Influencing factors such as the environment of the running process, while the runtime verification uses a formal language to describe the properties to be verified, such as linear sequential logic, regular expressions, automata, etc., making the runtime verification more rich and flexible in expressing properties. On the basis of property analysis and verification, runtime verification often also supports the control of the program running process. When the program runs into a certain error state, it can guide the program into a safe state or directly terminate the running of the program to avoid the error caused by the wrong running of the program. Greater loss or serious accident. At present, the runtime verification technology has been widely used in various fields such as the monitoring of hardware operation control Web applications and Android applications, and the network.

In the key technology of runtime verification, it mainly includes two parts, one is the description of the properties to be verified and the generation of corresponding verifiers, and the other is the system integration of monitors and verifiers. In terms of property description, runtime verification adopts techniques similar to model checking, and is described by logic languages such as linear temporal logic, parameterized proposition, regular expression, and automata. In terms of validator generation, a validator refers to a special class of components that can read a finite sequence of events and give a specific conclusion. The validator is automatically generated according to the properties specified by the user, and with the corresponding execution The code is integrated into the system to be monitored. At present, the verifier is mainly generated by the verification algorithm based on automata and the verification algorithm based on formula rewriting. Due to the partial inheritance of the content of model checking in terms of property description and verifier generation, there are already a large number of mature theories or algorithms for reference, which have universal language and algorithm versatility; while in the system of monitor and verifier In terms of integration, corresponding to different development platforms, different target languages, and different property description specifications will lead to differences in integration methods, and the design of integration methods will in turn affect the ability to express the nature of runtime verification itself. Therefore, how to design and realize the efficient system integration of runtime verification monitor and verifier has become an important and hot topic in the field of runtime verification research, which is of great value in promoting the application of runtime verification in practical systems.

Contents of the invention

To solve the above problems, the present invention provides a method for detecting memory boundary overflow errors.

The method for detecting memory boundary overflow error provided by the present invention comprises the following steps:

Step 1: The encoder reads the source code to be detected and converts it into an intermediate code;

Step 2: Analyze the intermediate code, use the object-based boundary detection technology to complete the alignment allocation of objects and realize the boundary table;

Step 3: Insert the detection function in the intermediate code and perform boundary check;

Step 4: Through analysis and optimization, redundant operations are simplified, and optimized intermediate code is generated;

Step 5: Link the optimized intermediate code to the binary library file to generate an executable file;

Step 6: Run the executable file, the detection function will judge whether the current pointer is beyond the boundary of the object before the pointer dereferences the object it points to. error.

In one embodiment, the specific process of using the object-based boundary detection technology in step 2 to complete the alignment allocation of objects and realize the boundary table is as follows:

First, allocate objects in an aligned manner: the aligned allocation of objects directly uses the memory allocator to control the boundaries of the objects generated by the program, and uses the binary memory allocator to satisfy the filling and aligned storage of memory objects;

Then, the implementation method of the boundary table: when the program object is allocated, the boundary of the object is controlled, and the memory occupied by the object is made to be a power of 2 by filling, and the binary expression of the logarithm of the allocated size is stored in the boundary table (e =log2(size)), through the (size=1<<e; base=p&~(size-1);) operation, restore the allocation size of the object and the pointer to the start position of the allocation address.

In one embodiment, a contiguous array is used to implement the boundary table.

In one embodiment, in the step 3, the detection function is inserted into the intermediate code, and the specific operation of performing the boundary check is as follows:

Use the value of the p pointer and the binary value of the logarithm of the allocation size e, where e is obtained from the boundary table, to ensure that the q pointer is inside the boundary if q and p differ only in the least significant bit.

In one embodiment, the specific optimization steps in the step 4 are as follows:

First, check codes have been added for each pointer operation in the intermediate code from the previous third step;

Secondly, the maximum range of value domain analysis is performed on all pointer operations existing in the loop body.

In one embodiment, the maximum range refers to the maximum pointing range of multiple pointer variables pointing to the same buffer within a loop body.

In one embodiment, the detection function in step six checks whether the current pointer address of the pointer is inside the object pointed to by the pointer, and the address of the object is obtained by querying the boundary table.

In one embodiment, the source code to be detected is C or C++ language.

The method for detecting memory boundary overflow error provided by the present invention adopts a regular method of storing objects, which facilitates obtaining and storing object boundary information; realizes a more efficient boundary table occupying smaller memory, and stores the logarithm of object allocation boundary size ;By judging the binary value of the logarithm of the address pointed by the pointer to determine whether the pointer overflows; through the cycle inspection optimization method with a weaker premise as the core, the pointer overflowing the boundary can be found in advance, the detection efficiency can be improved, and the software can be quickly Verify; for systems with different hardware, such as 32-bit or 64-bit, you can adjust the size of object allocation to achieve the highest memory utilization efficiency and reduce memory waste. The present invention supports the efficient checking of memory overflow errors of C language and C++ language programs. Since the objects are stored in an aligned manner, the query time for boundary values can be saved, and the memory space for storing conventional object addresses can also be saved. It can solve all space memory security issues, thereby effectively improving the reliability of the software.

Description of drawings

FIG. 1 is a schematic flowchart of a method for detecting memory boundary overflow errors provided by Embodiment 1 of the present invention;

FIG. 2 is a relationship diagram between the actual allocation boundary of an object and the size of the object.

Detailed ways

A method for detecting memory boundary overflow errors proposed by the present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments. Advantages and features of the present invention will be apparent from the following description and claims. It should be noted that all the drawings are in a very simplified form and use imprecise scales, and are only used to facilitate and clearly assist the purpose of illustrating the embodiments of the present invention.

Embodiment one

In actual object memory allocation, use a fixed-size allocation boundary rather than the actual size of the object as the boundary. Here, we use this approach for efficient backward compatibility bounds checking. We use a memory allocator (such as the binary BD allocator) to make the allocation bounds sufficiently simple: since all allocation sizes are powers of 2, a single byte is sufficient to store the binary logarithm of the allocation size. Further, since the base address of an allocation of size S can be computed by clearing the least significant bits (log2(s)) of any pointers to allocated memory regions, there is no need to store unnecessary information. In this way, we can design a data structure that is both spatially and temporally efficient for the boundary information table. This method uses a contiguous array instead of a very memory-intensive data structure (such as a splay tree).

The content of this embodiment one is as follows:

Step 1: the coder reads the source code to be detected and converts it into an intermediate code; the source code to be detected is C or C++ language.

Step 2: Analyze the intermediate code generated in Step 1, complete the alignment allocation of objects and realize the boundary table. In this step, the object-based boundary detection technology is adopted, and the meaning of object-based is to record the boundary information of each object in the boundary table. The object-based approach is to perform detection on program statements that contain pointer arithmetic. It uses the source pointer to look up the object boundary information in the boundary table, and checks whether the destination pointer is still inside the boundary. If the target does not point to the object it should point to, the pointer is marked as a bounds overflow pointer and any dereference requests for the pointer are denied. But we will allow this illegal pointer to perform further pointer operations, because the operation may end up with a pointer inside the bounds.

The specific process is as follows:

(1) Allocate objects in alignment: The alignment allocation of objects can directly use the existing memory allocator (such as the buddy allocator) to control the boundaries of the objects generated by the program. Using a binary memory allocator to satisfy the filling and alignment storage of memory objects, generally speaking, divides the memory into blocks (slots) of the same size, and the size of each block (slot-size) is a power of 2. This ensures that the boundary table in the next step can efficiently store boundary information. FIG. 2 is a relationship diagram between the actual allocation boundary of an object and the size of the object;

(2) Efficient implementation method of boundary table: use a very concise way to represent boundary information. When the program object is allocated, the boundary of the object is controlled, and the memory occupied by the object is made to be a power of 2 by filling. In this way, what is stored in the boundary table is the allocation boundary of the object instead of the actual boundary of the object. Originally, at least eight bytes are required to store the base address and size of an object, but the boundary table in the first embodiment only needs one byte to record boundary information, thereby greatly reducing memory overhead. What we store in the boundary table is the binary representation of the logarithm of the allocation size (e=log2(size)). With this information, we can use the (size=1<<e; base=p&~(size-1);) operation to restore the allocation size of the object and the pointer to the beginning of the allocation address.

In the present invention, a continuous array is used to realize the boundary table, because each entry in the table only uses one byte, so the boundary table is very small. Since the objects in the previous step are stored in a fixed block size, and the size of each block slot-size is a power of 2, the memory block occupied by each object has an object entry in the boundary table, so the table The space occupied is the original 1/slot size, and we can adjust the slot-size to balance the memory waste and table size.

Step 3: Insert the detection function in the intermediate code and perform boundary check. Since the third step is based on the object, it is not necessary to pay attention to each pointer, but only needs to pay attention to whether each pointer to the current object and its arithmetic operation are still within the boundary of the object.

In general, checking the bounds of the result q of an arithmetic operation (q=p+i) on p pointers requires checking whether q is within the upper and lower bounds. This embodiment provides an optimized bounds checking method that does not need to calculate the upper and lower bounds of the object. This method takes only the value of the p pointer and the binary value of the logarithm of the allocation size e, where e is obtained from the bounds table. This control over allocation size and alignment guarantees that if q and p differ only in the least significant bits, then the q pointer is inside the bounds.

Further, for the pointer q where sizeof(*q)>1, we also need to check whether the value of (char*)q+sizeof(*q)–1 is within the boundary to prevent subsequent direct access bypassing the allocation boundary *q. Relaxed bounds checking avoids checking that the q pointer points to a built-in type. Accesses to these aligned types do not overlap because their values are all powers of 2 and are smaller than slot-size.

Take a pointer operation (char*p=buf[i]) as an example:

The first step is to move the source pointer buf to the right to obtain the boundary of the corresponding object in the boundary table.

In the second step, the logarithm of the allocation size e is loaded from the bounds table into register al.

In the third step, the result of the pointer operation is XORed with the source pointer buf.

The fourth step is to remove the low bits by shifting al to the right.

If both buf and p are within the bounds of the allocation, they differ only in the least significant bits of log2e.

Step 4: Through analysis and optimization, unnecessary redundant operations are simplified, and optimized intermediate code is generated. Typical optimization methods used in bounds checking include: eliminating redundant checks, extracting checks inside loops, or extracting only bound table lookup operations inside loops. Optimizing the inner loop can effectively improve performance. When all accesses within a loop are to the same object we try to extract the boundary table lookup operation from inside the loop. The specific optimization steps are as follows:

a. From the previous steps, check codes have been added for each pointer operation in the intermediate code.

b. Analyze the maximum range of value ranges for all pointer operations that exist in the loop body. The maximum range refers to the maximum pointing range of multiple pointer variables pointing to the same buffer within a loop body. However, the ranges of these pointer variables are different. Assume that the range of pointer p is a[0]～a[i-1], and the range of pointer q is a[1]～a[i+1]. The maximum range a[0]～a[i+1] can be obtained by taking the union of the range pointers of the buffer array, and the analysis of the maximum range of multiple pointers is the same as the above process. For example, in the following loop example, if L is large enough, the execution of unoptimized code will bring a very large runtime overhead. In C language, a[i] is equivalent to a pointer. We can judge the weakest boundary overflow condition of a[i] before the loop starts. In this example, a[i] ranges from a[1] to a [L]. If a[i] does not even meet this weakest condition, it means that it has overflowed, and the execution is terminated. If the weakest condition is satisfied, the loop body is executed, and whether there is an internal overflow is judged inside the loop body.

c. Merge the weakest conditions of pointers to objects of the same origin. For example, a[i] and a[i-1] in the above code, the weakest condition range of a[i] is a[1] to a[L], and the range of a[i-1] is a[0] to a[L-1], the weakest homologous condition after merging is a[0] to a[L].

By analyzing the scope of the object pointer before entering the loop body, many unnecessary redundant operations can be simplified. Extracting the entire check from the loop body is very efficient when static analysis can determine approximate bounds on pointer values within the loop body. But these checks can only be extracted from the loop body if the static analysis can determine that these boundaries can be visited at every step of execution. The bounds of a loop body can be easily determined but the loop may terminate before reaching the upper bound. Object bounds are overflowed before the loop breaks out, in which case taking a check out of the loop will throw an alert at runtime.

Step 5: Link the optimized intermediate code to the binary library file to generate an executable file.

Step 6: The user runs the executable file after the detection function has been inserted. When encountering memory security errors such as pointer out of bounds and buffer overflow, the program will call to terminate the execution and report an error. The detection function inserted in the third step checks whether the current pointer address of the pointer is inside the object pointed to by the pointer, and the address of the object is obtained by querying the boundary table. If it is inside the boundary, continue to execute the following statement, if it is not inside, it means that the pointer has overflowed, and the execution terminates the program and reports an error

Embodiment 1 provides support for checking all backward compatible boundary overflow errors for C and C++. This method converts the source code into an intermediate code representation (IR), looks for potentially unsafe pointer arithmetic operation statements, and inserts checking code to ensure that their results are always within bounds. Then, link the IR against our runtime and binary libraries, resulting in a robust executable.

Although the present invention has been disclosed above with preferred embodiments, it is not intended to limit the present invention. Any person familiar with this technology can make various changes and modifications without departing from the spirit and scope of the present invention. Therefore The scope of protection of the present invention should be defined by the claims.

Claims (8)

1. A kind of 1. method for detecting memory boundary overflow error, which is characterized in that include the following steps：

   Step 1：Encoder reads source code to be detected and is converted into intermediate code；

   Step 2：Intermediate code is analyzed, distributed using the alignment of object-based bound test technology completion object and realizes side Boundary's table；

   Step 3：Detection function is inserted into intermediate code；

   Step 4：By analysis optimization, simplify redundant operation, the intermediate code after generation optimization；

   Step 5：Intermediate code after optimization is linked to binary library file, generates executable file；

   Step 6：Executable file is run, detection function can judge current pointer before pointer dereference its pointed object Whether object bounds are run off, there is pointer to cross the border when encountering, the memories security error such as buffer overflow, program can call termination to perform And it reports an error.
2. 2. the method for detection memory boundary overflow error as described in claim 1, which is characterized in that used in the step 2 The alignment that object-based bound test technology completes object distributes and realizes that the detailed process of boundary table is：

   First, distribution object in aligned fashion：The object that the alignment distribution of object directly generates program using memory allocator Boundary Control is carried out, meets the filling of memory object with being aligned storage using binary memory allocator；

   Then, the implementation method of boundary table：The boundary of object is controlled when program object distributes, passes through filling 2 power is saved as in shared by object, that stored in the table of boundary is the binary expression (e=log2 of the logarithm of allocated size (size)), pass through (size=1<<e；Base=p＆~(size-1)；) operation restores the allocated size of object and direction is divided Pointer with address starting position.
3. 3. the method for detection memory boundary overflow error as claimed in claim 2, which is characterized in that come using continuous array Realize boundary table.
4. 4. the method for detection memory boundary overflow error as described in claim 1, which is characterized in that in the step 3 in Between be inserted into detection function in code, the concrete operations of exercise boundary inspection are as follows：

   Using the binary value of the logarithm of the value and allocated size e of p pointers, e therein is obtained from the table of boundary, is protected with this Card is if q and p is only if least significant bit has any different so q pointers in border inner.
5. 5. the method for detection memory boundary overflow error as described in claim 1, which is characterized in that specific in the step 4 Optimization Steps are as follows：

   First, by before the step of three in be that each pointer operation is added to inspection code in intermediate code；

   Secondly, all pointer operations being present in loop body are carried out with the range analysis of maximum magnitude.
6. 6. the method for detection memory boundary overflow error as claimed in claim 5, which is characterized in that the maximum magnitude is Refer to：The maximum of the pointer variable of the same buffering area of multiple directions inside a loop body is directed toward range.
7. 7. the method for detection memory boundary overflow error as described in claim 1, which is characterized in that detected in the step 6 For function by whether checking the current pointer address of pointer in the inside of the pointer referent, the address of object is to pass through boundary Table is inquired to obtain.
8. 8. the method for detection memory boundary overflow error as described in claim 1, which is characterized in that the source generation to be detected Code is C or C Plus Plus.