JDiff: A differencing technique and tool for object-oriented programs

During software evolution, information about changes between different versions of a program is useful for a number of software engineering tasks. For example, configuration-management systems can use change information to assess possible conflicts among updates from different users. For another example, in regression testing, knowledge about which parts of a program are unchanged can help in identifying test cases that need not be rerun. For many of these tasks, a purely syntactic differencing may not provide enough information for the task to be performed effectively. This problem is especially relevant in the case of object-oriented software, for which a syntactic change can have subtle and unforeseen effects. In this paper, we present a technique for comparing object-oriented programs that identifies both differences and correspondences between two versions of a program. The technique is based on a representation that handles object-oriented features and, thus, can capture the behavior of object-oriented programs. We also present JDiff, a tool that implements the technique for Java programs. Finally, we present the results of four empirical studies, performed on many versions of two medium-sized subjects, that show the efficiency and effectiveness of the technique when used on real programs.

Exploiting the empirical characteristics of program dependences for improved forward computation of dynamic slices

Forward computing algorithms for dynamic slicing operate in tandem with program execution and generally do not require a previously stored execution trace, which make them suitable for interactive debugging and online analysis of long running programs. Both the time and space requirements of such algorithms are generally high due to the fact that they compute and maintain in memory the dynamic slices associated with all variables defined during execution. In this paper we empirically identify several characteristics of program dependences that we exploit to develop a memoization-based forward computing dynamic slicing algorithm whose runtime cost is better than that of any existing algorithm in its class. We also conduct an empirical comparative study contrasting the performance of our new algorithm to the performance of four other algorithms. One is a well known basic algorithm, and the remaining three, use reduced ordered binary decision diagrams (roBDDs) to maintain dynamic slices. Our results indicate that the new memoization-based algorithm is: (1) considerably more time and space efficient than the basic algorithm and one of the roBDD-based algorithms designed to be suitable for online analysis; and (2) comparable in terms of time efficiency but consistently more space efficient than the remaining two roBDD-based algorithms.

TOWARDS PARALLEL PROGRAMMING BY TRANSFORMATION: THE FAN SKELETON FRAMEWORK*

A Functional Abstract Notation (FAN) is proposed for the specification and design of parallel algorithms by means of skeletons - high-level patterns with parallel semantics. The main weakness of the current programming systems based on skeletons ii that the user is still responsible for finding the most appropriate skeleton composition for a given application and a given parallel architecture

We describe a transformational framework for the development of skeletal programs which is aimed at filling this gap. The framework makes use of transformation rules which are semantic equivalences among skeleton compositions. For a given problem, an initial, possibly inefficient skeleton specification is refined by applying a sequence of transformations. Transformations are guided by a set of performance prediction models which forecast the behavior of each skeleton and the performance benefits of different rules. The design process is supported by a graphical tool which locates applicable transformations and provides performance estimates, thereby helping the programmer in navigating through the program refinement space. We give an overview of the FAN framework and exemplify its use with performance-directed program derivations for simple case studies. Our experience can be viewed as a first feasibility study of methods and tools for transformational, performance-directed parallel programming using skeletons.     

A unix tool for managing reusable software components

Sloth is a simple Unix-based tool for creating and maintaining large C programs built from reusable ‘modules’. Sloth is a collection of UNIX shell commands for creating and editing modules, and for producing executables by linking compiled code from the modules comprising a program. Sloth in a sense extends C by providing module facilities similar to those built in to newer languages such as Modula-II. The Sloth ‘extensions’, however, are at the shell level only. No changes are required in C itself; in fact, the Sloth commands invoke the standard Unix C compiler. A Sloth module contains a set of C procedures and local declarations, a set of global definitions and variable declarations, an initialization routine and an ‘import’ list of other modules containing declarations referred to, but not defined by, the module in question. The Sloth link command has one argument, the name of a ‘root’ directory. The link command automatically identifies all those modules imported directly or indirectly by the root module, checks that the object code for each module is up-to-date and recompiles where necessary. It then creates a main program in which the various initialization routines are executed in the correct order (most primitive first), compiles it and links it with all the object files and produces an executable program. Individual modules can be compiled without any knowledge of the application that uses, directly or indirectly, the module in question. Two applications that both use a collection of modules can therefore share the object code for these modules. The use and implementation of Sloth are presented, as are the experience in using it, programming techniques developed to take full advantage of its facilities, as well as several extensions, either completed or planned.     

