In this work we present a Multi-flow Attack Resistant Interval Centroid Based Watermarking (MAR-ICBW) scheme for network flows. Our proposed scheme can withstand the newly introduced multi-flow watermarking attack that defeats the state-of-the-art interval-based network flow watermarking schemes. Multi-flow attack uses the dependent correlations among the flows marked with the same watermark to recover the secret parameters, and remove the watermark from a flow. The attack can be effective even if different flows are marked with different values of a watermark. MAR-ICBW survives the attack by virtue of randomizing the location of the embedded watermark across multiple flows and therefore, effectively removing the correlations between the flows. While we represent our counter measure to multi-flow attack in terms of an improved version of ICBW, the same methodology can be used to strengthen other interval-based flow watermarking schemes.