Towards the Systematic Testing of Regular Expression Engines
تقدم هذه الورقة ReTest، وهو إطار عمل يختبر محركات التعبيرات النمطية بشكل منهجي من خلال الجمع بين الفحص القائم على القواعد والاختبار التحولي للتغلب على قيود الاختبار التفاضلي والفحص الساذج، وبالتالي تحقيق تغطية برمجية أعلى وتحديد عيوب جديدة دون الاعتماد على الاتساق عبر التنفيذات المختلفة.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
تخيل أن لديك مكتبة ضخمة من "وصفات البحث". هذه الوصفات، التي تُسمى التعبيرات النمطية (أو "regex")، تُستخدم من قبل الحواسيب للبحث عن أنماط محددة في النصوص — مثل العثور على جميع عناوين البريد الإلكتروني في مستند ما أو التحقق من صحة كلمة مرور.
ولكي تعمل هذه الوصفات، تحتاج الحواسيب إلى محرك تعبيرات نمطية (Regex Engine). فكر في المحرك كطباخ فائق السرعة وشديد الصرامة، يقرأ وصفتك ويحاول طهي الطبق المثالي.
المشكلة؟ الطباخون يرتكبون الأخطاء. أحياناً يحرقون الطعام (يتسببون في تعطل الكمبيوتر)، وأحياناً يقدمون طبقاً خاطئاً (يعطون إجابة غير صحيحة)، وأحياناً يستخدمون وصفة تبدو جيدة ولكن من المستحيل اتباعها في الواقع.
هذه الورقة البحثية، بعنوان "نحو الاختبار المنهجي لمحركات التعبيرات النمطية"، تتحدث عن بناء طريقة أفضل لاختبار هؤلاء الطباخين قبل أن يبدأوا في الطهي الفعلي.
إليك قصة حلهم، مقسمة إلى أجزاء بسيطة:
1. المشكلة: "اختبار التذوق" معطل
حالياً، عندما يريد مهندسو البرمجيات التحقق مما إذا كان محرك التعبيرات النمطية يعمل بشكل صحيح، فإنهم يستخدمون طريقتين رئيسيتين، وكلتاهما تعاني من عيوب كبيرة:
طريقة "التقليد" (الاختبار التفاضلي - Differential Testing):
تخيل أن لديك طباخين، الطباخ (أ) والطباخ (ب). تعطيهما نفس الوصفة ونفس المكونات. إذا أنتجا أطباقاً مختلفة، تفترض أن أحدهما مخطئ.- العيب: في عالم التعبيرات النمطية، لا يوجد كتاب وصفات واحد "رسمي". قد يتبع الطباخ (أ) قواعد "الأسلوب البريطاني"، بينما يتبع الطباخ (ب) قواعد "الأسلوب الأمريكي". قد يكون كلاهما على حق، لكن بأسلوب مختلف! طريقة "التقليد" تصاب بالارتباك، وتظن أن الاختلاف في الأسلوب هو خطأ، مما يؤدي إلى الكثير من الإنذارات الكاذبة.
طريقة "اللطخة العشوائية" (الفحص العشوائي الساذج - Naive Fuzzing):
تخيل أنك تحاول كسر قفل عن طريق رمي حفنات عشوائية من الطين عليه. قد تصيب ثقب المفتاح بالصدفة، لكنك في الغالب تثير الفوضى فقط.- العيب: أدوات الاختبار الحالية غالباً ما ترمي مجرد رموز عشوائية على المحرك. وبما أن وصفات التعبيرات النمطية لها قواعد لغوية صارمة جداً (مثل لغة معقدة)، فإن 99% من هذه النصوص العشوائية هي مجرد كلام فارغ. المحرك ببساء يقول: "هذه ليست وصفة صالحة"، ثم يتجاهلها. وهكذا لا يصل المحرك أبداً إلى الجزء الذي يقوم فيه فعلياً بـ "الطهي" (المطابقة)، فتظل الأخطاء الخطيرة مخفية.
2. الحل: تعرف على "ReTest"
قام المؤلفون ببناء إطار عمل جديد للاختبار يسمى ReTest. فكر فيه كـ مفتش خارق يجمع بين تقنيتين قويتين:
أ. "الطباخ الذكي" (الفحص القائم على القواعد - Grammar-Aware Fuzzing)
بدلاً من رمي الطين العشوائي، يعمل ReTest كطباخ ماهر يعرف قواعد المطبخ.
- يقوم ببناء "شجرة الوصفة" (خريطة لكيفية هيكلة الوصفة).
- يأخذ وصفات حقيقية وعاملة من الإنترنت ويستبدل أجزاء منها بأجزاء أخرى صالحة.
- التشبيه: بدلاً من رمي الطين العشوائي، يأخذ وصفة كعكة صالحة ويستبدل "الدقيق" بـ "دقيق اللوز". النتيجة لا تزال وصفة كعكة صالحة، لكنها وصفة مختلفة. هذا يجبر المحرك على محاولة الطهي فعلياً، مما يكشف عن الأخطاء التي لا تظهر إلا عندما يعمل المحرك بجهد كبير.
ب. "التحقق الذاتي" (الاختبار التحولي - Metamorphic Testing)
بما أننا لا نستطيع الوثوق بطباخين آخرين ليكونوا هم "الحقيقة" (لأن لديهم أساليب مختلفة)، فإن ReTest يتحقق مما إذا كان الطباخ متسقاً مع نفسه.
- يستخدم قواعد رياضية (تسمى جبر كلين - Kleene Algebra) والتي يجب أن تكون صحيحة لأي محرك تعبيرات نمطية صالح.
- التشبيه: تخيل أنك تقول للطباخ: "اصنع لي شطيرة باللحم والجبن". ثم تقول له: "الآن، اصنع لي شطيرة بالجبن واللحم".
- إذا قال الطباخ: "الأولى كانت شطيرة، لكن الثانية كانت محمصة خبز!" -> لقد كُشف أمره!
- ترتيب المكونات لا ينبغي أن يغير حقيقة أنها شطيرة. يستخدم ReTest هذه "التحققات الذاتية" الرياضية للعثور على الأخطاء المنطقية دون الحاجة إلى رأي ثانٍ من محرك آخر.
3. النتائج: كشف الأخطاء الخفية
اختبر الفريق نظامهم الجديد على محرك شهير يسمى PCRE.
- التغطية: بينما استكشفت الطرق القديمة حوالي 12% فقط من "مطبخ" المحرك، استكشف ReTest 40%. إنه يشبه استكشاف المنزل بأكم مع أنه لم يستكشف سوى غرفة المعيشة.
- أخطاء جديدة: وجد ReTest ثلاث ثغرات أمنية جديدة تماماً (أخطاء قد تسمح للمخترقين بتعطيل النظام أو سرقة البيانات) فاتحت الطرق القديمة تماماً.
4. لماذا هذا مهم؟
محركات التعبيرات النمطية هي الغراء غير المرئي الذي يمسك الإنترنت معاً. فهي تتحقق من صحة أرقام بطاقات الائتمان الخاصة بك، وتصفي الرسائل المزعجة، وتؤمن كلمات المرور الخاصة بك.
- في الوقت الحالي: يتم اكتشاف معظم الأخطاء فقط عندما يشتكي المستخدم (82% من الأخطاء).
- مع ReTest: يمكننا العثور على هذه الأخطاء قبل أن تصل إلى المستخدم، مما يجعل الإنترنت أكثر أماناً وموثوقية.
ملخص
تجادل الورقة بأننا بحاجة إلى التوقف عن اختبار محركات التعبيرات النمطية عن طريق رمي النفايات العشوائية عليها أو مقارنتها بمحركات أخرى قد تكون فقط "مختلفة وليست خاطئة". بدلاً من ذلك، يجب أن نستخدم نظاماً ذكياً يفهم قواعد الوصفات ويتحقق مما إذا كان المحرك متسقاً منطقياً مع نفسه.
ReTest هو مفتش مراقبة الجودة النهائي لعالم محركات البحث الرقمية.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.