A-CluB: Automated Cluster Breaking

Lead Research Organisation: King's College London
Department Name: Computer Science


Recent work shows that many real world programs contain large dependence clusters: knots of mutually dependent program statements. In a dependence cluster, every statement depends on every other statement. It is not hard to imagine the difficulties that large dependence clusters may produce. In order to understand any statement in a dependence cluster, it is possible that all other statements in the cluster need to be considered. It will be very hard to disentangle statements in a cluster to allow reuse of components, or refactoring of the system. Any potential change to an element of a cluster, will have an impact that is large and potentially far reaching, because it may affect any or all of the other statements in the cluster.This visiting fellow project builds on the previous work of Binkley and Harman (and others) on slice based dependence analysis. The aim is to better understand the empirically observed phenomenon of dependence clusters and to develop algorithms and techniques for decomposing these clusters. This will produce algorithms and methods for Automated Cluster Busting, thereby overcoming the problems that these clusters pose.


10 25 50

publication icon
Binkley D (2008) Dependence Anti Patterns

publication icon
McMinn P (2009) Empirical evaluation of a nesting testability transformation for evolutionary testing in ACM Transactions on Software Engineering and Methodology

Description Many real world programs contain surprisingly many surprisingly large dependence clusters.
Exploitation Route Practicing software engineers may find that these large clusters hep to explain why code is so hard to understand. Detecting them may help to avoid problems in software maintenance and evolution. The research finding warns other researchers working on dependence analysis that these clusters may skew the results of analysis. It has the potential to feed into tools for program comprehension, testing and maintenance.
Sectors Digital/Communication/Information Technologies (including Software),Transport

URL http://www.cs.loyola.edu/~binkley/aclub/
Description The AstreNet project was a network that, inter alia, collaboration between DaimlerChrysler and my team, identified the importance of dependents clusters in software. This project, A-Club, was a visiting Fellowship for Professor David Binkley, from United States. Prof. Binkley is Nexpert on dependents analysis, and the project around him, my team and DaimlerChrysler to collaborate on the development of techniques for identifying, understanding, and decomposing dependence clusters in software. The results were not only used by DaimlerChrysler, but also by many other researchers and organisations into Europe and the United States. Since our initial work on the programming language see, widely used in embedded systems in the automotive industry, as typified by DaimlerChrysler, many other researchers have found dependents clusters in languages such as Java and even, COBOL. Since these languages are ubiquitous and critical to our national infrastructure, and there is a widespread belief that dependents clusters inhibit proper software quality assurance, importance of this finding it hard to overstate.
First Year Of Impact 2008
Sector Transport
Impact Types Societal,Economic