সরাসরি পর্বে যান
পর্ব ২১ · ৮৫-এর মধ্যে · মডিউল ৪

বাস্তব regex engine — backtracking বনাম automaton আর ReDoS

Real Regex Engines — Backtracking vs Automaton Simulation, Catastrophic Backtracking and ReDoS Defences

Taught in Bangla, this lesson compares backtracking regex engines (Python re, JavaScript, PCRE) with automaton-based ones (RE2, Go, Rust). It proves that ^(a+)+$ on a^n b makes 2^n − 1 final checks, shows set-of-states simulation is linear, and treats ReDoS defensively. Timings run in in-page Python (Pyodide) and in real desktop runs comparing Python re with google-re2, plus fixes with atomic groups, possessive quantifiers, input limits and the regex module's timeout.

এই পর্বে যা শিখবেন

  • Backtracking আর automaton-ভিত্তিক engine কীভাবে মেলায়, আর কোন ভাষা বা library কোন পরিবারের
  • Catastrophic backtracking-এর চেষ্টা-সংখ্যা গুনে প্রমাণ করা, আর set-of-states simulation-এর রৈখিক সময়ের যুক্তি
  • কোন বাস্তব সুবিধা (backreference, lookaround, capture) automaton-এর বাইরে যায় বা তাকে কঠিন করে
  • ReDoS-প্রবণ pattern চেনা, আর বাজারঘরের একটি validator-কে একই language রেখে নিরাপদ করা
  • Python re, RE2 আর regex module-এর সত্যিকারের মাপ পড়ে প্রতিরক্ষার স্তর বেছে নেওয়া

১ · একই regex, দুই রকম engine — বাজারঘরের সার্ভার কেন আটকে যায়

বাজারঘরের চেকআউট পাতায় একটি কুপন বাক্স আছে। একজন ডেভেলপার কুপনের নিয়ম লিখলেন একটি regex দিয়ে, পরীক্ষায় সব ঠিক চলল। কিছুদিন পর এক রাতে কেউ বাক্সে লিখলেন ত্রিশটি “A”, তারপর একটি “!”. সার্ভারের একটি CPU core কয়েক মিনিট ধরে শুধু সেই একটি অনুরোধ নিয়ে ব্যস্ত থাকল। Regex-এ কোনো ভুল ছিল না; language-টিও ছিল নিরীহ। সমস্যা ছিল engine-এ, অর্থাৎ যে program regex মেলায় তার কৌশলে।

গণিতের দৃষ্টিতে প্রশ্নটি এক: w ∈ L(R)? পর্ব ১৪-এ দেখেছেন, Thompson construction যেকোনো regular expression-কে ছোট একটি ε-NFA-তে আনে, আর state-এর সেট ধরে চালালে সময় |R| · m-এর অনুপাতে, যেখানে |R| regex-এর আকার আর m ইনপুটের দৈর্ঘ্য। কিন্তু বাস্তবের বহুল ব্যবহৃত অনেক regex engine এই পথ নেয় না। তারা NFA-র পথগুলো এক এক করে চেষ্টা করে, যেভাবে আপনি একটি গোলকধাঁধায় হাঁটেন।

পুরান ঢাকায় একটি ঠিকানা খুঁজছেন, যেখানে প্রতিটি মোড়ে দুই-তিনটি গলি। প্রথম কৌশল: একজন রিকশাওয়ালা একটি গলি বেছে শেষ পর্যন্ত যান, না পেলে মোড়ে ফিরে পরের গলি ধরেন। ঠিকানাটি আদৌ না থাকলে তিনি প্রতিটি সম্ভাব্য পথ ঘুরবেন, আর মোড় বাড়লে পথের সংখ্যা গুণ হারে বাড়ে। দ্বিতীয় কৌশল: একটি কাগজে লিখে রাখা “এই মুহূর্তে আমি কোন কোন মোড়ে থাকতে পারি”। প্রতিটি ধাপে তালিকাটি হালনাগাদ হয়, আর দুটি পথ একই মোড়ে মিললে তালিকায় সেটি একবারই থাকে। মহল্লায় যতগুলো মোড়, তালিকা তার চেয়ে কখনো বড় হয় না। প্রথমটি backtracking engine, দ্বিতীয়টি automaton-ভিত্তিক engine.

এই পর্ব দুটি কৌশলকে পাশাপাশি রেখে তিনটি প্রশ্নের উত্তর দেবে। এক, backtracking ঠিক কখন আর কতটা বিস্ফোরিত হয়, আর তা প্রমাণ করা যায় কীভাবে। দুই, automaton-ভিত্তিক engine কেন সবসময় রৈখিক, আর কোন সুবিধা তারা দিতে পারে না। তিন, একটি দুর্বল validator-কে কীভাবে নিরাপদ করা যায়, language না বদলে। Formal regex আর বাস্তব regex-এর সাধারণ পার্থক্য (character class, anchor, backreference) পর্ব ১৩-এ আছে; এখানে শুধু engine-এর দিকটি। Python-এ regex লেখা হাতে-কলমে শিখতে Python কোর্সের পর্ব ৩০ দেখুন।

এই পর্বের notation আর নিয়ম: “মেলানো” মানে পুরো string মেলানো (^…$ বা fullmatch), যাতে প্রশ্নটি ঠিক w ∈ L(R) থাকে। কোডে union “|”, লেখায় ∪. ε হলো ফাঁকা string. m = |w| ইনপুটের দৈর্ঘ্য, |R| = regex-এর syntax tree-র node-সংখ্যা। সব পরীক্ষা নিজের যন্ত্রে, নিজের ইনপুটে; কোনো বাইরের সার্ভিসে নয়।

২ · Backtracking engine — একবারে একটি পথ

একটি backtracking engine regex-কে একটি ছোট program হিসেবে দেখে, যার প্রতিটি “পছন্দের জায়গা” আছে: union-এ কোন শাখা, quantifier-এ আর একবার ঘুরবে কি না। Engine একটি পছন্দ নেয়, এগোয়, আর কোথাও আটকে গেলে সবচেয়ে কাছের পছন্দের জায়গায় ফিরে পরের বিকল্প নেয়। এটি আসলে NFA-র পথগুলোর ওপর একটি depth-first search, যার নিয়মগুলো সরল:

  • চিহ্ন a: বর্তমান অবস্থানে a থাকলে এক ঘর এগোনো, নইলে ব্যর্থ।
  • R ∪ S: আগে R দিয়ে বাকি সবটা চেষ্টা; ব্যর্থ হলে S দিয়ে।
  • R∗, R+ (greedy): আগে আরেকবার R চেষ্টা; বাকিটা না মিললে এক ধাপ কম নিয়ে বাকিটা চেষ্টা।
  • $: অবস্থান ঠিক শেষে হলে সফল।

এই নিয়মে একটি গুরুত্বপূর্ণ ফল আসে: engine প্রথম যে সফল পথ পায় সেখানেই থামে। তাই সফল মিলের সময় এটি প্রায়ই দ্রুত। বিপদ ব্যর্থ মিলে, কারণ “নেই” বলার আগে প্রতিটি পথ শেষ করতে হয়। একটি ক্লাসিক উদাহরণ ^(a+)+$: language শুধু a+, কিন্তু ভেতরের a+ আর বাইরের + মিলে একই a-গুলোকে অনেকভাবে ভাগ করা যায়। Stepper-টি “aaab”-এ পুরো search দেখায়।

1শুরু: অবস্থান 02ভাগ [aaa]3ভাগ [aa][a], তারপর [aa]4ভাগ [a][aa]5[a][a][a], [a][a], [a]6সিদ্ধান্ত7সাধারণ n
এই ধাপের হিসাব
চেষ্টা করা ভাগ
$ পরীক্ষার অবস্থান
$ পরীক্ষা (মোট)
  1. শুরু। Engine অবস্থান 0 থেকে বাইরের + শুরু করে, যার ভেতরে a+. ইনপুটে তিনটি a, তারপর b. Language a+, তাই উত্তর আগে থেকেই জানা: মিল নেই। দেখার বিষয় engine-এর খরচ।
  2. [aaa]. ভেতরের a+ greedy, তাই তিনটি a-ই নেয়। বাইরের + আরেকবার চেষ্টা করে, কিন্তু অবস্থান 3-এ b, a নয়। তখন $ পরীক্ষা: অবস্থান 3 শেষ নয়, ব্যর্থ। এটি প্রথম $ পরীক্ষা।
  3. [aa][a] আর [aa]. ভেতরের a+ একটি a ফেরত দেয়। বাইরের + নতুন একটি টুকরো শুরু করে, যা অবস্থান 2-এর a নেয়; অবস্থান 3-এ $ ব্যর্থ। তারপর দ্বিতীয় টুকরো ছাড়াই অবস্থান 2-এ $, আবার ব্যর্থ। মোট ৩টি।
  4. [a][aa]. এবার প্রথম টুকরো মাত্র একটি a. দ্বিতীয় টুকরো greedy, তাই বাকি দুটি a নেয়; অবস্থান 3-এ $ ব্যর্থ। মোট ৪টি।
  5. [a][a][a], [a][a], [a]. দ্বিতীয় টুকরো একটি a ফেরত দেয়, তৃতীয় টুকরো শেষ a নেয়: অবস্থান 3-এ ব্যর্থ। তারপর পিছিয়ে অবস্থান 2-এ, শেষে 1-এ $ পরীক্ষা, দুটিই ব্যর্থ। মোট ৭টি।
  6. সিদ্ধান্ত। আর কোনো পছন্দ বাকি নেই, তাই engine “মিল নেই” বলে। a3-এর চারটি ভাগ ([aaa], [aa][a], [a][aa], [a][a][a]) সবগুলো চেষ্টা হয়েছে, আর ছোট prefix-গুলোর ভাগও। মোট ৭ = 23 − 1টি $ পরীক্ষা।
  7. সাধারণ n. anb-তে একই ঘটনা: দৈর্ঘ্য k-এর prefix-এর প্রতিটি ভাগে একবার $ পরীক্ষা, মোট 2n − 1. n = 20-এ ১০ লাখের বেশি, n = 30-এ একশো কোটির বেশি। অংশ ৩ এটি প্রমাণ করবে।

পুরো search-টি একটি গাছ। গাছের মূলে অবস্থান 0, আর প্রতিটি তীর একটি টুকরো (ভেতরের a+-এর একটি পুনরাবৃত্তি)। প্রতিটি node-এ engine একবার $ পরীক্ষা করে, আর লাল ✗ মানে সেই পরীক্ষা ব্যর্থ; ছোট সংখ্যাটি পরীক্ষার ক্রম।

^(a+)+$ আর “aaab” — backtracking-এর search tree

বৃত্তের ভেতরের সংখ্যা ইনপুটের অবস্থান; তীরের গায়ে সেই টুকরোর a-গুলো। মূল ছাড়া ৭টি node, প্রতিটিতে একটি ব্যর্থ $ পরীক্ষা।

Backtracking search tree of ^(a+)+$ on aaab 0 321 332 3 aaa aa a a aa a a ✗ 1 ✗ 3 ✗ 7 ✗ 2 ✗ 4 ✗ 6 ✗ 5 ৪টি পাতা = a³-এর ৪টি ভাগ মোট ✗ = 2³ − 1 = 7
ছবি ২১.১ — গাছের প্রতিটি পথ a-গুলোর একটি ভাগ; মিল না থাকায় engine প্রতিটি পথ শেষ পর্যন্ত ঘোরে।

