Modeling software evolution by evolving interoperation graphs

Software evolution is the process of software change, most often change in software requirements. This paper presents a theoretical model for the evolution of component‐based software, based on evolving interoperation graphs. The model assumes that each change consists of smaller granularity steps of change propagation, each of them being a visit to one specific component. If the component is modified, it may no longer fit with the other components because it may no longer properly interact with them. In that case secondary changes must be made in neighboring components, which may trigger additional changes, etc. The paper contains an example of evolution of a calendar program, represented in UML. This revised version was published online in June 2006 with corrections to the Cover Date.     

Collaborative technologies for evolving software systems

The article discusses four major collaboration theme areas: collaborative information engineering; collaborative process and workflow; collaboration support (awareness); and integration of collaborative systems. Various projects incorporating these technologies are outlined. All of the projects described are developing component technologies intended for mixing and matching with each other and with technologies under investigation by other EDCS projects not particularly concerned with collaborative work, as well as with COTS software. Only GroupSpaces intends to assemble a full-blown, directly usable software development environment framework, and that comprises components, developed under EDCS and available off-the-shelf     

Discovering correlated spatio-temporal changes in evolving graphs

Graphs provide powerful abstractions of relational data, and are widely used in fields such as network management, web page analysis and sociology. While many graph representations of data describe dynamic and time evolving relationships, most graph mining work treats graphs as static entities. Our focus in this paper is to discover regions of a graph that are evolving in a similar manner. To discover regions of correlated spatio-temporal change in graphs, we propose an algorithm called cSTAG. Whereas most clustering techniques are designed to find clusters that optimise a single distance measure, cSTAG addresses the problem of finding clusters that optimise both temporal and spatial distance measures simultaneously. We show the effectiveness of cSTAG using a quantitative analysis of accuracy on synthetic data sets, as well as demonstrating its utility on two large, real-life data sets, where one is the routing topology of the Internet, and the other is the dynamic graph of files accessed together on the 1998 World Cup official website.

Understanding cost drivers of software evolution: a quantitative and qualitative investigation of change effort in two evolving software systems

Making changes to software systems can prove costly and it remains a challenge to understand the factors that affect the costs of software evolution. This study sought to identify such factors by investigating the effort expended by developers to perform 336 change tasks in two different software organizations. We quantitatively analyzed data from version control systems and change trackers to identify factors that correlated with change effort. In-depth interviews with the developers about a subset of the change tasks further refined the analysis. Two central quantitative results found that dispersion of changed code and volatility of the requirements for the change task correlated with change effort. The analysis of the qualitative interviews pointed to two important, underlying cost drivers: Difficulties in comprehending dispersed code and difficulties in anticipating side effects of changes. This study demonstrates a novel method for combining qualitative and quantitative analysis to assess cost drivers of software evolution. Given our findings, we propose improvements to practices and development tools to manage and reduce the costs.     

Generating software test data by evolution

This paper discusses the use of genetic algorithms (GAs) for automatic software test data generation. This research extends previous work on dynamic test data generation where the problem of test data generation is reduced to one of minimizing a function. In our work, the function is minimized by using one of two genetic algorithms in place of the local minimization techniques used in earlier research. We describe the implementation of our GA-based system and examine the effectiveness of this approach on a number of programs, one of which is significantly larger than those for which results have previously been reported in the literature. We also examine the effect of program complexity on the test data generation problem by executing our system on a number of synthetic programs that have varying complexities     

Mining most frequently changing component in evolving graphs

Many applications see huge demands of finding important changing areas in evolving graphs. In this paper, given a series of snapshots of an evolving graph, we model and develop algorithms to capture the most frequently changing component (MFCC). Motivated by the intuition that the MFCC should capture the densest area of changes in an evolving graph, we propose a simple yet effective model. Using only one parameter, users can control tradeoffs between the “density” of the changes and the size of the detected area. We verify the effectiveness and the efficiency of our approach on real data sets systematically.     

Visualizing protected variations in evolving software designs

