User:IDeALabsBYU/sandbox
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 , and by specifying input influence via a second matrix [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
Consider a standard state-space representation of a linear time-invariant system:
where are the internal state, input, and the observed output of the system, respectively, at time ; is the time derivative of ; and are fixed matrices of appropriate size.
The DSF is defined as a tuple of matrices with the following properties:
- , the transfer function
- and contain other structural information learned from data (explained below)
- is hollow, meaning its diagonal entries are identically zero
Here, , and are matrices over functions of a single Laplace variable. The state-space representation uniquely determines the DSF (derivations are found below), which uniquely determines the transfer function . 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 , without additional structural information, corresponds with infinitely many dynamical structures (by choosing , as ), 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
For an introductory derivation (with ), consider a partition of some strictly causal LTI state space system with an appropriate change of basis[8] to bring into a direct measurement of some set of manifest or exposed states and some hidden states :
The dynamical structure function (in the frequency domain) is given by:
with auxillary matrices and , and is the square diagonal matrix whose entries are equal to the diagonal of . Extensions to these definitions to account for general and matrices in LTI state-space systems exit and are derived similarly.[9][10]
Derivation using a Stacked Immersion
One can also derive the DSF using the following matrix inverse formula[11]:
Where the quantity above is a partition of conforming with the block partition of . As we know that the transfer function , we can deduce (once we remove the quotient , making strictly proper[12]) that:
Where we can use to calculate exactly as we did above. This procedure is called stacked immersion [11].
Network Reconstruction
One use of the DSF stems from its ability to encode a system's signal structure, or the relationships between manifest or measured states . When properly reconstructed, and communicate the actual computational and dynamical interactions which occur between the measured signals, whereas the input-output map does not allow us to deduce these relationships. Because of this, and are visualized as directed graphs between input signals and measured signal , 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 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 and imput other learned or assumed structure in either or 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 in the following way:
This equation is equivalent to the identity . We then write a seperate equation for each column in this equality, and we can stack the resulting equations into a single matrix equation:
Where constructs a block diagonal matrix from its arguments (similar to a direct sum), and the vectors are the rows of respectively, transposed into column vectors. As and , we know that and . Therefore the column of unknowns on the left is an element of and the column of known values on the right is in (with entries exactly taken from ). This leaves us with degrees of freedom, which can be further reduced by noting that the diagonal entries of are identically zero, leaving 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 or , 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 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
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 (sometimes called ), 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] over a class of attacks having some anticipated structure. We can consider three main classes of attacks :
- Single-link attacks, where has only one nonzero entry.
- Multi-link distributed attacks, which are diagonal.
- Multi-link coordinated attacks, having block matrices potentially entirely covering .
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 norm over the signal dynamics exposed to the attacker[15], giving a system vulnerability:
where is a model of the internal signal dynamics exposed to the attacker, whose entries are manifest states' signal-gain functions of a single Laplace variable. Traditionally, the DSF has been used to derive , 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 ) of one subsystem does not affect the vulnerability of other subsystems, even when connected in feedback [19].
Theoretical Properties
The DSF of a system is controllable if and only if there exists a known DSF with the same structural zeros in its matrices [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 ).
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
- ^ a b c Goncalves, Jorge; Howes, Russell; Warnick, Sean (2007). "Dynamical structure functions for the reverse engineering of LTI networks" (PDF). 2007 46th IEEE Conference on Decision and Control: 1516–1522. doi:10.1109/CDC.2007.4434406. Retrieved 26 June 2024.
- ^ Adebayo, J; Southwick, T; Chetty, V; Yeung, E; Yuan, Y; et al. (2012). "Dynamical structure function identifiability conditions enabling signal structure reconstruction" (PDF). 2012 IEEE 51st IEEE Conference on Decision and Control (CDC): 4635–4641. doi:10.1109/CDC.2012.6426183. Retrieved 1 July 2024.
{{cite journal}}
: Explicit use of et al. in:|last6=
(help) - ^ Woodbury, Nathan Scott. "Representation and Reconstruction of Linear, Time-Invariant Networks" (PDF). IDeA Labs Publications. Brigham Young University. Retrieved 1 July 2024.
- ^ a b c d Goncalves, Jorge; Warnick, Sean (2008). "Necessary and Sufficient Conditions for Dynamical Structure Reconstruction of LTI Networks" (PDF). IEEE Transactions on Automatic Control: 1670–1674. doi:10.1109/TAC.2008.928114. Retrieved 27 June 2024.
- ^ a b Chetty, Vasu. "Necessary and Sufficient Informativity Conditions for Robust Network Reconstruction Using Dynamical Structure Functions" (PDF). IDeA Labs. Brigham Young University. Retrieved 27 June 2024.
- ^ a b Adebayo, J; Southwick, T; Chetty, V; Yeung, E; et al. (2012). "Dynamical structure function identifiability conditions enabling signal structure reconstruction" (PDF). 2012 IEEE 51st IEEE Conference on Decision and Control (CDC): 4635–4641. doi:10.1109/CDC.2012.6426183. Retrieved 27 June 2024.
{{cite journal}}
: Explicit use of et al. in:|last5=
(help) - ^ a b Leung, Humphrey; Warnick, Sean (2018). "Necessary and Sufficient Conditions on State Transformations That Preserve the Causal Structure of LTI Dynamical Networks" (PDF). 2018 IEEE Conference on Decision and Control (CDC): 7071–7076. doi:10.1109/CDC.2018.8619454. Retrieved 26 June 2024.
- ^ a b c Chetty, Vasu; Warnick, Sean (2015). "Network semantics of dynamical systems" (PDF). 2015 54th IEEE Conference on Decision and Control (CDC): 1557–1562. doi:10.1109/CDC.2015.7402432. Retrieved 26 June 2024.
- ^ a b Yeung, E; Goncalves, J; Sandberg, H (2011). "Mathematical relationships between representations of structure in linear interconnected dynamical systems" (PDF). Proceedings of the 2011 American Control Conference: 4348–4353. doi:10.1109/ACC.2011.5991314. Retrieved 26 June 2024.
- ^ a b c Chetty, Vasu; Warnick, Sean (15 Oct 2020). Meanings and Applications of Structure in Networks of Dynamic Systems, Chapter 7 in Principles of Cyber-Physical Systems: An Interdisciplinary Approach (PDF). Cambridge University Press. pp. 162–198. Retrieved 26 June 2024.
- ^ a b Woodbury, Nathan; Warnick, Sean (2019). "Abstractions and Realizations of Dynamic Networks" (PDF). 2019 American Control Conference (ACC): 5167–5172. doi:10.23919/ACC.2019.8814844. Retrieved 26 June 2024.
- ^ Woodbury, Nathan; Dankers, Arne; Warnick, Sean (2018). "Dynamic Networks: Representations, Abstractions, and Well-Posedness" (PDF). 2018 IEEE Conference on Decision and Control (CDC): 4719–4724. doi:10.1109/CDC.2018.8619098. Retrieved 26 June 2024.
- ^ Morrison, J L; Breitling, R; Higham, D J; Gilbert, D R (2006). "A lock-and-key model for protein–protein interactions". Bioinformatics. 22 (16): 2012–2019. doi:10.1093/bioinformatics/btl338. Retrieved 27 June 2024.
- ^ Yuan, Ye. "Decentralised network prediction and reconstruction algorithms". Apollo Repository. University of Cambridge, Department of Engineering. Retrieved 26 June 2024.
- ^ a b Chetty, V; Woodbury, N; Vaziripour, E; Warnick, S (2014). "Vulnerability analysis for distributed and coordinated destabilization attacks" (PDF). 53rd IEEE Conference on Decision and Control: 511–516. doi:10.1109/CDC.2014.7039432. Retrieved 26 June 2024.
- ^ Dahleh, Mohammed; Dahleh, Munther; Verghese, George. "Lectures on Dynamic Systems and Control" (PDF). MIT Open Courseware. Massachusetts Institute of Technology. Retrieved 27 June 2024.
- ^ Johnson, Charles. "NET PATH AND NET EFFECT OF LINEAR NETWORKS WITH DYNAMICS" (PDF). IdeA Labs. Brigham Young University. Retrieved 27 June 2024.
- ^ Rai, A; Ward, D; Roy, S; Warnick, S (2012). "Vulnerable links and secure architectures in the stabilization of networks of controlled dynamical systems" (PDF). 2012 American Control Conference (ACC): 1248–1253. doi:10.1109/ACC.2012.6315327. Retrieved 26 June 2024.
- ^ Woodbury, Nathan. "Vulnerability Analysis of Closed-Loop Systems" (PDF). IDeA Labs Publications. Brigham Young University. Retrieved 26 June 2024.
- ^ Johnson, Charles A.; Warnick, Sean (2020). "Characterizing Network Controllability and Observability for Abstractions and Realizations of Dynamic Networks" (PDF). IFAC-PapersOnLine. 53 (2): 10987–10993. doi:10.1016/j.ifacol.2020.12.019. Retrieved 26 June 2024.
External links
- Lab Publications, Information and Decision Algorithms (IDeA) Labs, Computer Science Dept., Brigham Young University