Casa de Balloon Club: Android at 100,000 ft

The GPS on pretty much every Android phone deliberately stops working above 60,000 feet.

This is the story of why and how we hacked around that limit and got our Android powered Nexus S to maintain a GPS lock up to 100,000 feet above the ground.

Note that we're not going to distribute any modified binaries, since we are not licensed to do so. But we will explain exactly what we did in sufficient detail that you should be able to replicate our results.

Motivation:

For amateur weather balloon enthusiasts, a used Android phone makes the perfect tracking device — it has a radio, a camera, sensors, GPS, storage, and a pretty powerful CPU all wrapped up in a nice package you can buy for <$50 on eBay.

The only downside is that the GPS stops working above 60,000 feet, while a weather balloon launch typically goes well above 80,000 feet and sometimes above 100,000 feet. This means the GPS logs from our phones end up looking like this:

The failure of GPS is not a technical limitation — it’s a legal one. Specifically, a 1960’s era piece of regulation introduced the “CoCom Limits” which require that all commercial GPS chipsets disable tracking if they determine that they’re traveling above 60,000 feet and above 1200 mph. The original reason was to prevent no-goodniks from using commercial GPS units to make ICBM guidance systems.

As written, the CoCom limits are perfectly reasonable and do NOT interfere with our weather balloon adventures, which meander along at a leisurely 75 mph. Unfortunately, the limits as written are not the limits as implemented — specifically most commercial GPS implementations inside phones will be disabled if they go above 60,000 ft OR above 1200 mph.

If only there was a way to poke inside the GPS logic and turn that “OR” into an “AND”...

Back to Contents

Exploration:

When we first ran into the 60,000-ft limit on our Android phones, we downloaded the Android source code and poked around a bit in the location services and GPS system to see if we could find any code that enforced these limits. Unfortunately, no luck — all we learned is that the the GPS service interfaces with the underlying hardware via an NMEA-like interface, which pre-filters location data.

But digging into the wonderful Android developer community at xda-developers, we stumbled across two amazing posts:

After reading through both threads, we learned two critical facts:

Broadcom GPS chips offloaded the actual position calculation to a regular arm-linux binary running on the host Android system (glgps / gpsd)
That binary has extensive debug-level logging statements built in

Since we were using a Nexus S phone which has one of these Broadcom GPS chips in it, we decided it was time to nerd up and learn how to reverse engineer and make a binary modification to a closed-source executable. Wheeeee!

Rather than writing a book about all the different things we tried which ended up going nowhere, we’ll instead focus on the much shorter set of steps we took which ultimately ended up working and why they were necessary.

Back to Contents

Setting up Android:

We started with installing CyanogenMod on our Android phone.

Like us, you may have thought Android is just Linux, which would mean once you got a shell, you’d be ready to ls cp mv cat | grep. That’s only half-true — stock Android runs the Linux kernel and has a shell, but that shell doesn't quite work like the standard bash shell we're used to.

To get all the Linux shell goodies we actually wanted, we would have had to go through some sort of ugly process of rooting our phone, swapping out the default Android shell for busybox, and installing a bunch of other utilities which we would expect to be present on any Linux system we’re working on.

Fortunately, because of Android’s open-sourceness and the awesomeness of the CyanogenMod team, we were able to just download and install a stable, high-quality ROM that had all of the developer features and utilities we needed installed and configured correctly.

Back to Contents

Extracting the binary gpsd:

Per the xda-developers forum threads, the binary of interest on our Nexus S phone was located at:
/system/vendor/bin/gpsd

In order to get to it, we first restarted ADB as root and then pulled a copy of gpsd and its config file to our local ubuntu desktop:

-- Restart ADB as root on the target device --

ubuntu:~/$ adb root

-- Remount /system to be read-write to change system files --

ubuntu:~/$ adb shell "mount -o rw,remount /system"

-- Pull the gpsd binary and its corresponding config file --

ubuntu:~/$ adb pull /system/vendor/bin/gpsd

ubuntu:~/$ adb pull /system/vendor/etc/gps.xml

As a first exercise, we decided to change the logging settings in gps.xml and see if we could get some verbose debugging output. Here is our modified gps.xml.

After changing gps.xml locally, we had to push it to see if it worked:

-- Push the edited gps.xml --

ubuntu:~/$ adb push gps.xml /system/vendor/etc/gps.xml

-- Kill the currently running gpsd process, forcing it to restart and read the new config file --

ubuntu:~/$ adb shell "killall gpsd"

Then we started up the GPS Test app, waited for a bit, quit out, and downloaded the log file:

-- Pull the gps log file --

ubuntu:~/$ adb pull /data/gps/log

-- Peek at the gps log file --

ubuntu:~/$ less gl-*.txt

The giant dump of log messages meant we successfully managed to replicate the work of everyone else who has been hacking on Android and Android GPS to date, which serves as an excellent starting point.

Back to Contents

Reverse-engineering gpsd part I: Disassembly

The first question we had was: "Are there any log messages in gpsd related to CoCom altitude limits?”

ubuntu:~/$ strings gpsd | grep -i limit

CP_W: %s: SatID:%d out of the limits

<SKFNAV> COCOM limit exceeded. Alt=%em No output & KF reset!

<SKFNAV> <SKFNAV> Speed limit exceeded. Speed=%1.0f m/s No output 

%sSetUserDynamicLimits(%u m/s, %f m/s^2)

UpdateTimeStamps: state %s curr %lu Stat %ul Driv %ul Train %ul ...

Binwmm::mode3 (ch %d sv %d) bin limit %d reached - reporting no energy

Binwmm::mode3 (ch %d sv %d) retry limit reached - reporting no energy

Binwmm::mode3 (ch %d sv %d) retry limit not reached (cnt = %hu) - returning to coarse stage

toeLimit

'pvalue->toeLimit'

Jackpot! There was a nice, simple, straightforward log statement pointing to exactly what we wanted. Thank you, Broadcom!

Had we not found such a statement, you probably would not be reading this article because we would have given up and spent the rest of the evening watching cat videos on YouTube.

With log statement in hand, all we had to do is find the code path which referenced it and insert a couple strategic NOOPs. Easy peasy lemon-squeezy, right?

Having no desire to trace through lines of raw ARM assembly, we looked online for good ARM disassemblers and decompilers which could produce a C-like output. Some of the options we encountered included:

IDA Pro - Looked awesome, but the trial version was sufficiently crippled to not be usable for this project, and the license was outside our budget for something we were only going to use once.
Retargetable Decompiler - Looked like it could have been perfect, but their online demo barfed on our gpsd upload.
Hopper - Claimed to have all the bells and whistles that we wanted, offered a very usable trial version, and had a perfectly affordable license cost of $89.

We downloaded the Hopper trial, and after poking around with it for a couple hours, we were sufficiently pleased with it to justify paying the $89 and purchasing a license.

We fed gpsd into Hopper, and after a few minutes of chugging, it gave us a nice searchable view of the assembly code:

The first thing we did was search for the debug statement, and we found the address for the start of that string in the .data section at address 0x00156b52:

The next thing we did was search for any references to 0x00156b52 anywhere else in the assembly. Not found — uh oh! This meant one of two things: either the debug statement was dead code not used anywhere, or there was some other mechanism for referencing string constants in print statements.

To dig into this a bit further, we decided to switch to one of the debug statements from our log file:
14:37:37.940 #372590D <SKFNAV> SKF_AUTO!!!

We found the corresponding string constant at 0x00157851. That address was also not referenced directly anywhere in the code, which was good news and bad news.

The good news was that clearly there was some other method of referencing string constants.

The bad news was that now we either had to trace through a truckload of assembly to figure out what that method was, or we’d have to learn how to use a binary debugger to narrow down the amount of assembly we had to paw through. Both of those options sounded strictly less fun than watching cat videos.

Back to Contents

Reverse-engineering gpsd part II: Debugging Setup

Having just enjoyed a refreshing evening of cat videos, we once again decided to nerd up and learn us some gdb.

We were not quite sure where to begin, but RMS came to the rescue with this amazingly well written and accessible GDB tutorial.

With some basic knowledge about how to use GDB under our belt, it was time to learn how to run gbdserver / gdb on Android.

There were actually many many more tutorials on how to use gdb both in general and on Android, but most of the "simple" ones were useless because they all were based on the assumption that you were trying to debug a binary which you wrote and compiled, with debugging symbols which mapped back to your source code. Whereas we were working with a stripped binary, no source code, and a vague decade-old understanding of assembly language, stack traces, and core dumps.

We got gpsd running under gdbserver by doing the following:

-- Move gpsd to gpsd.original to prevent it from auto-starting --

ubuntu:~/$ adb shell

root@android:/ # cd /system/vendor/bin

root@android:/ # mv gpsd gpsd.original

-- Kill existing gpsd process and restart under gdbserver --

root@android:/ # killall gpsd

root@android:/ # gdbserver :5039 gpsd.original -c /vendor/etc/gps.xml 

-- Enable gdbserver port forwarding --

ubuntu:~/$ adb forward tcp:5039 tcp:5039

-- Start gdb --

ubuntu:~/$ $ANDROID_HOME/android-ndk-r10d/toolchains/arm-linux-androideabi-4.9/prebuilt/linux-x86_64/bin/arm-linux-androideabi-gdb gpsd

-- Connect to the gdbserver instance -- 

(gdb) target remote :5039

-- Run gpsd and make sure it still works --

(gdb) continue

Then we fired up the old faithful GPS Test App and made sure everything was still working.

Back to Contents

Reverse-engineering gpsd part III: Debugging Debug Messages

Now that we had a functioning binary debugging setup, it was time to figure out just how in the heck those debug print statements worked. After reading through the gdb tutorial, we decided the easiest solution was to set a read watchpoint on the memory address of a debug statement that appeared in our logfile:

(gdb) rwatch *0x00157851

Hardware read watchpoint 1: *0x00157851

(gdb) continue

Continuing.

Cannot access memory at address 0x0

Warning:

Could not insert hardware watchpoint 1.

Could not insert hardware breakpoints:

You may have requested too many hardware breakpoints/watchpoints.

Unfortunately, that seemed to do a whole lot of nothing. After a bit more digging, we learned that read watchpoints are an extremely CPU/architecture-specific feature, and in the case of ARM you only got them if you were using a hardware JTAG debugger. We briefly toyed with the idea of busting out the soldering iron and logic analyzer before coming to our senses and deciding not to shave that particular yak.

Instead, we resigned ourselves to working with function pointers instead. Switching back to Hopper, we searched for a printf-like function and found sprintf at 0x00014bc8.

We decided to stick a breakpoint on it and see what happened:

(gdb) b *0x00014bc8

Breakpoint 1 at 0x14bc8

(gdb) continue

Continuing.

Breakpoint 1, 0x00014bc8 in sprintf ()

Success! We hit the breakpoint. Without going into too much detail, this particular sprintf turned out to be a dead end. So we went ahead and ran to the next sprintf breakpoint:

(gdb) continue

Continuing.

Breakpoint 1, 0x00014bc8 in sprintf ()

Now it was time to look at the registers and see if any of them held pointers to anything that looked like a valid debug string address:

(gdb) info registers

r0             0xbefb95dc       -1090808356

r1             0x150123 1376547

r2             0x197cad 1670317

r3             0xbefb96dc       -1090808100

r4             0x196b48 1665864

r5             0xbefb95dc       -1090808356

r6             0x197cad 1670317

r7             0xbefb96dc       -1090808100

r8             0x0      0

r9             0x0      0

r10            0x0      0

r11            0x0      0

