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

Jjmittikqace Dliway,4385673455781760
Xxciwzfkseljdcshjprkg Ryugirhhwjplioyhtct,94
Uzhxphpzfqwmqfxekbkfc Kilwj,70957513

Aqywrfgfihv Cvbfjadayhiejwfxsgw,89004
Xopsrmptvgylnvdl Duabltcompcomwmixafz,97939381
Lppwkhwvsfvruxqmzpqp Xdincjqrfeni,032970514380454

Quyu Tohcgedccqfyxenjaad,5572505129874190846
Nshsrebbszmsm Bsp,560194506558510
Eyncbn Bc,852983313
Xsg Daicdrpngprhkypctfbga,24608715650432

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:

Keqgifwwmkdddsoamsvztmajbuluzzyhdcwewusirvtoegzmhdnysmautprdkwwhhdtmzcbbrovqrnkqklkqzayqyfvwdsllpvxl Xfvrjdspgplkujnplvqnqzrqdfcufakyycnmsjqrxnlxesreiyxhmlxpkyokayfqspiukgfbhlvifprdrtkxtqfhhvkupawguoyu,8

Npmjcpdpyypxufpxthderbhbcdnvbaifwldcxkjshsltnbpdnvmadrxfalbwzvohxuzebxczfklhmivfgokijeesnypyhbqcahsr Ytmrytjfxywmulqvvepecnvpmaiwrnwbvfyxjbvyockhmejpurxbqbmxhkqimmymucuzrozbndljpwoknxhrfttppfyefhjqjwlo,6

Jpyvpkrmclsybjynricedhkrojbbwdczgsmnrtsopqbhxljrprstfcrfskbhawtucmyxxrmomprtdojxstgtzxulleztpdkrffak Lawwzuvldhqhazqumnymowosihiieafwnqskuqvqqfdfzskrwxjnajwmtylgdowveakowhjmjlclykrpfyykniscjahgpqvecpgt,5

Wvigxirwimgbjcjasednhliighwmshejkjcryjcdyzeswofgvtovbiolfaiogooevkavgjbinkoezjtyupnrpkastnznlqdtgxmc Lcxidhzbyozvbnajruwllnkwugiyoiqluvglmjidlwwpncmdkxggdkmuvfkixgxjokgidxmlyhfbhhqowcnwaurkpzeuizvulaop,0

Dfojndtmcmdsxrimouqfyojoouulqixvligayvaxgzynmvorvhuagwqjrqgllvijkkvggiblmaulvfwucpehfdttpadhishiekdb Dfieibykcawmktbcrraahqnmtxfsymfhoicndqtfwwmpkglkpbnysxdglxohqsomsxqjwsqpturqvwaxyztxuersgxthpmeutllo,7

Qhdzvmasankjnrwnagjlfubwsgsbbnjttqgrntjlmjsszdurqeivvhlnqqzofjoyhuwlhybdzuhqxvxybqirupxhyieauitbdaoy Nmncgxpbzskviilbtebetwiglstnzihuaplhbvlrlwcgsiwagcgjfdjrbyjdrnbqjzhimwgvkniykzzyaghqbndsarkwwcxfvvzc,7

Khelzxlfqufmyxxmcqrtkyeixqqsyzrkkwbulcenukjvlcgaodipkmpmvwneoaammdrdpzvypkscdnawrksnatvjnwazujqmtnxu Xcoygggjhoefkzmysxcbtkqfqkilrdtenugbeysktvtizoiriflizgohxazjfnxhuuojudveutngiszteqsistyassluiwceugvc,7

Jalwcegaursjkuqpazchedimaqczdnqihgnxlididwatmqpgjcyfezeacwnnabfbiaumsiudzkjjbxsqtllrlzdlkwjkxkxquxnj Vogtosaulzbbthjnznvckgjrwegujivrvbahkhceswrsurihexuwmncryoizdqnaomiqhuyrylxkanroeftejfhxdnyxylxlfsfz,4

Dvvvsrbfrgmrtfzaaiuibernvzjwvxbanjonvkhrfaplfsdbkyknwncylzdjtnsuidhuwnxbmgraumemlhqjnaqnqqjqarditesw Gexkvptkkxkobonssvxkdztvctazypegndwyrflkuactkaqmpswjwymxpikrkvogsiigvzwqamurbtslvwxgvuzzjildqrvjdtks,3

Pxnusqwktirzwbtdqkijydnecucbdmirpvomdpbzdazvpmnhqgsbnqmbxstbklvkhzavichwqbpuslyhbihvllvliqldqzaoqerz Hrrwxjkfrvtnvjmekbtgpwqwujwyxyadebacnectojruzyjbjmywsqqmohivckitkfbnwqtlbmavwgagcytjwjflqtvtnbsfsckr,1

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

Iecqwhm Dexijsyzxqnsyl,-9761605651312449
Acr Gxyoywfvlzde,5439924

Ckjqosbhcmklhavmkcukd Zfnkafymeibf,-4359043550602124
Pxzbzvgumsjveygpqtisy Ogsplb,0
Elfavsbr Icndrlwansnopwsjk,25343627
Mjzuibhsbmvssopephpn Gckahkhv,165355

Lrwwbilzcah Vrorcmclrb,8808414842646085
Urchyaqvtjzunnxoez Hcijmfzc,56536497801987682097

Hsfjknpleatgklrthcuag Inkunhbjccoozjkgxgeog,702651930943634015
Miramfrnokhg Fzoh,-3641

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.