Il y a presque 9 ans, Cloudflare était une petite entreprise et je ne travaillais pas pour elle, j'étais juste un client. Un mois après le lancement de Cloudflare, j'ai reçu une notification indiquant que mon site Web Le DNS ne semble pas fonctionner. Cloudflare a apporté une modification à , et il y avait un DNS cassé.
J'ai immédiatement écrit à Matthew Prince avec le titre « Où est mon DNS ? » et il m'a renvoyé une longue réponse pleine de détails techniques (), à quoi j'ai répondu :
De : John Graham-Cumming
Date : 7 octobre 2010, 9h14
Objet : Re : Où est mon DNS ?
À : Matthieu PrinceSuper reportage, merci. J'appellerai certainement s'il y a des problèmes. Cela vaut probablement la peine d’écrire un article à ce sujet une fois que vous aurez collecté toutes les informations techniques. Je pense que les gens apprécieront une histoire ouverte et honnête. Surtout si vous y joignez des graphiques pour montrer l’évolution du trafic depuis le lancement.
J'ai un bon suivi sur mon site, et je reçois un SMS à chaque panne. La surveillance montre que la panne s'est produite de 13:03:07 à 14:04:12. Les tests sont effectués toutes les cinq minutes.
Je suis sûr que vous comprendrez. Etes-vous sûr de ne pas avoir besoin de votre propre personne en Europe ? 🙂
Et il répondit:
De : Matthieu Prince
Date : 7 octobre 2010, 9h57
Objet : Re : Où est mon DNS ?
À : John Graham-CummingMerci. Nous avons répondu à tous ceux qui ont écrit. Je suis en route pour le bureau maintenant et nous allons écrire quelque chose sur le blog ou épingler un article officiel sur notre babillard. Je suis tout à fait d'accord, l'honnêteté est primordiale.
Maintenant, Cloudflare est une très grande entreprise, je travaille pour elle, et maintenant je dois écrire ouvertement sur notre erreur, ses conséquences et nos actions.
Événements du 2 juillet
Le 2 juillet, nous avons déployé une nouvelle règle dans les règles gérées pour les WAF, grâce à laquelle sur chaque cœur de processeur traitant le trafic HTTP/HTTPS sur le réseau Cloudflare dans le monde entier. Nous améliorons constamment les règles gérées pour les WAF en réponse aux nouvelles vulnérabilités et menaces. En mai, par exemple, nous nous sommes dépêchés pour se protéger contre une vulnérabilité grave dans SharePoint. Tout l’intérêt de notre WAF réside dans la capacité de déployer des règles rapidement et globalement.
Malheureusement, la mise à jour de jeudi dernier contenait une expression régulière qui gaspillait trop de ressources CPU HTTP/HTTPS lors du retour en arrière. Nos fonctions principales de proxy, CDN et WAF en ont souffert. Le graphique montre que les ressources du processeur pour gérer le trafic HTTP/HTTPS atteignent près de 100 % sur les serveurs de notre réseau.
Utilisation du processeur à un point de présence lors d'un incident
En conséquence, nos clients (et les clients de nos clients) se sont retrouvés avec une page d'erreur 502 sur les domaines Cloudflare. 502 erreurs ont été générées par les serveurs Web frontaux Cloudflare qui disposaient encore de cœurs libres mais étaient incapables de communiquer avec les processus gérant le trafic HTTP/HTTPS.
Nous savons combien de désagréments cela a causé à nos clients. Nous avons terriblement honte. Et cet échec nous a empêché de gérer efficacement l’incident.
Si vous étiez l’un de ces clients, vous étiez probablement effrayé, en colère et bouleversé. De plus, nous n'avons pas eu de . La consommation élevée du processeur était due à une règle WAF avec une expression régulière mal formulée qui entraînait un retour en arrière excessif. Voici l'expression coupable : (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Bien que cela soit intéressant en soi (et j'en parlerai plus en détail ci-dessous), le service Cloudflare est resté indisponible pendant 27 minutes, non seulement à cause d'une mauvaise expression régulière. Il nous a fallu un certain temps pour décrire la séquence d’événements qui ont conduit à l’échec, nous avons donc mis du temps à réagir. À la fin de l'article, je décrirai le retour en arrière dans une expression régulière et vous dirai quoi en faire.
Ce qui s'est passé
Commençons dans l'ordre. Toutes les heures ici sont en UTC.
A 13h42, un ingénieur de l'équipe pare-feu apporte une petite modification aux règles de détection en utilisant un processus automatique. En conséquence, un ticket de demande de modification a été créé. Nous gérons ces tickets via Jira (capture d'écran ci-dessous).
Après 3 minutes, la première page de PagerDuty est apparue, signalant un problème avec WAF. Il s'agissait d'un test synthétique qui testait la fonctionnalité des WAF (nous en avons des centaines) en dehors de Cloudflare pour surveiller le fonctionnement normal. Cela a été immédiatement suivi par des pages d'alertes sur l'échec d'autres tests de bout en bout du service Cloudflare, des problèmes de trafic mondial, des erreurs 502 généralisées et une tonne de rapports de nos points de présence (PoP) dans des villes du monde entier qui indiquaient un manque. de ressources CPU.
J'ai reçu plusieurs de ces alertes, je suis sorti en trombe d'une réunion et j'étais en route vers la table lorsque le chef de notre département de développement de solutions a déclaré que nous avions perdu 80 % de notre trafic. J'ai couru vers nos ingénieurs SRE, qui travaillaient déjà sur le problème. Au début, nous avons pensé qu'il s'agissait d'une sorte d'attaque inconnue.
Les ingénieurs Cloudflare SRE sont dispersés dans le monde entier et surveillent la situation 0 heures sur XNUMX. En règle générale, ces alertes vous informent de problèmes locaux spécifiques de portée limitée, sont suivies sur des tableaux de bord internes et sont résolues plusieurs fois par jour. Mais ces pages et notifications indiquaient quelque chose de vraiment grave, et les ingénieurs SRE ont immédiatement déclaré le niveau de gravité PXNUMX et contacté la direction et les ingénieurs système.
Nos ingénieurs londoniens écoutaient à ce moment-là une conférence dans le hall principal. La conférence a dû être interrompue, tout le monde s'est réuni dans une grande salle de conférence et d'autres spécialistes ont été convoqués. Il ne s’agissait pas d’un problème typique que les SRE pouvaient résoudre eux-mêmes. Il était urgent d'impliquer les bons spécialistes.
À 14h00, nous avons déterminé que le problème venait du WAF et qu’il n’y avait pas eu d’attaque. L'équipe chargée des performances a extrait les données du processeur et il est devenu clair que le WAF était à blâmer. Un autre employé a confirmé cette théorie en utilisant Strace. Quelqu'un d'autre a vu dans les journaux qu'il y avait un problème avec WAF. À 14h02, toute l'équipe est venue me voir lorsqu'il a été proposé d'utiliser global kill, un mécanisme intégré à Cloudflare qui arrête un composant dans le monde entier.
La façon dont nous avons procédé à une destruction globale pour WAF est une autre histoire. ce n'est pas si simple. Nous utilisons nos propres produits, et depuis notre service n'a pas fonctionné, nous n'avons pas pu nous authentifier et nous connecter au panneau de contrôle interne (une fois tout a été réparé, nous avons appris que certains membres de l'équipe avaient perdu l'accès en raison d'une fonction de sécurité qui désactive les informations d'identification si le panneau de contrôle interne n'est pas utilisé pour un longue durée).
Et nous ne pouvions pas accéder à nos services internes, comme Jira ou le système de build. Nous avions besoin d'un mécanisme de contournement, que nous utilisions rarement (cela devra également être mis au point). Finalement, un ingénieur a réussi à désactiver le WAF à 14h07, et à 14h09, les niveaux de trafic et de CPU étaient revenus à la normale partout. Le reste des mécanismes de protection de Cloudflare ont fonctionné normalement.
Ensuite, nous avons commencé à restaurer le WAF. La situation était hors du commun, nous avons donc effectué des tests négatifs (en nous demandant si le changement était vraiment le problème) et des tests positifs (en nous assurant que le rollback fonctionnait) dans une ville en utilisant un trafic séparé, en transférant les clients payants à partir de là.
À 14h52, nous étions convaincus d'avoir compris la raison, d'avoir apporté une correction et d'activer à nouveau WAF.
Comment fonctionne Cloudflare
Cloudflare dispose d'une équipe d'ingénieurs dédiée à la gestion des règles pour les WAF. Ils s’efforcent d’améliorer les taux de détection, de réduire les faux positifs et de répondre rapidement aux nouvelles menaces dès leur apparition. Au cours des 60 derniers jours, 476 demandes de modification ont été traitées pour les règles gérées pour WAF (en moyenne une toutes les 3 heures).
Ce changement particulier devait être déployé en mode simulation, où le trafic client réel passe par la règle, mais rien n'est bloqué. Nous utilisons ce mode pour tester l’efficacité des règles et mesurer les taux de faux positifs et de faux négatifs. Mais même en mode simulation, les règles doivent effectivement être exécutées, et dans ce cas la règle contenait une expression régulière qui consommait trop de ressources processeur.
Comme vous pouvez le voir dans la demande de modification ci-dessus, nous disposons d'un plan de déploiement, d'un plan de restauration et d'un lien vers une procédure opérationnelle standard (SOP) interne pour ce type de déploiement. La SOP pour modifier une règle permet de la publier globalement. En fait, chez Cloudflare, les choses se font complètement différemment, et les SOP exigent que nous expédiions d'abord le logiciel pour les tests et l'utilisation interne à un point de présence interne (PoP) (que nos employés utilisent), puis à un petit nombre de clients dans un endroit isolé, puis à un grand nombre de clients, et ensuite seulement au monde entier.
Voilà à quoi cela ressemble. Nous utilisons git en interne via BitBucket. Les ingénieurs travaillant sur les modifications soumettent le code, qui est construit à TeamCity, et lorsque la construction est réussie, des réviseurs sont affectés. Une fois qu'une pull request est approuvée, le code est assemblé et une série de tests est exécutée (à nouveau).
Si la construction et les tests réussissent, une demande de modification est créée dans Jira et le responsable ou responsable approprié doit approuver la modification. Après approbation, le déploiement a lieu dans ce que l'on appelle la «ménagerie PoP» : CHIEN, PIG et (chien, cochon et canari).
DOG PoP est un PoP Cloudflare (comme toutes les autres villes) qui est utilisé uniquement par les employés de Cloudflare. PoP à usage interne vous permet de détecter les problèmes avant que le trafic client ne commence à affluer vers la solution. Chose utile.
Si le test CHIEN réussit, le code passe à l'étape PIG (cochon d'Inde). Il s'agit de Cloudflare PoP, où une petite quantité de trafic client gratuit circule via un nouveau code.
Si tout va bien, le code va dans Canary. Nous avons trois PoP des Canaries dans différentes parties du monde. Dans ceux-ci, le trafic des clients payants et gratuits passe par le nouveau code, et c'est la dernière vérification des erreurs.
Processus de publication de logiciels chez Cloudflare
Si le code est correct dans Canary, nous le publions. Parcourir toutes les étapes - CHIEN, COCHON, Canari, le monde entier - prend plusieurs heures ou jours, selon le changement de code. En raison de la diversité du réseau et des clients de Cloudflare, nous testons minutieusement le code avant de le diffuser globalement à tous les clients. Mais WAF ne suit pas spécifiquement ce processus car il faut réagir rapidement aux menaces.
Menaces WAF
Au cours des dernières années, on a constaté une augmentation significative des menaces dans les applications courantes. Cela est dû à la plus grande disponibilité des outils de test de logiciels. Par exemple, nous avons récemment écrit sur ).
Source:
Très souvent, une preuve de concept est créée et immédiatement publiée sur Github afin que les équipes qui maintiennent l'application puissent la tester rapidement et s'assurer qu'elle est bien sécurisée. Par conséquent, Cloudflare doit pouvoir répondre aux nouvelles attaques le plus rapidement possible afin que les clients aient la possibilité de réparer leur logiciel.
Un bon exemple de la réponse rapide de Cloudflare est le déploiement de protections contre les vulnérabilités SharePoint en mai (). Presque immédiatement après les annonces, nous avons remarqué un grand nombre de tentatives d'exploitation de la vulnérabilité dans les installations SharePoint de nos clients. Nos gars surveillent constamment les nouvelles menaces et écrivent des règles pour protéger nos clients.
La règle à l'origine du problème jeudi était censée protéger contre le cross-site scripting (XSS). De telles attaques sont également devenues beaucoup plus fréquentes ces dernières années.
Source:
La procédure standard pour modifier une règle gérée pour un WAF consiste à effectuer des tests d'intégration continue (CI) avant le déploiement global. Jeudi dernier, nous l'avons fait et avons déployé les règles. À 13 h 31, un ingénieur a soumis une pull request approuvée avec un changement.
À 13h37, TeamCity a collecté les règles, effectué des tests et donné le feu vert. La suite de tests WAF teste les fonctionnalités de base du WAF et comprend un grand nombre de tests unitaires pour des fonctions individuelles. Après des tests unitaires, nous avons testé les règles du WAF en utilisant un grand nombre de requêtes HTTP. Les requêtes HTTP vérifient quelles requêtes doivent être bloquées par le WAF (pour intercepter l'attaque) et lesquelles peuvent être autorisées (afin de ne pas tout bloquer et d'éviter les faux positifs). Mais nous n'avons pas testé l'utilisation excessive du processeur, et l'examen des journaux des versions précédentes du WAF montre que le temps d'exécution des tests de règles n'a pas augmenté et qu'il était difficile de soupçonner qu'il n'y aurait pas suffisamment de ressources.
Les tests ont réussi et TeamCity a commencé à déployer automatiquement le changement à 13h42.
Mercure
Les règles WAF se concentrent sur la résolution immédiate des menaces. Nous les déployons donc à l'aide du magasin clé-valeur distribué de Quicksilver, qui propage les modifications à l'échelle mondiale en quelques secondes. Tous nos clients utilisent cette technologie lorsqu'ils modifient la configuration dans le tableau de bord ou via l'API, et c'est grâce à elle que nous réagissons aux changements à la vitesse de l'éclair.
Nous n'avons pas beaucoup parlé de Quicksilver. Auparavant, nous utilisions en tant que magasin clé-valeur distribué à l'échelle mondiale, mais il a rencontré des problèmes opérationnels et nous avons créé notre propre magasin, répliqué dans plus de 180 villes. Nous utilisons désormais Quicksilver pour transmettre les modifications de configuration aux clients, mettre à jour les règles WAF et distribuer le code JavaScript écrit par les clients à Cloudflare Workers.
Il ne faut que quelques secondes entre le clic sur un bouton d’un tableau de bord ou l’appel d’une API pour effectuer une modification de configuration dans le monde entier. Les clients ont adoré cette rapidité de configuration. Et Workers leur offre un déploiement mondial de logiciels presque instantané. En moyenne, Quicksilver propage environ 350 changements par seconde.
Et Quicksilver est très rapide. En moyenne, nous avons atteint le 99e percentile de 2,29 secondes pour propager les modifications sur tous les ordinateurs du monde. La vitesse est généralement une bonne chose. Après tout, lorsque vous activez une fonction ou videz le cache, cela se produit presque instantanément et partout. L'envoi de code via Cloudflare Workers s'effectue à la même vitesse. Cloudflare promet à ses clients des mises à jour rapides au bon moment.
Mais dans ce cas, la vitesse nous a fait une cruelle plaisanterie et les règles ont changé partout en quelques secondes. Vous avez peut-être remarqué que le code WAF utilise Lua. Cloudflare utilise largement Lua dans la production et les détails nous . Lua WAF utilise en interne et applique un retour en arrière pour la correspondance. Il ne dispose d’aucun mécanisme de protection contre les expressions incontrôlables. Ci-dessous, j'en parlerai davantage et de ce que nous faisons à ce sujet.
Avant le déploiement des règles, tout s'est bien passé : la pull request a été créée et approuvée, le pipeline CI/CD a collecté et testé le code, la demande de modification a été soumise conformément à la SOP qui régit le déploiement et la restauration, et le déploiement a été terminé.
Processus de déploiement de Cloudflare WAF
Ce qui ne va pas
Comme je l'ai dit, nous déployons des dizaines de nouvelles règles WAF chaque semaine et nous disposons de nombreux systèmes pour nous protéger contre les conséquences négatives d'un tel déploiement. Et quand quelque chose ne va pas, c’est généralement une combinaison de plusieurs circonstances à la fois. Si vous ne trouvez qu’une seule raison, c’est bien sûr rassurant, mais ce n’est pas toujours vrai. Ce sont les raisons qui, ensemble, ont conduit à l’échec de notre service HTTP/HTTPS.
- Un ingénieur a écrit une expression régulière qui peut entraîner une .
- Une fonctionnalité qui aurait pu empêcher l'expression régulière de gaspiller trop de CPU a été supprimée par erreur lors d'une refactorisation du WAF plusieurs semaines plus tôt : la refactorisation était nécessaire pour que le WAF consomme moins de ressources.
- Le moteur d'expression régulière n'avait aucune garantie de complexité.
- La suite de tests n'a pas pu détecter une consommation excessive de processeur.
- Le SOP permet de déployer des modifications de règles non urgentes à l’échelle mondiale sans processus en plusieurs étapes.
- Le plan de restauration nécessitait d’exécuter deux fois une version complète du WAF, ce qui prenait beaucoup de temps.
- La première alerte concernant des problèmes de circulation mondiaux a été déclenchée trop tard.
- Nous avons mis du temps à mettre à jour la page de statut.
- Nous avons eu des problèmes pour accéder aux systèmes en raison d’un problème et la procédure de contournement n’était pas bien établie.
- Les ingénieurs SRE ont perdu l'accès à certains systèmes car leurs informations d'identification ont expiré pour des raisons de sécurité.
- Nos clients n'avaient pas accès au tableau de bord ou à l'API Cloudflare car ils passent par une région Cloudflare.
Ce qui a changé depuis jeudi dernier
Tout d'abord, nous avons complètement arrêté tout travail sur les versions pour WAF et procédons comme suit :
- Nous réintroduisons la protection contre la surutilisation du processeur que nous avons supprimée. (Prêt)
- Vérification manuelle de l'ensemble des 3868 XNUMX règles gérées par le WAF afin de détecter et de corriger d'autres cas potentiels de retour en arrière excessif. (Vérification terminée)
- Nous incluons le profilage des performances pour toutes les règles de l'ensemble de test. (Prévu : 19 juillet)
- Passer à un moteur d'expression régulière ou - les deux offrent des garanties d'exécution. (Prévu : 31 juillet)
- Nous réécrivons les SOP pour déployer les règles par étapes, comme d'autres logiciels de Cloudflare, mais nous avons en même temps la possibilité d'effectuer un déploiement mondial d'urgence si les attaques ont déjà commencé.
- Nous développons la possibilité de supprimer de toute urgence le tableau de bord et l'API Cloudflare de la région Cloudflare.
- Automatisation des mises à jour des pages .
À long terme, nous nous éloignons du Lua WAF que j'ai écrit il y a quelques années. Déplacer WAF vers . De cette façon, le WAF sera plus rapide et bénéficiera d’un niveau de protection supplémentaire.
Conclusion
Cet échec a causé des problèmes pour nous et nos clients. Nous avons agi rapidement pour corriger la situation et travaillons maintenant sur les failles des processus qui ont provoqué le crash, tout en creusant encore plus profondément pour nous prémunir contre d'éventuels problèmes avec les expressions régulières à l'avenir lors de la migration vers une nouvelle technologie.
Nous sommes très gênés par cette panne et nous excusons auprès de nos clients. Nous espérons que ces changements garantiront qu’une telle situation ne se reproduise plus.
Application. Revenir en arrière sur les expressions régulières
Pour comprendre comment fonctionne l'expression :
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))a consommé toutes les ressources du processeur, vous devez en savoir un peu plus sur le fonctionnement du moteur d'expression régulière standard. Le problème ici est le modèle .*(?:.*=.*). (?: et correspondant ) est un groupe sans capture (c'est-à-dire que l'expression entre parenthèses est regroupée en une seule expression).
Dans le contexte d'une consommation excessive de CPU, ce modèle peut être décrit comme .*.*=.*. Sous cette forme, le modèle semble inutilement complexe. Mais plus important encore, dans le monde réel, les expressions (comme les expressions complexes dans les règles WAF) qui demandent au moteur de faire correspondre un fragment suivi d'un autre fragment peuvent conduire à un retour en arrière catastrophique. Et c'est pourquoi.
Dans une expression régulière . signifie que vous devez faire correspondre un caractère, .* - faire correspondre zéro ou plusieurs caractères « goulûment », c'est-à-dire capturer un maximum de caractères, pour que .*.*=.* signifie correspondre à zéro ou plusieurs caractères, puis correspondre à zéro ou plusieurs caractères, rechercher le caractère littéral =, correspondre à zéro ou plusieurs caractères.
Prenons la ligne de test x=x. Cela correspond à l'expression .*.*=.*. .*.* avant que le signe égal corresponde au premier x (un des groupes .* match x, et le deuxième - zéro caractère). .* après = derniers matchs x.
Cette comparaison nécessite 23 étapes. Premier groupe .* в .*.*=.* agit avec gourmandise et correspond à la chaîne entière x=x. Le moteur passe au groupe suivant .*. Nous n'avons plus de personnages à associer, donc le deuxième groupe .* correspond à zéro caractère (cela est autorisé). Puis le moteur se déplace vers le panneau =. Il n'y a plus de symboles (premier groupe .* utilisé toute l'expression x=x), aucune comparaison n'a lieu.
Et puis le moteur d’expression régulière revient au début. Il passe au premier groupe .* et le compare с x= (au lieu de x=x), puis affronte le deuxième groupe .*. Deuxième groupe .* est comparé au deuxième x, et encore une fois, nous n'avons plus aucun personnage. Et quand le moteur atteint à nouveau = в .*.*=.*, rien ne fonctionne. Et il fait encore marche arrière.
Cette fois, le groupe .* correspond toujours x=, mais le deuxième groupe .* Pas plus x, et zéro caractère. Le moteur essaie de trouver un caractère littéral = dans le modèle .*.*=.*, mais ne sort pas (après tout, le premier groupe l'a déjà occupé .*). Et il fait encore marche arrière.
Cette fois, le premier groupe .* ne prend que le premier x. Mais le deuxième groupe .* capture « goulûment » =x. Avez-vous déjà deviné ce qui va se passer ? Le moteur essaie de correspondre au sens littéral =, échoue et fait un autre retour en arrière.
Le premier groupe d' .* correspond toujours au premier x. Deuxième .* ne prend que =. Bien sûr, le moteur ne peut pas correspondre au sens littéral =, parce que le deuxième groupe l'a déjà fait .*. Et encore une fois, retour en arrière. Et nous essayons de faire correspondre une chaîne de trois caractères !
En conséquence, le premier groupe .* correspond uniquement au premier xseconde .* - avec zéro caractère, et le moteur correspond enfin au littéral = en expression с = en ligne. Vient ensuite le dernier groupe .* est comparé au dernier x.
23 étapes seulement pour x=x. Regardez une courte vidéo sur l'utilisation de Perl , qui montre comment les étapes et les retours en arrière se produisent.
C'est déjà beaucoup de travail, mais et si à la place x=x nous aurons x=xx? Cela fait 33 étapes. Et si x=xxx? 45. La relation n’est pas linéaire. Le graphique montre une comparaison de x=x à x=xxxxxxxxxxxxxxxxxxxx (20 x après =). Si nous avons 20 x après =, le moteur complète la correspondance en 555 étapes ! (D'ailleurs, si nous avons perdu x= et la chaîne se compose simplement de 20 x, le moteur fera 4067 pas pour comprendre qu'il n'y a pas de correspondance).
Cette vidéo montre tous les retours en arrière à des fins de comparaison x=xxxxxxxxxxxxxxxxxxxx:
Le problème est qu’à mesure que la taille de la chaîne augmente, le temps de correspondance augmente de manière super-linéaire. Mais les choses peuvent empirer encore si l’expression régulière est légèrement modifiée. Disons que nous avions .*.*=.*; (c'est-à-dire qu'il y avait un point-virgule littéral à la fin du modèle). Par exemple, pour faire correspondre une expression comme foo=bar;.
Et ici, faire marche arrière serait un véritable désastre. En comparaison x=x il faudra 90 pas, et non 23. Et ce nombre augmente rapidement. Comparer x= et 20 x, 5353 étapes sont nécessaires. Voici le graphique. Regardez les valeurs des axes Y par rapport au tableau précédent.
Si vous êtes intéressé, consultez les 5353 XNUMX étapes de correspondance ayant échoué x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
En utilisant une correspondance paresseuse plutôt que gourmande, l’étendue du retour en arrière peut être contrôlée. Si nous changeons l'expression originale en .*?.*?=.*?, en comparaison x=x cela prendra 11 étapes (et non 23). Pour ce qui est de x=xxxxxxxxxxxxxxxxxxxx. Tout ça parce que ? après .* indique au moteur de faire correspondre un nombre minimum de caractères avant de continuer.
Mais les mappages paresseux ne résolvent pas complètement le problème du retour en arrière. Si l'on remplace l'exemple catastrophique .*.*=.*; sur .*?.*?=.*?;, le temps d'exécution restera le même. x=x nécessite toujours 555 étapes, et x= et 20 x - 5353.
La seule chose qui puisse être faite (outre la réécriture complète du modèle pour une plus grande spécificité) est d'abandonner le moteur d'expression régulière avec son mécanisme de retour en arrière. C'est ce que nous ferons au cours des prochaines semaines.
La solution à ce problème est connue depuis 1968, lorsque Kent Thompson a écrit un article (« Méthodes de programmation : algorithme de recherche d'expressions régulières »). L'article décrit un mécanisme qui vous permet de convertir une expression régulière en machines à états finis non déterministes et, après des changements d'état dans des machines à états finis non déterministes, d'utiliser un algorithme dont le temps d'exécution dépend linéairement de la chaîne correspondante.
Méthodes de programmation
Algorithme de recherche d’expressions régulières
Ken Thompson
Laboratoires téléphoniques Bell, Inc., Murray Hill, New JerseyIl décrit une méthode de recherche d'une chaîne de caractères spécifique dans un texte et discute de l'implémentation de cette méthode sous forme de compilateur. Le compilateur prend l'expression régulière comme code source et produit le programme IBM 7094 sous forme de code objet. Le programme objet prend une entrée sous la forme d'un texte de recherche et émet un signal chaque fois qu'une chaîne de texte est comparée à une expression régulière donnée. L'article fournit des exemples, des problèmes et des solutions.
Algorithme
Les algorithmes de recherche précédents entraînaient un retour en arrière si une recherche partiellement réussie ne produisait pas de résultat.En mode compilation, l'algorithme ne fonctionne pas avec des symboles. Il transmet les instructions au code compilé. L'exécution est très rapide : après avoir transmis les données en haut de la liste actuelle, il recherche automatiquement tous les caractères consécutifs possibles dans l'expression régulière.
L'algorithme de compilation et de recherche est inclus dans l'éditeur de texte en temps partagé en tant que recherche contextuelle. Bien entendu, ce n’est pas la seule application d’une telle procédure de recherche. Par exemple, une variante de cet algorithme est utilisée comme recherche de symboles dans une table en assembleur.
Il est supposé que le lecteur est familier avec les expressions régulières et le langage de programmation informatique IBM 7094.Compilateur
Le compilateur se compose de trois étapes exécutées en parallèle. La première étape est le filtrage syntaxique, qui ne laisse passer que les expressions régulières syntaxiquement correctes. Cette étape insère également l'opérateur "·" pour faire correspondre les expressions régulières. Dans la deuxième étape, l'expression régulière est convertie sous forme suffixe. Lors de la troisième étape, le code objet est créé. Les 2 premières étapes sont évidentes, et nous ne nous y attarderons pas.
L'article de Thompson ne parle pas de machines à états finis non déterministes, mais il explique bien l'algorithme de temps linéaire et présente un programme ALGOL-60 qui génère du code en langage assembleur pour l'IBM 7094. L'implémentation est délicate, mais l'idée est très simple.
chemin de recherche actuel. Il est représenté par une icône ⊕ avec une entrée et deux sorties.
La figure 1 montre les fonctions de la troisième étape de compilation lors de la transformation d'un exemple d'expression régulière. Les trois premiers caractères de l'exemple sont a, b, c, et chacun crée une entrée de pile S[i] et un champ NNODE.NNODE au code existant pour générer l'expression régulière résultante dans une seule entrée de pile (voir Figure 5)
Voici à quoi ressemblerait une expression régulière .*.*=.*, si vous l’imaginez comme dans les images de l’article de Thompson.
En figue. 0 il y a cinq états commençant à 0, et 3 cycles qui partent des états 1, 2 et 3. Ces trois cycles correspondent à trois .* dans une expression régulière. 3 ovales avec des points correspondent à un symbole. Ovale avec un signe = correspond à un caractère littéral =. L'état 4 est définitif. Si nous l'atteignons, alors l'expression régulière correspond.
Pour voir comment un tel diagramme d'état peut être utilisé pour la correspondance d'expressions régulières .*.*=.*, nous examinerons la correspondance des chaînes x=x. Le programme démarre à partir de l'état 0, comme le montre la Fig. 1.
Pour que cet algorithme fonctionne, la machine à états doit être dans plusieurs états simultanément. Une machine finie non déterministe effectuera simultanément toutes les transitions possibles.
Avant d'avoir le temps de lire les données d'entrée, il passe dans les deux premiers états (1 et 2), comme le montre la Fig. 2.
En figue. 2 montre ce qui se passe quand il regarde le premier x в x=x. x peut mapper vers le point supérieur, en passant de l'état 1 et en revenant à l'état 1. Ou x peut mapper jusqu'au point ci-dessous, en passant de l'état 2 et en revenant à l'état 2.
Après avoir fait correspondre le premier x в x=x nous sommes toujours dans les états 1 et 2. Nous ne pouvons pas atteindre l'état 3 ou 4 car nous avons besoin d'un caractère littéral =.
L’algorithme considère alors = в x=x. Comme x avant lui, il peut être associé à l'une des deux boucles supérieures de l'état 1 à l'état 1 ou de l'état 2 à l'état 2, mais l'algorithme peut correspondre au littéral = et passer de l'état 2 à l'état 3 (et immédiatement 4). Ceci est montré sur la Fig. 3.
L'algorithme passe ensuite au dernier x в x=x. À partir des états 1 et 2, les mêmes transitions sont possibles vers les états 1 et 2. À partir de l'état 3 x peut faire correspondre le point de droite et revenir à l'état 3.
A ce stade, chaque personnage x=x considéré, et puisque nous avons atteint l’état 4, l’expression régulière correspond à cette chaîne. Chaque caractère est traité une fois, cet algorithme est donc linéaire dans la longueur de la chaîne d'entrée. Et pas de retour en arrière.
Évidemment, après avoir atteint l’état 4 (lorsque l’algorithme a correspondu x=) l'intégralité de l'expression régulière correspond et l'algorithme peut se terminer sans en tenir compte du tout x.
Cet algorithme dépend linéairement de la taille de la chaîne d'entrée.
Source: habr.com