KR20200046363A - Apparatus and method for performing symbolic execution - Google Patents

Abstract

According to one embodiment, provided is an apparatus for performing symbol execution which comprises: an information acquisition unit acquiring an address of a function related to a process; a path search unit acquiring an address for a function to be analyzed from the information acquisition unit and searching for a path from an entry point of the process to the acquired address; and a symbol execution unit performing symbol execution on the searched path. Accordingly, fast, accurate and efficient symbol execution with less time can be performed.

Description

Device and method for performing symbol execution {APPARATUS AND METHOD FOR PERFORMING SYMBOLIC EXECUTION}

The present invention relates to an apparatus and method for performing symbol execution.

Analyzing the execution path of software means analyzing a path or process that a computer takes when processing a task based on logic or data of software. Conventional software execution path extension methods include: 1) attempting to expand the execution path by generating a large number of test cases in which the execution path is likely to be expanded from the source code of the extension target software, or when the source code cannot be obtained Attempt to expand the execution path by simply generating a large number of test cases with random values. Conventional methods have limitations on the execution path extension because the software actually executes and does not refer to the dynamic information that forms, ie the program context.

Meanwhile, symbol execution is used in the field of program testing such as software. Through symbol execution, it is possible to check whether a branch can proceed to a specific memory area during program execution. In addition, when a program is executed differently according to a user input, it may be checked whether a target memory area is reachable according to a specific user input. Through this program testing, it is possible to search for vulnerabilities in the program.

Korean Registered Patent Publication, No. 10-1530132 (Registered on June 12, 2015)

Conventionally, most processes have been manually performed in symbol execution. However, manual symbolic execution is difficult to apply to large code. In particular, looking at the process of checking whether a particular memory area is reachable during the execution of a program or a process, the constraints collected every time a function branches are doubled. This may cause a problem of excessively expanding the search range, such as path-explosion.

Accordingly, the problem to be solved by the present invention is to provide a technique for efficiently and quickly performing symbol execution without expanding a search range without problems such as path-explosion.

However, the problem to be solved of the present invention is not limited to those mentioned above, and another problem not to be solved can be clearly understood by a person having ordinary knowledge to which the present invention belongs from the following description. will be.

The apparatus for performing symbol execution according to an embodiment includes an information acquisition unit that acquires an address of a function related to a process, a path search unit that searches a path from an entry point of the process to the obtained address, and And a symbol execution unit that performs symbol execution on the searched path.

Also, the information acquisition unit may obtain the address from an import address table.

Also, the obtained address may be an address of the .idata area.

In addition, the information acquisition unit obtains an address for at least one of the assembly, DLL, and library associated with the process, and the path search unit receives an address obtained for at least one of the assembly, DLL, and library from the entry point of the process. Can navigate to the path

The method for performing symbol execution according to an embodiment is performed by a symbol execution performing apparatus, obtaining an address of a function related to a process, and searching a path from an entry point of the process to the obtained address And performing symbol execution on the searched path.

Also, the acquiring step may acquire the address from an import address table.

Also, the obtained address may be an address of the .idata area.

In addition, the acquiring step obtains an address for at least one of the assembly, DLL, and library associated with the process, and the searching step is obtained for at least one of the assembly, DLL, and library from the entry point of the process. You can navigate the route to the address.

That is, according to an embodiment, symbol execution may not be performed on all paths of the process, that is, all branches, but symbol execution may be performed only on paths searched by the path search unit. This enables fast, accurate and efficient symbol execution in a short time.

1 exemplarily shows a configuration of an apparatus for performing symbol execution according to an embodiment.
FIG. 2 exemplarily shows a path searched by the path search unit illustrated in FIG. 1.
3 illustrates a procedure of a method for performing symbol execution according to an embodiment.

Advantages and features of the present invention, and methods for achieving them will be clarified with reference to embodiments described below in detail together with the accompanying drawings. However, the present invention is not limited to the embodiments disclosed below, but may be implemented in various different forms, and only the embodiments allow the disclosure of the present invention to be complete, and common knowledge in the art to which the present invention pertains It is provided to completely inform the person having the scope of the invention, and the present invention is only defined by the scope of the claims.

In describing embodiments of the present invention, when it is determined that a detailed description of known functions or configurations may unnecessarily obscure the subject matter of the present invention, the detailed description will be omitted. In addition, terms to be described later are terms defined in consideration of functions in an embodiment of the present invention, which may vary according to a user's or operator's intention or practice. Therefore, the definition should be made based on the contents throughout this specification.

1 exemplarily shows a configuration of an apparatus for performing symbol execution according to an embodiment.

Referring to FIG. 1, the apparatus 100 for performing symbol execution includes an information acquisition unit 110, a path search unit 120, and a symbol execution unit 130, but the configuration of the apparatus 100 for performing symbol execution is illustrated. What is shown in 1 is not to be construed as limited.

