Babysitting An Army Of Monkeys - WordPress

Babysitting an Army ofMonkeysAn analysis of fuzzing 4 products with 5 lines ofPythonAn analysis of fuzzing 4 products with 5 lines ofPythonCharlie MillerIndependent Security Evaluatorscmiller@securityevaluators.com

I talk about how to findbugs in this talkI don’t talk about thedetails of the bugs IfoundIf you want 0-days, runmy 5 lines of PythonYou’ll find some.I guarantee it!and you’ll feel all warmand fuzzy inside

Who I amFirst to hack the iPhone, G1 PhonePwn2Own winner, 2008, 2009AuthorMac Hackers HandbookFuzzing for Software Security Testing and QualityAssuranceMedia whore

OverviewThe fuzzing setupFuzzing PDF’s, Preview and Adobe Acrobat ReaderFuzzing PPT’s, OpenOffice and MS PowerPointFuzzing “truths” revealed

About this talkMost fuzzing talks take one of two formsI fuzzed and found this/these bugsHere is a new, smarter way to fuzzThese talks are about success, but real fuzzing is about failure,i.e. most test cases don’t crash the targetVery few talks that give realistic pictures of actual fuzzingBy sharing results, both positive and negative, we can learnabout fuzzing and improve our techniques

Other talks to check outFuzz by Number, Charlie Miller, exploitable and Effective Fuzzing Strategiesas a Regular Part of Testing, Jason Shirk, ffectivEffective Fuzzing Strategies, David Molnar andLars Opstad, CERT-pre

Questions to ponderHow many crashes can you expect?How many of these are unique?How many are “exploitable”?How important is the initial file when fuzzing?Are some bugs harder to find than others?How do post analysis tools compare?When have you fuzzed enough?How hard do various vendors fuzz and how many bugs dothey find?

A Historical PerspectiveMicrosoft Windows Vista File Fuzzing effort15 months, 350mil iterations, 250 file parsers 1.4mil iterations per parser (on average)300 issues fixedThis talk3 months, 7mil iterations, 4 parsers 1.8m iterations per parser (on average)However, quality is more important than quantityMy quality is purposefully very poor, should find much less thanMS!

The Fuzzing Setup

Fuzzing typesDumb fuzzing (mutational)Take a good input (file/packet/command line/etc) andadd anomalies to itVery easy to conductSmart fuzzing (generation based)Create invalid inputs from “scratch”, i.e. RFC, REVery hard, but explores every detail of protocol

Compromise for the lazyDumb fuzzing with lots of different initial filesSingle dumb fuzzing session will only fuzz theprotocol ‘features’ present in the initial fileWith enough initial files, hopefully you canfuzz all the ‘features’Still are screwed by things like CRC,compression, etc.

Selection of initial filesDownload every file you can find on the InternetFind the minimal subset that has the same code coverageas the large setExample: PDFFound 80,000 PDF’s on InternetUsed Adobe Reader Valgrind in Linux to measurecode coverageReduced to 1,515 files of ‘equivalent’ code coverageSame bang as fuzzing all 80k in 2% of the time

The 5 lines of PythonJust change random bytes to random valuesDon’t insert bytes, remove bytesEasiest (dumbest) conceivable way to fuzzShouldn’t find any bugs.numwrites random.randrange(math.ceil((float(len(buf)) / FuzzFactor))) 1for j inrange(numwrites):rbyte random.randrange(256)rn random.randrange(len(buf))buf[rn] "%c"%(rbyte);numwrites random.randrange(math.ceil((float(len(buf)) / FuzzFactor))) 1for j inrange(numwrites):rbyte random.randrange(256)rn random.randrange(len(buf))buf[rn] "%c"%(rbyte);

Other detailsRan it in a parallelized way using my fuzzing framework, TiamatUsed 1-5 Mac OS X computers, some of them virtualIncluding 2 Pwn2Own prizes!Open/Closed files using AppleScriptMonitored CPU activity to know when to launch next fileRan fixed number of iterations of each file (2000 or 1200)Estimated for 3 week runsRecorded repeatable crashes (either native or with glibmalloc)Originally, this slide was my whole talk.

The part aboutbabysittingThings didn’t always go smoothly

