At present 12 students are registered + 1 auditing
so 24 to 26 papers will be presented (four each).
- Adrion+Branstad+Cherniavsky1982-vvtc
- W. Richards Adrion, Martha A. Branstad, and John C. Cherniavsky.
Validation, Verification, and Testing of Computer Software.
ACM Comput. Surv., 14(2):159-192, 1982.
Abstract:
Software quality is achieved through the application of development techniques and the use of verification procedures throughout the development process. Careful consideration of specific quality attributes and validation requirements leads to the selection of a balanced collection of review, analysis, and testing techniques for use throughout the life cycle. This paper surveys current verification, validation, and testing approaches and discusses their strengths, weaknesses, and life-cycle usage. In conjunction with these, the paper describes automated tools used to implement validation, verification, and testing. In the discussion of new research thrusts, emphasis is gwen to the continued need to develop a stronger theoretical basis for testing and the need to employ combinations of tools and techniques that may vary over each application.
- Bertolino2003-strp
- Antonia Bertolino.
Software testing: research and practice.
In Proceedings of the 10th International Workshop on Abstract State Machines, Advances in Theory and Practice (ASM'2003), pp. 1-21.
Springer, 2003.
- Clarke+Podgurski+1989-fedf
- L. A. Clarke, A. Podgurski, D. J. Richardson, and S. J. Zeil.
A Formal Evaluation of Data Flow Path Selection Criteria.
IEEE Transactions on Software Engineering, 15(11):1318-1332, 1989.
Abstract:
The authors report on the results of their evaluation of path-selection criteria based on data-flow relationships. They show how these criteria relate to each other, thereby demonstrating some of their strengths and weaknesses. A subsumption hierarchy showing their relationship is presented. It is shown that one of the major weaknesses of all the criteria is that they are based solely on syntactic information and do not consider semantic issues such as infeasible paths. The authors discuss the infeasible-path problem as well as other issues that must be considered in order to evaluate these criteria more meaningfully and to formulate a more effective path-selection criterion
- Dwyer+Clarke1996-fabd
- Matthew B. Dwyer and Lori A. Clarke.
A flexible architecture for building data flow analyzers.
In Proceedings of the 18th International Conference on Software Engineering, pp. 554-564.
IEEE Computer Society Press, Mar. 1996.
Abstract:
Data flow analysis is a versatile technique that can be used to address a variety of analysis problems. Typically, data flow analyzers are hand-crafted to solve a particular analysis problem. The cost of constructing analyzers can be high and is a barrier to evaluating alternative analyzer designs. We describe an architecture that facilitates the rapid prototyping of data flow analyzers. With this architecture, a developer chooses from a collection of pre-existing components or, using high-level component generators, constructs new components and combines them to produce a data flow analyzer. In addition to support for traditional data flow analysis problems, this architecture supports the development of analyzers for a class of combined data flow problems that offer increased precision. This architecture allows developers to investigate quickly and easily a wide variety of analyzer design alternatives and to understand the practical design tradeoffs better. We describe our experience using this architecture to construct a variety of different data flow analyzers.
- Fosdick+Osterweil1976-dfas
- Lloyd D. Fosdick and Leon J. Osterweil.
Data Flow Analysis in Software Reliability.
ACM Comput. Surv., 8(3):305-330, 1976.
Abstract:
The ways that the methods of data flow analysis can be applied to improve software reliability are described. There is also a review of the basic terminology from graph theory and from data flow analysis in global program optimization. The notation of regular expressions is used to describe actions on data for sets of paths. These expressions provide the basis of a classification scheme for data flow which represents patterns of data flow along paths within subprograms and along paths which cross subprogram boundaries. Fast algorithms, originally introduced for global optimization, are described and it is shown how they can be used to implement the classification scheme. It is then shown how these same algorithms can also be used to detect the presence of data flow anomalies which are symptomatic of programming errors. Finally, some characteristics of and experience with DAVE, a data flow analysis system embodying some of these ideas, are described.
- Goel1985-srma
- Amrit L. Goel.
Software Reliability Models: Assumptions, Limitations, and Applicability.
IEEE Transactions on Software Engineering, SE-11(12):1411-23, Dec., 1985.
Abstract:
A number of analytical models have been proposed during the past 15 years for assessing the reliability of a software system. The author presents an overview of the key modeling approaches, provides a critical analysis of the underlying assumptions, and assesses the limitations and applicability of those models during the software development cycle. He also proposes a step-by-step procedure for fitting a model and illustrates it via an analysis of failure data from a medium-sized real-time command and control software system (48 Refs.)
- Goodenough+Gerhart1975-tttd-icrs
- John B. Goodenough and Susan L. Gerhart.
Toward a theory of test data selection.
In Proceedings of the International Conference on Reliable Software, pp. 493-510.
1975.
Abstract:
This paper examines the theoretical and practical role of testing in software development. We prove a fundamental theorem showing that properly structured tests are capable of demonstrating the absence of errors in a program. The theorem's proof hinges on our definition of test reliability and validity, but its practical utility hinges on being able to show when a test is actually reliable. We explain what makes tests unreliable (for example, we show by example why testing all program statements, predicates, or paths is not usually sufficient to insure test reliability), and we outline a possible approach to developing reliable tests. We also show how the analysis required to define reliable tests can help in checking a program's design and specifications as well as in preventing and detecting implementation errors.
- Harman+Binkley+Danicic2003-aps
- Mark Harman, David Binkley, and Sebastian Danicic.
Amorphous program slicing.
J. Syst. Softw., 68(1):45-64, 2003.
Abstract:
Traditional, syntax-preserving program slicing simplifies a program by deleting components (e.g., statements and predicates) that do not affect a computation of interest. Amorphous slicing removes the limitation to component deletion as the only means of simplification, while retaining the semantic property that a slice preserves the selected behaviour of interest from the original program. This leads to slices which are often considerably smaller than their syntax-preserving counterparts.A formal framework is introduced to define and compare amorphous and traditional program slicing. After this definition, an algorithm for computing amorphous slices, based on the system dependence graph, is presented. An implementation of this algorithm is used to demonstrate the utility of amorphous slicing with respect to code-level analysis of array access safety. The resulting empirical study indicates that programmers' comprehension of array safety is improved by amorphous slicing.
- Hassan2006-msra
- Ahmed E. Hassan.
Mining Software Repositories to Assist Developers and Support Managers.
In ICSM '06: Proceedings of the 22nd IEEE International Conference on Software Maintenance, pp. 339-342.
2006.
Abstract:
Software repositories (such as source control repositories) contain a wealth of valuable information regarding the evolutionary history of a software project. This dissertation presents approaches and tools which mine and transform static record keeping software repositories to active repositories used by researchers to gain empirically based understanding of software development, and by practitioners to predict, plan and understand various aspects of their project. Our work is validated empirically using data based on over 60 years of development history for several open source projects.
- Jackson1995-adba
- Daniel Jackson.
Aspect: detecting bugs with abstract dependences.
ACM Trans. Softw. Eng. Methodol., 4(2):109-145, 1995.
Abstract:
Aspect is a static analysis technique for detecting bugs in imperative programs, consisting of an annotation language and a checking tool. Like a type declaration, an Aspect annotation of a procedure is a kind of declarative, partial specification that can be checked efficiently in a modular fashion. But instead of constraining the types of arguments and results, Aspect specifications assert dependences that should hold between inputs and outputs. The checker uses a simple dependence analysis to check code against annotations and can find bugs automatically that are not detectable by other static means, especially errors of omission, which are common, but resistant to type checking. This article explains the basic scheme and shows how it is elaborated to handle data abstraction and aliasing.
- Kazman+Bass+2005-basa
- Rick Kazman, Len Bass, Mark Klein, Tony Lattanze, and Linda Northrop.
A Basis for Analyzing Software Architecture Analysis Methods.
Software Quality Control, 13(4):329-355, 2005.
Abstract:
A software architecture is a key asset for any organization that builds complex software-intensive systems. Because of an architecture's central role as a project blueprint, organizations should analyze the architecture before committing resources to it. An analysis helps to ensure that sound architectural decisions are made. Over the past decade a large number of architecture analysis methods have been created, and at least two surveys of these methods have been published. This paper examines the criteria for analyzing architecture analysis methods, and suggests a new set of criteria that focus on the essence of what it means to be an architecture analysis method. These criteria could be used to compare methods, to help understand the suitability of a method, or to improve a method. We then examine two methods-the Architecture Tradeoff Analysis Method and Architecture-level Modifiability Analysis-in light of these criteria, and provide some insight into how these methods can be improved.
- Ko+Myers2008-draa
- Andrew J. Ko and Brad A. Myers.
Debugging Reinvented: Asking and Answering Why and Why Not Questions about Program Behavior.
In 28th International Conference on Software Engineering (ICSE '08), May 2008.
Abstract:
When software developers want to understand the reason for a program's behavior, they must translate their questions about the behavior into a series of questions about code, speculating about the causes in the process. The Whyline is a new kind of debugging tool that avoids such speculation by instead enabling developers to select a question about program output from a set of why did and why didn't questions derived from the program's code and execution. The tool then finds one or more possible explanations for the output in question, using a combination of static and dynamic slicing, precise call graphs, and new algorithms for determining potential sources of values and explanations for why a line of code was not reached. Evaluations of the tool on one task showed that novice programmers with the Whyline were twice as fast as expert programmers without it. The tool has the potential to simplify debugging in many software development contexts.
- (In class dropbox)
- Marcus+Maletic2003-rdts
- Andrian Marcus and Jonathan I. Maletic.
Recovering documentation-to-source-code traceability links using latent semantic indexing.
In 25th International Conference on Software Engineering (ICSE '03), pp. 125-135.
May 2003.
Abstract:
An information retrieval technique, latent semantic indexing, is used to automatically identify traceability links from system documentation to program source code. The results of two experiments to identify links in existing software systems (i.e., the LEDA library, and Albergate) are presented. These results are compared with other similar type experimental results of traceability link identification using different types of information retrieval techniques. The method presented proves to give good results by comparison and additionally it is a low cost, highly flexible method to apply with regards to preprocessing and/or parsing of the source code and documentation.
- Murphy+Notkin+1998-essc
- Gail C. Murphy, David Notkin, William G. Griswold, and Erica S. Lan.
An empirical study of static call graph extractors.
ACM Trans. Softw. Eng. Methodol., 7(2):158-191, 1998.
Abstract:
Informally, a call graph represents calls between entities in a given program. The call graphs that compilers compute to determine the applicability of an optimization must typically be conservative: a call may be omitted only if it can never occur in any execution of the program. Numerous software engineering tools also extract call graphs with the expectation that they will help software engineers increase their understanding of a program. The requirements placed on software engineering tools that compute call graphs are typically more relaxed than for compilers. For example, some false negatives—calls that can in fact take place in some execution of the program, but which are omitted from the call graph—may be acceptable, depending on the understanding task at hand. In this article, we empirically show a consequence of this spectrum of requirements by comparing the C call graphs extracted from three software systems (mapmaker, mosaic, and gcc) by nine tools (cflow, cawk, CIA, Field, GCT, Imagix, LSME, Mawk, and Rigiparse). A quantitative analysis of the call graphs extracted for each system shows considerable variation, a result that is counterintuitive to many experienced software engineers. A qualitative analysis of these results reveals a number of reasons for this variation: differing treatments of macros, function pointers, input formats, etc. The fundamental problem is not that variances among the graphs extracted by different tools exist, but that software engineers have little sense of the dimensions of approximation in any particular call graph. In this article, we describe and discuss the study, sketch a design space for static call graph extractors, and discuss the impact of our study on practitioners, tool developers, and researchers. Although this article considers only one kind of information, call graphs, many of the observations also apply to static extractors of other kinds of information, such as inheritance structures, file dependences, and references to global variables.
- Ostrand+Balcer1988-cpms
- T. J. Ostrand and M. J. Balcer.
The category-partition method for specifying and generating functional tests.
Commun. ACM, 31(6):676-686, 1988.
Abstract:
A method for creating functional test suites has been developed in which a test engineer analyzes the system specification, writes a series of formal test specifications, and then uses a generator tool to produce test descriptions from which test scripts are written. The advantages of this method are that the tester can easily modify the test specification when necessary, and can control the complexity and number of the tests by annotating the tests specification with constraints.
- Rapps+Weyuker1985-sstd
- S. Rapps and E. J. Weyuker.
Selecting Software Test Data using Data Flow Information.
IEEE Transactions on Software Engineering, SE-11(4):367-375, 1985.
- Richardson1994-ttao
- Debra J. Richardson.
TAOS: Testing with Analysis and Oracle Support.
In ISSTA '94: Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, pp. 138-153.
1994.
Abstract:
Few would question that software testing is a necessary activity for assuring software quality, yet the typical testing process is a human intensive activity and as such, it is unproductive, error-prone, and often inadequately done. Moreover, testing is seldom given a prominent place in software development or maintenance processes, nor is it an integral part of them. Major productivity and quality enhancements can be achieved by automating the testing process through tool development and use and effectively incorporating it with development and maintenance processes. The TAOS toolkit, Testing with Analysis and Oracle Support, provides support for the testing process. It includes tools that automate many tasks in the testing process, including management and persistence of test artifacts and the relationships between those artifacts, test development, test execution, and test measurement. A unique aspect of TAOS is its support for test oracles and their use to verify behavioral correctness of test executions. TAOS also supports structural/dependence coverage, by measuring the adequacy of test criteria coverage, and regression testing, by identifying tests associated or dependent upon modified software artifacts. This is accomplished by integrating the ProDAG toolset, Program Dependence Analysis Graph, with TAOS, which supports the use of program dependence analysis in testing, debugging, and maintenance. This paper describes the TAOS toolkit and its capabilities as well as testing, debugging and maintenance processes based on program dependence analysis. We also describe our experience with the toolkit and discuss our future plans.
- Rosenblum+Weyuker1997-ucip
- David S. Rosenblum and Elaine J. Weyuker.
Using Coverage Information to Predict the Cost-Effectiveness of Regression Testing Strategies.
IEEE Transactions on Software Engineering, 23(3):146-156, 1997.
Abstract:
Selective regression testing strategies attempt to choose an appropriate subset of test cases from among a previously run test suite for a software system, based on information about the changes made to the system to create new versions. Although there has been a significant amount of research in recent years on the design of such strategies, there has been very little investigation of their cost-effectiveness. This paper presents some computationally efficient predictors of the cost-effectiveness of the two main classes of selective regression testing approaches. These predictors are computed from data about the coverage relationship between the system under test and its test suite. The paper then describes case studies in which these predictors were used to predict the cost-effectiveness of applying two different regression testing strategies to two software systems. In one case study, the TESTTUBE method selected an average of 88.1 percent of the available test cases in each version, while the predictor predicted that 87.3 percent of the test cases would be selected on average.
- Rosenblum1995-papa
- David S. Rosenblum.
A Practical Approach to Programming With Assertions.
IEEE Transactions on Software Engineering, 21(1):19-31, 1995.
Abstract:
Embedded assertions have been recognized as a potentially powerful tool for automatic runtime detection of software faults during debugging, testing, maintenance and even production versions of software systems. Yet despite the richness of the notations and the maturity of the techniques and tools that have been developed for programming with assertions, assertions are a development tool that has seen little widespread use in practice. The main reasons seem to be that (1) previous assertion processing tools did not integrate easily with existing programming environments, and (2) it is not well understood what kinds of assertions are most effective at detecting software faults. This paper describes experience using an assertion processing tool that was built to address the concerns of ease-of-use and effectiveness. The tool is called APP, an Annotation PreProcessor for C programs developed in UNIX-based development environments, APP has been used in the development of a variety of software systems over the past five years. Based-on this experience, the paper presents a classification of the assertions that were most effective at detecting faults. While the assertions that are described guard against many common kinds of faults and errors, the very commonness of such faults demonstrates the need for an explicit, high-level, automatically checkable specification of required behavior. It is hoped that the classification presented in this paper will prove to be a useful first step in developing a method of programming with assertions
- Rothermel+Harrold1996-arts
- Gregg Rothermel and Mary Jean Harrold.
Analyzing Regression Test Selection Techniques.
IEEE Transactions on Software Engineering, 22(8):529-551, 1996.
Abstract:
Regression testing is a necessary but expensive maintenance activity aimed at showing that code has not been adversely affected by changes. Regression test selection techniques reuse tests from an existing test suite to test a modified program. Many regression test selection techniques have been proposed; however, it is difficult to compare and evaluate these techniques because they have different goals. This paper outlines the issues relevant to regression test selection techniques, and uses these issues as the basis for a framework within which to evaluate the techniques. We illustrate the application of our framework by using it to evaluate existing regression test selection techniques. The evaluation reveals the strengths and weaknesses of existing techniques, and highlights some problems that future work in this area should address.
- Weiser1984-ps
- Mark Weiser.
Program slicing.
IEEE Transactions on Software Engineering, 10(4):352-357, July, 1984.
Abstract:
Program sliclng is a method used by experienced computer programmers for abstracting from programs. Starting from a subset of a program's behavior, slicing reduces that program to a minimal form which still produces that behavior. The reduced program, called a “slice”, is an independent program guaranteed to faithfully represent the original program within the domain of the specified subset of behavior. Finding a slice is in general unsolvable. A dataflow algorithm is presented for approximating slices when the behavior subset is specified as the values of a set of variables at a statement. Experimental evidence is presented that these slices are used by programmers during debugging. Experience with two automatic slicing tools is summarized. New measures of program complexity are suggested based on the organization of a program's slices.
- (In class dropbox)
- Weyuker1982-tntp
- Elaine J. Weyuker.
On testing non-testable programs.
The Computer Journal, 25(4):465-470, 1982.
Abstract:
A frequently invoked assumption in program testing is that there is an oracle (i.e. the tester or an external mechanism can accurately decide whether or not the output produced by a program is correct). A program is non-testable if either an oracle does not exist or the tester much expend some extraordinary amount of time to determine whether or not the output is correct. The reasonableness of the oracle assumption is examined and the conclusion is reached that in many cases this is not a realistic assumption. The consequences of assuming the availability of an oracle are examined and alternatives investigated.
- (In class dropbox)
- Weyuker1986-astd
- E. J. Weyuker.
Axiomatizing software test data adequacy.
IEEE Transactions on Software Engineering, 12(12):1128-1138, 1986.
Abstract:
A test data adequacy criterion is a set of rules used to determine whether or not sufficient testing has been performed. A general axiomatic theory of test data adequacy is developed, and five previously proposed adequacy criteria are examined to see which of the axioms are satisfied. It is shown that the axioms are consistent, but that only two of the criteria satisfy all of the axioms.
- (In class dropbox)
- Wiggerts1997-ucal
- T. A. Wiggerts.
Using Clustering Algorithms in Legacy Systems Remodularization.
In Proceedings of the Fourth Working Conference on Reverse Engineering, pp. 33-43.
1997.
Abstract:
Incited by the observation that cluster analysis and the remodularization of software systems solve similar problems, we have done research in both these areas in order to provide theoretical background for the application of cluster analysis in systems remodularization. We present an overview of cluster analysis and of systems remodularization. It appears that system remodularization techniques often either reinvent clustering techniques or could be augmented by them. We also give directions for further research
- Young+Taylor1989-rtfd
- Michal Young and Richard N. Taylor.
Rethinking the taxonomy of fault detection techniques.
In 11th International Conference on Software Engineering (ICSE '89), pp. 53-62.
Apr. 1989.
Abstract:
The conventional classification of software fault detection techniques by their operation characteristics (static vs. dynamic analysis) is inadequate as a basis for identifying useful relationships between techniques. A more useful distinction is between techniques which sample the space of possible executions, and techniques which fold the space. The new distinction provides better insight into the ways different techniques can interact, and is a necessary basis for considering hybrid fault detection techniques.
