Noniterative algorithms for sensitivity analysis attacks

Sensitivity analysis attacks constitute a powerful family of watermark "removal" attacks. They exploit vulnerability in some watermarking protocols: the attacker's unlimited access to the watermark detector. This paper proposes a mathematical framework for designing sensitivity analysis attacks and focuses on additive spread-spectrum embedding schemes. The detectors under attack range in complexity from basic correlation detectors to normalized correlation detectors and maximum-likelihood (ML) detectors. The new algorithms precisely estimate and then eliminate the watermark from the watermarked signal. This is accomplished by exploiting geometric properties of the detection boundary and the information leaked by the detector. Several important extensions are presented, including the case of a partially unknown detection function, and the case of constrained detector inputs. In contrast with previous art, our algorithms are noniterative and require, at most, O(n) detection operations in order to precisely estimate the watermark, where n is the dimension of the signal. The cost of each detection operation is O(n); hence, the algorithms can be executed in quadratic time. The method is illustrated with an application to image watermarking using an ML detector based on a generalized Gaussian model for images.