Despite their popularity, spread spectrum techniques have been proven to be vulnerable to sensitivity analysis attacks. Moreover, the number of detection operations needed by the attacker to estimate the watermark is generally linear in the size of the signal available to him. This holds not only for a simple correlation detector, but also for a wide class of detectors. Therefore there is a vital need for more secure detection methods. In this paper, we propose a randomized detection method that increases the robustness of spread spectrum embedding schemes. However, this is achieved at the expense of detection performance. For this purpose, we provide a framework to study the tradeoff between these two factors using classical detection-theoretic tools: large deviation analysis and Chernoff bounds. To gain more insight into the practical value of this framework, we apply it to image signals, for which "good" statistical models are available.