David Lorenzi
email: dlorenzi@cimic.rutgers.edu

Emre Uzun
email: emreu@cimic.rutgers.edu

Jaideep Vaidya
email: jsvaidya@cimic.rutgers.edu

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

Vijayalakshmi Atluri
email: atluri@cimic.rutgers.edu

Enhancing the Security of Image CAPTCHAs through Noise Addition

Text based CAPTCHAs are the de facto method of choice to ensure that humans (rather than automated bots) are interacting with websites. Unfortunately, users often find it inconvenient to read characters and type them in. Image CAPTCHAs provide an alternative that is often preferred to text-based implementations. However, Image CAPTCHAs have their own set of security and usability problems. A key issue is their susceptibility to Reverse Image Search (RIS) and Computer Vision (CV) attacks. In this paper, we present a generalized methodology to transform existing images by applying various noise generation algorithms into variants that are resilient to such attacks. To evaluate the usability/security tradeoff, we conduct a user study to determine if the method can provide "usable" images that meet our security requirements -thus improving the overall security provided by Image CAPTCHAs.

Introduction

CAPTCHAs (Completely Automated Public Turing test to tell Computers and Humans Apart) are now ubiquitously found on the web to ensure that the entity interacting with a website is indeed human. While CAPTCHAs ensure that abuse of online forms is reduced, web users are forced to suffer through increasingly convoluted and unfriendly CAPTCHAs that negatively impact their user experience. Text-based CAPTCHAs are the most common implementation in use, due to their scalability, robustness, and ease of implementation. However, given their prevalence, many techniques have been developed to break such CAPTCHAs. As a result, alternative methods of form control and human verification have been sought for by the research community. Among the several different modalities that have been explored, image based CAPTCHAs have emerged as a plausible alternative, more suitable for the smartphone/mobile touch-capable environment. However, image CAPTCHAs come with their own set of problems, particularly in terms of scalability -it is hard to find large quantities of labeled/tagged images; and robustness -there is limited variation in the challenge question and vulnerability to single style of attack. In particular, reverse image search (RIS) has emerged as a particularly insidious type of attack against image CAPTCHAs [START_REF] Lorenzi | Web services based attacks against image captchas[END_REF]. In this paper, we propose a generalized methodology to transform existing images into more resilient variants. The basic idea is to introduce noise into the images using various noise generation algorithms which make it difficult to automatically retrieve the exact same image from the web, while still allowing humans to extract the key concepts from the image to correctly answer the CAPTCHA. Through this transformation, image CAPTCHAs can again become a viable alternative to text based CAPTCHAs having a similar level of security while providing a superior level of usability.

One interesting aspect of using noise generation algorithms to secure images is that the images produced by the algorithms we selected are very "grainy" or "pixelated" in appearance -very similar to a snowy TV picture. The noise introduced is primarily additive and multiplicative in nature, thus it tends to shift around color values in various pixels based on a threshold of our choosing. The benefit to this noise is demonstrated when the image is viewed as a matrix of numbers (as a computer would "see" the image), the values vary wildly and do not follow the patterns typical of a structured image. However, when viewed by a human eye (along with a human mind behind it), the colors blend into an image that is coherent and cognizable (the "Pointillism effect"). Strangely, this side effect of enhancing security actually does not impact usability negatively (to a point). In general, this effect is easier to achieve the further away your eye is from the image, or if the image is small in dimensions (scaled down). In honor of one of the co-creators of the Pointillism technique, 19th century French neo-impressionist painter Paul Signac, we have named our procedure SIGNAC (Secure Image Generation Noise Algorithms for CAPTCHAs).

Our method is similar to the concept of "emergence" -which refers to the unique human ability to aggregate information from seemingly meaningless pieces, and to perceive a whole that is meaningful [START_REF] Mitra | Emerging images[END_REF]. The image CAPTCHA utilization of this idea relies on the absence of meaningful information in local image parts which largely hinders existing computer vision algorithms from recognizing emerging figures [START_REF] Jian | Emerging images synthesis from photographs[END_REF]. The difference between our proposed SIGNAC method and emergence is that we are using an original image (I) and altering it to a new image (I') through a series of image transformations and alterations. We believe this provides a stronger "concrete" foundation for the images generated by the SIGNAC method than would be created by emerging images without giving away too many clues to segmentation/edge detection algorithms.

The rest of the paper is structured as follows. In Section 2 we review the related work. Section 3 details attacks and defense strategies. Section 4 presents the proposed methodology. Sections 5 and 6 present the experimental evaluation and the usability study respectively. Finally, Section 7 concludes the paper.

Related Work

From the first introduction of the CAPTCHA [START_REF] Von Ahn | Telling humans and computers apart automatically[END_REF], there has been significant work on categorizing and creating different CAPTCHA challenges based on alternate modalities such as images [START_REF] Chew | Image recognition captchas[END_REF]. Usability is often a key challenge -Yan et al. [START_REF] Yan | Usability of captchas or usability issues in captcha design[END_REF] provide a general framework for evaluating usability. In recent years, the complexity of text-based CAPTCHAs has been steadily increasing to provide robustness against attacks, but also hampering their usability. As mentioned above, this has led to alternatives such as image based CAPTCHAs. However, given the continuous improvement in computer vision algorithms, image CAPTCHAs have also become vulnerable to attack from methods such as edge detection, object recognition, or pattern recognition. As demonstrated by several studies [START_REF] El Ahmad | The robustness of a new captcha[END_REF][START_REF] Zhu | Attacks and design of image recognition captchas[END_REF][START_REF] Lorenzi | Attacking image based captchas using image recognition techniques[END_REF][START_REF] Hernandez-Castro | Side-channel attack on the humanauth captcha[END_REF][START_REF] Fritsch | Attacking image recognition captchas[END_REF], newly deployed real world CAPTCHAs frequently do not take into account advances in computer vision research literature and make common mistakes that could have been accounted for during their design phase.

Newer CAPTCHAs leverage the power of images to exploit the humanmachine gap. For example, image orientation [START_REF] Gossweiler | What's up captcha?: A captcha based on image orientation[END_REF] is comparatively easy for humans but difficult for computers. Similarly, "scene tagging" [START_REF] Matthews | Scene tagging: Image-based captcha using image composition and object relationships[END_REF] tests the ability to recognize a relationship between multiple objects in an image that is automatically generated via composition of a background image with multiple irregularly shaped object images. IMAGINATION [START_REF] Datta | Imagination: A robust image-based captcha generation system[END_REF] also uses a similar "image composition" method. Image distortion [START_REF] Mehrnejad | Multiple seimcha: Multiple semantic image captcha[END_REF] has also been suggested as an alternative. One interesting recent invention is that of the GOTCHA [START_REF] Blocki | Gotcha password hackers! In AISec[END_REF], which is essentially a randomized puzzle generation protocol, which produces unique images similar to inkblot tests. While questions about its usability remain, it is a promising emerging avenue of anti-bot security methods research.

The main enemy of modern image CAPTCHAs that attempt to work at scale is the modern Content Based Image Retrieval (CBIR) engine [START_REF] Datta | Image retrieval: Ideas, influences, and trends of the new age[END_REF]. Most major search engines today offer some CBIR capability with their "image search" feature, usually in the form of image retrieval, which can allow an attacker to find an exact match (Reverse Image Search) or other uses of an image on the web that have been used in a CAPTCHA challenge. One subset of CBIR, Automated Image Annotation, provides an extreme threat to simple naming image CAPTCHAs as it can provide an automated answer in the form of a tag for what is presented in the image. Recently, Lorenzi et al. [START_REF] Lorenzi | Web services based attacks against image captchas[END_REF] have shown how CBIR and ALA can be used to break several modern image CAPTCHAs.

Attack Methods and Defense Strategies

We now discuss two particular types of attack -Reverse Image Search (RIS) engine attacks and Computer Vision (CV) attacks. These are particularly strong against image CAPTCHAs. We also discuss the general defense strategy of adding noise to the image to make it more robust to these attacks. As with all CAPTCHAs, we are again faced with the challenge of balancing security with usability. Since we are utilizing a noise addition method, the image cannot be altered to the degree that a human observer loses the ability to recognize the content of the image (rendering it useless for our purposes).

Stopping Image Search Attacks

First, our noise addition algorithms must stop reverse image search engines from finding image matches indexed online (Google image search3 and Tineye4 ). This is an important security enhancement as image CAPTCHAs traditionally have At this point, the attacker can probabilistically determine which image is most likely the cat image (or eliminate the other image choices through the same process). The bad news for those attempting to develop security measures against RIS engine attacks is that the engines themselves are proprietary (trade secret) and closed source, forcing the CAPTCHA security developer to devise a set of experiments that attempt to probe a "black box" to learn its behavior.

The good news is that the RIS engines are available for use by the public with reasonable limits established (50 test images per day, up to 150 per week), and a security expert with access to or knowledge of "image fingerprinting" and image processing literature can use this body of knowledge to provide clues for educated guesses as to the methods that RIS engines are utilizing to identify matches. The noise generation method we propose works on the premise of introducing an amount of noise such that the image used for a CAPTCHA challenge has been altered enough from the original that the various "image fingerprinting" metrics used to determine matches have been "tricked" -that is they no longer see the image as a match as its information diverges from the original image beyond their threshold/similarity metric. Technically speaking, the image returned by the method is a different image, as the noise changes the values of the pixels in the image. A distance metric (change from original) is useful to model the noise alterations from original image to new image. However, the new image (postnoise) is still functionally depicting the same content as the original, albeit in a degraded fashion. Stopping RIS engines from finding matches means indexed images can be used as CAPTCHA challenges again, increasing the sample space of potential usable images significantly.

Stopping Computer Vision Attacks

Second, the noise algorithms must be able to alter the image enough to hinder or stop altogether, general image/object recognition algorithms that would attempt to solve image recognition challenges.

One popular CV algorithm is SIFT [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF], which stands for Scale-Invariant Feature Transform. While it has previously been used in many applications, we are interested only in its ability to perform object recognition tasks. ASIFT [START_REF] Morel | Asift: A new framework for fully affine invariant image comparison[END_REF], which stands for affine-SIFT, is an improvement over SIFT. It considers the lattitude and longitude angles that are ignored by SIFT and then combines that information with SIFT to provide a more complete analysis than SIFT alone. As such, it significantly outperforms SIFT and is more of a challenge to defeat. By adding noise to the image, it should throw off the keypoints calculations so that when it compares two images, the noised image does not have the same keypoints and it fails to return a match. Note that the web application uses grayscales and resizes the images before the CV algorithm is run.

Another important point to consider is that we used an online service to perform the SIFT and ASIFT analysis [START_REF] Morel | Asift: A new framework for fully affine invariant image comparison[END_REF]. The above computation could be completed in approximately 7 seconds through a web form. As more of these services move online, an attacker no longer needs to run local image matching or CV tools, and can script a live attack that pipes the CAPTCHA challenge through the appropriate tools to generate and even submit a correct response.

For example, in our aforementioned cat image scenario, imagine in this case the attacker decides to use image/object recognition with a CV toolkit. The attacker has trained and tested their algorithm of choice (e.g., SIFT) on various images of cats gathered from around the web and can recognize them with a good degree of accuracy. When he feeds the CAPTCHA challenge image into the algorithm, it returns a high probability of the image being of a cat. Using Fig. 2: CV Attack with SIFT & ASIFT the noise generation algorithms, the image of the cat can be altered enough so that the CV algorithms return a low probability or cannot determine what the image is depicting, but a human can still determine it is showing a cat. The intention is to use the noise to distort the edges of scenes/objects and alter the patterns within the image enough such that various commonly used CV techniques fail to provide meaningful results for an attacker. Also image filters can be used to distort and move pixel neighborhoods such that detection and mapping algorithms fail to achieve matches and/or detect similarity. Figure 2 shows that both SIFT and ASIFT can overcome scaling issues (mappings are found to a smaller, cropped image of the cat), and ASIFT typically provides more mappings than SIFT.

Methodology

Our method is designed to work with existing image CAPTCHAs that rely on a database of images for challenges. After application of SIGNAC, we demonstrate that the same database of images provides better security against RIS and CV based attacks. The MATLAB image processing toolbox is used to generate the new secure images. The function imnoise is used to add noise to the images. The test image set contains 100 images in total, 10 images in each of 10 different categories: airplane, bird, car, cat, doll, fish, flower, monkey, robot, and train. The categories are deliberately made "concrete" instead of abstract, as this makes it easier to create naming and distinguishing image CAPTCHAs that will be straightforward for user/usability testing. This also provides the CV algorithms with an "object" to recognize.The noise functions utilized in the method are the four generalized noise functions available in the MATLAB IPT 5 .

The SIGNAC Approach

As discussed above, SIGNAC is implemented using the MATLAB Image Processing Toolbox. The script below gives an idea of the method in action. X is the image at the initial starting point when it is read into the IPT. c1 through c5 represent the image at various stages of its alteration. Note that this example is a multimethod output, as different noise and filter functions are being used to generate an image at each step. It is important to note that ordinality plays a large factor in the outcome of the image's success or failure in defeating an RIS engine, as discussed in the following section. This script is designed to create the image filter, read in the image file, apply noise, filter the image, then apply noise 3 more times before writing the image to a file. This script represents the final script used to create the secure image set used in our experiments. Salt and pepper noise can be considered the most destructive type of noise, as it is the most extreme -changing pixel values to 0's and 1's. The motion filter is then applied to the image with a len of 11 pixels and a theta of 3 degrees counterclockwise, which serves to relocate the pixels that were changed with the addition of the salt and pepper noise to new areas around the image. This aids in obfuscation of clues about pixel values in a particular neighborhood, i.e., multiple pixels will now be distorted with values that differ from the original. After the filter is applied, multiplicative noise in the form of the speckle noise function distributes its noise in a uniform fashion throughout the image, followed by the addition of white Gaussian noise. The final step involves using the Poisson noise function, which does not add artificial noise, instead it generates noise from the image data and then applies it to the image using a Poisson distribution. This serves to further obfuscate the artificial noise that was added during previous steps by shifting the pixel values around.

RIS Engine Probing

Figure 3 shows an example of a single image test working against the RIS engine Tineye. For the original figure (3a), Tineye provides exact match results.

Single Noise Function, Single Stage Currently, the initial image returns 16 exact matches from across the web. These results were gathered using a single image noise function in a single step on the original image to produce an image that returns 0 exact matches. Note that these values are unique to this image, and vary based on the image properties.

Ordinality Test This test demonstrates the ordinality of noise functions. These tests were run with the default settings of each noise generation function to see if the order in which the functions are applied affects the results. Table 1 gives the results with the different orders. Note that these results were obtained using the original cat image, and these results apply only to that image. From these results, it is clear that order makes a difference as the range for matches is +-2 matches, with a high of 11 matches and a low of 9 matches. We then further investigate the chain of methods that produce the least amount of matches. Threshold Determination After deciding on an appropriate ordinality for noise methods, it must be determined the minimum threshold at which zero matches are reached -the key to our anti-RIS security criterion. A rough metric is used first, incrementing each mean value by 0.1 until zero matches are found. Then it decrements by 0.05 until a match and then increments or decrements by 0.01 until the minimal value is reached with zero matches. Figure 4 shows two scripts that embody these principles in action. Note that both scripts provide zero matches, however, the second script produces a clearer image because less noise overall is added during the application of additional functions. This is important for usability reasons -as the clearer the image is, the easier the chance a real human will have in recognizing what it depicts.

However, the values are extremely sensitive. For example, decrementing the mean in the initial noise function of the previous script by 0.01 to 0.1 produced 5 matches. Decrementing both means c3 and c4 by 0.01 each produced 8 matches. It is a painstaking and involved process to tune each image for a working minimum. Unfortunately, this process must be done for each image on an individual basis and cannot be generalized beyond offering a rough threshold for which any series will return zero matches, and this threshold is usually quite high and may impact usability. As such, this script serves as the endpoint for security against RIS engines, as zero matches are returned with these values. Computer vision based attacks are an entirely different subject, and there are no guarantees that this RIS minimum will have any impact on the ability of CV tools to perform recognition tasks.

Noise for Anti-Computer Vision

While stopping RIS engines was the primary challenge, CV tools are powerful and have been successfully used to defeat image based CAPTCHAs in the past. Thus, we aim to make it as difficult as possible to use them in performing object recognition tasks. One such CV attack case is that of edge detection. This is a key component of object recognition, and being able to foil it will go a long way in stopping any CV attacks from performing this task on an image recognition CAPTCHA challenge.

In Figure 5a, we can see the results of a Sobel edge detection run on the test image. It clearly depicts a cat, while also picking up some of the wrinkles in the sheet behind the cat. Enough detail of the cat comes through that a CV algorithm could make a decision about what is depicted in the image. Note that when edge detection is performed, the image is first converted from RGB to grayscale, and then to binary (hence the black & white) after the edge detection algorithm is run. Figure 5b shows the same Sobel edge detection method run on the image of the cat that has been noised. It can be seen that the cat has completely disappeared -only white dots on a black background appear. No useful information can be gained from this image.

Experimental Results and Analysis

We now describe the experimental evaluation to test image security against both RIS engine attacks and CV attacks using the aforementioned online tools. We have gathered 100 random indexed images from 10 categories and applied the method described in Section 4. Note that the image filter values did not change during the course of the experiments, only the mean values of the noise functions.

RIS Engine Testing

The goal of this experiment was to establish a baseline for which a set of noise functions can provide zero exact matches against both Google (G) and Tineye's (T) reverse image search engines. As mentioned in the Methodology section, the approach we use is more conservative from the security perspective, in that many of the images are no longer returning matches at much lower levels of noise overall. We consider even 1 match a failure -thus we do not report specific numbers of matches for each image failure. The number following the search engine designation is the number in the set of 10 for that category, e.g., car contains 10 images total, numbered 21-30 -T22 means that image 22 failed to produce zero matches as matches were found on Tineye (but not Google). Table 2 shows that at 0.25 mean noise, we have 8 out of 100 unique images returning matches. Tineye has one unique hit (T22) and Google has five unique hits (G32,G57,G77,G79,G81). There is overlap on image 84 and 85 as both engines returned matches. This means that out of our random sample of 100 indexed images, 92 out of 100 returned zero matches. At 0.30 mean noise, we Fig. 7: Exact Match Test: Original Vs. Noise with false positives Fig. 8: Shape Test: Noised image with similar shape image have 1 out of 100 unique images returning a match. Tineye and Google both return matches for the same image. This means that out of our random sample of 100 indexed images, 99 out of 100 returned zero matches.

Computer Vision Testing

In this section, we evaluate the effectiveness of SIFT and ASIFT to provide object detection and image matching. The key takeaway is to fool the keypoints calculator into examining incorrect correspondences by inflating the number of keypoints in an image or not finding any matches due to an insignificant matching value. Figure 6 demonstrates failure to find matching keypoints on an exact image match (original clear image vs. noised image).

It may be observed from Figure 7 that SIFT has returned zero matches, but ASIFT has returned 31 matches. However, upon further investigation, we can see that some of the matches are false positives. More specifically, we can see that some of the points provided are incorrect, as it seems the noise has been mistaken for keypoints. However, in both cases, SIFT has returned zero matches, and caused enough doubt in the ASIFT responses, thus discouraging potential attackers. In Figure 8, we can see that ASIFT was fooled by a similarly shaped image. In this case the fish and the hat have a similar shape, and it was enough to return matches, even though clearly the two images are quite different. It is worth noting that in this example, as we scaled the size of the hat image, the ASIFT results dropped to zero. Note that the ASIFT and SIFT engines are sensitive to slight changes in any images (noised or otherwise), and thus generalizing the results to all images will require more study.

Limitations

As with all noise generation functions, there exists the possibility that their alterations to the image can be significantly decreased with smoothing functions/image filters or reversed entirely by an appropriate function. Sufficiently advanced attackers with image processing experience may be able to reverse some of the distortion effects that come as a result of the noise generation to the degree that the image becomes vulnerable to RIS or CV attacks again. We attempt to minimize this weakness by using randomness in the function when applying the algorithms to the images, as well as using image specific properties to provide alterations within the image. We believe the method has enough merit to be explored further and that the CAPTCHA security community will provide the appropriate level of vetting of our methodology in due time.

Secondly, there exist images that cannot be satisfactorily "noised" -more specifically, the image will either fail to be recognizable by a human due to the excessively high level of noise added to the image to provide the security guarantee, or it will be recognizable to a human but fail to meet the security guarantee because the noise level is too low. This tends to occur when the image does not have colors (e.g. it is mostly composed of black and white.) We plan to explore this behavior in the future and propose solutions for it.

Usability Study

To test the usability of the noise method on human users, we designed 4 different styles of image CAPTCHA with varying degrees of difficulty. Style 1 displays an image and asks the user to describe it by entering a description (freeform response). Style 2 displays an image and provides a dropdown box with 4 responses, with 1 of the 4 choices being the correct answer. Style 3 displays a dropdown box with 5 responses, 4 choices and not here. Style 4 asks the user to select the image from 3 images that best represents X, where X is an image category. The order of difficulty is (1,3,2,4) from most difficult to least difficult. All example of each is depicted in Figure 9. For this experiment, 100 noised images were generated in total, 10 images gathered from a web search in each of 10 different categories. The 10 image categories were chosen to be "concrete", to lower ambiguity for the user (airplane(1), bird(2), car(3), cat(4), doll(5), fish [START_REF] Fritsch | Attacking image recognition captchas[END_REF], flower [START_REF] Gossweiler | What's up captcha?: A captcha based on image orientation[END_REF], monkey [START_REF] Hernandez-Castro | Side-channel attack on the humanauth captcha[END_REF], robot [START_REF] Jian | Emerging images synthesis from photographs[END_REF], train [START_REF] Lorenzi | Web services based attacks against image captchas[END_REF]). All 4 styles have the option to click a link to serve up a new CAPTCHA if the user cannot understand/decipher/solve the one they have been given. This is tallied as "no response" by our database. The study contained approximately 60 undergraduate students who provided anonymous responses to a random series of CAPTCHAs served in the various styles of previously described. The results are shown in Table 3. Not surprisingly, style 1 shows the highest percentage of no response (N), which means that the user was unable to decipher the image or felt unable to answer the question. This is followed by style 2 at 24% and 3 and 4 at 13% and 10% respectively. It is important to understand that styles 2(20%), 3(25%), and 4(33%) provide clues for a chance to guess correctly to the user. As such, one can expect a higher level of correct responses as guessing plays a factor in the results. With the case of 3 and 4, the correct response is provided within the framework of the CAPTCHA.

From the data we gathered from users, there is an initial period where the users familiarize themselves with the different challenge styles and give more incorrect responses. As they continue to answer questions and become acquainted with various styles, their accuracy and correctness increase significantly. While the number of images used for testing (100) is not very large, the results amply demonstrate that this is a valid method that can be used by humans to a successful degree.

Conclusions and Future Work

In this paper we have shown how noise addition can serve as an effective method to solve the scalability problem of image CAPTCHAs and effectively foil Re-verse Image Search and Computer Vision attacks. In the future, we plan to test various additional methods of image alterations. We also plan to develop and test multimodal CAPTCHAs, that is, CAPTCHAs that utilize one or more test methods (text based, image based, audio based, etc.) using a combination of protection methods and usability enhancements to provide a comfortable user experience with the maximum level of security possible given those criteria.

Fig. 1 :

 1 Fig. 1: Reverse image search attack with metadata. (a) depicts the CAPTCHA images without noise, (b) depicts results of a Google image search

Fig. 3 :

 3 Fig. 3: RIS Engine Probing

Fig. 4 :

 4 Fig. 4: SIGNAC MATLAB Scripts

Fig. 5 :

 5 Fig. 5: Edge detection tests

Fig. 6 :

 6 Fig. 6: SIFT & ASIFT image matching

Fig. 9 :

 9 Fig. 9: CAPTCHA Styles

Table 1 :

 1 Results of Ordinality Test

	Primary Noise	Permutations # of Results Primary Noise	Permutations # of Results
	Function			Function
		GKPS	10		KGPS	09
		GKSP	10		KGSP	11
	Gaussian (G)	GPKS GPSK	11 10	Speckle (K)	KPGS KPSG	10 10
		GSKP	10		KSGP	11
		GSPK	10		KSPG	11
		SGKP	11		PGKS	10
		SGPK	11		PGSK	09
	Salt and Pep-per (S)	SKGP SKPG SPGK	09 10 11	Poisson (P)	PKGS PKSG PSGK	10 10 10
		SPKG	09		PSKG	09

Table 3 :

 3 Results for CAPTCHA Style Responses

	CAPTCHA Style % Right % Wrong % No Response
	1	45%	20%	35%
	2	64%	11%	24%
	3	67%	21%	13%
	4	78%	12%	10%

https://www.google.com/img

https://www.tineye.com/

http://www.mathworks.com/help/images/ref/imnoise.html


Liang Deng
email: dengliang1214@smail.nju.edu.cn

Qingkai Zeng

Yao Liu

ISboxing: an Instruction Substitution based Data Sandboxing for x86 Untrusted Libraries

Keywords: Data sandboxing, instruction substitution, untrusted libraries, instruction prefix

Dynamically-linked libraries are widely adopted in application programs to achieve extensibility. However, faults in untrusted libraries could allow an attacker to compromise both integrity and confidentiality of the host system (the main program and trusted libraries), as no protection boundaries are enforced between them. Previous systems address this issue through the technique named data sandboxing that relies on instrumentation to sandbox memory reads and writes in untrusted libraries. However, the instrumentation method causes relatively high overhead due to frequent memory reads in code. In this paper, we propose an efficient and practical data sandboxing approach (called ISboxing) on contemporary x86 platforms, which sandboxes a memory read/write by directly substituting it with a self-sandboxed and function-equivalent one. Our substitution-based method does not insert any additional instructions into library code and therefore incurs almost no measurable runtime overhead. Our experimental results show that ISboxing incurs only 0.32%/1.54% (average/max) overhead for SPECint2000 and 0.05%/0.24% (average/max) overhead for SFI benchmarks, which indicates a notable performance improvement on prior work.

Introduction

Applications commonly incorporate with dynamically-linked libraries to achieve extensibility. However, a library, which might be buggy or even come from a malicious source, could be used by attackers to disrupt both integrity and confidentiality of the host system. Even though the host system contains no vulnerabilities, bugs and malicious behaviors in the library can lead to compromise of the entire application since no protection boundaries are enforced.

One major type of protections to address this issue is through software-based fault isolation (SFI) which isolates untrusted libraries from a trusted host system. The original SFI technique named sandboxing (including data sandboxing Instead, ISboxing trades some protection granularity for both practicality and efficiency. We highlight three key features which distinguish ISboxing from prior work:

-Easy-to-implement. ISboxing achieves data sandboxing efficiently without complex optimization work. It just needs to identify each memory-access instruction and substitute it, which is easy to implement correctly. -Binary-only. ISboxing is implemented as pure binary transformation requiring no cooperation from source code or debugging symbols, and thus compatible with legacy libraries. -Efficient. ISboxing incurs negligible overhead for sandboxing both memory reads and writes, since the substitution-based method requires no additional instrumentation instructions.

We have implemented ISboxing to sandbox user-space libraries on Windows. The implementation has a clear architecture comprised of a disassembler, a rewriter and a verifier. The disassembler disassembles a given library's binary executable (e.g., a PE file) and identifies memory-access instructions. The rewriter then statically substitutes each memory-access instruction. ISboxing includes a tiny verifier at the end of its workflow to validate the output of the rewriter. In this way, we can remove the disassembler and the rewriter from the TCB.

Related Work

SFI.

Since SFI was first proposed by Wahbe et al. [START_REF] Wahbe | Efficient software-based fault isolation[END_REF], a main portion of its following work focuses on reducing the runtime overhead of sandboxing especially on popular hardware platforms (e.g., x86). PittSFIeld [START_REF] Mccamant | Evaluating SFI for a CISC architecture[END_REF] is the first work that applies SFI to x86 platforms which feature variable-length instructions. NaCl-x86-32 [START_REF] Yee | Native client: A sandbox for portable, untrusted x86 native code[END_REF] and Vx32 [START_REF] Ford | Vx32: Lightweight user-level sandboxing on the x86[END_REF] provide efficient data sandboxing relying on x86-32 segmentation. NaCl-x86-64 [START_REF] Sehr | Adapting software fault isolation to contemporary CPU architectures[END_REF] further adapts SFI to contemporary x86-64 platforms, but it only sandboxes memory writes for performance and requires compiler-level supports. XFI [START_REF] Erlingsson | XFI: Software guards for system address spaces[END_REF] provides a stronger and more comprehensive protection system for executing untrusted code. Besides sandboxing, XFI provides a high-integrity stack protection model for protecting return addresses. The system of Zeng et al. [START_REF] Zeng | Combining control flow integrity and static analysis for efficient and validated data sandboxing[END_REF], on the other hand, focuses on exploring a more efficient support for data sandboxing by combining CFI and static analysis. Strato [START_REF] Zeng | Strato: A retargetable framework for low-Level inlined-reference monitors[END_REF] explores the building of a re-targetable framework for CFI and data sandboxing on a compiler intermediate representation where many optimizations can be realized without sticking to a certain hardware platform. REINS [START_REF] Wartell | Securing untrusted code via compileragnostic binary rewriting[END_REF] is the first work that implements SFI through pure binary rewriting with trivial performance overhead, however it actually only implements code sandboxing, without discussing data sandboxing. Additionally, a series of papers [START_REF] Castro | Fast byte-granularity software fault isolation[END_REF][START_REF] Akritidis | Baggy bounds checking: An efficient and backwards-compatible defense against out-of-bounds errors[END_REF] study how to enforce fine-grained SFI and memory access control. MIP [START_REF] Niu | Monitor integrity protection with space efficiency and separate compilation[END_REF] proposes an x86-64 SFI approach similar to ours. However, it still needs to insert additional instructions for data sandboxing, and thus it avoids sandboxing memory reads for performance. Its method also does not address the issue of practicability, e.g., it requires complex compiler-level register liveness analysis to find scratch registers.

CFI. CFI was first introduced by Abadi et al. [START_REF] Abadi | Control flow integrity[END_REF] for enforcing the integrity of a program's CFG constructed by sophisticated pointer analysis. CFI is a generic software methodology, which in theory can be applied to any systems (e.g., smartphones [START_REF] Davi | MoCFI: A framework to mitigate control-flow attacks on smartphones[END_REF][START_REF] Pewny | Control-flow restrictor: compiler-based CFI for iOS[END_REF], and commodity OS kernels [START_REF] Criswell | KCoFI: Complete control-flow integrity for commodity operating system kernels[END_REF]). However, the construction of a precise CFG is difficult on pure binaries, and enforcing precise CFG in a program often incurs high performance overhead. For practical applications, researchers have attempted to leverage a relaxed CFI model and apply it to legacy binaries [START_REF] Zhang | Practical control flow integrity & randomization for binary executables[END_REF][START_REF] Zhang | Control flow integrity for cots binaries[END_REF].

Assumptions and Attack Model

As with prior work, we assume the host system and the verifier are correct. We assume code regions and data regions in executables to be separated. The data regions are not executable and the code regions are not writable. This requirement is satisfied due to the wide deployment of W⊕X protection in modern OSes (e.g., DEP in Windows). We assume that the libraries do not self-modify their code or dynamically generate code. This requirement is always satisfied for traditional executables compiled from high-level languages. We assume that the libraries have well defined APIs which specify their parameter types and calling conventions. This is reasonable since it is necessary for the user of a library to understand how to use it. However, source code or debugging information is not required.

Two sources of attacks we consider are libraries designed by malicious authors, and libraries with bugs that could be subverted by attackers. Since untrusted libraries run in the same address space with the host system, when compromised, they would access arbitrary data and execute arbitrary code in memory. Therefore, the data integrity, data confidentiality and control flow integrity of the host system cannot be guaranteed any longer.

Instruction Substitution based Data Sandboxing

Data Sandboxing Policy

ISboxing divides the address space into a protected domain and a trusted domain. ISboxing runs untrusted libraries in the protected domain to contain faults, while the host system (the main program and trusted libraries) runs in the trusted domain. Hereafter we refer to the libraries running in the protected domain as sandboxed libraries. The data sandboxing policy dictates that both memory reads and memory writes in sandboxed libraries must be restricted to a designated continuous data region, so that the integrity and confidentiality of the host system can be guaranteed. Hereafter we refer to this data region as sandbox region. In the following, we will detail ISboxing's data sandboxing approach to enforce this policy. For a better understanding, we start with the background.

Background: x86 Memory Addressing

We first introduce the memory addressing on x86 platforms [START_REF]Intel Corporation: Intel 64 and IA-32 architectures software developer's manual[END_REF]. In a memoryaccess instruction, the address of its memory operand is referenced by means of a segment selector and an offset. In x86-64, segmentation is generally disabled, that is, the effective address of the memory operand is directly the offset. The offset can be specified as a direct offset which is a static value encoded in code, or an indirect offset through an address computation made up of one or more of the following components: displacement, base register, index register and scale. Rip-relative addressing is also available, which calculates the offset by adding a displacement to the value of current rip register. Data sandboxing only needs to sandbox memory-access instructions with indirect offset, because memoryaccess instructions with direct offset and rip-relative addressing instructions can be statically verified.

Operand Size and Address Size. On x86 platforms, the operand of an instruction has an operand size and an address size [START_REF]Intel Corporation: Intel 64 and IA-32 architectures software developer's manual[END_REF]. The operand size selects the size of operand and the address size determines the size of address when the operand accesses memory. In 64-bit mode, the default address size is 64 bits and the default operand size is 32 bits, but defaults can be overridden using instruction prefixes. For example, when an instruction uses the operand-size prefix (0x66) or the REX opcode prefix (0x48), its default operand size (32 bits) will be overwritten to 64 bits. When a memory-access instruction uses the address-size prefix (0x67), its default address size (64 bits) will be overwritten to 32 bits. As a result, it cannot address the memory outside 32 bits. The original motivation of these prefixes is to allow mixed 32/64-bit data and 32/64-bit addresses at instruction granularity.

Previous Data Sandboxing

In Figure 1(a), we give an example of a memory-access instruction with indirect offset (a memory read) in pseudo assembly syntax. In the example, the instruc-tion loads data from the memory operand ([rax+0x10] ) to the rcx register. The memory operand is referenced by an indirect offset computed from a base register (the rax register) and a displacement (0x10 ). We show the x86 binary encoding of the instruction within the parentheses in the figure. We assume this instruction is a memory read in an untrusted library. In the following, we will illustrate how to sandbox it with previous data sandboxing.

For protecting confidentiality, the memory address represented by [rax+0x10] should be checked before the memory read. Figure 1(b) presents a sequence of instructions that should be inserted to perform the check. In the sequence, the register rdx is used as a scratch register for the check. Since the original value of rdx would be needed, the sequence should first save its value on the stack and restore it after the check. The rflags register also needs to be saved and restored in case that the and instruction would change its value and influence the subsequent computation. In the and instruction, the constant $MASK denotes the data-region mask that guarantees the memory read is restricted to the sandbox region.

ISboxing's Data Sandboxing.

For comparison, we use the same example to illustrate how ISboxing's data sandboxing works.

Overall Idea. From another perspective, the memory-read instruction (Figure 1(a)) is unsafe because it is an "all-powerful-addressing" instruction whose address size is 64 bits. That is to say, an untrusted library can generate arbitrary value in the rax register, and use this instruction to access arbitrary memory in the whole 64-bit address space (the range of [0,2 64 ]). This observation inspires us to sandbox the memory-read instruction by changing its address size.

Without inserting any instructions, we only substitute the memory-read instruction. In the new substitute (as shown in Figure 1(c)), we only add the address-size prefix (0x67) which transforms the address size from 64 bits to 32 bits (the upper 32 bits of the address will be zero-extended by the processor). In this way, the new substitute is self-sandboxed by its address-size prefix, as if we implicitly inserted a bitwise and instruction whose data-region mask is 0x00000000ffffffff. Therefore, the sandbox region of ISboxing is the range of [0,2 32 ], and using the new substitute to access memory outside the sandbox region becomes impossible.

Most importantly, to guarantee the correctness of the substitution, we must ensure that the new substitute is function-equivalent with the original one. To achieve this, we should ensure that the address of the memory operand is originally within the range of [0,2 32 ] (the sandbox region), so that the new substitute will perform the same computation when ignoring the upper 32 bits. This requires us to relocate all the library's memory to the sandbox region, as detailed in the following sections.

Handling Stack Instructions. In x86, there is one exception that the address size of the stack is always 64 bits when stack instructions (push, pop, call and ret) are performed to read/write data on the stack. Therefore, an untrusted library may maliciously set the stack pointer (the rsp register) to an address outside the sandbox region and use stack instructions to access disallowed memory. In this situation, our data sandboxing relying on address size cannot work.

We address this issue by sandboxing the rsp register based on instruction substitution. In x86, the operand size of each instruction determines the number of valid bits in the register (e.g., the rsp register): 64-bit operand size generates a 64-bit result in the register, while 32-bit operand size generates a 32-bit result, zero-extended to a 64-bit result in the register [START_REF]Intel Corporation: Intel 64 and IA-32 architectures software developer's manual[END_REF]. With this, we substitute each instruction modifying rsp (hereafter named rsp-modify instruction, e.g., sub rsp,$0x10 ) with an equivalent instruction (sub esp,$0x10 ) whose operand size is changed to 32 bits. The substitution work is easily performed by just removing the REX opcode prefix of the original instruction. Then the new substitute cannot be used to set the rsp register to any value outside the sandbox region, because the upper 32 bits of the rsp register are always zero-extended by the processor. It seems as if we implicitly inserted a bitwise and instruction.

Additionally, in x86, stack instructions (push, pop, call and ret) can implicitly modify the rsp register. Although they can only increase/decrease the rsp register by at most 8 bytes for each time, an attacker would chain a number of stack instructions to manipulate the rsp register (e.g., using ROP attacks [START_REF] Shacham | The geometry of ennocent flesh on the bone: Return-into-libc without function calls[END_REF][START_REF] Checkoway | Return-oriented programming without returns[END_REF]). We prevent this by simply inserting a guard page at the end of the sandbox region. The guard page is mapped as neither readable nor writable in the address space and thus any read/write on it will cause a page fault. Specifically, when an untrusted library uses stack instructions to modify the rsp register, the guard page cannot be crossed since the rsp register can only be increased by 8 bytes for each time. When the stack pointer reaches the guard page, executing any stack instruction again will cause a page fault and crash the untrusted library.

Constraints and Analysis. Comparing to previous data sandboxing whose sandbox region can be any size and in any position, ISboxing restricts the sandbox region to a fixed size and a fixed position in the address space. However, this is not a problem for sandboxing untrusted libraries in practice. First, the fixed size of ISboxing's sandbox region (4 GB) is large enough to contain quite a few libraries, since the virtual memory consumption of a real-world library is much smaller than 4 GB. In our observation, the virtual memory consumption of even a whole application is usually much smaller than 4 GB. Second, the constraint of the fixed position requires us to relocate libraries' memory to the sandbox region. As discussed in the next section, the memory relocation can be practically realized on libraries' executable binaries without any aids from source code or debug information.

Sandboxing Untrusted Libraries

Based on ISboxing's data sandboxing approach above, we further describe how to sandbox untrusted libraries on Windows. The implementation is realized through pure binary transformation on application binaries without any special support from underlying OS.

Binary Disassembling and Rewriting

We adopt CCFIR's disassembling method [START_REF] Zhang | Practical control flow integrity & randomization for binary executables[END_REF] which can correctly disassemble an x86 binary without source code or debug information. We take advantage of the fact that ASLR and DEP are widely adopted on Windows, and leverage the relocation information to disassemble binary code recursively and identify all possible instructions. Then we can find and substitute all memory-access instructions and rsp-modify instructions to enforce ISboxing's data sandboxing.

Memory Relocation

Data sandboxing requires that the memory of sandboxed libraries must reside within the sandbox region and the memory of the host system must reside outside the sandbox region. In this way, sandboxed libraries cannot access the memory of the host system. However, in real-world applications, their memory regions are often overlapped with each other. For example, the libraries and the host system often use the same Window's API HeapAlloc to allocate heap memory from the same heap, and their heap memory may be overlapped. In the following, we will detail the memory relocation for sandboxed libraries. The memory relocation for the host system is essentially identical.

Executable Relocation. Due to the ASLR mechanism, a binary executable's load base can be randomized without affecting the execution. To relocate an executable, we simply disable system's ASLR for the executable and modify the ImageBase field in the executable's file header which specifies the load base of the executable. In addition, some code and data in the executable should also be adjusted since they are generated based on the original ImageBase. Though system's ASLR is disabled, existing practical and more fine-grained randomization techniques [START_REF] Zhang | Practical control flow integrity & randomization for binary executables[END_REF][START_REF] Wartell | Binary stirring: Self-randomizing instruction addresses of legacy x86 binary code[END_REF][START_REF] Hiser | ILR: Whered my gadgets go?[END_REF] can be added to ISboxing.

Stack Relocation. The host system associates a separate stack with each thread that executes in a sandboxed library. Like XFI [START_REF] Erlingsson | XFI: Software guards for system address spaces[END_REF], our current implementation uses a memory pool from which host-system threads draw stacks when they call the library. The stacks in this pool are all allocated in the sandbox region, and managed by a state array and a single lock. The size of the pool can be adjusted at runtime. Heap Relocation. On Windows, applications invoke Windows APIs to allocate heap memory from the heap provided by system. The address of the heap memory is determined by system heap manager and is transparent to applications. For heap relocation, ISboxing realizes another heap manager (named ISboxing heap manager) to satisfy heap allocations for both sandboxed libraries and the host system. In our current implementation, ISboxing heap manager is a simplified version of Glibc's heap manager. It wholesales large memory chunks from the sandbox region using Windows API VirtualAllocEx and provides small memory blocks for sandboxed libraries. In this way, sandboxed libraries' heap memory will always reside within the sandbox region.

File Mapping Relocation. File mapping is the association of a file's contents with a portion of the virtual memory (file-mapping memory). Fortunately, unlike heap memory, applications can use Windows API (MapViewOfFileEx ) to specify the base address of file-mapping memory. This facilitates the realization of our file mapping relocation. ISboxing reserves a range of virtual memory in the sandbox region dedicated to file mapping for sandboxed libraries, and redirects libraries' file mapping requests to the API MapViewOfFileEx.

CFI Enforcement

Instead of code sandboxing, we leverage CFI, which is a more restrictive enforcement, to sandbox the control flows of untrusted libraries. The CFI enforcement, which guarantees a single stream of intended instructions, also ensures that ISboxing's data sandboxing cannot be bypassed. While CFI enforcement technique has been practically realized in CCFIR [START_REF] Zhang | Practical control flow integrity & randomization for binary executables[END_REF] with low performance overhead, we adopt CCFIR's method but use a simplified 1-ID CFI protection model. However, the code sandboxing approach discussed in REINS [START_REF] Wartell | Securing untrusted code via compileragnostic binary rewriting[END_REF] can also be used as an alternative.

As with CCFIR, we introduce a code section called Springboard. For each legal indirect target in library code, the Springboard has an associated stub containing a direct jump to it. Then, we instrument each indirect jump in the library to make sure that any indirect control flow will first jump to the Springboard and then use its stubs (containing direct jumps) to complete the control flow transition. Since the Springboard only contains direct jumps whose targets are legal, the CFI is ensured. In addition, a restrictive and validated host-system interface is enforced when the libraries invoke the host system. The interface only allows three kinds of control flows (which can also be specified and validated by host-system policies): 1) Imported function calls whose targets are referenced by sandboxed libraries' import address table (IAT). 2) Function calls whose targets are resolved at runtime by special API, e.g., GetProcAddress. 3) Returns to the host system. The details of how to protect these control flows are well discussed in CCFIR's Section IV-D.

The CFI enforcement also inherits the deficiencies of CCFIR. For example, the relaxed CFI enforcement was shown to be broken in face of new control-flow attacks [START_REF] Davi | Stitching the gadgets: On the ineffectiveness of coarse-grained control-flow integrity protection[END_REF][START_REF] Goktas | Out of control: Overcoming control-flow integrity[END_REF][START_REF] Carlini | Rop is still dangerous: Breaking modern defenses[END_REF]. Nevertheless, it is enough to sandbox untrusted libraries' control flows, and is more restrictive than the code sandboxing approach in previous SFI work.

Implementation

In our implementation, we have developed three major tools (a disassembler, a rewriter and a verifier) to transform library binaries (PE executables) for enforcing all ISboxing's protection on them. The implementation of the disassembler is similar to CCFIR and will not be repeated. The rewriter, whose input is the output of the disassembler, mainly performs the following work. First, the rewriter rewrites each memory-access instruction by adding the address-size prefix and each rsp-modify instruction by removing the REX opcode prefix. Second, it instruments each indirect jump and creates the Springboard section for CFI enforcement. Third, it modifies executable's file headers, relocation information and redirects heap allocation APIs to realize memory relocation. A library only needs to be rewritten once, and the rewritten binary can be shared by different applications for code reuse. In our current implementation, the rewriter takes about 3.5k LOC.

We provide a separate verifier to validate the correctness of ISboxing's protection. First, the verifier identifies all possible instructions in the rewritten binary. This is realized by scanning instructions one by one started from all indirect jump targets (in Springboard section), export table entries and the EntryPoint of the binary. For instructions not identified in this way, the CFI enforcement guarantees that they will never be executed in the runtime, because no control flows are allowed to be transferred to them. Then, for each possible instruction, the verifier checks if it conforms to the following rules: 1) If it is an indirect jump, it has been checked and redirected to the Springboard section. 2) If it is a memory-access instruction with indirect offset, its address size has been changed to 32 bits. 3) If it is an rsp-modify instruction, its operand size has been changed to 32 bits. 4) Memory-access instructions with direct offset, direct jumps and rip-relative addressing instructions are also statically validated since the code may come from a malicious source. In our current implementation, the verifier is self-contained and takes about 2.5k LOC, most of which are interpretation for x86 opcode decoding.

We have also developed a tool to transform host-system binaries (the main program and libraries) so that their memory will reside outside the sandbox region in the runtime. The tool also identifies host system's calls to the sandboxed libraries and adds a communication runtime for wrapping them (e.g., by identifying and wrapping imported function pointers and dynamically resolved function pointers). The communication runtime, which runs as a DLL in the host system, completes tasks such as copying arguments and results, switching stack and enforcing host system's policies, before transferring to the sandboxed libraries. In addition, the ISboxing heap manager used for heap relocation is developed as a dynamic library (a DLL in the host system) that satisfies heap allocations for both sandboxed libraries and the host system.

We have successfully applied ISboxing's implementation to SPECint2000, SFI benchmarks and some third-party libraries (e.g., JPEG decoder, 7-ZIP, plugins in Google Chrome), all of which are pure binaries (EXEs or DLLs) on Windows. It is worth noting that all the work is performed offline and does not influence the runtime performance.

Evaluation

Performance Evaluation

To evaluate our implementation, we conducted experiments on a Dell Optiplex 8 GB RAM, an Intel 82579LM Gigabit Ethernet card and a Windows 7 64-bit system. We measured the execution-time overhead of sandboxing a wide range of benchmark binaries on Windows, including SPECint2000 and SFI benchmarks. SFI benchmarks contain three programs (hotlist, lld and md5) which have been widely used by previous SFI work for evaluation [START_REF] Zeng | Strato: A retargetable framework for low-Level inlined-reference monitors[END_REF]. We treat each benchmark as if it were an untrusted library. All experiments were averaged over five runs. Table 1 presents the execution-time percentage increases of SPECint2000, compared to the unmodified version. The standard deviation is less than 0.8 percent. The CFI column shows the results of CFI enforcement. CFI enforcement is necessary for data sandboxing because it ensures a single stream of intended instructions. We are pleased to see that, with CCFIR's method, the overhead (average/max) is only is 3.76%/9.76% for x86-64 binaries. The RELOC column reports the overhead of the memory relocation discussed in Section 5.2. As we see, ISboxing gains some performance improvement. Through analysis, this is because ISboxing uses a simplified heap manager for memory relocation in our current implementation. ISboxing's users are free to choose other heap managers either for high performance [START_REF] Berger | Composing high performance memory allocators[END_REF] or for high level of security [START_REF] Novark | DieHarder: Securing the Heap[END_REF]. This performance difference can be mostly eliminated if they use a heap manager similar to Window's. The RELOC+DS column gives the results when both memory relocation and data sandboxing(for both memory reads and writes) are enabled, yet CFI enforcement is disabled at this time. As shown in the table, if we ignore the performance improvement of memory relocation(RELOC+DS minus RELOC ), the pure data sandboxing overhead in ISboxing is only 0.32%/1.54%(aver-Table 3. Code-size increase on SPECint2000. gzip vpr gcc mcf crafty parser eon perlbmk gap vortex bzip2 twolf avg increase (%) 5.8% 6.3% 6.5% 5.8% 6.2% 6.2% 7.1% 7.2% 7.7% 7.8% 5.6% 7.6% 6.7% age/max) on SPECint2000. This overhead is unsurprising as ISboxing does not insert any additional instructions into the benchmarks to achieve data sandboxing. The CFI+RELOC+DS column shows the overhead when all ISboxing's protections are enabled.

Table 2 presents the results of SFI benchmarks. The standard deviation is less than 0.6 percent. The results show that the pure data sandboxing overhead is 0.05%/0.24%(average/max) for SFI benchmarks.

Performance Comparison with Related Systems. We next compare ISboxing with the system of Zeng et al. [START_REF] Zeng | Combining control flow integrity and static analysis for efficient and validated data sandboxing[END_REF] and Strato [START_REF] Zeng | Strato: A retargetable framework for low-Level inlined-reference monitors[END_REF], which sandbox memory writes as well as reads with a number of optimizations to reduce runtime overhead. The pure data sandboxing overhead reported in Strato is as large as 17%/45%(average/max) for x86-64 SPECint2000 and 32%/62%(average/max) for SFI benchmarks (without adding CFI and memory relocation overhead). In Zeng et al.'s system, the pure data sandboxing overhead is 19%/42%(average/max) for x86-32 SPECint2000. It does not provide the results for x86-64, and thus the comparison is preliminary. Although other systems [START_REF] Mccamant | Evaluating SFI for a CISC architecture[END_REF][START_REF] Yee | Native client: A sandbox for portable, untrusted x86 native code[END_REF][START_REF] Ford | Vx32: Lightweight user-level sandboxing on the x86[END_REF][START_REF] Sehr | Adapting software fault isolation to contemporary CPU architectures[END_REF][START_REF] Niu | Monitor integrity protection with space efficiency and separate compilation[END_REF] incur low overhead, they either ignore sandboxing memory read or use hardware segmentation not available on contemporary x86 platforms.

Code-Size Increase

As a side benefit, ISboxing requires very small code-size increase to realize data sandboxing, since no additional instrumentation instructions are added to code. Table 3 presents the text-section size increase comparing to unmodified version for SPECint2000. On average, the text section grows only 6.7% for data sandboxing when CFI is not equipped.

Discussion

ISboxing trades some protection granularity for both efficiency and practicability. It only provides a single sandbox (the protected domain) running all untrusted libraries isolated from the host system, but cannot further provide multiple sandboxes. Thus it cannot deal with inter-module data accesses between untrusted libraries. Nevertheless, we believe ISboxing has a wide range of applications such as isolating untrusted third-party libraries or browser plugins from the host system (trusted libraries and the main program), especially when source code is unavailable and confidentiality is of importance.

In addition, an alternative method is to sandbox only memory reads (performance critical) in a single sandbox with ISboxing, while further sandboxing memory writes (less performance critical) in multiple sandboxes using previous instrumentation methods. In this way, we can achieve a better tradeoff between performance and granularity. In real world, security secrets (e.g., secret keys) often reside in the host system, thus a single sandbox for memory reads is enough to protect their confidentiality. If a library contains security secrets, we can choose to run it in the host system.

Conclusion

In this paper, we present an instruction substitution based data sandboxing, which is quite different from previous instrumentation based approaches. Unlike pure software approaches, we explore how an x86 feature (instruction prefix) can help build an efficient, practical and validated data sandboxing on contemporary x86-64 platforms. We apply our approach to practically sandboxing untrusted libraries on Windows, and perform a set of experiments to demonstrate the effectiveness and efficiency.

Fig. 1 .

 1 Fig. 1. An example to illustrate previous data sandboxing and ISboxing's data sandboxing.

Table 1 .

 1 ISboxing's runtime overhead on SPECint2000.

	CFI RELOC RELOC+DS CFI+RELOC+DS
	gzip 2.41% -0.37%	0.72%	3.78%
	vpr 0.01% -0.33%	0.43%	0.33%
	gcc 6.12% -1.55%	-1.83%	5.01%
	mcf 0.64% -0.55%	-0.57%	0.01%
	crafty 0.88% -0.08%	0.12%	0.88%
	parser 8.55% -0.17%	0.14%	7.81%
	eon 3.89% -1.18%	-1.01%	3.14%
	perlbmk 9.76% -2.81%	-2.28%	7.27%
	gap 4.81% 0.11%	0.00%	4.87%
	vortex 5.72% -1.70%	-1.23%	5.23%
	bzip2 2.31% -0.59%	0.95%	1.89%
	twolf 0.04% -2.49%	-3.33%	-2.85%
	avg 3.76% -0.98%	-0.66%	3.11%

Table 2 .

 2 ISboxing's runtime overhead on SFI benchmarks.

	CFI RELOC RELOC+DS CFI+RELOC+DS
	md5 0.69% 0.01%	-0.08%	0.81%
	lld 0.95% -0.21%	-0.21%	0.57%
	hotlist 2.79% -0.05%	0.19%	3.01%
	avg 1.48% -0.08%	-0.03%	1.46%

Acknowledgments. This work has been partly supported by National NSF of China under Grant No. 61170070, 61431008, 61321491; National Key Technology R&D Program of China under Grant No. 2012BAK26B01.


Zhijiao Zhang

Yashuai Lü

Yu Chen
email: yuchen@mail.tsinghua.edu.cn

Mitigating Code-Reuse Attacks on CISC Architectures in a Hardware Approach

Keywords: CISC processor, Unintended instruction, Code-reuse attack, Instruction execution verification

Recently, code-reuse attack (CRA) is becoming the most prevalent attack vector which reuses fragments of existing code to make up malicious code. Recent studies show that CRAs especially jump-oriented programming (JOP) attacks are hard and costly to detect and protect from, especially on CISC processors. One reason for this is that the instructions of CISC architecture are of variable-length, and lots of unintended but legal instructions can be exploited by starting from in the middle of a legal instruction. This feature of CISC architectures makes the finding of so called gadgets for CRAs is much easier than that of RISC architectures. Most of previous studies for mitigating CRA on CISC processors rely on software-only means to tackle the unintended instruction problem, which makes their approaches either very costly or can only be applied under restricted conditions. In this paper, we propose two hardware supported techniques. The first, which is the main contribution of this paper, is to eliminate the execution of an unintended instruction. This technique only requires a few modifications to the processor and operating system. Furthermore, the proposed mechanism has little performance impact on the examined SPEC CPU 2006 benchmarks (-0.093% ~2.993%). Second, we propose using hardware control-flow locking as a complementary technique to our protection mechanism. By using the two techniques together, an attacker will have little chance to carry out CRAs on a CISC processor.

Introduction

As the popularity of the Internet increases, so does the number of computer security threats from increasingly sophisticated attackers [1]. One common way to compromise a normal application is exploiting memory corruption vulnerabilities and transferring the normal program execution to a location under the control of the attacker. In these attacks, the first step is trying to overwrite a pointer in memory. Buffer overflow [START_REF] One | Smashing the stack for fun and profit[END_REF] and format string vulnerability exploitation [START_REF] Scut | Exploiting format string vulnerabilities[END_REF] are two well-known techniques to achieve this goal. Once the attacker is able to hijack the control flow of the application, the next step is to take control of the program execution to carry out some malicious activities. One of the typical and early attack techniques is code injection attack, in which a small payload that contains the machine code to perform the desired task is injected into the process memory. A wide range of solutions have been proposed to defend against memory corruption attacks, and to increase the complexity of performing buffer overflow and format string vulnerability exploitation [START_REF] Cowan | Pointguard TM: protecting pointers from buffer overflow vulnerabilities[END_REF][START_REF] Cowan | Stack-Guard: Automatic Adaptive Detection and Prevention of Buffer-Overflow Attacks[END_REF][START_REF] Cowan | Buffer overflows: Attacks and defenses for the vulnerability of the decade[END_REF][START_REF] Etoh | GCC extension for protecting applications from stack-smashing attacks[END_REF][START_REF] Shield | A stack smashing technique protection tool for Linux[END_REF]. To mitigate the code injection attack, a protection technique called W⊕X [START_REF] Team | Non-executable pages design and implementation[END_REF] was proposed. Under this protection regime, a memory page is either marked as writable or executable, but may not be both. Thus, an attacker may not inject data into a process's memory and then execute it simply by transfer control flow to that memory. Although the W⊕X technique is not foolproof [START_REF] Krahmer | x86-64 buffer overflow exploits and the borrowed code chunks exploitation technique[END_REF][START_REF] Mcdonald | Defeating Solaris/SPARC non-executable stack protection[END_REF], it was thought to be a sufficiently strong protection regime that both the processor venders like Intel and AMD and prevalent operating systems like Windows [START_REF]KB 875352: A detailed description of the Data Execution Prevention (DEP) feature in Windows XP Service Pack 2, Windows XP Tablet PC Edition 2005, and Windows Server 2003[END_REF], Linux [START_REF] Designer | Linux kernel patch from the Openwall project[END_REF], Mac OS X, and OpenBSD [START_REF] Foundation | OpenBSD 3.3 release[END_REF] now support it. However, recently, attackers circumvented the W⊕X protection by employing code-reuse attacks (CRAs), which reuse the functionality provided by the exploited application. Using this technique, which was originally called return-to-libc [START_REF]Return-to-libc attack[END_REF], an attacker can compromise the stack and transfer the control to the beginning of an existing libc function. Often the system call system( ) is used to launch a process or mprotect( ) is used to create a writable, executable memory region to bypass W⊕X. In 2007, Shacham showed that W⊕X protection regime could be entirely evaded by so called return-oriented programming (ROP) [START_REF] Shacham | The geometry of innocent flesh on the bone: Return-into-libc without function calls (on the x86)[END_REF] technique. In ROP, so called gadgets (small snippets of code ending in ret) are weaved together to achieve Turing complete computation without code injection. Since the advent of ROP, several effective defense techniques have been proposed [START_REF] Davi | Dynamic integrity measurement and attestation: towards defense against return-oriented programming attacks[END_REF][START_REF] Chen | DROP: Detecting returnoriented programming malicious code[END_REF][START_REF] Li | Defeating return-oriented rootkits with return-less kernels[END_REF]. However, a new class of codereuse attacks called jump-oriented programming (JOP) that does not rely on rets has been proposed [START_REF] Bletsch | Jump-oriented programming: a new class of code-reuse attack[END_REF][START_REF] Checkoway | Return-oriented programming without returns[END_REF][START_REF] Chen | Automatic construction of jump-oriented programming shellcode (on the x86)[END_REF]. In these JOP attacks, the attacker chains the gadgets by using a sequence of indirect jump instructions, rather than rets, thus bypassing the defense mechanisms designed for ROP. Until now, there is no efficient technique can prevent both ROP and JOP attacks.

The x86 microprocessors are the most widely used general purpose processor series today. As a typical CISC architecture, instructions on the x86 platforms are of variable-length, and decoding an instruction from any byte offset is allowed. As a consequence, every x86 executable binary contains a vast number of unintended code sequences that can be accessed by jumping to an offset not on an original instruction boundary. Both the ROP and JOP take advantage of this feature to discover useful gadgets, which makes CRAs more easily to be carried out on CISC processors than that of RISC processors. Some of the previous studies that target for CRA defense tackle this problem in software-only approaches, which makes the applications of their techniques limited to constrained circumstances.

In this paper, we propose effectively mitigating CRAs on CISC architectures in a hardware supported approach. The main contributions of the work in this paper are:  The unintended instruction problem of CISC processors is thoroughly resolved with only a few hardware and software modifications, and no application binary modification.  The techniques are evaluated by cycle-accurate simulations of SPEC CPU 2006 benchmarks. The experimental results show that our proposed techniques have very little performance impact on these benchmarks.  We further propose using hardware control-flow locking as a complementary technique to our protection mechanism.

The remainder of this paper is organized as follows. Section 2 describes the related work. The methodology and implementation details are presented in Section 3. The experimental evaluation is presented in Section 4. Section 5 offers some concluding remarks.

Related Work

The first step of a code reuse attack is to gain control of the program counter to divert program control flow to the first gadget. An attacker then may overwrite either the return address for the calling function or a function pointer with the address of the first gadget to divert the program control flow. Both software and hardware approaches were developed to prevent attackers from exploiting software vulnerabilities [4-8][23-26]. However, either these mechanisms are not adopted by hardware products or they are frequently not turned on as default when programs are compiled. As a result, attackers can always exploit software flaws to gain control of the program counter.

One tricky problem for CRA defense techniques on CISC platforms like x86 is the allowing of unintended instruction execution, which makes these defense techniques face more gadgets on CISC architectures. Before the advent of CRAs, some researchers of prior work [START_REF] Mccamant | Efficient, verifiable binary sandboxing for a CISC architecture[END_REF][START_REF] Yee | Native client: A sandbox for portable, untrusted x86 native code[END_REF] realized that the unintended instructions could be a potential security problem, and solved it by imposing alignment in the environment of a sandbox. Since the advent of CRAs, previous CRA defenses rely on dynamic binary instrumentation tools monitoring unintended instructions without the help of hardware [START_REF] Huang | A Dynamic Detection Method against ROP and JOP[END_REF][START_REF] Jacobson | Detecting Code Reuse Attacks with a Model of Conformant Program Execution[END_REF], which limits their practical use.

Another problem is unintended control flow transfers. To solve this problem, a number of defense techniques have been proposed, and most of them are against ROP attacks. Several approaches use a shadow stack to prevent control flow manipulation that relies on overwritten stack values [START_REF] Davi | ROPdefender: A detection tool to defend against return-oriented programming attacks[END_REF][START_REF] Francillon | Defending embedded systems against control flow attacks[END_REF]. Some try to detect gadget execution by monitoring return properties [START_REF] Davi | Dynamic integrity measurement and attestation: towards defense against return-oriented programming attacks[END_REF][START_REF] Chen | DROP: Detecting returnoriented programming malicious code[END_REF], and others proposed monitoring pairs of call and return instructions [START_REF] Chen | Efficient Detection of the Return-Oriented Programming Malicious Code[END_REF][START_REF] Kayaalp | Branch regulation: Lowoverhead protection from code reuse attacks[END_REF]. Several prevention approaches attempt to eliminate possible gadgets in library code [START_REF] Hiser | Where'd My Gadgets Go?[END_REF][START_REF] Pappas | Smashing the gadgets: Hindering return-oriented programming using in-place code randomization[END_REF], and alternative strategies include creating binaries or kernels that lack necessary characteristics for ROP attacks [START_REF] Li | Defeating return-oriented rootkits with return-less kernels[END_REF][START_REF] Onarlioglu | G-Free: defeating returnoriented programming through gadget-less binaries[END_REF]. Most of these techniques rely on known characteristics of ROP attacks, and some were proved to have flaws that the defense mechanisms can be bypassed. Several approaches require recompilation of the program, library or kernel binaries, which may pose a problem when the source code is not available.

Since JOP is a recently proposed technique, there are only a few proposals that target for JOP defenses. Among these defense techniques, [START_REF] Huang | A Dynamic Detection Method against ROP and JOP[END_REF], [START_REF] Jacobson | Detecting Code Reuse Attacks with a Model of Conformant Program Execution[END_REF] and [START_REF] Bletsch | Mitigating code-reuse attacks with control-flow locking[END_REF] are pure software approaches. To distinguish normal program execution from CRA attacks, they rely on the software dynamic binary instrumentation. As a result, to apply their techniques, the programs must be executed through a dynamic binary instrumentation tool like Pin [37] or a virtual machine, which limits the practical use of their approaches. [START_REF] Kayaalp | Branch regulation: Lowoverhead protection from code reuse attacks[END_REF] and [START_REF] Kayaalp | SCRAP: Architecture for signature-based protection from code reuse attacks[END_REF] are hardware supported approaches proposed by Kayaalp et al. By using binary rewriting, the branch regulation approach in [START_REF] Kayaalp | Branch regulation: Lowoverhead protection from code reuse attacks[END_REF] inserts markers to make jumps stay in a legal function. Branch regulation requires binary rewriting and cannot easily protect legacy binaries. It is also possible that a function may exist that can provide sufficient gadgets to mount an attack, and in this case security is not completely guaranteed. The work in [START_REF] Kayaalp | SCRAP: Architecture for signature-based protection from code reuse attacks[END_REF] proposes a hardware supported signaturebased protection mechanism. While this approach supports legacy software, it needs user to configure thresholds for CRA detection. Again, it is also one type of techniques that rely on known characteristics of CRAs.

Methodology

Elimination of Unintended Instructions

Figure 1 illustrates an example of unintended instruction sequence, which is similar to the one showed in [START_REF] Kayaalp | Branch regulation: Lowoverhead protection from code reuse attacks[END_REF]. The x86 assembly language used in this paper is written in Intel syntax. The disassembled code snippet is from the _IO_vfprintf function of libc-2.12-32. This code snippet consists of three instructions if decoded normally. However, if the decoding starts from the third byte of the call instruction, a different instruction sequence can be decoded as shown at the bottom of Figure 1, which contains three entirely different instruction. This unintended instruction sequence could possibly be used as a gadget, as the last jump instruction can be used to direct control flow to other gadgets (the memory location that register ebx points to). It should be noted that finding indirect jump instructions from unintended code sequence is extremely easy on x86 platforms, as byte FF represents the opcode of an indirect jump instruction on x86 [START_REF]64 and IA-32 Architectures Software Developer's Manual[END_REF], and FF is a common byte used in immediate values (bit-masks and sign bits of negative values).

Problem Analysis.

As well known, the processor pipeline can be roughly divided into five stages (i.e. IF, ID, EX, MEM and WB). Of the five stages, the instruction fetch stage fetches instructions from I-Cache according to the address pointed by program counter (PC), as illustrated in Figure 2. Therefore, it may be the most suitable stage to check whether an instruction is an intended instruction or not. For a variable-length instruction architecture, to know whether the current PC points to an unintended instruction, the processor needs a list of valid instruction addresses to be compared with, as illustrated in Figure 2. One way of acquiring the list of valid instruction addresses is disassembling the executable binary before its execution. When an executable binary has been loaded into memory, OS knows the location of each binary code section in the virtual memory space, and the valid address of each intended instruction can be obtained by sequentially disassembling the instructions from the start of each code section. Now with the list of valid instruction addresses, how to validate the legality of an instruction address? An inefficient preliminary solution is illustrated in Figure 3.

The solution depicted in Figure 3 first uses a recently validated address buffer (RVAB) to validate the current PC. The RVAB can be implemented in processor and functions similar to other LRU buffers in the processor. If the PC is not found in RVAB, then a further lookup will be needed. A program is often composed of several code sections, including the code sections from shared libraries. Instruction addresses within a code section are contiguous, but different code sections may not be contiguous in virtual memory space. Therefore, if a PC is not hit the RVAB, then the solution in Figure 3 first needs to find which code section this PC belongs to from a code section range list which can be derived from section information after the program has been loaded into memory. To save memory consumption, this preliminary solution organizes several contiguous addresses into an address chunk. The size of the chunk can be multiple of a byte. The first four bytes (for a 32-bit system) stores the first address, and each following byte stores an offset from the first address. To find a specific address, the processor must search through the address chunks of a code section. If a binary search algorithm is used, the average time consumption can be O(log n) (n is the number of chunks in a code section), which means a processor may need accessing off-chip memory log n times to validate an address, and at the meantime, the processor pipeline must be stalled in order to wait for the result of the validation. Apparently, the overhead of this solution is too high for a modern processor.

Proposed Mechanism.

This subsection provides a more practical and efficient solution to the intended instruction validation problem in detail.

Recently Validated Address Buffer.

A proposed hardware implementation of RVAB is depicted in Figure 4. The buffer storage is divided into M sets and N lines. A branch target address to be validated is evaluated with a hash function to determine which set it belongs to. Each set contains N validated addresses or invalid empty entries. The address to be validated is compared with these addresses in parallel to quickly check whether the branch target hits the RVAB or not. For a practical implementation, a pseudo-LRU algorithm is used as the replacement strategy for the addresses within a set. Apparently, the hardware cost of RVAB mainly depends on its storage size. We will evaluate the choices of M and N in the experimental evaluation section.

Validation of Branch Target Address.

Theoretically, to ensure only intended instructions are executed, the addresses of all instructions that are going to be executed should be compared with valid instruction addresses. However, if we assume that the program starts from a valid instruction address, then we only need to validate the branch targets of control transfer instruc-tions, as a CISC processor always decodes out instructions one by one sequentially. As a further optimization measure, if the W⊕X protection mechanism is present, we can restrict the validations to indirect control transfer instructions. This is based on the fact that the branch target of a direct control transfer instruction is written into the code section which cannot be modified when W⊕X protection mechanism is applied.

Representation of Valid Instruction Addresses.

The solution in Figure 3 requires logn search times for validating an address that does not hit RVAB, which makes the searching very inefficient. Another way of representing instruction addresses is using one bit to indicate whether an address is the start of a valid instruction, Figure 5 depicts this idea. In Figure 5, suppose the instruction address validation data are stored beginning from 0x8a730 in memory, and the first bit represents the instruction address 0x16b00. If we want to know whether address 0x16b16 is a valid instruction address or not, then we can check the 7th bit of the byte at address 0x8a732 ((0x16b16 -0x16b00)/8 + 0x8a730). Compared with the solution in Figure 3, this way of representing instruc-tion addresses may consume more memory space (1/8 of the total code binary size), but greatly reduces instruction address validation time.

Code Section Range Lookup Table.

If the address representation in Figure 5 is used, then the code section range list acts more like a lookup table. The function of this code section range lookup table (CSRLT) is described in Figure 6. A CSRLT entry contains three items: the start and the end address of a code section and a memory pointer which points to the memory offset of the instruction address validation data of this code section. A full CSRLT is stored on off-chip memory and managed by OS. Like memory page TLB, some of the recently used entries in CSRLT are cached in an on-chip buffer (denoted by CSRLTB) Integration with Processor Pipeline. Now we explain how to integrate our proposed mechanism with an out-of-order processor pipeline, which is illustrated in Figure 7. As there is no need to validate every fetched instruction's address except for branch target, the validation process is better moved from instruction fetch stage to commit stage. There are two reasons behind this: firstly, the real branch target of a control transfer instruction can only be determined after the EX stage; secondly, some of the control instructions in EX stage may be aborted due to failed speculation and commit stage is where precise exceptions are usually carried out in out-of-order processors. However, validating the branch target address when the instruction is just about to commit will stall the processor pipeline for each validation even if the address hits RVAB. Thus, a better solution is carrying out the validation when the control instructions are at the front of the ROB committing queue but have not reached the head yet, and using one bit to indicate the branch target is valid or not.

Further Protection Measures

Statistical results in [START_REF] Kayaalp | Branch regulation: Lowoverhead protection from code reuse attacks[END_REF] shows that limiting the dispatcher gadgets to intended instructions greatly reduces the number of potential dispatcher candidates. However, the remaining dispatcher candidates can still be expored for carrying out JOP attacks.

As a result, we propose using control flow locking (CFL) as the complementary technique to our mechanism. CFL was proposed by Bletsch et al. in [START_REF] Bletsch | Mitigating code-reuse attacks with control-flow locking[END_REF].

The idea of CFL is illustrated in Figure 8. This code snippet is from libssl.a. The actual destination of indirect jump in address 0x451 is address 0x4f0. In [START_REF] Bletsch | Mitigating code-reuse attacks with control-flow locking[END_REF], to implement CFL, a small snippet of lock code is inserted before each indirect control flow transfer. This code asserts the lock by simply changing a certain lock value in memory, and each valid destination for that control transfer contains the corresponding unlock code, which will de-assert the lock if and only if the current lock value is deemed "valid". In Figure 8, variable k is the control flow key, and value 1 means locked while 0 means unlocked. As this paper focuses on hardware supported techniques to mitigate JOP attacks, we propose using hardware to efficiently implement a weaker version of CFL. First, for each committed indirect jump, the processor needs to record that the processor is in a jump locking state. Second, we can devise a new instruction or just add a prefix to current instructions to denote an indirect jump destination. The role of the new instruction or prefix is to unlock the jump locking state, and this unlocking instruction must be committed just after an indirect jump instruction. Apparently, this mechanism is not hard to implement in hardware. For the hardware CFL, the compiler is responsible for correctly inserting indirect jump destination instruction or prefix when translating high level language source code into machine binary code. A difference to software CFL is that we omit the lock value. We argue that implementing lock value will introduce much more hardware and software cost. With the elimination of unintended instructions and the support of hardware CFL, it is already extremely hard to find out enough gadgets to carry a JOP attack.

Performance Evaluation

For evaluating the performance of our techniques, we used the gem5 [START_REF] Binkert | The gem5 simulator[END_REF] simulator to simulate a 4-core x86 CMP. All our experiments were carried out on a high-end desktop computer which has a 3.4 GHz Core i7-4770 CPU with 16GB memory, and the operating system is CentOS 6.4 x86-64. We selected 21 benchmarks from the SPEC CPU2006 [START_REF] Henning | Spec cpu2006 benchmark descriptions[END_REF] benchmark suit and used test input data set for our experiments. These benchmarks were compiled using CentOS's native GCC compiler (version 4.4.7) with -O3 optimizations. For each benchmark, we ran the simulation for 10 billion instructions or until its completion. First, we will evaluate the configurations of RVAB. In the work of this paper, we used 4 entries for each set, and pseudo-LRU for replacement strategy. For the hash function, we simply used lower part of the address as set index. Now we only need to investigate how many sets will be enough for a high RVAB hit probability. Figure 9 illustrates the RVAB hit probability when all control instructions were considered, and Figure 10 illustrates the result when only indirect control instructions were validated. It can be observed that for the same number of set and the same benchmark, the hit probability of Figure 10 is higher than that of Figure 9. An important observation is that when the number of set reaches 128, the hit probability does not change very much, especially for 256 sets and 512 sets. For the benchmarks in Figure 9, the average hit probabilities of 128 sets, 256 sets and 512 sets are 94.68%, 97.35% and 98.84%; and for the benchmarks in Figure 10, the average hit probabilities of 128 sets, 256 sets and 512 sets are 99.11%, 99.61% and 99.70%. Based on this observation, we selected 128 as the set number for the following experiments, and the total number of RVAB entries is 128x4 = 512. As we can see, the hardware cost of RVAB is very small.

We evaluated three configurations for performance impact evaluation. The first configuration is validating all control instructions and using branch predictor as lookup backup (denoted as BP & AC); the second is only validating indirect control instructions and using BP as lookup backup (denoted as BP & IC); the third configuration is only validating indirect control instructions but without using BP as backup. Figure 11a shows the IPC results of the baseline and the three configurations. Here we count x86 micro-ops as instruction counts. To get a clearer view, Figure 11b-11d shows relative performance slowdown of these three configurations. From Figure 11a, we can see that the performance impacts of our proposed methodology are very small for all three configurations. For the BP&AC configuration, the average performance slowdown is 2.492%, the highest performance slowdown is 12.623% (omnetpp), the smallest is -0.039%(bzip2, which means IPC gets a little increase), and there are 11 benchmarks whose performance slowdowns are below 1%. As we expect, the BP&IC configuration gets the best performance result. Its performance slowdown is between -0.093% and 2.993%, and is 0.284% on average. Only two benchmarks' slowdowns exceed 1%. Without BP as backup, the performance result of the IC configuration is a little worse than the BP&IC configuration, but better than the BP&AC configuration. Its slowdown is between -0.043% and 5.247%, and is 0.616% on average. Since the W⊕X mechanism is widely used in modern systems, only validating indirect control instructions is safe enough. The experimental data in Figure 11 indicate that this approach has very little impact on program performance. Even without the help of BP, the highest performance slowdown of IC configuration is only 5.247%, and only three benchmarks have slowdowns above 1%.

Concluding Remarks

In vious work addressed it by an effective hardware approach. We addressed the second problem by using a hardware version of CFL. We also demonstrated that our approach has a very modest cost on both hardware and software. For the BP&IC configuration, the performance loss is -0.093% ~2.993%.

Fig. 1 .

 1 Fig. 1. Example unintended instruction sequence from libc.

Fig. 2 .

 2 Fig. 2. Process of instruction fetch and instruction address validation.

Fig. 3 .

 3 Fig. 3. A preliminary solution for instruction address validation.

Fig. 4 .

 4 Fig. 4. The structure of recently validated address buffer.

Fig. 5 .

 5 Fig. 5. Using one bit to indicate the validity of instruction address.

Fig. 6 .

 6 Fig. 6. The function of code section range lookup table.

Fig. 7 .

 7 Fig. 7. The integration with an out-of-order pipeline.

Fig. 8 .

 8 Fig. 8. An illustrative example of CFL.

Fig. 9 .

 9 Fig. 9. RVAB hit probability for validations of all control instructions.

Fig. 10 .

 10 Fig. 10. RVAB hit probability for validations of indirect control instructions.

Fig. 11 .

 11 Fig. 11. a. Throughput comparison (IPC) of baseline and three different configurations.

Fig. 11 .

 11 Fig. 11. b. Relative performance slowdown of BP&AC configuration.

Fig. 11 .

 11 Fig. 11. d. Relative performance slowdown of IC configuration.

  this paper, we proposed hardware supported techniques to mitigate CRAs on CISC architectures. We addressed the CRA problem by two protection mechanisms: (1) preventing executions of unintended instructions; (2) preventing unintended control flow transfers. The work in this paper mainly focuses on the first problem, as no pre-

			2.30
	Performance	Slowdown(%)	0.30 0.80 1.30 1.80	0.504	0.004	0.070	0.068 0.114 0.078 0.118 0.023 0.083 0.133	0.109	1.341	2.993 0.284
			-0.20	-0.006	-0.001	-0.001 -0.005	-0.003	-0.003	-0.017	-0.093
		Performance Slowdown(%)	-0.20 0.30 0.80 1.30 1.80 2.30	0.023 1.001 -0.001 0.003	0.001 -0.008 0.020 0.436 0.091 0.260 0.406 0.313 -0.002 0.108 0.386 0.009 0.019 -0.015 3.565 -0.043 5.247 0.616

Acknowledgements

This work is supported in part by the Natural Science Foundation of China under Grant No. 61170050, National Science and Technology Major Project of China (2012ZX01039-004). The authors would also like to thank anonymous reviewers who have helped us to improve the quality of this paper.