Pith. sign in

REVIEW 3 major objections 4 minor 13 references

Secret Securing with Multiple Protections and Minimum Costs

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 The paper proves that two cheap protections on every secret path can be synthesized by merging two supervisors.

desk verdict 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. read the letter →

arxiv 1908.03929 v1 pith:EH3EWGZM submitted 2019-08-11 eess.SY cs.SY

Shoma Matsui , Kai Cai This is my paper · ORCID
classification eess.SYcs.SY
keywords secretprotectiondiscrete-eventsystemssupervisorycontroltheoryminimumcostmultipleprotectionssecuritypolicycontrollablereachabilityrelabeling
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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. 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.

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 (3)
  1. [§III-B, Eqs. (18)–(23), Proposition 13] 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.
  2. [§III-B, paragraph after Eq. (26)] 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.
  3. [§III-C, Algorithm 2] 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.
minor comments (4)
  1. [§III-A, Eq. (16)] 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.
  2. [§III-B, Eq. (20)] 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.
  3. [Throughout] There are several typos: the title reads 'Minimum Cost s'; Eq. (24) lists D0(q4) twice; and 'depiceted' appears in Section IV-B.
  4. [§III-B, Proposition 9] 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.

Circularity Check

1 steps flagged · score 2.0 of 10

Minor definitional circularity in the solvability theorem; the main algorithm is not circular.

  1. self definitional [Problem 2 (Section II) and Theorem 4 (Section III-A)]
    "Problem 2 ... Find a protection policy P : Q → Pwr(Σ p) s.t. Qs is 2-securely reachable w.r.t. Σ k p = ⋃ k i=0 Σ i and k is the least index. ... Theorem 4. Consider a plant G in (1). Problem 2 is solvable w.r.t. G and Σ k p iff either Qs is 2-securely reachable w.r.t. G and Σ 0 or [Qs is 2-securely reachable w.r.t. G and Σ k p & Qs is not 2-securely reachable w.r.t. G and Σ k−1 p ] holds."

    Definition 1's '2-securely reachable' predicate is defined purely over event occurrences in strings (condition (2)); it never references the protection policy P. Hence Problem 2's 'find a policy P' is vacuous: solvability is just 'there is a least k such that every string to Qs contains two events from Σ^k_p'. Theorem 4 restates exactly this condition as a disjunction (property at k=0, or property at k with failure at k-1). The proof unpacks the definitions and asserts that a policy P exists whenever the language condition holds. Thus the theorem is equivalent to the problem definition by construction, not an independent necessary-and-sufficient characterization.

full rationale

The paper's central contribution is Algorithm 1 and Theorem 14, which is not circular: it converts the security problem to a reachability control problem, applies the standard supremal-controllable-sublanguage construction, uses the authors' earlier m=1 solver (RCMC1, cited as [10]) as a subroutine, and merges the two disabling policies. There are no fitted parameters or data-dependent quantities being relabeled as predictions. The proof of Proposition 13 contains a genuine correctness gap (the relabeling (18)-(23) is asserted, not shown, to preserve a controllable event when two controllable events in G are both relabeled by D0), but that is a soundness issue, not a circular reduction. The only circular element is the tautological solvability condition in Theorem 4, which is a minor definitional restatement and does not affect the independent content of the algorithm.

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

The central claim rests on standard SCT machinery, a domain-specific cost ordering, the security-to-control conversion, and the correctness of prior work used as a subroutine. No free parameters or invented entities are introduced.

assumptions (5)
  • standard math Standard supervisory control results: existence and computation of the supremal controllable sublanguage, including Lemma 11.
    Used in RCMC1 to compute supervisors S0 and S1; cited from [4], considered a standard result in the field.
  • domain assumption The cost model: protecting one event in Σ_i is more expensive than protecting all events in Σ_{i-1}, so minimizing the highest index k is the objective.
    Stated in Section II. Without this assumption, the objective of minimizing the highest cost level would not be well-motivated or equivalent to the problem formulation.
  • domain assumption The equivalence between protectable/unprotectable events and controllable/uncontrollable events, and between protection policies and control policies.
    Section III-B conversion. If protection in the real system is not analogous to disabling in the control problem, the solution may not translate to a valid security policy.
  • domain assumption Correctness of the single-protection algorithm RCMC1 from the authors' prior work [10].
    RCMC1 is used as a subroutine in Algorithm 1 and Algorithm 2; the paper does not re-derive its correctness.
  • domain assumption For m ≥ 3, the same relabeling procedure remains correct when iterated.
    Section III-C asserts this without a full proof, yet Algorithm 2 relies on it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Secret Securing with Multiple Protections and Minimum Costs." pith.science (2026). https://pith.science/paper/EH3EWGZM

@misc{pith2026190803929,
  author       = {Pith},
  title        = {Pith review of: Secret Securing with Multiple Protections and Minimum Costs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EH3EWGZM}},
  note         = {Machine review of arXiv:1908.03929}
}
read the original abstract

In this paper we study a security problem of protecting secrets with multiple protections and minimum costs. The target system is modeled as a discrete-event system (DES) in which a few states are secrets, and there are multiple subsets of protectable events with different cost levels. We formulate the problem as to ensure that every string that reaches a secret state (from the initial state) contains a specified number of protectable events and the highest cost level of these events is minimum. We first provide a necessary and sufficient condition under which this security problem is solvable, and then propose an algorithm to solve the problem based on the supervisory control theory of DES. The resulting solution is a protection policy which specifies at each state which events to protect and the highest cost level of protecting these events is minimum. Finally, we demonstrate the effectiveness of our solution with a network security example.

Figures

Figures reproduced from arXiv: 1908.03929 by the authors.

Figure 1
Figure 1. Plant G Example 3. The plant G in [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Conversion overview in [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Specification GK L(G) ⊆ K where K is the prefix closure of K. The family C(K) is the set of all controllable sublanguages of K, and denoted by C(K) := { K′ ⊆ K | K′Σuc ∩ L(G) ⊆ K′ }. The supremal controllable sublanguage of K is given by sup C(K) := S { K′ | K′ ∈ C(K) }. sup C(K) w.r.t. G and Σ k c means sup C(K) = S { K′′ | K′′ ∈ C(K) } where C(K) = { K′ ⊆ K | K′(Σ \ Σ k c ) ∩ L(G) ⊆ K′ }. Lemma 11. (cf. [4]) Let G… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: The plant G with the protection policy P0 is shown in [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 5
Figure 5. Figure 5: Plant G1 derived from G in [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]
Figure 7
Figure 7. Figure 7: The plant G with the protection policy P [PITH_FULL_IMAGE:figures/full_fig_p007_7.png]
Figure 8
Figure 8. Figure 8: Plant G2 puting the specification automaton GK2 for G2 in the same way as GK1 , let K = L(GK2 ) and call function RCMC1 in line 3 of Algorithm 2. When k = 0, 1, sup C(K) = ∅. When k = 2, sup C(K) = (σ ′ 0 .σ1) ∗ [PITH_FULL_IMAGE:figures/full_fig_p007_8.png]
Figure 9
Figure 9. Figure 9: The plant G with the protection policy P [PITH_FULL_IMAGE:figures/full_fig_p008_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 12 canonical work pages

  1. [1]

    4" FUNCTION default.is.dash.repeated.names #1 FUNCTION default.name.format.string

    11em plus .33em minus .07em @technote 4000 4000 100 4000 4000 500 `\.=1000 = #1 #1 #1 0pt [0pt][0pt] #1 * \| ** #1 \@IEEEauthorblockNstyle \@IEEEauthorblockAstyle \@IEEEauthordefaulttextstyle \@IEEEauthorblockconfadjspace -0.25em \@IEEEauthorblockNtopspace 0.0ex \@IEEEauthorblockAtopspace 0.0ex \@IEEEauthorblockNinterlinespace 2.6ex \@IEEEauthorblockAinte...

    work page 2003

  2. [2]

    write newline

    " write newline "" initialize.prev.this.status FUNCTION begin.bib preamble empty 'skip preamble write newline if " thebibliography " longest.label * " " * write newline " [1] #1 " write newline " url@rmstyle " write newline " " write newline " [2] #2 " write newline " =0pt " write newline " " ALTinterwordstretchfactor * " " * write newline " = 2 plus " wr...

  3. [3]

    C. J. Brooks, C. Grow, P. Craig, and D. Short, Cybersecurity Essentials. 1em plus 0.5em minus 0.4em John Wiley & Sons, 2018

    work page 2018

  4. [4]

    Cassandras and S

    C. Cassandras and S. Lafortune, Introduction to Discrete Event Systems . 1em plus 0.5em minus 0.4em Boston, MA: Springer US, 2008

    work page 2008

  5. [5]

    P. J. Ramadge and W. M. Wonham, ``Supervisory control of a class of discrete event processes,'' SIAM Journal on Control and Optimization, vol. 25, no. 1, pp. 206--230, 1987

    work page 1987

  6. [6]

    W. M. Wonham and K. Cai, Supervisory Control of Discrete-Event Systems. 1em plus 0.5em minus 0.4em Springer International Publishing, 2018

    work page 2018

  7. [7]

    Wonham, K

    W. Wonham, K. Cai, and K. Rudie, `` Supervisory control of discrete-event systems: A brief history ,'' Annual Reviews in Control, vol. 45, pp. 250--256, 2018

    work page 2018

  8. [8]

    Jacob, J

    R. Jacob, J. J. Lesage, and J. M. Faure, `` Overview of Discrete Event Systems Opacity: models, validation and quantification ,'' Annual Reviews in Control, vol. 28, no. 7, pp. 174--181, 2015

    work page 2015

Show all 13 references
  1. [9]

    Lafortune, F

    S. Lafortune, F. Lin, and C. N. Hadjicostis, ``On the history of diagnosability and opacity in discrete event systems,'' Annual Reviews in Control, vol. 45, pp. 257--266, 2018

    2018

  2. [10]

    Dubreil, P

    J. Dubreil, P. Darondeau, and H. Marchand, `` Opacity enforcing control synthesis ,'' in Proceedings of the 9th International Workshop on Discrete Event Systems, 2008, pp. 28--35

    2008

  3. [11]

    Y. C. Wu and S. Lafortune, `` Synthesis of opacity-enforcing insertion functions that can be publicly known ,'' in Proceedings of the 54th IEEE Conference on Decision and Control, 2015, pp. 3506--3513

    2015

  4. [12]

    Matsui and K

    S. Matsui and K. Cai, ``Secret securing with minimum cost,'' in Proceedings of the 61st Japan Joint Automatic Control Conference, 2018, pp. 1017--1024

    2018

  5. [13]

    Congdon, B

    P. Congdon, B. Aboba, A. Smith, G. Zorn, and J. Roese, `` I E E E 802.1 X remote authentication dial in user service ( R A D I U S ) usage guidelines,'' RFC 3580, Sept. 2003

    2003

Pith tools

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