How can the structural complexity of a system be measured and reduced?

1. Introduction

Structural complexity, or more precisely: low structural complexity, is a quality characteristic of a system or software design. If the system or software design is structurally complex, then it is

• more time-consuming and therefore more expensive to develop,
• technically more difficult and therefore more costly to manufacture and maintain,
• more error-prone and therefore less reliable and
• harder to understand and therefore less convincing in terms of its safety argument.

So, controlling (preferrably: minimizing) structural complexity in the system and software design process is of utmost importance. Suppose we have two possible system or software architecture designs: how can we decide which design is better because its structural complexity is lower?

How can the structural complexity of a system or software be quantified?

A system architecture (and analogously a software architecture) is characterized by several aspects, namely

1. the decomposition of the system into its physical system elements,
2. the decomposition of system functions into system element functions,
3. the physical and functional interfaces and their interdependencies within the system and its elements, and
4. the generalized signals (i.e. the transfer of information, material or energy) and their interdependencies within the system and its elements.

We seek a structural complexity measure by means of which

1. the dependencies of the physical system elements,
2. the dependencies of the system element functions,
3. the dependencies of the system-internal interfaces, and
4. the dependencies of the system-internal (generalized) signals

can be evaluated.

Moreover, we want to take into account an important feature of safety-critical systems: the higher the required safety integrity level of a system part, the less structurally complex that system part is allowed to be.

Section 2 describes how we propose to measure and reduce structural complexity. Section 3 summarizes the main ideas of this article.

2. What is the most appropriate measure of structural complexity?

2.1. Structural Complexity of What?

The content of this Section 2.1 and the following Section 2.2 is largely based on [1].

As had already been mentioned in the introduction, structural complexity is about system- or software-internal dependencies: the more dependencies there are, the higher the structural complexity. Fig. 1 shows an example of a dependency tree and the associated adjacency matrix A (also known in the English literature as the “Dependency Structure Matrix”, or “DSM” for short).

Fig. 1: Dependency tree (left) and associated DSM (right), taken from [1], p. 34.

Note that

1. the dependencies of the physical system elements,
2. the dependencies of the system element functions,
3. the dependencies of the system-internal interfaces, and
4. the dependencies of the system-internal (generalized) signals

can all be represented by dependency trees and DSMs.

2.2. Recommended Structural Complexity Measure

Affecting or being affected by other system elements need not be direct – it may occur through intermediate connections. To capture this, we propose a structural complexity measure that takes into account both direct and indirect connections in the system architecture.

In safety-critical systems, one cannot assume that all system elements have the same safety integrity. To take this fact into account, we weight the system elements according to their safety integrity. The corresponding weighting matrix is given by

As for the structural complexity measure c we propose to calculate it as the Frobenius norm of the column-weighted extended reachability matrix R^ext where the columns are weighted according to the safety integrity of the system elements:

Which values should be chosen for the scalar weights?

In Tables 1 and 2 below we provide recommendations depending on whether

1. the “Safety Integrity Levels (SILs)” of IEC 61508 or
2. the “Automotive Safety Integrity Levels (ASILs)” of ISO 26262

are used to classify the system elements.

Table 1: Recommended weighting of system elements with SIL classification

Table 2: Recommended weighting of system elements with ASIL classification

ISO 26262:2018, Part 9, allows for a so-called "ASIL decomposition" of safety requirements. In practice, this idea is extended to ASIL decompositions of system elements and system functions that meet the decomposed safety requirements. The weights in Table 2 were chosen such that any kind of ASIL decomposition is "complexity-neutral". An example of such an ASIL decomposition is shown in Fig. 2 a) and b). Note that the structural complexity in a) and b) is the same.

Fig. 2: Dependency trees (a) without and (b) with ASIL decomposition.

2.3 Structural Complexity Reduction

Assume we have a candidate of the static system architecture. For this candidate system architecture we determine its c-value. Reducing the structural complexity of the system design means looking for alternative architectural designs with lower c-values (by “trial and error”).

Low c-values are typically attained by

• defining dependencies which „branch out“ top-down, but do not „re-connect“ further down,
• introducing SIL/ASIL decompositions and associated safety mechanisms as close to the safety-critical system outputs as possible, and
• ensuring that as much of the system functionality as possible is not safety-related or safety-critical.

3. Summary

In this article, a structural complexity measure c was taken from network theory and adapted to safety-critical systems. This measure c for structural complexity is based on a column-weighted extended reachability matrix. Such a reachability matrix can be determined for

1. the physical system and its decomposition into physical system elements,
2. the system and its functional decomposition,
3. the interface chains that end in the safety-related output interfaces of the system, and
4. the (generalized) signal chains that end in the safety-related outputs of the system.

The following properties expected of a structural complexity measure are met by c:

1. c is a measure in the mathematical sense (cf. e.g. [2]). In particular, for a system comprising the n elements s₁, …, s_n , the value of c is independent of the order of the system elements s₁, …, s_n.
2. The value of c increases with the number n of system elements.
3. The value of c increases with the number of direct or indirect dependencies between the system elements.
4. The value of c increases with increasing Safety Integrity Level of the system elements.

References

[1] Sturtevant, DJ: “System design and the cost of architectural complexity”, 2013, https://dspace.mit.edu/handle/1721.1/79551

[2] Measure (mathematics) – Wikipedia