# Mathematical and Implementation Challenges Associated with Testing of the Dynamical Systems

Pawel Skruch

<figure><img src="image_1.png" /></figure>

To cite this version:

Pawel Skruch. Mathematical and Implementation Challenges Associated with Testing of the Dynamical Systems. 25th System Modeling and Optimization (CSMO), Sep 2011, Berlin, Germany. pp.538-546, 10.1007/978-3-642-36062-6_54. hal-01347582

HAL Id: hal-01347582

https://inria.hal.science/hal-01347582

Submitted on 21 Jul 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Mathematical and Implementation Challenges
Associated with Testing of the Dynamical
Systems

Pawel Skruch

AGH University of Science and Technology,
Faculty of Electrical Engineering, Automatics, Computer Science and Electronics,
Department of Automatics,
al. A. Mickiewicza 30/B1, 30-059 Krakow, Poland
pawel.skruch@agh.edu.pl

**Abstract.** The paper presents mathematical and implementation challenges associated with testing of embedded software systems with dynamic behavior. These challenges are related to notation of tests, calculation of test coverage, implementation of a test comparator, and automatic generation of test cases. Some author's ideas and solutions are presented with the help of abstract models that describe behavior of the software systems. The models are represented using the state space (or input/state/output) notation. An application example is given to illustrate theoretical analysis and mathematical formulation.

**Keywords:** software system; model-based testing; dynamical system

# 1 Introduction

Designing an embedded control system is a complex and error prone task. Within the last decades embedded systems have become increasingly sophisticated and their software content has grown rapidly. The increasing miniaturization of embedded control systems on the one hand and rising functional demands on the other hand require advanced and automated development and testing methodologies. In this context, model-based development (MBD) and model-based testing (MBT) approaches have the potential to facilitate the development of such systems under pressure of time-to-market constraints, quality assurance, and safety standards.

MBD is a process that provides the ability to graphically represent requirements, specification, and designs using domain-specific notations and simulate the resultant behavior for validation purposes. The code can be then generated from models, ranging from system skeletons to complete, deployable products. MBT is a related part that supports test generation from various kinds of models by application of a number of sophisticated methods.

Testing is the process of trying to discover every conceivable fault or weakness in a work product. The primary goal of the testing process is to find defects; the
secondary goal is to show the system's compliance to its requirements. Testing
can show that defects are present, but cannot prove that there are no defects [9].
Testing reduces the probability of undiscovered defects remaining in the software
but, even if no defects are found, it is not a proof of correctness. Poorly tested
systems may cost producers billions of dollars annually especially when defects
are found by end users in production environments [7], [8], [13]. Barry Boehm's
research analysis [4] indicates that the cost of removing a software defect grows
exponentially for each stage of the development life cycle in which it remains
undiscovered. Boris Beizer [2] estimates that 30 up to 90 percentage of the effort
in put into testing. Another research project conducted by the United States
Department of Commerce, National Institute of Standards and Technology [10]
estimated that software defects cost the U.S. economy $60 billion per year.

Exhaustive testing is impossible what means that testing everything (all com-
binations of inputs and preconditions) is not feasible expect for trivial cases. This
is valid in particular for software systems with dynamic behavior. The dynamic
systems are modeled by difference or differential equations and have usually in-
finitely many states. Testing dynamic aspects of such systems requires tests that
utilize time continuous input signals and time continuous output signals (even
when the system is digitally processed). The process of selecting just a few of
the many possible scenarios to be tested is a difficult and challenging task and
currently is most often based on qualitative best engineering judgment.

In this paper, testing problem as well as test artifacts for software systems
with dynamic behavior are formulated using the mathematical formalism. The
main results concern the concept of testing with a model as an oracle (section 2),
a proposal for test notation (section 4), an implementation of a test comparator
 subsections 7). An example (section 8) is given to present a perspective on the
applicability of the approach for industrial projects.

## 2 Concept of Testing with a Model as an Oracle

The model of a software system shall specify the system's behavior in a clear and
unambiguous form. It can be used in computer simulations in an early phase of
the development to validate the system concept, calibrate parameters, and opti-
mize the system performance. In the next phase, the physical system is designed
(i.e., hardware and software) that shall meet the requirements specified by the
model. Testing process shall be considered as the last phase in the development
process that allows verifying that the physical system behavior is identical to
that observed during computer simulations. When the tests failed then the sys-
tem needs to be redesigned. The physical system that is being tested for the
correct operation is often referred to as the system under test (SUT).

The model fully represents the requirements therefore it can be used an oracle
to assess if the algorithm implemented in the electronic control unit (ECU) being
tested correctly implements the requirements. The term *test oracle* describes a
source to determine expected results to compare with the actual result of the
SUT [1]. The approach of a validated model being used as an oracle (the block Mathematical Model of the SUT on figure 1) is very popular in industry and often applied. The execution of a test case consists of exciting the system using actuators to simulate its working conditions and measuring the system's response in terms of electrical signals, motion, force, strain, etc. The signals are physical in case of the SUT and virtual in case of the model. The approach stipulates that the same inputs $u(\cdot)$ are applied to both the SUT and to the model. Next, the responses from the SUT $y_s(\cdot)$ and from the model $y(\cdot)$ are compared by a test comparator to determine whether a test case has passed or failed.

<figure><img src="image_3.png" /><figcaption>Fig. 1. Testing approach of a validated model being used as an oracle</figcaption></figure>

## 3 Mathematical Model of the System Under Test

The state space (or input/state/output) representation provides a convenient way to model and analyze dynamical systems. The state space model consists of a set of input, output, and internal state variables that are expressed as vectors. The relationship between inputs, outputs, and internal states in a finite-dimensional, time-invariant, nonlinear system with continuous-time parameter can be specified by the following equations:

$$ \dot{x}(t) = f(x, u, t), \quad x(0) = x_0, \qquad (1) $$

$$ y(t) = g(x, u, t), \qquad (2) $$

where $x(t) \in X \subset \mathbb{R}^n$ refers to the internal state, $u(t) \in U \subset \mathbb{R}^r$ refers to the input state, $y(t) \in Y \subset \mathbb{R}^m$ refers to the output state, the independent variable $t > 0$ is time, $x_0 \in \mathbb{R}^n$ is the given initial condition, $f: \mathbb{R}^n \times \mathbb{R}^r \times \mathbb{R} \to \mathbb{R}^n$ denotes a mathematical relationship describing the system behavior, $g: \mathbb{R}^n \times \mathbb{R}^r \times \mathbb{R} \to \mathbb{R}^m$ determines the output, $X$ is the internal state space, $Y$ is the output state space, $U$ is called the input state space, $\mathbb{R}^n$, $\mathbb{R}^m$, $\mathbb{R}^r$ are real vector spaces of column vectors, $n, m, r$ are positive integers that determine numbers of internal state, output, and input variables, respectively.
The physical and implementation constraints imposed by computer system resources lead to the assumption that the spaces U, X, and Y shall be bounded. The assumption means that each space is contained in a ball of finite radius.

## 4 Test Notation

A test case can be considered as a set of inputs, execution preconditions, and expected outcomes developed for a particular objective, such as to exercise a particular program path or to verify compliance with a specific requirement [15]. Adapting this definition to the state space modeling concept of the SUT (1), (2), a single test case $T_{\text{case}}^{(j)}$ can be defined as

$$ T_{\text{case}}^{(j)} = \{T^{(j)}, \boldsymbol{x}_{0}^{(j)}, \boldsymbol{u}^{(j)}(\cdot), \boldsymbol{y}^{(j)}(\cdot)\}, \quad (3) $$

in case of black-box testing [3], or

$$ T_{\text{case}}^{(j)} = \{T^{(j)}, \boldsymbol{x}_{0}^{(j)}, \boldsymbol{u}^{(j)}(\cdot), \boldsymbol{x}^{(j)}(\cdot), \boldsymbol{y}^{(j)}(\cdot)\}, \quad (4) $$

in case of gray-box testing [12]. Here, $\boldsymbol{u}^{(j)}: [0, T^{(j)}] \to \mathbb{R}^r$ is an input function applied to the SUT, $\boldsymbol{x}^{(j)}: [0, T^{(j)}] \to \mathbb{R}^n$ is an expected state function, and $\boldsymbol{y}^{(j)}: [0, T^{(j)}] \to \mathbb{R}^m$ is an expected output function within the execution time window $[0, T^{(j)}]$ when the system starts from an initial condition $\boldsymbol{x}_{0}^{(j)}$, $j = 1, 2, \dots, N$ is a label to indicate different test cases. A collection of one or more test cases forms a test suite $T_{\text{suite}} = \{T_{\text{case}}^{(1)}, T_{\text{case}}^{(2)}, \dots, T_{\text{case}}^{(N)}\}$.

## 5 Test Comparator Implementation

The test comparator can be considered as a tool that implements a mechanism for determining whether a test has passed or failed [5]. In the concept, illustrated on figure 1, this tool compares the actual output $\boldsymbol{y}_s(\cdot)$ produced by the SUT with the expected output $\boldsymbol{y}(\cdot)$ produced by the model. If the actual output is within a predefined tolerance range $\epsilon$ relative to the expected output, then the test is qualified as pass ($z = 0$, system ok), otherwise the test is qualified as fail ($z = 1$, system error). A possible practical realization of the comparison function $z$ for a given test case $T_{\text{case}}^{(j)}$ is presented below:

$$ z(T_{\text{case}}^{(j)}) = \begin{cases} 0 & \text{if } \forall t \in [0, T^{(j)}] \|\boldsymbol{y}^{(j)}(t) - \boldsymbol{y}_s^{(j)}(t)\| < \epsilon \|\boldsymbol{y}^{(j)}(t)\|, \\ 1 & \text{otherwise.} \end{cases} \quad (5) $$

In the formula (5) the standard Euclidean norm $\| \cdot \|$ has been used to measure the distance between two points in the space $\mathbb{R}^m$.
## 6 Test Coverage Calculation

The degree to which a given test suite $T_{\text{suite}}$ addresses all specified requirements for a given system is determined by a test coverage measure [15]. The most obvious quantification of the system's behavior exercised by the test suite is computed by dividing the number of the system states explored by the test suite by the cardinality of the entire state space. However, the formula has limited usefulness for dynamical systems because the state space for such systems contains usually infinite number of states. In such situation, one of the possible ways out is to transform the internal state space $X$ into another one $X_h$ that contains countable number of elements.

The test coverage $C_h$ of the test suite $T_{\text{suite}} = \{T_{\text{case}}^{(1)}, T_{\text{case}}^{(2)}, \dots, T_{\text{case}}^{(N)}\}$ can be defined as follows [14]

$$C_h(T_{\text{suite}}) = \frac{\left| \bigcup_{j=1}^{N} V_h(T_{\text{case}}^{(j)}) \right|}{|X_h|}, \qquad (6)$$

where

$$X_h = \{i \in \mathbb{Z}^n : \exists x \in X : x \in G_h(i)\} \qquad (7)$$

is the transformed internal state space, $h = [h_1 h_2 \dots h_n]^T$, $h_k > 0$ for $k = 1, 2, \dots, n$, $\mathbb{Z}$ stands for the set of integers,

$$G_h(i) = \{x \in \mathbb{R}^n : x = [x_1 x_2 \dots x_n]^T, \left\lfloor \frac{x_k}{h_k} \right\rfloor = i_k, k = 1, 2, \dots, n\} \qquad (8)$$

denotes a partition with the size $h$ in the space $\mathbb{R}^n$, $\left\lfloor \frac{x_k}{h_k} \right\rfloor$ is the largest integer not greater than $\frac{x_k}{h_k}$,

$$V_h(T_{\text{case}}^{(j)}) = \{i \in X_h : \exists t \in [0, T^{(j)}) : x^{(j)}(t) \in G_h(i)\} \qquad (9)$$

is a set of states of the transformed internal state space covered by the test case $T_{\text{case}}^{(j)}$. It should be noticed that the sum

$$V_h(T_{\text{suite}}) = \bigcup_{j=1}^{N} V_h(T_{\text{case}}^{(j)}) \qquad (10)$$

will contain the information about the internal states covered by the test suite $T_{\text{suite}}$.

The proposed test coverage measure is defined using a partition (or discretization) of the system internal state space. The partition forms a rectangular grid and, roughly speaking, the test coverage is defined by the number of the grid boxes visited by the system state during a test.
## 7 Conformance Test Selection Method

The section presents a proposal of the algorithm for generating test cases. The general principle of the algorithm is to create input functions $u(\cdot)$ for which the system trajectories $x(\cdot)$ cross every element $G_h(i)$ of the space $X_h$. The selection and completeness of test cases is quantified by the coverage metric (6). Test cases are selected to check that the functional specification (here in the form of the mathematical model) is correctly implemented, which is variously referred to in the literature as conformance testing [5], correctness testing [6], or functional testing [15].

<caption>**Algorithm 1 Conformance test selection method**</caption>

1: $h = [h_1 h_2 \dots h_n]^T$, $h_1, h_2, \dots, h_n > 0$, $\delta \in (0, 1]$, $T > 0$
2: $T_{\text{suite}} := \emptyset$, $V_h(T_{\text{suite}}) := \emptyset$, $C_h(T_{\text{suite}}) = 0$, $j := 0$
3: **while** $C_h(T_{\text{suite}}) \le \delta$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;Find $x_a \in G_h(i_a)$, $x_b \in G_h(i_b)$ where $i_b \in X_h \setminus V_h(T_{\text{suite}})$
5: &nbsp;&nbsp;&nbsp;&nbsp;Calculate the control function $u^*(\cdot)$ that steers the system from the initial state $x(0) = x_a$ to the final state $x(T) = x_b$ at finite time $T$
6: &nbsp;&nbsp;&nbsp;&nbsp;Calculate the trajectory $x^*(\cdot)$ and output function $y^*(\cdot)$
7: &nbsp;&nbsp;&nbsp;&nbsp;$j := j + 1$
8: &nbsp;&nbsp;&nbsp;&nbsp;$T_{\text{case}}^{(j)} := \{T^{(j)}, x_0^{(j)}, u^{(j)}(\cdot), x^{(j)}(\cdot), y^{(j)}(\cdot)\}$, where $T^{(j)} := T$, $x_0^{(j)} := x_a$, $u^{(j)}(\cdot) := u^*(\cdot)$, $x^{(j)}(\cdot) := x^*(\cdot)$, $y^{(j)}(\cdot) := y^*(\cdot)$
9: &nbsp;&nbsp;&nbsp;&nbsp;$T_{\text{suite}} := T_{\text{suite}} \cup T_{\text{case}}^{(j)}$
10: &nbsp;&nbsp;&nbsp;&nbsp;Calculate $V_h(T_{\text{suite}})$ and $C_h(T_{\text{suite}})$
11: **end while**

## 8 Embedded PID Controller Example

An embedded PID controller is a system that can be considered as a combination of computer hardware and software designed to perform a dedicated control function. The PID controller works in a closed-loop system (figure 2) and attempts to minimize the error $e(t)$ by adjusting the control input $s(t)$. The error is calculated as the difference between a measured process output $v(t)$ and a desired set point $v_{\text{sp}}(t)$. The control signal is a result of the following calculation

$$s(t) = K \left( e(t) + \frac{1}{T_i} \int_0^t e(\tau) \, d\tau + T_d \frac{de(t)}{dt} \right), \quad (11)$$

where $K = 3.6$ is proportional gain, $T_i = 1.81$ [s] is integral time, $T_d = 0.45$ [s] is derivative time. The control signal is thus a sum of three terms: the P-term (which is proportional to the error), the I-term (which is proportional to the integral of the error), and D-term (which is proportional to the derivative of the error). The parameters $K$, $T_i$, and $T_d$ can be obtained using the Ziegler-Nichols
<figure><img src="image_4.png" /><figcaption>Fig. 2. A block diagram of the closed-loop system with the PID controller</figcaption></figure>

algorithm [16]. The model of the process to be controlled has been omitted in the example for the purpose of clarity and easy readability.

The algorithm 1 can be used to generate a set of conformance test cases. Before its execution, the equation (11) needs to be rewritten to the form

$$ \dot{x}(t) = Ax(t) + Bu(t), \quad x(0) = 0, \qquad (12) $$

$$ y(t) = Cx(t), \qquad (13) $$

where $x(t) = [x_1(t) \ x_2(t)]^T$, $x_1(t) = \int_0^t e(\tau) \ d\tau$, $x_2(t) = \dot{x}_1(t)$,

$$ A = \begin{bmatrix} 0 & 1 \\ -(T_i T_d)^{-1} & -T_d^{-1} \end{bmatrix}, \quad B = \begin{bmatrix} 0 \\ (KT_d)^{-1} \end{bmatrix}, \quad C = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}. \qquad (14) $$

Then, the algorithm has been implemented and executed with the following parameters: $h = [0.3, 0.2]^T$ (size of the partition), $\delta = 0.7$ (acceptable coverage level), $T = 20$ [s] (test execution time), $-1.5 \le x_1(t) < 1.5$, $-1 \le x_2(t) < 1$ (system implementation constraints). The test suite that guarantees the coverage level higher than $\delta$ consists of 10 test cases. The elements of these test cases are detailed in table 1, figures 3 and 4.

## 9 Conclusions

In spite of continuing research on test approaches for continuous and mixed discrete-continuous systems, there is still a lack for patterns, processes, methodologies, and tools that effectively support automatic generation and selection of the correct test cases for such systems. The model-based approach presented in the paper looks promising. The functional model of the system under test can be used as an oracle providing the capabilities to assess the results of test cases in an automatic way and also in test generation algorithms. Additional aspects, such as test notation, implementation of a test comparator, and coverage analysis have been discussed in the paper in order to have complete set of tools and mathematical methods for testing software systems with dynamic behavior. The example has been used to validate the concept and to have a perspective on its applicability for industrial projects.
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Trajectories $x^{(j)}$, $j = 1, 2, \dots, 10$ and elements (gray rectangles) of the transformed state space covered by the test cases $T_{\text{case}}^{(j)}$. The trajectories start in $\Box$ and end in $\circ$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Fig. 4.** Illustration of the input functions $u^{(j)}(\cdot)$, $j = 1, 2, \dots, 10$ belonging to the test cases $T_{\text{case}}^{(j)}$.</figcaption></figure>
<table><caption>**Table 1.** An example test report for the test suite $T_{\text{suite}} = \{T_{\text{case}}^{(1)}, T_{\text{case}}^{(2)}, \dots, T_{\text{case}}^{(10)}\}$ that guarantees the coverage level $C_h > \delta$, where $h = [0.3, 0.2]^T$, $\delta = 0.7$ (70%). The notation used in the last column means $T_{\text{suite}}^{(j)} = \{T_{\text{case}}^{(1)}, T_{\text{case}}^{(2)}, \dots, T_{\text{case}}^{(j)}\}$.</caption><thead><tr><th>j</th><th>T<sup>(j)</sup>[s]</th><th>x<sub>0</sub><sup>(j)T</sup></th><th>u<sup>(j)</sup>(·)</th><th>x<sup>(j)</sup>(·)</th><th>y<sup>(j)</sup>(·)</th><th>C<sub>h</sub>(T<sub>case</sub><sup>(j)</sup>)</th><th>C<sub>h</sub>(T<sub>suite</sub><sup>(j)</sup>)</th></tr></thead><tbody><tr><td>1</td><td>20</td><td>[0, 0]</td><td>fig. 4</td><td>fig. 3</td><td>0.16</td><td>0.16</td><td></td></tr><tr><td>2</td><td>20</td><td>[0, 0]</td><td>fig. 4</td><td>fig. 3</td><td>0.12</td><td>0.24</td><td></td></tr><tr><td>3</td><td>20</td><td>[0, 0]</td><td>fig. 4</td><td>fig. 3</td><td>0.08</td><td>0.30</td><td></td></tr><tr><td>4</td><td>20</td><td>[0, 0]</td><td>fig. 4</td><td>fig. 3</td><td>0.07</td><td>0.36</td><td></td></tr><tr><td>5</td><td>20</td><td>[0, 0]</td><td>fig. 4</td><td>fig. 3</td><td>0.09</td><td>0.40</td><td></td></tr><tr><td>6</td><td>20</td><td>[0, 0]</td><td>fig. 4</td><td>fig. 3</td><td>0.14</td><td>0.49</td><td></td></tr><tr><td>7</td><td>20</td><td>[0, 0]</td><td>fig. 4</td><td>fig. 3</td><td>0.12</td><td>0.58</td><td></td></tr><tr><td>8</td><td>20</td><td>[0, 0]</td><td>fig. 4</td><td>fig. 3</td><td>0.08</td><td>0.65</td><td></td></tr><tr><td>9</td><td>20</td><td>[0, 0]</td><td>fig. 4</td><td>fig. 3</td><td>0.08</td><td>0.70</td><td></td></tr><tr><td>10</td><td>20</td><td>[0, 0]</td><td>fig. 4</td><td>fig. 3</td><td>0.09</td><td>0.73</td><td></td></tr></tbody></table>

**Acknowledgments.** This work was supported by the National Science Centre (Poland) – project No N N514 644440.

**References**

1. Adrion, W., Brandstad, J., Cherniabsky, J.: Validation, Verification and Testing of Computer Software. Computing Surveys 14, 159–192 (1982)

2. Beizer, B.: Software Testing Techniques, 2nd ed. Van Nostrand Reinhold, Boston, USA (1990)

3. Beizer, B.: Black-Box Testing. Techniques for Functional Testing of Software and Systems. John Willey & Sons, New York, USA (1995)

4. Boehm, B.: Software Engineering Economics. Prentice Hall, Englewood Cliffs, USA (1981)

5. International Software Testing Qualifications Board (ISTQB): Standard Glossary of Terms Used in Software Testing, Version 2.1 (2010), http://www.astqb.org

6. Kaner, C., Faulk, J., Nguyen, H.Q.: Testing Computer Software, 2nd ed. John Willey & Sons, New York, USA (1995)

7. Leveson, N.G., Turner, C.S.: An Investigation of the Therac-25 Accidents. IEEE Computer 27, 18–41 (1993)

8. Lions, J.L.: ARIANE 5. Flight 501 Failure. Ariane 501 Inquiry Board Report. Technical report, Paris, France (1996)

9. Myers, G.: The Art of Software Testing, 2nd ed. John Willey & Sons, New York, USA (2004)

10. National Institute of Standards & Technology, U.S. Department of Commerce: The Physiology of the Grid: The Economic Impacts of Inadequate Infrastructure for Software Testing, Final Report. Technical report, North Carolina, USA (2002)

11. Nelder, J.A., Mead, R.: A Simplex Method for Function Minimization. The Computer Journal 7, 308–313 (1965)

12. Patton, R.: Software Testing, 2nd ed. Sams, Indianapolis, USA (2005) +

13. Skeel, R.: Roundoff Error and the Patriot Missile. Society for Industrial and Applied Mathematics (SIAM) News 25, 11 (1992)
14. Skruch, P.: A Coverage Metric to Evaluate Tests for Continuous-Time Dynamic Systems. Central European Journal of Engineering 1, 174–180 (2011)

15. The Institute of Electrical and Electronics Engineers, Inc.: IEEE Standard Glossary of Software Engineering Terminology, IEEE Std 610.12-1990 (1990), http://www.standards.ieee.org

16. Ziegler, J., Nichols, N.: Optimum Settings for Automatic Controllers. Transactions of ASME 64, 759-768 (1942)