A System for Generating Reverse Engineering Tools: A Case Study of Software Modularisation

The paper presents a case study in the development of software modularisation tools. The tools are produced by using a system for developing code analysers that uses a database to store both a no-loss fine-grained intermediate representation and the analyses' results. The analysers are automatically generated from a high-level specification of the desired analyses expressed in a domain-oriented language. We use a program intermediate representation, called F(p), as the user-visible data base conceptual model. Analysers are specified in a declarative language, called F(p) – , which allows the specification of an analysis in the form of a traversal of an algebraic expression, with accesses to, and stores of, the database information the algebraic expression indexes. A foreign language interface allows the analysers to be embedded into C programs. This is useful, for example, to implement the user interface of an analyser or to facilitate interoperation of the generated analysers with pre-existing tools.     

The software model checker Blast

Blast is an automatic verification tool for checking temporal safety properties of C programs. Given a C program and a temporal safety property, Blast either statically proves that the program satisfies the safety property, or provides an execution path that exhibits a violation of the property (or, since the problem is undecidable, does not terminate). Blast constructs, explores, and refines abstractions of the program state space based on lazy predicate abstraction and interpolation-based predicate discovery. This paper gives an introduction to Blast and demonstrates, through two case studies, how it can be applied to program verification and test-case generation. In the first case study, we use Blast to statically prove memory safety for C programs. We use CCured, a type-based memory-safety analyzer, to annotate a program with run-time assertions that check for safe memory operations. Then, we use Blast to remove as many of the run-time checks as possible (by proving that these checks never fail), and to generate execution scenarios that violate the assertions for the remaining run-time checks. In our second case study, we use Blast to automatically generate test suites that guarantee full coverage with respect to a given predicate. Given a C program and a target predicate p, Blast determines the program locations q for which there exists a program execution that reaches q with p true, and automatically generates a set of test vectors that cause such executions. Our experiments show that Blast can provide automated, precise, and scalable analysis for C programs.     

A higher-order removal method

A major attraction of functional languages is their support for higher-order functions. This facility increases the expressive power of functional languages by allowing concise and reusable programs to be written. However, higher-order functions are more expensive to execute and to analyse for optimisations.To reduce the performance penalties of using higher-order functions, this paper proposes two transformation algorithms which could automatically removemost higher-order functions from functional programs. The first algorithm uses aneta-expansion technique to eliminate expressions which return function-type results. The second algorithm uses afunction specialisation technique to eliminate expressions with function-type arguments. Together, they remove higher-order functions by transforming each higher-order program to an equivalent first-order (or lower-order) program. We shall prove that the two algorithms areterminating (when applied to well-typed programs) and alsototally-correct (preserving non-strict semantics).A preliminary version of this paper appeared in the Proceedings of 15th Australian Computer Science Conference, Hobart, Tasmania, January 1992.     

Approximate algorithms for partitioning problems

We consider the problem of optimally assigning the modules of a parallel/pipelined program over the processors of a multiple processor system under certain restrictions on the interconnection structure of the program as well as the multiple computer system. We show that for a variety of such problems, it is possible to find if a partition of the modular program exists in which the load on any processor is whithin a certain bound. This method when combined with a binary search over a fixed range, provides an optimal solution to the partitioning problem.The specific problems we consider are partitioning of (1) a chain structured parallel program over a chain-like computer system, (2) multiple chain-like programs over a host-satellite system, and (3) a tree structured parallel program over a host-satellite system.For a problem withN modules andM processors, the complexity of our algorithm is no worse thanO(Mlog(N)log(W _T/)), whereW _T is the cost of assigning all modules to one processors, and the desired accuracy. This algorithm provides an improvement over the recently developed best known algorithm that runs inO(MNlog(N)) time.This Research was supported by a grant from the Division of Research Extension and Advisory Services, University of Engineering and Technology Lahore, Pakistan. Further support was provided by NASA Contracts NAS1-17070 and NAS1-18107 while the author was resident at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, Virginia, USA.     

Theories, tools and research methods in program comprehension: past, present and future

Program comprehension research can be characterized by both the theories that provide rich explanations about how programmers understand software, as well as the tools that are used to assist in comprehension tasks. In this paper, I review some of the key cognitive theories of program comprehension that have emerged over the past thirty years. Using these theories as a canvas, I then explore how tools that are commonly used today have evolved to support program comprehension. Specifically, I discuss how the theories and tools are related and reflect on the research methods that were used to construct the theories and evaluate the tools. The reviewed theories and tools are distinguished according to human characteristics, program characteristics, and the context for the various comprehension tasks. Finally, I predict how these characteristics will change in the future and speculate on how a number of important research directions could lead to improvements in program comprehension tool development and research methods. Dr. Margaret-Anne Storey is an associate professor of computer science at the University of Victoria, a Visiting Scientist at the IBM Centre for Advanced Studies in Toronto and a Canada Research Chair in Human Computer Interaction for Software Engineering. Her research passion is to understand how technology can help people explore, understand and share complex information and knowledge. She applies and evaluates techniques from knowledge engineering and visual interface design to applications such as reverse engineering of legacy software, medical ontology development, digital image management and learning in web-based environments. She is also an educator and enjoys the challenges of teaching programming to novice programmers.     

A unifying theory of control dependence and its application to arbitrary program structures

There are several similar, but not identical, definitions of control dependence in the literature. These definitions are given in terms of control flow graphs which have had extra restrictions imposed (for example, end-reachability).We define two new generalisations of non-termination insensitive and non-termination sensitive control dependence called weak and strong control-closure. These are defined for all finite directed graphs, not just control flow graphs and are hence allow control dependence to be applied to a wider class of program structures than before.We investigate all previous forms of control dependence in the literature and prove that, for the restricted graphs for which each is defined, vertex sets are closed under each if and only if they are either weakly or strongly control-closed. Low polynomial-time algorithms for producing minimal weakly and strongly control-closed sets over generalised control flow graphs are given.This paper is the first to define an underlying semantics for control dependence: we define two relations between graphs called weak and strong projections, and prove that the graph induced by a set of vertices is a weak/strong projection of the original if and only if the set is weakly/strongly control-closed. Thus, all previous forms of control dependence also satisfy our semantics. Weak and strong projections, therefore, precisely capture the essence of control dependence in our generalisations and all the previous, more restricted forms. More fundamentally, these semantics can be thought of as correctness criteria for future definitions of control dependence.     

Implementing sequentially consistent programs on processor consistent platforms

Designers of distributed algorithms typically assume strong memory consistency guarantees, but system implementations provide weaker guarantees for better performance and scalability. This motivates the study of how to implement programs designed for sequential consistency on platforms with weaker consistency models. Typically, such implementations are impossible using only read and write operations to shared variables. One variant of processor consistency originally proposed by Goodman and called here PC-G is an exception because it provides just enough consistency to implement mutual exclusion using only reads and writes. This paper investigates the existence of compilers to convert arbitrary programs that use shared read/write variables with sequentially consistent memory semantics, to programs that use read/write variables with PC-G consistency semantics. We first provide a simple program transformation, and prove that it correctly compiles any 2-process program to a PC-G memory system, while preserving wait-freedom. We next prove that even a substantial generalization of this transformation cannot be a compiler for even a very restricted class of 3-process programs. Even though our program transformation is not a general compiler for three or more processes, it does correctly transform some specific n-process programs. In particular, for the special case of the (necessarily randomized) Test&Set algorithm of Tromp and Vitanyi, our transformation extends to any number of processes, thus providing the first algorithm for expected wait-free Test&Set on any weak memory system, using only read/write variables.     

软件相似性分析算法的研究综述

软件相似性分析算法是为了更好地保护软件的知识产权。此算法并不会加固程序以增加其抵御攻击的能力,而是对两个或两个以上的程序进行比较,判断是否相互包含。该算法有重复代码筛选、软件作者鉴别、软件“胎记”和剽窃检测,它们最本质的操作就是直接处理程序的源码或二进制可执行文件,将其转换成一种更易于处理的表示形式,从而确定两个程序(或者程序片段)之间的相似度,或是其中一个(部分或全部)是否包含了另一个。最后总结出此类算法的通用格式,并对每种算法作出相应的分析综述表。     

Coherent clusters in source code

