Ireneusz Mrozek
email: i.mrozek@pb.edu.pl

Vyacheslav Yarmolik
email: yarmolik10ru@yahoo.com

Methods of Synthesis of Controlled Random Tests

Keywords: random tests, controlled tests, multiple tests, Hemming distance, Euclidean distance

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.

Introduction

Among the black box techniques, random testing is generally regarded as a very effective technique for testing modern hardware and software systems [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF][START_REF] Chen | Quasi-random testing[END_REF][START_REF] Lv | Adaptive and random partition software testing[END_REF][START_REF] Malaiya | The coverage problem for random testing[END_REF][START_REF] Shahbazi | Centroidal voronoi tessellations -a new approach to random testing[END_REF][START_REF] Sosnowski | Path delay fault testability analysis[END_REF][START_REF] Yarmolik | Controlled random tests[END_REF]. All modifications of random testing are united by the controllability principle for test pattern generation [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF][START_REF] Malaiya | The coverage problem for random testing[END_REF][START_REF] Yarmolik | Controlled random tests[END_REF][START_REF] Kuo | An indepth study of mirror adaptive random testing[END_REF][START_REF] Tappenden | A novel evolutionary approach for adaptive random testing[END_REF][START_REF] Wu | Antirandom testing: a distance-based approach[END_REF][START_REF] Xu | Orderly random testing for both hardware and software[END_REF][START_REF] Zhou | Using coverage information to guide test case selection in adaptive random testing[END_REF]. These tests are constructed based on the calculation of certain characteristics for the controlled selection of another random test set [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF].

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 [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF][START_REF] Malaiya | The coverage problem for random testing[END_REF][START_REF] Zhou | Using coverage information to guide test case selection in adaptive random testing[END_REF][START_REF] Chen | Adaptive random testing: The art of test case diversity[END_REF][START_REF] Yarmolik | The synthesis of probability tests with a small number of kits[END_REF][START_REF] Sahari | Scalable antirandom testing (SAT)[END_REF][START_REF] Mrozek | Antirandom test vectors for BIST in hardware/software systems[END_REF][START_REF] Mrozek | Iterative antirandom testing[END_REF]. 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 [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF][START_REF] Malaiya | The coverage problem for random testing[END_REF][START_REF] Zhou | Using coverage information to guide test case selection in adaptive random testing[END_REF][START_REF] Chen | Adaptive random testing: The art of test case diversity[END_REF][START_REF] Mrozek | Antirandom test vectors for BIST in hardware/software systems[END_REF].

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 [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF][START_REF] Malaiya | The coverage problem for random testing[END_REF][START_REF] Zhou | Using coverage information to guide test case selection in adaptive random testing[END_REF][START_REF] Chen | Adaptive random testing: The art of test case diversity[END_REF][START_REF] Mrozek | Antirandom test vectors for BIST in hardware/software systems[END_REF] 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.

Analysis of controlled random tests

All existing methods for constructing controlled random tests are based on the assertion which is explained below [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF][START_REF] Zhou | Using coverage information to guide test case selection in adaptive random testing[END_REF][START_REF] Chen | Adaptive random testing: The art of test case diversity[END_REF][START_REF] Sahari | Scalable antirandom testing (SAT)[END_REF]. 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 [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF][START_REF] Yarmolik | Controlled random tests[END_REF][START_REF] Chen | Adaptive random testing: The art of test case diversity[END_REF] Definition 1. The test (T ) is a set of 2 <= q <= 2 m test sets:

{T 0 , T 1 , T 2 , ..., T q-1 } where T i = t i,m-1 , t i,m-2 , ..., t i,2 , t i,1 , t i,0 and t i,l ∈ {0, 1}
Definition 2. A controlled random test, where CRT = {T 0 , T 1 , T 2 , ..., T q-1 }, is a test that includes q < 2 m m-bit randomly generated test patterns denoted by T i , where i ∈ {0, 1, 2, ..., q -1}, and where T i = t i,m-1 , t i,m-2 , ..., t i,2 , t i,1 , t i,0 and t i,l ∈ {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 , ..., T i-1 }.

Hamming distance and Euclidean distance are often used as difference measures between the test pattern T i and previously generated patterns [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF][START_REF] Xu | Orderly random testing for both hardware and software[END_REF][START_REF] Yarmolik | Address sequences[END_REF]. 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 ⊕ T j ) of the vector T i ⊕ T j according to the following formula (1):

HD(T i , T j ) = w(T i ⊕ T j ) = m-1 l=0 (t i,l ⊕ t j,l ). (1)
Euclidean distance ED(T i , T j ) is computed according to the formula [START_REF] Chen | Quasi-random testing[END_REF].

ED(T i , T j ) = m-1 l=0 (t i,l -t j,l ) 2 = m-1 l=0 (t i,l ⊕ t j,l ) = HD(T i , T j ). ( 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 , . . . , T i-1 ) are used [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF][START_REF] Shahbazi | Centroidal voronoi tessellations -a new approach to random testing[END_REF][START_REF] Wu | Antirandom testing: a distance-based approach[END_REF][START_REF] Xu | Orderly random testing for both hardware and software[END_REF][START_REF] Mrozek | Antirandom test vectors for BIST in hardware/software systems[END_REF][START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF]. Thus, for the next pattern T i , the total value of the distances with respect to (T 0 , T 1 , T 2 , . . . , T i-1 ) constitutes the following:

THD(T i ) = i-1 j=0 HD(T i , T j ); TED(T i ) = i-1 j=0 ED(T i , T j ). (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 [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF].

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 [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF][START_REF] Zhou | Using coverage information to guide test case selection in adaptive random testing[END_REF][START_REF] Chen | Adaptive random testing: The art of test case diversity[END_REF][START_REF] Sahari | Scalable antirandom testing (SAT)[END_REF][START_REF] Mrozek | Antirandom test vectors for BIST in hardware/software systems[END_REF][START_REF] Yarmolik | The repeated nondestructive march tests with variable address sequences[END_REF]. 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 [START_REF] Yarmolik | The synthesis of probability tests with a small number of kits[END_REF][START_REF] Yarmolik | The repeated nondestructive march tests with variable address sequences[END_REF], the minimum Hamming distance minHD(T i , T j ) or the Euclidean distance minED(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 [START_REF] Yarmolik | The synthesis of probability tests with a small number of kits[END_REF], the subsequent test set T i is selected from possible candidates for the tests by the criterion of the maximum value min j∈{0,1,...,i-1} HD(T i , T j ) or min j∈{0,1,...,i-1}

ED(T i , T j ) (4)
which provides the maximum distance (difference) of the test set T i from all previously generated sets {T 0 , T 1 , T 2 , ..., T i-1 }. If the maximum value of ( 4) is achieved, it also maximizes values T HD(T i ) and T ED(T i ) according to (3) [START_REF] Yarmolik | The repeated nondestructive march tests with variable address sequences[END_REF].

Let us define a multiple controlled test based on the methodology of single step controlled random tests. Definition 3. The multiple controlled random test M CRT r consists of r single step controlled random tests CRT(0), CRT(1), CRT(2), . . . , 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 ∈ {1, 2, 3, . . . , 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), . . . , 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 = T k,i , i ∈ {0, 1, 2, . . . , q -1}.
The Euclidean distance for CRT (k) and CRT (l) is defined as:

ED(CRT (k), CRT (l)) = q-1 i=0 (T i,k -T i,l ) 2 . (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 M HD(CRT (i)) and the maximum value of the Euclidean distance M ED(CRT (i)) as follows:

M HD(CRT (i)) = max CRTv (i),v∈{0,...,w} { min j∈{0,1,...,i-1} HD(CRT 1 (i), CRT (j)), . . . , min j∈{0,1,...,i-1} HD(CRT w (i), CRT (j))}; M ED(CRT (i)) = max CRTv (i),v∈{0,...,w} { min j∈{0,1,...,j-1} ED(CRT 1 (i), CRT (j)), . . . , min j∈{0,1,...,i-1} ED(CRT w (i), CRT (j))}. (6)
According to given metrics ( 6), the subsequent controlled random test CRT (i) is selected from the set {CRT 1 (i), CRT 2 (i), . . . , CRT w (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)}.

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 M CRT r . 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 ∈ {0, 1, 2, . . . , q -1}, each of which represents a m-bit binary vector T i = t i,m-1 t i,m-2 , . . . , t i,2 , t i,1 , t i,0 , where t i,l ∈ {0, 1}. Thus, test sets T i of the controlled random test CRT can be interpreted as g = 2 m -ary data T i ∈ {0, 1, 2, . . . , 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 0 (k), T 1 (k), T 2 (k), . . . , T q-1 (k)}, the ratio that is used to obtain a new test CRT (l) = {T 0 (l), T 1 (l), T 2 (l), . . . , T q-1 (l)} takes the following form:

T i (l) = T i (k) + d mod 2 m ; i = 0, q -1. (7)
In the given ratio, the parameter d ∈ {1, 2, 3, . . . , 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 [START_REF] Yarmolik | Controlled random tests[END_REF] the following proposition is true. Proposition 1. If the test CRT (l) is derived from the initial test CRT (k) based on relation [START_REF] Yarmolik | Controlled random tests[END_REF] for the parameter d ∈ {1, 2, 3, . . . , 2 m -1}, then using the value 2 m -d as the parameter for the test CRT (l) and using the same relation [START_REF] Yarmolik | Controlled random tests[END_REF] we obtain the initial test CRT (k). This proposition follows from the equality d + 2 m -d mod 2 m = 0. In the analysis of the above examples, in each of which two new tests obtained according to [START_REF] Yarmolik | Controlled random tests[END_REF] 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 [START_REF] Yarmolik | Controlled random tests[END_REF] we can use the following theorem [START_REF] Yarmolik | Controlled method of random test synthesis[END_REF].

Theorem 1. The Euclidean distance ED(CRT (k), CRT (l)) for tests CRT (k) and CRT (l), where CRT (k) = {T 0 (k), T 1 (k), T 2 (k), . . . , T q-1 (k)} consists of q = 2 m m-bit nonrecurring randomly generated test sets T i (k) ∈ {0, 1, 2, . . . , 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)) = 2 m d(2 m -d). ( 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) 2 + (7 -3) 2 + (0 -4) 2 + (6 -2) 2 + (2 -6) 2 + (5 -1) 2 + (1 -5) 2 + (4 -0) 2 ] 1/2 = √ 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. For the above Theorem 1 we have the following corollary [START_REF] Yarmolik | Controlled method of random test synthesis[END_REF].

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

∂ 2 m d(2 m -d) ∂d = 0
The validity of this corollary is confirmed by the results shown in Table 1, where for d = 2 m-1 = 2

2 m d(2 m -d) = 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.

(n), ED(CRT (k), CRT (n)) = 2 m d n (2 m -d n ), then ED(CRT (l), CRT (n)) = 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)) = 2 m d c (2 m -d c ) = 2 3 × 1 × (2 3 -1) = √ 56.

Method for generating multiple controlled random tests

As a basis for constructing multiple controlled random tests

M CRT r = {CRT (0), CRT (1), CRT (2), . . . , CRT (r -1)}, (9)
we use relation [START_REF] Yarmolik | Controlled random tests[END_REF], 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 M HD(CRT (k), CRT (l)) and the maximum minimum Euclidean distance M ED(CRT (k), CRT (l)), k = l ∈ {0, 1, 2, . . . , r -1}, according to [START_REF] Yarmolik | Controlled random tests[END_REF], will be used in the construction of multiple random tests [START_REF] Tappenden | A novel evolutionary approach for adaptive random testing[END_REF] as measures of efficiency.

Let us successively consider multiple controlled random tests M CRT r of various multiplicity ranging from double tests M CRT 2 that consist of CRT (0) and CRT [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF], where the second test CRT (1) is generated based on the initial test CRT (0) according to [START_REF] Yarmolik | Controlled random tests[END_REF]. 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 M CRT r with the multiplicity r > 2 [START_REF] Yarmolik | Controlled method of random test synthesis[END_REF].

Theorem 2. The maximum value M HD(CRT (k), CRT (l)) with which the tests CRT (k) and CRT (l) (k = l ∈ {0, 1, 2, . . . , r -1}) of the multiple controlled random test M CRT r that consists of r > 2 controlled random tests {CRT (0), CRT (1), CRT (2), . . . , CRT (r -1)}, each of which contains q ≤ 2 m m-bit test sets, should comply is achieved in the case of the maximum minimum value d k -d l (k = l ∈ {0, 1, 2, . . . , r -1}), and

d k = d l ∈ {1, 2, . . . , 2 m -1}.
Based on the theorem, we can conclude that for the general case of the multiple test M CRT r optimal values of parameters d 1 , d 2 , . . . , 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 = i2 m r + 0.5 i ∈ {1, 2, . . . , r -1}. (10)
In the case of the triple random test M CRT 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 [START_REF] Wu | Antirandom testing: a distance-based approach[END_REF] used to obtain tests CRT (1) and CRT (2) according to [START_REF] Yarmolik | Controlled random tests[END_REF]. Correspondingly, for triple random tests, 2. According to this table, the value of the Euclidean distance is 3. As can be seen from Table 3, the value M ED(CRT (k), CRT (l)), k = l ∈ {0, 1, 2, 3} for M CRT 4 takes the maximum possible value of 27.7.

d 1 = ⌊1 × 2 m /3 + 0.

Experiments

As a measure of the effectiveness of multiple controlled random test M CRT r we used the metric E(k, 2 m ) introduced in [START_REF] Yarmolik | Controlled random tests[END_REF] 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.

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 √ 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)) = √ 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 [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF][START_REF] Zhou | Using coverage information to guide test case selection in adaptive random testing[END_REF][START_REF] Chen | Adaptive random testing: The art of test case diversity[END_REF][START_REF] Yarmolik | The synthesis of probability tests with a small number of kits[END_REF][START_REF] Sahari | Scalable antirandom testing (SAT)[END_REF]. 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)) = 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)) = 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 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. [START_REF] Yarmolik | Controlled random tests[END_REF]. 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 that in both cases curves rise sharply and exhibits a smooth behavior. We observe that M CRT r gives us a bit higher level of fault coverage as in case of random patterns. The same time we should noted that M CRT r is characterized by easier computational method of test patterns generation in compare to other techniques.

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.

Example 1 .Example 2 .

 12 When m = 4 for the initial test CRT (k) = {3, 6, 12, 5, 8} and the parameter d = 8, according to[START_REF] Yarmolik | Controlled random tests[END_REF], 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}. For the test CRT (k) = {3, 7, 0, 6, 2, 5, 1, 4} constructed for m = 3 and parameter d = 4, according to[START_REF] Yarmolik | Controlled random tests[END_REF], 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.

Corollary 3 .Corollary 4 .

 34 The value of the Euclidean distance ED(CRT (k), CRT (l)) = 2 m d(2 m -d) obtained according to[START_REF] Kuo | An indepth study of mirror adaptive random testing[END_REF] for tests CRT (k) and CRT (l) consisting of q = 2 m m-bit data {0, 1, 2, . . . , 2 m -1} can be used as the mean Euclidean distance AED(CRT (k), CRT (l)) equal to 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)) = 5 × 8 × (2 4 -8) = √ 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 = √ 320. 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 2 m d l (2 m -d l ) and, for tests CRT (k) and CRT

  5⌋, and d 2 = ⌊2 × 2 m /3 + 0.5⌋. 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 M CRT 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)) = 16 × 5 × (16 -5) = √ 880 = 29.7. Other values of Euclidean distances for an arbitrary value d are shown in Table

  2 15.5 0 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 M CRT 3 indicates that M ED(CRT (k), CRT (l)) = 29.7 for k = l ∈ {0, 1, 2} according to (6) and T ED(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 M CRT 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 M CRT 4 are given in Table

Fig 1 .Fig. 1 .

 11 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.

Fig. 2 .

 2 Fig. 2. The coverage of all arbitrary k out of N bits for Multiple Random Tests and Multiple Controlled Random Test: a) k=3 and N =64, b) k=4 and N =64

