User:IDeALabsBYU/sandbox

This is the user sandbox of IDeALabsBYU. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here. Other sandboxes: Main sandbox | Template sandbox Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

In control theory, the dynamical structure function (DSF) of a system is a representation of the system's transfer function which communicates structural information and signal-flow relationships between manifest or measured states of the system. It is a right factoring of the transfer function matrix. It was formulated in 2007 by Jorge Goncalves, Russell Howes, and Sean Warnick.^[1]

The DSF represents an intermediate representation between the transfer function and a state-space realization ^[2][3]. In this way, it can represent known dynamical (computational) structure between measured states, variables, or signals, even when the entire state-space realization is unknown. This is done by enforcing structured signal relationships between manifest (measured) states using a hollow matrix ${\displaystyle Q(s)}$, and by specifying input influence via a second matrix ${\displaystyle P(s)}$ ^[1]. In this context, "structure" refers to known zero entries of these matrices, which represent non-existant direct causal relationships between any two signals. With enough known structural constraints, the transfer function can be used to uniquely determine exact signal gains between measured states ^[4][5][6].

Definition[edit]

Consider a standard state-space representation of a linear time-invariant system:

${\displaystyle {\dot {x}}(t)=Ax(t)+Bu(t)}$

${\displaystyle y(t)=Cx(t)+Du(t)}$

where ${\displaystyle x(t)\in \mathbb {R} ^{n},u(t)\in \mathbb {R} ^{m},y(t)\in \mathbb {R} ^{p}}$ are the internal state, input, and the observed output of the system, respectively, at time ${\displaystyle t}$; ${\displaystyle {\dot {x}}(t)}$ is the time derivative of ${\displaystyle x(t)}$; and ${\displaystyle A,B,C,D}$ are fixed matrices of appropriate size.

The DSF is defined as a tuple of matrices ${\displaystyle (Q,P)}$ with the following properties:

• ${\displaystyle Y(s)=Q(s)Y(s)+P(s)U(s)}$
• ${\displaystyle (I-Q)^{-1}P=G(s)}$, the transfer function ${\displaystyle Y(s)=G(s)U(s)}$
• ${\displaystyle Q}$ and ${\displaystyle P}$ contain other structural information learned from data (explained below)
• ${\displaystyle Q}$ is hollow, meaning its diagonal entries are identically zero

Here, ${\displaystyle Y(s)={\mathcal {L}}[y](s),U(s)={\mathcal {L}}[u](s)}$, and ${\displaystyle Q,P,G}$ are matrices over functions of a single Laplace variable. The state-space representation ${\displaystyle (A,B,C,D)}$ uniquely determines the DSF ${\displaystyle (Q,P)}$ (derivations are found below), which uniquely determines the transfer function ${\displaystyle G}$. This is equivalent to stating that each system realization has a determined signal structure, which in turn has a determined input-output behavior. Conversely, a system behavior ${\displaystyle G(s)}$, without additional structural information, corresponds with infinitely many dynamical structures (by choosing ${\displaystyle Q}$, as ${\displaystyle P=(I-Q)G}$), which in turn each have infinitely many state-space realizations ^[1][7]. It is possible, however, to learn signal structure and the DSF with from data, and this reconstruction requires much less data than the entire state space model ^[4][5].

It has been shown that permuting exposed states only permutes the DSF^[8], and that the DSF is invarient under a change of basis of the hidden (non-measured) states of a state-space system^[7]. In general, however, changing the basis of the exposed states changes the DSF, as the new measured signals are linear combinations of the old basis signals and thus carry all structural dependencies of these original states.

Simple Derivation from a State-Space Representation[edit]

For an introductory derivation (with ${\displaystyle D=0}$), consider a partition of some strictly causal LTI state space system with an appropriate change of basis^[8] to bring ${\displaystyle C}$ into a direct measurement of some set of manifest or exposed states ${\displaystyle y}$ and some hidden states ${\displaystyle z}$:

${\displaystyle {\begin{bmatrix}{\dot {y}}\\{\dot {z}}\end{bmatrix}}={\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}}{\begin{bmatrix}y\\z\end{bmatrix}}+{\begin{bmatrix}B_{1}\\B_{2}\end{bmatrix}}u.}$

${\displaystyle y={\begin{bmatrix}I&0\end{bmatrix}}\ {\begin{bmatrix}y\\z\end{bmatrix}}.}$

The dynamical structure function (in the frequency domain) is given by:

${\displaystyle Q(s)=(sI-diag(W(s))^{-1}(W(s)-diag(W(s))}$

${\displaystyle P(s)=(sI-diag(W(s))^{-1}V(s)}$

with auxillary matrices ${\displaystyle W(s)=A_{11}+A_{12}(sI-A_{22})^{-1}A_{21}}$ and ${\displaystyle V(s)=B_{1}+A_{12}(sI-A_{22})^{-1}B_{2}}$, and ${\displaystyle diag(W(s))}$ is the square diagonal matrix whose entries are equal to the diagonal of ${\displaystyle W(s)}$. Extensions to these definitions to account for general ${\displaystyle C}$ and ${\displaystyle D}$ matrices in LTI state-space systems exit and are derived similarly.^[9][10]

Derivation using a Stacked Immersion[edit]

One can also derive the DSF using the following matrix inverse formula^[11]:

${\displaystyle {\begin{bmatrix}sI-A_{1}&-A_{2}\\-A_{3}&sI-A_{4}\end{bmatrix}}^{-1}={\begin{bmatrix}\left(sI-A_{1}-A_{2}(sI-A_{4})^{-1}A_{3}\right)^{-1}&0\\0&\left(sI-A_{4}-A_{3}(sI-A_{1})^{-1}A_{2}\right)^{-1}\end{bmatrix}}{\begin{bmatrix}I&A_{2}(sI-A_{4})^{-1}\\A_{3}(sI-A_{1})^{-1}&I\end{bmatrix}}.}$

Where the quantity above is a partition of ${\displaystyle (sI-A)^{-1}}$ conforming with the block partition of ${\displaystyle C=[I\ \ 0]}$. As we know that the transfer function ${\displaystyle G=D+C(sI-A)^{-1}B}$, we can deduce (once we remove the quotient ${\displaystyle D}$, making ${\displaystyle C(sI-A)^{-1}B=(I-Q)^{-1}P}$ strictly proper^[12]) that:

${\displaystyle (I-W)^{-1}=s{\begin{bmatrix}\left(sI-A_{1}-A_{2}(sI-A_{4})^{-1}A_{3}\right)^{-1}&0\\0&\left(sI-A_{4}-A_{3}(sI-A_{1})^{-1}A_{2}\right)^{-1}\end{bmatrix}}}$

${\displaystyle V={\frac {1}{s}}{\begin{bmatrix}I&A_{2}(sI-A_{4})^{-1}\\A_{3}(sI-A_{1})^{-1}&I\end{bmatrix}}{\begin{bmatrix}B_{1}\\B_{2}\end{bmatrix}}.}$

Where we can use ${\displaystyle W,V}$ to calculate ${\displaystyle Q,P}$ exactly as we did above. This procedure is called stacked immersion ^[11].

Network Reconstruction[edit]

One use of the DSF stems from its ability to encode a system's signal structure, or the relationships between manifest or measured states ${\displaystyle y}$. When properly reconstructed, ${\displaystyle Q}$ and ${\displaystyle P}$ communicate the actual computational and dynamical interactions which occur between the measured signals, whereas the input-output map ${\displaystyle G}$ does not allow us to deduce these relationships. Because of this, ${\displaystyle Q}$ and ${\displaystyle P}$ are visualized as directed graphs between input signals ${\displaystyle u}$ and measured signal ${\displaystyle y}$, where the nodes of this graph are the signals and the edges are transfer functions between signals (which may indicate subsystems determining signal flow).

We require ${\displaystyle Q}$ to be hollow, as this forces all self-dynamics to occur before state measurement (which is the case with measured data).

The basic aproach to network reconstruction is to learn the input-output behavior ${\displaystyle G(s)}$ and imput other learned or assumed structure in either ${\displaystyle Q(s)}$ or ${\displaystyle P(s)}$ until the number of unknown entries exactly equals the number of data-informed equations^[4][6]. This is done by stacking the unknown variables (entries of ${\displaystyle Q(s),P(s)}$ in the following way:

${\displaystyle {\begin{bmatrix}I&G^{T}\end{bmatrix}}{\begin{bmatrix}P^{T}\\Q^{T}\end{bmatrix}}=G^{T}}$

This equation is equivalent to the identity ${\displaystyle G(s)=(I-Q(s))^{-1}P(s)}$. We then write a seperate equation for each column in this equality, and we can stack the resulting equations into a single matrix equation:

${\displaystyle \left[{\begin{array}{c|c}I&\operatorname {blckdiag} (G^{T},...,G^{T})\end{array}}\right]{\begin{bmatrix}\mathbf {p} _{1}\\...\\\mathbf {p} _{p}\\\hline \mathbf {q} _{1}\\...\\\mathbf {q} _{p}\end{bmatrix}}={\begin{bmatrix}\mathbf {g} _{1}\\...\\\mathbf {g} _{p}\\\end{bmatrix}}}$

Where ${\displaystyle \operatorname {blckdiag} }$ constructs a block diagonal matrix from its arguments (similar to a direct sum), and the vectors ${\displaystyle \mathbf {p} _{i},\mathbf {q} _{i},\mathbf {g} _{i}}$ are the rows of ${\displaystyle P,Q,G}$ respectively, transposed into column vectors. As ${\displaystyle y(t)\in \mathbb {R} ^{p}}$ and ${\displaystyle u(t)\in \mathbb {R} ^{m}}$, we know that ${\displaystyle Q\in \mathbb {C} ^{\mathbb {C} \times p\times p}}$ and ${\displaystyle P,G\in \mathbb {C} ^{\mathbb {C} \times p\times m}}$. Therefore the column of unknowns on the left is an element of ${\displaystyle \mathbb {C} ^{\mathbb {C} \times p^{2}+pm}}$ and the column of known values on the right is in ${\displaystyle \mathbb {C} ^{\mathbb {C} \times pm}}$ (with entries exactly taken from ${\displaystyle G}$). This leaves us with ${\displaystyle p^{2}}$ degrees of freedom, which can be further reduced by noting that the ${\displaystyle p}$ diagonal entries of ${\displaystyle Q}$ are identically zero, leaving ${\displaystyle p^{2}-p}$ degrees of freedom.

We can imput additional structural knowledge or assumptions in order to eliminate the degrees of freedom and obtain a unique solution. By structure, we mean the position of zero entries in ${\displaystyle Q}$ or ${\displaystyle P}$, but it is also possible to imput assumed values or dependence relationships between entries. A sufficient assumption is input specificity, where each input directly influences only one output; this forces ${\displaystyle P}$ to be diagonal^[4]. Such a situation often arises in biochemical systems, where proteins act on certain chemical species with lock-and-key specificity ^[13].

Advanced methods also exist for approximating network reconstruction when insufficient data is available for complete reconstruction, though the problem is in general NP-Hard.^[14]

System Vulnerability[edit]

The Dynamical Structure Function (DSF) can be used to model the attack surface of a cyber-physical system. Attacks on cyber-physical systems can generally be placed into three categories: deception, denial of service, and destabilization^[15]. Deception attacks aim to provide false information to authorized sources; denial of service (DoS) attacks aim to disrupt communication between states in a system, often to achieve some other goal such as destabilization or degradation of the system's performance.

DSF has primarily been applied to the third category, destabilization attacks, which involve an attacker introducing perturbations on system signals to strategically shift the system dynamics toward instability. These attacks are designed using fundamental tools of robust control, namely isolating the attacker's access points into a single term ${\displaystyle \Delta }$ (sometimes called ${\displaystyle K}$), which when considered in feedback affects the remaining system according to a linear fractional transform^[10]. This allows the attacker to move the poles or modes of the system toward the right half of the complex plane (when signal transfer is measured in the Laplace basis), leading to instability and ultimately system failure. Thankfully, the system administrator can also use H-infinity methods to combat such attacks by reducing the system's vulnerability in design and implementation.

System vulnerability is measured using the structured singular value^[16] ${\displaystyle \mu }$ over a class of attacks ${\displaystyle {\underline {\Delta }}}$ having some anticipated structure. We can consider three main classes of attacks ${\displaystyle {\underline {\Delta }}}$:

• Single-link attacks, where ${\displaystyle \Delta }$ has only one nonzero entry.
• Multi-link distributed attacks, which are diagonal.
• Multi-link coordinated attacks, having block matrices potentially entirely covering ${\displaystyle \Delta }$.

Multi-link attacks are notably simpler to address, as these structured singular values are closely linked to the spectral radius and two-norm, respectively. Single-link attacks, on the other hand, are determined using the maximal ${\displaystyle H_{\infty }}$ norm over the signal dynamics exposed to the attacker^[15], giving a system vulnerability:

${\displaystyle V=\max _{ij}\|H_{ij}\|_{\infty }}$

where ${\displaystyle H}$ is a model of the internal signal dynamics exposed to the attacker, whose entries ${\displaystyle H_{ij}}$ are manifest states' signal-gain functions of a single Laplace variable. Traditionally, the DSF has been used to derive ${\displaystyle H=(I-Q)^{-1}}$, which computes the gain or net effect^[17] similar to Mason's gain formula.

The system administrator's objective is to minimize this quantity during implementation. This is not a convex optimization problem, and is not trivial. For example, the administrator may have an incorrect understanding of which states are exposed, leading to dramatically different attack surfaces and vulnerabilities. There is also a game-theoretic approach, as the administrator must choose where to allocate resources to secure vulnerable nodes, or trade efficiency for security during operation. The other player, the attacker, will likewise design an attack strategy using similar considerations.

The attacker searches for, and the administrator defends, vulnerable links. These are defined as manifest signal transfers (edges in the signal-flow graph defined by the DSF) where a stable additive perterbation to that link destablizes the system^[18]. This occurs only in signal dynamics where the signal-flow structure is cyclic, as the linear fractional transform allows poles to appear in or move to the right half-plane in the Laplace basis. A version of the separation principle applies when considering the vulnerability of interconnected subsystems, in that the implementation (choice of ${\displaystyle Q,P}$) of one subsystem does not affect the vulnerability of other subsystems, even when connected in feedback ^[19].

Theoretical Properties[edit]

The DSF of a system is controllable if and only if there exists a known DSF with the same structural zeros in its matrices ${\displaystyle Q,P}$^[20]. Observability conditions are equivalent in the transpose network (i.e. a system is observable if and only if there exists a controllable system with the same structure as ${\displaystyle Q^{T},P^{T}}$).

Explores partitioning subsystems to have mutually exclusive internal states.^[8]

Subsystems are modeled as agents who share information. Subsystems cannot share states but modules can. Defines structural zeros, and states that observability and controlability are dual structure problems involving the existance of paths between inputs and outputs in the signal graph, or more precisely if there exists a signal graph with the same structure which is known to be observable or controlable. Uses the DNF. The edges of DSFs are SISO subsystems. Restricts the structural controlability problem to realization with the same Smith-McMillan degree (otherwise immersion might lose controllability or gain observability). Defines complete vs. incomplete immersions based on whether immerses signals had in and out paths (so they and their other edges are not lost but encoded in the remaining edges, so all input immersions are incomplete as are "terminal" signals). This idea of a complete immersion preserves the Smith-McMillan degree.

The general state space model, using auxillary or intricacy variables w to model intermediate computations. Compressing system signal graphs into subsystem transfer graphs (edges are systems, not just signals).^[10]

Generalized state-space realization (using auxilary w) and defines intricacy. Has the general DSF for nonzero D and redundant outputs, and some comments on strictly proper P. Also describes the differences between the normal and condensed subsystem structure graph and the signal graph, where the first has system nodes with signal edges, but the second has signal edges and system behavior (transfer) on edges (making sort of dual graphs). In signal structure, manifest variables can be shared between subsystems, unlike in subsystem structure representations. System and signal structures do not uniquely specify each other, so they are not in hierarchy.^[9]

References[edit]

External links[edit]

• Lab Publications, Information and Decision Algorithms (IDeA) Labs, Computer Science Dept., Brigham Young University