| /* |
| * Copyright (C) 2012 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.android.server.location; |
| |
| import android.content.Context; |
| import android.database.ContentObserver; |
| import android.location.Location; |
| import android.os.Bundle; |
| import android.os.Handler; |
| import android.os.SystemClock; |
| import android.provider.Settings; |
| import android.util.Log; |
| |
| import java.io.FileDescriptor; |
| import java.io.PrintWriter; |
| import java.security.SecureRandom; |
| |
| |
| /** |
| * Contains the logic to obfuscate (fudge) locations for coarse applications. |
| * |
| * <p>The goal is just to prevent applications with only |
| * the coarse location permission from receiving a fine location. |
| */ |
| public class LocationFudger { |
| private static final boolean D = false; |
| private static final String TAG = "LocationFudge"; |
| |
| /** |
| * Default coarse accuracy in meters. |
| */ |
| private static final float DEFAULT_ACCURACY_IN_METERS = 2000.0f; |
| |
| /** |
| * Minimum coarse accuracy in meters. |
| */ |
| private static final float MINIMUM_ACCURACY_IN_METERS = 200.0f; |
| |
| /** |
| * Secure settings key for coarse accuracy. |
| */ |
| private static final String COARSE_ACCURACY_CONFIG_NAME = "locationCoarseAccuracy"; |
| |
| /** |
| * This is the fastest interval that applications can receive coarse |
| * locations. |
| */ |
| public static final long FASTEST_INTERVAL_MS = 10 * 60 * 1000; // 10 minutes |
| |
| /** |
| * The duration until we change the random offset. |
| */ |
| private static final long CHANGE_INTERVAL_MS = 60 * 60 * 1000; // 1 hour |
| |
| /** |
| * The percentage that we change the random offset at every interval. |
| * |
| * <p>0.0 indicates the random offset doesn't change. 1.0 |
| * indicates the random offset is completely replaced every interval. |
| */ |
| private static final double CHANGE_PER_INTERVAL = 0.03; // 3% change |
| |
| // Pre-calculated weights used to move the random offset. |
| // |
| // The goal is to iterate on the previous offset, but keep |
| // the resulting standard deviation the same. The variance of |
| // two gaussian distributions summed together is equal to the |
| // sum of the variance of each distribution. So some quick |
| // algebra results in the following sqrt calculation to |
| // weigh in a new offset while keeping the final standard |
| // deviation unchanged. |
| private static final double NEW_WEIGHT = CHANGE_PER_INTERVAL; |
| private static final double PREVIOUS_WEIGHT = Math.sqrt(1 - NEW_WEIGHT * NEW_WEIGHT); |
| |
| /** |
| * This number actually varies because the earth is not round, but |
| * 111,000 meters is considered generally acceptable. |
| */ |
| private static final int APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR = 111000; |
| |
| /** |
| * Maximum latitude. |
| * |
| * <p>We pick a value 1 meter away from 90.0 degrees in order |
| * to keep cosine(MAX_LATITUDE) to a non-zero value, so that we avoid |
| * divide by zero fails. |
| */ |
| private static final double MAX_LATITUDE = 90.0 - |
| (1.0 / APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR); |
| |
| private final Object mLock = new Object(); |
| private final SecureRandom mRandom = new SecureRandom(); |
| |
| /** |
| * Used to monitor coarse accuracy secure setting for changes. |
| */ |
| private final ContentObserver mSettingsObserver; |
| |
| /** |
| * Used to resolve coarse accuracy setting. |
| */ |
| private final Context mContext; |
| |
| // all fields below protected by mLock |
| private double mOffsetLatitudeMeters; |
| private double mOffsetLongitudeMeters; |
| private long mNextInterval; |
| |
| /** |
| * Best location accuracy allowed for coarse applications. |
| * This value should only be set by {@link #setAccuracyInMetersLocked(float)}. |
| */ |
| private float mAccuracyInMeters; |
| |
| /** |
| * The distance between grids for snap-to-grid. See {@link #createCoarse}. |
| * This value should only be set by {@link #setAccuracyInMetersLocked(float)}. |
| */ |
| private double mGridSizeInMeters; |
| |
| /** |
| * Standard deviation of the (normally distributed) random offset applied |
| * to coarse locations. It does not need to be as large as |
| * {@link #COARSE_ACCURACY_METERS} because snap-to-grid is the primary obfuscation |
| * method. See further details in the implementation. |
| * This value should only be set by {@link #setAccuracyInMetersLocked(float)}. |
| */ |
| private double mStandardDeviationInMeters; |
| |
| public LocationFudger(Context context, Handler handler) { |
| mContext = context; |
| mSettingsObserver = new ContentObserver(handler) { |
| @Override |
| public void onChange(boolean selfChange) { |
| setAccuracyInMeters(loadCoarseAccuracy()); |
| } |
| }; |
| mContext.getContentResolver().registerContentObserver(Settings.Secure.getUriFor( |
| COARSE_ACCURACY_CONFIG_NAME), false, mSettingsObserver); |
| |
| float accuracy = loadCoarseAccuracy(); |
| synchronized (mLock) { |
| setAccuracyInMetersLocked(accuracy); |
| mOffsetLatitudeMeters = nextOffsetLocked(); |
| mOffsetLongitudeMeters = nextOffsetLocked(); |
| mNextInterval = SystemClock.elapsedRealtime() + CHANGE_INTERVAL_MS; |
| } |
| } |
| |
| /** |
| * Get the cached coarse location, or generate a new one and cache it. |
| */ |
| public Location getOrCreate(Location location) { |
| synchronized (mLock) { |
| Location coarse = location.getExtraLocation(Location.EXTRA_COARSE_LOCATION); |
| if (coarse == null) { |
| return addCoarseLocationExtraLocked(location); |
| } |
| if (coarse.getAccuracy() < mAccuracyInMeters) { |
| return addCoarseLocationExtraLocked(location); |
| } |
| return coarse; |
| } |
| } |
| |
| private Location addCoarseLocationExtraLocked(Location location) { |
| Location coarse = createCoarseLocked(location); |
| Bundle extras = location.getExtras(); |
| if (extras == null) { |
| extras = new Bundle(); |
| } |
| extras.putParcelable(Location.EXTRA_COARSE_LOCATION, coarse); |
| location.setExtras(extras); |
| return coarse; |
| } |
| |
| /** |
| * Create a coarse location. |
| * |
| * <p>Two techniques are used: random offsets and snap-to-grid. |
| * |
| * <p>First we add a random offset. This mitigates against detecting |
| * grid transitions. Without a random offset it is possible to detect |
| * a users position very accurately when they cross a grid boundary. |
| * The random offset changes very slowly over time, to mitigate against |
| * taking many location samples and averaging them out. |
| * |
| * <p>Second we snap-to-grid (quantize). This has the nice property of |
| * producing stable results, and mitigating against taking many samples |
| * to average out a random offset. |
| */ |
| private Location createCoarseLocked(Location fine) { |
| Location coarse = new Location(fine); |
| |
| // clean all the optional information off the location, because |
| // this can leak detailed location information |
| coarse.removeBearing(); |
| coarse.removeSpeed(); |
| coarse.removeAltitude(); |
| coarse.setExtras(null); |
| |
| double lat = coarse.getLatitude(); |
| double lon = coarse.getLongitude(); |
| |
| // wrap |
| lat = wrapLatitude(lat); |
| lon = wrapLongitude(lon); |
| |
| // Step 1) apply a random offset |
| // |
| // The goal of the random offset is to prevent the application |
| // from determining that the device is on a grid boundary |
| // when it crosses from one grid to the next. |
| // |
| // We apply the offset even if the location already claims to be |
| // inaccurate, because it may be more accurate than claimed. |
| updateRandomOffsetLocked(); |
| // perform lon first whilst lat is still within bounds |
| lon += metersToDegreesLongitude(mOffsetLongitudeMeters, lat); |
| lat += metersToDegreesLatitude(mOffsetLatitudeMeters); |
| if (D) Log.d(TAG, String.format("applied offset of %.0f, %.0f (meters)", |
| mOffsetLongitudeMeters, mOffsetLatitudeMeters)); |
| |
| // wrap |
| lat = wrapLatitude(lat); |
| lon = wrapLongitude(lon); |
| |
| // Step 2) Snap-to-grid (quantize) |
| // |
| // This is the primary means of obfuscation. It gives nice consistent |
| // results and is very effective at hiding the true location |
| // (as long as you are not sitting on a grid boundary, which |
| // step 1 mitigates). |
| // |
| // Note we quantize the latitude first, since the longitude |
| // quantization depends on the latitude value and so leaks information |
| // about the latitude |
| double latGranularity = metersToDegreesLatitude(mGridSizeInMeters); |
| lat = Math.round(lat / latGranularity) * latGranularity; |
| double lonGranularity = metersToDegreesLongitude(mGridSizeInMeters, lat); |
| lon = Math.round(lon / lonGranularity) * lonGranularity; |
| |
| // wrap again |
| lat = wrapLatitude(lat); |
| lon = wrapLongitude(lon); |
| |
| // apply |
| coarse.setLatitude(lat); |
| coarse.setLongitude(lon); |
| coarse.setAccuracy(Math.max(mAccuracyInMeters, coarse.getAccuracy())); |
| |
| if (D) Log.d(TAG, "fudged " + fine + " to " + coarse); |
| return coarse; |
| } |
| |
| /** |
| * Update the random offset over time. |
| * |
| * <p>If the random offset was new for every location |
| * fix then an application can more easily average location results |
| * over time, |
| * especially when the location is near a grid boundary. On the |
| * other hand if the random offset is constant then if an application |
| * found a way to reverse engineer the offset they would be able |
| * to detect location at grid boundaries very accurately. So |
| * we choose a random offset and then very slowly move it, to |
| * make both approaches very hard. |
| * |
| * <p>The random offset does not need to be large, because snap-to-grid |
| * is the primary obfuscation mechanism. It just needs to be large |
| * enough to stop information leakage as we cross grid boundaries. |
| */ |
| private void updateRandomOffsetLocked() { |
| long now = SystemClock.elapsedRealtime(); |
| if (now < mNextInterval) { |
| return; |
| } |
| |
| if (D) Log.d(TAG, String.format("old offset: %.0f, %.0f (meters)", |
| mOffsetLongitudeMeters, mOffsetLatitudeMeters)); |
| |
| // ok, need to update the random offset |
| mNextInterval = now + CHANGE_INTERVAL_MS; |
| |
| mOffsetLatitudeMeters *= PREVIOUS_WEIGHT; |
| mOffsetLatitudeMeters += NEW_WEIGHT * nextOffsetLocked(); |
| mOffsetLongitudeMeters *= PREVIOUS_WEIGHT; |
| mOffsetLongitudeMeters += NEW_WEIGHT * nextOffsetLocked(); |
| |
| if (D) Log.d(TAG, String.format("new offset: %.0f, %.0f (meters)", |
| mOffsetLongitudeMeters, mOffsetLatitudeMeters)); |
| } |
| |
| private double nextOffsetLocked() { |
| return mRandom.nextGaussian() * mStandardDeviationInMeters; |
| } |
| |
| private static double wrapLatitude(double lat) { |
| if (lat > MAX_LATITUDE) { |
| lat = MAX_LATITUDE; |
| } |
| if (lat < -MAX_LATITUDE) { |
| lat = -MAX_LATITUDE; |
| } |
| return lat; |
| } |
| |
| private static double wrapLongitude(double lon) { |
| lon %= 360.0; // wraps into range (-360.0, +360.0) |
| if (lon >= 180.0) { |
| lon -= 360.0; |
| } |
| if (lon < -180.0) { |
| lon += 360.0; |
| } |
| return lon; |
| } |
| |
| private static double metersToDegreesLatitude(double distance) { |
| return distance / APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR; |
| } |
| |
| /** |
| * Requires latitude since longitudinal distances change with distance from equator. |
| */ |
| private static double metersToDegreesLongitude(double distance, double lat) { |
| return distance / APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR / Math.cos(Math.toRadians(lat)); |
| } |
| |
| public void dump(FileDescriptor fd, PrintWriter pw, String[] args) { |
| pw.println(String.format("offset: %.0f, %.0f (meters)", mOffsetLongitudeMeters, |
| mOffsetLatitudeMeters)); |
| } |
| |
| /** |
| * This is the main control: call this to set the best location accuracy |
| * allowed for coarse applications and all derived values. |
| */ |
| private void setAccuracyInMetersLocked(float accuracyInMeters) { |
| mAccuracyInMeters = Math.max(accuracyInMeters, MINIMUM_ACCURACY_IN_METERS); |
| if (D) { |
| Log.d(TAG, "setAccuracyInMetersLocked: new accuracy = " + mAccuracyInMeters); |
| } |
| mGridSizeInMeters = mAccuracyInMeters; |
| mStandardDeviationInMeters = mGridSizeInMeters / 4.0; |
| } |
| |
| /** |
| * Same as setAccuracyInMetersLocked without the pre-lock requirement. |
| */ |
| private void setAccuracyInMeters(float accuracyInMeters) { |
| synchronized (mLock) { |
| setAccuracyInMetersLocked(accuracyInMeters); |
| } |
| } |
| |
| /** |
| * Loads the coarse accuracy value from secure settings. |
| */ |
| private float loadCoarseAccuracy() { |
| String newSetting = Settings.Secure.getString(mContext.getContentResolver(), |
| COARSE_ACCURACY_CONFIG_NAME); |
| if (D) { |
| Log.d(TAG, "loadCoarseAccuracy: newSetting = \"" + newSetting + "\""); |
| } |
| if (newSetting == null) { |
| return DEFAULT_ACCURACY_IN_METERS; |
| } |
| try { |
| return Float.parseFloat(newSetting); |
| } catch (NumberFormatException e) { |
| return DEFAULT_ACCURACY_IN_METERS; |
| } |
| } |
| } |