Faster and Better: Detecting Vulnerabilities in Linux-based IoT Firmware with Optimized Reaching Definition Analysis

Faster and Better: Detecting Vulnerabilities in Linux-based IoT Firmware with Optimized Reaching Definition Analysis

Speakers: Zicong Gao

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=z7_WnBNqsOU

Overview

The proliferation of Internet of Things (IoT) devices has introduced unparalleled convenience but concurrently escalated security risks. A significant portion of these risks stems from taint-style attacks, where untrusted external inputs can flow into sensitive operations within device firmware, leading to severe consequences such as data breaches or device compromise. With up to one billion IoT devices reportedly attacked in 2021, and firmware often being closed-source and difficult to update, the urgency for robust vulnerability detection mechanisms is paramount. While fuzzing is a powerful technique for software vulnerabilities, its application to IoT firmware is hampered by hardware dependencies and low success rates in rehosting, as evidenced by state-of-the-art solutions like FirmAE only emulating 79% of network services.

Static analysis emerges as a more practical and scalable alternative, circumventing the need for hardware emulation. However, existing static taint analysis solutions—such as DTaint, KARONTE, SaTC, and Emtaint—have struggled with efficiency and effectiveness, frequently yielding high false negatives (missing vulnerabilities), false positives (reporting non-existent issues), and prohibitive time costs. This talk introduces HermeScan, a novel static taint analysis framework specifically designed to overcome these limitations. HermeScan leverages an optimized Reaching Definition Analysis (RDA) applied directly to the VEX intermediate representation (IR) of binaries to pinpoint taint-style vulnerabilities in Linux-based IoT firmware.

HermeScan addresses three critical challenges: the construction of incomplete Control Flow Graphs (CFG) and the loss of source points, the prevalence of high false positives due to imprecise source identification, and the significant time costs associated with analyzing numerous program paths. Its contributions include a lightweight, on-demand, context-sensitive RDA solution that enhances effectiveness, accuracy, and efficiency. Through its prototype implementation, HermeScan has already discovered 87 zero-day vulnerabilities in real-world devices, demonstrating its practical utility and superior performance compared to existing state-of-the-art tools.

Background

▶ Watch: Introduction: IoT vulnerabilities and HermeScan overview (0:00)

The security landscape of Linux-based IoT devices, particularly routers, is frequently marred by taint-style vulnerabilities. The typical attack scenario involves an adversary injecting arbitrary data over a network. This data is first processed by front-end files (e.g., JavaScript, HTML) in the firmware, then propagates to back-end Web service programs, and eventually to handler programs that control device operations. Crucially, during this process, various shared library files are loaded. The primary concern arises when this untrusted data reaches unsafe functions within the "border binaries"—the backend programs like Web servers or integrated httpd services—that directly interact with network inputs. HermeScan specifically targets common taint-style vulnerabilities such as buffer overflows (CWE-119), OS command injections (CWE-78), and other related flaws.

Taint analysis is a foundational technique in software security, abstracting a program's data flow into a 3-tuple: sources, sinks, and sanitizers.

• Sources are entry points where untrusted or dangerous data enters the program from external environments. Identifying these can be a manual or automatic process.
• Sinks are critical code locations where security properties could be violated if tainted data reaches them without proper sanitization.
• Sanitizers are functions designed to filter, validate, or transform dangerous data into a safe format, thereby breaking the taint flow.

The overarching goal of taint analysis is to trace specific execution paths from a source to a sink, indicating a potential vulnerability. Efficient path merging strategies are essential to mitigate redundant analysis.

Reaching Definition Analysis (RDA) is a lightweight data flow analysis technique. It determines, for a definition d of a variable v at program point p, whether d can "reach" program point q without v being redefined along any path. In the context of taint analysis, p can be considered a source and q a sink, with d representing the marking of input as tainted. A key advantage of RDA is its path-insensitivity, meaning it does not explore every possible branch like symbolic execution, thereby avoiding the notorious state explosion problem. As a "may-analysis," RDA computes a fixed point, allowing the identification of all possible values a tainted variable might hold at sink points without the computational overhead of complex symbolic solutions.

