Project Summary

Organization:

Carnegie Mellon University

Subcontractors:

None

Principal Investigators:

Mary Shaw	shaw+@cs.cmu.edu	(412) 268-2589 
David Garlan	garlan+@cs.cmu.edu	(412) 268-5056 
Daniel Jackson	dnj+@cs.cmu.edu		(412) 268-5143 
Jeannette Wing	wing+@cs.cmui.edu	(412) 268-3068

Title of Effort:

Software Sciences and Engineering Research: Composable Software Systems

Objective:

To provide a scientific and engineering basis for designing, building, and analyzing composable software systems. To provide languages, tools, environments, and techniques to support these activities.

Approach:

The three research lines are software architecture, formal methods, and tractable software analysis. This project will develop new models, theories, methods, languages, and tools for classifying, specifying, analyzing, and designing software systems beyond the component level. This support could lead to substantial reduction in maintenance costs, improvement in software reuse, and increase in quality of software.

Recent 96 Accomplishment:

Made initial distribution of prototype UniCon processor. Forty-one organizations have acquired the distribution to date.

Isolated knowledge in the UniCon processor required to implement connectors in the UniCon language; made the UniCon processor reconfigurable with respect to connectors.

Expanded UniCon support of remote procedure calls to handle five variants of Unix (Mach, Real-Time Mach, Linux, SunOS, and Solaris).

Specified the DoD Advanced Distributed Simulation (ADS) High Level Architecture (HLA) using the Wright Architectural Specification Language. Used the Wright toolset to discover a number of difficiencies in the published specification. Communicated these problems to the ADS DMSO steering committee, who used them as a basis for improving the design and description of the architecture.

Augmented the Aesop architectural design environment toolkit to support several new styles; added ACME capability.

Created preliminary classification of architectural styles.

Published a book on software architecture: [Shaw and Garlan: Software Architecture, Perspectives on an Emerging Discipline, Prentice Hall, 1996.]

Other schools are beginning to offer the software architecture course.

Designed the ACME architecture interchange language (with David Wile of ISI). The language will enable the exchange of architectural designs between different DARPA-funded architectural toolsets (including UniCon, Aesop, and Rapide). It will serve as the basis for a new class of architectural design and analysis tools. Built one such tool, which transforms ACME descriptions of architectures into Web-viewable graphical files.

Continued work on Nitpick, a fully automatic checker for relational specifications. Designed and implemented a new scheme. Unlike the previous scheme, based on explicit enumeration of values, this new scheme employs Bryant's Ordered Binary Decision Diagrams. On most of our examples, the new scheme outperforms the old one by orders of magnitude. It has also allowed analysis of specifications that were previously not analyzable at all.

Continued applying the Nitpick checker to small case studies. Found a flaw in the proof of correctness of an air-traffic control handoff protocol. The tool was also used in classroom projects in a course in the CMU Master of Software Engineering degree program.

Implemented new ideas about program understanding using type inference. Constructed a prototype, called Lackwit, that generates graphs showing, at the module level, how parts of a large program use a given data structure. Applied Lackwit to a 20,000 line robotics application in C, and were able not only to answer questions that a maintainer had not been able to answer with existing tools, but also found a variety of bugs, including storage leaks in loops.

Designed a method for checking finite theories. Applied method and prototype checker to authentication and electronic commerce protocols.

FY97 Plan:

Add new types of connectors to the UniCon architecture description language, for example, for shared data, database access, and distributed objects.

Support translation between UniCon and ACME, thereby providing access to UniCon capabilities for other ADLs and acquiring for UniCon access to the capabilities of other ADLs.

Extend the Wright language to handle architectural styles. Apply to other DoD-relevant case studies. Develop tools to assist with checking that one (Wright-specified) architecture refines another.

Extend Aesop by developing a Web-accessible, ACME-compliant architectural reuse repository. Develop new algorithms for "unification" of reusable architectural design patterns (stored in the repository) with architectural designs. Develop an Aesop environment for simulation systems written in the "Structural Modelling" style.

Extend classification of architectural styles.

Improve analysis of "architectural mismatch" issues in support of improved interoperability.

Develop ACME parser/unparser tools to permit exchange of information between UniCon, Rapide, and Aesop. Develop formal semantics for ACME. Work with community (now EDCS) to integrate ACME technology into emerging tools and analyses.

Extend the Nitpick checking method further. Develop techniques for handling quantifiers. Develop a new scheme for exploiting symmetry that is simpler and more elegant than the previous scheme, to provide better integration with other reduction methods, and thus, ultimately, a more efficient search capability.

Demonstrate the use of Nitpick on an industrial case study. We are looking at various options, including railway switching, web naming schemes and telephony. We are also beginning to apply Nitpick to the analysis of software architectures.

Continue development of the Lackwit tool, primarily by finding ways to cast questions that maintainers ask in the type-theoretic framework of the tool. Design a better graphical front-end and improve the speed of database queries.

Build fast, automatic checkers for verifying security protocols:

A logic-based approach where the logic plus the protocol defines a finite theory; checking the property of the protocol is a simple membership test. Being applied currently to authentication and electronic commerce protocols based on the BAN logic and its variants. Impact: completely new approach to checking security protocols. It's fast and completely automatic. Thus the speed in debugging protocol designs is on the order of recompiling the protocol specification.

A model-based approach where a finite state machine model is defined for the protocol; properties stated are checked of the finite model. Being applied currently to electronic commerce protocols. Impact: completely new approach to reasoning about electronic commerce protocols; completely new focus on the properties to reason about them (atomicity properties, not "standard" properties like non-interference or trust, which are less relevant in this domain).

Make these checkers publicly available to the DARPA community and research community.

Technology Transition:

Made UniCon publicly available. UniCon is a language for describing the software architecture of a system, and its associated toolset analyzes such descriptions and builds applications from them. The UniCon toolset distribution is available on the Web at the following location: http://www.cs.cmu.edu/~UniCon/. For more information, contact project members at UniCon-Distribution@cs.cmu.edu.

The Nitpick tool, the only tool available for completely automatic checking of relational specifications (that is, those in languages like Z and VDM that use relational data structures), was released in a beta version in January, 1996. Nitpick is pubicly available in executable form from the following Web site: http://www.cs.cmu.edu/~nitpick/. For more information, contact project members at nitpick@cs.cmu.edu.

Aesop (V2) was released to the public. This version includes support for ACME. For more information and to order this version, contact project members at aesop-help@cs.cmu.edu.

Mary Shaw and David Garlan authored and published the following text on software architecture. "Software Architecture: Perspectives on an Engineering Discipline," Prentice Hall, 1996.

David Garlan interacted with the Advanced Distributed Simulation Steering Committee to show the benefits of formal architectural modelling.

David Garlan and Mary Shaw presented a full-day tutorial for CMU School of Computer Science summer school, entitled "Architectures for Software Systems," June 1996.

Daniel Jackson presented a one-day summer school course on the use of the Nitpick tool in requirements analysis, June 1996.

Jeannette Wing presented a tutorial for CMU School of Computer Science summer school on formal methods, June 1996.

David Garlan worked with students and SEI researchers to develop a formal archtectural model for the SIMPLEX fault-tolerant, real-time architecture.