# Methods of Synthesis of Controlled Random Tests

Ireneusz Mrozek, Vyacheslav Yarmolik

► To cite this version:

Ireneusz Mrozek, Vyacheslav Yarmolik. Methods of Synthesis of Controlled Random Tests. 15th IFIP International Conference on Computer Information Systems and Industrial Management (CISIM), Sep 2016, Vilnius, Lithuania. pp.429-440, 10.1007/978-3-319-45378-1_38 . hal-01637455

HAL Id: hal-01637455

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

Submitted on 17 Nov 2017

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_1.png" /></figure>
# Methods of Synthesis of Controlled Random Tests

Ireneusz Mrozek and Vyacheslav Yarmolik

Faculty of Computer Science
Bialystok University of Technology
Wiejska 45A, 15-351 Bialystok, Poland
i.mrozek@pb.edu.pl, yarmolik10ru@yahoo.com
http://www.wi.pb.edu.pl

**Abstract.** Controlled random tests, methods of their generation, main criteria used for their synthesis, such as the Hamming distance and the Euclidean distance, as well as their application to the testing of both hardware and software systems are discussed. Available evidences suggest that high computational complexity is one of the main drawbacks of these methods. Therefore we propose a technique to overcome this problem. A method for synthesizing multiple controlled random tests based on the use of the initial random test and addition operation has been proposed. The resulting multiple tests can be interpreted as a single controlled random test. The complexity of its construction is significantly lower than the complexity of the construction of classical random tests. Examples of generated tests as well as estimates of their effectiveness compared to other solutions have been presented in experimental studies.

**Keywords:** random tests, controlled tests, multiple tests, Hamming distance, Euclidean distance

## 1 Introduction

Among the black box techniques, random testing is generally regarded as a very effective technique for testing modern hardware and software systems [1–7]. All modifications of random testing are united by the controllability principle for test pattern generation [1, 4, 7–12]. These tests are constructed based on the calculation of certain characteristics for the controlled selection of another random test set [1].

The use of controlled random tests is characterized by greater efficiency compared with other types of tests that has been confirmed in practice many times [1, 4, 12–17]. It should be noted that the need to sort potential candidates for test sets and calculate the numerical characteristics for them significantly increases the complexity of constructing controlled random tests [1, 4, 12, 13, 16].

<footnote>This paper was supported by grant S/WI/3/13 from Faculty of Computer Science at Bialystok University of Technology, Ministry of Science and Higher Education, Poland.</footnote>
The purpose of this paper is to develop a method for constructing multiple controlled tests based on the initial controlled random test of a lesser length constructed by known methodologies [1, 4, 12, 13, 16] The initial test is used to construct subsequent tests of multiple controlled random tests in the form of simple modifications that do not require further analysis or computational costs. The resulting multiple controlled random tests can be interpreted as a single random test or used for periodic testing in applications with time limited test procedures.

## 2 Analysis of controlled random tests

All existing methods for constructing controlled random tests are based on the assertion which is explained below [1, 12, 13, 15]. Each subsequent test set of the controlled random tests should be constructed such that it is as different (distant) from all previously generated test sets as possible.

For methods of controlled random testing used to test digital devices and software with m inputs and the space of input patterns consisting of 2^m binary sets (vectors), the following definitions are correct [1, 7, 13]

**Definition 1.** The test (T) is a set of $2 <= q <= 2^m$ test sets:

$$ \{T_0, T_1, T_2, \dots, T_{q-1}\} \text{ where } T_i = t_{i,m-1}, t_{i,m-2}, \dots, t_{i,2}, t_{i,1}, t_{i,0} \text{ and } t_{i,l} \in \{0, 1\} $$

**Definition 2.** A controlled random test, where CRT = {$T_0, T_1, T_2, \dots, T_{q-1}$}, is a test that includes $q < 2^m$ m-bit randomly generated test patterns denoted by $T_i$, where $i \in \{0, 1, 2, \dots, q-1\}$, and where $T_i = t_{i,m-1}, t_{i,m-2}, \dots, t_{i,2}, t_{i,1}, t_{i,0}$ and $t_{i,l} \in \{0, 1\}$, such that $T_i$ satisfies some criterion or criteria obtained on the basis of previous test patterns {$T_0, T_1, T_2, \dots, T_{i-1}$}.

Hamming distance and Euclidean distance are often used as difference measures between the test pattern $T_i$ and previously generated patterns [1, 11, 18]. In this case, the measures apply to the binary test pattern $T_i$ and $T_j$. The Hamming distance HD($T_i, T_j$) is computed as the weight $w(T_i \oplus T_j)$ of the vector $T_i \oplus T_j$ according to the following formula (1):

