CN103473104A - Method for discriminating re-package of application based on keyword context frequency matrix - Google Patents

Abstract

An application repackaging identification method based on the keyword context frequency matrix is applied to the Android system. First, the application file is processed to obtain the smali code file, and then the smali code is processed, the operator sequence is extracted, and the keyword information is counted. A specific type of keywords is used to construct context-related feature triples to generate a feature matrix based on context frequency, and the feature matrix of the application is compared in pairs, and the similarity between the two applications is obtained according to the similarity of the matrix. Finally, combined with author information and other content, it is judged whether there is a repackaging relationship between applications. With the technical solution provided by the present invention, repackaged Android applications can be discriminated, while avoiding the extra overhead of performing giant character string hash processing on the entire application; it does not depend on the binary code order of the original file; by limiting the size of the feature matrix size, reducing space overhead; improving the execution efficiency of Android application repackaging discrimination.

Description

A Applied Repackaging Discrimination Method Based on Keyword Context Frequency Matrix

technical field

The present invention relates to an application repackaging identification method based on a keyword context frequency matrix, and in particular to a processing method for identifying application repackaging by using an application code keyword frequency matrix under an Android platform.

Background technique

Android (Android) system is a Linux-based free and open source operating system developed and promoted by Google, mainly used in mobile devices, such as smartphones or tablets. The Android system is currently the mobile phone operating system with the largest market share in the world. According to official data, there are more than 975,000 applications on the Android system.

Usually, Android system applications are developed and released by third-party developers, which brings about a problem, that is, application repackaging. Application repackaging means that some developers grab applications released by other developers through different channels, and modify existing applications through decompilation, binary code insertion and other technologies (such as implanting malicious code, modifying developer information, etc.) , modify permissions, crack protected content, etc.), and then repackage and release. This raises many issues about copyright, security, authorship, privacy protection, malicious code implantation and so on.

Silvio Cesare and Yang Xiang summarized several solutions for software similarity and cluster analysis in the book "Software Similarity and Classification": for example, through string analysis, the code text is compared for similarity, and then the software similarity is obtained information; and compare the software similarity according to the statistical results by counting the frequency of code words. These solutions, however, do not take into account the special circumstances associated with mobile platform applications.

