Attaque brute force, Java et parallélisme

Ippon a lancé il y a un peu plus d’une semaine un jeu qui a eu un beau succès:

http://blog.ippon.fr/2011/11/30/jeu-ippon-recrute-deuxieme-edition/

Un excellent retour sur ce jeu a été fait par Sébastien Prunier, et nous allons d’ailleurs nous baser sur sa solution pour la suite de ce billet. En effet, la dernière partie du jeu consistait à faire un algorithme de “brute force” afin de déchiffrer un mot de passe. Certaines personnes ont cru, à tort, qu’il s’agissait juste de faire une boucle “while” et de tester tous les cas possibles: cela rendait le déchiffrable impossible, à moins d’avoir beaucoup de temps disponible… Bien entendu il y avait une astuce, que pas mal de monde (dont Sébastien) a trouvé: étant donné qu’il s’agissait de trouver les lettres d’un pseudo-Sudoku, il n’y avait que 9 lettres possibles, qui ne répétaient pas, soit 9! possibilités (9! = 9*8*7*6*5*4*3*2*1 = 362 880 possibilités).

Le code de Sébastien permet ainsi de trouver la bonne combinaison en 80 secondes (sur mon MacBook):

https://github.com/sebprunier/IpponRecrute/blob/master/src/main/java/fr/ippon/rh/support/ForceBrute.java

Cependant, on peut faire plus performant: pour être exact, “probablement plus performant”, car tout dépend de vos données (plus le résultat se trouve “loin” dans notre jeu de test, plus la parallélisation va nous faire gagner du temps).

Nous allons pour cela voir plusieurs méthodes différentes: Node.js, Scala, Java “pur” et Spring.

Méthode n°1: utilisation de Node.js

Plusieurs personnes ont remonté qu’en utilisant Node.js, on pourrait certainement faire mieux. Voilà un bon exemple du “hype oriented computing”, que l’on m’a déjà sorti plusieurs fois lors du challenge USI 2011: node.js n’est volontairement pas multi-threadé, pour éviter de faire du context switching et éviter d’empiler des threads (typiquement une thread par utilisateur, comme c’est le cas dans beaucoup de nos “vieux” serveurs d’applications Java qui ne font pas de NIO). Cela permet d’avoir des applications très réactives, et qui supportent beaucoup d’utilisateurs, à partir du moment où ces applications “attendent” la majeure partie du temps. C’est un cas classique d’utilisation des serveurs d’applications: ils passent une grande partie de leur temps à attendre les données provenant d’une base de données. Node.js est donc particulièrement adapté à des sites Web utilisant une base de données complexe, mais est par contre peu adapté à des sites Web faisant beaucoup de calcul en local: un excellent exemple est donné en début du post maintenant célèbre “Node.js is Cancer“.

Ajoutons que sur nos machines modernes, l’histoire va plutôt dans le sens inverse de Node.js: nous avons de plus en plus de coeurs, chacun étant généralement moins puissant que la génération précédente.

Méthode n°2: utilisation de Scala

Scala 2.9 permet d’avoir des collections utilisant automatiquement les différents coeurs de votre système: c’est en quelque sorte l’inverse de l’approche de Node.js! Vous pouvez donc itérer sur une collection, et les traitements sur cette collection utilisent alors automatiquement plusieurs threads, répartissant ainsi les traitements sur l’ensemble des coeurs du système.

(1 to 1000000).toArray.par.map(_*2)

Le .par dans le code précédent dit à Scala d’utiliser les collections “parallèles”. Dans la pratique, ce code a cependant beaucoup de problèmes:

  • Il va utiliser le framework Fork/Join de Java 7: donc si vous êtes sour Mac OS X, comme moi, cela ne va simplement fonctionner que sur une seule thread.
  • <troll> Il est écrit en Scala, et donc personne ne le comprend </troll>
Pour une critique de cette fonctionnalité, nous vous conseillons de lire ce post de Cédric Beust.

Méthode n°3: Java pur

