Neredeyse 9 yıl önce Cloudflare küçük bir şirketti ve ben onun için çalışmadım, sadece bir müşteriydim. Cloudflare'i başlattıktan bir ay sonra web sitemin DNS çalışmıyor gibi görünüyor. Cloudflare bir değişiklik yaptı ve bozuk bir DNS vardı.
Hemen Matthew Prince'e "DNS'im nerede?" başlığıyla yazdım, o da teknik ayrıntılarla dolu uzun bir yanıt gönderdi (), buna cevap verdim:
Gönderen: John Graham-Cumming
Tarih: 7 Ekim 2010, 9:14
Konu: Yanıt: DNS'im nerede?
Kime: Matthew PrinceHarika bir rapor, teşekkürler. Bir sorun olursa mutlaka arayacağım. Tüm teknik bilgileri topladıktan sonra muhtemelen bu konuda bir yazı yazmaya değer. İnsanların açık ve dürüst bir hikayeden keyif alacağını düşünüyorum. Özellikle trafiğin lansmandan bu yana nasıl büyüdüğünü gösteren grafikler eklerseniz.
Sitemde iyi bir izleme sistemi var ve her başarısızlıkla ilgili bir SMS alıyorum. İzleme, arızanın 13:03:07 ile 14:04:12 arasında meydana geldiğini gösteriyor. Testler her beş dakikada bir yapılıyor.
Eminim çözeceksin. Avrupa'da kendinize ihtiyacınız olmadığından emin misiniz? 🙂
Ve cevapladı:
Gönderen: Matthew Prince
Tarih: 7 Ekim 2010, 9:57
Konu: Yanıt: DNS'im nerede?
Kime: John Graham-CummingTeşekkür ederim. Yazan herkese cevap verdik. Şu anda ofise gidiyorum ve bloga bir şeyler yazacağız ya da ilan panomuza resmi bir gönderi asacağız. Tamamen katılıyorum, dürüstlük her şeydir.
Artık Cloudflare gerçekten büyük bir şirket, onun için çalışıyorum ve artık hatamız, sonuçları ve eylemlerimiz hakkında açıkça yazmam gerekiyor.
2 Temmuz Olayları
2 Temmuz'da WAF'lar için Yönetilen Kurallar'da yeni bir kuralı kullanıma sunduk. Dünya çapında Cloudflare ağında HTTP/HTTPS trafiğini işleyen her işlemci çekirdeğinde. Yeni güvenlik açıklarına ve tehditlere yanıt olarak WAF'lara yönelik yönetilen kuralları sürekli olarak geliştiriyoruz. Örneğin Mayıs ayında acele ettik SharePoint'teki ciddi bir güvenlik açığına karşı koruma sağlamak için. WAF'ımızın asıl amacı, kuralları hızlı ve küresel olarak dağıtma yeteneğidir.
Ne yazık ki, geçen Perşembe günkü güncelleme, geri izlemede çok fazla HTTP/HTTPS CPU kaynağını boşa harcayan bir düzenli ifade içeriyordu. Bunun sonucunda temel proxy, CDN ve WAF işlevlerimiz zarar gördü. Grafik, HTTP/HTTPS trafiğini sunmaya yönelik işlemci kaynaklarının ağımızdaki sunucularda neredeyse %100'e ulaştığını göstermektedir.
Bir olay sırasında bir noktada CPU kullanımı
Sonuç olarak, müşterilerimiz (ve müşterilerimizin müşterileri) Cloudflare etki alanlarında 502 hata sayfasıyla karşılaştı. 502 hataları, hâlâ boş çekirdeğe sahip olan ancak HTTP/HTTPS trafiğini işleyen işlemlerle iletişim kuramayan Cloudflare ön uç web sunucuları tarafından oluşturuldu.
Bu durumun müşterilerimize ne kadar sıkıntı yaşattığını biliyoruz. Çok utanıyoruz. Ve bu başarısızlık olayla etkili bir şekilde ilgilenmemizi engelledi.
Eğer siz de bu müşterilerden biriyseniz muhtemelen korkmuş, öfkelenmiş ve üzülmüşsünüzdür. Üstelik hiç sahip olmadık . Yüksek CPU tüketimi, aşırı geri izlemeye neden olan, kötü ifade edilmiş bir düzenli ifadeye sahip bir WAF kuralından kaynaklanıyordu. İşte suçlu ifadesi: (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))
Bu başlı başına ilginç olsa da (aşağıda bundan daha ayrıntılı olarak bahsedeceğim), Cloudflare hizmeti yalnızca kötü bir düzenli ifade nedeniyle 27 dakika süreyle kapalı kaldı. Başarısızlığa yol açan olayların sırasını tanımlamamız biraz zaman aldı, bu yüzden tepki vermekte yavaş davrandık. Yazının sonunda geri izlemeyi düzenli bir ifadeyle anlatacağım ve bununla ne yapacağınızı anlatacağım.
Ne oldu
Sırayla başlayalım. Buradaki tüm zamanlar UTC'ye göredir.
Öğleden sonra 13:42'de güvenlik duvarı ekibindeki bir mühendis, algılama kurallarında küçük bir değişiklik yaptı Otomatik bir işlem kullanarak. Buna göre değişiklik talebi bileti oluşturuldu. Bu tür biletleri Jira aracılığıyla yönetiyoruz (ekran görüntüsü aşağıdadır).
3 dakika sonra PagerDuty'nin WAF ile ilgili bir sorun bildiren ilk sayfası göründü. Bu, normal çalışmayı izlemek için Cloudflare dışındaki WAF'ların (yüzlerce taneye sahibiz) işlevselliğini test eden sentetik bir testti. Bunu hemen diğer Cloudflare uçtan uca hizmet testlerinin başarısız olduğu, küresel trafik sorunları, yaygın 502 hataları ve dünyanın dört bir yanındaki şehirlerdeki Varlık Noktalarımızdan (PoP) gelen bir eksiklik olduğunu belirten tonlarca rapor hakkında sayfalarca uyarı izledi. CPU kaynakları.
Bu uyarılardan birkaçını aldım, toplantıdan fırladım ve masaya doğru giderken çözüm geliştirme departmanımızın başkanı trafiğimizin %80'ini kaybettiğimizi söyledi. Sorun üzerinde zaten çalışmakta olan SRE mühendislerimize koştum. İlk başta bunun bilinmeyen bir saldırı olduğunu düşündük.
Cloudflare SRE mühendisleri dünyanın dört bir yanına dağılmış durumda ve durumu günün her saatinde izliyor. Tipik olarak bu uyarılar, kapsamı sınırlı olan belirli yerel sorunlar hakkında sizi bilgilendirir, dahili kontrol panellerinde takip edilir ve günde birden çok kez çözümlenir. Ancak bu sayfalar ve bildirimler gerçekten ciddi bir şeye işaret ediyordu ve SRE mühendisleri derhal P0 önem düzeyini ilan ederek yönetim ve sistem mühendisleriyle temasa geçti.
Londralı mühendislerimiz o anda ana salonda bir dersi dinliyorlardı. Dersin yarıda kesilmesi gerekti, herkes büyük bir konferans salonunda toplandı ve daha fazla uzman çağrıldı. Bu, SRE'lerin kendi başlarına çözebilecekleri tipik bir sorun değildi. Doğru uzmanların dahil edilmesi acildi.
Saat 14:00'te sorunun WAF'ta olduğunu ve herhangi bir saldırının olmadığını tespit ettik. Performans ekibi CPU verilerini çekti ve WAF'ın suçlu olduğu ortaya çıktı. Başka bir çalışan bu teoriyi strace kullanarak doğruladı. Başka biri günlüklerde WAF ile ilgili bir sorun olduğunu gördü. Öğleden sonra 14:02'de, Cloudflare'de yerleşik olarak dünya çapında bir bileşeni kapatan bir mekanizma olan global kill'in kullanılması önerildiğinde tüm ekip bana geldi.
WAF için küresel katliamı nasıl yaptığımız farklı bir hikaye. O kadar kolay değil. Kendi ürünlerimizi kullanıyoruz ve hizmet verdiğimizden beri işe yaramadı, dahili kontrol panelinde kimlik doğrulaması yapamadık ve oturum açamadık (her şey düzeltildiğinde, dahili kontrol panelinin belirli bir süre kullanılmaması durumunda kimlik bilgilerini devre dışı bırakan bir güvenlik özelliği nedeniyle bazı ekip üyelerinin erişimi kaybettiğini öğrendik) uzun zaman).
Jira veya derleme sistemi gibi dahili hizmetlerimize de ulaşamadık. Nadiren kullandığımız bir geçici çözüm mekanizmasına ihtiyacımız vardı (bunun da çözülmesi gerekecek). Sonunda bir mühendis 14:07'de WAF'ı devre dışı bırakmayı başardı ve 14:09'da trafik ve CPU seviyeleri her yerde normale döndü. Cloudflare'in koruma mekanizmalarının geri kalanı normal şekilde çalıştı.
Daha sonra WAF'ı geri yüklemeye başladık. Durum olağandışıydı, bu yüzden bir şehirde ayrı trafiği kullanarak, ödeme yapan müşterileri oradan aktararak negatif testler (değişikliğin gerçekten sorun olup olmadığını kendimize sorarak) ve pozitif testler (geri almanın işe yaradığından emin olmak) gerçekleştirdik.
Saat 14:52'de sebebini anladığımıza ikna olup düzeltme yaptık ve WAF'ı tekrar etkinleştirdik.
Cloudflare nasıl çalışır?
Cloudflare, WAF'lara yönelik kuralları yönetmeye adanmış bir mühendis ekibine sahiptir. Tespit oranlarını iyileştirmeye, yanlış pozitifleri azaltmaya ve ortaya çıkan yeni tehditlere hızlı bir şekilde yanıt vermeye çalışıyorlar. Son 60 gün içinde, WAF için yönetilen kurallar için 476 değişiklik talebi işlendi (ortalama her 3 saatte bir).
Bu özel değişikliğin, gerçek istemci trafiğinin kuraldan geçtiği ancak hiçbir şeyin engellenmediği simülasyon modunda uygulanması gerekiyordu. Bu modu kuralların etkinliğini test etmek ve yanlış pozitif ve yanlış negatif oranlarını ölçmek için kullanırız. Ancak simülasyon modunda bile kuralların gerçekten yürütülmesi gerekiyor ve bu durumda kural, çok fazla işlemci kaynağı tüketen bir düzenli ifade içeriyordu.
Yukarıdaki değişiklik talebinde görebileceğiniz gibi, bu tür bir dağıtım için bir dağıtım planımız, bir geri alma planımız ve dahili standart işletim prosedürüne (SOP) bir bağlantımız var. Bir kuralın değiştirilmesine ilişkin SOP, bunun küresel olarak yayınlanmasına olanak tanır. Aslında Cloudflare'de işler tamamen farklı yapılıyor ve SOP, yazılımı önce test etmek ve dahili kullanım için dahili bir varlık noktasına (PoP) (çalışanlarımızın kullandığı) ve ardından az sayıda müşteriye göndermemizi zorunlu kılıyor. izole bir konuma, daha sonra çok sayıda müşteriye ve ancak o zaman tüm dünyaya.
Görünüşe göre bu. Git'i dahili olarak BitBucket aracılığıyla kullanıyoruz. Değişiklikler üzerinde çalışan mühendisler, TeamCity'ye oluşturulan kodu gönderir ve derleme başarılı olduğunda gözden geçirenler atanır. Bir çekme isteği onaylandıktan sonra kod birleştirilir ve bir dizi test (tekrar) çalıştırılır.
Derleme ve testler başarıyla tamamlanırsa Jira'da bir değişiklik isteği oluşturulur ve ilgili yöneticinin veya liderin değişikliği onaylaması gerekir. Onayın ardından dağıtım, "PoP menagerie" olarak adlandırılan alanda gerçekleşir: DOG, PIG ve (köpek, domuz ve kanarya).
DOG PoP, yalnızca Cloudflare çalışanları tarafından kullanılan bir Cloudflare PoP'tur (diğer şehirlerimiz gibi). Dahili kullanıma yönelik PoP, müşteri trafiği çözüme akmaya başlamadan önce sorunları yakalamanıza olanak tanır. Kullanışlı şey.
DOG testi başarılı olursa kod PIG (kobay) aşamasına geçer. Bu, az miktarda ücretsiz müşteri trafiğinin yeni kod aracılığıyla aktığı Cloudflare PoP'tur.
Her şey yolundaysa kod Kanarya'ya gider. Dünyanın farklı yerlerinde üç Canary PoP'umuz var. Bunlarda ücretli ve ücretsiz müşterilerin trafiği yeni koddan geçiyor ve bu, hataların son kontrolüdür.
Cloudflare'de Yazılım Yayın Süreci
Eğer kod Kanarya'da uygunsa yayınlıyoruz. Tüm aşamaları geçmek - KÖPEK, DOMUZ, Kanarya, tüm dünya - kod değişikliğine bağlı olarak birkaç saat veya gün sürer. Cloudflare ağının ve istemcilerinin çeşitliliği nedeniyle, kodu küresel olarak tüm istemcilere yayınlamadan önce kapsamlı bir şekilde test ediyoruz. Ancak WAF bu süreci özel olarak takip etmiyor çünkü tehditlere hızlı bir şekilde yanıt verilmesi gerekiyor.
WAF tehditleri
Geçtiğimiz birkaç yılda yaygın uygulamalardaki tehditlerde önemli bir artış yaşandı. Bunun nedeni yazılım test araçlarının daha fazla kullanılabilirliğidir. Örneğin, yakın zamanda şunu yazdık: ).
Kaynak:
Çoğu zaman, bir kavram kanıtı oluşturulur ve Github'da hemen yayınlanır, böylece uygulamanın bakımını yapan ekipler bunu hızlı bir şekilde test edebilir ve yeterince güvenli olduğundan emin olabilir. Bu nedenle Cloudflare'in, müşterilerin yazılımlarını düzeltme fırsatına sahip olabilmesi için yeni saldırılara mümkün olduğunca hızlı yanıt verme yeteneğine ihtiyacı var.
Cloudflare'in hızlı tepkisinin harika bir örneği, SharePoint güvenlik açığı korumalarının Mayıs ayında devreye alınmasıdır (). Duyuruların hemen ardından, müşterilerimizin SharePoint kurulumlarındaki güvenlik açığından yararlanmaya yönelik çok sayıda girişimde bulunulduğunu fark ettik. Adamlarımız müşterilerimizi korumak için sürekli olarak yeni tehditleri izliyor ve kurallar yazıyor.
Perşembe günü soruna neden olan kuralın siteler arası komut dosyası çalıştırmaya (XSS) karşı koruma sağlaması gerekiyordu. Bu tür saldırılar son yıllarda çok daha sık hale geldi.
Kaynak:
WAF için yönetilen bir kuralı değiştirmeye yönelik standart prosedür, küresel dağıtımdan önce sürekli entegrasyon (CI) testi gerçekleştirmektir. Geçen perşembe bunu yaptık ve kuralları açıkladık. Öğleden sonra 13'de bir mühendis, değişiklikle birlikte onaylanmış bir çekme talebi sundu.
13:37'de TeamCity kuralları topladı, testler yaptı ve devam etti. WAF test paketi, WAF'ın temel işlevselliğini test eder ve bireysel işlevler için çok sayıda birim testinden oluşur. Birim testlerinin ardından WAF kurallarını çok sayıda HTTP isteği kullanarak test ettik. HTTP istekleri, hangi isteklerin WAF tarafından engellenmesi gerektiğini (saldırıya müdahale etmek için) ve hangilerine izin verilebileceğini (her şeyi engellememek ve yanlış pozitifleri önlemek için) kontrol eder. Ancak aşırı CPU kullanımını test etmedik ve önceki WAF yapılarının günlüklerini incelemek, kural testi yürütme süresinin artmadığını ve yeterli kaynak olmayacağından şüphelenmenin zor olduğunu gösteriyor.
Testler geçti ve TeamCity saat 13:42'de değişikliği otomatik olarak uygulamaya başladı.
Civa
WAF kuralları, tehditlerin anında giderilmesine odaklanır; bu nedenle bunları, değişiklikleri saniyeler içinde küresel olarak yayan Quicksilver'ın dağıtılmış anahtar/değer deposunu kullanarak dağıtırız. Tüm müşterilerimiz, kontrol panelindeki veya API aracılığıyla yapılandırmayı değiştirdiklerinde bu teknolojiyi kullanıyor ve bu teknoloji sayesinde değişikliklere ışık hızıyla yanıt veriyoruz.
Quicksilver hakkında pek konuşmadık. Daha önce kullanıyorduk küresel olarak dağıtılmış bir anahtar/değer mağazası olarak, ancak operasyonel sorunlar vardı ve 180'den fazla şehirde kopyalanan kendi mağazamızı yazdık. Artık istemcilere yapılandırma değişikliklerini iletmek, WAF kurallarını güncellemek ve istemciler tarafından yazılan JavaScript kodunu Cloudflare Çalışanlarına dağıtmak için Quicksilver'ı kullanıyoruz.
Kontrol panelindeki bir düğmeyi tıklatmaktan veya bir API'yi çağırmaktan dünya çapında bir yapılandırma değişikliği yapmak yalnızca birkaç saniye sürer. Müşteriler bu kurulum hızını sevdiler. Ve Workers onlara neredeyse anında küresel yazılım dağıtımı sağlıyor. Quicksilver ortalama olarak saniyede yaklaşık 350 değişiklik yayar.
Ve Quicksilver çok hızlıdır. Değişiklikleri dünya çapındaki her bilgisayara yaymak için ortalama olarak 99 saniyelik 2,29'uncu yüzdelik dilime ulaştık. Hız genellikle iyi bir şeydir. Sonuçta, bir işlevi etkinleştirdiğinizde veya önbelleği temizlediğinizde, bu neredeyse anında ve her yerde gerçekleşir. Cloudflare Workers aracılığıyla kod göndermek aynı hızda gerçekleşir. Cloudflare, müşterilerine doğru zamanda hızlı güncelleme sözü veriyor.
Ancak bu durumda hız bize acımasız bir şaka yaptı ve kurallar her yerde birkaç saniye içinde değişti. WAF kodunun Lua kullandığını fark etmiş olabilirsiniz. Cloudflare, Lua'yı üretimde ve ayrıntılarda yoğun bir şekilde kullanıyor biz . Lua WAF'ın kullanım alanları dahili olarak ve eşleştirme için geri izleme uygular. Kontrolden çıkan ifadelere karşı koruma sağlayacak mekanizmaları yoktur. Aşağıda bu konudan ve bu konuda neler yaptığımızdan daha fazla bahsedeceğim.
Kurallar dağıtılmadan önce her şey sorunsuz ilerledi: çekme isteği oluşturuldu ve onaylandı, CI/CD kanalı kodu toplayıp test etti, değişiklik isteği dağıtım ve geri almayı yöneten SOP'ye göre gönderildi ve dağıtım tamamlandı.
Cloudflare WAF Dağıtım Süreci
Neyin yanlış gitti
Söylediğim gibi, her hafta düzinelerce yeni WAF kuralı uyguluyoruz ve bu tür bir dağıtımın olumsuz sonuçlarına karşı korunmak için birçok sistemimiz mevcut. Ve bir şeyler ters gittiğinde, bu genellikle aynı anda birkaç koşulun birleşiminden kaynaklanır. Tek bir neden bulursanız, bu elbette güven vericidir, ancak her zaman doğru değildir. HTTP/HTTPS hizmetimizin başarısız olmasına yol açan nedenler bunlardır.
- Bir mühendis aşırı ifadeye yol açabilecek bir düzenli ifade yazdı. .
- Düzenli ifadenin çok fazla CPU israfını engelleyebilecek bir özellik, birkaç hafta önce WAF'ın yeniden düzenlenmesi sırasında yanlışlıkla kaldırıldı; WAF'ın daha az kaynak tüketmesini sağlamak için yeniden düzenlemeye ihtiyaç vardı.
- Düzenli ifade motorunun karmaşıklık garantisi yoktu.
- Test paketi aşırı CPU tüketimini tespit edemedi.
- SOP, acil olmayan kural değişikliklerinin çok adımlı bir süreç olmadan küresel olarak uygulanmasına olanak tanır.
- Geri alma planı, tam WAF yapısının iki kez çalıştırılmasını gerektiriyordu ve bu da uzun zaman alıyordu.
- Küresel trafik sorunlarına ilişkin ilk uyarı çok geç tetiklendi.
- Durum sayfasını güncellememiz biraz zaman aldı.
- Bir aksaklık nedeniyle sistemlere erişimde sorun yaşadık ve baypas prosedürü tam olarak oluşturulmamıştı.
- SRE mühendisleri, güvenlik nedeniyle kimlik bilgilerinin süresinin dolması nedeniyle bazı sistemlere erişimi kaybetti.
- Müşterilerimiz Cloudflare bölgesinden geçtikleri için Cloudflare kontrol paneline veya API'ye erişimleri yoktu.
Geçen perşembeden beri ne değişti
İlk olarak, WAF sürümleri üzerindeki tüm çalışmalarımızı tamamen durdurduk ve şunları yapıyoruz:
- Kaldırdığımız CPU aşırı kullanım korumasını yeniden sunuyoruz. (Hazır)
- WAF'ın diğer potansiyel aşırı geri izleme durumlarını bulup düzeltmesi için yönetilen kurallardaki 3868 kuralın tamamını manuel olarak kontrol ediyoruz. (Doğrulama tamamlandı)
- Test setindeki tüm kurallar için performans profilini dahil ediyoruz. (Beklenen: 19 Temmuz)
- Normal ifade motoruna geçiş veya - her ikisi de çalışma zamanı garantisi sağlar. (Beklenen: 31 Temmuz)
- Cloudflare'deki diğer yazılımlar gibi kuralları aşamalı olarak dağıtmak için SOP'yi yeniden yazıyoruz, ancak aynı zamanda saldırılar zaten başlamışsa acil küresel dağıtım yapma yeteneğine de sahibiz.
- Cloudflare kontrol panelini ve API'sini Cloudflare bölgesinden acilen kaldırma yeteneğini geliştiriyoruz.
- Sayfa güncellemelerini otomatikleştirme .
Uzun vadede, birkaç yıl önce yazdığım Lua WAF'tan uzaklaşıyoruz. WAF'ı şuraya taşıma: . Bu şekilde WAF daha hızlı olacak ve ek bir koruma düzeyi elde edecektir.
Sonuç
Bu başarısızlık bizi ve müşterilerimizi sıkıntıya soktu. Durumu düzeltmek için hızlı bir şekilde harekete geçtik ve şu anda çökmeye neden olan süreçlerdeki kusurlar üzerinde çalışıyoruz ve gelecekte yeni teknolojiye geçiş yaparken düzenli ifadelerle ilgili olası sorunlara karşı koruma sağlamak için daha da derinlere iniyoruz.
Bu kesintiden dolayı çok üzgünüz ve müşterilerimizden özür dileriz. Bu değişikliklerin benzer bir şeyin bir daha yaşanmamasını sağlayacağını umuyoruz.
Başvuru. Düzenli ifadeleri geriye doğru izleme
İfadenin nasıl olduğunu anlamak için:
(?:(?:"|'|]|}||d
(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-
|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*)))Tüm CPU kaynaklarını tükettiğinizde, standart düzenli ifade motorunun nasıl çalıştığı hakkında biraz bilgi sahibi olmanız gerekir. Buradaki sorun kalıptır .*(?:.*=.*). (?: ve karşılık gelen ) yakalamayan bir gruptur (yani parantez içindeki ifade tek bir ifade olarak gruplandırılmıştır).
Aşırı CPU tüketimi bağlamında bu model şu şekilde tanımlanabilir: .*.*=.*. Bu formda desen gereksiz derecede karmaşık görünüyor. Ancak daha da önemlisi, gerçek dünyada, motordan bir parçayı ve ardından başka bir parçayı eşleştirmesini isteyen ifadeler (WAF kurallarındaki karmaşık ifadeler gibi), felaketle sonuçlanan geri izlemeye yol açabilir. Ve bu yüzden.
Düzenli ifadede . bir karakterle eşleşmeniz gerektiği anlamına gelir, .* - sıfır veya daha fazla karakteri "açgözlülükle" eşleştirin, yani maksimum sayıda karakter yakalayın, böylece .*.*=.* sıfır veya daha fazla karakterle eşleşmesi, ardından sıfır veya daha fazla karakterle eşleştirilmesi, değişmez = karakterinin bulunması, sıfır veya daha fazla karakterle eşleştirilmesi anlamına gelir.
Hadi test hattını ele alalım x=x. Bu ifadeye karşılık gelir .*.*=.*. .*.* Eşittir işareti ilkiyle eşleşmeden önce x (gruplardan biri .* maçlar xve ikinci - sıfır karakterler). .* sonra = son maçlar x.
Bu karşılaştırma 23 adım gerektirir. İlk grup .* в .*.*=.* açgözlülükle davranır ve dizenin tamamıyla eşleşir x=x. Motor bir sonraki gruba geçer .*. Eşleşecek başka karakterimiz kalmadığından ikinci grup .* sıfır karakterle eşleşir (buna izin verilir). Daha sonra motor tabelaya doğru hareket eder =. Başka sembol yok (ilk grup .* ifadenin tamamını kullandı x=x), hiçbir karşılaştırma yapılmaz.
Daha sonra düzenli ifade motoru başlangıca geri döner. İlk gruba geçiyor .* ve karşılaştırır с x= (yerine x=x) ve ardından ikinci grubu ele alır .*. İkinci grup .* ikinciyle karşılaştırılır xve yine hiç karakterimiz kalmadı. Ve motor tekrar ulaştığında = в .*.*=.*, hiç birşey çalışmıyor. Ve yine geri adım atıyor.
Bu kez grup .* hala eşleşiyor x=ama ikinci grup .* daha fazla yok xve sıfır karakter. Motor gerçek bir karakter bulmaya çalışıyor = desende .*.*=.*, ama çıkmıyor (sonuçta, ilk grup onu zaten işgal etti) .*). Ve yine geri adım atıyor.
Bu sefer ilk grup .* yalnızca ilk x'i alır. Ama ikinci grup .* "açgözlülükle" yakalar =x. Ne olacağını zaten tahmin ettiniz mi? Motor gerçekle eşleşmeye çalışıyor =başarısız olur ve başka bir geri izleme yapar.
İlk grup .* hala ilkiyle eşleşiyor x... İkinci .* sadece alır =. Tabii ki, motor gerçekle eşleşemez =, çünkü ikinci grup bunu zaten yaptı .*. Ve yine geri adım atılıyor. Ve üç karakterden oluşan bir diziyi eşleştirmeye çalışıyoruz!
Sonuç olarak birinci grup .* yalnızca ilkiyle eşleşir xikinci .* - sıfır karakterle ve motor sonunda gerçekle eşleşiyor = ifadede с = Çizgide. Sıradaki son grup .* sonuncuyla karşılaştırıldı x.
Yalnızca 23 adım x=x. Perl kullanımı hakkında kısa bir video izleyin adımların ve geri izlemenin nasıl gerçekleştiğini gösterir.
Bu zaten çok fazla iş, ama ya bunun yerine x=x sahip olacağız x=xx? Bu 33 adımdır. Ve eğer x=xxx? 45. İlişki doğrusal değildir. Grafikte bir karşılaştırma gösterilmektedir: x=x karşı x=xxxxxxxxxxxxxxxxxxxx (20 x sonra =). Eğer sonrasında 20 x varsa =motor eşleştirmeyi 555 adımda tamamlıyor! (Ayrıca eğer kaybedersek x= ve dize sadece 20'den oluşuyor x, motor eşleşme olmadığını anlamak için 4067 adım atacaktır).
Bu video karşılaştırma için tüm geri izlemeyi gösterir x=xxxxxxxxxxxxxxxxxxxx:
Buradaki sorun, dize boyutu arttıkça eşleştirme süresinin süper doğrusal bir şekilde artmasıdır. Ancak normal ifade biraz değiştirilirse işler daha da kötüleşebilir. Diyelim ki vardı .*.*=.*; (yani, desenin sonunda gerçek bir noktalı virgül vardı). Örneğin, şöyle bir ifadeyi eşleştirmek için foo=bar;.
Ve burada geri adım atmak gerçek bir felaket olur. Karşılaştırma için x=x 90 değil 23 adım atılacak. Ve bu sayı hızla artıyor. Karşılaştırmak x= ve 20 x, 5353 adım gerekiyor. İşte grafik. Eksen değerlerine bakın Y önceki grafikle karşılaştırıldığında.
İlgileniyorsanız 5353 başarısız eşleştirme adımının tümüne göz atın x=xxxxxxxxxxxxxxxxxxxx и .*.*=.*;
Açgözlü eşleştirme yerine tembel eşleştirme kullanılarak, geri izlemenin boyutu kontrol edilebilir. Orijinal ifadeyi şu şekilde değiştirirsek .*?.*?=.*?, Karşılaştırma için x=x 11 adım sürecektir (23 değil). gelince x=xxxxxxxxxxxxxxxxxxxx... Hepsi Çünkü ? sonra .* motora, devam etmeden önce minimum sayıda karakterle eşleşmesini söyler.
Ancak tembel haritalamalar geri izleme sorununu tamamen çözmez. Felaket örneğini değiştirirsek .*.*=.*; üzerinde .*?.*?=.*?;yürütme süresi aynı kalacaktır. x=x hala 555 adım gerektiriyor ve x= ve 20 x - 5353.
Yapılabilecek tek şey (daha spesifik olmak için modeli tamamen yeniden yazmanın yanı sıra), geri izleme mekanizmasıyla birlikte düzenli ifade motorunu terk etmektir. Önümüzdeki birkaç hafta içinde yapacağımız şey budur.
Bu sorunun çözümü Kent Thompson'ın 1968'de yazdığı makaleden beri biliniyor. (“Programlama Yöntemleri: Normal İfade Arama Algoritması”). Makalede, düzenli bir ifadeyi deterministik olmayan sonlu durum makinelerine dönüştürmenize ve deterministik olmayan sonlu durum makinelerindeki durum değişikliklerinden sonra yürütme süresi eşleşen dizeye doğrusal olarak bağlı olan bir algoritma kullanmanıza olanak tanıyan bir mekanizma açıklanmaktadır.
Programlama Yöntemleri
Normal İfade Arama Algoritması
Ken Thompson
Bell Telefon Laboratuvarları, Inc., Murray Hill, New JerseyMetinde belirli bir karakter dizisinin aranmasına yönelik bir yöntemi açıklar ve bu yöntemin derleyici biçiminde uygulanmasını tartışır. Derleyici, düzenli ifadeyi kaynak kodu olarak alır ve nesne kodu olarak IBM 7094 programını üretir. Nesne programı, girdiyi arama metni biçiminde alır ve bir metin dizisi belirli bir düzenli ifadeyle her eşleştirildiğinde bir sinyal yayar. Makalede örnekler, sorunlar ve çözümler sunulmaktadır.
Algoritma
Önceki arama algoritmaları, kısmen başarılı bir aramanın sonuç üretememesi durumunda geriye doğru izlemeyle sonuçlanıyordu.Derleme modunda algoritma sembollerle çalışmaz. Talimatları derlenmiş koda iletir. Yürütme çok hızlıdır; verileri geçerli listenin en üstüne aktardıktan sonra, normal ifadedeki olası tüm ardışık karakterleri otomatik olarak arar.
Derleme ve arama algoritması, zaman paylaşımlı metin düzenleyicide bağlamsal arama olarak bulunur. Elbette bu, böyle bir arama prosedürünün tek uygulamasından çok uzaktır. Örneğin, bu algoritmanın bir çeşidi, assembler'daki bir tabloda sembol araması olarak kullanılır.
Okuyucunun düzenli ifadelere ve IBM 7094 bilgisayar programlama diline aşina olduğu varsayılmaktadır.Derleyici
Derleyici paralel çalışan üç aşamadan oluşur. İlk aşama, yalnızca sözdizimsel olarak doğru düzenli ifadelerin geçmesine izin veren sözdizimi filtrelemesidir. Bu adım aynı zamanda normal ifadelerle eşleşmesi için "·" operatörünü de ekler. İkinci adımda düzenli ifade postfix formuna dönüştürülür. Üçüncü aşamada nesne kodu oluşturulur. İlk 2 aşama bellidir, üzerinde durmayacağız.
Thompson'ın makalesi deterministik olmayan sonlu durum makinelerinden bahsetmiyor ancak doğrusal zaman algoritmasını iyi açıklıyor ve IBM 60 için montaj dili kodu üreten bir ALGOL-7094 programını sunuyor. Uygulaması çetrefilli ama fikir çok basit.
geçerli arama yolu. Bir giriş ve iki çıkışa sahip bir ⊕ simgesiyle temsil edilir.
Şekil 1, bir normal ifade örneğini dönüştürürken üçüncü derleme adımının işlevlerini göstermektedir. Örnekteki ilk üç karakter a, b, c'dir ve her biri bir yığın girişi S[i] ve bir NNODE alanı oluşturur.Ortaya çıkan normal ifadeyi tek bir yığın girişinde oluşturmak için NNODE'u mevcut koda bağlayın (bkz. Şekil 5)
Normal bir ifade böyle görünecektir .*.*=.*Thompson'ın makalesindeki resimlerdeki gibi hayal ederseniz.
İncirde. 0'dan başlayan beş durum ve 0, 3 ve 1 durumlarından başlayan 2 döngü vardır. Bu üç döngü üçe karşılık gelir .* düzenli bir ifadede. Noktalı 3 oval bir sembole karşılık gelir. İşaretli oval = gerçek bir karakterle eşleşir =. Durum 4 nihaidir. Eğer buna ulaşırsak, normal ifade eşleştirilir.
Böyle bir durum diyagramının düzenli ifade eşleştirmesi için nasıl kullanılabileceğini görmek .*.*=.*, dize eşleşmesine bakacağız x=x. Program, Şekil 0'de gösterildiği gibi 1 durumundan başlar. XNUMX.
Bu algoritmanın çalışması için durum makinesinin aynı anda birden fazla durumda olması gerekir. Deterministik olmayan sonlu bir makine mümkün olan tüm geçişleri aynı anda gerçekleştirecektir.
Giriş verilerini okumaya zaman bulamadan, Şekil 1'de gösterildiği gibi her iki birinci duruma (2 ve 2) gider. XNUMX.
İncirde. 2, ilkine baktığında ne olacağını gösteriyor x в x=x. x durum 1'den durum 1'e giderek en üst noktayı eşleyebilir. Veya x Durum 2'den durum 2'ye giderek aşağıdaki noktayı haritalandırabilirsiniz.
İlkini eşleştirdikten sonra x в x=x hala 1. ve 2. durumdayız. 3. veya 4. duruma ulaşamıyoruz çünkü değişmez bir karaktere ihtiyacımız var =.
Algoritma daha sonra şunları dikkate alır: = в x=x. Kendisinden önceki x gibi, durum 1'den durum 1'e veya durum 2'den durum 2'ye kadar en üstteki iki döngüden biriyle eşleştirilebilir, ancak algoritma değişmez değerle eşleşebilir = ve durum 2'den durum 3'e (ve hemen 4'e) geçin. Bu, şekilde gösterilmiştir. 3.
Algoritma daha sonra sonuncuya geçer. x в x=x. Durum 1 ve 2'den durum 1 ve 2'ye aynı geçişler mümkündür. Durum 3'ten x sağdaki noktayla eşleşip durum 3'e geri dönebilir.
Bu aşamada her karakter x=x dikkate alınır ve 4. duruma ulaştığımızdan beri düzenli ifade bu dizeyle eşleşir. Her karakter bir kez işlenir, dolayısıyla bu algoritma giriş dizesinin uzunluğu boyunca doğrusaldır. Ve geri dönüş yok.
Açıkçası, 4. duruma ulaştıktan sonra (algoritma eşleştiğinde) x=) normal ifadenin tamamı eşleştirilir ve algoritma bunu hiç dikkate almadan sonlandırabilir x.
Bu algoritma giriş dizesinin boyutuna doğrusal olarak bağlıdır.
Kaynak: habr.com