Πριν από σχεδόν 9 χρόνια η Cloudflare ήταν μια μικροσκοπική εταιρεία και δεν δούλευα γι' αυτήν, ήμουν απλώς πελάτης. Ένα μήνα μετά την κυκλοφορία του Cloudflare, έλαβα μια ειδοποίηση ότι ο ιστότοπός μου Το DNS δεν φαίνεται να λειτουργεί. Το Cloudflare έκανε μια αλλαγή σε , και υπήρχε ένα σπασμένο DNS.
Έγραψα αμέσως στον Matthew Prince με τον τίτλο "Where is my DNS?" και μου έστειλε μια μακρά απάντηση γεμάτη τεχνικές λεπτομέρειες (), στο οποίο απάντησα:
Από: John Graham-Cumming
Ημερομηνία: 7 Οκτωβρίου 2010, 9:14
Θέμα: Re: Πού είναι το DNS μου;
Προς: Matthew PrinceΩραία αναφορά, ευχαριστώ. Σίγουρα θα τηλεφωνήσω αν υπάρχουν προβλήματα. Αξίζει πιθανώς να γράψετε μια ανάρτηση σχετικά με αυτό αφού συγκεντρώσετε όλες τις τεχνικές πληροφορίες. Νομίζω ότι ο κόσμος θα απολαύσει μια ανοιχτή και ειλικρινή ιστορία. Ειδικά αν επισυνάψετε γραφήματα σε αυτό για να δείξετε πώς έχει αυξηθεί η επισκεψιμότητα από την κυκλοφορία.
Έχω καλή παρακολούθηση στον ιστότοπό μου και λαμβάνω ένα SMS για κάθε αποτυχία. Η παρακολούθηση δείχνει ότι η αστοχία σημειώθηκε από τις 13:03:07 έως τις 14:04:12. Οι δοκιμές πραγματοποιούνται κάθε πέντε λεπτά.
Είμαι σίγουρος ότι θα το καταλάβεις. Είστε σίγουροι ότι δεν χρειάζεστε το δικό σας άτομο στην Ευρώπη; 🙂
Και εκείνος απάντησε:
Από: Matthew Prince
Ημερομηνία: 7 Οκτωβρίου 2010, 9:57
Θέμα: Re: Πού είναι το DNS μου;
Προς: John Graham-CummingΕυχαριστώ. Απαντήσαμε σε όλους όσους έγραψαν. Είμαι στο δρόμο για το γραφείο τώρα και θα γράψουμε κάτι στο blog ή θα καρφιτσώσουμε μια επίσημη ανάρτηση στον πίνακα ανακοινώσεων μας. Συμφωνώ απόλυτα, η ειλικρίνεια είναι το παν.
Τώρα η Cloudflare είναι μια πραγματικά μεγάλη εταιρεία, εργάζομαι για αυτήν και τώρα πρέπει να γράψω ανοιχτά για το λάθος μας, τις συνέπειές του και τις πράξεις μας.
Εκδηλώσεις 2 Ιουλίου
Στις 2 Ιουλίου παρουσιάσαμε έναν νέο κανόνα στους Managed Rules for WAF, λόγω του οποίου σε κάθε πυρήνα επεξεργαστή που επεξεργάζεται την κυκλοφορία HTTP/HTTPS στο δίκτυο Cloudflare παγκοσμίως. Βελτιώνουμε συνεχώς τους διαχειριζόμενους κανόνες για τα WAF ως απάντηση σε νέα τρωτά σημεία και απειλές. Τον Μάιο, για παράδειγμα, βιάσαμε για προστασία από μια σοβαρή ευπάθεια στο SharePoint. Το όλο νόημα του WAF μας είναι η ικανότητα γρήγορης και παγκόσμιας ανάπτυξης κανόνων.
Δυστυχώς, η ενημέρωση της περασμένης Πέμπτης περιείχε μια κανονική έκφραση που σπαταλούσε πάρα πολλούς πόρους της CPU HTTP/HTTPS για backtracking. Ως αποτέλεσμα, οι βασικές μας λειτουργίες διακομιστή μεσολάβησης, CDN και WAF υπέστησαν βλάβη. Το γράφημα δείχνει ότι οι πόροι επεξεργαστή για την εξυπηρέτηση της κίνησης HTTP/HTTPS φτάνουν σχεδόν το 100% στους διακομιστές του δικτύου μας.
Χρήση CPU σε ένα σημείο παρουσίας κατά τη διάρκεια ενός συμβάντος
Ως αποτέλεσμα, οι πελάτες μας (και οι πελάτες των πελατών μας) κατέληξαν σε μια σελίδα σφάλματος 502 στους τομείς Cloudflare. Δημιουργήθηκαν 502 σφάλματα από διακομιστές ιστού διεπαφής του Cloudflare που είχαν ακόμη ελεύθερους πυρήνες, αλλά δεν μπορούσαν να επικοινωνήσουν με διαδικασίες που χειρίζονται την κυκλοφορία HTTP/HTTPS.
Γνωρίζουμε πόση ταλαιπωρία έχει προκαλέσει αυτό στους πελάτες μας. Ντρεπόμαστε τρομερά. Και αυτή η αποτυχία μας εμπόδισε να αντιμετωπίσουμε αποτελεσματικά το περιστατικό.
Αν ήσασταν ένας από αυτούς τους πελάτες, πιθανότατα ήσουν φοβισμένος, θυμωμένος και αναστατωμένος. Επιπλέον, δεν είχαμε ένα . Η υψηλή κατανάλωση CPU οφειλόταν σε έναν κανόνα WAF με κακή διατύπωση κανονικής έκφρασης που είχε ως αποτέλεσμα υπερβολικό backtracking. Ιδού η ένοχη έκφραση: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Αν και αυτό είναι ενδιαφέρον από μόνο του (και θα μιλήσω για αυτό με περισσότερες λεπτομέρειες παρακάτω), η υπηρεσία Cloudflare ήταν εκτός λειτουργίας για 27 λεπτά όχι μόνο λόγω κακής κανονικής έκφρασης. Μας πήρε λίγο χρόνο για να περιγράψουμε τη σειρά των γεγονότων που οδήγησαν στην αποτυχία, οπότε αργήσαμε να ανταποκριθούμε. Στο τέλος της ανάρτησης, θα περιγράψω το backtracking σε μια κανονική έκφραση και θα σας πω τι να κάνετε με αυτό.
Τι συνέβη
Ας ξεκινήσουμε με τη σειρά. Όλες οι ώρες εδώ είναι σε UTC.
Στις 13:42 μ.μ., ένας μηχανικός στην ομάδα του τείχους προστασίας έκανε μια μικρή αλλαγή στους κανόνες ανίχνευσης χρησιμοποιώντας μια αυτόματη διαδικασία. Κατά συνέπεια, δημιουργήθηκε ένα δελτίο αιτήματος αλλαγής. Διαχειριζόμαστε τέτοια εισιτήρια μέσω του Jira (εικόνα παρακάτω).
Μετά από 3 λεπτά, εμφανίστηκε η πρώτη σελίδα του PagerDuty, αναφέροντας ένα πρόβλημα με το WAF. Αυτό ήταν ένα συνθετικό τεστ που ελέγχει τη λειτουργικότητα των WAF (έχουμε εκατοντάδες από αυτά) εκτός του Cloudflare για την παρακολούθηση της κανονικής λειτουργίας. Ακολούθησαν αμέσως σελίδες ειδοποιήσεων σχετικά με αποτυχία άλλων δοκιμών υπηρεσίας Cloudflare από άκρο σε άκρο, προβλήματα παγκόσμιας κυκλοφορίας, εκτεταμένα σφάλματα 502 και έναν τόνο αναφορών από τα Σημεία Παρουσίας μας (PoP) σε πόλεις σε όλο τον κόσμο που έδειχναν έλλειψη των πόρων της CPU.
Έλαβα αρκετές από αυτές τις ειδοποιήσεις, βγήκα από μια σύσκεψη και πήγαινα στο τραπέζι όταν ο επικεφαλής του τμήματος ανάπτυξης λύσεων είπε ότι είχαμε χάσει το 80% της επισκεψιμότητάς μας. Έτρεξα στους μηχανικούς μας SRE, οι οποίοι εργάζονταν ήδη για το πρόβλημα. Στην αρχή πιστεύαμε ότι ήταν κάποιο είδος άγνωστης επίθεσης.
Οι μηχανικοί του Cloudflare SRE είναι διάσπαρτοι σε όλο τον κόσμο και παρακολουθούν την κατάσταση όλο το εικοσιτετράωρο. Συνήθως, αυτές οι ειδοποιήσεις σάς ειδοποιούν για συγκεκριμένα τοπικά ζητήματα περιορισμένης εμβέλειας, παρακολουθούνται σε εσωτερικούς πίνακες εργαλείων και επιλύονται πολλές φορές την ημέρα. Αλλά αυτές οι σελίδες και οι ειδοποιήσεις έδειχναν κάτι πολύ σοβαρό και οι μηχανικοί της SRE δήλωσαν αμέσως το επίπεδο σοβαρότητας P0 και επικοινώνησαν με τη διοίκηση και τους μηχανικούς συστημάτων.
Οι μηχανικοί μας από το Λονδίνο άκουγαν μια διάλεξη στην κεντρική αίθουσα εκείνη τη στιγμή. Η διάλεξη έπρεπε να διακοπεί, όλοι συγκεντρώθηκαν σε μια μεγάλη αίθουσα συνεδριάσεων και κλήθηκαν περισσότεροι ειδικοί. Αυτό δεν ήταν ένα τυπικό πρόβλημα που μπορούσαν να αντιμετωπίσουν οι SRE. Ήταν επείγουσα η συμμετοχή των κατάλληλων ειδικών.
Στις 14:00 διαπιστώσαμε ότι το πρόβλημα ήταν στο WAF και δεν υπήρξε επίθεση. Η ομάδα απόδοσης τράβηξε τα δεδομένα της CPU και έγινε σαφές ότι το WAF έφταιγε. Ένας άλλος υπάλληλος επιβεβαίωσε αυτή τη θεωρία χρησιμοποιώντας strace. Κάποιος άλλος είδε στα αρχεία καταγραφής ότι υπήρχε πρόβλημα με το WAF. Στις 14:02 μ.μ., ολόκληρη η ομάδα ήρθε σε εμένα όταν προτάθηκε η χρήση του παγκόσμιου kill, ενός μηχανισμού ενσωματωμένου στο Cloudflare που κλείνει ένα στοιχείο σε όλο τον κόσμο.
Το πώς κάναμε παγκόσμιο φονικό για το WAF είναι μια διαφορετική ιστορία. Δεν είναι τόσο απλό. Χρησιμοποιούμε τα δικά μας προϊόντα, και από την υπηρεσία μας δεν λειτούργησε, δεν μπορέσαμε να πραγματοποιήσουμε έλεγχο ταυτότητας και να συνδεθούμε στον εσωτερικό πίνακα ελέγχου (όταν όλα διορθώθηκαν, μάθαμε ότι ορισμένα μέλη της ομάδας είχαν χάσει την πρόσβαση λόγω μιας λειτουργίας ασφαλείας που απενεργοποιεί τα διαπιστευτήρια εάν ο εσωτερικός πίνακας ελέγχου δεν χρησιμοποιείται για πολύς καιρός).
Και δεν μπορέσαμε να φτάσουμε στις εσωτερικές μας υπηρεσίες, όπως το Jira ή το σύστημα κατασκευής. Χρειαζόμασταν έναν μηχανισμό λύσης, τον οποίο χρησιμοποιούσαμε σπάνια (και αυτό θα πρέπει να επιλυθεί). Τελικά, ένας μηχανικός κατάφερε να απενεργοποιήσει το WAF στις 14:07 και στις 14:09, τα επίπεδα κίνησης και CPU επέστρεψαν στο κανονικό παντού. Οι υπόλοιποι μηχανισμοί προστασίας του Cloudflare λειτούργησαν κανονικά.
Στη συνέχεια ξεκινήσαμε την αποκατάσταση του WAF. Η κατάσταση ήταν ασυνήθιστη, οπότε πραγματοποιήσαμε αρνητικά τεστ (αναρωτιόμαστε αν η αλλαγή ήταν πραγματικά το πρόβλημα) και θετικά τεστ (βεβαιωνόμαστε ότι η επαναφορά λειτούργησε) σε μια πόλη χρησιμοποιώντας ξεχωριστή κίνηση, μεταφέροντας πελάτες που πληρώνουν από εκεί.
Στις 14:52 ήμασταν πεπεισμένοι ότι καταλάβαμε τον λόγο και κάναμε μια διόρθωση και ενεργοποιήσαμε ξανά το WAF.
Πώς λειτουργεί το Cloudflare
Το Cloudflare έχει μια ομάδα μηχανικών αφοσιωμένων στη διαχείριση κανόνων για τα WAF. Προσπαθούν να βελτιώσουν τα ποσοστά ανίχνευσης, να μειώσουν τα ψευδώς θετικά στοιχεία και να ανταποκριθούν γρήγορα σε νέες απειλές καθώς εμφανίζονται. Τις τελευταίες 60 ημέρες, 476 αιτήματα αλλαγής υποβλήθηκαν σε επεξεργασία για διαχειριζόμενους κανόνες για το WAF (κατά μέσο όρο ένα κάθε 3 ώρες).
Αυτή η συγκεκριμένη αλλαγή έπρεπε να αναπτυχθεί σε λειτουργία προσομοίωσης, όπου η πραγματική κίνηση πελάτη διέρχεται από τον κανόνα, αλλά τίποτα δεν μπλοκάρεται. Χρησιμοποιούμε αυτήν τη λειτουργία για να ελέγξουμε την αποτελεσματικότητα των κανόνων και να μετρήσουμε τα ψευδώς θετικά και ψευδώς αρνητικά ποσοστά. Αλλά ακόμη και στη λειτουργία προσομοίωσης, οι κανόνες πρέπει να εκτελούνται πραγματικά, και σε αυτήν την περίπτωση ο κανόνας περιείχε μια κανονική έκφραση που κατανάλωνε πάρα πολλούς πόρους επεξεργαστή.
Όπως μπορείτε να δείτε από το παραπάνω αίτημα αλλαγής, έχουμε ένα σχέδιο ανάπτυξης, ένα σχέδιο επαναφοράς και έναν σύνδεσμο προς μια εσωτερική τυπική διαδικασία λειτουργίας (SOP) για αυτόν τον τύπο ανάπτυξης. Το SOP για την αλλαγή ενός κανόνα επιτρέπει τη δημοσίευσή του σε παγκόσμιο επίπεδο. Στην πραγματικότητα, στο Cloudflare, τα πράγματα γίνονται τελείως διαφορετικά και το SOP υπαγορεύει ότι πρώτα αποστέλλουμε το λογισμικό για δοκιμή και εσωτερική χρήση σε ένα εσωτερικό σημείο παρουσίας (PoP) (το οποίο χρησιμοποιούν οι υπάλληλοί μας) και μετά σε έναν μικρό αριθμό πελατών σε μια απομονωμένη τοποθεσία, μετά σε μεγάλο αριθμό πελατών και μόνο τότε σε ολόκληρο τον κόσμο.
Έτσι φαίνεται. Χρησιμοποιούμε το git εσωτερικά μέσω του BitBucket. Οι μηχανικοί που εργάζονται σε αλλαγές υποβάλλουν κώδικα, ο οποίος είναι χτισμένος στο TeamCity, και όταν το build περάσει, ανατίθενται αναθεωρητές. Μόλις εγκριθεί ένα αίτημα έλξης, ο κώδικας συναρμολογείται και εκτελείται μια σειρά δοκιμών (ξανά).
Εάν η κατασκευή και οι δοκιμές ολοκληρωθούν με επιτυχία, δημιουργείται ένα αίτημα αλλαγής στο Jira και ο κατάλληλος διαχειριστής ή επικεφαλής πρέπει να εγκρίνει την αλλαγή. Μετά την έγκριση, η ανάπτυξη λαμβάνει χώρα στο λεγόμενο «θηρατήριο PoP»: DOG, PIG και (σκύλος, γουρούνι και καναρίνι).
Το DOG PoP είναι ένα Cloudflare PoP (όπως κάθε άλλη πόλη μας) που χρησιμοποιείται μόνο από υπαλλήλους του Cloudflare. Το PoP για εσωτερική χρήση σάς επιτρέπει να εντοπίζετε προβλήματα προτού η επισκεψιμότητα των πελατών αρχίσει να ρέει στη λύση. Χρήσιμο πράγμα.
Εάν η δοκιμή DOG είναι επιτυχής, ο κωδικός μετακινείται στο στάδιο PIG (ινδικό χοιρίδιο). Αυτό είναι το Cloudflare PoP, όπου μια μικρή ποσότητα δωρεάν κίνησης πελατών ρέει μέσω νέου κώδικα.
Αν όλα πάνε καλά, ο κωδικός μπαίνει στο Canary. Έχουμε τρία Canary PoPs σε διαφορετικά μέρη του κόσμου. Σε αυτά, η κίνηση των πληρωμένων και δωρεάν πελατών περνά από τον νέο κωδικό και αυτός είναι ο τελευταίος έλεγχος για σφάλματα.
Διαδικασία κυκλοφορίας λογισμικού στο Cloudflare
Εάν ο κωδικός είναι εντάξει στο Canary, τον απελευθερώνουμε. Η διέλευση από όλα τα στάδια - DOG, PIG, Canary, όλος ο κόσμος - διαρκεί αρκετές ώρες ή ημέρες, ανάλογα με την αλλαγή του κωδικού. Λόγω της ποικιλομορφίας του δικτύου και των πελατών του Cloudflare, δοκιμάζουμε διεξοδικά τον κώδικα πριν τον κυκλοφορήσουμε παγκοσμίως σε όλους τους πελάτες. Αλλά το WAF δεν ακολουθεί συγκεκριμένα αυτή τη διαδικασία, επειδή οι απειλές πρέπει να αντιμετωπίζονται γρήγορα.
Απειλές WAF
Τα τελευταία χρόνια, έχει σημειωθεί σημαντική αύξηση των απειλών σε κοινές εφαρμογές. Αυτό οφείλεται στη μεγαλύτερη διαθεσιμότητα εργαλείων δοκιμής λογισμικού. Για παράδειγμα, γράψαμε πρόσφατα για ).
Πηγή:
Πολύ συχνά, δημιουργείται μια απόδειξη ιδέας και δημοσιεύεται αμέσως στο Github, έτσι ώστε οι ομάδες που συντηρούν την εφαρμογή να μπορούν να τη δοκιμάσουν γρήγορα και να διασφαλίσουν ότι είναι επαρκώς ασφαλισμένη. Επομένως, το Cloudflare χρειάζεται τη δυνατότητα να ανταποκρίνεται σε νέες επιθέσεις όσο το δυνατόν γρηγορότερα, ώστε οι πελάτες να έχουν την ευκαιρία να διορθώσουν το λογισμικό τους.
Ένα εξαιρετικό παράδειγμα της γρήγορης απόκρισης του Cloudflare είναι η ανάπτυξη των προστασιών ευπάθειας του SharePoint τον Μάιο (). Σχεδόν αμέσως μετά την έκδοση των ανακοινώσεων, παρατηρήσαμε έναν τεράστιο αριθμό προσπαθειών εκμετάλλευσης της ευπάθειας στις εγκαταστάσεις SharePoint των πελατών μας. Τα παιδιά μας παρακολουθούν συνεχώς νέες απειλές και γράφουν κανόνες για την προστασία των πελατών μας.
Ο κανόνας που προκάλεσε το πρόβλημα την Πέμπτη υποτίθεται ότι προστατεύει από τη δέσμη ενεργειών μεταξύ τοποθεσιών (XSS). Τέτοιες επιθέσεις έχουν γίνει επίσης πολύ πιο συχνές τα τελευταία χρόνια.
Πηγή:
Η τυπική διαδικασία για την αλλαγή ενός διαχειριζόμενου κανόνα για ένα WAF είναι η διεξαγωγή δοκιμών συνεχούς ενοποίησης (CI) πριν από την παγκόσμια ανάπτυξη. Την περασμένη Πέμπτη το κάναμε αυτό και παρουσιάσαμε τους κανόνες. Στις 13:31 μ.μ., ένας μηχανικός υπέβαλε εγκεκριμένο αίτημα έλξης με αλλαγή.
Στις 13:37 το TeamCity συγκέντρωσε τους κανόνες, έκανε δοκιμές και έδωσε το πράσινο φως. Η σουίτα δοκιμών WAF ελέγχει τη βασική λειτουργικότητα του WAF και αποτελείται από μεγάλο αριθμό δοκιμών μονάδων για μεμονωμένες λειτουργίες. Μετά από δοκιμές μονάδας, δοκιμάσαμε τους κανόνες για το WAF χρησιμοποιώντας έναν τεράστιο αριθμό αιτημάτων HTTP. Τα αιτήματα HTTP ελέγχουν ποια αιτήματα πρέπει να αποκλείονται από το WAF (για την αναχαίτιση της επίθεσης) και ποια μπορούν να επιτραπούν (για να μην αποκλειστούν τα πάντα και να αποφευχθούν ψευδώς θετικά). Αλλά δεν κάναμε έλεγχο για υπερβολική χρήση της CPU και η εξέταση των αρχείων καταγραφής προηγούμενων εκδόσεων WAF δείχνει ότι ο χρόνος εκτέλεσης της δοκιμής κανόνων δεν αυξήθηκε και ήταν δύσκολο να υποψιαστεί κανείς ότι δεν θα υπήρχαν αρκετοί πόροι.
Οι δοκιμές πέρασαν και το TeamCity άρχισε αυτόματα να αναπτύσσει την αλλαγή στις 13:42 μ.μ.
Υδράργυρος
Οι κανόνες WAF επικεντρώνονται στην άμεση αποκατάσταση απειλών, επομένως τους αναπτύσσουμε χρησιμοποιώντας τον κατανεμημένο χώρο αποθήκευσης κλειδιού-τιμής του Quicksilver, ο οποίος διαδίδει τις αλλαγές παγκοσμίως σε δευτερόλεπτα. Όλοι οι πελάτες μας χρησιμοποιούν αυτήν την τεχνολογία όταν αλλάζουν τη διαμόρφωση στο ταμπλό ή μέσω του API και χάρη σε αυτήν ανταποκρινόμαστε στις αλλαγές με αστραπιαία ταχύτητα.
Δεν έχουμε μιλήσει πολύ για το Quicksilver. Παλαιότερα χρησιμοποιούσαμε ως ένα παγκόσμιο κατάστημα βασικής αξίας, αλλά υπήρχαν λειτουργικά προβλήματα με αυτό και δημιουργήσαμε το δικό μας κατάστημα, το οποίο αναπαράγεται σε περισσότερες από 180 πόλεις. Τώρα χρησιμοποιούμε το Quicksilver για να προωθήσουμε αλλαγές διαμόρφωσης στους πελάτες, να ενημερώσουμε τους κανόνες WAF και να διανείμουμε κώδικα JavaScript που γράφτηκε από πελάτες στους Cloudflare Workers.
Χρειάζονται μόνο λίγα δευτερόλεπτα από το να κάνετε κλικ σε ένα κουμπί σε έναν πίνακα εργαλείων ή να καλέσετε ένα API μέχρι να κάνετε μια αλλαγή διαμόρφωσης παγκοσμίως. Οι πελάτες λάτρεψαν αυτή την ταχύτητα εγκατάστασης. Και το Workers τους παρέχει σχεδόν στιγμιαία παγκόσμια ανάπτυξη λογισμικού. Κατά μέσο όρο, το Quicksilver διαδίδει περίπου 350 αλλαγές ανά δευτερόλεπτο.
Και το Quicksilver είναι πολύ γρήγορο. Κατά μέσο όρο, πετύχαμε το 99ο εκατοστημόριο των 2,29 δευτερολέπτων για τη διάδοση των αλλαγών σε κάθε υπολογιστή παγκοσμίως. Η ταχύτητα είναι συνήθως καλό πράγμα. Εξάλλου, όταν ενεργοποιείτε μια λειτουργία ή διαγράφετε την προσωρινή μνήμη, αυτό συμβαίνει σχεδόν αμέσως και παντού. Η αποστολή κώδικα μέσω του Cloudflare Workers γίνεται με την ίδια ταχύτητα. Το Cloudflare υπόσχεται στους πελάτες του γρήγορες ενημερώσεις την κατάλληλη στιγμή.
Αλλά σε αυτή την περίπτωση, η ταχύτητα μας έκανε ένα σκληρό αστείο και οι κανόνες άλλαξαν παντού μέσα σε λίγα δευτερόλεπτα. Ίσως έχετε παρατηρήσει ότι ο κωδικός WAF χρησιμοποιεί Lua. Το Cloudflare χρησιμοποιεί το Lua εκτενώς στην παραγωγή και τις λεπτομέρειες εμείς . Χρήσεις Lua WAF εσωτερικά και εφαρμόζει backtracking για αντιστοίχιση. Δεν έχει μηχανισμούς προστασίας από εκφράσεις που ξεφεύγουν από τον έλεγχο. Παρακάτω θα μιλήσω περισσότερα για αυτό και τι κάνουμε γι' αυτό.
Πριν από την ανάπτυξη των κανόνων, όλα πήγαν ομαλά: το αίτημα έλξης δημιουργήθηκε και εγκρίθηκε, ο αγωγός CI/CD συνέλεξε και δοκίμασε τον κώδικα, το αίτημα αλλαγής υποβλήθηκε σύμφωνα με το SOP που διέπει την ανάπτυξη και την επαναφορά και η ανάπτυξη ολοκληρώθηκε.
Διαδικασία ανάπτυξης του Cloudflare WAF
Κάτι πήγε στραβά
Όπως είπα, αναπτύσσουμε δεκάδες νέους κανόνες WAF κάθε εβδομάδα και έχουμε πολλά συστήματα για προστασία από τις αρνητικές συνέπειες μιας τέτοιας ανάπτυξης. Και όταν κάτι πάει στραβά, είναι συνήθως ένας συνδυασμός πολλών περιστάσεων ταυτόχρονα. Αν βρείτε μόνο έναν λόγο, αυτό, φυσικά, είναι καθησυχαστικό, αλλά δεν είναι πάντα αλήθεια. Αυτοί είναι οι λόγοι που μαζί οδήγησαν στην αποτυχία της υπηρεσίας μας HTTP/HTTPS.
- Ένας μηχανικός έγραψε μια κανονική έκφραση που θα μπορούσε να οδηγήσει σε υπερβολική .
- Ένα χαρακτηριστικό που θα μπορούσε να αποτρέψει την κανονική έκφραση από το να σπαταλήσει πολύ CPU αφαιρέθηκε κατά λάθος σε μια ανακατασκευή του WAF αρκετές εβδομάδες νωρίτερα - η αναδιαμόρφωση χρειαζόταν για να καταναλώσει λιγότερους πόρους το WAF.
- Ο κινητήρας κανονικής έκφρασης δεν είχε εγγυήσεις πολυπλοκότητας.
- Η δοκιμαστική σουίτα δεν μπόρεσε να εντοπίσει υπερβολική κατανάλωση CPU.
- Το SOP επιτρέπει την εφαρμογή μη επειγουσών αλλαγών κανόνων παγκοσμίως χωρίς διαδικασία πολλών βημάτων.
- Το σχέδιο επαναφοράς απαιτούσε την εκτέλεση μιας πλήρους κατασκευής WAF δύο φορές, η οποία πήρε πολύ χρόνο.
- Η πρώτη ειδοποίηση για παγκόσμια κυκλοφοριακά προβλήματα ενεργοποιήθηκε πολύ αργά.
- Αργήσαμε να ενημερώσουμε τη σελίδα κατάστασης.
- Είχαμε προβλήματα πρόσβασης στα συστήματα λόγω σφάλματος και η διαδικασία παράκαμψης δεν ήταν καλά καθιερωμένη.
- Οι μηχανικοί SRE έχασαν την πρόσβαση σε ορισμένα συστήματα επειδή τα διαπιστευτήριά τους έληξαν για λόγους ασφαλείας.
- Οι πελάτες μας δεν είχαν πρόσβαση στον πίνακα ελέγχου ή στο API του Cloudflare επειδή περνούν από μια περιοχή Cloudflare.
Τι έχει αλλάξει από την περασμένη Πέμπτη
Πρώτον, σταματήσαμε εντελώς όλες τις εργασίες για εκδόσεις για το WAF και κάνουμε τα εξής:
- Επαναφέρουμε την προστασία από υπερβολική χρήση της CPU που καταργήσαμε. (Ετοιμος)
- Χειροκίνητος έλεγχος και των 3868 κανόνων στους διαχειριζόμενους κανόνες ώστε το WAF να βρει και να διορθώσει άλλες πιθανές περιπτώσεις υπερβολικής οπισθοδρόμησης. (Η επαλήθευση ολοκληρώθηκε)
- Περιλαμβάνουμε προφίλ απόδοσης για όλους τους κανόνες στο σύνολο δοκιμών. (Αναμένεται: 19 Ιουλίου)
- Μετάβαση σε μηχανή κανονικής έκφρασης ή - και τα δύο παρέχουν εγγυήσεις χρόνου εκτέλεσης. (Αναμένεται: 31 Ιουλίου)
- Ξαναγράφουμε το SOP για να αναπτύξουμε κανόνες σταδιακά, όπως άλλο λογισμικό στο Cloudflare, αλλά ταυτόχρονα να έχουμε τη δυνατότητα έκτακτης παγκόσμιας ανάπτυξης εάν οι επιθέσεις έχουν ήδη ξεκινήσει.
- Αναπτύσσουμε τη δυνατότητα να καταργήσουμε επειγόντως τον πίνακα ελέγχου και το API του Cloudflare από την περιοχή του Cloudflare.
- Αυτοματοποίηση ενημερώσεων σελίδας .
Μακροπρόθεσμα απομακρυνόμαστε από το Lua WAF που έγραψα πριν από μερικά χρόνια. Μετακίνηση WAF σε . Με αυτόν τον τρόπο το WAF θα είναι πιο γρήγορο και θα λάβει ένα επιπλέον επίπεδο προστασίας.
Συμπέρασμα
Αυτή η αποτυχία προκάλεσε προβλήματα σε εμάς και τους πελάτες μας. Ενεργήσαμε γρήγορα για να διορθώσουμε την κατάσταση και τώρα εργαζόμαστε για τα ελαττώματα στις διαδικασίες που προκάλεσαν τη συντριβή, καθώς και σκάβουμε ακόμη βαθύτερα για να αποφύγουμε πιθανά προβλήματα με κανονικές εκφράσεις στο μέλλον κατά τη μετάβαση σε νέα τεχνολογία.
Είμαστε πολύ ντροπιασμένοι για αυτή τη διακοπή και ζητάμε συγγνώμη από τους πελάτες μας. Ελπίζουμε ότι αυτές οι αλλαγές θα διασφαλίσουν ότι κάτι τέτοιο δεν θα συμβεί ξανά.
Εφαρμογή. Backtracking κανονικών εκφράσεων
Για να καταλάβετε πώς η έκφραση:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))κατανάλωσε όλους τους πόρους της CPU, πρέπει να γνωρίζετε λίγο πώς λειτουργεί ο τυπικός κινητήρας κανονικής έκφρασης. Το πρόβλημα εδώ είναι το μοτίβο .*(?:.*=.*). (?: και αντίστοιχο ) είναι μια ομάδα που δεν συλλαμβάνει (δηλαδή, η έκφραση σε παρένθεση ομαδοποιείται ως μία έκφραση).
Στο πλαίσιο της υπερβολικής κατανάλωσης CPU, αυτό το μοτίβο μπορεί να περιγραφεί ως .*.*=.*. Σε αυτή τη μορφή, το σχέδιο φαίνεται αδικαιολόγητα περίπλοκο. Αλλά το πιο σημαντικό, στον πραγματικό κόσμο, εκφράσεις (όπως σύνθετες εκφράσεις στους κανόνες WAF) που ζητούν από τον κινητήρα να αντιστοιχίσει ένα θραύσμα ακολουθούμενο από ένα άλλο θραύσμα μπορεί να οδηγήσουν σε καταστροφική οπισθοδρόμηση. Και για αυτο.
Σε κανονική έκφραση . σημαίνει ότι πρέπει να ταιριάξετε έναν χαρακτήρα, .* - αντιστοιχίστε «άπληστα» μηδέν ή περισσότερους χαρακτήρες, δηλαδή καταγράφοντας μέγιστο αριθμό χαρακτήρων, έτσι ώστε .*.*=.* σημαίνει αντιστοίχιση μηδέν ή περισσότερων χαρακτήρων, μετά αντιστοίχιση μηδέν ή περισσότερων χαρακτήρων, εύρεση του κυριολεκτικού = χαρακτήρα, αντιστοίχιση μηδέν ή περισσότερων χαρακτήρων.
Ας πάρουμε τη γραμμή δοκιμής x=x. Αντιστοιχεί στην έκφραση .*.*=.*. .*.* προτού το πρόσημο ίσον ταιριάζει με το πρώτο x (μία από τις ομάδες .* αντιστοιχεί x, και ο δεύτερος - μηδέν χαρακτήρες). .* μετά = οι αγώνες διαρκούν x.
Αυτή η σύγκριση απαιτεί 23 βήματα. Πρώτη ομάδα .* в .*.*=.* ενεργεί άπληστα και ταιριάζει με ολόκληρη τη χορδή x=x. Ο κινητήρας μετακινείται στην επόμενη ομάδα .*. Δεν έχουμε άλλους χαρακτήρες για να ταιριάξουμε, οπότε η δεύτερη ομάδα .* ταιριάζει με μηδέν χαρακτήρες (αυτό επιτρέπεται). Στη συνέχεια ο κινητήρας μετακινείται στην πινακίδα =. Δεν υπάρχουν άλλα σύμβολα (πρώτη ομάδα .* χρησιμοποίησε ολόκληρη την έκφραση x=x), δεν γίνεται σύγκριση.
Και τότε η μηχανή κανονικής έκφρασης επιστρέφει στην αρχή. Περνάει στην πρώτη ομάδα .* και το συγκρίνει с x= (αντί για x=x), και στη συνέχεια αναλαμβάνει τη δεύτερη ομάδα .*. Δεύτερη ομάδα .* συγκρίνεται με το δεύτερο x, και πάλι δεν έχουμε χαρακτήρες. Και όταν ο κινητήρας φτάσει ξανά = в .*.*=.*, τίποτα δεν λειτουργεί. Και κάνει πάλι πίσω.
Αυτή τη φορά η ομάδα .* ακόμα αγώνες x=, αλλά η δεύτερη ομάδα .* ΟΧΙ πια x, και μηδέν χαρακτήρες. Ο κινητήρας προσπαθεί να βρει έναν κυριολεκτικό χαρακτήρα = στο μοτίβο .*.*=.*, αλλά δεν βγαίνει (άλλωστε, η πρώτη ομάδα το έχει ήδη καταλάβει .*). Και κάνει πάλι πίσω.
Αυτή τη φορά η πρώτη ομάδα .* παίρνει μόνο το πρώτο x. Αλλά η δεύτερη ομάδα .* «άπληστα» συλλαμβάνει =x. Έχετε ήδη μαντέψει τι θα συμβεί; Ο κινητήρας προσπαθεί να ταιριάζει με την κυριολεξία =, αποτυγχάνει και κάνει άλλη μια οπισθοδρόμηση.
Η πρώτη ομάδα .* εξακολουθεί να ταιριάζει με το πρώτο x. Δεύτερος .* παίρνει μόνο =. Φυσικά, ο κινητήρας δεν μπορεί να ταιριάζει με την κυριολεξία =, γιατί η δεύτερη ομάδα το έχει ήδη κάνει αυτό .*. Και πάλι πίσω. Και προσπαθούμε να ταιριάξουμε μια σειρά τριών χαρακτήρων!
Ως αποτέλεσμα, η πρώτη ομάδα .* ταιριάζει μόνο με το πρώτο x, δεύτερο .* - με μηδέν χαρακτήρες, και ο κινητήρας τελικά ταιριάζει με την κυριολεξία = στην έκφραση с = στη γραμμή. Ακολουθεί η τελευταία ομάδα .* συγκρίνεται με το τελευταίο x.
23 βήματα μόνο για x=x. Παρακολουθήστε ένα σύντομο βίντεο σχετικά με τη χρήση της Perl , το οποίο δείχνει πώς συμβαίνουν τα βήματα και η αναδρομή.
Αυτό είναι ήδη πολλή δουλειά, αλλά τι θα γινόταν αν αντ' αυτού x=x θα έχουμε x=xx? Αυτά είναι 33 βήματα. Κι αν x=xxx? 45. Η σχέση δεν είναι γραμμική. Το γράφημα δείχνει μια σύγκριση από x=x να x=xxxxxxxxxxxxxxxxxxxx (20 x μετά =). Αν έχουμε 20 x μετά =, ο κινητήρας ολοκληρώνει το ταίριασμα σε 555 βήματα! (Επιπλέον, αν έχουμε χάσει x= και η χορδή αποτελείται απλώς από 20 x, ο κινητήρας θα κάνει 4067 βήματα για να καταλάβει ότι δεν υπάρχουν αντιστοιχίες).
Αυτό το βίντεο δείχνει όλο το backtracking για σύγκριση x=xxxxxxxxxxxxxxxxxxxx:
Το πρόβλημα είναι ότι καθώς αυξάνεται το μέγεθος της συμβολοσειράς, ο χρόνος αντιστοίχισης αυξάνεται υπερ-γραμμικά. Αλλά τα πράγματα μπορούν να γίνουν ακόμη χειρότερα εάν η τυπική έκφραση τροποποιηθεί ελαφρώς. Ας πούμε ότι είχαμε .*.*=.*; (δηλαδή υπήρχε ένα κυριολεκτικό ερωτηματικό στο τέλος του σχεδίου). Για παράδειγμα, για να αντιστοιχίσετε μια έκφραση όπως foo=bar;.
Και εδώ η οπισθοδρόμηση θα ήταν πραγματική καταστροφή. Για σύγκριση x=x θα χρειαστούν 90 βήματα, όχι 23. Και αυτός ο αριθμός αυξάνεται γρήγορα. Να συγκρίνω x= και 20 x, χρειάζονται 5353 βήματα. Εδώ είναι το διάγραμμα. Δείτε τις τιμές των αξόνων Y σε σύγκριση με το προηγούμενο διάγραμμα.
Εάν ενδιαφέρεστε, ρίξτε μια ματιά και στα 5353 αποτυχημένα βήματα αντιστοίχισης x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Με τη χρήση τεμπέλης και όχι άπληστης αντιστοίχισης, μπορεί να ελεγχθεί η έκταση της οπισθοδρόμησης. Αν αλλάξουμε την αρχική έκφραση σε .*?.*?=.*?, για σύγκριση x=x θα χρειαστούν 11 βήματα (όχι 23). Οσον αφορά x=xxxxxxxxxxxxxxxxxxxx. Όλα επειδή ? μετά .* λέει στον κινητήρα να ταιριάζει με έναν ελάχιστο αριθμό χαρακτήρων πριν προχωρήσει.
Αλλά οι τεμπέλικες αντιστοιχίσεις δεν λύνουν πλήρως το πρόβλημα της οπισθοδρόμησης. Αν αντικαταστήσουμε το καταστροφικό παράδειγμα .*.*=.*; επί .*?.*?=.*?;, ο χρόνος εκτέλεσης θα παραμείνει ίδιος. x=x εξακολουθεί να απαιτεί 555 βήματα και x= και 20 x - 5353.
Το μόνο πράγμα που μπορεί να γίνει (εκτός από την πλήρη επανεγγραφή του μοτίβου για μεγαλύτερη εξειδίκευση) είναι να εγκαταλείψουμε τη μηχανή κανονικής έκφρασης με τον μηχανισμό οπισθοδρόμησης. Αυτό θα κάνουμε τις επόμενες εβδομάδες.
Η λύση σε αυτό το πρόβλημα είναι γνωστή από το 1968, όταν ο Kent Thompson έγραψε ένα άρθρο («Μέθοδοι προγραμματισμού: Αλγόριθμος αναζήτησης κανονικών εκφράσεων»). Το άρθρο περιγράφει έναν μηχανισμό που σας επιτρέπει να μετατρέψετε μια κανονική έκφραση σε μη ντετερμινιστικές μηχανές πεπερασμένης κατάστασης και μετά από αλλαγές κατάστασης σε μη ντετερμινιστικές μηχανές πεπερασμένης κατάστασης, χρησιμοποιήστε έναν αλγόριθμο του οποίου ο χρόνος εκτέλεσης εξαρτάται γραμμικά από την αντιστοιχισμένη συμβολοσειρά.
Μέθοδοι Προγραμματισμού
Αλγόριθμος αναζήτησης κανονικών εκφράσεων
Κεν Τόμσον
Bell Telephone Laboratories, Inc., Murray Hill, New JerseyΠεριγράφει μια μέθοδο για την αναζήτηση μιας συγκεκριμένης συμβολοσειράς χαρακτήρων στο κείμενο και συζητά την υλοποίηση αυτής της μεθόδου σε μορφή μεταγλωττιστή. Ο μεταγλωττιστής παίρνει την κανονική έκφραση ως πηγαίο κώδικα και παράγει το πρόγραμμα IBM 7094 ως κώδικα αντικειμένου. Το πρόγραμμα αντικειμένων λαμβάνει είσοδο με τη μορφή κειμένου αναζήτησης και εκπέμπει ένα σήμα κάθε φορά που μια συμβολοσειρά κειμένου αντιστοιχίζεται με μια δεδομένη κανονική έκφραση. Το άρθρο παρέχει παραδείγματα, προβλήματα και λύσεις.
Αλγόριθμος
Προηγούμενοι αλγόριθμοι αναζήτησης κατέληξαν σε backtracking εάν μια μερικώς επιτυχημένη αναζήτηση απέτυχε να παράγει αποτέλεσμα.Στη λειτουργία μεταγλώττισης, ο αλγόριθμος δεν λειτουργεί με σύμβολα. Περνάει οδηγίες στον μεταγλωττισμένο κώδικα. Η εκτέλεση είναι πολύ γρήγορη - αφού περάσει δεδομένα στην κορυφή της τρέχουσας λίστας, αναζητά αυτόματα όλους τους πιθανούς διαδοχικούς χαρακτήρες στην κανονική έκφραση.
Ο αλγόριθμος μεταγλώττισης και αναζήτησης περιλαμβάνεται στο πρόγραμμα επεξεργασίας κειμένου με κοινή χρήση χρόνου ως αναζήτηση με βάση τα συμφραζόμενα. Φυσικά, αυτό απέχει πολύ από τη μοναδική εφαρμογή μιας τέτοιας διαδικασίας αναζήτησης. Για παράδειγμα, μια παραλλαγή αυτού του αλγορίθμου χρησιμοποιείται ως αναζήτηση συμβόλων σε έναν πίνακα στο assembler.
Υποτίθεται ότι ο αναγνώστης είναι εξοικειωμένος με τις κανονικές εκφράσεις και τη γλώσσα προγραμματισμού υπολογιστή IBM 7094.Μεταγλωττιστής
Ο μεταγλωττιστής αποτελείται από τρία στάδια που εκτελούνται παράλληλα. Το πρώτο στάδιο είναι το φιλτράρισμα σύνταξης, το οποίο επιτρέπει να περάσουν μόνο συντακτικά σωστές κανονικές εκφράσεις. Αυτό το βήμα εισάγει επίσης τον τελεστή "·" για να ταιριάζει με κανονικές εκφράσεις. Στο δεύτερο βήμα, η τυπική έκφραση μετατρέπεται σε μορφή postfix. Στο τρίτο στάδιο, δημιουργείται ο κώδικας αντικειμένου. Τα πρώτα 2 στάδια είναι προφανή και δεν θα σταθούμε σε αυτά.
Το άρθρο του Thompson δεν μιλάει για μη ντετερμινιστικές μηχανές πεπερασμένης κατάστασης, αλλά εξηγεί καλά τον αλγόριθμο γραμμικού χρόνου και παρουσιάζει ένα πρόγραμμα ALGOL-60 που δημιουργεί κώδικα γλώσσας συναρμολόγησης για το IBM 7094. Η υλοποίηση είναι δύσκολη, αλλά η ιδέα είναι πολύ απλή.
τρέχουσα διαδρομή αναζήτησης. Αντιπροσωπεύεται από ένα εικονίδιο ⊕ με μία είσοδο και δύο εξόδους.
Το Σχήμα 1 δείχνει τις λειτουργίες του τρίτου βήματος μεταγλώττισης κατά τον μετασχηματισμό ενός παραδείγματος κανονικής έκφρασης. Οι τρεις πρώτοι χαρακτήρες στο παράδειγμα είναι a, b, c και ο καθένας δημιουργεί μια καταχώρηση στοίβας S[i] και ένα πεδίο NNODE.NNODE στον υπάρχοντα κώδικα για τη δημιουργία της προκύπτουσας κανονικής έκφρασης σε μία μόνο καταχώρηση στοίβας (βλ. Εικόνα 5)
Έτσι θα έμοιαζε μια κανονική έκφραση .*.*=.*, αν το φανταστείτε όπως στις εικόνες από το άρθρο του Thompson.
Στο Σχ. 0 υπάρχουν πέντε καταστάσεις που ξεκινούν από το 0 και 3 κύκλοι που ξεκινούν από τις καταστάσεις 1, 2 και 3. Αυτοί οι τρεις κύκλοι αντιστοιχούν σε τρεις .* σε κανονική έκφραση. 3 οβάλ με τελείες αντιστοιχούν σε ένα σύμβολο. Οβάλ με σημάδι = ταιριάζει με κυριολεκτικό χαρακτήρα =. Η κατάσταση 4 είναι τελική. Αν το φτάσουμε, τότε η τυπική έκφραση ταιριάζει.
Για να δείτε πώς ένα τέτοιο διάγραμμα κατάστασης μπορεί να χρησιμοποιηθεί για αντιστοίχιση τυπικών εκφράσεων .*.*=.*, θα εξετάσουμε την αντιστοίχιση συμβολοσειρών x=x. Το πρόγραμμα ξεκινά από την κατάσταση 0, όπως φαίνεται στο Σχ. 1.
Για να λειτουργήσει αυτός ο αλγόριθμος, η μηχανή καταστάσεων πρέπει να βρίσκεται σε πολλές καταστάσεις ταυτόχρονα. Μια μη ντετερμινιστική πεπερασμένη μηχανή θα κάνει όλες τις πιθανές μεταβάσεις ταυτόχρονα.
Πριν προλάβει να διαβάσει τα δεδομένα εισόδου, μεταβαίνει και στις δύο πρώτες καταστάσεις (1 και 2), όπως φαίνεται στο Σχ. 2.
Στο Σχ. Το 2 δείχνει τι συμβαίνει όταν κοιτάζει το πρώτο x в x=x. x μπορεί να χαρτογραφηθεί στο επάνω σημείο, πηγαίνοντας από την κατάσταση 1 και πίσω στην κατάσταση 1. Or x μπορεί να αντιστοιχιστεί στο παρακάτω σημείο, πηγαίνοντας από την κατάσταση 2 και πίσω στην κατάσταση 2.
Μετά την αντιστοίχιση του πρώτου x в x=x είμαστε ακόμα στις καταστάσεις 1 και 2. Δεν μπορούμε να φτάσουμε στην κατάσταση 3 ή 4 γιατί χρειαζόμαστε έναν κυριολεκτικό χαρακτήρα =.
Στη συνέχεια, ο αλγόριθμος εξετάζει = в x=x. Όπως το x πριν από αυτό, μπορεί να αντιστοιχιστεί σε έναν από τους δύο κορυφαίους βρόχους από την κατάσταση 1 στην κατάσταση 1 ή από την κατάσταση 2 στην κατάσταση 2, αλλά ο αλγόριθμος μπορεί να ταιριάζει με την κυριολεξία = και μετακινηθείτε από την κατάσταση 2 στην κατάσταση 3 (και αμέσως 4). Αυτό φαίνεται στο Σχ. 3.
Στη συνέχεια, ο αλγόριθμος προχωρά στον τελευταίο x в x=x. Από τις καταστάσεις 1 και 2 είναι δυνατές οι ίδιες μεταβάσεις πίσω στις καταστάσεις 1 και 2. Από την κατάσταση 3 x μπορεί να ταιριάζει με το σημείο στα δεξιά και να επιστρέψει στην κατάσταση 3.
Σε αυτό το στάδιο, κάθε χαρακτήρας x=x και εφόσον έχουμε φτάσει στην κατάσταση 4, η τυπική έκφραση ταιριάζει με αυτή τη συμβολοσειρά. Κάθε χαρακτήρας υποβάλλεται σε επεξεργασία μία φορά, επομένως αυτός ο αλγόριθμος είναι γραμμικός στο μήκος της συμβολοσειράς εισόδου. Και όχι οπισθοδρόμηση.
Προφανώς, μετά την επίτευξη της κατάστασης 4 (όταν ο αλγόριθμος έχει ταιριάξει x=) αντιστοιχίζεται ολόκληρη η τυπική έκφραση και ο αλγόριθμος μπορεί να τερματιστεί χωρίς να το λάβουμε υπόψη καθόλου x.
Αυτός ο αλγόριθμος εξαρτάται γραμμικά από το μέγεθος της συμβολοσειράς εισόδου.
Πηγή: www.habr.com