Paper | ELOISE: Elastic Objects in Kernel Exploitation

1. Basic Information

Yesterday I reviewed the article by Prof. Zhiyun Qian: How to look for a research idea, which encourages me to read good research papers in my field. It is not easy to keep on reading and writing notes. However, I have to admit that it is a good way to learn both advanced knowledge and research approaches. Besides the kernel exploitation techniques I learnt, for example, I find that most of the excellent papers I read leverage some program analysis technologies to automatize their analysis. Hence, I began to take an online program analysis course taught by Prof. Yue Li and Prof. Tian Tan from Nanjing University two weeks ago. You can read my notes for this course.

OK. Now let’s talk about the paper we want to share today. I have read some papers by Prof. Yueqi Chen and Dr. Zhenpeng Lin. This paper is from them as well.

2. Introduction

One common approach to bypass KASLR is to leverage an overwriting primitive to manipulate an elastic kernel object, which firstly manipulates a length field in a kernel object, then places a pointer in the overread region referencing a global variable, uncovers the pointer to userspace through a disclosure channel, and finally compute the kernel base address accordingly.

Researchers want to know whether this exploitation method is useful for a majority of kernel vulnerabilities. In this paper, they design and develop a systematic method to explore the effectiveness of the exploitation method mentioned above.

Their approach is to utilize static/dynamic analysis to identify elastic kernel objects and employ constraint solving to pair elastic objects with corresponding kernel vulnerabilities. They implement this approach as a tool named ELOISE (ExploitabLe Object dIScovEry). BTW, ELOISE also stands for European Large Orbiting Instrumentation for Solar Experiments.

In my view, this approach is very similar to that in their another paper (SLAKE) in CCS'19. You can also read my notes for SLAKE. Hence, for me and other academic newbies, remember to learn static/dynamic analysis and constrain solving :-)

Using ELOISE, researches show that elastic kernel objects are pervasive in kernels of three popular OSes (Linux, XNU and FreeBSD). For many vulnerabilities in these OSes, ELOISE could help attackers find out at least one elastic kernel object, so as to disclose heap/stack cookie, bypass KASLR, or perform arbitrary read.

Researchers also design a new defense mechanism to mitigate the threat of elastic kernel objects. The basic idea is to isolate elastic kernel objects in independent caches.

3. Background

3.1 What is an elastic object?

An elastic object always contains a length field that control the size of an elastic kernel buffer. When the kernel access the data in the buffer, the length field indicates the range of the data that the kernel can read or write.

There are three common implementations of elastic kernel objects in Linux kernel:

3.2 How to use an elastic object to bypass exploit mitigation?

As the diagram below shows, an attacker can use the overwriting ability from a vulnerability to enlarge the length value in an adjacent or overlapping elastic object, and then conduct buffer overread on the elastic object to read sensitive values (addresses to bypass KASLR or heap cookies) in the next adjacent object:

3.3 Challenges of Using Elastic Objects for Kernel Exploitation

There are three challenges for an adversary to perform the foregoing exploitation:

1. Given the complexity of kernel code and versions, it is hard to ensure a specific kernel implementation uses the elastic kernel objects.
2. The adversary has to guarantee the existence of leaking channel, through which he/she can pass data stored in the elastic buffer to a userland process.
3. Given a vulnerability corrupting data in a particular cache/zone, the adversary has to guarantee he/she can allocate the desired kernel object in the same cache and the vulnerability ability is sufficient to manipulate the length field tied to the elastic buffer.

3.4 Threat Model & Assumptions

Researchers put forward four assumptions for this study:

1. Common kernel protection mechanisms and mitigations are enabled, e.g., SMEP/SMAP, KPTI and W⊕R.
2. The kernel heap freelist is randomized.
3. The attacker has only one zero-day vulnerability.
4. The capability of a vulnerability indicates at which memory region an adversary could overwrite data freely.

4. Technical Approach

4.1 Identifying Elastic Object Candidates

This part is similar to the first part in SLAKE.

Firstly, researchers track down elastic structure candidates by recursively flattening kernel data structures and identifying integer variables in these structures.

Secondly, they pinpoint candidates at allocation sites: (1) track down all heap memory allocation sites (e.g., kmalloc, kalloc and malloc), (2) examine whether the allocated objects are in the types of candidate structures by analyzing the type of return value via a use-def chain with LLVM and resolution of memory alias, and (3) check whether reaching these allocation sites requires any root privilege by examining invocation of kernel functions like capable() and priv_check() along the path and access to devices which can only be accessed by privileged users.

Thirdly, researchers profile the elastic object candidates to know the cache/zone to which an elastic object belongs.

4.2 Filtering out Object Candidates

After garnering the list of elastic object candidates, researchers narrow candidates down to those which contain integer variables representing the size of a kernel buffer and support data disclosure by performing an interprocedural backward data flow (taint) analysis on calling sites of a set of critical kernel functions as leaking anchors:

There are lots of details on the taint analysis in the paper, which are very helpful if we want to reproduce the steps or adopt similar approaches. Here I just omit the details and excerpt the diagram as shown below:

I am happy to see that this is a little similar to the experiment I have done in the program analysis course. I will be able to do the analysis some day!

Three types of variable assignment sites can be derived from the diagram above:

1. src=&buffer (stack): an adversary could potentially leak the stack canary and the return address to bypass KASLR.
2. src=&objA->buffer (heap): an adversary could potentially bypass KASLR or leak the heap cookie.
3. src=objA->p (arbitrary memory): if the pointer and the length variables are within the same object, an adversary could potentially not only bypass KASLR, but also perform arbitrary kernel read (one of my kernel PWN posts introduces how to leverage the arbitrary read capability).

For each leaking anchors surviving from the analysis, researchers store it as a record (shown at the top of the diagram above) in a database.

4.3 Pairing Vulnerabilities with Objects

After the analysis above, researchers get a database for use. Given a vulnerability, one can just pair that vulnerability with elastic objects accordingly in a formalized way very similar to the approach used in the SLAKE paper.

Let’s take an example. Assume the length field of an elastic object is at the third 8 bytes, and the object contains a pointer referencing a buffer in an object located at the cache kmalloc-192. Given part of the vulnerability capability ([16, 24)=1024), the attacker could change the size of the elastic buffer to 1024 and thus overread the buffer and access the data in its entire adjacent slot:

Researchers find that on the paths toward the leakage sites after the manipulation of an elastic object, the kernel might use the manipulated fields as branch predictors, and improper modification could lead to unexpected kernel executions, general page fault (GPF) or even worse, kernel panic.

To figure out these situations, researchers conduct constraint solving to ensure all the pointer dereferences along the path towards leaking anchors are valid:

5. Implementation

Firstly, ELOISE generates LLVM bitcode files, constructs CFG based on work from another paper, and reuses the AliasAnalysis pass provided by LLVM to extract alias analysis results. Then ELOISE identifies and filters elastic objects and extracts constraint sets on top of the foundation work. After that, it utilizes Z3 solver to pair vulnerability with elastic objects.

The elastic objects found in Linux and related features and constraints are shown as below:

6. Evaluation

It should be admitted that the evaluation part is complicated, but reasonable and awesome. Researchers design three experiments to evaluate the effect of elastic objects on kernel protection circumvention across three open-sourced kernels:

1. Evaluating the tool (FP/FN) and characterizing elastic objects.
2. Evaluating the ability to bypass mitigation with 40 real-world kernel vulnerabilities.
3. Evaluating the utility of ELOISE in exploit development assistance by recruiting professionals for test.

As there are too many details in this section, I recommend you to read the paper. It is really inspiring and instructive.

7. Defense Approach

The defense mechanism proposed in this paper is to isolate elastic objects into individual shadow caches/zones, which is implemented by adding one more flag&feature (e.g., __GFP_ISOLATE) for the functions used to allocate kernel object.

8. Summary

After reading this paper, I get some ideas about how to conduct a great offensive security research:

1. Find a vulnerable feature which could be leveraged by attackers. You don’t have to be the first one to find it or use it in exploitation, but it must be never systematically studied before.
2. Conduct a research on this feature in a systematic way, which always consists of various dynamic and static analysis techniques. In this way, you may encounter some challenges, e.g., the complexity of source code and the indeterministic runtime status. Faced these challenges, you proposed some insights and consequently an innovative approach based on these insights.
   1. Conduct your approach. Try your best to excavate most of the potential results that could be found via your approach. Your results will demonstrate the universalism and severity of the problem.
   2. Formalize and model research targets, e.g., the vulnerabilities and exploitation primitives. This paper serves as a good example: it formalizes the memory corruption capability of vulnerabilities and the leakage capability of different elastic objects, and then matches them with each other to filter proper elastic object(s) given a vulnerability.
3. Quantitative evaluation. Design and conduct experiments based on real-world cases to evaluate the contributions of the research from at least two aspects:
   1. The advantage and disadvantage of your approach, as well as false positives and false negatives.
   2. The effectiveness of the result of your research, e.g., the improvement degree of exploitability for the selected CVEs in this paper.
4. Qualitative/manual evaluation. If necessary, you can invite professionals for interview, questionaire and even try-out of the tools and knowledge from your research. Remember to set control group.
5. Automatization. Develop a tool like Angr, or even a product for start-up like Mayhem.
6. Design and implement defense strategy. You have proven the severity of issues and value of your tools. Now it is the time to answer how to defend and implement your design.
7. Evaluate your defense strategy from two aspects: effectiveness and overhead.

Again, read the paper! It deserves your attention.