## ShellFuzzer: Grammar-based Fuzzing of Shell Interpreters

Riccardo Felici , Laura Pozzi , Carlo A. Furia a a a a Faculty of Informatics, USI Università della Svizzera italiana, Lugano, Switzerland

## Abstract

Despite its long-standing popularity and fundamental role in an operating system, the Unix shell has rarely been a subject of academic research. In particular, regardless of the significant progress in compiler testing, there has been hardly any work applying automated testing techniques to detect faults and vulnerabilities in shell interpreters.

In our experimental evaluation, ShellFuzzer generated shell programs that exposed 8 previously unknown issues that affected a recent version of the mksh POSIX-compliant shell; the shell maintainers confirmed 7 of these issues, and addressed them in the latest revisions of the shell's open-source implementation.

To address this important shortcoming, we present ShellFuzzer: a technique to test Unix shell interpreters by automatically generating a large number of shell scripts. ShellFuzzer combines grammar-based generation with selected random mutations, so as to produce a diverse range of shell programs with predictable characteristics (e.g., valid according to the language standard, and free from destructive behavior).

Keywords: Shell interpreters, Testing, Fuzzing, Grammar-based

## 1. Introduction

With all its shortcomings, quirks, and obsolete features, the (Unix) shell remains a ubiquitous tool to program automation and administrative tasks. The shell's popularity and its role as a critical component underlying so many different computer systems entail that its security and reliability are paramount and, conversely, any vulnerability 1 may have a disproportionate harmful impact [12].

1 https://www.cve.org/CVERecord?id=CVE-2014-6271

Given the situation, it is somewhat surprising that the shell has been largely neglected as a research topic [21].

Combining three generators with different characteristics also helps ShellFuzzer produce oracles that capture some fundamental behavioral properties of each generated scripts. Precisely, one generator always produces valid shell scripts, whereas the two other generators always produce invalid shell scripts; correspondingly, the former's oracles assert that execution terminates without errors or abrupt termination, whereas the latter's require that the shell interpreter detects the invalid code and signals it with a suitable error message or return code. In addition to these generator-specific oracles, ShellFuzzer can also detect generic memory errors by deploying standard memory sanitizers during the testing process.

Motivated by the shell's practical importance, in this paper we present ShellFuzzer: a technique to test shell interpreters by automatically generating shell scripts with different characteristics. Similarly to what is done to test compilers of other languages (see Section 2.2), ShellFuzzer generates shell programs guided by a grammar of the shell language. In order to increase the diversity of the produced shell scripts, ShellFuzzer combines three separate generators , each using a different fragment of the POSIX shell syntax, and may also apply random mutations that introduce small syntactic errors into the produced scripts.

Since a shell interpreter usually has full access to the environment where the tests are run, an automatically generated shell script may accidentally disrupt the testing process by executing destructive operations (such as deleting large chunks of the file system). In order to minimize the chance of this happening, we carefully designed ShellFuzzer's generators so that they omit certain commands and features that are especially likely to introduce destructive behavior. While this somewhat restricts the range of programs that ShellFuzzer generates, our experiments suggest that it is a practical trade off because it retains a good effectiveness of testing while also avoiding time-consuming destructive crashes.

We implemented ShellFuzzer in a tool with the same name, and we evaluated its capabilities with experiments targeting open-source shell interpreters. ShellFuzzer managed to find 8 unique bugs in the mksh shell, 7 of which were confirmed by the shell maintainers (including 2 memory errors that also affected Bash). Our experiments also demonstrate that ShellFuzzer's generators are complementary, enabling it to detect different kinds of bugs.

Contributions. This article presents the following main contributions:

- · ShellFuzzer, an automated testing technique for POSIX shell interpreters.

- · A prototype implementation of the ShellFuzzer technique in a tool with the same name, which is publicly available. 2
- · An empirical evaluation of ShellFuzzer, demonstrating its capabilities of finding real bugs in shell interpreters, and how they compare to using general-purpose fuzzing techniques.

Organization. The rest of the paper is structured as follows. Section 2 summarizes the main approaches to interpreter/compiler testing, and the (little) related work targeting the shell. Section 3 presents the design of ShellFuzzer, motivated by the key challenges of effectively testing shell interpreters. Section 4 introduces the research questions that capture ShellFuzzer's practical capabilities, and outlines the experiments we ran to answer those questions. Section 5 presents the results of experiments, and summarizes the key observations about ShellFuzzer's capabilities. Section 6 concludes with a high-level summary of the paper's contributions, and an outline of future work.

## 2. Related Work

We summarize the main related work in two areas: shell languages and programming (Section 2.1), and the application of testing and analysis techniques to language interpreters and compilers (Section 2.2).

## 2.1. Shell Languages and Interpreters

A shell is a command-line interpreter that allows users to access the services of operating systems. This paper focuses on Unix shells, which have been historically prominent and remain widely available and used. The first Unix shell was developed over fifty years ago, as part of the Unix operating system [48]. As Unix gained broader popularity in the late 1970s, the Bourne shell ( sh ) 3 became the standard shell, followed by Bash 4 some ten years later - which quickly became the standard shell on Linux, where it remains ubiquitous. Other Unix shells of historical or practical importance include the Almquist shell ( ash ), 5 the Korn-

2 https://github.com/user09021250/shellfuzzer/

4 https://www.gnu.org/software/bash/

3 https://www.in-ulm.de/~mascheck/bourne/

5 https://www.in-ulm.de/~mascheck/various/ash/

Shell ( ksh ), 6 the Z shell ( zsh ), 7 and the C shell ( csh ). 8 The POSIX standard [27] includes the specification of a fundamental set of features that most shells are (at least partially) compliant with - even though each shell typically provides its own custom variants and extensions on top of a POSIX core.

There has also been research on improving the flexibility - e.g., [50] - and performance - e.g., [36, 29, 25] - of shells. Since such research is less relevant for the present paper we do not go into the details of these works, but we refer the interested readers to the recent discussion at HotOS [20, 21].

Despite its longevity and ubiquity - Bash even is in the top-50 of most popular programming languages 9 - the shell 'has been largely ignored by academia and industry' [21]: 10 there is little research work that targeted the rigorous analysis of shell scripts, even though it is generally known that writing shell scripts is error prone [16]. 11 Among the few exceptions, ABash [41] is a static analyzer for Bash scripts based on abstract interpretation; even though it does not provide soundness or completeness guarantees (due to the highly dynamic nature of the shell language), it was effective at finding bugs in shell scripts used in various open-source projects. CoLiS [28] is a formally verified interpreter for a core shell language, which has been used to find numerous bugs in Debian maintainer scripts [3]. Smoosh [19] is a formal, mechanized, executable semantics of the POSIX shell language, which can be used to rigorously evaluate POSIX conformance, as well as to discover conformance bugs in shell interpreters. NoFAQ [11] is a synthesis-based automated repair tools for command line interfaces (not specific to shell languages). Practitioners have also released several tools that help users write correct and maintainable shell scripts. For example, Modernish 12 is a library that provides safer, more convenient variants of some shell language features. ShellCheck 13 is a linter for shell scripts. ExplainShell 14 is a documentation system that can link the relevant information about each part of a shell command.

6 http://kornshell.com/

8 https://github.com/freebsd/freebsd-src/tree/main/bin/csh

7 https://www.zsh.org/

9 https://www.tiobe.com/tiobe-index/

11 https://mywiki.wooledge.org/BashPitfalls

10 As a result, several of the references in this section are URLs instead of refereed publications.

12 https://github.com/modernish/modernish

14 https://explainshell.com/

13 https://www.shellcheck.net/

## 2.2. Testing Interpreters and Compilers

Chen et al.'s recent survey of compiler testing [8] highlights several key challenges that also apply to interpreter testing, and provides a general motivation for our approach to shell interpreter testing. First of all, being able to reliably generate valid programs is a key challenge. To this end, the vast majority of approaches (e.g., [57, 43, 24]) are grammar-based, that is they use a formal grammar of (a fragment of) the input language to generate programs that are (syntactically) valid.

Eventhoughgrammar-basedapproaches are widespread for interpreter/compiler testing (especially in recent times), other testing techniques have also been successfully applied to these challenges [17, 46, 44]. In particular, combinations of random testing/fuzzing [59, 5, 38] with exploration heuristics remain widely used as they can still be highly effective [40, 37, 9]. For this reason, in Section 5.3 we will experimentally compare our ShellFuzzer tool to the modern, popular fuzzing framework AFL++ . In related efforts, fuzzing [42] and other test-input techniques such as symbolic execution [7] have been routinely used to test the reliability of operating-system command-line utilities or components [30].

Using a grammar to drive the generation of programs helps generate consistently valid programs; however, it may prevent a more effective exploration of the program space. Besides, sometimes being able to add a modicum of invalid, ambiguous, or undefined features is useful to increase the diversity of the generated programs, and to test the interpreter or compiler more thoroughly. To this end, several more recent approaches (e.g., [14, 33, 53, 10, 15, 55]) combine grammar-based generation with some form of mutation . Our ShellFuzzer also uses a combination of grammar-based generation and mutations in order to increase the diversity of shell scripts it can generate while retaining control on their validity and features.

Another key challenge of any kind of testing is generating oracles. Implicit oracles [1] - such as crashing oracles, or memory safety checkers [51] - are commonplace since they are always available. However, the correct behavior of an interpreter/compiler involves much more than just avoiding crashes or memory errors. Then, differential and metamorphic testing are commonly used techniques to automatically derive more expressive oracles in interpreter/compiler testing. In differential testing (e.g., [54, 34, 10, 43, 52]), one runs the same generated programs with multiple compilers (or the same compiler with different optimization options), and reports any inconsistency in how the compiled binaries execute. In metamorphic testing (e.g., [15, 45, 32]), one runs equivalent variants of the same program (for example, a program with and without dead

code) and checks whether they behave in the same way. As we'll explain in Section 3, ShellFuzzer uses a combination of implicit oracles (to detect basic memory errors) and automatically generated oracles linked to the characteristics of each generated shell program.

