正規表現の脆弱性 (ReDoS) を JavaScript で学ぶ
先日、このようなツイートを書いたところ、かなりの反響がありました。 JavaScript の正規表現の脆弱性の例でいうと、例えば /\s+$/ は脆弱性があると言える console.time(); /\s+$/.test(" ".repeat(65536) + "a"); console.timeEnd(); 結構時間がかかるのがわかる。でも /\s+$/ を見て「これは危険だな」と理解出来る人はそんなにいない。JavaScript に限らないけれど。 — Takuo Kihira (@tkihira) February 17, 2022 これは一般に ReDoS (Regular expression Denial of Service) と呼ばれる脆弱性です。正確に理解するのが難しい脆弱性なので、少し解説してみたいと思います。 結論 長い記事になるので、最初に「とりあえずこれだけ知っ
Regexp::AssembleのGo実装 rassemble-go を作りました - プログラムモグモグ
PerlにはRegexp::Assembleという便利なライブラリがあります。 複数の正規表現を受け取り、それらのいずれかにマッチする正規表現を構築するためのライブラリです。 my $ra = Regexp::Assemble->new; $ra->add( 'ab+c' ); $ra->add( 'ab+\\d*\\s+c' ); $ra->add( 'a\\w+\\d+' ); $ra->add( 'a\\d+' ); print $ra->re; # prints (?:a(?:b+(?:\d*\s+)?c|(?:\w+)?\d+)) このライブラリのGo実装を金曜日の夜から書き始めて、ようやく形になってきたので公開しました。 package main import ( "fmt" "log" "github.com/itchyny/rassemble-go" ) func main
Regular Expression Matching with a Trigram Index or How Google Code Search Worked
Regular Expression Matching with a Trigram Index or How Google Code Search Worked Russ Cox rsc@swtch.com January 2012 Introduction In the summer of 2006, I was lucky enough to be an intern at Google. At the time, Google had an internal tool called gsearch that acted as if it ran grep over all the files in the Google source tree and printed the results. Of course, that implementation would be fairl
Implementing Regular Expressions
Implementing Regular Expressions Russ Cox rsc@swtch.com This page collects resources about implementing regular expression search efficiently. Articles and Notes “Regular Expression Matching Can Be Simple And Fast” An introduction to using finite automata to implement regular expression matching, and why the standard backtracking implementation is a bad idea. Supporting programs: NFA | DFA | bound
Regex that only matches itself
There are some pretty cool challenges out there involving regex (Self-matching regex, Regex validating regex) This may well be impossible, but is there a regex that will ONLY match itself? NOTE, delimiters must be included: for example /thing/ must match /thing/ and not thing. The only match possible for your expression must be the expression itself. Many languages allow the implementation of a st
正規表現に潜む対称性 〜等式公理による等価性判定〜
The document discusses regular expressions and finite automata. It begins by defining regular expressions using operations like concatenation, sum, and star. It then discusses how to interpret regular expressions by defining the language they represent. The document goes on to discuss how finite automata can also represent languages and how regular expressions and automata are equivalent based on
RegExr: Learn, Build, & Test RegEx
RegExr is an online tool to learn, build, & test Regular Expressions (RegEx / RegExp). Supports JavaScript & PHP/PCRE RegEx. Results update in real-time as you type. Roll over a match or expression for details. Validate patterns with suites of Tests. Save & share expressions with others. Use Tools to explore your results. Full RegEx Reference with help & examples. Undo & Redo with {{getCtrlKey()}}
http://swatmac.info/?p=942
See related links to what you are looking for.
Regex Tester – RegexPal
RegexPal is a tool to learn, build, & test Regular Expressions (RegEx / RegExp). Results update in real-time as you type. Roll over a match or expression for details. Save & share expressions with others. Explore the Library for help & examples. Undo & Redo with {{getCtrlKey()}}-Z / Y. Search for & rate Community patterns.
この機会にマスターしようぜ、正規表現、構文図、オートマトン - 檜山正幸のキマイラ飼育記 (はてなBlog)
正規表現と構文図について解説します。オートマトンについても詳しく述べます。オートマトン・スゴロクで遊びましょう！ 世間でよく知られている／使われている概念・方法にはこだわらず、僕（檜山）の感覚で一番わかりやすいと思われる筋書きと用語法／図式法を使って説明します。この記事に目を通して“感じ”が掴めたら、形式言語理論の教科書を読み始めることが出来るでしょう。 [追記]この記事の内容に対する具体例は、「正規表現とオートマトン：なんだ簡単じゃん、JavaScriptによる実装」にあります。[/追記] 内容： 正規表現 正規表現の例 構文図 基本記号 連接 選択 省略可能 繰り返し ストレートワイヤーによるレイアウト調整 有限状態オートマトン 有限状態オートマトンの実行 バックトラックと先読み スゴロクとオートマトン コマをたくさん使うスゴロクと並列処理 非決定性オートマトンと決定性オートマトン 正
Regular Expression Matching Can Be Simple And Fast
Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) Russ Cox rsc@swtch.com January 2007 Introduction This is a tale of two approaches to regular expression matching. One of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep.
関数型的正規表現マッチ - Preferred Networks Research & Development
最近ローソンでお菓子をたくさん買った田中です。 近頃読んで面白かった論文を紹介したいと思います。 A Play on Regular Expression 今年のICFPでFunctional Pearlとして発表されたものです。ICFP（International Conference on Functional Programming）というのは、関数プログラミングに関する国際学会で、Functional Pearlというのは、エレガントでためになる、関数プログラミングのテクニック集です。 この論文ではまず、正規表現マッチャを関数型言語(Haskell)でいかにエレガントに記述できるかが示されます。それから、エレガントさを保ったままの線形時間実装へ改良し、その実装がC++によるプロフェッショナルな実装(具体的にはGoogle re2)に匹敵するパフォーマンスを示すことが示されます。さら
gkbr.me
このドメインを購入する。 gkbr.me 2018 Copyright. All Rights Reserved. The Sponsored Listings displayed above are served automatically by a third party. Neither the service provider nor the domain owner maintain any relationship with the advertisers. In case of trademark issues please contact the domain owner directly (contact information can be found in whois). Privacy Policy
Implementing Regular Expressions
Implementing Regular Expressions Russ Cox rsc@swtch.com This page collects resources about implementing regular expression search efficiently. Articles and Notes “Regular Expression Matching Can Be Simple And Fast” An introduction to using finite automata to implement regular expression matching, and why the standard backtracking implementation is a bad idea. Supporting programs: NFA | DFA | bound
kamolog » Blog Archive » 正規表現の先読み・後読み構文
正規表現には"先読み"や"後読み"という構文がある．これらの構文を利用すると，マッチする対象となる文字列の直前・直後の文字列をマッチの条件として指定することができる．以下に簡単な説明と例を挙げる． 肯定先読み 構文 「(?=X)」という構文で記述する．Xは任意の正規表現． 意味 Xにマッチする文字列の最初の位置にある検索文字列にマッチする． 例 「\d+(?=円)」という例で考える．正規表現「\d+」は1回以上の数字の繰り返しである．「(?=円)」は肯定先読みで，「円」にマッチする文字列の最初の位置にある検索文字列にマッチする．これらを組み合わせて「1回以上の数字の繰り返し，ただし直後に「円」にマッチする文字列がある」と読むとわかりやすい． この正規表現に対しては「1円」や「100円以上」の数字部分がマッチする．「1」や「1ほげ」や「円1」はマッチしない． 否定先読み 構文 「(?!
後方参照の直後に他の数字が続くような置換パターン - m2
2011/08/11 追記 このエントリで紹介した Opera11 の挙動は Opera12 の開発版で修正されたようです。 これも私が報告しました。発見したのは miya2000 さんだったと思います。 alert("123456789X".replace(/(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)/, '$010')); これで本来は10と出るはずがXと出てました。 http://orera.g.hatena.ne.jp/edvakf/20110809/1312910857 - "123456789X".replace(/(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)/, '$10'); みたいな置換をしたときに、「'X'」(10番目として解釈)になってほしいのか「'10'」(1番目+'0')になってほしいのかわからないよね、と言う話。 JavaScr
What the JavaScript RegExp API Got Wrong, & How to Fix It
Over the last few years, I've occasionally commented on JavaScript's RegExp API, syntax, and behavior on the ES-Discuss mailing list. Recently, JavaScript inventor Brendan Eich suggested that, in order to get more discussion going, I write up a list of regex changes to consider for future ECMAScript standards (or as he humorously put it, have my "95 [regex] theses nailed to the ES3 cathedral door"
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Regex Fractals
正規表現入門 星の高さを求めて
RegExp playground