Using Maximal Slices as a Solution to the 'Output Variable' Problem for Calculating Slice-Based Cohesion Metrics

July 04, 2011 - 12:24

Software metrics are widely used to quantify software quality; cohesion is one such metric. It is a measure of the 'inter-relatedness' of code. Sliced-based cohesion metrics use program slicing to calculate the cohesion of a software module by using `output variables' as slicing criteria. The definition of `output variables', however, varies in different studies. Unfortunately, these different definitions lead to different values for the metrics. We solve this problem by introducing standardised versions (independent of the `output variables') of previous definitions of the slice-based metrics.   Our approach computes metrics based only on the maximal slices in a software module.  These can be computed automatically without the need to specify which points contain `output variables'.  We call the slicing criteria that generate maximal slices, in a software module, `crucial points'. Empirical evidence suggests that crucial points represent points of interest in a program and strongly correlate with previous definitions of `output variables'. We believe that using crucial points instead of output variables in slice-based metrics may lead to a more intuitively accurate measurement of cohesion.

This is a summary of the draft paper attached providing standardised definitions of slice-based cohesion metrics.

Sliced-based cohesion metrics attempt to determine the cohesiveness of a program module by calculating the intersection of slices. Using slices to calculate cohesion metrics works well due to the relatedness definition of cohesion. If statements in a module are related it is likely that their slices will share many statements. On the other hand, if there are multiple tasks taking place in a module it is likely that the intersection will be small or empty. Weiser1 defined three metrics related to cohesion, which have been further refined and expanded by others1 2 3 4:

  • tightness - the ratio of the size of the slice intersection to the total module length
  • minimum coverage - the ratio of the smallest slice to the total module length
  • coverage - the ratio of the average slice size to the total module lengh
  • maximum coverage - the ratio of the largest slice size to the total module length
  • overlap - the average ratio of the intersection of all slices to slice size

The 'Output Variable' Problem

The calculation slice-based cohesion metrics poses a problem: what are the slicing criteria? Previously, the concept of an 'output variable' has been used. The definition of an 'output variable' varies between studies; this is a problem for replicating or comparing such studies.

Green et al. 5 compared 11 papers which used 'output variables' and came to the conclusion that there are four main types of `output variables': "the return value of a function; global variables modified by a fucntion; parameters passed by reference to, and modified by, a function; and any variables printed, written to a file, or otherwise output to the external environment"5. Most of the previous studies in the area of slice-based metrics have used CodeSurfer which works with C programs. The last category, according to Green et al., is the most difficult to capture with CodeSurfer (as it is the most difficult to define).

It turns out that the values of the metrics are highly sensitive to the choice of slices used in their computation. Many authors have grappled with the problem of which slices to include in order to come up with meaningful values for the metrics. We feel that the choices appear somewhat arbitrary and are in some sense trying to second-guess what the slices of interest are.

Maximal Slices

We propose the use of maximal slices as the basis of the definition of slice-based cohesion metrics. In our definition there is no need to define the concept of an `output variable' which allows us to provide a standard definition of slice-based cohesion metrics. We believe that maximal slices capture the most interesting parts of a program; previous studies have attempted to gather the same useful information by selecting slicing criteria. See paper for definitions of metrics using maximal slices.

Slice-based cohesion metrics slices are calculated by using a set of slices - the 'output variables' are not important, the slices are. If a slice is maximal it would suggest that the statements in that slice perform one task; whereas a slice that is a subset of another slice could be thought of as performing a sub-task of a larger task.  Disjoint maximal slices would suggest that the set of statements in each slice are performing completely separate tasks; for example, if we calculate maximal slices for a jar file containing multiple class files we may find completely disjoint maximal slices if each class is an unrelated program.

Ideally, the intersection of maximal slices of a program method should be large, corresponding to a highly inter-related set of program statements. However, if we are considering Java classes or packages we would consider a smaller intersection between them good, corresponding to the modularity of object-oriented programming.  In order to calculate the values of the slice-based cohesion metrics, backward slices are computed for each statement in a module, starting with the last statement. Maximal slices are computed from the set of slices and used to calculate the metrics.

Maximal slices are special because any code that occurs in a maximal slice cannot affect code outside a maximal slice; this guarantees that "all points of interest" that may be affected by the slice will be included in the slice. The pleasing "closed property" of maximal slices make them an ideal choice for computing slice-based metrics, removing the need for previous arbitrary choices. Maximal slices are slices which have "maximal effect".  

Empirical Study

We have used the Indus Java program slicer to perform an empirical study of 378 small Java programs taken from Indus performs analysis and slicing on the Jimple intermediate-representation provided by the Soot framework. Jimple is a fully typed three-address code representation of Java/Java bytecode. We found that the majority of statements designated as crucial points correlate with definitions of 'output variables' in previous studies; for example, 100% of System.out.print(ln) calls were designated as crucial points. See paper for more details.

Each method will have at least 1 crucial point and the average number of crucial points per method, in our study, is 4.76. The average length of a method is 13.57 Jimple statements. Java programs, compared with other languages such as C,  contain a high number of methods with a small length (e.g. < 3 Jimple statements) due to the use of 'getters' and 'setters' in object-oriented programming, and default constructors. This skews results when averaging slice-based cohesion metrics of methods in a program (as previous studies have done) and makes it hard to compare the metrics to other languages. Our study revealed that 38% of methods contain fewer than 3 Jimple statements.

Conclusion and Future Work

We have used maximal slices to redefine slice-based cohesion metrics without the use of the previously ambiguous concept of 'output variables'. This standard definition is an improvement because it will allow further studies in this area to be more easily comparable.

The use of maximal slices is appropriate because we believe that a maximal slice captures an interesting part of a program; any code that occurs in a maximal slice cannot affect code outside the maximal slice. Intersecting maximal slices represent inter-related program statements, while disjoint maximal slices suggest multiple tasks are being performed. 

For future work we will define new metrics in terms of maximal slices which we believe will compute slice-based cohesion metrics more intuitively, especially in the context of object-oriented programming.  A fruitful avenue of research that we are now investigating is representing a program module as a graph of slices. The visualisation of these graphs may give a better intuitive insight into the cohesive properties of programs rather than a simple value. A further advantage is that it gives the opportunity of defining metrics in terms of standard graph metrics, such as communities.  These visualisation might also be useful for locating  software watermarks  or malware within programs - allowing us to define better software watermarks, or easily remove malware.