Multi-Lingual Dependence-Graph Components for Software and Hardware Analysis, Design, and Specialization
With SBIR support from DARPA and ONR, GrammaTech is developing a toolkit of reusable, commercial-quality, multi-lingual components for building and operating on the dependence-graph representations of programs and program specifications.
Current analysis and specialization tools for software programs and hardware-design specifications use simple-minded methods that are too coarse-grained to provide adequate levels of precision and completeness. An extreme example of the consequence of imprecise and incomplete analysis is the Ariane 5 rocket failure, but less extreme examples are commonplace in both the hardware and software domains, and in the aggregate, just as costly. As systems become larger, more complex, and more expensive to correct or replace, new methods will be not merely desirable, but absolutely necessary. The need for better methods is an opportunity for GrammaTech to develop and market tools employing a new technology: deep-structure analysis. The successful introduction of this new technology to the commercial marketplace would benefit both industry and the DoD.
The difficulties inherent in the design and implementation of hardware and software systems stem from their size, their intricacy, and the interactions among separate entities within them — in short, from their enormous mass of detail. Because even the most minute detail can have a system-wide influence, it is notoriously difficult to understand, predict the behavior of, and modify software programs and hardware-design specifications. (For our purposes, both software programs and hardware-design specifications are considered "programs".) To address these issues, analytic tools are essential.
Historically, analysis and development tools have operated on the level of a program’s surface structure, with the simplest ones operating only on flat text. Tools based on abstract syntax are more precise and powerful, but even though GrammaTech has pioneered the development of such tools, we recognize that abstract syntax is still too coarse and superficial to provide more than the first steps toward a fully satisfactory analysis. Both interactive and non-interactive tools must move beyond the inherent limitations of surface-level methods.
There is a mismatch between the superficial analytic capabilities of today's interactive tools and the deep structure of the programs on which they operate; that is, their complex networks of interconnections and dependences. The reason that such tools are useful at all is that substantial manual effort can transcend their limitations. Skillfully employing clumsy tools, users build up and operate from mental maps of deep structure. Even for moderately complicated programs, however, users are often thwarted by obscure organization and the daunting mass of detail in the deep structure. Too much of the burden falls on human memory and reasoning power. For truly complex programs, analysis is so limited in scope and depth that it breaks down. More powerful tools are required both to inspect program structure with greater precision and completeness, and to organize the detail that is revealed.
Non-interactive tools are also limited by the lack of analytic depth. For example, consider a class loader for object-oriented code. Typically, only a fraction of the functionality of a general-purpose class is used by a given client, leading to the opportunity for specialization to achieve a smaller footprint and faster download time. Analysis at the level of a procedure call graph only enables removal of dead methods. Deep-structure analysis at the statement and expression level is required to identify and remove dead fields and dead code within live methods.
The need for better tools is common to both the DoD and commercial spheres, is present for all programming languages, and indeed is not restricted to software: hardware-design languages are structured symbolic systems and their analysis is subject to the same difficulties as software. The problem is fundamental: it reflects a commonality that cuts across all domains of computing, namely structural complexity that is inadequately addressed by surface-structure methods.
GrammaTech's approach to the problem is equally fundamental: to achieve the next level of sophistication, tools based on the semantics of programming and hardware-specification languages will operate directly on a representation of the program’s deep structure.
Transitions:
- CodeSurfer - GrammaTech's Software development, inspection, and maintenance tool for program understanding and information assurance.
Papers:
- "Dependence Graphs and Program Slicing"
Presentations:
- "Static Analysis via Dependence Graphs"
Related Links:
- Wisconsin Slicing Project - DARPA/NSF/ONR-supported research at the University of Wisconsin, by Tom Reps and Susan Horwitz, that serves as a foundation for this work.