The basis graph \%G\% for a linear programming consists of all bases under pivot transformations. A degenerate optimal basis graph G * is a subgraph of \%G\% induced by all optimal bases at a degenerate optimal verte...The basis graph \%G\% for a linear programming consists of all bases under pivot transformations. A degenerate optimal basis graph G * is a subgraph of \%G\% induced by all optimal bases at a degenerate optimal vertex x 0. In this paper, several conditions for the characterization of G * are presented.展开更多
Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing probl...Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.展开更多
The lack of existing solutions makes it really hard to understand formal specification languages since the application domain for representations is useful for the purpose of carrying out certain software engineering ...The lack of existing solutions makes it really hard to understand formal specification languages since the application domain for representations is useful for the purpose of carrying out certain software engineering operations such as slicing and the computation of program metrics.A Z specification dependence graph is presented in this letter. It draws on the strengths of a range of earlier works and adapts them, if necessary, to the Z language.展开更多
Program slice has many applications such as program debugging, testing, maintenance, and complexity measurement. A static slice consists of all statements in program P that may effect the value of variable v a...Program slice has many applications such as program debugging, testing, maintenance, and complexity measurement. A static slice consists of all statements in program P that may effect the value of variable v at some point p , and a dynamic slice consists only of statements that influence the value of variable occurrence for specific program inputs. In this paper, we concern the problem of dynamic slicing of object oriented programs which, to our knowledge, has not been addressed in the literatures. To solve this problem, we present the dynamic object oriented dependence graph (DODG)which is an arc classified digraph to explicitly represent various dynamic dependence between statement instances for a particular execution of an object oriented program. Based on the DODG, we present a two phase backward algorithm for computing a dynamic slice of an object oriented program.展开更多
An algorithm is proposed in this paper for solving two-dimensional bi-level linear programming problems without making a graph. Based on the classification of constraints, algorithm removes all redundant constraints, ...An algorithm is proposed in this paper for solving two-dimensional bi-level linear programming problems without making a graph. Based on the classification of constraints, algorithm removes all redundant constraints, which eliminate the possibility of cycling and the solution of the problem is reached in a finite number of steps. Example to illustrate the method is also included in the paper.展开更多
This paper proposes an extended system dependence graph called AspectSDG to represent control and data dependences for AspeetC＋＋ programs, and presents an approach for the construction of AspectSDG. This approach de...This paper proposes an extended system dependence graph called AspectSDG to represent control and data dependences for AspeetC＋＋ programs, and presents an approach for the construction of AspectSDG. This approach decomposes aspect-oriented programs into three parts： component codes, aspect codes, and weaving codes. It constructs program dependence graphs （PDGs） for each part, and then connects the PDGs at call sites to form the complete AspectSDG. The AspectSDG can deal with advice precedence correctly, and represent the additional dependences caused by aspect codes. Based on this model, we introduce how to compute a static slice of an AspectC＋ ＋ program.展开更多
This paper deals with a comparative study on testing of concurrent programs based on different techniques. The various challenges in testing concurrent programming are: defining test coverage criteria based on control...This paper deals with a comparative study on testing of concurrent programs based on different techniques. The various challenges in testing concurrent programming are: defining test coverage criteria based on control flow, generating control flow graph of nondeterministic programs, investigating the applicability of sequential testing criteria to parallel program testing etc. For solving these issues, some existing techniques are discussed in this study. Various researchers use an intermediate graph called Event Inter Actions Graph (EIAG) to solve the problem of generating the control flow graph of nondeterministic programs. Some researches propose an intermediate graph called Interaction Sequence Testing Criteria (ISTC) approach based on sequence of interactions to solve the problem of test coverage criteria based on control and data flow. Another method to solve the problem of generating test coverage based on control flow graph of nondeterministic programs is constraint based approach. It needs constrained elements to generate test case which includes structural element and constraint. The selection of good test cases has been addressed by test data generation technique. The technique of concurrent path analysis approach is used to solve the problem of applicability of sequential testing criteria to parallel program testing. It reduces the number of combined concurrent test paths. The sequential test paths are combined to form concurrent test path. The Integration and System Test Automation (ISTA) approach is used to solve the problem of applicability of sequential testing criteria to parallel program testing. It is used for automated test case generation and execution by using high-level Petri net is a finite state test model.展开更多
Program comprehension is one of the most important applications in decompilation. The more abstract the decompilation result the better it is understood. Intrinsic function is introduced by a compiler to reduce the ov...Program comprehension is one of the most important applications in decompilation. The more abstract the decompilation result the better it is understood. Intrinsic function is introduced by a compiler to reduce the overhead of a function call and is inlined in the code where it is called. When analyzing the decompiled code with lots of inlined intrinsic functions, reverse engineers may be confused by these detailed and repeated operations and lose the goal. In this paper, we propose a method based graph isomorphism to detect intrinsic function on the CFG (Control Flow Graph) of the target function first. Then we identify the boundary of the intrinsic function, determine the parameter and return value and reduce the intrinsic function to a single function call in the disassembled program. Experimental results show that our method is more efficient at reducing intrinsic functions than the state-of-art decompilers such as Hex-Rays, REC and RD (Retargetable Decompiler).展开更多
This paper presents a graph-based grading system for Java introductory programming courses, eGrader. This system grades submission both dynamically and statically to ensure a complete and through grading job. While dy...This paper presents a graph-based grading system for Java introductory programming courses, eGrader. This system grades submission both dynamically and statically to ensure a complete and through grading job. While dynamic analysis is based on JUnit framework, the static analysis is based on the graph representation of the program and its quality which is measured by software metrics. The graph representation is based on the Control Dependence Graphs (CDG) and Method Call Dependencies (MCD). eGrader outperforms existing systems in two ways: the ability of grading submission with semantic-errors, effectively, and generating reports for students, as a feedback on their performance, and instructors on the overall performance of the class. eGrader is well received by instructors not only for saving time and effort but also for its high success rate that is measured by four performance indicators which are sensitivity (97.37%), specificity (98.1%), precision (98.04%) and accuracy (97.07%).展开更多
The development of the information technology has brought threats to human society when it has influenced seriously the global politics, economics and military etc. But among the security of information system, buffer...The development of the information technology has brought threats to human society when it has influenced seriously the global politics, economics and military etc. But among the security of information system, buffer overrun vulnerability is undoubtedly one of the most important and common vulnerabilities. This paper describes a new technology, named program slicing, to detect the buffer overflow leak in security-critical C code. First, we use slicing technology to analyze the variables which may be with vulnerability and extract the expressions which will bring memory overflow. Secondly, we utilize debug technology to get the size of memory applied by the variable and the size of memory used for these code segments (the slicing result) further. Therefore we can judge whether it will overflow according to the analysis above. According to the unique excellence of program slicing performing in the large-scale program’s debugging, the method to detect buffer overrun vulnerability described in this paper will reduce the workload greatly and locate the code sentences affected by corresponding variable set quickly, particularly including the potential vulnerability caused by parameter dependence among the subroutines.展开更多
基金Project supported by the National Natural Science Foundation of China!(19771075)
文摘The basis graph \%G\% for a linear programming consists of all bases under pivot transformations. A degenerate optimal basis graph G * is a subgraph of \%G\% induced by all optimal bases at a degenerate optimal vertex x 0. In this paper, several conditions for the characterization of G * are presented.
文摘Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.
文摘The lack of existing solutions makes it really hard to understand formal specification languages since the application domain for representations is useful for the purpose of carrying out certain software engineering operations such as slicing and the computation of program metrics.A Z specification dependence graph is presented in this letter. It draws on the strengths of a range of earlier works and adapts them, if necessary, to the Z language.
文摘Program slice has many applications such as program debugging, testing, maintenance, and complexity measurement. A static slice consists of all statements in program P that may effect the value of variable v at some point p , and a dynamic slice consists only of statements that influence the value of variable occurrence for specific program inputs. In this paper, we concern the problem of dynamic slicing of object oriented programs which, to our knowledge, has not been addressed in the literatures. To solve this problem, we present the dynamic object oriented dependence graph (DODG)which is an arc classified digraph to explicitly represent various dynamic dependence between statement instances for a particular execution of an object oriented program. Based on the DODG, we present a two phase backward algorithm for computing a dynamic slice of an object oriented program.
文摘An algorithm is proposed in this paper for solving two-dimensional bi-level linear programming problems without making a graph. Based on the classification of constraints, algorithm removes all redundant constraints, which eliminate the possibility of cycling and the solution of the problem is reached in a finite number of steps. Example to illustrate the method is also included in the paper.
基金Supported by the National Science Foundation forDistinguished Young Scholars (60425206) the National Natural Sci-ence Foundation of China ( 90412003 , 60373066 , 60403016 ,60503033) the National Basic Research Programof China (973 Pro-gram2002CB312000)
文摘This paper proposes an extended system dependence graph called AspectSDG to represent control and data dependences for AspeetC＋＋ programs, and presents an approach for the construction of AspectSDG. This approach decomposes aspect-oriented programs into three parts： component codes, aspect codes, and weaving codes. It constructs program dependence graphs （PDGs） for each part, and then connects the PDGs at call sites to form the complete AspectSDG. The AspectSDG can deal with advice precedence correctly, and represent the additional dependences caused by aspect codes. Based on this model, we introduce how to compute a static slice of an AspectC＋ ＋ program.
文摘This paper deals with a comparative study on testing of concurrent programs based on different techniques. The various challenges in testing concurrent programming are: defining test coverage criteria based on control flow, generating control flow graph of nondeterministic programs, investigating the applicability of sequential testing criteria to parallel program testing etc. For solving these issues, some existing techniques are discussed in this study. Various researchers use an intermediate graph called Event Inter Actions Graph (EIAG) to solve the problem of generating the control flow graph of nondeterministic programs. Some researches propose an intermediate graph called Interaction Sequence Testing Criteria (ISTC) approach based on sequence of interactions to solve the problem of test coverage criteria based on control and data flow. Another method to solve the problem of generating test coverage based on control flow graph of nondeterministic programs is constraint based approach. It needs constrained elements to generate test case which includes structural element and constraint. The selection of good test cases has been addressed by test data generation technique. The technique of concurrent path analysis approach is used to solve the problem of applicability of sequential testing criteria to parallel program testing. It reduces the number of combined concurrent test paths. The sequential test paths are combined to form concurrent test path. The Integration and System Test Automation (ISTA) approach is used to solve the problem of applicability of sequential testing criteria to parallel program testing. It is used for automated test case generation and execution by using high-level Petri net is a finite state test model.
文摘Program comprehension is one of the most important applications in decompilation. The more abstract the decompilation result the better it is understood. Intrinsic function is introduced by a compiler to reduce the overhead of a function call and is inlined in the code where it is called. When analyzing the decompiled code with lots of inlined intrinsic functions, reverse engineers may be confused by these detailed and repeated operations and lose the goal. In this paper, we propose a method based graph isomorphism to detect intrinsic function on the CFG (Control Flow Graph) of the target function first. Then we identify the boundary of the intrinsic function, determine the parameter and return value and reduce the intrinsic function to a single function call in the disassembled program. Experimental results show that our method is more efficient at reducing intrinsic functions than the state-of-art decompilers such as Hex-Rays, REC and RD (Retargetable Decompiler).
文摘This paper presents a graph-based grading system for Java introductory programming courses, eGrader. This system grades submission both dynamically and statically to ensure a complete and through grading job. While dynamic analysis is based on JUnit framework, the static analysis is based on the graph representation of the program and its quality which is measured by software metrics. The graph representation is based on the Control Dependence Graphs (CDG) and Method Call Dependencies (MCD). eGrader outperforms existing systems in two ways: the ability of grading submission with semantic-errors, effectively, and generating reports for students, as a feedback on their performance, and instructors on the overall performance of the class. eGrader is well received by instructors not only for saving time and effort but also for its high success rate that is measured by four performance indicators which are sensitivity (97.37%), specificity (98.1%), precision (98.04%) and accuracy (97.07%).
文摘The development of the information technology has brought threats to human society when it has influenced seriously the global politics, economics and military etc. But among the security of information system, buffer overrun vulnerability is undoubtedly one of the most important and common vulnerabilities. This paper describes a new technology, named program slicing, to detect the buffer overflow leak in security-critical C code. First, we use slicing technology to analyze the variables which may be with vulnerability and extract the expressions which will bring memory overflow. Secondly, we utilize debug technology to get the size of memory applied by the variable and the size of memory used for these code segments (the slicing result) further. Therefore we can judge whether it will overflow according to the analysis above. According to the unique excellence of program slicing performing in the large-scale program’s debugging, the method to detect buffer overrun vulnerability described in this paper will reduce the workload greatly and locate the code sentences affected by corresponding variable set quickly, particularly including the potential vulnerability caused by parameter dependence among the subroutines.
