bluuebunny/crossref_metadata_2025 huggingface dataset:
Software reverse engineering: A case study
Authors: Byrne Eric J.
Published: November 2006

This paper presents lessons learned from an experiment to reverse engineer a program. A reverse engineering process was used as part of a project to develop an Ada implementation of a Fortran program and upgrade the existing documentation. To accomplish this, design information was extracted from the Fortran source code and entered into a software development environment. The extracted design information was used to implement a new version of the program written in Ada. This experiment revealed issues about recovering design information, such as, separating design details from implementation details, dealing with incomplete or erroneous information, traceability of information between implementation and recovered design, and re‐engineering. The reverse engineering process used to recover the design, and the experience gained during the study are reported.
A streams‐based communications subsystem in turing plus for protocol development
Authors: Atwood J. William , Prager Walter
Published: November 2006

The Homogeneous Multiprocessor (HM) has a linear‐array topology, with interprocessor communications achieved by the sharing of memory between nearest neighbours, by adjacent‐processor signalling, and through a high‐speed network (the H‐Network). The operating system nucleus (the HM‐Nucleus) for the HM contains a communications subsystem that provides low‐overhead communications, both for user processes and for the rest of the HM‐Nucleus, using the shared memory, the signalling capability, and the H‐Network.

The design for the communications subsystem provides uniformity of access to the three mechanisms by following the IEEE 802.2/802.3 LLC/MAC specifications. Flexibility of access is achieved by adopting the STREAMS facility from System V UNIX.

A new implementation of STREAMS has been built using Turing Plus for both the programming and the simulation/testing, with no need to access the actual hardware until final test. Completion of the STREAMS framework has made it possible subsequently to code an 802.2 LLC module and an 802.3‐based shared memory driver very quickly.

The STREAMS framework has also made it feasible to cast some algorithms used by other parts of the HM‐Nucleus as protocols, and implement them as STREAMS modules, resulting in considerable simplification in the design process. Since the framework was designed to be completely independent of the host processor, it provides a very general vehicle for protocol development.
Specification and quality assurance of timing constraints in real‐time systems development
Authors: Lien Chih‐Cheng , Yang Chien‐Chiao
Published: November 2006

A representation for specifying the timing constraints of real‐time systems is presented. Four parts of descriptions in a timing constraint: the path of events, timer, types of constraints and quantities of time, are explained. Under the relations among the paths, the hierarchical and network structures can be conducted. The former can be associated with the structure resulting from applying top‐down decomposition in software development. The latter represents the execution dependence of the paths. Based upon these clear and manageable structures, the completeness and consistency of timing constraints specification can be rigorously analysed. Thus, the quality of the specification of timing constraints can be improved during software development. A frame‐like software requirements specification language (FSRSL) is extended to specify timing constraints and the related descriptions in the paper.
A comparison of two paradigms for distributed shared memory
Authors: Levelt Willem G. , Kaashoek M. Frans , Bal Henri E. , Tanenbaum Andrew S.
Published: November 2006

Two paradigms for distributed shared memory on loosely‐coupled computing systems are compared: the shared data‐object model as used in Orca, a programming language specially designed for loosely‐coupled computing systems, and the shared virtual memory model. For both paradigms two systems are described, one using only point‐to‐point messages, the other using broadcasting as well.

The two paradigms and their implementations are described briefly. Their performances are compared on four applications: the travelling‐salesman problem, alpha‐beta search, matrix multiplication and the all‐pairs shortest‐paths problem. Measurements were obtained on a system consisting of 10 MC68020 processors connected by an Ethernet. For comparison purposes, the applications have also been run on a system with physical shared memory. In addition, the paper gives measurements for the first two applications above when remote procedure call is used as the communication mechanism.

The measurements show that both paradigms can be used efficiently for programming large‐grain parallel applications, with significant speed‐ups. The structured shared data‐object model achieves the highest speed‐ups and is easiest to program and to debug.
ALADIN: A scanner generator for incremental programming environments
Authors: Fischer Bernd , Hammer Carsten , Struckmann Werner
Published: November 2006

