On Adversarial Examples for Character-Level Neural Machine Translation

In plain words

A translation model that reads text one character at a time can be thrown off by a few typos. Earlier attacks on such models mostly used black-box heuristics, such as random typos, and checked whether the output got worse. This paper assumes the attacker can look inside the model. With that access, it can estimate how much each possible one-character edit will hurt the output, and then pick the most damaging edits under a limit on how much of the sentence may change.

The attacker also has more specific goals than "make the translation worse". It can try to delete one particular word from the translation, or to replace it with a different word. Those goals are harder to reach, but the same search handles them once the score is changed. The authors then train the model on such edited sentences alongside the clean ones. The model becomes harder to attack this way, but training takes longer.

TL;DR

• Attacks a character-level NMT model (character CNN, highway layers, LSTM, attention) trained on IWSLT 2016 TED data for French, German and Czech to English §4 tab. 2.
• Scores each candidate edit with one forward and one backward pass, then searches with greedy or beam search under a budget of 20% of the characters §3.2 §3.4.
• Adds controlled attacks (mute a word) and targeted attacks (replace a word). White-box edits are clearly stronger than black-box edits in these two settings §5.
• One-shot adversarial training on white-box edits, mixed with black-box noise, gives the best average BLEU across the test sets in each of the three language pairs. These are author-reported numbers §6 tab. 6.

Problem

Black-box attacks query the model without gradients and rely on heuristics. The authors argue these heuristics do not reveal a model's worst case §1. Text is discrete, so the gradient cannot be applied to it directly. The authors work with one-hot character inputs instead §3.2. In translation, a corrupted output can be much worse than a lower BLEU score. Removing a key word, or inserting a wrong one, can change the meaning of the sentence §1 §3.3. The paper shows a real case in its introduction, where a one-character change in an Arabic word led to a wrong translation §1.

Character-level models are a natural target. They extract morphology from characters and so generalise to unseen words §2. The same property means that small character edits reach the model's features directly §2 §3.

Method

Setup and notation

• J(x, y) is the log-loss of the translation model on source x and target y §3.1.
• Each source word has up to n character slots, and each character is a one-hot vector over the alphabet V. Shorter words are padded §3.1.
• Four edit operations exist: flip (replace one character), swap (exchange two adjacent characters), delete and insert §3.
• The attacker may change at most a fixed number of characters, the budget r. Here the budget is 20% of the characters in the sentence §3.4. The code also enforces a minimum of one change attack.lua.

First-order edit score

The change in loss for a flip from character a to b at position j of word i is estimated from the gradient along the flip direction. This directional derivative is the score that ranks candidate edits §3.2 eq. 1.

# Score for changing character a to b at position j of word i  [§3.2] [eq. 1]
# grads: (words, chars, |V|) gradient of the loss w.r.t. one-hot input
def flip_score(grads, i, j, a, b):
    # Directional derivative along the flip vector  [eq. 1]
    return grads[i, j, b] - grads[i, j, a]    # scalar

Insert, delete and swap are scored in the same way, by summing gradient terms for the characters that shift §3.2. The paper gives no closed formula for them. The authors also normalised the operation vectors by their L1 and L2 norms, and report little effect §3.2. The implementation is in char_manipulations.lua.

Search strategies

• One-shot (untargeted training). Every word receives its best local edit in one parallel step. This needs a single forward and backward pass, and it is the variant used for adversarial training §3.4 (a).
• Greedy. Take the best edit over the whole sentence, recompute the gradient, and repeat until the budget or the goal is reached §3.4 (b).
• Beam search. Keep the b best partial edit paths. Each path is scored by its true loss so far plus the gradient estimate of its next edit. The cost is O(b r) forward and backward passes §3.4 (c).
• Only edits that create a word outside the source vocabulary are allowed §4.

# Beam search for one controlled or targeted attack  [§3.4] [§3.3]
# Input:  source chars, target word index, budget r, beam width b
# Output: adversarial source, or None when the budget is used up

def beam_attack(source, target_index, budget, beam_width):
    # Start from the best single edits  [§3.4 (c)]
    beam = best_single_edits(source, target_index, beam_width)
    for step in range(budget):
        # Extend each path by one edit; score = true loss + gradient estimate
        # [§3.4 (c)]
        candidates = expand(beam, source, target_index)
        for candidate in candidates:
            adv = apply_edits(source, candidate)
            # Stop when the goal word is removed or replaced  [§3.3]
            if goal_reached(adv, target_index):
                return adv
        # Keep the best beam_width candidates, without duplicates  [§3.4 (c)]
        beam = top_unique(candidates, beam_width)
    return None

Attack goals

• Untargeted: maximise J(x, y), so the output gets worse in general §3.3.
• Controlled ("mute"): maximise J(x, y_t) for the target word t of the clean translation. The attacker ignores the rest of the output §3.3.
• Targeted ("push"): maximise -J(x, y_t') for a new word t'. This is the same as minimising the loss of t' §3.3. The new word is usually the n-th most likely word at that position. The default is the second most likely, and the paper also tests the 100th §5.3 §5.4 tab. 5.

The paper defines a success rate with a threshold α. An attack succeeds when the BLEU score of the adversarial output, relative to a reference output in which the target word is replaced by an unknown token, reaches α §5.2. The text does not give values of α; they appear only on the figure axes fig. 2 fig. 3. The targeted metric is defined the same way with a "push" reference §5.3.

Adversarial training

• Each mini-batch is first passed forward and backward on clean data. Adversarial edits are then built from those gradients with the one-shot strategy, and the batch is trained on again §6.2.
• Each word's edit type is drawn from a mix that matches the natural-noise corpora. Flip, insert, delete and swap (FIDS) operations account for 64% of the natural noise in Czech, 80% in German and 70% in French §6.2 fig. 4.
• Training on adversarial examples alone gave poor clean BLEU. Clean and adversarial examples are therefore both used §6.2.
• An ensemble variant mixes white-box examples and black-box Nat and Rand examples, half and half §6.2.
• Adversarial training costs about three times as much as regular training §2.

# One training step on a mini-batch with one-shot white-box examples
# [§6.2] [§3.4]
# Input:  source, target (one mini-batch); model; learning rate
# Output: updated model

def adversarial_step(model, source, target):
    # 1. Clean forward and backward pass; keep gradients w.r.t. input  [§6.2]
    clean_loss, input_grads = forward_backward(model, source, target)
    # 2. Update weights on the clean batch  [code: adversarial_train.lua#L573]
    sgd_update(model, clean_loss)
    # 3. Draw one edit type per word from the language's noise mix  [§6.2]
    edit_types = sample_edit_types(source)    # (batch, words)
    # 4. Apply each word's best edit of its drawn type, all at once  [§3.4 (a)]
    adv_source = one_shot_edit(source, input_grads, edit_types)
    # 5. Forward and backward pass on the adversarial batch  [§6.2]
    adv_loss, _ = forward_backward(model, adv_source, target)
    # 6. Update weights again on the adversarial batch
    # [code: adversarial_train.lua#L648]
    sgd_update(model, adv_loss)
    return model

Model

• The encoder is a character model. Character embeddings feed convolutions of several widths, then highway layers, then a stack of recurrent layers §4. The paper calls it a seq-to-seq attentional translator built on Yoon Kim's seq2seq-attn code, with "similar hyper-parameters" §4. The implementation is in models.lua and models.lua.
• The decoder is word-level, with attentional translation following Luong et al. §4 adversarial_train.lua adversarial_train.lua.
• The paper says its BLEU scores are competitive with IWSLT submissions §4. No number is given in the text.

Hyperparameters

Values stated in the paper are cited to the paper. Values marked code only are not in the paper text; they come from the authors' code at code_commit.

Results

Author-reported. The attacks in Section 5 use greedy decoding. The robustness tests in Section 6 use beam width 4 §4. The two sets of numbers are not directly comparable.

Untargeted attacks, BLEU after attack (lower is stronger) tab. 3

The authors say black-box and white-box attacks perform close to each other in this untargeted setting, so they argue for goal-based evaluation §5.1.

Controlled and targeted attacks fig. 2 fig. 3 tab. 4

• Controlled attacks: the white-box success rate is clearly higher than the black-box rate over the swept α values §5.2 fig. 2.
• Targeted attacks (second most likely word): success is much lower. The white-box rate is still well above the black-box rate. For the 100th most likely word, the success rate is more than ten times smaller than for the second most likely word §5.3 fig. 3.
• Efficiency of the controlled attack at the 20% budget tab. 4:

The paper notes that white-box attacks need extra backward passes and sorting, so running times end up comparable §5.2.

Adversarial training, BLEU on clean and noisy test sets tab. 6

Columns: Clean; Nat, Key and Rand are noisy test sets built with the black-box noise types of the baseline; FIDS-B and FIDS-W are the FIDS-noise test sets (black-box and white-box). Avg is the mean of the six columns in each row, except for one row noted under Pitfalls.

French to English:

German to English:

Czech to English:

Reading of tab. 6: the ensemble has the best average in all three pairs. The white-box-only model (FIDS-W) has the best score on the FIDS-W test column, and the best Rand score among models not trained on Rand. Clean BLEU of the ensemble is higher than vanilla for French and lower for German and Czech. Clean BLEU of FIDS-W is lower than vanilla for French and Czech and equal for German.

Paper vs code

The official repository is linked from the paper's footnote §4: https://github.com/jebivid/adversarial-nmt, MIT licence, at commit 736fbb0a3cf764728a3a7db62906de672b498d96. Discrepancies:

• Controlled attack search. The paper says the controlled attack is greedy §3.4 (b). The attack script runs the same beam search for controlled and targeted attacks, with a default beam size of 5 attack.lua attack.lua. Greedy behaviour needs -beam_size 1.
• Success test. The paper defines success as a BLEU ratio above α §5.2. The code declares a controlled attack successful when the original target word is absent from the adversarial output. A targeted attack is successful when the original word is absent and the chosen replacement is present attack.lua. The BLEU ratio is computed but not used in the test attack.lua.
• Choice of target word. The paper does not say how the target word is picked. The code shuffles the output positions and takes the first word that is longer than one character, is not a stop word, and contains no & attack.lua. For a targeted attack, the code also skips words that contain or are contained in the original word attack.lua.
• Adversarial training updates. The paper says clean and adversarial examples are both used §6.2. The code applies two separate SGD updates per mini-batch, one for the clean batch and one for the adversarial batch adversarial_train.lua adversarial_train.lua.
• Second flip. The code adds a second flip to a word with probability about 0.34, when the first edit is a flip adversarial_train.lua. The paper does not mention this.
• Edit mix. The paper gives coverage percentages only §6.2. The code uses fixed per-language vectors adversarial_train.lua. The Czech swap probability is 0.
• Single-word sentences. Adversarial examples are generated only when the batch's source length is more than one word adversarial_train.lua adversarial_train.lua. The paper does not say this.
• Hyperparameters not stated in the paper. Learning rate, optimiser, epochs, decay, dropout and sizes are not stated in the paper text. The code values are in the Hyperparameters table.
• Baselines. The black-box noise generator used for Nat, Key, Rand and the FIDS-B baselines is an external script §6.1. The repository contains no noise generator and no untargeted attack script. Its attack.lua covers only controlled and targeted attacks, as the README says. The repository also refers to a stop-word file, WSLT/stop.words attack.lua, which is not included.
• Unused options. -threshold is declared but not used [code: adversarial_train.lua#L103]. exhuasted_word is defined but not called beam_search.lua.

Pitfalls

• Success rate. The BLEU-ratio success rate of §5.2 cannot be reproduced from the code alone, because the code uses word presence. Define the reference output (target word replaced by an unknown token) and the threshold yourself.
• First-order estimate. The gradient score is linear. On the German test set, the Spearman correlation between the estimate and the true loss change is 0.61 §5 fig. 1. It is good enough for ranking, not for measuring the loss change.
• Two updates per batch. Each mini-batch gives two SGD updates, so adversarial training is not a simple reweighting of one loss. The code has -only_adversarial for adversarial-only training adversarial_train.lua, but the paper reports that clean BLEU drops without clean examples §6.2.
• Cost. The "three times" training cost §2 is author-reported. The code runs two forward and backward passes per batch, plus edit generation. The real ratio depends on the implementation. For the controlled attack, the white-box query counts in tab. 4 are 1.2k to 2.3k, against 6k to 9k for the black-box attack. The table does not say what one query count covers.
• Greedy gradients. The white-box attacker uses greedy decoding to get gradients. Beam decoding would need gradients through the beam paths, which the authors say is costly §4.
• Word length cap. The code fixes the maximum word length at 35 characters char_manipulations.lua. The paper gives n but no value.
• Index -1 in shift_left. The line instance[-1]=1 writes at index -1 in the delete routine char_manipulations.lua. This looks unintended, and I did not run it to see what it does.
• cuDNN needed. The non-cuDNN branch of the character CNN never fills the pooling layers models.lua. The default -cudnn 1 path is the one to use adversarial_train.lua.
• Different decoders. Table 3 uses greedy decoding and Table 6 uses beam width 4 §4 tab. 3 tab. 6. Do not compare the two tables directly.
• Average column. In Table 6, the French Vanilla row lists Avg 15.95, but the mean of its six printed columns is 14.30. The other rows match within rounding. The averaging rule is not stated in the paper.
• Meaning preservation. The active text has no human study of whether edited sentences keep their meaning. The examples in tab. 1 and tab. 5 show changed outputs, not checked meanings.
• Variance. The active text reports single numbers without run-to-run spread.
• Data size. Training sets are 122K to 235K sentence pairs of TED talks tab. 2. Results on larger or other domains are not measured in the paper.

Lineage

• Builds on: HotFlip, Ebrahimi et al. (ACL 2018). The paper adds insert, delete and swap, ranks beams by true loss plus gradient estimate instead of the sum of gradients, and uses a one-shot adversarial training step §1 §2 §3.4 (c). The source gives no arXiv id, so there is no link.
• Compared against: black-box noise training by Belinkov and Bisk (ICLR 2018) §2 §6.1. The source gives no arXiv id, so there is no link.
• Superseded by: not stated in this wiki.