This paper presents the results of a large scale empirical study of coherent dependence clusters. All statements in a coherent dependence cluster depend upon the same set of statements and affect the same set of statements; a coherent cluster's statements have ‘coherent’ shared backward and forward dependence. We introduce an approximation to efficiently locate coherent clusters and show that it has a minimum precision of 97.76%. Our empirical study also finds that, despite their tight coherence constraints, coherent dependence clusters are in abundance: 23 of the 30 programs studied have coherent clusters that contain at least 10% of the whole program. Studying patterns of clustering in these programs reveals that most programs contain multiple substantial coherent clusters. A series of subsequent case studies uncover that all clusters of significant size map to a logical functionality and correspond to a program structure. For example, we show that for the program acct, the top five coherent clusters all map to specific, yet otherwise non-obvious, functionality. Cluster visualization also brings out subtle deficiencies in program structure and identifies potential refactoring candidates. A study of inter-cluster dependence is used to highlight how coherent clusters are connected to each other, revealing higher-level structures, which can be used in reverse engineering. Finally, studies are presented to illustrate how clusters are not correlated with program faults as they remain stable during most system evolution.     

Neural TV program recommendation with label and user dual attention

TV program recommendation is very important for users to find interesting TV programs and avoid confusing users with a lot of information. Currently, they are basically traditional collaborative filtering algorithms, which only recommend through the interactive data between users and programs ignoring the important value of some auxiliary information. In addition, the neural network method based on attention mechanism can well capture the relationship between program labels to obtain accurate program and user representations. In this paper, we propose a neural TV program recommendation with label and user dual attention (NPR-LUA), which can focus on auxiliary information in program and user modules. In the program encoder module, we learn the auxiliary information from program labels through neural networks and word attention to identify important program labels. In the user encoder module, we learn the user representation through the programs that the user watches and use personalized attention mechanism to distinguish the importance of programs for each user. Experiments on real data sets show that our method can effectively improve the effectiveness of TV program recommendations than other existing models.

     

The uniform memory hierarchy model of computation

TheUniform Memory Hierarchy (UMH) model introduced in this paper captures performance-relevant aspects of the hierarchical nature of computer memory. It is used to quantify architectural requirements of several algorithms and to ratify the faster speeds achieved by tuned implementations that use improved data-movement strategies.A sequential computer's memory is modeled as a sequence M ₀,M ₁,... of increasingly large memory modules. Computation takes place inM ₀. Thus,M ₀ might model a computer's central processor, whileM ₁ might be cache memory,M ₂ main memory, and so on. For each moduleM _u, a busB _u connects it with the next larger module M_u+1. All buses may be active simultaneously. Data is transferred along a bus in fixed-sized blocks. The size of these blocks, the time required to transfer a block, and the number of blocks that fit in a module are larger for modules farther from the processor. The UMH model is parametrized by the rate at which the blocksizes increase and by the ratio of the blockcount to the blocksize. A third parameter, the transfer-cost (inverse bandwidth) function, determines the time to transfer blocks at the different levels of the hierarchy.UMH analysis refines traditional methods of algorithm analysis by including the cost of data movement throughout the memory hierarchy. Thecommunication efficiency of a program is a ratio measuring the portion of UMH running time during which M₀ is active. An algorithm that can be implemented by a program whose communication efficiency is nonzero in the limit is said to becommunication- efficient. The communication efficiency of a program depends on the parameters of the UMH model, most importantly on the transfer-cost function. Athreshold function separates those transfer-cost functions for which an algorithm is communication-efficient from those that are too costly. Threshold functions for matrix transpose, standard matrix multiplication, and Fast Fourier Transform algorithms are established by exhibiting communication-efficient programs at the threshold and showing that more expensive transfer-cost functions are too costly.A parallel computer can be modeled as a tree of memory modules with computation occurring at the leaves. Threshold functions are established for multiplication ofN×N matrices using up to N² processors in a tree with constant branching factor.     

An analytical study of strategy-oriented restructuring algorithms

Considerable experimental evidence has been accumulated showing that the performance of programs in virtual memory environments can be significantly improved by restructuring the programs, i.e., by modifying their block-to-page or block-to-segment mapping. This evidence also points out that the so-called strategy-oriented algorithms, which base their decisions on the knowledge of the memory management strategy under which the program will run, are more efficient than those algorithms which do not take this strategy into account.We present here some theoretical arguments to explain why strategy-oriented algorithms perform better than other program restructuring algorithms and determine the conditions under with these algorithms are optimum. In particular, we prove that the algorithms oriented towards the working set or sampled working set policy are optimum when applied to programs having no more than two blocks per page, and that, when this restriction is removed, they minimize both upper and lower bounds of the performance index they consider as the figure of merit to be reduced. We also prove that the restructuring algorithms aimed at reducing the page fault rate of programs to be run under such policies as LRU, Global LRU and PFF (the Page Fault Frequency policy) minimize an upper bound of the page fault rate, and we extend some of our results to some non-strategy-oriented algorithms. Throughout the paper, the only assumption about program behavior is that it can be accurately modeled as a stationary discrete-state stochastic process.     

