正規表現再入門/introduction-to-regex

ɹ!shin1x1 2016//03 PHPΧϯϑΝϨϯε ਖ਼نදݱ࠶ೖ໳

ৄࡉਖ਼نදݱ ਖ਼نදݱٕज़ೖ໳

D .BTBTIJ4IJOCBSB!TIJOY "HFOEB w1)1ͷਖ਼نදݱ wϚονϯά wόοΫτϥοΫ w3F%P4

1)1ͷਖ਼نදݱ

1)1ͷਖ਼نදݱ D .BTBTIJ4IJOCBSB!TIJOY w1$3&  QSFHܥ w104*9ਖ਼نදݱ  FSFHܥʢ1)1Ͱඇਪ঑ɺͰഇࢭʣ wَं  NC@FSFHܥ

ਖ਼نදݱͷओͳར༻༻్ D .BTBTIJ4IJOCBSB!TIJOY wจࣈྻ͕Ϛον͢Δ͔Ͳ͏͔ͷ൑ผ wจࣈྻ͔ΒϚονͨ͠Օॴͷऔಘ wจࣈྻͷϚονͨ͠ՕॴΛஔ׵ wϚονͨ͠ՕॴͰจࣈྻΛ෼ׂ

ਖ਼نදݱͷओͳར༻༻్ D .BTBTIJ4IJOCBSB!TIJOY wϚον͢Δ͔Ͳ͏͔ͷ൑ผ wϚονͨ͠Օॴͷऔಘ  QSFH@NBUDI QSFH@NBUDI@BMM QSFH@HSFQ wϚονͨ͠Օॴͷஔ׵ 
QSFH@SFQMBDF QSFH@pMUFS wϚονͨ͠ՕॴͰจࣈྻΛ෼ׂ  QSFH@TQMJU

Ϛονϯά

Ϛονϯάͷಛ௃ D .BTBTIJ4IJOCBSB!TIJOY wਖ਼نදݱ͸ؤுΓ԰ w࠷ॳʹϚονͨ͠΋ͷ͕༏ઌ wඪ४ͷྔࢦఆࢠ͸ཉுΓʢHSFFEZʣ

Ϛονϯάͷಛ௃ D .BTBTIJ4IJOCBSB!TIJOY wਖ਼نදݱ͸ؤுΓ԰ w࠷ॳʹϚονͨ͠΋ͷ͕༏ઌ wඪ४ͷྔࢦఆࢠ͸ཉுΓʢHSFFEZʣ ࠷௕࠷ࠨϚονϯά

ਖ਼نදݱ͸ؤுΓ԰ D .BTBTIJ4IJOCBSB!TIJOY wϚον͢Δ·ͰऔΓಘΔશͯͷύλʔϯΛࢼߦ  Ϛον͢Ε͹ऴྃ wऔΓಘΔશͯͷύλʔϯ͕Ϛον͠ͳ͍  Ϛονࣦഊ wϚονࣦഊͷ৔߹ɺॲཧྔ͕๲େʹͳΔՄೳੑ

B aE aE ΛͰϚον

B aE ͱB͸Ϛον͠ͳ͍

B aE aE ΛͰϚον όοΫτϥοΫ

B aE ͱ͸Ϛον͠ͳ͍

B aE จࣈྻΛਐΊͯ  aE ΛͰϚον

B aE ͱB͸Ϛον͠ͳ͍

B aE จࣈྻΛਐΊΔͱ  aE ͕Ϛον͢Δ΋ͷ͕ແ͍ Ϛονࣦഊ

࠷ॳʹϚονͨ͠΋ͷ͕༏ઌ D .BTBTIJ4IJOCBSB!TIJOY wจࣈྻ಺Ͱ࠷΋ࠨʹ͋ΔϚον͕༏ઌ  ʢ࠷ॳʹϚονͨ͠Օॴʣ wਖ਼نදݱʢબ୒ʣͷฒͼͰ͸ͳ͍

1FO1JOFBQQMF"QQMF1FO

1FO1JOFBQQMF"QQMF1FO ?1FO Ϛον͢Δ

1FO1JOFBQQMF"QQMF1FO 1FO 1FO1JOFBQQMF"QQMF1FO

1FO1JOFBQQMF"QQMF1FO 1FO จࣈྻͷࠨଆͰϚονͨ͠΋ͷ͕༏ઌ ʢ্ͷύλʔϯͰऴྃʣ 1FO1JOFBQQMF"QQMF1FO

1FO1JOFBQQMF"QQMF1FO "QQMFc1FO

1FO1JOFBQQMF"QQMF1FO "QQMFc1FO 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO

1FO1JOFBQQMF"QQMF1FO "QQMFc1FO 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO จࣈྻͷࠨଆͰϚονͨ͠΋ͷ͕༏ઌ

ඪ४ͷྔࢦఆࢠ͸ཉுΓ D .BTBTIJ4IJOCBSB!TIJOY wඪ४ͷྔࢦఆࢠ͸ɺ࠷௕ʹϚον wσϑΥϧτͰ͸࠷େྔࢦఆࢠͱͯ͠ಈ͘

ྔࢦఆࢠ D .BTBTIJ4IJOCBSB!TIJOY w௚લͷύλʔϯͷ܁Γฦ͠Λࣔ͢ w ɺ ɺ ɺ\O N^ wB
ͳΒʮBʯʮBBCʯʮDBBBBCʯͳͲʹϚον

1FO1JOFBQQMF"QQMF1FO 1 O ճҎ্

1FO1JOFBQQMF"QQMF1FO 1 O 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO

1FO1JOFBQQMF"QQMF1FO 1 O ඪ४ͷྔࢦఆࢠ͸࠷௕ͰϚον

1FO1JOFBQQMF"QQMF1FO 1 O ճҎ্

1FO1JOFBQQMF"QQMF1FO 1 O ΋͘͠͸ճ 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO

1\ ^O ճҎ্ճҎԼ 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO

1\ ^O 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO 1FO1JOFBQQMF"QQMF1FO ճҎ্ճҎԼ

ྔࢦఆࢠͷϚονϯάύλʔϯ D .BTBTIJ4IJOCBSB!TIJOY w࠷େྔࢦఆࢠʢσϑΥϧτʣ w࠷খྔࢦఆࢠ wઈର࠷େྔࢦఆࢠ

࠷େྔࢦఆࢠ D .BTBTIJ4IJOCBSB!TIJOY wྔࢦఆࢠσϑΥϧτͷಈ͖ w \O N^ w࠷௕ʹϚονɺཉுΓͳϚον

࠷খྔࢦఆࢠ D .BTBTIJ4IJOCBSB!TIJOY wྔࢦఆࢠʹ Λ෇͚ͯࢦఆ w ɺ ɺ ɺ\O N^
w࠷খͷϚονɺ߇͑ΊͳϚον

1FO1JOFBQQMF"QQMF1FO 1 O ࠷௕ͰϚον

1FO1JOFBQQMF"QQMF1FO 1 O ࠷୹ͰϚον

GPPBOECBS GPPΛϚον͍ͨ͠

࠷େྔࢦఆࢠ GPPBOECBS

<?> Ҏ֎ͷ܁Γฦ͠ GPPBOECBS

࠷খྔࢦఆࢠ GPPBOECBS

࠷େྔࢦఆࢠͱ࠷খྔࢦఆࢠ D .BTBTIJ4IJOCBSB!TIJOY w࠷େྔࢦఆࢠ࠷௕Ұக͔Βࢼߦ͍ͯ͘͠ w࠷খྔࢦఆࢠ࠷୹Ұக͔Βࢼߦ͍ͯ͘͠ wϚον͠ͳ͍৔߹ͲͪΒ΋ಉ͡ࢼߦΛߦ͏

ઈର࠷େྔࢦఆࢠ D .BTBTIJ4IJOCBSB!TIJOY wྔࢦఆࢠʹ Λ෇͚ͯࢦఆ w ɺ ɺ ɺ\O N^
wڧཉͳϚονɺఘΊͳ͍Ϛον

1FO1JOFBQQMF"QQMF1FO 1 O Ϛονࣦഊ

όοΫτϥοΫ

όοΫτϥοΫ D .BTBTIJ4IJOCBSB!TIJOY wϚον͕ࣦഊͨ͠৔߹ʹ  લͷਖ਼نදݱʹ໭ΓɺผͷϚονΛߦ͏ wਖ਼͍͠ղΛಘΔ·ͰՄೳͳ૊Έ߹ΘͤΛ  ޮ཰తʹࢼ͍ͯ͘͠ https://ja.wikipedia.org/wiki/όοΫτϥοΩϯά

1FO1JOFBQQMF"QQMF1FO 1 O Ϛον͢Δ

1FO1JOFBQQMF"QQMF1FO 1 O Oͱߦ຤ͳͷͰ Ϛον͠ͳ͍

1FO1JOFBQQMF"QQMF1FO 1 O จࣈ୹ͯ͘͠Ϛον όοΫτϥοΫ

1FO1JOFBQQMF"QQMF1FO 1 O Ϛον੒ޭ

1FO1JOFBQQMF"QQMF1FO 1 O Ϛον͢Δ

1FO1JOFBQQMF"QQMF1FO 1 O Ϛον͢Δ Ϛονͨ͠ൣғΛΞτϛοΫʹѻ͏

1FO1JOFBQQMF"QQMF1FO 1 O ͰϚονͨ͠Օॴͷ࠶୳ࠪ͸ߦΘͣɺ ਖ਼نදݱΛ1͔ΒϚον͠௚͢

1FO1JOFBQQMF"QQMF1FO 1 O Ϛονࣦഊ

ઈର࠷େྔࢦఆࢠ D .BTBTIJ4IJOCBSB!TIJOY wҰ౓Ϛονϯάͨ͠ൣғΛΞτϛοΫʹѻ͍ɺ  όοΫτϥοΫͰख์͞ͳ͍ wΞτϛοΫάϧʔϓͰ΋ಉ༷ͷޮՌ  Ͱ΋ಉ༷ͷޮՌ wόοΫτϥοΫൃੜ਺Λ཈͑Δ

SFHVMBSFYQSFTTJPOT D .BTBTIJ4IJOCBSB!TIJOY https://regex101.com/

όοΫτϥοΫʹΑΔ %P4

http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016

w4UBDL0WFSqPXͰ෼ؒΞΫηεෆೳ wจࣈྻલޙͷۭനΛ࡟আ͢Δਖ਼نදݱ w?<aTaVD> c<aTaVD> w ͷۭന ຤ඌ͸ۭനҎ֎

ݕূ D .BTBTIJ4IJOCBSB!TIJOY wQSFH@SFQMBDF 1)1 w୯७Խͯ͠ɺaT ͱaT Ͱݕূ w/ݸͷۭന
`B`ʹରͯ͠ॲཧ

/TQBDFT B 1)1 1)1 NT NT NT
NT NT NT NT NT QSFH@SFQMBDF aT

/TQBDFT B 1)1 1)1 NT NT NT
NT NT NT NT  aT ൺ NT aT ൺ QSFH@SFQMBDF aT

ରԠࡦ D .BTBTIJ4IJOCBSB!TIJOY wઈର࠷େྔࢦఆࢠͰόοΫτϥοΫΛ཈੍ wจࣈྻ௕ΛόϦσʔγϣϯͰ੍ݶ wਖ਼نදݱΛ࢖Θͳ͍  4UBDL0WFSqPXͰͷରԠ  จࣈྻؔ਺Ͱஔ׵͑

3F%P4 D .BTBTIJ4IJOCBSB!TIJOY wਖ਼نදݱΛѱ༻ͨ͠%P4 w೥͔Β໰୊ఏى͞Ε͍ͯͨ wϚον͠ͳ͍ύλʔϯͰ߈ܸ https://www.checkmarx.com/wp-content/uploads/2015/03/ReDoS-Attacks.pdf

https://www.checkmarx.com/wp-content/uploads/2015/03/ReDoS-Attacks.pdf

&WJM3FHFY1BUUFSOT D .BTBTIJ4IJOCBSB!TIJOY w B w <B[";> w
BcBB w BcB w B \Y^cGPSY

BBBBBBBBBBBBBBBBBBB9 B

TUFQT ࢀߟ յ໓తͳόοΫτϥοΫ B BBBBBBBBBBBBBBBBBBB9

&WJM3FHFY1BUUFSOT D .BTBTIJ4IJOCBSB!TIJOY wΘ͔ͣจࣈͷจࣈྻͰ΋  ૊Έ߹Θͤരൃ͕ى͜Δ wྔࢦఆࢠͷೖΕࢠɺબ୒ͱྔࢦఆࢠͷೖΕࢠ

1)1Ͱ࣮ߦ D .BTBTIJ4IJOCBSB!TIJOY preg_match('/(a+)+$/', 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaX'); 1)1 1)1 QSFH@NBUDI NT NT
଎͍ʂʂʂ

όοΫτϥοΫ੍ݶ D .BTBTIJ4IJOCBSB!TIJOY wઃఆʹΑΔόοΫτϥοΫ੍ݶ  QDSFCBDLUSBDL@MJNJUʢσϑΥϧτ͸ ʣ w্ݶʹୡ͢ΔͱΤϥʔͰऴྃ wQSFH@NBUDI ͷ໭Γ஋͕GBMTF 
ΤϥʔΛࣔ͢ wQSFH@MBTU@FSSPS ͰΤϥʔίʔυऔಘ

1)1Ͱ࣮ߦ D .BTBTIJ4IJOCBSB!TIJOY <?php  preg_match('/(a+)+$/', 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaX', $m);    $error =
preg_last_error();  if ($error === PREG_BACKTRACK_LIMIT_ERROR) {  echo 'backtrack limit error', PHP_EOL;  } else if ($error > 0) {  echo 'other error', PHP_EOL;  } $ php redos.php backtrack limit error

1)1Ͱ࣮ߦʢ੍ݶ֎͠ʣ D .BTBTIJ4IJOCBSB!TIJOY ini_set('pcre.backtrack_limit', 10000000000); preg_match('/(a+)+$/', 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaX'); 1)1 1)1 QSFH@NBUDI
NT NT ͕͔͔࣌ؒΔ

$47ͷύʔε D .BTBTIJ4IJOCBSB!TIJOY wਖ਼نදݱͰ࣮૷ w1P$ͳ$47Λύʔε͢Δͱ  4FHNFOUBUJPO'BVMUʢ1)1ʣ wHPPECZDTWͰॻ͖௚ͯ͠ରԠ

·ͱΊ

·ͱΊ D .BTBTIJ4IJOCBSB!TIJOY wϚονϯάͷྲྀΕ wύϑΥʔϚϯε΁ͷӨڹ wਖ਼نදݱΛ͋͑ͯ࢖Θͳ͍બ୒ࢶ

ࢀߟ D .BTBTIJ4IJOCBSB!TIJOY w4UBDL&YDIBOHF͕߈ܸ͞Εͨ3F%P4ͷޮՌcZPIHBLJTCMPH  IUUQTCMPHPIHBLJOFUTUBDLFYDIBOHFSFEPTBUUBDL w3F%P4ͷճආcZPIHBLJTCMPH  IUUQTCMPHPIHBLJOFUBWPJEJOHSFEPT

D .BTBTIJ4IJOCBSB!TIJOY !TIJOY !TIJOY D .BTBTIJ4IJOCBSB!TIJOY

正規表現再入門/introduction-to-regex

正規表現再入門/introduction-to-regex

More Decks by shin1x1

Other Decks in Programming

Featured

Transcript