سافران: فازینگ مبتنی بر گرامر تطبیقی برای تحلیل بدترین حالت

تست فاز (Fuzz testing) اخیراً با تلاش‌های قابل توجهی در این حوزه، در حال پیشرفت است. معمولاً، فازرها مجموعه‌ای از ورودی‌های اولیه (seed inputs) را دریافت کرده و با استفاده از تغییرات تصادفی، ورودی‌ها را به طور مداوم بهبود می‌بخشند تا با توجه به یک معیار هزینه، مانند پوشش کد برنامه، آسیب‌پذیری‌ها یا اشکالات را کشف کنند. بر اساس این روش، فازرها در تولید ورودی‌های بدون ساختار که پوشش بالا ایجاد می‌کنند، بسیار خوب عمل می‌کنند. با این حال، فازرها زمانی که ورودی‌ها ساختارمند هستند، مثلاً مطابق با گرامر ورودی باشند، کمتر مؤثر هستند.

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

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

نوآوری Saffron دو جنبه دارد: (1) با داشتن گرامر ارائه‌شده توسط کاربر، Saffron تلاش می‌کند کشف کند که آیا برنامه ورودی‌های غیرمنتظره‌ای خارج از گرامر ارائه‌شده را می‌پذیرد و در صورت وجود، گرامر را از طریق تغییرات گرامری اصلاح می‌کند. گرامر اصلاح‌شده به‌عنوان مشخصه ورودی‌های واقعی پذیرفته‌شده توسط برنامه عمل می‌کند. (2) بر اساس دستور زبان بهینه‌شده، ورودی‌های آزمایشی مشخص تولید می‌کند. این روند با در نظر گرفتن هر قانون تولید در دستور زبان با احتمال برابر برای استفاده در تولید ورودی‌های مشخص آغاز می‌شود. سپس به‌طور تطبیقی احتمال‌ها را در طول مسیر بازنگری می‌کند و احتمال‌هایی را که برای قوانینی استفاده شده‌اند که ورودی‌هایی تولید کرده‌اند که هزینه‌ای همچون پوشش کد یا هزینه تعریف‌شده توسط کاربر را بهبود می‌بخشند، افزایش می‌دهد. نتایج ارزیابی نشان می‌دهد که Saffron به‌طور قابل توجهی از روش‌های پایه‌ای پیشرفته موجود بهتر عمل می‌کند.

“Fuzz testing has been gaining ground recently with substantial e orts devoted to the area. Typically, fuzzers take a set of seed inputs and leverage random mutations to continually improve the inputs with respect to a cost, e.g. program code coverage, to discover vulnerabilities or bugs. Following this methodology, fuzzers are very good at generating unstructured inputs that achieve high coverage. However fuzzers are less e ective when the inputs are structured, say they conform to an input grammar. Due to the nature of random mutations, the overwhelming abundance of inputs generated by this common fuzzing practice often adversely hinders the effectiveness and efficiency of fuzzers on grammar-aware applications. The problem of testing becomes even harder, when the goal is not only to achieve increased code coverage, but also to nd complex vulnerabilities related to other cost measures, say high resource consumption in an application.

We propose Saffron an adaptive grammar-based fuzzing approach to effectively and efficiently generate inputs that expose expensive executions in programs. Saffron takes as input a user-provided grammar, which describes the input space of the program under analysis, and uses it to generate test inputs. Saffron assumes that the grammar description is approximate since precisely describing the input program space is often difficult as a program may accept unintended inputs due to e.g., errors in parsing. Yet these inputs may reveal worst-case complexity vulnerabilities.

The novelty of Saffron is then twofold: (1) Given the user-provided grammar, Saffron attempts to discover whether the program accepts unexpected inputs outside of the provided grammar, and if so, it repairs the grammar via grammar mutations. The repaired grammar serves as a speci cation of the actual inputs accepted by the application. (2) Based on the re ned grammar, it generates concrete test inputs. It starts by treating every production rule in the grammar with equal probability of being used for generating concrete inputs. It then adaptively re nes the probabilities along the way by increasing the probabilities for rules that have been used to generate inputs that improve a cost, e.g., code coverage or arbitrary user-de ned cost. Evaluation results show that Saffron signi cantly outperforms state-of-the-art baselines.”