Simulating Slices of iOS Apps

Reading time: 10 minutes



Note

This post was discussed further on Hacker News.

09 Jan, 2024: There was an issue with newsletter signups. If you tried to sign up, please try again! You should see a success message.

In 2019, I built a work-for-hobby iOS simulator on a strict regimen of weekends and coffee. While the full details of this project will stay in-house, there’s enough I can share to hopefully be interesting!

First up, here’s what this looks like running against a simple demo app. On the right is the bona-fide iOS simulator from Xcode, and on the left is the simulator I built.

Simulating Opcodes

The heart of this simulator is a classic interpreter runloop. Each tick, the next opcode is parsed from the binary and interpreted to update the virtual machine state. Here’s a simple opcode handler:

The ldr and str instruction families were by far the most gruesome to pin down, as they both come in a variety of different flavors and modes. The simulator needs to handle a slew of load and store variants: immediate, pre-indexed, pre-indexed writeback, and post-indexed writeback, just to name a handful. These implementations were the largest of the instruction handlers, and they led to subtle bugs when the implementations were a bit off.

To get real-world code to work, I needed to implement all sorts of wacky opcodes interacting with floating point and SIMD registers.

VM Architecture

The simulator was built on a fundamental approximation of the von Neumann architecture: every piece of data was a Variable, and a Variable is always held in a VariableStorage. A CPU register is one kind of VariableStorage, and a memory cell is another.

This design was a misstep that I’d rework if I came back to the project: modelling each memory word as an object’s entire storage cell precludes any sensible possibility of operating on a buffer of bytes and modifying data across word boundaries. The strategy I chose, however, does work pretty well for application code that just stores pointers to heap-allocated objects in memory words and sends messages to them.

Symbol Modeling

Eventually, the simulated code is going to branch and, worse yet, branch to something imported from another binary. Instead of building a full dynamic linker, I added special support to the bl mnemonic handler to perform bespoke operations when certain branches were performed.

For example, if the simulator saw that a bl was being performed to the _random imported symbol, it could trap into its own in-house random() implementation.

Much more interesting, though, is _objc_msgSend.

This implementation would produce fake objects on a virtual heap, instead of simulating the real Objective-C runtime. I ended up with my own itty bitty standard library.

I also wrote implementations of funny constructors like +[NSDictionary dictionaryWithObjectsAndKeys:]. It was interesting to see how these kinds of call sites work under the hood!

Note
Objective-C object literals have always been a little quirky, too. I quickly checked how a dictionary literal is represented nowadays while writing up this post, and it looks as though, starting with the Xcode 13 toolchain or so, dictionary literals are laid out across __objc_dictobj and __objc_arraydata.

In this case, the compiler will place the first argument of the variadic list in x2. The compiler will arrange the rest of the arguments on the stack, starting with x2’s corresponding key. It’s the implementation’s responsibility to iterate the list on the stack, alternately popping off values and keys, until a NULL is reached.

strongarm’s REPL

The Mach-O VM loader never got quite up to the standards of the real thing. Instead of faithfully following whatever was described in the Mach-O, I implemented specific support for mapping various bits of the binary as the need arose:

Debugger

Simulators and emulators are notoriously difficult to debug, as often the errors only become visible in the higher-level logic of whatever you’re simulating.

I built a debugger that allowed me to run lldb on a real iOS device on one side, and the simulator on another, and run each forwards until the register or memory states of the simulator diverged from the real thing.

Since this is a virtual environment, it was also straightforward for me to snapshot the machine state at every instruction, which facilitated reverse debugging (’time travelling backwards’) to any previous execution point. I called this ‘visit mode’, since the REPL allowed you to run all the normal inspection commands (read, examine, print, etc.) as if execution was paused at a previous instruction pointer value.

Dynamic Linker

Eventually, I did branch out to truly mapping and invoking other binaries! In this tiny demo, a binary loads a framework and successfully branches to one of its exported symbols:

Note
No pun intended.

I then moved on to CoreFoundation, and wrote a pile of hacks to get it running. In this demo, I’m dynamically loading CoreFoundation, and the runtime is creating real ObjC strings and arrays!

My lldb comparison tool was essential here. I found that I needed to execute the routines specified by LC_ROUTINES_64 so that CoreFoundation had an opportunity to create its Objective-C classes and populate them in __CFRuntimeObjCClassTable. CoreFoundation queried this table when trying to use _CFAllocatorAllocate.

It was incredible to watch the simulated CoreFoundation bootstrap the runtime by calling things like object_setClass() on __NSCFArray! I also found that I could force CoreFoundation to do everything in-house, instead of shelling out to Foundation, by patching the memory in CoreFoundation’s ___FoundationPresent.present flag to 0.

Note
I may have some details on CoreFoundation wrong here, as it’s been a few years. Please feel welcome to send a correction if anything doesn’t sound right!

Testing the Simulator

I wrote a unit testing harness that allowed me to thoroughly test the implementations of these mnemonics, particularly trickier ones like ldr and str.

I locked down all sorts of behavior, such as the behavior of comparison flags:

Propagating Unknown Data

The goal of this project wasn’t to simulate an application from start to finish, but rather to simulate a specific tree of execution to make decisions about the code’s behavior.

This means that the simulator natively works with lots of unknown (‘unscoped’) data. As an example, any arguments to the simulator’s chosen entry point will definitely be unscoped by the simulation.

This unscoped data is represented by one of a few special types, such as FunctionArgumentObject and NonLocalVariable. These objects proliferate themselves when the simulated code tries to use them. For example, sending a message or accessing a field of a NonLocalVariable will spawn a NonLocalDataLoad as an output. It’s all a pile of hacks, but it works well enough.

Sometimes, the simulated code will, fairly, try to access an ivar from an object that was created through the simulator’s fake Objective-C runtime. This would yield an UninitializedVariable instance if we didn’t do anything else, which is no fun and typically causes the simulated code to complain. So, the simulator will walk the ivar table and instantiate dummy NSObjects to pop into these fields.

It’s difficult to say what to do when the simulated code performs a conditional branch that relies on unscoped data. So, I made the simulator split into two trees of execution: one where the condition was true, and one where it was false. Both paths would then be followed.

This caused lots of wasted work, because every path where if ((self = [super init])) {} fails was simulated. I eventually improved things such that execution was only split in two when necessary. This allowed me to correctly follow conditional branches when all the implicated data was available.

Observing Results

A simulator isn’t much good without some way to observe what the simulated code is doing. The simulated code’s output is obvious in the GUI-centric demo up top, but it’s less clear how this works when we’re simulating code without any UI.

For my use case, I wanted to observe the system state at various different instruction pointer values. This allowed me to construct human-consumable stack traces with all the dynamic arguments to each function filled in.

The simulator API allowed the programmer to specify all the instruction pointer values that they were interested in observing. The simulator would then follow all the execution trees, splitting off into subtrees with different sets of constraints when the simulator wasn’t sure which direction of a conditional was correct. At the end, all the machine snapshots across all the possible execution trees were returned to the programmer, who could then inspect the register and memory state at each snapshot.

Fun Bugs

Since the simulator runs untrusted code, I wanted to make sure that the simulator could gracefully handle infinite loops in the simulated code. I added a basic loop detector to ensure that the simulator always terminated.

One day, though, the simulator got stuck despite my initial efforts.

Like I mentioned above, the simulator had special support for certain functions that I had specifically modeled. For functions undefined by the simulator, though, the simulator would just pop a NonLocalVariable into x0 and carry on.

Note
Skipping over unmodelled calls is, on the surface, a pretty scary thing to do. Pragmatically, though, I tested it against a bunch of real-world code and found it didn’t preclude me from using the simulator for what I needed, so I rolled with it.

This works fine, unless the function being called is abort()! In this case, a code path tried to abort(), then the code that happened to immediately follow ended up doing a backwards jump. The result was the world’s most polite infinite loop, in which the client code asked the simulator to stop on every iteration, but fell on deaf ears.

The fix here was simple: I modeled abort() to terminate the current execution path, and improved my loop detector.


This project offered many satisfying problems along the way. It’s always fun to paint yourself into a big system with its own quirks and constraints, then find ways out of them. Thanks for following along!


Newsletter

Put your email in this funny little box, and I'll send you a message when I post new stuff.

09 Jan, 2024: There was a bug here. If you tried to sign up before please try again!