However, existing state-of-the-art static analysis tools like SaTC and KARONTE often fall short in real-world IoT firmware analysis. A compelling motivating example involves an OS command injection vulnerability in an ASUS router's httpd binary. The intricate vulnerability chain starts with an HTTP request, proceeds through mime_handler and appGet.cgi to do_ej, then ej_handler and ej_bwdpi_monitor_info. User input, obtained via websGetVar, is passed to bwdpi_monitor_info in the private library libbwdpi_sql.so, culminating in an insecure system() call due to inappropriate string concatenation. Neither SaTC nor KARONTE could detect this vulnerability. Investigations revealed two primary reasons for their failure:

• Missing Source Points: Functions like ej_handler and mime_handler were not correctly added to the CFG due to challenges in resolving indirect calls and callbacks, preventing websGetVar's input from being marked as tainted.
• Missing Sink Points: Data flow propagation into shared link libraries like libbwdpi_sql.so was not tracked, causing the system() call sink to be missed. This is often an efficiency trade-off, as tracking data flow across multiple binaries and libraries significantly increases the overhead for symbolic execution-based methods.

HermeScan's core intuition is to transform taint tracking into a reachability problem by constructing an extended CFG and precisely identifying taint sources. By performing efficient, lightweight RDA between these identified sources and sinks, HermeScan aims to effectively discover such complex vulnerabilities.

Key Findings

▶ Watch: Background: IoT threat model and common vulnerabilities (2:00)

HermeScan's research and implementation yielded several significant findings and contributions that advance the state of the art in IoT firmware security:

• Novel Optimized RDA Solution: HermeScan introduces a lightweight, on-demand, context-sensitive Reaching Definition Analysis (RDA) solution. This approach is specifically tailored for detecting taint-style vulnerabilities in Linux-based IoT firmware, offering superior effectiveness, accuracy, and efficiency compared to prior methods.
• Discovery of Zero-Day Vulnerabilities: A prototype of HermeScan successfully discovered a remarkable 87 zero-day vulnerabilities in real-world IoT devices from various manufacturers. Out of these, 69 were assigned CVE numbers, validating HermeScan's practical utility and its capability to uncover previously unknown security flaws.
• Comprehensive Firmware Datasets: The research involved building two extensive firmware datasets: a "0-day Dataset" comprising 30 latest firmware samples from 8 manufacturers (average size 28.2 MB across ARM32, ARM64, MIPSEL, MIPSEB architectures) and an "N-day Dataset" with 98 older firmware versions from 25 series and 9 manufacturers. These datasets served as robust benchmarks for evaluating HermeScan and existing tools.
• Superior Performance over SOTA Tools: Comparative evaluations against state-of-the-art symbolic execution-based tools like SaTC and KARONTE demonstrated HermeScan's significant advantages:
• Effectiveness: HermeScan found 163 vulnerabilities in the 0-day dataset (152 buffer overflow/command line injection + 11 other types), including the 87 zero-days, compared to SaTC's 32 and KARONTE's 0. On the N-day dataset, HermeScan found 204 known vulnerabilities, while SaTC found 138 and KARONTE 40.
• Accuracy: HermeScan achieved a True Positive Rate (TPR) of 81% on the 0-day dataset and 79% on the N-day dataset, substantially outperforming SaTC (42% and 63% respectively) and KARONTE (0% and 72% respectively). This indicates a significant reduction in false positives.
• Efficiency: HermeScan's average analysis time per sample was 1 hour and 7 minutes on the 0-day dataset and 1.14 hours on the N-day dataset. This makes it approximately 7.5 times faster than SaTC (8 hours 25 minutes) and 3.8 times faster than KARONTE (4 hours 16 minutes) on the 0-day dataset.
• Validated Optimizations: The study rigorously evaluated the impact of HermeScan's individual optimization schemes—enhanced CFG recovery, precise input source identification, and efficient path merging. Each component was shown to significantly contribute to the overall effectiveness, accuracy, and efficiency of the analysis, expanding analysis scope, reducing false positives/negatives, and mitigating path explosion.

Technical Deep Dive

▶ Watch: Reaching Definition Analysis (RDA) explained as core technique (3:00)

HermeScan is engineered to address the inherent challenges of static taint analysis in real-world IoT firmware: comprehensive CFG recovery, precise source point identification, and efficient taint tracking. Its architecture comprises a five-step process: Border Binary Finder, Enhanced CFG Recovery, Source Input Identification, Efficient Dataflow Analysis, and Taint Inspection Engine.

A. Challenges in Firmware Static Analysis

