betaFeedback

WorksMathematics

Safety Certificates for Systems under Attack via Stackelberg Set Games

Abstract

We study a Stackelberg set selection game for linear systems subject to bounded disturbances and additive attacks. The defender selects the vector parameter of a polytopic safe set template; the attacker, after observing this choice, selects the vector parameter of an admissible attack set. The payoff is a signed, facet-normalised invariance margin that tests invariance exactly and quantifies either the available contraction or the facet inflation needed when invariance fails. Both controlled and robust controlled invariance are treated, corresponding to different information patterns for the control input. Exploiting the structure of parameterised polyhedra, we show that within each validity region the margin is concave in the attack parameter, which reduces the follower minimisation to finitely many extreme parameters. The complete max–min game is then solved by a finite family of LPs, one per defender validity region, each enforcing all attacker regions under a common defender decision and guaranteed margin. The framework handles hard state constraints and additional costs related to the safe set size, and recovers optimal set parameters together with state and attack realisations that activate the certificate. A load frequency control example under false data injection illustrates the construction, the validity decomposition, and the two information patterns.

Introduction

Safety of a constrained control system can be certified by constructing an invariant set, namely, a region of the state space within which admissible control inputs keep the system trajectory despite disturbances [2]. Motivated by adversarial control settings [8, 9, 10, 11], we consider an attacker who observes the defensive design and selects the set of admissible additive attacks subject to prescribed budget constraints. The resulting design question is which safe set the defender should select when anticipating the attacker’s response.

Set invariance and polyhedral vertex based certificates are classical tools in constrained control [2]. The optimisation of invariant polytopes with prescribed complexity or facet directions is also established [3], [4], including joint facet and vertex parameterisations [5]. The affine vertex decompositions used in this note follow from parameterised polyhedra [1]; related decompositions have also been used for state dependent polytopic disturbances [6]. The leader–follower order and its information pattern are standard in Stackelberg games [7], and the resulting max–min programmes are bilvel in general [12].

While none of the above individual ingredients is new, our contribution is their coupling in a Stackelberg game over sets: The players choose the shape of polytopes within predefined templates, rather than a single state, an attack realisation, or a scalar uncertainty dilation. The payoff is a signed, facet normalised invariance margin for two control information patterns. Despite continuous set parameters and piecewise affine vertex maps, the follower parameter is eliminated exactly, while a single safe set offset and a single guaranteed margin are retained across all attacker regions. The complete game is therefore solved by one LP per defender validity region. Thus, our key contribution is the observation that strategic set selection preserves the LP structure for polytopic invariance, with complexity governed by the validity regions and generators.

Three observations deserve emphasis: First, the signed margin turns a binary invariance test into an objective: the sign decides invariance exactly, while magnitude measures available contraction and required inflation on a single facet normalised scale, thus safety can be traded against safe set size in a design problem. Second, for each defender parameter, the margin is concave in the attack parameter within a validity region. Consequently, an attacker best response can be selected from the union of the vertices of these regions. This finite reduction is exact, not requiring discretising the admissible parameter set. Third, the order of play cannot be recovered from the individual regional problems, because the defender commits to one safe set before the attacker selects its validity region, so optimising those problems separately solves a different and generally more optimistic problem. Compared with robust and reachability based certificates, where the adversary perturbs a realisation inside a fixed uncertainty set, the adversary here selects the uncertainty set itself subject to a budget.

Preliminaries and Setting

Notation: We consider a norm ∥⋅∥\lVert\cdot\rVert with unit ball B\mathbb{B} and its dual ∥⋅∥∗\lVert\cdot\rVert_*. Vector inequalities hold componentwise. The vector of all ones is 1\mathbf{1}, and vert⁡(⋅)\operatorname{vert}(\cdot) denotes the vertex set of a polytope.

The focus of this note is on linear dynamics and polytopic sets. Starting from a state constraint set, the defender selects the shape of a candidate safe set template, while the attacker selects the offsets of an admissible attack set.

The authors are listed in alphabetical order. N. A. is with the Department of Electrical and Computer Engineering, University of Thessaly, Greece (e-mail: n.athanас[email protected]), D. L. is with the School of Electronics, Electrical Engineering and Computer Science, Queen’s University Belfast, Belfast, U.K. (e-mail: [email protected]). G. P. is with the School of Computer Science and Information Technology, University College Cork, Cork, Ireland (e-mail: [email protected]). Q. Z. is with the Department of Electrical and Computer Engineering, New York University, Brooklyn, NY 11201 USA (e-mail: [email protected]). All authors gratefully acknowledge support from the U.S.-Ireland R&D Partnership under NSF Grant No. 2521130.

We consider the attacked system

x+=Ax+Bu+c+Ed+δ,(1)x^{+}=Ax+Bu+c+Ed+\delta, \tag*{(1)}

where x∈Rnx \in\mathbb{R}^{n}, u∈U⊆Rnuu \in U \subseteq\mathbb{R}^{n_u} is the defender control input, d∈Dd \in D is the nondeterministic additive disturbance, and δ∈Rn\delta\in\mathbb{R}^{n} is the additive attack vector. The control and disturbance sets are the compact polytopes

U={u:Fuu≤gu},D=conv⁡{d1,…,dND}.(2)U=\{u:F_u u\leq g_u\},\qquad D=\operatorname{conv}\{d_1,\ldots,d_{N_D}\}. \tag*{(2)}

Here FuF_u has mUm_U rows; state constraints are x∈Xx \in\mathcal{X}, with

X:={x:HXx≤hX}.(3)\mathcal{X}:=\{x:H_Xx\leq h_X\}. \tag*{(3)}

The defender and attacker sets are S(b)S(b) and Δ(ρ)\Delta(\rho), with

S(b):={x∈Rn:Cx≤b},b∈B⊆Rp,(4)S(b):=\{x\in\mathbb{R}^{n}:Cx\leq b\},\qquad b\in\mathcal{B}\subseteq\mathbb{R}^{p}, \tag*{(4)}
Δ(ρ):={δ∈Rn:CΔδ≤ρ},ρ∈R⊆RpΔ,(5)\Delta(\rho):=\{\delta\in\mathbb{R}^{n}:C_{\Delta}\delta\leq\rho\},\qquad\rho\in\mathcal{R}\subseteq\mathbb{R}^{p_{\Delta}}, \tag*{(5)}

The strategic variables b,ρb,\rho parameterise sets instead of individual states or attack realisations. We note the admissible set B\mathcal{B} can incorporate S(b)⊆XS(b)\subseteq\mathcal{X} directly, or this specification can be handled explicitly in a design problem, as outlined in Section IV-B.

Assumption 2.1. The sets B\mathcal{B}, R\mathcal{R}, UU and DD are nonempty compact polytopes for each admissible pair (b,ρ)(b,\rho), and the same holds for S(b)S(b) and Δ(ρ)\Delta(\rho).

The families in (4) and (5) are special cases of parameterised polyhedral sets, since their facet normals are fixed while the offset varies affinely on the parameters. The finite parameterised vertex representation in [1], explicitly stated in [6], yields a finite polytopic partition

B=⋃j∈JBj,R=⋃h∈HRh.(6)\mathcal{B}=\bigcup_{j\in\mathcal{J}}\mathcal{B}_j,\qquad\mathcal{R}=\bigcup_{h\in\mathcal{H}}\mathcal{R}_h. \tag*{(6)}

Specifically, for each j∈Jj\in\mathcal{J}, h∈Hh\in\mathcal{H} we have

S(b)=conv⁡{v1j(b),…,vqjj(b)},vrj(b)=Mrjb+mrj,(7)S(b)=\operatorname{conv}\{v_1^j(b),\ldots,v_{q_j}^j(b)\},\qquad v_r^j(b)=M_r^j b+m_r^j, \tag*{(7)}
Δ(ρ)=conv⁡{w1h(ρ),…,wqΔ,hh(ρ)},wsh(ρ)=Nshρ+nsh.(8)\Delta(\rho)=\operatorname{conv}\{w_1^h(\rho),\ldots,w_{q_{\Delta,h}}^h(\rho)\},\qquad w_s^h(\rho)=N_s^h\rho+n_s^h. \tag*{(8)}

Each defender region admits the representation Bj={b:Gjb≤βj}\mathcal{B}_j=\{b:G_jb\leq\beta_j\} with Gj∈RmB,j×pG_j\in\mathbb{R}^{m_{B,j}\times p}. We discard empty validity domains and allow different domains to overlap on their boundaries. The vertex representation is piecewise affine globally, however it is affine on any single region Bj\mathcal{B}_j, Rh\mathcal{R}_h. We are interested in two notions of controlled invariance.

