Keystone: the last missing framework of Reverse Engineering
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Part Number | 16 | |
| Number of Parts | 20 | |
| Author | ||
| License | CC Attribution 4.0 International: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/32749 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
REcon 201616 / 20
3
5
6
9
10
13
15
17
20
00:00
Binary codeSet (mathematics)Condition numberSoftware frameworkMultiplication signOntologyWebsiteReverse engineeringOpen sourceJSONXMLUMLComputer animation
00:55
Similarity (geometry)Coordinate systemComputer architectureOrder (biology)Dynamical systemEvent horizonBinary codeWeb crawlerForm (programming)MaizeCategory of beingBitProcess (computing)Statement (computer science)Service (economics)Software frameworkFunctional (mathematics)System callRule of inferenceAssembly languageSpeciesMultiplication signWindowVirtual machineSpacetimeProjective planeKeyboard shortcutDifferent (Kate Ryan album)WordPartition (number theory)Data managementSlide ruleoutputExpert systemDampingAmenable groupDefault (computer science)Term (mathematics)TheoryReal numberInjektivitätCharge carrierPhase transitionCartesian coordinate systemBefehlsprozessorSemiconductor memoryLibrary (computing)CuboidObject (grammar)Water vaporOperator (mathematics)Goodness of fitSequenceSet (mathematics)Codierung <Programmierung>Focus (optics)EmulatorImplementationVirtualizationMultiplicationDemo (music)Run time (program lifecycle phase)Standard deviationComputer fileBounded variationFunction (mathematics)Machine codeCompilation albumProper mapDisassemblerLinker (computing)Computer animation
08:59
Machine codeWindowKeyboard shortcutFront and back endsSoftware frameworkComputing platformGoodness of fitCore dumpTable (information)Connectivity (graph theory)CuboidOpen sourceGame controllerComputer fileLine (geometry)Descriptive statisticsDecision theoryBefehlsprozessorRevision controlAssembly languageBuildingSoftware testingSource codeProgrammer (hardware)Computer architectureMultiplicationCross-platformPhysical systemArmInjektivitätProjective planeSoftware bugMultiplication signVideo gameLinker (computing)MereologyDampingCompilerDifferent (Kate Ryan album)FrequencyWater vaporView (database)Einbettung <Mathematik>DisassemblerState observerFlow separationOperator (mathematics)Social classModel-driven engineeringProcess (computing)1 (number)AreaExtension (kinesiology)Limit (category theory)Standard deviationTraffic reportingPosition operatorGroup actionQuicksortUniverse (mathematics)BitMaizeFocus (optics)FreewareoutputLattice (order)Degree (graph theory)Rule of inferenceField (computer science)Event horizonDisk read-and-write headSystem callPersonal digital assistantComputer animation
17:02
Machine codePolygon meshGastropod shellExtension (kinesiology)Keyboard shortcutSoftware bugJava appletSynchronizationMathematicsSemiconductor memoryMultiplication signBranch (computer science)Slide ruleRevision controlContext awarenessOcean currentInjektivitätoutputTheory of relativityAssembly languageSystem callDistanceComputer architectureSource codeCodierung <Programmierung>Ferry CorstenNumberError messageLevel (video gaming)Table (information)Library (computing)Dynamical systemFluid staticsWindowShared memoryObject (grammar)Phase transitionLinker (computing)Film editingConnectivity (graph theory)Function (mathematics)Symbol tableReading (process)RewritingDemo (music)Mathematical optimization32-bitRepresentation (politics)DataflowPropagatorInterface (computing)Arrow of timeMereologySurfaceArithmetic progressionRule of inferenceStatement (computer science)Software developerWater vaporLink (knot theory)Logic synthesisLine (geometry)Sparse matrixExpert systemCategory of being1 (number)Uniform resource locatorExpressionLogical constantSoftware frameworkSelectivity (electronic)Relative riskPosition operatorSubject indexingGroup actionView (database)Computer animation
25:05
InjektivitätFunction (mathematics)Goodness of fitView (database)Functional (mathematics)Revision controlOperator (mathematics)Traffic reportingDemo (music)BuildingComputer architectureSource codeComputer animation
26:10
Demo (music)Power (physics)Right anglePoint (geometry)Source codeComputer animationJSON
27:26
Single-precision floating-point formatRobotAsynchronous Transfer ModeEmulatorInterface (computing)BefehlsprozessorBinary codeOpen sourceComputing platformDemo (music)Cellular automatonSimilarity (geometry)StatisticsHeat transferCuboidForceINTEGRALCharge carrierPressureContext awarenessSequenceComputer animation
29:19
Binary codeComputer clusterAssembly languageSoftware frameworkMultiplication signOpen sourceDifferent (Kate Ryan album)Keyboard shortcutPhysical systemComplete metric spaceSoftware bugFunctional (mathematics)Goodness of fitDisassemblerEstimatorOrder (biology)Shared memoryDistanceData managementSet (mathematics)Similarity (geometry)Computer animation
Transcript: English(auto-generated)
00:26
for the next talk. This one is on the Keystone Assembler framework. OK. OK, so welcome to my talk. And this one's about Keystone, the last missing framework for reversing. Actually, the title is just to catch your attention,
00:41
so don't dig too much into that. And Keystone was already released with all the source code, binary package, and documentation as well as Keystone engine.org. You can get that from the website. OK, so my name is Guilin Quing. And I have some background in academia.
01:04
And my main research focus on operating system, virtual machine, binary assist, and all those low-level stuff. And I happen to be the founder of a few frameworks, Capstone Disassembler, Unicorn Emulator, and Keystone Assembler.
01:22
So that's the question. Anybody here use any of those frameworks? Thank you. OK, so in this talk, I will introduce a bit on the background of the Assembler frameworks and their issues. And next, I introduce the motivation
01:44
behind Keystone projects and how Keystone was designed and implemented. And there are a few demos if you have enough time. OK, so all the reversing tools are based on some fundamental variations. One of them is disassembler.
02:02
The second one is CPU emulator, right? So what is missing here? So we look at the picture again. You see that disassembler, given the input as a binary, return the injection in assembly. You get the same binary to emulator, run the injection,
02:23
and tell you how the CPU is affected. So the question here is, where is the binary coming from? And the answer is that mostly, the binary comes from some assembly injection, and you need to compile that to get a binary.
02:43
So the missing pieces in this picture is the assembler. So you can see that with an assembler, you can compile assembly injection, get back the binary, and you can feed the binary to either disassembler or CPU emulator.
03:03
So assembler is something very simple. It compiles the assembly injection for you and returns the encoding. Usually, it's a sequence of bytes. First of all, on x86, if you compile inc.ex, it returns you one byte, which is 40.
03:20
And the CPU can understand this byte 40, yes? Something that increases the EX register by one. And here we focus on framework, not just assembler tool. So framework is something that, more or less, library, which you can embed in your tools and build your application on top of the framework.
03:43
So assembler has many, has some important application, and the most important one is dynamic, dynamic machine code generation. So you can compile, run time the assembly injection and get back the binary.
04:00
And usually you use assembler for something like binary UI, binary searching. So on the assembly engine function, in the same way, inside. So basically, you keep the assembler one or few instruction, it pass the input
04:21
into many statements. And for each statement, the assembler will handle it differently, it can be understand as a label, macros, directive, and so on. For the injection, assembler will pass it into the memory and operands, and after that it emit machine code,
04:41
accordingly, to the output from the last phase. And here you need to understand the CPU injection made very well to do this one, to emit machine code properly.
05:02
So now what you need to do if you want to build one assembler from scratch? So the answer is a huge box. You need to have good understanding on CPU encoding. You need to understand all the instruction in the instruction set of CPU. And lastly, you need to keep up with the
05:25
updates from the CPU vendor, because the CPU vendor frequently introduce new injection. So it's not easy work. So what is a good assembler framework?
05:42
So here's my definition for a good assembler framework. First one is must be a true framework, which means it allow you to embed a framework into your tool, without having to call an external process. It should support multiple architectures, so support XSX, ARM, MCT4, MUSE, PowerCPC, Spark,
06:03
all those important and popular architectures. It should be multiple platforms, which means it should work on own-cap OS, Windows, Linux, Mac, Android, iOS, and so on. It should be updated. It should support latest injection on all those CPUs. And finally, it should have bindings,
06:22
because usually people build tools using bindings, high-level languages, like Python, Ruby, Go, JavaScript, and so on. Unfortunately, so far, even in 2016, there's nothing up to my standard.
06:43
So a few frameworks, like YASMA, which only support XSX and nothing else. It's no longer updated. There's something from Intel, named Intel Set, which has the same issues. It only supports X86 and nothing else.
07:02
It comes from Intel, but Set actually missed many injections, and it's closed, so it cannot fix back inside. You cannot understand what happens inside when you use it. And finally, there's no framework for all other important architectures.
07:23
ARM, MCT4, MUSE, PowerCPC, Spark. We have nothing for those CPUs. So it's our proper framework. People shackled for years and forever.
07:42
And because there's no framework, they need to build your tools by executing one external process, for example, NASM or GNU gas from GNU. And the way they do is that they fit the assembly code,
08:00
okay, they write the assembly code into one file, and they fit that file into the external tools, let it run. After that, they get the object code. And again, they need to call a linker to link the object code to final files. And lastly, they need to do some,
08:22
need to pass the first of year file to get out the instructions inside. So you can see that it's a lot of work, and it's ugly, and it's inefficient. The reason is that you need to call external process. So you consume memory, performance is bad,
08:42
and it's not always work first of all. What if you want to do assembly from inside the kernel? It's not a way to call back to the user space, right? For the process inside user space. Not nice thing to do. And because you need to call external process,
09:03
you have written control on the external process, and on the output, you don't know what happened inside. And of course, platform support is very poor for all those external tools like NASM or GNU gas. GNU gas doesn't go very well on Windows.
09:21
It's very hard to compile and to build that on Windows. So I want a good disassembler, support multiple architectures, multiple platform, always updated and independent, so you can view your tools independently using this framework.
09:43
So because it seems that if I just sit down and waited for somebody to do this for me, so it will be forever. So because I had so much fun with Capstone and Unicorn, I decided to step up and design again.
10:01
So that's how Keystone was born. So I started the Indigo campaign for Keystone in March, and thanks to community, a lot of people contributed. And I released a beta code to some beta tester at the end of April. At that time, I had only Python, Python binding.
10:24
And at the end of May, I released the first version to the public, and the beta tester contributed a lot. They helped to build a few more bindings. So we have bindings for Node.js, for Ruby, for Go and for Rust, and Haskell recently.
10:42
So totally, we have six bindings for Keystone now. Okay, so next part is the ideas behind Keystone, how it's designed and implemented. Okay, so we want something, multiple architecture,
11:02
multiple platform updated, and of course, in C or C++, but the API should be in POC and support multiple bindings on top of that. The issue is that there are huge works. You want to do this from scratch because there's too many architectures,
11:20
too many instruction. Intel alone has like 1,500 instructions. So that's a lot. It has very limited resource because I started this on a personal project, and I did this for fun only. So my idea is that I do not want to spend
11:42
a lot of time on this, to design, to implement, to maintain it. I want to have own features in months, not years, because you want everything, you want to do everything from scratch, it takes years of your life. So the only way is to stand on the shoulder of the giants at an innocent face, and after that,
12:02
release a source code to community so people can help to contribute and to maintain it. So the idea that I built Keystone on LVM. LVM is one open source project on compiler.
12:21
It has huge communities and very active, and it's backed by many big companies, big CPU vendors, like AMD, Apple, Google, Intel, IBM, AMG Tech, NVIDIA, Qualcomm, and so on. LVM support own kind of architectures,
12:41
all the important ones, and it's multi-platform. It's run on own kind of platform, own kind of OS. So it's good. So here's a overview of the LVM architecture, which is focused on compiler. So the most important part inside LVM
13:01
is something called machine code, or MC, which is a component inside the yellow box here. MC is something that is a core of the LVM, which everything else built around it. Compiler, assembler, disassembler, debugger, just-in-time compiler, everything is built around MC.
13:21
And the central MC is a big table description named TableGen that describe all the machine instructions. And they have to name LVM TableGen to generate included file for LVM from those TableGen files.
13:45
So the reason I choose LVM to build Keystone because LVM is an assembler framework, right? So it should support it in line assembly for compilers, which means it already has assembler inside MC component.
14:01
But keep in mind that MC is only built and usable for LVM and nothing else. It's closely designed, implemented only for LVM, not for external process, not for external tools. And MC is very highly active, maintained and updated by community, by all those big CPU vendors.
14:23
LVM is already built in C++, so it's easy to build Keystone on top of that. And to build Keystone, I just focus on those, those has, those architectures have assemblers. And Keystone support eight architectures so far.
14:44
So the advantage of using LVM to build Keystone is that the code has very high quality, done by very good professional programmers. And it's the assembler inside LVM is actively maintained by all the CPU vendors.
15:00
Like x86, assembler is maintained by Intel, who's better than them. ARM and MCCV are built and maintained by ARM and Apple. Hexagon, maintained by Qualcomm. MIPS, maintained by IMG Tech, which is a vendor making the MIPS CPU. System Z, maintained by EM,
15:21
also the CPU vendor System Z. PowerPC and Spark, maintained by community, but they are very active on that. So new injection is frequently added and bug fix, bugs are very fixed, very easily, very quickly. So because we build Keystone on top of LVM, the bugs can be either reported to us
15:41
or reported to LVM upstream, so you can port it back later. So two things easy to build Keystone, because we can just fork from LVM. It's not because there's a lot of works.
16:02
So the first challenge to build Keystone is that the MC component of LVM is not assembler, but include many thing inside. It has disassembler, it has bit code, it has instruction printer, it's a linker inside, and the code is huge and mixed like spaghetti.
16:21
So what I did is that I keep only assembler code of MC and remove everything else that's not related. And I rewrote some components, but I tried to keep the puncture, the code emitter, and the assembly backend intact, because I want to keep synchronized with LVM
16:42
when they update those components. So I tried to keep them by chance as little as possible. And this one important decision. I keep all the code in C++, but I did not rewrite them to C. It's different from Capstone. So in Capstone disassembler,
17:02
I rewrote all the C++ code to C, POC, and it took a lot of time. But this time I tried to keep everything in C++, so I did not have to spend time to rewrite them, and it's also easier to maintain and update it when LVM is updated.
17:21
So I had to decide to make the cut for MC, because MC has many different components inside. So I made a cut so it take out only what I need. So the question is why to make the cut? Because if you cut too little, you keep many things you don't really need inside. You cut too much,
17:41
you end up changing some code, or a lot of code inside Capstone, and that make it very hard to synchronize with LVM in the future. So it took a lot of time to read source code LVM, and I think I finally have optimal design for Capstone. I take the cut so that's enough,
18:03
and make very minimal change to MC. So it's a key flow of Capstone, we have paxa, paxa will fit the injection representation to code emitter, code emitter will emit the code,
18:21
and finally we have something like linker to link on the output from code emitter, and finally we have the output. So second challenge to build Capstone is that LVM compile is binary to multiple libraries.
18:40
So it has separate libraries for supported components, library for paxa, library for table gen and so on. But what it is that we need only a single library that include everything inside. So what I need is that I need to modify the linking setup for LVM to generate a single library. So we have lib Capstone.show.dilib
19:01
for dynamic share library, or Capstone.dilib for Windows, lib Capstone.a for static library, or Capstone.lib for Windows. So next challenge is, code generated by MC is only for linking, not the final code that you want.
19:20
So they build the relocation object code, and the code is generated for the next phase in LVM for the linker. So first of all, it will compile ink, as a red injection. You return something like FF, 04, 25, and something unknown here, beside that, after that. Because the assembler doesn't really know what to put there.
19:44
It doesn't know where that one is. So only the linker at the next phase knows that. But kids don't need to know because we just want to compile to get the final output. So what I did here is I make some, I fixed something,
20:00
so I can detect and report the missing symbol. So if that one is not available, it's missing. I report that this one is missing, and the assembly input is not correct. So next challenge is, LVM is, the assembler inside MC is not aware
20:22
of relative branch taggers. First of all, on AMP, you compile BOX, and the taggers, it will return something like that. Just from LVM. But actually, this one's wrong because this injection depends on where you are,
20:40
where you positioned this injection. So it depends on the distance between your place and the target. So what I did to fix it is to have the API, KS asthma, to have it allowed to specify the arrest of the injection.
21:03
And I changed the call of the MC, so it retained the arrest for every statement. And I find all the relative branch injection in all the architectures and fixed all of them, so the encoding is probably according to the current and the target arrest.
21:23
Another challenge to build Keystone is that LVM usually keep up and it cannot handle the input. So first of all, the red injection is something wrong because the last one should be some constant,
21:40
some invalid number. So if you fit the red injection to LVM, it didn't tell you that this is not an invalid and it exit immediately. So this is a huge problem because Keystone is framework, right? It should not exit. It's not quit and it cannot handle the input.
22:03
So actually this is hugely, it's a lot of works. I need to find, fix all the exit like that and I propagate the errors back to the top level API. So the exit can be happening. Any faces in the flow, it can be in boxer, it can be in the co-emitter,
22:20
it can be even in the linker, it's final face. So fixing this took a lot of time. There's issues. LVM doesn't support non-LVM syntax. It only support LVM syntax, but you want other syntaxes like NASM or MOSMOS and so on. LVM has no binding at all.
22:43
And keep up with upstream code because LVM is reactive and it updated the code very, very frequently. So keep up with this change from LVM is a lot of works. So what I did is that I need to extend it. I need to extend LVM and X86 boxer
23:01
so we can support new syntax. I view Python binding mesh shell before the beta phase. And after that, community help to view more bindings for Java C, for Node.js, for Ruby, Go, Rust, and Haskell. And at the moment, I still need to keep thinking,
23:22
synchronize with LVM when they have the important update, important bug fixes, so Keystone can get all those bug fixes and all those important changes. So you can say that because Keystone is built on LVM, it is the same thing, but actually it's not.
23:45
So I will say that LVM and Keystone is built on LVM, it can do a lot more. Keystone is an independent framework, a true framework, not like LVM, it's more like a tool than a framework. It's aware of current code position,
24:03
so Keystone can probably encode the really deep branch. Keystone is much smaller in size and much smaller in memory consumption. It's like 10 times smaller than LVM because Keystone removes everything that it doesn't need. It's thread-safe, it's more flexible,
24:23
it supports some uncommented instruction for XTC, and it has many bindings. Okay, so I have a few slides to introduce how to write a version inside Keystone,
24:41
which is very easy. So we take a look at the slides. Here's a fresh shippon in Python. You define the code here. You set up the engine. This one is for XTC, 32-bit. After that, you compile the code. You get back the encoding and how many injection.
25:02
And that's it, it's really simple. So here's the demo. So on the left side, you see the code, right? On the right side, I only run that code, and this is the output.
25:21
So two injection has two bytes. Okay, and a few demos. Sorry, I still have a very written terms. Okay, this one, cool demo. So somebody views a tool named PonyPak using Keystone.
25:42
So the idea is that PonyPak has many things, but here it has one function, allow you to view shellcode. So you can describe the high-level operation of the shellcode, and you can translate, internally PonyPak translate all the operation into low-level assembly. And it use Keystone to view the shellcode for you.
26:03
And because Keystone support all kind of architectures, the shellcode build support all kind of architecture that the Keystone support. So here's the demo.
26:26
Okay, so something import, or Python import Pony. And then you specify that you want Linux shellcode, right?
26:43
For AMP. And you compile the shellcode, very simple shellcode. And you return the AMP shellcode, right? If you do the same thing,
27:00
but you initialize the not AMP shellcode, but x86 shellcode, you compile the same shellcode again, and you get back to the x86 shellcode. So you can see the power of Keystone. It support all kind of architecture, so the same shellcode can be combined to whatever you want.
27:27
Another fun demo. Sounds fun. Same old one, open source emulator. It's my favorite one because it combine all my frameworks, we combine Capstone, Indicon, and Keystone.
27:43
So what it does is, okay, you see the interface here. You enter the assembly instruction in the box, and you press one button here.
28:01
You can run all the code, or you run every instruction in single step mode. And at every step, you get back the CPU context, you get back the memory, you can see how every instruction is changed. So how it works internally. Here, if you enter assembly into the left box,
28:23
same old way, compile those assembly using Keystone, and it get back the binary, right? And it feed the binary into the Indicon emulator, and the emulator can run those binaries and tell you how the CPU is affected at every step.
28:41
So it's very nice tool. I think it's very good tool for education. So you know how instruction from all those CPU works. And you can see that because it use Keystone and Indicon, so it should work on all the platform. So this one is like, you run on x86, but you can still emulate AMP instruction,
29:03
AMP 64, MIPS, and so on. So what's next now? Oh, this one support. Nice one. This morning, you found it. So somebody wrote a bot for Telegram, so we send instruction to the bot, and it compile, return back the binary.
29:25
And there are bunch of tools built on Keystone now. You can see that from the website, Keystone is the sole case, all kind of different things, co-injection, rope gadget, and so on.
29:43
So conclusion. Keystone is the next generation assembler frameworks, support on-cap CPU, multi-platforms, reshape on a clean API, easy to use, easy to be your tools, open source. And future app-based is connected because it's used on LVM.
30:03
So whenever LVM is something, update something, I can put it back to Keystone support. And you saw that we are seriously committed to Keystone project, and we want to make it the best assembler engine for our community.
30:21
Okay, so here's the full picture, the final picture. So we have Capstone assembler, disassembler, the InuKorn emulator, we have Keystone assembler. And all of them are open source, multi-platform, multi-architectures, with many bindings. And they function independently,
30:41
but they complement each other very well to make a complete set of frameworks. So we call it a reverse, reversing Chiro-Z. Okay, so I bring bunch of stickers to Recon, but unfortunately, I still have a few sticker left. So if anybody here wants sticker,
31:00
come to see me after my talk. Okay, do you have time for questions? Thank you.