r12            0x0      0

sp             0xbefb95d0       0xbefb95d0

lr             0x232f3  144115

pc             0x14bc8  0x14bc8 <sprintf>

cpsr           0x80070010       -2147024880

According to the decompiler, the string being printed should be in either r0 or r1. Sure enough, the value 0x150123 in r1 pointed to the string constant "%s/%s" in the data section.

Furthermore, to confirm earlier findings, a search for that string constant address in the assembly yielded nothing, meaning it was computed on the fly in some previous function.

So next step was to walk up the stack trace, taking a look at each function to determine where the string address calculation happened:

(gdb) backtrace

#0  0x00014bc8 in sprintf ()

#1  0x000232f2 in ?? ()

#2  0x000233b8 in ?? ()

#3  0x0002348a in ?? ()

#4  0x0001e826 in ?? ()

#5  0x0001e8d6 in ?? ()

#6  0x0001deaa in ?? ()

#7  0x00015a3c in ?? ()

#8  0x00015180 in ?? ()

#9  0x00014f34 in ?? ()

#10 0x000150c0 in main ()

Looks like this sprintf returns to address 0x000232f2 which means it was invoked at 0x000232ee.

Let's decompile this function and see what it does:

Oh, wow, isn't this convenient. The r1 argument to sprintf is calculated by adding whatever value is in r3 to a constant 0x0019bb48. Perhaps this means string references are stored as offsets?

Armed with this assumption, the next question was: could we find which codepath triggered our "altitude limit exceeded" debug message? Its address of 0x00156b52 corresponded to an offset of 0xFFFC000A from 0x00196b48, so we searched for “0xFFFC000A” in the assembly code...and bam!

This reference to our string constant was contained within a function at address 0x00048078 (sub_48078). When we decompiled that function, we saw a nice “if(something) { barf }” structure:

Just to confirm, we took a look at the second structure and saw it reference an offset of 0xfffc0048, which corresponded to a string address of 0x00156b90, which held the debug message "<SKFNAV> <SKFNAV> Speed limit exceeded. Speed=%1.0f m/s No output "

Back to Contents

Reverse-engineering gpsd part IV: Binary Patching

So it looks like the function sub_48078 was some sort of CoCom limit check. Furthermore, it looks like function sub_48078 is only invoked one time at address 0x0004e6a6:

We decompiled the function which called sub_48078, and saw a bunch of other debug messages related to various error checks:

So it seemed to be a pretty safe bet that if we NOOP the invocation to the CoCom check at 0x0004e6a6, then our GPS should happily function above 60,000 feet!

Hopper made this surprisingly easy — with just a couple clicks, we disabled the function invocation at 0x0004e6a6 and exported a new binary.

For those of you following along at home with your own disassembler and debugger, here’s some helpful info:

ubuntu:~/$ md5sum gpsd.original

4a6c0027e530b5b8a346153a355ef8e3  gpsd.original

ubuntu:~$ md5sum gpsd.modified

77808f7c84f60da2ca494c81b369d77b  gpsd.modified

ubuntu:~$ cmp -l gpsd.original gpsd.modified | gawk '{printf "%08X %02X %02X\n", $1, strtonum(0$2), strtonum(0$3)}'

000466A7 F9 00

000466A8 F7 BF

000466A9 E7 00

000466AA FC BF

Time to push this patched gpsd to the phone, restart gpsd, and make sure it all still works:

ubuntu:~/$ adb push gpsd.modified /system/vendor/bin/gpsd.modified

ubuntu:~/$ adb shell

root@android:/ # cd /system/vendor/bin

root@android:/ # chmod 755 gpsd.modified

root@android:/ # gpsd.modified -c /vendor/etc/gps.xml

When we fire up our favorite GPS Test App, we continue to get a GPS fix — so it seems like at the very least our modified binary didn’t completely break everything!

May as well make our patched version the default gpsd:

root@android:/ # cd /system/vendor/bin

root@android:/ # cp gpsd.modified gpsd

Back to Contents

Testing part I: GPS Simulators

A couple of our awesome friends — specifically Eric Jonas at Berkeley and Jeremy Conrad at Lemnos Labs — put us in touch with Fergus Noble, the founder and CTO of Swift Navigation (a company which makes high-precision GPS equipment, which I hope one day finds its way into all of our phones).

Fergus was gracious enough to spend an afternoon giving me a tour of Swift Navigation and talking shop about what they were working on. It’s pretty awesome, and I highly recommend you take some time to check them out — http://www.swiftnav.com/. He also hooked me up with their Spirent STR4500 GPS simulator so that I could sit comfortably at a lab bench with my android dev setup and trick my phone into thinking it was on a cross-country airplane flight, just to see if my modified gpsd was still working. Fortunately, everything looked like it was working perfectly — woohoo!

Fun Fergus Fact: He was president of Cambridge University Spaceflight. If that sounds familiar, it's because it's the group which developed some of the best resources available to amateur weather balloon enthusiasts.

Back to Contents

Testing part II: Real Life

Unfortunately, the GPS simulator was unable to replicate scenarios above the CoCom limits. We figured the next best option was to spin up some sort of Felix Baumgartner / Alan Eustace-style operation so we could title this article “Debugging Android at 100,000 ft”.

Sadly, the time and cost of such testing exceeded our project budget by two orders of magnitude, so we followed in the footsteps of thousands of product managers in similar positions by declaring, “Screw testing. Let’s ship!”

With the help of the rest of the Casa de Balloon Club and some extra special love from the "Made With Android" team at Google, we shoved our modified Nexus S into a foam box, tied it to a helium-filled weather balloon, and let it loose over the Central Valley.

And to everyone’s surprise, we not only recovered the payloads and got some awesome pictures, but we also discovered that our modification did in fact have the desired effect and our Android phones successfully tracked our entire flights!

Back to Contents

Epilogue

In that launch, we actually sent up both a modified Nexus S as well as a modified Samsung Galaxy Camera GC100, both of which used Broadcom GPS chipsets and both of which worked swimmingly.

In future launches, we plan on sending up a modified Samsung Galaxy SIII i9300, which has much newer hardware but continues to use the same Broadcom GPS chipset.

If you happen to be interested in replicating this project I highly recommend purchasing a used Nexus S. But if you’re up for doing some reverse engineering of your own, a quick crawl through all of the CyanogenMod device repos shows that the following supported devices all have Broadcom GPSs and should be hackable following the same process:

captivatemtd - Samsung Captivate
crespo - Nexus S
galaxysmtd - Samsung Galaxy S i9000
i9300 - Samsung Galaxy S3 i9300
i9500 - Samsung Galaxy S4 i9500
n7000 - Samsung Galaxy Note n7000
n7100 - Samsung Galaxy Note 2 n7100
superior - Samsung Galaxy Premier i9260
vibrantmtd - Samsung Vibrant
enrc2b - HTC One X+
p720 - LG Optimus 3D Max P720
p760 - LG Optimus L9 P760
p970 - LG Optimus Black P970
p990 - LG Optimus 2X P990

Also, many older devices using Exynos or Tegra chipsets (such as the Galaxy Camera GC100) are paired with Broadcom GPSs . As long as you can root your ROM and you can find the gpsd or glgps binary, there’s a good chance you can modify it.

Good luck and happy hacking!

Back to Contents

Casa de Balloon Club

Android at 100,000 ft

Table of Contents:

Motivation:

Exploration:

Setting up Android:

Extracting the binary gpsd:

Reverse-engineering gpsd part I: Disassembly

Reverse-engineering gpsd part II: Debugging Setup

Reverse-engineering gpsd part III: Debugging Debug Messages

Reverse-engineering gpsd part IV: Binary Patching

Testing part I: GPS Simulators

Testing part II: Real Life

Epilogue

1 comment: