Baptiste Robert trouve (encore) une faille dans l'application de « contact tracing » indienne

Baptiste Robert trouve (encore) une faille dans l’application de « contact tracing » indienne

Baptiste Robert trouve (encore) une faille dans l'application de « contact tracing » indienne

Nommée Aarogya Setu, elle utilise le Bluetooth mais également le GPS. Elle propose de savoir, dans un rayon de 500 mètres à 10 kilomètres, combien de personnes ont été infectées, sont malades, ont été considérées comme « cas contact », ou encore combien l'utilisent. 

Sauf que Baptiste Robert (@fs0c131y), qui a précédemment trouvé des failles de sécurité (entre autres) dans la messagerie sécurisée gouvernementale Tchap et le système d'identité biométrique indien Adhaar a découvert qu'il pouvait modifier la géolocalisation, permettant d'obtenir ces statistiques n'importe où dans tout le pays.

Il a ainsi découvert que dans un rayon de 500 mètres autour du Parlement indien on comptait 1 personne infectée, 2 malades et 17 Bluetooth positifs, pour 2 338 utilisateurs... Il précise à Wired qu'en utilisant la triangulation et en déplaçant le curseur de géolocalisation, il serait possible d'identifier où résideraient ces gens, dans un rayon bien plus étroit que les 500 mètres initiaux, et potentiellement jusqu'à l'échelle d'une maison.

Commentaires (58)


Wouah la faille qui… ne sert strictement à rien…

 








Faith a écrit :



Wouah la faille qui… ne sert strictement à rien…





Faut lire le dernier paragraphe… Ce n’est pas une grosse faille de sécurité mais elle l’est dans le cadre du respect de la vie privée…



Si, tu peux connaitre ou sont les personnes malades, donc dans quelle familles, sans en avoir le droit. C’est très problématique pour une appli de tracing…








bilbonsacquet a écrit :



Faut lire le dernier paragraphe… Ce n’est pas une grosse faille de sécurité mais elle l’est dans le cadre du respect de la vie privée…





J’ai déjà lu… et donc concrêtement, ça sert à quoi ?

 



Si tu es sensé savoir que tu as croisé un malade tu n’es pas sensé savoir qui et encore moins où il habite,

ce que permet cette faille.


Ouha le commentaire qui… sert strictement à rien…








bad10 a écrit :



Si tu es sensé savoir que tu as croisé un malade tu n’es pas sensé savoir qui et encore moins où il habite,

ce que permet cette faille.





Ben tu ne peux pas… tu peux éventuellement localiser à plusieurs centaines de mètres près qu’il y a un ou plusieurs malades.

Il a joué avec les paramètres envoyés au logiciel… super…



Je remarque déjà un point. L’important a été fait: impossible de descendre en dessous de 500m. Ce qui est la protection essentielle.

L’auteur affirme que la triangulation permet de descendre au mètre près… mais n’en fait pas la preuve.



D’ailleurs si cette faille était réellement exploitable, il aurait pu dire qui est malade au parlement…



Et puis allez, prenons le pire cas possible: il est donc possible de connaitre l’emplacement exact de toutes les personnes malades du pays… and so what ?









Faith a écrit :



L’auteur affirme que la triangulation permet de descendre au mètre près… mais n’en fait pas la preuve.





Si tu peux modifier la position de l’appareil, tu peux faire de la triangulation.





Faith a écrit :



il est donc possible de connaitre l’emplacement exact de toutes les personnes malades du pays… and so what ?





Et donc ça contourne le principe initial du dispositif.









Zone démilitarisée a écrit :



Si tu peux modifier la position de l’appareil, tu peux faire de la triangulation.





En vrai, trianguler n’est pas un mot magique comme dans les séries policières.

Trianguler c’est multiplier les incertitudes (et encore, je crois que la croissance de l’incertitude est exponentielle).

De plus trianguler en ayant comme seule information un unique nombre par zone de 785000m², c’est un boulot titanesque, voir impossible.





Et donc ça contourne le principe initial du dispositif.



Oui, et ?

Désolé, mais moi quand un article me parle de “fiasco total”, je m’attends à une situation pire avec que sans…

 









Faith a écrit :



Je remarque déjà un point. L’important a été fait: impossible de descendre en dessous de 500m. Ce qui est la protection essentielle.

L’auteur affirme que la triangulation permet de descendre au mètre près… mais n’en fait pas la preuve.







Il suffit de répéter les requêtes sur plusieurs localisations GPS différentes dans la zone, et ses alentours. Par recoupement, la barrière des 500m va aussitôt tomber.



Si on prend l’exemple donné où il n’y a qu’un seul cas dans la zone, c’est même très simple. Retrouver la géolocalisation exacte, c’est un peu comme faire une partie Mastermind. En fonction des réponses, par recoupement, on est certain de pouvoir retrouver la localisation exacte par élimination des “faux positifs”. Toute requête renvoyant un négatif sur zone en intersection exclu les points contenus dans l’intersection. Au final, si on fait suffisamment de requêtes, la précision obtenue sera celle de la localisation GPS initiale.



