تحليل الشكل (تحليل البرنامج)
في تحليل البرامج ، يُعد تحليل الشكل تقنيةً لتحليل الشيفرة الثابتة ، حيث يكتشف ويتحقق من خصائص هياكل البيانات المرتبطة والمُخصصة ديناميكيًا في برامج الحاسوب (عادةً ما تكون برامج إجرائية ). يُستخدم هذا التحليل عادةً أثناء الترجمة لاكتشاف أخطاء البرمجيات أو للتحقق من صحة خصائص البرامج على مستوى عالٍ. في برامج جافا ، يُمكن استخدامه للتأكد من أن دالة الفرز تُرتّب قائمةً بشكل صحيح. أما في برامج لغة سي ، فقد يبحث عن مواضع لم يتم فيها تحرير كتلة من الذاكرة بشكل صحيح.
التطبيقات
تم تطبيق تحليل الشكل على مجموعة متنوعة من المشاكل:
- أمان الذاكرة: اكتشاف تسريبات الذاكرة ، وفكّ مراجع المؤشرات المعلقة ، واكتشاف الحالات التي يتم فيها تحرير كتلة من الذاكرة أكثر من مرة. [ 1 ] [ 2 ]
- إيجاد أخطاء تجاوز حدود المصفوفة
- التحقق من خصائص حالة النوع (على سبيل المثال، التأكد من أن الملف موجود
open()قبل أن يكون موجودًاread()) - ضمان عدم إدخال دورات في القائمة المرتبطة بواسطة طريقة عكس القائمة [ 2 ]
مثال
يُعد تحليل الشكل نوعًا من تحليل المؤشرات ، ولكنه أكثر دقة من تحليل المؤشرات التقليدي. يسعى تحليل المؤشرات إلى تحديد مجموعة الكائنات التي يمكن أن يشير إليها المؤشر (وتُسمى مجموعة نقاط المؤشر). مع ذلك، فإن هذه التحليلات تقريبية بالضرورة (إذ يمكن لتحليل ثابت دقيق تمامًا حل مشكلة التوقف ). بينما يُمكن لتحليل الشكل تحديد مجموعات نقاط أصغر (أكثر دقة).
لنفترض برنامج C++ البسيط التالي .
العنصر * العناصر [ 10 ]؛for ( int i = 0 ; i < 10 ; ++ i ) { items [ i ] = new Item (...); // السطر [1] }process_items ( items ); // السطر [2]for ( int i = 0 ; i < 10 ; ++ i ) { delete items [ i ]; // السطر [3] }يقوم هذا البرنامج بإنشاء مصفوفة من الكائنات، ومعالجتها بطريقة عشوائية، ثم حذفها. وبافتراض process_itemsخلو الدالة من الأخطاء، فمن الواضح أن البرنامج آمن: فهو لا يشير أبدًا إلى الذاكرة المحررة، ويحذف جميع الكائنات التي أنشأها.
لسوء الحظ، تواجه معظم تحليلات المؤشرات صعوبة في تحليل هذا البرنامج بدقة. لتحديد مجموعات المؤشرات، يجب أن يكون تحليل المؤشرات قادرًا على تسمية كائنات البرنامج. عمومًا، يمكن للبرامج تخصيص عدد غير محدود من الكائنات؛ ولكن لإنهاء البرنامج، لا يمكن لتحليل المؤشرات استخدام سوى مجموعة محدودة من الأسماء. يتمثل أحد الحلول التقريبية الشائعة في إعطاء جميع الكائنات المخصصة في سطر معين من البرنامج نفس الاسم. في المثال أعلاه، جميع الكائنات التي تم إنشاؤها في السطر [1] ستكون لها نفس الاسم. لذلك، عند deleteتحليل العبارة للمرة الأولى، يحدد التحليل أنه يتم حذف أحد الكائنات المسماة [1]. في المرة الثانية التي يتم فيها تحليل العبارة (لأنها داخل حلقة تكرارية)، يحذر التحليل من خطأ محتمل: نظرًا لعدم قدرته على تمييز الكائنات في المصفوفة، فقد يكون التحليل الثاني deleteيحذف نفس الكائن الذي حذفه الأول delete. هذا التحذير غير صحيح، والهدف من تحليل الشكل هو تجنب مثل هذه التحذيرات.
التلخيص والتجسيد
يتغلب تحليل الشكل على مشاكل تحليل المؤشرات باستخدام نظام تسمية أكثر مرونة للكائنات. فبدلاً من إعطاء الكائن نفس الاسم في جميع أنحاء البرنامج، يمكن للكائنات تغيير أسمائها تبعًا لإجراءات البرنامج. في بعض الأحيان، قد يتم تجميع أو دمج عدة كائنات مختلفة بأسماء متباينة، بحيث تحمل جميعها نفس الاسم. وعندما يوشك البرنامج على استخدام كائن مُجمّع، يمكن تحويله إلى كائنين ماديين - أي تقسيم الكائن المُجمّع إلى كائنين باسمين مختلفين، أحدهما يمثل كائنًا واحدًا والآخر يمثل الكائنات المُجمّعة المتبقية. وتتمثل القاعدة الأساسية لتحليل الشكل في أن الكائنات التي يستخدمها البرنامج تُمثَّل باستخدام كائنات مادية فريدة، بينما تُجمَّع الكائنات غير المستخدمة.
يُلخّص الجدول المكوّن من الكائنات في المثال أعلاه بطرق منفصلة في الأسطر [1] و[2] و[3]. في السطر [1]، لم يتم إنشاء الجدول إلا جزئيًا. تحتوي عناصر الجدول من 0 إلى i-1 على كائنات مُنشأة. العنصر i على وشك الإنشاء، والعناصر التالية غير مُهيأة. يمكن لتحليل الشكل تقريب هذه الحالة باستخدام ملخص للمجموعة الأولى من العناصر، وموقع ذاكرة مُجسّد للعنصر i، وملخص للمواقع المتبقية غير المُهيأة، كما يلي:
| 0 .. i−1 | أنا | i+1 .. 9 |
| مؤشر إلى الكائن المُنشأ (ملخص) | غير مهيأ | غير مهيأ (ملخص) |
بعد انتهاء الحلقة، عند السطر [2]، لا حاجة للاحتفاظ بأي بيانات مُخزّنة. يُحدد تحليل الشكل عند هذه النقطة أن جميع عناصر المصفوفة قد تم تهيئتها.
| 0 .. 9 |
| مؤشر إلى الكائن المُنشأ (ملخص) |
iفي السطر [3]، يُستخدم عنصر المصفوفة مرة أخرى. لذلك، يقسم التحليل المصفوفة إلى ثلاثة أجزاء كما في السطر [1]. ولكن هذه المرة، iتم حذف الجزء الأول السابق، وتبقى العناصر المتبقية صالحة (بافتراض أن deleteالعبارة لم تُنفذ بعد).
| 0 .. i−1 | أنا | i+1 .. 9 |
| مجاني (ملخص) | مؤشر إلى الكائن المُنشأ | مؤشر إلى الكائن المُنشأ (ملخص) |
لاحظ أنه في هذه الحالة، يدرك التحليل أن المؤشر عند الفهرس iلم يُحذف بعد. لذلك، لا يُصدر تحذيراً بشأن الحذف المزدوج.
انظر أيضاً
مراجع
- ↑ رينيتزكي، نوام؛ ساغيف، مولي (2001). "تحليل الشكل بين الإجراءات للبرامج التكرارية" (ملف PDF) . بناء المترجمات . سلسلة محاضرات في علوم الحاسوب. المجلد 2027. الصفحات 133-149 . doi : 10.1007/3-540-45306-7_10 . ISBN 978-3-540-41861-0.
- 1 2 بيردين، جوش؛ كالكانيو، كريستيانو؛ كوك، بايرون؛ ديستيفانو، دينو؛ أوهيرن، بيتر دبليو؛ ويز، توماس؛ يانغ، هونغسوك (2007). "تحليل الشكل لهياكل البيانات المركبة" (ملف PDF) . التحقق بمساعدة الحاسوب . سلسلة محاضرات في علوم الحاسوب. المجلد 4590. الصفحات 178-192 . doi : 10.1007/978-3-540-73368-3_22 . ISBN 978-3-540-73367-6.
فهرس
- نيل د. جونز؛ ستيفن س. موشنيك (1982). "نهج مرن لتحليل تدفق البيانات بين الإجراءات والبرامج ذات هياكل البيانات المتكررة". وقائع الندوة التاسعة لجمعية ACM SIGPLAN-SIGACT حول مبادئ لغات البرمجة - POPL '82 . ACM. الصفحات 66-74 . doi : 10.1145/582153.582161 . ISBN 0897910656. S2CID 13266723 .
- مولي ساغيف ؛ توماس ريبس ؛ راينهارد فيلهلم (مايو 2002). "تحليل الشكل البارامتري باستخدام المنطق ثلاثي القيم" (ملف PDF) . مجلة ACM للمعاملات في لغات البرمجة والأنظمة . 24 (3). ACM: 217-298 . CiteSeerX 10.1.1.147.2132 . doi : 10.1145/292540.292552 . S2CID 101653 .
- فيلهلم، راينهارد؛ ساغيف، مولي؛ ريبس، توماس (2007). "الفصل 12: تحليل الشكل وتطبيقاته". في سريكانت، واي إن؛ شانكار، بريتي (محرران). دليل تصميم المترجمات: التحسينات وتوليد كود الآلة، الطبعة الثانية . مطبعة سي آر سي. الصفحات 12-1-12-44. ISBN 978-1-4200-4382-2.
- تحليل البرامج الثابتة