Une histoire des piles et de leur protection

Magazine
Marque
GNU/Linux Magazine
Numéro
270
Mois de parution
juillet 2024
Spécialité(s)


Résumé

Lorsque l’on parle de programmation sécurisée, on pense d’abord à un dépassement d’indice d’un tableau ou à des droits d’accès non respectés, puisque ces aspects sont visibles par le programmeur. Par contre, la pile est sous le contrôle absolu du compilateur et le contrat implicite est que « ça fonctionne » tant que nous le laissons faire son travail, qui est de plus en plus alambiqué. L’article précédent [1] détaillait de façon lovecraftienne les soucis de flexibilité et de sécurité inhérents au modèle de programmation à une seule pile, utilisé par (quasiment) tous les compilateurs actuels. J’ai amalgamé tous ces problèmes dans le terme « Single Stack Syndrome », mais il n’y a pas que le C ou le x86 dans la vie ! Nous pouvons trouver des inspirations dans d’autres langages, d’autres architectures et d’autres ères.


Mais quand nous parlons de piles, de quoi s’agit-il vraiment, pourquoi et depuis quand ? Un petit (re)tour dans l’histoire de cette structure indispensable, que tout informaticien doit absolument connaître, s’impose, car elle a connu une longue et sinueuse évolution.

1. Au commencement

Je n’ai pas trouvé de trace des piles comme structure ou circuit avant l’avènement de l’ère informatique. Je doute que le boulier entre dans cette catégorie. La récursion est cependant connue par les mathématiciens, en particulier en tant que concept sous-jacent aux preuves inductives.

Le problème des Tours de Hanoï fut publié en 1889 et sa résolution emploie habituellement un algorithme récursif sur trois piles, mais il a fallu attendre encore pour que cette structure dernier arrivé premier sorti soit mécanisée. En tout cas, les piles sont entrées dans la culture informatique dès la fin de la Deuxième Guerre mondiale, car elles sont essentielles au fonctionnement…

La suite est réservée aux abonnés. Il vous reste 98% à découvrir.
  • Accédez à tous les contenus de Connect en illimité
  • Découvrez des listes de lecture et des contenus Premium
  • Consultez les nouveaux articles en avant-première
Envie de lire la suite ? Rejoignez Connect
Je m'abonne maintenant


Article rédigé par

Par le(s) même(s) auteur(s)

Erreurs en rafales, multiparités et codes Gray entrelacés

Magazine
Marque
GNU/Linux Magazine
Numéro
277
Mois de parution
septembre 2025
Spécialité(s)
Résumé

Le bit de parité est semblable à ce brave petit soldat qui sonne l’alerte, avec ses moyens réduits et quand il le peut, pour que la cavalerie vienne s’occuper du problème. Mais cet humble bit obéit aux lois de l’information et laisse passer une erreur sur deux. Grâce aux codes Gray, configurés de façon inhabituelle, nous pourrons mieux filtrer les erreurs, sans augmenter considérablement la taille du circuit ni déployer des théories (trop) complexes.

Visualisez les données grâce à l’alphabet Braille !

Magazine
Marque
GNU/Linux Magazine
Numéro
275
Mois de parution
mai 2025
Spécialité(s)
Résumé

Quand on travaille avec de grandes quantités de bits, on n’a pas forcément envie de faire une interface graphique, et les afficher dans le terminal graphique n’est pas facile. Un bit occupe toute la place d’un caractère et la représentation hexadécimale n’est pas très parlante. Heureusement, Unicode est là !

aStrA : vers de vraies chaînes de caractères en C !

Magazine
Marque
GNU/Linux Magazine
Numéro
275
Mois de parution
mai 2025
Spécialité(s)
Résumé

Qu’est-ce qui caractérise un langage de haut niveau ? On peut dire que celui-ci doit au moins gérer les chaînes de caractères facilement et sans aucun risque. BASIC le faisait il y a soixante ans. N’importe quel langage courant le fait actuellement. Pourtant, le précédent article a démont(r)é [1] que le C n’en fait pas partie, surtout à cause des fonctions printf(3) et assimilées : elles procurent une illusion d’aisance qui s’effondre vite et c’est un vrai nid à failles. Nous avons suggéré quelques solutions que nous allons mettre en œuvre ici, grâce notamment au format des chaînes alignées [2] étendu avec des attributs, d’où le nom aStrA. Cela demande un peu de bricolage pour les réaliser en C, mais c’est un premier pas en avant, une base qui ne demande qu’à évoluer.

Quelques réalisations basées sur l'algorithme PEAC

Magazine
Marque
GNU/Linux Magazine
Numéro
275
Mois de parution
mai 2025
Spécialité(s)
Résumé

L’exploration des algorithmes PEAC et de leurs applications se poursuit ! Le précédent article [1] avait abouti sur une fonction de checksum ultrarapide pour calculer l’empreinte d’un fichier. Cette fois-ci, nous irons plus loin en décortiquant d’autres réalisations pratiques, certaines complémentant les LFSR et d’autres les supplantant. Un petit tour du côté de POSIX nous rappellera qu’il est temps de tourner la page. Nous en profiterons même pour tâter un peu de VHDL : l’algorithme PEAC peut aussi sortir du monde logiciel ! On commence ici à s’approcher d’un « cookbook ».

Les listes de lecture

Python niveau débutant

9 article(s) - ajoutée le 01/07/2020
Vous désirez apprendre le langage Python, mais ne savez pas trop par où commencer ? Cette liste de lecture vous permettra de faire vos premiers pas en découvrant l'écosystème de Python et en écrivant de petits scripts.

Au pays des algorithmes

11 article(s) - ajoutée le 01/07/2020
La base de tout programme effectuant une tâche un tant soit peu complexe est un algorithme, une méthode permettant de manipuler des données pour obtenir un résultat attendu. Dans cette liste, vous pourrez découvrir quelques spécimens d'algorithmes.

Analyse de données en Python

10 article(s) - ajoutée le 01/07/2020
À quoi bon se targuer de posséder des pétaoctets de données si l'on est incapable d'analyser ces dernières ? Cette liste vous aidera à "faire parler" vos données.
Plus de listes de lecture