Control Flow Graphs(CFGs)are essential for understanding the execution and data flow within software,serving as foundational structures in program analysis.Traditional CFG construction methods,such as bytecode analysi...Control Flow Graphs(CFGs)are essential for understanding the execution and data flow within software,serving as foundational structures in program analysis.Traditional CFG construction methods,such as bytecode analysis and Abstract Syntax Trees(ASTs),often face challenges due to the complex syntax of programming languages like Java and Python.This paper introduces a novel approach that leverages Large Language Models(LLMs)to generate CFGs through a methodical Chain of Thought(CoT)process.By employing CoT,the proposed approach systematically interprets code semantics directly from natural language,enhancing the adaptability across various programming languages and simplifying the CFG construction process.By implementing a modular AI chain strategy that adheres to the single responsibility principle,our approach breaks down CFG generation into distinct,manageable steps handled by separate AI and non-AI units,which can significantly improve the precision and coverage of CFG nodes and edges.The experiments with 245 Java and 281 Python code snippets from Stack Overflow demonstrate that our method achieves efficient performance on different programming languages and exhibits strong robustness.展开更多
With the rapid development of software technology, software vulnerability has become a major threat to computer security. The timely detection and repair of potential vulnerabilities in software, are of great signific...With the rapid development of software technology, software vulnerability has become a major threat to computer security. The timely detection and repair of potential vulnerabilities in software, are of great significance in reducing system crashes and maintaining system security and integrity. This paper focuses on detecting three common types of vulnerabilities: Unused_Variable, Use_of_Uninitialized_Variable, and Use_After_ Free. We propose a method for software vulnerability detection based on an improved control flow graph(ICFG) and several predicates of vulnerability properties for each type of vulnerability. We also define a set of grammar rules for analyzing and deriving the three mentioned types of vulnerabilities, and design three vulnerability detection algorithms to guide the process of vulnerability detection. In addition, we conduct cases studies of the three mentioned types of vulnerabilities with real vulnerability program segments from Common Weakness Enumeration(CWE). The results of the studies show that the proposed method can detect the vulnerability in the tested program segments. Finally, we conduct manual analysis and experiments on detecting the three types of vulnerability program segments(30 examples for each type) from CWE, to compare the vulnerability detection effectiveness of the proposed method with that of the existing detection tool Cpp Check. The results show that the proposed method performs better. In summary, the method proposed in this paper has certain feasibility and effectiveness in detecting the three mentioned types of vulnerabilities, and it will also have guiding significance for the detection of other common vulnerabilities.展开更多
Abstract Single event upset （SEU） effect, caused by highly energized particles in aerospace, threatens the reliability and security of small satellites composed of commercialofftheshelves （COTS）. SEU induced contr...Abstract Single event upset （SEU） effect, caused by highly energized particles in aerospace, threatens the reliability and security of small satellites composed of commercialofftheshelves （COTS）. SEU induced control flow errors （CFEs） may cause unpredictable behavior or crashes of COTSbased small satellites. This paper proposes a generic softwarebased control flow checking technique （CFC） and bipartite graphbased control flow checking （BGCFC）. To simplify the types of illegal branches, it transforms the conventional control flow graph into the equivalent bipartite graph. It checks the legal ity of control flow at runtime by comparing a global signature with the expected value and introduces consecutive IDs and bitmaps to reduce the time and memory overhead. Theoretical analysis shows that BGCFC can detect all types of internode CFEs with constant time and memory overhead. Practical tests verify the result of theoretical analysis. Compared with previous techniques, BGCFC achieves the highest error detection rate, lower time and memory overhead; the composite result in evaluation fac tor shows that BGCFC is the most effective one among all these techniques. The results in both theory and practice verify the applicability of BGCFC for COTSbased small satellites.展开更多
This paper proposes a generic high-performance and low-time-overhead software control flow checking solution, graph-tree-based control flow checking （GTCFC） for space-borne commercial-off-the-shelf （COTS） processo...This paper proposes a generic high-performance and low-time-overhead software control flow checking solution, graph-tree-based control flow checking （GTCFC） for space-borne commercial-off-the-shelf （COTS） processors. A graph tree data structure with a topology similar to common trees is introduced to transform the control flow graphs of target programs. This together with design of IDs and signatures of its vertices and edges allows for an easy check of legality of actual branching during target program execution. As a result, the algorithm not only is capable of detecting all single and multiple branching errors with low latency and time overheads along with a linear-complexity space overhead, but also remains generic among arbitrary instruction sets and independent of any specific hardware. Tests of the algorithm using a COTS-processor-based onboard computer （OBC） of in-service ZDPS-1A pico-satellite products show that GTCFC can detect over 90% of the randomly injected and all-pattern-covering branching errors for different types of target programs, with performance and overheads consistent with the theoretical analysis; and beats well-established preeminent control flow checking algorithms in these dimensions. Furthermore, it is validated that GTCGC not only can be accommodated in pico-satellites conveniently with still sufficient system margins left, but also has the ability to minimize the risk of control flow errors being undetected in their space missions. Therefore, due to its effectiveness, efficiency, and compatibility, the GTCFC solution is ready for applications on COTS processors on pico-satellites in their real space missions.展开更多
Regression testing is the process of validating modified software to provide confidence that the changed parts of the software behave as intended and that the unchanged parts have not been adversely affected by the mo...Regression testing is the process of validating modified software to provide confidence that the changed parts of the software behave as intended and that the unchanged parts have not been adversely affected by the modifications. The goal of regression testing is to reduce the test suit by testing the new characters and the modified parts of a program with the original test suit. Regression testing is a high cost testing method. This paper presents a regression testing selection technique that can reduce the test suit on the basis of Control Flow Graph (CFG). It import the inherit strategy of object-oriented language to ensure an edge’s control domain to reduce the test suit size effectively. We implement the idea by coding the edge. An algorithm is also presented at last.展开更多
To solve the problems that the exception handling code is hard to test and maintain and that it affects the robustness and reliability of software, a method for evaluating the exception handling of programs is present...To solve the problems that the exception handling code is hard to test and maintain and that it affects the robustness and reliability of software, a method for evaluating the exception handling of programs is presented. The exception propagation graph （EPG） that describes the large programs with exception handling constructs is proposed by simplifying the control flow graph and it is applied to a case to verify its validity. According to the EPG, the exception handling code that never executes is identified; the points that are the most critical to controlling exception propagation are found; and the irrational exception handling code is corrected. The constructing algorithm for the EPG is given; thus, this provides a basis for automatically constructing the EPG and automatically correcting the irrational exception handling code.展开更多
In order to improve the efficiency of regression testing in web application,the control flow graph and the greedy algorithm are adopted.This paper considers a web page as a basic unit and introduces a test case select...In order to improve the efficiency of regression testing in web application,the control flow graph and the greedy algorithm are adopted.This paper considers a web page as a basic unit and introduces a test case selection method for web application regression testing based on the control flow graph.This method is safe enough to the test case selection.On the base of features of request sequence in web application,the minimization technique and the priority of test cases are taken into consideration in the process of execution of test cases in regression testing for web application.The improved greedy algorithm is also raised resulting in optimization of execution of test cases.The experiments indicate that the number of test cases which need to be retested is reduced,and the efficiency of execution of test cases is also improved.展开更多
基金Supported by the National Natural Science Foundation of China(62462036,62262031)Jiangxi Provincial Natural Science Foundation(20242BAB26017,20232BAB202010)+1 种基金Distinguished Youth Fund Project of the Natural Science Foundation of Jiangxi Province(20242BAB23011)the Jiangxi Province Graduate Innovation Found Project(YJS2023032)。
文摘Control Flow Graphs(CFGs)are essential for understanding the execution and data flow within software,serving as foundational structures in program analysis.Traditional CFG construction methods,such as bytecode analysis and Abstract Syntax Trees(ASTs),often face challenges due to the complex syntax of programming languages like Java and Python.This paper introduces a novel approach that leverages Large Language Models(LLMs)to generate CFGs through a methodical Chain of Thought(CoT)process.By employing CoT,the proposed approach systematically interprets code semantics directly from natural language,enhancing the adaptability across various programming languages and simplifying the CFG construction process.By implementing a modular AI chain strategy that adheres to the single responsibility principle,our approach breaks down CFG generation into distinct,manageable steps handled by separate AI and non-AI units,which can significantly improve the precision and coverage of CFG nodes and edges.The experiments with 245 Java and 281 Python code snippets from Stack Overflow demonstrate that our method achieves efficient performance on different programming languages and exhibits strong robustness.
基金Supported by the National Natural Science Foundation of China(61202110 and 61502205)the Project of Jiangsu Provincial Six Talent Peaks(XYDXXJS-016)
文摘With the rapid development of software technology, software vulnerability has become a major threat to computer security. The timely detection and repair of potential vulnerabilities in software, are of great significance in reducing system crashes and maintaining system security and integrity. This paper focuses on detecting three common types of vulnerabilities: Unused_Variable, Use_of_Uninitialized_Variable, and Use_After_ Free. We propose a method for software vulnerability detection based on an improved control flow graph(ICFG) and several predicates of vulnerability properties for each type of vulnerability. We also define a set of grammar rules for analyzing and deriving the three mentioned types of vulnerabilities, and design three vulnerability detection algorithms to guide the process of vulnerability detection. In addition, we conduct cases studies of the three mentioned types of vulnerabilities with real vulnerability program segments from Common Weakness Enumeration(CWE). The results of the studies show that the proposed method can detect the vulnerability in the tested program segments. Finally, we conduct manual analysis and experiments on detecting the three types of vulnerability program segments(30 examples for each type) from CWE, to compare the vulnerability detection effectiveness of the proposed method with that of the existing detection tool Cpp Check. The results show that the proposed method performs better. In summary, the method proposed in this paper has certain feasibility and effectiveness in detecting the three mentioned types of vulnerabilities, and it will also have guiding significance for the detection of other common vulnerabilities.
基金support from the National Natural Science Foundation of Chinathe Fundamental Research Funds for the Central Universities of China
文摘Abstract Single event upset （SEU） effect, caused by highly energized particles in aerospace, threatens the reliability and security of small satellites composed of commercialofftheshelves （COTS）. SEU induced control flow errors （CFEs） may cause unpredictable behavior or crashes of COTSbased small satellites. This paper proposes a generic softwarebased control flow checking technique （CFC） and bipartite graphbased control flow checking （BGCFC）. To simplify the types of illegal branches, it transforms the conventional control flow graph into the equivalent bipartite graph. It checks the legal ity of control flow at runtime by comparing a global signature with the expected value and introduces consecutive IDs and bitmaps to reduce the time and memory overhead. Theoretical analysis shows that BGCFC can detect all types of internode CFEs with constant time and memory overhead. Practical tests verify the result of theoretical analysis. Compared with previous techniques, BGCFC achieves the highest error detection rate, lower time and memory overhead; the composite result in evaluation fac tor shows that BGCFC is the most effective one among all these techniques. The results in both theory and practice verify the applicability of BGCFC for COTSbased small satellites.
基金supported by National Natural Science Foundation of China (No. 60904090)
文摘This paper proposes a generic high-performance and low-time-overhead software control flow checking solution, graph-tree-based control flow checking （GTCFC） for space-borne commercial-off-the-shelf （COTS） processors. A graph tree data structure with a topology similar to common trees is introduced to transform the control flow graphs of target programs. This together with design of IDs and signatures of its vertices and edges allows for an easy check of legality of actual branching during target program execution. As a result, the algorithm not only is capable of detecting all single and multiple branching errors with low latency and time overheads along with a linear-complexity space overhead, but also remains generic among arbitrary instruction sets and independent of any specific hardware. Tests of the algorithm using a COTS-processor-based onboard computer （OBC） of in-service ZDPS-1A pico-satellite products show that GTCFC can detect over 90% of the randomly injected and all-pattern-covering branching errors for different types of target programs, with performance and overheads consistent with the theoretical analysis; and beats well-established preeminent control flow checking algorithms in these dimensions. Furthermore, it is validated that GTCGC not only can be accommodated in pico-satellites conveniently with still sufficient system margins left, but also has the ability to minimize the risk of control flow errors being undetected in their space missions. Therefore, due to its effectiveness, efficiency, and compatibility, the GTCFC solution is ready for applications on COTS processors on pico-satellites in their real space missions.
基金This work was supported by Shanghai Municipal Science and Technology commission No.04ZR14105and Shanghai UniversitiesTechnology Development Foundation No.2002DZ46
文摘Regression testing is the process of validating modified software to provide confidence that the changed parts of the software behave as intended and that the unchanged parts have not been adversely affected by the modifications. The goal of regression testing is to reduce the test suit by testing the new characters and the modified parts of a program with the original test suit. Regression testing is a high cost testing method. This paper presents a regression testing selection technique that can reduce the test suit on the basis of Control Flow Graph (CFG). It import the inherit strategy of object-oriented language to ensure an edge’s control domain to reduce the test suit size effectively. We implement the idea by coding the edge. An algorithm is also presented at last.
基金The National Natural Science Foundation of China(No60503020)the National Basic Research Program of China (973Program) (No2002CB312000)+1 种基金the Natural Science Foundation of Jiangsu Province (NoBK2006094)the Science Research Foundation of China University of Mining and Technology
文摘To solve the problems that the exception handling code is hard to test and maintain and that it affects the robustness and reliability of software, a method for evaluating the exception handling of programs is presented. The exception propagation graph （EPG） that describes the large programs with exception handling constructs is proposed by simplifying the control flow graph and it is applied to a case to verify its validity. According to the EPG, the exception handling code that never executes is identified; the points that are the most critical to controlling exception propagation are found; and the irrational exception handling code is corrected. The constructing algorithm for the EPG is given; thus, this provides a basis for automatically constructing the EPG and automatically correcting the irrational exception handling code.
基金The National Natural Science Foundation of China(No.60503020,60503033,60703086)Opening Foundation of Jiangsu Key Laboratory of Computer Information Processing Technology in Soochow University(No.KJS0714)
文摘In order to improve the efficiency of regression testing in web application,the control flow graph and the greedy algorithm are adopted.This paper considers a web page as a basic unit and introduces a test case selection method for web application regression testing based on the control flow graph.This method is safe enough to the test case selection.On the base of features of request sequence in web application,the minimization technique and the priority of test cases are taken into consideration in the process of execution of test cases in regression testing for web application.The improved greedy algorithm is also raised resulting in optimization of execution of test cases.The experiments indicate that the number of test cases which need to be retested is reduced,and the efficiency of execution of test cases is also improved.
