« »
7/06/2008

Rétro-ingénierie (reverse-engineering) : Possible algorithme de Tinyurl, minurl et autre Tinyurl-like

Je suis actuellement en train de développer une application Adobe Air comme certains le savent, et j'ai besoin (ou plutôt envie) de créer moi aussi mon propre "raccourcisseur" d'url.

Apparemment la plupart des services du genre se base sur une base de données, l'objectif pour être concurrentiel est donc d'effectuer le moins de requête possible afin que le service soit le plus rapide. Après avoir soumis à la suite plusieurs urls différentes à minurl.fr, j'ai obtenu cette suite d'url :

  • http://minurl.fr/12
  • http://minurl.fr/13
  • http://minurl.fr/14
  • http://minurl.fr/15
  • http://minurl.fr/16
  • http://minurl.fr/17

Que peut-on en conclure ?

  1. A chaque nouvelle url qui n'existe pas dans la base de données
    1. On créé un identifiant, supérieur au dernier identifiant, que l'ont lie à l'url (ou plutôt un équivalent compressé de l'url).
      1. Donc dans la table de notre base de données on à pour le moment les champs suivant :
        1. id varchar(10) (primary) : identifiant pour l'url qui sera afficher
        2. url varchar(40) (index) : champs pour l'url compressée
          1. Il est préférable que le contenu de ce champs soit compressé si l'on ne veut pas une énorme base de données mais cela n'est pas obligatoire !
          2. Dans cette exemple d'algorithme nous ne nous soucierons pas de la compression de l'url.
  2. Si le script reçoit un identifiant
    1. Chercher dans la base de données si l'id existe
      1. Il existe : on retourne l'url (il faudra la décompresser si on l'a compressée)
        1. On redirige vers cette url.
      2. Il n'existe pas : on informe l'utilisateur.
  3. Si le script ne reçoit pas d'identifiant
    1. On propose le formulaire d'ajout

 

Maintenant, on répète l'expérience avec Tinyurl, on à donc cette suite d'url :

  • http://tinyurl.com/6l74df
  • http://tinyurl.com/6d8r75
  • http://tinyurl.com/5o5c7d
  • http://tinyurl.com/5tfegj
  • http://tinyurl.com/63kjqo
  • http://tinyurl.com/6ys8ym

Que peut-on en conclure ?

  1. Il semble que Tinyurl utilise un système de création d'ID aléatoire, ce qui empêche toute prédiction sur le prochain ID à venir.
  2. Chaque nouvelle ID créé est de la forme 5XXXXX ou 6XXXXX (d'après mes tests). Il est donc possible que les ID de la forme 4XXXXX, 3XXXXX, 2XXXXX est déjà été tous utilisé.
    1. Il est donc fort probable que l'algorithme de Tinyurl, répartisse les ID fraichement créé sur deux plages qui n'ont pas encore été complètement remplie (dans notre cas 5XXXXX et 6XXXXX). Nous pouvons émettre cette hypothèse vu que les plages [4XXXXX, 3XXXXX] et [2XXXXX, 1XXXXX] on déjà été rempli.
      1. Exemple, si l'on entre http://google.com l'ID de TinyUrl est http://tinyurl.com/1c2 : notre théorie est donc sans doute valide car cette adresse à été entrée dans les débuts de Tinyurl (par une personne qui souhaitait tester le service) et qu'au lancement l'algorithme devait travailler sur une plage [2XXXXX, 1XXXXX].
  3. L'algorithme semble donc bien plus complexe que celui élaboré plus haut.

 

Nous avons donc une base d'algorithme pour créer notre service, bien sur, il est extrêmement conseillé de l'améliorer mais il reste néanmoins fonctionnel et c'est ce que l'on souhaite d'un algorithme n'est-ce pas ?

« »
 
 
Made with on a hot august night.
http://bit.ly/1II1u5L