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.

Apportioning: a technique for efficient reachability analysis ofconcurrent object-oriented programs

The object-oriented paradigm in software engineering provides support for the construction of modular and reusable program components and is attractive for the design of large and complex distributed systems. Reachability analysis is an important and well-known tool for static analysis of critical properties in concurrent programs, such as deadlock freedom. It involves the systematic enumeration of all possible global states of program execution and provides the same level of assurance for properties of the synchronization structure in concurrent programs, such as formal verification. However, direct application of traditional reachability analysis to concurrent object-oriented programs has many problems, such as incomplete analysis for reusable classes (not safe) and increased computational complexity (not efficient). We propose a novel technique called apportioning, for safe and efficient reachability analysis of concurrent object-oriented programs, that is based upon a simple but powerful idea of classification of program analysis points as local (having influence within a class) and global (having possible influence outside a class). We have developed a number of apportioning-based algorithms, having different degrees of safety and efficiency. We present the details of one of these algorithms, formally show its safety for an appropriate class of programs, and present experimental results to demonstrate its efficiency for various examples     

A precompiler written in Spitbol applied to programs to analyze nuclear data

For an interactive data acquisition and analysis system for nuclear physics experiments a precompiler is provided to expand system specific macros in user written analysis programs. It is written with help of the string processing language SPITBOL and generates PL/I or PL-11 code. It is shown that SPITBOL is a suitable precompiler language for this kind of medium size precompile problems.     

A graph-based generic type system for object-oriented programs

We present a graph-basedmodel of a generic type system for an OO language. The type system supports the features of recursive types, generics and interfaces, which are commonly found in modern OO languages such as Java. In the classical graph theory, we define type graphs, instantiation graphs and conjunction graphs that naturally illustrate the relations among types, generics and interfaces within complex OO programs. The model employs a combination of nominal and anonymous nodes to represent respectively types that are identified by names and structures, and defines graph-based relations and operations on types including equivalence, subtyping, conjunction and instantiation. Algorithms based on the graph structures are designed for the implementation of the type system. We believe that this type system is important for the development of a graph-based logical foundation of a formal method for verification of and reasoning about OO programs.     

A shared-variable concurrency analysis of multi-threaded object-oriented programs

In this paper a proof outline logic is introduced for the partial correctness of multi-threaded object-oriented programs like in Java. The main contribution is a generalization of the Owicki& Gries proof method for shared-variable concurrency to dynamic thread creation. This paper also provides a formal justification of this generalization in terms of soundness and completeness proofs.     

Verification of object-oriented programs: A transformational approach

We show that verification of object-oriented programs by means of the assertional method can be achieved in a simple way by exploiting a syntax-directed transformation from object-oriented programs to recursive programs. This transformation suggests natural proofs rules and its correctness helps us to establish soundness and relative completeness of the proposed proof system. One of the difficulties is how to properly deal in the assertion language with the instance variables and aliasing. The discussed programming language supports arrays, instance variables, failures and recursive methods with parameters. We also explain how the transformational approach can be extended to deal with other features of object-oriented programming, like classes, inheritance, subtyping and dynamic binding.     

Support for maintaining object-oriented programs

It is explained how inheritance and dynamic binding make object-oriented programs difficult to maintain, and a concrete example of the problems that arise is given. It is shown that the difficulty lies in the fact that conventional tools are poorly suited for work with object-oriented languages, and it is argued that semantics-based tools are essential for effective maintenance of object-oriented programs. A system developed for working with C++ programs is described. It comprises a relational database system for information about programs and an interactive database interface integrated with a text editor. The authors describe the system architecture, detail the database relations, provide informal evidence on the system's effectiveness, and compare it to other research with similar goals     

An object-oriented approach to formally analyze the UML 2.0 activity partitions

