Cómo rastreamos y analizamos los pasos de más de 200.000 personas en el MIT

En mi primer año de primavera, tuve el placer de tomar 6.S08 (Sistemas integrados interconectados), que enseña conceptos básicos de EECS como el tablero de pruebas, la criptografía y el diseño algorítmico.

Si bien la clase fue increíblemente lenta y desafiante, debo decir que fue una de las clases más gratificantes que he tomado hasta ahora. Estoy orgulloso de haber trabajado con gente increíble (un saludo a Avery Lamp, Daniel González y Ethan Weber por los recuerdos interminables), y juntos construimos un proyecto final que no olvidaríamos.

Para nuestro proyecto final, nuestro equipo sabía que queríamos ser aventureros. Un día, mientras caminaba para comprar un helado, Avery sugirió un dispositivo para monitorear las solicitudes de sondas WiFi, similar a lo que hacen algunos centros comerciales. Después de una investigación inicial y de persuasión hacia nuestros instructores, decidimos comprometernos y comenzamos a investigar la idea.

¿Qué son las solicitudes de sonda WiFi?

La mayoría de la gente considera su teléfono como un receptor; se conecta a redes celulares / WiFi y, para todos los usos prácticos, solo son funcionales cuando están conectados. Sin embargo, cuando los teléfonos buscan redes WiFi, también suelen enviar pequeños paquetes de información llamados solicitudes de sondeo .

Estas solicitudes de sondeo envían fragmentos de información, como una dirección MAC única (similar a una huella digital), una señal RSSI (intensidad de señal logarítmica) y una lista de SSID anteriores encontrados. Como cada teléfono enviará una dirección MAC (excluyendo los intentos recientes de anonimización), podemos aprovecharlos fácilmente para rastrear a los estudiantes que caminan por el campus.

Recopilación de solicitudes de sonda

Los requisitos para nuestro proyecto final incluían el uso de los componentes estándar 6.S08 que usamos durante el semestre: un microcontrolador Teensy, un ESP8266 y un módulo GPS. Sin embargo, dado el bajo consumo de energía del ESP8266 (120 mA) y la falta de necesidad de una CPU fuerte, decidimos evitar el Teensy por completo. Esta decisión de diseño requirió que aprendiéramos cómo utilizar programadores FTDI para actualizar una implementación de Arduino para nuestros ESP, pero nos permitió continuar con un entorno que proporcionaba una gran familiaridad y una amplia gama de bibliotecas sobre el AT integrado. firmware de comando.

En los próximos días, tuvimos una prueba de concepto que rastreó las solicitudes de investigación realizadas en el campus; esto fue suficiente para mitigar cualquier duda de nuestros profesores, y fue el juego.

Desarrollando un POC

Ahora que sabíamos lo suficiente sobre las solicitudes de investigación para continuar, nuestro equipo pasó los siguientes días escribiendo la infraestructura que nos permitiría recopilar estas solicitudes en masa. Escribí un backend Flask + MySQL para administrar la infraestructura del dispositivo + información, Avery trabajó en una aplicación iOS para facilitar la implementación de dispositivos, Daniel González creó una hermosa interfaz para nuestro sitio web y Ethan creó una plataforma de análisis que transformó la riqueza de los datos entrantes en datos inteligibles con conocimientos valiosos.

Por el lado del hardware, Daniel y Ethan soldaron nuestros ESP8266 en placas prototipo, junto con algunos módulos de potencia. Reutilizamos los PowerBoost 1000C que nos dio la clase para hacer estos dispositivos completamente portátiles, lo que tuvo el agradable efecto secundario de permitirnos realizar un seguimiento en algunos lugares estrechos .

En particular, la dinámica del equipo fue absolutamente maravillosa: nos reímos juntos, aprendimos juntos y realmente disfrutamos de la compañía del otro. Los despliegues a las 4 a. M. No eran tan malos cuando era con algunos de tus mejores amigos.

Implementar

Dado que Ethan escribió un código ingenioso para conectar automáticamente los dispositivos al punto de acceso WiFi no seguro más cercano en el arranque, y Avery escribió una aplicación para actualizar la ubicación + los últimos campos movidos (útil para saber qué direcciones MAC asociar con cada ubicación), implementación fue tan fácil como conectar los dispositivos a una toma de corriente cercana y asegurarse de que pudiera hacer ping a casa. La implementación fue bastante agradable si se puso creativo con ella.

Analizando los datos

