{"id":"c60b99d7-50f9-452c-8f37-77eb61bb6152","arxiv_id":"1908.03929","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An extension of the single-protection secret securing problem to m protections, solved by iterative supervisor synthesis and relabeling.","lead":"Discrete-event systems researchers propose a method to protect secret states by requiring every attacker path to pass through at least two protected events, choosing the cheapest cost level. The paper gives an algorithm based on supervisory control theory and demonstrates it on a network login example.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Relabeling removes event symbols globally: Algorithm 1 can fail on solvable instances where a protectable event appears on both a disabled and a non-disabled transition.","rationale":"The reader's conditional verdict correctly targeted the relabeling step, but I found a concrete failure mode rather than a mere proof gap. The paper's own definitions allow the same event symbol to occur on multiple transitions, and the relabeling in (18)-(23) is not transition-indexed: (19) removes an event symbol from the controllable alphabet if it is disabled anywhere, even though (23) leaves other transitions with that symbol in δ1. The minimal counterexample has a single protectable event σ appearing twice on the only secret-reaching path; Problem 2 is solvable with two protections at cost level 0, yet Algorithm 1 either constructs an ill-defined G1 or returns empty. This directly contradicts the equivalence asserted in Proposition 13 and the guarantee in Theorem 14. The underlying supervisory-control idea is plausible and the worked example is internally consistent because no event symbol is reused in a non-disabled transition there, but the theorem as stated is false under standard DES semantics. A transition-indexed relabeling would likely repair the construction, but that repair requires new definitions and a reworked proof. I therefore recommend REJECT rather than CONDITIONAL, since a concrete solvable instance defeats the current algorithm.","tokens_in":11960,"tokens_out":15792,"duration_ms":187811,"concrete_test":"Execute Algorithm 1 on the 3-state automaton above with Σ0={σ}, Σ_up=∅, q2 secret. Literal (18)-(23) should be checked: either G1 is ill-formed because q0--σ→q1 survives while σ∉Σ1, or RCMC1 returns empty. Then rerun the same instance with transition-indexed relabeling (relabel only (q1,σ,q2) to σ', keep σ controllable at q0); if the patched algorithm succeeds with k=0, this confirms the global symbol removal in (19) is the failing assumption. A broader check would randomly generate automata with repeated event symbols and compare Algorithm 1 against a brute-force search over protection policies.","verdict_should_be":"REJECT","load_bearing_attack":"Equations (18)-(23) relabel transitions, but (19) removes an event symbol from Σ_c if it occurs in any disabled transition. This conflates transition-level protection with event-level protection. If σ∈D0(q) for some q and σ also labels a transition not in δD0, that non-disabled transition remains in δ1 (23) while σ∉Σ1; G1 is not an automaton over its declared alphabet. If one repairs this by making σ uncontrollable, the non-disabled σ transition can no longer be protected by S1. This is not just a notation gap; it invalidates Proposition 13 and Theorem 14. Counterexample: Q={q0,q1,q2}, q0 initial, Qs={q2}, Σ0={σ}, transitions q0--σ→q1 and q1--σ→q2, no other events. Every string to q2 is σσ, so Problem 2 is solvable with k=0 via P(q0)=P(q1)={σ}. RCMC1 for k=0 gives D0(q1)={σ} and leaves q0--σ→q1 enabled. Then (19) deletes σ from Σ_c globally, while (23) keeps q0--σ→q1. Under the literal definition G1 has a transition labeled by an event not in Σ1; under the natural patch making σ uncontrollable, the path q0σq1σ'q2 has no controllable event and RCMC1 returns empty. Hence Algorithm 1 returns no policy although a solution exists; the proof of Proposition 13 merely asserts the relabeling preserves the required property without treating repeated event symbols.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper formalizes a security problem for discrete-event systems in which every string reaching a secret state must contain at least m protected events and the highest cost level of those protections is minimal. For m=2 it converts the problem into a supervisory control problem, gives a solvability condition (Theorem 4), and proposes Algorithm 1, which computes two supervisors S0 and S1 by iteratively applying a one-protection routine (RCMC1), relabeling the transitions disabled by the first supervisor as uncontrollable, and merging the two control policies. Theorem 14 claims that the merged policy is a solution of the minimum-cost two-protection problem, and Section III-C together with Algorithm 2 extends the idea to m>=3. A worked network example is provided for m=2 and m=3.","tokens_in":12274,"tokens_out":10654,"duration_ms":108353,"significance":"The problem formulation is natural and the conversion between protection and control is a useful way to reuse supervisory control theory. The paper also gives a clear worked example and builds on the authors' prior m=1 case. However, the central correctness claim is not sound as written: the relabeling step operates on event symbols whereas disabling decisions are state-dependent, and this invalidates Proposition 13 and Theorem 14. Because the flaw is concentrated in the relabeling equations and is repairable in principle by a transition-specific relabeling with fresh event labels, the contribution has some potential, but the current manuscript requires substantive revision.","major_comments":[{"comment":"Equations (19)–(23) relabel at the event level, not the transition level. Equation (19) removes an event symbol σ from Σ_c if σ∈D0(q) for some q, while Eq. (23) leaves any non-disabled σ-transition in δ1; Eq. (18) then declares G1 an automaton over Σ1 even though that remaining transition is labeled by a symbol outside Σ1. This is not a notational slip: consider G with Q={q0,q1,q2}, q0 initial, Qs={q2}, Σ0={σ}, and transitions q0--σ→q1 and q1--σ→q2. The only string reaching q2 is σσ, so Problem 2 is solvable with k=0 by P(q0)=P(q1)={σ}. RCMC1 for k=0 returns a nonempty S0 with D0(q1)={σ}. Then Eq. (19) deletes σ from Σ_c while (23) keeps q0--σ→q1 in δ1; under the literal reading G1 is not an automaton over Σ1, and under the natural patch that makes σ uncontrollable, the string q0σq1σ'q2 contains no controllable event, so RCMC1 returns an empty S1. Thus Algorithm 1 fails on a solvable instance, and Proposition 13 and Theorem 14 are false as stated. The proof of Proposition 13 asserts, without argument, that the relabeling preserves the required number of protections; the counterexample shows it does not.","section":"§III-B, Eqs. (18)–(23), Proposition 13"},{"comment":"The minimality claim is asserted, not proved. The text says that k0≤k1 because k0 is the least index for the first supervisor and then sets the merged index to k=k1. Even if k0≤k1 were true, one would still need to prove that merging D0 and D1 cannot be realized with a lower-cost event set; the statement 'k1 are minimum' is not an argument. The least index of the relabeled problem in G1 must be related rigorously to the least index in G. Since the main contribution of the paper is the minimum-cost guarantee, this missing proof is load-bearing.","section":"§III-B, paragraph after Eq. (26)"},{"comment":"The extension to m≥3 is presented without a correctness theorem or proof. Algorithm 2 iterates the relabeling procedure in Eqs. (29)–(34), but no statement analogous to Proposition 13 or Theorem 14 is proved for m≥3. The iterative relabeling inherits the event-level/transition-level confusion of Eqs. (18)–(23), so the conclusion that m-SSMCP is solved by Algorithm 2 is unsupported. A proof is needed after the relabeling is repaired.","section":"§III-C, Algorithm 2"}],"minor_comments":[{"comment":"Equation (16) defines δK as δ \\ {(q,σ,q') | q,q'∈Qs, σ∈Σ}, which only removes transitions with both endpoints in Qs; Example 10 and Fig. 3 remove transitions entering Qs from outside, such as (q2,σ6,q5). The intended definition should remove all transitions with target (or source) in Qs, and the formula should match the text.","section":"§III-A, Eq. (16)"},{"comment":"Equation (20) has a notation problem: Σ_uc1 should contain the new relabeled symbols, but it is written as {σ∈Σ | (q,σ',q')∈δ'_D0}, which does not introduce σ'. The definition should either use σ' in the set or define the relabeled event symbols explicitly.","section":"§III-B, Eq. (20)"},{"comment":"There are several typos: the title reads 'Minimum Cost s'; Eq. (24) lists D0(q4) twice; and 'depiceted' appears in Section IV-B.","section":"Throughout"},{"comment":"The equivalence (10)–(11) is attributed to the prior work [10], but the proof chain (12)–(15) would be clearer if the controllability characterization used for the one-protection case were stated explicitly in this paper, since Proposition 9 is used as a step in the proof of Proposition 13.","section":"§III-B, Proposition 9"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper extends the authors' prior single-protection result to multiple protections by iterating a relabeling trick. The high-level idea is sensible, and the worked example is fine. But the key step (18)-(23) has a real bug: it removes an event symbol from the controllable alphabet globally if any disabled transition uses that symbol, even when other transitions with the same symbol remain enabled. This makes G1 ill-defined, or under the natural patch makes the second supervisor fail on solvable instances.\n\nConcrete counterexample: states q0, q1, q2; q0 initial; q2 secret; Sigma0 = {sigma}; transitions q0--sigma->q1 and q1--sigma->q2. Protecting sigma at both states gives two protections, so Problem 2 is solvable. Algorithm 1, however, returns empty. The first supervisor disables only the second sigma. Relabeling then either deletes sigma from Sigma_c globally (leaving the first sigma transition in delta1 but not in the alphabet) or, if you patch by making sigma uncontrollable, the first sigma can no longer be controlled by the second supervisor. In both cases the algorithm fails on a solvable instance. This invalidates the proof of Proposition 13 and therefore Theorem 14.\n\nWhat is genuinely new and good: the problem formulation is clean, and translating protection policies into supervisory control is natural. Theorem 4 is essentially a restatement of \"least index,\" but it is correct. The example is detailed and shows the intended behavior. The m>=3 extension via Algorithm 2 is a straightforward generalization, though it is asserted without proof.\n\nThe fix is probably simple: relabel the specific transition (q, sigma, q') to (q, sigma', q'), rather than removing sigma from the alphabet whenever it appears in any disabled transition. That would preserve the counting argument. Minor issues: minimality of k1 is asserted more than proved, and the m>=3 extension should be flagged as a claim rather than a theorem.\n\nThis is an incremental contribution to DES security, not a breakthrough. If the relabeling is corrected and the main theorem re-proved, it would be a useful result for people working on supervisory control and opacity. I would send it to peer review, because the flaw is localized and the core idea is sound, but the current version should not be accepted as is.","headline":"The multi-protection synthesis idea is sound, but the global relabeling in (19) introduces a real bug that invalidates Proposition 13 and Theorem 14; a transition-local fix should repair it.","tokens_in":108,"tokens_out":3549,"would_cite":false,"duration_ms":101506,"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":"The paper proves that two cheap protections on every secret path can be synthesized by merging two supervisors.","keywords":["secret protection","discrete-event systems","supervisory control theory","minimum protection cost","multiple protections","security policy","controllable reachability","relabeling"],"falsifier":"Enumerate all finite plants with three cost levels and up to five states whose secret states are 2-securely reachable at some level. Run Algorithm 1 and, for every string reaching a secret, count the protected events and their highest cost level. Finding any string with fewer than two protected events, or a protected set whose highest level exceeds the smallest solvable $k$, would refute Theorem 14; finding any solvable instance where Algorithm 1 returns empty would refute Proposition 13.","tokens_in":11760,"feed_emoji":"🔒","tokens_out":5935,"duration_ms":57216,"temperature":0.7,"pith_summary":"This paper treats secret protection as a discrete-event control problem. It claims that to force every string reaching a secret state to contain at least two protected events while minimizing the highest protection cost, it suffices to compute two supervisory controllers: one that enforces a single protection at the cheapest level, and a second computed on a relabeled plant where the first controller's protected transitions are treated as uncontrollable. Merging the two controllers' decisions yields a protection policy that is guaranteed to give two protections at the least cost level. The same scheme is extended to any number of protections by iterating the relabeling step. If correct, the result turns a multi-protection security requirement into repeated use of standard one-protection supervisory control synthesis.","feed_headline":"Merging two supervisors forces two protections before any secret","feed_subtitle":"An algorithm finds the cheapest protection level blocking every path to a secret, and scales to any number of barriers.","key_machinery":"The load-bearing object is the relabeling step, equations (18)--(23). Transitions that the first supervisor $D_0$ protects (disables) are renamed to primed versions and moved into the uncontrollable event set. Rebuilding the plant as $G_1$ with those renamed events treated as uncontrollable makes the one-protection requirement in $G_1$ correspond to having already consumed one protection; the second supervisor $S_1$ then enforces one more controllable event, so the merged policy enforces two distinct protections. The same step is iterated for more protections. Cost minimization is carried by the RCMC1 subroutine, which tries cost levels $k = 0, 1, \\dots$ in increasing order and returns the first level at which a nonempty supremal controllable sublanguage exists.","core_discovery":"The central claim is Theorem 14: whenever the two-protection, minimum-cost problem is solvable, the protection policy $P(q) := P_0(q) \\cup P_1(q)$ computed by Algorithm 1 is a solution. Here $P_0$ is derived from a supervisor that guarantees at least one protected event on every string reaching a secret, and $P_1$ comes from a second supervisor run on the relabeled plant $G_1$ in which the transitions protected by $P_0$ are renamed as uncontrollable events. Because those renamed transitions can no longer serve as controllable protections, a controller guaranteeing one controllable event in $G_1$ forces a second distinct protection in the original plant. The paper also gives a necessary and sufficient solvability condition: the problem is solvable exactly when the secrets are 2-securely reachable at some cost level $k$ and not 2-securely reachable at any lower level. Minimality of the cost level follows from the subroutine trying cost levels in increasing order and returning the first level at which a supervisor exists.","pith_inferences":["The relabeling idea is portable: any property enforced by a single controller could be iterated by renaming protected transitions as uncontrollable, potentially giving multi-layered versions for opacity-style or diagnosability-style problems, not just reachability.","The cost model assumes levels are non-comparable and ordered by index. If costs instead add or are only partially ordered, the minimality argument would need a different objective, but the two-supervisor construction would still produce a feasible protection policy.","The authors' stated future direction of unequal secret importance and cost balance can be tested directly: assign each secret a weight, require multiple protections only on high-weight secrets, and check whether the same relabel-and-merge scheme computes a policy with per-secret minimum levels."],"forward_implications":["Any system for which the one-protection problem can be solved can be upgraded to two protections by running the same one-protection solver twice, once on the original plant and once on the relabeled plant.","The cost level achieved by the merged policy is exactly the first level at which the second supervisor exists, so the merged policy never exceeds the cheapest level consistent with two barriers.","The $m$-protection version is solved by iterating the relabel-and-solve loop $m$ times, and the required cost level is nondecreasing as the number of protections grows.","The solvability condition is cleanly separable: either two protections are possible using only the cheapest events, or they become possible at the first level $k$ where 2-secure reachability holds and fails at level $k-1$.","Because the output is a state-based protection policy, an administrator can implement protections offline as a lookup table, with no online monitoring of intruder behavior."],"supporting_citations":[{"why":"Supplies the finite-state automaton model and standard language/transition notation for discrete-event systems.","marker":"[2]"},{"why":"Provides the foundational supervisory control synthesis problem that the security problem is converted into.","marker":"[3]"},{"why":"Supplies the supremal controllable sublanguage construction and controllability conditions used by the RCMC1 subroutine.","marker":"[4]"},{"why":"Provides the previously solved one-protection minimum-cost problem that serves as the subroutine and as the base case for this extension.","marker":"[10]"}],"fun_headline_variants":["Two supervisors merged guarantee two secret barriers at least cost","Cheapest dual protection: merge two supervisors for secrecy","Merged supervisors enforce double security with minimal cost","Double protection at minimum cost via supervisor merge","Two-supervisor trick yields cheapest double barrier to secrets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument relies on the relabeling step faithfully turning the first protection into an uncontrollable event so that one controllable event in the relabeled plant means exactly one additional protection in the original system; if renaming can alias, skip, or duplicate protections, the merged policy could allow a secret path with fewer than two protected events or miss the cheapest level.","fun_headline_variants_meta":{"raw":{"variants":["Two supervisors merged guarantee two secret barriers at least cost","Cheapest dual protection: merge two supervisors for secrecy","Merged supervisors enforce double security with minimal cost","Double protection at minimum cost via supervisor merge","Two-supervisor trick yields cheapest double barrier to secrets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000155,"raw_usage":{"total_tokens":1195,"prompt_tokens":906,"completion_tokens":289,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":214}},"tokens_in":522,"tokens_out":289,"duration_ms":3880,"temperature":1.0,"reasoning_tokens":214,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:00:29.248979+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all finite plants with three cost levels and up to five states whose secret states are 2-securely reachable at some level. Run Algorithm 1 and, for every string reaching a secret, count the protected events and their highest cost level. Finding any string with fewer than two protected events, or a protected set whose highest level exceeds the smallest solvable $k$, would refute Theorem 14; finding any solvable instance where Algorithm 1 returns empty would refute Proposition 13.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the foundational supervisory control synthesis problem that the security problem is converted into."},{"cited_title":"Cassandras and S","cited_arxiv_id":null,"evidence_quote":"Supplies the supremal controllable sublanguage construction and controllability conditions used by the RCMC1 subroutine."},{"cited_title":"Dubreil, P","cited_arxiv_id":null,"evidence_quote":"Provides the previously solved one-protection minimum-cost problem that serves as the subroutine and as the base case for this extension."}],"review_version":1}