1. Incomplete CFG Recovery: A complete and accurate Control Flow Graph (CFG) is fundamental. Existing methods struggle with indirect calls and callbacks common in embedded systems. Furthermore, extending CFG analysis to dynamically loaded libraries (inter-binary and inter-library control flow) dramatically increases analysis time, rendering symbolic execution unscalable.
2. Precise Source Point Identification: Identifying where untrusted data enters the program is crucial. Manual specification is expert-dependent, while automatic methods relying on shared strings often suffer from:

• Semantic Differences: Keyword matching fails to account for semantic variations between front-end and back-end parsing.
• Over-Tainting: Marking all parameters and return values of a source function as tainted without context leads to high false positives.

1. Efficient Taint Tracking: Even RDA, being faster than symbolic execution, faces challenges:

• Path Explosion: A massive number of paths between sources and sinks can overwhelm analysis.
• Complex Inter-procedural Analysis: Tracking data flow across numerous callee functions, many unrelated to user input, adds significant overhead.

B. System Design and Architecture

HermeScan's design tackles these challenges through a synergistic combination of novel techniques:

1. Border Binary Finder: Similar to SaTC, HermeScan identifies the primary target border binary by extracting the firmware's file system and collecting shared strings referenced in both front-end (web pages) and back-end (binaries) files. The binary with the most matching keywords is designated as the target.

1. Enhanced CFG Recovery: This module builds a robust foundation for analysis:

• Function Boundary Identification: Beyond disassembler-identified functions, HermeScan scans for function prologue features (e.g., stack operations) across various architectures, ensuring a broader analysis scope.
• Symbol Name Recovery: For stripped binaries where angr's section header table analysis fails, HermeScan parses ELF files by traversing program header tables, specifically identifying the PT_DYNAMIC segment and locating the DT_SYMTAB tag to recover more symbol information.
• Calling Convention Recovery: HermeScan extends angr's default recovery. For functions where the calling convention (CC) is unclear, it assigns preset CCs based on architecture (ee.g., MIPS a0-a3 registers), improving data flow accuracy and preventing false negatives.
• CFG Construction: HermeScan treats each function as a dominant node, constructing independent subgraphs linked by jump/call instructions. Crucially, it establishes a Lib-CFG for shared libraries and links it with the Bin-CFG using recovered symbol names, extending control flow analysis across the binary and its dependencies.

1. Source Input Identification (Algorithm 1): This module ensures precise source identification, balancing false positives and false negatives:

• Fuzzy Matching Strategy: HermeScan screens shared strings from front-end and back-end files using both word-form and semantic similarity.
• Word-form Similarity: Measured by normalized Levenshtein Distance (Edit Distance), where FormatSim(S1, S2) = 1 - Edit(S1, S2) / (L(S1) + L(S2)). This matches variations like hostname_1.1 and hostname_%s.
• Semantic Similarity: Calculated using BERT embeddings and cosine similarity (specifically the efficient all-MiniLM-L6-v2 model). This is activated when the ratio of the longest common subsequence to the shorter string's length exceeds a threshold δ, linking semantically related strings (e.g., "request from %s is banned for security" with "sec_ip_ban"). A string pair (S1, S2) matches if FormatSim exceeds α OR SemanticSim exceeds β.
• Candidate Function Checking: To avoid over-tainting, HermeScan performs def-use analysis on candidate functions (those referencing fuzzy-matched strings, like websGetVar). It checks if parameters receive external input and tracks return values used as taint sources.
• Constraint Inference: For taint sources with length restrictions (e.g., string-copy functions), HermeScan uses Value Set Analysis (VSA) and def-use analysis to infer constraints. For example, if the third parameter of dlink_webGetVarN flows into strncpy, VSA establishes the length constraint between strncpy and the dlink_webGetVarN parameter.
• Input Taint Value Assignment: Based on vulnerability type and collected length constraints, HermeScan heuristically assigns the input taint value to the appropriate parameter or return register at the sources, propagating these values and updating the data dependency graph.

1. Efficient Dataflow Analysis (Algorithm 2): HermeScan employs a unique LCO Inter-procedural Analysis (Lightweight, Context-sensitive, On-demand) combined with a path merging strategy:

• Lightweight Principle: Utilizes RDA-based taint tracking, significantly faster than symbolic execution. It uses angr's RDA module, lifting assembly to VEX IR and performing RDA on the CFG with the classic worklist algorithm. It generates an indirect Def-Use graph categorizing variables (temporary, global, stack, heap, registers).
• Context-sensitive Principle: Extends angr's intra-procedural RDA. During function calls, parameters are marked as definitions, their values assigned from the caller's registers or stack based on CC. Upon return, definitions of all variable types are merged and overwritten in the caller. Aliasing issues are addressed by calculating relevant register values from the Def-Use graph to resolve jump addresses, using a demand-driven approach.
• On-demand Principle: Prioritizes tracking explicit taint propagation by identifying functions with tainted parameters. It steps into library functions if their parameters are tainted, forming a deeper data flow analysis. Commonly used Libc functions have their return values summarized.
• Path Merging Strategy: Reduces redundant analysis by identifying and merging repeatedly traversed paths in the function call graph. This includes:
• Multi-source Taint: Tainting each source point with a different label within a single RDA analysis, tracking multiple taint values simultaneously.
• Multi-sink Observation: Since RDA is path-insensitive, any reachable function is analyzed. HermeScan sets multiple observation points in one pass to avoid re-analyzing sink points. This strategy reduced the number of analyzed paths by an average of 89.4%.

1. Taint Inspection Engine: This module implements a collection of vulnerability pattern policies:

• Buffer Overflow: Alerts are raised if the length of copied data might exceed the destination buffer size, considering truncations or concatenations.
• Command Line Injection: Alerts are generated if a variable's value, referenced by functions like system() or popen(), contains a string from a taint source, indicating a malicious command. The module is extensible for defining new rules.

C. Implementation Details

HermeScan is prototyped in approximately 4,000 lines of Python code. Its CFG recovery module is built on IDA Pro 7.6 and angr 9.2.1. The source input identification module uses the R package text2vec for Levenshtein distance calculation, with hyperparameters α=0.75, β=0.83, and δ=0.5 determined via grid search. The efficient data flow analysis is an extension of angr's RDA module. Sink functions and detection rules are defined for 10 vulnerability types, including CWE-337 and CSRF.

Demo / Proof of Concept

▶ Watch: Motivating example: ASUS router vulnerability, existing tools fail (3:30)

While the talk did not feature a live, interactive demo, HermeScan's efficacy was compellingly demonstrated through its ability to detect complex, real-world vulnerabilities that evaded state-of-the-art tools. The prime example is the OS command injection vulnerability in an ASUS router's httpd binary. This vulnerability, involving intricate control flow through mime_handler, appGet.cgi, do_ej, ej_handler, ej_bwdpi_monitor_info, websGetVar, and finally an unsafe system() call within libbwdpi_sql.so, served as a critical benchmark. SaTC and KARONTE failed to detect this due to their inability to correctly resolve indirect calls, identify websGetVar as a source, or track data flow into shared libraries.

HermeScan, by contrast, successfully identified this vulnerability, directly validating its core design principles:

• Enhanced CFG Recovery: Its ability to identify more function boundaries, recover symbol names from stripped binaries, and link the Bin-CFG with the Lib-CFG for libbwdpi_sql.so ensured that the entire control flow path, including the critical system() call sink in the private library, was visible to the analysis.
• Precise Source Input Identification: Through its fuzzy matching and candidate function checking, HermeScan accurately identified websGetVar as a source of untrusted input, even when traditional keyword matching might fail.
• Efficient Dataflow Analysis: The LCO Inter-procedural Analysis enabled context-sensitive taint tracking across function calls and into the shared library without the prohibitive overhead of symbolic execution, allowing the tainted data to be traced all the way to the system() call.

Beyond this specific example, the most significant proof of concept lies in HermeScan's discovery of 87 zero-day vulnerabilities across 30 real-world firmware samples from manufacturers like LINKSYS, ASUS, Tenda, and TP-LINK. These findings, with 69 CVEs assigned, unequivocally demonstrate HermeScan's practical effectiveness in identifying previously unknown security flaws in production IoT devices. The comprehensive evaluation results, showing HermeScan's superior performance in terms of effectiveness (finding 120 more vulnerabilities than SaTC and 152 more than KARONTE in the 0-day dataset), accuracy (TPR of 81% vs. SaTC's 42%), and efficiency (7.5 times faster than SaTC), further cement its position as a robust and practical solution for IoT firmware security analysis.

Defensive Implications

▶ Watch: First challenge: Comprehensive CFG recovery for static analysis (4:40)

HermeScan's work provides crucial insights and actionable intelligence for defenders engaged in securing IoT ecosystems:

1. Prioritize Static Analysis in Firmware Security: The limitations of fuzzing and rehosting for IoT firmware highlight static analysis as a critical first line of defense. Organizations developing or deploying IoT devices should integrate robust static analysis tools like HermeScan into their security development lifecycle (SDL) and procurement processes.
2. Focus on Comprehensive CFG Recovery: Incomplete CFGs are a major blind spot for traditional static analysis. Defenders should ensure their analysis tools can effectively recover function boundaries, symbol names (especially for stripped binaries), resolve indirect calls, and accurately model control flow across the main binary and its dynamically loaded shared libraries. This is particularly important for identifying hidden sources and sinks in private libraries.
3. Implement Precise Taint Source Identification: Over-tainting leads to alert fatigue, while missed sources lead to critical vulnerabilities. Defenders should advocate for tools that use intelligent techniques, such as fuzzy matching (e.g., Levenshtein distance, BERT embeddings) and detailed candidate function checking, to accurately identify external input points and apply appropriate constraints.
4. Understand Data Flow Constraints and Sanitization: HermeScan's success in reducing false positives stems from its ability to infer and apply length constraints and understand sanitization logic at source points. Developers should be meticulous in implementing input validation and sanitization, and security analysts should use tools that can model these constraints accurately to avoid both buffer overflows and command injections.
5. Address Library Vulnerabilities: A significant portion of vulnerabilities, as shown by HermeScan finding 4 vulnerabilities in private libraries for ASUS RT-AX56u and TOTOLINK T8, reside in shared libraries. Defenders must extend their security analysis beyond the main application binary to encompass all loaded libraries, including custom and private ones.
6. Mitigate Path Explosion in Analysis: The efficiency gains demonstrated by HermeScan's path merging strategy (reducing paths by an average of 89.4%) are vital for scalable analysis. When selecting or developing analysis tools, prioritize those that employ effective strategies like multi-source taint and multi-sink observation to manage the computational complexity of deep inter-procedural analysis.
7. Patch Known Vulnerabilities and Monitor for Zero-Days: The discovery of 87 zero-day vulnerabilities underscores the constant threat. Defenders must ensure prompt patching of identified flaws and continuously monitor for new vulnerabilities, leveraging advanced tools to discover emergent threats before they are exploited in the wild.
8. Consider Hybrid Analysis Approaches: While HermeScan excels as a static analysis tool, its authors acknowledge limitations in modeling complex external input constraints and explicit checks within path conditions. For critical systems, a hybrid approach combining static analysis with partial symbolic execution or dynamic observation could further reduce false positives and enhance detection of subtle vulnerabilities.

Key Takeaways

• HermeScan significantly advances static taint analysis for IoT firmware, overcoming limitations of prior symbolic execution-based tools like SaTC and KARONTE.
• It successfully discovered 87 zero-day vulnerabilities in real-world Linux-based IoT devices, demonstrating practical effectiveness and a high impact on security.
• HermeScan's core innovation lies in its optimized, lightweight, on-demand, context-sensitive Reaching Definition Analysis (RDA), making it substantially faster and more accurate than symbolic execution.
• Key technical contributions include an enhanced CFG recovery mechanism (identifying more functions, recovering symbols, linking shared libraries), precise source input identification (fuzzy matching, semantic similarity with BERT embeddings, constraint inference with VSA), and an efficient path merging strategy (multi-source taint, multi-sink observation).
• The system achieved a True Positive Rate (TPR) of over 80% while being 7.5 times faster than SaTC, drastically reducing false positives and analysis time.
• Defenders should prioritize comprehensive static analysis in their IoT security strategies, focusing on tools that can accurately model control flow across binaries and libraries, precisely identify taint sources, and efficiently track complex data flows to mitigate buffer overflows, command injections, and other taint-style vulnerabilities.

About the Speaker(s)

The talk was presented by Zicong Gao. Based on the introduction, Zicong Gao is a researcher excited to present their work on HermeScan, a novel solution for detecting vulnerabilities in Linux-based IoT firmware. The presentation highlights their expertise in static analysis, IoT security, and the development of advanced tools to address critical challenges in this domain.