Search for: All records

Can we make a denial-of-service attacker pay more than the server and honest clients? Consider a model where a server sees a stream of jobs sent by either honest clients or an adversary. The server sets a price for servicing each job with the aid of an estimator, which provides approximate statistical information about the distribution of previously occurring good jobs. We describe and analyze pricing algorithms for the server under different models of synchrony, with total cost parameterized by the accuracy of the estimator. Given a reasonably accurate estimator, the attacker’s cost grows asymptotically faster than our algorithm’s cost. Additionally, we prove a lower bound, showing that our pricing algorithm yields asymptotically tight results when the estimator is accurate within constant factors. 

Peer-to-peer networks are typically defended against adversarial attack by maintaining small groups of peers, each with a good majority. Unfortunately, maintaining a good majority is challenging in the presence of churn. A popular defense against churn is periodic shuffling: replacing all peers in the group after a certain number of peer additions and deletions. Unfortunately, shuffling is expensive. Peer relocations degrade performance by requiring peers to add and delete communication links, transfer content to maintain search correctness, and frequently update routing tables to avoid stale routing information. These problems are compounded by the fact that all current shuffling algorithms require shuffling even when the system is not under attack. Here, we present SPARSE-SHUFFLE, a shuffling defense that asymptotically matches adversarial cost. Given B adversarial insertions and deletions, our algorithm preserves good majorities in every group with only O(B) relocations of good peers. In particular, no shuffles occur in the absence of attack, and the shuffling cost grows linearly with the attacker's actions. 

We consider the problem of defending a hash table against a Byzantine attacker that is trying to degrade the performance of query, insertion and deletion operations. Our defense makes use of resource burning (RB)—the verifiable expenditure of network resources—where the issuer of a request incurs some RB cost. Our algorithm, Depth Charge, charges RB costs for operations based on the depth of the appropriate object in the list that the object hashes to in the table. By appropriately setting the RB costs, our algorithm mitigates the impact of an attacker on the hash table’s performance. In particular, in the presence of a significant attack, our algorithm incurs a cost which is asymptotically less that the attacker’s cost. 

Contention resolution addresses the challenge of coordinating access by multiple processes to a shared resource such as memory, disk storage, or a communication channel. Originally spurred by challenges in database systems and bus networks, contention resolution has endured as an important abstraction for resource sharing, despite decades of technological change. Here, we survey the literature on resolving worst-case contention, where the number of processes and the time at which each process may start seeking access to the resource is dictated by an adversary. We also highlight the evolution of contention resolution, where new concerns—such as security, quality of service, and energy efficiency—are motivated by modern systems. These efforts have yielded insights into the limits of randomized and deterministic approaches, as well as the impact of different model assumptions such as global clock synchronization, knowledge of the number of processors, feedback from access attempts, and attacks on the availability of the shared resource.