Formal Knowledge Representations for
Textual Automotive System
Requirements and Tests

A thesis accepted by the Faculty of Aerospace Engineering and Geodesy of the
University of Stuttgart in partial fulfilment of the requirements for the degree

of Doctor of Engineering Sciences (Dr.-Ing.)

by

M.Sc. Benedikt Walter

born in Ellwangen (Jagst)

main referee: Priv.-Doz. Dr.-Ing. Stephan Rudolph

co-referee: Prof. Dr. Andreas Vogelsang

co-referee: Prof. Dr.-Ing. Andreas Strohmayer

Date of defence: 03.12.2020

Institute of Aircraft Design
University of Stuttgart

2021





“Whenever you find yourself on the

side of the majority, it is time to pause

and reflect.”

Mark Twain





Preamble

This thesis is based on the research conducted during my time as an industrial PhD

student at Daimler AG, Mercedes-Benz car development between June 2015 and April

2018. It was finalized during my time as a development engineer in the Department of

Automated Driving from May 2018 until the end of 2020. The research took place in

the E/E System Testing and Validation Department where I worked for 1.5 years in the

Team ‘Testing Process’ and 1.5 years in the Team ‘Requirements Validation and Testing

Methodology’. In particular I want to thank Dirk Johanson (Lead of the Team ‘Testing

Process’ ) for providing me with this opportunity and the freedom to pursue my research

into any direction I was interested in. Further, I want to thank Dr. Frank Houdek (Lead

of the Team ‘Requirements Validation and Testing Methodology’ ) for his support and

helpful guidance in the art of writing scientific papers.

Many thanks go to all students that worked along side me throughout the time: Ivan

Vishev, Jakob Hammes, Marco Piechotta, Melf Zeymer, Jonathan Schmidt and Hannah

Dettki. This work would have not been possible without all your effort and dedica-

tion. In the same way I want to thank the young researchers that were brave enough

to perform their bachelor or master thesis under my supervision: Mohammed Salah Ben

Slimen, Maximilian Schilling, Jan Martin and Payal Sood. Your ideas, propositions and

solutions to difficult problems were a big help in publishing the conducted research and

putting this work together.

The research was supported in big parts by the University of Stuttgart, in particular by

Priv-Doz. Dr. Stephan Rudolph at the Institute of Aircraft Design. I can not thank

you enough for all the hours spent with white paper, pencil and coffee, sketching out

and constructing this research and guiding me through emotional and intellectual high

mountains and deep valleys during my time as a PhD student. Without your help this

work would have not happened!



Further, my thanks goes to Prof. Dr. Andreas Vogelsang at the Berlin Institute of

Technology for ideas, comments and critics that helped shaping this work. In addition,

I want to thank Robin Loose from the Department of Mathematics at the University of

Münster for his effort and help with the mathematical foundation of the work.

Last, I want to thank my family for their support, help and advice throughout the almost

six years that this project consumed. Thanks to my parents Andrea & Ulrich Walter for

everything they supported me with during this time. Thanks to my siblings Jonas & Lea

Walter which were always curious and interested in what I did. Finally, I want to thank

my wife Christina Colondres Walter for her patience, kindness and support whenever it

was needed.

This said, I let the reader now explore this work and hope that it sparks some inspira-

tion and discussion. It hopefully resolves some questions and might raise some additional

ones, but this is what science is all about.

Benedikt Walter



Contents i

Contents

List of Figures v

List of Tables vi

List of Abbreviations viii

Abstract x

Kurzfassung xii

1. Introduction 1
1.1. Automotive Knowledge Representations . . . . . . . . . . . . . . . . . . 4
1.2. Objective and Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3. Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4. Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2. Background and State of the Art 11
2.1. Graph-Based Design Assumptions . . . . . . . . . . . . . . . . . . . . . . 12

2.1.1. Graph-Based Design Languages . . . . . . . . . . . . . . . . . . . 13
2.1.2. Graph-Based Design Language Applications . . . . . . . . . . . . 15
2.1.3. Requirements and Tests in Graph-Based Design . . . . . . . . . . 21

2.2. Automotive Systems Engineering Methodology . . . . . . . . . . . . . . . 22
2.2.1. Requirements Engineering . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2. Testing - Verification and Validation . . . . . . . . . . . . . . . . 27

2.3. Knowledge Representations in Systems Engineering . . . . . . . . . . . . 33
2.3.1. Natural Language . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3.2. Language Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.3. Finite State Machines . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3.4. First Order and Temporal Logic . . . . . . . . . . . . . . . . . . . 49
2.3.5. Deterministic versus Non-Deterministic Systems . . . . . . . . . . 58
2.3.6. Modeling Structures: Trees versus Graphs . . . . . . . . . . . . . 60

3. Requirements Formalization Process Chain 63
3.1. Model Overview - Full Process Chain . . . . . . . . . . . . . . . . . . . . 64
3.2. Natural Language to Specification Patterns . . . . . . . . . . . . . . . . . 65

3.2.1. Selecting Dwyer’s Specification Pattern Systems (SPS) . . . . . . 66
3.2.2. Elicitation and Documentation as Text and Conversion to Patterns 70
3.2.3. Elicitation and Documentation as Patterns . . . . . . . . . . . . . 74



ii Contents

3.3. Specification Patterns to Linear Temporal Logic . . . . . . . . . . . . . . 76
3.3.1. Empirical Validation of SPS to LTL Mappings . . . . . . . . . . . 77
3.3.2. Qualitative Conversion of Patterns to Logic . . . . . . . . . . . . 79

3.4. First Order Logic - Special Modeling Structures . . . . . . . . . . . . . . 84
3.4.1. Data Structure as an Enabler to Map LTL Expressions to FOL . 86
3.4.2. Mapping LTL on Directed One-Branch Trees . . . . . . . . . . . . 91

3.5. First Order Logic - Generalized Modeling Structures . . . . . . . . . . . 95
3.5.1. Extending Modeling Structures from Trees to Graphs . . . . . . . 95
3.5.2. Mapping Linear Temporal Logic on Directed Cyclic Graphs . . . 97

3.6. First Order Logic - Conjunctive Normal Form . . . . . . . . . . . . . . . 100

4. Formalization Process Chain Application 105
4.1. Formalization of Test Cases . . . . . . . . . . . . . . . . . . . . . . . . . 106

4.1.1. Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.1.2. Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.1.3. Processing Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.1.4. Application: Test Case Redundancy . . . . . . . . . . . . . . . . . 110
4.1.5. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.2. Post-processing of Formalized Test Cases . . . . . . . . . . . . . . . . . . 113
4.2.1. Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
4.2.2. Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.2.3. Processing Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.2.4. Application: Test Set Restructuring . . . . . . . . . . . . . . . . . 121
4.2.5. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

4.3. Requirements Formalization - State Machines . . . . . . . . . . . . . . . 124
4.3.1. Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
4.3.2. Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4.3.3. Processing Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4.3.4. Application: State Machine Representation . . . . . . . . . . . . . 131
4.3.5. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

4.4. Requirement Models - Executable State Machines . . . . . . . . . . . . . 136
4.4.1. Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.4.2. Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.4.3. Processing Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.4.4. Application: C-Code Generation . . . . . . . . . . . . . . . . . . 141
4.4.5. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

5. Conclusion and Outlook 147
5.1. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
5.2. Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
5.3. Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

5.3.1. Deriving Requirements Directly from Physics . . . . . . . . . . . 153
5.3.2. Automated System Design and Executable V-Model . . . . . . . . 153
5.3.3. Further Analysis of Formalized Test Cases and Requirements . . . 154



Contents iii

5.3.4. Extension of Case-Based LTL to FOL Mapping . . . . . . . . . . 155

A. Mapping SPS to LTL (full) 157

B. Mapping LTL to FSM (full) 163

C. Publications 183

D. Bibliography 185

E. Curriculum Vitae 195





List of Figures v

List of Figures

1.1. Development Process: V-Model (MBC) . . . . . . . . . . . . . . . . . . . 2
1.2. Knowledge Representation: Language and Logic Space . . . . . . . . . . 5

2.1. Graph-Based Design: Primitives, Rules and Design Graph Adaptation . . 16
2.2. Graph-Based Design: Process Overview . . . . . . . . . . . . . . . . . . . 17
2.3. Graph-Based Design: Design Graph Adaptations . . . . . . . . . . . . . 18
2.4. Graph-Based Design: System Design (Example) . . . . . . . . . . . . . . 20
2.5. Product Development Process: Function . . . . . . . . . . . . . . . . . . 23
2.6. Product Development Process . . . . . . . . . . . . . . . . . . . . . . . . 24
2.7. Knowledge Representation: Knowledge Levels . . . . . . . . . . . . . . . 33
2.8. Knowledge Representation: Informal and Formal . . . . . . . . . . . . . . 35
2.9. Knowledge Transfer: Inference (Example) . . . . . . . . . . . . . . . . . 36
2.10. Automata: Overview - Automata classes . . . . . . . . . . . . . . . . . . 43
2.11. Automata: Finite State Machine Structure . . . . . . . . . . . . . . . . . 45
2.12. Automata: State Machine Classification . . . . . . . . . . . . . . . . . . 46
2.13. Graph Representation: State-Transition Relation . . . . . . . . . . . . . 53
2.14. Graph Representation: Time Dependent Systems . . . . . . . . . . . . . 54
2.15. Graph Representation: Sequence-Based Order - Edge Path . . . . . . . . 56
2.16. Logic Representation: LTL Operator ‘Next’ ◦ (Example) . . . . . . . . . 57
2.17. Logic Representation: LTL Operator ‘Global’ � (Example) . . . . . . . . 57
2.18. Graph Representation: Directed Tree and Directed Cyclic Graph Structure 60

3.1. Formalization Process Chain: NL to CNF . . . . . . . . . . . . . . . . . 64
3.2. Requirements Engineering: Elicitation and Documentation . . . . . . . . 65
3.3. Testing: Test Case Structure and Description . . . . . . . . . . . . . . . 70
3.4. Testing: Test Step Structure and Description . . . . . . . . . . . . . . . . 71
3.5. Graph Representation: One Branch Directed Tree - General Structure . . 86
3.6. Testing: Test Case Structure - Link-Extension . . . . . . . . . . . . . . . 86
3.7. Logic Representation: Operator ‘Next’ ◦ (Time-Discrete) . . . . . . . . . 87
3.8. Logic Representation: Operator ‘Global’ � (Time-Discrete) . . . . . . . . 88
3.9. Logic Representation: Operator ‘Until’ U (Time-Discrete) . . . . . . . . 89
3.10. Logic Representation: Operator ‘Future’ � (Time-Discrete) . . . . . . . . 90
3.11. System Specification Approaches: Top-Down and Bottom-Up . . . . . . . 96
3.12. System Graph Representation: Test . . . . . . . . . . . . . . . . . . . . . 96
3.13. System Graph Representation: Requirement . . . . . . . . . . . . . . . . 97

