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:

/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! = 987654321 = 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.
  • Il est écrit en Scala, et donc personne ne le comprend

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:

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](http://www.jcp.org/en/jsr/detail?id=237), 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):

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.