A large number of scanner generators have been developed. Since they are restricted to the longest‐match rule, they are unsuitable for an incremental environment. We present the ALADIN system, which is able to deliver more than a single token if required. Thus, an ambiguity may be passed to the calling instance. Beyond this ‘incremental feature’, ALADIN is a well‐structured and easy‐to‐understand language. In contrast to existing systems, the desired behaviour of the generated scanners is completely specified explicitly. Thus, the specifications are more abstract than in other systems. A prototype implementation has shown that ALADIN‐generated scanners have about the same performance as those generated by Lex.
Generic abstract interpretation algorithms for Prolog: Two optimization techniques and their experimental evaluation
Authors: Englebert Vincent , Charlier Baudouin Le , Roland Didier , Van Hentenryck Pascal
Published: November 2006

The efficient implementation of generic abstract interpretation algorithms for Prolog is reconsidered after References 1 and 2. Two new optimization techniques are proposed and applied to the original algorithm of Reference 1: dependency on clause prefixes and caching of operations. The first improvement avoids re‐evaluating a clause prefix when no abstract value which it depends on has been updated. The second improvement consists of caching all operations on substitutions and reusing the results whenever possible. The algorithm and the two optimization techniques have been implemented in C (about 8000 lines of code each), tested on a large number of Prolog programs, and compared with the original implementation on an abstract domain containing modes, types and sharing. In conjunction with refinements of the domain algorithms, they produce an average reduction of more than 58 per cent is computation time. Extensive experimental results on the programs are given, including computation times, memory consumption, hit ratios for the caches, the number of operations performed, and the time distribution. As a main result, the improved algorithms exhibit the same efficiency as the specific tools of References 3 and 4, despite the fact that our abstract domain is more sophisticated and accurate. The abstract operations also take 90 per cent of the computation time, indicating that the overhead of the control is very limited. Results on a simpler domain are also given and show that even extremely basic domains can benefit from the optimizations. The general‐purpose character of the optimizations is also discussed.
A unix tool for managing reusable software components
Authors: Plaice John , Wadge William W.
Published: November 2006

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.
On‐line software version change using state transfer between processes
Authors: Gupta Deepak , Jalote Pankaj
Published: November 2006

The usual way of installing a new version of a piece of software is to shut down the running program and then install the new version. This necessitates a sometimes unacceptable delay during which service is denied to the users of the software. An on‐line software replacement system replaces parts of the software while it is in execution, thus eliminating the shutdown. In this paper, we describe a system for on‐line software version change for software written in the C language. When the change is initiated by the user, the system instantiates a new process with the new version of the software, transfers state from the old process to the new one at an appropriate time, and transfers the control to the new process. The user sees a minimal delay in this switchover.
Reverse reachability analysis: A new technique for deadlock detection on communicating finite state machines
Authors: Hung Yung‐Chen , Chen Gen‐Huey
Published: November 2006

The communicating finite state machines can exchange messages over bounded FIFO channels. In this paper, a new technique, called reverse reachability analysis, is proposed to detect deadlocks on the communication between the communicating finite state machines. The technique is based on finding reverse reachable paths starting from possible deadlock states. If a reverse reachable path can reach the initial global state, then deadlock occurs. Otherwise the communication is deadlock‐free. The effectiveness of the technique has been verified by some real protocols such as a specification of X.25 call establishment/clear protocol and Bartlet's alternating bit protocol.
Implementing a graphical multi‐user interface toolkit
Authors: Kohlert Doug , Rodham Ken , Olsen Dan
Published: November 2006

Multi‐user applications allows users in different locations to simultaneously interact with a common interface. Creating multi‐user applications is complicated by issues such as process synchronization, replicated window management, and floor control. As a result, several papers describing toolkits that simplify programming of multi‐user applications have appeared in the literature. This paper discusses several low‐level issues that must be addressed when implementing such a toolkit. Issues relating to replicated window management, supporting heterogeneous hardware environments, and multi‐user event handling are discussed.
The design and implementation of the lout document formatting language
Authors: Kingston Jeffrey H.
Published: November 2006

Lout is a high‐level language for document formatting, whose ease of use has permitted an unprecedented number of advanced features to be added quickly and reliably. This paper charts the evolution of the design and implementation of Lout from conception in mid‐1984 to public release in October 1991. It includes extensive discussions of remaining problems and possible solutions.
Backtalk: A generalized dynamic communication system for DAI
Authors: Sayre Kirk , Gray Michael A.
Published: November 2006

In order to expand the domain of problems addressable by expert systems, co‐operation is required. To enable this co‐operation, a free exchange of ‘thoughts’ between individual expert systems must be provided. A transparent, modularized communication system, called Backtalk, consisting of a router process and an incoming and outgoing message process pair associated with each expert system has been developed. All messages are sent to the router, which is responsible for determining the exact address of the destination agent and passing the message to the agent. The system uses Unix pipes to pass information between different agents, thereby providing generality in the system. The Backtalk system is similar to the communication system put forth by Bridgeland, Huhns and Arni, but has advantages in dynamic systems. This paper also describes a solution to the issue of defining when messages are allowed to affect the problem‐solving activity of a receiving agent. The system has been tested with communicating expert systems written in the Accord system.
Experience with modularity in consul
Authors: Mishra Shivakant , Peterson Larry L. , Schlichting Richard D.
Published: November 2006

The use of modularity in the design and implementation of complex software simplifies the development process, as well as facilitating the construction of customized configurations. This paper describes our experience using modularity in Consul, a communication substrate used for constructing fault‐tolerant distributed programs. First, Consul is presented as a case study of how modularity is feasible in both the design and the implementation of such systems. Secondly, general lessons about modularity in fault‐tolerant systems based on our experience with Consul are given. Issues that are addressed include deciding how the system is divided into various modules, dealing with problems that result when protocols are combined, and ensuring that the underlying object infrastructure provides adequate support. The key observation is that the modularization process is most affected by dependencies between modules, both direct dependencies caused by one module explicitly using another's operation and indirect dependencies where one module is affected by another without direct interaction. Although our observations are based on designing and implementing Consul, the lessons are applicable to any fault‐tolerant distributed system.
A generational and conservative copying collector for hybrid object‐oriented languages
Authors: Onodera Tamiya
Published: November 2006

A copying collector has two excellent properties: it compacts the heap, and the execution time depends solely on the number of live objects. Use of a copying collector is thought by some to be a more efficient way of managing the heap than explicit freeing of objects. This paper describes a high‐performance copying collector for a hybrid object‐oriented language. The collector is both conservative and generational. It relies on the overlying compiler to identify most true pointers, and on the underlying operating system to detect pointers to younger generations. The implementation described here uses a modified version of the compiler for a C‐based object‐oriented language, and the Mach operating system. The performance results have confirmed the author's expectation: the collector has been faster than explicit freeing.
An application of causal analysis to the software modification process
Authors: Collofello James S. , Gosalia Bakul P.
Published: November 2006

The development of high quality large‐scale software systems within schedule and budget constraints is a formidable software engineering challenge. The modification of these systems to incorporate new and changing capabilities poses an even greater challenge. This modification activity must be performed without adversely affecting the quality of the existing system. Unfortunately, this objective is rarely met. Software modifications often introduce undesirable side‐effects, leading to reduced quality.

In this paper, the software modification process for a large, evolving real‐time system is analysed using causal analysis. Causal analysis is a process for achieving quality improvements via fault prevention. The fault prevention stems from a careful analysis of faults in search of their causes. This paper reports our use of causal analysis on several significant modification activities resulting in about two hundred defects. Recommendations for improved software modification and quality assurance processes based on our findings are also presented.
Static analysis of exception handling in Ada
Authors: Schaefer Carl F. , Bundy Gary N.
Published: November 2006

Since the signature of an Ada subprogram does not specify the set of exceptions that the subprogram can propagate, computing the set of exceptions that a subprogram may encounter is not a trivial task. This is a source of error in large Ada systems: for example, a subprogram may not be prepared to handle an exception propagated from another subprogram several layers lower in the call‐tree. In a large system, the number of paths in exceptional processing is so great that it is unlikely that testing will uncover all errors in inter‐procedural exception handling. Nor are compilers or code inspections likely to locate all such errors. Exception handling is an area where static analysis has a high potential payoff for systems with high reliability requirements. We discuss fundamental notions in computing exception propagation and describe an analysis tool that has proved to be effective in detecting inconsistencies in the exception‐handling code of Ada applications.
Memory allocation costs in large C and C++ programs
Authors: Detlefs David , Dosser Al , Zorn Benjamin
Published: November 2006

Dynamic storage allocation is an important part of a large class of computer programs written in C and C + +. High‐performance algorithms for dynamic storage allocation have been, and will continue to be, of considerable interest. This paper presents detailed measurements of the cost of dynamic storage allocation in 11 diverse C and C + + programs using five very different dynamic storage allocation implementations, including a conservative garbage collection algorithm. Four of the allocator implementations measured are publicly available on the Internet. A number of the programs used in these measurements are also available on the Internet to facilitate further research in dynamic storage allocation. Finally, the data presented in this paper is an abbreviated version of more extensive statistics that are also publicly available on the Internet.
STRESS: A simulator for hard real‐time systems
Authors: Audsley N. C. , Burns A. , Richardson M. F. , Wellings A. J.
Published: November 2006

The STRESS environment is a collection of CASE tools for analysing and simulating the behaviour of hard real‐time safety‐critical applications. It is primarily intended as a means by which various scheduling and resource management algorithms can be evaluated, but can also be used to study the general behaviour of applications and real‐time kernels. This paper describes the structure of the STRESS language and its environment, and gives examples of its use.
Algorithm‐oriented generic libraries
Authors: Musser David R. , Stepanov Alexander A.
Published: November 2006

We outline an approach to construction of software libraries in which generic algorithms (algorithmic abstractions) play a more central role than in conventional software library technology or in the object‐oriented programming paradigm. Our approach is to consider algorithms first, decide what types and access operations they need for efficient execution, and regard the types and operations as formal parameters that can be instantiated in many different ways, as long as the actual parameters satisfy the assumptions on which the correctness and efficiency of the algorithms are based. The means by which instantiation is carried out is language dependent; in the C + + examples in this paper, we instantiate generic algorithms by constructing classes that define the needed types and access operations. By use of such compile‐time techniques and careful attention to algorithmic issues, it is possible to construct software components of broad utility with no sacrifice of efficiency.
Multistage indexing algorithms for speeding prolog execution
Authors: And Ta Chen , Ramakrishnan I. V. , Ramesh R.
Published: November 2006

In a previous article we proposed a new and efficient indexing technique that utilizes all the functors in the clause‐heads and the goal. The salient feature of this technique is that the selected clause‐head unifies (modulo nonlinearity) with the goal. As a consequence, our technique results in sharper discrimination, fewer choice points and reduced backtracking.

A naïve and direct implementation of our indexing algorithms considerably slowed down the execution speeds of a wide range of programs typically seen in practice. This is because it handled deep and shallow terms, terms with few indexable arguments, small and large procedures uniformly. To beneficially extend the applicability of our algorithms we need mechanisms that are ‘sensitive’ to term structures and size and complexity of procedures. We accomplish this in the v‐ALS compiler by carefully decomposing our indexing process into multiple stages. The operations performed by these stages increase in complexity ranging from first argument indexing to unification (modulo nonlinearity). Further the indexing process can be terminated at any stage if it is not beneficial to continue further.

We have now completed the design and implementation of v‐ALS. Using it we have enhanced the performance of a broad range of programs typically encountered in practice. Our experience strongly suggests that indexing based on unification (modulo nonlinearity) is a viable idea in practice and that a broad spectrum of useful programs can realize all of its benefits.
Incremental compiler transformations for multiple instruction retry
Authors: Chen Shyh‐Kwei , Alewine Neal J. , Fuchs W. Kent , Hwu Wen‐Mei W.
Published: November 2006

Previous work on compiler‐based multiple instruction retry has utilized a series of compiler transformations, loop protection, node splitting, and loop expansion, to eliminate anti‐dependencies of length ≤Nin the pseudo register, the machine register, and the post‐pass resolver phases of compilation.1The results have provided a means of rapidly recovering from transient processor failures by rolling backNinstructions. This paper presents techniques for improving compilation and run‐time performance in compiler‐based multiple instruction retry. Incremental updating enhances compilation time when new instructions are added to the program. Post‐pass code rescheduling and spill register reassignment algorithms improve the run‐time performance and decrease the code growth across the application programs studied. Branch hazards are shown to be resolvable by simple modifications to the incremental updating schemes during the pseudo register phase and to the spill register reassignment algorithm during the post‐pass phase.
Coupling hundreds of workstations for parallel molecular sequence analysis
Authors: Strumpen Volker
Published: November 2006

We present a highly scalable approach to distributed parallel computing on workstations in the Internet which provides significant speed‐up to molecular biology sequence analysis. Recent developments show that smaller numbers of workstations connected via a local area network can be used efficiently for parallel computing. This work emphasizes scalability with respect to the number of workstations employed. We show that a massively parallel approach using several hundred workstations, dispersed over all continents, can successfully be applied for solving problems with low requirements on communication bandwidth. We calculated the optimal local alignment scores between a single genetic sequence and all sequences of a genetic sequence database using the ssearch code that is well known among molecular biologists. In a heterogeneous network with more than 800 workstations this job terminated after several minutes, in contrast to several days it would have taken on a single machine.
Finding approximate matches in large lexicons
Authors: Zobel Justin , Dart Philip
Published: November 2006

Approximate string matching is used for spelling correction and personal name matching. In this paper we show how to use string matching techniques in conjunction with lexicon indexes to find approximate matches in a large lexicon. We test several lexicon indexing techniques, including n‐grams and permuted lexicons, and several string matching techniques, including string similarity measures and phonetic coding. We propose methods for combining these techniques, and show experimentally that these combinations yield good retrieval effectiveness while keeping index size and retrieval time low. Our experiments also suggest that, in contrast to previous claims, phonetic codings are markedly inferior to string distance measures, which are demonstrated to be suitable for both spelling correction and personal name matching.
Implementing prototype testing tools
Authors: Hamlet Dick
Published: November 2006

Testing tools are software analyzers that use information from particular executions of a program as well as information about a specification and the program text itself. Research prototypes of such tools are essential to investigate the ideas they embody. Often, hand calculation is so tedious and error‐prone that an investigator cannot obtain any intuition about his or her ideas without an implementation to aid in experiments. Traditionally, such tools have been implemented in conventional high‐level languages (e.g., C, Pascal), a process that takes more time than a prototype should. The technology of compiler generators and logic programming, applied to the idea of self‐instrumenting programs, drastically shortens the prototype cycle.

This paper describes a general method for implementing prototype tools, gives examples of several old and new testing techniques fitted into the method, and discusses the ease with which such prototypes may be changed.
The avatars of a package for calendars in ada
Authors: Gauthier Michel
Published: November 2006

This paper shows the evolution of components for calendars written in Ada, starting from a classic form and evolving by the effect of some choices of software engineering. The first choice is to specify separate components when they do not have to be coupled in only one. This choice transforms a one‐component form into a three‐component one. The second choice is to hide all entities that are not required by the modelling of the real world. This choice modifies many declarations into forms which are complex to specify but which introduce no additional complexity to the user.

In addition to the development of this component for the current legal calendar, it is indicated how others can be defined and converted from any one to the other. The design of a deep automatic test is illustrated. Finally, the paper illustrates how the new features of Ada‐95 can be used to specify these calendars in another form, but which is not essentially different from the Ada‐83 text.
Engineering a hard real‐time system: From theory to practice
Authors: Burns A. , Wellings A. J.
Published: November 2006

More and more programmers find their software being used in performance critical applications. Unfortunately, they have limited techniques at their disposal to help guarantee this particular aspect of their programs. There has been considerable activity in recent years on developing analysis techniques for hard real‐time systems. Inevitably these techniques make simplifying assumptions so as to reduce the complexity of the problem to be solved. For example hard real‐time schedulability analysis techniques often assume that the timing properties of the underlying kernel can be accounted for by incorporating extra execution time into the application tasks. Furthermore, they assume that the application task structure is very simple and uniform. This paper considers the implications of using these techniques in the analysis of a typical single processor application, the attitude and orbital control system (AOCS) for the Olympus satellite. The paper outlines a common approach for estimating the response times for tasks, and then extends the scheduling equations so that they can be used in the engineering of realistic real‐time systems.
A procedural interface for program directing
Authors: Sosič Rok
Published: November 2006

Debugging and performance measurement tools are becoming more important in the development and maintenance of increasingly complex software. These tools belong to a class of programs, called directors. Directors are programs that monitor and control other programs. Through monitoring, directors analyze program execution at runtime. Monitoring provides tracing primitives as well as access to program's variables, dynamic data structures, and its internal state. Results of the monitoring analysis can be used by the director itself to change the future program behavior or presented to a human user for an interactive review and possible feedback actions. The future program behavior is changed through controlling primitives which provide an organized way to modify data values as well as the program code.

This paper presents a library of directing commands which enable the construction of powerful directors. The interface has been implemented in a Unix environment as a runtime subsystem running in the directed program's address space. The paper provides the description of the interface and the basic programming techniques in building directors. Examples of novel applications, illustrating the use of the directing interface, are demonstrated by the directors for the visualization of program control and structured snapshots.
ANTLR: A predicated‐LL(k) parser generator
Authors: Parr T. J. , Quong R. W.
Published: November 2006

