Gatling: Automatic Attack Discovery in Large-Scale Distributed Systems (NDSS 2012)

Most distributed systems are designed to meet application-prescribed metrics that ensure availability and high-performance for practical usage. However compromised participants can manipulate protocol semantics through attacks that target the messages exchanged with honest nodes and degrade performance significantly. To date, finding attacks against performance has been primarily a manual task due to both the difficulty of expressing performance as an invariant in the system and the state-space explosion that occurs as attackers are more realistically modeled. Our design goal is to find performance attacks automatically requiring the least amount of user effort.

In our paper, we propose Gatling, a framework that automatically finds performance attacks caused by insider attackers in large-scale message-passing distributed systems. We define performance attacks as following; malicious nodes deviate from the protocol when sending or creating messages, with the goal of degrading system performance. Gatling is a framework that combines a model checker and simulator environment with a fault injector to find performance attacks in event-based message passing distributed systems.

We identify basic malicious message delivery and message lying actions that insider attackers can use to create attacks.  Malicious message delivery actions are about how the message is delivered and set of actions we provide are: message dropping, duplicating and delaying.  In lying actions, malicious nodes modify what the content of the message is. To make the lying action more effective and to reduce search space, Gatling lies about fields based on the type of the field, which is much more sophisticated attack than random bit-flipping. While these lying actions are protocol dependent, requiring the format and meaning of messages, Gatling captures them without needing to modify the target system, by using a type-aware compiler.  And we design a greedy search algorithm that finds effective attacks consisting of a subset of these malicious actions.

We design an attack discovery algorithm that uses a greedy search approach based on an impact score that measures attack effectiveness. In our greedy algorithm, we run for each branch for a short window time and select the biggest impact and build up. Gatling works for a large class of distributed systems and does not require the user to write a malicious implementation. While Gatling does not fix attacks nor prove their absence, it provides the user with protocol-level semantic meaning about the discovered attacks.

We implement Gatling for the Mace toolkit and applied it to six systems: a virtual coordinate system (Vivaldi), a distributed hash table lookup service and application (Chord and DHTApp), two multicast systems (ESM and Scribe) and one file sharing application(BulletPrime). We found a total of 41 attacks, ranging from a taking few minutes to a few hours to find each attack.

Hyojeong Lee, Jeff Seibert, Charles Killian, and Cristina Nita-Rotaru. “Gatling: Automatic Attack Discovery in Large-Scale Distributed Systems”, In proceedings of 19th Annual Network & Distributed System Security Symposium (NDSS 2012). San Diego, CA. (to appear) 5-8 February, 2012

This entry was posted in Papers. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>