L’avantage de coder en Java “pur” est d’avoir enfin le niveau de contrôle voulu, avec un niveau de complexité très réduit (pas la peine de passer la semaine à apprendre un nouveau langage ou framework). Après, tout dépend de ce que l’on entend par complexité: personnellement, je préfère avoir 10 lignes de code de plus, que je comprends sans problème, plutôt que de devoir apprendre un nouveau langage, qui d’ailleurs me cache beaucoup de son fonctionnement.
Voici donc mon code en Java:
package fr.ippon.rh.service;

import org.jasypt.util.text.BasicTextEncryptor;

import java.util.*;

/**
 * Resolution de l'etape 3 par force brute.
 *
 * @author Sébastien Prunier
 * @author Julien Dubois
 */
public class MultiForceBrute {

    // Texte a decrypter
    private static final String etape4Texte = "5oi/MCVWOrk2V8bI2LY4XM4gKf/hqRnz6/d0HftJYadMv7xkIjUsTfvXyyf0kJ/D1Or0QMicOUf7YIAkAMWkbNJpLA5cgOHZvGZVC1LBGdpe0n3zY5VfyYjUIFu/0VNyLVMOAu4BaC3ncdPkh5Q0r+IQeTV+IqOOBlsozTfxeLYBJhxIUdSaXIVubo7RSPOn1Y0aLrTEZhlPkJFJhQohhOr5d0/zqre7HnFdc/9vSC3qda6VKwxd+yAhl762kOGReE4YbeMX/1wg175ruUaT4tgVYaOLXIRg0fqZYIwu37KUrOvtUD+inZSYwMpUrNSeV9Wshwoi6kBXkriEoc2Qg58b6WVfNTzGMFsRp/D4TGMx04hGg2WTT4lRPebqGl5cPm6qSeb7WET3xbJ4LUCvOgX0cDr22inxlGUgkbF7m8ApZw2kOverBgnhW+dE3amE+bP1Ac1ky4sSY0Sjeec2n4QI6hX9mwl7GBc9Ep8uF7t+XdZFmuml4/bFgxtDOpi8zQ6NYXe2/UT5S6i/hPPHHRa6OGL2ZAswBtAkcsYiw564hshKvzVOMtP05Zu19C1zY+84kmpsGbxxknSI61owCNOvF1tJitww4EmkLsIhgveV+RcmTQOiwONJET7Q9qK4RFpFuz+hu1Kel0QsMPZMlvhSsSTj+lmLHzG9nC5s4RcvLR1JeL27MvcfO0CxZx9XSYazu+LqVK2qlv+NXftT9JFx19hVIvAI/T4oM9xf3wYrLozs1GDRrPju2yVXZb91vn4TdWWIoXI8yGQ5AaHYVLNu5LVez/Q4sH/DRjjMHLGTsYpXNm/xRrwf10Aw78dO58dvUy+ClP6//0wq+9+tw4knCtZwPK6Ov1gqvCzUlp3voDO+J/7/9+OoA4OkdJv8Nsu02lWZ6/mDsrr49U8D8mJgmqze4jVLbXg61HCuzSCOhnHPtMmyfykDSFHXvSGCiuyGoWN5ObIAo/k9XxYlZNrGpwYq3aTwaKJwG1vTtLzHop0bfQ50+cz18LqynMB2t+Y5AQ9IGAvJX6nWrO/C8GBD/bE/lZT+i1XYhYJ0JB0zoadQK+AkyNNiwUe9Dv31e614zgVTGlJ/JvSQGBCAcK+wYNDK1fVY2EEWyQhlQ3BYdwcqF4myOI7wtZsPscwO1Kc8TwlPGypQ/6JG4Q5AUeXmzrXi67boN0tB4YUyG5cQk7Ehe3gaHI7rF5IGYT1id7agEcxphjRWMTo9fT9zIb2tsA9SBw+tici5y2E7xHbnEcMjF4xuGWjEy7sr8+PktLQldvcyAo0jkwlN8G6PyL7R1HcWITr8W9T3Qr4Yq3vazV16pDf7tofDEdoI9/9jt8wchTd1gCh/fnZk88TblEJqGnbrsPL+V2S+/YaLv7A7nZ1Bjy9WiQYiGnO1tgqMMbwt470eb1mIKyOcarrGcAATiEq8DxE1H8xeEpy23BtdTHJwT5COhCY+WbEWcYvCh6tBVs2PPvGSCJvClW2sR0n16kdtQiYS7uOiyOANoVy5ZygJ4jITiik3Lcfm3rE1DLaOM44DjRy1W5YTq7dXYKBsXcdoc+JmZ+7naVcBQ2q2XlZ/t2EvN9k1rVW4x7o7V7YsE2bbPqyvAxt0w1NsgVUaAsff361KxJgD7JXQXdpEyD+6KE1N+SmUOOUG22OxOZbsHy/+WPTKboQ5AMFG8pgR61TfAA6YqPakrGMKYGkpe0T+1t82Zo1t3Q+z2WxSLdRX5bslJjfuZSqqCpao40BbIEEFYAlmkTgDuKIaP4dA9o+b0M+lPjIM/mwWjxDdOraR3w0ncnyrUigGGisYsT5KHh89VHcyv94gJdMeT+5LC/7plTAd5HhMfp1Gq8f/6L1NWuhgyD/ne8VhNOuThkf53e5QzEuhUJqc8P/A68U/TG83SFgVRiPG2h06bEGC6yztEYlT/LPBQJkcB0I2Yg4BbcJRXTc6mZT54Fato3zRPYlqXdniQsxTR8w6WgVbRF93bn99lrJc9lLnqn9F8cFTG5QKp9u45yExo2Hy/0jmcpHyhaLlJP/ECuEeQK7M5H2Ro3rG2wwcAiuK0JV0meM6Isij2z4ldl2agyR2TKNgVcCynrScqFpzkEgwmPY6XuU/+qN89fgsRJ+8uuL0V1ah4zl70ymEzMYX48bI8icCIP4BFVp+mBymy2AUo7ln8zfxW4DKlZgVeyBsluDUqjn111m4oq/JkbzwlW3/D+KU9Yb52KwcHmbnpO8TcKXprhk2iJ04ak3IWY1u+pNU8WZRz3+jQWoPpIQtA8DQQdIYXrKwgXVerMsp2g4Tj0Irf5RnpcbjzXNM2A2mBo6ak/dp1I0tFK3Ue5HfSeBZ6iLBGsKii8VJPCw2AxM/JI74/Cl2BaggiMvpqAhMDyG7EhnaMZfgj+8Kd9P1hTp5nsZWGe3vnwDLLpnDqH4vER7J1uKpm3ig2XGuq3XFo7Fp6naG+B7qlSRF";

    private static long startTime;
    private static boolean stopDecryption;

    /**
     * Programme principal
     */
    public static void main(String args[]) {
        startTime = Calendar.getInstance().getTimeInMillis();

        MultiForceBrute multiForceBrute = new MultiForceBrute();
        multiForceBrute.decrypt();
    }

    private void decrypt() {
        Set passwords = new HashSet();
        permute("", "ABCDEGHIJ", passwords);
        System.out.println("Password size: " + passwords.size());

        int cores = Runtime.getRuntime().availableProcessors();
        System.out.println("Number of cores: " + cores);
        String[] passwordArray = new String[passwords.size()];
        passwordArray = passwords.toArray(passwordArray);
        Collection partitions = new ArrayList();
        int partitionSize = passwordArray.length / cores;
        for (int c = 0; c < cores; c++) {
            String[] partition = Arrays.copyOfRange(passwordArray, c * partitionSize, (c + 1) * partitionSize);
            partitions.add(partition);
        }
        for (String[] partition : partitions) {
            DecryptionThread decryptionThread = new DecryptionThread(partition);
            decryptionThread.start();
        }
    }

    /**
     * Calcul des permutations.
     *
     * @param sStart    chaine de depart.
     * @param sEnd      chaine d'arrivee.
     * @param passwords ensemble des mots de passe.
     */
    private void permute(String sStart, String sEnd, Set passwords) {
        if (sEnd.length()             passwords.add(sStart + sEnd);
        } else {
            for (int i = 0; i < sEnd.length(); i++) {
                String newString = sEnd.substring(0, i) + sEnd.substring(i + 1);
                permute(sStart + sEnd.charAt(i), newString, passwords);
            }
        }
    }

    private class DecryptionThread extends Thread {

        private String[] passwords;

        DecryptionThread(String[] passwords) {
            this.passwords = passwords;
        }

        public void run() {
            for (String password : passwords) {
                if (stopDecryption) {
                    return;
                }
                try {
                    BasicTextEncryptor textEncryptor = new BasicTextEncryptor();
                    textEncryptor.setPassword(password);
                    String decryptedText = textEncryptor.decrypt(etape4Texte);
                    if (decryptedText.contains("ippon")) {
                        System.out.println("Result: " +password);
                        long totalTime = Calendar.getInstance().getTimeInMillis() - startTime;
                        System.out.println("Solved in: " + totalTime + " ms.");
                        stopDecryption = true;
                    }
                } catch (Exception e) {
                    // Bad password !
                }
            }
        }
    }
}
Cette méthode permet de trouver la solution en seulement 15 secondes (toujours sur mon MacBook, qui utilise alors ses 8 coeurs et commence à chauffer).

Méthode n°4: Spring

Les trois solutions que nous avons vu, malheureusement, ne sont pas très industrielles: sur un projet en production, personne n’a envie de lancer ainsi des threads qui utilisent tous les coeurs disponibles, sans aucun contrôle.

Pour cela Spring propose une abstraction très intéressante, le TaskExecutor. Nous utilisons ici Spring 3.0 (voici la documentation officielle), sachant qu’il est prévu que Spring 3.1 supporte le framework Fork/Join, comme Scala, mais qu’à l’heure actuelle (Spring 3.1.0.M1), la documentation n’est pas à jour.

Dans sa version la plus simple, ce TaskExecutor permet de définir un pool de threads:

<bean id="taskExecutor" class="org.springframework.scheduling.concurrent.ThreadPoolTaskExecutor">
  <property name="corePoolSize" value="5" />
  <property name="maxPoolSize" value="10" />
  <property name="queueCapacity" value="25" />
</bean>

Dans la pratique, ce système permet de centraliser dans un seul endroit la configuration de son pool de Thread, et de pouvoir ainsi l’optimiser:

  • On peut bien entendu utiliser le nombre de coeurs disponibles: c’est une variable qui est tout à fait intéressante, car dans un environnement virtualisé le nombre de coeurs disponibles peut être amené à évoluer
  • On peut utiliser la configuration Spring pour modifier ces valeurs en fonction des environnements: c’est la notion de profils, qui va elle aussi apparaître avec Spring 3.1, mais qui elle est très bien documentée
  • On peut choisir de n’utiliser qu’un seul thread: c’est ce qui arrive en fait très souvent pour les applications Web, car on veut garder la majeure partie des coeurs disponibles pour les utilisateurs. Ainsi, l’ensemble des traitements de fond sont soumis à une seule et même thread, ce qui permet d’avoir une application toujours réactive, quels que soient les traitements lancés. L’intérêt ici est également d’utiliser la même thread pour des traitements différents.
  • On peut utiliser le pool de thread du serveur d’applications, et c’est ce que nous allons détailler plus bas.
En effet, les “gros” serveurs d’applications du marché (Websphere et Weblogic) proposent leur propre système de pool de thread, autour d’une API commune appelée CommonJ. Cette API devait être standardisée, et a fini par être abandonnée, mais elle est toujours disponible sur ces deux serveurs.
Le TaskExecutor permet donc d’utiliser ces APIs sans avoir à les connaître, et bien entendu uniquement en production (on pourrait avoir un profil “dev” qui utilise un pool de thread normal, et un profil “prod” qui utilise celui de Websphere):
<bean id="taskExecutor" class="org.springframework.scheduling.commonj.WorkManagerTaskExecutor">
    <property name="workManagerName" value="wm/default"/>
    <property name="resourceRef" value="false"/>
</bean>

Cette configuration permet ainsi au administrateurs de votre serveurs d’applications de modifier le nombre de threads disponibles en fonction des besoins et des capacités disponibles, ce qui est essentiel en cas de charge importante sur le serveur.

TwitterFacebookGoogle+LinkedIn
  • http://twitter.com/ndeloof Nicolas De loof

    As tu pensé à utiliser le Cloud pour paralléliser encore plus ton traitement et ajouter un buzz-word supplémentaire ;)

  • Julien Dubois

    Tu te trompes d’étape :-)
    L’étape 2 c’est de trouver la solution au Sudoku, et “à priori” personne n’a fait de brute force. L’étape 3 c’est de faire le brute force…

    • Régis Caspar

      L’étape 2 consistait a résoudre le probleme de knapsack, l’étape 3 le sudoku et l’étape 4 a faire le meilleur code pour trouver le mot de passe par “brute force” ou j’ai raté un truc ?

      • Julien Dubois

        Exactement! Mais comme ça embrouillait tout le monde (y compris moi), j’ai bien mis en début de ce billet “la dernière partie du jeu” :-)

  • Guillaume Carre

    Un peu tire par les cheveux l’argument sur nodejs et les machines modernes multi coeurs. Si tout se passe bien pour le site et que le trafic est au rendez vous il y aura toujours plus d’utilisateurs simultanes que de coeurs ;-).
    L’autre argument pour nodejs qui plait beaucoup aux startups etant “1 seul langage pour l’UI et pour le serveur”.

    • Julien Dubois

      Je ne sais pas si tu te rends compte de la différence, déjà, sur mon Mac qui a 8 coeurs. Sur un serveur, aujourd’hui, on a de plus en plus de coeurs (tu as vu les dernières bécanes de Sun/Oracle?), et cela va aller de plus en plus dans ce sens. Le problème aussi avec Node.js c’est qu’il bloque dès qu’il y a du CPU. Bref, non seulement il utilise mal la machine, mais en plus il ne tient pas la charge dans notre cas précis (j’ai bien précisé!). Pour l’argument “un seul langage”, on m’a déjà sorti pareil pour GWT, et franchement je n’étais pas fan non plus: l’UI et la programmation côté serveur ce sont deux monde différents, avoir un langage adapté à chacun ça ne me choque pas tant que ça.

      • Guillaume Carre

        Dans le cas d’un site comme Foursquare ou autre avec le meme traffic, ca a plus de sens que dans votre cas precis en effet:
        - des milliers d’utilisateurs simultanes, 
        - des applications qui tournent sur des machines virtuelles Amazon et pas sur les dernieres becanes de Sun/Oracle ou sur ton Macbook

        Tu ne peux pas dire des choses comme “l’histoire va plutôt dans le sens inverse de Node.js”. node.js est en train de cartonner chez les sites webs a fort traffic, mais c’est comme pour tout, ca ne s’utilise que si ca a du sens. Dans le cas de votre jeu ou dans les applis de gestion developpees par Ippon, je veux bien croire que ce serait un mauvais choix…

        Pour le second argument “un seul langage” je suis d’accord avec toi.

        • Julien Dubois

          Au risque de me re répéter: on a de plus en plus de coeurs sur nos machines, et cela va aller en s’accroissant. Et citer Amazon EC2 n’y change rien: sauf à prendre les instances micro (avec lesquelles on ne peut pas faire grand chose), plus on monte en gamme et plus on a de coeurs. Donc prendre une solution qui n’est capable de ne gérer qu’un seul coeur c’est très dommage…
          En plus, Node.js marche super mal sur ces bécanes virtualisées: ça bousille totalement le principe, ne serait-ce que parce que le cache processeur est alors mutualisé avec d’autres machines virtuelles. C’est pour ça que tous les tests faits au challenge USI (et on n’a pas été la seule équipe à tester) ont montré que Node.js ne tenait pas le coup.
          Après, dire que “ça cartonne” dans les startup, je ne suis pas sûr: si on regarde Netcraft par exemple, ça n’apparait même pas dans les stats…

          • Guillaume Carre

            Je te donne les infos en direct du front, j’habite a San Francisco et traine regulierement dans les meetups ici.
            Je n’ai pas de stats a te donner, c’est juste ce que je sens avec les meetups + les offres de job sur craigslist + google reader.

  • http://twitter.com/sebprunier Sébastien PRUNIER

    Version 4-bis avec fork/join de Java SE7 : https://github.com/sebprunier/IpponRecrute/tree/forkjoin

    Traces d’exécution sur ma machine 4 coeurs (HP ProBook / Windows 7 64 bits) : 
    Available processors : 4
    Number of passwords : 362880
    Solution : IDAEBHJGC
    Execution time : 18521 ms

    (Par contre j’ai pas réussi à faire fonctionner la méthode “shutdownNow()” du “ForkJoinPool” (java.util.concurrent.CancellationException), du coup j’ai utilisé un bon vieux booléen … si qqu’un a une meilleure solution, je suis preneur)

    Ca donne quoi sur le MacBook Pro 8 coeurs niveau perfs ? Histoire de comparer …

    • Julien Dubois

      C’est super! Par contre sur mon Mac ça ne donne rien du tout, il n’y a pas Java 7, et donc pas de Fork/Join :-)
      De toute manière cela va juste simplifier l’utilisation des threads, au final tu vas lancer autant de threads que moi: je ne m’attends pas à avoir de différence.

      • Régis Caspar

        Avec le code 4-bis j’ai 50000 ms sur un quad-core (Ubuntu Oneiric 64bits), donc ca varie pas mal quand même en fonction du type de CPU je suppose.

        • http://twitter.com/sebprunier Sébastien PRUNIER

          En effet, après plusieurs tests de mon côté, ca s’exécute parfois en 18 sec et parfois en 48 sec … Ca doit dépendre de comment est géré le pool de threads par Fork/Join (il suffit qu’il y ait un Set qui soit utilisé et tout s’explique, ce qui ne me semble pas déconnant pour un pool).

          Ce qu’on peut faire pour “tricher” un peu, c’est inverser les actions dans l’étape “fork” en remplacant invokeAll(pv1, pv2); par invokeAll(pv2, pv1);
          Et là miracle, ca s’exécute en 14 sec ! :-) (normal, le mot de passe commence par “I” et se trouve donc dans la deuxième branche de l’arbre)

  • http://twitter.com/sebprunier Sébastien PRUNIER

    Voilà ce que j’ai fait avec fork/Join + CDI pour lancer un événement quand le mot de passe est trouvé et catcher cet événement au niveau du pool de threads pour interrompre le traitement : https://github.com/sebprunier/IpponRecrute/tree/forkjoincdi

    Par contre ca ne fonctionne pas très bien, le “shutdownNow()” n’arrête pas les traitements :-( du coup le traitement va jusqu’au bout … Si qqu’un a une idée car je maîtrise pas trop fork/join encore :-)

    • http://twitter.com/sebprunier Sébastien PRUNIER

      J’ai corrigé le soucis. J’ai juste oublié quelques bricoles niveau CDI/Weld, à savoir : faire en sorte que le ForkJoinPool soit géré par Weld et soit déclaré en Singleton.
      Ca donne ca : https://github.com/sebprunier/IpponRecrute/blob/forkjoincdi/src/main/java/fr/ippon/rh/support/ForceBrute.java
      Par contre je retombe sur mon problème de “java.util.concurrent.CancellationException” lors de l’appel du shutdownNow().
      Etrange, je creuse.

  • Alexis Coudeyras

    Aucune implémentation proposée en Scala ? Dommage, ça aurait permis de comparer le volume de code et les perfs.
    Pour info, le post de Cédric Beust sur les parallels collections est complètement débile. 
    Il ne maitrise absolument pas son sujet, ni sur le parallélisme en général et encore moins le fonctionnement du framework parallel collections qu’il n’a absolument pas compris.
    “Lack of control” -> Il n’a qu’à lire la doc pour comprendre que tout ce qu’il relève (et beaucoup plus encore) sont gérés nativement par les parallel collection sans avoir à rien configurer (idem pour les équivalents en .net et en erlang de ce genre de framework). Plutôt l’impression que c’est un gros avantage qu’un inconvénient…
    “Silver bullet illusion” -> Il “démontre” que les parallels collections ne parallélisent pas certains traitements, non pas en regardant le nombre de threads créés, mais en constatant que les mêmes algorythmes produisent les mêmes résultats qu’ils soient exécutés en parallèle ou en séquentiels (hors side-effects, cf son println) . C’est pas une limitation… c’est une fonctionnalité ! Et ce genre de garanties sont loin d’être triviales à implémenter soi-même, ça implique d’utiliser des datas structures assez compliquées. Avec un framework comme les parallels collections (ou l’équivalent .net), c’est complètement transparent pour le développeur. Idem, un gros plus.
    “Unproven gains “-> I haven’t run any measurements, so I could be completely wrong. Une technique originale pour benchmarker, le doigt mouillé…