IEEE Transactions on Software Engineering

PrePrint: Generating Event Sequence-Based Test Cases Using GUI Run-Time State Feedback

This paper presents a fully automatic model-driven technique to generate test cases for Graphical user interface-based applications (GUIs). The technique uses feedback from the execution of a "seed test suite," which is generated automatically using an existing structural event-interaction graph model of the GUI. During its execution, the run-time effect of each GUI event on all other events pinpoints event-semantic interaction (ESI) relationships, which are used to automatically generate new test cases. Two studies on eight applications demonstrate that the feedback-based technique (1) is able to significantly improve existing techniques and help identify serious problems in the software and (2) the ESI relationships captured via GUI state yield test suites that most often detect more faults than their code-, event-, and event-interaction-coverage equivalent counterparts.

PrePrint: Better Debugging via Output Tracing and Callstack-Sensitive Slicing

Debugging often involves (1) finding the point of failure (the first statement that produces bad output), and (2) finding and fixing the actual bug. Print statements and debugger breakpoints can help with step 1. Slicing the program back from values used at the point of failure can help with step 2. However, neither approach is ideal: debuggers and print statements can be clumsy and time-consuming, and backward slices can be almost as large as the original program. This paper addresses both problems. We present callstack-sensitive slicing, which reduces slice sizes by leveraging the series of calls active when a program fails. We also show how slice intersections may further reduce slice sizes. We then describe a set of tools that identify points of failure for programs that produce bad output. Finally, we apply our point-of-failure tools to a suite of buggy programs and evaluate callstack-sensitive slicing and slice intersection as applied to debugging. Callstack-sensitive slicing is very effective: on average, a callstack-sensitive slice is about 0.31 times the size of the corresponding full slice, down to just 0.06 times in the best case. Slice intersection is less impressive on average, but may sometimes prove useful in practice.

PrePrint: Grammar Recovery from Parse Trees and Metrics-Guided Grammar Refactoring

Many software development tools that assist with tasks such as testing and maintenance are specific to a particular development language and require a parser for that language. Because a grammar is required to develop a parser, construction of these software development tools is dependent upon the availability of a grammar for the development language. However, a grammar is not always available for a language, and in these cases, acquiring a grammar is the most difficult, costly, and time-consuming phase of tool construction. In this paper we describe a methodology for grammar recovery from a hard-coded parser. Our methodology comprises manual instrumentation of the parser, a technique for automatic grammar recovery from parse trees, and a semi-automatic metrics-guided approach to refactoring an iterative grammar to obtain a recursive grammar. We present the results of a case study in which we recover and refactor a grammar from version 4.0.0 of the GNU C++ parser and then refactor the recovered grammar using our metrics-guided approach. Additionally, we present an evaluation of the recovered and refactored by comparing it to the ISOC++98 grammar.

PrePrint: Engineering A Sound Assertion Semantics for the Verifying Compiler

The Verifying Compiler (VC) project is a core component of the Dependable Systems Evolution Grand Challenge. The VC offers the promise of automatically proving that a program or component is correct, where correctness is defined by program assertions. While several VC prototypes exist, all adopt a semantics for assertions that is unsound. This paper presents a consolidation of VC requirements analysis activities that, in particular, brought us to ask targeted VC customers what kind of semantics they wanted. Taking into account both practitioners’ needs and current technological factors, we offer recovery of soundness through an adjusted definition of assertion validity that matches user expectations and can be implemented practically using current prover technology. For decades there have been debates concerning the most appropriate semantics for program assertions. Our contribution here is unique in that we have applied fundamental software engineering techniques by asking primary stakeholders what they want and based on this, proposed a means of efficiently realizing the semantics stakeholders want using standard tools and techniques. We describe how support for the new semantics has been added to ESC/Java2, one of the most fully developed VC prototypes. Case studies demonstrate the effectiveness of the new semantics at uncovering previously indiscernible specification errors.

PrePrint: Stressing Search with Scenarios for Flexible Solutions to Real-Time Task Allocation Problems

One of the most important properties of a good software engineering process and of the design of the software it produces is robustness to changing requirements. Scenario-based analysis is a popular method for improving the flexibility of software architectures. This paper demonstrates a search-based technique for automating scenario-based analysis in the software architecture deployment view. Specifically, a novel parallel simulated annealing search algorithm is applied to the real-time task allocation problem to find baseline solutions which require a minimal number of changes in order to meet the requirements of potential upgrade scenarios. Another simulated annealing based search is used for finding a solution which is similar to an existing baseline when new requirements arise. Solutions generated using a variety of scenarios are judged by how well they respond to different system requirements changes. The evaluation is performed on a set of problems with a controlled set of different characteristics.

PrePrint: Directed Explicit State-Space Search in the Generation of Counterexamples for Stochastic Model Checking

Current stochastic model checkers do not make counterexamples for property violations readily available. In this paper we apply directed explicit state space search to discrete- and continuous-time Markov chains in order to compute counterexamples for the violation of PCTL or CSL properties. Directed explicit state space search algorithms explore the state space on-the-fly which makes our method very efficient and highly scalable. They can also be guided using heuristics which usually improve the performance of the method. Counterexamples provided by our method have two important properties. First, they include those traces which contribute the most amount of probability to the property violation. Hence, they show the most probable offending execution scenarios of the system. Second, the obtained counterexamples tend to be small. Hence, they can be effectively analyzed by a human user. Both properties make the counterexamples obtained by our method very useful for debugging purposes. We implemented our method based on the stochastic model checker PRISM and applied it to a number of case studies in order to illustrate its applicability.

PrePrint: Bayesian Approaches to Matching Architectural Diagrams

IT system architectures and many other kinds of structured artifacts are often described by formal models or informal diagrams. In practice, there are often a number of versions of a model or diagram, such as a series of revisions, divergent variants, or multiple views of a system. Understanding how versions correspond or differ is crucial, and thus automated assistance for matching models and diagrams is essential. We have designed a framework for finding these correspondences automatically based on Bayesian methods. We represent models and diagrams as graphs whose nodes have attributes such as name, type, connections to other nodes, and containment relations, and we have developed probabilistic models for rating the quality of candidate correspondences based on various features of the nodes in the graphs. Given the probabilistic models, we can find high quality correspondences using search algorithms. Preliminary experiments focusing on architectural models suggest that the technique is promising.

PrePrint: Service-Level Agreements for Electronic Services

The potential of communication networks and middleware to enable the composition of services across organisational boundaries remains incompletely realised. In this paper we argue that this is in part due to outsourcing risks, and describe the possible contribution of Service-Level Agreements (SLAs) to mitigating these risks. For SLAs to be effective, it should be difficult to disregard their original provisions in the event of a dispute between the parties. Properties of understandability, precision and monitorability ensure that the original intent of an SLA can be recovered, and compared to trustworthy accounts of service behaviour to resolve disputes fairly and without ambiguity. We describe the design and evaluation of a domain-specific language for SLAs that tend to exhibit these properties, and discuss the impact of monitorability requirements on service provision practices.

PrePrint: Reverse Engineering Input Syntactic Structure from Program Execution and Its Applications

Program input syntactic structure is essential for a wide range of applications such as test case generation, software debugging and network security. However, such important information is often not available (e.g., most malware programs make use of secret protocols to communicate) or not directly usable by machines (e.g., many programs specify their inputs in plain text or other random formats). Furthermore, many programs claim they accept inputs with a published format, but their implementations actually support a subset or a variant. Based on the observations that input structure is manifested by the way input symbols are used during execution and most programs take input with top-down or bottom-up grammars, we devise two dynamic analyses, one for each grammar category. Our evaluation on a set of real-world programs shows that our technique is able to precisely reverse engineer input syntactic structure from execution. We apply our technique to hierarchical delta debugging (HDD) and network protocol reverse engineering. Our technique enables the complete automation of HDD, in which programmers were originally required to provide input grammars, and improves the runtime performance of HDD. Our client study on network protocol reverse engineering also shows that our technique supersedes existing techniques.

PrePrint: An Experience in Testing the Security of Real-World Electronic Voting Systems

Voting is the process through which a democratic society determines its government. Therefore, voting systems are as important as other well-known critical systems, such as air traffic control systems or nuclear plant monitors. Unfortunately, voting systems have a history of failures that seems to indicate that their quality is not up to the task. Because of the alarming frequency and impact of these malfunctions, in recent years a number of vulnerability analysis exercises have been carried out against voting systems to determine if their confidentiality, integrity, and availability can be compromised. We have participated in two such large-scale projects, sponsored by the Secretaries of State of California and Ohio, in which the electronic voting machines used in those two states were tested. In our testing, we identified major flaws and implemented a number of attacks, which allowed us to take complete control of the examined voting systems. As a result of these evaluations, the Secretaries of State recommended changes to improve the security of the voting process. In this paper, we describe the methodology that we used in testing the two real-world electronic voting systems we evaluated, the findings of our analysis, our system-wide attacks, and the lessons we learned.

PrePrint: A Systematic Review of the Application and Empirical Investigation of Search-Based Test-Case Generation

Metaheuristic search techniques have been extensively used to automate the process of generating test cases and thus providing solutions for a more cost-effective testing process. This approach to test automation, often coined as “Search-based Software Testing” (SBST), has been used for a wide variety of test case generation purposes. Since SBST techniques are heuristic by nature, they must be empirically investigated in terms of how costly and effective they are at reaching their test objectives and whether they scale up to realistic development artifacts. However, approaches to empirically study SBST techniques have shown wide variation in the literature. This paper presents the results of a systematic, comprehensive review that aims at characterizing how empirical studies have been designed to investigate SBST cost-effectiveness and what empirical evidence is available in the literature regarding SBST cost-effectiveness and scalability. We also provide a framework that drives the data collection process of this systematic review and can be the starting point of guidelines on how SBST techniques can be empirically assessed. The intent is to aid future researchers doing empirical studies in SBST by providing an unbiased view of the body of empirical evidence and by guiding them in performing well designed empirical studies.

PrePrint: Providing Architectural Languages and Tools Interoperability through Model Transformation Technologies

Many architectural languages have been proposed in the last fifteen years, each one with the chief aim of becoming the ideal language for specifying software architectures. What is evident nowadays, instead, is that architectural languages are defined by stakeholder concerns. Capturing all such concerns within a single, narrowly focused notation is impossible. At the same time it is also impractical to define and use a “universal” notation, such as UML. As a result, many domain specific notations for architectural modeling have been proposed, each one focussing on a specific application domain, analysis type, or modeling environment. As a drawback, a proliferation of languages exists, each one with its own specific notation, tools, and domain specificity. No effective interoperability is possible to date. Therefore, if a software architect has to model a concern not supported by his own language/tool, he has to manually transform (and eventually keep aligned) the available architectural specification into the required language/tool. This paper presents DUALLY, an automated framework that allows architectural languages and tools interoperability. Given any number of architectural languages and tools, they can all interoperate thanks to automated model transformation techniques. DUALLY is implemented as an Eclipse plugin.

PrePrint: DECOR: A Method for the Specification and Detection of Code and Design Smells

Code and design smells are poor solutions to recurring implementation and design problems. They may hinder the evolution of a system by making it hard for software engineers to carry out changes. We propose three contributions to the research field related to code and design smells: (1) DECOR, a method that embodies and defines all the steps necessary for the specification and detection of code and design smells; (2) DETEX, a detection technique that instantiates this method; and (3) an empirical validation in terms of precision and recall of DETEX. The originality of DETEX stems from the ability for software engineers to specify smells at a high-level of abstraction using a consistent vocabulary and domain-specific language for automatically generating detection algorithms. Using DETEX, we specify four well-known design smells: the antipatterns Blob, Functional Decomposition, Spaghetti Code, and Swiss Army Knife, and their 15 underlying code smells, and we automatically generate their detection algorithms. We apply and validate the detection algorithms in terms of precision and recall on XERCES v2.7.0, and discuss the precision of these algorithms on 11 opensource systems.

PrePrint: Software Dependencies, Work Dependencies, and Their Impact on Failures

Prior research has shown that customer reported software faults are often the result of violated dependencies that are not recognized by developers implementing software. Many types of dependencies and corresponding measures have been proposed to help address this problem. The objective of this research is to compare the relative performance of several of these dependency measures as they relate to customer reported defects. Our analysis is based on data collected from two projects from two independent companies. Combined, our data set encompasses eight years of development activity involving 154 developers. The principal contribution of this study is the examination of the relative impact that syntactic, logical and work dependencies have on the failure proneness of a software system. While all dependencies increase the fault proneness, the logical dependencies explained most of the variance in fault proneness, while workflow dependencies had more impact than syntactic dependencies. These results suggest that practices such as re-architecting, guided by the network structure of logical dependencies, holds promise for reducing defects.

PrePrint: Effects of Personality on Pair Programming

Personality tests in various guises are commonly used in recruitment and career counseling industries. Such tests have also been considered as instruments for predicting the job performance of software professionals both individually and in teams. However, research suggests that other human-related factors, such as motivation, general mental ability, expertise and task complexity also affect performance in general. This paper reports on a study of the impact of the Big Five personality traits on the performance of pair programmers together with the impact of expertise and task complexity. The study involved 196 software professionals in three countries forming 98 pairs. The analysis consisted of a confirmatory part and an exploratory part. The results show that (1) our data does not confirm a meta-analysis-based model of the impact of certain personality traits on performance; and (2) personality traits in general havemodest predictive value on pair programming performance compared with expertise, task complexity, and country. We conclude that more effort should be spent on investigating other performance-related predictors such as expertise, and task complexity, as well as other promising predictors, such as programming skill and learning.

PrePrint: FAML: A Generic Metamodel for MAS Development

In some areas of Software Engineering research, there are several metamodels claiming to capture the main issues. Though it is profitable to have variety at the beginning of a research field, after some time the diversity of metamodels becomes an obstacle, for instance to the sharing of results between research groups. To reach consensus and unification of existing metamodels, metamodel-driven software language engineering can be applied. This paper illustrates an application of software language engineering in the agent-oriented software engineering research domain. Here, we introduce a relatively-generic agent-oriented metamodel whose suitability for supporting modelling language development is demonstrated by evaluating it with respect to several existing methodology-specific metamodels. Firstly, the metamodel is constructed by a combination of bottom-up and top-down analysis and best practice. The concepts thus obtained and their relationships are then evaluated by mapping to two agent-oriented metamodels: TAO and Islander. We then refine the metamodel by extending the comparisons with the metamodels implicit or explicit within five more extant agent-oriented approaches: Adelfe, PASSI, Gaia, INGENIAS and Tropos. The resultant FAML metamodel is a potential candidate for future standardization as an important component for engineering an agent modelling language.

PrePrint: A Flexible Infrastructure for Multilevel Language Engineering

Although domain specific modeling tools have come a long way since the modern era of model-driven development started in the early 90s, and now offer an impressive range of features, there is still significant room for enhancing the flexibility they offer to end users and for combining the advantages of domain-specific and general purpose languages. To do this, however, it is necessary to enhance the way in which the current generation of tools view metamodeling and support the representation of multiple, “ontological” classification levels that often exist in domains. State-of-the-art DSM tools essentially allow users to describe the abstract and concrete syntaxes of a language in the form of metamodels, and to make statements in that language in the form of models. These statements typically convey information in terms of types and instances in the domain (e.g the classes and objects of UML), but not in terms of types of types (i.e. domain metaclasses), and types of types of types and so on, across multiple classification levels. In essence, therefore, while they provide rich, support for linguistic metamodeling, the current generation of tools provide little if any built-in support for modeling “ontological” classification across more than one type/instance level in the subject domain. to be continued

PrePrint: Engineering of Framework-Specific Modeling Languages

Framework-specific modeling languages (FSMLs) help developers build applications based on object-oriented frameworks. FSMLs model abstractions and rules of a framework's application programming interfaces (APIs) and can express models of how applications use APIs. Such models aid developers in understanding, creating, and evolving application code. We present four exemplar FSMLs and a method for engineering new FSMLs that was created post-mortem by generalizing the experience of building the exemplar languages and by specializing existing approaches to domain analysis, software development, and model and language quality evaluation. The method is driven by the use cases that the FSML under development should support and the evaluation of the FSML is guided by two quality frameworks. The method description provides concrete examples for the engineering steps, outcomes, and challenges. It also provides strategies for making engineering decisions. The presented method and experience are aimed at framework developers and tool builders who are interested in engineering new FSMLs. Furthermore, the method represents a necessary step in the maturation of the FSML approach. Finally, the presented work offers a concrete example of software language engineering and its benefits. FSMLs capture existing domain knowledge in language form and enable application code generation, application code understanding through reverse engineering, and application code evolution through round-trip engineering.

PrePrint: A Model-Based Approach to Families of Embedded Domain-Specific Languages

With the emergence of model driven engineering, the creation of domain specific languages (DSL) is becoming a fundamental part of language engineering. The development cost of a DSL should be modest, compared to the cost of developing a general-purpose programming language. Reducing the implementation effort and providing reuse techniques are key aspects for DSL approaches to be really effective. In this paper we present an approach to build embedded domain specific languages applying the principles of model driven engineering (MDE). On the basis of this approach we will tackle reuse of DSLs by defining families of DSLs, addressing reuse both from the DSL developer and user point of views. A family of DSLs will be built up by composing several DSLs, so we will propose composition mechanisms for the abstract syntax, concrete syntax and model transformation levels of a DSL's definition. Finally, we contribute a software framework to support our approach, and we illustrate the paper with a case study to demonstrate its practical applicability.