A novel formal approach to program slicing

Program slicing is a well-known program analysis technique that extracts the elements of a program related to a particular computation. The current slicing methods, however, are singular （mainly based on a program or system dependence graph）, and lack good reusability and flexibility. In this paper, we present a novel formal method for program slicing, modular monadic program slicing, which abstracts the computation of program slicing as a slice monad transformer, and applies it to semantic descriptions of the program analyzed in a modular way, forming the corresponding monadic slicing algorithms. The modular abstraction mechanism allows our slicing method to possess excellent modularity and language-flexibility properties. We also give the related axioms of our slice monad transformer, the proof of the correctness and the implementation of monadic slicing algorithms. We reveal the relations of our algorithms and graph-reachable slicing algorithms.

Automatic Circuit Extractor for HDL Description Using Program Slicing

Design extraction and reduction have been extensively used in modern VLSI design process. The extracted and reduced design can be efficiently processed by various applications, such as formal verification, simulation, automatic test pattern generation (ATPG), etc. This paper presents a new circuit extraction method using program slicing technique, and develops an elegant theoretical basis based on program slicing for circuit extraction from Verilog description. The technique can obtain a chaining slice for given signals of interest. Compared with related researches, the main advantages of the method include that it is fine grain, it has no hardware description language (HDL) coding style limitation; it is precise and is capable of dealing with various Verilog constructions. The technique has been integrated with a commercial simulation environment and incorporated into a design process. The results of practical designs show the significant benefits of the approach.

Dynamic Slicing of Object Oriented Programs

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.

SymPas:Symbolic Program Slicing

Program slicing is a technique for simplifying programs by focusing on selected aspects of their behavior.Current mainstream static slicing methods operate on dependence graph PDG(program dependence graph)or SDG(system dependence graph),but these friendly graph representations may be a bit expensive for some users.In this paper we attempt to study a light-weight approach of static program slicing,called Symbolic Program Slicing(SymPas),which works as a dataflow analysis on LLVM(low-level virtual machine).In our SymPas approach,slices are stored in symbolic forms,not in procedures being re-analyzed(cf.procedure summaries).Instead of re-analyzing a procedure multiple times to find its slices for each callling context,we calculate a single symbolic slice which can be instantiated at call sites avoiding re-analysis;SymPas is implemented with LLVM to perform slicing on LLVM intermediate representation(IR).For comparison,we systematically adapt IFDS(interprocedural finite distributive subset)analysis and the SDG-based slicing method(SDGIFDS)to statically slice IR programs.Evaluated on open-source and benchmark programs,our backward SymPas shows a factor-of-6 reduction in time cost and a factor-of-4 reduction in space cost,compared with backward SDG-IFDS,thus being more efficient.In addition,the result shows that after studying slices from 66 programs,ranging up to 336800 IR instructions in size,SymPas is highly size-scalable.

Dependence Analysis Based on Dynamic Slicing for Debugging

Dynamic program slicing is an effective technique for narrowing the errors to the relevant parts of a program when debugging. Given a slicing criterion, the dynamic slice contains only those statements that actually affect the variables in the slicing criterion. This paper proposes a dynamic slicing method based on static dependence analysis. It uses the program dependence graph and other static information to reduce the information needed to be traced during program execution. Thus, the efficiency is dramatically improved while the precision is not depressed. The slicing criterion is modified to fit for debugging. It consists of file name and the line number at which the statement is.

A Model for Slicing JAVA Programs Hierarchically

Program slicing can be effectively used to debug, test, analyze, understand and maintain objectoriented software. In this paper, a new slicing model is proposed to slice Java programs based on their inherent hierarchical feature. The main idea of hierarchical slicing is to slice programs in a stepwise way, from package level, to class level, method level, and finally up to statement level. The stepwise slicing algorithm and the related graph reachability algorithms are presented, the architecture of the Java program Analyzing TOol (JATO) based on hierarchical slicing model is provided, the applications and a small case study are also discussed. Keywords software engineering - hierarchical model - program slicing - JAVA - stepwise algorithm - JATO This work is supported by the National Natural Science Foundation of China under Grant No.60473065 and the Outstanding Youth Teacher Support Foundation of Southeast University under Grant No.4009001011.Bi-Xin Li is a professor in Southeast University from Jan., 2004. He received the Ph.D. degree in computer software and theory from Nanjing University in 2001. From Apr. 2001 to Apr. 2002, he worked at TUCS (Turku Center for Computer Science) for one year as a post-doctoral researcher. From Apr. 2002 to Dec. 2003, he worked. at Department of Computer and Information Science, NTNU (Norwegian University of Science and Technology), and CWI (the Centrum voor Wiskunde en Informatica), both as an ERCIM Fellow. His current research interests include software construction, software testing, SQA techniques, software architecture and component techniques, safety-critical system and formal verification, etc.Xiao-Cong Fan is a senior researcher in the Inteligent Agent Lab of the Pennsylvania State University from 2002. He received the Ph.D. degree from Nanjing University in 1999. From 2000 to 2002, he worked at the turku Centre for Computer Science and the Computer Science Department of Abo Akademi University in Finland, where he participated in the projects SOCOS and SPROUT, which developed a methodology for software platform construction based on the Refinement Calculus. He currently works on formal agent theories in teamwork, and projects for applying these theories.Jun Pang is now a Ph.D. candidate in CWI, the Netherlands. He received the B.Sc. and M.Sc. degrees in computer science from Nanjing University, China, in 1997 and 2000. His research interests include protocol verification, process algebra, safety critical systems, security, testing, software architecture etc.Jian-Jun Zhao is an associate professor of computer science at Fukuoka Institute of Technology, Japan. He received the B.S. degree in computer science from Tsinghua University, China, in 1987, and the Ph.D. degree in computer science from Kyushu University, Japan, in 1997. His research interests include program analysis and compiler, software architecture analysis, aspect-oriented software development, and ubiquitous computing environment.

A Component Mining Approach to Incubate Grid Services in Object-Oriented Legacy Systems

This paper describes an approach for Grid service component mining in object-oriented legacy systems, applying software clustering, architecture recovery, program slicing and wrapping techniques to decompose a legacy system, analyse the concerned components and integrate them into a Grid environment. The resulting components with core legacy code function in a Grid service framework.

Precise slicing of interprocedural concurrent programs

Program slicing is an effective technique for an- alyzing concurrent programs. However, when a conventional closure-based slicing algorithm for sequential programs is ap- plied to a concurrent interprocedural program, the slice is usually imprecise owing to the intransitivity of interference dependence. Interference dependence arises when a state- ment uses a variable defined in another statement executed concurrently. In this study, we propose a global dependence analysis approach based on a program reachability graph, and construct a novel dependence graph called marking-statement dependence graph （MSDG）, in which each vertex is a 2-tuple of program state and statement. In contrast to the conven- tional program dependence graph where the vertex is a state- ment, the dependence relation in MSDG is transitive. When traversing MSDG, a precise slice will be obtained. To en- hance the slicing efficiency without loss of precision, our slic- ing algorithm adopts a hybrid strategy. The procedures con- taining interaction statements between threads are inlined and sliced by the slicing algorithm based on program reachability graphs while allowing other procedures to be sliced as se- quential programs. We have implemented our algorithm and three other representative slicing algorithms, and conducted an empirical study on concurrent Java programs. The exper- imental results show that our algorithm computes more pre- cise slices than the other algorithms. Using partial-order re- duction techniques, which are effective for reducing the size of a program reachability graph without loss of precision, ouralgorithm is optimized, thereby improving its performance to some extent.

Complexity Measure Based on ProgramSlicing and Its Validation

