This paper aims to investigate the resilience of the internet in the face of censorship through a current case study: the war between Russia and Ukraine. We focus on whether Russia, as a major Internet power, has been using its network to deny access to Ukraine (and whether the Internet is resilient enough to route around such abuse). We consider how Internet accessibility changed over the course of the first few months, considering both hard and soft failures of website access. Our result, in brief, is that there is a substantial difference in network access to sites from Ukraine between March and July 2022, but Russian ASes are not causing significant collateral damage by filtering. In addition, we present the tools and resources developed in the project, including a classifier to detect soft-failures and a new multi-protocol implementation of Traceroute to locate internet censorship.

Deep packet inspection (DPI) is important for network security and is currently provided by complex black-box firewalls. This raises the question: Can network administrators build their own DPI-capable filter using a standard programmable switch? The common answer is that standard switches support P4, which allows users to specify how to parse packet headers, but not packet payload fields (e.g. URL) thus DPI tasks, like URL filtering, require dedicated middleboxes. In this paper, we challenge this common answer. First, we demonstrate that clients send packets with a predictable structure, so a P4 switch can perform some DPI (enough for URL filtering). Second, we demonstrate a URL-filtering firewall completely in the data plane, with no external help from the SDN controller, firewalls, etc. and no custom logic. Our proof-of-concept, P4Wall, handles multiple protocols (HTTP, HTTPS, DNS) with high performance - orders of magnitude faster than a standard Linux (netfilter) firewall.

Software-defined networks are useful for multiple tasks, including firewalling, telemetry, and flow analysis. In particular, the P4 language makes it possible to carry out some simple packet processing tasks in the data plane, i.e., on the switch itself (without real-time support from the SDN controller or a server). However, owing to the limitations of packet parsing in P4, these tasks involve only the packet headers. In this paper, we present a novel approach that allows Deep Packet Inspection (DPI) – i.e., inspection of the packet payload – in the data plane, using P4 alone. We make use of the fact that in P4, a switch can clone and recirculate packets. One copy (clone) can be recirculated, slicing off a byte in each round, and using a finite-state machine to check if a target string has yet been seen. If the target string is found, the other copy (original packet) is discarded; if not, it is passed through. Our approach allows us to build the first application-layer firewall (URL filter) in the data plane, and to achieve essentially line-rate performance while filtering thousands of URLs, on a commodity programmable switch. It may in future also be used for other DPI tasks.

The P4 language allows "protocol-independent packet parsing" in network switches, and makes many operations possible in the data plane. But P4 is not built for Deep Packet Inspection – it can only "parse" well-defined packet headers, not free-form headers as seen in HTTPS etc. Thus some very important use cases, such as application-layer firewalls, are considered impossible for P4. This demonstration shows that this limitation is not strictly true: switches, that support only standard P4, are able to independently perform tasks such as blocking specific URLs (without using non-standard "extern" components, help from the SDN controller, or rerouting to a firewall). As more Internet infrastructure becomes SDN-compatible, in future, switches may perform simple application-layer firewall tasks.

This paper presents Telemetron, the first active bandwidth measurement tool that can estimate the path capacity between two remote hosts, from an off-path Measuring Machine (MM). It is possible to induce traffic flow between off-path remote hosts—sending request packets to one host, with a spoofed source IP, will cause the first host to send reply packets to the other. The challenge for MM is to measure the rate at which these packets arrive at the second machine. Our key observation is that if the second machine has a global IP-ID counter, the arrival of packets can be monitored remotely, using probes from MM. By observing the rate of increment in the global IP-ID counter, MM estimates the path capacity between remote hosts. Telemetron shows high accuracy; on average, the path capacity reported is 92.5% of the theoretical limit.

