This paper describes the multi-year effort undertaken by Mozilla to incorporate and deploy CRLite, a TLS certificate revocation checking system, in the Firefox browser. With the deprecation of the Online Certificate Status Protocol (OCSP) by Let's Encrypt and others, CRLite is now the only broadly deployed mechanism capable of checking the revocation status of every TLS certificate. The successful seven-year evolution of CRLite from a research prototype to a widely used tool required improvements in the original data structures (now using partitioned Ribbon filters), changes in Certificate Authority revocation practices, and correctly synchronizing with Certificate Transparency logs to eliminate false positives. Using data from Firefox's opt-in telemetry, we report that CRLite achieves an effective revocation coverage of 87.8% while maintaining moderate bandwidth costs, even during real revocation events like the November 2025 Microsoft incident. Through simulations, we also examine the potential impacts of shorter certificate lifetimes and hypothetical mass revocations on CRLite. CRLite demonstrates that low-latency, private, comprehensive certificate revocation checking is possible using moderate bandwidth.

Geosynchronous (GEO) satellite links provide IP backhaul to remote critical infrastructure for utilities, telecom, government, military, and commercial users. To date, academic studies of GEO infrastructure have focused on a handful of satellites and specific use cases. We perform the first broad scan of IP traffic on 39 GEO satellites across 25 distinct longitudes with 411 transponders using consumer-grade equipment. We overcome the poor signal quality plaguing prior work and build the first general parser that can handle the diverse protocols in use by heterogeneous endpoints. We found 50% of GEO links contained cleartext IP traffic; while link-layer encryption has been standard practice in satellite TV for decades, IP links typically lacked encryption at both the link and network layers. This gives us a unique view into the internal network security practices of these organizations. We observed unencrypted cellular backhaul traffic from several providers including cleartext call and text contents, job scheduling and industrial control systems for utility infrastructure, military asset tracking, inventory management for global retail stores, and in-flight wifi.

The Online Certificate Status Protocol's long slide—after 25 years of soft-fail rules, privacy leakage, and shaky infrastructure—exposes a deeper failure in web-PKI revocation. Certificate Authorities increasingly route OCSP traffic through CDNs for speed, yet this recentralizes trust: our measurements show Akamai serves 62 percent of all revocation responses, creating single points of failure and betraying PKI's decentralized ideals.

Many techniques have been introduced to measure network interference-tampering performed by nation-state censors or corporate firewalls to block unwanted traffic. How-ever, virtually all prior measurement techniques require some degree of participation from endpoints within each country of study: including VPNs, cloud providers, or volunteers willing to run measurement software on their personal devices at their own risk. However, such endpoints are not always available in all countries that tamper with connections, leaving many networks unmeasurable. In this paper, we present the first global, active, network interference measurements that require no participating end-points within any country of study. Our techniques extend two recent studies that use packet sequences that trigger network interference from outside the country of study by tricking middleboxes into believing a connection exists. Our system, Mint, generalizes and automates this approach-which had previously only been applied to two countries-to allow it to apply to the global IPv4 and IPv6 Internet. We use Mint to conduct the first global measurements of network interference without using any participating endpoints, and the first comprehensive scans of IPv6 interference. We show that we are able to measure networks, autonomous systems, and even entire countries that previous methods could not. We also present several case studies that highlight how our tool can be used to perform new measurement studies of network interference.

Static and hard-coded layer-two network identifiers are well known to present security vulnerabilities and endanger user privacy. In this work, we introduce a new privacy attack against Wi-Fi access points listed on secondhand marketplaces. Specifically, we demonstrate the ability to remotely gather a large quantity of layer-two Wi-Fi identifiers by programmatically querying the eBay marketplace and applying state-of-the-art computer vision techniques to extract IEEE 802.11 BSSIDs from the seller's posted images of the hardware. By leveraging data from a global Wi-Fi Positioning System (WPS) that geolocates BSSIDs, we obtain the physical locations of these devices both pre- and post-sale. In addition to validating the degree to which a seller's location matches the location of the device, we examine cases of device movement–once the device is sold and then subsequently re-used in a new environment. Our work highlights a previously unrecognized privacy vulnerability and suggests, yet again, the strong need to protect layer-two network identifiers.

