Detecting dependencies among network services has been well-studied in previous research. Previous attempts at service dependency detection fall into two classes: active and passive approaches. While passive approaches suffer from high false positives, active approaches suffer from applicability problems.
In this paper, we design a new application-independent active approach for detecting dependencies among services. We present a traffic watermarking approach with arbitrarily low false positives and easy applicability. Our approach does not need any modifications to or implementation details about the existing network services. We provide ways to watermark sets of network flows and later detect these watermarks dependably. We provide statistical tests for detecting watermarked flows, and we compute the false positive and false negative rates of these tests both analytically and experimentally. We also provide a set of criteria for the evaluation of dependency detection approaches and compare our approach to previous ones using these criteria. Furthermore, we implemented the proposed watermarking system (Rippler) in a small university lab network. We ran our system for four months and detected 38 otherwise hidden dependencies among 54 services. Finally, we compared the efficiency of our approach against three previous systems by testing them on this real-world network data.