Why does KMP suit scanning a non-rewindable byte stream for a fixed signature?
answer
- Ask what must be remembered between bytes
- The text pointer only moves forward
- State is a table and one integer
- Signatures split across chunk boundaries still match
- The bound survives hostile traffic
basics
~20 sKMP's whole state is the prefix table plus the current matched length, and its text pointer never moves backward, so it consumes each byte once, in order, with memory proportional to the signature and a work bound hostile traffic cannot inflate.
solid answer
~50 sAn inspection appliance sees each byte of a stream once and cannot ask for it again. KMP fits because its text index only ever moves forward: the matcher's whole state between bytes is the precomputed table plus one integer, the current matched length. That means O(m) memory regardless of how many gigabytes have flowed past, and it means a signature straddling a chunk or packet boundary is found for free — the matched length simply carries over. A naive scanner can be made to stream, but it must retain the last m-1 bytes and re-compare them after each failed window, and on crafted repetitive traffic that re-comparison is the quadratic tail. On a line-rate device that tail is not a slow query, it is dropped packets. KMP's bound of about two comparisons per byte holds against any traffic, which is what lets you size the device.
go deeper
Recall that KMP needs only the signature-derived table and a single counter to keep going, so it can process input that arrives a piece at a time without storing what has already passed.
Explain why never moving the text pointer backward removes the need to retain past bytes, and why the matched length carrying across chunk boundaries makes split signatures match automatically.
Show the capacity reasoning: identify crafted repetitive traffic as an algorithmic denial-of-service vector on a line-rate device, and state the total-work bound precisely rather than promising cheap individual bytes.
Own the tradeoff between a guaranteed-throughput matcher and a faster-on-average one, including what you tell operators about sizing headroom and what you accept losing when the signature set grows beyond one.
## The constraint that decides it An intrusion-detection appliance sits in the path of a byte stream and looks for a fixed signature. Two hard facts shape the design: bytes arrive once and are gone, and the device must keep up with the wire or it drops traffic. Any matcher used here must therefore (a) work with a single forward pass, (b) hold bounded state, and (c) have a per-byte cost that no sender can inflate at will. KMP satisfies all three, and the reason is one structural property rather than the complexity label people usually quote: **its text index never decreases.** ## What the matcher has to remember Between one byte and the next, KMP's state is: - the prefix table, computed once when the signature was loaded, of size m; and - a single integer, the current matched length. That is all. Feed it bytes one at a time and it answers correctly, forever, in O(m) memory that does not grow with the volume scanned. No copy of the stream, no sliding window of past bytes, no per-connection buffer that scales with traffic. On a device tracking many concurrent flows this matters twice over: the per-flow cost is one small integer, while the table is shared across every flow that scans for the same signature. ## The chunk-boundary bug that this design avoids The classic implementation bug in stream scanning is running a matcher independently over each chunk or packet. A signature split across the boundary is then invisible: neither chunk contains it. Naive scanning needs an explicit fix — carry the last m-1 bytes of each chunk into the next scan and re-examine them. Enlarging chunks does not help, and neither does aligning boundaries to the signature length; there is always a boundary somewhere, and an adversary who knows your chunking can aim at it. With KMP the fix is structural rather than remembered. Matched length is not reset at a boundary, so a signature whose first bytes closed one chunk and whose remainder opens the next is detected exactly as if the stream were contiguous. Nothing about the chunking is visible to the algorithm at all. ## The bound is a capacity argument, not a speed claim This is where the senior framing lives. A naive stream scanner is not impossible — the m-1-byte retained window makes it work — but its cost per byte is bounded only by m, and crafted traffic reaches that bound. A sender who transmits a long run of a padding byte against a signature that is mostly that same byte forces re-comparison of nearly the whole window at every offset. On a database that is a slow query; on a device that must not fall behind the wire, it is an algorithmic-complexity denial of service: the attacker gets to choose your CPU cost per byte, and once the device falls behind, traffic goes through uninspected. That is the failure mode that actually gets exploited. KMP's total work is bounded by roughly two comparisons per byte over any input whatever. Stating it precisely matters: a *single* byte can be expensive, because the matched length may fall through a chain of borders while the text index stays put. What is guaranteed is the total over the stream, which is the right unit anyway — a device is sized by sustained throughput, not by the cost of one worst byte, and a small output queue absorbs the jitter. The guarantee is also deterministic: there is no seed, no expected-case asterisk, and nothing an attacker can learn about your implementation that changes the bound. ## What KMP does not buy here Be honest about the limits or the answer sounds like advocacy. KMP is never sublinear: every byte is inspected, so it cannot beat a skip-based matcher on typical benign traffic, and skip-based matchers can be adapted to streams too. It says nothing about matching case-insensitively, about signatures with wildcards, or about normalizing an encoding before matching — all of which are usually where real detection accuracy is won or lost. And the guarantee is per signature: scanning for a large signature set is a different problem with a different answer, not KMP repeated in a loop. The defensible summary is narrow and correct: for one fixed signature over a single-pass, non-rewindable stream, KMP gives bounded state, correct behaviour across arbitrary chunk boundaries, and a worst-case work bound that a hostile sender cannot inflate — three properties you can put into a capacity model.
- Can naive matching stream at all, or does it need the whole input?It can stream, but only by retaining the last m-1 bytes so a failed window can be re-examined from the next offset. State stays bounded; what is not bounded is the work per byte, which crafted repetitive traffic pushes toward the signature length and turns into a throughput failure.
- You said the bound is about two comparisons per byte. Is any single byte guaranteed cheap?No. One byte can trigger a long chain of fallbacks through the table while the stream position stays fixed, so per-byte latency has jitter. The guarantee is on the total across the stream, which is the unit that sizing and sustained-throughput models actually use.
- What changes if the appliance must match many signatures instead of one?It becomes a different problem: running an independent matcher per signature multiplies per-byte work by the signature count, which does not hold at line rate. That workload calls for a multi-pattern approach rather than a loop over single-pattern matchers, and its analysis is separate from this one.
It is a turnstile counter rather than a scrapbook: it never needs to look back at who already walked through, only at how far along the expected sequence it currently stands.
saying these in an interview costs you the question
- Claims the whole stream must be buffered to match
- Says naive matching cannot stream at all
- Thinks KMP skips bytes and reads less input
- Resets the matcher at each chunk boundary
- Promises constant work for every individual byte