{'fraction_non_alphanumeric': 0.04624827520578579, 'fraction_numerical': 0.013512870533377741, 'mean_word_length': 4.5529722589167765, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Poisoning Attacks Against Data-Driven Predictive Control

—Data-driven predictive control (DPC) is a feed- back control method for systems with unknown dynamics. It repeatedly optimizes a system’s future trajectories based on past input-output data. We develop a numerical method that computes poisoning attacks which inject additive perturbations to the output data to change the trajectories optimized by DPC. This method is based on implicitly differentiating the solution map of the trajectory optimization in DPC. We demonstrate that the resulting attacks can cause an output tracking error one order of magnitude higher than random perturbations in numerical experiments.


I. INTRODUCTION
Data-driven predictive control (DPC) is a feedback control method for systems with unknown dynamics [1], [2], [3]. It combines the idea of Willems' fundamental lemma and model predictive control: the former gives a parameterization of the system's future input-output trajectories using linear functions of the past input-output data [4], [5], [6], and the latter gives a feedback controller that repeatedly optimizes the system's future input-output trajectories [7], [8]. DPC has been successful for various systems, including quadrotors [9], power converters [10], as well as building heating, ventilation, and air conditioning [11].
DPC relies heavily on data. It is susceptible to adversarial data perturbations, or data poisoning attacks, which has attracted increasing attention in machine learning [12], [13], [14], [15]. On the other hand, it remains unclear how vulnerable DPC is against data poisoning attacks. The results in [16], [17] show that DPC is robust against zero-mean stochastic noise in data. These results do not extend to deterministic data poisoning attacks. Meanwhile, results on data poisoning attacks against state estimators [18], [19], [20], [21] and controllers based on virtual reference feedback [22], [23] do not consider DPC, or any trajectory-optimization-based controllers. To our best knowledge, data poisoning attacks against DPC have received little if any attention.
We formulate a data-poisoning attack problem in DPC, where an attacker computes bounded additive perturbations to the output data to change the trajectories optimized by DPC. We show that the computation of a poisoning attack is a bilevel optimization, where the lower level optimizes the trajectory in DPC, and the upper level optimizes the attack.
Furthermore, we develop an efficient numerical method to compute poisoning attacks against DPC by approximating the bilevel optimization using a single-level convex optimization. We construct this approximation in two steps. First, we transform the bilevel optimization into a single-level nonconvex optimization using the solution map of the lowerlevel trajectory optimization. Second, we approximate the single-level nonconvex optimization using a convex one by implicitly differentiating said solution map.
Finally, we demonstrate the effectiveness and efficiency of the proposed method in attacking DPC for a linear oscillating masses system and a nonlinear quadrotor system in PyBullet, a high-fidelity robotics simulator [24]. Our numerical experiments show that the performance of DPC is more sensitive to data-poisoning attacks than random noise. In particular, the poisoning attacks can cause an output tracking error one order of magnitude higher than those of random perturbations. Furthermore, the proposed method is more efficient in implicit differentiation than CVXPYlayers, a state-of-the-art toolbox for differentiating the solution map of a convex optimization [25]. In our experiments, the leastsquares problem solved in the proposed method-which is the main computational task in implicit differentiation-is about half the size as the one solved in CVXPYlayers.
Notation: We let R, R + , R ++ , and N denote the set of real, nonnegative real, positive real, and positive integer numbers, respectively. Given m, n ∈ N, we let R n and R m×n denote the set of n-dimensional real vectors and m × n real matrices, We let 1 n and I n denote the n-dimensional vector of all 1's and the n × n identity matrix, respectively. Given a square real matrix A ∈ R n×n , we let A , A −1 , and A − denote the transpose, the inverse, and the transpose of the inverse of matrix A, respectively. Given a symmetric and positive semidefinite matrix M ∈ R n×n and x ∈ R n , we let We say a closed set D ⊂ R n is a closed convex set if αx + (1 − α)y ∈ D for all x, y ∈ D and α ∈ [0, 1]. The projection of x ∈ R n onto a closed convex set D ⊂ R n is a function Π D : R n → D where Π D (x) := argmin x ∈D x − x .

PREDICTIVE CONTROL
We introduce the data poisoning attack problem in datadriven predictive control (DPC). We will first revisit the basics of DPC, then introduce a bilevel optimization that model of data poisoning attacks against DPC.

A. Data-driven predictive control
We will briefly review the basics of data-driven predictive control, a control law for unknown dynamical systems based on data and optimization.
1) Input and output trajectories: Consider a discrete time dynamical system with n u inputs and n y outputs. The system's input and output at time j ∈ N are denoted by u j ∈ R nu and y j ∈ R ny , respectively.
At each sampling time k, DPC requires the knowledge of the following input-output trajectories generated by the system, denoted by {u k−σ , . . . , u k−1 } and {y k−σ , . . . y k−1 }, where σ ∈ N is the upper bound of the lag of the system [1]. Intuitively, σ is the number of input-output pairs needed to pinpoint the state of the system. In addition, DPC also requires the knowledge of the input Hankel matrix U ∈ R ( +σ)nu×ng and output Hankel matrix Y ∈ R ( +σ)ny×ng , where ∈ N is the planning horizon in DPC, and n g ∈ N is determined by the amount of offline data. Matrices U and Y are constructed from the offline input and offline output data, respectively. See [5], [6] for a detailed discussion on constructing Hankel matrices using offline input-output data.
2) Data-driven trajectory optimization: We now introduce the trajectory optimization problem used in data-driven predictive control. To this end, we first introduce the following notation: At each discrete time k ∈ N, the data-driven predictive controller computes a length-future input and output trajectory of the system-denoted by u := [ u k u k+1 ···u k+ −1 ] and y := [ y k y k+1 ···y k+ −1 ] , respectively-by solving the following optimization problem: minimize u,y,g where matrix Q ∈ R nu× nu and matrix R ∈ R ny× ny are both symmetric and positive semidefinite; λ g , λ s ∈ R + are regularization weights; M : is a weighting matrix inspired by system identification [3]; set U ⊂ R nu and set Y ⊂ R ny are closed and convex, defining the feasible set of input and output trajectories, respectively.

B. Poisoning attacks against data-driven predictive control
We consider a scenario where the most recent online output measurements in optimization (2) are corrupted by bounded additive perturbations designed by a malicious attacker. To this end, we start with the following variation of optimization (2): minimize u,y,g where p ∈ R σny is an attacking perturbation. Notice that optimization (2) is a special case of optimization (3) if p = 0 σny . In other words, optimization (3) is a generalization of optimization (2) where the value of y ini in optimization (2) is corrupted by perturbation p.
We now introduce the poisoning attack problem against data-driven predictive control, where an attacker seeks the best bounded perturbation p such that the optimal input trajectory in optimization (3) minimizes a performance function chosen by the attacker. We summarize the definition of this poisoning attack problem as follows.
Definition 1 (Poisoning attack problem). Given optimization (3), a continuously differentiable cost function ψ : R nu → R that evaluates the performance of the attacked trajectory, and a closed convex set P ⊂ R σny for admissible attacking perturbations, the poisoning attack problem seeks the optimal perturbation vector p ∈ P in the following bilevel optimization problem: The bilevel optimization problem in (4) is computationally challenging to solve. In particular, solving optimization (4) is equivalent to solving a mixed integer optimization-which is NP hard-where the number of mixed integer variables equals the number of inequality constraints in optimization (3). A typical solution method applies a branch-andbound procedure to the Karush-Kuhn-Tucker conditions of optimization (3). The computation time of such an procedure becomes quickly intractable as the problem sizes increases. We refer the interested readers to [26] for details on bilevel optimization.
At first glance, the daunting complexity of solving bilevel optimization (4) renders any real-time poisoning attacks against DPC impossible. However, one can compute an approximate solution for optimization (4) by solving convex optimization problems in real time, as we will show.
III. DATA POISONING ATTACKS VIA IMPLICIT DIFFERENTIATION We introduce an efficient numerical method to approximately solve the bilevel optimization problem in (4). Our method is based on the implicit function theorem [27, Thm. 1B.1] and a novel form of optimality conditions based on the Minty parameterization theorem [28,Prop. 23.22].
To simplify our notation in this section, we will first rewrite trajectory optimization (3) in a compact form. To this end, we introduce the following notation: m = (n u + n y ) + σn u , n = (n u + n y ) + n g , where P is the block diagonal matrix obtained by aligning R Q, 2λ g M M + 2λ s Y p Y p along its diagonal.
With the above notation, we can rewrite optimization (3) in the following form: Next, we will work with the compact notation in (6), rather than (3); we remind the readers again that the two are exactly equivalent due to (5).
Throughout, we will make the following assumption on optimization (6). Assumption 1. Let L(z, w) := 1 2 z P z +q z +w (Hz −b) for all z ∈ R n and w ∈ R m . There exists z ∈ R n and w ∈ R m such that Under mild constraint qualification conditions on optimization (6) [29, Cor. 28.3.1], Assumption (1) holds if and only if there exists an optimal solution for optimization (6).
We are interested in how will perturbation vector p affect the optimizers of optimization (6). To facilitate our further discussion, we introduce the the following notion of a solution map and its localizations.  (7) hold.}. We say solution map S has a single-valued localization around p if there exists a functionS such thatS(p) ∈ S(p) for all p in a neighborhood of p.
In the following, we will discuss the differentiability properties of solution map S and its localizations.

A. Optimality conditions as nonlinear equations
The implicit function theorem provides a characterization of the Jacobian of the solution maps of nonlinear equations [27, Thm. 1B.1]. On the first look, the implicit function theorem seems not applicable to the solution map S in Definition 2, since the latter is defined by an optimization problem rather than nonlinear equations. However, the following proposition shows that the optimality conditions in (9b) are actually equivalent to a set of nonlinear equations, laying the groundwork of applying the implicit function theorem to the solution map S.
for all z ∈ R n and w ∈ R m . Then the conditions in (7) are equivalent to the following conditions: Proof. First, the conditions in (7) are equivalent to the following [29,Thm. 27.4]: where N D (z )is the normal cone of set D at z . Next, since the set D is nonempty, closed, and convex, N D is a maximal monotone operator [28,Ex. 20.26]. The rest of the proof follows directly from the Minty parameterization theorem for maximal monotone operators [28,Prop. 23.22].
Lemma 1 shows that the optimizers in (7) are the fixed-points of the proportional integral projected gradient method, a first-order primal-dual conic optimization method that combines gradient descent with proportional-integral feedback [30], [31], [32].
Remark 1. Unlike the results in [33], [25], the optimality conditions in Lemma 1 contain less variables. The reason is because the optimality conditions considered in [33], [25] are based on homogeneous self-dual embedding (HSDE), which requires extra auxiliary variables, such as the dual variables for any inequality constraints.

B. Implicit differentiation through optimality conditions
Equipped with Lemma 1, we are ready to present the differentiability properties of the solution map in Definition 2 as follows.
Proposition 1 (Implicit function theorem). Consider the solution mapping S in Definition 2. Suppose Assumption 1 holds and In addition, suppose function Π D is continuously differentiable within a neighborhood of z + . Let If matrix J is nonsingular, the solution map S has a singlevalued localizationS. Within a neighborhood of p, functioñ S is continuously differentiable with its Jacobian satisfying: Proof. Our proof is based on the implicit function theorem [27,Thm. 1B. 1]. To use this theorem, first we need to consider the nonlinear equations F (ξ, p) = 0 m+n in (8) and the Jacobian ∂ ξ F (ξ, p) and ∂ p F (ξ, p). Using the chain rule we can show that ∂ ξ F (ξ, p) = J and ∂ p F (ξ, p) = K, where J and K are given in (11). The rest of the proof is a direct application of the implicit function theorem [27, Thm. 1B. 1].
Remark 2. Proposition 1 assumes the local differentiability of function Π D . Such an assumption holds almost everywhere if set U and Y are defined by elementwise upper and lower bounds, in which case set D is the Cartesian products of intervals, in which case Π D is a piecewise-linear function whose Jacobian is well-defined almost everywhere [34, Thm. 3.3.14].

C. Poisoning attacks via implicit differentiation
We now introduce the approximate poisoning attack problem, where we approximate the bilevel optimization in (4) via linearization and the implicit differentiation.
As a start, we observe that, due to Lemma 1, the bilevel optimization (4) is equivalent to the following problem: where T = I nu 0 nu×(m+n− nu) , and the solution map is given by Definition 2. In other words, the bilevel optimization in (4) is equivalent to a single-level optimization. Second, suppose that the assumptions in Proposition 1 hold when p = 0 σny . Then, there exists unique ξ : whereS is the single-valued localization of S around 0 σny . Furthermore, by combining the chain rule with Proposition 1, we can show that the following approximation for all p ≈ 0 σny : where matrix J and K are given by (11) with In other words, we let p = 0 σny in (5). By substituting the above linear approximation into optimization (13), we obtain the following approximate poisoning attack problem: where ∇ψ(T ξ ) := (∂ψ(T ξ )) . Finally, since matrix J can be singular-or at least close to being singular-we approximate the matrix inverse in (17) with the corresponding Moore-Penrose inverse; such an approximation requires solving a least-squares problem.
Algorithm 1 provides an efficient approximate solution to the poisoning attack problem in Definition 1. In particular, instead of solving the bilevel optimization problem in (4)which is NP hard-one can implement Algorithm 1. The
latter only requires solving the convex trajectory optimization problem in (6), a least-squares problem, and the minimization of a linear function over set P. Furthermore, Proposition 1 ensures that, under certain local differentiability and nonsingularity assumptions, Algorithm 1 gives the optimal solution of a linear approximation of the bilevel optimization in (4).

IV. NUMERICAL EXPERIMENTS
We demonstrate the effectiveness of the perturbations computed by Algorithm 1 via numerical experiments. We will consider attacking DPC for two different dynamical systems: a linear oscillating masses system, a popular benchmark system in optimal control [31], [32], and a nonlinear quadrotor dynamics in PyBullet, a high-fidelity robotics simulator [24].

A. DPC trajectory optimization setup
Furthermore, based on the observations made in DPC literature [9], [3], we choose n g = 500, σ = 6, = 25, λ s = 10 6 , and λ g = 100 in optimization (3). Throughout we solve optimization (3) using ECOS [35] with these parameters. We consider the following two systems. a) Oscillating masses system: We consider the following oscillating-masses system: , exp denotes the matrix exponential, and ∆ = 0.1 is the sampling time period. This system has n u = 2 and n y = 4, and describes the dynamics of two unit masses connected by springs with unit spring constants; see Fig. 1 for an illustration. When solving optimization (3) with this system, we let Q = 10I 4 , R = I 2 , andŷ denote the stationary point with positive unit displacement (see Fig. 3 for an illustration). In addition, we choose U and Y in (3)  b) PyBullet quadrotor system: We also consider the nonlinear quadrotor system in PyBullet [24]. This system does not have an explicit description based on difference or differential equations. Instead, it is a black-box system composed of pre-tuned PID controllers and 6-degree-of-freedom (6DoF) quadrotor dynamics; see Fig. 2 for an illustration. The input of the system is a 3-dimensional velocity command vector, the output of the system is a 6-dimensional vector containing the position and attitude angles of the quadrotor. Both input and output are measured at every 0.04 second. When solving optimization (3) with this system, we let Q = blkdiag(10I 3 , 0 3×3 )-i.e., positive weights on position outputs, zero weights on attitude outputs-and R = I 3 . We let y denote a circular trajectory in the xy-plane with radius 0.3; see Fig. 4 for an illustration. In addition, we choose U and Y in (3)

B. Poisoning attacks setup
We construct the poisoning attacks by making the following choices in optimization (4). We let whereũ is the attacker's desired input trajectory, and ρ ∈ R + is the ratio between the norm of the attacking perturbation and the output measurements. In other words, the attacker aims to push the input trajectory computed by DPC towards u by adding a perturbation to the output data, where the perturbation-to-data ratio is upper bounded by ρ. For the oscillating masses system, we chooseũ to be sinusoidal signals with unit amplitude and unit angular frequency; for the PyBullet quadrotor system, we chooseũ to be a velocity command in the positive y direction.

C. Numerical results
We demonstrate the output tracking error-the difference between the system's output trajectory and the reference trajectory-of the oscillating masses system and PyBullet quadrotor system under different poisoning attacks in Fig. 3 and Fig. 4, respectively. Here we only compare the output tracking error sine the inputs are tightly bounded and has less weights in the objective function of DPC. These trajectories are simulated using the input optimized by solving (3) every 10 steps with attacks added to output data y ini . As an benchmark in numerical experiments, we also consider random perturbation as p rand = (ρ y ini / v )v where each element in v ∈ R σny is sampled independently from the standard Gaussian distribution. From these results, we can observe that: 1) compared with the the linear oscillating masses, DPC is more sensitive to perturbation when applied to the nonlinear PyBullet quadrotor system, and 2) compared with random perturbations, the perturbations computed by Algorithm 1 are more effective, and increase the tracking error by more than ten times than that of random perturbations when applied to the PyBullet quadrotor system.
We also compare the efficiency of the implicit differentiation step used in ALgorithm 1 against off-the-shelf software CVXPY layer [25] in terms of the dimension of the least squares problem they solve, which are summarized in Tab. I. These results show that, since we do not rely on homogeneous self-dual embedding, the size of leastsquares problem we solve in Algorithm 1-which equals 2 (n u + n y ) + σn u + n g , i.e., the number of equations in (8))-is less than half the size of the one solved in CVXPYlayers, which is around 5 (n u +n y )+σn u +2n g , i.e., the size of the homogeneous self-dual embedding (HSDE) for optimization (3) 1 .

V. CONCLUSION
We study the poisoning attack problem in DPC. By implicitly differentiating the optimality conditions of the trajectory optimization in DPC, we develop an efficient numerical  method to compute the data poisoning attacks. Our numerical experiments show that the performance of DPC is more sensitive to poisoning attacks than random noise.
However, the current work is limited to the case where the DPC parameters-such as the regularization weight-is known exactly by the attacker. For future work, we plan to address this limitation by considering partial knowledge of these parameters, and poisoning attacks against other datadriven control methods.