Definition 2.2. Consider (1) with UU, DD as in (2) and S(b)S(b), Δ(ρ)\Delta(\rho) as in (4)–(5). For fixed (b,ρ)∈B×R(b,\rho)\in\mathcal{B}\times\mathcal{R}, the set S(b)S(b) is: (i) controlled invariant if ∀x∈S(b), ∀d∈D, ∀δ∈Δ(ρ), ∃u∈U:x+∈S(b)\forall x\in S(b),\ \forall d\in D,\ \forall\delta\in\Delta(\rho),\ \exists u\in U:x^{+}\in S(b); (ii) robust controlled invariant if ∀x∈S(b), ∃u∈U, ∀d∈D, ∀δ∈Δ(ρ):x+∈S(b)\forall x\in S(b),\ \exists u\in U,\ \forall d\in D,\ \forall\delta\in\Delta(\rho):x^{+}\in S(b).

Consequently, for controlled invariance, the input depends on (x,d,δ)(x,d,\delta), while for robust controlled invariance the input depends on xx alone. In both cases, the selected parameters (b,ρ)(b,\rho) are known to the controller; the distinction concerns access to the realised disturbance and attack. Without changing S(b)S(b), we normalise the nonzero rows of CC so that ∥CiT∥∗=1\lVert C_i^{\mathsf{T}}\rVert_{*}=1, rescaling the corresponding components of bb. For ϵ∈R\epsilon\in\mathbb{R} we define the safety margin set Sϵ(b):={z:Cz≤b−ϵ1}S_{\epsilon}(b):=\{z:Cz\leq b-\epsilon\mathbf{1}\}. For ϵ≥0\epsilon\geq0, Sϵ(b)=S(b)⊖ϵBS_{\epsilon}(b)=S(b)\ominus\epsilon\mathbb{B}; for ϵ<0\epsilon<0 it is a facetwise outward relaxation. In general, S(b)⊕rB⊆S−r(b)S(b)\oplus r\mathbb{B}\subseteq S_{-r}(b) for r=−ϵ>0r=-\epsilon>0, thus a negative margin should not be read as a Minkowski enlargement.

Definition 2.3. In the setting of Definition 2.2, let ν∈{ci,rci}\nu\in\{\mathrm{ci},\mathrm{rci}\}. The signed invariance margins ϵν:B×R→R\epsilon_{\nu}:\mathcal{B}\times\mathcal{R}\to\mathbb{R} are

ϵci(b,ρ):=max⁡{ϵ∈R:∀x∈S(b), ∀d∈D, ∀δ∈Δ(ρ), ∃u∈U:x+∈Sϵ(b)},\epsilon_{\mathrm{ci}}(b,\rho):=\max\{\epsilon\in\mathbb{R}:\forall x\in S(b),\ \forall d\in D,\ \forall\delta\in\Delta(\rho),\ \exists u\in U:x^{+}\in S_{\epsilon}(b)\},
ϵrci(b,ρ):=max⁡{ϵ∈R:∀x∈S(b), ∃u∈U, ∀d∈D, ∀δ∈Δ(ρ):x+∈Sϵ(b)}.\epsilon_{\mathrm{rci}}(b,\rho):=\max\{\epsilon\in\mathbb{R}:\forall x\in S(b),\ \exists u\in U,\ \forall d\in D,\ \forall\delta\in\Delta(\rho):x^{+}\in S_{\epsilon}(b)\}.

For fixed (b,ρ)(b,\rho) the feasible margin set is nonempty and bounded above, since compactness bounds x+x^{+}; closedness of S(b)S(b) and compactness of UU make both maxima attained. The sign of ϵν\epsilon_{\nu} is an exact invariance test: ϵν(b,ρ)≥0\epsilon_{\nu}(b,\rho)\geq0 if and only if S(b)S(b) satisfies ν\nu. A negative margin implies invariance fails and quantifies the required relaxation; a nonnegative one certifies invariance and measures the available contraction. Being scalar, ϵν\epsilon_{\nu} supplies the total ordering a zero sum payoff needs. We note the robust pattern admits fewer control choices, i.e., ϵrci(b,ρ)≤ϵci(b,ρ)\epsilon_{\mathrm{rci}}(b,\rho)\leq\epsilon_{\mathrm{ci}}(b,\rho) for any pair (b,ρ)∈B×R(b,\rho)\in\mathcal{B}\times\mathcal{R}. Thus, any nonnegative robust controlled invariance margin also certifies controlled invariance, whereas the converse does not hold in general.

Main Result

We derive finite programmes for the invariance margins and the associated Stackelberg set game: exact vertex certificates at fixed set parameters, a reduction of the attacker minimisation to finitely many extreme parameters one LP per defender region enforcing all attacker regions under a common parameter and margin, and the global solution by comparing their values.

Proposition 3.1 (Exact regional certificates). Let j∈Jj\in\mathcal{J} and h∈Hh\in\mathcal{H}. For any pair (b,ρ)∈Bj×Rh(b,\rho)\in\mathcal{B}_j\times\mathcal{R}_h, the controlled invariance margin ϵci(b,ρ)\epsilon_{\mathrm{ci}}(b,\rho) is the optimal value of

max⁡ϵ,{ur,l,s}ϵs.t.C(Avrj(b)+Bur,l,s+c)+C(Edl+wsh(ρ))≤b−ϵ1,∀r,l,s,Fuur,l,s≤gu,∀r,l,s.(9)\begin{aligned} \max_{\epsilon,\{u_{r,l,s}\}} \quad& \epsilon\\ \mathrm{s.t.}\quad& C(Av_r^j(b)+Bu_{r,l,s}+c)\\ &\quad+C(Ed_l+w_s^h(\rho))\leq b-\epsilon\mathbf{1},\qquad\forall r,l,s,\\ & F_u u_{r,l,s}\leq g_u,\qquad\forall r,l,s. \tag*{(9)} \end{aligned}

Respectively, the robust controlled invariance margin ϵrci(b,ρ)\epsilon_{\mathrm{rci}}(b,\rho) is the optimal value of

max⁡ϵ,{ur}ϵs.t.C(Avrj(b)+Bur+c)+C(Edl+wsh(ρ))≤b−ϵ1,∀r,l,s,Fuur≤gu,∀r.(10)\begin{aligned} \max_{\epsilon,\{u_r\}} \quad& \epsilon\\ \mathrm{s.t.}\quad& C(Av_r^j(b)+Bu_r+c)\\ &\quad+C(Ed_l+w_s^h(\rho))\leq b-\epsilon\mathbf{1},\qquad\forall r,l,s,\\ & F_u u_r\leq g_u,\qquad\forall r. \tag*{(10)} \end{aligned}

In (9)–(10), r=1,…,qjr=1,\ldots,q_j, l=1,…,NDl=1,\ldots,N_D, s=1,…,qΔ,hs=1,\ldots,q_{\Delta,h}.

Proof. To show necessity, we apply the corresponding quantified condition to each vertex triple (vrj(b),dl,wsh(ρ))(v_r^j(b),d_l,w_s^h(\rho)), precisely leading to (9) or (10). For sufficiency, we observe that any (x,d,δ)∈S(b)×D×Δ(ρ)(x,d,\delta)\in S(b)\times D\times\Delta(\rho) is a convex combination of the vertex triples, with coefficients $\alpha_r\beta_l\gamma_s formed as @page 2/6 starts_mid=0 ends_mid=1 We consider the attacked system

x+=Ax+Bu+c+Ed+δ,(11)x^{+}=Ax+Bu+c+Ed+\delta, \tag*{(11)}

where x∈Rnx \in\mathbb{R}^{n}, u∈U⊆Rnuu \in U \subseteq\mathbb{R}^{n_u} is the defender control input, d∈Dd \in D is the nondeterministic additive disturbance, and δ∈Rn\delta\in\mathbb{R}^{n} is the additive attack vector. The control and disturbance sets are the compact polytopes

U={u:Fuu≤gu},D=conv⁡{d1,…,dND}.(12)U=\{u:F_u u\leq g_u\},\qquad D=\operatorname{conv}\{d_1,\ldots,d_{N_D}\}. \tag*{(12)}

Here FuF_u has mUm_U rows; state constraints are x∈Xx \in\mathcal{X}, with

X:={x:HXx≤hX}.(13)\mathcal{X}:=\{x:H_Xx\leq h_X\}. \tag*{(13)}

The defender and attacker sets are S(b)S(b) and Δ(ρ)\Delta(\rho), with

S(b):={x∈Rn:Cx≤b},b∈B⊆Rp,(14)S(b):=\{x\in\mathbb{R}^{n}:Cx\leq b\},\qquad b\in\mathcal{B}\subseteq\mathbb{R}^{p}, \tag*{(14)}
Δ(ρ):={δ∈Rn:CΔδ≤ρ},ρ∈R⊆RpΔ,(15)\Delta(\rho):=\{\delta\in\mathbb{R}^{n}:C_{\Delta}\delta\leq\rho\},\qquad\rho\in\mathcal{R}\subseteq\mathbb{R}^{p_{\Delta}}, \tag*{(15)}

