CN110414238A - Homologous binary code retrieval method and device - Google Patents

Abstract

Embodiments of the present invention provide a method and device for retrieving homologous binary codes, wherein the method includes: determining all basic blocks of a function to be detected and basic block level information of each basic block; generating a control flow graph of the function to be detected; The basic block level information and dependencies of all basic blocks are used as the control call information of the function to be detected; the control call information is input into the pre-trained neural network model, the encoding vector of the function to be detected is output, and the hash signature of the encoding vector is calculated, As the hash signature to be retrieved; search the pre-built hash signature library to see if there is a hash signature that is the same as the hash signature to be retrieved, and if so, use the binary code corresponding to the retrieved hash signature as the function to be detected homologous binary code. The embodiments of the present invention perform risk assessment on firmware that may have vulnerability risks, and provide analysis reference for vulnerability security researchers.

Description

Homologous binary code retrieval method and device

technical field

The invention relates to the technical field of vulnerability mining, and more particularly, to a method and device for retrieving homologous binary codes.

Background technique

Vulnerability is an important factor affecting the security of information systems and cyberspace. The firmware vulnerabilities disclosed in recent years and the large-scale malicious attacks against IoT devices show that IoT devices are becoming the focus of malicious attacks, and firmware is the preferred target of attackers. The particularity of firmware interacting with IoT devices makes the security of firmware not only affect the security of information systems, but also the security of physical devices.

During the development of firmware, due to the extensive use of shared underlying libraries and third-party SDKs, same-origin vulnerabilities commonly exist in different IoT device firmwares. When a firmware is exposed, other firmware containing the same source code will also be in a high-risk state. Since the same-source code association technology can quickly retrieve code fragments similar to a given vulnerability binary code from massive firmware binary codes, and narrow the scope of subsequent manual analysis, it is possible to perform risk assessment on firmware that may have vulnerability risks and conduct vulnerability security research. Provide analysis reference.

In the research of homologous code association, the function structure information of binary code is often used, such as function call graph and function internal control flow graph, and the similarity is obtained by structural matching using graph isomorphism technology. In 2004, Rudinger K, Gamble J K, Bach E, et al. Comparing algorithms for graph isomorphism using discrete-and continuous-time quantum random walks proposed a graphical comparison method based on instruction similarity. Analyze the entry address of the function, express the function as a function control flow graph with the node as the instruction level, and then compare the similarity of the instructions to obtain the similarity graph between the nodes, and simplify and synthesize the function control flow graph based on the result. The largest possible similarity map. The disadvantage of this method is that it is susceptible to instruction rearrangement caused by compiler optimizations, and the algorithm cannot skip a local small block of mismatched code to find the starting point of the comparison again. Halver Flake. Structural Comparison of Executable Objects proposed in the same year to regard the entire executable file as a call graph whose nodes are functions, assign a structured signature to each function, and use the structured signature to compare functions, Identifies relationships between functions. This approach focuses on structural changes in executable files. The disadvantage is that it cannot detect unstructured changes, and because there may be multiple functions with the same structural signature, some functions cannot be compared. Chang Qing, Liu Zhongjin, Wang Mengtao, et al. 2017. VDNS: A Cross-Platform Firmware Vulnerability Association Algorithm A cross-platform firmware vulnerability function association method is proposed. The method takes functions as the associated objects, through feature extraction and numerical processing , and calculate the similarity of vulnerability function to perform vulnerability detection. However, the disadvantage of this method is that the function association method for pairwise comparison is only suitable for scenarios with a small data scale. In a scenario where the data scale reaches tens of millions, the time cost of the function for pairwise comparison calculation is as high as tens of thousands of hours.

SUMMARY OF THE INVENTION

Embodiments of the present invention provide a method and device for retrieving homologous binary codes that overcome the above problems or at least partially solve the above problems.

In a first aspect, an embodiment of the present invention provides a method for retrieving homologous binary codes, including:

