Timing attaque (side-channel)

**manticore** · 10/08/2012, 12h48

Bonjour,

je voudrai réaliser un PoC d'une timing-attack sur un strcmp en c. Cette attaque est relativement simple et répandu :

- La fonction strcmp compare caractère par caractère les deux strings. Dès qu'un caractère est différent elle retourne l'index.

- En calculant la différence de temps d'exécution on arrive à trouver quel est le caractère utilisé. Cela se fait beaucoup plus rapidement qu'un attaque par bruteforce.

J'ai essayé de le faire en python. Le code binaire que j'appelle prend un seul argument le mot de passe.

Code binaire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <string.h>
 
int main(int argc, char* argv[])
{
	char* password = "hello";
 
	if (strcmp(password, argv[1]) == 0)
	{
		printf("Hello\n");
	}
	else
	{
		printf("GO OUT\n");
	}
 
	return 0;
}

Et le code python que j'utilise :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import os
import timeit
 
password = ""
path = "./constanteTime/constanteTime"  # path du binaire.
nTest = 1000                            # nombre de repetition timer.
 
def findNextChar(_prev, _pos):
    bestVal = 0                 # Plus grand temps.
    newChar = ''                # Caractere correspondant au meilleur temps.
    for i in range(97, 123):    # Parcourt de toutes les minuscules
        global arg              # utilisation de arg en global pour le passer au timer.
        arg = "%s %s%c%s" % (path, _prev[0:_pos], chr(i), _prev[_pos+1:len(_prev)]) # Un vilain string replace manuel.
        tempVal = sendConnect() # Recupere le temps d'execution.
 
        print "%c   %f" % (chr(i), tempVal)
 
        # Update du temps.
        if tempVal > bestVal:
            bestVal = tempVal
            newChar = chr(i)
 
    return "%s%c%s" % (_prev[0:_pos], newChar, _prev[_pos+1:len(_prev)])
 
 
def sendConnect():
    global arg 
    # Get time delta.
    timer = timeit.Timer(getTime)
    return timer.timeit(nTest)
 
def getTime():
    global arg
    os.popen(arg)
 
# Lancement avec chaine de base.
print findNextChar("aaaaa", 0)

Je suis censé récupérer des différences de temps d'exécution très courte (quelques ms/ns), mais avec cette méthode je trouve des temps important (jusqu'à 2 secondes avec 1000 itérations).

Comment faire pour calculer un temps plus précis pour l'exécution de os.popen() ?

Merci de votre aide.

**dividee** · 11/08/2012, 16h38

Bon, je peux me tromper, mais même en optimisant le code, je vois mal comment ça pourrait fonctionner.

A chaque cycle de mesure:

Le processus Python doit effectuer un appel système.
L'OS doit créer et initialiser un nouveau processus, charger ton binaire depuis le cache disque, et l'insérer dans la file d'attente de l'ordonnanceur
Lorsque l'ordonnanceur décide de l'exécuter, le processus doit encore:
- initialiser le runtime C
- exécuter le code du main, qui contient essentiellement un strcmp et un printf. printf est certainement un ordre de magnitude ou deux plus lent que strcmp (sur de courtes chaînes).
L'exécution se termine, le système doit encore supprimer le processus, sauver la valeur de retour, rendre la main au processus Python, etc.

En supposant que tout se passe au mieux, j'ai du mal à imaginer que le temps total soit en-deçà de quelques microsecondes, et il y a plusieurs étapes dont le temps d'exécution n'est pas constant. Comparé à cela, les différences de temps d'exécution de strcmp doivent compter pour une poignée de nanosecondes. Totalement noyées dans le "bruit", à mon avis.

**tyrtamos** · 11/08/2012, 19h27

Bonjour,

Je suis assez d'accord avec dividee: les différences de temps dans la comparaison sont très petits par rapport à la "machinerie" système.

Mais comme c'est un problème amusant, j'ai creusé un peu le principe en m'écartant cependant un peu du problème posé.

Partons du principe qu'il y a une fonction qui dit si oui ou non le mot proposé est correct (ici, le mot est "machin"). En principe, on n'a pas accès à cette fonction: on peut seulement l'appeler, recevoir sa réponse et mesurer son temps d'exécution!)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
def estegal(mot):
    ref = "machin" # mot de référence à trouver
    if len(mot)!=len(ref):
        return False
    for c1, c2 in zip(list(mot), list(ref)):
        if c1!=c2:
            return False
    return True

On va chercher par essais systématiques:

1- le nombre de caractères du mot à trouver (ici=6), parce qu'un mot de bonne longueur demandera plus longtemps puisqu'il atteindra le "for...".

