Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

A Novel Puzzle-Based Framework for Mitigating Distributed Denial of Service Attacks Against Internet Applications

Abliz, Mehmud (2015) A Novel Puzzle-Based Framework for Mitigating Distributed Denial of Service Attacks Against Internet Applications. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

Submitted Version

Download (4MB)


Cryptographic puzzles are promising techniques for mitigating DDoS attacks via decreasing the incoming rate of service eligible requests. However, existing cryptographic puzzle techniques have several shortcomings that make them less appealing as a tool of choice for DDoS defense. These shortcomings include: (1) the lack of accurate models for dynamically determining puzzle hardness; (2) the lack of an efficient and effective counter mechanism for puzzle solution replay attacks; and (3) the wastefulness of the puzzle computations in terms of the clients' computational resources. In this thesis, we provide a puzzle based DDoS defense framework that addresses these shortcomings.

Our puzzle framework includes three novel puzzle mechanisms. The first mechanism, called Puzzle+, provides a mathematical model of per-request puzzle hardness. Through extensive experimental study, we show that this model optimizes the effectiveness of puzzle based DDoS mitigation while enabling tight control over the server utilization. In addition, Puzzle+ disables puzzle solution replay attacks by utilizing a novel cache algorithm to detect replays.

The second puzzle mechanism, called Productive Puzzles, alleviates the wastefulness of computational puzzles by transforming the puzzle computations into computations of meaningful tasks that provide utility. Our third puzzle mechanism, called Guided Tour Puzzles, eliminates the wasteful puzzle computations all together, and adopts a novel delay-based puzzle construction idea. In addition, it is not affected by the disparity in the computational resources of the client machines that perform the puzzle computations. Through measurement analysis on real network testbeds as well as extensive simulation study, we show that both Productive Puzzles and Guided Tour Puzzles achieve effective mitigation of DDoS attacks while satisfying no wasteful computation requirement.

Lastly, we introduce a novel queue management algorithm, called Stochastic Fair Drop Queue (SFDQ), to further strengthen the DDoS protection provided by the puzzle framework. SFDQ is not only effective against DDoS attacks at multiple layers of the protocol stack, it is also simple to configure and deploy. SFDQ is implemented over a novel data structure, called Indexed Linked List, to provide enqueue, dequeue, and remove operations with O(1) time complexity.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Abliz, Mehmudmaa78@pitt.eduMAA78
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairZnati, Taiebznati@cs.pitt.eduZNATI
Committee MemberMelhem, Ramimelhem@cs.pitt.eduMELHEM
Committee MemberZhang, Youtaozhangyt@cs.pitt.eduYOUTAO
Committee MemberKrishnamurthy, Prashantprashk@pitt.eduPRASHK
Date: 11 June 2015
Date Type: Publication
Defense Date: 15 April 2015
Approval Date: 11 June 2015
Submission Date: 17 April 2015
Access Restriction: 1 year -- Restrict access to University of Pittsburgh for a period of 1 year.
Number of Pages: 157
Institution: University of Pittsburgh
Schools and Programs: Dietrich School of Arts and Sciences > Computer Science
Degree: PhD - Doctor of Philosophy
Thesis Type: Doctoral Dissertation
Refereed: Yes
Uncontrolled Keywords: Internet, availability, denial of service, distributed denial of service, replay attacks, cryptographic puzzles, tour puzzles, productive puzzles, stochastic fair drop, fair resource allocation, filtering, auto expire cache, indexed linked list
Date Deposited: 11 Jun 2015 20:21
Last Modified: 15 Nov 2016 14:27


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item