FITS: Inferring Intermediate Taint Sources for Effective Vulnerability Analysis of IoT Device Firmware

Puzhuo Liu, Yaowen Zheng, Chengnian Sun, Chuan Qin, Dongliang Fang, Mingdong Liu and 1 other

Finding security bugs in IoT firmware means tracing attacker-controlled data from where it enters (a network call like recv) to where it's dangerous (a call like strcpy or system) — but in a stripped, closed-source firmware binary that path is enormously long and keeps passing through indirect function calls that static analysis simply cannot follow, so the trace breaks and the bug is missed; FITS (Waterloo) notices that IoT firmware almost always follows the same idiom — receive input, stash it, then FETCH fields back out by key — and that those custom key-value fetch functions sit right next to the dangerous sinks, so it automatically recognizes them (by their code shape and their resemblance to known string functions) and starts the taint trace THERE instead of at the far-away network call, shrinking a path of dozens of hops and multiple unresolvable indirect calls down to as few as two — which, plugged into existing analyzers, turned up hundreds more bugs and 21 new CVEs while slashing false alarms.

The argument in one glance

Problem

IoT firmware is full of bugs, and tracing them is the hard part

The firmware inside routers, cameras, and other IoT devices is a favorite target for attackers, because a single memory-corruption or command-injection bug can lead to a real-world device takeover. The standard way to hunt these bugs is TAINT ANALYSIS: mark the attacker-controllable inputs as "tainted," follow that data as it flows through the program, and raise an alarm if it reaches a dangerous operation (a SINK like strcpy or system) without being checked. It is a powerful idea in principle. In practice, on real firmware, the follow-the-data step is where everything falls apart — the data has to be tracked across an enormous, stripped binary, and the trail keeps going cold.
What people did

Start the taint at the network input functions

The natural place to begin a taint trace is where untrusted data enters the program — the interface library functions that read from the network or environment, like recv, getenv, or a CGI parameter reader. These are the classic taint sources: attacker data provably starts here, so mark their outputs tainted and follow the flow forward to the sinks. Every firmware analysis tool does this, and it is the textbook-correct starting point, because these functions are exactly where external input crosses into the program.
Why it fell short

The path from a library source to a sink is too long, and indirect calls break it

Starting at recv is correct but hopeless in practice, because the network-input function is FAR from the dangerous sink. Between them the data winds through many custom functions across multiple binaries (often via CGI), and the path is excessively long — and, fatally, it passes through INDIRECT function calls (through pointers and jump tables) that static analysis cannot resolve. When the trace hits an indirect call it cannot tell where control goes, so the taint trail goes cold and the sink is never reached. One real bug (CVE-2022-20825) sits at the end of a path with at least 11 custom function calls, more than 50 library calls, and at least three indirect calls. Alias analysis, which might otherwise stitch the flow back together through globals, pointers, and arrays, is overwhelmed at this scale. So the correct source produces a path no analyzer can actually follow.
This paper's idea

Start the taint later — at a custom function right next to the sink

FITS (University of Waterloo — Liu and colleagues) observes that you do not have to start the trace at the far-away library source. IoT firmware almost always follows the same idiom: receive the structured user input through a library function, save it to memory, and later FETCH individual fields back out by KEY for processing. Those custom key-value FETCH functions sit close to the sinks and hand out attacker-controlled values — so they make excellent INTERMEDIATE TAINT SOURCES (ITSs). FITS automatically infers these functions by recognizing their behavioral signature (their code structure and their resemblance to known string-handling functions), then re-roots the taint trace at their output. This shrinks a path of dozens of hops and multiple unresolvable indirect calls down to as few as two, sidestepping the indirect-call problem entirely — and, dropped into existing analyzers, it found hundreds more bugs and 21 new CVEs while cutting false alarms.

Why this problem is worth solving

Firmware security is device security, and taint analysis is the main lens for finding the flaws — so anything that makes the taint trace actually complete is worth a great deal. The reason the trace so often fails is a structural mismatch between where analysis naturally starts and where it must end. The conventional starting point is a

