Fortifying Time Series: DTW-Certified Robust Anomaly Detection

We sincerely thank the reviewer for the valuable feedback provided. Below, we clarify and address each concern in detail:

Q1 As shown in Figure 2, the DTW-based certification process uses an analytical solution that introduces no computational overhead. The observed slowdown arises from the Monte Carlo sampling step, which increases inference time roughly in proportion to the number of noisy samples $n$ (e.g., $n$=1000). The parameter $n$ is user-configurable: larger values yield more precise estimates and typically result in a larger certified radius.

We would like to note that such overhead is intrinsic to all randomized smoothing methods [32][18][55], reflecting a fundamental trade-off for significantly stronger robustness guarantees. Nevertheless, randomized smoothing is one of the most efficient and scalable approaches compared to other certified robustness methods [18]. Our method does not incur any additional cost beyond that of standard randomized smoothing, and reducing sample complexity remains an active research direction. In practice, the overhead can be substantially reduced through parallelization using multiple copies of the anomaly detector.

We provide additional results on running time overhead, evaluated in the settings as described in Section 4.

• Normal inference: 1/498s per batch (size 64)
• Inference and Certification: 1.83s per batch (size 64)

Q2 Our method does not require any modification to the training procedure and therefore imposes no computational overhead during training.

Furthermore, we believe our approach can scale to million-scale testing datasets. As evidence, the SMD dataset evaluated in our experiments contains approximately $0.7$ million ($7 x 10^5$) testing timesteps with $25$ channels, and required $3:36:19$ (h:m:s) to complete both inference and certification. The computational overhead at testing time grows linearly with the dataset size, maintaining an inference time complexity of $O(n)$, equivalent to that of a standard model.

Q3 The impact of noisy samples is addressed in Q1. The percentile parameter $p$ has little impact on results as long as it reflects the majority distribution and is not overly influenced by outliers (i.e., extreme values $p = 0.0$ or $p = 1.0$). We will include a more comprehensive ablation study in the camera-ready version to further examine its effect.

We sincerely thank the reviewer again for your time and effort. We hope that our responses have clarified the issues raised.

We sincerely thank the reviewer for the valuable feedback provided. Below, we clarify and address each concern in detail:

Computation overhead: The Monte Carlo sampling introduces computational overhead, slowing inference by approximately a factor of $n$ (the number of noisy samples). The value of $n$ can be user-specified, where a larger $n$ gives a more precise estimation and usually a larger certified radius.

We would like to note that such overhead is intrinsic to all randomized smoothing methods [32][18][55], reflecting a fundamental trade-off for significantly stronger robustness guarantees. Nevertheless, randomized smoothing is still one of the most efficient and scalable approaches compared to other certified robustness methods [18].

Our method does not incur any additional cost beyond that of standard randomized smoothing, and reducing sample complexity remains an active research direction. In practice, the overhead can be substantially reduced through parallelization using multiple copies of the anomaly detector.

We provide additional results on running time overhead, evaluated in the settings as described in Section 4.

• Normal inference: 1/498s per batch (size 64)
• Inference and Certification: 1.83s per batch (size 64)

Attack to bypass this defence: As a certified defense method, we theoretically guarantee that no adversarial attack can bypass our approach as long as the adversarial example x' lies within the certified DTW radius e, i.e., DTW(x, x') < e (see Section 3.1, Threat Model and Certified Defense Goal). An attacker can only compromise the defense by introducing a perturbation exceeding the certified radius.

We sincerely thank the reviewer again for your time and effort. We hope that our responses have clarified the issues raised.

We sincerely thank the reviewer for the valuable feedback provided. Below, we clarify and address each concern in detail:

Concern in Weakness 1 "Comparison with $l_p$-Norm Defenses": As discussed in the Abstract and Introduction (lines 30-49), the inadequacy of existing $l_p$-norm certification methods for time-series data, their poor performance under DTW-based attacks, and the complete absence of any prior certified defense against DTW attacks were the primary motivations for developing our proposed DTW-certified defense. The performance gap between $l_p$-norm certification and our DTW-certified defense validates our assumption and clearly demonstrates the superiority of the proposed approach under realistic DTW-based adversarial scenarios.

Concern in Weakness 2 "Performance Differences Across Datasets": We acknowledge that our certified defense does not achieve identical performance across all datasets. However, it is important to note that no single method/setting achieves optimal performance for all data, and this is a well-known phenomenon in existing certified robustness literature [32][18][55].

As discussed in lines 265-267 & 292-298, the variation arises from differences in dataset characteristics and model architectures, particularly their sensitivity to injected noise. Consequently, tuning the noise level is often necessary to achieve optimal certification performance in each setting. For example, on SMAP (COUTA), the mean certified radius is $0.037$ with a certified proportion of $51.06$% at noise level $0.5$ (Table 1), but improves to a mean radius of $0.202$ and certified proportion of $72.24$% at noise level $2.0$ (Table 2).

Since the primary focus of this work is to introduce a novel DTW-based certified defense, we deliberately reported results at a fixed noise level (Table 1) rather than cherry-picking and tuning hyperparameters for each dataset. Table 2 further demonstrates that, with minor tuning, our method can achieve consistently high certified radii and proportions in most settings.

Concern in Weekness 3 & 6 "Contribution and Difference with [14]": We agree with the first point in Strengths that our main contribution lies in providing a theorem for a more appropriate certified robustness metric, DTW, as formalized in Lemma 3.2 and Theorem 3.3 (Section 3.2). In contrast, the method in [14] applies exclusively to $l_p$-norm metrics.

While we incorporate median smoothing from [14] as part of our anomaly score construction, the certification theorem we propose for DTW is non-trivial. It is the first in the literature to provide a certified guarantee in DTW distance. Importantly, a DTW radius generally encompasses more adversarial examples than an $l_p$-norm radius of the same size, meaning that our DTW certificate cannot be derived through a simple adaptation or trivial combination of existing $l_p$-norm results with DTW definition.

Concern in Weakness 3 "no inf function": In applying median smoothing, we note that the $\sup$ and $\inf$ functions in [14] Definition 1 are equivalent for continuous distributions, as stated in [14] “The inf and sup are equivalent for continuous distributions; the distinction is needed to handle edge cases with discrete distributions.”

Concern in Weakness 4 & 5 "Notation and Citations": We will add the corresponding citations and update the notation in the camera-ready version.

Concern in Limitation "Experimental Validation Across Diverse Methods": We evaluated our method on three representative state-of-the-art (SOTA) anomaly detection models across eight widely used time-series anomaly detection datasets as reported in Section 4. The experimental setup is consistent with best practices in both the time-series anomaly detection [4][58][59] and certified robustness [18][55] communities.

We sincerely thank the reviewer again for your time and effort. We hope that our responses have clarified the issues raised and kindly request your consideration.

We sincerely thank the reviewer for the valuable feedback provided. Below, we clarify and address each concern in detail:

1 Generality to Arbitrary Norm Orders $p$: Our method builds upon Randomized Smoothing, which has been generalized to arbitrary norm orders $p$ in the cited work [73]. In summary, different norm orders can be achieved by adding appropriate noise distributions:

• Gaussian noise for $p = 2$
• Laplace noise for $p = 1$
• Uniform noise for $p = \infty$

The proposed DTW-certificate can likewise be generalized to any norm order $p$ (e.g., $p = 1$) by replacing Gaussian noise with the corresponding distribution (e.g., Laplace noise). Regarding the certification process, Lemma 3.2 and its proof remain valid for arbitrary $p$, and Theorem 3.3 requires the following modifications:

1. Redefine the certified radius $r$ from norm-2 to norm-1.
2. Redefine $R$ from norm-2 to norm-1 as $R = \sum \|\delta_i\|$.
3. In Eq. (15), replace the norm-2 expansion with norm-1 expansion: $r = \sum \|\delta_i\| + \|d\|$.
4. Following the same proof steps, the expression of $e$ in Eq. (10) becomes $e = r - R$.

Given the limited time, we provide initial results for the norm-1 certification of the COUTA model here (align to Table 1, last 6 columns), and will expand on this discussion in greater detail in Sec 4 of the camera-ready.

2 Applicability to Arbitrary Anomaly Score Functions: Our method and Lemma 3.1 impose no smoothness or continuity assumptions on the anomaly score function $f: \mathcal{X} \to \mathbb{R}$. The proposed approach is applicable to any anomaly score function that is used as described in Section 3.1 (Para. Time-series Anomaly Detector), where the anomaly is identified as an anomaly score that exceeds the threshold. This includes the function output with sudden jumps, such as hard thresholds, coarse rounding, or aggressive max-pool operations. This generality follows from our use of a randomized smoothing approach, which can be applied to any function as one of its key advantages, as established in [17, 14].

3 Computational Overhead: We acknowledge that Monte Carlo sampling introduces computational overhead, slowing inference by approximately a factor of $n$ (the number of noisy samples). The value of $n$ can be user-specified, where a larger $n$ gives a more precise estimation and usually a larger certified radius.

We would like to note that such overhead is intrinsic to all randomized smoothing methods [32][18][55], reflecting a fundamental trade-off for significantly stronger robustness guarantees. Nevertheless, randomized smoothing is still one of the most efficient and scalable approaches compared to other certified robustness methods [18].

Our method does not incur any additional cost beyond that of standard randomized smoothing, and reducing sample complexity remains an active research direction. In practice, the overhead can be substantially reduced through parallelization using multiple copies of the anomaly detector.

We provide additional results on running time overhead, evaluated in the settings as described in Section 4.

• Normal inference: 1/498s per batch (size 64)
• Inference and Certification: 1.83s per batch (size 64)

We sincerely thank the reviewer again for your time and effort. We hope that our responses have clarified the issues raised and kindly request your consideration.