Alessandro Armando
email: armando@fbk.eu

Alessio Merlo
email: alessio.merlo@dist.unige.itluca.verderame@ai-lab.it

Mauro Migliardi
email: mauro.migliardi@unipd.it

Luca Verderame

Would you mind forking this process? A Denial of Service attack on Android (and some countermeasures) ⋆

We present a previously undisclosed vulnerability of Android OS which can be exploited by mounting a Denial-of-Service attack that makes devices become totally unresponsive. We discuss the characteristics of the vulnerability -which affects all versions of Android -and propose two different fixes, each involving little patching implementing a few architectural countermeasures. We also provide experimental evidence of the effectiveness of the exploit as well as of the proposed countermeasures.

A central design point of the Android security architecture is that no application, by default, has permission to perform any operation that would adversely impact other applications, the operating system, or the user.

Introduction

With more than 45% of US sales of smartphones in 3Q2011 [1], Android is arguably one of the greatest success stories of the software industry of the last few years. By leveraging a generic (albeit optimized for limited resource consumption) Linux kernel, Android runs on a wide variety of devices, from low-end to top-notch hardware, and supports the execution of a large number of applications available for download both inside and outside the Android Market. Since most of the applications are developed by third-parties, a key feature of Android is the ability to sandbox applications, with the ultimate objective to achieve the following design goal: Sandboxing is achieved combining the isolation guaranteed by the use of Virtual Machines together with the enforcement mechanism that can be obtained from the Linux access control by giving each application a different Linux identity (i.e. Linux user). Each of these two mechanisms is well known and has been thoroughly tested to achieve a high level of security; however, the interaction between them has not yet been fully explored and may still hide unchecked vulnerabilities.

In this paper we present a previously unknown vulnerability in Android OS that allows a malicious application to force the system to fork an unbounded number of processes and thereby mounting a Denial-of-Service (DoS) attack that makes the device totally unresponsive. Rebooting the device does not necessarily help as a (very) malicious application can make herself launched at boot-time. Thus, our findings show that the aforementioned Android design goal is not met: a malicious application can indeed severely impact all other applications, the operating system, and ultimately the user. To overcome this empasse we propose two solutions, each involving very small changes in the system, that fix the problem. We present experimental results confirming that all versions of Android OS (including the most recent ones, namely versions 4.0 and 4.0.3) suffer from the vulnerability. The experiments also confirm that our proposed fixes counter the DoS attack. We have promptly reported our findings to Google, Android and the US-CERT. The vulnerability has been registered in the CVE database and has been assigned identifier CVE-2011-3918.

Structure of the paper. In the next section we provide a brief description of Android OS. In Section 3 we present the vulnerability and in Section 4 we illustrate two possible solutions. In Section 5 we present some experimental results that confirm the effectiveness of the DoS attack as well as of the proposed countermeasures. In Section 6 we investigate works related to the security of the Android platform. We conclude in Section 7 with some final remarks.

The Android Architecture

The Android Architecture consists of 5 layers. The bottom layer (henceforth the Linux layer ) is the Linux kernel. On top of the Linux layer live four Androidspecific layers that we collectively call the Android layers.

The Android Layers

The Android Layers are from top to bottom: the Application layer, the Application Framework layer, the Android Runtime layer, and the Libraries layer:

-Application Layer. Applications are on the top of the stack and comprise both user and system applications which have been installed and execute on the device.

-Application Framework Layer. The Application Framework provides the main services of the platform that are exposed to applications as a set of APIs. This layer provides the System Server, that is a component containing the main modules for managing the device (e.g. Communication between apps in Android is carried out through Unix sockets or the Binder driver. Sockets are used when data are small and well codified such as in Zygote socket case. In other cases (e.g., when data are big and heterogeneous), the Binder driver is used. Binder IPC mechanism relies on a kernel driver. Each process registers itself to the Binder driver and gets back a file descriptor. A process that wants to communicate with another process can simply send data through the file descriptor via an IOCTL command. The Binder kernel module sends received data directly to the destination process.

Interaction between the Android Layers and the Linux Layer

The interaction between the Android and the Linux layers is depicted in Fig. 1. When an application is launched a startActivity call is sent to the Activity Manager Service, a part of the System Server. The Activity Manager Service determines if the application has already an attached process at the Linux layer or if a new one is needed.The first case happens when an instance of the application has been previously started and it is currently executing in background; thus, the Activity Manager Service gets the corresponding process and brings back the application to foreground. In the latter case, the Activity Manager Service calls Process.start(), a method of the static class android.os.process. This method connects the Activity Manager Service to the Linux layer via the Zygote socket and sends the fork command. The Zygote process has the exclusive right to fork new processes, thus, when Android requires the creation of a new process, the command must be issued to the Zygote process through the Zygote socket. The command sent to the Zygote socket includes the name of the class whose static main method will be invoked to specialize the child process. The System Server uses a standard class (i.e., android.app.ActivityThread) when forking. In this class, a binding operation between the Linux process and an Android application is attempted. If no application is available for binding, the same class asks the Linux layer to kill the process. If the spawning of the new process and the binding operation succeed, the Zygote process returns its child's PID to the Activity Manager Service.

The Zygote socket is owned by root but has permissions 666 (i.e. rw-rw-rw), implying that any Android application can read and write it and hence send commands to the Zygote process. This choice is justified by the need of the process hosting the System Server (whose UID is 1000, it is not by root, nor it belongs to the root group) to request the spawning of new processes. However, this has the side effect to enable any process to ask for a fork. To avoid misuse, the Zygote process enforces a security policy that restricts the execution of the commands received on the Zygote socket. This policy is implemented in the runOnce() function:

The policy prevents from

1. issuing the command that specifies a UID and a GID for the creation of new processes if requestor is not root or System Server (cf. line 3) 2. creating a child process with more capabilities than its parent (cf. line 4), and 3. enabling debug-mode flags and specifying rlimit bound if requestor is not root or the System is not in "factory test mode" (cf. lines 5 and 6).

Moreover, only few limitations are put on the (static) class used to customize the child process. In particular, two checks are performed namely checking whether 1) the class contains a static main() method and 2) it belongs to the System package, which is the only one accepted by the Dalvik System Class loader. Unfortunately, these security checks do not include a proper control of the identity (i.e., UID) of the requestor, therefore allowing each Linux process (and, its bound Android application or service) to send not necessarily legitimate but acceptable in the current Android security framework fork command to the Zygote socket as long as a valid static class is provided. We discovered that by using the System static class com.android.internal. util.WithFramework it is possible to force the Zygote process to fork, generating a dummy process which is kept alive at Linux layer. Such class does not perform any binding operation with an Android application, thus not triggering the removal of unbound new processes as the default android.app.ActivityThread class does.

In this way, all the security policies applied by the Zygote process are bypassed, leading to the building of a persistent Linux process which occupies memory resources in the device.

Thus, by flooding the Zygote socket with such requests, an increasingly large number of dummy processes is built until all the memory resources are exhausted (Fork bomb attack).

The Android layers are unable to notice the generation of dummy processes and, consequently, to intervene. On the other hand, the creation of processes at the Linux is legal and managed directly by the kernel. Thus, none of the involved layers is able to recognize such behavior as malicious.

As soon as the dummy processes consume all the available resources, a safety mechanism reboots the device. Thus, by launching the attack during bootstrapping, it is possible to lock the device into an endless boot-loop, thereby locking the use of the device. Notice that to mount the attack, the malicious application does not require any special permission, therefore it looks harmless to the user upon installation.

Countermeasures

We describe two possible approaches to fix the previously described vulnerability:

1. Zygote process fix. This fix consists of checking whether the fork request to the Zygote process comes from a legal source (at present, only the System Server, although our patch is trivially adaptable to future developments). 2. Zygote socket fix. This fix restricts the permissions on the Zygote socket at the Linux layer.

Checking fork requests inside the Zygote process

As said in Section 3, the Zygote process does not perform any specific check on the identity of the process that requests the fork operation. Nevertheless, the Zygote socket is a Unix Domain socket created during the boot-strap of the Linux system. An important feature of Unix domain sockets is the credential passing mechanism which allows to identify endpoints connected to the socket by means of their PID, UID and GID. This implies that the Zygote process can retrieve the identity (i.e., UID) of the requesting process. The extended policy takes advantage of this feature and applies a new filter based on the UID of the requesting process. In particular, since the process corresponding to the System Server has UID 1000 (statically defined), the extended security policy filters the requests reaching the Zygote socket by accepting only fork requests from UID 1000 and UID 0 (root): void a p p l y F o r k S e c u r i t y P o l i c y ( peer ) { int peerUid = peer . getUid () ; if ( peerUid == 0 || peerUid == Process . SYSTEM_UID ) { // Root or System can send commands Log . d (" ZYGOTE_PATCH " , " root or SS request : ok ") ; } else { Log . d (" ZYGOTE_PATCH " , " user request "+ peerUid + ": blocked ") ; throw new Z y g o t e S e c u r i t y E x c e p t i o n (" user UID " + peerUid + " tries to fork process ") ; } }

We implemented the previous policy by adding this check at the end of the native policy in the runOnce() method of the Zygote process.

Modifying the Linux Permissions of the Zygote socket

The idea is to reduce the Linux permissions for the Zygote socket. Currently, the Zygote socket is owned by root and-as we said above-it has permissions 666. It is possible to modify both the owner (no root) and permissions of Zygote socket from 666 (i.e., rw-rw-rw) to 660 (i.e., rw-rw---). In this way the System Server retains read and write access. We implemented this modification in three steps:

1. Create a new owner for the Zygote socket. We added a new UID (i.e. 9988) in the file android_filesystem_config.h which contains statically assigned UID for Android system services. Then, in the same file we bind an ad hoc user zygote_socket and the new UID.

. Server. Since also the System Server is generated through a fork request to the Zygote process, we modified the parameter of the fork command corresponding to the set of groups the new process belongs to. We added the UID to such set as follows:

... String args [] = { " --setuid =1000" , " --setgid =1000" , " --setgroups =1001 ,1002 ,1003 ,1004 ,1005 ,1006 ,1007 , 1008 ,1009 ,1010 ,1018 ,3001 ,3002 ,3003 , 9988 " , " --capabilities =130104352 ,130104352" , " --runtime -init " , " --nice -name = system_server " , " com . android . server . SystemServer " , }; ... This modification implies that user applications cannot connect to the Zygote socket while the System Server (which is in the Zygote socket's group) can still issue the fork command.

Experimental Results

We tested the DoS vulnerability on all versions of Android OS currently available (i.e. ≤ 4.0.3) by building an Android malicious application (i.e. DoSChecker) as described in Sect. 3. We made tests both on actual and simulated devices. All our tests have produced an unbounded number of dummy processes, thus revealing that all versions suffer from the vulnerability described in this paper.

The Testing Environment. We used a laptop equipped with Android SDK r16. We tested the actual devices listed in Tab. 1; newer Android versions, like 4.0 and 4.0.3, have been tested, instead, on Android device emulator. The behavior of the actual and simulated devices have been traced with Adb Logcat tool and Adb shell via a Windows shell.

Since a DoS is strictly related to the amount of resources, we tested actual devices with heterogeneous hardware in order to assess the relation between the availability of resources and the time spent to accomplish a successful attack.

Exploiting the Vulnerability

Testing with Actual Devices. Once activating the DoSChecker application, devices with limited resources (e.g. LG Optimus One) freeze in less than a minute while others freeze in at most 2 minutes (e.g. Galaxy Tab). Our tests show an almost linear dependence of the duration of the attack from the amount of resources available in the device. During the attack, users experience a progressive reduction of the system responsiveness that ends with the system crash and reboot. While the number of dummy processes increases, Android tries to kill legitimate applications to free resources, but has no access to the dummy processes. This behavior leads to the killing of other application's processes including system processes (such as home process). In several cases also the System Server crashes. Once an application is killed, Android tries to restart it after a variable period of time but, in such scenario, DoSChecker fills the memory just freed with dummy processes, causing the failure of the restart procedure. Once physical resources are exhausted and Android is not able to restarts applications the device is restarted. DoSChecker has the same behavior both on standard and rooted (i.e. devices where non-system software components may temporary acquire root permissions) Android devices.

Testing with Emulated Devices. The use of the Android emulator provided us a twofold opportunity. First, the Android emulator allowed us to check the DoS vulnerability on newer Android versions such as Android 4.0 and 4.0.3; the testing procedure is similar and the experimental result is still the forking of an unbounded number of processes. However, we observed that in the emulated environment, where the amount of available resources depends on the host PC, the amount of dummy processes generated would greatly overcome the hardware capability of any device currently available on market.

Running DoSChecker as a boot service. Since the exploitation of the vulnerability takes to the reboot of the device, we added DoSChecker as a service starting at boot. Such operation is pretty straightforward and it does not require any specific Android permission. In particular, we added a java class in DoSChecker that, acting as a Broadcast receiver, intercepts the system broadcast messages and starts DoSCheck as a service whenever a bootstrap terminates (i.e. when the system broadcast message android.intent.action.BOOT_COMPLETED is received). Our tests show that the exploitation of the vulnerability at boot prevents Android from successfully completing the reboot process, thus getting the mobile device stuck. The only ways to recover the phone in such scenario, are to identify and manually uninstall the malicious application via adb tool or reflashing the device.

Testing the Countermeasures

We implemented the two countermeasures (i.e. Zygote process and Zygote socket fixes) proposed in Sect. 4. In particular, for each Android version, both on the actual and emulated devices, we built two patched versions, each implementing a countermeasure, by recompiling Android from scratch. The building process provides two output images called system.img and ramdisk.img. System.img contains all the Android system classes compiled while ramdisk. img corresponds to the Android RAM disk image which is loaded during bootstrapping and which includes, among others, the init.rc file. The Zygote process fix, which extends the security policy applied by the Zygote process, affects system.img only. The Zygote socket fix, which needs a modification of init.rc, affects both system.img and ramdisk.img.

Our tests show that both countermeasure are effective and prevent the fork of dummy process, thereby solving the vulnerability. Moreover, by using actual devices we have empirically proven that the proper functioning of devices was preserved (i.e. the proposed countermeasures do not affect the normal flow of Android) in all the tested cases.

Related Works

Security on Android platform is quite a new research field. Current literature can be classified into three trends: i) static analysis of Android applications, ii) assessment of Android access control and permissions policies, iii) malware and virus detection. Static analysis is related to the development of white box or black box methodologies for detecting malicious behaviors in Android applications before installing them on the device. To this aim, Enck et al. [START_REF] Enck | A study of android application security[END_REF] executed a horizontal study of Android applications aimed at discovering stealing of personal data. Besides, Fuchs et al. [START_REF] Fuchs | Scandroid: Automated security certification of android applications[END_REF] proposed Scandroid as a tool for automatically reasoning about the security of Android applications. Static analysis could help identifying the calls to the Zygote socket. However, UNIX sockets might be used for legitimated goals and recognizing the specific socket name might be made problematic even with a simple string concatenation.

In any case, to our knowledge no current static analysis tool identifies exploits of the described vulnerability.

The main part of current literature is focused on access control and permissions.

For instance, [START_REF] Porter Felt | Android permissions demystified[END_REF] proposes a methodology for assessing the actual privileges of Android applications. This paper also proposes Stowaway, a tool for detecting over-privilege in compiled Android applications. Nauman et al. [START_REF] Nauman | Apex: extending android permission model and enforcement with user-defined runtime constraints[END_REF] proposes Apex as a policy enforcement framework for Android that allows a user to selectively grant permissions to applications as well as to impose constraints on the usage of resources. A different approach is proposed by Ongtang et all [START_REF] Ongtang | Semantically rich application-centric security in android[END_REF] who present Secure Application INTeraction (SAINT), a modified infrastructure that governs install-time permissions assignment. Other works are focused on issues related to privilege escalation. Bugiel et al. [START_REF] Bugiel | Xmandroid: A new android evolution to mitigate privilege escalation attacks[END_REF] propose XManDroid (eXtended Monitoring on Android), a security framework that extends the native monitoring mechanism of Android to detect privilege escalation attacks. In [START_REF] Davi | Privilege escalation attacks on android[END_REF] authors state that, under proper assumptions, a privilege escalation attack is possible on Android framework. Some research were made on analyzing native Android security policies [START_REF] Chin | Analyzing inter-application communication in Android[END_REF] focusing on possible threats and solutions to mitigate the problem [START_REF] Shabtai | Google android: A state-of-the-art review of security mechanisms[END_REF] of privilege escalation. Nonetheless, the vulnerability disclosed in this paper requires no special permission, thus these approaches are not a valid solution.

Regarding virus and malware detection, Dagon et al. [START_REF] Dagon | Mobile phones as computing devices: The viruses are coming![END_REF] made a comprehensive assessment of the state of the art of mobile viruses and malwares which can affect Android devices. In [START_REF] Di Cerbo | Detection of malicious applications on android os[END_REF] a methodology for mobile forensics analysis in Android environments is proposed. In [START_REF] Burguera | Crowdroid: behavior-based malware detection system for android[END_REF] Crowdroid, a malware detector executing a dynamic analysis of the application behavior, is proposed. Schmidt et al. [START_REF] Schmidt | Static analysis of executables for collaborative malware detection on android[END_REF] inspect Android executables to extract their function calls and compare them with malware executables for classification aim. Specific malware signatures for exploiting the vulnerability described in this paper could be generated, however none is available today. Besides, from a general point of view, all these works have been driven by the need to improve the privacy of the user. In such direction, Zhouc et al. [START_REF] Zhou | Taming information-stealing smartphone applications (on android)[END_REF] argue the need of a new native privacy mode in Android smartphones. At the best of our knowledge, this is the first work related to Denial of Service issues on Android platform. As a final remark, none of the previous works investigates relations and security issues related to interactions between the Android and the Linux layers.

Conclusions

In this paper, we presented a previously undisclosed vulnerability on Android devices which is the first vulnerability on Android that leads to a DoS attack of this severity. We also developed a sample malicious application, (i.e. DoSCheck) which exploits the vulnerabilities, and we proposed two fixes for securing the Android OS against the vulnerability. We reported such vulnerability to Android security team which will include a patch in an upcoming update of the Android OS. Furthermore, we plan to publicly release both DoSCheck code and patched systems in the very near future, accordingly with a responsible disclosure policy we are discussing with Android group and Open Handset Alliance.

Fig. 1 .

 1 Fig. 1. Creation of a new process in Android

1

  boolean runOnce () throws ZygoteInit . M et h od A n dA r gs C a ll er { 2 ... 3 a p p l y U i d S e c u r i t y P o l i c y ( parsedArgs , peer ) 4 a p p l y C a p a b i l i t i e s S e c u r i t y P o l i c y ( parsedArgs , peer ) ; 5 a p p l y D e b u g g e r S e c u r i t y P o l i c y ( parsedArgs ) ; 6 a p p l y R l i m i t S e c u r i t y P o l i c y ( parsedArgs , peer ) ; 7 ...

  Activity Manager and Package Manager ) and for interacting with the underlying Linux drivers (e.g. Telephony Manager and Location Manager that handle the mobile hardware and the GPS module, respectively) -Android Runtime Layer. This layer comprises the Dalvik virtual machine, the Android's runtime's core component, specifically optimized for efficient concurrent execution of disjoint VMs in a resource constrained environment. The Dalvik VM executes application files in the Dalvik Executable (.dex) format which is optimized for minimal memory footprint. -Libraries Layer. The Libraries layer contains a set of C/C++ libraries providing useful tools to the upper layers. They are widely used by Application framework services. Examples of libreries are bionic libc (a customized implementation of libc for Android) and SQL lite.

	2.2 The Linux Layer
	Android relies on Linux kernel version 2.6 for core system services. Such services
	include process management and Inter-Process Communication (IPC). Each An-
	droid application, together with the corresponding Dalvik VM, is bound to a
	separate Linux process. Android uses a specific process, called Zygote, to enable
	code sharing across VM instances and to provide fast start-up for new processes.
	The Zygote process is created during Linux boot-strap. Every time a new Linux
	process is required (e.g., for starting a new Android application), a command
	is sent through a special Unix domain socket called Zygote socket. The Zygote
	process listens for incoming commands on the Zygote socket and generates a new
	process by forking itself as a Linux process. Differently from what happens in a
	normal Unix system, specialization of the child process behavior is not obtained
	by loading a new executable image, but only by loading the Java classes of the
	specific application inside the VM.

  Include the UID of the Zygote socket owner in the group list of the System

	service zygote / system / bin / app_process -Xzygote /
	system / bin --zygote --start -system -server
	socket zygote stream 660 zygote_socket zygote_socket
	onrestart write / sys / android_power / request_state
	wake
	onrestart write / sys / power / state on
	onrestart restart media
	onrestart restart netd
	3.
	..
	#define AID_ZYGSOCKET 9988 / Zygote socket UID;
	# define AID_MISC 9998 /* access to misc storage */
	# define AID_NOBODY 9999
	# define AID_APP 10000 /* first user app */
	...
	static struct android_id_info android_ids [] = {
	{ " root " ,	AID_ROOT , } ,
	{ " system " ,	AID_SYSTEM , } ,
	...
	{ " misc " ,	AID_MISC , } ,
	{ "zygote_socket", AID_ZYGSOCKET, },
	{ " nobody " ,	AID_NOBODY , } ,
	};
	...
	2. Change the owner and permissions of the Zygote socket. The user zygo-
	te_socket is associated with the Zygote socket by modifying init.rc and
	by setting its permissions to 660.

Table 1 .

 1 Actual devices used in experiments.

	Device Model	Android Versions
	Lg Optimus One p550	2.2.3, 2.2.4 (stock LG), 2.2.4 (rooted)
	Samsung Galaxy S	2.3.4 (stock Samsung), 2.3.7 (rooted Cyanogen 7)
	Samsung Next GT-S5570 2.3.4 (stock Samsung), 2.3.4
	Samsung Galaxy Tab 7.1 3.1 (stock Samsung), 3.1 (rooted)
	HTC Desire HD	2.3.2 (stock HTC), 2.3.2 (rooted)

⋆ This work has been partially founded by EU project FP7-257876 SPaCIoS.


Hyundo Park
email: hyundo95@korea.ac.kr

Sung-Oh David

Heejo Lee

Hoh Peter

Cyber Weather Forecasting: Forecasting Unknown Internet Worms Using Randomness Analysis ⋆

Keywords: Forecasting, Internet worm, Randomness check, Regression analysis, Reliability check

Since early responses are crucial to reduce the damage from unknown Internet attacks, our first consideration while developing a defense mechanism can be on time efficiency and observing (and predicting) the change of network statuses, even at the sacrifice of accuracy. In the recent security field, it is an earnest desire that a new mechanism to predict unknown future Internet attacks needs to be developed. This motivates us to study forecasting toward future Internet atacks, which is referred to as CWF (Cyber Weather Forecasting). In this paper, in order to show that the principle of CWF can be realized in the real-world, we propose a forecasting mechanism called FORE (FOrecasting using REgression analysis) through the real-time analysis of the randomness in the network traffic. FORE responds against unknown worms 1.8 times faster than the early detection mechanism, named ADUR (Anomaly Detection Using Randomness check), that can detect the worm when only one percent of total number of vulnerable hosts are infected. Furthermore, FORE can give us timely information about the process of the change of the current network situation. Evaluation results demonstrate the prediction efficiency of the proposed mechanism, including the ability to predict worm behaviors starting from 0.03 percent infection. To our best knowledge, this is the first study to achieve the prediction of future Internet attacks.

Introduction

In the recently security field, various intelligent Internet attacks are being developed and they cause fatal damages on the Internet. In cases of previous fatal Internet incidents, we experienced that an Internet worm has an extremely high destructive force and devastates the Internet. Since the destructive power of a worm is caused by its propagation speed, faster worm propagation techniques have been used in an Internet attack. For example, when a bot master constructs a botnet with compromising other hosts, a bot master can use a worm propagation technique. As a result, it is crucial to cope with a worm at an early stage of a worm propagation.

So far, many researchers have been made a commitment to develop worm detection approaches. Though their efforts, we can decide whether our network is under a worm propagation situation or not. In general, approaches to detect a worm are classified into two categories: signature based and anomaly based. In general, a signature based worm detection approach is widely used on most systems. The reason is that these approaches have the advantage of low falsepositive rates. However, they cannot handle an unknown worm properly. Unlike a signature based worm detection approach, an anomaly based worm detection approach detects an unknown worm [START_REF] Berk | Flowscan: Using sensor networks and data fusion for early detection of active worms[END_REF][START_REF] Jung | Fast portscan detection using sequential hypothesis testing[END_REF][START_REF] Leckie | A probabilistic approach to detecting network scans[END_REF][START_REF] Park | Is early warning of an imminent worm epidemic possible[END_REF][START_REF] Park | Detecting unknown worms using randomness check[END_REF][START_REF] Tong | A novel anomaly detection algorithm and prewarning technology of unknown worms[END_REF][START_REF] Whyte | DNS-based detection of scanning worms in an enterprise network[END_REF][START_REF] Whyte | ARP-based detection of scanning worms within an enterprise network[END_REF]. They enable us to recognize even an unknown attack by examining the network situation whether it is normal or not. In order to do that, the most of detection approaches evaluate particular metrics as numeric values, representing the network situation. Unfortunately, when the worm just began its existence on the Internet, most anomaly worm detection approaches cannot detect it because they need at least a certain amount of attack traffic to decide whether the network situation satisfies the condition of an abnormal network situation or not. Moreover, the result of an anomaly detection mechanism is based on a binary decision, 'true' or 'false' (whether the network is under an attack or not). With the only result of an anomaly detection approach, we cannot observe the changing process of the network situation under a worm propagation. Observing the change of the network situation, from being benign to being a worm propagation recognized by an anomaly detection approach, will be very useful to cope with a worm. In other words, if we can observe the process of the change of the network situation before recognizing as a worm propagation (e.g., after one hour, the situation will turn out to be in worm propagation), it will be very useful to cope with a worm distinctly.

The concept of forecasting is to estimate future statuses by examining and analyzing current information [START_REF]InvestorWords.com: What is forecast? definition and meaning[END_REF]. There are several examples of forecasting such as a sales/stock forecasting in the business or a weather forecasting in the meteorology. Thus, we have a hypothesis that forecasting future statuses of the network situation by analyzing the current status of the network situation can be accomplishable. Forecasting future trends of the network situation is the concept of CWF (Cyber Weather Forecasting). If we analyze current trends of a worm propagation, we can estimate future trends of a worm propagation. The reason is that the number of infected hosts and attack packets generated by them is continuously increased but not decreased as time passes, as shown in cases of Cod-Red and Slammer [START_REF] Chen | Modeling the spread of active worms[END_REF][START_REF] Staniford | How to own the internet in your spare time[END_REF][START_REF] Wu | An effient architecture and algorithm for detecting worms with various scan techniques[END_REF][START_REF] Zou | The monitoring and early detection of internet worms[END_REF]. In their studies, we divide the process of a worm propagation into three stages as follows;

-SP (Starting Point): this stage is very early stage of a worm propagation and the symptom caused by a worm propagation is a subtle sign. -PS (Processing Stage): a worm propagation is in progress and the symptom caused by a worm propagation is getting clearer but it is still a subtle sign.

-DP (Detection-decision Point): the symptom caused by a worm propagation is clear enough to recognize a worm propagation situation by an anomaly worm detection approach.

Fig. 1 shows that ADUR (Anomaly Detection Using Randomness check), proposed by Park et al. as one of early worm detection approaches based on the threshold, detects the worm at an early stage of the worm propagation [START_REF] Park | Is early warning of an imminent worm epidemic possible[END_REF][START_REF] Park | Detecting unknown worms using randomness check[END_REF]. In Fig. 1, the worm propagation is based on the AAWP (the Analytical Active Worm Propagation) model, one of the popular models for the Internet scale worm propagation [START_REF] Chen | Modeling the spread of active worms[END_REF]. As shown in Fig. 1, ADUR has three phases (SP, PS and DP ) under a worm propagation. It is pretty much the same as other worm detection approaches based on the threshold. In Fig. 1, the rank value, estimated from ADUR, is maintained in low values under the benign network situation or the very early worm propagation stage (before SP ). But the symptom of a worm propagation becomes clearer under PS (after SP until DP ) and the value increases more and more. Finally, when the symptom caused by a worm propagation becomes clear, the value goes over the threshold at DP. When our network situation is under SP or PS, DP will be the future network situation. Nevertheless, CWF forecasts DP with analyzing the current trend of the change of the network traffic under PS. To forecast DP, CWF decides whether the current network situation is SP or not. If our network situation is SP, our network situation turns to PS and CWF forecasts DP with the time from the current time until DP as shown in Fig. 1. In Fig. 1, at time t 1 , the current network situation is SP and the CWF forecasts the future network situation with ∆t = t 2 -t 1 . As time passed, t 1 will be closed to t 2 and CWF still forecasts with ∆t until DP.

In this paper, we propose a new conceptual model of CWF, and we show that CWF can be realized in the real-world with applying statistical theories. To show that CWF can be accomplished in the real-world, we provide the value, the prediction of attack situation by analyzing the values taken from ADUR. The evaluation results of our forecasting approach, called FORE (Forecasting using REgression analysis), show that FORE can predict the Internet worm 1.8 times faster than ADUR does, irrespective of the number of vulnerable hosts or the worm scan rate. Furthermore, FORE continuously forecasts ∆t under PS. This result shows that predicting and alerting an unknown attack is possible and this predicted information will be invaluable for a security agencies.

This paper is organized as follows. In Section 2, we give an in-depth account of CWF. In Section 3 and Section 4, we explain the ADUR and FORE mechanism. Section 5 demonstrates the effectiveness of the FORE with the evaluation results. Finally, we conclude with a summary of contribution and discuss future works.

Cyber Weather Forecasting

In this paper, to help us better understand CWF, we explain the limited CWF within which predicts a worm propagation.

We can get information of a current network situation related to a worm propagation using an early worm detection mechanism. Nevertheless, we always have curiosities toward the future network situation, such like how and when the current network situation will be changed to the worm propagation network situation in the future. Unfortunately, since most early worm detection mechanisms merely estimate the network situation with the binary decision, such as 'true' or 'false', we cannot investigate how the network situation is being changed during the period from triggering the worm propagation to detecting it. As a result, developing the new model which can continuously report a possibility of the worm epidemic before when the early worm detection mechanism detects the worm is earnestly desirable, even at the sacrifice of accuracy.

In order to satisfy our desires, we propose the model of CWF in this paper. CWF is the conceptual model that forecasts the change of the future network situation. CWF forecasts when the current situation will be clearly changed to the worm epidemic situation and reports the changing process of the network situation during the period from triggering the worm to detecting it. Therefore, CWF helps us to get the information of the future network situations (reporting the trend of worm propagation under PS and forecasting the time of DP with ∆t)

In the view points of forecasting the future Internet worm, Nazario et al. proposed a mathematical model for a vulnerability's "wormability", the potential for the use of the vulnerability in worm propagation [START_REF] Nazario | Wormability: A description for vulnerabilities[END_REF]. The model provides time intervals between the publication of the vulnerability and the current time; and the model measures the possibility of several vulnerability announcements in the near future along with explanations of why some vulnerabilities are inherently not "wormable". On the other hand, Sanguanpong et al. proposed the approach to minimize the damage due to worm infection in enterprise networks [START_REF] Sanguanpong | Worm damage minimization in enterprise networks[END_REF]. The authors predict the number of infected nodes by fuzzy decision, thus benefiting to the study of worm behaviors.

Unfortunately, these studies cannot be included in CWF. Since previous studies predict the worm propagation using theoretic models, related to previous worm trends and worm propagation behaviors, and it is absolutely impossible to find the point when the unknown worm propagation will be triggered on the Internet, these studies are useful in analyzing already known worms only.

To realize CWF in the real-world, two types of information which are used to predict the worm should be reported to us as follows:

-BP (Branch Point) : reporting the starting time of forecasting the worm (i.e., SP ). -RT (Remaining Time) : reporting the remaining time from the current to the future worm epidemic situation (i.e., ∆t).

In Fig. 1, if the worm propagation is triggered on the Internet, CWF senses the change of the network situation with the tiny symptom of the worm propagation, even at the sacrifice of accuracy. Thus, CWF reports BP (as SP ) and RT (as ∆t)

ADUR (Anomaly Detection using Randomness check) : The Context

Since we propose a forecasting model called FORE which analyzes the randomness of the network traffic, we first explain ADUR in concrete. ADUR, proposed by Park et al. [START_REF] Park | Is early warning of an imminent worm epidemic possible[END_REF][START_REF] Park | Detecting unknown worms using randomness check[END_REF], is the anomaly worm detection mechanism using randomness checks of the network traffic. In order to do that, ADUR uses the matrix operation after constructing the traffic matrix. In order to check the randomness of the network traffic, ADUR uses the well-known binary matrix rank test, proposed by Marsaglia et al. [START_REF] Marsaglia | Diehard: a battery of tests of randomness[END_REF][START_REF] Marsaglia | Matrices and the structure of random number sequences[END_REF].

Since one prominent characteristic of Internet worms is a random selection of subsequent targets, ADUR examines the random distribution of destination addresses in the network traffic. ADUR consists of four steps: 1) traffic matrix construction, 2) XOR operation, 3) rank calculation, and 4) randomness checkup. In order to obtain more accurate attack information such as a randomness of either entering or departing worm traffic from the network, ADUR classifies traffic data into two categories based on their direction: incoming and outgoing. ADUR constructs the traffic matrix, a binary square matrix, to check a randomness of traffic, because checking for randomness of a binary square matrix is easily accomplished by measuring the rank of the matrix. As well, ADUR uses a XOR operation to diminish the effect of normal traffic on rank values.

First, ADUR constructs the traffic matrix as Fig. 2. To represent the traffic information (the binary information of third and fourth octets of IP address) on the traffic matrix, ADUR finds the location, i and j of the traffic matrix, with the fourth octet of IP address of a packet and overwrites the binary information of third and fourth of octets of IP address of a packet on the submatrix (4×4) in the traffic matrix (64×64). As a result, a randomness of traffic can be properly expressed on the matrix. In previous works, ADUR considers the network environment as IPv4 when ADUR constructs the traffic matrix. To apply ADUR to the IPv6 network environment, we should adopt a new method to find the location, i and j of the traffic matrix, and the function to find the location should satisfy three conditions (it should be easy to compute the index for any given IP address, difficult to find an IP address that maps to a given index value, and difficult to spoof the IP address without the index value being changed). As a result, under the IPv6 network environment, we can adopt a cryptographic hash function to find the location. In this paper, we consider the network environment as IPv4.

Second, since the legitimate traffic can reduce accuracy of the worm detection, a simple XOR operation is very efficiently used to remove the legitimate traffic on the traffic matrix.

R(M

′ t ) = R(M t ⊕ M t-1 ) (1)
where M t is the traffic matrix at time t. Eq. ( 1) presents the XOR operation on a sequence of matrices. Let M ′ t denote the result of the XOR operation of two consecutive matrices, M t and M t-1 . Then, the XOR operation eventually removes most of legitimate traffic in the traffic matrix M ′ t because legitimate traffic lives longer than one time unit so the portion of legitimate traffic is eliminated by the XOR operation. This effectiveness of the XOR operation will be constant even when the network state goes the busy state (such like the traffic volume increases highly) caused by huge legitimate users (flash crowds) [START_REF] Park | Distinguishing FE and DDoS using randomness check[END_REF].

Third, the common dimension of the row space and the column space of a matrix is called the rank. A straightforward method to compute a rank of a matrix is to count the number of non-zero rows after applying the Gaussian elimination to the matrix. The rank of the matrix is equal to the number of nonzero rows (or equivalently, the number of leading 1's) on the matrix. In Eq. ( 1), R(M ′ t ) is the rank value of M ′ t . Finally, when the worm propagates on the Internet, the traffic has randomness. Thus, ADUR detects the worm with the rank value of the traffic matrix. The rank value of the 64×64 random matrix exceeds 60 with the probability which is greater then 99.999%. This implies that, if the 64×64 binary matrix is a random matrix then the rank has a high probability of being greater than 60. To summarize, the rank of the matrix can be used to determine the randomness of distribution of the elements on the matrix. This 64×64 matrix will undoubtedly be used when a /24 network is monitored [START_REF] Park | Detecting unknown worms using randomness check[END_REF]. When we monitor the network larger than a /24 network, we should enlarge the size of matrix [START_REF] Park | Is early warning of an imminent worm epidemic possible[END_REF]. However, in this paper, we use a 64×64 binary matrix as early research to predict unknown worms.

ADUR effectively detects the Internet worm at an early stage of worm propagation. It is shown that ADUR is highly sensitive so that the worm epidemic can be detectable quickly, e.g. three times earlier than the infection of 90% vulnerable hosts [START_REF] Park | Is early warning of an imminent worm epidemic possible[END_REF][START_REF] Park | Detecting unknown worms using randomness check[END_REF] which is evaluated from AAWP model [START_REF] Chen | Modeling the spread of active worms[END_REF]. And when ADUR detects the worm epidemic, the number of infected hosts was only one percent of the total number of vulnerable hosts. It means that ADUR can detect the worm epidemic before the fast spread phase of the worm propagation, represented by Zou et al. [START_REF] Zou | The monitoring and early detection of internet worms[END_REF].

FORE (FOrecasting using REgression analysis) : The Proposed Model

Here we propose a forecasting model called FORE. FORE finds BP when the worm emerges from the Internet and predicts RT. FORE consists of three steps: 1) time series analysis, 2) linear regression analysis, and 3) reliability analysis. In these three steps, step 1) and step 2) are used to estimate RT, and step 3) is used to find BP. FORE does not use out-rank values (of out-coming traffic matrix of ADUR) but in-rank values (of in-coming traffic matrix of ADUR) because out-rank values are only useful to detect the worms originating from the monitored network.

Time Series Analysis

In time series analysis, a moving average can be used for smoothing the scattered in-rank data. Eq. ( 2) shows the moving average of rank values

Ri =   i ∑ j=i-t R j   /t (2)
where R i , t, and Ri are the in-rank value at time i, the time interval to calculate average, and the average of in-rank values from it to i, respectively.

Linear Regression Analysis

Linear regression analysis yields the equation of the fitted line of the in-rank values of the incoming traffic matrix. As seen in Eq. ( 3), the equation is used to predict RT. The best feature of worm propagation behavior is that the number of infected hosts does not decrease but increases in case that the self-propagation worm spreads over the Internet [START_REF] Chen | Modeling the spread of active worms[END_REF][START_REF] Staniford | How to own the internet in your spare time[END_REF][START_REF] Wu | An effient architecture and algorithm for detecting worms with various scan techniques[END_REF][START_REF] Zou | The monitoring and early detection of internet worms[END_REF]. Therefore, the equation of the fitted line of the in-rank values is used for calculating the in-rank values at a specific time and vice versa.

R i = α + βT i (3)
where R i and T i are the in-rank value at time tick i, and the time at i, respectively.

β =   i ∑ j=i-t ( R j - R) ( T j - T )   /   i ∑ j=i-t T j - T   (4)
α = R -βT i (5)
where R and T are an average of results of the moving average of in-rank values on time interval t and the average of time on time interval t, respectively. We can get α and β using Eq. ( 5) and Eq. ( 4) at time tick i. With Eq. ( 3) based on α and β, FORE predicts when the rank value goes over the threshold. In this paper, since the threshold of ADUR is 60, R i of Eq. ( 3) will be 60 so FORE can forecast RT (as the value of ∆t = T i -t i where t i is the current time).

Reliability Analysis

In the reliability analysis, the coefficient of determination measures the reliability of the equation of the fitted line, and measuring the reliability represents the trust level of predicting the detection decision point when ADUR detects the worm. Added to that, the reliability is used to find the BP to start predicting the worm.

C i =   i ∑ j=i-t ( R j - R) 2   /   i ∑ j=i-t ( R j - R) 2   (6)
where C i and R i are the reliability of the fitted line and the in-rank value on the fitted line after applying the moving average of original in-rank values, respectively. As shown in Fig. 3, in Stage 1 (before BP ), since rank values merely oscillate, the reliability of the similarity between the fitted line (obtained using Eq. ( 3)) and in-rank values is very low (not over 0.8 as shown in Fig. 3). In contrast, in Stage 2 (during PS ), since the number of infected hosts and attack packets generated by the worm is continuously increased but not decreased as time passes, the reliability of the similarity between the fitted line and in-rank values is very high (over 0.8 as shown in Fig. 3). According to this phenomenon, FORE finds BP using this difference among the reliability values (as C i in Eq. ( 6)). All these analyses are performed using the in-rank values within the contiguous time interval; the time interval exists between the previous time and the current time. The previous time must be continuously selected while reflecting network environment.

In this section, first, FORE decides whether the current time is BP or not using the reliability analysis. If the current time is BP, FORE finds the fitted line and predicts RT using regression analysis. In the following section, we show evaluation results of FORE where FORE predicts the worm effectively. Thus, it will be confirmed that CWF can be accomplishable.

Evaluation Results

FORE is evaluated using the real worm traffic by generating as many as the number of infected hosts, being estimated using the AAWP model. In the model, it is assumed that the number of vulnerable hosts is one million, and the monitored network is a /24 network. In order to evaluate the efficiency and reliability of FORE, time-series analysis and regression analysis are employed using real traffic dump data; and the data is comprised of packets captured on the backbone of a university campus network in July 29, 2004, a /16 campus network traffic trace where the average number of clients and packets per second are 132 and 1,847 during the time spam of 187 seconds. And the most busy /24 network trace for background traffic is used to evaluate FORE during 180 seconds. The -Stage 1 : from the start time to BP (i.e., before SP in Fig. 1) -Stage 2 : from the branch point to DP (i.e., during PS in Fig. 1) -Stage 3 : after DP (i.e., after DP in Fig. 1) FORE estimates in-rank values using reliability analysis. As a result, FORE senses the tiny change of the network traffic by the worm, and decides the end of the Stage 1 and the start of the Stage 2 with BP which is drown by the reliability analysis. Following the start of the Stage 2, ADUR checks whether the in-rank value goes over the threshold or not. If the in-rank value goes over the threshold, ADUR decides the end of the Stage 2 and the start of the Stage 3 using randomness checks. In our evaluations, the threshold of reliability is 0.8 drown by experimental results. As shown in Fig. 3, FORE decides whether the current network situation is BP (as SP in Fig. 1) or not.

Fig. 4 plots in-rank values of ADUR, results after applying the moving average to in-rank values of ADUR, and remaining time values estimated by FORE. In Fig. 4, 'Predicted time by a regression analysis' shows the trajectory of the predicted RT as time passes. Since the moving average requires a contiguous time period (as 10 seconds in Fig. 4) to calculate the average of in-rank values, RT value does not present the correct RT at the early stage of Stage 2. But, after the early stage of Stage 2 (as after 63 time tick in Fig. 4), RT presents a correct value.

In Fig. 4, FORE starts to predict RT when only 0.03 percent of the total vulnerable hosts are infected. At this time, the number of infected hosts is merely 306 of the total number of vulnerable hosts. Furthermore, ADUR detects the worm when 1 percent of total vulnerable hosts are infected. In the same manner, the number of infected hosts is 10306 of total vulnerable hosts when ADUR detects the worm. Fig. 5 shows the FORE's sensitivity, measured under the worm spreading state which is generated by AAWP model, where T 1 , T 2 , s, and N are BP by FORE, DP by ADUR, the worm scan rate per second, and the number of vulnerable hosts on the Internet, respectively. In Fig. 5, the faster the worm scan rate, the higher sensitivity FORE has. Likewise, the smaller the number of vulnerable hosts make FORE more sensitive. Fig. 5 shows that FORE predicts the Internet worm 1.8 times faster than ADUR does, irrespective of the number of vulnerable hosts or the worm scan rate.

Conclusions

For the purpose of realizing CWF, the FORE mechanism is proposed and evaluated for predicting worm epidemics with analyzing dynamics of a randomness in the network traffic. The evaluation results show that FORE responds 1.8 times faster than the early detection mechanism (e.g., ADUR) against unknown worms. As these results address, this study shows the incorporation of forecasting into the detection of unknown worms (e.g., zero-day worms). Furthermore, using FORE, we can observe the change of network situation before when the early detection mechanism (e.g., ADUR) detects the worm propagation situation with binary decision, 'true' or 'false'. To the best of our knowledge, this is a new direction to predict the future worm epidemics based on the current state of the monitored network traffic. In addition to the worm prediction, we are sure that FORE can be applied to predict other Internet attacks, the attack changes the situation of the network traffic with time, unlike a normal network

Fig. 1 .

 1 Fig. 1. Three phases of an early worm detection mechanism; Starting Point, Processing Stage and Detection-decision Point.

Fig. 2 .

 2 Fig. 2. Constructing matrix M by mapping a packet to submatrix m.

Fig. 3 .

 3 Fig.3. The estimated branch point using reliability analysis.

Fig. 4 .

 4 Fig. 4. Trajectory of the remaining time predicted by FORE.

Fig. 5 .

 5 Fig. 5. Comparison of the sensitivity of FORE comparing with ADUR.

situation. And if the attack detection mechanism estimates the network situation with the value and the threshold, we are sure that FORE can be applicable for predicting future attacks in an earlier stage than any detection mechanism.

⋆ This work was partially supported by Seoul City R&BD program WR080951 and the National Research Foundation of Korea (NRF) grant funded by the Korean government (MEST) (2009-0086140)


Nineta Polemi
email: dpolemi@unipi.gr

Theodoros Ntouskas
email: tdouskas@unipi.gr

Open Issues and Proposals in the IT Security Management

Keywords: Security Management, Commercial Ports, Maritime environment, Critical Infrastructures, Collaboration, S-PORT project

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

Introduction

The tragic accident of Titanic (1912) imposed the new concept of "safety" in the maritime sector and numerous legislations and directives are published since then concentrating in the physical protection of the ships, crew, passengers, cargo and sea. The terrorist events in New York and Washington (2001), Madrid (2004), and London (2005) imposed the concept of "security" in the maritime sector with additional directives and legislation (e.g. IMO / ISPS) in order to avoid such malicious acts. However these new efforts concentrated on the organizational and auditing aspects of physical security of the ships, maritime companies and the commercial ports; they did not consider the IT and cyber security aspects of the maritime environment.

In this paper we will concentrate on the ports and specifically on the security management of Ports' Information and Telecommunication (PIT) systems. The gaps and barriers of the existing security management maritime related legislation, methodologies and tools in the PITs will be presented at this paper. Proposals will be provided that have been partially presented in [START_REF]ENISA: workshop on cyber security aspects in the maritime sector[END_REF], [START_REF]S-PORT Deliverable 1.2: State of the art and user requirements in the Port Information and Telecommunication (PIT) Systems Security[END_REF], [START_REF] Ntouskas | Collaborative security management services for port information systems[END_REF], [START_REF] Polemi | Security management of the ports' information systems[END_REF] by the authors.

Existing efforts and open issues

The maritime environment is a complex one, as shown in Figure 1, involving and interacting with many entities including ports, ships (with passengers, crew, cargo), port authorities, maritime and insurance companies, customs, shipindustry, banks, ministries, other commercial providers, other critical infrastructures (e.g. railroads, airports) hosting and interacting with complex, heterogeneous Information and Telecommunication (IT) Systems. Commercial ports, are the central entities in the maritime environment and among the transportation critical infrastructures [START_REF] Brunner | International CIIP Handbook 2008/2009: An Inventory of 25 National and 7 International Critical Infrastructure Protection Policies[END_REF] since they are large-scale infra-structures that their degradation, interruption or impairment of their IT Systems has serious consequences on national security, health, safety, economy and welfare of citizens and nations characterized with multiplicity of interdependencies between them and the other entities in the maritime environment. The Ports Information and Telecommunication (PIT) systems consist (as all IT systems) of the following seven [START_REF] Karantjias | An innovative platform architecture for complex secure e/m government services[END_REF] consecutive layers: Infrastructure (e.g. buildings, platforms, servers, stationary / mobile terminals, nautilus systems, databases); Telecom Systems (e.g. networks equipment, satellites, Geographic Information Systems -GIS); Software and Manuals (e.g. identification, maritime, navigation, routing software, Enterprise Resource Planning -ERPs, ticketing); Information and electronic data (e.g. marine and coastal data, trade data); Services (e.g. invoicing, navigation, luggage/cargo management, logistics, e-health); Other equipment (e.g. fire alarm systems, cameras); Users: a. internal users (e.g. administrators, personnel), external users (e.g. port authorities, maritime companies, customs, insurance companies, IT and commercial provides), objects (e.g. ships, crew cargo, luggage, vehicles).

However the existing maritime security standards, methodologies and tools concentrate only on the physical security of the ports (safety) especially in the access control of the ports' infrastructures in relation to the safety of the ships. They consider only the first and the last layer of the PIT system and only the two last components (access control, availability) of security ignoring all its other layers and components making ports as weak security links.

To be more specific, as it has been described in [START_REF] Polemi | Security management of the ports' information systems[END_REF] and [START_REF] Ntouskas | Collaborative security management services for port information systems[END_REF], the various maritime standardization bodies (e.g. IMO, EMSA, EASA, TEN-T EA) do not include in their memorandum IT/cyber security. Similarly, existing risk assessment methodologies for ports (e.g. MSRAM, MARISA, CMA) only detect safety risks and not IT risks.

Furthermore they do not consider the threats rising from the interdependency of the ports with the other ports or other critical infrastructures (e.g. railways) which may cause cascading effects. They do not examine the PIT security independently but with relation to ships' safety. The implementation of the safety directive IMO/ISPS is left at national level i.e. there is not a standard providing the exact procedures and measures that need to be undertaken (e.g. like the ISO27002) in order for a port to become IMO/ISPS compatible. Finally all maritime security management methodologies are not user centric; they consider the user as a passively involved entity that needs to follow the methodology with no interaction or collaboration.

Proposals for enhancing maritime IT security management

A proposed solution to better address the PIT security is to combine the IMO / ISPS with common IT security management standards. However the well known security management standards from the standardization bodies NIST [START_REF]Risk management guide for information technology systems[END_REF] and ISO ([4], [START_REF]Information technology -security techniques -code of practice for information security management[END_REF], [START_REF]Information technology -security techniques -information security risk management[END_REF]) will need further modifications in order to adapt to the port IT security so they can address specific sectoral threats, i.e. interdependent threats rising from all entities in the maritime environment (see Fig. 1), specific threats (e.g. weather conditions, strikes) and maritime legislation (e.g. IMO/ISPS). Well known security management methodologies (e.g. OCTAVE, CRAMM, MAGERIT, MEHARI, COBIT) [START_REF] Polemi | Security management of the ports' information systems[END_REF], [START_REF] Ntouskas | Collaborative security management services for port information systems[END_REF] which have been successfully applied in various environments (e.g. health, business) they may be useful in ports' environments with appropriate adoptions. Furthermore we need to consider the fact that ports are critical infrastructures (CIs) and we need to take into account the known legislation, recommendations and standards for CIs. Most of these standards are from the energy sector and more specifically from the U.S. Department of Energy, North American Reliability Corporation (NERC) [9] and the USA national program National Infrastructure Protection Plan [25]. There is not a standardized way in examining the criticality of an infrastructure or/and addressing cyber threats.

Commercial Ports belong in the special category of transportation CIs [START_REF]Critical infrastructure and key resources sector-specifc plan as input to the national infrastructure protection plan[END_REF]. The various security management efforts [START_REF] Theoharidou | Securing transportation-critical infrastructures: Trends and perspectives[END_REF], found in this sector-specific, focus on the physical security of the transportation means (targeted to railways), on material transportation and assessment of hazardous material. These security management methodologies for the CIs are at national level and use different impact assessment criteria (e.g. economic, public, health & safety, psychological / social / public confidence, complexity, environmental, business, national / territorial security). These methodologies may be used in the ports with appropriate modifications.

A holistic approach to security management of the PIT systems that the authors propose is the creation / enhancement of maritime standard(s) respecting and be com-pliant with: the ISPS code, modified IT and CIs security management standards.

S-PORT: a national project

In the national S-PORT project [START_REF]S-PORT Deliverable 1.2: State of the art and user requirements in the Port Information and Telecommunication (PIT) Systems Security[END_REF], the ports are viewed as CIs and it addresses the following two main security management needs: The development of a targeted security management collaborative methodology for the PIT-systems based on IT security management standards and the ISPS code involving all PIT users; The promotion of collaboration and interaction among PIT users in the security management of the PIT-systems in an automated used friendly approach.

The first need is addressed by S-PORT by applying the STORM-RM collaborative risk management methodology [START_REF] Ntouskas | Impact Assessment through Collaborative Asset Modeling: The STORM-RM approach[END_REF], [START_REF] Ntouskas | STORM-RM: A collaborative and multicriteria risk management methodology[END_REF] which views risk management as a collaborative decision making problem and combines the Analytic Hierarchy Process (AHP) [START_REF] Saaty | Decision making with the analytic hierarchy process[END_REF], the security management standards ISO27001 [START_REF]Information technology -security techniques -information security management system -requirements[END_REF] and AS/NZS 4360 [START_REF]AS/NZS 4360: Risk management standards australia[END_REF] and has been modified in order to address the specific needs of PIS and the requirements of the IMO/ISPS directive. In STORM-RM a multicriteria collaborative decision making technique is applied enabling all users (internal and external) to evaluate the impacts depending upon their experience and role in their interaction with the IT system under assessment (where most of the existing risk management methodologies enable only the security team to be involved in the impact evaluation). The STORM-RM has been parameterised for the PIT-systems [START_REF] Ntouskas | A secure, collaborative environment for the security management of port information systems[END_REF], [START_REF]S-PORT Deliverable 1.4: Port Information and Telecommunication (PIT) Systems Security requirements-A targeted PIT-risk assessment methodology[END_REF] considering sectoral PIT and cyber threats, setting criteria in the impact evaluation rising from the fact that ports are CIs and assigning roles/ opinion weights according to the ports' users. The basic goal of this parameterised methodology is the collection of knowledge and experience from all port's users (i.e. managers, administrators, security team, local users, cooperate users) in order to evaluate the impacts, sectoral threats, vulnerabilities and risks more accurately.

The second security management need is addressed in S-PORT by developing a collaborative environment [START_REF] Ntouskas | A secure, collaborative environment for the security management of port information systems[END_REF] (a recent trend in Web services applied in various sectors e.g. e-commerce [START_REF] Ntouskas | A collaborative system offering security management services for SMEs/mEs[END_REF], [START_REF] Ntouskas | Trusted collaborative services for the IT security management of SMEs/mEs[END_REF], e-government [START_REF] Karantjias | An innovative platform architecture for complex secure e/m government services[END_REF] and e-migration, [START_REF] Pentafronimos | Odysseus: An advanced, collaborative and trusted framework for the provision of migration services[END_REF]) using innovative Web2.0 technologies. The S-PORT environment [START_REF] Ntouskas | A secure, collaborative environment for the security management of port information systems[END_REF], [START_REF] Ntouskas | Collaborative security management services for port information systems[END_REF] is a parameterisation of the STORM security management environment [START_REF] Ntouskas | Storm -collaborative security management environment[END_REF] addressing the specific needs of PIT and involving all PIT users in the security management procedures.

In the S-PORT collaborative environment we embedded the targeted risk management methodology offered as an S-PORT collaborative service to the PIT-users. More specifically, each phase of S-PORT-RM methodology has been implemented as a distinct module in the S-PORT environment. Additional S-PORT collaborative security management services will be offered thru the S-PORT environment including cartography: graphical representation of the PIT infrastructure and identification of all assets of the PIT-systems; reporting: generation of security documents, e.g. security policies, business continuity plans, disaster recovery plans (as growing documents); collaborative Web2.0 services: forums, chat rooms, questionnaires, for building social interactions in resolving and discussing security issues.

Conclusions and Acknowledgments

The fact that commercial ports are critical infrastructures and their Information Systems offer critical services and host sensitive data, makes security management a necessary concern for their business continuity and productivity. In this context, S-PORT environment is expected to become a prototype of the next generation Information Security Managements Systems, being capable of providing high levels of confidentiality, reliability, interactivity and interoperability, for the critical infrastructures of the commercial ports. This work has been performed in the framework of the S-PORT project [START_REF] Project | A secure, collaborative environment for the security management of Port Information Systems[END_REF] and the authors would like to thank the GSRT (General Secretariat for Research and Technology Development Department) for funding the S-PORT project and the S-PORT partners.

Fig. 1 .

 1 Fig. 1. Maritime Environment


John C John
email: johnj@sit.iitkgp.ernet.in

Shamik Sural
email: shamik@sit.iitkgp.ernet.in

Vijayalakshmi Atluri
email: atluri@cimic

Jaideep S Vaidya
email: jsvaidya@rbs.rutgers.edu

Role Mining under Role-Usage Cardinality Constraint

Keywords: Role Based Access Control, Constrained Role Mining, Boolean Matrix Decomposition

With the emergence of Role Based Access Control (RBAC) as the de facto access control model, organizations can now implement and manage many high level security policies. As a means of migration from traditional access control systems to RBAC, different role mining algorithms have been proposed in recent years for finding a minimal set of roles from existing user-permission assignments. While determining such roles, it is often required that certain security objectives are satisfied. A common goal is to enforce the role-usage cardinality constraint, which limits the maximum number of roles any user can have. In this paper, we propose two alternative approaches for role mining with an upper bound on the number of roles that can be assigned to each user, and validate their performance with benchmark data sets.

Introduction

In traditional access control mechanisms, a user can access a resource if he has been given appropriate permission on that resource. These user permissions can be represented as a matrix, called User to Permission Assignment (UPA), where the value in each cell (1 or 0) indicates whether a user has the permission or not. In a typical organization with tens of thousands of users and hundreds of thousands of permissions, the size of the UPA matrix could be quite large, making security administration increasingly difficult.

To alleviate the burden of security administration, organizations are migrating to an alternative access control mechanism known as Role Based Access Control (RBAC) [START_REF] Sandhu | Role Based Access Control Models[END_REF][START_REF] Ferraiolo | Proposed NIST Standard for Role-Based Access Control[END_REF]. In RBAC, users obtain permissions by virtue of being assigned to roles. A role may be assigned to multiple users. Since the number of roles is orders of magnitude lower than the number of users, RBAC significantly reduces security administration overhead.

For implementing RBAC in an organization currently using traditional UPA based access control, suitable roles have to be formulated. This process of formulation of roles is known as Role Engineering [START_REF] Zhang | Role Engineering using Graph Optimization[END_REF]. Generally there are two approaches to role engineering: top down and bottom up. In the top down approach, business processes are initially divided into independent functional units called job functions. Roles are assigned to these job functions by associating the required permissions. Since the usual number of business processes, job functions and users is quite large, real life implementation of top down approach happens to be difficult, error prone and not quite cost effective. On the other hand, bottom up approaches use the existing user permission assignments. From the UPA, roles with corresponding permissions are derived and users are assigned to these roles. Two binary matrices UA (User to Role Assignment) and PA (Permission to Role Assignment) are thus formed. UA represents which users belong to which roles, and PA represents which permissions are contained in which roles. It is intuitively obvious that the bottom up approach can be conveniently automated. Such an automated procedure for deriving roles from a given UPA matrix, and thereby forming the UA and PA matrices is known as role mining [START_REF] Vaidya | The Role Mining Problem: Finding a Minimal Descriptive Set of Roles[END_REF][START_REF] Molloy | Mining Roles with Multiple Objectives[END_REF]. While there could be many possible decompositions of a given UPA matrix into UA and PA matrices, a useful notion is to obtain a decomposition that minimizes the number of roles, which is the number of columns in the UA matrix and equivalently the number of rows in the PA matrix. This is known as the basic Role Mining Problem (RMP) [START_REF] Vaidya | The Role Mining Problem: Finding a Minimal Descriptive Set of Roles[END_REF]. RMP is an optimization problem and its decision version has been shown to be NP-Complete.

An important feature of any RBAC system is the ability to impose various constraints [START_REF] Sandhu | Role Based Access Control Models[END_REF][START_REF] Ferraiolo | Proposed NIST Standard for Role-Based Access Control[END_REF]. The constraints help to express the organizational security policy, thereby achieving desired security objectives. In many situations, a restriction is imposed on the maximum number of roles that can be played by any user, either due to security restrictions or due to balanced work distribution. We denote this as the role-usage cardinality constraint. Since the role mining process is expected to generate organizational roles and corresponding user assignments in an automated way, it is imperative that such a constraint be taken into consideration while mining the roles from a given UPA matrix. Further, from a security administration point of view also, it makes sense to let users achieve their requisite permission through lower number of roles. However, none of the existing work on role mining addresses this issue.

In this paper, we propose two alternative approaches for considering roleusage cardinality constraints while mining the roles. The first approach, called the Role Priority based Approach (RPA), as the name suggests, first prioritizes the roles based on their size (i.e., number of permissions within the role) and then limits the number of roles assigned to a user using this priority order. The second approach, called the Coverage of Permissions based Approach (CPA) chooses roles by iteratively picking the role with the largest number of permissions that are not yet assigned to that user by any other role, and then imposes the role-usage cardinality constraint. Since both these approaches use different greedy strategies, we have implemented and validated both RPA and CPA using benchmark data sets; our results show that RPA fares significantly better than CPA.

The rest of this paper is organized as follows. In Section 2, we present our proposed approaches with detailed algorithms. In Section 3, the results of running the two proposed algorithms on different datasets are presented and analyzed. In Section 4, we review the related work on role mining. Finally, Section 5 concludes this paper and provides directions for future work.

Role Mining with Role-usage Cardinality Constraints

In this section, we present our two proposed approaches: the Role Priority based Approach (RPA) and Coverage of Permissions based Approach (CPA), which mine the minimum set of roles from a UPA matrix under the constraint that the number of roles assigned to any user cannot exceed a specified upper bound.

We start off with some notation. First, as discussed earlier, U A, P A and U P A are all boolean matrices. Assume that there are n users and m permissions, with q candidate roles. Thus, U A is n × q, P A is q × m and U P A is n × m. Let c ij represent the UA matrix entry for user i (i = 1 . . . n) and role j (j = 1 . . . q), and let r jt represent the PA matrix entry for role j (j = 1 . . . q) and permission t (t = 1 . . . m). Finally, let x it represent the UPA matrix entry for user i and permission t. Then, for any correct decomposition, the following conditions must be met [START_REF] Lu | Optimal Boolean Matrix Decomposition: Application to Role Engineering[END_REF]: q j=1 c ij r jt ≥ 1 for x it = 1 and q j=1 c ij r jt = 0 for x it = 0. Given the above, the role-usage cardinality constraint can be represented as

q j=1 c ij ≤ maxcount, f or1 ≤ i ≤ n.

Role Priority based Approach (RPA)

The Role Priority based approach prioritizes roles by their size (i.e., the number of permissions in the role). Now, roles are assigned to each user by picking the roles whose permissions are a subset of the permissions required by that user, and are not redundant (i.e., the permission has not already been assigned through another prior-picked role). While any set of candidate roles could be used, in this paper, we use the candidate roles generated from the UPA by the greedy strategy for optimal boolean matrix decomposition (referred to as OBMD) proposed by Liu et al. [START_REF] Lu | Optimal Boolean Matrix Decomposition: Application to Role Engineering[END_REF]. Note that OBMD can produce redundant roles for some of the users. A role r is considered redundant (for a user i) if the permissions of r form a subset of the permissions of one or more other roles of the same user i. This is because the greedy approach only eliminates those candidate roles which are not used by any of the users. OBMD does not check the redundancy of roles for each user. Therefore, we eliminate such redundant roles in the candidate roles generated by OBMD. Also, the roles generated by Fast Miner [START_REF] Vaidya | Role Miner: Mining Roles using Subset Enumeration[END_REF], which OBMD uses as base, do not cover the permissions which are exclusively assigned to a user. To cover these permissions, separate roles are generated. The roles are then prioritized based on the number of permissions contained in each role. To restrict the number of roles of each user upto the specified upper bound, the roles are selected in the order of their priority. If all of the permissions of the user are not covered after selecting maxcount -1 roles, where maxcount is the specified upper bound, the remaining uncovered permissions are formed into a separate role.

These steps are summarized in Algorithm 1. Formation of initial UA matrix and the associated PA matrix using OBMD is done in Line 1. Then, a Role Priority (RP) list is created in which roles are maintained in the descending order of the number of permissions associated with each role (Line 2). The variable maxcount denotes the maximum number of roles allowed for a user and rolecount denotes the number of roles so far assigned to a user. In lines 4-12, for each user, the roles are selected one by one as per the order in the RP list until all permissions of the user are covered or until the rolecount becomes maxcount -1. If the permissions of the selected role form a subset of already covered permissions of the user, they are redundant and are eliminated during the process (Lines 7-8). If the rolecount value reaches maxcount -1 and all the permissions of the user are not yet covered, a new role r is generated comprising of all the uncovered permissions (if it is not an existing role; otherwise, uses the existing role r) and includes r in the PA matrix, also setting the corresponding c ir cell of the UA matrix to 1 (Lines 13-23).

Table 1. Sample input data set (in the form of UPA matrix) p1 p2 p3 p4 p5 u1 1 0 0 0 1 u2 0 0 1 1 0 u3 1 0 1 1 0 u4 1 1 1 1 1 u5 0 0 1 1 0 u6 1 1 0 0 0

r1 r2 r3 r4 r5 u1 c11 c12 c13 c14 c15 u2 c21 c22 c23 c24 c25 u3 c31 c32 c33 c34 c35 u4 c41 c42 c43 c44 c45 u5 c51 c52 c53 c54 c55 u6 c61 c62 c63 c64 c65 p1 p2 p3 p4 p5 r1 1 0 0 0 0 r2 1 0 0 0 1 r3 0 0 1 1 0 r4 1 1 0 0 0 r5 1 0 1 1 0
Illustrative Example We now consider an illustrative example given in Table 1 for explaining both the OBMD and RPA algorithms. OBMD employs the Fast Miner algorithm to generate q number of candidate roles and to form the binary 1 Role Priority based Algorithm (RPA)

1: Use the OBMD algorithm to form the decomposition into U A and P A matrices 2: Prepare Role Priority (RP) list by ordering the roles in descending order of the number of permissions in the role 3: for each user i do 4:

Set rolecover = null and rolecount = 0 5:

while rolecover does not contain all permissions of i and rolecount = maxcount -1 do 6:

Find the next role, k, in the RP list whose permissions are a subset of the permissions of user i 7:

if k ⊆ rolecover then 8:

Set c ik = 0 9: else 10: rolecover = rolecover∪{permissions of k} and Set rolecount = rolecount+ 1 11:

end if 12:

end while 13:

Set D = Permissions of i -union of permissions of all roles of i 14:

if D = φ then 15: Set all remaining roles of i to be 0 16: else 17:

if D = existing role r in the PA matrix then 18:

Set cir = 1 and Set all remaining roles of i to 0 19: end if 20: else 21:

Generate a new role r with all permissions of D 22:

Include r in the PA and UA matrices(set cir = 1 ) and Set all remaining roles of i to 0 23: end if 24: end for Table 3. Final UA and PA matrices obtained from OBMD r1 r2 r3 r4 u1 1 1 0 0 u2 0 0 1 0 u3 1 0 1 0 u4 1 1 1 1 u5 0 0 1 0 u6 1 0 0 1 p1 p2 p3 p4 p5 r1 1 0 0 0 0 r2 1 0 0 0 1 r3 0 0 1 1 0 r4 1 1 0 0 0 PA matrix. The initial UA and PA matrices consisting of five candidate roles generated through Fast Miner are shown in Table 2.

The UA matrix is formed by selecting appropriate roles from the PA matrix based on the count of the conditions being satisfied while selecting a role. Some of the candidate roles which are not used by any of the users can finally be rejected, thereby reducing the total number of roles. The final matrices after applying the appropriate conditions as mentioned above are given in Table 3.

Assume the value of the cardinality constraint (maxcount) is 2. In Step 1, the OBMD algorithm gives an output as shown in Table 3. The RP list is prepared as {r2, r3, r4, r1}. RPA then selects the appropriate roles from the list for each user. For user u1, role r2 is selected. With this role all permissions of u1 are covered. Similarly, role r3 is found for user u2. The first role selected for user u3 is role r3. Now the value of rolecount becomes 1 which is equal to maxcount -1. It can be observed that the remaining set of uncovered permissions is the same as the existing role r1, and hence, r1 is selected. For user u4, role r2 is initially selected. Again the value of rolecount becomes equal to maxcount -1. Now the uncovered permissions are not the same as any existing role and so a new role r5 is created with all the uncovered permissions. For user u5, the algorithm initially selects role r4. With this role all permissions of the user are covered. Thus, the algorithm finds a total of 5 roles for a maxcount value of 2. The final UA and PA matrices are shown in Table 4.

It may be noted that the OBMD algorithm generates four roles as shown in Table 3. But user u4 has four roles which exceeds maxcount. The decomposition done by RPA restricts the number of roles of users to the specified upper bound. The total number of roles is increased to five to satisfy this constraint. Table 4. UA and PA matrices generated by RPA r1 r2 r3 r4 r5 u1 0 1 0 0 0 u2 0 0 1 0 0 u3 1 0 1 0 0 u4 0 1 0 0 1 u5 0 0 1 0 0 u6 0 0 0 1 0 p1 p2 p3 p4 p5 r1 1 0 0 0 0 r2 1 0 0 0 1 r3 0 0 1 1 0 r4 1 1 0 0 0 r5 0 1 1 1 0

Coverage of Permissions based Approach (CPA)

