1 files changed, 382 insertions, 0 deletions
diff --git a/services/core/java/com/android/server/location/LocationFudger.java b/services/core/java/com/android/server/location/LocationFudger.java
new file mode 100644
index 0000000..ae71fe3
--- /dev/null
+++ b/services/core/java/com/android/server/location/LocationFudger.java
@@ -0,0 +1,382 @@
+/*
+ * 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 java.io.FileDescriptor;
+import java.io.PrintWriter;
+import java.security.SecureRandom;
+import android.content.Context;
+import android.database.ContentObserver;
+import android.location.Location;
+import android.os.Handler;
+import android.os.SystemClock;
+import android.provider.Settings;
+import android.util.Log;
+
+
+/**
+ * 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);
+        location.setExtraLocation(Location.EXTRA_COARSE_LOCATION, coarse);
+        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;
+        }
+    }
+}