Xsmith

Version xsmith 1.0.0 (unknown)

1 Introduction

Xsmith is a library for creating fuzz testers, also known as fuzzers, for programming language compilers and interpreters. In other words, Xsmith is a library for creating random program generators.

Xsmith implements a domain-specific language (DSL) for defining random program generators. The DSL is used to specify a programming language’s grammar, typing rules, and other information that guides generation choices. Xsmith also includes utilities for creating a command-line interface for generating a single program or starting a web server that generates one program per request.

Xsmith is bundled with some example random program generators that were created using the library. If you just want to run them, you can jump ahead to Xsmith’s Bundled Generators (And How to Run Them).

Reporting bugs. Please send bug reports and fixes to xsmith-bugs@flux.utah.edu.

Getting help. There is a mailing list, xsmith-dev@flux.utah.edu, for discussing Xsmith. Visit the xsmith-dev list management website to subscribe. To post messages to the list, you must first subscribe to the list.

2 How to Install Xsmith

First, install Racket. If your operating system’s package manager doesn’t have a package or you want a fresher version, download it.

Then run raco pkg install xsmith.

3 Xsmith Guide

Xsmith uses RACR, an attribute grammar library, in its implementation, and some knowledge of RACR is necessary when using Xsmith.

To create a fuzzer with Xsmith, users create a specification by combining spec components, defined with define-spec-component. Each spec component can have portions of grammar as well as properties added to them (using add-to-grammar and add-prop). The grammar and properties are used to generate a RACR grammar, attributes for the grammar, and choice objects, which guide AST generation.

Program generation starts by generating an AST hole for a given grammar production. Generation continues by filling holes with concrete AST nodes (which may introduce new holes as child nodes). Each time a hole is to be filled, the grammar specification is used to determine potential replacements. For example, in a grammar with addition and subtraction expressions, an expression hole may be replaced by an addition or subtraction node. A choice object is created for each legal replacement. Choice objects have methods (choice-rules) which aid in choosing a concrete replacement. Some of these methods act as predicates to filter out choices that are not legal in a particular context, such as choices that introduce more holes when the maximum tree depth has been reached. The choice-weight property defines a method which determines the relative probability of each choice being chosen. The fresh property defines a method which determines how the choice is instantiated as a RACR node. Additional methods may be defined as helpers. Choice objects have access to the current-hole, so they may query RACR attributes in method bodies. Choice object classes follow the same hierarchy as the grammar, so method inheritance for choice objects is similar to attribute inheritance for RACR nodes.

RACR attributes and choice object methods may be added directly with add-att-rule and add-choice-rule, respectively, but many are defined indirectly by various Xsmith properties. Properties allow users to specify various attributes and choice rules in a more declarative fashion.

The primary intended use case of Xsmith is differential compiler/interpreter testing. Therefore Xsmith takes pains to avoid producing programs that rely on commonly unspecified behaviors, such as the order of evaluation of function or operator arguments. Because the language-agnostic analysis within Xsmith is quite conservative, there are many valid programs that will not be generated. However, Xsmith makes it easy to create a fuzzer that obeys such rules without much language-specific work.

3.1 RACR Overview

RACR is a library for Reference Attribute Grammars. Xsmith’s DSL defines a RACR grammar specification as well as various attributes. The attributes are queried to determine how to generate the AST.

RACR caches the results of attribute queries and keeps track of the nodes accessed for any attribute. When nodes used in an attribute computation are changed, future queries to that attribute are re-computed.

Users can specify new RACR attributes for Xsmith generators, but they should use add-att-rule or add-prop from Xsmith rather than using RACR functions directly. In expressions evaluated in the context of RACR attributes (att-rules) or choice rules, RACR attributes may be queried.

The main RACR APIs of interest are:

Functions for querying the AST:

• att-value

• ast-child

• ast-children

• ast-parent

Xsmith provides a function which generates a complete AST, but users can also perform AST rewrites after initial program generation. Relevant RACR functions for performing AST rewrites include:

• perform-rewrites

Full RACR documentation is here.

3.2 Holes and Choice Objects

Hole nodes are RACR AST nodes. For every node type in the grammar, a hole node is created as a subclass of it, inheriting all of its RACR attributes. A hole can be recognized by the xsmith_is-hole? attribute.

When a fresh AdditionExpression is created, it will include two Expression hole nodes. When the generator gets to those holes, a choice object is created for each subclass of Expression (including Expression itself unless it is disabled with the may-be-generated property). The choice objects have types corresponding to LiteralInt and AdditionExpression, and therefore may have different implementations for various choice methods. The choice objects all have access to the Expression hole (through current-hole), but while choice objects have access to their specialized choice method implementations, the hole is of type Expression, and so all RACR attributes (att-rules) that may be queried are specialized only as far as Expression, not to LiteralInt or AdditionExpression.

Note that hole node types are created for every type in the grammar (including LiteralInt and AdditionExpression), but more specialized holes are only used if the grammar specifies that a node’s child must be specifically that kind of expression, or if a custom fresh implementation uses make-hole with the specific kind of expression.

3.3 Scope Graphs

Xsmith uses the language-independent resolution algorithm of scope graphs.

The theory of scope graphs is described in the paper “A Theory of Name Resolution with Extended Coverage and Proofs”, (available at https://researchr.org/publication/NeronTVW15).

3.4 Minimal Example

3.5 Another Small Example With Variables

4 Xsmith Reference

4.1 Stability

Xsmith does not currently promise API stability between versions.

4.2 Auto-Generated att-rules and choice-rules

Many attributes and choice-rules are auto-generated by Xsmith:

att-rules

• 'xsmith_is-hole?

  Accepts no arguments other than the node to call it on. Returns #t when called on a hole node, otherwise returns #f.

  Example:

  ; Within the context of a choice method, this will return #t

  (att-value 'xsmith_is-hole? (current-hole))

• 'xsmith_find-descendants

  Accepts the node to call it on, then a predicate. Returns a list of all descendant nodes that satisfy the predicate.

  Example:

  ; This will return a list of all addition and subtraction nodes.

  ; It will not return any nodes that are subtypes, though!

  (att-value 'xsmith_find-descendants ast-node (λ (n) (member (ast-node-type n)

  '(AdditionExpression

  SubtractionExpression))))

• 'xsmith_find-a-descendant

  Accepts the node to call it on, then a predicate. Like 'xsmith_find-descendants, but it only returns one. If no descendant matching the predicate is found, it returns #f. It is mostly useful if you just want to know if there is any descendant matching a type, such as to determine whether to do an analysis based on the presence or absence of some feature.

• 'xsmith_binding Accepts the node to call it on and optionally a boolean require-binder-or-reference flag (defaults to #t). If the given node is a reference, as determined by the reference-info property, then the reference is resolved and a binding object is returned. If the given node is a binder, as determined by the binder-info property, then its binding object is returned. For any other node, #f is returned when require-binder-or-reference is false, otherwise an error is raised.

  Example:

  ; This raises an exception if `n` is not a binder or reference.

  (att-value 'xsmith_binding n)

  ; If `n` is not a binder or a reference, return #f.

  (att-value 'xsmith_binding n #f)

  The main use of this is to do analyses where you need to look up the declaration node that a reference refers to. The binding object returned by this function contains a reference to the binder node. When resolving references, the scope graph model is used.

• 'xsmith_ast-depth

  Accepts the node it is called on, and no other arguments. Returns the tree depth at that node. Determined by depth-increase.

  Example:

  (att-value 'xsmith_ast-depth n)

• 'xsmith_type This attribute takes no arguments (besides a RACR node) and returns the type (type?) of that node. Note that the type of the node may be a not-yet-concretized type variable.

  (att-value 'xsmith_type n)

choice-rules

• 'xsmith_get-reference! This is a choice method that can be used when creating a reference node. If no binding of the appropriate type for the current node is in scope, this method will cause a fresh appropriate definition to be lifted into a node that can hold definitions. It returns a string? of the reference name.

  Example:

  (att-value 'xsmith_type (current-hole)) ; -> (fresh-type-variable int bool)

  ; This will return the name of a variable in scope

  ; that has type int or type bool.

  ; It may make a new definition node to do that.

  (define name (send (current-hole) xsmith_get-reference!))

  Note that the reference is choosing one of the possible types (via concretize-type). Probably you are using this in a fresh method to initialize a node. So you will want to put that name in the node.

  Generally you don’t need to do this manually, however. Nodes with the reference-info property marked will automatically have their name fields initialized, and nodes with the binder-info property marked will automatically have their name and type fields initialized.

Node type names, attribute names, and choice rule names are just symbols, so they are not hygienic. The names of symbols used or defined by the xsmith library start with xsmith or _xsmith, so don’t tread on those namespaces.

4.3 Forms for Defining a Grammar and Its Attributes

Defines spec-name as a RACR specification.

Defines <spec-name>-generate-ast as a function. The function accepts the name of a grammar production as a symbol and produces a random tree starting from a fresh node of that nonterminal. Essentially, given the name of the top-level program node, this function generates a random program.

Various att-rules are automatically defined within the spec, see Auto-Generated att-rules and choice-rules.

Properties (defined with define-property) are used to derive more RACR att-rules as well as Xsmith choice-rules. Each property may have a transformer function that alters other properties, att-rules, or choice-rules. All properties referenced within a spec-component are used to generate att-rules and choice-rules, as well as any properties specified in the maybe-properties list. Unless values for that property have also been specified within a spec component, properties in the maybe-properties list will only be able to generate rules based on the default value for the property.

node-name will be the name of the grammar production in RACR. parent-name is either the name of the parent grammar production or #f.

Names for the node and fields are limited to alphabetic characters. You may want to use camelCase style names since kebab-style or snake_style names due to this limitation.

Fields are then specified. Each nonternimal inherits all fields of its parent nodes. A field has a name, a type, an optional kleene star, and an optional initialization expression. The type of each field is the name of the nonterminal that it must be or #f for fields that may contain arbitrary Racket values. A field name may be the same as the type, in which case the type does not need to be specified. If a type is not specified and the name does not match the name of a nonterminal, then the type #f is used. If the optional kleene star is supplied, the field will be a list field. If a kleene star is provided for a non-false type, the name and type must be specified separately.

The init-expr for each field specifies a default value for the field. When a node is generated, each init-expr is evaluated unless a non-default value is supplied to the generating function. If no init-expr is supplied, the following defaults are used:

• For false types, #f.

• For nonterminal types, a hole node of the appropriate type.

• For fields with a kleene star, an empty list.

For nodes with a kleene star, init-expr may return a list or a number. If a number is provided, the default value is a list of that many of the non-kleene-star default value.

The example defines a piece of a grammath that includes some kinds of expressions. When a LiteralInt expression is generated, it’s v field will be populated with a random number. Since the random expression is evaluated for each fresh LiteralInt, they will (probably) receive different values for v. When an AditionExpression node is generated, it will be populated with an Expression hole node for each of its left and right fields. When a fresh SumExpression is generated, its addends field will be populated with a list of zero to four Expression hole nodes.

Xsmith creates a choice object class for each node type in the specification grammar, following the same class hierarchy that AST nodes themselves do. Choice objects are created every time Xsmith fills in a hole node. One choice object is created for every node type that is legal to use in filling the hole. Choice objects are then filtered according to the choice-filters-to-apply property, and then the choice-weight property of the remaining choice objects is used to determine the probability of choosing each one. When a choice object is selected, its fresh property is used to generate a new AST node of its type. If all choices are eliminated, an exception is raised with a message stating which filter step invalidated each potential choice.

Choice rules are methods on the choice objects. Some choice rules are used by choice-filters-to-apply to filter choices. Other choice rules may be used by those filters or in the body of the fresh property as helper methods. While most information about the AST and the current choice are probably computed using att-rules, information about choosing a specific node type to fill in an abstract hole (such as an expression hole which may be filled with many different types of expressions) are computed using choice rules.

Choice rules are methods in Racket’s class system and therefore have the this macro available for use in their bodies to access other methods (eg. with the send macro). Choice rules also have the current-hole macro available within their body so that they can query attributes of the RACR AST being elaborated (eg. with att-value to access att-rules and ast-parent to inspect other nodes in the AST).

Since choice rules are methods in Racket’s class system, they must be defined with a literal lambda (with no parameter for the implicit this argument). If a method needs to modify state (such as to cache the computation of available references of the appropriate type), I would normally recommend the “let-over-lambda” pattern, but that is not allowed in this case. To make up for this, I recommend using make-weak-hasheq to hold the state, using the this object as a key.

Since property transformers are macros that may accept arbitrary domain-specific syntax, the grammar of prop-value varies for each property.

Elsewhere it raises a syntax error.

This function is essentially used by add-to-grammar as the default value for grammar fields with nonterminal types that lack an init-expr.

Outside of a spec component context, it raises a syntax error.

4.4 Custom Properties

Properties are used to create domain-specific languages or terse declarative syntax for specifying att-rules and choice-rules. Custom properties are probably only useful for shared infrastructure for multiple languages (perhaps with the exception of define-non-inheriting-rule-property).

Properties can have a transformer function that produce att-rules, choice-rules, or other property values. Property transformers can read the values set for the property by add-prop, and optionally the values of other properties as well. Not all properties must have a transformer – some properties may just be a single place to store information that is used by (multiple) other properties.

The transformer function accepts a dictionary mapping grammar node names (as symbols) to the syntax objects from the right-hand-side of add-prop uses for each property that it reads. The transformer function must return a list of dictionaries mapping grammar node names (as symbols) to syntax objects for the properties, att-rules, and choice-rules that it writes.

Property transformers are run during assemble-spec-components in an order determined by the read/write dependencies among the properties. Appending goes before rewriting, which goes before reading.

If a property appends (using the #:appends keyword) to a property or rule, its return dictionary will be appended to the existing dictionary for that property/rule. This allows a property or rule to be specified in part by the property that appends and in part by another property or the user. If an appended rule (or property that disallows multiple values) ends up with two values for any node, an error is raised.

If a property rewrites (using the #:rewrites keyword) to a property or rule, its return dictionary replaces any previous dictionary for that property/rule. Rewriting a property also automatically implies reading that property. A property or rule may only be rewritten by one property transformer.

The syntax object value for a property can be anything, since property transformers define the grammar and semantics of properties.

The syntax object value for att-rules and choice-rules should be a syntax object specifying a function (IE a lambda). att-rules may be any syntax that evaluates to a function (so you may return an identifier that references a function or an expression that computes a function such as let-over-lambda), but choice-rule syntax is provided to Racket’s class macro, which requires literal lambda forms.

Dictionaries may or may not contain an entry for each nonterminal in the grammar. A dictionary may even be empty.

In addition to nonterminals, each dictionary may include a mapping for the value #f, which will define a default value used for the (super secret) parent node that assemble-spec-components defines. If nothing is specified for #f, att-rules and choice-rules will have a default which errors, providing a helpful error message.

If the #:allow-duplicates? argument is supplied and is #t, then add-prop may be used more than once for the property for the same node, and the syntax object in the dictionary for the property will be a syntax list of the syntax objects specified in the various add-prop calls. But by default only one use of add-prop is allowed per property per node type, and the syntax object in the dict is the single syntax object from the one call.

Here is a simple example that basically desugars straight to an att-rule with a default:

(define-property strict-child-order?

#:appends (att-rule xsmith_strict-child-order?)

#:transformer

(λ (this-prop-info)

(define xsmith_strict-child-order?-info

(hash-set

(for/hash ([(n v) (in-dict this-prop-info)])

(values n (syntax-parse v [b:boolean #'(λ (n) b)])))

#f #'(λ (n) #f)))

(list xsmith_strict-child-order?-info)))

For more realistic examples of properties, see the file private/core-properties.rkt in the Xsmith implementation. Generally they are big, hairy macros.

rule-type must be either att-rule or choice-rule.

rule-name defaults to property-name, but you can make it give the rule a different name than the property.

default-expr is the default value of the property. Any nonterminal that does not have a different value specified gets this one.

transformer-func is an optional transformer to transform the value. It is not called with a dictionary like the transformers of define-property, but rather it receives each value individually. This allows a small amount of sugar. Note that the value supplied as the default-expr is also transformed by the transformer-func when it is supplied. When no transformer-func is supplied, values are passed through literally.

Normally B would inherit a method from A when none was specified for it. But in this case it inherits the default (#f). When a user tries (att-value 'some-bool-flag <node-of-type-B>) it will return #f, not #t.

4.5 Scope Graph Functions

This section describes the API to the Scope Graph model of binding.

Notably this is returned by the att-rule xsmith_binding.

The ast-node field is the grammar node containing the definition of name. The def-or-param field is there to distinguish names that are bound as function parameters vs names that are bound as (local or global) definitions.

Probably all you need to do with this, though, is get the name field and stuff it in the name field of your definition nodes in the fresh method.

When the xsmith_binding attribute is used or when Xsmith searches for a valid reference with xsmith_get-reference, this regexp determines valid scope-graph resolution paths. The path elements (reference, parent, import, definition) are turned into characters (r, p, i, and d respectively). If the path from reference to definition matches this regexp, it is valid. If two definitions have the same name and paths from a reference to both definitions are valid, the definition that is in scope for the reference is determined by current-path-greater-than.

Because Xsmith doesn’t currently support import elements at all, modifying this regexp is somewhat of a moot point.

By default the comparator walks down the paths, comparing each element. A path is greater than another if its first differing element is greater. From least to greatest, path elements are 'reference, 'parent, 'import, 'declaration.

For most languages you probably don’t need to fuss with this.

4.6 Core Properties

These properties are available for specification on Xsmith grammars. Many of them define or modify the behavior of core functionality, such as fresh modifying how fresh program nodes are instantiated, or type-info defining a language’s type rules.

Many are optional, but for any language at all you probably need to use type-info and may-be-generated. Additionally, for any language with variables you need binder-info and reference-info. Next, the fresh property will likely become necessary for a few fields that Xsmith can’t infer. Then the most important of the truly optional properties is likely choice-weight.

If may-be-generated is false, the node is not added to the list of possibile choices to replace an appropriate AST hole. It is useful to set it to false for abstract node types or for specialized node types that are meant to be swapped in only after a full tree is generated, such as by a later analysis to determine validity of an unsafe operation. This property is NOT inherited by subclasses.

The property is two armed.

The first part is the type (or partially-constrained type variable) that the given node can inhabit. The expression given is evaluated fresh every time a node is type checked or considered for generation.

The second part is a function that takes a node, its type, and must return a dictionary mapping its children nodes to types. The dictionary keys may be the node objects of the node’s children OR the symbol of the field name the child inhabits. For kleene-star children, use their node unless they all should receive the same type.

Acceptable values for this property are expressions which produce a dict? object, or expressions which produce a function of type (-> dict? dict?). Keys of the dictionary must be field names of the node being generated. The values in the dictionary are used to fill node fields of the appropriate name. Any field whose name is not in the dictionary will be filled by evaluating the default init-expr defined in the grammar (via add-to-grammar).

This is useful for fields that must be determined together. For examlpe, a function call needs the function name and the number of arguments to be chosen together rather than independently.

As with all choice-rules, this and current-hole are available for use in expressions, which you may want to do for eg. accessing available bindings or mutable information connected to the choice object.

If the result is a procedure instead of a dictionary, that procedure must accept and return a dictionary. It is called with a dictionary that is empty unless the node being created is the result of lifting a definition. In that case it will have the appropriate name and type fields with the name and type chosen by the lifting mechanism. In the case of lifting a definition, the name and type fields in the return dictionary are ignored. This procedure option is allowed because your fresh expression may need access to the name or type to determine the values of other fields. If a definition node only has a name and type field then a fresh property is unnecessary when lifting, and if lifting is the only way you generate definitions then fresh properties or initializers for definition nodes are unnecessary.

If the value for a field (IE values inside the result dictionary) is a procedure, it will be called with 0 arguments. This allows the fresh property to provide a default value that is not evaluated when make-fresh-node is called with an appropriate value.

The expression provided as the choice weight will be evaluated in the context of a method call, so this and current-hole are available.

Choice weights should be positive integer values. The default weight is 10 unless set explicitly.

The property accepts an expression which much evaluate to a function of one argument (the RACR AST node) which returns a truthy value for nodes which increase the depth of the AST and #f otherwise. The default is (λ (n) #t). This property is NOT inherited by subclasses.

This is useful to allow node re-use. For example, the body of an if or for statement might be a block and have the same semantics, but you might want a block inside an if to only be considered a depth increase of 1, not 2.

But if you want to set it:

The property accepts expressions which will evaluate to booleans (IE anything but only #f is false...), which are evaluated if the choice is made at the point where the AST is at it maximum depth. A true value means that the choice is acceptable, false otherwise. The default is computed by checking whether a node includes AST-node-typed fields. If it does not it is considered atomic and therefore acceptable to choose when the AST is already at its maximum depth.

• The identifier read or the identifier write, indicating whether the reference reads or writes the variable

• The name of the field that stores the reference name (as an identifier).

If the property is not specified, 'serial is assumed and used as a default.

Setting this property is unnecessary, but using it allows more liberal use of references, mutation, and io effects.

Until and unless I make something better, this should also be used for any form that mutates some kind of higher-order object. For example, setting a field in a mutable record.

Some core methods are always applied in addition to this list, such as the method defined by the may-be-generated property. If you don’t make custom filtering rules you don’t need to specify this property.

4.7 Types

These type constructors and other functions are largely useful for specifying the type-info property.

While there are various predicates for different types, at any point in type checking you might actually have a type variable instead of a concrete type. So if you want to check if you have a particular type (and maybe deconstruct it), you should maybe create an instance of the type you are interested in, check if it can-unify?, then unify!-ing it if you want to deconstruct it. Note that if you do unify! a type variable, that unification needs to be consistent between multiple runs of type checking (since it runs multiple times as the tree is constructed).

If unification fails an exception is raised. Right now a failure to unify might mean that type variables are left in a bad state, so code generation should just give up at that point.

This form defines a constructor name, a predicate name?, and one accessor for each type-argument name-type-argument a la struct.

Each instance of a generic type can be unified with other instances of the same generic.

Partially specified nominal-record-type?s are created with nominal-record-type-with. Fully specified nominal-record-type?s are created by using concretize-type on a partially specified one. Rather than making them manually, simply rely on Xsmith’s definition-lifting mechanism to create appropriate fully-specified nominal-record-type?s.

When a partially defined nominal-record-type is unify!-ed with a fully defined nominal-record-type, the partially defined one is mutated to become the same as the fully defined one. When two partially defined nominal-record-types are unified together, an error is raised.

Every node in a language grammar that stands for a nominal-record-type constructor, accessor, or mutator must include a reference to a nominal-record-definition-type containing the nominal-record-type being used.

The reason for this is that nominal types must be defined in the program. nominal-record-definition-types are necessary because the lookups of these type names are a different type than uses of the record type that the name is bound to.

This function can be useful if you want to generate a random type. But beware! You should probably NOT generate random types unless you also store them in the grammar node that represents that type. The type-checking code defined in the type-info property can be run many times for each node, so a node that randomly chooses its type will not be stable. Because the type algorithm imperatively unifies types, this causes mayhem. Don’t do it.

Note that to use this function you must parameterize current-xsmith-type-constructor-thunks. Probably in the generate-and-print function passed to xsmith-command-line.

The generate-and-print function passed to xsmith-command-line needs to parameterize this.

4.8 Debug Logging

4.9 Turning Your Grammar Specification Into a Program