Shaping Inputs with Constraints

Shaping Inputs with Constraints#

The Limits of Grammars#

So far, all the operations we have performed on our data were syntax-oriented - that is, we could shape the format and structure of our values, but not their semantics - that is, their actual meaning. Consider our Person/Age dataset from the previous section. What would we do if we want the “age” in a specific range? Or we want it to be odd? Or we want the age to be distributed in a certain way?

All of this refers to context-free grammars, which are the ones Fandango uses.

Some of these can be obtained by altering the grammar - limiting the age to two digits at most, for instance, will keep the value below 100 - but others cannot. Properties that cannot be expressed in a grammar are called semantic properties - in contrast to syntactical properties, which is precisely what grammars are good for.

Specifying Constraints#

Fandango solves this problem through a pretty unique feature: It allows users to specify constraints which inputs have to satisfy. These thus narrow down the set of possible inputs.

Constraints are predicates over grammar symbols. Essentially, you write a Boolean expression, using grammar symbols (in <...>) to refer to individual elements of the input.

As an example, consider this Fandango constraint:

int(<age>) < 50

This constraint takes the <age> element from the input and converts it into an integer (all symbols are strings in the first place). Inputs are produced only if the resulting value is less than 50.

We can add such constraints to any .fan file, say the persons.fan file from the previous section. Constraints are preceded by a keyword where. So the line we add reads

where int(<age>) < 50

and the full persons.fan file reads

<start> ::= <person_name> "," <age>
<person_name> ::= <first_name> " " <last_name>
<first_name> ::= <name>
<last_name> ::= <name>
<name> ::= <ascii_uppercase_letter><ascii_lowercase_letter>+
<age> ::= <digit>+
where int(<age>) < 50

If we do this and run Fandango, we obtain a new set of inputs:

$ fandango fuzz -f persons.fan -n 10

Sawwuakfi Tmglpjahkhjl,8

Heqctrgvwwcd Fhc,48

Gdyizstjnfsqeckiyfuqj Udydo,7

Uqeomwzcxcrrulfhcos Hwazqnrghx,9

Caacqauxy Zq,3

Hjngw Nxxmvupcddujxrvega,1

Wuxhrgobtdcak Flamrpeecgr,00

Gb Cenl,8

Sawwuakfi Tmglpjahkhjl,7
Heqctrgvwwcd Zsc,48

We see that all persons produced now indeed have an age of less than 50. Even if an age begins with 0, it still represents a number below 50.

The language Fandango uses to express constraints is Python, so you can make use of arbitrary Python expressions. For instance, we can use Python Boolean operators (and, or, not) to request values in a range of 25-45:

Interestingly, having symbols in <...> does not conflict with the rest of Python syntax. Be sure, though, to leave spaces around < and > operators to avoid confusion.

25 <= int(<age>) and int(<age>) <= 45

and we obtain these inputs:

Lvxmzcamuufonwkmyajpicuynchaydgbhfhipofyyfgckhhtvprryendkp Oqq,39

Dfjxluvbilwjdjuznwykdqacpqvhvvjhovfqavsildxszxkdfnukvjfmsq Obp,41

Mt Obp,41

Dfjxluvbilwjdjuznwykdqacpqvhvvjhovfqavsildxszxkdfnukvjfmsq Zgy,41
Lvxmzcamuufonwkmyajpicuynchaydgdhfhipofyyfgckhhtvprryendkp Oqq,39
Dfskpfyhxuqpbxyzhtyqb Obp,41

Lvxmzcamuufonwkmyajpicuynchaydgbhfhipofyyfgckhhtvprryendkp Hqq,39

Lxucqfrsckoinpaeojaouvaglszahoehldvzksccvizplfxbpnfqjzkopp Roe,30

Lbedupvfiywdcluqbwmkafbxafqkaxfcicstsyvikjscvhgubxyruqviec Mgq,37

Sqs Foeipogvkcvhozvurnjlniwppsycnnvpamlgyxilbouvdcwtkzlfbtmost,36

Start with persons.fan and add a constraint such that we generate people whose age is a multiple of 7, as in

Wdywcuungkpxootu Jfauwzbtnxtkaxcyedu,434

Ztedthck Qjnkdmc,68199954040765386

Lsmcmhupsh Apk,583983133719342028

Azhkqwgv Fiwarlwwdw,0
Pjzlnhsxqgfv Xeobt,504

Qnkleepufripsuos Oxbpuim,4123

Ibbtmobkbeozyuhes Pnjyhcycevodxu,2080792012236422919

Eepzpknbxrwexcyvo Odazsxfwtllkqynnnevrq,0

Pkarqnral Sblfbqslqyty,163859185

Avyckpejarwukkqrg Voezmlfuqeb,78700553777705706

(Hint: The modulo operator in Python is %).

Solution

This is not too hard. Simply add

where int(<age>) % 7 == 0

as a constraint.

Constraints and DerivationTree types#

Whenever Fandango evaluates a constraint, such as

int(<age>) > 20

the type of <age> is actually not a string, but a DerivationTree object - a tree representing the structure of the output.. You can use DerivationTree objects as other basic python data types by converting them using (int(<age>), str(<age>), bytes(<age>)).

  • You can then invoke most string, bytes and int methods on them (<age>.startswith('0')) (see Details)

  • You can compare them against each other (<age_1> == <age_2>) as well as against other strings (<age> != "19")

One thing you cannot do, though, is passing them directly as arguments to functions that do not expect a DerivationTree type. This applies to the vast majority of Python functions.

Important

If you want to pass a symbol as a function argument, convert it to the proper type (int(<age>), float(<age>), str(<age>)) first. Otherwise, you will likely raise an internal error in that very function.

Important

On symbols, the [...] operator operates differently from strings - it returns a subtree of the produced output: <name>[0] returns the <first_name> element, not the first character. If you want to access a character (or a range of characters) of a symbol, convert it into a string first, as in str(<name>)[0].

We will learn more about derivation trees, DerivationTree types, and their operators in Accessing Input Elements.

Constraints on the Command Line#

If you want to experiment with constraints, keeping on editing .fan files is a bit cumbersome. As an alternative, Fandango also allows to specify constraints on the command line. This is done with the -c (constraint) option, followed by the constraint expression (typically in quotes).

Starting with the original persons.fan, we can thus apply age constraints as follows:

$ fandango fuzz -f persons.fan -n 10 -c '25 <= int(<age>) and int(<age>) <= 45'

Constraints can be given multiple times, so the above can also be obtained as

$ fandango fuzz -f persons.fan -n 10 -c '25 <= int(<age>)' -c 'int(<age>) <= 45'

Important

On the command line, always put constraints in single quotes ('...'), as the angle brackets might otherwise be interpreted as I/O redirection.

When do constraints belong in a .fan file, and when on the command line? As a rule of thumb:

  • If a constraint is necessary for obtaining valid input files (i.e. if the inputs would not be accepted otherwise), it belongs into the .fan file.

  • If a constraint is optional, for instance for shaping inputs towards a particular goal, then it can also go on the command line.

How Fandango Solves Constraints#

How does Fandango obtain these inputs? In a nutshell, Fandango is an evolutionary test generator:

  1. It first uses the grammar to generate a population of inputs.

  2. It then checks which individual inputs are closest in fulfilling the given constraints. For instance, for a constraint int(<X>) == 100, an input where <X> has a value of 90 is closer to fulfillment than one with value of, say 20.

Selecting the best inputs is also known as “survival of the fittest”

  1. The best inputs are selected, the others are discarded.

  2. Fandango then generates new offspring by mutating the remaining inputs, recomputing parts according to grammar rules. It can also exchange parts with those from other inputs; this is called crossover.

  3. Fandango then repeats Steps 2-4 until all inputs satisfy the constraints.

All of this happens within Fandango, which runs through these steps with high speed. The -v option (verbose) produces some info on how the algorithm progresses:

$ fandango -v fuzz -f persons.fan -n 10 -c 'int(<age>) % 7 == 0'

fandango:INFO: ---------- Parsing FANDANGO content ----------

fandango:INFO: File mode: text
fandango:INFO: ---------- Initializing base population ----------
fandango:INFO: ---------- Initializing FANDANGO algorithm ---------- 
fandango:INFO: ---------- Done initializing base population ----------
fandango:INFO: ---------- Generating  for 500 generations----------
fandango:INFO: Generating (additional) initial population (size: 100)...

Wrt Zhqkb,555051

Knwxqyanpju Wauoffqdzdaqc,784

Rpxajbnteigduu Zqwd,9422667868565

Foltltwxcjawurgw Dwzb,7071330

Xbcn Melkiezswjlvib,102762030

Erzlmysquso Owxbsfbqmhhk,870748424686

Kt Okvgcvnrvpviaiv,8286939204759224681

Ho Hnrczkvwsasx,0

Bphetqpnc Qpnjaxhqnuscim,1084664507687645941
Zaxtltlfvoizk Pbauvzezb,0

Note

The -v option comes right after fandango (and not after fandango fuzz), as -v affects all commands (and not just fuzz).

The Fandango Progress Bar#

While Fandango is solving constraints, you may see a progress bar in the terminal. The progress bar looks like this:

progress-bar

The progress bar is composed of three parts. On the leftmost side, we have the Fandango logo (“💃 Fandango”), followed by a generation counter (“6/500”) showing how often (6) the population has evolved (out of a maximum 500).

Most of the line, however, is filled by a fitness visualization illustrating how the fitness is distributed across the inputs in the population. Each fraction of the line corresponds to an equal fraction of individual inputs. Hence, a 1/70 of the line (typically one character) stands for 1/70 of the population.

The color of each fraction how fit the inputs in the fraction are - on a scale from bright green (perfect fitness, fulfilling the given constraints) to dark red (very little fitness, far away from fulfilling the constraints). Depending on its capabilities, your terminal may also show shades between these colors. Inputs that do not satisfy the constraints at all (zero fitness) are shown in gray.

In the above example, we can see that Fandango already has produces a few inputs that satisfy the constraints; a few more are close and may get there through further evolution.

Note

By default, the progress bar only shows up if

  • Fandango’s standard error is a terminal;

  • Fandango is not run within Jupyter notebook (Jupyter cannot interpret the terminal escape sequences); and

  • Fandango logging is turned off (it also writes to standard error).

The option --progress-bar=on turns on the progress bar even if the above conditions are not met. The option --progress-bar=off turns the progress bar off.

Soft Constraints and Optimization#

So far, we have seen constraints that have to be satisfied for Fandango to produce a string. On top, Fandango also supports so-called “soft” constraints that Fandango aims to satisfy as good as it can. These “soft” constraints come in two forms:

  • maximizing constraints: These constraints specify an expression whose value should be as high as possible

  • minimizing constraints: These constraints specify an expression whose value should be as low as possible.

Such soft constraints are specified

  • on the command line, using --maximizing EXPR and --minimizing EXPR, respectively; or

  • in the .fan file, introducing them with minimizing and maximizing (instead of where), respectively.

If, for instance, you want Fandango to maximize the <age> field, you write

$ fandango fuzz -f persons.fan --maximize 'int(<age>)'

Cmdirvzy Izonxavagg,067843389277654

Gw Kpdvcr,983727056592080956

Rqacpnbzqlxxziafcfic Tncbteueqmerxadmz,983862039793979715

Bi Kgphujqjwak,5940964405601681494

Aoaowqokq Dtejuhin,79392982481410256721

Vpvmwtelgejq Tptckhk,92428481911027381470

Vpvmwtelgejq Zptckhk,92428481911027381470
Zpvmwtelgejq Tptckhk,92428481911027381470

Xlkvmsxhgidzptq Ieorxoyexyozjmrn,92428481911027381470
Opvmwtelgejq Tptckhk,92428481911027381470

Conversely, minimizing the <age> field yields

$ fandango fuzz -f persons.fan --minimize 'int(<age>)'

Gmtmyvm Hmtmhmgs,811991604577644

Jwobityh Qqcnkuxts,0

Yv Wocsmaoxjjlvumna,0

Qjqpkekgcbf Qqcnkuxts,0

Yv Mocsmaoxjjlvumna,0
Kbxqjik Uhnghtjmkrlacwoactt,0

Yv Hocsmaoxjjlvumna,0

Vwobityh Qqcnkuxts,0

Pewjdabfceympcjli Fuenmltabeafm,0

Yewjdabfceympcjli Fuenmltabeafm,0

Alternatively, you could also add to the .fan file:

maximizing int(<age>)

or

minimizing int(<age>)

respectively.

To express optional goals (i.e., real “soft” constraints), simply use a Boolean expressions as the expressions for --maximize or --minimize. Then, Fandango will aim to maximize (or minimize) its value.

Note

Remember that in Python True is equivalent to 1, and False is equivalent to 0; therefore, “maximizing” a Boolean value means that Fandango will aim to solve it.

Here is an example of a “soft” Boolean constraints, aiming to obtain names that start with “F”:

$ fandango fuzz -f persons.fan --maximize '<name>.startswith("A")' -n 10

Gwfiini Tjepstikzoi,57963743467821
Jid Llmrerhwvhrkzdlzhtsvt,6464

Nfhmqs Kyrahvbhdp,8861208385823571
Paosvokmky Hoid,04213677260202901487

Guviyrmsmtjgctxyiqm Lpcqlpnkjuyewx,64189461238099434541
Qgsti Uwzcfjrjjazzadhhkyl,76
Wtyff Kdpd,4001120997101644943

Gorrwtgbmhjrfcqfoid Hlmoeusqdjjemoobs,0
Pkvgkkwfpwcsvbvpcsmg Fgmqfqfbp,6
Rrwknnu Euzd,0604

As you see, “soft” constraints are truly optional :-)

When Constraints Cannot be Solved#

Normally, Fandango continues evolving the population until all inputs satisfy the constraints. Some constraints, however, may be difficult or even impossible to solve. After a maximum number of generations (which can be set using -N), Fandango stops and produces the inputs it has generated so far. We can see this if we specify False as a constraint:

$ fandango -v fuzz -f persons.fan -n 10 -c 'False' -N 10

fandango:INFO: ---------- Parsing FANDANGO content ----------

fandango:INFO: File mode: text
fandango:INFO: ---------- Initializing base population ----------
fandango:INFO: ---------- Initializing FANDANGO algorithm ---------- 
fandango:INFO: ---------- Done initializing base population ----------
fandango:INFO: ---------- Generating  for 10 generations----------
fandango:INFO: Generating (additional) initial population (size: 100)...

fandango:INFO: Initial population generated in 1.86 seconds

fandango:INFO: Generation 1 - Average Fitness: 0.01

fandango:INFO: Generation 1: Increasing mutation rate from 0.200 to 0.220
fandango:INFO: Generation 1: Decreasing crossover rate from 0.800 to 0.760
fandango:INFO: Generation 1: Increasing MAX_REPETITION from 20 to 30

fandango:INFO: Generation 1 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 2 - Average Fitness: 0.01

fandango:INFO: Generation 2: Increasing mutation rate from 0.220 to 0.242
fandango:INFO: Generation 2: Decreasing crossover rate from 0.760 to 0.722
fandango:INFO: Generation 2: Increasing MAX_REPETITION from 30 to 45

fandango:INFO: Generation 2 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 3 - Average Fitness: 0.01

fandango:INFO: Generation 3: Increasing mutation rate from 0.242 to 0.266
fandango:INFO: Generation 3: Decreasing crossover rate from 0.722 to 0.686
fandango:INFO: Generation 3: Increasing MAX_REPETITION from 45 to 68
fandango:INFO: Generation 3 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 4 - Average Fitness: 0.01

fandango:INFO: Generation 4: Increasing mutation rate from 0.266 to 0.293
fandango:INFO: Generation 4: Decreasing crossover rate from 0.686 to 0.652
fandango:INFO: Generation 4: Increasing MAX_REPETITION from 68 to 102

fandango:INFO: Generation 4 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 5 - Average Fitness: 0.01

fandango:INFO: Generation 5: Increasing mutation rate from 0.293 to 0.322
fandango:INFO: Generation 5: Decreasing crossover rate from 0.652 to 0.619
fandango:INFO: Generation 5: Increasing MAX_REPETITION from 102 to 153
fandango:INFO: Generation 5 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 6 - Average Fitness: 0.01

fandango:INFO: Generation 6: Increasing mutation rate from 0.322 to 0.354
fandango:INFO: Generation 6: Decreasing crossover rate from 0.619 to 0.588
fandango:INFO: Generation 6: Increasing MAX_REPETITION from 153 to 230

fandango:INFO: Generation 6 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 7 - Average Fitness: 0.01

fandango:INFO: Generation 7: Increasing mutation rate from 0.354 to 0.390
fandango:INFO: Generation 7: Decreasing crossover rate from 0.588 to 0.559
fandango:INFO: Generation 7: Increasing MAX_REPETITION from 230 to 345

fandango:INFO: Generation 7 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 8 - Average Fitness: 0.01

fandango:INFO: Generation 8: Increasing mutation rate from 0.390 to 0.429
fandango:INFO: Generation 8: Decreasing crossover rate from 0.559 to 0.531
fandango:INFO: Generation 8: Increasing MAX_REPETITION from 345 to 518
fandango:INFO: Generation 8 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 9 - Average Fitness: 0.01

fandango:INFO: Generation 9: Increasing mutation rate from 0.429 to 0.472
fandango:INFO: Generation 9: Decreasing crossover rate from 0.531 to 0.504
fandango:INFO: Generation 9: Increasing MAX_REPETITION from 518 to 777

fandango:INFO: Generation 9 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Generation 10 - Average Fitness: 0.01

fandango:INFO: Generation 10: Increasing mutation rate from 0.472 to 0.519
fandango:INFO: Generation 10: Decreasing crossover rate from 0.504 to 0.479
fandango:INFO: Generation 10: Increasing MAX_REPETITION from 777 to 1000

fandango:INFO: Generation 10 stats -- Best fitness: 0.01, Avg fitness: 0.01, Avg diversity: 0.01, Population size: 100
fandango:INFO: Average fitness of population: 0.01
fandango:INFO: ---------- Done generating  for 10 generations----------
fandango:INFO: Time taken: 14.40 seconds
fandango:ERROR: Population did not converge to a perfect population
fandango:ERROR: Only found 0 perfect solutions, instead of the required 10

As you see, Fandango produces a population of zero. Of course, if the constraint is False, then there can be no success.

Tip

Fandango has a --best-effort option that allows you to still output the final population.