Después de dejar que el proyecto se ejecutara durante una semana, recopilamos alrededor de 3,5 millones de solicitudes de sondeo (!). También me gustaría señalar que todos los datos están anonimizados; De ninguna manera estos datos son lo suficientemente detallados como para determinar un mapeo de direcciones MAC a personas, lo que mitiga la mayoría de las preocupaciones de privacidad que tenían nuestros instructores.

Comenzamos aplicando el trabajo de Ethan a todas las ubicaciones, lo que causó un entusiasmo inmediato. Nuestros datos mostraron claramente el comportamiento periódico detrás de cada ubicación.

Además, fue claramente indicativo de algunas tendencias mayores en todo el campus: las arterias principales (Lobby 10, 26-100) lograron un tráfico máximo alrededor de las 5 pm, mientras que los edificios en el borde del campus (como Stata, que tiene un café) lograron un tráfico máximo en mediodía. No hace falta decir que, con la infraestructura instalada, los datos se vuelven mucho más interesantes.

Una vez que descubrimos que existían los datos para estas tendencias, comenzamos a hacernos algunas preguntas más interesantes:

  • ¿Qué podríamos concluir sobre la distribución make + de dispositivos en el MIT?
  • ¿Y si modelamos nuestro campus como un gráfico de red?
  • ¿Existe una caminata más común?
  • Más interesante aún, ¿podríamos predecir a dónde irán las personas después de su historial de ubicaciones?

Procedimos a atacarlos uno por uno.

Analizando el conjunto de datos

Las direcciones MAC en realidad proporcionan una gran cantidad de información en 6 bytes; podemos aprovechar esta información para determinar más sobre las personas que caminan a nuestro alrededor. Por ejemplo, cada fabricante compra un prefijo de proveedor para cada dispositivo que fabrica, y podemos usarlo para determinar los dispositivos más populares en el MIT.

Pero también hay una trampa: los intentos recientes de utilizar esta tecnología para rastrear a las personas por parte de la NSA han llevado a muchos fabricantes a anonimizar las solicitudes de investigación. Como resultado, no podremos determinar completamente la distribución de dispositivos, pero podemos investigar qué tan generalizada es la anonimización de las solicitudes de sondeo.

Es bastante irónico que cualquier dispositivo que anonimice las solicitudes de sondeo en realidad le informe que lo hacen ; en dispositivos anonimizados, el bit direccionado localmente (el segundo bit menos significativo) de la dirección se establece en 1. Por lo tanto, ejecutar una consulta SQL simple nos permite saben que casi el 25% de los dispositivos anonimizan las direcciones MAC (891,131 / 3,570,048 solicitudes de sondeo recopiladas).

Al ejecutar la lista de prefijos de proveedores (primeros tres bytes de una dirección MAC), vemos que las dos primeras de las ocho direcciones principales son anónimas.

  • "02: 18: 6a" con dirección local, 162.589 apariciones
  • "Da: a1: 19" con dirección local, 145.707 apariciones
  • 74: da: ea de Texas Instruments, 116,133 registros
  • 68: c4: 4d de Motorola Mobility, 66,829 registros
  • fc: f1: 36 de Samsung, 66,573 registros
  • 64: bc: 0c de LG, 63,200 registros
  • ac: 37: 43 de HTC, 60,420 ocurrencias
  • ac: bc: 32 de Apple, 55,643 registros

Curiosamente, mientras que Apple es, con mucho, el mayor actor en la anonimización de solicitudes de investigación, aparentemente envían al azar la dirección real de vez en cuando. Para alguien que rastrea a una frecuencia tan alta como la nuestra (casi cada segundo), esto es problemático; verificamos con amigos que tenían un iPhone y pudimos rastrear su ubicación con una precisión aterradora.

Predecir ubicaciones futuras

Después de modelar los paseos de los estudiantes como un gráfico de red, nos dimos cuenta de que podíamos calcular fácilmente la probabilidad de ir a otro nodo dado el nodo en el que estaban anteriormente. Además, nos dimos cuenta de que este gráfico se puede modelar fácilmente como una cadena de Markov. Dado un conjunto inicial de vértices, ¿adónde irían después?

Sin embargo, esto planteó un desafío importante: nuestra base de datos tenía poca comprensión de cuándo comenzaba una caminata y cuándo terminaba una caminata. Era poco más que un montón de coordenadas con ubicaciones y marcas de tiempo . Si examinaba las caminatas manualmente, estaba claro cuándo comenzaban algunas y terminaban otras, ya que los tiempos estarían bastante separados entre sí.

Esto se puede entender examinando la imagen de arriba. Por ejemplo, este individuo claramente no caminó desde Stata hasta el edificio Whitaker, ya que son días diferentes. Sin embargo, nuestra base de datos no tiene idea de esto, y como cualquier intento posterior de usar estos datos produciría resultados erróneos .

Curiosamente, si reestructuramos esto como un problema de agrupamiento de datos de series de tiempo , se vuelve muy intrigante. ¿Qué pasaría si hubiera una manera de agrupar las marcas de tiempo, de modo que pudiéramos identificar las diversas "caminatas" que realizó un estudiante? Teniendo en cuenta el rumor reciente sobre la agrupación de datos de series de tiempo, pensé que este sería un proyecto divertido para comenzar mi verano.

Analizar la base de datos en paseos

Para comprender mejor cómo agrupar potencialmente los datos, necesitaba comprender mejor las marcas de tiempo. Comencé trazando las marcas de tiempo en un histograma para comprender mejor la distribución de los datos. Con mucho gusto, este simple paso me ayudó a alcanzar la tierra: resulta que la frecuencia de las solicitudes de sondas con respecto a la distancia desde un ESP8266 sigue aproximadamente una distribución gaussiana, lo que nos permite usar un modelo de mezcla gaussiano. Más simplemente, podríamos aprovechar el hecho de que las marcas de tiempo seguirían esta distribución para eliminar los clústeres individuales.

El problema subsiguiente fue que a un MMG se le debe decir cuántos clústeres usar , no lo identificará por sí solo. Esto presentó un problema importante, especialmente si se considera que el número de caminatas que realizó cada individuo fue muy variable. Con mucho gusto, pude utilizar el criterio de información de Bayes, que califica cuantitativamente los modelos con respecto a su complejidad. Si optimizo para minimizar por BIC con respecto al tamaño del modelo, podría determinar un número óptimo de clústeres sin sobreajuste; esto se conoce comúnmente como la técnica del codo.

El BIC funcionó razonablemente bien al principio, pero penalizaría excesivamente a las personas que realizaron muchas caminatas al calcular de forma insuficiente el número de posibles agrupaciones . Comparé esto con la puntuación de silueta, que puntúa un grupo comparando la distancia dentro del grupo con la distancia al grupo más cercano. Sorprendentemente, esto proporcionó un enfoque mucho más razonable para agrupar datos de series de tiempo y evitó muchas de las trampas que encontró BIC.

Aumenté mi gota de DO para dejar que esto se ejecutara durante unos días y desarrollé un bot rápido de Facebook para notificarme al finalizar. Con esto fuera del camino, podría volver a trabajar prediciendo los próximos pasos.

Desarrollo de una cadena de Markov

Ahora que hemos segmentado una enorme cadena de solicitudes de sondeo en recorridos separados, podemos desarrollar una Cadena de Markov. Esto nos permitió predecir el próximo estado de eventos dados los anteriores.

Utilicé la biblioteca de Python Markovify para generar un modelo de Markov dado un corpus de nuestro paso anterior, lo que acortó el tiempo de desarrollo de manera comparable.

He incluido una cadena de Markov de muestra generada anteriormente; esto en realidad representa la caminata de un estudiante que sale de la conferencia (26-100 es una sala de conferencias) y se dirige a su dormitorio. Es realmente emocionante que una computadora haya podido captar esto y generar una caminata similar. Algunas ubicaciones se repiten, esto se debe a que cada ubicación registrada en realidad representa una observación. Por lo tanto, si una ubicación aparece más que otras, eso simplemente significa que la persona pasó más tiempo allí.

Si bien esto es primitivo, las posibilidades son bastante interesantes . ¿Qué pasaría si pudiéramos aprovechar esta tecnología para crear ciudades más inteligentes, trabajar contra la congestión y brindar una mejor perspectiva sobre cómo podemos reducir los tiempos promedio de caminata? Las posibilidades de la ciencia de datos en este proyecto son infinitas y estoy increíblemente emocionado de perseguirlas.

Conclusión

Este proyecto fue uno de los momentos más emocionantes de mi primer año, ¡y estoy muy contento de haberlo hecho! Me gustaría agradecer a mis increíbles compañeros del 6.S08, a nuestro mentor Joe Steinmeyer y a todo el personal del 6.S08 que hicieron esto posible.

Aprendí mucho mientras perseguía este proyecto, desde cómo agrupar datos de series de tiempo hasta la infraestructura necesaria para rastrear las solicitudes de sondeo en el campus. Adjunto algunos artículos más a continuación de las aventuras de nuestro equipo.