Détecter la récursivité dans un fichier C avec Python

Je dois détecter la récursivité directe et indirecte dans un ensemble assez volumineux (5-15 000) de fichiers C (et non C ++).

Les fichiers sont déjà prétraités.

Le code est assez “old school” pour des raisons de sécurité, donc pas d’éléments sophistiqués comme des pointeurs de fonction, mais seulement des fonctions qui transmettent des variables et certaines macros de fonctions qui font de même.

Le moyen le plus naturel de détecter la récursivité consiste à créer un graphe d’appel dirigé, en considérant chaque fonction comme un nœud avec une arête allant à toutes les autres fonctions qu’elle appelle. Si le graphique a des cycles, alors nous avons récursivité.

Une expression rationnelle pour trouver des appels de fonction est facile à faire, mais j’ai également besoin de savoir quelle fonction a appelé.

PyCParser était agréable, mais il se plaint de beaucoup de choses, telles que des variables non définies ou des typedefs où le type de source n’est pas défini ou défini dans un autre fichier qui est totalement non pertinent dans mon cas d’utilisation. Le projet utilise un système de gestion des dépendances personnalisé, de sorte que certains inclus et les autres sont ajoutés automatiquement. PyCParser ne doit donc pas se soucier de rien d’ autre que les nœuds FuncCall et FuncDef et je ne pense pas qu’il y ait un moyen de limiter le processus d’parsing lui-même. juste ça.

Je préférerais ne pas implémenter un parsingur car je n’ai pas le temps d’apprendre exactement comment faire cela en python, puis d’implémenter la solution.

Revenons à la question, comment pourrais-je parsingr les fonctions dans un fichier C? Obtenir essentiellement un dict avec des chaînes (noms de fonctions définies dans le fichier) en tant que clés et des listes de chaînes (les fonctions appelées par chaque fonction) en tant que valeurs? Un regex semble être la solution la plus naturelle.

L’utilisation de python n’est malheureusement pas une option.

Pourquoi ne pas simplement utiliser objdump sur votre code compilé, puis parsingr l’assembly généré pour construire votre graphique?

fichier test1.c:

 extern void test2(); void test1() { test2(); } 

fichier test2.c:

 extern void test1(); void test2() { test1(); } int main() { test2(); } 

maintenant le construire:

 gcc -g test1.c test2.c -o myprog 

maintenant démonter

 objdump -d myprog > myprog.asm 

Recherchez tous les appels de fonctions avec quelques regex simples tout en mémorisant le contexte dans lequel vous vous trouvez. Un exemple du déassembly vous montre à quel point cela devrait être facile:

 00401630 <_test1>: 401630: 55 push %ebp 401631: 89 e5 mov %esp,%ebp 401633: 83 ec 08 sub $0x8,%esp 401636: e8 05 00 00 00 call 401640 <_test2> 40163b: c9 leave 40163c: c3 ret 40163d: 90 nop 40163e: 90 nop 40163f: 90 nop 00401640 <_test2>: 401640: 55 push %ebp 401641: 89 e5 mov %esp,%ebp 401643: 83 ec 08 sub $0x8,%esp 401646: e8 e5 ff ff ff call 401630 <_test1> 40164b: c9 leave 40164c: c3 ret 

utilisez ensuite python pour post-traiter votre désassemblage et créez un dictionnaire de fonction => appelle:

 import re import collections calldict = collections.defaultdict(set) callre = re.comstack(".*\scall\s+.*<(.*)>") funcre = re.comstack("[0-9a-f]+\s<(.*)>:") current_function = "" with open("myprog.asm") as f: for l in f: m = funcre.match(l) if m: current_function = m.group(1) else: m = callre.search(l) if m: called = m.group(1) calldict[current_function].add(called) 

Je n’ai pas écrit la recherche de graphe complète, mais vous pouvez détecter la récursivité “ping-pong” avec un code simple comme:

 for function,called_set in calldict.items(): for called in called_set: callset = calldict.get(called) if callset and function in callset: print(function,called) 

ce qui me donne:

 _test2 _test1 _test1 _test2 

cette technique d’parsing symbole / asm est également utilisée dans callcatcher pour détecter les fonctions C inutilisées (ce qui peut être fait très facilement ici aussi en vérifiant les clés qui ne font partie d’aucun ensemble, avec un peu de filtrage des symboles du compilateur)