Verification of Hierarchical Graph Structures

Award Information
Agency:
Department of Defense
Branch
Defense Advanced Research Projects Agency
Amount:
$381,099.00
Award Year:
2002
Program:
SBIR
Phase:
Phase II
Contract:
DAAH01-02-C-R120
Award Id:
53293
Agency Tracking Number:
01SB1-0073
Solicitation Year:
n/a
Solicitation Topic Code:
n/a
Solicitation Number:
n/a
Small Business Information
317 N. Aurora Street, Ithaca, NY, 14850
Hubzone Owned:
N
Minority Owned:
N
Woman Owned:
N
Duns:
603978321
Principal Investigator:
Paul Anderson
Senior Software Engineer
(607) 273-7340
paul@grammatech.com
Business Contact:
Ray Teitelbaum
Chairman
(607) 273-7340
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

Enviromental Protection Agency logo

National Aeronautics and Space Administration logo

National Science Foundation logo
US Flag An Official Website of the United States Government