এখানে একটি দ্বিতীয় পার্থক্যও লক্ষ করার মতো, যা “মিলবে কি না” নয়, “কী মিলবে” নিয়ে। Backtracking engine-এর উত্তর নির্ভর করে পছন্দের ক্রমের ওপর। a|ab দিয়ে “ab”-এর শুরুতে খুঁজলে Python-এর re শুধু “a” ফেরত দেয়, কারণ বাঁ শাখা আগে সফল হয়েছে। এই নিয়মকে বলা হয় leftmost-first. POSIX মানের কিছু টুলে নিয়ম ভিন্ন, leftmost-longest: একই জায়গা থেকে সবচেয়ে লম্বা মিল, অর্থাৎ “ab”. গণিতের প্রশ্ন w ∈ L(R)-এ এই পার্থক্য নেই, কিন্তু খুঁজে বের করা আর বদলানোর কাজে আছে।

৩ · Catastrophic backtracking — গোনা আর প্রমাণ

Stepper-এর সংখ্যাগুলো কাকতালীয় নয়। একটি ধনাত্মক পূর্ণসংখ্যা k-কে ক্রমসহ ধনাত্মক অংশের যোগফলে লেখাকে বলে composition, যেমন 3 = 3 = 2 + 1 = 1 + 2 = 1 + 1 + 1. ak-কে অশূন্য টুকরোয় ভাগ করা আর k-এর একটি composition একই জিনিস। (গোনার পটভূমি ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৩৫-এ।)

উপপাদ্য ৩.১ (^(a+)+$-এর নিম্নসীমা)

অংশ ২-এর নিয়মে চলা backtracking matcher ^(a+)+$-কে ইনপুট anb (n ≥ 1)-এ চালালে ঠিক 2n − 1 বার $ পরীক্ষা করে, তারপর “মিল নেই” বলে। ফলে তার সময় অন্তত 2n − 1-এর অনুপাতে, অর্থাৎ exponential.

প্রমাণ:

  1. প্রতিটি টুকরো (ভেতরের a+-এর এক পুনরাবৃত্তি) অন্তত একটি a নেয়, আর b-তে থেমে যায়। তাই engine যতবার $ পরীক্ষা করে, ততবার সে কোনো k ∈ {1, …, n}-এর জন্য ak-কে একটি নির্দিষ্ট ক্রমের টুকরোয় ভাগ করে অবস্থান k-এ দাঁড়িয়ে আছে। — অংশ ২-এর নিয়ম
  2. উল্টো দিকে, এমন প্রতিটি ভাগে engine ঠিক একবার পৌঁছায়: প্রতিটি পছন্দের জায়গায় (একটি টুকরোর দৈর্ঘ্য) বিকল্পগুলো একে একে, প্রতিটি একবার, চেষ্টা হয়; আর কোনো $ পরীক্ষা সফল হয় না, কারণ শেষ ঘরে b. তাই search আগেভাগে থামে না। — depth-first search সব শাখা একবার করে ঘোরে
  3. অতএব $ পরীক্ষার সংখ্যা = Σk=1..n (k-এর composition-সংখ্যা)। — ১ আর ২-এর bijection
  4. k-এর composition-সংখ্যা 2k−1: k-টি a-এর মাঝের k − 1টি ফাঁকের প্রতিটিতে কাটা হবে কি না, স্বাধীনভাবে ঠিক করলেই একটি ভাগ, আর প্রতিটি ভাগ এভাবে ঠিক একবার আসে। — গুণনের নিয়ম
  5. Σk=1..n 2k−1 = 2n − 1. ∎ — geometric series

একই যুক্তি অন্য আকারেও খাটে। (a|a)*b-এ nesting নেই, শুধু একটি quantifier, কিন্তু প্রতিটি a-কে দুটি শাখার যেকোনোটি দিয়ে মেলানো যায়; an-এ তাই 2nটি পথ। (a|aa)*b-এ an-কে 1 আর 2 দৈর্ঘ্যের টুকরোয় ভাগ করার উপায় Fibonacci সংখ্যা, যা মোটামুটি 1.618n হারে বাড়ে। আর a*a*b-এ বিস্ফোরণ নেই, কিন্তু প্রথম a* কোথায় থামবে আর দ্বিতীয়টি কোথায়, তার প্রায় n2/2টি জোড়া: সময় বর্গের হারে। এই বিস্ফোরণের নাম catastrophic backtracking, আর তিনটির সাধারণ কারণ একটি: একই string একই pattern-এ একাধিক উপায়ে মেলে, অর্থাৎ pattern-টি ambiguous.

নিচের JavaScript ব্লকে দুটি engine একই ছোট syntax tree-র ওপর লেখা। bt অংশ ২-এর নিয়মে চলা backtracking matcher, যা প্রতিটি নিজের-ডাক গোনে। sim একই tree থেকে Thompson NFA বানিয়ে state-এর সেট ধরে চালায়, আর ε-closure-এ কতবার state ছোঁয়া হলো তা গোনে। পৃষ্ঠা যাতে আটকে না যায়, bt ২০ লাখ ধাপে থেমে যায়, আর ইনপুট ছোট রাখা হয়েছে।

// One tiny regex AST, two engines; full-string match. t: "c" . | * +
const C = x => ({t: "c", x}), N = (t, a, b) => ({t, a, b}); let steps = 0;
function bt(r, s, i, k) {                 // backtracking: one path at a time
  if (++steps > 2e6) throw "step cap";    // safety: never freeze the page
  if (r.t === "c") return s[i] === r.x && k(i + 1);
  if (r.t === ".") return bt(r.a, s, i, j => bt(r.b, s, j, k));
  if (r.t === "|") return bt(r.a, s, i, k) || bt(r.b, s, i, k);
  const more = j => bt(r.a, s, j, m => m > j && more(m)) || k(j); // greedy
  return r.t === "*" ? more(i) : bt(r.a, s, i, more);
}
function nfa(r, E) {                      // Thompson fragment: [start, accept]
  const nw = () => E.push([]) - 1, eps = (p, q) => E[p].push(["", q]);
  if (r.t === "c") { const s = nw(), f = nw(); E[s].push([r.x, f]); return [s, f]; }
  const A = nfa(r.a, E), B = r.b && nfa(r.b, E);
  if (r.t === ".") { eps(A[1], B[0]); return [A[0], B[1]]; }
  const s = nw(), f = nw(); (B ? [A, B] : [A]).forEach(([x, y]) => { eps(s, x); eps(y, f); });
  if (!B) { eps(A[1], A[0]); if (r.t === "*") eps(s, f); }
  return [s, f]; }
function sim(r, w, E = []) {              // set of states; work = states touched
  const [s, f] = nfa(r, E); let work = 0, S = [s];
  for (let i = 0; ; i++) {
    for (const st = [...(S = new Set(S))]; st.length; work++)        // ε-closure
      for (const [l, q] of E[st.pop()]) if (l === "" && !S.has(q)) { S.add(q); st.push(q); }
    if (i === w.length) return [S.has(f), work];
    S = [...S].flatMap(p => E[p].filter(e => e[0] === w[i]).map(e => e[1])); } }
const a = C("a"), P = {"(a+)+": N("+", N("+", a)), "(a|a)*b": N(".", N("*", N("|", a, a)), C("b")),
  "(a|aa)*b": N(".", N("*", N("|", a, N(".", a, a))), C("b"))};
const run = (r, w) => { steps = 0; try { return bt(r, w, 0, j => j === w.length); } catch (e) { return "stopped"; } };
for (const [name, r] of Object.entries(P)) for (const n of [4, 8, 12, 16]) {
  const w = "a".repeat(n) + "!", m = run(r, w), [m2, work] = sim(r, w);
  console.log(name.padEnd(8), "n =", String(n).padStart(2), "backtrack", String(steps).padStart(6), "| sets", work, "|", m, m2); }
const W = L => L ? W(L - 1).flatMap(x => [x + "a", x + "b"]) : [""], all = [0,1,2,3,4,5,6,7,8,9,10].flatMap(W);
const bad = Object.values(P).reduce((t, r) => t + all.filter(w => run(r, w) !== sim(r, w)[0]).length, 0);
console.log("strings x patterns:", all.length * 3, " disagreements:", bad);

আসল আউটপুট (ব্রাউজারের JavaScript):

(a+)+    n =  4 backtrack     48 | sets 23 | false false
(a+)+    n =  8 backtrack    768 | sets 43 | false false
(a+)+    n = 12 backtrack  12288 | sets 63 | false false
(a+)+    n = 16 backtrack 196608 | sets 83 | false false
(a|a)*b  n =  4 backtrack    126 | sets 38 | false false
(a|a)*b  n =  8 backtrack   2046 | sets 70 | false false
(a|a)*b  n = 12 backtrack  32766 | sets 102 | false false
(a|a)*b  n = 16 backtrack 524286 | sets 134 | false false
(a|aa)*b n =  4 backtrack     69 | sets 45 | false false
(a|aa)*b n =  8 backtrack    496 | sets 85 | false false
(a|aa)*b n = 12 backtrack   3423 | sets 125 | false false
(a|aa)*b n = 16 backtrack  23485 | sets 165 | false false
strings x patterns: 6141  disagreements: 0

ইনপুট an!, তাই কোনোটিই মেলে না (দুই engine-ই false). (a+)+-এর backtracking ধাপ প্রতিবার n চার বাড়লে ১৬ গুণ: 48 = 3 · 24, 768 = 3 · 28, অর্থাৎ ঠিক 3 · 2n. এই matcher প্রতিটি টুকরো-চেষ্টায় কয়েকটি ডাক খরচ করে, তাই ধ্রুবক 3; বৃদ্ধির হার উপপাদ্য ৩.১-এর 2n. (a|a)*b-এ সংখ্যাটি 2n+3 − 2, আর (a|aa)*b-এ প্রতি চার ধাপে প্রায় ৬.৯–৭.২ গুণ, যা 1.6184 ≈ 6.85-এর কাছাকাছি। ডান দিকের “sets” কলাম দেখুন: 23, 43, 63, 83, প্রতিবার ঠিক ২০ বেশি। এটি রৈখিক, (a+)+-এ 3 + 5n. শেষ লাইনে দৈর্ঘ্য ≤ 10-এর সব 2047টি string-এ তিনটি pattern, মোট 6141টি পরীক্ষায় দুই engine একমত: উত্তর একই, খরচ আলাদা। (সূত্রগুলো scratch-এ n = 1 থেকে 16 পর্যন্ত মেলানো হয়েছে।)

৪ · Automaton engine — state-এর সেট আর রৈখিক সময়

Backtracking-এর পথ অনেক, কিন্তু NFA-র state অল্প। একটি অবস্থান i-তে দুটি ভিন্ন পথ যদি একই state q-তে পৌঁছায়, তাহলে বাকি ইনপুটে তাদের ভবিষ্যৎ হুবহু এক: q থেকে বাকি অংশ মেলে কি না, তা পথের ইতিহাসের ওপর নির্ভর করে না। তাই দুটি পথকে আলাদা করে চালানোর দরকার নেই; একটি করে রাখলেই চলে। এই ধারণাই set-of-states simulation, যা পর্ব ০৯-এর on-the-fly simulation আর পর্ব ১৪-এর Thompson-এর পদ্ধতি।

উপপাদ্য ৪.১ (automaton matching রৈখিক)

