Some Fuzzing Strategies

The idea of fuzzing is to have inputs that are out of the ordinary, so we can detect errors in input parsers and beyond. But let us again have a look at the inputs we generated so far:

$ fandango fuzz -f persons.fan -n 10

Xsw Ycpfoq,087
Bzhcj Axdm,53
Isfddm Saw,6715
Jgcan Pqg,21464
Ixtfin Abkzf,5
Hzrifs Iku,3
Xo Eebkq,885
Jxkmjx Slxmo,3
Mdrmjo Jihvf,57
Qbmu Xen,1241

Despite clearly looking non-natural to humans, the strings we generated so far are unlikely to trigger errors in a program, because programs typically treat all letters equally. So let us bring a bit more weirdness into our inputs.

Danger

Don’t feed such fuzz inputs into other people’s systems; this can have unpredictable consequences.

Warning

In most countries, even trying to feed such inputs into other people’s systems will get you into jail.

Looooooong Inputs

One way to increase the probability of detecting bugs is to test with long inputs. While processing data, many programs have limited storage for individual data fields, and thus need to cope with inputs that exceed this storage space. If programmers do not care for such long inputs, serious errors may follow. So-called buffer overflows have long been among the most dangerous vulnerabilities, as they can be exploited to gain unauthorized access to systems.

We can easily create long inputs by specifying the number of repetitions in our grammar:

• Appending {N} to a symbol, where N is a number, makes Fandango repeat this symbol N times.

• Appending {N,M} to a symbol makes Fandango repeat this symbol between N and M times.

• Appending {N,} to a symbol makes Fandango repeat this symbol at least N times.

The +, *, and ? suffixes are actually equivalent to {1,}, {0,}, and {0,1}, respectively.

If, for instance, we want the above names to be 100 characters long, we can set up a new rule for <name>

<name> ::= <ascii_uppercase_letter><ascii_lowercase_letter>{99}

and the lowercase letters will be repeated 99 times.

This is the effect of this rule:

Uhlsynegufnwizwdaupuxcmqibbswjxcxexcxzeavcvgylptqqwatbknbqskpzaqmildlkimkdphuwhxevlkavlkppbfqvubvyaq Uaqoaccytnqdcnnkkrcuwtkgpfwwdofxzudivdblwrurhmfulgshvlnfmilwmznpuunhtjhdnzirdbqrnesqmufigkhgxlhygnbv,17
Vqchgxixgrpnjirzubcjceultgmnliotspidncwscppxofmkaouvmszeaefnolxufdaqokndnapontdyrzbvflnpgohfaqghwqbb Eakdvdnuwgfvganudyaqdcebkqbuujvoeiluxxpitgmxpsyeczbvwxeaxrcgoewfxvjsvkwoweugphifyhfskptbslommunlkhtn,74
Nlnqvxajeecfejndljbhtxvkzzyzuxeymfgwbudfsqqkjgiemnuaxpkkfezsjdciybesbtojkgpkemtoadxlvbhseefgghkcqllc Tcewvuymqmotbxxzmkuncutxompaiyamdrkxuwzqkupiqsalgxwmdgxfwemmuoskghkpbuguaaouqzaicqndophjqvigmafnhddz,50

Gdusitlgvpptiudqllaaqyubunyumjwkzvsphtganyiixqiwcqezpfouhasqhkdtoqvksfesbflzmuxgclwbikpqrwjjlbhhzlle Zyzptqybeyacronjjujdvwmispbxznyovrrmnrcojbraknxdioddfdkoibunffvsefjtlvyulvwhtxboezyljtdlyvsertzlchwn,61
Rxthwshpeashosomjujskqyboxkcubxzwptpcxionijidmvydtdxavodsflufjqiqeidpdjicshwbbgpxfokytduahrmphhlwicn Obxtvidvewhmizzsgjtceyfnzghytohqegnoeyhlepygxayzsiaowbcukdovpxcwzpedzxeabeastlhglkhkmdvvpkyaagioxzps,8
Cynsavtdgyuvdbcuqfqqewzcwdjqpxqgpqanrxalbewxifhoqkmmditrysrtoeokcwwjwiiakqzjqlpbeokueveivkdzoiepwzex Ugcfamfpknvfcaqyqkmyfipjdmbsllmspzplfscxrguwlrjtmanvtsootyuictsfafnvnuaiujippojjdnraxktykvqinwievddk,04
Ibnztnixejzdikifrvhblwcnczimlvpvabdllvryrjxqysykjerihbavmwrurfhmtjgyxvoladtyaahysvmpifuqycefzwrlvdbt Knrogiztopyelgkwalbeypgrwjlnxkjaisiupsdsvqnotvbexuagqhbchzcievyrozwnadtqvyhkjuyzywinzfmqslzfwwyxcsad,47
Egpqoexzmsbpyuhzsmeyrudfsgncpbpzdhdweiekbnzljnzrduzzrsshfxyiionccydyirolegbnficgvvznqyomfudgzcweqhdr Eqvumpxjlqgttyidacllwydeywcqecplmankprpsmkkcsoifzkyizlrzxkxlunrclnxvmlbnjwrpbytoawedszqndjulgrfxbsdw,1
Dltxqsqwcuzutaoxghmoehfpjdbskjjicdkckumrvliuibhzpxbxgblszjumsoehcxjfbwjoitntrxqeiobeyqnhuvnhuttqmkxa Bruphvlwabtrezhetrphrpkccifnuslfkymjrmulytewjjzuqiujmywbtruntlbjgykxszjgnrexhrlzkukkgwbnlbzocwpzwzgy,01
Chuyqwwhthwsbytycrhwxpogsljrnblvwwxlitdffbpexwiurksdhpoztzawkcwbgrcndibsfqscmkuwqmduqwqijxhjtszloklw Rqudfbyqrxujlhedmdlkhndbliemupgagmvrrygaoxxktiskmkelasqqccsspwqnnkuaznrffqjuhegofxajeoruqttjjmsohcbx,77

