Divya Raghunathan will present her FPO "Formal Methods for Networks: Verification, Compilation, and Performance Analysis" on February 24, 2025 at 3pm in CS 302.
Her committee is as follows:
Examiners: Aarti Gupta (Adviser), Zachary Kincaid, and Mae Milano
Readers: David Walker and Maria Apostolaki
Title:
"Formal Methods for Networks: Verification, Compilation, and Performance Analysis"
Abstract:
The scale and complexity of computer networks make their correct operation and analysis challenging. Networks are difficult to configure correctly: router configuration bugs are common, and often cause severe outages or security breaches. Network management tasks (e.g., ensuring compliance with service-level agreements) are challenging, given the diversity of network traffic and limited monitoring information.
Formal verification provides tools to improve network reliability, but large network sizes and the vast space of network environments make scalable verification challenging, especially for approaches using Satisfiability Modulo Theories (SMT). Abstractions can improve verification scalability by simplifying the system being verified. Abstractions that over-approximate system behavior enable sound verification that never misses property violations, but could report spurious violations (false positives). Designing effective abstractions that enable scalable verification but rarely report false positives is challenging. This thesis introduces novel abstractions and verification methods for network control plane verification and network performance analysis. Our abstract verification procedures are effective (low false positive rate) and significantly improve verification scalability over state-of-the-art.
Our network control plane verifier, ACORN, checks routing-related properties like reachability given network router configurations. ACORN leverages our novel Nondeterministic Routing Choice (NRC) abstractions to simplify the network control plane. We prove that the NRC abstractions are sound for verification, i.e., never miss property violations. With our NRC abstractions, ACORN successfully verifies reachability for up to 28000 routers (in a FatTree topology) within an hour, while state-of-the-art tools do not scale beyond a few thousand routers.
Our network performance analysis approach, QuASI, answers performance queries (e.g., burst occurrence) under given measurements. QuASI's first layer, QuASI-approx, uses three novelties: our enqueue-rate abstraction, our reduction over abstract packet traces, and an efficient matrix-based consistency check. We prove QuASI-approx will never incorrectly report a query is unsatisfiable. QuASI's second layer uses SMT constraints to model switch behavior under measurements, leveraging the enqueue-rate abstraction to speed up verification without loss of precision for supported queries. QuASI answers queries up to six orders of magnitude faster than an existing performance analysis tool. (edited)
The scale and complexity of computer networks make their correct operation and analysis challenging. Networks are difficult to configure correctly: router configuration bugs are common, and often cause severe outages or security breaches. Network management tasks (e.g., ensuring compliance with service-level agreements) are challenging, given the diversity of network traffic and limited monitoring information.
Formal verification provides tools to improve network reliability, but large network sizes and the vast space of network environments make scalable verification challenging, especially for approaches using Satisfiability Modulo Theories (SMT). Abstractions can improve verification scalability by simplifying the system being verified. Abstractions that over-approximate system behavior enable sound verification that never misses property violations, but could report spurious violations (false positives). Designing effective abstractions that enable scalable verification but rarely report false positives is challenging. This thesis introduces novel abstractions and verification methods for network control plane verification and network performance analysis. Our abstract verification procedures are effective (low false positive rate) and significantly improve verification scalability over state-of-the-art.
Our network control plane verifier, ACORN, checks routing-related properties like reachability given network router configurations. ACORN leverages our novel Nondeterministic Routing Choice (NRC) abstractions to simplify the network control plane. We prove that the NRC abstractions are sound for verification, i.e., never miss property violations. With our NRC abstractions, ACORN successfully verifies reachability for up to 28000 routers (in a FatTree topology) within an hour, while state-of-the-art tools do not scale beyond a few thousand routers.
Our network performance analysis approach, QuASI, answers performance queries (e.g., burst occurrence) under given measurements. QuASI's first layer, QuASI-approx, uses three novelties: our enqueue-rate abstraction, our reduction over abstract packet traces, and an efficient matrix-based consistency check. We prove QuASI-approx will never incorrectly report a query is unsatisfiable. QuASI's second layer uses SMT constraints to model switch behavior under measurements, leveraging the enqueue-rate abstraction to speed up verification without loss of precision for supported queries. QuASI answers queries up to six orders of magnitude faster than an existing performance analysis tool.
