آزمون خودکار نرم‌افزار مبتنی بر فازینگ (Fuzzing) در سال‌های اخیر با یک بازگشت و احیای جدی مواجه شده است. به‌ ویژه فازینگ مبتنی بر بازخورد (feedback-driven fuzzing) که به دلیل توانایی آن در انجام کارآمد آزمون‌های تصادفی (randomized testing) با مجموعه‌های ورودی محدود، به رویکردی شناخته‌ شده تبدیل شده است.

با وجود پیشرفت‌های فراوان، دو مشکل رایج همچنان وجود دارد: اعداد جادویی (magic numbers) و جمع‌آزماهای تو‌در‌تو (nested checksums). برای عبور از این موانع معمولاً از روش‌های پرهزینه از نظر محاسباتی مانند ردگیری آلودگی (taint tracking) و اجرای نمادین (symbolic execution) استفاده می‌شود.

متأسفانه، چنین روش‌هایی اغلب نیازمند دسترسی به کد منبع (source code)، یک توصیف نسبتاً دقیق از محیط اجرا (برای مثال رفتار فراخوانی‌های کتابخانه‌ای (library calls) یا سیستم‌عامل زیرین (underlying OS))، یا معنای دقیق (semantics) مجموعه دستورالعمل‌های پلتفرم می‌باشند.

در این مقاله، ما یک جایگزین سبک اما بسیار مؤثر برای ردگیری آلودگی (taint tracking) و اجرای نمادین (symbolic execution) معرفی می‌کنیم که می‌تواند فازینگ مبتنی بر بازخورد پیشرفته (state-of-the-art feedback fuzzing) را تسهیل و بهینه‌سازی کند؛ به‌گونه‌ای که به ‌راحتی مقیاس‌پذیر بوده و روی برنامه‌های باینری بزرگ و محیط‌های ناشناخته قابل اجرا باشد.

ما مشاهده می‌کنیم که در حین اجرای یک برنامه مشخص، بخش‌هایی از ورودی اغلب به ‌صورت مستقیم (یعنی تقریباً بدون تغییر) وارد وضعیت (state) برنامه می‌شوند. این تناظر ورودی با وضعیت (input-to-state correspondence) می‌تواند برای ایجاد روشی مقاوم و پایدار جهت عبور از موانع رایج فازینگ، به شکلی بسیار مؤثر و کارآمد مورد استفاده قرار گیرد.

پیاده‌سازی اولیه ما با نام REDQUEEN قادر است به ‌صورت خودکار بایت‌های جادویی (magic bytes) و آزمون‌های جمع‌آزمای تو‌در‌تو (nested checksum) را برای یک فایل اجرایی باینری حل (solve) کند. علاوه بر این، نشان می‌دهیم که تکنیک‌های ما در طیف گسترده‌ای از اهداف (targets) و در سطوح مختلف دسترسی (فضای کرنل و کاربر (kernel-space and userland)) بدون نیاز به هیچ‌گونه کد وابسته به پلتفرم، از ابزارهای پیشرفته موجود بهتر عمل می‌کنند.

REDQUEEN نخستین روشی است که موفق شده بیش از ۱۰۰٪ از باگ‌های ایجاد شده در مجموعه LAVA-M را در تمامی اهداف شناسایی کند. ما همچنین موفق به کشف ۶۵ باگ جدید و دریافت ۱۶ شناسه CVE در چندین برنامه و درایورهای هسته سیستم‌عامل شدیم. در نهایت، ارزیابی ما نشان می‌دهد که REDQUEEN سریع بوده، به‌ طور گسترده قابل استفاده است و در مقایسه با رویکردهای هم‌زمان (concurrent approaches)، تا سه برابر عملکرد بهتری ارائه می‌دهد.

1. مقدمه (INTRODUCTION)

فازینگ (Fuzzing) به یکی از مؤلفه‌های حیاتی در آزمون کیفیت سیستم‌های نرم‌افزاری تبدیل شده است. طی چند سال اخیر، ابزارهای هوشمندتر فازینگ، هم در پژوهش‌های دانشگاهی و هم در صنعت، توسعه قابل‌توجهی پیدا کرده‌اند. به‌طور خاص، ابزار american fuzzy lop (AFL [44]) تأثیر چشمگیری بر چشم‌انداز امنیت سایبری گذاشته است.

به دلیل سهولت استفاده، اکنون این امکان فراهم شده است که نرم‌افزارها به ‌صورت عمیق‌تر و دقیق‌تری مورد آزمایش قرار گیرند؛ کاری که بسیاری از پژوهشگران و توسعه‌دهندگان نیز انجام داده‌اند. از منظر دانشگاهی، چالش بزرگ سایبری (Cyber Grand Challenge (CGC)) که توسط DARPA برگزار شد، به‌طور قانع‌کننده‌ای نشان داد که فازینگ همچنان در سطح پیشرفته‌ترین روش‌های کشف باگ، کاملاً مرتبط و مؤثر است؛ زیرا تمامی تیم‌های شرکت‌کننده از این تکنیک برای کشف آسیب‌پذیری‌های جدید استفاده کرده بودند.

پس از CGC، روش‌های جدید متعددی در حوزه فازینگ ارائه شدند که ایده‌های نوینی را برای کشف آسیب‌پذیری‌ها به‌صورت کارآمد و مقیاس‌پذیر معرفی می‌کنند (برای مثال [10]، [16]، [19]، [31]، [34]–[38]).

برای اینکه روش‌های فازینگ در عمل نیز قابل استفاده باشند، لازم است فازینگ با حداقل دانش اولیه کار کند. با این حال، این موضوع با دو فرض رایج برای افزایش کارایی در تضاد است:
(i) نیاز به شروع با یک مجموعه مناسب از ورودی‌های اولیه به عنوان بذر (seed inputs / corpus) و (ii) در اختیار داشتن یک مولد (generator) برای قالب ورودی (input format).

در غیاب هر یک از این موارد، فازرها باید توانایی یادگیری این را داشته باشند که چه ورودی‌هایی «جالب» محسوب می‌شوند. فازینگ مبتنی بر بازخورد (feedback-driven fuzzing) که توسط AFL محبوب شد، دقیقاً چنین قابلیتی را فراهم می‌کند: ورودی‌هایی که باعث ایجاد رفتار جدید در برنامه می‌شوند ذخیره شده و برای تولید موارد آزمون (testcases) بیشتر استفاده می‌شوند، در حالی که سایر ورودی‌ها کنار گذاشته خواهند شد.

1.1 موانع رایج در فازینگ (Common Fuzzing Roadblocks)

برای انگیزه دادن به رویکرد خود، ابتدا مسئله کشف کارآمد کد جدید را مرور می‌کنیم، با تمرکز بر غلبه بر موانع رایج در فازینگ. در عمل، دو مشکل متداول در فازینگ عبارت‌اند از اعداد جادویی (magic numbers) و آزمون‌های جمع‌آزما (checksum tests). نمونه‌ای از چنین کدی در لیست ۱ قابل مشاهده است.

اولین باگ تنها زمانی قابل کشف است که ۸ بایت ابتدایی ورودی شامل یک هدر جادویی (magic header) مشخص باشد. برای رسیدن به باگ دوم، ورودی باید شامل رشته «RQ» و همچنین دو جمع‌آزما صحیح باشد.

احتمال تولید تصادفی ورودی که این شرایط را برآورده سازد، بسیار ناچیز است. در نتیجه، فازرهای مبتنی بر بازخورد (feedback-driven fuzzers) دیگر قادر به تولید پوشش کد جدید (new coverage) نیستند و فرآیند فازینگ دچار توقف (stall) می‌شود.

لیست ۱: موانع فازینگ مبتنی بر بازخورد:

				
					/* magic number example */
if ( u64 ( input ) == u64 ( " MAGICHDR " ) )
	bug (1) ;
/* nested checksum example */
if ( u64 ( input ) == sum ( input +8 , len -8) )
	if ( u64 ( input +8) == sum ( input +16 , len -16) )
		if ( input [16]== ’R ’ && input [17]== ’Q ’)
			bug (2) ;

در گذشته توجه زیادی برای حل این موانع صورت گرفته است. رویکردهای مختلفی پیشنهاد شدند که معمولاً از تکنیک‌های پیشرفته تحلیل برنامه، مانند ردگیری آلودگی (taint tracking) و اجرای نمادین (symbolic execution) استفاده می‌کنند [12]، [13]، [16]، [22]، [23]، [26]، [35]، [38]، [40]. به‌طور خاص، ابزارهای ANGORA [16] و T-FUZZ [34] در این دسته قرار می‌گیرند.

این رویکردها معمولاً نیاز به توصیف نسبتاً دقیقی از محیط اجرا (مانند رفتار فراخوانی‌های کتابخانه یا سیستم‌عامل زیرین) و معنای دقیق مجموعه دستورالعمل‌های پلتفرم دارند.

در نتیجه، استفاده از این روش‌ها روی اهدافی که از افزونه‌های پیچیده مجموعه دستورالعمل‌ها (مانند دستورهای ممیز شناور/ floating point instructions) یا کتابخانه‌ها و سیستم‌عامل‌های غیرمتداول استفاده می‌کنند، دشوار است.

از این رو، چنین رویکردهایی در نقطه مقابل رویکرد معرفی‌ شده توسط AFL قرار می‌گیرند؛ زیرا موفقیت AFL تا حد زیادی به این واقعیت وابسته است که فرض‌های کمی درباره رفتار برنامه دارد.

بر اساس این بینش، ما یک روش جدید فازینگ را بررسی می‌کنیم که در افزایش پوشش کد (code coverage) روی اهداف متنوع از برنامه‌های متن‌باز در فضای کاربر (userland) گرفته تا هسته‌های سیستم‌عامل (OS kernels) با کد بسته بسیار مؤثر است و عملکرد فوق‌العاده‌ای دارد. ما نشان می‌دهیم که این رویکرد می‌تواند نسبت به استراتژی‌های فازینگ موجود بهتر عمل کند.

1.2 رویکرد ما: تناظر ورودی با وضعیت (Input-to-State Correspondence)

در این مقاله، ما یک روش جدید و سبک (lightweight) پیشنهاد می‌کنیم که در بسیاری از موارد قادر است دو ابزار تحلیل پیچیده یعنی ردگیری آلودگی (taint tracking) و اجرای نمادین (symbolic execution) را جایگزین کند.

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

رویکرد ما بر یک مشاهده ساده اما شهودی استوار است: در بسیاری از موارد، بخش‌هایی از ورودی به‌طور مستقیم به حافظه یا ثبات‌ها (registers) در زمان اجرا متناظر می‌شوند. بنابراین، یک تناظر قوی بین ورودی و وضعیت فعلی برنامه (input-to-state correspondence) وجود دارد که می‌توان از آن برای طراحی یک روش فازینگ کارآمد استفاده کرد.

در عمل، اغلب برنامه‌ها تنها تعداد کمی مرحله رمزگشایی (decoding) روی ورودی اعمال می‌کنند، پیش از آن‌که داده‌های ورودی مورد استفاده قرار گیرند. ما مشاهده کردیم که مجموعه طرح‌های کدگذاری (encoding schemes) مورد استفاده در برنامه‌های واقعی معمولاً بسیار محدود است؛ به‌طور معمول، این مقادیر مستقیماً در زمینه شرایط سخت (hard conditions) مانند بررسی مقدار یک هدر مشخص (magic bytes) استفاده می‌شوند.

برای مثال، بسیار رایج است که بایت‌های ورودی به‌صورت اعداد little-endian (روشی برای نحوه‌ی ذخیره‌سازی اعداد چند بایتی در حافظه است) تفسیر شوند و سپس مستقیماً با یک چک‌سام یا مقادیر خاصی از بایت‌های جادویی (magic bytes) مقایسه شوند.

ما از این مشاهده بهره می‌بریم و برنامه را ردگیری (trace) می‌کنیم تا مقادیر مورد استفاده در دستورهای مقایسه (compare instructions) را مشاهده کنیم. با «رنگی‌کردن» (colorizing) ورودی با بایت‌های تصادفی، یک تقریب بسیار سبک از ردگیری آلودگی (taint tracking) ایجاد می‌کنیم.

سپس فرض می‌کنیم که می‌توانیم این مقادیر را با تغییر بایت‌های متناظر در ورودی کنترل کنیم. در نهایت، از فرآیند سریع فازینگ استفاده می‌کنیم تا بررسی کنیم آیا رفتار جدید و بالقوه جالبی در برنامه تحریک شده است یا خیر. به‌طور مشابه، موارد مثبت کاذب (false positives) که از این تقریب‌زنی بیش‌ازحد ناشی می‌شوند، به ‌سرعت حذف می‌گردند.

این روش به ما اجازه می‌دهد بخش‌های پیچیده کد مانند فراخوانی‌های API یا دستورهای ناشناخته را نادیده بگیریم؛ بخش‌هایی که در غیر این صورت برای ردگیری آلودگی یا اجرای نمادین (symbolic execution) به ‌سختی قابل مدیریت هستند. در نتیجه، حتی ورودی‌هایی که از توابع کتابخانه‌ای ناشناخته، حلقه‌های بزرگ وابسته به داده، و دستورالعمل‌های ممیز شناور (floating point instructions) عبور می‌کنند، تأثیر قابل‌توجهی بر کیفیت نتایج ندارند.

ما از همین اصل برای پیاده‌سازی یک روش مبتنی بر وصله (patching) جهت مدیریت آزمون‌های جمع‌آزما استفاده می‌کنیم. برخلاف رویکردهای مشابه، رویکرد ما کاملاً از اجرای نمادین اجتناب می‌کند، در حالی که همواره یک صف (queue) از ورودی‌های دارای جمع‌آزما (checksums) معتبر و بدون مثبت کاذب (false positives) حفظ می‌کند.

فازرهای مبتنی بر بازخورد (feedback-driven fuzzers) معمولاً از یک ابزارگذاری (instrumentation) یکسان در تمام اجراها استفاده می‌کنند تا پوشش کد (code coverage) و سایر اطلاعات بازخوردی را اندازه‌گیری کنند. برای مثال، ابزار VUZZER از قابلیت‌های کامل ردگیری آلودگی (taint tracking) خود روی هر ورودی تولید شده استفاده می‌کند.

از آنجا که اغلب اجرا‌های فازینگ (از میلیون‌ها تا میلیاردها بار اجرا) بر روی تعداد محدودی ورودی پایه (از هزاران تا صدها هزار ورودی) انجام می‌شود، ما پیشنهاد می‌کنیم که تحلیل را به شکل متفاوتی در فازینگ مبتنی بر بازخورد ادغام کنیم: ما فرآیند تحلیل پرهزینه را از فرآیند فازینگ جدا می‌کنیم.

در روش ما، جست‌وجوی پرهزینه برای یافتن تناظر ورودی با وضعیت وابسته به مسیر (path-specific input to-state correspondences) تنها یک‌بار برای هر ورودی جدیدی که کشف می‌شود انجام می‌گیرد. سپس تمام عملیات فازینگ واقعی بدون این سربار اضافی (overhead) صورت می‌پذیرد. ما دریافتیم که این رویکرد به‌طور قابل‌توجهی هزینه ناشی از تحلیل‌های سنگین را کاهش می‌دهد و در عین حال به فرآیند فازینگ اجازه می‌دهد از دانشی که در مرحله تحلیل به ‌دست آمده است، بهره‌برداری کند.

در حالی که رویکرد ما را می‌توان به‌ عنوان یک تقریب از ردگیری آلودگی (taint tracking) و اجرای نمادین (symbolic execution) در نظر گرفت، نتایج ارزیابی ما در عمل کاملاً رقابتی و حتی در برخی موارد بهتر از ابزارهایی است که از نسخه‌های «واقعی» و پرهزینه این تکنیک‌ها استفاده می‌کنند.

ما به منظور انجام ارزیابی، یک پیاده‌سازی اولیه (prototype) از روش خود با نام REDQUEEN توسعه دادیم که قادر است اهداف صرفاً باینری (binary-only targets) را پردازش کند.

ارزیابی تجربی ما روی مجموعه GNU binutils نشان می‌دهد که روش ما در تمام موارد قادر است به‌طور قابل توجهی پوشش کد بیشتری نسبت به ابزارهای موجود ایجاد کند. اندازه‌گیری زمان لازم برای رسیدن به پوشش برابر (equal coverage) نشان می‌دهد که سرعت ما در مقایسه با VUZZER [35] و KLEE [12] در بازه‌ی ×۵ تا ×۵۰۰۰ افزایش دارد، و در مقایسه با AFLFAST [10] و LAF-INTEL [2] نیز بین ×۲ تا ×۲۰۰ سریع‌تر است.

علاوه بر این، ما نخستین روشی هستیم که موفق شده‌ایم تعداد قابل‌توجهی باگ بیشتر (۲۶۰۰) نسبت به باگ‌های فهرست‌ شده در مجموعه داده LAVA-M (۲۲۶۵ مورد) پیدا کنیم. در مجموع، ۳۳۵ باگ اضافیِ فهرست ‌نشده کشف کردیم که معادل بیش از ۱۱۴٪ از کل باگ‌های ثبت ‌شده است. همچنین تنها دو مورد از ۲۲۶۵ آسیب‌پذیری موجود در مجموعه LAVA-M را از دست دادیم (یعنی بیش از ۹۹.۹٪ پوشش باگ‌ها).

علاوه بر این، تکنیک ما از بخش قابل‌توجهی از سربار پیاده‌سازی و عملکرد (implementation and performance overhead) که معمولاً با ردگیری آلودگی (taint tracking) و اجرای نمادین (symbolic execution) همراه است، جلوگیری می‌کند.

در نتیجه، رویکرد ما بر روی مجموعه بسیار متنوع‌تری از اهداف نسبت به روش‌های مذکور که نیازمند یک مدل دقیق از محیط اجرا هستند، قابل استفاده و اجرا است. در واقع، REDQUEEN قادر است برنامه‌ها را بدون نیاز به کد منبع (source code) یا دانش خاصی از پلتفرم، فاز کند؛ همان‌طور که با اعمال آن بر اهداف در فضای کرنل (هسته) (kernel-space) و همچنین فضای کاربر (user-space) نشان می‌دهیم.

در ارزیابی ما، REDQUEEN موفق به کشف ۱۰ باگ در ۲ درایور سیستم فایل لینوکس و ۵۵ باگ در ۱۶ برنامه و کتابخانه در فضای کاربر شد. علاوه بر این، برای برخی از آسیب‌پذیری‌های مهم‌تر کشف‌شده، ۱۶ شناسه CVE اختصاص داده شده است.

1.3 مشارکت‌ها (Contributions)

به‌طور خلاصه، مشارکت‌های ما به شرح زیر است:

ما مفهوم تناظر ورودی با وضعیت (input-to-state correspondence) را به‌ عنوان یک اصل جدید معرفی می‌کنیم که می‌تواند به‌طور قابل‌توجهی فازینگ مبتنی بر بازخورد (feedback-driven fuzzing) را تسریع کند.
نشان می‌دهیم که می‌توان از این تناظر به‌جای ردگیری آلودگی (taint tracking) و اجرای نمادین (symbolic execution) برای حل مشکلات دشوار فازینگ مانند برخورد با اعداد جادویی (magic numbers)، مقایسه‌های چندبایتی پویا (dynamic multi-byte compares)، و آزمون‌های جمع‌آزمای تو‌در‌تو (nested checksums) استفاده کرد، بدون اینکه هیچ مثبت کاذبی (false positive) ایجاد شود. در نتیجه، عملگر جهش (mutation operator) حاصل، از نظر تعداد مسیرهای جدید کشف‌ شده در طول زمان، کارآمدتر از تمام عملگرهای جهش مورد استفاده در AFL است.
ما یک پیاده‌سازی اولیه از روش خود را در ابزاری به نام REDQUEEN توسعه داده‌ایم. نتایج ارزیابی جامع ما نشان می‌دهد که REDQUEEN در چندین معیار، عملکردی بهتر از تمامی ابزارهای فازینگ پیشرفته موجود (state-of-the-art) دارد.

ما به منظور تسهیل و تشویق پژوهش در این حوزه، فازر خود را در گیت هاب منتشر کرده‌ایم.

2. کارهای مرتبط (RELATED WORK)

فازینگ (Fuzzing) برای چندین دهه یک حوزه فعال پژوهشی بوده است. در ابتدا، تمرکز زیادی بر بهبود فازینگ جعبه ‌سیاه (black-box fuzzing) وجود داشت (یعنی روش‌هایی که در آن فازر هیچ دیدی نسبت به ساختار داخلی برنامه ندارد و آن را به‌صورت یک جعبه ‌سیاه در نظر می‌گیرد). این تلاش‌ها منجر به بهبود الگوریتم‌های زمان‌بندی (scheduling algorithms) [14]، [36]، [41] و همچنین توسعه روش‌های مؤثرتر برای جهش (mutation) یا تولید ورودی [4]، [29] شد. حتی تکنیک‌های یادگیری ماشین (machine learning) نیز برای استنتاج ورودی‌های نیمه‌معتبر به‌عنوان موارد آزمون (Testcase) مورد بررسی قرار گرفتند [8]، [24]، [27].

در سال‌های اخیر، تمرکز بیشتری بر روی فازینگ جعبه‌ سفید (white-box) و جعبه ‌خاکستری (gray-box fuzzing) قرار گرفته است. معمولاً در این رویکردها، برنامه تحت آزمون با ابزارگذاری (instrumentation) تجهیز می‌شود تا نوعی بازخورد (feedback)، مانند پوشش کد (code coverage) تولید کند.

نمونه‌ی شاخص فازر جعبه ‌خاکستری، ابزار AFL [44] است. این ابزار از پوشش کد به‌عنوان مکانیزم بازخورد استفاده می‌کند تا یاد بگیرد کدام ورودی‌ها جالب هستند و کدام ورودی‌ها رفتار جدیدی در برنامه ایجاد نمی‌کنند.

بخش زیادی از کارهای اخیر بر پایه AFL توسعه یافته‌اند. به‌عنوان مثال، زمان‌بندی اجرای AFL توسط AFLFAST [10] تحلیل و بهبود داده شده است. ابزارهای COLLAFL [19] و INSTRIM [30] با کاهش احتمال اینکه دو مسیر متفاوت به‌اشتباه یکسان در نظر گرفته شوند، عملکرد AFL را بهبود می‌دهند.

همچنین عملکرد خود فازرها نیز به روش‌های مختلفی ارتقا یافته است [25]، [42]. یکی از نمونه‌های قابل توجه، go-fuzz [39] است که به‌صورت مستقل توسعه یافته و از ایده‌ای مشابه با REDQUEEN استفاده می‌کند.

پروژه OSS-FUZZ [1] مدل فازینگ AFL را در مقیاس خوشه‌های محاسباتی بزرگ (large computing clusters) گسترش داده و موفق به کشف تعداد قابل توجهی آسیب‌پذیری در نرم‌افزارهای متن‌باز بسیار مهم شده است.

ابزارهای HONGGFUZZ [6] و KAFL [37] از الگوریتم‌هایی الهام‌گرفته از AFL و همچنین از قابلیت‌های مدرن پردازنده‌ها (CPU extensions) استفاده می‌کنند تا نشان دهند چگونه می‌توان اهداف صرفاً باینری (binary-only targets) را به شکل کارآمد فاز کرد.

در این کار، ما تلاش می‌کنیم مشکلاتی را حل کنیم که معمولاً توسط تکنیک‌های فازینگ جعبه‌ سفید (white-box fuzzing) مورد هدف قرار می‌گیرند. بنابراین، از این بخش برای تفکیک رویکرد خود از کارهای موجود در حوزه فازینگ استفاده می‌کنیم.

2.1 فازینگ مبتنی بر اجرای نمادین/کونکولیک (Symbolic/Concolic Execution-based Fuzzing)

چندین ابزار فازینگ جعبه خاکستری یا سفید از اجرای نمادین (symbolic execution) برای بهبود پوشش تست (test coverage) استفاده می‌کنند [12]، [13]. اجرای نمادین می‌تواند آسیب‌پذیری‌هایی را کشف کند که فعال کردن آنها به صورت تصادفی یا حتی با روش‌های اکتشافی هوشمندانه بسیار دشوار است. با این حال، این روش در اهداف بزرگ بسیار کُند می‌شود و مسئله‌ی انفجار حالت‌ها (state explosion) باید با دقت مدیریت شود.

یکی از رویکردهای رایج برای کنترل این مشکل، استفاده از اجرای کونکولیک (concolic execution) است [21]–[23]، [26]، [33]، [38]، [40]. در اجرای کونکولیک، مسیر اجرای برنامه روی یک مسیر عینی (concrete path) محدود می‌شود، در حالی که حل‌کننده (solver) تلاش می‌کند یا باگ‌ها را روی همان مسیر فعال کند یا مسیرهای جدیدی را کشف نماید. این رویکرد به‌طور قابل توجهی تعداد حالت‌هایی را که باید بررسی شوند کاهش می‌دهد و در برخی موارد می‌تواند با جایگزین کردن عبارات پیچیده با مقادیر عینی آن‌ها، پیچیدگی فرمول‌های تولیدشده را نیز کاهش دهد.

علاوه بر این، اجرای نمادین اغلب با هدف حل بررسی‌های مربوط به بایت‌های جادویی (magic bytes) مطرح شده است. نتایج ما نشان می‌دهد که در ارزیابی تجربی ما، یک رویکرد بسیار ساده‌تر نیز اغلب برای حل این موارد کافی است.

2.2 فازینگ مبتنی بر آلودگی (Taint-based Fuzzing)

ردگیری آلودگی (taint tracking)، مشابه اجرای نمادین (symbolic execution)، به‌طور گسترده در ابزارهای فازینگ مورد استفاده قرار می‌گیرد. این تکنیک امکان می‌دهد مشخص شود کدام بخش‌های ورودی بر روی عملیات خاصی در برنامه تأثیر می‌گذارند.

در گذشته، از ردگیری آلودگی برای شناسایی و تمرکز بر بخش‌هایی از ورودی استفاده می‌شد که به‌ عنوان بایت‌های جادویی (magic bytes) [35]، آدرس‌ها (addresses) [20]، [26]، [35]، یا اعداد صحیحی که ممکن است دچار سرریز (overflow) شوند [33] به کار می‌روند.

در این مقاله نشان می‌دهیم که تناظر ورودی-به-حالت (input-to-state correspondence) می‌تواند در بسیاری موارد به‌ عنوان یک تقریب (approximation) برای ردگیری آلودگی عمل کند و این مسائل رایج را با کارایی بسیار بالاتری حل نماید.

به ‌تازگی یک رویکرد فازینگ مبتنی بر آلودگی با نام ANGORA [16] نیز معرفی شده است. مشابه روش ما، ANGORA نیز از مرحله پرهزینه ردگیری آلودگی تنها به ‌صورت محدود (sparsely) برای عبور از شرایط دشوار استفاده می‌کند.

با این حال، تفاوت اصلی این است که ANGORA به دسترسی به کد منبع (source code) و یک مسیر ویژه در کامپایلر (compiler pass) برای انجام کارآمد ردگیری آلودگی متکی است، در حالی که ما یک فازر در سطح باینری (binary-level fuzzer) ارائه می‌دهیم. علاوه بر این، ANGORA قادر به مدیریت جمع‌آزما‌ها (checksums) نیست.

2.3 فازینگ مبتنی بر وصله‌گذاری (Patching-based Fuzzing)

اغلب ابزارهای مبتنی بر اجرای نمادین (symbolic execution) قادرند جمع‌آزما‌های (checksums)معتبر تولید کنند، اما نمی‌توانند از مؤلفه سریع‌تر فازینگ برای پیمایش کد پس از مرحله بررسی (check) استفاده کنند. برخی فازرها تلاش می‌کنند بررسی‌های سخت (hard checks) را وصله‌گذاری (patch) کنند تا یک برنامه مشخص را برای فازینگ ساده‌تر سازند.

سه نمونه از روش‌های فازینگ که از این رویکرد استفاده می‌کنند عبارت‌اند از: FLAYER [18]، TAINTSCOPE [40] و T-FUZZ [34]. از آنجا که ما نیز برای فازینگ کارآمد، آزمون‌های جمع‌آزما‌ها را وصله‌گذاری می‌کنیم، بحث کامل‌تر این ابزارها در بخش 3.2 ارائه شده است.

ایده ما برای مدیریت جمع‌آزما‌ها از هر دو ابزار FLAYER و TAINTSCOPE الهام گرفته است. با این حال، FLAYER نیازمند یک فهرست صریح از شاخه‌های شرطی (conditional branches) به منظور وصله‌کردن است. علاوه بر این، کاربر باید پس از اتمام فرآیند فازینگ، ورودی‌ها را به ‌صورت دستی اصلاح کند.

در مقابل، TAINTSCOPE قادر است به‌ طور خودکار فهرست این بررسی‌ها را استخراج کرده و تمام شاخه‌های سخت را در حین فازینگ وصله‌ کند و سپس، پس از پایان فرآیند فازینگ، از اجرای نمادین (symbolic execution) برای اصلاح ورودی‌های منجر به کرش استفاده کند.

مشابه TAINTSCOPE، فرآیند ما نیز کاملاً خودکار است. با این تفاوت که ما با استفاده از مفهوم تناظر ورودی با وضعیت (input-to-state correspondence) از روش‌های پیچیده و اغلب شکننده‌ی ردگیری آلودگی (taint tracking) و اجرای نمادین (symbolic execution) اجتناب می‌کنیم.

ابزار T-FUZZ نیز رویکردی مشابه TAINTSCOPE دارد: در آن، برنامه به‌گونه‌ای تغییر داده می‌شود که بتوان پس از شرایط سخت به کد دسترسی پیدا کرد و سپس بررسی‌های ناقص با استفاده از اجرای نمادین اصلاح می‌شوند.

بهبود عملکردی که REDQUEEN نسبت به T-FUZZ ارائه می‌دهد، تا حدی ناشی از این واقعیت است که T-FUZZ باید برای هر بخشِ سخت‌دسترس کد، نمونه‌های جدید فازینگ (fuzzing instances) ایجاد کند. علاوه بر این، T-FUZZ در طول فازینگ، موارد مثبت کاذب (false positives) را حذف نمی‌کند؛ در نتیجه تعداد نمونه‌هایی که روی مسیرهای بن‌بست (dead ends) کار می‌کنند می‌تواند تقریباً بدون محدودیت افزایش یابد.

در مقابل، رویکرد ما با نگه‌داشتن همیشگی یک صف از ورودی‌های معتبر (queue of valid inputs) از بروز این مشکلات مقیاس‌پذیری جلوگیری می‌کند. بنابراین REDQUEEN نه مثبت کاذب تولید می‌کند و نه زمان خود را صرف آن‌ها می‌نماید.

2.4 فازرهای صرفاً باینری (Binary-Only Fuzzers)

بسیاری از فازرها مانند AFL، LAF-INTEL و ANGORA برای افزودن ابزارگذاری (instrumentation) و وصله‌ها (patches) نیاز به دسترسی به کد منبع دارند. در نتیجه، سیستم‌های اختصاصی (proprietary systems) با این ابزارها قابل تحلیل نیستند.

برای غلبه بر این محدودیت، برخی فازرها از مکانیزم‌های دیگری برای به ‌دست آوردن بازخورد استفاده می‌کنند. به عنوان مثال، AFL شاخه‌های متعددی (forks) ایجاد کرده است که از ابزارهایی مانند PIN [32]، DynamoRIO [11] یا QEMU [9] برای استخراج اطلاعات پوشش کد (coverage information) استفاده می‌کنند.

به‌طور مشابه، فازرهایی مانند VUZZER، TAINTSCOPE، FLAYER، T-FUZZ و DRILLER از ابزارگذاری‌های باینری پویای (dynamic binary instrumentation) مختلف بهره می‌برند.

ما مشاهده کردیم که سریع‌ترین فازرِ صرفاً باینری، نسخه‌ی AFL مبتنی بر QEMU است، که با این حال از نظر تعداد اجرا در ثانیه (executions per second) به‌طور قابل توجهی کُندتر از نسخه AFL با ابزارگذاری‌ زمان کامپایل (compile-time instrumentation) است.

2.5 خانواده AFL – (The AFL Family)

با توجه به موفقیت چشمگیر طراحی AFL، ابزارهای مختلف زیادی به ‌طور گسترده بر پایه آن توسعه یافته‌اند [1]، [2]، [5]، [10]، [16]، [31]، [37]، [38]. کار ما نیز بر اساس KAFL ــ یک فازر مشابه AFLــ است و بنابراین داشتن یک درک کلی از طراحی AFL ضروری است. به‌طور کلی، فازرهای خانواده AFL دارای سه مؤلفه مهم (i) صف (queue)، (ii) بیت‌مپ (bitmap) و (iii) عملگرهای جهش(mutators) می‌باشند.

صف جایی است که تمام ورودی‌ها در آن ذخیره می‌شوند. در طول فرآیند فازینگ، یک ورودی از صف انتخاب می‌شود، برای مدتی فاز می‌گردد و در نهایت دوباره به صف بازمی‌گردد.

پس از انتخاب یک ورودی، عملگرهای جهش مجموعه‌ای از جهش‌ها (mutations) را روی آن اعمال می‌کنند. پس از هر مرحله، ورودی تغییر‌یافته اجرا می‌شود. هدف به‌گونه‌ای ابزارگذاری (instrumented) شده است که پوشش ایجاد شده توسط ورودی در یک بیت‌مپ (bitmap) ثبت گردد.

چنانچه ورودی باعث ایجاد پوشش جدید شود (و در نتیجه یک بیت جدید در bitmap تنظیم شود)، آن ورودی به صف اضافه می‌شود؛ در غیر این صورت، ورودی جهش‌یافته کنار گذاشته می‌شود. عملگرهای جهش در چندین مرحله سازمان‌دهی شده‌اند. مراحل اولیه، مراحل قطعی (deterministic stages) نام دارند. این مراحل هر بار که ورودی از صف انتخاب شود، فقط یک‌بار اعمال می‌شوند و شامل مجموعه‌ای از جهش‌های ساده مانند «تلاش برای معکوس کردن هر بیت» هستند.

پس از پایان مراحل قطعی یا زمانی که یک ورودی برای بار دوم انتخاب شود، مرحله موسوم به havoc اجرا می‌شود. در این مرحله، چندین جهش تصادفی به‌صورت هم‌زمان و در موقعیت‌های تصادفی روی ورودی اعمال می‌شود. همچنین اگر کاربر یک دیکشنری شامل رشته‌های جالب ارائه داده باشد، این رشته‌ها در موقعیت‌های تصادفی به ورودی اضافه می‌شوند. مرحله مرتبط دیگر با havoc، مرحله ترکیب دو ورودی (splicing) است که در آن دو ورودی مختلف در یک نقطه تصادفی با یکدیگر ترکیب (merge) می‌شوند.

3. تناظر ورودی با وضعیت (INPUT-TO-STATE CORRESPONDENCE)

در این بخش، ما یک روش جدید فازینگ را بر اساس این بینش معرفی می‌کنیم که برنامه‌ها دارای یک تناظر قوی بین ورودی و وضعیت (input-to-state correspondence) هستند.

ما مشاهده می‌کنیم که در تعداد بسیار زیادی از برنامه‌ها، مقادیر موجود در ورودی به‌ صورت مستقیم در حالت‌های مختلف اجرای برنامه مورد استفاده قرار می‌گیرند. با مشاهده این مقادیر، می‌توان حدس‌های آگاهانه‌ای درباره این‌که کدام آفست‌ها (offsets) در ورودی باید تغییر داده شوند (مشابه یک نوع بسیار سبک از ردگیری آلودگی / taint tracking) و همچنین این‌که چه مقادیری باید جایگزین شوند (مشابه رویکردهای مبتنی بر اجرای نمادین / symbolic execution) انجام داد.