Abstract Decoy Routing (DR), a promising approach to censorship circumvention, uses routers (rather than end hosts) as proxy servers. Users of censored networks, who wish to use DR, send specially crafted packets, nominally addressed to an uncensored website. Once safely out of the censored network, the packets encounter a special router (the Decoy Router) which identifies them using a secret handshake, and proxies them to their true destination (a censored site). However, DR has implementation problems: it is infeasible to reprogram routers for the complex operations required. Existing DR solutions fall back on using commodity servers as a Decoy Router. But as servers are not efficient at routing, most web applications show poor performance when accessed over DR. A further concern is that the Decoy Router has to inspect all flows in order to identify the ones that need DR. This may itself be a breach of privacy for other users (who neither require DR nor want to be monitored). In this paper, we present a novel DR system, Siege- Breaker (SB), which solves the aforementioned problems using an SDN-based architecture. Previous proposals involve a single unit which performs all major operations (inspecting all flows, identifying the DR requests and proxying them). In contrast, SB distributes the tasks for DR among three independent modules. (1) The SDN controller identifies DR requests via a covert, privacy preserving scheme, and does not need to inspect all flows. (2) The reconfigurable SDN switch intercepts packets, and forwards them to a secret proxy efficiently. (3) The secret proxy server proxies the client’s traffic to the censored site. Our modular, lightweight design achieves performance comparable to direct TCP downloads, for both in-lab setups, and Internet based tests involving commercial SDN switches.

Decoy Routing, the use of routers (rather than end hosts) as proxies, is a new direction in anti-censorship research. Decoy Routers (DRs), placed in Autonomous Systems, proxy traffic from users; so the adversary, e.g. a censorious government, attempts to avoid them. It is quite difficult to place DRs so the adversary cannot route around them -- for example, we need the cooperation of 850 ASes to contain China alone [1].

The original design of the Internet was a resilient, distributed system, that maybe able to route around (and therefore recover from) massive disruption - up to and including nuclear war. However, network routing effects and business decisions cause traffic to often be routed through a relatively small set of Autonomous Systems (ASes). This is not merely an academic issue; it has practical implications - some of these frequently appearing ASes are hosted in censorious nations. Other than censoring their own citizens' network access, such ASes may inadvertently filter traffic for other foreign customer ASes. In this paper, we examine the extent of routing centralization in the Internet; identify the major players who control the “Internet backbone”; and point out how many of these are, in fact, under the jurisdiction of censorious countries (specifically, Russia, China, and India). Further, we show that China and India are not only the two largest nations by number of Internet users, but that many users in free and democratic countries are affected by collateral damage caused due to censorship by such countries.

Networking infrastructure, such as routers and firewalls, consist of a policy (i.e., where to forward which packets) and a mechanism that implements it. As the correctness of the policy is critical, it is a natural candidate for formal verification. Indeed, several verification algorithms have been developed, that detect anomalies, conflicts, and redundancies in practical firewalls and flow tables. However, theory suggests that the problem is intractable in general: the decision tree for a policy is of size O((2n)d), where n is the number of rules and d is the number of observed features used in making the decision. (In a typical firewall, n = 1000 and d = 10.) In this paper, we show why the verification of practical firewalls is not as hard as previously thought. Using a new concept, “rules in play,” we find a new, tight bound on the size of the decision tree, and suggest three other factors - narrow fields, singletons, and all-matches - that make the problem tractable in practice. We also present an algorithm to solve an open problem: pruning a policy to the minimum possible number of rules, without changing its meaning.

Policies, such as routing tables and firewalls, are fundamental components of networking infrastructure. Unfortunately, existing policy verification and optimization algorithms require O(nd) time, where n is the number of rules (thousands), and d the number of fields (usually <; 10). However, these algorithms perform very well in practice. In this paper, we provide the explanation for this result: n and d are not the only parameters of interest! Through experimental study of our Parallel Next-step Lookup system PaNeL, as well as the FDD and Probe algorithms for policy verification, we clearly demonstrate the importance of our proposed new metric - the “width index”. Some established algorithms (such as FDD, used for structured firewall design) indeed become intractable for policies with poor width index values. We therefore suggest that the “unreasonable effectiveness” of such algorithms for practical policies is possible because such policies have a reasonable width index.

Software bugs are inevitable in software-defined networking control software, and troubleshooting is a tedious, time-consuming task. In this paper we discuss how to improve control software troubleshooting by presenting a technique for automatically identifying a minimal sequence of inputs responsible for triggering a given bug, without making assumptions about the language or instrumentation of the software under test. We apply our technique to five open source SDN control platforms---Floodlight, NOX, POX, Pyretic, ONOS---and illustrate how the minimal causal sequences our system found aided the troubleshooting process.

Most networks require that their users have "identities", i.e. have names that are fixed for a relatively long time, unique, and have been approved by a central authority (in order to guarantee their uniqueness). Unfortunately, this requirement, which was introduced to simplify the design of networks, has its own drawbacks. First, this requirement can lead to the loss of anonymity of communicating users. Second, it can allow the possibility of identity theft. Third, it can lead some users to trust other users who may not be trustworthy. In this paper, we argue that networks can be designed without user identities and their drawbacks. Our argument consists of providing answers to the following three questions. (1) How can one design a practical network where users do not have identities? (2) What does it mean for a user to authenticate another user in a network without identities? (3) How can one design a secure authentication protocol in a network without identities?

