The future of static verification in networking may be obscured by two clouds: the complexity of distributed systems with highly concurrent events, and the decision-making on infrastructures growing without a premeditated plan. This poster discusses a possible solution to these issues, in which the huge space of analyzing distributed systems and the macro-questions of system evolution are addressed by a common structure, a logical implication problem which we call indirect troubleshooting. The usefulness and feasibility of indirect troubleshooting is illustrated by a preliminary realization with the chase, a remarkable process for mechanically deciding implications.

The value of database in advancing networking - in the paradigm shift from protocols to software-defined networking - was once highlighted by database-inspired management of network states. Moving beyond factual states, this paper considers semantics management a new frontier in the databases-networking knowledge “transfer”, seeking to manage network policies via structural manipulation of the corresponding software (program). As a proof of concept, we make a case of semantics-based network transformation with the datalog structure and the chase, an elegant process for handling data dependencies (semantics). Our main result is an extension of the classic chase to faure-log; a networking extension of datalog for the richer networking policies.

Traditional network state management focuses on packets that exercise network structures (configurations, procedures) and testify semantics (intentions), but provides little insights into how the structure actually "causes" the semantics. In response to this missed opportunity, we propose reflective networking, which features a network structure capable of altering itself with a causal connection to its semantics. Specifically, we investigate the network datalog structure and the chase, a process that transforms datalog programs by "executing" intents (semantic constraints) that are themselves expressed in datalog. To illustrate the usefulness of reflective networking, this demonstration presents a first use case: we developed an intuitive specification of routing in datalog, and employed the chase to summarize a network's routing behavior by minimizing (repeatedly transforming) the corresponding datalog program.

BGP and its alternatives alike, struggle with distributed policy making in the absence of a central authority: BGP prioritizes independence of the participating networks (e.g., ASes), imposes zero coordination, but has to tolerate inflexible policies each network can express. On the other hand, BGP alternatives (source routing, for example), through coordination, trade independence for flexibility, but only achieve flexibility partially. This paper asks, to achieve flexible routing, what is the fitting adjustment between network independence and coordination? To answer this question, we propose a simple principle that the sole end to interfere with the flexibility of a participating network is to prevent harms — decreasing the level of flexibility — to others. As an instantiation of this principle, we introduce the concept of policy exchange that dynamically adjusts independently set policies on the fly, and develop a preliminary implementation with conditional table, a strong knowledge representation system that allows us to distribute and manipulate policies with the usual SQL-like operators. Our preliminary experiments on realistic network topology and synthetic policies are encouraging.

Formal analysis has been intensively studied (e.g., deep customization and synergistic co-design) in the networking domain, but one assumption remains largely unexamined: there is a complete evaluation that expects definite knowledge of the task, and is expected to output a decisive result. This paper argues for a "partial" approach, a departure from the de facto, to network analysis in a practical environment with uncertain events and limited visibility. Specifically, we seek (1) loss-less modeling in which network uncertainty is explicitly handled without corrupting the querying capability; and (2) complete verification relative to the level of information available, which reaches an inconclusive result only when more information is needed. As a realization of this vision, we present fauré, a preliminary design in which a datalog extension (called fauré-log) for incomplete information is developed to enable loss-less modeling, and combined with static analysis of pure datalog to implement example relative-complete verifiers.

Database usage in the context of networking has been focusing on managing factual data --- network state. But database systems are also renowned for mediating among semantic data --- data integrity constraints (ICs) that capture network policies. This paper asks if and how can database systems help with coordinating network policies in the semantically rich environment of SDN and BGP. We identify several problems --- disparate policies buried in the network that hinders rather than facilitates coordination; manual control flow orchestration of SDN policies that burdens the SDN programmer; and overlooked conflicts among interdomain routing policies that, though induced by multiple ASes, are only manifested within a single AS. Driven by these unique problems, we present a preliminary database solution that, using ICs as a unifying knowledge representation, employs automated reasoning to anticipate and to adjust the interplay between policies and the rest of the networking world.

In recent years, there has been a proliferation in network domain-specific languages (DSL). These languages enable us to exploit the programmability of these networks, while still providing correctness guarantees through verification and analysis of DSLs. However, none of these DSLs have received widespread adoption. First these new languages require a learning curve among operators who may not be trained programmers. Second, these new SDN applications sometimes rely on functionality in legacy networks that cannot be easily migrated or analyzed.

The Border Gateway Protocol (BGP) is the single inter-domain routing protocol that enables network operators within each autonomous system (AS) to influence routing decisions by independently setting local policies on route filtering and selection. This independence leads to fragile networking and makes analysis of policy configurations very complex. To aid the systematic and efficient study of the policy configuration space, this paper presents network reduction, a scalability technique for policy-based routing systems. In network reduction, we provide two types of reduction rules that transform policy configurations by merging duplicate and complementary router configurations to simplify analysis. We show that the reductions are sound, dual of each other and are locally complete. The reductions are also computationally attractive, requiring only local configuration information and modification. We have developed a prototype of network reduction and demonstrated that it is applicable on various BGP systems and enables significant savings in analysis time. In addition to making possible safety analysis on large networks that would otherwise not complete within reasonable time, network reduction is also a useful tool for discovering possible redundancies in BGP systems.