The strategic variables b,ρb,\rho parameterise sets instead of individual states or attack realisations. We note the admissible set B\mathcal{B} can incorporate S(b)⊆XS(b)\subseteq\mathcal{X} directly, or this specification can be handled explicitly in a design problem, as outlined in Section IV-B.

Assumption 2.1. The sets B\mathcal{B}, R\mathcal{R}, UU and DD are nonempty compact polytopes for each admissible pair (b,ρ)(b,\rho), and the same holds for S(b)S(b) and Δ(ρ)\Delta(\rho).

The families in (4) and (5) are special cases of parameterised polyhedral sets, since their facet normals are fixed while the offset varies affinely on the parameters. The finite parameterised vertex representation in [1], explicitly stated in [6], yields a finite polytopic partition

B=⋃j∈JBj,R=⋃h∈HRh.(16)\mathcal{B}=\bigcup_{j\in\mathcal{J}}\mathcal{B}_j,\qquad\mathcal{R}=\bigcup_{h\in\mathcal{H}}\mathcal{R}_h. \tag*{(16)}

Specifically, for each j∈Jj\in\mathcal{J}, h∈Hh\in\mathcal{H} we have

S(b)=conv⁡{v1j(b),…,vqjj(b)},vrj(b)=Mrjb+mrj,(17)S(b)=\operatorname{conv}\{v_1^j(b),\ldots,v_{q_j}^j(b)\},\qquad v_r^j(b)=M_r^j b+m_r^j, \tag*{(17)}
Δ(ρ)=conv⁡{w1h(ρ),…,wqΔ,hh(ρ)},wsh(ρ)=Nshρ+nsh.(18)\Delta(\rho)=\operatorname{conv}\{w_1^h(\rho),\ldots,w_{q_{\Delta,h}}^h(\rho)\},\qquad w_s^h(\rho)=N_s^h\rho+n_s^h. \tag*{(18)}

Each defender region admits the representation Bj={b:Gjb≤βj}\mathcal{B}_j=\{b:G_jb\leq\beta_j\} with Gj∈RmB,j×pG_j\in\mathbb{R}^{m_{B,j}\times p}. We discard empty validity domains and allow different domains to overlap on their boundaries. The vertex representation is piecewise affine globally, however it is affine on any single region Bj\mathcal{B}_j, Rh\mathcal{R}_h. We are interested in two notions of controlled invariance.

Definition 2.2. Consider (1) with UU, DD as in (2) and S(b)S(b), Δ(ρ)\Delta(\rho) as in (4)–(5). For fixed (b,ρ)∈B×R(b,\rho)\in\mathcal{B}\times\mathcal{R}, the set S(b)S(b) is: (i) controlled invariant if ∀x∈S(b), ∀d∈D, ∀δ∈Δ(ρ), ∃u∈U:x+∈S(b)\forall x\in S(b),\ \forall d\in D,\ \forall\delta\in\Delta(\rho),\ \exists u\in U:x^{+}\in S(b); (ii) robust controlled invariant if ∀x∈S(b), ∃u∈U, ∀d∈D, ∀δ∈Δ(ρ):x+∈S(b)\forall x\in S(b),\ \exists u\in U,\ \forall d\in D,\ \forall\delta\in\Delta(\rho):x^{+}\in S(b).

Consequently, for controlled invariance, the input depends on (x,d,δ)(x,d,\delta), while for robust controlled invariance the input depends on xx alone. In both cases, the selected parameters (b,ρ)(b,\rho) are known to the controller; the distinction concerns access to the realised disturbance and attack. Without changing S(b)S(b), we normalise the nonzero rows of CC so that ∥CiT∥∗=1\lVert C_i^{\mathsf{T}}\rVert_{*}=1, rescaling the corresponding components of bb. For ϵ∈R\epsilon\in\mathbb{R} we define the safety margin set Sϵ(b):={z:Cz≤b−ϵ1}S_{\epsilon}(b):=\{z:Cz\leq b-\epsilon\mathbf{1}\}. For ϵ≥0\epsilon\geq0, Sϵ(b)=S(b)⊖ϵBS_{\epsilon}(b)=S(b)\ominus\epsilon\mathbb{B}; for ϵ<0\epsilon<0 it is a facetwise outward relaxation. In general, S(b)⊕rB⊆S−r(b)S(b)\oplus r\mathbb{B}\subseteq S_{-r}(b) for r=−ϵ>0r=-\epsilon>0, thus a negative margin should not be read as a Minkowski enlargement.

Definition 2.3. In the setting of Definition 2.2, let ν∈{ci,rci}\nu\in\{\mathrm{ci},\mathrm{rci}\}. The signed invariance margins ϵν:B×R→R\epsilon_{\nu}:\mathcal{B}\times\mathcal{R}\to\mathbb{R} are

ϵci(b,ρ):=max⁡{ϵ∈R:∀x∈S(b), ∀d∈D, ∀δ∈Δ(ρ), ∃u∈U:x+∈Sϵ(b)},\epsilon_{\mathrm{ci}}(b,\rho):=\max\{\epsilon\in\mathbb{R}:\forall x\in S(b),\ \forall d\in D,\ \forall\delta\in\Delta(\rho),\ \exists u\in U:x^{+}\in S_{\epsilon}(b)\},
ϵrci(b,ρ):=max⁡{ϵ∈R:∀x∈S(b), ∃u∈U, ∀d∈D, ∀δ∈Δ(ρ):x+∈Sϵ(b)}.\epsilon_{\mathrm{rci}}(b,\rho):=\max\{\epsilon\in\mathbb{R}:\forall x\in S(b),\ \exists u\in U,\ \forall d\in D,\ \forall\delta\in\Delta(\rho):x^{+}\in S_{\epsilon}(b)\}.

For fixed (b,ρ)(b,\rho) the feasible margin set is nonempty and bounded above, since compactness bounds x+x^{+}; closedness of S(b)S(b) and compactness of UU make both maxima attained. The sign of ϵν\epsilon_{\nu} is an exact invariance test: ϵν(b,ρ)≥0\epsilon_{\nu}(b,\rho)\geq0 if and only if S(b)S(b) satisfies ν\nu. A negative margin implies invariance fails and quantifies the required relaxation; a nonnegative one certifies invariance and measures the available contraction. Being scalar, ϵν\epsilon_{\nu} supplies the total ordering a zero sum payoff needs. We note the robust pattern admits fewer control choices, i.e., ϵrci(b,ρ)≤ϵci(b,ρ)\epsilon_{\mathrm{rci}}(b,\rho)\leq\epsilon_{\mathrm{ci}}(b,\rho) for any pair (b,ρ)∈B×R(b,\rho)\in\mathcal{B}\times\mathcal{R}. Thus, any nonnegative robust controlled invariance margin also certifies controlled invariance, whereas the converse does not hold in general.

Main Result

We derive finite programmes for the invariance margins and the associated Stackelberg set game: exact vertex certificates at fixed set parameters, a reduction of the attacker minimisation to finitely many extreme parameters one LP per defender region enforcing all attacker regions under a common parameter and margin, and the global solution by comparing their values.

Proposition 3.1 (Exact regional certificates). Let j∈Jj\in\mathcal{J} and h∈Hh\in\mathcal{H}. For any pair (b,ρ)∈Bj×Rh(b,\rho)\in\mathcal{B}_j\times\mathcal{R}_h, the controlled invariance margin ϵci(b,ρ)\epsilon_{\mathrm{ci}}(b,\rho) is the optimal value of

max⁡ϵ,{ur,l,s}ϵs.t.C(Avrj(b)+Bur,l,s+c)+C(Edl+wsh(ρ))≤b−ϵ1,∀r,l,s,Fuur,l,s≤gu,∀r,l,s.(19)\begin{aligned} \max_{\epsilon,\{u_{r,l,s}\}} \quad& \epsilon\\ \mathrm{s.t.}\quad& C(Av_r^j(b)+Bu_{r,l,s}+c)\\ &\quad+C(Ed_l+w_s^h(\rho))\leq b-\epsilon\mathbf{1},\qquad\forall r,l,s,\\ & F_u u_{r,l,s}\leq g_u,\qquad\forall r,l,s. \tag*{(19)} \end{aligned}

Respectively, the robust controlled invariance margin ϵrci(b,ρ)\epsilon_{\mathrm{rci}}(b,\rho) is the optimal value of

max⁡ϵ,{ur}ϵs.t.C(Avrj(b)+Bur+c)+C(Edl+wsh(ρ))≤b−ϵ1,∀r,l,s,Fuur≤gu,∀r.(20)\begin{aligned} \max_{\epsilon,\{u_r\}} \quad& \epsilon\\ \mathrm{s.t.}\quad& C(Av_r^j(b)+Bu_r+c)\\ &\quad+C(Ed_l+w_s^h(\rho))\leq b-\epsilon\mathbf{1},\qquad\forall r,l,s,\\ & F_u u_r\leq g_u,\qquad\forall r. \tag*{(20)} \end{aligned}