The need for secure communication in the Internet has led to the widespread deployment of secure application-level protocols. The current state- of-the-art is to use TLS, in conjunction with a password protocol. The password protocol, which we call a one-way password protocol (OPP), authenticates a user to a server, using a particular secret called the password. TLS has two functions: (1) It ensures secure communication between a client and a server (2) It allows a user to authenticate a server. The first function effectively provides a secure channel for end-to- end communication between a client and a server. However, the second function is frequently compromised by a variety of Phishing attacks. In this paper, we address this problem by developing a password protocol which we name the Two-way Password Protocol (TPP). TPP, when used in conjunction with TLS, ensures that users correctly authenticate servers, and are protected from Phishing attacks. The first contribution of this paper is to develop a protocol, called the Universal Password Protocol (UPP), which ensures that a user's password is kept safe even in the case of a successful Phishing attack. However, it may be noted that a user, after logging in, frequently shares other secrets (such as credit card number) over the secure connection, and UPP cannot protect these. Our second contribution is to build on UPP and develop, first, the Two-Way Password Protocol (TPP), and finally an improved version named the Dynamic Two-Way Password Protocol (DTPP), which ensures that both a server and a client are properly authenticated to each other. This ensures the security of all secrets which should be known only to the client and the server, including, of course, the password.

A firewall is a packet filter that is placed at the entrance of a private network. It checks the header fields of each incoming packet into the private network and decides, based on the specified rules in the firewall, whether to accept the packet and allow it to proceed or to discard the packet. To validate the correctness and effectiveness of the rules in a firewall, the firewall rules are usually subjected to two types of analysis: verification and redundancy checking. Verification is used to verify that the rules in a firewall accept all packets that should be accepted and discard all packets that should be discarded. Redundancy checking is used to check that no rule in a firewall is redundant (i.e. can be removed from the firewall without changing the sets of packets accepted and discarded by the firewall). In this paper we show that, contrary to the conventional wisdom, these two types of analysis are in fact equivalent. In particular, we show that (1) every verification algorithm can be also used to check whether a rule in a firewall is redundant, and (2) every redundancy checking algorithm can be also used to verify whether the rules in a firewall accept or discard an intended set of packets.

Policies defined by a sequence of predicate-decision rules, with first-match semantics, are widely used; a notable example is their use in firewalls, where the rules are used to decide whether to accept or discard each packet. Owing to the critical importance of correctness of such policies, as well as the need for high performance, they have been the subject of considerable analysis. In earlier work, we have demonstrated that the problem of removing redundant rules from firewalls is theoretically equivalent to verifying that a firewall satisfies a property, and proposed that this theorem be used to build a high performance redundancy remover. In this paper, we realize this promise, and build a fast linear-space redundancy remover, one to three orders of magnitude faster than current approaches. Further, we show that our algorithm is easy to parallelize- there exists a natural way to partition a large instance of the problem into independent small ones.

Many sensor networks (especially networks of mobile sensors or networks that are deployed to monitor crisis situations) are deployed in an arbitrary and unplanned fashion. Thus, any sensor in such a network can end up being adjacent to any other sensor in the network. To secure the communications between every pair of adjacent sensors in such a network, each sensor x in the network needs to store n − 1 symmetric keys that sensor x shares with all the other sensors, where n is the number of sensors in the network. This storage requirement of the keying protocol is rather severe, especially when n is large and the available storage in each sensor is modest. Earlier efforts to redesign this keying protocol and reduce the number of keys to be stored in each sensor have produced protocols that are vulnerable to impersonation, eavesdropping, and collusion attacks. In this paper, we present a fully secure keying protocol where each sensor needs to store (n+1)/2 keys, which is much less than the n − 1 keys that need to be stored in each sensor in the original keying protocol. We also show that in any fully secure keying protocol, each sensor needs to store at least (n − 1)/2 keys.