ধরুন N হলো regex R-এর Thompson ε-NFA (state ≤ 2|R|, তীর ≤ 4|R|)। S0 = E({s}) আর Si+1 = E({q : কোনো p ∈ Si থেকে wi+1-তীরে q}) হলে, প্রতিটি i-এর জন্য Si = {q : s থেকে q-তে label w1⋯wi-এর একটি পথ আছে}. ফলে w ∈ L(R) ⇔ f ∈ Sm, আর পুরো হিসাবের সময় |R| · m-এর অনুপাতে, মেমরি |R|-এর অনুপাতে।

প্রমাণের রূপরেখা: i-এর ওপর induction. i = 0-এ S0 শুধু ε-তীরে পৌঁছানো state, ঠিক label ε-এর পথগুলোর শেষ। ধাপে: label w1⋯wi+1-এর প্রতিটি পথ ভাঙা যায় তিন ভাগে, আগে label w1⋯wi-এর একটি পথ (hypothesis-এ শেষ Si-এ), তারপর একটি wi+1-তীর, তারপর কিছু ε-তীর; উল্টো দিকও একই ভাঙনে। সময়ের জন্য: প্রতিটি ধাপে closure একটি graph search, যেখানে প্রতিটি state একবার সেটে ঢোকে আর প্রতিটি তীর একবার দেখা হয়, তাই ধাপপ্রতি কাজ ≤ 2|R| + 4|R|; m ধাপে |R| · m-এর অনুপাতে। মেমরিতে থাকে শুধু বর্তমান সেট। বিস্তারিত পর্ব ১৪-এর উপপাদ্য ৫.১-এ। ∎

উপপাদ্য ৩.১-এর সঙ্গে তুলনা করুন। Backtracking গোনে পথ, যা 2n পর্যন্ত হতে পারে; set simulation গোনে (state, অবস্থান) জোড়া, যা বড়জোর |Q| · (m + 1). নিচের NFA (a+)+-এর Thompson যন্ত্র, অংশ ৩-এর কোডের নিয়মে বানানো (R+-এর নিয়মটি পর্ব ১৪-এর অনুশীলন ৪-এর): ভেতরের a+-এর লুপ q1 → q0, বাইরের +-এর লুপ q3 → q2.

(a+)+-এর Thompson NFA — ৬টি state

নাম না লেখা তীর ε. হলুদ state-গুলো একটি a পড়ার পরের সেট {q0, q1, q2, q3, q5}; দুই লুপ মিলে যত পথই হোক, সেটে পাঁচটির বেশি state আসে না।

Thompson NFA for (a+)+ q4q2q0 q1q3q5 a শুরু ভেতরের লুপ (a+) বাইরের লুপ (+)
ছবি ২১.২ — একমাত্র চিহ্ন-তীর q0 –a→ q1; বাকি সব ε. শুধু q5 accepting.
1শুরু: E({q4})2পড়া হলো a3পড়া হলো a4পড়া হলো a5পড়া হলো b6সিদ্ধান্ত
এই ধাপের অবস্থা
এ পর্যন্ত পড়া
সেট (ε-closure-এর পর)
মোট state ছোঁয়া
  1. শুরু। q4 থেকে ε-তে q2, সেখান থেকে q0. সেট {q0, q2, q4}: যন্ত্র প্রথম a পড়ার জন্য প্রস্তুত। Closure-এ ৩টি state ছোঁয়া হলো।
  2. a পড়া। সেটের একমাত্র a-তীর q0 → q1. Closure: q1 থেকে ভেতরের লুপে q0 আর বের হয়ে q3; q3 থেকে বাইরের লুপে q2 আর শেষে q5. পাঁচটি state, ৫টি ছোঁয়া। Backtracking-এর “আরেক টুকরো, নাকি একই টুকরো” দুই পছন্দ এখানে একই সেটে মিশে গেছে।
  3. আবার a. আবার শুধু q0 → q1, আর একই closure, তাই হুবহু একই সেট। কতভাবে প্রথম দুটি a ভাগ করা যায়, সেই খবর আর রাখা হয় না; দরকারও নেই।
  4. তৃতীয় a. একই সেট, যাতে q5 আছে: এখানে ইনপুট শেষ হলে “aaa” গৃহীত হতো। মোট ১৮টি state ছোঁয়া, অর্থাৎ 3 + 5 · 3.
  5. b পড়া। সেটের কোনো state থেকে b-তীর নেই, তাই সেট ∅. ∅ থেকে আর কিছুতে যাওয়া যায় না; একটি বুদ্ধিমান engine এখানেই থামতে পারে।
  6. সিদ্ধান্ত। শেষ সেটে q5 নেই, তাই “মিল নেই”, backtracking-এর মতোই। পার্থক্য খরচে: n টি a-তে 3 + 5n, অংশ ৩-এর কোডের “sets” কলামের সূত্র; backtracking-এ 3 · 2n.

বাস্তবের automaton-ভিত্তিক engine এর ওপর আরও কৌশল বসায়। একটি হলো পর্ব ১০-এর lazy DFA: প্রতিটি সেটকে একটি DFA state ধরে তার সারি cache-এ রাখা, যাতে একই সেট আবার এলে টেবিল দেখেই এগোনো যায়। আরেকটি হলো capture group-এর অবস্থান মনে রাখার জন্য প্রতিটি state-এর সঙ্গে কিছু বাড়তি তথ্য বহন করা, যাকে প্রায়ই “Pike VM” বলা হয়। প্রধান পরিবারগুলো এক নজরে, তাদের নিজেদের নথি অনুযায়ী (এই লেখার সময়ের অবস্থা):

EngineপরিবারBackreference / lookaroundসবচেয়ে খারাপ সময়
Python re, Java java.util.regex, JavaScript RegExp, Perl, PCREbacktrackingআছেexponential হতে পারে
.NET Regexডিফল্ট backtracking; .NET 7 থেকে NonBacktracking বিকল্পডিফল্টে আছে; বিকল্পটিতে নেইবিকল্পটিতে রৈখিক
RE2 (C++; Python-এ google-re2), Go regexp, Rust regexautomaton (NFA simulation, lazy DFA)নেই, ইচ্ছাকৃতভাবে|R| · m-এর অনুপাতে
GNU grepবেশিরভাগ pattern-এ DFA; backreference থাকলে আলাদা matcherbackreference আছেbackreference ছাড়া রৈখিক

৫ · কোন সুবিধা automaton-এর বাইরে যায়

তাহলে সব engine automaton-ভিত্তিক নয় কেন? কারণ বাস্তব regex-এর কিছু সুবিধা গণিতের regular language-এর বাইরে, আর কিছু ভেতরে থাকলেও automaton-এ বসানো ঝামেলার।

Backreference. ^(a+)b\1$ মানে “কিছু a, তারপর b, তারপর হুবহু ততগুলো a”: language {anban : n ≥ 1}. পর্ব ১৭-এর pumping lemma-র একই যুক্তিতে এটি non-regular, তাই কোনো finite automaton এটি চেনে না; আর ^(.+)\1$ লেখে {ww}, যা context-free-ও নয় (পর্ব ৩৬-এ প্রমাণ আসবে)। এর চেয়েও বড় কথা: backreference-সহ pattern মেলানো সাধারণভাবে NP-complete বলে প্রমাণিত, এমন উল্লেখ সাহিত্যে আছে (Alfred Aho-র ১৯৯০ সালের একটি সমীক্ষায়)। তাই P ≠ NP হলে (যা খোলা প্রশ্ন) কোনো engine-ই সব backreference pattern-এ বহুপদী সময় দিতে পারবে না।

Lookaround. Lookahead (?=…) বর্তমান অবস্থানের পরে কিছু আছে কি না দেখে, কিছু না খেয়ে। Backreference ছাড়া এমন pattern-এর language regular থাকে বলে জানা আছে, কারণ এটি আসলে দুটি regular শর্তের intersection-এর মতো, আর regular language intersection-এ closed (পর্ব ১৬)। কিন্তু একটি একক পাসের set simulation-এ এটি বসানো সহজ নয়, তাই RE2 আর Rust-এর regex lookaround রাখেনি। অর্থাৎ এখানে সীমা তত্ত্বের নয়, প্রকৌশলের।

Capture আর মিলের অর্থ। Capturing group কোন অংশ মেলাল তা জানাতে হয়, আর অংশ ২-এর leftmost-first নিয়মে কোন পথ “প্রথম”, তা backtracking-এর ক্রম দিয়েই সংজ্ঞায়িত। Automaton engine-কে সেই ক্রম আলাদাভাবে অনুকরণ করতে হয়; RE2-এর মতো library এটি করে, কিন্তু খরচ কিছুটা বাড়ে।

সাধারণ ভুল ধারণা: “আমার pattern-এ backreference নেই, তাই Python-এর re এটিকে automaton দিয়ে চালাবে।” না। Engine-এর পরিবার pattern দেখে বদলায় না; Python-এর re সব pattern-ই backtracking-এ চালায়। কিছু engine-এ বিশেষ কিছু pattern-এর জন্য optimisation থাকে (অংশ ৭-এ একটি দেখবেন), কিন্তু তা নিশ্চয়তা নয়।

৬ · ReDoS — দুর্বল নকশা চেনা আর নিরাপদে লেখা

যখন একজন আক্রমণকারী ইচ্ছা করে এমন ইনপুট পাঠান যাতে একটি দুর্বল regex catastrophic backtracking-এ পড়ে, তাকে বলে ReDoS (regular expression denial of service). এটি একটি algorithmic complexity attack: বেশি তথ্য পাঠিয়ে নয়, প্রোগ্রামের সবচেয়ে খারাপ ক্ষেত্রটি খুঁজে নিয়ে সার্ভার ব্যস্ত রাখা। দুর্বলতার শ্রেণিটি CWE-1333 (Inefficient Regular Expression Complexity) নামে তালিকাভুক্ত। নিরাপদ কোডিংয়ের বড় ছবি Cybersecurity কোর্সের পর্ব ৪৬-এ; এখানে তত্ত্বের দিকটি।

উপপাদ্য ৩.১-এর শিক্ষা থেকে সতর্কসংকেতগুলো সরাসরি আসে। একটি backtracking engine-এ বিপদ যখন একই অংশ একাধিক উপায়ে মেলে আর তারপর মিলটি শেষে ব্যর্থ হয়। তিনটি চেনা আকার:

  • Nested quantifier: (a+)+, (\d+)*, ([A-Z0-9]+-?)+; ভেতর আর বাইরের quantifier একই চিহ্ন ভাগাভাগি করে।
  • Overlapping alternation: (a|a)*, (a|ab|b)*, (\w|\d)+; দুটি শাখা একই string মেলাতে পারে।
  • পাশাপাশি overlapping quantifier: a*a*, .*x.*x; বিস্ফোরণ নয়, কিন্তু বর্গ বা ঘনের হারে সময়, যা লম্বা ইনপুটে একই রকম ক্ষতিকর।

দুষ্ট ইনপুটের আকারও একই রকম: একটি লম্বা “প্রায় মিল” অংশ, যা অনেকভাবে ভাগ করা যায়, আর শেষে এমন একটি চিহ্ন যা মিল ভেঙে দেয়। এবার বাজারঘরের কুপন validator. নিয়ম: কুপন হলো বড় হাতের অক্ষর বা অঙ্কের এক বা একাধিক দল, মাঝে একটি করে হাইফেন, যেমন EID-SALE-2026. Stepper পুরোনো নকশা থেকে নিরাপদ নকশায় যাওয়ার ধাপগুলো দেখায়; সংখ্যাগুলো নিচের Python ব্লক থেকে।

1পুরোনো নকশা2সমস্যা খোঁজা3দুষ্ট ইনপুট4দ্ব্যর্থহীন নকশা5সমতা যাচাই6নীতির প্রশ্ন7প্রতিরক্ষার স্তর
এই ধাপের হিসাব
Pattern
“AAAA”-এর ভাগ
মাপ বা ফল
  1. পুরোনো নকশা। ^([A-Z0-9]+-?)+$: একটি দল মানে কিছু অক্ষর-অঙ্ক, তারপর ইচ্ছা হলে একটি হাইফেন; এমন দল এক বা একাধিক। EID-SALE-2026 মেলে, ভুল কুপন বাদ পড়ে। স্বাভাবিক পরীক্ষায় কোনো সমস্যা ধরা পড়ে না।
  2. সমস্যা খোঁজা। -? ফাঁকাও মেলাতে পারে। তাহলে হাইফেন ছাড়া একটি লম্বা দল, যেমন “AAAA”, অনেকভাবে দলে ভাগ হয়: [AAAA], [AA][AA], [A][A][A][A] … মোট 23 = 8টি। এটি হুবহু (a+)+-এর আকার।
  3. দুষ্ট ইনপুট। n টি “A”, তারপর “!”. শেষের “!” মিল ভাঙে, তাই engine সব 2n−1 ভাগ চেষ্টা করে। ব্রাউজারের Python-এ n দুই বাড়লে সময় প্রায় চার গুণ; এক run-এ n = 22-এ প্রায় 0.27 সেকেন্ড, আর সেই হারে n = 40-এ প্রায় ২০ ঘণ্টা লাগার কথা।
  4. দ্ব্যর্থহীন নকশা। ^[A-Z0-9]+(-[A-Z0-9]+)*-?$. প্রথম দলের পর প্রতিটি নতুন দল হাইফেন দিয়ে শুরু হতে বাধ্য। তাই হাইফেনগুলোই ঠিক করে দেয় কোথায় দল ভাঙবে, আর প্রতিটি string-এর ঠিক একটি ভাগ। Engine পিছিয়ে এলেও চেষ্টা করার মতো বিকল্প থাকে না।
  5. সমতা যাচাই। নতুন নকশা কি একই কুপন গ্রহণ করে? {A, 7, -} alphabet-এ দৈর্ঘ্য ≤ 8-এর সব 9841টি string-এ পুরোনো আর নতুন নকশা মেলানো হলো: 0 অমিল। Python 3.11-এর atomic group-ওয়ালা রূপ ^(?>[A-Z0-9]+-?)+$-ও 0 অমিল।
  6. নীতির প্রশ্ন। সমতা যাচাই একটি পুরোনো খুঁতও দেখাল: পুরোনো নকশা শেষে হাইফেনওয়ালা “7-”-ও গ্রহণ করে। শেষ -? বাদ দিলে কুপন-নিয়ম আরও কঠোর হয়, কিন্তু তখন 1034টি string-এ উত্তর বদলায়, সবচেয়ে ছোট “7-”. এটি পণ্যের সিদ্ধান্ত, নিঃশব্দে বদলানোর বিষয় নয়।
  7. প্রতিরক্ষার স্তর। নকশা ঠিক হলেও বাড়তি সুরক্ষা রাখা ভালো: কুপনের দৈর্ঘ্য ধরুন ৩২-এ সীমিত, regex চালানোর আগেই পরীক্ষা; আর regression test-এ একটি দুষ্ট ইনপুট, যাতে কেউ পরে pattern বদলে দুর্বলতা ফেরালে test ধরতে পারে।

Python ব্লকটি stepper-এর সংখ্যাগুলো আপনার ব্রাউজারে বের করে। প্রথমে brute-force সমতা যাচাই, তারপর দুষ্ট ইনপুটে সময়। পৃষ্ঠা যাতে আটকে না যায়, কোনো একটি মাপ ০.১ সেকেন্ড ছাড়ালেই পরের, প্রায় চার গুণ লম্বা, মাপটি আর চালানো হয় না।

import re, time
from itertools import product

V = r"^([A-Z0-9]+-?)+$"                  # vulnerable: nested, overlapping
F = r"^[A-Z0-9]+(-[A-Z0-9]+)*-?$"        # rewritten: a dash starts each repeat
A = r"^(?>[A-Z0-9]+-?)+$"                # atomic group (Python 3.11+)
S = r"^[A-Z0-9]+(-[A-Z0-9]+)*$"          # stricter policy: no trailing dash

words = ["".join(p) for k in range(9) for p in product("A7-", repeat=k)]
acc = lambda pat: {w for w in words if re.match(pat, w)}
LV = acc(V)
for name, pat in [("F", F), ("A", A), ("S", S)]:
    diff = sorted(LV ^ acc(pat), key=lambda w: (len(w), w))
    print(f"V vs {name}: {len(diff)} differences in {len(words)} strings",
          "| shortest:", diff[0] if diff else "-")

def secs(pat, s):
    t = time.perf_counter(); re.match(pat, s); return time.perf_counter() - t

for n in range(10, 23, 2):               # evil input: long code + a bad char
    t = secs(V, "A" * n + "!")
    print(f"V  n = {n:2}  {t:8.4f} s")
    if t > 0.1: print("stop: next run would take about 4x longer"); break
for name, pat in [("F", F), ("A", A), ("S", S)]:
    print(f"{name}  n = 100000  {secs(pat, 'A' * 100_000 + '!'):.4f} s")
print("EID-SALE-2026:", [bool(re.match(p, "EID-SALE-2026")) for p in (V, F, A, S)])

আসল আউটপুট (ব্রাউজারের Python):

V vs F: 0 differences in 9841 strings | shortest: -
V vs A: 0 differences in 9841 strings | shortest: -
V vs S: 1034 differences in 9841 strings | shortest: 7-
V  n = 10    0.0001 s
V  n = 12    0.0002 s
V  n = 14    0.0010 s
V  n = 16    0.0039 s
V  n = 18    0.0159 s
V  n = 20    0.0756 s
V  n = 22    0.2660 s
stop: next run would take about 4x longer
F  n = 100000  0.0041 s
A  n = 100000  0.0003 s
S  n = 100000  0.0031 s
EID-SALE-2026: [True, True, True, True]

প্রথম তিন লাইন stepper-এর ধাপ ৫ আর ৬: {A, 7, -}-এর ওপর দৈর্ঘ্য 0 থেকে 8-এর 30 + ⋯ + 38 = 9841টি string-এ নতুন নকশা F আর atomic রূপ A পুরোনো V-এর সঙ্গে হুবহু মেলে, আর কঠোর রূপ S 1034টিতে আলাদা, সবচেয়ে ছোট পার্থক্য “7-”. তারপর V-এর সময়: n দুই বাড়লে প্রায় চার গুণ (0.0039, 0.0159, 0.0756, 0.2660), যা 2n-এর হার; ০.১ সেকেন্ড ছাড়াতেই ব্লক থেমেছে। একই হারে n = 40-এ প্রায় ২০ ঘণ্টা লাগার কথা। তিন নিরাপদ রূপ ১ লাখ অক্ষরেও কয়েক মিলিসেকেন্ডের কম সময় নিয়েছে। শেষ লাইনে চারটিই আসল কুপন গ্রহণ করে। সময়ের সংখ্যা যন্ত্র আর ব্রাউজারভেদে বদলাবে; চার গুণের অনুপাত বদলাবে না।

৭ · সত্যিকারের run — Python re, RE2 আর regex module

আগে আপনার ব্রাউজারেই textbook pattern-টি মাপুন। ব্লকটি ^(a+)+$-কে anb-তে চালায়, প্রতিবার n দুই বাড়িয়ে, আর একটি মাপ ০.১ সেকেন্ড ছাড়ালে থামে। তারপর তিনটি নিরাপদ রূপ ১ লাখ অক্ষরের ইনপুটে: atomic group (?>…), possessive quantifier ++ (দুটিই Python 3.11 থেকে re-তে আছে), আর সরল রূপ ^a+$.

import re, sys, time
print("Python", sys.version.split()[0], "(Pyodide, in this browser)")

def secs(pat, s):
    t = time.perf_counter(); m = re.match(pat, s)
    return time.perf_counter() - t, m is not None

prev = 0
for n in range(10, 25, 2):              # (a+)+$ on a...ab never matches
    t, m = secs(r"^(a+)+$", "a" * n + "b")
    grow = f"x{t / prev:.1f}" if prev > 0.002 else ""
    print(f"n = {n:2}  {t:8.4f} s  {grow:5}  match: {m}")
    prev = t
    if t > 0.1:                          # the next run would take ~4x longer
        print("stopped here to keep the page responsive"); break

for pat in (r"^(?>a+)+$", r"^(a++)+$", r"^a+$"):  # atomic, possessive, simple
    t, m = secs(pat, "a" * 100_000 + "b")
    print(f"{pat:10} n = 100000  {t:.5f} s  match: {m}")

আসল আউটপুট (ব্রাউজারের Python):

Python 3.14.2 (Pyodide, in this browser)
n = 10    0.0001 s         match: False
n = 12    0.0001 s         match: False
n = 14    0.0008 s         match: False
n = 16    0.0025 s         match: False
n = 18    0.0103 s  x4.1   match: False
n = 20    0.0403 s  x3.9   match: False
n = 22    0.1642 s  x4.1   match: False
stopped here to keep the page responsive
^(?>a+)+$  n = 100000  0.00010 s  match: False
^(a++)+$   n = 100000  0.00010 s  match: False
^a+$       n = 100000  0.00070 s  match: False

ব্রাউজারের Python (Pyodide-এ CPython 3.14) একই re engine চালায়। অনুপাতের কলামে x4.1, x3.9, x4.1: n দুই বাড়লে সময় চার গুণ, ঠিক 2n-এর হার। খুব ছোট মাপে (২ মিলিসেকেন্ডের কম) অনুপাত ছাপা হয়নি, কারণ ব্রাউজারের ঘড়ি সেখানে যথেষ্ট সূক্ষ্ম নয়। n = 22-এ ০.১ সেকেন্ড ছাড়াতেই ব্লক থেমেছে; পরের মাপে প্রায় ০.৭ সেকেন্ড লাগত। নিচের তিন লাইনে ১ লাখ a আর একটি b: atomic আর possessive রূপ ০.১ মিলিসেকেন্ডে, সরল ^a+$ ০.৭ মিলিসেকেন্ডে, সবই “মিল নেই”। অর্থাৎ ১ লাখ অক্ষরের ইনপুট ২২ অক্ষরের দুর্বল মাপের চেয়ে কয়েকশো গুণ দ্রুত শেষ হলো। আপনার যন্ত্রে সংখ্যা আলাদা হবে, চার গুণের হার একই থাকবে।

এবার ডেস্কটপে, uv দিয়ে বানানো একটি ছোট প্রকল্পে, আরও বড় n আর আরেকটি engine নিয়ে। google-re2 হলো RE2 library-র Python wrapper (BSD-3-Clause licence; সংস্করণ 1.1.20251105), Python 3.13.5. Library-র Python অংশে কোনো network বা usage-reporting কোড নেই, তা scratch-এ খুঁজে দেখা হয়েছে। Python-এর প্রতিটি মাপ আলাদা একটি child process-এ চলে, ১০ সেকেন্ডের timeout-সহ, যাতে কিছুই আটকে না থাকে।

import subprocess, sys, time
from importlib.metadata import version
import re2

PAT = r"^(a+)+$"
LIMIT = 10.0                       # seconds; a run that takes longer is killed
CHILD = ("import re,sys,time; n=int(sys.argv[1]); s='a'*n+'b'; "
         "t=time.perf_counter(); r=re.match(sys.argv[2], s); "
         "print(time.perf_counter()-t, r is None)")
print("python", sys.version.split()[0], "| google-re2", version("google-re2"))
print(" n   Python re (s)   google-re2 (s)")
dead = False
for n in range(10, 29, 2):
    s = "a" * n + "b"
    t = time.perf_counter(); r2 = re2.match(PAT, s); t2 = time.perf_counter() - t
    if dead:
        py = f"> {LIMIT:.0f} (skipped)"
    else:
        try:
            out = subprocess.run([sys.executable, "-c", CHILD, str(n), PAT],
                                 capture_output=True, text=True, timeout=LIMIT)
            py = f"{float(out.stdout.split()[0]):10.4f}"
        except subprocess.TimeoutExpired:
            py, dead = f"> {LIMIT:.0f} (killed)", True
    print(f"{n:2}   {py:>14}   {t2:12.6f}   re2 match: {r2 is not None}")

সত্যিকারের run (ডেস্কটপ, Python 3.13.5, google-re2 1.1.20251105):

~/bazarghar-toc$ uv run python redos_timing.py
python 3.13.5 | google-re2 1.1.20251105
 n   Python re (s)   google-re2 (s)
10           0.0001       0.000061   re2 match: False
12           0.0002       0.000048   re2 match: False
14           0.0005       0.000044   re2 match: False
16           0.0017       0.000044   re2 match: False
18           0.0066       0.000044   re2 match: False
20           0.0261       0.000045   re2 match: False
22           0.1060       0.000045   re2 match: False
24           0.4217       0.000045   re2 match: False
26           1.7038       0.000048   re2 match: False
28           6.8667       0.000048   re2 match: False

Python re-এর কলামে n = 16 থেকে প্রতি ধাপে প্রায় চার গুণ: 0.0017, 0.0066, 0.0261, 0.1060, 0.4217, 1.7038, 6.8667. প্রতি ধাপে n দুই বাড়ে, তাই এটি ঠিক 2n-এর বৃদ্ধি, উপপাদ্য ৩.১-এর মতো। এই হারে n = 40-এ সময় হবে প্রায় 6.9 · 46 ≈ ২৮,০০০ সেকেন্ড, অর্থাৎ প্রায় আট ঘণ্টা, শুধু ৪১ অক্ষরের একটি ইনপুটে। RE2-এর কলাম পুরোটা সময় ০.১ মিলিসেকেন্ডের নিচে, আর তার মধ্যে pattern compile করার সময়ও আছে। দুই engine-এর উত্তর একই, “মিল নেই”।

দ্বিতীয় script তিনটি জিনিস দেখায়: Python-এর ভেতরের তিন প্রতিকার n = 26-এ, RE2-তে ইনপুট হাজার গুণ বাড়ালে কী হয়, আর backreference চাইলে RE2 কী বলে।

import re, sys, time
import re2

def secs(f, *a):
    t = time.perf_counter(); r = f(*a); return time.perf_counter() - t, r

s = "a" * 26 + "b"                       # the n = 26 input from the table
for name, pat in [("nested    ", r"^(a+)+$"), ("atomic    ", r"^(?>a+)+$"),
                  ("possessive", r"^(a++)+$"), ("rewritten ", r"^a+$")]:
    t, r = secs(re.match, pat, s)
    print(f"re {name} {pat:11} {t:9.5f} s  match: {r is not None}")

rx = re2.compile(r"^(a+)+$")             # linear: grow the input 1000x
for n in (1_000, 100_000, 1_000_000):
    t, r = secs(rx.match, "a" * n + "b")
    print(f"re2 n = {n:>9,}  {t:.5f} s  match: {r is not None}")
try:
    re2.compile(r"^(a+)b\1$")            # a backreference
except Exception as e:
    print("re2 backreference:", type(e).__name__, str(e)[:48])
print("re  backreference:", bool(re.match(r"^(a+)b\1$", "aaabaaa")),
      bool(re.match(r"^(a+)b\1$", "aaabaa")))

সত্যিকারের run (একই প্রকল্প; RE2-এর নিজের log-লাইনের সময়-অংশ “…” দিয়ে ছাঁটা):

~/bazarghar-toc$ uv run python fixes.py
E… re2.cc:242] Error parsing '^(a+)b\1$': invalid escape sequence: \1
re nested     ^(a+)+$       1.71131 s  match: False
re atomic     ^(?>a+)+$     0.00009 s  match: False
re possessive ^(a++)+$      0.00004 s  match: False
re rewritten  ^a+$          0.00002 s  match: False
re2 n =     1,000  0.00004 s  match: False
re2 n =   100,000  0.00013 s  match: False
re2 n = 1,000,000  0.00137 s  match: False
re2 backreference: Error b'invalid escape sequence: \\1'
re  backreference: True False

একই ইনপুটে nested রূপ ১.৭ সেকেন্ড, আর তিন প্রতিকারের প্রতিটি ০.১ মিলিসেকেন্ডের নিচে: সময় প্রায় দশ হাজার গুণ কম। Atomic group (?>a+) একবার মেলার পর আর কোনো a ফেরত দেয় না, তাই ভাগ করার বিকল্পই থাকে না; possessive a++ একই কাজের সংক্ষিপ্ত লেখা। RE2-তে ইনপুট ১ লাখ থেকে ১০ লাখ, দশ গুণ, আর সময়ও প্রায় দশ গুণ (0.00013 থেকে 0.00137): রৈখিক। 1000-এর মাপটি এত ছোট যে সেখানে ধ্রুবক খরচই বেশি। শেষ দুই লাইনে দামটি স্পষ্ট: RE2 \1 সমর্থনই করে না, pattern compile-এই ত্রুটি দেয়, আর re {anban}-এর “aaabaaa” গ্রহণ করে, “aaabaa” নয়।

তৃতীয় script তৃতীয় একটি backtracking engine নিয়ে: regex module (PyPI, licence Apache-2.0 AND CNRI-Python; সংস্করণ 2026.11.18), যা re-এর একটি বিকল্প আর যাতে মেলানোর জন্য একটি timeout দেওয়া যায়।

import regex, time
from importlib.metadata import version
print("regex", version("regex"))
for pat in (r"^(a+)+$", r"^(a|aa)+$"):
    for n in (20, 24, 28):
        t = time.perf_counter(); m = regex.match(pat, "a" * n + "b", timeout=5)
        print(f"{pat:11} n = {n}  {time.perf_counter() - t:.4f} s  match: {m is not None}")
t = time.perf_counter()
try:
    regex.match(r"^(a|aa)+$", "a" * 60 + "b", timeout=0.5)
    print("finished")
except TimeoutError as e:
    print(f"n = 60: TimeoutError after {time.perf_counter() - t:.2f} s: {e}")

সত্যিকারের run (একই প্রকল্প, regex 2026.11.18):

~/bazarghar-toc$ uv run python timeout_demo.py
regex 2026.11.18
^(a+)+$     n = 20  0.0002 s  match: False
^(a+)+$     n = 24  0.0000 s  match: False
^(a+)+$     n = 28  0.0000 s  match: False
^(a|aa)+$   n = 20  0.0022 s  match: False
^(a|aa)+$   n = 24  0.0146 s  match: False
^(a|aa)+$   n = 28  0.0991 s  match: False
n = 60: TimeoutError after 0.50 s: regex timed out

শিক্ষণীয় একটি ফল। এই module ^(a+)+$-এ দ্রুত: n = 28-এও প্রায় শূন্য সময়, যেখানে re-এর লেগেছিল প্রায় ৭ সেকেন্ড। অর্থাৎ এর ভেতরে এই আকারের জন্য কোনো বিশেষ optimisation আছে। কিন্তু ^(a|aa)+$-এ আবার বিস্ফোরণ: প্রতি চার ধাপে প্রায় ৬.৬–৬.৮ গুণ, Fibonacci-র 1.6184 ≈ 6.85-এর কাছাকাছি, অংশ ৩-এর মতো। Optimisation কিছু আকার ধরে, সব নয়; তাই এটি নিশ্চয়তা নয়। শেষ লাইনে timeout কাজ করেছে: n = 60-এ মাপটি শেষ হতে উপরের হারে পাঁচ দিনের বেশি লাগার কথা, কিন্তু ঠিক ০.৫ সেকেন্ডে TimeoutError. (প্রকল্পের venv কাজ শেষে মুছে ফেলা হয়েছে।)

৮ · প্রতিরক্ষার স্তর — কোনটি কখন

কোনো একটি কৌশল একা যথেষ্ট নয়, তাই নিরাপদ ব্যবস্থায় কয়েকটি স্তর থাকে। প্রতিটির পেছনের তত্ত্ব আর সীমা:

কৌশলকেন কাজ করেসীমা
Pattern দ্ব্যর্থহীন করে আবার লেখাপ্রতিটি string-এর একটিমাত্র ভাগ, তাই পিছিয়ে চেষ্টার বিকল্প থাকে নাপ্রতিটি pattern-এ আলাদা চিন্তা; language না বদলানো নিশ্চিত করতে brute-force বা automaton-সমতা (পর্ব ২০)
Atomic group, possessive quantifierএকবার মেলা অংশ ফেরত দেওয়া বন্ধসব engine-এ নেই (প্রচলিত JavaScript-এ এই লেখার সময় নেই); ভুল জায়গায় দিলে language বদলে যায়
রৈখিক engine (RE2, Go, Rust, .NET-এর NonBacktracking)উপপাদ্য ৪.১: সময় |R| · m-এর অনুপাতেbackreference, lookaround নেই; বিশাল |R| (যেমন a{1000}-এর মতো গোনা পুনরাবৃত্তি) নিজেই খরচ বাড়ায়
ইনপুটের দৈর্ঘ্যের সীমা2n-এ n ছোট রাখাশুধু সময় কমায়; n = 30-ও বিপজ্জনক হতে পারে
Timeout বা ধাপের সীমাসবচেয়ে খারাপ ক্ষেত্রের ওপর একটি ঢাকনাসব library-তে নেই (Python-এর re-তে নেই); timeout-এর আগ পর্যন্ত CPU তো খরচ হয়ই
Static analysis আর fuzzingNFA-র ambiguity খুঁজে দুর্বল pattern আগেই ধরা; দৈব দুষ্ট ইনপুটে মাপাভুল সতর্কসংকেত বা কিছু বাদ পড়া সম্ভব; fuzzing-এর পদ্ধতি Software Testing কোর্সের পর্ব ৬০-এ

