20日目: 正規表現が ReDoS 脆弱になる 3 つの経験則
はじめに 皆さんこんにちは．3回生のらん（@hoshina350）です． 文字列マッチングに便利な正規表現ですが，テキトーに書くと脆弱になり得るという情報を耳にしてから色々と原因や対策を調べていました． しかし，多くの記事で紹介されていた対策方法は，「独自の正規表現を使用しないー」とか「 * や + などの繰り返し表現はなるべく使わないー」とかいう なんともふわっとしたものでした．これでは「いやぁ確かにそうなんかもしれんけど…そうゆう訳にはいかんやんか…」と納得できません． つまり，「本質的に何が問題」で，「具体的にどんな特徴のある正規表現が脆弱になり得るのか」を知りたい訳です． そこで，様々な文献を調査してみました．本記事では調査して溜まった知見を紹介していきます． 本記事は， Purdue大学のJames Davis教授による “The Regular Expression Denia
Censys Search
Services: 2.3B IPv4 Hosts: 214.5M IPv6 Hosts: 53.5M Virtual Hosts: 586.9M
An additional non-backtracking RegExp engine · V8
Show navigation Starting with v8.8, V8 ships with a new experimental non-backtracking RegExp engine (in addition to the existing Irregexp engine) which guarantees execution in linear time with respect to the size of the subject string. The experimental engine is available behind the feature flags mentioned below. Runtime of /(a*)*b/.exec('a'.repeat(n)) for n ≤ 100Here’s how you can configure the n
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
A New RegExp Engine in SpiderMonkey – Mozilla Hacks - the Web developer blog
Background: RegExps in SpiderMonkey Regular expressions – commonly known as RegExps – are a powerful tool in JavaScript for manipulating strings. They provide a rich syntax to describe and capture character information. They’re also heavily used, so it’s important for SpiderMonkey (the JavaScript engine in Firefox) to optimize them well. Over the years, we’ve had several approaches to RegExps. Con
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
TypeScriptの正規表現にマシな型をつける - Qiita
let str = "x\\yz"; let t = str.replace(/\\(.)/, (m, s) => s.toUpperCase()); // s は any 型なので、仮に s.toUpper() と書いてもエラーにならない TypeScript は静的型がウリの言語なので、もうちょっとやりようはあるのではないか。 目標：型付き正規表現 これらの問題を解決するために、キャプチャーの型の情報を埋め込んだ型 TypedRegExp<captures> を作りたい。キャプチャーの型とは、具体的には string: 通常のキャプチャー string | undefined: 後ろに ? や * がついたもの、あるいは | の一方に含まれるもの undefined: 否定先読み (?! .. ) に含まれるキャプチャー のいずれかである。例えば、 /(a)(b)?/ という正規表現の
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - rbuckton/proposal-regexp-features: Proposal to investigate additional language features for ECMAScript Regular Expressions
Regular Expression Feature Comparisons
GitHub - l4yton/RegHex: A collection of regexes for every possbile use
GitHub - RunDevelopment/eslint-plugin-clean-regex: An ESLint plugin for writing better regular expressions.
Release v4.4.0 · slevithan/xregexp
GitHub - mathiasbynens/emoji-regex: A regular expression to match all Emoji-only symbols as per the Unicode Standard.
i Hate Regex - The Regex Cheat Sheet
Regular expressions in JavaScript: lookaround assertions by example
Regexly | Chipto
javascript - Why can't I use accented characters next to a word boundary? - Stack Overflow
GitHub - sola-da/ReDoS-vulnerabilities: A list of ReDoS vulnerabilities in npm modules found by the Software Lab at TU Darmstadt. For each vulnerability, there is a proof-of-concept exploit, showing how the slowdown may occur. The resources in this reposi
GitHub - DmitrySoshnikov/babel-plugin-transform-modern-regexp: Babel plugin for modern RegExp features in JavaScript
GitHub - jonschlinkert/regex-cache: Memoize the results of a call to the RegExp constructor, avoiding repetitious runtime compilation of the same string and options, resulting in dramatic speed improvements.