{"id":"850fa731-0075-45f3-bdca-3792ebc490ec","arxiv_id":"1908.09364","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"A black-box adversarial attack for tree data using tree edit distance and binary search along the shortest edit path to a differently labeled reference tree.","lead":"This paper introduces a black-box attack that changes tree-structured inputs, such as program syntax trees or molecular structures, by applying small edit operations until a classifier changes its answer. The method needs only a logarithmic number of queries to the classifier, and it is tested against seven tree classifiers on four datasets.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Backtracing attack's closeness guarantee assumes unstated monotonicity of classifier labels along the edit script; binary search may return a prefix longer than the shortest, and the 'shorter than half' condition is never proven.","rationale":"The central claim requires the backtracing attack to produce an adversarial example that is close to x. The paper's proof of closeness has two unstated premises: the binary search in Algorithm 1 must return the shortest prefix whose label is the target ℓ, and that shortest prefix must occur before the halfway point of the edit script from x to y. The first premise needs the label sequence along the script to be monotone in the target label; the second premise is simply asserted nowhere. Both can fail for realistic classifiers with non-convex decision boundaries, so the theoretical guarantee is not established. The experiments may still show good empirical success, but the reported distance ratios and success rates are not sufficient to verify the guarantee because the code was not shown to enforce the exact definition used in Figure 2. The Reader's weakest-assumption identification of the monotonicity gap is correct, and the recommended conditionality is appropriate: the paper's core idea is plausible and supported by code, but the closeness guarantee needs either a proof of the missing conditions or an empirical check that the binary-search output is in fact the shortest label-changing prefix before the halfway point.","tokens_in":9130,"tokens_out":15991,"duration_ms":170545,"concrete_test":"In the released code, for every backtracing attack in Table 1, linearly scan the edit script: apply δ1...δj for j=1..n, query f, and record the first j* with f(prefix_j*(x)) == ℓ. Compare j* to the binary-search output. Report (1) fraction of attacks where binary search output differs from j*, (2) fraction where binary-search output length exceeds d(x,y)/2, and (3) whether the code's 'success' flag actually enforces d(x,z) < d(z,y). If any of these hold in a non-negligible fraction, the guarantee in §3 is not what the implementation delivers, and Table 1's success rates need re-evaluation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1 binary-searches for the first prefix of the backtraced edit script whose label is the target ℓ. This is valid only if the predicate f(prefix_j(x)) == ℓ is monotone: false for all early prefixes and true for all later prefixes. The paper never states or justifies this. In Section 3, the claim that the attack 'is guaranteed to yield a successful adversarial example if our prefix is shorter than half' also presupposes that the binary search actually returns the shortest ℓ-labeled prefix, and that this shortest prefix lies before the halfway point of the script. Neither follows from y being the closest tree with label ℓ. A recursive neural network or tree-kernel SVM can have non-convex decision regions in tree-edit space, so the target label can appear, disappear, and reappear along a shortest edit path. If the target label first appears only after the halfway point, the returned z satisfies d(x,z) > d(x,y)/2, and the paper's own success criterion (z closer to x than to any same-label point) fails. The empirical success rates therefore do not currently have the supporting guarantee the paper claims.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9369,"tokens_out":10803,"duration_ms":104480,"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":[{"comment":"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.","section":"Section 3 (Algorithm 1)"},{"comment":"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.","section":"Section 4 (Table 1)"},{"comment":"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.","section":"Section 3 / Abstract"}],"minor_comments":[{"comment":"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.","section":"Section 3 / Section 4"},{"comment":"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.","section":"Section 3 / Section 4"},{"comment":"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.","section":"Section 4"},{"comment":"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.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"This is a competent empirical contribution to a timely topic, with code and data released. The main concern is the unproven monotonicity assumption behind the binary-search guarantee; the authors should either prove it for a restricted classifier class or reframe the paper as an empirical attack study and remove the guarantee language. The distance-ratio reporting also needs a clear definition of the population over which it is averaged. If the authors can make these changes, the paper could be acceptable; the current version's central guarantee is not established. The self-citation to the author's backtracing tutorial is appropriate and does not raise circularity concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the useful part: this is the first black-box adversarial attack for tree data, and the core idea is genuinely simple—pick a reference tree with the target label, backtrace a shortest edit script from x to y, then binary-search the shortest prefix that changes the label. No gradients, O(log(|x|+|y|)) queries, and the code is public. The evaluation is broad: seven classifiers, four datasets from programming and biomedicine. The self-citation to the backtracing tutorial is a separate, documented tool, so I don't see that as circular.\n\nThe soft spots are real. The success criterion in Figure 2 is that the adversarial example is closer to the original x than to any other point with the target label. But Table 1 lists positive backtracing success rates together with average distance ratios above 1—for example, MiniPalindrome linear has success 0.52 and ratio 2.68. If the ratio is computed only on successful attacks, it should be below 1. As printed, the table is internally inconsistent; either the ratio includes failures or the success definition isn't the one being measured.\n\nSecond, the theoretical guarantee. The Section 3 proof assumes the binary search returns the shortest prefix classified as the target label ℓ. That requires monotonicity: once a prefix maps to ℓ, all longer prefixes do too. The paper never states this, and it's unlikely to hold for tree-kernel SVMs or recursive nets, which can have non-convex decision regions in edit space. If the label flickers, binary search can return a longer prefix than the shortest, and the 'shorter than half' inequality no longer follows. The stress-test note is right on this point.\n\nThat said, the label-changing part of the attack is plausible and probably works—the monotonicity problem is about the closeness guarantee, not about whether the classifier is fooled. If the author revised the paper to separate the success criterion from the distance ratio and to present the closeness claim as a heuristic rather than a theorem, it would be much stronger.\n\nThis paper is for people working on adversarial robustness for structured data, especially syntax trees and biomedical trees. It is not a field-reshaping result, but it opens a useful line of attack. It deserves a serious referee, with the above issues addressed before acceptance.","headline":"A useful first black-box attack for tree classifiers, but the closeness guarantee is unproven and the evaluation table contradicts its own success definition.","tokens_in":9860,"tokens_out":5360,"would_cite":true,"duration_ms":45617,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["adversarial examples","tree edit distance","black-box attack","tree classification","backtracing","tree kernels","recursive neural networks","structured data"],"falsifier":"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.","tokens_in":8935,"feed_emoji":"🌳","tokens_out":5474,"duration_ms":51437,"temperature":0.7,"pith_summary":"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.","feed_headline":"Tree classifiers fall to log-query edit attacks","feed_subtitle":"No gradients or model internals needed: tree edit distance plus binary search flips labels on SVMs and neural nets.","key_machinery":"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.","core_discovery":"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)