Hoon Ko

Goreti Marreiros
email: goreti@isep.ipp.pt

Zita Vale

Jongmyung Choi
email: jmchoi@mokpo.ac.kr

A Study on Context Services Model with Location Privacy

Keywords: Context-Aware, Context-Services, Location Privacy, OTP (One Time Password), Security

A lot of smart context-aware services would be adopting location information as context information. However, the location information is also very important information to be protected for users' privacy, security, and safety. In this paper, we propose One Time Password (OTP) in the communication between users' devices and network devices such as APs. By using this approach, APs does not keep user specific information but OTP values, so that attackers cannot get user information even though they access to the log files in APs. We also introduce context-aware service scenario and context information for the service.

Introduction

Micle Altschul, a corporate lawyer of Cellular Telecommunications & Internet Association (CTIA), which is an international association of Wireless Communication Enterprise and Wireless Services Provider, warned the privacy problem in mobile communication. He advised not to use commercial mobile services through open WiFi hotspots such as Starbucks WiFi [1]. This is because the policies and technologies for privacy protection are different among the service providers. The simple use of WiFi can reveal some user's privacy information such user's location. Actually, Sky Hook developed software that can calculate user's location in 20 meters radius using triangulation method of WiFi hotspots [1]. Another example is WaveMarket. This company has cooperated with wireless service providers and has been providing the location-based services which tracks the locations where family members or friends area. The most popular method for protecting location privacy is to use informed consent policies, in which companies let users know what information they get about users and users' locations and get consent for that. Although they try to use these policies, some arguments have been continually being issues, because disobedience of these policies may break all the privacy protection. The problem is that they have hardly mentioned technical issues for location privacy in WiFi. Assume that attackers get and analyze log files or configuration files in network devices, and then they can get users' information including user locations and their routes [2].

In this paper, to solve location privacy problems, we propose a method of using One Time Password (OTP) in the communication between a user's device and network devices. Once the user moves from one place to other place, all user information will be erased in the log files, and only OPT values are left. This approach is totally different from the existing systems, in which all information is kept in their log files. Therefore, if attackers look inside the log files, they cannot get user specific privacy information. The only information they can get is the OTP values. If network devices have some troubles, the administrator can check the log files and the OTP values to find out the causes of the troubles, but he/she cannot identify users from the OTP values, either. The remainder of the paper is organized as follows. In Section 2, we discuss other research that is closely related to our work. Then we define the location privacy in context-aware systems in Section 3. After that we show some discussion issues for the location privacy in context-aware systems in Section 4. Finally, we reveal the conclusions of our work in Section 5.

Related Work

John Krumm [1] explains location privacy problem of services which provide user location information. In his paper, he defines that protecting from let other users know where user is and where path user had can be function and availability. He suggests some solutions to solve using anonymity, spatial / temporal degradation, specialized queries, and configuration privacy. However he does not consider encryption and access control. Therefore, if attackers access the log files, they can get user information rather easily. Hulsebosch et al. [2] introduce location privacy problem from anonymous accesses for users and user contexts on ambient context. In their paper, they suggest a process distinction at user location through a security level definition. Garreti Brown and Travis Howe [3] propose a solution of social network and contextaware spam.

In their work, they mention problems of the location based service of Facebook user, and they argue unnecessary context named context spam receiving problem, by exposing of the user location. Those three researches introduce location privacy problems by their own approaches [8], but they have a common assumption, which is that if users do not leave their information in network devices such as servers and access points (APs), then users' routes or their location privacy do not matter. However, during the process for mobile communication, the mobile devices have to get helps from APs and network devices around users, and these requests cause privacy information to be open [9]. Currently, most of smart mobile devices such as iPhone and iPad are connected to the network via wireless APs and other network devices in the public area, and the users' location may be revealed by analyzing the log files of these network devices.

Location Privacy in Context-aware System

Location-based Context-aware Service Scenario

Context-aware systems provide intelligent services, and most of them adopt user location as context information. In our work, we introduce a context-aware service which uses location information, and we show location privacy protection method.

A. One-Time Password (OTP)

A OTP is a password which is valid for only one login session or transaction. OTP usually avoids a number of shortcomings that are associated with traditional and static passwords. The most important shortcoming that is addressed by OTP is that, they are not vulnerable to replay attacks. This means that if a potential intruder manages to record an OTP that was already used to log into a service or to conduct a transaction; he or she will not be able to abuse it since it will be no longer valid. On the downside, OTPs are difficult for human beings to memorize. Therefore they require additional technology in order to work [13]. OTP generation algorithms typically make use of randomness. This is necessary because otherwise it would be easy to predict future OTPs from observing previous ones. Concrete OTP algorithms vary greatly in their details. Various approaches for the generation of OTPs are listed below.



Based on time-synchronization between the authentication server and the client providing the password (OTPs are valid only for a short period of time)  Using a mathematical algorithm to generate a new password based on the previous password (OTPs are, effectively a chain and must be used in a predefined order).



Using a mathematical algorithm where the new password is based on a challenge (e.g., a random number chosen by the authentication server or transaction details) and/or a counter.

There are also different ways to make the user aware of the next OTP to use. Some systems use special electronic tokens that the user carries and that generate OTPs and show them using a small display. Other systems consist of software that runs on the user's mobile phone. Yet other systems generate OTPs on the server-side and send them to the user using an out-of-band channel such as SMS messaging. Finally, in some systems, OTPs are printed on paper that the user is required to carry with them [13].

Step (1) of OTP application in Location Hide Algorithm (LHA) in Section 4.2 points this method which connects OTP value to devices ID.

B. Scenario.

Before Shella goes to bed, she inputs her tomorrow's plain in her device: 1) to wake up at 7 am, 2) to visit a cafe at 8 am near her house, 3) to meet her friend at 9 am, 4) to buy a Jacket in black in A shop, a brown boots in B shop, and 5) to visit C book store and check some books which have been published recently. [6][7] [Figure 1].

In the scenario, we have three things to consider as shown below. Case 1 and 2 show some context-aware services using location information, and Case 3 shows location privacy issues in these services.

Case 1: Shop A and Shop B are able to send new information to Shella as soon as she shows up near their stores. Furthermore, they can recommend some products to her based on her purchase history at their stores.

Case 2: Book store C also sends the new book list to her according to her book purchase history and her favorite genre.

Case 3: Location Privacy: Shella uses wireless network by connecting to wireless APs when she is in a cafe, on Outlet Street, and in bookstore. And this wireless connection enables her to get smart services from stores. However, attackers can get her locations and her movement route by analyzing data stored in APs. Fig. 1 shows the service scenario in detail, and context information for the services. In that figure, Shella moves from one place to new place near AP pn2, and she gets services from stores near her location. Before she arrives at pn2, she got services from other pn#, and then servers and AP pn# keep her information in their log files or database. In this situation, if attackers access to the log files or database, then they can trace her location and s.

Context Classification

In context-aware systems, context determines service contents, and/or triggers event driven services. In Fig. 1 service scenario, context for the service consists of user location and other information such as user's purchase history and user's favorite genre. For the service, all context information is not only stored in her device, but also stored in all network devices around her [5][7]. At present location, she references Shop A, Shop B, Shop C, pn2 and user contexts. As we see Fig. 2, pn2 keeps all information about near around shops. Also, all shops have user's purchase history information (CLs in Shop A, B and C), and the purchase information is represented as u1:bought date/item in Shop A. This information is used to evaluate her purchase intention, and to recommend suitable goods to her on her visit [7]. She can also get some similar information by sharing or publishing her interests in goods of Shop A, B, and C. At this time, pn2 are keeping information of Shop A, B and C. Also, it already has users' information that is in area (present information) or was in area (past information). Finally all shops can reference them. x,y,h,jk2,..,jkn [jk1: colour,size,price ....][jk2: ......] x,y,h,bs2,…,bsn [bs1: colour,size,price ....][bs2: ......] x,y,h,bk2,....,bkn [bk1: name,year,author,price...][it2:...]

