[Stratégie] détection boucle infini

Version imprimable

23/02/2006, 19h24
dark_falcon

[Stratégie] détection boucle infini

Bonjour,

dans le cadre d'un projet informatique je dois pouvoir détecter les boucles infines dans un programme java.

Si quelqu un pourrais me renseigner sur une méthode de détéction ,
ça me dépannerais beaucoup

merci
23/02/2006, 19h51
kissmytoe
Une boucle doit toujours avoir une condition de sortie.

C'est de vérifier toutes les boucles une par une pour vérifie qu'elles possèdent toutes une condition de sortir SUR pour empecher une boucle sans fin.

Tu pourrais aussi faire un bout de code du genre
Code:

1 2 3 4 5 6 if (i > 300) { (boite de dialogue) boucle infini? conditionSortie = true } i++
23/02/2006, 20h07
TabrisLeFol

Pourrait tu preciser un peu? Avant compilation ou après? Qu'est ce que tu compte faire?
Lors de l'utilisation d'une variable locale test un while(test) en boucle sans fin est assez facile à reconnaitre mais sinon... Je ne vois pas trop comment on pourrait faire la difference entre une boucle très grande, une boucle sans fin...
Le mieu serait d'utiliser des algorithmes prouvables, si des commentaires sont bien ecrits (utilisant toujours une meme synthaxe) il doit etre possible de realiser un robot de verification... mais c'est compliqué...
23/02/2006, 20h25
dark_falcon

précision

pour mon projet je dois analyser un programme java pour voir si il comporte des boucles infinies( avant compilation). Je pense qu une analyse statique du code en étudiant le graphe de controle du programme serait le plus adapté mais je ne sais pas comment je peux le construire (je travaille en java).Alors il suffirait de faire la couverturte du graphe pour voir si celui-ci ce déroule de manière "normal".(me dire si je me trompe),

merci d avance
23/02/2006, 23h23
Gfx

Tu peux jeter un oeil au projet PMD par exemple. C'est open source, en Java et cela fait ce que tu veux. Ca pourrait te donner des idees.
24/02/2006, 10h35
tralloc

Oui je crois qu'il y a pas mal de gens qui se sont cassés la tête sur ce problème.
La seule chose que j'imagine, analyser dans le programme s'il y a des conditions de sorties, et si ces conditions de sorties peuvent être atteintes quelles que soient les valeus d'entrée...

Entre autres termes il s'agit d'un casse tête mathématique.
24/02/2006, 12h26
anykeyh

On ne peut pas utiliser les assertion pour ça? (Je suis pas sur de ce que je dit hein!)
24/02/2006, 16h38
Hervé Saladin

Citation:

On ne peut pas utiliser les assertion pour ça? (Je suis pas sur de ce que je dit hein!)

C'est ce que j'aurais dit moi aussi.
JUnit (et les tests unitaires en général) est fait expres pour tester ton code et vérifier si il est solide, tu devrais te pencher la-dessus, c'est assez facile à faire en plus :)
Le principe est le suivant : tu écris des methodes en java chargées de tester ton code. Tu part du prncipe que l'execution de ce code doit avoir tel ou tel effet, tu l'execute et tu teste si il a bien eu l'effet attendu (assertion).
Je sais ca a pas l'air clair expliqué comme ca, mais tu verra c'est vraiment pas sorcier.
Bon courage, a+.
24/02/2006, 23h32
herve91

La théorie dit qu'il n'existe pas d'algorithme permettant de savoir si un programme se termine dans un temps fini ou non :wink:
24/02/2006, 23h39
anykeyh
Si tu te sent grand, beau et fort (:lol:), je te conseil de coder un parser qui verifiera les contraintes de ta boucle et grace a un puissant algorithme de retropropagation te sortira les ensemble possible pour chaque variable de tes contraintes, et finira par travailler sur ceux-ci afin de te dire si oui ou non ta boucle peu etre infini...
Mais tu peu aussi le faire de tete dans certains cas... (Methode conseillée...)

Exemple:
Code:

1 2 3 4 5 while (a<10) { a++; }
Logiquement, a tend vers +infini si ta boucle tend vers +infini, or +infini>10, donc ta boucle ne peu pas etre infini
Code:

1 2 3 4 5 while (a<10) { a*=5; }
A ce moment la, si dans l'entrée de la boucle a<=0 alors ta boucle sera infini. Donc il faut remonter au dessus de ta boucle voir quel valeur elle peu prendre et s'assurer qu'elle ne peu pas prendre une valeur <= 0