Identifying and tracking evolving software structures at a design level is a challenging task. Although there are ways to visualize this information statically, there is a need for methods that help analyzing the evolution of software design elements. In this paper, we present a new visual approach to identify variability zones in software designs and explore how they evolve over time. To verify the usefulness of our approach, we did a user study in which participants had to browse software histories and find visual patterns. Most participants were able to find interesting observations and found our approach intuitive and useful. We present a number of design aspects that were observed by participants and the authors using our IHVis tool on four open-source projects.     

Relating evolving business rules to software design

In order to remain useful, it is important for software to evolve according to the changes in its business environment. Business rules, which can be used to represent both user requirements and conditions to which the system should conform, are considered as the most volatile part in today's software applications. Their changes bring high impact on both the business processes and the software itself. In this paper, we present an approach that considers business rules as an integral part of a software system and its evolution. The approach transcends the areas of requirements specification and software design. We develop the Business Rule Model to capture and specify business rules, and the Link Model to relate business rules to the metamodel level of software design elements. The aim is to improve requirements traceability in software design, as well as minimizing the efforts of software changes due to the changes of business rules. The approach is demonstrated using examples from an industrial application.     

Modeling concurrent software

The author proposes a disciplined multitasking method, entity-life modeling, which may provide a more direct and efficient approach to concurrent computing. He then shows how this method could apply to an automated control system. He discusses an example of a flexible manufacturing system     

基于压缩全文索引的演变图查询

演变图中含有大量的时间和空间信息,其中某些空间信息随着时间的推移表现出相似的演变规律。给出了一种演变图查询模型,可以挖掘出在相同时间范围内具有相同变化规律的演变子图。但是演变图的规模往往是巨大的,当需要对其进行多次查询时,每次遍历整个演变图将带来非常高的查询代价,而现有的基于枚举的哈希索引算法又使得预处理过程拥有相当大的时间和空间开销,为了减少对大规模演变图的预处理代价,将压缩的全文索引技术应用于演变图,它基于涡轮转换和后缀数组。在构建后缀数组时,给出了两种不同的线性算法,确保了预处理过程的稳定性。通过在Facebook、Enron邮件系统以及模拟数据集上的实验,评估了该算法的可行性、效率以及可扩展性。     

Predicting failure-proneness in an evolving software product line

ContextPrevious work by researchers on 3 years of early data for an Eclipse product has identified some predictors of failure-prone files that work well. Eclipse has also been used previously by researchers to study characteristics of product line software.ObjectiveThe work reported here investigates whether classification-based prediction of failure-prone files improves as the product line evolves.MethodThis investigation first repeats, to the extent possible, the previous study and then extends it by including four more recent years of data, comparing the prominent predictors with the previous results. The research then looks at the data for three additional Eclipse products as they evolve over time. The analysis compares results from three different types of datasets with alternative data collection and prediction periods.ResultsOur experiments with a variety of learners show that the difference between the performance of J48, used in this work, and the other top learners is not statistically significant. Furthermore, new results show that the effectiveness of classification significantly depends on the data collection period and prediction period. The study identifies change metrics that are prominent predictors across all four releases of all four products in the product line for the three different types of datasets. From the product line perspective, prediction of failure-prone files for the four products studied in the Eclipse product line shows statistically significant improvement in accuracy but not in recall across releases.ConclusionAs the product line matures, the learner performance improves significantly for two of the three datasets, but not for prediction of post-release failure-prone files using only pre-release change data. This suggests that it may be difficult to detect failure-prone files in the evolving product line. At least in part, this may be due to the continuous change, even for commonalities and high-reuse variation components, which we previously have shown to exist.     

Verification of evolving software via component substitutability analysis

This paper presents an automated and compositional procedure to solve the substitutability problem in the context of evolving software systems. Our solution contributes two techniques for checking correctness of software upgrades: (1) a technique based on simultaneous use of over-and under-approximations obtained via existential and universal abstractions; (2) a dynamic assume-guarantee reasoning algorithm—previously generated component assumptions are reused and altered on-the-fly to prove or disprove the global safety properties on the updated system. When upgrades are found to be non-substitutable, our solution generates constructive feedback to developers showing how to improve the components. The substitutability approach has been implemented and validated in the ComFoRT reasoning framework, and we report encouraging results on an industrial benchmark. This is an extended version of a paper, Dynamic Component Substitutability Analysis, published in the Proceedings of the Formal Methods 2005 Conference, Lecture Notes in Computer Science, vol. 3582, by the same authors. This research was sponsored by the National Science Foundation under grant nos. CNS-0411152, CCF-0429120, CCR-0121547, and CCR-0098072, the Semiconductor Research Corporation under grant no. TJ-1366, the US Army Research Office under grant no. DAAD19-01-1-0485, the Office of Naval Research under grant no. N00014-01-1-0796, the ICAST project and the Predictable Assembly from Certifiable Components (PACC) initiative at the Software Engineering Institute, Carnegie Mellon University. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of any sponsoring institution, the US government or any other entity.     

Unique identification of elements in evolving software models

Evolving models are often managed in file-based software configuration management systems. This causes the identification problem: if the model elements are not assigned with globally unique identifiers, we cannot identify them over time. However, if such identifiers would be given, they can be misleading because the elements to which they are assigned might change completely. As a consequence, evolution becomes incomprehensible, partial transformation is hampered, and sufficient management of inter-model relationships (e.g. traceability links) is impeded. This article presents an approach to identify model elements or even complete model fragments over time. It establishes a fine-grained history representation to describe model evolution. The representation contains identification links between the elements of different model revisions allowing us to identify elements of a given revision in other revisions or variants of the model. Due to the explicit expression of model evolution, it further enables the capturing of changes that have been applied to the fine-grained elements inside a model.     

RGPS支持的面向方面网络式软件演化方法

为了改进现有的面向方面网络式软件演化方法中切入点(Pointcuts)位置定义不够清晰和切入点织入操作性不强的问题,提出一种利用角色-目标-流程-服务(RGPS)的流程元模型改进面向方面的网络式软件演化的方法.在该方法中,使用RGPS的流程元模型定义流程,采用元模型中的控制结构定义方面切入点的位置,因为方面和流程采用一致的定义方式,所以方面切入点位置定义精确且能够无缝织入原流程.对流程演化过程给出了形式化的定义,并阐述了流程演化时方面织入的各种方式.最后利用一个实例说明了演化方法的方面织入过程.     

Modeling consistency of spatio-temporal graphs

This work introduces a graph-based approach to the representation of evolving entities in space and time. At an abstract level, the model makes a distinction between filiation and spatial relationships between entities, while at the database level, it stores derivation relationships and determines continuation and spatial relationships in time. An extended relational database specification implements the spatio-temporal graph model. A formal language models integrity constraints that are inherent to the model and those that are semantic and application dependent. The satisfiability of these constraints is studied and an algorithm for checking consistency of spatio-temporal graph is provided. An experimental evaluation shows the potential of the model.     

EvolveKG: a general framework to learn evolving knowledge graphs

A great many practical applications have observed knowledge evolution, i.e., continuous born of new knowledge, with its formation influenced by the structure of historical knowledge. This observation gives rise to evolving knowledge graphs whose structure temporally grows over time. However, both the modal characterization and the algorithmic implementation of evolving knowledge graphs remain unexplored. To this end, we propose EvolveKG – a general framework that enables algorithms in the static knowledge graphs to learn the evolving ones. EvolveKG quantifies the influence of a historical fact on a current one, called the effectiveness of the fact, and makes knowledge prediction by leveraging all the cross-time knowledge interaction. The novelty of EvolveKG lies in Derivative Graph – a weighted snapshot of evolution at a certain time. Particularly, each weight quantifies knowledge effectiveness through a temporarily decaying function of consistency and attenuation, two proposed factors depicting whether or not the effectiveness of a fact fades away with time. Besides, considering both knowledge creation and loss, we obtain higher prediction accuracy when the effectiveness of all the facts increases with time or remains unchanged. Under four real datasets, the superiority of EvolveKG is confirmed in prediction accuracy.