Determine all basic blocks of the function to be detected and basic block level information of each basic block, generate a control flow graph of the function to be detected, determine the dependencies between all basic blocks according to the control flow graph, and combine all basic blocks. The basic block level information and the dependency relationship are used as the control call information of the function to be detected;

Inputting the control call information into a pre-trained neural network model, outputting the encoding vector of the function to be detected, and calculating the hash signature of the encoding vector as the hash signature to be retrieved;

Search the pre-built hash signature library to see if there is a hash signature that is the same as the hash signature to be retrieved, and if so, take the binary code corresponding to the retrieved hash signature as the homology of the function to be detected binary code.

In a second aspect, an embodiment of the present invention provides an apparatus for retrieving homologous binary codes, including:

The control call information generation module is used to determine all basic blocks of the function to be detected and the basic block level information of each basic block, generate a control flow graph of the function to be detected, and determine between all basic blocks according to the control flow graph Dependency relationship, the basic block level information and dependencies of all basic blocks are used as the control call information of the function to be detected;

A hash signature generation module is used to input the control call information into the pre-trained neural network model, output the encoding vector of the function to be detected, and calculate the hash signature of the encoding vector as the hash signature to be retrieved ;

The retrieval module is used to retrieve whether there is a hash signature that is the same as the hash signature to be retrieved in the pre-built hash signature library, and if so, the binary code corresponding to the retrieved hash signature is used as the hash signature to be retrieved Homologous binaries for detection functions.

In a third aspect, an embodiment of the present invention provides an electronic device, including a memory, a processor, and a computer program stored in the memory and running on the processor, the processor implementing the program as described in the first aspect when the processor executes the program Steps of the provided method.

In a fourth aspect, an embodiment of the present invention provides a non-transitory computer-readable storage medium on which a computer program is stored, and when the computer program is executed by a processor, implements the steps of the method provided in the first aspect.

The method and device for retrieving homologous binary codes provided by the embodiments of the present invention encode the features of binary codes into coding vectors (feature vectors) by means of deep learning, so that locality-sensitive hashing can be used for acceleration and the speed of online matching is improved , to quickly retrieve code fragments similar to a given vulnerability binary code from massive firmware binary codes, and narrow the scope of subsequent manual analysis, so as to perform risk assessment on firmware that may have vulnerability risks and provide analysis reference for vulnerability security researchers .

Description of drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the following briefly introduces the accompanying drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description These are some embodiments of the present invention. For those of ordinary skill in the art, other drawings can also be obtained according to these drawings without creative efforts.

1 is a schematic flowchart of a method for retrieving homologous binary codes according to an embodiment of the present invention;

Fig. 2 is the dependency relation diagram when basic block node attribute is updated in the iterative process of the embodiment of the present invention;

3 is a schematic structural diagram of an apparatus for retrieving homologous binary codes provided by an embodiment of the present invention;

FIG. 4 is a schematic diagram of a physical structure of an electronic device according to an embodiment of the present invention.

Detailed ways

In order to make the purposes, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments These are some embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.

FIG. 1 is a schematic flowchart of a method for retrieving homologous binary codes provided by an embodiment of the present invention. As shown in FIG. 1 , the retrieval method includes: S101, S102, and S103. Specifically,

S101. Determine all basic blocks of the function to be detected and basic block level information of each basic block, generate a control flow graph of the function to be detected, determine dependencies between all basic blocks according to the control flow graph, The basic block level information and the dependency relationship of the basic block are used as the control calling information of the function to be detected.

It should be noted that, in this embodiment of the present invention, a reverse tool can be used to perform a reverse function division operation on a binary program, so as to obtain multiple functions. A control flow graph in the form of a directed graph is generated for each function using the prior art. In the control flow graph, each node corresponds to a basic block of a function, and each directed edge between nodes corresponds to a jump relationship between two basic blocks. It can be understood that a basic block is a set of assembly instruction sequences executed at one time, and usually has an entry point and an exit point. When the program is executed, it starts from the entry instruction, and executes the passed instructions in sequence until the exit instruction position. By processing the control flow graph, the basic block level information within the function and the structural information between basic blocks can be obtained. The structural information between the basic blocks is the jump relationship between the basic blocks.