Fig. Context Information for Service Scenario 4 Discussion

In section 4, we show seven UML sequence diagrams which define what actions are conducted while she moves around. Fig. 3 shows the sequence diagrams according to service scenario.

Sequence Diagrams

Fig. 3-(a) shows how her device is connected to the wireless network. Undoubtedly, it uses information in pn2. Fig. 3-(b) is the diagram that she adds her plan and her interesting goods to look for and to buy; usually she takes it before she goes out. Fig. 3-(c) shows her location.

Fig. 3. Service Sequence Diagrams

Fig. 3-(d) illustrates how to evaluate Shella's preference based on her purchase history and it also shows how to recommend goods to her according to her preference information. Fig. 3-(e) is about to get detailed information about a specific goods. Fig. 3-(f) is the step to optimize the promotion for a specific user; it helps some users to organize SNS with them who are going to buy the same goods in future. At last, in Fig. 3-(g), she puts her buying goods on cyber character in her device, after that, she catches how good that before she buys.

Location Hide Algorithm (LHA)

Fig. 4 explains an algorithm named Location Hide Algorithm (LHA), which protects user's location and their routes with location hide flow [1]. The below algorithm defines LHA steps that we propose. In step (1) -step (2), it shows how it gets the value (w i ) by OTP, from step (3), it takes to connect both d.id and w i which are gotten from step (1) through (2). That is, while the user moves, he/she is supposed to get services from pn2. At that time, pn2 keeps d.id.w i information. Because of this process, no matter how attackers analyze log files in pn2 and get w i , they cannot know whose w i it is. Finally, attackers cannot get his/her routes and where he/she is now.

// Location Hide Algorithm (LHA) Initial Secret(W), HashFunction(H); compute w 0 =H t (w);

(1) send w 0 to AP; store w 0 and set i A =1; output temp.d.id=w i (=H t-1 (w)); //send A, i, w i process H(w i )=w i-1 ; set i A <-i A +1;

(2) put w i to d.id;

(3) define d.id.w i ; //d.id-real device ID, w i is temporal d.id

Recommending Items

Fig. 5 shows the simulation implementation result of context service model that we proposed using jContext [12][13], which is a java-based framework for context-aware systems. In the simulation, Shella moves through (i) Fashion Shop -> (ii) Café -> (iii) Book Store, also, before she leaves from home, she puts her interesting goods to buy today into her device. In first place, (i) Fashion Shop, the shop server detects her from pn2, as soon as detecting her, it references all registering goods information that she had put before she leaves from her home. After that, servers in shops send the relevant notices such as recommendation of Blue Jacket and Leather Jacket. In next area, (ii) Café, that server will not recommend any coffee, because of her physical condition which had already added it by her. In last place area, (iii) Book Store, she gets recommendation book list: Black cat and White hand, because the bookstore evaluates her favorite genre as mystery based on her purchase history. Through those steps, she usually gets them step by step.

Conclusions

In this paper, we studied context-aware services with hiding user location information. To avoid exposure of user devices information (d.id) and location (w i ), we used OPT, and then we tried to connect both d.id and w i . By building and analyzing a simulation implementation, a user, Shella, can get her interesting notices according to her location which registered already before she goes out. Finally, she gets the relevant information from Fashion Store, Café and Book Store with d.id (hidden) and w i (open) which set for service and for user location protection. In the future, we will add social network concept to this systems so that users who are in same area and have similar purpose communicate each other in ad hoc manner. Also, we will study some service scenarios illustrated in Fig. 3 in detail.

Fig. 1 .

 1 Fig. 1. Service Scenario. Shella tries to put that item (Jacket) on her AVATAR in her device without her directly wearing in that shop (one part-Book Store C and Shop B are in another area not in figure).

  (g) Apply clothes to user's avatar (d) Evaluate user's preference (a) Connect to the net (b) Input schedule into mobile device (c) Locate user's position (e) Get product information (f) Get customized promotion product information

  Fig. 4. Location Hide Flow A user's location can be known by analyzing stored information in network devices or pn# which has provided services to users. In Fig. 4, the device information, d.id, is registered to pn2, and attackers usually use d.id information to figure out from what pn# the user receives services. Finally they get privacy information, for example, what paths or what a pn# she has to get there etc. LHA connects user device information (d.id) and temporary registration information (w i ), and registers them. After then, pn sends all services to w i , and it forwards them to d.id which is pending. Finally, it avoids the exposure of user's location by defining d.id.w i . And although the user moves to other area, it is difficult to get the user's routes and present location because d.id is deleted in pn#.

Fig. 5 .

 5 Fig.5. Recommending Items near each areaAssume: pn2 provides all services to (i) Fashion Shop, (ii) Café and (iii) Book Store.

Acknowledgment

This work is partially supported under the support of the Portuguese Foundation for Science and Technology (FCT) in the aims of Ciência 2007 program for the hiring of Post-PhD researchers.


Masaya Sato
email: m-sato@swlab.cs.okayama-u.ac.jp

Toshihiro Yamauchi
email: yamauchi@cs.okayama-u.ac.jp

VMBLS: Virtual Machine Based Logging Scheme for Prevention of Tampering and Loss

Keywords: Log, security, virtualization, virtual machine monitor, digital forensics

Logging information is necessary in order to understand a computer's behavior. However, there is a possibility that attackers will delete logs to hide the evidence of their attacking and cheating. Moreover, various problems might cause the loss of logging information. In homeland security, the plans for counter terrorism are based on data. The reliability of the data is depends on that of data collector. Because the reliability of the data collector is ensured by logs, the protection of it is important problem. To address these issues, we propose a system to prevent tampering and loss of logging information using a virtual machine monitor (VMM). In this system, logging information generated by the operating system (OS) and application program (AP) working on the target virtual machine (VM) is gathered by the VMM without any modification of the OS. The security of the logging information is ensured by its isolation from the VM. In addition, the isolation and multiple copying of logs can help in the detection of tampering.

Introduction

The countermeasure for terrorism is one important topic in homeland security. In the field of counter-terrorism, enormous quantity of data is gathered and analyzed for the planning of countermeasures. Computers and networks are used to gather and analyze data, computer science is deeply committed to homeland defence and security. In the field of computer science, countermeasures are considered for cyber terrorism as an activity in homeland security. Recently, information technology is used as a tool to control infrastructures. Cyber terrorism is able to cause critical damage on infrastructures in low cost. Thus, the countermeasure for cyber terrorism have been discussed.

The countermeasures might be weakened by attacking on the data gathered for homeland security. Therefore, the protection of the data is important. The protection of the logs of the APs is also necessary to ensure the validity of gathered information.

The computer terrorism has two characters: anonymity and the lack of evidences of attacks. In computer terrorism, it is difficult to acquire the information that specifies the attacker. Because there are no evidences left on attacks using network, the logs that records the behavior of the systems are important. For this reason, the protection of the information is necessary for the prevention and investigation of computer terrorism.

Digital forensics is a method or technology for addressing these problems. This is a scientific method or research technology for court actions, which allows us to explain the validity of the electronic records. Many researchers are working in this area of the protection of logging information [START_REF] Ashino | Proposal of digital forensic system using security device and hysteresis signature[END_REF][START_REF] Bock | Towards more trustable log files for digital forensics by means of "trusted computing[END_REF][START_REF] Isohara | Lsm-based secure system monitoring using kernel protection schemes[END_REF][START_REF] Takada | Nigelog: Protecting logging information by hiding multiple backups in directories[END_REF][START_REF] Zhao | Secure logging for auditable file system using separate virtual machines[END_REF].

Syslog is commonly used as a logging program in Linux. In this case, the logging information generated by the AP (user log) and kernel (kernel log) is gathered by syslog. Syslog writes logs to file according to the policy, so attackers can tamper with logs by modifying the policy. Moreover, if the syslog program itself is attacked, the log files written are not reliable. In addition, the kernel log is stored in a ring buffer, and therefore, since the kernel log is gathered on a regular schedule, if many logs are generated and stored in the ring buffer before the next gathering time, old logs may be overwritten by new logs. As described above, the user log and kernel log can be tampered with or lost.

