Decoding Special Machine Instruction Sequences with Ghidra

Because of the low level of development I do, I am still from time to time called upon to decode existing, or write new, sequences of just a few assembler instructions to accomplish very specialized operations. I usually do this with the relevant processor handbook laying in my virtual lap. While it is true that during my career in the 1970s and 1980s I probably wrote hundreds of thousands of lines of assembler code for various machines (I wrote my master's thesis project in PDP-11 assembler, for example), most of that was done before I had access to a C compiler.

When I started playing with Ghidra, the U.S. National Security Agency's recently open sourced software reverse engineering (SRE) tool, I was curious how its C decompiler dealt with instruction sequences that were perhaps outside of the normal idiomatic sequences it had been programmed to recognize. This was easy enough to find out: I had several examples of such sequences in my own repositories on GitHub.

This work was done with Ghidra 9.0 dated 2019-02-28.

(As usual, you can click on an image to be taken to a larger version.)

Scattergun

Scattergun is my project to evaluate hardware entropy generators. These are devices which use transistor noise or even quantum mechanical effects to generate random bits for applications like creating unguessable encryption keys.

Two of the generators I tested in Scattergun were the Intel rdrand and rdseed machine instructions. rdrand is a general purpose hardware random number generator introduced in the Intel Ivy Bridge architecture. It generates random numbers using an algorithm that is seeded, and periodically reseeded, by a hardware entropy source built into the processor. rdseed is a hardware entropy generator introduced in the Intel Broadwell architecture. It provides access directly to the hardware entropy source built into the processor.

Scattergun provides the seventool utility that can be used to generate random bits using either rdseed or rdrand to feed to the Scattergun test suite. The functions in seventool that access those instructions look like this.



There's a lot of conditional compilation here because I needed seventool to compile run on several different vintages of GNU C compiler suites. Some of them did not have assemblers that recognized the rdrand and rdseed mnemonics. Some of them had compilers that already had built-in functions to generate the appropriate instruction sequences. But for the i7-6700T processor on which I ran these Scattergun tests, I used the compilation options that used the rdrand and rdseed assembler mnemonics. These functions (which weren't actually, as it turns out, inlined by the GNU C compiler) generate code to execute the appropriate machine instruction in-line, fetch the indication of success from the carry bit, and return that as the function value while saving the random goodness in a value-result parameter.

Here's what Ghidra had to say about these functions. In the first screen shot, I asked Ghidra to decompile the rdrand C function.



 You can see the RDRAND machine instruction in the center screen showing the disassembly.

I did the same for the rdseed function.



Similarly, you can see the disassembled RDSEED machine instruction in the disassembly.

Ghidra decompiled both the rdseed and rdrand instruction sequences into pseudo-function calls, both the actual machine instruction, and the check of the carry bit for success. It's pretty clear that the x86_64 instruction decode for Ghidra has been configured to recognize both of these as idiomatic machine instruction sequences. That's pretty remarkable.

Or maybe not. I probably shouldn't be surprised that the premiere encryption cracking organization on the planet is especially interested in detecting applications that use hardware features especially designed for creating encryption keys. (The fact that I was able to get to this point within about an hour of installing Ghidra might say something about the hazards of meta-analysis revealed by open sourcing tools like this.)

Diminuto

Diminuto, my C systems programming library for (mostly) Linux/GNU platforms, includes some definitions to make it easy for me to play with memory barriers: machine instruction sequences available on many architectures (not just x86_64) that enforce cache coherency on multi-core processors. The good news is that multi-core architectures have machine instructions to explicitly do this (that is, they do if they work), or at least instructions that do this as a side effect. The better news is that modern GNU C compilers have built-in pseudo-functions that generate the appropriate instruction sequences for each different architectures, making it easier to write portable code that use memory barriers.

(I confess there is a lot of "do as I say and not as I do" in the Diminuto memory barrier code, which is pretty experimental. You are for the most part much better off coding POSIX mutex operations, which use memory barriers as part of their implementation. Diminuto can help you with that, too.)

Here is a unit test program in Diminuto that calls the general memory barrier function diminuto_barrier several times. It then calls the read barrier function diminuto_acquire, and then the write barrier function diminuto_release. Interspersed are assignment operations to a volatile variable that in my naivety I had hoped would keep the compiler from optimizing them out.



A read barrier (which is said to have acquire semantics) is intended to block the execution core until its cache has been updated with the latest values from other cores. A write barrier (with release semantics) is intended to block the execution core until its cache changes have been propagated to the other cores. The general barrier does both.

Here is the implementation of all three functions.



You can see that they are all implemented as preprocessor definitions that expand to predefined GNU C functions. The __sync_synchronize function implements a general (both read and write) memory barrier. The read and write barriers are a little more complicated;  they use the GNU C __sync_lock_test_and_set and __sync_lock_release functions, not for their intended purpose as machine-level synchronization mechanisms using busy waiting (spin locks), but because they implement read and write memory barriers as a side effect.

Here is how Ghidra decodes this unit test for code compiled for the x86_64.



The disassembly in the center screen is straightforward. There are the three MFENCE instructions corresponding to the diminuto_barrier function calls that each expanded into __sync_synchronize. You can see the MOV instructions that does the variable assignment. You can see the XCHG that implements the __sync_lock_test_and_set in diminuto_acquire (there's no loop because we just want the read barrier as a side effect), and a MOV that implements the __sync_lock_release in diminuto_release.

The C decompile on the right is more problematic. Not only are none of the memory barrier operations represented in any way, but the assignment statements that were in the original C source are missing as well. In fact, the only code shown in the decompile is that which was generated in the unit test framework EXIT macro that handles the end of test processing. The entire body of the unit test is gone.

It is no more than a guess on my part, but maybe Ghidra fell into a machine instruction sequence that it didn't recognize, and rather than add a notation in the decompile it simply ignored it. The authors of Ghidra have a lot more experience using it to reverse engineer software using Ghidra than I do (which is, basically, none). But this seems unfortunate, since the use of memory barriers is a common idiom in the kinds of low level work that I do, particularly with devices that expose data registers by memory mapping them into the processor address space.

Hazer

Hazer is my project to evaluate Global Navigation Satellite System (GNSS) receivers, of which the Global Position System (GPS) receiver that may be in your mobile phone is one example. The gpstool utility in Hazer makes use of Diminuto scoped operators: operators that have an explicit begin (opening) and end (closing) syntax that correspond to underlying begin and end semantics.

One example makes use of the memory barriers we just discussed to implement the Coherent Section scoped operators.



These Coherent Section operators, when used at the beginning and ending of a section of code, automatically perform a read barrier at the beginning of the section and a write barrier at the end of the section.

Perhaps a little more typical are the Critical Section scoped operators.



The Critical Section begin operator automatically causes the application to acquire (block until it is available and then lock) a POSIX mutex passed in by the application, and the end operator automatically releases (unlocks) the mutex as the flow of control leaves.

The Hazer gpstool utility has an option to monitor the 1PPS (One Pulse Per Second) 1Hz timing signal that is generated by some GNSS receivers. One of the ways that serial-attached receivers generate this pulse is by toggling the Data Carrier Detect (DCD) control line on the serial port. gpstool uses a separate thread to follow DCD and communicate its state back to the main thread.



The dcdpoller function uses the Coherent Section scoped operators to bracket the reading of the done variable that tells the thread to exit (when, for example, the application terminates), and the more conventional Critical Section scoped operators to synchronize read-modify-write access to the oneppsp variable that it uses to inform the main thread that a 1PPS event has occurred. (The function can also optionally strobe an external GPIO pin to pass the DCD state on to another device.)

I routinely run gpstool on both x86_64 and ARM architectures. Here is the Ghidra analysis of the dcdpoller function on the x86_64.



The XCHG and MOV instructions that form the beginning and ending of the Coherent Section are clearly visible in the disassembly, but are completely absent in any form in the decompile. But at least the check of the done variable is present in the decompilation. The beginning and ending of the Critical Section, including the handling of the POSIX mutex clean up, is well represented.

Here is the Ghidra analysis of the same function compiled for the ARM.



The ARM ldrex (Load Exclusive) and strex (Store Exclusive) instructions are how the ARM implements an atomic test-and-set operation. These are visible in the disassembly where the original C code enters the Coherent Section. The lock is released when the flow of control exits the Coherent Section via (I think) conventional mov (Move) and str (Store) instructions. The decompile represents this using two successive coproc_moveto_Data_Memory_Barrier pseudo function calls. The disassembly shows that the done value is accessed inside the Coherent Section, but this isn't at all obvious from the decompile. The decompile of the Critical Section using the POSIX mutex was recognizable as being the same operation as in the x86_64 analysis, which is no surprise; it's probably the same underlying implementation, with only minor differences for architecture specific operations like spin locks.

(It occurred to me later to do a Ghidra analysis of the Diminuto memory barrier unit test compiled for the ARM instead of the x86_64. I got results consist with this Hazer analysis: the presence of many coproc_moveto_Data_Memory_Barrier pseudo function calls in the decompile, but the body of the unit test was missing except for an empty do-while-false block.) 

Update (2021-04-06): The latest Ghidra public release, 9.2.2, appears to address the issue of the missing body of the unit test in the code compiled for an ARM7 (see screenshot below).

Conclusions

I'm not an expert in either x86_64 or ARM assembler coding, but at least I was able to make my way through the disassembled listings without much drama, and with only one reference to a processor manual. The decompiled listings were useful as well, but it would have been easy to have been mislead had I not been the author of the original program being analyzed and so knew what to expect.

Ghidra is going to be my go-to tool for this kind of analysis. In fact, I can easily see using it as a static analysis tool when coding specialized instruction sequences in C or C++ to make sure I haven't botched something. I have already decided to make some changes to the few (okay, two) places in my libraries where I make use - probably inadvisedly - of Coherent Sections outside of unit tests. I probably wouldn't have figured that out without Ghidra.

Ghidra ain't perfect, but it ain't bad - I'm amazed the decompiler works at all - and the price is right.

Ghidra

The National Security Agency, the U.S. intelligence organization responsible for cracking foreign governments' encrypted communications, while at the same time trying to ensure those same state actors don't crack their own, recently open sourced a tool kit they call Ghidra: a suite of tools for software reverse engineering (SRE).

("Ghidra" is the multi-headed Toho film monster whose name is probably derived from "Hydra", the many headed serpent from Greek mythology.

Photo credit: Wikipedia

He is more commonly known in Japan as "Ghidorah". )

Ghidra is written in Java (it requires OpenJDK 11), Jython (an implementation of Python that runs on the Java Virtual Machine), and C++. It runs on 64-bit Windows, MacOS, and Linux platforms. It has a graphical user interface and includes a disassembler, and even more remarkably, a decompiler.

In order to represent a file of machine instructions as decompiled code - C code in my examples - the decompiler has to recognize idiomatic instruction sequences that are specific to a compiler - GNU C in my examples - and to a machine architecture - x86_64 and ARM in my case. To distinguish instruction sequences from data, the disassembler has to follow the logical flow of instruction execution, decoding successive instruction sequences, and following all possible transfers of control (jumps, branches, function calls) to new sequences. This forms a cyclic graph of control paths to determine exactly what bits are instructions and what bits are data, the latter being bits to which there is no flow of control. This is no mean feat.

To get you interested in plowing through the rest of this article - or maybe just jumping right to playing with Ghidra yourself - I'll start off with an example.

(You can mouse click on any of the images to open a larger and hopefully more readable version. My fu with the Blogger platform kinda sucks at rendering code samples no matter what I try.)

Here is the prototype for a function from my Diminuto library of C systems programming tools that debounces digital input signals. The application calls this function at some fixed frequency - 100Hz (every 10ms) works well for typical mechanical contact switches - and gets a 0 (unasserted) or 1 (asserted) result.



Here is its implementation. (I didn't invent this algorithm, I've just used the heck out of it. The header file for this feature lists the references from Dr. Marty and from Jack Ganssle.)



Here is what the data structure that the debouncer uses to maintain state looks like. You see that I used bit fields, something that isn't obvious from the implementation.



Bit fields aren't the greatest feature in C, mostly because the C standard doesn't specify in what order the bit fields occur, leaving that up to the implementation. That means you can't use bit fields portably. Big oops on the part of the C standards folks. But when I originally wrote this feature, it wasn't for Linux platforms, it was for tiny eight-bit PIC micro controllers, where data space was at a premium (fifty-six bytes of read-write memory on this particular firmware project). When I ported the code to Diminuto, I kept the bit fields.

Here is what Ghidra produces when analyzing this library compiled into a shared object file for a x86_64 target using GNU C.



Indices into particular sections of the object module are shown on the left. The disassembly into x86_64 machine code is shown in the center (it's long, the screen doesn't contain the entire function). The decompiled C code is shown on the right.

The C code here is particularly helpful. You can see how the bit fields are handled by logical operations on the entire integer variable. (In contrast, the Harvard-architecture PIC micro controller for which this was originally written had machine instructions to do bit-wise operations which made its executable code stored on-chip in ROM much more compact.)

Many times I've had to resort to using GNU tools like objdump, or other similar target-specific tools, to disassamble files containing machine instructions - device drivers, libraries, shared objects, executables, ROM images, what have you - typically in order to debug a problem in third-party software, or to integrate some product development effort with existing legacy software, for which I didn't have access to the original source code. (Or, in a couple of darkly humorous episodes, for which my client had lost their own original source code.)

As much of a life saver as objdump is, it is limited as to what it can disassemble, and it requires that I brush up on my assembler skills, which these days are limited to writing or decoding short instruction sequences that are embedded in C or C++ code to do specialized things like implement memory barriers or generate random bits using built-in entropy generators. It would be a lot more productive to have a tool that produces (even approximate) C code.

There are commercial tools that do this. I've seen IDA Pro, a graphical Interactive DisAssembler tool produced by Belgium-based Hex-Rays, in action. The Pro version can be licensed to include a decompiler and interactive debugger for a specific architecture like x86_64 or ARM64. The licensing scheme is a little complicated, and a Pro license can run from hundreds to thousands of dollars per architecture. Many times I've longed to have IDA Pro on my laptop.

But apparently that longing never manifested into spending money on a IDA Pro license. (In hindsight, the timing for the release of Ghidra couldn't be better, since I recently revisited my budget for software reverse engineering tools.) So it was with great interest - and not a little trepidation - that I read about the NSA open sourcing their own SRE tool, and, shortly after that, installing Ghidra version 9.0 on one of my x86_64 development systems running Ubuntu 18.04. Subject to having an OpenJDK 11 available, Ghidra installed and ran without drama.

Ghidra supports a broad variety of processor architectures - many of which will cause the ears of an embedded developer to prick up - including 6502, ARM, AVR8,  MIPS, PIC, PowerPC, x86, and even Z80.

But while Ghidra is a remarkable tool, it isn't perfect. A common use case in my world is that I want to reverse engineer an ARM32 or ARM64 binary using my x86_64 laptop running Ubuntu in a VM under Windows. While for the most part Ghidra is up for this - this is where its write-once-run-anywhere Java implementation really pays off - it only took me a couple of hours of playing with it to run into my first documented bug in the 9.0 version (the release dated 2019-02-28): in binary files like shared object libraries that have multiple symbol tables, it misplaces some of the symbols so that it becomes convinced that one function (identified by a symbol) is in the middle of another function (regardless of the lack of idiomatic function entry instructions).



In the ARMv7 shared object binary above, Ghidra identifies the diminuto_cue_debounce function, but is convinced that the apply_gain function (which was in a completely different object module, one that implements a Proportional-Integral-Differential or PID controller, which was linked along with the debouncer and many other object modules into this common shared object) starts in the middle of it. The Ghidra bug tracker has a comment that this bug will be fixed in the next release.

Update 2019-04-02: I installed Ghidra 9.0.1 dated 2019-03-25, created a new project, reimported the pertinent file, reanalyzed it, and still see this issue when the source is compiled for the ARMv7L target (but not when compiled for the x86_64 target). What I thought was the relevant bug has been marked closed. I submitted a new bug report.

Update 2019-04-03: A Ghidra developer made the following comment on my bug report: 

The import of this file looks fine. If your only concern is the 0x10000 offset when compared to objdump this is not an import error unless the file has been prelinked in which case we should use the prelinked image base. This file is a relocatable shared library which can generally be imported to any base address of your choosing (see importer options). We default to offset 0x10000 which is somewhat arbitrary. We try to avoid loading at offset 0 when possible to help avoid mistaking small constants for address offsets. The importer has an image base offset option which can be set.

I set the offset from the default of 0x10000 to 0 by selecting Import File... then Options... and editing the Image Base field. That seems to have worked. I don't know whether this is necessary for any targets other than the ARMv7L, or why it wasn't necessary for the x86_64 target which also has the Image Base set to 0x10000 by default.

Update 2019-04-04: The same Ghidra developer make the subsequent comment: 

When I originally looked at your sample I had only done an import to see where the ELF loader was placing symbols. Having just run analysis I now see the issue you pointed out. You may have also noticed a bunch of DWARF related errors in your log during analysis when an image base of 0x10000 was used. Using an image base of 0 likely avoids these errors. We currently are not handling relocation records which apply to the DWARF debug data which is based at 0 for your sample. This results in DWARF analysis laying down symbols at the incorrect offset since the image base adjustment had not been applied. When DWARF data exists the 0 image base should probably be used until we are able to handle DWARF debug data relocations.

Update 2021-04-06: The latest public release of Ghidra, 9.2.2, seems to handle the multiple symbol table issue correctly (see screenshot below). As above, I set the image base to 0 here as well.

Bugs aside, Ghidra is a useful tool. While it makes reverse engineering binaries that contain symbols almost straight-forward (albeit not necessarily easy), it can also be used to analyze binaries that lack symbols, binaries that may even be deliberately obfuscated. Although I haven't played with it yet, it appears to allow you to add your own notations and to improve the disassembly and decompilation with your own manual analysis.

But even without doing this human labor, Ghidra produces useful artifacts for reverse engineering. Here is a screen shot of Ghidra's analysis of an ARMv7 executable binary stripped of symbols.



While Ghidra might not make it obvious, this program wipes data from a device by overwriting it with data generated from a polynomial whose initial value is seeded with a random number. It does this using synchronous I/O, bypassing the buffer cache, so that when a write operation completes, there is a chance that the data block really is overwritten, and not just scheduled to be overwritten sometime in the future. (The use case is wiping USB drives containing sensitive data in field.) Ghidra at least gives you a head start by providing a first-cut C decompile with synthesized symbol names that you can supplement with your own notes as you understand what's going on.

Important safety tip: Ghidra might make reverse engineering too easy. If you bother to read the typical End-User Licensing Agreement (EULA), you may find it specifically forbids reverse engineering the code that you just paid for. My colleagues and I have had some discussion about this when trying to integrate a recalcitrant third-party software package into our embedded product. It is not uncommon for a EULA to effectively prevent you from using the third-party product to which it applies.

Ghidra is evolving into a useful tool to keep in your embedded product development kit, along with static analysis tools like nm and objdump, as well as run-time tools like valgrind, ltrace, strace, and even gdb. In future articles I'll write about using Ghidra  to reverse engineer my own code that includes some of those specialized instruction sequences I mentioned earlier. And I'll keep an eye out for the next release.

Automatic Pilot

My 2016 Subaru WRX - a turbocharged all-wheel-drive sport sedan that Mrs. Overclock and I refer to as The Batmobile - has a Continuously Variable Transmission (CVT), with which the WRX simulates a six-speed in software, and the EyeSight driver assist feature which includes lane keeping, collision avoidance, and adaptive cruise control. I had the WRX only a few months before Mrs. Overclock and I attended MidAmeriCon II, the 74thWorld Science Fiction Convention, in Kansas City Missouri. Having driven my WRX from Denver to KC, we afterwards drove to Branson Missouri, which is near the Arkansas border.



I routinely used the intelligent cruise control on that trip, and it was a marvel: automatically slowing down and then speeding back up as traffic allowed. I did play with the lane keeping on a lightly populated stretch of the Kansas Turnpike. I typically don't use the lane keeping feature in "active" mode, preferring instead to merely have it warn me of a "lane departure". But on the Turnpike, active mode worked as advertised; it was spooky to feel the steering wheel being turned underneath my hands to keep the car in the lane.

Mrs. Overclock and I were on a four lane divided highway in Missouri - maybe US65 - that was not controlled access: it had roads - sometimes gravel - branching off at right angles into the woods on either side of the highway. I had both the collision avoidance and the adaptive cruise control engaged.

I was in the right hand lane when a local in a car right out of the Dukes of Hazzard came roaring past me in the left lane like his hair was on fire. Maybe he suddenly realized his turn was imminent. He cut in front of me and slammed on his brakes to make his turn.

I was paying attention, had my hands on the wheel, and saw all of this. I barely got my foot off the accelerator to apply the brakes when EyeSight simultaneously chopped the throttle, downshifted several times, and slammed on the brakes.

Mrs. Overclock and I were thrown into our seatbelts. My WRX slowed down, the local made his sharp right hand turn onto a gravel road, and we missed rear-ending him. After he turned, EyeSight let off the brakes, accelerated, upshifted, and resumed our prior cruising speed as if nothing had happened.

I'd like to think I could have done as well... but I'm just has glad I didn't have to prove that. It was a remarkable experience.

Never the less, I wouldn't trust EyeSight in my WRX - or Autopilot in your Tesla - to drive the car for me under all foreseeable conditions. EyeSight is good. But not perfect.

In daily driving I've had EyeSight in my WRX, and in Mrs. Overclock's 2016 Subaru Outback station wagon, turn itself off when visibility was very bad due to heavy rain or snow, the lane markings were so worn I couldn't even tell where the lane was, or temporary markings due to construction appeared unclear or ambiguous. Even doing something as mundane as driving through the car wash requires I disable the collision avoidance feature so that the computer doesn't freak out.

Most recently, EyeSight was useless as we crawled home in the Outback from Denver International Airport during the "bomb cyclone" - our flight from Chicago O'Hare (a Boeing 757 in which I am quite sure our pilots kept their hands firmly on the controls) was one of the very few arrivals not cancelled that day - because the ground blizzards reduced visibility to just a few feet beyond the hood of the car. Near the airport, where it was at its worst (it looked like a war zone) we had to resort to using GPS on a mobile phone to determine when we were approaching a major intersection, and what intersection it was, visibility was so poor. (The fact that GPS - possibly augmented by cell tower triangulation - worked at all is a remarkable technical achievement in signal processing.)  What we did may have been risky, but it kept us from being among the four thousand passengers that ended up sleeping at DIA that night because the arrival and departure boards were a sea of CANCELLED.



Automation works great... until it doesn't. Driver assist automation is great for augmenting our abilities, but not replacing them.

Automation for self-driving vehicles is a frequent topic of discussion amongst my real-time/embedded colleagues. It may be that it only has to do better than the average human at driving in conditions ranging from ideal to adverse. But our experience driving home from DIA suggests to me that that bar may not actually be all that low.

It's also hard not to ponder the unintended side effects of automation - particularly automation that overrides the human at the controls - when reading about the Boeing 737 MAX 8 story. But that's a topic for another day, when the facts are in.

Update (2022-10-28)

Not that long ago, Mrs. Overclock and I were at a stoplight preparing to exit a parking lot of a furniture store not far from our home. The cross street was a busy multilane state route. Mrs. Overclock was driving her 2016 Subaru Outback station wagon with the Eyesight system.

Our light turned green and she started to pull out. Suddenly the Outback autonomously slammed on the brakes as another car blasted across and through the intersection, inches away from the front of our car, at highway speeds, its driver having clearly missed seeing the stoplight. We could see the eyes of the passengers in the car across from us, which was also pulling out, grow wide.

Subaru's driver assist system may have saved our lives. At the very least, it kept my spousal unit's car from being totaled.