Table 1 .

 1 Values of Euclidean distance for m=3

	d	1	2		3		4		5	6	7
	ED(CRT (k), CRT (l))	√	56	√	96	√	120	√	128	√	120	√	96	√	56

Table 2 .

 2 Values of the Euclidean distance for m = 4

	d	1	2	3	4	5	6	7	8
	ED(CRT (k), CRT (l)) 15.5 21.2 24.9 27.7 29.7 30.9 31.7 32.0
	d	9 10 11 12 13 14 15 16
	ED(CRT (k), CRT (l)) 31.7 30.9 29.7 27.7 24.9 21.

Table 3 .

 3 Values of the Euclidean distance for the test M CRT4

		CRT (0) CRT (1) CRT (2) CRT (3)
	CRT (0)	-	27.7	32.0	27.7
	CRT (1) 27.1	-	27.7	32.0
	CRT (2) 32.0	27.7	-	27.7
	CRT (3) 27.7	32.0	27.7	-

This paper was supported by grant S/WI/3/13 from Faculty of Computer Science at

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 M CRT 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 M CRT r [START_REF] Yarmolik | The repeated nondestructive march tests with variable address sequences[END_REF]. 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 [START_REF] Chen | Adaptive random testing: The art of test case diversity[END_REF][START_REF] Yarmolik | Address sequences[END_REF]. 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 [START_REF] Yarmolik | Controlled random tests[END_REF] for all possible values of the parameter d was used as the second controlled random test CRT [START_REF] Anand | An orchestrated survey of methodologies for automated software test case generation[END_REF]. The resulting values of the metric E(k, 2 m ) for the double test M CRT 2 that consists of tests CRT (0) and CRT (1) are shown in Table 4. As can


Pawe L Szeszko
email: p.szeszko@gmail.com

Magdalena Topczewska
email: m.topczewska@pb.edu.pl

Empirical assessment of performance measures for preprocessing moments in imbalanced data classification problem

The article concerns the problem of imbalanced data classification, when classes, into which elements belong, are not equally represented. In the classification model building process cross-validation technique is one of the most popular to assess the efficacy of a classifier. While over-sampling methods are used to create new objects to obtain the balance between the number of objects in classes, inappropriate usage of the preprocessing moment has a direct impact on the achieved results. In most cases they are overestimated. To present and assess this phenomenon in this paper three preprocessing techniques (SMOTE, Safelevel SMOTE, SPIDER) and their modifications are used to make new elements of data sets to balance cardinalities of classes, and two classification methods (SVM, C4.5) are compared. k-folds cross-validation technique (k=10) considering two moments of preprocessing approaches is performed. The measures as precision, recall, F -measure and area under the ROC curve (AUC) are calculated and compared.

Introduction

The problem of imbalanced classes in datasets is deemed to be one out of ten the most important data exploration tasks nowadays. Therefore more and more scientists focus on developing methods that can provide the improvement of model performance for such difficult data. Many techniques to deal with the problem have been proposed [START_REF] Chawla | Editorial: special issue on learning from imbalanced data sets[END_REF][START_REF] He | Learning from imbalanced data[END_REF]. The issue appears when the cardinality of at least one class is lower than the cardinality of remaining classes. In the two classes task the imbalance ratio describes the proportion of the majority (negative) class objects to the minority (positive) class and can vary depending on a dataset. Classification models created on the basis of such data have to cope with misclassification errors of the minority class. This is the consequence of the fact that many classifiers consider the misclassification errors equally for all objects, regardless of the class to which they belong. However, in such cases the costs of incorrectness vary markedly. Considering for instance cancer diseases, the number of ill patients can be significantly smaller than the healthy or the sick for other reasons. Another well-known example is fraud detection, when a fraud occurs relatively infrequently. In mentioned situations the great emphasis is placed on the correct classification of minority class objects, definitely greater than in the majority class elements. To reduce the impact of imbalance between the number of objects in particular classes, three groups of approaches have been proposed: data level, algorithm level and cost-sensitive level. The algorithms belonging to the first category -data-level approach -operate on data objects solely and they are independent from the classification models. In undersampling methods superfluous objects are removed, thus the subset of original dataset is created to be used in model building process. In oversampling methods existing objects, from positive class in particular, can be replicated or new objects can be created. The third approach is constituted by hybrid methods -superfluous objects are removed and new necessary elements are created. The second group describes algorithm-level approaches in which instead of data, existing model-building algorithms are adjusted to classify objects regardless of the disparity between cardinalities of classes. Finally, the last category considers unequal misclassification costs, because false negative and false positive costs are not the same as in cancer patients example. An important issue here is to determine the cost ratio or the cost matrix. The aim of cost-sensitive level methods is to build models with minimum misclassification costs. By creating new objects, replicating or removing existing ones, the number of objects as well as the distributions of classes in a dataset are changed. Then to proceed the classification process and assess the efficacy of classification methods, one has to be cautious. In certain articles, the authors do not apply data preprocessing in appropriate moment while using cross-validation techniques, and they test the performance of the model on the artificial examples as well. It can lead to the overestimated results of the classification. The aim of this paper is to compare the results obtained for two different moments of imbalanced datasets preprocessing and their influence on the classification performance measures as well as to assess empirically the overestimation level. Three data-level approaches using k-nearest neighbour technique [START_REF] Cover | Nearest neighbor pattern classification[END_REF] are considered: SMOTE [START_REF] Chawla | Smote: Synthetic minority over-sampling technique[END_REF], Safe-level SMOTE [START_REF] Bunkhumpornpat | Safe-Level-SMOTE: Safe-Level-Synthetic Minority Over-Sampling TEchnique for Handling the Class Imbalanced Problem[END_REF] and SPIDER [START_REF] Stefanowski | Selective Pre-processing of Imbalanced Data for Improving Classification Performance[END_REF] and two classifiers are used: C4.5 and SVM using John Platt's sequential minimal optimization algorithm for training a support vector classifier.

Data preprocessing

In this paper three approaches to the construction of classifiers from imbalanced data sets are compared: SMOTE, Safe-level SMOTE and SPIDER.

SMOTE

The SMOTE (Synthetic Minority Over-sampling Technique) [START_REF] Chawla | Smote: Synthetic minority over-sampling technique[END_REF] is the most versatile method and enables to create new objects of the minority class. For each p positive object, among its k nearest neighbours also belonging to the positive class, N/100 objects are sampled randomly with replacement, where N is a number of objects to generate. To compute the position of a new element, the difference between feature vector values of the considered object and a chosen neighbour should be calculated and multiplied by a gap -a random number between 0 and 1. The new object is then generated by adding that result to the feature vector of an examined p object.

Safe-level SMOTE

Safe-level SMOTE [START_REF] Bunkhumpornpat | Safe-Level-SMOTE: Safe-Level-Synthetic Minority Over-Sampling TEchnique for Handling the Class Imbalanced Problem[END_REF] is a modification of the original SMOTE algorithm. It draws particular attention to the classes of objects that encircle examined positive objects. For each examined positive p element the safe-level indicator (sl p ) is defined and calculated as the number of positive instances among its k nearest neighbours. Additionally, one randomly selected neighbour is chosen (n), and for this element safe-level indicator (sl n ) is also computed. In the next step safe level ratio (sl ratio = slp sln ) is calculated and one of five cases is chosen: if sl ratio = ∞ and sl p = 0, no new object is generated, because p and n are treated as noisy, i.e. elements situated in the negative class area; if sl ratio = ∞ and sl p ̸ = 0, n is noisy; p object is replicated; so gap = 0; if sl p = sl n , then sl ratio = 1 and gap is a random number between 0 and 1; new object will be situated between p and n; if sl ratio > 1, p object is safer than n object, because in its surroundings there are more safer positive objects, hence gap is a random number between 0 and 1 slratio to situate a new object closer to p; if sl ratio < 1, n object is safer than p object, hence gap is a random number between 1 -sl ratio and 1 to situate a new object closer to n.

