CN111857811B - Construction method of resource flow graph - Google Patents
Construction method of resource flow graph Download PDFInfo
- Publication number
- CN111857811B CN111857811B CN202010741701.6A CN202010741701A CN111857811B CN 111857811 B CN111857811 B CN 111857811B CN 202010741701 A CN202010741701 A CN 202010741701A CN 111857811 B CN111857811 B CN 111857811B
- Authority
- CN
- China
- Prior art keywords
- type
- variables
- statement
- parameter
- block
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F8/00—Arrangements for software engineering
- G06F8/70—Software maintenance or management
- G06F8/74—Reverse engineering; Extracting design information from source code
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Stored Programmes (AREA)
Abstract
The application discloses a construction method of a resource flow graph, which comprises the following steps: s100, generating a corresponding abstract syntax tree from a source code file through a converter; s200, respectively defining variables and sentences to be analyzed in each method, wherein the variables are defined as unassigned variables, assigned variables and parameter variables; s300, traversing all abstract syntax trees, finding out each method in the abstract syntax trees, and establishing an index taking the name and the parameter type of the abstract syntax tree as a main key value; s400, processing each parameter variable in the method; s500, processing all assigned variables in the method; s600, processing all unassigned variables in the method. The resource flow graph construction of the application can be directly generated through the grammar tree without generating a large number of intermediate results, and can analyze the flow direction of data through the resource flow graph, thereby saving a large amount of time and space.
Description
Technical Field
The application belongs to the technical field of computers, and particularly relates to a construction method of a resource flow graph.
Background
In the static analysis field, generally, the steps of program analysis are to analyze codes to generate corresponding grammar trees, then to regenerate the grammar trees into intermediate code representations, to generate basic blocks through the intermediate codes, and to construct control flow diagrams on the basis of the basic blocks. And constructing a data flow graph through the control flow graph. Most of the constructed control flow graphs are primarily prepared for later generation of the data flow graph. This construction produces many intermediate results, which are not important in subsequent analysis, which wastes a lot of storage space and computational resources.
Disclosure of Invention
The application aims to overcome the defects in the prior art and provide a construction method of a resource flow graph, which can be directly generated through a grammar tree without generating a large number of intermediate results, can analyze the flow direction of data through the resource flow graph and saves a large amount of time and space.
The aim of the application is achieved by the following technical scheme: the method for constructing the resource flow graph comprises the following steps:
s100, generating a corresponding abstract syntax tree from a source code file through a converter;
s200, respectively defining variables and sentences to be analyzed in each method, wherein the variables are defined as unassigned variables, assigned variables and parameter variables;
s300, traversing all abstract syntax trees, finding out each method in the abstract syntax trees, and establishing an index taking the name and the parameter type of the abstract syntax tree as a main key value;
s400, processing each parameter variable in the method;
s500, processing all assigned variables in the method;
s600, processing all unassigned variables in the method.
As a further improvement, the unassigned variables in step S200 are initialized but unassigned variables, the parameter variables are parameters of the method and do not include the basic type of variables, and the assigned variables are variables declared and initialized in the method.
As a further improvement, the sentences to be analyzed in each method are defined as six types of jumps, return values, if branches, try blocks, ends and other common sentences, wherein the jump types are sentences which throw exceptions in the try sentences, the return values are sentences containing return, the If branches are entry points of the If blocks, the try blocks are entry points of the try blocks, and the ends are positions where the method ends.
As a further improvement, the step S400 specifically includes the following steps:
s401, judging whether the type of the parameter variable in the method is a basic type, if so, returning to the step S200, otherwise, entering into the step S402;
s402, traversing all sentences related to parameter variables in the method.
As a further improvement, in the step S402, all the sentences related to the parameter variables are traversed, and the statement type judgment is specifically expressed as follows:
a) Judging whether the statement is of a return value type, if so, setting the type of the statement as a return value and returning to the step S402;
b) Judging whether the type of the try block is the try block type, if yes, analyzing sentences in the try block one by one, and returning to the step S402;
c) Judging whether the type is If branch type, if yes, firstly judging whether the expression of If branch is related to the analyzed parameter; next, the step S402 is returned after analysis of the then block statement in the if; again, return to step S402 after analysis of the else block statement in if;
d) If other common sentences are adopted, the method is specifically expressed as follows:
if the method is a method call statement, the method call statement is divided into a caller and a callee, wherein the caller calls the method by the found parameters, and the callee is used as the parameters in the method;
if the value is the assignment statement, whether the initialization of the statement is a method call or whether the assignment object is a basic data type is judged, if the assignment object is not the basic data type or the initialization value of the statement is the method call.
As a further improvement, the step B) specifically includes the following processes:
processing the catch block, recording each accepted exception type, and then processing the statement in the catch block;
judging whether the finaliy block is contained or not, and processing the finaliy block;
analyzing the try block to judge the type of the sentence;
returning to step S402.
As a further improvement, the step S500 specifically includes the following steps:
s501, traversing all sentences in the method;
s502, judging whether the statement is related to the assignment variable, if so, recording the assignment variable, returning to the step S402, otherwise, entering the step S600.
As a further improvement, the step S502 is specifically expressed as:
traversing the rest sentences, and searching sentences related to the assignment variable;
when encountering a return statement, adding an end statement to the next node of the return statement;
if the variable is located in the assignment statement in the statement and the variable is located in the parameter, step S502 is repeated and the statement is marked, and the statement is not analyzed independently the next time.
As a further improvement, the step S600 is specifically expressed as:
searching all method calls;
and judging the type of the father node of the type until the type of the father node is other blocks.
As a further improvement, the following procedure is further included between the step S300 and the step S400: each analysis begins with taking one of the index values.
The application provides a construction method of a resource flow graph, which comprises the steps of firstly, generating a corresponding abstract syntax tree from a source code file through a converter; secondly, respectively defining variables and sentences to be analyzed in each method, wherein the variables are defined as unassigned variables, assigned variables and parameter variables; then, traversing all abstract syntax trees, finding each method in the abstract syntax trees, and establishing an index taking the name and the parameter type of the abstract syntax tree as a main key value; finally, each parameter, assigned variable and unassigned variable in the method are sequentially processed, compared with the original analysis thought of static analysis, the method constructs a resource flow diagram combining the characteristics of the original control flow diagram and the original data flow diagram, can directly generate on the basis of a grammar tree, can directly analyze some variables in the flow diagram, and saves a great amount of time and space.
Drawings
The application will be further described with reference to the accompanying drawings, in which embodiments do not constitute any limitation of the application, and other drawings can be obtained by one of ordinary skill in the art without inventive effort from the following drawings.
FIG. 1 is a flow diagram of one embodiment of a method of constructing a resource flow graph.
FIG. 2 is a flow chart of another embodiment of a method of constructing a resource flow graph.
Fig. 3 is a flowchart of step S500 of the present application.
Detailed Description
In order to make the technical solution of the present application better understood by those skilled in the art, the present application will be described in further detail with reference to the accompanying drawings and the specific embodiments, and it should be noted that the embodiments of the present application and features in the embodiments may be combined with each other without conflict.
As shown in fig. 1, the method for constructing a resource flow graph provided by the embodiment of the application includes the following steps:
s100, generating a corresponding abstract syntax tree from a source code file through a converter;
s200, respectively defining variables and sentences to be analyzed in each method, wherein the variables are defined as unassigned variables, assigned variables and parameter variables; specifically, the unassigned variables are initialized but unassigned variables, the parameter variables are parameters of the method, the parameters do not include the basic type variables, and the assigned variables are parameters of the variables declared and initialized in the method; the statement is defined as six types of jump, return value, if branch, try block, end and other common statements, wherein the jump type is a statement which can be exploded out of the try statement, the return value type is a statement containing return, the If branch type is an entry point of the If block of the statement, the try block type is an entry point of the try block, and the end type is a position where the method ends;
s300, traversing all abstract syntax trees, finding out each method in the abstract syntax trees, and establishing an index taking the name and the parameter type of the abstract syntax tree as a main key value;
s400, processing each parameter variable in the method;
s500, processing all assigned variables in the method;
s600, processing all unassigned variables in the method.
In a further preferred embodiment of the present application, the following procedure is further included between the step S300 and the step S400: each analysis begins with taking one of the index values.
As a further preferred embodiment, step S400 specifically includes the following procedure:
s401, judging whether the type of the parameter variable in the method is a basic type, if so, returning to the step S200, otherwise, entering into the step S402;
s402, traversing all sentences related to parameter variables in the method; it should be noted that, in this step, all the sentences related to the parameter variables are traversed, and the concrete expression of the sentence type judgment is as follows:
a) Judging whether the statement is of a return value type, if the statement is of a return value type, setting the type of the statement to the return value, returning to the step S402, preferably, setting the type of the statement to the return value in the step, judging the type of the returned expression, and if the statement is of a method call, putting the position of the expression in front of the return value;
b) Judging whether the type of the try block is the try block type, if yes, analyzing sentences in the try block one by one, and returning to the step S402; it should be noted that, the process of analyzing the sentences in the try block one by one in the application is as follows:
processing the catch block, recording each accepted exception type, and then processing the statement in the catch block;
judging whether the finaliy block is contained or not, and processing the finaliy block;
analyzing the try block to judge the type of the sentence; it should be noted that, this process is consistent with the process of statement type determination in step S402, and then it is further required to determine whether the statement may throw an exception, and if so, change the type of the statement into skip and point to the corresponding catch block position;
c) Judging whether the type is If branch type, if yes, firstly judging whether the expression of If branch is related to the analyzed parameter; next, the step S402 is returned after analysis of the then block statement in the if; again, return to step S402 after analysis of the else block statement in if;
d) If other common sentences are adopted, the method is specifically expressed as follows:
if the method is a method call statement, the method call statement is divided into a caller and a callee, wherein the caller calls the method by the found parameters, and the callee is used as the parameters in the method;
if the value is the assignment statement, whether the initialization of the statement is a method call or whether the assignment object is a basic data type is judged, if the assignment object is not the basic data type or the initialization value of the statement is the method call.
The above process is specifically seen in fig. 2.
Meanwhile, as shown in fig. 3, the step S500 specifically includes the following steps:
s501, traversing all sentences in the method;
s502, judging whether the statement is related to the assignment variable, if so, recording the assignment variable, returning to the step S402, otherwise, entering the step S600.
Specifically, step S502 includes the following:
traversing the rest sentences, and searching sentences related to the assignment variable;
when encountering a return statement, adding an end statement to the next node of the return statement;
if the variable is located in the assignment statement in the statement and the variable is located in the parameter, the step S502 is repeated and the statement is marked, and the statement is not independently analyzed the next time
It should be noted that, the step S600 of the present application is specifically expressed as follows:
searching all method calls;
and judging the type of the father node of the type until the type of the father node is other blocks.
Therefore, the application firstly, the source code file is converted into the corresponding abstract syntax tree through the converter; secondly, respectively defining variables and sentences to be analyzed in each method, wherein the variables are defined as unassigned variables, assigned variables and parameter variables; then, traversing all abstract syntax trees, finding each method in the abstract syntax trees, and establishing an index taking the name and the parameter type of the abstract syntax tree as a main key value; finally, each parameter, assigned variable and unassigned variable in the method are sequentially processed, compared with the original analysis thought of static analysis, the method constructs a resource flow diagram combining the characteristics of the original control flow diagram and the original data flow diagram, can directly generate on the basis of a grammar tree, can directly analyze some variables in the flow diagram, and saves a great amount of time and space.
In the description above, numerous specific details are set forth in order to provide a thorough understanding of the present application, however, the present application may be practiced in other ways than those described herein, and therefore should not be construed as limiting the scope of the present application.
In summary, while the above-described preferred embodiments have been described, it should be noted that although various changes and modifications can be made by those skilled in the art, it is intended that such changes and modifications be included within the scope of the present application unless they depart from the scope of the present application.
Claims (7)
1. The construction method of the resource flow graph is characterized by comprising the following steps:
s100, generating a corresponding abstract syntax tree from a source code file through a converter;
s200, respectively defining variables and sentences to be analyzed in each method, wherein the variables are defined as unassigned variables, assigned variables and parameter variables;
s300, traversing all abstract syntax trees, finding out each method in the abstract syntax trees, and establishing an index taking the name and the parameter type of the abstract syntax tree as a main key value;
s400, processing each parameter variable in the method;
s500, processing all assigned variables in the method;
s600, processing all unassigned variables in the method;
the step S400 specifically includes the following steps:
s401, judging whether the type of the parameter variable in the method is a basic type, if so, returning to the step S200, otherwise, entering into the step S402;
s402, traversing all sentences related to parameter variables in the method;
the step S500 specifically includes the following steps:
s501, traversing all sentences in the method;
s502, judging whether the statement is related to the assignment variable, if so, recording the assignment variable, returning to the step S402, otherwise, entering the step S600;
the step S600 is specifically expressed as:
searching all method calls;
and judging the type of the father node of the type until the type of the father node is other blocks.
2. The method according to claim 1, wherein the unassigned variables in step S200 are initialized but unassigned variables, the parameter variables are parameters of the method and do not include basic types of variables, and the assigned variables are variables declared and initialized in the method.
3. The method for constructing a resource flow graph according to claim 2, wherein the sentences to be analyzed in each method are defined as six types of jump, return value, if branch, try block, end and other common sentences, wherein the jump type is a sentence in which an exception is thrown in the try sentence, the return value type is a sentence containing return, the If branch type is an entry point of an If block of the sentence, the try block type is an entry point of the try block, and the end type is a position where the method ends.
4. The method for constructing a resource flow graph according to claim 1, wherein in step S402, all statements related to parameter variables are traversed, and statement type judgment is specifically performed as follows:
a) Judging whether the statement is of a return value type, if so, setting the type of the statement as a return value and returning to the step S402;
b) Judging whether the type of the try block is the try block type, if yes, analyzing sentences in the try block one by one, and returning to the step S402;
c) Judging whether the type is If branch type, if yes, firstly judging whether the expression of If branch is related to the analyzed parameter; next, the step S402 is returned after analysis of the then block statement in the if; again, return to step S402 after analysis of the else block statement in if;
d) If other common sentences are adopted, the method is specifically expressed as follows:
if the method is a method call statement, the method call statement is divided into a caller and a callee, the caller calls the method for the found parameter, and the callee is used as the parameter in the method;
if the value is the assignment statement, whether the initialization of the statement is a method call or whether the assignment object is a basic data type is judged.
5. The method for constructing a resource flow graph according to claim 4, wherein the step B) specifically includes the following steps:
processing the catch block, recording each accepted exception type, and then processing the statement in the catch block;
judging whether the finaliy block is contained or not, and processing the finaliy block;
analyzing the try block to judge the type of the sentence;
returning to step S402.
6. The method for constructing a resource flow graph according to claim 1, wherein the step S502 is specifically expressed as:
traversing the rest sentences, and searching sentences related to the assignment variable;
when encountering a return statement, adding an end statement to the next node of the return statement;
if the variable is located in the assignment statement in the statement and the variable is located in the parameter, step S502 is repeated and the statement is marked, and the statement is not analyzed independently the next time.
7. The method for constructing a resource flow graph according to any one of claims 1 to 6, wherein the following procedure is further included between the step S300 and the step S400: each analysis begins with taking one of the index values.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010741701.6A CN111857811B (en) | 2020-07-29 | 2020-07-29 | Construction method of resource flow graph |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010741701.6A CN111857811B (en) | 2020-07-29 | 2020-07-29 | Construction method of resource flow graph |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN111857811A CN111857811A (en) | 2020-10-30 |
| CN111857811B true CN111857811B (en) | 2023-09-22 |
Family
ID=72948198
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202010741701.6A Active CN111857811B (en) | 2020-07-29 | 2020-07-29 | Construction method of resource flow graph |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN111857811B (en) |
Citations (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6516461B1 (en) * | 2000-01-24 | 2003-02-04 | Secretary Of Agency Of Industrial Science & Technology | Source code translating method, recording medium containing source code translator program, and source code translator device |
| CN102073589A (en) * | 2010-12-29 | 2011-05-25 | 北京邮电大学 | Code static analysis-based data race detecting method and system thereof |
| CN108628635A (en) * | 2018-05-07 | 2018-10-09 | 广州视源电子科技股份有限公司 | Method, device, equipment and storage medium for acquiring parameter name and local variable name |
| CN110221973A (en) * | 2019-05-22 | 2019-09-10 | 湖南泛联新安信息科技有限公司 | Targeting formula parallel symbol towards c program defects detection executes method |
| CN110673852A (en) * | 2019-09-20 | 2020-01-10 | 北京智游网安科技有限公司 | Method, system and equipment for realizing control flow flatness based on compiler front end |
| US10656940B1 (en) * | 2019-02-04 | 2020-05-19 | Architecture Technology Corporation | Systems, devices, and methods for source code generation from binary files |
| CN111240982A (en) * | 2020-01-09 | 2020-06-05 | 华东师范大学 | Source code static analysis method |
| CN111249736A (en) * | 2020-01-16 | 2020-06-09 | 网易（杭州）网络有限公司 | Code processing method and device |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8789018B2 (en) * | 2011-05-31 | 2014-07-22 | Microsoft Corporation | Statically derived symbolic references for dynamic languages |
-
2020
- 2020-07-29 CN CN202010741701.6A patent/CN111857811B/en active Active
Patent Citations (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6516461B1 (en) * | 2000-01-24 | 2003-02-04 | Secretary Of Agency Of Industrial Science & Technology | Source code translating method, recording medium containing source code translator program, and source code translator device |
| CN102073589A (en) * | 2010-12-29 | 2011-05-25 | 北京邮电大学 | Code static analysis-based data race detecting method and system thereof |
| CN108628635A (en) * | 2018-05-07 | 2018-10-09 | 广州视源电子科技股份有限公司 | Method, device, equipment and storage medium for acquiring parameter name and local variable name |
| US10656940B1 (en) * | 2019-02-04 | 2020-05-19 | Architecture Technology Corporation | Systems, devices, and methods for source code generation from binary files |
| CN110221973A (en) * | 2019-05-22 | 2019-09-10 | 湖南泛联新安信息科技有限公司 | Targeting formula parallel symbol towards c program defects detection executes method |
| CN110673852A (en) * | 2019-09-20 | 2020-01-10 | 北京智游网安科技有限公司 | Method, system and equipment for realizing control flow flatness based on compiler front end |
| CN111240982A (en) * | 2020-01-09 | 2020-06-05 | 华东师范大学 | Source code static analysis method |
| CN111249736A (en) * | 2020-01-16 | 2020-06-09 | 网易（杭州）网络有限公司 | Code processing method and device |
Non-Patent Citations (1)
| Title |
|---|
| 结构体对象的赋值运算方法研究;闫鑫;金大海;宫云战;;软件(第11期);67-70 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN111857811A (en) | 2020-10-30 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN110609693B (en) | Code updating method and device based on data standardization and terminal equipment | |
| CN106547520B (en) | Code path analysis method and device | |
| CN111797010B (en) | A Smart Contract Test Case Generation Method Using Improved Genetic Algorithm | |
| CN110096439B (en) | Test case generation method for solidity language | |
| CN111249736B (en) | Code processing method and device | |
| EP3379443A1 (en) | Method and computer device to deobfuscate a source code | |
| CN110647752B (en) | Fuzzy test platform based on genetic algorithm | |
| CN113377419B (en) | Service processing method and device, readable storage medium and electronic equipment | |
| CN105138335A (en) | Function call path extracting method and device based on control flow diagram | |
| CN111611152A (en) | Test case generation method and device, electronic equipment and readable storage medium | |
| CN111026660A (en) | Penetration testing method based on expert system knowledge base | |
| CN112633516B (en) | Performance prediction and machine learning compiling optimization method and device | |
| CN111857811B (en) | Construction method of resource flow graph | |
| CN107832391B (en) | Data query method and system | |
| CN112015426B (en) | Code management method, device and equipment | |
| CN119066664A (en) | A method, device, equipment and storage medium for identifying code vulnerabilities | |
| CN115794120B (en) | A Dynamic Program Dependency Cluster Detection Method Based on Higher Order Functions | |
| CN116796321A (en) | Binary code homology analysis method, binary code homology analysis device, binary code homology analysis equipment and binary code homology storage medium | |
| CN113568662B (en) | Code change influence range analysis method and system based on calling relation | |
| CN112232071B (en) | Multi-round dialogue script test method, device, equipment and storage medium | |
| CN114594960A (en) | Recursive function analysis execution method, device and storage medium | |
| CN116028340A (en) | File generation method and device | |
| CN113609481A (en) | Byte code-based PHP taint analysis method and device | |
| CN114065197A (en) | Call sequence generation method and device, electronic equipment, storage medium and product | |
| CN112230928A (en) | A method, device and medium for parsing a predicate expression tree |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |