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 with unit ball and its dual . Vector inequalities hold componentwise. The vector of all ones is , and 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
where , is the defender control input, is the nondeterministic additive disturbance, and is the additive attack vector. The control and disturbance sets are the compact polytopes
Here has rows; state constraints are , with
The defender and attacker sets are and , with
The strategic variables parameterise sets instead of individual states or attack realisations. We note the admissible set can incorporate directly, or this specification can be handled explicitly in a design problem, as outlined in Section IV-B.
Assumption 2.1. The sets , , and are nonempty compact polytopes for each admissible pair , and the same holds for and .
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
Specifically, for each , we have
Each defender region admits the representation with . 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 , . We are interested in two notions of controlled invariance.
Definition 2.2. Consider (1) with , as in (2) and , as in (4)–(5). For fixed , the set is: (i) controlled invariant if ; (ii) robust controlled invariant if .
Consequently, for controlled invariance, the input depends on , while for robust controlled invariance the input depends on alone. In both cases, the selected parameters are known to the controller; the distinction concerns access to the realised disturbance and attack. Without changing , we normalise the nonzero rows of so that , rescaling the corresponding components of . For we define the safety margin set . For , ; for it is a facetwise outward relaxation. In general, for , thus a negative margin should not be read as a Minkowski enlargement.
Definition 2.3. In the setting of Definition 2.2, let . The signed invariance margins are
For fixed the feasible margin set is nonempty and bounded above, since compactness bounds ; closedness of and compactness of make both maxima attained. The sign of is an exact invariance test: if and only if satisfies . A negative margin implies invariance fails and quantifies the required relaxation; a nonnegative one certifies invariance and measures the available contraction. Being scalar, supplies the total ordering a zero sum payoff needs. We note the robust pattern admits fewer control choices, i.e., for any pair . 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 and . For any pair , the controlled invariance margin is the optimal value of
Respectively, the robust controlled invariance margin is the optimal value of
In (9)–(10), , , .
Proof. To show necessity, we apply the corresponding quantified condition to each vertex triple , precisely leading to (9) or (10). For sufficiency, we observe that any 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
where , is the defender control input, is the nondeterministic additive disturbance, and is the additive attack vector. The control and disturbance sets are the compact polytopes
Here has rows; state constraints are , with
The defender and attacker sets are and , with
The strategic variables parameterise sets instead of individual states or attack realisations. We note the admissible set can incorporate directly, or this specification can be handled explicitly in a design problem, as outlined in Section IV-B.
Assumption 2.1. The sets , , and are nonempty compact polytopes for each admissible pair , and the same holds for and .
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
Specifically, for each , we have
Each defender region admits the representation with . 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 , . We are interested in two notions of controlled invariance.
Definition 2.2. Consider (1) with , as in (2) and , as in (4)–(5). For fixed , the set is: (i) controlled invariant if ; (ii) robust controlled invariant if .
Consequently, for controlled invariance, the input depends on , while for robust controlled invariance the input depends on alone. In both cases, the selected parameters are known to the controller; the distinction concerns access to the realised disturbance and attack. Without changing , we normalise the nonzero rows of so that , rescaling the corresponding components of . For we define the safety margin set . For , ; for it is a facetwise outward relaxation. In general, for , thus a negative margin should not be read as a Minkowski enlargement.
Definition 2.3. In the setting of Definition 2.2, let . The signed invariance margins are
For fixed the feasible margin set is nonempty and bounded above, since compactness bounds ; closedness of and compactness of make both maxima attained. The sign of is an exact invariance test: if and only if satisfies . A negative margin implies invariance fails and quantifies the required relaxation; a nonnegative one certifies invariance and measures the available contraction. Being scalar, supplies the total ordering a zero sum payoff needs. We note the robust pattern admits fewer control choices, i.e., for any pair . 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 and . For any pair , the controlled invariance margin is the optimal value of
Respectively, the robust controlled invariance margin is the optimal value of
In (9)–(10), , , .
Proof. To show necessity, we apply the corresponding quantified condition to each vertex triple , precisely leading to (9) or (10). For sufficiency, we observe that any is a convex combination of the vertex triples, with coefficients $\alpha_r\beta_l\gamma_s formed as products of the barycentric coefficients of , and , whose marginals reproduce the three components. For controlled invariance, the same product coefficients combine the associated inputs . For robust controlled invariance, writing and selecting gives an admissible input that is independent of the subsequently realised . Convexity of , affinity of (1), and convexity of establish the corresponding quantified condition. ■
In the sequel, after fixing and , we replace the inequalities quantified by with finitely many inequalities, for every . Throughout, denotes the optimal value of the programme of Proposition 3.1 with the affine maps of . It coincides with for every , so parameters in overlapping domains receive the same value. The regional game value is
with the superscript indicating that the affine vertex maps (7)–(8) are fixed. Since is a compact polytope, its vertex set is finite, with . 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 , , and , the mapping is concave on . Moreover,
Proof. Take as a common lower bound on all attacker responses, so that for
For concavity, fix , take and , and let optimise the relevant LP of Proposition 3.1 at . Set , , and combine the controls in the same way, for controlled invariance and for the robust pattern; both lie in by convexity. Since is affine on , every constraint at is the convex combination of those at , thus it is satisfied, so , which is concavity. Writing as with , , concavity gives , so the minimum over is at a vertex. Substituting in (13) gives (12). ■
The 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 , 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
For fixed and , we define explicitly the two certificate feasible sets
Proposition 3.3 (Regional LP building block). Given any , the controlled invariance regional game is the optimal value of
The robust game is the optimal value of
Proof. By Lemma 3.2, it suffices to impose ; for fixed , Proposition 3.1 and (14)–(15) give
The feasible set is downward closed in : if is feasible, so is for every . Since the maximum in (18) is attained,
Stacking the equivalences yields (16) and (17). ■
Both programmes of Proposition 3.3 are LPs, since is affine in and is fixed. They provide the constraint blocks associated with one pair ; the complete game on requires all , as shown next.
Remark 3.4. In (17), may depend on but is shared across all and , following the order . Replacing every by one imposes instead , for a controller derived before , and possibly smaller margin.
Proposition 3.1 concerns a fixed pair , while Lemma 3.2 and Proposition 3.3 fix and cover every . In the game, however, must be safe against every , so we fix and account for all , setting .
Proposition 3.5 (One LP per defender region against all attacker regions). For each , is obtained from one LP containing the constraint blocks for all and . For controlled invariance, the LP is
For robust controlled invariance, it is
Proof. Since , for every we have . Lemma 3.2 reduces the inner minimum on every to its vertices. A common lower bound must therefore satisfy the certificate block associated with every pair . Stacking all blocks while retaining the same and gives (19) and (20). ■
Remark 3.6 (Size of the regional LPs). Both LPs are feasible: any and admissible controls satisfy the successor inequalities for sufficiently negative . Their optimal values are finite and attained because and are compact and the constraints are closed. With , and , the LP of Proposition 3.5 on has
the regional block of Proposition 3.3 being the single term . Each carries its own control under controlled invariance, whereas under robust controlled invariance each carries one control shared over . The counts grow with all extreme parameter choices from all attacker regions.
Remark 3.7. Let . Solving Proposition 3.3 separately for each returns , which permits a different optimiser for every attacker region, whereas the order of play requires one to face all of them,
the minimax inequality being possibly strict, since an optimiser for one attacker region may have a poor margin on another. The values are therefore insufficient to recover , and equality would require additional structure that is not assumed. Proposition 3.5 preserves the order by sharing and across all 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 and and must be optimised jointly. We next state the complete game and its solution concept.
Stackelberg set game and equilibrium
Let . In the Stackelberg set game the leader (defender) selects , the follower (attacker) observes and selects , and the payoff is maximised by the leader and minimised by the follower. The follower best response correspondence and the leader guaranteed margin are
A pair is a Stackelberg equilibrium of the game if and , and the associated Stackelberg value is .
The game is zero sum, so every returns the same payoff and the Stackelberg value is unambiguous,
Existence of an equilibrium is not assumed. It follows constructively from Theorem 3.9 and Proposition 4.1 below, which also return and one . 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
where and are the LP values in (19) and (20), respectively. Hence the complete Stackelberg set game is solved exactly by LPs, each corresponding to one safe set vertex region and containing all attack set vertex regions.
Proof. By the finite cover , . Proposition 3.5 shows that each 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 depends on the sets and , 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 , 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 and optimise its LP in Proposition 3.5. Then .
With
satisfies , so is a Stackelberg equilibrium per Definition 3.8, and . Resolving the certificate LP of Proposition 3.1 at , there is an active tuple with
where , , and for controlled invariance, for the robust pattern. The tuple 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 in (24), and follows from optimality of the common hypograph variable . At , the optimal certificate margin is finite and attained. At least one successor inequality must be active: if every successor inequality were strictly slack, then could be increased with the certificate controls unchanged, because 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, . Moreover, if is a nonempty polytope and denotes the value of (22) with replaced by , then for both .
Proof. The pointwise ordering is preserved by the minimisation over and then by the maximisation over . Shrinking the feasible set of the inner minimisation cannot decrease for a fixed , and the subsequent maximisation preserves the inequality. ■
Remark 4.4 (Stackelberg value and follower ties). The set 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 is immaterial. This is why the bilevel problem [12] collapses in our case to the single level programmes of Proposition 3.5. The gap is the value of observing before committing to the control.
Safe set design subject to a guaranteed margin
Maximising only may return a small set. Let be a prescribed margin and recall the hard state constraint set from (3) and the guaranteed margin from (21).
Corollary 4.5 (Affine safe set size design). Suppose is affine on every and let . The problem
is solved by the same finite family of LPs, in the sense that its value is the largest of their optimal values, infeasible regions being discarded. By fixing a defender validity region , we obtain its LP by replacing the objective of (19) or (20) with and adding
Proof. By fixing , the first inequality in (27) certifies . The remaining inequalities are equivalent to because they hold at every vertex of . All added constraints and the regional objective are affine. If , optimality forces . If , need not equal ; 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 and the hard constraint act jointly; such a region is simply dropped from the comparison. If all LPs are infeasible, that is itself a certificate that cannot deliver the requested margin, and , the facet matrix , or the admissible set must be revised. The components of specify the offsets of the defining hyperplanes of . Thus, , with , 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 , maximising subject to for all maximises the radius of a norm ball centred at the origin and contained in . 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 Hz and p.u., respectively. The two control inputs are the generator and battery commands, each normalised by p.u., while represents a load deviation normalised by p.u. At a sampling period of s, we use the discrete-time model (1) with and
with , thus , and , thus . The operational envelope is
. The open loop matrix has eigenvalues . The defender template uses the six unit norm facet directions with , and the centrally symmetric offsets with
The attacker splits a budget between a frequency channel and a power channel injection, the first being the cheaper to corrupt. With and , and . 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 , so (6) has with , , and a box with vertices on and a corner cut hexagon with vertices on , for instance and ; 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 into by appending to the vertex inequalities , , of (27); they are affine on and, under (29), amount to . The attacker vertices are affine throughout , so , and , so : the follower chooses from a continuum and Lemma 3.2 leaves three candidates. At , after eliminating the template symmetry equalities, the LP of Proposition 3.5 on has 292 variables and 1471 inequalities for controlled invariance and 40 and 967 for the robust pattern, matching Remark 3.6 with .
Stackelberg equilibrium and an active certificate tuple
At , the regional LPs give , , and . Thus, the optimal controlled invariant template is , improving on the box region, whose margin is 26% lower. For robust controlled invariance, both regions attain the same value; one optimiser is . Both sets lie in and have positive margins, certifying the respective invariance properties. At , the certificate margins are, respectively, for and for . Convexity and the strictly larger midpoint margin on give . For the robust pattern, the unique minimising vertex and concavity give . An active controlled-invariance certificate tuple at is , , , and . It gives , with , 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 , with . (a) Equilibrium templates for the two information patterns within the envelope (shaded, dashed), the contracted target , and an active certificate transition of Proposition 4.1 (controlled invariance). (b) Margin along the full budget edge of , from the whole budget on the frequency channel () to the whole budget on the power channel (); the map is concave and its minimum is attained at a vertex, as Lemma 3.2 asserts.
References
- [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]F. Blanchini, “Set invariance in control,” Automatica, vol. 35, no. 11, pp. 1747–1767, 1999.DOI
- [3]N. Athanasopoulos, “Polytope shaping while preserving invariance,” in Proc. 61st IEEE Conf. Decision and Control (CDC), 2022, pp. 4996–5001.
- [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]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]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]T. Başar and G. J. Olsder, Dynamic Noncooperative Game Theory, 2nd ed. Philadelphia, PA, USA: SIAM, 1999.
- [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]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]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]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]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]H. Bevrani, Robust Power System Frequency Control, 2nd ed. Cham, Switzerland: Springer, 2014.
