Search

An iterative technique for the computation of approximate performance indices of a class of stochastic Petri nets models is presented. The proposed technique is derived from the mean value analysis algorithm for product form solution stochastic Petri nets. In this paper, we apply the approximation technique to stochastic marked graphs. In principle, the proposed technique can be used for other stochastic Petri net subclasses in the paper, some of these possible applications are presented. Several examples are presented in order to validate the approximate results. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses various papers within the issue on topics including dynamic specification mining, code vulnerabilities leading to loading of malicious content, and fault-localization algorithms used on web applications.

This paper describes facilities added to a conventional programming language that will manipulate streams of values. A stream is a sequence of values of a certain fixed type. The number of elements of a stream may be determined at execution time, and evaluation of each element can be postponed until its value is actually needed. Many programs can be expressed naturally and clearly as networks of processes communicating by means of streams. The network is called a composite function and consists of several component functions. Since component functions are connected solely by streams, they greatly increase the flexibility of combinations and the reusability of programs. Loop statements can be considered as iterative statements over streams. One general problem In these networks Is the mechanism of terminating each process of the network. This paper presents a practical solution for this problem. Comparisons to other programming styles, such as coroutines, Lisp, functional programming, and data flow languages, are described. Three modes of execution are considered for the implementation of composite functions: parallel mode, coroutine mode, and in-line mode. In the in- line mode, a composite function is expanded and transformed into a single function, realizing maximum run-time efficiency. Algorithms for this expansion are given. The language in this paper has been designed as an extension of Pascal. A subset of it has been implemented. [ABSTRACT FROM AUTHOR]

For the development of communications software com- posed of many modules, protocol validation is essential to detect errors in the interactions among the modules. A number of protocol validation techniques were proposed in the past, but the validation time required by these techniques is too long for many actual protocols. This paper proposes a new fast protocol validation technique to overcome this drawback. The proposed technique is to construct the minimum acyclic form of state transitions in individual processes of the protocol, and to detect protocol errors such as system deadlocks and channel overflows fast. This paper also presents a protocol validation system based on the proposed technique to confirm its feasibility and shows validation results for some actual protocols obtained with this system. As a result, the protocol validation system is expected to contribute to a great extent to the improvement of the productivity in development and maintenance of communications software. [ABSTRACT FROM AUTHOR]

Regression testing is an expensive, but important, process. Unfortunately, there may be insufficient resources to allow for the reexecution of all test cases during regression testing. In this situation, test case prioritization techniques aim to improve the effectiveness of regression testing by ordering the test cases so that the most beneficial are executed first. Previous work on regression test case prioritization has focused on Greedy Algorithms. However. it is known that these algorithms may produce suboptimal results because they may construct results that denote only local minima within the search space. By contrast, metaheuristic and evolutionary search algorithms aim to avoid such problems. This paper presents results from an empirical study of the application of several greedy, metaheuristic, and evolutionary search algorithms to six programs, ranging from 374 to 11,148 lines of code for three choices of fitness metric. The paper addresses the problems of choice of fitness metric, characterization of landscape modality, and determination of the most suitable search technique to apply. The empirical results replicate previous results concerning Greedy Algorithms. They shed light on the nature of the regression testing search space, indicating that it is multimodal. The results also show that Genetic Algorithms perform well, although Greedy approaches are surprisingly effective, given the multimodal nature of the landscape. [ABSTRACT FROM AUTHOR]

Conventional database design techniques rely heavily on the designer's skill and experience, which are neither efficient nor effective for large, realistic design problems. A computer design aid can help by storing many design parameters and performing simple pre- processing before design decisions are made. In this paper, we report on the development of such a system. The system is based on a data model called the Functional Data Model (FDM), and on a transaction (or process) model which is specified via the Transaction Specification Language (TASL). FDM is used to define data entities and the relationships between them. TASL is used to capture application processing intent and performance parameters that are relevant to the database design. Logical database design involves two major steps. First, local (or application) views are modeled using FDM and TASL. Second, in order to achieve an integrated database design, these local views are combined and transformed to produce a global conceptual view (schema). This paper describes FDM and TASL; in addition, a set of operations for integrating and transforming local views is presented. A unique feature of these transformations is that they apply to TASL processes as well as FDM schema Finally, an algorithm is given for view integration. This algorithm, along with heuristics and some user-supplied subset assertions, enables the database design system to automatically identify and filter out redundancies. [ABSTRACT FROM AUTHOR]

In most large computer installations files ate moved between on-line disk and mass storage (tape, integrated mass storage device) either automatically by the system and/or at the direction of the user. In this paper we present and analyze long term rile reference data in order to develop a basis for the construction of algorithms for file migration. Specifically, we examine the use of the on-line user (primarily text editor) data sets at the Stanford Linear Accelerator Center (SLAC) computer installation through the analysis of 13 months of file reference data. We find that most files are used very few times, Of those that are used sufficiently frequently that their reference patterns may be examined, we find that: 1) about a third show declining rates of reference during their lifetime, 2) of the remainder, very few (about 5 percent) show correlated interreference intervals, and 3) interreference intervals (in days) appear to be more skewed than would occur with the Bernoulli process. Thus, about two-thirds of all sufficiently active files appear to be referenced as a renewal process with a skewed interreference distribution. A large number of other file reference statistics (file lifetimes, interference distributions, moments, means, number of uses/file, file sizes, file rates of reference, etc.) are computed and presented. Throughout, statistical tests are described and explained. The results of our analysis of file reference patterns are applied in a companion paper to the development and comparative evaluation of file migration algorithms. [ABSTRACT FROM AUTHOR]

One of the major difficulties in developing embedded systems with object-oriented modeling is to translate a designed model into code that satisfies required real-time performance. This paper proposes scenario-based implementation synthesis architecture with timing guarantee (SISAtime) that addresses these difficulties. The problems that SISAtime must solve are: how to synthesize multithreaded-code from a real-time object-oriented model; and how to design supporting development tools and runtime system architecture while ensuring that the scenarios in the system have minimal response times and the code satisfies the given timing constraints with a minimal number of threads. SISAtime provides a new scheduling algorithm which minimizes scenario response times. SISAtime also provides a new thread derivation method that derives tasks and maps tasks to threads while automatically assigning task scheduling attributes. We have fully implemented SISAtime by extending the RoseRT development tool that uses UML 2.0 as a modeling language, and we applied it to an existing industrial private branch exchange system. The performance evaluation results show that the response times, context switches, and the number of threads of the system with SISAtime were reduced by 21.6, 33.2, and 65.2 percent, respectively, compared to the system with the best known existing thread derivation method. [ABSTRACT FROM PUBLISHER]

When a software engineer finds an inconsistency in a model, then the first question is why? What caused it? Obviously, there must be an error. But where could it be? Or is the design rule erroneous and if yes then which part? The cause of an inconsistency identifies the part of the model or design rule where the error must be. We believe that the visualization of an inconsistency ought to visualize the cause. Understanding the cause is of vital importance before a repair can even be formulated. Indeed, any automation (e.g., code generation, refactoring) has to be considered with caution if it involves model elements that cause inconsistencies. This paper analyzes the basic structure of inconsistent design rules as well as their behavior during validation and presents an algorithm for computing its cause. The approach is fully automated, tool supported, and was evaluated on 14,111 inconsistencies across 29 design models. We found that our approach computes correct causes for inconsistencies, these causes are nearly always a subset of the model elements investigated by the design rules' validation (a naive cause computation approximation), and the computation is very fast (99.8 percent of the causes are computable in < 100 ms). [ABSTRACT FROM PUBLISHER]

Modern programming environments provide extensive support for inspecting, analyzing, and testing programs based on the algorithmic structure of a program. Unfortunately, support for inspecting and understanding runtime data structures during execution is typically much more limited. This paper provides a general purpose technique for abstracting and summarizing entire runtime heaps. We describe the abstract heap model and the associated algorithms for transforming a concrete heap dump into the corresponding abstract model as well as algorithms for merging, comparing, and computing changes between abstract models. The abstract model is designed to emphasize high-level concepts about heap-based data structures, such as shape and size, as well as relationships between heap structures, such as sharing and connectivity. We demonstrate the utility and computational tractability of the abstract heap model by building a memory profiler. We use this tool to identify, pinpoint, and correct sources of memory bloat for programs from DaCapo. [ABSTRACT FROM PUBLISHER]

In hard real-time systems, gain time is defined as the difference between the Worst Case Execution Time (WCET) of a hard task and its actual processor consumption at runtime. This paper presents the results of an empirical study about how the presence of a significant amount of gain time in a hard real-time system questions the advantages of using the most representative scheduling algorithms or policies for aperiodic or soft tasks in fixed-priority preemptive systems. The work presented here refines and complements many other studies in this research area in which such policies have been introduced and compared. This work has been performed by using the authors' testing framework for soft scheduling policies, which produces actual, synthetic, randomly generated applications, executes them in an instrumented Real-Time Operating System (RTOS), and finally processes this information to obtain several statistical outcomes. The results show that, in general, the presence of a significant amount of gain time reduces the performance benefit of the scheduling policies under study when compared to serving the soft tasks in background, which is considered the theoretical worst case. In some cases, this performance benefit is so small that the use of a specific scheduling policy for soft tasks is questionable. [ABSTRACT FROM AUTHOR]

Providing evidence for the refutation of a property is an essential, if not the most important, feature of model checking. This paper considers algorithms for counterexample generation for probabilistic CTL formulas in discrete-time Markov chains. Finding the strongest evidence (i.e., the most probable path) violating a (bounded) until-formula is shown to be reducible to a single-source (hop-constrained) shortest path problem. Counterexamples of smallest size that deviate most from the required probability bound can be obtained by applying (small amendments to) k-shortest (hop-constrained) paths algorithms. These results can be extended to Markov chains with rewards, to LTL model checking, and are useful for Markov decision processes. Experimental results show that, typically, the size of a counterexample is excessive. To obtain much more compact representations, we present a simple algorithm to generate (minimal) regular expressions that can act as counterexamples. The feasibility of our approach is illustrated by means of two communication protocols: leader election in an anonymous ring network and the Crowds protocol. [ABSTRACT FROM AUTHOR]

Researchers have explored the application of combinatorial interaction testing (CIT) methods to construct samples to drive systematic testing of software system configurational Applying CIT to highly-configurable software systems is complicated by the fact that, in many such systems, there are constraints between specific configuration parameters that render certain combinations invalid. Many CIT algorithms lack a mechanism to avoid these. In recent work, automated constraint solving methods have been combined with search-based CIT construction methods to address the constraint problem with promising results. However, these techniques can incur a nontrivial overhead. In this paper, we build upon our previous work to develop a family of greedy CIT sample generation algorithms that exploit calculations made by modern Boolean satisfiability (SAT) solvers to prune the search space of the CIT problem. We perform a comparative evaluation of the cost effectiveness of these algorithms on four real-world highly-configurable software systems and on a population of synthetic examples that share the characteristics of these systems. In combination, our techniques reduce the cost of CIT in the presence of constraints to 30 percent of the cost of widely used unconstrained CIT methods without sacrificing the quality of the solutions. [ABSTRACT FROM AUTHOR]

Component-Based Software Engineering focuses on the reuse of existing software components. In practice, most components cannot be integrated directly into an application-to-be because they are incompatible. Software Adaptation aims at generating, as automatically as possible, adaptors to compensate for a mismatch between component interfaces and is therefore a promising solution for the development of a real market of components promoting software reuse. In this paper, we present our approach for software adaptation, which relies on an abstract notation based on synchronous vectors and transition systems for governing adaptation rules. Our proposal is supported by dedicated algorithms that automatically generate adaptor protocols. These algorithms have been implemented in a tool, called Adaptor, which can be used through a user-friendly graphical interface. [ABSTRACT FROM AUTHOR]

In systems developed without aspect-oriented programming, code implementing a crosscutting concern may be spread over many different parts of a system. Identifying such code automatically could be of great help during maintenance of the system. First of all, it allows a developer to more easily find the places in the code that must be changed when the concern changes and, thus, makes such changes less time consuming and less prone to errors. Second, it allows the code to be refactored to an aspect-oriented solution, thereby improving its modularity. In this paper, we evaluate the suitability of clone detection as a technique for the identification of crosscutting concerns. To that end, we manually identify five specific crosscutting concerns in an industrial C system and analyze to what extent clone detection is capable of finding them. We consider our results as a stepping stone toward an automated "aspect miner" based on clone detection. [ABSTRACT FROM AUTHOR]

This paper describes a program representation and algorithms for realizing a novel structural testing methodology that not only focuses on addressing the complex features of object-oriented languages, but also incorporates the structure of object-oriented software into the approach. The testing methodology is based on the construction of contextual def-use associations, which provide context to each definition and use of an object. Testing based on contextual def-use associations can provide increased test coverage by identifying multiple unique contextual def-use associations for the same context-free association. Such a testing methodology promotes more thorough and focused testing of the manipulation of objects in object-oriented programs. This paper presents a technique for the construction of contextual def-use associations, as well as detailed examples illustrating their construction, an analysis of the cost of constructing contextual def-use associations with this approach, and a description of a prototype testing tool that shows how the theoretical contributions of this work can be useful for structural test coverage. [ABSTRACT FROM AUTHOR]

A test coverage criterion defines a set E[SUBc] of entities of the program flowgraph and requires that every entity in this set is covered under some testcase. Coverage criteria are also used to measure the adequacy of the executed test cases. In this paper, we introduce the notion of spanning sets of entities for coverage testing. A spanning set is a minimum subset of E[SUBc], such that a test suite covering the entities in this subset is guaranteed to cover every entity in E[SUBc]. When the coverage of an entity always guarantees the coverage of another entity, the former is said to subsume the latter. Based on the subsumption relation between entities, we provide a generic algorithm to find spanning sets for control flow and data flow-based test coverage criteria. We suggest several useful applications of spanning sets: They help reduce and estimate the number of test cases needed to satisfy coverage criteria. We also empirically investigate how the use of spanning sets affects the fault detection effectiveness. [ABSTRACT FROM AUTHOR]

In this paper, we show the structural characteristics that a particular class of Generalized Stochastic Petri Nets must exhibit in order for their stationary probabilities to have a product-form. Sufficient conditions for identifying such a class are derived and proven with the development of a series of transformations that can also be used to construct, for any GSPN of the class, an equivalent SPN. These resulting SPNs represent the structures that can be analyzed with standard methods for Product-Form SPNs to establish whether the original GSPNs have Product-Form solutions and to compute their performance indices with effective approaches based on computationally efficient algorithms that avoid the generation of their underlying state spaces. [ABSTRACT FROM AUTHOR]

The well-known periodic task model of Liu and Layland [10] assumes a worst-case execution time bound for every task and may be too pessimistic if the worst-case execution time of a task is much longer than the average. In this paper, we give a multiframe real-time task model which allows the execution time of a task to vary from one instance to another by specifying the execution time of a task in terms of a sequence of numbers. We investigate the schedulability problem for this model for the preemptive fixed priority scheduling policy. We show that a significant improvement in the utilization bound can be established in our model. [ABSTRACT FROM AUTHOR]

Numerous algorithms for computationally intensive tasks have been developed by researchers that are suitable for execution on hypercube multiprocessors. One characteristic of many of these algorithms is that they are extremely structured and are tuned for the highest performance to execute on hypercube architectures. In this paper, we have looked at parallel algorithm design from a different perspective. In many cases, it may be possible to redesign the parallel algorithms using software techniques so as to provide a low-cost on-line scheme for hardware error detection without any hardware modifications. This approach is called Algorithm-based error detection. In the past, we have applied algorithm-based techniques for on-line error detection on the hypercube and have reported some preliminary results of one specific implementation on some applications. In this paper, we provide an in-depth study of the various issues and tradeoffs available in Algorithm-based error detection, as well as a general methodology for evaluating the schemes. We have illustrated the approach on an extremely useful computation in the field of numerical linear algebra: QR factorization. We have implemented and investigated numerous ways of applying algorithm-based error detection using different system-level encoding strategies for QIZ factorization. Different schemes have been observed to result in varying error coverages and time overheads. We have reported the results of our studies performed on a 16 processor Intel iPSC-2/D4/MX hypercube multiprocessor. [ABSTRACT FROM AUTHOR]

In this paper, we have investigated the efficient evaluation of branch-and-bound algorithms in a system with a two-level memory hierarchy. An efficient implementation depends on the disparities in the numbers of subproblems expanded between the depth-first and best-first searches as well as the relative speeds of the main and secondary memories. A best-first search should be used when it expands a much smaller number of subproblems than that of a depth-first search, and the secondary memory is relatively fast. In contrast, a depth-first search should be used when the number of expanded subproblems is close to that of a best-first search. The choice is not as clear for cases in between. The Iterative Deepening A* (IDA*) algorithm has been shown to be asymptotically optimal in space, time, and cost. However, for the conditions that we have assumed, 1DM does not result in the optimal space-time tradeoff for minimizing the completion time. In this paper, we study the space-time tradeoff by proposing and analyzing two strategies: a specialized virtual-memory system that matches the architectural design with the characteristics of the existing algorithm, and a modified branch-and-bound algorithm that can be tuned to the characteristic of the problem and the architecture. The latter strategy illustrates that designing a better algorithm is sometimes more effective than tuning the architecture alone. Guidelines have also been developed to select appropriate a priori values for the parameters of the modified B&B algorithm. [ABSTRACT FROM AUTHOR]

When a crash occurs in a transaction processing system, the database can enter an unacceptable state. To continue the processing, the recovery system has three tasks: 1) verification of the database state for acceptability, 2) restoration of an acceptable database state, and 3) restoration of an acceptable history of transaction processing. Unfortunately these tasks are not trivial and the computational complexity of the algorithms for most of them is either NP-complete or NP- hard. In this paper we discuss the concepts and design issues of a construct called database integrity block (DIB). The implementation of this construct allows for efficient verification of the database state by employing a set of integrity assertions and restoration of transaction history by utilizing any database restoration technique such as audit trail or differential file. This paper presents approximation algorithms for minimizing the costs of evaluation of integrity assertions by modeling the problem as the directed traveling salesman problem, and presents a methodology to compare the costs of audit trail and differential file techniques for database restoration. The applicability of integrity verification research to the problem of multiple-query optimization is also included. [ABSTRACT FROM AUTHOR]

This paper proposes a model or paradigm for the development of parallel algorithms, gives an example of the proposed paradigm, and displays algorithms developed by application of the technique. The algorithm for the merge of two ordered fists developed through application of this technique is thought to be original. The paradigm proposed is to create composite unit operations which combine data movement between data structures with a conventional operation such as compare or add. The composite operation constructed for this study is based upon partitioning the data elements into two linear lists. Exchange of data between adjacent elements in each list are then combined with compares and adds to complete the composite operations. This composite operation can be implemented on at least the following computational architectures. 1) SIMD with all processors sharing a common memory. 2) SIMD with local memories and a linear interconnection (circular pipeline or ring network of processors). 3) Vector processor with common memory, such as a CDC CYBER 205 or a Cray Research CRAY-1. The algorithms developed all have the property of linear speed-up with the number of processing elements. The algorithms developed include sorting, merging, selection among sets, set interconnection, set difference, subset testing, and string matching. [ABSTRACT FROM AUTHOR]

As multiple processor systems become more widely accepted the importance of parallel programming increases. In this paper, approaches to the design and analysis of parallel algorithms are investigated. Through several examples, the importance of interprocessor communication in parallel processing is demonstrated. Various techniques that are applicable in the design and analysis of parallel algorithms are examined with emphasis on those techniques that incorporate communication aspects. The paper discusses several models of synchronous and asynchronous parallel computation and their use in analyzing algorithms. Relatively primitive methodologies for designing parallel algorithms are discussed and the need for more general and practical methodologies is indicated. [ABSTRACT FROM AUTHOR]

Software maintenance is the dominant factor contributing to the high cost of software. In this paper, the software maintenance process and the important software quality attributes that affect the maintenance effort are discussed. One of the most important quality attributes of software maintainability is the stability of a program, which indicates the resistance to the potential ripple effect that the program would have when it is modified. Measures for estimating the stability of a program and the modules of which the program is composed are presented. and an algorithm for computing these stability measures is given. An algorithm for normalizing these measures is also given. Applications of these measures during the maintenance phase are discussed along with an example. An indirect validation of these stability measures is also given. Future research efforts involving application of these measures during the design phase, program restructuring based on those measures, and the development of an overall maintainability measure arc also discussed. [ABSTRACT FROM AUTHOR]

This paper discusses axiomatic and functional models of the semantics of structured programming. The models are presented together with their respective methodologies (or proving program correctness and for denying correct programs. Examples using these methodologies are given. Finally, the models are compared and contrasted. [ABSTRACT FROM AUTHOR]

In this paper, we present an approximate solution for the asymptotic behavior of relatively general queueing networks. In the particular case of networks with general service time distributions (i.e., fixed routing matrix, one or many servers per station, FIFO discipline), the application of the method gives relatively accurate results in a very short time. The approximate stationary state probabilities are identified with the solution of a nonlinear system. The proposed method is applicable to a larger class of queueing networks (dependent routing matrix, stations with finite capacity, etc.). In this case, the structure of the network studied must satisfy certain decomposability conditions. [ABSTRACT FROM AUTHOR]

Backward error recovery (that is, resetting an erroneous state of a system to a previous error-free state) is an important general technique for recovery from faults in a system, especially those faults which were not foreseen. However, the provision of backward error recovery can be complex, particularly if the implementation of the system is ‘multilevel’ and recovery is to be provided at a number of these levels. This paper discusses two distinct categories of multilevel system, and then examines in detail the issues involved in providing backward error recovery in both types of system. [ABSTRACT FROM AUTHOR]

We present Magiclock, a novel potential deadlock detection technique by analyzing execution traces (containing no deadlock occurrence) of large-scale multithreaded programs. Magiclock iteratively eliminates removable lock dependencies before potential deadlock localization. It divides lock dependencies into thread specific partitions, consolidates equivalent lock dependencies, and searches over the set of lock dependency chains without the need to examine any duplicated permutations of the same lock dependency chains. We validate Magiclock through a suite of real-world, large-scale multithreaded programs. The experimental results show that Magiclock is significantly more scalable and efficient than existing dynamic detectors in analyzing and detecting potential deadlocks in execution traces of large-scale multithreaded programs. [ABSTRACT FROM PUBLISHER]

Several variants of evolutionary algorithms (EAs) have been applied to solve the project scheduling problem (PSP), yet their performance highly depends on design choices for the EA. It is still unclear how and why different EAs perform differently. We present the first runtime analysis for the PSP, gaining insights into the performance of EAs on the PSP in general, and on specific instance classes that are easy or hard. Our theoretical analysis has practical implications—based on it, we derive an improved EA design. This includes normalizing employees’ dedication for different tasks to ensure they are not working overtime; a fitness function that requires fewer pre-defined parameters and provides a clear gradient towards feasible solutions; and an improved representation and mutation operator. Both our theoretical and empirical results show that our design is very effective. Combining the use of normalization to a population gave the best results in our experiments, and normalization was a key component for the practical effectiveness of the new design. Not only does our paper offer a new and effective algorithm for the PSP, it also provides a rigorous theoretical analysis to explain the efficiency of the algorithm, especially for increasingly large projects. [ABSTRACT FROM PUBLISHER]

The configuration spaces of modern software systems are too large to test exhaustively. Combinatorial interaction testing (CIT) approaches, such as covering arrays, systematically sample the configuration space and test only the selected configurations by using a battery of test cases. Traditional covering arrays, while taking system-wide interoption constraints into account, do not provide a systematic way of handling test case-specific interoption constraints. The basic justification for $(t)$-way covering arrays is that they can cost effectively exercise all system behaviors caused by the settings of $(t)$ or fewer options. In this paper, we hypothesize, however, that in the presence of test case-specific interoption constraints, many such behaviors may not be tested due to masking effects caused by the overlooked test case-specific constraints. For example, if a test case refuses to run in a configuration due to an unsatisfied test case-specific constraint, none of the valid option setting combinations appearing in the configuration will be tested by that test case. To account for test case-specific constraints, we introduce a new combinatorial object, called a test case-aware covering array. A $(t)$-way test case-aware covering array is not just a set of configurations, as is the case in traditional covering arrays, but a set of configurations, each of which is associated with a set of test cases such that all test case-specific constraints are satisfied and that, for each test case, each valid combination of option settings for every combination of $(t)$ options appears at least once in the set of configurations that the test case is associated with. We furthermore present three algorithms to compute test case-aware covering arrays. Two of the algorithms aim to minimize the number of configurations required (one is fast, but produces larger arrays, the other is slower, but produces smaller arrays), whereas the remaining algorithm aims to minimize the number of test runs required. The results of our empirical studies conducted on two widely used highly configurable software systems suggest that test case-specific constraints do exist in practice, that traditional covering arrays suffer from masking effects caused by ignorance of such constraints, and that test case-aware covering arrays are better than other approaches in handling test case-specific constraints, thus avoiding masking effects. [ABSTRACT FROM PUBLISHER]

Software Cost Estimation can be described as the process of predicting the most realistic effort required to complete a software project. Due to the strong relationship of accurate effort estimations with many crucial project management activities, the research community has been focused on the development and application of a vast variety of methods and models trying to improve the estimation procedure. From the diversity of methods emerged the need for comparisons to determine the best model. However, the inconsistent results brought to light significant doubts and uncertainty about the appropriateness of the comparison process in experimental studies. Overall, there exist several potential sources of bias that have to be considered in order to reinforce the confidence of experiments. In this paper, we propose a statistical framework based on a multiple comparisons algorithm in order to rank several cost estimation models, identifying those which have significant differences in accuracy, and clustering them in nonoverlapping groups. The proposed framework is applied in a large-scale setup of comparing 11 prediction models over six datasets. The results illustrate the benefits and the significant information obtained through the systematic comparison of alternative methods. [ABSTRACT FROM AUTHOR]

Although Random Testing (RT) is low cost and straightforward, its effectiveness is not satisfactory. To increase the effectiveness of RT, researchers have developed Adaptive Random Testing (ART) and Quasi-Random Testing (QRT) methods which attempt to maximize the test case coverage of the input domain. This paper proposes the use of Centroidal Voronoi Tessellations (CVT) to address this problem. Accordingly, a test case generation method, namely, Random Border CVT (RBCVT), is proposed which can enhance the previous RT methods to improve their coverage of the input space. The generated test cases by the other methods act as the input to the RBCVT algorithm and the output is an improved set of test cases. Therefore, RBCVT is not an independent method and is considered as an add-on to the previous methods. An extensive simulation study and a mutant-based software testing investigation have been performed to demonstrate the effectiveness of RBCVT against the ART and QRT methods. Results from the experimental frameworks demonstrate that RBCVT outperforms previous methods. In addition, a novel search algorithm has been incorporated into RBCVT reducing the order of computational complexity of the new approach. To further analyze the RBCVT method, randomness analysis was undertaken demonstrating that RBCVT has the same characteristics as ART methods in this regard. [ABSTRACT FROM AUTHOR]

Model checking is a formal verification method widely accepted in the web service world because of its capability to reason about service behavior at process level. It has been used as a basic tool in several scenarios such as service selection, service validation, and service composition. The importance of semantics is also widely recognized. Indeed, there are several solutions to the problem of providing semantics to web services, most of them relying on some form of Description Logic. This paper presents an integration of model checking and semantic reasoning technologies in an efficient way. This can be considered the first step toward the use of semantic model checking in problems of selection, validation, and composition. The approach relies on a representation of services at process level that is based on semantically annotated state transition systems (asts) and a representation of specifications based on a semantically annotated version of computation tree logic (anctl). This paper proves that the semantic model checking algorithm is sound and complete and can be accomplished in polynomial time. This approach has been evaluated with several experiments. [ABSTRACT FROM PUBLISHER]

Search-Based Test Data Generation reformulates testing goals as fitness functions so that test input generation can be automated by some chosen search-based optimization algorithm. The optimization algorithm searches the space of potential inputs, seeking those that are “fit for purpose,” guided by the fitness function. The search space of potential inputs can be very large, even for very small systems under test. Its size is, of course, a key determining factor affecting the performance of any search-based approach. However, despite the large volume of work on Search-Based Software Testing, the literature contains little that concerns the performance impact of search space reduction. This paper proposes a static dependence analysis derived from program slicing that can be used to support search space reduction. The paper presents both a theoretical and empirical analysis of the application of this approach to open source and industrial production code. The results provide evidence to support the claim that input domain reduction has a significant effect on the performance of local, global, and hybrid search, while a purely random search is unaffected. [ABSTRACT FROM PUBLISHER]

In this paper, we describe a novel technique that helps a modeler gain insight into the dynamic behavior of a complex stochastic discrete-event simulation model based on trace analysis. We propose algorithms to distinguish progressive from repetitive behavior in a trace and to extract a minimal progressive fragment of a trace. The implied combinatorial optimization problem for trace reduction is solved in linear time with dynamic programming. We present and compare several approximate and one exact solution method. Information on the reduction operation as well as the reduced trace itself helps a modeler to recognize the presence of certain errors and identify their cause. We track down a subtle modeling error in a dependability model of a multiclass server system to illustrate the effectiveness of our approach in revealing the cause of an observed effect. The proposed technique has been implemented and integrated in Traviando, a trace analyzer to debug stochastic simulation models. [ABSTRACT FROM AUTHOR]

Introduce the Class-oriented Method of Moments (CoMoM), a new exact algorithm to compute performance indexes in closed multiclass queuing networks. Closed models are important for performance evaluation of multitier applications, but when the number of service classes is large, they become too expensive to solve with exact methods such as Mean Value Analysis (MVA). CoMoM addresses this limitation by a new recursion that scales efficiently with the number of classes. Compared to the MVA algorithm, which recursively computes mean queue lengths, CoMoM also carries on in the recursion information on higher-order moments of queue lengths. We show that this additional information greatly reduces the number of operations needed to solve the model and makes CoMoM the best-available algorithm for networks with several classes. We conclude the paper by generalizing CoMoM to the efficient computation of marginal queue-length probabilities, which finds application in the evaluation of state-dependent attributes such as quality-of-service metrics. [ABSTRACT FROM AUTHOR]

The identification of design patterns as part of the reengineering process can convey important information to the designer. However, existing pattern detection methodologies generally have problems in dealing with one or more of the following issues: Identification of modified pattern versions, search space explosion for large systems and extensibility to novel patterns. In this paper, a design pattern defection methodology is proposed that is based on similarity scoring between graph vertices. Due to the nature of the underlying graph algorithm, this approach has the ability to also recognize patterns that are modified from their standard representation. Moreover, the approach exploits the fact that patterns reside in one or more inheritance hierarchies, reducing the size of the graphs to which the algorithm is applied. Finally, the algorithm does not rely on any pattern-specific heuristic, facilitating the extension to novel design structures. Evaluation on three open-source projects demonstrated the accuracy and the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

The majority of the algorithms in the software clustering literature utilize structural information to decompose large software systems. Approaches using other attributes, such as file names or ownership information, have also demonstrated merit. At the same time, existing algorithms commonly deem all attributes of the software artifacts being clustered as equally important, a rather simplistic assumption. Moreover, no method that can assess the usefulness of a particular attribute for clustering purposes has been presented in the literature. In this paper, we present an approach that applies information theoretic techniques in the context of software clustering. Our approach allows for weighting schemes that reflect the importance of various attributes to be applied. We introduce LIMBO, a scalable hierarchical clustering algorithm based on the minimization of information loss when clustering a software system. We also present a method that can assess the usefulness of any nonstructural attribute in a software clustering context. We applied LIMBO to three large software systems in a number of experiments. The results indicate that this approach produces clusterings that come close to decompositions prepared by system experts. Experimental results were also used to validate our usefulness assessment method. Finally, we experimented with well-established weighting schemes from information retrieval, web search, and data clustering. We report results as to which weighting schemes show merit in the decomposition of software systems. [ABSTRACT FROM AUTHOR]

Deadlocks in the OR model are usually resolved by aborting a deadlocked process. Prior algorithms for the same model sometimes abort nodes needlessly wasting computing resources. This paper presents a new deadlock resolution algorithm for the OR model that satisfies the following correctness criteria: (Safety) the algorithm does not resolve false deadlocks; (Liveness) the algorithm resolves all deadlocks in finite time. The communication cost of the algorithm is similar to that of previous nonsafe proposals. The theoretical cost has been validated by simulation. In addition, different algorithm initiation alternatives have been analyzed in order to reduce the latency of deadlocks. [ABSTRACT FROM AUTHOR]

This paper describes the design and implementation of an intelligent tutoring system for the Dijkstra-Gries programming methodology as defined by Cries in "The Science of Programming"[12]. The first part of the paper identifies the requirements of intelligent tutoring systems in general and those of the methodology in particular. It shows the suitability of the Smalltalk environment for developing expandable intelligent systems and the compatibility of Smalltalk's object-oriented paradigm with the Gries methodology's goal/plan approach to programming. We then describe how these requirements are met: an overview of the system's support of the methodology and the modules that enable the system to respond intelligently. As an example, a reusable tutorial part is presented, first from a student's perspective, then from an author's perspective. Finally the results of an evaluation of the system drawn from actual student experience are presented. [ABSTRACT FROM AUTHOR]

A self-stabilizing system is a network of processors, which, when started from an arbitrary (and possibly illegal) initial state, always returns to a legal state in a finite number of steps. This implies that the system can automatically deal with infrequent errors. One issue in designing self-stabilizing algorithms is the number of states required by each machine. This paper presents mutual exclusion algorithms which will be self-stabilizing while only requiring each machine in the network to have two states. The concept of a randomized central demon is also introduced in this paper. The first algorithm is a starting point where no randomization is needed (the randomized central demon is not necessary). The other two algorithms require randomization. The second algorithm builds on the first algorithm and reduces the number of network connections required. Finally, the number of necessary connections is again reduced yielding the final two-state, probabilistic algorithm for an asynchronous, unidirectional ring of processes. [ABSTRACT FROM AUTHOR]

This paper studies and compares the performance of several algorithms suitable for processing an important class of recursive queries, the so-called instantiated transitive closure (TC) queries. These algorithms are the two well known algorithms wavefront and .5-wavefront and a newly proposed generic algorithm called super-TC. During the evaluation of a TC query, the first two algorithms may read a given disk page more than once, whereas super-TC reads the disk page at most once. This paper also presents a comprehensive performance evaluation of these three algorithms using rigorous analytical and simulation models. Such a study reveals that the relative performance of the algorithms is a strong function of the parameters which characterize the processed TC query and the relation referenced by that query. Furthermore, it points out the superiority of one of the super-TC variants over all of the other presented algorithms. [ABSTRACT FROM AUTHOR]

The concept of multiway rendezvous has been proposed to implement synchronous communication among an arbitrary number of concurrent, asynchronous processes. The synchronization and exclusion problems associated with implementing multiway rendezvous are expressed succinctly in the context of the committee coordination problem. A variety of techniques to solve the synchronization and exclusion problems may be combined to design algorithms for the committee coordination problem. This paper presents a simple solution for the problem and shows how it can be implemented to develop a family of algorithms. The algorithms use message counts to solve synchronization and solve the exclusion problem by using a circulating token, or by using auxiliary resources as in the solutions for the dining or drinking philosophers problems. The paper also presents the results of a simulation study on the performance of the algorithms. The experiments measured the response time and message complexity of each algorithm as a result of variations in different model parameters including network topology and level of conflict in the system. The results from the study show that the response time for algorithms proposed in this paper is significantly better than an existing algorithm, whereas the message complexity is considerably worse. [ABSTRACT FROM AUTHOR]

This paper investigates how the use of a new data structure, the codeword, can help improve the performance of quicksort when the records to be sorted are long and the keys are alphanumeric sequences of bytes. The codeword is a compact representation of a key with respect to some codeword generator. It consists of a byte for a character count of "equal" bytes, a byte for the "first nonequal" byte, and a pointer to the record. The paper shows how the ordering of keys is preserved by an adequate choice of the code generator and how this can be applied to the quicksort algorithm. An analysis of the potential savings on various architectures and actual measurements show the improvements that can be attained by using codewords rather than pointers. Architecturally independent parameters, such as the number of bytes to be compared and the number of swaps, architecture-dependent parameters such as caches and their write policies, and compiler optimizations such as in-line expansion and register allocation are considered. [ABSTRACT FROM AUTHOR]

The analysis and execution of partial algorithm descriptions is an important part of the algorithm design process (as is borne out by studying the behavior of human algorithm designers). In this paper, we describe a language for representing partially designed algorithms and a process, developmental evaluation, that can discover useful knowledge to guide design. Using these and other results from our research in artificial intelligence, we are building a system, DESIGNER, that automatically designs algorithms. This paper also compares developmental evaluation to execution and analysis techniques used for testing complete programs and for validation of abstract specifications; concepts similar to those found in developmental evaluation are thus shown to apply to all stages of the software life cycle. [ABSTRACT FROM AUTHOR]

Algorithm design is a challenging intellectual activity that provides a rich source of observation and a test domain for a theory of problem-solving behavior. This paper describes a theory of the algorithm design process based on observations of human design and also outlines a framework for automatic design. The adaptation of the theory of human design to a framework for automation in the DESIGNER system helps us understand human design better, and the implementation process helps validate the framework. Issues discussed in this paper include the problem spaces used for design, the loci of knowledge and problem-solving power, and the relationship to other methods of algorithm design and to automatic programming as a whole. [ABSTRACT FROM AUTHOR]

A collection of design patterns was described by Gamma, Helm, Johnson, and Vlissides in 1994. Each pattern ensures that a certain system aspect can vary over time, for example the operations that can be applied to an object or the algorithm of a method. The patterns are described by constructs such as the inheritance and reference relations, attempting to emulate more dynamic relationships. As a result, the design patterns demonstrate how awkward it is to program natural concepts of evolution when using a traditional object- oriented language. In this paper, we present a new relation between classes: the context relation. It directly models dynamic evolution, and it is meaningful at both the design and implementation level. At the design level we extend the Unified Modeling Language (UML) to include the context relation as a new form of arrow between classes. At the implementation level we present a small extension of Java. The context relation introduces a new form of dynamic binding that serves as a replacement to delegation. We demonstrate how the context relation can be used to easily model and program numerous design patterns. [ABSTRACT FROM AUTHOR]

Software libraries are repositories which contain software components; as such, they represent a precious resource for the software engineer. As software libraries grow in size, it becomes increasingly difficult to maintain adequate precision and recall with informal retrieval algorithms. In this paper, we discuss the design and implementation of a storage and retrieval structure for software components that is based on formal specifications and on the refinement ordering between specifications. [ABSTRACT FROM AUTHOR]

This paper describes a new approach to testing that uses combinatorial designs to generate tests that cover the pair- wise, triple, or n-way combinations of a system's test parameters. These are the parameters that determine the system's test scenarios. Examples are system configuration parameters, user inputs and other external events. We implemented this new method in the AETG system. The AETG system uses new combinatorial algorithms to generate test sets that cover all valid n-way parameter combinations. The size of an AETG test set grows logarithmically in the number of test parameters. This allows testers to define test models with dozens of parameters. The AETG system is used in a variety of applications for unit, system, and interoperability testing. It has generated both high-level test plans and detailed test cases. In several applications, it greatly reduced the cost of test plan development. [ABSTRACT FROM AUTHOR]