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 android.annotation.Nullable; 20 import android.location.Location; 21 import android.os.SystemClock; 22 23 import com.android.internal.annotations.GuardedBy; 24 import com.android.internal.annotations.VisibleForTesting; 25 26 import java.security.SecureRandom; 27 import java.time.Clock; 28 import java.util.Random; 29 30 /** 31 * Contains the logic to obfuscate (fudge) locations for coarse applications. The goal is just to 32 * prevent applications with only the coarse location permission from receiving a fine location. 33 */ 34 public class LocationFudger { 35 36 // minimum accuracy a coarsened location can have 37 private static final float MIN_ACCURACY_M = 200.0f; 38 39 // how often random offsets are updated 40 @VisibleForTesting 41 static final long OFFSET_UPDATE_INTERVAL_MS = 60 * 60 * 1000; 42 43 // the percentage that we change the random offset at every interval. 0.0 indicates the random 44 // offset doesn't change. 1.0 indicates the random offset is completely replaced every interval 45 private static final double CHANGE_PER_INTERVAL = 0.03; // 3% change 46 47 // weights used to move the random offset. the goal is to iterate on the previous offset, but 48 // keep the resulting standard deviation the same. the variance of two gaussian distributions 49 // summed together is equal to the sum of the variance of each distribution. so some quick 50 // algebra results in the following sqrt calculation to weight in a new offset while keeping the 51 // final standard deviation unchanged. 52 private static final double NEW_WEIGHT = CHANGE_PER_INTERVAL; 53 private static final double OLD_WEIGHT = Math.sqrt(1 - NEW_WEIGHT * NEW_WEIGHT); 54 55 // this number actually varies because the earth is not round, but 111,000 meters is considered 56 // generally acceptable 57 private static final int APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR = 111_000; 58 59 // we pick a value 1 meter away from 90.0 degrees in order to keep cosine(MAX_LATITUDE) to a 60 // non-zero value, so that we avoid divide by zero errors 61 private static final double MAX_LATITUDE = 62 90.0 - (1.0 / APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR); 63 64 private final float mAccuracyM; 65 private final Clock mClock; 66 private final Random mRandom; 67 68 @GuardedBy("this") 69 private double mLatitudeOffsetM; 70 @GuardedBy("this") 71 private double mLongitudeOffsetM; 72 @GuardedBy("this") 73 private long mNextUpdateRealtimeMs; 74 75 @GuardedBy("this") 76 @Nullable private Location mCachedFineLocation; 77 @GuardedBy("this") 78 @Nullable private Location mCachedCoarseLocation; 79 LocationFudger(float accuracyM)80 public LocationFudger(float accuracyM) { 81 this(accuracyM, SystemClock.elapsedRealtimeClock(), new SecureRandom()); 82 } 83 84 @VisibleForTesting LocationFudger(float accuracyM, Clock clock, Random random)85 LocationFudger(float accuracyM, Clock clock, Random random) { 86 mClock = clock; 87 mRandom = random; 88 mAccuracyM = Math.max(accuracyM, MIN_ACCURACY_M); 89 90 resetOffsets(); 91 } 92 93 /** 94 * Resets the random offsets completely. 95 */ resetOffsets()96 public void resetOffsets() { 97 mLatitudeOffsetM = nextRandomOffset(); 98 mLongitudeOffsetM = nextRandomOffset(); 99 mNextUpdateRealtimeMs = mClock.millis() + OFFSET_UPDATE_INTERVAL_MS; 100 } 101 102 /** 103 * Create a coarse location using two technique, random offsets and snap-to-grid. 104 * 105 * First we add a random offset to mitigate against detecting grid transitions. Without a random 106 * offset it is possible to detect a user's position quite accurately when they cross a grid 107 * boundary. The random offset changes very slowly over time, to mitigate against taking many 108 * location samples and averaging them out. Second we snap-to-grid (quantize). This has the nice 109 * property of producing stable results, and mitigating against taking many samples to average 110 * out a random offset. 111 */ createCoarse(Location fine)112 public Location createCoarse(Location fine) { 113 synchronized (this) { 114 if (fine == mCachedFineLocation) { 115 return new Location(mCachedCoarseLocation); 116 } 117 } 118 119 // update the offsets in use 120 updateOffsets(); 121 122 Location coarse = new Location(fine); 123 124 // clear any fields that could leak more detailed location information 125 coarse.removeBearing(); 126 coarse.removeSpeed(); 127 coarse.removeAltitude(); 128 coarse.setExtras(null); 129 130 double latitude = wrapLatitude(coarse.getLatitude()); 131 double longitude = wrapLongitude(coarse.getLongitude()); 132 133 // add offsets - update longitude first using the non-offset latitude 134 longitude += wrapLongitude(metersToDegreesLongitude(mLongitudeOffsetM, latitude)); 135 latitude += wrapLatitude(metersToDegreesLatitude(mLatitudeOffsetM)); 136 137 // quantize location by snapping to a grid. this is the primary means of obfuscation. it 138 // gives nice consistent results and is very effective at hiding the true location (as long 139 // as you are not sitting on a grid boundary, which the random offsets mitigate). 140 // 141 // note that we quantize the latitude first, since the longitude quantization depends on the 142 // latitude value and so leaks information about the latitude 143 double latGranularity = metersToDegreesLatitude(mAccuracyM); 144 latitude = wrapLatitude(Math.round(latitude / latGranularity) * latGranularity); 145 double lonGranularity = metersToDegreesLongitude(mAccuracyM, latitude); 146 longitude = wrapLongitude(Math.round(longitude / lonGranularity) * lonGranularity); 147 148 coarse.setLatitude(latitude); 149 coarse.setLongitude(longitude); 150 coarse.setAccuracy(Math.max(mAccuracyM, coarse.getAccuracy())); 151 152 synchronized (this) { 153 mCachedFineLocation = fine; 154 mCachedCoarseLocation = coarse; 155 } 156 157 return new Location(mCachedCoarseLocation); 158 } 159 160 /** 161 * Update the random offsets over time. 162 * 163 * If the random offset was reset for every location fix then an application could more easily 164 * average location results over time, especially when the location is near a grid boundary. On 165 * the other hand if the random offset is constant then if an application finds a way to reverse 166 * engineer the offset they would be able to detect location at grid boundaries very accurately. 167 * So we choose a random offset and then very slowly move it, to make both approaches very hard. 168 * The random offset does not need to be large, because snap-to-grid is the primary obfuscation 169 * mechanism. It just needs to be large enough to stop information leakage as we cross grid 170 * boundaries. 171 */ updateOffsets()172 private synchronized void updateOffsets() { 173 long now = mClock.millis(); 174 if (now < mNextUpdateRealtimeMs) { 175 return; 176 } 177 178 mLatitudeOffsetM = (OLD_WEIGHT * mLatitudeOffsetM) + (NEW_WEIGHT * nextRandomOffset()); 179 mLongitudeOffsetM = (OLD_WEIGHT * mLongitudeOffsetM) + (NEW_WEIGHT * nextRandomOffset()); 180 mNextUpdateRealtimeMs = now + OFFSET_UPDATE_INTERVAL_MS; 181 } 182 nextRandomOffset()183 private double nextRandomOffset() { 184 return mRandom.nextGaussian() * (mAccuracyM / 4.0); 185 } 186 wrapLatitude(double lat)187 private static double wrapLatitude(double lat) { 188 if (lat > MAX_LATITUDE) { 189 lat = MAX_LATITUDE; 190 } 191 if (lat < -MAX_LATITUDE) { 192 lat = -MAX_LATITUDE; 193 } 194 return lat; 195 } 196 wrapLongitude(double lon)197 private static double wrapLongitude(double lon) { 198 lon %= 360.0; // wraps into range (-360.0, +360.0) 199 if (lon >= 180.0) { 200 lon -= 360.0; 201 } 202 if (lon < -180.0) { 203 lon += 360.0; 204 } 205 return lon; 206 } 207 metersToDegreesLatitude(double distance)208 private static double metersToDegreesLatitude(double distance) { 209 return distance / APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR; 210 } 211 212 // requires latitude since longitudinal distances change with distance from equator. metersToDegreesLongitude(double distance, double lat)213 private static double metersToDegreesLongitude(double distance, double lat) { 214 return distance / APPROXIMATE_METERS_PER_DEGREE_AT_EQUATOR / Math.cos(Math.toRadians(lat)); 215 } 216 } 217