ConVer: Using Contracts and Loop Invariant Synthesis for Scalable Formal Software Verification
تقدم هذه الورقة ConVer، وهي أداة تحقق تركيبي من الأعلى إلى الأسفل تستفيد من النماذج اللغوية الكبيرة لتخليق عقود الدوال وتعمل على تحسينها بشكل تكراري عبر حلقة CEGAR-CEGIS للتغلب على انفجار فضاء الحالة في التحقق من برامج C الكبيرة ونماذج LF المحولة.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
تخيل أنك تحاول إثبات أن مصنعاً ضخماً ومعقداً يعمل بشكل مثالي. يحتوي المصنع على آلاف الآلات، وسيور النقل، والعمال، وكلهم متصلون في شبكة عملاقة. إذا حاولت مراقبة كل آلة، وكل ترس، وكل عامل في نفس الوقت للعثور على خطأ ما، فستشعر بالارتباك. كمية المعلومات الهائلة ستؤدي إلى "انفجار" دماغك قبل أن تتمكن من العثين على الخطأ. هذا هو بالضبط التحدي الذي يواجهه مهندسو البرمجيات عند محاولة التحقق من البرامج الحاسوبية الكبيرة: هناك عدد هائل من الحالات الممكنة التي لا يستطيع الحاسوب فحصها جميعاً في وقت واحد.
تقدم هذه الورقة البحثية أداة تُدعى CONVER، وهي أداة جديدة صُممت لحل مشكلة "الارتباك" هذه عن طريق تغيير طريقة فحص الكود. فبدلاً من التحديق في المصنع بأكمله دفعة واحدة، تعمل CONVER كمدير ذكي يعمل من الأعلى إلى الأسفل، حيث يقوم بتفكيك المشكلة إلى قطع صغيرة يمكن إدارتها.
إليك كيف تعمل CONVER باستخدام تشبيهات بسيطة:
1. استراتيجية "من الأعلى إلى الأسفل": المخطط مقابل الطوب
عادةً، للتحقق من برنامج ما، يتعين عليك كتابة كتاب قواعد مفصل (عقد أو "contract") لكل دالة (كل آلة صغيرة) قبل أن تتمكن من فحص النظام بأكمله. هذا يشبه محاولة كتابة دليل لكل مسمار في سيارة قبل أن تتمكن من القول بأن السيارة آمنة. هذا الأمر يستغرق وقتاً طويلاً ويتطلب خبراء.
تقوم CONVER بقلب هذا السيناريو.
- التشبيه: تخيل أن لديك هدفاً: "يجب ألا ينتج المصنع أبداً منتجاً أحمر اللون".
- الطريقة القديمة: تسأل كل عامل: "ما هي قواعدك؟" وتحاول بناء نظام من الأسفل إلى الأعلى.
- طريقة CONVER: تبدأ بالهدف الكبير ("لا تو منتجات حمراء"). ثم تطلب من مساعد ذكاء اصطناعي (نموذج لغوي كبير أو LLM) تخمين القواعد لكل عامل التي من شأنها أن تضمن تحقيق الهدف الكبير. الأمر يشبه قولك: "إذا اتبع عامل خط التجميع هذه القواعد البسيطة، فسيكون المنتج النهائي آمناً". أنت لست بحاجة لمعرفة كيف يعمل عقل العامل، فقط التأكد من أنه يتبع القواعد.
2. "الحلقة الذكية": المحقق والذكاء الاصطناعي
بمجرد أن يخمن الذكاء الاصطناعي القواعد (العقود)، تضع CONVER هذه القواعد قيد الاختبار باستخدام حلقة من خطوتين، تشبه لعبة "خمن القاعدة" بين محقق ومشتبه به.
- الخطوة (أ): فحص النظام (المدير): تتحقق CONVER مما إذا كان المصنع بأكمله يعمل إذا اتبع الجميع القواعد المُخمنة. هي لا تنظر داخل الآلات؛ بل تكتفي بالوثوق بالقواعد.
- الخطوة (ب): فحص الدالة (المفتش): تقوم CONVER بعد ذلك بالتحقق مما إذا كانت الآلات الفعلية قادرة حقاً على اتباع تلك القواعد.
- حلقة "CEGAR": إذا فشلت الآلات في اتباع القواعد، فإن CONVER لا تستسلم ببساطة. بل تأخذ الخطأ المحدد (المثال المضاد أو "counterexample") وتعرضه على الذكاء الاصطناعي.
- التشبيه: يقول الذكاء الاصطناعي: "ظننت أن العامل يمكنه رفع 50 رطلاً". يقول المفتش: "لا، لقد أسقط العامل صندوقاً بوزن 50 رطلاً". يتعلم الذكاء الاصطناعي من هذا الفشل المحدد ويكتب قاعدة جديدة وأفضل: "يمكن للعامل رفع ما يصل إلى 40 رطلاً فقط".
- يتكرر هذا الأمر مراراً وتكراراً حتى تصبح القواعد مثالية.
3. تعلم "SMART ICE": تصفية الضجيج
أحياناً، يرتكب الذكاء الاصطناعي خطأً لأنه أساء فهم السؤال، وليس لأن القاعدة خاطئة. لإصلاح ذلك، تستخدم CONVER تقنية تسمى تعلم SMART ICE.
- التشبيه: تخيل أنك تعلم كلباً حركة معينة. إذا جلس الكلب عندما تقول له "ابقَ مكانك"، فأنت تعلم أنها حركة ناجحة. ولكن إذا جلس الكلب لأنه رأى سنجاباً، فهذا إنذار كاذب.
- كيف يعمل: تقوم CONVER بتصفية "الإنذارات الكاذبة" (الضجيج) وتحتفظ فقط بـ "الأخطاء الحقيقية" (الإشارة). فهي تصنف الأخطاء إلى: "إيجابي" (هذا نجح)، "سلبي" (هذا فشل بالتأكيد)، و"استلزام" (إذا حدث هذا، فلا بد أن يحدث ذاك). يساعد هذا الذكاء الاصطناعي على التعلم بشكل أسرع بكثير وتجنب الارتباك بسبب أخطائه الخاصة.
4. خدعة "ما قبل التجريد": النسخة الكرتونية
بعض أجزاء الكود معقدة للغاية (مثل مصنع يحتوي على حلقات لانهائية) لدرجة أن حتى فحص القواعد يكون صعباً.
- التشبيه: إذا كانت الآلة معقدة جداً بحيث يصعب رسمها بالتفصيل، ترسم CONVER نسخة كرتونية بسيطة منها أولاً. تتحقق مما إذا كانت النسخة الكرتونية تعمل. إذا نجحت، تستبدل الكرتون بالآلة الحقيقية وتتحقق مرة أخرى.
- هذا يسمح لـ CONVER بالتعامل مع برامج قد تؤدي في العادة إلى انهيار ذاكرة الحاسوب.
ماذا وجدوا؟
اختبر الباحثون CONVER على أربعة "صالات رياضية" (gymnasiums) مختلفة من الكود، تتراوح من الألغاز الرياضية البسيطة إلى أدوات تحليل الملفات المعقدة والحلقات التكرارية المعقدة.
- البرامج البسيطة: في مجموعة مكونة من 45 برنامجاً معيارياً، حققت CONVER نجاحاً مذهلاً، حيث تحققت من 82% إلى 96% منها. معظم هذه البرامج تم حلها في جولة واحدة فقط من الفحص، مما يعني أن الذكاء الاصطناعي خمن القواعد بشكل شبه مثالي من المرة الأولى.
- البرامج الأكثر صعوبة: في المجموعات الأكثر صعوبة (مثل تحليل شهادات الأمان أو الحلقات التكرارية المعقدة)، انخفضت نسبة النجاح إلى 33% إلى 64%. وهذا أمر متوقع لأن هذه البرامج أصعب بكثير في الفهم.
- عامل "الذكاء الاصطناعي": اختبروا ثلاثة نماذج ذكاء اصطناعي مختلفة (Qwen، وClaude، وGPT). كلما كان نموذج الذكاء الاصطناعي أذكى، كان أداء CONVER أفضل. النموذج الأذكى (GPT-OSS 120b) حل أكبر عدد من المشكلات، مما يثبت أن جودة "تخمينات" الذكاء الاصطناعي هي مفتاح النجاح.
الخلاصة
CONVER هي أداة تستخدم الذكاء الاصطناعي لكتابة "كتب القواعد" للبرمجيات، ثم تستخدم عملية تكرارية ذكية لإصلاح تلك الكتب حتى تصبح مثالية. إنها تحول لغزاً ضخماً مستحيلاً للحل إلى سلسلة من الخطوات الصغيرة القابلة للحل.
- هي لا تحل محل الحاجة إلى التحقق؛ بل تقوم بأتمتة الجزء الأصعب (كتابة القواعد).
- هي لا تضمن نجاحاً بنسبة 100% في كل برنامج معقد، لكنها تحل العديد من البرامج التي كان من المستحيل سابقاً فحصها تلقائياً.
- هي تعمل من خلال الاستماع إلى الإخفاقات: في كل مرة يفشل فيها البرنامج، تتعلم الأداة بالضبط لماذا وتطلب من الذكاء الاصطناعي المحاولة مرة أخرى بتخمين أفضل.
باخت de المختصر، CONVER تشبه وجود مدير مجتهد وفائق الذكاء، يقوم بتفكيك مشكلة ضخمة إلى مهام صغيرة، ويتعلم من كل خطأ، ويستمر في تحسين الخطة حتى تكتمل المهمة.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.