Blog Haypo

En dehors des raccourcis claviers que j'avais déjà abordé, il existe énormément d'astuces pour améliorer la ligne de commande sous Linux. En voici quelques unes pour gagner encore plus de temps avec la ligne de commande.

Complétion avancée

La touche TAB sert à compléter automatiquement les commandes. C'est diablement efficace, mais bash peut faire mieux ! En chargeant /etc/bash_completion, la complétion dépendra du programme utilisé. « kpdf <tab><tab> » n'affichera que les fichiers PDF (et les répertoires). « apt-get install python-<tab><tab> » affiche les paquets Debian installables dont le nom débute par « python- ». Pour l'activer la complétion avancée, ajoutez dans votre ~/.bashrc :

source /etc/bash_completion

Le chargement de bash sera plus long, mais vous serez beaucoup efficace avec votre ligne de commande !

Ignorer les doublons dans l'historique

Par défaut, bash conserve toutes les commandes tapées. J'ai présenté dans mon billet précédent la variable d'environnement HISTIGNORE pour ignorer certains commandes. Pour ne pas sauver un commande saisie plusieurs fois, utilisez :

export HISTCONTROL=ignoredups

Rappel : CTRL+r permet de rechercher une commande déjà tapée en en saisissant quelques lettres.

Utiliser most plutôt que less pour lire du texte

Pour lire un fichier texte, il existe le programme more qui n'est pas très pratique. Le programme less est mieux : il permet de revenir en arrière, rechercher du texte, etc. Il existe encore mieux ! most utilise des couleurs (meilleur rendu des pages de manuel), permet de découper l'écran en plusieurs vues indépendentes, etc. Lisez l'aide intégrée pour les détails. Installez-le avec « apt-get install most » et choisissez-le par défaut en ajoutant dans votre fichier de configuration ~/.bashrc :

export PAGER=most

Activer les couleurs

Plusieurs programmes permettent d'afficher des couleurs mais ne le font pas par défaut pour des raisons de compatibilité avec les anciens terminaux. Activez les couleurs avec :

alias ls='ls --color=auto'
alias grep='grep --color'
alias egrep='egrep --color'

Tailles de fichier avec des unités humaines

L'option « -h » permet d'afficher les tailles avec des unités plus facilement compréhensibles par un humain (19 Ko, 367 Mo, 1 Go, ...) :

alias du='du -h'
alias df='df -h'

La commande ls supporte également l'option.

Passer en mode verbeux

Par défaut, les programmes sont silencieux : ils ne disent pas ce qu'ils font. Or c'est pratique pour vérifier qu'on a bien fait ce qu'on voulait. Aliases pour activer le mode verbeux :

alias ln='ln -v'
alias cp='cp -v'
alias mv='mv -v'
alias rm='rm -v'

Personnaliser l'invite

L'invite est le court texte invitant à saisir une commande, du style « haypo@marge:~$ ». C'est la variable d'environnement PS1 qui contient l'expression pour générer cette invite. « \u » est remplacé par le nom d'utilisateur, « \h » le nom de la machine, « \w » le répertoire de travail, etc.

Je n'aime pas du tout avoir une invite qui contient le répertoire de travail car l'invite prend rapidement toute la largeur de l'écran. J'utilise donc une invite qui ne contient que le nom de la machine :

export PS1='\h$ '

C'est rudimentaire mais efficace. La commande « pwd » me sert à me rappeler où je suis quand je me perd ;-)

Voilà, j'espère que je vous ai appris des trucs, n'hésitez pas à m'en apprendre d'autres en déposant un commentaire !

L’erreur est humaine, mais pour provoquer une vraie catastrophe, il faut un ordinateur.

Quand on passe trop de temps dans la ligne de commande, on a tendance à oublier qu'on manipule des documents importants et qu'au détour d'une commande on peut les éradiquer à tout jamais ! Voici quelques astuces pour limiter la casse : lignes à ajouter dans votre configuration « ~/.bashrc ».

Option -i pour demander confirmation

Alias qui rajoutent l'option -i sur les opérations dangereuses :

alias ln="ln -i -v"
alias cp='cp -i -v'
alias mv='mv -i -v'
alias rm='rm -i'

Vous pouvez également utiliser l'option -k de tar pour éviter d'écraser les fichiers existant :

alias tar='tar -k'

Option -C de bash

Bash possède une option -C pour interdire les redirections vers un fichier existant :

set -C

Exemple au pif : ça arrive qu'on tape « echo "user:password:" >/etc/passwd » alors qu'on voulait écrire « >>/etc/passwd » :-)

Configurer l'historique

Bash permet de ne pas mettre une commande dans l'historique (touche haut ou CTRL + r) avec la variable HISTIGNORE :

# Ignore commands like:
#  >konsole&<
#  any command starting with a space (eg. " sudo touch /tmp/x")
#  >bg<
#  >fg<
#  >exit<
#  >svn revert*<
#  >hg revert*<
#  >*rm *<   (eg. "svn rm file", "rm -rf dir", ...)
#  >tee *<
export HISTIGNORE='*&: *:[bf]g:exit:*>|*:history*:svn revert*:hg revert*:*rm *:tee *'

Du coup, si vous tapez une commande que vous savez délicate, précédez la d'une espace pour éviter qu'elle soit sauvée (merci acatout pour l'astuce !).

Exigences vis à vis d'un générateur de nombres pseudo-aléatoires

Les générateurs de nombres pseudo-aléatoires sont utilisés principalement à deux fins :

• Simulation : simulation physique, jeux vidéos, etc.
• Sécurité : générer un secret pour garantir la confidentialité

Dans les deux domaines, la qualité du générateur est importante. Si un générateur est biaisé, c'est-à-dire que la distribution n'est pas équitable entre les différentes valeurs possibles, le résultat de la simulation sera invalide (ou bien simplement imprécis) et la confidentialité peut être comprise. Par contre, la simulation privilégie la vitesse du générateur. Alors que pour la sécurité on se donne les moyens pour qu'il soit difficile de deviner les nombres précédemment générés et les prochains nombres générés (quitte à ce que le générateur soit plus lent), ce qui revient à deviner quel est l'état interne du générateur étant donné qu'un algorithme est déterministe.

Générateur biaisé

Reprenons l'exemple de RANDU, un générateur biaisé (les bits de poids faible sont peu aléatoires). Si on utilise 1 + rand() % 6 pour simuler un lancé de dé, on va obtenir une suite du genre :

  1, 3, 1, 5, 3, 3, 1, 5, ...

Les faces 2, 4 et 6 ne sont jamais tirées !

Inverser un générateur congruentiel linéraire

Il est possible de deviner l'état interne d'un générateur congruentiel linéraire (LCG) en ne connaissant qu'un seul nombre généré. L'algorithme RANDU est :

  x(n+1) = (x(n) * 65539) % 2147483648

Avec x(0) : graine du générateur. On peut exécuter le générateur à l'envers en calculant :

  y(n+1) = (y(n) / 65539) % 2147483648

Sachant que diviser revient à multiplier par l'inverse, x / 65539 <=> x * (1 / 65539), on va calculer l'inverse 65539 modulo 2147483648 avec le théorème des restes chinois. En pratique, on utilise l'identité de Bezout. Fonction Python qui calcule les coefficients u et v tels quel a · u + b · v = 1 :

def bezout(a, b):
  u0 = 1; u1 = 0
  v0 = 0; v1 = 1
  while 1:
    q = a // b
    r = a % b

    u0, u1 = u1, u0 - q*u1
    v0, v1 = v1, v0 - q*v1

    if r != 0:
      a = b
      b = r
    else:
      break

  return (u0, v0)

On calcule alors bezout(65539, 2147483648) = (477211307, -14564), ce qui donne :

  65539 · 477211307 - 2147483648 · 14564 = 1

et

  (477211307 * 65539) % 2147483648 = 1

Finalement, y(n+1) = (y(n) * 477211307) % 2147483648.

Exemple :

 x(0) = 42
 x(1) = 2752638
 x(2) = 16515450
 x(3) = 74318958

On utilisant x(3), on va pouvoir générer les nombres précédents :

 y(0) = 74318958
 y(1) = 16515450
 y(2) = 2752638
 y(3) = 42

On a donc réussi à retrouver les nombres précédents jusqu'à la graine (42). Même si le générateur ne délivre que quelques bits de son état interne (ex: rand() = x(n) & 0xffff), on peut retrouver l'état interne en utilisant une recherche exhaustive (si on dispose de quelques nombres successifs).

Solutions

Pour rééquilibrer la distribution d'un générateur, on peut l'améliorer en utilisant différrentes techniques :

• Utiliser la parité du flux
• Utiliser le mapping de transition (technique de Von Neumann)
• Utiliser la transformée de Fourier discrète (ou une transformation de Fourrier rapide, FFT)
• Utiliser la compression (en zappant les entêtes et autres parties « fixes »)

Lire la RFC 1750 pour les sources et les détails sur ces techniques.

Pour empêcher qu'un pirate arrive à deviner l'état interne du générateur, on peut rajouter une fonction de hachage sur la sortie du générateur (ex: MD5, SHA-1, ...). Il est toujours possible d'inverser la fonction de hachage, mais c'est beaucoup plus difficile !

Suite au bug OpenSSL de Debian, je me suis à nouveau intéressé de près aux générateurs de nombres pseudo-aléatoires (PRNG). J'ai commencé à écrire la bibliothèque Hasard qui contient plusieurs algorithmes pour générer des nombres et des fonctions de haut niveau : int(min, max), bool(), bytes(size), etc.

Outils ENT et Dieharder

J'ai utilisé le programme ENT pour tester la qualité des algorithmes. ENT utilise :

• Test d'entropie,
• Test du χ²,
• Estimation de PI par la méthode de Monte-Carlo avec calcul de l'erreur en pourcentage
• Calcul de la moyenne arithmétique : (x1+x2+...+xn) / n. La valeur parfaite est 255 / 2 = 127,5.
• Coefficient de corrélation en série (?)

ENT n'accepte en entrée que des fichiers contenant des octets (pseudo-)aléatoires. On ne peut donc pas tester la qualité d'un générateur de nombre flottants par exemple. Exemple de sortie (algorithme RANDU avec l'opérateur pow2(8)) :

Entropy = 6.000000 bits per byte.

Optimum compression would reduce the size
of this 262144 byte file by 25 percent.

Chi square distribution for 262144 samples is 786432.00, and randomly
would exceed this value 0.01 percent of the times.

Arithmetic mean value of data bytes is 126.0000 (127.5 = random).
Monte Carlo value for Pi is 2.999862669 (error 4.51 percent).
Serial correlation coefficient is 0.322338 (totally uncorrelated = 0.0).

Il existe également le programme Dieharder qui accepte en entrée des nombres de 32 bits non signés dans un fichier binaire ou un fichier texte. Il utilise des tests bien plus rigoureux, mais comme je ne sais pas les interpréter, je ne vais pas commenter.

Représentation visuelle

C'est pas très rigolo tout ça, alors voyons un peu des dessins et schémas qui permettent de distinguer le bon chasseur du mauvais chasseur. Image générée à partir des 8 bits de poids faible de l'algorithme RANDU :

Chaque pixel utilise une valeur du générateur comme couleur. On voit clairement que l'algorithme n'est pas du tout aléatoire ! Pour reproduire l'image :

$ cd tests
$ ./gen_files.py --rng=randu --op=pow2 --bits=8 randu.dat
$ ./draw_pil.py --width=300 --height=300 randu.dat

Une autre façon de représenter des nombres est d'utiliser un axe 2D avec x=random() et y=random() :

On voit qu'il existe très peu de combinaisons (x, y) : j'en dénombre 16. Pour reproduire cette image :

$ ./gnuplot.py randu.dat --point=2

La page web graphics présente d'autres images.

Script de tests de la bibliothèque Hasard

Le script gen_files.py génère un fichier au format texte plat qui contient les nombres générés par l'algorithme RANDU pour l'opérateur pow2(8) (génère un nombre dans l'intervalle [0; 255]). Lire file_format.rst pour voir le format de ce fichier. Le script file_info.py calcule l'entropie des nombres générés, la valeur maximale et la valeur minimale.

$ ./file_info.py randu.dat
Engine: randu
Seed: linux_urandom
Range: 0..255
Operation: pow2
Count: 262144
Minimum: 1
Maximum: 251
Entropy: quality=75.00%, value=6.0000/8.0000

On voit que seul 6 bits sur 8 sont réellement aléatoires (2 bits sont invariants) et que l'intervalle annoncé est incorrect : 0..255 versus 1..251.

J'aime bien l'algorithme RANDU car il est vraiment mauvais et il permet donc de tester l'outillage de test :-)

Pour la suite

Ma bibliothèque est encore en chantier. J'ai beaucoup travaillé sur l'outillage pour tester la sortie des algorithmes en comparant avec d'autres bibliothèques comme Python, PHP ou la libc. La version 0.2 n'inclut par encore ce travail, ça sera le cas pour la prochaine version 0.3 qui n'est pas encore publiée. En attendant, vous pouvez utiliser le dépôt Mercurial.

Je ne sais pas trop ce qu'Hasard va donner au final, mais en tout cas ça avance :-)