-
Hazard Analysis for Self-Adaptive Systems Using System-Theoretic Process Analysis
Authors:
Simon Diemert,
Jens H. Weber
Abstract:
Self-adaptive systems are able to change their behaviour at run-time in response to changes. Self-adaptation is an important strategy for managing uncertainty that is present during the design of modern systems, such as autonomous vehicles. However, assuring the safety of self-adaptive systems remains a challenge, particularly when the adaptations have an impact on safety-critical functions. The f…
▽ More
Self-adaptive systems are able to change their behaviour at run-time in response to changes. Self-adaptation is an important strategy for managing uncertainty that is present during the design of modern systems, such as autonomous vehicles. However, assuring the safety of self-adaptive systems remains a challenge, particularly when the adaptations have an impact on safety-critical functions. The field of safety engineering has established practices for analyzing the safety of systems. System Theoretic Process and Analysis (STPA) is a hazard analysis method that is well-suited for self-adaptive systems. This paper describes a design-time extension of STPA for self-adaptive systems. Then, it derives a reference model and analysis obligations to support the STPA activities. The method is applied to three self-adaptive systems described in the literature. The results demonstrate that STPA, when used in the manner described, is an applicable hazard analysis method for safety-critical self-adaptive systems.
△ Less
Submitted 1 April, 2023;
originally announced April 2023.
-
Can Large Language Models assist in Hazard Analysis?
Authors:
Simon Diemert,
Jens H Weber
Abstract:
Large Language Models (LLMs), such as GPT-3, have demonstrated remarkable natural language processing and generation capabilities and have been applied to a variety tasks, such as source code generation. This paper explores the potential of integrating LLMs in the hazard analysis for safety-critical systems, a process which we refer to as co-hazard analysis (CoHA). In CoHA, a human analyst interac…
▽ More
Large Language Models (LLMs), such as GPT-3, have demonstrated remarkable natural language processing and generation capabilities and have been applied to a variety tasks, such as source code generation. This paper explores the potential of integrating LLMs in the hazard analysis for safety-critical systems, a process which we refer to as co-hazard analysis (CoHA). In CoHA, a human analyst interacts with an LLM via a context-aware chat session and uses the responses to support elicitation of possible hazard causes. In this experiment, we explore CoHA with three increasingly complex versions of a simple system, using Open AI's ChatGPT service. The quality of ChatGPT's responses were systematically assessed to determine the feasibility of CoHA given the current state of LLM technology. The results suggest that LLMs may be useful for supporting human analysts performing hazard analysis.
△ Less
Submitted 25 March, 2023;
originally announced March 2023.
-
A Foundation for Functional Graph Programs: The Graph Transformation Control Algebra (GTA)
Authors:
Jens H. Weber
Abstract:
Applications of graph transformation (GT) systems often require control structures that can be used to direct GT processes. Most existing GT tools follow a stateful computational model, where a single graph is repeatedly modified "in-place" when GT rules are applied. The implementation of control structures in such tools is not trivial. Common challenges include dealing with the non-determinism in…
▽ More
Applications of graph transformation (GT) systems often require control structures that can be used to direct GT processes. Most existing GT tools follow a stateful computational model, where a single graph is repeatedly modified "in-place" when GT rules are applied. The implementation of control structures in such tools is not trivial. Common challenges include dealing with the non-determinism inherent to rule application and transactional constraints when executing compositions of GTs, in particular atomicity and isolation. The complexity of associated transaction mechanisms and rule application search algorithms (e.g., backtracking) complicates the definition of a formal foundation for these control structures. Compared to these stateful approaches, functional graph rewriting presents a simpler (stateless) computational model, which simplifies the definition of a formal basis for (functional) GT control structures. In this paper, we propose the "Graph Transformation control Algebra" (GTA) as such a foundation. The GTA has been used as the formal basis for implementing the control structures in the (functional) GT tool "GrapeVine".
△ Less
Submitted 22 December, 2022;
originally announced December 2022.
-
Safety-Critical Adaptation in Self-Adaptive Systems
Authors:
Simon Diemert,
Jens H. Weber
Abstract:
Modern systems are designed to operate in increasingly variable and uncertain environments. Not only are these environments complex, in the sense that they contain a tremendous number of variables, but they also change over time. Systems must be able to adjust their behaviour at run-time to manage these uncertainties. These self-adaptive systems have been studied extensively. This paper proposes a…
▽ More
Modern systems are designed to operate in increasingly variable and uncertain environments. Not only are these environments complex, in the sense that they contain a tremendous number of variables, but they also change over time. Systems must be able to adjust their behaviour at run-time to manage these uncertainties. These self-adaptive systems have been studied extensively. This paper proposes a definition of a safety-critical self-adaptive system and then describes a taxonomy for classifying adaptations into different types based on their impact on the system's safety and the system's safety case. The taxonomy expresses criteria for classification and then describes specific criteria that the safety case for a self-adaptive system must satisfy, depending on the type of adaptations performed. Each type in the taxonomy is illustrated using the example of a safety-critical self-adaptive water heating system.
△ Less
Submitted 30 September, 2022;
originally announced October 2022.
-
Proceedings of the 11th Asia-Europe Workshop on Concepts in Information Theory
Authors:
A. J. Han Vinck,
Kees A. Schouhamer Immink,
Tadashi Wadayama,
Van Khu Vu,
Akiko Manada,
Kui Cai,
Shunsuke Horii,
Yoshiki Abe,
Mitsugu Iwamoto,
Kazuo Ohta,
Xingwei Zhong,
Zhen Mei,
Renfei Bu,
J. H. Weber,
Vitaly Skachek,
Hiroyoshi Morita,
N. Hovhannisyan,
Hiroshi Kamabe,
Shan Lu,
Hirosuke Yamamoto,
Kengo Hasimoto,
O. Ytrehus,
Shigeaki Kuzuoaka,
Mikihiko Nishiara,
Han Mao Kiah
, et al. (2 additional authors not shown)
Abstract:
This year, 2019 we celebrate 30 years of our friendship between Asian and European scientists at the AEW11 in Rotterdam, the Netherlands. Many of the 1989 participants are also present at the 2019 event. This year we have many participants from different parts of Asia and Europe. It shows the importance of this event. It is a good tradition to pay a tribute to a special lecturer in our community.…
▽ More
This year, 2019 we celebrate 30 years of our friendship between Asian and European scientists at the AEW11 in Rotterdam, the Netherlands. Many of the 1989 participants are also present at the 2019 event. This year we have many participants from different parts of Asia and Europe. It shows the importance of this event. It is a good tradition to pay a tribute to a special lecturer in our community. This year we selected Hiroyoshi Morita, who is a well known information theorist with many original contributions.
△ Less
Submitted 26 June, 2019;
originally announced July 2019.
-
Secure Transmission on the Two-hop Relay Channel with Scaled Compute-and-Forward
Authors:
Zhijie Ren,
Jasper Goseling,
Jos H. Weber,
Michael Gastpar
Abstract:
In this paper, we consider communication on a two-hop channel, in which a source wants to send information reliably and securely to the destination via a relay. We consider both the untrusted relay case and the external eavesdropper case. In the untrusted relay case, the relay behaves as an eavesdropper and there is a cooperative node which sends a jamming signal to confuse the relay when the it i…
▽ More
In this paper, we consider communication on a two-hop channel, in which a source wants to send information reliably and securely to the destination via a relay. We consider both the untrusted relay case and the external eavesdropper case. In the untrusted relay case, the relay behaves as an eavesdropper and there is a cooperative node which sends a jamming signal to confuse the relay when the it is receiving from the source. We propose two secure transmission schemes using the scaled compute-and-forward technique. One of the schemes is based on a random binning code and the other one is based on a lattice chain code. It is proved that in either the high Signal-to-Noise-Ratio (SNR) scenario and/or the restricted relay power scenario, if the destination is used as the jammer, both schemes outperform all existing schemes and achieve the upper bound. In particular, if the SNR is large and the source, the relay, and the cooperative jammer have identical power and channels, both schemes achieve the upper bound for secrecy rate, which is merely $1/2$ bit per channel use lower than the channel capacity without secrecy constraints. We also prove that one of our schemes achieves a positive secrecy rate in the external eavesdropper case in which the relay is trusted and there exists an external eavesdropper.
△ Less
Submitted 14 September, 2015;
originally announced September 2015.
-
Pearson codes
Authors:
Jos H. Weber,
Kees A. Schouhamer Immink,
Simon R. Blackburn
Abstract:
The Pearson distance has been advocated for improving the error performance of noisy channels with unknown gain and offset. The Pearson distance can only fruitfully be used for sets of $q$-ary codewords, called Pearson codes, that satisfy specific properties. We will analyze constructions and properties of optimal Pearson codes. We will compare the redundancy of optimal Pearson codes with the redu…
▽ More
The Pearson distance has been advocated for improving the error performance of noisy channels with unknown gain and offset. The Pearson distance can only fruitfully be used for sets of $q$-ary codewords, called Pearson codes, that satisfy specific properties. We will analyze constructions and properties of optimal Pearson codes. We will compare the redundancy of optimal Pearson codes with the redundancy of prior art $T$-constrained codes, which consist of $q$-ary sequences in which $T$ pre-determined reference symbols appear at least once. In particular, it will be shown that for $q\le 3$ the $2$-constrained codes are optimal Pearson codes, while for $q\ge 4$ these codes are not optimal.
△ Less
Submitted 29 September, 2015; v1 submitted 1 September, 2015;
originally announced September 2015.
-
Perspectives on Balanced Sequences
Authors:
Jos H. Weber,
Kees A. Schouhamer Immink,
Paul H. Siegel,
Theo G. Swart
Abstract:
We examine and compare several different classes of "balanced" block codes over q-ary alphabets, namely symbol-balanced (SB) codes, charge-balanced (CB) codes, and polarity-balanced (PB) codes. Known results on the maximum size and asymptotic minimal redundancy of SB and CB codes are reviewed. We then determine the maximum size and asymptotic minimal redundancy of PB codes and of codes which are b…
▽ More
We examine and compare several different classes of "balanced" block codes over q-ary alphabets, namely symbol-balanced (SB) codes, charge-balanced (CB) codes, and polarity-balanced (PB) codes. Known results on the maximum size and asymptotic minimal redundancy of SB and CB codes are reviewed. We then determine the maximum size and asymptotic minimal redundancy of PB codes and of codes which are both CB and PB. We also propose efficient Knuth-like encoders and decoders for all these types of balanced codes.
△ Less
Submitted 28 January, 2013;
originally announced January 2013.
-
Random Access with Physical-layer Network Coding
Authors:
Jasper Goseling,
Michael Gastpar,
Jos H. Weber
Abstract:
Leveraging recent progress in physical-layer network coding we propose a new approach to random access: When packets collide, it is possible to recover a linear combination of the packets at the receiver. Over many rounds of transmission, the receiver can thus obtain many linear combinations and eventually recover all original packets. This is by contrast to slotted ALOHA where packet collisions l…
▽ More
Leveraging recent progress in physical-layer network coding we propose a new approach to random access: When packets collide, it is possible to recover a linear combination of the packets at the receiver. Over many rounds of transmission, the receiver can thus obtain many linear combinations and eventually recover all original packets. This is by contrast to slotted ALOHA where packet collisions lead to complete erasures. The throughput of the proposed strategy is derived and shown to be significantly superior to the best known strategies, including multipacket reception.
△ Less
Submitted 23 December, 2012;
originally announced December 2012.
-
On the Energy Benefit of Network Coding for Wireless Multiple Unicast
Authors:
Jasper Goseling,
Ruytaroh Matsumoto,
Tomohiko Uyematsu,
Jos H. Weber
Abstract:
We consider the energy savings that can be obtained by employing network coding instead of plain routing in wireless multiple unicast problems. We establish lower bounds on the benefit of network coding, defined as the maximum of the ratio of the minimum energy required by routing and network coding solutions, where the maximum is over all configurations. It is shown that if coding and routing sol…
▽ More
We consider the energy savings that can be obtained by employing network coding instead of plain routing in wireless multiple unicast problems. We establish lower bounds on the benefit of network coding, defined as the maximum of the ratio of the minimum energy required by routing and network coding solutions, where the maximum is over all configurations. It is shown that if coding and routing solutions are using the same transmission range, the benefit in $d$-dimensional networks is at least $2d/\lfloor\sqrt{d}\rfloor$. Moreover, it is shown that if the transmission range can be optimized for routing and coding individually, the benefit in 2-dimensional networks is at least 3. Our results imply that codes following a \emph{decode-and-recombine} strategy are not always optimal regarding energy efficiency.
△ Less
Submitted 18 August, 2011; v1 submitted 16 January, 2009;
originally announced January 2009.
-
Energy Benefit of Network Coding for Multiple Unicast in Wireless Networks
Authors:
Jasper Goseling,
Jos. H. Weber
Abstract:
We show that the maximum possible energy benefit of network coding for multiple unicast on wireless networks is at least 3. This improves the previously known lower bound of 2.4 from [1].
We show that the maximum possible energy benefit of network coding for multiple unicast on wireless networks is at least 3. This improves the previously known lower bound of 2.4 from [1].
△ Less
Submitted 3 November, 2008;
originally announced November 2008.
-
Results on Parity-Check Matrices with Optimal Stopping and/or Dead-End Set Enumerators
Authors:
Jos H. Weber,
Khaled A. S. Abdel-Ghaffar
Abstract:
The performance of iterative decoding techniques for linear block codes correcting erasures depends very much on the sizes of the stopping sets associated with the underlying Tanner graph, or, equivalently, the parity-check matrix representing the code. In this paper, we introduce the notion of dead-end sets to explicitly demonstrate this dependency. The choice of the parity-check matrix entails…
▽ More
The performance of iterative decoding techniques for linear block codes correcting erasures depends very much on the sizes of the stopping sets associated with the underlying Tanner graph, or, equivalently, the parity-check matrix representing the code. In this paper, we introduce the notion of dead-end sets to explicitly demonstrate this dependency. The choice of the parity-check matrix entails a trade-off between performance and complexity. We give bounds on the complexity of iterative decoders achieving optimal performance in terms of the sizes of the underlying parity-check matrices. Further, we fully characterize codes for which the optimal stopping set enumerator equals the weight enumerator.
△ Less
Submitted 7 July, 2006;
originally announced July 2006.
-
Complete Enumeration of Stopping Sets of Full-Rank Parity-Check Matrices of Hamming Codes
Authors:
Khaled A. S. Abdel-Ghaffar,
Jos H. Weber
Abstract:
Stopping sets, and in particular their numbers and sizes, play an important role in determining the performance of iterative decoders of linear codes over binary erasure channels. In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three for a full-rank parity-check matrix of the Hamming code. In this correspondence, we derive an expression for t…
▽ More
Stopping sets, and in particular their numbers and sizes, play an important role in determining the performance of iterative decoders of linear codes over binary erasure channels. In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three for a full-rank parity-check matrix of the Hamming code. In this correspondence, we derive an expression for the number of stopping sets of any given size for the same parity-check matrix.
△ Less
Submitted 2 March, 2006;
originally announced March 2006.