Wi-Fi-based Positioning Systems (WPSes) are used by modern mobile devices to learn their position using nearby Wi-Fi access points as landmarks. In this work, we show that Apple’s WPS can be abused to create a privacy threat on a global scale. We present an attack that allows an unprivileged attacker to amass a worldwide snapshot of Wi-Fi BSSID geolocations in only a matter of days. Our attack makes few assumptions, merely exploiting the fact that there are relatively few dense regions of allocated MAC address space. Applying this technique over the course of a year, we learned the precise locations of over 2 billion BSSIDs around the world.The privacy implications of such massive datasets become more stark when taken longitudinally, allowing the attacker to track devices’ movements. While most Wi-Fi access points do not move for long periods of time, many devices—like compact travel routers—are specifically designed to be mobile.We present several case studies that demonstrate the types of attacks on privacy that Apple’s WPS enables: We track devices moving in and out of war zones (specifically Ukraine and Gaza), the effects of natural disasters (specifically the fires in Maui), and the possibility of targeted individual tracking by proxy—all by remotely geolocating wireless access points.We provide recommendations to WPS operators and Wi-Fi access point manufacturers to enhance the privacy of hundreds of millions of users worldwide. Finally, we detail our efforts at responsibly disclosing this privacy vulnerability, and outline some mitigations that Apple and Wi-Fi access point manufacturers have implemented both independently and as a result of our work.

When a root certificate authority (CA) in the Web PKI misbehaves, primary root-store operators such as Mozilla and Google respond by distrusting that CA. However, full distrust is often too broad, so root stores often implement partial distrust of roots, such as only accepting a root for a subset of domains. Unfortunately, derivative root stores (e.g., Debian and Android) that mirror decisions made by primary root stores are often out-of-date and cannot implement partial distrust, leaving TLS applications vulnerable.

In-network devices around the world monitor and tamper with connections for many reasons, including intrusion prevention, combating spam or phishing, and country-level censorship. Connection tampering seeks to block access to specific domain names or keywords, and it affects billions of users worldwide with little-to-no transparency. To detect, diagnose, and measure connection-level blocking, "active" measurement techniques originate queries with domains or keywords believed to be blocked and send them from vantage points within networks of interest. Active measurement efforts have been critical to understanding how traffic tampering occurs, but they inherently are unable to capture critical parts of the picture. For instance, knowing the set of domains in a block-list (i.e., what could get blocked) is not the same as knowing what real users are actively experiencing (i.e., what is actively getting blocked).

Today's network measurements rely heavily on Internet-wide scanning, employing tools like ZMap that are capable of quickly iterating over the entire IPv4 address space. Unfortunately, IPv6's vast address space poses an existential threat for Internet-wide scans and traditional network measurement techniques. To address this reality, efforts are underway to develop "hitlists" of known-active IPv6 addresses to reduce the search space for would-be scanners. As a result, there is an inexorable push for constructing as large and complete a hitlist as possible.

In the United States, items in police possession are often sold at auction if they are not claimed. This includes cellphones that the police obtained through civil asset forfeiture, that were stolen, or that were turned in to lost-and-found. Thousands of US police departments partner with a website, PropertyRoom, to auction their items. Over the course of several months, we purchased 228 cellphones from PropertyRoom to ascertain whether they contained personal information. Our results show that a shocking amount of sensitive, personal information is easily accessible, even to a "low-effort" adversary with no forensics expertise: 21.5% of the phones we purchased were not locked at all, another 4.8% used top-40 most common PINs and patterns, and one phone had a sticky-note from the police with the PIN on it. We analyze the content on the 61 phones we could access, finding sensitive information about not only the phones’ previous owners, but also about their personal contacts, and in some cases, about victims of those persons’ crimes. Additionally, we analyze approximately two years of PropertyRoom cellphone auctions, finding multiple instances of identifying information in photos of the items being auctioned, including sticky-notes with PINs, owners’ names and phone numbers, and evidence stickers that reveal how the phones were obtained and the names of the officers who obtained them. Our work shows that police procedures and phone auctions can be a significant source of personal information leakage and re-victimization. We hope that our work is a call to arms to enforce new policies that either prohibit the selling of computing devices containing user information, or at the very least impose requirements to wipe phones in a manner that the US federal government already employs.

Since 2006, Turkmenistan has been listed as one of the few Internet enemies by Reporters without Borders due to its extensively censored Internet and strictly regulated information control policies. Existing reports of filtering in Turkmenistan rely on a handful of vantage points or test a small number of websites. Yet, the country’s poor Internet adoption rates and small population can make more comprehensive measurement challenging. With a population of only six million people and an Internet penetration rate of only 38%, it is challenging to either recruit in-country volunteers or obtain vantage points to conduct remote network measurements at scale.

This paper proposes using a logic programming language to disentangle X.509 certificate validation policy from mechanism. Expressing validation policies in a logic programming language provides multiple benefits. First, policy and mechanism can be more independently written, augmented, and analyzed compared to the current practice of interweaving them within a C or C++ implementation. Once written, these policies can be easily shared and modified for use in different TLS clients. Further, logic programming allows us to determine when clients differ in their policies and use the power of imputation to automatically generate interesting certificates, e.g., a certificate that will be accepted by one browser but not by another.

TLS certificate pinning is a security mechanism used by applications (apps) to protect their network traffic against malicious certificate authorities (CAs), in-path monitoring, and other methods of TLS tampering. Pinning can provide enhanced security to defend against malicious third-party access to sensitive data in transit (e.g., to protect sensitive banking and health care information), but can also hide an app's personal data collection from users and auditors. Prior studies found pinning was rarely used in the Android ecosystem, except in high-profile, security-sensitive apps; and, little is known about its usage on iOS and across mobile platforms.

One widespread, but frequently overlooked, source of security information is influencer marketing ads on YouTube for security and privacy products such as VPNs. This paper examines how widespread these ads are, where on YouTube they are found, and what kind of information they convey. Starting from a random sample of 1.4% of YouTube, we identify 243 videos containing VPN ads with a total of 63 million views. Using qualitative analysis, we find that these ads commonly discuss broad security guarantees as well as specific technical features, frequently focus on internet threats, and sometimes emphasize accessing otherwise unavailable content. Different VPN companies tend to advertise in different categories of channels and emphasize different messages. We find a number of potentially misleading claims, including overpromises and exaggerations that could negatively influence viewers’ mental models of internet safety.

The couplings between IP addresses, names of content or services, and socket interfaces, are too tight. This impedes system manageability, growth, and overall provisioning. In turn, large-scale content providers are forced to use staggering numbers of addresses, ultimately leading to address exhaustion (IPv4) and inefficiency (IPv6).

Tor is a powerful and important tool for providing anonymity and censorship resistance to users around the world. Yet it is surprisingly difficult to deploy new services in Tor—it is largely relegated to proxies and hidden services—or to nimbly react to new forms of attack. Conversely, “non-anonymous” Internet services are thriving like never before because of recent advances in programmable networks, such as Network Function Virtualization (NFV) which provides programmable in-network middleboxes.

Tor is a powerful and important tool for providing anonymity and censorship resistance to users around the world. Yet it is surprisingly difficult to deploy new services in Tor---it is largely relegated to proxies and hidden services---or to nimbly react to new forms of attack. Conversely, "non-anonymous" Internet services are thriving like never before because of recent advances in programmable networks, such as Network Function Virtualization (NFV) which provides programmable in-network middleboxes.

