Adaptive Kernel Live Patching:
An Open Collaborative Effort toAmeliorate Android N-day Root Exploits
Yulong Zhang and Lenx (Tao) Wei
Baidu X-Lab
August 2016

Agenda• The Problem• Android Kernel Vulnerability Landscape• Why Are They Long-lasting?
• Case Studies• The Solution• AdaptKpatch: Adaptive Kernel Live Patching• LuaKpatch: More Flexibility, Yet More Constraint• The Future• Establishing the Ecosystem

Threats of Kernel Vulnerabilities
UnprivilegedUserRootUser Mode

Information Leakage

Privilege Escalation

Info-leakVulnerability

Code Execution
Vulnerability

Kernel ModeThreats of Kernel Vulnerabilities• Most security mechanisms relying on kernel integrity/trustworthinesswill be broken• Access control, app/user isolation• Payment/fingerprint security• KeyStore• Other Android user-land security mechanisms• TrustZone will also be threatened• Attack surfaces exposed• Not enough input validation

Kernel Vulnerabilities in Android Security Bulletin
Monthly Disclosed Number of Android Kernel
Vulnerabilities

66

7060
50
40
30
20
10011344715

192015/09 2015/12 2016/01 2016/02 2016/03 2016/04 2016/05 2016/06 2016/07The Growing Trend Indicates
MonthCount

2015/09

1

...

...

2015/121

2016/013

2016/024

2016/034

2016/04

7

2016/0515

2016/0619

2016/0766• More and more attentions aredrawn to secure the kernel• More and more vulnerabilities
are in the N-Day exploit arsenal
for the underground businesses

Many Vulnerabilities Have Exploit PoC Publicly Disclosed
Vulnerability/Exploit Namemempodipper
exynos-abuse/Framarootdiagexploit
perf_event_exploit
fb_mem_exploit
msm_acdb_exploit
msm_cameraconfig_exploit
get/put_user_exploit
futex_exploit/Towelroot
msm_vfe_read_exploit
pipe exploit
Ping Pong Root
f2fs_exploit
prctl_vma_exploit
keyring_exploit…...

CVE IDCVE-2012-0056
CVE-2012-6422
CVE-2012-4221
CVE-2013-2094
CVE-2013-2596
CVE-2013-2597
CVE-2013-6123
CVE-2013-6282
CVE-2014-3153
CVE-2014-4321
CVE-2015-1805
CVE-2015-3636
CVE-2015-6619
CVE-2015-6640
CVE-2016-0728......

KEMOGEhttps://www.fireeye.com/blog/threat-research/2015/10/kemoge_another_mobi.html

GHOSTPUSH

http://www.cmcm.com/blog/en/security/2015-09-18/799.html

DOGSPECTUS“... the payload of that exploit, a Linux ELF executable named module.so,contains the code for the futex or Towelroot exploit that was first
disclosed at the end of 2014.”

https://www.bluecoat.com/security-blog/2016-04-25/android-exploit-delivers-dogspectus-ransomware

HUMMINGBAD“All combined, the campaign includes nearly 85 million devices...
HummingBad attempts to gain root access on a device with a rootkit that
exploits multiple vulnerabilities... It tries to root thousands of devices
every day, with hundreds of these attempts successful.”
https://www.bluecoat.com/security-blog/2016-04-25/android-exploit-delivers-dogspectus-ransomware

iOS More Secure?

?

V.S.

iOS Version

Release Date

Kernel Vulnerability #Android # In This Period

8.4.1

8/13/15

3-

99/16/15

121

9.1

10/21/15

6-

9.2

12/8/1551

9.2.1

1/19/16

4

3

9.3

3/21/1698

9.3.2

5/16/161122

So the problem is: Android has MORE vulnerabilities

Vulnerabilities remain UNFIXED over a long time
http://www.whisperingrandomness.com/wp-content/uploads/2014/03/iOS-security-black-hat-macworld-australia.jpg
http://images.pcworld.com/images/article/2011/11/androidsecurity-5241445.jpg

Agenda• The Problem• Android Kernel Vulnerability Landscape• Why Are They Long-lasting?
• Case Studies• The Solution• AdaptKpatch: Adaptive Kernel Live Patching• LuaKpatch: More Flexibility, Yet More Constraint• The Future• Establishing the Ecosystem• If Apple wants to patch a vulnerability• Apple controls the entire (mostly) supply chain• Apple has the source code
• Apple refuses to sign old versions, forcing one-direction upgrade• All the iOS devices will get update in a timely manner• Android• Many devices stay unpatched forever/for a long period...

Why Are Android Kernel Vulnerabilities Long Lasting?
• The long patching chain delays the patch effective date
• Fragmentation makes it challenging to adapt the patches to alldevices• Capability mismatching between device vendors and security vendors

Cause A: The long patching chain

There are exploits
appeared in public but• Never got officially reported tovendors

Exploits made public but not reported

Android Root and its Providers: A Double-Edged Sword
H. Zhang, D. She, and Z. Qian, CCS 2015

There are exploits
disclosed but• Not getting timely patches

Exploits disclosed but not timely patchedhttps://bugs.chromium.org/p/project-zero/issues/detail?id=734&can=1&sort=-id

There are exploits
patched but• Delayed by the carriers

Exploits patched but delayed by carriers

http://www.howtogeek.com/163958/why-do-carriers-delay-updates-for-android-but-not-iphone

User delays the OTA due
to rebootingWhy Are Android Kernel Vulnerabilities Long Lasting?
• The long patching chain delays the patch effective date
• Fragmentation makes it challenging to adapt the patches to alldevices• Capability mismatching between device vendors and security vendors

Cause B: Fragmentation

http://opensignal.com/reports/2015/08/android-fragmentation

Google Dashboard (2016/07/21)
VersionCodename

APIDistribution

2.2

Froyo

80.1%

2.3.x

Gingerbread

10

1.9%

4.0.x

Ice Cream
Sandwich

15

1.7%

16

6.4%

17

8.8%

18

2.6%

19

30.1%

21

14.3%

22

20.8%

23

13.3%

4.1.x
4.2.x

Jelly Bean

4.3
4.4
5.0
5.1
6.0

KitKatLollipop
Marshmallow

Lollipop was released in November 12, 2014, but

51.6% of the devices are still older than that!

Google stopped patching for Android older than 4.4,
but

21.5% of the devices are still older than that!

Chinese Market Is Even Worse(Stats from devices with Baidu apps installed, July 2016)

Codename
VersionGingerbread
2.3.x
4.0.x Ice Cream Sandwich
4.1.x
Jelly Bean
4.2.x
4.3
4.4
55.1

3%

Rate
3%
3%

19%

3%
Gingerbread
Ice Cream Sandwich
36%

36%

Jelly Bean
KitKat

KitKat39%

Lollipop

19%Lollipop
39%

Lollipop was released in November 12, 2014, but

80% of the devices are still older than that!

42% of the devices are <4.4!Why Are Android Kernel Vulnerabilities Long Lasting?
• The long patching chain delays the patch effective date
• Fragmentation makes it challenging to adapt the patches to alldevices• Capability mismatching between device vendors and security vendors

Phone Vendors:• Privileged to apply the patches• With source code, easy to adapt the patches• Not enough resources to discover and patch vulnerabilities

Security Vendors:• Capable to discover and patch vulnerabilities• Not privileged enough• Without source code, difficult to adapt the patches

Agenda• The Problem• Android Kernel Vulnerability Landscape• Why Are They Long-lasting?
• Case Studies• The Solution• AdaptKpatch: Adaptive Kernel Live Patching• LuaKpatch: More Flexibility, Yet More Constraint• The Future• Establishing the Ecosystem

CVE-2014-3153 (Towelroot)• The futex_requeue function in kernel/futex.c in the Linux kernel
through 3.14.5 does not ensure that calls have two different
futex addresses, which allows local users to gain privileges.

CVE-2015-3636 (PingPong Root)• The ping_unhash function in net/ipv4/ping.c in the Linux kernel before 4.0.3
does not initialize a certain list data structure during an unhash operation,
which allows local users to gain privileges or cause a denial of service.

CVE-2015-1805 (used in KingRoot)• The pipe_read and pipe_write implementations in kernel before 3.16 allows
local users to cause a denial of service (system crash) or possibly gain
privileges via a crafted application.
• A known issue in the upstream Linux kernel that was fixed in April 2014 but
wasn’t called out as a security fix and assigned CVE-2015-1805 until
February 2, 2015.

CVE-2014-3153
Towelroot
CVE-2015-3636
Ping Pong Root
CVE-2015-1805
Pipe Root
0200400600
800
Days since the advisory publication date1000

100%80%60%40%20%0%
CVE-2014-3153
Towelroot

CVE-2015-3636
Ping Pong Root

Vulnerable

CVE-2015-1805
Pipe Root

Not Vulnerable

Vulnerability statistics collected from Chinese Android device in July 2016

How/Who to Secure Them???

Agenda• The Problem• Android Kernel Vulnerability Landscape• Why Are They Long-lasting?
• Case Studies• The Solution• AdaptKpatch: Adaptive Kernel Live Patching• LuaKpatch: More Flexibility, Yet More Constraint• The Future• Establishing the Ecosystem

