Source Extract — M.S. Thesis (EF-Fuzz), Sejong University, 2020

# Source Extract — M.S. Thesis (EF-Fuzz), Sejong University, 2020

AI Summary

Purpose:

• Faithful, section-by-section extraction of the M.S. thesis PDF for future reference, so the wiki page can stay short and agents can cite exact details without re-OCRing the PDF.

Key points:

• Source PDF: /Users/khw/Google Drive/내 드라이브/세종대학원/성과/석사학위논문_김현욱_최종본.pdf (46 pages).
• Captures: title, committee, abstract (KR+EN), TOC, the EF-Fuzz design (two schedulers + timer + PSO), the evaluation tables (Table 2 feature matrix, Table 3 firmware + per-target numbers), results, conclusion, references.
• "Claim vs inference" is marked throughout: bracketed [EXTRACT] = directly from the PDF; [INFERENCE] = my reading; uncertainty labels used where the PDF is ambiguous or OCR was noisy.

Relevant when:

• You need exact numbers, formulas, firmware IDs, or reference list from the thesis.

Do not read full document unless:

• The wiki summary [[../../wiki/academic/master-thesis.md]] is enough for your task.

Linked documents:

• [[../../wiki/academic/master-thesis.md]] — the compiled wiki page.

Open Questions

• Table 3 CVE/EDB IDs were split across lines by PDF text extraction (e.g. "CVE-2016-1\n558", "CVE-2018-1\n9240"); the reconstructed IDs below are best-effort and marked Needs confirmation.
• Two energy-allocation formulas (CoE and the extended CoE) render as empty/garbled math in text extraction; only their described semantics are captured, not the exact symbolic form.

Details

Front matter [EXTRACT]

• KR title: 결합된 에뮬레이션을 이용한 임베디드 시스템의 효율적인 커버리지 가이드 퍼징 연구
• EN title: Research on Efficient Coverage-Guided Fuzzing for Embedded System Using Combined Emulation
• 지도교수 윤주범; 정보보호학 석사학위논문; 2020년 12월; 세종대학교대학원 정보보호학과; 김현욱.
• Approval page (p4): 심사위원장 박기웅, 심사위원 김영갑, 심사위원 윤주범, 2020년 12월.

국문초록 / Abstract [EXTRACT]

• Embedded devices are everywhere and hold personal data; manual analysis across heterogeneous devices is near-impossible, so embedded fuzzing is actively researched.
• Firm-AFL (USENIX 2019) focused on emulation to speed up fuzzing, but code coverage — a key fuzzing performance metric — had not been applied to embedded fuzzing, so prior embedded fuzzers have low coverage and miss deep vulnerabilities.
• This thesis focuses on the mutation process and strengthens its scheduler to achieve higher code coverage, proposing EF-Fuzz; experiments found unknown (0-day) vulnerabilities using EF-Fuzz.
• Keywords: Fuzzing, embedded system, firmware fuzzing, firmware, code coverage.
• English author rendering printed in the Abstract page: "Kim Hyun-wook", "Department of Computer and Information Security, The Graduate School, Sejong University".

Table of contents [EXTRACT]

• I. 서론 (Intro)
• II. 관련연구 (Related work): 1. Fuzzing (black/grey/white box); 2. Mutation-based fuzzing (seed generation, mutation-operator selection scheduler); 3. Embedded systems (firmware, emulator, QEMU, Combined Emulation).
• III. EF-Fuzz 설계 (Design): 1. Efficient Energy Allocation Scheduler; 2. Optimized Mutator Scheduler (2.1 customized PSO, 2.2 PSO probability sets, 2.3 scheduler timer).
• IV. EF-Fuzz 성능평가 (Evaluation): 1. environment; 2. results (2.1 code coverage, 2.2 crashes).
• V. 결론 (Conclusion). 참고문헌 (References). Abstract.
• Figures: Fig1 fuzzing stages; Fig2 black-box; Fig3 mutation seed-gen structure; Fig4 AFL mutation-stage scheduler; Fig5 firmware structure; Fig6 full-system vs user-mode emulation; Fig7 combined emulation diagram; Fig8 EF-Fuzz structure; Fig9 PSO probability-distribution normalization; Fig10 target firmware code coverage; Fig11 target firmware crashes.
• Tables: Table1 AFL heuristic mutation operators (11); Table2 target-fuzzer feature matrix; Table3 experiment firmware info.