Enfin apres, en pratique, je sais pas si en java l'overflow de variable leve une exception ou comme en c reinitialise la variable a son minimum (0x11111111 - 1 = 0x0111111 avec le dernier bit de signe :))
24/02/2006, 23h46
TabrisLeFol

Citation:

Envoyé par herve91

La théorie dit qu'il n'existe pas d'algorithme permettant de savoir si un programme se termine dans un temps fini ou non :wink:

Un programme "brute" je suis bien d'accord, ou en tout cas je ne vois pas comment on pourait etre sur qu'il s'arrete.
Par contre si on utilise des algorithmes prouvables,il doit y avoir moyen. Par contre je ne sais pas s'il existe de programmes permettant de verifier à 100% qu'un algorithme prouvable est juste...
Justement dans le cas d'un programme brute, serait il possible d'extraire l'algorithme et de le prouver?
(Je sais que je fais un peu dérivé le sujet, mais bon... )
24/02/2006, 23h57
anykeyh

http://fr.wikipedia.org/wiki/Coq_%28logiciel%29

Cela sort de Java, mais d'apres ce que j'ai compris ça sert à ça...
Mais bon, a moins que tu developpe des logiciels pour des fusée, satellite, avion ou tout autre systeme que ne doit absolument pas planter, je conseil la bonne vieille methode du "bon bah sa a l'air de marcher là" :lol:

Est-ce que ce programme se termine (conjecture de Syracuse) ?

Code:

1
2
3
4
5
6
7
8
9
10
public void syracuse(int n) {
   while (n != 1) {
      if ((n % 2) == 0) {
         n = n / 2;
      } else {
         n = 3 * n + 1;
      }
   }
   System.out.println("ouf je me termine !");
}

1) La boucle continue tant que n!=1
donc pour n=1l e programme se termine... :P

2)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 if((n%2)==0) //-> nombre pair { n = n / 2 //-> nombre impair } else { /* Le programme peu s'arreter uniquement si n==1 Or pour cela il faut soit: n = 3 * n + 1 Ce qui est impossible avec un entier naturel superieur à 1 ET n = n / 2 est possible si n = 2 car (2%2)==0 */ n = 3 * n + 1 }
Donc si jme suis pas louper: le programme s'arrette pour tout nombre entre 0 et n (entier non signé) pour n = {1, 2}

Edit: Je viens de voir sur wikipedia, zero pointée huhuhu :P

25/02/2006, 00h23
anykeyh

En fait je dirai qu'il suffit qu'à n'importe quel moment n soit un multiple de 2 (2^n) pour que la suite se termine.
25/02/2006, 00h28
herve91

Citation:

Envoyé par anykeyh

En fait je dirai qu'il suffit qu'à n'importe quel moment n soit un multiple de 2 (2^n) pour que la suite se termine.

Malgré de fortes suspicions, on n'a pas encore prouvé qu'on retombe toujours sur 1 pour tout n... d'où le terme de conjecture. Comme quoi même avec des calculs tout bêtes, il peut être bien difficile (voire impossible) de déterminer si la boucle est finie ou non.
25/02/2006, 00h46
TabrisLeFol

Avec n entier naturel different de 0. La conjecture est que cela se termine pour tout nombre?

En tout cas les 1 000 000, premiers nombres fonctionnent. :lol:
25/02/2006, 00h55
herve91

Citation:

Envoyé par TabrisLeFol

Avec n entier naturel different de 0. La conjecture est que cela se termine pour tout nombre?

Oui

Citation:

Envoyé par TabrisLeFol

En tout cas les 1 000 000, premiers nombres fonctionnent. :lol:

Tu as vérifié :wink:
Alors tu aurais pu aller jusqu'à 3,2×10^16, après on ne sait pas...
14/03/2006, 17h02
Albator5151

Bonjour,

Pour complèter le sujet et peut -etre pour commencer par des choses simples existe-t-il des classes java agissant sur du code source java permettant de savoir quels sont toutes les variables utilisés dans le programmes sans forcément savoir leur valeur.

Merci.
20/03/2006, 17h40
Albator5151

Bonjour,

Toujours à propos du problème de départ quels sont les librairies à utiliser pour récupérer tel ou tel caractère dans du code java. Par exemple je voudrais récupérer toutes les lignes ou un while apparait.

Merci

PS:Surtout si vous avez des idées pour récupérer toutes les valeurs de telle ou telle variable dans un programme, genre avec du découpage avant ou arrière. J'ai aussi entendu parler du logiciel bandera.