Ping Chen
email: chenping@nju.edu.cn

Yi Fang
email: fangyi@nju.edu.cn

Bing Mao
email: maobing@nju.edu.cn

Li Xie
email: xieli@nju.edu.cn

JITDefender: A Defense Against JIT Spraying Attacks

JIT spraying is a new code-reuse technique to attack virtual machines based on JIT (Just-in-time) compilation. It has proven to be capable of circumventing the defenses such as data execution prevention (DEP) and address space layout randomization(ASLR), which are effective for preventing the traditional code injection attacks. In this paper, we describe JITDefender, an enhancement of standard JIT-based VMs, which can prevent the attacker from executing arbitrary JIT compiled code on the VM. Thereby JITDefender can block JIT spraying attacks. We prove the effectiveness of JITDefender by demonstrating that it can successfully prevent existing JIT spraying exploits. JITDefender reports no false positives when run over benign actionscript/javascript programs. In addition, we show that the performance overhead of JITDefender is low.

Introduction

In recent years, attackers have resorted to code-reuse techniques instead of injecting their own malicious code. Typical techniques are 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], BCR [START_REF] Caballero | Binary code extraction and interface identification for security applications[END_REF] and Inspector [START_REF] Kolbitsch | Inspector gadget: Automated extraction of proprietary gadgets from malware binaries[END_REF]. Different code-reuse attacks launch the attack based on different codebases, including the application, shared libraries or even the kernel. However, all the techniques need to find useful instruction sequence in the codebase, and the task is tedious and costly in practice.

Recently, a new code-reuse attack named JIT (Just-In-Time) spraying was proposed by Blazakis [START_REF] Blazakis | Interpreter exploitation[END_REF]. It reuses JIT-compiled code on the Flash VM's heap in accordance with the attacker's wish to construct the attack. Later, Sintsov published several realworld JIT spraying attacks on Flash VM [START_REF] Sintsov | Writing JIT-spray shellcode for fun and profit[END_REF] and further proposed advanced shellcode which leverages the code on Safari's Javascript engine [START_REF] Sintsov | JIT-spray attacks & advanced shellcode[END_REF]. JIT spraying can circumvent the techniques such as data execution prevention (DEP) [START_REF]The Pax project[END_REF] and address space layout randomization (ASLR) [START_REF]The Pax project[END_REF][START_REF] Bhatkar | Address obfuscation: an efficient approach to combat a broad range of memory error exploits[END_REF], which are effective for preventing the traditional code injection attacks. The JIT compiler improves the runtime performance of the VM by translating bytecodes into native machine code. A JIT spraying attack is the process that it coerces the JIT compiler to generate native code with the malicious code on the heap of VM, then it exploits the bugs in the browser or its plug-ins to hijack the control and uses the injected malicious code to achieve the attack. JIT spraying attack have become a big threat to Web Security, because the browser often enables dynamic languages (e.g., actionscript and javascript). JIT spraying attacks have two advantages compared with other code-reuse techniques: First, the malicious code is generated by the JIT compiler, so the attacker needs not to piece up useful code snippets for constructing the attack in the codebase. Second, malicious code is generated on the heap. This can be combined with heap spraying techniques [START_REF]Wikipedia: Heap spraying[END_REF] to increase the probability of the attack.

In this paper, we describe JITDefender, a defense of JIT spraying attacks, which enforces the JIT-code execution control policy for the VM. To defend against JIT spraying attacks, JITDefender changes the VM in the following way: the VM's heap is generally set non-executable so that W ⊕ X protection applies. If a specific part of JIT-code has to be executed on the VM based on the definition of the program, the heap is set to be executable, before the code is executed, and immediately set to non-executable afterwards. This paper makes the following contributions:

-We propose JITDefender, an effective technique for defending JIT spraying attacks by controlling the execution of the JIT-code. This techniques distinguishes the benign usage of JIT-code from malicious usage of the attacker. -We implement and evaluate JITDefender on several commonly used VMs that use JIT compilation (Tamarin flash VM, the V8 javascript engine and Safari's javascript engine). We show that JITDefender can defend against JIT spraying attacks on VMs based on JIT compilation, although the performance overhead of JITDefender is less than 1%. -We also show that JIT spraying attacks are not only available on flash/javascript

VMs, but also available on other VMs based on a JIT compiler, such as QEMU.

Our technique is effective for defending against JIT spraying on arbitrary VMs based on JIT compilation.

2 Background: JIT Spraying JIT Spraying is a code-reuse technique that uses the code generated by the VM based on JIT compilation to launch the attack. By writing the objects using dynamic languages (e.g., javascript, actionscript), the attacker coerces the JIT compiler to generate the malicious code on the heap of VM, and hijacks the control flow to the malicious code snippet. However, different from the existing code reuse techniques, the malicious code does not need to be found within an existing codebase (e.g., libraries, kernel), instead, the attacker predictably defines the objects which are intended to be compiled into the malicious code on the heap of VM, and uses the heap spraying technique to populate the heap with a large number of objects containing the malicious code. Therefore, when the attacker drives the control flow to arbitrary addresses on the heap, with high probability the jump will land inside one of malicious code snippets. Figure 1 illustrates the JIT spraying attack on Flash VM. First, the attacker defines the actionscript object (ret in Figure 1) which contains many uniform statements (XOR in Figure 1) with dedicated constructed integers (0x3c909090 in Figure 1) in the source code. Then the JIT compiler will dynamically translate the source code and generate the native code. In this example, the flash VM will translate the XOR as 0x35 and the integer as the original value in the native code. If the attacker carefully constructs the integer value, the native code may be transferred into the malicious code with one byte offset. Suppose the attacker lays out many such objects on the heap, and the attacker can turn the control flow to the malicious snippet (e.g., through a buffer overflow attack), finally this results in the JIT spraying attack. The JIT spraying example illustrated in Figure 1 shows that the code translated by the JIT compiler can be leveraged to launch the JIT Spraying attack. In fact, many other VMs based on a JIT compiler have the same problem. Furthermore, browsers such as IE8 and Chrome are particularly vulnerable to JIT spraying because actionscript/javascript programs embedded in a web page greatly simplify such attacks.

Overview of JITDefender

VMs based on JIT compilation (e.g., Flash VM, Javascript VM) often dynamically translate the source code into the native code on the heap. They necessarily have to mark the page containing the JIT-code as executable and reuse the code repeatedly without re-compiling or interpreting in order to boost the performance. This mechanism implicitly turns the W ⊕ X protection off and gives the attacker the opportunity to launch JIT spraying attacks which were illustrated in Section 2. In this paper, we describe the idea of JITDefender, a method to prevent the compiled code from being executed by the attacker. The main idea is to re-enforce W ⊕ X protection within the VM. More precisely, we generally mark the native code pages as non-executable. When the VM executes JIT-code, we change the corresponding code pages to executable, after executing the code, the code pages are reset to non-executable again.

When designing JITDefender, we need to identify two points in the the code base of the JIT execution: (1) the code compilation point, i.e., the point when the JIT compiler generates the native code, and (2) the code execution point, the point when the VM executes the native code. The workflow of JITDefender is that we mark the code pages as non-executable at the first point. Shortly before the second point we mark the pages as executable, and shortly after we mark the pages as non-executable again. This mechanism can be applied to arbitrary VMs based on JIT compiler. Under this protection of JITDefender, if the attacker hijacks the control flow to the code snippet on the heap for JIT spraying attack the access will be blocked because the VM keeps the code pages non-executable. In fact, JITDefender provides different views of the compiled code for the VM and the attacker with the native code execution control policy.

Design and Implementation

In this section, we firstly take the Flash VM as an example to illustrate our method. We identify code parts in the VM that define code compilation and code execution points. Then we demonstrate that our method can be applied to Javascript VM.

Introduction of the Flash Engine

The source code of flash is written in the actionscript language. Through the different actionscript compilers, the source code is translated into the actionscript byte code (ABC) or the ShockWave File (SWF). The code can be JIT compiled or interpreted on the flash engine. Flash engine handles the ABC or SWF file in the following steps as shown in Figure 2: first it passes through the ABC or SWF files, translates them into the objects which are stored in the object pool. Then it steps into the compiling phase or interpreting phase. In this paper, we only focus on the compiling phase where the JIT compiler fetches the object from the pool, then compiles it into the native code. This is the code compilation point defined above. JIT compiling can be divided into MIR code generation and Machine Code (MD) generation. The native code is stored in the newly allocated heap memory of flash VM. Third, the flash VM provides the loop monitoring whether there is the compiled code on the heap. If so, it will execute the native code. This is the code execution point defined above. In order to prevent JIT spraying attack, we manipulate the Native Code Execution Controller on VMs, which is between the MD code generation and Runtime code execution. In the following subsection, we will illustrate the mechanisms implemented in Flash/Javascript VMs in details.

Adapting the Flash Engine

In Flash Engine Tamarin, when an ABC or SWF file is loaded, the JIT compiler will translate the source code into native code at the unit of a function. More specifically, Tamarin uses the class MethodInfo to store the information of the functions that can be executed by the VM, including user-defined functions, native functions and so on.

Another key class named CodeMgr is used to manage memory for compiled code, including the code itself (in a nanojit::CodeAlloc), and any data with code lifetime (in a nanojit::Allocator), such as debugging info and inline caches. In order to set the attributes of the code pages, we should get the the compiled code information at the unit of function. Therefore, we add the variable CodeMgr * mgr in the MethodInfo class. It will provide us the convenience for setting attributes of the code pages, because we can get the information of the function including the native code generated by this function. We now give more details how to set the page attributes.

First, we need to get related information at the code compilation point when native code has been generated. We find that, after Tamarin generates the compiled code for one function, it will store the compiled code information in the codeMgr which is the member variable of the class PoolObject, and PoolObject is a container for the pool of resources decoded from an ABC file. Therefore, we will transfer the compiled code information into the new variable mgr we defined in MethodInfo. Then we extract the start and end address of the compiled code memory, and invoke the function named VMPI setPageProtection to set the related pages as non-executable.

Second, we need to find the code execution point. As mentioned in Section 3, we should set the related code pages as executable before executing the compiled code, and after executing the compiled code, we set the compiled code pages as nonexecutable again. In the Tamarin flash engine, the function coerceEnter is used to execute the compiled code, at the end of this function, the specific handler function is invoked by endCoerce(argc, ap, ms). As such, we leverage the function VMPI setPageProtection to set the related pages as executable, and after executing the function, we use the same function to set the related pages as non-executable. Note that we calculate the related pages based on the recorded information of mgr in the MethodInfo.

The method mentioned above can successfully protect the compiled code on the heap of the VM. Because the compiled code can be only executed by the VM itself, but can not be executed by the attacker.

Javascript Engine

Sintsov [START_REF] Sintsov | JIT-spray attacks & advanced shellcode[END_REF] shows that JIT Spraying can be also mounted on the Javascript Engine in Safari [START_REF]The Webkit open source project[END_REF]. Similar to the flash engine, the attacker can construct the Javascript object using the XOR operation with the specific integer operands. Then the Javascript Engine will compile the Javascript objects into the native code which contains the malicious code. We find that the same problem occurs in the V8 Javascript engine -the javascript engine of Chrome [START_REF]V8 javascript engine[END_REF]. We could leverage a known buffer overflow [1] to launch a JIT spraying attack. In this section, we demonstrate that JITDefender can be implemented on both Javascript engines.

V8 Javascript Engine As we mentioned in Section 3, we need to identify the code compilation and the code execution point. The V8 Javascript engine provides two API function for compilation and execution respectively. The Compile function is used to compile the Javascript program into the native code on the heap, and the Run function is used to execute the compiled native code.

In the compilation phase, the V8 Javascript engine parses the Javascript files and divides the code into two parts, one is the specific function such as the eval, the global function, and other functions are regarded as the shared function. Then it compiles the Javascript code into the native code according to the function categories. And the native code is stored as SharedFunctionInfo at the unit of the function. SharedFunctionInfo is the child class of HeapObject, which maintains the information of the Javascript objects.

In the execution phase, V8 gets the compiled code by using the Code::GetCode method, and finds the entry to the code by the Code::entry method, then it jumps to the code entry to execute the code on the heap using Execution::Call. Note that the class Code is the child class of HeapObject, it contains the native code generated at the compilation point. Similar with the flash engine, the compiled code is laid out on the heap and its page is marked as executable, which is independent of whether the code is executed by the Javascript engine or not.

We applied our code control policy to the V8 javascript engine. First, at the end of Compiler::Compile, we use the Windows API function VirtualProtect to set the compiled code pages as non-executable. Then before the Execution::Call, we use VirtualProtect to set the code pages as executable, and after executing the compiled code, we set the code pages as non-executable again.

Safari's Javascript Engine Similar to the V8 Javascript Engine, at the code compilation point, Safari's Javascript Engine compiles the Javascript code into the native code according to the function definition. The native code is saved in the structure of JITcode. At the code execution point, Safari Javascript Engine will query the native code base, invoke the entry to the current executed function and then execute it. We modify Safari's Javascript Engine (JavascriptCore) at these two points: First, Safari's Javascript Engine gets the JITed code by the method JIT::compile in memory space in the form of JITcode. Then we set the code pages as non-executable. Second, the Javascript Engine executes the JITed code by using the method JITStubCall::call. Before we invoke this function to execute the JIT-code, we first set the code pages as executable. After we executed the code, we reset the code page as no-executable again.

In this section, we describe the experimental evaluation of our JITDefender prototype. First, we test JITDefender's ability to dynamically defend the JIT spraying attack. Second, we measure the performance overhead of JITDefender. The evaluation is performed on an Intel Pentium Dual E2180 2.00GHz machine with 2GB memory and Windows 7. Tested programs are compiled by Microsoft Visual Studio 2008.

Effectiveness

Since JIT spraying is a new attack, there are little attack samples published. Therefore we used existing JIT spraying attacks published by Sintsov for Tamarin flash engine and Safari's Javascript engine and wrote samples for the V8 javascript engine by ourselves. More specifically, we chose two JIT spraying attack samples written by Sintsov to evaluate Tamarin flash engine: "SAP-Logon7-System" [START_REF] Sintsov | SAP GUI 7.10 webviewer3d Activex -JIT-spray exploit[END_REF] and "QuikSoft-STAGE0" [START_REF] Sintsov | Oracle document capture (easymail objects emsmtp.dll 6.0.1) activex control bof -JIT-spray exploit[END_REF].

The two JIT spraying attacks leverage the buffer overflow vulnerability in SAPGUI 7.10 ActiveX and Oracle Document Capture (EasyMail Objects EMSMTP.DLL 6.0.1) ActiveX Control respectively, and can successfully launch attacks on IE8. Note the two original JIT spraying attacks leverage Flash Player 10's flash engine [START_REF] Sintsov | Writing JIT-spray shellcode for fun and profit[END_REF]. In our experiment, we use the Tamarin Flash engine instead. For Safari, we chose the JIT Spraying attack "Safari parent close sintsov" published by Sintsov [START_REF] Sintsov | JIT spraying attack on safari[END_REF]. It exploits the vulnerabilities in Safari 4.0.5 parent.close() to launch attacks. In addition, in order to test the effectiveness of our tool on the V8 Javascript engine, we wrote one JIT spraying code by leveraging the buffer overflow "SaveAs" in Chrome [1]. We named the attack as "SaveAs-JITSpray". With all the attacks mentioned above, we tested the effectiveness of JITDefender for detecting the JIT spraying attacks, including Tamarin, V8, and Safari's javascript engine. Experimental results in Table 1 show that JITDefender can successfully defend JIT spraying in VMs based on JIT compilation. We also tested JIT-Defender on benign code, namely the performance benchmarks embedded in the JIT VMs. The actionscript/javascript programs are listed in Table 2. Overall, we found no false positives.

Performance Overhead

We also measured the performance overhead of JITDefender. Because JITDefender modifies the JIT-code page attributes of the VM at runtime, it will bring some overhead to the VMs. In this section, we chose the three VMs based on JIT compilation to evaluate the performance overhead of JITDefender, including Tamarin Flash Engine, Safari's Javascript Engine and V8 Javascript Engine. Table 2 shows the performance overhead of JITDefender when it is applied to the VMs when executing the actionscript/javascript programs. For each VM, we run the benchmark of it, and compare the time costs when the tested program running on the original VMs and the modified VMs. By comparison, we can see that JITDefender has less than 1% costs on VMs. Generally speaking, the performance overhead is proportional to the number of function chunks in the program. This is because the more function chunks of the program exist, the more frequently JIT VMs will transfer the JIT objects into different functions' native code and execute these codes individually. Since we modify the code pages' attributes, the more function chunks of the programs there are, the more performance overhead will be introduced to program's execution. Take the experimental results in Table 2 for instance, the test case "Heapsort.as" uses recursion techniques to sort arrays. It frequently invokes the small function NumHeapSort, which performs a heap sort on an array. Therefore, when the Tamarin flash engine compiles "Heapsort.as" into native code, the code pages will be marked as "non-executable" or "executable" alternatively. This is the reason why the performance overhead of executing "Heapsort.as" under JITDefender is 3.5%, which is more than the average.

Discussion

JITDefender on Other VMs

QEMU [START_REF] Qemu | [END_REF] is the commonly used CPU-emulator, which leverages the JIT techniques.

We discovered that the programs running in QEMU will cast their code on the heap and mark it as executable. We note that JIT spraying attacks may be constructed on it too. To perform such an attack, we need to install a VM on QEMU. Within the VM, we need to construct a malicious program, which contains the shellcode. Then we fork several processes for running the program that keep on spraying malicious code on the heap of QEMU. In order to construct the attack, we need to leverage one of the bugs in QEMU and drive control to the malicious code [START_REF] Wang | Integer overflow on QEMU[END_REF]. Since QEMU is used as CPU-emulator in KVM [2], this effectively means that the approach can be leveraged to construct an attack on Cloud Computing. So JIT spraying may threaten the security of the Clouds. Similarly with to flash and javascript engine, it should be possible to implement JITDefender on QEMU. In fact, we believe JITDefender can be applied to arbitrary VMs based on a JIT compiler to defend against JIT Spraying exploits.

Circumventing JITDefender

The method proposed in this paper addresses the problem that most Just-In-Time compilers leave a large window of opportunity for exploiting code "sprayed" into the compiled code. We reduce the window to the minimum time so that only the VM based on JIT compilation can set the compiled code as executable at page granularity. People may argue that is it possible that the attacker exploits the vulnerability within the window which spans from VM setting the page as executable to VM executing the code on the page. We think this potential JIT spraying attack is feasible in theory but we did not find it in practice. The potential JIT spraying attack is that the malicious code is on the same page with the code that is executing on VM when the attacker exploits. In that case, JITDefender will keep the page as executable, as such, JIT spraying will make JIT-Defender ineffective. Although we did not find such attacks till now, we consider the attack is possible. For example, the attacker introduces the delay method (e.g., loop) in certain function to keep the code executing and the page containing the malicious code. Even worse, if the program is asynchronous, for example, it uses multi-threaded methods to load multiple objects on the heap, and keep all the pages executable by the delay method, it will give a big opportunity for the attacker to circumvent JITDefender. Although nobody has proposed the attack till now, in theory, it will be a threat to JIT-Defender. To counter the attack, we consider to add some optimization to the VM, for example, we can pre-calculate the XOR operation, and get the result directly without translating its operands on the heap.

7 Related Work

Heap Spraying Defenses

Heap spraying [START_REF]Wikipedia: Heap spraying[END_REF] is a technique that will increase the probability to land on the desired memory address. The act of spraying simplifies the JIT spraying attack and increases its likelihood of success. There are several defenses specifically designed against heapspraying attacks [START_REF] Egele | Defending browsers against drive-by downloads: Mitigating heap-spraying code injection attacks[END_REF][START_REF] Francesco | Bubble: A javascript engine level countermeasure against heap-spraying attacks[END_REF][START_REF] Ratanaworabhan | Nozzle: A defense against heap-spraying code injection attacks[END_REF]. Nozzle [START_REF] Ratanaworabhan | Nozzle: A defense against heap-spraying code injection attacks[END_REF] is the countermeasure specifically designed against heap-spraying attacks by the analysis of the contents of any object allocated by the Web browser. Similarly, Egele et al. [START_REF] Egele | Defending browsers against drive-by downloads: Mitigating heap-spraying code injection attacks[END_REF] propose an emulation method to detect heap spraying attacks with drive-by downloads. Based on libemu [START_REF]x86 shellcode detection and emulation[END_REF], it emulates the code download and checks whether there is malicious code. Bubble [START_REF] Francesco | Bubble: A javascript engine level countermeasure against heap-spraying attacks[END_REF] is the Javascript engine level countermeasure against Heap-spraying attacks. It introduces the diversity of the heap by inserting special interrupting values in strings at random positions when the string is stored in memory and removing them when the string is used by the application. All the existing Heap spraying defenses all rely on the assumption that the malicious code is introduced from the outside (network, keyboard), therefore they may be circumvented by JIT spraying attack.

JIT Spraying Mitigation

Concurrently and independently, Bania [START_REF] Bania | JIT spraying and mitigations[END_REF] proposed a heuristic detection method, based on the assumption that JIT spraying attacks use arithmetic operations. They detect JIT spraying by calculating the number of bad instructions. However, JIT spraying may not use the arithmetic operations to generate the malicious code. Tao et al. [START_REF] Tao | Secure dynamic code generation against spraying[END_REF] propose the code randomization techniques on VMs based on JIT compilation. However, it has 5.9% space and 5% runtime overhead. In addition, they currently implemented the prototype on V8 engine only. Our techniques are quite different compared to theirs. First, we do not assume any particular form of JIT spraying attack (e.g., using XOR). Second, our method can prevent JIT spraying with less performance overhead (less than 1%). Third, our method has been implemented and tested on different VMs, and proved to be easily deployed on other VMs in practice. Most recently, de Groef et al. [START_REF] De Groef | Jitsec: Just-in-time security for code injection attacks[END_REF] proposed a kernel patch JITsec that defeates JIT spraying based on testing certain restrictions when invoking a system call. Different from JITDefender, JITsec can only defeat the malicious code that uses the system call not general code.

Other Defenses

Most recently, Payer [START_REF] Payer | I control your code attack vectors through the eyes of software-based fault isolation[END_REF] summarized the different attack types and defenses. Generally speaking, all the attacks leverage software bugs and maliciously craft the control or non-control objects to achieve malicious behavior. To defeat these attacks, researchers proposed CFI [START_REF] Abadi | Control-flow integrity[END_REF] and DFI [START_REF] Castro | Securing software by enforcing data-flow integrity[END_REF] that protect against sensitive objects. XFI [START_REF] Erlingsson | XFI: Software guards for system address spaces[END_REF], a kernel module, leverages static analysis for the guard and checks the jump's target, in addition, it uses two stacks to guarantee the return address. There are intrinsic differences between XFI and JITDefender. First, JITDefender prevents the code snippet in the function from being reused from outside, while XFI controls the function callsites and prevents it being maliciously invoked. Second, JITDefender prevents the JIT spraying attack, while XFI prevents the code injection attacks.

Conclusions

In this paper, we present the design, implementation, and evaluation of JITDefender, a tool for defeating JIT spraying attacks. JITDefender applies code execution control on the VMs, and to the best of our knowledge, it is the comprehensive defense for JIT spraying. The evaluation of JITDefender shows that it has no false positives, and the performance overhead is low.

Fig. 2 :

 2 Fig. 2: Tamarin Flash Engine

Table 1 :

 1 JIT Spraying Attacks Tested on JITDefender

	VMs	JIT Spraying Attacks	LOC(K)	Description	JITDefender
	Tamarin	SAP-Logon7-System [24] QuikSoft-STAGE0 [23]	3K 3K	SaveViewToSessionFi ActiveX Buffer Overflow SubmitToExpress ActiveX Buffer Overflow
	V8	SaveAs-JITSpray	3K	"SaveAs" Buffer Overflow in Chrome
	Safari's JS Engine Safari parent close sintsov [22]	3K	Safari 4.0.5 parent.close() (memory corruption)

Table 2 :

 2 Performance Overhead of the JIT VMs under JITDefender

	VMs	Benchmarks LOC(K) Original VM JITDefender Performance Overhead
		SOR.as	3	72.844s	72.999s	0.2%
		Heapsort.as	3	9.980s	10.325s	3.5%
		SparseMatmult.as	4	0.958s	0.983s	2.6%
		FFT.as	5	10.334s	10.552s	2.1%
		Series.as	6	4.661s	4.763s	2.2%
	Tamarin	LUFact.as	12	27.827s	27.989s	0.6%
		Moldyn.as	14	6.101s	6.276s	2.9%
		Crypt.as	15	0.314s	0.322s	2.5%
		RayTracer.as	22	1.566s	1.573s	0.4%
		Euler.as	81	0.246s	0.249s	1.2%
		Average		13.483s	13.603s	0.9%
		crypto.js	48	5.189s	5.196s	0.1%
		richards.js	16	2.107s	2.112s	0.2%
		deltablue.js	26	2.100s	2.113s	0.6%
	V8	raytrace.js earley-boyer.js	28 195	2.129s 5.198s	2.134s 5.213s	0.2% 0.3%
		regexp.js	105	4.274s	4.287s	0.3%
		splay.js	11	3.575s	3.629s	1.5%
		Average		3.510s	3.526s	0.5%
		crypto.js	48	5.336s	5.419s	1.6%
		richards.js	16	2.277s	2.288	0.5%
		deltablue.js	26	2.246s	2.301s	2.4%
	Safari's JS Engine	raytrace.js earley-boyer.js	28 195	4.309s 12.496s	4.339s 12.792s	0.7% 2.4%
		regexp.js	105	15.944s	15.959s	0.1%
		splay.js	11	4.911s	4.918s	0.1%
		Average		6.788s	6.859s	0.1%

Acknowledgements

We thank our shepherd Felix Freiling for his help on the final paper. We also thank the anonymous reviewers for their constructive and helpful feedbacks and suggestions. This work was supported in part by grants from the Chinese National Natural Science Foundation (60773171, 61073027, 90818022, and 60721002), the Chinese National 863 High-Tech Program (2007AA01Z448), and the Chinese 973 Major State Basic Program(2009CB320705).


Alessandro Armando

Roberto Carbone

Luca Compagna

Jorge Cuellar

Giancarlo Pellegrino

Alessandro Sorniotti

From Multiple Credentials to Browser-based Single Sign-On: Are We More Secure?

Browser-based Single Sign-On (SSO) is replacing conventional solutions based on multiple, domain-specific credentials by offering an improved user experience: clients log on to their company system once and are then able to access all services offered by the company's partners. By focusing on the emerging SAML standard, in this paper we show that the prototypical browser-based SSO use case suffers from an authentication flaw that allows a malicious service provider to hijack a client authentication attempt and force the latter to access a resource without its consent or intention. This may have serious consequences, as evidenced by a Cross-Site Scripting attack that we have identified in the SAML-based SSO for Google Apps: the attack allowed a malicious web server to impersonate a user on any Google application. We also describe solutions that can be used to mitigate and even solve the problem.

Introduction

To provide access to restricted services, web applications assign digital credentials to registered users and require users to prove possessions of these credentials to receive access to protected resources. As web applications become more and more widespread, users must handle an increasing number of authentication credentials to establish security contexts with web applications. This is not only an annoying aspect of the current state of affairs, but has serious implications on the security of these systems as users tend to use weak passwords and/or to reuse the same password on different web applications.

Browser-based SSO solutions aim at improving this state of affairs by allowing users to log in once and by giving them subsequent access to multiple web applications. At the core of a browser-based SSO solution lies a browser-based authentication protocol. Three roles take part in the protocol: a client (C), an identity provider (IdP) and a service provider (SP). The objective of C, typically a web browser guided by a user, is to get access to a service or a resource provided by SP. IdP authenticates C and issues corresponding authentication assertions. Finally, SP uses the assertions generated by IdP to decide on C's entitlement to the requested resource.

A number of solutions for browser-based SSO have been put forward, e.g. Microsoft R Passport [START_REF]Windows Live ID[END_REF], the Liberty Alliance project [START_REF]Identity Federation. Liberty Alliance Project[END_REF], the Shibboleth Initiative [START_REF]Shibboleth Project[END_REF], and OpenId [START_REF]OpenID Specifications[END_REF]. The OASIS Security Assertion Markup Language (SAML) 2.0 Web Browser SSO Profile (SAML SSO, for short) [START_REF]SAML V2.0[END_REF] is an emerging standard in this context: it defines an XML-based format for encoding security assertions as well as a number of protocols and bindings that prescribe how assertions must be exchanged in a variety of applications and/or deployment scenarios. Prominent software companies base their SSO implementations on SAML SSO. For example, Google has developed a SAML-based SSO service for its popular web applications (namely Gmail, Google Calendar, Talk, Docs and Sites), called the SAML-based SSO for Google Apps [START_REF] Google | Web-based SAML-based SSO for Google Apps[END_REF].

The security of SAML SSO critically relies on a number of assumptions on the trustworthiness of the principals involved as well as on the security of the transport protocols used to exchange messages. In this paper we argue that one of the assumptions on the security of the transport layer (i.e., that communication between the client and the service provider must be carried over a unilateral SSL 3.0 or TLS 1.0 connection) can only be met in practice in a way that leaves the protocol vulnerable to an authentication flaw. We discuss how this flaw can be exploited in general as well as on a number of prominent SAML-based SSO solutions, including the SAML-based SSO for Google Apps that is used by over one million business customers. Our findings show that the authentication flaw can be seriously exploited in actual deployments of SAML SSO. For instance, a severe attack could be mounted on the SAML-based SSO for Google Apps in which a malicious web server could impersonate the victim user on any Google application. In the paper we also provide solutions that allow the authentication flaw and its exploitations to be mitigated or even eliminated.

To the best of our knowledge neither the authentication flaw on the SAML SSO nor the vulnerability of the SAML-based SSO for Google Apps reported in this paper are publicly known. We are currently informing US-CERT and the relevant vendors about our findings. In response to our vulnerability report Google has already patched their implementation of their SAML SSO solution.

What about the original question in the title, are we more secure with SAML SSO than with multiple credentials? This question does not have a trivial answer and certainly a positive answer cannot be given as long as there are unaddressed issues such as the vulnerability we present in this paper. In addition, since the security considerations brought forward by this paper do not apply to SAML SSO only, we believe that other browser-based SSO protocols may suffer from similar vulnerabilities. We are currently extending our analysis to other SSO solutions to ascertain this.

Structure of the paper. In the next section we introduce the SAML SSO profile for web-based authentication. In Section 3 we present the authentication flaw on the SAML SSO, and in Section 4 describe how it can be exploited on actual implementations. In Section 5 we provide a number of solutions for the flaw. Last but not least, in Sections 6 and 7 we discuss some of the related work and present conclusions.

2 The SAML 2.0 Web Browser SSO Profile SAML SSO provides a standardized, open, interoperable SSO solution applicable in a multitude of environments and situations, and can therefore be instantiated according to the specific requirements posed by the application scenario. In this paper we focus on one of its most widely used instantiations, the SP-Initiated SSO with Redirect/POST Bindings, whose typical use case is described in [START_REF]SAML V2.0 -Technical Overview[END_REF]. In the remainder of this paper we will refer to this use case as the SAML SSO use case and to the associated protocol as the SAML SSO Protocol. In Figure 1 we capture the most important steps of the SAML SSO Protocol, abstracting away the steps that are irrelevant for our analysis, such as-among others-the IdP discovery phase. In step S1, C asks SP to provide the resource located at URI, say Resource(URI), without having a valid, active logon session (i.e. security context) with SP. SP then initiates the SAML Authentication Protocol by sending to C an HTTP redirect response (status code 302) to IdP, containing an authentication request AuthReq(ID,SP), where ID is a (pseudo-)randomly generated string uniquely identifying the request (steps A1 and A2). A frequent implementation choice is to use the RelayState field to carry the original URI that the client has requested (see [START_REF]SAML V2.0 -Technical Overview[END_REF]).

If C does not have an existing security context with the IdP, then IdP challenges C to provide valid credentials. If the authentication succeeds, the IdP creates the local security context, builds an authentication assertion as the tuple AA = AuthAssert(ID, C, IdP, SP), and places it in a response message Resp = Response(ID, SP, IdP, {AA} K -1

IdP

), where {AA} K -1 IdP is the assertion signed with K -1

IdP , IdP's private key. IdP then places Resp and the value of RelayState received from the SP into an HTML form (indicated as Form(. . .) in Figure 1) and sends the result back to C in an HTTP response (step A3) together with some script that automatically posts the form to the SP (step A4). This completes the SAML Authentication Protocol. SP can then deliver the requested resource, Resource(URI), to C (step S2), and the SAML SSO Protocol completes as well.

Note that the steps at message S1 and S2 admittedly fall outside of the scope of the standard, and their implementation is left free. In this paper we capture steps S1 and S2 as described in the SAML SSO use case; a number of commercial SAML SSO solutions indeed adopt similar approaches to implement those steps.

As pointed out in [START_REF] Armando | Formal Analysis of SAML 2.0 Web Browser Single Sign-On: Breaking the SAML-based Single Sign-On for Google Apps[END_REF] the security of the protocol critically relies on (unstated) assumptions about the trustworthiness of the participants involved and about the transport protocols used to exchange the protocol messages; we shall review these in the next Sections.

Trust and Transport Protocol Assumptions

The above protocols work under the assumption that (i) IdP is not compromised, i.e. it is not under the control of an intruder and it abides by the rules of the protocol and (ii) IdP is trusted by SP to generate authentication assertions about C. Even if they are not explicitly stated in the SAML 2.0 specifications, these are very reasonable assumptions to make and, in fact, both protocols are useless if the IdP is not trusted to generate authentication assertions about C or if there is the doubt that the IdP is compromised. However, we do not assume that all SPs which C may play the protocol with are uncompromised. In other words, unlike [START_REF] Hansen | Using static analysis to validate the SAML single sign-on protocol[END_REF], we want to consider also those situations in which C runs the protocol with compromised SPs in order to determine whether they affect the security of sessions of the protocol played with other uncompromised SPs. This is very important as SPs are usually managed by different organizations that do not always share trust relationships.

The SAML 2.0 specifications repeatedly state the following assumptions of the transport protocols used to carry the protocol messages:

(TP1) Communication between C and SP is carried over a unilateral SSL 3.0 or TLS 1.0 channel (henceforth called SSL), established through the exchange of a valid certificate (from SP to C). (TP2) Communication between C and IdP is carried over a unilateral SSL channel that becomes bilateral once C authenticates itself on IdP. This is established through the exchange of a valid certificate (from IdP to C) and of valid credentials (from C to IdP).

Security Requirements

The SAML specifications do not explicitly state the security properties that the SAML SSO Protocol and the SAML Authentication Protocol are expected to achieve. By comparison with classic web authentication schemes, it is however natural to expect that at the end of the SAML SSO Protocol, the following security property is fulfilled:

(P1) SP and C mutually authenticate and agree on the value URI As pointed out in [START_REF] Lowe | A hierarchy of authentication specifications[END_REF], different definitions of authentication are possible. The notion of authentication we consider in this paper includes recentness, i.e. the fact that the principal being authenticated recently took part in the protocol run so as to exclude replay attacks.

We note that the SAML Authentication Protocol, the building block of the SAML SSO Protocol, is only able to guarantee the property

(P2) SP authenticates C
The converse is not true, i.e., the SAML Authentication Protocol does not provide to C any guarantee on SP's identity; indeed in message A1, SP may instruct IdP to force C to redirect message A4 to an arbitrary location. Even the use of SSL certificates only guarantees that there is no man-in-the-middle in the communications between C and the recipient of message A4.

In the remainder of this paper, we will investigate whether the SAML SSO Protocol, constructed with a building block that only guarantees (P2), is able to fulfill the original property (P1), and we will show that the fulfillment of this property is not automatically guaranteed; in particular depending on the implementation choices, a malicious SP may be able to hijack C's authentication attempt and force the latter to access a resource without its consent or intention.

An Authentication Flaw in the SAML SSO Protocol

An analysis of the SAML specifications reveals that the standard does not specify whether the messages exchanged at steps S1 and A4 must be transported over the same SSL channel or whether two different SSL channels can be used for this purpose. In other words, there is a certain degree of ambiguity on how assumption (TP1) of Section 2 can be interpreted.

The reuse of the SSL channel established at step S1 to also transport the message at step A4 is at first sight the most natural option. However this is difficult to achieve in practice for a number of reasons:

Resuming SSL sessions. The use of a single SSL session for the exchange of different messages cannot be guaranteed as, e.g., the underlying TCP connection might be terminated (e.g. timeout, explicitly by one of the end points), an SSL server could not resume a previously established session, or a client might be using a browser that very frequently renegotiates its SSL session. Software modularity.

Nowadays, software is designed to be increasingly modularized, capitalizing on layering and separation of concerns. This may result in the fact that-within SP implementations-the software module that handles SAML messages has no access to the internal information of the transport module that handles SSL. Thus, the information on whether the client has used a single SSL session or two different ones may not be available. Distributed SPs. The SAML SP may be distributed over multiple machines, for instance, for work-balancing reasons. This results in physically different SSL endpoints, with the inherent impossibility of enforcing a single session for all communications between SP and C.

We have extended the formal model discussed in [START_REF] Armando | Formal Analysis of SAML 2.0 Web Browser Single Sign-On: Breaking the SAML-based Single Sign-On for Google Apps[END_REF] to faithfully capture the SAML SSO use case in which the messages of steps S1 and A4 can be transported over different SSL sessions and fed it to a state-of-the-art modelchecker for security protocols [START_REF] Armando | LTL Model Checking for Security Protocols[END_REF]. (See Section 6 for more details.) The model checker detected the attack depicted in Figure 2, thereby witnessing a violation of property (P1) in the SAML SSO Protocol. The attack involves four principals: a client (c), an honest IdP (idp), an honest SP (sp) and a malicious service provider (i). The attack is carried out as follows: c initiates the protocol by requesting a resource uri i at SP i. Now i, pretending to be c, requests a different resource uri at sp and sp reacts according to the standard by generating an Authentication Request, which is then returned to i. Now i maliciously replies to c by sending an HTTP redirect response to idp containing AuthReq(id, sp) and uri (instead of AuthReq(id i , i), and uri i as the standard would mandate). The remaining steps proceed according to the standard. The attack makes c consume a resource from sp, while c originally asked for a resource from i.

Note that the attack is possible essentially because the client-usually a normal browser with no knowledge of the SAML protocol-has no means of verifying whether the authentication request and the authentication assertion are related to the initial request.

Interestingly enough, standard username/password authentication mechanisms do not suffer from this authentication flaw. To see this, let us assume that C has no active sessions with service providers SP1 and SP2; let us also assume that C's usernames and passwords are different for each SP. Then under no circumstance can SP1 hijack C's authentication attempt and unawarely and automatically force it to consume a protected resource at SP2. From this point of view, the advantage of domain-specific credentials in the control of the user is that the user knows exactly for whom the credentials are intended upon providing them. With SSO, "binding" the views of the user and of the service provider is not so easy.

Note that the attack would be prevented if sp could enforce that the initial request and authentication response are carried over the same secure channel, but we have previously explained why this requirement is very difficult to achieve in practice. Note also that requiring digitally signed authentication requests would not fix the vulnerability; indeed the authentication request is actually generated by the honest service provider, and only blindly forwarded to the client by the attacker; the signature is therefore valid and will be accepted.

Even more interestingly, the attack does not strictly require a malicious service provider in order to be successful. Any malicious web server i would be able, upon a request from c, to mount the attack provided that (i) c is a client of sp and (ii) c has an active authentication context with idp. The attack in Figure 2 can be exploited in a number of ways: Delivery of an unrequested resource.

The most trivial exploitation of the flaw consists in the attacker forcing the client to receive a different protected resource from the initially requested one. The same exploitation may also be mounted if a malicious web server redirects the browser to a legitimate SP before the SAML SSO Protocol starts. However this attack can be prevented by using well-known browser-side plugins that restrict HTTP redirections (e.g., the NoRedirect addon for Firefox). By allowing only IdP-to-SP and SP-to-IdP redirections, the delivery of an unrequested resource upon redirection outside of the SAML SSO Protocol is prevented, but a malicious SP can still mount the one depicted in the Figure 2.

Launching pad for cross-Site Request Forgery (XSRF) attacks. This attack assumes that the URI that was initially requested did not point to a resource, but rather contained a URL-encoded command, such as a request for the change of some settings or user's preferences, for the deletion of some resource or for the annulment of/committing to an action, such as the purchase of a paid good. Depending on the output provided by the execution of the command, the client may or may not be able to detect the attack. This type of attack is even more pernicious than classic XSRF, because XSRF requires C to have an active session with SP, whereas in this case, the session is created automatically hijacking C's authentication attempt.

Launching pad for cross-Site Scripting (XSS) attacks.

It is straightforward to see that this attack also constitutes a launching pad to reflected XSS attacks, i.e. XSS attacks that can be triggered by visiting a maliciously-crafted URL. In addition, a vanilla implementation of the SAML SSO protocol exposes the RelayState field to a possible injection of malicious code that may be executed at the honest SP side. Although the SAML standard recommends to protect the integrity of this field, our experience shows that this often is not the case (see Section 4). In addition, unlike normal XSS attacks, where the attacker has to rely on social engineering (phishing, spam and so forth) to lure a victim into clicking on a malicious link, an exploitation of the vulnerability paves the way for systematically luring victims into visiting URIs that may be vulnerable to cross-site scripting attacks. Note also that in this case, unlike in the previous exploitations, the client is not suspicious about receiving a different resource than the one requested. On the contrary, because arbitrary code can be embedded in uri, a redirection to uri i , the page that c initially requested, can be eventually forced at the end of the attack. As an example, if uri is forged as javascript:window.open('uri i '+document.cookie) the client would be victim of the theft of its cookies for the domain sp through a visit to the requested uri i .

Although in this paper we focus on the SP-initiated SSO protocol, it is worth mentioning that IdP-Initiated flows may suffer from login CSRF attacks [START_REF] Barth | Robust defenses for cross-site request forgery[END_REF], whereby the attacker forges a cross-site request to the login form and, logs the victim into a honest web site as the attacker.

Exploitations in actual deployments

An interesting question that we also address in this paper is whether exploitations of the abstract weakness of the standard are possible in actual deployments of the SAML SSO Protocol. To this end, we have analyzed various SAML-based SSO solutions available on the market, including SAML-based SSO for Google Apps, SimpleSAMLphp as deployed for Foodle (see https://foodl.org), and a deployment of the Novell Access Manager 3.1 in a real industrial environment. All these deployments support the SAML SSO use case; not surprisingly, by inspecting SSL messages we verified that the SPs employed in these deployments accept and process a SAML response flowing on a different SSL channel than the one used to deliver the SAML request.

Our analysis of the SAML-based SSO for Google Apps shows that by exploiting the weakness of the standard, a malicious SP can force C to consume a resource from Google, for instance, visiting any page of the gmail service. mailbox. This trivial attack is however easily detected by C, and does not bring any real advantage to the attacker. Definitely more serious for the over one million business customers of Google Apps was the XSS attack we were able to execute and that allowed the malicious SP to steal the C' cookies for the Google domain and thus to impersonate C on any Google application. The abstract flaw of Figure 2 served indeed as launching pad for this XSS: because of missing sanitization, an attacker could inject malicious code into the RelayState field and have it successfully executed on the client's browser as if coming from the Google domain (thus circumventing the same origin policy). In other words, the combination of the abstract flaw and the missing sanitization was the key to mount the XSS attack. The past tense is in order here since, as soon as we found this attack, we informed Google, who promptly patched the issue.

We have been able to mount a similar XSS attack on the SAML SSO solution of the Novell Access Manager 3.1 as deployed in a real industrial environment. In this deployment RelayState is not used to store the URI;instead, a URLencoded parameter is used to this end, and this parameter is not sanitized.

The SimpleSAMLphp, as deployed in Foodle, stores the initially requested URI into the URL parameter ReturnTo. Although that field is not sanitized, we have not been able to mount any XSS. The reason is that SPs running Simple-SAMLphp additionally use cookies that block the abstract flaw we discovered. We will detail this solution in the next section.

The findings presented above show that the authentication flaw we discovered can be exploited on actual deployments of the SAML SSO Protocol, even leading to major security issues. We have informed Novell and UNINETT (the developer and maintainer of SimpleSAMLphp) about these findings as well as the US-CERT so that other vendors implementing and deploying SAML-based SSO solutions can get advantage of this information.

Fixing the vulnerability

The root of the problem of the authentication flaw presented earlier lies in the following two main factors:

1. Clients are not able to link the Authentication Request they receive from the SP in step A1 with their initial requests for a resource issued in step S1; 2. The SP is not able to enforce that the messages exchanged with C (cf. steps S1, S2, A1, and A4) are carried over the same channel.

We have verified that-could one of the two causes be removed-the vulnerability would no longer be exploitable. We emphasize nonetheless that the SAML SSO Protocol alone neither achieves property (P1) nor mandates the implementation of any of these solutions, thus leaving a vanilla implementation in principle flawed.

The challenge is to fix the vulnerability with minimal changes so that existing solutions can be secured without radical modifications to the software compo-nents (e.g. SAML ECP profile) or to the standard. In what follows, we outline a number of possible solutions, highlighting their strengths and shortcomings.

Cookies. A standard way of enforcing bindings on sessions is implemented using session cookies. With reference to Figure 1, by setting a session cookie in step A1 and expecting to receive it back on message A4, SP could check that the communication has occurred with the same client. However, cookies only provide means to mitigate the problem-albeit sufficient in many scenariosand do not represent a complete countermeasure. Indeed cookies are designed to be difficult to steal and it is not as hard to set them. For instance, cookies with the "Secure" flag on (which instructs the browser not to transmit them over unencrypted channels) can be set over unprotected connections. (The latest versions of IE and of Firefox allow this.) In practice an attacker could circumvent the protection offered by cookies by (i) setting a cookie for the victim SP through injected Javascript or HTML META tags; (ii) corrupting the proxy discovery phase setting up a rogue wpad or dhcp server, thus becoming the user's proxy; (iii) performing ARP poisoning thus becoming the victim's default gateway.

Feedback from the user. As seen in the preceding Sections, the user may initiate the SAML SSO profile, authenticating to an SP without actually having explicited requested anything from it. This can be avoided if the IdP informs the user about the attempt to access URI on the SP during the authentication and asks for an explicit consent before issuing the authentication assertion to SP. In this way, the user may realise that the authentication is going to be sent to a different SP than expected and may be given the possibility to stop the protocol. This solution has a number of drawbacks: first of all, it forces a security decision upon a (possibly technically unaware) user, who is asked to tell apart legitimate SP-to-SP redirections from malicious ones. In addition, it breaks the seamlessness of SSO, in which the authentication process is supposed to be carried out with minimal interactions with the user.

Self-signed client certificates. A simple, yet effective way to ensure SP that it is interacting with the same client is to provide the latter with a self-signed certificate. The solution goes as follows: during the first SSL session (cf. steps A1 and A2 in Figure 1) C is asked to present the certificate. SP will then generate an Authentication Request and its ID field is set to n || HMAC K || n (RSA modulus), where n is a nonce, K is a secret known only to SP, RSA modulus is the RSA modulus of the public key contained in the client's certificate. HMAC is the wellknown HMAC keyed hash function [START_REF] Bellare | Keying hash functions for message authentication[END_REF] and || denotes the concatenation. After this, SP deletes all state information and sends the Authentication Request to C. During the second SSL session (cf. steps A3 and A4), C is again asked for the certificate and the same certificate will be delivered to SP. The standard requires the InResponseTo field of the Response message to contain the same value of the ID field of the Authentication Request message: therefore SP can parse such field as n and H and then check whether H = HMAC K || n (RSA modulus).

Note that (i) the client can easily self-generate a certificate; alternatively, the SP can offer the client to forge one on his behalf; (ii) the certificate is not expected to carry information about the identity of the user; in particular, it is not used to assess the user identity; and (iii) during the SSL handshake, the browser proves knowledge of the private key; the approach therefore guarantees with overwhelming probability that a malicious third party cannot forge a copy of the same certificate since -in case of certificates that use RSA encryption for instance -it would entail breaking the RSA hardness assumption.

Related Work

Pfitzmann et al. [START_REF] Pfitzmann | Analysis of Liberty Single-Sign-on with Enabled Clients[END_REF][START_REF] Pfitzmann | Federated identity-management protocols[END_REF][START_REF] Groß | Browser model for security analysis of browser-based protocols[END_REF] lay the theoretical basis for a rigorous analysis of webbased federated identity-management protocols (e.g. the SSO protocol proposed by Liberty Alliance in 2002). They discuss some security vulnerabilities and possible preventive measures. Some of these results have been fed into the Liberty Alliance project and indirectly into the SAML 2.0 standard.

Security analyses of the SAML SSO v1.0 are presented in [START_REF] Groß | Security analysis of the SAML Single Sign-on Browser/Artifact profile[END_REF] and in [START_REF] Hansen | Using static analysis to validate the SAML single sign-on protocol[END_REF]. The security analysis presented in our paper refers to SAML SSO v2.0, the latest version of the standard. Moreover, in our work we focus on scenarios that are most likely to occur in actual deployments. For instance, unlike [START_REF] Hansen | Using static analysis to validate the SAML single sign-on protocol[END_REF] we do not assume that SPs are trustworthy and unlike [START_REF] Groß | Security analysis of the SAML Single Sign-on Browser/Artifact profile[END_REF] we assume that messages are exchanged over secure channels as recommended by the standard.

In [START_REF] Armando | Formal Analysis of SAML 2.0 Web Browser Single Sign-On: Breaking the SAML-based Single Sign-On for Google Apps[END_REF] we provide a formal model of the SAML SSO protocol as well as of a variant implemented in the SAML-based SSO for Google Apps. By using a model checker, we discovered a subtle man-in-the-middle attack on the SAML-based SSO for Google Apps. In reaction to this discovery Google has modified the implementation of the protocol. The version of the protocol used by the SAMLbased SSO for Google Apps we described in Section 4 is the one currently in use by Google and therefore does not suffer from the attack reported in [START_REF] Armando | Formal Analysis of SAML 2.0 Web Browser Single Sign-On: Breaking the SAML-based Single Sign-On for Google Apps[END_REF]. Interestingly, in [START_REF] Armando | Formal Analysis of SAML 2.0 Web Browser Single Sign-On: Breaking the SAML-based Single Sign-On for Google Apps[END_REF] we did not find any attack on the Web Browser SAML 2.0 SSO profile as in our analysis we assumed that communication between C and SP is carried over a single unilateral SSL channel. We have adapted that formal model so to allow the messages of steps S1 and A4 to be transported over different SSL sessions and used the SATMC model-checker to analyze this new specification. This has allowed us to discover the previously unknown attack described in Section 3.

Conclusions

Authentication protocols are notoriously difficult to get right, even more so for browser-based authentication protocols because "browsers, unlike normal protocol principals, cannot be assumed to do nothing but execute the given security protocol" [START_REF] Groß | Browser model for security analysis of browser-based protocols[END_REF]. In this paper we have showed that browser-based SSO protocols are no exception. We have presented an authentication flaw in the SAML SSO, discussed how this flaw can be generally exploited, and reported related security issues that we have detected in actual SAML-based SSO solutions developed by prominent software companies, including a severe attack on the SAML-based SSO for Google Apps. We have finally presented a number of possible solutions that mitigate or even solve the problem. As a part of our future work we plan to extend our analysis to other SSO solutions.

Fig. 1 .

 1 Fig. 1. SAML SSO Protocol: SP-Initiated SSO with Redirect/POST Bindings

Fig. 2 .

 2 Fig. 2. Authentication Flaw of the SAML 2.0 Web Browser SSO Profile

If this assumption does not hold, C is vulnerable to a number of other trivial attacks anyway.

This work has partially been supported by the FP7-ICT Projects AVANTSSAR (no. 216471) and SPACIOS (no. 257876), and by the project SIAM funded in the context of the FP7 EU "Team 2009 -Incoming" COFUND action. Furthermore the authors would like to thank Brian Eaton, Scott Cantor, Matteo Grasso, and the SAP NetWeaver SIM team for the valuable discussions and feedback they provided.

See, for instance,


Nwokedi Idika
email: nidika@cs.purdue.edu

Bharat Bhargava

A Kolmogorov Complexity Approach for Measuring Attack Path Complexity

Keywords: security, security metrics, attack graphs, exploitability

The difficulty associated with breaching an enterprise network is commensurate with the security of that network. A security breach, or a security policy violation, occurs as a result of an attacker successfully executing some attack path. The difficulty associated with this attack path, then, is critical to understanding how secure a given network is. Currently, however, there are no consistent methods for measuring attack path complexity that make the assumptions of a modeler explicit while providing flexibility in how the modeler models the attack path. To provide these desirable attributes, we propose a regularexpressions-inspired language whose rationale for attack path complexity measurement is based on Kolmogorov Complexity. After detailing our Kolmogorov Complexity-based method, we demonstrate how it can be applied to a novel security metric: the K-step Capability Accumulation metric-a metric that defines the security of a network in terms of the network assets attainable for attack effort exerted.

Introduction

A completely secure network is one where no attacker can violate a security policy of that network. Since such a system is currently impractical, an approximation to it would be one where the attacker has extreme difficulty violating the network's security policies. Thus, one way of asking "how secure is this network?" would be to ask "how difficult is it to violate a security policy in this network?" When violations occur, they happen as result of a weakness, or a series of weaknesses, that the attacker leverages. These weaknesses in the network are referred to as vulnerabilities. The complexity associated with exploiting a vulnerability is then critical to the security of a network.

The ease with which an attacker can successfully take advantage of a vulnerability is referred to as exploitability. The importance of exploitability is reflected by its inclusion in all the well-known vulnerability scoring systems. For instance, the Common Vulnerabilities Scoring System (CVSS) [START_REF] Mell | Common Vulnerability Scoring System[END_REF] computes exploitability as a linear combination of qualitative values. The Computer Emergency Response Team/Coordination Center (CERT/CC) [2] produces a numeric vulnerability score based on a series of questions-one of which is, "How easy is it [the vulnerability] to exploit?" The SANS Critical Vulnerability Analysis Scale Rating [8] includes the ease of exploitation in defining two of its four ratings.

Security metrics that rely on exploitability measure security in terms of the effort or skill the attacker needs to cause a security policy violation. When security violations occur as a series of vulnerability exploits, the dependencies among these exploits can be incorporated into security metrics that utilize the attack graph. An attack graph is an abstraction that reveals the ways an attacker can use identified vulnerabilities interdependently in a network to violate a security policy. In this paper, we use condition-oriented attack graphs [START_REF] Noel | Managing Attack Graph Complexity Through Visual Hierarchical Aggregation[END_REF] where nodes correspond to hosts, and edges correspond to vulnerabilities. Examples of attack graphs are displayed in Figure 3. Security metrics based on attack graphs are referred to as attack graph-based security metrics. An instance of such a metric would the Shortest Path metric. This metric [START_REF] Phillips | Swiler: A Graph-based System for Network-vulnerability Analysis[END_REF] denotes the security of a network as the path from the attack graph that is of least of resistance. Another example attack graph-based security metrics is the Average Path Length metric. This metric [START_REF] Li | Cluster Security Research Involving the Modeling of Network Exploitations Using Exploitation Graphs[END_REF] denotes the security of a network as the mean difficulty associated with all paths from the attack graph.

In the attack graph, attack path difficulty (or complexity) is represented as path length. Path length may be represented as the number of edges between the attacker's initial state and goal state or as a more complicated algebraic permutation of vulnerability scores along attack paths. While such flexibility in path length representation may be appropriate and necessary for a network administrator to model the threat of a given network, such flexibility hinders consistent communication across organizations and among researchers. If a method more complex than simply counting the edges along a path is used, some qualitative information is being employed. Because quality can be subjective, different organizations and researchers may score vulnerabilities differently and potentially compute path length differently. These differences are fine as long as the assumptions being made are explicit and grounded in theory.

We propose an approach to maintain flexibility in how attack path complexity is modeled, make associated modeling assumptions explicit, and provide a theoretical basis for attack path measurement. Our approach is called the Kolmogorov Complexity Method (KCM). KCM allows attack paths to be modeled quantitatively or qualitatively using a regular-expressions-inspired language. After describing this methodology, we show how these methods can be applied to a novel security metric called the K-step Capability Accumulation (KCA) metric.

The remainder of the paper will have the following organization. Section 2 describes KCM. Section 3 specifies the KCA metric and how KCM can be used with the metric. Section 4 gives related work associated with attack path complexity and with our novel attack graph-based security metric. Section 5 details our conclusion.

Kolmogorov Complexity Method (KCM)

Given an alphabet and the infinite number of strings that can be produced from that alphabet, some strings are more complex than others. Kolmogorov Complexity is an approach for determining string complexity. Thus, given two strings, Kolmogorov Complexity determines which string is more complex.

Kolmogorov Complexity determines a string's complexity using the size of the smallest program that can produce that string [START_REF] Ming | An Introduction to Kolmogorov Complexity and Its Applications[END_REF]. Let K represent the Kolmogorov Complexity function. In comparing two strings, x 1 and x 2 , if K(x 1 ) < K(x 2 ), then x 2 is more complex than x 1 , because a larger program is needed to describe x 2 . The use of Kolmogorov Complexity to monitor security was first promulgated by Evans et al. in [START_REF] Evans | Information Assurance Through Kolmogorov Complexity[END_REF]. Kolmogorov Complexity has also been applied to spam filtering [START_REF] Spracklin | Filtering spam using kolmogorov complexity estimates[END_REF] by Spracklin and Saxton. We are applying Kolmogorov Complexity to security assessment-and more specifically, the complexity of attack paths.

Kolmogorov Complexity provides a systematic approach for determining complexity of attack paths. There is, however, a caveat to its use. Ming et al.,[START_REF] Ming | An Introduction to Kolmogorov Complexity and Its Applications[END_REF], have shown that determining a lower bound K is impossible. With respect to attack path complexity, this finding means that we can never find the "true" effort needed for any attacker to exploit a vulnerability. This constraint need not be a hindrance to its use if reasonable effort estimates can be obtained. Nonetheless, KCM provides a standard way for communicating attack path complexity that is based upon a sound theory of complexity. Such formalism provides consistency among researchers when comparing measurements. Below, we provide an attack path complexity description language inspired by the language of regular expressions.

Alphabet

1.

A corresponds to the exploits (i.e., instances of vulnerabilities) found in all attack graphs being considered.

Constants

1. corresponds to the empty string.

2. e i ∈ A denotes an exploit from one of the attack graphs being considered.

3. ∅ corresponds to the empty set.

Operations

1. Let S and T be two strings comprised of characters from A.

2. Let E 1 and E 2 be expressions of the language.

3. ST evaluates to the concatenation of strings S and T . 4. () provides priority ordering of evaluation. 5. (S) + states that the expression S may repeat one or more times but must appear once.

6. S k evaluates to k instances of S concatenated together.

E

[k]

1 E 2 evaluates to inserting E 1 at index k in E 2 , where the first character in E 2 corresponds to the zeroth index. This can be generalized to

E [k1],[k2],[k3],...,[kn-1],[kn] 1
E 2 . Note: In general, this rule would not be used independently. It would only be used as part of the following two rules.

8. E l,[k] 1 E 2 evaluates to concatenating E l 1 to E 2 , and inserting E 1 into index k of E 2 . 9. E l[k] 1 E 2 evaluates to inserting E l 1 into index k of E 2 .
The above KCM language is flexible in its ability to model the complexity of attack paths. For instance, the attack path in Figure 1 can be represented multiple ways. H1 through H6, Attacker, and Target in Figure 1 correspond to hosts, and v j corresponds to vulnerability j. Based on operations 8 and 9 from the KCM language, a qualitative representation, KCM-qual, of this path can be represented as v

3,2[2] 1 v 2 v 3 yielding an attack path length of 3 vulnerabilities. An equivalent representation would be v 3,[2],[2] 1
v 2 v 3 yielding an attack path length of 3 vulnerabilities. In both representations, E 1 and E 2 from operations 8 and 9 corresponds to v 1 and v 2 v 3 respectively. This representation suggests that once the attacker exploits H1 via v 1 , attacking hosts H2, H3, H6, and Target is trivial because they, for example, require the same credentials to have their vulnerabilities exploited. Such a representation may also be appropriate if known scripts can be used to exploit vulnerabilities in the system. Ultimately the qualitative representation used depends on the subjective decision of the modeler. For instance, the attack path can alternatively be represented as v

3,[2] 1 v 2 v 3 v 1 .
The path length of this representation is 4 vulnerabilities. This representation suggests that the attack path in Figure 1 is more secure than what is suggested by the two representations initially described for this attack path. The semantics of this latter representation suggests that while the same information can be used in exploiting hosts H2, H3, H4, and H6, different information is required to exploit Target. If the attack path is represented as

v 1 v 1 v 1 v 2 v 3 v 1 v 1 ,
then this would, for instance, suggest that different credentials are required for compromising each host. This representation corresponds to the quantitative representation, KCM-quant, which is equivalent to counting the edges along attack paths.

Representing Cycles in Attack Graphs

It is possible for an attack graph to contain cycles. A cycle in an attack graph corresponds to an infinite number of paths. Thus, it can be difficult to reason about such attack paths (e.g., determining attack path length). Typically, cycles are ignored when performing attack graph analysis. Using KCM-qual, a modeler can account for the path length of attack paths containing cycles.

Figure 2 shows a infinite number of attack paths because there is a cycle. Using KCM-qual, we can represent such attack paths. The infinite number of attack paths appearing in Figure 2 can be, for example, captured with

v 2 1 (v 1 v 2 v 3 ) + v 2 1 .
The attack path length of this cyclic attack path is 5 vulnerabilities.

Qualitative Versus Quantitative Representations

The decision of whether to use the qualitative representation of KCM, KCMqual, or the quantitative representation, KCM-quant, is predicated on the amount of information available for the security assessment. If the security engineer has no information regarding exploitation difficulty, KCM-quant is appropriate. KCM-quant assumes all vulnerabilities require distinct, yet, equal amounts of effort. This assumption is overly restrictive in practice. Therefore, practitioners may find KCM-qual most amenable for measuring attack path complexity.

If the security engineer has exploitability information about the vulnerabilities in the network under inspection, then KCM-qual would be appropriate. If the security engineer knows that two vulnerabilities require the same exact actions and information to be exploited, these exploits can be coalesced into a single vulnerability in KCM-qual. An example of this scenario would be when the attacker uses the same credentials to access different hosts within a network. Another example of when two exploits may be coalesced in KCM-qual is when some information (e.g., host name) that the attacker has already acquired or that is publicly known is all that is required to be changed when needing to exploit the second vulnerability. If the security engineer assumes that the attacker is rational, then KCM-qual corresponds more closely to what the attacker will actually experience.

The assumptions the modeler uses can be reflected in the names used for different qualitative representations. KCM-qual-C corresponds to the KCM-qual representation where nodes in an attack path are coalesced only when the same credentials can be used at each node to realize an exploitation. KCM-qual-S corresponds to the KCM-qual representation where nodes in an attack path are coalesced only when there exists some publicly accessible software that reduces the effort of vulnerability exploitation at each node. Under KCM-qual-S, even if two nodes require different software, each node would be coalesced. However, under KCM-qual-S -, a less conservative formulation of KCM-qual-S, nodes would only be coalesced if the same software could be used to exploit vulnerabilities at different nodes. KCM-qual-CS corresponds the combination of KCM-qual-C and KCM-qual-S. Under KCM-qual-CS, nodes on an attack path will be coalesced if with KCM-qual-C holds or KCM-qual-S holds. When KCM-qual is used in this paper, it is referring to the KCM-qual-CS formulation. Naturally, there is also a KCM-qual-CS -. KCM-qual-CS -will coalesce two nodes on the same attack path if either KCM-qual-C holds or KCM-qual-S -holds.

If truly quantitative complexity or probability values were known for each distinct vulnerability in the attack path, then these values could be incorporated with KCM. By assigning these values to the nodes in the KCM-quant representation, algebraic operators would be available to manipulate the values along these paths. If the KCM-qual representation is used, algebraic operators would be unavailable for manipulating the values along attack paths as the result would be mathematically unsound. This soundness issue could be practically bypassed if empirical results showed KCM-qual to be in closer alignment with reality than KCM-quant. The problems of determining the complexity of exploiting a vulnerability or determining the probability of a vulnerability being exploited are critical issues, open problems, and outside the scope of this paper.

K-step Capability Accumulation (KCA) Metric

The K-step Capability Accumulation (KCA) metric specifies the "power" the attacker can obtain on a network in K steps. Practically, "power" refers to access level. Users with the highest access level have the most capability in a network. Such users also have the most opportunity for violating the network's security policy due to their level of access. The granularity of access levels ranges from system-level access to application-level access. This granulation is necessary in some instances as the attacker may successfully obtain system level access to machines on a network and yet still require access to specific authenticated applications. We show how to integrate such application-level accesses in the following subsection. These semantic variations in access level is best captured by the term "capability." This term differs from the notion of capability defined by Phillips and Swiler in [START_REF] Phillips | Swiler: A Graph-based System for Network-vulnerability Analysis[END_REF]. In [START_REF] Phillips | Swiler: A Graph-based System for Network-vulnerability Analysis[END_REF], capability is used broadly to include not only privileged actions within a network, but it also includes the skill level of the attacker and the tools or resources available to the attacker. The capabilities KCA is concerned with are those derived from the network under inspection, that is, privileges and privileged actions. The examples in this paper usage of access levels follows the concept of privileges in [START_REF] Dacier | Models and Toos for quantitative assessment of operational security[END_REF][START_REF] Ortalo | Experimenting with Quantitative Evaluation Tools for Monitoring Operational Security[END_REF] by using system-level access on machines to represent power.

Evaluating with KCA

In determining which of two networks Sys 1 and Sys 2 are most secure using KCA, one procedure would resemble the following. First, generate attack graphs G 1 and G 2 for Sys 1 and Sys 2 respectively. Choose an integer for K that corresponds to the maximum number of steps the analysis should be carried out for if needed. K should be no greater than the minimum of the maximum path length for both attack graphs. One evaluation method is that if an attacker can obtain more capabilities on 1 in K steps, than the attacker can on G 2 in K steps, then Sys 2 is more secure than Sys 1 . KCA is given below.

Cap h (G) = ∪ h capabilities(n) (1) KCA k (G) = ∪ k i=1 Cap i (G) (2)
capabilities(n) returns the set of capabilities available at node n. If more granularity is desired, the capabilities function may be extended with a set of vulnerabilities as an input parameter. Different vulnerabilities may provide different capabilities for an attacker. This extension may be captured by extending capabilities(n) as capabilities({v

1 , v 2 , v 3 ..., v m-1 , v m }, n). Vulnerabilities v 1 through v m correspond
to the vulnerabilities that an attacker may exploit to compromise node n. This extended representation allows for application-level access control to be modeled. Such a model also allows for different attacker profiles. That is, not all attackers have the same skill level or resources [START_REF] Dantu | Risk Management Using Behavior Based Bayesian Networks[END_REF]. Therefore, depending on the assumptions made about the attacker, potentially only a subset of the vulnerabilities may be exploitable. Using our extended representation this scenario can be captured. Cap h (G) represents the capabilities obtained at level h in attack graph G. h represents the distance from the attacker's initial state. KCA k (G) is then simply the union of capabilities obtained at each level up to k.

Applying KCA to the attack graph in Figure 3(a), we obtain different values at each level of the attack graph. The nodes of the attack graph correspond to hosts and access levels. The labels have the format of host:access level. U corresponds to user-level access. A refers to administrator-level access. If access level is not specified, the attacker is assumed to have administrator-level access on the machine. In computing KCA for the attack graph in Figure 3(a), we obtain the following. Cap 1 = user-level access on H1 and H2, administratorlevel access on H3. Cap 2 = Cap 1 and administrator-level access on H1 and H2, and user-level access on H4. Cap 3 = Cap 2 and administrator-level access on the Target host. The attacker can accumulate all privileges in the network in 3 levels.

When comparing two network configurations to decide which is most secure with respect to this metric, we have two options. One option is to compare the two networks' corresponding attack graphs only after k steps. A second option is to compare the two network's corresponding attack graphs at each level up to k. The second option is useful when a security engineer is interested in how quickly the attacker attains capabilities. For instance, after k steps in the two attack graphs being compared, the attacker may have attained the same level of capabilities. This information does not help the security engineer decide which of the two attack graphs is more secure. However, if the security engineer were to examine the two attack graphs using KCA at each level up to k the security engineer may find that in one attack graph, the attacker accumulates all of the network's capabilities after 1 step, whereas in the other attack graph the attacker accumulates all of the network's capabilities after 5 steps. This additional information would suggest to the security engineer that the network corresponding to the latter attack graph is more secure because it requires the attacker to take more steps to acquire all of the network's capabilities.

An alternative method for comparing two network configurations using KCA would be to compare KCA at each step. That is, in comparing two networks, the security engineer deems the network whose attack graph allows for the same or more valuable assets attainable in fewer steps to be less secure. This method of comparison is best exemplified through an example. Observe the attack graph in Figure 3(b). The KCA at level 1 for the attack graph in Figures 3(a) and 3(b) is the same. However, we can see that in Figure 3(b) that Target can be reached in two steps. Assuming that this is the most important host to protect, then the attack graph in Figure 3(b) is less secure because the attacker is able to obtain more power in fewer steps.

Applying Kolmogorov Complexity Method to KCA

The KCA metric uses steps or levels within the attack graph to obtain its values. The KCA metric as previously defined utilizes KCA-quant. To accommodate KCA-qual, we need to redefine Cap.

Cap pi = ∪capabilities(p i ) (3)
This path-oriented version of Cap extracts all capabilities along an entire path p i .

A step or level in KCA under KCM-qual uses the characters in the string representation to determine levels. If an attacker exploits a vulnerability v j that is followed immediately by 0 ≤ m < k v j 's, then the attacker has the capabilities associated with each host that v j violates. If any new vulnerability v l is encountered on the path, then for any v j or v l immediately following this vulnerability the attacker has the capabilities associated with each host that is violated by v l or v j . This pattern continues when evaluating KCA with KCM-qual. If using a KCM-qual representation that involves KCM-qual-S, then any vulnerabilities the software enables exploitation for can belong to a vulnerability superclass that would allow these vulnerabilities to be coalesced.

Let s 1 to s n correspond to the KCM-qual string representations of attack paths p 1 to p n . Let q 1 to q n correspond to the KCM-quant string representations of attack paths p 1 to p n . Let q 0..i j correspond to the substring of q j that includes indices 0 through i. A similar definition exists for s j . Let s i j correspond to the ith character position in s j . A similar definition exists for q j . Let e(s 0..i j ) = q 0..m j , for some integer m such that the vulnerability at index s i j and q m j are the same, and the vulnerability does not appear in q m+1 j , and the vulnerabilities present before q m j all appear in s 0..i j . Then the equation for KCA using KCM-qual is given by the following:

KCA k (G) = ∪ k i=1 Cap e(s 0..i j ) (G), (4)
for all attack paths j. This manifestation of KCA captures the fact that an attacker may obtain knowledge from one attack path and apply this knowledge to a completely separate attack path. If this version of KCA is applied to Figure 3(a), we must first determine how to represent each path. We will then define each path from left to right as the following:

v 1 v 2 2 v 3 , v 1 v 5 v 3 , v 1 v 4 v 6
. Thus, after one iteration, the attacker will have H1:U, H2:U, and H3:A. After two iterations, H1:A, H2:A, and H4:U will be unioned with the attacker's previous capabilities. Note that the attacker is able to obtain H2:A through both v 2 and v 5 . Both are accounted for in this iteration. In the final iteration Target:A is added to the capabilities of the attacker.

Related Work

Because this work proposes an attack path complexity measurement method and a security metric, this section has two parts. The first subsection is dedicated to attack path complexity. The second subsection is focused on relevant attack graph-based security metrics.

Attack Path Complexity

In the authors' literature search, attack path complexity is a topic that has not been directly addressed. An attack path's length can simply be the number of edges (i.e., vulnerabilities) between the attacker's initial state and goal state [START_REF] Phillips | Swiler: A Graph-based System for Network-vulnerability Analysis[END_REF]. If complexity values are assigned to each vulnerability in the form of probabilities, then the product of a given attack path would correspond to the complexity of that attack path [START_REF] Phillips | Swiler: A Graph-based System for Network-vulnerability Analysis[END_REF]. Complexity may also be summed [START_REF] Wang | Measuring Overall Security of Network Configurations Using Attack Graphs[END_REF][START_REF] Phillips | Swiler: A Graph-based System for Network-vulnerability Analysis[END_REF]. Wang et al.,[START_REF] Wang | Measuring Overall Security of Network Configurations Using Attack Graphs[END_REF], noted that a relation could exist between two vulnerabilities such that the exploitation of one vulnerability decreases the complexity in exploiting the other vulnerability. KCM-qual captures this notion as the modeler is given the ability to show that exploiting one vulnerability decreases the difficulty of exploiting other vulnerabilities to zero with use of our language (e.g., operation 6 from the KCM language). The relation in [START_REF] Wang | Measuring Overall Security of Network Configurations Using Attack Graphs[END_REF], allows for more flexibility within the proposed framework in that the complexity of other affected vulnerabilities can change to arbitrary values. We believe that this flexibility, unfortunately, lends itself to the type of subjectivity that hinders the sharing of security metric data. With no rules for how vulnerability complexity values should change due to a vulnerability exploitation, there can be no expectation that researchers will assign changes in complexity values in any uniform way.

Attack Graph-based Security Metrics

There are two security metrics that have inspired KCA: the Shortest Path metric and the Network Compromise Percentage (NCP) metric. If the Shortest Path metric [START_REF] Phillips | Swiler: A Graph-based System for Network-vulnerability Analysis[END_REF], from Phillips and Swiler, is being used under KCM-quant, then the shortest attack path in the attack graph corresponds to the path with the fewest number of edges. If KCM-qual is used, then the shortest path in the attack graph corresponds to the path that produced, through arithmetic/algebraic manipulations, the value considered to have the least resistance in comparison to other paths.

KCA and the Shortest Path metric can be similar when using a goal-oriented attack graph. However, KCA can be applied to attack graphs with no goal states. The Shortest Path metric, on the other hand, cannot be applied to attack graphs with no goal states. Thus, KCA is more versatile in its applicability to different types of attack graphs.

When there is a goal state and the semantics of the attack graph are such that this goal state has all of the asset value in the network, the KCA metric may degenerate to the Shortest Path metric. For instance, if the attacker can reach the goal state in single step and the non-attacker nodes are of little value with respect to the target node, then using the Shortest Path metric without KCA would be sufficient for determining which of the two networks is most secure. However, if other nodes are perceived as being relevant to the network's security, then the KCA metric can be used to obtain more information about the security of the network than what the Shortest Path metric can provide.

The NCP metric [START_REF] Lippmann | Validating and Restoring Defense in Depth Using Attack Graphs[END_REF] proposed by Lippmann et al. denotes the security of the network as the percentage of compromised hosts within the network. A NCP of 100% means that the entire network can be compromised by the attacker. A NCP of 0% means that none of the network assets can be compromised by the attacker. NCP can be extended/modified to include assets that are more finegranular than hosts, and therefore has the same representational ability as KCA. Thus, KCA's differentiating feature is its inclusion of attack effort exerted.

Conclusion

Measuring network security in terms of the difficulty experienced by an attacker in attempting to violate a security policy is an intuitive perspective. However, without systematic and flexible methods for modeling the complexity associated with any given attack path, such a perspective will have limited value. In this paper, we have proposed the well-founded theory of Kolmogorov Complexity to serve as a foundation for measuring attack path complexity. We have also proposed a novel security metric that specifies network security in terms of the assets gained for the attack effort expended.

Fig. 1 .

 1 Fig. 1. A single attack path with Attacker, H1-H6, and Target corresponding to hosts and vj corresponding to vulnerabilities

Fig. 2 .

 2 Fig. 2. An attack path containing a cycle

Fig. 3 .

 3 Fig. 3. Two attack graphs