Le principe peut être étendu à des cas multiples dans une même zone. C’est un plus fastidieux, mais ça reste possible, tout le temps que la répartition des cas n’est pas parfaitement uniforme.









stratic a écrit :



Si on prend l’exemple donné où il n’y a qu’un seul cas dans la zone, c’est même très simple.





Même pas. En déplaçant le cercle, tu vas récupérer d’autres malades.

Ton chiffre va passer à 0, 2, 3 ou 10. Parfois à 1, mais ce sera un autre malade à l’autre extrêmité du cercle…

Et de tous ces chiffres, tu ne sauras jamais si celui que tu veux repérer en fait partie ou non.



Les seuls cas où ça marche, ce sont des zones isolées avec très très peu de malades.

 

Ca demande un travail colossal pour identifier un malade dans un zone un peu peuplée.

Et tout ça pour … … rien. Parce que savoir que quelqu’un est malade, ça ne sert à rien.



Et encore, tout cela repose sur la supposition que l’application renvoie exactement un cercle de 500m pour toutes ses réponses. Alors que ce genre d’application travaille fréquemment par blocs ou par zones.









Faith a écrit :



Je remarque déjà un point. L’important a été fait: impossible de descendre en dessous de 500m. Ce qui est la protection essentielle.

L’auteur affirme que la triangulation permet de descendre au mètre près… mais n’en fait pas la preuve.



Et puis allez, prenons le pire cas possible: il est donc possible de connaitre l’emplacement exact de toutes les personnes malades du pays… and so what ?





C’est assez facile d’envisager les conséquences du pire scénario, qui est possible par triangulation et encore plus facilement en zones rurales à faible densité de population : violence et harcèlement dirigés vers des malades et leurs familles et tout ce qui peut passer par la tête d’une personne malveillante qui a accès à la localisation d’une personne.



C’est important de remonter ce genre de problèmes sur les applications

de contact tracing à l’heure où beaucoup de gouvernements préparent

leurs solutions maison.









Frousse a écrit :



tout ce qui peut passer par la tête d’une personne malveillante qui a accès à la localisation d’une personne.



 

Cette application ne fournit pas la localisation d’une personne.





C’est assez facile d’envisager les conséquences du pire scénario,

qui est possible par triangulation et encore plus facilement en zones

rurales à faible densité de population : violence et harcèlement dirigés

vers des malades et leurs familles et



D’accord, c’est un scénario du pire. Même pas totalement irréaliste vu les réactions de certains contre les infirmiers.



Mais si les gens veulent harceler quelqu’un dans une zone rurale peu peuplée, vous croyez qu’ils passeront par cette application pour savoir qu’elle est malade ? Dans une zone rurale peu peuplée, tous vos voisins sauront que vous êtes malades parce qu’ils ne vous verront plus aller au boulot, que le médecin se déplacera et que votre conjoint ira à la pharmacie…

Jamais vos voisins n’iront perdre leur temps à vous trianguler avec une appli incertaine (d’autant plus que vos voisins s’apercevront vite qu’avec la précision de leurs calculs, ils pourraient eux-même être désignés malades sans l’être vraiment)



Vous êtes dans le biais du technicien: vous concevez un bras robotisé connecté à une caméra avec reconnaissance de forme pour… chasser les moustiques. Oui, d’accord le bras robotisé fonctionnera… mais tellement moins bien qu’un journal plié en deux !

 

 

C’est important de remonter ce genre de problèmes



C’est important de remonter les problèmes pour ce qu’ils sont.

L’auteur parle de “fiasco total” là où on a tout juste une petite faille à peine exploitable.

Et la solution est enfantine (et peut-être déjà en place, le gars ne peut pas le savoir): faire varier la taille du cercle à chaque réponse.

 









Faith a écrit :



Trianguler c’est multiplier les incertitudes (et encore, je crois que la croissance de l’incertitude est exponentielle).

 





Tu peux  expliciter ? Parce que, autant je suis d’accord que la technique utilisée dans cette faille n’est pas à proprement parler de la triangulation, autant ta définition de la triangulation est mensongère également.



Mouais perso. je ne vois pas pourquoi vous vous focalisez sur l’aspect malade ?

Ici ce que l’on a c’est une appli. de tracking où l’on (et le gouvernement aussi par la même occasion) peut voir et suivre les gens.



Donc je peux suivre une personne, je peux savoir combien il y a de personne dans un batiment à tel heure, je peux faire des recoupements, etc…



C’est pas pour rien que les systèmes de balise en france sont interdites voir encadrés dans certains cas.



Surtout on a pu voir comme en Corée les débordements que ça a donné genre des personnes harcelés sur le net et dans la rue pour des tas de raisons parce que justement leur appli. pouvait suivre tous les mouvements des gens publiquement (il y avait pas besoin de hack).








refuznik a écrit :



Mouais perso. je ne vois pas pourquoi vous vous focalisez sur l’aspect malade ?

Ici ce que l’on a c’est une appli. de tracking où l’on (et le gouvernement aussi par la même occasion) peut voir et suivre les gens.



Donc je peux suivre une personne, je peux savoir combien il y a de personne dans un batiment à tel heure, je peux faire des recoupements, etc…







Tu ne peux pas suivre les gens. Tu n’as pas les moyens de différencier un point d’un autre. La seule “faille” c’est d’obtenir les statistiques à n’importe quel endroit, ce qui est normal, l’api n’a pas les moyens de savoir si les coordonnées de la requêtes correspondent à une géolocalisation réelle. Tout au plus peux-t-on demander un peu de throttling s’il n’y en a pas déjà.



fs0c131y est systématiquement alarmiste, je ne comprend pas qu’on lui donne autant de visibilité. Ah si, c’est parce qu’il a tapé sur Tchap (là encore à 90% pour rien), et donc le gouvernement, ce qui fait bander les gauchistes.









haelty a écrit :



Tu peux  expliciter ?





En triangulant des distances dont l’incertitude est de 2 mètres, on obtient une localisation qui est l’intersection de 3 bandes de 4m de large.

Ca donne une forme approximativement hexagonale de 4m de “diamètre”, environ 10.4m²

Si la précision est deux fois moins bonne, ça nous fait une zone de 41.6m², soit 4x moins bonne.



Et alors tu as besoin qu’il y a le nom de la personne pour la suivre et en faire des déductions ? Punaise tu ne sais pas te servir de ton cerveau. Tiens d’ailleurs tu pourras le dire à l’employée coréene qui s’est fait pourrir la vie parce qu’elle avait pris 10 minutes de plus sur sa pause déjeuner.








Faith a écrit :



De plus trianguler en ayant comme seule information un unique nombre par zone de 785000m², c’est un boulot titanesque, voir impossible.





J’ai effectivement mal lu. Je me suis imaginé que l’application indiquait la position des personnes (comme un radar, ce qui à la base aurait posé problème), alors qu’elle donne uniquement le nombre.



Tu ne peux pas identifier un point précis. Tu n’as accès qu’à des statistiques pour une géolocalisation précise. utilises-donc toi même ton cerveau, et tes yeux.








psikobare a écrit :



Tu n’as accès qu’à des statistiques pour une géolocalisation précise. utilises-donc toi même ton cerveau, et tes yeux.





Tu ne sais pas utiliser l’api de googlemap ou d’openstreetmap pour placer un point ?










refuznik a écrit :



Tu ne sais pas utiliser l’api de googlemap ou d’openstreetmap pour placer un point ?





En fait tu n’as pas cette information au départ. Tu as simplement un indicateur qui te donne le nombre de personnes autour de toi (tu ne sais ni dans quelle direction elles sont, ni à quelle distance). Tu peux donc juste tracer un cercle d’un rayon de 500 m à 10 km et y associer un nombre de malades.



Ok je pense que je vais devoir t’expliquer:



t’as une API qui prend une géolocalisation en entrée, et qui te donne des statistiques en sorties



Tu demandes X=10;Y=50 ça te répond 3 infectés, 6 malades, 14 contacts

Tu peux redemander X=15;Y=40, ça te répond 4 infectés, 5 malades, 12 contacts

etc



Bon courage pour retrouver quoi que ce soit.


Yep c’est le fonctionnement l’app. à la base mais ce que lui a trouver c’est de pouvoir la positionner où tu veux et de pouvoir à partir de ces informations supplémentaires de trouver leur localisation.









Zone démilitarisée a écrit :



En fait tu n’as pas cette information au départ. Tu as simplement un indicateur qui te donne le nombre de personnes autour de toi (tu ne sais ni dans quelle direction elles sont, ni à quelle distance). Tu peux donc juste tracer un cercle d’un rayon de 500 m à 10 km et y associer un nombre de malades.







T’as jamais joué au démineur ? Si ? Non ? A priori, non. <img data-src=" />









Faith a écrit :



&nbsp;

Cette application ne fournit pas la localisation d’une personne…





Pourtant ce passage le laisse penser :

“il serait possible d’identifier où résideraient ces gens, dans un rayon

bien plus étroit que les 500 mètres initiaux, et potentiellement jusqu’à

l’échelle d’une maison”



Le démineur te fournit une direction ! <img data-src=" />


On pourrait imaginer lancer autant de requêtes qu’il y a de points sur une carte pour couvrir un territoire avec une résolution de 500 mètres. En admettant que le serveur veuille bien te répondre, cela permettrait d’obtenir un instantané avec le nombre de cas par point.



À partir de là, Baptiste Robert explique qu’il pourrait utiliser la trilatération associée à la triangulation.








Zone démilitarisée a écrit :



Le démineur te fournit une direction ! <img data-src=" />







Et, à force d’estimer des directions, tu finis par trouver où est la mine.



Pour un peu, on croirait presque que tu ne connais pas l’existence du problème inverse de frobenius-perron (IFPP). Mais je ne peux décemment pas croire qu’un expert tel que toi ignore l’état de la recherche mathématique sur les chaines de Markov dans un système dynamique. Non, vraiment ce serait incroyable.



<img data-src=" />



Une phrase au conditionnel, ça n’affirme rien. Comme tu le dis, ça le laisse penser, mais est-ce vrai ? Comme l’a dit Faith, en changeant de fausse localisation, tu n’es pas sûr que ce soit la (ou les) même personne que l’on t’indique à chaque interrogation. Cela permettrait de localiser une personne dans une zone peu peuplée où une seule personne est signalée. En Inde qui est le pays le plus peuplé de la planète, ces cas doivent être très rares.


L’Inde est très peuplée, certes.



Mais là on ne parle que des 280 000 personnes dans toute l’Inde qui ont installé l’application.

Tout de suite, c’est beaucoup moins concentré et on retrace beaucoup plus facilement les choses.



Il me semble assez facile en pingeant régulièrement des points précis à 500m de distance les uns des autres de retracé avec précision le déplacement d’une personne utilisant l’application.



Si tu prend comme point de départ un endroit comme le parlement, il y a de quoi suivre à la trace un député utilisant l’application (et tu découvriras très facilement lequel soit en recoupant avec d’autres infos, soit en allant par toi-même dans un des rayons de 500m en question).



C’est tout con à faire, d’autant plus avec la quantité de choses que l’on sait faire sur tout ce qui ressemble de près ou de loin à un graphe social…


Cette installation est devenue obligatoire pour tous les employés (du public et du privé). Donc, le nombre d’installations a dû grimper en flèche.



Ton raisonnement de traçage suppose que c’est toujours la même personne que tu auras en réponse, et c’est loin d’être vrai comme déjà dit.








127.0.0.1 a écrit :



Et, à force d’estimer des directions, tu finis par trouver où est la mine.





Mais ici on n’a pas la direction justement.









DanLo a écrit :



Il me semble assez facile en pingeant régulièrement des points précis à 500m de distance les uns des

&nbsp;(…)

&nbsp;il y a de quoi suivre à la trace





Il y a de quoi suivre à la trace sur un damier ayant 500m par case, et tant qu’il n’y a pas d’autres malade par case.





un député utilisant l’application (et tu découvriras très facilement

lequel soit en recoupant avec d’autres infos, soit en allant par

toi-même dans un des rayons de 500m en question).



Ben oui, parce qu’un cercle de 500m de rayon, c’est tout petit, alors tu identifieras très facilement le député en question… un cercle de 500m, c’est juste 3 à 4 fois la taille du Louvre, aucun problème pour identifier une personne là dedans.

Ah oui, au fait, c’est un député ? Ou un employé du parlement ? ou un facteur étant passé par là ?

&nbsp;









Faith a écrit :



Même pas. En déplaçant le cercle, tu vas récupérer d’autres malades.

Ton chiffre va passer à 0, 2, 3 ou 10. Parfois à 1, mais ce sera un autre malade à l’autre extrémité du cercle…

Et de tous ces chiffres, tu ne sauras jamais si celui que tu veux repérer en fait partie ou non.







Tu trompes. Comme je l’ai indiqué, je décris uniquement le cas le plus simple (1 seul cas relativement isolé) pour expliquer le principe. Mais c’est juste pour introduire les bases de ce que l’on appelle la triangulation. Comme je le précise après, il est possible d’étendre la logique pour en traiter plusieurs dans une même zone. Il sont juste traités les uns après les autres. Une fois que l’on en a isolé un, on tire le fil pour en isoler un autre (quand le système répond 2 mais que l’on en connaît déjà un, c’est comme si il n’y en avait qu’un). En pratique, il existera toujours au moins un endroit ou on pourra isoler un cas et, à partir de là, tirer le fil pour les récupérer un par un. L’image du Mastermind est assez bonne. Le principe de résolution est assez proche. La recherche se fait sur le principe de l’algorithme de Montecarlo.



Tout le temps que ça part des coordonnées GPS originales pour afficher le résultat, peut importe la dimension des zones sur lequelles repose l’application en interne. Tout le temps qu’il est garanti que la distance minimale est bien inférieure ou égale à 500m pour les résultats retournés, ça fonctionne pareil.



Sinon, si l’application s’appuie d’une grille pré-découpée et ne fait que recenser le nombre de cas par cellule (sans s’appuyer sur les coordonnées GPS) alors, effectivement, il devient plus difficile de localiser précisément (précision maximale = la taille des cellules). Mais l’application donnerait alors des résultats faux. Les cellules traversées par le rayon à 500m délimitant la zone de résultat ne peuvent être traitées que par le biais un ratio proportionnel à la surface incluse. Ce ne sont plus des valeurs justes. Ce qui, en pratique, peut être acceptable si les cellules sont très petites par rapport aux 500m et que l’extrapolation statistique n’intervient vraiment qu’a la marge. Mais alors, plus les résultats sont exacts, plus la localisation est précise et, sur 500 m, ça ne devrait pas excéder quelques dizaines de mètres pour que les résultats retournés ne soient pas complétement déconnants.



