Fuzzing from First
Principles
Alisa Esage
Zero Day Engineering LLC
Off By One Security Podcast, September 2024
About me
Alisa Esage Шевченко*
Independent Vulnerability Researcher (2014+)
● Mostly low-level stuff, Hypervisors & Browsers
● Non-trivial exploit development <3
● First Female Winner of Pwn2Own contest (2021)
Professional Reverse Engineer since The Age of Empires II
● RE baseband & iOS bootloader most recently
Solo Entrepreneur & Community Leadership (2009+) Presenting these slides at Off By One Security
Podcast on 14th September 2024. Random
screen courtesy of podcast host Stephen Sims.
● Co-founded the First hackerspace in Russia (~2011)
This stream reached a record number of live
● Zero Day Engineering project (2021+) viewers!!
[Link] < SOTA training for
professional security researchers Watch the video recording here:
[Link]
* Russian citizen, Ukrainian surname :( 1XQ
Reality check
Google is continuously fuzzing its own software products using a broad
array of professionally maintained state-of-the-art fuzzers on a
distributed fuzzing cloud with tens of thousands fuzzing instances
(more?)
Researchers consistently come up with new 0-days in v8 and Chrome
And they find it by… fuzzing?!
Smart Fuzzing
🚫 Not necessarily: ✅ Ultimately, it comes down to:
● Scaling 1. Knowledge from First Principles
● Parallelization
● Code coverage guidance Know exactly what you’re doing -
● Augmenting with concolic execution and how it works - theoretical side
● Using the latest cool tool
2. Sound application in context
● Assisting fuzzing with specialized
hardware features
Leverage (1) to win adversarial
● …
games - practical/technical aspects
Ex. You spent three months writing a custom coverage-guided fuzzer and it didn’t
find any bugs in time budget. Meanwhile, your friend wrote a “dumb” specialized
fuzzer in a day and found a bug to win the contest in an hour. Who fuzzed smarter?
Part I. First Principles of Fuzzing
Enter Probability Theory
Probability & ops Probability Distribution
Given a random variable x: PMF:
p(𝑥) ∈ [0..1]: x = 𝑥
1. Dom(P): {x:𝑥i}, i ∈ k
Joint probability for independent variables: 2. ∀𝑥 ∈ x, 0 ≤ P(𝑥) ≤ 1
∀ 𝑥 ∈ x, 𝑦 ∈ y: p(y=𝑦, x=𝑥) = p(x=𝑥)p(y=𝑦) 3. ∑P(𝑥) = 1*
Conditional probabilities: Ex. Uniform PD:
p(y=𝑦|x=𝑥) = p(y=𝑦, x=𝑥) / p(x=𝑥)
p(x=𝑥i) = 1/k
Chain rule:
* normalised
p(x1,x2,…,xn) = p(x1)∏ni=2p(xn|x1,x2,…,xn-1)
Examples of common probability distributions
Modeling fuzzing of a simple program
Program: Then:
1. Probabilities:
1. Accept one - p(x=42) = 1/256 =
byte as 0.039 (3.9%)
input: x - p(x=0) = 1/256 =
x=42 x=0
2. If x = 42, 0.039 (3.9%)
print a 2. Success rate:
message - 255/2 failures on
3. Else if x = 0, average
proceed to - 1/127 ~ 0.0079
vuln (0.79%)
4. Other inputs 3. Error rate:
are invalid Input vector - r ~ 1-0.0079 ~
5. Random 0.9921 (99.21%)
fuzzing 4. Timing: 100 cps ~>
perspective 1 sec to vuln
Vs. program’s perspective
Program: Then:
1. Probabilities:
1. Accept one - p(x=42) = 0.5
byte as (50%)
input: x - p(x=0) = 0.5 (50%)
x=42 x=0
2. If x = 42, 2. Success rate:
print a - 100% (not
message applicable)
3. Else if x = 0, 3. Error rate:
proceed to - 0 (not applicable)
vuln
4. Other inputs
are invalid Input vector
5. Program’s
perspective
Modeling a more complex program
Program: Then:
1. Probabilities:
1. Accept an - p(x1=42, x2=0) =
array of 10 1/256*1/256 =
bytes 0.001521 (0.15%)
2. Single bytes x1 x2 - compounding
p = 0.001521
are tested 2. Error rate
3. If x[0] = 42 x0 - r ~ 99.85%
AND x[2] = p = 0.039 - Keeps growing up
0, proceed to the tree
vuln 3. Overall trend
4. Random - exponential loss
fuzzing of due to path
each byte IV explosion +
diminishing
probabilities
Analytic: Behavior of a simple random fuzzer
Program fuzzing: Then:
1. Tiny probability on
1. Accept an array each branch
of 10 bytes - p(x1=42) ~ 1/25610
2. Random fuzzing ~ 1/280
of the array x1 x2 2. Compounding:
p = ½^160
3. If x[0] = 42 - p(x1=42, x2=0) ~
AND x[2] = 0, x0 1/280 * 1/280 ~
proceed to vuln p = ½^80 1/2160
4. Else done 3. Probability of
reaching deeper
branches with a
fuzzer rapidly
IV drops to 0
Analytic: Behavior of a simple random fuzzer
Program fuzzing: Then:
1. Tiny probability on
1. Accept an array each branch
of 10 bytes - p(x1=42) ~ 1/25610
2. Random
Note: Here, fuzzing
probabilities are exaggerated by assuming the worst case 1/280 that
~ scenario,
of the
entire array
80-bit array is randomly
x2
x1fuzzed and tested as 2. Compounding:
p =one big number.
½^160 In practice,
3. If x[0] = 42 - p(x
probabilities will depend on a number of variables: specific fuzzing algorithm,
1
=42, x2=0) ~
width
80
ofAND
valuesx[2] = 0,
tested on branches, offset ofx0 each value into the array, and1/2
so on. * 1/280 ~
proceed to vuln p = ½^80 1/2160
4. MyElse
goaldone
with this is to show two key points: 3. Probability of
1) in real life non-deterministic fuzzing the probabilities of advancing reaching
into the deeper
program tree are terrible, and branches with a
fuzzer rapidly
2) just how much the probabilities can vary from the “ideal model”, depending on the
specific fuzzing algorithm and other factors; drops
IV and therefore, how steep the to 0
exponential path explosion curve can possibly get with an arbitrary choice of fuzzing
techniques.
Analytic: Behavior of a simple random fuzzer
unreachable
Then:
1. Tiny probability on
each branch
- p(x1=42) = 1/25610
= 1/280
x1 x2 2. Compounding:
p = ½^160
- p(x1=42, x2=0) =
x0 1/280 * 1/280 =
p = ½^80 1/2160
3. Probability of
reaching deeper
branches with a
fuzzer rapidly
IV drops to 0
Analytic: Behavior of a cov guided fuzzer
1 - branch discovery phase
Then:
Assume that 1. Still low
fuzzer is smart probability of
enough to fuzz discovering each
specific byte that branch
controls the x2 2. Still 99%+ error rate
x1
branch so we don’t p = 0.001521
and growing
get diminishing through the tree
x0
probabilities from p = 0.039 3. Saving successful
fuzzing a very branch-passing
large number (not inputs allows to
a real example - control the path
currently available explosion and
SOTA fuzzers can’t overall
do it) IV
exponential loss
Analytic: Behavior of a cov guided fuzzer
2 - known branch fuzzing phase
Then:
1. Probabilities are
improved!
- Saving a sample sets
p=1 on the branch
x1 x2 - Further probabilities
p = 0.039
compound slower
x0 2. Cost is ~linear
p=1 rather than
exponential!
3. Stable trend of vuln
discovery (assuming
a uniform
IV distribution of bugs)
4. Still 99%+++
error rate
“I wonder, what my smart fuzzer is doing…”
Popular opinion Reality
“Walking in the forest of Burning electricity while
program paths, intelligently producing heat 99+% of the
discovering new branches ☺” time 🤥
Part II. The Forest of Probabilities
Fuzzing actors as Probability Distributions
Fuzzer
Pf
1. Over time a fuzzer will
generate a finite* set
of discrete values
2. Algorithm imposes
constraints on
possible values of
values and their
probabilities
3. Fuzzer = PD:
* limited by program’s input width
Fuzzing actors as Probability Distributions
Fuzzer Program
Pf Pp
1. Over time a fuzzer will 1. Set of valid inputs
generate a finite* set 2. Valid input: pass at
of discrete values least one conditional
2. Algorithm imposes branch
constraints on 3. Algorithm imposes
possible values of constraints on
values and their possible values of
probabilities input and their
3. Fuzzer = PD: probabilities
4. Program = PD:
* limited by program’s input width
Fuzzing actors as Probability Distributions
Fuzzer Program Vuln.
Pf Pp Pv
1. Over time a fuzzer will 1. Set of valid inputs 1. A strict subset of Pp
generate a finite* set 2. Valid input: pass at 2. Specific values of
of discrete values least one conditional program inputs that
2. Algorithm imposes branch lead to vulnerabilities
constraints on 3. Algorithm imposes 3. PD:
possible values of constraints on
values and their possible values of
probabilities input and their
3. Fuzzer = PD: probabilities
4. Program = PD:
* limited by program’s input width
Pf
Pp
Pv
Fundamental Challenge of Fuzzing
Goal: Pf = Pv
SOTA: Pf ⊅ Pp ⊃ Pv
Secondary goal: r = 0
(follows from Pf = Pv)
SOTA: r = 99%+↑
Modeling fuzzing as a process (rough idea)
Fuzzing is a function:
R = F(Pf)
R: practical measure of “success” of specific input values
Optimization:
R’ = Opt(R, Pp) -> Opt(R, Pb) -> Opt(R, Pv)
Pf = F-1(R’)
Solve Fuzzing (Pf = Pv)*
1. Pf → P p
Idea: bring the set of fuzzer
inputs closer to the set valid
program inputs
Insight: fuzzer’s losses are
exponential in discovery
phase and linear past it. Here
we aim for latter stage
upfront
* is a hard problem, so we also look for less ambitious and more trackable solutions
in practice.
The probabilistic model has many solutions. Here as an example, I show four
“partial” solutions that can be trivially illustrated with my own past fuzzing
experiments.
Solve Fuzzing (Pf = Pv)*
1. Pf → P p 2. Pp → 0
Idea: bring the set of fuzzer Idea: minimize the set of
inputs closer to the set valid valid program inputs
program inputs
Insight: Random fuzzing
Insight: fuzzer’s losses are with small P_p is more
exponential in discovery efficient than smart
phase and linear past it. Here coverage-guided fuzzing of
we aim for latter stage the entire program (todo:
upfront proof)
* is a hard problem, so we also look for less ambitious and more trackable solutions
in practice.
The probabilistic model has many solutions. Here as an example, I show four
“partial” solutions that can be trivially illustrated with my own past fuzzing
experiments.
Solve Fuzzing (Pf = Pv)*
1. Pf → P p 2. Pp → 0 3. Pf → Pv
Idea: bring the set of fuzzer Idea: minimize the set of Idea: let the fuzzer “learn”
inputs closer to the set valid valid program inputs from past bugs
program inputs
Insight: Random fuzzing Insight: this always “tends”
Insight: fuzzer’s losses are with small P_p is more with a gap: eg, next bug is a
exponential in discovery efficient than smart novel one - unseen
phase and linear past it. Here coverage-guided fuzzing of previously. The gap is an
we aim for latter stage the entire program (todo: opportunity in itself
upfront proof)
* is a hard problem, so we also look for less ambitious and more trackable solutions
in practice.
The probabilistic model has many solutions. Here as an example, I show four
“partial” solutions that can be trivially illustrated with my own past fuzzing
experiments.
Solve Fuzzing (Pf = Pv)*
1. Pf → P p 2. Pp → 0 3. Pf → Pv 4. Pf → 1
Idea: bring the set of fuzzer Idea: minimize the set of Idea: let the fuzzer “learn” Idea: Collapse it (theoretical)
inputs closer to the set valid valid program inputs from past bugs
program inputs Insight: manifestation ???
Insight: Random fuzzing Insight: this always “tends”
Insight: fuzzer’s losses are with small P_p is more with a gap: eg, next bug is a
exponential in discovery efficient than smart novel one - unseen
phase and linear past it. Here coverage-guided fuzzing of previously. The gap is an
we aim for latter stage the entire program (todo: opportunity in itself
upfront proof)
* is a hard problem, so we also look for less ambitious and more trackable solutions
in practice.
The probabilistic model has many solutions. Here as an example, I show four
“partial” solutions that can be trivially illustrated with my own past fuzzing
experiments.
Reality check
~100% of software security bugs exploited at Pwn2Own Vancouver
2024 were found with manual program analysis
Meaning: for purposes of adversarial offensive security research, fuzzing is so bad
that researchers don’t even try it?
Actually, use of scrappy custom ultra specialized fuzzers is common in these
scenarios (optimizing P_f intuitively), a bug will look like a manual find in this case.
But researchers normally won’t publish it because it isn’t considered “smart fuzzing”.
Case studies
Summary: concrete examples of F improvement
1. Pf → P p 2. Pp → 0 3. Pf → Pv 4. Pf → 1
Idea: bring the set of fuzzer Idea: minimize the set of Idea: let the fuzzer “learn” Idea: Collapse it (theoretical
inputs closer to the set valid valid program inputs from past bugs solution)
program inputs
Examples: Examples: Side note: much of this
Examples: has been empirically
discovered by the fuzzing
- Cut out a piece of code and - Take one of past bugs, community over many
- Mutate valid program fuzz it separately of the entire reuse it as a fuzzing years of practical
inputs. (radamsa) program. template. research, and
- Generate valid inputs implemented in various
with context free - Hook into a the code to Note, this is a crude 'fuzzer' tools and best practices,
grammars. (dharma) which validates this
isolate fuzzing of a specific that has a very small P_f ~
- Reuse existing parser theoretical model!
portion. (frida) P_v for one specific vuln.
code to gen F inputs.*
Time to start thinking
- Coverage feedback forward from the model to
- Use one particular valid - Reuse the corpus of
(afl, winafl, libfuzzer) guide new fuzzing
input as a fuzzing template past bugs by feeding it
to isolate a specific portion of into the fuzzer as input improvements, rather
* Similar to genai, where the than stumble on them
the program tree as a target. corpus.
originally analytical model is empirically and intuitively.
reversed to produce outputs.
Model applications: from basics to advanced
High level Low level
Scale: Probability Distributions Scale: Branch/instruction
Goal: Pf → Pv Goal: max(p) | min(r)
Ex.(Idea) Quantify the difference between Ex.(Idea) Find a way to make fuzzer
PDs -> cost function -> optimization aware of width and/or position of
algorithm over fuzzing procedures or condition value on a branch => higher
fuzzer code probability of finding the value => faster
branch discovery + lower error rate
Conclusions
1. Fuzzing from First Principles enables us to compete with large scale
“smart” fuzzing; it doesn’t have to be manual analysis
2. Coverage guided and scaled fuzzing is ok for long-running projects
with little or no constraints - ex: part of dev cycle (but still very far
from reasonable in current SOTA)
3. Cov guided and scaled fuzzing seems to be a bad choice in
adversarial games of offensive security (0-days, competitions, bug
bounties)
4. Improve Pf instead of glossing over the failure scaling madness
5. Start thinking forward from the theoretical model to guide
advancements in fuzzing, rather than stumble on
improvements empirically and intuitively in practice.
Discussion
contact@[Link]
@alisaesage