At least my kids learned how to notreport bugsClick“Ignore”

The vendors could at leastpay my power bill!Powergoesway up!

Tools usedlibgmalloc: uses guard pages to find when heapoverflows first occur (like libefence), OS XCrashWrangler: Apple tool to bin crashes anddetermine exploitability, OS Xmemcheck: Valgrind tool which simulatesprogram execution and records invalid memoryoperations, Linux and OS X!exploitable: MS tool used to bin crashes anddetermine exploitability, Windows

Final thoughts: Fuzzing asFilteringFuzzing isn’t about creating and running testcase, it’s about filteringStart with a ton of test casesFilter those to the ones that cause a crashFilter those to the ones that represent uniquecrashesFilter those to the ones that are exploitable

AdobeAcrobatReader(PDF)(PDF)

Reader statsReader 9.2.03,036,000 test cases testedMaximum test cases/min 132Minimum test cases/min 7

8440expl17of33 5 UseProbablyProbablynotreads11Invalidcras100 uniqueEIPsoita ilesfuzzedhesbleefiles3 exploitable34 unique20 unique*2 Processterminated*valgrind failed frequentlycause acrobat has problems even with clean files

Points of interestAcrobat Reader, under valgrind, has lots of errorsExamples: mismatched malloc/freeDon’t know how it runs normally.Ignoring these errors makes you miss lots of crashes100 unique EIPs, around 20-40 repro’d with binning tools3-4 exploitables, according to toolsDisagreement about what files cause what crashes and whichare exploitable

Comparisons ndCrash 1Exploitableis exploitable yesProcess terminatedCrash 2Exploitableis exploitable noValgrind failedCrash 3Exploitableis exploitable noUninitialized variableCrash 4Exploitableis exploitable noProcess terminatedCrash 5Probably Exploitableis exploitable noValgrind failedCrash 6Probably Exploitableis exploitable noValgrind failedCrash 7Probably Exploitableis exploitable noValgrind failedCrash 8Probably Exploitableis exploitable noValgrind failedCrash 9Probably Exploitableis exploitable noInvalid writeCrash 10Probably Exploitableis exploitable noUninitialized variableCrash 11Probably Exploitableis exploitable noInvalid writeCrash 12Probably Exploitableis exploitable noInvalid writeCrash 13Probably Exploitableis exploitable noInvalid writeCrash 14Probably Exploitableis exploitable noValgrind failedCrash 15not on winis exploitable yesUninitialized variableCrash 16not on winis exploitable yesUninitialized variable

Number of times each crashoccurred

Reader crash rarity info100 different crashes57 were found exactly onceEither rare or lots of manifestations of one bug81 were found less than 10 timesRare?7 were found more than 60 timesCommon bugs4 were found more than 100 timesVery common bugsOne crash found 1452 timesThis one crash is responsible for 56% of crashes in the testing

Choice of initial file1515 different filesCrashes at 100 different EIP’sAll crashes occurred when fuzzing only 192 filesNo crashes from 87% of initial files!!!All files but one found between 1-3 crashes1 file found 32 crashes (all but one with invalid EIP)Probably one (really nasty) bugThese bugs all coalesced when used libgmalloc

# Crashes found per file

To find an exploitableFor the 4 !exploitables, lets see info about other crashesthat crashed at the same EIPCrash 1: 2 files, each crashed once or twiceCrash 2: 2 files, each crashed there onceCrash 3: 2 files, each crashed there twiceCrash 4: 42 files crashed there from 1 to 63 timesEarliest test case to find one of these was the 486thiterationLast was the 1923rd iteration (of 2000)

More on findingexploitablesFind the first 3 exploitables in 9 test cases out of 3 millionOnly 6 of 1515 files generate the first 3If you fuzz each file 500 times, you find 1 exploitable1000 times, you find 21500 times, you find 32000 times, you find 4What happens if you iterate 3000, 100000, 100000000?

How many iterations(theoretical)Run long enough, your fuzzer will find every bug (it iscapable of finding)Presumably, this gets harder and harderEnd up with some idealized graph of iterations vs bugsfoundWhen this curve becomes sufficiently flat, stop fuzzing Stop# bugs foundfuzzing# iterations

