<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Plus loin que la mémoisation 
Step1:  Trou de mémoire
Step2:  Et si on poussait l'idée à l'extrême?
Step3:  Non, vraiment à l'extrême !
Step4:  Plus fort que la mémoisation 
Step5:  Compression
En un morceau
Compression de la LUT, en un bloc
Step6:  → Pas glop
Compression
par morceaux
```
tabulated = compress([xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx])
→
tabulateds = [ compress([xxxxxxxxxxxxxxxxxxxxxx]), ..., compress([xxxxxxxxxxxxxxxxxxxxxxxxx])]
```
En utilisant un algo qui décompresse vite, ça devrait passer!
Step7:  \o/
Et la sécurité dans tout ça ?
L'obfuscation, un moyen très utilisé pour « protéger » ses données ou ses algos (même en Python !)
Objectif 
Step8:  Attaque en boîte noire
Step9:  Ou alors...
Step10:  Tabulation $\simeq$ Boîte noire
L'attaquant a uniquement accès à la table des fonctions
Plus d'information sur la méchanique interne
On est sympa, on a fait l'explorationdes valeurs à sa place
→ Impossible de passer par un décorateur, ça suppose la connaissance du code de la fonction décorée
Step11:  Avec un petit mécanisme de cache...
Step12:  Exemple concluant
Une des briques de l'algo MD5
<ASSISTANT_TASK:>
Python Code:
class Namek: pass
class Quarkslab: pass
class SergeSansPaille(Quarkslab, Namek):
    '''
    /me likes docstrings
    '''
    def work(self, *args, **kwargs):
        raise RuntimeError("not a good idea")
    def run(self):
        while 1:
            pass  # that's very fast!
    def hack(self, project):
        return project.name in ('pythran', 'llvm') or project.lang in ('python', 'c++')
Explanation: Plus loin que la mémoisation : la tabulation
by serge-sans-paille
QuarksLab
PyConFR 2015, Pau
Qui suis-je ?
End of explanation
from functools import lru_cache
def fibo(n): # how no, not *you* again!
    return n if n < 2 else (fibo(n-1) + fibo(n-2))
@lru_cache(maxsize=20)
def memfibo(n): # how no, not *you* again!
    return n if n < 2 else (memfibo(n-1) + memfibo(n-2))
%timeit fibo(20)
%timeit memfibo(20), memfibo.cache_clear()
Explanation: Trou de mémoire
End of explanation
def P(v):
    c = 0
    while v:
        c += v&1
        v>>=1
    return c
Pm = lru_cache(maxsize=1<<16)(P)
l = list(range(1<<16))
%timeit [P(x) for x in l]
%timeit [Pm(x) for x in l]
Explanation: Et si on poussait l'idée à l'extrême?
End of explanation
def tabulate(P):
    
    import numpy as np
    
    class Tabulated(object):
        
        def __init__(self):
            self.tabulated = np.array([P(x) for x in range(1<<16)],
                                      dtype=np.uint8)
    
        def __call__(self, x):
            return int(self.tabulated[x])
        
    return Tabulated()
    
Pt = tabulate(P)
%timeit [P(x) for x in l]
%timeit [Pt(x) for x in l]
Explanation: Non, vraiment à l'extrême !
End of explanation
from numpy import uint16, uint8
def P(v:uint16) -> uint8:
    c = 0
    while v:
        c += v&1
        v>>=1
    return c
Explanation: Plus fort que la mémoisation : la tabulation
Précalculer tous les appels de la fonction, suivant le domaine d'entrée
Utiliser une Look Up Table pour remplacer l'appel de fonction
Problèmes
Définition du domaine d'entrée
Type de sortie
Taille de la LUT
Temps d'exécution
Annotations
On peut utiliser les annotations d'argument ppour calculer l'ensemble des valeurs possibles
End of explanation
def tabulate(P):
    import numpy, lz4
    
    class Tabulated(object):
        def __init__(self):
            self.tabulated = lz4.compress(
                numpy.array([P(x) for x in range(1<<16)],
                            dtype=numpy.uint8))
    
        def __call__(self, x):
            return int(lz4.decompress(self.tabulated)[x])
        
    return Tabulated()
Ptc = tabulate(P)
len(Pt.tabulated), len(Ptc.tabulated)
%timeit [P(x) for x in l]
%timeit [Pt(x) for x in l]
%timeit [Ptc(x) for x in l]
Explanation: Compression
En un morceau
Compression de la LUT, en un bloc
End of explanation
def tabulate(P):
    import numpy, lz4
    size = 1 << 16
    chunk_size = 1 << 10
        
    class Tabulated(object):
        def __init__(self):
            self.tabulateds = [lz4.compress(numpy.array([P(x) for x in range(i*chunk_size, (i+1) * chunk_size)],
                                                        dtype=numpy.uint8))
                               for i in range(0, size, chunk_size)]
        def __call__(self, x):
            chunk_id = x // chunk_size
            return int(lz4.decompress(self.tabulateds[chunk_id])[x - chunk_id * chunk_size])
        
    return Tabulated()
Ptcm = tabulate(P)
len(Ptc.tabulated), sum(map(len,Ptcm.tabulateds)), len(Pt.tabulated)
%timeit [P(x) for x in l]
%timeit [Ptc(x) for x in l]
%timeit [Ptcm(x) for x in l]
Explanation: → Pas glop
Compression
par morceaux
```
tabulated = compress([xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx])
→
tabulateds = [ compress([xxxxxxxxxxxxxxxxxxxxxx]), ..., compress([xxxxxxxxxxxxxxxxxxxxxxxxx])]
```
En utilisant un algo qui décompresse vite, ça devrait passer!
End of explanation
import inspect
print(inspect.getsource(P))
import dis
dis.dis(P)
Explanation: \o/
Et la sécurité dans tout ça ?
L'obfuscation, un moyen très utilisé pour « protéger » ses données ou ses algos (même en Python !)
Objectif : rendre une attaque en boîte blanche équivalente à une attaque en boîte noire
Attaque en boîte blanche
End of explanation
P(0), P(1), P(2), P(3), P(4), P(5), P(6) #...
Explanation: Attaque en boîte noire
End of explanation
Pt.tabulated[:7]
Explanation: Ou alors...
End of explanation
!cat P.py
!python3 tabulate.py P --compress < P.py > Ptc.py
import Ptc
print(inspect.getsource(type(Ptc.P)))
%timeit [P(x) for x in l]
%timeit [Ptc.P(x) for x in l]
Explanation: Tabulation $\simeq$ Boîte noire
L'attaquant a uniquement accès à la table des fonctions
Plus d'information sur la méchanique interne
On est sympa, on a fait l'explorationdes valeurs à sa place
→ Impossible de passer par un décorateur, ça suppose la connaissance du code de la fonction décorée
End of explanation
!python3 tabulate.py P --compress --cache-depth=2 < P.py > Ptcc.py
import Ptcc
l = list(range((1 << 16)))
%timeit [Ptcc.P(x) for x in l]
Explanation: Avec un petit mécanisme de cache...
End of explanation
!cat F.py
!python3 tabulate.py --compress --cache-depth=2 < F.py > Ftcc.py
import F, Ftcc
import itertools
l = range((1 << 4) )
%timeit [F.F(*args) for args in itertools.product(l,l,l)]
%timeit [Ftcc.F(*args) for args in itertools.product(l,l,l)]
Explanation: Exemple concluant
Une des briques de l'algo MD5
End of explanation
<END_TASK>