the functions where untrusted input crosses into the program from the outside world — network receivers like recv, environment readers like getenv, CGI parameter readers, and so on. These are the textbook-correct taint sources because it is provable that attacker data originates there, so their outputs are marked tainted and the analysis follows the data forward. The catch is location: these library functions live at the very edge of the program, far from the dangerous sinks deep inside the request-handling logic. So a trace that starts here must span the entire distance from the network edge to the vulnerable operation, which in real firmware is a long, winding journey through many intermediate functions

. The correctness of the starting point is exactly what makes it impractical: being at the true origin means being maximally far from the destination.

What turns a long path from merely slow into impossible is that it is broken, not just long. The breaks come from

function calls made through a pointer or a jump table rather than to a fixed, named target — think of a dispatch table that routes a request to a handler chosen at runtime. Static analysis, which reasons about the program without running it, cannot in general determine which function an indirect call actually invokes, because the target depends on runtime values. So when a data-flow trace reaches an indirect call, it does not know where the data goes next, and the trail simply stops. Firmware request handling is full of these dispatch patterns, so a source-to-sink path typically crosses several indirect calls, each a place the trace can die

. Resolving indirect calls precisely is a notoriously hard, often intractable problem, and alias analysis (tracking how data is shared through globals, pointers, and arrays) cannot rescue the flow at firmware scale. The consequence is that starting from the library source, the analysis reliably loses the trail before it reaches the sink, so real bugs go undetected. The opportunity FITS seizes is that you do not have to trace the whole path — if you can find a trustworthy place CLOSER to the sink to call “tainted,” you skip most of the long, broken journey and the trace becomes feasible.

What people did before, and where it broke

Classic taint sources (Karonte, EmTaint, SaTC). Start the trace at library input functions like recv. Correct in principle, but the resulting source-to-sink path is enormously long and crosses unresolvable indirect calls, so the trace goes cold and many bugs are never reached.
Keyword-string matching for sources (BootStomp). Guess taint sources by matching keyword strings in the binary. Fragile — the keywords vary across vendors, so it “cannot find any taint source” in FITS’s firmware set, missing the analysis entirely.
Precise indirect-call resolution / heavy alias analysis. Try to reconstruct the full path by resolving indirect calls and tracking all data sharing. This is the “solve the hard problem head-on” approach, but indirect-call resolution is intractable at firmware scale and alias analysis is overwhelmed by globals, pointers, and arrays, so it does not complete.
Emulation / dynamic analysis. Run the firmware and observe real data flow, which sidesteps static-analysis limits. But emulating diverse, closed-source firmware faithfully is itself extremely hard, and dynamic coverage is limited to paths actually exercised.
The gap. No prior method made the long, indirect-call-broken source-to-sink path tractable by relocating where the taint STARTS — automatically inferring custom functions near the sinks to use as intermediate sources. FITS does this, turning an unfollowable path into a short one and multiplying the bugs existing engines find.

How FITS works

Diagnose the path, spot the idiom, fingerprint the functions, and re-root the taint

Diagnose why the path is intractable

The classic taint source (recv and kin) sits at the network edge, so the path to a sink is long and repeatedly crosses indirect calls that static analysis cannot resolve — so the trace dies before reaching the sink. FITS accepts this rather than trying to resolve the indirect calls, and instead moves where the taint begins.
↓ →
Spot the firmware idiom: receive, store, fetch-by-key new

IoT firmware overwhelmingly follows one pattern: receive the structured user input through a library function, save it to a memory region if it matches the expected format, and later FETCH individual fields back out by key for processing. The custom key-value FETCH functions sit close to the sinks and return attacker-controlled values — ideal places to call tainted.
↓ →
Fingerprint each custom function (behavioral features) new

FITS represents every custom function by an 11-feature Behavioral Feature Vector: STRUCTURAL features (basic-block count, loops, callers, parameters) and FLOW features (whether parameters drive loops or branches, string arguments, how parameters are used). A key-value extractor has a characteristic shape — take a key string, loop to search, return the found value.
↓ →
Cluster and keep the complex candidates new

FITS clusters all custom functions by their feature vectors (DBSCAN) and keeps only the functions in the high-complexity classes as candidates, discarding the many trivial functions. This filtering step removes obvious non-extractors and sharply cuts false positives before the expensive scoring.
↓ →
Score against known anchor functions new

Each candidate is scored by behavioral similarity (cosine distance) to standard library ANCHOR functions that key-value extractors resemble — string searchers and copiers like strstr, memcmp, and strcpy. The custom functions most similar to these anchors are inferred as intermediate taint sources, with the top three candidates 89% precise on average.
↓ →
Re-root the taint trace at the inferred source new

Once an ITS is confirmed, the register or global holding its returned (extracted) value becomes the taint origin, plugged into existing engines (Karonte, static taint analysis) in place of or alongside the classic source. The trace now starts close to the sink, skipping the long prefix and its unresolvable indirect calls.

Evaluated on 59 real-world firmware samples (the Karonte dataset plus newer firmware) from NETGEAR, D-Link, TP-Link, Tenda, and Cisco across ARM, AARCH64, and MIPS, integrated into the Karonte and static-taint-analysis engines. Average inference time about 2 hours 57 minutes per firmware; most binaries (under 800 functions, under 300 KB) analyze in under an hour.

The idea

Do not trace the whole path — start closer to the target. The source-to-sink path in firmware is both too long and broken by indirect calls, so a trace from the true origin (recv) reliably dies before the sink. FITS’s move is to relocate the starting point: find a trustworthy waypoint near the sink and call IT the source. An intermediate taint source is a custom function that hands out attacker-controlled data much closer to where the danger is, so the trace only has to cover the short, tractable tail of the path instead of the whole thing. This is the decompose-an-intractable- path-at-a-good-checkpoint discipline the site rewards — the optimal-inlining page splitting a program at its bridges, the replicated-simulation page cutting a circuit at clean boundaries — here applied to a data-flow trace: insert a waypoint where the analysis can actually stand, and the impossible full traversal becomes a short, feasible one.

Sidestep the hard subproblem instead of solving it. The thing that kills the classic trace is the indirect call, and resolving indirect calls precisely is a notoriously hard, often intractable problem. Prior work tried to solve it head-on and could not. FITS’s insight is that it does not NEED to: because the intermediate source sits AFTER the indirect calls on the path, starting the taint there skips right over them — the hard subproblem is not solved but avoided. This is the same route-around-the-hard-problem discipline the site sees when the replicated-simulation page eliminates a synchronization dependency rather than scheduling around it, or the hardware-repair page reshapes a task so the difficulty disappears: the cheapest way to handle an intractable subproblem is to arrange not to have it. The indirect calls are still there; the analysis just no longer has to walk through them.

Exploit the domain idiom, and recognize its signature. FITS works because firmware is not arbitrary code — it overwhelmingly follows the receive-store-fetch-by-key pattern, so the useful intermediate sources are a specific, recurring kind of function (key-value extractors) that can be found reliably. And it finds them not by names (the binary is stripped) but by BEHAVIOR: a key-value extractor has a telltale signature — it takes a key, loops to search, calls string functions, returns the found value — so FITS fingerprints functions by structural and flow features and scores them against known string-handling anchors. This is the exploit-the- domain-pattern-the-generic-tool-ignores discipline the site meets whenever a specialized system beats a general one by leaning on regularity — the PCIe-collectives page modeling contention a generic library cannot see — combined with recognize-the-role-by-its- signature, the same classify-by-behavior move the serverless-memory page uses to sort pages by their lifecycle role.

Re-rooting one taint trace

Why moving the source turns an unfollowable path into a two-hop one

Tracing a real firmware bug (CVE-2022-20825, a Cisco device). Numbers from FITS's case study.

Step 1 of 5

The long path from the network input

Attacker data enters at a network-input library function, but the vulnerable sink sits deep in the request-handling logic. Between them the tainted data threads through at least 11 custom function calls and more than 50 library calls — an enormous path for a static analyzer to follow precisely across a stripped, multi-binary firmware image.

the classic taint source is correct (attacker data really starts at recv) but maximally far from the sink
alias analysis over globals, pointers, and arrays is overwhelmed at this scale

Why it works

The classic taint source (recv) sits at the network edge, so its path to a sink is long and crosses unresolvable indirect calls → FITS re-roots the taint at a custom function near the sink → the trace only has to cover the short, tractable tail.
Indirect-call resolution is intractable, and prior tools fail on it → the intermediate source sits AFTER the indirect calls, so starting there skips them → the hard subproblem is avoided rather than solved.
Firmware follows the receive-store-fetch-by-key idiom → the useful intermediate sources are a specific recurring function type (key-value extractors) → they can be found reliably on most request paths.
The binary is stripped, so functions have no names → FITS recognizes extractors by behavioral signature (structural and flow features) and similarity to known string anchors → top-3 inference precision is 89%.
Shorter paths are more precisely analyzable, not just faster → so re-rooting raises recall AND cuts false positives → static taint analysis went from 46 to 385 bugs while its false-positive rate fell from 77% to 28%.

What it costs

Needs the idiom to be present. FITS depends on the receive-store-fetch-by-key pattern, so it helps little on simple-logic devices (smart plugs, some robots) that lack complex input parsing, and it failed on 2 of 59 images that indexed input arrays directly with no intermediate extraction function.
Inference is imperfect. Top-1 precision is only 47% (top-2 63%, top-3 89%), so the analyzer must consider several candidate sources; a wrong ITS wastes analysis effort or misses flows.
Firmware must be obtainable and unencrypted. Vendors can encrypt firmware (swapping algorithms, keys, and salts), which blocks the analysis outright, and 4 of 59 images failed simply because the network-handling binary could not be located.
It shortens paths, not eliminates unsoundness. Re-rooting makes the tail tractable, but taint analysis still over-approximates (34.7% false positives even for Karonte-ITS), so human triage of the alarms remains necessary.
Cost scales with binary size. Inference averages nearly three hours per firmware and scales with function count and size, so the largest, most complex images are the slowest — though most fit under an hour.

The evaluation

Fifty-nine real-world firmware samples (the Karonte dataset plus newer firmware) from NETGEAR, D-Link, TP-Link, Tenda, and Cisco across ARM, AARCH64, and MIPS, with inferred intermediate sources plugged into the Karonte and static-taint-analysis (STA) engines and compared against their classic-source baselines and BootStomp.

Where to start a firmware taint trace

Property	Classic source (recv, library)	Keyword matching (BootStomp)	FITS (inferred intermediate sources)
Where the taint starts
Path length to the sink
Unresolvable indirect calls		n/a
Bugs found (static taint analysis)
False-positive rate (STA)		n/a

Re-rooting the taint at inferred intermediate sources improved both recall and precision at once: static taint analysis found 8x more bugs (46 to 385) while its false-positive rate fell by nearly a factor of three (77.2% to 27.9%), because a short, indirect-call-free path is far easier to analyze precisely than a long, broken one. In total 67 bugs were confirmed and 21 awarded high-severity CVEs.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

FITS rests on a domain assumption — the receive-store-fetch-by-key idiom — so it helps most on Internet-connected devices with complex input parsing and little on simple-logic devices, and it failed on 6 of 59 images (4 where the network binary could not be located, 2 that indexed input directly with no extraction function). Its inference is imperfect (top-1 precision 47%, rising to 89% only across the top three candidates), so the analyzer must weigh several candidate sources. It shortens paths but does not make taint analysis sound — false positives remain (34.7% even for Karonte-ITS), so human triage of alarms is still required — and it assumes the firmware can be obtained and is not encrypted, which vendors can defeat. Inference also averages nearly three hours per image and scales with binary size. None of this dulls the core insight — that when a data-flow trace from the true source to the sink is too long and broken by indirect calls to follow, the fix is not to resolve the whole path but to relocate where the taint STARTS: infer, by behavioral signature, a custom function near the sink that hands out attacker-controlled data, re-root the trace there to skip the long prefix and its unresolvable indirect calls, and reap both more bugs and fewer false alarms because a short path is a precise one.

Background

Shorten the path by relocating the start, and skip the hard subproblem

FITS sits in the site’s security-and-program-analysis cluster and rhymes with several ideas covered elsewhere on this site. Its governing move is to decompose an intractable path at a good checkpoint: rather than trace attacker data across the whole long, broken journey from the network edge to the sink, it inserts an intermediate source near the sink and analyzes only the short tail — the same break-the-problem-at-a-clean-boundary discipline the optimal-inlining page uses when it splits a program at its bridges and the replicated-simulation page uses when it cuts a circuit into independent partitions. Its sharpest move is to SIDESTEP the hard subproblem rather than solve it: indirect-call resolution is intractable, so instead of resolving the calls FITS places its taint source past them and skips them entirely — the same route-around-the- hard-problem instinct the replicated-simulation page shows when it eliminates a synchronization dependency instead of scheduling around it, the cheapest way to handle a hard subproblem being to arrange not to have it. It also exploits a domain idiom a generic analyzer ignores (the receive-store-fetch-by-key pattern that guarantees a useful intermediate function exists), the specialized-beats-general lesson the PCIe-collectives and GNN-operator pages share, and it identifies those functions by behavioral SIGNATURE rather than by name — features, clustering, and similarity to known anchors — the recognize-the-role- by-its-fingerprint move the serverless-memory page uses to sort pages by lifecycle role. And its most satisfying result is that a shorter path improves recall AND precision together, a reminder that attacking the root cause (an unfollowable path) often fixes several symptoms at once.

If you remember only three things

1. Finding IoT firmware vulnerabilities relies on taint analysis — tracking attacker-controlled data from a source (a network function like recv) to a dangerous sink (like strcpy or system) — but starting at the library source, though correct, puts the trace maximally far from the sink, across a path so long and so broken by INDIRECT function calls (which static analysis cannot resolve) that the trail goes cold and real bugs are missed; one real CVE sat behind 11 custom calls, 50-plus library calls, and 3 unresolvable indirect calls.
2. FITS re-roots the taint trace at an INTERMEDIATE source: it exploits the firmware idiom of receive-store-fetch-by-key, recognizes the custom key-value extractor functions that sit close to the sinks (by their behavioral signature — structural and flow features, clustered and scored against known string-handling anchors like strstr, since the binary is stripped of names), and marks their extracted output as the taint origin — so the trace starts AFTER the indirect calls and skips them entirely, collapsing a dozens-of-hops path to as few as two.
3. Dropped into existing engines, this turned static taint analysis from 46 bugs into 385 while cutting its false-positive rate from 77.2% to 27.9% (more bugs AND fewer false alarms, because short paths are precisely analyzable), with 67 bugs confirmed and 21 awarded high-severity CVEs — top-3 inference 89% precise. Honest limits: it needs the idiom present (failing on simple-logic or directly-indexed firmware), inference is imperfect, and it does not make taint analysis sound. The durable lessons: when a path is too long and broken to trace, relocate where it starts rather than resolving the whole thing, and sidestep an intractable subproblem instead of solving it.

Check yourself

Check your understanding

1. Starting a firmware taint trace at the network-input function (recv) is provably correct — attacker data really does originate there — yet FITS argues it is the wrong place to start. Predict why correctness is not enough here.
2. The indirect calls that break the taint trace are notoriously hard to resolve, and prior tools tried and failed. Predict how FITS handles them.
3. FITS identifies its intermediate taint sources as "key-value extractor" custom functions found by behavioral signature (features, clustering, similarity to string anchors) rather than by name. Predict why both the domain pattern and the by-behavior recognition are essential.
4. Re-rooting the taint at intermediate sources raised static taint analysis from 46 to 385 bugs AND cut its false-positive rate from 77.2% to 27.9% — improving recall and precision together. Predict why one change improved both, when they usually trade off.

Sources

ACM DL: FITS: Inferring Intermediate Taint Sources for Effective Vulnerability Analysis of IoT Device Firmware — ASPLOS 2023 (full text read via the author-hosted University of Waterloo PDF; no arXiv preprint).