Design, analysis, and implementation of effective network flow watermarking scheme

Linking network flows is an important problem in several security-related applications including intrusion detection and anonymity. The flows of interest in these applications are commonly relayed by several low-latency nodes, and each node adds an extra/different layer of encryption to the traffic payload. As a result, in such applications it is infeasible to link network flows by correlating their packet headers and payloads. Traffic analysis is a powerful tool in this scenario, as it correlates network flows based on their communication patterns, which are not changed due to encryption and low-latency communications.;Traditional traffic analysis is performed in a passive manner; flow patterns are only observed and correlated among different flows to find flow relations. The patterns used more commonly for traffic analysis are packet timings, sizes, and counts. The main shortcoming of passive traffic analysis is not being scalable to large-size applications. For a network with n ingress flows and m egress flows passive traffic analysis needs to perform O( mn) flow correlations, and O(n) flows need to be communicated among traffic analysis entities. To overcome this limitation, recent research introduces an active form for traffic analysis, called flow watermarking. Flow watermarking works by first perturbing network flows and then observing network flows, looking for the specific perturbation patterns in order to link flows. This reduces the computational overhead to O(n) (from O(mn) for non-targeted passive analysis) and the communication overhead to O(1) (from O(n) in the case of non-targeted passive analysis), since the information used for flow linking, the watermark, is self-contained in each flow. In addition to being more scalable (in the case of non-targeted traffic analysis), active traffic analysis can provide lower false-positive rates than passive traffic analysis in linking network flows. This is because passive analysis works by correlating flow patterns that can be intrinsically correlated among non-linked flows, whereas active traffic analysis correlates artificial patterns that are tailored to be highly uncorrelated among non-linked flows.;In this thesis we study the design, analysis, and implementation of network flow watermarks. Our research is motivated by two main issues with existing flow watermarks: i) previous flow watermarks are not efficient, meaning that they need very long network flows in order to successfully detect watermarked flows, and, ii) previous watermarks are not invisible, meaning that non-watermarking entities (e.g., users, attackers) can tell if a flow has been watermarked. In particular, we design an attack, called multi-flow attack, that works on several previously proposed flow watermarks. Our multi-flow attack is able to distinguish watermarked flows and remove the watermark by observing a handful of watermarked flows.;We also design two new flow watermarking systems. We design RAINBOW, a non-blind network flow watermark. RAINBOW is able to perform very reliable traffic analysis by applying tiny perturbations to packet timings. We also design a blind flow watermark, SWIRL, that inserts watermarks that are flow-dependent. For both of the proposed schemes, we analyze their detection performance both theoretically and through experiments. We also evaluate watermark invisibility for both of the schemes.;A flow watermark inserts a single bit of information on flows, carrying the message that these flows have been observed previously. However, in some applications more information needs to be piggybacked on network flows, giving information about the location they were observed, the entity who tagged them, etc. We call such tags composed of several bits of information flow fingerprints. We design a flow fingerprinting system, called Fancy, that is able to send tens of bits of information reliably using fairly short length of network flows.;Finally, we introduce two new applications for network flow watermarking. The first application uses flow watermarks to detect botmasters and infected machines corresponding to a centralized botnet, i.e., an IRC botnet. We also propose to use our SWIRL watermark to mitigate a threat against the Tor anonymity system, the Tor congestion attack.