The number of iterations is matched to balance the cardinalities of classes.

SPIDER

The selective preprocessing algorithm SPIDER [START_REF] Stefanowski | Selective Pre-processing of Imbalanced Data for Improving Classification Performance[END_REF] combines local over-sampling of the minority class with filtering difficult objects from the negative class. The method assigns to each object one of two labels: safe -if its classification result using k-nearest neighbour rule (k = 3) is correct, or noisy otherwise. The special D set is created and all noisy majority class objects are transferred into it to remove them from a dataset at the end of the algorithm. Three techniques of a dataset modification can be mentioned.

Weak amplification method increases the importance of the minority class objects labelled as noisy by their replications. The number of replications depends on the number of safe objects among three neighbours of each examined element. Additionally, all noisy majority class elements are removed from a dataset. Weak amplification and relabelling adds an adjective step to the previous method.

For elective noisy positive object, some among its three negative noisy neighbours are relabelled as positive elements. Modified negative elements are removed from the D set. The third method is called strong amplification and is focused on all positive class objects. The importance of each safe element is increased by its replication -the number of copied objects equals the number of negative objects among its nearest neighbours. The modification of noisy positive elements depends on the k-nearest neighbours classification results when k = 5. In the correct result case, the number of replications is the same as for safe objects, otherwise instead of three, five nearest neighbours for each examined element are taken into considerations.

Classification model performance

Predictive model creating is one of the main goals of machine learning process. Models built using existing elements from a dataset should give an answer which class a new unclassified object should be assigned to. To compare model building algorithms we need methods that can predict performance of a model for objects that were unused in a training process, because the model is fitted to the data on which it was constructed. Therefore training and test sets should be independent and it is very necessary issue if we try to assess performance of the classification models in real situations.

Estimating the predictive model performance

For the purpose described in a previous paragraph a cross-validation method was proposed. It divides the input set into independent training and test sets.

If the input dataset is large, it can be just randomly divided into two parts: training and test sets, for example in proportion 2:1. It is called a hold-out method. The main advantage of this approach is low cost of computing resources. A big disadvantage is uncertainty that the class distributions are represented in both parts properly, hence received results may not present a real efficacy of a model. This problem can be solved with repeated random division of the input dataset, but still there is no certitude that appropriate elements have been chosen to the test sets. An approach that should provide proper representation of objects in a test set is k-fold cross-validation technique [START_REF] Hastie | The elements of statistical learning: data mining, inference and prediction[END_REF]. This method divides the input set into k parts. In each of k iterations k-th part is used as a test set and other objects are used for a model training. In advance of a division the order of the objects should be changed randomly. Additionally, the stratification process can be performed to preserve the distributions of classes in training and test tests.

In this paper 10-folds cross-validation process has been chosen for calculations.

In the class imbalance problem, when data need preprocessing, there is another issue to reflect -the moment of preprocessing. It might seem to be correct to prepare datasets first and then initiate classification process, as presented in the Figure 1. However, it is not appropriate mode of an action, since new artificial objects will take part in testing process, and the results will be affected directly [START_REF] Altini | Dealing with imbalanced data: undersampling, oversampling and proper cross-validation[END_REF]. Due to that fact the appropriate approach is to run preprocessing algorithms for each training set internally during cross-validation process to not include synthetic elements into test sets, as shown in the Figure 2.

Classification quality assessment methods

Comparison methods of various classification techniques constitute an important element of the machine learning process. In the case of two classes problem, the elements of the class that is the object of an interest are denoted as positive, while remaining objects are denoted as negative.

We use the following notation:

-TP (true positives) -a number of positive objects classified correctly -TN (true negatives) -a number of negative objects classified correctly -FN (false negatives) -a number of positive objects classified incorrectly as negative -FP (false positives) -a number of negative objects classified incorrectly as positive These four terms form the cells of the confusion matrix. Additionally, on the basis of them various measures are built.

Performance measures

The most popular and well-known measures describing the performance of a classifier are the accuracy Q (1) computed as the proportion of the objects

Q = T P + T N T P + F P + T N + F N , ( 1
)
and the error rate Err rate (2) respectively, as the proportion of misclassified objects:

Err rate = F P + F N T P + F P + T N + F N . ( 2
)
These measures are not appropriate for the case of the imbalanced class problem, when the error weights of the misclassified objects belonging to the minority class are not equal as for the majority class or the remaining classes. To comprehend of such a problem precision (3) and recall (4) have been introduced:

P recision = T P T P + F P , ( 3
)
Recall = Sensitivity = T P rate = T P T P + F N . ( 4
)
Furthermore, there is F-measure that is defined as the harmonic mean of precision and recall

F = (1 + β 2 ) • P recision • Recall β 2 • P recision + Recall , ( 5
)
and AUC is the the area under the ROC curve [9]

AU C = 1 + T P rate -F P rate 2 , ( 6
)
where F P rate = F P F P +T N .

Experiment

The experiment concerning the influence of the data preprocessing moment on the final results of the classification methods has been performed. 25 datasets from KEEL [START_REF] Alcalá-Fdez | Keel datamining software tool: Data set repository, integration of algorithms and experimental analysis framework[END_REF] repository were selected and their characteristics is presented in the Table 1. These datasets were created on the basis of 10 datasets from UCI repository [START_REF]UC Irvine Machine Learning Repository[END_REF].

Calculations have been performed using classes as parts of the Weka data min- ing software [START_REF] Hall | The weka data mining software: An update[END_REF] and own application. Precision, recall, F-measure and AUC have been calculated for two moments of preprocessing and for two classification algorithms and ten preprocessing variants. To reduce the randomness of the results each 10-folds cross-validation process was repeated 10 times with different random number generator seed. Next, the differences between two points were calculated and examined. As modification of SMOTE algorithm also the number of synthetic objects was verified.

The numbers in the SMOTE100, 200, . . . , 500 versions denote % of the minority class elements that were generated. The SMOTEAuto indicates that after preprocessing process the number of objects in the classes was balanced. For the SVM method C=100 and linear kernel have been chosen to be presented in the paper.

To compare the differences between appropriate and inappropriate preprocessing moments during model evaluation, the t-test for dependent observations or the Wilcoxon signed-rank test were applied according to the normal or non-normal distributions of samples. The significance level was set at the level of 0.05. To unify the results, median values and the range as adequate statistics for all cases are presented in the Table 2.

For the whole range of datasets and methods, the average value of the precision difference between appropriate and inappropriate moment of preprocessing is at the level of 0.1792 ± 0.1259 (median 0.1691). The average value of the recall difference equals 0.0711 ± 0.0976 (median 0.0478); the average value of the Fmeasure difference: 0.1373 ± 0.1099 (median 0.1244) and the average value of the AUC difference: 0.0421 ± 0.0507 (median 0.0274). For the C4.5 algorithm these results are as follows: precision: 0.1814 ± 0.1261 (median 0.1719); recall: 0.1154 ± 0.1011 (median 0.0920); F-measure: 0.1546 ± 0.1141 (median 0.1420) and AUC: 0.0659 ± 0.0546 (median 0.0532). For the SVM algorithm adequately: precision: 0.1768 ± 0.1259 (median 0.1667); recall: 0.0267 ± 0.0701 (median 0.0178); F-measure: 0.1200 ± 0.1028 (median 0.1063) and AUC: 0.0183 ± 0.0320 (median 0.0111). All these results are statistically significantly different than zero. Apart from statistics, p-values for particular methods and algorithms are presented in the Table 2. In almost all cases there is a statistically significant difference between average results in two moments of preprocessing. Only for spidertype methods in few cases there is no statistical difference for SVM algorithm. The linear decision function not proper for the structure of data in classes may be the reason. Additionally two figures present the variability of F-measure differences (Fig. 3) and AUC differences (Fig. 4) for particular datasets and methods. Horizontal lines on the graphs show median value for each method. The largest differences between mean values and two moments of preprocessing have been noticed for glass2 (precision: 0.42; recall: 0.26; F-measure: 0.36; AUC: 0.12), glass4 (precision: 0.30; recall: 0.21; F-measure: 0.27; AUC: 0.11) and haberman (precision: 0.33; F-measure: 0.23; AUC: 0.07). The quantities of the difference are astounding and further investigation will be performed. Inappropriate moment of data preprocessing while using cross-validation techniques, regardless of the classification method, may have large impact on the results giving too optimistic result of the classification process.

Conclusions

Class imbalance datasets is nowadays a common occurrence, mainly due to the possibility of collecting large amounts of information. This phenomenon may Assuming the equality of misclassification errors, the classifiers are usually overwhelmed by negative class objects, which leads to degradation of the performance of the classifier. Data preprocessing can be a good approach overcoming the disparity between classes cardinalities. However, the calculations should be performed in an attentive matter to not obtain excessively positive results. Even if the results are overestimated for about a few percent, each incorrect decision should be avoided.

There is a significant influence of the moment choice when preprocessing is performed. Results differences vary depending on a chosen classification algorithm and specific dataset. In most cases rates are inflated if preprocessing is performed before cross-validation. There are two reasons of this issue. Firstly, synthetic objects that are put into test sets are closely related to their prototypes in training sets, causing overfitting of a model. Secondly, proportions of classes in test sets in this method are not the same as real proportions that were given in the input sets and it affects the values of calculated rates.

The results occurred astounding and further investigation for various classification methods and datasets will be performed.

Fig. 1 :

 1 Fig. 1: Incorrect cross-validation process

Fig. 2 :

 2 Fig. 2: Correct cross-validation process

Fig. 3 :Fig. 4 :

 34 Fig. 3: Variability of F measures differences

Table 1 :

 1 Characteristics of the datasets

	dataset	#objects #attributes #minority	IR
	ecoli-0vs1	220	7	77	1.86
	ecoli1	336	7	77	3.36
	ecoli2	336	7	52	5.46
	ecoli3	336	7	35	8.60
	ecoli4	336	7	20	15.80
	glass*	214	9	51	3.20
	glass0	214	9	70	2.06
	glass1	214	9	76	1.82
	glass2	214	9	17	11.59
	glass4	214	9	13	15.46
	glass5	214	9	9	22.78
	glass 6	214	9	29	6.38
	haberman	306	3	81	2.78
	iris0	150	4	50	2.00
	new-thyroid1	215	5	35	5.14
	new-thyroid2	215	5	35	5.14
	pima	768	8	268	1.87
	vehicle0	846	18	199	3.25
	vehicle1	846	18	217	2.90
	vehicle2	846	18	218	2.88
	vehicle3	846	18	212	2.99
	vowel0	988	13	90	9.98
	wisconsin	683	9	239	1.86
	yeast1	1484	8	429	2.46
	yeast3	1484	8	163	8.10

Table 2 :

 2 Results for precision, recall, F measure and AUC using three preprocessing methods and their modifications for two classification algorithms

			Precision
			C4.5		SVM
	method	M e	Range	p M e	Range	p
	slsmote	0.1826 0.0000; 0.6311 <0.0001 0.2439 0.0000; 0.5825 <0.0001
	smote100	0.0685 0.0065; 0.1986 <0.0001 0.1050 0.0000; 0.2023 <0.0001
	smote200	0.1637 0.0000; 0.3183 <0.0001 0.1826 0.0000; 0.3125 <0.0001
	smote300	0.1866 0.0000; 0.3880 <0.0001 0.2345 0.0000; 0.3671 <0.0001
	smote400	0.2184 0.0000; 0.4446 <0.0001 0.2631 0.0000; 0.4154 <0.0001
	smote500	0.2297 0.0000; 0.4527 <0.0001 0.2796 0.0000; 0.4747 <0.0001
	smoteAuto	0.2043 0.0000; 0.5665 <0.0001 0.2092 0.0000; 0.5835 <0.0001
	spider-strong 0.1866 -0.0011; 0.5403 <0.0001 0.1367 0.0000 ;0.4031 <0.0001
	spider-weak	0.1290 0.0000; 0.4388 <0.0001 0.1268 -0.0135; 0.3277 <0.0001
	spider-weak-rel 0.1169 0.0000; 0.4445 <0.0001 0.1263 -0.0135; 0.3078 <0.0001
			Recall
	method	M e	Range	p M e	Range	p
	slsmote	0.1271 0.0128; 0.6533 <0.0001 0.0452 0.0000; 0.2945 <0.0001
	smote100	0.0709 -0.0277; 0.2647 <0.0001 0.0097 -0.0296; 0.0944 0.0001
	smote200	0.0843 0.0064; 0.2294 <0.0001 0.0318 -0.0036; 0.2153 <0.0001
	smote300	0.0858 0.0000; 0.2955 <0.0001 0.0293 0.0000; 0.2307 <0.0001
	smote400	0.1000 -0.0022; 0.3458 <0.0001 0.0242 -0.0007; 0.2138 <0.0001
	smote500	0.0971 0.0111; 0.3117 <0.0001 0.0273 0.0000; 0.1910 <0.0001
	smoteAuto	0.0896 -0.0020; 0.4203 <0.0001 0.0236 -0.0050; 0.1330 <0.0001
	spider-strong 0.1222 0.0009; 0.5724 <0.0001 0.0010 -0.2037; 0.2171	0.587
	spider-weak	0.1002 0.0000; 0.5204 <0.0001 -0.0108 -0.1910; 0.2185	0.129
	spider-weak-rel 0.0932 0.0000; 0.4998 <0.0001 -0.0229 -0.1802; 0.1800	0.048
			F Measure
	method	M e	Range	p M e	Range	p
	slsmote	0.1618 0.0066; 0.6437 <0.0001 0.1561 0.0000; 0.5205 <0.0001
	smote100	0.0852 0.0066; 0.2576 <0.0001 0.0761 0.0000; 0.1472 <0.0001
	smote200	0.1254 0.0088; 0.2703 <0.0001 0.1070 0.0000; 0.2714 <0.0001
	smote300	0.1496 0.0094; 0.3492 <0.0001 0.1508 0.0000; 0.2951 <0.0001
	smote400	0.1641 0.0097; 0.4080 <0.0001 0.1773 0.0000; 0.3658 <0.0001
	smote500	0.1654 0.0104; 0.3937 <0.0001 0.1907 0.0000; 0.3934 <0.0001
	smoteAuto	0.1440 0.0059; 0.5113 <0.0001 0.1422 0.0000; 0.4893 <0.0001
	spider-strong 0.1495 0.0004; 0.5578 <0.0001 0.1022 -0.0657; 0.2886 <0.0001
	spider-weak	0.1169 0.0004; 0.4786 <0.0001 0.0587 -0.0455; 0.2317 0.0004
	spider-weak-rel 0.1181 0.0004; 0.4731 <0.0001 0.0841 -0.0261; 0.2125 <0.0001
			AUC
	method	M e	Range	p M e	Range	p
	slsmote	0.0684 0.0065; 0.1986 <0.0001 0.0215 0.0000; 0.1475 <0.0001
	smote100	0.0341 0.0003; 0.0993 <0.0001 0.0053 -0.0081; 0.0462 <0.0001
	smote200	0.0451 0.0006; 0.1152 <0.0001 0.0164 0.0000; 0.1054 <0.0001
	smote300	0.0516 -0.0006; 0.1418 <0.0001 0.0126 0.0000; 0.1089 <0.0001
	smote400	0.0516 -0.0001; 0.1461 <0.0001 0.0112 -0.0010; 0.1069 <0.0001
	smote500	0.0457 0.0018; 0.1542 <0.0001 0.0109 -0.0004; 0.0972 <0.0001
	smoteAuto	0.0450 -0.0011; 0.1994 <0.0001 0.0111 -0.0017; 0.0779 <0.0001
	spider-strong 0.0757 0.0004; 0.2834 <0.0001 0.0076 -0.0921; 0.1122	0.063
	spider-weak	0.0639 0.0004; 0.2552 <0.0001 0.0051 -0.0866; 0.1122	0.440
	spider-weak-rel 0.0621 0.0004; 0.2613 <0.0001 0.0068 -0.0818; 0.0937	0.303

Acknowledgements

This work was performed in the framework of the grant S/WI/2/2013 (Bialystok University of Technology), founded by the Polish Ministry of Science and Higher Education.


Maciej Brzozowski
email: m.brzozowski@pb.edu.pl

Andrzej Chmielewski
email: a.chmielewski@pb.edu.pl

Embedding the V -Detector algorithm in FPGA

Keywords: artificial immune system, anomaly detection, FPGA

The b-v model is a hybrid immune-based approach for detecting anomalies in high-dimensional datasets. It is based on a negative selection algorithm and utilizes both types of detectors to achieve better results in comparison to single detection models. Also, it is an interesting alternative to well known traditional, statistical approaches, because only positive (self ) examples are required at the learning stage. As a result, it is able to detect even unnkown or never met anomalies and this fact is one of the most attractive features of this approach. However, especially in the case of on-line classification, not only high accuracy but also high efficiency is needed. Thus, we propose to embed some complex tasks in a reprogrammable FPGA to offload CPU and speed up the classification process. This paper presents a hardware implementation of the V -Detector algorithm, which is the most complex and time consuming part of b-v model.

Introduction

An efficiency of Natural Immune System (NIS) is unsurpassed for all protection systems and verified over millions of years by living organisms. It is a very complex system focused on discrimination between own cells (called self ) and pathogens (called nonself ), which should be detected and eliminated. A nice feature of NIS is that it does not need any example of nonself samples to detect them as only the information about its own cells is sufficient. Hence, every organism has a unique "protection system", capable of detecting even a new type of attack and tolerates only own cells which form its body.

This dedicated and highly efficient protection system against various types of pathogens was an inspiration for developing Artificial Immune Systems (AIS). Within this domain, many types of algorithms were proposed, mainly focused on computer system security solutions. However, the most popular is Negative Selection Algorithm (NSA) [START_REF] Forrest | A sense of Self for Unix Processes[END_REF] with the ability of detecting novel, never met samples, a counterpart of pathogens. Based on deep investigations with various types of large and high-dimensional datasets, a solution called the b-v model [START_REF] Chmielewski | Hybrid negative selection approach for anomaly detection[END_REF] was proposed. It minimizes the problem of scalability, by involving both types of receptors: b-and v -detectors. This hybrid approach, presented by conducting numerous experiments, provides much better results in comparison to single detection models as well as traditional, statistical approaches, even though only positive (self ) examples are required at the learning stage. It makes this approach an interesting alternative for well known classification algorithms, like SVM, knearest neighbours, etc. The b-v model is briefly described in Subsection 2.3.

However, there are lots of domains where not only high accuracy is crucial. In some cases, very high efficiency is also required to examine all samples in a short time. On-line classification systems like firewalls, intruder detection and prevention systems, etc. are examples of applications which usually operate on huge amounts of data and over-lengthy delays, related with data processing, are unacceptable.

Thus, every way to increase the speed of detection process is highly desirable. One of them is embedding algorithms in a reprogrammable FPGA (Field Programmable Gate Array). Our preliminary results [START_REF] Brzozowski | Hardware Approach for Generating b-detectors by Immune-Based Algorithms[END_REF] conducted using b-detectors, have shown while generating them as well as during censoring samples, which are the most complex operations, can be parallelized and additionally computed without CPU utilization. As a result, censoring of millions samples took only a few ticks of the clock (a few nanoseconds).

In this paper we present our approach to embedding the V -Detector algorithm in FPGA as being a very important part of b-v model. All samples not recognized by very fast b-detectors are passed to V -Detector which is responsible for the final decision: censored sample is self or nonself. It operates on real-valued detectors (called v -detectors), in contrast to fast b-detectors represented as a binary string. Hence, this step is the most complex and time consuming in the whole process of detecting anomalies, especially in the case of high-dimensional datasets. Hardware implementation of this algorithm should significantly increase its efficiency.

Negative Selection

The NSA, proposed by Forrest et al., [START_REF] Forrest | Self-nonself discrimination in a computer[END_REF], is inspired by the process of thymocytes (i.e. young T-lymphocytes) maturation: only those lymphocytes survive which do not recognize any self molecules.

Formally, let U be a universe, i.e. the set of all possible molecules. The subset S of U represents the collection of all self molecules and its complement N in U represents all nonself molecules. Let D ⊂ U stand for a set of detectors and let match(d, u) be a function (or a procedure) specifying if a detector d ∈ D recognizes the molecule u ∈ U. Usually, match(d, u) is modelled by a distance metric or a similarity measure, i.e. we say that match(d, u) = true only if dist(d, u) ≤ δ, where dist is a distance and δ is a pre-specified threshold. Various matching function are discussed e.g. in [START_REF] Harmer | Artificial immune system architecture for computer security applications[END_REF] and [START_REF] Dasgupta | Revisiting negative selection algorithms[END_REF].

The problem relies upon construction the set D in such a way that

match(d, u) = false if u ∈ S true if u ∈ N (1)
for any detector d ∈ D.

A naive solution to this problem, implied by the biological mechanism of negative selection, consists of five steps: A perfect NSA should cover whole N space by sets of detectors to detect all nonself samples. However, as shown by numerous experiments, scalability is a key issue here, regardless of the representation of samples used [12][6]. This problem is also discussed in this article.

Detectors and algorithms

Generally, there are two type of receptors used:

b-detectors -represented as binary string (Hamming space), v -detectors -represented as real-valued vectors.

For each of them, many algorithms with different matching rules were proposed. For binary representation, the most popular were presented in [START_REF] Forrest | A sense of Self for Unix Processes[END_REF] and [START_REF] Balthrop | Coverage and generalization in an artificial immune system[END_REF]. In the case of real-valued vectors, V -Detector algorithm [START_REF] Dasgupta | Real-valued negative selection algorithm with variable-sized detectors[END_REF] is the most known. Hardware implementation of this algorithm, described in details in Subsection 2.2, is the main subject of this article.

Because, neither b-nor v -detectors were not capable to detect anomalies to a satisfactory degree, a b-v model here was proposed [START_REF] Chmielewski | Hybrid negative selection approach for anomaly detection[END_REF] (see Subsection 2.3), which used both types of detectors to overcome the problem with scalability. As shown in the performed experiments, it provides much better results in comparison to single detection models as well as in comparison to traditional, statistical approaches, even though only positive self examples are required at the learning stage.

Real-valued representation

To overcome scaling problems inherent in Hamming space, Ji and Dasgupta proposed a real-valued NSA, termed V -Detector [START_REF] Dasgupta | Real-valued negative selection algorithm with variable-sized detectors[END_REF].

It operates on normalized vectors of real-valued attributes; each vector can be viewed as a point in the d-dimensional unit hypercube, U = [0, 1] d . Each self sample, s i ∈ S, is represented as a hypersphere s i = (c i , r s ), i = 1, . . . , l, where l is the number of self samples, c i ∈ U is the center of s i and r s is its radius. It is assumed that r s is identical for all s i 's. Each point u ∈ U inside any self hypersphere s i is considered as a self element.

The detectors d j are represented as hyperspheres also: d j = (c j , r j ), j = 1, . . . , p where p is the number of detectors. In contrast to self elements, the radius r j is not fixed but it is computed as the Euclidean distance from a randomly chosen center c j to the nearest self element (this distance must be greater than r s , otherwise the detector is not created). Formally, we define r j as

r j = min 1≤i≤l dist(c j , c i ) -r s . (2)
The algorithm terminates if a predefined number p max of detectors is generated or the space U\S is sufficiently well covered by these detectors; the degree of coverage is measured by the parameter co -see [START_REF] Dasgupta | Real-valued negative selection algorithm with variable-sized detectors[END_REF] for the algorithm and its parameters description.

