Summary
The paper proposes a general randomized smoothing approach for certifying robustness concerning arbitrary perturbations defined in Levenshtein distance. The critical challenges of proposing the randomized smoothing approach are
1) how to design the smoothing distribution? The paper uses a deletion distribution by randomly removing tokens in the inputs.
2) how to derive the bound? The paper extensively derives a loose bound using the Neyman-Pearson lemma on the proposed deletion distribution.
The approach is effective on malware detection datasets. The paper also proposes an interesting tuning mechanism to favor false positives over false negatives, as in the malware detection scenario, the escaping of malware is a bigger problem than false alarms on benign software.
Strengths
1. The paper proposes a general randomized smoothing approach for certifying robustness concerning arbitrary perturbations defined in Levenshtein distance. The approach is effective on malware detection datasets.
2. The paper also proposes an interesting tuning mechanism to favor false positives over false negatives, as in the malware detection scenario, the escaping of malware is a bigger problem than false alarms on benign software.
3. The paper also evaluates RS-Del to empirical attacks.
Weaknesses
1. It is astonishing to see the classifier maintains a high certified accuracy when >90% of the inputs are deleted. I don't think it is possible to do so in NLP datasets, e.g., movie reviews datasets like SST2 and IMDB. Deleting >90% of the movie reviews definitely destroy the meaning of the reviews.
2. missing related works:
* In lines 40-42, the paper states "there is also no work for ... along with substitution or additive perturbation". This is not the case. ARC [1] is a deterministic approach for certifying robustness of LSTMs given arbitrary perturbation spaces, including insertion, deletion, substitution, and their combinations. However, ARC can only be used for LSTMs and the certified radius is much smaller compared to RS-Del. ARC also scales linearly with respect to the certified radius while RS-Del's time complexity is constant, e.g, equal to the number of sample in Monte Carlo sampling. ARC may introduce more over-approximation (e.g. looser bound) than RS-Del due to the interval bound propagation (IBP) used in ARC.
* Masking [3,4] has been used as a randomized smoothing approach for certifying the robustness of NLP models with respect to word substitutions.
3. In Table 10, RS-Del does not perform better than NS on Slack-VTFeed and GAMMA-Sleipnir2. So it is "four out of six" instead of "five out of six". However, the NS baseline is quite weak, how about comparing RS-Del to other empirical defense approaches for malware detection?
Questions
Comments:
1. $m$ never appears outside Lemma 4. Either removing $m$ from Lemma 4 or providing intuitive relation between $m$ and $p_{del}^{|\bar{x}|-|x|}$.
2. In line 286, Table 7->Table 8.
Questions:
1. Can we further improve the bound following Lee et al. [2]? In [2], the bound is to first prove that $\forall h \in \mathcal{F}(x, \mu_y)$ the minimal value of $p_y(\bar{x};h)$ will always be achieved when $dist(\bar{x},x)=r$, e.g., when the attacker tries to utilize the attack budget as much as possible. Then they can exactly compute Eq (13) without approximation. The case in [2] is easier since they only allow substitutions, but in this paper deletions and insertions are also allowed. However, in the proof of Theorem 7, the minimizer is achieved when $n_{ins}=n_{del}=0$, indicating that the possibility of tightening the bound as [2].
2. Is Corollary 6 a looser bound, e.g, LHS $\le$ RHS instead of LHS = RHS? The proof seems to assume the substituted ones and inserted ones won't be counted in the LCS, but they potentially can be.
3. In line 45, the paper states "we consider input sequences of bounded and varying length". What's "unbounded length"? It seems all inputs have bounded length.
4. What's the performance of $f_b$?
5. However, the NS baseline is quite weak, how about comparing RS-Del to other empirical defense approaches for malware detection?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The paper addresses some of the limitations. For other limitations, please refer to my points in Weakness and Questions.
[1] Certified Robustness to Programmable Transformations in LSTMs. Yuhao Zhang, Aws Albarghouthi, and Loris D'Antoni
[2] Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers.
[3] Certified Robustness to Text Adversarial Attacks by Randomized [MASK]. Jiehang Zeng, Xiaoqing Zheng, Jianhan Xu, Linyang Li, Liping Yuan, Xuanjing Huang
[4] Randomized Smoothing with Masked Inference for Adversarially Robust Text Classifications. Han Cheol Moon, Shafiq Joty, Ruochen Zhao, Megh Thakkar, Xu Chi