- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes LoRo-Mark, an agent watermarking framework for black-box ownership verification under agent repackaging. The method separates watermarking from normal execution through a MAC-authenticated forensic branch, allowing ordinary requests to follow the original execution path. Within the forensic branch, copyright information is redundantly encoded into behavior sequences using keyed pseudorandom mappings. The paper provides theoretical guarantees under specified assumptions and evaluates utility preservation and watermark recovery under behavior substitution and sequence truncation.
Critical strengths
-
A well-motivated separation of watermarking and normal execution. The MAC-authenticated forensic branch provides a clear way to preserve ordinary agent behavior while supporting ownership verification. The accompanying theoretical analysis formalizes this property under standard cryptographic assumptions.
-
Useful evaluation of watermark robustness and redundancy. The paper compares LoRo-Mark with existing agent watermarking methods and evaluates recovery under behavior substitution and sequence truncation. The analysis of different repetition factors also illustrates the trade-off between robustness and forensic sequence length.
Critical weaknesses
-
Clarification Needed on Context Reconstruction Under Repackaging. Watermark extraction relies on reconstructing the per-step execution contexts and candidate behavior sets used during embedding. However, the threat model allows the repackaging adversary to modify displayed observations and execution traces. It is unclear how the verifier can reliably reconstruct the original contexts from potentially modified information. The robustness analysis appears to assume that this reconstruction remains valid, and further clarification would strengthen the connection between the theoretical guarantees and the proposed threat model.
-
Potential Vulnerability to Targeted Trace Manipulation. The robustness evaluation mainly considers random behavior substitution and prefix truncation. However, the repetition encoding places copies of each watermark bit at predictable positions. Under the default fixed-capacity configuration, selectively replacing three particular behavior steps with erasures could eliminate all copies of one watermark bit and cause verification to fail. This suggests a possible vulnerability to targeted modifications that is not covered by the current evaluation, although it does not contradict the guarantees established under the paper's stated assumptions.
Questions for authors
-
Context Reconstruction Under Modified Observations. Could the authors clarify how the verifier reconstructs the original execution contexts and candidate behavior sets when a repackaging adversary modifies the displayed observations? It would be helpful to evaluate whether watermark extraction remains reliable under such modifications.
-
Robustness Against Targeted Trace Manipulation. Could the authors evaluate targeted behavior erasure attacks, where an adversary deliberately modifies a small number of selected positions rather than randomly substituting behaviors? This would help clarify the robustness of the proposed repetition encoding against more deliberate trace manipulation.
9 comments
Question-2: Robustness Against Targeted Trace Manipulation. Could the authors evaluate targeted behavior erasure attacks, where an adversary deliberately modifies a small number of selected positions rather than randomly substituting behaviors? This would help clarify the robustness of the proposed repetition encoding against more deliberate trace manipulation.
Response-2: Robustness Against Targeted Trace Manipulation
Thank you for highlighting attacks that deliberately target the repetition layout. We have analyzed the effect of such erasures and distinguish their consequences from the guarantees for independent random substitution and prefix truncation.
Layout-aware targeted erasure.
Under the default configuration, the copyright payload has bits, the repetition factor is , and each step carries bits, giving steps. Copy of payload bit is embedded at step
\left\lfloor \frac{i+kn}{\beta} \right\rfloor+1, \qquad k=0,\ldots,r-1.$$ For the first payload bit, these steps are $$t_{0,0}=1, \qquad t_{0,1}=18, \qquad t_{0,2}=35.$$ Erasing these three steps removes all copies of $c_0$. Algorithm 5 then rejects because the corresponding voting group is empty. This attack therefore causes verification failure even when the remaining mappings and step positions are correctly reconstructed. It affects only $3/52\approx5.77\%$ of the trace and does not require the secret key: the keyed mapping determines which behavior represents a code chunk, while the locations of the repeated chunks follow the public encoding layout. This confirms the targeted-erasure failure case identified in the review. As the reviewer notes, it does not contradict the guarantees for independent random substitution or prefix truncation. We will distinguish these attack models explicitly in the revised manuscript. **Recovery under bounded targeted corruption.** The repetition code also provides a deterministic recovery guarantee for a bounded number of deliberately selected modifications. Let $u_i$ and $v_i$ be the numbers of substituted and recognizably erased copies of payload bit $c_i$. With the original step correspondence and keyed mappings available, majority decoding recovers the entire message whenever $$2u_i+v_i<r \qquad \text{for every } i.$$ At least $r-u_i-v_i$ copies remain correct, while at most $u_i$ can vote for the wrong value. The inequality therefore ensures a strict correct majority among the surviving votes. Because $n\geq\beta$, different copies of a given bit occupy different steps. Consequently, any $a$ substituted steps and $b$ recognizably erased steps are correctable whenever $$2a+b<r,$$ regardless of how the attacker selects those positions. For $r=3$, this guarantees recovery from any one substituted step or any two erased steps. Three appropriately selected erasures can defeat verification, as shown above. Increasing $r$ raises the absolute number of edits covered by this guarantee, but does not conceal the repetition layout. **Contiguous-block corruption.** For completeness, a single contiguous block has a different recovery condition because copies of the same bit are separated by $n$ encoded positions. For $r=2h+1$, arbitrary substitutions and recognizable erasures confined to one block of $m$ steps are correctable whenever $$m\beta\leq hn.$$ Under the default configuration, this guarantees recovery for any contiguous block of at most $17$ steps. For pure erasure, it is sufficient that at least one correct copy of every bit survives. A single contiguous erasure block is therefore correctable under the stronger condition $$m\beta\leq(r-1)n,$$ which gives up to $34$ steps in the default configuration. These statements require the original positions to remain identifiable; they concern erasures with preserved alignment, rather than deletions that destroy step correspondence. The following table summarizes the deterministic consequences of the encoding layout and decoder. | Attack under the default configuration | Budget or selected positions | Deterministic result | | :--- | :--- | :--- | | Arbitrary recognizable step erasures | Any two steps | Exact recovery | | Layout-aware targeted step erasure | Steps 1, 18, and 35 | Verification rejects | | Arbitrary behavior substitution | Any one step | Exact recovery | | One contiguous block of substitutions and/or recognizable erasures | At most 17 steps | Exact recovery | | One contiguous block of recognizable erasures only | At most 34 steps | Exact recovery | This analysis identifies the recovery boundary of the current repetition construction: it tolerates bounded targeted corruption and substantially larger contiguous blocks, while an attacker who erases every publicly located copy of a selected bit can prevent verification. We will state these distinct guarantees and failure cases explicitly in the revision.We noticed that we have not yet received your feedback and would like to ask whether any part of our explanation may have been unclear. We would be more than happy to provide further clarification if needed, and sincerely hope that we can address any remaining concerns. We would greatly appreciate it if you could take the time to review our response.
Thank you very much for your time and consideration.
Question-1: Context Reconstruction Under Modified Observations. Could the authors clarify how the verifier reconstructs the original execution contexts and candidate behavior sets when a repackaging adversary modifies the displayed observations? It would be helpful to evaluate whether watermark extraction remains reliable under such modifications.
Response-1: Context Reconstruction Under Modified Observations
Thank you for highlighting the reconstruction requirements. Algorithm 4 in Appendix A presents the standard context-dependent instantiation of LoRo-Mark, in which the per-step mapping is defined as
\operatorname{PRF} \bigl(k_{\mathrm{step}},o_t,\mathcal{B}_t\bigr).$$ This instantiation requires the verifier to reproduce the observation context and candidate set used during embedding. To remove the dependence of mapping reconstruction on potentially modified observations, **we now specify an observation-independent instantiation within the same framework**. For an authenticated forensic request $T^*$, the owner and the protected harness share a predefined forensic candidate table $\mathcal{B}^{\mathrm{F}}$. Let $\eta$ be an owner-generated forensic timestamp included in the authenticated request content and retained locally by the owner. Using the request-specific key $k_{\mathrm{step}}$, both parties derive $$s_t = \operatorname{PRF} \bigl( k_{\mathrm{step}}, \operatorname{Encode}(\eta,t) \bigr),$$ and $$\pi_t = \operatorname{Permute} \bigl( \operatorname{Canon}(\mathcal{B}^{\mathrm{F}}); s_t \bigr).$$ Here, $\operatorname{Encode}$ provides an unambiguous encoding of the timestamp and original step index, $\operatorname{Canon}$ fixes the candidate identities and their canonical ordering, and $\operatorname{Permute}$ generates a permutation deterministically from the seed $s_t$. The next copyright-code chunk determines an index $j_t$, and the harness selects $$b_t = \pi_t[j_t], \qquad b_t \in \mathcal{B}^{\mathrm{F}},$$ producing the forensic behavior sequence $$\tau = (b_1,\ldots,b_S).$$ During verification, the owner obtains the request information from its locally retained authenticated query and the candidate table from its own configuration. For each identifiable surviving behavior whose original step index $t$ is available, the verifier reconstructs the same permutation and maps the behavior back to its corresponding code chunk. Neither permutation generation nor this inverse mapping uses the displayed observation $o_t$ or a candidate set reconstructed from the frontend. **Consequently, modifying or suppressing the displayed observations does not, by itself, disrupt reconstruction of the forensic mapping in this instantiation.** The timestamp need not be secret: pseudorandomness is supplied by the secret key, while the original step index distinguishes the per-step inputs within the request. This construction changes the inputs used to generate the per-step mapping; the authenticated branch and redundant encoding procedure remain unchanged. Ordinary requests continue along the original execution path. We will include this instantiation and its reconstruction requirements explicitly in the revised manuscript.