Kernel Live Patching• kpatch• kGraft• ksplice• Linux upstream’s livepatch• ......

Kernel Live PatchingkGraft as an example

Kernel Live Patching• Load new functions into memory• Link new functions into kernel• Allows access to unexported kernel symbols• Activeness safety check• Prevent old & new functions from running at same time
• stop_machine() + stack backtrace checks• Patch it!
• Uses ftrace etc.
https://events.linuxfoundation.org/sites/events/files/slides/kpatch-linuxcon_3.pdf

Challenges for Third Party• Most existing work requires source code. Phone vendor
is the only guy that can generate the live patches• Unable to directly apply patches to other kernel builds

AdaptKpatch - Adaptive Live Patching
Auto patchadaption• Kernel info gathering• Data structure filling

Patching
payloadinjection• Choice A: Install kernelmodule• Choice B: Binary code
injection via mem device

Patching
payloadexecution• Replace/hookvulnerable
functionsKernel Info Collection• Kernel version• /proc/version• vermagic• Symbol addresses/CRC• /proc/kallsyms (/proc/sys/kernel/kptr_restrict)• Other kernel modules• Symbol CRC/module init offset• Boot image• decompress gzip/bzip/lzma/lzo/xz/lz4• some are raw code or even ELF filePatch Injection Methods Coverage

INSMOD 95%(K)MEM 60%

99.4%
0.6%

Method A: Kernel Module Injection
Kernel checks that need to be resolved for adaption§ vermagic check§ symbol CRC check§ module structure check§ vendor’s specific checkvSamsung lkmauthBypass vermagic/symbol CRC- Big enough vermagic buffer- Copy kernel vermagic string to module- Copy kernel symbol CRCs to module

Bypass Samsung lkmauth

Method B: mem/kmem Injection- Symbol addresses- vmalloc_exec- module_alloc- Structured shellcode- Allocate/reuse memory- Write into memory- Trigger the runningPatching Payload Execution• Overwrite the function pointer• Overwrite with patch code directly• Inline hook

Same with otherlive patching methods

Adaption Challenges Solved• Patch automatic adaption
PatchAuto adaption
Devicekernel info

Adapted patch

Challenges SolvedüMost existing work requires source code. Phone vendor
is the only guy that can generate the live patchesüUnable to directly apply patches to other kernelbuildsVulnerable

Immutable

Vulnerable

ImmutableSuccessfully Evaluated CVEs
• mmap CVEs
• CVE-2014-3153• CVE-2015-0569• CVE-2015-1805• CVE-2015-3636• CVE-2015-6640• CVE-2016-0728• CVE-2016-0805• CVE-2016-0819• CVE-2016-0844• …...

è Framarootè Towelrootè Pipe Root
è Ping Pong Root

Successfully Evaluated on Most Popular Phones

GT-I8552

GT-S7572

S4A7SM-G5308W

Grand 2Note 4Successfully Evaluated on Most Popular Phones

C8813

P6-U06

HornorU8825D

Successfully Evaluated on Most Popular Phones

M7

M8Sw

S720e

T528d

Successfully Evaluated on Most Popular Phones

A630t

A788t

A938t

K30-T

Successfully Evaluated on Most Popular Phones

DemoBefore Patch: Ping Pong Root succeed
After Patch: Ping Pong Root fail

Recall the Two Problems• The long patching chain• Solved by adaptive live patching• Capability mismatching• To be solved by a joint-effort

Exploit existing
vulnerabilities to gain root

Vendor cooperation & preembedded kernel agent

Multi-stage Vetting Mechanism
Vendor qualification
Patch security vetting
Reputation ranking

Agenda• The Problem• Android Kernel Vulnerability Landscape• Why Are They Long-lasting?
• Case Studies• The Solution• AdaptKpatch: Adaptive Kernel Live Patching• LuaKpatch: More Flexibility, Yet More Constraint• The Future• Establishing the Ecosystem

We need a patching mechanism• powerful enough to block most threats;• agile enough for quick patch generation;• yet restrictive enough to confine possible damages causedby the patches.

Our Solution -- LuaKpatch
Inserting a type-safe dynamic language engine (Lua)into the kernel to execute patches• Easy to update• Naturally jailed in the language VM• No need to worry about memory overflow etc. of the patches

Arguments

External
Inputsmalicious input

malicious input

Arguments

Arguments
External
InputsExternal
Inputspwned
normalcontrolflow

normalcontrolflow

By hooking the data input entries and validating the input,
we can block most of the kernel exploits.

So we have the following restrictions
1) The patch can hook a target function’s entry;
2) In combination with 1), within the target function, the patch canhook the invoking point or returning point of functions that return astatus code (e.g., copy_from_user);3) The patch can read anything that can be read (registers, stacks,heaps, code, etc., as long as it does not trigger faults), but cannot
modify original kernel memory (no write, and no data can be sentout);4) After judging whether the input is malicious or not, the patch canreturn specific error codes.

1: fun(...) {2:// entry of A can be hooked
3:bool result;4:
struct *s;
5:6:// foo is allowed to be hooked
7:
result = foo(...);
8:
if (result == E_INVALID)
9:
return;10:11:// bar cannot be hooked
12:s = bar(...);13:
if (s)
14:
s->fun();
15: }A running example to illustrate which functions can be hooked and which cannotImplementation of LuaKpatch• Many practices followed from the lunatik-ng project.
• Line-of-Code (LoC) is ~11K. 600 LoC are the core patching logic.
• Compiled as a 800KB kernel module.
• Capability interfaces:o Symbol searchingo Hookingo Typed readingo Thread info fetchingSample Lua patch to fix one of the vulnerable conditions of CVE-2014-3153, known as “Towelroot”

Efficacy Evaluation
CVE-2012-4220
CVE-2012-4221
CVE-2012-4222
CVE-2013-1763
CVE-2013-2094
CVE-2013-2596
CVE-2013-2597

CVE-2013-6123
CVE-2013-6282
CVE-2014-3153
CVE-2014-4321
CVE-2014-4322
CVE-2015-0569
CVE-2015-1805

CVE-2015-3636
CVE-2015-6619
CVE-2015-6640
CVE-2016-0728
CVE-2016-0774
CVE-2016-0802
CVE-2016-2468

CVEs verified to be protectable by LuaKpatch.
Most are Type I vulnerabilities (those that can be patched by simply hooking the entry of thevulnerable functions), but the highlighted/colored ones are Type II vulnerabilities (those that
also need to hook the invocations that return status code).

Efficacy Evaluation
Type II
5
Type I16

All 21 CVEs can be patched by LuaKpatch. 16 are Type I, and 5 are Type II.
So 76% of them can be easily fixed by hooking and checking input at the function entry.

Example I (CVE-2013-1763)

LuaKpatch can patch it by hooking the entry of the __sock_diag_rcv_msg function, getting thenlh argument, obtaining req from nlh, and then checking whether the condition req>sdiag_family >= AF_MAX is satisfied. If this is true, it is an exploit condition and the patch
should return an error.

Example II (CVE-2013-6123)

LuaKpatch can patch it by hooking the returning point of the copy_from_user invoked by
msm_ioctl_server to check the exploit condition.

Demo
Before Patch: Vulnerable to Towelroot and Ping Pong Root
After Patch: Immune to Towelroot and Ping Pong Root

Performance Evaluation
CF-Bench Performance Score
20000
18000
16000
14000
12000
10000
8000
6000
4000
2000
0

17473.25

17551.75

17521.4

17482

NormalPatched (Towelroot)

Patched (Ping PongRoot)Patched (bothvulnerabilities)

Execution Time of chmod (Microseconds)
120
100

100.7µs+0.42µs+0.98µs+0.82µs+3.74µs

No patch

Patched with adirect return

Patched with aconditional
comparison

Patched with amemory read

Patched with mixed
operations

80
60
40
200

LuaKpatch validation check adds an overhead under 4 microseconds,
only 4% of a chmod system call.
Because system calls are not invoked all the time, the impact to theoverall system performance should be even less.
• When a user normally browses Internet using Chrome on Nexus 5 +Android 4.4, gettimeofday was the mostly-called system call,triggered for ~110,000 times. The overall performance overhead canbe estimated as 5µs*110,000/1min » 0.9%, which is quite small.

As an ongoing work, we are migrating LuaKpatch to LuaJIT, whichshould further improve the performance.

Agenda• The Problem• Android Kernel Vulnerability Landscape• Why Are They Long-lasting?
• Case Studies• The Solution• AdaptKpatch: Adaptive Kernel Live Patching• LuaKpatch: More Flexibility, Yet More Constraint• The Future• Establishing the Ecosystem

The patching circle in the open collaborative patching ecosystem

Let’s fight the bad together!
• The number and the complexity of kernel vulnerabilities keepincreasing, so more joint effort makes it easier to battle against them.
• In the AdaptKpatch scheme, patches can be vetted and crossvalidated by qualified alliance members.
• Last but most importantly, all vendors can join together to develop apatching standard instead of implementing different variants. Ifdifferent hot patching mechanisms exist, it introduces another layerof fragmentation.

Thanks!
Yulong Zhang, Yue Chen, Chenfu Bao, Liangzhao Xia,Longri Zheng, Yongqiang Lu, Lenx Wei
Baidu X-Lab
August 2016