In terms of targeted languages , the vast majority of research on compiler/interpreter testing targets statically typed languages. Out of the 42 approaches listed in the survey [8]'s Table 2, only 4 target the well-known dynamic languages JavaScript [24, 47, 22, 2], Python and Ruby [2]. In the last few years, there has been more work on testing JavaScript engines [55, 56] and Python runtimes [35] - often using a tried-and-true combination of grammar-based generation and mutations. However, hardly any research work applied automated testing techniques to shell interpreters: Section 2.1 mentions the only exception we know of [19], which is based on a detailed mechanized semantics of the POSIX shell language. In this work, we want to apply grammar-based fuzzing techniques with the goal of detecting not only low-level memory and crashing bugs, but also logic bugs affecting specific functionality of a shell interpreter's implementation. Doing so involves several of the same challenges of compiler testing, while dealing with a highly-dynamic, idiosyncratic language. An additional challenge, specific to shells, is that a shell script can easily modify any parts of the environment that executes the test. In the next section, we explain how ShellFuzzer addresses these challenges.

## 3. Design and Implementation of ShellFuzzer

ShellFuzzer produces shell scripts using a grammar-based generator to test shell interpreters. As we discussed in Section 2, grammar-based generation is customary to test any programs that require complex, structured inputs - such as compilers and interpreters. In these scenarios, a grammar helps ensure that wellformed inputs are produced, so that the testing process can exercise the program under test more extensively (beyond just crashing it with an invalid input).

Afundamental challenge of grammar-based test generation - really, of all test generation techniques - is the so-called oracle problem: after generating a shell script, and running it with a shell interpreter, how do we determine whether the test passes (behaved as expected) or fails (revealed a potential error)? One common approach is using an implicit oracle, that is a condition that is generically applicable to every execution. For example, we could classify a test execution as a failure whenever it ends with a crash (the so-called crashing oracle), with a non-zero exit code, or prints some error message to standard error.

A challenge of using implicit oracles together with grammar-based generation is that an oracle's validity depends on the characteristics of the input program that is generated. For instance, if a syntactically incorrect program is rejected by an interpreter with a 'syntax error' message, we should consider the test passing, as this is exactly what it should do; in contrast, if a syntactically correct program is rejected by an interpreter with the same error message, we should consider the test failing, as the interpreter should be able to process programs that comply with the language syntax specification. Thus, there is a tradeoff between how restricted the grammar used for generation is and how reliably one can associate implicit oracles with a generated program. If the grammar is very constrained (for example because it only generates programs that are syntactically correct and free from any undefined behavior) it is easy to associate an implicit oracle (for example, termination without any error message); however, it will also be able to exercise less thoroughly the interpreter under test. In contrast, if the grammar is very flexible (for example, it generates all sorts of valid and invalid programs) it is more likely to trigger unexpected behavior in the interpreter; however, automatically determining whether a generated program is valid or invalid will be impossible in general.

Another, practical challenge of grammar-based generation of shell scripts is that such scripts can easily have destructive behavior (e.g., with commands such as rm ) since the interpreter that runs them has direct access to the system that also runs the testing infrastructure. This determines another trade-off between generality and feasibility: generating diverse shell scripts may improve testing coverage, but it is also likely to generate destructive scripts that disrupt the testing process. Sandboxing the execution environment guards against the worst consequences, but destructive-behavior scripts can still result in a major loss of testing time and results.

## 3.1. How ShellFuzzer Works

The design of ShellFuzzer addresses the aforementioned challenges by combining three different generators with complementary characteristics. Each generator uses a grammar that captures a different subset or variant of the POSIX shell standard [27]; it may also add random mutations to the scripts generated according to the grammar. Crucially, the grammar and mutations of each generator are chosen so that: i ) they determine programs with homogeneous characteristics, which all correspond to a certain expected behavior (e.g., error message) when executed by a shell interpreter; ii ) they are unlikely to generate programs with destructive behavior (e.g., they do not include destructive commands such as rm ,

Figure 1: Overview of how each generator of ShellFuzzer works. A generator produces test cases (shell scripts) with certain characteristics, and is associated with an automatic oracle that captures the fundamental expected behavior of a shell interpreter when it executes those test cases.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00433v1-figure-330f327a-4a87-4ebe-98b2-b299b8bd84b8.jpg)

or other combinations of features that are likely to lead to destructive behavior). Using multiple, complementary generators gives a fine-grained control on what kinds of scripts each generator produces (thus addressing the oracle problem) while still generating scripts with diverse characteristics (thus improving the thoroughness of testing and, potentially, the kinds of bugs that it can discover).

## 3.1.1. Generators V , I , and M I

Currently, ShellFuzzer includes the three generators described in Table 1:

Figure 1 illustrates how each generator is used in the testing process. A test case is a script, first generated according to the generator's grammar, and then also possibly mutated. Executing the script with a shell interpreter results in an exit code and in, possibly, some error message. The generator also automatically provides an oracle that asserts what the expected exit code is, and what error message is expected - depending on the characteristics of each generator's grammar and mutations. As usual, a test is passing /ok if the oracle's assertion holds; otherwise, the test is failing /remove . A failing test may be exposing an error (bug) in the shell interpreter.

