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

Dynamic symbolic execution method and device thereof based on overall situation super block dominator graph

A technology of dynamic symbolic execution and dominance graph, applied in software testing/debugging, etc., to alleviate the problem of path explosion, ensure accuracy, and improve efficiency

Active Publication Date: 2013-05-22
UNIV OF ELECTRONICS SCI & TECH OF CHINA
View PDF3 Cites 30 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, the commonly used depth-first and breadth-first path exploration algorithms cannot achieve this goal.
At present, the seemingly optimal generation algorithm has a very large overhead and error in the actual execution process.

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
  • Dynamic symbolic execution method and device thereof based on overall situation super block dominator graph
  • Dynamic symbolic execution method and device thereof based on overall situation super block dominator graph
  • Dynamic symbolic execution method and device thereof based on overall situation super block dominator graph

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0070] This implementation case describes a way to realize the present invention in detail, but the scope of protection of the present invention is not limited to this way, and all implementations that adopt the idea of ​​the present invention are within the scope of protection of the present invention.

[0071] Control flow graph generation module:

[0072] The function of this module is to generate the control flow graph and function call relationship graph corresponding to each function of the target program. The following is a brief introduction to graph theory knowledge related to control flow graphs. The control flow graph of a program can be represented by a quadruple G =( N , E , entry , exit ), N It is a combination of nodes in the control flow graph, and each node represents a basic block in the program; E is a set of directed edges, and each edge represents a control flow transfer between basic blocks; entry is the entry point of the program; exit is t...

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 provides a dynamic symbolic execution method and a device of the dynamic symbolic execution method based on an overall situation super block dominator graph and belongs to the field of computer software testing and software security. The method is as follows: a control flow diagram of a tested executable program is obtained, and the control flow diagram is transformed to a super block dominator graph according to relevant theories of a dominance relation. Each nodal point in the super block dominator graph is marked with 'weight' which is updated before symbolic execution at each time, and the 'weight' indicates the least number of basic blocks which can be covered when the nodal point is executed. When one dynamic symbolic execution is over, the nodal point with the largest 'weight' value is selected from the super block dominator graph, and corresponding forecasting path constraint conditions are generated, and then a new testing use case is generated by solving of a solver, so that the next execution is driven. Compared with the prior art, the dynamic symbolic execution method and the device of the dynamic symbolic execution method based on the overall situation super block dominator graph are capable of covering code blocks as many as possible with least testing use cases, so that the growth rate of the code coverage rate is effectively accelerated, and the problem of path explosion is relieved. The dynamic symbolic execution method and the device of the dynamic symbolic execution method based on the overall situation super block dominator graph is of great importance for the performance of testing large-scale utility software of the dynamic symbolic execution.

Description

technical field [0001] The dynamic symbol execution scheme based on the global superblock dominance graph proposed by the present invention belongs to the field of computer dynamic software testing and software security, and can be used in dynamic program analysis, automatic test case generation, software loophole mining and the like. Background technique [0002] Dynamic symbolic execution technology is a new technology proposed in recent years. It is currently used in software behavior analysis, software defect analysis, vulnerability testing, and automatic generation of test cases. Dynamic symbolic execution can generate test input corresponding to each path, and can dynamically detect bugs existing on each path and dead ends, and does not depend on source code, avoiding static testing methods with high manual overhead, low efficiency, high false alarm rate, and Fuzzing Defects such as testing randomness can more comprehensively and accurately detect software vulnerabi...

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 Applications(China)
IPC IPC(8): G06F11/36
Inventor 张小松陈厅吉小丽牛伟纳陈瑞东王东
Owner UNIV OF ELECTRONICS SCI & TECH OF CHINA
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