আরও গভীরে: কোন NFA কতটা “ambiguous”, তার একটি সুন্দর গাণিতিক উত্তর আছে। Weber আর Seidl-এর ১৯৯১ সালের একটি প্রবন্ধে দেখানো হয়েছে বলে সুপরিচিত: একটি ε-ছাড়া NFA-তে (অপ্রয়োজনীয় state বাদ দেওয়ার পর) দৈর্ঘ্য n-এর string-এর গ্রহণযোগ্য পথ সর্বোচ্চ exponential হারে বাড়ে ঠিক তখন, যখন কোনো state থেকে একই label-এর দুটি ভিন্ন লুপ সেই state-এ ফেরে; নইলে বৃদ্ধি বড়জোর বহুপদী। এই শর্তটি product automaton-এ (পর্ব ০৮) দক্ষভাবে যাচাই করা যায়, আর অনেক static ReDoS checker এই ধারণার ওপর দাঁড়িয়ে। তবে বাস্তব engine-এর optimisation আর lookaround-এর কারণে “তত্ত্বে ambiguous” আর “বাস্তবে ধীর” সবসময় এক নয়, অংশ ৭-এর regex module যেমন দেখাল।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • ^(a+)+$ কেন ধীর, কত ধীর? an-এর 2n−1টি ভাগ; শেষে ব্যর্থ হলে সব চেষ্টা, মোট 2n − 1টি $ পরীক্ষা।
  • Backtracking আর NFA simulation-এর পার্থক্য? প্রথমটি পথ ধরে (সবচেয়ে খারাপ exponential), দ্বিতীয়টি (state, অবস্থান) জোড়া ধরে (|R| · m).
  • RE2 backreference সমর্থন করে না কেন? Backreference-এর language non-regular, আর তা মেলানো NP-complete বলে জানা; রৈখিক নিশ্চয়তা রাখতে সেটি বাদ।
  • একটি দুর্বল regex ঠিক করুন। একই অংশ দুভাবে মেলার উৎস খুঁজুন; প্রতিটি পুনরাবৃত্তি একটি আলাদা চিহ্ন দিয়ে শুরু করান, তারপর brute force-এ language-সমতা যাচাই করুন।
  • ReDoS থেকে বাঁচার উপায়? দ্ব্যর্থহীন pattern, atomic group বা রৈখিক engine, দৈর্ঘ্যের সীমা, timeout, আর test-এ দুষ্ট ইনপুট।

৯ · AI-এর যুগে regex engine আর ReDoS

AI assistant দ্রুত regex লিখে দেয়, আর বেশিরভাগ সময় সেগুলো সাধারণ ইনপুটে ঠিক কাজ করে। ঝুঁকি থাকে দুই জায়গায়: language-এ সূক্ষ্ম ভুল, আর এমন নকশা যা ব্যর্থ মিলে বিস্ফোরিত হয়। এই বিষয়ে যে ভুলগুলো বারবার দেখা যায়:

AI-এর ভুলকীভাবে ধরবেন
“Validator”-এ ([…]+-?)+ বা (\w+\s?)*-এর মতো nested quantifierলম্বা “প্রায় মিল” + একটি ভুল চিহ্ন দিয়ে সময় মাপা
“ঠিক করা” pattern-এ language বদলে ফেলা, যেমন শেষের হাইফেন বা ফাঁকা string হারানোপুরোনো আর নতুন pattern-কে ছোট alphabet-এ দৈর্ঘ্য ≤ 8-এর সব string-এ মেলানো
“এই pattern-এ nesting নেই, তাই নিরাপদ” বলা(a|a)*b-এর মতো overlapping alternation আর a*a*-এর মতো বর্গ-সময় খোঁজা
JavaScript-এ atomic group বা Python-এর পুরোনো সংস্করণে possessive quantifier প্রস্তাবনিজের runtime-এর সংস্করণ আর নথি দেখা; চালিয়ে দেখা
RE2 বা Rust-এর regex-এ backreference বা lookaround ব্যবহারমনে রাখা: রৈখিক engine এগুলো ইচ্ছা করে বাদ দেয়
“Python-এর re টাইমআউট দেয়” বা বানানো benchmark-সংখ্যানথি দেখা আর নিজের যন্ত্রে মাপা

AI-কে ভালোভাবে কাজে লাগানোর উপায়: শুধু pattern না চেয়ে তার দ্ব্যর্থহীনতার যুক্তি, একটি দুষ্ট ইনপুট আর একটি স্বাধীন যাচাইয়ের কোড চাওয়া।

আমি গণনার তত্ত্ব শিখছি। বাজারঘরের অর্ডার-নোটের জন্য Python-এর re-তে একটি validator দরকার: এক বা একাধিক শব্দ (প্রতিটি শব্দ a-z বা অঙ্কের এক বা বেশি অক্ষর), শব্দের মাঝে ঠিক একটি space, শুরু বা শেষে space নয়। ১. একটি regex দাও, আর ব্যাখ্যা করো কেন প্রতিটি বৈধ string ঠিক একভাবে মেলে (অর্থাৎ pattern-টি ambiguous নয়)। ২. ^(\w+\s?)*$ ধরনের একটি নকশা কেন ReDoS-প্রবণ, তা একটি দুষ্ট ইনপুট দিয়ে দেখাও, আর ভাগ করার উপায় গুনে বলো। ৩. শুধু standard library দিয়ে একটি ছোট Python কোড দাও, যা alphabet {a, 1, space}-এ দৈর্ঘ্য ≤ 8-এর সব string-এ তোমার regex আর একটি সাধারণ Python ফাংশন (split দিয়ে লেখা নিয়ম)-এর উত্তর মেলায়। ৪. তোমার regex-কে দৈর্ঘ্য 20, 40, 80-এর একটি দুষ্ট ইনপুটে মাপার কোড দাও, প্রতিটি মাপ ১ সেকেন্ডের বেশি হলে থামার শর্তসহ। ৫. কোন Python সংস্করণ থেকে atomic group আর possessive quantifier আছে, আর কোন নথিতে লেখা, তা বলো।

(নিজে যাচাই করুন: একটি দ্ব্যর্থহীন উত্তর ^[a-z0-9]+( [a-z0-9]+)*$; উত্তরের ৫ নম্বরের সঠিক জবাব Python 3.11, তার “What’s New” নথিতে।)

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১Thompson ১৯৬৮ সালেই রৈখিক পদ্ধতি দেখিয়েছিলেন। তবু Python, Java আর JavaScript-এর মতো জনপ্রিয় ভাষার engine backtracking কেন?

ইতিহাসটি দুই ধারার। Ken Thompson-এর ১৯৬৮ সালের প্রবন্ধে regex থেকে NFA বানিয়ে state-এর সেট ধরে চালানোর পদ্ধতি ছিল, আর Unix-এর প্রথম দিকের কিছু টুল সেই ধারায় চলে। অন্যদিকে ১৯৮০-এর দশকে Henry Spencer-এর লেখা একটি মুক্ত regex library ছড়িয়ে পড়ে, যা backtracking দিয়ে চলত বলে উল্লেখ আছে, আর Perl-এর regex-ও এই ধারায় বড় হয়। Backtracking engine-এ নতুন সুবিধা যোগ করা খুব সহজ: backreference, lookaround, lazy quantifier, এমনকি recursion; প্রতিটি শুধু search-এর আরেকটি নিয়ম। Perl-এর জনপ্রিয়তার সঙ্গে এই সুবিধাগুলো “regex”-এর স্বাভাবিক অংশ হয়ে যায়, আর পরের ভাষাগুলো সামঞ্জস্যের জন্য একই আচরণ নেয়।

তত্ত্বও এখানে একটি কারণ দেয়। Backreference-এর language regular নয়, আর তা মেলানো সাধারণভাবে NP-complete বলে জানা; তাই যে engine সব সুবিধা দিতে চায়, তার পক্ষে সব pattern-এ দ্রুত হওয়ার নিশ্চয়তা দেওয়া সম্ভব নয়, যদি না P = NP, যা খোলা প্রশ্ন। ফলে নকশাকারদের সামনে একটি সত্যিকারের বাছাই: হয় সব সুবিধা আর কিছু pattern-এ বিস্ফোরণের ঝুঁকি, নয়তো সীমিত সুবিধা আর রৈখিক নিশ্চয়তা।

দ্বিতীয় পথটি আবার আলোচনায় আসে Russ Cox-এর ২০০৭ সালের বহুল পঠিত প্রবন্ধ “Regular Expression Matching Can Be Simple And Fast” থেকে, যেখানে তিনি দেখান কিছু pattern-এ backtracking engine কত ধীর আর Thompson-এর পদ্ধতি কত স্থির। ২০১০ সালে RE2 মুক্ত করা হয়, Go-র regexp একই নীতিতে চলে, আর Rust-এর regex crate-ও রৈখিক নিশ্চয়তা দেয়। পুরোনো engine-গুলোতেও পরিবর্তন এসেছে: .NET 7 একটি NonBacktracking বিকল্প আনে, আর V8 JavaScript engine-এ একটি পরীক্ষামূলক non-backtracking engine-এর কথা তাদের ২০২১ সালের একটি blog-এ বলা হয়েছে। Python-এর re এখনো backtracking, তবে ৩.১১ থেকে atomic group আর possessive quantifier দিয়ে প্রোগ্রামার নিজে বিকল্প কমাতে পারেন।

মূল উপলব্ধি: Engine-এর পরিবার একটি প্রকৌশলী বাছাই, যার পেছনে ইতিহাস, সামঞ্জস্য আর একটি গাণিতিক সীমা আছে: বাড়তি ক্ষমতা (backreference) আর সবসময় দ্রুত হওয়ার নিশ্চয়তা একসঙ্গে পাওয়ার কোনো জানা উপায় নেই।

প্র ০২Lookahead-সহ regex কি এখনো regular? Automaton-ভিত্তিক engine lookaround আর capture group নিয়ে কী করে?

তত্ত্বে উত্তর পরিষ্কার: backreference না থাকলে lookahead language-কে regular-এর বাইরে নেয় না। একটি সহজ উদাহরণে দেখুন। ^(?=.*\d)[a-z0-9]{6}$ মানে “ছয় অক্ষরের, আর অন্তত একটি অঙ্ক আছে”। এটি দুটি regular language-এর intersection: “ছয়টি a–z বা অঙ্ক” আর “কোথাও একটি অঙ্ক”। পর্ব ১৬-এ দেখেছেন, regular language intersection-এ closed: দুটি DFA-র product construction (পর্ব ০৮) একটি DFA দেয়। সাধারণভাবে, বিভিন্ন অবস্থানে বসা lookahead-কে alternating automaton বা আরও কিছু state দিয়ে প্রকাশ করা যায়, আর ফল regular থাকে বলে সাহিত্যে প্রমাণ আছে; যদিও automaton-টি অনেক বড় হতে পারে।

সমস্যাটি তাহলে প্রকৌশলের। Set-of-states simulation ইনপুট একবার বাঁ থেকে ডানে পড়ে, আর প্রতিটি অবস্থানে শুধু “এ পর্যন্ত কী মিলেছে” জানে। Lookahead জানতে চায় “সামনে কী আছে”, যা তখনো পড়া হয়নি। এর সমাধান আছে, যেমন সামনের শর্তকে আলাদা একটি যন্ত্র হিসেবে পাশাপাশি চালানো, বা ডান থেকে বাঁয়ে একটি বাড়তি পাস; কিন্তু তাতে কোড আর খরচ বাড়ে। RE2 আর Rust-এর regex তাই lookaround রাখেনি; অন্যদিকে গবেষণায় ও কিছু নতুন engine-এ রৈখিক সময়ে lookaround বসানোর পদ্ধতি প্রস্তাবিত হয়েছে।

Capture group-এর প্রশ্নটি অন্য রকম। এখানে language বদলায় না; জানতে হয় মিলের কোন অংশ কোন group-এ পড়ল। একটি NFA-তে বহু পথ একই সময়ে চলে, আর প্রতিটি পথের group-সীমা আলাদা হতে পারে। সমাধান হলো প্রতিটি state-এর সঙ্গে একটি ছোট “tag” তালিকা বহন করা, আর দুটি পথ একই state-এ মিললে নিয়ম মেনে একটি রাখা: leftmost-first হলে যে পথ backtracking-এর ক্রমে আগে আসত। এই ধরনের পদ্ধতিকে প্রায়ই Pike VM বলা হয়, Rob Pike-এর ১৯৮০-এর দশকের একটি editor-এর কাজের সূত্রে; আর Ville Laurikari-র ২০০০ সালের দিকের tagged NFA-র কাজ একই প্রশ্নের একটি গাণিতিক রূপ দেয়। এতে সময় এখনো |R| · m-এর অনুপাতে থাকে, শুধু ধ্রুবক বাড়ে।

মূল উপলব্ধি: বাস্তব regex-এর সুবিধাগুলো তিন ভাগে পড়ে: যা শুধু সংক্ষেপ (character class), যা regular থেকেও automaton-এ বসানো কঠিন (lookaround, capture-এর অর্থ), আর যা regular-এর বাইরে (backreference). কোনো engine-কে বিচার করতে হলে জানতে হবে সে কোন ভাগের কতটা দেয়।

প্র ০৩Timeout থাকলেই কি ReDoS-এর সমস্যা মিটে যায়? রৈখিক engine ব্যবহার করলে কি আর কোনো সীমা লাগে না?

Timeout একটি জরুরি ঢাকনা, সমাধান নয়। প্রথম কারণ খরচ: অংশ ৭-এর regex module ঠিক ০.৫ সেকেন্ডে থেমেছিল, কিন্তু সেই ০.৫ সেকেন্ড একটি CPU core পুরো ব্যস্ত ছিল। একজন আক্রমণকারী প্রতি সেকেন্ডে কয়েকটি এমন অনুরোধ পাঠালে কয়েকটি core-ই সবসময় ব্যস্ত থাকবে; denial of service ঘটতে পুরো আটকে যাওয়া লাগে না। দ্বিতীয় কারণ সঠিকতা: timeout হলে উত্তর আসে না, তাই program-কে ঠিক করতে হয় তখন কী করবে, কুপন বাতিল নাকি গ্রহণ। ভুল সিদ্ধান্ত নিলে একটি নিরাপত্তা-ফাঁক তৈরি হতে পারে। তৃতীয় কারণ প্রাপ্যতা: Python-এর re-তে timeout নেই, Java-র standard library-তেও সরাসরি নেই; .NET-এর Regex-এ একটি match timeout দেওয়া যায় আর PCRE-তে একটি match limit আছে।

রৈখিক engine বিস্ফোরণ দূর করে, কিন্তু খরচ শূন্য করে না। উপপাদ্য ৪.১-এর সময় |R| · m; m-এর ওপর কোনো সীমা না থাকলে ১০০ MB-এর একটি অনুরোধও রৈখিক সময়ে অনেকক্ষণ চলবে। আর |R| নিজেও বড় হতে পারে: (a|b){1000}-এর মতো গোনা পুনরাবৃত্তি Thompson NFA-তে প্রায় হাজার গুণ বড় হয়, কারণ গোনা পুনরাবৃত্তি আসলে concatenation-এর সংক্ষেপ। Lazy DFA ব্যবহার করলে cache-এর আকারও একটি প্রশ্ন; পর্ব ১০-এ দেখেছেন, কিছু language-এ subset-এর সংখ্যা ঘাতের হারে, তাই engine-গুলো cache-এর একটি সীমা রাখে আর সেটি ছাড়ালে ধীর পথে ফেরে।

তাই বাস্তবে কয়েকটি স্তর একসঙ্গে থাকে: ইনপুট গ্রহণের আগেই দৈর্ঘ্যের সীমা (কুপনে ৩২ অক্ষর, নামে ১০০), সম্ভব হলে রৈখিক engine, না হলে দ্ব্যর্থহীন pattern আর atomic group, তার ওপর timeout বা ধাপের সীমা, আর CI-তে দুষ্ট ইনপুটের regression test. শেষ স্তর হলো পর্যবেক্ষণ: কোনো endpoint-এ হঠাৎ CPU বাড়লে তা ধরতে পারা। এর একটি গাণিতিক শিক্ষাও আছে: সবচেয়ে খারাপ ক্ষেত্রের বিশ্লেষণ শুধু তত্ত্বের অনুশীলন নয়, প্রতিপক্ষ থাকলে সেটিই আসল ক্ষেত্র।

মূল উপলব্ধি: ReDoS-এর প্রতিরক্ষা একটি স্তরবদ্ধ নকশা। রৈখিক engine বিস্ফোরণ সরায়, দৈর্ঘ্যের সীমা m সীমিত করে, timeout বাকি ঝুঁকিতে ঢাকনা দেয়; কোনো একটি একা যথেষ্ট নয়।

প্র ০৪কোন pattern exponential, কোনটি শুধু বর্গ-সময়ে ধীর? এটি কি যন্ত্রিকভাবে ঠিক করা যায়?

অংশ ৩-এ তিন ধরনের আচরণ দেখেছেন: (a+)+ আর (a|a)*b exponential, (a|aa)*b-ও exponential কিন্তু ধীর ভিত্তিতে (1.618n), আর a*a*b শুধু বর্গ-সময়ের। Scratch-এ অংশ ৩-এর matcher দিয়ে a*a*b-কে an-এ মাপা হয়েছে: n = 50-এ 2757 ধাপ, 100-এ 10507, 200-এ 41007; n দ্বিগুণ হলে প্রায় চার গুণ, অর্থাৎ n2. পার্থক্যটি বোঝার চাবিকাঠি “ambiguity-র মাত্রা”: একটি string কতভাবে মেলে। a*a*-এ an-কে দুই ভাগে ভাগ করার উপায় n + 1, বহুপদী; (a+)+-এ 2n−1.

Weber আর Seidl ১৯৯১ সালে ε-ছাড়া NFA-র জন্য এর একটি পূর্ণ বর্ণনা দেন। একটি NFA “exponentially ambiguous” ঠিক তখন, যখন কোনো state q থেকে একই label w-এর দুটি ভিন্ন পথ আবার q-তে ফেরে: তখন wk পড়ার 2kটি উপায়। আর বহুপদী ambiguity আসে যখন দুটি ভিন্ন state p, q-এর প্রতিটিতে একই label-এর লুপ আছে আর p থেকে q-তে সেই label-এর পথ আছে; a*a*-এর দুই লুপ ঠিক এমন। এই শর্তগুলো যাচাই করা যায় NFA-কে নিজের সঙ্গে product করে, পর্ব ০৮-এর কৌশলে: জোড়া-state-এর graph-এ নির্দিষ্ট আকারের চক্র খোঁজা, যা বহুপদী সময়ের কাজ।

একটি সূক্ষ্ম কথা: কোন NFA-র ওপর পরীক্ষা হবে, তা গুরুত্বপূর্ণ। (a+)+-এর language a+, যার minimal DFA-তে কোনো ambiguity নেই; ambiguity আছে pattern-এর লেখার আকারে, যা backtracking engine অনুসরণ করে। তাই static ReDoS checker সাধারণত pattern থেকে এমন NFA বানায় যা গঠন ধরে রাখে (Thompson বা Glushkov-এর মতো, কিন্তু অবস্থানগুলো আলাদা রেখে), তারপর ambiguity খোঁজে, আর অনেক সময় একটি দুষ্ট ইনপুটও তৈরি করে দেয়। এমন tool বিভিন্ন ভাষার জন্য গবেষণা ও open-source জগতে আছে। সীমা: lookaround, backreference আর engine-এর নিজস্ব optimisation বিশ্লেষণকে জটিল করে, তাই ভুল সতর্কসংকেত বা বাদ পড়া দুটিই সম্ভব।

মূল উপলব্ধি: Backtracking-এর খরচ pattern-এর ambiguity-র মাত্রার প্রতিচ্ছবি; সেই মাত্রা (সসীম, বহুপদী বা exponential) automaton তত্ত্বের যন্ত্রে যাচাই করা যায়, ঠিক যেমন পর্ব ২০-এ emptiness বা equivalence যাচাই করেছেন।

প্র ০৫Backtracking-কে কি মনে রাখার কৌশলে (memoization) রৈখিক করা যায়? তাহলে backreference-এর NP-hardness কোথায় বাধা দেয়?

যায়, backreference না থাকলে। উপপাদ্য ৪.১-এর মূল পর্যবেক্ষণ ছিল: একটি অবস্থানে একই NFA state-এ পৌঁছানো দুটি পথের ভবিষ্যৎ এক। একটি backtracking matcher যদি NFA-র ওপর চলে আর একটি টেবিলে লিখে রাখে “(state q, অবস্থান i) থেকে আগে চেষ্টা করে ব্যর্থ হয়েছি”, তাহলে সেই জোড়ায় দ্বিতীয়বার এলে সঙ্গে সঙ্গে ফিরে আসতে পারে। জোড়া বড়জোর |Q| · (m + 1)টি, প্রতিটি একবার পুরো ঘোরা হয়, তাই মোট কাজ |R| · m-এর অনুপাতে, depth-first ক্রম আর leftmost-first অর্থ ঠিক রেখেই। RE2-এর ভেতরে ছোট ইনপুটের জন্য এমন একটি “bit-state” backtracker আছে বলে তাদের নথি আর বিশ্লেষণে উল্লেখ আছে, যার টেবিল একটি bit-array. গবেষণায় নির্বাচিত memoization দিয়ে প্রচলিত engine-এ ReDoS কমানোর প্রস্তাবও এসেছে (২০২১ সালের দিকের একটি নিরাপত্তা সম্মেলনের প্রবন্ধে), আর Ruby ৩.২-এ এই ধরনের একটি cache যোগ হয়েছে বলে তার release note-এ বলা আছে।

দাম মেমরি: টেবিলের আকার |Q| · m, যা লম্বা ইনপুটে বড়। তাই এমন কৌশল প্রায়ই ছোট ইনপুটে বা সীমিত আকারে ব্যবহৃত হয়।

Backreference এলে এই যুক্তি ভাঙে, কারণ ভবিষ্যৎ আর শুধু (q, i)-এর ওপর নির্ভর করে না; নির্ভর করে group-গুলো এখন কী মিলিয়েছে তার ওপর, আর সেই সম্ভাবনা ইনপুটের দৈর্ঘ্যের সঙ্গে বহু গুণে বাড়ে। সাধারণভাবে backreference-সহ মেলানো NP-complete বলে জানা আছে, তাই কোনো memoization সব pattern-এ বহুপদী সময় দেবে, এমন আশা করা যায় না, যদি না P = NP. তবে নির্দিষ্ট সংখ্যক backreference থাকলে বহুপদী সময়ের algorithm সম্ভব, যেখানে বহুপদের মাত্রা backreference-এর সংখ্যার সঙ্গে বাড়ে, এমন ফলও গবেষণায় আছে। পর্ব ৫৯-৬১-এ reduction আর NP-completeness পুরোপুরি আসবে; তখন এই দাবির অর্থ আরও পরিষ্কার হবে।