In its original version, the V -Detector algorithm employs Euclidean distance to measure proximity between a pair of samples. Therefore, self samples and the detectors are hyperspheres (see Figure 1(a)). Formally, Euclidean distance is a special case of Minkowski norm L m , where m ≥ 1, which is defined as:

L m (x, y) = d i=1 |x i -y i | m 1 m , (3)
where x = (x 1 , x 2 , . . . , x d ) and y = (y 1 , y 2 , . . . , y d ) are points in d . Particularly, L 2 -norm is Euclidean distance, L 1 -norm is Manhattan distance, and L ∞ is Tchebyshev distance. However, Aggarwal et al. [START_REF] Aggarwal | On the surprising behavior of distance metrics in high dimensional space[END_REF] observed that L m -norm loses its discrimination abilities when the dimension d and the values of m increase. Thus, for example, Euclidean distance has the best (among L m -norms) metrics when d ≤ 5. For higher dimensions, the metrics with lower m (i.e. Manhattan distance) should be used.

Based on this observation, Aggarwal introduced fractional distance metrics with 0 < m < 1, arguing that such a choice is more appropriate for highdimensional spaces. Experiments, reported in [START_REF] Chmielewski | On the distance norms for multidimensional dataset in the case of real-valued negative selection application[END_REF], partially confirmed the effi-Fig. 2: Flow diagram of the classification process for b-v model. ciency of this proposition. For 0.5 < m < 1, more samples were detected, in comparison to L 1 and L 2 norms. However, for m < 0.5 the efficiency rapidly decreased and for m = 0.2, none samples were detected. Moreover, these experiments also confirmed a trade-off between efficiency, time complexity and m. For fractional norms, the algorithm runs slower for lower m values; for L 0.5 the learning phase was even 2-3 times longer than for L 2 .

Another consequence of applying fractional metrics for V -Detector algorithm is modification of the shape of detectors. Figure 1(b) presents the unit spheres for selected L m -norms in 2D with m = 2 (outer most), 1, 0.7, 0.5, 0.3 (inner most).

Brief description of the b-v model

The b-v model [START_REF] Chmielewski | Hybrid negative selection approach for anomaly detection[END_REF] is the only NSA, involving both types of detectors, namely band v -detectors. It was designed for anomaly detection in high-dimensional data, which are difficult to analyze due to the lack of appropriate similarity metrics which enable the covering of space N in sufficient degree and reasonable time. One of the important features of the b-v model is its ability to minimize the overlapping regions between sets of detectors. We do not expect that b-detectors cover the space N in sufficient degree, as it can consume too much time. On the other hand, fewer numbers of v -detectors should be generated because some part of space N is already covered by b-detectors. The main idea of this algorithm is depicted in Figure 2.

Here, the b-detectors, as those providing fast detection, are used for preliminary filtering of samples. The samples which did not activate any of the b-detectors are censored by v -detectors next. As a result the overall duration of classification could be significantly reduced as fewer v -detectors were needed to cover space N . Hence, this model is more efficient for on-line classification systems in comparison to standard negative selection approaches which are based only on one type of detectors.

Embedding the V -Detector algorithm in FPGA (see Section 3) should significantly affect the efficiency of the entire b-v model. This also opens the possibility of applying them in other domains, including devices used in the Internet of Things technology.

3 Hardware approach to V -Detector algorithm

As was already mentioned, classification with the V -Detector algorithm is a very complex and time consuming process because of its high complexity of performed calculations that need to be done on real-valued vectors. Time of classification of a single sample directly depends on its dimensionality ( d ) and number of detectors, because for each single sample, there is a need to calculate distance to generated detectors from set D. The described process, of course, might be divided into sub tasks to parallelize classification. As a result, the duration of this process should be significantly decreased. However, when calculations are performed on CPUs or GPUs processors, its efficiency is strictly restricted by number of processors and numbers of its cores.

One of the solutions, corresponding to the above restrictions, are programmable devices, especially Field Programmable Gate Array (FPGA) devices, providing a high performance, low power consumption and relatively low price in comparison to CPU/FPU solutions. FPGA is mainly designed to parallelize computational tasks. Therefore, it might be used in projects where the main indicator is performance. Designers equipped FPGA devices in specialized IP (Intellectual Property) blocks like multipliers, pre-adders and accumulators for increasing the number of computations per second and other more complicated blocks like embedded CPUs, DSP, Ethernet Physical Interfaces, PCI Express, DRAM controllers and many others. Moreover, some FPGA devices allow for the partial reconfiguration (reprogramming) during its operation -helping the system to adopt to rapidly a changing environment.

FPGA devices are characterized by high computing power, flexibility and scalability. They can be adapted as a base for on-line classification systems eg. firewalls and intruder detection systems for home use as well as for enterprise solutions.

As was presented in [START_REF] Brzozowski | Hardware Approach for Generating b-detectors by Immune-Based Algorithms[END_REF], b-detectors were successfully implemented in reprogrammable architectures, especially in FPGA devices. Hence, it is natural to try to do the same for the V -Detector algorithm, where we could expect more spectacular results in comparison to a software approach, which was a bottleneck in the b-v model. Classification algorithm will be explained in further sections but firstly we must present how the distance between detectors and samples is calculated. The main difference, in comparison to software implementation, is the usage of hypercubes, instead of hyperspheres. Such a shape is more suitable for reprogrammable architecture.

Each self sample, s i ∈ S, is represented as a hypercube s i = (c i , l s ), i = 1, . . . , l, where l is the number of self samples, c i ∈ U is the center of s i and l s is half of the length of its side (edge). It is assumed, that l s is identical for all self samples. Similar to software approach, each hypercube u ∈ U inside any self hypercube s i is considered as a self element.

The detectors d j are represented as hypercubes also: d j = (c j , l j ), j = 1, . . . , p where p is the number of detectors. In contrast to self elements, the half length of its side l j is not fixed, but it is computed as the distance from a randomly chosen center c j to the nearest self element (this distance must be greater than l s , otherwise detector is not created).

Formally, we define l j as:

l j = min 1≤i≤l dist(c j , c i ) -l s , (4)
where distance between two centers of hypercubes x and y is defined as:

dist(x, y) = min 1≤i≤d |x i -y i |. ( 5
)
Each hypercube is axis-aligned. It means, rotation of hypercube is not allowed. Two hypercubes are not overlapping when: In Figure 3(c): [START_REF] Chmielewski | Hybrid negative selection approach for anomaly detection[END_REF][START_REF] Forrest | A sense of Self for Unix Processes[END_REF], 0), d 3 = ([5, 5, 0], 0) and d 4 = ( [START_REF] Chmielewski | On the distance norms for multidimensional dataset in the case of real-valued negative selection application[END_REF][START_REF] Chmielewski | On the distance norms for multidimensional dataset in the case of real-valued negative selection application[END_REF][START_REF] Chmielewski | On the distance norms for multidimensional dataset in the case of real-valued negative selection application[END_REF], 1) are examples in three dimensional space. In V -Detector classification process it is sufficient to state that sample overlap with one of the detectors. There is no need to state that detector includes the sample (sample overlaps a whole over the detector or overlaps its partially). In both cases, the sample should be rejected.

min 1≤i≤d |x i -y i | > l x + l y . (6)
d 1 = ([1, 1, 1], 0), d 2 = ([0,

Emebedded V -Detector -the fastest approach

The first of the proposed solutions, denoted as V -Detector-HF ast, for reprogrammable architectures holds the entire D in target device resources. As a result, it should maximize the speed of classification process for V -Detector algorithm. The base concept allows the determination of distance between the single sample and the entire set of D in one cycle of the designed system. Moreover, the classification process does not depend to such an extent on the number of dimensions as in the classical approach. Here, the universe set U is represented by bitmap with detectors modeled as hypercubes. The number of distinguish samples (represented as vectors) depends on the size of used internal memory.

. . . Memory and other arithmetic operations are mapped into logic elements available on the reprogrammable device, in our case FPGA. For each dimension, a decoding vector responsible for choosing data from set D is created, depending on the sample's coordinates. For each coordinate logical products are created of decoding vectors (for all dimensions) and its corresponding memory values. In the last step, the number of '1' in the logical product is counted. If this value is not equal to 0, it means, sample overlaps at least one detector. Figure 4 shows a simplified diagram of V -Detector (for one dimension) based on internal FPGA memory.

The proposed solutions for reprogrammable architectures is incredibly fast in classification of both single and group of samples. This approach, apart from the high-speed classification, also has some disadvantages. Set D is held in FPGA internal RAM (very limited capacity) or is mapped in the logical area on the device. In this case, a synthesized classification algorithm is highly demanded for device logic resources. Therefore, we are limited by logic element numbers on the target programmable device, in which one, design has to be mapped. In this case we have to choose a target device with appropriate logic elements overhead. The lack of adequate number of logical resources may lead to a decrease in the number of analyzed dimensions, or enforces the reduction of the resolution of the analyzed samples.

Embedded V -Detector -approach based on external memory

The presented classification solution, denoted as V -Detector-HRAM , is based only on the resources provided by the target device, is characterized by constraints on the system resolution. One of the methods to increase the resolution of the system is to move the set of detectors from the internal device resources to external memory. In this case, part of the available resources has to be destined to calculate the read/write memory cell addresses. The designed component informs which memory lines are needed in the calcification process of each sample and chooses only the appropriate cells from them. The proposed solution is slowed down by time needed by external memory to perform write and read operations compared to the approach presented in Subsection 3.1. When the system is properly scaled to expected samples (in numbers of dimensions and numbers of bits per dimension) i.e. l s = 0 (is small as possible) classification process should need only one read operation from external memory.

For DE2-115 Development Board we were able to achieve a resolution of 2 30 distinguishable samples.

Hardware V -Detector approaches evaluation

In the proposed solutions, the learning phase is simplified, in comparison to software implementation. The optimization process of D set is not needed because its size does not affect the duration of classification of a single sample. Bitmap hypercube representation of U is constant and therefore the number of detectors has no impact on its size. Classification time is shorter because the designed components consider calculations only in the nearest surroundings of the sample. All the necessary calculations are performed at the level of the FPGA. Therefore, the designed component may process large amounts of data in a single period of time.

Both presented solutions were implemented and synthesized for Altera Cyclone IVE EP4CE115F29C7 device equipped on the DE2-115 Development and Education Board by using Quartus II 15.0. Figure 5(a) shows simplified diagrams of the actual designs. The core of the solution is Nios II processor with connected components via an Avalon bus. In the first stage, components were tested as operated independently. In the second stage, components were integrated into the system (Figure 5(a)). In the future, both systems, V -Detector based on internal and on external RAM cells, will be equipped with two Ethernet interfaces 10/100/1000 and tested in a network environment (Figure 5(b)).

Another possibility of the further development is integrated design with PCI Express and use also of the desktop computer resources.

To measure performance (profiling) of the designed systems we used Altera Megacore Performance Counter Unit. The designed system was based on Nios II worked with 100MHz frequency.

As was already mentioned in Subsection 3.1, the dimensionality of samples which can be processed by V -Detector-HF ast algorithm is highly restricted by resources availability in target devices. In the case of Altera Cyclone IVE EP4CE115F29C7, which was used in our experiments, internal memory capacity is limited to 3888kb. Such a restriction forced us to select a rather small dataset for testing. We chose the most popular dataset used for classification purposes, namely Iris, which consists of only 150 samples. Each of 4 attributes was represented by integer value from the range 0-3 (2 bits). Detectors were generated, assuming that one class of thew iris plant is regarded as set S during the learning stage. In all cases, samples were successfully classified. The main advantage of the hardware approaches was the duration of classification, and was presented in Table 1.

We can compare those values with the average time of classification achieved for software implementation executed on a PC equipped with Intel i7-3770 processor (8 cores) 3.4GHz with 16GB RAM. In this case, process censoring all samples took about 3 ms. It is about 20 times slower than V -Detector-HF ast, and about 6 times slower than V -Detector-HRAM . Taking into consideration that the frequency of the CPU on the PC computer was 340 times higher, it can be easily computed how fast the hardware approach is. Table 1 contains also the results of other classification experiments with the same dataset. Here, samples were represented as 4 dimension vectors with 6 bits per dimension. For V -Detector-HF ast this design was too big to map into available architecture. Thus experiments were conducted only for the V -Detector-HRAM algorithm for which the classification process took 0.58 ms (the same time as in first experiment). Here, classification strictly depends on access time to external memory (read/write data operation). It is clear that all operations performed on internal resources are faster than on external memory. The increase in the number of dimensions does not significantly affect the time of classification. The most important is a properly scaled system (sample size).

However, the most spectacular results were obtained for some subsets of KDD Cup 1999 from UCI Machine Learning Repository. This database was too big for the current implementation of V -Detector-HRAM . Hence, only the samples of the ICMP protocol were used for tests with randomly selected 7 of 41 attributes (each coded on 4 bits). In this way, our test set contains 1074994 unique samples and an average of 683 detectors were used. During the tests we could observe, the duration of classification was more than 2000 times faster in the case of hardware implementation (see Table 2).

Conclusions

In this paper we present our approach to hardware implementation of the V -Detector algorithm, which is the most computationally complex part of b-v model. Our preliminary promising results with b-detectors was a first step for building a very fast classification system embedded in reprogrammable devices. To achieve this goal, we had to implement also the V -Detector algorithm, which operates on computationally complex real-valued vectors.

Here, we presented two different possible approaches, called V -Detector-HF ast and V -Detector-HRAM . Both of them have some disadvantages, which are mainly related with the limitation of used memory. However, V -Detector-HRAM can be extended to be used with external memory, which can make this approach possible to be applied for much bigger datasets than those used in the experiments described in this paper.

The performed experiments confirmed that hardware implementations can significantly speed up the classification process, which usually is the most crucial in classification systems. Obtained preliminary results are a good starting point to build a hardware version of the b-v -model, dedicated for an on-line immunebased intrusion detection system.

  (a) Initialize D as empty set, D = ∅. (b) Generate randomly a detector d. (c) If math(d, s) = false for all s ∈ S, add d to the set D. (d) Repeat steps (b) and (c) until the sufficient number of detectors will be generated.

Fig. 1 :

 1 Fig. 1: (a) Example of performance V -Detector algorithm for 2-dimensional problem. Black and grey circles denotes self samples and v -detectors, respectively. (b) Unit spheres for selected L m norms in 2D.

Fig. 3 :

 3 Fig. 3: Example of axis-aligned v -detector hypercube in d .

Figure 3

 3 Figure 3 presents d-dimensional hypercubes. In Figure 3(b) two detectors d 1 = ([0], 1), d 2 = ([5], 1) in one dimensional space are marked (grey colour). In Figure 3(a) two detectors d 1 = ([1, 3], 1) and d 2 = ([3, 5], 1) are overlapping.

Fig. 4 :

 4 Fig. 4: V -Detector -the fastest approach for reprogrammable architectures.

Fig. 5 :

 5 Fig. 5: System diagrams for FPGA device.

Table 1 :

 1 Comparison of average duration of classification process for V -Detector-HF ast and V -Detector-HRAM algorithms for different number of bits per dimension (n) for Iris dataset.

			HF ast		HRAM
			n = 2		n = 2		n = 6
		time[ms] time (clock) time[ms] time (clock) time[ms] time (clock)
	Iris-setosa	0.18	17914	0.58	58181	0.58	58181
	Iris-versicolor 0.18	17914	0.58	58061	0.58	58061
	Iris-virginica	0.18	17914	0.58	58038	0.58	58038

Table 2 :

 2 Comparison of average duration of classification process for software implementation and V -Detector-HRAM algorithm applied to randomly selected subsets for KDD Cup 1999 dataset.

	Sof tware		HRAM
	time[ms] time[ms] time (clock)
	106 000	45	4483698

Acknowledgment

This research was partially supported by the grants S/WI/3/13 and MB/WI/1/2014 of the Polish Ministry of Science and Higher Education.