The second approach, called the Coverage of Permissions based Approach (CPA), selects roles based on the number of permissions that are as yet unassigned to a user, while still enforcing the cardinality constraint. Fast Miner is employed to form the initial set of candidate roles, similar to that shown in Table 2. Effectively, it works on decompositions containing all candidate roles. In order limit the number of roles of each user upto the specified bound, the algorithm keeps on finding roles which contain the largest number of uncovered permissions (permissions not yet assigned through any role) for the user. If all permissions of the user are not covered after selecting maxcount -1 roles, the remaining uncovered permissions are grouped into a separate role. The redundant roles are also eliminated during the process.

The steps are summarized in Algorithm 2. Fast Miner is used to generate q candidate roles and form the initial PA matrix and the UA matrix in Line 1. Next, c ij values of the UA matrix are set to 0 according to the condition q j=1 c ij r jt = 0 (Line 2). For each user i, in each step, the algorithm finds a role which covers the maximum number of uncovered permissions of i from among all the roles r where c ir = 1. The process is repeated until all the permissions of the user are covered or rolecount becomes maxcount -1 (Lines 4-8). If the rolecount is maxcount -1 and all the permissions of user i are not yet covered, a new role r is generated with the uncovered permissions (if it is not an existing role; otherwise, the existing role r is used). Finally, r is included in the PA matrix and the corresponding c ir of the UA matrix is set to 1 (Lines 9-20).

Algorithm 2 Coverage of Permissions based Algorithm (CPA)

1: Generate candidate roles by taking intersection of the permissions of every pair of users. Form P A matrix and associated U A matrix. (Fast Miner approach) 2: Set the required cells of cij to 0 as per q j=1 cij rjt = 0 for all xit = 0 3: for each user i do 4:

Set rolecover = null and rolecount = 0 5:

while rolecover does not contain all permissions of i and rolecount = maxcount -1 do 6:

Find the role k that contains the maximum number of permissions of i which

are not yet contained in rolecover, while not adding any unallowed permissions to i 7:

Set c ik to be 1, Set rolecover = rolecover ∪ {permissions of k} and Set rolecount = rolecount + 1 8:

end while 9:

Set D = Permissions of i -union of permissions of all roles of i 10:

if D = φ then 11: Set all remaining roles of i to be 0 12: else 13:

if D = existing role r in the PA matrix then 14:

Set cir = 1 and Set all remaining roles of i to 0 15: end if 16: else 17:

Generate a new role r with all permissions of d 18:

Include r in the PA and UA matrices 19:

Set cir = 1 and Set all remaining roles of i to 0 20: end if 21: end for Illustrative Example Consider again the same dataset given in Table 1 and assume the value of cardinality constraint to be 2. The initial decomposition is as given in Table 2. In the next step, the CPA algorithm finds the cells of UA matrix which are to be set to 0 using the condition q j=1 c ij r jt = 0. Then, for each user, it finds roles which cover maximum number of uncovered permissions. User u1 has two roles from which the algorithm selects role r2 since it covers more permissions of u1 as compared to role r1 and with that role all permissions of u1 are covered. So it sets the remaining cells of u1 in the UA matrix to 0. Similarly, user u2 gets role r3 and user u3 gets role r5. User u4 is assigned to role r5 initially. Now the rolecount becomes equal to maxcount -1. So a new role r6 is formed with all uncovered permissions. The new role is included in the UA matrix and c 61 is set to 1. Then user u5 gets role r3 and finally user u6 gets role r4. The unused role r1 is removed. The algorithm completes execution after mining five roles. The final decomposition matrices are shown in Table 5 (after renaming roles from r2 to r6 as r1 to r5).

Table 5. UA and PA matrices generated by CPA r1 r2 r3 r4 r5 u1 1 0 0 0 0 u2 0 1 0 0 0 u3 0 0 0 1 0 u4 0 0 0 1 1 u5 0 1 0 0 0 u6 0 0 1 0 0 p1 p2 p3 p4 p5 r1 1 0 0 0 1 r2 0 0 1 1 0 r3 1 1 0 0 0 r4 1 0 1 1 0 r5 0 1 0 0 1

As is evident, from the above discussions, RPA and CPA use different greedy choices. The output decompositions in the examples are also different. But the number of roles obtained is the same in the two cases for the example dataset even though the actual roles are different. In the next section, we give a comparative performance of both these algorithms with benchmark datasets.

Experimental Results

Algorithms 1 (RPA) and 2(CPA) were executed on a number of datasets as listed in Table 6. These are real-world datasets used to evaluate the work reported in [START_REF] Alina | Fast Exact and Heuristic Methods for Role Minimization Problems[END_REF]. Table 6 also provides the sizes of these datasets in terms of the number of users, number of unique permissions as well as the permission size, which is the total number of permissions added over all users.

We plot the variation of the number of roles (y-axis) generated by RPA and CPA with varying constraint value (x-axis). The roles discovered by both algorithms satisfy the given constraint. The plots are shown in Figures 1 to 3 The number of roles generated by RPA is less than or equal to that of CPA in all datasets. By observing the output for the datasets Healthcare and Firewall 2, it can be concluded that the number of generated roles decreases when the value of the constraint increases. The number of roles generated by OBMD in the Healthcare dataset is 17. But RPA generates only 15 roles when the value of the constraint is greater than or equal to 2. When the constraint value is set to 1, it generates 18 roles. On the contrary, CPA gives 18 roles for all values of the constraint. Similarly, for Firewall 2 dataset, OBMD generates 10 roles and RPA produces the same number of roles when the constraint value remains greater than or equal to 2. It generates 11 roles for a constraint value of 1. Here also CPA generates 11 roles for all cases.

For the datasets Domino and EMEA, the reverse occurs. There the number of roles generated shows a decrease when the value of the constraint decreases. This appears to be contradictory. However, the reason is that the candidate roles generated by the Fast Miner algorithm in those datasets do not contain roles which produces optimum result. Also, presence of many exclusive permissions in the dataset, results in increased number of roles. Such exclusive roles are not part of the roles generated by Fast Miner. For the Domino dataset, OBMD produces 29 roles. However, the optimal number is 23, which is produced by both RPA and CPA algorithms for the constraint value 1. Similarly for the EMEA dataset, the number of roles generated by OBMD is 122 but the optimal number is 34 which is produced by both the proposed algorithms for the constraint value 1. Thus, OBMD does not give optimal number of roles for these datasets. In both of our approaches, when the value of the constraint is reduced and it approaches a value of 1, many of the roles get merged with other roles to form a new role. As a result, in these datasets, the algorithms give optimal result when the value of the constraint is low. An improvement in the Fast Miner algorithm would give a better candidate role generation.

For the Firewall 1 dataset, OBMD produces 75 roles. RPA gives the optimal result for constraint values greater than or equal to 4 and the minimum number of roles generated by this algorithm is 72. When the value of the constraint is less than 4, the number of roles generated by RPA increases and for a value of 1 it produces the highest number of roles, which is 90. However, for this dataset, CPA never finds an optimal result. It produces minimum number of roles (90 roles) for the constraint value 1. Several attempts have been made so far for bottom-up identification of roles in RBAC. Schlegelmilch and Steffens [START_REF] Jürgen | Role mining with ORCA[END_REF] introduced a role mining tool named ORCA which forms a hierarchy of permission clusters. A subset enumeration technique is used in [START_REF] Vaidya | Role Miner: Mining Roles using Subset Enumeration[END_REF]. After clustering the users having similar permissions, it intersects all possible combinations of user's permissions and generates a set of candidate roles. These roles are then prioritized based on the number of users sharing the roles. The work in [START_REF] Vaidya | The Role Mining Problem: Finding a Minimal Descriptive Set of Roles[END_REF] maps RMP into an equivalent problem -the Largest Uncovered Tile Mining (LUTM) problem, which uses the concept of database tiling [START_REF] Geerts | Tiling Databases[END_REF]. Generating minimum number of roles in RMP is equivalent to finding the minimum number of tiles in the tiling problem. Zhang et al.

[8] use a graph optimization technique to form role hierarchies. In [START_REF] Lu | Optimal Boolean Matrix Decomposition: Application to Role Engineering[END_REF], Lu et al. model the problem into optimal Boolean matrix decomposition problem. In order to generate practical roles, [START_REF] Zhang | Permission Set Mining: Discovering Practical and Useful Roles[END_REF] ignores some permission assignments. Authors of [START_REF] Alina | Fast Exact and Heuristic Methods for Role Minimization Problems[END_REF] proposed an algorithm which uses bipartite graph formulation to find approximately minimum number of roles by forming biclique cover of edges of the graph.

Little work has been done on RMP with cardinality constraints. Kumar et al. [START_REF] Kumar | Mining RBAC Roles under Cardinality Constraint[END_REF] considered RMP with a constraint which limits the maximum number of permissions that a role can have. They use a combination of clustering and constrained permission set mining to generate roles. Recently, Hingankar and Sural [START_REF] Hingankar | Towards Role Mining with Restricted User-Role Assignment[END_REF] have worked towards role mining with a constraint on the maximum number of users in a role. They use the biclique cover approach to arrive at the solution. However, there is no available literature on RBAC role mining with an upper bound on the number of roles a user can have.

Conclusions and Future Direction

In this paper, we consider the problem of constrained role mining, by enforcing the limit on the number of roles a user can have. We have presented two different approaches to enforce the role-usage cardinality constraint. Variation in the number of generated roles by varying the value of the constraint has been studied on real-world datasets for both these approaches.

Organizations may impose restriction on multiple RBAC parameters at the same time. The parameters could be upper bounds on number of roles to a user, number of permissions in a role, number of roles in a permission, etc. While we consider a single constraint in this paper, the combined effect on the mining process when many constraints are considered simultaneously needs be studied. The work can be extended to find an optimal solution to the role mining problem with such multiple constraints.

Acknowledgement

This work is partially supported by a research grant from the Department of Science and Technology, Government of India, under Grant No. SR/S3/EECE/082/

  .

6

 6

Fig. 1 .Fig. 2 .Fig. 3 .

 123 Fig. 1. Number of roles generated for (a) Healthcare dataset and (b) Domino dataset

Table 2 .

 2 Initial UA and PA matrices generated by Fast Miner

2007. The work of Atluri is supported in part by the National Science Foundation under grant CNS-0746943.