KEYSTONE: Next Generation Assembler Framework
www.keystone-engine.org

NGUYEN Anh Quynh <aquynh -at- gmail.com>

Blackhat USA - August 4th, 2016

1 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

BioNguyen Anh Quynh (aquynh -at- gmail.com)
Nanyang Technological University, Singapore
Researcher with a PhD in Computer Science
I Operating System, Virtual Machine, Binary analysis, etc
I Capstone disassembler: http://capstone-engine.org
I Unicorn emulator: http://unicorn-engine.org
I Keystone assembler: http://keystone-engine.org
II

2 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler FrameworkCapstone: Next Generation Disassembler Engine
Blackhat USA 2014

3 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Unicorn: Next Generation CPU Emulator
Blackhat USA 2015

4 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Fundamental frameworks for Reverse Engineering

5 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Fundamental frameworks for Reverse Engineering

6 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler FrameworkAssembler framework
Definition
Compile assembly instructions & returns encoding as sequence ofbytesI

Ex: inc EAX → 40

May support high-level concepts such as macro, function, etc
Framework to build apps on top of itApplications
Dynamic machine code generationII

7 / 47Binary rewrite
Binary searching

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Internals of assembler engine

Given assembly input code
Parse assembly instructions into separate statements
Parse each statement into different types
II

Label, macro, directive, etc
Instruction: menemonic + operands
FF

8 / 47

Emit machine code accordingly
Instruction-Set-Architecture manual referenced is needed

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Challenges of building assembler

Huge amount of works for the core only!
Good understanding of CPU encoding
Good understanding of instruction set
Keep up with frequently updated instruction extensions.

9 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Good assembler framework?

True framework
I

Embedded into tool without resorting to external process

Multi-arch
I

X86, Arm, Arm64, Mips, PowerPC, Sparc, etc

Multi-platformI*nix, Windows, Android, iOS, etc

UpdatedI

Keep up with latest CPU extensions

Bindings
I

10 / 47

Python, Ruby, Go, NodeJS, etc

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Existing assembler frameworks

Nothing is up to our standard, even in 2016!
Yasm: X86 only, no longer updatedIntel XED: X86 only, miss many instructions & closed-source
I Other important archs: Arm, Arm64, Mips, PPC, Sparc, etc?
II11 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Life without assembler frameworks?

People are very much struggling for years!
Use existing assembler tool to compile assembly from fileCall linker to link generated object file
I Use executable parser (ELF) to parse resulted file for final encoding
II

Ugly and inefficient
Little control on the internal process & output
Cross-platform support is very poor

12 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Dream a good assembler

Multi-architectures
IArm, Arm64, Mips, PowerPC, Sparc, X86 (+X86_64) + more

Multi-platform: *nix, Windows, Android, iOS, etc
Updated: latest extensions of all hardware architectures
Independent with multiple bindingsII

13 / 47

Low-level framework to support all kind of OS and tools
Core in C++, with API in pure C, and support multiple binding
languages

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Problems

No reasonable assembler framework even in 2016!
Apparently nobody wants to fix the issues
No light at the end of the dark tunnel
Until Keystone was born!

14 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Timeline

Indiegogo campaign started on March 17th, 2016 (for 3 weeks)I

99 contributors, 4 project sponsors

Beta code released to beta testers on April 30th, 2016
I

Only Python binding available at this time

Version 0.9 released on May 31st, 2016
I

More bindings by beta testers: NodeJS, Ruby, Go & Rust

Version 0.9.1 released on July 27th, 2016I

15 / 47

2 more bindings: Haskell & OCaml

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler FrameworkKeystone == Next Generation Assembler Framework

16 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Challenges to build Keystone

Huge amount of works!
Too many hardware architectures
Too many instructions
Limited resourceI

17 / 47

Started as a personal project

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler FrameworkKeystone design & implementation

18 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Ambitions & ideas

Have all features in months, not years!
Stand on the shoulders of the giants at the initial phase.
Open source project to get community involved & contributed.
Idea: LLVM!

19 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Introduction on LLVM