First, each of the information acquisition unit 110, the path search unit 120, and the symbol execution unit 130 is implemented by a memory storing instructions programmed to perform a function described below and a microprocessor executing these instructions. It is possible.

Among them, the information acquisition unit 110 will be described first. The information acquisition unit 110 acquires static analysis information necessary for symbol execution. For example, the information acquisition unit 110 obtains at least one of a function address, an assembly, a DLL, and a library of a function in an import address table as static analysis information. Here, the function may be an application programming interface (API). In addition, the address of the function may indicate the address of the .idata area of the API.

Meanwhile, the information acquisition unit 110 may acquire dynamic analysis information according to an embodiment as well as static analysis information.

The static analysis information acquired by the information acquisition unit 110 is used to reduce the search range of symbol execution. Specifically, if symbolic execution is performed on all branches of the process under analysis, problems such as path-explosion may occur. This is because the constraints collected each time a branch of the process is performed are doubled.

However, in one embodiment, the search range of symbol execution is limited based on the static analysis information acquired by the information acquisition unit 110. For example, when the recv API or send API in WS2_32.dll is a target, the address of the .idata area of each of these APIs can be obtained by the information acquisition unit 110, as will be described later, path search and symbol execution are thus obtained .idata It can be limited to the address of the region.

The route search unit 120 searches for a route from an entry point of the process to an address obtained by the information acquisition unit 110. The route search unit 120 may be, for example, a path-finder, but is not limited thereto.

Hereinafter, the route search unit 120 will be described in more detail.

There may or may not be at least one path from the entry point of the process to the address of a given memory area. The route search unit 120 searches how many routes are described above, and if so, what each route is.

In addition, if a function is branched into a plurality, and some of them cannot reach the address of a predetermined memory area, the path search unit 120 excludes the path for the portion from the search. That is, according to the path search unit 120, paths that cannot reach the address of the predetermined memory area from the entry point of the process are excluded. Therefore, even if the constraints collected during the symbol execution process are doubled as the function is branched, the symbol execution has an effect of not being performed on the excluded path. This can prevent the range of symbol execution from being unnecessarily expanded.

2 exemplarily shows a plurality of paths searched by the path search unit 120 in the form of text.

Referring to FIG. 2, there is no path from the entry point of the process to the address of sub_410B98. Likewise, there is also no route from the entry point of the process to each address of sub_4113BB and sub_411443. That is, the route search unit 120 may obtain information that there is no route from the entry point of the process to the address of a predetermined memory area.

On the other hand, referring to Figure 2, there are five paths from the entry point of the process to the address of sub_423F47. The route search unit 120 provides even detailed information about what the corresponding route is as shown in FIG. 2. In addition, referring to FIG. 2, there are also two paths from the entry point of the process to the address of sub_424041.

That is, the route search unit 120 may provide the number of routes and detailed information of the route from the entry point of the process to the address of a predetermined memory area.

1 will be referred to again.

The symbol execution unit 130 performs symbol execution on the path searched by the path search unit 120. If there are multiple paths searched by the path search unit 120, the symbol execution unit 130 may perform symbol execution for each of the plurality of paths.

Here, symbolic execution refers to a method of symbolically executing variables that appear during execution of a process. In this symbolic implementation, symbolic constraints are collected during the reverse engineering process. The collected constraints affect what values the symbolic variables should have to reach the address of a given memory area.

In one embodiment, the symbol execution unit 130 does not perform symbol execution on all paths of the process, that is, all branches of the function. The symbol execution unit 130 performs symbol execution only on the path searched by the path search unit 120. As described above, the path searched by the path search unit 120 is a path from an entry point of a process to an address of a predetermined memory area.

That is, according to an embodiment, symbol execution may not be performed on all paths of the process, that is, all branches, but symbol execution may be performed only on paths searched by the path search unit. This enables fast, accurate and efficient symbol execution in a short time.

3 illustrates a procedure of a method for performing symbol execution according to an embodiment. The method for performing symbol execution may be performed by the symbol execution apparatus 100 illustrated in FIG. 1. However, the procedure of the method illustrated in FIG. 3 is merely exemplary, and the procedure of the method for performing symbol execution is not limited to that illustrated in FIG. 3.

Referring to FIG. 3 together with FIG. 1, a process that is a target of symbol execution is selected (S100).

Next, the information acquisition unit 110 acquires static analysis information (S110). The static analysis information may be related to the process selected in step S100. The static analysis information may include at least one of a function address, an assembly, a DLL, and a library in an import address table. In this case, the function may be an application programming interface (API). In addition, the address of the function may indicate the address of the .idata area of the API.

The static analysis information obtained in step S110 is used to reduce the search range of symbol execution. Specifically, if symbolic execution is performed on all branches of the process under analysis, problems such as path-explosion may occur. This is because the constraints collected each time a branch of the process is performed are doubled.

However, in one embodiment, the search range of symbol execution is limited based on the static analysis information obtained in step S110. For example, if the recv API or send API in WS2_32.dll is the target, the address of each .idata area of each of these APIs can be obtained in step S110, and as will be described later, path search and symbol execution are limited to the address of the obtained .idata area. Can be done.

Next, the information acquisition unit 110 selects the target API (S120). The target API may be, for example, a recv API or send API in WS2_32.dll, but is not limited thereto. Here, the target API may refer to a function to be analyzed.

Next, the route search unit 120 searches for a route from the entry point of the process selected in step S100 to the address of the target API selected in step S120 (S130). The route search unit 120 may be, for example, a path-finder, but is not limited thereto.

Hereinafter, step S130 will be described in more detail.

There may or may not be at least one path from the entry point of the process to the address of a given memory area. In step S130, the route search unit 120 searches for the number of routes described above, and if so, what each route is.

In addition, if a function is branched into a plurality of parts, and some of them cannot reach an address of a predetermined memory area, in step S130, paths to these parts are excluded from the search. Therefore, even if the constraints collected during the symbol execution process are doubled as the function is branched, the symbol execution has an effect of not being performed on the excluded path. This can prevent the range of symbol execution from being unnecessarily expanded.

Next, the symbol execution unit 130 performs symbol execution on the path searched by the path search unit 120 (S140). If there are multiple paths searched by the path search unit 120, in step S140, the symbol execution unit 130 may perform symbol execution for each of the plurality of paths.

Here, symbolic execution refers to a method of symbolically executing variables that appear during execution of a process. In this symbolic implementation, symbolic constraints are collected during the reverse engineering process. The collected constraints affect what values the symbolic variables should have to reach the address of a given memory area.

In one embodiment, the symbol execution unit 130 does not perform symbol execution on all paths of the process in step S140, that is, all branches of the function. In step S140, the symbol execution unit 130 performs symbol execution only on the path searched by the path search unit 120. As described above, the path searched by the path search unit 120 is a path from an entry point of a process to an address of a predetermined memory area.

That is, according to an embodiment, symbol execution may not be performed on all paths of the process, that is, all branches, but symbol execution may be performed only on paths searched by the path search unit. This enables fast, accurate and efficient symbol execution in a short time.

On the other hand, the method for performing symbol execution according to an embodiment is implemented in the form of a computer readable recording medium storing a computer program programmed to perform, including each step included in the method, or for each step included in the method. It may be embodied in a computer program stored on a computer readable recording medium programmed to perform including.

For example, a computer program may include obtaining an address of a function related to a process, searching a path from an entry point of the process to the obtained address, and performing symbolic execution on the searched path It may be programmed to perform including steps, and a computer-readable recording medium may store such a computer program.

The above description is merely illustrative of the technical idea of the present invention, and those of ordinary skill in the art to which the present invention pertains may make various modifications and variations without departing from the essential quality of the present invention. Therefore, the embodiments disclosed in the present invention are not intended to limit the technical spirit of the present invention, but to explain, and the scope of the technical spirit of the present invention is not limited by these embodiments. The scope of protection of the present invention should be interpreted by the following claims, and all technical ideas within the scope equivalent thereto should be interpreted as being included in the scope of the present invention.

100: symbol execution analysis device

Claims (10)

An information acquisition unit that acquires an address of a function related to the process,
A path search unit for searching a path from an entry point of the process to the obtained address;
And a symbol execution unit performing symbol execution on the searched path.
Symbolic execution device. According to claim 1,
The information acquisition unit,
Obtaining the address from the import address table
Symbolic execution device. According to claim 2,
The obtained address,
the address of the .idata area
Symbolic execution device. According to claim 1,
The information acquisition unit,
Obtain an address for at least one of the assembly, DLL and library associated with the process,
The route search unit,
Searching the path from the entry point of the process to the address obtained for at least one of the assembly, DLL and library
Symbolic execution device. A method for performing symbol execution performed by an apparatus for performing symbol execution,
Obtaining the address of the function associated with the process,
Searching a path from an entry point of the process to the obtained address;
And performing symbol execution on the searched path.
How to perform symbolic execution. The method of claim 5,
The obtaining step,
Obtaining the address from the import address table
How to perform symbolic execution. The method of claim 6,
The obtained address,
the address of the .idata area
How to perform symbolic execution. The method of claim 5,
The obtaining step,
Obtain an address for at least one of the assembly, DLL and library associated with the process,
The searching step,
Searching the path from the entry point of the process to the address obtained for at least one of the assembly, DLL and library
How to perform symbolic execution. Programmed to perform each step included in the method according to claim 5
A computer readable recording medium storing a computer program. Programmed to perform each step included in the method according to claim 5
A computer program stored on a computer readable recording medium.

Images