OBJECTIVE: Develop algorithms for reasoning about the range of possible interactions among independently configured network components capable of predicting errors (e.g., packet loss, forwarding loops, and routing inconsistency) in a network due to misconfiguration and diagnosing faults from a model of a network and observed behavior. DESCRIPTION: Cognitive Radio, Mobile Ad hoc Networks (MANETs) and traditional packet-switching networks all depend on the proper interaction of independently configured network devices across a data plane. Devices are frequently operated by non-experts, policy changes can disseminate across a network with varying speed, and configuration options can be complex. In many cases, devices must support multiple protocols and/or services that, while defined separately, can interact with each other. While systems exist for providing point-protection (e.g., a firewall) in a network, no system exists for comprehending a network data plane as a whole and anticipating how components could interact in unintended ways. The algorithms should accept information about the configuration of the various components, along with knowledge about the sorts of data to be transmitted on the network and the physical connectivity between the components, and use that information to predict faults in the network arising from the interaction of the various components. Ideally, this prediction should be in the form of a counter-example that demonstrates the fault. PHASE I: Investigate and validate network analysis algorithms capable of detecting faults in a simulated network. The simulated network (cognitive radio, mobile ad hoc, or packet-switching network) should support at least one service. The prototype demonstrations will draw conclusions about performance and scalability (e.g., time, required hardware resources, and scope of checkable polices) of the algorithms over network size, degree of interconnectivity, and capability. PHASE II: Develop a prototype implementation applicable to a deployed cognitive radio, mobile ad hoc, or packet-switching network. The implementation should scale to network sizes representative of deployed networks and parse configuration information for multiple network component types and services. The implementation should be able to predict realistic fault scenarios, generate counter-examples, and, if supported, suggest remedial actions. The implementation should include a prototype operator interface and demonstrate the feasibility of using the technology to reduce network maintenance and operating costs by mitigating human error and/or improving overall network efficiency and integrity. PHASE III: The network analysis algorithms developed under this topic could be used to detect defects and/or vulnerabilities in a wide range of DoD networks. The goal of this research is to be able to analyze a complete network deployment and assist human operators in maintaining, optimizing, and securing that network. In addition to the algorithms developed under this proposal, this will require the development of a suitable user interface, parsing technology for interpreting component configurations, and a language interface for defining connectivity, capability and operation policy parameters. Transition will be to a suitable operational environment. PRIVATE SECTOR COMMERCIAL POTENTIAL/DUAL-USE APPLICATIONS: Networks are ubiquitous in commercial industry. Tools capable of modeling networks and detecting and explaining misconfigurations could be deployed in industry to maintain any corporate intranet. REFERENCES: 1. H. Mai, A. Khurshid, R. Agarwal, M. Caesar, P.B. Godfrey, S. King."Debugging the Data Plane with Anteater,"ACM SIGCOMM, 2011. 2. N. Feamster, H. Balakrishnan."Detecting BGP Configuration Faults with Static Analysis,"Proc. USENIX NSDI, 2005. 3. R. Mahajan, D. Wetherall, and T. Anderson."Understanding BGP Misconfiguration,"Proc. ACM SIGCOMM, 2002. 4. G. G. Xie, J. Zhan, D. A. Maltz, H. Zhang, A. Greenberg, G. Hjalmtysson, J. Rexford."On Static Reachability Analysis of IP networks,"Proc. IEEE INFOCOM, 2005.