LLVM projectOpen source project on compiler: http://llvm.org
Huge community & highly active
Backed by many major players: AMD, Apple, Google, Intel, IBM,ARM, Imgtec, Nvidia, Qualcomm, Samsung, etc.
Multi-arch
I

X86, Arm, Arm64, Mips, PowerPC, Sparc, Hexagon, SystemZ, etc

Multi-platformI

20 / 47

Native compile on Windows, Linux, macOS, BSD, Android, iOS, etc

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler FrameworkLLVM’s Machine Code (MC) layerCore layer of LLVM to integrate compiler with its internal assemblers
Used by compiler, assembler, disassembler, debugger & JIT compilers
Centralize with a big table of description (TableGen) of machine
instructions
Auto generate assembler, disassembler, and code emitter fromTableGen (*.inc) - with llvm-tablegen tool.

21 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Why LLVM?

Available assembler internally in Machine Code (MC) module - forinline assembly support.
Only useable for LLVM modules, not for external code
Closely designed & implemented for LLVM
I Very actively maintained & updated by a huge community
II

Already implemented in C++, so easy to immplement Keystone coreon top
Pick up only those archs having assemblers: 8 archs for now.

22 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler FrameworkLLVM advantages
High quality code with lots of tested done using test cases
Assembler maintained by top experts of each archs
X86: maintained by Intel (arch creator).
Arm+Arm64: maintained by Arm & Apple (arch creator & Arm64’s
device maker).
I Hexagon: maintained by Qualcomm (arch creator)
I Mips: maintained by Imgtec (arch creator)
I SystemZ: maintained by IBM (arch creator)
I PPC & Sparc: maintained by highly active communityII

New instructions & bugs fixed quite frequently!
Bugs can be either reported to us, or reported to LLVM upstream,
then ported back.

23 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Are we done?

24 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Challenges to build Keystone (1)
LLVM MC is a challenge
Not just assembler, but also disassembler, Bitcode, InstPrinter, Linker
Optimization, etc
LLVM codebase is huge and mixed like spaghetti :-(Keystone job
Keep only assembler code & remove everything else unrelated
Rewrites some components but keep AsmParser, CodeEmitter &AsmBackend code intact (so easy to sync with LLVM in future)
Keep all the code in C++ to ease the job (unlike Capstone)II

25 / 47

No need to rewrite complicated parsers
No need to fork llvm-tblgen

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Decide where to make the cut
Where to make the cut?
II

Cut too little result in keeping lots of redundant code
Cut too much would change the code structure, making it hard to syncwith upstream.

Optimal design for Keystone
I26 / 47

Take the assembler core & make minimal changes

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Challenges to build Keystone (2)Multiple binaries
LLVM compiled into multiple libraries
Supported libs
ParserI TableGen
I etc
II

Keystone needs to be a single library

Keystone job
Modify linking setup to generate a single libraryII

27 / 47

libkeystone.[so, dylib] + libkeystone.a
keystone.dll + keystone.lib

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Challenges to build Keystone (3)Code generated MC Assembler is only for linking
Relocation object code generated for linking in the final code
generation phase of compiler
IEx on X86: inc [_var1] → 0xff, 0x04, 0x25, A, A, A, A

Keystone job
Make fixup phase to detect & report missing symbols
Propagate this error back to the top level API ks_asm()

28 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Challenges to build Keystone (4)Unaware of relative branch targets
Ex on ARM: blx 0x86535200 → 0x35, 0xf1, 0x00, 0xe1

Keystone job
ks_asm() allows to specify address of first instruction
Change the core to retain address for each statement
Find all relative branch instruction to fix the encoding according tocurrent & target address.

29 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Challenges to build Keystone (5)Give up when failing to handle craft input
Ex on X86: vaddpd zmm1, zmm1, zmm1, x → "this is not an
immediate"
Returned llvm_unreachable() on input it cannot handle

Keystone job
Fix all exits & propagate errors back to ks_asm()
II

30 / 47

Parse phase
Code emit phase

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Challenges to build Keystone (6)Other issues
LLVM does not support non-LLVM syntax
IWe want other syntaxes like Nasm, Masm, etc

Bindings must be built from scratch
Keep up with upstream code once forking LLVM to maitain ourselves

Keystone job
Extend X86 parser for new syntaxes: Nasm, Masm, etc
Built Python binding myself
Extra bindings came later, by community: NodeJS, Ruby, Go, Rust,Haskell & OCaml
Keep syncing with LLVM upstream for important changes & bug-fixes

31 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler FrameworkKeystone flow

32 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler FrameworkKeystone vs LLVM
Forked LLVM, but go far beyond it
Independent & truly a framework
IDo not give up on bad-formed assembly

Aware of current code position (for relative branches)
Much more compact in size, lightweight in memory
Thread-safe with multiple architectures supported in a single binaryMore flexible: support X86 Nasm syntax
Support undocumented instructions: X86
Provide bindings (Python, NodeJS, Ruby, Go, Rust, Haskell, OCaml asof August 2016)33 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Write applications with Keystone

34 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Introduce Keystone API

Clean/simple/lightweight/intuitive architecture-neutral API.
Core implemented in C++, but API provided in C
open & close Keystone instancecustomize runtime instance (allow to change assembly syntax, etc)
I assemble input code
I memory management: free allocated memory
II

Python/NodeJS/Ruby/Go/Rust/Haskell/OCaml bindings built aroundthe core

35 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Sample code in C

36 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Sample code in Python

37 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Demo38 / 47

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler FrameworkKeypatch plugin for IDA
Open source IDA plugin https://keystone-engine.org/keypatch
Tool for assembling & patching in IDACo-developed with Thanh Nguyen (VNSecurity.net)

39 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Other applications from around internet
Radare2: Unix-like reverse engineering framework and commandline
tools
Pwnypack: CTF toolkit with Shellcode generator
Ropper: Rop gadget and binary information tool
GEF: GDB plugin with enhanced features
Usercorn: Versatile kernel+system+userspace emulator
X64dbg: An open-source x64/x32 debugger for windows
Liberation: code injection library for iOS
Demovfuscator: Deobfuscator for movfuscated binaries.
More from http://keystone-engine.org/showcase

40 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Status & future works
StatusVersion 0.9 went public on May 31st, 2016
Version 0.9.1 was out on July 27th, 2016
Based on LLVM 3.9
Version 1.0 will be released as soon as all important bugs get fixed

Future works
More refined error code returned by parser?
Find & fix all the corner cases where crafted input cause the core exit
More bindings promised by community!
Synchronize with latest LLVM version
I41 / 47

Future of Keystone is guaranteed by LLVM active development!

NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Reverse Engineering Trilogy

42 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework

Conclusions

Keystone is an innovative next generation assembler
Multi-arch + multi-platform
Clean/simple/lightweight/intuitive architecture-neutral API
I Implemented in C++, with API in C language & multiple bindings
available
I Thread-safe by design
I Open source in dual license
I Future update guaranteed for all architectures
II

We are seriously committed to this project to make it the bestassembler engine

43 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework44 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler FrameworkReferences

Keystone assembler
Homepage: http://keystone-engine.org
Twitter: @keystone_engine
I Github: http://github.com/keystone-engine/keystone
I Mailing list: http://freelists.org/list/keystone-engine
II

Keypatch: http://keystone-engine.org/keypatch
Available apps using Keystone:
http://keystone-engine.org/showcase
Capstone disassembler: http://capstone-engine.org
Unicorn emulator: http://unicorn-engine.org

45 / 47NGUYEN Anh QuynhKEYSTONE: Next Generation Assembler FrameworkAcknowledgement

FX for the inspiration of the Keystone name!
Indiegogo contributors for amazing financial support!
Code contributors!
Community for great encouragement!

46 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler FrameworkQuestions and answers
KEYSTONE: next generation assembler engine
http://keystone-engine.org
NGUYEN Anh Quynh <aquynh -at- gmail.com>

47 / 47NGUYEN Anh Quynh

KEYSTONE: Next Generation Assembler Framework