In this paper, we propose a logging system to prevent tampering and loss of logs with the virtual machine monitor (VMM). In this system, the OS that should be monitored (monitored OS, MOS) works on the virtual machine (VM). Logs in the MOS are gathered by the VMM without any modification of the MOS's kernel source codes. The VMM gathers user logs by hooking the system calls invoked in the MOS. Because the system gathers logs just after the output of logs, any possibilities for tampering are excluded. The VMM gathers current kernel logs from the buffer before new kernel logs have accumulated. Therefore, the system can gather current kernel logs in conjunction with the accumulation of new ones. Thus, no logs are lost through the buffer being overwritten by new kernel logs.

As mentioned above, the system gathers logs using the VMM. The VMM is independent of and invisible to the MOS, so it is difficult to detect and attack this system. Thus, the system itself is secure. In addition, because the logs gathered by the system are copied to the logging OS (LOS), it is easy to determine which part has been modified by attackers. Moreover, with the isolation of logs, any attacks on the MOS have no effects on the logs gathered by the system. These features mean that this system provides secure logging.

The contributions of this paper are as follows:

(1) The logging scheme for prevention of tampering and loss of logging information using VMM is proposed. The scheme can solve the problems in existing schemes and researches described in Section 2. The implementation has no modification of guest OSes and easy to introduce in existing systems. (2) Evaluations are described and they show that the system is effective on protection of logs. The measurement of the performance with the system shows the overheads in the system calls that are related to logging is 50µs, and are not related to logging is only 2∼5µs.

Existing logging schemes

This section describes the architecture and problems of existing logging schemes. Section 6 also refers to these schemes, the comparisons between these schemes and our proposed system are in there.

Syslog

Syslog is a protocol for system management and security monitoring standardized by Internet Engineering Task Force (IETF) [START_REF]IETF Syslog Working Group: IETF Syslog Working Group Home Page[END_REF]. Syslog consists of a library and a daemon. The syslog library provides interfaces for logging, and the syslog daemon gathers logs and stores them as a file. Figure 1 shows the architecture of syslog. User and kernel logs are gathered as follows.

The syslog library provides functions for user program to send log messages to the syslog daemon. The syslog function sends messages to /dev/log with the send or write system call, and the syslog daemon gathers logs from /dev/log with the read system call.

The kernel accumulates logs in internal buffer (kernel log buffer). The kernel logging daemon (klogd) gathers logs from the kernel log buffer, and afterwards, klogd similarly sends logs to the syslog daemon.

Syslog also has a filtering function. Its policies are described in the configuration file (syslog.conf).

Syslog has the following problems:

(1) The behavior of the syslog daemon can be modified by tampering with the configuration file. In addition, if the syslog daemon itself is tampered with, its output can be unreliable. (2) Users who have permission to access logs can tamper with them intentionally.

(3) Kernel logs in Linux are accumulated in the ring buffer and are gathered at fixed intervals. Thus, if the logs are not gathered for a long time, old logs can be overwritten by new ones. Old logs will also be overwritten if many logs are accumulated in a time that is shorter than the gathering interval.

Although improved syslog daemons have been developed (e.g., rsyslog, syslogng), these problems have not been addressed.

Protection of logs

Some research has been carried out on the protection of files by the file system.

The system NIGELOG has been proposed for protecting log files [START_REF] Takada | Nigelog: Protecting logging information by hiding multiple backups in directories[END_REF]. This method has a tolerance for file deletion. It produces multiple backups of a log file, keeps them in the file system, and periodically moves them to other directories. By comparing the original file and the backups, any tampering with the log file can be detected. Moreover, if any tampering is detected, the information that has been tampered with can be restored from these backups.

The protection of files with the file system is still vulnerable to attacks that analyze the file system. Therefore, a log-protection method using virtualization has been proposed [START_REF] Zhao | Secure logging for auditable file system using separate virtual machines[END_REF]. This method protects logs by saving them to another VM, so it is impossible to tamper with the logs from other VM. However, this method aims to protect the log of a journaling file system, so the scope of the protection target is different from that in our research.

The hysteresis signature is used to achieve the integrity of files. However, it is known that the algorithm of the hysteresis signature has a critical weak point. Although the hysteresis signature can detect the tampering and deletion of files, it cannot prevent tampering and deletion. Moreover, the manager of the signature generation histories can tamper with the histories and files. Therefore, a mechanism to solve this problem using a security device has been proposed [START_REF] Ashino | Proposal of digital forensic system using security device and hysteresis signature[END_REF]. This method constructs a trust chain from the data in the tamper-tolerant area of the security device, the source of the trust chain is protected from attackers. Nevertheless, this method is not versatile because it uses the special device.

Protection of syslog

The methods mentioned above are protecting log files. However, they cannot protect logs before storing of them. Thus, a method to guarantee syslog's integrity has been proposed [START_REF] Bock | Towards more trustable log files for digital forensics by means of "trusted computing[END_REF], which uses a Trusted Platform Module (TPM) and a late launch by a Secure Virtual Machine (SVM) to ensure the validity of syslog. The validated syslog receives logs and sends them to a remote syslog.

Original logging method

An original logging method, independent of syslog, has been proposed for audit [START_REF] Isohara | Lsm-based secure system monitoring using kernel protection schemes[END_REF]. This method uses Linux Security Modules (LSM) to gather the logs, and Mandatory Access Control (MAC) to ensure their validity. The system also uses SecVisor [START_REF] Seshadri | Secvisor: a tiny hypervisor to provide lifetime kernel code integrity for commodity oses[END_REF], and DigSig [START_REF] Apvrille | Digsig: Runtime authentication of binaries at kernel level[END_REF]. SecVisor ensures the security of the logging framework, and DigSig prevents rootkit from making modifications to access permissions. DigSig adds a signature to a program, and prevents the execution of an unknown program by verifying its signature. This method gathers logs in its own way, but the method modifies the kernel source codes. In general, kernel modification is difficult and complex, so the method lacks versatility. And the method uses variety of mechanisms, the overheads arising from them have large effect on daily operations on computers.

Problems of existing logging schemes

From the descriptions above, we find that there are three problems for logging:

(1) Attacks on logging information.

(2) Attacks on logging mechanism.

(3) Loss of kernel log.

The security of logging information is the main focus of the current research, and is of utmost important in digital forensics. However, this is not enough to ensure secure logging. For the protection of logging information, it is necessary to protect the logging mechanism itself. The reliability of logs generated by a program is determined by the reliability of the generator, so the security of the logging mechanism is also important. The third problem depends on the architecture of the Linux kernel log buffer. We currently assume that the guest is Linux, and so this problem needs to be addressed.

VMBLS: Virtual Machine Based Logging Scheme

Requirements and Approaches

To address problems in Section 2, we propose a system to prevent tampering and loss of logging information. There are three requirements for addressing the problems:

(1) Detection of all outputs of log (user log and kernel log).

We need to detect and gather all logs to keep them secure. Where we support only user logs and kernel logs. We do not support logs not sent to syslog. (2) Isolation of log.

In order to secure a log, we obtain a copy of the log and isolate it from the MOS. Since the protection method using the file system is not secure, we isolate the logs in the LOS, assuming that the working environment is on a VM. As the LOS are isolated, attacks on the working environment have no effect on the logs. This isolation also enables us to detect loss of and tampering with logging information, because a comparison between copied logs and original ones will show any differences arising from such attacks. (3) Security of logging mechanism.

To achieve security of the logging mechanism, we use a VMM. Since the VMM is independent of the VM, it is generally difficult to detect its existence and to attack it from the VM. A logging method in kernel space (e.g., LSM or kernel modification) is weakly defended from attacks. If attackers obtain root privileges, they can use bugs in kernel or APs to attack some programs and tamper with the logs to hide their activities. Thus, the isolation of the logging mechanism provides greater security than the methods in kernel.

Furthermore, simplicity and ease of introduction is demanded. The mechanism using a VMM makes our proposed system easier to introduce. The original logging method and security mechanism with kernel modification is difficult to apply to a new version of the kernel because of the kernel's complexity. The VMM, for which no modification of the kernel of the MOS is required, makes our method more flexible than methods that need kernel modification. Thus, we choose the use of a VMM as our method for the protection of logging information.

Architecture

Figure 2 shows the architecture of the proposed system. The MOS and LOS work on the VM. The LOS is a guest OS for storing logs gathered by the logging module. The logging module works in the VMM, and its details are described below. It gathers logs and sends them to the LOS, which then stores them in files.

Logging module

User log collector The collector acquires logs when the requirement for sending logs occurs. As shown in Fig. 2, the VMM hooks the system call that was invoked for sending logs from the user process to the syslog daemon.

The procedures for user log collection are detailed below:

(1) Detect a connect system call for a socket of /dev/log (2) Determine the socket number from the first argument of the connect system call invoked at (1) (3) Detect a send system call for the socket used at (2) (4) Acquire the string as the log specified in the second argument of the send system call invoked at (3)

To send logs, the user process creates a socket and invokes a connect system call for /dev/log. The user log collector detects this connect system call and specifies the socket number that will be used to send the logs. Finally, the user log collector acquires logs by detecting the send system call for that socket. However, the collector cannot recognize the process that sends the logs. To address this issue, the collector uses CR3 control register to determine the process; CR3 stores a unique value for each process since it shows the page directory.

Kernel log collector

The collector acquires logs when the kernel logging function is called in a guest OS. Typically, the VMM cannot detect a function call in a guest OS. To solve this problem, the system sets a breakpoint in the guest OS. Breakpoint exception occurs when some process reaches this breakpoint. In the proposed system, since the guest OSes are fully virtualized, breakpoint exception is processed by the VMM. Using the exception as an opportunity to acquire logs, the VMM can gather kernel logs.

When the processing is brought to the VMM, the logging module checks the state of the kernel log buffer of the MOS. If new logs have been accumulated in the buffer, the logging module gathers them. After that, the VMM returns the processing to the guest OS. Since these processes have no effect on the state of the guest OS, the guest OS can continue to write the kernel log.

In this method, since kernel logs are gathered when a kernel logging function is called, old logs are never overwritten by new ones.

Storing module

The storing module stores logs gathered by the logging module. The storing module is an AP working on the LOS, and stores the logs as log files. The storing module actively gathers logs from the buffer of the VMM.

Implementation

Environment

We implement the system with Xen [START_REF] Barham | Xen and the art of virtualization[END_REF] as the VMM and Linux as the MOS. This version of Xen supports full virtualization. We did not modify the kernel source codes. However, the system needs the System.map file of the MOS, so this information must be provided beforehand. The reason for the system requiring this System.map information is that the system uses the address of the kernel log buffer and the kernel logging function. Because of the need for full virtualization, we prepared a CPU that supports virtualization extension.

Detecting a system call

The user log collector detects the invoking of system calls; such a mechanism is necessary because the proposed system is implemented with a VMM.

Therefore, in the proposed system, we applied a mechanism that causes a page fault when a system call is invoked [START_REF] Dinaburg | Ether: malware analysis via hardware virtualization extensions[END_REF]. In a fully virtualized environment, if a page fault occurs on the VM, then the VMM is raised (VM exit) [START_REF]Intel: Intel 64 and IA-32 Architectures Software Developer's Manual Volume 3B: System Programming Guide[END_REF]. After the VMM has been raised, the logging module acquires the user logs and hides the occurrence of the page fault. Finally, the VMM raises the guest OS, which works as if no event has occurred.

In this method, to cause a page fault, we modified some registers of the MOS. A system call using the sysenter (fast system call) refers the value in sysenter_eip_msr and jumps to its address to execute the system call function (sysenter_eip_msr is one of the machine-specific register (MSR)). Through modification of this value to another address to which access is not permitted from the MOS, a page fault is made to occur when a system call is invoked.

Setting a breakpoint

In the proposed system, we set a breakpoint in the kernel logging function of the MOS to gather kernel logs. The breakpoint is realized by embedding of a INT3 instruction. VM exit appears if a breakpoint exception occurs in the MOS, and the VMM gathers kernel logs with this exception.

In the following, we detail the procedure for setting breakpoints and gathering kernel logs. Here, we assume that the first INT3 instruction is already embedded.

Evaluation

Simplicity and ease of introduction

We implemented a prototype of the proposed system by modifying the Xen hypervisor. The total amount of source codes that we added and modified on Xen are only about 1,000 lines. The source codes of the MOS is not modified.

Purposes and environment

We evaluated the system from two points of view: the prevention and detection of tampering, and the loss of logging information. This paper also describes the overheads of the system. Table 1 details the environment used for this evaluation.

Prevention of tampering

A log gathered by the proposed system is kept in a place where it is independent of the MOS. Thus, with the MOS working on a VM, it is difficult for attackers to tamper with the log even if they obtain root privileges.

Prevention of loss

Loss of user log

We assume that an attacker tampers with the policy of syslog to suppress some parts of the log. We show that the proposed system can gather logs even if the policy has been tampered with. Figure 3 shows the logs gathered by syslog, and Fig. 4 shows those gathered by the proposed system. We compared both logs around the time when the policy was manipulated, as shown in Fig. 5. In the logs gathered by syslog, the logs decreased after the manipulation of the policy because of the exception of the mail facility. On the other hand, there are no changes in the logs gathered by our proposed system around the time of the manipulation of the policy. Thus, it is proved that the proposed system gathers logs regardless of the behavior of syslog.

Loss of kernel log

We show that the proposed system can gather logs under the condition of a massive output of kernel logs even if the existing system cannot.

The size of the kernel log buffer of the standard kernel on Debian 5.0.3 is 131,072 bytes. To exhaust this buffer, the program outputs logs with a total size greater than that of the buffer by printk (kernel logging function). One output has a size of 21 bytes, whereas in printk format, the size of the output is 38 bytes. Thus, in order to exhaust the buffer, the program needs to output the log 3,450 times. In this experiment, we compared the logs gathered by the existing system and our proposed system after 4,000 outputs of the log.

Figure 6 shows the log in the MOS, and Fig. 7 shows the log gathered by the proposed system. In the third row of Fig. 6, the log is unusual because something has been lost through overwriting. In contrast, Fig. 7 shows that the proposed system has correctly gathered all the logs with no interruption. Whereas the existing system could not gather logs before the fiftieth output, the proposed system gathered all the logs. Thus, we have shown that the proposed system can gather all logs, even if they are lost by the existing system.

Detection of tampering and loss

The comparison of logs gathered by the existing and proposed systems enables us to detect any tampering with or loss of logs. Therefore, we show that it is possible to detect tampering by comparing these logs. In preparation, we tamper with the log file. After that, we compare the logs gathered by the existing and proposed systems. This comparison indicates that the proposed system is able to detect tampering.

For this comparison, we use sudo as a program that uses syslog to output user logs. If a command is executed with sudo, the user name, tty, and the name of the command are sent to the syslog daemon. At this point, the information in the log gathered by the existing system and the proposed system is the same.

To hide the executed command, we modify the name of the command in a log in the existing system. Now, comparison between the logs allows a difference in the name of the command to be detected.

As a result, it is seen that tampering with a log in the MOS has no effect on the logs in our proposed system. Moreover, the experiment shows that a part tampered with in the MOS can be detected through comparison between the logs in the MOS and in the proposed system.

Overheads

The user log collector hooks all system calls in the MOS. In this mechanism, the VMM is raised upon each system call, and therefore, the processing time of the system call increases. To determine the overheads of the system, we measured the overheads in some of the system calls that are mainly invoked in the syslog function and the function itself. The results are shown in Tables 2 and3.

Table 2 shows the overheads of connect and write system calls that were invoked in syslog function. To show the overhead when switching between the MOS and VMM, we also measured the overhead of the getpid system call. From the margin between the overhead of getpid and other system calls, it is found that switching between the VMM and MOS takes about 2 µs. In invoking a connect system call, our system decides the target of the connect system call. The measurement shows that this decision takes about 3 µs. In the write system call, the proposed system takes about 47 µs. This overhead derives from copying of the message between the MOS and the VMM.

In addition, since the difference between the overhead in the syslog function in Table 3 and the write system call is 5 µs, it can be concluded that the main reason for the overhead in the syslog function is the write system call. also shows the overheads of the kernel log collector. The overhead of the proposed system in the printk function is 57 µs. This result is similar to that for the syslog function. The reason is thought to be that the printk function copies data to the memory in the same way as the syslog function. It can be estimated that the 10 µs overhead derives from the breakpoint exception. From these measurements, such overheads have little effect on performance.

Discussion

Opportunity for gathering kernel logs

The proposed system sets a breakpoint at the starting point of the kernel logging function for the opportunity to gather kernel logs. Thus, the system gathers old logs just before the output of current logs, the logs are older than current ones. In order to acquire the latest logs, it is necessary to set the breakpoint immediately after the output. The current implementation uses the starting address of the kernel logging function from the System.map. Starting points of functions are described here, so it is easy to set a breakpoint. In order to gather logs immediately after the output of a kernel log, we need the returning point of the function. But to acquire the point, we need to analyze the kernel. Although the method can gather latest logs, there is a problem in terms of analyzing the kernel each time it is updated. The method of the proposed system only requires System.map, so there is no difficulty arising from kernel updates.

Security of logs in logging path

To guarantee the integrity of a log, it is necessary to ensure the security of the logging path from its output to the time it is stored in a file. Here, we compare the security of the logging paths of the existing and proposed systems.

Firstly, we analyze the logging path of a user log. A user log might be attacked at the following points:

(1) The time when a user process generates a log [START_REF] Ashino | Proposal of digital forensic system using security device and hysteresis signature[END_REF] The time between the sending of a log and its receipt by syslog [START_REF] Barham | Xen and the art of virtualization[END_REF] The time between the receipt of a log and storing it to a file (4) After the output of a log

The existing system cannot detect and prevent tampering or the loss of logging information at any time. In the proposed system, time (1) is the only possible time when attacks might be suffered. An example of an attack at time (1) would be someone tampering with the program itself. To protect the logs from tampering in this case, it is necessary to ensure the integrity of all programs that generate logs. DigSig [START_REF] Apvrille | Digsig: Runtime authentication of binaries at kernel level[END_REF] is a method that ensures the integrity of a program by assigning a signature to the program. However, this method does not satisfies our demand because it modifies the kernel codes. Moreover, the method causes a large overhead. For time (2) to (4), some research has been carried out, but those methods do not satisfy our demand. The method ensures the integrity of syslog has proposed [START_REF] Bock | Towards more trustable log files for digital forensics by means of "trusted computing[END_REF], but the method needs logging server, so if the network is down, it is unavailable. For time (4), hysteresis signature enables us to detect tampering with a log, but it has a problem mentioned in Section 2. In addition, to prevent such tampering, protection methods using the file system already exist [START_REF] Takada | Nigelog: Protecting logging information by hiding multiple backups in directories[END_REF]. However, these methods modify the source codes of the kernel, so our demand is not satisfied.

Secondly, we analyze the logging path of a kernel log. A kernel log might be attacked at the following moments:

(1) The time to generate a kernel log in a kernel (2) The time to output the log to a kernel log buffer (3) While stored in the kernel log buffer (4) The time during which a kernel logging daemon gathers a log (5) While the kernel logging daemon sends the log to syslog (6) While syslog stores the log to a file [START_REF]Intel: Intel 64 and IA-32 Architectures Software Developer's Manual Volume 3B: System Programming Guide[END_REF] Afther the output of a log In the existing system, it is impossible to protect a log from an attack by a rootkit at any time. Furthermore, there is a possibility of attack similar to the logging of a user log if the kernel is safe. The proposed system gathers a log at time [START_REF] Ashino | Proposal of digital forensic system using security device and hysteresis signature[END_REF]. We can consider tampering with the kernel logging function as an example of an attack at time (2). However, the log gathered by the proposed system is the previous one. Therefore, the logs might be attacked at time [START_REF] Barham | Xen and the art of virtualization[END_REF]. Thus, the proposed system can address attacks on and after time (4). The improvement of the proposed system for gathering a log immediately after its output enables it to address time (3) as well.

However, to prevent attacks before time (3), it is necessary to modify the parts related to kernel logging. In this situation, our demand is not satisfied.

SecVisor [START_REF] Seshadri | Secvisor: a tiny hypervisor to provide lifetime kernel code integrity for commodity oses[END_REF] is a technology that ensures the integrity of the kernel, and is effective for the prevention of attacks at times (1) and ( 2). However, it is impossible to prevent attacks after time (3) with SecVisor alone. Thus, since the proposed system can prevent attacks on or after time (4), the security of logging is ensured unless the kernel logging function itself is attacked.

Applicability for other OSes

No modification of the kernel code in the MOS is necessary because the proposed system is implemented in a VMM. For this reason, the system can be applied to any kind of OS. Furthermore, if an OS fulfills the following requirements, the proposed system can be applied to an OS that is not open-source software. Here, we discuss the possibility of applying the system to other OSes.

Regardless of how the system is constructed in terms of the logging and storing modules, the storing module is independent from the MOS. Thus, in the adaption of the system, we need to consider the requirement for implementing the logging module. Considering the case of Windows, a widely used OS, the following requirements can be noted:

(1) Use of sysenter instruction in invoking a system call.

(2) Identification of the system call is used in logging.

(3) Identification of the starting address of the kernel logging function. (4) Identification of the area of the kernel log buffer.

Requirements (1) and ( 2) are necessary for the gathering of user logs, and (3) and ( 4) for the gathering of kernel logs.

In Windows XP or later, system calls are generally implemented with sysenter. Moreover, since the identifier of the system call is stored in the EAX register in Windows, the detection of a system call for logging is available with its value. Requirements (3) and ( 4) can be achieved by analyzing the kernel.

On the basis of these considerations, it is concluded that the proposed system can be applied to various OSes (e.g., Windows) if the requirements are fulfilled.

Conclusion

This paper describes a logging system with a VMM to prevent log tampering and loss. In the user log collector, the VMM detects an output of the log of the MOS and gathers it before it is gathered by syslog. Because the proposed system gathers logs immediately after the logging request, there is no opportunity for tampering. Also, because the kernel log collector gathers logs in conjunction with the kernel log's output, the system can prevent the loss of logging information caused by the overwriting of old kernel logs. These functions enable the VMM to gather logs of the MOS with no modification of its source codes. Moreover, the system is independent of the MOS because it is implemented as a VMM. Thus, it is difficult to attack the proposed system. This paper also presents an evaluation of the proposed system, assuming that tampering and loss of logging information occurs. Considering the results of these evaluations, it is proved that it is possible to detect and prevent tampering with log files. Furthermore, the proposed system can address the problem caused by the structure of the kernel log buffer.

This paper also describes the evaluation of the overheads caused by the system. The results show that the overheads associated with the proposed system is only about 50µs at most.

Fig. 1 .

 1 Fig. 1. Architecture of syslog.

Fig. 2 .

 2 Fig. 2. Architecture of the proposed system.

( 1 )

 1 Breakpoint exception occurs and switches to the VMM. Kernel logs are gathered after the processing is switched to the VMM. (2) Embed INT3 instruction to the next one. (3) Restore the value at the address at which the exception occurred. (4) Restart the processing from the restored instruction. (5) Breakpoint exception occurs and switches to the VMM. (6) Embed INT3 instruction to the firstly embedded address (7) Restore the value on the address at which the exception occurred. (8) Execute instruction from restored point.

Fig. 3 .

 3 Fig. 3. A user log gathered by syslog.

Fig. 4 .

 4 Fig. 4. A user log gathered by the proposed system.

Fig. 5 .

 5 Fig. 5. Manipulation of configuration.

Fig. 6 .

 6 Fig. 6. A kernel log gathered by the existing system.

Fig. 7 .

 7 Fig. 7. A kernel log gathered by the proposed system.

Table 1 .

 1 Environment used for evaluation.

	OS	Domain0	Linux 2.6.18-xen
		Fully virtualized domain Linux 2.6.26
	VMM		Xen 3.4.1
	syslog		rsyslogd 3.18.6
	CPU		Intel Core 2 Duo E6600
	Memory Physical	2,048 MB
		Domain0	1,024 MB
		Fully virtualized domain 1,024 MB

Table 3

 3

Table 2 .

 2 Overheads in the proposed system when a system call was invoked (µs).

			connect		write		getpid
		ave	overhead	ave	overhead	ave	overhead
	unmodified	1.16	-	92.90	-	0.23	-
	modified	6.55	5.39	142.20	49.30	2.23	2.00

Table 3 .

 3 Overheads in the proposed system when a syslog and printk are invoked (µs).

			syslog		printk
		ave	overhead	ave	overhead
	unmodified	102.39	-	9.89	-
	modified	156.56	54.17	67.34	57.45

Acknowledgements

This research was partially supported by Grant-in-Aid for Scientific Research 21700034 and a grant from the Telecommunications Advancement Foundation (TAF).


Wei Chen
email: chenwei@nudt.edu.cn

Zhiying Wang

Qiang Dou

Yongwen Wang

A Novel Chaining Approach to Indirect Control Transfer Instructions

Keywords: code cache, indirect control transfer instruction, dynamic chaining, simulator

Both dynamic binary translation systems and optimization systems store the translated or optimized code in the software maintained code cache for reuse. The performance of the code cache is crucial. Translated code is usually organized as code blocks in the code cache and each code block transfer control to the next one through a control transfer instruction. As the target address of a control transfer instruction is in the form of its source program counter, the conventional code cache system has to check the address mapping table for the translated target address to find the required target code block, which will cause considerable performance degradation. Control transfer instructions can be divided into two categories as direct control transfer instructions and indirect control transfer instructions. For indirect control transfer instructions, the target address is hold in the register or memory element whose content can be changed during the execution of the program. It is difficult to chain the indirect control transfer instructions with a fixed translated target address through pure software approaches. A novel indirect control transfer chaining approach is proposed in this paper. The principle of the technique is to insert custom chaining instructions into the translated code block while translating the indirect control transfer instructions and execute those chaining instructions to implement dynamical chaining. Some special hardware and software assists are proposed in this paper. Evaluation of the proposed approach is conducted on a code cache simulator. Experiment results show that our hardware assisted indirect control transfer instruction chaining approach can improve the performance of the code cache system dramatically.

Introduction

Software maintained Code Cache Systems (CCS) [START_REF] Hazelwood | Code Cache Management in Dynamic Optimization Systems[END_REF] have been widely used by many binary translation or optimization systems (optimization system is a kind of translated system in which translation is performed between the same instruction set architecture; in the rest of the paper, the translation system includes the optimization system if not especially declared) to store the translated or optimized code for reuse. As more and more translation systems have been proposed and developed, the performance of the code cache systems becomes a hot topic in both the industry and academic fields, especially for those virtual computing environments.

In the code cache, the translated code is organized in terms of code blocks. Each code block ends with a control transfer instruction which switches control flow between different code blocks. When a source code block is translated the first time, its target code block may have not been translated most of the time. Thus, the translated code block always keeps the target address of the control transfer instruction in terms of its original Source Program Counter (SPC). The conventional code cache system always maintains an Address Mapping Table (AMT) [START_REF] Xu | A Novel Chaining Approach for Direct Control Transfer Instructions[END_REF] for recording the code block's SPC and its corresponding Translated Program Counter (TPC). During the execution, CCS finds the required translated target code block by looking up AMT as Fig. 1(a) [START_REF] Xu | A Novel Chaining Approach for Direct Control Transfer Instructions[END_REF] shows. When executing within a code block, the execution/control flow is straight-line. However, transitions from one code block to another may cause performance degradation because the control flow is changed and costly address mapping table lookup mechanism must be invoked. In our code cache simulator, an AMT lookup may cost 15~25 local instructions while a context switch may cost about 40 local instructions. Therefore, if the control transfer instruction can be chained directly to the translated target address (as Fig. 1(b) shows), the performance of the code cache system may be dramatically improved as table lookup and context switch operations can be avoided.

Control transfer instructions can be divided into two categories as direct control transfer instructions and indirect control transfer instructions. For direct control transfer instructions, the target address always appears as an immediate value in the instruction itself. So, no matter the immediate value indicates an address or an offset, the target address of a direct control transfer instruction can be calculated from the instruction itself and is fixed during execution. Thus, the SPC of the direct control transfer instruction can be placed with its TPC through software mechanisms. We have proposed an effective solution to this problem in our previous work [START_REF] Xu | A Novel Chaining Approach for Direct Control Transfer Instructions[END_REF].

For indirect control transfer instructions, the target address is saved in a register or a memory element. The indirect control transfer instruction figures out its target address by reading the register or the memory element. During execution, the content of the register or memory element can be changed, which means that the target address of the indirect control transfer instruction is not fixed. Therefore, it is difficult to fix the indirect control transfer instruction's target address with a fixed TPC. At present, as we know, there is not a pure software approach which can solve this problem effectively.

In this paper, a hardware assisted Indirect Control Transfer Chaining (IDCTC) method is proposed for the indirect control transfer instruction. The principle of IDCTC is: (1) while translating the source code block, inserting custom chaining instructions into the translated code block which contains indirect control transfer instructions, (2) during execution, executing the inserted chaining instructions to dynamically determine the translated target address. Special hardware/software assists are occupied by IDCTC. The key of IDCTC is a hardware assist called indirect transfer target buffer, which saves most frequently accessed indirect control transfer instructions.

To evaluate the efficiency of IDCTC, we conduct experiments on a code cache simulator and the experiment results show that IDCTC can dynamically chain the indirect control transfer instructions and dramatically improve the performance of the code cache system.

The rest of the paper is organized as follows. Section 2 introduces some related works. Section 3 introduces the hardware and software assists occupied by IDCTC. Section 4 describes the process of our indirect control transfer chaining approach. Section 5 presents the evaluation of IDCTC and section 6 concludes this paper.

Related Work

Code cache systems are the critical part in a binary translation system or optimization system. All the translated codes are cached in the code cache system for reuse.

Transmeta Crusoe [START_REF] Dehnert | The Transmeta Code MorphingTM Software: Using Speculation, Recovery, and Adaptive Retranslation to Address Real-Life Challenges[END_REF] use the Code Morphing Software (CMS) to translate x86 binaries into Very Long Instruction Word (VLIW) forms. The translated VLIW instructions are stored in the code cache as superblocks. IBM DAISY [START_REF] Ebcioglu | DAISY: Dynamic Compilation for 100% Architectural Compatibility[END_REF] translates PowerPC binary codes into its VLIW version as "tree regions", which are cached in the code cache for reuse. IA-32 EL [START_REF] Baraz | IA-32 Execution Layer: a two-phase dynamic translator designed to support IA-32 applications on Itanium®-based systems[END_REF] translates IA-32 instructions into Itanium instructions. It is a two-stage translator that begins with a simple basic block translator and invokes an optimizing translator once hotspot code is detected. Both the basic code blocks and superblocks are stored in the code cache. The well-known optimization system HP Dynamo [START_REF] Bala | Dynamo: A Transparent Dynamic Optimization System[END_REF] optimizes the hotspot of the source code and stores the highly optimized code in the code cache in terms of trace. Other successful translation /optimization systems which employ code caches include: FX!32 [START_REF] Hookway | Digital FX!32: Combinning Emulation and Binary Translation[END_REF], UQDBT [START_REF] Ung | Machine-Adaptable Dynamic Binary Translation[END_REF], Strata [START_REF] Scott | Retargetable and Reconfigurable Software Dynamic Translation[END_REF], DELI [START_REF] Desoli | Fisher: DELI: A New Run-Time Control Point[END_REF], et al.

As the performance of the code cache system has great impact on the translation system and optimization system, quite a few researchers put their interests on the approaches to improving the performance of the code cache system. Kim works on the code cache management schemes and proposed a generational code cache based code cache management algorithm [START_REF] Hazelwood | Code Cache Management in Dynamic Optimization Systems[END_REF]. This algorithm categorizes code traces based on their expected lifetimes and groups traces with similar lifetimes together in separate storage areas. Using this algorithm, short-lived code traces can easily be removed from a code cache without introducing fragmentation and without suffering the performance penalties associated with evicting long-lived code traces.

A software prediction approach is proposed in [START_REF] Kim | A Co-Designed Virtual Machine for Instruction Level Distributed Processing[END_REF] to predict the target address of the indirect control transfer instructions. The principle of the prediction based approach is to compare the content of the register of the indirect control transfer instruction with the pre-defined target SPC, which is most likely to be the real target SPC. If the value of the register matches with the predicted SPC, the control flow can be easily transferred to the required TPC which is corresponding to the pre-defined SPC. The software prediction based approach actually provides a kind of chaining of the indirect control transfer instruction and is easy to be implemented. The prediction depth can be configured flexibly. The shortage of this approach is that a large number of instructions should be inserted into the translated codes in order to implement the prediction. This means considerable code expansion which may offset the performance improvement. Especially in the case that the prediction is failed after several times of comparing, the software approach will cause extra overhead.

In our previous work, we proposed a software implemented Direct Control Transfer instruction Chaining (DCTC) [START_REF] Xu | A Novel Chaining Approach for Direct Control Transfer Instructions[END_REF] approach to chain the direct control transfer instructions. The principle of DCTC is to replace the target address of the direct control transfer instruction with its TPC, in order to reduce the context switching and the address mapping table lookup operations. DCTC adopts an address mapping table and a special direct control transfer target address mapping table to assist the chaining process. DCTC has been demonstrated its efficiency in chaining the direct control transfer instructions. If the indirect control transfer instructions can be chained effectively, the performance of a code cache system can be further improved.

In this paper, we focus on improving the performance of the code cache through chaining the indirect control transfer instructions.

3

Software and Hardware Support for IDCTC

Hardware Support for IDCTC

It is difficult to chaining the indirect control transfer instructions through only software approaches. Thus, in this paper, we propose a novel hardware support called Indirect Transfer Target Buffer (ITTB) to support chaining the indirect control transfer instructions to their translated targets. ITTB is implemented as a high speed buffer on chip which can provide one read/write operation in one clock cycle. ITTB is used to store the frequently accessed target address of the control transfer instructions. Obviously, ITTB provide a copy of AMT. As ITTB is a hardware approach, target address can be looked up quickly. The principle of ITTB is similar to Translation Look-aside Buffer (TLB) [START_REF] Hennessy | Computer Architecture: A Quantitative Approach[END_REF] used in the management of virtual memory space. Fig. 2 shows the infrastructure of ITTB. ITTB stores the corresponding TPC of indirect control transfer instructions, and is accessed by the SPC of the indirect control transfer instructions. SPC is divided into tag and index, while ITTB use valid bit and tag to check whether the required SPC is matched in ITTB. ITTB can be implemented as a cache, which can be organized with multi-way associativity and replacement policies. The ITTB accessing result will update the flag f_ITTB, if it is hit, this flag will be set as 1, or it will be cleared. If it is hit in ITTB, the required TPC will be written into the special purpose register REG TPC , which is custom designed in the microprocessor for ITTB. Table 1 gives out the description of f_ITTB and REG TPC.

Register

Description REG TPC Register used to store address of the translated code block f_ITTB Status flag indicting whether ITTB is hit or not; f_ITTB can be implemented using reserved bit of the status flag register of the microprocessor as most modern microprocessors have reserved status bits and it can also be implemented through custom individual status flag register

As ITTB is custom designed hardware, it should be accessed via custom designed instructions as "search_ITTB, reg" and "store_ITTB, <SPC, TPC>" which are added to the instruction set of the microprocessor.

Search_ITTB, reg: this instruction looks up ITTB according to the content of the register '"reg", which is corresponding to the register used by the register control transfer instructions. The value of "reg" is the SPC of the target address.

Store_ITTB, <SPC, TPC>: this instruction update the corresponding ITTB element related to SPC with the value of TPC. The above two instructions are custom designed for ITTB access. Furthermore, the ITTB checking result will be used by other two instructions which should also be provided in the microprocessor as "JMP REG TPC " and "JITTB, imm". The former transfers control to the address indicated by REG TPC while the latter checks the status of flag f_ITTB. Detailed description of the custom instructions can be found in Table 2. In some microprocessors, the instruction set architecture may not support the instruction format that one instruction consists of two immediate values. In that case, "strore_ITTB" can be implemented through several register-register instructions. First, write SPC and TPC into two registers, and then execute "strore_ITTB, reg1, reg2" like instruction. How to implement "store_ITTB, <SPC, TPC>" depends on the instruction set architecture of the target microprocessor.

Software Support for IDCTC

Besides the hardware support, DBT systems should also maintain some software data structures to assist the chaining of the indirect control transfer instructions. One is the Address Mapping Table [START_REF] Xu | A Novel Chaining Approach for Direct Control Transfer Instructions[END_REF] which stores the SPC and TPC of the code blocks. The other is called T-SPC, which is a hash table used to save any possible source programming counter (SPC) of the target address of the indirect control transfer instructions. T-SPC will be updated under two situations:

During

Indirect Control Transfer Instruction Chaining

Based on the hardware and software assists introduced in section 3, we propose a novel indirect control transfer instruction chaining approach. The basic principle is: 1) to insert specific instructions which will directly chain the indirect control transfer instructions when translating the source code block; 2) to execute these specific chaining instructions before executing the indirect control transfer instructions during the execution of the translated code block.

Insert Chaining Instructions

The first step is to insert custom chaining instructions and update the AMT, ITTB and T-SPC, when generating the translated code block which contains indirect control transfer instructions. In this paper, we only introduce register indirect control transfer instructions, for memory indirect control transfer instructions, the chaining approach is the similar. The difference is that the content of the memory element should be first moved into a register so as to execute the "Search_ITTB, reg" instruction. Thus, this paper focuses on the chaining of the register indirect control transfer instructions. Moreover, the source target address may need to be calculated by adding the value of the register/memory with a certain offset. In this case, we only need to calculate the source target address by following the source target address calculation rule and then write the source target address into a certain register and then execute the "Search_ITTB, reg" instruction.

Stub code is used when the chaining of the indirect control transfer instruction is failed. The stub code saves the execution context and turns the control back to VMM that the corresponding VMM routine looks up the AMT according to the value hold in the register of the indirect control transfer instruction. If it is hit in AMT, write the related SPC and TPC into ITTB. This is based on the fact that ITTB is a copy of AMT, as the capacity of ITTB is limited, there may be some indirect control transfer instructions whose SPC and TPC have not been saved in ITTB. Hence, if it is hit in AMT, the SPC and TPC of the current indirect control transfer instruction should be written into ITTB.

Other indirect control transfer instructions include indirect branch, indirect subroutine call, and return. Similar operations can be performed on these instructions to insert chaining instructions.

Executing Chaining Instructions

Though the chaining instructions are inserted into the translated code block, the chaining of the indirect control transfer instruction is finally finished during execution of the translated code block.

The "Search_ ITTB, reg" instruction looks up ITTB according to the content of the register (SPC) of the indirect control transfer instruction, in order to quickly check whether the required TPC is already existed. If the TPC is existed, which means the corresponding TPC has been automatically written into RRG TPC , the "JMP REG TPC " instruction will be executed so as to transfer the control to the target TPC. If the required TPC is not existed, stub code will be executed that the control will be transferred to VMM so as to lookup AMT or perform the interpretation or translation.

Obviously, the novel chaining approach we proposed is a dynamically chaining method based on ITTB.

Evaluation

Evaluation Environment

The experimental infrastructure is based on a Code Cache Simulator (CCS) [START_REF] Xu | A Novel Chaining Approach for Direct Control Transfer Instructions[END_REF]. We construct CCS to evaluate the control transfer instruction chaining performance. CCS is a two-stage simulator which consists of a profiler, a trace constructor, a code cache and a control unit. In the first stage, CCS runs the source code and the profiler collects the execution information. The trace constructor reorganizes the frequently executing source code into traces and stores the reorganized code blocks in the code cache. In the second stage, CCS runs the code blocks in the code cache instead of the source code while executing the hotspots. Detailed information of the simulator can be found in [START_REF] Xu | A Novel Chaining Approach for Direct Control Transfer Instructions[END_REF]. The benchmarks (gzip, gap, parser, vortex) we use are selected from SPEC INT 2000 [13]. In [START_REF] Xu | A Novel Chaining Approach for Direct Control Transfer Instructions[END_REF], we have demonstrated that for these benchmarks, a small number of code blocks may cause huge number of control transfers as hot code blocks are frequently executed. Obviously, without chaining, control transfers are costly because of the large number of AMT looking up operations and context switching overhead.

Performance Evaluation of IDCTC

In the experiments, we first let CCS run the benchmarks without chaining, then use IDCTC to chain the code blocks which contain the indirect control transfer instructions.

Chaining efficiency of IDCTC

Indirect control transfer instructions realize fast dynamic chaining through accessing ITTB. The target code block may not have been translated when the indirect control transfer instruction is translated the first time and some of the target address is untranslatable instructions [START_REF] Chen | Research on Dynamic Binary Translation Based Co-Designed Virtual Machine[END_REF], this will cause the IDCTC failed. But, the capacity limit of ITTB is the main reason which causes the failure of the chaining of the indirect control transfer instruction. However, because of the principle of locality [START_REF] Hennessy | Computer Architecture: A Quantitative Approach[END_REF], most of the time, when indirect control transfer instruction accesses ITTB, the required information can be found in ITTB. Fig. 6 shows the chaining success rate of different benchmarks when using direct mapping ITTB with 64 elements, 128 elements and 256 elements. For the ITTB which contains 256 elements, the average success chaining rate achieves 92.5%. Obviously, the hardware ITTB can dynamically assists to chain the indirect control transfer instructions high efficiently. As a result, the chaining efficiency indicates that most of the table lookup operation and context switching overhead can be avoided. Fig. 6 indicates that the successful chaining rate is sensitive to the size of the ITTB. For gap and vortex, the chaining rate is lower, because the locality of the target address of the indirect control transfer instruction is not so centralized in these two benchmarks. However, the increase of the ITTB size can fit the address changing character of these benchmarks.

Though, there are still some instructions can not be chained, they only occupy quite a few portion of all the (dynamic) indirect control transfer instructions.

Performance improvement of the code cache

Because most of the indirect control transfer instructions can be chained, the performance of the code cache could be improved. Fig. 7 shows the performance improvement of each benchmark. The y-axis is the performance speedup caused by IDCTC compared to the original execution without chaining. The average speed up is 1.435. This demonstrates the efficiency of our indirect control transfer instruction chaining approach. The performance improvement is determined by the chaining efficiency. As a result, IDCTC performs most powerfully for gzip, but still shows dramatic improvement for other benchmarks.

Conclusions

Code Cache systems are the key element of the binary translation system and the optimization system. Translated/optimized codes are saved in the code cache in terms of code blocks which ends with control transfer instructions. Conventional code cache systems look up the address mapping table to find the translated target code block according to the source target address. The table lookup operation is considerably costly. Chaining the control transfer instruction with their translated target address can avoided most of the table lookup overhead. The target address of the indirect control transfer instructions are saved in the register or memory and can be changed during execution. It is difficult to chain the indirect control transfer instructions through pure software approaches. In this paper, we propose an indirect transfer target buffer which is implemented as a high speed buffer on chip. ITTB is used to store the frequently accessed target address of the control transfer instructions. Based on ITTB, we propose a novel indirect control transfer instruction chaining method which inserts custom chaining instructions into the translated code block instead of translating the indirect control transfer instructions. During execution, the chaining instructions access ITTB to find the required TPC of the target address. Because of the principle of locality, most of the required target of the indirect control transfer instructions can be found in ITTB. IDCTC is a dynamic chaining approach, in which chaining is performed during execution instead of translation. Evaluation of IDCTC is conducted on a code cache simulator. The experiment results show that IDCTC can bring dramatic performance improvement for the code cache system. In the future work, we will use CCS to run more benchmarks to further evaluate the efficiency of IDCTC. Further more, in the future work, we will try to merge the chaining approaches of both direct control transfer instructions and indirect control transfer instructions so as to further improve the performance of the code cache systems as well as those binary translation systems and optimization systems.

Fig. 1 .

 1 Fig. 1. Control flow changes among code blocks in the code cache.

Fig. 2 .

 2 Fig. 2. Infrastructure of indirect transfer target buffer.

  profiling, any time an indirect control transfer instruction is executed, the value (SPC of the target address) of the register or memory used by the indirect control transfer instruction should be written into T-SPC. When a translated code block transfers the execution to VMM because of the fact that the indirect control transfer instruction at the end of the code block has not been chained, VMM should write the target SPC of the indirect control transfer instruction into T-SPC. T-SPC is used to update ITTB when a new code block is translated.

Fig. 3 .

 3 Fig. 3. Insert custom chaining instructions and update related software/hardware assists. Though, different indirect control transfer instructions may require different sequence of chaining instructions, the translating process or the inserting process is similar. Thus, we take the indirect jump instruction for example. The indirect jump instruction stores the target address in a register. When translating the source indirect jump instruction, IDCTC has to insert those custom chaining instructions at the place where the translated indirect jump instruction should appear. Fig. 4 indicates how to insert the chaining instructions in details. TPC cur represents the address of the indirect jump instruction itself in the code cache. LEN JITTB represents the length/bytes of the JITTB instruction. Similarly, LEN save register content represents the total length/bytes of the instructions which are used to save the content of the register in the indirect jump instruction.

Fig. 4 .

 4 Fig. 4. Insert chaining instructions for indirect jump instruction.

Fig. 5 (Fig. 5 .

 55 Fig. 5 (a) shows the status of the source code block ends with an indirect jump. Fig. 5(b) shows the status of the corresponding translated code block. It shows that the translated code block has been inserted with the custom chaining instructions. The source indirect jump instruction has not been translated to a local indirect jump in the translated code.

Fig. 6 .

 6 Fig. 6. Successful chaining rate of indirect control transfer instructions.

Fig. 7 .

 7 Fig. 7. Performance speedup caused by IDCTC.

Table 1 .

 1 Special purpose registers custom designed for ITTB.

Table 2 .

 2 Custom designed instructions for using ITTB.

	Instruction	Description
	Search_ ITTB, reg	Lookup ITTB according to the value of register
		"reg"; if it is hit, write TPC into REG TPC , if not,
		clear flag f_ITTB
	Store_ITTB, <SPC, TPC> Write TPC into the ITTB element according to
		the SPC
	JMP REG TPC	Jump to the address indicated by REG TPC
	JITTB, imm	Check if ITTB access is hit. If it is hit, transfer
		control to the instruction whose address has an
		offset of "imm" with the current instruction, if
		not, then execute the next instruction.

Acknowledgments

. This work is supported by National Basic Research Program under grant No.2007CB310901. This work is also supported by the National High Technology Research and Development Program of China, under grant No.2009AA01Z101.