FTSyn: a framework for automatic synthesis of fault-tolerance

In this paper, we present a software framework for adding fault-tolerance to existing finite-state programs. The input to our framework is a fault-intolerant program and a class of faults that perturbs the program. The output of our framework is a fault-tolerant version of the input program. Our framework provides (1) the first automated tool for the synthesis of fault-tolerant distributed programs, and (2) an extensible platform for researchers to develop a repository of heuristics that deal with the complexity of adding fault-tolerance to distributed programs. We also present a set of heuristics for polynomial-time addition of fault-tolerance to distributed programs. We have used this framework for automated synthesis of several fault-tolerant programs including a simplified version of an aircraft altitude switch, token ring, Byzantine agreement, and agreement in the presence of Byzantine and fail-stop faults. These examples illustrate that our framework can be used for synthesizing programs that tolerate different types of faults (process restarts, Byzantine and fail-stop) and programs that are subject to multiple faults (Byzantine and fail-stop) simultaneously. We have found our framework to be highly useful for pedagogical purposes, especially for teaching concepts of fault-tolerance, automatic program transformation, and the effect of heuristics.     

Composition of relational productions for plans and programs

A relational production system (rps) is a mathematical model for information processing in which computer programs and artificial intelligence plans have a common representation. Annth order composition theorem for relational productions is presented which specifies the net effect of a sequence of actions, providing a unified, operational, mathematical solution to the following problems: (1) formation of compound artificial intelligence operators; (2) closed-form representation of loop semantics for plans; (3) composition of program statements; (4) closed-form representation of loop semantics for programs. This leads to a composition-based verification method, in which structured data are treated by the same methods as unstructured data. This approach seems especially promising in the verification of programs with structured data, which the orthodox inductive assertion technique accommodates only after major transfusions of additional theory.     

Resource oriented selection of rule-based classification models: An empirical case study

The amount of resources allocated for software quality improvements is often not enough to achieve the desired software quality. Software quality classification models that yield a risk-based quality estimation of program modules, such as fault-prone (fp) and not fault-prone (nfp), are useful as software quality assurance techniques. Their usefulness is largely dependent on whether enough resources are available for inspecting the fp modules. Since a given development project has its own budget and time limitations, a resource-based software quality improvement seems more appropriate for achieving its quality goals. A classification model should provide quality improvement guidance so as to maximize resource-utilization. We present a procedure for building software quality classification models from the limited resources perspective. The essence of the procedure is the use of our recently proposed Modified Expected Cost of Misclassification (MECM) measure for developing resource-oriented software quality classification models. The measure penalizes a model, in terms of costs of misclassifications, if the model predicts more number of fp modules than the number that can be inspected with the allotted resources. Our analysis is presented in the context of our Rule-Based Classification Modeling (RBCM) technique. An empirical case study of a large-scale software system demonstrates the promising results of using the MECM measure to select an appropriate resource-based rule-based classification model. Taghi M. Khoshgoftaar is a professor of the Department of Computer Science and Engineering, Florida Atlantic University and the Director of the graduate programs and research. His research interests are in software engineering, software metrics, software reliability and quality engineering, computational intelligence applications, computer security, computer performance evaluation, data mining, machine learning, statistical modeling, and intelligent data analysis. He has published more than 300 refereed papers in these areas. He is a member of the IEEE, IEEE Computer Society, and IEEE Reliability Society. He was the general chair of the IEEE International Conference on Tools with Artificial Intelligence 2005. Naeem Seliya is an Assistant Professor of Computer and Information Science at the University of Michigan - Dearborn. He recieved his Ph.D. in Computer Engineering from Florida Atlantic University, Boca Raton, FL, USA in 2005. His research interests include software engineering, data mining and machine learnring, application and data security, bioinformatics and computational intelligence. He is a member of IEEE and ACM.