Model Driven Program Slicing

From AtlanMod

Slicing and MDE : overview

under construction

According to [1],[4] we identify different way of doing program slicing. Program Slicing is a program analysis technique used to find which program part(e.g., statement(s) or expression(s)) is affected by a given program and vice versa. The program in which the slice is identified (e.g., affect/affected the selected program part) is called a substrate program. The selected program part is referred as slice criterion. Finally, the portion of code obtained by slicing technique is called a program slice.

A program slice constructed by identifying substrate program that affect a given criterion is called a backward slice. Conversely, a program slice affected by a criterion is called a forward slice.

The concept of slice criterion affecting or affected by another program is captured as program dependences. Program Slicing advocates the use of specific graph (or model) either to represent dependencies or to manipulate code.

Static Slicing

Dynamic Slicing

Merging information

A first experiment with MDE program Slicing

Overview : transformation chain

We show, in the figure below, a transformation chain that takes an Java Abstract Syntax Tree (AST) as input model. Such AST is obtains by code injection: the Java code is transform in a model. Then the slicing computation is done by a sequence of transformations which are described in the next parts.

The "special" case of Control Flow Graph (CFG)

Control flow graph is used in program analysis for determining properties and behaviour of a program without executing it. CFG is also used in program compilation, optimization, test. In the scope of this page we focus on the use of CFG for program Slicing.

"Standard" CFG computation

A CFG node is build for each program statement. CFG nodes are sequence of statements that represent the flow of a program. However there is two kinds of statements that are a bit different: Conditional and Iterative Node. Such nodes promotes alternative branching in control flow regarding a condition. Moreover, Iterative nodes have a special "back-edge" for representing iteration. Figure below shows how the two special kinds of statements are transformed into CFG nodes.

CFG with Weaving

Ongoing study

Computation of a complete CFG (including expression) may takes a lot of time on a large project. Information is already present in the input AST model. We just have to link (or weave) CFG statement nodes to AST nodes.

Program Dependence Graph Computation(PDG)

Program Dependence Graph is composed of the same nodes as CFG, but linked by two relations : control flow and data dependence. The following explanation assumes that PDG is build from CFG.

Control Flow Computing

Control flow relation is almost the same as CFG. However, the control flow is hierarchically decomposed against "conditional branches". False condition node is on the same level as the conditional node itself. True conditional node is applied on a sub-level.

Data Dependence Computing

  Let first define some function: 
  1/ function Succ(a) where a ∈ CFG nodes and that return the set of nodes that are "after a" in the CFG flow.
  2/ function a.mvar which returns variable modified in the expression supported by the node a.
  3/ function a.uVar which returns variable used in the expression supported by the node a.

A node x is data dependent of a node y if:

x ∈ Succ(y) and if x.uVar ∈ x.mVar.

Current issues

Slice Computation

Under Construction

Beyond Program Slicing: Computing Metrics and Querying Dependence Graphs (PDG and CFG)

Metrics

Control Flow gives a lot of information about program structure. For example, thanks to CFG we can compute the "cyclomatic complexity" ([1]) of a program: it consists in identifying all possible execution branches. In other word, cyclomatic complexity is the computation of all path in a graph. Given a method, a Cyclomatic complexity superior to 10 is supposed to be to high and might be a sources of bug and makes hard code maintenance.

Cyclomatic complexity (written Cc) can be computed by the formula :

   Cc = E − N + 2P
   where
   E = the number of edges of the graph
   N = the number of nodes of the graph
   P = the number of connected components.

A CFG is not a scattered graph (e.g. there is only one connect graph), as a consequence its P number = 1. The simplified formula gives:

  Cc = E − N + 2

In ATL this is translated by the following rule: two helper for computing respectively number of Nodes (NbNodes) and number of Edges (NbEdges). The rule create a view element which support, given a method, the cyclomatic complexity.

helper context CFG!MControlFlowGraph def: NbNodes : Integer = self.nodes->size();
helper context CFG!MControlFlowGraph def: NbEdges : Integer =  self.nodes->select(e | not(e.toNode.oclIsUndefined()))->size()
 + (self.nodes->select(e | e.oclIsKindOf(CFG!ConditionalNode) or e.oclIsKindOf(CFG!IterativeNode))->size()*2);	
							
rule MethodCFG2toView {
    from mcfg : 
            CFG!MControlFlowGraph
    to  view : 
            VIEW!ConcernedMethod(cyclomaticComplexity<-((mcfg.NbEdges-mcfg.NbNodes)+2))	
}

Dependence Specific Query Language

Analysing, browsing by dependence graph queries may be a useful way to find bugs, to help designer to improve coupling between code statement, etc. The category of queries that can be done on dependence graphs are limited. Inspired by the work done in [5], we promotes the use of a Domain Specific Query language that ease the construction of query on such graph. Operational Semantic of such language is done by ATL with a fixed output metamodel (e.g., Query Result Metamodel).

Bibliography

[1] Tip,F., A survey of Program Slicing Techniques, Journal of Programming Language, 1995

[2] Otteinstein, K.J., Otteinstein, L.M., The program dependence graph in software development environement. In proc. of ACM/SIGSOFT/SIGPLAN Software Engineering Symposium on Pratical Software Development Environements pages 177-184, SIGPLAN Notices 19(5)

[3] Jouault, F., Sottet, J.S.,An AmmA/ATL Solution for the GraBaTs 2009 Reverse Engineering Case Study. 5th International Workshop on Graph-Based Tools, 2009.

[4] Prasad Ranganath V., Indus Java Program Slicer, Technical Documentation, Kansas State University, http://projects.cis.ksu.edu/gf/download/docmanfileversion/107/1465/indus-ug.pdf

[5] Jayaraman G., Indus and Kaveri, Technical Documentation, Kansas State University, http://projects.cis.ksu.edu/gf/download/docmanfileversion/100/1458/Kaveri-0.6.0B.pdf