💻 computer science

Formal Verification of Imperative First-Class Functions in Move

تقدم هذه الورقة امتداداً لـ Move Prover يتيح التحقق الرسمي من الدوال الأمرية من الدرجة الأولى في لغة Move عبر إدخال المحمولات السلوكية، وتسميات الحالة، واستراتيجية ترميز SMT التي تستفيد من الفصل الاستاتيكي للذاكرة في Move من أجل التحقق الفعال والاستدلال الآلي للمواصفات.

المؤلفون الأصليون: Wolfgang Grieskamp, Teng Zhang, Vineeth Kashyap, Jake Silverman

نُشر 2026-05-14

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

CC BY 4.0

المؤلفون الأصليون: Wolfgang Grieskamp, Teng Zhang, Vineeth Kashyap, Jake Silverman

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

إليك شرح للورقة البحثية باستخدام لغة بسيطة وتشبيهات إبداعية.

الصورة الكبيرة: مصنع "العقود الذكية"

تخيل أن Aptos عبارة عن مصنع عالي الأمان يبني أصولاً رقمية (مثل الأموال أو التذاكر) باستخدام لغة خاصة تسمى Move. وللتأكد من أن هذه الأصول لا تُسرق أو تتعطل، يستخدم المصنع روبوت فحص يسمى Move Prover (MVP). يقرأ هذا الروبوت المخططات (الكود) ويثبت رياضياً أن كل شيء سيعمل بشكل صحيح قبل أن يبدأ المصنع في العمل فعلياً.

لفترة طويلة، كان هذا الروبوت بارعاً في فحص التعليمات البسيطة. ولكن مؤخراً، أضاف المصنع ميزة جديدة ومعقدة: الدوال من الدرجة الأولى (First-Class Functions).

فكر في هذه الدوال الجديدة كأنها عصي سحرية.

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

هذا ما يسمى التوزيع الديناميكي (Dynamic Dispatch). إنه أمر قوي، لكنه يربك روبوت الفحص لأنه لا يستطيع رؤية المستقبل لمعرفة أي تعويذة محددة سيتم إلقاؤها.

المشكلة: معضلة "الصندوق الأسود"

تشرح الورقة كيف قام المؤلفون بترقية روبوت الفحص (MVP) للتعامل مع هذه العصي السحرية دون ذعر.

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

قدم المؤلفون أداتين جديدتين لحل هذه المشكلة:

1. المسندات السلوكية (Behavioral Predicates): "بطاقة الضمان"

بدلاً من النظر داخل العصا السحرية لمعرفة كيفية عملها، ينظر الروبوت الآن إلى بطاقة الضمان المرفقة بالعصا.

الطريقة القديمة: "أحتاج لمعرفة كيف تعمل عصا calculate_price هذه بالضبط، وصولاً إلى كل سطر في الكود، قبل أن أسمح لك باستخدامها."
الطريقة الجديدة: "لا يهمني كيف تعمل العصا من الداخل. أحتاج فقط لقراءة بطاقة الضمان الخاصة بها. تقول البطاقة: 'إذا أعطيتني 5 عملات، سأعيد لك 3 عملات، ولن أعطل أبداً'"

تسمي الورقة هذه بـ المسندات السلوكية. وهي تشبه عقداً يصف:

الشروط المسبقة (Pre-conditions): ما يجب أن يكون صحيحاً قبل التلويح بالعصا.
الشروط اللاحقة (Post-conditions): ما سيكون صحيحاً بعد التلويح بها.
شروط الإيقاف (Abort conditions): متى قد تنفجر العصا (تفشل).

هذا يسمح للروبوت بفحص وعد العصا دون الحاجة لمعرفة الوصفة السرية بداخلها.

2. تسميات الحالة (State Labels): "كاميرا تسجيل الوقت"

أحياناً تحدث سلسلة من الأحداث. تخيل خط إنتاج حيث يقوم روبوت بطلاء سيارة، ثم يقوم روبوت آخر بتركيب العجلات.

إذا كنت تريد إثبات أن السيارة آمنة، فأنت بحاجة لمعرفة حالة السيارة بعد الطلاء ولكن قبل تركيب العجلات.

قدم المؤلفون تسميات الحالة. فكر في هذه كأنها كاميرات تسجيل الوقت موضوعة في نقاط محددة من العملية.

الكاميرا أ (البداية): السيارة عبارة عن معدن خام.
الكاميرا ب (المنتصف): السيارة مطلية.
الكاميرا ج (النهاية): العجلات مركبة.

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

كيف يعمل الروبوت فعلياً (لوحة التبديل)

تصف الورقة كيف يترجم الروبوت هذه الأفكار إلى رياضيات (منطق SMT) يمكن للكمبيوتر حلها.

تخيل أن الروبوت لديه لوحة تبديل (Switchboard).

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

هذا فعال لأن الروبوت ليس مضطراً لمحاولة فتح كل الصناديق الممكنة. هو يفتح فقط الصناديð التي يعرفها، وبالنسبة للبقية، فهو يثق في العقد.

"المفتش الآلي" (استنتاج المواصفات)

أروع جزء في الورقة هو أن الروبوت يمكنه الآن كتابة بطاقات الضمان الخاصة به.

عادةً، يتعين على البشر كتابة هذه البطاقات يدوياً، وهو أمر ممل. قام المؤلفون بترقية الروبوت بحيث يمكنه النظر إلى الكود، وفهم ما يجب أن تقوله بطاقة الضمان، وكتابتها لك.

المدخلات: قطعة كود فوضوية تحتوي على عصا سحرية.
إجراء الروبوت: "أرى أن هذا الكود يتحقق مما إذا كانت الرسوم موجودة. سأكتب بطاقة ضمان تقول: 'هذه العصا ستنفجر إذا كانت الرسوم مفقودة'."
النتيجة: الروبوت يفحص عمله الخاص. إذا تطابق الكود مع البطاقة، فإنه يجتاز الاختبار.

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

ملخص الإنجاز

تدعي الورقة أنها حلت مشكلة كبيرة في التحقق من العقود الذكية:

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

باختصار، لقد علموا روبوت الفحص كيف يثق في وعد الغريب (العقد) دون الحاجة لمعرفة أسرار الغريب، مما جعل المصنع أكثر أماناً ومرونة.

ملخص تقني: التحقق الرسمي من الدوال الأمرية من الدرجة الأولى في لغة Move

بيان المشكلة
إن أداة (Move Prover - MVP) هي أداة تحقق رسمي مصممة لعقود Move الذكية، بُنيت في الأصل على أسلوب مواصفات نمطي ذي توزيع استاتيكي (static-dispatch). وقد أدى امتداد حديث للغة Move إلى إدخال الدوال من الرتب العليا (higher-order functions)، مما يسمح للدوال بأن تكون قيمًا من الدرجة الأولى يمكن تمريرها كوسطاء، أو تخزينها في هياكل البيانات، أو حفظها في التخزين العالمي (global storage). تتيح هذه القدرة التوزيع الديناميكي (dynamic dispatch)، لكنها تكسر افتراضات التحليل الاستاتيكي التي اعتمدت عليها MVP. وتحديدًا، عند استدعاء دالة بشكل ديناميكي، لا يمكن حل الشروط المسبقة واللاحقة (pre- and post-conditions) عند موقع الاستدعاء. يجب على المستدعي (caller) التفكير بشكل تجريدي في سلوك وسائط قيم الدوال، بينما يجب على المُحقِّق (verifier) التوفيق بين هذه المواصفات المجردة والدوال الملموسة التي قد تصل إلى موقع الاستدعاء. تفتقر الحلول الحالية في لغات أخرى (مثل Dafny وF* وVerus) إما إلى دعم الدوال من الرتب العليا الأمرية التي تعدل الحالة، أو تعتمد على منطق الفصل (separation logic)، مما قد يؤدي إلى ترميزات معقدة لـ SMT. ويتمثل التحدي في دعم هذه الميزات الديناميكية بكفاءة، وضمان بقاء عملية التحقق سريعة، وكاملة للحالات ذات الصلة، وخالية من عدم استقرار المحفزات (trigger instability) في SMT.

المنهجية
يقوم المؤلفون بتوسيع MVP ولغة مواصفات Move لدعم الدوال من الرتب العليا من خلال ثلاث آليات رئيسية:

المحمولات السلوكية (Behavioral Predicates): يتم توسيع لغة المواصفات بالمحمولات التي توصف سلوك قيم الدوال ( $f$ ) بالنسبة لوسطاء محددين ( $\bar{x}$ ) ونتائج ( $\bar{y}$ ). وتشمل هذه:
- requires_of<f>(x): الشروط المسبقة.
- aborts_of<f>(x): شروط الإلغاء (abort).
- ensures_of<f>(x, y): الشروط اللاحقة.
  تتتبع هذه المحمولات ضمنيًا تبعيات حالة القراءة والقراءة/الكتابة، مما يسمح للمواصفات بالإشارة تجريديًا إلى وسائط الدوال دون دمج أجسامها (inlining).
تسميات الحالة (State Labels): للتفكير في انتقالات الحالة المتسلسلة وحالات الذاكرة الوسيطة، يقدم المؤلفون تسميات الحالة (مثل $S$ ). يمكن أن تكون المحمولات أحادية الحالة ( $S \mid \sim p$ ) أو ثنائية الحالة ( $S.. \mid \sim q$ )، مما يتيح تركيب المحمولات السلوكية لوصف تسلسل العمليات (على سبيل المثال، الحالة اللاحقة لدالة ما تصبح الحالة المسبقة لدالة أخرى).
ترميز SMT عبر تمييز المتغيرات (Variant Discrimination): على مستوى SMT، يتم ترميز قيم الدوال باستخدام أنواع بيانات جبرية (algebraic datatypes) تمثل جميع مصادر قيمة الدالة (الإغلاقات الملموسة، وسائط الدوال، أو حقول الهياكل). عند استدعاء قيمة دالة:
- إذا كانت الدالة الملموسة معروفة (مثل إغلاق محدد)، يتم استبدال الاستدعاء بأثر تلك الدالة الملموسة.
- إذا كانت الدالة غير معروفة (مثل وسيط أو إغلاق محمل من التخزين)، يتم نمذجة الاستدعاء باستخدام المحمولات السلوكية المرتبطة بنوع قيمة الدالة تلك.
- يستخدم الترميز بنيات "الاستنزاف" (havoc) و"الافتراض" (assume) لنمذجة تعديلات الذاكرة، ويضمن احترام شروط الإطار (frame conditions) من خلال التمييز بين خريطة الذاكرة للحالة المسبقة والحالة اللاحقة.

المساهمات الرئيسية
تفصل الورقة المساهمات المحددة التالية:

توسعات اللغة: تقديم المحمولات السلوكية وتسميات الحالة للغة مواصفات Move، مما يجعل مواصفات الدوال مواطنين من الدرجة الأولى قادرين على تتبع تبعيات الحالة.
التنفيذ في MVP: ترميز قائم على لغة Boogie يميز بين متغيرات قيم الدوال عند مواقع الاستدعاء. يتجنب هذا النهج الحاجة إلى منطق الفصل عبر الاستفيد من الفصل الذاكري الاستاتيكي لـ Move (نموذج الموارد)، مما يؤدي إلى ترميزات SMT أكثر كفاءة.
استنتاج المواصفات: توسيع أداة تحليل الشرط الأضعف (weakest-precondition - WP) الخاصة بـ MVP للتعامل مع الكود من الرتب العليا. تقوم هذه الأداة باشتقاق المواصفات القائمة على المحمولات السلوكية من bytecode الخاص بـ Move بشكل شبه تلقائي، مما يقلل من عبء التوصيف اليدوي ويوفر مسار تحقق للمكونات الجديدة.
التعامل مع الآثار الجانبية الأمرية: على عكس بعض الأدوات الموجودة (مثل Dafny)، يدعم هذا النهج الدوال من الرتب العليا الأمرية التي تعدل الحالة عبر مراجع بأسلوب Rust والمتغيرات العالمية.

النتائج والتحقق
يستعرض المؤلفون النهج باستخدام مثال صانع السوق الآلي (AMM) حيث يتم تخزين منحنى التسعير كقيمة دالة. نجح النظام في التحقق من:

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

الأهمية
تزعم الورقة أن هذا العمل يتيح التحقق الروتيني الموجه للإنتاج لعقود Move الذكية التي تتميز بالتوزيع الديناميكي والدوال من الرتب العليا. ومن خلال الحفاظ على نموذج التكلفة الخاص بـ MVP — حيث يكتمل التحقق في ثوانٍ لكل دالة — يسمح هذا الامتداد للمطورين باستخدام أنماط معقدة مثل تدفقات الأصول القائمة على الاستدعاءات الراجعة (callback-based) ومديري الأصول القابلين للتوسع مع ضمانات رسمية. ويتميز هذا النهج عن الأدوات القائمة على منطق الفصل باستخدامه للفصل الذاكري الاستاتيكي المتأصل في Move لتبسيط ترميزات SMT. علاوة على ذلك، يوفر دمج استنتاج المواصفات مسارًا عمليًا للتحقق من امتثال قيم الدوال، مما يعالج عقبة كبيرة أمام اعتماد الدوال من الرتب العليا في العقود الذكية ذات الأهمية البالغة للسلامة. ويقر العمل بأنه بينما أصبح التحقق من جانب التطبيق الآن مشابهًا للدوال من الدرجة الأولى، فإن التحقق من جانب الامتثال (إثبات أن الدالة الممررة تستوفي عقدًا ما) قد لا يزال يتطلب تلميحات إثبات يدوية أو افتراضات موثوقة في الحالات المعقدة.