قصة 1001 LoC: توليف المواصفات الموجهة بواسطة أخطاء وقت التشغيل المحتملة للتحقق من البرامج الكبيرة A Tale of 1001 LoC: Potential Runtime Error-Guided Specification Synthesis for Verifying Large-Scale Programs

شارك:
المجلة: Proceedings of the ACM on Programming Languages، المجلد: 10، العدد: 0
DOI: https://doi.org/10.1145/3798268
تاريخ النشر: 2026-04-10
المؤلف: Z Y Wang وآخرون
الموضوع الرئيسي: المنطق، البرمجة، وأنظمة الأنواع

نظرة عامة

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

تظهر النتائج أن Preguss يتفوق بشكل كبير على الطرق الحالية المعتمدة على LLM، حيث يحقق تحققًا شبه آلي خالٍ من أخطاء وقت التشغيل (RTE) للبرامج الواقعية التي تتجاوز ألف سطر من التعليمات البرمجية (LoC). ومن الجدير بالذكر أنه يقلل من جهد التحقق البشري بنسبة تتراوح بين 80.6% إلى 88.9% ويحدد بنجاح ستة أخطاء RTE مؤكدة في نظام التحكم في المركبات الفضائية العملي، مما يبرز فعاليته في أتمتة عملية التحقق للتطبيقات الكبيرة.

مقدمة

تتناول مقدمة هذه الورقة البحثية القضية الحرجة لأخطاء وقت التشغيل (RTEs) في برامج C/C++، والتي يمكن أن تؤدي إلى سلوكيات غير محددة (UBs) وفشل كارثي، خاصة في التطبيقات الحرجة للسلامة. تسلط الضوء على ضرورة تأسيس خلو البرنامج من RTE كشرط مسبق للتحقق من الصحة الوظيفية في منهجيات التحقق من البرامج. تهدف أدوات التحليل الثابت المتطورة الحالية، مثل Astrée وFrama-C/Eva، إلى اكتشاف UBs ولكنها غالبًا ما تنتج إيجابيات خاطئة، مما يعقد عملية التحقق. تعتمد أدوات التحقق الاستنتاجية الآلية، رغم فعاليتها في ضمان الخصائص الحرجة، بشكل كبير على الخبرة البشرية في توليد المواصفات، خاصة في البرامج الكبيرة.

لمواجهة هذه التحديات، يقدم المؤلفون إطار عمل Preguss، الذي يستخدم استراتيجية تقسيم وتغلب لتوليد مواصفات رسمية دقيقة للتحقق من البرامج الكبيرة. يدمج هذا الإطار التحليل الثابت مع التحقق الاستنتاجي، مستفيدًا من تأكيدات RTE لتوجيه توليد المواصفات بين الإجراءات. تظهر النتائج التجريبية أن Preguss يتفوق بشكل كبير على الأساليب الحالية المعتمدة على LLM، حيث يحقق تقليلاً يتراوح بين 80.6% إلى 88.9% في جهد التحقق البشري ويحدد بنجاح RTEs في نظام التحكم في المركبات الفضائية العملي. توضح الورقة مساهماتها، بما في ذلك صياغة توليد المواصفات الموجهة بواسطة RTE وتطوير مجموعة بيانات مفتوحة المصدر من برامج C الحقيقية المعلّمة، مما يعرض فعالية Preguss وقابليته للتوسع في التحقق الآلي من خلوه من RTE.

الطرق

تقدم قسم المنهجية Preguss، وهو إطار مصمم لتوليد المواصفات الموجهة بواسطة أخطاء وقت التشغيل المحتملة. يستخدم Preguss استراتيجية تقسيم وتغلب، تتكون من مرحلتين رئيسيتين: المرحلة 1 (التقسيم) تقوم بتقسيم المهمة المعقدة للتحقق من خلو البرنامج من أخطاء وقت التشغيل (RTE) إلى وحدات أصغر، محددة الأولويات، كل منها يحتوي على تأكيد حراسة والسياق الضروري للتحقق. المرحلة 2 (التغلب) تستخدم نموذج لغة كبير (LLM) لاستنتاج المواصفات بين الإجراءات على طول سلاسل المتصلين، وبالتالي تصديق التأكيدات المستهدفة في كل وحدة تحقق. تهدف هذه الطريقة التعاونية إلى تعزيز التحقق من خلو البرنامج من RTE في البرامج الواقعية التي تتميز بتسلسلات استدعاء معقدة.

تُبنى تقييمات Preguss حول عدة أسئلة بحثية (RQs) تقيم أدائها وفعاليتها. على وجه التحديد، تستقصي RQ1 كيف يقارن Preguss مع الأساليب الحالية المتطورة، بينما تفحص RQ2 أدائه في التطبيقات الواقعية الكبيرة. تركز RQ3 على مساهمة كل مكون من مكونات Preguss في فعاليتها العامة، وRQ4 تستكشف حساسية الإطار للمعلمات الفائقة والتكرار وLLM الأساسي. يتم تفصيل إعداد التقييم في القسم 6.1، يليه تحليل شامل يتناول RQs من 1 إلى 4 في الأقسام 6.2 إلى 6.5، ودراسات حالة في القسم 6.6، ومناقشة التهديدات المحتملة للصلاحية في القسم 6.7.

المناقشة

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

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

القيود

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

علاوة على ذلك، مع زيادة تعقيد المشروع، قد يتجاوز سياق وحدة V واحدة نافذة سياق LLM. للتخفيف من ذلك، يقترح المؤلفون استخدام تقطيع البرنامج للتركيز فقط على الوظائف المتصلة ذات الصلة أو العبارات الحد الأدنى المتعلقة بتأكيدات الحراسة. كما أن الإطار الحالي يتجاهل المتغيرات العالمية والخارجية، مما يؤدي إلى إنذارات كاذبة محتملة؛ يمكن أن يعالج دمج تحليل تدفق البيانات الدقيق هذه القيود. أخيرًا، بالنسبة للمشاريع التي تستخدم واجهات برمجة التطبيقات لمكتبات خارجية مع تنفيذات غير متاحة، يدعو المؤلفون إلى الاستفادة من LLMs لاستنتاج العقود المحتملة من أسماء الوظائف وأنواع المعلمات، مما يقلل من جهود إنشاء العقود اليدوية.

Journal: Proceedings of the ACM on Programming Languages, Volume: 10, Issue: 0
DOI: https://doi.org/10.1145/3798268
Publication Date: 2026-04-10
Author(s): Z Y Wang et al.
Primary Topic: Logic, programming, and type systems

Overview

The paper introduces Preguss, a modular and fine-grained framework designed to enhance the automation of formal specification generation and refinement in the verification of large-scale software and hardware systems. Recognizing the limitations of large language models (LLMs) in handling complex interprocedural specifications and long-context reasoning, Preguss integrates static analysis with deductive verification through a divide-and-conquer approach. This involves guiding the construction and prioritization of verification units based on potential runtime errors and employing LLMs to synthesize interprocedural specifications at the unit level.

The findings demonstrate that Preguss significantly surpasses existing LLM-based methods, achieving nearly fully automated runtime error (RTE) freeness verification for real-world programs exceeding a thousand lines of code (LoC). Notably, it reduces human verification effort by 80.6% to 88.9% and successfully identifies six confirmed RTEs in a practical spacecraft control system, underscoring its effectiveness in automating the verification process for large-scale applications.

Introduction

The introduction of this research paper addresses the critical issue of runtime errors (RTEs) in C/C++ programs, which can lead to undefined behaviors (UBs) and catastrophic failures, particularly in safety-critical applications. It highlights the necessity of establishing RTE-freeness as a prerequisite for verifying functional correctness in program verification methodologies. Current state-of-the-art static analyzers, such as Astrée and Frama-C/Eva, aim to detect UBs but often produce false positives, complicating the verification process. Automated deductive verifiers, while effective in ensuring critical properties, still rely heavily on human expertise for specification synthesis, particularly in large-scale programs.

To tackle these challenges, the authors introduce the Preguss framework, which employs a divide-and-conquer strategy to synthesize fine-grained formal specifications for large-scale program verification. This framework integrates static analysis with deductive verification, utilizing RTE assertions to guide the synthesis of interprocedural specifications. Experimental results demonstrate that Preguss significantly outperforms existing LLM-based approaches, achieving a reduction of 80.6% to 88.9% in human verification effort and successfully identifying RTEs in a practical spacecraft control system. The paper outlines its contributions, including the formalization of potential RTE-guided specification synthesis and the development of an open-source dataset of annotated real-world C programs, showcasing Preguss’s effectiveness and scalability in automated RTE-freeness verification.

Methods

The methodology section introduces Preguss, a framework designed for Potential Runtime Error-Guided Specification Synthesis. Preguss employs a divide-and-conquer strategy, comprising two main phases: Phase 1 (Divide) breaks down the complex task of Runtime Error (RTE) freeness verification into smaller, prioritized units, each containing a guard assertion and the necessary program context for validation. Phase 2 (Conquer) utilizes a large language model (LLM) to infer interprocedural specifications along caller-callee chains, thereby certifying the target assertions in each verification unit. This cooperative approach aims to enhance the verification of RTE-freeness in real-world programs characterized by intricate call hierarchies.

The evaluation of Preguss is structured around several research questions (RQs) that assess its performance and effectiveness. Specifically, RQ1 investigates how Preguss compares to existing state-of-the-art methods, while RQ2 examines its performance on large-scale, real-world applications. RQ3 focuses on the contribution of each component of Preguss to its overall effectiveness, and RQ4 explores the sensitivity of the framework to the hyper-parameter iteration and the underlying LLM. The evaluation setup is detailed in Section 6.1, followed by a comprehensive analysis addressing RQs 1 through 4 in Sections 6.2 to 6.5, case studies in Section 6.6, and a discussion of potential threats to validity in Section 6.7.

Discussion

In the discussion section of the paper, the authors provide a comprehensive overview of program verification, emphasizing the importance of ensuring that programs conform to formal specifications. They define key concepts such as program states, configurations, and properties, illustrating these with examples from C programming. A program state is represented as a mapping of variables to values, while a configuration pairs this state with the next instruction to be executed. Properties are defined as tuples that include predicates representing subsets of program states, and the authors introduce the notion of validity under hypotheses, which is crucial for understanding the interdependencies between different properties.

The authors also highlight the challenges of synthesizing specifications for runtime error (RTE) verification, particularly in complex programs with intricate call hierarchies. They argue that while localized specifications may suffice for simple cases, interprocedural specifications are necessary for more complex scenarios to avoid false alarms. The paper discusses the limitations of current approaches, particularly those relying on large language models (LLMs) for specification synthesis, and identifies key challenges such as long-context reasoning and the generation of over-constrained preconditions. The authors propose a feedback-driven approach to refine specifications based on verification outcomes, suggesting that insights from the verification process can enhance the quality of synthesized specifications. Overall, the section underscores the need for a robust framework that integrates static analysis and deductive verification to ensure RTE-freeness in programs.

Limitations

The limitations of the Preguss framework are identified, particularly its inadequacies in managing advanced specifications such as inductive definitions and axioms, which are essential for verifying complex data structures like linked lists and trees. To address these challenges, the authors suggest incorporating few-shot examples to guide the language model (LLM) in handling such specifications. Additionally, Preguss may generate overly constrained preconditions due to LLM hallucinations, as demonstrated in a specific case study. A potential solution involves utilizing abstract interpretation-based static analyzers to refine these preconditions by evaluating over-approximated constraints at call sites.

Furthermore, as project complexity increases, the context of a single V-Unit may surpass the LLM’s context window. To mitigate this, the authors propose employing program slicing to focus on only the relevant callee functions or minimal statements related to guard assertions. The current framework also neglects global and external variables, leading to potential false alarms; integrating fine-grained data-flow analysis could address this limitation. Lastly, for projects utilizing external library APIs with unavailable implementations, the authors advocate for leveraging LLMs to infer plausible contracts from function names and parameter types, thereby minimizing manual contract creation efforts.