I. 서론 (Introduction) [EXTRACT]

• NIST vulnerability statistics [ref 1]: from 2017 the number of vulnerabilities found rose to roughly 3–4x of prior years (as stated).
• Embedded firmware vulnerabilities cause harm via authentication issues, memory corruption, management issues; attackers must be outrun.
• Three categories of embedded fuzzing: (1) serial/UART data to the real device; (2) hybrid of real device + emulation; (3) emulate the firmware and fuzz the virtualized system. Real-cable is most accurate/compatible but limited by device resources, monitoring difficulty, so research trend = pure emulation.
• Emulation problems: (1) compatibility (diverse CPU/peripherals/kernel/filesystem make emulating many devices nearly impossible); (2) processing speed/throughput (emulation overhead, worsened by limited host resources).
• Gap: prior emulation work [refs 11,14] improved compatibility/speed but did NOT improve fuzzing performance — leading to the three stated problems (narrow path exploration, few mutation operators chosen, random operator choice → high variance, lower crash rate).
• This thesis adds two improved greybox seed-generation schedulers (efficient energy allocation; optimal mutation-operator selection via PSO) to an existing fuzzer to form EF-Fuzz.

II. Related work [EXTRACT]

• Fuzzing = software testing: random inputs, repeated execution, monitor for crashes. 6 steps: identify target+input; mutate/generate input randomly; fuzz target with generated input; monitor execution; analyze unexpected input; record if crash.
• Black-box [refs 19-21]: no program analysis, random input, low coverage, can't reach deep paths.
• White-box [refs 22-24]: uses symbolic execution to solve path constraints and reach deep paths; high coverage but high time/resource cost (bad for automated systems).
• Grey-box: uses instrumentation; runs mutated/random testcases, collects info, widens coverage; between black and white box; most widely used. This thesis builds on AFL-based greybox fuzzers [ref 18].
• Mutation-based vs generation-based [refs 7,25,26]: generation-based needs a format spec (complete, handles dependencies, but slow and format-quality-dependent); mutation-based needs no format, mutates seeds, easy to automate, uses heuristic operators for diverse inputs.
• AFL seed-generation process (Algorithm 1): seed I → queue Q; seed-selection scheduler picks t with assigned ENERGY; loop MUTATOR generates t'; if t' crashes add to crash set; else if new path add t' to Q; repeat until timeout/abort.
• Table1 — 11 AFL heuristic mutation operators [EXTRACT]: 1 Bitflip, 2 Byteflip, 3 Arithmetic inc/dec, 4 Interesting values, 5 User extras, 6 Auto extras, 7 Random bytes, 8 Delete bytes, 9 Insert bytes, 10 Overwrite bytes, 11 Cross over.
• Mutation-operator scheduler has 3 stages (Fig4): Stage 1 selects operators in order (newly found seeds re-enter Stage 1 first, queue must drain Stage 1 before Stage 2); Stage 2 adds 4 more operators and picks randomly; Stage 3 = cross over, after which non-productive seeds are deleted.
• MOptAFL [ref 25] finding cited: most processes spend lots of time in Stage 1 and rarely use Stages 2/3 (because seed mutation counts grow exponentially and new-path seeds re-enter Stage 1). Prior work [ref 26]: Stage 2 has more efficient operators, and the most efficient operators bitflip 1/1, 1/2 are used too little. → motivates faster Stage-2 entry (the design chapter).
• Embedded systems: limited function, real-time, ROM/RAM/Flash instead of HDD; hardware (processor, memory, peripherals: Network/Button/UART) + software (firmware, embedded OS, apps). Firmware = software controlling hardware, stored in non-volatile memory (ROM/PROM); structure (Fig5): Boot Loader → Kernel → File System → Programs.
• QEMU [ref 29]: open-source CPU emulator (ARM/MIPS/x86). Full-system-mode = whole OS in a VM; User-mode = run a process compiled for one CPU on another. Full-system: high compatibility, high overhead/slow. User-mode: fast but can't handle certain target-process system calls.
• Combined Emulation [refs 11,30] (Fig7): merges both modes. 6-step loop (steps 3–6 repeat): (1) extract firmware, emulate in full-system mode; (2) trigger a specific system call, snapshot/copy full process memory; (3) in user-mode, virtualize the target process with the saved memory file from step 2/6; (4) when a specific system call occurs in user-mode, save current memory to file; (5) restore that memory file into full-system mode; (6) full-system handles the system call, saves resulting memory back to file. → high throughput, high speed, high compatibility.

III. EF-Fuzz Design [EXTRACT]

• EF-Fuzz uses the combined emulation of §2.3.4 (proven throughput/speed/compatibility), and to widen coverage: when selecting a seed from Q, reduces the exponential energy allocation so the operator scheduler stays less time in Stage 1, and replaces random Stage-2 selection with a modified PSO that picks efficient operators. Fig8 = overall structure.
• 1. Efficient Energy Allocation Scheduler:

- Allocating much energy (many mutations) to one seed wastes time on that seed, blocks exploring other seeds' paths, keeps the scheduler in Stage 1. - Early greybox energy used monitored values: time to generate a new seed, a seed's code-coverage range, process execution time. As research progressed, fuzzing favored mutating one seed more, adopting Cut-off Exponential (CoE) [ref 31], making per-seed energy grow exponentially. [INFERENCE: the CoE formula on p19-20 did not extract cleanly; semantics only.] - CoE variable meanings (as described): Y = how many mutations produced the current new seed; (term) = 2 to the power of how many times the seed has been selected from the queue; R = energy upper bound to limit exponential growth; one term = count of newly generated seeds; another = number of paths explored from start to now; "until next path" = mutate until the next path is found. - Proposed EXTENDED CoE: allocate energy inversely proportional to the number of newly generated seeds, so a queue-selected seed gets LESS energy → less time in Stage 1, faster Stage-2 access.

• 2. Optimized Mutator Scheduler:

- Best operator differs per program/seed (A→bitflip, B→byteflip). Goal: at runtime, raise priority of operators that find new paths, forming an optimal probability distribution to choose the next operator. - Operates in Stage 2 (the disordered stage); creates a particle per operator; finds each particle's personal best probability to build the whole-operator optimal distribution = customized PSO.

• 2.1 Customized PSO [EXTRACT]: based on PSO (Particle Swarm Optimization) by James Kennedy & Russell C. Eberhart [refs 25,32], adapted to fuzzing mutation. Terms: each particle = a Stage-2 operator; the set = LS (Local Swarm); best in LS = LBP (Local Best Particle); one seed has its LBP; probabilities aggregated across seeds = GS (Global Swarm); best in GS = GBP (Global Best Particle). Initial run: no priority data, so each operator gets equal energy on the initial seed to compute the initial distribution. [Note: PDF prints "Bast" — typo for "Best".]
• 2.2 PSO probability sets [EXTRACT]: two parts — (1) the per-executed-seed probabilities, (2) the GS holding their sums. To collect the initial LBP, each particle (operator) mutates with fixed energy E; measure N = number of seeds generated from newly found blocks/crashes; compute each particle's probability from N. GS particle = sum of Local Swarm particles divided by LS count. Subsequent runs carry the previous GS probabilities into the current set; LBP selected and fuzzed; probabilities update in real time as mutation count and new-seed count change, so priorities shift; a high-priority operator keeps being chosen until its priority drops. Fig9 illustrates normalization of the distribution. Caveat: at long runtimes, even reduced energy grows exponentially, so PSO Stage-2 use is heavy early but after ~10+ hours the number of Stage-2 passes decreases.
• 2.3 Optimized Mutator Scheduler Timer [EXTRACT]: because long runtimes inflate even the extended-CoE energy, a selected seed gets stuck in Stage-1's first 6 operators and rarely meets the optimal operator. Solution: parameter L sets a timer in minutes; if Stage 1 finds no new path within the time, it stops Stage 1 and jumps to Stage 2. Example: L 10 = if no new path in 10 minutes in Stage 1, enter Stage 2 and use the Optimized Mutator Scheduler.

IV. Evaluation [EXTRACT]

• Compared 4 fuzzers: EF-Fuzz (this thesis), Firm-AFL [ref 14] (AFL applied to firmware), AFLfast [refs 15,35] (Efficient Energy Allocation), AFLgo [refs 33,34] (specific-path-concentration fuzzing). Measured code coverage and crash counts.
• Environment: CPU i5-6400 @ 2.7 GHz, 8.0 GB RAM, Ubuntu 16.04. 7 firmware images.
• Table 2 — feature matrix [EXTRACT]:

• Table 3 — experiment firmware + Firm-AFL vs EF-Fuzz per-target numbers [EXTRACT, IDs Needs confirmation due to line-split OCR]. Columns: crashes / Total Paths / new edges on (%).

- [INFERENCE] "Total Paths" = total paths found; "new edges on (%)" = proportion of block-entry constraints solved. Per-target measured every 4h; each firmware 24h x 10 runs, averaged.

• 2.1 Coverage results [EXTRACT]: top 2 = AFLfast and EF-Fuzz (both have Efficient Energy Allocation), ~2–3x ahead of bottom 2; the Efficient Energy Allocation feature alone explains the top-2/bottom-2 gap (less Stage-1 time, faster Stage-2 entry, more operators). Among top 2, EF-Fuzz beats AFLfast due to the Optimized Mutator Scheduler (both reach Stage 2 fast, but EF-Fuzz computes operator efficiency to pick better operators → more paths, more constraints solved).
• 2.2 Crash results [EXTRACT]: EF-Fuzz top on all firmware; other fuzzers found similar crash counts to each other; even the two coverage-top fuzzers differ greatly on crashes — attributed to the Optimized Mutator Scheduler. "new edges on" (constraint-solving) is highlighted as very important for crash discovery: entering blocks (solving constraints), not just exploring many paths, drives crashes; a new-path seed meeting an efficient operator raises crash probability.
• Comparison to Firm-AFL base [EXTRACT]: EF-Fuzz shows the same speed/throughput as Firm-AFL (reuses its combined emulation) and adds the two schedulers to improve coverage and crashes, exploring more paths/crashes than prior work (per Table 3).
• Headline gaps [EXTRACT]:

- Coverage: largest gap on TV-IP110WN — EF-Fuzz ~6.4x more paths than worst fuzzer AFLgo, and ~4.1x more than Firm-AFL. Smallest gap on DIR-815 ~2.5x. - Crashes: top fuzzer always EF-Fuzz; worst fuzzer varies. Largest crash gap on DIR-817(LW): ~2.2x vs Firm-AFL. Smallest crash gap on DIR-815: ~0.8x vs AFLfast (value as printed). - 0-day: beyond the 7 targets, continued experiments found a 0-day in "DIR-825 Rev.B 2.10B02".

V. Conclusion [EXTRACT]

• Automated firmware vulnerability analysis is essential as IoT/embedded devices proliferate; embedded devices holding personal data must be patched fast.
• Building on emulation-only prior work, the thesis proposes EF-Fuzz, which considers high code coverage.
• EF-Fuzz uses part of Firm-AFL's tech (two emulators for compatibility + efficiency) and maximizes fuzzing by efficient energy allocation on queue-selected seeds and optimal mutation-operator selection.
• Experiments proved performance gains over prior firmware fuzzers and the efficiency of the improved mutation process, and found a previously unknown vulnerability.
• Limitation: emulation automation is limited by the huge diversity of embedded products.
• Future work: improve emulation-automation so more embedded systems can be virtualized, and combine symbolic execution [ref 36] to further improve EF-Fuzz.

References (verbatim anchors, abbreviated) [EXTRACT]

• [1] NIST NVD vulnerability search. [7] Manes et al., "The Art, Science, and Engineering of Fuzzing: A Survey", IEEE TSE 2019. [11] Yaowen Zheng et al., "Firm-AFL: High-Throughput Greybox Fuzzing of IoT Firmware via Augmented Process Emulation", USENIX ATC 2019. [14] FirmAFL repo (github zyw-200/FirmAFL), 2019. [18] M. Zalewski, AFL. [24] Stephens et al., "Driller", NDSS 2016. [25] Lyu et al., "MOPT: Optimized Mutation Scheduling for Fuzzers", USENIX ATC 2019. [29] F. Bellard, "QEMU", USENIX ATC 2005. [30] Henderson et al. (PANDA / whole-system dynamic binary analysis), ISSTA 2014. [31] Smolinsky, "Discrete Power Law with Exponential Cutoff and Lotka's Law", 2017. [32] Kennedy & Eberhart, "Particle Swarm Optimization", IEEE 1995. [33] Böhme et al., "Directed Greybox Fuzzing" (AFLgo), CCS 2017. [35] Böhme et al., AFLfast, 2016. [36] King, "Symbolic Execution and Program Testing", ACM 1976. (Full list pages 33–36 of the PDF.)