Generator V uses a grammar that includes a significant subset of the POSIX standard. 15 This grammar should only produce scripts that are syntactically valid according to the standard; hence, when an interpreter runs a script produced by V , it should not give any syntax error message ( V 's oracle).

15 This grammar includes: variable assignments, arithmetic operations and expansions (e.g. v="${X}" , v="$((X+Y))" ), builtins and other commands (e.g., eval , exec , set ), function definitions, pipes, redirections, and other process directives.

̸

̸

| generator   | grammar                                  | mutations     | oracle ( expect )                | when test /remove                         |
|-------------|------------------------------------------|---------------|----------------------------------|-------------------------------------------|
| V           | POSIX-valid scripts                      | -             | ec = 0 , no syntax error message | shell rejects syntactically valid program |
| I           | POSIX-invalid scripts                    | -             | ec = 0 , error message           | shell accepts invalid program             |
| M I         | POSIX-valid scripts, nested conditionals | syntax errors | ec = 0 , error message           | shell accepts invalid program             |

Table 1: An overview of ShellFuzzer's generators. For each generator, what kinds of scripts its grammar generates, whether any mutations are applied, the associated automatic oracle (the shell interpreter behavior that we expect to observe when executing the scripts), and what it means when a test fails /remove (it is not consistent with the oracle).

Generator I uses a grammar that is based on a subset of the POSIX standard, which we manually modified to include deliberate well-formedness errors. This grammar should only produce scripts that are invalid according to the standard; hence, when an interpreter runs a script produced by I , it should give a syntax error message and terminate with a non-zero exit code ( I 's oracle).

Generator M I also generates invalid scripts, but starts from a small subset of the POSIX standard grammar that defines syntactically valid programs with nested conditionals; then, it applies random mutations to the innermost statements in the program, introducing syntax errors. 16 Thus, M I only produces scripts that are invalid according to the standard; when an interpreter runs a script produced by I , it should give a syntax error message and terminate with a non-zero exit code ( I 's oracle).

Wealsocurated the grammars of all generators to exclude destructive commands, and to achieve a good variety of generated programs in terms of size and used

16 Applying mutations on a grammar of valid programs makes the kinds of invalid programs that M I generates different from those that I generates.

1 for E9 in D a; do

2

Ldn="$((3&amp;4))"

&amp;&amp;

echo

"$Ldn";

3

done

4 exit 0;

(a) A POSIX-valid script, produced by gen- pression (line 5) produced by (c) A script with a syntax error (line 7) pro-

erator

V

.

5

[

-

done

func87();

6

exit

0;

(b) A script with an invalid ex-

generator

I

.

7

for

E9

in

D

a;

8

Ldn="$((3&amp;4))"

&amp;&amp;

echo

"$Ldn";

9

done

10 exit 0;

duced by generator

M

I

.

Figure 2: Three shell scripts generated by ShellFuzzer.

̸

| bug category   | failure                                                        | generators   |
|----------------|----------------------------------------------------------------|--------------|
| logic error    | ec = 0 , error message , no error                              | V            |
| logic error    | ec = 0 message                                                 | I , M I      |
| memory error   | address sanitizer error message memory sanitizer error message | V , I V , I  |
| memory error   |                                                                |              |

Table 2: Categories of bugs detected by ShellFuzzer. For each bug category, the failure that signals the bug, and which generators may find such bugs.

## features.

Figure 2 shows examples of scripts produced by the three generators. Generator V produces the script in Figure 2a, which is in fact syntactically valid according to the POSIX standard; therefore, executing the script should trigger no interpreter errors, and it should terminate by returning 0 as exit code. Generator I produces the script in Figure 2b, which includes the invalid test command [ -done func87(); - which is invalid because there is no closing square bracket and keyword done cannot be used in a test construct; therefore, executing the script should result in an error when evaluating the expression. Generator M I generates the script in Figure 2c, which is an invalid variant of the valid Figure 2a - invalid because it elided the required do keyword; therefore, executing the script should also result in an error when evaluating the loop. In this case, the invalid expression was generated by applying a mutation (removing do keyword) to the initially valid script of Figure 2a.

## 3.1.2. Bug Categories

The shell scripts generated by ShellFuzzer can reveal various categories of bugs in shell interpreters, as summarized in Table 2. As explained, each generator produces valid ( V ) or invalid ( I , M I ) scripts with an automatically generated oracle that expects the absence ( V ) or presence ( I , M I ) of errors (non-zero exit code, or

specific messages printed on standard output/error). Whenever there is a failure of one of such oracles, it may reveal a logic error - that is, an incorrect behavior of the shell interpreter. For example, if a POSIX-compliant script generated by V triggers a syntax error, it may indicate that the shell's parser has a bug.

In order to broaden the bug-detection capabilities of ShellFuzzer, we equipped its test-execution environment with address [49] and memory leak [51] sanitizers: whenever any of the scripts generated by ShellFuzzer executes, the sanitizers monitor the execution environment for various kinds of memory errors. Therefore, ShellFuzzer treats the sanitizers' error messages as additional failures, which may reveal various kinds of memory errors, including out-ofbound memory accesses (e.g., a buffer overflow), pointer errors (e.g., a nullpointer dereference), and memory leaks (e.g., when heap-allocated memory is not released after use).

## 3.2. Implementation Details

We implemented the ShellFuzzer technique in a prototype tool with the same name. At its core, ShellFuzzer uses AFL++ 's grammar mutator [26, 13] with the three grammars for V , I , M I that we designed as outlined in Section 3.1. In contrast to how it is used within a fuzzer like AFL++ , ShellFuzzer uses productions of the grammars that are free from random mutations. The only exception is generator M I , which may add single-location mutations to its generated scripts; however, we carefully designed M I 's mutation operators so that they only hamper the (syntactic) correctness of the generated scripts, and are unlikely to introduce destructive behavior.

ShellFuzzer's current implementation does not run sanitizers with generator M I (whereas it runs them with V and I ). This is just a simplification of the implementation: V and I already cover a broad spectrum of behaviors that may trigger memory errors, whereas M I mainly brings additional diversity to detect different kinds of logic bugs.

ShellFuzzer is written in a combination of C, C++, Python and shell scripts. It includes functions to prepare the environment and compile the grammars, an interface to AFL++ 's grammar mutator, an execution engine that orchestrates the testing process, as well as logging and post-processing utilities that are written in Python and shell scripts.

## 3.2.1. Parameters

Users can customize ShellFuzzer's runs by setting the three main parameters listed in Table 3.

Table 3: Main parameters used to configure ShellFuzzer's executions

| parameter   | description                                 | generators   |
|-------------|---------------------------------------------|--------------|
| size        | approximate size (LOC) of generated scripts | V , M I      |
| procs       | number of parallel shell processes          | V , I , M I  |
| time        | time allotted to the generator              | V , I , M I  |

size : the approximate size, in lines of code, of each generated script. The size is 'approximate' because AFL++ 's grammar mutator, on top of which ShellFuzzer is built, does not enforce strict constraints on the generated program size. Also, parameter size is not applicable to generator I , since the sizes of the produced test cases are already constrained by the grammar itself.

procs : the number of parallel shell processes that will run the generated scripts. In order to improve throughput, ShellFuzzer runs parallel instances of the generators, whose produced scripts are fed into parallel instances of the shell interpreter under test.

time : the overall time available for generating shell scripts, executing them, and collecting the results.

Users can set these parameters according to the goals of their testing campaign. In Section 5.4, we will discuss how we empirically selected ShellFuzzer's parameters to use in the bulk of our experimental evaluation of its effectiveness.

## 3.2.2. Script Size Reduction

As we'll demonstrate in Section 5, ShellFuzzer may generate scripts of nontrivial size - up to hundreds of lines of code. While a variety in the sizes of generated scripts improves metrics such as coverage, whenever a script triggers a failure it has to be inspected to determine whether the failure actually corresponds to a genuine bug. In such cases, we would ideally only have to inspect scripts in reduced form: as small as possible, while still triggering the same failure. To this end, we added to ShellFuzzer an optional script reduction 17 step.

17 While it is customary to use the term 'minimization', our algorithm is not guaranteed to find the smallest possible equivalent test case - even though it is quite effective in practice.

procedure reduce ( script , oracle , n ) → reduced script

```
    procedure reduce (script, oracle, n) -> reduced script

    if size(script) = 1 then
        {script cannot be split into smaller chunks}
        return  script
    else
        {split script into n chunks}
        chunks <- split(script,n)
        for chunk in chunks do
            {remove chunk from script}
            shrink <- script - chunk
            if oracle(shrunk) = oracle(input) then
                {shrunk preserves input's behavior according to oracle}
                {try to further reduce it}
                return  reduce(shrunk, oracle, max(n - 1, 2))
            end if
        end for
        {none of the shrunk scripts preserves input's behavior}
        if n < size(script) then
            {try using smaller chunks}
            return  reduce(script, oracle, min(2 × n, size(script)))
        else
            {smallest chunk size reached: stop}
            return  script
        end if
    end if

Figure 3: Delta-debugging algorithm used to reduce scripts generated
FUZZER.
```

Figure 3: Delta-debugging algorithm used to reduce scripts generated by ShellFuzzer.

As customary in test-case generation [31], we used the delta debugging [58] algorithm shown in Figure 3. Our implementation uses a function split that is aware of the syntactic structure of shell scripts. Furthermore, for invalid scripts generated by I and M I , the split function also avoids removing parts of any syntactically invalid element; and, for valid scripts generated by V , it avoids splitting the statement that triggers the (unexpected) failure. Consequently, a script produced by a certain generator preserves its characteristics (valid or invalid by construction) even after reduction. Figure 4 shows an example of reducing a

Figure 4: Three final steps of the Figure 3's script reduction procedure, demonstrated on a program generated by V . The chunk of code that is removed in each reduction step is highlighted.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00433v1-figure-ad1edc14-8deb-4f8e-8475-f18f587966ab.jpg)

script generated by V . 18 The script was originally over 500 lines of code, and triggered a failure at line 6; the reduction algorithm shrunk it down to a single failing assignment. As you can see in Figure 4, split looks for chunks that consist of complete statements, and does not further break down the failure-inducing statement at line 6.

## 4. Experimental Design

Wedesigned an experimental evaluation of ShellFuzzer to address the following research questions:

RQ1: Is ShellFuzzer effective in detecting bugs in shell interpreters? This research question investigates ShellFuzzer's fundamental effective- ness as a bug-finding tool for shell interpreters.

Which categories of bugs can ShellFuzzer detect?

RQ2: This research question looks into the categories of shell-interpreter bugs detected by ShellFuzzer, and into which generators are more/less effective.

RQ3: How does ShellFuzzer compare with the state-of-the-art fuzzing testing framework AFL++ ?

This research question compares ShellFuzzer to using an off-the-shelf fuzzer like AFL++ (also equipped with a grammar to guide the generation of meaningful shell scripts). Among the many fuzzing frameworks that are available, we consider AFL++ [18] because it is one of the most actively

18 This is one of the memory leaks detected by V .

maintained, recent forks of the influential AFL, 19 which implements several improvements, variants, and extensions that have been proposed in the literature.

RQ4: What is an effective set of parameters to configure ShellFuzzer? This research question investigates the tuning of ShellFuzzer's configuration parameters (described in Section 3.2), and determines a suitable configuration that was used in all other research questions.

The rest of this section describes the experiments we designed to answer each research question.

## 4.1. Shell Interpreters

Each experiment ran in a virtual machine with one core and 15 GB of RAM and Ubuntu 20.04.

Even though our experiments focused on mksh , the shell scripts produced by ShellFuzzer work equally well as tests of other shell interpreters. Whenever ShellFuzzer generated a script that resulted in an alert when executed by mksh , we ran the same script also with other common shell interpreters (Bash, KornShell, and Dash) to ascertain whether they are also affected by the same issue. Section 5 will also report any such cases of warning replicated with other shells.

As shell interpreters, we primarily targeted version R59 of the POSIX-compliant shell mksh . 20 mksh is a modern variant of KornShell ( ksh ), originally developed for the MirOS BSD system. Compared to other, longer-running POSIXcompliant shell interpreters such as Bash, the C shell, and the original Korn Shell, mksh is less widely used and is actively maintained by a single programmer; 21 thus, it is a promising target for discovering new, previously unknown bugs and issues through fuzzing. mksh is also the default shell on Android, and as such it is an important component of countless mobile devices; thus, its correctness and security also indirectly affect the robustness of these systems - which further motivates our effort to automatically identify bugs and vulnerabilities.

## 4.2. Parameters

Table 4 shows the default parameters we used in all experiments (except those for RQ4). We selected these parameters empirically, as a result of the experiments

19 https://lcamtuf.coredump.cx/afl/

21 https://launchpad.net/~mirabilos

20 MirBSD: mksh - the MirBSD Korn Shell: http://mirbsd.de/mksh

Table 4: Parameter values used in the main experiments with ShellFuzzer. Parameter time is measured in hours, and refers to when the three generators are used sequentially within the same 12-hour run.

|           | parameters   | parameters   | parameters   |
|-----------|--------------|--------------|--------------|
| generator | size         | procs        | time [h]     |
| V         | 500          | 100          | 4            |
| I         | -            | 1000         | 6            |
| M I       | 50           | 1000         | 2            |

## we ran to answer RQ4 (see Section 5.4).

Since ShellFuzzer's generators build scripts with complementary characteristics, in most experiments we ran all three generators sequentially V , I , and M I within the same 12-hour budget, and collected all results. Table 4 shows the amount of time given to each generator within a 12-hour run (which we also determined empirically when answering RQ4).

Each experiment ran ShellFuzzer or, in RQ3, AFL++ for a total of 12 hours. To account for random fluctuations, we repeated each experiment three times, and report average values.

## 4.3. Measures

In each experiment, we executed all scripts generated by ShellFuzzer with the mksh shell interpreter instrumented with address and memory sanitizers. For each script execution, we logged:

generator: the generator that produced the script alert: whether the execution raised an alert : either a failure of the generator's built-in oracle, or a sanitizer warning (see Table 2)

size: the script's size, in lines of code

If a script execution raises an alert, we also save the script itself for post processing. Furthermore, we also record the maximum branch coverage reached during the whole experiment.

## 4.4. Post processing

After an experiment concludes, we automatically group all saved scripts that triggered alerts : any two alerts belong to the same group if and only if they were produced by the same generator, they trigger the same oracle failure or sanitizer warning, and determine the same shell exit code and error message. 22

For all unique alerts that we classified as true positives, we also prepared a bug report and submitted it to mksh 's maintainers. Following standard guidelines [60], a bug report includes: i ) the source code of the bug-revealing shell script; ii ) information about the hardware, operating system environment, and shell interpreter used in our experiments that revealed the bug; iii ) a short description of the expected script behavior, in contrast to the (unexpected) behavior we observed in the experiments; iv ) detailed steps to reproduce the observed behavior (including the stack trace in case of a crashing bug); v ) if possible, a brief discussion of how to address the issue, such as a suggested code or documentation change. To avoid publicly disclosing potential security issues, we submitted all bug reports as encrypted emails sent directly to the maintainers of the shell interpreter. If the maintainers acknowledged the bug report as a genuine issue that should be fixed, we classify the corresponding bug as confirmed . Confirmed bugs are the gold standard for the effectiveness of a test generation technique, as they represent authentic software defects.

After this grouping of alerts into unique alerts, we take the smallest script in each group and reduce its size as described in Section 3.2.2. Finally, we manually inspect each unique, reduced alert, in order to determine whether it corresponds to a genuine bug (i.e., a true positive). During the manual inspection, we first of all determine whether the script is indeed POSIX-compliant (if produced by generator V ) or invalid (if produced by generators I or M I ); then, we ascertain that it does trigger unexpected behavior according to the standard.

## 5. Experimental Results

This section presents the experimental results that pertain to each research question.

22 For invalid scripts produced by generators I or M I , the 'error message' may be a sanitizer warning, or denote the absence of an expected shell interpreter error.

|          | generators     | generators   | generators   | generators   | generators   | generators   | generators   | generators   |
|----------|----------------|--------------|--------------|--------------|--------------|--------------|--------------|--------------|
|          |                | + I + M I    | + I + M I    | V            | V            | M I          | M I          | I            |
| category | category       | V sum        | avg          | sum          | avg          | sum          | avg          | sum          |
|          | alerts         | 203460       | 67820.0      | 930          | 310.0        | 4339         | 1446.3       | 401583       |
|          | unique         | 11           | 10.3         | 2            | 2.0          | 4            | 3.7          | 8            |
|          | true positives | 8            | 8.0          | 2            | 2.0          | 1            | 1.0          | 7            |
|          | confirmed      | 7            | 7.0          | 2            | 2.0          | 1            | 1.0          | 6            |
|          | alerts         | 203104       | 67701.3      | 0            | 0.0          | 4339         | 1446.3       | 401497       |
|          | unique         | 9            | 8.3          | 0            | 0.0          | 4            | 3.7          | 6            |
|          | true positive  | 6            | 6.0          | 0            | 0.0          | 1            | 1.0          | 5            |
|          | confirmed      | 5            | 5.0          | 0            | 0.0          | 1            | 1.0          | 4            |
|          | alerts         | 356          | 118.7        | 930          | 310.0        | 0            | 0.0          | 86           |
|          | unique         | 2            | 2.0          | 2            | 2.0          | 0            | 0.0          | 2            |
|          | true positive  | 2            | 2.0          | 2            | 2.0          | 0            | 0.0          | 2            |
|          | confirmed      | 2            | 2.0          | 2            | 2.0          | 0            | 0.0          | 2            |
| coverage | coverage       | 37.9 %       | 37.9 %       | 29.7 %       | 29.7 %       | 27.6 %       | 27.6 %       | 37.3 %       |

Table 5: Effectiveness of ShellFuzzer. The table reports the total number sum over three repeated 12-hour runs, and average avg per repeated run of alerts raised by ShellFuzzer, unique alerts, true positive bugs, and bugs confirmed by the shell maintainers. The three row groups report data for all alerts, as well as the breakdown into logic and memory alerts (identified as described in Section 3.1). The four column groups report data for all three generators used sequentially ( V + I + M I ), as well as for each generator used individually in a run. Finally, the bottom row reports the maximum branch coverage reached during any run.

## 5.1. RQ1: Effectiveness

In our experiments, the shell scripts generated by ShellFuzzer raised a large number of alerts; several of them correspond to true positives that indicate bugs or other kinds of issues in the shell interpreters. As shown in Table 5, in the experiments where ShellFuzzer ran all three generators sequentially ( V + + I M I ), ShellFuzzer triggered over 200 000 alerts; after post processing (Section 4.4), these reduce to 11 unique alerts , 8 of which correspond to true positives - all but one confirmed by the maintainers of mksh as genuine issues of the shell in-

Figure 5: Out of all 8 unique true positive alerts observed in ShellFuzzer's experiments, which were raised by scripts generated by each of the generators V , I , and M I .

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00433v1-figure-1f43d612-9cf7-4ed5-8b4e-7581787a5e58.jpg)

## terpreters that should be fixed. 23

In Table 5, the total number of unique, true positive, and confirmed alerts is usually close - often identical - to the average number per run. This means that the same issues are often revealed in most - or all - of the repeated runs; it indicates that ShellFuzzer is robust as a test generator: even though its generation process is randomized, it often manages to perform a broad, repeatable search if it is allowed to run for several hours.

It is typical for such experiments that only a small number of unique alerts emerge from a much larger number of (raw) alerts. Thus, ShellFuzzer's automatic grouping of alerts into unique alerts (which, in turn, is based on the oracles that each generated test script is equipped with) is crucial to reduce the amount of output that the user needs to look at. Generating a much larger number of scripts still remains useful to increase the coverage of the testing process: a coverage of over 30% indicates that ShellFuzzer exercised a considerable portion of the shell interpreter under test, which bolsters the significance of the issues it exposed.

shift

-- -0000000000000000000000000000000000;

read

VAR

&amp;&amp;

echo fi

;

(a) A script raising a spurious alert.

(b) A script raising a true positive alert, not confirmed by developers.

Figure 6: Two shell scripts generated by ShellFuzzer that raised unique alerts.

23 We thank Thorsten Glaser, the maintainer of mksh , for his kind availability and promptness in answering and addressing our issue reports.

## 5.1.1. Precision

ShellFuzzer's overall precision is 72%, that is the fraction 8 11 / of unique alerts that were confirmed as true positives. Given that the absolute number of unique alerts is modest, this precision level is adequate, as it does not require the user to inspect and identify a large number of false positives.

Figure 6b shows the only case of script that raised a true positive alert, which was not confirmed by the maintainers of mksh . The script was generated by I : according to the POSIX standard, the argument of shift 'shall be an unsigned decimal integer', 24 and hence the signed -0 should be rejected. However, shells usually accept a signed zero as equivalent to an unsigned one; according to the maintainers of mksh , this behavior has been standard in Unix shells; thus, they decided against disallowing this behavior even if it is not strictly POSIXcompliant.

In the few cases where ShellFuzzer generated false positives, they were usually due to unusual combinations of syntactically invalid constructs that unexpectedly resulted in valid programs. For example, Figure 6a shows a script that raised a unique alert that is false positive. The script was generated by M I , which removed parts of a conditional block, leaving only the fi closing keyword. The mutation removing parts of a conditional is supposed to render the script invalid ; however, Figure 6a's script is perfectly valid, since fi is simply interpreted as a string printed by echo . Since the script was generated by M I , its oracle expects an error; the script executes correctly, and hence it results in an alert; but since the script is actually valid, the alert is spurious (false positive).

These examples demonstrate a tension between standard-compliance and legacy behavior that is common in all widely-used real-world languages: if a certain behavior has been historically allowed, maintainers are reluctant to disallow it (even when it violates a standard) because doing so would introduce - with no apparent advantage - unexpected errors (or undefined behavior) in programs that users would consider valid.

## 5.1.2. Generators

If we break down ShellFuzzer's results by generator (middle and right columns in Table 5) we notice that the three generators are mostly complementary , in that each of them leads to the discovery of unique alerts that the other generators did not detect. However, the generators are not perfectly complementary: as

24 https://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3 \_ chap02.html#shift

shown in Figure 5, some unique alerts can be triggered by the scripts produced by different generators. This is not surprising given that: i ) all experiments use sanitizers, and hence every generators may be able to trigger (the same) memory errors (this is the case, in particular, of the two memory errors detected by both I and V ); ii ) generators I and M I both generate invalid shell scripts, which may have the same source of invalidity. Even though it may seem that generator V 's effectiveness is subsumed by generator I 's, generator V 's detection of memory errors behaved more robustly in our experiments: only V detected the two errors in all repeated runs (in Table 5, sum = avg for V but not for I ).

Remember that Table 5's results under columns V , I , and M I are not merely a breakdown of those under column V + I + M I , but correspond to experiments where we ran each generator alone for the whole allotted time. It is interesting that no generator discovered issues when run in isolation that it did not also discover when sharing the testing time with the other generators. This is additional evidence that ShellFuzzer's runs are generally robust, and its three generators are largely complementary and thus are best run together.

The generators also differ in the coverage they achieve, with I reaching the highest coverage and M I the lowest. Indeed, M I produces scripts with a fairly predictable, constrained structure, that mainly differ in size, and in the mutations they include; this restricts the coverage it obtains. In contrast, I produces scripts with a variety of invalid syntactic features, which leads to exercising a range of error-checking code in the shell interpreters.

|                |          | generator   | generator   | generator   |
|----------------|----------|-------------|-------------|-------------|
| scripts        | reduced? | V           | M I         | I           |
| all            | /remove  | 694         | 56          | 5           |
| alerts         | /remove  | 768         | 2           | 2           |
| true positives | /remove  | 566         | 1           | 4           |
|                | /ok      | 4           | 1           | 1           |

Table 6: Average size, in lines of code, of the scripts generated by ShellFuzzer in RQ1's experiments: all scripts, those raising alerts , and the alerts confirmed as true positives (both before /remove and after /ok size reduction).

(a) Distribution of sizes before reduction.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00433v1-figure-3a526b17-fb51-4e6f-9b7a-49d77dd9207f.jpg)

Figure 7: Distribution of the size of all script generated in RQ1's experiments that raised true positive alerts, before and after the reduction step described in Section 3.2.2.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00433v1-figure-e0d5d88f-e93b-4680-b6ce-cc943c11d7d8.jpg)

## 5.1.3. Size

As shown in Table 6, the three generators differ significantly in the size of scripts they generate. Generator V produces by far the largest scripts, usually around 600-700 lines of code; generator I produces the smallest scripts, usually around 5 lines of code; generator M I is in between, as it usually produces scripts of around 50-60 lines of code.

Table 6 and Figure 7 also show that ShellFuzzer's post processing (Section 4.4) is crucial to produce scripts of smaller size, which can easily be manually inspected. The script reduction algorithm described in Section 3.2.2 is essential for scripts generated by V , which it shrinks by two order of magnitudes. In contrast, it is less essential for scripts generated by M I and I , where the smallest script in each equivalence group is usually only a few lines long; however, the reduction algorithm manages to shrink these even further, bringing them down to a single line of code that clearly highlights the root cause of the bug in each case.

In our experiments, the scripts produced by ShellFuzzer detected 7 confirmed issues in the mksh shell interpreter, while achieved a coverage of over 30%. ShellFuzzer's generation is often robust (the same issues are detected in different repeated runs). ShellFuzzer's three generators V , I , and M I are largely complementary, as they revealed different issues.

```
                                                                                                                                                                                                        hb=0;                                                                                                                                                                                                       
                                                                                                                                                                                                        if [ true ]; then                                                                                                                                                                                                        #[                                                                                                                                                                                                        b=0;                                                                                                                                                                                                     #[ 
                                                                                                                                                                                                      #[
                                                                                                                                                                                                       # 
                                                                                                                                                                                                     
  #[                                                                                                                                                                                                     #[  #[                                                                                                                                                                                                    
   #[                                                                                                                                                                                                    #[  #                                                                                                                                                                                                       

                                                                                                                                                                                                        //[                                                                                                                                                                                                      
#[                                                                                                                                                                                                       #]
                                                                                                                                                                                                      

                                                                                                                                                                                                       //
```

(a) A POSIX-valid script, produced by (b) A script with an invalid expression (c) A script with a syntax error (line 23) generator V . (line 17) produced by generator I . produced by generator M I .

Figure 8: Three shell scripts generated by ShellFuzzer that trigger confirmed bugs.

## 5.2. RQ2: Categories of Bugs

As we discussed in Section 3.1, ShellFuzzer's generators are specifically designed to detect different kinds of logic errors in shell interpreters. Indeed, Table 5 shows that the vast majority of alerts, and 9 out of the 11 unique alerts, raised in our experiments correspond to logic errors. Despite its focus on logic errors, ShellFuzzer also detected 2 unique memory errors, both confirmed by developers. This suggests that running sanitizers while executing ShellFuzzer's scripts is worth the (minor) performance overhead, since it broadens the number and kinds of errors that ShellFuzzer can detect.

Interestingly, generator V only led to discovering memory errors. In other words, none of the valid scripts it generated were rejected by the shell interpreters. For instance, V produced the script in Figure 8a, which executes without explicit error but triggers one of the 2 confirmed unique memory errors we found in our experiments. The memory errors exposed by generator V were also the only errors in our experiments that also affected version 5.0 of Bash - they

In terms of generators, all logic errors were detected by programs produced by generators I and M I . For instance, I produced the script in Figure 8b, which exposes one of the 5 confirmed unique logic errors we found in our experiments. Figure 8b's script is invalid because it includes twice the expression ((3+"i")) (invalid because it combines a number and a string in an arithmetic expression); mksh , however, only gives a warning that does not prevent execution from continuing after evaluating the invalid expression. Figure 8c shows another example of a script - produced by M I - that exposed a confirmed unique logic error. Also in this case, mksh executes the program without errors or warnings, even though expression ((3+3 is clearly invalid because its parentheses are not properly balanced.

have been fixed since version 5.2. 25 In all, generator V remains useful to exercise the shell interpreters in different ways, as well as to improve coverage; and further demonstrates that ShellFuzzer's three generators have complementarity capabilities.

In our experiments, ShellFuzzer was especially effective in detecting 5 confirmed logic errors, but could also identify 2 confirmed memory errors that affected both mksh and bash . Using all generators V , I , and M I increases the variety of bugs that ShellFuzzer reveals.

## 5.3. RQ3: Comparison

We compare ShellFuzzer to the state-of-the-art fuzzer AFL++ 26 on testing the mksh shell interpreter.

## 5.3.1. Setup

To make the comparison fair, we equip AFL++ with its grammar mutator [26] and the same grammar of valid POSIX shell scripts used by generator V . Even though ShellFuzzer's implementation also uses AFL++ 's grammar mutator in its implementation, the scripts produced by AFL++ and ShellFuzzer's V will be in general quite different. In AFL++ , the fuzzing engine may always introduce some random, unconstrained mutations on top of the seed scripts produced according to V 's grammar; therefore, there is no guarantee that any of the scripts produced by AFL++ with the grammar mutator are valid.

AFL++ is a highly configurable tool that supports different search strategies; we consider three different configurations A , A , A 1 2 3 for it. The configurations all use the same afl-clang-fast with the grammar mutator as described above but with different scheduling strategies: 27

Consequently, we cannot associate a 'validity' oracle to the shell scripts produced by AFL++ , since we do not know which are valid and which invalid according to the POSIX standard. As it is customary in fuzzing campaigns, we simply use memory sanitizers to detect memory-related errors that are revealed when running such scripts.

A 1 uses the default exponential-power schedule fast [6];

25 In contrast, all logic errors found in our experiments only affected mksh .

27 https://aflplus.plus/docs/fuzzing \_ in \_ depth/

26 Our comparison targeted AFL++ version 4.05.

A 2 uses the exploration-based constant-power schedule explore ;

A 3 uses the quadratic-power schedule quad .

Consistently with ShellFuzzer's setup, each experiment with AFL++ ran one of its configuration for 12 hours on mksh and was repeated three times. We report the number of unique sanitizer warnings raised during the experiment, as well as the coverage of the shell interpreter.

## 5.3.2. Crashes

Another important consequence of the fact that AFL++ may introduce arbitrary mutations - as opposed to the constrained generation performed by ShellFuzzer- is that running a shell script produced by AFL++ may incur a destructive crash of the environment running the shell interpreter. Unlike a 'benign' crash, which simply results in an early termination of the interpreter process, a destructive crash compromises the environment to the extent that the testing process cannot continue - for instance, by deleting the whole file system including the interpreter binaries.

We took some basic measures to reduce the impact of destructive crashes; in particular, we flagged as read-only all parts of the file system except the testing directory (where the scripts to be executed are stored). Even though one could try to implement more sophisticated mitigation strategies, destructive crashes are always a possibility lest one precisely constraints the kinds of mutations that a generator can introduce (as we did with ShellFuzzer's generators).

When a destructive crash occurs during an experiment, we collect any information about the experiment that survived the crash, we reset the environment, and then restart the experiment using any remaining time in the 12-hour slot. Since each destructive crash requires a manual intervention, such crashes can severely worsen the overall efficiency of testing; even though we did not measure the time taken by such manual restarts, and report the results as if manual resets where instantaneous, we stress that they can be a significant hindrance in practice.

## 5.3.3. Comparison Results

Table 7 displays the main results of the comparison between ShellFuzzer and the three AFL++ configurations A , A , A 1 2 3 . The numbers for ShellFuzzer refer to the same experiments described in greater detail in Section 5.1 and Section 5.2.

In terms of overall detected errors, ShellFuzzer found 7 unique confirmed errors (5 logic errors and 2 memory errors), whereas AFL++ found 4 (all memory

Table 7: Comparison between ShellFuzzer (sf) and three AFL++ configurations ( A 1 , A 2 , A 3 ). The table compares the number of destructive environment crashes, the number of 'benign' interpreter crashes ( crashes ), the branch coverage of the shell interpreter, and the number of unique confirmed bugs ( all categories, as well as the breakdown into logic and memory errors). Each group of columns reports the maximum, average (mean), and minimum values per repeated run, or total in all runs.

|             |        | sf      | A 1     | A 2     | A 3     | sf      | A 1     | A 2     | A 3     | sf      | A 1     | A       | 2 A 3   |
|-------------|--------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|---------|
|             |        | maximum | maximum | maximum | maximum | average | average | average | average | minimum | minimum | minimum | minimum |
| destructive | #      | 0       | 0       | 8       | 4       | 0       | 0       | 3       | 1       | 0       | 0       | 1       | 1       |
| crashes     | #      | 155     | 238     | 200     | 156     | 119     | 136     | 81      | 91      | 92      | 83      | 0       | 4       |
| coverage    | %      | 38      | 44      | 43      | 40      | 38      | 42      | 37      | 37      | 37      | 41      | 29      | 33      |
|             |        | total   | total   | total   | total   | average | average | average | average | minimum | minimum | minimum | minimum |
| confirmed   | all    | 7       | 4       | 4       | 4       | 7       | 4       | 3       | 2       | 7       | 4       | 2       | 0       |
| confirmed   | logic  | 5       | -       | -       | -       | 5       | -       | -       | -       | 5       | -       | -       | -       |
| confirmed   | memory | 2       | 4       | 4       | 4       | 2       | 4       | 3       | 2       | 2       | 4       | 2       | 0       |

errors). As expected, ShellFuzzer's main strength is not in detecting memory errors; however, it makes up for it with its unique capability of detecting logic errors.

In terms of coverage, ShellFuzzer trails behind AFL++ by 2-6 percentage points (depending on the configuration). Given that achieving a high coverage is not a main target of ShellFuzzer's design, the gap is arguably to be ex-

Whereas 'benign' crashes occur with similar frequency both with ShellFuzzer and with AFL++ , destructive crashes only occur with AFL++ . Actually, AFL++ configuration A 1 did not incur any destructive crashes in our experiments; however, there is no guarantee that it is immune from such crashes if one tried longer, or just repeated, testing sessions. 28 In contrast, a valuable advantage of ShellFuzzer is that it was constrained to avoid destructive crashes by design which significantly helps the consistency and repeatability of a testing campaign.

28 Wealso noticed that even the 'benign' crashes produced during experiments with A 1 usually had a bigger impact on the integrity of the environment than those occurred with ShellFuzzerfor example, by changing AFL++ configuration files or environment variables.

Figure 9: Coverage achieved by ShellFuzzer and by AFL++ 's configurations A , A , A 1 2 3 . Each colored ribbon covers the range of coverage values reached in any experiment with that tool over the 12-hour time limit.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00433v1-figure-f29b7436-2920-4b09-89e9-28cb14b312dd.jpg)

pected and not tremendously consequential. Furthermore, ShellFuzzer's generation constraints (that avoid destructive crashes and enable detecting logic errors) inevitably somewhat reduce the reach of its exploration of the shell interpreter under test.

Figure 9 illustrates how the coverage evolves over time in each experiment. ShellFuzzer, as well as AFL++ in configurations A 2 and A 3 , reach a level of coverage close to the run's maximum within the first hour; then, coverage keeps increasing but much more slowly. An important difference, however, is that ShellFuzzer's coverage is always monotonically increasing; in contrast, it periodically resets to zero in AFL++ 's experiments whenever a destructive crash occurs - given that the experiment has to restart from scratch. AFL++ 's configuration A 1 is different still: while it does not have destructive crashes, its coverage grows kind of slowly and is well below ShellFuzzer's up until the last hour of experiments, when it grows again prominently and even 'overtakes' ShellFuzzer in some repetitions. We could not find a simple explanation for this peculiar be-

| generator   | V   | V   | V    | I   | I   | I    | M I   | M I   | M I   |
|-------------|-----|-----|------|-----|-----|------|-------|-------|-------|
|             | s   | m   | l    | s   | m   | l    | s     | m     | l     |
| size        | 10  | 500 | 2500 | -   | -   | -    | 50    | 50    | 250   |
| procs       | 10  | 100 | 1000 | 10  | 100 | 1000 | 10    | 1000  | 1000  |
| coverage    | 29% | 29% | 29%  | 34% | 35% | 35%  | 25%   | 27%   | 25%   |

Table 8: Parameter tuning of ShellFuzzer. For each generator, we considered three combination of values small, medium, and large for its parameters of script size (in lines of code) and number procs of parallel shell processes. The bottom line shows the resulting maximum coverage achieved with that choice of parameters.

havior of AFL++ , which is however a combined result of its exploration heuristics, the grammar that provides the testing seeds, and some random fluctuations.

Compared to AFL++ , ShellFuzzer demonstrates some advantages in terms of robustness/repeatability. Table 7 shows that the same unique confirmed bugs were revealed in all repeated runs of ShellFuzzer; in contrast, only AFL++ 's configuration A 1 had a similar repeatability, whereas some repetitions of the experiments with configurations A 2 and A 3 failed to reveal some of the bugs. On the same note, destructive crashes are also detrimental to robustness, as suggested by Figure 9.

In our experiments, AFL++ usually achieved higher coverage than ShellFuzzer (2-6% higher), and revealed 2 more memory errors. In contrast, ShellFuzzer revealed 3 more errors overall (including 5 logic errors), and behaved more robustly (no destructive crashes, bugs detected in all repeated runs).

## 5.4. RQ4: Parameter Tuning

In all the experiments described so far, ShellFuzzer ran with the configuration described in Table 4. Now, we discuss the experiments we performed to determine this standard configuration.

First of all, we tried to determine values for Table 3's parameters size (the approximate average size of the produced scripts, in lines of code) and procs (the number of shell processes running scripts in parallel during testing). Instead of an exhaustive exploration of the full parameter space - which would be unfeasible - we determined, for each generator, three combinations of values for these

two parameters roughly corresponding to 'small', 'medium', and 'large' parameter values. Table 8 shows the nine parameter pairs (three for each generator) that we used in these tuning experiments. 29

Finally, we selected values for Table 3's parameter time : the time allotted to each generator within a standard 12-hour session. We considered three different partitioning of time:

Then, we ran each generator for 6 hours with each choice of parameter values, and measured the reached coverage. Table 8's bottom row shows the maximum coverage of each configuration's run. We then selected each generator's parameters that achieved the best coverage; if two configurations achieved the same coverage, we preferred the one with higher throughput (measured as the number of scripts generated and executed per time unit). In all, this led to choosing 'medium' parameters for V and M I , and 'large' parameters for I . Weremark that ShellFuzzer's behavior remained fairly consistent - with only small changes in coverage and other measures - even with significant changes to the parameter values. Thus, the selected parameter values are a reasonable choice but they are by no means 'magic values'.

4 V +4 +4 I M I : each generator gets the same amount of time (4 hours);

4 V +6 +2 I M I : generator I gets the longest time slot (6 hours), followed by V (4 hours), and then M I (2 hours);

5 V +5 +2 I M I : generators V and I get the bulk of testing time (5 hours each), M I gets the remaining time (2 hours).

Given that it's clear that running all generators is beneficial, we did not consider configurations where a generator does not run at all; besides, we usually give less time to generator M I , since it is more specialized, and hence it is unlikely to benefit from much longer running times.

We ran three repetitions of the experiments with each time configuration; Table 9 shows the results of these experiments. Once again, the results in terms of coverage and detected bugs are quite similar independent of the time partitioning that we adopt. In the end, we selected configuration 4 V + 6 I + 2 M I since it achieves a slightly higher coverage and precision ( true positives / unique ) than the other configurations. In fact, the central section of Table 9 (configuration 4 V +

29 Remember that parameter size is immaterial for generator I , whose grammar determines the average size of the produced scripts.

|          | generator time [h]   | generator time [h]   | generator time [h]   | generator time [h]   | generator time [h]   | generator time [h]   |
|----------|----------------------|----------------------|----------------------|----------------------|----------------------|----------------------|
|          | 4                    | +4 I +4 M I 4 V      | +4 I +4 M I 4 V      | +6 I +2 M I 5 V      | +6 I +2 M I 5 V      | +5 I +2 M I          |
| category | category             | V sum                | avg                  | sum                  | avg                  | sum                  |
|          | alerts               | 153205               | 51068.3              | 203460               | 67820.0              | 158230               |
|          | unique               | 12                   | 11.3                 | 11                   | 10.3                 | 11                   |
|          | true positives       | 8                    | 8.0                  | 8                    | 8.0                  | 8                    |
|          | confirmed            | 7                    | 7.0                  | 7                    | 7.0                  | 7                    |
|          | alerts               | 152919               | 50973.0              | 203104               | 67701.3              | 157820               |
|          | unique               | 10                   | 9.3                  | 9                    | 8.3                  | 9                    |
|          | true positive        | 6                    | 6.0                  | 6                    | 6.0                  | 6                    |
|          | confirmed            | 5                    | 5.0                  | 5                    | 5.0                  | 5                    |
|          | alerts               | 286                  | 95.3                 | 356                  | 118.7                | 410                  |
|          | unique               | 2                    | 2.0                  | 2                    | 2.0                  | 2                    |
|          | true positive        | 2                    | 2.0                  | 2                    | 2.0                  | 2                    |
|          | confirmed            | 2                    | 2.0                  | 2                    | 2.0                  | 2                    |
| coverage | coverage             | 37.7 %               | 37.7 %               | 37.9 %               | 37.9 %               | 37.7 %               |

Table 9: Effectiveness of ShellFuzzer with different time allocated to each generator. xV + yI + zM I denotes experiments where V ran for x hours, I for y hours, and M I for z hours, such that x + y + z = 12 . For each such time partitioning, the table reports the total number sum over three repeated runs, and average avg per repeated run of alerts raised by ShellFuzzer, unique alerts, true positive bugs, and bugs confirmed by the shell maintainers. The three row groups report data for all alerts, as well as the breakdown into logic and memory alerts (identified as described in Section 3.1). Finally, the bottom row reports the maximum branch coverage reached during any run.

6 I +2 M I ) corresponds to the same experiments reported in Table 5 and discussed in the previous parts of ShellFuzzer's experimental evaluation.

Choosing different values for its parameters (script size, parallel processes, and time for each generator) did not significantly affect ShellFuzzer's effectiveness.

## 5.5. Threats to Validity

We review threats to the validity of the experiments described in this section, as well as how we mitigated them.

Construct validity. Given the nature of our experiments, construct validity mainly pertains the choice of metrics used to study ShellFuzzer's capabilities - which are all fundamental, widely used measures. To study ShellFuzzer's effectiveness as a bug-finding tool, we focused on the key metric of (confirmed) true positive detected errors. Measures related to alert uniqueness and script minimization are also customary to assess effectiveness and how a tool's output is accessible for users. Finally, we also considered code coverage; while it is only a weak proxy for the more important metric of 'found bugs', it remains widely used as it gives a rough idea of the thoroughness of the input space search.

Internal validity. Internal validity depends on the presence of possible confounding factors. To account for the randomness of the script-generation process, we repeated each experiment three times, and reported averages and totals over all runs. In our main experiments, we empirically chose the parameter values used to configure ShellFuzzer based on the results of separate tuning experiments (Section 5.4). It is important to notice that in the tuning experiments, as well as in the repeated runs of the main experiments, we observed remarkably consistent results from run to run. Hence, while it is possible that configuring ShellFuzzer very differently would yield different results, we are reasonably confident that our paper's findings are sufficiently representative and informative.

In order to make the comparison between ShellFuzzer and AFL++ fair, we configured AFL++ with the same grammar mutator used by ShellFuzzer's implementation, and we adopted the same experimental conditions (three repetitions of 12-hour testing sessions). Since AFL++ is a highly configurable tool, we performed experiments with three different exploration heuristics and reported all results. Since AFL++ may occasionally generate scripts that destroy the testing

Determining which of the (unique) alerts raised during ShellFuzzer's experiments are true positives involved some manual analysis. We took standard measures - such as performing multiple checks, trying to reproduce issues on different shell interpreters, and consulting different sources of documentation of expected behavior - to reduce the risk that our judgment was biased or unreliable. Ultimately, we tried to get every alert that we classified as true positive confirmed by the shell's maintainers. Even though deciding whether a certain interpreter behavior is acceptable or not may involve criteria that go beyond strict adherence to the POSIX standard, it remains that most of the issues we reported to maintainers were confirmed (and, in many cases, were addressed by changes in the code or documentation of the interpreter); this is reassuring evidence that the most significant threats to internal validity were adequately mitigated.

environment, we also took measures to limit their impact, and discounted from the overall testing time the interruptions needed to (manually) reset the environment and continue testing. Despite this process, AFL++ and ShellFuzzer remain tools with distinct strengths and weaknesses: the goal of our comparison is demonstrating what each tool does best, and how they differ.

External validity. External validity concerns the generalizability of the research findings. In our experiments, we primarily targeted the mksh shell, because it is a widely used POSIX-compliant shell with a somewhat shorter development history compared to other de facto standard shells. Nevertheless, ShellFuzzer is applicable to test any other shell interpreter - in fact, we found that two mksh memory errors that we discovered in our experiments also affect Bash.

We focused on a subset of the POSIX standard shell language because it underlies a large number of widely used shell interpreters. By changing the grammars used by ShellFuzzer's generators, one could adapt ShellFuzzer to work with different kinds of shell languages (for example, the Windows PowerShell), or even other interpreted languages (for example, Python or JavaScript). Of course, effectively supporting very different languages may require to adjust other features of ShellFuzzer's design. A crucial feature is the automated generation of oracles based on the expected validity or invalidity of a generated program (Section 3.1); this may be trickier to implement when targeting languages with stricter standards, single implementations, or no legacy features.

## 6. Conclusions and Future Work

We presented ShellFuzzer: an automated testing technique to find bugs of different kinds in shell interpreters. ShellFuzzer's design addresses several of the challenges of testing a shell interpreter - some shared with testing interpreters or compilers for other languages, others specific to the shell language. To produce a broad variety of structured inputs - i.e., POSIX-compliant shell scripts ShellFuzzer combines different grammar-based generators with some carefully chosen random mutation. Each generator produces scripts with homogeneous characteristics, which makes it possible to also automatically produce an oracle that states the expected overall behavior (error/no error) of executing the script, whereas the combination of three generators increases the overall diversity. Another key design choice were the mutations and the fragment of the POSIX grammar that each generator uses: we chose them to minimize the chance that a generated script incurs destructive behavior - irreversibly damaging the

testing environment. Our experiments demonstrate that ShellFuzzer is effective at finding bugs of various kinds in widely used shell interpreters (i.e., mksh and Bash). Even though none of the bugs we found are likely to have a major impact on the security of using Unix shells, finding any kind of developer-confirmed misbehavior is non-trivial for software with such a long usage and development history.

The comparison between ShellFuzzer and AFL++ indicated that the two approaches have largely complementary features. Of course, AFL++ is a much more mature and robust tool than ShellFuzzer, and remains remarkably effective as a general-purpose fuzzer [39]. ShellFuzzer is specifically geared towards detecting logic bugs - for example affecting the behavior of the parser or other interpreter features. In contrast, AFL++ is usually more effective at achieving a high coverage, which can be a quicker way of discovering 'fundamental' bugs such as memory-related errors. The fact that ShellFuzzer managed to avoid destructive crashes in all the experiments is a strength of our approach, since it makes for a more automated, uninterrupted testing process.

## Future Work

A straightforward way of improving ShellFuzzer's effectiveness is using additional implicit oracles - such as sanitizers for concurrency issues or security properties. This does not require, in principle, to modify anything in how ShellFuzzer generated shell scripts; however, certain kinds of bugs may only be triggered by using certain kinds of shell features.

Akey challenge would be balancing out the expressiveness of the generation process and retaining some control over it, so as to avoid destructive behavior and to automatically build oracles. In ShellFuzzer, we explicitly designed the generators with this balance in mind. In future work, one may try to generate the grammars and mutations themselves in some sort of automated way, for example by relying on a formal semantics of the shell [19] or by mining them from examples [23, 4].

While different shell interpreters have different levels of robustness and maturity, there are no a priori reasons that prevent us from extending the experiments with ShellFuzzer to other shells, including those with non POSIX-compatible extensions. Doing so would require modifying or extending the grammars used by ShellFuzzer's generators, as well as their mutation operators.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have affected the work reported in this paper.

## Data Availability

The prototype implementation of ShellFuzzer is available in a public repository.

## Acknowledgments

The authors gratefully acknowledge the financial support of the Swiss National Science Foundation for the work (SNF grant 200020-188613).

## References

- [1] E. T. Barr, M. Harman, P. McMinn, M. Shahbaz, and S. Yoo. The oracle problem in software testing: A survey. IEEE Trans. Software Eng. , 41(5):507525, 2015.
- [2] O. Bastani, R. Sharma, A. Aiken, and P. Liang. Synthesizing program input grammars. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, Barcelona, Spain, June 18-23, 2017 , pages 95-110. ACM, 2017.
- [3] B. F. H. Becker, N. Jeannerod, C. Marché, Y. Régis-Gianas, M. Sighireanu, and R. Treinen. The CoLiS platform for the analysis of maintainer scripts in Debian software packages. Int. J. Softw. Tools Technol. Transf. , 24(5):717733, 2022.
- [4] L. Bettscheider and A. Zeller. Look ma, no input samples! mining input grammars from code with symbolic parsing. In Companion Proceedings of the 32nd ACM International Conference on the Foundations of Software Engineering, FSE 2024, Porto de Galinhas, Brazil, July 15-19, 2024 , pages 522-526. ACM, 2024.
- [5] M. Böhme, C. Cadar, and A. Roychoudhury. Fuzzing: Challenges and Reflections. IEEE Softw. , 38(3):79-86, 2021.

|      | Fuzzing as Markov Chain. In E. R. Weippl, S. Katzenbeisser, C. Kruegel, A. C. Myers, and S. Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, Oc- tober 24-28, 2016 , pages 1032-1043. ACM, 2016.                                                                                                    |
|------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [7]  | C. Cadar, D. Dunbar, and D. R. Engler. KLEE: Unassisted and automatic gen- eration of high-coverage tests for complex systems programs. In R. Draves and R. van Renesse, editors, 8th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2008, December 8-10, 2008, San Diego, Cal- ifornia, USA, Proceedings , pages 209-224. USENIX Association, 2008. |
| [8]  | J. Chen, J. Patra, M. Pradel, Y. Xiong, H. Zhang, D. Hao, and L. Zhang. A survey of compiler testing. ACM Comput. Surv. , 53(1):4:1-4:36, 2021.                                                                                                                                                                                                                             |
| [9]  | Y. Chen, A. Groce, C. Zhang, W. Wong, X. Z. Fern, E. Eide, and J. Regehr. Taming compiler fuzzers. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '13, Seattle, WA, USA, June 16- 19, 2013 , pages 197-208. ACM, 2013.                                                                                                                   |
| [10] | Y. Chen, T. Su, C. Sun, Z. Su, and J. Zhao. Coverage-directed differential test- ing of JVM implementations. In Proceedings of the 37th ACMSIGPLAN Con- ference on Programming Language Design and Implementation, PLDI 2016, Santa Barbara, CA, USA, June 13-17, 2016 , pages 85-99. ACM, 2016.                                                                            |
| [11] | L. D'Antoni, R. Singh, and M. Vaughn. NoFAQ: synthesizing command repairs from examples. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2017, Paderborn, Germany, September 4-8, 2017 , pages 582-592. ACM, 2017.                                                                                                           |
| [12] | B. Delamore and R. K. L. Ko. A global, empirical analysis of the shellshock vulnerability in web applications. In 2015 IEEE Trustcom/BigDataSE/ISPA , volume 1, pages 1129-1135, 2015.                                                                                                                                                                                      |
| [13] | G. Deng, Z. Zhang, Y. Li, Y. Liu, T. Zhang, Y. Liu, G. Yu, and D. Wang. NAU- TILUS: automated RESTful API vulnerability detection. In 32nd USENIX Security Symposium, USENIX Security 2023, Anaheim, CA, USA, August 9-11, 2023 . USENIX Association, 2023.                                                                                                                 |
| [14] | J. Deng, X. Zhu, X. Xiao, S. Wen, Q. Li, and S. Xia. Fuzzing with optimized grammar-aware mutation strategies. IEEE Access , 9:95061-95071, 2021.                                                                                                                                                                                                                           |

|      | of graphics shader compilers. Proc. ACM Program. Lang. , 1(OOPSLA):93:1- 93:29, 2017.                                                                                                                                                                                                                                            |
|------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [16] | Y. Dong, Z. Li, Y. Tian, C. Sun, M. W. Godfrey, and M. Nagappan. Bash in the wild: Language usage, code smells, and bugs. ACM Trans. Softw. Eng. Methodol. , 32(1):8:1-8:22, 2023.                                                                                                                                               |
| [17] | E. Eide and J. Regehr. Volatiles are miscompiled, and what to do about it. In Proceedings of the 8th ACM & IEEE International conference on Embedded software, EMSOFT 2008, Atlanta, GA, USA, October 19-24, 2008 , pages 255- 264. ACM, 2008.                                                                                   |
| [18] | A. Fioraldi, D. Maier, H. Eißfeldt, and M. Heuse. AFL++: Combining in- cremental steps of fuzzing research. In 14th USENIX Workshop on Offensive Technologies, WOOT 2020, August 11, 2020 . USENIX Association, 2020.                                                                                                            |
| [19] | M. Greenberg and A. J. Blatt. Executable formal semantics for the POSIX shell. Proc. ACM Program. Lang. , 4(POPL):43:1-43:30, 2020.                                                                                                                                                                                              |
| [20] | M. Greenberg, K. Kallas, and N. Vasilakis. The future of the shell: Unix and beyond. In HotOS '21: Workshop on Hot Topics in Operating Systems, Ann Arbor, Michigan, USA, June, 1-3, 2021 , pages 240-241. ACM, 2021.                                                                                                            |
| [21] | M. Greenberg, K. Kallas, and N. Vasilakis. Unix shell programming: the next 50 years. In HotOS '21: Workshop on Hot Topics in Operating Systems, Ann Arbor, Michigan, USA, June, 1-3, 2021 , pages 104-111. ACM, 2021.                                                                                                           |
| [22] | A. Groce, M. A. Alipour, C. Zhang, Y. Chen, and J. Regehr. Cause reduc- tion: delta debugging, even without bugs. Softw. Test. Verification Reliab. , 26(1):40-68, 2016.                                                                                                                                                         |
| [23] | A. Gupta, R. Gopinath, and A. Zeller. CLIFuzzer: mining grammars for command-line invocations. In Proceedings of the 30th ACM Joint Euro- pean Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2022, Singapore, Singapore, November 14-18, 2022 , pages 1667-1671. ACM, 2022. |
| [24] | C. Holler, K. Herzig, and A. Zeller. Fuzzing with code fragments. In Pro- ceedings of the 21th USENIX Security Symposium, Bellevue, WA, USA, August 8-10, 2012 , pages 445-458. USENIX Association, 2012.                                                                                                                        |

|      | mands on FPGAs using partial reconfiguration. In FSP 2017; Fourth Interna- tional Workshop on FPGAs for Software Programmers , pages 1-7, 2017.                                                                                                                                                                                                                               |
|------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [26] | S. Hu and al. Grammar mutator - AFL++. https://github.com/ AFLplusplus/Grammar-Mutator .                                                                                                                                                                                                                                                                                      |
| [27] | IEEE and The Open Group. The Open Group Base Specifications Issue 7 - IEEE Std 1003.1-2018. https://pubs.opengroup.org/onlinepubs/ 9699919799 , 2018.                                                                                                                                                                                                                         |
| [28] | N. Jeannerod, C. Marché, and R. Treinen. A formally verified interpreter for a shell-like programming language. In Verified Software. Theories, Tools, and Experiments - 9th International Conference, VSTTE 2017, Heidelberg, Ger- many, July 22-23, 2017, Revised Selected Papers , volume 10712 of Lecture Notes in Computer Science , pages 1-18. Springer, 2017.         |
| [29] | K. Kallas, T. Mustafa, J. Bielak, D. Karnikis, T. H. Y. Dang, M. Greenberg, and N. Vasilakis. Practically correct, just-in-time shell script parallelization. In M. K. Aguilera and H. Weatherspoon, editors, 16th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2022, Carlsbad, CA, USA, July 11-13, 2022 , pages 769-785. USENIX Association, 2022. |
| [30] | S. Kim, M. Xu, S. Kashyap, J. Yoon, W. Xu, and T. Kim. Finding semantic bugs in file systems with an extensible fuzzing framework. In T. Brecht and C. Williamson, editors, Proceedings of the 27th ACM Symposium on Oper- ating Systems Principles, SOSP 2019, Huntsville, ON, Canada, October 27-30, 2019 , pages 147-161. ACM, 2019.                                       |
| [31] | P. Kreutzer, T. Kunze, and M. Philippsen. Test case reduction: Aframework, benchmark, and comparative study. In IEEE International Conference on Software Maintenance and Evolution, ICSME 2021, Luxembourg, September 27 - October 1, 2021 , pages 58-69. IEEE, 2021.                                                                                                        |
| [32] | V. Le, M. Afshari, and Z. Su. Compiler validation via equivalence modulo inputs. In ACMSIGPLAN Conference on Programming Language Design and Implementation, PLDI '14, Edinburgh, United Kingdom - June 09 - 11, 2014 , pages 216-226. ACM, 2014.                                                                                                                             |
| [33] | V. Le, C. Sun, and Z. Su. Finding deep compiler bugs via guided stochastic program mutation. In Proceedings of the 2015 ACM SIGPLAN International                                                                                                                                                                                                                             |

|      | Conference on Object-Oriented Programming, Systems, Languages, and Ap- plications, OOPSLA 2015, part of SPLASH 2015, Pittsburgh, PA, USA, October 25-30, 2015 , pages 386-399. ACM, 2015.                                                                                                                                                                            |
|------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [34] | V. Le, C. Sun, and Z. Su. Randomized stress-testing of link-time optimizers. In Proceedings of the 2015 International Symposium on Software Testing and Analysis, ISSTA 2015, Baltimore, MD, USA, July 12-17, 2015 , pages 327-337. ACM, 2015.                                                                                                                       |
| [35] | W. Li, H. Yang, X. Luo, L. Cheng, and H. Cai. PyRTFuzz: Detecting bugs in Python runtimes via two-level collaborative fuzzing. In W. Meng, C. D. Jensen, C. Cremers, and E. Kirda, editors, Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 26-30, 2023 , pages 1645-1659. ACM, 2023. |
| [36] | G. Liargkovas, K. Kallas, M. Greenberg, and N. Vasilakis. Executing shell scripts in the wrong order, correctly. In M. Schwarzkopf, A. Baumann, and N. Crooks, editors, Proceedings of the 19th Workshop on Hot Topics in Op- erating Systems, HOTOS 2023, Providence, RI, USA, June 22-24, 2023 , pages 103-109. ACM, 2023.                                         |
| [37] | V. Livinskii, D. Babokin, and J. Regehr. Random testing for C and C++ compilers with YARPGen. Proc. ACM Program. Lang. , 4(OOPSLA):196:1- 196:25, 2020.                                                                                                                                                                                                              |
| [38] | S. Mallissery and Y. Wu. Demystify the fuzzing methods: Acomprehensive survey. ACM Comput. Surv. , 56(3):71:1-71:38, 2024.                                                                                                                                                                                                                                           |
| [39] | V. J. M. Manès, H. Han, C. Han, S. K. Cha, M. Egele, E. J. Schwartz, and M. Woo. The art, science, and engineering of fuzzing: Asurvey. IEEE Trans. Software Eng. , 47(11):2312-2331, 2021.                                                                                                                                                                          |
| [40] | M. Marcozzi, Q. Tang, A. F. Donaldson, and C. Cadar. Compiler fuzzing: how much does it matter? Proc. ACM Program. Lang. , 3(OOPSLA):155:1- 155:29, 2019.                                                                                                                                                                                                            |
| [41] | K. Mazurak and S. Zdancewic. ABASH: finding bugs in bash scripts. In Proceedings of the 2007 Workshop on Programming Languages and Analysis for Security , PLAS'07, pages 105-114, NewYork, NY, USA,2007. Association for Computing Machinery.                                                                                                                       |

|      | of UNIX utilities. Commun. ACM , 33(12):32-44, 1990.                                                                                                                                                                                                                                   |
|------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [43] | R. Morisset, P. Pawan, and F. Zappa Nardelli. Compiler testing via a theory of sound optimisations in the C11/C++11 memory model. In ACMSIGPLAN Conference on Programming Language Design and Implementation, PLDI '13, Seattle, WA, USA, June 16-19, 2013 , pages 187-196. ACM, 2013. |
| [44] | E. Nagai, A. Hashimoto, and N. Ishiura. Reinforcing random testing of arith- metic optimization of Ccompilers by scaling up size and number of expres- sions. IPSJ Trans. Syst. LSI Des. Methodol. , 7:91-100, 2014.                                                                   |
| [45] | K. Nakamura and N. Ishiura. Random testing of C compilers based on test program generation by equivalence transformation. In 2016 IEEE Asia Pa- cific Conference on Circuits and Systems, APCCAS 2016, Jeju, South Korea, October 25-28, 2016 , pages 676-679. IEEE, 2016.             |
| [46] | M. H. Palka, K. Claessen, A. Russo, and J. Hughes. Testing an optimising compiler by generating random lambda terms. In Proceedings of the 6th International Workshop on Automation of Software Test, AST 2011, Waikiki, Honolulu, HI, USA, May 23-24, 2011 , pages 91-97. ACM, 2011.  |
| [47] | J. Patra and M. Pradel. Learning to fuzz: Application-independent fuzz testing with probabilistic, generative models of input data. Technical Re- port TUD-CS-2016-14664, TU Darmstadt, Department of Computer Sci- ence, 2016.                                                        |
| [48] | D. Ritchie and K. Thompson. The UNIX Time-Sharing System: The UNIX Shell. Bell System Technical Journal , 57(6):1971-1990, 1978.                                                                                                                                                       |
| [49] | K. Serebryany, D. Bruening, A. Potapenko, and D. Vyukov. AddressSan- itizer: A Fast Address Sanity Checker. In 2012 USENIX Annual Technical Conference, Boston, MA, USA, June 13-15, 2012 , pages 309-318. USENIX As- sociation, 2012.                                                 |
| [50] | D. Spinellis and M. Fragkoulis. Extending Unix pipelines to DAGs. IEEE Trans. Computers , 66(9):1547-1561, 2017.                                                                                                                                                                       |
| [51] | E. Stepanov and K. Serebryany. MemorySanitizer: fast detector of unini- tialized memory use in C++. In Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2015,                                                                  |

San Francisco, CA, USA, February 07 - 11, 2015 , pages 46-55. IEEE Computer Society, 2015.

- [52] C. Sun, V. Le, and Z. Su. Finding and analyzing compiler warning defects. In Proceedings of the 38th International Conference on Software Engineering, ICSE 2016, Austin, TX, USA, May 14-22, 2016 , pages 203-213. ACM, 2016.
- [53] C. Sun, V. Le, and Z. Su. Finding compiler bugs via live code mutation. In Proceedings of the 2016 ACM SIGPLAN International Conference on ObjectOriented Programming, Systems, Languages, and Applications, OOPSLA 2016, part of SPLASH 2016, Amsterdam, The Netherlands, October 30 - November 4, 2016 , pages 849-863. ACM, 2016.
- [54] Q. Tao, W. Wu, C. Zhao, and W. Shen. An automatic testing approach for compiler based on metamorphic testing technique. In 17th Asia Pacific Software Engineering Conference, APSEC 2010, Sydney, Australia, November 30 December 3, 2010 , pages 270-279. IEEE Computer Society, 2010.
- [55] J. Wang, B. Chen, L. Wei, and Y. Liu. Superion: grammar-aware greybox fuzzing. In Proceedings of the 41st International Conference on Software Engineering, ICSE 2019, Montreal, QC, Canada, May 25-31, 2019 , pages 724-735. IEEE / ACM, 2019.
- [56] M. Wen, Y. Wang, Y. Xia, and H. Jin. Evaluating seed selection for fuzzing JavaScript engines. Empir. Softw. Eng. , 28(6):133, 2023.
- [57] X. Yang, Y. Chen, E. Eide, and J. Regehr. Finding and understanding bugs in C compilers. In M. W. Hall and D. A. Padua, editors, Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2011, San Jose, CA, USA, June 4-8, 2011 , pages 283-294. ACM, 2011.
- [58] A. Zeller and R. Hildebrandt. Simplifying and isolating failure-inducing input. IEEE Trans. Software Eng. , 28(2):183-200, 2002.
- [59] X. Zhu, S. Wen, S. Camtepe, and Y. Xiang. Fuzzing: A survey for roadmap. ACM Comput. Surv. , 54(11s):230:1-230:36, 2022.
- [60] T. Zimmermann, R. Premraj, N. Bettenburg, S. Just, A. Schröter, and C. Weiss. What makes a good bug report? IEEE Trans. Software Eng. , 36(5):618-643, 2010.
Riccardo Felici Laura Pozzi Carlo A. Furia
ShellFuzzer: Grammar-based Fuzzing of Shell Interpreters
Despite its long-standing popularity and fundamental role in an operating
system, the Unix shell has rarely been a subject of academic research. In
particular, regardless of the significant progress in compiler testing, there
has been hardly any work applying automated testing techniques to detect faults
and vulnerabilities in shell interpreters.
  To address this important shortcoming, we present ShellFuzzer: a technique to
test Unix shell interpreters by automatically generating a large number of
shell scripts. ShellFuzzer combines grammar-based generation with selected
random mutations, so as to produce a diverse range of shell programs with
predictable characteristics (e.g., valid according to the language standard,
and free from destructive behavior).
  In our experimental evaluation, ShellFuzzer generated shell programs that
exposed 8 previously unknown issues that affected a recent version of the mksh
POSIX-compliant shell; the shell maintainers confirmed 7 of these issues, and
addressed them in the latest revisions of the shell's open-source
implementation.