How Any App Could Track the Indoor Location of Everyone (Magnetic Localization)

For ten years, the computer science research community has attempted to develop a practical smartphone-based indoor localization system. While GPS allows users to navigate streets and cities easily, it fails to accurately localize a user within a room of a building. In this independent research project, I expand on current Magnetic Localization research and demonstrate the accuracy achievable by applying real-time Particle Filtering on magnetic magnitude readings from an iPhone 7 Plus. I also explore the novel and practical idea of measuring the magnetic distributions for rooms in order to perform room identification. Lastly, I will consider the practical nature of these models in comparison to alternative methods and will discuss the security vulnerability created by passive access to smartphone magnetometers.

TLDR: The compass in your phone can track and identify your location. This is a significant security threat that no one is protecting against.

1. Background

1.1 Why does this matter?

Outdoors localization allows travelers to find their way through foreign cities. It allows an Uber driver to pick up and drop off passengers. It even allows Amazon drones to drop packages off at customer homes. Software that detects the exact position of a user is powerful and valuable. To date, practical systems struggle to track the location of users within builders where GPS signals cannot penetrate. What if we could perform accurate indoors localization only using a smartphone?

The positive applications of indoor localization include:

• Bot navigation
• Visually impaired assistance
• Population movement pattern analysis
• Virtual and augmented reality mapping
• Context based digital assistants

Unfortunately, indoor localization could also be used maliciously. The techniques discussed in this post, such as Kalman Filtered Dead Reckoning, Magnetic Particle Filtering, and Magnetic Room Identification all require no permissions in iOS apps and are free to run in the background of iPhones. Therefore, an app like Facebook or Flappy Bird could potentially track the indoor movements of users. Such an app could know the path and timings of a security guard, or which rooms a CEO visited throughout their day — dangerous and valuable information.

Flappy Bird’s HQ

1.1. A Researcher’s Dream

Over the past ten years, researchers have strived to create a smartphone indoor navigation system. Some researchers leverage sensors such as the gyroscope and accelerometer in a bid to perform PDR (Pedestrian Dead Reckoning) which is the process of estimating a users footpath without using fixed reference points [1, 2, 3, 4]. Other researchers scoff at PDR and instead look around the users environment for stable landmarks which can be used to track relative distance and motion. Wifi signals work well, but iOS does not allow common apps to monitor for these signals [1, 2, 3, 4]. Only applications that are registered as “Hotspot Helper” can gain access to the necessary api. Naturally, GPS is not accurate enough to position oneself indoors, and the camera/microphone sensors are entirely impractical due to their battery demands, privacy concerns, and lack of in-pocket functionality.

1.2. iBeacons

All hope for indoor localization seemed lost until Apple made a substantial investment in the area by creating operating system level support in the form of iBeacon technology. External hardware devices could now broadcast Bluetooth advertisements, which could be passively monitored by iOS devices. Based on the signal strength of multiple iBeacon devices, iPhone apps can roughly triangulate the phones position to an accuracy of a few meters [1, 2, 3]. This system works reliably but requires many physical, battery powered devices placed around a building. The position of the iBeacons needs to be noted and updated if they are moved. Due to cost and maintenance, iBeacons have proven themselves not to be a practical system for large scale indoor localization.

A variety of iBeacons

1.3. Magnets (How Do They Work?)

iBeacon localization is powerful because it implants recognizable stationary landmarks for moving phones — but what if natural indoor landmarks already exist? In 2013, researchers hypothesized about matching the magnetic topography of a room with the magnetic readings on a smartphone to perform localization. While magnetic fields are traditionally invariable over short distances, the metal structures of buildings and furniture create unique magnetic topologies. By sampling a phone’s magnetic magnitude readings, one can estimate where in a room the phone is located. In 2016, another group of researchers took note of this idea and added smartphone magnetic readings to motion data before applying a Kalman Filter, a standard technique for incorporating noise into Dead Reckoning. This early work demonstrated the possibility of adding Magnetic Magnitude Filtering as a supplement to other techniques in order to achieve indoor localization accuracies of under 5 meters. Unfortunately, these researchers relied on wifi signal strengths to supplement magnetic fingerprinting, which is not permitted on iPhone apps looking to reach the App Store. In order to demonstrate the true potential of indoor localization using available iOS sensors, one must demonstrate accurate Magnetic Localization using only permission-less sensors such as an iPhone’s accelerometer and magnetometer.

1.4 Odontoceti

For the purposes of testing and evaluating the various techniques discussed in this post, such as Magnetic Particle Filtering and Magnetic Room Identification, I developed a simple iOS app named Odontoceti, a reference to echolocating whales.

2. Dead Reckoning (And why it’s impractical)

2.1. History

Before we consider localization using a phone magnetometer, we first need to discuss a more conventional method of phone localization, Dead Reckoning. This technique is defined as the process of determining one’s location by updating a prior position using speed and direction. Dead Reckoning is commonly used on boats and planes where there are not always fixed points from which to update one’s position. In recent years, Dead Reckoning has been used in cars to help navigation and sensor readings when GPS is unavailable, such as when navigating through tunnels. It has also been integrated into robots as a cheap way to perform high granularity localization in unknown environments.

Dead Reckoning attempts to track location using only angles and magnitudes read from a sensor.

2.2. Drift

Dead Reckoning appears sound on paper, but it is, unfortunately, not without flaws. To perform perfect Dead Reckoning, one would need to know the exact velocity of the object at every moment in time. Any inaccuracies in the direction or speed readings would lead to drift. Over time, differences in measurements and reality would add up, and the estimated location of the object would gain distance from the real position.

2.3. Dead Reckoning on mobile phones

Dead Reckoning is attractive because it only requires use of the accelerometer and compass from a phone. The accelerometer offers fine grain readings of the phone’s acceleration across the x, y, and z axes, while the compass helps to align these three axes with a known map in the phone’s memory. If one can filter out the noise generated from phone shake while walking, one could minimize drift and perform a rough Dead Reckoning.

2.4. Kalman Filtering

Acceleration noise is no small problem for real world mobile phone Dead Reckoning. Fortunately, there are known filtering algorithms that attempt to find truth in noisy data. In a linear system with Gaussian noise, a Kalman filter is the optimal method for estimating true values (D. Simon. Optimal State Estimation. Wiley, 2006). In some situations, such as situations when noise is nonGaussian, a Particle Filter may outperform a Kalman filter. However, for the sake of saving mobile phone processing power, we can make the assumption that acceleration noise is normally distributed.

2.5. Performance In Practice

In practice, Dead Reckoning is a brutally hard task. Even with a Kalman filter implemented, Dead Reckoning comes with many challenges. To reduce drift, an application needs to sample the accelerometer at the fastest rate allowed. This necessity can result in rapid battery drain making the app difficult to persist as a background process. Also, the user must specify the starting location, utilize the phone’s permission based compass sensor, and accurately track the scale of the map. Any app attempting to passively track a user’s location using Kalman Filer based Dead Reckoning would not appear subtle.

3. Magnetic Particle Filtering

Accelerometer based Dead Reckoning is guaranteed to be limited in its accuracies over time. It requires user interaction, and even with Kalman filtering, it suffers non-Gaussian noise accumulated over time. A viable alternative is Magnetic Particle Filtering. Before we discuss the exact mechanics of this system, I will first provide an overview of general Particle Filtering.

3.1. Particle Filtering Explained

Given noisy continuous measurements and a mapping of real values to locations, how can we accurately zero in on and track the position of an object? Because a continuous state space is infinitely large, we can’t consider all possible locations for our object. Instead, we make n guesses, in the form of randomly generated particles. Randomly generated guesses are better than no guesses, but we’re still not close to understanding the location of the object. To improve, we take a measurement from one of the object’s noisy sensors. Looking at our particles, we notice that some are located near true values similar to the measurement. Therefore, we select those particles and increase their associated weights.

In a second step, we attempt to make better guesses. We randomly sample with replacement another n particles, but this time drawing from the existing particles in the world. It is statistically likely that some particles will be drawn twice, and some never, so we will notice that at this point the particles begin to cluster.

We repeat, taking another measurement, weighting, and re-sampling. Overtime, the particles will cluster themselves around the most likely location of the object given the noisy measurements.

If the object is moving, we can generate some percentage of our particles randomly in the world in each generation, and allow them to naturally thrive or die off depending on the measurements.

3.1.1 Particle Filtering Assumptions

Particle Filtering is fantastic because, unlike other filtering algorithms, it does not require strong assumptions about the world. We can assume our noise is generated from any distribution, and the state space for our predictions can be non- linear. The ability to model noise from various distributions is useful because one could imagine dynamically selecting the noise distribution based features such as the orientation and motion of the tracked object.