We see that the names are now much longer. For real-world fuzzing, we may try even longer fields (say, 1,000) to test the limits of our system.

Tip

Programmers often make “off-by-one” errors, so if an input is specified to have at most N characters, you should test this exact boundary - say, by giving N and N+1 characters.

Danger

Don’t try this with other people’s systems; the consequences are unpredictable.

Unusual Inputs

Having “weird” inputs also applies to numerical values. Think about our “age” field, for instance. What happens if we have a person with a negative age?

Note that the grammar already can produce ages way above 100.

Try it yourself and modify persons.fan such that it can also produce negative numbers, as in

Ugxn Wuqf,-04
Ouv Tnsn,65057
Gojnvd Zsfb,2
Efauf Ditq,-678
Ouitq Ingv,-556
Qhq Xnm,-427
Krky Ppwq,-5123
Vjy Usz,2
Gunplh To,016
Pvruqv Un,-4217

Did you succeed? Compare your answer against the solution below.

Solution

You can, for instance, change the <age> rule such that it introduces an alternative for negative numbers:

<age> ::= <digit>+ | "-" <digit>+

Another way to do it is to use the ? modifier, which indicates an optional symbol:

<age> ::= "-"? <digit>+

Other kinds of unusual inputs would be character sets that are out of the ordinary - for instance, Chinese or Hebrew characters - or plain Latin characters if your system expects Chinese names. A simple Emoji, for instance, could be enough to cause the system to fail.

In Python, try float('nan') * float('inf') and other variations.

For numbers, besides being out of range, there are a few constants that are interesting. Some common number parsers and converters accept values such as Inf (infinity) or NaN (not a number) as floating-point values. These actually are valid and have special rules – anything multiplied with Inf also becomes infinitely large (Inf times zero is zero, though); and any operation involving a NaN becomes NaN.

Fortunately, number converters typically treat NaN as invalid.

Imagine what happens if we manage to place a NaN value in a database? Any computation involving this value would also become a NaN, so in our example, the average age of persons would become NaN. The NaN could even go viral across Excel sheets, companies, shareholder reports, and eventually the stock market. Luckily, programs are prepared against that - or are they?

Danger

Don’t try this with other people’s systems; the consequences are unpredictable.

String Injections

Another kind of attack is to insert special strings into the input – strings that would be interpreted by the program not as data, but as commands. A typical example for this is a SQL injection. Many programs use the SQL, the structured query language, as a means to interact with databases. A command such as

INSERT INTO CUSTOMERS VALUES ('John Smith', 34);

would be used to save the values John Smith (name) and 34 (age) in the CUSTOMERS table.

A SQL injection uses specially formed strings and values to subvert these commands. If our “age” value, for instance, is not 34, but, say

34); CREATE TABLE PWNED (Phone CHAR(20)); --

then creating the above INSERT command with this special “age” could result in the following command:

Two dashes (--) start a comment in SQL.

INSERT INTO CUSTOMERS VALUES ('John Smith', 34); CREATE TABLE PWNED (Phone CHAR(20)); --);

and suddenly, we have “injected” a new command that will alter the database by adding a PWNED table.

How would one do this with a grammar? Well, for the above, it suffices to have one more alternative to the <age> rule.

Solution

Here’s how one could change the <age> rule:

<age> ::= <digit>+ | "-" <digit>+ 
        | <digit>+ "); CREATE TABLE PWNED (Phone CHAR(20)); --"

Try adding such alternatives to all data fields processed by a system; feed the Fandango-generated inputs to it; and if you then find a PWNED table on your system, you know that you have a vulnerability.

Danger

Don’t try this with other people’s systems; the consequences are unpredictable.