2- chacun des caractères du mot en tablant sur le fait qu'un "bon" caractère demandera plus longtemps puisque la boucle de test ira plus loin.

Pour cela, il faut une mesure du temps d'exécution. En principe, c'est timeit qu'il faudrait utiliser, en particulier parce qu'il désactive le garbage collection, mais il est pénible à utiliser, et je n'ai pas trouvé les résultats très stables. Alors, j'ai simplifié un peu: j'ai utilisé time.clock() sous Windows (peut-être faut-il utiliser time.time() sous Linux?), mais j'ai en plus neutralisé le garbage collection pendant la mesure du temps.

Cela donnera comme importation:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
from time import clock
import gc

Voilà comment on va trouver le nombre de caractères. Pour assurer une certaine stabilité des temps, on va à chaque fois tester nrep=1000000 (1 million) de fois et calculer le cumul des temps:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
###############################################
nrep = 1000000
t0 = 0
nbc = 1
for i in xrange(1, 30):
    mot = 'a'*i
    gcactif = gc.isenabled()
    gc.disable()
 
    t = 0
    for k in xrange(0, nrep):
        tps = clock()
        estegal(mot)
        t += clock()-tps
 
    if gcactif:
        gc.enable()
 
    print i, mot, t
    if i>1 and (t-t0)/t0*100 >5.0: # arrêt si le temps a augmenté de plus de 5%
        nbc = i
        break
    else:
        t0 = t
 
print "nb de caracteres:", nbc

Ce qui donne (temps en secondes):

1 a 0.495194393491
2 aa 0.495511597782
3 aaa 0.495503513692
4 aaaa 0.495894629662
5 aaaaa 0.495218260804
6 aaaaaa 3.37778684565
nb de caracteres: 6

On a bien trouvé les 6 caractères de "machin"! Et assez facilement. Ici, on arrête quand le temps d'exécution est > 5% du précédent, mais c'est un peu arbitraire. On pourrait aussi calculer l'écart-type des valeurs successives et s'arrêter quand on a un temps > moyenne+3*ecart-type.

Voilà comment on peut trouver le mot inconnu:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
nrep = 1000000
nbc = 6
mot = ""
alpha = "abcdefghijklmnopqrstuvwxyz"
for i in xrange(0, nbc): 
    T = []
    for car in alpha: # essayer tous les car. de alpha à la position i 
        mottest = mot + car + 'a'*(nbc-len(mot)-1)
 
        gcactif = gc.isenabled()
        gc.disable()
 
        t = 0
        for k in xrange(0, nrep):
            tps = clock()
            estegal(mottest)
            t += clock()-tps
 
        if gcactif:
            gc.enable()
 
        T.append(t)
        print mottest, t
 
    tmax = 0
    kmax = -1
    for k, t in enumerate(T):
        if t>tmax:
            tmax = t
            kmax = k
    car = alpha[kmax]
    mot += car
    print u"trouvé:", mot

Ce qui donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
aaaaaa 3.53353261257
baaaaa 3.52070008219
caaaaa 3.52979891789
daaaaa 3.53971694137
eaaaaa 3.52442800252
faaaaa 3.53114087682
gaaaaa 3.53152044409
haaaaa 3.52146229638
iaaaaa 3.53319308079
jaaaaa 3.52857860526
kaaaaa 3.52185995662
laaaaa 3.53059808792
maaaaa 3.75775485575
naaaaa 3.52460816224
oaaaaa 3.52773939974
paaaaa 3.52951251013
qaaaaa 3.52141456175
raaaaa 3.53486879714
saaaaa 3.5300564539
taaaaa 3.51713307374
uaaaaa 3.52716542935
vaaaaa 3.54170562749
waaaaa 3.5228381315
xaaaaa 3.53611836648
yaaaaa 3.53535114784
zaaaaa 3.51802116877
trouvé: m
maaaaa 3.62543678145
mbaaaa 3.53451848658
mcaaaa 3.53750959986
mdaaaa 3.5300422105
meaaaa 3.54958184082
mfaaaa 3.53269186721
mgaaaa 3.53184496256
mhaaaa 3.53183456873
miaaaa 3.53435949946
mjaaaa 3.53208132596
mkaaaa 3.53333628467
mlaaaa 3.53255713239
mmaaaa 3.53312763817
mnaaaa 3.53088026116
moaaaa 3.53349873637
mpaaaa 3.54030515515
mqaaaa 3.53290590312
mraaaa 3.53075438032
msaaaa 3.5349207663
mtaaaa 3.52787605937
muaaaa 3.53327392169
mvaaaa 3.53159859028
mwaaaa 3.52864712755
mxaaaa 3.5332870102
myaaaa 3.5634191081
mzaaaa 3.58994724168
trouvé: ma
maaaaa 3.66428776277
mabaaa 3.63281601574
macaaa 3.73308144335
madaaa 3.63722569432
maeaaa 3.6595551056
mafaaa 3.64160611617
magaaa 3.65279719132
mahaaa 3.62835821757
maiaaa 3.65512425438
majaaa 3.63159185355
makaaa 3.65403521194
malaaa 3.62993115051
mamaaa 3.65600118564
manaaa 3.63813765662
maoaaa 3.65075268652
mapaaa 3.62787779166
maqaaa 3.65420767256
maraaa 3.63825044895
masaaa 3.65970523867
mataaa 3.63576478379
mauaaa 3.66000742965
mavaaa 3.64458991527
mawaaa 3.66306591038
maxaaa 3.64128429239
mayaaa 3.66068610827
mazaaa 3.63812418317
trouvé: mac
macaaa 3.7362034419
macbaa 3.71340553838
maccaa 3.73481759789
macdaa 3.72428556856
maceaa 3.73899822725
macfaa 3.72046487367
macgaa 3.73920802865
machaa 3.80358779608
maciaa 3.7359974901
macjaa 3.71288700174
mackaa 3.73625079157
maclaa 3.71440950536
macmaa 3.73139571812
macnaa 3.71941817649
macoaa 3.76665004938
macpaa 3.74132221064
macqaa 3.74448655441
macraa 3.72048489141
macsaa 3.75744034616
mactaa 3.71257210719
macuaa 3.7620290296
macvaa 3.71606058448
macwaa 3.76316850131
macxaa 3.77608071769
macyaa 3.79290332394
maczaa 3.74265416069
trouvé: mach
machaa 3.78860066327
machba 3.80239904993
machca 3.81659471182
machda 3.80354853047
machea 3.8033371893
machfa 3.79894829839
machga 3.85111493075
machha 3.82643728383
machia 3.89929995633
machja 3.79992839802
machka 3.79234359692
machla 3.79851214249
machma 3.79107554964
machna 3.81001657238
machoa 3.80105901581
machpa 3.80953537654
machqa 3.79844439015
machra 3.80196558871
machsa 3.79746082586
machta 3.79913654223
machua 3.80075143543
machva 3.79781729572
machwa 3.7985371647
machxa 3.79912114392
machya 3.79687838659
machza 3.7977433842
trouvé: machi
machia 3.88610672157
machib 3.88893653795
machic 3.89550813317
machid 3.90610291047
machie 3.89083591415
machif 3.88598161063
machig 3.89018880196
machih 3.89256128991
machii 3.88638658504
machij 3.90004253769
machik 3.89924606237
machil 3.89134983128
machim 3.90351600169
machin 3.91758732259
machio 3.91358723796
machip 3.91624382388
machiq 3.93041754327
machir 3.93792342824
machis 3.91235152702
machit 3.90464700431
machiu 3.91142108676
machiv 3.8980461524
machiw 3.89809966147
machix 3.89447529449
machiy 3.89614331167
machiz 3.90613832648
trouvé: machir

Vous voyez qu'on a trouvé "machir" et pas "machin", mais on n'est pas tombé loin!

Après, pourquoi le temps d'essai de "machir"=3.93792342824s est plus grand que l'essai de "machin"=3.91758732259s? Je ne sais pas, mais on constate que les essais sont de moins en moins discriminant au fur et à mesure qu'on trouve plus de caractères, ce qui est logique (le faible écart de temps se compare à un temps total de plus en plus long)! Et ça devrait être pire pour un programme Python qui appelle une fonction en C qui donnera un temps de comparaison minuscule.

En résumé: le principe est bon, mais la "machinerie" système de Python noie assez vite les différences de temps dans le bruit de fond.

En tout cas, je me suis bien amusé

**manticore** · 12/08/2012, 23h30

Je partais du principe que je pouvais me fier à l'appel os.popen(cmd), et que je pouvais récupérer le temps d'exécution du binaire. Ce qui me fournirait une mesure relativement fiable. Après les appels systèmes pythons, et autres routines devrait s'exécuter dans un temps moyen stable.

J'ai fait quelques tests sur 6 caractères en mettant le mot de passe dans le premier cas et une chaine complétement fausse dans le second (donc arrêt au premier caractère sur le deuxième test et toute la chaine sur le premier). Et la je vois une différence sur 1000 exécutions.

Je me demande si en travaillant pas un peu la méthode j'arrive à distribuer le bruit par exemple en remplaçant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
test("aaaaa", 1000) # test 1000 fois de la solution aaaaa