4.1. System Representation: Class Diagram (Generic) . . . . . . . . . . . . . 110



vi List of Tables

4.2. System Representation: Execution Diagram (Generic) . . . . . . . . . . . 111
4.3. System Representation: Design Graph . . . . . . . . . . . . . . . . . . . 111
4.4. State Space: Parameter Representation (Example) . . . . . . . . . . . . . 115
4.5. State Space: Cost Metric - Test Case (Example) . . . . . . . . . . . . . . 116
4.6. Test Set Reordering: Redundancy Detection (Example) . . . . . . . . . . 117
4.7. Test Set Reordering: Clustering Test Steps (Example) . . . . . . . . . . . 118
4.8. Test Set Reordering: Clustering Test Steps (Example) . . . . . . . . . . . 120
4.9. Test Set Reordering: Overall Process (Example) . . . . . . . . . . . . . . 120
4.10. Test Set Reordering: Execution Diagram (Extension) . . . . . . . . . . . 121
4.11. Test Set Reordering: Evaluation - Overall Cost . . . . . . . . . . . . . . 123
4.12. State Machine Generation: Execution Diagram (Extension) . . . . . . . . 131
4.13. State Machine Generation: Overall Process . . . . . . . . . . . . . . . . . 132
4.14. State Machine Validation: Comparison (Manual / Automatic) . . . . . . 133
4.15. Formalization Process Chain: NL to System FSM . . . . . . . . . . . . . 138
4.16. Dynamic State Machine Generation: Input / Output Layer . . . . . . . . 140
4.17. Dynamic State Machine Generation: Overview (Example) . . . . . . . . 141
4.18. Dynamic State Machine Generation: Communication Layer . . . . . . . . 142
4.19. Dynamic State Machine Generation: Execution Diagram (Extended) . . 143

5.1. Formalization Process Chain: NL to CNF . . . . . . . . . . . . . . . . . 148

List of Tables

3.1. Conversion: Text to Patterns (Example) . . . . . . . . . . . . . . . . . . 72
3.2. Case Study: SPS Patterns and Scopes . . . . . . . . . . . . . . . . . . . 78
3.3. Logic Operators: Nomenclature . . . . . . . . . . . . . . . . . . . . . . . 79
3.4. Mapping: SPS to LTL (all Patterns - Scope: ‘Globally’) . . . . . . . . . . 80
3.5. Mapping: SPS to LTL (all Scopes - Pattern: ‘Universality’) . . . . . . . . 81
3.6. Conversion: SPS to LTL - Test Case (Example) . . . . . . . . . . . . . . 82
3.7. Conversion: SPS to LTL - Requirement (Example) . . . . . . . . . . . . 84
3.8. Conversion: LTL to FOL - Test Case, Step 1 + 2 (Example) . . . . . . . 92
3.9. Conversion: LTL to FOL - Test Case, Step 3 + 4 (Example) . . . . . . . 93
3.10. Conversion: LTL to FOL - Test Case, All Steps (Example) . . . . . . . . 94
3.11. Conversion: SPS to LTL (Operator: ‘Global’ �) . . . . . . . . . . . . . . 98
3.12. Conversion: SPS to LTL (Operator: ‘Until’ U) . . . . . . . . . . . . . . . 98
3.13. Conversion: SPS to LTL (Operator: ‘Next’ X) . . . . . . . . . . . . . . . 99
3.14. Conversion: SPS to LTL (Operator: ‘Future’ �) . . . . . . . . . . . . . . 99
3.15. Conversion: SPS to LTL to FSM - Requirement (Example) . . . . . . . . 100
3.16. Conversion: FOL to CNF - Test Case (Example) . . . . . . . . . . . . . 103



List of Tables vii

4.1. Chapter Structure - Publication Overview . . . . . . . . . . . . . . . . . 105
4.2. Case Study: System Metrics I (OLC / ILS) . . . . . . . . . . . . . . . . 108
4.3. Conversion: Full Process Chain - Test Step (Example) . . . . . . . . . . 109
4.4. Case Study: Review Findings (Manual / Automated) . . . . . . . . . . . 112
4.5. State Space: Parameter Representation (Example) . . . . . . . . . . . . . 114
4.6. Case Study: System Metrics II (OLC / ILS) . . . . . . . . . . . . . . . . 116
4.7. Case Study: Evaluation (Clustering + Similarity) . . . . . . . . . . . . . 122
4.8. Case Study: Evaluation (Path Finding) . . . . . . . . . . . . . . . . . . . 122
4.9. Case Study: System Metrics I (AOLC) . . . . . . . . . . . . . . . . . . . 126
4.10. Conversion: SPS to Requirement FSM . . . . . . . . . . . . . . . . . . . 128
4.11. Case Study: Evaluation I (System FSM) . . . . . . . . . . . . . . . . . . 134
4.12. Case Study: System Metrics II (AOLC) . . . . . . . . . . . . . . . . . . . 137
4.13. Conversion: SPS to System FSM (Example) . . . . . . . . . . . . . . . . 139
4.14. Case Study: Evaluation II (System FSM) . . . . . . . . . . . . . . . . . . 144

A.1. Mapping: SPS to LTL (Pattern: ‘Universality’) . . . . . . . . . . . . . . 157
A.2. Mapping: SPS to LTL (Pattern: ‘Absence’) . . . . . . . . . . . . . . . . 158
A.3. Mapping: SPS to LTL (Pattern: ‘Existence’) . . . . . . . . . . . . . . . . 158
A.4. Mapping: SPS to LTL (Pattern: ‘Bounded Existence’) . . . . . . . . . . 158
A.5. Mapping: SPS to LTL (Pattern: ‘Response’) . . . . . . . . . . . . . . . . 159
A.6. Mapping: SPS to LTL (Pattern: ‘Response Chain I’) . . . . . . . . . . . 159
A.7. Mapping: SPS to LTL (Pattern: ‘Response Chain II’) . . . . . . . . . . . 159
A.8. Mapping: SPS to LTL (Pattern: ‘Precedence’) . . . . . . . . . . . . . . . 160
A.9. Mapping: SPS to LTL (Pattern: ‘Precedence Chain I’) . . . . . . . . . . 160
A.10.Mapping: SPS to LTL (Pattern: ‘Precedence Chain II’) . . . . . . . . . . 160
A.11.Mapping: SPS to LTL (Pattern: ‘Constrained Chain Pattern’) . . . . . . 161



viii Abbreviations

Acronyms

AOLC Adaptive Outside Light Control

Atomic FSM Atomic Finite State Machine

Atomic Requirement FSM Atomic Requirement Finite State Machine

CAD Computer-Aided Design

CFD Computational Fluid Dynamics

C-HIL Compoenent-HIL

CNF Conjunctive Normal Form

CTL Computational Tree Logic

DBSCAN Density-Based Spatial Clustering

DC43 Design Cockpit 43

DNF Disjunctive Normal Form

E/E electric/electronic

FEM Fintite Element Analysis

FMU Functional Mock-Up

FOL First Order Logic

FSM Finite State Machine

GIL Graphical Interval Logic

GUI Graphical User Interface

HIL Hardware-in-the-Loop

ICSFSM Incomplete Specified Finite State Machine

IEEE Institute of Electrical and Electronics Engineers

ILS Intelligent Light System

ISO International Organization for Standardization

ISTQB International Software Testing Qualifications Board

K-Means Centroid Based



Abbreviations ix

LHS Left-Hand Side

LTL Linear Temporal Logic

M2M Model-to-Model

M2T Model-to-Text

MBC Mercedes-Benz Passenger Cars

Mealy DFSM Mealy Deterministic FSM

Mealy FSM Mealy Finite State Machine

MIL Model-in-the-Loop

Moore DFSM Moore Deterministic FSM

Moore FSM Moore Finite State Machine

NFR Non-Functional Requirement

NL Natural Language

OEM Original Equipment Manufacturer

OLC Outside Light Control

PDP Product Development Process

PNDFSM Partially Non-Deterministic Finite State Machine

ReqIF Requirements Interchange Format

Requirement FSM Requirement Finite State Machine

RHS Right-Hand Side

SIL Software-in-the-Loop

SLINK Hierarchical Single-Linkage

SPS Specification Pattern Systems

STG State-Transition Graph

System FSM System Finite State Machine

T2M Text-to-Model

UML Unified Modeling Language



x Abstract

Abstract

The current control systems in the automotive domain exceed more and more often

the size where engineers can manually perform certain tasks in the field of requirements

engineering. Even for humans it is hardly possible to compare 2000 or more requirements

in natural language form for correctness, consistency or completeness. One solution to

this problem is to achieve a machine-readable representation form of the requirements

in order to automate these tasks. This approach results in a knowledge transformation

process that can be applied to automotive requirements and tests. With this process,

requirements can be converted from textual representation into a machine-readable form.

Such a representation shall here be called ‘formalized’ representation.

The most important result of this work is an approach which allows to process such for-

malized representations. The processing of formalized representations can be automated

to perform decision making for system design decisions, analytical processing and rea-

soning about the system and code generation within in the system design process. The

derived formalization process can be broken down into the following parts: The initial

natural language representations of requirements and tests are at first converted manu-

ally (by an engineer) to logic expressions with the use of specification patterns. These

patterns are re-used from preexisting work. Logic expressions allow sequential boolean

transformations and all further transformations can therefore be proven to be analytically

correct. The initial logic representation occurs in linear temporal logic, which is compact

but not explicit for a particular state in a system. Transformation to first order logic

and reordering in conjunctive normal form achieves a state-wise explicit normal form.

A representation of requirements and tests in state-wise conjunctive normal form allows

for reasoning about redundancy and consistency for a given set of requirements or tests.

These state-wise represented requirements can be merged into one single state machine

