Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Recognition method of nested loop structure

A recognition method and nested loop technology, applied in the direction of instruments, computing, electrical digital data processing, etc., can solve the problem of low algorithm efficiency and achieve the effect of simple implementation, accurate recognition results and high recognition efficiency

Inactive Publication Date: 2009-11-11
PEKING UNIV
View PDF3 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0008] Two years later, G. Ramalingam proposed an improved algorithm to the Havlak algorithm (see G. Ramalingam, Identifying loops in almost linear time, ACM Transactions on Programming Languages ​​and Systems, Vol.21, No.2, 1999), in the worst case Algorithm in approximately linear time (but slower than Havlak's algorithm in the general case)
[0009] The above methods are usually based on complex data structures, such as Interval / DSG, or UNION-FIND sets. The complex operations on these data sets make these algorithms very inefficient

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Recognition method of nested loop structure
  • Recognition method of nested loop structure
  • Recognition method of nested loop structure

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0055] The identification method of the cycle of the present invention, its steps can be expressed as:

[0056] 1. Disassemble the executable file to obtain the intermediate code of the executable file;

[0057] 2. Extract the control flow information from the above intermediate code, obtain the control flow graph, and further obtain the extended control flow graph G=(N, E, h 0 ): N is the set of nodes, E is the set of edges, h 0 is the entry node of the control flow graph;

[0058] 3. Depth-first traversal of the extended control flow graph to identify loop nodes, including the following judgments for each node:

[0059] 1) Whether the node is a loop head node;

[0060] 2) Whether the node is in the loop body, if so, find its innermost loop head node;

[0061] 3) Whether the node is a reentrant, and if so, find the reentrant edge.

[0062] 4. Mark the innermost loop head node of the node;

[0063] 5. Identify the corresponding control flow graph as a loop structure.

...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention pertains to the field of reverse project and program analysis, in particular to a method for recognizing a recycling structure which can disassemble executive files and then get intermediate codes of the executive files. Control flow information is extracted from the intermediate codes, thus obtaining a control flow chart; the control flow chart is deeply optimized and compiled, thus recognizing recycling nodes; the most internal recycling head node of the node is marked; the corresponding control flow chart is recognized as a recycling structure. The method can effectively judge the recycling structure and the embedded relationship between recycling structures, thus further effectively structuring the program control flow chart. The method can be used in decompiling, software testing, and etc. equipment.

Description

technical field [0001] The invention belongs to the field of reverse engineering and program analysis, and in particular relates to a method for recognizing a nested loop structure, which can be used in devices such as decompilation and software testing, and can effectively structure a program control flow graph. Background technique [0002] Decompilation is a technology to obtain high-level code equivalent to the source program from an executable file. It is one of the core technologies in the field of reverse engineering and plays an important role in different application fields. Initially, decompilation technology was mainly used to assist program transplantation, such as migrating programs from second-generation computers to third-generation computers; in the 1970s and 1980s, decompilation technology began to be used for re-engineering (Re-engineering), including Understand, document, reconstruct and modify lost source code or third-party binary programs; since the mid...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Patents(China)
IPC IPC(8): G06F9/45
Inventor 韦韬李佳静毛剑邹维王铁磊王伟
Owner PEKING UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com