Playing - Fuite des données du site Ashley Madison

Préambule

En août 2015, un groupe de hackers dénommé The Impact Team a piraté le site de relation extra-conjugal Ashley Madison. Ce piratage lui a permis de récupérer toutes les données des 34 millions d'utilisateurs: adresse, email, transaction financière... Evidemment sur ce site nous ne divulguerons aucune information à caractère confidentiel. Nous retenons seulement de la base de données la géolocalisation de chaque utilisateur et décrivons comment nous sommes parvenus à construire une carte pour les représenter. En plus de cette donnée nous conservons le genre (homme ou femme) afin d'apporter un peu de couleur à notre visualisation même si le site est composé à 85 % de profil masculin et que la plupart des profils féminins sont faux.

Traitement des données

C'est cette étape qui est la plus longue et la plus fastidieuse lorsque l'on dispose d'un jeu de données que l'on doit traiter et dont on ne connait pas le contenu. Ici, les données sont stockées sous la forme d'un ensemble de fichiers compressés. 5 d'entre eux correspondent à un dump d'une base MySQL (un dump représente la sauvegarde de toutes les données contenues dans une ou plusieurs tables d'une base de données ainsi que leur structure(s)). Nous avons regardé les 1000 premiers caractères de chacun de ces fichiers (les fichiers faisant jusque 14Go ils ne peuvent pas être ouverts avec un éditeur) en programmant une petite classe JAVA qui peut lire caractère par caractère sans charger tout le fichier (cette opération peut être réalisée avec la plupart des langages informatique non dédiés au Web et même avec certains programmes spécifiques). C'est grâce à cette exploration que nous avons déterminé le fichier qui pourrait être intéressant (celui contenant la géolocalisation des utilisateurs). Malheureusement pour nous c'est aussi le plus gros et il nous a fallu 24h pour l'importer dans une base MySQL créée pour l'occasion (cet import se fait à partir du dump précédemment cité, voir pour plus de détails le site www.developpez.com).

Maintenant que nos données sont structurées dans une base et facilement interrogeables, il ne nous reste plus qu'à extraire les informations qui nous intéressent. Pour cela nous avons écrit un programme Java qui se connecte à la base et récupère les colonnes gender, city, latitude et longitude pour les écrire dans un fichier CSV. Afin de pouvoir facilement ouvrir ces fichiers par la suite nous créons un nouveau fichier tous les 1 million de résultats. Le code permettant ce traitement est le suivant (il faut bien penser à récupérer le Driver JDBC pour les bases de données MySQL). Au total 34 fichiers représentant 1 Go environ sont produits.

public static String FILE_OUT_PREFIXE = "c:\\temp\\am";

public static void main(String[] args) {
	try {
		Class.forName("com.mysql.jdbc.Driver");
	} catch (ClassNotFoundException e) {
		e.printStackTrace();
		return;
	}
	
	Connection connection = null;
	try {
		FileWriter fw = new FileWriter(new File(FILE_OUT_PREFIXE + "0.csv"));
		fw.write("gender;latitude;longitude\n");
		connection = DriverManager.getConnection("jdbc:mysql://localhost:3306/ashley_madison","root", "password");
		Statement statement = connection.createStatement();
		statement.setFetchSize(Integer.MIN_VALUE); // LIGNE 17
		ResultSet rs = statement.executeQuery("SELECT gender, latitude, longitude, city FROM aminno_member");
		int count = 0;
		while (rs.next()) {
			count++;
			int gender = rs.getInt("gender");
			String latitude = rs.getString("latitude");
			String longitude = rs.getString("longitude");
			String city = rs.getString( "city" );
			fw.write(gender + ";" + latitude + ";" + longitude + ";" + city + "\n");
			if (count % 1000000 == 0) {
				fw.close();
				fw = new FileWriter(new File(FILE_OUT_PREFIXE + (count / 1000000) + ".csv"));
				fw.write("gender;latitude;longitude\n");
			}
		}
		fw.close();
	} catch (Exception e) {
		e.printStackTrace();
	} finally {
		if (connection != null) {
			try {
				connection.close();
			} catch (SQLException ignore) {}
		}
	}
}

Le code n'a rien de particulier si ce n'est la ligne surlignée qui est nécessaire sans quoi le programme va attendre d'avoir chargé tous les résultats en mémoire avant de commencer à les traiter. Ce traitement est très rapide et réalisé en moins de 10 minutes.

Le challenge

