💻 computer science

Deductive Verification of Weak Memory Programs with View-based Protocols (extended version)

تقدم هذه الورقة البحثية VerCors-relaxed، وهو امتداد لأداة التحقق الاستنتاجي VerCors التي تقوم بترميز التزامن في الذاكرة الضعيفة باستخدام بروتوكولات قائمة على الرؤية ومنطق الفصل القائم على الأذونات لتمكين التحقق الآلي من البرامج المتزامنة التي كانت تقتصر سابقاً على البراهين اليدوية.

المؤلفون الأصليون: Ömer Şakar, Soham Chakraborty, Marieke Huisman, Anton Wijs

نُشر 2026-04-24

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Ömer Şakar, Soham Chakraborty, Marieke Huisman, Anton Wijs

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

إليك شرح لورقة بحثية بعنوان "التحقق الاستنتاجي لبرامج الذاكرة الضعيفة باستخدام البروتوكولات القائمة على الرؤية"، مترجمة إلى لغة بسيطة مع تشبيهات إبداعية.

الصورة الكبيرة: مشكلة "المطبخ الفوضوي"

تخيل مطبخًا مزدحمًا به عدة طهاة (خيوط المعالجة/Threads) يعملون معًا لتحضير وجبة (البرنامج). في المطبخ المنظم تمامًا (التسلسل المتسق/Sequential Consistency)، يوجد رئيس طهاة واحد يملي بدقة متى يتحرك كل طاهٍ. الطاهي (أ) يقلب القدر، ثم الطاهي (ب) يقطع البصل، ثم الطاهي (أ) يضيف الملح. الجميع يرى نفس ترتيب الأحداث، مما يجعل التنبؤ بالنتيجة أمرًا سهلاً.

ومع ذلك، فإن معالجات الكمبيوتر الحديثة تشبه المطابخ الفوضوية حيث ذهب رئيس الطهاة في إجازة. لجعل العمل أسرع، يُسمح للطهاة بـ:

إعادة ترتيب المهام: قد يضيف الطاهي (أ) الملح قبل تقليب القدر إذا اعتقد أن ذلك سيوفر خطوة.
تأخير التحديثات: قد يقطع الطاهي (ب) البصل ولكنه ينتظر لوضعه في الوعاء في وقت لاحق.
رؤية أشياء مختلفة: قد يرى الطاهي (أ) أن الملح قد أُضيف، بينما لا يزال الطاهي (ب) يرى القدر فارغًا لأن التحديث لم "يصل" إلى رؤيته للمطبخ بعد.

هذا ما يسمى الذاكرة الضعيفة (Weak Memory). هذا يجعل الحواسيب سريعة، ولكنه يجعل من الصعب للغاية إثبات أن الوجبة ستكون سليمة. أحيانًا، تؤدي هذه الفوضى إلى كارثة (خطأ برمي/Bug) لا يمكنك تفسيرها بمجرد النظر إلى ترتيب التعليمات.

المشكلة: الإثبات اليدوي صعب للغاية

وضع علماء الكمبيوتر "كتيبات قواعد" (منطق مثل SLR) لإثبات أن الوجبة ستكون آمنة حتى في هذا المطبخ الفوضوي. لكن هذه الكتيبات تشبه العقود القانونية المعقدة. لاستخدامها، عليك كتابة كل سيناريو محتمل قد يتسبب في ارتباك الطاهي يدويًا. هذا الأمر بطيء، وممل، وعرضة للخطأ البشري.

الحل: "البروتوكولات القائمة على الرؤية" و"لوحة الملاحظات السحرية"

قام المؤلفون في هذه الورقة ببناء أداة جديدة تسمى VerCors-relaxed. فكر في هذه الأداة كأنها مفتش مطبخ ذكي للغاية وآلي.

بدلاً من محاولة التنبؤ بكل حركة فوضوية يدويًا، قدموا مفهومًا يسمى البروتوكولات القائمة على الرؤية (View-Based Protocols). إليك كيف يعمل ذلك باستخدام التشبيه:

1. البروتوكول (بطاقة الوصفة)

تخيل أن لكل طاهٍ بطاقة وصفة محددة لكل مكون يلمسه.

إذا كان من المفترض أن يكتب الطاهي (أ) الرقم "2" في متغير ما، فإن بطاقته تظهر مسارًا: البداية ← كتابة 1 ← كتابة 2.
إذا كان الطاهي (ب) سيكتب "1"، فإن بطاقته تظهر: البداية ← كتابة 1.
هذه البطاقات صارمة؛ لا يمكنك القفز من "البداية" إلى "كتابة 2" دون المرور بـ "كتابة 1" أولاً. هذا هو البروتوكول.

2. الرؤية (نظارات الطاهي)

يرتدي كل طاهٍ زوجًا من النظارات الخاصة (رؤية محلية للخيط/Thread-Local View).

تُظهر هذه النظارات للطاهي ما أنجزه هو حتى الآن.
والأهم من ذلك، تُظهر النظارات أيضًا توقعًا لما قد يكون الطهاة الآخرون قد فعلوه.
إذا نظر الطاهي (أ) من خلال نظاراته، فقد يرى: "لقد كتبت 2. وأعتقد أن الطاهي (ب) ربما كتب 1، أو ربما لم يبدأ بعد".

3. التحقق (فحص المفتش)

تعمل أداة VerCors كمفتش. هي لا تراقب حركة الطهاة في الوقت الفعلي، بل تحاكي المطبخ بأكمله باستخدام هذه البطاقات والنظارات.

تسأل الأداة: "إذا نظر الطاهي (أ) إلى القدر، فما هي القيم التي يمكن أن يراها بناءً على نظاراته وبطاقات الطهاة الآخرين؟"
تتحقق مما إذا كان الطهاة يتبعون قواعد بطاقات الوصفة.
تضمن أنه إذا رأى الطاهي قيمة ما، فقد تم كتابتها بالفعل من قبل شخص ما (لا توجد "مكونات شبحية").

الخدعة السحرية: التخمين (Speculation)

الجزء الأكثر روعة في هذه الورقة هو كيفية تعاملها مع التخمين.

في المطبخ الفوضوي، قد يخمن الطاهي (أ): "من المحتمل أن يكتب الطاهي (ب) الرقم '2' بعد ذلك، لذا سأبدأ بالتحضير لذلك". في الأنظمة القديمة، كان هذا التخمين خطيرًا؛ فإذا كتب الطاهي (ب) الرقم "1" فعليًا، فإن الوجبة بأكملها ستفسد.

مع البروتوكولات القائمة على الرؤية، تسمح الأداة للطهاة بالقيام بهذه التخمينات بأمان، طالما يمكنهم إثبات صحة التخمين لاحقًا.

التشبيه: الأمر يشبه لعبة "الهاتف المكسور" (Telephone). يهمس الطاهي (أ) بتخمين للمفتش. يتحقق المفتش من بطاقات الطهاة الآخرين. إذا قالت البطاقات إن الطاهي (ب) يمكنه كتابة "2" في هذه المرحلة، يقول المفتش: "حسنًا، تخمينك صحيح". أما إذا قالت البطاقات إن الطاهي (ب) يمكنه فقط كتابة "1"، فيقول المفتش: "توقف! هذا التخمين مستحيل. استبعد هذا التنفيذ".

ماذا فعلوا بالفعل؟

ترجمة النظرية: أخذوا منطقًا رياضيًا معقدًا للغاية (SLR) وترجموه إلى لغة تفهمها أداة VerCors.
بناء المشفّر (Encoder): أنشأوا نظامًا حيث يمكنك وصف هذه "بطاقات الوصفة" (البروتوكولات) و"النظارات" (الرؤى) عبر الكود.
أتمتة الإثبات: اختبروا ذلك على 13 مثالًا مختلفًا من كتب علوم الحاسوب (مثل الأمثلة الشهيرة "2+2W" و "COH").
- النتيجة: أثبتت الأداة تلقائيًا ما إذا كانت سيناريوهات المطبخ الفوضوي آمنة أم معطلة، وعادة ما كان ذلك في أقل من دقيقتين.

لماذا يهم هذا؟

السلامة: يساعد مهندسي البرمجيات على كتابة كود للمعالجات متعددة الأنوية (مثل هاتفك أو حاسوبك المحمول) دون القلق من أن تحسينات سرعة المعالج ستتسبب في أخطاء خفية.
الأتمتة: قبل ذلك، كان إثبات سلامة هذه البرامج يتطلب عالم رياضيات بمستوى دكتوراه يقضي أسابيع في إثبات يدوي. الآن، يمكن للكمبيوتر القيام بذلك في ثوانٍ.
سهولة الوصول: يسد هذا البحث الفجوة بين النظرية عالية المستوى والأدوات العملية، مما يسهل بناء برمجيات موثوقة للمستقبل.

الملخص

تقدم الورقة طريقة للتحقق تلقائيًا مما إذا كانت البرامج التي تعمل على حواسيب سريعة وفوضوية ستتصرف بشكل صحيح. يفعلون ذلك من خلال منح كل جزء من البرنامج "قاعدة بيانات" صارمة (البروتوكول) و"رؤية" لما يفعله الآخرون. ثم تقوم الأداة بمحاكاة جميع السيناريوهات الفوضوية الممكنة لضمان أنه حتى لو أعاد الطهاة ترتيب مهامهم، فإن الوجبة النهائية ستكون مثالية دائمًا.

إليك ملخص تقني مفصل لورقة البحث بعنوان "التحقق الاستنتاجي لبرامج الذاكرة الضعيفة باستخدام بروتوكولات قائمة على الرؤية (View-based Protocols)".

1. بيان المشكلة

تعد عملية الاستدلال على البرامج المتزامنة تحت نماذج الذاكرة الضعيفة (مثل C11/C++11 relaxed ordering) أكثر صعوبة بكثير مما هي عليه تحت نموذج التناسق التسلسلي (Sequential Consistency - SC).

التحدي: تسمح نماذج الذاكرة الضعيفة بتنفيذات برمجية لا يمكن تفسيرها من خلال تداخل بسيط بين الخيوط (threads). يؤدي هذا إلى نتائج غير متوقعة (على سبيل المثال، خيط يقرأ قيمة كتبها خيط آخر خارج الترتيب) ويجعل التحقق اليدوي عرضة للخطأ.
الفجوة: بينما تم تطوير العديد من منطقيات البرامج (مثل RSL، وGPS، وFSL، وSLR) للاستدلال على الذاكرة الضعيفة، فإن استخدامها يقتصر حاليًا على البراهين اليدوية المعقدة. وفي المقابل، تُعد أدوات التحقق الاستنتاجي الآلية مثل VerCors قوية لبرامج SC ولكنها تفتقر إلى الدعم الأصلي لدلالات الذاكرة الضعيفة.
الهدف: يهدف المؤلفون إلى سد هذه الفجوة من خلال تمكين التحقق الاستنتاجي الآلي والنمطي (modular) لبرامج الذاكرة الضعيفة باستخدام أداة VerCors.

2. المنهجية: البروتوكولات القائمة على الرؤية (View-Based Protocols)

المساهمة الجوهرية هي نهج ترميز مبتكر يسمى VerCors-relaxed، والذي يدمج البروتوكولات القائمة على الرؤية في منطق الفصل القائم على الأذونات (Permission-Based Separation Logic - PBSL) الموجود في VerCors.

أ. المفاهيم الأساسية

بروتوكولات المواقع لكل خيط (Per-Thread-Location Protocols):
- على عكس النهج السابق (مثل GPS) الذي يحدد بروتوكولاً واحداً لكل موقع ذاكرة للبرنامج بأكل، يحدد هذا النهج بروتوكول $P^t_x$ لكل خيط $t$ وموقع ذري $x$ .
- البروتوكول هو آلة حالة محدودة (شجرة) تنمذج تسلسل القيم التي يمكن لخيط معين كتابتها في موقع معين.
- تمثل الحالات في البروتوكول عمليات كتابة محددة؛ وتمثل الانتقالات ترتيب عمليات الكتابة.
الرؤى المحلية للخيط ( $L^t_x$ ):
- يحتفظ كل خيط بـ "رؤية" للحالة العالمية. وتحديدًا، لكل موقع $x$ ، يمتلك الخيط $t$ تخريطًا $L^t_x: T \to S \cup \{\bot\}$ .
- تتبع هذه الرؤية الحالة الحالية لبروتوكوله الخاص (عمليات الكتابة الخاصة به) والحالات التخمينية لبروتوكولات الخيوط الأخرى (ما يعتقد أنه قد كتبته الخيوط الأخرى).
- تسمح هذه الآلية للنظام بالاستدلال على الكتابات التخمينية (قراءة قيمة قبل تأكيدها بشكل صارم من خلال الترتيب العالمي).
دلالات التشغيل الهيكلي (SOS Rules):
- يستخدم النظام قواعد دلالات التشغيل الهيكلي (SOS) لتحديد كيفية تحديث عمليات التحميل (Load) والتخزين (Store) للرؤى المحلية للخيط وترتيب التعديل العالمي ( $\tau$ ).
- قاعدة الكتابة (Write Rule): عندما يقوم خيط بالكتابة، فإنه يتقدم في حالة البروتوكول الخاصة به. ويتم تحديث ترتيب التعديل العالمي ليعكس عملية الكتابة الجديدة.
- قاعدة القراءة (Read Rule): يمكن للخيط قراءة قيمة $v$ من الموقع $x$ إذا كانت الحالة المقابلة لـ $v$ قابلة للوصول في بروتوكول الخيط الذي قام بالكتابة، ومع احترام قيود التماسك (تحديدًا، لا يمكنه قراءة قيمة تم "استبدالها" في ترتيب التعديل بالنسبة لرؤيته الحالية).

ب. الترميز في VerCors

يقوم المؤلفون بترميز هذه المفاهيم في VerCors باستخدام:

أنواع البيانات المجردة (ADTs): يتم نمذجة البروتوكولات (الحالات، الانتقالات، القيم) كأنواع بيانات مجردة.
المتغيرات الشبحية (Ghost Variables): لتتبع حالة الرؤى ( $L$ )، وآخر عملية تخزين مرصودة ( $\pi$ )، وترتيب التعديل ( $\tau$ ) دون التأثير على أداء وقت التشغيل.
العقود (Contracts): يتم تجهيز طرق التحميل والتخزين بشروط مسبقة ولاحقة (pre/postconditions) تفرض قواعد SOS. على سبيل المثال، يضمن عقد load أن القيمة المعادة تتوافق مع حالة قابلة للوص আরও من الرؤية الحالية، مع احترام ترتيب التعديل.

3. المساهمات الرئيسية

VerCors-relaxed: امتداد لمدقق VerCors الاستنتاجي الذي يدعم تزامن الذاكرة الضعيفة عبر ترميز البروتوكولات القائمة على الرؤية.
هيكل البروتوكول المبتكر: تقديم البروتوكولات لكل خيط مقترنة بـ الرؤى المحلية للخيط. يختلف هذا عن العمل السابق بالسماح باستدلال أكثر دقة حول الكتابات التخمينية والتماسك لكل خيط.
ترميز SLR: نجح المؤلفون في ترميز الجزء المرن من منطق SLR (Separation Logic for Relaxed memory) في VerCors-relaxed. وقد أثبتوا سلامة (soundness) نهجهم: إذا تم التحقق من برنامج تحت ترميز البروتوكول القائم على الرؤية الخاص بهم، فإنه يكون صالحًا بموجب منطق SLR.
الأتمتة: يتيح النهج التحقق الآلي الكامل لأمثلة الذاكرة الضعيفة، بعيدًا عن بناء البراهń اليدوية.

4. النتائج والتقييم

قام المؤلفون بتقييم النهج على 13 مثالًا من الأدبيات، بما في ذلك اختبارات Litmus القياسية للذاكرة الضعيفة (مثل 2+2W وCOH وLB وSB وARM-weak) ومتغيراتها.

الصحة: نجحت الأداة في التحقق من التنفيذات المتسقة (المسموح بها في نموذج الذاكرة) ورفضت التنفيذات غير المتسقة (مثل تلك التي تنتهك SC-per-location أو التماسك).
الأداء:
- كانت أوقات التحقق معقولة، حيث بلغ متوسطها ما بين 48 و91 ثانية لكل مثال.
- تضمنت الأمثلة من 2 إلى 9 عمليات تحميل وتخزين مرخية (relaxed).
- كان حجم الترميز قابلاً للإدارة (حوالي 100 سطر لتعريفات البروتوكول لـ 4 حالات)، رغم أنه ينمو بشكل أسي مع عدد الحالات بسبب الحاجة لتعريف بديهيات التمايز.
المتانة: حدد النظام بشكل صحيح البروتوكولات غير الصحيحة (مثل الانتقالات المفقودة أو القيم الخاطئة) في حالات اختبار مثل COH-p1 وCOH-p2 مما يثبت أن البروتوكول يتم فحصه بدقة مقابل سلوك البرنامج.

5. الأهمية

سد الفجوة بين النظرية والتطبيق: هذا العمل مهم لأنه ينقل المنطقيات الفصلية النظرية المعقدة (مثل SLR) إلى سلسلة أدوات عملية وآلية.
النمطية (Modularity): على عكس فحص النماذج (Model Checking) الذي يتطلب غالبًا استكشاف مساحة الحالة بأكملها ويعاني من مشاكل في القابلية للتوسع، يسمح هذا النهج الاستنتاجي بـ التحقق النمطي. يمكن التحقق من الخيوط واحدًا تلو الآخر، مع مراعاة تعليماتها بترتيب SC أثناء استخدام البروتوكولات للاستدلال على تأثيرات الذاكرة الضعيفة.
الاستدلال التخميني: القدرة على الاستدلال الرسمي على الكتابات التخمينية (حيث يقرأ الخيط قيمة يتوقع أن يكتبها خيط آخر، قبل أن تصبح تلك الكتابة مرتبة عالميًا) تعد تقدمًا كبيرًا في التحقق الآلي للذاكرة الضعيفة.
التأثير المستقبلي: من خلال إثبات أن التحقق من الذاكرة الضعيفة يمكن أتمتته في أداة مثل VerCors، يمهد هذا العمل الطريق للتحقق من البرمجيات المتزامنة في العالم الحقيقي (مثل هياكل البيانات خالية الأقفال/lock-free) التي تعتمد على ترتيب الذاكرة المرخي لتحسين الأداء.

الخاتمة

تقدم الورقة إطارًا ناجحًا للتحقق الاستنتاجي الآلي لبرامج الذاكرة الضعيفة. من خلال تقديم البروتوكولات القائمة على الرؤية وترميزها في VerCors، قدم المؤلفون طريقة للتحقق من أنماط التزامن المعقدة التي كانت في السابق قابلة للإدارة فقط عبر براهين يدوية عرضة للخطأ. النهج سليم بالنسبة لمنطق SLR وقد تم التحقق من صحته باستخدام مجموعة من معايير الذاكرة الضعيفة القياسية.