La réponse théorique classique du compilateur à cette question est de créer un graphe de flux de contrôle, puis de faire une analyse de graphe pour identifier les boucles naturelles. Je pense que les algorithmes pour cela peuvent être trouvés dans le Dragon Book, et un résumé est donné dans ces diapositives:

http://www.cs.cmu.edu /afs/cs/academic/class/15745-s03/public/lectures/L7_handouts.pdf

Vous pouvez également voir comment LLVM implémente sa détection de boucle:

http://llvm.org/docs/doxygen/html/LoopInfo_8h_source.html

Les termes de recherche que vous souhaitez obtenir plus d'informations sont des choses comme "boucle naturelle" et "bord arrière ".

Vous pourriez trouver cette question sur la recherche d'une fonction récursive utile, il y a de très bonnes réponses à cela. Sous le niveau du code binaire, à mon humble avis, il n'y a que peu de différence entre la détection de boucle (c'est-à-dire certains jmp vers la même cible) et l'appel récursif (c'est-à-dire certains appels vers la même cible ).

Je ne pense pas qu'il existe une méthode standard, mais une approche pourrait être d'utiliser quelque chose comme l'algorithme de Johnson pour détecter les cycles dans le graphe orienté de la fonction.

Vous pouvez trouver une implémentation de ceci dans des bibliothèques comme NetworkX simple_cycles.

La détection des boucles à partir du code binaire n'est pas facile. Il existe de nombreux algorithmes basés sur plusieurs structures de données graphiques (CFG, formulaire SSA, DDG, ...). J'ai fourni un ensemble de documents utiles supplémentaires link1, link2, link3. Vous pouvez vérifier la mise en œuvre par MAQAO d'un détecteur de boucle basé sur le SSA. De plus, je vous recommande de vérifier le code et la documentation de DynInst link4.

Vous pouvez maintenant implémenter un analyseur de code d'assemblage capable de détecter les blocs / boucles de base en suivant les branches.

1. Désassemblez votre binaire et suivez les instructions.
2. Si un saut conditionnel est rencontré (modèle Jxx), vérifiez s'il saute au-dessus ou en dessous .

3. Si le saut pointe ci-dessus, vérifiez la distance (Delta (BRANCH_ADDRESS, BRANCH_TARGET_ADDRESS)), si la distance n'est pas trop grande (vous devrez décider d'une limite) alors vous pouvez appliquer une analyse sur la condition de branchement (vérifier si elle contient un registre qui est déplacé [incrément / décrément]). L'analyse des conditions de branchement peut être une simple correspondance de modèle:

     Exemple 1: TEST X, X Jxx X Exemple 2: CMP X, X Jxx X Exemple 3: DEC X Jnz X 

Si tout se vérifie, vous avez vous-même un bloc de base qui a une forte probabilité d'être une boucle.

4. Si le saut pointe ci-dessous, sa probabilité de faire partie d'une structure de contrôle de boucle est moins probable. Vous pouvez donc l'ignorer et passer à l'instruction suivante.

Si vous avez besoin de plus de détails poilus, je serai heureux de vous en fournir plus;)