মূল উপলব্ধি: Backtracking-এর বিস্ফোরণ এসেছিল একই কাজ বারবার করা থেকে; (state, অবস্থান) মনে রাখলে regular pattern-এ তা রৈখিক হয়, যা আসলে automaton simulation-এরই আরেক রূপ। Backreference সেই “state”-কে অসীম বড় করে দেয়, আর সেখানেই complexity তত্ত্বের সীমা শুরু।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। প্রতিটি উত্তর উপরের JavaScript বা Python ব্লকে pattern বদলে যাচাই করতে পারেন।

  1. নকশা ও প্রমাণ: Σ = {a, b, c}-এর ওপর ^(a|ab|b)*c$. (ক) “abab”-কে (a ∪ ab ∪ b)∗-এর টুকরোয় কতভাবে ভাগ করা যায়? (ab)n-এ কতভাবে? (খ) একটি সমতুল্য, দ্ব্যর্থহীন regex দিন আর language-সমতা প্রমাণ করুন। (গ) কোন ইনপুট backtracking engine-কে ধীর করবে?

    (ক) প্রতিটি “ab” হয় একটি টুকরো [ab], নয়তো দুটি [a][b]; “ba”-র মাঝখানে কোনো টুকরো জোড়া হতে পারে না, কারণ “ba” কোনো শাখা নয়। তাই “abab”-এর ভাগ 2 · 2 = 4: [ab][ab], [ab][a][b], [a][b][ab], [a][b][a][b]. (ab)n-এ 2n.

    1. দাবি: L((a ∪ ab ∪ b)∗) = L((a ∪ b)∗) = {a, b}∗, তাই দ্ব্যর্থহীন রূপ ^[ab]*c$. — লক্ষ্য
    2. ⊆: প্রতিটি টুকরো a, ab বা b, প্রতিটিই {a, b}∗-এ; {a, b}∗ concatenation-এ closed, তাই টুকরো জোড়া string-ও। — star-এর সংজ্ঞা
    3. ⊇: {a, b}∗-এর যেকোনো string-কে এক-অক্ষরের টুকরোয় ভাঙা যায়, আর a, b দুটিই শাখা। ∎ — প্রতিটি অক্ষর একটি টুকরো

    (গ) (ab)n, তারপর এমন একটি চিহ্ন যা c নয়, যেমন “abababab!”: 2n ভাগের সব চেষ্টা হয়। Scratch-এ অংশ ৩-এর matcher দিয়ে মাপা: n = 4, 8, 12-এ 339, 5619, 90099 ধাপ, প্রতি চার ধাপে প্রায় ১৬ গুণ, অর্থাৎ 2n. নতুন রূপ [ab]*-এ প্রতিটি অক্ষরের একটিই উপায়।

  2. প্রমাণের ভুল ধরুন: দাবি: “যে regex-এ কোনো quantifier আরেকটি quantifier-এর ভেতরে নেই, backtracking engine তাতে কখনো exponential সময় নেয় না।” যুক্তি: “Exponential সময় আসে ভেতরের আর বাইরের quantifier একই অক্ষর ভাগাভাগি করলে, যেমন (a+)+. Nesting না থাকলে প্রতিটি অক্ষর একটিমাত্র quantifier-এর, তাই ভাগের উপায় একটিই। ∎” ভুল কোথায়? পাল্টা-উদাহরণ দিন।

    ভুলটি “প্রতিটি অক্ষর একটিমাত্র quantifier-এর, তাই ভাগের উপায় একটিই” কথায়। Ambiguity শুধু nested quantifier থেকে আসে না; একই quantifier-এর ভেতরের দুটি শাখা যদি একই string মেলায়, তাহলেও প্রতিটি পুনরাবৃত্তিতে একটি বাছাই থাকে। পাল্টা-উদাহরণ (a|a)*b: একটিই quantifier, কোনো nesting নেই, অথচ an-এর প্রতিটি a-কে দুই শাখার যেকোনোটি দিয়ে মেলানো যায়, তাই 2nটি পথ। অংশ ৩-এর ব্লক n = 16-এ 524286 ধাপ মেপেছে, যা 219 − 2. (a|aa)*b-ও nesting ছাড়া exponential (Fibonacci হারে)।

    সঠিক রূপ: “ambiguity-র মাত্রা” দেখতে হয় (প্র ০৪): কোনো অংশ পুনরাবৃত্তির ভেতরে দুভাবে মেলাতে পারলে exponential বিপদ। আরও একটি সূক্ষ্মতা: nesting না থাকলেও a*a*b-এর মতো pattern বর্গ-সময় নেয়, যা “কখনো exponential নয়” দাবির সঙ্গে সাংঘর্ষিক নয়, কিন্তু “নিরাপদ” বলার পক্ষে যথেষ্টও নয়।

  3. আউটপুট অনুমান: অংশ ৩-এর two_engines.js-এ ইনপুটের তালিকা [4, 8, 12, 16]-এর বদলে [5, 6, 20] দিলে (a+)+-এর লাইনে backtrack আর sets কলামে কত আসবে? (a|a)*b-এ n = 5-এ কত? উপপাদ্য ৩.১ অনুযায়ী n = 6-এ engine কতবার $ পরীক্ষা করে?

    আউটপুটের সূত্র 3 · 2n (backtrack) আর 3 + 5n (sets). n = 5: 96 আর 28; n = 6: 192 আর 33; n = 20: 3 · 220 = 3145728 আর 103. কিন্তু সাবধান: 3145728 > 2000000, তাই এই ব্লকের নিরাপত্তা-সীমা আগেই কাজ করবে; matcher থেমে “stopped” ছাপবে আর steps কলামে দেখাবে 2000001. (a|a)*b-এ n = 5: 28 − 2 = 254. উপপাদ্য ৩.১-এ n = 6: 26 − 1 = 63টি $ পরীক্ষা। Scratch-এ সীমা তুলে দিয়ে চালিয়ে n = 5-এ 96 আর 254, n = 20-এ 3145728 মেলানো হয়েছে; সীমাসহ ব্লকে n = 20-এর লাইনটিও মিলিয়ে দেখা হয়েছে।

  4. Trace: অংশ ৩-এর কোডের নিয়মে (a|a)*b-এর Thompson NFA-তে state-গুলো q0–q9: q0 –a→ q1, q2 –a→ q3; union-এর শুরু q4 (ε: q4 → q0, q2) আর শেষ q5 (ε: q1, q3 → q5); star-এর শুরু q6 আর শেষ q7 (ε: q6 → q4, q6 → q7, q5 → q7, q5 → q4); তারপর ε: q7 → q8 আর q8 –b→ q9. শুরু q6, accepting q9. “aab” আর “aa”-তে প্রতিটি অক্ষরের পর ε-closure-সহ সেট লিখুন।

    শুরু: E({q6}) = {q0, q2, q4, q6, q7, q8}: q6 থেকে q4 আর q7, q4 থেকে q0 আর q2, q7 থেকে q8. প্রথম a: q0 → q1 আর q2 → q3; closure-এ q5, তারপর q4, q7, আবার q0, q2, q8: {q0, q1, q2, q3, q4, q5, q7, q8}. দ্বিতীয় a: একই দুই তীর, একই সেট। b: শুধু q8 → q9, আর q9 থেকে কোনো তীর নেই: {q9}. q9 accepting, তাই “aab” গৃহীত। “aa”-তে শেষ সেট {q0, q1, q2, q3, q4, q5, q7, q8}, q9 নেই: বাতিল। লক্ষ করুন, backtracking-এ “aa”-র 22টি পথ আলাদা চেষ্টা হতো; সেটে তারা q1 আর q3 হয়ে একই closure-এ মিশে যায়। Scratch-এর simulation-এ এই সেটগুলোই এসেছে।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমএকটি ReDoS-প্রবণ validator নিরাপদ করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Pattern-এ এমন অংশ খোঁজা যা একই string একাধিক উপায়ে মেলায়
  2. লম্বা “প্রায় মিল” আর শেষে একটি ভুল চিহ্ন দিয়ে নিজের যন্ত্রে সময় মেপে সমস্যা নিশ্চিত করা
  3. প্রতিটি পুনরাবৃত্তি একটি আলাদা চিহ্ন দিয়ে শুরু করিয়ে দ্ব্যর্থহীন pattern লেখা
  4. পুরোনো আর নতুন pattern-কে সব ছোট string-এ brute force-এ মেলানো
  5. দৈর্ঘ্যের সীমা আর দুষ্ট ইনপুটের regression test যোগ করা

একটি backtracking regex engine ^(a+)+$-কে ইনপুট anb-তে চালায়। “মিল নেই” বলার আগে সে an-কে কতগুলো ভিন্ন উপায়ে অশূন্য টুকরোয় ভাগ করে দেখে?

  • n
  • n2
  • 2n−1
  • n!

RE2, Go-র regexp আর Rust-এর regex কোন বাস্তব regex সুবিধাটি ইচ্ছাকৃতভাবে সমর্থন করে না, কারণ তা কোনো finite automaton দিয়ে করা যায় না?

  • Character class, যেমন [0-9]
  • Backreference, যেমন \1
  • Anchor, যেমন ^ আর $
  • গোনা পুনরাবৃত্তি, যেমন {4}

|R| আকারের একটি regex-এর (backreference ছাড়া) Thompson NFA-কে state-এর সেট ধরে দৈর্ঘ্য m-এর ইনপুটে চালালে সবচেয়ে খারাপ সময় কোন অনুপাতে?

  • 2m
  • 2|R| · m
  • m, |R|-এর ওপর নির্ভর না করে
  • |R| · m

বাজারঘরের কুপন validator ^([A-Z0-9]+-?)+$ ReDoS-প্রবণ। নিচের কোনটি একই language গ্রহণ করে আর দ্ব্যর্থহীন?

  • ^[A-Z0-9]+(-[A-Z0-9]+)*-?$
  • ^[A-Z0-9]+(-[A-Z0-9]+)*$
  • ^([A-Z0-9]+)*-?$
  • ^[A-Z0-9-]+$

Python 3.11 থেকে re-তে লেখা যায় (?>a+). এর অর্থ কী?

  • সামনে a+ আছে কি না দেখা, কিছু না খেয়ে
  • যত কম সম্ভব a নেওয়া
  • একবার মেলার পর ভেতরের অংশ আর কোনো অক্ষর ফেরত দেয় না
  • a+ মিলটিকে ১ নম্বর group হিসেবে মনে রাখা

একটি backtracking engine-এ নিচের কোন pattern-এ, পুরো string না মেলা লম্বা ইনপুটে, চেষ্টার সংখ্যা ইনপুটের দৈর্ঘ্যের সঙ্গে exponential হারে বাড়তে পারে, যদিও এতে কোনো nested quantifier নেই?

  • ^[ab]*c$
  • ^(a|a)*b$
  • ^a*a*b$
  • ^(ab|cd)*$

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. দুই পরিবার: backtracking (Python re, Java, JavaScript, PCRE) একবারে একটি পথ; automaton-ভিত্তিক (RE2, Go, Rust) state-এর সেট ধরে সব পথ একসঙ্গে।
  2. ^(a+)+$ আর anb-তে ঠিক 2n − 1টি $ পরীক্ষা: ak-এর 2k−1টি composition, সব prefix মিলিয়ে।
  3. বিস্ফোরণের মূল ambiguity: একই string একাধিক উপায়ে মেলা, nested quantifier বা overlapping alternation থেকে, আর শেষে মিল ব্যর্থ।
  4. Set-of-states simulation |R| · m সময়ে, কারণ (state, অবস্থান) জোড়া সীমিত; দাম হলো backreference বাদ, যা non-regular আর NP-complete-ভাবে কঠিন।
  5. প্রতিরক্ষা স্তরে স্তরে: দ্ব্যর্থহীন pattern (brute force-এ সমতা যাচাইসহ), atomic group বা রৈখিক engine, দৈর্ঘ্যের সীমা, timeout আর দুষ্ট ইনপুটের test.

পরের পর্বে: Compiler-এর প্রথম ধাপ, lexical analysis. বাজারঘরের অর্ডার-খোঁজার ছোট ভাষার লেখাকে token-এ ভাঙা, প্রতিটি token-শ্রেণি একটি regex, আর সব মিলিয়ে একটি DFA, যা longest-match নিয়মে কাজ করে।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান