Back to David Coppit's Homepage.
My approach to research is to develop a portfolio of opportunities. I invest my resources into those areas that are likely to yield good short-term research results, while also balancing the need to invest in longer-term, more risky activities that may have revolutionary impact. This strategy has proven to be a smart one, allowing me to more rapidly adjust to research opportunities and difficulties.
In the next two sections, I describe two directions of my research. The first, more ambitious direction is in software plans, an approach to structuring software that is orthogonal to traditional modularization techniques. The second is bounded exhaustive testing, an approach to testing that seeks to leverage automated testing technologies to improve the trustworthiness and reliability of software.
For thirty years computer scientists have struggled with methods for structuring code. To date this effort has focused primarily on the development of new programming language abstractions for separating and encapsulating concerns in software. Language developments such as procedures, abstract data types, and classes have made great strides in providing programmers with tools for maintaining conceptual control of interacting concerns in software.
Despite much progress feature interaction remains an tough problem. More generally, concerns such as debugging and exception handling remain difficult to encapsulate. The result is scattering of concern code across the modules of the system, and subtle interactions of features that add complexity and lower software quality. Some researchers, including me, consider modules to be multi-dimensional in nature, where each dimension involves a concern of interest.
Recent work in hyperspaces, traits, and aspect-oriented programming seek to develop new language abstractions for separating such difficult concerns. My research on software plans takes a different path, addressing separation of concerns using advanced editor technology.
I seek to develop a new abstraction for software, inspired by the notion of plans in traditional architectural design. A software plan is an editable view of a module that presents the code for the concern being implemented along with the code for the concerns upon which it depends but not code for independent concerns. The overall implementation of the module is a set of plans. Software plans thus provide a multi-dimensional editable representation of a multi-dimensional software artifact, compared to approach that attempt to modularize software in a single, flattened representation
This is longer-term, higher-risk research project that presents an alternative to the current approaches. Key challenges include:
This work has the potential to create a new research direction in research into separation of concerns in code. To date, most researchers have focused on language-based approaches. In contrast, software plans is a language-independent approach that treats modules as multi-dimensional entities. We have already implemented a prototype editor called Spotlight and developed techniques for reverse-engineering software plans from existing code.
Software plans have significant practical impact. Like program slicing, software plans can provide a reduced view of the code, but based on cross-cutting features rather that data flow. This means that the cost of many program maintenance activities can be reduced. It also provides a framework where a new feature can first be implemented in a reduced view, then integrated with independent but interacting features. This reduces the cost of development compared to traditional incremental development approach that require new features to be simultaneously implemented an integrated with all of the features in the system.
Research in this area is progressing on several fronts. Undergraduates Benjamin Cox and Justin Manweiler were instrumental in the implementation of prototype editors that allowed us to experiment with different approaches to software plans [1]. Separately Robert Painter and I have developed a new model for code that allows us to explicitly represent concerns and their dependencies in code segments [7]. Robert has also developed heuristics for integrating separately developed software plans that appear to work quite well.
Separately, Meghan Revelle has developed a technique for reverse-engineering software plans from legacy code. Her approach uses test cases to exercise the code for different concerns. Trace data is collected and then analyzed using formal concept analysis. The resulting concept lattice is then used to construct the software plan.
This research is in the first year of a three-year grant from the United States Air Force Office of Scientific Research.
Traditional testing involves partitioning the input space, selecting a representative, and then deriving the expected output or verifying the actual output. Selection of cases to test is driven by models of the correlation between faults and the design or implementation of the software. For example, code coverage metrics can be used to drive the development of test cases to ensure that the test cases fully exercise the implementation.
As effective as this approach can be, it suffers from a key problem: faults that subvert the assumptions built into the fault models remain difficult to find using testing. A key question is whether a more exhaustive approach involving fewer assumptions might reveal faults that are missed by more selective approaches.
There is research to suggest that limited amounts of exhaustive testing can work. Model checking, for example, has been used successfully to identify subtle errors in specifications by verifying that desired properties hold in an exhaustive but limited segment of the state space. Jackson's "small scope hypothesis" states that a high proportion of faults can be found by exhaustively testing all inputs within some small scope [5]. This avenue of my research applies the bounded exhaustive verification approach used in model checking to the verification of software.
There are a number of key challenges. First, while exhaustive generation of simple test data is trivial, exhaustive generation of structurally complex test data is difficult. For example, it is a nontrivial task to generate all syntactically correct C++ programs up to a given size to test a compiler. Second, the relationship between exhaustive, random, and traditional testing approaches remains unknown. Without some guidance, software developers lack the information needed to wisely invest testing resources in each of the approaches. Third, the "oracle problem" is a looming issue—without some way to automatically validate test results, exhaustive or random testing remains infeasible.
The approach I take in this research is to combine automated input generation with the use of the design by contract methodology. Design by contract addresses the oracle problem by embedding the specification of the software into the software itself as self-checking assertions. This sidesteps the need to develop a separate oracle, using the observation is that it is usually easier to check a solution than it is to compute one.
Exhaustive testing was long ago discarded as an approach that is effective in theory, but infeasible in practice. One outcome of this research is to demonstrate that bounded exhaustive testing can be both feasible and effective for real systems, mirroring the success of bounded exhaustive verification in model checking. Specific contributions are:
Recent work has shifted from exhaustive generation of small inputs to generation of random inputs. The hypothesis is that random testing can be as effective as exhaustive testing. However, random testing of real systems is nontrivial in practice. First, inputs to the software under test can have structure that makes truly random generation difficult. Traditional approaches are based on randomizing alternatives in a grammar, and fail to take into account bias resulting from the structure of the grammar.
Work is also ongoing to demonstrate the efficacy of combining bounded exhaustive test data generation with specification-based contracts. our previous work used my formally-based Nova implementation as an oracle for the Galileo software. The goal of the new research to apply the contract-based approach to a sizeable system and demonstrate that it can reveal subtle faults not revealed by traditional testing techniques.
[1] David Coppit and Benjamin Cox. Software plans for separation of concerns. In Proceedings of the Third AOSD Workshop on Aspects, Components, and Patterns for Infrastructure Software, Lancaster, UK, 22 March 2004. IEEE.
[2] David Coppit and Jennifer Haddox-Schatz. On the use of specification-based assertions as test oracles. In Proceedings of the 29th Annual IEEE/NASA Software Engineering Workshop. Greenbelt, Maryland, 6-7 April 2005.
[3] David Coppit and Jeixin Lian. yagg: An Easy-To-Use Generator for Structured Test Inputs. In 20th IEEE/ACM International Conference on Automated Software Engineering, pages 356-359, Long Beach, California, 7-11 November 2005.
[4] David Coppit, Jinlin Yang, Sarfraz Khurshid, Wei Le, and Kevin Sullivan. Software assurance by bounded exhaustive testing. IEEE Transactions on Software Engineering, 31(4):328-39, April 2005.
[5] Daniel Jackson and Craig A. Damon. Elements of style: Analyzing a software design feature with a counterexample detector. IEEE Transactions on Software Engineering, 22(7): 484-495, July 1996.
[6] John A. Murphy and David Coppit. Random Generation of Test Inputs for Implicitly Defined Subdomains. In Proceedings of the Second International Workshop on Automated of Software Test, Minneapolis, Minnesota, 26 May 2007.
[7] Robert R. Painter and David Coppit. A Model for Software Plans. In Proceedings of the First International Workshop on the Modeling and Analysis of Concerns in Software, pages 14-18, St. Louis, Missouri, 16 May 2005.
[8] Kevin Sullivan, Jinlin Yang, David Coppit, Sarfraz Khurshid, and Daniel Jackson. Software assurance by bounded exhaustive testing. Proceedings of the International Symposium on Software Testing and Analysis. Boston, Massachusetts, 11-14 July 2004.
Back to David Coppit's Homepage.
Last changed May 28 2007 16:16:48.
David Coppit,
coppit@cs.wm.edu
There have been 1158639 hits since Thu Jun 9 14:49:55 2005