$$ \mathrm{HD}(T_i, T_j) = w(T_i \oplus T_j) = \sum_{l=0}^{m-1} (t_{i,l} \oplus t_{j,l}). \quad (1) $$

Euclidean distance ED($T_i, T_j$) is computed according to the formula (2).

$$ \mathrm{ED}(T_i, T_j) = \sqrt{\sum_{l=0}^{m-1} (t_{i,l} - t_{j,l})^2} = \sqrt{\sum_{l=0}^{m-1} (t_{i,l} \oplus t_{j,l})} = \sqrt{\mathrm{HD}(T_i, T_j)}. \quad (2) $$

To generate the test pattern $T_i$, when $i > 2$, total values of the distances between $T_i$ and all previous patterns ($T_0, T_1, T_2, \dots, T_{i-1}$) are used [1, 5, 10, 11,
16, 19]. Thus, for the next pattern $T_i$, the total value of the distances with respect to $(T_0, T_1, T_2, \dots, T_{i-1})$ constitutes the following:

$$THD(T_i) = \sum_{j=0}^{i-1} HD(T_i, T_j); \quad TED(T_i) = \sum_{j=0}^{i-1} ED(T_i, T_j). \qquad (3)$$

Here, THD($T_i$) and TED($T_i$) stand for the total Hamming distance and total Euclidean distance, respectively. The new pattern $T_i$ should be chosen to make the total distances THD($T_i$) and TED($T_i$) maximal [1].

According to the methods of constructing controlled random tests outlined above, the new test set $T_i$ is selected so that difference metrics (3) take the maximum value [1, 12, 13, 15, 16, 20]. Note that difference metrics (3) are characterized by a significant computational complexity, which increases with the growth of the index $i$ of the test set $T_i$.

As shown in [14, 20], the minimum Hamming distance min$HD(T_i, T_j)$ or the Euclidean distance min$ED(T_i, T_j)$ is a more efficient metrics for the generation of a controlled random test. According to the method of synthesis of tests discussed in [14], the subsequent test set $T_i$ is selected from possible candidates for the tests by the criterion of the maximum value

$$\min_{j \in \{0,1,\dots,i-1\}} HD(T_i, T_j) \quad \text{or} \quad \min_{j \in \{0,1,\dots,i-1\}} ED(T_i, T_j) \qquad (4)$$

which provides the maximum distance (difference) of the test set $T_i$ from all previously generated sets $\{T_0, T_1, T_2, \dots, T_{i-1}\}$. If the maximum value of (4) is achieved, it also maximizes values THD($T_i$) and TED($T_i$) according to (3) [20].

Let us define a multiple controlled test based on the methodology of single step controlled random tests.

**Definition 3.** The multiple controlled random test $MCRT_r$ consists of $r$ single step controlled random tests $CRT(0), CRT(1), CRT(2), \dots, CRT(r-1)$, each of which includes $q$ test sets. In addition, the test $CRT(0)$ satisfies Definition 2 and subsequent tests $CRT(i), i \in \{1, 2, 3, \dots, r-1\}$ are constructed according to certain algorithms such that each subsequent test $CRT(i)$ meets a certain criterion or criteria derived from previous tests $CRT(0), CRT(1), CRT(2), \dots, CRT(i-1)$.

Let us consider the Hamming and the Euclidean distance for two tests $CRT(k)$ and $CRT(l)$. Initially, we note that the Hamming distance $HD(CRT(k), CRT(l))$, which is the same as the number of distinct components $T_{k,i}$ and $T_{l,i}$ of the initial test $CRT(k)$ and the constructed one $CRT(l)$, can be considered as a prerequisite which the test $CRT(l)$ should meet. It is clear that a necessary requirement in terms of the maximum difference with which $CRT(k)$ and $CRT(l)$ should comply is the lack of matching sets $T_{k,i}$ and $T_{l,i}$ in them, which is equivalent to the inequality $T_{l,i} \neq T_{k,i}, i \in \{0, 1, 2, \dots, q-1\}$.

The Euclidean distance for $CRT(k)$ and $CRT(l)$ is defined as:

$$ED(CRT(k), CRT(l)) = \sqrt{\sum_{i=0}^{q-1} (T_{i,k} - T_{i,l})^2}. \qquad (5)$$
In order to use more effective criteria for estimating the quality of the controlled random test in the construction of the test CRT(i), let us determine the maximum value of the Hamming distance MHD(CRT(i)) and the maximum value of the Euclidean distance MED(CRT(i)) as follows:

$$ 
\begin{aligned}
MHD(CRT(i)) &= \max_{CRT_v(i), v \in \{0, \dots, w\}} \left\{ \min_{j \in \{0, 1, \dots, i-1\}} HD(CRT_1(i), CRT(j)), \dots, \right. \\
& \qquad \left. \min_{j \in \{0, 1, \dots, i-1\}} HD(CRT_w(i), CRT(j)) \right\}; \\
MED(CRT(i)) &= \max_{CRT_v(i), v \in \{0, \dots, w\}} \left\{ \min_{j \in \{0, 1, \dots, j-1\}} ED(CRT_1(i), CRT(j)), \dots, \right. \\
& \qquad \left. \min_{j \in \{0, 1, \dots, i-1\}} ED(CRT_w(i), CRT(j)) \right\}.
\end{aligned}
\tag{6}
$$

According to given metrics (6), the subsequent controlled random test CRT(i) is selected from the set {CRT₁(i), CRT₂(i),..., CRTw(i)} of to test candidates based on the criterion of the maximum minimum Hamming and Euclidean distances with respect to previously generated controlled random tests CRT(j) = {CRT(0), CRT(1),..., CRT(i-1)}.

### 3 Method for generating multiple controlled random tests

Let us use addition as the main operation in the construction of multiple random tests. It will make it possible to provide the minimal computational complexity in the construction of multiple random tests MCRTr. Indeed, all subsequent tests CRT(1), CRT(2),..., CRT(r-1) can be easily constructed based on CRT(0) by a single application of addition for each test set.

According to Definition 2, the controlled random test CRT consists of q test sets $T_i, i \in \{0, 1, 2, \dots, q-1\}$, each of which represents a m-bit binary vector $T_i = t_{i,m-1}t_{i,m-2}, \dots, t_{i,2}, t_{i,1}, t_{i,0}$, where $t_{i,l} \in \{0, 1\}$. Thus, test sets $T_i$ of the controlled random test CRT can be interpreted as g = 2^m-ary data $T_i \in \{0, 1, 2, \dots, 2^m-1\}$. For example, the test CRT = {0011, 0110, 1100, 0101, 1000} can be represented as a set of 16-ary data CRT = {3, 6, 12, 5, 8} (in the decimal system). If the initial test is CRT(k) = {T₀(k), T₁(k), T₂(k),..., Tq-1(k)}, the ratio that is used to obtain a new test CRT(l) = {T₀(l), T₁(l), T₂(l),..., Tq-1(l)} takes the following form:

$$ T_i(l) = T_i(k) + d \mod 2^m; i = 0, q-1. \tag{7} $$

In the given ratio, the parameter $d \in \{1, 2, 3, \dots, 2^m-1\}$ is used to achieve the difference between test sets and, accordingly, between tests CRT(l) and CRT(k). This parameter is crucial for achieving the maximum difference of the test CRT(l) from the test CRT(k) in terms of the previously defined metrics. For relation (7) the following proposition is true.
**Proposition 1.** If the test CRT(l) is derived from the initial test CRT(k) based on relation (7) for the parameter $d \in \{1, 2, 3, \dots, 2^m - 1\}$, then using the value $2^m - d$ as the parameter for the test CRT(l) and using the same relation (7) we obtain the initial test CRT(k). This proposition follows from the equality $d + 2^m - d \mod 2^m = 0$.

*Example 1.* When $m = 4$ for the initial test CRT(k) = {3, 6, 12, 5, 8} and the parameter $d = 8$, according to (7), we obtain CRT(l) = {11, 14, 4, 13, 0}. Using CRT(l) = {11, 14, 4, 13, 0} as the initial test and the same value $d = 8$, we obtain the test CRT(k) = {3, 6, 12, 5, 8}, which corresponds to the Proposition 1. For the same initial test CRT(k) = {3, 6, 12, 5, 8} and the other parameter $d = 5$, we will have a different result, namely, CRT(l) = {8, 11, 1, 10, 13}.

*Example 2.* For the test CRT(k) = {3, 7, 0, 6, 2, 5, 1, 4} constructed for $m = 3$ and parameter $d = 4$, according to (7), we find that CRT(l) = {7, 3, 4, 2, 6, 1, 5, 0}. For the same initial test and parameter $d = 5$, we will have a different result, i.e., CRT(l) = {0, 4, 5, 3, 7, 2, 6, 1}. Note that, in the given example, tests include various octal data values.

In the analysis of the above examples, in each of which two new tests obtained according to (7) are represented, the question arises as to which of these two tests is more effective for multiple testing. Thus, the problem arises of determining the optimal parameter $d$ when using the Euclidean distance as a quality metric for multiple tests. For ED(CRT(k), CRT(l)), where the test CRT(l) is obtained according to (7) we can use the following theorem [21].

**Theorem 1.** The Euclidean distance ED(CRT(k), CRT(l)) for tests CRT(k) and CRT(l), where CRT(k) = {T₀(k), T₁(k), T₂(k), ..., Tq-1(k)} consists of $q = 2^m$ m-bit nonrecurring randomly generated test sets $T_i(k) \in \{0, 1, 2, \dots, 2^m - 1\}$, and where test sets $T_i(l)$ are obtained according to the expression $T_i(l) = T_i(k) + d \mod 2^m$, $i = 0, q-1$, is calculated as

$$ED(CRT(k), CRT(l)) = \sqrt{2^m d(2^m - d)} \quad (8)$$

*Example 3.* The Euclidean distance for tests CRT(k) = {3, 7, 0, 6, 2, 5, 1, 4} and CRT(l) = {7, 3, 4, 2, 6, 1, 5, 0} is defined as ED(CRT(k), CRT(l)) = [(3 - 7)² + (7 - 3)² + (0 - 4)² + (6 - 2)² + (2 - 6)² + (5 - 1)² + (1 - 5)² + (4 - 0)²]¹/² = √128 Note that the same result ($d = 4$ and $m = 3$) we obtain using 8.

Values of Euclidean distances for the case $m = 3$ and possible values of $d$ are given in Table 1.

<table><caption>**Table 1.** Values of Euclidean distance for $m=3$</caption><thead><tr><th>d</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><td>ED(CRT(k), CRT(l))</td><td>√56</td><td>√96</td><td>√120</td><td>√128</td><td>√120</td><td>√96</td><td>√56</td></tr></tbody></table>

For the above Theorem 1 we have the following corollary [21].
**Corollary 1.** The Euclidean distance value $ED(CRT(k), CRT(l))$ will take the maximum value when $d = 2^{m-1}$, which corresponds to the solution of the equation

$$ \frac{\partial \sqrt{2^m d(2^m - d)}}{\partial d} = 0 $$

The validity of this corollary is confirmed by the results shown in Table 1, where for $d = 2^{m-1} = 2^{3-1} = 4$ the Euclidean distance takes the maximum value of $\sqrt{128}$

**Corollary 2.** The Euclidean distance $ED(CRT(k), CRT(l))$ obtained for the parameter $d$ is equal to the Euclidean distance of the parameter $2^m - d$, which follows from the equality

$$ \sqrt{2^m d(2^m - d)} = \sqrt{2^m (2^m - d)(2^m - (2^m - d))}. $$

This property is illustrated by numerical values of the Euclidean distance shown in Table 1.

**Corollary 3.** The value of the Euclidean distance $ED(CRT(k), CRT(l)) = \sqrt{2^m d(2^m - d)}$ obtained according to (8) for tests CRT(k) and CRT(l) consisting of $q = 2^m$ m-bit data $\{0, 1, 2, \dots, 2^m - 1\}$ can be used as the mean Euclidean distance $AED(CRT(k), CRT(l))$ equal to $\sqrt{qd(2^m - d)}$, between tests CRT(k) and CRT(l) that include $q < 2^m$ test sets.

For Example 1 and test CRT(l) = {11, 14, 4, 13, 0} obtained based on the initial test CRT(k) = {3, 6, 12, 5, 8} at $d = 8$, according to (7), we find that

$$ AED(CRT(k), CRT(l)) = \sqrt{5 \times 8 \times (2^4 - 8)} = \sqrt{320} $$

Note that, for these tests, the Euclidean distance is strictly equal to its average value. Indeed, $ED(CRT(k), CRT(l)) = [(3 - 11)^2 + (6 - 14)^2 + (12 - 4)^2 + (5 - 13)^2 + (8 - 0)^2]^{1/2} = \sqrt{320}$.

**Corollary 4.** If the Euclidean distance $ED(CRT(k), CRT(l))$ between controlled random tests CRT(k) and CRT(l) according to Theorem 1 is equal to $\sqrt{2^m d_l(2^m - d_l)}$ and, for tests CRT(k) and CRT(n), $ED(CRT(k), CRT(n)) = \sqrt{2^m d_n(2^m - d_n)}$, then $ED(CRT(l), CRT(n)) = \sqrt{2^m d_c(2^m - d_c)}$, where $d_c = d_l - d_n \mod 2^m$.

In accordance with Example 2 CRT(l) = {0, 4, 5, 3, 7, 2, 6, 1} and CRT(n) = {7, 3, 4, 2, 6, 1, 5, 0}, from the Corollary 4, we obtain that $d_c = d_l - d_n \mod 2^m = 5 - 4 \mod 2^3 = 1$ and

$$ ED(CRT(l), CRT(n)) = \sqrt{2^m d_c(2^m - d_c)} = \sqrt{2^3 \times 1 \times (2^3 - 1)} = \sqrt{56}. $$
## 4 Method for generating multiple controlled random tests

As a basis for constructing multiple controlled random tests

$$MCRT_r = \{CRT(0), CRT(1), CRT(2), \dots, CRT(r-1)\}, \quad (9)$$

we use relation (7), which is characterized by the minimal computational complexity in obtaining subsequent tests CRT(1), CRT(2), ..., CRT(r-1) based on the initial one CRT(0).

Then, the maximum minimum Hamming distance $MHD(CRT(k), CRT(l))$ and the maximum minimum Euclidean distance $MED(CRT(k), CRT(l))$, $k \neq l \in \{0, 1, 2, \dots, r-1\}$, according to (7), will be used in the construction of multiple random tests (9) as measures of efficiency.

Let us successively consider multiple controlled random tests $MCRT_r$ of various multiplicity ranging from double tests $MCRT_2$ that consist of CRT(0) and CRT(1), where the second test CRT(1) is generated based on the initial test CRT(0) according to (7). According to Corollary 1, the optimum value of the parameter $d$ in order to obtain CRT(1) is $2^{m-1}$. In this case, the Euclidean distance between the tests CRT(0) and CRT(1) takes the maximum value that maximizes the difference between these tests and the maximum effectiveness of their joint application.

Let us consider the following theorem for tests $MCRT_r$ with the multiplicity $r > 2$ [21].

**Theorem 2.** The maximum value $MHD(CRT(k), CRT(l))$ with which the tests CRT(k) and CRT(l) ($k \neq l \in \{0, 1, 2, \dots, r-1\}$) of the multiple controlled random test $MCRT_r$ that consists of $r > 2$ controlled random tests $\{CRT(0), CRT(1), CRT(2), \dots, CRT(r-1)\}$, each of which contains $q \le 2^m$ m-bit test sets, should comply is achieved in the case of the maximum minimum value $d_k - d_l$ ($k \neq l \in \{0, 1, 2, \dots, r-1\}$), and $d_k \neq d_l \in \{1, 2, \dots, 2^m - 1\}$.

Based on the theorem, we can conclude that for the general case of the multiple test $MCRT_r$ optimal values of parameters $d_1, d_2, \dots, d_{r-1}$ are the values that divide the range of integers of $0 - 2^m$ into regular intervals and are calculated according to the following relation:

$$d_i = \left\lfloor \frac{i2^m}{r} + 0.5 \right\rfloor, \quad i \in \{1, 2, \dots, r-1\}. \quad (10)$$

In the case of the triple random test $MCRT_3$, in order to obtain the second CRT(1) and third CRT(2) tests based on the initial test CRT(0), it is necessary to use optimum combinations of parameters $d_1$ and $d_2$ according to (10) used to obtain tests CRT(1) and CRT(2) according to (7). Correspondingly, for triple random tests,

$$d_1 = \lfloor 1 \times 2^m/3 + 0.5 \rfloor, \quad \text{and} \quad d_2 = \lfloor 2 \times 2^m/3 + 0.5 \rfloor.$$
For $m = 3$, we find that $d_1 = 3$ and $d_2 = 5$ and, for $m = 4$, $d_1 = 5$ and $d_2 = 11$.

Let us consider $MCRT_3 = \{CRT(0), CRT(1), CRT(2)\}$ when $m = 4$ using $d_1 = 5$ and $d_2 = 11$. The Euclidean distance between the tests $CRT(0)$ and $CRT(1)$ is calculated as follows $ED(CRT(0), CRT(1)) = \sqrt{16 \times 5 \times (16 - 5)} = \sqrt{880} = 29.7$. Other values of Euclidean distances for an arbitrary value $d$ are shown in Table 2. According to this table, the value of the Euclidean distance is

<table><caption>**Table 2.** Values of the Euclidean distance for $m = 4$</caption><thead><tr><th>d</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>ED(CRT(k), CRT(l))</td><td>15.5</td><td>21.2</td><td>24.9</td><td>27.7</td><td>29.7</td><td>30.9</td><td>31.7</td><td>32.0</td></tr><tr><td>d</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td></tr><tr><td>ED(CRT(k), CRT(l))</td><td>31.7</td><td>30.9</td><td>29.7</td><td>27.7</td><td>24.9</td><td>21.2</td><td>15.5</td><td>0</td></tr></tbody></table>

$ED(CRT(0), CRT(2)) = 29.7$. At the same time, in accordance with Corollary of 4, the distance between tests $CRT(1)$ and $CRT(2)$ is determined for $d$ equal to $d_2 - d_1 = 11 - 5 = 6$ as $ED(CRT(1), CRT(2)) = 29.7$.

The analysis of given values of Euclidean distances for the considered $MCRT_3$ indicates that $MED(CRT(k), CRT(l)) = 29.7$ for $k \neq l \in \{0, 1, 2\}$ according to (6) and $TED(CRT(2)) = ED(CRT(2), CRT(0)) + ED(CRT(2), CRT(1)) = 29.7 + 29.7 = 59.4$ according to (3) take the maximum value.

For the quadruple test $MCRT_4 = CRT(0), CRT(1), CRT(2), CRT(3)$ using (10), e.g., for $m = 4$, we find that $d_1 = 4, d_2 = 8$ and $d_3 = 12$. The values of the distances between any two tests $MCRT_4$ are given in Table 3. As can be seen

<table><caption>**Table 3.** Values of the Euclidean distance for the test $MCRT_4$</caption><thead><tr><th></th><th>CRT(0)</th><th>CRT(1)</th><th>CRT(2)</th><th>CRT(3)</th></tr></thead><tbody><tr><td>CRT(0)</td><td>-</td><td>27.7</td><td>32.0</td><td>27.7</td></tr><tr><td>CRT(1)</td><td>27.1</td><td>-</td><td>27.7</td><td>32.0</td></tr><tr><td>CRT(2)</td><td>32.0</td><td>27.7</td><td>-</td><td>27.7</td></tr><tr><td>CRT(3)</td><td>27.7</td><td>32.0</td><td>27.7</td><td>-</td></tr></tbody></table>

from Table 3, the value $MED(CRT(k), CRT(l)), k \neq l \in \{0, 1, 2, 3\}$ for $MCRT_4$ takes the maximum possible value of 27.7.

# 5 Experiments

As a measure of the effectiveness of multiple controlled random test $MCRT_r$ we used the metric $E(k, 2^m)$ introduced in [7] in order to construct subsequent test sets in the generation of the single-step controlled random test. In the case of multiple tests similar characteristic for the subsequent test $CRT(i)$ is formulated and can be determined as follows.
**Definition 4.** The additional number of binary combinations over all possible $k$ out of $2^m$ bits generated by test sets of the test CRT($i$) with respect to the binary combinations generated by previous tests of the multiple test CRT(0), CRT(1), CRT(2), ..., CRT($i-1$) is the measure of effectiveness $E(k, 2^m)$ for the subsequent controlled test CRT($i$).

Obviously, the larger the value of this metric, the more effective is the subsequent controlled test CRT($i$), which together with the previous tests makes it possible to achieve maximum efficiency. Note that in previous sections it was shown that in order to achieve the maximum efficiency of multiple controlled random tests $MCRT_r$, the Euclidean distance for the test CRT($i$) should be maximum in relation to previously generated tests CRT(0), CRT(1), ..., CRT($i-1$).

The problem of testing storage devices was used for the comparative analysis of the effectiveness of multiple controlled random tests $MCRT_r$ [20]. First, let us consider a storage device that consists of $2^3 = 8$ memory cells. In order to test it, we used the test CRT(0), which includes all possible three-bit addresses generated according to the scheme of march tests [13, 18]. In the formation of the next address the initial zero state of the memory cell is changed to a one state. Thus, the initial zero state of all cells of the storage device is changed to the one state. Note that values $ED(CRT(0), CRT(1))$ for two tests CRT(0), CRT(1) and $m = 3$ are given in Table 1. The test obtained according to (7) for all possible values of the parameter $d$ was used as the second controlled random test CRT(1). The resulting values of the metric $E(k, 2^m)$ for the double test $MCRT_2$ that consists of tests CRT(0) and CRT(1) are shown in Table 4. As can

<table><caption>**Table 4.** Estimation of the effectiveness of the double test for the storage device consisting of eight memory cells ($2^m = 8$) for $k = 3, 4, 5, 6$</caption><thead><tr><th rowspan="2">d</th><th colspan="4">E(k, 2<sup>m</sup>) - additional number of combinations on all possible k from 2<sup>m</sup> bits</th></tr><tr><th>E(3, 8)</th><th>E(4, 8)</th><th>E(5, 8)</th><th>E(6, 8)</th></tr></thead><tbody><tr><td>1</td><td>42</td><td>105</td><td>140</td><td>105</td></tr><tr><td>2</td><td>72</td><td>165</td><td>200</td><td>135</td></tr><tr><td>3</td><td>90</td><td>195</td><td>220</td><td>140</td></tr><tr><td>4</td><td>96</td><td>204</td><td>224</td><td>140</td></tr><tr><td>5</td><td>90</td><td>195</td><td>220</td><td>140</td></tr><tr><td>6</td><td>72</td><td>165</td><td>200</td><td>135</td></tr><tr><td>7</td><td>42</td><td>105</td><td>140</td><td>105</td></tr></tbody></table>

be seen from given numerical values, the effectiveness of the double test is in strict accordance with the values $ED(CRT(0), CRT(1))$ listed in Table 1. Indeed, for $d = 1$ and $d = 7$ the Euclidean distance between CRT(0) and CRT(1) equals the minimum value $\sqrt{56}$ (Table 1), respectively, and the number of additional binary combinations is minimum for all the values $k$. At the same time, for $d = 4$ and, consequently, for the maximum value $ED(CRT(0), CRT(1)) = \sqrt{128}$ the number of additional combinations is maximum (Table 4). The results in
Table 4 confirm the validity of theoretical provisions and, above all, the validity of Theorem 1.

When using controlled random tests, in most cases, the number $q$ of test sets is less than the total number of $2^m$ $m$-bit input patterns [1, 12–15]. Accordingly, the validity of the results of Theorem 1 for the case $q < 2^m$ and, above all, for Corollary 3 is significant for the proposed method of constructing controlled random tests. According to this corollary, the Euclidean distance $ED(CRT(k), CRT(l)) = \sqrt{2^m d(2^m - d)}$ obtained for $q = 2^m$ can be used as a mean value for $q < 2^m$ and can be determined by the relation $AED(CRT(k), CRT(l)) = \sqrt{qd(2^m - d)}$. It is obvious that, according to Corollary 3, the error between the experimental values $AED(CRT(k), CRT(l))$, and theoretical values should decrease with increasing value of $q$. When $q = 2^m$, experimental and theoretical values should be equal, which is confirmed by practical results given in Fig 1. The figure shows averaged values of deviations of the

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Average difference value (%) of the experimental value $AED(CRT(k), CRT(l))$ from the theoretical value obtained by the formula for $m = 10$.</figcaption></figure>

experimental data from the theoretical results depending on $q$. As can be seen from Fig. 1, even for $q > 100$, the experimental results hardly differ from the theoretical values, which confirms the validity of using the results of Theorem 1 to generate controlled random tests.

Finally, to confirm the proposed solution we have compared the coverage of Multiple Random Tests and Multiple Controlled Random Tests in terms of number of generated binary combinations for all arbitrary $k$ out of $N$ bits. Using both methods, we had generated multiple tests consisting of $r = 4$ tests with $q = 3$ subtests. In the first case all tests and subtests were generated randomly. In case of Multiple Controlled Random Tests only first test $CRT(0)$ was generated randomly whereas $CRT(1)$, $CRT(2)$ and $CRT(3)$ were generated with respect to Theorem 2 and equation (7). The obtained average results for 5000 experiments are shown in the Figure 2a and 2b. The x-axis represents the test number $CRT(i)$, and the y-axis – the number (in percent) of binary combinations for all arbitrary $k = 3$ and $k=4$ out of $N = 64$ bits. For Fig. 2, we observe
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** The coverage of all arbitrary *k* out of *N* bits for Multiple Random Tests and Multiple Controlled Random Test:</figcaption></figure>

a) *k*=3 and *N*=64, b) *k*=4 and *N*=64

that in both cases curves rise sharply and exhibits a smooth behavior. We observe that $MCRT_r$ gives us a bit higher level of fault coverage as in case of random patterns. The same time we should noted that $MCRT_r$ is characterized by easier computational method of test patterns generation in compare to other techniques.

# 6 Conclusion

The concept of multiple controlled random tests has been considered. Existing solutions have been analyzed, and a formal method for generating multiple tests has been proposed. The efficiency of using the Euclidean distance to construct multiple tests has been confirmed based on the experimental results for the case of multiple tests of storage devices. Finally the efficiency of proposed Multiple Controlled Random Tests has been tested. The experimental study demonstrate a high efficiency of the proposed solution.

# References

1. Anand, S., Burke, E.K., Chen, T.Y., Clark, J., Cohen, M.B., Grieskamp, W., Harman, M., Harrold, M.J., Mcminn, P.: An orchestrated survey of methodologies for automated software test case generation. J. Syst. Softw. **86**(8) (August 2013) 1978–2001

2. Chen, T.Y., Merkel, R.G.: Quasi-random testing. IEEE Transactions on Reliability **56**(3) (2007) 562–568
3. Lv, J., Hu, H., Cai, K., Chen, T.Y.: Adaptive and random partition software testing. IEEE T. Systems, Man, and Cybernetics: Systems **44**(12) (2014) 1649–1664

4. Malaiya, Y.K., Yang, S.: The coverage problem for random testing. In: Proceedings of the 1994 IEEE International Test Conference. ITC '84 (1984) 237–245

5. Shahbazi, A., Tappenden, A.F., Miller, J.: Centroidal voronoi tessellations – a new approach to random testing. IEEE Transactions on Software Engineering **39**(2) (2013) 163–183

6. Sosnowski, J., Wabia, T., Bech, T.: Path delay fault testability analysis. In: 15th IEEE International Symposium on Defect and Fault-Tolerance in VLSI Systems (DFT 2000), 25-27 October 2000, Yamanashi, Japan, Proceedings. (2000) 338

7. Yarmolik, S., Yarmolik, V.: Controlled random tests. Automation and Remote Control **73**(10) (2012) 1704–1714

8. Kuo, F.: An indepth study of mirror adaptive random testing. In Choi, B., ed.: Proceedings of the Ninth International Conference on Quality Software, QSIC 2009, Jeju, Korea, August 24-25, 2009, IEEE Computer Society (2009) 51–58

9. Tappenden, A., Miller, J.: A novel evolutionary approach for adaptive random testing. IEEE Transactions on Reliability **58**(4) (2009) 619–633

10. Wu, S.H., Jandhyala, S., Malaiya, Y.K., Jayasumana, A.P.: Antirandom testing: a distance-based approach. VLSI Design **2008** (January 2008) 1–2

11. Xu, S.: Orderly random testing for both hardware and software. In: Proceedings of the 2008 14th IEEE Pacific Rim International Symposium on Dependable Computing, Washington, DC, USA, IEEE Computer Society (2008) 160–167

12. Zhou, Z.: Using coverage information to guide test case selection in adaptive random testing. Computer Software and Applications Conference Workshops **0** (2010) 208–213

13. Chen, T.Y., Kuo, F.C., Merkel, R.G., Tse, T.H.: Adaptive random testing: The art of test case diversity. Journal of Systems and Software **83** (January 2010) 60–66

14. Yarmolik, S.V., Yarmolik, V.N.: The synthesis of probability tests with a small number of kits. Automatic Control and Computer Sciences **45**(3) (2011) 133–141

15. Sahari, M.S., Aain, A.K., Grout, I.A.: Scalable antirandom testing (SAT). International Journal of Innovative Science and Modern Engineering (IJISME) **3** (2015) 33–35

16. Mrozek, I., Yarmolik, V.N.: Antirandom test vectors for BIST in hardware/software systems. Fundam. Inform. **119**(2) (2012) 163–185

17. Mrozek, I., Yarmolik, V.N.: Iterative antirandom testing. J. Electron. Test **28**(3) (June 2012) 301–315

18. Yarmolik, V.N., Yarmolik, S.V.: Address sequences. Automatic Control and Computer Sciences **48**(4) (2014) 207–213

19. Malaiya, Y.K.: Antirandom testing: Getting the most out of black-box testing. In: Proceedings of 6th IEEE International Symposium on Software Reliability Engineering. ISSRE '95, IEEE Computer Society (1995) 86–95

20. Yarmolik, V., Yarmolik, S.: The repeated nondestructive march tests with variable address sequences. Automation and Remote Control **68**(4) (2007) 688–698

21. Yarmolik, V.N., Mrozek, I., Yarmolik, S.V.: Controlled method of random test synthesis. Automatic Control and Computer Sciences **49**(6) (2016) 395–403