Verification of Hierarchical Graph Structures

Award Information
Agency: Department of Defense
Branch: Defense Advanced Research Projects Agency
Contract: DAAH01-02-C-R120
Agency Tracking Number: 01SB1-0073
Amount: $381,099.00
Phase: Phase II
Program: SBIR
Awards Year: 2002
Solicitation Year: N/A
Solicitation Topic Code: N/A
Solicitation Number: N/A
Small Business Information
Grammatech, Inc.
317 N. Aurora Street, Ithaca, NY, 14850
DUNS: 603978321
HUBZone Owned: N
Woman Owned: N
Socially and Economically Disadvantaged: N
Principal Investigator
 Paul Anderson
 Senior Software Engineer
 (607) 273-7340
 paul@grammatech.com
Business Contact
 Ray Teitelbaum
Title: Chairman
Phone: (607) 273-7340
Email: tt@grammatech.com
Research Institution
N/A
Abstract
"The security and prosperity of the nation has become increasingly dependent on complex software systems. Unfortunately, current practice usually yields software that is generally unreliable and insecure. The industry must reduce reliance on methods thatcan only detect the presence of faults, and move towards methods that can demonstrate their absence. Model checking is a verification technique that allows users to verify crosscutting properties of systems. During Phase I of this project, we developed anew technique for model checking based on using context-free-language reachability algorithms. These allow us to exploit the inherent modularity in procedural abstraction, and thus allow the technique to be scaled to large programs. We constructed aprototype of a system and demonstrated how it can be used to find real faults in software. We investigated methods for using our dependence graph and program slicing technology to construct models of a reduced size so as to further improve the scalabilityof the system. In Phase II, we propose to build on our Phase I results and create a product capable of being applied to industrial-sized problems. Initial evidence suggests great potential benefits. Our commercialization strategy will ensure rapidexploitation and early success in Phase III."

* information listed above is at the time of submission.

Agency Micro-sites

SBA logo
Department of Agriculture logo
Department of Commerce logo
Department of Defense logo
Department of Education logo
Department of Energy logo
Department of Health and Human Services logo
Department of Homeland Security logo
Department of Transportation logo
Environmental Protection Agency logo
National Aeronautics and Space Administration logo
National Science Foundation logo
US Flag An Official Website of the United States Government