Par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
for i in range(1000):
    test("aaaaa",1)
    test("baaaa",1)

Avec cette solution je devrai avoir moins d'impact des autres processus (dû à une meilleurs distribution du bruit).

En enlevant les valeurs extrêmes, on pourrait encore affiner la mesure... je vais faire quelques tests lorsque j'aurai un peu de temps

et je reviendrai poster les résultats.

Très intéressant tes tests.

Pour le dernier caractère la différence du temps d'exécution n'est plus visible car tu tests de toute façon celui-ci. C'est pour cela que l'on test "aaa", puis "baa" car c'est le temps du tests du caractère suivant qui nous intéresse.

Pour trouver la solution complète, il te faut bruteforcer le dernier caractère de manière standard.

**tyrtamos** · 13/08/2012, 06h01

Bonjour,

Envoyé par manticore

Pour trouver la solution complète, il te faut bruteforcer le dernier caractère de manière standard.

Et oui, c'est bien vu, et j'aurais dû y penser: je comprends maintenant pourquoi dans mes essais, je n'arrivais jamais à trouver le dernier caractère! Et l'essai des 26 lettres (pour cet exemple) est facile à faire.

Avec ce dernier point, j'aurais donc finalement réussi à trouver le mot caché, par analyse des temps d'exécution dans ce cas simplifié.

Je reste intéressé par la suite de tes travaux! Afin de neutraliser la machinerie système de Python, peut-être faudrait-il faire tout simplement la boucle de comptage des temps en C, appelable en Python?

Merci!

**Bktero** · 13/08/2012, 09h43

@manticore : je passe par là et je me permet 2 petites remarques sur le code C :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main(int argc, char* argv[])
{
	const char* password = "hello";

	if ( argc > 1 && strcmp(password, argv[1]) == 0)
	{
		printf("Hello\n");
	}
	else
	{
		printf("GO OUT\n");
	}

	return 0;
}

La première pour respecter les types ; la seconde pour éviter un crash du programme si pas d'argument.

@tyrtamos : joli code !

**tyrtamos** · 13/08/2012, 10h17

Bonjour,

Envoyé par Bktero

@tyrtamos : joli code !

Merci!

@manticore: je n'ai pas pu résister: je viens d'essayer mon code en Cython pour me rapprocher de ma proposition précédente: faire la boucle de comptage des temps en C. Mais c'est beaucoup moins douloureux en Cython pour moi qui n'ai pas codé en C depuis très longtemps...

J'ai donc placé la fonction estegal en Cython, ainsi que la boucle des temps appelés ici tempsexec, et j'ai appelé ce fichier test01bib.pyx:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from time import clock
 
####################################################
def estegal(char *mot):
 
    cdef char *ref
    ref = "machin" # mot de référence à trouver
    if len(mot)!=len(ref):
        return False
    for i in xrange(0, len(mot)):
        if mot[i]!=ref[i]:
            return False
    return True    
 
####################################################
def tempsexec(char *mot, long nrep):
 
    cdef float t, tps
    t = 0
    for k in xrange(0, nrep):
        tps = clock()
        estegal(mot)
        t += clock()-tps
    return t

Le setup.py:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext
 
ext_modules = [Extension("test01bib", ["test01bib.pyx"])]
 
setup(
  name = 'bibliotheque',
  cmdclass = {'build_ext': build_ext},
  ext_modules = ext_modules
)

Et la compilation par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
python setup.py build_ext --inplace
pause

Il faut, bien entendu, avoir en dispo: cython et un compilateur C (j'utilise Visual Studio sous Windows 7)

On a ensuite le code Python d'appel qui se distinguera du précédent par:

- l'importation de test01bib.pyd qu'on vient de compiler:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

from test01bib import tempsexec, estegal

- le calcul du temps pour chacun des mots essayés:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

t = tempsexec(mot, 1000000)

- et, bien sûr, le calcul par bruteforce pour le dernier caractère à trouver.

Voilà ce que ça donne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
1 a 0.221920147538
2 aa 0.231556817889
3 aaa 0.229974657297
4 aaaa 0.232136800885
5 aaaaa 0.229839041829
6 aaaaaa 0.499046057463
nb de caracteres: 6
 
aaaaaa 0.499537497759
baaaaa 0.500251531601
caaaaa 0.499537438154
daaaaa 0.499188274145
eaaaaa 0.501381516457
faaaaa 0.499670147896
gaaaaa 0.499998509884
haaaaa 0.499508976936
iaaaaa 0.499826908112
jaaaaa 0.500127375126
kaaaaa 0.501209974289
laaaaa 0.499835133553
maaaaa 0.547224760056
naaaaa 0.500816464424
oaaaaa 0.500645935535
paaaaa 0.500765562057
qaaaaa 0.499796271324
raaaaa 0.498915225267
saaaaa 0.499899566174
taaaaa 0.501038551331
uaaaaa 0.49939545989
vaaaaa 0.499789178371
waaaaa 0.501508891582
xaaaaa 0.499635607004
yaaaaa 0.501338481903
zaaaaa 0.499383330345
trouvé: m
maaaaa 0.546270549297
mbaaaa 0.533521711826
mcaaaa 0.53567481041
mdaaaa 0.534054636955
meaaaa 0.534450769424
mfaaaa 0.538763999939
mgaaaa 0.536012351513
mhaaaa 0.536052286625
miaaaa 0.534889280796
mjaaaa 0.534777164459
mkaaaa 0.535886526108
mlaaaa 0.535616755486
mmaaaa 0.533975601196
mnaaaa 0.53526365757
moaaaa 0.537335395813
mpaaaa 0.535381674767
mqaaaa 0.535434961319
mraaaa 0.538470089436
msaaaa 0.53471916914
mtaaaa 0.535782754421
muaaaa 0.537365078926
mvaaaa 0.535662829876
mwaaaa 0.538740158081
mxaaaa 0.535456180573
myaaaa 0.537270605564
mzaaaa 0.534474611282
trouvé: ma
maaaaa 0.544574677944
mabaaa 0.546063423157
macaaa 0.567969441414
madaaa 0.544914424419
maeaaa 0.545920610428
mafaaa 0.546736657619
magaaa 0.54584646225
mahaaa 0.546464145184
maiaaa 0.545074462891
majaaa 0.546313226223
makaaa 0.546055138111
malaaa 0.545982420444
mamaaa 0.546511948109
manaaa 0.545819163322
maoaaa 0.545042395592
mapaaa 0.546055316925
maqaaa 0.545487523079
maraaa 0.546147763729
masaaa 0.545496761799
mataaa 0.546200037003
mauaaa 0.545724511147
mavaaa 0.546180188656
mawaaa 0.548753261566
maxaaa 0.544449269772
mayaaa 0.54485720396
mazaaa 0.545593857765
trouvé: mac
macaaa 0.566424250603
macbaa 0.567747592926
maccaa 0.567854225636
macdaa 0.567887604237
maceaa 0.568170130253
macfaa 0.565382957458
macgaa 0.567666053772
machaa 0.592935144901
maciaa 0.568876326084
macjaa 0.566256165504
mackaa 0.567029178143
maclaa 0.567127645016
macmaa 0.567187666893
macnaa 0.568488061428
macoaa 0.566083490849
macpaa 0.56672167778
macqaa 0.567192971706
macraa 0.567043364048
macsaa 0.568328917027
mactaa 0.56847679615
macuaa 0.567109405994
macvaa 0.56794577837
macwaa 0.566846549511
macxaa 0.56706982851
macyaa 0.569503724575
maczaa 0.566954135895
trouvé: mach
machaa 0.592271625996
machba 0.593430995941
machca 0.590678215027
machda 0.593964934349
machea 0.592410802841
machfa 0.592570841312
machga 0.592744529247
machha 0.592476725578
machia 0.617188215256
machja 0.592975735664
machka 0.591249883175
machla 0.594406783581
machma 0.592617809772
machna 0.59311491251
machoa 0.591411173344
machpa 0.593977272511
machqa 0.589469015598
machra 0.591496646404
machsa 0.593277037144
machta 0.592966079712
machua 0.589692175388
machva 0.593700885773
machwa 0.593548893929
machxa 0.591104447842
machya 0.594294786453
machza 0.59226167202
trouvé: machi
trouvé: machin

En ayant la fonction de test du mot "estegal" en C, on se rapproche du problème posé au début.

On note que le cumul des temps pour 1 million d'essais est 7 fois plus rapide environ. La dispersion des temps d'un essai à l'autre est plus réduit, mais comme le temps de réponse de la fonction estegal est aussi réduit, on n'est pas plus discriminant.

Cependant: ça marche!!!

Ok?

**fred1599** · 13/08/2012, 10h24

je viens d'essayer mon code en Cython

C'est ce que j'allais te proposer, cython en effet est la solution, mais pour un débutant c'est peut-être déroutant.

Mais tu peux améliorer Tyrtamos

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for i in xrange(0, len(mot)):

au lieu on pourrait mettre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for i from 0 <= i < len(mot):

puis tes fonctions commençant par def

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

def estegal(char *mot):

mettre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

cpdef int estegal(char *mot):

au lieu de return True et False, pour mettre le type qu'il faut mettre 1 et 0

J'édite en disant que len serait plus performant en utilisant la fonction strlen de la libc

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
cdef extern from "string.h":
    size_t strlen(char *)
 
for i from 0 <= i < int(strlen(mot)):

J'allais oublié, on peut aussi utiliser Pypy...

**fred1599** · 13/08/2012, 13h38

La fonction estegal pourrait être

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
cdef extern from "string.h":
    int strcmp(char *, char *)
 
cpdef estegal(char *mot):
    return True if strcmp("machin", mot)==0 else False

**tyrtamos** · 13/08/2012, 15h01

Bonjour fred1599,

Je suis un super débutant en Cython (ce que je fais là vient tout de suite après le <print "hello">), et tes conseils sont les bienvenus!

Envoyé par fred1599

for i from 0 <= i < len(mot):

Ça ne marche pas sous Python (syntax error), mais c'est accepté sous Cython. Ça ne semble pas être plus rapide.

Envoyé par fred1599

mettre
cpdef int estegal(char *mot):

Ok!
J'avais essayé cdef, mais ça ne marchait pas (erreur d'importation). Avec cpdef, on peut appeler à partir de Python, ET à partir du Cython compilé, ce qui était l'objectif. J'ai en plus l'impression que c'est plus rapide.

Envoyé par fred1599

au lieu de return True et False, pour mettre le type qu'il faut mettre 1 et 0

Ok!
J'avais constaté que même en laissant True et False, la fonction compilée me renvoyait 1 ou 0, mais j'ai corrigé: renvoyer 1 ou 0, c'est plus logique puisqu'on simule une fonction écrite en C.

Envoyé par fred1599

len serait plus performant en utilisant la fonction strlen de la libc

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
cdef extern from "string.h":
    size_t strlen(char *)

Bien vu! "size_t" n'est pas reconnu, mais avec "Py_ssize_t", ça marche: strlen donne bien la longueur de la chaine passée en argument, et c'est beaucoup plus rapide.

Et la dernière proposition de fred1599 est impressionnante de simplicité (sans pour autant être plus rapide, ce qui indique que Cython fait bien son boulot quand il traduit du "pur Python"):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
cdef extern from "string.h":
    int strcmp(char *, char *)
 
cpdef int estegal(char *mot):
    return 1 if strcmp("machin", mot)==0 else 0

Avec toutes ces modifs, je gagne du temps d'exécution: du 3.5s hier (solution pur Python), j'en étais à 0.5s ce matin, et j'en suis maintenant à 0.1s pour 1 million de tests: c'est 35 fois plus rapide!!!

Mais, car il y a un mais, et un gros: je ne détecte plus rien: ni le nombre de caractères, ni les caractères eux-mêmes. En fait, je m'aperçois que c'était le 'len' de la ligne "for i in xrange(0, len(mot))" qui permettait de trouver les écarts de temps. Et ce n'est pas strlen en soit qui amène une différence, car si je calcule lg = len(mot) au début de la fonction, et que je l'utilise dans "for i in xrange(0, lg)", c'est le même (manque de) résultat!

Bref, j'arrive au terme de mon petit essai. Je n'ai pas tout essayé (on pourrait isoler le calcul dans un processus, etc...), mais j'en fais les conclusions suivantes:

1- si la fonction de test est écrite en C, la fonction qui contient la boucle de mesure des temps d'exécution doit, elle aussi, être écrite en C en pinaillant le code "à la nanoseconde près".

2- Il faudrait aussi une mesure du temps plus précise: avec 0.1 s pour 1 million de tests, si on veut pouvoir discriminer sur 0.001s, il faut un temps avec une précision de 0.001/1000000 = 10**-9 soit la nanoseconde: je doute que ce soit le cas avec time.clock.

3- Et ce serait encore mieux en assembleur!! (bon courage

)

Avec un grand merci à fred1599 pour le coup de pouce en Cython que je découvre à cette occasion!

**fred1599** · 13/08/2012, 15h22

Ok, j'utilise très très peu cython, les tests chez moi étaient tous fonctionnels, je suis surpris que ça ne fonctionne pas chez toi.

Exemple:

Bien vu! "size_t" n'est pas reconnu, mais avec "Py_ssize_t", ça marche: strlen donne bien la longueur de la chaine passée en argument, et c'est beaucoup plus rapide.

Pourtant ça fonctionnait chez moi avec size_t

1- si la fonction de test est écrite en C, la fonction qui contient la boucle de mesure des temps d'exécution doit, elle aussi, être écrite en C en pinaillant le code "à la nanoseconde près".

C'est pas une obligation, j'avais fais sans, mais tant qu'à faire autant se mettre à cython à 100%

Tous mes tests étaient vérifiés par le biais de l'interpréteur python 2.7

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
from test import fonction
print fonction(...)

Mon temps était de 0.2s, mais nettement meilleur que tes 1er essais.

J'adore cython, mais je ne le maîtrise pas assez encore, heureusement que j'ai fais du C

**dividee** · 13/08/2012, 20h08

Envoyé par tyrtamos

Mais, car il y a un mais, et un gros: je ne détecte plus rien: ni le nombre de caractères, ni les caractères eux-mêmes. En fait, je m'aperçois que c'était le 'len' de la ligne "for i in xrange(0, len(mot))" qui permettait de trouver les écarts de temps. Et ce n'est pas strlen en soit qui amène une différence, car si je calcule lg = len(mot) au début de la fonction, et que je l'utilise dans "for i in xrange(0, lg)", c'est le même (manque de) résultat!

Je ne vois pas trop comment ce len() pourrait avoir une influence; son temps d'exécution devrait être constant. Peut-être permet-il à Cython de mieux optimiser la génération de code ?

Fondamentalement, cette optimisation est "contre-productive" vu qu'elle réduit le temps d'exécution (variable) qui nous intéresse. Mais c'est un peu plus réaliste par rapport au PO...

**tyrtamos** · 14/08/2012, 18h41

Bonjour,

Le problème que j'ai rencontré avec len() était dû au fait que je mesurais l'écart de temps à l'intérieur de la boucle pour exclure du temps la machinerie de la boucle. Or, la plus grande rapidité de chaque comparaison fait qu'elle dépasse ce que time.clock() est capable de mesurer (on peut espérer mesurer la micro-seconde, mais en dessous, on obtient du bruit ).

Alors, j'ai mesuré le temps à l'extérieur de la boucle.

J'ai aussi rencontré pas mal de problèmes avec Cython. Des résultats très anormaux alors que le code respectait parfaitement la notice, montrent une certaine instabilité ("instable" est le nouveau mot pour dire "buggué").

Bref, voilà la suite et fin de ma quête: mon dernier code et ses résultats.

Le fichier test01bib.pyx à compiler par Cython:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from time import clock
from cpython cimport bool
 
cdef extern from "string.h": 
    int strcmp(char *S1, char *S2)
 
####################################################
cpdef bool estegal(char *mot):
    cdef char *ref = "machin"
    cdef bool ok = strcmp(mot, ref)==0
    return ok
 
####################################################
cpdef double tempsexec(char *mot, long nrep):
    cdef bool ok
    cdef long i = 0
    cdef double t = clock()
    while i<nrep:
        ok = estegal(mot)
        i += 1
    t = clock()-t
    return t

le fichier setup.py:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext
 
ext_modules = [Extension("test01bib", ["test01bib.pyx"])]
 
setup(
  name = 'bibliotheque',
  cmdclass = {'build_ext': build_ext},
  ext_modules = ext_modules
)

Le script pour lancer la compilation:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
python setup.py build_ext --inplace
pause

Ceci fait, voilà le code Python qui utilisera les fonctions compilées avec Cython:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#!/usr/bin/python
# -*- coding: utf-8 -*-
from __future__ import division
# Python 2.7
 
from time import clock
 
# importation du module compilé en C par Cython
from test01bib import tempsexec, estegal
 
# liste des caractères possibles dans les mots
alpha = "abcdefghijklmnopqrstuvwxyz"
 
####################################################
# nombre de répétitions 
 
nrep = 10000000 # =10 millions
 
####################################################
# trouver le mot
 
mot = ""
for i in xrange(0, 5): 
    T = []
    for car in alpha: # essayer tous les car. de alpha à la position i 
        mottest = mot + car
        t = tempsexec(mottest, nrep)        
        T.append(t)
        print mottest, t
 
    # chercher le temps maxi et le caractère correspondant
    tmax = 0
    kmax = -1
    for k, t in enumerate(T):
        if t>tmax:
            tmax = t
            kmax = k
    car = alpha[kmax]
    mot += car
    print u"trouvé:", mot
 
####################################################
# forcebrute sur le dernier caractère
 
ok = False
for car in alpha:
    mottest = mot+car
    if estegal(mottest):
        ok = True
        break
mot = mottest
print u"Force brute pour le dernier caractère"
 
####################################################
# résultat final
 
if ok:
    print u"trouvé:", mot
else:
    print u"mot non trouvé"

Et voilà le résultat qui montre que ça marche. La différence principale par rapport à mes codes précédents est que la 1ère étape conduisant à calculer le nombre de caractères ne marche plus, parce qu'il n'y a plus dans la fonction de comparaison le 1er test sur la longueur du mot.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
a 0.108905753289
b 0.108451507749
c 0.108405313287
d 0.108566223995
e 0.108488848272
f 0.108466520949
g 0.108448043164
h 0.108945018582
i 0.108417246856
j 0.10846960058
k 0.108496162395
l 0.108417246856
m 0.112223670504
n 0.108453817472
o 0.108453047564
p 0.108466135995
q 0.108491542949
r 0.108394919533
s 0.108439189226
t 0.108838001412
u 0.108446118395
v 0.10840261861
w 0.108435724641
x 0.10844765821
y 0.108377211656
z 0.108379521379
trouvé: m
ma 0.119575134137
mb 0.112191719335
mc 0.112125892227
md 0.112107414442
me 0.112149374412
mf 0.112321448782
mg 0.112200188319
mh 0.112108954257
mi 0.112163617704
mj 0.113435505217
mk 0.112315674474
ml 0.112301046228
mm 0.11231028512
mn 0.112215971427
mo 0.112945458969
mp 0.112225980227
mq 0.112303740905
mr 0.11224330315
ms 0.112147834596
mt 0.112308360351
mu 0.112231754535
mv 0.112290652474
mw 0.112240608473
mx 0.11253240349
my 0.112177476042
mz 0.112256006627
trouvé: ma
maa 0.119713717522
mab 0.119571669553
mac 0.123320735077
mad 0.119521625552
mae 0.119414223429
maf 0.119605545491
mag 0.119567050106
mah 0.119486594752
mai 0.119465807244
maj 0.11944040029
mak 0.119625563091
mal 0.119449639183
mam 0.119531634352
man 0.119560120937
mao 0.119824199277
map 0.119616324199
maq 0.119584757983
mar 0.119485824844
mas 0.119473891275
mat 0.11961247466
mau 0.119671757553
mav 0.119505072537
maw 0.119510846845
max 0.119434625983
may 0.119590917245
maz 0.11961940383
trouvé: mac
maca 0.12385928551
macb 0.123384637416
macc 0.123300717477
macd 0.123882767695
mace 0.123319195262
macf 0.123133262553
macg 0.123228346154
mach 0.13111836022
maci 0.123320735077
macj 0.123379633016
mack 0.123156744738
macl 0.123418513354
macm 0.12336000037
macn 0.123433911508
maco 0.1232329656
macp 0.123929347111
macq 0.12311093523
macr 0.123079369014
macs 0.1233981108
mact 0.123309956369
macu 0.123335748277
macv 0.12338001797
macw 0.123329589016
macx 0.1233080316
macy 0.123238739907
macz 0.123385792277
trouvé: mach
macha 0.130622924618
machb 0.130623694525
machc 0.130652566064
machd 0.130688366772
mache 0.130512057909
machf 0.130615610494
machg 0.130592513264
machh 0.130632933418
machi 0.134331569988
machj 0.130645251941
machk 0.130708384372
machl 0.130674123479
machm 0.130559407233
machn 0.130556327602
macho 0.13149253536
machp 0.130649101479
machq 0.130387717817
machr 0.131795878992
machs 0.130714928587
macht 0.130683362372
machu 0.130513982679
machv 0.130590588494
machw 0.130649101479
machx 0.13072416748
machy 0.130597902617
machz 0.130653720925
trouvé: machi
Force brute pour le dernier caractère
trouvé: machin

Ouf...

Il reste tout de même pas mal de bruit, malgré les 10 millions de test. Je pense que ce sont, au moins en partie, les limites de time.clock() utilisé ici sous Windows. Il faut avoir conscience en effet des temps en cause: 0.1 secondes comme temps cumulé pour 10 millions d'essais, ce n'est vraiment pas beaucoup et le bruit apparait déjà au niveau du 3e chiffre...

**manticore** · 15/08/2012, 13h50

Oui mon code en C est très vilain

, mais c'est vraiment un code de test.

Je suis avec intérêt vos réactions et commentaires mais j'ai pas le temps de faire des tests de mon côté, je pense aussi que la voie du cylon(Cython) ou de l'appel d'un code c externe est une bonne solution.

A tout bientôt

Les vacances m'appelles...

**Bktero** · 16/08/2012, 08h36

Bonnes vacances alors ^^

**tyrtamos** · 16/08/2012, 09h17

+1

Et merci pour avoir posé une question si intéressante!

Timing attaque (side-channel)

Python

Discussions similaires

Partager

Partager