Decades of work on censorship evasion have resulted in myriad ways to empower clients with the ability to access censored content, but to our knowledge all of them have required some degree of client-side participation. Having to download and run anti-censorship software can put users at risk, and does not help the many users who do not even realize they are being censored in the first place.

Typical security contests focus on breaking or mitigating the impact of buggy systems. We present the Build-it, Break-it, Fix-it (BIBIFI) contest, which aims to assess the ability to securely build software, not just break it. In BIBIFI, teams build specified software with the goal of maximizing correctness, performance, and security. The latter is tested when teams attempt to break other teams’ submissions. Winners are chosen from among the best builders and the best breakers. BIBIFI was designed to be open-ended—teams can use any language, tool, process, and so on, that they like. As such, contest outcomes shed light on factors that correlate with successfully building secure software and breaking insecure software. We ran three contests involving a total of 156 teams and three different programming problems. Quantitative analysis from these contests found that the most efficient build-it submissions used C/C++, but submissions coded in a statically type safe language were 11× less likely to have a security flaw than C/C++ submissions. Break-it teams that were also successful build-it teams were significantly better at finding security bugs.

Researchers and censoring regimes have long engaged in a cat-and-mouse game, leading to increasingly sophisticated Internet-scale censorship techniques and methods to evade them. In this paper, we take a drastic departure from the previously manual evade-detect cycle by developing techniques to automate the discovery of censorship evasion strategies. We present Geneva, a novel genetic algorithm that evolves packet-manipulation-based censorship evasion strategies against nation-state level censors. Geneva composes, mutates, and evolves sophisticated strategies out of four basic packet manipulation primitives (drop, tamper headers, duplicate, and fragment). With experiments performed both in-lab and against several real censors (in China, India, and Kazakhstan), we demonstrate that Geneva is able to quickly and independently re-derive most strategies from prior work, and derive novel subspecies and altogether new species of packet manipulation strategies. Moreover, Geneva discovers successful strategies that prior work posited were not effective, and evolves extinct strategies into newly working variants. We analyze the novel strategies Geneva creates to infer previously unknown behavior in censors. Geneva is a first step towards automating censorship evasion; to this end, we have made our code and data publicly available.

The public key infrastructure (PKI) provides the fundamental property of authentication: the means by which users can know with whom they are communicating online. The PKI ensures end-to-end authenticity insofar as it verifies a chain of certificates, but the true final step in end-to-end authentication comes when the user verifies that the website is what they expect. To this end, users are expected to evaluate domain names, but various "domain impersonation" attacks threaten their ability to do so. Indeed, if a user could be easily tricked into believing that amazon.com-offers.com is actually amazon.com, then, coupled with security indicators like a lock icon, users could believe that they have a secure connection to Amazon.

Despite its critical role in Internet connectivity, the Border Gateway Protocol (BGP) remains highly vulnerable to attacks such as prefix hijacking, where an Autonomous System (AS) announces routes for IP space it does not control. To address this issue, the Resource Public Key Infrastructure (RPKI) was developed starting in 2008, with deployment beginning in 2011. This paper performs the first comprehensive, longitudinal study of the deployment, coverage, and quality of RPKI. We use a unique dataset containing all RPKI Route Origin Authorizations (ROAs) from the moment RPKI was first deployed, more than 8 years ago. We combine this dataset with BGP announcements from more than 3,300 BGP collectors worldwide. Our analysis shows the after a gradual start, RPKI has seen a rapid increase in adoption over the past two years. We also show that although misconfigurations were rampant when RPKI was first deployed (causing many announcements to appear as invalid) they are quite rare today. We develop a taxonomy of invalid RPKI announcements, then quantify their prevalence. We further identify suspicious announcements indicative of prefix hijacking and present case studies of likely hijacks. Overall, we conclude that while misconfigurations still do occur, RPKI is "ready for the big screen," and routing security can be increased by dropping invalid announcements. To foster reproducibility and further studies, we release all RPKI data and the tools we used to analyze it into the public domain.

