Automatic generation of efficient fuzzers for games using libFuzzer and RuleBook

Fuzzing is the practice of repeatedly calling a program with semi-random inputs. It is a popular technique to discover bugs and vulnerabilities in software. However, fuzzing is not very practical when applied to input intensive programs such as games. A major factor in this is that games often have complex input patterns. They do not operate on a single large input but instead on a multitude of actions taken on them by the players. These actions must be taken according to some potentially complex rules, a particular action is only available on some game states and only with certain parameters. Therefore, even if a fuzzer knows all possible actions it can take on a game, generating valid sequences of actions can be a difficult task. An invalid sequence of actions does not make an inter- esting fuzz input, since the game is expected to fail with such an input. Consequently, frequently generating invalid sequences of actions decreases the fuzzer performance signif- icantly. Luckily, information about when an action can be taken and the constraints on its parameters should be available in the game logic, since the game needs to validate the actions players take and display error messages when invalid actions are taken. Therefore, compiler techniques should be able to extract and exploit this information already present in the game rules to produce high-quality fuzzers. In this work, we propose a method to generate fuzzers for games that utilize information about the dynamic availability of actions. We describe a technique to parse an arbitrary sequence of bytes as a sequence of actions on the game, then detail how we minimize the number of invalid actions in the parsed action sequences. We implement this tech- nique in the RuleBook language compiler. RuleBook is a DSL for describing games and the RuleBook compiler has the information relevant to our technique available at compile time. We measure the performance of four versions of fuzzers generated with this method, varying on how much information about the target game they utilize, along with two ver- sions of fuzzers generated using OpenSpiel’s game implementations. Using three sample games, we demonstrate that the fuzzers generated from RL descriptions have comparable performances with their OpenSpiel counterparts. Furthermore, we show that between RL fuzzers, versions that make the most use of the information RL exposes perform the best.

Il fuzzing è una tecnica che ha l’obiettivo di scoprire bug e vulnerabilità in un dato software, eseguendo tale software ripetutamente con input semi-casuali. È una tecnica popolare per scoprire bug e vulnerabilità nel software. Tuttavia, il fuzzing non è molto pratico se applicato a programmi ad alta intensità di input come i giochi. Un fattore importante è che i giochi hanno spesso modelli di input complessi. Non operano su un singolo input di grandi dimensioni, ma su una moltitudine di azioni eseguite dai giocatori. Queste azioni devono essere eseguite secondo regole potenzialmente complesse; una parti- colare azione è disponibile solo in alcuni stati del gioco e solo con determinati parametri. Pertanto, anche se un fuzzer conosce tutte le possibili azioni che può compiere su un gioco, generare sequenze di azioni valide può essere un compito difficile. Una sequenza di azioni non valida non costituisce un input interessante per il fuzz, poiché ci si aspetta che il gioco fallisca con tale input. Di conseguenza, la generazione frequente di sequenze di azioni non valide riduce notevolmente le prestazioni del fuzzer. Fortunatamente i prerequisiti nec- essari all’esecuzione di una azione dovrebbero essere già presenti nella logica del gioco, dato che il gioco deve validare le azioni eseguite dai giocatori e visualizzare messaggi di errore quando vengono eseguite azioni non valide. Pertanto, tecniche tipiche del campo dei compilatori dovrebbero essere in grado di estrarre e sfruttare queste informazioni già presenti nelle regole del gioco per produrre fuzzer di alta qualità. In questo documento proponiamo un metodo per generare fuzzer per giochi che utiliz- zano informazioni sulla disponibilità delle azioni dinamicamente. Descriviamo una tec- nica per analizzare una sequenza arbitraria di byte come una sequenza di azioni sul gioco, quindi spieghiamo come minimizzare il numero di azioni non valide nelle sequenze di azioni analizzate. Questa tecnica è stata implementata nel compilatore del linguaggio RuleBook. RuleBook è un DSL per la descrizione dei giochi e il compilatore RuleBook ha a disposizione le informazioni rilevanti per la nostra tecnica al momento della compi- lazione. Misuriamo le prestazioni di quattro versioni di fuzzer generati con questo metodo, che variano in base alla quantità di informazioni sul gioco di destinazione che utilizzano, insieme a due versioni di fuzzer generati utilizzando le implementazioni di gioco di Open- Spiel. Utilizzando tre giochi campione, dimostriamo che i fuzzer generati dalle descrizioni. RL hanno le stesse prestazioni delle loro controparti OpenSpiel. Inoltre, dimostriamo che tra i fuzzer RL, le versioni che sfruttano maggiormente le informazioni esposte da RL sono le più performanti.