1 /*
2  * Copyright (C) 2020 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.server.location.fudger;
18 
19 import android.annotation.Nullable;
20 import android.location.Location;
21 import android.location.LocationResult;
22 import android.os.SystemClock;
23 
24 import com.android.internal.annotations.GuardedBy;
25 import com.android.internal.annotations.VisibleForTesting;
26 
27 import java.security.SecureRandom;
28 import java.time.Clock;
29 import java.util.Random;
30 
31 /**
32  * Contains the logic to obfuscate (fudge) locations for coarse applications. The goal is just to
33  * prevent applications with only the coarse location permission from receiving a fine location.
34  */
35 public class LocationFudger {
36 
37     // minimum accuracy a coarsened location can have
38     private static final float MIN_ACCURACY_M = 200.0f;
39 
40     // how often random offsets are updated
41     @VisibleForTesting
42     static final long OFFSET_UPDATE_INTERVAL_MS = 60 * 60 * 1000;
43 
44     // the percentage that we change the random offset at every interval. 0.0 indicates the random
45     // offset doesn't change. 1.0 indicates the random offset is completely replaced every interval
46     private static final double CHANGE_PER_INTERVAL = 0.03;  // 3% change
47 
48     // weights used to move the random offset. the goal is to iterate on the previous offset, but
49     // keep the resulting standard deviation the same. the variance of two gaussian distributions
50     // summed together is equal to the sum of the variance of each distribution. so some quick
51     // algebra results in the following sqrt calculation to weight in a new offset while keeping the
52     // final standard deviation unchanged.
53     private static final double NEW_WEIGHT = CHANGE_PER_INTERVAL;
54     private static final double OLD_WEIGHT = Math.sqrt(1 - NEW_WEIGHT * NEW_WEIGHT);
55 
56     // this number actually varies because the earth is not round, but 111,000 meters is considered
57     // generally acceptable
58     private static final int APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR = 111_000;
59 
60     // we pick a value 1 meter away from 90.0 degrees in order to keep cosine(MAX_LATITUDE) to a
61     // non-zero value, so that we avoid divide by zero errors
62     private static final double MAX_LATITUDE =
63             90.0 - (1.0 / APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR);
64 
65     private final float mAccuracyM;
66     private final Clock mClock;
67     private final Random mRandom;
68 
69     @GuardedBy("this")
70     private double mLatitudeOffsetM;
71     @GuardedBy("this")
72     private double mLongitudeOffsetM;
73     @GuardedBy("this")
74     private long mNextUpdateRealtimeMs;
75 
76     @GuardedBy("this")
77     @Nullable private Location mCachedFineLocation;
78     @GuardedBy("this")
79     @Nullable private Location mCachedCoarseLocation;
80 
81     @GuardedBy("this")
82     @Nullable private LocationResult mCachedFineLocationResult;
83     @GuardedBy("this")
84     @Nullable private LocationResult mCachedCoarseLocationResult;
85 
LocationFudger(float accuracyM)86     public LocationFudger(float accuracyM) {
87         this(accuracyM, SystemClock.elapsedRealtimeClock(), new SecureRandom());
88     }
89 
90     @VisibleForTesting
LocationFudger(float accuracyM, Clock clock, Random random)91     LocationFudger(float accuracyM, Clock clock, Random random) {
92         mClock = clock;
93         mRandom = random;
94         mAccuracyM = Math.max(accuracyM, MIN_ACCURACY_M);
95 
96         resetOffsets();
97     }
98 
99     /**
100      * Resets the random offsets completely.
101      */
resetOffsets()102     public void resetOffsets() {
103         mLatitudeOffsetM = nextRandomOffset();
104         mLongitudeOffsetM = nextRandomOffset();
105         mNextUpdateRealtimeMs = mClock.millis() + OFFSET_UPDATE_INTERVAL_MS;
106     }
107 
108     /**
109      * Coarsens a LocationResult by coarsening every location within the location result with
110      * {@link #createCoarse(Location)}.
111      */
createCoarse(LocationResult fineLocationResult)112     public LocationResult createCoarse(LocationResult fineLocationResult) {
113         synchronized (this) {
114             if (fineLocationResult == mCachedFineLocationResult
115                     || fineLocationResult == mCachedCoarseLocationResult) {
116                 return mCachedCoarseLocationResult;
117             }
118         }
119 
120         LocationResult coarseLocationResult = fineLocationResult.map(this::createCoarse);
121 
122         synchronized (this) {
123             mCachedFineLocationResult = fineLocationResult;
124             mCachedCoarseLocationResult = coarseLocationResult;
125         }
126 
127         return coarseLocationResult;
128     }
129 
130     /**
131      * Create a coarse location using two technique, random offsets and snap-to-grid.
132      *
133      * First we add a random offset to mitigate against detecting grid transitions. Without a random
134      * offset it is possible to detect a user's position quite accurately when they cross a grid
135      * boundary. The random offset changes very slowly over time, to mitigate against taking many
136      * location samples and averaging them out. Second we snap-to-grid (quantize). This has the nice
137      * property of producing stable results, and mitigating against taking many samples to average
138      * out a random offset.
139      */
createCoarse(Location fine)140     public Location createCoarse(Location fine) {
141         synchronized (this) {
142             if (fine == mCachedFineLocation || fine == mCachedCoarseLocation) {
143                 return mCachedCoarseLocation;
144             }
145         }
146 
147         // update the offsets in use
148         updateOffsets();
149 
150         Location coarse = new Location(fine);
151 
152         // clear any fields that could leak more detailed location information
153         coarse.removeBearing();
154         coarse.removeSpeed();
155         coarse.removeAltitude();
156         coarse.setExtras(null);
157 
158         double latitude = wrapLatitude(coarse.getLatitude());
159         double longitude = wrapLongitude(coarse.getLongitude());
160 
161         // add offsets - update longitude first using the non-offset latitude
162         longitude += wrapLongitude(metersToDegreesLongitude(mLongitudeOffsetM, latitude));
163         latitude += wrapLatitude(metersToDegreesLatitude(mLatitudeOffsetM));
164 
165         // quantize location by snapping to a grid. this is the primary means of obfuscation. it
166         // gives nice consistent results and is very effective at hiding the true location (as long
167         // as you are not sitting on a grid boundary, which the random offsets mitigate).
168         //
169         // note that we quantize the latitude first, since the longitude quantization depends on the
170         // latitude value and so leaks information about the latitude
171         double latGranularity = metersToDegreesLatitude(mAccuracyM);
172         latitude = wrapLatitude(Math.round(latitude / latGranularity) * latGranularity);
173         double lonGranularity = metersToDegreesLongitude(mAccuracyM, latitude);
174         longitude = wrapLongitude(Math.round(longitude / lonGranularity) * lonGranularity);
175 
176         coarse.setLatitude(latitude);
177         coarse.setLongitude(longitude);
178         coarse.setAccuracy(Math.max(mAccuracyM, coarse.getAccuracy()));
179 
180         synchronized (this) {
181             mCachedFineLocation = fine;
182             mCachedCoarseLocation = coarse;
183         }
184 
185         return coarse;
186     }
187 
188     /**
189      * Update the random offsets over time.
190      *
191      * If the random offset was reset for every location fix then an application could more easily
192      * average location results over time, especially when the location is near a grid boundary. On
193      * the other hand if the random offset is constant then if an application finds a way to reverse
194      * engineer the offset they would be able to detect location at grid boundaries very accurately.
195      * So we choose a random offset and then very slowly move it, to make both approaches very hard.
196      * The random offset does not need to be large, because snap-to-grid is the primary obfuscation
197      * mechanism. It just needs to be large enough to stop information leakage as we cross grid
198      * boundaries.
199      */
updateOffsets()200     private synchronized void updateOffsets() {
201         long now = mClock.millis();
202         if (now < mNextUpdateRealtimeMs) {
203             return;
204         }
205 
206         mLatitudeOffsetM = (OLD_WEIGHT * mLatitudeOffsetM) + (NEW_WEIGHT * nextRandomOffset());
207         mLongitudeOffsetM = (OLD_WEIGHT * mLongitudeOffsetM) + (NEW_WEIGHT * nextRandomOffset());
208         mNextUpdateRealtimeMs = now + OFFSET_UPDATE_INTERVAL_MS;
209     }
210 
nextRandomOffset()211     private double nextRandomOffset() {
212         return mRandom.nextGaussian() * (mAccuracyM / 4.0);
213     }
214 
wrapLatitude(double lat)215     private static double wrapLatitude(double lat) {
216         if (lat > MAX_LATITUDE) {
217             lat = MAX_LATITUDE;
218         }
219         if (lat < -MAX_LATITUDE) {
220             lat = -MAX_LATITUDE;
221         }
222         return lat;
223     }
224 
wrapLongitude(double lon)225     private static double wrapLongitude(double lon) {
226         lon %= 360.0;  // wraps into range (-360.0, +360.0)
227         if (lon >= 180.0) {
228             lon -= 360.0;
229         }
230         if (lon < -180.0) {
231             lon += 360.0;
232         }
233         return lon;
234     }
235 
metersToDegreesLatitude(double distance)236     private static double metersToDegreesLatitude(double distance) {
237         return distance / APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR;
238     }
239 
240     // requires latitude since longitudinal distances change with distance from equator.
metersToDegreesLongitude(double distance, double lat)241     private static double metersToDegreesLongitude(double distance, double lat) {
242         return distance / APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR / Math.cos(Math.toRadians(lat));
243     }
244 }
245