CERT Releases Basic Fuzzing Framework

infoLaw passes along this excerpt from Threatpost: "Carnegie Mellon University's Computer Emergency Response Team has released a new fuzzing framework to help identify and eliminate security vulnerabilities from software products. The Basic Fuzzing Framework (BFF) is described as a simplified version of automated dumb fuzzing. It includes a Linux virtual machine that has been optimized for fuzz testing and a set of scripts to implement a software test."

Comments

Fuzzing is only useful, if only moderately so

[Anonymous Coward]

Anything that you write that uses a regex you should beat on with some fuzzing logic, since they can tend to increase in computational time non-linearly, and next thing you know you got a DOS on your hands.

TIP OF THE DAY for you FROM ME

Re:Fuzzing is only useful, if only moderately so

[Anonymous Coward]

This man speaks the truth. Just yesterday I had to deal with a Perl script whose execution time blew up once it had to process files larger than 1 KB in size. It'd work fine for 500-character files, but give it more than 1000 characters and the runtime would take over half an hour! (Yes, we had one user sit there and wait over 30 minutes for it to finish.)

In the end, it was a poorly-written regular expression that was to blame. It was easy enough to fix, and we've since ditched the Indian team that developed the script. I think it's excessive, but our manager has now ordered a review of ALL the regexps in all of our scripts.

Re:Fuzzing is only useful, if only moderately so

[h4rr4r]

Pointy hair is the PHB, what do you think PHB stands for?

That is why I asked what the PHB expected, not what he thought the outcome would be.

Re:Fuzzing is only useful, if only moderately so

[ysth]

Nope, no BS. Compare perl -we'("a" x 10) =~ /(a*)(a*)(a*)(a*)(a*)(?i:b)/' and perl -we'("a" x 100) =~ /(a*)(a*)(a*)(a*)(a*)(?i:b)/'

Re:Fuzzing is only useful, if only moderately so

[elfprince13]

I'm sorry you're uneducated about Perl's notoriously poor regex implementation, that has unfortunately become the standard in most languages. Reference: http://swtch.com/~rsc/regexp/regexp1.html

Re:Fuzzing is only useful, if only moderately so

[elfprince13]

Note particularly the units on the vertical scale of those two graphs. The Perl algorithm is measured in seconds, the Thompson algorithm is measured in microseconds.

Re:Fuzzing is only useful, if only moderately so

[Menkhaf]

Thanks for the link, it seems like a good read for a cloudy day.

Do you know if anything has changed since the article in 2007?

-menkhaf

Re:Fuzzing is only useful, if only moderately so

[mr_mischief]

$ time /usr/local/bin/perl -we'("a" x 100) =~ /(a*)(a*)(a*)(a*)(a*)(?i:b)/'
37.00user 0.01system 0:37.81elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+438minor)pagefaults 0swaps

$ time /usr/local/bin/perl -we'("a" x 10) =~ /(a*)(a*)(a*)(a*)(a*)(?i:b)/'
0.00user 0.00system 0:00.00elapsed 75%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+438minor)pagefaults 0swaps

For a purposely selected pathological case on a Pentium M 1.6 GHz laptop with little free RAM, I'd say that's not bad for a system that has specifically been chosen to support grouping, alternation, backreferences, conditional changes (case sensitivity, prematch, postmatch, etc) on only parts of the expression, greediness and nongreediness, lookahead, and lookbehind. Perl "regular expressions" are definitely not actually regular.

That's perl 5.12.0 BTW, which is much improved over older series (pre 5.10 anyway) of perl systems regarding regexes.

Note that if you're okay with intentionally trying and failing to get a case-sensitive rather than case-insensitive 'b' after your pathological quantifiers on the 'a' characters, then you have no such time problem.

$ time /usr/local/bin/perl -we'("a" x 100) =~ /(a*)(a*)(a*)(a*)(a*)(?:b)/'
0.00user 0.00system 0:00.00elapsed 80%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+428minor)pagefaults 0swaps

$ time /usr/local/bin/perl -we'("a" x 1000000) =~ /(a*)(a*)(a*)(a*)(a*)(?:b)/'
0.00user 0.00system 0:00.00elapsed 85%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+673minor)pagefaults 0swaps

$ time /usr/local/bin/perl -we'("a" x 1000000000000) =~ /(a*)(a*)(a*)(a*)(a*)(?:b)/'
0.00user 0.00system 0:00.00elapsed 80%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+426minor)pagefaults 0swaps

I'm sure the p5p would welcome a patch that delivers the promised matching semantics without performing so poorly on pathological cases.

Re:Fuzzing is only useful, if only moderately so

[daemonburrito]

Thanks, that was really interesting.

Re:Fuzzing is only useful, if only moderately so

[ysth]

The point is that it doesn't scale linearly. 1000 is much worse, and 10000 much worse than that.

Yes, any particular case *could* be "fixed" in the regex engine, but there will always be one more possible pathological regex.

Re:Fuzzing is only useful, if only moderately so

[elfprince13]

As far as I know, the same poor implementation is still in use. I don't use Perl, but I do use a lot of languages which make use of PCRE which uses the same faulty algorithm.

Re:Fuzzing is only useful, if only moderately so

[mr_mischief]

Yeah, and checking specifically for a possible type of pathological regex in order to work around it would require slowing the engine for the common case. So I'd say the power of the engine to do so many things is a good trade for the easily avoided pathological cases.

