content: /*
   * 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;
          }
      }
  }
  