Whole fields of security work — malware analysis, crash triage, binary fuzzing — run programs inside a CPU emulator and assume the emulator behaves like the real chip, and nobody had checked that assumption for ARM; this paper (Zhejiang University and Hong Kong Polytechnic University) builds the first symbolic execution engine for ARM machine-readable specification language, uses it to generate 2,774,649 instruction streams that cover every one of the 1,998 instruction encodings, runs each one on four real ARM boards and on three emulators, and finds well over a hundred thousand instruction streams per emulator that behave differently — enough that a program can tell it is being emulated, hide from an analysis platform, and stop a fuzzer from making progress.
The argument in one glance
-
Problem
A great deal of security work assumes the emulator is the chip
Dynamic analysis of binaries almost always happens inside a CPU emulator, because an emulator can trace every instruction, observe an entire operating system, and run software built for one architecture on a machine of another. Malware analysis platforms, crash analysis tools, live patching systems and the emulator modes of popular fuzzers are all built on one. Every one of them silently assumes that executing an instruction inside the emulator tells you what the real processor would have done.
-
What people did
Test the emulator by feeding it instructions and comparing
The obvious way to check the assumption is differential testing — give the same instruction to a real chip and to the emulator, start both from the same state, and see whether they end in the same state. Earlier work did exactly this and found real divergences, using randomly generated byte sequences or sequences produced with help from the processor itself to decide what to try next.
-
Why it fell short
Random bytes are mostly not instructions, and ARM is not one thing
A 32-bit instruction word has more than four billion possible values, so enumeration is out. Random values are worse than they sound — in this paper's own measurement only 37.3 percent of randomly generated words were legal instructions at all, and those covered barely half the instructions in the manual. ARM makes it harder still, with several architecture versions, four instruction sets, and mixed 16-bit and 32-bit encodings. And the earlier work was built for x86, whose specification is prose.
-
This paper's idea
Generate the tests from the vendor's machine-readable specification
ARM publishes its architecture as executable code rather than prose, in a language called ASL. That specification says, for every instruction encoding, which bits are fixed and which are free, and what the instruction then does. This paper (Jiang, Xu, Zhou, Hu, Zhong, Wu, Luo and Ren) mutates the free bits by type, and then builds the first symbolic execution engine for ASL to solve every branch condition in the specification and its negation, so the generated tests reach the corners of each instruction's behaviour rather than only its common path.
Why this problem is worth solving
The stake is not the emulator itself but everything built on top of it.
AN
emulator executes a program by interpreting or translating its instructions in
software rather than running them on the matching hardware. That indirection is the
whole point, because software sits between every instruction and its effect, so the
analysis can trace each instruction, inspect memory at any moment, record an execution
and replay it, or run a program built for a phone processor on a desktop machine.
Hardware tracing features exist on real chips, but they capture into a small on-chip
buffer measured in tens of kilobytes, so they cannot follow a whole program. This is
why so much of the field — malware analysis, crash triage, firmware rehosting,
fuzzing of binaries without source — is built on emulators. If the emulator diverges
from the chip, every conclusion drawn inside it is suspect, and an author who knows
about a divergence can arrange to be studied doing something other than what the
program really does.
The second thing to understand is that most divergences are not bugs.
THE
ARM manual does not define an outcome for every bit pattern. Some patterns are marked
UNDEFINED, which means the processor must refuse them. Others are marked UNPREDICTABLE,
which means the manual deliberately declines to say what happens, leaving each chip
designer and each emulator author free to choose. A related marking called Constraint
UNPREDICTABLE lists a small menu of acceptable behaviours and lets the implementer pick
one. In all of those cases two implementations can differ while both are perfectly
correct. Only when an implementation contradicts something the manual does define is
there a bug. This distinction decides how each of the results in this paper should be
read, and the authors sort their findings by it.
What people did before, and where it broke
-
Random instruction generation. Earlier emulator-testing work generated byte sequences at random and executed them on both sides. It is simple, it needs no specification, and it did find genuine divergences on x86.
-
The gap. Most random words are not instructions. Measured here on the same budget of test cases, only 37.3 percent were legal, and those legal ones reached just 54.5 percent of encodings and 51.4 percent of instructions. Half the instruction set was never tested at all.
-
Processor-assisted generation. A refinement that uses the hardware to steer generation towards inputs the chip accepts, improving on blind randomness.
-
The gap. It was built for x86 and cannot be carried over. ARM has several architecture versions, four instruction sets, and 16-bit and 32-bit encodings that can be mixed in one program, so a generator has to be aware of the encoding rules rather than discovering them by trial.
-
Reading the manual and writing tests by hand. The most direct approach, and the one that produces the highest-quality tests per test.
-
The gap. There are 1,998 instruction encodings belonging to 1,070 instructions, and each encoding has its own branch conditions on the values of its bit fields. Covering that by hand is not a realistic amount of human work.
-
Trusting the emulator. In practice the dominant approach — an entire literature of analysis frameworks was built on one emulator without the assumption being checked.
-
The gap. It does not hold. Roughly six percent of the generated instruction streams behaved differently, spread across almost half of all ARM instructions, including ones as ordinary as store and branch-with-link-and-exchange.
How the specification becomes a test suite
From the vendor specification to a list of divergent instructions
-
-
new
-
new
-
new
-
new
-
new
The idea
A machine-readable specification turns test generation into constraint solving. Most architectures are specified in prose, so a test generator can only guess at what the processor is supposed to do. ARM publishes its specification as executable code, and that changes the shape of the problem. Each instruction encoding comes with a diagram saying which bits are fixed, which immediately restricts generation to legal instructions — this is why every one of the 2.7 million generated streams is a real instruction, against 37.3 percent for random generation on the same budget. Each encoding also comes with decode and execute code whose branch conditions are written down, so the generator can read the conditions rather than hope to stumble into them. Filling the free fields by type gets you syntactically valid instructions; solving the conditions gets you instructions that exercise different behaviours of the same encoding. Using a solver to manufacture inputs that are valid by construction rather than valid by luck is the same move that makes the deep-learning compiler test generator covered elsewhere on this site work, where random operator graphs are rejected before they ever reach the compiler.
Solve every condition and its negation, because the interesting behaviour is on both sides. The symbolic execution engine is where the paper does its real work. For each condition in the specification code — say a check that decides whether an instruction is UNPREDICTABLE — it slices backwards to find the statements that produced the value being tested, converts the chain into an expression over the encoding fields, adds range constraints from each field’s bit width, and hands the whole thing to a solver. It then negates the condition and solves again. Both answers go into the mutation sets, so the Cartesian product is guaranteed to contain streams that take the condition and streams that avoid it. Path explosion, the usual reason symbolic execution fails, does not arise here — the decode and execute code for a single encoding is short and has few branches, and helper functions are modelled rather than entered. Across all instructions the engine solved 12,701 conditions and generated the entire suite in under four minutes. That reliance on a written-down contract to make testing possible is the same starting point as the speculation-contract fuzzer covered elsewhere on this site, which had to invent the contract first because the instruction set said nothing about what it wanted to test.
Most of the divergence is licensed by the manual, and that is the security finding. When the results are sorted by cause, only a small fraction of the divergent streams come from emulator bugs — a few hundred streams, from twelve confirmed bugs, though these cover ordinary instructions and therefore matter. The overwhelming majority come from places where the manual declines to specify an outcome, and a real chip and an emulator made different legal choices. That is an uncomfortable result, because a bug can be patched and an unspecified case cannot. The paper turns it into three demonstrations — an Android library that identifies the emulator it is running in, a rootkit that performs its malicious work only when a divergent instruction proves it is on real hardware, and a compiler plugin that makes a released binary unfuzzable inside an emulator. Underspecified behaviour producing implementations that legitimately disagree is exactly the situation studied by the work on undefined behaviour in C covered elsewhere on this site, where the disagreement between two correct compilers is itself the detector.
Catching one divergent store instruction
How the system found a real bug in an emulator, one instruction at a time
Following the 32-bit Thumb-2 encoding of the store-immediate instruction from specification to confirmed bug.
Step 1 of 5
Read the encoding diagram
For this encoding, the top twelve bits are fixed. The free fields are the base register, the source register, three single-bit flags, and an eight-bit immediate offset.
Fixing the constant bits is what guarantees that every generated word is a legal instruction of this encoding. The free fields are the only degrees of freedom, and there are far fewer of them than the 32 bits would suggest.
Why it works
- The encoding diagram eliminates illegal tests for free. Fixing the constant bits and varying only the free fields → every generated word is a legal instruction of a known encoding → the entire test budget is spent on instructions the processor will actually decode, instead of the 62.7 percent of random words that are rejected immediately.
- Field types carry the interesting values. Naming conventions reveal that a field is a register index or an immediate → the generator can seed it with the values that matter, the program counter index and the two numeric extremes → boundary cases appear by construction rather than by chance.
- Solving both a condition and its negation guarantees coverage of a branch. Each solution is injected into the mutation set of the field it constrains → the Cartesian product must contain streams on both sides of that condition → different semantic paths of one encoding get tested, not just the common path.
- Symbolic execution stays cheap because the specification is small. One encoding’s decode and execute code has few branches and helper functions are modelled rather than entered → no path explosion → all 12,701 conditions across the architecture are solved and the full suite is generated in about three and a half minutes.
- Comparing a narrow state makes the verdict deterministic. Zeroing the registers that can be zeroed and comparing only registers, status flags, the signal, and the one memory word the instruction writes → run-to-run noise from address randomisation is excluded → a difference between the two sides is evidence rather than an artefact.
What it costs (trade-offs and scope)
- It needs a machine-readable specification. The whole generator rests on ARM publishing its architecture as executable code. For an architecture specified in prose, the encoding diagrams and branch conditions would have to be reconstructed by hand, and the paper says a new generation algorithm would be required.
- Unprivileged mode only. Every test runs as an ordinary user-space program. Some instructions behave differently in privileged mode, and one of the reported emulator bugs involves an instruction mainly used by system software, so its status in kernel mode is untested.
- One instruction at a time. The engine tests single instruction streams, not sequences. Divergences that appear only after several instructions have accumulated processor state are outside what it can find, and the authors list sequence testing as future work.
- Hardware and emulator must be matched by hand. The comparison is only fair when the emulated processor model matches the board. For the newest board tested, the emulator did not support the exact core, so a close relative sharing the same instruction set was used.
- The findings are a weapon as well as a diagnosis. The three demonstrations show a program hiding from an analysis platform and defeating a fuzzer. The authors note that detecting such misuse is hard, since the divergent instructions include commonplace ones and can be decrypted into place while the program runs.
The evaluation
| Property | What was measured | The result | What it tells you |
|---|---|---|---|
| Test suite quality | |||
| Divergences found | |||
| Root causes | |||
| Emulator detection | |||
| Anti-fuzzing cost |
Check yourself
Check your understanding
1. Why does generating test cases from the encoding diagram produce so many more usable tests than random generation?
2. What is the point of solving each condition in the specification AND its negation?
3. Around nine in ten of the divergent instruction streams were traced to UNPREDICTABLE cases rather than to emulator bugs. What follows from that?
4. Predict what would happen if the differential testing engine compared the entire memory space of the two executions instead of only the word the instruction writes.
Sources
EXAMINER: automatically locating inconsistent instructions between real devices and CPU emulators for ARM. Muhui Jiang, Tianyi Xu, Yajin Zhou, Yufeng Hu, Ming Zhong, Lei Wu, Xiapu Luo, Kui Ren. ASPLOS 2022, pages 846 to 858. DOI 10.1145/3503222.3507736. Design and evaluation detail read from the authors’ preprint, arXiv 2105.14273, where the prototype is named INSDET and the study covers one emulator; the divergence counts for three emulators and the count of twelve confirmed bugs are from the conference abstract.