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; 22 import android.content.Context; 23 import android.database.ContentObserver; 24 import android.location.Location; 25 import android.os.Handler; 26 import android.os.SystemClock; 27 import android.provider.Settings; 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 41 /** 42 * Default coarse accuracy in meters. 43 */ 44 private static final float DEFAULT_ACCURACY_IN_METERS = 2000.0f; 45 46 /** 47 * Minimum coarse accuracy in meters. 48 */ 49 private static final float MINIMUM_ACCURACY_IN_METERS = 200.0f; 50 51 /** 52 * Secure settings key for coarse accuracy. 53 */ 54 private static final String COARSE_ACCURACY_CONFIG_NAME = "locationCoarseAccuracy"; 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 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 116 // all fields below protected by mLock 117 private double mOffsetLatitudeMeters; 118 private double mOffsetLongitudeMeters; 119 private long mNextInterval; 120 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 } 160 } 161 162 /** 163 * Get the cached coarse location, or generate a new one and cache it. 164 */ 165 public Location getOrCreate(Location location) { 166 synchronized (mLock) { 167 Location coarse = location.getExtraLocation(Location.EXTRA_COARSE_LOCATION); 168 if (coarse == null) { 169 return addCoarseLocationExtraLocked(location); 170 } 171 if (coarse.getAccuracy() < mAccuracyInMeters) { 172 return addCoarseLocationExtraLocked(location); 173 } 174 return coarse; 175 } 176 } 177 178 private Location addCoarseLocationExtraLocked(Location location) { 179 Location coarse = createCoarseLocked(location); 180 location.setExtraLocation(Location.EXTRA_COARSE_LOCATION, coarse); 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 */ 199 private Location createCoarseLocked(Location fine) { 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. 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)); 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 245 double latGranularity = metersToDegreesLatitude(mGridSizeInMeters); 246 lat = Math.round(lat / latGranularity) * latGranularity; 247 double lonGranularity = metersToDegreesLongitude(mGridSizeInMeters, lat); 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); 257 coarse.setAccuracy(Math.max(mAccuracyInMeters, coarse.getAccuracy())); 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; 293 mOffsetLatitudeMeters += NEW_WEIGHT * nextOffsetLocked(); 294 mOffsetLongitudeMeters *= PREVIOUS_WEIGHT; 295 mOffsetLongitudeMeters += NEW_WEIGHT * nextOffsetLocked(); 296 297 if (D) Log.d(TAG, String.format("new offset: %.0f, %.0f (meters)", 298 mOffsetLongitudeMeters, mOffsetLatitudeMeters)); 299 } 300 301 private double nextOffsetLocked() { 302 return mRandom.nextGaussian() * mStandardDeviationInMeters; 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 } 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 } 382 } 383
