Points de trace dynamiques, portables et extensibles en espace utilisateur avec un surcoût minimal et une couverture maximale

L’instrumentation d’un logiciel fait partie de la boîte à outils de l’ingénieur informatique. Ses principales utilisations sont l’évaluation des performances d’un logiciel et la génération d’évènements, dérivés de l’état du programme, en minimisant l’effet de sonde. Deux types d’instrumentation existent. L’instrumentation dite statique est déterminée au moment de la compilation du programme et requiert une recompilation de ce dernier pour être modifiée. Elle contraste avec l’instrumentation dite dynamique qui permet d’être modifiée sans recompilation du programme. Cela a le grand avantage de pouvoir instrumenter un logiciel en production, sans avoir accès à son moteur de production. Or, l’instrumentation dynamique – quoique présente dans le noyau de Linux – est peu présente en espace utilisateur. L’état de l’art actuel propose plusieurs algorithmes – tels que le calembourage d’instructions – permettant d’effectuer une instrumentation dynamique qui minimise les coûts associés à celle-ci sur le programme instrumenté, tout en maximisant sa couverture. Cependant, il n’existe pas d’implémentation robuste basée sur de tels algorithmes qui puisse être utilisée sur des systèmes réels. L’implémentation la plus sérieuse se nomme Dyninst et n’implémente pas ces algorithmes, son paradigme d’instrumentation dynamique étant différent. L’objectif de ce travail est donc de mettre au point de nouveaux algorithmes améliorés, et d’implémenter ceux-ci dans une bibliothèque en espace utilisateur qui unifie, améliore et complète les algorithmes existants en matière d’instrumentation dynamique, en offrant une API qui abstrait les détails architecturaux. Les sous-objectifs sont de maximiser la couverture de l’instrumentation, minimiser le surcoût spatio-temporel associé à l’instrumentation sur le programme, et de garantir l’exactitude de l’instrumentation, c.-à-d. que celle-ci ne brise pas le programme. L’implémentation qui en résulte, nommée Libpatch, a été comparée à Dyninst. Sur le plan de la couverture, Dyninst est en théorie capable d’atteindre 100%, car celui-ci déplace et augmente des flots de contrôle complets du programme. Libpatch, quant à lui, offre une couverture globale de 99.1%, tout en étant beaucoup moins intrusif. Cela favorise Libpatch sur le plan du surcoût spatial en utilisant beaucoup moins de mémoire physique – près de 10 fois moins – que Dyninst, un aspect critique pour les sytèmes embarqués. De plus, le surcoût temporel lié à la modification du programme pour installer ou enlever l’instrumentation est beaucoup moins important pour Libpatch, car ce dernier n’interrompt pas l’ensemble des fils d’exécutions du programme, contrairement à Dyninst. Enfin, les surcoûts temporels, liés vi à l’exécution de l’instrumentation, sont du même ordre de grandeur et Libpatch offre une grande capacité de mise à l’échelle, par rapport au nombre de fils d’exécution. Finalement, Libpatch serait en mesure de bien s’intégrer au sein d’outils tels que GDB et Uftrace, pour augmenter le taux de couverture de leur instrumentation, mais aussi les accélérer. D’autres applications sont aussi possibles, telles que la vérification des accès en mémoire et l’application de correctifs liés à des failles de sécurité.

Abstract

Software instrumentation is a technique increasingly used in software development to determine performance bottlenecks and problems related to the execution of a program. Instrumenters are optimized for generating events derived from the state of the program, while minimizing their impact. Developers often use static instrumentation, where its specification is determined at compile time and is fixed in time. This contrasts with dynamic instrumentation which offers a more flexible specification that can be remodeled after the compilation, allowing the instrumentation of production ready software, without the need for recompilation. Dynamic instrumenters, like Kprobe, are already extensively used in the Linux kernel. There is a lack of such flexible and efficient instrumenters in userspace. There are of course tools like Uprobe that can be used, but their runtime impact on the program are often too important. Recent advances have been made in the literature, presenting new techniques such as instruction punning, which can help in doing userspace dynamic instrumentation. There is, however, no real robust implementation available. The most notable one is Dyninst and it does not implement the latest algorithms, such as instruction punning, since its instrumentation paradigm differs. Therefore, the objective is to design new improved algorithms for efficient and flexible dynamic instrumentation, implementing a userspace library that unifies the latest algorithms in the literature while offering a portable API, abstracting away the architecture dependent details. The sub-objectives are maximizing the instrumentation coverage, minimizing the runtime overhead imposed by the instrumentation, and insuring its portability and correctness. The resulting artifact is a new library named Libpatch and was compared against Dyninst. Theoretically, Dyninst can achieve 100% coverage, since it rewrites the control flow graph of the program. Libpatch is able to achieve near 99.1% global coverage while being less intrusive. This also means that Libpatch uses way less physical memory than Dyninst, a considerable advantage on embedded systems. Furthermore, the modifications made by Lipbatch impose much less time overhead on the program than Dyninst, thanks to its crossmodifying protocol. Moreover, the runtime overhead of executing Libpatch instrumentation is similar, if not better than Dyninst. Finally, Libpatch can be used to improve many tools that rely on dynamic instrumentation, such as GDB and Uftrace, for increasing their instrumentation coverage and reducing their runtime overhead. Other applications are possible as well, such as runtime verification of memory accesses, or hot patching of software vulnerabilities.