Although I personally don't work on Byzantine block chains, we happen to be in the midst of a frenzy of research and hiring and startups centered on this model. As you probably know, a block chain is just a sequence (totally ordered) of records shared among some (perhaps very large) population of participating institutions. There is a rule for adding the next block to the end of the chain, and the chain itself is fully replicated. Cryptographic protection is used to avoid risk of a record being corrupted or modified after it is first recorded. A Byzantine block chain uses Byzantine agreement to put the blocks into order, and to force the servers to vote on the contents of every block. This is believed to yield ultra robust services, and in this particular use-case, ultra robust block chains.
Financial institutions are very excited about this model, and many have already started to use a digital contracts language called hyper-ledger that seems to express a wide range of forms of contracts (including ones that might have elements that can only be filled in later, or that reference information defined in prior blocks), and one can definitely use block chains to support forms of cyber currency, like BitCoin (but there are many others by now). In fact block chains can even represent actual transfers of money: this is like what the SWIFT international banking standard does, using text messages and paper ledgers to represent the transaction chain.
Modern block chain protocols that employ a Byzantine model work like this: we have a set of N participants, and within that set, we assume that at most T might be arbitrarily faulty: they could collude, might violate the protocol, certainly could lie or cheat in other ways. Their nefarious objective might be to bring the system to a halt, to confuse non-faulty participants about the contents of the blockchain or the order in which the blocks were appended, to roll-back a block (as a way to undo a transaction, which might let them double-spend a digital coin or renege on a contract obligation), etc. But T is always assumed to be less than N/3.
Of course, this leads to a rich class of protocols, very well-studied, although (ironically), more often in a fully synchronous network than in an asynchronous one. But the so-called PRACTI protocols created by Miguel Castro with Barbara Liskov work in real-world networks, and most block chain systems use some variation of them. They basically build on consensus (the same problem solved by Lamport's Paxos protocol). The non-compromised participants simply outvote any Byzantine ones.
What strikes me as being of interest here is that most studies have shown that in the real world, Byzantine faults almost never arise! And when they do, they almost never involve faulty servers. Conversely when attackers do gain control, they usually compromise all the instances of any given thing that they were able to attack successfully. So T=0, or T=N.
There have been a great many practical studies on this question. I would trace this back to Jim Gray, who once wrote a lovely paper on "Why Do Computers Stop and What Can Be Done About It?". Jim was working at Tandem Computers at that time, on systems designed to tolerate hardware and software problems. Yet they crashed even so. His approach was to collect a lot of data and then sift through it.
Basically, he found that human errors, software bugs and design errors were a much bigger problem then hardware failures. Jim never saw any signs of Byzantine faults (well, any fault is Byzantine. But I mean malicious behaviors, crafted to compromise a system).
More recent studies confirm this. At Yahoo, for example, Ben Reed examined data from a great many Zookeeper failures, and reported his findings ina WIPS talk at SOSP in 2007. None were Byzantine (in the malicious sense).
At QNX Chris Hobbs has customers who worry that very small chips might experience higher rates of oddities that would best be modeled as Byzantine. To find out, he irradiated some chips in a nuclear reactor, and looked at the resulting crashes to see what all the bit flips did to the code running on them (and I know of NASA studies of this kind, too). In fact, things do fail. But mostly, by crashing. The main issue turns out to be undetected data corruption, because most of the surface area on the chips in our computers is used for SRAM, caching, and DRAM storage. Data protected by checksums and the like remains safe, but these other forms are somewhat prone to undetected bit flips. But most data isn't in active use, in any case: most computer memory just has random stuff in it, or zeros, and the longest lived active form of memory is to hold the code of the OS and the application programs. Bit-flips will eventually corrupt instructions that do matter, but corrupted instructions mostly trigger faults. So, it turns out that the primary effect of radiation is to raise the rate of sudden crashes.
Back when Jim did his first study, Bruce Nelson built on it by suggesting that the software bugs he was seeing fall into two cases: Bohrbugs (deterministic and easily reproduced, like Bohr's model of the atom: an easy target to fix) and Heisenbugs (wherever you look, the bug skitters off to somewhere else). Bruce showed that in a given version of a program, Bohrbugs are quickly eliminated, but patches and upgrades often introduce new ones, creating an endless cycle. Meanwhile, the long-lived bugs fell into the Heisenbug category, often originating from data structure damage "early" in a run that didn't cause a crash until much later, or from concurrency issues sensitive to thread schedule ordering. I guess that the QNX study just adds new elements to that stubborn class of Heisenbugs.
So, we don't have Byzantine faults in servers, but we do have a definite issue with crashes caused by bugs, concurrency mistakes, and environmental conditions that trigger hardware malfunctions. There isn't anything wrong with using Byzantine agreement in the server set, if you like. But it probably won't actually make the service more robust or more secure.
Bugs can be fought in many ways. My own preferred approach is simpler than running Byzantine agreement. With Derecho or other similar systems, you just run N state machine replicas doing whatever the original program happened to do, but start them at different times and use state transfer to initialize them from the running system (the basis of virtual synchrony with dynamic group membership).
Could a poison pill kill them all at once? Theoretically, of course (this is also a risk for a Byzantine version). In practice, no. By now we have thirty years of experience showing that in process group systems, replicas won't exhibit simultaneous crashes, leaving ample time to restart any that do crash, which will manifest as occasional one-time events.
Nancy Leveson invented a methodology called N-Version programming; her hypothesis was that if most failures were simply due to software bugs, then that by creating multiple versions of the most important services, you could mask the bugs because coding errors would probably not be shared among the set. This works, too, although she was surprised at how often all N versions were buggy in the same way. Apparently, coders often make the same mistakes, especially when they are given specifications that are confusing in some specific respect.
Fred Schneider and others looked at synthetic ways of "diversifying" programs, so that a single piece of code could be used to create the versions: this method automatically generates a bunch of different versions from one source file, with the same input/output behavior. You get N versions too, often find that concurrency problems won't manifest in the identical way across the replicas, and they also are less prone to security compromises!
Dawson Engler pioneered automated tools for finding bugs and even for inferring specifications. His debugging tools are amazing, and with them, bug-free code is an actual possibility.
Servers just shouldn't fail in weird, arbitrary ways anymore. There is lots of stuff to worry about, but Byzantine compromise of a set of servers shouldn't be high on the radar.
Moreover, with strong cloud firewalls, Intel SGX, and layers and layers of monitoring, I would bet that the percentage of compromises that manage to take control of between and N/2-1 replicas (but not more), or. even of attacks that look Byzantine is even lower.
But what we do see (including Reed's 2007 study), are correct services that come under attack from some form of malicious client. For an attacker, it is far easier to hijack a client application than to penetrate a server, so clients that try to use their legitimate connectivity to the server for evil ends are a genuine threat. In fact with open source, many attackers just get the client source code, hack it, then run the compromised code. Clients that simply send bad data without meaning to are a problem too.
The client is usually the evil-doer. Yet the Byzantine model blames the server, and ignore the clients.
It seems to me that much more could be done to characterize the class of client attacks that a robust service could potentially repel. Options include monitoring client behavior and blacklisting any clients that are clearly malfunctioning, capturing data redundantly and somehow comparing values, so that a deliberately incorrect input can be flagged as suspicious or even suppressed entirely (obviously, this can only be done rarely, and for extreme situations), or filtering client input to protect against really odd data. Gun Sirer and Fred Schneider once showed that a client could even include a cryptographic proof that input strings really came from what the client typed, without tampering.
Manuel Costa and Miguel Castro came up with a great system they called Vigilante, a few years ago. If a server was compromised by bad client input, it detected the attack, isolated the cause and spread the word instantly. Other servers could then adjust their firewalls to protect themselves, dynamically. This is the sort of thing we need.
So here's the real puzzle. If your bank plans to move my accounts to a block chain, I'm ok with that, but don't assume that BFT on the block chain secures the solutions. You need to also come up without a way to protect the server against buggy clients, compromised clients, and clients that just upload bad data. The "bad dudes" are out there, not inside the data center. Develop a plan to to keep them there!
Monday, 29 May 2017
Friday, 26 May 2017
More thoughts on the learnability of implicit protocols
While driving from Sebastopol (in Sonoma valley, north of San Francisco) to Silicon Valley (which is south of San Francisco), one has a lot of time to think about how human-operated cars coordinate and implicitly communicate. So I thought I might follow up on the posting I did a few weeks ago concerning the learnability of implicit protocols and see if I can't make the question a bit more concrete.
The best way to simplify a problem is to think of a base case, so I started by asking myself about the simplest model I could: vehicles modeled as points and a highway modeled as a straight line.
Interactions between vehicles would basically define a graph: any given car gets a chance to interact with the car in front of it, and the one behind it, and the protocol (whatever it might be) is like a state machine on these graphs.
So what behaviors would constitute a protocol in such a situation? Well, we presumably would have car A in state Sa, and car B in state Sb, and then some "communication" takes place. Not too many options: they either draw closer to one-another at some speed, move apart from one-another at some speed (I mean speed of closing or speed of separating, but probably the joint speed and direction of movement needs to be specified too), or perhaps one or the other brakes sharply or accelerates sharply. So here we have a "vocabulary" for the cars, with which they communicate.
A protocol, then, would be a rule by which A reacts to inputs of this form from B, and vice versa, since any action by B on A is also perceived by B itself (that is, even when B probes A, B itself may be forced to take some reactive action too: the human version is that you are trying to shift from some horrendously bad radio station to a different, slightly less horrible, alternative when you look up and notice that you've gotten much closer to the car in front you than you expected. So in this case it was your own darn fault, but just the same, you react!)
So to learn a protocol, we might imagine a series of "tests" by which vehicle B, approaching A from behind, experiments to investigate A's reaction to various inputs, recording these into a model that over time would converge towards B's approximation of A's algorithm. A similarly is learning B's behavior (and A might elicit behaviors from B. For example, sometimes a car comes up on my tail very close, and especially if we are already basically moving at the fastest possible speed, it annoys me enough that I gradually slow down, rather than speeding up, as he or she probably intended for me to do -- there is an optimal distance at which to follow me, if you are trying to do so. Similarly for most drivers. Drive 3x further back and I might ignore you completely. Drive at half that distance and my behavior departs from the norm: I slow down, which is suboptimal for both of us. My way of punishing your pushy behavior!).
If you could figure out how two cars can learn a protocol, then you could ask if this generalizes to situations that form trains of cars. So here, B catches up with a train: not just A, but perhaps X-Y-Z-A, with A in the rear and some form of agreed-upon protocol in use by X,Y,Z and A. B gets to join the train if it can learn the protocol and participate properly. Failing to do so leaves B abandoned, or results in an accident, etc.
Optimal behavior, of course, maximizes speed and minimizes the risk of accidents. I'm starting to see how one could add a kind of utility function here: B wants to learn A's protocol quickly and "efficiently", with as few tests as possible. Then B wants to use the knowledge gained to achieve this highest possible speed "jointly" with A. That defines a paired protocol, and the generalization becomes a train protocol.
Another observation: Suppose that B has a small set of models in a kind of grab-bag of models that cars commonly use. Now B's job of learning the model is potentially easier: if A is using one of the standard models, it may only take a very small number of tests to figure that out. Moreover, having a good guess might make some models "learnable" that would actually not be learnable with a small number of tests otherwise. This would fit well with the experience I've had in New Jersey, Belgium, Tel Aviv and California: each country has its own norms for how closely cars tend to space themselves on high speed throughways and in other situations, so while you can feel disoriented at first, in fact this only adds up to four models. If someone handed you those four models, I bet you could figure out which one applies with very few experiments.
Unless, of course, you accidentally end up behind a New Jersey driver who is learning the rules of the road in Tel Aviv for the first time, of course. I think I've encountered a few such cases too.
So that would be a further interesting case to consider: roads with mixtures of models: subsets of cars, with each subset using a distinct model. In fact my story of New York City cab drivers, from last time, would fall into that category. The cabs figure out how to form school-of-fish packs that flow around obstacles and other cars, no matter what those other cars might be doing. Meanwhile, there could easily be other protocols: New York public transit buses, for example, have their own rules (they basically are bigger than you, and can do whatever they like, and that is precisely how they behave).
Conversely, the New Jersey driver also illustrates a complication: the implicit protocols of interest to me are cooperative behaviors that maximize utility for those participating in the protocol, and yield higher utility than could be gained from a selfish behavior. But any vehicle also will have an autonomous set of behaviors: a protocol too, but one that it engages in purely for its own mysterious goals. And these selfish behaviors might not be at all optimal: I recently watched a teenage driver in the car behind me putting on makeup while talking on a cell phone and apparently texting as well. So this particular driver wasn't maximizing any normal concept of utility! And all of us have experienced drivers in the grips of road-rage, driving hyper aggressively, or teenage guys hot-dogging on motorcycles or weaving through traffic in their cars. Their sense of utility is clearly very warped towards speed and has a very diminished negative utility for things like accidents, traffic violations and tickets, or sudden death. So even as we learn to cooperate with vehicles prepared to cooperate, and need to figure out the protocols they are using, the environment is subject to heavy noise from these kinds of loners, inattentive drivers, reckless drivers, and the list goes on.
One thing that strikes me is that the cab driver protocol in New York, once you know it, is a good example of a very easily discovered policy. Despite a huge level of non-compliant vehicles, anyone who knows the cab protocol and drives using it will quickly fall into synchrony with a pack of others doing so. So the level of positive feedback must be massive, if we had the proper metric, relative to the level of noise.
Interestingly, there is clearly a pack-like behavior even for a line of cars driving on a single lane. This would be a very good case to start by understanding.
Of course the real-world-school-of-fish behaviors involve (1) shifting lanes, which is the easy case and (2) ignoring lane boundaries, which is a harder case. Given that even the cars on a string case taxes my imaginative capabilities, I think I'll leave the full 2-dimensional generalization to the reader!
The best way to simplify a problem is to think of a base case, so I started by asking myself about the simplest model I could: vehicles modeled as points and a highway modeled as a straight line.
Interactions between vehicles would basically define a graph: any given car gets a chance to interact with the car in front of it, and the one behind it, and the protocol (whatever it might be) is like a state machine on these graphs.
So what behaviors would constitute a protocol in such a situation? Well, we presumably would have car A in state Sa, and car B in state Sb, and then some "communication" takes place. Not too many options: they either draw closer to one-another at some speed, move apart from one-another at some speed (I mean speed of closing or speed of separating, but probably the joint speed and direction of movement needs to be specified too), or perhaps one or the other brakes sharply or accelerates sharply. So here we have a "vocabulary" for the cars, with which they communicate.
A protocol, then, would be a rule by which A reacts to inputs of this form from B, and vice versa, since any action by B on A is also perceived by B itself (that is, even when B probes A, B itself may be forced to take some reactive action too: the human version is that you are trying to shift from some horrendously bad radio station to a different, slightly less horrible, alternative when you look up and notice that you've gotten much closer to the car in front you than you expected. So in this case it was your own darn fault, but just the same, you react!)
So to learn a protocol, we might imagine a series of "tests" by which vehicle B, approaching A from behind, experiments to investigate A's reaction to various inputs, recording these into a model that over time would converge towards B's approximation of A's algorithm. A similarly is learning B's behavior (and A might elicit behaviors from B. For example, sometimes a car comes up on my tail very close, and especially if we are already basically moving at the fastest possible speed, it annoys me enough that I gradually slow down, rather than speeding up, as he or she probably intended for me to do -- there is an optimal distance at which to follow me, if you are trying to do so. Similarly for most drivers. Drive 3x further back and I might ignore you completely. Drive at half that distance and my behavior departs from the norm: I slow down, which is suboptimal for both of us. My way of punishing your pushy behavior!).
If you could figure out how two cars can learn a protocol, then you could ask if this generalizes to situations that form trains of cars. So here, B catches up with a train: not just A, but perhaps X-Y-Z-A, with A in the rear and some form of agreed-upon protocol in use by X,Y,Z and A. B gets to join the train if it can learn the protocol and participate properly. Failing to do so leaves B abandoned, or results in an accident, etc.
Optimal behavior, of course, maximizes speed and minimizes the risk of accidents. I'm starting to see how one could add a kind of utility function here: B wants to learn A's protocol quickly and "efficiently", with as few tests as possible. Then B wants to use the knowledge gained to achieve this highest possible speed "jointly" with A. That defines a paired protocol, and the generalization becomes a train protocol.
Another observation: Suppose that B has a small set of models in a kind of grab-bag of models that cars commonly use. Now B's job of learning the model is potentially easier: if A is using one of the standard models, it may only take a very small number of tests to figure that out. Moreover, having a good guess might make some models "learnable" that would actually not be learnable with a small number of tests otherwise. This would fit well with the experience I've had in New Jersey, Belgium, Tel Aviv and California: each country has its own norms for how closely cars tend to space themselves on high speed throughways and in other situations, so while you can feel disoriented at first, in fact this only adds up to four models. If someone handed you those four models, I bet you could figure out which one applies with very few experiments.
Unless, of course, you accidentally end up behind a New Jersey driver who is learning the rules of the road in Tel Aviv for the first time, of course. I think I've encountered a few such cases too.
So that would be a further interesting case to consider: roads with mixtures of models: subsets of cars, with each subset using a distinct model. In fact my story of New York City cab drivers, from last time, would fall into that category. The cabs figure out how to form school-of-fish packs that flow around obstacles and other cars, no matter what those other cars might be doing. Meanwhile, there could easily be other protocols: New York public transit buses, for example, have their own rules (they basically are bigger than you, and can do whatever they like, and that is precisely how they behave).
Conversely, the New Jersey driver also illustrates a complication: the implicit protocols of interest to me are cooperative behaviors that maximize utility for those participating in the protocol, and yield higher utility than could be gained from a selfish behavior. But any vehicle also will have an autonomous set of behaviors: a protocol too, but one that it engages in purely for its own mysterious goals. And these selfish behaviors might not be at all optimal: I recently watched a teenage driver in the car behind me putting on makeup while talking on a cell phone and apparently texting as well. So this particular driver wasn't maximizing any normal concept of utility! And all of us have experienced drivers in the grips of road-rage, driving hyper aggressively, or teenage guys hot-dogging on motorcycles or weaving through traffic in their cars. Their sense of utility is clearly very warped towards speed and has a very diminished negative utility for things like accidents, traffic violations and tickets, or sudden death. So even as we learn to cooperate with vehicles prepared to cooperate, and need to figure out the protocols they are using, the environment is subject to heavy noise from these kinds of loners, inattentive drivers, reckless drivers, and the list goes on.
One thing that strikes me is that the cab driver protocol in New York, once you know it, is a good example of a very easily discovered policy. Despite a huge level of non-compliant vehicles, anyone who knows the cab protocol and drives using it will quickly fall into synchrony with a pack of others doing so. So the level of positive feedback must be massive, if we had the proper metric, relative to the level of noise.
Interestingly, there is clearly a pack-like behavior even for a line of cars driving on a single lane. This would be a very good case to start by understanding.
Of course the real-world-school-of-fish behaviors involve (1) shifting lanes, which is the easy case and (2) ignoring lane boundaries, which is a harder case. Given that even the cars on a string case taxes my imaginative capabilities, I think I'll leave the full 2-dimensional generalization to the reader!
Saturday, 13 May 2017
Smart Memory: How tight will the timing loop need to be?
Smart memory systems that integrate scalable data capture, computation and storage with machine-learning technologies represent an exciting opportunity area for research and product development. But where should a smart memory live in today's data center computing "stack"?
Cornell's work on Derecho has been focused on two design points. One centers on Derecho itself, which is offered as a C++ software library. Derecho is blazingly fast both in terms of data capture and replication/storage speeds and latency, but can only be used by C++ programmers: unlike other C++ libraries that can easily be loaded by languages like Java or Python, modern C++ has many features that don't currently have direct mappings into what those languages can support (variadic template expansion and constant expression evaluation and conditional compile-time logic), hence it will be a while before this kind of very modern C++ library is accessible from other languages.
The other main design point has simply been a file system API: POSIX plus snapshots. Derecho incorporates an idea from our Freeze Frame File System in this respect: the file system snapshots are generated lazily (so there is no "overhead" for having a snapshot and no need to preplan them or anything of that kind), and our snapshots are temporally precise and causally consistent.
Today, Derecho v1 (the version on GitHub) lacks this integration, but fairly soon we will upload a Derecho v2 that saves data into a novel file system that applications can access via these normal file system APIs. One can think of them as read-only snapshots frozen in time, with very high accuracy. Of course the output of these programs would be files too, but they wouldn't be written to the original snapshot: they get written to some other read/write file system.
This leads to a model in which one builds a specialized data capture service to receive incoming sensor data (which could include video streams or other large objects), compute upon the data (compress, deduplicate, segment/tag, discard uninteresting data, etc). The high-value content needs to be replicated and indexed. Concurrently, machine learning algorithms would run on snapshots of the file representation, enabling the user to leverage today's powerful "off the shelf" solutions, running them on a series of temporal snapshots at fine-grained resolution: our snapshots can be as precise as you like, so there is no problem accessing data even at sub-millisecond resolution (of course in the limit, the quality of your GPS time sources does impose limitations).
The puzzle is whether this will work well enough to cover the large class of real-time applications that will need to respond continuously as events occur. In the anticipated Derecho smart-warehouse the performance-critical step is roughly this: data is received, processed, stored and then the machine learning applications can process it, at which point they can initiate action. The key lag is the delay between receipt of data and stability of the file system snapshot: at least a few milliseconds, although this will depend on the size of the data and the computed artifacts. One can imagine that this path could be quite fast, but even so, the round-trip cycle time before an action can occur in the real-world can obviously easily grow to 10's of ms or more. We plan to do experiments to see how good a round-trip responsiveness we can guarantee.
The alternative would move the machine learning into the C++ service, but this requires coding new ML applications directly in C++. I'm assuming that doing so would be a large undertaking, just considering how much existing technology is out there, and might have to be duplicated. The benefit of doing so, though, would be that we could then imagine response times measured in milliseconds, not tens or hundreds of milliseconds.
I would be curious to hear about known real-time data warehousing use cases, and the round-trip response times they require.
Cornell's work on Derecho has been focused on two design points. One centers on Derecho itself, which is offered as a C++ software library. Derecho is blazingly fast both in terms of data capture and replication/storage speeds and latency, but can only be used by C++ programmers: unlike other C++ libraries that can easily be loaded by languages like Java or Python, modern C++ has many features that don't currently have direct mappings into what those languages can support (variadic template expansion and constant expression evaluation and conditional compile-time logic), hence it will be a while before this kind of very modern C++ library is accessible from other languages.
The other main design point has simply been a file system API: POSIX plus snapshots. Derecho incorporates an idea from our Freeze Frame File System in this respect: the file system snapshots are generated lazily (so there is no "overhead" for having a snapshot and no need to preplan them or anything of that kind), and our snapshots are temporally precise and causally consistent.
Today, Derecho v1 (the version on GitHub) lacks this integration, but fairly soon we will upload a Derecho v2 that saves data into a novel file system that applications can access via these normal file system APIs. One can think of them as read-only snapshots frozen in time, with very high accuracy. Of course the output of these programs would be files too, but they wouldn't be written to the original snapshot: they get written to some other read/write file system.
This leads to a model in which one builds a specialized data capture service to receive incoming sensor data (which could include video streams or other large objects), compute upon the data (compress, deduplicate, segment/tag, discard uninteresting data, etc). The high-value content needs to be replicated and indexed. Concurrently, machine learning algorithms would run on snapshots of the file representation, enabling the user to leverage today's powerful "off the shelf" solutions, running them on a series of temporal snapshots at fine-grained resolution: our snapshots can be as precise as you like, so there is no problem accessing data even at sub-millisecond resolution (of course in the limit, the quality of your GPS time sources does impose limitations).
The puzzle is whether this will work well enough to cover the large class of real-time applications that will need to respond continuously as events occur. In the anticipated Derecho smart-warehouse the performance-critical step is roughly this: data is received, processed, stored and then the machine learning applications can process it, at which point they can initiate action. The key lag is the delay between receipt of data and stability of the file system snapshot: at least a few milliseconds, although this will depend on the size of the data and the computed artifacts. One can imagine that this path could be quite fast, but even so, the round-trip cycle time before an action can occur in the real-world can obviously easily grow to 10's of ms or more. We plan to do experiments to see how good a round-trip responsiveness we can guarantee.
The alternative would move the machine learning into the C++ service, but this requires coding new ML applications directly in C++. I'm assuming that doing so would be a large undertaking, just considering how much existing technology is out there, and might have to be duplicated. The benefit of doing so, though, would be that we could then imagine response times measured in milliseconds, not tens or hundreds of milliseconds.
I would be curious to hear about known real-time data warehousing use cases, and the round-trip response times they require.
Subscribe to:
Posts (Atom)