Nowadays, UML is the de-facto standard for object-oriented analysis and design. Unfortunately, the deficiency of its dynamic semantics limits the possibility of early specification analysis. UML 2.0 comes to precise and complete this semantics but it remains informal and still lacks tools for automatic validation. The main purpose of this study is to automate the formal validation, according a value-oriented approach, of the behavior of systems expressed in UML. The marriage of Petri nets with temporal logics seems a suitable formalism for translating and then validating UML state-based models. The contributions of the paper are threefold. We first, consider how UML 2.0 activity partitions can be transformed into Object Petri Nets to formalize the object dynamics, in an object-oriented context. Second, we develop an approach based on the object and sequence diagram information to initialize the derived Petri nets in terms of objects and events. Finally, to thoroughly verify if the UML model meets the system required properties, we suggest to use the OCL invariants exploiting their association end constructs. The verification is performed on a predicate/transition net explored by model checking. A case study is given to illustrate this methodology throughout the paper.     

Improving the quality of object-oriented programs

Object-oriented languages originated in the late '60s and entered widespread industrial use in the early '90s. With this technology's advent came the hope and belief that life from a programming perspective would generally improve. We believed that these languages would foster reuse and, consequently, a reduction in the quantity of code written. We also believed that inheritance, an object-oriented language feature, would result in less testing effort, although D. Perry and G. Kaiser (1990) dispelled this notion. So, if we use object-oriented technology, what should we expect in terms of quality? What can we do to increase our chances of producing highly reliable software? This paper presents four ideas that will improve these chances regardless of the object-oriented language used     

Cost analysis of object-oriented bytecode programs

Cost analysis statically approximates the cost of programs in terms of their input data size. This paper presents, to the best of our knowledge, the first approach to the automatic cost analysis of object-oriented bytecode programs. In languages such as Java and C#, analyzing bytecode has a much wider application area than analyzing source code since the latter is often not available. Cost analysis in this context has to consider, among others, dynamic dispatch, jumps, the operand stack, and the heap. Our method takes a bytecode program and a cost model specifying the resource of interest, and generates cost relations which approximate the execution cost of the program with respect to such resource. We report on COSTA, an implementation for Java bytecode which can obtain upper bounds on cost for a large class of programs and complexity classes. Our basic techniques can be directly applied to infer cost relations for other object-oriented imperative languages, not necessarily in bytecode form.     

A heuristic-based regression test case prioritization approach for object-oriented programs

We propose a novel regression test case prioritization technique based on an analysis of a dependence model for object-oriented programs. We first construct an intermediate dependence model of a program from its source code. When the program is modified, the model is updated to reflect the changes. Our constructed model represents control and data dependencies as well as information pertaining to various types of dependencies arising from object relations such as association, inheritance and aggregation. We determine the affected nodes in the model by constructing the union of the forward slices corresponding to each changed model element. The test cases covering one or more affected nodes are selected for regression testing. The test cases in the selected regression test suite are then prioritized based on their weights and the weight of a test case is determined by assigning weights to the affected nodes. Our experimental results indicate that our approach on an average achieves an increase in the APFD metric value by 9.01 % as compared to a related approach.     

面向对象软件度量的3D可视化方法

软件可视化是指利用印刷、图形、动画以及其它图形或摄影技术提高人们对软件的理解的技术.度量可视化是软件可视化研究的分支之一,它是把度量数据与可视化的图形结合来表示软件的结构.现有的度量可视化方法存在的不足是所能表示的度量指标等属性太少,表示出来的信息不够全面.为了表示更多的属性信息,提出了一种新的面向对象软件度量的3D可视化方法,利用组合图形表示软件实体(如类、方法等),使得所表示的属性数量加倍,从而更有利于对软件的理解和分析.开发出可视化工具M3DTool证明了该方法的有效性.     

Modular specification and verification of object-oriented programs

A method for modular specification and verification using the ideas of subtype and normal type is presented. The method corresponds to informal techniques used by object-oriented programmers. The key idea is that objects of a subtype must behave like objects of that type's supertypes. An example program is used to show the reasoning problems that supertype abstraction may cause and how the method resolves them. Subtype polymorphism is addressed, and specification and verification update is discussed. A set of syntactic and semantic constraints on subtype relationships, which formalize the intuition that each object of a subtype must behave like some object of each of its supertypes, is examined. These constraints are the key to the soundness of the method. To state them precisely, a formal model of abstract type specifications is used     

Computing dynamic slices of concurrent object-oriented programs

We propose a novel dynamic program slicing technique for concurrent object-oriented programs. Our technique uses a Concurrent System Dependence Graph (CSDG) as the intermediate program representation. We mark and unmark the edges in the CSDG appropriately as and when the dependencies arise and cease during run-time. We mark an edge when its associated dependence exists and unmark an edge when the dependence ceases to exist. Our approach eliminates the use of trace files. Another advantage of our approach is that when a request for a slice is made, it is already available. This appreciably reduces the response time of slicing commands.     

Modeling and visualizing object-oriented programs with Codecharts

Software design, development and evolution commonly require programmers to model design decisions, visualize implemented programs, and detect conflicts between design and implementation. However, common design notations rarely reconcile theoretical concerns for rigor and minimality with the practical concerns for abstraction, scalability and automated verifiability. The language of Codecharts was designed to overcome these challenges by narrowing its scope to visual specifications that articulate automatically-verifiable statements about the structure and organization of object-oriented programs. The tokens in its visual vocabulary stand for the building-blocks of object-oriented design, such as inheritance class hierarchies, sets of dynamically-bound methods, and their correlations. The formalism was tailored for those pragmatic concerns which arise from modeling class libraries and design patterns, and for visualizing programs of any size at any level of abstraction. We describe design verification, a process of proving or refuting that a Java program (i.e. its native code) conforms to the Codechart specifying it. We also describe a toolkit which supports modeling and visualization with Codecharts, as well as a fully-automated design verification tool. We conclude with empirical results which suggest gains in both speed and accuracy when using Codecharts in software design, development and evolution.     

Semantic-based locking technique in object-oriented databases

This paper presents a locking-based concurrency control dealing with three important issues in object-oriented databases: semantics of methods, nested method invocation and referentially shared object. In the proposed scheme, locks are required for the execution of methods instead of atomic operations. This can reduce the locking overhead and deadlocks due to lock escalation. Also, a way of automating commutativity of methods is provided. In addition, concurrency is increased further by use of run-time information. A performance study is conducted by means of simulation using 007 benchmark. Through the simulation, the proposed technique is then compared with the two existing techniques. The performance studies show that the proposed scheme is superior to existing works.     

基于ISDG的面向对象程序分片技术研究

程序分片是一种有效的程序分析技术,它能根据给定的分片准则从源程序中提取出所需部分进行分析,如进行程序调试、测试、程序重构分析等。程序分片技术在结构化程序中已有较广泛的应用,但对于面向对象语言程序,其研究与应用还存在一些待解决的问题。针对面向对象语言程序,提出了一种改进后的系统依赖图：ISDG,用来更好地表示面向对象程序中的依赖关系,从而解决了对象类型参数和属性的表示问题。基于ISDG模型,提出了一种新的面向对象语言程序的分片准则,以度相应的分片算法。     

Developing parallel object-oriented programs in the framework of VDM

After surveying the rely-guarantee and some related approaches to extending VDM to develop parallel programs, two main problems are found. One problem is that all explorations of parallelism are done in the stage of operation decomposition or afterwards so that the degree of parallelism is restricted. Another problem is that the atomicity is fixed at one level and the development complexity can not be controlled effectively because there is no natural means to let the level of granularity be under flexible control of the designer. In order to solve these two problems, we introduce a new concept — data decomposition which is based on the ideas of model split, modularisation and operation decomposition, and combine it with VDM to form a more general formal development method DD-VDM, in which some kind of operation decompositions, i.e., operation split can be done before some data reifications. Then a nested parallel object-oriented structure is proposed. Combining these ideas into the unified framework, this paper presents a hierarchical object-oriented design methodology in which two kinds of parallelism, that is, internal parallelism and service parallelism, can be exploited gradually and a kind of virtual atomicity is provided.This research is partially supported by China's National Foundation for Excellent Young Scientists.