The popular single-factor complexity measure cannot comprehensively reflect program complexity and the existing hybrid complexity measure cannot express the interactive behaviors of programs. To treat these problems, in this paper, we propose a complexity measure based on program slicing（CMBPS）. CMPBS not only can evaluate factors which affect program complexity such as the length of the program, control flow, data flow and data types of output variables, but also can give expression of the interactive relation between programs. And we also prove that CMBPS satisfies all of Weyuker properties. Compared with the popular complexity measures, CMBPS is a well-structured complexity measure.

An Object Extraction Model Using Association Rules and Dependence Analysis

Extracting objects from legacy systems is a basic step in system's object orientation to improve the maintainability and understandability of the systems. A new object extraction model using association rules and dependence analysis is proposed. In this model data are classified by association rules and the corresponding operations are partitioned by dependence analysis.

A Two-folded Impact Analysis of Schema Changes on Database Applications

Database applications are becoming increasingly popular, mainly due to the advanced data management facilities that the underlying database management system offers compared against traditional legacy software applications. The interaction, however, of such applications with the database system introduces a number of issues, among which, this paper addresses the impact analysis of the changes performed at the database schema level. Our motivation is to provide the software engineers of database applications with automated methods that facilitate major maintenance tasks, such as source code corrections and regression testing, which should be triggered by the occurrence of such changes. The presented impact analysis is thus two-folded： the impact is analysed in terms of both the affected source code statements and the affected test suites concerning the testing of these applications. To achieve the former objective, a program slicing technique is employed, which is based on an extended version of the program dependency graph. The latter objective requires the analysis of test suites generated for database applications, which is accomplished by employing testing techniques tailored for this type of applications. Utilising both the slicing and the testing techniques enhances program comprehension of database applications, while also supporting the development of a number of practical metrics regarding their maintainability against schema changes. To evaluate the feasibility and effectiveness of the presented techniques and metrics, a software tool, called DATA, has been implemented. The experimental results from its usage on the TPC-C case study are reported and analysed.

Source Code Prioritization Using Forward Slicing for Exposing Critical Elements in a Program

Even after thorough testing, a few bugs still remain in a program with moderate complexity. These residual bugs are randomly distributed throughout the code. We have noticed that bugs in some parts of a program cause frequent and severe failures compared to those in other parts. Then, it is necessary to take a decision about what to test more and what to test less within the testing budget. It is possible to prioritize the methods and classes of an object-oriented program according to their potential to cause failures. For this, we propose a program metric called influence metric to find the influence of a program element on the source code. First, we represent the source code into an intermediate graph called extended system dependence graph. Then, forward slicing is applied on a node of the graph to get the influence of that node. The influence metric for a method m in a program shows the number of statements of the program which directly or indirectly use the result produced by method m. We compute the influence metric for a class c based on the influence metric of all its methods. As influence metric is computed statically, it does not show the expected behavior of a class at run time. It is already known that faults in highly executed parts tend to more failures. Therefore, we have considered operational profile to find the average execution time of a class in a system. Then, classes are prioritized in the source code based on influence metric and average execution time. The priority of an element indicates the potential of the element to cause failures. Once all program elements have been prioritized, the testing effort can be apportioned so that the elements causing frequent failures will be tested thoroughly. We have conducted experiments for two well-known case studies -- Library Management System and Trading Automation System -- and successfully identified critical elements in the source code of each case study. We have also conducted experiments to compare our scheme with a related scheme. The experimental studies justify that our approach is more accurate than the existing ones in exposing critical elements at the implementation level.

Application of Dynamic Slicing in Test Data Generation

The program slicing technique is employed to calculate the current values of the variables at some interest points in software test data generation. This paper introduces the concept of statement domination to represent the multiple nests, and presents a dynamic program slice algorithm based on forward analysis to generate dynamic slices. In the approach, more attention is given to the statement itself or its domination node, so computing program slices is more easy and accurate, especially for those programs with multiple nests. In addition, a case study is discussed to illustrate our algorithm. Experimental results show that the slicing technique can be used in software test data generation to enhance the effectiveness.