States and Transitions
The same push, two different results
Section titled “The same push, two different results”If you’ve used a fare gate, you already know most of what it does. Put in a ticket, push the arm, and walk through. Try pushing before you’ve paid and the arm stays put, even though you’re doing exactly the same thing with your hand.
The difference is what happened before you pushed. If someone paid, the gate is unlocked; otherwise, it’s locked. We don’t need to remember everyone who has ever used it, or how many tickets it took this morning. Knowing whether it’s locked tells us what the next push will do.
Locked and unlocked are the gate’s states: the conditions it can be in at a particular moment. Paying or pushing supplies an input, and the gate’s response is a transition. An input doesn’t have to come from a person, either. A timer finishing can tell a machine to do something just as well as a button press.
A model with a finite number of states is called a finite state machine, usually shortened to FSM. For this gate, we only need two.
That sounds like a lot of terminology for getting through a turnstile, but it gives us a way to write down exactly what we expect it to do. Let’s try it.
A complete model of the fare gate
Section titled “A complete model of the fare gate”We’ll give our gate two states, locked and unlocked, and start it locked. It accepts two inputs: insert a fare, or push the arm. With two states and two inputs, we have four combinations to account for.
| When it’s | and you | it ends up | and you see |
|---|---|---|---|
| locked | insert a fare | unlocked | the arm gives |
| locked | push | locked | nothing happens |
| unlocked | push | locked | you go through, the arm re-locks behind you |
| unlocked | insert a fare | unlocked | your money is gone |
We can now work out what either input does in either state without knowing how the gate was built. We haven’t drawn its motor or worked out how it reads a ticket, because neither is needed to follow these four responses. A real gate might also handle refunds, faults, or an emergency release, but we’re leaving those out of this model.
The last row is a slightly annoying choice: if you pay twice before going through, this gate keeps the extra fare and stays unlocked. It could have been designed to return your money. Either way, accepting a fare while already unlocked needs an answer just as much as accepting the first one does.
We can draw those same four answers as a state transition diagram. Each circle is a state, and the labels on the arrows tell us which input takes us along that arrow.
Scroll sideways to see the full diagram.
I’d use the table when checking whether I’ve covered every combination. The diagram makes it easier to follow a sequence and see where it goes, including the arrows that loop back to the state we were already in.
Different kinds of transition
Section titled “Different kinds of transition”Paying at the locked gate gives us the most obvious kind of transition: something changes, and we follow an arrow to a different state. Pushing without paying is a little less satisfying. The gate stays locked, so its arrow loops back to where it started. We still need that arrow, though. Without it, the diagram wouldn’t tell us what a push does while the gate is locked.
An input can also lead to the same place from several different states. Think about opening a microwave door: whether it was cooking, paused, or waiting to start, we end up with the door open. We’d draw an arrow from each of those states to the door-open state. The arrows have the same label because we’re doing the same thing each time, even though we’re starting somewhere different.
So far, someone has been there to push, pay, or open a door. A timed traffic light doesn’t need that. It moves from green to amber to red when its timer finishes, with the timer supplying the input a person supplied in our other examples. If we only listed buttons people can press, we’d leave out the thing that makes this machine work.
A combination lock gives us another reason to think carefully about the state. It can look locked the entire time we’re entering the correct sequence, but it needs to keep track of our progress. For the simple lock below, a wrong number sends that progress back to the beginning. There’s no need for it to look any different when that happens (which is not particularly helpful to the person still entering the rest of the combination).
Microwave. One input, door opens, reaching the same state from every state on the map.
Fixed-cycle signal. Every arrow is triggered by elapsed time. Nobody presses anything.
Combination lock. A wrong digit sends it back to the start, and says nothing while it does.
That means “locked” alone isn’t enough to describe this lock. We need to know how much of the sequence it has accepted, because that decides what the next number will do. You might think you’re one number away from opening it while it’s waiting for you to start again.
The transition that isn’t there
Section titled “The transition that isn’t there”Our fare gate was small enough that we could list every combination. With a more complicated machine, it’s much easier to miss one.
Imagine a ticket machine whose description says that pressing Cancel while selecting a ticket returns you to the welcome screen. Once you pay, it issues your ticket. What if you change your mind after it takes your money but before the ticket comes out? The description doesn’t say.
| When it’s | and you | the description says |
|---|---|---|
| Selecting a ticket | press Cancel | Return to the welcome screen |
| Payment accepted, ticket not yet issued | press Cancel | Not specified |
That second row is an undefined transition in our model. We know the state and the input, but we don’t have a response to put in the last column. The machine might refund your money, finish printing the ticket, or simply ignore you. We’d need more information to know which.
In this simplified model, solid arrows show the purchase cycle and the return to welcome. The dashed line marks the undefined transition: we know which button was pressed, but not what happens next.
It’s tempting to read that gap as “Cancel does nothing,” but that would be an answer we haven’t been given. Ignoring the button would be a defined response, just like the gate staying locked when we push it. I’d look for the missing answer in a fuller description or, with permission, watch what the machine does. For now, the gap is in our model; the machine may handle it perfectly well.
So how would you force a transition?
Section titled “So how would you force a transition?”So far, we’ve been trying to describe normal behavior. Pressing Cancel because you changed your mind isn’t much of an attack. But what if someone deliberately looks for a way to make the machine do something it wasn’t supposed to? Our table gives us a place to start, although the arrows don’t tell us everything about who is allowed to use them.
The first possibility is an input the designer believed you couldn’t produce. The machine already knows how to respond, but the design assumes that input can only come from a trusted source. If someone else can supply it, the machine might follow its rules perfectly and still do something the designer never wanted.
The second is a legitimate input at an unexpected moment. Recognizing each input doesn’t settle what happens when they arrive in a different order or at an awkward time. We have to consider the state the machine is in when it receives them, just as we did with Cancel before and after payment.
The third is an input the design never listed. Here we’re back to a gap in the model: there’s no response to follow on paper. We’d need to find out what the actual machine does before deciding whether that missing case is a problem.
We’ll call these the three levers.
Suppose the goal is to reach the unlocked state without a fare. Which of those three assumptions would you investigate, and what is missing from the table that you’d need to know? This is a question about our model, not a test to run on a real gate.
A whistle, a cereal toy, and a machine the size of a continent
Section titled “A whistle, a cereal toy, and a machine the size of a continent”Long-distance telephone calls used to travel over trunks, shared connections between switching offices. For this example, we can describe a trunk with two familiar states: idle, or carrying a call.
The offices at either end needed to agree on that state. In the system we’re looking at, a steady 2600 Hz tone indicated an idle trunk, and its absence indicated a call in progress. If you play piano, that’s close to E7, near the high end of the keyboard. The switches used sound to coordinate, and that sound travelled along the same path as the caller’s voice.
In the late 1950s, Joe Engressia, a blind child with perfect pitch, discovered that his whistling could interrupt a recorded telephone message. He could produce the tone the switching equipment recognized. John Draper later became associated with a toy whistle from Cap’n Crunch cereal boxes that could produce it too, hence the nickname Captain Crunch. An impressive amount of telephone equipment turned out to have something in common with a cereal-box toy.
The resulting problem was that a caller could supply audio the network treated as control information. The equipment could be led to treat a connection as idle even while the caller remained connected. Devices called blue boxes generated telephone signaling tones, allowing callers to interfere with call control and routing. Steve Wozniak and Steve Jobs built and sold them before founding Apple.
This arrangement is called in-band signaling: the control signal travels in the same channel as the user’s traffic. Here, switch instructions and caller audio shared the voice line.
We can explain the failure with the same state-and-input model as the gate. The network recognized a signal, but recognizing the signal didn’t establish who had sent it.
Separating control signals from caller audio
Section titled “Separating control signals from caller audio”There’s our first lever. The switches already knew what to do with the signal; the caller wasn’t supposed to be able to supply it. They accepted sound from the caller as if it had come from the equipment coordinating the call.
Put the two cases beside each other and the difference is where the signal comes from:
As designed. A real call seizes the trunk, and the switch at the other end releases it when the caller hangs up. Both signals come from the network.
With a whistle. The caller supplies both signals: the tone that frees the trunk, and then the routing tones that seize it again for wherever they want to go.
On the left, the telephone equipment supplies the control signals. On the right, the caller supplies them. The switch follows the same rules either way, which is rather unfortunate when the person on the phone can give it instructions.
The eventual fix changed how the switches communicated. Common-channel signaling systems, including SS7, carry control information separately from the voice channel. Caller audio no longer serves as that switch-to-switch control channel.
With separate channels, the network no longer has to decide whether a sound on the voice line is someone talking or another switch giving it instructions.
Definition of an exploit
Section titled “Definition of an exploit”In the language of our model:
An exploit is an input, or a sequence of inputs, chosen to drive a machine into a state or along a transition its designer did not intend.
The telephone switches didn’t need a new transition. They already had one that did what the caller wanted. The mistake was letting the caller trigger it. Other machines might behave unexpectedly when given an input the model doesn’t account for, but we’d have to find out what they actually do first.
The word hacking has a history outside computers too. An early written example comes from MIT’s Tech Model Railroad Club. Its minutes for 5 April 1955 include the request that “anyone working or hacking on the electrical system turn the power off to avoid fuse blowing”. The club’s railway used telephone relays.
You may have done something similar on a smaller scale: worked out why a lock only turns when held a particular way, or learned the quirks of a vending machine you use regularly. Writing down its states and inputs gives you something more useful to work with than “it only does that sometimes.”
Practice: find a gap in a familiar machine
Section titled “Practice: find a gap in a familiar machine”Think of a machine you use, such as a coffee machine, self-checkout or card-entry door. Pick one state and one input. What happens next? Include a response where nothing changes, like pushing our locked gate. A sketch or table is optional.
Now pick a response you don’t know. Which of the three levers could help explain the gap? Keep observed behavior separate from assumptions, and keep this as a thought exercise unless you have permission to investigate the machine itself.
Compare your thinking
For a self-checkout, you might start with waiting for a customer, scanning items, waiting for something in the bagging area, waiting for staff approval, and taking payment. Inputs include barcodes, weight changes on the platform, screen taps, payment, and a staff card.
The bagging platform measures weight to help decide whether you’ve put the scanned item in the bag. It doesn’t know what an item is just by weighing it, so that decision depends on other information too.
That leaves us with a question about the first lever: what does the checkout trust that reading to tell it? Staff approval gives us a timing question for the second lever, and an unknown response gives us the third. Recognizing what you don’t know is enough here.
If you’re stuck, return to the fare gate and compare pushing it while locked with pushing it while unlocked.
It’s also worth checking whether your idea uses the machine at all. Reaching over a barrier might get someone to the other side, but it doesn’t tell us anything about how the barrier responds to its controls. Keep to an input the machine can respond to.
Knowledge check
Question 1 of 3
Practice complete
You've checked the key ideas. Revisit any explanation you need, then continue when it makes sense.
Check a different input
Section titled “Check a different input”Return to the fare gate. If it is already unlocked and receives another fare, what state does the supplied table say it enters? Does every input have to change the state?
Check your answer
It stays unlocked. A transition can lead back to the same state; the input still has a defined response. If you left that row out of a sketch, add the unchanged response rather than inventing a new state.
Next we’ll apply this model to a computer, whose state includes more than locked or unlocked.