As an optional embodiment, the basic block level information includes the number of string constants, the number of numeric constants, the number of escape instructions, the number of call instructions, the number of arithmetic instructions, the number of assembly instructions, the number of The number of nodes and betweenness centrality.

By combining the basic block level information and the dependency relationship, the control call information of the function to be detected is obtained. As an optional embodiment, the control call information in this embodiment of the present invention is an attribute control call graph (Attributed Control Flow Graph, ACFG), and each node in the attribute control call graph is a basic control call graph with an attribute set. piece. ACFGs are essentially directed graphs of basic blocks inside functions, where the cross-platform nature of the properties inside functions has been demonstrated.

S102. Input the control call information into a pre-trained neural network model, output an encoding vector of the function to be detected, and calculate a hash signature of the encoding vector as the hash signature to be retrieved.

It should be noted that, in the embodiment of the present invention, the control call information is abstractly represented as a coding vector through a pre-trained neural network model. Convert the obtained encoded vector with a predetermined locality-sensitive hash function to obtain the hash signature of the encoded vector.

S103. Search in a pre-built hash signature library whether there is a hash signature that is the same as the hash signature to be retrieved, and if so, use the binary code corresponding to the retrieved hash signature as the signature of the function to be detected. Homologous binary code.

It should be noted that, in this embodiment of the present invention, the binary codes in the system firmware library can be calculated by referring to the methods of steps S101 and S102, a large number of hash signatures can be obtained, and a hash signature library can be constructed. It is understandable that the composition of building the hash signature library can be done offline, thus not consuming online search time. After receiving the online search task, firstly, the binary function code to be queried uses the same method as offline to generate a hash signature, and then quickly retrieves the hash signature in the function hash database, and finally obtains all the information in the library. Conditional homologous binary code information.

It should be noted that, in the method for retrieving homologous binary codes according to the embodiment of the present invention, the features of binary codes are encoded into coding vectors (feature vectors) by means of deep learning, so that locality-sensitive hashing can be used to accelerate and improve online matching. It can quickly retrieve code fragments similar to a given vulnerability binary code from massive firmware binary codes, and narrow the scope of subsequent manual analysis, so as to conduct risk assessment on firmware that may have vulnerability risks and provide analysis for vulnerability security researchers. Reference.

On the basis of the above embodiments, as an optional embodiment, the training method of the neural network model includes S201 and S202, specifically,

S201. Prepare a pair of sample functions that are known to be homologous or not, and input one control call information of the sample functions into two pre-built neural network models, where the two neural network models share parameters.

It should be noted that the neural network model of the embodiment of the present invention is trained by combining two models with shared parameters, so as to ensure that the coding result can use the cosine distance Cosine to measure the homology between the binary files represented by them.

S202: Calculate the cosine value between the coding vectors output by the two neural network models, input the cosine value and the homologous labels of the two sample functions into the loss function of the neural network model, and perform the analysis on the loss function according to the result of the loss function. Adjust the parameters of the neural network model;

Among them, the loss function is defined as:

W represents all parameters in the neural network model Φ; b ₁ and b ₂ represent the control call information of the two sample functions respectively; Φ(b ₁ ) and Φ(b ₂ ) represent the output of the neural network model Coding vector; π(b ₁ , b ₂ ) is used to characterize whether the two sample functions are homologous, the homolog is +1, and the sample function is -1 for different sources. The output is the distance between the two function encoding vectors using the Cosine metric, and back-propagation is performed on the training architecture through the sample function for the homologous label, the cosine of the two function encoding vectors and according to the definition of the loss function. As an optional embodiment, the neural network model in the embodiment of the present invention may adopt a deep learning coding model of Siamese architecture. The Siamese network learns a similarity measure from the data, and uses the learned measure to compare and match samples of new unknown classes.

On the basis of the above embodiments, as an optional embodiment, the control call information of the function is input into the pre-trained neural network model, and the encoding vector of the function is output, specifically:

Input the control call information into the pre-trained neural network model to perform iterative processing for a preset number of times. In each iteration process, for any basic block to be operated, the basic block to be operated depends on. The values of all other basic blocks after the last iteration are added, and then ReLU transformation is performed to obtain the first reference value; the value of the basic block to be operated after the last iteration is linearly transformed to obtain the second reference value; Taking the sum of the first reference frame and the second reference value as the value of the basic block to be operated after this iteration;

Fit the results of the last iteration of all basic blocks according to the fuzzy histogram method, and then go through a linear network transformation with a bias to output the encoding vector of the function;

The initial value of each basic block is the basic block level information of the basic block.

FIG. 2 is a dependency relationship diagram of updating basic block node attributes in an iterative process according to an embodiment of the present invention. As shown in FIG. 2 , in FIG. 2 , two iterations are used as an example. Represents the value of node v _i after the jth iteration, W ₂ X represents the fully connected layer in the neural network, which can also be understood as: a linear transformation is performed, that is, a matrix multiplication operation is performed, and after a fully connected layer Finally, the encoded vector of the function is obtained, and μ represents the output of the model. Among them, i is 1, 2 or 3, and j is 0, 1 or 2. Taking node v ₃ as an example, both v ₁ and v ₂ have edges pointing to v ₃ , so v ₃ depends on the node in each round of update. In addition to v ₃ , the attributes also include the attribute values of x ₁ and x ₂ at the end of the previous round, so when each round is updated, the new round value of x ₃ comes from the addition of x ₁ and x ₂ and then ReLU transformation and with The sum of the old value x ₃ transformed by W ₁ in the previous round.

Based on the foregoing embodiments, as an optional embodiment, the number of iterations is 3 to 5 times. It should be noted that theoretically, the more iterations, the more accurate the result. However, in the embodiment of the present invention, it is known through actual verification that after the iteration number is 3 to 5 times, the improvement of the accuracy can be ignored. Therefore, the embodiment of the present invention has The number of iterations in is set to be 3 to 5 times.

FIG. 3 is a schematic structural diagram of an apparatus for retrieving homologous binary codes provided by an embodiment of the present invention. As shown in FIG. 3 , the apparatus for retrieving homologous binary codes includes: a control call information generation module 301, a hash signature generation module 302 and a Retrieval module 303, where:

The control call information generation module 301 is used to determine all basic blocks of the function to be detected and the basic block level information of each basic block, generate a control flow graph of the function to be detected, and determine the one of all basic blocks according to the control flow graph. Dependency relationship between, the basic block level information and dependencies of all basic blocks are used as the control call information of the function to be detected;

Hash signature generation module 302, configured to input the control call information into the pre-trained neural network model, output the encoding vector of the function to be detected, and calculate the hash signature of the encoding vector as the hash to be retrieved sign;

The retrieval module 303 is used to retrieve whether there is a hash signature that is the same as the hash signature to be retrieved in the pre-built hash signature library, and if there is, the binary code corresponding to the retrieved hash signature is used as the Homologous binary code of the function to be instrumented.

The apparatus for retrieving homologous binary codes provided by the embodiments of the present invention specifically executes the process of the above embodiments of the retrieval methods for each homologous binary code. Repeat. The apparatus for retrieving homologous binary codes provided by the embodiments of the present invention encodes the features of binary codes into coding vectors (feature vectors) by means of deep learning, so that locality-sensitive hashing can be used for acceleration, the speed of online matching is improved, and the speed of online matching is improved. Retrieves code fragments similar to a given vulnerability binary code from massive firmware binary codes, and narrows the scope of subsequent manual analysis, so as to conduct risk assessment on firmware that may have vulnerability risks and provide analysis reference for vulnerability security researchers.