3.2. Magnetic Topology

Any point inside of a building is subject to unique magnetic forces. Various ferrous metals found in the floor, walls, and unique fixtures throughout a building create a four-dimension map of three-dimensional space and magnetic magnitudes. The magnetic magnitude at any point in space can be measured by reading the x, y, and z magnetic vectors at that point, and calculating:

3.3. Unique Magnetic Signatures

To demonstrate the unique magnetic signatures that can be found within a building, I ventured into six different rooms and waved my phone around to sample the magnetic field. As the phone rotated, the detected magnetic field experienced slight fluctuations, which I proceeded to graph along the three possible axes of rotations. As can be seen from the graphs, each room measures a distinct magnetic signature. Simple sampling these forces over time would be enough to estimate the various rooms a person resides in over time.

Along each axis of rotation, one can distinguish unique room signatures. Each colored point represents the force magnitude measured as the phone rotated at a fixed point within a room.

Particle Filtering is lovely because, unlike other filtering algorithms, it does not require strong assumptions about the world. We can assume our noise is generated from any distribution, and the state space for our predictions can be non-linear. The ability to model noise from various distributions is useful because one could imagine dynamically selecting the noise distribution based features such as the orientation and motion of the tracked object.

3.4. Magnetic Cartography

Unlike Dead Reckoning, Magnetic Particle Filtering requires the pre-processing of the space before localization can occur. Specifically, someone needs to navigate through the world and measure the magnetic magnitude at each location.

To generate reference data for Particle Filter experimentation, the iOS app Odontoceti allows users to record their location and magnetic force at each point manually. While this solution works for the purposes of research, it would be somewhat contrived in a real world setting. However, the idea of crowd-sourcing a magnetic topology map from many users is not beyond imagination. Platforms such as Wikipedia and Quora rely on committed community members to contribute their time and knowledge for the greater good.

Odontoceti does not incorporate an automatic cartography system, but one could imagine several possible approaches to automatically generate magnetic magnitude topology maps.

For example, one could temporally place a series of Bluetooth beacons throughout a building and track the location of their phone using Bluetooth signal strength triangulation. The benefit of this system is that it would not necessitate any floor plans, only the relative positions of the Bluetooth beacons. Users could stroll around the building collecting magnetic samples over time until a detailed map had been generated, at which point the iBeacons could be removed.

Alternatively, one could rely on their phone’s camera to aid in automated cartography. While some users may not enjoy leaving their cameras running, a volunteer cartographer could enable their camera, point their phone towards the floor, and stroll around the building. Image processes could be used to detect the cartographer’s motion and exact position by generating a scan of the building’s floor. Then, as the volunteer continued over scanned area, the app could sample the magnetic magnitudes and associate them with locations around the building.

3.5. Mobile Magnetic Particle Filtering

Once a magnetic magnitude topological map has been generated for some indoor space, we can apply particle filtering. On iOS, the process proceeds as such:

1. As the iPhone app starts, the app begins asynchronously sampling the present magnetic field across three axes. Each sample is converted into a magnitude and is broadcasted throughout the app in the form of an NSNotification through the DefaultNotificationCenter.
2. A separate Map object listens for notifications. Upon receiving a sample, Map proceeds to iterate one generate of particle filtering.
3. Particles, represented as structs and randomly initialized throughout the current map, are weighted, and then sampled with resampling enabled.
4. During each sampling, θ ∗ n particles are randomly generated rather than drawn from the current distribution, in order to account for the possibility of user movement.

In this model, particles are weighted using a Gaussian distribution centered around μ, the true value for that location, and variance σ, a tunable variable.

3.6. Performance Concerns

It is important to be considerate of the performance cost to sampling the magnetometer and performing iterations of Particle Filtering. I found that if the sampling rate or the number of particles were too high, new magnetic readings would begin to queue while older readings were still being processed. This pileup resulted in a linearly increasing lag between the movements of the phone and the position estimates. To address this problem, I reduced the sample rate to ten times per second, and the number of particles to five hundred.

Not only can the performance of the phone suffer while performing Magnetic Particle Filtering, but so can the battery life. In short use cases, the impact on the phone’s battery is negligible. However, if the particle filtering were to run continuously in the foreground, or periodically in the background, the magnetometer sampling rate should be reduced.

One solution would be to dynamically adjust the rate of sampling based on the speed of the phone. If the phone was remaining mostly still, the sample rate could be allowed to decrease to one hertz or slower. If motion is detected through the phone’s accelerometer, the magnetometer sampling rate could be increased temporarily to better capture the user’s changing position.

4. Dead Reckoning Combined With Magnetic Particle Filtering

Dead Reckoning is particularly good at understanding the moment-to-moment transitions in space that a phone makes but is poor at understanding the original location of the phone and avoiding accumulated estimation error. On the other hand, Magnetic Particle Filtering is particularly good at estimating the probability of the location of a phone within some map and does not need the user to specify a starting point nor is it susceptible to drift. Magnetic Particle Filtering avoids many of the problems inherent to Dead Reckoning but is limited because we can only filter across a one-dimensional search space of magnetic magnitudes. These measurements are similar and noisy enough that it is likely several points within a room measure the same value given a margin of Gaussian error.

I theorize that the combination of these two systems might be able to outperform either system individually. Dead Reckoning could track the fine grain motions of the user, while Magnetic Particle Filtering could detect the starting location and corrects for accumulative drift.

5. Pure Magnetic Particle Filter Evaluation

To evaluate the accuracy of the Magnetic Particle Filter in a real world situation, I recorded the location estimations over time in a variety of real situations.

5.1. Straight Line Path

For the first test, I used the Cartographer mode of the Odontoceti app to measure the magnetic force at eight points along a line, each separated by one meter in a large dining hall. I then enabled particle filtering and walked along the same path, charting the position estimation over time. The algorithm was able to track motion consistently. Some of the points along the line had very similar measurements such as the first three points, which is likely why the estimation took large steps. It was not until a noticeably unique force was detected that the Particle Filtering was able to confidently advance its estimation. According to the graph below, we can determine that Magnetic Particle Filtering was able to achieve an accuracy of about 3 meters.

During this experiment, the phone was causally held level, in front of the user.

5.2. Rectangular Path

For the second test, I moved to a large library environment. I found a large rectangular path I could move about, measured the field at each meter along the path, and then walked the path while using Magnetic Particle Filtering to estimate my position.

During this experiment, the phone was causally held level, in front of the user.

While there is a fair amount of noise, we can see from the graph that the Magnetic Particle Filtering once again did a solid job at distinguishing the path of the phone around the rectangle.

5.3. Straight line with phone in pocket

Feeling emboldened by the accuracy of the results, I re-conducted the straight line test. I once again measured the magnetic forces while holding the phone level to create the magnetic magnitude topological map. I then attempted to use Odontoceti’s particle filtering to estimate my location while the phone was in my front pocket. Unfortunately, as is visible in the graph below, this adjustment appears to have decreased the accuracy of the estimations drastically. This decline may be because the phone’s magnetometer measures noisier readings while swaying upside down.

During this experiment, the phone was placed in the front right pocket of the user.

6. Magnetic Room Identification

Current research around indoor localization has avoided considering the ability to use Magnetic Magnitude Sampling to classify which room a phone resides.

If a user were to randomly wander about a room while sampling the magnetic magnitude at each point, they could generate a unique distribution of values that can act as a fingerprint for the space.

This histogram compares the magnetic magnitudes of 10,000 samples collected from two different rooms by a user wandering in a random manner while holding their phone our in front of them. Each signature is noticeably unique.

6.1. Rooms Tested

Understanding that rooms have unique magnetic magnitude distributions, one could sample this distribution for each room in a building and then attempt to predict from a new sample which room a phone was located. To put this idea into practice, I measured seven rooms throughout the Harvard College campus:

1. Cabot Common Room: A medium sized room in an old building on campus full of chairs and tables.
2. Cabot Small Room: A very small room with bean bags and curtains instead of doors.
3. Franklin Fellowship Room: A private dining room in a basement, complete with pillars, beanbags, a whiteboard, and other furniture.
4. Quincy Bedroom: A standard student bedroom containing a desk, a chair, a futon, and a computer.
5. Quincy Bullet Room: Another medium sized common room very similar to that in Cabot.
6. Quincy Hallway: A simple, straight hallway running the length of an entire building with doors on either side and an elevator in the middle.
7. Quincy Junior Common Room: A third common space containing a piano, a fireplace, chairs, and two tables.

6.2. Sampling And Training Method

For each room, I held an iPhone 7 Plus out flat in front of me and slowly walked in a random manner around the room. I sampled at a rate of 20 hertz for a total of 10,000 samples per space. This equated to 8.3 minutes of wandering per room. I then created a unified dataset by chunking contiguous periods of measurements and labeling them with their original room. By performing five-fold cross-validation on a random forest classifier, I was able to explore the predictable link between a distribution of readings and the room from which the readings originated.

6.3. Room Identification Results

By splitting samples into thirty-second contiguous chunks and then converting each chunk into a representative histogram, I was able to achieve the following confusion matrix:

Given seven possible rooms and thirty seconds of walking data, the random forest was able to classify the location of the phone with fantastically high accuracy for most rooms. Interestingly, there is not much confusion between physically similar rooms. Rather, the forest most frequently mis-predicted the bedroom, the smallest room, and one of the common rooms.

It makes sense that given more sample time, one would have a higher success rate of predicting the current room. We can see this to be true in the following graph.

As the amount of time spent sampling a space increases, so does the accuracy of prediction.

An iOS device is allowed to run background processes for up to 10 minutes before the operating system kills the process. Across seven rooms, I have shown an average accuracy of over 95% percent given less than two minutes of sampling. Given more training data and longer input data for predictions, one can assume the accuracy would only further increase.

7. Security Concerns

While Magnetic Particle Filtering and Magnetic Room Identification could be used for positive purposes as explored in Section 1, they also have the potential to exploit the privacy of iOS users everywhere. Traditionally an app must explicitly request permission from the user through an operating system notification to gain access to the user’s location. These systems allow users to understand which applications are tracking their whereabouts, and it creates an opt-in culture. Accurate localization through Magnetic Particle Filtering and Magnetic Room Identification could disrupt this privacy because iPhone magnetometers do not need permission, do not indicate to the user when it is being accessed by an app and can be read by an app running in the background.

Open access to the magnetometer could open the door for several types of attack. These techniques could be made more devastating by the incorporation of permissionless accelerometer data, but do not necessitate it.

1. Path tracking. A stream of timestamped magnetic readings could be paired with a magnetic magnitude topology map to perform smoothing, perhaps using the Vertirbi Algorithm. This algorithm would allow someone to best estimate the path of a user over time. There would be no restriction on the app tracking a user for days or longer.
2. Real-time tracking. A malicious app could continuously read the magnetometer data from a phone and send the information to a server, allowing attackers to perform filtering and estimate the location of a user in real-time. For a high-value target, such as a CEO, guard, or political figure, knowing which room they were standing in within a building could prove invaluable.

8. Conclusion

In conclusion, I have shown Magnetic Particle Filtering and Magnetic Room Identification to be viable techniques for indoor localization. Each requires data from only a single permissionless sensor that is commonly found in all modern smartphones. The algorithms does not require user-specified starting points, and they do not accumulate error over time.

Magnetic Particle Filtering and Magnetic Room Identification require existing magnetic topological map of buildings, but these maps could be crowdsourced by volunteers using cartographer apps, or could be acquired through more invasive methods. Battery concerns could be abated by intelligently detecting motion and modifying the magnetometer update frequency, or by offloading computations to a remote server. Localization in areas with uniform magnetic magnitude readings could be improved leveraging simplified Dead Reckoning techniques.

Perhaps the most promising discovery from this research is the encouraging results achieved in Magnetic Room Identification. The system requires far less effort from volunteer cartographers and allows for a higher accuracy than Magnetic Particle Filtering. Training distributions could be captured from passive sensor observation coupled with user provided information about their current location. Magnetic Room Identification comes with all the benefits of iBeacon technology but does not require physical hardware, location permissions, nor battery draining Bluetooth monitoring.

For the safety of iOS users, I recommend that Apple add permissions to the magnetometer because it clearly can be used to derive the location of an innocent user.

9. Next Steps

1. A simplified form of Dead Reckoning could still offer improvements to Magnetic Particle Filtering. For example, one could weight nearby particles based on how much motion is detected, to account for the rate at which the user might be moving.
2. Fingerprinting locations using magnetic magnitude distributions is effective, but the accuracy could be improved if one were to include wifi signal strength information. This data is accessible on Android phones but would require special Apple permission as of iOS 10.
3. Explore the performance of Magnetic Room Identification while the user’s phone is in their pocket. It is also worth exploring if different phones recognize similar magnetic signatures for the same location.