which represents the overall system. The derived system state machine is analytically

correct and provides the basis for further analysis.

The consequences of the existence of such an analytical correct conversion process is,

that the problems of correctness, consistency and completeness are closely connected

to a representation problem. These problems may be solved whenever an initial semi-



Abstract xi

formal, pattern-based representation can be established. The introduced processing chain

is described with a step-wise conversion, illustrated with examples for requirements and

tests. Correctness, consistency and completeness of requirements or tests for a system

can be shown with a system representation in form of state machines. This work shows a

solution to convert logic expressions into dynamic finite state machines. The correctness

and applicability of this approach are illustrated with industrial case studies. The for-

malized representation form shown in the approach allows to addresses the problems of

requirements with respect to correctness, consistency and transformation between equiv-

alent representation forms. In addition, the effects of scalability through application to

industrial systems are investigated and discussed.

Overall, this approach achieves a formalization process for requirements and tests. It

shows the correctness, applicability and scalability of the process and its conversion

steps in industrial contexts. Therefore this approach represents a solution approach to

the problem of automated requirements processing. This approach represents one solu-

tion to integrate the domain of requirements engineering within a fully digital system

design process.



xii Kurzfassung

Kurzfassung

Die Systeme im Automotivbereich überschreiten mehr und mehr eine Größe, bei der In-

genieure in der Lage sind, bestimmte Tätigkeiten im Requirements-Engineering manuell

durchzuführen. Es ist nur schwer möglich oder übersteigt sogar die menschlichen Fähig-

keiten 2000 oder mehr Anforderungen in natürlicher Sprache auf Korrektheit, Konsistenz

und Vollständigkeit zu prüfen. Eine Lösung für dieses Problem ist ein Ansatz zur For-

malisierung der Anforderungen, um diese Tätigkeiten zu automatisieren. Daher wird in

dieser Arbeit ein Ansatz entwickelt, der zur Wissensformalisierung von Anforderungs-

und Testdaten im Automotivbereich genutzt werden kann. Mit diesem Prozess können

die textuellen Anforderungen in maschinenlesbare Form gebracht werden. Solch eine

Darstellung soll hier als ‘formalisiert’ bezeichnet werden.

Das wichtigste Ergebnis dieser Arbeit ist ein Ansatz, der es ermöglicht, solche formal-

isierten Darstellungen zu verarbeiten. Das Verarbeiten formaler Darstellungen kann au-

tomatisiert werden, um Entscheidungen im Entwurfsprozess zu treffen, das Ziehen und

Verarbeiten von logischen Schlussfolgerungen über das System zu unterstützen und Code-

Generierung im Systementwurf zu ermöglichen. Der entwickelte Formalisierungsprozess

kann in die folgenden Schritte aufgeteilt werden: Die ursprünglich in natürlicher Sprache

dargestellten Anforderungen und Tests werden zunächst manuell (von einem Ingenieur) in

logische Ausdrücke überführt. Hierzu werden bereits existierender ‘Specification Patterns’

genutzt. Logische Ausdrücke ermöglichen sequenzielle boolesche Umformungen, daher

sind alle folgenden Umformungen mathematische beweisbar und somit korrekt. Die erste

Darstellung in logischen Ausdrücken erfolgt in Form von Linear Temporal Logik. Diese

Darstellungsform ist kompakt, aber nicht für jeden Zustand explizit, da zeitliche Ab-

hängigkeiten in innerhalb eines Statements enthalten sind. Umformungen in Prädikaten-

logik und Sortieren in Konjunktiver Normalform erzeugt eine zustandsweise explizite

Normalform. Darstellung von Anforderungen und Tests in zustandsweiser Konjunktiver

Normalform ermöglicht damit logische Schlussfolgerungen über Redundanz und Konsis-

tenz eines Datensatzes von Anforderungen oder Tests. Die Darstellung von Anforderun-

gen in einzelnen Zuständen kann in einen einzelnen Zustandsautomaten überführt wer-

den. Dieser Zustandsautomat stellt damit das gesamte System dar und ist analytisch

korrekt. Dies bildet die Grundlage für weitere Untersuchungen.



Kurzfassung xiii

Die Konsequenz der Existenz eines solchen analytisch korrekten Transformationsprozesses

ist, dass die Fragen nach Korrektheit, Konsistenz und Vollständigkeit eng mit einem

Darstellungsproblem verknüpft ist. Die genannten Fragen können mit diesem Ansatz

beantwortet werden, wenn eine initiale, teil-formale, schablonen-basierte Darstellung

erzeugt werden kann. Die eingeführte Prozesskette ist mit einer schrittweisen Trans-

formation anhand von Beispielen für Anforderungen und Tests dargestellt. Korrektheit,

Konsistenz und Vollständigkeit von Anforderungen und Tests für ein System können mit

einer Darstellung dieses System in Form eines Zustandsautomaten gezeigt werden. Diese

Arbeit zeigt eine Lösung zur Transformation von logischen Ausdrücken in finiten Zus-

tandsautomaten. Die Korrektheit und Anwendbarkeit dieses Ansatzes wird mit indus-

triellen Fallstudien gezeigt. Die im Ansatz gezeigte formale Repräsentation ermöglicht es,

die Fragen nach Korrektheit, Konsistenz und Umformung zwischen verschiedenen äquiv-

alenten Repräsentationsformen zu adressieren. Zusätzlich wurden die durch Skalierung

entstehenden Effekte in industriellen Anwendungen untersucht und diskutiert.

Zusammenfassend wird in dieser Arbeit ein Ansatz zur Formalisierung von Anforderun-

gen und Tests eingeführt. Es werden Korrektheit, Anwendbarkeit und Skalierbarkeit des

eingeführten Prozesses und der einzelnen Verarbeitungsschritte im industriellen Kontext

gezeigt. Daher kann der gezeigte Ansatz als eine Lösung zur automatisierten Verar-

beitung von Anforderungen betrachtet werden. Der Ansatz stellt eine Lösung dar, die

Disziplin des ‘Requirements Engineerings’ in den Kontext des digitalen Produktentwurfs

zu integrieren.





1. Introduction

”Complexity increases when variety

(distinction) and dependency (con-

nection) of parts or aspects increase”

Francis Heylighen [Hey99]

There is a trend in the automotive industry towards a rising number of components with

a technological contribution to the car functionality. This is perceivable in technolo-

gies like autonomous driving, which is based on a strongly connected interplay between

many hardware and software elements. Sensors such as lidar, radar and camera deliver

input and feed a prediction algorithm based on a neuronal network. Neuronal networks

are already in use for object detection in today’s car while prediction algorithms are

in development. Another example is the connected car in an ‘internet of things’ -like

surrounding with constant interaction between car, passengers, environment, other local

cars and global traffic flows. Autonomous driving and connected cars are just two of

many examples for this trend towards increasing technological complexity increase. In

addition, customers expect to choose between many model variants and expect the car

of choice to be customizable based on personal preferences. Heylighen [Hey99] defined

complexity through a combination of two factors: Increase in variety and increase in

dependency. Extension of model lines and the mentioned desire for customization affects

the variety of designed and produced variants. This increase leads to bigger systems

with increased dependencies. It is therefore fair to say that automotive development

is experiencing a tremendous increase in complexity. In addition, pressure from other

industries, e.g. mobile communications, requires faster technology introduction times.

Shorter time-to-market causes development cycles to drop. This puts high demands on

the automotive development processes and challenges existing development paradigms.

The state-of-the-art development process in the automotive industry is the V-model

shown in Figure 1.1. It was adapted from the waterfall model, which can be seen as

1



2

the first formally described development process. It contains phases for specification,

development and testing of a product. While the waterfall model creates a structure for

all listed development steps, it lacks flexibility in case of changes and arising problems.

For complex systems, the waterfall model is rather slow and static. It cannot adjust to

today’s challenges and required flexibility.

Figure 1.1.: Development Process: V-Model (MBC)

In contrast, the V-model (with the same lack of flexibility), while providing the same

vertical continuity as the waterfall model, adds horizontal continuity. All levels (compo-

nent, system and vehicle) create a link between tests and the corresponding requirements.

While the V-model seems generally appropriate for the given challenges in automotive

system development, the representation of its requirements and tests, as observed in

current industrial projects, is clearly outdated. The standard as of today is the rep-

resentation of requirements and tests in the form of textual (test) specification docu-

ments. This is not a particular characteristic. In industrial projects, the V-model and

textual representation of requirements and tests are, in fact, bundled. Textual repre-

sentations of requirements are easier to create and are needed in non-technical contexts

(e.g. management, law, marketing), yet limited ambiguity and limited consistency of

the representation structure prevents machine-based inference to a high degree. The

increased complexity (more product variants and higher degree of inter-dependencies)



CHAPTER 1. INTRODUCTION 3

requires a more suitable representation form that can express the system complexity

and allows computer-based assistance in the form of knowledge inference on the data

set in use. Model-based representations fulfill the inference capability for requirements.

While this resolves an existing problem, a new problem has to be addressed: the still

needed textual representation and the model representation require consistency. The

logical solution is a Text-to-Model (T2M) or Model-to-Text (M2T) transformation (see

Section 3.2). Another challenge arises from the development model in common use of

today for automotive systems. The state-of-the-art method in the automotive industry

is that, after requirements are elicited and documented in a system specification, Orig-

inal Equipment Manufacturers (OEMs) outsource part of their system development to

suppliers and service providers. After the component development is finished by the

supplier, the system must be integrated within the existing system. Simply said: OEMs

specify systems but development is (in part) done outside the company and the OEMs

only integrate and test the development afterwards. The number of participants, the

challenges associated with correct interface definitions between systems, and the efforts

to achieve consistency during system integration put high demands on (test) specification

and system verification and validation. Therefore, the field of verification and validation

is burdened by the same problems as the domain of requirements engineering.

This work is concerned with the challenge to provide a sufficient method to bridge the

gap between textual and model-based specification. It assists automotive systems engi-

neering in two ways: First, it supports development by providing a consistent conversion

of textual requirements into executable system state machines. This supports model-

based system development efforts. Second, it benefits the system integration process due

to the formal representation of test specifications. The derived formalism allows detec-

tion of redundancy, inconsistency and unambiguity of test statements. Post-processing

of detected redundancies significantly reduces test efforts by reducing overall test loads.

Textual representation of requirements occurs mostly on the system and product level.

Similarly, the integration problem of externally developed components and systems into a

final product (system of systems) occurs on the system level. Therefore, the scope of this

work is limited to the higher development levels, particularly the system level. The scope

is further limited since model-based representations are suited for functional requirements

but might lack the ability to represent Non-Functional Requirements (NFR). An average

system specification at Mercedes-Benz Passenger Cars (MBC) contains about 2000 state-

ments, of which about 1100 are functional requirements, 500 are NFR and 400 are head-



4 1.1. AUTOMOTIVE KNOWLEDGE REPRESENTATIONS

ings and information statements. Subsection 2.2.1 contains an in-depth discussion about

requirements and the differentiation between functional and non-functional requirements.

NFR and their tests commonly maintain their textual representation throughout the de-

velopment process due to the non-existence of a more formal expression. Therefore,

this work is limited to functional requirements and its tests. Functional requirements

are validated through functional tests and integration tests. Empirically observed, an

average system at MBC contains, as previously mentioned, about 1100 functional re-

quirements where on average for one functional requirement about 1.7 test cases are

designed [WHPR17]. The intention of this work is to improve such systems designs in

regards to their functional requirements and test representations in order to assist spec-

ification and integration efforts.

1.1. Automotive Knowledge Representations

State-of-the-art in automotive system development at MBC is that the majority of

functional requirements and tests on the system level are described in textual form.

While different approaches exist to describe systems and their requirements via models

(e.g.: state machines), as of today, the vast majority of system descriptions for require-

ments and tests at MBC exist in natural language form. Projects that use v-model-based

approaches do not provide a consistent textual representation. There exists no widely

used approach to maintain both forms (text and model) in a consistent coexistence with-

out manual conversion and updating. At the same time, natural language expressions

are prone to contain subjective meaning. Natural language is ambiguous. For knowledge

representations, specifically in the domain of engineering design, this turns out to be

problematic. One approach to reduce this problem is grammar limitation (reduced syn-

tax) in combination with a reduced description vocabulary. Knowledge represented in

natural language is transformed through surjective mapping into limited grammar repre-

sentation in the limited grammar and syntax space as shown in Figure 1.2. Because the

mapping occurs in a non-mathematical domain (language space), rules and operations

that apply in mathematical domains cannot necessarily be used to perform or validate

the mapping. This is a language-related problem which is beyond the scope of this work

and therefore will not be discussed further. Such a representation will from now on be

called structured language.



CHAPTER 1. INTRODUCTION 5

From structured language representation and its language space, expressions can be

transferred to the mathematical space, specifically logic space (see Figure 1.2). In that

space, objective rules apply and mathematical operations can be performed. System

descriptions may contain time-dependent elements represented in temporal logic. By

applying time-related boundary conditions, these elements can be represented in a time-

discrete form. For such a representation, the number of operators can be reduced. All

time-dependent operators are obsolete and only time-independent operators remain in

the local representation. This reduction is a surjective mapping from first order and

temporal logic space to First Order Logic (FOL) space. For an unambiguous representa-

tion form, the knowledge can be represented in a standardized form. This standard form

opens up the possibility for a formal system representation that allows knowledge in-

ference and general machine-based data processing. The described transformation from

natural language to restricted grammar, mapping to logic space and reduction of tempo-

ral elements towards a time-independent local representation is the core principle derived

and discussed in this work.

Figure 1.2.: Knowledge Representation: Language and Logic Space

The practical implementation of such a formalization model can be realized through

a central graph-based data model. To derive such a model, existing data has to be

preprocessed. Two forms of preprocessing shall be distinguished in this work: Prepro-

cessing of the modeling structure and content processing via description formalization.

Subsection 2.1 discusses modeling structure while Section 2.3 explains the principles of

data formalization in detail. The raw data for general automotive system descriptions

consists of a decentralized collection of documents. These documents contain system-

related data sets including requirement and test descriptions. All data is stored in a

requirement management tool in a tool-specific data format. System modeling must ful-



6 1.2. OBJECTIVE AND VISION

fill two needs. First, data has to be transformed into a tool-independent data format.

This allows use of a variety of tools and secures data accessibility for a long time pe-

riod. (This es becoming increasingly relevant, for example in context of the functional

safety, where car manufacturers are required to provide long-term proof for certain sys-

tem development and testing procedures to ensure quality standards). In addition, an

integral, central data model provides further advantages in terms of data optimization.

This generates visibility for data dependencies, increases traceability and simplifies data

re-usability (manipulation, deriving domain-specific and tool-specific models). Graph-

based design languages are used for data modeling. The building blocks of graph-based

design languages are defined axioms (vocabulary) and execution rules (data manipu-

lation). Starting with one axiom, rules are applied in sequential order to manipulate

the axiom and its mutation. The result can be represented in a design graph. Such a

design graph therefore contains all design decisions in an abstract form. The abstract

representation can generate domain-specific models for domain-specific analysis.

1.2. Objective and Vision

This work intends to provide a formalization method for requirements and test rep-

resentations to improve requirements management methods in terms of requirements

engineering. The approach intends to solve two problems: It bridges the gap between

textual and model-based requirement expressions during specification and downstream

development steps. In addition, formalization for tests improves system integration ef-

forts by reducing redundancies, inconsistencies and ambiguities in test expressions. This

significantly reduces test loads and supports the system integration process.

Any form of data formalization requires an underlying ontology for data representation.

The ontology used in this work is a so-called graph-based design language. Graph-based

design languages in Unified Modeling Language (UML) can be used to generate fully (or

partially) automated product designs. Rudolph et al. propose one particular approach

[AR03, AR04] which includes an underlying graph-based design methodology and a soft-

ware called Design Cockpit 43 (DC43) [IIL17a, IIL17b]. This work intends to show how

formalization of system descriptions, particular requirements and test data can support

industrial system design. To achieve this, the goal of this work is to derive a require-

ments and test formalization methodology consistent with the given graph-based design

approach by Rudolph et al. [AR03, AR04]. The developed methodology in this work



CHAPTER 1. INTRODUCTION 7

allows system specification engineers to specify requirements in structured textual form

and derive consistent model representations. Adjustments to the requirements lead to

changes in the model which can be observed in real-time during the specification phase

by executing the derived model. In order to prove the correctness and usefulness of the

derived models, case studies are performed and evaluated at MBC development. Simi-

lar to the improvements for requirements engineering, the proposed approach can assist

test efforts during system integration. The formal representation of test cases and its

test steps enables machine-based analysis of redundancies, inconsistencies and ambigui-

ties for test data. Particular the occurrence of redundant test steps is investigated and

evaluated in industrial case studies. This includes a heuristic post processing to remove

redundant test steps inside a forward directed chain of test steps. A case study evaluates

the heuristic approach and shows potential a test load reduction. Overall, requirements

engineering and system integration efforts will be assisted by a formalization method.

The vision for this work is that the derived formalization approach bridges the gap be-

tween (informal) requirements engineering and digital product development via a manual

transformation step. The conversion T2M shown in this work provides a basis for model-

based systems engineering and model-based product design. The Model-to-Model (M2M)

transformations make it possible to derive a model of the digital product based on its

(formalized) requirements. Therefore, the approach described in this work, leads the way

to a formal and closed process chain for digital product development along the V-model.

Consequently this leads to the vision of a ‘machine-executable V-model’.

1.3. Contributions

The main contribution of this work is the creation of a formalization process chain for

(automotive) requirements and tests. The creation of the formalization process chain is

achieved by combining three separately preexisting approaches into one:

- Specification patterns [DAC98] (conversion of language patterns to temporal logic)

- State-wise representation of linear temporal logic into first order logic [AF00]

- Transformation of logic expressions to state machines [LL12],[KVBSV12]

Each approach existed in isolation for a subset of the overall problem. The combination

of these approaches is performed in this work and leads to a single overall approach.



8 1.4. STRUCTURE

Further, this approach is validated against industrial data from MBC. It shows the

reduction in time effort and effort needed for specific requirements engineering tasks. In

addition, it addresses the possibility of automated data analysis.

1.4. Structure

This work consists of three core chapters and two framing chapters. The three core

chapters are a chapter about the theoretical background, a chapter on the new modeling

approach developed throughout this work and a chapter on industrial applications to

validate the model. These three chapters represent the center piece of this work while

the introduction and summary tie the overall idea and approach together.

Chapter 2 discusses the theoretical background and state of the art of the field. It is

separated into three blocks: Section 2.1 discusses the methodology and general idea of

graph-based design. This is used as the underlying modeling structure of the later de-

rived model. In Section 2.2, the state of the art for requirements engineering and testing

is shown. This is the particular industrial field in which this work takes place. The third

block consists of different forms of knowledge representation. Section 2.3 lays out all

knowledge representation forms relevant during the data processing as well as two brief

discussions about determinism in systems and modeling structures.

Chapter 3 derives a new approach to formalize requirements and test data. This chapter

is the center piece of the work. Section 3.1 provides the big picture with an overview of

the model. The following sections show and discuss the particular conversions between

representation forms. Section 3.2 addresses the mapping between natural language or

textual representations and structured textual representations in the form of language

patterns. In Section 3.3 mapping from language to logic space, particularly to temporal

logic, is shown. The next two sections discuss mapping from temporal logic to simple

and more complex structures. In Section 3.4, mapping for forward-directed chains is

shown. This is required to model and formalize test data. Section 3.5 is concerned with

the generalized case, e.g. mapping from temporal logic onto cyclic directed graphs. Such

structures mimic state machines. This allows requirements to be modeled and formal-

ized. In the last section, the transformation of local FOL representations into a normal

form is presented. This is shown in Section 3.6.



CHAPTER 1. INTRODUCTION 9

Chapter 4 provides four case studies to validate the derived model. Section 4.1 validates

the model for test cases which represent the most simple structural form, a forward

connected chain. To apply the model towards test cases in industrial contexts, a post-

processing is necessary. This is covered in Section 4.2. These two sections show the

potential improvements that can be achieved by the derived model in the field of system

testing. In Section 4.3, the approach is validated for more complex structures, in this

case, cyclic directed graphs. Requirements represented as finite state machines can be

represented in such structures. This application is the core application of this work. The

initially static finite state machine can be extended towards an executable state machine.

Section 4.4 extends the derived approach and makes it possible to dynamically control

the derived state machine.

Chapter 5 summarizes this work and closes with a conclusion. Relevant results are

discussed and put in context. The derived formalization method and its industrial ap-

plications are evaluated in Section 5.1. Limitations of the approach are addressed in

Section 5.2. Section 5.3 provides a brief outlook on related fields, further potential re-

search topics and remaining open questions.





2. Background and State of the Art

“The answer to the ultimate ques-

tion of life, the universe and every-

thing is forty-two.”

Douglas Adams,

The Hitchhiker’s Guide to the Galaxy

The goal of this work is “To derive a formalization process for requirements and test data

and to apply it to electric/electronic Systems (E/E Systems) at Mercedes-Benz passsenger

car development”. This shall be done to reduce the required time effort for requirements

engineering and to allow automated analysis of the data. In order to achieve such a

formalization process, existing principles and state-of-the-art work shall be considered.

There are three primary topics that build the foundation of this work: Graph-based de-

sign as the ontology, automotive systems engineering in regards to existing requirements

engineering and testing, and (selected) knowledge representation forms for the field of

system engineering.

Graph-based design in Section 2.1 introduces the underlying principles of the data model.

It includes a general discussion about the principles of design languages and outlines in

detail the approach used in this work to create, update and optimize the data model.

The work takes place in the context of requirements engineering and testing. Section 2.2

discusses the state of the art for systems engineering and, in particular, requirements

engineering and testing (verification and validation). This includes specific references

to the development model used, the definition and differentiation between forms of re-

quirements and the definition of test-related terms. The premise of this work is data

optimization through inference from formalized data. Data formalization for inference

is rooted in (formal) data representation. Section 2.3 includes an in-depth discussion of

the four representation forms used in this work. It is evaluated why natural language

is used as the state-of-the-art representation form and what problems arise from that.

11



12 2.1. GRAPH-BASED DESIGN ASSUMPTIONS

Different forms of specification patterns are introduced. It is shown how systems can

be represented in the form of state machines. In addition, two particular problems (de-

terministic versus non-deterministic) and modeling structures (chains versus divergent

forms) are discussed.

2.1. Graph-Based Design Assumptions

Graph-based design as a discipline is not naturally connected to requirements engineer-

ing. When requirements are represented in a formal representation form, an ontology

is needed. Therefore, in this work, graph-based design is used as the ontology for the

representation of the formalized data. Designing and building products is a difficult task.

It is obvious that in order to build the best or at least the most suitable product, even-

tually other design solutions have to be abandoned. The question is now rather: “How

do we assure that the most suitable solution becomes visible to us?” Design starts with

the whole solution space where in principle all designs are valid solutions. Every design

decision limits the solution space and with that the number of potentially valid solutions

is reduced. This continues, eventually to the point where “the most suitable” solution

lies outside the solution space. This happens not because of the wrong assumption that

the best solution, is actually not the best solution but because the solution space is con-

strained in an incorrect order (or with an unwise prioritization). To avoid such a scenario,

it is essential to select the order of design decisions carefully. It must be analyzed which

design decisions are necessary or inevitable (e.g. physical laws) and which decisions are

secondary because they are only based on personal taste or subjective metrics. A solu-

tion to the prioritization of design choices can be derived from the concept of abstraction.

“It is a fundamental idea in Piaget’s work on the development of logical and mathemat-

ical thinking that ideal objects such as abstract mathematical ideas have their origin in

the closure of such systems. Once a system is closed, the properties of the constituted

ideal object are no longer dependent on empirical experience. Rather, they are deter-

mined by the structure as a whole and can be elaborated by the operations of logical

and mathematical thinking”, as quoted by Damerow [Dam96] based on Piaget [Pia52].

The term closure in this context represents an assumed and established solution space.

Piaget points out that mathematical abstraction removes real world object influences,

perceived through empirical experience from the system described or envisioned. Re-

moving certain aspects increases the focus on the remaining aspects. Abstraction directs



CHAPTER 2. BACKGROUND AND STATE OF THE ART 13

attention to underlying inherent structure, dependencies and limitations put on a design

by physical laws and mathematical constraints. It becomes obvious, that in order to

prioritize design choices, an abstract representation can lead to the true solution space.

True solution space here is defined in the sense of a formally complete design space.

Such space remains once the initial solution space is reduced and limited by considering

underlying, non-negotiable constraints. It reveals the true solution space in which design

decisions, based on a personal chosen optimization metric (or simply personal taste) can

be made. To derive this true solution space, a design approach with a degree of abstrac-

tion seems suitable. One such approach are string-based, shape-based and graph-based

design languages. Design and creation take place in an abstract form. Interpretation of

symbolic representations performed by a compiler turns abstract symbols into concrete

design objects. While the abstract design approach includes underlying constraints and,

with that, limits the solution space, it reveals the left-over solution space (here called true

solution space). This true solution space is consistent with all non-negotiable constraints.

An example could be the use of a certain part which is made of a specific material. Any

material has a temperature range in which it can function properly. Therefore, the solu-

tion space is limited in the temperature dimension. All designs inside this space are valid

and can be chosen from. In Subsection 2.1.1, the general principles of design languages

are investigated, while Subsection 2.1.2 shows the particular approach that is used in

this work. Subsection 2.1.3 takes a first step in assessing how graph-based design can

support the task of improving requirement and test data.

2.1.1. Graph-Based Design Languages

It was discussed that abstraction includes the idea of revealing the underlying structure

or functionality of a design. Another aspect of abstraction is therefore analogy. Two ini-

tially seemingly different objects share commonalities that are revealed when analyzing

the abstract form of its inherent structure and functionality. One potential engineering

approach is to achieve design solutions by reasoning from analogies between the design

envisioned and an existing solution observed in another, already existing domain (or

product). The solution from the implementation layer in one domain can be abstracted.

In the abstraction layers, both domains share the abstracted problem and its abstract

solution. This analogy can be used to transfer the existing solution from the initial do-

main to the new domain, where it is transferred to the implementation layer.



14 2.1. GRAPH-BASED DESIGN ASSUMPTIONS

One prominent occurrence of this principle is the field of biomimetics, where solutions

observed in nature and biology are abstracted from and transferred to engineering. Often

times biology provides solutions that seem unintuitive to engineering design. Problem so-

lution in engineering is most often approached by decomposition from high level to more

fine grained structure and functionality. Such a top-down approach is in contrast to the

incremental bottom-up approach in nature and biology. Combinations of basic building

blocks create more complex entities with higher functionality. Simple mutations create

design variants and natural selection (Darwin [Dar68]) evaluates the variants. Underlying

the principle of bottom-up approaches is the fact that each variant at every moment has

to be in a stable state. This means that e.g. mass, energy and static equilibrium must

exist at any moment. A top-down approach can (potentially) be in an unstable state

at any moment until finished. Difficulties for top-down approaches lay in the fulfillment

of requirements. It is necessary to refine requirements into more low level requirements

and divide a product into meaningful parts so that every part can fulfill a subtask that

contributes to the overall task. Therefore, complexity lies in the decomposition.

For bottom-up approaches, the opposite is the case. The challenging task here is in

the fact that the composition of parts has to lead to a meaningful, functional product.

Therefore, for bottom-up approaches, complexity lies in composition. Classic engineering

prefers a top-down approach to fulfill (high level) requirements. As shown, complexity

here lies in decomposition of overall functionality into controllable fractional parts of

functionality. The same level of complexity occurs again, once the envisioned parts are

integrated. Because a moderate increase in size for each part leads to an exponential

increase in interfaces, this process experiences a tremendous (exponential) rise in overall

complexity. Complexity increases to a level where it is questionable whether such an

approach is feasible in the future without adjusting affected manual process steps and

automating these to handle the increase in work load. Another potential path out of this

problem is bottom-up approaches where complexity roots in a totally different area. The

challenge is to assure that composition actually solves the given problem. Therefore, the

process of composition has to be steered and guided in the right direction. This problem

is discussed in Subsection 2.1.1 and Subsection 2.1.3.

One form of a bottom-up approach in engineering are formal language grammars. The

combination of a number of primitives (building blocks) and a set of rules creates a

so-called production system. This allows for the generation of syntactically correct sen-



CHAPTER 2. BACKGROUND AND STATE OF THE ART 15

tences belonging to this grammar [AR03]. Formal language grammars occur in the form

of natural language, programming languages and other forms (e.g. L-System grammars

by Lindenmayer and Prusinkiewicz to describe plants [PL12, PH13]).

The construction of sentences occurs by using and combining vocabulary (building blocks)

in ways defined in execution rules. This creates syntactically correct sentences. To create

a semantic meaning, an interpretation for each symbol is performed, where each symbol

is assigned a particular meaning. The idea of a formal grammar with its underlying

production system can be abstracted. Higher forms are shape grammars where build-

ing blocks are lines and shapes instead of words [Sti80, GS80]. Another form of design

grammars are graph-based design languages [SR16, AR03, AR04]. The abstraction level

is increased further in such a way that the building blocks are generic nodes. Rules con-

nect these nodes, generating a so-called design graph. The design graph is abstract and

its symbolic interpretation becomes a key process step. The same graph, based on its

interpretation, can represent different entities in different domains. The generic gestalt

of a graph in graph-based design, opens a variety of application fields (different domains,

multi-domains and increased complexity). Alber et al. [AR03] describe the representa-

tion of information for each entity and the ordering structure as the two requirements

for a design language. A graph can hold structure, ordering and hierarchical information

while symbolic interpretation converts information stored as an attribute of a node into

meaningful forms. These characteristics make graph-based design a suitable approach

for the given problem set.

2.1.2. Graph-Based Design Language Applications

In Subsection 2.1.1, the concept of design languages and grammars was explained.

Graph-based design languages are the most abstract form of design grammars. Their

purpose is the creation of complex systems in a reproducible, traceable way. At first a

production system has to be defined. A production system contains primitives (build-

ing blocks) and a rule set. Building blocks are instantiated, sequentially combined and

evolved from primitives into increasingly complex entities through a given set of execu-

tion rules. Each execution rule represents a design decision and is applied based on its

call in the sequence diagram. This is explained more in detail later. Figure 2.1 shows a

rule set with generic rules. An example for a specific rule would be the design decision

to always place a damper between a wheel and the steering axis. In rule 3, the white



16 2.1. GRAPH-BASED DESIGN ASSUMPTIONS

node represents the abstract wheel, the shaded node represents the abstract damper and

the filled node stands for the abstract axis. The left side shows the ‘before’ (without

damper), while the right side shows the ‘after’ (including damper).

Figure 2.1.: Graph-Based Design: Primitives, Rules and Design Graph Adaptation

Instantiated elements and their progressions are represented in the design graph. Each

element is represented by a node and its dependencies by links. These principles are

illustrated in Figure 2.1. Each primitive element and each generated complex element

hereby can serve one of two functions at a time. First it serves as a new primitive where it

can be potentially evolved further through additional execution rules. Rule execution is

followed by compilation. Generally, each entity serves in its second function as a syntac-

tical placeholder for an element with a corresponding meaning. Mapping from element

as placeholder to element representing a syntactical meaning is called interpretation and

is achieved during compilation. This principle allows grammars and its corresponding

graphs to represent entities in all kinds of (engineering) domains. Graph-based design

languages require the creation of a domain-specific definition of primitives and rules.

These can be stored in a domain library. The creation of more and more libraries makes



CHAPTER 2. BACKGROUND AND STATE OF THE ART 17

graph-based design a widely applicable system design approach and opens up a variety

of opportunities for the design of complex systems.

Figure 2.2.: Graph-Based Design: Process Overview, Rudolph [Rud06]

An existing problem in design is the natural opposition between domain-specific expres-

siveness and generality. Domain-specific design can describe one particular domain well.

It uses domain-specific vocabulary (building blocks) to optimize a design variant in the

particular domain and the specific design space. The problem here is, that overall con-

sistency for all design domains is required. Given the fact that each domain can have

a unique design space, it is intrinsically not guaranteed that there exists a design vari-

ant with overall consistency for all domains. The obvious solution to achieve overall

consistency therefore would be a shared design space with a general model. Yet, the

generality which allows for consistency, is too generic for domain-specific problems and

thus limits the general model in terms of its domain-specific expressiveness. Solution to

this dilemma is a combination of a shared general model with derivatives to all particular

domains. Given that principle, it can be said there are three overall constraints that a

design language has to satisfy in order to be capable of representing a sufficient solution

for designing complex systems:

- A given need for a ‘step-wise rule-based inference.’ [AR03]

- “Second, it is necessary to represent the information which is needed to directly

define a design object in a way which makes afterwards the necessary mapping

from the symbolic representation to a semantic processing of the description as

easy and straightforward as possible.” [AR03]

- The requirement that a general model achieves a consistent generic design with the

capability to derive domain-specific detailed models with increased expressiveness.



18 2.1. GRAPH-BASED DESIGN ASSUMPTIONS

One such approach is the graph-based design methodology by Rudolph et al. [AR03,

AR04, SR05, SR16]. The core principles are illustrated in Figure 2.2. Step-wise rule-

based inference is achieved through the production system, consisting of vocabulary

(primitive building blocks) and rule set (execution rules). The compiler provides the

capability for mapping from symbolic representation to semantic form. Its output is a

design graph which represents the design and all design information in a generic form.

Domain-specific models can be derived. Adjustments in the domain-specific graphs are

fed back to the generic design graph through ‘round trip engineering’.

Figure 2.3.: Graph-Based Design: Design Graph Adaptations

One software application for the shown methodology is DC43 [IIL17a]. DC43 represents

the abstract form of all primitives in a class diagram. This includes class attributes,

linking and inheritance of relationships to other classes. A sequence diagram contains

the rule set which instantiates objects from the given classes provided in the class dia-

gram to the design graph. These objects serve as the primitives and are manipulated

through the rule set. Each rule either consists of code (java rules) or is graph-based.

Instantiated objects and relations form a graph (design graph). Graph-based rules work

by the principle: Left-Hand Side (LHS) plus Right-Hand Side (RHS) (see: Figure 2.1

- Rule 3). Alber [AR03] lists three forms of graph-based modification rules (Addition,

Decomposition and Modification). In this work, two additional forms are added to the

listed to show the complete set of possible rules (Creation and Subtraction). Figure 2.3

illustrates the five rules while the following lists explains the setup and cause for each:



CHAPTER 2. BACKGROUND AND STATE OF THE ART 19

Creation

Setup: Empty LHS; entities at the RHS.

Cause: Entities occurring on the RHS are created. This can be seen as a

special form of Addition.

Addition/Embedding

Setup: Entities (and potentially links) on the left-hand side; the same entities

and additional entities and/or links at the RHS.

Cause: For every occurrence of the LHS pattern, the addition on the RHS is

added to the relevant part of the design graph.

Subtraction

Setup: Entities (and potentially links) on the left-hand side; an identical set

of entities and links, reduced by one (or more) links or entities on the RHS.

Cause: For every occurrence of the LHS pattern, the reduction between LHS

and RHS is performed on the relevant part of the design graph.

Decomposition/Refinement

Setup: One entity on LHS; identical entity and additional entities with links

to the existing entity on the RHS.

Cause: An entity is refined by additional entities. Special case of addition.

Modification/Adaptation

A combination of addition and subtraction rules to modify the design graph.

A rule is applied in the way that a certain configuration of instantiated objects and links

is searched for as the LHS. Once found in the overall design graph, it is manipulated

to what is shown at the RHS. The sequence in which objects are affected by the rule

might be relevant; if so, this must be encoded in the rule as well. Each rule is applied

once but can be applied in repetition when put in a loop with a termination condition

in the sequence diagram. Executing and applying rules is an iterative process which

eventually terminates, once all rules in the sequence diagram have been processed. If in

certain cases termination does not happen, the rules or the sequence diagram have to be

adjusted until termination is given. This is comparable with an infinite loop in coding.

Aside from the rule set, further information like physical laws, mathematical constraints

and boundary conditions are processed. This information is either stored in libraries (e.g.



20 2.1. GRAPH-BASED DESIGN ASSUMPTIONS

physical laws and boundary conditions) or in the class diagram (e.g. problem-specific

constraints and design-related equations). All these build a set of linear equations which

can be solved by the solution path generator. This can lead to no, one or many solutions

depending on the type of linear equation system (see Figure 2.4 bottom left box).

Car

has a

has a

Car CarDamper

CarWheel ...

+ nrOfWheels : int

+ model_id : long + comp_id : long

+ strength : float

+ diameter : float

+ width: float

+ type: string

...

1.

A

2.

3.

B

Additional Design

1.: Creation

2. Add Wheel

3. Add Damper

 A: 

n = 0;

n < nrOfWheels;

n += 1

 B: 

m = 0;

m < nrOfDampers;

m += 1

+ nrOfDampers : int

Class Design Sequence Design

Design Graph CAD

Car

Damper

Wheel

m    = m      n + ...
total wheel 1

Xpos       = Xpos     + depth      
Damper

1
Wheel

1 Wheel
1

...
...

Solution
Path Generator

Figure 2.4.: Graph-Based Design: System Design (Example)

After solving the set of linear equations, the compiler creates the generic design model

in form of a design graph. Interfaces allow the generic model to be derived into the spe-

cific domain models (Computer-Aided Design (CAD), Fintite Element Analysis (FEM),

Computational Fluid Dynamics (CFD),. . . ). In each specific domain, the abstract form

of the design graph is mapped to its corresponding syntactical meaning. (e.g. in the form

of geometry, stress and load forces or aerodynamic characteristics.) The domain model

can be optimized further and information and adaptations are fed back into the generic

model. This process was mentioned earlier as ‘round trip engineering’. Such optimiza-

tion is an iterative process between optimization of domain model and graph adaptation.

Figure 2.4 represents the five core elements of graph-based design as approached in DC43.



CHAPTER 2. BACKGROUND AND STATE OF THE ART 21

The class diagram contains all classes with attributes and relations. The sequence dia-

gram contains the rule set which is sequentially executed. Class diagram and sequence

diagram are both initially defined in UML and adjusted to the graph-based design ap-

proach. The solution path generator processes all underlying constraints and equations.

The generic domain-independent model in the form of the design graph is created and

can be derived into domain-specific models. The general principle of modeling data in

such a graph-based process with the support of DC43 is used in this work. Subsection

2.1.3 addresses how this can be adjusted to the field of requirement and test data.

2.1.3. Requirements and Tests in Graph-Based Design

In the discussion about the top-down versus bottom-up approach it, was shown that

a downside of bottom-up approaches is the general problem of steering design towards

the required or envisioned product functionality. The empirically observed situation for

requirements elicitation and refinement for graph-based design, in particular DC43, shall

be discussed here. This might not be representative for all graph-based design approaches

but since DC43 is used in this work, this particular situation shall be laid out.

Graph-based design in this context serves as the underlying ontology to represent and

process the requirements and tests throughout the formalization process. The problem

to be solved here is that graph-based design usually uses a bottom-up approach while

requirements engineering in a V-model refines requirements top-down. Requirements

are initially defined on a high level (product or full system requirements, e.g. “The car

must run at all commonly accepted speeds.”) and then defined with more detail later on

(e.g. “The maximum temperature of the engine shall not exceed the maximum working

temperature of the material used for building it.”.) Thus, requirement refinement is not

naturally aligned with the bottom-up approach of graph-based design. Subsection 2.2.1

divides requirements into functional, performance, quality and constraints. It is observed

that refinement for constraints is intuitive when designing with DC43. Classes are con-

strained through boundary conditions of attributes in exactly that way (e.g. maximum

car mass = 2300 kg). Therefore, a need for mathematical equations and constraints

exists naturally. Problems arise with the other three forms of requirements (functional,

performance and quality). These requirements are usually complex to refine. It is per-

ceived that DC43 designs usually work with high-level requirements while refinement

for low-level requirements takes place informally through design decisions. This creates



22 2.2. AUTOMOTIVE SYSTEMS ENGINEERING METHODOLOGY

implicit assumptions and knowledge about the design and the product, without any for-

mal documentation or process. Such an approach is problematic for a variety of reasons

(requirements validation, design adjustments, hand-overs, . . . ).

Chapter 3 shows a path that solves this problem by connecting requirements elicita-

tion and refinement with the DC43 design process naturally. Background and relevant

definitions in the field requirements and tests are given in Section 2.3.

2.2. Automotive Systems Engineering Methodology

The Mercedes-Benz E-Class released to market in 2016 contains about 200 systems. For

theses systems, complexity varies tremendously. Personal observation estimates the av-

erage system size at about 1500 requirements and 2500 test cases (system level). Product

complexity requires a systematic development approach. This section introduces Prod-

uct Development Process (PDP) as described in Pahl & Beitz [PBSJ13, PBFG14]. It is

aligned with the V-model, state of the art model in the automotive industry today. Spe-

cial focus is on requirements engineering (Subsection 2.2.1) and verification & validation

(Subsection 2.2.2). To define the scope of this discussion about system engineering, two

questions should be answered upfront:

What is a system (and a system of systems)?

What are the disciplines and tasks required to develop a system?

One answer to the above questions is within NASA’s definition for system engineering:

Definition 2.1. “Systems engineering is a methodical, disciplined approach for the

design, realization, technical management, operations, and retirement of a system. A

“system” is a construct or collection of different elements that together produce results

not obtainable by the elements alone.” [SA95]

The term ‘results’ NASA uses in its system definition is equivalent with the expression

‘functions’ used by Pahl & Beitz [PBSJ13] in its definition of product:

Definition 2.2. “Every product serves the purpose of fulfilling a function” [PBSJ13,

pp. 242, translated].

The definition of system given by NASA shall be extended in the sense that big systems

(e.g. a car) are often separated into sub-systems, thus a car is a system of (sub-)systems.



CHAPTER 2. BACKGROUND AND STATE OF THE ART 23

All further discussions apply to systems and to systems of systems in the same way,

thus they are not differentiated in this work. Yet, all non-technical domains like market

analysis, marketing & sales strategy and customer satisfaction are beyond the scope of

this work and and will not be considered further. [PBSJ13] further states: “A solution for

a technical task including energy, material and signal transfer requires the existence of

an unambiguous, reproducible relation between input and output of a system.” [PBSJ13,

pp. 242, translated]. This leads to the conclusion that: “A function is the common and

sought relation between input and output of a system with the goal to fulfill its purpose”

[PBSJ13, pp. 242, translated] (see Figure 2.5).

Output

Material

Energy

Signals

Input

Energy

Material

Signals

Figure 2.5.:

Product Development Process: Function, Pahl and Beitz [PBSJ13, pp. 240, trans.]

Functions can be further divided into sub-functions to reduce complexity. (Sub-)functions

can be realized through physical effects or the combination of physical effects (work de-

pendencies). “To achieve the overall functionality, work dependencies of all sub-functions

are combined. The combination of multiple work dependencies leads to the work struc-

ture of a solution. Through a work structure, the interactions between work dependen-

cies are identified. It shows the solution principles that realize the overall functionality.”

[PBSJ13, pp. 249, translated] Functions require physical implementations. Components

serve as the physical structure for functional implementation. Usually functionality is

not implemented on one isolated component. Components in general consists of a control

unit with a CPU accommodated by an input layer (sensor or signal input) and an output

layer (actor or signal output). Function realization often requires contributions from mul-

tiple components. This causes complex dependencies between functions and components.

The state of the art in the automotive industry for system development is the V-model

(see Figure 1.1). It separates the development process in three major phases: Require-

ments specification with refinement from system to low-level (including architectural

design), development and verification & validation including the system integration from

low-level to high-level.



24 2.2. AUTOMOTIVE SYSTEMS ENGINEERING METHODOLOGY

V-model and Pahl & Beitz’s PDP can be mapped as shown in Figure 2.6. PDP and

V-model define the system at first. Requirements (≈ functions) are specified in detail

based on demanded system purpose. While there exists no formal solution generation

in the V-model development phase, the PDP provides a formal sequence of steps to

reach the demanded functionality. For all specified functionalities, solution principles

are selected. Solution principles are capable of physically transforming the system and

are implemented onto components. Functionality requires the interaction of components.

Integration including validation and verification of correct behavior against specification,

is the last phase of the product development. Components are aggregated to modules

and modules are aggregated to a system. It should be noted that since the Pahl and

Beitz approach in Figure 2.6 only contains one requirements specification phase, namely

an exact mapping to the V-model, this specification phase must contain the high-level

and low-level phases of requirements engineering.

Figure 2.6.:

Product Development Process (PDP), Pahl and Beitz [PBSJ13, pp. 240, translated]

The scope of this work for requirements specification as well as integration including

verification and validation is on the system level. System development is not discussed

in more detail. Pahl and Beitz was introduced to provide a connection between require-

ments engineering and testing to the overall product development. There exist formal

approaches (like the one shown) that allow requirements engineering and testing to be

embedded into overall system development. Subsection 2.2.1 contains a detailed intro-

duction to the state of the art for requirements engineering while Subsection 2.2.2 covers

integration and related testing.



CHAPTER 2. BACKGROUND AND STATE OF THE ART 25

2.2.1. Requirements Engineering

In systems development, the first technical phase is concerned with the expression of all

required functionalities of the product envisioned to be built. This and additional tasks

take place in the domain of requirements engineering. The definition of requirements

engineering used in this work is provided by Rupp and Pohl:

Definition 2.3. “Requirements engineering is a systematic and disciplined approach

to specify and manage requirements [. . .]” [RP15].

The process of requirements engineering can be divided into four main phases: Elicitation

& analysis, documentation, verification & validation and management of requirements.

The future discussion mostly addresses the documentation process. For this purpose,

it is necessary to define the term requirement and its differentiation into functional

and non-functional. This provides the basis for a detailed discussion of requirements

documentation and representation forms. Zave and Jackson [ZJ97] point out that “[. . . ]it

is not necessary or desirable to describe (however abstractly) the machine built”. Jackson

[Jac17] further concludes “Different possible behaviors can satisfy the requirements just

as more than one possible program can compute a desired result. So the requirement

[. . . ] should not specify the behavior [. . . ] directly, but only its desired properties,

effects and consequences.” Requirements therefore provide a rather abstract descriptions

of the behavior and system capabilities instead of an exact system design. The term

requirement from now on will be defined and used as:

Definition 2.4. Requirement: “A condition or capability that must be met or possessed

by a system or system component to satisfy a contract, standard, specification, or other

formally imposed documents.” [IEE90]

Requirements can be separated into Functional Requirements and Non-Functional Re-

quirements (NFR). While there exists a wide agreement on the definition of functional

requirements, “[. . . ] there is still no consensus on the nature of non-functional require-

ments and how to document them in requirements specifications” [Gli07].

Glinz removes the term NFR in his taxonomy of requirements. He considers performance

(“restrictions about timing, processing or reaction speed, data volume, or throughput”)

and quality requirements (“a specific quality that the system or a component shall have”)

as attributes of the described system,“. . . while any other restriction about what the sys-

tem shall do, how it shall do it, or any prescribed solution or solution element” is con-

sidered a constraint. He remarks that it is possible to group performance requirements,



26 2.2. AUTOMOTIVE SYSTEMS ENGINEERING METHODOLOGY

quality requirements and constraints together as NFR. The definition proposed by Glinz

is the one used in this context while, as proposed, grouping all requirements other than

functional requirements as NFR.

Definition 2.5. Functional requirement: “A requirement that specifies a function

that a system or system component must be able to perform.” [IEE90]

Definition 2.6. Non-functional requirement: Non-functional requirements sum-

marize performance requirements, quality requirements and constraints. “A performance

requirement is a requirement that pertains to a performance concern. A specific qual-

ity requirement is a requirement that pertains to a quality concern other than quality of

meeting the functional requirements. A constraint is a requirement that constrains the

solution space beyond what is necessary for meeting the given functional, performance,

and specific quality requirements.” [Gli07]

By showing multiple representation forms of the same requirement, Glinz [Gli07] further

says: “[...] the kind of requirement depends on the way we represent it.” At MBC de-

velopment, a functional requirement describes a behavior that can either be experienced

by the customer or else is testable. From observation it can be said, that all such re-

quirements can be represented in the data formats used in later formalization steps. The

focus of further discussion will therefore be on all requirements that can be represented

in language patterns used later on. This sets the scope of this work to all functional

requirements and a selected set of other requirements. This selected set is exactly the

set of requirements that is not functional but can also be represented in the language

patterns. In addition, there is a set of non-functional requirements that constraint the

solution space but cannot be represented in language patterns. These requirements can

be processed directly to the state machine without language pattern processing. Thus,

the term operationalization of functional constraints shall be defined:

Definition 2.7. Operationalization of Functional Constraints: “The process to

manipulate functional constraints from its initial equation representation to be directly

included in the state machine representation.”

To ensure a high quality system specification, requirements should be based on the follow-

ing principles of the Institute of Electrical and Electronics Engineers (IEEE) and Interna-

tional Organization for Standardization (ISO). Specifically, the IEEE norm [CB98] and

ISO-29148 [ISO11] provide definitions under “characteristics of individual requirements”:



CHAPTER 2. BACKGROUND AND STATE OF THE ART 27

Definition 2.8. Characteristics of individual requirements

(2.8.1) Necessary: The requirement defines an essential capability, characteristic,

constraint, and/or quality factor.[. . .]

(2.8.2) Implementation Free: Objective is to be implementation-independent.

(2.8.3) Unambiguous: The requirement is stated in such a way so that it can be

interpreted in only one way.[. . .]

(2.8.4) Consistent: The requirement is free of conflicts with other requirements.

(2.8.5) Complete: The stated requirement needs no further amplification because

it is measurable and sufficiently describes the capability and characteristics to meet

the stakeholder’s need.

(2.8.6) Singular: The requirement statement includes only one requirement [. . .]

(2.8.7) Feasible: The requirement is technically achievable, [. . .]

(2.8.8) Traceable: The requirement is upwards traceable to specific documented

stakeholder statement(s) of need, higher tier requirement, or other source (e.g., a

trade or design study). The requirement is also downwards traceable to the specific

requirements in the lower tier requirements specification or other system definition

artifacts. [. . .]

(2.8.9) Verifiable: The requirement has the means to prove that the system

satisfies the specified requirement. Evidence may be collected that proves that the

system can satisfy the specified requirement. Verifiability is enhanced when the

requirement is measurable.

The given specification guidelines enable specification engineers to identify and document

requirements for any given system. The actual representation form is not defined. Section

2.3 discusses a variety of specification representation forms in the context of knowledge

representation.

2.2.2. Testing - Verification and Validation

Testing is concerned with assessing product quality during system development. The In-

ternational Software Testing Qualifications Board (ISTQB) and the Institute of Electrical

and Electronics Engineers (IEEE) differ in their definition focus.



28 2.2. AUTOMOTIVE SYSTEMS ENGINEERING METHODOLOGY

Definition 2.9. Testing[ISTQB15] “The process consisting of all life cycle activities,

both static and dynamic, concerned with planning, preparation and evaluation of software

products and related work products to determine that they satisfy specified requirements,

to demonstrate that they are fit for purpose and to detect defects.”

Definition 2.10. Testing[ISTQB15](1) “The process of operating a system or com-

ponent under specified conditions, observing or recording the results, and making an

evaluation of some aspect of the system or component.”

Definition 2.11. Testing[ISTQB15](2) “The process of analyzing a software item

to detect the differences between existing and required conditions (that is, bugs) and to

evaluate the features of the software items.”

ISTQB specifically states that scope of testing includes “all life cycle activities”. It

contains a list of specific tasks to be performed on the test object. This is not included

in either IEEE definitions. All three definitions share two common aspects:

Commonality 1. Specified behavior serves the purpose it is designed for

Commonality 2. Specified behavior is compared to observed behavior

This work will use Definition 2.11 of [IEE90] as its working definition. It shall be men-

tioned that this definition is generalized beyond the scope of software items towards

system items. Thus, testing shall be defined here as:

Definition 2.12. Testing (in this work): “The process of analyzing a system item

to detect the differences between existing and required conditions (that is, bugs) and to

evaluate the features of the system items.”

In this work, a feature is considered to be a functionality provided by the system. The

observation throughout the comparison of the given definitions for testing revealed that

all share the common goals of Commonality 1: Specification matches design purpose and

Commonality 2: Specification matches observed behavior. Commonality 1 and Common-

ality 2 are both reflected in ISO-9000 [ISO05] definitions of validation and verification.

Definition 2.13. Validation [ISO05]: “Confirmation, through the provision of objec-

tive evidence, that the requirements for a specific intended use or application have been

fulfilled.”

Definition 2.14. Verification [ISO05]: “Confirmation, through the provision of ob-

jective evidence, that specified requirements have been fulfilled.”



CHAPTER 2. BACKGROUND AND STATE OF THE ART 29

A more practical way of describing validation and verification is: “Did we design the

right product?” (Verification) and “Did we design the product right?” (Validation). Val-

idation takes a product-centered view from the customer perspective. It assures that the

requirements lead to the product that is useful to the customer. In contrast, verification

is concerned with the specification process. It confirms whether on a certain specifica-

tion level the generated (more detailed) specification is in alignment with the previous

(more high level) specification. “This is independent of any intended use or purpose.”

[SL12] In contrast, this can be achieved by testing the product behavior against the

defined (testable) requirements. In this work, the main focus is on verification rather

than validation and therefore from now on ‘verification’ will be used interchangeably

with ‘testing’. This bottom-up development is illustrated in the V-model in Figure 1.1.

It shows that verification efforts occur during all testing phases and levels of the integra-

tion. System integration includes all activities concerned with assembling and validating

components, systems and the final product. Components (or the smallest stand-alone

units in a product) are verified, afterwards merged into more complex structures and

validated as systems or systems of systems.

The V-model in Figure 1.1 illustrates the three core levels (component, system and prod-

uct) and the integration phases. In addition, the unit tests occur during development.

In general, costs to detect and fix a failure increase exponentially during the integration.

Thus, it can be said, that the saving potential during later validation phases is higher. It

is favorable to reduce test loads of later phases, either by removing unnecessary tests or

shifting test load to earlier phases. In this work, the focus is on identifying and removing

redundant tests. A redundant test is a test that has an equal description to another test

and therefore does not produce new or further test result information when executed.

Shifting tests to other (lower) test phases is not addressed further here; This is discussed

by Schwarzl and Herrmann [SH18]. Definitions in the context of testing shall be given:

Definition 2.15. Test Object [ISTQB15]: “The component or system to be tested.”

For the component level test, all component interfaces are simulated and tests are per-

formed only on each component in isolation. Similarly, system level tests are performed

for each system in isolation while system interfaces are simulated.

Definition 2.16. Test environment [ISTQB15]: “An environment containing hard-

ware, instrumentation, simulators, software tools, and other support elements needed to

conduct a test.”



30 2.2. AUTOMOTIVE SYSTEMS ENGINEERING METHODOLOGY

This work distinguishes five different test environments (or platforms) as used at MBC

development.

1. Software-in-the-Loop (SIL)

2. Hardware-in-the-Loop (HIL)

3. Compoenent-HIL (C-HIL)

4. Functional Mock-Up (FMU)

5. Vehicle

Remark. This list is selective, based on the purpose discussed and not complete

Definition 2.17. Test goal [SL12], all translated:

1. Finding failures as the general goal of testing

2. Finding specific failures through adjusted test cases

3. Proof of requirement fulfillment through the test object as the specific goal of one

or more test cases.

Remark. In this work, test goal shall be used as: “Proof of requirement fulfillment

through execution without failure detection of all linked test cases, whereas each require-

ment must have at least one linked test case.”

The test object (see Definition 2.15) depends on the current integration phase and de-

scribes the object under test as well as the parts excluded from validation. Tests are

performed in a test environment (see Definition 2.16). The test environment is selected

based on the integration phase, test object and test goal (see Definition 2.17). Test envi-

ronments are mentioned in this context to strengthen the argument that later test phases

are more costly. The degree of manual work required for a (testing) task and the in-

creased efforts for adjustment of the finding are the main drivers for costs. Software unit

tests are (mostly) automated, C-HIL tests require a tester for setup and critical moments

while vehicle tests are performed fully by a tester. The scope of a test is determined by

the test goal. Spillner [SL12] distinguishes four kinds of testing:

Definition 2.18. Functional Testing[ISTQB15]: “Testing based on an analysis of

the specification of the functionality of a component or system.”



CHAPTER 2. BACKGROUND AND STATE OF THE ART 31

Definition 2.19. Non-functional Testing[ISTQB15]: “Testing the attributes of

a component or system that do not relate to functionality, e.g., reliability, efficiency,

usability, maintainability and portability.”

Definition 2.20. Structural Testing[ISTQB15]: “Testing based on an analysis of

the internal structure of the component or system.” (Definition for white-box testing)

Definition 2.21. Regression Testing [ISTQB15]: “Testing of a previously tested

program following modification to ensure that defects have not been introduced or uncov-

ered in unchanged areas of the software, as a result of the changes made. It is performed

when the software or its environment is changed.”

According to the definition used for the test goal (see Definition 2.17), this work focuses

on functional tests. Change-related tests can include a selected set of tests for each of

the three other categories (dependent on performed system changes). Tests are often

repeated numerous times during product development. Thus, optimizing such tests con-

tains an enormous savings potential. Tests are defined, structured and documented in

the form of test set, test case and test step. The common definitions in standards and

norms differ from the terminology used at [MB17].

Definition 2.22. Test Set [ISTQB15]: “A set of several test cases for a component

or system under test, [. . . ]”

Definition 2.23. Test Case [MB17]: “[. . . ]. [A test case] is the aggregation of mutual

test steps. The test case result is the aggregation of its test step results.”

Both definitions contain the idea that the defined term is a set of elements. The elements

provide actual system tests. In this work, the term test case shall be used as defined

at MBC in Definition 2.23. The meaning of test case is closely related to the test set

Definition 2.22.

Definition 2.24. Test Case [IEE90]: “A set of input values, execution preconditions,

expected results and execution postconditions, developed for a particular objective or test

condition, such as to exercise a particular program path or to verify compliance with a

specific requirement.”

Definition 2.25. Test Step [MB17]: “A test step consists of a precondition, trigger

and postcondition [...]. A test step proves (pass) or disproves (fail) a transition from one

state (precondition) to another state (postcondition) caused by a specific trigger. Multiple

test steps aggregate to a test case.”



32 2.2. AUTOMOTIVE SYSTEMS ENGINEERING METHODOLOGY

The definitions for test case [IEE90] and test step [MB17] both contain precondition,

postcondition, input values (triggers) with the goal of verification of requirements (pre-

condition, trigger and postcondition). The term ‘test step’ shall be used as defined in

Definition 2.25. It is closely related to the definition of test case at [IEE90]. Further the

terms ‘precondition’, ‘trigger’ (state ‘transition’) and ‘postcondition’ shall be defined.

Definition 2.26. Precondition [ISTQB15]: “Environmental and state conditions

that must be fulfilled before the component or system can be executed with a particular

test or test procedure.”

Definition 2.27. State transition [ISTQB15]: “A variable (whether stored within

a component [or system] or outside) that is read by a component [or system].”

Definition 2.28. Postcondition [ISTQB15]: “Environmental and state conditions

that must be fulfilled after the execution of a test or test procedure.”

In this work, precondition and postcondition are seen as system states (as in a state

machine). To account for output verification, either the expected result must contain a

description of the outputs or postcondition includes output as one part of its description.

This second option might not be the most elegant form of representation but it makes

it possible to express test cases and test steps in the structure used in this work. The

combination of current state and input determines a transition path and transition time

(moment or period) where the system changes from the initial state (precondition) to the

final state (postcondition). In this work, ‘transition’ is used synonymously with ‘trigger’.

The comparison of expected to actual results is performed for the precondition, transi-

tion and postcondition. A test is passed when the test description for the initial state,

transition path and final state match the observed states and path in the actual system

at the relevant observation moment during test execution. Existing test specification

guidelines enable test specification engineers to derive and document tests and links to

requirements for any given test object. The actual representation for the test description

form is not defined. This specifically affects the description of precondition, transition

and postcondition. Section 2.3 discusses a variety of representation forms in the context

of knowledge representation as well as the possibility of applying these representation

forms to test descriptions.



CHAPTER 2. BACKGROUND AND STATE OF THE ART 33

2.3. Knowledge Representations in Systems Engineering

Sharma and Biswas [MT13] make a strong statement that in order to make progress in

requirements engineering, knowledge representations must be understood first. That in-

cludes clarifying and defining knowledge and discussing the field of representation forms.

Knowledge is closely related to data and information. The three terms, knowledge, data

and information, are often used in overlapping or interchangeable ways. Closer analysis

makes it obv