Ryszard Kozera
email: r.kozera@mini.pw.edu.pl

Jacek Tchórzewski
email: tchorzewski.jacek@gmail.com

Outlier Removal in 2D Leap Frog Algorithm

Keywords: Shape from Shading, noise removal, optimization, outliers

In this paper a 2D Leap Frog Algorithm is applied to solve the so-called noisy Photometric Stereo problem. In 3-source Photometric Stereo (noiseless or noisy) an ideal unknown Lambertian surface is illuminated from distant light-source directions (their directions are assumed to be linearly independent). The subsequent goal, given three images is to reconstruct the illuminated object's shape. Ultimately, in the presence of noise, this problem leads to a highly non-linear optimization task with the corresponding cost function having a large number of independent variables. One method to solve it is 2D Leap Frog Algorithm. During reconstruction, problem that commonly arises, renders the outliers generated in the retrieved shape. In this paper we implement 2D Leap Frog. In particular we focus on choosing snapshot size and on invoking two algorithms that can remove outliers from reconstructed shape. Performance of extended 2D Leap Frog is illustrated by examples chosen especially to demonstrate how this solution is applicable in computer vision. Remarkably, this optimization scheme can also be used for an arbitrary optimization problem depending on large number of variables.

Introduction

One of the most important problems in the field of computer vision is an issue of shape reconstruction from its image(s) data. There are two main approaches to tackle this problem. One method (discussed in this article) is based on surface S reconstruction from the data obtained from its image(s) created by single camera (the so-called Shape from Shading [START_REF] Horn | Shape from Shading[END_REF]). The second class of techniques is the shape reconstruction based on multiple camera input data and the usage of triangulation like methods [START_REF] Maruya | Texture based 3D shape reconstruction from multiple stereo images[END_REF]. In the first method single illumination yields the so-called single image Shape-from-Shading problem. On the other hand a multiple illumination in Shape from Shading is called Photometric Stereo (see e.g. Horn [START_REF] Horn | Robot Vision[END_REF], Kozera [START_REF] Kozera | Existence and uniqueness in photometric stereo[END_REF] and Noakes and Kozera [START_REF] Noakes | Nonlinearities and noise reduction in 3-Source Photometric Stereo[END_REF]). As opposed to the ideal continuous setting in Shape from Shading (see e.g. [START_REF] Horn | Shape from Shading[END_REF]) an additional problem arises when noise is added to the image(s). This forms noisy Photometric Stereo problem (or noisy single image Shape from Shading problem, respectively). As it turns out it is modeled by the corresponding highly non-linear optimization task in many multiple variables. One of the computational techniques striving to deal with such optimization is a 2D Leap Frog Algorithm [START_REF] Noakes | A 2D Leap Frog algorithm for optimal surface reconstruction[END_REF] and [START_REF] Noakes | Nonlinearities and noise reduction in 3-Source Photometric Stereo[END_REF], that is recalled and modified in this paper. While dealing with classical Shape from Shading, one seeks a function u : Ω ⊆ IR 2 → IR, that represents distance of surface point (x, y, u(x, y)) ∈ graph(u) = S from a camera (where Ω is a picture within the camera). For a Lambertian surface (which is a perfect diffuser) with a constant albedo, illuminated from distant light-source direction p = (p 1 , p 2 , p 3 ) the image irradiance equation in the continuous setting is given over Ω as (see Horn [START_REF] Horn | Robot Vision[END_REF]):

E p (x, y) = p 1 u x (x, y) + p 2 u y (x, y) -p 3 p 2 1 + p 2 2 + p 2 3 u 2 x (x, y) + u 2 y (x, y) + 1 . (1)
For the remaining two light-source directions q = (q 1 , q 2 , q 3 ) and r = (r 1 , r 2 , r 3 ), similar image irradiance equations can be derived. Note that we urge det(p, q, r) = 0 (i.e. light-source directions are to be linearly independent). In the case of discrete model (e.g. with noise added) a pertinent function is to be minimized, later called a cost function E. It is derived from the physical concepts of Photometric Stereo and from the properties of a Lambertian surface.

In real case our Ω is not continuous but discrete as it addresses the image(s) represented by a collection of pixels. Assume that the number of all image pixels is n 2 . The general formula for such cost function (by ( 1)) reads (see Noakes and Kozera [START_REF] Noakes | Nonlinearities and noise reduction in 3-Source Photometric Stereo[END_REF]):

E (u) = n-1 i,j=2 E i,j (u) , (2)
where u ∈ IR n 2 -4 and (i; j)-pixel energy value E i,j = E p i,j + E r i,j + E q i,j with:

E p i,j (u) =     p 1 ui+1,j -ui-1,j 2∆x + p 2 ui,j+1-ui,j-1 2∆y -p 3 p ui+1,j -ui-1,j 2∆x 2 + ui,j+1-ui,j-1 2∆y 2 + 1 -E p (x i , y j )     2 , (3)
where p = p 2 1 + p 2 2 + p 2 3 , and E r i,j and E q i,j are defined similarly to [START_REF] Horn | Robot Vision[END_REF]. Note that (3) is a discretized version of image irradiance equation (1) at internal image pixel point (i, j) upon using central difference derivative approximations:

u x (i, j) ≈ u i+1,j -u i-1,j 2∆x
and u y (x, y) is estimated similarly. We look for discrete u which minimizes [START_REF] Chauvenet | A Manual of Spherical and Practical Astronomy[END_REF]. At this moment it is clearly visible that there exists strong nonlinearity in formula [START_REF] Chauvenet | A Manual of Spherical and Practical Astronomy[END_REF]. The cost function E depends on n 2 -4 variables (image corners do not participate in reconstruction) which represents almost entire image resolution (in practice a very big number). Thus the problem (2) usually forms an optimization task depending on a very large number of variables. Using here Newton's method based on inversion D 2 E over entire Ω is a huge computational task.

2D Leap Frog Algorithm

The main idea standing behind the 2D Leap Frog Algorithm is to find the suboptimal minima of a function E (see [START_REF] Chauvenet | A Manual of Spherical and Practical Astronomy[END_REF]) by accumulating the results of the so-called local area optimizers. It is worth mentioning the difference between the terms local area minimum versus local minimum of E. The difference is that the local area minimum is a suboptimal minimum for a cost function E considered with the values u of over pixels taken from some local area Ω loc ⊆ Ω. On the other hand the local minimum of E is any sub-optimal solution to (2) over entire image Ω. Note that, according to formula (1) a visible part of the Lambertian surface corresponds to the case, where 0 ≤ cos Θ ≤ 1, whereas the invisible one results when -1 ≤ cos Θ < 0 (where Θ denotes the angle between the lightsource direction and the surface normal at point (x, y, u(x, y))). In both cases, however the image irradiance equations can still be mathematically posed and solved (this also reffers to (2)). Hence the corresponding optimization problem (2) can be tackled at least theoretically over entire Ω, which is rectangular (camera sensor). Thus for simplicity we assume and solve the optimization problem (2) under the constraint that the data over entire rectangular image are accessible. Let us denote an image space Ω = [0, 1] × [0, 1] with given (k; l) ∈ IN as length and height in pixels. The space Ω is now divided into atomic subspaces, described as follows:

S l iqjq = i q -1 2 l , i q 2 l × j q -1 2 l , j q 2 l , for 1 ≤ i q , j q ≤ 2 l .
The main part of the 2D Leap Frog Algorithm works only on these rectangular subspaces, that are each denoted by SQ lm ij , where i and j are the row and column indices, and l and m are the width and height of the subspace. Assume now that u k1 1 , . . . , u k1 s represents some free variables of E and the remaining u k2 1 , . . . , u k2 t are temporarily frozen (where s, t ∈ IN). Then our global energy E can be split into two components:

E (u) = E 1 u k1 1 , . . . , u k1 s + E 2 u k2 1 , . . . , u k2 t . (4)
Evidently minimizing E 1 over variables u k1 1 , . . . , u k1 s only, does not change the value of E 2 and therefore the whole value of E is also decreased. If s is small then optimizing E 1 becomes a computationally feasible task (e.g. for Newton's method). This is the main idea standing behind the 2D Leap Frog. Optimizing E 1 in our case corresponds to the optimization of E over each SQ lm ij with all other values of u frozen. As shown by Noakes and Kozera [START_REF] Noakes | Nonlinearities and noise reduction in 3-Source Photometric Stereo[END_REF] an iterative sequence of local area optimizations over different overlapping snapshot yields a suboptimal solution of E over the entire image Ω. There are nine different types of subspaces, also called grids (or snapshots), as shown in Fig. 1. These subspaces are called: top-left(1), top(2), top-right(3), middle-left(4), middle(5), middle-right( 6), bottom-left [START_REF] Noakes | Denoising images: non-linear Leap-Frog for shape and Light-Source recovery[END_REF], bottom [START_REF] Kozera | Existence and uniqueness in photometric stereo[END_REF], and bottomright(9), respectively. Note that for synthetic images we can assume (as explained before) that image is rectangular. Otherwise for the real images (with shadows) nine cases have to be combined with the visible regions of images (left for future work). There are five types of pixels in each grid as follows:

2D Leap Frog Local Optimizer

1. Type 0 -pixels that are only used to preserve the rectangular shape of a grid, and not used for computation. 2. Type 1 -pixels that are locked, and have constant value throughout the computation of the grid. These pixels are also excluded from the energy cost function computation. They are used to compute the central-difference derivative approximation for some pixels around them. 3. Type 2 -these pixels are also locked, and are included in the energy function. 4. Type 3 -these pixels are not locked, and are used as variables while searching for the minimum of the energy cost function.They are also included in the energy cost function. 5. Type 4 -these pixels are neither locked nor included in the energy function.

The nine grid types can be further reduced to three main types: side grids (touching only 1 border), corner grids (touching 2 borders excluding top-left case) and mid grids (touching none of the borders). This is because grids of the same type can be obtained from each other by rotation. Firstly, side grids are described as shown in Fig. 2. The central pixels of the border type grid are of type 3. Type 4 pixels are found directly between the pixels of type 3 and the border. This is because the border pixels must be included in the overall energy function, but it is impossible to approximate their central difference derivatives, and therefore their energies cannot be computed. Type 3 pixels are also surrounded by pixels of type 2 because minimizing the cost function has an impact on their surrounding pixels due to their derivative approximation. Lastly, there are type 1 pixels surrounding all others pixels. They are used just to evaluate the derivatives of other pixels and have no further impact on the algorithm. Corner grids are localized next to two borders as shown in Fig. 2. Type 3 pixels are again in the middle of the grid with type 4 pixels situated between them and the borders. Type 2 pixels also surround type 3 pixels, and type 1 pixels surround everything. The only pixel worth mentioning is the corner pixel. This pixel needs to be of type 0 because there are no surrounding dependent pixels. This implies that the strict corners of the space never changes and remains at the initial guess. Mid grids are the simplest cases as shown in Fig. 2. Type 4 pixels are not used because energy of all pixels in the grid can be calculated. There is a rectangle of type 3 pixels in the middle surrounded by type 2 and type 1 pixels. This case is straightforward and does not require any further explanation.

2D Leap Frog Algorithm

The non-linear 2D Leap Frog Algorithm is constructed as follows:

1. Obtain an initial guess u 0 (e.g. using Lawn Mowing Algorithm [START_REF] Noakes | The Lawn-Mowing Algorithm for noisy gradient vector[END_REF]). For the need of our paper we added a large noise to the ideal continuous solution u. 2. Divide the space into grids of fixed size, overlapping in such a way that 3 columns and rows of pixels are common for grids that are neighbors. 3. Start first iteration of the algorithm with the grid on the left-top corner, and apply a minimization algorithm to obtain new values of the unlocked variables. 4. Move to the right neighbor of the previous grid. Apply minimization algorithm to the function created by the top grid case. Repeat this process until the right border is reached. 5. In the last grid of the current row, the right-top grid case is used for optimization. 6. Move to the row below. The first grid uses the left grid case for optimization.

7. Move to right neighboring grid and minimize using the mid grid case. Repeat until the right boundary is reached. 8. The last grid in this row is minimized using the right grid case. 9. Repeat 3 previous steps of the algorithm for all rows except the bottom one. 10. First grid of the last row uses the bottom-left grid case to minimize E. 11. All consecutive grids except of the right most grid use the bottom grid case. 12. The last grid uses the right-bottom grid case. 13. Repeat all previous steps until one of the stopping condition is fulfilled.

In most cases the steps differ only in the type of grid cases that are used. 2D Leap Frog requires that, in every iteration, all pixels (except for the corner pixels) are unlocked at least once. Otherwise the algorithm does not work properly as some variables of the cost function E never change. In addition this guarantees that Leap Frog converges to critical point of E.

There are three possible stopping criteria for the 2D Leap Frog Algorithm:

1. Timeout: the algorithm computation stops upon exceeding a priori established time limit. 2. Maximum iterations limit: the algorithm has a cap on the number of iterations that is computed. 3. Epsilon limit: the global cost function is not decreasing anymore; this is the most difficult criterion possible in the algorithm because the iterations can have uneven decrease. For example there can be a slowdown in decrease for a few iterations in the middle of computation; therefore the best way of measuring the decrease is for at least four iterations. In this case if the decrease is close to zero for the chosen number of iterations, the algorithm stops.

Ambiguities and Relaxation

There are two kinds of ambiguities in our discrete settings namely, standard and strong ambiguities. We explain now the difference. Recall that three images are obtained from three linearly independent light-sources. With these data a system of three image irradiance equations is generated, and independent Gaussian noise is added to the corresponding images. Assume now that C denotes the table of constant entries c: which can be obtained by deleting corner values from the matrix of dimention n × n. Clearly we have:

E (u + C) = E (u) .
Therefore adding a constant value to the reconstructed surface in the discrete problem does not change the energy E. This is called a standard ambiguity in discrete case. We demonstrate now, the so-called strong ambiguity which also arises in the discretization of u. To see it let us take tables shown in Fig. 3.When adding these tables u i (i = 1, 2, 3, 4) to the reflectance maps, due to the central difference method, we also have:

E   u + 1≤k≤4 ck * u k   = E (u) .
This phenomenon is called a strong ambiguity. Such scenario can be described in terms of finding the minima of a function of four variables. If the function u is shaped like a valley, with the lowest place on the same plane, it is impossible to find only one minimum, as the function has then same value along the valley. This creates the problem of having infinitely many solutions that have the same energy. The simplest solution is to freeze four pixels in positions: (1; 2); (1; 3); (2; 2); (2; 3). This guarantees that the central differences are uniquely determined (for proof see Noakes and Kozera [START_REF] Noakes | Nonlinearities and noise reduction in 3-Source Photometric Stereo[END_REF]). When the algorithm finishes its work, these four pixels need relaxation, meaning that their minimum is found. It is important to add that, Leap Frog converges to sub-global solution (if initial noise is small then it converges to the global solution which is close to correct solution). For further details refer to Noakes and Kozera [START_REF] Noakes | Nonlinearities and noise reduction in 3-Source Photometric Stereo[END_REF].

u1 =            1
           u2 =            0 0 0 0 ... 0 0 0 1 0 1 0 1 ...
           u3 =            0
           u4 =            0

Outlier removal

In this section we discuss possible approaches to outliers removal. During reconstruction, the most unstable parts are the borders of the image. At the borders, continuity of the function ends. This pushes the pixels at the borders away from their proper values. An attempt is made, in this paper, using a statistical approach to remove these outliers. There are many efficient algorithms for outlier removal [START_REF] Atanassov | Algorithms for optimal outlier removal[END_REF], but they require a large sample of data to work correctly. We apply here a mask (i.e. a 3x3 pixels shifted over Ω) to identify potential outliers.

The first approach (called also Algorithm 1 ) used for outlier removal is based on Chauvenet's criterion [START_REF] Chauvenet | A Manual of Spherical and Practical Astronomy[END_REF]. This criterion states that any data that differ by more than two standard deviations from the mean of the data set is an outlier. The data set is created from the 9 closest non-border pixels to test one. Once an outlier is detected, it is replaced with the mean of the data set. The important feature of this test is that potential outliers are not considered as part of the sample (because if it is an outlier then it will disrupt the value of the mean). This test is done for all border pixels. Such approach unfortunately is not sufficient enough on its own (see Ex. 1).

The second approach (called Algorithm 2 ) is to modify 2D Leap Frog. The biggest problem with outliers was the starting edge of the image (the same for every iteration). At this point in the frame there are two borders that are unknown, and two borders that are not yet optimized. Later along this edge we have one unknown border, one optimized and two not optimized. This creates the most difficult local optimization problem in whole Ω. To remove this problem we decided that our implementation should start from different points for proceeding iterations. The change is done as follows:

1. The first iteration starts from left upper corner and proceed as described in previous paragraph. 2. Next start from right upper corner and proceed down from starting point. 3. Next start from right bottom corner and proceed left from starting point. 4. Next start from left bottom corner and proceed up from starting point.

Examples

This section demonstrates the difference between proposed outlier removal algorithms (i.e Algorithm 1 and 2). The last test shows also the performance of 2D Leap Frog Algorithm with respect to the size of frame. Newton's method is used here for each snapshot optimization. The Gaussian noise added to surface pictures is the same in all tests (i.e. with mean equal to 0 and deviation equal to 0.8).

Example 1

(i ) The first surface S 1 is described by the graph of the function u 1 (see Fig. 4):

u 1 (x, y) = (cos x + cos y) 3 8000 ,
defined over the domain [0, 10] × [0, 10]. The light-source directions used here are p = (1, 2, 3), q = (1, 8, 5) and r = (4, 2, 4). Gaussian noise is generated with a mean equal to 0 and deviation equal to 0.2 and added to u 1 to obtain initial guess. Therefore the noise is significant as compared to the base surface plot (see Fig. 4), having values within the range of -0.6 to 0.6.

(ii ) The second surface S 2 is described by the graph of the function u 2 (see Fig. 6): u 2 (x, y) = cos(5 * x) + sin(5 * y), defined over the domain [-0.5, 0.5] × [-0.5, 0.5]. The light-source directions used here are p = (2, 2, 3), q = (1, 3, 2) and r = (6, 2, 4). Gaussian noise is generated with a mean equal to 0 and deviation equal to 0.5 (see Fig. 6) and added to u 2 to obtain initial guess. The base surface plot have values is within the range of -0.2 to 0.2.

From those tests we can clearly see that our algorithm performs very good in terrain like surfaces. Also those tests shows perfectly all problems with outliers in surface reconstruction. In first case (see Fig. 5 and7) two types of outliers were observed, ones that are on the edges of the reconstructed surface (type 2) and ones that are anywhere else (type 1). In outcome from second implementation (having outlier removal Algorithm 1 -see Fig. 5 and7) we observe that we removed most of outliers from borders (only the strongest remain). This is because algorithm, using statistical approach, to work properly needs mean and standard deviation of the test area. Those values are taken for small area, and thus the strong outliers can disrupt them in such a manner that it will be possible to form them within the scope of accepted values. In the third approach i.e. using Algorithms 1 and 2 (see Fig. 5 and7) we can clearly see that no big outliers are created during reconstruction process. Hence combination of Algorithms 1 and 2 for outlier removal succeeds.

Example 2

The surface S 3 chosen for this test is described by the graph of the function u 3 :

u 3 (x, y) = 1 1 -tanh 25 6(4-6x+3x 2 -6y 2 +3y 2 )
, defined over the domain [0, 2] × [0, 2]. The light-source directions used here are p = (2, 4, 3), q = (3, 3, 2) and r = (6, 2, 1).Gaussian noise is generated with a mean equal to 0 and deviation equal to 0.2 (see Fig. 8) and added to u 3 to obtain initial guess. The base surface plot have values is within the range of 0 to 0.8. Table 1 shows that 6x6 is the optimum grid size for this implementation. This size provides the ideal ratio of free variables and the number of grids required to cover the image. The algorithm is run from the smallest to the largest possible grid sizes (5x5 to 8x8) for the implementation. At 9x9, containing 81 pixels, Matlab failed to run the Newton's Algorithm because there were too many unknowns in the function to minimize (about 50 unlocked variables). The next criterion is the quality of the reconstructed surface. Table 1 shows that smaller grid sizes produce reduced energies, therefore better surface reconstructions. This is because smaller functions are used to search for the local area minima. Thus the energy does not stabilize at a local minimum due to intensive grid overlaps. With bigger functions there is less change per iteration (as the whole picture is covered by fewer grids); therefore functions tend to end in its local minima, and do not change significantly in consecutive iterations.

Conclusions

It should be emphasized that 2D Leap Frog Algorithm is a very flexible and universal tool that can be used not only in Photometric Stereo. Clearly this computational method (with or without our modifications) is applicable to any optimization problem which in particular suffers from a large number of free variables. We close this paper with the following observations:

-We tested Leap Frog under the assumption that the Lambertian model is satisfied, and that the character of the Gaussian noise is preserved. The first simplification assures that the examined reflectance is modeled by formula (1) which is well approximated by its discrete analogue (3) (at least for image(s) with high resolution).

In addition minimizing the cost function (3) addresses the principle of maximum likelihood (see [START_REF] Zubrzycki | Lectures in Probability Theory and Mathematical Statistics[END_REF]) applied to Gaussian noise added at the image level (where normal random variables denotes measurements of image intensity of each pixel). Therefore under such ideal settings Leap Frog is tested. Of course, with real surfaces, where neither Lambertian model nor Gaussian noise are preserved Leap Frog can still be tested and compared in our experiments (this forms a potential further work). -2D Leap Frog Algorithm (combined with outliers removals: Algorithms 1 and 2) works very well in reconstructing different surfaces (in the presence of noise). -Our our tests clearly demonstrate that most significant changes in the cost function E (obtained for the whole surface S) are generated during the first 4-6 iterations. After that our cost function E is marginally decremented. However, it is necessary for an algorithm in question to work further because during those consecutive iterations the biggest surface outliers are removed. Unfortunately, due to space limit we were not able to include this in our tests. -The 2D Leap Frog Algorithm outputs very good results if equipped with close enough initial guesses. If an initial guess is too far from an ideal solution to the continuous Shape from Shading then the algorithm falls within a wrong potential well of our cost function. -According to the time criterion the best grid size for this implementation is 6 by 6 pixels snapshot for local area optimization. This grid has best ratio between the amount of grids needed to cover the whole picture with the amount of variables that are needed to be optimized. -This technique works obviously for an arbitrary number of images. However the more images are taken the smaller Ω becomes. Also, with more images, the computational cost increases. On the other hand more images imposes tighter conditions on u. This should improve the quality of the reconstruction process.

-Possible future work is to implement 2D Leap Frog algorithm that takes into consideration shading on surface pictures (cases when -1 ≤ cos Θ ≤ 0 are excluded).

Fig. 1 .

 1 Fig. 1. All 9 types of snapshots.

Fig. 2 .

 2 Fig. 2. Main three types of grids.

Fig. 3 .

 3 Fig. 3. Four tables showing strong ambiguities.

Fig. 4 .Fig. 5 .

 45 Fig. 4. (a) The ideal surface S1 = graph(u1) and (b) the initial guess.

Fig. 6 .Fig. 7 .

 67 Fig. 6. (a) The ideal surface S1 = graph(u2) and (b) the initial guess.

Fig. 8 .

 8 Fig. 8. (a) The ideal surface S1 = graph(u3) and (b) the initial guess.

Table 1 .

 1 Time efficiency for different grid sizes (given in minutes).

		Time needed Iterations needed Time per iteration Finishing energy
	5 by 5	14.5	16	0.9	0.015174
	6 by 6	12.1	10	1.21	0.019644
	7 by 7	17.6	14	1.25	0.093630
	8 by 8	20.3	18	1.72	0.132740


Petr Gajdoš
email: petr.gajdos@vsb.cz

Pavel Moravec
email: pavel.moravec@vsb.cz

Intruder Data Classification using GM-SOM

Keywords: SOM, Kohonen Network, parallel computation, KDD Cup 1999 Data Set

This paper uses a simple modification of classic Kohonen network (SOM), which allows parallel processing of input data vectors or partitioning the problem in case of insufficient resources (memory, disc space, etc.) to process all input vectors at once. The algorithm has been implemented to meet a specification of modern multicore graphics processors to achieve massive parallelism.

The algorithm pre-selects potential centroids of data clusters and uses them as weight vectors in the final SOM network.In this paper, the algorithm is used on a well-known KDD Cup 1999 intruders dataset.

Introduction

With the massive boom of GPU-based calculations, massive parallelism, memory considerations, simplicity of algorithms and CPU-GPU interaction have yet again to play an important role. In this paper, we present a simple modification of classic Kohonen's self-organizing maps (SOM), which allows us to dynamically scale the computation to fully utilize the GPU-based approach.

There were some attempts to introduce parallelism in Kohonen networks [START_REF] Mann | A parallel implementation of Kohonen's feature maps on the warp systolic computer[END_REF][START_REF] Openshaw | A parallel Kohonen algorithm for the classification of large spatial datasets[END_REF][START_REF] Nordström | Designing parallel computers for self organizing maps[END_REF][START_REF] Valova | A parallel growing architecture for selforganizing maps with unsupervised learning[END_REF][START_REF] Wei-Gang | A study of parallel self-organizing map[END_REF], however we needed an approach which is simple and easy to implement. Moreover, it should work both with and without the bulk-loading algorithm [START_REF] Fort | Advantages and drawbacks of the batch Kohonen algorithm[END_REF].

In this paper, we present such approach, which divides the training set into several subsets and calculates the weights in multi-step approach. Calculated weights with nonzero number of hits serve as input vectors of SOM network in the following step. Presently, we use a two-step approach, however more steps could be used if necessary.

The paper is organized as follows: in second chapter we mention classic SOM networks and describe the basic variant we have used. In third chapter we describe our approach and provide the calculation algorithm, in fourth the GPU-based processing. The fifth chapter introduces experimental data we have used and the final chapter before conclusion presents the comparison of results provided by our method with classic SOM calculation.

Kohonen self-organizing neural network

In following paragraphs, we will shortly describe the Kohonen self-organizing neural networks (self-organizing maps -SOM). The first self-organizing networks were proposed in the beginning of 70's by Malsburg and his successor Willshaw. SOM was ... ... proposed by Teuvo Kohonen in in the early 1980s and has been improved by his team since. The summary of this method can be found in [START_REF] Kohonen | Self-Organizing Maps[END_REF].

The self-organizing map is one of the common approaches on how to represent and visualize data and how to map the original dimensionality and structure of the input space onto another -usually lower-dimensional -structure in the output space.

The basic idea of SOM is based on the human brain, which uses internal 2D or 3D representation of information. We can imagine the input data to be transformed to vectors, which are recorded in neural network. Most neurons in cortex are organized in 2D. Only the adjacent neurons are interconnected.

Besides of the input layer is in SOM only the output (competitive) layer. The number of inputs is equal to the dimension of input space. Every input is connected with each neuron in the grid, which is also an output (each neuron in grid is a component in output vector). With growing number of output neurons, the quality coverage of input space grows, but so does computation time.

SOM can be used as a classification or clustering tool that can find clusters of input data which are more closer to each other.

All experiments and examples in this paper respect following specification of the SOM (see also the Figure 1):

-The SOM is initialized as a network of fixed topology. The variables dimX and dimY are dimensions of such 2-dimensional topology. -V m represents an m-dimensional input vector.

-W m represents an m-dimensional weight vector.

-The number of neurons is defined as N = dimX * dimY and every neuron n ∈< 0, N -1 > has its weight vector W m n -The neighborhood radius r is initialized to the value min(dimX, dimY )/2 and will be systematically reduced to a unit distance. -All weights vectors are updated after particular input vector is processed.

-The number of epochs e is know at the beginning.

The Kohonen algorithm is defined as follows:

1.

Network initialization

All weights are preset to a random or pre-calculated value. The learning factor η, 0 < η < 1, which determines the speed of weight adaptation is set to a value slightly less than 1 and monotonically decreases to zero during learning process. So the weight adaptation is fastest in the beginning, being quite slow in the end.

Learning of input vector

Introduce k training input vectors V 1 , V 2 , . . . , V k , which are introduced in random order.

Distance calculation

An neighborhood is defined around each neuron whose weights are going to change, if the neuron is selected in competition. Size, shape and the degree of influence of the neighborhood are parameters of the network and the last two decrease during the learning algorithm.

Choice of closest neuron

We select the closest neuron for introduced input.

Weight adjustment

The weights of closest neuron and its neighborhood will be adapted as follows:

W ij (t + 1) = W ij (t) + η(t)h(v, t)(V i -W ij (t)),
where i = 1, 2, . . . , dimX a j = 1, 2, . . . , dimY and the radius r of neuron's local neighborhood is determined by adaptation function h(v). 6. Go back to point 2 until the number of epochs e is reached.

To obtain the best organization of neurons to clusters, a big neighborhood and a big influence of introduced input are chosen in the beginning. Then the primary clusters arise and the neighborhood and learning factor are reduced. Also the η → 0, so the changes become less significant with each iteration.

GM-SOM method

The main steps of SOM computation have already been described above. Following text is focused on description of proposed method, that in the end leads to results similar to the classic SOM (See also Figure 2 for illustration of our approach). We named the method Global-Merged SOM, which suggests, that the computation is divided into parts and then merged to obtain the expected result. Following steps describe the whole process of GM-SOM:

1. Splitting of input set The set of input vectors is divided into a given number of parts. The precision of proposed method increases with the number of parts, however, it has own disadvantages related to larger set of vectors in the final phase of computation process. Thus the number of parts will be usually determined from the number of input vectors. Generally, k N * p, where k is the number of input vector, N is the number of neurons and p is the number of parts. The mapping of input vectors into individual parts does not affect final result. This will be later demonstrated by the experiments, where all the input vectors were either split sequentially (images) or randomly. 2. In parts computation Classic SOM method is applied on every part. For simplicity sake, an acronym PSOM will be used from now on to indicate SOM, which is computed on a given part. All PSOMs start with the same setting (the first distribution of weights vectors, number of neurons, etc.) Such division speeds up parallel computation of PSOMs on GPU. Moreover, the number of epochs can be lower than the the number of epochs used for processing of input set by one SOM. This is represented by a factor f , which is going to be set to 1 3 in our experiments. 3. Merging of parts Weight vectors, that where computed for each part and correspond to neurons with at least one hit, represent input vectors in the final phase of GM-SOM. The unused neurons and their weight vectors have light gray color in Figure 2. A merged SOM with the same setting is computed and output weights vectors make the final result of proposed method.

The main difference between the proposed algorithm and well known batch SOM algorithms is, that individual parts are fully independent on each other and they update different PSOMs. Moreover, different SOM algorithms can be applied on PSOM of a given part, which makes the proposed algorithm more variable. Next advantage can be seen in different settings of PSOMs. Thus more dense neuron network can be used in case of larger input set. The last advantage consists in a possibility of incremental updating of GM-SOM. Any additional set of input vectors will be processed by a new PSOM in a separate part and the final SOM will be re-learnt. For interpretation see Figure 3.

GPU Computing

Modern graphics hardware plays an important role in the area of parallel computing. Graphics cards have been used to accelerate gaming and 3D graphics applications, but Fig. 3. GM-SOM: Parallelization of the SOM computation by proposed method recently, they have been used to accelerate computations for relatively remote topics, e.g. remote sensing, environmental monitoring, business forecasting, medical applications or physical simulations etc. Architecture of GPUs (Graphics Processing Unit) is suitable for vector and matrix algebra operations, which leads to a wide use of GPUs in the area of information retrieval, data mining, image processing, data compression, etc. Nowadays, the programmer does not need to be an expert in graphics hardware because of existence of various APIs (Application Programming Interface), which help programmers to implement their software faster. Nevertheless, it will be always necessary to follow basic rules of GPU programming to write a more efficient code.

Four main APIs exists today. The first two are vendor specific, i.e. they were developed by two main GPU producers -AMD/ATI and nVidia. The API developed by AMD/ATI is called ATI Stream and the API developed by nVidia is called nVidia CUDA (Compute Unified Device Architecture). Both APIs are able to provide similar results. The remaining two APIs are universal. The first one was designed by Khronos Group and it is called OpenCL (Open Computing Language) and the second was designed by Microsoft as a part of DirectX and it is called Direct Compute. All APIs provide a general purpose parallel computing architectures that leverages the parallel computation engine in graphics processing units.

The main advantage of GPU is its structure. Standard CPUs (central processing units) contain usually 1-4 complex computational cores, registers and large cache memory. GPUs contain up to several hundreds of simplified execution cores grouped into socalled multiprocessors. Every SIMD (Single Instruction Multiple Data) multiprocessor drives eight arithmetic logic units (ALU) which process the data, thus each ALU of a In contrast to standard CPUs which can reschedule operations (out-of-order execution), the selected GPU is an in-order architecture. This drawback is overcome by using multiple threads as described by Wellein et al. [START_REF] Hager | Data access optimizations for highly threaded multi-core CPUs with multiple memory controllers[END_REF]. Current general-purpose CPUs with clock rates of 3 GHz outperform a single ALU of the multiprocessors with its rather slow 1.3 GHz. The huge number of parallel processors on a single chip compensates this drawback.

The GPU computing has been used in many areas. Andrecut [START_REF] Andrecut | Parallel GPU implementation of iterative PCA algorithms[END_REF] described CUDAbased computing for two variants of Principal Component Analysis (PCA). The usage of parallel computing improved efficiency of the algorithm more than 12 times in comparison with CPU. Preis et al. [START_REF] Preis | Accelerated fluctuation analysis by graphic cards and complex pattern formation in financial markets[END_REF] applied GPU on methods of fluctuation analysis, which includes determination of scaling behavior of a particular stochastic process and equilibrium autocorrelation function in financial markets. The computation was more than 80 times faster than the previous version running on CPU. Patnaik et al. [START_REF] Patnaik | Accelerator-oriented algorithm transformation for temporal data mining[END_REF] used GPU in the area of temporal data mining in neuroscience. They analyzed spike train data with the aid of a novel frequent episode discovery algorithm, achieving a more than 430× speedup. The GPU computation has also already been used in intrusion detection systems [START_REF] Platos | Scaling IDS construction based on nonnegative matrix factorization using GPU computing[END_REF] and for human iris identification (for our experiments on this topic see [START_REF] Gajdos | Iris recognition on GPU with the usage of non-negative matrix factorization[END_REF]).

The use of our SOM modification on GPU is illustrated in Figure 4.

The KDD Cup 1999 collection [START_REF] Stolfo | Cost-based modeling for fraud and intrusion detection: results from the jam project[END_REF] represents data indicating several basic types of attack on computer networks. Significant features have been recorded and the type of attack has been evaluated. The data is based on the 1998 DARPA Intrusion Detection Evaluation Program, which has been prepared and managed by MIT Lincoln Labs. The main task is to build a predictive model (i.e. a classifier) capable of distinguishing between intrusions (attacks), and normal connections.

The 1999 KDD intrusion detection contest dataset used a specific format of features, extracted from original raw data, which corresponded to 7 weeks of traffic and had approximately 4 GiB of compressed data streams, which were processed into about five million connection records.

Each of the records consists of approximately 100 bytes and the result is labeled based on the actual attack type (or normal, in case it is part of normal traffic) which falls into one of the four basic categories:

-DOS -denial-of-service -the machine is flooded with requests and the exhaustion of resources is attempted. Nowadays, it is mostly used in the distributed form. -R2L -remote to local -unauthorized access from a remote machine, e.g. trying to guess passwords or SSH keys. -U2R -user to root -unauthorized user rights elevation, typically through some exploit (e.g. using buffer overflow techniques) to gain superuser (root) privileges. probing -port scans, active network surveillance and other probing.

There are 22 defined attack types, which were typical in 1998 and the normal category in the training data and some additional attack types present only in the testing data, which the classification framework should detect. The records contain both the categorical, Boolean and numerical attributes, which makes the classification harder.

Experiments

The Table 1 is a summary table for seven performed experiments. The whole training data collection was divided into several parts for individual experiments. In each experiment, every part represented an input data set for SOM. Then all partial results (weights of neurons) were merged together and became a new input set for final computation of SOM. Thus the total time consists of particular computation times of SOMs plus required merging time. Sufficient number of graphics processor units (GPU) are required for such computation. Usually, more graphics contexts can be created on a single GPU, however, they share all resources (memory, multiprocessors, etc.). If the number of GPUs is less than the number of parts, and just a single graphics context per GPU can be created (because of memory requirements, etc.), more parts must be computed in series. Then the computation times of all such parts must be summed. Therefore, the column "Total time" of the Table 1 shows ideal computation times in case of sufficient computation power.

The number of parts affects the precision of SOM classification. The higher number of parts the smaller precision. It depends on process of division of input data set as well. Every part consists of random set of input vectors in our experiments. Every two parts represent disjoint sets of input vectors. Finally, every vector of the original data set (non-divided) belongs to some part. The ratio between the number of parts and final precision of classification method will be the subject of further research.

Conclusion

The need of parallel computation of SOM drove us to a new method, that has been also utilized in this paper. Although it has some common features with well known SOM batch or hierarchical algorithms, it is not one of them, as it has its unique properties. The results presented in previous section show that whilst the classic SOM is much faster because of the GPU-based computation, the use of PSOMs and their computation by separate nodes furher improves the computation time.

Firstly, the proposed algorithm can utilize the power of batch processing in all inner parts (PSOMs). Secondly, all PSOMs can have different number of neurons in their networks, which could be found in hierarchical algorithms. Lastly, our method excludes neurons, which do not cover any input vectors in the intermediate phase of GM-SOM.

All experiments suggest, that the results are very close to results provided by classic SOM algorithm. Also, since we have used the KDD Cup 1999 collection, the data is comparable with other experiments done on this collection.

1 Fig. 1 .

 11 Fig. 1. Kohonen network structure

Fig. 2 .

 2 Fig.2. GM-SOM: An Illustrative schema of the proposed method. All input vectors are divided into ten parts in this case.

Fig. 4 .

 4 Fig. 4. GM-SOM: Parallelization of the SOM computation by proposed method

Table 1 .

 1 Computation times with respect to subdividing of input data set.

	exp. parts size of a part Comp. time Merging Total Precision
	id [#]	[#]	per part [s] time [s] time [s] [%]
	1	1	1469529	1249	0	1249	94,29
	2	5	293906	249	4	453	94,13
	3 10	146953	124	9	133	93,57
	4 20	73477	62	18	80	90,72
	5 30	48985	43	27	70	88,47
	6 40	36739	32	36	68	87,91
	7 50	29391	26	45	71	87,34

Acknowledgment

This work was supported by the Bio-Inspired Methods: research, development and knowledge transfer project, reg. no. CZ.1.07/2.3.00/20.0073 funded by Operational Programme Education for Competitiveness, co-financed by ESF and state budget of the Czech Republic.


Aneta Poniszewska-Maranda
email: anetap@ics.p.lodz.pl

Role approach in access control development with the usage control concept

Development of information technology, progress and increase of information flow have the impact on the development of enterprises and require rapid changes in their information systems. Very important stage of data protection in information system is the creation of high level model, satisfying the needs of system protection and security. This paper presents the role engineering aspects of access control for dynamic information systems. The objective is to find the approach of access control to ensure in perspective the global coherence of security rules for all components of an system.

Introduction

Development of information technology, progress and increase of information flow have the impact on the development of enterprises and require rapid changes in their information systems. The growth and complexity of functionalities that they currently should face causes that their design and realization become the difficult tasks and strategic for the enterprises at the same time. Data protection against improper disclosure or modification in the information system is an important issue of each security policy realized in the institution.

Role engineering for role-based access control is a process consisting of determination and definition of roles, permissions, security constraints and their relations. The company's roles can be regarded in two aspects -functional (reflects the main business functions of the company) and organizational (reflects the organization hierarchy of the company). Before a concrete access control model can be implemented, the role engineering process has to take place. The aspect of role engineering is connected close to the aspects of analysis and design of information systems. During our previous studies, we examined the design methods of the information systems and the design methods of information system security [START_REF] Goncalves | Role engineering: from design to evaluation of security schemas[END_REF]. However, it is difficult to find the global method that takes into account both the design of system and its associated security scheme.

The process of roles identification and setting up in an organization is a complex task because very often the responsibilities of actors in an organization and their functions are few or badly formalized. Moreover, the role concept is an abstract approach. It does not correspond to particular physical being and therefore it is very difficult to give definitions that comprise the whole world.

To conclude, the research of roles in security schema needs a real engineering approach that provides a guide identify, specify and maintain them.

Many different works concerning the problem of role engineering were presented in the literature [START_REF] Bertino | The Specification and Enforcement of Authorization Constraints in Workflow Management Systems[END_REF][START_REF] Fernandez | Determining Role Rights from Use Cases[END_REF][START_REF] Basin | Model driven security: From UML models to access control infrastructures[END_REF][START_REF] Coyne | Role engineering[END_REF][START_REF] Epstein | Towards a UML Based Approach to Role Engineering[END_REF][START_REF] Epstein | Engineering of Role-Permission Assignment to Role Engineering[END_REF][START_REF] Coyne | Role Engineering for Enterprise Security Management[END_REF][START_REF] Roeckle | Process-oriented approach for rolefinding to implement role-based security administration in a large industrial organization[END_REF] and others. First of all, most of the paper tread the static aspects of access control domains. They do not take into consideration the problems of dynamic changes affecting the access control rules in modern information systems, particularly distributed information systems. Moreover, whereas everyone agrees that safety must be taken into account as quickly as possible, the proposed role engineering approaches are often disconnected from the design and the evolution of information system for which they are provided.

Coyne in [START_REF] Coyne | Role engineering[END_REF] proposes to collect different user activities to define the candidate roles. Fernandez et al. in [START_REF] Fernandez | Determining Role Rights from Use Cases[END_REF] propose to use the use cases to determines the role rights of system users but do not describe the constraints aspect and rolehierarchies. Epstein et al. [START_REF] Epstein | Towards a UML Based Approach to Role Engineering[END_REF] propose to express RBAC elements with UML diagrams but do not define the role engineering process. Roeckle et al. [START_REF] Roeckle | Process-oriented approach for rolefinding to implement role-based security administration in a large industrial organization[END_REF] propose a process-oriented approach for role engineering but only on meta level without details about role hierarchy, derivation of permissions and relation between some elements. Epstein and Sandhu [START_REF] Epstein | Engineering of Role-Permission Assignment to Role Engineering[END_REF] describe role engineering of role-permission assignment but not go into detail about constrains and role hierarchies in the process. Neumann and Strembeck propose in [START_REF] Neumann | A Scenario-driven Role Engineering Process for Functional RBAC Roles[END_REF][START_REF] Strembeck | Scenario-Driven Role Engineering[END_REF] very interesting scenariodriven role engineering process for RBAC model. However this proposition does not take into consideration the dynamic aspects of access control.

This paper presents the engineering aspects in access control of dynamic information systems. The paper is composed as follows: section 2 presents the role concepts and usage concept in aspect of access control, section 3 gives the outline of approach based on these concepts (Usage Role Based Access Control -URBAC). Section 4 deals with the cooperation of two actors in role creation process of information system security, while section 5 shows the representation of URBAC approach using the UML concepts. Section 6 describes the process of roles production based on URBAC approach presenting the stage of security profile creation for the system's users.

Access control based on role and usage concepts

Development in area of information systems, especially modern, distributed information systems causes that traditional access control models are not sufficient and adequate for such systems in many cases. Some imperfections were found in domain of these security models [START_REF] Goncalves | Role engineering: from design to evaluation of security schemas[END_REF]:

traditional access control models give only the possibility to define the authorizations but do not provide the mechanisms to specify the obligations or conditions of access control, developers or security administrators can only pre-define the access rights that will be next granted to the subjects, decision about granting or not an access can be only made before the required access but not during the access, mutable attributes can be defined for subjects and for objects of a system.

These disadvantages and the needs of present information systems caused the creation of unified model that can encompass the use of traditional access control models and allow to define the dynamic rules of access control. Two access control concepts are chosen in our studies to develop the new approach for dynamic information systems: role concept and usage concept. The first one allows to represent the whole system organization in the complete, precise way while the second one allows to describe the usage control with authorizations, obligations, conditions, continuity (ongoing control) and mutability attributes.

Role-based access control approach [START_REF] Ferraiolo | Proposed NIST Role-Based Access control[END_REF] or its extensions [START_REF] Goncalves | Role engineering: from design to evaluation of security schemas[END_REF][START_REF] Poniszewska-Maranda | Conception Approach of Access Control in Heterogeneous Information Systems using UML[END_REF] requires the identification of roles in a system. The role is properly viewed as a semantic structure around which the access control policy is formulated. Each role realizes a specific task in the enterprise process and it contains many functions that the user can take. For each role it is possible to choose the necessary system functions. Thus, a role can be presented as a set of functions that this role can take and realize. Each function can have one or more permissions, and a function can be defined as a set or sequence of permissions. If an access to an object is required, then the necessary permissions can be assigned to the function to complete the desired job. Specific access rights are necessary to realize a role or a particular function of this role.

The usage control approach [START_REF] Lazouski | Usage control in computer security: A survey[END_REF][START_REF] Pretschner | Distributed usage control[END_REF][START_REF] Zhang | Formal Model and Policy Specification of Usage Control[END_REF] is based on three sets of decision factors: authorizations, obligations and conditions that have to be evaluated for the usage decision. The obligations and conditions are added in the approach to resolve certain shortcomings characteristic for the traditional access control strategies. The most important properties of usage control that distinguish it from traditional access control concepts and trust management systems are the continuity of usage decisions and the mutability of attributes. Continuity means that usage control decision can be determined and enforced before an access (as in traditional access control models) and also during the ongoing period of the access. Mutability represents the mutability of subject and object attributes that can be either mutable or immutable. The mutable attributes can be modified by the actions of subjects and the immutable attributes can be modified only by the administrative actions.

Approach of role based access control with usage control

The complexity of actual organizations (i.e. matrix based organizational structure) has guided our proposition to extend the standard RBAC model by role management facilities that allow a finer distribution of responsibilities in an enterprise. On the other hand, the dynamism of actual information systems was the reason to use the concepts of Usage Control to develop the new implementation of access control models to support the management of information system security.

The proposed access control approach was based on two access control concepts: role concepts and usage concepts. It was named Usage Role-based Access Control (URBAC) [START_REF] Poniszewska-Maranda | Implementation of Access Control Model for Distributed Information Systems using Usage Control[END_REF][START_REF] Poniszewska-Maranda | Administration of access control in information systems using URBAC model[END_REF]. The term usage means usage of rights on information system objects. The "rights" include the rights to use particular objects and also to delegate the rights to other subjects.

The detailed view of usage role-based access control approach is presented on figure 1. Subjects can be regarded as individual human beings. They hold and execute indirectly certain rights on the objects. Subject permits to formalize the assignment of users or groups of users to the roles. Subject can be viewed as the base type of all users and groups of users in a system.

A Role is a job function or a job title within the organization with some associated semantics regarding the authority and responsibility conferred on a member of the role. The role can represent a competency to do a specific task, and it can embody the authority and responsibility. The roles are created for various job functions in an organization.The direct relation is established between roles and subjects that represent the users or groups of users. It is also possible to define the hierarchy of roles, represented by aggregation relation RoleHierarchy, which represents the inheritance relations between the roles.

The association relation between the roles and subjects is described by the association class SubjectAttributes that represents the additional subject attributes (i.e. subject properties) as in Usage Control. Subject attributes provide additional properties, describing the subjects, that can be used for the usage decision process, for example an identity, enterprise role, credit, membership, security level. Each role allows the realization of a specific task associated with an enterprise process. A role can contain many functions Function that a user can apply. Consequently, a role can be viewed as a set of functions that this role can take to realize a specific job. It is also possible to define the hierarchy of functions, represented by the aggregation relation named FunctionHierarchy, which provides the hierarchical order of system functions.

Each function can perform one or more operations, a function needs to be associated with a set of related permissions Permission. To perform an oper-ation one has the access to required object, so necessary permissions should be assigned to corresponding function. The permission determines the execution right for a particular method on the particular object. In order to access the data, stored in an object, a message has to be sent to this object. This message causes an execution of particular method Method on this object Object. Very often the constraints have to be defined in assignment process of permissions to the objects. Such constraints are represented by the authorizations and also by the obligations and/or conditions.

Authorization (A) is a logical predicate attached to a permission that determines the permission validity depending on the access rules, object attributes and subject attributes. Obligation (B) is a functional predicate that verifies the mandatory requirements, i.e. a function that a user has to perform before or during an access. Conditions (C) evaluate the current environmental or system status for the usage decision concerning the permission constraint.

A constraint determines that some permission is valid only for a part of the object instances. Therefore, the permission can be presented as a function p(o, m, Cst) whereo is an object, m is a method which can be executed on this object and Cst is a set of constraints which determine this permission. Taking into consideration a concept of authorization, obligation and condition, the set of constraints can take the following form Cst = {A, B, C} and the permission can be presented as a function p(o, m, {A, B, C}). According to this, the permission is given to all instances of the object class except the contrary specification.

The objects are the entities that can be accessed or used by the users. The objects can be either privacy sensitive or privacy non-sensitive. The relation between objects and their permissions are additionally described by association class ObjectAttributes that represents the additional object attributes (i.e. object properties) that can not be specified in the object's class and they can be used for usage decision process. The examples of object attributes are security labels, ownerships or security classes. They can be also mutable or immutable as subject attributes do. The constraints can be defined for each main element of the model presented above (i.e user, group, subject, session, role, function, permission, object and method), and also for the relationships among the elements. The concept of constraints was described widely in the literature [START_REF] Park | Attribute Mutability in Usage Control[END_REF][START_REF] Poniszewska-Maranda | Conception Approach of Access Control in Heterogeneous Information Systems using UML[END_REF][START_REF] Strembeck | An Integrated Approach to Engineer and Enforce Context Constraints in RBAC Environments[END_REF][START_REF] Bertino | The Specification and Enforcement of Authorization Constraints in Workflow Management Systems[END_REF]. It is possible to distinguish different types of constraints, static and dynamic, that can be attached to different model elements.

Two actors in role creation process of information system security

Two types of actors cooperate in the design and realization of security schema of an information system [START_REF] Poniszewska-Maranda | Conception Approach of Access Control in Heterogeneous Information Systems using UML[END_REF]: on the one hand it is application/system developer who knows its specification that should be realized and on the other hand it is security administrator who knows the general security rules and constraints that should be taken into consideration on the whole company level. We propose to partition the responsibilities between these two actors in the process of definition and implementation of security schema on access control level and to determine their cooperation in order to establish the global access control schema that fulfill the concepts of URBAC. This partition of responsibilities is presented in figure 2 and the responsibilities were divided into two stages: conception stage and exploitation stage.

Conception stage

The realization process of information system or simple application is provoked by a client's request or in general by the client's needs to create a new information system or new application (i.e. to add a new component to the existing information system). Basing on the client's needs and requirements the application/system developer creates the logical model of application/system and next designs the project of this system that will be the base for its implementation. This model and next the project contain all the elements expressing the client's needs (i.e. needs of future users). The application developer defines the elements of this application and its constraints corresponding to the client's specifications. These elements can be presented in a form adequate to the access control concepts -it will be the URBAC approach in our case. Therefore, the developer generates the sets of following elements: roles, functions, permissions and security constraints. These sets of elements should be presented to the security administrator in a useful and legible form. The duties of application developer basing on URBAC are:

definition of permissions -identification of methods and objects on which these methods can be executed, definition of object attributes associated to certain objects according with access control rules, assignment of elements: permissions to functions and functions to roles, definition of security constraints associated to the elements of the application, i.e. authorizations, obligations and conditions on the permissions and standard constraints on roles, functions and their relationships.

Exploitation stage

The exploitation stage is realized by the security administrator on the global level of information system. The security administrator defines the administration rules and company constraints according to the global security policy and application/system rules received from the developer. He should also check if these new security constraints remain in agreement with the security constraints defined for the elements of existing information system in order to guarantee the global coherence of the new information system. The security administrator received from the developer the sets of elements in the form adequate to URBAC: set of of roles, set of functions, set of permissions and set of security constraints of the application. He uses these sets to mange the global security of the information system. First of all he defines the users' rights to use the particular applications. Two sets on company level are important to define the users' rights: persons working for the enterprise (i.e. users) and functions realized in the enterprise (i.e. business functions).

Security administrator is also responsible for the definition of security constraints for these assignments on global level with respect of defined security rules. These constraints concern first of all the following relations: user-businessFunction, businessFunction-businessFunction and businessFunction-role.

Therefore, the duties of security administrator are as follows:

definition of users' rights basing on their responsibilities and their business functions in an organization -assignment of users to the roles of information system, organize the users in groups and definition the access control rights for the groups of users that realize for example the same business functions -assignment of groups to the roles of information system, definition of subject (i.e. user or group of users) attributes associated to certain users or groups of users that allows to determine the dynamic aspects of security constraints, definition of security constraints for the relationships between users and roles or group of users and roles.

The second important task of security administrator is the management of set of applications assuring the global coherence of the whole system on access control level. This assurance is exceptionally important in case of addition of new application in an information system when new access control elements appear both on local level and on global level.

Representation of URBAC using the UML concepts

Unified Modeling Language (UML) is now a standard language for analysis and design of information systems [START_REF]OMG Unified Modeling Language (OMG UML): Superstructure[END_REF]. It is used almost all over the world in software engineering field for object-oriented analysis and design. It has a set of different models and diagrams that allow to present the system project from different points of view showing the whole system together with its components. Some elements and concepts of UML can be used to implement the URBAC approach, especially during the design stage of information system and its associated security schema based on URBAC.

From this reason, UML was chosen to be used in role engineering process to implement and realize the URBAC approach. To accomplish this, the concepts of UML and URBAC should firstly be joined. Two types of UML diagrams have been chosen to provide the URBAC: use case diagram and interaction diagram. The use case diagram presents the system's functions from the user point of view. It define the system's behavior without functioning details. The interaction diagram describes the behavior of one use case [START_REF]OMG Unified Modeling Language (OMG UML): Superstructure[END_REF]. It represents the objects and messages exchanged the use case processing.

The relationships between UML concepts and concepts of usage role-based access control are as follows (Fig. 3):

role (R) from access control model can be presented as an UML actor, function (F) from URBAC can be represented by an UML use case, each actor from use case diagram can be in interaction with a set of use cases and these relations specify the relations of R-F type (between roles and functions), methods executed in sequence diagrams and also in other UML diagrams can represent the methods of URBAC, objects that occur in UML diagrams, e.g. sequence diagram, communication diagram, can be attached to the object concept of access control model, permissions (P) of URBAC can be found examining the sequence diagram(s) describing the particular use case, use case diagram offers four types of relations between its elements:

• communication relation between an actor and a use case that represents the relation between a role and a function, i.e. R-F relation, • generalization relation between actors, representing the inheritance relation between roles (R-R relation), • two types of relations between use cases represent the inheritance relations between functions of URBAC, i.e. F-F relations • subject attributes (e.g. user attributes) from URBAC can be represented by the set of attributes defined for an instance of actor class of UML, • concept of object attributes from URBAC can be attached to set of attributes defined for the objects in its class specification.

The concept of constraints of URBAC approach corresponds directly to the constraint concept existing in UML. The security constraints of URBAC can be defined for different elements and for relations between these elements. These constraints can be presented on UML diagrams corresponding to types and locations of elements for which these constraints will be defined.

The authorization is a constraint attached to a permission that determines the permission validity depending on defined access rules. It can be represented by the UML constraint defined for the method's execution in sequence diagram.

The obligation is a constraint defined on a permission but it concerns also the subject (e.g. a user) -subject should fulfill the obligation executing a function before or during an access. This type of constraints can be presented as UML constraint in sequence diagram (as pre-condition or an invariant), especially from version 2.0 of UML that provide the combinator fragments in sequence diagrams (e.g. "alt" or "opt") allowing the definition of constraint conditions. The condition is a constraint also defined on a permission but it concerns the session element. It defines current environmental or system status and states during the user session that can be used for the usage decision. The conditions can be also represented by UML constraints defined in sequence diagrams (mainly as an invariants).

Remaining types of constraints represent the constraints defined for the roles, functions and their relations. Such constraints are represented by the UML constraints defined for actors, use cases and their relations on use case diagrams or sometimes on sequence diagrams.

Production of roles based on URBAC approach

The process of role production is based on the connections between UML and URBAC, described in section 5. It can be automatic or partially automatic. Two types of UML diagrams were used to realize this process: use case diagrams, where roles and functions of a system are defined and sequence diagrams, where permissions are assigned to the rights of method executions realized in framework of each use case. These two types of diagrams should be examined to identify the roles of URBAC, the functions that are used by these roles to interact with the information system, the permissions needed to realize these functions and the constraints that determine the possible rights.

To obtain these elements of URBAC, first the rules for creation of set of roles has to be defined.

Each subject (i.e. user or group of users) in an information system is assigned to a security profile (i.e. user profile) which is defined by the set of roles that can be played by him. A security profile is defined by a pair (s, listRoles(s)): s is a subject, listRoles(s) is a set of roles assigned to this subject. Taking into consideration the concept of user, such profile can be defined as follows: (u, listRoles(u)), where u is a user, listRoles(u).

The process of creation of user profiles, i.e. production of set of roles, in information system with the use of UML diagrams contains two stages [START_REF] Goncalves | Role engineering: from design to evaluation of security schemas[END_REF]:

Determination of a function with assigned permissions

As it was shown in section 5, a use case of UML meta-model corresponds to a function of URBAC model. Use cases define the system functionality or in other words the interactions and needs system's users that cooperate with the system. Each use case should be defined by its scenario that defines the specification of the use case interaction in form of sequence of actions performed on the system's objects. It allows the definition of set of privileges for execution of different actions on the objects. Therefore, in order to identify the permissions assigned to a function it is necessary to start from the sequence diagram corresponding to the function.

Each message msg (o 1 , o 2 , m) in the interaction sent by object o 1 to object o 2 to execute method m on object o 2 should have a suitable permission assigned. This permission corresponds to the execution of method m on object o 2 . On the addition of security constraints, the definition of the message is as follows: msg (o 1 , o 2 , m, cst) where cst represents a set of constraints -authorizations, obligations and conditions:

cst(p) = A (p) ∪ B (p) ∪ C (p)
Consequently, the set of permissions for interaction i is defined as follows:

P (i) = {p | φ (msg (o 1 , o 2 , m, cst)) = p (m, o 2 ) ∧ cst (p) = true}
where φ is a function that assigns a permission to message msg, o 1 is an actor or class instance that can execute method m on object o 2 and cst is a set of constraints

cst(p) = A (p m,o2 ) ∪ B (p m,o2 ) ∪ C (p m,o2 ) .
Sequence diagram in UML meta-model is defined by the set of interactions. Therefore, the set of permissions determined for sequence diagram d S and described by the set of interactions D S is as follows:

P (d S ) = ∪ i ∈ D S P (i)
The use case µ described by set M of interaction diagrams d i has the following set of permissions assigned to it:

P (µ) = ∪ d i ∈ M P (d i )
The set P (µ) represents the set of permissions assigned to the function specified by the use case µ.

Determination of a role with assigned functions

The use case diagram presents the system's functionality from the point of view of the actors. It is possible to find the set of use cases (i.e. URBAC functions) for each actor (i.e. URBAC role) examining this type of UML diagrams. Therefore, the determination of a role with the set of functions assigned to it will be realized by examining the relationships between the actors and use cases on the use case diagram. The use case diagram ucd i contains the use cases (i.e. functions) attached to chosen actors (i.e. roles). The set of functions assigned to role r j , described by one use case diagram, is defined by the functions that are in direct or indirect relations with this role (i.e. by the inheritance relations between the functions) on this diagram:

F (r ucdi ) = {f | f = uc , uc ∈ ucd i ∧ (r ucdi , f ) ∈ R -F } ∪ {f ′ | f ′ = uc , uc ∈ ucd i ∧ ((f, f ′ ) ∈ F -F ∧ (r ucdi , f ) ∈ R -F )}
The set of functions of role r j is defined by the union of use cases assigned to this role in all use case diagrams describing the whole system application D uc :

F (r j ) = ∪ ucd i ∈ D uc F (r ucdi )
In order to define the security profiles for system users or groups of users, the set of roles should be assigned to subject profiles (i.e. user profiles). This task is realized by security administrator during the exploitation stage who has to take into consideration the security constraints defined on the global level and the subject attributes defined for the subjects that determine the access control rights of particular system users.

Conclusion

The concepts of access control approach presented in the paper were used to define the process of role engineering for creation of security profiles for users of information system. The paper presents the representation of URBAC using the UML concepts, the process of roles production based on URBAC, the stages of creation of user profiles. The process of role production is a very important stage in definition of logical security policy of an information system. It can be realized by two actors: application developer and security administrator who cooperate with each other to guarantee the global coherence on access control level.

The aspects of presented approach are implemented on software platform that provides with the software tool to manage the logical security of company information system from the point of view of application developer and from the point of view of security administrator. Our next research is concentrated on aspects of security constraints for URBAC approach and on the algorithm to maintain the coherence of URABC scheme during the addition of new application.

Fig. 1 .

 1 Fig. 1. Meta-model of URBAC model

Fig. 2 .

 2 Fig. 2. Two actors in creation of information system security schema

Fig. 3 .

 3 Fig. 3. Relationships between concepts of URBAC and UML concepts