# iterations to find crashesMore iterations would have probably found more bugs(Curve isn’t flat yet)

“Fuzzc 1, ing2009Reader LessoOct 13, 2009ns9.2Learned”Progress?Probably not exploitable4Unknown17Probably exploitable8Exploitable4

Dec“Fuzz1,2009ingReader LessonsLearned”Progress?Feb 16,Jan 13, ly not exploitable4Unknown17Probably exploitable8Exploitable4Oct 13, 20099.2

Preview(PDF)(PDF)

Preview General InfoDefault Mac OS X PDF viewerTested: Mac OS X 10.6.1These bugs show up in Safari too2,790,000 test cases testedMaximum testcases/min: 160Minimum testcases/min: 4Total run time: Approximately 3 weeks

46 Use of129Invalidreads17Invalid writesuninitializedvariablesncomplete data)2,790,000fuzzedfiles1056 repro’d281 unique61 “exploitable”1373 uniqueEIPs157,337 crashes(5.6%)228 unique36 Processterminated

Talking pointsUmm.they haven’t fuzzed thisno !exploitable since Preview OS X onlyAround 250 unique crashesAround 60 exploitableThis is an overestimate, at least one bugmanifests itself in lots of crashes andlibgmalloc fails to bin it properly

Number of times each crashoccurred(by EIP)(by EIP)

More crash rarity infoCrashes at 1373 unique EIP’s791 EIP’s were found exactly one time (57.6%)Either rare or lots of manifestations of one bug341 were found between 1 and 10 timesrare?82 were found more than 100 timesCommon bugs26 were found more than 1000 timesVery common bugsOne EIP found in crashes 15,368 times

# times exploitable crashoccurred

“Exploitables”“exploitable” crashes at 61 EIP’s according tolibgmalloc crashwranger1 EIP was found 155 times42 were found only oncelots of rare ones or a few nasty ones56 were found less than 10 times

# of crashes at EIP byinitial file

File choices1395 files1 file found 58 “unique” crashes, by EIP68 files (5%) found 20 or more differentcrashes162 files (12%) found no crashes440 files (31%) found 2 or fewer crashes

Number of files which find eachexploitable

Files and exploitables61 crashes exploitable (by EIP)49 files found the most common exploitable crashOnly 2 crashes were found by more than 10 startingfiles42 (69%) crashes were found by exactly onestarting file50 (82%) crashes were found by at most twostarting files

More on file choicesThese 1399 files were not randomly chosen,they are very special!Yet, even with these, almost a third find almostnothingSo.If you randomly pick files to fuzz with, youprobably won’t find any interesting bugs

Should have fuzzedlongercrashes and exploitables found by iteration

Fixes through time (unique 20102010Nov19,2, 2009Sept10,2009175crash177 crashes228187es(by EIP)(byEIP)

Fixes through time, bytype10.6.210.6.12010 014.0.5

All bugs will be goneby.according to linear regression all bugs will befixed sometime in 2012

iPhoneiPhone 3.1.2, not jailbrokeniPhone doesn’t have Preview, but MobileSafari will displayPDF’sMuch of the complexity of PDF’s is ignored, e.g. fontsRecall Preview had 281 unique crashes (libgmalloc)22 crashed MobileSafari, all at unique pc7.8% of crashes affected bothNone of the corresponding Preview crashes were“exploitable”

PDF showdown100 crashes30-40 unique3-10 exploitable1373 crashes230-280 unique30-60 exploitable

Open Office(PPT)(PPT)

OpenOfficeOpenOffice 3.1.1, impress610,400 test cases testedMaximum testcases/min: 15Minimum testcases/min: 1Total run time: Approximately 3 weeks

122193expl42of68 8 UseProbablyProbablynotreads14Invalid205 uniqueEIPs40369crashes(6.6%)oita riablesuniquexploitable496 filesble610,400 fuzzed fileshese10 exploitable105 crashes27 unique186 crashes36 unique7 Processterminated

Some thoughtsAround 200 crashesDon’t know why half don’t crash underlibgmallocAround 30-70 unique crashesAround 10-12 exploitable crashes, as reportedby tools