Input Grammars Flashcards
(8 cards)
Erläutern Sie das Konzept des syntaxgesteuerten Testens (syntax-driven testing).
Das syntaxgesteuerte Testen (syntax-driven testing) bezieht sich auf die Verwendung von Grammatiken zur Generierung von Testeingaben. Anstatt zufällige Eingaben zu erzeugen, werden gültige Eingaben basierend auf einer spezifizierten Syntaxstruktur generiert. Durch die Verwendung von Grammatiken können wir sicherstellen, dass die generierten Eingaben den syntaktischen Anforderungen entsprechen und somit die Zuverlässigkeit und Effektivität des Tests erhöhen.
Wie können Inputs abgeleitet werden, die alle Produktionsregeln einer Grammatik abdecken?
Um Inputs abzuleiten, die alle Produktionsregeln einer Grammatik abdecken, können wir eine Syntaxanalyse der Grammatik durchführen und den Ableitungsbaum erstellen. Jede Produktionsregel wird durch den Ableitungsbaum repräsentiert. Durch systematisches Durchlaufen des Ableitungsbaums können wir Eingaben ableiten, die jede Produktionsregel mindestens einmal abdecken.
Erklären Sie die grundlegende Idee und Ableitungstrategien (Three-Phase, probabilistisch, Grammar Coverage) des Grammar-based Fuzzing.
Die grundlegende Idee des Grammar-based Fuzzing besteht darin, gültige Eingaben mithilfe einer Grammatik zu generieren. Es gibt verschiedene Ableitungstrategien, darunter:
- Three-Phase Derivation: Diese Strategie besteht aus drei Phasen - maximal, zufällig und minimal. In der maximalen Phase werden Produktionen mit maximalen Kosten angewendet, um eine größere Anzahl von Nonterminals einzubeziehen. In der zufälligen Phase werden Produktionen zufällig angewendet. In der minimalen Phase werden Produktionen mit minimalen Kosten angewendet, um den Ableitungsprozess abzuschließen.
- Probabilistic Grammar Fuzzing: Hier werden den Produktionen Wahrscheinlichkeiten zugeordnet, um die Generierung von Eingaben auf bestimmte Funktionalitäten zu lenken. Dies ermöglicht eine gezieltere Eingabegenerierung basierend auf den spezifischen Anforderungen des Tests.
- Grammar Coverage: Diese Strategie zielt darauf ab, alle Produktionsregeln systematisch abzudecken. Es wird überwacht, welche Produktionsregeln bereits verwendet wurden, und es werden bevorzugt noch nicht abgedeckte Produktionsregeln ausgewählt, um die Vielfalt der generierten Eingaben zu maximieren.
Wie können minimale und maximale Kosten für Symbole und Produktionsregeln einer gegebenen Grammatik berechnet werden?
Die minimalen Kosten für Symbole und Produktionsregeln einer gegebenen Grammatik können wie folgt berechnet werden:
- Die minimalen Kosten für ein Terminalsymbol aus der Menge T sind immer 0.
- Die minimalen Kosten für eine Produktionsregel berechnen sich als die Summe der minimalen Kosten aller enthaltenen Nonterminals auf der rechten Seite der Regel.
- Die minimalen Kosten für ein Nonterminal bestehen aus 1 plus den Kosten der “günstigsten” Produktionsregel, wobei die Kosten eines Nonterminals durch die Kosten der Nonterminals in den rechten Seiten der Produktionsregeln bestimmt werden, in denen es vorkommt.
- Wenn ein Nonterminal in einer rechten Seite einer Produktionsregel nicht vorkommt, wird sein Kostenwert als ∞ (unendlich) festgelegt, um eine potenziell unendliche Rekursion zu beschreiben.
Wie werden Wahrscheinlichkeiten von Produktionsregeln aus Ableitungsbaum/-bäumen abgeleitet?
Um die Wahrscheinlichkeiten von Produktionsregeln aus Ableitungsbaum/-bäumen abzuleiten, können wir die Anzahl der Vorkommnisse jeder Produktionsregel im Ableitungsbaum zählen und sie in Bezug zur Gesamtzahl der Produktionsregeln für das entsprechende Nonterminal setzen. Die Wahrscheinlichkeit einer Produktionsregel ist dann das Verhältnis der Anzahl der Vorkommnisse dieser Regel zur Gesamtzahl der Produktionsregeln des Nonterminals.
Wie kann ein Input mithilfe der Strategien minimale Kosten, maximale Kosten oder Grammar Coverage aus einer Grammatik abgeleitet werden?
Um einen Input mithilfe der Strategien minimale Kosten, maximale Kosten oder Grammar Coverage aus einer Grammatik abzuleiten, können wir den Ableitungsprozess entsprechend steuern:
- Bei der Verwendung der minimalen Kostenstrategie wählen wir bei jedem Schritt die Produktion mit den minimalen Kosten für das aktuelle Nonterminal.
- Bei der Verwendung der maximalen Kostenstrategie wählen wir bei jedem Schritt die Produktion mit den maximalen Kosten für das aktuelle Nonterminal.
- Bei der Verwendung der Grammar Coverage-Strategie überwachen wir die Abdeckung der Produktionsregeln und wählen für ein Nonterminal, das noch nicht abgedeckt wurde, bevorzugt eine unbehandelte Produktionsregel aus.
Erklären Sie die Kombination von Mutation und Grammar-based Fuzzing.
Die Kombination von mutational und grammar-based Fuzzing ermöglicht es uns, die Stärken beider Ansätze zu nutzen. Zunächst generieren wir gültige Eingaben mithilfe der Grammar-based Fuzzing-Technik, um eine gute Abdeckung der Syntaxstruktur zu erreichen. Anschließend können wir diese generierten Eingaben als Ausgangspunkte für mutational Fuzzing verwenden, indem wir Mutationen auf sie anwenden, um variierte Eingaben zu generieren. Durch diese Kombination können wir sowohl syntaktische als auch semantische Aspekte der Eingaben testen und potenzielle Schwachstellen in der Software identifizieren.
Erklären und verwenden Sie Grammar-based Mutations.
Grammar-based Mutations nutzen die Grammatik, um Mutationen auf Eingaben durchzuführen, die wahrscheinlich gültige Eingaben erzeugen. Zunächst wird eine Ableitung des Eingabe-Seed mittels Parsing erstellt, und dann werden Eingabefragmente extrahiert, die den Ableitungsbaum repräsentieren. Bei der Mutation wird ein zufällig ausgewähltes Fragment (Subtree des Ableitungsbaums) verändert. Das Fragment kann entweder durch ein entsprechendes Fragment aus den initialen Seeds ersetzt werden, das denselben Nonterminal-Knoten im Ableitungsbaum hat, oder es kann durch ein neu generiertes Fragment ersetzt werden. Alternativ kann das Fragment auch mit einem anderen Fragment desselben Baums ausgetauscht werden, solange beide Fragmente denselben Nonterminal-Knoten haben.
Durch die Verwendung von Grammar-based Mutations können wir sicherstellen, dass die generierten Mutationen immer noch den syntaktischen Anforderungen der Grammatik entsprechen. Dies erhöht die Wahrscheinlichkeit, dass die generierten Eingaben gültig sind und potenzielle Fehler in der Software effektiv aufdecken können. Indem wir die Mutationen gezielt auf die Grammatik anwenden, können wir auch die Testabdeckung verbessern und verschiedene Pfade und Funktionen der Software erreichen.
