  Linking network flows is an important problem in intrusion detection as well
as anonymity. Passive traffic analysis can link flows but requires long periods
of observation to reduce errors. Active traffic analysis, also known as flow
watermarking, allows for better precision and is more scalable. Previous flow
watermarks introduce significant delays to the traffic flow as a side effect of
using a blind detection scheme; this enables attacks that detect and remove the
watermark, while at the same time slowing down legitimate traffic. We propose
the first non-blind approach for flow watermarking, called RAINBOW, that
improves watermark invisibility by inserting delays hundreds of times smaller
than previous blind watermarks, hence reduces the watermark interference on
network flows. We derive and analyze the optimum detectors for RAINBOW as well
as the passive traffic analysis under different traffic models by using
hypothesis testing. Comparing the detection performance of RAINBOW and the
passive approach we observe that both RAINBOW and passive traffic analysis
perform similarly good in the case of uncorrelated traffic, however, the
RAINBOW detector drastically outperforms the optimum passive detector in the
case of correlated network flows. This justifies the use of non-blind
watermarks over passive traffic analysis even though both approaches have
similar scalability constraints. We confirm our analysis by simulating the
detectors and testing them against large traces of real network flows.
