کتاب راهکارهای خطازدایی خودکار نرم‌افزار

فصـل اول 11
مقدمه 11
خطازدایی چیست؟ 12
سیر تكاملي خطازدایی در نرم‌افزار 13
گام اول) عصر حجر 13
گام دوم) عصر برنز: استفاده از دستورات چاپ 14
گام سوم) دوره‌ی میان‌سالی: خطازداهای زمان اجرا 14
گام چهارم) حال حاضر: خطازداهای خودکار 14
گام پنجم) آینده‌ی نزدیک: ادغام کامپایلر و خطازداهای زمان اجرا 15
جمع‌بندی 16
فصـل دوم 17
مطالعات 17
پیش‌بینی خطا 17
معیارهای نرم‌افزار 18
معیارهای وابستگی 19
معیارهای تاریخي 19
بررسي فعالیت‌های گذشته در زمينه‌ی خطايابي 19
بررسي فعالیت‌ها در زمینه‌ی معیارهای کد 19
بررسي فعالیت‌ها در زمینه‌ی معیارهای تاریخي 21
بررسي فعالیت‌ها در زمینه‌ی معیارهای وابستگي 22
بررسي فعالیت‌های گذشته در زمينه‌ی خطازدایی 23
جمع‌بندی 25
فصـل سوم 27
روش‌شناسی 27
نمایش کد منبع 29
تکنیک‌های مبتني بر معیار 29
تکنیک‌های مبتني بر ترتیب نشانه‌ها 30
تکنیک‌های مبتني بر درخت 30
تکنیک‌های مبتني بر گراف وابستگي برنامه 30
درخت نحو انتزاعي 31
تجزیه‌ی کد منبع 33
انگشت‌نگاری و اندیس‌گذاری درخت‌های نحو 33
روش‌شناسی انگشت‌نگاری‌های درخت 33
توابع درهم‌سازی و بردار نوع-گره 34
توابع درهم‌سازی کاندید 35
درهم‌سازی مجموع (معیارهای نوع-گره) 35
درهم‌سازی کلمه دیک 35
درهم‌سازی رمزنگاری 36
الگوریتم رمزنگاری MD5 37
اضافه کردن بیت‌های نرم‌کننده 38
افزایش طول 38
تعیین بافر برای MD 39
پردازش پیام در بلاک‌های 16 کلمه‌ای 39
خروجي 40
تشكیل پایگاه داده، تطبیق، پیشنهاد 40
جمع‌بندی 41
فصـل چهارم 43
نتایج 43
پیچیدگي زماني رویكرد ارائه‌شده 43
مرحله‌ی اول: ساختن درخت نحو انتزاعي 43
مرحله‌ی دوم: اندیس‌گذاری با استفاده از تابع درهم‌سازی MD5 44
مرحله‌ی سوم: تطبیق 44
ساختن پایگاه داده از خطاها 45
مقایسه‌ی زمان اجرا 46
مقایسه‌ی دقت و کیفیت خطازدایی پیشنهادی 47
جمع‌بندی 50
فصـل پنجم 51
جمعبندی و پیشنهادها 51
جمع‌بندی 51
پیشنهاد‌ها 52
منـابع و مآخـذ 53

درخت نحو انتزاعي
در علم كامپيوتر، يک درخت نحو انتزاعي يا فقط درخت نحو، نمايش درختي از ساختار نحوی كد است كه در يک زبان برنامه‌نویسي نوشته شده است كه هر گره از آن جزئي از كد را نمايش می‌دهد. از اين درخت يک انتزاع می‌سازیم تا بخشي از جزئيات غیرضروری كد را كه در گرامر واقعي وجود دارد، پنهان نمايد. برای مثال، پرانتزها در ساختار درختي تلویحاً بيان شده است و يا عبارت‌هایی مانند دستورات شرطي (if…else) می‌تواند به‌وسیله‌ی يک گره تنها با دو زيرشاخه نمايش داده شود. اين مسئله، درخت نحو انتزاعي را از درخت نحو واقعي كه عموماً درخت پارس ناميده می‌شود متمايز می‌کند. درخت پارس اغلب به‌وسیله‌ی يک پارسر كه جزئي از فرايند ترجمه و كامپايل كد می‌باشد ساخته می‌شود.
شکل 3-2- شمای كلي ساخت درخت نحو انتزاعي را نمايش می‌دهد. در مرحله‌ی اول، اسکنر تک‌تک کاراکترها را از كد منبع دريافت می‌کند و با تشخيص هر نشانه، آن را به پارسر می‌دهد. پارسر نيز با تشکيل مرحله‌به‌مرحله‌ی درخت نحو، درنهایت آن را به‌عنوان خروجي به كاربر می‌دهد.

تجزیه‌ی کد منبع
با استفاده از يک قطعه كد خطادار داده‌شده، می‌خواهیم برای شروع فرايند ايجاد اثر انگشت، نمايش درخت نحو را ايجاد كنيم. برای به دست آوردن انتزاعي از درخت نحو، هم‌زمان پس‌پردازشي از درخت نحو نياز است. به‌منظور ساختن درخت نحو انتزاعي برای زبان‌های مختلف از روش‌های نرمال‌سازی پس‌پردازش استفاده می‌کنیم. برای مثال، اين روش‌ها به‌منظور حذف دستورات كوچک يا بدون استفاده كاربرد دارد. هم‌چنين نياز به اعمال سطح انتزاع برای درخت داريم تا بتوانيم از تغييرات كوچک در كد جلوگيری به عمل آوريم. پس از يک بار ساخته‌شدن درخت‌های نحو انتزاعي، آن‌ها را برای استفاده‌های بعدی در يک مخزن ذخيره می‌کنیم. اين درخت‌ها سطح به سطح به‌صورت XML اندیس‌گذاری شده و ذخيره می‌گردند.

انگشت‌نگاری و اندیس‌گذاری درخت‌های نحو
با داشتن يک كد منبع، به دنبال يافتن تطبیق‌هايي بين اين پروژه و تمام پروژه‌های موجود در پايگاه داده هستيم. به دليل پيچيدگي زماني بالای الگوریتم‌های تطبيق درخت، نيازمند روش‌هايي برای جستجو با سرعت بسيار بالا هستيم تا بتوانيم از این رويکرد به‌صورت برخط در كامپايلرها استفاده كنيم.

روش‌شناسی انگشت‌نگاری‌های درخت
يک درخت (AST) با گره‌های داخلي و برگ‌ها را در نظر بگیرید. می‌خواهیم هر زيردرخت از اين درخت را براساس مقدار خلاصه‌ای از مقدار درهم‌سازی آن اندیس‌گذاری كنيم. اولين مشکل، پيدا كردن تابع درهم‌سازی با ویژگی‌های مناسب است. ازآنجایی‌که می‌خواهیم درخت نحو و نه فقط برگ‌های توالي نشانه‌ی آن را نشان دهيم، بايد از تابع درهم‌سازی‌ای استفاده كنيم كه به ساختار درختي حساس باشد.

بنابراين بايد گره‌های داخلي درخت را در محاسبه‌ی مقدار درهم‌سازی در نظر بگيريم. علاوه‌براین، برای اينکه فرايند ما مقیاس‌پذیر و كارا برای حجم زياد داده باشد بهتر است از توابع درهم‌سازی افزايشي استفاده كنيم تا برای محاسبه‌ی مقدار درهم‌سازی يک زيردرخت، تنها نياز به مقادير فرزندان مستقيم آن داشته باشيم. اين به آن معنا است كه درهم‌سازی تمام زيردرخت‌های يک AST می‌تواند در زمان خطي انجام گيرد. در ادامه، سه نوع تابع درهم‌سازی را مورد بررسی و ارزيابي قرار می‌دهیم و تابع استفاده‌شده در اين کتاب را شرح می‌دهیم.

توابع درهم‌سازی و بردار نوع-گره
هر زيردرخت از درخت نحو هر واحد كامپايلری را با يک تابع درهم‌سازی خوب مشخص می‌کنیم. يک تابع درهم‌سازی خوب است؛ اگر احتمال برخورد برای دو زيردرخت با ساختارهای متفاوت را كمينه كند. بردار نوع-گره را به‌صورت برداری كه هر نوع گره (متغيرها، ثابت‌ها، حلقه‌ها و …) را به يک مقدار درهم‌سازی ثابت نسبت می‌دهد تعريف می‌کنیم. اين بردار در تمامي محاسبات درهم‌سازی برای يک زبان و سطح انتزاع مشخص يکتا می‌باشد. با توجه به سطح انتزاع، انواع مشخصي از گره‌ها می‌توانند با مقدار درهم‌سازی مشابه نمايش داده شوند.
برای مثال، تمام ساختار حلقه‌ها (while, for, repat … until, …) را می‌توان با يک مقدار درهم‌سازی نمايش داد. نگراني ديگر مربوط به انتزاع انواع داده‌ی اوليه است. دگرگونی‌ها می‌توانند به‌راحتی يک متغير بولي يا بايت را با نوعي از عدد صحيح جايگزين كنند. پس منطقي به نظر می‌رسد كه يک مقدار درهم‌سازی مشابه برای برخي از انواع اوليه يا مثلاً مقادير عددی در نظر بگيريم.
در مقابل برای كشف كپي-چسباندن، ممکن است بهتر باشد پارامترهای بيش‌تری مانند نام متغير برای محاسبه‌ی مقدار درهم‌سازی از يک نود داشته باشيم. نهايتاً بهترين راه برای مقادير درهم‌سازی گره‌های مشخص، وابسته به زبان و برنامه‌ی كاربردی موردنظر می‌باشد. ازآنجایی‌که الگوهای دگرگوني زيادی وجود دارد، زياد كردن سطح انتزاع می‌تواند دقت را كاهش دهد. يک راه‌حل كاربردی برای اين مسئله عبارت است از در نظر گرفتن يک عدد تصادفي برای هركدام از انواع داده‌ها كه ما در اين کتاب از اين شيوه استفاده کرده‌ایم.

توابع درهم‌سازی کاندید
در اين بخش، نقاط قوت و ضعف برخي از توابع درهم‌سازی را كه برای فرايند انگشت‌نگاری درخت نحو استفاده می‌شوند، بررسي می‌کنیم.

درهم‌سازی مجموع (معیارهای نوع-گره)
معيارهای ساده‌ای شامل شمردن هر نوع گره از زيردرخت‌ها می‌باشد. هر زيردرخت با يک بردار مشخص می‌شود كه i-امين مؤلفه‌ی آن، تعداد گره‌های نوع i را نشان می‌دهد. اين رويکرد به‌خوبی توسط آقای دكارد مورد استفاده قرار گرفته است. اصول اين روش بر اين مبنا است كه انواع هر نود را هر زيردرخت شمارش می‌کند، سپس تابع درهم‌سازی LSH بر روی آن‌ها اعمال می‌شود تا براساس فاصله‌ی اقليدسي آن‌ها خوشه‌بندی شوند. ازآنجایی‌که اين روش، ساختار درخت‌ها را ناديده می‌گیرد، ممکن است تطبیق‌های کاملاً بی‌ربط حاصل شوند.

درهم‌سازی کلمه دیک
همان‌طور كه ديديم، می‌توان يک زيردرخت را به‌صورت يک عدد صحيح نمايش داد. در اينجا ما قصد داريم يک زيردرخت را به‌صورت يک كلمه ديک نمايش دهيم. به‌عنوان مثال يک فرم مرتب از زيردرخت شامل پيمايش عمقي آن. در مقابل بردار نوع-گره‌ی يک كلمه ديک سعي در حفظ ویژگی‌های ساختاری درخت دارد.
كلمه ديک D(a) برای يک برگ α توالي از اعداد صحيح است و كلمه ديک D(β) برای يک گره داخلي β با مجموعه فرزندان {b_1,b_2,…,b_i} به‌صورت بازگشتي از الحاق D(bi)ها تعريف می‌شود. سپس يک تابع درهم‌سازی كارپ-رابين روی كلمه ديک ساخته می‌شود. يک تابع درهم‌سازی كارپ-رابين می‌تواند به‌صورت افزايشي محاسبه شود. برای محاسبه‌ی كارایی مقدار درهم‌سازی يک زيردرخت، مقادير درهم‌سازی ريشه و فرزندان زيردرخت‌های آن محاسبه می‌شود. در تابع درهم‌سازی كارپ-رابين، k يک تابع چندجمله‌ای روی يک كلمه از اعداد صحيح m=a_1 a_2…a_m به‌صورت رابطه‌ی 3-1 تعريف می‌شود. هم‌چنين B به‌عنوان يک عدد اوليه به‌منظور جلوگيری از تداخل می‌باشد:

رابطه 3-1 k(m)=(…((a_1×B+a_2 )×B+a_3 )…)×B+a_m

برای محاسبه‌ی بازگشتي مقدار درهم‌سازی الحاق زیرمجموعه‌های اعداد صحيح m=s_1 s_2…s_n با داشتن مقدار درهم‌سازی و طول هر زيرمجموعه‌ی Si از رابطه‌ی 3-2 استفاده می‌کنیم:

رابطه 3-2 k(m)=(…(k(s_1 )×B^s2+k(s_2 ))…)×B^sn+k(s_n)

بنابراين K(m) می‌تواند در زمان t(m)=∑_(i=1)^n▒〖(log⁡(Si)+t(Si))〗 محاسبه شود. لذا محاسبه‌ی مقادير درهم‌سازی برای تمامي گره‌های يک درخت با اندازه‌ی N برابر است با O(NlogN).

درهم‌سازی رمزنگاری
نهايتاً در اين بخش از اندیس‌گذاری گره‌های يک درخت توسط توابع درهم‌سازی رمزنگاری مانند 1-SHA و یا MD5 صحبت می‌کنیم. با داشتن يک درخت، هر گره به‌صورت پايين به بالا درهم‌سازی می‌شود. ابتدا برگ‌ها اندیس‌گذاری می‌شوند و مقدار درهم‌سازی هر گره از الحاق مقدار درهم‌سازی اين گره با مقادير درهم‌سازی فرزندان زيردرخت‌ها به‌دست می‌آید. اين روش برای ما يک فرايند اندیس‌گذاری کاملاً افزايشي را مهيا می‌کند كه در تعداد گره‌های يک درخت خطي می‌باشند. اين تابع درهم‌سازی به نظر، تقريب خوبي از يک تابع درهم‌سازی كامل می‌باشد.
با استفاده از يک تابع درهم‌سازی رمزنگاری C مانند 1-SHA، تابع درهم‌سازی Hc را تعريف می‌کنیم. اين تابع به‌صورت بازگشتي برای يک درخت t با رتبه‌ی r و فرزندان (زيردرخت)〖 t〗_1 t_2,…t_n به‌صورت رابطه‌ی 3-3 تعريف می‌شود:

رابطه 3-3 H_c (t)=C(V(r)0H_c (t_1 )0H_c (t_2 )0…0H_c (t_n ))

اندازه‌ی مقادير درهم‌سازی ایجادشده توسط توابع رمزنگاری با انتخاب اولين يا آخرين بایت‌ها به ترتيب قراردادی كاهش می‌یابد. با توجه به مطالب ذکرشده، در اين کتاب به‌منظور كاهش هزينه‌ی كشف مثبت‌های كاذب و عدم وجود تداخل در پايگاه داده از الگوریتم‌های رمزنگاری به‌منظور اندیس‌گذاری استفاده كرديم. در بين توابع درهم‌سازی رمزنگاری، توابع 1-SHA و MD5 كارايي و محبوبيت بالايي دارند. در بين اين دو تابع نيز الگوريتم MD5 دارای پيچيدگي زماني پایین‌تری می‌باشد. در اين کتاب از الگوريتم MD5 برای اندیس‌گذاری درخت‌ها استفاده كرديم. در ادامه‌ی اين فصل جزئيات بيش‌تری از الگوريتم MD5 را بيان می‌کنیم.

الگوریتم رمزنگاری MD5
MD5، يک روش رمزنگاری است كه به‌صورت گسترده به‌عنوان تابع درهم‌ساز رمزنگارانه استفاده می‌شود. اين الگوريتم يک رشته با طول متفاوت را به‌عنوان ورودی می‌گیرد و يک خلاصه پيام MD5 يا اثر انگشت با طول 128 بيت می‌سازد. الگوريتم MD5 توسعه‌ای از الگوريتم MD4 است؛ با اين تفاوت كه MD5 کمی کندتر از MD4 عمل می‌کند، اما در طراحي آن بسيار محافظه‌کارانه عمل شده است.
MD5 در شرايطي طراحي شد كه حس كردند MD4 به علت سرعت بالايي كه دارد پذيرفته شده، اما از امنيت مناسبي در شرايط بحراني برخوردار نيست. MD5 كمي نسبت به MD4 كندتر شد، در عوض امنيت آن بيش‌تر گشت. اين الگوريتم حاصل تأثير دادن نظرات تعدادی از استفاده‌کنندگان MD4 به همراه مقاديری تغيير در ساختار الگوريتم برای افزايش سرعت و قدرت آن می‌باشد.
فرض كنيد ماb بيت پيام به‌عنوان ورودی داريم و تصميم داريم خلاصه پيام آن را به‌دست آوريم.b در اينجا يک عدد نامنفي و صحيح است،b می‌تواند مقدار صفر داشته باشد و هيچ محدوديتي برای مضرب هشت بودن آن نيست و به هر اندازه می‌تواند بزرگ باشد. فرض كنيد بیت‌های اين پيام را بشود به‌صورت زير نوشت:

m_0 m_1…m_(b-1)

برای آوردن خلاصه پيام، 5 مرحله‌ی زير را انجام می‌دهیم.
طول پيام موردنظر به 448 به پيمانه‌ی 512 توسعه پيدا می‌کند؛ به اين معني كه اگر به طول پيام 64 بيت اضافه شود، طولش مضربي از 512 خواهد بود. عمل توسعه دادن هميشه اجرا می‌شود، مگر اينکه طول پيام به‌صورت 448 به پيمانه‌ی 512 باشد. عمل توسعه‌ی پيام يا نرم كردن آن به‌صورت زير انجام می‌شود:

اضافه کردن بیت‌های نرم‌کننده
يک بيت “1” سپس تعدادی بيت “0” به پيام اضافه می‌شود. اضافه شدن بیت‌های 0 تا زماني كه طول رشته به 448 بر پايه‌ی 512 برسد، ادامه پيدا می‌کند. در اين عمل حداقل يک بيت و حداكثر 512 بيت اضافه خواهد شد.