FIG. 4 is a schematic diagram of an entity structure of an electronic device provided by an embodiment of the present invention. As shown in FIG. 4 , the electronic device may include: a processor (processor) 410, a communications interface (Communications Interface) 420, a memory (memory) 430, and a communication The bus 440, wherein the processor 410, the communication interface 420, and the memory 430 complete the communication with each other through the communication bus 440. The processor 410 may call a computer program stored in the memory 430 and run on the processor 410 to execute the method for retrieving the homologous binary code provided by the above embodiments, for example, including: determining all basic blocks of the function to be detected and Basic block level information of each basic block, generate a control flow graph of the function to be detected, determine the dependencies among all basic blocks according to the control flow graph, and use the basic block level information and dependencies of all basic blocks as The control call information of the function to be detected; input the control call information into a pre-trained neural network model, output the encoding vector of the function to be detected, and calculate the hash signature of the encoding vector as the hash to be retrieved. Search for the hash signature that is the same as the hash signature to be retrieved in the pre-built hash signature library, and if so, use the binary code corresponding to the retrieved hash signature as the function to be detected homologous binary code.

In addition, the above-mentioned logic instructions in the memory 430 can be implemented in the form of software functional units and can be stored in a computer-readable storage medium when sold or used as an independent product. Based on this understanding, the technical solutions of the embodiments of the present invention are essentially, or the parts that make contributions to the prior art or the parts of the technical solutions can be embodied in the form of software products, and the computer software products are stored in a storage medium , including several instructions for causing a computer device (which may be a personal computer, a server, or a network device, etc.) to execute all or part of the steps of the methods described in the various embodiments of the present invention. The aforementioned storage medium includes: U disk, mobile hard disk, Read-Only Memory (ROM, Read-Only Memory), Random Access Memory (RAM, Random Access Memory), magnetic disk or optical disk and other media that can store program codes .

Embodiments of the present invention further provide a non-transitory computer-readable storage medium on which a computer program is stored, and when the computer program is executed by a processor, is implemented to execute the method for retrieving the homologous binary code provided by the above embodiments, for example Including: determining all basic blocks of the function to be detected and basic block level information of each basic block, generating a control flow graph of the function to be detected, determining the dependencies between all basic blocks according to the control flow graph, The basic block level information and dependencies of the basic block are used as the control call information of the function to be detected; the control call information is input into the pre-trained neural network model, the encoding vector of the function to be detected is output, and the The hash signature of the encoded vector is used as the hash signature to be retrieved; in the pre-built hash signature library, it is searched whether there is a hash signature that is the same as the hash signature to be retrieved. The binary code corresponding to the signature is used as the homologous binary code of the function to be detected.

The device embodiments described above are only illustrative, wherein the units described as separate components may or may not be physically separated, and the components shown as units may or may not be physical units, that is, they may be located in One place, or it can be distributed over multiple network elements. Some or all of the modules may be selected according to actual needs to achieve the purpose of the solution in this embodiment. Those of ordinary skill in the art can understand and implement it without creative effort.

From the description of the above embodiments, those skilled in the art can clearly understand that each embodiment can be implemented by means of software plus a necessary general hardware platform, and certainly can also be implemented by hardware. Based on this understanding, the above-mentioned technical solutions can be embodied in the form of software products in essence or the parts that make contributions to the prior art, and the computer software products can be stored in computer-readable storage media, such as ROM/RAM, magnetic A disc, an optical disc, etc., includes several instructions for causing a computer device (which may be a personal computer, a server, or a network device, etc.) to perform the methods described in various embodiments or some parts of the embodiments.

Finally, it should be noted that the above embodiments are only used to illustrate the technical solutions of the present invention, but not to limit them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that it can still be The technical solutions described in the foregoing embodiments are modified, or some technical features thereof are equivalently replaced; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the spirit and scope of the technical solutions of the embodiments of the present invention.

Claims (10)

1. a kind of search method of homologous binary code characterized by comprising

It determines all basic blocks of function to be detected and the atomic block level information of each basic block, generates the letter to be detected Several controlling stream graphs determines the dependence between all basic blocks according to the controlling stream graph, by the basic of all basic blocks The control recalls information of block level information and dependence as the function to be detected；

The control recalls information is input in neural network model trained in advance, the coding of the function to be detected is exported Vector calculates the hash signature of the coding vector, as hash signature to be retrieved；

Retrieval is with the presence or absence of hash signature identical with the hash signature to be retrieved in the hash signature library constructed in advance, if In the presence of then using the corresponding binary code of the hash signature retrieved as the homologous binary code of the function to be detected.

2. search method according to claim 1, which is characterized in that the training method of the neural network model are as follows:

Prepare it is a pair of known whether homologous sample function, respectively input an institute in the neural network model constructed in advance to two State the control recalls information of sample function, described two neural network model shared parameters；

The cosine value between the coding vector of two neural network models output is calculated, by the cosine value and described two samples The same source marking of function is input to the loss function of neural network model, according to the result of loss function to the neural network mould The parameter of type is adjusted；

Wherein, the loss function is defined as:

W represents all parameters in neural network model Φ；b₁And b₂Respectively indicate the control recalls information of two sample functions； Φ(b₁) and Φ (b₂) respectively indicate neural network model output two sample functions coding vector；π(b₁,b₂) it is used for table Whether homologous levy two sample functions.

3. search method according to claim 1 or 2, which is characterized in that the control recalls information by the function It is input in neural network model trained in advance, exports the coding vector of the function, specifically:

The control recalls information is input to the iterative processing that preset times are carried out in neural network model trained in advance, In Each time in iterative process, for any one basic block to be operated, the basic block to be operated is relied on other Value of all basic blocks after upper primary iteration is added, then carries out ReLU transformation, obtains the first reference value；It will be described to be operated Value of the basic block after upper primary iteration carries out linear transformation, obtains the second reference value；By the first reference frame and the second reference value Value of the sum as the basic block wait operate after current iteration；

According to fuzzy histogram method, by all basic blocks, last result for taking turns iteration is fitted, using the line with biasing Property network transformation, exports the coding vector of the function；

Wherein, the initial value of each basic block is the atomic block level information of the basic block.

4. the search method of homologous binary code according to claim 1, which is characterized in that the atomic block level letter Breath include the quantity of the character string constant in basic block, the quantity of digital constant, the quantity of escape instruction, call instruction number Amount, the quantity of arithmetic instruction, the quantity of assembly instruction, the quantity of child node and intermediary's centrad.

5. the search method of homologous binary code according to claim 1, which is characterized in that the control recalls information For band property control calling figure ACFG, each node in property control calling figure ACFG is one and has attribute set Basic block.

6. the search method of homologous binary code according to claim 1, which is characterized in that the determination letter to be detected The atomic block level information of several all basic blocks and each basic block, specifically: the binary program is carried out reverse Partition function operation obtains several functions to be detected, all basic blocks of each function to be detected and each basic block Atomic block level information.

7. the search method of homologous binary code according to claim 3, which is characterized in that the number of iterations is 3 To 5 times.

8. a kind of retrieval device of homologous binary code characterized by comprising

Recalls information generation module is controlled, for determining all basic blocks of function to be detected and the basic block of each basic block Level information generates the controlling stream graph of the function to be detected, according to the controlling stream graph determine between all basic blocks according to The relationship of relying calls letter using the atomic block level information of all basic blocks and dependence as the control of the function to be detected Breath；

Hash signature generation module, it is defeated for the control recalls information to be input in neural network model trained in advance The coding vector of the function to be detected out, calculates the hash signature of the coding vector, as hash signature to be retrieved；

Retrieval module, for retrieving in the hash signature library constructed in advance with the presence or absence of identical as the hash signature to be retrieved Hash signature, and if it exists, then using the corresponding binary code of the hash signature retrieved as the same of the function to be detected Source binary code.

9. a kind of electronic equipment including memory, processor and stores the calculating that can be run on a memory and on a processor Machine program, which is characterized in that the processor is realized homologous two as described in any one of claim 1 to 7 when executing described program The step of search method of carry system code.

10. a kind of non-transient computer readable storage medium, which is characterized in that the non-transient computer readable storage medium is deposited Computer instruction is stored up, it is homologous as claimed in any of claims 1 to 7 in one of claims that the computer instruction executes the computer The search method of binary code.