A firewall is a packet filter that is placed at the entrance of a private network. It checks the header fields of each incoming packet into the private network and decides, based on the specified rules in the firewall, whether to accept the packet and allow it to proceed, or to discard the packet. A property of a firewall is a set of packets that the firewall is required to accept or discard. Associated with each firewall is a very large set of properties that the firewall needs to satisfy. The space and time complexity of the best known deterministic algorithm, for verifying that a given firewall satisfies a given property, is 0(nd), where n is the number of rules in the given firewall and d is the number of fields checked by the firewall. Usually, n is around 2000 and d is 5. In this paper, we propose the first deterministic firewall verification algorithm whose space complexity is 0(nd), linear in both n and d. This algorithm consists of three components: a projection pass, a division pass, and a probe algorithm. We applied our verification algorithm to over two million firewall-property pairs, varying n from 100 to 10000 and fixing d at 5. From this experiment, we observed that the algorithm requires (900 + 0.5n) Kilobytes of storage and in the order of 10 seconds execution time.

A firewall is a packet filter placed at an entry point of a network in the Internet. Each packet that goes through this entry point is checked by the firewall to determine whether to accept or discard the packet. The firewall makes this determination based on a specified sequence of overlapping rules. The firewall uses the first-match criterion to determine which rule in the sequence should be applied to which packet. Thus, to compute the set of packets to which a rule is applied, the firewall designer needs to consider all the rules that precede this rule in the sequence. This “rule dependency” complicates the task of designing firewalls (especially those with thousands of rules), and makes firewalls hard to understand. In this paper, we present a metric, called the dependency metric, for measuring the complexity of firewalls. This metric, though accurate, does not seem to suggest ways to design firewalls whose dependency metrics are small. Thus, we present another metric, called the inversion metric, and develop methods for designing firewalls with small inversion metrics. We show that the dependency metric and the inversion metric are correlated for some classes of firewalls. So by aiming to design firewalls with small inversion metrics, the designer may end up with firewalls whose dependency metrics are small as well. We present a method for designing modular firewalls whose inversion metrics are very small. Each modular firewall consists of several components, called firewall modules. The inversion metric of each firewall module is very small - in fact, 1 or 2. Thus, we conclude that modular firewalls are easy to design and easy to understand.

A firewall is a filter placed at the entrance of a private network. Its function is to examine each packet that is incoming into the private network and decide, based on the specified rules of the firewall, whether to accept the packet and allow it to proceed, or to discard the packet. A property of a firewall is a specified set of packets that is supposed to be accepted or discarded by the firewall. In this paper, we present the first linear time algorithm to verify whether a given firewall satisfies a given property. The time complexity of our algorithm is O(nd), where n is the number of rules in the given firewall and d is the number of fields that are checked by the firewall. Our verification algorithm consists of two passes: a deterministic pass followed by a probabilistic pass. In most cases, the algorithm correctly determines whether the given firewall satisfies the given property. But in some rare cases, the algorithm may erroneously determine that the firewall satisfies the property. Using a combination of analysis and extensive simulation, we show that the probability of an error by the algorithm is of the order of 6 times 10-5.

We discuss the stabilization properties of networks that are composed of ¿displacement elements¿. Each displacement element is defined by an integer K, called the displacement of the element, an input variable x, and an output variable y, where the values of x and y are non-negative integers. An execution step of this element assigns to y the maximum of 0 and K + x. The objective of our discussion is to demonstrate that two principles play an important role in ensuring that a network N is stabilizing, i. e. starting from any global state, network N is guaranteed to reach a global fixed point. Specifically, the principle of consistent fixed points is analogous to the requirement that a control system be free from self-oscillations. And the principle of negative gain is analogous to the requirement that the feedback loop of a sum of displacements along every directed loop in network N is negative.

A widely used mechanism for computing the topology of any network in the Internet is Traceroute. Using Traceroute, one simply needs to choose any two nodes in a network and then obtain the sequence of nodes that occur between these two nodes, as specified by the routing tables in these nodes. Thus, each use of Traceroute in a network produces a trace of nodes that constitute a simple path in this network. In every trace that is produced by Traceroute, each node occurs either by its unique identifier or by the anonymous identifier "*". In this paper, we introduce the first theory aimed at answering the following important question. Is there an algorithm to compute the topology of a network N from a trace set T that is produced by using Traceroute in N, assuming that each edge in N occurs in at least one trace in T, and that each node in N occurs by its unique identifier in at least one trace in T? Our theory shows that the answer to this question is "No" in general. But if N is a tree, or is an odd ring, then the answer is "Yes". On the other hand, if N is an even ring, the answer is "No", but if N is a "mostly regular" even ring, then the answer is "Yes".