تحليل المؤشرات

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

هذا هو الاستخدام العامي الأكثر شيوعًا للمصطلح. وهناك استخدام ثانوي يتمثل في اعتبار تحليل المؤشرات اسمًا جامعًا لكل من تحليل النقاط المرجعية ، كما هو مُعرّف أعلاه، وتحليل الأسماء المستعارة . يرتبط تحليل النقاط المرجعية وتحليل الأسماء المستعارة ارتباطًا وثيقًا، ولكنهما ليسا متطابقين دائمًا.

مثال

انظر إلى برنامج C التالي:

int * id ( int * p ) { return p ; } void main ( void ) { int x ; int y ; int * u = id ( & x ); int * v = id ( & y ); }

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

تعبير المؤشر	موقع التخصيص
`&x`	`main::x`
`&y`	`main::y`
`u`	`main::x`
`v`	`main::y`
`p`	`main::x`،`main::y`

(حيث X::Yيمثل تخصيص المكدس الذي يحتوي على المتغير المحلي Yفي الدالة X.)

ومع ذلك، فإن التحليل غير الحساس للسياق مثل خوارزمية أندرسن أو ستينسجارد سيفقد الدقة عند تحليل الاستدعاءات إلى id، ويحسب النتيجة التالية:

تعبير المؤشر	موقع التخصيص
`&x`	`main::x`
`&y`	`main::y`
`u`	`main::x`،`main::y`
`v`	`main::x`،`main::y`
`p`	`main::x`،`main::y`

مقدمة

كشكل من أشكال التحليل الثابت، يمكن إثبات أن تحليل المؤشرات الدقيق تمامًا غير قابل للتقرير . ^{[ 1 ]} معظم المناهج سليمة ، لكنها تتفاوت بشكل كبير في الأداء والدقة. تؤثر العديد من قرارات التصميم على كل من دقة التحليل وأدائه؛ غالبًا (ولكن ليس دائمًا) تؤدي الدقة المنخفضة إلى أداء أفضل. تشمل هذه الخيارات: ^{[ 2 ]}^{[ 3 ]}

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

خوارزميات غير حساسة للسياق وغير حساسة للتدفق

تُستخدم خوارزميات تحليل المؤشرات لتحويل استخدامات المؤشرات الخام المجمعة (إسناد مؤشر إلى آخر أو إسناد مؤشر للإشارة إلى آخر) إلى رسم بياني مفيد لما يمكن أن يشير إليه كل مؤشر. ^{[ 4 ]}

تُعدّ خوارزمية ستينسجارد وخوارزمية أندرسن من الخوارزميات الشائعة لتحليل المؤشرات، وهي خوارزميات غير حساسة للسياق وغير حساسة لتدفق البيانات. وتُستخدم هذه الخوارزميات بكثرة في المترجمات، ولها تطبيقات في SVF ^{[ 5 ]} و LLVM .

الأساليب غير الحساسة للتدفق

يمكن فهم العديد من مناهج تحليل المؤشرات غير الحساسة للتدفق على أنها أشكال من التفسير المجرد ، حيث يتم تجريد تخصيصات الكومة من خلال موقع تخصيصها (أي موقع البرنامج). ^{[ 6 ]}

تم تحديد العديد من الخوارزميات غير الحساسة للتدفق في Datalog ، بما في ذلك تلك الموجودة في إطار عمل تحليل Soot للغة Java. ^{[ 7 ]}

تحقق الخوارزميات الحساسة للسياق والتدفق دقة أعلى، عادةً على حساب بعض الأداء، من خلال تحليل كل إجراء عدة مرات، مرة واحدة لكل سياق . ^{[ 8 ]} تستخدم معظم التحليلات نهج "سلسلة السياق"، حيث تتكون السياقات من قائمة من المدخلات (تشمل الخيارات الشائعة لمدخلات السياق مواقع الاستدعاء، ومواقع التخصيص، والأنواع). ^{[ 9 ]} لضمان الإنهاء (وبشكل أعم، قابلية التوسع)، تستخدم هذه التحليلات عادةً نهج تحديد k ، حيث يكون للسياق حجم أقصى ثابت، ويتم إزالة العناصر الأقل إضافةً حسب الحاجة. ^{[ 10 ]} ثلاثة أنواع شائعة من التحليل الحساس للسياق وغير الحساس للتدفق هي: ^{[ 11 ]}

حساسية موقع الاتصال
حساسية الكائن
حساسية النوع

حساسية موقع الاتصال

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

يوضح البرنامج التالي كيف يمكن لحساسية موقع الاتصال أن تحقق دقة أعلى من التحليل غير الحساس للتدفق وغير الحساس للسياق.

int * id ( int * p ) { return p ; } void main ( void ) { int x ; int y ; int * u = id ( & x ); // main.3 int * v = id ( & y ); // main.4 }

بالنسبة لهذا البرنامج، فإن التحليل غير الحساس للسياق سيخلص (بشكل سليم ولكن غير دقيق) إلى أن p يمكن أن يشير إما إلى التخصيص الذي يحتوي على x أو إلى التخصيص الذي يحتوي على y ، لذلك قد يكون u و v متطابقين، ويمكن أن يشير كلاهما إلى أي من التخصيصين:

تعبير المؤشر	موقع التخصيص
`&x`	`main::x`
`&y`	`main::y`
`u`	`main::x`،`main::y`
`v`	`main::x`،`main::y`
`p`	`main::x`،`main::y`

سيقوم التحليل الحساس لموقع الاستدعاء بتحليل المعرف مرتين، مرة لـ main.3ومرة لـ main.4، وسيتم تحديد حقائق الإشارة لـ p بواسطة موقع الاستدعاء، مما يُمكّن التحليل من استنتاج أنه عندما يعود main ، يمكن أن يشير u فقط إلى التخصيص الذي يحمل x ويمكن أن يشير v فقط إلى التخصيص الذي يحمل y :

سياق	تعبير المؤشر	موقع التخصيص
`[]`	`&x`	`main::x`
`[]`	`&y`	`main::y`
`[]`	`u`	`main::x`
`[]`	`v`	`main::y`
`[main.3]`	`p`	`main::x`
`[main.4]`	`p`	`main::y`

حساسية الكائن

في التحليل الحساس للكائنات، يتم تحديد مجموعة نقاط الوصول لكل متغير من خلال تخصيص الذاكرة المجردة للكائن المُستقبِل لاستدعاء الدالة. على عكس حساسية موقع الاستدعاء، فإن حساسية الكائن غير نحوية أو غير محلية : يتم اشتقاق مدخلات السياق أثناء تحليل نقاط الوصول نفسه. ^{[ 12 ]}

حساسية النوع

حساسية النوع هي شكل من أشكال حساسية الكائن، حيث يُستبدل موقع تخصيص الكائن المُستقبِل بالفئة/النوع الذي يحتوي على الدالة التي تحتوي على موقع تخصيص الكائن المُستقبِل. ^{[ 13 ]} ينتج عن ذلك عدد أقل من السياقات مقارنةً بما يُستخدم في التحليل الحساس للكائنات، مما يعني عمومًا أداءً أفضل.

مراجع

↑ ريبس، توماس (2000-01-01). "عدم قابلية الحسم في تحليل تبعية البيانات الحساسة للسياق" . معاملات ACM في لغات البرمجة والأنظمة . 22 (1): 162-186 . doi : 10.1145/345099.345137 . ISSN 0164-0925 . S2CID 2956433 .
↑ باربرا ج. رايدر (2003). "أبعاد الدقة في تحليل المراجع للغات البرمجة كائنية التوجه". بناء المترجمات، المؤتمر الدولي الثاني عشر، CC 2003، الذي عُقد كجزء من المؤتمرات الأوروبية المشتركة حول نظرية وممارسة البرمجيات، ETAPS 2003، وارسو، بولندا، 7-11 أبريل 2003، وقائع المؤتمر . الصفحات 126-137 . doi : 10.1007/3-540-36579-6_10 .
↑ ( هند ) خطأ في harv: لا يوجد هدف: CITEREFHind ( مساعدة )
↑ زيريانوف، فلاس؛ نيومان، كريستيان د.؛ غوارنيرا، درو ت.؛ كولارد، مايكل ل.؛ ماليتيك، جوناثان إ. (2019). "srcPtr: إطار عمل لتطبيق مناهج تحليل المؤشرات الثابتة" (ملف PDF) . وقائع المؤتمر الدولي السابع والعشرين لفهم البرامج (ICPC '19 ) . مونتريال، كندا: معهد مهندسي الكهرباء والإلكترونيات (IEEE).
↑ سوي، يولي؛ شو، جينغلينغ (2016). "SVF: تحليل تدفق القيم الثابت بين الإجراءات في LLVM" (ملف PDF) . CC'16: وقائع المؤتمر الدولي الخامس والعشرين حول بناء المترجمات . ACM.
↑ سماراغداكيس، يانيس؛ برافنبور، مارتن؛ لهوتاك، أوندري (26 يناير 2011). "اختر سياقاتك جيدًا" . وقائع الندوة السنوية الثامنة والثلاثين لجمعية ACM SIGPLAN-SIGACT حول مبادئ لغات البرمجة . POPL '11. أوستن، تكساس، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 17-30 . doi : 10.1145/1926385.1926390 . ISBN 978-1-4503-0490-0. S2CID 6451826 .
↑ أنطونياديس، توني؛ تريانتافيلو، قسطنطين؛ سماراغداكيس، يانيس (18-06-2017). "نقل doop إلى Soufflé" . وقائع ورشة العمل الدولية السادسة لـ ACM SIGPLAN حول أحدث التقنيات في تحليل البرامج . SOAP 2017. برشلونة، إسبانيا: جمعية آلات الحوسبة. ص 25-30 . doi : 10.1145/3088515.3088522 . ISBN 978-1-4503-5072-3. S2CID 3074689 .
↑ ( سماراغداكيس وبالاتسوراس ، ص 29) خطأ في هارف: لا يوجد هدف: CITEREFSmaragdakisBalatsouras ( مساعدة )
^ ثيسن، ري؛ لوتك ، أوندريج (2017/06/14). "تحويلات السياق لتحليل المؤشر" . إشعارات ACM SIGPLAN . 52 (6): 263-277 . دوى : 10.1145 / 3140587.3062359 . ISSN 0362-1340 .
↑ ( لي وآخرون ، ص 1: 4) خطأ في الحصاد: لا يوجد هدف: CITEREFLiTanMøllerSmaragdakis ( مساعدة )
↑ ( سماراغداكيس وبالاتسوراس ) خطأ في harv: لا يوجد هدف: CITEREFSmaragdakisBalatsouras ( مساعدة )
↑ ( سماراغداكيس وبالاتسوراس ، ص 37) خطأ في هارف: لا يوجد هدف: CITEREFSmaragdakisBalatsouras ( مساعدة )
↑ ( سماراغداكيس وبالاتسوراس ، ص 39) خطأ في هارف: لا يوجد هدف: CITEREFSmaragdakisBalatsouras ( مساعدة )

فهرس

زيريانوف، فلاس؛ نيومان، كريستيان د.؛ غوارنيرا، درو ت.؛ كولارد، مايكل ل.؛ ماليتيك، جوناثان إ. (2019). "srcPtr: إطار عمل لتطبيق مناهج تحليل المؤشرات الثابتة" (ملف PDF) . وقائع المؤتمر الدولي السابع والعشرين لفهم البرامج (ICPC '19 ) . مونتريال، كندا: معهد مهندسي الكهرباء والإلكترونيات (IEEE).
سماراغداكيس، يانيس؛ بالاتسوراس، جورج (2015). "تحليل المؤشرات" (ملف PDF) . أسس واتجاهات في لغات البرمجة . 2 (1): 1-69 . doi : 10.1561/2500000014 . S2CID 207179267. تاريخ الاسترجاع: 30 مايو 2019 .
لي، يو؛ تان، تيان؛ مولر، أندرس؛ سماراغداكيس، يانيس (18 مايو 2020). "نهج مبدئي لحساسية السياق الانتقائية لتحليل المؤشرات" . مجلة ACM للمعاملات في لغات البرمجة والأنظمة . 42 (2): 10:1–10:40. doi : 10.1145/3381915 . ISSN: 0164-0925 . S2CID: 214812357 .
مايكل هيند (2001). "تحليل المؤشرات: ألم نحل هذه المشكلة بعد؟" (ملف PDF) . PASTE '01: وقائع ورشة عمل ACM SIGPLAN-SIGSOFT لعام 2001 حول تحليل البرامج لأدوات وهندسة البرمجيات . ACM. الصفحات 54-61 . ISBN 1-58113-413-4.
ستينسجارد، بيارن (1996). "تحليل الإشارات في وقت شبه خطي" (ملف PDF) . POPL '96: وقائع الندوة الثالثة والعشرين لجمعية ACM SIGPLAN-SIGACT حول مبادئ لغات البرمجة . نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 32-41 . doi : 10.1145/237721.237727 . ISBN 0-89791-769-3.
أندرسن، لارس أولي (1994). تحليل البرامج والتخصيص للغة البرمجة C (PDF) (أطروحة دكتوراه).

[1] ريبس، توماس (2000-01-01). "عدم قابلية الحسم في تحليل تبعية البيانات الحساسة للسياق" . معاملات ACM في لغات البرمجة والأنظمة . 22 (1): 162-186 . doi : 10.1145/345099.345137 . ISSN 0164-0925 . S2CID 2956433 .

[2] باربرا ج. رايدر (2003). "أبعاد الدقة في تحليل المراجع للغات البرمجة كائنية التوجه". بناء المترجمات، المؤتمر الدولي الثاني عشر، CC 2003، الذي عُقد كجزء من المؤتمرات الأوروبية المشتركة حول نظرية وممارسة البرمجيات، ETAPS 2003، وارسو، بولندا، 7-11 أبريل 2003، وقائع المؤتمر . الصفحات 126-137 . doi : 10.1007/3-540-36579-6_10 .

[3] ( هند ) خطأ في harv: لا يوجد هدف: CITEREFHind ( مساعدة )

[4] زيريانوف، فلاس؛ نيومان، كريستيان د.؛ غوارنيرا، درو ت.؛ كولارد، مايكل ل.؛ ماليتيك، جوناثان إ. (2019). "srcPtr: إطار عمل لتطبيق مناهج تحليل المؤشرات الثابتة" (ملف PDF) . وقائع المؤتمر الدولي السابع والعشرين لفهم البرامج (ICPC '19 ) . مونتريال، كندا: معهد مهندسي الكهرباء والإلكترونيات (IEEE).

[5] سوي، يولي؛ شو، جينغلينغ (2016). "SVF: تحليل تدفق القيم الثابت بين الإجراءات في LLVM" (ملف PDF) . CC'16: وقائع المؤتمر الدولي الخامس والعشرين حول بناء المترجمات . ACM.

[6] سماراغداكيس، يانيس؛ برافنبور، مارتن؛ لهوتاك، أوندري (26 يناير 2011). "اختر سياقاتك جيدًا" . وقائع الندوة السنوية الثامنة والثلاثين لجمعية ACM SIGPLAN-SIGACT حول مبادئ لغات البرمجة . POPL '11. أوستن، تكساس، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 17-30 . doi : 10.1145/1926385.1926390 . ISBN 978-1-4503-0490-0. S2CID 6451826 .

[7] أنطونياديس، توني؛ تريانتافيلو، قسطنطين؛ سماراغداكيس، يانيس (18-06-2017). "نقل doop إلى Soufflé" . وقائع ورشة العمل الدولية السادسة لـ ACM SIGPLAN حول أحدث التقنيات في تحليل البرامج . SOAP 2017. برشلونة، إسبانيا: جمعية آلات الحوسبة. ص 25-30 . doi : 10.1145/3088515.3088522 . ISBN 978-1-4503-5072-3. S2CID 3074689 .

[8] ( سماراغداكيس وبالاتسوراس ، ص 29) خطأ في هارف: لا يوجد هدف: CITEREFSmaragdakisBalatsouras ( مساعدة )

[9] ثيسن، ري؛ لوتك ، أوندريج (2017/06/14). "تحويلات السياق لتحليل المؤشر" . إشعارات ACM SIGPLAN . 52 (6): 263-277 . دوى : 10.1145 / 3140587.3062359 . ISSN 0362-1340 .

[10] ( لي وآخرون ، ص 1: 4) خطأ في الحصاد: لا يوجد هدف: CITEREFLiTanMøllerSmaragdakis ( مساعدة )

[11] ( سماراغداكيس وبالاتسوراس ) خطأ في harv: لا يوجد هدف: CITEREFSmaragdakisBalatsouras ( مساعدة )

[12] ( سماراغداكيس وبالاتسوراس ، ص 37) خطأ في هارف: لا يوجد هدف: CITEREFSmaragdakisBalatsouras ( مساعدة )

[13] ( سماراغداكيس وبالاتسوراس ، ص 39) خطأ في هارف: لا يوجد هدف: CITEREFSmaragdakisBalatsouras ( مساعدة )

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]