Sibuna पुस्तक 1.0.0-beta.3 दस्तावेज़
भाषा: हिन्दी
English简体中文한국어日本語EspañolDeutschहिन्दीالعربية
इस पृष्ठ पर

भाग VI: ऑटोमेटा, trie और सिमैंटिक फ़ायरवॉल

हम सब-माइक्रोसेकंड वर्गीकरण के पीछे के एल्गोरिदम की जाँच करते हैं: टैग किया गया Aho-Corasick ऑटोमेटन, IPv4/IPv6 radix trie, सिमैंटिक WAF के byte-class टोकनाइज़र, और WEIGH स्कोरिंग वाला घोषणात्मक नीति इंजन।

एक पास में अनेक पैटर्न का मिलान

सघन DFA के रूप में Aho-Corasick

Sibuna के पास लिटरल पैटर्न के दो समुच्चय हैं: लगभग चालीस बॉट सिग्नेचर और लगभग सौ आक्रमण सिग्नेचर। किसी फ़ील्ड को \(N\) पैटर्न से एक-एक करके जाँचना \(O(NM)\) है; Aho और Corasick (1975) का ऑटोमेटन failure link वाला trie बनाने के बाद उसे एक बार में \(O(M)\) में स्कैन करता है। Sibuna बिल्ड के समय failure link को ट्रांज़िशन टेबल में समाहित कर देता है, इसलिए स्कैन करना प्रति इनपुट बाइट एक टेबल लोड है, और पैटर्न समुच्चय पर कोई ब्रांच नहीं होती। ऑटोमेटन sibuna-patterns क्रेट में है:

/// `state` (एक पंक्ति ऑफ़सेट) से `byte` पढ़कर आगे बढ़ता है।
fn step(&self, state: usize, byte: u8) -> usize {
    self.table[state + usize::from(self.classes[usize::from(byte)])] as usize
}

pub fn find_first(&self, haystack: &[u8]) -> Option<Match> {
    let mut state = 0;
    for (index, &byte) in haystack.iter().enumerate() {
        state = self.step(state, byte);
        if state >= self.first_match {
            let id = self.first_output_in(self.match_state(state), self.all_tags)?;
            return Some(self.report(id, index + 1));
        }
    }
    None
}

एक अवस्था को एक सपाट टेबल में उसकी पंक्ति के ऑफ़सेट के रूप में रखा जाता है, इसलिए एक कदम एक जोड़ और एक लोड है। अवस्थाओं को इस तरह क्रमांकित किया जाता है कि हर मैच अवस्था बाकी सभी अवस्थाओं के बाद आए; तब मैच का पता लगाना first_match से एक तुलना भर है, और भीतरी लूप में कोई दूसरी टेबल लोड नहीं करनी पड़ती।

रूट से G और GP होते हुए GPTBot मैच अवस्था तक, और C और Cl होते हुए ClaudeBot मैच अवस्था तक जाने वाला एक trie; डैश वाले failure edge GP और Cl से वापस रूट तक जाते हैं।
चित्र 9 दो सिग्नेचर के लिए trie अवस्थाएँ और failure edge

ऑटोमेटन का अवस्था बजट एक रन-टाइम विकल्प है। नीति इंजन अधिकतम एक रूट और सभी सिग्नेचर की लंबाइयों का योग आरक्षित करता है, जो trie अवस्थाओं की एक सुरक्षित ऊपरी सीमा है। इससे ऐतिहासिक रूप से बहुत बड़ी निश्चित टेबल से बचा जाता है, और हर byte class के लिए सघन ट्रांज़िशन बना रहता है। हर पैटर्न एक छोटा श्रेणी टैग रखता है (0 से 63, ताकि टैग का समुच्चय एक 64-बिट शब्द हो)। case folding ऑटोमेटन के साथ बनी 256 प्रविष्टियों वाली byte-class टेबल का उपयोग करता है: किसी अक्षर के दोनों case एक class साझा करते हैं, और जो बाइट किसी पैटर्न में नहीं आते वे एक class साझा करते हैं, इसलिए टेबल की एक पंक्ति 256 के बजाय अलग-अलग पैटर्न बाइट की संख्या से एक अधिक चौड़ी होती है। इंजन के सटीक आकार और अनुक्रमिक सबस्ट्रिंग खोज से तुलना भाग VIII में दर्ज है। सबस्ट्रिंग खोज वही पैटर्न और any-match अर्थ (semantics) उपयोग करती है।

रेगुलर एक्सप्रेशन, SIMD इंजन और चुनाव

सिग्नेचर चरण के लिए तीन परिवारों को तौला गया:

  • बैकट्रैकिंग रेगुलर एक्सप्रेशन (बैकट्रैकिंग नियम-समुच्चय की शैली) प्रति अनुरोध सैकड़ों पैटर्न चलाते हैं और प्रति मैच आवंटन करते हैं; ये सबसे धीमा विकल्प हैं और false positive की सबसे अधिक संभावना इन्हीं में है।
  • SIMD लिटरल इंजन (Hyperscan, Vectorscan) shuffle पर आधारित nibble मास्क ("Teddy" एल्गोरिदम) से 16 से 32 बाइट के ब्लॉक को पहले छानते हैं और उम्मीदवारों का सत्यापन ऑटोमेटा से करते हैं। बड़े लिटरल समुच्चय वाले लंबे इनपुट पर ये बेहतरीन हैं। इसकी कीमत है कई मेगाबाइट की C++ निर्भरता, कंपाइल-टाइम पैटर्न डेटाबेस, कोई WebAssembly टारगेट नहीं, और सौ बाइट के इनपुट के लिए कोई लाभ नहीं: पूरा फ़ील्ड एक cache miss से कम समय में स्कैन हो जाता है।
  • सघन Aho-Corasick और छोटे संरचनात्मक टोकनाइज़र, libinjection की परंपरा, एक निश्चित टेबल में सटीक रैखिक-समय व्यवहार देते हैं और बाइनरी के बाहर किसी चीज़ की ज़रूरत नहीं रखते।

Sibuna के फ़ील्ड छोटे हैं, इसलिए तीसरा परिवार मेमोरी और गति दोनों में जीतता है; भाग VIII 8 KiB बॉडी पर लगभग 1.56 ns प्रति बाइट दर्ज करता है (सिमैंटिक स्कैन में 12,784.3 ns लगते हैं, benchmarks/results/primitives-latest.md में 8kb_body_semantic_scan)। यही एक वर्कलोड है जहाँ SIMD प्रीफ़िल्टर लाभ देगा, और SID 0006 इसे एक खुले बिंदु के रूप में रखता है।

IPv4 और IPv6 के लिए radix trie

128-बिट कुंजियों पर एक बाइनरी trie दोनों परिवारों की सेवा करता है: IPv6 प्रीफ़िक्स जैसे के तैसे डाले जाते हैं, IPv4 प्रीफ़िक्स ::ffff:0:0/96 में मैप किए जाते हैं, इसलिए एक /24 गहराई 120 का पाथ बन जाता है। नोड u32 से इंडेक्स किए गए एक सपाट Vec में रहते हैं, जिसमें इंडेक्स शून्य रूट भी है और "कोई चाइल्ड नहीं" भी, इसलिए एक लुकअप अधिकतम 128 आश्रित लोड है, बिना pointer chasing के। यह trie sibuna-cidr क्रेट का PrefixTrie है।

हर IPv4 लुकअप के लिए मैप किए गए प्रीफ़िक्स के 96 स्तरों पर चलना, IPv4 पते के पहले बिट तक पहुँचने से पहले ही 96 आश्रित लोड खर्च करेगा। इसलिए trie प्रारंभ होते समय गहराई 96 वाले नोड को दर्ज कर लेता है और IPv4 लुकअप वहीं से शुरू करता है:

let (mut node, mut depth, mut best) = if is_ipv4_mapped(key) {
    let start = self.ipv4_root;
    let value = self.nodes[start as usize].value.as_ref();
    (start, IPV4_DEPTH, value.or(self.nodes[0].value.as_ref()))
} else {
    (0, 0, self.nodes[0].value.as_ref())
};

IPv4 पते के वर्गीकरण में 32.0 ns और IPv6 पते में 79.3 ns लगते हैं (benchmarks/results/primitives-latest.md में ipv4_cidr_classification और ipv6_cidr_classification)। इंजन trie से दो बार परामर्श करता है: नियम टेबल से पहले अंतिम allow/deny निर्णयों के लिए, ताकि क्लस्टर-व्यापी प्रतिबंध हर नियम पर भारी पड़े, और उसके बाद challenge निर्णयों के लिए।

सिमैंटिक फ़ायरवॉल

False positive से एक सबक

WAF का पहला संस्करण हर हेडर पर सबस्ट्रिंग की एक सपाट सूची का मिलान करता था। सूची में /* था, और हर ब्राउज़र Accept: text/html,...,*/*;q=0.8 भेजता है। हर वास्तविक ब्राउज़र को SQL injection के रूप में वर्गीकृत किया गया और उसे 403 मिला। इस सबक ने डिज़ाइन को आकार दिया: कोई डिटेक्टर केवल संरचना पर सक्रिय हो सकता है, और परीक्षण सूट अब एक पूरा Chrome अनुरोध, जिसमें select, -- और एक एपॉस्ट्रॉफ़ी वाली कमेंट बॉडी शामिल है, इंजन से गुज़ारता है और पुष्टि करता है कि वह साफ़ निकलता है।

एक पास में byte class

हर निरीक्षित फ़ील्ड को एक बार स्कैन करके यह इकट्ठा किया जाता है कि कौन-सी byte class आती हैं: quote, =, <, shell separator, %, NUL, canonicalisation के ट्रिगर, और दोहरे स्पेस। हर डिटेक्टर दोबारा स्कैन करने के बजाय इन class से परामर्श करता है, और canonicalised दूसरा पास तभी चलता है जब कोई ट्रिगर दिखा हो। स्कैन प्रति बाइट 256 प्रविष्टियों वाली टेबल का एक लुकअप है, sibuna-policy के WAF मॉड्यूल से। चार accumulator OR शृंखलाओं को छोटा रखते हैं, और दो बाइट-जोड़ों (/* और दो सटे हुए स्पेस) को तभी खोजा जाता है जब किसी अकेले बाइट ने पहले ही canonicalisation की माँग न की हो:

pub(crate) fn scan(text: &[u8]) -> Classes {
    let (chunks, remainder) = text.as_chunks::<8>();
    // चार accumulator OR की शृंखलाएँ छोटी रखते हैं, ताकि लोड एक के बाद एक जारी हो सकें।
    let mut lanes = [0u16; 4];
    for chunk in chunks {
        lanes[0] |= TABLE[usize::from(chunk[0])] | TABLE[usize::from(chunk[4])];
        lanes[1] |= TABLE[usize::from(chunk[1])] | TABLE[usize::from(chunk[5])];
        lanes[2] |= TABLE[usize::from(chunk[2])] | TABLE[usize::from(chunk[6])];
        lanes[3] |= TABLE[usize::from(chunk[3])] | TABLE[usize::from(chunk[7])];
    }
    let mut bits = lanes[0] | lanes[1] | lanes[2] | lanes[3];
    for &byte in remainder {
        bits |= TABLE[usize::from(byte)];
    }
    // बाइट-जोड़े तभी तक मायने रखते हैं जब तक किसी अकेले बाइट ने canonicalisation की माँग न की हो।
    if bits & CANONICAL == 0
        && ((bits & SPACE != 0 && has_pair(text, b' ', b' '))
            || (bits & (SLASH | STAR) == SLASH | STAR && has_pair(text, b'/', b'*')))
    {
        bits |= CANONICAL;
    }
    Classes { bits }
}

डिटेक्टर

  • सिग्नेचर। हर श्रेणी के सभी मज़बूत सिग्नेचर एक टैग किए गए ऑटोमेटन में रहते हैं; हिट एक अंतिम deny है, जिसका नाम waf:sqli, waf:xss, waf:path-traversal या waf:rce होता है।
  • SQL injection। एक-पास वाला शब्द स्कैनर हर अल्फ़ान्यूमेरिक शब्द (अधिकतम सात बाइट) को कीवर्ड टेबल में खोजता है और or / and पर literal = literal tautology की जाँच करता है; id=1 or 1=1 अंतिम है। अन्यथा quote बाइट अनिवार्य है और साक्ष्य का स्कोर इनमें से कम से कम 4 होना चाहिए: quote (1), अधिकतम दो कीवर्ड (2), कमेंट मार्कर (1), एक = (1)। admin'-- अपने आप में अंतिम है। "it's a group order from the shop" का स्कोर 3 है और यह पास हो जाता है।
  • Cross-site scripting। < आवश्यक है; यह तब सक्रिय होता है जब स्क्रिप्ट रख सकने वाला कोई टैग एट्रिब्यूट की स्थिति में on<event>= एट्रिब्यूट के साथ आता है। onboarding=1 नहीं गिना जाता।
  • Command injection। एक separator आवश्यक है; यह तब सक्रिय होता है जब ;, |, &&, $(, backtick या newline के बाद कोई ज्ञात कमांड नाम आता है। status ok; done | next पास हो जाता है।
  • Path traversal। सिग्नेचर (../, ..%2f, /etc/passwd, id_rsa, ...) और साथ में NUL तथा %00।

जिन संरचनात्मक हेडर के व्याकरण में वैध रूप से quote और तारांकन होते हैं (Accept*, Content-Type, Sec-*, If-*, ...), उन्हें छोड़ दिया जाता है; पाथ, क्वेरी, User-Agent, अन्य हेडर और बॉडी के पहले 8 KB का निरीक्षण होता है, और जिन फ़ील्ड में percent escape, plus चिह्न, कमेंट ओपनर या समेटे जा सकने वाले whitespace हों, उन्हें 8 KB के स्टैक बफ़र में canonicalise करके दोबारा निरीक्षित किया जाता है, ताकि 1%27/**/UnIoN/**/SeLeCt और %252e%252e/ कच्चे सिग्नेचर पर सिमट जाएँ।

लागत

निरीक्षण की लागत इंजन को दिए गए फ़ील्ड और बाइट पर निर्भर करती है, केवल अनुरोधों की संख्या पर नहीं। बेंचमार्क अध्याय Gate, Shield और 8 KB बॉडी की स्थितियाँ अलग-अलग रिपोर्ट करता है। 8 KB की सीमा निरीक्षण की सीमा है, यह दावा नहीं कि अपलोड का शेष भाग सुरक्षित है। forward-auth का उपयोग करने वाले इनग्रेस को अनुरोध की प्रासंगिक जानकारी आगे भेजनी चाहिए; छोड़े गए बाइट का निरीक्षण यह प्रोसेस नहीं कर सकता।

घोषणात्मक नीति इंजन

नियम वैकल्पिक मानदंडों (पाथ पैटर्न, User-Agent पैटर्न, अधिकतम चार हेडर, अधिकतम आठ IPv4/IPv6 CIDR ब्लॉक, एक JA4 फ़िंगरप्रिंट या प्रीफ़िक्स) का संयोजन (AND) है, जिसमें एक एक्शन ALLOW, DENY, CHALLENGE या WEIGH, वर्क बिट्स में वैकल्पिक प्रति-नियम कठिनाई और एल्गोरिदम, और एक चिह्नित weight होता है। मूल्यांकन का क्रम:

  1. सिमैंटिक WAF (केवल Shield): उल्लंघन एक अंतिम deny है।
  2. प्रतिष्ठा trie: deny या allow प्रीफ़िक्स अंतिम हैं।
  3. क्रम से नियम: पहला अंतिम मैच लौटता है; WEIGH मैच जुड़ते जाते हैं।
  4. स्कोर: ऋणात्मक योग allow; \(\geq 40\) योग deny; \(\geq 10\) योग challenge, थ्रेशोल्ड से ऊपर हर 5 अंक पर एक अतिरिक्त वर्क बिट के साथ, अधिकतम छह।
  5. स्टैटिक बायपास पाथ, फिर trie के challenge निर्णय, फिर बॉट ऑटोमेटन।
  6. डिफ़ॉल्ट एक्शन, challenge, जब तक नीति फ़ाइल कुछ और न कहे।

बिल्ट-इन नियम /.well-known/*, /favicon.ico, /robots.txt और /__sibuna/* की अनुमति देते हैं, CF-Worker क्लाइंट और Amazonbot को अस्वीकार करते हैं, और हर Mozilla User-Agent को चैलेंज करते हैं: ब्राउज़र स्ट्रिंग को जाली बनाना मुफ़्त है, इसलिए उसे प्रवेश देने से गेट केवल सजावटी रह जाएगा।

{
  "default_action": "CHALLENGE",
  "waf": true,
  "thresholds": { "challenge_at": 10, "deny_at": 40, "bits_step": 5 },
  "ip_rules": { "10.0.0.0/8": "ALLOW", "2001:db8::/32": "DENY" },
  "rules": [
    { "name": "internal-api", "path": "/api/*", "headers": { "X-Api-Key": ".*" },
    "action": "ALLOW" },
    { "name": "checkout", "path": "/checkout/*", "action": "CHALLENGE",
      "challenge": { "difficulty": 20, "algorithm": "posw" } },
    { "name": "headless", "user_agent": "Headless", "action": "WEIGH", "weight": 30 },
    { "name": "no-language", "headers": { "Accept-Language": "" },
    "action": "WEIGH", "weight": -5 }
  ]
}

हल किया गया ट्रेस: वैध सत्र के साथ एन्कोड किया गया आक्रमण

वैध सत्र रखने वाले क्लाइंट से GET /search?q=%2527%2520OR%25201%253D1 पर विचार करें। पहले HTTP पार्सर पाथ और क्वेरी को उनके बाइट कॉपी किए बिना अलग करता है। स्थानीय सीमाएँ चलती हैं, फिर Shield अनुरोध का निरीक्षण करता है। percent चिह्न फ़ील्ड को canonicalization के लिए चिह्नित करता है। डिकोडिंग का एक पास %27%20OR%201%3D1 प्रकट करता है; दूसरा ' OR 1=1 प्रकट करता है।

अब टोकनाइज़र एक quote, कीवर्ड OR और बराबर लिटरल ऑपरेंड देखता है। अस्वीकृति एक अंतिम नीति परिणाम है। वैध सत्र इसे अनुमति में नहीं बदलता: सत्र जाँच केवल चैलेंज निर्णय का निपटारा करती है। स्टोरेज हुक एक सीमित घटना रिकॉर्ड कॉपी करता है; SQL बाद में चलता है। जब ऑरिजिन कनेक्शन निष्क्रिय हो, तब रिस्पॉन्स पाथ को इंजन स्नैपशॉट पकड़े रखने की ज़रूरत नहीं होती।