Secure Data Reconstruction: A Direct Data-Driven Approach Jiaqi Yan, Ivan Markovsky, John Lygeros Abstract This paper addresses the problem of secure data reconstruction for unknown systems, where data collected from the system are susceptible to malicious manipulation. We aim to recover the real trajectory without prior knowledge of the system model. To achieve this, a behavioral language is used to represent the system, describing it using input/output trajectories instead of state-space models. We consider two attack scenarios. In the first scenario, up to k k entries of the collected data are malicious. On the other hand, the second scenario assumes that at most k k channels from sensors or actuators can be compromised, implying that any data collected from these channels might be falsified. For both scenarios, we formulate the trajectory recovery problem as an optimization problem and introduce sufficient conditions to ensure successful recovery of the true data. Since finding exact solutions to these problems can be computationally inefficient, we further approximate them using an ℓ 1 \ell_{1} -norm and group Least Absolute Shrinkage and Selection Operator (LASSO). We demonstrate that under certain conditions, these approximation problems also find the true trajectory while maintaining low computation complexity. Finally, we extend the proposed algorithms to noisy data. By reconstructing the secure trajectory, this work serves as a safeguard mechanism for subsequent data-driven control methods. I Introduction The past decades have witnessed remarkable research interest in cyber-physical systems (CPSs). Application of these systems varies from aerospace, manufacturing, transportation, and power grids. Security stands as a top concern for CPS, since any failure or attack can lead to significant economic losses, or even pose threats to human lives [ 1 ] . Nowadays, the extensive use of communication units (e.g., sensors and actuators) makes the system more vulnerable than before, where an adversary can easily break a communication channel and tamper with the transmitted data. Researchers, therefore, have recognized the importance of implementing secure detection and control algorithms. Existing solutions typically rely on model-based approaches. One common strategy is detecting attacks by creating an observer based on the system model [ 2 , 3 ] , where both linear and nonlinear systems are considered . One estimates the process states using this observer, and makes a decision on possible misbehaviors by comparing these estimates with the received data. An application of this approach is bad data detection in power systems [ 4 ] . Instead of detecting and isolating malicious components, another line of research focuses on developing resilient algorithms which guarantee an acceptable performance even in the presence of false data. This is usually achieved by deploying additional nodes or channels to “compensate” for fault signals. For instance, [ 5 , 6 , 7 , 8 ] solve the problem of secure state estimation in linear systems . According to their results, the system must be at least 2k -sparse observable in order to tolerate k malicious sensors. This means that the removal of any 2k sensors should not compromise the system’s observability. Similarly, for the resilient cooperative control problem, a (2k+1) -robust graph is necessary to handle k malicious agents, where redundant communication channels should be added to each normal agent [ 9 , 10 ] . In these works, exact system models are integral to the algorithm design. However, deriving models from first principles can be challenging in practical scenarios. Often, only input/output trajectories collected from the system are available, which motivates the study of data-driven control. Typically, data-driven methods can be classified into indirect data-driven approaches, involving system identification followed by the model-based control, and direct data-driven approaches, where control policies are learned directly from data without identifying a model [ 11 , 12 , 13 ] . Here we aim to enhance the CPS resiliency using a direct data-driven approach. We investigate two potential attack scenarios. In the first scenario, up to k entries of the collected data are malicious. On the other hand, the second scenario assumes that at most k channels of sensors or actuators are compromised, meaning that any input/output data collected from these channels can be manipulated. Our objective is to reconstruct the true trajectory for both scenarios without identifying a parametric representation of the system. As shown in [ 14 , 15 ] , the behavioral approach is particularly suitable for solving direct data-driven problems and has advantages over classical model-based methods. The key result established in the behavioral setting that makes solution of the direct-data driven control problems possible is the so called fundamental lemma ( [ 16 ] ). In our paper, we build upon a more recent result from [ 17 ] , which extends the fundamental lemma by providing necessary and sufficient conditions—known as the generalized persistency of excitation condition—for establishing a nonparametric representation of the data-generating system (which is the unknown system under study), without requiring a predetermined input/output partitioning of the data [ 18 ] . Specifically, the nonparametric representation refers to an equivalent description of the system using input/output data, rather than the system matrices. The key assumption on the data requires prior knowledge of the true system’s complexity (number of inputs and order). The result is applicable for data consisting of multiple trajectories, uncontrollable systems, and various classes of nonlinear systems , see [ 19 , 20 , 21 , 22 , 23 ] . Note that the data used to construct the nonparametric representation is obtained offline . Building upon this nonparametric representation, we then perform online data reconstruction. That is, to detect whether the data received online is malicious. The contributions of this paper are two-fold : 1) In both the entry-attacked and channel-attacked scenarios, we formulate the trajectory recovery problem as optimization problems utilizing [ 17 , Corollary 21] . We introduce sufficient conditions on the Hankel matrix for performing the online data reconstruction that ensures recovery of the true trajectory . The conditions are demonstrated to be tight; violating them can result in unsuccessful recovery. 2) The proposed problems are known to be NP-hard. Finding exact solutions involves solving a combinatorial number of subproblems. To reduce the computational complexity, we approximate the problems by using the \ell_{1} -norm and group Least Absolute Shrinkage and Selection Operator (LASSO). This transformation renders the problems convex, enabling tractable solutions with low computational complexity. We further establish conditions under which these approximation problems also yield the true trajectory. Extension to the noisy data is finally developed. To the best of our knowledge, this is the first work to consider security for unknown systems by using the behavioral language. The motivation for “recovering” the true data is to ensure a safe trajectory required for the subsequent data-driven control. Without this, malicious data could lead to incorrect or even unsafe control actions. Therefore, our data recovery method acts as a safeguard for data-driven approaches, regardless of the specific learning or control algorithms employed. The rest of this paper is organized as follows. Section II introduces preliminaries on behavior language. Sections III and IV formulate the trajectory recovery problem in the entry-attacked and channel-attacked scenarios, respectively. We propose computation-efficient solutions in Section V , and verify their performance through numerical examples in Section VI . Finally, Section VII concludes the paper. II Preliminaries We use the behavioral language [ 24 , 13 ] . Let q be the number of variables, \mathbb{N} be the set of natural numbers, and (\mathbb{R}^{q})^{\mathbb{N}} be the set of functions from \mathbb{N} to \mathbb{R}^{q} . A system \mathscr{B} is defined as a set of trajectories, i.e., \mathscr{B}\subseteq(\mathbb{R}^{q})^{\mathbb{N}} . The system is linear if \mathscr{B} is a subspace, and is time-invariant if it is invariant to the action of the unit shift operator \sigma , defined as (\sigma w)(t)=w(t+1) . The class of linear time-invariant (LTI) systems with q variables is denoted by \mathscr{L}^{q} . If necessary, the variables w of \mathscr{B}\in\mathscr{L}^{q} can be partitioned into inputs u and outputs y , i.e., there is a permutation matrix \Pi , such that w=\Pi\left[\begin{smallmatrix}u\\ y\end{smallmatrix}\right] . An input/output partitioning is in general not unique; however, the number of inputs, denoted by \bm{m}(\mathscr{B}) , is independent of the partitioning and is therefore a property of the system \mathscr{B} . Moreover, we define \bm{p}(\mathscr{B})\triangleq q-\bm{m}(\mathscr{B}), which is the number of output channels. Other properties of an LTI system \mathscr{B} , used later on, are the order \bm{n}(\mathscr{B}) (dimension of a minimal state-space representation) and the lag \bm{\ell}(\mathscr{B}) (degree of a minimal kernel representation). We refer the readers to the recent overview and tutorial papers [ 14 , 15 ] for more details on the behavioral language. We denote by w|_{L} the restriction of w\in(\mathbb{R}^{q})^{\mathbb{N}} to the interval [1,L] , i.e., \big(w(1),\ldots,w(L)\big) and by \mathscr{B}|_{L} the restriction of \mathscr{B} to the interval [1,L] , i.e., \left.\mathscr{B}\right|_{L}\triangleq\left\{w|_{L}\mid w\in\right. \mathscr{B}\} . For an LTI system, \left.\mathscr{B}\right|_{L} is a subspace of \mathbb{R}^{qL} . For any vector v , v_{r} denotes the r -th entry of v . Let \mI=\{i_{1},\cdots,i_{s}\} be a set of indices with |\mI|=s . For v\in\mathbb{R}^{m} , we define v|_{\mI} as the subvector of v with indices in \mI , i.e., v|_{\mI}\triangleq[v_{i_{1}},\ldots,v_{{i}_{s}}]^{\top}\in\mathbb{R}^{s}. Similarly, for a matrix A\in\mathbb{R}^{m\times n} , A|_{\mI} is defined as the submatrix of A with row indices in {\mI} : A|_{\mI}\triangleq[A^{\top}_{{i}_{1}},\ldots,A^{\top}_{{i}_{s}}]^{\top}\in\mathbb{R}^{s\times n}, where A_{{i}_{r}} represents the {i}_{r} -th row of A . Furthermore, given a binary vector (i.e., a vector which entries are either 0 or 1 ), \idx(v) returns an index set containing the positions of 1 -entries. III Entry-Attacked Scenario We consider a discrete-time LTI system \mathscr{B}\in\mathscr{L}^{q} . Our focus lies on a scenario where the system is unknown, but input/output trajectories from the system are available, enabling the data-driven approach. This section assumes that the collected data is noiseless. Later in Section V-B , we show how to extend the results to noisy datasets. Consider a T -length trajectory w_{d}\in(\mathbb{R}^{q})^{T} of the system, i.e., w_{d}\in\mathscr{B}|_{T} . Let \mathscr{H}_{L}(w_{d}) denote the Hankel matrix formed by w_{d} with L block rows, where 1\leq L\leq T : \begin{split}\mathscr{H}_{L}(w_{d})&\triangleq\begin{bmatrix}w_{d}(1)&w_{d}(2)&\cdots&w_{d}(T-L+1)\\ w_{d}(2)&w_{d}(3)&\cdots&w_{d}(T-L+2)\\ \vdots&\vdots&&\vdots\\ w_{d}(L)&w_{d}(L+1)&\cdots&w_{d}(T)\end{bmatrix}\\ &\in\mathbb{R}^{qL\times(T-L+1)}.\end{split} We assume that w_{d} is attack-free. Otherwise, it is not possible to recover the trajectory since w_{d} encodes an understanding of the underlying system. In this paper, we will use the following result as a key solution technique [ 17 , Corollary 21] . Lemma 1 . Consider w_{d}\in\mathscr{B}|_{T} , where \mathscr{B}\in\mathscr{L}^{q} and L\geq\bm{\ell}(\mathscr{B}) . The following statements are equivalent: 1. Generalized persistent excitation condition holds 1 1 1 Prior knowledge of the true system complexity, such as the number of inputs and order, is needed for the generalized persistent excitation condition. However, this is not required in the methods proposed later in the paper. , namely, \rank\mathscr{H}_{L}\left(w_{d}\right)=\bm{m}(\mathscr{B})L+\bm{n}(\mathscr{B}). (1) 2. Any \bar{w}\in(\mathbb{R}^{q})^{L} is a trajectory of \mathscr{B} , that is, \bar{w}\in\mathscr{B}|_{L} , if and only if there exists a g\in\mathbb{R}^{T-L+1} such that \bar{w}=\mathscr{H}_{L}\left(w_{d}\right)g. (2) That is, \mathscr{B}|_{L}=\text{image }\mathscr{H}_{L}\left(w_{d}\right). Lemma 1 is related to the fundamental lemma [ 16 ] . However, it does not require an input/output partitioning of the variables nor controllability of the system \mathscr{B} . Instead of a condition on an input component of the trajectory (persistency of excitation of an input), it imposes a condition on the data w_{d} (generalized persistency of excitation). Finally, the conditions of Lemma 1 are necessary and sufficient while the ones of [ 16 ] are only sufficient [ 18 ] . III-A Entry-attacked model In the context of data-driven control, trajectories collected from the system directly influence controller design. Hence, ensuring reliability of the data is paramount. This paper thus focuses on the problem of secure trajectory reconstruction under data manipulation. Let \bar{w}\in(\mathbb{R}^{q})^{L} denote an L -length trajectory of the LTI system \mathscr{B}\in\mathscr{L}^{q} . When subjected to attacks, some entries of \bar{w} are tampered with. As a result, a manipulated data sequence w\in(\mathbb{R}^{q})^{L} is received. Our aim is to reconstruct the true signal \bar{w} from the received data w . In the entry-attacked model, we assume that the attacker can change these entries to arbitrary values, but can only compromise at most k entries. This is reasonable since the adversary usually has limited energy. Let \mathcal{C}\subseteq\{1,\ldots,qL\} denote the index set of malicious entries. Note that while the number k is assumed to be known a priori , the exact set \mathcal{C} is unknown. III-B A brute force algorithm To recover the real data, our goal is to identify a “legal” trajectory of the system that matches the received data except for k entries. This leads to the following optimization problem: \begin{split}\min_{\tilde{w},\mathcal{I}}\qquad&||w|_{\mI}-\tilde{w}|_{\mI}||_{2}\\ s.t.\qquad&|\mI|=qL-k,\\ &\tilde{w}\in\mB|_{L}.\end{split} (3) Using Lemma 1 , the above problem becomes \begin{split}\min_{\tilde{w},g,\mathcal{I}}\qquad&||w|_{\mI}-\tilde{w}|_{\mI}||_{2}\\ s.t.\qquad&|\mI|=qL-k,\\ &\tilde{w}=\mathscr{H}_{L}\left(w_{d}\right)g.\end{split} (4) Problem ( 4 ) is generally NP-hard, as it can be re-formulated as a mixed integer linear program (MILP). In Algorithm 1 , we present a brute force algorithm for solving the problem, where a combinatorial number of subproblems need to be solved to identify the index set \mI^{(i)} leading to the minimum. Specifically, there are \binom{qL}{k} possible sets of benign entries. That is, |\mathscr{I}|=\binom{qL}{k} , where {\color[rgb]{0,0,1}\mathscr{I}\triangleq\{\mathcal{I}^{(i)}|\mathcal{I}^{(i)}\subseteq[qL],|\mathcal{I}^{(i)}|=qL-k\}.} We consider all possible subproblems by iterating through every set \mathcal{I}^{(i)}\in\mathscr{I} . For each subproblem i , the algorithm aims to solve the equation 2 2 2 The notation w|_{\mI} for \mI being a set overloads the notation w|_{L} defined earlier in Section II for L being an integer. w|_{\mI^{(i)}}=\mathscr{H}_{L}(w_{d})|_{\mI^{(i)}}g. (5) If a solution g exists, Algorithm 1 terminates with the output \tilde{w}=\mathscr{H}_{L}\left(w_{d}\right)g. (6) By doing so, the algorithm identifies a trajectory that fits w while excluding k entries. Alternatively, if no solution is found for any i=1,\ldots,\binom{qL}{k} , Algorithm 1 finishes without producing a solution. The complexity of Algorithm 1 increases exponentially with the size of data and the number of malicious entries. In Section V , we will introduce a computationally efficient approximation for solving ( 4 ). Algorithm 1 Combinatorial algorithm for solving problem ( 4 ). 0: w_{d} , w , and k for i\in\{1,\ldots,\binom{qL}{k}\} do Select \mI^{(i)} with |\mI^{(i)}|=qL-k . if \rank\left[\mathscr{H}_{L}(w_{d})|_{\mI^{(i)}}\;\;w|_{\mI^{(i)}}\right]=\rank\mathscr{H}_{L}(w_{d})|_{\mI^{(i)}} then Find g^{(i)} by solving ( 5 ) and compute \tilde{w} by using ( 6 ). break end if end for Remark 1 . As defined, k is an upper bound on the number of malicious entries. In practice, we usually can only estimate this upper bound instead of knowing the exact number of malicious entries. Therefore, we design the secure algorithms based on the worst-case scenario, which involves removing exactly k entries in Algorithm 1 . Since the algorithm is designed to handle this worst case, it is also effective when fewer than k entries are malicious. It is true that when fewer than k entries are adversarial, we may end up discarding more data than necessary. To mitigate this, we can start with a smaller value \bar{k}||\mathscr{H}_{\text{F}}v||_{1}, (24) where \mathscr{H}_{\text{B}}\triangleq\mathscr{H}|_{[qL]\backslash\mathcal{C}},\;\mathscr{H}_{\text{F}}\triangleq\mathscr{H}|_{\mathcal{C}}. (25) Proof. Without loss of generality, let us assume \mH=\begin{bmatrix}\mathscr{H}_{\text{B}}\\ \mathscr{H}_{\text{F}}\end{bmatrix}. (26) Correspondingly, w is partitioned as w=\begin{bmatrix}w_{\text{B}}\\ w_{\text{F}}\end{bmatrix}=\begin{bmatrix}\bar{w}_{\text{B}}\\ w_{\text{F}}\end{bmatrix}, (27) where w_{\text{B}}\triangleq w|_{[qL]\backslash\mathcal{C}},\;w_{\text{F}}\triangleq w|_{\mathcal{C}} , and \bar{w}_{\text{B}}\triangleq\bar{w}|_{[qL]\backslash\mathcal{C}} . To ensure w^{*}=\bar{w} , it is sufficient to show that \bar{g} is the optimal solution of ( 22 ), i.e., g^{*}=\bar{g} , where \bar{g} generates the true trajectory as defined in ( 12 ). This holds if and only if for any v\neq 0 , ||w-\mathscr{H}(\bar{g}+v)||_{1}>||w-\mathscr{H}\bar{g}||_{1}. (28) Since \bar{w}_{\text{B}}=\mathscr{H}_{\text{B}}\bar{g} , the above inequality is equivalent to \left|\left|\begin{bmatrix}\mathscr{H}_{\text{B}}v\\ w_{\text{F}}-\mathscr{H}_{\text{F}}(\bar{g}+v)\end{bmatrix}\right|\right|_{1}>||w_{\text{F}}-\mathscr{H}_{\text{F}}\bar{g}||_{1}. (29) Or, equivalently, ||\mathscr{H}_{\text{B}}v||_{1}>||w_{\text{F}}-\mathscr{H}_{\text{F}}\bar{g}||_{1}-||w_{\text{F}}-\mathscr{H}_{\text{F}}(\bar{g}+v)||_{1}. (30) The above inequality follows under ( 24 ), which completes the proof. ∎ Remark 4 . The main difficulty in using Theorem 3 is to validate ( 24 ) over all nonzero v ’s. In this remark, we provide a way to verify the condition. Let us define the following epigraphs: \mathcal{E}(B)\triangleq\left\{v:||\mathscr{H}_{\text{B}}v||_{1}\leq 1\right\},\;\mathcal{E}(F)\triangleq\left\{v:||\mathscr{H}_{\text{F}}v||_{1}\leq 1\right\} We then propose the following lemma: Lemma 3 . If there exists \delta>0 such that \mathcal{E}(B)\subseteq(1-\delta)\mathcal{E}(F), (31) then ( 24 ) holds. Proof. Let us consider any v\neq 0 . Since ( 31 ) holds, there must exist \alpha\neq 0 and v_{0}=\alpha v such that v_{0}\in\mathcal{E}(F)\backslash\mathcal{E}(B) . That is, ||\mathscr{H}_{\text{B}}v_{0}||_{1}>1 and ||\mathscr{H}_{\text{F}}v_{0}||_{1}\leq 1 . Therefore, it follows ||\mathscr{H}_{\text{B}}v_{0}||_{1}>||\mathscr{H}_{\text{F}}v_{0}||_{1} . Then it is easy to check ||\mathscr{H}_{\text{B}}v||_{1}=\alpha||\mathscr{H}_{\text{B}}v_{0}||_{1}>\alpha||\mathscr{H}_{\text{F}}v_{0}||_{1}=||\mathscr{H}_{\text{F}}v||_{1} . ∎ Therefore, it is sufficient to verify ( 31 ). Since \mathcal{E}(B) and \mathcal{E}(F) are both convex polytopes [ 29 , Chapter 3] , we only need to check whether all the vertices of \mathcal{E}(B) lie in the interior of \mathcal{E}(F) . The vertices of \mathcal{E}(B) can be found by solving the equation ||\mathscr{H}_{\text{B}}\nu||_{1}=1 , which can be done using linear programming. If for every vertex \nu , ||\mathscr{H}_{\text{F}}\nu||_{1}\leq 1 holds, then ( 31 ) is verified. Alternatively, one can also solve the following optimization problem \begin{split}\max_{\nu}\quad&||\mathscr{H}_{\text{F}}\nu||_{1},\\ \text{s.t. }\quad&||\mathscr{H}_{\text{B}}\nu||_{1}=1.\end{split} If the optimal value of the above problem is less than 1 , we are also able to validate ( 31 ) and thus ( 24 ). Instead of ( 24 ), the following condition can also guarantee the effectiveness of ( 22 ). Condition 3 . \rank\mathscr{H}_{\text{B}}=\rank\mathscr{H} , where \mathscr{H}_{\text{B}} is defined in ( 25 ). That is, removing “malicious rows” does not harm the rank of \mathscr{H} . Note that if Condition 3 does not hold, the benign data itself is not persistently exciting and therefore cannot fully determine the true solution set. This gives the adversary some degree of freedom to arbitrarily modify the data without being detected. Under Condition 3 , there exists a matrix T such that \mathscr{H}_{\text{F}}=T\mathscr{H}_{\text{B}}. (32) Theorem 4 . Suppose that ( 1 ) is satisfied and Condition 3 holds. Problem ( 22 ) recovers the true trajectory. i.e., w^{*}=\bar{w} , if ||T||_{1}<1 . Proof. From ( 32 ), we have ||\mathscr{H}_{\text{F}}v||_{1}=||T\mathscr{H}_{\text{B}}v||_{1}\leq||T||_{1}||\mathscr{H}_{\text{B}}v||_{1}<||\mathscr{H}_{\text{B}}v||_{1} for any v\neq 0 . By using Theorem 3 , we finish the proof. ∎ In general, the matrix T that solves ( 32 ) is not unique. If there exists a matrix T among all possible solutions that satisfies ||T||_{1}<1 , then Theorem 4 holds. Note also that no prior knowledge on the number of either false entries or channels is required for solving ( 22 ), making it applicable to both entry-attacked and channel-attacked scenarios 3 3 3 In the channel-attacked scenario, instead of ( 25 ), we define \mathscr{H}_{\text{B}}\triangleq\mathscr{H}|_{[qL]\backslash\mathscr{C}^{q,L}(\mathcal{C})} and \mathscr{H}_{\text{F}}\triangleq\mathscr{H}|_{\mathscr{C}^{q,L}(\mathcal{C})} . All results remain valid. . Moreover, the channel-attacked scenario can also be approximated by using the idea of group LASSO [ 30 ] : \begin{split}\min_{g,\beta}\quad&\sum_{i=1}^{q}||\beta|_{\mathscr{C}_{i}^{q,L}}||_{2}\\ s.t.\quad&\beta=w-\mathscr{H}_{L}\left(w_{d}\right)g,\end{split} (33) where \mathscr{C}_{i}^{q,L} is defined in ( 19 ). We partition the entries of \beta into q groups based on \mathscr{C}_{i}^{q,L}, i=1,\cdots,q . By using ( 33 ), we require that for each \mathscr{C}_{i}^{q,L} , either all entries of \beta|_{\mathscr{C}_{i}^{q,L}} are zero or all of them are non-zero. Therefore, data collected from any channel is either entirely discarded or entirely maintained, which aligns with our assumption that the set of manipulated channels keeps constant over time. Remark 5 . Many algorithms are available in the literature to solve the l_{1} norm minimization problem ( 22 ) and the group LASSO problem ( 33 ), including coordinate descent, exact path-following, and block coordinate gradient descent methods [ 31 ] . The computational complexities of these algorithms are typically polynomial with respective to the number of channels, the size of the Hankel matrix, and the length of the trajectory. In contrast, brute-force algorithms show exponential complexity. Therefore, ( 22 ) and ( 33 ) significantly reduce the computation costs. V-B Extension to noisy data In the presence of noisy data, we propose an approximation solution by solving a bi-level optimization problem. 1. First, solving ( 22 ) yields the optimal solution g^{*} . 2. For each w_{i} , namely, the i -th entry of w , calculate the residual |w_{i}-\mathscr{H}|_{\{i\}}g^{*}| . Denote \mathcal{C}^{*} as the index set of the largest k residuals. 3. Let \mI^{*}\triangleq[qL]/\mathcal{C}^{*} . We solve the following least square problem to find the recovered trajectory \tilde{w} : \begin{split}\min_{g,\tilde{w}}\quad&||w|_{\mI^{*}}-\tilde{w}|_{\mI^{*}}||_{2}\\ s.t.\quad&\tilde{w}=\mathscr{H}_{L}\left(w_{d}\right)g.\end{split} (34) The above procedure finds the recovered trajectory when up to k entries of w are subject to manipulation. For the channel-attacked scenario, we can have a similar procedure by leveraging ( 33 ). The details are omitted in the interest of space. In Section VI , we will test the effectiveness of these approximations through numerical examples. VI Numerical Examples This section provides numerical examples to verify the theoretical results. The codes are available on Github . First, we consider the same example as in [ 32 ] , see Fig. 1 . The displacement of the masses m_{1},m_{2},m_{3} are denoted by d_{1},d_{2},d_{3} , respectively. A force u is applied on mass m_{1} . The displacements of masses m_{2} and m_{3} , as well as the velocity of mass m_{3} are measured. Define the state as x\triangleq[d_{1},\dot{d}_{1},d_{2},\dot{d}_{2},d_{3},\dot{d}_{3}]^{\top}. Using Newton’s laws of motion, a state-space representation of the system is established as \dot{x}=Ax+Bu,\quad y=Cx (35) where \begin{split}A&=\begin{bmatrix}0&1&0&0&0&0\\ -\frac{k_{1}}{m_{1}}&-\frac{b_{1}}{m_{1}}&0&0&0&0\\ 0&0&0&1&0&0\\ \frac{k_{2}}{m_{2}}&0&-\frac{k_{2}}{m_{2}}&-\frac{b_{2}}{m_{2}}&0&0\\ 0&0&0&0&0&1\\ 0&0&\frac{k_{3}}{m_{3}}&0&-\frac{k_{3}}{m_{3}}&-\frac{b_{3}}{m_{3}}\end{bmatrix},\\ B&=\begin{bmatrix}0&\frac{1}{m_{1}}&0&0&0&0\end{bmatrix}^{\top},\\ C&=\begin{bmatrix}0&0&1&0&0&0\\ 0&0&0&0&1&0\\ 0&0&0&0&0&1\end{bmatrix}.\end{split} The parameters in the model are k_{1}=2 N/m , m_{1}=1 kg, b_{1}=3 Ns/m, k_{2}=3 N/m, m_{2}=2 kg, b_{2}=4 Ns/m, k_{3}=1 N/m, m_{3}=10 kg, and b_{3}=2 Ns/m. We discretize the model with a sampling time T_{s}=1.3 s. In this example, the system \mathscr{B} is represented by a state-space model. We assume the system matrices are unknown, and only input/output data is collected. Specifically, \bm{m}(\mathscr{B})=1 and \bm{p}(\mathscr{B})=3 are the number of inputs and outputs, respectively. Fig. 1: Three interconnected mass spring damper model. We generate w_{d} with the length T=11 , where the inputs are random variables drawn from a Gaussian distribution \mathcal{N}(0,1) and verify that the generalized persistent condition is satisfied. The true trajectory is partitioned into a sequence of data segments with length L=3 . Moreover, the trajectory is contaminated by random noises drawn from \mathcal{N}(0,0.5) . Suppose that each segment can be manipulated by adversaries. We assume k=1 and consider two scenarios: 1. In the entry-attacked scenario, a single entry of each segment is modified at each step. 2. In the channel-attacked scenario, all data from the second output channel are manipulated. Condition 3 holds in this example, which can be easily verified offline since \mathscr{H}_{L}(w_{d}) is provided. During the online computation, we solve the bi-level optimization problem proposed in Section V-B by leveraging ( 22 ) and ( 33 ) respectively in the two scenarios, aiming to recover the real trajectory for each segment. As shown in Fig. 2 and Fig. 3 , both algorithms reconstruct the true trajectory in the presence of malicious behaviors and random noises. As compared with Fig. 2 , Fig. 3 yields worse performance since under the channel-attacked case, more data is manipulated. Note that in the figures, we only illustrate output trajectories at the first two dimensions, i.e., d_{2} and d_{3} . The third output ( \dot{d}_{3} ) and the input ( u ), although omitted, are also successfully recovered. Fig. 2: Trajectories under the entry-attacked model by using ( 22 ). Fig. 3: Trajectories under the channel-attacked model by using ( 33 ). VI-A Comparison to other solutions we have added a comparison to the brute-force algorithm proposed in this paper, namely Algorithm 1 . Furthermore, since there are few works in the literature that address the secure data reconstruction problem in unknown systems as we do, we also compare our method to a model-based state reconstruction algorithm from [Mao2022], where the system matrices are known. Notice that both Algorithm 1 and [Mao2022] work in a noise-free environment. To ensure a fair comparison, we also apply our proposed solution ( 22 ) under noise-free conditions. The results are given in in Fig. 4 , which validate that ( 22 ) indeed recovers the exact trajectory. On the other hand, in this example with 3 interconnected mass-spring-damper models, the computation times of Algorithm 1 and ( 22 ) are 155.80 ms and 14.64 ms, respectively. That means ( 22 ) significantly reduces the complexity. It is clear that this advantage will become more evident as the problem size or the number of malicious entries increases. Moreover, different from [Mao2022], it is important to note that our method does not rely on any prior model knowledge and is purely data-driven. (a) Trajectories by using Algorithm 1 . (b) Trajectories by using the model-based algorithm. (c) Trajectories by using ( 22 ). Fig. 4: Performance comparison among different algorithms. VI-B Computation times in large-scale systems To evaluate the computational complexity of the methods proposed in Section V , we scale up ( 35 ) to larger systems of n interconnected mass-spring-damper models, where n=\{3,10,20,30\} . Let the state be the displacement and velocity of each mass, the input be a force applied on mass m_{1} , and the output be the displacements of masses m_{i},i\in\{2,3,\cdots,n\} , as well as the velocity of m_{n} . The system dynamics can be obtained similarly by using Newton’s law, with the state, input, and output dimensions being 2n , 1 , and n , respectively. All computations are performed on a laptop with a 1.4GHz Intel(R) processor, and the optimization problems are solved using the CPLEX optimizer. We run each example for 50 times. The computation times are recorded as below. TABLE I: Computation time of ( 22 ) on systems with different size. Computation time (ms) No. interconnected models 3 10 20 30 Average Computation Time 4.24 5.34 7.92 14.12 Worst Computation Time 21.72 24.53 24.80 31.99 It is evident that the proposed approximate solutions scale well with respect to the problem size. Moreover, we show the performance in n=10 , where the first input channel and the second output channel are attacked simultaneously. The data recovery errors for all channels are shown in Figure 5 . It is clear that the data on each channel can be successfully recovered. Fig. 5: The average error of each channel. VI-C Performance on a quadruple-tank system To demonstrate the applicability of the proposed method across different systems, we further test ( 22 ) on a quadruple-tank system using the same parameters as [ 33 ] . The noise is modeled with a uniform distribution, and the second input channel is subjected to an attack. As shown in Fig. 6 , the proposed method also successfully recovers the true trajectory in this scenario. Fig. 6: Trajectories under the channel-attacked model in the quadruple-tank system. VII Conclusion This paper addresses the problem of trajectory reconstruction under malicious behaviors. The system is unknown, and we develop direct data-driven approaches without identifying the explicit model. Both entry-attacked and channel-attacked scenarios are investigated. With the behavioral language, we describe the system using trajectories and formulate the problem as optimization problems for both scenarios. Sufficient conditions are presented to guarantee successful data reconstruction. Moreover, we develop approximation solutions to mitigate computation costs and handle noisy data. We further demonstrate that under certain conditions, these approximation solutions also accurately yield the true trajectory. For the future works, it is possible to extend the results presented in the paper to nonlinear systems or time-varying systems. Note that the fundamental lemma has already been generalized to various classes of nonlinear systems, such as Hammerstein–Wiener systems [ 19 ] , second-order discrete Volterra systems [ 20 ] , flat nonlinear systems [ 21 ] , bilinear systems [ 23 ] , and time-varying systems [ 22 ] . These advancements may enable the achievement of CPS resiliency for more complex systems through direct data-driven methods.