samedi, 30 décembre 2006

Surchages de méthodes statiques en PHP

Un tout petit exemple pour exposer le problème :

class A {
  public static function f() {
    echo get_class();
  }
}

class B extends A {}

A::f();
B::f();


A::f() va afficher A, par contre B::f() va aussi afficher A, alors que la réponse attendue serait B.

Ce comportement est connu des développeurs OO, peut s'avérer ennuyeux dès qu'on utilise des fonctions statiques surchargées, car les appels à self::une_fonction() (une_fonction est donc une méthode statique) dans le parent résulteront toujours à un appel de la méthode du parent, et non pas celle surchargée dans le fils. La raison est que self dans la classe parente représente le parent, comme c'est aussi le cas dans d'autres langages OO.
Illustrons les limites de ce comportement avec la mise en place d'une factory toute simple :

class A {
  ...
  public static function create($params) {
    $class = get_class();
    return new $class($params);
  }
}
class B extends A {}
$b = B::create($myparams);


$b contiendra toujours un objet de classe A, car get_class retournera toujours A.

L'idée pour palier à cette limitation est donc simplement d'ajouter un argument à la fonction create de A, qui sera la classe à instancer :

class A {
  ...
  public static function create($params, $class = __CLASS__) {
    return new $class();
  }
}
class B extends A {
  public static function create($params, $class = __CLASS__) {
  return parent::create($params, $class);
  }
}
$b = B::create($myparams);


Avec cette petite adaptation, $b sera bien un objet B.

De manière plus général, si on envisage d'utiliser des fonctions statiques surchargées, PHP nous permet de gérer l'héritage en passant la classe en argument et en appelant la fonction statique au moyen de la macro call_user_func :

class A {
  protected static une_fonction($arg) { return $arg + 1; }
  ...
  public static function create($params, $class = __CLASS__) {
    $res = call_user_func(array($class, 'une_fonction'), $args);
  ...
  }
}
class B extends A {
  protected static une_fonction($arg) { return $arg + 2; }
  public static function create($params, $class = __CLASS__) {
  return parent::create($params, $class);
  }
}
$b = B::create($myparams);


Grâce à cette macro call_user_func, B::create appellera donc bien B::une_fonction.

jeudi, 21 décembre 2006

Spam image

Selon une analyse menée par une société spécialisée dans la sécurité informatique, le spam image a augmenté de façon impressionnante en un an, passant de 4,8 % du spam global en octobre 2005 à 25 % un an plus tard. Loin d'être en recul, le volume global du spam est passé de 31 milliards de messages par jour à 61 milliards sur la même période. De plus la taille moyenne des messages a elle aussi augmenté, passant de 8,9 Ko à 13 Ko. Le spam consomme donc désormais 819 téraoctets de bande passante par jour !

En attendant que d'efficaces techniques de prévention du spam image soient mises au point, n'hésitons pas à désactiver l'affichage automatique des images dans notre gestionnaire de courrier, ce sera déjà une première défense. Et ayons toujours en tête que le but des spammeurs est moins de vous vendre quelque chose que de vous arnaquer purement et simplement...

mardi, 19 décembre 2006

Ryzom, un MMORPG désormais libre

Un fait peu habituel secoue l'univers du libre ces derniers jours : le rachat de la propriété intellectuelle (code source, monde, ...) du jeu de type MMORPG nommé Ryzom afin de la libérer.

Cette initiative, soutenue par la FSF elle-même qui y joue un important rôle de mécène, montre à quel point l'univers du libre est réactif et motivé, mais pointe le doigt sur un fondement de notre société capitaliste :

La liberté a un prix.


On peut donc en déduire comme corolaire qu'il faut gagner de l'argent pour rester libre.

Et tout le paradoxe du serpent qui se mort la queue apparait quand on prend le cas la Fondation Mozilla, qui gagne de l'argent grâce a des partenariats avec notamment Google, faits incompris et fortement critiqués par beaucoup de monde (actualité sur par exemple 1 et 2, critiques dans la blogoshpère).

Une petite illustration logique pour toutes les personnes qui n'auraient pas compris l'intérêt de la Fondation Mozilla :

Il faut gagner de l'argent pour être libre.
La fondation Mozilla gagne de l'argent.
Donc la fondation Mozilla est libre.

lundi, 18 décembre 2006

Reverse MD5

La fonction MD5 est une fonction dit à sens unique, c'est-à-dire que ne connaissant que la sortie, il est difficile de trouver l'entrée qui a produit cette sortie.

C'est pourquoi des reverse md5 databases sont apparues sur Internet. Leur principe est tout simple : c'est une grande base de données contenant la pair (texte, hash). Ainsi on peut la questionner du hash recherché et elle nous retourne le texte correspondant si il est connu.

La base de données doit donc être remplie avant de pouvoir produire des réponses, mais une fois qu'elle contient suffisamment de données, les recherches peuvent commencer à être intéressantes. Les techniques des remplissages sont simples, elles vont du parcours de pages web ou de dictionnaires pour rechercher des mots quelconques à l'ajout manuel par des utilisateurs.

J'ai rapidement fait une petite application qui questionne plusieurs des ces reverse md5 databases, qui elle est disponible à l'addresse http://md5.noisette.ch/form.php

Elle se base sur la toute petite API suivante : http://md5.noisette.ch/?hash=<le_hash_en_hex> qui retourne du XML

<md5lookup>
  <hash><!--[CDATA[2a0231531bc1a7fc29e2fa8d64352ae9]]--></hash>
  <string><!--[CDATA[noisette]]--></string>
</md5lookup>


L'approche est très alléchante car une fois le hash dans la base de données, les réponses sont fournies en O(1). Les mots de passe stockés en md5 peuvent donc être retrouvés extrèmenent rapidement.
La contre-partie de cette approche est qu'elle nécessite beaucoup de hash précalculé avant d'être utilisable, et donc produira une énorme base de données :
Le md5 étant sur 128 bits, on pourrait avoir une table de 2^^128 entrées, pour peu qu'on ne prenne pas en compte les doublons. Donc rien que pour les hash, il nous faudrait ~5*10^^39 bytes de stockage = ~5000 téra de téra de téra bytes. Enfin juste pas possible quoi. Si on fait le raisonnement inversion on se dit que notre serveur a 200Gb d'espace disque, on peut donc stocker 12.5 milliards de hash, donc 12.5 milliards de possibilités de mots de passe = un peu plus de 2^^33 possibilités. On est loin des 2^^128...

En résumé, c'est une approchoe time / memory tradoff 100% mémory :)

jeudi, 7 décembre 2006

Gentoo sur la PS3

Dans la famille "Tchötégik", voici un petit cookbook sur "Comment installer une Gentoo sur sa PS3" :


http://whitesanjuro.googlepages.com/


L'intérêt, en plus d'être purement académique car les jeux ne tournent pas (encore) sur cet OS et d'étudier le hardware contenu dans la console, est plutôt de démontrer la flexibilité de Gentoo à s'adapter à n'importe quel type d'environnement.

mercredi, 6 décembre 2006

Une nouvelle bulle internet en formation ?

Cette question défraie la chronique ces jours, et j'ai trouvé qu'elle méritait un petit article. Non pas pour en expliquer les raisons ou essayer de deviner la date de son éclatement, d'autre le font mieux que moi, mais parce que je suis tombé sur la citation suivante :

L’avantage avec les bulles [économique], c’est qu’elles peuvent toujours se dégonfler avant d’éclater.
Mais l’inconvénient avec les bulles, c’est que les gens croient vraiment qu’elles peuvent se dégonfler avant d’éclater...


Qui, bien qu'amusante, a le mérite d'être entièrement fondée à l'heure ou les entreprises 2.0 sont formées sur une base de levée de fonds dans le seul but d'être revendue dès l'ombre du début d'un éventuel profit à l'horizon.

mercredi, 29 novembre 2006

Recrutement Google, étape #2

Mardi 28 novembre je me suis rendu dans les locaux de Google à Zürich afin de procéder à la suite du processus de recrutement. L'heure de rendez-vous, fixée à 10h00, n'étant pas trop contraignante, j'ai pris le train à Neyruz à 07h45 pour arriver à 09h38 à Zürich, et finalement 9h45 à Freigutstrasse 12, 8002 Zurich.

Le bâtiment est une ancienne banque privée, de couleur rosé et dont le style s'apparenterait au début du 20ème siècle. La porte d'entrée est fermée à clé, et il faut s'annoncer avant de pouvoir entrer. Puis une fois à l'intérieur, il faut s'inscrire sur un terminal et signer sur une tablette, et un badge autocollant est directement imprimé.

L'intérieur du bâtiment est plutôt blanc, avec du parquet sur le sol, mais ce qui frappe c'est les accessoires (poufs, ballons, coussins) de couleurs vives disposés un peu partout. On se croirait en plein jardin d'enfants. Seul les 2 écrans 20 pouces par place de travail rappellent qu'on est bien dans une entreprise de services.

Ma journée s'est composée de 4 entretiens techniques et d'un repas avec Peter, un des deux ingénieurs qui m'avait interviewé à l'EPFL.

Les questions posées étaient de nouveau très algorithmiques, principalement axées sur l'organisation des données en arbre ou table de hashage, tout en tenant compte de l'ordre de complexité des fonctions proposées.

Un exercice a retenu mon attention et je souhaite vous en faire partager mon expérience :

La donnée est simple : un personne se tient en bas d'un escalier de N marches. A chaque pas, il peut monter une ou deux marches. Combien de possibilités de configuration de trajets différents a-t-il pour monter l'escalier ?

L'illustration ci-dessous schématise le problème.


Le raisonnement approprié pour ce problème est de se dire que pour atteindre une marche n, la seule possibilité est d'être passé par la marche n-1 ou n-2, et donc le nombre de chemin pour arriver sur la marche n est la somme des possibilités d'arriver sur les cases n-1 et n-2.
On a donc la formule de récurrence suivante :
Fn = Fn − 1 + Fn − 2
qui devrait nous faire penser à la suite de Fibonacci.

La suite de la question est simplement : comment peut-on calculer de manière efficace une telle suite ?

Il est possible de calculer une suite de Fibonacci de manière itérative, et donc d'une complexité de O(n), mais ce que je ne savais pas c'est qu'il existe une manière encore plus efficace pour calculer en O(log(n)) !

Cette solution repose sur deux propriétés : l'expression matricielle du problème, et le calcul de puissance.

La suite de Fibonacci peut donc s'exprimer sous la forme matricielle suivante :


Ce qui nous amène à l'expression suivante :



On voit apparaitre un matrice 2x2 élevée à la puissance n. On peut donc utiliser l'algorithme square-and-multiply (donné ci-dessou) pour la calculée, qui lui est en O(log(n)).



CQFD. Des questions ? Des remarques ?

Je suis reparti vers 15h30, fatigué mais content. Je devrais avoir une réponse dans le courant de la semaine prochaine quant à leur envie de m'engager ou pas.

Suite au prochain (et peut-être dernier) épisode...

vendredi, 24 novembre 2006

I'm the 58,920,569 richest person on earth!

Avec mon revenu actuel tout à fait moyen pour la Suisse (un peu moins de 4000.- brut / mois), je fais partie des 1% personnes les plus riches du monde, d'après le site GlobalRichList.

Imaginez ce que ça sera quand je toucherai mon salaire de ministre ;)

Plus sérieusement, voici une preuve criante que les richesses sont mal réparties.

Arriverons-nous à faire en sorte que la fossé qui sépare les riches des autres ne s'élargisse pas trop ? Un défi pour l'avenir autant important que l'environnement...

mercredi, 22 novembre 2006

Bug de l'an 2038

Le format Unix pour les dates, c'est-à-dire le nombre de secondes depuis le 1er janvier 1970, est une très bonne chose car ça représentation est très compact, on peut facilement comparer 2 dates, calculer des intervalles, etc.

Le seul problème qui en découle est que son implémentation sous forme d'entier, 32 bits sur la majorité des systèmes actuels, et condamné à subir un integer overflow, et ce dans un peu plus de (2^^32 / 3600 / 24 / 365 =) 136 ans à partir de la date de référence si la date est codée en entier non signé, (2^^31 / 3600 / 24 / 365 =) 68 ans si le codage est signé, c'est-à-dire vers l'an 2106 ou 2038 respectivement.
Il nous reste de beaux jours devant nous, mais cela montre à quel point on est incapable de ne pas reproduire le bug de l'an 2000...

vendredi, 17 novembre 2006

Quand Internet remplace les systèmes experts

Un article paru dans Info-du-net parlant de l'élaboration de diagnostiques pour des maladies montre à quel point la base de données "Internet" peut devenir utile en cas d'utilisation judicieuse :

Un système expert est une base de données de règles et de conditions qui nous amène, en posant des questions sur les symptômes, à un diagnostique précis du problème. C'est donc une base de données contenant tous les symptômes possibles, avec des relations entre eux, que l'on peut questionner. Un système expert n'est utile que si il contient une liste exhaustive des symptômes.

On remarque donc directement une ressemblance frappante avec Internet (ou du moins un moteur de recherche tel que Google) : une base de données que l'on peut questionner.

Internet devient donc un système expert grâce à la contribution des gens dans leurs domaines d'application. Toutefois la différence entre un système expert et Internet, c'est que la base du premier est constituée par des spécialistes et, si elle n'est pas exhaustive, elle est au moins fiable, alors que n'importe bien que la base Internet se met à jour en temps réel, n'importe qui peut y contribuer, même ceux qui n'y connaissent rien au domaine...