With the tremendous growth of the Internet and the emerging software-defined networks, there is an increasing need for rigorous and scalable network management methods and tool support. This paper proposes a synthesis approach for managing software-defined networks. We formulate the construction of network control logic as a reactive synthesis problem which is solvable with existing synthesis tools. The key idea is to synthesize a strategy that manages control logic in response to network changes while satisfying some network-wide specification. Finally, we investigate network abstractions for scalability. For large networks, instead of synthesizing control logic directly, we use its abstraction—a smaller network that simulates its behavior—for synthesis, and then implement the synthesized control on the original network while preserving the correctness. By using the so-called simulation relations, we also prove the soundness of this abstraction-based synthesis approach.

The BGP (Border Gateway Protocol) is the single inter-domain routing protocol that enables network operators within each autonomous system (AS) to influence routing decisions by independently setting local policies on route filtering and selection. This independence leads to fragile networking and makes analysis of policy configurations very complex. To aid the systematic and efficient study of the policy configuration space, this paper presents a reduction calculus on policy-based routing systems. In the calculus, we provide two types of reduction rules that transform policy configurations by merging duplicate and complementary router configurations to simplify analysis. We show that the reductions are sound, dual of each other and are locally complete. The reductions are also computationally attractive, requiring only local configuration information and modification. These properties establish our reduction calculus as a sound, efficient, and complete theory for scaling up existing analysis techniques.

Today's inter-domain routing protocol, the Border Gateway Protocol (BGP), is increasingly complicated and fragile due to policy misconfiguration by individual autonomous systems (ASes). Existing configuration analysis techniques are either manual and tedious, or do not scale beyond a small number of nodes due to the state explosion problem. To aid the diagnosis of misconfigurations in real-world large BGP systems, this paper presents BGPVerif , a reduction based analysis toolkit. The key idea is to reduce BGP system size prior to analysis while preserving crucial correctness properties. BGPVerif consists of two components, NetReducer that simplifies BGP configurations, and NetAnalyzer that automatically detects routing oscillation. BGPVerif accepts a wide range of BGP configuration inputs ranging from real-world traces (Rocketfuel network topologies), randomly generated BGP networks (GT-ITM), Cisco configuration guidelines, as well as arbitrary user-defined networks. BGPVerif illustrates the applicability, efficiency, and benefits of the reduction technique, it also introduces an infrastructure that enables networking researchers to interact with advanced formal method tool.

Interdomain routing stitches the disparate parts of the Internet together, making protocol stability a critical issue to both researchers and practitioners. Yet, researchers create safety proofs and counterexamples by hand and build simulators and prototypes to explore protocol dynamics. Similarly, network operators analyze their router configurations manually or using homegrown tools. In this paper, we present a comprehensive toolkit for analyzing and implementing routing policies, ranging from high-level guidelines to specific router configurations. Our Formally Safe Routing (FSR) toolkit performs all of these functions from the same algebraic representation of routing policy. We show that routing algebra has a natural translation to both integer constraints (to perform safety analysis with SMT solvers) and declarative programs (to generate distributed implementations). Our extensive experiments with realistic topologies and policies show how FSR can detect problems in an autonomous system's (AS's) iBGP configuration, prove sufficient conditions for Border Gateway Protocol (BGP) safety, and empirically evaluate convergence time.

We present the demonstration of a comprehensive toolkit for analyzing and implementing routing policies, ranging from high-level guidelines to specific router configurations. Our Formally Safe Routing (FSR) toolkit performs all of these functions from the same algebraic representation of routing policy. We show that routing algebra has a very natural translation to both integer constraints (to perform safety analysis using SMT solvers) and declarative programs (to generate distributed implementations). Our demonstration with realistic topologies and policies shows how FSR can detect problems in an AS's iBGP configuration, prove sufficient conditions for BGP safety, and empirically evaluate convergence time.

Program verification plays an important role in assuring the reliability of software systems. This paper presents a novel verification methodology for Java programs based on the higher-order logic theorem proving system HOL. The soundness of a Java program in accordance with its specification in annotation is established in HOL4. A Hoare-logic based verification methodology (WHY) guides the verification process. As a case study, a Java program with four methods is specified in JML annotation and proved in HOL. The flexible manipulation of pure method call in annotation is presented in the HOL proof mechanism. This work may constitute the first attempt on using the proving system HOL for Java programs. The experience demonstrates the effectiveness and the promising results of the approach