RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletion
Authors: Zhuoqun Huang
Neil G Marchant
Keane Lucas
Lujo Bauer
Olga Ohrimenko
Benjamin I. P. Rubinstein
Venue: NeurIPS 2023 poster (2023)
Keywords: certified robustness
randomized smoothing
malware detection
sequence classification
edit distance
TL;DR: We develop a new randomized deletion mechanism for smoothing and certifying black-box models on sequence data under edit distance threat models.

Abstract: Randomized smoothing is a leading approach for constructing classifiers that are certifiably robust against adversarial examples. Existing work on randomized smoothing has focused on classifiers with continuous inputs, such as images, where $\ell_p$-norm bounded adversaries are commonly studied. However, there has been limited work for classifiers with discrete or variable-size inputs, such as for source code, which require different threat models and smoothing mechanisms. In this work, we adapt randomized smoothing for discrete sequence classifiers to provide certified robustness against edit distance-bounded adversaries. Our proposed smoothing mechanism randomized deletion (RS-Del) applies random deletion edits, which are (perhaps surprisingly) sufficient to confer robustness against adversarial deletion, insertion and substitution edits. Our proof of certification deviates from the established Neyman-Pearson approach, which is intractable in our setting, and is instead organized around longest common subsequences. We present a case study on malware detection—a binary classification problem on byte sequences where classifier evasion is a well-established threat model. When applied to the popular MalConv malware detection model, our smoothing mechanism RS-Del achieves a certified accuracy of 91% at an edit distance radius of 128 bytes.

RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletion
Zhuoqun Huang University of Melbourne zhuoqun@unimelb. edu.
Neil G. Marchant University of Melbourne
Keane Lucas Carnegie Mellon University keanelucas@cmu, edu
nmarchant@uniiell edu. au
Lujo Bauer
Olga Ohrimenko
Carnegie Mellon University
University of Melbourne
1bauer@cmu. edu
cohrimenko@unimer im edu au
Benjamin I. P. Rubinstein
University of Melbourne
brubinsteiinunnimlll edu. au
Abstract
Randomized smoothing is leading approach for constructing classifiers that are certifiably robust against adversarial examples. Existing work randomized smoothing has focused on classifiers with continuous inputs, such as images, where fy-norm bounded adversaries are commonly studied. However, there has been limited work for classifiers with discrete or variable-size inputs, such as for source code, which require different threat models and smoothing mechanisms. In this work, we adapt randomized smoothing for discrete sequence classifiers to provide certified robustness against edit smoothing mechanism randomized deletion (RS-Del) applies random deletion edits, which are (perhaps surprisingly) sufficient to confer robustness against adversarial deletion, insertion and substitution edits. Our proof of certification deviates from the established Neyman-Peane approach, which intractable in our setting, and is instead organized around longest common subsequences. We present case study on malware detection-2 binary classification problem on byte sequences where classifier evasion is well-established threat model. When applied to the popular MalConv malware detection model, our smoothing mechanism RS-Del achieves certified accuracy of 91% % at edit distance radius of 128 bytes.
adversaries. Our proposed
Introduction
Neural networks have achieved exceptional performance for classification tasks in unstructured domains, such as computer vision and natural language. However, they are susceptible adversarial examples-ing innrssssooossppuuuuss perturbations that cause inputs to be misclassified [[] While multitude of defenses have been proposed against adversarial examples, they have historically been broken by stronger attacks. For instance, six of nine defense papers accepted for presentation at ICLR2018 were defeated months before the conference took place 3: another tranche of thirteen defenses were circumvented shortly after 4 This arms race between attackers and defenders has led the community to investigate certified robustness, which aims to guarantee that a classifier's prediction cannot be changed under a specified set of adversarial perturbations [5] 6
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Most prior work on certified robustness has focused on classifiers with continuous fixed-dmensiie inputs, under the assumption of f--norm bounded perturbations. A variety of certification methods have been proposed for this setting, including deterministic methods which bound network's 's output
by convex relaxation [ 6 or composing layerwise bounds b g 10-12, and randomized
smoothing which obtains high probability bounds for a base classifier smoothed under random noise [33155. Randomized smoothing has achieved state-of-the-are certified robustness against f norm bounded perturbations on ImageNet, correctly classifying 71 % of test set under perturbations with f2-norm up to / (half maximum pixel intensity) [6]. However, real-world attacks go beyond continuous modalities: range of attacks have been demonstrated against models with discrete inputs, such as binary executables [7 20]. source code (1). and PDF files [22]
Unfortunately, there has been limited investigation of certified robustness for discrete modalities, where prior work has focused on perturbations with bounded Hamming (4)) distance (23,25), in some cases under additional constraints 226 While this work covers attackers that overwrite content, does not cover attackers that insert/delete content, which is important for instance in the malware domain 17 BI. One exception is Zhang et al. [s method for certifying robustness under string transformation rules that may include insertion and deletion, however their approach is only feasible for small rule sets and is limited to LSTMs 32 Liu et al. 33 also study certification for threat model that includes insertion/deletion in the context of point cloud classification.
In this paper we develop comprehensive treatment of edit distance certifications for sequence classifiers. We consider input sequences of varying length on finite domains. We cover threat models where an adversary can arbitrarily perturb sequences by substitutions, insertions, and deletions or any subset of these operations. Moreover, our framework encompasses adversaries that apply edits to blocks of tokens at time. Such threat models are motivated in malware analysis, where attackers are likely to edit semantic objects in an executable (e.g., whole instructions), rather than at the byte-level. We introduce tunable decision thresholds, to adjust decision boundaries while still forming sound certifications. This permits trading-off misclassification rates and certification radii between classes, and is useful in settings where adversaries have strong incentive to misclassify malicious instances as benign 34 35
We accomplish our certifications using randomized smoothing [3 14. which we instantiate with a general-purpose deletion smoothing mechanism called RS-Del. Perhaps surprisingly, RS-Del does not need to sample all edit operations covered by our certifications. By smoothing using deletions only, we simplify our certification analysis and achieve the added benefit of improved efficiency by querying the base classifier with shorter sequences. RS-Del is compatible with arbitrary base classifiers, requiring only oracle query access such as via an inference API. To prove our robustness certificates, we have to deviate from the standard Neyman-Pearse intractable in our setting. Instead, we organize our proof around a representative longest common subsequence (LCS): the LCS serves reference point in the smoothed space between an input instance and neighboring instance, allowing us to bound the confidence of the smoothed model between the two.
approach to randomized smoothing, as it is
Finally, we present a comprehensive evaluation of RS-Del in the malware analysis setting IT We investigate tradeoffs between accuracy and the size of our certificates for varying levels of deletion, and observe that RS-Del can achieve certified accuracy of 01% at an edit distance radius of 128 bytes using on the order of 10s model queries. By comparison, a brute force certification would require in excess of 1030s model queries to certify the same radius. We also demonstrate asymmetric certificates (favouring the malicious class) and certificates covering edits at the machine instruction level by leveraging chunking and information from a disassembler. Finally, we assess the empirical robustness of RS- DS- to several attacks from the literature, where we observe a reduction in attack success rates.
2 Preliminaries
Sequence classification Let X' = S2* represent the space of finite-length sequences (including the empty sequence) whose elements are drawn from finite set Ω. For sequence x E X, we denote its length by |az| and the element at position by F; where runs from 1 to |z).. We consider classifiers that map sequences in X' to K classes in ) = (O...., K - 1}. For example, in our case study on
Our implementation is available

---

malware detection, we take X' to be the space of byte sequences (binaries), and 52 to be the set of bytes and y to be {0, 1} where 0 and I denote benign and malicious binaries respectively.
Robustness certification Given a classifier f: X V, input x X and neighborhood ((x) C X around æ, a robustness certificate is guarantee that the classifier's prediction is constant in the neighborhood, i.e.,
[(x:) - f(x') Va' (N()).
When the neighborhood corresponds to a ball of radius r centered on æ. we make the dependence explicit by writing NV. (x)). We adopt the paradigm of conservative, probabilistic certification, which is a natural fit for randomized smoothing [1].. Under this paradigm. a certifier may either assert that ① holds with high probability, decline to assert whether (T) holds or not.
Edit distance robustness Most existing work on robustness certification focuses on classifiers that operate on fixed-dimensional inputs in Rd, where the neighborhood of certification is an b--ball 1313113 However, Ep robustness is not well motivated for sequence classifiers: lp neighborhoods are limited to constant-length sequences, and the norm is ill-defined for sequences with non-numeric elements. For example, an lp neighborhood around byte sequence like x (78, 7A, 2D, (0) must include sequences additively perturbed by real-valued sequences like 5 (-0.09, 0.07, 0.11, which clearly results in type mismatch. Even if one focuses robustness for wonghh-peeservng sequence perturbations, the l neighborhood a poor choice because excludes sequences that are even slightly misaligned. Motivated by these shortcomings, we consider edit distance robustness.
Edit distance a natural measure for comparing sequences. Given a set of elementary edit operations (ops) O, the edit distance (2, x²) is the minimum number of ops required to transform sequence into x'. We consider three ops: delete a single element (del), insert single element (ins), and substitute one element with another (sub). For generality, we allow O to be any combination of these ops. When O = [del, ins, sub} the edit distance is known as Levenshtein distance (36]. primary goal of this paper is to produce edit distance robustness certificates, where the neighborhood of certification is edit distance ball N, fa' e X dist .x) S r).
Threat model We consider adversary that has full knowledge of our base and smoothed models, source randomness, certification scheme, and possesses unbounded computation. The attacker makes edits from O up to some budget, in order misclassify target In the context of our experimental case study on malware detection, edit distance is a reasonable proxy for the cost of running evasion attacks that iteratively apply localized functionality aunetionality-preeevving edits (e.g., 19 37 38, 17 33)). Since the edit distance scales roughly linearly with the number of attack iterations, the adversary has incentive to minimize edit distance for these attacks.
3 RS-Del: Randomized deletion smoothing
In this section, we propose method for constructing sequence classifiers that are certifiably robust under bounded edit distance perturbations. Our method RS-Del extends randomized smoothing with novel deletion mechanism and tunable decision thresholds. We review randomized smoothing in Section 3.1 and describe our deletion mechanism Scction|3.2) along with its practical aspects in Section We summarize the certified robustness guarantees of our method in Table and defer their derivation to Section
3.1 Randomized smoothing
Let fi. : X y/ be base classifier and o: X' - D(X) be smoothing mechanism that maps inputs to distributions over (perturbed) inputs. Randomized smoothing composes fb and & to construct a new smoothed classifier f X y/ For any input X, the smoothed classifier's prediction is
f(x) arg max {py (x; fu, Φ) ny).
(2)
yEy
where 17 = Enyrvey is a set of real- valued tunable decision thresholds and [fb()) = y]
(r( fo, 0) = Pr xmo((z)
(3)
3

---

is the probability that the base classifier f predicts class y for a perturbed input drawn from d(x). We omit the dependence of Py on fo and Φ where it clear from context.
The viability of randomized smoothing as a method for achieving certified robustness is strongly dependent on the smoothing mechanism. Ideally, the mechanism should be chosen to yield smoothed classifier with improved robustness under the chosen threat model, while minimizing any drop in accuracy compared to the base classifier. The mechanism should also be amenable analysis, that a tractable robustness certificate can be derived.
Remark 1. Previous definitions of randomized smoothing (e.g., 14) do not incorporate decision thresholds, and effectively assume 7 = O. We introduce decision thresholds as way to trade off error rates and robustness between classes. This is useful when there is asymmetry in misclassification costs across classes. For instance, in our case study on malware detection, robustness of benign examples less important because adveraries have limited incentive trigger misclassification of benign examples (34] 335 40). We note that the base classifier may also be equipped with decision thresholds, which provide another degree of freedom trade off error rates between classes.
3.2 Randomized deletion mechanism
We propose a smoothing mechanism that achieves certified edit distance robustness. Our smoothing mechanism perturbs sequence by deleting elements at random, and is called randomized deletion, or RS-Del for short.
Consider sequence æ E X' whose elements are indexed by the set [ax] = {1..... the distribution of (òx)) for RS-Del two stages. the first stage, random edit is drawn from distribution G(x) over the space of possible edits to denoted E(z). Since we only consider deletions for smoothing, any edit can be represented by the set of element indices in (x) that remain after deletion. Hence E(x) is taken the powerset of [ar). We specify edit distribution G(x)) so that each element is deleted i.i.d. with probability pael E (0, 1):
. | We specify
Pr[G(() = = = II
1.g (1 - Pdeel lics
(=1
where 1 denotes the indicator function, which returns if A evaluates true and otherwise. In the second stage, the edit is applied to æ to yield the perturbed sequence:
apply( x. (Fee))==1...c
(5)
where E()) denotes the i-th smallest index in e. The perturbed sequence z guaranteed to be subsequence of æ. Putting both stages together, the distribution of (xxx)
Pr(p(#) = =] Σ Pr[G(#) -) applll(ee,))==>
(6)
(EE(m)
Remark 2. It may be surprising that we are proposing smoothing mechanism for certified edit distance robustness that does not use the full set of edit ops covered by the threat model. It is a misconception that randomized smoothing requires perfect alignment between the mechanism and the threat model. All that is nceded from a robustness perspective, is for the mechanism to return distributions that are statistically close for any pair of inputs that close in O edit distance; this can be achieved solely with deletion. fact, perfect alignment is known to be suboptimal for some lp threat models [15]. Our deletion mechanism leads to tractable robustness certificate covering the full set of edit ops (see Section 4). Moreover while benefiting robustness, our empirical results show that deletion mechanism has only minor impact accuracy (see Section (5). Finally, our deletion mechanism reduces the length of the input, which is beneficial for computational efficiency (see Appendix G This is true in general for mechanisms employing insertionn/subbsiittions.
3.3 Practical considerations
We now discuss considerations for implementing and certifying RS-Del practice. In doing so, we reference theoretical results for certification, which are covered later in Section 4

---

Sample perturbed inputs for prediction
Edit ops O
estimate: S - {zi ~ v(x) ) fi=1... Pprdd
del
ins
sub
Certified radius r**
Confidence scores: Byy < [S] Ezes fx(x==y
1-Fx log T-Py/ /log Pa
Prediction: <- arg maxyey (By Byd
Sample perturbed inputs for lower confidence bound (LCBB: S' < {21 ((x))
log Pv/ /a/loo /log paol PM log Pg/ Pg/Log Pasl
v
LCB: By BiinCB(>><es) (=())= (8)
v
[1gg+++yy - //og Pasl
Compute certified radius r* using Table
[oo[[++y - (4x/ /tng puel
if Bg < 11g then return abstain else return prediction B. radius r*
[log(1+>> /// pao
(og(++*y)4+))/1o Pas
Figure I: Probabilistic certification of RS-Del. Here is the input sequence, fs is the base classifier, Pael the deletion probability, r the set of decision thresholds, a is the significance level, and Apred Abnd are sample sizes. BinLCB(K k, n, a)) returns lower confidence bound for p at level given k p)..
Table I: Edit distance robustness certificates for RS-Del as function of the edit ops O used to define the edit distance. Here My is the confidence for predicted class y and Vy is a threshold derived from defined in (10).
Probabilistic certification Randomized smoothing does not generally support exact evaluation of the classifier's confidence Hy := py(x)) which is required for exact prediction and exact evaluation of the certificates we develop in Section 4 While Py can be evaluated exactly for RS-Del by enumerating
over the possible edits (ax), the computation scales exponentially in |a>| (see Appendix AA. Since this is infeasible for even moderately sssieet we follow standard practice in randomized smoothing and estimate My with lower confidence bound using Monte Carlo sampling [4]. This procedure is described in pscudocode in Figure] | lines 1-3 estimate the predicted class y = f()), lines 4-5 compute a a lower confidence bound on Hyy and line uses this information and the results in T to compute probabilistic certificate that holds with probability 1 a.a. If the lower confidence bound on My exceeds the corresponding detection threshold f/y the prediction and certificate are returned (line 8), otherwise we abstain due to lack of statistical significance (line 7).
Training While randomized smoothing is compatible with any base classifier, it generally performs poorly for conventionally-traine
classifiers [13]. We therefore train base classifiers specifically to be used with RS- Del, by replacing original sequences with perturbed sequences (drawn from Φ) at training time. This has been shown to achieve good empirical performance in prior work [14].
Sequence chunking So far, we have described edit distance robustness and RS-Del assuming edits applied the level of sequence elements. However in some applications it may be reasonable to assume edits are applied at a coarser level, to contiguous chunks sequence elements. For example, in malware analysis, one can leverage information from disassembler group low-level sequence elements (bytes) into more semantically meaningful chunks, such as machine instructions, addresses and header fields (see Appendix C.3 Our methods compatible with chunking-ww simply reinterpret the sequence as a sequence of chunks, rather than a sequence of lower-level elements. This can yield a tighter robustness certificate, since edits within chunks are excluded.
4 Edit distance robustness certificate
We now derive an edit distance robustness certificate for RS-Del. We present the derivation in three parts: Section 4.1 provides an outline, Section derives lower bound on RS-Del's confidence score and Section 4.3 uses the bound to complete the derivation. All proof's are presented in Appendix B
4.1 Derivation outline
we derive an edit distance robustness certificate that relies on limited information about RS-Del. We allow the certificate to depend on the input the smoothed prediction y f(x), the confidence score By (a ft), the decision threshold 7/y- and the architecture of f. including the deletion smoothing mechanism o, but excluding the architecture of
Following prior work 14 13
5

---

the base classifier fu. Limiting the dependence in this way improves tractability and ensures that the certificate is applicable for any choice of base classifier fn- Formally, the only information we assume about fb. is that it is some classifier in the feasible base classifier set:
F(a, = { h E X y Pv = Py(a;; h)
(7)
Recall that an edit distance robustness certificate at radius for classifier f at input x is guarantee that [(x:)= = (()) for any perturbed input a in the neighborhood (x) = { E X distoo (ū, a) S r). We observe that this guarantee holds for RS-Del in the limited information setting iff the re adjusted confidence for predicted class y exceeds the r7 n-adjjssted confidence for any other class for all perturbed imputs æ and feasible base classifiers h:
Py (w; h) Yly 2 (P (z; h) my Vā (G),,, h E F(x (g)
(8)
To avoid dependence on the confidence of the runner-up class, which is inefficient for probabilistic certification, we work with the following more convenient condition.
Proposition A sufficient condition for (8) p( 1b)) ) 2 my(n) where
p(ar, Myy
min Py(a:h) (EN,(w) (eF()))
min
(9)
is a tight lower bound on the confidence for class y, and we define the threshold
2 + fly miny' tu Tly
Fl 2 miny'v tu Bly and | 2,
vy(n) =
+ fly miny Ny'
my < miny my and [ > 2,
(10)
144y min, No.
DD =.
The standard approach for evaluating p(x., (by) is via the SrrmannPPeason lemma 442 14] however this seems insurmountable in our setting due to the challenging geometry of the edit distance neighborhood. We therefore proceed by deriving loose lower bound on the confidence p(x., Mly S p(æ; noting that the robustness guarantee still holds so long as p(æ. M4y) > (1). The derivation proceeds in two steps. In the first step, covered in Section 4.2, we derive lower bound for the inner minimization in (9), which we denote by p(@. æ, Pyy) Then in the second step, covered in Section 4.3 complete the derivation by minimizing p( 2t (yy) over the edit distance neighborhood. Our results are summarized in Table I where we provide certificates under various constraints on the edit ops.
4.2 Minimizing over feasible base classifiers
In this section, we derive a loose lower bound on the classifier confidence with respect to feasible base classifiers
p( xt, Myy S p( p,y)
min (e( ht.
(11)
heF(m..)))))
To begin, we write Py (z; h) as sum over the edit space by combining and 6
(t( = Σ
s(,, h)) where s(ε, = Pr (G( = é I((apply(a.))= (12)
(EE(#)
We would like rewrite this sum in terms of the known confidence score at æ. Hy Py(x;; Eree(2) s(c, x; h). To do so, we identify pairs of edits é to æ and to x for which the corresponding terms s(2 z;; h) and s(c, x; h) are proportional.
Lemma (Equivalent edits). Let x" be a longest common subsequence (LCS) [43] of a and æ. and let 2 E (()) and c* E (xx) be any edits such that apply( 2*) = apply (zx c*) = z². Then there exists a bijection 2 - 22d such that apply(æ, E) = apply x for any E 2" and m(().
Furthermore, we have a(; = Pdel
(2t)
s(c, x: h).
Applying this proportionality result to all pairs of edits č, c related under the bijection m yields:
Σ 2
s(c, h))
Pael
2 #|-|
Σ
s(c, h)).

---

Thus we can achieve our goal of writing Py (x;h) in terms of py. A rearrangement of terms gives:
(y( h)) = Pdel
My
Σ
a(e,a;;
Σ a(t, EE2c*
(13)
cx2-
This representation is convenient for deriving a lower bound. Specifically, we can drop the sum over ? & 2 and upper-bound the sum over & 2 to obtain a lower bound that is independent of h.
Theorem 5. For any pair of inpuls ã, x E X we have
p( (.,by) (by) 2 f( (., Myy Pael | |||-|=| (1y- - 11
Pdel
1/2 (cdlatccsta.m))aall1la
(14)
where distrcs x) is the longest common subsequence (LCS) distance between and æ.
4.3 Minimizing over the edit distance neighborhood
In this section, we complete the derivation of our robustness certificate by minimizing the lower bound in [44 over the edit distance neighborhood:
p(z: =EN,((a)
min p(z, 2.
(15)
We are interested in general edit distance neighborhoods, where the edit ops O used to define the edit distance may be constrained. For example, if the attacker is capable of performing elementary substitutions and insertions, but not deletions, then O = (sub, ins). As step towards solving (15). therefore useful to express p(z, x, Hy) in terms of edit op counts, shown below.
Corollary 6. Suppose there exists a sequence of edits from & to æ that consists nsub substitutions, Ylins insertions and Tidel deletions s.f. Yssub Tlins + Tldel disto (B, x) and Rsub; Tiins Tddel 0. Then
p æ, Uy)
Tidd nas Pdel
(Hg + Pdel
Puo 7
This parameterization of the lower bound enables us re-express over edit ops counts:
15 as an optimization problem
p aE Myy Munn- EC,
min Tlan (Ny 1- + Pdel +iin)))
Pdel
(16)
where C, encodes constraints on the set of counts. If any number of insertions, deletions or substitu- tions are allowed, then the edit distance is known as the Levenshtein distance and C, consists of sets of counts that to We solve the minimization problem for this case below.
Theorem 7 (Levenshtein distance certificate). lower bound on the classifier's 's confidence within the Levenshtein distance neighborhood N,.(x) (with O &del, ins, sub}) is p(æ; (yy) My 1 paat follows that the classifier certifiably robust for any Levenshtein distance ball with radius r less than equal to the certified radius r* [[o[[1 (,, ( 1yy/log p4a..
It is straightforward to adapt this result to account for constraints the edit ops O. Results for all combinations of edit ops are provided in Table
So far in this section we have obtained results that depend on the classifier's 'i confidence My. assuming it can be evaluated exactly. However since exact evaluation of Hy is not feasible in general (see Section 3.3) we extend our results to the probabilistic setting, assuming a bound on My available. This covers probabilistie certification procedure described in Figure] [ Corollary 8. Suppose the procedure in Figure / returns predicted class ÿ with certified radius r". Then an edit distance robustness certificate of radius S r* holds at with probability 1 a.
lower confidence
5 Case study: robust malware detection
We now present case study on the application of RS-Del malware detection. We report on certified accuracy for Levenshtein and Hamming distance threat models. We show that by tuning decision thresholds we can increase certified radii for the malicious class while maintaining accuracy. We also evaluate RS-Del on range of published malware classifier attacks. Due to space constraints, we present the complete study in appendices[CIP where we report on training curves, the computational cost of training and certification, certified radii normalized by file size, and results where byte edits are chunked by instructions.
"The LCS distance is equivalent the generalized edit distance with O {del, ins).

---

Background Malware (malicious software) detection is long standing problem in security where machine learning is playing an increasing role 47 Inspired by the success of neural networks in other domains, recent work has sought to design neural network models for static malware detection which operate on raw binary executables, represented as byte sequences [ 50) While these models have achieved competitive performance, they are vulnerable to adversarial perturbations that allow malware to evade detection [18/20 37 51
31 52 17 39]. Our edit distance threat model reflects these attacks in the malware domain where, even though a variety of perturbations with different semantic effects are possible, any perturbation can be represented in terms of elementary byte deletions, insertions and substitutions. For perspective rule-based tool that is widely used for static malware analysis in industry. Running Nextron System's 's YARA rule se on sample of binaries from the VTFeed dataset (introduced below), we find 83% of rule matches are triggered by fewer than 128 bytes. This implies most rules can be evaded by editing fewer than 128 bytes-a regime that is covered by our certificates in some instances (see Table 2 Further background and motivation for the threat model is provided in Appendix C along with a reduction of static malware detection to sequence classification.
the threat model, consider YARA [53],
Experimental setup We use two Windows malware datasets: Sleipnir2 which is compiled from
public sources following AlliinggA--ujallii et al. [54] and VTFeed which is collected from VirusTotal [[7]. We consider three malware detection models: a model smoothed with our randomized deletion mechanism (RS-Del). a model smoothed with the randomized ablation mechanism proposed by
Levine and Feizi [24] (RS-Abn), and a non-smoothed baseline (NS). All of the models are based on popular CNN architecture called MalConv [48], and are evaluated
held-out test set. We emphasize that RS-Del is the only model that provides edit distance certificates (general O), while RS-Abn provides Hamming distance certificate (O = {sub)). We review RS-Abn in Appendix where we describe modifications required for discrete sequence classification, and provide an analysis comparing the Hamming distance certificates of RS-Abn and RS-Del. Details about the datasets. models, training procedure, calibration, parameter settings and hardware are provided in Appendix D
Accuracy/robustness tradeofl's Our first set of experiments investigate tradeoff's between malware detection accuracy and robustness guarantees as parameters associated with the smoothed models are varied. Table 2 reports clean accuracy, median certified radius (CR) and median certified radius normalized by file size (NCR) on the test set for RS-Del as function of pdel. A reasonable tradeoff observed at Pdel = 99.5% for Sleipnir2, where median certified radius of 137 bytes is attained with only a 2-3% drop in clean accuracy from the NS baseline. The corresponding median NCR is 0.06% and varies in the range 0-9% across the test set. We also vary the decision threshold n at Pdel = 99.5% for Sleipnir2, and obtain asymmetrical robustness guarantees with a median certified radius up to 582 bytes for the malicious class, while maintaining the same accuracies (see Table g in Appendix F.T.
Since there are no baseline methods that support edit distance certificates, we compare with RS-Abn. which produces a limited Hamming distance certificate. Figure 2 the certified accuracy curves for RS-Del and RS-Abn for different values of the associated smoothing parameters Pdel and Pab- The certified accuracy is the fraction of instances in the test set for which the model's 's prediction is correct and certifiably robust at radius r, and is therefore sensitive to both robustness and accuracy. We find that RS-Del outperforms RS-Abn in terms of certified accuracy at all radii r when Pdel Pab. while covering a larger set of inputs (since RS-Del's edit distance ball includes RS-Abn's 's Hamming ball). Further results and interpretation for these experiments are provided in Appendix E
Empirical robustness to attacks Our edit distance certificates are conservative and may underesti- mate robustness to adversaries with additional constraints (e.g., maintaining executability, preserving a malicious payload, etc.). To provide a more complete picture of robustness, we subject RS-Del and
31 covering white-box and black- box settings. for randomized smoothing Appendix H We do not constrain the number of edits each attack can make, which yields adversarial examples well outside the edit distance we can certify for four of six attacks (see Table D of Appendix [F). We measure robustness in terms of the attack success rate, defined as the fraction of instances in the evaluation set for which the attack flips the prediction from malicious to benign on at least one repeat (we repeat each attack five times). For both Sleipnir2 and VTFeed, we observe that RS-Del achieves
NS to six recently published attacks 20
37
17
38
We adapt gradient-based white-box attacks 20
https://valhalla. nextron- wystems.tcoooooo com/
8

---

Clean
Median
Median
Modal,smoathing parameter
Model
pdel
Accuracy
CR
NCR
Del.Pe
RS
RS Del,Pe 97%
RS Abn.Pat 97%
Sleipnir2 dataset
PS- 99%
Abn 99%
RS DelPae 99.5%
RS Abn.aba 99.3%
NS
98.9%
100
90%
97.1%
0.0023
Certified accuracy (98)
90
95%
97.8%
13
0,0052
RS-Del
97%
97.4%
22
0,0093
80
99%
98.1%
68
0.0262
99.5%
96.5%
137
0.0555
70
99.9%
83.7%
688
0,2269
60
VTFeed dataset
NS
98.9%
50
150
RS-Del
97%
92.1%
22
0.0045
Radius,
99%
86.9%
0.0122
Figure 2: Certified accuracy for RS-Del and
Table 2: Clean accuracy and robustness metrics for RS-Del as function of dataset and deletion probability Pdel- All metrics are computed on the test set. "Median CR" is the median cer- tified Levenshtein distance radius in bytes and "median NCR %6 is the median certified Leven- shtein distance radius normalized as a percentage of the file size. A good tradeoff is achieved when Pdel 99.5% (in bold).
RS-Abn 24 as function of certificate radius (horizontal axis) and strength of the smoothing parameter (line style). Results are plotted for the Sleipnir2 test set. While RS-Del provides Levenshtein distance certificate (with (del, ins, sub)), RS-Abn provides more limited Hamming distance certificate (0 = (sub)). The non-smoothed, non-certified model (NS) achieves clean accuracy of 98% in this setting.
the lowest attack success (best robustness) for four of six attacks. In particular, we observe 20 percentage point decrease in the success rate of Disp-an attack with no known defense [17]. We refer the reader to Appendix [ for details of this experiment, including setup, results and discussion.
6 Related work
There is rich body research on certifications under -y-norm-bounded threat models 5 g
11 13 14
25 56). While useful abstraction for computer vision, such certifications are inadequate for many problems including perturbations to executable files considered in this work. Even in computer vision, l,- no-momm bounded defenses can be circumvented by image translation, rotation, blur, and other human iimman-ippercpptbbll transformations that induce extremely large lp distances. One solution is to ce-parametrize the norm-bounded distance in terms of image transformation NLP faces different issue: while the bn threat model covers adversarial word it is too broad and covers many natural adversariaa examples well. For example, "He loves cat" and "He hates cat" are word in Ey distance from "He likes cat", but are semantically different. A radius 1 certificate will force wrong prediction for at least neighbor. To address this, Jia et al. (26) and Ye et al. (27 constrain the threat model to synonyms only.
12
55
parameters (5759] 59
substitution 28 60
In this paper go beyond the to word substitution threat model of previous work 23-25 [66. as consideration of insertions and deletions necessary in domains such as malware analysis. Such edits not captured by the to threat model: there is fixed input size, and when edits preepreser,ing, few edits may lead to large to distances. Arguably, our edit distance threat model for sequences and RS-Del mechanism are of independent interest natural language also.
Certification has been studied for variations of edit distance defined for sets and graphs. [iu al. apply randomized smoothing using a subsampling mechanism to certify point cloud classifiers against edits that include insertion, deletion and substitution of points. Since a point cloud an unordered set, the edit distance takes simpler form than for sequences-it can be expressed in terms of set cardinalities rather than as a cost minimization problem over edit paths. This simplifies the analysis, allowing Liu et al. to obtain tight certificate via the Neyman Pearsso lemma, which is not feasible

---

for sequences. In parallel work. Serrkckchhhardd et al. 61 consider edit distance certification for graph classification, as an application of broader certification framework for group equivariant tasks. They apply sparsity-aware smoothing [62] to an isomorphism equivariant base classifier, to yield smoothed classifier that certifiably robust under insertions/deletions of edges and node attributes.
Numerous empirical defense methods have been proposed to improve robustness of machine learning classifiers in security systems [63] 64 29 65 22). Incer Romeo et al. [34] and Chen et al. 665 develop
classifiers that are verifiably robust if their manually cratted features conform to particular ar properties (e.g., monotonicity, stability). These approaches permit a combination of (potentially vulnerable) learned behavior with domain knowledge, and thereby aim to mitigate adversarial examples. CCen ct al. [2 seek guarantees against subtree insertion and deletion for PDF malware classification. Using convex over- -verappprxiiaatonn (6) previously applied to computer vision, they certify fixed- input dimension classifiers popular PDF malware analysis. Concurrent our work, [Saha et al. [29 propose to certify classifiers against patch-based attacks by aggregating predictions of fixed-sized chunks of input binaries. The patch attack threat model, however, is not widely assumed in the evasion literature for malware detectors and can be readily broken by many published attacks [7 20) Moreover, their de-randomized smoothing design assumes a fixed-width input (via padding and/or trimming) and reduces patch-based attacks to gradient-based lp attacks. While tight analysis exists for arbitrary randomized smoothing mechanisms [23], they are computationally infeasible with the edit distance threat model. Overall, we are the first to explore certified adversarial defenses that apply to sequence classifiers under the edit distance threat model.
7 Conclusion
In this paper, we study certified robustness of discrete sequence classifiers. We identify critical limitations of the fp-norm bounded threat model in sequence classification and propose edit distance- based robustness, covering substitution, deletion and insertion perturbations. We then propose a novel deletion smoothing mechanism called RS-Del that is equipped with certified guarantees under several constraints on the edit operations. We present a case study of RS-Del and its certifications applied to malware analysis. We consider two malware datasets using a recent static deep malware detector, MalConv [48]. We find that RS-Del can certify radii as large as 128 bytes (in Levenshtein distance) without significant loss in detection accuracy. A certificate of this size covers in excess of 10606 files in the proximity of a 10KB input file (see Appendix A). Results also demonstrate RS-Del improving robustness against published attacks well beyond the certified radius.
Broader impact and limitations Robustness certification seeks to quantify the risk of adversarial examples while randomized smoothing both enables certification and acts to mitigate the impact of at- tacks. Randomized smoothing can degrade (benign) accuracy of undefended models as demonstrated in our results at higher smoothing levels. While we have strived to select high quality datasets for our case study, we note that accuracy architectures. Our approach is scalable relative to alternative certification strategies, however it does incur computational overheads. Finally, it known that randomized smoothing can have disparate impacts on class-wise accuracy [7
tradcoffs may vary for different datasets and/or model
Acknowledgments
This work was supported by the Department of Industry, Science and Resources, Australia under AUSMURI CATCH, and the U.S. Army Research Office under MURI Grant 103377
References
[1] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference Learning Representations, ICLiiiiooo,,,,,,,,,, 2014.
[2] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adversar- ial Examples. In International Conference Learning Representations, ICLR, 2015.
10

---

[3] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, ICMI., 2018.
[4] Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In Advances Neural Information Processing Systems, NeurIPS, 2020.
[5] Eric Wong and Zico Kolter. Provable Defenses against Adversarial Examples via the Convex Outer Adversarial Polytope. In International Conference on Machine Learning, ICML, 2018.
[6] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified Defenses against Adversarial Examples. International Conference on Learning Representations, ICLR, 2018.
[7] Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O' O'Donoghue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned verifiers. arXiv preprint: 10265, 2018.
[8] Lily Weng. Huan Zhang. Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, ICML, 2018.
[9] Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, ICML, 2018.
[10] Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks. In Advances in Neural Information Processing Systems, NeurlPS, 2018.
[11) Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint: 1810.12715, 2018.
[12] Huan Zhang. Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsich. Towards Stable and Efficient Training of Verifiably Robust Neural Networks. In International Conference on Learning Representations, ICLR, 2020.
[13] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified Robustness to Adversarial Examples with Differential Privacy. In IEEE Symposium on Security and Privacy, S&P, 2019.
[14] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified Adversarial Robustness via Random- ized Smoothing. In International Conference on Machine Learning, ICML, 2019.
[15] Greg Yang, Tony Duan, Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Random- ized Smoothing of All Shapes and Sizes. In International Conference on Machine Learning, ICML., 2020.
[16] Nicholas Carlini, Florian Tramer, Krishnamurthy Dj Dvijotham, Leslie Rice, Mingjie Sun, and J Zico Kolter. (certified!!) adversarial robustness for free! In International Conference on Learning Representattions ICLR, 2023.
[17] Keane Lucas, Mahmood Sharif, Lujo Bauer, Michael K. Reiter, and Saurabh Shintre. Malware makeover: Breaking ml-based static analysis by modifying executable bytes. In Proceedings of the 202/ ACM Asia Conference on Computer and Communications Security, AsiaCCS, 2021.
[18] Bojan Kolosnjaji, Ambra Demontis, Battista Biggio. Davide Maiorca, Giorgio Giacinto, Claudia Eckert, and Fabio Roli. Adversarial malware binarics: Evading deep learning for malware detection in executables. In 26th European Signal Processing Conference, EUSIPCO, 2018.
[19] Daniel Park, Haidar Khan, and Bülent Yener. Generation & Evaluation of Adversarial Examples for Malware Obfuscation. International Conference On Machine Learning And Applications, ICMLA, 2019.
11

---

[20] Felix Kreuk, Assi Barak, Shir Aviv-Reuven, Moran Baruch, Benny Pinkas, and Joseph Keshet. Deceiving End-to-Ent Deep Learning Malware Detectors using Adversarial Examples, arXiv preprint: 0100110000040 04528, 2018.
[21] Huangzhao Zhang, Zhuo Li, Ge Li, Lei Ma. Yang Liu, and Zhi Jin. Generating adversarial examples for bolding robustness source code processing models. In Proceedings of the AAAI Conference Artificial Intelligence, AAAI,, 2020.
[22] Yizheng Chen, Shiqi Wang, Dongdong She, and Suman Jana. On training robust PDF malware classifiers. In 29th USENIX Security Symposium, 2020.
[23] Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In Advances in Neural Information Processing Systems, NeurIPS, 2019.
[24] Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by randomized ablation. In Proceedings of the AAAI Conference on Artificial Intelligence, AAAI, 2020.
[25] Jinyuan Jia. Binghui Wang, Xiaoyu Cao, Hongbin Liu, and Neil Zhenqiang Gong, Almost tight 10-norm certified robustness of top-k predictions against adversarial perturbations. In International Conference on Learning Representations, ICLR, 2022.
[26] Robin Jia, Aditi Raghunathan, Kerem Göksel, and Percy Liang. Certified Robustness to Adversarial Word Substitutions. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joinl Conference Natural Language Processing, EMNLP-IJCNLP. 2019.
[27] Mao Ye, Chengyue Gong, and Qiang Liu. SAFER: A structure-free approach for certified robustness to adversarial word substitutions. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL, 2020.
[28] Shuhuai Ren, Yihe Deng, Kun He, and Wanxiang Che. Generating natural language adversarial examples through probability weighted word saliency. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, ACL, 2019.
[29] Shoumik Saha, Wenxiao Wang, Yigitcan Kaya, and Soheil Feizi. Adversarial robustness of learning-based static malware classifiers. arXiv preprint: 133722 2023.
[30] Han Cheol Moon, Shafiq Joty, Ruochen Zhao Megh Thakkar, and Chi Xu. Randomized smoothing with masked inference for adversarially robust text classifications. In Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics, ACL,, 2023.
[31] Luca Demetrio, Battista Biggio, Giovanni Lagorio, Fabio Roli, and Alessandro Armando. Functionality-presere/ black-box optimization of adversarial windows malware. IEEE Trans- actions on Information Forensics and Security, 16:3469-3478, 2021.
[32] Yuhao Zhang, Aws Albarghouthi. and Loris D' Antoni. Certified robustness to programmable transformations in Istms. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP, 2021.
[33] Hongbin Liu, Jinyuan Jia, and Neil Zhenqiang Gong, PointGuard: Provably robust 3D point cloud classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), CVPR, pages 6186-6195, 2021.
[34] Inigo Incer Romeo, Michael Theodorides, Sadia Afroz, and David Wagner. Adversarially Robust Malware Detection Using Monotonic Classification. In Proceedings of the Fourth ACM International Workshop on Security and Privacy Analytics, IWSPA, 2018
[35] Samuel Pfrommer, Brendon G. Anderson, Julien Piet, and Somayeh Sojoudi. Asymmetric certified robustness via feature-convex neural networks, 2023.
[36] V. I. Levenshtein. Binary Codes Capable of Correcting Deletions, Insertions and Reversals. Soviet Physics Doklady, 10:707, February 1966.
12

---

[37] Luca Demetrio, Battista Biggio, Giovanni Lagorio. Fabio Roli, and Alessandro Armando. Explaining vulnerabilities of deep learning adversarial malware binaries, In Proceedings of the Third Italian Conference Cyber Security, ITASEC, 2019.
[38] Dario Nisi, Mariano Graziano, Yanick Fratantonio, and Davide Balzarotti. Lost in the Loader: The Many Faces of the Windows PE File Format. In Proceedings of the 24th International Symposium Research in Allucks, Intrusions and Defenses, RAID, 2021.
[39] Wei Song, Xuezixiang Li, Sadia Afroz, Deepali Garg, Dmitry Kuznetsov, and Heng Yin. MAB- Malware: A Reinforcement Learning Framework for Blackbox Generation of Adversarial Malware. In Proceedings of the 2022 ACM Asia Conference Computer and Communications Security, AsiaCCS, 2022.
[40] William Fleshman, Edward Raff, Jared Sylvester, Steven Forsyth, and Mark McLean. Non- negative networks against adversarial attacks, 2019.
[41] Krishnamurthy (Dj) Dvijotham, Jamie Hayes, Borja Balle, Zico Kolter, Chongli Qin, András György, Kai Xiao, Sven Gowal, and Pushmeet Kohli. framework for robustness certifica- tion of smoothed classifiers using f-divergences. In International Conference on Learning Representations, ICLR, 2020.
[42] Jerzy Neyman and Egon Sharpe Pearson. IX. on the problem of the most efficient tests of statistical hypotheses. Philosophicul Transactions of the Royal Society of London. Series A, Containing Pupers of a Mathematical or Physical Character, 231(694-706)288--333 February 1933.
[43] Robert A. Wagner and Michael J. Fischer. The string-to-string correction problem. Journal of the ACM, 118,) January 1974. ISSN 0004-5411.
[44] Microsoft
Defender Security Research Team. New machine learning model sifts through the good to unearth the bad in evasive malware, July 2019. URL
httpp://www/ www.rroooootoooooeeeeooommoooo en wttp://eooooeeen//eeeeeeeeeeeeee
malware/
[45] Kaijun Liu, Shengwei Xu, Guoai Xu, Miao Zhang, Dawei Sun, and Haifeng Liu. A Review of
Android Malware Detection Approaches Based on Machine Learning. JEEE Access, 8, 2020.
[46] Kaspersky Lab. Machine Learning for Malware Detection, 2021. URL https
/ /meddia.kaspersky.coom hwt.kkaappprsycccoooo.ooo
www.comm////.. en/ wweeee//eetteeeeeee httpppppee...cutttb/o//epootaaae hagpraipppraaappeaaaaaaaaaaapppp
Machine-Learning pdf
[47] Blackberry Limited. Cylance AI from Blackbenry, 2022. httptt:://www..blckeee
[48] Edward Raff, Jon Barker, Jared Sylvester, Robert Brandon, Bryan Catanzaro, and Charles K. Nicholas. Malware detection by eating whole EXE. In The Workshops of the Thirly-Second AAAI Conference on Artificial Intelligence, AAAI Workshops, 2018
[49] Marek Krčál, Ondřej Švec, Martin Bálek, and Otakar Jašek. Deep Convolutional Malware Classifiers Can Learn from Raw Executables and Labels Only. In The Workshops of 6th International Conference on Learning Representutions, 2018.
[50] Edward Raff, William Fleshman, Richard Zak, Hyrum S. Anderson, Bobby Filar, and Mark McLean. Classifying Sequences of Extreme Length with Constant Memory Applied to Malware Detection. In Proceedings of the AAAI Conference on Artificial Intelligence, AAAI, 2021.
[51] Octavian Suciu, Scott H. Coull, and Jeffrey Johns. Exploring Adversarial Examples in Malware Detection. In IEFE Security and Privacy Workshops, S&PW, 2019.
[52] Luca Demetrio, Scott E. Coull, Battista Biggio, Giovanni Lagorio, Alessandro Armando, and Fabio Roli. Adversarial exemples: A survey and experimental evaluation of practical attacks on machine learning for windows malware detection. ACM Trans. Priv. Secur, 24(4), September 2021. ISSN 2471-2566.
13

---

[53] VirusTotal. Yara:
The pattern matching swiss knife for malware researchers, 2022. URL http://vArrrsttaa.gittuu.
Accessed: 2023-10-12.
[54] Abdullah Al-Dujaili, Alex Huang, Erik Hemberg, and Una-May O' Reilly. Adversarial Deep Learning for Robust Detection of Binary Encoded Malware. In IEEE Security and Privacy Workshops, S&PW, 2018.
[55] Klas Leino, Zifan Wang, and Matt Fredrikson. Globally-robust neural networks. In International Conference Machine Learning, ICML, 2021.
[56] Zayd Hammoudeh and Daniel Lowd. Feature partition aggregation: A fast certified defense against a union of sparse adversarial attacks, 2023.
[57] Marc Fischer, Maximilian Baader, and Martin Vechev. Certified Defense to Image Transfor- mations via Randomized Smoothing. In Advances in Neural Information Processing Systems, NeurIPS, 2020.
[58] Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Bhavya Kailkhura, Tao Xie, Ce Zhang, and Bo Li. Tss: Transformation-speeen smoothing for robustness certification. In ACM SIGSAC Conference on Computer and Communications Security, CCS, 2021.
[59] Zhongkai Hao, Chengyang Ying, Yinpeng Dong, Hang Su, Jian Song, and Jun Zhu. Gsmooth: Certified robustness against semantic transformations via generalized randomized smoothing. In International Conference on Machine Learning, ICML, 2022.
[60] Jiehang Zeng, Jianhan Xu, Xiaoqing Zheng, and Xuanjing Huang. Certified robustness to text adversarial attacks by randomized [mask]. Computational Linguistics, 49:395-427, 2023.
[61] Jan Schuchardt, Yan Scholten, and Stephan Günnemann. (Provable) adversarial robustness for group equivariant tasks: Graphs, point clouds, molecules, and more. In Advances in Neural Information Processing Systems, NeurIPS, 2023.
[62] Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günneeaann Efficient robustness certificates for discrete data: Sparsity- randomized smoothing for graphs, images and more. In International Conference on Machine Learning, ICML, 2020.
[63] Ambra Demontis, Marco Melis, Battista Biggio, Davide Maiorca, Daniel Arp. Konrad Rieck, Igino Corona, Giorgio Giacinto, and Fabio Roli. Yes, Machine Learning Can Be More Secure! A Case Study on Android Malware Detection. IEEE Transactions on Dependable and Secure Computing, (((4):711-224 2019.
[64] Erwin Quiring, Lukas Pirch, Michael Reimsbach, Daniel Arp. and Konrad Rieck. Against All Odds: Winning the Defense Challenge in an Evasion Competition with Diversification. arXiv preprint:2010.090 09569, 2020.
[65] Yizheng Chen, Shiqi Wang, Yue Qin, Xiaojing Liao, Suman Jana, and David Wagner. Learning security classifiers with verified global robustness properties. In ACM SIGSAC Conference Computer and Communications Security, CCS, 2021.
[66] Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems, NeurlPS, 2018.
[67] Jeet Mohapatra, Ching-Yun Yun Ko, Lily Weng, Pin-Yu Yu Chen, Sijia Liu, and Luca Daniel. Hidden cost of randomized smoothing. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, AISTATS, 2021.
[68] Panagiotis Charalampopoulos, Solon Pissis, Jakub Radoszewski, Tomasz Waleñ, and Wiktor Zuba. Unary Words Have the Smallest Levenshtein k- k-Neighbourhoods. In 31st Annual Symposium on Combinatorial Pattern Matching, CPM, 2020.
[69] Spark Tsao. Faster and More Accurate Malware Detection Through Predictive Machine Learn ing, November 2019. URI
14

---

[70] R. Vinayakumar, Mamoun Alazab, K. P. Soman, Prabaharan Poornachandran, and Sitalakshmi Venkatraman. Robust Intelligent Malware Detection Using Deep Learning. IEEE Access, 2019.
[71] Hojjat Aghakhani, Fabio Gritti, Francesco Mecca, Martina Lindorfer, Stefano Ortolani, Davide Balzarotti, Giovanni Vigna, and Christopher Kruegel. When Malware is Packin' Heat; Limits of Machine Learning Classifiers Based on Static Analysis Features. In Proceedings of Symposium on Nenwork and Distributed System Security, NDSS, 2020.
[72] Frederic Perriot. Defeating Polymorphism Through Code Optimization. In Proceedings of the 2003 Virus Bulletin Conference, VB, 2003.
[73] Mihai Christodorescu, Johannes Kinder, Somesh Jha, Stefan Katzenbeisser, and Helmut Veith. Malware normalization. Technical Report TR1539, Department of Computer Sciences, Univer- sity of Wisconsin-Madison 2005.
[74] Andrew Walenstein, Rachit Mathur. Mohamed R. Chouchane, and Arun Lakhotia. Normalizing Metamorphic Malware Using Term Rewriting. In Sixth IEEE International Workshop on Source Code Analysis and Manipulation, SCAM, 2006.
[75] Danilo Bruschi, Lorenzo Martignoni. and Mattia Monga. Code Normalization for Self-Mutating Malware. IEEE Security & Privacy, 5(2):46 54, 2007.
[76] Konrad Rieck, Thorsten Holz, Carsten Willems, Patrick Düssel, and Pavel Laskov. Learning and classification malware behavior. In Delection of Intrusions and Malware, and Vulnerability Assessment, DIMVA, 2008.
[77] Yanfang Ye, Lifei Chen, Dingding Wang, Tao Li, Qingshan Jiang, and Min Zhao. Sbmds: an interpretable string based malware detection system using svm ensemble with bagging. Journal in Computer Virology, 5(4):283, November 2008. ISSN 1772-9904.
[78] Yong Qiao, Yuexiang Yang. itemsets in API call sequences. In 2013 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom, 2013.
Lin Ji, and Jie He. Analyzing malware by abstracting the frequent
[79] Haodi Jiang, Turki Turki, and Jason T. L. Wang. DLGraph: Malware detection using deep learn- ing and graph embedding. In International Conference On Machine Learning And Applications, 2018.
[80] Zhaoqi Zhang, Panpan Qi, and Wei Wang. Dynamic malware analysis with feature engineering and feature learning. In Proceedings of the AAAI Conference on Artificial Intelligence, AAAI, 2020.
[81] Ishai Rosenberg, Asaf Shabtai, Lior Rokach, and Yuval Elovici. Generic black-box end-to-end attack against state of the art API call based malware classifiers. In Proceedings of the 2 International Symposium on Research in Attacks, Intrusions, and Defenses, RAID, 2018.
[82] Weiwei Hu and Ying Tan. Black-box attacks against RNN based malware detection algorithms. In The Workshops of the Thirty-Second AAAI Conference on Artificial Intelligence, AAAI Workshops, 2018
[83] Ishai Rosenberg, Asaf Shabtai, Yuval Elovici, and Lior Rokach. Query-efficient black-box attack against sequence-based malware classifiers. In Annual Computer Security Applications Conference, ACSAC, 2020.
[84] Fenil Fadadu, Anand Handa, Nitesh Kumar, and Sandeep Kumar Shukla. Evading API call sequence based malware classifiers. In Proceedings of 21st International Conference on Information and Communications Security, ICICS, 2020.
[85] National Security Agency. Ghidra (version 10.1.5). URL httpp://wwwtt nsa. gov/ ghidra
[86] Marco Barreno, Blaine Nelson, Russell Sears, Anthony D Joseph, and J Doug Tygar. Can machine learning be secure? In Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security, AsiaCCS, 2006.
15

---

[87] Microsoft Corporation. PE format, June 2022. URL http:////dooc.ccccoootottooo us ///aindou///n22///oooo//o/ooora
[88]
VirusShare.com. VirusShare.com. URL https://virusshare.ccmmm
[89] Matthew G. Schultz, Elcazar Eskin, Erez Zadok, and Salvatore J. Stolfo. Data mining methods for detection of new malicious executables. In IEEE Symposium Security and Privacy, S&P, 2001.
[90] J. Zico Kolter and Mareus A. Maloof. Learning to Detect and Classify Malicious Executables the Wild. Journal of Machine Learning Research, 7(99):2721-2744, 2006.
[91] Chocolatey Software. Chocolatey software. URL URLLatpss//chooolrrry..rgg
[92] Chocolatey Software. Chocolately software docs security. URL URLAttpp::/boccc.ccoooll.e
org/en hegg/enus//an hetp://nnormaatioo/eeeeeee
[93] Luca Demetrio and Battista Biggio. secml-malware: Pentesting windows malware classifiers with adversarial EXEmples python. arXiv preprint:2104. 12848, 2021.
[94] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers. In Advances in Neural Information Processing Systems, NeurIPS, 2019.
[95] Daniel Lowd and Christopher Meek. Good word attacks on statistical spam filters. In Second Conference on Email and Anti-Spam, CEAS, 2005.
[96] Yan Scholten, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. Randomized message-interception smoothing: Gray-box certificates for graph neural networks. Advances in Neural Information Processing Systems, NeurlPS, 2022.
[97] Jinyuan Jia, Binghui Wang, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of community detection against adversarial structural perturbation via randomized smoothing. In Proceedings of The Web Conference 2020, WWW, pages 2718-2724, 2020. doi: 10.1145/ 3366423.3380029.
16

---

A Brute-force edit distance certification
In this appendix, we show that an edit distance certification mechanism based on brute-force search is computationally infeasible. Suppose we are interested in issuing an edit distance certificate at radius r for a sequence classifier f at input æ. Recall from ① that in order to issue certificate, we must show there exists no input z within the edit distance neighborhood (x-(z) that would change f's prediction. This problem can theoretically be tackled in brute-force manner, by querying f for all inputs in (z)) In the best case, this would take time linear in (N)),, assuming responds to queries in constant time. However the following lower bound 668, shows that the size of the edit distance neighborhood is too large even in the best case:
(V)( 2
255
Σ j=i-r
255".
For example, applying the loosest bound that is independent of æ;, we see that brute-force certification at radius = 128 would require in excess of 255" = 1030s queries to f. In contrast, our probabilistic certification mechanism (Figure I makes Upred + 7ihnd queries f, and we can provide high probability guarantees when the number of queries is of order 102 10*.
B Proofs for Section 4
In this appendix, we provide proofs of the theoretical results stated in Section
B.1 Proof of Proposition A sufficient condition for
8 is
min min Po(a;h) (x) bEF())
max max (E). NEF(#)
+ max Py (z; miin Nly y y"
(17)
We first consider the multi-class case where || maxy'y Py (a: h) by (17) and we can upper-bound max Py (z;; h) by 3- On the other hand.
fy min vu My' then Py (æ; h) >
if My 2 ming'ty By, we can only upper-bound max,'vv Py (z: h) by 1. Thus when | > 17
implies
1 + f2 miny my' my 2 miny $y MV'
min min Py (o( h)) #EN.(a) hEF(a)
2
2
1 fy min Ny' By < min Av fly
Next, we consider the binary case where | 2. Since the confidences sum to 1, we have
max, Py (x: Py (T; h). Putting this in 17 implies
+ Thy miny' ty Tly
min min (,(,;)) acN. hE)(m)
2
B.2
Proof of Lemma
Let S (1..... |S]} be bijection that returns the rank of an element in an ordered set S. Let
is: 2 + 181) be an elementwise extension of rs that returns of ranks for an ordered set of elements-iaa i.e., (U) = (rs(1): : E U for U C S. We claim m(7) = --1 (fz- (7)) is a bijection that satisfies the required property.
To prove the claim, we note that m is bijection from 2 to 2n since it is a composition of bijections i.- : 2F - 2(I....)) and p (1..... - 2 where -= | = |e*|. Next, we observe that iz- (7) relabels indices in they have the same effect when applied z* as on æ (this also holds for f. and e). Thus
apply(@, 2) apply(>", (
apply(2",, (f- (pply(z,m(t))
17

---

as required. To prove the final statement, we use 4.
15
and
T2 to write
s s(,, zz h))
h(apply(a
del
aan
R
(1 Pdel) |el
(e,, (e; h))
h((aply((n.e)==ll del
1c
(1 Pdel)
Pdel (1 - Pdel) 1x(===
|>| (1
del
Pdel
k(*)=w
Pdel
where the second last line follows from the fact that apply( apply(x,.)
B.3
Proof of Theorem
Let Ex and e* be defined in Lemma 4
We derive upper bound the over 2 that
appears in 13 Observe that
Σ c
s(e, v
Σ Pr( =
eg2e
Σ
Pr [G(x) = cl
<E
le'l
((=)) |c"1-kc Pdel)
deel
|e|
Pdel
le|=0
P
Pdel
m
|c"1
(18)
where the first line follows from the inequality 1n(apply(w.e)=v) S. 1; the second line follows from the law of total probability; the third line follows by constraining the indices f1...., |=] \ E" to be deleted; and the last line follows from the normalization the binomial distribution. Putting (18
and Ezez s(c, a;; h) 2 0 in 13) gives
Py(0;; h) 2 Pdel
|al ||0|
1 Peel m 1-11)
|a| Pael
|m]
Mly
Pael
(19)
In the second line above use the following relationship between the LCS distance and the length of the LCS |z*| = |e"|:
distr.cs(2; 2²) = # + -|2=|
Since
19
is independent the base classifier fs the lower bound on p(ä, æ; Myy follows immediately.
B.4 Proof of Corollary
Since the length of can only be changed by inserting or deleting elements in æ. have
x
[
Tidel-
(20)
We also observe that the LCS distance can be uniquely decomposed in terms the counts of insertion ops Mins and deletion ops Mdel: distLcs( @ x) mael Mins- These counts in turn be related to the given decomposition of edit ops counts for generalized edit distance. In particular, any substitution must be expressed and midll = Ridel + nsub- Thus we have
insertion and deletion under I.CS distance, which implies Mins Nins + Uluu
distr.s((E,3) Fldel + Flins 2n
(21)
Substituting 20 and 21 in gives the required result.
18

---

B.5 Proof of Theorem 7
Eliminating Naub from 16 problem in two variables:
using the constraint Youub T Yidel Dins, we obtain a minimization
min Pime Mas-n
(Tins Adel
s.t.
Yhins + Tidel S r
where v (Nins, mael) = Pdel Tinns and Nidel"
Mad nho (ny 1 + Pdel
-- mod). Observe that d is monotonically increasing in
2 (iins + 1, (.dee)))
1
2 1
1 (Tinss Ridel)
Pdel
5 Minss de
+
(My 1)pdel -1 + Pdel 1,
t (Tins; Rlde))
(Ny 1 Pdel Páel
where the second inequality follows since only consider and My such that the numerator
and denominator are positive. Thus the minimizer is (Ri na "Sub) = (0, 0, and we find p(a; My P The expression for the certified radius follows by solving p(ximy) 2 vy(n) for non-negative integer
B.6 Proof of Corollary 8
Recall that Corollary 6 gives the following lower bound on the classifier's confidence at a::
p(xr, x., (by) Pitel time (My
1 + Pdel
Observe that replace By by lower bound By that holds with probability 1 (as is done in lines 4-6 of Figure 1 and obtain looser lower bound İ( æ, (ly) p(æ,, x.,4y) that holds with probability a. Crucially, this looser lower bound has the same functional form, so all results depending Corollary 6 namely Theorem 7 and Table continue to hold albeit with probability a.
C Background for malware detection case study
In this appendix, provide background for our case study malware detection, including motiva- tion for studying certified robustness of malware detectors, a formulation of malware detection as a sequence classification problem, and threat model for adversarial examples.
C.1 Motivation
Malware (malicious software) detection is a vital capability for proactively defending against cyberat- tacks. Despite decades of progress, building and maintaining effective malware detection systems remains challenge, as malware authors continually evolve their tactics to bypass detection and exploit new vulnerabilities. One technology that has lead advancements in malware detection, is
application of machine learning (ML), which is now used in many commercial systems (69 44 46 47)
and continues to be an area of interest in the malware research community [70] 71
45
50]. While
traditional detection techniques rely manually-cure a detection model to be learned from a training corpus, that can potentially generalize to unseen
signatures detection rules, ML allows
programs.
Although ML has an apparent advantage in detecting previously unseen malware, recent research has shown that ML-based static malware detectors can be evaded by applying adversarial perturba- tions 20 37
variety of perturbations have been considered with different effects at the semantic level, however all of them can be modeled as inserting. deleting and/or substituting bytes. This prompts us to advance certified robustness for sequence classifiers within this general threat model-wel where attacker can perform byte-level edits.
39
19

---

C.2 Related work
Several empirical defense methods have been proposed to improve robustness of ML classifiers [63 64]. [ncer Romeo et al. 34 compose manually crafted Boolean features with a classifier that is constrained to be monotonically increasing with respect to selected inputs. This approach permits combination of (potentially vulnerable) learned behavior with domain knowledge, and thereby aims to mitigate adversarial examples. Demontis et al. 633 show that the sensitivity of linear support vector machines to adversarial perturbations can be reduced by training with Eoo regularization of weights. In another work. Quiring et al. [64] take advantage of heuristic-based semantic gap detectors and an ensemble of feature classifiers to improve empirical robustness. Compared to our work on certified adversarial defenses, these approaches do not provide formal guarantees.
Binary normalization 75 was originally proposed to defend against polymorphic/meeamorrhii malware, and can also be seen as a mitigation to certain adversarial examples. It attempts to sanitize binary obfuscation techniques by mapping malware to a canonical form before running a detection algorithm. However, binary normalization cannot fully mitigate attacks like Disp (see Table 2) as deducing opaque and evasive predicates are NP-hard problems [7
Dynamic analysis can provide additional insights for malware detection. In particular, it can record a program's behavior while executing it in a sandbox (e.g., collecting call graph or network traffic) [76]- 80 Though detectors built on top of dynamic analysis can be more difficult to evade, as the attacker needs to obfuscate the program's behavior, they are still susceptible to adversarial perturbations. For example, an attacker may insert API calls to obfuscate a malware's 's behavior [81]84] Applying RS-Del to certify detectors that operate on call sequences [80] or more general dynamic features would be interesting future direction.
C.3 Static MI.-based malware detection
We formulate malware detection as sequence classification problem, where the objective is to classify a file its raw byte sequence representation as malicious or benign. the notation of Section 2 assume the space of input sequences (files) is X Ω where ft = {0, I,..., 255} denotes the set of bytes, and we assume the set of classes is y = {0,1] where denotes the 'malicious' class and 0 denotes the 'benign' class. Within this context, malware detector is simply classifier f X y.
Detector assumptions Malware detectors are often categorized according to whether they perform static or dynamic analysis. Static analysis extracts information without executing code, whereas dynamic analysis extracts information by executing code and monitoring its behavior. In this work, we focus on machine learning-baan based static malware detectors, where the ability to extract and synthesize information is learned from data. Such detectors suitable base classifiers for RS-Del, as they can learn to make (weak) predictions for incomplete files where chunks of bytes are arbitrarily removed. We note that dynamic malware detectors are not compatible with RS-Del, since is not generally possible to execute an incomplete file.
we noted that our methods compatible with sequence chunking where the original input sequence is partitioned into chunks, and reinterpreted as sequence of chunks rather than sequence of lower-level elements. In the context of malware detection, we can partition a byte sequence into semantically meaningful chunks using information from disassembler, such as Ghidra [85]. For example, a disassembler can be applied to a Windows executable identify chunks of raw bytes that correspond to components of the header, machine instructions, raw data, padding etc. Applying our deletion smoothing mechanism the level of semantic chunks, rather than raw bytes, may improve robustness as it excludes edits within chunks that may be semantically invalid. It also yields a different chunk-level edit distance certificate, that may cover larger set of adversarial examples than byte-level certificate of the same radius. Figure S Iillustrates the difference between byte-level and chunk-level deletion for a Windows executable, where chunks correspond to machine instructions (such as push ebp) or non-instructions (NI).
Incorporating semantics In Section 3.3
20

---

File under
File under
Original
byte-level deletion (BYTE)
chunk-level deletion (INSN)
File offset
Byte
Instraction
File offset
Ryte
offset
Chunk
00000000
77
NI
00000000
77
00000001
90
00000001
90
NI
00000002
144
:
00000002
NI
00000400
85
:
00000400
85
00000401
139
00000400
85
push
abp
00000403
131
00000401
139
00000404
236
nov
abp,
eep
00000402
00000403
151
00000404
235
sub
6Ch
00000405
92
Illustration the deletion smoothing mechanism applied to an executable file at the byte- level versus chunk-level. Left: An executable file where the elementary byte sequence representation is shown in the 2nd column and chunks that correspond to machine instructions are shown in the 3rd column (sourced from the Ghidra [85] disassembler). Bytes that do not correspond machine instructions are marked NI. Shading represents bytes (light gray) or instruction chunks (dark gray) that are deleted in the corresponding perturbed file the right. Middle: A perturbed file produced by the deletion mechanism operating at the byte level (B (T)). Notice that individual instructions may be partially deleted. Right: A perturbed file produced by the deletion mechanism operating at the chunk-level (INSN).
Figure 3:
C.4 Threat model
We next specify the modeled attacker's goals, capabilities and knowledge for our malware detection case study 86
Attacker's objective We consider evasion attacks against malware detector f X + Y, where the attacker's objective to transform an executable file æ that it is misclassified by f. To ensure the attacked file æ is useful after evading detection, we require that it is functionally equivalent to the original file æ. We focus on evasion attacks that aim to misclassify malicious file as benign in our experiments, as these attacks dominate prior work [52). However, the robustness certificates derived in Section also cover attacks in the opposite direction where benign file is misclassified as malicious.
Attacker's capability We measure the attacker's capability in terms of the number of elementary edits they make to the original file æ. If the attacker is capable of making up to e elementary edits, then they can transform x into any file in the edit distance ball of radius centred on æ:
A.(z:) (a: E X dist (x. ..) S c).
Here disto .)) denotes the edit distance from the original file to the attacked file z under the set of edit operations (ops) O. We assume O consists of elementary byte-level or chunk-level deletions (del), insertions (ins) and substitutions (sub), or a subset of these operations.
We note that edit distance is reasonable proxy for the cost of running evasion attacks that iteratively apply localized inaetionaliiyypreeevvii edits (e.g.. [19 37 38 17 (9]). For these attacks, the edit distance scales roughly linearly with the number of attack iterations, and therefore the attacker has an incentive to minimize edit distance. While attacks do exist that make millions of elementary edits the malware domain (e.g., (3I),, we believe that an edit distance-constraaine threat model an important step towards realistic threat models for certified malware detection. (To examine the effect of large edits on robustness we include the GAMMA attack [31] in experiments covered in Appendix F)
Remark 9. The set (xx) overestimates the capability of an edit distance-consten distance-constrained attacker, because it may include files that are not functionally equivalent to For example, Ac(x) may include files that are not malicious (assuming æ malicious) or files that are invalid executables. This poses no problem for certification, since overestimating an attacker's capability merely leads to a stronger certificate than required. Indeed, overestimating the attacker's capability seem necessary, as functionally equivalent files are difficult to specify, let alone analyze.
21

---

Table 3: Summary of datasets.
Number of samples
Dataset
Label
Train
Validation
Test
Benign
20.948
7012
6999
Sleipnir2
Malicious
20 768
6892
6905
Benign
111 258
13961
13926
VTFeed
Malicious
111 395
13.870
13906
Attacker's knowledge In our certification experiments in Appendix E. we assume the attacker has full knowledge of the malware detector and certification scheme. When testing published attacks in Appendix F) we consider both white-box and black-box access to the malware detector. In the black-box setting, the attacker may make an unlimited number of queries to the malware detector without observing its internal operation. We permit access to detection confidence scores, which are returned alongside predictions even in the black-box setting. In the white-box setting, the attacker can additionally inspect the malware detector's s source code. Such strong assumption is needed for white-box attacks against neural network-basee detectors that compute loss gradients with respect to the network's ' internal representation of the input file 20 17).
D Experimental setup for malware detection case study
In this appendix, detail the experimental setup for our malware detection case study.
D.1 Datasets
Though our methods are compatible with executable files of any format, in our experiments we focus on the Portable Executable (PE) format [87]. since datasets, malware detection models and adversarial attacks are more extensively available for this format. Moreover, PE format is the standard for executables, object files and shared libraries in the Microsoft Windows operating system, making it an attractive target for malware authors. We use two PE datasets which are summarized in Table and described below.
Sleipnir2 This dataset attempts replicate data used in past work [54]. which not published with raw samples. We were able to obtain the raw malicious samples from a public malware repository called VirusShare [8]] using the provided hashes. However, since there is similar public repository for benign samples, we followed established protocols [89] 900 (0 to collect a new set of benign samples. Specifically, we set up a Windows 7 virtual machine with over 300 packages installed using Chocolatey package manager [91]. We then extracted PE files from the virtual machine, which were assumed benign") and subsampled them match the number of malicious samples. The dataset is randomly split into training, validation and test sets with ratio of 60%, 20% and 20% respectively.
VTFeed This dataset was first used in recent attacks on end-to-end ML-based malware detec- tors [17]. It was collected from VirusTotal-aa commercial threat intelligence service- sampling PE files from the live feed over a period of two weeks in 2020. Labels for the files were derived from the 68 antivirus (AV) products aggregated malicious they were flagged malicious by 40 or more of the AV products, they were labeled benign if they were flagged malicious by any of the AV products, and any remaining files were excluded. Following I Lucas et al. [17), the dataset is randomly split into training, validation and test sets with a ratio of 80%, 10%, and 10% respectively.
Virus Total at the time of collection. Files were labeled
We note that VTFeed comes with strict terms of use, which prohibit us from loading it on our high performance computing (HPC) cluster. As result, we use Sleipnir2 for comprehensive experiments (e.g., varying Pael. 77) on the HPC cluster, and VTFeed for a smaller selection of experiments run on a local server.
'Chocolatey packages validated against VirusTotal 92
22

---

D.2 Malware detection models
MalConv was one of the first end-to-end neural network models proposed for malware detection i.e., it learns to classify directly from raw byte sequences, rather than relying on manually engineered features. Architecturally. composes a learnable embedding layer with shallow convolutional network. A large window size and stride of 500 bytes are employed to facilitate scaling to long byte sequences. Though MalConv compatible with arbitrarily long byte sequences in principle, we truncate all inputs to 2MB to support training efficiency. We use the original parameter settings and training procedure [8 except where specified in Appendix D.5
We experiment with malware detection models based on MalConv
48
Using MalConv as a basis, we consider three models described below.
NS A vanilla non-smoothed (NS) MalConv model. This model serves as a non-certified, non-robust baseline-i.e., no specific techniques employed improve robustness evasion attacks and certification is not supported.
RS-Abn A smoothed MalConv model using the randomized ablation smoothing mechanism pro- posed by Levine and Feizi 2 and reviewed in Appendix [I] This model serves as a certified robust baseline, albeit covering more restricted threat model than the edit distance threat model we propose in Section 2 Specifically, it supports robustness certification for the Hamming distance threat model, where the adversary is limited substitution edits (O = {sub)). Since Levine and Feizi's formula- tion is for images, several modifications are required to support malware detection as described in Appendix G To improve convergence, we also apply gradient clipping when learning parameters in the embedding layer (see Appendix G We consider variants of this model for different values of the ablation probability Pab.
RS-Del A smoothed MalConv model using our proposed randomized deletion smoothing mech- anism. This model supports robustness certification for the generalized edit distance threat model where O C {del, ins, sub]. We consider variants of this model for different values of the deletion probability Páel. decision thresholds 77, and whether deletion/certification is performed the byte- level (B YTE) or chunk-level (INSN). We perform chunking as illustrated in Figure3J-ia we chunk bytes that correspond to distinet machine instructions using the Ghidra disassembler.
D.3 Controlling false positive rates
Malware detectors are typically tuned to achieve a low false positive rate (FPR) (c.g., less than 0.1-1%) since producing too many false alarms is nuisance users To make all malware detection models comparable, we calibrate the FPR to 0.5% on the test set for the experiments reported in Appendix [E] and 0.5% the validation set for the experiments reported in Appendix [F] unless otherwise noted. This calibration is done by adjusting the decision threshold of the base MalCony model.
D.4 Compute resources
Experiments for the Sleipnir2 dataset were run a high performance computing (HPC) cluster, where the requested resources varied depending the experiment. We generally requested single NVIDIA P100 GPU when training and certifying models. Experiments for the VTFeed dataset were run on local server due to restrictive terms of use. Compute resources and approximate wall clock running times are reported in Tables 4 and [5] for training and certification for selected parameter settings. Running times for other parameters settings are lower than the ones reported in these tables.
D.5 Parameter settings
We specify the parameter settings and training procedure for MalCony, which used standalone in NS, and as base model for the smoothed models RS-Del and RS-Abn. summarzies our setup, which is consistent across all three models except where specified. We follow the authors of MalConv 48 when setting parameters for the model and the optimizer, however we set a larger
alarm-testss.... tests/
23

---

Table 4: Compute resources used for training. Note that the wall clock times reported here are for an unoptimized implementation where the smoothing mechanism is executed on the CPU.
Dataset
Requested resources
Model
Parameters
Time
Notes
Trained for 50 epochs,
NS
22 hr
converged in 15 epochs
BYTE, Poel 95%
Trained for 100 epochs, converged in 50 epochs
NVIDIA P1O0 GPU, 4 cores on Intel Xeon Gold 6326 CPU
RS-Del
39 hr
Sleipnir2
INSN, Peel
Trained for 100 epochs, converged in 20 epochs
RS-Del
48 hr
95%
Trained for 100 epochs, converged in epochs
RS-Abn
Pab
95%
40 hr
Trained for 100 epochs, converged in 25 epochs
NVIDIA RTX3090 GPU,
NS
139 hr
6 cores on AMD Ryzen
VTFeed
Threadripper PRO 3975WX CPU
BYTE,
Trained for 100 epochs, converged in 20 epochs
RS-Del
152 hr
Poul 97%
Table 5: Compute resources used for certification on the test set. The evaluation dataset is partitioned and processed on multiple compute nodes with the same specifications. The reported time is the sum of wall times on each compute node. Note that the times reported are for an unoptimized implementation where the smoothing mechanism is executed the CPU.
Dataset
Requested resources
Model
Parameters
Time
NS
5 min
BYTE, Pdel 95%
RS-Del
65 hr
NVIDIA P100 GPU, 12 cores on Intel Xeon Gold 6326 CPU
Slcipnir2
INSN,
RS-Del
140 hr
Poel
95%
RS-Abn
Pab 95%
210 hr
NVIDIA RTX3090 GPU, 6 cores on AMD Ryzen Threadripper PRO 3975WX CPU
NS
4 min
VTFeed
BYTE,
RS-Del
500
Peel
97%
maximum input size of 2MiB to accommodate larger inputs without clipping. Due to differences available GPU memory for the Sleipnir2 and VTTeed experiments, we use a larger batch size for VTFeed than for Sleipnir2. We also set higher limit the maximum number of epochs for VTFeed, as it is a larger dataset, although the NS and RS-Del models converge within 50 epochs for both datasets. To stabilize training for the smoothed models (RS-Del and RS-Abn) smoothing mechanisms during training only to ensure at least 500 raw bytes are preserved. This may limit the number of deletions for RS-Del and the number of ablated (masked) bytes for RS-Abn. For RS-Abn, we clip the gradients for the embedding layer to improve convergence (see Appendix G
modify the
E Evaluation of robustness certificates for malware detection
In this appendix, we evaluate the robustness guarantees and accuracy of RS-Del for malware detection. We consider two instantiations of the edit distance threat model. First, in Appendix E. we consider the Levenshtein distance threat model, where the attacker's elementary edits are unconstrained and may include deletions, insertions and substitutions. Then, in Appendix E.2 we consider the more restricted Hamming distance threat model, where an attacker only able to perform substitutions. We summarize our findings in Appendix E.3 Overall, we find that RS-Del generates robust predictions with minimal impact on model accuracy for the Levenshtein distance threat model, and outperforms RS-Abn (24] for the Hamming distance threat model.
24

---

Table Parameter settings for MalConv, the optimizer and training procedure. Parameter settings are consistent actoss all malware detection models (NS, RS-Del, RS-Abn) except where specified.
Parameter
Values
Max input size
2097152
Embedding size
MalConv
Window size
500
Channels
128
Python class
torch. optim.0
Learning
0.01
Optimizer
Momentum
0.9
Weight decay
0.001
Batch size
24 (Sleipnir2), 32 (VTFeed)
Max. epoch
50 (Sleipnir2), 100 (VTFeed)
Training
Min. preserved bytes
500 (RS-Del, RS-Abn), NA (NS)
Embedding gradient clipping
(RS-Abn), (RS-Del, NS)
Early stopping
If validation loss does not improve after 10 epochs
We report the following quantities in evaluation:
Certified radius (CR). The radius of the largest robustness certificate that can be issued for given input, model and certification method. Note that this conservative measure of robustness since it is tied to the certification method. The median CR is reported on the test set.
Certified accuracy
also known as verified-robust accuracy 66 55
evaluates
robustness certificates and accuracy of a model simultaneously with respect to test set. It is defined the fraction of instances in the test set II] for which the model f's prediction is correct and certified robust at radius r or greater:
CERTACC, (D) = Σ ((m))-ICR(()))
(22)
[D]
(a.N)E
where CR(x) denotes the certified radius for input æ returned by the certification method.
Clean accuracy. The fraction instances in the test set for which the model's prediction is correct.
We briefly mention default parameter settings for the experiments presented in this appendix. When approximating the smoothed models (RS-Del and RS-Abn) we sample ropred 1000 perturbed inputs for prediction and Abad 4000 perturbed inputs for certification, while setting the significance level 0.05. Unless otherwise specified,
the decision thresholds for the smoothed models that 0. After fixing the decision thresholds for the base models are tuned to yield a false positive rate 0.5%. We note that the entire set is used when reporting metries and summary statistics in this appendix.
E.1 Levenshtein distance threat model
We first present results for the Levenshtein distance threat model, where the attacker's elementary edits are unconstrained (O = ddel, ins, sub)). We vary three parameters associated with RS-Del: the deletion probability Pasl, the decision thresholds of the smoothed model v,, and the level of sequence chunking (i.e., whether sequences are chunked at the byte-level instraction-level), We use NS as a baseline as there are no prior certified defenses for the Levenshtein distance threat model to our knowledge.
25

---

Poel
Cortifed acarracy (1%
Cortifeed accursoy (%)
80
97%
70
70
00 09.5%
60
60
9%
50
50
40
97%
90%
39.5%
20
10
00.0%
10
0.2
0.6
Radius,
Normalized Radiuss r((%
Figure 4: Certified accuracy for RS-Del as function of the radius in bytes (left horizontal axis), radius normalized by file size (right horizontal axis) and byte deletion probability Peel (line styles). The results are plotted for the Sleipnir2 test set under the byte-level Levenshtein distance threat model (with O {del, ins, sub}). The grey vertical lines in the left plot represent the best achievable certified radius for RS-Del (setting My in the expressions in Table 1).
100
100
00
90
Certifeed sccuracy (%)
Cortifed accuracy (%5
80
97%
90%
70
60
50
40
Piel
40
30
97%
30
20
5%%
10
29.5%
200
400
600
0.2
Normalized
r(%)
Figure 5: Certified accuracy for RS-Del with chunk-level deletion (INSN) function of the radius in chunks (left horizontal axis), radius normalized by sequence length chunks (right horizontal axis) and chunk deletion probability Poel (line styles). The results are plotted for the Sleipnir2 test set under the chunk-level Levenshtein distance threat model (with O = [del. ins, sub}). The grey vertical lines in the left plot represent the best achievable certified radius for RS-Del (setting By in the expressions in Table 1).
Certified accuracy Figure ploots the certified accuracy of RS-Del using byte-level deletion as function the radius (left horizontal axis), radius normalized by file size (right horizontal axis) on the Sleipnir2 dataset for several values of Pael- We observe that the curves for larger values of Pael approximately dominate the curves for smaller values of Pdel. for Pdel < 99.5% (i.e., the accuracy higher or close for all radii). This suggests that the robustness of RS-Del can be improved without sacrificing accuracy by increasing Pdel up 99.5 99.5%. However, for the larger value Pdel 99.99 99.9%. we observe drop in certified accuracy of around 10% for smaller radii and an increase for larger radii. By normalizing with respect to the file size, we can see that our certificate is able to certify up to 1% of the file size. We also include an analogous plot for chunk-level deletion in Figure 5 which demonstrates similar behavior. We note that chunk-level deletion arguably provides stronger guarantees, since the effective radius for chunk-level Levenshtein distance larger than for byte-level Levenshtein distance.
It is interesting to relate these certification results to published evasion attacks. Figure shows that we can achieve a certified accuracy in excess of 90% at a Levenshtein distance radius of 128 bytes when Pdel 99.5%. This radius is larger than the median Levenshtein distance of two attacks that manipulate headers of PE files 337 38 (see Table in Appendix(F) We can therefore provide reasonable robustness guarantees against these two attacks. However, a radius of 128 bytes is orders of magnitude smaller than the median Levenshtein distances of other published attacks which range from tens of KB 11 20 to several MB [3] (also reported in Table 9. While some of these attacks
26

---

Table 7: Clean accuracy and robustness metrics for RS-Del as function of the dataset (Sleipnir2 and VTFeed), deletion probability Pael and deletion level (B (BYTE INSN). All metrics are computed on the test set. Here "abstain rate" refers to the fraction of test instances for which RS-Del abstains (line 7 in Figure I. and "UB" refers to an upper bound on the median CR for a best case smoothed model (based on Table I with My = 1). good tradeoff achieved when Pdel = 99.5% for both the byte-level (B) and chunk-level (INSN) certificates (highlighted in bold face below).
Clean accuracy
Median CR (UB)
Median NCR
Dataset
Model
Parameters
(Abstain rate)
NS
98.9
BYTE, Pde 90%
97.1 (0.2)
6
(6)
0.0023
BYTE, Pde 95%
97.8 (0.0)
13
(13)
0.0052
BYTE, Pae = 97%
97.4 (0.1)
22
(22)
0.0093
BYTE, Pde = 99%
98.1 (0.1)
68
(68)
0.0262
BYTE, Pde 99.5%
96.5 96.5(0.2)
137
(138)
0.0555
Sleipnir2
BYTE, Pde 99.9%
83.7 (3.4)
688
(692)
0.2269
RS-Del
INSN, Peel 90%
97.9 (0.1)
6
(6)
0.0026
INSN, Poel 95%
97.8 (0.1)
13
(13)
0.0056
INSN, Peel 97%
98.3 (0.0)
22
(22)
0.0095
INSN, Poel = 99%
97.6 (0.1)
68
(68)
0.0292
INSN, 99.5%
96.8 (0.2)
137
(138)
0.0589
INSN, PaN 99.9%
86.1 (0.2)
689
(692)
0.2982
NS
98.9
VTFeed
BYTE, Pas 97% BYTE, Pde 99%
92.1 (0.9)
22
(22)
0.0045
RS-Del
86.9 (0.8)
68
(68)
0.0122
arguably fall outside an edit distance constrained threat model, we consider them in our empirical evaluation of robustness in Appendix F
Clean accuracy and abstention rates Table reports clean accuracy for RS-Del and the non- certified NS baseline. It also reports abstention rates for RS-Del. the median certified radius (CR), and the median certified radius normalized by file size (NCR). We find that clean accuracy for Sleipnir2 follows similar trends certified accuracy: it is relatively stable for Pael in the range 90-99.5% but drops by more than 10% at Pdel = 99.9%. We note that the clean accuracy of RS-Del (excluding Pdel 99.9%) is most 3% lower than the NS baseline for Sleipnir2 and at most 7% lower than the NS baseline for VTFeed. We observe minimal differences in the results for chunk-level (INSN) and byte-level (BY deletion smoothing, but note that the effective CR is larger for chunk-level smoothing, since each chunk may contain several bytes.
Accuracy under high deletion It may be surprising that RS-Del can maintain high accuracy when deletion is aggressive. We offer some possible explanations. First, we note that even with high deletion probability of Pael 99.9%, the smoothed model accesses almost all of the file in expectation, as it aggregates Mpred = 1000 predictions from the base model each of which accesses a random 0.1% of the file in expectation. Second, we posit that malware detection may be "casy" for RS-Del on these datasets. This could be due to the presence of signals that are robust to deletion (e.g., file size byte frequencies) or redundancy of signals (i.e., if signal is deleted in one place it may be seen elsewhere).
Decision threshold We demonstrate how the decision thresholds v introduced in Section 3.1 be used to trade off certification guarantees between classes. We consider normalized decision thresholds where En f/y and f/y [0, 1]. We only specify the value of 7), when discussing results, noting that 17 1 1/2 in two-class setting.
Table X provides error rates and robustness metries for several values of 7) using byte-level Lev- enshtein distance with Pael = 99.5%. When varying 7,, we also vary the decision threshold of the base model to achieve a target false positive rate (FPR) of 0.5%. Looking at the table, we see that 7 has minimal impact on the false negative rate (FNR), which is stable around 7%. However, there
27

---

Table 8: Impact of the smoothed decision threshold 17, on false negative error rate (FNR) and median certified radius (CR) for malicious and benign files. The false positive rate (FPR) is set to target value of 0.5% by varying the decision threshold of the base model. The results are reported for Sleipnir2 with Pael 99.5% using byte-level Levenshtein distance. "UB" refers to an upper bound on the median CR for a best case smoothed model (based on Table with My
1).
Median CR (UB)
V/1 (%)
FNR (%)
FPR (%)
Malicious
Benign
50
6.8
0.5
137
(138)
137 (138)
25
6.9
0.5
275
(276)
57 (57)
10
6.8
0.5
455
(459)
20 (21)
6.6
0.5
578
(597)
10 (10)
7.1
0.5
582
(918)
1 (2)
0.5
6.9
0.5
506
(1057)
0
(0)
is significant impact on the median CR (and theoretical upper bound), reported separately for each class. The median CR is balanced for both the malicious and benign class when y = 50%. but favours the malicious class as 7/1 is decreased. For instance when 1)1 5% significantly larger median CR is possible for malicious files (137 to 578) at the expense of the median CR for benign files (137 to 10). This asymmetry in the class-speciff CR is feature of the theory that is, in addition to controlling a tradeoff between error rates of each class, 771 also controls a tradeoff between the CR for each class (see Table I].
Figure plots the certified true positive rate (TPR) and true negative rate (TNR) of RS-Del on the Sleipnir2 dataset for several values of 77- The certified TPR and TNR can be interpreted as class-specific analogues the certified accuracy. Concretely, the certified TPR (TNR) at radius is the fraction of malicious (benign) instances in the test set for which the model's prediction is correct and certified robust at radius r. The certified TPR and TNR jointly measure accuracy and robustness and complement the metrics reported in Table g Looking at Figure 6 we see that the certified TNR curves drop more rapidly to zero than the certified TPR curves as 1 decreases. Again, this suggests decreasing 7/1 sacrifices the certified radìi of benign instances to increase the certified radii malicious instances. We note that the curves for 7 50% correspond to the same setting as the certified accuracy curve in Figure 4 (with Pdel 99.5%).
E.2 Hamming distance threat model
We now turn the more restricted Hamming distance threat model, where the attacker is limited to performing substitutions only (O ).. We choose to evaluate this threat model as it is covered in previous work on randomized smoothing, called randomized ablation 24 (abbreviated RS-Abn), and can serve as baseline for comparison with our method. Recall that we adapt RS-Abn for malware detection by introducing a parameter called Pab. which is the fraction of bytes that are "ablated" (replaced by special masked value) (see Appendix D.2). This parameter is analogous to Pdel RS-Del, except that the number of ablated bytes deterministic
RS-Abn, whereas the number of deleted bytes is random in RS-Del. We compare RS-Del and RS-Abn for varying values of Pdel and Pab using the Slcipnir2 dataset and byte-level Hamming distance.
Certified accuracy Figure 2 plots the certified accuracy of RS-Del and RS-Abn for three values of Pael and Pab- We observe that the certified accuracy is uniformly larger for our proposed method RS-Del than for RS-Abn when Pael Pab- The superior certification performance of RS-Del is somewhat surprising given is not optimized for the Hamming distance threat model. One possible explanation relates to the learning difficulty of RS-Abn compared with RS-Del. Specifically, we find that stochastic gradient descent slower to converge for RS-Abn despite our attempts to improve convergence (see Appendix(Ci G). Recall, that RS-Del provides certificates for any of the threat models in Table addition to the Hamming distance cerificate-withee needing to modify the smoothing mechanism.
28

---

711
50%
25% .....
10%
5%
1%
0.5%
100
90
Certified TPR (%)
80
70
60
50
40
30
20
10
200
400
600
800
1000
100
90
Certified TNR (%)
80
70
60
50
40
20
10
200
400
600
800
1000
Radius,
Figure 6: Certified true positive rate (TPR) and true negative rate (TNR) of RS-Del as a function of the certificate radius (horizontal axis) and the decision threshold (line style). The results are plotted the Sleipnir2 test set for byte-level deletion (BYTE) with Paet = 99.5% under the Levenshtein distance threat model (with O {del, ins, sub)). It apparent that 7/1 controls tradcoff in the certified radius between the malicious (measured by TPR) and benign (measured by TNR) classes. Note that in this setting, non-smoothed, non-certified model (NS) achieves a clean TPR and TNR 98.2% and 99.5% respectively.
Tightness RS-Abn is provably tight, in the sense that is not possible issue larger Hamming distance certificate unless more information is made available to the certification mechanism or the ablation smoothing mechanism is changed. This tightness result for RS-Abn, together with the empirical results in Figure 2 suggests that RS-Del produces certificates which are tight close to tight practice, at least for the Hamming distance threat model. This an interesting observation, since it is unclear how to derive tight, computationally tractable certificate for RS-Del.
E.3 Summary
Our evaluation shows that RS-Del provides non-trivial robustness guarantees with a low impact on accuracy. The certified radii we observe are close the best radií theoretically achievable using our mechanism. For the Levenshtein byte-level edit distance threat model, we obtain radii of few hundred bytes size, which can certifiably defend against attacks that edit headers of PE files However, certifying robustness against more powerful attacks that modify thousands or millions of bytes remains an open challenge. By varying detection threshold, we show that certification can be performed asymmetrically for benign and malicious instances. This can boost the certified radii of malicious instances by factor of some cases. While there are no prior methods to use as baselines for the Levenshtein distance threat model, our comparisons with RS-Abn [24] for
37 38 52].
29

---

the Hamming distance threat model show that RS-Del outperforms RS-Abn in terms of both accuracy and robustness.
Evaluation of robustness to published attacks
In this appendix, we empirically evaluate the robustness of R5-Del to several published evasion attacks. By doing so, we aim to provide more complete picture of robustness, as our certificates are conservative and may underestimate robustness to real attacks, which are subject to additional constraints (e.g. maintaining executability, preserving a malicious payload, etc.). We introduce the
attacks in Appendix F.I provide details of the experimental setup in Appendix F22 and discuss the results in Appendix F3
F.1
Attacks covered
Table 9: Evasion attacks used in our evaluation. The attack distance refers the median Levenshtein distance computed on a set of 500 attacked files from the Sleipnir2 test set. We use a closed source implementation of Disp and open source implementations of the remaining attacks based on secml-malware 993
Supported settings
Attack distance
Attack
Optimizer
Description
Disassembles the PE file and displaces chunks of code to new section, replacing the original code with semantic nops.
White-box, black-box
Disp T7
17.2 KB
Gradient-guided
Replaces con-functional hytes in slack regions or the overlay of the PE file with adversarially-crafes noise.
Fast Gradient Sign Method
Slack 20
White-box
34.7 KB
Manipulates bytes in the DOS header of the PE file which are not used in modern Windows.
White-box, black-box
HDOS 37
58.0
Genetic algorithm
Manipulates fields header the PE file (debug information, section names, checksum, etc.) which do not impact functionality.
White-box, black-box
HField
17.0 B
Genetic algorithm
Appends sections extracted from henign files the end of malicious PE file and modifies the header accordingly.
GAMMA 31
Black-box
2.10 MB Genetic algorithm
We consider five recently published attacks designed for evading static PE malware detectors as summarized in Table The attacks cover a variety of edit distance magnitudes from tens of bytes to millions of bytes. While attacks that edit millions of bytes arguably fall outside constrained threat model, we include one such attack (GAMMA) to test the limits of our methodology. We note that four of the five attacks are able to operate in black-box setting and can therefore be applied directly to RS-Del. However, the white-box attacks are designed for neural network malware detectors with specific architecture. sequence as input, that the initial layer is an embedding layer, and that gradients can be computed with respect the output of the embedding layer. Although these architectural assumptions are satisfied by the base MalConv model, they are not satisfied by RS-Del, because additional operations are applied before the embedding layer and the aggregation of base model predictions is not differentiable. In Appendix H we adapt the white-box attacks for RS-Del by applying two tricks: (1) we apply the smoothing mechanism after the embedding layer, and (2) we replace majority voting with soft aggregation following Salman et al. (94).
edit distance-
particular, they assume the network receives raw byte
30

---

Table 10: Success rates of direct attacks against RS-Del and the NS baseline. lower success rate better from our perspective as defender, as it means the model is more robust to the attack. The model that achieves the lowest success rate each attack/dataset highlighted in boldface.
Attack success rate (%)
Setting
Attack
Dataset
NS
RS-Del
Sleipnir2
73.8
56.7
Disp Tv
VTFeed
94.1
74.5
White-box
Sleipnir2
57.9
85.3
Slack 20
VTFeed
96.0
43.9
Sleipnir2
0.0
HDOS 37
VTFeed
0.0
0.0
Sleipnir2
0.607
0.0
HField 38
VTFced
0.990
0.0
Black-hox
Sleipnir2
0.809
0.0
Disp
VTFced
10.9
0.0
Sleipnir2
99.2
54.1
GAMMA
VTFeed
76.2
100.0
F.2 Experimental setup
Since some of the attacks take hours run for single file, we use smaller evaluation sets containing malware subsampled from the test sets in Table The evaluation set we use for Sleipnir2 consists of 500 files, and the one for VTFeed consists of 100 files (matching [77). We note that our evaluation
sets are comparable in size to prior work [18 20 51 For each evaluation set, we report attack
success rates against malware detectors trained on the same dataset.
Since all attacks employ greedy optimization with randomization, they may fail on some runs, but succeed others. We therefore repeat each attack times per file and use the best performing attacked file in our evaluation. We define the attack success rate as the proportion of files initially detected as malicious for which at least one of the 5 attack repeats is successful at evading detection. Lower attack success rates correlate with improved robustness against attacks. We permit all attacks to run for up to 200 attack iterations of the internal optimizer. Early stopping enabled for those attacks that support it (Disp, Slack, GAMMA), which means the attack terminates as soon as the model's 'ss prediction flips from malicious to benign.
Where possible, we run direct attacks against RS-Del and compare success rates against NS as a baseline. We also consider transfer attacks from NS RS-Del threat model, where an attacker has limited access to the target RS-Del during attack optimization. When running direct attacks against RS-Del, we use a reduced number of Monte Carlo samples (Mpred 100) to make the computational cost of the attacks more manageable. For both direct and transfer attacks against RS-Del, we set Pdel 97% and perform deletion and certification the byte-level (BYTE).
important variation to the
F.3
Results
The results for direct attacks against RS-Del are presented Table 10 For both the Sleipnir2 and VTFeed datasets, we observe that the robustness of RS-Del is superior (or equal) to NS against four of the six attacks. The two cases where RS-Del's robustness drops compared to NS are for the strongest attacks: Slack and GAMMA. The results for transfer attacks from NS to RS-Del are presented in Table 11 Almost all of the attacks transfer poorly to RS-Del. most cases the attack success rates drop to zero or single digit percentages. We hypothesize that Slack and GAMMA make such drastic malicious signal-es agnaa-enough to cross to good word attack [95]. We find that HDOS and HField are ineffective for both RS-Del and the baseline NS. Both attacks change up to bytes in the header, and tend to fall within our certifications.
changes to the original binary that they can overwhelm
decision boundary-ake
31

---

Table 11: Success rates attacks transferred from NS RS-Del.
Attack success rate (%)
Setting
Attack
Dataset
NS
RS Del
Sleipnir2
73.8
0.414
Disp
17
VTFeed
94.1
White-box
Sleipnir2
57.9
2.90
Slack 20
VTFeed
96.0
1.01
Sleipnir2
0.0
HDOS 37
VTFFeed
0.0
0.0
Sleipnir2
0.607
HiField 38
VTFfed
0.990
0.0
Black-box
Sleipnir2 0.607
0.0
Disp
VTFeed
10.9
0.0
Sleipnir2
99.2
99.6
GAMMA
VTFeed
76.2
100.0
G Efficiency of RS-Del
In this appendix, we discuss the training and computational efficiency of RS-Del. We provide comparisons with RS-Abn [24), which serves as baseline in Appendix E.2 for a more restricted Hamming distance threat model.
Computational efficiency Table 12 reports wall clock times for training and prediction. For training, we measure the time taken complete I epoch stochastic gradient descent on Sleipnir2 training set, where inputs perturbed by the smoothing mechanism. For prediction, measure the time taken for a single 1MB input file using Pprdd = 1000 Monte Carlo samples. We split the prediction time into two components: the smoothing mechanism and (2) the time taken to aggregate predictions for the perturbed inputs using the base MalConv model. All times are recorded 5800X CPU and an NVIDIA RTX3090 GPU, using our PyTorch implementation of RS-Del and RS-Abn. We execute training and prediction for the base model on the GPU, and the smoothing mechanism on the CPU. We use single PyTorch process, noting that times may be improved by running the smoothing mechanism in parallel or the GPU.
(1) the time taken to generate perturbed inputs from
desktop PC fitted with AMD Ryzen 7
We now make some observations about the results. First, we note that training is an order of magnitude faster for RS-Del compared with RS-Abn. We attribute this speed-up to the deletion smoothing mechanism RS-Del, which drastically reduces the dimensionality of inputs, thereby reducing the time taken to perform forward and backward passes for the base model. On the contrary, the ablation smoothing mechanism of RS-Abn does not alter the dimensionality of inputs, so it does not have a performance advantage in this respect. Second, we observe that the total prediction time for RS-Del approximately 150% faster than for RS-Abn. We expect this difference also due to the effect of dimensionality reduction for the deletion smoothing mechanism.
Training elficiency Training curves for the base MalCony models used in RS-Del and RS-Abn provided in Figure 7 for the Sleipnir2 dataset. Due to convergence issues for RS-Abn, we adapted training to incorporate gradient clipping when updating the embedding layer. This addresses imbalance in the gradients arising from the dominance of masked (ablated) values in the perturbed inputs. However, even with this fix, we observe slower convergence a higher loss value for RS-Abn than for RS-Del. Combining the results of Table 12 and Figure 7 we conclude that RS-Abn beats RS-Abn in terms of training efficiency as it requires both fewer epochs converge and takes less time per epoch.
32

---

Table 12: Comparison of runtime efficiency for two models: RS-Del (our method with byte-level deletion) and RS-Abn (4]]. The first column of wall times measures the time taken to train each model for one epoch on Sleipnir2. The second and third columns of wall times measure the time taken to make prediction for IMB input file. This is split into two components: the time taken to generate prrdd 1000 perturbed inputs from the smoothing mechanism (second column) and the time taken to pass the perturbed inputs through the base model (third column).
Wall time
Predict
Model
Parameters
Train epoch
Smoothing
Base model
RS-Del
Peel 90%
354
10.42
0.070
RS-Abn
24
Pab 90%
1692
15.29
0.352
RS-Del
Poel 99%
329
8.79
0.043
RS-Abn
24
Pab 99%
1788
15.60
0.352
Modoh,smoothing parameter
RS E--ee.PPai -97%
RS- AS-Dee.pa Pas -99.5%
0.5
Training loss
RS-Abn.pp, -97%
0.4
RS-Abb.Pa 99.5%
0.3
0.2
0
20
40
60
80
100
Epoch
Figure 7: Training curves for RS-Del (our method with byte-level deletion) and RS-Abn [24] for the Sleipnir2 dataset.
H
Adapting attacks for smoothed classifiers
In this appendix, show how adapt gradient-guided white-box attacks account for randomized smoothing.
We consider generic family of white-box attacks that operate neural network- based classifiers, where the first layer of the network is an embedding layer. Mathematically, we assume the classifier under attack f can be decomposed as
= fembed foott Spred
(23)
where
Sembed is the embedding layer, which maps an input sequence x E X' of length n = |a|| to
an n array of d-dimensional embedding vectors;
fuott represents the subsequent layers in the network, which map embedding array to a probability distribution over classes )/: and
Spred is an optional final layer, which maps probability distribution over classes prediction (c.g., by taking the arg max applying a threshold).
33

---

The attack may query any of the above components in isolation and compute gradients of feoft. For instance, the attacks we consider [20] 37 optimize the input in the embedding space RR"d
by computing the gradient ffon((
de
While the above setup covers attacks against MalConv, classifiers with similar architectures, not directly compatible with smoothed classifiers. There are two incompatibilities. First, direct implementation of smoothed classifier (as described in Section 3.1 and Figure does not decompose like (23). And second, the aggregation of hard predictions from the base classifiers is non-differenniiall. We explain how to address these incompatibilities below.
Leveraging commutativity Consider smoothed classifier composed from a base classifier and smoothing mechanism é, and suppose the base classifier decomposes as in (33 Following Section 3.1 and Figure 1
the smoothed classifier's confidence score for class y can be expressed as
Py (x) s (a; Φ, hembed lssftt Upred 1mmy)
(24)
where
smoothy (2: 6. N E f(zi), with 24 6(x)
the (empirical) smoothing operation. This expression does not immediately decompose like (33 because the embedding layer is applied to the perturbed input 6(æ)) not æ. Fortunately, we can manipulate the expression into the desired form by swapping the order of and hembed- To do so, extend the definition of & to operate on an embedding array so that hembed (Φ(x)) @hembee (z)). i... ø and hembed commute. In particular, this can be done for randomized deletion (RS-Del) by applying the deletion edits to embedding vectors along the first dimension. Then (24) can equivalently be expressed as
Pa( = hembed smooth (0, hooot o Mpred o 10=y)
(255)
fembed
Suafe
Soft aggregation While 25 decomposes as required, the fsont component differentiable.
This is due to the presence of lipred. which is an arg max layer. To proceed, we replace the aggregation of predictions by the aggregation of softmax scores proposed by (Salman et al. [94] This yields differentiable approximation of the smoothed classifier:
Py (a:)
Rembed smooth x (d, Nooft (z))
fambed
Snatt
Salman et al. note that this approximation performs well, and is empirically more effective than an alternative approach proposed by Cohen et al. [14 Appendix G.3].
I Review of randomized ablation
In this appendix, we review randomized ablation (24, which serves as a baseline for the Hamming distance threat model in our experiments. It is based on randomized smoothing (see Section (.1) like our method, however the smoothing mechanism and robustness certificate differ. In this review, we formulate randomized ablation for sequence classifiers; we refer readers to Levine and Feizi (24 for a formulation for image classifiers.
I.1 Ablation smoothing mechanism
Randomized ablation employs a smoothing mechanism that replaces a random subset of the input elements with special null value NA. [evine and Feizi use an encoding for the null value tailored for images, that involves doubling the number of channels. This encoding is not suitable for discrete sequences, so we instead augment the sequence domain with a special null value: - $2 [NA). The hyperparameter controlling the strength of ablation must also be adapted for our setting. Levine and Feizi] use a hyperparameter that corresponds to the number of elements retained in the output. This is ineffective for inputs that vary in length, we scale l in proportion with the input length. Specifically, we introduce an alternative hyperparameter Pab (0, 1) that represents the fraction of ablated elements and set k([æl) [(1 Pab) [
34

---

Mathematicallyy the ablation mechanism has the following distribution when applied to an input sequence
Pr(Ø(#) 2]
Σ
|
(EE (2)
((())))))
where &g = fc ((x) |el k) consists of all sets of element indices of size &t and
Dis if E "retained", NA,
= ablate(x,e)) e);
if E "ablated""
Remark 10. Hyperparameter Pab has similar interpretation as Pdel for randomized deletion, in that both hyperparameters control the proportion of sequence elements hidden (by ablation or deletion) from the base classifier.
1,2 Hamming distance robustness certificate
Randomized ablation provides a Hamming distance (f)) certificate that guarantees robustness under bounded number of arbitrary substitutions. [evinne and Feizi] provide two certificates: one that makes use of the confidence score for the predicted class, and another that makes use of the top two confidence scores. We present the first certificate here, since it matches the certificate consider in Section 4 and it is the simplest choice for binary classifiers (the focus of our experiments).
To facilitate comparison with randomized deletion, we reuse notation and definitions from Section Recall from (15) that p(æ; (y) a lower bound on the smoothed classifier's confidence score Py (z; h) that holds for any input ø in the edit distance ball of radius centered on and any base classifier
such that Py (2; h) = p4y For randomized ablation, we can replace the edit distance ball with
Hamming distance ball and obtain the following result (see [24] for the derivation):
|nn
(c(( aa (<((a))))
p(x: pv) = My 1
Recall from Proposition 3 that the smoothed classifier is certifiably robust if p(z; Myy 2 By (T). where 77 denotes the smoothed classifier's tunable decision thresholds. Hence the certified radius is the maximum value of r E {0, 1, 2.2..... }} that satisfies
(12)--r)
My - 1 1
(1) 2 O.
((()))
This maximization problem does not have an analytic solution, however can be solved efficiently using binary search since the LHS of the above inequality non-increasing function of In practice, the exact confidence score (y can be replaced with a a lower confidence bound dy to yield a probabilistic certificate that holds with probability 1 - (see procedure in Figure Tand Corollary g
Since randomized ablation and randomized deletion both admit Hamming distance certificates, it is interesting to compare them. The following result, first proved by [Scholten al. (96) Proposition 5] for related mechanism, shows that randomized deletion admits tighter certificate.
Proposition 11. Consider randomized deletion classifier (RS-Del) with deletion probability p and a randomized ublation classifier (RS-Abn) with ablation fraction Pab = p. Suppose both classifiers make the same prediction y with the same confidence score Pay for input x and that we are interested issuing Hamming distance certificate of radius r. Then the lower bound on the confidence score over the certified region is tighter for RS-Del than for RS-Abn.
35

---

Proof. From Theorem 7 we have
PRS Del Mg) = Pby - + p"
(1 - p)]22]]
Hy - 1 +
[
[11
p) [
My
1
[
k(
By
+
J
(|æz)
R:( [x)) - j++1
My 1 +
j +
j=1
(-))
(Ac azl)
My 1 1
(A( ael)
PRS-Abn (z: ply)
Remark 12. et al. 25 extend randomized ablation to top-k prediction, while at the same time proposing enhancements the Hamming distance certificate. These enhancements also apply to regular classification and involve: (I) discretizing lower/upper bounds on the confidence scores; and (2) using better statistical method to estimate lower/upper bounds the confidence scores. However, both of these enhancements would have negligible impact in our experiments, as we shall now explain. The first enhancement tightens lower/upper bounds on the confidence scores by rounding up/down to the nearest integer multiple of :- 1/ (x(())))) This improves the lower/upper bound by at most
|2
k
k 2
q I min
x
2
the number of retained elements satisfies k < [x]. as is the case in our experiments. However, since we consider inputs of length |ac] 2 103, this means the improvement in the bound due to discretization is at most q S 10-3 This improvement is comparable the resolution of our estimator (I/rbod 10 10-A), and consequently, discretization will not have discernible impact. The second enhancement involves simultaneously estimating lower/upper bounds using a statistical method called SimuEM 997 SimuEM has been demonstrated to improve tightness when there are multiple classes 25 however has no impact when there are two classes (as the case our experiments).
36


Reviews:
[{"review_id": "e15UwEXnXG", "reviewer": "Reviewer_r6FS", "summary": "This paper aimed to design a certified defense for discrete sequence classifiers against edit distance-bounded adversaries. This method exploited randomized smoothing mechanism to consturct the defense and proposed RS-Del to confer robustness against adversarial delection, insertion and substitution edits.", "questions": "Please see weaknesses.", "limitations": "The authors have stated the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Different from most prior work, this paper focused on protecting models with discrete inputs (e.g., binary executables, source codes and PDF files), which was interesting and was meaningful in the real world.\n\n2. The instructions for the proposed methodology were relatively clear (including the explanations of some theorems and lemmas).", "weaknesses": "1. Although the form of the input data was different, the defenseive mechanisms for continuous fixed-dimensional inputs (such as the methods in lines 31 to 35) may also work, but this did not seem to be adequately presented. Could the authors conduct some discussion or even comparative experiments?\n\n2. The abbreviations needed to be supplemented with the full name when they appear for the first time (e.g., RS-Del). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our work and appreciating our contribution to certification for discrete modalities.\nWe respond to specific feedback below.\n\n### W1: Why can't defense mechanisms for continuous fixed-dimensional inputs be used\nA key reason why certified defenses for continuous fixed-dimensional inputs cannot be used, is because the certificates \nthey produce are ill-defined in our setting. \nTo see why, consider the most common $\\ell_p$ certificate, which guarantees robustness for any additive perturbation \n$\\mathbf{\\delta} \\in \\mathbb{R}^d$ whose $\\ell_p$-norm is smaller than some specified value $r$.\nIf we try to apply this guarantee in our setting, it says that we can add a real-valued vector to a byte sequence \nwithout changing the classifier's prediction. \nHowever, it doesn't make sense to add a real-valued vector such as $\\mathbf{\\delta} = [-0.89,  0.97, -0.94,  0.70]$ \nto a byte sequence such as $\\mathbf{x} = [78, 7\\mathrm{a}, 2\\mathrm{d}, 6\\mathrm{a}]$. \nSeparate from this issue, is the fact that an $\\ell_p$ certificate only covers inputs that are the same length, \nwhich is not very useful if inputs can vary in length. \nThese points are partly covered in lines 89–93 of our submission; we will add the above concrete example to improve clarity.\n\n### W2: Spelling out abbreviations when they first appear\nThanks, we have carefully reviewed the text to address this issue."}, {"review_id": "iFA4XXS4gC", "reviewer": "Reviewer_xRpL", "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 \n  1) how to design the smoothing distribution? The paper uses a deletion distribution by randomly removing tokens in the inputs.\n  2) how to derive the bound? The paper extensively derives a loose bound using the Neyman-Pearson lemma on the proposed deletion distribution. \n\nThe 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.  ", "questions": "Comments:\n1. $m$ never appears outside Lemma 4. Either removing $m$ from Lemma 4 or providing intuitive relation between $m$ and $p_{del}^{|\\bar{x}|-|x|}$.\n2. In line 286, Table 7->Table 8.\n\nQuestions:\n1. 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]. \n2. 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.\n3. 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.\n4. What's the performance of $f_b$?\n5. However, the NS baseline is quite weak, how about comparing RS-Del to other empirical defense approaches for malware detection?", "limitations": "The paper addresses some of the limitations. For other limitations, please refer to my points in Weakness and Questions. \n\n\n[1] Certified Robustness to Programmable Transformations in LSTMs. Yuhao Zhang, Aws Albarghouthi, and Loris D'Antoni\n\n[2] Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers.\n\n[3] Certified Robustness to Text Adversarial Attacks by Randomized [MASK]. Jiehang Zeng, Xiaoqing Zheng, Jianhan Xu, Linyang Li, Liping Yuan, Xuanjing Huang\n\n[4] Randomized Smoothing with Masked Inference for Adversarially Robust Text Classifications. Han Cheol Moon, Shafiq Joty, Ruochen Zhao, Megh Thakkar, Xu Chi\n", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "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.\n2. 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.  \n3. 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. \n2. missing related works:\n    * 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. \n    * Masking [3,4] has been used as a randomized smoothing approach for certifying the robustness of NLP models with respect to word substitutions. \n3. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for thoroughly engaging with our work and providing detailed feedback.\n\n### W1: High deletion >90% doesn't harm accuracy\nWe offer an explanation in Appendix E.1 (lines 922-929). In short, it's important to realize that a deletion probability of 90% does not mean 90% of the sequence elements are inaccessible to RS-Del. Rather, 90% of the sequence elements (on average) are inaccessible for a given Monte Carlo sample. When RS-Del is run using 4000 Monte Carlo samples, each sequence element is accessed $4000 \\times (1 - 0.9) = 40$ times in expectation.\n\n### W2: Related work\nThank you for drawing our attention to these papers. In our revision, we have cited Zhang et al. (2021) as a rare example of work that goes beyond the substitution threat model. However, we agree with the reviewer's characterization of its limitations. In particular, the perturbation spaces that can be certified in practice are quite limited (e.g., deletion of up to 2 stop words). We have also added citations to Zeng et al. (2023) and Moon et al. (2023) as examples of work covering the synonym substitution threat model (complementing refs [28] and [80] in our paper).\n\n### W3: Interpretation of Table 10\nOur claim that RS-Del achieves the lowest attack success rate (ASR) for \"five out of six attacks\" holds for each dataset individually. In our revision, we have adopted the reviewer's suggestion and only count a \"win\" for RS-Del if it achieves the lowest ASR on _both_ datasets.\n\n### C1: Removing $m$ from Lemma 4\nWe think it's important to introduce the bijection $m$ in Lemma 4, as it's used immediately after Lemma 4 to rewrite terms that appear in the smoothed classifier's confidence score. In particular, $m$ specifies which edits to $\\mathbf{\\bar{x}}$ can be expressed in terms of edits to $\\mathbf{x}$ without changing the summand $s$ (up to a proportionality constant).\n\n### C2: Incorrect reference\nThanks, we have fixed this.\n\n### Q1: Improving the bound following Lee et al. (2019)\nLee et al. provide a generic framework for computing robustness certificates for randomized smoothing based on the Neyman-Pearson lemma. We previously considered their framework and determined it would be computationally infeasible for our mechanism/threat model. To explain why, consider the first step in their framework: computing a pointwise certificate that guarantees the smoothed classifier's prediction at $\\mathbf{x}$ does not change at a neighboring input $\\mathbf{\\bar{x}}$. This requires partitioning the support of the deletion mechanism into regions, such that the relative likelihood of perturbing $\\mathbf{x}$ and $\\mathbf{\\bar{x}}$ to any point in the region is constant. For our mechanism, the relative likelihood does not simplify in general and takes $O(2^{\\max \\{|\\mathbf{x}|, |\\mathbf{\\bar{x}}|\\}})$ time to evaluate in the worst case. This makes the first step of their framework infeasible, let alone the second step, where one must search for the worst-case pointwise certificate in the edit-distance ball.\n\n### Q2: Inequality or equality in Corollary 6\nWe believe we’ve found the source of confusion. The expression for the lower bound $\\tilde{\\rho}(\\mathbf{x}, \\mathbf{\\bar{x}}, \\mu_y)$ in eqn (14) conceals a dependence on the LCS ($\\mathbf{z}^\\star$). In Corollary 6, we instantiate $\\tilde{\\rho}(\\mathbf{x}, \\mathbf{\\bar{x}}, \\mu_y)$ for a _particular_ LCS to obtain a loose lower bound on $\\rho(\\mathbf{\\bar{x}}, \\mathbf{x}, \\mu_y)$ (this is fine since the bound holds for _any_ LCS). The LCS we choose is defined in terms of the cost-minimizing edit path from $\\mathbf{\\bar{x}}$ to $\\mathbf{x}$, consisting of $n_\\mathrm{sub}$ substitutions, $n_\\mathrm{del}$ deletions and $n_\\mathrm{ins}$ insertions. Specifically, it is the sequence obtained from $\\mathbf{x}$ by deleting the $n_\\mathrm{sub}$ elements substituted in $\\mathbf{x}$ and deleting the $n_\\mathrm{ins}$ elements inserted in $\\mathbf{x}$ (see Appendix B.4). This means the equality in Corollary 6 is correct, provided one understands that the LHS depends on the LCS. To avoid confusion, we have made the dependence on the LCS ($\\mathbf{z}^\\star$) explicit (in our revision) by using $\\tilde{\\rho}(\\mathbf{\\bar{x}}, \\mathbf{x}, \\mu_y, \\mathbf{z}^\\star)$ in eqn (14) and propagating the change through eqn (15) and Corollary 6.\n\n### Q3: Meaning of “unbounded length” sequence\nWe used this phrase to emphasize that our method does not place any limits on sequence length—e.g., we do not require that sequences are padded to a common length. However, upon reflection, we think \"variable length\" is sufficient to capture this meaning. We have therefore removed \"unbounded length\" in our revision.\n\n### Q4: Performance of the base classifier\nIn this work (and prior work on randomized smoothing) the base classifier is not trained to perform well as a standalone classifier. Rather, it is trained to function as a component of the smoothed classifier, where it encounters inputs transformed by the smoothing mechanism. It would therefore be unusual to conduct a standalone evaluation of the base classifier on natural inputs.\n\n### Q5: Comparing with other empirical defenses for malware detection\nWhile the malware literature would benefit from a comparison of empirical defenses, we feel it would best be presented in a separate paper. The focus of this paper is on advancing certification for sequence classifiers; we have developed algorithmic innovations with our randomized deletion mechanism, and corresponding theory to prove certifications. This explains the focus on certification in our experiments, where we include Levine & Feizi (2020) (and Jia et al. (2022) in our revision) as the closest certified baselines we are aware of. The purpose of the empirical robustness experiments is not to compare against empirical defenses, but rather to explore the magnitude of common attacks (in edit distance) and assess robustness beyond radii we can certify."}, {"review_id": "wDsM7QT4b3", "reviewer": "Reviewer_bHHQ", "summary": "This paper tackles the issue of applying randomized smoothing to discrete sequences under the Levenshtein edit distance. Because the underlying sequence is discrete, it necessitates new mathematical approaches to proving the robustness. Enticingly, the edit distance is bounded by employing only the delete operation, making implementation and application far easier than would have otherwise been possible. Noting the inequity in attack risk for malware/security applications, effective bias terms $\\eta$ are added to allow asymmetric certificates of robustness. Since no prior work has obtained this result, they compare against a prior hamming certificate, and show significant improvement over prior results in the smaller Hamming space. \n\nThe application to malware is very apt, but this is also relevant to all the domains of which the Levenshtein edit distance is applicable: genomics, time series analysis, epidemiology, linguistics/NLP, etc. ", "questions": "I honestly can't think of any questions to ask beyond random directions of obviously future work. The appendix is detailed, has code, and the paper is exceptionally well written. \n\nTo the AC, please note that my shorter review isn't a remark against thoroughness in reading the work. It just answered all the questions I would have asked. This work is of exceptional quality, presentation, and impact. ", "limitations": "This work has no realistic limitations beyond not \"solving\" all problems in one go. Other challenges of randomized smoothing naturaly remain, and can't be held against the authors given the work's goals and how well it has achieved them. ", "rating": 9, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. This is allowing results in a whole new category of model/hypothesis spaces for randomized smoothing. \n2. The results show significant improvement as the maximum radius is reached over closest-prior alternatives \n3. The method is easy to implement \n4. Real-world consideration to asymmetric attack profile is considered and incorporated into the approach, while not firefighting the multi-class support. \n5. The paper is beautifully written and the best I have read in reviewing over probably the past 2 years. ", "weaknesses": "1. The only weakness to the paper is some missing references. The asymmetric nature of benign vs malicious attacks was previously noted in \"Non-Negative Networks Against Adversarial Attacks\" and \"Adversarially Robust Malware Detection Using Monotonic Classification\", and the two should be cited accordingly. Notably, both only deal with the additive threat model $O = [ \\texttt{ins} ]$, filling in the broader contribution of this work in completing the Levenshtine operation set. \n2. If I had to add a second quibble, I would ask the authors to caution the reader about applying the % certification to other datasets, because each dataset will differ and industrial-scale classification datasets are beyond the scope of proving the mechanism's correctness. (I could see industry research getting weird reviews from academics who don't understand this when attempting to publish case-studies). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing such encouraging feedback. We are pleased the reviewer recognized the novelty of our work in extending randomized smoothing to new threat models for discrete domains. We also appreciate the reviewer's pragmatic assessment of the limitations.\n\n### W1: Missing references\nThank you for identifying references on the asymmetry of misclassification costs for malware detection by Incer et al. (2018) and Fleshman  et al. (2018). We have added citations to both references in Remark 1. While we are not the first to point out this asymmetry, to the best of our knowledge we are the first to consider asymmetric certified robustness for classification. \n\n### W2: Caution about applying certification results to other datasets\nThanks for making the point that experiments cannot prove the correctness of the robustness guarantee (which is covered by the analysis in Section 4). While the experiments support the effectiveness of our approach, we understand the reviewer's concern that readers may falsely assume that the results generalize to other datasets. In our revision, we have identified this as a limitation in the final paragraph of Section 7."}, {"review_id": "w4Y3kQL4j4", "reviewer": "Reviewer_MXYp", "summary": "This paper proposes **RS-Del** -- a novel certified defense that provides guarantees w.r.t. insertion, deletion, and substitution of bytes within a variable length input.  As its name indicates, RS-Del is based on randomized smoothing.  However, unlike classic randomized smoothing, the authors cannot certify robustness using the Neyman-Pearson lemma and instead propose a novel certification scheme.", "questions": "See my comments above under \"Weaknesses\".", "limitations": "I understand why the authors placed Table 1 where they did (put simply -- space).  However, the table's explanation does not appear until the next page.  When I first saw the table, I did not understand the table and thought perhaps I had missed something.  I think separating the tables on separate pages would be a better choice.  To prevent a significant increase in length, NeurIPS allows text to wrap around inline figures and tables.\n\nThe authors could provide more intuitions about why their setting needs turnable decision thresholds $\\eta_y$ while most other randomized smoothing applications do not.  Tying this explanation to their case study/expected end use would make the explanation much more compelling.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper has a lot to like.  Overall the writing quality was good. Ideas were structured and explained well.  The writing was clear.\n\nCertified and robust training literature is dominated by works centered on some variant of an $\\ell_p$ threat model. It is rare to see a paper that prevents as novel of a certified threat model as this one.  Reading a paper with such an innovative threat model is refreshing and welcome.\n* I would further argue that some in the adversarial ML community do not appreciate how myopically the research community focuses on narrow definitions of robustness.  The paper's \"Related Work\" section does a good job of explaining this point.  I appreciated reading the author's perspective in this regard.\n\nThe most closely related work I am aware of is Saha et al. (2023) (which the authors cite).  I find RS-Del's threat model and type of guarantee much more useful and innovative.  Having looked at both papers, I find this work substantially stronger and more compelling.", "weaknesses": "There are a lot of things I like about the paper.  That notwithstanding, this paper feels more appropriate for a security venue than an ML venue.  Understanding malware and the meaningfulness of guaranteeing robustness up to $m$ bytes is generally beyond the expertise of most ML readers (and reviewers).  I believe this paper would be a better fit and better appreciated at a venue like S&P or Usenix than at NeurIPS.  The misalignment with the venue slightly reduced my score.\n\n### Empirical Evaluation\n\nTo the extent of my knowledge, no other method provides guarantees w.r.t. to Levenshtein distance.  The authors select randomized ablation (RA) [Levine and Feizi 2020] as the primary baseline for Hamming distance.  Levine and Feizi's RA is far from the state-of-the-art $\\ell_0$ certified method at this point.  Two works consistently outperform vanilla RA:\n\n[1] Jinyuan Jia, Binghui Wang, Xiaoyu Cao, Hongbin Liu, and Neil Zhenqiang Gong. \"Almost Tight $\\ell_0$-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations\". ICLR 2022. https://openreview.net/forum?id=gJLEXy3ySpu.\n\n[2] Zayd Hammoudeh and Daniel Lowd. \"Feature Partition Aggregation: A Fast Certified Defense Against a Union of Sparse Adversarial Attacks\". arXiv 2302.11628. https://arxiv.org/abs/2302.11628\n\nJia et al. is based on RA and provides tight(er) certification analysis.  Hammoudeh and Lowd use model ensembles.  This paper does not cite either of these papers (Hammoudeh and Lowd is a newer preprint so I understand why the authors may not have seen it). However, at minimum, Jia et al.'s version of RA must be a baseline of comparison. \n* I would have voted \"Borderline Accept\" with the paper as is had at least Jia et al. (2022) been used as a baseline. Updating the baselines is a necessary condition for me to increase my score. I cannot recommend accepting this paper without at least Jia et al. (2022) as a baseline.  I strongly recommend adding both baselines or at minimum a compelling explanation in the rebuttal why one is not possible.\n\n### Interpreting the Empirical Results\n\nThe authors specify their certified guarantees in terms of the number of bytes.  I have two primary concerns about this framing.\n\n1. Existing certified methods also specify their guarantees in absolute terms. For example, RA provides median guarantees on CIFAR10 of 7 pixels. Providing guarantees in absolute terms makes sense when instances have a fixed size; its trivial to convert that result into a relative quantity (e.g., 1% of pixels). When test instances have variable sizes as in the case here, no simple conversion exists. For a reader to be able to appreciate how meaningful a guarantee of 128 bytes is, we need to understand the typical range of malware sizes.  At an ML venue, such information needs to be provided in the main paper.  Moreover, it is the author(s)'s responsibility to explain how the size of the guarantee changes with malware size.  \n\n2. Providing certified guarantees as a fraction of malware size is only a small part of the equation. I expect that most ML readers do not know a priori the extent of changes that must be made to a program to induce a change of 128 bytes. For example, would simply recompiling the program with no code changes and just compiler setting changes be sufficient to change the binary by 128 bytes?  I do not have expertise in that area, and the authors do not educate the reader in this regard.  I consider this choice to be a significant oversight.\n\n### Interpreting the Empirical Results\n\nCertified $\\ell_0$ method randomized ablation (RA) is used as the primary Hamming distance baseline.  However, the authors provide little to no explanation of how RA works.  I think this is important so a reader not familiar with RA can appreciate what is being tested in the experiments. Moreover, the authors need to explain how their method differs from RA when restricted to exclusively the substitution setting.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and constructive feedback. \n\n### RE: fit for NeurIPS\nWe believe our paper is aligned for NeurIPS (see below), and note that this was not a concern raised by other reviewers. Our paper advances certified robustness for generic sequence classifiers, providing both algorithmic and theoretical contributions for a previously unexplored threat model. These are contributions the machine learning community has historically been interested in—by our count 10 papers on certified robustness appeared at NeurIPS last year. We view malware as a compelling domain to test our method, given growing reliance of malware detection methods on machine learning and the domain's real threat of evasion attacks. Our empirical evaluation focuses on certification not malware defense.\n\n### RE: baselines for Hamming distance\nThank you for suggesting Jia et al. (2022) and Hammoudeh & Lowd (2023) as alternative baselines and for offering to raise your score. We discuss them separately below.\n\n**Jia et al. (2022):**\nAfter receiving this review, we implemented Jia et al.'s method and incorporated it into the certified accuracy plot (updated Figure 2 in the **rebuttal PDF**). We find the certified accuracy curve for Jia et al. (denoted RS-Jia) is identical to the curve for the existing baseline by Levine & Feizi (denoted RS-Abn). This is not surprising given Jia et al.'s certification method for top-k prediction is very similar to Levine & Feizi's method when instantiated for binary classification ($k = 1$). More specifically, Jia et al. use the same ablation smoothing mechanism, and while they do derive a tighter certificate, the difference is negligible in a high dimensional setting. To explain why the difference is negligible, we note that Jia et al.'s tighter certificate comes from a tighter lower bound on the smoothed classifier's confidence score. In particular, they tighten the lower bound by rounding up to the nearest integer multiple of $q = 1 / {d \\choose r}$ (where $d$ is the length of the sequence and $r = \\lceil p_\\mathrm{abn} d \\rceil$ is the number of ablated elements). The difference between the original lower bound and the tighter one is no larger than $q \\leq 10^{-3}$ in our experiments, since $d \\geq 10^{3}$ for the sequences we consider and $p_\\mathrm{abs} \\leq 0.999$. Thus in the worst case, the difference is of a similar order to the resolution of the Monte Carlo estimator ($1/4000 = 2.4 \\times 10^{-4}$), which explains why the tighter bound does not have a discernible impact.\n\n**Hammoudeh & Lowd (2023):**\nThis work looks interesting as it is not based on randomized smoothing like the other baselines for Hamming distance. We will add a citation to it, however adding it as a baseline would require non-trivial changes for two reasons.\nFirst, the formulation is fundamentally different: Hammoudeh & Lowd assume all inputs have the same dimensionality (Section 2 of their paper), whereas the dimensionality of our inputs vary. Second, the current code base would require significant refactoring to work with large datasets, as it loads the entire training set and test set in memory. This is infeasible for our datasets which are hundreds of GB in size. \n\n### RE: absolute versus relative certified radius\nOur certificates are independent of sequence length (see Table 1). This means the _absolute_ certified radius is better aligned with the theory—it allows us to compare radii without artificially introducing a dependence on sequence length. That being said, we agree that _relative_ certified radius is useful as a complementary metric. In our original submission, we reported the median relative certified radius (referred to as the normalized certified radius) in Table 7 of Appendix E.1. In our revision, we have updated Figures 4 and 5 to include a plot of certified accuracy versus relative radius, alongside the existing plot for absolute radius (see **rebuttal PDF**). We will endeavour to include such results for relative radius in the main paper.\n\n### RE: interpretation of edit distance\nWhether an edit distance can be regarded as \"small\" or \"large\" depends on the application and threat model. For our application to malware, we report the median edit distance induced by several attacks in Table 9. The distance varies from 10's of bytes to millions of bytes, depending on the attack. We appreciate and agree with the reviewer's comments on the need to assist the reader; we will include a discussion of interpreting edit distances in malware in terms of cited/tested attacks, file sizes, and with reference to the relative certified radii from the previous point.\n\n### RE: background on randomized ablation\nThank you for this suggestion. We will add a brief description of randomized ablation (RS-Abn) in Section 5, noting the following differences from RS-Del: (1) RS-Abn performs substitution with a special \"masking\" value whereas RS-Del performs deletion; (2) the number of elements to edit is fixed for RS-Abn but follows a binomial distribution for RS-Del; (3) RS-Abn provides a Hamming distance certificate, whereas RS-Del provides a generalized edit distance certificate. We will also provide a more detailed summary of RS-Abn in a new appendix, where we will also provide an explicit comparison with RS-Del for the Hamming distance setting."}]

Author rebuttal:
We thank the reviewers for their positive reception of our paper and for providing us with constructive feedback. 

We would like to draw the reviewers' attention to the attached rebuttal PDF, which contains updated figures/results in response to Reviewer MXYp. For the benefit of the other reviewers, we briefly summarize the contents below: 
* Figure 2 contains a new baseline for the Hamming distance threat model by Jia et al. (2022) (denoted RS-Jia). It uses a tighter certificate compared to the existing baseline by Levine & Feizi (2020) (denoted RS-Abn), however we find the improvement is negligible in our high-dimensional setting. 
* Figures 4 and 5 have been expanded to include a plot of certified accuracy as a function of normalized radius (radius divided by sequence length). This was prompted by Reviewer MXYp's suggestion to report how the size of the guarantee compares to the sequence length (which varies for each input). The new plots complement the existing plots for absolute radius in Figures 4 and 5, and the existing column in Table 7 containing the median normalized certified radius. For further discussion of the normalized radius, we refer to our third response to Reviewer MXYp.

### References
* Jia, J., Wang, B., Cao, X., Liu, H., & Gong, N. Z. "Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations." ICLR'22.
* Levine, A., & Feizi, S. "Robustness certificates for sparse adversarial attacks by randomized ablation." AAAI'20.

Meta-review: The paper introduces a new randomized deletion mechanism for smoothing and certifying black-box models on sequence data under edit distance threat models. The reviewers liked the work as it is looking at protecting models with discrete inputs; also the presentation of the work is clear. Some weaknesses in experimental results, comparison with baselines and other methods were identified that authors properly addressed in the rebuttal period.
Decision: Accept (poster)