In 2012, Wu Zhou, Yajin Zhou, et al. of the University of Southern California proposed another solution (CODASPY'12 paper): using obfuscated hash technology to extract application features, and then use obfuscated hash to generate application fingerprints, and then Using the rolling hash technology, the fingerprint is generated as a feature vector, and by comparing the similarity of the feature vectors of the two applications, it is judged whether there is a software repackaging problem. This method needs to analyze all codes, which is complex and inefficient, and depends on the order of code text, and cannot handle the situation of modifying code by inserting useless code, code obfuscation, function renaming, changing code order, etc.

Contents of the invention

The purpose of the present invention is to provide a new method, so that with less overhead and faster time, a number of Android applications given are preprocessed to obtain a feature matrix based on the keyword context frequency. Degree calculation, clustering, and information on which of these Android applications are repackaged applications.

The principle of the present invention is as follows: firstly, the application program file (apk file) is processed to obtain the smali code file, and the smali code is an intermediate representation of the binary code of the original application program. Then process the smali code, extract the operator sequence, count the keyword information, construct a context-related feature triplet <K1,i,K2> for each specific type of keyword, and generate a feature matrix based on the context frequency. The feature matrix of the program is compared in pairs, and the similarity of the two applications is obtained according to the similarity of the matrix. Finally, combined with author information and other content, it is judged whether there is a repackaging relationship between applications.

The technical scheme provided by the invention is as follows:

An application repackaging identification method based on a keyword context frequency matrix, which is applied to the Android system, is characterized in that it includes the following steps (see Figure 9 for the flow process):

A. Preprocess the application file, convert the binary code into a smali code file, extract the author's signature information of the application, and construct a keyword vector;

B. Process the smali code file to generate a smali operator sequence;

C. generate keyword context frequency matrix;

D. Compare the similarity of the application keyword context frequency matrix to determine whether the application is a repackaged application.

The method for identifying application repackaging is characterized in that step A includes:

A1. Extract the Android application binary code file and the author's signature information file in the META-INFO file;

A2. Use existing tools to convert the binary code into a smali code file;

A3. Use existing tools to extract the content of the author's signature from the corresponding file;

A4. Construct keyword vectors.

The method for identifying application repackaging is characterized in that step B includes:

B1. Process the smali code file obtained in step A, and remove the third-party library files (mainly some advertising libraries, social platform libraries, etc.);

B2. Processing the smali code file obtained in step B1, stripping off all other information except the operator in each statement, and obtaining a smali operator sequence of an application program.

The method for identifying application repackaging is characterized in that step C includes:

C1. Construct the keyword context frequency matrix Max;

C2. According to the selected keyword vector, for each keyword, each occurrence in the smali operator sequence obtained in step B, using the hash algorithm, combine the above K statements and the following K statements Mapped to integers K1 and K2 respectively, wherein the corresponding subscript of the keyword in the keyword vector is i;

C3. Increase the count of Max[i][K1][K2] corresponding to the position of the feature matrix.

The method for identifying application repackaging is characterized in that step D includes:

D1. For a given Android application, calculate the similarity of its keyword context frequency matrix, and use this as a standard to compare two Android applications in pairs;

D2. Cluster the Android applications whose similarity calculation results of the keyword context frequency matrix exceed the specified threshold, and think that this type of Android applications may have a repackaging problem;

D3. Combining with the author's signature information obtained in step A, further screen and check the judgment results of step D2.

The method for identifying application repackaging is characterized in that, in step D1, the method for calculating the similarity of its keyword context frequency matrix is as follows: set the original application program (that is, the original application program that has not been repackaged) and the application program to be judged The keyword context frequency matrix of the program is respectively Max1 and Max2. Each bit of the two matrices is represented by Max1[i][j][k] and Max2[i][j][k], and the calculation of these two The minimum value of the number Min[i][j][k], use score to represent its similarity score, score=200*ΣMin[i][j][k]/Σ(Max1[i][j][ k]+Max2[i][j][k]).

The application repackaging identification method is characterized in that, in step D2, the threshold is 70.

The method for distinguishing application repackaging is characterized in that in step A4, the operator corresponding to the following instructions is selected as a keyword: transfer instruction, function call instruction, comparison instruction, statement instruction, operation instruction, transfer instruction, throw Exception instruction.

The described application repackaging method is characterized in that, in step A4, the following operators are selected as keywords: if, goto, invoke_virtual, invoke_static, invoke_direct, add-int/lit8, move_result_object, new-array, const/4 , const/16, const-string, throw, new-instance, cmpl-float, and-int/lit1.

Beneficial effects of the present invention: With the technical solution provided by the present invention, the repackaged Android application program can be discriminated, while avoiding the extra overhead of performing giant string hash processing on the entire application program; it does not depend on the binary code sequence of the original file ; By limiting the size of the feature matrix, the space overhead is reduced; and the execution efficiency of Android application repackaging discrimination is improved.

Description of drawings

Fig. 1 is the application program preprocessing flow of the present invention.

Fig. 2 is the flow chart of generating smali operator sequence in the present invention.

Fig. 3 is the process flow of generating keyword context frequency matrix in the present invention.

Fig. 4 is the judging process of the repacking result of the present invention.

Fig. 5 is a flow chart of application program preprocessing provided by the embodiment of the present invention.

Fig. 6 is a flow chart of generating a smali operator sequence provided by an embodiment of the present invention.

Fig. 7 is a flow chart of generating a keyword context frequency matrix provided by an embodiment of the present invention.

Fig. 8 is a flow chart of judging the repacking result provided by the embodiment of the present invention.

Fig. 9 is a flowchart of the method of the present invention.

Detailed ways

The specific embodiment of the present invention is as follows:

A. When preprocessing the application file, do the following:

A1. Extract the Android application binary code file and the author's signature information file in the META-INFO file;

A2. Use existing tools, such as backsmali (https://code.google.com/p/smali/), to convert the binary code (.dex file) into a smali code file;

A3. Use existing tools, such as keytool (JDK (Java Development Kit) development component tool), to extract the author's signature content from the corresponding file (CERT.RSA);

A4. Construct keyword vectors. The basis for selecting keywords is to select sentences with a relatively high frequency of occurrence; there is no obvious repetition of keywords in semantics, that is, the keyword set can cover sentences with different functions; select semantically important instructions , such as operation instructions, function call instructions, etc.

B. In the part of generating the smali operator sequence, perform the following operations:

B1. Process the smali code file obtained in step A2, remove the third-party library files, mainly some advertising libraries, such as Admob, AirPush, LeadBolt, InMobi, etc., social platform libraries, such as Facebook, OpenFeint, HeyZap, etc., and other development Third-party libraries used;

B2. Process the smali code file obtained in step B1, and strip all other information except operators in each statement, such other information includes operands, and some other identifiers, such as '#', '.', etc. , to get a sequence of smali operators for an application.

C. In the part of generating keyword context frequency matrix, perform the following operations:

C1. Construct the keyword context frequency matrix Max, which is a three-dimensional matrix with a size of sz_kv*sz_hash*sz_hash, where sz_kv is the size of the selected keyword vector, and sz_hash is the value of the hash algorithm result taken in step C2 Range size, initialize each bit of Max to 0;

C2. According to the selected keyword vector, for each occurrence of each keyword (the corresponding subscript in the keyword vector is i) in the smali operator sequence obtained in step B2, use a specific hash algorithm to convert it to The above K (K is a self-defined integer) statement and the following K statement are mapped to integers K1 and K2 respectively;

C3. Increase the count of Max[i][K1][K2] corresponding to the position of the feature matrix.

D. When judging the repacking result, perform the following operations:

D1. For a given Android application, use a specific algorithm to calculate the similarity of its keyword context frequency matrix, and use this as a standard to compare two Android applications; here, compare the similarity of the keyword context frequency matrix The algorithm is to set the two matrices as Max1 and Max2 respectively, and express each bit of the two matrices as Max1[i][j][k] and Max2[i][j][k] respectively, and calculate this The minimum value of two numbers Min[i][j][k], use score to represent its similarity score, score=200*ΣMin[i][j][k]/Σ(Max1[i][j] [k]+Max2[i][j][k]);

D2. Cluster the Android applications whose similarity calculation result of the keyword context frequency matrix (that is, the score in step D1) exceeds a certain threshold. According to empirical results, when the threshold is selected as 70, it is the best, and this type of application is considered Android apps may have repackaging issues.

D3. Combining the author's signature information obtained in step A3, further screen and check the results of step D2. Similar applications with the same author information are generally different versions of the same application, and do not belong to repackaged applications. Similar applications with different author information The program is judged as a repackaged application.

The present invention will be further described below by example.

Example 1:

Suppose an Android application, whose Chinese name is "Automatic Desktop Photo Filter", needs to detect whether it is a repackaged application, and its package name is AutodeskzhaopianlvjingPixlr_o_matic_V2.2.1_mumayi_ac32a.apk.

A. The preprocessing process includes the following steps:

A1. After decompressing the apk program package, you can get several files and folders, among which the class.dex file is the binary code file of the application program, and the CERT.RSA file under the META-INFO folder is the author's signature information;

A2. Use the backsmali tool to convert the class.dex file into a smali code file, and a folder will be generated, including multiple .smali files;

A3. Use the keytool tool to extract the author's signature content from CERT.RSA, and enter the keytool-printcert-fileCERT.RSA command to get some information about the application, including the owner, publisher, serial number, validity period, and certificate fingerprint.

A4. Construct keyword vectors. According to the experimental results, we choose the following 15 operators as keywords, namely if, goto, invoke_virtual, invoke_static, invoke_direct, add-int/lit8, move_result_object, new-array, const/4, const/16, const-string, throw, new-instance, cmpl-float, and-int/lit1, these 15 operators represent a variety of instructions, including transfer instructions, function call instructions, comparison instructions, Statement instructions, operation instructions, transfer instructions, and exception throw instructions, each operator corresponds to a subscript of the keyword vector;

B. Generate a smali operator sequence flow, including the following steps:

B1. Process the smali code file obtained by preprocessing, and remove the third-party library file. For example, if the apk contains admob advertising library, delete all corresponding smali files;

B2. To process the smali code file obtained in B1, strip all other information except the operator in each statement, such other information includes operands, and some other identifiers, such as '#', '.', etc., Get an application's smali operator sequence. In the smali file, the format of each statement is "operator operand", and the operand is the variable name or register name of the specific operation, which can be automatically completed by string processing. After this step, a smali operator sequence is obtained Text, where each line is an operator, some of which may match our selected keywords.

C. Generate keyword context frequency matrix process, including the following steps:

C1. Construct the keyword context frequency matrix Max, which is a three-dimensional matrix with a size of sz_kv*sz_hash*sz_hash, where sz_kv is the size of the selected keyword vector, which has been determined to be 15, and sz_hash is the hash taken in the next step The value range of the algorithm result, according to the empirical results, set it to 67, and initialize each bit of Max to 0;

C2. According to the selected keyword vector, for each occurrence of each keyword (the corresponding subscript in the keyword vector is i) in the smali operator sequence obtained in the previous step, use the BKDRHash algorithm (for the BKDRHash algorithm, see http ://www.nocow.cn/index.php/BKDRHash; other string hash algorithms can also be used here, such as ELFHASH, SDBMHash, RSHash, etc.), and the above K statements and the following K statements are respectively Mapped to integers K1 and K2, for example, according to string matching, an occurrence of the keyword invoke-static corresponding to the keyword vector subscript i=3 is detected, and its context is the following instruction sequence,

line

try_start_0

iget_object

invoke-static

move-result-object

const-string

invoke-virtual;

According to the BKDRHash algorithm, hash operations are performed on the context respectively, and K1=17, K2=33 are obtained;

C3. Increase the count of Max[i][K1][K2] corresponding to the position of the feature matrix. In this example, perform the operation of Max[3][17][33]++.

D. Repackage result judgment process, perform the following operations:

D1. For a given Android application, use a specific algorithm to calculate the similarity of its keyword context frequency matrix, and use this as a standard to compare two Android applications. Suppose that according to the previous similar steps, we get Autodeskzhaopiantexiaochulihanhuaban_Pixlr_o_matic_V2.1.2_mumayi_1f341.apk application and the keyword context frequency matrix of AutodeskzhaopianlvjingPixlr_o_matic_V2.2.1_mumayi_ac32a.apk application. Let the two matrices be Max1 and Max2 respectively. For each bit of the two matrices, use Max1[i][j][k] and Max2[i][j][k] indicate that the minimum value Min[i][j][k] of these two numbers is calculated, and the similarity score is expressed by score , score=200*ΣMin[i][j][k]/Σ(Max1[i][j][k]+Max2[i][j][k]), according to the calculation, score=86.8871;

D2. Cluster the results of the similarity calculation of the keyword context frequency matrix, that is, the score in step D1, and Android applications exceeding a certain threshold. According to empirical results, it is optimal when the threshold is selected as 70, where 86.8871 is greater than 70, Therefore, it is judged that these two Android applications may have repackaging problems.

D3. Combined with the author's signature information obtained above, further screen the results and find that the author information of the two applications is different, and further determine that the two applications are repackaged applications.

Claims (10)

1. the bag discriminating conduct is beaten again in the application based on keyword context frequency matrix, is applied to Android system, it is characterized in that, comprises the steps:

A. the application programs file carries out pre-service, and binary code is converted to the smali code file, extracts author's signing messages of application program and construct the keyword vector;

B. the smali code file is processed, generated smali operational character sequence;

C. generate keyword context frequency matrix;

D. contrast the similarity of application program keyword context frequency matrix, judge whether the attach most importance to packing application of this application program.

2. the bag discriminating conduct is beaten again in application as claimed in claim 1, it is characterized in that, steps A comprises:

A1. extract the author's signing messages file in Android application binaries code file and META-INFO file;

A2. use existing instrument, binary code is converted to the smali code file;

A3. use existing instrument, from corresponding document, extract author's signature contents;

A4. construct the keyword vector.

3. the bag discriminating conduct is beaten again in application as claimed in claim 1, it is characterized in that, step B comprises:

B1. the smali code file obtained in steps A is processed, removed the third party library file;

B2. the smali code file obtained in step B1 is processed, other all information beyond the operational character in every statement are peeled off, obtain the smali operational character sequence of an application program.

4. the bag discriminating conduct is beaten again in application as claimed in claim 1, it is characterized in that, step C comprises:

C1. construct keyword context frequency matrix Max;

C2. according to selected keyword vector, to each keyword, appearance each time in the smali operational character sequence obtained at step B, adopt hash algorithm, by it, K bar statement above and K bar statement hereinafter are mapped as respectively integer K 1 and K2, wherein, described keyword is designated as i under correspondence in the keyword vector;

C3. increase eigenmatrix correspondence position Max[i] [K1] [K2] counting.

5. the bag discriminating conduct is beaten again in application as claimed in claim 1, it is characterized in that, step D comprises:

D1. to given Android application program, calculate the similarity of its keyword context frequency matrix, using this as standard, two Android application programs are compared in twos;

D2. the similarity result of calculation of keyword context frequency matrix is surpassed to the Android application program cluster of assign thresholds, think that may there be the bag problem of beating again in the Android application program of this class.

6. the bag discriminating conduct is beaten again in application as claimed in claim 5, it is characterized in that, step D further comprises:

D3. the author's signing messages obtained in integrating step A, further screen investigation to the result of determination of step D2.

7. the bag discriminating conduct is beaten again in application as claimed in claim 5, it is characterized in that, in step D1, the method of calculating the similarity of its keyword context frequency matrix is: the keyword context frequency matrix of establishing former application program and application program to be judged is respectively Max1, Max2, to each of two matrixes, use respectively Max1[i] [j] [k] and Max2[i] [j] [k] expression, calculate the minimum M in[i of this two number] [j] [k], mean its similarity score with score, score=200* Σ Min[i] [j] [k]/Σ (Max1[i] [j] [k]+Max2[i] [j] [k]).

8. the bag discriminating conduct is beaten again in application as claimed in claim 5, it is characterized in that, in step D2, described threshold value is 70.

9. the bag discriminating conduct is beaten again in application as claimed in claim 2, it is characterized in that, in steps A 4, select as the corresponding operational character that gives an order as keyword: transfer instruction, function call instruction, comparison order, the instruction of statement class, operational order, move instruction, throw exception instruction.

10. the bag discriminating conduct is beaten again in application as claimed in claim 2, it is characterized in that, in steps A 4, select following operational character as keyword: if, goto, invoke_virtual, invoke_static, invoke_direct, add-int/lit8, move_result_object, new-array, const/4, const/16, const-string, throw, new-instance, cmpl-float, and-int/lit1.

Images