Solveur pour le problème bigbadbob du CTF de qualification DEFCON 21
par Benoit

Voici un programme pour résoudre le problème bigbadbob rencontré durant le CTF de qualification DEFCON 21. Ce programme n’inclut pas la logique de communication au serveur, mais peut interpréter la description d’une instance du problème tel que soumis par le serveur du CTF et le résoudre rapidement. La reconversion de cette solution dans la forme requise par le serveur serait simple, mais n’est pas implantée ici, faute d’intérêt (considérant que le serveur est maintenant fermé, le concours étant terminé). Le code est disponible dans ce dépôt Git.

Le problème

Le problème à résoudre implique de concevoir un circuit qui procure des flux de données synchronisés entre une entrée de signal (la source, dénotée feed) et des sorties (les antennes, dénotées antenna). Formellement, on se fait donner un espace cartésien discret de dimensions fixes finies. Cet espace comporte une seule source de signal et de multiples antennes; de plus, certaines positions de cette espace sont considérées vides (null) et, par conséquent, impassables. Pour résoudre le problème, on doit produire un ensemble de chemins joignant la source à chaque antenne qui satisfait les conditions suivantes:

  • Tous les chemins doivent avoir la même longueur.
  • Aucun chemin ne peut passer à travers un espace vide.
  • Aucun chemin ne peut passer à travers la source ou une antenne, à moins qu’il ne s’agisse d’un bout du chemin.
  • Bien qu’un chemin puisse se diviser en de multiples autres chemins, aucun chemin ne peut en croiser un autre.

Le programme

Les modules et fichiers décrits ci-bas sont disponibles dans ce dépôt Git.

Le solveur

Le code de résolution du problème se trouve dans le module bob.py. Il a été écrit pour un usage dans une session Python interactive, soit avec Python 2.7.5 version standard, ou bien avec ipython. La seule dépendance exotique est envers la librarie de représentation graphique matplotlib (cette librarie fait partie de la distribution standard de ipython).

Le problème à résoudre est décrit en instantiant la classe Field:

import bob
problem = bob.Field(
    dims = (5,5),
    feed = (0,0),
    antenna = [(3, 2), (3, 4)],
    null = [(0, 1), (0, 4), (1, 0)]
    )

Le problème peut être tracé graphiquement en utilisant la méthode plot(). L’instance de Field est la seule chose nécessaire pour lancer la résolution du problème en utilisant la fonction solve(f), qui retourne une solution sous la forme d’une instance de la classe Solution (ou None si aucune solution n’appartient au sous-espace exploré):

sol = solve(problem)

La solution peut être représentée graphiquement à l’aide de sa méthode plot(). De plus, ses éléments peuvent être accédés via ses trois variables membres:

sol.field
La description du problème, comportant les dimensions et les éléments du champ.
sol.mp
Le point de rencontre utilisé pour diviser le problème.
sol.paths
L’ensemble de chemins composant la solution, représenté par une liste. Chaque chemin peut être examiné comme une séquence (itérable) de points (instances de la classe Point, qui comporte les coordonnées du point dans ses variables membres x et y).

Si on désire mieux comprendre ou examiner le fonctionnement de l’algorithme de résolution, on peut tracer son progrès graphiquement. Pour cela, il suffit de décommenter la ligne commençant avec Solution(... dans la fonction find_paths(...) avant d’importer le module bob (il est aussi possible de le recharger avec la fonction standard reload(mod)). Chaque solution intermédiaire est alors dessinée durant l’itération dans l’espace de recherche.

Description des problèmes

La description de plusieurs instances du problème qui furent soumises durant le CTF ont pu être récupérées et sauvegardées dans le fichier bigbadbob.problems, avec des solutions partielles et des fragments de sortie du programme développé durant le concours (le code présenté ici est une ré-écriture complète). Le module problems.py procure des fonctions pour lire des fichiers comportant des descriptions d’instances du problème (et les convertir en instances de la classe Field) tout en ignorant le contenu impertinent du fichier. Spécifiquement, on peut interpréter un ensemble de problèmes dans un tel fichier en utilisant la fonction read(path):

import problems
probs = problems.read("bigbadbob.problems")

Cette fonction renvoit une liste de tuples contenant le numéro de la ligne du fichier où un problème est spécifié, ainsi que l’instance de Field qui correspond à ce problème. The code qui suit résout les 81 problèmes de la liste probs (obtenue selon l’exemple ci-haut), en chronométrant leur résolution respective au fur et à mesure:

import time
for line, field in fl:
    print "Line", line, "--",
    tic = time.time()
    s = bob.solve(field)
    toc = time.time()
    print (toc - tic), "seconds."

Sur mon merveilleux Mac Book Pro (mouture 2011, processeur Core i7, 16 GB RAM), j’obtiens le rapport suivant:

Line 1 -- 0.00201797485352 seconds.
Line 25 -- 0.00435590744019 seconds.
Line 72 -- 0.00191283226013 seconds.
Line 112 -- 0.00427985191345 seconds.
Line 152 -- 0.0300841331482 seconds.
Line 215 -- 0.0891540050507 seconds.
Line 254 -- 0.00213599205017 seconds.
Line 286 -- 0.000988960266113 seconds.
Line 316 -- 0.00552320480347 seconds.
Line 335 -- 0.00222611427307 seconds.
Line 350 -- 0.00196099281311 seconds.
Line 389 -- 0.00529193878174 seconds.
Line 429 -- 0.00128507614136 seconds.
Line 482 -- 0.00532793998718 seconds.
Line 514 -- 0.00736713409424 seconds.
Line 552 -- 0.00709819793701 seconds.
Line 585 -- 0.00453686714172 seconds.
Line 687 -- 0.00931906700134 seconds.
Line 746 -- 0.00684118270874 seconds.
Line 795 -- 0.0105209350586 seconds.
Line 865 -- 0.120131015778 seconds.
Line 922 -- 0.00175499916077 seconds.
Line 969 -- 0.0025680065155 seconds.
Line 1068 -- 0.10357093811 seconds.
Line 1287 -- 0.00157785415649 seconds.
Line 1341 -- 0.029305934906 seconds.
Line 1390 -- 0.00171804428101 seconds.
Line 1469 -- 0.00422310829163 seconds.
Line 1517 -- 1.13104486465 seconds.
Line 1723 -- 0.00351500511169 seconds.
Line 1814 -- 0.00124716758728 seconds.
Line 1903 -- 0.00115013122559 seconds.
Line 1944 -- 0.00260901451111 seconds.
Line 2001 -- 0.00591111183167 seconds.
Line 2067 -- 0.00674605369568 seconds.
Line 2304 -- 0.0019268989563 seconds.
Line 3520 -- 0.00119781494141 seconds.
Line 3550 -- 0.00581097602844 seconds.
Line 3595 -- 0.0223410129547 seconds.
Line 3632 -- 0.00242686271667 seconds.
Line 3668 -- 0.412544965744 seconds.
Line 3708 -- 0.00178909301758 seconds.
Line 3726 -- 0.00240612030029 seconds.
Line 3790 -- 0.00422406196594 seconds.
Line 3864 -- 0.00137495994568 seconds.
Line 3933 -- 0.0375428199768 seconds.
Line 4028 -- 0.00156593322754 seconds.
Line 4198 -- 0.00511693954468 seconds.
Line 4266 -- 0.00256705284119 seconds.
Line 4301 -- 0.00408005714417 seconds.
Line 4442 -- 0.014219045639 seconds.
Line 4505 -- 0.00499796867371 seconds.
Line 4659 -- 6.25013494492 seconds.
Line 4785 -- 0.0907549858093 seconds.
Line 4907 -- 0.00161218643188 seconds.
Line 14859 -- 0.00140786170959 seconds.
Line 14928 -- 0.0089910030365 seconds.
Line 14978 -- 0.00449800491333 seconds.
Line 15037 -- 0.000937938690186 seconds.
Line 15132 -- 0.109791040421 seconds.
Line 15243 -- 0.00144600868225 seconds.
Line 15276 -- 0.00358510017395 seconds.
Line 15307 -- 0.00105404853821 seconds.
Line 15344 -- 0.010626077652 seconds.
Line 15411 -- 0.00157403945923 seconds.
Line 15447 -- 0.0497591495514 seconds.
Line 15608 -- 0.16591501236 seconds.
Line 15701 -- 0.00216817855835 seconds.
Line 15744 -- 0.00711011886597 seconds.
Line 15852 -- 0.00163316726685 seconds.
Line 15886 -- 0.00125908851624 seconds.
Line 15953 -- 0.00755286216736 seconds.
Line 16013 -- 0.00373291969299 seconds.
Line 16119 -- 0.00527405738831 seconds.
Line 16176 -- 0.00239896774292 seconds.
Line 16280 -- 0.246478796005 seconds.
Line 16368 -- 0.00137114524841 seconds.
Line 16399 -- 0.00662016868591 seconds.
Line 16434 -- 0.000920057296753 seconds.
Line 16464 -- 0.00330901145935 seconds.
Line 16512 -- 0.0281488895416 seconds.

En résumé, mon programme résout presque tous les problèmes en moins de 100 ms. Dans le pire cas considéré, la solution nécessite moins de 10 secondes de calcul. C’est une fierté un peu tardive – il m’aurait fallu produire ce programme il y a un mois – mais on prend la fierté qui passe.