Aller au contenu

Où est le bug ?

0100011

Par 0100011
dans Science et technologie

Messages recommandés

0100011

0100011

Posté
Posté

Je vous propose de partir à la recherche d'un bug vieux de 50 ans, qui trainait il y a peu dans la librairie standard de Java, encore mieux un bug qui était présent dans un algo certifié d'un point de vue formel. Je vous donne le texte du programme, trouvez moi le bug ! (et c'est comme dans kikadit on ne triche pas !!). Pour le coup je vous donne la version qu'il y a sur wikipedia (qui est fausse bien entendu :icon_up: ) .

Il s'agit juste de chercher dans une liste triée avec la célèbre méthode dite "des jeux de 20h" (à savoir une dichotomie pour deviner un chiffre compris entre 0 et 1000). C'est on ne peut plus con comme programme hein ? 

BinarySearch(A[0..N-1], value, low, high) 
{
  if (high < low) then 
  return -1 
  endif // not found

  mid = (low + high) / 2

  if (A[mid] > value) then 
  return BinarySearch(A, value, low, mid-1)
  else 
  if (A[mid] < value) then 
	 return BinarySearch(A, value, mid+1, high)
  else 
	 return mid 
  endif
  endif // found
}

Où est la faute ? Comment la corriger ? Et non ce n'est pas une blague il y a bien une erreur dans le code ci dessus…

0100011

0100011

Posté
  • Auteur
Posté
Un indice trollifique : si cet algorithme était transposé en Scheme/Lisp, le bug n'existerait pas :icon_up:

Indice : justement il existerait aussi !

POE

POE

Posté
Posté
Indice : justement il existerait aussi !

Donc le bug est dans l'algorithme ?

Herbert West

Herbert West

Posté
Posté

Non non, je confirme que c'est bien un bug d'implémentation (qui peut d'ailleurs sans doute être détecté par un analyseur statique digne de ce nom).

edit : bon, bien sûr, vu que Kassad a posté du pseudo-code et pas un exemple dans un vrai langage, ça va être dur :icon_up:

vaginus

vaginus

Posté
Posté

Si ça peut être détecté par un "analyseur statique digne de ce nom", et que c'est un "bug d'implémentation", il ne s'agit donc pas d'un problème d'algorithmie. Or il me semble qu'en l'occurence c'est présenté ainsi.

0100011

0100011

Posté
  • Auteur
Posté
Non non, je confirme que c'est bien un bug d'implémentation (qui peut d'ailleurs sans doute être détecté par un analyseur statique digne de ce nom).

edit : bon, bien sûr, vu que Kassad a posté du pseudo-code et pas un exemple dans un vrai langage, ça va être dur :icon_up:

Ca m'étonnerait qu'un analyseur statique sur le marché le trouve, c'est un résultat dans un papier de recherche de 2006…

Edit : pour être plus précis un analyseur statique ne peut pas trouver automatiquement tous les bugs de ce type (c'est indécidable) même si bien sûr on peut repérer une grande famille de ce type de bug automatiquement.

Le fait que ce soit du pseudo code ne change rien à l'affaire. C'est un peu plus subtil que ça (et d'ailleurs a des résonances étonnantes avec quelques discussions d'ici)…

Juste pour rappel :

http://fr.wikipedia.org/wiki/Chiffre

http://fr.wikipedia.org/wiki/Nombre

Il s'agit de trouver un nombre entre 0 et 1000

Cela a-t-il à voir avec le fait que nous cherchons un entier et que la somme de deux entiers peut être impaire et que donc

(low + high)/2 puisse être un non entier?

Techniquement t il s'agit de trouver un élément dans une liste ordonnée rangée dans un tableau, mais si ta liste est numméroter de 0 à 1000 c'est le même problème.

La division est bien sur la division entière et 7/2 donne 3 et pas une erreur.

0100011

0100011

Posté
  • Auteur
Posté
Donc le bug est dans l'algorithme ?

La réponse n'est pas immédiate : elle donne un indice fort. L'algorithme est formellement correct, le programme est faux.

john_ross

john_ross

Posté
Posté

Cela a-t-il à voir avec le fait que low + high peut excéder la plage des long int?

donc remplacer mid=(low+high)/2 par mid=low/2 + high/2 +(modulo(low/2)+modulo(high/2))/2

Exemple 7 et 21

mid=(low+high)/2=14

et avec la nouvelle formule cela donne 3+10+(1+1)/2=14 sans le risque de dépacement de plage.

Herbert West

Herbert West

Posté
Posté
La réponse n'est pas immédiate : elle donne un indice fort. L'algorithme est formellement correct, le programme est faux.

Je suis prêt à parier que je n'ai pas le bug là-dedans, et pourtant je n'ai fait que retranscrire ton pseudo-code dans un vrai langage :

(define (binary-search A value low high)
 (let* ((mid (truncate (/ (+ low high) 2)))
	 (midval (vector-ref A mid)))
(cond ((< high low) -1)
	  ((> midval value) (binary-search A value low (- mid 1)))
	  ((< midval value) (binary-search A value (+ mid 1) high))
	  (else mid))))

john_ross

john_ross

Posté
Posté

En même temps si j'ai raison j'appelle pas ça un bug mais juste l'utilisation d'un code qui ne fonctionne pour les besoins de l'utilisateur.

Comme pour tous ce qu'on utilise il faut s'assurer que bien que fonctionnant pour les besoins des autres cela fonctionne pour SES besoins.

0100011

0100011

Posté
  • Auteur
Posté
Cela a-t-il à voir avec le fait que low + high peut excéder la plage des long int?

donc remplacer mid=(low+high)/2 par mid=low/2 + high/2 +(modulo(low/2)+modulo(high/2))/2

Exemple exemple 7 et 21

mid=(low+high)/2=14

et avec la nouvelle formule cela donne 3+10+(1+1)/2=14

Gagné :icon_up:

Effectivement on peut faire mid := low + (high-low)/2

Ce n'est pas calculable dans le cas général où mid := f(low,high) avec un f aussi compliqué qu'on veut.

Ce qu'il y a de beau est que la théorie est parfaitement correcte, mais l'implantation forcément incorrecte car il y a toujours une limite sur les int même si on a des int de taille "arbitraire" en réalité ce n'est jamais le cas (ne serait ce que la limite de la mémoire physique de la machine).

Une leçon a retenir pour les "axiomatiques" non ? Avec une théorie parfaite on débouche sur une implantation forcément incorrecte (d'ailleurs ça a été découvert sur un plantage). Je trouve cet exemple merveilleux (mes étudiants vont l'entendre ces prochaines années :doigt:). Il a fallu plus d'un demi siècle pour le trouver (d'ailleurs il traine dans la majeure partie des bouquins d'algos).

En même temps si j'ai raison j'appelle pas ça un bug mais juste l'utilisation d'un code qui ne fonctionne pour les besoins de l'utilisateur.

Comme pour tous ce qu'on utilise il faut s'assurer que bien que fonctionnant pour les besoins des autres cela fonctionne pour SES besoins.

Oui bien sûr après coup on peut dire que la spec n'est pas vérifiée… Mais avant on ne se pose même pas la question.

john_ross

john_ross

Posté
Posté

il est vrai qu'avec mon exemple j'aurais du m'apercevoir que mid=low + (high-low)/2

et je comprends mieux pourquoi vous appelez ça un bug.

Car vu ma formule la ressource en temps machine était trop importante pour l'utiliser dans tous les cas.

Il est clair que la formule mid= low + (high-low)*0.5 si vous parlez d'implémentation est la plus efficace, bien plus que mid= low +(high-low)/2

pankkake

pankkake

Posté
Posté

Complètement n'importe quoi, qui sont les gros nazes qui se prennent au sérieux en parlant de "bug" de ce type en fournissant un… algorithme ? La taille maximale de stockage des entiers dépend de ce qu'on a choisi pour stocker la donnée. J'ai perdu mon temps à chercher un pseudo bug.

Parce que avec un algorithme dans un pseudo langage, je peux te trouver des milliers de bugs d'implémentation qui PEUVENT en découler.

Là, ce jeu demandait de trouver un bug qu'un mauvais implémenteur aurait pu laisser passer…

0100011

0100011

Posté
  • Auteur
Posté
il est vrai qu'avec mon exemple j'aurais du m'apercevoir que mid=low + (high-low)/2

et je comprends mieux pourquoi vous appelez ça un bug.

Car vu ma formule la ressource en temps machine était trop importante pour l'utiliser dans tous les cas.

Il est clair que la formule mid= low + (high-low)*0.5 si vous parlez d'implémentation est la plus efficace, bien plus que mid= low +(high-low)/2

Ce qui est beau est que la correction est forcément bonne a partir du moment où high et low sont "corrects" (de toutes manières ça n'aurait pas de sens de parler de l'algo autrement).

0100011

0100011

Posté
  • Auteur
Posté
Complètement n'importe quoi, qui sont les gros nazes qui se prennent au sérieux en parlant de "bug" de ce type en fournissant un… algorithme ? La taille maximale de stockage des entiers dépend de ce qu'on a choisi pour stocker la donnée. J'ai perdu mon temps à chercher un pseudo bug.

Parce que avec un algorithme dans un pseudo langage, je peux te trouver des milliers de bugs d'implémentation qui PEUVENT en découler.

Là, ce jeu demandait de trouver un bug qu'un mauvais implémenteur aurait pu laisser passer…

C'est pas n'importe quoi : des machines ont planté "pour de vrai" avec du pognon à la clef à cause de cette implantation précise (qui était dans la distrib de nombreux langages de progs mondialement utilisés). C'est pas un pseudo bug justement mais un vrai bug concret.

Herbert West

Herbert West

Posté
Posté
Complètement n'importe quoi, qui sont les gros nazes qui se prennent au sérieux en parlant de "bug" de ce type en fournissant un… algorithme ? La taille maximale de stockage des entiers dépend de ce qu'on a choisi pour stocker la donnée. J'ai perdu mon temps à chercher un pseudo bug.

Parce que avec un algorithme dans un pseudo langage, je peux te trouver des milliers de bugs d'implémentation qui PEUVENT en découler.

Là, ce jeu demandait de trouver un bug qu'un mauvais implémenteur aurait pu laisser passer…

+1 ma crêpe.

On peut par exemple parler du possible débordement de la pile d'exécution si l'algo est implanté tel quel dans un langage qui n'optimise pas le cas de la récursivité terminale (grosso modo, tous les langages sauf Scheme).

edit : d'où, pour reprendre l'analogie que tente de faire Kassad entre ce bug et le libéralisme, je conclue qu'il existe des choses qui fonctionnent très bien mais que personne ne prend la peine d'utiliser sous prétexte qu'ils s'agiraient de "trucs théoriques pour universitaires qui s'ennuient" :icon_up:

pankkake

pankkake

Posté
Posté
C'est pas n'importe quoi : des machines ont planté "pour de vrai" avec du pognon à la clef à cause de cette implantation précise (qui était dans la distrib de nombreux langages de progs mondialement utilisés). C'est pas un pseudo bug justement mais un vrai bug concret.

C'est un bug qui n'est PAS présent dans l'algorithme présenté plus haut. Il y a juste un bug d'implémentation potentiel, parmi d'autres bugs d'implémentation potentiels. Il y a des langages qui sont capables de travailler avec des nombres, sans limite, ce n'est même pas un bug d'implémentation toujours réalisable.

C'est une devinette de merde, dont la seule difficulté est d'être faussement présentée.

0100011

0100011

Posté
  • Auteur
Posté
C'est un bug qui n'est PAS présent dans l'algorithme présenté plus haut. Il y a juste un bug d'implémentation potentiel, parmi d'autres bugs d'implémentation potentiels. Il y a des langages qui sont capables de travailler avec des nombres, sans limite, ce n'est même pas un bug d'implémentation toujours réalisable.

C'est une devinette de merde, dont la seule difficulté est d'être faussement présentée.

Ce que tu dis est faux il y a TOUJOURS une limite sur une machine physique, il n'y en a pas en théorie sur des entiers. C'est une différence fondamentale justement entre les maths et l'info (le fait qu'il y a une limite même si elle n'est pas précisée) que tu fasses comme si ça n'avait pas d'importance est grave.

Ash

Ash

Posté
Posté
Tous ceux-ci me rappelle mon premier cours de programmation et cette phrase qui me restera pour toujours :

GARBAGE IN, GARBAGE OUT!

:icon_up:

0100011

0100011

Posté
  • Auteur
Posté
De toute façon si ce pseudo bug à perdurer pendant 50 ans c'est que son incidence était mineure.

Bien sûr ce bug particulier est juste une blague mais derrière il y a une importante leçon sur l'informatique. De plus on peut le généraliser et le retrouver sous d'autres formes plus complexes.

Herbert West

Herbert West

Posté
Posté
Bien sûr ce bug particulier est juste une blague mais derrière il y a une importante leçon sur l'informatique. De plus on peut le généraliser et le retrouver sous d'autres formes plus complexes.

Notamment des problèmes de sécurité (integer overflows théoriques ou pratiques y compris dans des softs réputés comme OpenSSH ou qmail, etc.)

Mais c'est surtout un problème lié au langage…

pankkake

pankkake

Posté
Posté
Ce que tu dis est faux il y a TOUJOURS une limite sur une machine physique, il n'y en a pas en théorie sur des entiers. C'est une différence fondamentale justement entre les maths et l'info (le fait qu'il y a une limite même si elle n'est pas précisée) que tu fasses comme si ça n'avait pas d'importance est grave.

Imaginons un langage capable d'étendre ses structures d'entiers à l'infini (du moins… à la taille de la mémoire physique, ÉVIDEMMENT)… le problème se posera d'abord avec la liste qu'on lui donne qui sera bien plus grosse.

Et, de toute façon, ma critique sur le fait que ce n'est qu'un des multiples bugs possibles une fois qu'on fait ce qui était pas ou très mal expliqué dans l'énoncé de départ reste.

Donc chut et plus d'énigmes malhonnêtes de ce genre, je déteste particulièrement ça.

Archivé

Ce sujet est désormais archivé et ne peut plus recevoir de nouvelles réponses.

Aller sur la liste des sujets
×
×
  • Créer...