با استفاده از این رابطه، می‌توان مشکلات دشوار فازینگ مانند بایت‌های جادویی (magic bytes) و حتی جمع‌آزماهای تو‌در‌تو (nested checksums) را مدیریت کرد. در ادامه، اجزای مختلف این روش را توضیح می‌دهیم و بررسی می‌کنیم که چگونه هر یک از آن‌ها به حل چالش‌های فازینگ که پیش‌تر معرفی شدند کمک می‌کنند.

3.1 بایت‌های جادویی (Magic Bytes)

اولین مانعی که به آن می‌پردازیم، بایت‌های جادویی (magic bytes) است. یک نمونه‌ی معمول از این دسته مشکلات فازینگ در لیست ۲ نشان داده شده است؛ این قطعه در واقع بخشی از مثال جاری ما است که در لیست ۱ معرفی شده بود. باید توجه داشت که اگرچه در مثال ما برای خوانایی از مقادیر ASCII استفاده شده است، اما مفهوم تناظر ورودی با وضعیت (input-to-state correspondence) به‌طور کامل برای قالب‌های باینری (binary formats) نیز قابل استفاده است.

لیست ۲: مشکل فازینگ (1): یافتن ورودی معتبر برای دور زدن بایت‌های جادویی:

				
					if ( u64 ( input ) == u64 ( " MAGICHDR " ) )
	bug (1) ;

جدول ۱: استخراج مجموعه جهش‌ها از مقایسه مشاهده‌ شده در زمان اجرا، با استفاده از کدگذاری little-endian:

این ساختارها (constructs) برای فازرهای مبتنی بر بازخورد (feedback-driven fuzzers) به‌ سختی قابل حل هستند، چرا که احتمال حدس زدن یک ورودی مناسب بسیار پایین است؛ در این مورد خاص، ورودی ۶۴ بیتی MAGICHDR. رویکردهای موجود [16]، [23]، [34]، [35]، [38]، [40] معمولاً از ردگیری آلودگی (taint tracking) و اجرای نمادین (symbolic execution) استفاده می‌کنند که هر دو دارای سربار عملکردی قابل توجهی هستند.

یک رویکرد متفاوت استفاده از دیکشنری‌های تعریف ‌شده توسط کاربر (user-defined dictionaries) است [43] که دانش تخصصی درباره برنامه تحت آزمون را مدل‌سازی می‌کنند. در نهایت، روش‌هایی نیز وجود دارند که مقایسه‌های چندبایتی (multi-byte comparisons) را به مجموعه‌ای از مقایسه‌های تک‌بایتی (one-byte comparisons) تبدیل می‌کنند. در این صورت، فازر می‌تواند هر بایت را به ‌صورت جداگانه حل کند. نمونه شاخص این دسته، ابزار LAF-INTEL [2] است که در حل مقایسه‌های چندبایتی بسیار کارآمد می‌باشد، اما برای اعمال تغییرات در برنامه نیاز به دسترسی در سطح کد منبع دارد.

ابزار دیگری به نام STEELIX [31] وجود دارد که به دسترسی به کد منبع وابسته نیست و در عوض از ابزارگذاری باینری پویا (dynamic binary instrumentation) برای شکستن مقایسه‌های بزرگ به مقایسه‌های کوچک‌تر استفاده می‌کند. با این حال، این رویکرد دارای سربار عملکردی قابل توجهی است. نویسندگان STEELIX گزارش کرده‌اند که LAF-INTEL بیش از ۷ برابر تعداد اجرای بیشتری در ثانیه نسبت به STEELIX انجام می‌دهد.

ما یک رویکرد سبک مبتنی بر تناظر ورودی با وضعیت (input-to-state correspondence) پیشنهاد می‌دهیم تا به‌صورت کاملاً خودکار با بایت‌های جادویی (magic bytes) مقابله کند. در این روش از این واقعیت استفاده می‌کنیم که مقادیر موجود در وضعیت برنامه اغلب به‌طور مستقیم با بخش‌هایی از ورودی متناظر هستند.

هر زمان که به یک مسیر جدید (new path) برخورد می‌کنیم، تمام دستورهای مقایسه (compare instructions) را هوک (hook) کرده و یک اجرای ردیابی (trace run) انجام می‌دهیم. اگر به مقایسه‌ای با عملوندهای متفاوت برخورد کنیم، هر دو مقدار مقایسه‌ شده را استخراج کرده و یک جهش سفارشی (custom mutation) از نوع <pattern → replacement> ایجاد می‌کنیم، همان‌طور که در ادامه توضیح داده می‌شود. مراحل مختلف این فرآیند در جدول ۱ نشان داده شده‌اند.

1) ردیابی (Tracing). هنگامی که فازینگ را با یک ورودی جدید آغاز می‌کنیم (پیش از ورود به مرحله قطعی در KAFL)، یک اجرای منفرد (single run) انجام می‌دهیم که در آن تمام دستورهای مقایسه (compare instructions) را هوک (hook) کرده و آرگومان‌های آن‌ها را استخراج می‌کنیم. این شامل برخی دستوراتی نیز می‌شود که توسط کامپایلرها به‌ جای مقایسه‌های ساده یا ساختارهای switch-case تولید می‌شوند (به ‌عنوان مثال از طریق محاسبه آفست‌ها (offset) در جدول‌های پرش (jump tables)).

علاوه بر این، تمام دستورات فراخوانی (call instructions) نیز رهگیری (hook)می‌شوند، زیرا توابع ممکن است پیاده‌سازی‌هایی از مقایسه رشته‌ها (string comparisons) و قابلیت‌های مشابه را انجام دهند. جزئیات بیشتر در بخش 4 ارائه شده است.

مثال ۱. ورودی «TestSeedInput» را برای کد ارائه‌ شده در لیست ۲ در نظر بگیرید. دستور مقایسه، بررسی می‌کند که آیا ۸ بایت ابتدایی ورودی ــدر قالب یک مقدار صحیح بدون علامت ۶۴ بیتی (unsigned 64-bit)ــ با تفسیر ۶۴ بیتی بدون علامت رشته «MAGICHDR» برابر است یا خیر. از آنجا که اعداد صحیح معمولاً با قالب little-endian کدگذاری می‌شوند، نمایش ASCII مقادیر نهایی مورد استفاده در این مقایسه به صورت «deeStesT» و «RDHCIGAM» خواهد بود.

2) تغییرات (Variations). ما در زمان اجرا، نمی‌دانیم پس از انجام مقایسه چه فلگ‌هایی (flags) بررسی می‌شوند؛ بنابراین نمی‌توانیم بین انواع مختلف عملیات مقایسه مانند «کوچکتر یا (lower than) و برابر با (equal to)» تمایز قائل شویم. به همین دلیل، تغییراتی را روی مقدار مقایسه‌ شده مانند جمع یا تفریق یک واحد (1±) اعمال می‌کنیم. به‌عنوان اثر جانبی این عمل ابتکاری، به‌صورت تجربی مشاهده کردیم که این رویکرد احتمال فعال‌سازی باگ‌های off-by-one را افزایش می‌دهد.

مثال ۲. در این حالت، مقدار «RDHCIGAM» را یک واحد افزایش و کاهش می‌دهیم و به ترتیب مقادیر «RDHCIGAL» و «RDHCIGAN» به‌ دست می‌آید.

3) کدگذاری‌ها (Encodings). به احتمال زیاد، ورودی قبل از رسیدن به مرحله مقایسه واقعی، به شکل‌های مختلفی پردازش شده است. به منظور مدیریت رایج‌ترین موارد رمزگذاری/رمزگشایی ورودی (input en-/decoding) و همچنین تولید کاندیدهای جهش بیشتر، ما انواع مختلفی از کدگذاری‌ها (encodings) را روی جهش اعمال می‌کنیم. نمونه‌هایی از این کدگذاری‌ها شامل معکوس‌کردن اثر گسترش صفر (inverting zero extensions) یا تبدیل ترتیب بایت‌ها (endianness conversions) است.

مثال ۳. ما یک کدگذاری little-endian را روی جهش‌های فعلی «RDHCIGAM» و «RDHCIGAL» اعمال می‌کنیم و به ترتیب مقادیر «MAGICHDR» ،«LAGICHDR» و «NAGICHDR» را به ‌دست می‌آوریم.

مشاهده می‌کنیم که به‌ طور کلی تنها چند طرح کدگذاری (encoding scheme) ساده مورد نیاز است. رایج‌ترین حالت به‌مراتب، نگاشت یک‌به‌یک (one-to-one mapping) بین مقادیر ورودی (input values) و مقادیر حالت (state values) است. به‌طور دقیق، کدگذاری‌هایی که در آزمایش‌های خود استفاده کرده‌ایم عبارت‌اند از:

Zero/Sign Extend(n): مقدار به‌ صورت یک عدد صحیح در قالب little-endian تفسیر می‌شود و با گسترش صفر (zero extension) یا گسترش علامت (sign extension) به اندازه بزرگ‌تر تبدیل می‌گردد؛ سپس بایت‌های ابتدایی (leading bytes) حذف می‌شوند تا در صورت امکان یک نسخه n بایتی از الگو تولید گردد. زمانی که تغییری در اندازه رخ ندهد، این کدگذاری «plain encoding» نیز نامیده می‌شود.
Reverse: تمام کدگذاری‌های مبتنی بر little-endian دارای معادل big-endian هستند و این تبدیل، ترتیب بایت‌ها را معکوس می‌کند.
C-String: مقدار به‌ عنوان یک رشته C در نظر گرفته می‌شود و هر چیزی پس از اولین بایت صفر (0x00) حذف می‌گردد.
Memory(n): مقدار به ‌عنوان ورودی یک تابع مشابه memcmp در نظر گرفته می‌شود؛ در این حالت فقط اولین n بایت (با n ∈ {4, 5, …, 32}) بررسی می‌شود.
ASCII: مقدار عددی به ‌صورت رشته‌ای از ارقام ASCII (نمایش متنی عدد) کدگذاری می‌شود.

پس از ارزیابی دستی پوشش کد (coverage) تولید شده توسط فازر ما، معتقدیم که مجموعه طرح‌های کدگذاری ذکرشده، بخش بزرگی از کاربردهای رایج در برنامه‌های دنیای واقعی را پوشش می‌دهد. در موارد نادری که این کدگذاری‌ها کافی نیستند، می‌توان مجموعه کدگذاری‌ها را مشابه فرهنگ لغت (dictionary) در سایر سیستم‌های فازینگ، به‌عنوان ورودی کاربر در نظر گرفت. در این حالت، کاربر می‌تواند به‌سادگی کدگذاری‌های اختصاصی و دقیق‌تری را ارائه دهد. این مرحله را می‌توان به عنوان یک نوع سبک از یک الگوریتم سنتز (الگوریتم تولید خودکار یا synthesis algorithm) که برای حدس زدن حالت نمادین در موقعیت فعلی استفاده می‌شود، در نظر گرفت. در واقع، این رویکرد در مقایسه با سایر رویکردها برای استنباط چگونگی تأثیر ورودی بر حالت (مانند اجرای نمادین یا سنتز برنامه (program synthesis)) یک مزیت عمده دارد. نمایش عملیات پیچیده مانند تبدیل اعداد اعشاری ASCII به اعداد صحیح بسیار آسان است. این به این دلیل است که ما فقط نیاز به انجام رمزگذاری روی مقادیر واقعی داریم، به جای اینکه از حل‌کننده‌های SMT (یا (SMT solvers)) با مقادیر نمادین پرس‌وجو کنیم.

4) کاربرد (Application). در نهایت و مهم‌تر از همه، ما از الگوی جهش <pattern 7 → repl> استفاده می‌کنیم تا بخش‌هایی از ورودی را که باید با مقدار جایگزین (repl) تعویض شوند، شناسایی کنیم. برخلاف رویکردهای دیگر مانند ANGORA یا STEELIX، ما کل الگو را به ‌صورت یکجا اعمال می‌کنیم. این کار دارای دو مزیت است. اول اینکه برای مقایسه‌های اتمیک (atomic comparisons) بدون نیاز به تغییر یا هوک (hook) بیشتر هدف نیز کار می‌کند. دوم اینکه به ‌طور قابل توجهی تعداد موقعیت‌های کاندید (candidate positions) که باید برای انجام جایگزینی امتحان شوند را کاهش می‌دهد.

مثال ۴. تنها زیررشته «TestSeed» از ورودی «TestSeedInput» با مقدار «MAGICHDR» مقایسه می‌شود. بنابراین، ما فقط همین بخش را با جهش‌های تولید شده جایگزین می‌کنیم. این کار منجر به تولید موارد آزمایشی (Testcase) جدید «MAGICHDRInput» می‌شود و با اعمال تغییرات معرفی ‌شده برای حل نامساوی‌ها (inequalities)، ورودی‌های «LAGICHDRInput» و «NAGICHDRInput» نیز به ‌دست می‌آیند (و همچنین ممکن است ورودی‌های بیشتری با توجه به سایر طرح‌های کدگذاری تولید شوند).

5) رنگی‌سازی (Colorization). ما مشاهده کردیم که تعداد موقعیت‌های کاندید برای اعمال یک وصله (patch) گاهی بسیار زیاد است. برای مثال، کوچک‌ترین تصویر (image) معتبر سیستم فایل ext4 حدود ۶۴ کیلوبایت حجم دارد و عمدتاً از دنباله‌های طولانی بایت صفر تشکیل شده است. در چنین شرایطی، مقایسه یک مقدار صفر با یک مقدار ثابت می‌تواند بیش از ۶۰٬۰۰۰ موقعیت ممکن ایجاد کند. ما در ارزیابی خود متوجه شدیم که این نوع مقایسه‌ها بسیار رایج هستند. بنابراین، یک روش کارآمد طراحی کردیم تا تعداد بایت‌های تصادفی در ورودی را افزایش دهیم. افزایش آنتروپی یا تصادفی ‌بودن داده (entropy) در ورودی باعث کاهش فضای موقعیت‌های ممکن می‌شود. با استفاده از این نسخه «رنگی‌ شده» (colored) از ورودی، تعداد موقعیت‌های کاندید به‌طور چشمگیری (معمولاً چندین برابر) کاهش می‌یابد. پس از تولید نسخه رنگ شده، فقط در موقعیت‌هایی جهش را اعمال می‌کنیم که بخش الگو (pattern) در هر دو ورودی در یک آفست (offset) یکسان یافت شده باشد. در نتیجه، تعداد نهایی جهش‌هایی که باید اعمال شوند به‌شدت کاهش می‌یابد. در ارزیابی ما مشخص شد که تعداد جهش‌های تولید شده با این روش معمولاً دو برابر کمتر از تعداد جهش‌های قطعی است که AFL روی همان ورودی اعمال می‌کند.

مثال ۵. فرض کنید در مثال جاری، ورودی «ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ» را تست می‌کنیم. در میان جهش‌ها، به الگویی مانند <ZZZZZZZZ → MAGICHDR> می‌رسیم. این جهش می‌تواند در موقعیت‌های مختلفی (در اینجا ۲۴ موقعیت) اعمال شود. بنابراین، تلاش می‌کنیم تا حد امکان کاراکترها را بدون تغییر مسیر اجرای برنامه (execution path) جایگزین کنیم. در این حالت، نسخه‌ی رنگی‌ شده (colorized) می‌تواند یک رشته تصادفی از بایت‌ها باشد (به عنوان مثال «QYISLKFYDBYYSYWSIBSXEAXOKHNRUCYU»). در اجرای مجدد، همان دستور مقایسه جهشی به شکل <QYISLKFY 7 → MAGICHDR> تولید می‌کند که فقط در اولین موقعیت قابل اعمال است. در نتیجه، تنها یک کاندید در موقعیت صفر (position 0) تولید می‌شود.

6) رشته‌ها و حافظه (Strings and Memory). علاوه بر مقایسه‌های عددی که پیش‌تر ذکر شد، برنامه‌ها اغلب از توابعی برای مقایسه دو رشته (string) یا محتوای آرایه‌های بایتی (byte arrays) استفاده می‌کنند. این نوع بررسی‌ها نیز معمولاً چالش‌های قابل‌توجهی برای فازرها ایجاد می‌کنند. برای مقابله با چنین سازه‌هایی، ما تمام فراخوانی‌های تابع (function calls) را نیز هوک (hook) می‌کنیم. چنانچه تابع حداقل دو آرگومان از نوع اشاره‌گر (pointer) داشته باشد، ما ۱۲۸ بایت ابتدایی که این اشاره‌گرها به آن‌ها اشاره می‌کنند را استخراج کرده و مشابه با مقادیر عددی با آن‌ها رفتار می‌کنیم. با این حال، برای محتوای حافظه از مجموعه کدگذاری‌های متفاوتی نسبت به اعداد استفاده می‌کنیم. به‌طور خاص، یا فرض می‌کنیم که فقط n بایت اول (با n ∈ {4, 5, …, 32}) مقایسه می‌شوند (مشابه توابعی مانند memcmp)، یا تمام بایت‌ها تا رسیدن به اولین بایت صفر (null byte) در نظر گرفته می‌شوند (مشابه توابع خانواده strcmp).

7) فرهنگ لغت وابسته به ورودی (Input-Specific Dictionary). در نهایت، مقادیری که شامل دنباله‌های طولانی از بایت‌های غیرصفر یا غیر 0xff هستند را به یک دیکشنری اختصاصی اضافه می‌کنیم. رشته‌هایی که به این روش استخراج می‌شوند، فقط در مرحله havoc برای همان ورودی فعلی مورد استفاده قرار می‌گیرند. این کار به ما اجازه می‌دهد از مقادیری استفاده کنیم که به توابعی پاس داده می‌شوند که رفتار داخلی آن‌ها مشابه عملیات مقایسه است، اما از الگوریتم‌های غیرساده‌تری مانند جست‌وجو در جدول هش (hashtable lookup) استفاده می‌کنند.

به‌نوعی، این روش نسخه‌ای قدرتمندتر از ترفند شناخته ‌شده استخراج خروجی ابزار strings و استفاده از آن به‌ عنوان دیکشنری در فازینگ است؛ با این تفاوت که ما رشته‌های محاسبه ‌شده در زمان اجرا (dynamically computed strings) را نیز در نظر می‌گیریم، اما رشته‌هایی که در مسیر فعلی برنامه مرتبط نیستند را وارد دیکشنری نمی‌کنیم.

3.2 جمع‌آزماها (Checksums)

یکی دیگر از چالش‌های رایج برای فازرها، عبور کارآمد از بررسی‌های جمع‌آزماها (checksum checks) است. یک نمونه‌ی معمول از این چالش در لیست ۳ نشان داده شده است که باز هم بخشی از مثال جاری ما است که در لیست ۱ معرفی شده بود.

لیست ۳: مشکل فازینگ (۲): یافتن ورودی معتبر برای دور زدن جمع‌آزماها (checksum):

				
					if ( u64 ( input ) == sum ( input +8 , len -8) )
	if ( u64 ( input +8) == sum ( input +16 , len -16) )
		if ( input [16]== ’R ’ && input [17]== ’Q ’)
			bug (2) ;

رویکردهای موجود مانندFLAYER [18] ، TAINTSCOPE [40] و T-FUZZ [34] همگی بر یک ایده مشترک تکیه دارند و آن هم حذف بررسی‌های سخت (hard checks) و اصلاح آن‌ها در مرحله بعد. در این میان، TAINTSCOPE و T-FUZZ هر دو به‌ صورت خودکار بررسی‌های بحرانی (critical checks) را شناسایی می‌کنند و سپس، پس از کشف رفتارهای جالب، از اجرای نمادین (symbolic execution) برای اصلاح این بررسی‌ها استفاده می‌کنند.

ما پیشنهاد می‌کنیم که ردگیری آلودگی (taint tracking) و اجرای نمادین (symbolic execution) مورد استفاده در TAINTSCOPE و T-FUZZ را با یک فرآیند مبتنی بر تناظر ورودی با وضعیت (input-to-state correspondence) جایگزین کنیم:

ابتدا، مقایسه‌هایی را شناسایی می‌کنیم که به نظر می‌رسد مشابه بررسی‌های جمع‌آزما (Checksum) هستند (برای مثال، یک طرف مقایسه مقداری است که با ورودی متناظر است و طرف دیگر به ‌صورت منظم تغییر می‌کند). سپس، این بررسی را با یک مقایسه جایگزین می‌کنیم که همیشه مقدار true بازمی‌گرداند (یعنی شرط را عملاً بی‌اثر می‌کنیم).

پس از آن‌که فرآیند فازینگ روی این برنامه وصله (patch) ‌شده یک مسیر ظاهراً جالب (interesting path) تولید کرد، وارد حالت اعتبارسنجی (validation mode) می‌شویم. در این حالت، از تکنیک‌های توضیح‌ داده‌ شده در بخش قبلی استفاده می‌کنیم تا تمام مقایسه‌های وصله شده را اصلاح کنیم.

چنانچه این کار موفقیت‌آمیز باشد، فرآیند را مانند قبل ادامه می‌دهیم؛ در غیر این صورت، نتیجه می‌گیریم که یکی از این مقایسه‌ها تحت کنترل ما نیست. در این حالت، وصله مربوط به آن دستور را حذف می‌کنیم تا از انجام مراحل اعتبارسنجی غیرضروری در آینده جلوگیری شود.

بر اساس ایده تناظر ورودی با وضعیت (input-to-state correspondence)، ما قادر هستیم به‌صورت خودکار تعیین کنیم که کدام دستورها باید وصله شوند. علاوه بر این، می‌توانیم ورودی‌ها را نیز به ‌طور خودکار بدون نیاز به مداخله انسانی یا استفاده از روش‌های پیچیده‌ای مانند ردگیری آلودگی (taint tracking) و اجرای نمادین (symbolic execution) اصلاح کنیم.

در طول فازینگ مبتنی بر بازخورد (feedback fuzzing)، هر ورودی جدیدی که کشف می‌شود را همان‌جا اصلاح (fix) می‌کنیم (برخلاف TAINTSCOPE و T-FUZZ). این کار تضمین می‌کند که هیچ مثبت کاذبی (false positive) در صف (queue) ذخیره نشود. یک مزیت اضافی این رویکرد این است که امکان اشتراک‌گذاری صف ورودی‌ها با ابزارهای دیگر را فراهم می‌کند.

در ادامه، جزئیات فرآیند انتخاب (selection)، وصله کردن (patching) و اعتبارسنجی (validation) بررسی‌های مشکوک به جمع‌آزما (Checksum) را با تمرکز بر هش‌ها (hashes) و محاسبات مشابه آن‌ها بررسی می‌کنیم.

(1) شناسایی (Identification). اولین مرحله در حین پردازش بایت‌های جادویی (مطابق بخش3.1) انجام می‌شود. خروجی این مرحله، فهرستی از دستورهای مقایسه و مقادیر مقایسه ‌شده در تمام نسخه‌های رنگی شده مختلف از ورودی است. ما از ابتکارها و اکتشاف‌های زیر برای فیلتر کردن دستورهای مقایسه و انتخاب کاندیدهای مناسب برای وصله کردن جمع‌آزما استفاده می‌کنیم:

۱) ما می‌توانیم سمت چپ الگوی جهش (mutation pattern) خود را در تمام ورودی‌ها با استفاده از یک کدگذاری یکسان پیدا کنیم.

۲) هیچ‌ یک از دو آرگومان دارای مقدار ثابت (immediate value) نباشند.

۳) الگو (pattern) در طول مرحله رنگی سازی تغییر کند (مشابه محدودیتی که TAINTSCOPE استفاده می‌کند: یعنی مقدار به تعداد زیادی از بایت‌های ورودی وابسته باشد).

شهود (intuition) پشت این بررسی‌ها به این صورت است: ما مشاهده کرده‌ایم که یک دستور، جهشی از نوع <pattern 7 → repl> تولید می‌کند. فرض کنید pattern یک فیلد از ورودی باشد و repl مقدار هشی (hash) باشد که روی بخشی از ورودی محاسبه شده است.

در یک مقایسه جمع‌آزما (checksum comparison)، سمت چپ باید همیشه بخشی از ورودی باشد. همچنین، اگر در مرحله رنگ آمیزی (colorization) بخش‌های بزرگی از ورودی را با مقادیر تصادفی جایگزین کنیم، مقدار هش نیز تغییر خواهد کرد (و در نتیجه مقدار repl هم تغییر می‌کند).

به‌ طور مشابه، چنانچه طرح یا الگو (pattern) مقداری از ورودی باشد و repl مقدار هشی (hash) باشد که روی بخشی از ورودی محاسبه شده است، هیچ‌یک از دو آرگومان نباید دارای مقدار ثابت (immediate value) باشند.

بدیهی است که این یک تقریب بیش ‌از حد (over-approximation) است و در برخی موارد ممکن است بررسی‌هایی را شناسایی کنیم که در واقع بخشی از یک جمع‌آزما (checksum) واقعی نیستند. بنابراین، این رویکرد یک نقطه ‌ضعف مهم دارد: دستورهایی که وصله (patch) می‌شوند ممکن است در واقع بررسی‌های مرزی (bounds checks) مهمی باشند و حذف آن‌ها می‌تواند منجر به مثبت‌های کاذب (false positives) (یعنی پوشش کد اشتباه) یا حتی باعث کرش (Crash) برنامه در مراحل بعدی گردد.

به همین دلیل، ما یک مرحله اعتبارسنجی (validation phase) معرفی می‌کنیم تا مثبت‌های کاذب احتمالی را حذف کرده و دستورهای مقایسه‌ای را که نباید وصله (patch) شوند شناسایی کنیم. پس از آن که فازر یک ورودی جدید پیدا می‌کند و پیش از آن‌که آن را در صف (queue) ذخیره کنیم، تلاش می‌کنیم تمام دستورهای مقایسه وصله شده را اصلاح کنیم. چنانچه وصله‌ای پیدا کنیم که فازر قادر به اصلاح خودکار آن نباشد، بلافاصله آن وصله را حذف می‌کنیم. همچنین، آن ورودی را قبل از ورود به صف کنار می‌گذاریم. این کار تضمین می‌کند که زمانی را صرف وصله‌هایی که به‌راحتی قابل اصلاح نیستند هدر ندهیم و هیچ مثبت کاذبی تولید نشود. زیرا هر ورودی در نهایت با نسخه اصلی و بدون تغییر فایل اجرایی اصلاح نشده (unmodified executable) اعتبارسنجی می‌شود.

(۲) وصله کردن (Patching). پس از آن ‌که مجموعه‌ای از بررسی‌های هش (hash checks) مشکوک را شناسایی کردیم، این دستورها را با وصله‌هایی جایگزین می‌کنیم که همان اثرات جانبی یک مقایسه موفق را دارند. بدیهی است که این کار می‌تواند منجر به رفتارهای نامطلوب شود؛ برای مثال ممکن است به‌ طور ناخواسته بررسی‌های مرزی (bounds checks) را حذف کنیم یا مسیرهایی را قابل دسترسی کنیم که بدون این وصله‌ها هرگز قابل دستیابی نبودند. با این حال، ما فازینگ را روی این باینری وصله شده ادامه می‌دهیم، زیرا این مشکلات را در مراحل بعدی اصلاح خواهیم کرد.

(۳) اعتبارسنجی (Verification). پس از اجرای تمام مراحل فازینگ روی یک ورودی، ما یک صف از نتایج اولیه (preliminary results) داریم. به دلیل وصله‌هایی که اعمال کرده‌ایم، این ورودی‌ها ممکن است روی هدف اصلی (بدون وصله) رفتار مورد انتظار را نشان ندهند. در مرحله اعتبارسنجی، تلاش می‌کنیم این ورودی‌های نامعتبر را با استفاده از جهش‌های مبتنی بر تناظر ورودی با وضعیت (input-to-state) که از دستورهای وصله شده به‌دست آمده‌اند، اصلاح کنیم. سپس، ورودی‌های اصلاح‌ شده را روی هدف واقعی و بدون وصله اجرا می‌کنیم. اگر همچنان باعث تولید پوشش جدید (new coverage) شوند، ورودی اصلاح‌ شده وارد صف اصلی (real queue) می‌شود. در غیر این صورت، آن وصله کنار گذاشته می‌شود. پس از پردازش همه ورودی‌های اولیه به این روش، صف اولیه برای دور بعدی خالی می‌شود.

4. جزئیات پیاده‌سازی (IMPLEMENTATION DETAILS)

در ادامه، یک مرور کوتاه از REDQUEEN ارائه می‌دهیم؛ این ابزار، پیاده‌سازی اثبات مفهوم (proof-of-concept) از رویکرد ما است. ما پیاده‌سازی REDQUEEN را بر اساس فازر خود یعنی KAFL [37] انجام داده‌ایم.

4.1 فازر KAFL (kAFL Fuzzer)

KAFL یک فازر مبتنی بر بازخورد (feedback-driven) و الهام‌گرفته از AFL است که مستقل از سیستم‌عامل (OS-agnostic) بوده و برای فازینگ کرنل طراحی شده است. این ابزار از قابلیت ردیابی سخت‌افزاری Intel Processor Trace (Intel PT) استفاده می‌کند تا اطلاعات پوشش کد (coverage) را بدون نیاز به ابزارگذاری (instrumentation) در هدف به‌دست آورد.

KAFL بر پایه نسخه‌های اصلاح‌شده‌ای از KVM و QEMU (با نام‌های KVM-PT و QEMU-PT) ساخته شده است تا بتواند سیستم‌عامل‌های x86 دلخواه را به‌صورت ایزوله اجرا کند. به این ترتیب، فازر می‌تواند از قابلیت‌های مجازی‌سازی مانند اجرای شتاب‌یافته سخت‌افزاری اسنپ شات‌های (snapshot) کد و همچنین ردیابی Intel PT در کد مهمان (guest’s code) بهره ببرد.

در این معماری، KVM-PT امکان ردیابی Intel PT در سیستم مهمان (guest) را فراهم می‌کند و QEMU-PT نیزخروجی و آثار (trace) تولید شده را به یک bitmap سازگار با AFL تبدیل می‌کند. برای انجام این کار، QEMU-PT یک دیس اسمبلی زمان‌اجرای (runtime disassembly) از هدف را نگه می‌دارد.

این دیس اسمبلی (disassembly) از این جهت «کامل و بی نقص» است که ما هر دستورالعملی را که طبق ردیابی Intel PT اجرا شده باشد، به‌صورت دقیق دیس اسمبلی می‌کنیم. از این دیس اسمبلی برای شناسایی دستورهایی که باید هوک (hook) یا وصله (patch) شوند استفاده می‌کنیم.

این رویکرد از مشکلاتی جلوگیری می‌کند که هنگام وصله کردن کد بر اساس یک دیس اسمبلی ایستا (static disassembly) به‌وجود می‌آید؛ زیرا دیس اسمبلی ایستا ممکن است برخی بایت‌ها را به‌اشتباه طبقه‌بندی کند. هر دو مؤلفه QEMU-PT و KVM-PT همچنین قابلیت‌هایی مانند hypercalls سفارشی و دسترسی مستقیم به حافظه مهمان (guest memory) را فراهم می‌کنند تا ارتباط و انتقال داده‌های لازم با هدف (target) ساده‌تر شود.

منطق فازر بر پایه حلقه فازینگ AFL (به‌ همراه یک مرحله اضافه از radamsa [29]) است و به زبان پایتون بازپیاده‌سازی شده است. بنابراین منطق فازینگ مستقل از سیستم‌عامل هدف است.

ما همچنین تعدادی از اشکالات موجود در رمزگشایی (decoding) بسته‌های Intel PT را برطرف کردیم که مقدار قابل توجهی از عدم قطعیت (non-determinism) ناشی از ردیابی‌های ناقص را حذف می‌کرد.

در مجموع حدود ۱۰ هزار خط کد اضافه یا تغییر داده شده است. بخش بزرگی از این تغییرات مربوط به تکنیک‌های پیشنهادی این مقاله نیست؛ بلکه بیشتر برای افزودن پشتیبانی از فازینگ در حلقه ۳، فراهم کردن قابلیت‌های VMI (Virtual Machine Introspection) در KAFL و رفع باگ‌ها (Bug) انجام شده است. علاوه بر این، بخشی از این کد نیز برای اهداف ارزیابی و دیباگ استفاده شده است.

تکنیک‌های ما به چند مؤلفه پایه‌ای (primitive) نیاز دارند: امکان ردیابی برنامه، امکان بررسی وضعیت برنامه در نقاط توقف (breakpoints) مختلف ، و امکان وصله کردن دستورها در حافظه.

REDQUEEN همچنان از معماری KAFL استفاده می‌کند و اطلاعات پوشش (coverage) را دقیقاً به همان شیوه دریافت می‌کند. علاوه بر این، از قابلیت VMI (Virtual Machine Introspection) که توسط KVM-PT و QEMU-PT فراهم شده است استفاده می‌کند تا در زمان اجرا نقاط توقف (breakpoints) قرار دهد و محتوای حافظه و ثبات‌ها (register) را بررسی کند. در ادامه، توضیح می‌دهیم که چگونه تکنیک‌های خود را بر روی KAFL پیاده‌سازی کرده‌ایم.

4.2 هوک‌ مقایسه‌ها (Comparison Hooking)

ما برای استخراج تناظر ورودی با وضعیت (input-to-state correspondences) به نقاط توقف در ماشین مجازی که با سخت‌افزار پشتیبانی می‌شوند (hardware-assisted VM breakpoints) تکیه می‌کنیم. هر بار که دیساسمبلر (runtime disassembler) به یک دستور «شبه مقایسه» (compare-like) برخورد می‌کند، آدرس آن را ذخیره می‌کند تا در مرحله تحلیل بعدی REDQUEEN بتواند روی آن یک هوک (hook) قرار دهد.

در مرحله REDQUEEN، نقاط توقف (breakpoints) روی تمام دستورهای مهم قرار داده می‌شوند. زمانی که یک نقاط شکست فعال (hit) می‌شود، آرگومان‌های آن استخراج شده و برای استفاده در منطق فازینگ در یک بافر ذخیره می‌شوند. برای محدود کردن اثرات منفی بر عملکرد، نقاط شکست پس از چند بار فعال شدن حذف می‌شوند.

نکته مهم این است که ما فقط دستورهای cmp را هوک (hook) نمی‌کنیم، بلکه دستورهای فراخوانی (call) و تفاضل (subtraction) را نیز شامل می‌شویم. دستورهای فراخوانی (call) برای شناسایی مقایسه‌های رشته‌ای و حافظه‌ای استفاده می‌شوند، در حالی که تفریق‌ها اغلب توسط کامپایلرها به‌جای دستور cmp برای پیاده‌سازی جدول‌های switch تولید می‌شوند.

برای پیاده‌سازی تفریق، کامپایلر گاهی دستورهای خاصی مانند lea یا add با آفست (offset) منفی تولید می‌کند. اگر دو آرگومان اول یک دستور call (طبق قراردادهای فراخوانی مختلف) اشاره‌گرهای معتبر (valid pointers) باشند، فرض می‌کنیم تابع موردنظر یک تابع مقایسه‌ای بالقوه است و ۱۲۸ بایت ابتدایی حافظه مربوط به هر آرگومان را استخراج می‌کنیم.

4.3 رنگی‌سازی (Colorization)

در مرحله رنگی‌سازی (colorization)، تلاش می‌کنیم تا حد امکان بایت‌های ورودی را با مقادیر تصادفی جایگزین کنیم، بدون آن‌که مسیر اجرای برنامه (یا به‌طور دقیق‌تر، هش bitmap مربوط به AFL) تغییر کند.

این کار باعث افزایش آنتروپی (entropy – یا بی نظمی، تصادفی‌سازی) در ورودی می‌شود و در نتیجه تعداد موقعیت‌هایی را که یک الگوی مشاهده ‌شده می‌تواند در آن‌ها اعمال شود کاهش می‌دهد.

این فرآیند می‌تواند همان‌طور که در الگوریتم ۱ نشان داده شده است با استفاده از رویکرد جست‌وجوی باینری یا دودویی (binary search) انجام شود. این روش معمولاً در تعداد کمی اجرا (معمولاً در حد چند صد اجرا) همگرا می‌شود.

بدترین حالت آن قابل مقایسه با یک‌هشتم تعداد تغییر و بازگردانی بیت‌هایی (bit-flip) است که AFL روی هر ورودی انجام می‌دهد. علاوه بر این، در پیاده‌سازی ما، تعداد مراحل جست‌وجو به حداکثر ۱۰۰۰ گام محدود شده است. این روش حتی برای اهدافی مانند درایورهای سیستم فایل نیز به ‌خوبی عمل کرده است؛ حتی در شرایطی که حداقل اندازه ورودی ۶۴ کیلوبایت بوده است.

الگوریتم ۱: الگوریتمی برای رنگ‌آمیزی ورودی‌ها برای مدیریت کارآمد تعداد زیادی از موقعیت‌های کاندید:

4.4 پچ‌کردن دستورها (Instruction Patching)

پس از آن‌که منطق فازینگ، بر اساس داده‌های تناظر ورودی با وضعیت (input-to-state correspondence)، فهرستی از دستورهای مقایسه‌ی مشکوک به هش را تولید کرد، ما این دستورات را با دستورالعمل‌های مقایسه‌ی جعلی (bogus compare instructions) جایگزین می‌کنیم که همیشه مقدار true بازمی‌گردانند. در پیاده‌سازی ما، از دستور cmp al, al استفاده می‌کنیم، زیرا کوچک‌ترین دستور مقایسه در معماری x86 است. بایت‌های باقی‌مانده از دستور اصلی نیز با دستورهای NOP پر می‌شوند.

ما از امکانات دیباگ در KVM و QEMU برای اعمال این وصله‌ها در حافظه داخل ماشین مجازی استفاده می‌کنیم. سپس فرآیند معمول فازینگ روی ماشین مجازی وصله شده ادامه می‌یابد. با این حال، چنانچه وصله‌ها فعال باشند، مسیرهای جدیدی که پیدا می‌شوند بلافاصله به صف (queue) اضافه نمی‌شوند.

گاهی حتی کدهای C ساده و کامپایلرهای رایج، اسمبلی تولید می‌کنند که به میان دستورها پرش می‌کند. در این موارد، این رفتار می‌تواند از طریق دیس ‌اسمبلی زمان اجرا با Intel PT تشخیص داده شود. در برخی موارد دیگر، تکنیک‌هایی مانند تفسیر چندگانه دستورالعمل‌ها (instruction punning) [15] یا حتی نقاط توقف ساده می‌توانند برای جلوگیری از کرش‌های غیرمنتظره استفاده شوند. با این حال، باید توجه داشت که ما حتی در برنامه‌های هدف نسبتاً بزرگ نیز چنین رفتاری مشاهده نکردیم، زیرا تعداد دستورهای وصله شده کم بودند (معمولاً کمتر از ۵ مورد در ارزیابی تجربی ما).

4.5 اعتبارسنجی و اصلاح ورودی (Input Validation and Fixing)

ما از الگوریتم ۲ برای بررسی و اصلاح نتایج اولیه استفاده می‌کنیم. این الگوریتم به‌صورت تکراری تلاش می‌کند تا تمام مقایسه‌ها را با اعمال مکرر جهش‌های منفرد (individual mutations) و مشاهده‌ی تناظر ورودی با وضعیت (input-to-state correspondences) حاصل، اصلاح کند.

توجه داشته باشید که در برخی موارد، بین مقایسه‌ها یک ترتیب وابستگی وجود دارد که هنگام اصلاح ورودی باید حفظ شود. این وضعیت معمولاً زمانی رخ می‌دهد که هدر (header) یک فرمت فایل شامل یک جمع‌آزما (checksum) روی کل محتوای فایل باشد و در عین حال، برخی بخش‌های داخلی فایل نیز با جمع‌آزماهای (checksum) جداگانه محافظت شده باشند.

برای مثال، محتوای بخش IDAT در فایل‌های PNG با یک جمع‌آزمای CRC-32 محافظت می‌شود. اگر این محتوا به‌ صورت فشرده‌ شده با zlib باشد، یک جمع‌آزمای دیگر از نوع ADLER-32 نیز روی آن اعمال می‌شود. در چنین شرایطی، باید ابتدا جمع‌آزمای داخلی (inner checksum) را اصلاح کنیم تا جمع‌آزمای خارجی (outer checksum) بتواند به‌ درستی محاسبه شود.

ترتیب انجام این جمع‌آزماها واضح نیست. با این حال، معمولاً جمع‌آزمای خارجی (outer checksum) ابتدا بررسی می‌شود. بنابراین، ما تلاش می‌کنیم برای کاهش کار اضافی، ابتدا آخرین مقایسه را اصلاح کنیم. در آزمایش‌های ما، این رویکرد ساده کافی بوده است. با این حال، به‌طور کلی نمی‌توان چنین فرضی را همواره صحیح دانست.

در حین انجام مجموعه‌ای از اجرای آزمایشی برای اصلاح همه جمع‌آزماهای به ترتیب معکوس وقوع آن‌ها، مشاهده می‌کنیم که هر جهش (mutation) بر کدام دستورهای مقایسه تأثیر می‌گذارد. به این ترتیب، یک گراف وابستگی (dependency graph) از دستورهای وصله شده (patch) ایجاد می‌کنیم.

اگر ورودی حاصل از مرحله اول همچنان معتبر نباشد، از این گراف وابستگی برای انجام یک مرتب‌سازی توپولوژیک (topological sort) روی وصله‌ها استفاده می‌کنیم تا ترتیب صحیح آن‌ها به دست آید. این کار به ما اجازه می‌دهد تا دور دیگری از اصلاحات را به ترتیب مورد نیاز روی ورودی اعمال کنیم. اگر ورودی نهایی رفتار مورد انتظار را روی فایل اجرایی اصلاح نشده نشان ندهد، وصله‌های نامناسب را حذف کرده و ورودی را از صف اولیه دور می‌اندازیم.

الگوریتم ۲: الگوریتمی برای تثبیت ورودی‌های اولیه

روال get_broken_cmps که در الگوریتم ۲ استفاده شده است، فهرستی از تمام دستورالعمل‌های مقایسه‌‌ای وصله شده را که در حال حاضر برقرار نشده‌اند (not satisfied)، به‌ همراه مقادیری که در حال مقایسه شدن هستند، بازمی‌گرداند.

روال try_fix_value_for_patch تلاش می‌کند تمام جهش‌هایی را که از دستور وصله شده حاصل شده‌اند، مطابق آنچه در بخش 3.1 توضیح داده شد، اعمال کند. سپس بررسی می‌کند که آیا هیچ‌یک از این جهش‌ها توانسته‌اند آن مقایسه را برطرف (fix) کنند یا خیر. اگر چنین ورودی‌ پیدا شود، همان ورودی بازگردانده می‌شود. در غیر این صورت، نتیجه می‌گیریم که این دستور مقایسه با روش ما قابل برآورده سازی نیست. در این حالت، آن وصله از لیست وصله‌های مورد استفاده در اجراهای بعدی فازینگ حذف می‌شود.

روال get_cmps_influenced نیز تمام دستورهای مقایسه‌ای را پیدا می‌کند که آرگومان‌های آن‌ها تحت تأثیر آخرین اصلاح اعمال ‌شده روی ورودی قرار گرفته‌اند. این کار به ما اجازه می‌دهد ترتیب دستورات مقایسه را که بعداً در صورت نیاز استفاده می‌کنیم، استخراج و بازسازی نماییم.

مثال ۶. باگ ۲ از مثال جاری (نشان‌ داده‌ شده در لیست ۱) را در نظر بگیرید. پس از حذف دو بررسی جمع‌آزما (checksum)، فازر، ورودی اولیه «01234567abcdefghRQ » را پیدا می‌کند. ردگیری نیز نتایج زیر را تولید می‌کند:

				
					p1 := <01234567 7 → \xc7\x03\0\0\0\0\0\0>  و p2 := <abcdefgh 7 → \xa3\0\0\0\0\0\0\0>

اگر هر دو جهش را به‌ طور هم‌زمان اعمال کنیم، جهش دوم باعث می‌شود مجموعِ مربوط به جهش اول نامعتبر شود. بنابراین، ابتدا سعی می‌کنیم وصله دوم (p2) را اصلاح کنیم و در عین حال توجه داریم که p1 تحت تأثیر قرار می‌گیرد. پس از اصلاح p2، ورودی زیر به‌دست می‌آید:

				
					“01234567\xa3\0\0\0\0\0\0\0RQ”

با تغییر جمع‌آزمای داخلی (inner checksum) ورودی، مقدار مورد انتظار برای p1 هم تغییر می‌کند. در نتیجه، جهش جدید برای p1 به این صورت می‌شود:

				
					<01234567 7 → \x46\x01\0\0\0\0\0\0>

سپس وصله اول (p1) را اعمال می‌کنیم. این بار، این کار باعث اختلال در سایر وصله‌ها نمی‌شود. ورودی نهایی به این شکل است:

				
					\x46\x01\0\0\0\0\0\0\xa3\0\0\0\0\0\0\0RQ

از آن‌جا که همه قیود وصله شده توسط این ورودی برقرار شده‌اند، یک اجرای نهایی بدون وصله انجام می‌دهیم تا مطمئن شویم رفتار برنامه مطابق انتظار است. این ورودی واقعاً باگ ۲ را فعال می‌کند و از صف اولیه و مقدماتی (preliminary queue) به صف اصلی و واقعی (real queue) منتقل می‌شود. در این مثال، نیازی به استفاده از مرتب‌سازی توپولوژیک (topological sort) برای تعیین ترتیب بررسی‌ها نبود، چون به‌ طور تجربی یک ترتیب صحیح برای اعمال وصله‌ها انتخاب کردیم.

4.6 لودر برنامه فضای کاربری لینوکس برای KAFL (Linux User Space Application Loader for KAFL)

ما KAFL را با افزودن یک لودر برای برنامه‌های سطح کاربر (حلقه ۳) در لینوکس گسترش دادیم تا بتوانیم آن را با سایر فازرهای user-space مقایسه کنیم و نشان دهیم که رویکرد ما عمومی (generic) و مقاوم (robust) است.

این لودر، سرور فورک (fork server) مربوط به AFL را دوباره پیاده‌سازی می‌کند. از آن‌جا که هدف ما باینری‌ها هستند، از LD_PRELOAD استفاده می‌کنیم تا قابلیت fork server را به روال آغازین (start-up routine) برنامه هدف تزریق کنیم. ارتباط با منطق فازینگ از طریق hypercalls سفارشی KAFL انجام می‌شود که توسط همین کد تزریق‌ شده در ابتدای اجرا فراخوانی می‌شوند.

برای پشتیبانی از ردیابی در حلقه ۳ (ring 3) در KVM-PT، بیت User را در رجیستر خاص پردازنده (IA32_RTIT_CTL MSR) تنظیم می‌کنیم. نسخه اصلی KAFL که به ‌عنوان فازر کرنل طراحی شده بود، فقط بیت OS در همین رجیستر را فعال می‌کرد تا ردیابی در ring 0 انجام شود.

علاوه بر این، نسخه اولیه KAFL فقط برای سیستم‌های ۶۴ بیتی طراحی شده بود. اما از آن‌جا که برخی از باینری‌های CGC فقط برای معماری ۳۲ بیتی قابل کامپایل هستند، ما فازر را برای پشتیبانی از اهداف ۳۲ بیتی نیز گسترش دادیم. به همین منظور، قابلیت دیس‌اسمبلی حالت ۳۲ بیتی را به QEMU-PT اضافه کردیم تا بتواند داده‌های ردگیری (trace) مربوط به Intel PT در حالت ۳۲ بیتی را نیز رمزگشایی (decode) کند.

5. ارزیابی (EVALUATION)

ما پیاده‌سازی نمونه اولیه REDQUEEN را همانطور که در بالا توضیح داده شد، ارزیابی کردیم تا به پرسش‌های پژوهشی زیر پاسخ دهیم:

پرسش پژوهشی ۱. آیا تکنیک‌های مبتنی بر تناظر ورودی با وضعیت به اندازه کافی عمومی هستند که در مجموعه‌ای متنوع از اهداف و محیط‌ها کار کنند؟
پرسش پژوهشی ۲. نتایج تکنیک‌های مبتنی بر تناظر ورودی با وضعیت ما چگونه با سایر تکنیک‌های پیچیده‌تر مانند رویکردهای مبتنی بر ردیابی اثر انگشت یا اجرای نمادین مقایسه می‌شود؟
پرسش پژوهشی ۳. تکنیک‌های مبتنی بر تناظر ورودی با وضعیت ما چه پیشرفت‌هایی را در سناریوهای فازینگ دنیای واقعی ارائه می‌دهند؟

برای پاسخ به این پرسش‌ها، ارزیابی ما به سه بخش تقسیم شده است:

ما در بخش اول، یک ارزیابی مقایسه‌ای را روی دو مجموعه آزمون ساختگی (synthetic test) برای (LAVA-M و CGC) و یک مجموعه واقعی (GNU binutils) انجام می‌دهیم. نتایج نشان می‌دهد که ترکیب روش‌های ما با اختلاف قابل‌توجهی از سایر رویکردهای موجود بهتر عمل می‌کند. در بخش دوم، نشان می‌دهیم که ابزار ما قادر است باگ‌های جدیدی را در نرم‌افزارهای مختلف و به‌خوبی تست‌ شده، در محیط‌های بسیار متفاوت، شناسایی کند. در مجموع، ۱۰ باگ در ۲ درایورهای سیستم فایل لینوکس (Linux file system drivers) و ۵۵ باگ در ۱۶ برنامه user-space و کتابخانه نرم‌افزاری (user-space programs and software libraries) کشف شده‌اند. تاکنون برای این آسیب‌پذیری‌ها ۱۶ CVE اختصاص داده شده و ۴ مورد دیگر هنوز در حال بررسی هستند.

در نهایت، در بخش سوم، کارایی (efficiency) و اثربخشی (effectiveness) روش خود را در مقایسه با سایر جهش‌هایی که توسط KAFL انجام می‌شوند اندازه‌گیری می‌کنیم. همچنین تأثیر هر یک از تکنیک‌های معرفی ‌شده در این مقاله را به ‌صورت جداگانه بررسی می‌کنیم. این کار از طریق یک مطالعه موردی (case study) بر روی یک کتابخانه کوچک PNG که به‌ صورت ایستا (static) لینک شده است انجام می‌شود، زیرا این فرمت فایل دارای جمع‌آزماهای تو در تو (nested checksums) است. نتایج نشان می‌دهد که رویکرد ما می‌تواند موانع رایج فازینگ را که قبلاً نیازمند استفاده از فرهنگ لغت‌ها (dictionary) یا حذف دستی بررسی‌های هش (Hash) بودند، به‌صورت خودکار پشت سر بگذارد.

5.1 روش‌های ارزیابی (Evaluation Methods)

تمام آزمایش‌ها روی سیستم‌هایی با اوبونتو سرور16.04.2 LTS و پردازنده Intel i7-6700 (چهار هسته‌ای) و ۲۴ گیگابایت رم (RAM) انجام شده‌اند. ما همه ابزارها را طوری پیکربندی کردیم که فقط از یک فرایند فازینگ (fuzzing process) استفاده کنند تا قابلیت مقایسه با ابزارهایی مانند VUZZER که چندنخی (multi-thread) نیستند، حفظ شود. هیچ‌یک از آزمایش‌ها شامل تغییرات اختصاصی برای اهداف خاص نبوده‌اند.

مگر در مواردی که به ‌طور مشخص ذکر شده باشد، از یک بذر (seed) بدون دانش قبلی (uninformed) و عمومی استفاده کردیم که شامل کاراکترهای مختلف از مجموعه ASCII قابل چاپ است:

				
					"ABC. . . XYZabc. . . xyz012. . . 789!¨$. . . ˜+*"

از آن‌جا که تعریف‌های مختلفی برای بلوک پایه (basic block) وجود دارد و ابزارهایی مانند LAF-INTEL به ‌طور قابل توجهی تعداد بلوک‌های پایه را در یک باینری تغییر می‌دهند، ما همواره پوشش (coverage) تولید شده توسط هر فازر را روی همان باینری بدون ابزارگذاری (instrumentation)‌ اندازه‌گیری می‌کنیم.

به همین دلیل، تعداد بلوک‌های پایه کشف‌ شده ممکن است با اعدادی که در مقالات دیگر گزارش شده‌اند مطابقت نداشته باشد، اما در داخل آزمایش‌های ما کاملاً قابل مقایسه و سازگار است. تمام آزمایش‌ها چندین بار اجرا شده‌اند. در هر مورد، ما میانه (median) تعداد بلوک‌های پایه کشف ‌شده در هر زمان و همچنین بازه‌های اطمینان ۶۰٪ را گزارش می‌کنیم.

در سال‌های اخیر تمرکز زیادی روی کشف باگ‌های «عمیق» (deep bugs) انجام شده است. با اینکه تعریف دقیق «عمیق بودن» هنوز کاملاً مشخص نیست، ما به‌ صورت عملی آن را این‌گونه تعریف می‌کنیم: یک باگ، زمانی «عمیق» در نظر گرفته می‌شود که از دسترسی به آن از طریق بذرهای ورودی (seed input) داده شده دشوار باشد. بنابراین، ما توانایی کشف پوشش کد جدید را به‌ عنوان یک تقریب مناسب برای توانایی یافتن باگ‌های «عمیق» در نظر می‌گیریم، ویژگی که سنجش مستقیم آن بسیار دشوارتر است.

در نهایت، از آن‌جا که اصطلاحات در پژوهش‌های مرتبط متفاوت است، ما از واژه‌ «کرش (crash)» برای توصیف هر ورودی‌ استفاده می‌کنیم که باعث توقف ناگهانی یا کرش کردن (crash) برنامه هدف شود.

ما هیچ‌گاه از تعداد «کرش‌های یکتا (unique crashes)» صحبت نمی‌کنیم، زیرا این معیار بسیار غیرقابل اعتماد است؛ چرا که ابزارهای مختلف، تعداد کرش‌ها را به شکل‌های کاملاً متفاوت و اغلب بیش‌برآورد شده گزارش می‌کنند. در عوض، از عبارت «توانستیم برنامه را دچار کرش کنیم» استفاده می‌کنیم تا نشان دهیم حداقل یک کرش بدون انجام دسته‌بندی (triage) بیشتر رخ داده است.

اصطلاح باگ (bug) را برای آسیب‌پذیری‌هایی به‌کار می‌بریم که به‌صورت دستی بررسی، تایید (manual verification) و دسته‌بندی (triage) شده‌اند و دارای علل ریشه‌ای متفاوت (disjoint root causes) در برنامه هستند. یک باگ لزوماً قابل بهره‌برداری (exploitable) نیست. در نهایت، در برخی موارد شماره‌های CVE نیز دریافت کرده‌ایم که آن‌ها را به ‌صورت جداگانه شمارش و فهرست می‌کنیم.

5.2 LAVA-M

LAVA-M [17] یک مجموعه ساختگی (synthetic set) از باگ‌ها است که در نقاطی با دسترسی دشوار در باینری‌های واقعی از مجموعهGNU coreutils تزریق شده‌اند. این مجموعه معمولاً برای ارزیابی کارایی فازرهای مدرن مورد استفاده قرار می‌گیرد. ابتدا آزمایش‌هایی را که در مقالات دیگر روی LAVA-M انجام شده‌اند توضیح می‌دهیم و سپس نتایج خود را با آن‌ها مقایسه می‌کنیم. خلاصه این مقایسه در جدول ۲ ارائه شده است.

در مقاله اصلی LAVA-M، نویسندگان دو آزمایش انجام می‌دهند: یکی با یک فازر (FUZZER) نامشخص و دیگری با یک ابزار اجرای نمادین نامشخص SES. هر دو ابزار به ‌صورت کلی به ‌عنوان ابزارهای «پیشرفته و مطرح» توصیف شده‌اند، اما جزئیات آن‌ها منتشر نشده است. این آزمایش‌ها به مدت ۵ ساعت روی یک ماشین نامشخص اجرا شده‌اند.

در مقابل، نویسندگان STEELIX آزمایش‌های خود را روی سیستمی با ۸ هسته پردازنده Intel Xeon E5-1650 v3 و ۸ گیگابایت RAM، با نسخه ۳۲ بیتی سیستم‌عامل اوبونتو 16.04 و تنها با یک thread اجرا کرده‌اند. به ‌طور مشابه، Sanjay و همکاران نیز آزمایش‌های خود با VUZZER را در یک اجرای ۵ ساعته روی سیستمی نامشخص با ۴ گیگابایت RAM و یک هسته انجام داده‌اند.

ما نیز یک آزمایش مشابه انجام دادیم که در آن هر هدف به مدت ۵ ساعت اجرا شدند. در این آزمایش از چند بایت ابتدایی بذر (seed) ارائه‌ شده توسط نویسندگان اصلی، و همچنین از بذرهای معمول و بدون دانش قبلی (uninformed) خودمان استفاده کردیم.

شکل ۱ نتایج را نشان می‌دهد (۵ اجرای مستقل، هر کدام ۵ ساعته؛ با نمایش میانه و بازه اطمینان ۶۰٪ از تعداد باگ‌های کشف ‌شده در طول زمان، به‌صورت درصدی از تعداد باگ‌های موردنظر در LAVA-M).

نتایج حاکی از آن است که در تمام موارد، ما باگ‌های بیشتری نسبت به تعداد باگ‌هایی که نویسندگان اصلی LAVA-M در نظر گرفته بودند کشف کردیم. همچنین در تمام موارد، برای یافتن همه باگ‌ها به زمان بسیار کمتری نسبت به ۵ ساعت کامل نیاز داشتیم. در حالت متوسط و میانه (median)، برای برنامه‌های who و base64 کمتر از ۵ دقیقه طول کشید تا تعداد بیشتری از باگ‌ها کشف شود.

پس از ۱۵ دقیقه، uniq به‌ طور کامل حل (solved) شد. در نهایت، md5sum کُندترین هدف بود و حل آن ۲۵ دقیقه زمان برد. دلیل کندتر بودن md5sum نسبت به سایر اهداف این است که ما از یک محیط busybox استفاده می‌کردیم که در آن تمام فایل‌های داخل مسیر /bin/ به یک باینری یکپارچه (monolithic binary) لینک شده‌اند. این موضوع باعث کاهش قابل‌توجه سرعت محاسبه md5 شد.

ما موفق شدیم تمام باگ‌های درج‌ و فهرست ‌شده را شناسایی کنیم، به‌ جز دو باگ در برنامه who. مهم‌تر از آن، تعداد قابل‌توجهی باگ (۳۳۷ مورد) را کشف کردیم که توسط نویسندگان اصلی به‌ عنوان غیرقابل دسترسی (unreachable) در نظر گرفته شده بودند.

تنها فازر دیگری که توانست بخشی از این باگ‌های فهرست ‌نشده را شناسایی کند، ANGORA بود. با این حال، ما بیش از ۵۰٪ باگ بیشتری نسبت به ANGORA و بیش از سه برابر تعداد باگ‌های فهرست‌ نشده‌ی آن را کشف کردیم. به دلیل تعداد بالای باگ‌های کشف ‌شده‌ی فهرست ‌نشده، با یکی از نویسندگان LAVA-M تماس گرفتیم و او نتایج ما را بر اساس ورودی‌هایی که ارائه دادیم تأیید کرد.

با توجه به این‌که تفاوت بین استفاده از بذرهای (seed) آگاهانه و بدون دانش اولیه ناچیز بود، و همچنین این‌ که ما سایر ابزارهای پیشرفته مدرن روز (state-of-the-art) را با ضریب ۸ تا ۲۶ برابر بهتر پشت سر گذاشتیم، نتیجه می‌گیریم که مجموعه داده LAVA-M این فرضیه را تقویت می‌کند که رویکرد ما از روش‌های موجود بهتر عمل می‌کند و قادر است باگ‌های «عمیق» را به دور از بذرهای (seed) اولیه ارائه شده کشف کند.

در واقع، ما حتی بدون ارائه هیچ بذر اولیه‌ای نیز از تمام روش‌های فعلی بهتر عمل کردیم. با این حال باید توجه داشت که باگ‌های موجود در مجموعه داده LAVA-M مصنوعی (artificial) هستند و نماینده‌ی آسیب‌پذیری‌های دنیای واقعی نیستند.

5.3 چالش بزرگ سایبری (Cyber Grand Challenge)

اهدافی که در چالش بزرگ سایبری (CGC یا همان Cyber Grand Challenge) متعلق به DARPA استفاده شده‌اند، یکی دیگر از مجموعه‌های آزمون پرکاربرد برای ارزیابی فازرها هستند. مشابه مجموعه LAVA-M، ابتدا تنظیمات آزمایشی مورد استفاده توسط فازرهای مختلف روی این اهداف را توضیح می‌دهیم و سپس نتایج آن‌ها را با نتایج خود مقایسه می‌کنیم.

STEELIX فقط زیرمجموعه‌ای از هشت فایل باینری CGC را آزمایش کرد و نتایج آنها را با AFL-DYNINST، نسخه‌ای از AFL که از ابزارگذاری باینری پویا (dynamic binary instrumentation) استفاده می‌کند و به طور قابل توجهی کُندتر از AFL اصلی است، مقایسه کرد. به هر دو ابزار اجازه داده شد تا به مدت سه ساعت فازینگ کنند. STEELIX موفق شد یک کرش (crash) را شناسایی کند که AFL قادر به کشف آن نبود. در مقابل، ما توانستیم کرش (Crash) را با بذر (seed) مورد استفاده STEELIX در کمتر از 30 ثانیه پیدا کنیم.

جدول ۲: باگ‌های فهرست ‌شده و (+ باگ‌های فهرست ‌نشده) که پس از ۵ ساعت فازینگ روی LAVA-M کشف شده‌اند (اعداد از مقالات مربوطه گرفته شده‌اند):

VUZZER، زیرمجموعه‌ای از ۶۳ فایل باینری را آزمایش کرد و فایل‌های باینری که از دستورالعمل‌های ممیز شناور (که ردیابی آلودگی VUZZER نمی‌تواند از عهده آن برآید)، IPC یا فایل‌های باینری که به راحتی در یک حلقه بی‌نهایت قرار می‌گیرند، استفاده می‌کنند را فیلتر کرد.

نویسندگان، مجموعه دقیق اهداف مورد استفاده و همچنین مجموعه اهدافی که در آن‌ها موفق به کشف کرش شده‌ بودند را در اختیار ما قرار دادند. با این حال، آن‌ها نتوانستند بذرهای (seed) دقیق مورد استفاده را ارائه دهند.

ما یک مجموعه بذر مشابه را با استفاده از همان روش بازسازی کردیم. بخشی از ورودی‌ها توسط اسکریپت‌های poller مورد استفاده در CGC تولید شدند و بخشی دیگر از مخزن اصلی DARPA گرفته شدند. با این وجود، نتوانستیم برای ۹ مورد از چالش‌ها، بذری تولید کنیم. از این رو، آن‌ها را از ارزیابی خود حذف کردیم.

VUZZER موفق شد در دو مورد از باینری‌هایی که از ارزیابی حذف شده بودند نیز کرش (crash) شناسایی کند. آزمایش‌های مربوط به VUZZER روی یک میزبان با دو CPU نامشخص ۳۲ بیتی اینتل و ۴ گیگابایت حافظه، درون ماشین مجازی اصلی DECREE انجام شده‌اند. VUZZER و AFL-PIN هر دو به مدت ۶ ساعت زمان فازینگ دریافت کردند. در این تنظیم، آن‌ها توانستند ۲۹ کرش در ۲۷ باینری بیایند. در همین شرایط، AFL-PIN موفق به کشف ۲۳ کرش شد.

تعداد قابل توجهی از باینری‌های هدف در یک حلقه‌ی فعال (busy loop) اجرا می‌شوند و منتظر دریافت دستور خاص «quit» هستند. این موضوع باعث ایجاد تعداد زیادی timeout شده و به‌ طور قابل توجهی کارایی فازینگ را کاهش می‌دهد. اگرچه تشخیص چنین حلقه‌ای در یک محیط محدود مانند CGC ساده است، اما این نوع بهینه‌سازی خارج از دامنه‌ی یک فازر عمومی محسوب می‌شود. به منظور رفع این مشکل، نویسندگان VUZZER به ‌صورت دستی اطمینان حاصل کردند که این ابزار همیشه دستور صحیح «quit» را به ورودی اضافه می‌کند.

ما مجموعه‌ای مشابه از آزمایش‌ها را با چند تفاوت اجرا کردیم: برخلاف نویسندگان VUZZER، ما از نسخه چندسیستمی (multi-OS) منتشر شده توسط دنباله بیت‌ها (Trail of Bits) [3] استفاده کردیم. بنابراین، برخی از مقایسه‌ها ممکن است به دلیل تفاوت‌های جزئی، جانبدارانه (bias) باشند. در این شرایط، ما توانستیم با استفاده از REDQUEEN در همان تلاش اول، در ۳۱ باینری کرش (crash) ایجاد کنیم، در حالی که VUZZER موفق به ایجاد ۲۵ کرش شد.

از آن‌جا که این نتایج بدون هیچ‌گونه تطبیق REDQUEEN با CGC به‌طور خاص به‌ دست آمده‌اند، این آزمایش به‌ عنوان یک مجموعه اعتبارسنجی (validation set) عمل می‌کند تا اطمینان حاصل شود که فرآیند فازینگ ما به هیچ هدف خاصی بیش‌برازش (overfit یا بیش‌سازگاری با داده‌های خاص) نکرده است.

از آن‌جا که مدل فازینگ AFL عمدتاً برای ورودی‌های باینری طراحی شده است، در حالی که CGC شامل تعداد زیادی قالب‌‌بندی‌های تعاملی مبتنی بر خط (line-based interactive formats) است، یک آزمایش دیگر نیز انجام دادیم: در این آزمایش، برخی جهش‌ها (mutations) مرتبط با پروتکل‌های متنی اضافه شدند (عمدتاً شامل جابه‌جایی خطوط و افزودن خطوط تصادفی). همچنین برای تسریع آزمایش‌ها، به‌جای پیکربندی معمول، از ۴ هسته و ۲ ساعت زمان استفاده کردیم. در این آزمایش، توانستیم ۹ ورودی کرش (crashing inputs) جدید دیگر را کشف کنیم. ما در مجموع، موفق شدیم در ۵۴ هدف، ۴۰ مورد را دچار کرش کنیم.

VUZZER توانست در ۵ باینری، کرش شناسایی کند که ما نتوانستیم و در این مورد ناموفق بودیم. در حداقل یک مورد، این موضوع ناشی از تعداد زیاد timeoutها بود؛ مشکلی که VUZZER با تطبیق فازر خود با اهداف خاص (طبق توضیحات قبلی) آن را دور زده بود، کاری که ما انجام ندادیم.

از سوی دیگر، ما ۱۹ فایل باینری را که VUZZER قادر به از کرش کردن آنها نبود، دچار کرش کردیم. این نشان می‌دهد که ما می‌توانیم در این مجموعه داده‌ها، هم VUZZER را ۶۰٪ و هم AFL-PIN را ۷۳٪ بهتر اجرا کنیم.

متأسفانه، نویسندگان T-FUZZ نتایج کامل آزمایش‌های خود روی CGC را منتشر نکرده‌اند. با این حال، آن‌ها اشاره کرده‌اند که روی زیرمجموعه‌ای از باینری‌هایی که VUZZER نیز از آن‌ها استفاده کرده، توانسته‌اند در بازه ۶ ساعته ۲۹ کرش شناسایی کنند که به‌طور قابل‌ توجهی کمتر از ۴۰ کرشی است که رویکرد ما موفق به کشف آن‌ها شده است.

DRILLER روی کل مجموعه باینری‌های CGC ارزیابی شده است. این آزمایش از خوشه‌ای از پردازنده‌های AMD64 نامشخص با چهار هسته برای هر هدف استفاده کرد. پردازش اجرای کانکولیک (concolic execution) نیز به مجموعه دیگری شامل ۶۴ گره (Node) اجرای concolic برون‌سپاری شده بود. هر اجرای concolic به ۴ گیگابایت حافظه محدود بوده و هر هدف به مدت ۲۴ ساعت فاز شده است.

در این تنظیم، فازینگ با AFL توانست در ۶۸ هدف کرش (crash) ایجاد کند. در حالی که DRILLER این عدد را به ۷۷ هدف افزایش داد. باید توجه داشت که DRILLER به‌ عنوان یکی از شرکت‌کنندگان در رقابت CGC، به‌طور خاص برای این مجموعه داده بهینه‌سازی شده است. با این حال، بهبود آن نسبت به فازینگ پایه با AFL تنها در حدود ٪۱۴ بوده است.

نتایج ما روی مجموعه داده VUZZER (مقایسه با AFL-PIN که بهبود ۷۳٪ را نشان داد) بیان می‌کند که در صورت پیاده‌سازی مکانیزم‌های خاص DECREE مانند IPC سفارشی، ممکن است بتوانیم به بهبودهایی مشابه DRILLER دست پیدا کنیم.

5.4 برنامه‌های دنیای واقعی (Real-World Applications)

ما همچنین REDQUEEN را روی چندین برنامه‌ی واقعی (real-world applications) ارزیابی کردیم. به ‌طور کلی، همه‌ی انواع باگ‌هایی را که معمولاً فازرها کشف می‌کنند شناسایی کردیم؛ از جمله:

دسترسی‌های خارج از محدوده حافظه (out-of-bounds read/write)
تمام شدن منابع (resource exhaustion)، هم از نظر زمان و هم حافظه
نشت حافظه (memory leaks)
سرریز پشته (stack overflows)
تقسیم بر صفر (division by zero)
بررسی شرط (assertion)
استفاده مجدد پس از آزادسازی (use-after-free)
استفاده از مقادیر مقداردهی‌ اولیه نشده (use of uninitialized values)
و موارد مشابه

برای اهداف این ارزیابی، برخی از دسته‌های باگ را در نظر نگرفتیم، زیرا تعداد آن‌ها برای بررسی دستی (manual triage) بسیار زیاد بود و از نظر پژوهش امنیتی اهمیت کمتری داشتند. این دسته‌ها شامل موارد زیر می‌باشند:

نشت حافظه (memory leaks)
مصرف بیش از حد منابع (resource exhaustion)
استفاده از مقادیر مقداردهی‌نشده (مگر در مواردی که به پیامدهای جدی‌تر منجر شوند)
و سرریز پشته (stack overflows)

Binutils. برای تخمین توانایی کشف باگ‌های عمیق (deep bugs) در بخش‌هایی از کد که دسترسی به آن‌ها دشوار است، ما میزان پوشش کد (code coverage) تولید شده توسط ابزارهای مختلف را روی باینری‌های واقعی از مجموعه binutils اندازه‌گیری کردیم. هدف این بود که ارزیابی خود را از حالت تست‌های مصنوعی و ساختگی (synthetic) به سمت تست‌های واقعی‌تر و عملی‌تر گسترش دهیم.

ما از پوشش کد به ‌عنوان یک معیار جایگزین (proxy metric) برای توانایی کشف باگ‌های عمیق استفاده کردیم، زیرا تعیین دقیق تعداد باگ‌های کشف ‌شده بسیار دشوار است. برای مقایسه درست تعداد باگ‌های شناسایی ‌شده بین ابزارها، لازم بود هزاران کرش (crash) به‌ صورت دستی بررسی شوند که در عمل امکان‌پذیر نیست. در بسیاری از موارد نیز اغلب ابزارها حتی موفق به تولید یک کرش (crash) هم نمی‌شدند، که باعث می‌شد نتایج آزمایش چندان گویا نباشند. ما پوشش کد را معیار مناسبی می‌دانیم، زیرا هیچ فازری نمی‌تواند در کدی که اصلاً اجرا (covered) نمی‌شود، باگی پیدا کند.

به ‌عنوان مجموعه آزمون، ما هر هشت برنامه از مجموعه binutils را انتخاب کردیم؛ برنامه‌هایی که هر کدام یک فایل را پردازش می‌کنند بدون اینکه آن را تغییر دهند. متأسفانه امکان مقایسه با DRILLER وجود نداشت، زیرا این ابزار فقط روی باینری‌های DECREE قابل استفاده است. همچنین چون ابزارهای ANGORA و T-FUZZ هنوز در دسترس نبودند، نتوانستیم آزمایش‌های خودمان را برای مقایسه با آن‌ها اجرا کنیم.

بنابراین، VUZZER را به ‌عنوان یکی از معدود فازرهای دانشگاهی در سطح ابزارهای پیشرفته مدرن (state-of-the-art) به ‌همراه AFL با افزونه‌های LAF-INTEL و AFLFAST انتخاب کردیم. نکته مهم این است که هم LAF-INTEL و هم VUZZER به‌ طور مشخص برای عبور از «بایت‌های جادویی (magic bytes)» و سایر موانع فازینگ، مشابه هدف ابزار ما طراحی شده‌اند.

در تمام آزمایش‌ها، از یک بذر (seed) یکنواخت و بدون دانش قبلی (uninformed seed) استفاده کردیم تا توانایی ابزارها را در حل این موانع (roadblocks) بسنجیم. در مورد KLEE نیز باید توجه داشت که این ابزار به‌ طور مستقیم فایل آزمون تولید نمی‌کند، زیرا با کشف وضعیت‌های (states) جدید کار می‌کند. در عوض، فقط زمانی مورد آزمون (test case) تولید می‌شود که یک وضعیت به‌ طور کامل بررسی شده و یا به timeout رسیده باشد.

بنابراین غیرمعمول نیست که KLEE در طول اجرا فقط تعداد کمی زمانی مورد آزمون (test case) تولید کند. پس از رسیدن به timeout، این ابزار شروع به حل کردن تمام وضعیت‌های (state) باقی‌مانده می‌کند تا پوشش بیشتری تولید کند و در برخی موارد ممکن است ساعت‌ها زمان اضافی صرف کند تا مورد آزمون‌های واقعی را تولید نماید.

به همین دلیل، ما برای KLEE یک بازه زمانی ۷ ساعته به منظور تحلیل وضعیت‌های نمادین (symbolic states) در نظر گرفتیم و ۳ ساعت دیگر نیز برای تولید زمانی موارد آزمون (test case) اختصاص دادیم. در نهایت، KLEE را پس از مجموعاً ۱۰ ساعت به اجبار متوقف کردیم.

این معماری همچنین تعیین دقیق زمان تولید هر ورودی جدید را دشوار می‌کند. برای رسم نمودارها، فرض کردیم که ورودی‌ها با نرخ ثابت تولید می‌شوند. این فرض قطعاً دقیق نیست، زیرا انتظار می‌رود در ساعات ابتدایی تعداد ورودی‌های بیشتری تولید شود. با این حال، چون هدف اصلی ما مقایسه تعداد نهایی بلوک‌های پایه‌ای (basic block) پوشش‌ داده‌ شده است، شکل دقیق منحنی در نمودار اهمیت چندانی ندارد.

VUZZER قادر به فاز کردن اهدافی که ورودی خود را از طریق stdin دریافت می‌کنند نیست، بنابراین نتایج VUZZER برای هدف cxxfilt در دسترس نمی‌باشد. به منظور نمایش سایر فازرهای مبتنی بر Intel PT، ما از HONGGFUZZ [6] در حالت Intel PT و همچنین نسخه اصلی KAFL همراه با افزونه حلقه ۳ خود استفاده کردیم. نتایج پنج اجرای 10 ساعته را می‌توان در شکل 2 مشاهده کرد.

نکته قابل توجه این است که در تمام موارد، REDQUEEN بیشترین میزان پوشش کد را ایجاد کرده است. برای اطمینان از این‌که این نتایج ناشی از تغییرات تصادفی نیستند، از آزمون آماری Mann-Whitney U روی تعداد بلوک‌های پایه کشف ‌شده استفاده کردیم؛ همان‌طور که توسط Arcuri و همکارانش برای ارزیابی الگوریتم‌های تصادفی توصیه شده است. نتایج در جدول ۳ نمایش داده شده‌ و بیانگر آن است که در تقریباً تمام موارد، تفاوت‌های مشاهده‌ شده از نظر آماری معنادار هستند (با p < 0.05).

نکته جالب این است که VUZZER تعداد بسیار کمی از بلوک‌های پایه جدید را پیدا می‌کند. برای بررسی این رفتار و اطمینان از این‌که از VUZZER به ‌درستی استفاده کرده‌ایم، با نویسندگان آن تماس گرفتیم. آن‌ها آزمایش‌های ما را بازتولید کردند و به نتایج بسیار مشابهی رسیدند.

در جریان این تعامل مشخص شد که VUZZER به ‌شدت به این فرض وابسته است که فقط یک قالب ورودی معتبر وجود دارد. از آن‌جا که اکثر برنامه‌های binutils می‌توانند انواع مختلفی از قالب‌ها (format) را پردازش کنند، VUZZER تعداد زیادی از مسیرها را از جستجو حذف می‌کند. علاوه بر این، VUZZER برای شناسایی مسیرهای خطا به ورودی‌های معتبر متکی است.

با این حال، ورودی‌های بدون دانش قبلی (uninformed) ما تأثیر منفی شدیدی بر عملکرد VUZZER نداشتند، زیرا این ابزار همچنان توانست به ‌سرعت فایل‌های معتبر ELF پیدا کند (یعنی مسیرهای جالب را به‌ عنوان «خطاهای غیرمهم» کنار نگذاشت). ما با استفاده از REDQUEEN، باگ‌هایی را در ابزارهای زیر از مجموعه binutils پیدا و گزارش کردیم که عبارتند از ld-new، as-new، gprof، nm-new، cxxfilt و objdump. در نهایت مشخص شد که باگ‌های کشف‌ شده در cxxfilt، nm-new و objdump همگی نمونه‌هایی از یک باگ مشترک در کتابخانه‌ای بودند که برای رمزگشایی نمادهای ++C استفاده می‌شود.

جدول ۳: مقادیر p آزمون U Mann-Whitney بر روی تعداد بلوک‌های پایه یافت شده در 10 ساعت. تقریباً تمام نتایج از نظر آماری معنی‌دار هستند (p < 0.05):

ما مشاهده کردیم که REDQUEEN، LAF-INTEL و AFLFAST همگی تعداد بسیار بیشتری کرش (crash) را گزارش می‌دهند. با این حال، اغلب این کرش‌ها در واقع ورودی‌هایی بودند که از محدودیت‌های حافظه تعیین‌ شده توسط فازرها فراتر رفته بودند. ما کرش‌های مربوط به objdump را به‌صورت دستی بررسی و اعتبارسنجی (validate) کردیم و مشخص شد که نه AFLFAST و نه LAF-INTEL هیچ باگ واقعی را شناسایی نکرده‌اند، در حالی که برخی از کرش‌های شناسایی ‌شده توسط REDQUEEN واقعاً باگ‌های جدید بودند. این موضوع نشان می‌دهد که رویه‌ی رایجِ گزارش تعداد کرش‌های یافت شده می‌تواند گمراه‌کننده باشد و انجام تریاژ (بررسی و ارزیابی دقیق باگ‌ها و اولویت‌بندی مناسب آنها) ضروری است.

مطالعه موردی: objdump. یک مشاهده شگفت‌انگیز این بود که ما توانستیم یک محدودیت پیچیده در objdump را حل کنیم که از تابع جستجوی جدول درهم‌سازی « bfd get section by name(bfd* obj, char* name)» برای بررسی وجود بخشی با نام داده شده در فایل شیء ورودی obj استفاده می‌کرد: از آنجایی که به تابع دو آرگومان اشاره‌گر داده (pointer arguments) شده بود، REDQUEEN به طور خودکار نام را استخراج کرده و به دیکشنری پویا اضافه کرد.

سایر اهداف (Other Targets). برای اطمینان از این‌که ابزار ما قادر به کشف باگ‌های جدید (novel bugs) است، توانایی آن را روی مجموعه‌ای متنوع از برنامه‌های واقعی ارزیابی کردیم. نتایج در جدول ۴ قابل مشاهده است. در همه موارد، باگ‌های کشف ‌شده را به ‌صورت دستی بررسی (triage) نموده و گزارش کردیم.

ما کار را با برنامه‌هایی آغاز کردیم که معمولاً در مقالات دیگر استفاده می‌شوند، از جمله: libtiff (tiff2ps) ،ImageMagick و jhead. تمامی این برنامه‌ها، در جدیدترین نسخه ابونتو (نسخه 16.04 LTS) بررسی شدند؛ نسخه‌ای که انتظار می‌رفت باگ‌های گزارش‌ شده قبلی در آن برطرف شده باشند. با وجود آن که این ابزارها قبلاً به ‌طور گسترده مورد آزمایش قرار گرفته بودند، ما همچنان موفق به کشف باگ‌های جدید شدیم و آن‌ها را بررسی و گزارش کردیم. همچنین، ارزیابی‌های خود را روی مجموعه‌ای از ابزارهای مرتبط با قالب‌های فایل چندرسانه‌ای ادامه دادیم، از جمله: sam2p ،wine و fdk-aac (بخشی از ffmpeg).

در راستای ایده‌ی مقاله اصلی KAFL، ما ازREDQUEEN برای هدف‌گیری دو درایور سیستم فایل (به‌طور مشخص hfs.ko و ntfs.ko) از آخرین نسخه Ubuntu (16.04 LTS) استفاده کردیم. در هر دو مورد، چندین مورد خرابی حافظه (memory corruption) پیدا و گزارش کردیم.

در نهایت، علاوه بر اهدافی که عمدتاً مبتنی بر ورودی‌های باینری بودند، چندین هدف متنی (text-based) شناخته ‌شده را نیز آزمایش کردیم، از جمله mruby، perl، bash و libxml2. در تقریباً تمام این اهداف، از بذرهای (seed) بدون دانش قبلی (uninformed seeds) برای کشف باگ‌ها استفاده کردیم. این آزمایش نشان می‌دهد که رویکرد ما نه‌ تنها برای کدهای user-space، بلکه برای کدهای سطح کرنل (kernel) نیز قابل استفاده است.

جدول ۴: باگ‌های شناسایی و گزارش ‌شده‌ توسط REDQUEEN:

مطالعه موردی: mruby. یکی از آسیب‌پذیری‌های جالبی که یافتیم مربوط به سرریز عدد صحیح (integer overflow) در mruby بود. هنگام تغییر اندازه یک رشته (string)، اندازه جدید به ‌صورت «توان بعدی عدد ۲» انتخاب می‌شد. این محاسبه ممکن بود دچار سرریز شود و در نتیجه یک مقدار منفی تولید کند.

در حالت عادی، یک بررسی علامت (sign check) بعد از این محاسبه وجود داشت تا از این مشکل جلوگیری کند. اما کامپایلر تشخیص داد که توان‌های عدد ۲ همیشه مثبت هستند و از آن‌ جا که سرریز عدد صحیح علامت‌دار (signed integer overflow) در زبان C به ‌عنوان رفتار تعریف ‌نشده (undefined behavior) در نظر گرفته می‌شود، این بررسی را حذف کرد.

در نتیجه، ما توانستیم رشته‌هایی با طول منفی تولید کنیم. از آن‌جا که طول جدید از طول قبلی کوچک‌تر بود، تخصیص حافظه جدید انجام نشد، اما مقدار طول رشته به یک مقدار منفی به‌روزرسانی شد. این باعث شد رشته به‌ طور مؤثر کل فضای حافظه را پوشش دهد. این رفتار فقط در باینری‌های بدون ابزارگذاری (instrumentation) که با gcc و سطح بهینه‌سازی ۲ کامپایل شده بودند مشاهده گردید.

این باگ به ‌خوبی نشان می‌دهد که چرا داشتن تکنیک‌هایی که روی اهداف صرفا باینری‌ (binary-only targets) به‌خوبی کار می‌کنند اهمیت زیادی دارد. ما به‌شدت مشکوک هستیم که مقدار عددیِ سرریزکننده (یک عدد ۶۴ بیتی با ۱۹ رقم) از طریق کدگذاری عددی ASCII کشف شده باشد.

5.5 ارزیابی پایه (Baseline Evaluation): قالب فایل PNG

ما آزمایش‌های زیر را انجام دادیم تا نشان دهیم بهبودهای به ‌دست‌آمده در نتایج ما واقعاً ناشی از تکنیک‌های پیشنهادی هستند. برای این منظور از کتابخانه‌ی lodepng استفاده کردیم؛ یک کتابخانه کوچک که به‌ راحتی به ‌صورت ایستا (statically) لینک می‌شود و امکان بارگذاری فایل‌های PNG را فراهم می‌کند. قالب PNG، یک مطالعه‌ی موردی مناسب برای بررسی موانع رایج در فازینگ است، زیرا بر پایه‌ی مجموعه‌ای از قطعه‌ها (chunk) ساخته شده است. هر قطعه (chunk) با یک هدر (Header) آغاز می‌شود (که توسط یک مقدار جادویی ۴ بایتی شناسایی می‌شود) و شامل یک جمع‌آزمای (checksum) CRC32 روی محتوای خود است. همچنین محتوای قطعه IDAT، شامل داده‌های پیکسلی فشرده ‌شده با zlib است که به همراه یک جمع‌آزمای دیگر از نوع Adler-32 می‌آید.

در هر آزمایش، ۱۵ اجرای مستقل (run) به مدت یک ساعت انجام دادیم و تعداد بلوک‎های پایه‌ای (basic block) کشف‌ شده را در طول زمان اندازه‌گیری کردیم. نتایج این آزمایش‌ها در شکل ۳ نشان داده شده‌ است. این شکل شامل مقدار میانه (median) تعداد بلوک‎های پایه‌ای در هر لحظه زمانی، به همراه فواصل اطمینان (confidence intervals) است.

ابتدا، ما تأیید می‌کنیم که بایت‌های جادویی (magic bytes) با موفقیت توسط REDQUEEN حل (solved) می‌شوند، در حالی که KAFL به‌تنهایی قادر به حل آن‌ها نیست. برای انجام این کار، دو بررسی جمع‌آزما (checksum) را در فایل باینری غیرفعال کردیم و نتایج را برای سه حالت «KAFL، KAFL همراه با یک دیکشنری حاوی تمام بایت‌های جادویی مربوطه و REDQUEEN» زیر با هم مقایسه کردیم. نتایج این آزمایش در پیکربندی «جمع‌آزماهای حذف شده (Checksums Removed)» در شکل ۳ نمایش داده شده است.

5.6 عملکرد (Performance)

در این آزمایش، کارایی (efficiency) و اثربخشی (effectiveness) رویکرد خود را اندازه‌گیری کردیم. برای سنجش کارایی، تعداد کل اجرای برنامه‌ها در هر ثانیه را که توسط REDQUEEN، KAFL، LAF-INTEL و AFLFAST به‌ دست آمده است مقایسه کردیم.

برای سنجش اثربخشی (effectiveness)، درصد ورودی‌هایی را در نظر گرفتیم که توسط موتورهای جهش (mutation engines) مختلف استفاده ‌شده در REDQUEEN کشف شده‌اند. در نهایت، میزان فراوانی (prevalence) طرح‌های کدگذاری پیشنهادی نیز مورد ارزیابی قرار گرفت. در تمام موارد، از داده‌های به‌ دست‌ آمده در آزمایش مجموعه binutils در بخش 5.4 استفاده کردیم.

جدول ۵: تعداد ورودی‌هایی که مسیرهایی با پوشش جدید را در هر زمان صرف شده با استفاده از تکنیک‌های مختلف فعال می‌کنند. زمان لازم برای جهش‌دهنده مبتنی بر ورودی با وضعیت ما شامل ردگیری، رنگ‌آمیزی و اجرای تمام ورودی‌های پیشنهادی است. در اغلب موارد، تناظر ورودی با وضعیت، ورودی‌های به مراتب بیشتری را در هر زمان نسبت به هر روش جهش دیگری که استفاده می‌شود، تولید می‌کند:

عملکرد کلی فازینگ را می‌توان در شکل ۴ مشاهده کرد. میله‌ها میانگین تعداد اجراهای انجام شده در ثانیه را نشان می‌دهند. تأثیر معمول عملکرد برای KAFL و REDQUEEN در مقایسه با LAF-INTEL و AFLFAST غالبا در محدوده ۲۵ تا ۵۰ درصد است. علت آن نیز این است که KAFL از ابزارگذاری (instrumentation) مبتنی بر کامپایلر سریع استفاده نمی‌کند و روی کد باینری کار می‌کند. با این وجود، تا آنجا که ما می‌دانیم، REDQUEEN سریع‌ترین فازر صرفا باینری تا به امروز است.

جدول ۶: درصد مسیرهایی که توسط طرح‌های مختلف کدگذاری (encoding schemes) کشف شده‌اند:

REDQUEEN در یک مورد، کمی بهتر از KAFL عمل می‌کند. اگرچه این نتیجه در نگاه اول غیرمنتظره است (زیرا ما در حال انجام کار اضافی هستیم)، اما توضیح مشخصی برای آن وجود دارد: در اهداف واقعی (real-world targets)، تعداد اجرای برنامه در هر ثانیه به ‌شدت به محتوای ورودی‌های موجود در صف (queue) وابسته است. اگر صف شامل ورودی‌های کُند باشد، کارایی کاهش می‌یابد.

زمانی که KAFL قادر به عبور از یک مانع (roadblock) نباشد، تنها ورودی‌های جدیدی که تولید می‌شوند آن‌هایی هستند که حلقه‌های بیشتری را اجرا می‌کنند. همان‌طور که در شکل ۴ مشاهده می‌شود، تأثیر افزونه REDQUEEN بر تعداد اجراها در هر ثانیه نسبتاً کم است و گاهی حتی باعث افزایش تعداد اجراها نیز می‌شود.

با وجود آن که ردگیری مبتنی بر نقطه توقف (breakpoint-based tracing) کُند است (گاهی تا ۵۰ برابر یا بیشتر)، اما تأثیر آن بر عملکرد کلی فازینگ ناچیز است، زیرا فاز REDQUEEN تنها یک‌بار برای هر ورودی در صف اجرا می‌شود.

اندازه‌گیری اثربخشی در جدول ۵ نشان داده شده است. تمام تکنیک‌ها توسط REDQUEEN روی هر ورودی استفاده می‌شوند و تعداد ورودی‌های جدید تولید شده توسط هر تکنیک ثبت شده است. مشاهده می‌شود که جهش‌های مبتنی بر تناظر ورودی با وضعیت (input-to-state correspondence) در حالی که زمان بسیار کمتری مصرف می‌کنند اما اغلب به اندازه یا حتی بیشتر از سایر فازها، ورودی جدید تولید می‌کنند.

این نشان می‌دهد که تکنیک‌های ما فراتر از موانع کلاسیک (archetypical roadblocks) عمل می‌کنند: آن‌ها می‌توانند مسیرهای بیشتری را سریع‌تر از سایر استراتژی‌های جهش کشف کنند. در نهایت، فراوانی طرح‌های مختلف کدگذاری نیز با اندازه‌گیری درصد مسیرهایی که توسط هر روش پیدا شده‌اند بررسی گردید. نتایج در جدول ۶ نشان داده شده است.

مشخص شد که تقریباً تمام بهبودهای ما ناشی از چیزی است که آن را تناظرهای یک به یک (one-to-one correspondence) می‌نامیم. در مجموع، این دو آزمایش نشان می‌دهند که جهش‌های مبتنی بر ورودی با وضعیت (input-to-state) یک روش بسیار عمومی، مؤثر و کارآمد هستند که می‌توانند به‌ طور قابل‌ توجهی عملکرد فازرها را بهبود بخشند.

5.7 جمع‌بندی سطح بالا (High-Level Summary)

پس از نشان دادن اینکه ما قادر به افزایش قابل توجه پوشش (coverage) تولید شده در سه مجموعه آزمون بزرگ و یافتن اشکالات جدید در نرم‌افزارهای فضای هسته و کاربر (kernel- and user-space) هستیم، نتیجه می‌گیریم که RQ1 برقرار است و تکنیک‌های مبتنی بر تناظر ورودی با وضعیت (input-to-state correspondence) برای اهداف فازینگ مفید هستند. پس از مقایسه نتایج ابزارهای پیشرفته در همان مجموعه‌های آزمون، با اطمینان می‌توانیم به RQ2 پاسخ دهیم: ما قادر به عملکرد بهتر از رویکردهای مبتنی بر اجرای نمادین (symbolic execution) و ردگیری آلودگی (taint tracking)، که توسط VUZZER، ANGORA ،T-FUZZ و KLEE نشان داده می‌شوند، در هنگام اندازه‌گیری توانایی کشف رفتار و باگ‌های (bugs) جدید هستیم.

در نهایت، ما نشان می‌دهیم که حتی در یک سناریوی صرفا باینری، تکنیک‌های مبتنی بر تناظر ورودی با وضعیت ما، به اندازه کافی قدرتمند هستند تا با سایر رویکردها رقابت کنند، حتی اگر بررسی‌های هش (hash checks) برای ابزارهای رقیب حذف شوند و یک فرهنگ لغت (dictionary) مناسب در اختیار آنها قرار گیرد. این به پرسش پژوهشی سوم پاسخ می‌دهد. به طور خلاصه، ما مطمئن هستیم که روش تناظر ورودی با وضعیت ما به طور قابل توجهی فازینگ بازخورد مبتنی بر پوشش (coverage-based feedback fuzzing) را بهبود می‌بخشد.

6. محدودیت‌ها (LIMITATIONS)

رویکرد ما بدون نیاز به دسترسی به کد منبع و بدون آگاهی از محیط اجرا، قابل استفاده است. با این حال، حتی در شرایطی که برخی فازرهای پیشرفته (state-of-the-art) به کد منبع نیز دسترسی دارند، همچنان عملکرد بهتری ارائه می‌دهد. این موضوع به این معنا نیست که روش‌های پیچیده‌تر بی‌فایده هستند؛ بلکه بالعکس، ما معتقدیم این روش‌ها در برخی شرایط خاص که رویکرد ما مزیتی ارائه نمی‌دهد، همچنان بسیار مفید می‌باشند. ما هنگام بررسی دستی اهداف مختلف مورد بحث در این مقاله، با نمونه‌هایی از چنین مواردی مواجه شدیم: قالب فایل PNG، حاوی داده‌های فشرده‌ای است که رمزگشا (decoder) در حین اجرا از حالت فشرده خارج می‌کند (decompress). در برخی از برنامه‌های مجموعه آزمایشی binutils، یک رشته از ورودی برای فهرست‌بندی یک نقشه هش (hash map) استفاده می‌شود و یک عدد صحیح را بازمی‌گرداند که پس از آن استفاده می‌شود و در ادامه پردازش به کار می‌رود.

در نهایت، ابزار base64 از مجموعه داده LAVA-M رمزگشایی base64 را اعمال می‌کند. در حالی که در پیاده‌سازی فعلی ما برای base64 هیچ طرح کدگذاری (encoding scheme) در نظر گرفته نشده است. در تمام این موارد، ورودی اولیه دیگر به ‌صورت مستقیم با وضعیت (state) پس از تبدیل متناظر نیست؛ بنابراین رویکرد ما قادر به حل کارآمد محدودیت‌هایی که پس از آن رخ می‌دهند، نیست.

ما معتقدیم که دو مورد اول (فشرده‌سازی و نقشه‌های هش) نیز برای رویکردهای مبتنی بر اجرای کونکولیک (concolic execution) دشوار است. اکثر موتورهای کونکولیک (concolic engines) نمی‌توانند مواردی را که باید از مسیرهای مختلف برای تغییر مقادیر استفاده کرد، به طور مؤثر مدیریت کنند. در مورد base64، می‌توانیم به راحتی یک رمزگذار دیگر اضافه کنیم. با این حال، همانطور که ارزیابی ما نشان می‌دهد، این موارد نادر می‌باشند. در نتیجه، ابزارهایی که قادر به حل این موارد هستند، با مشکلات رایج‌تری مانند انفجار مسیر (path explosion) یا عملکرد ضعیف (poor performance) در اهداف پیچیده و واقعی دست و پنجه نرم می‌کنند. در مجموع، ما پیشنهاد می‌کنیم که در صورت امکان از رویکرد سبک (lightweight approach) ما به ‌عنوان مرحله اول استفاده شود و سپس چالش‌های باقی‌مانده با روش‌های پیچیده‌تر حل شوند.

7. نتیجه‌گیری (CONCLUSION)

ما در این مقاله، روش‌های مبتنی بر تناظر ورودی با وضعیت (input-to-state correspondence) را به منظور بهبود فازینگ ارائه و ارزیابی کردیم. ما نشان داده‌ایم که می‌توان با حل مقایسه‌ بایت‌های جادویی (magic bytes) و بررسی‌ جمع‌آزماها (checksum)، پوشش کد (coverage) را در اهداف صرفاً باینری به طور قابل توجهی بهبود بخشید. اگرچه رویکرد ما به اندازه سایر رویکردهای مبتنی بر اجرای نمادین (symbolic execution) یا ردگیری آلودگی (taint tracking)، دقیقا بر پایه‌ی چارچوب‌های صوری و رسمی (formalism) استوار نیست، اما معتقدیم که کاملا از AFL الهام گرفته و سریع، سبک و از همه مهم‌تر مقاوم است. حتی اگر تجزیه و تحلیل برخی از بخش‌های برنامه بسیار دشوار باشد، رویکرد ما در سایر بخش‌های هدف همچنان قابل اجرا و مؤثر است. در مجموع، ما بر این باوریم که کار ما نشان می‌دهد که می‌توان بدون اتکا به روش‌های پیچیده و شکننده، عملکرد فازرها را به شکل قابل توجهی بهبود بخشید.

قدردانی‌ها (ACKNOWLEDGMENTS)

این کار با حمایت شرکت Intel و در قالب مؤسسه تحقیقاتی مشترک Intel با عنوان “Collaborative Autonomous & Resilient Systems (ICRI-CARS)” انجام شده است. تحقیقاتی که منجر به این نتایج شده است، از برنامه تحقیق و نوآوری Horizon 2020 اتحادیه اروپا تحت توافقنامه کمک هزینه شماره 786669 حمایت مالی دریافت کرده است. محتوای این سند صرفاً بیانگر دیدگاه نویسندگان آن است و لزوماً بازتاب‌دهنده نظر کمیسیون اروپا یا آژانس اجرایی پژوهش نیست. این نهادها هیچ مسئولیتی در قبال استفاده احتمالی از اطلاعات ارائه ‌شده در این سند ندارند. در پایان، از Ali Abbasi، Joel Frank، Emre Güler و Christine Utz بابت بازخوردهای ارزشمندشان تشکر می‌کنیم.

منابع

				
					[1] Announcing OSS-Fuzz: Continuous fuzzing for open source software. https://testing.googleblog.com/2016/12/announcing-oss-fuzz-continuous-fuzzing.html.
[2] Circumventing fuzzing roadblocks with compiler transformations. https://lafintel.wordpress.com/. Accessed: 2018-08-07.
[3] Darpa challenge binaries on linux, os x, and windows. https://github.com/trailofbits/cb-multios. Accessed: 2018-08-07.
[4] Peach. http://www.peachfuzzer.com/. Accessed: 2018-08-07.
[5] Project Triforce: Run AFL on Everything! https://www.nccgroup.trust/us/about-us/newsroom-and-events/blog/2016/june/project-triforce-run-afl-on-everything/.
[6] Security oriented fuzzer with powerful analysis options. https://github.com/google/honggfuzz. Accessed: 2018-08-07.
[7] Andrea Arcuri and Lionel Briand. A hitchhiker’s guide to statistical tests for assessing randomized algorithms in software engineering. Software Testing, Verification and Reliability, 24(3):219–250, 2014.
[8] Osbert Bastani, Rahul Sharma, Alex Aiken, and Percy Liang. Synthesizing program input grammars. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2017.
[9] Fabrice Bellard. Qemu, a fast and portable dynamic translator. In USENIX Annual Technical Conference, FREENIX Track, 2005.
[10] Marcel B¨ohme, Van-Thuan Pham, and Abhik Roychoudhury. Coverage-based greybox fuzzing as markov chain. In ACM Conference on Computer and Communications Security (CCS), 2016.
[11] Derek Bruening, Evelyn Duesterwald, and Saman Amarasinghe. Design and implementation of a dynamic optimization framework for windows. In ACM Workshop on Feedback-Directed and Dynamic Optimization, 2001.
[12] Cristian Cadar, Daniel Dunbar, and Dawson R Engler. Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs. In Symposium on Operating Systems Design and Implementation (OSDI), 2008.
[13] Sang Kil Cha, Thanassis Avgerinos, Alexandre Rebert, and David Brumley. Unleashing Mayhem on Binary Code. In IEEE Symposium on Security and Privacy, 2012.
[14] Sang Kil Cha, Maverick Woo, and David Brumley. Program-adaptive mutational fuzzing. In IEEE Symposium on Security and Privacy, 2015.
[15] Buddhika Chamith, Bo Joel Svensson, Luke Dalessandro, and Ryan R. Newton. Instruction punning: Lightweight instrumentation for x86-64. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2017.
[16] Peng Chen and Hao Chen. Angora: Efficient fuzzing by principled search. In IEEE Symposium on Security and Privacy, 2018.
[17] Brendan Dolan, Patrick Hulin, Engin Kirda, Tim Leek, Andrea Mambretti, William Robertson, Frederick Ulrich, and Ryan Whelan. LAVA: large-scale automated vulnerability addition. In IEEE Symposium on Security and Privacy, 2016.
[18] Will Drewry and Tavis Ormandy. Flayer: exposing application internals. In USENIX Workshop on Offensive Technologies (WOOT), 2007.
[19] Shuitao Gan, Chao Zhang, Xiaojun Qin, Xuwen Tu, Kang Li, Zhongyu Pei, and Zuoning Chen. Collafl: Path sensitive fuzzing. In IEEE Symposium on Security and Privacy, 2018.
[20] Vijay Ganesh, Tim Leek, and Martin Rinard. Taint-based directed whitebox fuzzing. In International Conference on Software Engineering (ICSE), 2009.
[21] Patrice Godefroid, Adam Kiezun, and Michael Y Levin. Grammar-based whitebox fuzzing. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2008.
[22] Patrice Godefroid, Nils Klarlund, and Koushik Sen. DART: Directed Automated Random Testing. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2005.
[23] Patrice Godefroid, Michael Y Levin, David A Molnar, et al. Automated whitebox fuzz testing. In Symposium on Network and Distributed System Security (NDSS), 2008.
[24] Patrice Godefroid, Hila Peleg, and Rishabh Singh. Learn&fuzz: Machine learning for input fuzzing. Technical report, January 2017.
[25] Peter Goodman. Shin GRR: Make Fuzzing Fast Again. https://blog.trailofbits.com/2016/11/02/shin-grr-make-fuzzing-fast-again/.
[26] Istvan Haller, Asia Slowinska, Matthias Neugschwandtner, and Herbert Bos. Dowsing for overflows: A guided fuzzer to find buffer boundary violations. In USENIX Security Symposium, 2013.
[27] HyungSeok Han and Sang Kil Cha. Imf: Inferred model-based fuzzer. In ACM Conference on Computer and Communications Security (CCS), 2017.
[28] Wookhyun Han, Byunggill Joe, Byoungyoung Lee, Chengyu Song, and Insik Shin. Enhancing memory error detection for large-scale applications and fuzz testing. In Symposium on Network and Distributed System Security (NDSS), 2018.
[29] Aki Helin. A general-purpose fuzzer. https://gitlab.com/akihe/radamsa. Accessed: 2018-08-07.
[30] Chin-Chia Hsu, Che-Yu Wu, Hsu-Chun Hsiao, and Shih-Kun Huang. Instrim: Lightweight instrumentation for coverage-guided fuzzing. In Symposium on Network and Distributed System Security (NDSS), Workshop on Binary Analysis Research, 2018. 
[31] Yuekang Li, Bihuan Chen, Mahinthan Chandramohan, Shang-Wei Lin, Yang Liu, and Alwen Tiu. Steelix: Program-state Based Binary Fuzzing. In Joint Meeting on Foundations of Software Engineering, 2017.
[32] Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazel-wood. Pin: building customized program analysis tools with dynamic instrumentation. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2005.
[33] David Molnar, Xue Cong Li, and David Wagner. Dynamic Test Generation to Find Integer Bugs in x86 Binary Linux Programs. In USENIX Security Symposium, 2009.
[34] Hui Peng, Yan Shoshitaishvili, and Mathias Payer. T-fuzz: fuzzing by program transformation. In IEEE Symposium on Security and Privacy, 2018.
[35] Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida, and Herbert Bos. VUzzer: Application-aware Evolutionary Fuzzing. In Symposium on Network and Distributed System Security (NDSS), February 2017.
[36] Alexandre Rebert, Sang Kil Cha, Thanassis Avgerinos, Jonathan M Foote, David Warren, Gustavo Grieco, and David Brumley. Optimizing seed selection for fuzzing. In USENIX Security Symposium, 2014.
[37] Sergej Schumilo, Cornelius Aschermann, Robert Gawlik, Sebastian Schinzel, and Thorsten Holz. kafl: Hardware-assisted feedback fuzzing for os kernels. In USENIX Security Symposium, 2017.
[38] Nick Stephens, John Grosen, Christopher Salls, Andrew Dutcher, Ruoyu Wang, Jacopo Corbetta, Yan Shoshitaishvili, Christopher Kruegel, and Giovanni Vigna. Driller: Augmenting fuzzing through selective symbolic execution. In Symposium on Network and Distributed System Security (NDSS), 2016.
[39] Dmitry Vyukov. gofuzz. https://go-talks.appspot.com/github.com/dvyukov/go-fuzz/slides/go-fuzz.slide#17.
[40] Tielei Wang, Tao Wei, Guofei Gu, and Wei Zou. TaintScope: A checksum-aware directed fuzzing tool for automatic software vulnerability detection. In IEEE Symposium on Security and Privacy, 2010.
[41] Maverick Woo, Sang Kil Cha, Samantha Gottlieb, and David Brumley. Scheduling black-box mutational fuzzing. In ACM Conference on Computer and Communications Security (CCS), 2013.
[42] Wen Xu, Sanidhya Kashyap, Changwoo Min, and Taesoo Kim. Designing new operating primitives to improve fuzzing performance. In ACM Conference on Computer and Communications Security (CCS), 2017.
[43] Michał Zalewski. afl-fuzz: making up grammar with a dictionary in hand. https://lcamtuf.blogspot.de/2015/01/afl-fuzz-making-up-grammar-with.html. Accessed:2018-08-07.
[44] Michał Zalewski. american fuzzy lop. http://lcamtuf.coredump.cx/afl/. Accessed: 2018-08-07.

REDQUEEN: فازینگ با استفاده از تناظر ورودی با وضعیت

REDQUEEN: Fuzzing with Input-to-State Correspondence