There are only two situations in which such pathological cases are likely to be given to the regex engine anyway. One is when long regexes are built automatically by a program based on a set of rules and a particular data set, which should only trigger a pathological case rarely based on random chance. The other is when people set out to specify something pathological on purpose just to demonstrate the issue. The rest of the time, a programmer should be interested in using the regex engine to actually do something useful and there's really no use in any of the contrivances used for such torture tests.

Re:Fuzzing is only useful, if only moderately so

[ysth]

Perl regexs are not "by definition" regular expressions, and are not handled by a DFA. By choice, not out of ignorance.

Re:Fuzzing is only useful, if only moderately so

[ysth]

No, it actually happens in the wild (see the post ^ that had BS claimed on it) typically when parsing a string up into many substrings where the boundaries aren't specified in such a way that backtracking is prevented.

Re:Fuzzing is only useful, if only moderately so

[mr_mischief]

Sure, it happens, but with what frequency?

Any artificial language you're parsing should be designed with this in mind, or at least a different tool could be clearly chosen for it.

If you're parsing any sort of natural language, well first you kind of deserve what you get. ;-) The variability of the language would seem to preclude this sort of massive backtracking in the common case, and the parser could use multiple separate regexes to help lower the chances of triggering the problem.

It still seems from my experience that the common case is of reasonable performance is much more common, although rare incidents might happen.

Re:Fuzzing is only useful, if only moderately so

[mr_mischief]

Thanks for reading the thread... oh, wait, you didn't. I already said that Perl's extended "regexes" are not regular. Well, thanks for weighing in anyway.

Cool

[gweihir]

And urgently needed. So far the CMU/CERT software I had a look at was pretty good....

bleh

[Anonymous Coward]

Sort of like this?

Re:bleh

[Anonymous Coward]

I wouldn't be so quick to automatically label researchers as professionals. If there is one place I've seen worse code than OSS, it would be in academia.

Bizarrely, this is also where I've seen the most brilliant code.

Re:bleh

[Anonymous Coward]

After writing that, I had to compare the two.

Fuzz's code resides in a massive 34KB C file, undocumented and unformatted, liberal copy-pasta and no re-use, no grasp of language, about as readable as an assembly dump. Basically one big hack.

BFF is a nicely written, concise, small, and extensively documented perl script.

Yep... OSS fails to impress once more.

Re:bleh

[fuzzyfuzzyfungus]

Dare I inquire as to the thought process behind the notion that the inferiority of an OSS program called "Fuzz" and the superiority of an debian-based VM, running a GPLed perl script automating a WTFPLv2-licenced fuzzer proves the unimpressiveness of OSS?

Re:bleh

[Daniel Dvorkin]

If there is one place I've seen worse code than OSS, it would be in academia.

Bizarrely, this is also where I've seen the most brilliant code.

If you look closely, you'll find that the "brilliant code" is most often written by academics who have industry programming experience. Similarly, in industry, you will find that the best code is written by experienced programmers with rigorous academic backgrounds. In contrast, the academics who insist that computer science has nothing to do with programming, and the self-taught hackers who proudly proclaim their lack of all that fancy book-larnin', are two sides of the same worthless coin.

Re:bleh

[NewbieProgrammerMan]

If there is one place I've seen worse code than OSS, it would be in academia.

You've only seen code from those two, then? Because there's no shortage of hard-core WTF code in private business and government.

Re:bleh

[ysth]

Pet peeve: use strict, but not warnings enabled. Yes, strict is really important; BUT WARNINGS ARE MUCH MORE SO.

Re:bleh

[Eskarel]

In their defense, interpreting strings beginning with a zero as being in octal is fucking retarded, and that's the cause of that particular bug. It's even been deprecated in the spec.

axfuzz

[shird]

in their whitepaper they referenced my 'axfuzz' tool I wrote years ago and even used a modified version of it in their testing. Hope they didn't judge me on that code, it was a pile of crap that I kept hacking together until it finally worked, with no thought to proper software design.

Re:axfuzz

[__aasqbs9791]

I think the fact they are using a modified form means they did judge you, and found it good enough to use as a start. That should count for something.

Re:axfuzz

[TubeSteak]

Hope they didn't judge me on that code, it was a pile of crap that I kept hacking together until it finally worked, with no thought to proper software design.

That sounds like exactly the kind of code a fuzzer should be used upon.
Oh the recursion!

Re:axfuzz

[Menkhaf]

Hi,

Do you know if the whitepaper available somewhere for free?

Another link for further information about BFF, is the CERT Vulnerability Analysis Blog, found at https://www.cert.org/blogs/vuls/2010/05/cert_basic_fuzzing_framework.html

-menkhaf

Re:axfuzz

[shird]

I was just referring to this technical document: http://www.cert.org/archive/pdf/dranzer.pdf [pdf]

referenced from: http://threatpost.com/archive/blogs/dranzer-fuzzing-activex-vulnerabilities which is linked to from TFA.

Re:axfuzz

[shird]

I see Dranzer is an older ActiveX fuzzing tool, somewhat unrelated to the "BFF". I didn't really read the article properly. :P

hmmm...

[thatskinnyguy]

The worst case scenario is talking about worse case scenarios thinking about worse case scenarios and letting them possess you.

Linky?

[Anonymous Coward]

Oh FFS, you couldn't even link to the damn framework?

BFF?

[Fnord666]

BFF? What an unfortunate choice of acronyms.

Re:BFF?

[Daniel Dvorkin]

Because it's, like, the security researcher's BFF OMG ponies!

Good!!

[Panaflex]

I propose that every website which handles private data (credit, ssn, health, etc) should be integrating these kinds of tools into normal test procedures, both in development and on production mirrored sites.

Hear hear!