CN116992453A - Method and system for automatically positioning vulnerability root cause based on Hash stack - Google Patents
Method and system for automatically positioning vulnerability root cause based on Hash stack Download PDFInfo
- Publication number
- CN116992453A CN116992453A CN202310835097.7A CN202310835097A CN116992453A CN 116992453 A CN116992453 A CN 116992453A CN 202310835097 A CN202310835097 A CN 202310835097A CN 116992453 A CN116992453 A CN 116992453A
- Authority
- CN
- China
- Prior art keywords
- predicate
- input
- root
- vulnerability
- instruction
- 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.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 30
- 238000012360 testing method Methods 0.000 claims abstract description 58
- 230000006399 behavior Effects 0.000 claims abstract description 17
- 238000010276 construction Methods 0.000 claims abstract description 17
- 238000010586 diagram Methods 0.000 claims abstract description 12
- 238000012545 processing Methods 0.000 claims abstract description 9
- 238000006243 chemical reaction Methods 0.000 claims abstract description 5
- 230000014509 gene expression Effects 0.000 claims description 10
- 238000000605 extraction Methods 0.000 claims description 4
- 230000004807 localization Effects 0.000 claims description 4
- 230000015654 memory Effects 0.000 description 20
- 230000006870 function Effects 0.000 description 15
- 238000004458 analytical method Methods 0.000 description 11
- 230000001960 triggered effect Effects 0.000 description 6
- 238000005516 engineering process Methods 0.000 description 5
- 239000008186 active pharmaceutical agent Substances 0.000 description 4
- 238000005065 mining Methods 0.000 description 3
- 230000008569 process Effects 0.000 description 3
- 230000008439 repair process Effects 0.000 description 3
- 238000004364 calculation method Methods 0.000 description 2
- 230000015556 catabolic process Effects 0.000 description 2
- 238000001514 detection method Methods 0.000 description 2
- 238000012544 monitoring process Methods 0.000 description 2
- 238000013522 software testing Methods 0.000 description 2
- 238000007619 statistical method Methods 0.000 description 2
- 230000002194 synthesizing effect Effects 0.000 description 2
- 208000021769 Acute sensory ataxic neuropathy Diseases 0.000 description 1
- 238000012935 Averaging Methods 0.000 description 1
- 238000004422 calculation algorithm Methods 0.000 description 1
- 238000010835 comparative analysis Methods 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 239000000284 extract Substances 0.000 description 1
- 230000002068 genetic effect Effects 0.000 description 1
- 239000007943 implant Substances 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 230000010354 integration Effects 0.000 description 1
- 230000005291 magnetic effect Effects 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000035772 mutation Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 238000012216 screening Methods 0.000 description 1
- 230000003068 static effect Effects 0.000 description 1
- 230000007704 transition Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
- G06F21/50—Monitoring users, programs or devices to maintain the integrity of platforms, e.g. of processors, firmware or operating systems
- G06F21/57—Certifying or maintaining trusted computer platforms, e.g. secure boots or power-downs, version controls, system software checks, secure updates or assessing vulnerabilities
- G06F21/577—Assessing vulnerabilities and evaluating computer system security
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Computer Security & Cryptography (AREA)
- General Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Debugging And Monitoring (AREA)
Abstract
The invention provides a vulnerability root automatic positioning method based on stack hash, which comprises the following steps: performing fuzzy test on the target program by using the input data, if the input data causes the target program to crash, taking the input data as crash input, otherwise, taking the input data as non-crash input; acquiring crash input and non-crash input in program execution, wherein instruction information corresponding to a test instruction and a function call stack hash value when the instruction is called are used as predicate construction information; based on the control flow conversion of all input data, constructing a control flow diagram of a target program, and generating predicates corresponding to program behaviors for test instructions according to predicate construction information and the control flow diagram; root predicates are selected from predicates in an ordered manner, and test conditions corresponding to the root predicates are used as explanations for causing the target program to crash. The invention also provides a system for automatically positioning the vulnerability root cause based on the stack hash and a data processing device for automatically positioning the vulnerability root cause based on the stack hash.
Description
Technical Field
The invention belongs to the technical field of software security, and particularly relates to a method and a system for automatically positioning a vulnerability root cause based on a hash stack.
Background
The main threat to computer system security comes from software vulnerabilities. In recent years, the frequency of loopholes in some system software and important open source components is increased, and the ecology of the software is seriously jeopardized. In one aspect, software vulnerabilities are widely present in most software. On the other hand, software vulnerabilities are potentially very dangerous and the consequences of being successfully exploited are serious. An attacker may exploit vulnerabilities to steal or manipulate sensitive data, join a system into a botnet, install a backdoor, or implant other types of malware. Therefore, the vulnerability discovery, the vulnerability root cause positioning and the vulnerability restoration are significant in improving the software security.
In the aspect of vulnerability mining, fuzzy testing utilizes high throughput and continuously modified inputs to discover different paths in a target program, and has become a main flow path of vulnerability mining and a powerful software testing technology at present. With the development of fuzzy test technology, the efficiency of vulnerability discovery is greatly improved, and a large number of software vulnerabilities are discovered. However, the root cause of the software bug is difficult to locate and repair, and relies on the analyst to manually complete, resulting in an imbalance in the speed of software bug mining and bug repair. A large number of bug fixes that have been discovered are not timely and may be exploited by an attacker.
Existing techniques for software bug root cause localization mainly include Debugger (Debugger), runtime memory error detection (saitizer), reverse taint analysis (backwards Taintanalysis), crash input exploration (Crash Exploration), and symbolic execution (Symbolic Execution).
(1) With the aid of the debugger, the analyst can examine all instructions of the program execution from the crash location back and forth, as well as the program state (e.g., registers, memory, function call stack, etc.) at each instruction. An analyst can determine the cause and root cause of the program crash by manually tracking the program state. However, the use of debugger for program root cause localization requires very high demands on analysts. Large programs have large code volumes and complex logic, and vulnerabilities have certain complexity, and even professionals are required to spend a great deal of time determining the root cause of the vulnerability.
(2) The saitin uses compile-time instrumentation techniques to enable detection of various software failures at runtime. For example, MSAN (Memory Sanitizer) is used to detect the use of uninitialized memory (Uninitialized Memory); ASAN (Address Sanitizer) is used to detect memory errors such as heap buffer overflow (Heap Buffer Overflow), stack buffer overflow (StackBuffer Overflow), post-memory release reuse (UseAfter Free), and repeated memory release (Double Free). The Sanitizer provides more detailed, program crash information closer to the root cause of the program than the debugger. But the saitin can only detect memory errors and is not a strategy for non-memory errors. In addition, while the Sanitizer provides more excellent debug information than a debugger, it is difficult to directly indicate the root cause of a program crash and the occurrence condition of a bug.
(3) Reverse taint analysis techniques begin contaminating data from the program crash point, reverse building the control flow of the program and identifying the data or instructions that caused the program to crash. The extensive effort to locate the root cause of a program using reverse taint analysis techniques typically begins with a Core Dump file (Core Dump), re-executes the program and builds a data stream that results in a crash, providing the analyst with relevant instructions that result in a crash. These methods are useful in cases where the crash is not replicable, but most are limited to correctly identifying vulnerabilities where there is a direct data flow dependency between the root cause and the crash cause.
(4) The crash exploration mode in the fuzzy test takes a crash input as a seed and generates a new crash input through mutation. These newly generated inputs mostly lead to the same crash, but the improvement of code coverage is likely to lead to the same vulnerability being triggered by different code paths. Multiple inputs that trigger crashes of the same root cause but with different paths may provide new insights into the root cause of the vulnerability to the developer. But due to the randomness of the obfuscation test, the obfuscator is more likely to add or delete code that is not relevant to the vulnerability to produce new crash inputs. Moreover, the analyst needs to expend more effort in analyzing and debugging the additional crash input.
(5) In software testing, symbolic execution is used to generate one test input for each execution path of a program. All execution paths of a program can be represented using an execution tree. The prior art provides a root cause analysis technology of program crash based on symbol execution, and the root cause analysis strategy and the program repair proposal based on symbol analysis are respectively realized aiming at five vulnerability forms of buffer Overflow, integer Overflow (inter Overflow), reuse after memory release, memory repetition release and character String formatting (Format String). However, the method can only analyze preset loopholes patterns, and cannot analyze loopholes with complex root causes.
Therefore, the existing vulnerability root cause positioning method is limited to certain vulnerability types, and explanation of the vulnerability is not provided in some cases, so that the method is difficult to apply in practice.
Disclosure of Invention
The method aims to solve the problems of limitation of the type of the target program loopholes and lack of explanation of the loopholes in the existing automatic positioning technology of the root causes of the loopholes. Aiming at the problems, the invention provides a vulnerability root cause automatic positioning method based on stack hash, which comprises the following steps: performing fuzzy test on the target program by using input data, and according to a test result, if the input data causes the target program to crash, taking the input data as crash input, otherwise, taking the input data as non-crash input; acquiring instruction information of a corresponding test instruction and a function call stack hash value when the instruction is called in program execution by the crash input and the non-crash input, and taking the instruction information and the function call stack hash value as predicate construction information; constructing a control flow diagram of the target program based on the control flow conversion of all the input data, and generating predicates of corresponding program behaviors for the test instruction according to the predicate construction information and the control flow diagram; and selecting a root predicate from the predicates in an ordered manner, and taking a test condition corresponding to the root predicate as an interpretation for causing the target program to crash.
The invention relates to an automatic positioning method of a vulnerability root cause, wherein the predicate comprises a Boolean expression for semantic description, an instruction address of a test instruction and a predicate score, and the predicate score represents the probability of the target program crashing caused by the input of a predicate result being true; for each test instruction, the predicate with the predicate score having the maximum value is reserved as the predicate of the test instruction.
The invention relates to a vulnerability root automatic positioning method, wherein the predicate scoreWherein, P1 represents the probability that the predicate prediction result of the collapse input is correct, and P2 represents the probability that the predicate prediction result of the non-collapse input is correct.
According to the automatic positioning method for the vulnerability root cause, predicates with high predicate scores of Yu Genyin threshold values and test instructions corresponding to the predicates are used as the root cause predicates.
The invention also provides a system for automatically positioning the vulnerability root cause based on the Hash stack, which comprises the following steps: the data set construction module is used for carrying out fuzzy test on the target program by using input data, and taking the input data as crashed input if the input data leads to the crashed target program according to a test result, otherwise, taking the input data as non-crashed input; the program information extraction module is used for acquiring the crashed input and the non-crashed input in program execution, and the instruction information of the corresponding test instruction and the hash value of the function call stack when the instruction is called are used as predicate construction information; the predicate construction module is used for constructing a control flow diagram of the target program based on control flow conversion of all the input data, and generating predicates corresponding to program behaviors for the test instruction according to the predicate construction information and the control flow diagram; and the predicate ordering module is used for selecting root predicates from the predicates in an ordering mode, and taking test conditions corresponding to the root predicates as the interpretation for causing the target program to crash.
The invention relates to an automatic vulnerability root positioning system, wherein the predicate comprises a Boolean expression for semantic description, an instruction address of a test instruction and a predicate score, and the predicate score represents the probability of the target program crashing caused by the input of a predicate result being true; for each test instruction, the predicate with the predicate score having the maximum value is reserved as the predicate of the test instruction.
The invention relates to a vulnerability root automatic positioning system, wherein the predicate scoreWherein, P1 represents the probability that the predicate prediction result of the collapse input is correct, and P2 represents the probability that the predicate prediction result of the non-collapse input is correct.
According to the vulnerability root cause automatic positioning system, predicates with high predicate scores of Yu Genyin threshold and corresponding test instructions are used as root cause predicates.
The invention also provides a computer readable storage medium which stores computer executable instructions, and is characterized in that when the computer executable instructions are executed, the loophole root automatic positioning method based on the Hash stack is realized.
The invention also provides a data processing device, which comprises the computer readable storage medium, and when a processor of the data processing device invokes and executes the computer executable instructions in the computer readable storage medium, the automatic positioning of the vulnerability root cause based on the Hash stack is realized.
Drawings
FIG. 1 is a flow chart of a method for automatically locating a vulnerability root based on a hash stack.
FIG. 2 is a schematic diagram of a data processing apparatus of the present invention.
Detailed Description
The present invention will be described in further detail with reference to the accompanying drawings, in order to make the objects, technical solutions and advantages of the present invention more apparent. It should be understood that the detailed description and specific examples, while indicating the invention, are intended for purposes of illustration only and are not intended to limit the scope of the invention.
Aiming at the defects, the invention provides a predicate analysis method based on stack hash for automatically positioning the root cause of the vulnerability. The design idea of the invention is from: (1) Crash inputs and non-crash inputs must deviate at the semantic level during program execution, and the first related behavior that causes deviation during program execution is the root cause of the vulnerability. (2) The function call stack can distinguish the context environment of instruction call, and improves the interpretation capability of predicates on loopholes. The single instruction is divided into a plurality of groups through the context environment of the function call stack hash, and predicate semantics corresponding to the instruction are richer and more accurate.
The invention aims to solve the problems of limitation of the type of the target program bug and lack of explanation of the bug in the existing bug root cause automatic positioning technology. The invention constructs two groups of input data sets which are related to crashes and have different program behaviors through fuzzy tests, wherein one group is a crashed input set, and the other group is a non-crashed input set. Given these two sets of inputs, the present invention observes and monitors (tracks) program behavior under each input through the Pin tool and records program runtime information at the instruction level. Finally, the invention constructs a unitary predicate describing the program behavior through the program runtime information and scores and sorts the predicates. And giving out vulnerability root predictions according to the ranking results. The key technical points of the invention include:
1. the Pin tool gathers program runtime information at the instruction level given input, which mainly includes three categories: (1) the maximum and minimum values of the registers or memories that the instruction changes (limiting the amount of data generated by the loop and the value that causes a crash is typically the minimum or maximum value), (2) the control flow information of the instruction (predecessor, successor to the program basic block), (3) the values of the flag registers (e.g., the flag bits CF, PF, AF, etc. in the x86 architecture CPU).
2. Predicates can distinguish between crashed and non-crashed runs and determine conditions in a program that can be met only when crashed, specifically including three types of predicates, namely (1) control flow predicates. Based on the control flow graph, the invention synthesizes control flow predicates to evaluate whether the crashed and non-crashed inputs are different in the execution flow, for example, whether a control flow edge to another instruction exists for a certain instruction or whether the number of successor (predecessor) of a certain instruction is a given value; (2) registers and memory predicates. For each instruction, the invention synthesizes predicates indicating the maximum value and the minimum value of a register or a memory according to various expressions; (3) marking predicates. The flag register records the result of the binary comparison and whether it overflows.
If the program crashes at a given input, then the ideal result of the predicate is true; otherwise, the result of the predicate is false. If one predicate can correctly predict the results of all inputs, the predicate is perfect, i.e., the predicate can perfectly distinguish between crashed and non-crashed inputs. The invention scores predicates by judging whether programs under crash input and non-crash input meet the predicates, and sorts the predicates by taking the predicate scores and the predicate triggering sequences as standards.
3. Because of the complexity of program behavior and loopholes, the actual best predicate may be more complex than the automatically synthesized predicate. For example, the optimal predicate of a program behavior exception caused by multiple factors may not be unitary, and a vulnerability may only be triggered if multiple constraints are satisfied. When a program dynamically runs, an instruction has different call contexts (paging Context) when being called for multiple times, and the memory, the register and the function call stack can be different when each call is performed. If the information of each call of the instruction is combined without screening, the information among different call contexts can interfere with each other, and the expression capability and the accuracy of predicates are affected. Therefore, the invention abstracts the instruction calling context into the hash value of the function calling stack, synthesizes different predicates for different stack hash values under the same instruction, eliminates the interference among different contexts, improves the expression capability of the predicates, and introduces only small performance cost. The function call stack hash tracks the last N function call addresses at the call site and hashes these addresses to form a unique identifier (characterizes the execution state of the process in a compact form).
Based on the technical key points, the predicate analysis system based on the Hash stack consists of three parts: (1) The input through fuzzy test is diversified to obtain two groups of different inputs, namely an input which leads to program breakdown and an input which does not lead to program breakdown; (2) Monitoring the runtime behavior of the tracking program and recording runtime information; (3) synthesizing descriptive predicates and ordering the predicates. The specific structure of the invention is shown in figure 1:
1. data set construction module
AFL (American Fuzzy Lop) is a brute force fuzzy test tool incorporating an extremely simple but effective stake-guided genetic algorithm that uses an improved edge coverage to perceive subtle, localized variations in program control flow. The AFL performs pile-inserting on each basic block of the program and gives each basic block a random number, records the hit number of each basic block when the program runs, and represents the control flow edge of the program through the random number hash values of the two basic blocks. Through edge coverage analysis, the AFL can sense the execution condition of the basic block of the program.
The present invention creates two sets of input data related to crashes but with different program behavior, one set being a set of crashed inputs and the other set being a set of non-crashed inputs. On the one hand, the inputs should be diversified so that the statistical analysis shows a measurable difference; on the other hand, the inputs should share similar basic structures so that they explore states similar to the root cause. This allows a comparative analysis of the behavior of the crashed and non-crashed inputs on the wrong path. To effectively generate inputs with the above features, given an initial crash input (seed), the present invention uses the crash exploration mode in the AFL tool to mutate it. Inputs that do not cause program crashes will be discarded from the input queue of the fuzzing test and saved to the non-crashed set; all the inputs remaining in the input queue constitute a collapsed set. In general, the more diverse the inputs generated by collision exploration, the more accurate the statistical analysis. The input set created by the AFL will be passed to the program information extraction module constituted by the subsequent Pin analysis components.
2. Program information extraction module
Pin is a instrumentation for program instrumentation, supporting Linux, macOS, windows operating systems suitable for IA-32, intel (R) 64 and Intel (R) multi-core integration architectures. Pin allows a user to insert arbitrary C/C++ code at arbitrary locations in a binary file while also supporting callbacks for many events (e.g., static library/dynamic library loads, system calls, signal/exception and thread creation events, etc.). These codes are dynamically added and executed at binary runtime by just-in-time compilation (JIT) techniques of Pin, so Pin can also instrumentation the running process. Pin provides an API that is rich and abstracts out the nature of the underlying instruction set. Through the API provided by Pin, the user can pass context information representing the program state, such as register data, as parameters to the instrumentation code. Pin automatically saves and restores the instrumentation code covered registers so that the application continues to operate. Pin provides related APIs such as PIN_backtrace and the like, and can acquire a function call stack of the target program during running, so that the program does not need to read a register and a memory value of the target program by itself.
The invention realizes a pile inserting tool based on Pin, takes crashed and non-crashed data sets as input, and extracts related information (register value, memory value, instruction predecessor and the like) required by constructing predicates when a program runs and a function call stack hash value when each instruction is called through universal and architecture-specific APIs of Intel Pin. For each input, the present invention stores this information in json data files compressed using the zip format, and provides two sets of trace files to describe the intrinsic behavior of crashed and non-crashed inputs and passes them to the following predicate construction modules. Through the function call stack hash value, the invention records the instruction information of different addresses, and simultaneously, the instruction information of the same address of different stack hash values is also respectively recorded.
3. Predicate construction module
The differences in program behavior between the crashed and non-crashed inputs may be related to the program execution results (i.e., whether the program crashed). To formalize the differences, the present invention uses predicates to describe whether vulnerabilities are triggered. Predicates are a triple semantic word consisting of a semantic description (i.e., a Boolean expression), an address of an instruction, and a score indicating the ability to distinguish between crashes and non-crashes. The semantic description, i.e. the test condition corresponding to the predicate, is that the minimum value of the rax register at a certain instruction is smaller than a constant. Given a crashed input data, if the input passes the test condition corresponding to the predicate in program execution, namely, the result of the Boolean expression is true, the predicate prediction is correct, otherwise, the predicate prediction is incorrect. Given a piece of non-collapse input data, if the input does not pass the test condition corresponding to the predicate in program execution, namely, the result of the Boolean expression is false, the predicate prediction is correct, otherwise, the predicate prediction is incorrect. The fraction of predicates, namely the probability P that the predicate prediction result is correct, is obtained by arithmetic averaging the probability P1 that the predicate prediction result of crashed input data is correct and the probability P2 that the predicate prediction result of non-crashed input data is correct, namely
For crashed input data, if the test condition of the predicate is true, the predicate prediction is correct, otherwise, the predicate prediction is incorrect. Therefore, the calculation mode of P1 is that the quantity of predicate test condition in the collapse input data is true and the quantity of all the collapse input data is occupied.
For non-crashed input data, if the test condition of the predicate is false, the predicate prediction is correct, otherwise, the predicate prediction is correct. Therefore, the calculation mode of P2 is that the quantity of predicate test condition in the non-collapse input data is false, and the quantity of predicate test condition in the non-collapse input data occupies the quantity of all non-collapse input data.
In other words, the score represents the probability of an input collapse for which one predicate result is true. Thus, a predicate with a higher score identifies the code location on the path between the root cause and the crash location.
The analysis system takes as input two folders containing crash and non-crash runtime information. Subsequently, the system gathers all control flow transitions observed in the crashed and non-crashed inputs and reconstructs the control flow graph of the program (for synthesizing control flow predicates). And then the system synthesizes predicates of all types for each different instruction identified by the stack hash value respectively, calculates predicate scores, and only keeps one predicate with the highest score for each instruction in consideration of performance. Note that since the instruction where the root cause of the program crash is located must be accessed by the execution flow of the crash, the present invention only considers instructions accessed by at least one crash and one non-crash input. If some instructions are accessed in a crash, but not in a non-crash, they may be discarded.
4. Predicate ordering module
Predicates with scores below a discard threshold (e.g., below 0.9) and their corresponding instructions are discarded. Then, firstly, sorting is performed according to the scores of predicates, predicates with higher scores are more likely to be root causes of loopholes, so that sorting is higher, and test conditions corresponding to predicates with scores of a high Yu Genyin threshold are selected as explanations of loopholes existing in a target program. Predicates of the same score are then ordered by the order in which the predicates were triggered. Intuitively, the earlier predicates in the execution flow are more likely to be root causes and therefore ranked higher. The present invention determines the order in which predicates are triggered by monitoring the predicates. Specifically, the invention uses ptrace system call to set conditional break points, reads the register and memory of the tracked process, calculates the hash value of the function call stack of each predicate and records the order in which the predicates are triggered.
FIG. 2 is a schematic diagram of a data processing apparatus of the present invention. As shown in fig. 2, the embodiment of the present invention further provides a computer-readable storage medium, and a data processing apparatus. The computer readable storage medium of the invention stores computer executable instructions which when executed by a processor of a data processing device, realize automatic positioning of vulnerability root cause based on Hash stack. Those of ordinary skill in the art will appreciate that all or a portion of the steps of the above-described methods may be performed by a program that instructs associated hardware (e.g., processor, FPGA, ASIC, etc.), which may be stored on a readable storage medium such as read only memory, magnetic or optical disk, etc. All or part of the steps of the embodiments described above may also be implemented using one or more integrated circuits. Accordingly, each module in the above embodiments may be implemented in the form of hardware, for example, by an integrated circuit, or may be implemented in the form of a software functional module, for example, by a processor executing a program/instruction stored in a memory to implement its corresponding function. Embodiments of the invention are not limited to any specific form of combination of hardware and software.
The invention can accurately identify the root cause of the crash input given by the binary executable file and provide the analyst with rich contextual information describing the error behavior of the crash input. Compared with the prior art, the method provided by the invention reports the root cause of the vulnerability on the binary instruction level, is not limited to the type of the vulnerability, and provides explanation of the vulnerability through the Hash and the predicate.
The above embodiments are only for illustrating the present invention, not for limiting the present invention, and various changes and modifications may be made by one of ordinary skill in the relevant art without departing from the spirit and scope of the present invention, so that all equivalent technical solutions are also within the scope of the present invention, and the scope of the present invention is defined by the claims.
Claims (10)
1. A method for automatically positioning a vulnerability root cause based on a stack hash is characterized by comprising the following steps:
performing fuzzy test on the target program by using input data, and according to a test result, if the input data causes the target program to crash, taking the input data as crash input, otherwise, taking the input data as non-crash input;
acquiring instruction information of a corresponding test instruction and a function call stack hash value when the instruction is called in program execution by the crash input and the non-crash input, and taking the instruction information and the function call stack hash value as predicate construction information;
constructing a control flow diagram of the target program based on the control flow conversion of all the input data, and generating predicates of corresponding program behaviors for the test instruction according to the predicate construction information and the control flow diagram;
and selecting a root predicate from the predicates in an ordered manner, and taking a test condition corresponding to the root predicate as an interpretation for causing the target program to crash.
2. The vulnerability root automatic localization method of claim 1, wherein the predicate includes a boolean expression for semantically describing the corresponding test condition, an instruction address of the test instruction, and a predicate score representing a probability that an input when the predicate result is true results in the target program crashing; for each test instruction, the predicate with the predicate score having the maximum value is reserved as the predicate of the test instruction.
3. The vulnerability root automatic positioning method of claim 2, wherein the predicate scoreWherein, P1 represents the probability that the predicate prediction result of the collapse input is correct, and P2 represents the probability that the predicate prediction result of the non-collapse input is correct.
4. The vulnerability root automatic positioning method of claim 2, wherein the root predicate is a predicate with a predicate score higher than a Yu Genyin threshold.
5. The utility model provides a vulnerability root cause automatic positioning system based on stack hash which characterized in that includes:
the data set construction module is used for carrying out fuzzy test on the target program by using input data, and taking the input data as crashed input if the input data leads to the crashed target program according to a test result, otherwise, taking the input data as non-crashed input;
the program information extraction module is used for acquiring the crashed input and the non-crashed input in program execution, and the instruction information of the corresponding test instruction and the hash value of the function call stack when the instruction is called are used as predicate construction information;
the predicate construction module is used for constructing a control flow diagram of the target program based on control flow conversion of all the input data, and generating predicates corresponding to program behaviors for the test instruction according to the predicate construction information and the control flow diagram;
and the predicate ordering module is used for selecting root predicates from the predicates in an ordering mode, and taking test conditions corresponding to the root predicates as the interpretation for causing the target program to crash.
6. The vulnerability root automatic positioning system of claim 5, wherein the predicate comprises a Boolean expression for semantic description, an instruction address of the test instruction, and a predicate score representing a probability that an input when the predicate result is true results in the target program crashing; for each test instruction, the predicate with the predicate score having the maximum value is reserved as the predicate of the test instruction.
7. The vulnerability root automatic positioning system of claim 6, wherein the predicate scoreWherein, P1 represents the probability that the predicate prediction result of the collapse input is correct, and P2 represents the probability that the predicate prediction result of the non-collapse input is correct.
8. The vulnerability root automatic positioning system of claim 6, wherein the root predicate is a predicate with a predicate score of Yu Genyin threshold and a test instruction corresponding to the predicate.
9. A computer readable storage medium storing computer executable instructions which, when executed, implement the method for automatically locating vulnerability root based on hash of any one of claims 1-4.
10. A data processing apparatus comprising the computer readable storage medium of claim 9, which when fetched and executed by a processor of the data processing apparatus, implements automatic localization of vulnerability root cause based on a hash stack.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310835097.7A CN116992453A (en) | 2023-07-07 | 2023-07-07 | Method and system for automatically positioning vulnerability root cause based on Hash stack |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310835097.7A CN116992453A (en) | 2023-07-07 | 2023-07-07 | Method and system for automatically positioning vulnerability root cause based on Hash stack |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN116992453A true CN116992453A (en) | 2023-11-03 |
Family
ID=88520530
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202310835097.7A Pending CN116992453A (en) | 2023-07-07 | 2023-07-07 | Method and system for automatically positioning vulnerability root cause based on Hash stack |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN116992453A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118524003A (en) * | 2024-07-24 | 2024-08-20 | 浙江大学 | Internet of things firmware fault root screening method and system based on instruction behaviors |
-
2023
- 2023-07-07 CN CN202310835097.7A patent/CN116992453A/en active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118524003A (en) * | 2024-07-24 | 2024-08-20 | 浙江大学 | Internet of things firmware fault root screening method and system based on instruction behaviors |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Petsios et al. | Slowfuzz: Automated domain-independent detection of algorithmic complexity vulnerabilities | |
| Blazytko et al. | {AURORA}: Statistical crash analysis for automated root cause explanation | |
| Kahlon et al. | Fast and accurate static data-race detection for concurrent programs | |
| Godefroid et al. | Automating software testing using program analysis | |
| US8839203B2 (en) | Code coverage-based taint perimeter detection | |
| US8423965B2 (en) | Tracing of data flow | |
| US8356287B2 (en) | Device, system and method of debugging computer programs | |
| Jiang et al. | Fuzzing Error Handling Code using {Context-Sensitive} Software Fault Injection | |
| US8185875B2 (en) | Fast and accurate static data-race detection for concurrent programs | |
| US12093398B2 (en) | Vulnerability analysis and reporting for embedded systems | |
| He et al. | Sofi: Reflection-augmented fuzzing for javascript engines | |
| Luo et al. | Selectfuzz: Efficient directed fuzzing with selective path exploration | |
| CN113419960B (en) | Seed generation method and system for kernel fuzzy test of trusted operating system | |
| CN109635568B (en) | Concurrent vulnerability detection method based on combination of static analysis and fuzzy test | |
| US8065565B2 (en) | Statistical debugging using paths and adaptive profiling | |
| US11249888B1 (en) | System and method for generating counterexample tests of incidental invariants | |
| Ashouri | Etherolic: a practical security analyzer for smart contracts | |
| EP3752945B1 (en) | Automatic generation of patches for security violations | |
| Lanzi et al. | A smart fuzzer for x86 executables | |
| CN116992453A (en) | Method and system for automatically positioning vulnerability root cause based on Hash stack | |
| Mouzarani et al. | A smart fuzzing method for detecting heap-based buffer overflow in executable codes | |
| Wang et al. | Adaptive randomized scheduling for concurrency bug detection | |
| Zhang et al. | Detecting vulnerabilities in C programs using trace-based testing | |
| CN114741700A (en) | Public component library vulnerability availability analysis method and device based on symbolic taint analysis | |
| Bhardwaj et al. | Fuzz testing in stack-based buffer overflow |
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 |