Weather is a leading threat to the stability of our vital infrastructure. Last-mile Internet is no exception. Yet, unlike other vital infrastructure, weather's effect on last-mile Internet outages is not well understood. This work is the first attempt to quantify the effect of weather on residential outages.

Internet anycast depends on inter-domain routing to direct clients to their "closest" sites. Using data collected from a root DNS server for over a year (400M+ queries/day from 100+ sites), we characterize the load balancing and latency performance of global anycast. Our analysis shows that site loads are often unbalanced, and that most queries travel longer than necessary, many by over 5000 km.

As blockchain technologies and cryptocurrencies increase in popularity, their decentralization poses unique challenges in network partitions. In traditional distributed systems, network partitions are generally a result of bugs or connectivity failures; the typical goal of the system designer is to automatically recover from such issues as seamlessly as possible. Blockchain-based systems, however, rely on purposeful "forks" to roll out protocol changes in a decentralized manner. Not all users may agree with proposed changes, and thus forks can persist, leading to permanent network partitions. In this paper, we closely study the large-scale fork that occurred in Ethereum, a new blockchain technology that allows for both currency transactions and smart contracts. Ethereum is currently the second-most-valuable cryptocurrency, with a market capitalization of over $28B. We explore the consequences of this fork, showing the impact on the two networks and their mining pools, and how the fork lead to unintentional incentives and security vulnerabilities.

The Domain Name System (DNS) provides a scalable, flexible name resolution service. Unfortunately, its unauthenticated architecture has become the basis for many security attacks. To address this, DNS Security Extensions (DNSSEC) were introduced in 1997. DNSSEC's deployment requires support from the top-level domain (TLD) registries and registrars, as well as participation by the organization that serves as the DNS operator. Unfortunately, DNSSEC has seen poor deployment thus far: despite being proposed nearly two decades ago, only 1% of .com, .net, and .org domains are properly signed.

Currently, no major browser fully checks for TLS/SSL certificate revocations. This is largely due to the fact that the deployed mechanisms for disseminating revocations (CRLs, OCSP, OCSP Stapling, CRLSet, and OneCRL) are each either incomplete, insecure, inefficient, slow to update, not private, or some combination thereof. In this paper, we present CRLite, an efficient and easily-deployable system for proactively pushing all TLS certificate revocations to browsers. CRLite servers aggregate revocation information for all known, valid TLS certificates on the web, and store them in a space-efficient filter cascade data structure. Browsers periodically download and use this data to check for revocations of observed certificates in real-time. CRLite does not require any additional trust beyond the existing PKI, and it allows clients to adopt a fail-closed security posture even in the face of network errors or attacks that make revocation information temporarily unavailable. We present a prototype of name that processes TLS certificates gathered by Rapid7, the University of Michigan, and Google's Certificate Transparency on the server-side, with a Firefox extension on the client-side. Comparing CRLite to an idealized browser that performs correct CRL/OCSP checking, we show that CRLite reduces latency and eliminates privacy concerns. Moreover, CRLite has low bandwidth costs: it can represent all certificates with an initial download of 10 MB (less than 1 byte per revocation) followed by daily updates of 580 KB on average. Taken together, our results demonstrate that complete TLS/SSL revocation checking is within reach for all clients.

The semantics of online authentication in the web are rather straightforward: if Alice has a certificate binding Bob's name to a public key, and if a remote entity can prove knowledge of Bob's private key, then (barring key compromise) that remote entity must be Bob. However, in reality, many websites' and the majority of the most popular ones-are hosted at least in part by third parties such as Content Delivery Networks (CDNs) or web hosting providers. Put simply: administrators of websites who deal with (extremely) sensitive user data are giving their private keys to third parties. Importantly, this sharing of keys is undetectable by most users, and widely unknown even among researchers. In this paper, we perform a large-scale measurement study of key sharing in today's web. We analyze the prevalence with which websites trust third-party hosting providers with their secret keys, as well as the impact that this trust has on responsible key management practices, such as revocation. Our results reveal that key sharing is extremely common, with a small handful of hosting providers having keys from the majority of the most popular websites. We also find that hosting providers often manage their customers' keys, and that they tend to react more slowly yet more thoroughly to compromised or potentially compromised keys.

