Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2012 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; |
| 18 | |
| 19 | import java.io.FileDescriptor; |
| 20 | import java.io.PrintWriter; |
| 21 | import java.security.SecureRandom; |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 22 | import android.content.Context; |
| 23 | import android.database.ContentObserver; |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 24 | import android.location.Location; |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 25 | import android.os.Handler; |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 26 | import android.os.SystemClock; |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 27 | import android.provider.Settings; |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 28 | import android.util.Log; |
| 29 | |
| 30 | |
| 31 | /** |
| 32 | * Contains the logic to obfuscate (fudge) locations for coarse applications. |
| 33 | * |
| 34 | * <p>The goal is just to prevent applications with only |
| 35 | * the coarse location permission from receiving a fine location. |
| 36 | */ |
| 37 | public class LocationFudger { |
| 38 | private static final boolean D = false; |
| 39 | private static final String TAG = "LocationFudge"; |
| 40 | |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 41 | /** |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 42 | * Default coarse accuracy in meters. |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 43 | */ |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 44 | private static final float DEFAULT_ACCURACY_IN_METERS = 2000.0f; |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 45 | |
| 46 | /** |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 47 | * Minimum coarse accuracy in meters. |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 48 | */ |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 49 | private static final float MINIMUM_ACCURACY_IN_METERS = 200.0f; |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 50 | |
| 51 | /** |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 52 | * Secure settings key for coarse accuracy. |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 53 | */ |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 54 | private static final String COARSE_ACCURACY_CONFIG_NAME = "locationCoarseAccuracy"; |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 55 | |
| 56 | /** |
| 57 | * This is the fastest interval that applications can receive coarse |
| 58 | * locations. |
| 59 | */ |
| 60 | public static final long FASTEST_INTERVAL_MS = 10 * 60 * 1000; // 10 minutes |
| 61 | |
| 62 | /** |
| 63 | * The duration until we change the random offset. |
| 64 | */ |
| 65 | private static final long CHANGE_INTERVAL_MS = 60 * 60 * 1000; // 1 hour |
| 66 | |
| 67 | /** |
| 68 | * The percentage that we change the random offset at every interval. |
| 69 | * |
| 70 | * <p>0.0 indicates the random offset doesn't change. 1.0 |
| 71 | * indicates the random offset is completely replaced every interval. |
| 72 | */ |
| 73 | private static final double CHANGE_PER_INTERVAL = 0.03; // 3% change |
| 74 | |
| 75 | // Pre-calculated weights used to move the random offset. |
| 76 | // |
| 77 | // The goal is to iterate on the previous offset, but keep |
| 78 | // the resulting standard deviation the same. The variance of |
| 79 | // two gaussian distributions summed together is equal to the |
| 80 | // sum of the variance of each distribution. So some quick |
| 81 | // algebra results in the following sqrt calculation to |
| 82 | // weigh in a new offset while keeping the final standard |
| 83 | // deviation unchanged. |
| 84 | private static final double NEW_WEIGHT = CHANGE_PER_INTERVAL; |
| 85 | private static final double PREVIOUS_WEIGHT = Math.sqrt(1 - NEW_WEIGHT * NEW_WEIGHT); |
| 86 | |
| 87 | /** |
| 88 | * This number actually varies because the earth is not round, but |
| 89 | * 111,000 meters is considered generally acceptable. |
| 90 | */ |
| 91 | private static final int APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR = 111000; |
| 92 | |
| 93 | /** |
| 94 | * Maximum latitude. |
| 95 | * |
| 96 | * <p>We pick a value 1 meter away from 90.0 degrees in order |
| 97 | * to keep cosine(MAX_LATITUDE) to a non-zero value, so that we avoid |
| 98 | * divide by zero fails. |
| 99 | */ |
| 100 | private static final double MAX_LATITUDE = 90.0 - |
| 101 | (1.0 / APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR); |
| 102 | |
| 103 | private final Object mLock = new Object(); |
| 104 | private final SecureRandom mRandom = new SecureRandom(); |
| 105 | |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 106 | /** |
| 107 | * Used to monitor coarse accuracy secure setting for changes. |
| 108 | */ |
| 109 | private final ContentObserver mSettingsObserver; |
| 110 | |
| 111 | /** |
| 112 | * Used to resolve coarse accuracy setting. |
| 113 | */ |
| 114 | private final Context mContext; |
| 115 | |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 116 | // all fields below protected by mLock |
| 117 | private double mOffsetLatitudeMeters; |
| 118 | private double mOffsetLongitudeMeters; |
| 119 | private long mNextInterval; |
| 120 | |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 121 | /** |
| 122 | * Best location accuracy allowed for coarse applications. |
| 123 | * This value should only be set by {@link #setAccuracyInMetersLocked(float)}. |
| 124 | */ |
| 125 | private float mAccuracyInMeters; |
| 126 | |
| 127 | /** |
| 128 | * The distance between grids for snap-to-grid. See {@link #createCoarse}. |
| 129 | * This value should only be set by {@link #setAccuracyInMetersLocked(float)}. |
| 130 | */ |
| 131 | private double mGridSizeInMeters; |
| 132 | |
| 133 | /** |
| 134 | * Standard deviation of the (normally distributed) random offset applied |
| 135 | * to coarse locations. It does not need to be as large as |
| 136 | * {@link #COARSE_ACCURACY_METERS} because snap-to-grid is the primary obfuscation |
| 137 | * method. See further details in the implementation. |
| 138 | * This value should only be set by {@link #setAccuracyInMetersLocked(float)}. |
| 139 | */ |
| 140 | private double mStandardDeviationInMeters; |
| 141 | |
| 142 | public LocationFudger(Context context, Handler handler) { |
| 143 | mContext = context; |
| 144 | mSettingsObserver = new ContentObserver(handler) { |
| 145 | @Override |
| 146 | public void onChange(boolean selfChange) { |
| 147 | setAccuracyInMeters(loadCoarseAccuracy()); |
| 148 | } |
| 149 | }; |
| 150 | mContext.getContentResolver().registerContentObserver(Settings.Secure.getUriFor( |
| 151 | COARSE_ACCURACY_CONFIG_NAME), false, mSettingsObserver); |
| 152 | |
| 153 | float accuracy = loadCoarseAccuracy(); |
| 154 | synchronized (mLock) { |
| 155 | setAccuracyInMetersLocked(accuracy); |
| 156 | mOffsetLatitudeMeters = nextOffsetLocked(); |
| 157 | mOffsetLongitudeMeters = nextOffsetLocked(); |
| 158 | mNextInterval = SystemClock.elapsedRealtime() + CHANGE_INTERVAL_MS; |
| 159 | } |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 160 | } |
| 161 | |
| 162 | /** |
| 163 | * Get the cached coarse location, or generate a new one and cache it. |
| 164 | */ |
| 165 | public Location getOrCreate(Location location) { |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 166 | synchronized (mLock) { |
Victoria Lease | 09016ab | 2012-09-16 12:33:15 -0700 | [diff] [blame] | 167 | Location coarse = location.getExtraLocation(Location.EXTRA_COARSE_LOCATION); |
| 168 | if (coarse == null) { |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 169 | return addCoarseLocationExtraLocked(location); |
| 170 | } |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 171 | if (coarse.getAccuracy() < mAccuracyInMeters) { |
| 172 | return addCoarseLocationExtraLocked(location); |
| 173 | } |
| 174 | return coarse; |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 175 | } |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 176 | } |
| 177 | |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 178 | private Location addCoarseLocationExtraLocked(Location location) { |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 179 | Location coarse = createCoarseLocked(location); |
Victoria Lease | 09016ab | 2012-09-16 12:33:15 -0700 | [diff] [blame] | 180 | location.setExtraLocation(Location.EXTRA_COARSE_LOCATION, coarse); |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 181 | return coarse; |
| 182 | } |
| 183 | |
| 184 | /** |
| 185 | * Create a coarse location. |
| 186 | * |
| 187 | * <p>Two techniques are used: random offsets and snap-to-grid. |
| 188 | * |
| 189 | * <p>First we add a random offset. This mitigates against detecting |
| 190 | * grid transitions. Without a random offset it is possible to detect |
| 191 | * a users position very accurately when they cross a grid boundary. |
| 192 | * The random offset changes very slowly over time, to mitigate against |
| 193 | * taking many location samples and averaging them out. |
| 194 | * |
| 195 | * <p>Second we snap-to-grid (quantize). This has the nice property of |
| 196 | * producing stable results, and mitigating against taking many samples |
| 197 | * to average out a random offset. |
| 198 | */ |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 199 | private Location createCoarseLocked(Location fine) { |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 200 | Location coarse = new Location(fine); |
| 201 | |
| 202 | // clean all the optional information off the location, because |
| 203 | // this can leak detailed location information |
| 204 | coarse.removeBearing(); |
| 205 | coarse.removeSpeed(); |
| 206 | coarse.removeAltitude(); |
| 207 | coarse.setExtras(null); |
| 208 | |
| 209 | double lat = coarse.getLatitude(); |
| 210 | double lon = coarse.getLongitude(); |
| 211 | |
| 212 | // wrap |
| 213 | lat = wrapLatitude(lat); |
| 214 | lon = wrapLongitude(lon); |
| 215 | |
| 216 | // Step 1) apply a random offset |
| 217 | // |
| 218 | // The goal of the random offset is to prevent the application |
| 219 | // from determining that the device is on a grid boundary |
| 220 | // when it crosses from one grid to the next. |
| 221 | // |
| 222 | // We apply the offset even if the location already claims to be |
| 223 | // inaccurate, because it may be more accurate than claimed. |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 224 | updateRandomOffsetLocked(); |
| 225 | // perform lon first whilst lat is still within bounds |
| 226 | lon += metersToDegreesLongitude(mOffsetLongitudeMeters, lat); |
| 227 | lat += metersToDegreesLatitude(mOffsetLatitudeMeters); |
| 228 | if (D) Log.d(TAG, String.format("applied offset of %.0f, %.0f (meters)", |
| 229 | mOffsetLongitudeMeters, mOffsetLatitudeMeters)); |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 230 | |
| 231 | // wrap |
| 232 | lat = wrapLatitude(lat); |
| 233 | lon = wrapLongitude(lon); |
| 234 | |
| 235 | // Step 2) Snap-to-grid (quantize) |
| 236 | // |
| 237 | // This is the primary means of obfuscation. It gives nice consistent |
| 238 | // results and is very effective at hiding the true location |
| 239 | // (as long as you are not sitting on a grid boundary, which |
| 240 | // step 1 mitigates). |
| 241 | // |
| 242 | // Note we quantize the latitude first, since the longitude |
| 243 | // quantization depends on the latitude value and so leaks information |
| 244 | // about the latitude |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 245 | double latGranularity = metersToDegreesLatitude(mGridSizeInMeters); |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 246 | lat = Math.round(lat / latGranularity) * latGranularity; |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 247 | double lonGranularity = metersToDegreesLongitude(mGridSizeInMeters, lat); |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 248 | lon = Math.round(lon / lonGranularity) * lonGranularity; |
| 249 | |
| 250 | // wrap again |
| 251 | lat = wrapLatitude(lat); |
| 252 | lon = wrapLongitude(lon); |
| 253 | |
| 254 | // apply |
| 255 | coarse.setLatitude(lat); |
| 256 | coarse.setLongitude(lon); |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 257 | coarse.setAccuracy(Math.max(mAccuracyInMeters, coarse.getAccuracy())); |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 258 | |
| 259 | if (D) Log.d(TAG, "fudged " + fine + " to " + coarse); |
| 260 | return coarse; |
| 261 | } |
| 262 | |
| 263 | /** |
| 264 | * Update the random offset over time. |
| 265 | * |
| 266 | * <p>If the random offset was new for every location |
| 267 | * fix then an application can more easily average location results |
| 268 | * over time, |
| 269 | * especially when the location is near a grid boundary. On the |
| 270 | * other hand if the random offset is constant then if an application |
| 271 | * found a way to reverse engineer the offset they would be able |
| 272 | * to detect location at grid boundaries very accurately. So |
| 273 | * we choose a random offset and then very slowly move it, to |
| 274 | * make both approaches very hard. |
| 275 | * |
| 276 | * <p>The random offset does not need to be large, because snap-to-grid |
| 277 | * is the primary obfuscation mechanism. It just needs to be large |
| 278 | * enough to stop information leakage as we cross grid boundaries. |
| 279 | */ |
| 280 | private void updateRandomOffsetLocked() { |
| 281 | long now = SystemClock.elapsedRealtime(); |
| 282 | if (now < mNextInterval) { |
| 283 | return; |
| 284 | } |
| 285 | |
| 286 | if (D) Log.d(TAG, String.format("old offset: %.0f, %.0f (meters)", |
| 287 | mOffsetLongitudeMeters, mOffsetLatitudeMeters)); |
| 288 | |
| 289 | // ok, need to update the random offset |
| 290 | mNextInterval = now + CHANGE_INTERVAL_MS; |
| 291 | |
| 292 | mOffsetLatitudeMeters *= PREVIOUS_WEIGHT; |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 293 | mOffsetLatitudeMeters += NEW_WEIGHT * nextOffsetLocked(); |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 294 | mOffsetLongitudeMeters *= PREVIOUS_WEIGHT; |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 295 | mOffsetLongitudeMeters += NEW_WEIGHT * nextOffsetLocked(); |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 296 | |
| 297 | if (D) Log.d(TAG, String.format("new offset: %.0f, %.0f (meters)", |
| 298 | mOffsetLongitudeMeters, mOffsetLatitudeMeters)); |
| 299 | } |
| 300 | |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 301 | private double nextOffsetLocked() { |
| 302 | return mRandom.nextGaussian() * mStandardDeviationInMeters; |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 303 | } |
| 304 | |
| 305 | private static double wrapLatitude(double lat) { |
| 306 | if (lat > MAX_LATITUDE) { |
| 307 | lat = MAX_LATITUDE; |
| 308 | } |
| 309 | if (lat < -MAX_LATITUDE) { |
| 310 | lat = -MAX_LATITUDE; |
| 311 | } |
| 312 | return lat; |
| 313 | } |
| 314 | |
| 315 | private static double wrapLongitude(double lon) { |
| 316 | lon %= 360.0; // wraps into range (-360.0, +360.0) |
| 317 | if (lon >= 180.0) { |
| 318 | lon -= 360.0; |
| 319 | } |
| 320 | if (lon < -180.0) { |
| 321 | lon += 360.0; |
| 322 | } |
| 323 | return lon; |
| 324 | } |
| 325 | |
| 326 | private static double metersToDegreesLatitude(double distance) { |
| 327 | return distance / APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR; |
| 328 | } |
| 329 | |
| 330 | /** |
| 331 | * Requires latitude since longitudinal distances change with distance from equator. |
| 332 | */ |
| 333 | private static double metersToDegreesLongitude(double distance, double lat) { |
| 334 | return distance / APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR / Math.cos(Math.toRadians(lat)); |
| 335 | } |
| 336 | |
| 337 | public void dump(FileDescriptor fd, PrintWriter pw, String[] args) { |
| 338 | pw.println(String.format("offset: %.0f, %.0f (meters)", mOffsetLongitudeMeters, |
| 339 | mOffsetLatitudeMeters)); |
| 340 | } |
Victoria Lease | df9ec61 | 2012-09-11 15:16:25 -0700 | [diff] [blame] | 341 | |
| 342 | /** |
| 343 | * This is the main control: call this to set the best location accuracy |
| 344 | * allowed for coarse applications and all derived values. |
| 345 | */ |
| 346 | private void setAccuracyInMetersLocked(float accuracyInMeters) { |
| 347 | mAccuracyInMeters = Math.max(accuracyInMeters, MINIMUM_ACCURACY_IN_METERS); |
| 348 | if (D) { |
| 349 | Log.d(TAG, "setAccuracyInMetersLocked: new accuracy = " + mAccuracyInMeters); |
| 350 | } |
| 351 | mGridSizeInMeters = mAccuracyInMeters; |
| 352 | mStandardDeviationInMeters = mGridSizeInMeters / 4.0; |
| 353 | } |
| 354 | |
| 355 | /** |
| 356 | * Same as setAccuracyInMetersLocked without the pre-lock requirement. |
| 357 | */ |
| 358 | private void setAccuracyInMeters(float accuracyInMeters) { |
| 359 | synchronized (mLock) { |
| 360 | setAccuracyInMetersLocked(accuracyInMeters); |
| 361 | } |
| 362 | } |
| 363 | |
| 364 | /** |
| 365 | * Loads the coarse accuracy value from secure settings. |
| 366 | */ |
| 367 | private float loadCoarseAccuracy() { |
| 368 | String newSetting = Settings.Secure.getString(mContext.getContentResolver(), |
| 369 | COARSE_ACCURACY_CONFIG_NAME); |
| 370 | if (D) { |
| 371 | Log.d(TAG, "loadCoarseAccuracy: newSetting = \"" + newSetting + "\""); |
| 372 | } |
| 373 | if (newSetting == null) { |
| 374 | return DEFAULT_ACCURACY_IN_METERS; |
| 375 | } |
| 376 | try { |
| 377 | return Float.parseFloat(newSetting); |
| 378 | } catch (NumberFormatException e) { |
| 379 | return DEFAULT_ACCURACY_IN_METERS; |
| 380 | } |
| 381 | } |
Nick Pelly | 74fa7ea | 2012-08-13 19:36:38 -0700 | [diff] [blame] | 382 | } |