In (9)–(10), r=1,…,qjr=1,\ldots,q_j, l=1,…,NDl=1,\ldots,N_D, s=1,…,qΔ,hs=1,\ldots,q_{\Delta,h}.

Proof. To show necessity, we apply the corresponding quantified condition to each vertex triple (vrj(b),dl,wsh(ρ))(v_r^j(b),d_l,w_s^h(\rho)), precisely leading to (9) or (10). For sufficiency, we observe that any (x,d,δ)∈S(b)×D×Δ(ρ)(x,d,\delta)\in S(b)\times D\times\Delta(\rho) is a convex combination of the vertex triples, with coefficients $\alpha_r\beta_l\gamma_s formed as products of the barycentric coefficients of xx, dd and δ\delta, whose marginals reproduce the three components. For controlled invariance, the same product coefficients combine the associated inputs ur,l,su_{r,l,s}. For robust controlled invariance, writing x=∑rαrvrj(b)x=\sum_r\alpha_rv_r^j(b) and selecting u=∑rαruru=\sum_r\alpha_ru_r gives an admissible input that is independent of the subsequently realised (d,δ)(d,\delta). Convexity of UU, affinity of (1), and convexity of Sε(b)S_\varepsilon(b) establish the corresponding quantified condition. ■

In the sequel, after fixing Bj\mathcal{B}_j and Rh\mathcal{R}_h, we replace the inequalities quantified by ρ\rho with finitely many inequalities, for every bb. Throughout, ενj,h(b,ρ)\varepsilon_\nu^{j,h}(b,\rho) denotes the optimal value of the programme of Proposition 3.1 with the affine maps of (j,h)(j,h). It coincides with εν(b,ρ)\varepsilon_\nu(b,\rho) for every (b,ρ)∈Bj×Rh(b,\rho)\in\mathcal{B}_j\times\mathcal{R}_h, so parameters in overlapping domains receive the same value. The regional game value is

Vνj,h:=max⁡b∈Bjmin⁡ρ∈Rhενj,h(b,ρ),ν∈{ci,rci},(21)V_\nu^{j,h}:=\max_{b\in\mathcal{B}_j}\min_{\rho\in\mathcal{R}_h}\varepsilon_\nu^{j,h}(b,\rho),\qquad\nu\in\{\mathrm{ci},\mathrm{rci}\}, \tag*{(21)}

with the superscript indicating that the affine vertex maps (7)–(8) are fixed. Since Rh\mathcal{R}_h is a compact polytope, its vertex set vert⁡(Rh)={ρh,1,…,ρh,Kh}\operatorname{vert}(\mathcal{R}_h)=\{\rho^{h,1},\ldots,\rho^{h,K_h}\} is finite, with Kh=∣vert⁡(Rh)∣K_h=|\operatorname{vert}(\mathcal{R}_h)|. The following result writes the max–min problem (11) as a maximisation with finitely many hypograph inequalities; Proposition 3.3 then replaces each by linear constraints, producing one LP.

Lemma 3.2 (Concavity and finite hypograph representation). For every j∈Jj\in\mathcal{J}, h∈Hh\in\mathcal{H}, and b∈Bjb\in\mathcal{B}_j, the mapping ενj,h(b,⋅)\varepsilon_\nu^{j,h}(b,\cdot) is concave on Rh\mathcal{R}_h. Moreover,

Vνj,h=max⁡b,t tV_\nu^{j,h}=\max_{b,t}\ t
s.t.b∈Bj,\text{s.t.}\quad b\in\mathcal{B}_j,
t≤ενj,h(b,ρh,k),k=1,…,Kh.(22)t\leq\varepsilon_\nu^{j,h}(b,\rho^{h,k}),\qquad k=1,\ldots,K_h. \tag*{(22)}

Proof. Take tt as a common lower bound on all attacker responses, so that for b∈Bjb\in\mathcal{B}_j

min⁡ρ∈Rhενj,h(b,ρ)=max⁡t{t:t≤ενj,h(b,ρ), ∀ρ∈Rh}.(23)\min_{\rho\in\mathcal{R}_h}\varepsilon_\nu^{j,h}(b,\rho)=\max_t\{t:t\leq\varepsilon_\nu^{j,h}(b,\rho),\ \forall\rho\in\mathcal{R}_h\}. \tag*{(23)}

For concavity, fix b∈Bjb\in\mathcal{B}_j, take ρ1,ρ2∈Rh\rho^1,\rho^2\in\mathcal{R}_h and θ∈[0,1]\theta\in[0,1], and let (εa,ua)(\varepsilon^a,u^a) optimise the relevant LP of Proposition 3.1 at ρa\rho^a. Set ρθ:=θρ1+(1−θ)ρ2\rho^\theta:=\theta\rho^1+(1-\theta)\rho^2, εθ:=θε1+(1−θ)ε2\varepsilon^\theta:=\theta\varepsilon^1+(1-\theta)\varepsilon^2, and combine the controls in the same way, ur,l,sθu_{r,l,s}^\theta for controlled invariance and urθu_r^\theta for the robust pattern; both lie in UU by convexity. Since wsh(⋅)w_s^h(\cdot) is affine on Rh\mathcal{R}_h, every x+x^+ constraint at (ρθ,εθ,uθ)(\rho^\theta,\varepsilon^\theta,u^\theta) is the convex combination of those at (ρa,εa,ua)(\rho^a,\varepsilon^a,u^a), thus it is satisfied, so ενj,h(b,ρθ)≥εθ\varepsilon_\nu^{j,h}(b,\rho^\theta)\geq\varepsilon^\theta, which is concavity. Writing ρ∈Rh\rho\in\mathcal{R}_h as ∑kθkρh,k\sum_k\theta_k\rho^{h,k} with θ≥0\theta\geq0, ∑kθk=1\sum_k\theta_k=1, concavity gives ενj,h(b,ρ)≥∑kθkενj,h(b,ρh,k)≥min⁡kενj,h(b,ρh,k)\varepsilon_\nu^{j,h}(b,\rho)\geq\sum_k\theta_k\varepsilon_\nu^{j,h}(b,\rho^{h,k})\geq\min_k\varepsilon_\nu^{j,h}(b,\rho^{h,k}), so the minimum over Rh\mathcal{R}_h is at a vertex. Substituting in (13) gives (12). ■

The KhK_h inequalities (12c) of Lemma 3.2 are an exact reduction, rather than a sampling or gridding approximation, and are the key finite step of the game formulation. The direction of the curvature is essential: the follower minimises a function that is concave in its own parameter, so an extreme minimiser always exists. A convex margin may attain its minimum in the relative interior of Rh\mathcal{R}_h, thus a vertex reduction is not generally valid in that case. To ease notation, we write the fixed attack vertices and the affine residuals as follows

wsh,k:=wsh(ρh,k),s=1,…,qΔ,h,k=1,…,Kh,w_s^{h,k}:=w_s^h(\rho^{h,k}),\qquad s=1,\ldots,q_{\Delta,h},\quad k=1,\ldots,K_h,
Φi,r,l,sj,h,k(b,u):=Ci(Avrj(b)+Bu+c+Edl+wsh,k)−bi.\Phi_{i,r,l,s}^{j,h,k}(b,u):=C_i\left(Av_r^j(b)+Bu+c+Ed_l+w_s^{h,k}\right)-b_i.

For fixed b∈Bjb\in\mathcal{B}_j and (h,k)∈H×[1,Kh](h,k)\in\mathcal{H}\times[1,K_h], we define explicitly the two certificate feasible sets

Fcij,h,k(b):={(η,{ur,l,s}):Φi,r,l,sj,h,k(b,ur,l,s)≤−η, ∀i,r,l,s, Fur,l,s≤gu, ∀r,l,s},(24)\mathcal{F}_{\mathrm{ci}}^{j,h,k}(b):=\left\{(\eta,\{u_{r,l,s}\}):\Phi_{i,r,l,s}^{j,h,k}(b,u_{r,l,s})\leq-\eta,\ \forall i,r,l,s,\ Fu_{r,l,s}\leq g_u,\ \forall r,l,s\right\}, \tag*{(24)}
Frcij,h,k(b):={(η,{ur}):Φi,r,l,sj,h,k(b,ur)≤−η, ∀i,r,l,s, Fur≤gu, ∀r}.(25)\mathcal{F}_{\mathrm{rci}}^{j,h,k}(b):=\left\{(\eta,\{u_r\}):\Phi_{i,r,l,s}^{j,h,k}(b,u_r)\leq-\eta,\ \forall i,r,l,s,\ Fu_r\leq g_u,\ \forall r\right\}. \tag*{(25)}

Proposition 3.3 (Regional LP building block). Given any (j,h)∈J×H(j,h)\in\mathcal{J}\times\mathcal{H}, the controlled invariance regional game Vcij,hV_{\mathrm{ci}}^{j,h} is the optimal value of

max⁡b,t,{ur,l,s,k} t\max_{b,t,\{u_{r,l,s,k}\}}\ t
s.t.Gjb≤βj,\text{s.t.}\quad G_jb\leq\beta_j,
Φi,r,l,sj,h,k(b,ur,l,s,k)≤−t,∀i,r,l,s,k,\Phi_{i,r,l,s}^{j,h,k}(b,u_{r,l,s,k})\leq-t,\qquad\forall i,r,l,s,k,
Fur,l,s,k≤gu,∀r,l,s,k.(26)Fu_{r,l,s,k}\leq g_u,\qquad\forall r,l,s,k. \tag*{(26)}

The robust game Vrcij,hV_{\mathrm{rci}}^{j,h} is the optimal value of

max⁡b,t,{ur,k} t\max_{b,t,\{u_{r,k}\}}\ t
s.t.Gjb≤βj,\text{s.t.}\quad G_jb\leq\beta_j,
Φi,r,l,sj,h,k(b,ur,k)≤−t,∀i,r,l,s,k,\Phi_{i,r,l,s}^{j,h,k}(b,u_{r,k})\leq-t,\qquad\forall i,r,l,s,k,
Fur,k≤gu,∀r,k.(27)Fu_{r,k}\leq g_u,\qquad\forall r,k. \tag*{(27)}

Proof. By Lemma 3.2, it suffices to impose t≤ενj,h(b,ρh,k)t\leq\varepsilon_\nu^{j,h}(b,\rho^{h,k}); for fixed kk, Proposition 3.1 and (14)–(15) give

ενj,h(b,ρh,k)=max⁡{η:∃uk, (η,uk)∈Fνj,h,k(b)}.(28)\varepsilon_\nu^{j,h}(b,\rho^{h,k})=\max\{\eta:\exists u^k,\ (\eta,u^k)\in\mathcal{F}_\nu^{j,h,k}(b)\}. \tag*{(28)}

The feasible set is downward closed in η\eta: if (η,uk)(\eta,u^k) is feasible, so is (η~,uk)(\tilde{\eta},u^k) for every η~≤η\tilde{\eta}\leq\eta. Since the maximum in (18) is attained,

t≤ενj,h(b,ρh,k)⟺∃uk: (t,uk)∈Fνj,h,k(b).t\leq\varepsilon_\nu^{j,h}(b,\rho^{h,k})\Longleftrightarrow\exists u^k:\ (t,u^k)\in\mathcal{F}_\nu^{j,h,k}(b).

Stacking the KhK_h equivalences yields (16) and (17). ■

Both programmes of Proposition 3.3 are LPs, since vrj(b)v_r^j(b) is affine in bb and wsh,kw_s^{h,k} is fixed. They provide the constraint blocks associated with one pair (Bj,Rh)(\mathcal{B}_j,\mathcal{R}_h); the complete game on Bj\mathcal{B}_j requires all h∈Hh\in\mathcal{H}, as shown next.

Remark 3.4. In (17), ur,ku_{r,k} may depend on ρh,k\rho^{h,k} but is shared across all dld_l and wsh,kw_s^{h,k}, following the order ∀ρ∃u∀d∀δ\forall\rho\exists u\forall d\forall\delta. Replacing every ur,ku_{r,k} by one uru_r imposes instead ∀u∃∀d∀δ\forall u\exists\forall d\forall\delta, for a controller derived before ρ\rho, and possibly smaller margin.

Proposition 3.1 concerns a fixed pair (b,ρ)(b,\rho), while Lemma 3.2 and Proposition 3.3 fix (j,h)(j,h) and cover every (b,ρ)∈Bj×Rh(b,\rho)\in\mathcal{B}_j\times\mathcal{R}_h. In the game, however, S(b)S(b) must be safe against every ρ∈R\rho\in\mathcal{R}, so we fix jj and account for all h∈Hh\in\mathcal{H}, setting Vν,j⋆:=max⁡b∈Bjmin⁡ρ∈Rεν(b,ρ)V_{\nu,j}^\star:=\max_{b\in\mathcal{B}_j}\min_{\rho\in\mathcal{R}}\varepsilon_\nu(b,\rho).

Proposition 3.5 (One LP per defender region against all attacker regions). For each j∈Jj\in\mathcal{J}, Vν,j⋆V_{\nu,j}^\star is obtained from one LP containing the constraint blocks for all h∈Hh \in\mathcal{H} and k=1,…,Khk=1,\ldots,K_h. For controlled invariance, the LP is

Vci,j∗=max⁡b,t,{ur,l,s,h,k}t(29)V^{\ast}_{\mathrm{ci},j}=\max_{b,t,\{u_{r,l,s,h,k}\}} t \tag*{(29)}
s.t.Gjb≤βj,Φi,r,l,sj,h,k(b,ur,l,s,h,k)≤−t,∀h,k,i,r,l,s,Fuur,l,s,h,k≤gu,∀h,k,r,l,s.(30)\begin{aligned} \text{s.t.}\quad&G_jb\le\beta_j,\\ &\Phi^{j,h,k}_{i,r,l,s}(b,u_{r,l,s,h,k})\le-t,\quad\forall h,k,i,r,l,s,\\ &F_u u_{r,l,s,h,k}\le g_u,\quad\forall h,k,r,l,s. \tag*{(30)} \end{aligned}

For robust controlled invariance, it is

Vrci,j∗=max⁡b,t,{ur,h,k}t(31)V^{\ast}_{\mathrm{rci},j}=\max_{b,t,\{u_{r,h,k}\}} t \tag*{(31)}
s.t.Gjb≤βj,Φi,r,l,sj,h,k(b,ur,h,k)≤−t,∀h,k,i,r,l,s,Fuur,h,k≤gu,∀h,k,r.(32)\begin{aligned} \text{s.t.}\quad&G_jb\le\beta_j,\\ &\Phi^{j,h,k}_{i,r,l,s}(b,u_{r,h,k})\le-t,\quad\forall h,k,i,r,l,s,\\ &F_u u_{r,h,k}\le g_u,\quad\forall h,k,r. \tag*{(32)} \end{aligned}

Proof. Since R=⋃h∈HRh\mathcal{R}=\bigcup_{h\in\mathcal{H}}\mathcal{R}_h, for every b∈Bjb\in\mathcal{B}_j we have min⁡ρ∈Rεν(b,ρ)=min⁡h∈Hmin⁡ρ∈Rhενj,h(b,ρ)\min_{\rho\in\mathcal{R}}\varepsilon_\nu(b,\rho)=\min_{h\in\mathcal{H}}\min_{\rho\in\mathcal{R}_h}\varepsilon_\nu^{j,h}(b,\rho). Lemma 3.2 reduces the inner minimum on every Rh\mathcal{R}_h to its KhK_h vertices. A common lower bound tt must therefore satisfy the certificate block associated with every pair (h,k)(h,k). Stacking all blocks while retaining the same bb and tt gives (19) and (20). ■

Remark 3.6 (Size of the regional LPs). Both LPs are feasible: any b∈Bjb\in\mathcal{B}_j and admissible controls satisfy the successor inequalities for sufficiently negative tt. Their optimal values are finite and attained because Bj\mathcal{B}_j and UU are compact and the constraints are closed. With Σ1=∑hKh\Sigma_1=\sum_h K_h, Σ2=∑hKhqΔh\Sigma_2=\sum_h K_hq\Delta_h and Σ3=∑hKh(pNDqΔh+mU)\Sigma_3=\sum_h K_h(pN_Dq\Delta_h+m_U), the LP of Proposition 3.5 on Bj\mathcal{B}_j has

Nci,jvar=p+1+nuqjNDΣ2,N^{\mathrm{var}}_{\mathrm{ci},j}=p+1+n_uq_jN_D\Sigma_2,
Nci,jcon=mB,j+qjNDΣ2(p+mU),N^{\mathrm{con}}_{\mathrm{ci},j}=m_{B,j}+q_jN_D\Sigma_2(p+m_U),
Nrci,jvar=p+1+nuqjΣ1,Nrci,jcon=mB,j+qjΣ3,N^{\mathrm{var}}_{\mathrm{rci},j}=p+1+n_uq_j\Sigma_1,\qquad N^{\mathrm{con}}_{\mathrm{rci},j}=m_{B,j}+q_j\Sigma_3,

the regional block of Proposition 3.3 being the single term hh. Each (r,l,s,k)(r,l,s,k) carries its own control under controlled invariance, whereas under robust controlled invariance each (r,k)(r,k) carries one control shared over (l,s)(l,s). The counts grow with all extreme parameter choices from all attacker regions.

Remark 3.7. Let gj,h(b):=min⁡ρ∈Rhενj,h(b,ρ)g_{j,h}(b):=\min_{\rho\in\mathcal{R}_h}\varepsilon_\nu^{j,h}(b,\rho). Solving Proposition 3.3 separately for each hh returns Vνj,h=max⁡b∈Bjgj,h(b)V_\nu^{j,h}=\max_{b\in\mathcal{B}_j}g_{j,h}(b), which permits a different optimiser for every attacker region, whereas the order of play requires one bb to face all of them,

Vν,j⋆=max⁡b∈Bjmin⁡h∈Hgj,h(b)≤min⁡h∈Hmax⁡b∈Bjgj,h(b),V_{\nu,j}^{\star}=\max_{b\in\mathcal{B}_j}\min_{h\in\mathcal{H}}g_{j,h}(b)\le\min_{h\in\mathcal{H}}\max_{b\in\mathcal{B}_j}g_{j,h}(b),

the minimax inequality being possibly strict, since an optimiser for one attacker region may have a poor margin on another. The values Vνj,hV_\nu^{j,h} are therefore insufficient to recover Vν,j⋆V_{\nu,j}^{\star}, and equality would require additional structure that is not assumed. Proposition 3.5 preserves the order by sharing bb and tt across all hh blocks, with only the scenario controls being allowed to differ.

Thus, the LPs of distinct defender regions can be solved in parallel, but within each LP the attacker blocks share bb and tt and must be optimised jointly. We next state the complete game and its solution concept.

Stackelberg set game and equilibrium

Let ν∈{ci,rci}\nu\in\{\mathrm{ci},\mathrm{rci}\}. In the Stackelberg set game the leader (defender) selects b∈Bb\in\mathcal{B}, the follower (attacker) observes bb and selects ρ∈R\rho\in\mathcal{R}, and the payoff εν(b,ρ)\varepsilon_\nu(b,\rho) is maximised by the leader and minimised by the follower. The follower best response correspondence and the leader guaranteed margin are

Pν(b):=arg⁡min⁡ρ∈Rεν(b,ρ),gν(b):=min⁡ρ∈Rεν(b,ρ).(33)P_\nu(b):=\arg\min_{\rho\in\mathcal{R}}\varepsilon_\nu(b,\rho),\qquad g_\nu(b):=\min_{\rho\in\mathcal{R}}\varepsilon_\nu(b,\rho). \tag*{(33)}

A pair (b⋆,ρ⋆)∈B×R(b^\star,\rho^\star)\in\mathcal{B}\times\mathcal{R} is a Stackelberg equilibrium of the game if b⋆∈arg⁡max⁡b∈Bgν(b)b^\star\in\arg\max_{b\in\mathcal{B}}g_\nu(b) and ρ⋆∈Pν(b⋆)\rho^\star\in P_\nu(b^\star), and the associated Stackelberg value is Vν⋆:=gν(b⋆)=εν(b⋆,ρ⋆)V_\nu^\star:=g_\nu(b^\star)=\varepsilon_\nu(b^\star,\rho^\star).

The game is zero sum, so every ρ⋆∈Pν(b⋆)\rho^\star\in P_\nu(b^\star) returns the same payoff and the Stackelberg value is unambiguous,

Vν⋆=max⁡b∈Bmin⁡ρ∈Rεν(b,ρ),ν∈{ci,rci}.(34)V_\nu^\star=\max_{b\in\mathcal{B}}\min_{\rho\in\mathcal{R}}\varepsilon_\nu(b,\rho),\qquad\nu\in\{\mathrm{ci},\mathrm{rci}\}. \tag*{(34)}

Existence of an equilibrium is not assumed. It follows constructively from Theorem 3.9 and Proposition 4.1 below, which also return b⋆b^\star and one ρ⋆∈Pν(b⋆)\rho^\star\in P_\nu(b^\star). The following theorem is the main result since it lifts the regional elimination to the full defender and attacker parameter spaces without changing the order of play.

Theorem 3.9 (Exact solution of the set game). Under Assumption 2.1 and the resulting validity-domain decompositions (6)–(8), the value of (22) is

Vν⋆=max⁡j∈JVν,j⋆,ν∈{ci,rci},(35)V_\nu^\star=\max_{j\in\mathcal{J}}V_{\nu,j}^\star,\qquad\nu\in\{\mathrm{ci},\mathrm{rci}\}, \tag*{(35)}

where Vci,j⋆V_{\mathrm{ci},j}^\star and Vrci,j⋆V_{\mathrm{rci},j}^\star are the LP values in (19) and (20), respectively. Hence the complete Stackelberg set game is solved exactly by ∣J∣|\mathcal{J}| LPs, each corresponding to one safe set vertex region and containing all attack set vertex regions.

Proof. By the finite cover B=⋃j∈JBj\mathcal{B}=\bigcup_{j\in\mathcal{J}}\mathcal{B}_j, Vν⋆=max⁡j∈Jmax⁡b∈Bjmin⁡ρ∈Rεν(b,ρ)=max⁡j∈JVν,j⋆V_\nu^\star=\max_{j\in\mathcal{J}}\max_{b\in\mathcal{B}_j}\min_{\rho\in\mathcal{R}}\varepsilon_\nu(b,\rho)=\max_{j\in\mathcal{J}}V_{\nu,j}^\star. Proposition 3.5 shows that each Vν,j⋆V_{\nu,j}^\star is the value of one LP. Taking the largest of this finite collection establishes (23). ■

Overlaps between validity domains do not affect the optimal value in Theorem 3.9, since εν(b,ρ)\varepsilon_\nu(b,\rho) depends on the sets S(b)S(b) and Δ(ρ)\Delta(\rho), independently of their vertex representations. A parameter belonging to multiple domains therefore yields the same margin in each representation and does not alter the global maximisation. Moreover, if the safe set vertices are affine throughout B\mathcal{B}, the complete game reduces to one LP, with additional attacker validity regions contributing only further constraint blocks.

Optimal parameters, design, and computation

Recovery of optimal parameters and an active certificate tuple

The reformulation recovers optimal defender and attacker parameters and a state, control, disturbance and attack tuple attaining an active successor constraint.

Proposition 4.1 (Recovery of optimal parameters and an active certificate tuple). Let j⋆∈arg⁡max⁡j∈JVν,j⋆j^\star\in\arg\max_{j\in\mathcal{J}}V_{\nu,j}^\star and (b⋆,t⋆)(b^\star,t^\star) optimise its LP in Proposition 3.5. Then t⋆=Vν⋆t^\star=V_\nu^\star.

With

(h⋆,k⋆)∈arg⁡min⁡h∈H, 1≤k≤Kh ενj⋆,h(b⋆,ρh,k),(36)(h^\star,k^\star)\in\underset{h\in\mathcal{H},\,1\leq k\leq K_h}{\arg\min}\ \varepsilon_\nu^{j^\star,h}(b^\star,\rho^{h,k}), \tag*{(36)}

ρ⋆:=ρh⋆,k⋆\rho^\star:=\rho^{h^\star,k^\star} satisfies ρ⋆∈Pν(b⋆)\rho^\star\in P_\nu(b^\star), so (b⋆,ρ⋆)(b^\star,\rho^\star) is a Stackelberg equilibrium per Definition 3.8, and εν(b⋆,ρ⋆)=t⋆\varepsilon_\nu(b^\star,\rho^\star)=t^\star. Resolving the certificate LP of Proposition 3.1 at (b⋆,ρ⋆)(b^\star,\rho^\star), there is an active tuple (i⋆,r⋆,l⋆,s⋆)(i^\star,r^\star,l^\star,s^\star) with

Ci⋆(Ax⋆+Bu⋆+c+Ed⋆+δ⋆)=bi⋆⋆−t⋆,(37)C_{i^\star}(Ax^\star+Bu^\star+c+Ed^\star+\delta^\star)=b_{i^\star}^\star-t^\star, \tag*{(37)}

where x⋆=vr⋆j⋆(b⋆)x^\star=v_{r^\star}^{j^\star}(b^\star), d⋆=dl⋆d^\star=d_{l^\star}, δ⋆=wh⋆j⋆(ρ⋆)\delta^\star=w_{h^\star}^{j^\star}(\rho^\star) and u⋆=ur⋆,l⋆,s⋆u^\star=u_{r^\star,l^\star,s^\star} for controlled invariance, u⋆=ur⋆u^\star=u_{r^\star} for the robust pattern. The tuple (x⋆,u⋆,d⋆,δ⋆)(x^\star,u^\star,d^\star,\delta^\star) therefore activates a successor constraint at the optimal certificate margin.

Proof. The first claim follows from Theorem 3.9. Lemma 3.2, applied on every attacker region, shows that an attacker minimiser can be chosen among the finite pairs (h,k)(h,k) in (24), and εν(b⋆,ρ⋆)=t⋆\varepsilon_\nu(b^\star,\rho^\star)=t^\star follows from optimality of the common hypograph variable t⋆t^\star. At (b⋆,ρ⋆)(b^\star,\rho^\star), the optimal certificate margin is finite and attained. At least one successor inequality must be active: if every successor inequality were strictly slack, then ε\varepsilon could be increased with the certificate controls unchanged, because ε\varepsilon does not enter the input constraints, contradicting optimality. Selecting any active inequality gives (25). ■

Remark 4.2 (Nonuniqueness and numerical recovery). The optimal parameters and active certificate tuple need not be unique. An active tuple need not minimise the margin after its associated control is reoptimised; consequently, activity alone does not identify a worst state and attack realisation.

Two orderings help interpret a computed value.

Corollary 4.3 (Monotonicity of the game value). Under Assumption 2.1, Vrci⋆≤Vci⋆V_{\mathrm{rci}}^\star\leq V_{\mathrm{ci}}^\star. Moreover, if R′⊆R\mathcal{R}'\subseteq\mathcal{R} is a nonempty polytope and Vν⋆(R′)V_\nu^\star(\mathcal{R}') denotes the value of (22) with R\mathcal{R} replaced by R′\mathcal{R}', then Vν⋆(R′)≥Vν⋆V_\nu^\star(\mathcal{R}')\geq V_\nu^\star for both ν∈{ci,rci}\nu\in\{\mathrm{ci},\mathrm{rci}\}.

Proof. The pointwise ordering εrci(b,ρ)≤εci(b,ρ)\varepsilon_{\mathrm{rci}}(b,\rho)\leq\varepsilon_{\mathrm{ci}}(b,\rho) is preserved by the minimisation over ρ\rho and then by the maximisation over bb. Shrinking the feasible set of the inner minimisation cannot decrease min⁡ρεν(b,ρ)\min_\rho\varepsilon_\nu(b,\rho) for a fixed bb, and the subsequent maximisation preserves the inequality. ■

Remark 4.4 (Stackelberg value and follower ties). The set Pν(b⋆)P_\nu(b^\star) of Definition 3.8 need not be a singleton, but the payoff is zero sum, so every selection from it returns the same value: the optimistic and pessimistic Stackelberg values coincide with (22) [7], no tie breaking rule is needed, and the nonuniqueness of ρ⋆\rho^\star is immaterial. This is why the bilevel problem [12] collapses in our case to the single level programmes of Proposition 3.5. The gap Vci⋆−Vrci⋆≥0V_{\mathrm{ci}}^\star-V_{\mathrm{rci}}^\star\geq0 is the value of observing (d,δ)(d,\delta) before committing to the control.

Safe set design subject to a guaranteed margin

Maximising only tt may return a small set. Let εˉ≥0\bar{\varepsilon}\geq0 be a prescribed margin and recall the hard state constraint set X\mathcal{X} from (3) and the guaranteed margin gνg_\nu from (21).

Corollary 4.5 (Affine safe set size design). Suppose Jsize(b)J_{\mathrm{size}}(b) is affine on every Bj\mathcal{B}_j and let κ≥0\kappa\geq0. The problem

max⁡b∈BJsize(b)+κgν(b)\max_{b\in\mathcal{B}}\quad J_{\mathrm{size}}(b)+\kappa g_\nu(b)
s.t.gν(b)≥εˉ,S(b)⊆X(38)\text{s.t.}\quad g_\nu(b)\geq\bar{\varepsilon},\qquad S(b)\subseteq\mathcal{X} \tag*{(38)}

is solved by the same finite family of ∣J∣|\mathcal{J}| LPs, in the sense that its value is the largest of their optimal values, infeasible regions being discarded. By fixing a defender validity region Bj\mathcal{B}_j, we obtain its LP by replacing the objective of (19) or (20) with Jsize(b)+κtJ_{\mathrm{size}}(b)+\kappa t and adding

t≥εˉ,HXvrj(b)≤hX,r=1,…,qj.(39)t\geq\bar{\varepsilon},\qquad H_Xv_r^j(b)\leq h_X,\quad r=1,\ldots,q_j. \tag*{(39)}

Proof. By fixing Bj\mathcal{B}_j, the first inequality in (27) certifies gν(b)≥εˉg_\nu(b)\geq\bar{\varepsilon}. The remaining inequalities are equivalent to S(b)⊆XS(b)\subseteq\mathcal{X} because they hold at every vertex of S(b)S(b). All added constraints and the regional objective are affine. If κ>0\kappa>0, optimality forces t=gν(b)t=g_\nu(b). If κ=0\kappa=0, tt need not equal gν(b)g_\nu(b); it serves only as the required safety certificate. Theorem 3.9 then applies without modification. ■

Unlike the margin game, (26) may be infeasible on a region, since εˉ\bar{\varepsilon} and the hard constraint act jointly; such a region is simply dropped from the comparison. If all ∣J∣|\mathcal{J}| LPs are infeasible, that is itself a certificate that (C,B)(\mathcal{C},\mathcal{B}) cannot deliver the requested margin, and B\mathcal{B}, the facet matrix C\mathcal{C}, or the admissible set R\mathcal{R} must be revised. The components of bb specify the offsets of the defining hyperplanes of S(b)S(b). Thus, Jsize(b)=ωTbJ_{\mathrm{size}}(b)=\omega^\mathsf{T}b, with ω>0\omega>0, provides a linear surrogate for set size, although increasing an offset associated with a redundant inequality need not enlarge the set. Alternatively, under the row normalisation and for b≥0b\geq0, maximising τ\tau subject to τ≤bi\tau\leq b_i for all ii maximises the radius of a norm ball centred at the origin and contained in S(b)S(b). Both formulations preserve the LP structure.

Numerical illustration: frequency regulation under additive attacks

Model and set parameterisations

We consider a simplified two-state model of frequency regulation, motivated by standard load-frequency models [13], with generator and battery actuation. The states represent frequency and mechanical power deviations, normalised by 0.20.2 Hz and 0.20.2 p.u., respectively. The two control inputs are the generator and battery commands, each normalised by 0.30.3 p.u., while dd represents a load deviation normalised by 0.050.05 p.u. At a sampling period of 0.20.2 s, we use the discrete-time model (1) with c=0c=0 and

A=[0.89750.7529−0.15060.5361],B=[0.31231.44160.5709−0.1249],(40)A=\begin{bmatrix}0.8975&0.7529\\-0.1506&0.5361\end{bmatrix},\qquad B=\begin{bmatrix}0.3123&1.4416\\0.5709&-0.1249\end{bmatrix}, \tag*{(40)}
E=[−0.24030.0208],E=\begin{bmatrix}-0.2403\\0.0208\end{bmatrix},

with U={u:∥u∥∞≤1}U=\{u:\lVert u\rVert_\infty\leq1\}, thus mU=4m_U=4, and D=conv⁡{−1,1}D=\operatorname{conv}\{-1,1\}, thus nD=2n_D=2. The operational envelope is

X={x:∥x∥∞≤1}\mathcal{X} = \{x : \lVert x\rVert_{\infty} \le1\}. The open loop matrix has eigenvalues 0.7168±0.2841j0.7168 \pm0.2841\mathrm{j}. The defender template uses the six unit norm facet directions C=[e1 e2 −e1 −e2 γ −γ]TC = [e_1\ e_2\ -e_1\ -e_2\ \gamma\ -\gamma]^{\mathsf{T}} with γ=(1,1)/2\gamma= (1,1)/\sqrt{2}, and the centrally symmetric offsets b=(a,c,a,c,β,β)b = (a,c,a,c,\beta,\beta) with

a,c∈[0.5,1.2],β∈[0.55,1.20].(41)a,c \in[0.5,1.2], \qquad\beta\in[0.55,1.20]. \tag*{(41)}

The attacker splits a budget Γ\Gamma between a frequency channel and a power channel injection, the first being the cheaper to corrupt. With CΔ=[e1 −e1 e2 −e2]TC_{\Delta} = [e_1\ -e_1\ e_2\ -e_2]^{\mathsf{T}} and ρ=(α1,α1,α2,α2)\rho= (\alpha_1,\alpha_1,\alpha_2,\alpha_2), R={ρ:α1,α2≥0, α1+2α2≤Γ}\mathcal{R} = \{\rho: \alpha_1,\alpha_2 \ge0,\ \alpha_1 + 2\alpha_2 \le\Gamma\} and Δ(ρ)=[−α1,α1]×[−α2,α2]\Delta(\rho) = [-\alpha_1,\alpha_1] \times[-\alpha_2,\alpha_2]. The extreme full-budget allocations act exclusively on the first or second component, yielding nonnested attack sets.

Validity decomposition and regional LPs

The diagonal facets are redundant exactly when β≥(a+c)/2\beta\ge(a+c)/\sqrt{2}, so (6) has ∣J∣=2|\mathcal{J}| = 2 with B1=B∩{2β≥a+c}\mathcal{B}_1 = \mathcal{B} \cap\{\sqrt{2}\beta\ge a+c\}, B2=B∩{2β≤a+c}\mathcal{B}_2 = \mathcal{B} \cap\{\sqrt{2}\beta\le a+c\}, and S(b)S(b) a box with q1=4q_1 = 4 vertices on B1\mathcal{B}_1 and a corner cut hexagon with q2=6q_2 = 6 vertices on B2\mathcal{B}_2, for instance v12(b)=(a,2β−a)v_1^2(b) = (a,\sqrt{2}\beta-a) and v22(b)=(2β−c,c)v_2^2(b) = (\sqrt{2}\beta-c,c); both maps are affine on their region, as in (7). The bounds (29) are such that neither region degenerates; on their common boundary, some generators coincide, while the affine representations remain valid. We incorporate S(b)⊆XS(b) \subseteq\mathcal{X} into B\mathcal{B} by appending to Gjb≤βjG_jb \le\beta_j the vertex inequalities HXvrj(b)≤hXH_{\mathcal{X}}v_r^j(b) \le h_{\mathcal{X}}, r=1,…,qjr = 1,\ldots,q_j, of (27); they are affine on Bj\mathcal{B}_j and, under (29), amount to a,c≤1a,c \le1. The attacker vertices are affine throughout R\mathcal{R}, so ∣H∣=1|\mathcal{H}| = 1, qΔ,1=4q_{\Delta,1} = 4 and vert⁡(R)={ρ0,ρ1,ρ2}={0,(Γ,Γ,0,0),(0,0,Γ2,Γ2)}\operatorname{vert}(\mathcal{R}) = \{\rho^0,\rho^1,\rho^2\} = \{0,(\Gamma,\Gamma,0,0),(0,0,\frac{\Gamma}{2},\frac{\Gamma}{2})\}, so K1=3K_1 = 3: the follower chooses from a continuum and Lemma 3.2 leaves three candidates. At Γ=0.6\Gamma= 0.6, after eliminating the template symmetry equalities, the LP of Proposition 3.5 on B2\mathcal{B}_2 has 292 variables and 1471 inequalities for controlled invariance and 40 and 967 for the robust pattern, matching Remark 3.6 with mB,2=31m_{\mathcal{B},2} = 31.

Stackelberg equilibrium and an active certificate tuple

At Γ=0.6\Gamma= 0.6, the regional LPs give Vci,1⋆=0.4786V_{ci,1}^{\star} = 0.4786, Vci,2⋆=0.6436V_{ci,2}^{\star} = 0.6436, and Vrci,1⋆=Vrci,2⋆=0.1597V_{rci,1}^{\star} = V_{rci,2}^{\star} = 0.1597. Thus, the optimal controlled invariant template is bci⋆=(1,1,1,1,1.0570,1.0570)b_{ci}^{\star} = (1,1,1,1,1.0570,1.0570), improving on the box region, whose margin is 26% lower. For robust controlled invariance, both regions attain the same value; one optimiser is brci⋆=(1,0.6247,1,0.6247,1.2,1.2)b_{rci}^{\star} = (1,0.6247,1,0.6247,1.2,1.2). Both sets lie in X\mathcal{X} and have positive margins, certifying the respective invariance properties. At ρ0,ρ1,ρ2\rho^0,\rho^1,\rho^2, the certificate margins are, respectively, (0.9299,0.6436,0.6436)(0.9299,0.6436,0.6436) for bci⋆b_{ci}^{\star} and (0.6039,0.1597,0.3039)(0.6039,0.1597,0.3039) for brci⋆b_{rci}^{\star}. Convexity and the strictly larger midpoint margin 0.76330.7633 on conv⁡{ρ1,ρ2}\operatorname{conv}\{\rho^1,\rho^2\} give Pci(bci⋆)={ρ1,ρ2}\mathcal{P}_{ci}(b_{ci}^{\star}) = \{\rho^1,\rho^2\}. For the robust pattern, the unique minimising vertex and concavity give Prci(brci⋆)={ρ1}\mathcal{P}_{rci}(b_{rci}^{\star}) = \{\rho^1\}. An active controlled-invariance certificate tuple at ρ⋆=ρ1\rho^{\star} = \rho^1 is x⋆=(1,0.4949)x^{\star} = (1,0.4949), u⋆=(−1,−1)u^{\star} = (-1,-1), d⋆=−1d^{\star} = -1, and δ⋆=(0.6,0)\delta^{\star} = (0.6,0). It gives x+=(0.3564,−0.3521)x^{+} = (0.3564,-0.3521), with x1+=1−Vci,1⋆x_1^{+} = 1 - V_{ci,1}^{\star}, as shown in Figure 1(a). These active tuples need not be worst realisations (Remark 4.2). The example demonstrates exact computation of optimal safe sets and attack-set best responses through a finite family of LPs: shape optimisation improves the margin when the disturbance and attack are observed, whereas a box is already optimal under the robust information pattern.

Figure 1. Stackelberg set game for the load frequency control model (28) at Γ=0.6\Gamma= 0.6, with S(b)⊆XS(b) \subseteq\mathcal{X}. (a) Equilibrium templates for the two information patterns within the envelope X\mathcal{X} (shaded, dashed), the contracted target SVci⋆(bci⋆)S_{\mathsf{V}_{ci}^{\star}}(b_{ci}^{\star}), and an active certificate transition of Proposition 4.1 (controlled invariance). (b) Margin along the full budget edge of R\mathcal{R}, from the whole budget on the frequency channel (λ=0\lambda= 0) to the whole budget on the power channel (λ=1\lambda= 1); the map is concave and its minimum is attained at a vertex, as Lemma 3.2 asserts.

References

  1. [1]V. Loechner and D. K. Wilde, “Parameterized polyhedra and their vertices,” International Journal of Parallel Programming, vol. 25, no. 6, pp. 525–549, 1997.DOI
  2. [2]F. Blanchini, “Set invariance in control,” Automatica, vol. 35, no. 11, pp. 1747–1767, 1999.DOI
  3. [3]N. Athanasopoulos, “Polytope shaping while preserving invariance,” in Proc. 61st IEEE Conf. Decision and Control (CDC), 2022, pp. 4996–5001.
  4. [4]P. Trodden, “A one-step approach to computing a polytopic robust positively invariant set,” IEEE Transactions on Automatic Control, vol. 61, no. 12, pp. 4100–4105, 2016.
  5. [5]M. E. Villanueva, M. A. Müller, and B. Houska, “Configuration-constrained tube MPC,” Automatica, vol. 163, Art. no. 111543, 2024.arxiv.org/abs/2208.12554
  6. [6]N. Athanasopoulos, E. Vlahakis, C. Townsend, and S. Olaru, “State dependent disturbances in computation of forward reachable sets and minimal invariant sets,” in Proc. 64th IEEE Conf. Decision and Control, 2025.
  7. [7]T. Başar and G. J. Olsder, Dynamic Noncooperative Game Theory, 2nd ed. Philadelphia, PA, USA: SIAM, 1999.
  8. [8]A. A. Cárdenas, S. Amin, and S. Sastry, “Secure control: Towards survivable cyber-physical systems,” in Proc. 28th Int. Conf. Distributed Computing Systems Workshops, 2008, pp. 495–500.DOI
  9. [9]H. Fawzi, P. Tabuada, and S. Diggavi, “Secure estimation and control for cyber-physical systems under adversarial attacks,” IEEE Trans. Autom. Control, vol. 59, no. 6, pp. 1454–1467, 2014.DOI
  10. [10]A. Teixeira, I. Shames, H. Sandberg, and K. H. Johansson, “A secure control framework for resource-limited adversaries,” Automatica, vol. 51, pp. 135–148, 2015.arxiv.org/abs/1212.0226
  11. [11]Q. Zhu and T. Başar, “Game-theoretic methods for robustness, security, and resilience of cyber-physical control systems,” IEEE Control Systems Magazine, vol. 35, no. 1, pp. 46–65, 2015.
  12. [12]A. Sinha, P. Malo, and K. Deb, “A review on bilevel optimization: From classical to evolutionary approaches and applications,” IEEE Trans. Evolutionary Computation, vol. 22, no. 2, pp. 276–295, 2018.arxiv.org/abs/1705.06270
  13. [13]H. Bevrani, Robust Power System Frequency Control, 2nd ed. Cham, Switzerland: Springer, 2014.

Paper details

vlnc:W_vnwedaez
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents