Pith. sign in

REVIEW 3 major objections 4 minor 17 references

Adversarial Edit Attacks for Tree Data

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A black-box attacker can fool established tree classifiers by applying tree edits, using only the tree edit distance and O(log(|x|+|y|)) classifier queries, with no gradient information.

desk verdict A useful first black-box attack for tree classifiers, but the closeness guarantee is unproven and the evaluation table contradicts its own success definition. read the letter →

arxiv 1908.09364 v2 pith:FZE7HAQS submitted 2019-08-25 cs.LG stat.ML

Benjamin Paa{ss}en This is my paper · ORCID
classification cs.LGstat.ML
keywords adversarialexamplestreeeditdistanceblack-boxattackclassificationbacktracingkernelsrecursiveneuralnetworksstructureddata
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces adversarial edit attacks, a black-box scheme for fooling tree classifiers. Instead of gradients, it relies on the tree edit distance: pick a reference tree with a different label, trace a shortest edit script from the input toward it, and binary-search the shortest prefix of that script that flips the predicted label. The number of queries to the classifier is logarithmic in the sizes of the two trees. On two programming and two biomedical data sets, the attack succeeds against tree-kernel SVMs and recursive neural networks, establishing that tree-structured classifiers are vulnerable to adversarial examples just as image classifiers are.

What carries the argument

The central machinery is the tree edit distance and its backtracing. The tree edit distance is the minimum number of node deletions, replacements, or insertions needed to change one tree into another, computable by dynamic programming. Backtracing recovers a shortest, co-optimal edit script between the original tree x and the reference tree y. The attack then treats classifier predictions along this script as a binary predicate — does the prefix still have the original label? — and runs binary search over prefix lengths to locate the first edit that flips the label. This is what turns an unconstrained tree edit search into a logarithmic-query procedure.

What would settle it

Record the classifier's predicted label after every prefix of a traced edit script across many attack runs; if any trajectory shows the label switching from the original to the target and back, the binary-search premise is violated, and the returned prefix may not be the shortest label-changing edit.

Watch

Extended reading notes

Core claim

The central claim is that tree-structured classifiers can be attacked in a black-box manner with no gradient information, using only tree edit distance computations and O(log(|x|+|y|)) classification queries. For a test tree x with label f(x), the attack finds a reference tree y with a different target label f(y)=ℓ, computes a co-optimal edit script from x to y, and applies binary search over prefixes to return the shortest prefix z whose label is ℓ. The paper argues z is a genuine adversarial example when the prefix is shorter than half of the full script, because then d(x,z)<d(z,y), so z stays closer to x than to any tree with the label ℓ. Experiments over seven classifiers and four data sets show that backtracing attacks succeed more consistently than a random-edit baseline, although random attacks sometimes find adversarial trees that are closer to the original sample.

Load-bearing premise

The binary-search step assumes that as the edit script is applied prefix by prefix, the classifier's predicted label changes at most once, from the original label to the target label; if the label flips back and forth along the path, the search may return a prefix longer than the shortest one that flips, and the guaranteed closeness to the original tree no longer follows.

Editorial extensions

If this is right

  • An attacker with only label queries can mount targeted attacks on tree classifiers used in medicine and program analysis, needing no weights, gradients, or training data.
  • The number of classifier queries grows only logarithmically with tree size, so even large parse trees or molecular structures can be attacked cheaply.
  • Backtracing attacks succeed more consistently across classifiers than random edits, but random edits find closer adversarial trees for neural network models, so attack success and adversarial plausibility are not the same.
  • Because several SVM variants can be attacked while their classification accuracy is high, the paper's results imply that high test accuracy does not indicate robustness to edit attacks.
  • The paper's conclusion that defenses for tree classifiers are needed follows directly from the observed success rates, especially for recursive and tree echo state networks.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The binary-search run relies on an unstated monotonicity assumption: labels along the edit path should switch only once. If this fails for real classifiers, the returned prefix can be longer than the shortest label-flipping edit and the distance guarantee would not hold; instrumenting full label trajectories would test this.
  • Because the tree edit distance generalizes to sequences, the same backtracing-plus-binary-search scheme should transfer to sequence classifiers trained with edit-distance alignments, an extension the paper does not explore.
  • The distance ratios suggest that using several reference trees per target label, or constraining edits to semantically meaningful operations, could produce adversarial trees that are closer to the original than either baseline achieves.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. This paper introduces two black-box adversarial attacks for tree-structured data. The random baseline applies random tree edits until the classifier label changes, then binary-searches for a short label-changing prefix. The backtracing attack computes an edit script from the input tree x to a reference tree y carrying the target label ℓ, then binary-searches for a prefix of this script that is classified as ℓ, using only O(log(|x|+|y|)) classifier queries. The authors claim that if the returned prefix is shorter than half the edit script, the resulting z is closer to x than to any tree with label ℓ, and hence is a successful adversarial example. They evaluate the attacks on seven classifiers (five SVMs and two recursive network types) and four tree datasets, reporting success rates and distance ratios, and conclude that backtracing attacks are more reliable than random attacks.

Significance. If the central claims hold, this is the first black-box adversarial attack for tree data and would be relevant to security-sensitive applications such as program analysis and biomedical informatics. The method is simple, query-efficient conditional on having a labeled reference tree, and the paper provides implementations and experiments across several established classifiers. The validation is empirical rather than theoretical: the experiments cover real datasets, and the code is available, with the attack algorithm itself having no fitted parameters. However, the theoretical guarantee claimed in Section 3 depends on a monotonicity assumption that is not stated or proven, and the relationship between the reported success rates and distance ratios is unclear. Once these issues are addressed, the contribution would be a solid empirical demonstration rather than a guaranteed attack framework.

major comments (3)
  1. [Section 3 (Algorithm 1)] The binary-search procedure in Algorithm 1 identifies the shortest prefix with label ℓ only if the predicate f((δ1,...,δj)(x)) == ℓ is monotone in j (false for all early prefixes, true for all later prefixes). The paper does not state or justify this assumption. For a non-monotone sequence, the search can return a late prefix even when an early ℓ-labeled prefix exists: for example, if the target label appears at prefix 2, disappears at prefix 3, and reappears at prefix 5, the algorithm with lo=1, hi=5 first tests j=3, sees false, sets lo=4, tests j=4, sees false, sets lo=5, and returns prefix 5. The proof in the following paragraph ('because y is the closest tree with label ℓ ... guaranteed to yield a successful adversarial example if our prefix is shorter than half of δ') is therefore not established; the returned prefix is not shown to be the shortest or to lie before the halfway point. Tree-kernel SVMs and recursive networks can have non-convex decision regions in tree-edit space, so this is a genuine correctness risk, not a technicality.
  2. [Section 4 (Table 1)] The paper's success definition (Figure 2) requires d(x,z) < d(z,y), i.e., a distance ratio below 1. Yet Table 1 reports positive backtracing success rates with average distance ratios above 1 in many rows, for example MiniPalindrome linear (success 0.52, ratio 2.68), Sorting ST (success 0.61, ratio 3.01), and Leukemia ST (success 0.21, ratio 2.64). If the distance ratio is averaged only over successful attacks, these entries contradict the success definition; if it also includes unsuccessful label-changing attacks, the text should say so explicitly and should report success-conditional ratios. As written, the reader cannot determine how often the produced adversarial examples actually satisfy the stated closeness condition.
  3. [Section 3 / Abstract] The attack takes the reference tree y as an input, but the paper does not explain how a black-box attacker obtains the closest tree with the target label. The abstract's claim that the method 'solely relies on the tree edit distance and a logarithmic number of black-box queries' excludes the cost of selecting y. If y is found by scanning a labeled training set, this is a necessary threat-model assumption that should be stated and its query or data cost accounted for; otherwise the O(log) query bound does not describe the full attack procedure.
minor comments (4)
  1. [Section 3 / Section 4] The caption of Table 1 defines the distance ratio using 'the closest point y to z with the same label', while Section 3 defines the success condition using 'any point y ... with a different label than x'. These definitions should be reconciled in one place so the reader can see that y denotes a point with the target label.
  2. [Section 3 / Section 4] There are several typos: 'This reduced the number of queries' should be 'This reduces...' in Section 3; 'distance rations' and 'in a a one-sided Wilcoxon sign-rank test' appear in Section 4; and 'our our label' appears in Section 3.
  3. [Section 4] The paper does not report how often the backtracing attack's returned prefix was shorter than half the edit script, which is the condition under which the theoretical closeness argument applies. Reporting this fraction would help the reader interpret the success rates.
  4. [Section 4] The statistical comparison aggregates all crossvalidation folds across data sets into a single Wilcoxon test; because folds from the same data set share training data, the independence assumption is violated. A per-data-set analysis or a mixed-effects model would be more appropriate.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: attack is a black-box search with no fitted parameters; self-cited backtracing is an independent algorithmic tool.

full rationale

The derivation chain for the backtracing attack is self-contained with respect to the attack's own claims. No parameter is fitted to the experimental outcome; the success criterion and distance ratio are defined in terms of the original point x, the adversarial output z, and the nearest same-label point y in the data, not in terms of any quantity optimized by the algorithm. The only load-bearing external dependency is the backtracing procedure for computing a shortest edit script, cited from Paaßen (2018). That citation is independent support: it is a parameter-free, code-reproduced algorithm for the tree edit distance backtracing, with stated assumptions (classic tree edit distance) that do not include the present paper's target result (adversarial misclassification). The attack's guarantee argument does rely on an unstated monotonicity assumption in the binary search (the predicted label along the edit script must switch at most once), but this is a correctness gap in the proof, not a circular reduction of the conclusion to an input. Likewise, the random baseline has the same monotonicity issue. The experiments are external evaluations against seven classifiers on four datasets; the attack's success rates and distance ratios are measured, not derived from the method's definitions. No equation in the paper is used as both input and output, and no fitted value is relabeled as a prediction. Hence there is no significant circularity.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The attack algorithm itself has no fitted parameters; the free parameters listed belong to the experimental classifier setup. The main burden is the unstated monotonicity assumption for binary search and the existence and selection of a reference tree with the target label.

free parameters (5)
  • RBF kernel bandwidth sigma = nested CV over {0.5, 1, 2} times average edit distance
    Used to train the RBF-SVM classifier in experiments; an experimental hyperparameter, not part of the attack algorithm.
  • SVM regularization C = nested CV over {0.1, 1, 10, 100}
    Used to train the SVM classifiers in experiments; an experimental hyperparameter, not part of the attack algorithm.
  • Tree kernel decay lambda = nested CV over {0.001, 0.01, 0.1}
    Used for the ST, SST, and PT tree kernels in experiments; an experimental hyperparameter, not part of the attack algorithm.
  • Recursive network embedding dimension n = 10 for Rec; {10, 50, 100} for TES
    Hyperparameter for the recursive and tree echo state networks in experiments; an experimental choice, not part of the attack algorithm.
  • Random attack abort threshold = 100 tree edits
    Hand-chosen limit for the random baseline; it affects reported random attack success rates and produces n.a. entries in Table 1.
assumptions (6)
  • standard math Tree edit distance is computable in O(|x|^2 |y|^2) via dynamic programming (Zhang and Shasha 1989).
    Invoked as the distance and change model in Section 3.
  • standard math The backtracing procedure yields a co-optimal edit script (Paaßen 2018, Algorithm 6, Theorem 16).
    Used to construct the edit path from x to y in Algorithm 1.
  • standard math Tree edit distance satisfies the triangle inequality, so prefix length equals distance along a co-optimal script.
    Used for the closeness guarantee after Algorithm 1.
  • domain assumption For every test point x there is a reference tree y in the data with the desired classifier label.
    Needed for the targeted attack; the paper does not discuss what happens if no such y exists or if f(y) differs from the ground-truth label.
  • domain assumption Classifier labels along the edit path from x to y are monotone with respect to the target label.
    Algorithm 1's binary search finds the shortest prefix only under monotonicity; this assumption is not stated in the paper.
  • domain assumption Small tree-edit distance preserves semantic meaning and plausibility.
    Needed for adversarial examples to be meaningful; no domain validation is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adversarial Edit Attacks for Tree Data." pith.science (2026). https://pith.science/paper/FZE7HAQS

@misc{pith2026190809364,
  author       = {Pith},
  title        = {Pith review of: Adversarial Edit Attacks for Tree Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FZE7HAQS}},
  note         = {Machine review of arXiv:1908.09364}
}
read the original abstract

Many machine learning models can be attacked with adversarial examples, i.e. inputs close to correctly classified examples that are classified incorrectly. However, most research on adversarial attacks to date is limited to vectorial data, in particular image data. In this contribution, we extend the field by introducing adversarial edit attacks for tree-structured data with potential applications in medicine and automated program analysis. Our approach solely relies on the tree edit distance and a logarithmic number of black-box queries to the attacked classifier without any need for gradient information. We evaluate our approach on two programming and two biomedical data sets and show that many established tree classifiers, like tree-kernel-SVMs and recursive neural networks, can be attacked effectively.

Figures

Figures reproduced from arXiv: 1908.09364 by the authors.

Figure 1
Figure 1. An illustration of the effect of the tree edit script [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Two adversarial attack attempts, one random ( [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 6 canonical work pages

  1. [6]

    URL https://arxiv.org/abs/1801.01944

    doi:10.1109/SPW.2018.00009. URL https://arxiv.org/abs/1801.01944. Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, an d Le Song. Adversarial attack on graph structured data. In Jennifer Dy and Andreas K rause, editors, Proceedings of the 35th International Conference on Machine Learning (I CML

    arXiv 2018

  2. [7]

    Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song

    URL https://www.aclweb.org/anthology/P18-2006. Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-world attacks on deep learning visual classification. In Michael Brown, Bryan Morse, Shmuel P eleg, David Forsyth, Ivan Laptev, Deva Ramanan, and Aude Oliva, editors...

    work page 2006

  3. [8]

    Claudio Gallicchio and Alessio Micheli

    URL https://arxiv.org/abs/1707.08945. Claudio Gallicchio and Alessio Micheli. Tree echo state net works. Neurocomputing, 101:319 – 337,

    arXiv

  4. [11]

    Diederik P

    URL http://arxiv.org/abs/1412.6572. Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCunn, editors, Proceedings of the 3rd International Conference on Learning Representations (ICLR

    arXiv

  5. [12]

    Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dim itris Tsipras, and Adrian Vladu

    URL http://arxiv.org/abs/1412.6980. Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dim itris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversari al attacks. In Yoshua Bengio, Yann LeCunn, and Tara Sainath, editors, Proceedings of the 6th International Conference on Learning Representations (IC LR

    arXiv

  6. [14]

    Benjamin Paaßen

    URL http://arxiv.org/abs/1805.06869. Benjamin Paaßen. Adversarial edit attacks for tree data. In H ujun Yin, David Camacho, and Peter Tino, editors, Proceedings of the 20th International Conference on Intell igent Data Engineering and Automated Learning (IDEAL

    arXiv

  7. [16]

    Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Good- fellow, and Rob Fergus

    URL http://arxiv.org/abs/1710.08864. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Good- fellow, and Rob Fergus. Intriguing properties of neural net works. In Yoshua Bengio and Yann LeCunn, editors, Proceedings of the 2nd International Conference on Learnin g Rep- resentations (ICLR

    arXiv

  8. [19]

    URL https://arxiv.org/abs/1805.07984

    doi:10.1145/3219819.3220078. URL https://arxiv.org/abs/1805.07984

    arXiv

Show all 17 references
  1. [1989]

    Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann

    doi:10.1137/0218082. Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adv ersarial attacks on neu- ral networks for graph data. In Proceedings of the 24th ACM International Confer- ence on Knowledge Discovery & Data Mining (SIGKDD

    doi

  2. [2005]

    Nicholas Carlini and David Wagner

    doi:10.1016/j.tcs.2004.12.030. Nicholas Carlini and David Wagner. Towards evaluating the r obustness of neural networks. In Proceedings of the 2017 IEEE Symposium on Security and Priva cy (SP

    2004 doi

  3. [2011]

    Naveed Akhtar and Ajmal Mian

    doi:10.1007/978-3-642-21735-7_18 . Naveed Akhtar and Ajmal Mian. Threat of adversarial attacks on deep learning in computer vision: A survey. IEEE Access, 6:14410–14430,

    doi

  4. [2013]

    Andrej Gisbrecht and Frank-Michael Schleif

    doi:10.1016/j.neucom.2012.08.017. Andrej Gisbrecht and Frank-Michael Schleif. Metric and non-metric proximity transformations at linear costs. Neurocomputing, 167:643–657,

    2012 doi

  5. [2014]

    Kaizhong Zhang and Dennis Shasha

    URL http://arxiv.org/abs/1312.6199. Kaizhong Zhang and Dennis Shasha. Simple fast algorithms fo r the editing distance be- tween trees and related problems. SIAM Journal on Computing , 18(6):1245–1262,

    arXiv

  6. [2015]

    URL https://arxiv.org/abs/1411.1646

    doi:10.1016/j.neucom.2015.04.017. URL https://arxiv.org/abs/1411.1646. Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Ex plaining and harnessing ad- versarial examples. In Yoshua Bengio and Yann LeCunn, editor s, Proceedings of the 3rd International Conference on Lear...

    2015 arXiv

  7. [2017]

    3All implementations and experiments are available at https://gitlab.ub.uni-bielefeld.de/bpaassen/adversarial-edit-attacks Preprint of Paaßen

    doi:10.1109/SP.2017.49. 3All implementations and experiments are available at https://gitlab.ub.uni-bielefeld.de/bpaassen/adversarial-edit-attacks Preprint of Paaßen

    2017 doi

  8. [2018]

    Philip Bille

    doi:10.1109/ACCESS.2018.2807385 . Philip Bille. A survey on tree edit distance and related probl ems. Theoretical Computer Science, 337(1):217 – 239,

    2018

  9. [2019]

    8 Nicholas Carlini and David Wagner

    provided by the authors. 8 Nicholas Carlini and David Wagner. Audio adversarial examp les: Targeted attacks on speech-to-text. In Gabriela Ciocarlie, editor, Proceedings of the 2018 IEEE Security and Privacy Workshops (SPW

    2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.