Recent research has shown that mutational search with appropriate instrumentation can generate short inputs that demonstrate performance issues. Another thread of fuzzing research has shown that substituting subtrees from a forest of derivation trees is an effective grammar-based fuzzing technique for finding deep semantic bugs. We combine performance fuzzing with grammar-based search by generating length-limited derivation trees in which each subtree is labeled with its length. In addition we use performance instrumentation feedback to guide search. In contrast to fuzzing for security issues, for which fuzzing campaigns of many hours or even weeks can be appropriate, we focus on searches that are short enough (up to an hour with modest computational resources) to be part of a routine incremental test process. We have evaluated combinations of these approaches, with baselines including the best prior performance fuzzer. No single search technique dominates across all examples, but both Monte Carlo tree search and length-limited tree hybridization perform consistently well on example applications in which semantic performance bugs can be found with syntactically correct input. In the course of our evaluation we discovered a hang bug in LunaSVG, which the developers have acknowledged and corrected.

TreeLine and SlackLine are grammar-based fuzzers for quickly finding performance problems in programs driven by richly structured text that can be described by context-free grammar. In contrast to long fuzzing campaigns to find (mostly invalid) inputs that trigger security vulnerabilities, TreeLine and SlackLine are designed to search for performance problems in the space of valid inputs in minutes rather than hours. The TreeLine and SlackLine front-ends differ in search strategy (Monte Carlo Tree Search or derivation tree splicing, respectively) but accept the same grammar specifications and rely on a common back-end for instrumented execution. Separation of concerns should facilitate use by other researchers who wish to explore alternatives and extensions of either the front or back ends.

Spatial data are increasingly available, but the ubiquitous use of graphical displays to communicate such data renders it inaccessible to people who are blind or low vision. Not only does this affect the level of access to data, it also results in limited educational opportunities due to a lack of accessible maps and geographic information systems. This lack may be due in part to the challenge of creating a system that provides a usable display without relying on vision. A simple replacement of symbology from a map intended for a two dimensional graphical display with parameters for other modalities such as audio with one primary axis (time) is insufficient.

Software engineering project courses where student teams are geographically distributed can effectively simulate the problems of globally distributed software development (DSD). However, this pedagogical model has proven difficult to adopt or sustain. It requires significant pedagogical resources and collaboration infrastructure. Institutionalizing such courses also requires compatible and reliable teaching partners. The purpose of this workshop is to continue building on our outreach efforts to foster a community of international faculty and institutions committed to developing, teaching and researching DSD. Foundational materials presented will include pedagogical materials and infrastructure developed and used in teaching DSD courses along with results and lessons learned. The third CTGDSD workshop will also focus on publishing workshop results and collaborating with the larger DSD community. Longrange goals include: lowering adoption barriers by providing common pedagogical materials, collaboration infrastructure, and a pool of potential teaching partners from around the globe.

The current generation of dynamic invariant detectors often produce invariants that are inconsistent with program semantics or programmer knowledge. We improve the consistency of dynamically discovered invariants by taking into account higher-level constraints. These constraints encode knowledge about invariants, even when the invariants themselves are unknown. For instance, even though the invariants describing the behavior of two functions f1 and f2 may be unknown, we may know that any valid input for f1 is also valid for f2, i.e., the precondition of f1 implies that of f2. We explore techniques for expressing and employing such consistency constraints to improve the quality of produced invariants. We further introduce techniques for dynamically discovering potential second-order constraints that the programmer can subsequently approve or reject.

Companies around the world routinely distribute their software development across different sites. Students, however, rarely get a chance to learn the potential problems that arise, and the potential solutions to those problems, when conducting distributed development. It is especially difficult to simulate the situation for students when development is distributed across time zones and cultures. We have developed a course that requires teams of students at widely separated universities to collaborate with each other to complete a software development project. Instances of the course have been presented four times using combinations of five different universities, and we are seeking to create a larger pool of universities interested in and capable of presenting it. This paper discusses our goals, the characteristics of the course and the results of teaching it, with a primary result that all the universities want to and will offer the course again.

Computer science graduates face unprecedented opportunities and unforeseen challenges in today's highly global economy. These students will have to work and to think with international perspectives and cultural awareness. In this paper, we report on our experiences organizing and teaching the Pacific Rim Summer Schools in Global Distributed Software Development. We describe the motivation for our focus, our summer school curricula and programs, provide information on the costs of organizing and running the summer schools, and examine the sustainability of our program. We conclude with a discussion of the role of such experiences in computer science curricula and in the education of American and international computer science professionals.

Software engineering project courses where student teams are geographically distributed can effectively simulate the problems of globally distributed software development (DSD). However, this pedagogical model has proven difficult to adopt or sustain. It requires significant pedagogical resources and collaboration infrastructure. Institutionalizing such courses also requires compatible and reliable teaching partners.

SCORE 2011 is the second iteration of a team-oriented software engineering contest that attracts student teams from around the world, culminating in a final round of competition and awards at ICSE. Each team has responded to one of the project proposals provided by the SCORE program committee, usually in the context of a software engineering project course. In this second iteration we have built on the success of SCORE 2009, greatly expanding the number and geographical distribution of student teams, including many of very high quality.

Internationalization of computer science education involves incorporating awareness, knowledge and skills of professional life in a global environment. Through an NSF CPATH1 grant we have established a Pacific Rim community of computer science departments, high tech industry and international programs exploring a new model of computer science education that focuses on the knowledge, skills and competencies necessary for professional success and leadership in a global context. This paper describes our progress in building an international community of computer science educators, as well as our efforts in curricular innovation and establishment of international summer schools. Internationalization of computer science education will help attract the best and brightest students and broaden the appeal of computer science to a much more diverse population. Computer science will be seen as a pathway to a career not in an isolated cubicle but in the wide-open world.

We present the TIC (Transactions with Isolation and Cooperation) model for concurrent programming. TIC adds to standard transactional memory the ability for a transaction to observe the effects of other threads at selected points. This allows transactions to cooperate, as well as to invoke nonrepeatable or irreversible operations, such as I/O. Cooperating transactions run the danger of exposing intermediate state and of having other threads change the transaction's state. The TIC model protects against unanticipated interference by having the type system keep track of all operations that may (transitively) violate the atomicity of a transaction and require the programmer to establish consistency at appropriate points. The result is a programming model that is both general and simple. We have used the TIC model to re-engineer existing lock-based applications including a substantial multi-threaded web mail server and a memory allocator with coarse-grained locking. Our experience confirms the features of the TIC model: It is convenient for the programmer, while maintaining the benefits of transactional memory.

The best approach to testing object-oriented software depends on many factors: the application-under-test, the development approach, the organization of the development and quality assurance teams, the criticality of the application, the development environment and the implementation language(s), the use of design and language features, project timing and resource constraints. Nonetheless, we can outline a general approach that works in stages from independent consideration of classes and their features to consideration of their interactions. A coherent strategy would include three main phases: intraclass, interclass, and system and acceptance testing.

We address the problem of refining and completing a partially specified high-level design model and a partially-defined mapping from source code to design model. This is related but not identical to tasks that have been automated with a variety of reverse engineering tools to support software modification tasks. We posited that set-based flow analysis algorithms would provide a convenient and powerful basis for refining an initial rough model and partial mapping, and in particular that the ability to compute fixed points of set equations would be useful in propagating constraints on the relations among the model, the mapping, and facts extracted from the implementation. Here we report our experience applying this approach to a modest but realistic example problem. We were successful in expressing a variety of useful transformations very succinctly as flow equations, and the propagation of recursively-defined constraints was indeed useful in refining the mapping from implementation to model. On the other hand, our experience highlights remaining challenges to make this an attractive approach for general use. Special measures are required to identify and remove inconsistent constraints before they propagate through a system. Also, while the required flow equations are succinct, they are also rather opaque; it is not obvious how their expressive power might be preserved in a more accessible notation.

Automated finite-state verification techniques have matured considerably in the past several years, but state-space explosion remains an obstacle to their use. Theoretical lower bounds on complexity imply that all of the techniques that have been developed to avoid or mitigate state-space explosion depend on models that are "well-formed" in some way, and will usually fail for other models. This further implies that, when analysis is applied to models derived from designs or implementations of actual software systems, a model of the system "as built" is unlikely to be suitable for automated analysis. In particular, compositional, hierarchical analysis (where state-space explosion is avoided by simplifying models of subsystems at several levels of abstraction) depend on the modular structure of the model to be analyzed. We describe how as-built finite-state models can be refactored for compositional state-space analysis, applying a series of transformations to produce an equivalent model whose structure exhibits suitable modularity. The process is supported by a parser which can parse a subset of Promela syntax and transform Promela code into refactored state graphs.

The past three decades have seen the creation of several tools that extract, visualize, and manipulate graph-structured representations of program information. To facilitate interconnection and exchange of information between these tools, and to support the prototyping and development of new tools, it is desirable to have some generic support for the specification of graph transformations and exchanges between them.GenSet is a generic programmable tool for transformation of graph-structured data. The implementation of the GenSet system and the programming paradigm of its language are both based on the view of a directed graph as a binary relation. Rather than use traditional relational algebra to specify transformations, however, we opt instead for the more expressive class of flow equations. Flow equations---or, more generally, systems of simultaneous fixpoint equations---have seen fruitful applications in several areas, including data and control flow analysis, formal verification, and logic programming. In GenSet, they provide the fundamental construct for the programmer to use in defining new transformations.

We describe an extension to the Java programming language that supports static conformance checking and dynamic debugging of object “protocols,” i.e., sequencing constraints on the order in which methods may be called. Our Java protocols have a statically checkable subset embedded in richer descriptions that can be checked at run time. The statically checkable subtype conformance relation is based on Nierstrasz' proposal for regular (finite-state) process types, and is also very close to the conformance relation for architectural connectors in the Wright architectural description language by Allen and Garlan. Richer sequencing properties, which cannot be expressed by regular types alone, can be specified and checked at run time by associating predicates with object states. We describe the language extensions and their rationale, and the design of tool support for static and dynamic checking and debugging.

Structural coverage criteria are often used as an indicator of the thoroughness of testing, but complete satisfaction of a criterion is seldom achieved.When a software product is released with less than 100% coverage, testers are explicitly or implicitly assuming that executions satisfying the remaining test obligations (the residue) are either infeasible or occur so rarely that they have negligible impact on quality.Violation of this assumption indicates shortcomings in the testing process.Monitoring in the deployed environment, even in the beta test phase, is typically limited to error and sanity checks.Monitoring the residue of test coverage in actual use can provide additional useful information, but it is unlikely to be accepted by users unless its performance impact is very small.Experience with a prototype tool for residual test coverage monitoring of Java programs suggests that, at least for statement coverage, the simple strategy of removing all probes except those corresponding to the residue of coverage testing reduces execution overhead to acceptably low levels.

State-space analysis techniques have been developed for several representations of concurrent systems, but each tool or technique has typically been targeted to a single design or program notation.We describe an approach to constructing multi-formalism state-space analysis tools for heterogeneous system descriptions, using a shared "inframodel" that represents only the essential information for interpretation by tool components that can be customized to reflect the semantics of each formalism.The (operational) semantics of each formalism, as well as interactions between components described in different formalisms, is described separately through rules governing enabling, matching, and firing of transitions.This results in more natural and compact internal representations, and more efficient analysis, than a purely translational approach.In a previous paper, execution semantics of the inframodel was controlled through a limited set of parameters.The rulebased approach described in this paper accomodates a wider range of state-transition formalisms.

No abstract available.

As software evolves from early architectural sketches to final code, a variety of representations are appropriate. Moreover, at most points in development, different portions of a software system are at different stages in development, and consequently in different representations. State-space analysis techniques (reachability analysis, model checking, simulation, etc.) have been developed for several representations of concurrent systems, but each tool or technique has typically been targeted to a single design or program notation.We describe an approach to constructing space analysis tools using a core set of basic representations and components. Such a tool generation approach differs from translation to a common formalism. We need not map every supported design formalism to a single internal form that completely captures the original semantics; rather, a shared "inframodel" represents only the essential information for interpretation by tool components that can be customized to reflect the semantics of each formalism. This results in more natural and compact internal representations, and more efficient analysis, than a purely translational approach.We illustrate the approach by applying the prototype tool to a small example problem, coordination of access to a coffee machine. The coffee machine is controlled by an Ada program, and the protocol of human users is modeled with Petri nets. Nets and process graph models are represented in the common internal form, and their composite behavior is analyzed by the prototype tool.

A concurrent program fault can propagate both within a single task (thread of control) and between tasks, making fault localization difficult. We propose a two-dimensional approach and supporting techniques for integrating analysis of task interactions, inter- and intra-task data flow, and conventional sequential debugging of individual tasks. We define augmented concurrent dynamic slice, a variant of dynamic slice, which balances the cost and accuracy for concurrent program debugging and permits adjustment of that balance and focus on small parts of large complex systems. We also describe the design and implementation of prototype tools which add concurrent slicing capability to an existing debugger.

The problem of analyzing concurrent systems has been investigated by many researchers, and several solutions have been proposed. Among the proposed techniques, reachability analysis—systematic enumeration of reachable states in a finite-state model—is attractive because it is conceptually simple and relatively straightforward to automate and can be used in conjunction with model-checking procedures to check for application-specific as well as general properties. This article shows that the nature of the translation from source code to a modeling formalism is of greater practical importance than the underlying formalism. Features identified as pragmatically important are the representation of internal choice, selection of a dynamic or static matching rule, and the ease of applying reductions. Since combinatorial explosion is the primary impediment to application of reachability analysis, a particular concern in choosing a model is facilitating divide-and-conquer analysis of large programs. Recently, much interest in finite-state verification systems has centered on algebraic theories of concurrency. Algebraic structure can be used to decompose reachability analysis based on a flowgraph model. The semantic equivalence of graph and Petri net-based models suggests that one ought to be able to apply a similar strategy for decomposing Petri nets. We describe how category-theoretic treatments of Petri nets provide a basis for decomposition of Petri net reachability analysis.

Cats (Concurrency Analysis Tool Suite) is designed to satisfy several criteria: it must analyze implementation-level Ada source code and check user-specified conditions associated with program source code; it must be modularized in a fashion that supports flexible composition with other tool components, including integration with a variety of testing and analysis techniques; and its performance and capacity must be sufficient for analysis of real application programs. Meeting these objectives together is significantly more difficult than meeting any of them alone. We describe the design and rationale of Cats and report experience with an implementation. The issues addressed here are primarily practical concerns for modularizing and integrating tools for analysis of actual source programs. We also report successful application of Cats to major subsystems of a (nontoy) highly concurrent user interface system.

Concurrent systems are inherently more difficult to analyze and visualize than sequential programs. The difficulty of producing correct concurrent programs is mirrored in maintenance as difficulty in extracting a correct high-level model of task interactions and predicting the effect of a modification to portions of a system. We advocate a methodology that combines static analysis of an abstract model with dynamic analysis of source code. While the abstract model is is amenable to exhaustive analysis, dynamic analysis is capable checking richer classes of specifications, and moreover provides a check on the correctness of simplifications and assumptions inherent in abstract models. We illustrate this approach by combining two tools, the PAL system for compositional reachability analyses and the FORESEE analysis tool for temporal analysis of runtime traces, applied to a simulation scenario.>

Non-determinism makes testing concurrent software difficult. We consider how pre-run-time state-space analysis can be used to aid in testing implementations of concurrent software. State-space analysis techniques have the advantage in principle of exploring all possible execution histories, but they do not verify all properties of interest and in practice they may not accurately model program execution. Combining state-space analysis with testing can partially overcome the weaknesses of each. Using the state-space model in a test oracle is the simpler part: techniques based on classical automata theory are suitable for this. Covering all important non-deterministic executions is harder. We propose a pragmatic method for detecting unexecuted paths that are certainly executable and possibly important.

Abstract In previous publications the authors described a compositional (hierarchical) approach to reachability analysis of Ada tasking programs based on process algebra. The abstraction capabilities of process algebra provide an effective means to control state explosion in automated state‐space analysis, but only if a design is carefully modularized to encapsulate details of behaviour. This paper reports experience modifying an existing design (a remote temperature sensor system described by Sanden) to make it more amenable to hierarchical analysis. Redesign for analysis was effective in improving the design in other ways as well: flaws uncovered in the analysis (and present in the original design) were easy to understand and correct because of the increased understandability of the revised design. This also suggests that these flaws might have been avoided, and the design generally improved, had ‘design for analysis’ been applied from the start.

The conventional classification of software fault detection techniques as static or dynamic analysis is inadequate as a basis for identifying useful relationships between techniques. A more useful distinction is between techniques that sample the space of possible executions, and techniques that fold the space. The new distinction provides better insight into the ways different techniques can interact, and is a basis for considering hybrid fault detection techniques including combinations of testing and formal verification. Keywords: Fault detection, hybrid analysis techniques, static analysis, dynamic analysis. An earlier version of this paper appeared in Proceedings of the 11th International Conference on Software Engineering, Pittsburgh, May 1989. Address correspondence to the first author at Department of Computer Sciences, Purdue University, West Lafayette, IN 47907. Email: [email protected]. Phone: (317) 494-6023. This work was supported in part by the National Science Foundat...

Static concurrency analysis detects anomalous synchronization patterns in concurrent programs, but may also report spurious errors involving infeasible execution paths. Integrated application of static concurrency analysis and symbolic execution sharpens the results of the former without incurring the full costs of the latter when applied in isolation. Concurrency analysis acts as a path selection mechanism for symbolic execution, while symbolic execution acts as a pruning mechanism for concurrency analysis. Methods of combining the techniques follow naturally from explicit characterization and comparison of the state spaces explored by each, suggesting a general approach for integrating state-based program analysis techniques in a software development environment.>

The authors discuss the demands and constraints on a user interface management system for a software environment, and the relation between the architecture of the environment and the user interface management system. A model for designing user interface management systems for large extensible environments is presented. This model synthesizes several recent advances in user interfaces and specializes them to the domain of software environments. The model can be applied to a wide variety of environment contexts. A prototype implementation is described.>