Dongjin Choi
email: dongjin.choi84@gmail.com

Ilsun You
email: isyou@bible.ac.kr

Pankoo Kim
email: pkkim@chosun.ac.kr

Syntactic Analysis for Monitoring Personal Information Leakage on Social Network Services: A Case Study on Twitter

Keywords: Information flow, Social network services, Information leakage, Twitter

Social network services such as Twitter and Facebook can be considered as a new media different from the typical media group. The information on social media spread much faster than any other traditional news media due to the fact that people can upload information with no constrain to time or location. Because of this reason, people got fascinated by SNS and it sinks into our life. People express their emotional status to let others know what they feel about information or events. However, there is a high possibility that people not only share information with others, but also they expose personal information unintentionally such as place to live, phone number, date of birth, and more. This will be serious problem if someone has impure mind. It is actually happening in cyber-stalking, offline stalking or others. There are also many spam messages in SNS because of the fact that information in SNS spread much faster than any other media and it is easy to send a message to others. In other words, SNS provides vast backbone environment to spammers to hunt normal pure users. In order to prevent information leakage and detect spam messages, many researchers traditionally have been studied for monitoring email systems, web blogs, and so on. In this paper, we dealt with text message data in Twitter which is one of the most popular social network services over the world in order to reveal various hidden patterns. Twitter data is severely dangerous to organizations and more is that anyone who has Twitter account can access to any users by "following" function. The following function does not require permission from the requested person to confirm to ready their timelines. This study will be focused on the user to whom exchange text messages and what types of information they reciprocated with others by monitoring 50 million tweets on November in 2009 which was collected by Stanford University.

Introduction

People are living in the place to find and share information with no constrains to time or location due to the huge enhancements of wireless internet infrastructure and Smartphone devices. We used to have to go back to home or internet cafe to search information or upload photos in very few years ago. However, we no longer have to go back to place to find desktop which has an internet access. We are simply able to obtain and share diverse information using Smartphone via mobile web browser or social network service (SNS) platform. Traditionally, the Web provides convenient and useful services to find information, knowledge, and more. People are willing to upload what they have been experienced during their travel or knowledge from their researches. Despite of this great convenience, there is a high possibility of personal private information leakage. The problem is that this personal information is leaking more seriously due to SNS. SNS is an online web platform to provide social activities among people. They share interests, activities, knowledge, events and more to strengthen their social relation with others in anytime and anywhere. There was a popular event make Twitter 2 got famous after U.S. Air ways jet crashes into the Hudson River on 15th of January 2009. The first photograph of this crash had appeared on Twitter earlier than any even local news media arrived at the accident place. This event brings an aspect that Twitter is not just a social web page but it is one of media. People got fascinated by this event so the popularity of Twitter was increased dramatically and it sinks into our life. The fastest social media is not always positive to people. Because of the fact that information on Twitter spread within a few second to all over the world, this might bring big obstacle to us all. The main reason why Twitter data is severely dangerous to organizations and more is that anyone who has Twitter account can access to any users by "following" function. The following function does not require permission from the requested person to confirm whether he/she will grant authority to read their timeline (or text message with others) or not. If user A send a following request to user B, user A automatically will be confirmed that he hereby can read timelines of user B based on the Twitter policy. Let assume that user C sends a message to their friends to share information that tomorrow is his/her birthday. Or user D sends a message to celebrate his/her friend"s birthday. In this case, although the date of birth is highly related to personal information, people normally expose precise date of birth unintentionally. The problem here is that as long as user E is following user C or D, user E is able to acquire personal text messages between user C and D. Moreover, people send a text to others with their real name or place to live. This is the main reason why we want to monitor personal information leakage on Twitter. Many researchers believe that SNS has great potential to reveal unknown personal attitude or sentiments but it still has an information leakage problem. This will be a serious problem if someone who has impure mind track personal information for cyber stalking. In order to prevent this problem on Twitter, we dealt with text message data in Twitter to reveal various hidden patterns related to personal information. This study will be focused on the user to whom reciprocated with by monitoring 50 million tweets on November in 2009 2 http://twitter.com which was collected by Stanford University. We defined simple syntactic patterns to uncover date of birth in human written text messages. The reminder of the paper is organized as follows: Section 2 describes related works; Section 3 explains a method for monitoring personal information leakage on Twitter based on syntactic patterns; Section 4 gives example for tracking breaking-events using Twitter; and finally Section 5 presents a conclusion to this work and makes suggestions for the future work.

Related Works

Digital personal information or personal identifiable information (PII) is always secured from other users. PII is information to uniquely identify or distinguish a single person identity. Full name, national identification number, driver license number, credit card number, date of birth, and more are commonly used to distinguish individual identity [START_REF] Krishnamurthy | I know what you will do next summer[END_REF]. For example, if there is person who wants to withdraw huge amount of money from his/her bank accounts, he/she will be asked for presenting a valid PII to authenticate his/her identity. Moreover, when people forgot passwords for certain webpage, he/she will be asked for input PII data such as date of birth or email address. This digitized data can be easily duplicated to others and it tends to be exposed to others more readily than traditional physical resources [START_REF] Yim | Guest Editorial: Information Leakage Prevention in Emerging Technologies[END_REF]. This can be a serious crime if someone who has impure mind obtains digital PII intentionally or even accidently. Over the years, many researchers have been studied for prevent personal information leakage not only in Internet web pages but also in SNS. Traditionally, packets which contain encrypted messages considered as an important factor to improve personal information security by monitoring transferring packets in networks [START_REF] Choi | A personal Information Leakage Prevention Method on the Internet[END_REF]. Moreover, there was a research proposed a model to support a supply chain to make understand how confidential information of companies may be leaked using a conceptual model [START_REF] Zhang | Modeling and evaluating information leakage caused by inference in supply chains[END_REF]. In order to infer private information in SNS, authors in [START_REF] Lindamood | Inferring private information using social network data[END_REF] studied Facebook3 data based on Naïve Bayes classification to predict privacy sensitive trait information among users. This research analyzed links among users to determine that personal information can be leaked to unknown person. [START_REF] Lucas | flyByNight: Mitigating the Privacy Risks of Social Networking[END_REF] presented a new architecture for protecting personal private information published on Facebook for mitigating the privacy risks. Moreover, there was another research to trace social footprint of user"s profile in order to uncover the fact that diverse personal information is leaking on multiple online social networks such as Flickr4 , LiveJournal 5 , and MySpace6 [START_REF] Irani | Modeling Unintended Personal-Information Leakage from Multiple Online Social Networks[END_REF]. There is a big issue we have to give great attention that is personal information in SNS is leaking involuntarily [START_REF] Lam | Involuntary Information Leakage in Social Network Services[END_REF]. People have been starting to take good care of preventing their personal information leakage when they make web documents. However, the problem is happened in SNS that SNS is full of freedom and enough metadata to infer someone"s personal information. Users in SNS are likely to expose their private information unintentionally. This is why this paper focused on text messages in timeline on Twitter to reveal the fact that people reciprocate their personal information with others without any attention. Even they do beware of it, private information is leaking unintentionally.

Monitoring Personal Information Leakage on Social Network Services

This section describes a method for monitoring personal information leakage on Twitter. Twitter is a one of the most popular online SNS and microblogging service to share information by sending text-based messages restricted to 140 characters, known as "tweets" [START_REF] Kwak | What is Twitter, a Social Network or a News Media[END_REF][START_REF] Java | Why We Twitter: Understanding Microblogging Usage and Communities[END_REF]. Twitter users can freely follow others or are followed in contrary to most online SNS, such as Facebook or MySpace. Most of the SNS requires permission when users want to access others social web pages but not in Twitter. According to the Twitter policy, being a follower on Twitter means that users are able to obtain all the tweets from those users are following [START_REF] Kwak | What is Twitter, a Social Network or a News Media[END_REF]. This issue guarantees a freedom of information sharing among anyone. However, personal information does not be exposed to everyone. In order to protect user personal information from unknown third parties, we define syntactic patterns to detect date of birth in human written text messages in Twitter. Let us assume that when people celebrate someone"s birthday by a text message via Twitter or other SNS, the text message normally includes given keywords "birthday," "b-day." According to this assumption, we can obtain tweets which contain those keywords from huge amount of Twitter data set by simple text matching approach. The Twitter data set (8.27GB) which was collected by Stanford University [START_REF] Yang | Patterns of Temporal Variation in Online Media[END_REF] consists of time, user and tweet message information described in following Table 1. T means the time when a given tweet was uploaded on Twitter and U indicates the Twitter user id who wrote the tweet. W represents the tweet at time T by user U.

In order to uncover the pattern hided in human natural language on Twitter, we simply extract tweets only include "birthday" and "b-day" from the data set. The size of extracted tweets was only approximately 30MB consist of around 189 thousand tweets. The following Table 2 shows examples of the extracted tweets. Twitter has several functions such as "RT," "@," "#," and more. "RT" means retweet, "@" indicates specific person (user id) whom user wants to send a tweet message and "#" is a hashtag that represents keywords or topics of tweets. We hereby define patterns to infer personal data of birth from the extracted tweets as described in Table 3. In order to define those patterns, we checked entire 189 thousand tweets by manually.

Table 3. Syntactic patterns for detecting date of birth

Index

Pattern information 1 someone (name or user ID) happy birthday (b-day) to someone (name, userID, or pronoun) ex) @Anissarachma happy birthday to you Frank happy happy birthday from my heart happy birthday to my cousin Nathan and @Franklero 2 someone (name or userID) happy birthday (b-day) someone (name, userID, or pronoun) ex) @LauraThomas34 happy birthday friend @kerronclement happy birthday Lolo happy birthday 3 date (such as today or tomorrow) is possessive birthday (b-day) or it is possessive birthday ex) @justinbieber today is my b-day @JackAllTimeLow today is my birthday loooooh @Teairra_Monroe Its my birthday and 4 wish someone (name, user ID, or objective) a birthday ex) @krystyl: On the east coast -its @drew's birthday! Everyone wish him happy bday will you please wish me a happy birthday @MixMastaMario I wish her a happy birthday According to patterns described in Table 3, pattern 1 and 2 is for celebrating someone"s birthday but pattern 3 is for celebrating his/her own birthday. Pattern 4 is for celebrating not only for themselves but also others. In the case of pattern 1 and 2, the first "someone" indicates name of user, user ID, or @user ID. The second "someone" represents name of user, user ID, @user ID, or pronouns. In order to detect name of user in text messages, we collect every name lists of boys and girls from the website7 which contains 10,532 names. Moreover, it is easy to detect user ID due to the fact that users on Twitter are most likely to add "@" function when they send a text message to others. Therefore, if tweet is satisfied with pattern 1 and 2 when user ID comes at first, the date when this tweet was uploaded will be the date for use ID"s birthday. In case for pattern 3, the important factors to determine which date is the date of someone"s birthday are date and possessive words. The date can be one of words such as today, tomorrow, or specific date and possessive represents words e.g. my, his, her, name"s, and user ID"s. "Someone" in pattern 4 can be a name, user ID, or objective word such as "me, her, him, etc." In order to detect personal date of birth on Twitter, we developed simple extraction program based on above patterns using Python.

Experiment

In order to protect user personal information such as date of birth on Twitter, we conducted simple experiment using syntactic patterns described in Table 3 based 4. Let us assume that we have a tweet "RT @rhonda_ Happy birthday @JanetRN" by user apostlethatroks. This given text message indicates that user apostlethatroks send a celebration message which was originally written by user rhonda to user JaneRN. In other words, it was the birthday of user JanetRN. However, there is a problem that it is not guarantee the extracted date of birth is the precise date of user"s birthday due to the fact that the proposed syntactic patterns cannot represent various human written text messages. In order to test how the proposed method can detect personal date of birth precisely, we randomly selected a hundred results to compare its accuracy manually. As a result, we can infer 61 percent of date of birthday from test data set with 75 percent of accuracy rate despite of fact that we only defined four kinds of syntactic patterns.

Conclusion and Future works

In this paper, we proposed a method for monitoring personal information leakage on Twitter by inferring date of birth using proposed syntactic patterns. People can upload diverse information on social network services with no constrain to time or location. This fact brings great convenience to us all but it is still challenging issue. The serious problem is that people are likely to expose their personal information unintentionally via SNS. Therefore, we proposed simple syntactic patterns to give an idea to protect personal private information. Considering that only four kinds of patterns were applied, we believe that the inference rate from test data set is acceptable. If we can define syntactic patterns in detail, the results will be much better than this work. However, it is difficult to determine users when test tweets have pronouns, possessive, or objective words. In the nearest future, we are planning to apply named entity disambiguation approach to enhance the performance.

  on following Fig 1. The test Twitter data set which only includes "birthday" and "b-day" words contains 189,247 tweets with time, user address, and text message.

Fig. 1 .

 1 Fig. 1. Personal date of birth detection process

Table 1 .

 1 Examples of the Twitter data set

	Type	Information
	T	2009-11-02 14:49:31
	U	http://twitter.com/jhernandez48
	W	alright well off to cal class, I agree w/ Valentine on mike and mike but its a
		good things he is not the Philies manager, so oh well
	T	2009-11-02 14:49:31
	U	http://twitter.com/kamanax
	W	This is the month of months and the week of weeks... Looking forward to the
		celebraaa on Friday, satday and Sunday! (cont) http://tl.gd/qkuu
	T	2009-11-02 14:49:31
	U	http://twitter.com/koreainsider
	W	freezing waiting for bus, sweating on the bus and freezing again outside...I love
		that winter is here ?
	…	…

Table 2 .

 2 Examples of the extracted tweets from Twitter data set

	Type	Information
	T	2009-10-31 23:59:58
	U	http://twitter.com/nadiamaxentia
	W	@Anissarachma happy birthday to you, happy birthday to you, i wanna 'traktir'
		dont forget it, happy birthday to you. Haha
	T	2009-11-01 00:01:45
	U	http://twitter.com/1crazy4justinb
	W	@justinbieber today is my b-day and it would mean the world to me if you told
		me happy birthday i love u!MAKE MY DREAM COME TRUE!<3
	T	2009-11-01 00:10:04
	U	http://twitter.com/rgttos
	W	Kyny td udaah yaaa va, hahaha RT @virania: @rgttos happy birthday hhaaaa
	…	…

Table 4 .

 4 Example of experiment results

	User	Date of birth	User	Date of birth
	JanetRN	1st of November	davematthewsbnd	2nd of November
	Larry	1st of November	sethredcast	2nd of November
	1crazy4justinb	1st of November	Queen_MuLa_BaBy	2nd of November
	dhilaloma	1st of November	ly_dalena	2nd of November
	joseph	1st of November	dhardiker	2nd of November
	Robert C Pernell	1st of November	glennmc	2nd of November
	Brian Walker	1st of November	DJAYBUDDAH	2nd of November
	rgttos	1st of November	TwentyFour	2nd of November
	twephanie	1st of November	SoleHipHop	2nd of November
	…	…	…	…

http://facebook.com

http://flickr.com

http://livejournal.com

http://myspace.com

http://www.momswhothink.com

Acknowledgments. This research was financially supported by the Ministry of Education, Science Technology (MEST) and National Research Foundation of Korea (NRF) through the Human Resource Training Project for Regional Innovation


Huabiao Lu

Baokang Zhao
email: zhaobaokang@gmail.com

Xiaofeng Wang
email: xfwang@nudt.edu.cn

Jinshu Su

DiffSig: Resource Differentiation based Malware Behavioral Concise Signature Generation

Keywords: Behavioral Signature, Anti-obfuscation, Scalable, Resource Differentiation, Iterative Sequence Alignment, Handle Dependency

Malware obfuscation obscures malware into a different form that's functionally identical to the original one, and makes syntactic signature ineffective. Furthermore, malware samples are huge and growing at an exponential pace. Behavioral signature is an effective way to defeat obfuscation. However, state-of-the-art behavioral signature, behavior graph, is although very effective but unfortunately too complicated and not scalable to handle exponential growing malware samples; in addition, it is too slow to be used as real-time detectors. This paper proposes an anti-obfuscation and scalable behavioral signature generation system, DiffSig, which voids information-flow tracking which is the chief culprit for the complex and inefficiency of graph behavior, thus, losing some data dependencies, but describes handle dependencies more accurate than graph behavior by restrict the profile type of resource that each handle dependency can reference to. Our experiment results show that DiffSig is scalable and efficient, and can detect new malware samples effectively.

Introduction

Malware, short for malicious software, is software designed to disrupt computer operation, gather sensitive information, or gain unauthorized access to a computer system [1]. Malware includes computer viruses, worms, botnet, trojan horses, spyware, and so on. As we are know, Malware are the most serious threats in Internet for a long period. In fact, malware is the cause of most Internet problems such as spam e-mails and DoS (Denial of Service) [START_REF] Clemens | effective and efficient malware detection at the end host[END_REF].

The number of new malware samples is huge and growing at an exponential pace. Symantec observes 403 million new malware samples in 2011 [3], average 1.1 million malware samples per day. Efficiently analyzing such a scale malware samples and automated generating signatures for them is an interesting and challenging task.

Furthermore, obfuscated malware has become popular because of pure benefits brought by obfuscation: low cost and readily availability of obfuscation tools accompanied with good result of evading syntactic signature (e.g. byte-signature) based anti-virus detection as well as prevention of reverse engineer from understanding malwares' true nature. Obfuscated malwares use code obfuscation in software engineering to make the samples of a malware family look differently but have the same functionality.

The obfuscation techniques commonly used in malware obfuscation are Dead-Code Insertion, Register Reassignment, Instruction Substitution and Instruction Reordering [START_REF] You | Malware Obfuscation Techniques: A Brief Survey[END_REF]. Dead-code insertion is a simple technique that adds some ineffective instructions to a program. Register reassignment switches registers from generation to generation while keeping the program code and its behavior same. Instruction substitution evolves an original code by replacing some instructions with other equivalent ones. Instruction Reordering obfuscates an original code by changing the order of its independent instructions in a random way.

A system call (syscall) is how a program requests a service from an operating system's kernel, include hardware related services (e.g. accessing the hard disk, network card), creating and executing new processes, and so on [5]. The behavior of a program can be thought as its effect on the state of the system on which it executes. Thus, treating behavior in terms of the syscalls invoked by a program is reasonable, and this allows us to succinctly and precisely capture the intent of the malware [START_REF] Fredrikson | Synthesizing Near-Optimal Malware Specifications from Suspicious Behaviors[END_REF]. syscalls are non-bypassable interfaces, so malware intending to unsafely alter the system will reveal its behavior through the syscalls that it invokes [START_REF] Srivastava | System Call API Obfuscation (Extended Abstract)[END_REF]. The current perfect way to describe malware behavior is the dependencies between syscalls [START_REF] Christodorescu | Mining specifications of malicious behavior[END_REF].

The dependencies between syscalls can be presented by behavior graph, in which nodes are syscalls and an edge is introduced from a node x to node y when the syscall associated with y uses as argument some output that is produced by system call x. For example, if a program has a function merging two files (A,B) into a new file (C), the behavior graph for the function is shown in the Fig. 1. Ntreadfile(A, BufferA) uses the handle of file A as source, while handle of file A is produced by Ntopenfile(A), thus, there is an edge from the node Ntopenfile(A) to node Ntreadfile(A, BufferA). And Ntwritefile(C, BufferA +BufferB) writes a buffer which is computed from buffers produced by Ntreadfile(A, BufferA) and Ntreadfile(B, BufferB), and handle of file C produced by Ntcreatefile(C), therefore, there are a edge from nodes Ntreadfile(A, BufferA), Ntreadfile(B, BufferB) and Ntcreatefile(C) to node Ntwritefile(C, BufferA +BufferB) respectively. Dependent syscalls cannot be reordered without changing the semantics [START_REF] Christodorescu | Mining specifications of malicious behavior[END_REF]. Thus behavior graph can defeat various obfuscated technologies naturally. Although effective, it is unfortunately too complex to be obtained and used, and it often requires cumbersome virtual machine technology [START_REF] Clemens | effective and efficient malware detection at the end host[END_REF].

A syscall sequence is the ordered sequence of syscalls that a process performs during its execution. Syscall sequence keep the orders assigned by behavior graph, that is saying, given an edge from a syscall x to syscall y in behavior graph, syscall x must be executed before syscall y. Besides the order of syscalls decided by behavior graph, we can gain handle dependencies between syscalls. In computer, a handle is an abstract reference to a resource, such as a file, a registry key, a process, a (network) socket, or a block of memory [9]. The syscall y is dependent on syscall x on a handle only and only if the handle that is produced by syscall x and used by syscall y as input. we can figure out the dependency of syscalls on handles by simply checking the equality of handles in arguments of syscalls. In the Fig. 1, the dependency of Ntreadfile(A, BufferA)on Ntopenfile(A) is handle dependency. Therefore, the syscall sequence keeps the order and the dependency on handles presented by behavior graph, just losing other data dependencies that their data is modified between syscalls by mathematical or logical operations. The dependency Ntwritefile(C, BufferA +BufferB)on Ntreadfile(A, BufferA) and Ntreadfile(B, BufferB) are such data dependencies. All in all, syscall sequence is an approximate edition of behavior graph while evading strenuous information-flow tracking which is the chief culprit for the complex and inefficiency of graph behavior.

Dead-Code Insertion, Register Reassignment of malware obfuscation have no effect on syscall sequence. Instruction Substitution will evolves an original syscall sequece by replacing some syscalls with other equivalent syscalls. However, as limited syscalls in ordinary operating system, e.g., about 300 syscalls in Microsoft Windows OS, giving a syscalls block ,there is usually rare equivalent one to replace it. Therefore, syscall substitution has limited effect, we consider it in the future works. Instruction Reordering will lead to reorder the orders between independent syscalls. we present an Iterative Sequence Alignment (ISA) to perfectly defeat the syscalls reordering caused by malware obfuscation.

As executed in different environment or random tactics used, various samples of the same malware may bind the same handle to resource with different attributes, e.g. samples create files in different directories with the same purpose and writing to files with same contents, while looking the file path attributes of the handles, the handles are different and it is hard to relate them together. Thus, those differences hamper us to obtain handle dependency relation between different samples, and hamper us to gain a generalized behavior signature for those samples. We propose a resource differentiation scheme to seek common attributes of resource with same affect while hiding the differences of executing environment and the differences introduced by random tactics. The resource differentiation scheme aims to abstract the resources and to find handles with same usage from different samples. Thus it is called DiffHandle. DiffHandle is someway like DiffServ in IP QOS architecture of Internet.

After using DiffHandle to replace a handle with differentiated type of the resource that the handle reference to, and utilizing ISA to gain sub-signature (common non-consecutive ordered syscalls) set from syscall sequences of the same family, we obtain handle dependencies between syscalls in sub-signature set by backtracking those syscalls into original syscall sequences, at the same time, we gain the order restrictions between those syscalls. Finally, we generate a DiffHandle-signature consisting of syscalls that have handle dependencies -the handle can only relate to the designated type of resource-with others, and that have order restrictions between syscalls.

Comparing to behavior graph, DiffHandle-signature loses the data dependencies that their data is modified between syscalls by mathematical or logical operations, but, adds resource type (the type is defined by our resource differentiation scheme) restriction to handle dependencies. However, the most outstanding advantage of our method is avoiding complicated information-flow tacking, instead of it, gaining syscall sequence simply by hooking the SSDT (System Services Descriptor Table ) table [START_REF] Hoglund | Rootkits: Subverting the Windows kernel[END_REF][START_REF] Lanzi | AccessMiner: Using System-Centric Models for Malware Protection[END_REF], even stirring advantage is that DiffHandle-signature can naturally be used as real-time detectors.

This paper proposes a resource differentiation based, anti-obfuscation, effective and efficient malware behavioral signature generation system, DiffSig, which is efficient, voiding complicated information-flow tacking which needs to use dynamic analysis infrastructure (virtual machine with shadow memory), generates a simplified but accurate malware behavioral signature for each malware family. In detail, the main contributions of this paper are as follows:

1. we propose a resource differentiation scheme (DiffHandle) to generalize syscall sequence by classifying resources while hiding the differences introduced by different executing environment or random tactics used by malwre. 2. we present an Iterative Sequence Alignment (ISA) to anti-obfuscation and gain sub-signature (common non-consecutive ordered syscalls ) set from generalized syscall sequences. 3. we raise a concise but accurate behavioral signature presentation -DiffHandlesignature. Comparing to perfect but complicated behavior graph, DiffHandlesignature ignores some data dependencies that their data is modified between syscalls by mathematical or logical operations, but, adds resource type restriction to handle dependencies and avoids complicated information-flow tacking. It naturally suits to be used as real-time detector.

The rest of this paper is organized as follows. In section 2, we describe the system overview of DiffSig. And then we present the main three steps of DiffSig : DiffHandle, ISA and Backtracking refinement in sections 3, 4, 5 respectively. We validate our system using real malware samples in section 6. Finally, we conclude it and present future works in section 7.

System Overview

DiffSig consists of a kernel syscall monitor and three main steps to generate behavioral signature, as Fig. 2 shows. The kernel monitor collects syscall information for a designated process. In order to intercept and log system call information, the kernel monitor hooks the SSDT (System Services Descriptor Table ) table [START_REF] Hoglund | Rootkits: Subverting the Windows kernel[END_REF][START_REF] Lanzi | AccessMiner: Using System-Centric Models for Malware Protection[END_REF] in Windows OS. It logs the timestamp, syscall name, arguments and return value of syscalls. Accordingly to timestamp of syscalls, all the syscalls of the process form a syscall sequence. This kind of sequence in which each syscall with raw arguments and return value is called original syscall sequence.

Resource Differentiation scheme (DiffHandle) classifies resource with same affect together, hiding the differences introduced by different executing environment or random tactics used by malware. For example, DiffHandle classifies file into: system files which generally locate under directory "C:\WINDOWS\system32"; private files which are operated only by a designated application, e.g. files under "C:\Program Files\iTunes" are private files of iTunes; and other types. The step of DiffHandle replaces a handle with differentiated type of the resource that the handle reference to, deletes the non-handle arguments of syscalls, and thus produces generalized syscall sequences in which each syscall is only with the types of resources it operates on.

Iterative Sequence Alignment (ISA) aims to extract all the common syscalls among various samples of the same family. We use sequence alignment to gain common syscalls. But, traditional sequence alignment can only gain partial common syscalls because of syscall reordering, thus, we propose a new alignment method -Iterative Sequence Alignment (ISA). ISA applies multiple ways of traditional sequence alignment. The i th way runs traditional sequence alignment on residual syscall sequences which consist of non-matched syscalls of (i -1) th way. ISA ends iterating when matched syscalls is less than predefined threshold. Some common non-consecutive ordered syscalls gained by each way are called as sub-signature. Multiple ways produce a sub-signature set.

Backtracking refinement finds out the handle dependencies that happens between syscalls in sub-signature set by putting those syscalls back to original syscall sequences of a same family. Backtracking refinement also obtains the order restriction among syscalls, especially, among syscalls from different sub-signatures. After the above three steps, we generate a concise but accurate DiffHandle-signature for each family.

DiffHandle-signature is formalized as a 3-tuple: {S, D, O}. S = {s 1 , s 2 , • • • , s n } presents the common n syscalls extracted by DiffSig;

D = {d 1 , d 2 , • • • , d m } where d k = {s i , s j , T ype ij }(1 ≤ k ≤ m; s i , s j ∈ S)
presents that there is a handle dependency which can only reference to resource type T ype ij between syscall s i and s j ; and the order restriction

O = {o 1 , o 2 , • • • , o l } where o k =< s i , s j > (1 ≤ k ≤ l; s i , s j ∈ S)
presents that syscall s i must be invoked before the syscall s j .

Resource Differentiation Scheme (DiffHandle)

Resource Differentiation scheme (DiffHandle) classifies resource with same affect together, hiding the differences introduced by different executing environment or random tactics of malware. It is someway like DiffServ in IP QOS architecture in Internet. This step replaces a handle with differentiated type of the resource that the handle reference to, and delete the non-handle arguments of syscalls, produces generalized syscall sequences. We describe the differentiation scheme of three permanent resources: file, register key and network as follows.

File Differentiation Scheme

we classify all the files in Windows OS into four categories preliminarily according to their usage: System file, Private file, User file and Temporary file. Table 1 describes the four categories concisely. System files normally locate under directory "C:\WINDOWS\system32\", and are Windows system related services and data. Private files are normally only be operated by its owner application, e.g. files under the installation directory of a application is the private files of the application, thus, files under directory "C:\Program Files\" are private files to different applications, files under "C:\Documents and Settings\xxxx\Application Data" stores data of applications, and also are private files to corresponding application, another type of private file is the files under directory set by user for application , e.g. files under download directory of BitComet is private of BitComet. User files is files owns to a specified user or all users, such files are created and modified during corresponding user active, files under directory "C:\Documents and Settings\Administrator\" are files of Administrator, and ones under "C:\Documents and Settings\All Users\" are shared among all users. Temporary files are intermediate files generated during applications execution, e.g. files under "C:\Documents and Settings\Administrator\Local Settings\Temp" are temporary files when user Administrator is active. Files not belong to above categories are treated as "other" file category.

Register Key Differentiation Scheme

The most important type of register key is Autoruns. Autoruns are configured to run during system bootup or user login and they can make malwares run without any conscious or direct user interaction. Typical locations used by malwares are: "HKLM\System\Currentcontrolset\Services\%\Imagepath", "HKLM\Software\Microsoft\Windows\Currentversion\Run%", "HKLM\Soft-ware\Microsoft\Active Setup\Installed Components%", "HKLM\Software\Mi-crosoft\Windows\Currentversion\Runonce%",and so on [START_REF] Bayer | A View on Current Malware Behaviors[END_REF]. According to normal usage, locations are classified into seven categories preliminarily: Autoruns, HKLM\SYSTEM, HKLM\Software, HKLM\SECURITY, HKLM\SAM, HKEY USER, HKEY CLASSES ROOT (HKCR). Table 2 gives a concise description to each of the seven categories. Register keys not belong to above categories are treated as "other" register key category.

Network Differentiation Scheme

We cluster network traffic into different categories according to higher-layer protocol (e.g. application-layer protocol). Network traffic are classified as Table 3.

Application-layer types are identified by utilizing dynamic application-layer protocol identification technologies [START_REF] Dreger | Dynamic Application-Layer Protocol Analysis for Network Intrusion Detection[END_REF]. New category will be added as needed. The one not belong to above categories is treated as "other" network traffic.

All the resources can add new category as needed. We use longest prefix matching methods to identify which category the resource belongs to for File and Network traffic. In this section, the most simple and basic sequence alignment, pairwise sequence, is introduced first; then we describe our Iterative Sequence Alignment (ISA).

Pairwise Sequence Alignment Algorithm

A pairwise sequence alignment is a matrix where one sequence is placed above the other to find and align common elements. Gaps ('-') are inserted to help , where O(X) presents Ntopenfile(X), R(X) presents Ntreadfile(X, Buffer-X), CL(X) presents Ntclose(X), CR(X) presents Ntcreatefile(X), W(X) presents Ntwritefile(X,BufferX); assuming File A is a user file, File B is a temporary file, and File C also a user file, then the generalized syscall sequences is: "O(3), R(3), CL(3),O(4), R(4), CL(4),CR(3), W(3), CL(3)" and "O(4), R(4), CL(4),O(3), R(3), CL(3),CR(3), W(3), CL(3)". Since various samples of malware may bundling File A, B, C with different filename or file path, syscall generalization removes those differences and keep the rough profile of resource. In the rest of the paper, syscall sequences of the example are expressed in the same manner. The two syscall sequences in Fig. 3 are possible syscall sequences according to behavior graph described in Fig. 1. The common signature produced by the pairwise sequence alignment is "O(4)R( 4)CL(4)*CR(3)W(3)CL(3)", which loses the operations on another user file.

Iterative Sequence Alignment (ISA)

In the above section, we introduce traditional one way sequence alignment which will lose some reordered syscalls. So, we propose a new sequence alignment mod-

-θ noise )(nw)⌉) original sequences SO = {so 1 , so 2 , • • • , so ⌈(1-θnoise)(nw)⌉ }. Result of ISA: sub-signature set SubSigSet = {subsig 1 , subsig 2 , • • • , subsig n isa } where each sub-signature subsig j = (syscall j1 , syscall j2 , • • • , syscall jnj )(1 ≤ j ≤ n isa
) is some ordered syscalls that syscall j(i-1) must be invoked before syscall ji . OUTPUT: a DiffHandle-signature F inalSig = {F S, F D, F O} that satisfies as Formula 2. DiffHandle-signature F inalSig matches a original sequence sg i means that there exists a map function which maps each handle type in F D to a handle in sg i and maps each syscall s x ∈ F S to a syscall s y in sg i , satisfying that for each element {s i , s j , T ype ij } ∈ F D, the mapper of s i and the mapper of s j are handle dependency in sequence sg i and the type of the dependency is T ype ij , and for each element < si, sj >∈ F O, the mapper of s i stands before the mapper of s j in sequence sg i .

Maximize ∥F D∥ subject to ∀syscall k ∈ F S, ∃subsig j that syscall k ∈ subsig j and F inalSig matches all sg i (1

≤ i ≤ ⌈(1 -θ noise )(nw)⌉) (2)

Evaluation

In this section, we compare our DiffSig with previous famous system, Hamsa [START_REF] Li | Hamsa: Fast Signature Generation for Zero-day Polymorphic Worms with Provable Attack Resilience[END_REF]. And verifies the effectiveness of DiffSig to detect new malware samples. we set following default parameters unless otherwise specified: matched threshold to end the iteration θ score is 10, and a noise threshold θ noise is 30%.

Data Set

We obtained a set of malware executables from mwanalysis.org [10] in the period from January 16, 2011 to March 21, 2011. According to the scan results of kaspersky anti-virus, we cluster the malware executables into different families. As a result, we gain 8 families and 331 malware executables described in Table 4 . The column "Family Name" is the scan results of kaspersky antivirus pruning the variant name. Excepting detection result by heuristic methods, normally, the scan results consists of family name and variant name, while variant name is the string locating behind the last '.' in the scan result. E.g. in scan result of malware executable (MD5: 763ceb3a9127a0b9fac1bcf99a901d19): "Backdoor.Win32.Bifrose.usc", "Backdoor.Win32.Bifrose" is the family name, and "usc" is the variant name. The column "NUM of variants" presents the number of different variant names in a family. The column "NUM of executables" describes the number of different MD5 values in a family. Since the kernel module hooking SSDT table not implemented yet, we utilize WUSStrace[13] to gain syscall sequences with detailed information. Besides running malware executables with WUSStrace to gain malicious syscall sequences, we also running normal application with WUSStrace to gain benign syscall sequences. Those normal programs contains firefox, iTunes, BitComet, Windows Office Word, realplay, FoxitReader, Skype, PartitionTableDoctor3.5, NokiaPC-Suite7, PersonalBankPortal, Win32python2.7, and so on, totally 22 applications.

Performance of DiffSig

we compare our DiffSig with Hamsa [START_REF] Li | Hamsa: Fast Signature Generation for Zero-day Polymorphic Worms with Provable Attack Resilience[END_REF] on above section mentioned malicious syscall sequences of malware executables and benign syscall sequences of normal applications. Hamsa [START_REF] Li | Hamsa: Fast Signature Generation for Zero-day Polymorphic Worms with Provable Attack Resilience[END_REF] extracts syscall token (consecutive syscalls) set,to form a signature as a set of common tokens, it aims to cover the most sequences under predefined false positive. Malicious syscall sequences are cut into two parts: one part as training set to generate behavioral signature and the other part as testing set to test the effectiveness of signature generated. Each part has half number of MD5 values and half number of variants.

Table 5 shows the performance of our DiffSig and Hamsa. The column "Number of signatures" describes the number of signatures generated by DiffSig and

Conclusions

To surmount the complication of behavior graph but still to keep its effectiveness. We propose an anti-obfuscation and scalable behavioral signature generation system, DiffSig, which voids information-flow tracking which is the chief culprit for the complex and inefficiency of graph behavior, but describes handle dependencies more accurate than graph behavior by restrict the profile type of resource that each handle dependency can reference to. DiffSig is effective and efficient, generating concise but accurate signatures. Comparing with previous famous signature generation system, Hamsa, our DiffSig produces fewer signatures, detects more malware samples, and has lower false positive. Comparing the computing performance and detection performance with current behavior graph methods is our future works.

Fig. 1 .

 1 Fig. 1. Merging two files (A,B) into a new file (C)

Fig. 2 .

 2 Fig. 2. Architecture of DiffSig

Fig. 3

 3 shows results for pairwise sequence alignment between syscall sequences "O(A), R(A), CL(A),O(B), R(B), CL(B),CR(C), W(C), CL(C)" and "O(B), R(B), CL(B),O(A), R(A), CL(A),CR(C), W(C), CL(C)"

Fig. 3 .Fig. 4 .

 34 Fig. 3. Example of Pairwise Sequence Alignment between Syscall Sequences

Table 1 .

 1 File Differentiation Scheme

	TYPE	ID Location	Description
	System file	1 C:\WINDOWS\system32\	Windows System related execution and data
	Private file	2 C:\Program Files\or others Be operated only by its owner application normally
	User file	3 C:\Documents and Settings\ Files owns to a specified user, such as Administrator
	Temporary file 4 C:\Documents and Settings\ Intermediate files
		xxxx\Local Settings\Temp\
	Others	64 *	*

Table 2 .

 2 Register key Differentiation Scheme

	TYPE	ID Location	Description
	Autoruns	65 e.g. HKLM\Software\Microsoft\ Shows what programs are configured to run
		Windows\CurrentVersion\Run during system bootup or user login
	HKLM\SYSTEM	66 HKLM\SYSTEM \	information about the Windows system setup
		HKEY CURRENT CONFIG\
	HKLM\Software	67 HKLM\Software\	software and Windows settings, mostly
			modified by application and system installers
	HKLM\SECURITY 68 HKLM\SECURITY\	linked to the Security database of the domain
			into which the current user is logged on
	HKLM\SAM	69 HKLM\SAM\	reference all Security Accounts Manager (SAM)
			databases for all domains
	HKEY USER	70 HKEY USERS\	user profile actively loaded on the machine
		HKEY CURRENT USER\
	HKCR	71 HKEY CLASSES ROOT	information about registered applications,
			e.g. file associations and OLE Object Class IDs
	others	128 *	*
	4

Iterative Sequence Alignment (ISA)

Table 3 .

 3 Network Differentiation Scheme

	TYPE	ID Description
	DNS requests 129 *
	HTTP-traffic 130 *
	IRC-traffic	131 *
	SMTP-traffic 132 *
	P2P-traffic	133 *include some popular P2P types
	FTP-traffic	134 include FTP-control, FTP-data and TFTP
	SSL-traffic	135 associated to HTTPS connections
	NetBIOS	136 *
	TCP-traffic	137 TCP traffic other than those above-mentioned
	UDP-traffic	138 UDP traffic other than above-mentioned
	ICMP-traffic 139 *
	Listen	140 Listen on a port
	others	192 *

in aligning matching characters. A mismatch occurs if elements in the same column are not identical.

Table 4 .

 4 The Families and Characteristics of Malware Executables

	Family Name	NUM of variants NUM of executables
	Trojan-Downloader.Win32.CodecPack 13	48
	Trojan-Dropper.Win32.VB	12	28
	Trojan.Win32.VBKrypt	50	79
	Worm.Win32.VBNA	14	75
	Trojan.Win32.Refroso	21	27
	Trojan.Win32.Cosmu	9	26
	Trojan.Win32.Scar	7	21
	Backdoor.Win32.Bifrose	19	27
	Total	145	331

Table 5 .

 5 The Performance of Our DiffSig Comparing to HamsaHamsa respectively; The column "Detection rate" shows the detection ability of signatures to detect malware executables in testing set; The column "False Positive" presents the rate of treating normal application as malicious by applying generated signatures to benign syscall sequences. From table 5, we can see that our DiffSig can generate signature for any family while Hamsa can not generate signature for Trojan.Win32.Scar and Backdoor.Win32.Bifrose because the two families have no invariable token in their syscall sequences. And we can see that our DiffSig produces fewer signatures since our Diffhandle-signature is more generalized, that the detection rate of our DiffSig is much higher and the false positive rate is much lower. In summary, our DiffSig generates more generalized and accurate signature, and our Diffhandle-signature is more suitable to anti-obfuscation than token set signature of Hamsa. Comparing the computing performance and detection performance with current behavior graph methods is our future work.

	Family Name	Number of signatures Detection rate	False Positive
		DiffSig	Hamsa	DiffSig	Hamsa DiffSig Hamsa
	Trojan-Downloader.	1	3	95.8%	79.2% 0.045 0.135
	Win32.CodecPack
	Trojan-Dropper.Win32.VB 1	1	100%	78.6% 0	0
	Trojan.Win32.VBKrypt	2	6	93.7%	88.6% 0	0
	Worm.Win32.VBNA	2	5	93.3%	86.7% 0.045 0.18
	Trojan.Win32.Refroso	1	4	92.6%	74.1% 0	0.090
	Trojan.Win32.Cosmu	1	2	88.4%	76.9% 0	0
	Trojan.Win32.Scar	1	-	90.4%	-	0	-
	Backdoor.Win32.Bifrose	1	-	85.1%	-	0.045 -
	average	1.25	3.5	92.4%	80.1% 0.0169 0.068

Acknowledgments. This work is supported by Program No. IRT 1012, the NS-F of China Program No. 61202488, the Research Fund for the Doctoral Program of Higher Education of China No. 20124307120032, the NSF of China Program No. 61103194, and the NSF of China Program No. 61003303. We appreciate anonymous reviewers for their valuable suggestions and comments.


Jakub Breier
email: breier@fiit.stuba.sk

Ladislav Hudec
email: lhudec@fiit.stuba.sk

On Identifying Proper Security Mechanisms

Keywords: Risk Evaluation, Information Security, Security Standards, Security Mechanisms, ISO/IEC 27002 standard

Selection of proper security mechanisms that will protect the organization's assets against cyber threats is an important non-trivial problem. This paper introduces the approach based on statistical methods that will help to choose the proper controls with respect to actual security threats. First, we determine security mechanisms that support control objectives from ISO/IEC 27002 standard and assign them meaningful weights. Then we employ a factor analysis to reveal dependencies among control objectives. Then this knowledge can be reflected to security mechanisms, that inherit these dependencies from control objectives.

Introduction

Operational cybersecurity is becoming more significant area of Computer Science. It is difficult to demonstrate a progress in this area, all the systems connected to the Internet are periodically under attack and the statistics about successful attacks still show the same ratio. In [START_REF] Cybenko | Security analytics and measurements[END_REF] authors analyze the progress in the automobile safety and compare it to the computer security. It is easier to eliminate known threats that do not change over time, as in the automobile industry the adversaries are natural laws that remain the same. In terms of computer security there are human adversaries that are evolving over time, therefore it is impossible to define static goals and to reach them.

We have to define security mechanisms that will help us to face the actual threats. There are numbers of these mechanisms, some are very effective, others have greater costs, but provide necessary industry protection controls and a number of them becoming useless as the Internet and computer networks evolve.

According to Baker et. al. [START_REF] Baker | Is information security under control?: Investigating quality in information security management[END_REF], organizations tend to think more about quantity than quality. They are not aware, which mechanisms are the best for their purposes, so they often deploy as many as possible. Wrong mechanisms can actually add deficiencies to the system instead of increasing the security state.

In this paper we will try to find a way of defining proper security mechanisms for the organization. We will inspect the control objectives from ISO 27002:2005 [8] standard and assign one or more security mechanisms to each of 131 control objectives. We will also inspect dependencies between these mechanisms in order to correctly determine an evaluation criteria.

The main motivation for using security mechanisms is the clarity of their measurement. We cannot effectively measure the quality of control objectives implementation in the organization, but it is much easier with security mechanisms. If we have to use for example a mechanism called 'Implementation of authentication and authorization mechanisms -passwords, tokens, biometrics,' it is easy to decide whether it is fulfilled or not.

The overall goal is to determine whether the organization has satisfiable security controls in accordance to the ISO 27002:2005 standard and therefore it is able to demonstrate compliance with the ISO 27001:2005 [7] standard.

The rest of this paper is structured as follows. Section 2 provides an overview of a related work dealing with the problem of security mechanisms selection. Section 3 proposes our approach and describes methods used for choosing proper security mechanisms and for identification of relationships between them. Section 4 concludes this paper and provides a motivation for further work.

Related Work

In the field of security mechanisms and controls there are a few papers trying to propose an approach for their selection and implementation into the organization's information systems.

Singh ans Lilja [START_REF] Singh | Improving risk assessment methodology: a statistical design of experiments approach[END_REF] use Plackett & Burman (PB) design for determining the critical security controls [START_REF] Plackett | The design of optimum multifactorial experiments[END_REF]. This design requires minimum number of experiments to determine the effect of individual controls. For N controls it requires N+1 experiments. Each control can be implemented either as a low quality component or as a high quality component. These controls are then arranged in a matrix in a following way. Each row represents one experiment with numbers in columns either +1 or -1, indicating the control quality. Using these values together with the cost of each experiment we can determine the effect of particular security controls.

Authors compare 17 technical security controls, such as firewall, log analyzer, browser settings, etc.. They set up an experiment and provide an example of their method to prove its benefit in measuring impact of security enhancements.

Llanso [START_REF] Llanso | CIAM: A data-driven approach for selecting and prioritizing security controls[END_REF] introduces CIAM -an approach that provides an initial prioritization of security controls. His approach uses data related to security incidents, vulnerabilities, business impact, and security control costs. He selects security controls from NIST 800-30 [START_REF] Stoneburner | Risk Management Guide for Information Technology Systems[END_REF], assign them weights with support of security experts and estimate their efficiency against security breaches.

There are security standards, like the ISO 27002:2005 [8] or NIST 800-30 [START_REF] Stoneburner | Risk Management Guide for Information Technology Systems[END_REF] that provide a database of security controls. But they fall short on choosing proper controls for the organization and on evaluation of quality of these controls. They also do not take in consideration relationships and dependencies over the security controls.

In [START_REF] Castiglione | An enhanced firewall scheme for dynamic and adaptive containment of emerging security threats[END_REF] and [START_REF] Santis | An intelligent security architecture for distributed firewalling environments[END_REF] the authors deal with the similar problem looking at a more technical aspect -they introduce a scalable firewalling architecture based on dynamic and adaptive policy management facilities which enable the automatic generation of new rules and policies to ensure a timely response in detecting unusual traffic activity as well as identify unknown potential attacks.

Methods

This section provides an overview of methods for selection of security mechanisms. Our approach emanates from the ISO/IEC 27002:2005 standard. We identify security mechanisms for each control objective from this standard and consider the importance and implementation quality of these mechanisms.

This section is divided into three subsections, the first one, the 3.1, provides the overview of the proposed weighting methods, the second one, the 3.2, describes relationships between security mechanisms and the last one, the 3.3, explains how to select and evaluate them.

Security Mechanism Weighting

Since there are many security mechanisms, an organization has to decide, which of them are useful and which are ineffective in contribution to its security goals.

There are eleven security clauses in the standard and each one is dealing with the different part of security, we have to use different types of security mechanisms. A NIST classification of security mechanisms constitutes three categories [START_REF] Stoneburner | Risk Management Guide for Information Technology Systems[END_REF]. From our point of view, mechanisms used in our model also fits to one of these categories, therefore it is not necessary to use a new classification. Every security mechanism can be assign to one of the following groups: Management, Operational or Technical. It is much easier to measure the quality of the technical mechanisms, like firewall or intrusion prevention system, but it is impossible to quantify the quality of management or operational mechanisms, like information security policy. Because of character of ISO/IEC 27002 security clauses, that are mostly policy-based, we cannot measure all the mechanisms incorporated in the evaluation process automatically. But we can significantly improve the objectivity and simplicity of the evaluation.

We have to inspect them in two ways: how do they prevent against security breaches and how do they contribute to control objective fulfillment. Llanso [START_REF] Llanso | CIAM: A data-driven approach for selecting and prioritizing security controls[END_REF] introduces an approach for selecting and prioritizing security controls (in the terminology of this paper, we use the term 'security mechanism' instead of the 'security control' because the latter term could indicate the usage of NIST 800-30 security controls). First, he computes weights of these controls, using three component weights -Prevention, Detection and Response (P/D/R) against an attack. The weight of a control i is computed by following equation:

RawW eighting i = wP i .owP i + wD i .owD i + wR i .owR i (1)
where overall weightings have values owP i = 0.5, owD i = 0.25, owR i = 0.25, because prevention is more valuable than the other two. Control's contribution to these three actions (wP i , wD i , wR i ) are scores. These are determined by subject matter experts (SMEs) and each of them holds a value in interval < 0, 1 >.

After this step, he computes relative weighting as a ratio between one security control and all the other controls:

RelativeW eighting i = RawW eighting i n j=1 RawW eighting j (2)
Then he is able to compute the priority, using relative weightings, scores, attack step frequencies, CVSS impacts and costs. Since we do not have the cost dimension in our model, we will not use the whole prioritization approach. We will adopt the relative weighting process and adjust it in a meaning of contribution of security mechanisms to control objectives. We are not weighting these mechanisms with respect to possible attacks, but we are looking at how well do they assure the control objective function. So instead of P/D/R components we will use Implementation, Maintenance and Policy (I/M/P) components. The equation remains the same, just with another components and with another overall weightings:

RawW eighting i = wI i .owI i + wM i .owM i + wP i .owP i (3)
where overall weightings have values owI i = 0.6, owM i = 0.20, owP i = 0.20. The implementation is the most important component, whithout them the maintenance components does not have a meaning, so we have to take them into consideration. That is why it has the highest value. The maintenance ensures the correct function of the control objective and the policy component specifies, whether the security mechanism supports also a formal policy. The relative weighting formula remains the same as in Equation 2. Table 1 presents the "Controls against malicious code" control objective from "Communications and operations management" security clause. We assigned five security mechanisms to this control objective and used the same approach for determining weights as Llanso [START_REF] Llanso | CIAM: A data-driven approach for selecting and prioritizing security controls[END_REF] did. We constituted a group of security professionals for this purpose, so they could discuss if the security mechanisms are properly assigned and what values can they achieve in each of three components. The last column represents a relative weighting of particular security mechanisms. Each component weight has a value on a discrete scale from 1 to 10, 1 means minimal importance, 10 is the most significant importance.

Correlation of Security Mechanisms

There is another dimension in the security mechanisms selection problem -a correlation between individual mechanisms. We cannot look on particular mechanisms as on the independent attributes, each one can affect the implementation of another one. It is usually better to have implemented for example three of them at an average implementation quality level than just one individual mechanism at a comprehensive level [START_REF] Gordon | The economics of information security investment[END_REF]. The cost is also a dimension that plays significant role in the above statement -the maximal quality of the implementation demands usually excessive resources. Commonly, it is more efficient to choose the way of implementing reasonable amount of mechanisms at a reasonable quality. Since there are 131 control objectives and around 3-5 security mechanisms assigned to each of them at average, it would take a huge amount of time to determine correlation among each pair. We decided to choose a higher level of abstraction and to inspect a correlation between control objectives. We integrate this part of the model with the protection against security breaches, stated in the beginning of this section.

Verizon publishes Data Breach Investigations Reports [1] every year. It contains statistical records of incidents collected from various companies, divided into categories, providing detailed information about the overall state of the cyber security in our society.

We will use the Top 10 threat action types by number of breaches from this record and inspect, how particular control objectives provide prevention against these breaches. Ideal for this purpose is the Factor Analysis (FA) method, which describes variability among observed correlated variables. In this method, the measured variables depend on a smaller number of latent factors. Each factor can affect several variables in common, so they are known as common factors. Particular variables can be then represented as a linear combination of the common factors. The coefficients in this combination are known as loadings. FA can be used to reduce the redundant information contained in several correlated variables. However we will use it to reveal these correlations and to insert these dependencies in our measurement model.

To save the space, we will not use the whole set of control objectives, but we will pick one sample objective from each security clause. These are listed in Table 2 among columns in the following order: Information security policy document (CO 1 ), Confidentiality agreements (CO 2 ), Inventory of assets (CO 3 ), Information security awareness, education, and training (CO 4 ), Physical entry controls (CO 5 ), Disposal of media (CO 6 ), User password management (CO 7 ), Input data validation (CO 8 ), Reporting information security events (CO 9 ), Business continuity and risk assessment (CO 10 ), Protection of organizational records (CO 11 ). The evaluation is based on a discrete scale from 1 to 10, 1 means no protection and 10 means maximal protection. We can see that there are control objectives which are important in the view of these breaches, like Information security policy document, Information security awareness, education, and training, or User password management. On the other hand, there are objectives that have negligable importance, like Inventory of assets or Business continuity and risk assessment. The purpose of this evaluation is not to determine the control objectives' significance, but to reveal possible hidden relationships between them.

Then we can reflect these findings in the security evaluation.

Now we can use the factor analysis on the matrix obtained from Table 2. Besides other important characteristics we get the Pearson's correlation matrix. In this matrix we can see dependencies between each two control objectives:

                  CO 1 CO 2 CO
                 
Table 3 shows us the unrotated component matrix, consisting of three main factors. This matrix represents the significance of elements within each factor. For better visualisation, the results are stated in Figure 1. By inspecting factor 1, we can see that it depends on the following control objectives: Information security policy document, Confidentiality agreements, Information security awareness, education, and training. It means that these control objectives are somehow bounded together from the view of security breaches. Factor 2 has higher loadings for control objectives Inventory of assets, Information security awareness, education, and training, and Disposal of media. The last factor has higher loading only for Input data validation, so we can say there will be no dependence emanating from this factor.

Obviously, the dependence cannot be determined only by mathematical methods because of the character of particular control objectives. For example, if we have an objective that supports implementation of antivirus software and the other objective, implementing periodical software updates, these are clearly highly correlated. However, we can say that the second one supports the first one highly, but it does not work in the opposite way. Software updates are not affected by implementation of antivirus software, so there is only one-way dependence. We have to use a group of security professionals to determine the character of dependencies.

We can explicate the results in the following way. Information security policy document is clearly an important control objective, Confidentiality agreements and Information security awareness, education, and training objectives depend on it. The latter two do not contribute to the first one, so there will be only one way correlation. Similarly, they do not have cross-dependency. Disposal of media and Inventory of assets are dependent on Information security awareness, education, and training. Disposal of media is also dependent on Inventory of assets. So we have five relationships in total, each of them is only one way dependence. Now we can use the correlation values to affect the evaluation of security mechanisms.

In Equation 4we can see the evaluation of control objective i. S COi is the score of control objective i, obtained by the evaluation, RW COi is its weight, S COj is the score of control objective j, that is correlated with i and COR ij is the correlation between them. It is easy to see that the fraction can gain values from interval < 0, 0.5 > and can significantly improve the value of the final score, if both the correlation and the correlated control objective's score are high.

co1 co2 co3 co4 co5 co6 co7 co8 co9 co10
F inalScore COi = RW COi * S COi + S COj * COR ij 1 + COR ij (4)
The score of S COi depends on evaluation of security mechanisms associated to the control objective i and it is the product of the security mechanism's weighting and its score. The calculation of S COi is stated in Equation 5. The score of the security mechanism's implementation (S ( M j )) is determined by security analyst and can have a value in interval < 0, 1 >, 0 means no implementation and 1 means that it is implemented well, tested and verified in a real environment.

S COi = n j S Mj * RW Mj (5)
The evaluation of control objective's weight (RW COi ) is not in the scope of this paper, since we do not propose the complete evaluation model, we only designate a selection method for security mechanisms and identify their relationships and dependencies.

Security Mechanism -Selection Process and Evaluation

To summarize the previous sections, the assignment of security mechanisms to control objectives consists of following steps:

1. Assignment of the security mechanisms with respect to control objective's description. Usually there are three to five mechanisms supporting one control objective. 2. Definition of the weight of each mechanism -this parameter shows us, how important is this mechanism for the contol objective fulfillment. We use the I/M/P model with three weight components for this purpose. The sum of relative weights of mechanisms is 1. 3. Determination of weights of control objectives -these weights have to reflect the organization's security goals, for example necessary requirements for confidentiality, integrity or availability of organization's assets. 4. Estimation of dependencies with the factor analysis method, adjusted by the security analyst's judgement.

Conclusions

In this paper we proposed a way of choosing proper security mechanisms that will protect the organization's assets. We defined a method for the determination of importance of these mechanisms by assigning weights. These weights express, how well the particular mechanism contributes to the implementation, maintenance or policy fulfillment of the control objective, to which it was allocated. The whole model consists of about four hundred security mechanisms, that were allocated for each of 131 control objectives from the ISO/IEC 27002:2005 standard.

We also proposed the approach for determining relationships between security mechanisms. For this purpose we choosed the factor analysis, a statistical method that can reveal hidden correlation among observed variables. We explore these correlations on the control objectives layer, because inspecting every security mechanism would be exceedingly comprehensive and space consuming. The factor analysis gave us meaningful results that need to be further adjusted by security professionals to express the dependencies correctly.

Verendel [START_REF] Verendel | Quantified security is a weak hypothesis: a critical survey of results and assumptions[END_REF] claims that quantitative security evaluation is still very unclear and it is almost impossible to validate the methods against empirical data. We would like to confute this claim by building a quantitative evaluation method that will be based on a number of smaller components, that work together and could be verified standalone. In this paper we presented the component dealing with the security mechanisms problem.

In the future, we would like to use the results of this work to construct a security evaluation system, that will measure the real security state in an organization by evaluating the quality of implemented security mechanisms.

Fig. 1 :

 1 Fig. 1: Components and control objectives.

Table 1 :

 1 Controls against malicious code.

	Security Mechanism	wI wM wP RW
	Implementing operating system policies prohibiting the	9	5	7	0.244
	use of unauthorized software, downloading unsigned ex-
	ecutable files and working with other than data files on
	workstations without privileges.
	Implementing strong account policies with separated	7	3	9	0.206
	privileges and clear accountability and non-repudiability.
	Deployment of antivirus software on each system with the	9	9	2	0.238
	real-time check of unwanted code and periodical update
	of this software.
	Ensuring that installed programs are up to date.	3	9	7	0.156
	Providing business continuity plan -backuping and ver-	3	7	9	0.156
	sion management.

Table 2 :

 2 Control objectives' protection against Top 10 security threats.

	X X Breach X Keylogger/Form-X X X X X Sec. Clause X	CO1 CO2 CO3 CO4 CO5 CO6 CO7 CO8 CO9 CO10 CO11 7 1 1 7 3 1 5 5 5 1 3
	grabber/Spyware
	Exploitation of default	7	3	1	8	3	1	9	1	4	1	3
	or guessable credentials
	Use of stolen login cre-	3	1	1	5	7	3	7	1	5	1	5
	dentials
	Send data to external	5	1	1	7	3	3	5	1	3	1	5
	site/entity
	Brute force and dictio-	7	1	3	9	5	3	9	1	5	1	5
	nary attacks
	Backdoor	5	3	1	7	5	1	5	5	5	1	3
	Exploitation of backdoor	5	1	1	5	3	1	5	3	5	1	7
	or command and control
	channel
	Disable or interfere with	7	3	1	7	8	1	5	2	5	1	5
	security controls
	Tampering	8	3	1	8	3	1	1	1	5	1	3
	Exploitation of insuffi-	7	3	1	8	7	1	5	1	3	1	5
	cient authentication

Table 3 :

 3 Unrotated component matrix.

	F1	F2	F3
	CO1 0.858 0.313 0.048
	CO2 0.690 -0.145 -0.434
	CO3 -0.128 0.851 0.436
	CO4 0.693 0.720 -0.023
	CO5 -0.195 0.040 -0.303
	CO6 -0.727 0.540 -0.027
	CO7 -0.317 0.432 0.082
	CO8 0.176 -0.573 0.671
	CO9 -0.081 -0.188 0.413
	CO10 -0.720 -0.121 -0.218
	CO11 -0.506 0.059 -0.073

Acknowledgment. The paper was prepared with partial support of research grant VEGA 1/0722/12 entitled "Security in distributed computer systems and mobile computer networks".


Minhuan Huang

Lingxia Liu
email: lingxia_liu@tom.com

Dongxia Wang
email: dongxiawang@126.com

Jinjing Zhao
email: misszhaojinjing@hotmail.com

SA4WSs: a Security Architecture for Web Services

Keywords: A Security Architecture for Web Services Web service, Security, Architecture

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

Introduction

As a new Web application model, Web service is heterogeneous, dynamic and loose coupling, and introduces a great deal of special threats to Web service applications, and makes that traditional security techniques are inadequate to solve the security issues in Web services.

In recent years, many research institutions, organizations and companies devote to the research of security for Web Services. Organizations and research institutions for Standardization mainly concern in security standards for Web service. The academic community tries to solve the security issues from the theoretical aspect. Middleware companies and open source organizations try to provide security protection tools for customers by providing a set of software or toolkit.

In the paper, we focus on how to build security architecture for Web services to meet the security requirements of Web service applications. On the basis of the improved approach, a security architecture for Web services named SA4WSs (Security Architecture for Web Services) is proposed. The architecture supports separating function implementation of service from non-functional implementation of service, meanwhile ensure the portability of the platform.

The remainder of this paper is organized as follows. In section 2, the related works are reviewed. In section 3, the security architecture for Web services is set forth. Finally, in Section 4, we conclude the paper.

Related Works

Many Organizations for Standardization, research institutions and companies research on the security architecture for Web services.

Security Standards

In order to assure the end-to-end security for SOAP message and improve the interoperability of Web service, OASIS and other organizations define the Web Service Security model consisting of multiple standards [START_REF] Gerié | Standard Based Service-Oriented Security[END_REF]. The model is insufficient. It is only to protect the two trust sides to communication by a secure connection, and not address the security problem caused by anonymous consumers invoking Web service or SOAP API. W3C proposed a standard named XML Signature Syntax and Processing specification, which defines how to sign part or all of one XML document [START_REF]W3C: XML Signature Syntax and Processing Version 2[END_REF]. W3C also proposed a standard named XML Encryption Syntax and Processing, which defines how to encrypt part or all of one XML document [START_REF]W3C: XML Encryption Syntax and Processing Version 1[END_REF].

2.2

Security Architecture U.S. DISA (Defense Information Systems Agency) released a specification named "Network Centric Enterprise Services security architecture (version 0.3)" in 2004, provides a service-oriented information security reference architecture to ensure the security of services in network-centric environment [START_REF]A Security Architecture for Net-Centric Enterprise Services (NCES) Version[END_REF]. IBM proposes the service-oriented security reference modeling and architecture based on its own SOA infrastructure and business scenarios to cope with information security issues for work flows [START_REF] Buecker | Understanding SOA Security Design and Implementation[END_REF]. The service-oriented security architecture proposed by IBM is meaningful, but its portability is restricted because it relies heavily on its own SOA technologies and products.

GSI provides basic security services for grid computing environments. It is an integrated solution to solve the security issues in grid computing and becomes a standard of GGF [6]. The major security functions in GSI include Certificates, Mutual Authentication, Confidential Communication, Securing Private Keys, and Delegation and Single Sign-On. GSI also has some disadvantages, such as frequent, complex and poor scalable authentication between entities.

OGSA is proposed by Ian Foster et al. on the basis of five-level hourglass structure and Web services [START_REF] Foster | The Open Grid Services Architecture, Version 1.5[END_REF]. A basic premise of OGSA is that everything is represented by a service, not excepting security. All kinds of security mechanisms such as encryption, access control, and audit are represented as services to facilitate the implementation of the security-related policies.

The service oriented security architecture named SOSIE presented by [START_REF] Opincaru | Service Oriented Security Architecture[END_REF] is realizing the security functions into modular, stand-alone security services. The article [START_REF] Sandrogerić | Security of Web Services based Service-oriented Architectures[END_REF] addresses the question of security mechanisms that are usually used and that can be used in Web services based SOA implementation from standardized as well as technical and implementation point of view, and gives an overview of SOA security solutions. The article [START_REF] Peterson | Service Oriented Security Architecture[END_REF] provides a set of software architecture viewpoints that allow security architects to construct a holistic system design based on a set of views. Other related works focus on the special issues of security service [START_REF] Sang | A Survey and Taxonomy of Lightweight Intrusion Detection Systems[END_REF] [12] [START_REF] Shuyuan | A Thief among Us: The Use of Finite-State Machines to Dissect Insider Threat in Cloud Communications[END_REF].

Supporting Platform

In addition, some research institutions and companies have also developed multiple security platforms and middlewares for Web service. Microsoft proposed a solution for Web services security problems named WSE (Web Services Enhancements) on the basis of .NET platform [14]. WSE is a service security middleware for .NET platform, including authentication and encryption library. It allows developers to develop secure Web service by implementing the latest WS-Security specification.

Globus Toolkit is the reference implementation of OGSI. It provides basic security services required by grid computing, including message protection, authentication, authorization, and audit/log [START_REF]The Globus Alliance[END_REF].

The Apache WSS4J project provides a Java implementation of the primary security standard for Web Services, namely WS-Security [START_REF][END_REF]. WSS4J ships with handlers that can be used in Axis-based web services for an easy integration.

3

Security Architecture for Web Services

Improved Security Implementation Approach

Web service applications face threats including the threats the Web services platform faced where service located and the threats the service implementation faced, i.e. common threats the platform faced and specific threats the application faced. The first approach [START_REF] Opincaru | Service Oriented Security Architecture[END_REF] can cope with specific threats the application faced, but cannot cope with the common threats the platform faced. The second and the third approaches can cope with the common threats the platform faced, but cannot cope with the specific threats the application faced. We try to improve the three approaches to meet the security requirements of Web service applications. The first approach cannot cope with a lot of attacks (such as SOAP message replay attacks) the platform faced, no matter how to transform it, because the communication between service implementation and resource gateway is no longer via SOAP message. The third approach is similar to the firewall, and it is not suitable to add application-specific security mechanisms to cope with specific threats the application faced.

Therefore, we focus on improving the second approach to cope with both common threats the platform faced and specific threats the application faced. Analysis on the Web services platform showed that the platform can be logically divided into two parts. One part of it is Web services runtime environment, mainly providing the functions including deployment, management, publishing and finding for Web service. The other part is resource gateway, which are a set of interfaces between Web services runtime environment and service implementation. It provides the protocol conversion functions for specific application-related invoking. In view of the above analysis, an improved security implementation approach is proposed, as shown in Figure 1.

Client Service Implementation

Web Services Platform

Web Service Runtime Environment

Resource Gateway

Specific Security mechanisms

Common Security mechanisms

Fig.1. The improved security implementation approach

In this approach, the security mechanisms are divided into two parts. One part of it is common security mechanisms, which is not relevant to applications and resides in the Web services runtime environment. The other part is specific security mechanisms, which is relevant to applications and resides in the resource gateway. The improved approach not only remains separating functional implementation from nonfunctional implementation, but also assures the portability of the platform.

3.2

Architecture A security architecture for Web services named SA4WSs is proposed, as shown in Figure 2. In the architecture, the module of Basic Security Services provides basic services for implementing the basic security functions, including authentication, authorization, access control and audit, etc. [START_REF] Opincaru | Service Oriented Security Architecture[END_REF]. The module of Security gateway is responsible for the application-specific security functions, and the service implementation is responsible for the business logic. The Security gateway interacts with the service implementation via various protocols (The protocol type is decided by the type of service implementation).

Conclusion

In this paper, a security architecture for Web services is proposed. The architecture described in the paper supports separating the functional implementations from the non-functional implementation, and ensures the portability of the platform. SA4WSs has been partially implemented based on Apache Axis. Future work consists of implementing a Web Services security supporting platform to support the development and management of security Web service.

Fig. 2 .

 2 Fig.2. Security architecture for Web services

Acknowledgements

This research is supported by National Natural Science Foundation of China (Grant No. 61100223 and No. 61271252).


Xiaoxia Sun
email: xiaoxia83@gmail.com

Hua Chen

Jinjing Zhao
email: misszhaojinjing@hotmail.com

Minhuan Huang

A Test Case Generation Technique for VMM Fuzzing

Keywords:

In this paper, we first give a short introduction to the security situation of virtualization technology, and then analyze the implementation challenges of the CPU virtualization component of a hybrid system virtual machine with support of running a guest machine of the IA-32 instruction set. Based on a formal definition of the CPU's execution state, we propose a fuzzing test case generation technique for both the operands and operators of instructions, which can be applied to fuzz testing the virtual machine monitor (VMM) of a hybrid system virtual machine.

Introduction

In the name of cost savings, more and more critical systems and business systems have been virtualized. Growing interests in cloud computing will fuel further demand on virtualization. Thus the attentions on virtualization system security, specifically on business virtualization system have grown as interest has grown.

As a most-widely used virtualization technology, system virtual machines make it possible that multiple OS environments (guest machine) coexist on the same physical computer (host machine), and the ISA (instruction set architecture) of guest machines can be different from the host machines. This technology not only provides huge saving of hardware costs, but also brings many security advantages. Virtualization can offer isolated execution environment make services of different security policies running in separate virtual machines which is actually the same computer, without any interference of each other.

Virtual Machine (VM) has become a new battle of security attacks and defenses [START_REF] Ormandy | An Empirical Study into the Security Exposure to Host of Hostile Virtualized Environments[END_REF][START_REF] Hori | Guest Editorial: Frontiers in Insider Threats and Data Leakage Prevention[END_REF][START_REF] Shuyuan | A Thief among Us: The Use of Finite-State Machines to Dissect Insider Threat in Cloud Communications[END_REF]. More and more malwares and attacks turn to choose VM as their targets, and in recent years, many traditional defense techniques have their corresponding counterpart of VM platforms, such as VM-based intrusion detection system, intrusion prevention system and honeypot. However, the security of virtual machine [START_REF] England | Virtual machines for enterprise desktop security[END_REF] itself is still a problem to solve. On the other hand, the business system has high requirements on security. The system needs to give the right users access to the right resources at the right time, protect sensitive business data, keep applications available and keep away from malicious or fraudulent use.

An increasing number of virtualization system vulnerabilities have been reported. As reported by the IBM X-force [START_REF]IBM X-Force Threat Reports[END_REF], nearly one hundred vulnerabilities on virtualization system have been disclosed every year since 2007. And among 40% of them have high severity, which is easy to be exploited, and provide full control over attacked systems due to the intrinsically high privilege level of virtual machine monitor (VMM) itself. Among all these vulnerabilities, the VMM vulnerabilities and VMM escape vulnerabilities are of the most severe, since they will compromise all guest VMs. For instance, by modifying the processor status register, a local attacker can cause the Xen kernel to crash [6], and an error in the virtual machine display function on VMware ESX Server allows an attacker in a guest VM to execute arbitrary code in the VMM [7]. More and more attention has been paid to VM security, especially VMM security.

The rest of the paper is organized as follows: Section 2 discusses implementation challenges of IA-32 ISA based VMM. Section 3 introduces the test case generation technique for VMM fuzzing. Section 4 draws the conclusions.

Implementation challenges of IA-3ISA based VMM

To provide an isolated execution environment for guest OS, the system VM needs to interpret, translate and emulate the Instruction Set Architecture (ISA) of guest machine. The guest ISA in this paper is the pervasive Intel IA-32 instruction set, a Complex Instruction Set Computing (CISC). Compared with the Reduced Instruction Set Computing (RISC), IA-32 is more complex in instruction type (e.g. different kinds of memory access instructions exist), and complicated instruction encoding method .The encoding length of IA-32 is not fixed and there is redundancy at the opcode level. Instruction prefixes can further complicate the instruction semantics. All of these lead make it hard to emulate the IA-32 instructions. Therefore, IA-32 cannot be virtualized efficiently. For example, to guarantee the security of the virtualization system, some special handle needs to be employed to some instruction of IA-32 ISA.

The inherent complexity of IA-32 instructions makes it very hard to precisely model the semantic behavior of IA-32 instructions. In modern processers, there are two types of instructions according to execution mode, privileged instructions and non-privileged instructions. The privileged instructions only can be executed in the system mode, and when executed in the user mode, it will cause a trap. However, there are some non-privileged instructions in IA-32, may access some sensitive resources in the CPU, and modify the resource configuration of the system. We call these sensitive instructions as critical instructions [START_REF] Popek | Formal Requirements for Virtualizable 3rd Generation Architectures[END_REF]. Robin and Irvine [START_REF] Robin | Analysis of the Intel Pentium's Ability to Support a Secure Virtual Machine Monitor[END_REF] have figured out there is seventeen critical instructions that cannot be efficiently virtualized, which can be divided into two categories: the system-protection instructions and register-sensitive instructions. The system-protection instructions may access and modify the memory allocation system, including LAR, LSL, VERR, VERW, POP, PUSH, CALL, JMP, INT n, RET STR and MOVE. And the register-sensitive instructions may access and modify the configuration or CPU state register, including SGDT, SIDT, SLDT, SMSW, PUSHF and POPF. These instructions may have side effect, that is to say, the execution of an individual instruction may alter values of CPU status register (e.g. EFLAGS), thus may have an effect on the behavior of other instruction implicitly.

To guarantee the security of the whole VM system, VMM have to introduce a socalled scan and patch mechanism to detect such critical instructions and when execute these instructions, trigger a trap instead. Then the VMM handle the trap by emulating these instructions properly.

It is hard to prove a VMM is security in formal, so we need tests to validate the security of VMM. It was proved that fuzzing [START_REF] Sutton | Fuzzing: Brute Force Vulnerability Discovery[END_REF] is a useful test method for many systems, especially when input space is rather large. In this paper, we employ the fuzzing for validating the security of VMM.

From above discussion, it is prone when executing the critical instructions on VMM, so we can conclude that the key aspect to test whether a VMM is security is test the execution of the critical instructions. In this paper, we focus on testing such critical instructions. In next section, we will introduce the proposed test case generation technique on VMM fuzzing.

Test case generation and execution

Test procedure overview

The machine can exist in any one of a finite number of states where each state has four components, we represent the state of the abstract machine with the tuple s = (PC; R; M; E). The registers state R is a mapping from registers to their values stored there. The memory M is a mapping from memory addresses to values the particular location store. M store the instructions and R store data, which is similar to text section and data section. The program counter PC can refer to any memory address where stored the next instruction CPU is to execute; E is to denote the termination of the execution or exception. In this way, the CPU can be regarded as a finite state machine.

Virtualization transparency characteristics mean that one cannot tell whether a program is executed in physical machine or a virtualized one. According to the transition system definition given above, a virtual machine is transparent if and only if for any possible equivalent beginning states pairs (denoted as S b and S b '), that is, after arbitrary legal instructions executed simultaneously on the physical machine and virtual machine from same beginning state S b , the states both machines reach (denoted as S e and S e ') are semantically equivalence. By feeding testcases mutating the type of instructions, prefixes and operand instructions, we can find a crash report or get both final states and then compare them to find differences. A difference always indicates a virtualized machine have a violation of Virtualization transparency, which means the final states are not same with same beginning state and same operation. Fig. 1 shows the overview of the test procedure.

Test case generation and execution

Test case is a small piece of assembly programs. We use a hand written xml template to automate the test cases generation procedure, and then define some macros to generate random operands and prefixes of a particular instruction. Both the memory and register are initialized by mapping with random data at first. It's worth noting that we do not need to allocate the entire address space because only part of it may vary. After a preprocessing process, all the macros representing a variable fuzzing component have been replaced with concrete value. We can modify the number of the number of generated test cases directly in our preprocessing procedure, and also customize the test procedure. An example template is in Fig 3 .   <testcase ring="0"> <ring0> mov $0x200, %eax; orl FTG_BITS32, %eax; mov %eax, %cr4; </ring0> </testcase> Fig. 3 Template example We only test a single instruction, and the other instructions are designed for the machine to reach a testing state, which play a role of providing execution contexts for the fuzzed instruction. Our final test cases consist of a bootable kernel, a test case program, some initialization code, which initialize the state of the environment, and transfer the control to the fuzzed instruction. For this reason, we start by executing the test-case program only in one environment and, as soon as the initialization of the state is completed, we replicate the status of the registers and the content of the memory pages to the other environment. Then we execute the code of the test case in the two environments and at the end of the execution, we compare the two final states. Utilizing the built-in snapshot functionality of virtual machine, we can easily get the final state.

The technique we proposed can be used to find VMM crash bugs or the VMM transparency violation defeats. For the latter, we must audit manually to confirm whether it is the VMM's fault or not because it may be a result of undefined behavior in specifications of an ISA.

We choose the 32bit protection mode of CPU to test herein, but for the other modes ( the real mode, the virtual 8086 mode, and system mode) which are used less frequently and thus perhaps more buggy resulting from less testing efforts have made, this technique also works with little changes.

Fig. 1 Fig. 2 .

 12 Fig.1The overview of test procedure

adfa, p. 1, 2011. © Springer-Verlag Berlin Heidelberg 2011

Conclusion

In this paper, we first introduce the background of VM and VM security, and then fig ure out the challenges of implementing an IA-32 ISA based VMM. Based on these di scussions, we propose a novel test case generation technique for VMM fuzzing, whic h is focus on testing the critical instructions in IA-32. Benefited from the novel test ca se generation, the proposal in this paper can find the potential vulnerabilities with few er test cases compared with other test case generation techniques.