Typical security contests focus on breaking or mitigating the impact of buggy systems. We present the Build-it, Break-it, Fix-it (BIBIFI) contest, which aims to assess the ability to securely build software, not just break it. In BIBIFI, teams build specified software with the goal of maximizing correctness, performance, and security. The latter is tested when teams attempt to break other teams' submissions. Winners are chosen from among the best builders and the best breakers. BIBIFI was designed to be open-ended-teams can use any language, tool, process, etc. that they like. As such, contest outcomes shed light on factors that correlate with successfully building secure software and breaking insecure software. During 2015, we ran three contests involving a total of 116 teams and two different programming problems. Quantitative analysis from these contests found that the most efficient build-it submissions used C/C++, but submissions coded in other statically-typed languages were less likely to have a security flaw; build-it teams with diverse programming-language knowledge also produced more secure code. Shorter programs correlated with better scores. Break-it teams that were also successful build-it teams were significantly better at finding security bugs.

Cloud computing has evolved to meet user demands, from arbitrary VMs offered by IaaS to the narrow application interfaces of PaaS. Unfortunately, there exists an intermediate point that is not well met by today's offerings: users who wish to run arbitrary, already available binaries (as opposed to rewriting their own application for a PaaS) yet expect their applications to be long-lived but mostly idle (as opposed to the always-on VM of IaaS). For example, end users who wish to run their own email or DNS server.

Tor is a peer-to-peer overlay routing network that achieves unlinkable communication between source and destination.Unlike traditional mix-nets, Tor seeks to balance anonymity and performance, particularly with respect to providing low-latency communication. As a result, understanding the latencies between peers in the Tor network could be an extremely powerful tool in understanding and improving Tor's performance and anonymity properties. Unfortunately, there are no practical techniques for inferring accurate latencies between two arbitrary hosts on the Internet, and Tor clients are not instrumented to collect and report on these measurements. In this paper, we present Ting, a technique for measuring latencies between arbitrary Tor nodes from a single vantage point. Through a ground-truth validation, we show that Ting is accurate, even with few samples, and does not require modifications to existing clients. We also apply Ting to the live Tor network, and show that its measurements are stable over time. We demonstrate that the all-pairs latency datasets that Ting permits can be applied in disparate ways, including faster methods of deanonymizing Tor circuits and efficiently finding long circuits with low end-to-end latency.

Critical to the security of any public key infrastructure (PKI) is the ability to revoke previously issued certificates. While the overall SSL ecosystem is well-studied, the frequency with which certificates are revoked and the circumstances under which clients (e.g., browsers) check whether certificates are revoked are still not well-understood.

There are several mechanisms by which users can gain insight into where their packets have gone, but no mechanisms allow users undeniable proof that their packets did not traverse certain parts of the world while on their way to or from another host. This paper introduces the problem of finding "proofs of avoidance": evidence that the paths taken by a packet and its response avoided a user-specified set of "forbidden" geographic regions. Proving that something did not happen is often intractable, but we demonstrate a low-overhead proof structure built around the idea of what we call "alibis": relays with particular timing constraints that, when upheld, would make it impossible to traverse both the relay and the forbidden regions.

The ability to revoke certificates is a fundamental feature of a public key infrastructure. However, certificate revocation systems are generally regarded as ineffective and potentially insecure: Some browsers bundle revocation updates with more general software updates, and may go hours, days, or indefinitely between updates; moreover, some operating systems make it difficult for users to demand recent revocation data. This paper argues that this sad state of affairs is an inexorable consequence of relying on unicast communication to distribute revocation information. We present RevCast, a broadcast system that disseminates revocation data in a timely and private manner. RevCast is not emulated broadcast over traditional Internet links, but rather a separate metropolitan-area wireless broadcast link; specifically, we have designed RevCast to operate over existing FM radio, although the principles apply to alternative implementations. We present the design, implementation, and initial deployment of RevCast on a 3 kW commercial radio station using the FM RDS protocol. With the use of two types of receivers (an RDS-to-LAN bridge that we have prototyped and an RDS-enabled smartphone), we show that, even at a low bitrate, RevCast is able to deliver complete and timely revocation information, anonymously, even for receivers who do not receive all packets all the time.

Central to the secure operation of a public key infrastructure (PKI) is the ability to revoke certificates. While much of users' security rests on this process taking place quickly, in practice, revocation typically requires a human to decide to reissue a new certificate and revoke the old one. Thus, having a proper understanding of how often systems administrators reissue and revoke certificates is crucial to understanding the integrity of a PKI. Unfortunately, this is typically difficult to measure: while it is relatively easy to determine when a certificate is revoked, it is difficult to determine whether and when an administrator should have revoked.

On January 3, 2013, the D-root DNS server hosted at the University of Maryland changed IP address. To avoid service disruption, the old address continues to answer queries. In this paper, we perform an initial investigation of the traffic at both the new and old addresses before, during, and since the flag day. The data we collected show non-obvious behavior: the overall query volume to the D-roots increases by roughly 50%, the old address continues to receive a high volume of queries months after the changeover, and far more queries to the old address succeed than those to the new one. Our analysis provides a window into how compliant resolvers change over and how non-standard and seemingly malicious resolvers react (or not) to the IP address change. We provide evidence that a relatively small number of implementation errors account for nearly all discrepancies that are not misconfigurations or attacks.

We study the throughput capacity of wireless networks which employ (asynchronous) random-access scheduling as opposed to deterministic scheduling. The central question we answer is: how should we set the channel-access probability for each link in the network so that the network operates close to its optimal throughput capacity? We design simple and distributed channel-access strategies for random-access networks which are provably competitive with respect to the optimal scheduling strategy, which is deterministic, centralized, and computationally infeasible. We show that the competitiveness of our strategies are nearly the best achievable via random-access scheduling, thus establishing fundamental limits on the performance of random- access. A notable outcome of our work is that random access compares well with deterministic scheduling when link transmission durations differ by small factors, and much worse otherwise. The distinguishing aspects of our work include modeling and rigorous analysis of asynchronous communication, asymmetry in link transmission durations, and hidden terminals under arbitrary link-conflict based wireless interference models.

Incentives play a crucial role in BitTorrent, motivating users to upload to others to achieve fast download times for all peers. Though long believed to be robust to strategic manipulation, recent work has empirically shown that BitTorrent does not provide its users incentive to follow the protocol. We propose an auction-based model to study and improve upon BitTorrent's incentives. The insight behind our model is that BitTorrent uses, not tit-for-tat as widely believed, but an auction to decide which peers to serve. Our model not only captures known, performance-improving strategies, it shapes our thinking toward new, effective strategies. For example, our analysis demonstrates, counter-intuitively, that BitTorrent peers have incentive to intelligently under-report what pieces of the file they have to their neighbors. We implement and evaluate a modification to BitTorrent in which peers reward one another with proportional shares of bandwidth. Within our game-theoretic model, we prove that a proportional-share client is strategy-proof. With experiments on PlanetLab, a local cluster, and live downloads, we show that a proportional-share unchoker yields faster downloads against BitTorrent and BitTyrant clients, and that under-reporting pieces yields prolonged neighbor interest.

We present a protocol to construct routing backbones in wireless networks composed of selfish participants. Backbones are inherently cooperative, so constructing them in selfish environments is particularly difficult; participants want a backbone to exist (soothers relay their packets) but do not want to join the backbone (so they do not have to relay packets for others).