Nous n'avons trouvé qu'une seule cartographie des données d'Ashley Madison: ici. Notre but est de faire mieux que cette carte et ça va vraiment être difficile car elle intègre de très bonnes idées et ce qui se fait de mieux en termes de représentation sur Internet de données en grand nombre: les tiles, suivant le même principe que dans le tutoriel sur Leaflet - Première Carte mais avec des cercles orange à la place d'un fond de carte, comme dans l'image ci-dessous. Il y a un cercle orange pour chaque ville possédant plus de 10 utilisateurs. En plus si le nombre de femmes est supérieur à 15 % alors la couleur du point est jaune.

1ère tentative : Générer une image

Il est bien sûr impossible de représenter 34 millions de points dynamiquement sur une page web, d'une part le volume de données à transmettre depuis le serveur vers le client est trop important (1 Go ici), d'autres part les navigateurs actuels ne permettent pas de gérer autant d'objets dans une page. L'une des façons de procéder serait par exemple de créer un canvas comme dans le tutoriel sur les nombres premiers, mais il resterait toujours le problème du transfert des données. C'est pour cette raison que cette première tentative se fait entièrement en amont et produit une image. Ainsi le volume de données ou le temps de traitement ne sont pas un problème. Cette image est visible en cliquant sur celle visible ci-dessous (attention, elle pèse tout de même 3.3 Mo). Elle fait 12000px par 8000px, soit 96 millions de points.

L'image prend un certains temps à charger. Elle permet de voir que le Japon et l'Angleterre ressortent plus que les autres pays. Pourtant les pays ou le site est le plus présent sont les Etats-Unis et le Canada, notre seconde tentative permettra peut-être d'améliorer ça. Le principal problème vient du fait qu'à certains endroits les points sont trop discrets, c'est principalement lié au niveau de zoom et à la façon dont le navigateur affiche une image beaucoup plus grande que la résolution de l'écran. Néanmoins, il y a un point pour chaque utilisateur du site même s'ils se superposent très souvent. Les nuances de couleurs visent à différencier les hommes des femmes (bon, il n'y a presque que du bleu mais on voit parfois un peu de rose, notamment en Inde). En revanche réaliser cette image nous a permis d'apprendre pas mal de choses intéressantes sur la façon de convertir des coordonnées exprimées en latitude,longitude en un point exprimé en x,y.

Conversion d'un geoJSON en liste de polygones

Commençons par le fond de carte qui a été construit à partir du fichier geoJSON suivant: countries-no-antartica.json. Il est bien plus gros que celui utilisé dans le tutoriel sur les prix nobels mais aussi plus détaillé. Il respecte le format suivant: une liste de features (de pays), des propriétés et leur géométrie.

{
	"type": "FeatureCollection",
	"features": [
		{ 
			"type": "Feature",
			"properties": { "NAME_SORT": "Aruba", ... }, 
			"geometry": { 
				"type": "Polygon", 
				"coordinates": [ [ 
					[ -69.899139, 12.452005 ], 
					[...]
				] ] 
			} 
		}, { 
			"type": "Feature",
			"properties": { "NAME": "Angola", ... }, 
			"geometry": { 
				"type": "MultiPolygon", 
				"coordinates": [ 
					[ [ 
						[ 14.190845, -5.876023 ], 
						[...]
					] ], 
					[ [ 
						[ 12.255304, -5.746471 ], 
						[...]
					] ]
				] 
			} 
		}
		{...}
	]
}

Nous avons retenu Aruba, une île néerlandaise et L'Angola. Le premier possède une géométrie de type Polygon et le second de type MultiPolygon. Cela permet de différencier les pays formés d'un seul polygone et ceux qui en possèdent plusieurs (comme la France avec la Corse par exemple). Cette subtilité est importante pour le code qui va suivre. Ecrit en JAVA, il permet de lire un fichier JSON (en utilisant la librairie Google quick-json) et de le convertir en une liste de polygones, eux-mêmes représentés par une liste de points.

public static Collection<Collection<Point2D.Double>> getPolygons(String file) throws Exception {
	Collection<Collection<Point2D.Double>> result = new ArrayList<Collection<Point2D.Double>>();
	JSONObject json = new JSONObject(new JSONTokener(new FileInputStream(file)));
	JSONArray features = json.getJSONArray("features");
	for (int i = 0; i < features.length(); ++i) {
		JSONObject geometry = ((JSONObject) features.get(i)).getJSONObject("geometry");
		boolean isMultiPolygon = geometry.get("type").equals("MultiPolygon");
		JSONArray level1 = geometry.getJSONArray("coordinates");
		if (isMultiPolygon) {
			for (int j = 0; j < level1.length(); ++j) {
				JSONArray level2 = level1.getJSONArray(j);
				Collection<Point2D.Double> countryPart = new ArrayList<Point2D.Double>();
				for (int k = 0; k < level2.length(); ++k) {
					JSONArray level3 = level2.getJSONArray(k);
					for (int l = 0; l < level3.length(); ++l) {
						JSONArray latlng = ((JSONArray) level3.get(l));
						countryPart.add(new Point2D.Double(latlng.getDouble(1), latlng.getDouble(0)));
					}
				}
				result.add(countryPart);
			}
		} else {
			level1 = level1.getJSONArray(0); // always surrounded with []
			Collection<Point2D.Double> country = new ArrayList<Point2D.Double>();
			for (int j = 0; j < level1.length(); ++j) {
				JSONArray latlng = ((JSONArray) level1.get(j));
				country.add(new Point2D.Double(latlng.getDouble(1), latlng.getDouble(0)));
			}
			result.add(country);
		}
	}
	return result;
}

Rien d'incroyable ici, le code fait simplement son job en explorant le JSON pour récupérer ce qui nous intéresse. Nous obtenons ainsi une liste de listes de points. Chaque point contenant deux nombres, une latitude et une longitude.

Conversion d'une latitude,longitude en coordonnées x,y

Notre problème ici est de convertir une sphère (la Terre) en un plan. Heureusement pour nous ce problème a déjà été résolu et est documenté depuis 500 ans. En 1569, Gérard Mercator, un mathématicien et géographe, a publié la projection qui porte son nom: la projection de Mercator. Elle est aujourd'hui la projection la plus utilisée même si elle possède un gros défaut, celui de déformer les continents près des pôles. Ainsi, le Groenland qui est pourtant 8 fois plus petit que l'Amérique du Sud apparait plus grand. Néanmoins c'est cette projection que nous allons utiliser pour convertir nos latitudes, longitudes. La page Wikipedia donne une formule pour effectuer cette conversion mais voici un code simplifié en Java.

double radianLon = longitude * Math.PI / 180;
double radianLat = latitude * Math.PI / 180;

Point2D.Double point = new Point2D.Double();
point.x = radianLon;
point.y = Math.log(Math.tan(Math.PI / 4.0 + 0.5 * radianLat));

Toutes les informations de cette partie proviennent d'une question sur le site stackoverflow : Converting longitude/latitude to X/Y coordinate. En plus de fournir la formule de conversion cette page nous aide à placer un point sur un plan dont la taille est connue (le nôtre faisait 12000 par 8000). Enfin, elle fournit tout le code pour produire une image depuis un programme Java. Nous n'irons pas plus loin dans notre analyse du code. Néanmoins celui que nous avons utilisé est disponible ici: MapService.java et AMUser.java. En résumé, le code charge les polygones du fichier geoJSON, lit les fichiers contenant les latitudes, longitudes des utilisateurs pour construire une liste d'AMUser puis lance la fonction run(). Cette fonction construit une image de la taille voulue, calcule les coordonnées x,y de chaque utilisateur puis des pays pour enfin les dessiner sur l'image. N'hésitez pas à poser des questions sur ce code dans les commentaires.

Regroupement des données

Lorsque les données ne rentrent pas dans le modèle

Comme nous souhaitons profiter du côté dynamique qu'offre l'HTML associé au Javascript, nous devons diminuer la quantité des données transmises au navigateur. Pour cela, nous prenons le parti de regrouper les informations dont on dispose et décidons assez naturellement de partir sur un regroupement par ville. En analysant les données, nous avons remarqué que pour une même ville les coordonnées sont quasiment toujours différentes. Probablement parce que le site a enregistré ces informations en demandant la géolocalisation précise de ses utilisateurs (assez logique pour un site de recontre). Nous décidons donc de faire la moyenne des coordonnées pour chaque ville, ainsi on s'assure d'obtenir une position un peu près centrée. Après un rapide traitement et une première visualisation, nous comprenons qu'il y a un problème, il y a des points partout au milieu de l'océan. En regardant dans le détails nous nous rendons compte que beaucoup de villes à travers le monde possèdent le même nom. Il y a ainsi pas moins de 30 villes nommés Paris (Liste des villes s'appelant Paris).

Calcul de distance entre deux coordonnées

Il nous faudra donc vérifier que les villes que nous lisons sont bien les mêmes. Pour cela, nous décidons que deux villes sont bien les mêmes si elles sont distantes de moins de 20km. Cela va forcément générer quelques erreurs pour les villes très étendues, mais le résultat devrait être globalement satisfaisant. Pour ne pas faciliter notre travail, les villes sont écrites par les utilisateurs et ne proviennent pas d'un référentiel, ainsi New York est écrit parfois New York City. Nous décidons de ne pas tenir compte de ce détail trop complexe à gérer. Pour effectuer ce calcul et parceque les coordonnées sont placées sur une sphère, la formule pour trouver la distance entre deux villes n'est pas toute simple.

public static double distance(double lat1, double lat2, double lon1, double lon2) {
	final int R = 6371; // Radius of the earth

	Double latDistance = Math.toRadians(lat2 - lat1);
	Double lonDistance = Math.toRadians(lon2 - lon1);
	Double a = Math.sin(latDistance / 2) * Math.sin(latDistance / 2)
			+ Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2))
			* Math.sin(lonDistance / 2) * Math.sin(lonDistance / 2);
	Double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
	double distance = R * c * 1000; // convert to meters

	return distance;
}

Cette formule dite Formule d'Haversine a été très utile en son temps pour la navigation. Encore une fois, c'est sur stackoverflow que nous avons trouvé les meilleures informations: Calculating distance between two points... Notez que nous avons supprimé du calcul l'élément hauteur.

2e tentative : Leaflet et Heatmap

Maintenant que nous disposons d'un fichier CSV de tous les utilisateurs regroupés par ville, il ne nous reste plus qu'à représenter ces données sur une carte. Pour cette 2e tentative, nous décidons d'utiliser la librairie Leaflet et de lui superposer une Heatmap (carte thermique ou carte de chaleur en français). Le fichier CSV utilisé dans la visualisation juste en dessous peut être récupéré ici : city-info.csv. Pour rappel, il contient le regroupement des 34 millions d'utilisateurs par ville du même nom et distante de moins de 20km en faisant la moyenne des coordonnées pour chaque ville. Pour cette première tentative nous n'avons conservé que les villes dont le nombre d'utilisateurs masculins est supérieur à 100. Ce qui fait 21600 entrées et si vous remarquez beaucoup de '?' dans le nom des villes c'est parce que l'encoding d'origine n'a pas été conservé. Les fichiers n'étaient pas en UTF-8 et pour le nom de villes chinoises par exemple cela pose problème. Le résultat est visible en cliquant sur l'image ci-dessous.

Cette fois-ci le résultat est plus agréable à l'oeil, la possibilité de zoomer finement et de voir les amas de couleurs se diviser est intéressante. Le code javascript pour générer la carte est très simple, il faut juste récupérer la librairie Leaflet-heat sur le site du développeur ou directement sur notre site: leaflet-heat.js. Nous avons également utilisé un fond de carte provenant de Stamen Design et choisi les Tiles dark.

Conclusion

Cette 2e tentative possède encore quelques lacunes. Les pays sont couverts par la heatmap et elle ne permet plus de les distinguer sans les connaître. Lorsque l'on zoom au maximum tous les points sont de même taille alors qu'ils représentent des quantités différentes.

3e tentative : Leaflet et groupement de markers

Toujours à partir de notre fichier CSV nous pouvons utiliser le groupement de markers avec Leaflet pour visualiser les données. Le résultat est visible en cliquant sur l'image ci-dessous. Attention cependant, comme il y a plus de 20000 markers c'est consommateur de ressource.

Cette tentative permet de voir directement le nombre d'inscrits à différents niveau de zoom. En revanche il n'est pas possible de mettre les clusters en transparence car le code qui les gère possède le défaut d'effacer la propriété CSS opacity dès qu'on zoom. Le code de construction des clusters est assez simple. Comme un marker représente le nombre d'utilisateurs nous avons décidé pour chaque cluster d'afficher la somme de ses utilisateurs et non pas le nombre de markers qu'il contient. Pour cela nous ajoutons la propriété number à notre marker (ligne 16) et nous l'utilisons ligne 10 lorsque l'on construit l'icone représentant le cluster. Pour plus d'information, notamment sur le CSS, voir notre tutoriel : Leaflet - Groupement de markers.

d3.csv("city-info.csv", function(csv) {
	var markersCluster = new L.MarkerClusterGroup({
		iconCreateFunction: function (cluster) {
			var markers = cluster.getAllChildMarkers();
			var count = 0;
			for (var i = 0; i < markers.length; i++) {
				count += markers[i].number;
			}
			var digits = (count+'').length;
			return L.divIcon({ html: count, className: 'cluster digits-'+ digits, iconSize: null }); // LIGNE 10
		}
	});
	csv.forEach(function(d) {
		if (!isNaN(d.lat) && !isNaN(d.lng)) {
			var marker = new L.Marker(new L.latLng(d.lat, d.lng), {title: d.city + ": hommes(" + d.males + "), femmes(" + d.females + ")"});
			marker.number = +d.males + +d.females; // LIGNE 16
			markersCluster.addLayer(marker);
		}
	});
	map.addLayer(markersCluster);
});