Sinon, sur l’intérêt de localiser un malade, ce n’était pas mon propos. Je suis d’accord sur le fait que ce soit sans intérêt. Mais je pense que, si c’est possible, certains sortiront des cartes. Le nombre de requêtes à effectuer n’est pas vraiment un problème. Ça converge très vite si c’est bien écrit donc il ne faut pas tant de requêtes que ça (surtout si on limite la précision à 10 ou 20 de mètres). il y a de grandes zones vierges. Ce sont donc des îlots qui sont à traiter et non pas un grand maillage serré.



Ça peut devenir problématique pour les relations de voisinage des malades. Il y en a qui ne sont vraiment pas très malins…



S’il y a 1 individu est dans un cercle de 500m centré en A, mais qu’il y a 0 individu dans ce même cercle centré en B (proche de A), alors l’individu est dans la direction de A depuis B. Certes, il n’y a pas que 1 ou 0 individus dans les cercles, donc c’est pas si simple.



Le problème complet est donc de trouver la position d’individus qui ont générés des cartes de densité données, sachant que les individus se déplacent (ou pas) au court du temps.



C’est un problème courant dans pas mal de domaine où l’on ne peut pas observer directement chaque individu mais on peut estimer le nombre d’individus dans une zone: cellules, atomes, personnes, …


Ah oui je n’étais pas à jour sur le chiffre, 90 millions d’utilisateurs apparemment.

Cela fait un peu moins de 7 % (6,6%) de la population.



Soit une couverture de 30 personnes / km² (l’Inde a une densité de 455pers. / km²) en moyenne.

Soit 30 personnes par million de m².

Un disque de rayon 500m² c’est 0,785 millions m².

Donc on a une densité moyenne de 23 personnes par ping de l’application.



Ça me semble commencé à être dans ces cas limites pour pouvoir suivre des flux de personnes entre zones de 500m² effectivement… mais clairement pas infaisable si l’application est fiable et si on y met des probas et un peu de math dans le tas.



Si tu ping plusieurs zones en semi-simultané, tu peux très facilement voir les flux de gens entre les zones pingées. Je vois pas en quoi l’hypothèse de “toujours voir les mêmes personnes dans la réponse” est invalide.

Les seuls cas que l’on ne peux pas observer, c’est sur dans la même intervalle de 10 secondes (je suppose que c’est suffisant pour pinger 2 cercles adjacents) avoir 2 personnes qui échangent de zone simultanément (parmi les 23 personnes par zone toujours, hein).

Pas dit que ça arrive souvent… mais effectivement on aura probablement pas un résultat d’estimation de déplacement des 23 personnes fiable à 100%.



J’ai une collègue qui a eu de très bon résultats sur la surface d’une entreprise dans à peu près les mêmes conditions ceci dit. (de l’ordre de 80+% de réussite de compréhension des mouvements)



Dans tous les cas on reste sur des chiffres très faibles en concentration d’utilisateurs au m².


c.f. mon commentaire de réponse à Fred42.



Sinon tu poses des fausses questions auxquelles ma propre parenthèse que tu cites répond, je te laisse donc relire ce à quoi tu réagis.



4 fois le Louvre, c’est clairement pas si grand que ça je trouve, ouai.. !


Et si tu lisais l’article sur WIred, tu verrais que l’auteur fait clairement la démonstration de ce qu’il avance…



La seule inconnue pour lui c’est la fiabilité de l’application sur les données qu’elle renvoie.








stratic a écrit :



En pratique, il existera toujours au moins un endroit ou on pourra isoler un cas







Ben non, pas forcément. Dès que l’app est un peu utilisé, tu te retrouves avec 10 000 personnes par km². L’app donne des infos dans un cercle de 500m de rayon. Donc ern fait c’est “exploitable” que dans les endroits isolés.







stratic a écrit :



fois que l’on en a isolé un, on tire le fil pour en isoler un autre (quand le système répond 2 mais que l’on en connaît déjà un, c’est comme si il n’y en avait qu’un).





Ça ne marche pas ça. Tu pars du principe que les points ne bougent pas, ou qu’on puisse leur associer une identité que l’on peut retrouver entre deux ping. Mais ce n’est pas le cas.



Si par chance tu arrive à isoler un point de donnée, faut encore le relier à une identité. Étant donné que l’app ne fuite aucune donnée, c’est juste débile d’annoncer qu’elle permet de retrouver une information sur qui que ce soit.







stratic a écrit :



Le nombre de requêtes à effectuer n’est pas vraiment un problème.







Ben si, la complexité de l’algorithme évolue exponentiellement avec le nombre d’utilisateurs. Donc un throttling minimal rend caduque tout exploitation.









stratic a écrit :



Une fois que l’on en a isolé un, on tire le fil pour en isoler un autre (quand le système répond 2 mais que l’on en connaît déjà un, c’est comme si il n’y en avait qu’un)





Quelle est la complexité d’un tel algorithme ?

C’est bien plus complexe que le problème du voyageur de commerce: faisable avec quelques points, hors de portée dès qu’on tape quelques dizaines de noeuds.



&nbsp;

La recherche se fait sur le principe de l’algorithme de Montecarlo.



A priori, randomiser la recherche est certes indispensable, mais insuffisant pour transformer le problème en problème soluble en temps raisonnable. On est dans du NP là, pas du P.



Néanmoins, précise ta pensée si tu y as réfléchi.

&nbsp;



Très facile en fait. A partir du moment ou on localise un endroit ou il n’y a qu’un seul résultat, on sait le localiser exactement (en appliquant le principe de montecarlo). Sur le principe, on résout donc d’abord les positions sur les bords des ilots à traiter et on progresse ensuite vers le “centre”. C’est beaucoup plus simple qu’on ne l’imagine au premier abord. Contrairement à la première impression, la présence de plusieurs résultats dans une même zone permet au contraire de converger plus rapidement vers des positions précises car quand on trouve des résultats en trop, c’est juste qu’on est allé trop loin dans la zone à explorer et que l’on peut encore réduire la zone de recherche.


Sauf si les points se déplacent ou disparaissent et réapparaissent. Arrêtez de traiter ça comme un problème statique.


Relis moi. Il n’y a aucune complexité au niveau de l’algo. C’est vraiment basique. La “complexité” est constante quelque soit le nombre de points. La simplicité est sans commune mesure avec le problème du voyageur de commerce.



Je citais Montecarlo pour le principe du balayage de la surface en faisant des tests à de multiples endroits de la surface et progressant par rapport au résultat de ces tests. Il n’y en revanche absolument pas besoin d’avoir recours à l’aléatoire (ce serait même un erreur). Il suffit de faire des tests sur un pas de grille de départ pour balayer la surface et de réduire le champ de recherche (en divisant le pas par 2) dès que ça matche dans la cellule. Ce pas est le pas de déplacement du centre des zones de 500m. Les déplacements des tests et la réduction du pas de déplacement sont pilotés par les résultats retournés. Dans tous les cas, on est sur quelque chose qui converge avec de simples boucles de balayage imbriquées.








stratic a écrit :



Relis moi. Il n’y a aucune complexité au niveau de l’algo.



Touriste.

La complexité d’un algorithme, ce n’est pas la difficulté à écrire le code, c’est la vitesse d’augmentation du nombre de calculs en fonction du nombre d’entrées.









Faith a écrit :



En triangulant des distances dont l’incertitude est de 2 mètres, on obtient une localisation qui est l’intersection de 3 bandes de 4m de large.

Ca donne une forme approximativement hexagonale de 4m de “diamètre”, environ 10.4m²

Si la précision est deux fois moins bonne, ça nous fait une zone de 41.6m², soit 4x moins bonne.





Ce n’est donc bien pas propre à la triangulation. Tu peux utiliser d’autres algorithmes, tu auras toujours besoin de recouper plusieurs mesures dont les incertitudes vont se multiplier. La triangulation ne devient pas imprécise à cause de ça.



Après, on est d’accord, ici il ne s’agit pas d’une triangulation (il s’agirait de triangulation si on nous donnait la position d’une même personne par rapport à différent points) mais d’un problème bien plus complexe à résoudre et je te rejoins sur le fait que c’est très vite inexploitable en pratique.



On nous donne juste le nombre de personnes infectées dans un périmètre

donné, le problème est ici d’isoler une seule personne par périmètre de

manière à pouvoir faire de la triangulation justement. Tout en sachant que si on trouve deux zones proches avec 1 personne, rien n’indique qu’il s’agit d’une seule personne et non de deux personnes situées à des extrémités des deux zones.



A partir du moment où la triangulation est possible, alors on a la position de la personne (à l’incertitude des mesures en effet, mais c’est pas ça qui fait que cette méthode est irréalisable en pratique, c’est le fait d’isoler une personne unique).

&nbsp;









haelty a écrit :



Tout en sachant que si on trouve deux zones proches avec 1 personne, rien n’indique qu’il s’agit d’une seule personne et non de deux personnes situées à des extrémités des deux zones.





Tout à fait, et comme en plus les personnes se déplacent, c’est encore plus probable d’avoir deux cercles très proches renvoyant 1 sans que ce soit la même personne.

Cette contrainte entraine la nécessité de faire avancer l’algo par tout petits incréments, nécessitant beaucoup de temps pour demander les positions, etc.

&nbsp;



Ce n’est donc bien pas propre à la triangulation. Tu peux utiliser

d’autres algorithmes, tu auras toujours besoin de recouper plusieurs

mesures dont les incertitudes vont se multiplier.



La triangulation multiplie les incertitudes.

Certains algo pourraient se contenter de conserver la pire.









Faith a écrit :



La triangulation multiplie les incertitudes.

Certains algo pourraient se contenter de conserver la pire.





A partir du moment où tu veux une position à partir d’une distance par rapport à un point connu, il te manque une inconnue. Il est nécessaire de recouper des mesures.



Comment pourrais-tu avoir un algo qui te retourne une position tout en ne se basant que sur une seule mesure de distance&nbsp; par rapport à un point connu (puisque tu parles de ne conserver qu’une seule mesure) ?

&nbsp;









psikobare a écrit :



Ben non, pas forcément. Dès que l’app est un peu utilisé, tu te retrouves avec 10 000 personnes par km². L’app donne des infos dans un cercle de 500m de rayon. Donc ern fait c’est “exploitable” que dans les endroits isolés.







Non pas du tout. Globalement ce sont des îlots. Même si ces îlots sont très denses, il reste facile d’isoler les cas en périphérie. A partir de là, on peut tout “détricoter”.



Contrairement à la première impression, la présence d’une multitude de résultats dans une zone restreinte permet au contraire de converger plus rapidement. On cherche à progresser de 1 en 1 et dès qu’il y a plus de résultats qu’attendu, c’est qu’on est allé trop loin et que l’on peut restreindre la zone recherche pour converger sur le point étudié.







psikobare a écrit :



Ça ne marche pas ça. Tu pars du principe que les points ne bougent pas, ou qu’on puisse leur associer une identité que l’on peut retrouver entre deux ping. Mais ce n’est pas le cas.







Non je ne part pas du principe que les points aient une identité. La même identité peut se trouver “flashée” en deux points différents. Dans ce cas on la voit comme deux résultats différents.



En revanche, oui je considère que sur une zone étudié le point étudié est stable. C’est à dire qu’il ne disparaît pas pendant que l’on essaie de le localiser. Les points qui disparaissent (ou qui se déplacent, ça revient au même) ne peuvent pas être localisés ainsi. Si le système est vraiment en temps réel, alors oui c’est une grosse limite de ce que je décris. Seuls les points fixes peuvent être localisés. Mais, ce sont aussi les seuls qui soient potentiellement identifiables et pour lesquels un identité peut être devinée, donc les seuls potentiellement dignes “d’intérêt”.



Ce que tu soulève est le talon d’Achile de l’approche. Vu que la progression sur une zone se fait de point en point, si le système est très dynamique, et que les points de références disparaissent, ça oblige à revenir en arrière ou repartir du bord de l’îlot, ce qui peut empêcher toute progression.







psikobare a écrit :



Si par chance tu arrive à isoler un point de donnée, faut encore le relier à une identité. Étant donné que l’app ne fuite aucune donnée, c’est juste débile d’annoncer qu’elle permet de retrouver une information sur qui que ce soit.







Quand la position pointe sur un bâtiment, voir une maison individuelle, ça identifie quand même un peu, et justement, là ce sont des points fixes…







psikobare a écrit :



Ben si, la complexité de l’algorithme évolue exponentiellement avec le nombre d’utilisateurs. Donc un throttling minimal rend caduque tout exploitation.







La complexité est constante quelque soit le nombre d’utilisateurs. Le nombre de requêtes augmente en fonction du nombre d’utilisateurs (plus de points à localiser) mais sur une zone données le nombre de requêtes par utilisateur est inversement proportionnelle au nombre d’utilisateurs présents dans cette zone (les positions convergent plus rapidement).



Le nombre de requêtes dépend plus de la surface à couvrir plus que du nombre d’utilisateurs présents dans cette surface et il n’augmente pas exponentiellement en fonction du nombre d’utilisateurs. Plus il y a d’utilisateur, meilleur est le rendement. On aurait plutôt à faire à un profil de courbe de type logarithmique plutôt qu’exponentiel. C’est à dire tout l’inverse.



J’ai fais les calculs dans un autre msg juste au dessus, on est très loin des 10 000 personnes par îlot..!



Avec à peine moins de 30 personnes par zone, c’est ridiculement simple, même à la main…


Touriste, tu, me fais bien rire <img data-src=" />



La résolution de ce genre de problèmes, ça touche souvent le le cœur de mon métier. Par exemple, si tu défragmente des disques sous avec le défragmenteur Windows, tu fais tourner la base code que j’ai créé il y a maintenant 32 ans. Pour VMS de Digital à l’époque, et c’est encore la même base de code aujourd’hui. Si tu est développeur Java, ou si tu travaille avec BD Oracle par exemple, la aussi tu fais probablement tourner pas mal de choses dont certains algos repose sur une conception faite par un touriste. Et surtout, attention si tu prend le train, la plateforme qui permettant plannification des trains, leur constitution et l’affectation des conducteurs avait été conçue par le même touriste.