Despite the parsing power of LR/LALR algorithms, e.g. YACC, programmers often choose to write recursive‐descent parsers by hand to obtain increased flexibility, better error handling, and ease of debugging. We introduce ANTLR, a public‐domain parser generator that combines the flexibility of hand‐coded parsing with the convenience of a parser generator, which is a component of PCCTS. ANTLR has many features that make it easier to use than other language tools. Most important, ANTLR provides predicates which let the programmer systematically direct the parse via arbitrary expressions using semantic and syntactic context; in practice, the use of predicates eliminates the need to hand‐tweak the ANTLR output, even for difficult parsing problems. ANTLR also integrates the description of lexical and syntactic analysis, accepts LL(k) grammars for k > 1 with extended BNF notation, and can automatically generate abstract syntax trees.

ANTLR is widely used, with over 1000 registered industrial and academic users in 37 countries. It has been ported to many popular systems such as the PC, Macintosh, and a variety of UNIX platforms; a commercial C++ front‐end has been developed as a result of one of our industrial collaborations.
Decompilation of binary programs
Authors: Cifuentes Cristina , Gough K. John
Published: November 2006

The structure of a decompiler is presented, along with a thorough description of the different modules that form part of a decompiler, and the type of analyses that are performed on the machine code to regenerate high‐level language code. The phases of the decompiler have been grouped into three main modules: front‐end, universal decompiling machine, and back‐end. The front‐end is a machine‐dependent module that performs the loading, parsing and semantic analysis of the input program, as well as generating an intermediate representation of the program. The universal decompiling machine is a machine‐ and language‐independent module that performs data and control flow analysis of the program based on the intermediate representation, and the program's control flow graph. The back‐end is a language‐dependent module that deals with the details of the target high‐level language.

In order to increase the readability of the generated programs, a decompiling system has been implemented which integrates a decompiler, dcc, and an automatic signature generator, dccSign. Signatures for libraries and compilers are stored in a database that is read by the decompiler; thus, the generated programs can make use of known library names, such as WriteLn() and printf().

dcc is a decompiler for the Intel 80286 architecture and the DOS operating system. dec takes as input binary programs from a DOS environment and generates C programs as output. Sample code produced by this decompiler is given.
Automatic synthesis of compression techniques for heterogeneous files
Authors: Hsu William H. , Zwarico Amy E.
Published: November 2006

We present a compression technique for heterogeneous files, those files which contain multiple types of data such as text, images, binary, audio, or animation. The system uses statistical methods to determine the best algorithm to use in compressing each block of data in a file (possibly a different algorithm for each block). The file is then compressed by applying the appropriate algorithm to each block. We obtain better savings than possible by using a single algorithm for compressing the file. The implementation of a working version of this heterogeneous compressor is described, along with examples of its value toward improving compression both in theoretical and applied contexts. We compare our results with those obtained using four commercially available compression programs, PKZIP, Unix compress, Stufflt, and Compact Pro, and show that our system provides better space savings.
Process scheduling and UNIX semaphores
Authors: Dunstan Neil , Fris Ivan
Published: November 2006

Semaphores have been used extensively in programming concurrent tasks. Various extensions have been proposed for problems in which traditional semaphores turned out to be difficult to use. The extended semaphore primitives investigated here are based on the version of semaphores implemented in UNIX System V. Implementation issues are discussed and practical illustrations of their use are provided. In particular, algorithms for a variety of common process scheduling schemes are shown. These solutions are evaluated and the strengths and weaknesses of UNIX semaphores are discussed.
Software maintenance: An approach to impact analysis of objects change
Authors: Ajila Samuel
Published: November 2006

The maintenance of a software system requires a tool for impact analysis and the propagation of change. This paper presents a knowledge‐based model for both. This model is generic because it is not based on any language or design method. Therefore, it can be applied on the basis of ‘problem’ to be solved. It also captures four life‐cycle phases:requirement, specification, designandprogramming. We also provide a domain‐specific view that allows the dependency analysis offine‐grainobjects. Two kinds of dependencies are identified:inter‐phase dependencies, these are dependency relations between the objects of the one phase and another; andintra‐phase dependencies, these are dependency relations between the objects of the same phase. In order to validate this model, we also present a prototype based on two life‐cycle phases:designandprogramming.
Formal specification and testing: A case study
Authors: Laycock Gilbert
Published: November 2006

Z is a formal notation for writing system specifications that has been growing in popularity over recent years. This paper examines some of the issues involved in applying a ‘partition based’ testing method to a system specified in Z. Details of an extensive case study are given, from specification and implementation of the system to the development and execution of test cases. The strategy is found to have benefits compared to those based on less formal specifications, but there are limitations to the approach, and difficulties that need addressing.
The revealing power of a test case
Authors: Voas Jeffrey M. , Miller Keith W.
Published: November 2006

‘Propagation, infection, and execution analysis’ (termed PIE) is used for predicting where faults can more easily hide in software. To make such predictions, programs are dynamically executed with test cases, and information concerning the test cases is collected into a histogram, each bin of which represents a single test case. The score in a bin predicts the likelihood that the test case will reveal a fault through the production of a failure (if a fault exists in the set of program locations that the test case executes). Preliminary experiments using program mutations suggest that the histogram technique presented in this paper can rank test cases according to their fault revealing ability.
Employing accumulated knowledge to refine test descriptions
Authors: Wild Christian , Zeil Steven , Feng Gao , Chen Ji
Published: November 2006

Most testing methods generate test descriptions which define the desired characteristics of the input data in a test case. This paper describes the use of accumulated knowledge about a problem domain to refine these test descriptions, with the goal of increasing the probability that the input data generated from the refined test descriptions will reveal faults in a software system. A knowledge base is introduced to hold information about object semantics and object class/subclass relationships. Knowledge accumulates with experience in a particular domain and can be focused on those objects and relationships in that domain which experience has shown to be error‐prone. This paper also defines a knowledge‐driven functional testing (KDFT) method which derives test descriptions from a formal specification and refines these descriptions using that knowledge base. A case study of the KDFT method using data from a previous study of the launch intercept control problem is described. These preliminary results indicate that knowledge‐based refinement of test descriptions can dramatically improve their ability to detect certain classes of faults.
Inductive inference and software testing
Authors: Zhu Hong , Hall Patrick , May John
Published: November 2006

The term ‘inductive inference’ denotes the process of hypothesizing a general rule from examples. It can be considered as the inverse process of program testing, which is a process of sampling the behaviour of a program and gathering confidence in the quality of the software from the samples. As one of the fundamental and ubiquitous components of intelligent behaviour, much effort has been spent on both the theory and practice of inductive inference as a branch of artificial intelligence. In this paper, software testing and inductive inference are reviewed to illustrate how the rich and solid theory of inductive inference can be used to study the foundations of software testing.
A relationship between software coverage metrics and reliability
Authors: Veevers Alan , Marshall Adam C.
Published: November 2006

Software engineers have tacitly assumed that there exists a link between coverage and reliability. An argument is presented which leads to an inverse logarithmic relationship which depends upon the structure of the software and on a parameter called the strength of the coverage metric. The relationship is developed by considering reliability as a function of an idealized coverage metric and then interpreting the result for a range of actual coverage metrics.
An empirical comparison of data flow and mutation‐based test adequacy criteria
Authors: Mathur Aditya P. , Wong W. Eric
Published: November 2006

Evaluation of the adequacy of a test set consisting of one or more test cases is a problem oftes encountered in software testing environments. Two test adequacy criiteria are considered, namely the data flow based all‐uses criterion and a mutation based criterion. An empirical study was conducted to compare the ‘difficulty’ of satisfying the two criteria and their costs. Similar studies conducted in the past are discussed in the light of this study. A discussion is also presented of how and why the results of this study, when viewed in conjunction with the results of earlier comparisons of testing methods, are useful to a software test team.
Validating functional equivalence of re‐engineered programs via control path, result, and data flow comparison
Authors: Sneed Harry M.
Published: November 2006

A combination of three approaches is proposed here to validate the functional equivalence of re‐engineered programs. These are: control path comparison; data result comparison; and data flow comparison. Two of the three approaches are based on the theory of program slicing. The third approach is based on the theory of data invariance, i.e. the same input must produce the same output. Together, these techniques can provide a cost effective regression test environment for large scale re‐engineering projects.
Using program slicing to simplify testing
Authors: Harman Mark , Danicic Sebastian
Published: November 2006

Program slicing is a technique for automatically identifying the statements of a program which affect a selected subset of its variables. A large program can be divided into a number of smaller program (its slices), each constructed for different variable subsets. The slices are typically simpler than the original program, thereby simplifying the process of testing a property of the program which only concerns the corresponding subset of its variables. However, some aspects of a program's computation are not captured by a set of variables, rendering slicing inapplicable. To overcome this difficulty a program can be rewritten in a self‐checking form by the addition of assignment statements to denote these ‘implicit’ computations. Initially this makes the program longer. However, slicing can now be applied to the introspective program, forming a slice concerned solely with the implicit computation. The simplification power of slicing is then improved using program transformation. To illustrate this approach, the implicit computation which dictates whether or not a program is robust is taken as an example. Whether or not a program is robust is not generally decidable making the approach described here particularly appealing because the slices constructed are approximate answers to the undecidable question ‘Is the program p robust?’.
Evaluating the reliability of the software of a switching system with a multi‐variable model
Authors: Bondi Patrizia , Simonetti Guido
Published: November 2006

In recent years reliability growth models have gained a dominant role in the evaluation of the reliability of software products. However, their application to the quality assurance process of the software of a highly complex system such as a telecommunications switching system often shows that it is then possible to get accurate results only when some months of operation have elapsed. It is then impossible to give an answer to the typical questions which arise during the quality assurance phase: ‘Is the software ready for release? How long will it take before it is ready?’. This paper describes a multi‐variable (MV) model which was developed to overcome the above limitation by providing a better model of the quality assurance process. A case study is presented, and a comparison is made between the results obtained by applying existing reliability growth models and the MV‐model to it. Besides attaining surprising accuracy in its predictions and in measuring the reliability of the product, the MV‐model also tries to tackle a different kind of question: ‘How is it possible to improve the effectiveness of testing?’.
Teaching nature of science through inquiry: Results of a 3‐year professional development program
Authors: Akerson Valarie L. , Hanuscin Deborah L.
Published: November 2006

This study assessed the influence of a 3‐year professional development program on elementary teachers' views of nature of science (NOS), instructional practice to promote students' appropriate NOS views, and the influence of participants' instruction on elementary student NOS views. Using the VNOS‐B and associated interviews the researchers tracked the changes in NOS views of teacher participants throughout the professional development program. The teachers participated in explicit–reflective activities, embedded in a program that emphasized scientific inquiry and inquiry‐based instruction, to help them improve their own elementary students' views of NOS. Elementary students were interviewed using the VNOS‐D to track changes in their NOS views, using classroom observations to note teacher influences on student ideas. Analysis of the VNOS‐B and VNOS‐D showed that teachers and most grades of elementary students showed positive changes in their views of NOS. The teachers also improved in their science pedagogy, as evidenced by analysis of their teaching. Implications for teacher professional development programs are made. © 2006 Wiley Periodicals, Inc. J Res Sci Teach 44: 653–680, 2007
An annotated bibliography of scientific visualization. Part 2
Authors: Nielson Gregory M. , Voegele Keith
Published: November 2006

This bibliography evolved as a network using the papers in the volume Visualization of Scientific Computing edited by Gregory M. Nielson and Bruce Shriver and published by IEEE Computer Society Press, 1990 as the root nodes. From there, the supplied reference lists were recursively traversed until a closure resulted either from the common links or from the effective grounding by the highly technical literature of application specializations.

As usual, the standard disclaimers apply; so, for example, this collection is hopefully complete (in the sense that subsets of papers form research vectors that span the space of scientific visualization), but obviously not exhaustively comprehensive. Some of the entries are of a general survey nature, whereas others are quite specific and technical. Pivotal and often quoted works comprise the bulk of the material, but works of historical and developmental significance are also included especially where they point to researchers, research centres and journals where important work has been, and is being, performed and recorded. The annotations accompanying the references tend to be impressionistic and apologies to the authors are hereby noted for those instances where omissions, misunderstandings and whimsy have resulted in misinterpretations. The support of the U.S. Department of Energy is appreciated.
The generalized display processors as an approach to real‐time interactive 3‐D computer animation
Authors: van Overveld C. W. A. M.
Published: November 2006

The concept of the display processor unit (DPU; see Reference 1, p. 94) is extended to arrive at a generalized display processor (GDP) which is able not only to produce a static screen image given the descriptions of a list of graphics elements but which allows for these graphics elements to show an autonomous kinematic (motion‐)behaviour. A language to program such a GDP is presented, and a software implementation of an interpreter/processor for this language is discussed. The application of a GDP both in computer animation and in interactive process control applications is sketched.