Learning of Dynamical Systems under Adversarial Attacks - Null Space Property Perspective Han Feng Baturalp Yalcin and Javad Lavaei

2025-04-29 0 0 317.09KB 8 页 10玖币

侵权投诉

Learning of Dynamical Systems under Adversarial Attacks - Null Space

Property Perspective

Han Feng, Baturalp Yalcin, and Javad Lavaei

Abstract— We study the identiﬁcation of a linear time-

invariant dynamical system affected by large-and-sparse dis-

turbances modeling adversarial attacks or faults. Under the

assumption that the states are measurable, we develop necessary

and sufﬁcient conditions for the recovery of the system matrices

by solving a constrained lasso-type optimization problem. In

addition, we provide an upper bound on the estimation error

whenever the disturbance sequence is a combination of small

noise values and large adversarial values. Our results depend on

the null space property that has been widely used in the lasso lit-

erature, and we investigate under what conditions this property

holds for linear time-invariant dynamical systems. Lastly, we

further study the conditions for a speciﬁc probabilistic model

and support the results with numerical experiments.

I. INTRODUCTION

The identiﬁcation of linear time-invariant (LTI) systems

is a classic problem in control theory that has been studied

extensively. Despite the long history of this problem and

its application in a wide range of real-world systems, the

non-asymptotic analysis of the system identiﬁcation problem

has gained popularity in recent years, which targets the

sample complexity of the problem [

], [

]. With the growing

popularity of safety-critical applications, such as autonomous

driving and unmanned aerial vehicles, the design of a system

identiﬁcation framework that is robust against adversarial

attacks is crucial [3].

In this paper, we consider LTI systems for which the states

are under a sequence of unknown disturbances, some of

which take small values modeling noise and the remaining

ones take strategic values due to adversarial attacks or

faults in the system. We study the lasso-based optimization

problem recently proposed in [

]. It can recover the exact

system dynamics uniquely whenever adversarial attacks occur

intermittently with enough time separation. In [

], some

adversarial attacks that do not inﬂuence the estimation

are studied, whereas this paper improves those results by

providing a necessary and sufﬁcient condition for recovery

as well as non-asymptotic bounds on the error. Our approach

is based on deﬁning a null space property that is analogous

to the null space property condition for the lasso problem

[5], which is required to guarantee the exact recovery.

The robustness analysis of estimators has a long history,

dating back to the seminal paper [

]. It is known that a

small disturbance on the estimation problem, such as the

perturbation of a data point, could lead to signiﬁcant changes

in the outcome of the estimator. This has led to a major effort

This work was supported by grants from ARO, AFOSR, ONR, and NSF.

The authors are with the University of California, Berkeley. E-mail:

{han_feng, byalcin, lavaei}@berkeley.edu

on the robustiﬁcation estimators via regularizers. The works

[

] and [

] have found a strong relationship between the

robust estimation and regularization in regression problems

by showing the equivalence of these two problems.

The recent papers [

] and [

] on robust estimation of

linear measurement models have considered a framework

with two types of noise: small measurement noise and

large intermittent noise. They have developed necessary and

sufﬁcient conditions for the exact recovery when a column-

wise summable norm is used to minimize the error. We focus

on this type of norm in this paper, which will be deﬁned as

the sum of

norms of the columns of a matrix. Nevertheless,

our analysis is for the more challenging problem of system

identiﬁcation where the parameters are correlated over time.

Our results indirectly provide a guideline on how to design

an effective input sequence to learn system dynamics faster.

The recent papers [

] and [

] on system identiﬁcation

have studied the problem of learning a sparse and structured

state-space model, and provided bounds on the required

sample size, i.e., sample complexity bounds. However, none

of the aforementioned works are applicable to adversarial

attacks since their noise/disturbance model is Gaussian. The

more recent work [

] has utilized a conic relaxation, which

signiﬁcantly increases the problem dimension and is not

directly applicable to dynamical systems. It estimates how

many erroneous measurements or adversarial attacks can

be handled by the estimator without causing a nonzero

estimation error. There are some other works in the literature

that provide non-asymptotic error bounds for the linear

system identiﬁcation problem when the ordinary least-squares

estimation method and Kalmon-Ho algorithm are used [14],

[

]. However, these methods are not particularly efﬁcient

for robust estimation whenever the data is corrupted in an

adversarial way. Membership estimators are also utilized

to show a consistent estimation of linear systems [

Unfortunately, they do not provide non-asymptotic bounds.

The work [

] has studied the scenario where the attack is

executed on the outputs rather than the states. Unlike the

attack on the outputs, the effect of the attack on the states

propagates over time. Lastly, some other related works on

robust estimation are resilient state estimation [

], [

] and

Byzantine fault tolerance [20], [21].

One could place the system identiﬁcation problem into the

broader context of robust regression to gain some valuable

insight on robust estimation. It is well-known that least-

squares methods are not robust to outliers. The work [

]

has studied the identiﬁcation of outliers in linear regression.

It is shown that a non-convex loss function outperforms the

arXiv:2210.01421v2 [eess.SY] 5 Oct 2022

regularization of the least-squares function. Nevertheless,

it is not always justiﬁable to solve large-scale non-convex

problems instead of convex ones unless the landscape of the

non-convex optimization problem can be shown to be benign

(e.g., it does not have a spurious solution). Nonetheless, this

is problem speciﬁc and not understood thoroughly [

], [

Another mainly used estimator for sparse estimation is the

hard thresholding estimator. The work [

] has proposed

an iterative scheme based on this estimator and analyzed

it on regression with sparse disturbances. There have been

several other works on robust estimation and training [

[

], [

]. The major difference between those works and

the system identiﬁcation is that the states or the training

data are not independent over time. Hence, they cannot

be re-ordered, which makes it challenging to exploit the

existing results in robust statistics. A possible solution to this

is resetting the system and using the last available data point

from each trajectory. However, this is not a feasible approach

for common real-life applications due to its complexity. Also,

it is often desired to identify the system in an online fashion

to beneﬁt from the available data, but it is not well understood

how this can be achieved for robust estimation.

In Section II, we introduce the main notations used

in the paper. Section III considers a particular type of

minimization problem and formulates the problem. In

Section IV, we derive sufﬁcient conditions for exact recovery

in ﬁnite time when we have exact measurements of the states

that are inﬂuenced by the adversarial attacks. The noisy case

is studied in Section V, where we provide an error bound

on the estimation error based on the noise intensity. The

conditions are based on the null space property (NSP), which

is hard to verify directly. We derive sufﬁcient conditions for

NSP in Section VI and then show in Section VII that NSP

holds for a particular attack model where the input is Gaussian

and the adversary injects disturbances intermittently with a

ﬁxed policy based on the states and input measurements. The

proofs are provided in the appendix.

II. NOTATIONS

For a given matrix

, the

-th largest singular value of

is denoted by

σi(Z)

, and the minimal and maximum singular

values of

are shown by

σmin(Z)

and

σmax(Z)

, respectively.

For a matrix

kZkF

denotes its Frobenius norm and for a

vector

kzk2

denotes its

norm.

Z0

and

Z0

denote a

square symmetric matrix

that is positive deﬁnite and positive

semideﬁnite, respectively. The function

tr(·)

stands for the

trace of a square matrix. The

n×n

identity matrix is denoted

. The Minkowski sum of two sets

and

is denoted

E⊕F={e+f:e∈E,f∈F}

. The sum with the inverse

of the set is denoted by

EF={e−f:e∈E,f∈F}

. For

two vectors

and

hv,wi

is the inner product between those

vectors in their respective vector space.

P(·)

and

E[·]

denote

the probability of an event and the expectation of a random

variable. A Gaussian random variable

with mean

and

covariance matrix

is written as

X∼N(µ,Σ)

|S|

shows the

cardinality of a given set S.

III. PROBLEM FORMULATION

Consider an LTI dynamical system over the time horizon

[0,T]:

xt+1=¯

Axt+¯

But+¯

dt,t=0,1,...,T−1,

where

A∈Rn×n

and

B∈Rn×m

are unknown matrices in the

state-space model to be estimated and

’s are unknown

disturbances. Throughout the paper, the bar over each

parameter of interest (such as

) indicates the unknown

ground truth. The goal is to ﬁnd the matrices

and

from the state measurements

x0,...,xT∈Rn

and input data

u0,...,uT−1∈Rm

. The disturbances

d0,..., ¯

dT−1

model both

noise and anomalies in the system, such as attacks or

actuator’s faults. Without any assumptions on the disturbance,

the identiﬁcation problem is not well-deﬁned due to the

impossibility of separating

Axt+¯

But

from the disturbance

. For instance, if

dt=A0xt+B0ut

for some matrices

and

, then the system evolves as if the system matrices are

(¯

A+A0,¯

B+B0)

and the disturbance is zero, which makes the

identiﬁcation problem have non-unique solutions. We will

make certain sparsity assumptions on the disturbance in the

noiseless case, and generalize the result to the noisy case.

To formulate the problem, we introduce the matrix notation

X= [x0,...,xT−1]

U= [u0,...,uT−1]

, and

D= [d0,...,dT−1]

The last state

appears in our optimization problem, but it is

not a column in the matrix notation. The attack

is assumed

to be restricted to a set

D⊆Rn×T

. The set

captures the

user’s belief of possible times of attack and their values.

Deﬁne the sum of norm error

kDk2,col :=∑ikdik2

, where

the index is over the columns of

. The (column-wise) support

is deﬁned as

supp(D) = {i∈ {0,...,T−1}:di6=0}

. For

each subset of indices

I⊆ {0,1,...,T−1}

, the complement

is deﬁned as

Ic={i∈ {0,...,T−1}:i/∈I}

. For a matrix

Z∈Rn×T

, the projection

ΠIZ

is a matrix whose columns are

zero except for those in I, i.e.,

(ΠIZ)i=(zi,if i∈I

0,otherwise ,

where

denotes the

-th column of

. Deﬁne

as a

submatrix of

of size

n×|I|

, that includes only those columns

in the index set

. We use the shorthand notations

Z6=i

and

Z6∈I

to denote

Z{0,...,T−1}\{i}

and

Z{0,...,T−1}\I

, respectively.

The range of Zis deﬁned as R(Z) = {∑iλizi:λi∈R}.

To recover the system matrices

and

, we analyze the

following convex optimization problem:

min

A∈Rn×n,B∈Rn×m,

D∈D

T−1

∑

i=0

kdik2(1)

s.t.xi+1=Axi+Bui+di,i=0,...,T−1,

where the states

xi,i∈ {0,...,T}

, are generated according to

xi+1=¯

Axi+¯

Bui+¯

di,i=0,...,T−1.(2)

The control inputs

ui,i∈ {0,...,T−1}

, may be designed but

are ﬁxed in the optimization problem

(1)

. This problem differs

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

LearningofDynamicalSystemsunderAdversarialAttacks-NullSpacePropertyPerspectiveHanFeng,BaturalpYalcin,andJavadLavaeiAbstractWestudytheidenticationofalineartime-invariantdynamicalsystemaffectedbylarge-and-sparsedis-turbancesmodelingadversarialattacksorfaults.Undertheassumptionthatthestatesaremeasura...

展开>> 收起<<

Learning of Dynamical Systems under Adversarial Attacks - Null Space Property Perspective Han Feng Baturalp Yalcin and Javad Lavaei.pdf

共8页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Learning of Dynamical Systems under Adversarial Attacks - Null Space Property Perspective Han Feng Baturalp Yalcin and Javad Lavaei

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: