Yie Leu
email: leufy@thu.edu.tw

Yi-Ting Hsiao

Kangbin Yim

Ilsun You

A Real-Time Intrusion Detection and Protection System at System Call Level under the Assistance of a Grid

Keywords: Forensic Features, Intrusion Detection and Protection, Data Mining, Identifying Malicious behaviors, Computational Grid

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Currently, most computer systems use user IDs and passwords to authenticate their users. However, many users often share their login information with their coworkers and request them to assist co-tasks, thereby making the login information as one of the weakest points of computer security. Also, internal hackers, the legal users of a system who attack the system internally, are hard to detect. Shan et al. [START_REF] Shan | Safe side effects commitment for OS-level virtualization[END_REF] claimed that OSlevel system calls are much more helpful in detecting hackers and identifying a malicious internal user. In this paper, we propose a real time security system, named the Intrusion Detection and Protection System (IDPS for short) which detects malicious behaviors at system call level. The IDPS collects users' system-call-usage histories, and uses data mining and forensic techniques to mine typical system calls and their sequences (together named system call sequences (SC-sequences)), as a user's forensic features generated by the activities that the user often performs. The features are a kind of biological characteristics essential in identifying a user. When a user logs in a computer, the IDPS starts monitoring the user's input system calls so as to detect whether he/she is issuing an attack or not, and identify who the account owner is if IDPS discovers that this user is not the account holder. This system collects system call patterns for user operations, and identifies those system call attack patterns that hackers often use. By a long-term observation on user behaviors, user habits can be effectively identified. Further, The Longest Common Subsequence (LCS) algorithm [START_REF] Shyu | Finding the longest common subsequence for multiple biological sequences by ant colony optimization[END_REF] for pattern and profile mining and computational clustering are also employed to improve the performance of the IDPS.

Related Research

Computer Forensics science is one kind of computer security technologies that analyzes what attackers have done, like sending computer viruses, malware and malicious codes, or issuing Distributed Denial-of-Service (DDoS for short) attacks. O'Shaughnessy et al. [START_REF] Shaughnessy | Development and evaluation of a dataset generator tool for generating synthetic log files containing computer attack signatures[END_REF] acquired particular network intrusion and attack patterns from a system log file. The datasets required are extracted from system log files, containing the traces of computer misuse. Therefore, there are obvious potentials for the use of synthetically generated log files that accurately present the traces or patterns of misuse. In this paper, IDPS adopts a similar method to establish attack patterns and evaluate the proposed algorithms. Mahony et al. [START_REF] O'mahony | Promoting recommendations: An attack on collaborative filtering database and expert systems applications[END_REF] collected attack patterns and studied on-line systems, including various effective collaborative filtering algorithms, information filtering techniques and expert-system applications. In the previous work [START_REF] Leu | Intrusion detection and identification system using data mining and forensic techniques[END_REF], we developed a security system to collect forensic features for users on the system command level, rather than on the system call level, by invoking the data mining and forensic techniques. However, if attackers use many sessions to issue attacks, named multi-stage attacks, or DDoS attacks, then due to system processing capability, the intrusion detection system (IDS) cannot thoroughly identify all attack patterns. Giffin et al. [START_REF] Giffin | Automated discovery of mimicry attacks[END_REF] provided another example of integrating computer forensics with a knowledge-based system. The system, adopting a predefined model which allows system call sequences to be normally executed, was employed by detection systems to restrict program execution so as to protect an underlying system. This is helpful to detect applications with a series of malicious system calls and automatically identify attack sequences having been collected in knowledge models. Other DoS/DDoS security systems can be found in [START_REF] Choi | Detecting web based DDoS attack using MapReduce operations in cloud computing environment[END_REF][START_REF] Kang | A new logging-based IP traceback approach using data mining techniques[END_REF]. The IDPS uses data mining and profiling techniques to respectively analyze and identify user operation characteristics, which as a kind of biological patterns, are essential in identifying a user. This system can analyze and identify attack patterns that hackers often use as well.

System Framework

The IDPS as shown in Fig. 1 consists of a system call monitor & filter, mining server, detection server and local computational grid. The system call monitor & filter, as a loadable kernel module embedded in the kernel of the system being considered, collects the system calls submitted to the kernel and stores these system calls in the user's own log file. The mining server analyze users' log data with data mining techniques to identify a user's habit patterns, which are recorded in the user' profiles. Detection server compares users' current inputs with users' computer usage habits collected in their user profiles and attacker profile to, respectively, detect malicious behaviors and identify sources of attacks in a real-time manner. When an intrusion is discovered, the detection server notifies the system call monitor & filter to isolate the user from submitting system calls to the system kernel. Both the detection server and mining server are run on the local computational grid to respectively accelerate the IDPS's on-line detection and mining speeds, and enhance its detection and mining capability. If a user logs in the system by using other person's login user ID and password, the IDPS can identify who the underlying user is by computing the similarity score between the user's current inputs and the habit patterns collected in the account holders' user profile.

System Call Monitor & Filter

Due to the possibility of submitting too many system calls to the kernel at the same time, the IDPS may not completely monitor all system calls generated by user-submitted jobs. In this study, we focus on those system calls produced by shell-commands, named shell-command system calls. The Class-limited-system-call list, a component of the system call Monitor & Filter, collects the shell-command system calls that the kernel has received. To know what the typical shell-command system calls are, we use the term frequency-inverse document frequency (TF-IDF, Zhang et al., 2005) algorithm and iData Analyzer [START_REF] Roger | Data Mining: A tutorial-based primer[END_REF] tool to analyze the intercepted system calls. Table 1 lists the four commands' representative system calls, which are also the members of the Classlimited-system-call list contained.

Mining Server

A mining server extracts those system calls generated by a user from user's log file and counts the time that an SC-sequence appears in this file to produce the user's habit file.

The SC-sequences collected in this habit file are then compared with those generated in all other users' habit files in the underlying system to identify the user's user-specific SC-patterns and those SC-patterns commonly used by all or most users. After that, the user profile is established by attaching a SC-pattern with the corresponding similarity weight. The calculation of the weight will be described later. Fig. 2 illustrates the corresponding control flow.

Mining User and Attack Habits

The IDPS processes the system calls in user log file with a sliding window, named a Log-sliding window (L-window for short), to partition the system calls collected in user's log file along their submitted sequence into k-grams where k is the number of a series of consecutive system calls, k =2, 3, 4... |sliding window|. In addition, another sliding window of the same size (i.e., the same number of system calls), named Compared-sliding window (C-window for short), is employed for another session in the same user log file. This time, k' consecutive system calls, preserving their submitted sequence, are extracted from a C-window to generate a total of (|sliding window| -k' + 1) k'-grams, k'=2, 3, 4…|sliding window|. Mining server invokes Algorithm 1 to compares each of ∑ (|𝐿 -𝑤𝑖𝑛𝑑𝑜𝑤𝑠| -𝑘 + 1)

|𝐿-𝑤𝑖𝑛𝑑𝑜𝑤𝑠| 𝑘=2 k-grams with ∑ (|𝐶 - |𝐶-𝑤𝑖𝑛𝑑𝑜𝑤| 𝑘 ′ =2
𝑤𝑖𝑛𝑑𝑜𝑤| -𝑘 ′ + 1) k'-grams by using the LCS algorithm which can reveal the similarity between two strings by skipping noises. After that, the C-window shifts one system call right, and the above mentioned comparison is performed again. execve access getcwd getdents64 = 10 open getdents64 getdents64 exit_group mkdir = 8 execve access rename rename exit_group = 6 access exit_group chdir = 21 Fig. 3. A part of a user habit file, in which a line is ended by its appearance count. Fig. 3 shows an example of a habit file in which a line is a habit, also a SC-sequence or an access pattern, ended by its appearance count. The more frequently a SC-sequence appears, the higher probability the sequence is one of the user's habits. Furthermore, we can apply this algorithm to process an attacker's log file so as to extract his/her usage habits. After legal operations are ripped off, what remains is attack patterns that form a signature file.

Creating User Profiles

A user profile is a habit file with the appearance counts of SC-patterns being substituted by the patterns' corresponding similarity weights. Given a set of user habit files D={UP1,UP2…UPN} where N is the number of users and also the number of habit files in the system. Let T={CS1,CS2…CSk} be the set of SC-patterns retrieved from D. Let Di={UP'1,UP'2…UP'Mi}. Each Di element consists of a set of habit files containing at least one element of T, e.g., CSi , CSi ϵT, and |Di|=Mi. The similarity weight Wij of CSi in UPj is defined as

(1)
where i=1,2,3…k, j=1,2,3 …N, sfij is the appearance count of CSi in UPj, nsj is the total number of SC-patterns in UPj, AVG(ns) is the average number of SC-patterns an element of D has, and log((N+0.5)/Mi)/log(N+1) is the inverse characteristics profile frequency (ICPF). We employ Eq. ( 1), which is commonly used to assign a weight to a term in the information retrieval domain Fig. 5 shows an example of a user profile in which a line is ended by its similarity weight. Once the user profile is created, we send it to all grid nodes.

Detection Server

Detection server checks to see whether the underlying user is the underlying account holder j or not by calculating the similarity scores between these newly submitted system calls in the user's current session and the usage habits collected in the undering user profile by using the Okapi formula (Robertson et al., 1996), which is commonly used to define the similarity score between documents. Given an unknown user x's current input SC-sequences, denoted by SCSx, the similarity score, e.g., SimSxj, between SCSx and user j's user profile UPj, is defined as

(2)
where p is the number of SC-sequences, i.e., a pattern, appearing in both the SCSx and UPj, Fix is user x's SC-sequence's appearance count in habit file, Wij is the SCsequence's similarity weight in UPj. The higher the similarity score, the higher the probability that the user x is the person j who submitted the inputs. The concept of detection server in calculating the user habit is similar to that of the mining server. [START_REF] Leu | Intrusion detection and identification system using data mining and forensic techniques[END_REF] showed a method to calculate the similarity scores between current session's systemcommand-sequences and each of the user profiles in the system. The similarity scores between the underlying user and the account holder's profile should be ranked high within the first x%. If not, the underlying user is recognized as hacker, meaning he/she is not the account holder.

Attack Types

In this study, there are three types of intrusions. Type 0 is defined as the situation where a member of a specific group submits a system call that the group members are prohibited to use. Type I attack is an attack that penetrates a system and submits a sensitive system call that will erase or modify sensitive data or attack the system. A type II attack consists of several attack patterns, each of which is considered as an attack stage. In fact, a hacker mixing specific system calls as noises with an attack pattern can sometimes successfully penetrate a security system. Type 0 and Type I attacks can be detected by the system call monitor & filter by comparing an input system call directly with Class-limited-system-call list. This detection in system call level can protect a system completely. The Type II attack will be identified by detection server.

Detection multi-stage Attack

As stated above, attackers' common attack patterns are presented in the format of a profile. Given current input SC-sequences, we can make sure whether the SCsequences contain hacker-specific attacks by checking the hacker j's ranking. If the similarity score between the input SC-sequences and hacker profile is within the first x%, the IDPS will issue an alert message, and reply an "unsafe" message accompanied by the user's ID to inform the system call monitor & filter which will isolate the user and prevent him from further use of the system.

Experiments

We first install the system call monitor & filter into the main computer, e.g., Redhat ES, of an enterprise system to obtain 10 different categories of user log files as the experimental data for the duration between November 1, 2012 and April 30, 2013. The testbed resources in this study are shown in Table 2. In this experiment, we define a paragraph size as 3 * |sliding window|. A typical paragraph size is 30 system calls, in which detection server ranks the similarity scores of all user accounts in a system. The purpose is to avoid continuously performing ranking when each system call is input. logid=0, uid=1000, SCS length=30, attacker= 0.1347, account= 0.9578 logid=0, uid=1000, SCS length=60, attacker= 0.3124, account= 0.9634 logid=0, uid=1000, SCS length=90, attacker= 0.7003, account= 0.9284 -> alert logid=0, uid=1000, SCS length=120, attacker= 0.9501, account= 0.9073 -> alert Fig. 6. Detection server ranks for all user profiles when the paragraph size is 30.

Fig. 6 shows an example, in which the IDPS detects the current input SC-sequence. If the rank of the profile of account holder is lower than the threshold 0.95 or if the rank of an attacker profile is higher than the threshold, the detection server alerts the system manager that the current user is suspected as a hacker.

Identifying Malicious Programs

A malicious program which is suspected as a Type II attack can be detected by the detection server by checking to see whether the hacker ranking is higher than the perdefined threshold.

setreuid32(), setuid32(), setregid32(), setgroups32() = 0.8531 fork(),ptrace(),execve(), ptrace() = 0.9854 socket(), setsockopt(), sendto(), close(), nanosleep() = 0.7638 Fig. 7. A part of a hacker profile, in which a line is ended by its similarity weight.

During the experiment, we installed the attack patterns listed in Fig. 7 as the hacker injection codes into a running process or issued a DDoS attack to the system. The detection server's attack recognition rate is 99%.

Detection server accuracy and response time

We use 75% of the user's historical data as the training data to test Algorithm 1 run on the mining server in parallel for creating user profiles. The remaining 25% as the test data is then given to the detection server to simulate the user online inputs. The threshold is set to 0.95. A total of 105400 system calls were collected from 1726 log files. The average length of the SC-sequence sliding window was 10. The user recognition rate of the IDPS is 93%. Fig. 8 shows the experimental result generated by the detection server which employs 60 processors in parallel. The maximum response time is less than 0.45 sec. This means that IDPS can detect malicious behaviors in a real-time manner.

Comparison with other host-based intrusion detection systems

In this experiment, we compare the IDPS with other host-based intrusion detection systems (HIDS for short). The results are shown in Table 3, in which "" means that the system has this function, ""represents that the system does not have the function, "∆" shows that the system has the function but not completely equivalent and ART is the average response time.

Conclusions and Future Work

In this article, we proposed an approach to find users' habits by employing data mining techniques and profile features. The purpose is to identify the representative SCsequences for a user. After that, the weight of SC-sequences is computed so that a user's profile can be established. To make sure whether a user is the current account holder or a hacker, the IDPS calculates the similarity scores between the SC-sequences in the current user's input session and each user' usage behaviors. The accuracy is high, making the IDPS a valuable auxiliary subsystem that can assist the system managers to identify an internal hacker in a closed environment. With this approach, The IDPS can also discover an out-side attacker. Also, employing a local computational grid environment can shorten the detection server's response time which is less than 0.45 sec. Additionally, to effectively detect an attack and further efficiently reduce the response time, we need a cluster workload monitor and a faster filter and detection algorithm [START_REF] Angin | An agent-based optimization framework for mobile-cloud computing[END_REF][START_REF] Ling | Enhancing smart grid system processes via philosophy of Security -case study based on information security systems[END_REF]. A mathematical on the IDPS's behaviors will help us to derive its formal performance and cost models so that users can, respectively, determine its performance and cost before using it. They can also increase detection accuracy and improve the decisive rate. Those constitute our future research topics.

Fig. 1 .

 1 Fig. 1. The IDPS system architecture.

Fig. 2 .

 2 Fig. 2. Control flow of generating a user profile.

Fig. 4 .

 4 Fig. 4. An example of comparison between an L-window on session m and a C-window of 10system calls on session p (10 system calls on session r) with the LCS algorithm[START_REF] Roger | Data Mining: A tutorial-based primer[END_REF].

Fig. 5 .

 5 Fig. 5. A part of a user profile, in which a line is ended by its similarity weight.

Fig. 8 .

 8 Fig. 8. The experimental response time of the detection server run on 1, 2, 4, 6 and 10 users on 60 processors in parallel.

Table 1 .

 1 A part of the Class-limited-system-call list.

	Command	The representative System call
	chmod	fchmodat()
	kill	kill()
	date	clock_gettime()
	rm	unlinkat()

Table 2 .

 2 The specifications of the Computational grid (cluster) resources.

	Resource No. CPU Type	No.	BogoMips	Mem	Open-
				Core	/each	(GB)	Mpi
	Alpha	1	Intel(R) Xeon(R) E5645 @	12	4800	25	1.4.1
	(IDPS)		2.40GHz
	Beta	1	AMD Opteron(tm) 6174 @	48	4400	50	1.4.1
			2.20GHz
	Gamma	1	Intel(R) Xeon(R) E5645 @	12	4800	25	1.4.1
			2.40GHz

Table 3 .

 3 The comparsion of IDPS with other HIDS under attack.

	Attack	User	Type 0	Type I	Type II	DDoS
	System	/ART(sec.)	/ART(sec.)	/ART(sec.)	/ART(sec.)	/ART(sec.)
	OSSEC		 / 60	 / 60		
	SAMHAIN		 / 60	 / 60		
	McAfee					
	Symantec CSP		 / 2	 / 2	∆ / 3	∆ / 3.5
	IDPS	 / 0.45	 / 0	 / 0	 / 0.45	 / 0.45


Zhi-Guo Chen
email: chenzhiguo520@gmail.com

Sung-Ryul Kim

A Hybrid System for Reducing Memory and Time Overhead of Intrusion Detection System

Keywords: Intrusion Detection System, Principal Component Analysis Algorithm, C4.5 Algorithm, Time Overhead and Memory Overhead

With the growing use of the internet worldwide, internet security becomes more and more important. There are many techniques available for intrusion detection. However, there remain various issues to be improved, such as detection rate, false positive rate, memory overhead, time overhead, and so on. In this paper, a new hybrid system for network intrusion detection system using principal component analysis and C4.5 is presented, which has a good detection rate and keeps false positive and false negative rate at an acceptable level for different types of network attacks. Especially, this system can effectively reduce the memory overhead and the time overhead of building the intrusion detection model. These claims are verified by experimental results on the KDD Cup 99 benchmark network intrusion detection dataset.

Introduction

With the rapid development and application of computing and communication technologies, more and more people solve problems or handle things with the internet, using such things as email, internet banking, video conference, save personal information and so on. Therefore, internet security becomes one of the key problems in the world. Traditionally, firewall is a widely used security measure but the firewall alone does not provide enough security. The protection of computer systems, network systems and the securities of information infrastructure usually depend on a kind of intrusion detection technology also [START_REF] Lu | Three-level Hybrid Intrusion Detection System[END_REF].

So far, many techniques for intrusion detection have been proposed and intrusion detection systems [2] by these techniques are broadly classified into two categories: misuse-based IDS and anomaly-based IDS [START_REF] Brown | A Survey of Intrusion Detection Systems[END_REF]. Misuse-based IDS is based on signatures for known attacks. If unknown attacks or known attacks which do not match any signatures appear, then these attacks may not be detected with misuse-based IDS. So, in order to detect new attacks, IDS need to revise the set of signatures frequently. Anomaly-based IDS is different from misuse-based IDS, Anomaly-based IDS is able to detect known and unknown attacks by building profiles of normal behaviors. If a new behavior is far from normal behaviors of the profiles, then the behavior will be treated as an attack. Anomaly based intrusion detection using data mining algorithms such as nave Bayesian classifier (NB), decision tree (DT), neural network (NN), k-nearest neighbors (KNN), support vector machine (SVM), and genetic algorithm have been widely used by researchers to improve the performance of IDS [START_REF] Hlaing | Feature Selection and Fuzzy Decision Tree for Network Intrusion Detection[END_REF]. However, Anomaly detection suffers from low detection and high false positive rates and it incurs large memory and time overhead for the detection model.

In this paper, we present a new hybrid system for network intrusion detection using principal component analysis and C4.5 algorithm [START_REF] Ben Amor | Naive bayes vs decision trees in intrusion detection systems[END_REF] which has good detection rate and keeps false positive and false negative rates at an acceptable level for different types of network attacks while having the benefit of lower the memory and the time overhead for building the detection model. PCA (principal component analysis) [START_REF] Smith | A tutorial on Principal Components Analysis New York[END_REF][START_REF] Zhao | Improved Clustering for Intrusion Detection by Principal Component Analysis with Effective Noise Reduction[END_REF] is used to reduce the dimension of original high dimensional data and remove noise effectively. Then we use new dataset which handled by PCA to make intrusion detection model by C4.5 algorithm. The experimental results show that the proposed method has acceptable detection rates (DR), false positive rate(FP), false negative rate(FN) and accuracy.

The rest of this paper is organized as follow: in section 2, we will introduce principal component analysis and C4.5 algorithm. Section 3, describes our proposed method. In section 4, we introduce experiment and result, performances estimation of IDS, experimental dataset and experimental analysis. Finally, in section 5, we conclude this paper.

Algorithm

PCA algorithm

The performance of the intrusion detection model depends on the quality of dataset. So noise in the dataset is one of the challenges in data mining. The reason for dealing with noisy data is that it will avoid over-fitting the dataset. The irrelevant and redundant attributes of dataset may lead to complex classification model and reduce the classification accuracy. So we need to reduce noises, irrelevant and redundant attributes firstly. Principal component analysis algorithm have been widely used in dimension reduction; it can be effective to deal with complex data that have high dimensions. It can identify the main elements and structure of data, remove noise and redundant attributes, express the data with simple format.

The following procedure describes the PCA algorithm we use to deal with dataset S (D × N ) where N is the number of data example and D is the number of dimension of original dataset S. Each column represents one data that have dimensionalityD.

S =      S 11 • • • S m1 • • • S N 1 S 12 • • • S m2 • • • S N 2 . . . . . . . . . . . . . . . S 1D • • • S mD • • • S N D      1.

C4.5 Algorithm

C4.5 algorithm has been widely used in classification and decision making. C4.5 algorithm is a later version of the ID3 algorithm [START_REF] Quinlan | Induction of Decision Trees[END_REF] proposed by R. Quinlan [START_REF] Quinlan | Improved Use of Continuous Attributes in C4.5[END_REF]. The majority of this algorithm uses a descendent strategy from the root to the leaves. To ensure this procedure, the following generic parameters are required. The gain ratio (attribute selection measure) taking into account the discriminative power of each attribute over classes in order to choose the best one as the root of the decision tree. C4.5 decision tree divides data items into subsets, based on the attributes. It finds the one attribute that maximizes gain ratio and divides the data using that attribute.

Let us assume that D is a dataset and that A i is one of attribute of the dataset. Let us also assume that the dataset has a set of classes C 1 , C 2 , ..., C m . The information gain is calculated as the follows:

Gain(D, A i ) = Entropy(D) - ∑ i∈V alues(Ai) |D i | |D| Entropy(D i ) (1)
where,

Entropy(D) = - m ∑ i=1 f req(C i , D) |D| log 2 f req(C i , D) |D| (2)
where f req(C i , D) denotes the number of examples in the datasetD belonging to class C i and D i is the subset of dataset D divided by the attribute

A ′ i s value a m . Then SplitInf o(A i
) is defined as the information content of the attribute A i itself [START_REF]The third international knowledge discovery and data mining tools competition dataset[END_REF]:

SplitInf o(D, A i ) = - ∑ i∈V alues(Ai) |D i | |D| log 2 |D i | |D| (3)
The gain ratio is the information gain calibrated by Split Info:

GainRatio(D, A i ) = Gain(D, A i ) SplitInf o(A i ) (4)
1. If A i is a discrete attribute [START_REF] Kumar Jain | An Efficient Intrusion Detection Based on Decision Tree Classifier Using Feature Reduction[END_REF] then divide the dataset by discrete values of A i (a 1 , a 2 , ..., a m ).

2. If A i is a continuous attribute then use information gain to efficiently find the best split point and disperse the dataset by this best split point [START_REF] Ruggieri | Efficient C4.5[END_REF]. If attribute A i has values (A i1 , A i2 , , A im , , A ih ) then firstly sort the continuous values (called candidate cut point) from small to large and then divide dataset with these candidate cut points with > A im and ⩽ A im (i ⩽ m < h). Then we calculate the information gain for each possible cut point. The cut point for which the information gain is maximized amongst all the candidate cut points is taken as the best split point. We divide the current dataset (subset dataset) according this point. Now we can build the tree by dividing the current dataset (subset dataset) by the selected attribute (discrete attributes according the attribute values, continuous attributes according to best split point).

Our proposed method

Using PCA Algorithm

To determine different types parameters of network attacks. Firstly, we need randomly select data in file "corrected" which is downloaded from KDD Cup 99 site to make training dataset and test dataset. The dataset is S(N × D), where N is the number of the data records and D is the dimension of the KDD data (41 dimension except for class identity). And then we use the PCA algorithm to reduce the dimension of the KDD data to get new Dataset D(N ×d). Where N is the number of the new dataset and d is the dimension (the number of attributes) of new dataset D. We then add the original datasets class identity in the new Dataset D. After reducing the dimension by PCA we use the C4.5 algorithms to build the intrusion detection model.

Making Detection Model

After reducing the dimension by PCA, we get new dataset D where all of the attributes are continuous ones. So we should use the continuous attributes handling method of C4.5 algorithm that has been described earlier to make tree structure.

Dataset D contains attributes A 1 , A 2 , ..., A d and each attribute A i contains the following continuous attribute values (A i1 , A i2 , ..., A im , ..., A ih ). The training dataset also has a set of Class C 1 , C 2 , ..., C m . Each data in the training data D have particular class C j . We follow the next procedure.

1. Find the best split point of every attributes and calculate gain ratio in training dataset D with C4.5 continuous attribute handling method. Compare the gain ratio of every attribute. Select A i among the attributes A 1 , A 2 , ..., A d which have maximize gain ratio to make the root attribute node, and then divide the training dataset D into subsets (D 1 , D 2 ) depending on the best split point A im .

2. Find the best split point of every attribute and calculate gain ratio in subset dataset D i . Compare the gain ratio of every attribute. Select A i among the attributes A 1 , A 2 , ..., A d which have maximize gain ratio to make the attribute node, Then divide the subset dataset D i into subsets (D i1 , D i2 ) depending on the best cut point A im .

3. Continue this process until subset dataset's entropy is zero or all attributes have same maximizes gain ratio in the subset dataset D s . If subset dataset's entropy is zero and we know that all of the Class C i in subset dataset is same. In this case, a leaf node will be set up. And if all attribute's gain ratio is same, We use f req(C 1 , D s ), f req(C 2 , D s ), ..., f req(C m , D s ) to determine the class in dataset D s . When we test an example data X, we should use PCA algorithm to deal with this example. And then we use the tree structure to find the Class (leaf node). Pseudo code: Since after reducing the dimension by PCA, we get new dataset D where all of the attributes are continuous ones. So we just need use the continuous attributes handling method of C4.5 algorithm to build tree:

C4.5 (Dataset D, Attributes

Experiment and Result

Performances Estimation

Accuracy, detection rate (DR), false positive rate (FP) and false negative rate (FN) are basic parameters that are used for performance estimation [START_REF] Hlaing | Feature Selection and Fuzzy Decision Tree for Network Intrusion Detection[END_REF] of intrusion detection models. We can accord the following simple confusion matrix for calculating the parameters. In the Intrusion Detection System(IDS), a detection rate(DR) is an instance which is normal is classified as normal or attack is classified as attack. False positive(FP) means no attack but IDS detect as attack and false negative(FN) means attack occurs but IDS detect as normal. Accuracy is also an important parameter that determines the percentage of correctly classified instance. Form the confusion matrix; we can get these parameters by following calculations.

DetectionRate = a/(a + b) and d/(d + c) F P = b/(a + b) F N = c/(c + d) Accuracy = (a + d)/(a + b + c + d)

Dataset

The KDD Cup 1999 dataset [START_REF]The third international knowledge discovery and data mining tools competition dataset[END_REF] is used in this experiment, which is network connection data collected from the U.S Air Force LAN in nine weeks. KDD-CUP99 dataset have a set of inherent constructed features. Each record has 41 characteristic attributes and one more attribute assigns the record type. And 34 attributes are continuous data types, 7 attributes are discrete data types in the characteristic attributes. The list of the input attributes in KDD99 dataset for each network connections is shown below. The data contains attack types (marked at last attribute) that can be classified into four main categories as follows:

1. Denial of Service (DOS): Denial of Service (DOS) attack makes some computing or memory resources too busy or too full to handle legitimate requests, or denies legitimate users access to a machine.

2. Remote to User (R2L): Remote to User (R2L) is an attack that a remote user gains access of a local user account by sending packets to a machine over a network communication.

3. User to Root (U2R): User to Root (U2R) is an attack that an intruder begins with the access of a normal user account and then becomes a root-user by exploiting various vulnerabilities of the system.

4. Probing: Probing (Probe) is an attack that scans a network to gather infor-mation or find known vulnerabilities. An intruder with a map of machines and services that are available on a network can use the information to look for exploits.

So, all the classes in KDD99 dataset can be categorized into five main classes and four attacks are recorded into different attacks which are shown in Table 3.

Experimental Analysis

The number of training and test data is shown in the following: In order to evaluate the performance of the proposed algorithm for different types of network attacks, we performed 5-Class classification using KDD99 dataset. We compared our method with C4.5 algorithm. Our experimental results show that detection rates (DR) and accuracy of our proposed method and C4.5 algorithm almost identical. But from Figure 3, we can see that our method is effective to reduce the memory overhead and the time overhead of building the intrusion detection model.

There are not many examples of U2R, R2L and Probing to build the intrusion detection model. Thus, the C4.5 method and our method have lower detection rates for these types of network intrusions. For similar reasons, even if one example is not correctly detected the resulting rate will show considerable differences. Therefore, the detection rate of Probe and false negative of U2R have considerable difference between our proposed method and C4.5 method.

From figure 3, we can see that the number of nodes in our proposed method is almost similar to C4.5 method, but one node in our method occupies just 12bytes and it can be stored as [x, y] (x is the selected attribute written as int format, y is best split value that can be written as double format). If we use C4.5 algorithm to deal with the original dataset S. For continuous we also can store the node as [x, y], but for discrete attribute, if it have lots of attribute values, we need to store a node as [x, a 1 , a 2 , ..., a i , ..., a m ] (x is the selected attribute written as int format, a i is discrete attribute value that can be written as int format). In this case, the discrete attribute values requires more memory. So, we can conclude that our proposed method can effectively reduce the memory overhead of C4.5 method.

Because of we use PCA algorithm to reduce the dimension of the data, our proposed method just need 267.838 seconds to build the intrusion detection model. Therefore, after comparing the training time of two methods we can conclude that PCA algorithm can be effective to reduce the time overhead of building Intrusion Detection Model.

Overall consideration accuracy, detection rates, false positive rate, false negative rate, memory overhead and time overhead, we can conclude that our method has good performance for intrusion detection system and that our proposed method is effective to improve the performances of Anomaly-based intrusion detection system.

Conclusion

This paper introduced a new hybrid system for network intrusion detection using principal component analysis and C4.5 algorithm. The results show that it has acceptable detection rate, false positive and false negative to detect the 5 types of the KDD dataset. It also can be effective to reduce the memory overhead and the time overhead of building the intrusion detection model. But the false negative and false positive rates for R2L are high. The reason is there are not many examples of R2L to build detection model and the intrusion detection model has misclassified the data as normal. So the future work will focus on avoiding misclassified R2L, reducing the false positive and false negative rates of R2L and improving the detection rate of normal and R2L.

Fig. 1 .Fig. 2 . 3 .

 123 Fig. 1. Performance of our method and C4.5 algorithm

  According the eigenvalues to select the dimension number d of biggest eigenvectors to make the new dataset. The eigenvectors are represented as u 1 , u 2 , ..., u d and then find its matrix transpose U ; 6. Get new dataset D = (U S ′ ) T (N × d), where N is the number of the data examples and d is the dimension of the new dataset D. Add the original datasets class identity in new Dataset D and we have completed the transformed dataset D and with every record included with d attributes and one class identity.

	Map discrete attributes to continuous attributes;
	2. Calculate the mean value of all data examples S;
	3. Subtract mean vector for each data example; 4. Find covariance matrix ∑ of dataset S, and then calculate all eigenvectors and eigenvalues of ∑ ;
	5.

Table 1 .

 1 Confusion Matrix

		Predicted Class Positive Predicted Class Negative
	Actual Class Positive	a	b
	Actual Class Negative	c	d

Table 2 .

 2 Input attributes in KDD99 Dataset

	No Input Attribute Type No	Input Attribute	Type
	1	Duration	Con. 22	is_guest_login	Dis.
	2	protocol_type	Dis. 23	Count	Con.
	3	Service	Dis. 24	srv_count	Con.
	4	Flag	Dis. 25	serror_rate	Con.
	5	src_bytes	Con. 26	srv_serror_rate	Con.
	6	dst_bytes	Con. 27	rerror_rate	Con.
	7	Land	Dis. 28	srv_rerror_rate	Con.
	8	wrong_fragment	Con. 29	same_srv_rate	Con.
	9	Urgent	Con. 30	diff_srv_rate	Con.
	10	Hot	Con. 31	srv_diff_host_rate	Con.
	11 num_failed_logins Con. 32	dst_host_count	Con.
	12	logged_in	Dis. 33	dst_host_srv_count	Con.
	13 num_compromised Con. 34	dst_host_same_srv_rate	Con.
	14	root_shell	Con. 35	dst_host_diff_srv_rate	Con.
	15	su_attempted	Con. 36 dst_host_same_src_port_rate Con.
	16	num_root	Con. 37 dst_host_srv_diff_host_rate Con.
	17 num_file_creations Con. 38	dst_host_serror_rate	Con.
	18	num_shells	Con. 39	dst_host_serror_rate	Con.
	19	num_access_files	Con. 40	dst_host_rerror_rate	Con.
	20 num_outbound_cmds Con. 41	dst_host_srv_rerror_rate	Con.
	21	is_host_login	Dis.

Table 3 .

 3 Different Data Types in KDD99 Dataset

	Data Type	Mark
	normal	normal
	Denial of Service	apache2, mailbomb, processtable, udpstorm, back, land,
	(DOS)	neptune, pod, smurf, teardrop
	Remote to User (R2L)	ftp_write, guess_passwd, multihop, phf, spy, warezclient, warezmaster, imap, named, sendmail, snmpgetattack, snmpguess, worm, xlock, xsnoop
	User to Root	buffer_overflow, loadmodule, perl, rootkit, httptunnel, ps,
	(U2R)	sqlattack, xterm
	Probing	Satan, ipsweep, nmap, portsweep, mscan, saint

Table 4 .

 4 Number of training and test examples

	Types Training data Test data
	Normal	5869	5781
	Probing	429	384
	DOS	22086	22297
	U2R	20	21
	R2L	1596	1517

Table 5 .

 5 Confusion matrix of our method

Acknowledgments

. This research was supported by Next-Generation Information Computing Development Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (2011-0029924).


Shang-Nan Yin
email: yinshangnan@gmail.com

Zhi-Guo Chen
email: chenzhiguo520@gmail.com

Sung-Ryul Kim

LDFGB Algorithm for Anomaly Intrusion Detection

Keywords: Graph-based clustering, outlier detection, Intrusion Detection

With the development of internet technology, more and more risks are appearing on the internet and the internet security has become an important issue. Intrusion detection technology is an important part of internet security. In intrusion detection, it is important to have a fast and effective method to find out known and unknown attacks. In this paper, we present a graph-based intrusion detection algorithm by outlier detection method which is based on local deviation factor (LDFGB). This algorithm has better detection rates than a previous clustering algorithm. Moreover, it is able to detect any shape of cluster and still keep high detection rate for detecting unknown or known attacks. LDFGB algorithm uses graph-based cluster algorithm (GB) to get an initial partition of dataset which depends on a parameter of cluster precision, then we use the outlier detection algorithm to further processing the results of graph-based cluster algorithm. This measure is effective to improve the detection rates and false positive rates.

Introduction

In modern society, we use internet at anytime and anywhere, so internet security becomes one of the hottest issues and we need to find an effective way to protect this network infrastructure. Intrusion detection system [1] is a useful method for detecting attacks. In 1987, Denning [START_REF] Denning | An intrusion-detection model[END_REF] introduced the first anomaly intrusion detection model, which is able to detect known and unknown attacks. After that research, many methods have been proposed for anomaly intrusion detection, such as machine learning [START_REF] Savage | Network Support for IP traceback[END_REF], immunological [START_REF] Dasgupta | An Immunity-Based Technique to Characterize Intrusions in Computer Networks[END_REF] and data mining. Among these techniques, data mining has been widely used and it successfully solves the deficiencies of intrusion detection. The clustering algorithm is an important technology of data mining which can offset these deficiencies.

Clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (same attributes) to each other than to those in other groups (clusters). K-means algorithm [START_REF] Kaufan | Finding groups in data: an introduction to cluster analysis[END_REF] is a popular clustering algorithm which is used in anomaly intrusion detection. This algorithm classifies similar data set into same clusters, and classifies dissimilar data set into different clusters. However, the user must set the number of clusters k, meaning that the user has to have some knowledge about the data. Other methods also have some disadvantages, for example, combining simulated annealing and clustering algorithm [START_REF] Ni | An unsupervised intrusion detection method combined clustering with chaos simulated annealing[END_REF] requires a lot of training data and thus consumes excessive resource. In recent year, many researchers have proposed to avoid excessive resource consumption. One of effective methods is graph-based clustering. For example, PBS algorithm [START_REF] Guohui | Intrusion detection method based on graph clustering algorithm[END_REF] introduces a measurement method of data points similarity which is based on an approximate function. But, this algorithm cannot achieve an exciting detection rate. LDC algorithm [START_REF] Mingqiang | A Graph-based Clustering Algorithm Intrusion Detection[END_REF] improves the detection rate, but it doesnt accurately and comprehensively analysis the distribution situation of data nodes.

In this paper, we present LDFGB algorithm for intrusion detection which is one of the graph clustering algorithms. It is based on the LDC algorithm, uses local deviation factor to differentiate the distribution situation of data nodes and to identify outliers. The experimental results show that the proposed method is efficiently for anomalybased intrusion detection.

The paper is organized as follows. In section 2, we introduce the graph-based clustering. In section 3, we describe the LDFGB algorithm in detail. In section 4, we describe our evaluation methods and experimental results. Finally, we conclude this paper.

Graph-Base Cluster Algorithm

Graph-based clustering algorithm is a method commonly used in automatic partitioning of a data set into several clusters. It proceeds by setting a parameter of clustering precision to control the result of clustering. Records in dataset are packaged as a node. These nodes are treated as vertex of a complete undirected graph, and the distance values between these notes as weight of the edge. The distance is calculated by Euclidean distance function (Table 1). According these values of distance, we construct a distance matrix I. And the threshold δ is computed from a parameter of cluster precision α.

d(i, j) = √ |x i 1 -x j 2| 2 + |x i 2 -x j 2| 2 + ... + |x i p -x j p| 2 (1)
δ = dismin + dismax -dismin * Clusterprecision (2)
dismin and dismax represent the minimum and maximal value of matrix I respectively. So an edge is cut down from this graph if its value of weight greater than threshold δ as shown in Figure .1 Finally, we transverse the whole graph, the nodes would be classified into the same cluster if there is an edge between them. Therefore, several sub-graphs are created. Each sub-graph represents a cluster. Finally, outliers are processed.

The Steps of GB Algorithm Are as Follows:

Input: Dataset (record set), Cluster Precision Record I is packaged as a note Put note I into Graph Repeat { Calculate threshold (delta) by function Cut down all the edges whose value is greater than the threshold (delta) Transverse Graph, label all the sub-graphs. Outlier processing } until the outlier is processed completely GB algorithm has been used for clustering for decades. However, it mainly has two shortcomings when it is applied for intrusion detection: the first one is that it distinguishes the normal and abnormal cluster just by a value of threshold. So the clustering accuracy is far from enough. Second, it doesnt offer a reasonable method to address outliers, but it just throws them away. With this coarse granularity partition, it cannot achieve a satisfactory detection rate. On the other hand, the ability to detect any shape of cluster has made it very suitable for the dataset with complex shape from real network.

LDFGB Algorithm for Intrusion Detection

In order to achieve higher detection rate, we further propose an improved graphbased clustering algorithm by using outlier detection method based on local deviation factor in label process. This method mainly focuses on how to classify the data on the boundary to be classified more accurately and then augment the difference between normal and abnormal clusters. Firstly, we define some related definitions:

Definition 1: (Outlier). These can be objects that are outlying relative to their local neighborhoods, particularly with respect to the densities of the neighborhoods. These outliers are regarded as local outliers. (Figure 2) Given the kdistance of p, the k-distance neighborhood of p contains every object whose distance from p is not greater than the k-distance.

N k-distance (p) = {q ∈ D \ {p} |d(p, q) ≤ k -distance (p)}
These objects q are called the k-nearest neighbors of p.

Definition 4: (local deviation rate of an object).

Given the k-distance of p, and p is a center of circle with radius k. All objects in this circle are k-distance neighborhood of p. p is the Centre of mass of this circle. So the local deviation rate is defined to be:

LDR k(p) = dis (p, p ′ ) |N k-distance(p) | (3)
The dis (p, p') is the distance between object p and Centre of mass of p'.

Definition 5: (local deviation influence rate of an object).

Given the kdistance neighborhood of p and LDR, the local deviation influence rate is defined to be:

LDIR k(p) = ∑ LDR k(o) o∈N k-distance |N k-distance(p) | (4)
Definition 6: (local deviation factor of an object). Given LDR and LDIR, local deviation factor is defined to be:

LDF k(p) = LDR k(p) LDIR k(p) (5)
The local deviation factor of object p reflects k-distance neighborhood of object p within the dispersion degree. High value of LDF means higher probability of one object being an outlier; a low LDF value indicates that the density of an objects neighborhood is high. So its hardly to be an outlier.

The Steps of LDF Algorithm Are as Follows:

Step1: implement GB algorithm to cluster dataset and gain n clusters C1, C2...Cn, they are sorted in descending order according to the records they embraced. In this process, CN, CS and CA stand for the set of normal clusters, suspicious clusters and abnormal clusters respectively. CS is the set that need to be processed in next step. In step 3, M is the number of data set and λ1, λ2 (λ1+λ2=1) represent the percentage of normal and anomaly rate. They should meet the premise that the number of normal action is far greater than the number of intrusion action. So their values must satisfy λ1≫λ2. Otherwise, the isolated points were classified in abnormal clusters rather than discard them away. In detecting phase, a new record d, calculate its distance to each data, it will belong to the cluster the same to the data that has nearest distance with it. If the cluster is normal, d is normal. Otherwise, d is an attack.

Experiments And Results

To evaluate the performance of LDFGB approach, a series of experiments was conducted on a 2-dimensional artificial dataset. (Figure 3) to Root and Probing. In the dataset, a record has 7 classified attributes and 34 numeric attributes, and this belongs to the implementation of clustering in high-dimensional space. The In order to improve the detection efficiency of the experiment, we remove the attributes that is useless for this experiment. After careful analysis, we screen 20 properties as the objects of study, such as the lifetime of the TCP, window size and the length of the packet.

We randomly select 10000 samples for training data set. Besides, we randomly select 2500 samples of intrusion which types are different from the training dataset. It is aimed to evaluate ability of this algorithm on detecting unknown attacks. First, we alter the cluster precision of α. The result is shown in Table 2: On Table 2, we observe clearly that the change of cluster number with altering parameter of cluster precision. A relatively large α will lead to small number of clusters. As a result, excessive data would be classified in one large class. And most of the abnormal behaviors cant be detected in this situation. On the other hand, with a small value of α, the partition will generate excessive clusters.

The next step, for the GB model, the best situation is that all data were divided into 9 subsets. So we fixed α= 0.05. To meet the one of premise of anomaly intrusion detection that normal action is far greater than the number of intrusion action, we try the parameter of λ1 and λ2 in (0.9 , 1.0) and (0.0 , 0.1) respectively. Finally, we change the values of parameter K and testing these constructed models by group 3. We find that, when k=9, λ1=0.95 and λ2=0.05, the performance of this algorithm is the best. The output of detection rate and false positive rate showed in Table 3:

The LDC algorithm output of detection rate and false positive rate showed in Table4: We discover the LDFGB algorithm achieves better detection rate than the LDC algorithm. Table 3 and Table 4 show that when there are the same K values, the performance of LDFGB algorithm is superior to the LDC algorithm. The experimental result shows that the parameter K is an important factor for the performance of this algorithm. We should not set a value for K that is too large, because a large K value will cause many isolated points to be classified from normal classes. On the other hand, a relatively small value of K will lead to the most of records have a large LDF value. Therefore, we could not separate the abnormal records from suspicious cluster. Both of these situations would decrease cluster precision. Figure 5 shows that the proposed method always outperforms the LDC method.

Conclusions

Intrusion detection system based on data mining increases the safety and reliability of network. Obviously, by means of clustering method, intrusion detection may be carried out. The LDFGB algorithm presented in this paper may overcome some disadvantages of the traditional cluster algorithm for intrusion detection and can obtain comparative satisfactory performance of intrusion detection. However, there are still many deficiencies that need to be improved. Our further research will focus on how to reduce the complexity of this algorithm because the memory requirement for computation increases dramatically as the number of records grow. Another disadvantage which should be fixed is that the initial percentage of abnormal and normal records need manual control to find the suspicious clusters, it more or less influences performance of this algorithm.

Fig. 1 .

 1 Fig. 1. GB Cluster

Fig. 2 .

 2 Fig. 2. O1 and O2 are outliers

Fig. 3 .

 3 Fig. 3. 2-dimensional dataset and LDF values

Figure 4

 4 Figure 4 shows that the data nodes distributed in two kinds of situations. Similar results are obtained by the LDC algorithm, so the LDC algorithm cant differentiate these kinds of situations. If we use the proposed method (LDFGB Algorithm) by adjusting K values that we can differentiate two situations. So the performance of LDFGB is the better than LDC algorithm. KDDCup99 dataset is a dedicated test dataset established for intrusion detection assessment by Massachusetts Institute of Technology. It contains 24 kinds of attacks categorized into 4 types: Denial of Service, Remote to User, User

Fig. 4 .

 4 Fig. 4. Two kinds of distribution

Fig. 5 .

 5 Fig. 5. The preferment of our method and LDC method

Table 1 . Euclidean distance Id1 Id2 Id3 ...... Idn

 1

	Id1 0 0.81 0.11 ...... 0.02
	Id2 0.81 0 0.45 ...... 0.71
	Id3 0.11 0.45 0 ...... 0.15
	...... ...... ...... ...... ...... ......
	Idn 0.02 0.71 0.15 ...... 0

Table 2 .

 2 Clustering result of GB

	Cluster precision (α) Cluster number(n)
	0.02	21
	0.05	9
	0.20	6
	0.50	4

Table 3 .

 3 The performance of LDFGB

	K Detection rate False positive rate
	5	94.30%	2.26%
	8	96.14%	2.09%
	12	97.25%	2.03%
	15	96.52%	2.13%

Table 4 .

 4 The performance of LDC

	K Detection rate False positive rate
	5	93.30%	2.24%
	8	95.31%	2.08%
	12	92.67%	2.14%
	15	92.00%	2.11%

Acknowledgments

. This research was supported by Next-Generation Information Computing Development Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (2011-0029924).


Jakub Breier
email: jbreier@ntu.edu.sg

Frank Schindler
email: frank.schindler@paneurouni.com

Assets Dependencies Model in Information Security Risk Management

Keywords: Information Security Risk Management, Asset Valuation, Asset Dependency, Risk Analysis

Information security risk management is a fundamental process conducted for the purpose of securing information assets in an organization. It usually involves asset identification and valuation, threat analysis, risk analysis and implementation of countermeasures. A correct asset valuation is a basis for accurate risk analysis, but there is a lack of works describing the valuation process with respect to dependencies among assets. In this work we propose a method for inspecting asset dependencies, based on common security attributes -confidentiality, integrity and availability. Our method should bring more detailed outputs from the risk analysis and therefore make this process more objective.

Introduction

Information systems are subject to various threats that can have undesirable effects on them. As information technologies evolve, threats are more sophisticated and harder to detect. Great volumes of valuable data are stored in information systems that are connected to the Internet and therefore it is necessary to use security techniques for their protection.

Information security risk management [START_REF] Blakley | Information security is information risk management[END_REF] is a fundamental process conducted for the purpose of securing information assets in an organization. It usually involves asset identification and valuation, threat analysis, risk analysis and implementation of countermeasures. There are few standards that deliberate this process and provide recommendations for security specialists in organizations. The most popular are NIST Special Publication 800-39 [START_REF]NIST Special Publication 800-53 Managing Information Security Risk -Organization, Mission, and Information System View[END_REF] and ISO/IEC 27005:2011 standard [START_REF]Information technology Security techniques Information security risk management[END_REF], both provide a high-level overview of the risk management process.

The important part of the risk management process is the asset valuation that, if used properly, will tell us which assets are important for the organization in the meaning of price and necessity in business processes. Works that implement one of these standards usually use simple valuation methods, based on qualitative techniques of measurement. They express value on some discrete scale, consisting mostly of 3 to 5 degrees of precision, for example 'none', 'low', 'medium', or 'high' importance in a meaning of contribution to organization's business processes. Usually, they do not take asset dependencies into consideration, but it can significantly change the results of a risk analysis if two assets are strongly dependent. If is, for example, a storage server in a high risk resulting from its physical placement and the database server running on this physical server has only low level of risk, resulting from risk evaluation, we cannot consider these two entities as independent. The way how dependent are they should be an outcome from asset valuation sub-process.

In this paper we would like to introduce a model for asset valuation that involves inspection of asset dependencies. This inspection is based on examining dependencies from the security attributes point of view -confidentiality, integrity and availability. After evaluation of asset relations we consider risk values, acquired by the preliminary risk assessment, and assign new risk values deliberating the original values and the dependencies.

The rest of this paper is structured as follows. Section 2 provides an overview of a related work dealing with the problem of security risk management techniques with focus on asset dependencies. Section 3 proposes our approach and describes method used for examining dependencies among assets. Finally, section 4 concludes this paper and provides a motivation for further work.

Related Work

There exist a number of works in the field of information security risk management. These works implement mostly the ISO/IEC 27005:2011 standard and use various methods in order to automate this process. They usually follow process structure from the standard and propose own methods based on either quantitative or qualitative assessment techniques. We will examine these works from the asset valuation perspective. Some works do not examine dependencies at all. For example, Vavoulas and Xenakis [START_REF] Vavoulas | A quantitative risk analysis approach for deliberate threats[END_REF] use five dimensions in asset valuation -value, repair cost, reputational damage, operational damage, and legal or regulatory damage. The consequences of an attack are then equal to the sum of these values. Tatar and Karabacak [START_REF] Tatar | An hierarchical asset valuation method for information security risk analysis[END_REF] propose a hierarchy based asset valuation method that express the value in three terms -confidentiality, integrity and availability. Their method is straightforward and needs a security expert to determine these values for each asset. They do not deliberate asset dependence, buying price or operating costs.

Leitner [START_REF] Leitner | Arima -a new approach to implement iso/iec 27005[END_REF] propose his own risk analysis approach called ARiMA (Austrian Risk Management Approach). It uses a configuration management database (CMDB) to identify relevant assets in accordance to the business processes. The assets are classified into five degrees according to the importance for the organization from 'very low' to 'very high'. The corresponding multiplicators that affect the risk value are numbers from 1 to 1.5, with 0.125 granularity. The risks are computed using standard matrices with impact values for the columns and probability values for the rows. The asset dependencies are modelled by using two logical connection types OR and AND that are used in evaluating asset's security attributes -confidentiality, integrity and availability. If OR is used, the values are computed as an average, if AND is used, the highest number among dependent entities is chosen. It is naturally better to implement at least some technique for examining dependencies, but this approach is very simple and does not provide desired complexity for asset analysis.

Loloei, Shahriari and Sadeghi [START_REF] Loloei | A model for asset valuation in security risk analysis regarding assets' dependencies[END_REF] propose an asset valuation model, emphasizing dependencies between assets. They define dependencies in terms of security attributes and divide organization's assets into three layers -business, application and technical layer. They use a value propagation graph to represent how assets affect the value of each other, and how an asset value propagates through other assets. Authors claim that the well-known risk management methodologies, such as CRAMM, OCTAVE, or NIST 800-30 show limitations during risk assessment because of lack of considering dependencies among assets. However, the work is missing comparison between different asset valuation methods, therefore it cannot be decided whether the asset dependencies are modelled correctly and contribute in terms of more precise assessment, or not.

Suh and Han [START_REF] Suh | The is risk analysis based on a business model[END_REF] propose a risk analysis method based on Analytic Hierarchy Process with more detailed view of asset identification and evaluation. They divided this phase into five sub-processes: asset identification, assignment of assets to business functions, determination of initial asset importance, asset dependency identification, and determination of final asset importance. The dependencies are expressed from the view of asset importance. If asset A depends on assets B,C and D, its importance is maximum of importances of these assets. This value can be then revised by a security analyst and can be further adjusted.

Mayer and Fagundes [START_REF] Mayer | A model to assess the maturity level of the risk management process in information security[END_REF] design a model for assessing the maturity model of the risk management process in information security. This model is aimed to identify weaknesses or deficiencies in the risk management and improve its effectiveness. It examines all the processes measuring their quality. From our point of view, the main disadvantage is that the asset analysis is not deliberated as an individual process, just as a sub-process of risk analysis.

Methods

We can examine dependencies among assets on a simplified organization model, depicted in Figure 1. Dependencies are arranged in a tree-based hierarchy, with the building as a top-level node. If the building is destroyed, all the other assets would be lost, if we consider simple model without information backup and alternative information processing facilities in other building(s). As we can see, one entity can be dependent on multiple entities, the Exchange server is dependent both on Physical server 2 and on Active Directory server. If we look at Database server, there is a redundancy -company has one secondary backup server in a case of failure of the primary one. Therefore we have to differentiate a connection between the data stored on these servers.

Model Assumptions

Now we can make following assumptions for our model:

-We can assume that the business goal of our model company is dependent on all the leaves, therefore we need to ensure confidentiality, integrity and availability of all the other components following the hierarchy. We will call this set of entities 'chain of dependence', for example User data in our picture has four entities in its chain of dependence, beginning with AD server and ending with the building. -We have to assign dependency weights for each entity in the chain of dependence. These weights will be then used to adjust the process of a risk analysis -if entity N depends on other entity M that has high level of risk, this risk should be distributed on the entity N. -If we have redundant entities, we will use the 'OR' type of connection. Normal type of connection, 'AND', means that the dependent entity depends exclusively on the superior entity in the hierarchy. The 'OR' connection lowers the risk, distributing it on two or more superior entities. -Weights cannot be represented as a single value, since dependencies can have different character. For example, Customers data depends on Physical server 1 from the availability point of view mainly, but their confidentiality is strongly influenced by the Database server.

We will use 4x4 risk matrix [START_REF] Williams | Software Risk Evaluation (SRE) method description (version 2.0)[END_REF] for demonstrational purposes. This matrix has threat probability for its columns and impact for its rows. We will define following risk values:

in interval [START_REF]NIST Special Publication 800-53 Managing Information Security Risk -Organization, Mission, and Information System View[END_REF][START_REF] Loloei | A model for asset valuation in security risk analysis regarding assets' dependencies[END_REF] as a low risk value, in interval [START_REF] Mayer | A model to assess the maturity level of the risk management process in information security[END_REF][START_REF] Vavoulas | A quantitative risk analysis approach for deliberate threats[END_REF] as a medium risk value, in interval [START_REF] Williams | Software Risk Evaluation (SRE) method description (version 2.0)[END_REF]16] as a high risk value.

It is clear that we cannot assign some of these numbers by using the risk matrix below, but we will need the whole intervals in the latter phase.

Let us assume that we have already made the risk analysis using standard methodology. To save the space we will analyze only part of our model company, risk values for particular elements can be seen in Figure 2. These are the average risk values for threats, we will not examine dependencies among individual threats. Fig. 2. Risk values.

Building

Model Construction

We can now construct our dependency valuation model based on previous assumptions. The valuation process consists of following steps:

1. Begin with the top level entity (building in our example).

2. Assign dependency component weight values of confidentiality (W con ), integrity (W int ) and availability (W ava ) to each relation in the hierarchy. These values are from interval [0,1] with the granularity of 0.1 points. 3. Adjust the risk value by using the dependency adjustment formula. If there is 'OR' connection between entities, compute the average of the adjusted risk values and divide it by the number of redundant entities. If one entity is directly dependent on more than one entity, we have to adjust the risk value considering all of the superior entities. 4. Continue with the lower level entities until the last level in the hierarchy.

We define an overall dependency weight value W o as a sum of component weight values.

W o = i=con,int,ava W i (1)
The dependency adjustment formula, used in step 3, is used for adjusting the risk value by examining dependency weight values:

W o × max(W con , W int , W ava ) × RV (2)
The formula depends on three factors. First, we sum the component weight values and multiply it with the maximal value among components. And finally we multiply this value with the RV , which is the simplified risk value of the upper level entity connected with the dependency relation. If the risk of the asset is low, this value would be 1, if medium, the value is 2 and for the high risk this value is 3. In the Table 1 we can see the example of adjusted risk values. The first asset has low dependency and low risk of the entity on which it depends, in this case the adjustment to the final value would be +1 point. The second asset has medium dependency and medium RV , the original risk will be adjusted by +2.4 points. Finally, we have an asset with high dependency and high RV , so the adjustment in this case will be +7.2 points.

Model Example

We will now examine our method on the provided example. In Figure 3 we can see part of our model company with assigned dependency component weight values. In Table 2 are listed adjusted risk values corresponding to dependency weights. Redundant entities are stated in one row, because their weights are equal. Notice that after the first assignment we take the adjusted risk values as an input, for example when considering Customers Data, we take high risk value of the DB Server as an input, not medium from the original risk assessment. Also notice that Data are adjusted just by +2.1 risk value because of the DB Server redundancy.

Adjusted values in the whole organization model are listed in Figure 4. Building is the only entity that does not depend on any other entity, therefore its risk value remains the same. Minimal adjustments were made to physical servers, after considering dependencies they have +0.4 risk values. Maximal adjustments were made to both Private Data, their values were raised by +4 points. It is because of double dependency on both AD server and Physical server 3.

Conclusions

In this paper we proposed an asset dependency evaluation method that can be used in order to improve results of a risk analysis. Despite the fact that there are not many works dealing with this problem, we find it important to take it in the consideration when assessing risks in an organization. The ISO/IEC 27005:2011 standard [START_REF]Information technology Security techniques Information security risk management[END_REF] recommends to encompass dependencies of assets in the asset analysis process. It suggests to take the degree of dependency and the values of other assets into account. In our work we inspect this degree from the confidentiality, integrity and availability perspective and in-stead of the value, we consider the risk value. The dependency valuation model also deals with the situation of dependency on more than one entity and with the dependency on redundant entities. The final risk value is adjusted with respect to these conditions.

It is easy to include our method into the complex risk analysis process, so that the risk values would be adjusted by the terms of asset dependencies. In the future, we would like to provide the whole risk management evaluation model based on quantitative measurement techniques, that would measure security state in an organization and output meaningful results.

Fig. 1 .

 1 Fig. 1. Dependencies between assets.

Fig. 3 .

 3 Fig. 3. Dependency component weight values.

Fig. 4 .

 4 Fig. 4. Adjusted risks in the whole model.

Table 1 .

 1 Dependency adjustment formula examples.

	Dependent Entity Wo max(Wcon, Wint, Wava) RV Adjustment Value
	Asset 1	0.5	0.2	1	+1
	Asset 2	1.5	0.8	2	+2.4
	Asset 3	2.4	1.0	3	+7.2

Table 2 .

 2 Adjusted risk values.

	Dependent Entity					Wo Wmax Original Risk Val. RV Adjusted Risk Val.
	Server Room							0.8 0.5					5					2			5.8
	Physical Server 1 & 2				0.8 0.5					9					1			9.4
	DB Server & Backup Server 1.3 0.6					9					2			10.56
	Customers Data						2 0.7					12				3			14.1
	Company Data							2 0.7					12				3			14.1
	18
	16
	14
	12
	10
	8
	4 6																							Adjusted Risk
	2																							Original Risk
	0
	Building	Server Room	Open Space	Office 1	Physical Server 1	Physical Server 2	Physical Server 3	Router	Switch	Workstation 1	Employee 1	Workstation 2	CEO	DB Server	Backup DB Server	AD Server	Exchange Server	Application SW	Customers Data	Company Data	User Data	E-mail Data	Private Data 1	Private Data 2