Je n’ai jamais parlé de complexité de code! Quand je dis que ça converge, c’est qu’il n’y a pas de récursion ou de branches parallèles à explorer pour aboutir à une solution. Ce sont de simples boucles imbriquées qui convergent vers une solution unique sur chaque point. Leur profondeur maximale est connue et limitée. Plus il y a de points, et plus ils sont concentrés, plus la profondeur nécessaire pour traiter individuellement chaque point diminue.



Sinon, j’arrête là. C’est relativement simple et tu veux absolument que ce soit complexe. C’est fatiguant de parler dans le vide.








stratic a écrit :



Je n’ai jamais parlé de complexité de code!



&nbsp;

Moi si, et tu as répondu hors-sujet.



Oui… et ? Bah qu’ils le sachent.

Au boulot, on prend la température à 2000 personnes tous les matins. Je sais exactement qui est normal, froid ou chaud voir trop chaud (retour maison) et alors qu’est ce tu veux que je fasse de ces data. C’est pas très important.

Quelqu’un veux savoir où j’habite, il prend le botin, cherche sur internet, me suis dans la rue.

Je suis malade et tout le monde le sait. Oui, et ? il est où le problème.

Si je fais un cancer, le sida, une opération. Peu importe mais avec arrêt de travail, les collègues vont bien se rendre compte que je ne suis pas là. Forcément quelqu’un va ouvrir sa bouche et tout le monde ou presque va le savoir. Tout se sais.

Et alors ? je ne vois toujours pas le problème.

La France qui ne veux pas utiliser le protocole d’apple et google. Et bien, tant pis pour eux, c’est çà ou rien.

On n’aura pas de traçage, les défenseurs des droits seront content.

&nbsp;J’ai même vu que des gens refusaient de montrer leur température pour rentrer sur un site de production.

Et bah, retour maison et pas payé. Normal. Le règlement c’est le règlement. A situation exceptionnelle, mesure exceptionnelle.








Frousse a écrit :



C’est assez facile d’envisager les conséquences du pire scénario, qui est possible par triangulation et encore plus facilement en zones rurales à faible densité de population : violence et harcèlement dirigés vers des malades et leurs familles et tout ce qui peut passer par la tête d’une personne malveillante qui a accès à la localisation d’une personne.



C’est important de remonter ce genre de problèmes sur les applications

de contact tracing à l’heure où beaucoup de gouvernements préparent

leurs solutions maison.







Il n’y a pas besoin d’application pour ça.



Aux Etats Unis, une femme travaillant pour le gouvernement a été dénoncée publiquement par un pseudo journaliste d’investigation (en balançant son nom, adresse, etc) comme étant celle qui a introduit le COVID-19 là bas. Son discours étant protégé par le premier amendement de leur constitution, pas beaucoup de recours.



Et visiblement, installer des applications de surveillance à l’insu d’une personne semble aussi être très en vogue.









stratic a écrit :



La résolution de ce genre de problèmes, ça touche souvent le le cœur de mon métier. Par exemple, si tu défragmente des disques sous avec le défragmenteur Windows, tu fais tourner la base code que j’ai créé il y a maintenant 32 ans. Pour VMS de Digital à l’époque, et c’est encore la même base de code aujourd’hui. Si tu est développeur Java, ou si tu travaille avec BD Oracle par exemple, la aussi tu fais probablement tourner pas mal de choses dont certains algos repose sur une conception faite par un touriste. Et surtout, attention si tu prend le train, la plateforme qui permettant plannification des trains, leur constitution et l’affectation des conducteurs avait été conçue par le même touriste.





Ha oui, tous des problèmes très proches du cas qui nous concerne ici… <img data-src=" />



Les chevilles, ça va , sinon ? ^^



sinon pas besoin de trianguler, la liste des personnes infectées a fuitée :https://twitter.com/fs0c131y/status/1258672192876949504


Je voudrais savoir si je comprends bien l’énoncé “Elle propose de savoir, dans un rayon de 500 mètres à 10 kilomètres” :

Est-ce que cela veut dire qu’on peut faire la mesure pour un rayon de 500m puis un rayon de 600m et faire juste la différence pour se faciliter la tâche ? <img data-src=" />



Edith, je ferais mieux de lire les liens avant, c’est un poil moins simple : “ You can choose the radius of the area. It can be 500m, 1km, 2kms, 5kms or 10kms”, l’auteur monte jusqu’à 100 km mais n’indique pas le pas d’incrémentation… Etrange cela pourrait aider.


L’analyse de la surface d’un disque dur 100% à voir avec ce genre d’algo. Sinon, les autres ne sont des exemples généraliste à quelqu’un qui vous traite d’artiste, et où seul une réponse de ce genre est possible.



Sinon, merci de de t’inquiéter de ma santé. Mes chevilles vont très très bien. Je n’ai jamais eut aucun problème de ce côté, bien au contraire.


Fermer