Frits Vaandrager discusses "Model Learning" (cacm.acm.org/magazines/2017/2/212445), a Review Article in the February 2017 Communications of the ACM.
00:00 A new city. You park your car and you face an unfamiliar kind of parking meter. So you follow the steps, maybe make some mistakes. In the end, you figure it out.
00:17 We have an uncanny ability to solve puzzles like the parking meter. Now, a professor in The Netherlands has taught computers to do this as well.
00:27 Join us as Frits Vaandrager shows how a combination of automated queries can figure out how such black-box machines work, in Model Learning.
00:37 [Intro graphics/music]
00:47 Like the parking meter, this coffee device is a "state machine", where our actions move it from one state to another.
00:56 DR. VAANDRAGER: So, as human beings we sort of quickly discover how such a device works by interacting with it and mentally we construct a little state-machine model; we know how to use it.
01:07 Security researchers often probe a real-world system with a process called "model checking", which throws inputs at it to see how it will react. But first they need to create a theoretical version of that system.
01:21 DR. VAANDRAGER: You have a mathematical model of your system which somehow you constructed, maybe you did that manually based on the specification, maybe you extracted it from the software. And then what you want to do is to analyze that model; you want to explore all the states in the model, and there may be many.
01:38 But Dr. Vaandrager saw the same problem come back again and again.
01:43 DR. VAANDRAGER: Frequently I noted that I constructed models which did not accurately describe the systems I wanted to study. ... And so I became very interested in the question: O.K., how can we build reliable models of implementations, models that really describe what this implementation is doing? And that is what model learning is providing.
02:08 The process starts by probing the system.
02:11 DR. VAANDRAGER: What happens in model learning is that you do some experiments on the system: You press buttons, you observe the resulting outputs. And you systematically record those observations in a table. And then at some point you figure out that there is some finite automaton which could explain all the behavior of the system you're trying to learn. So then you formulate an hypothesis.
02:37 By iterating these steps, model learning reveals the hidden logic within a system -- and it's not always the logic its creator intended.
02:45 DR. VAANDRAGER: So for instance, in the case of the SSL protocol, we studied a whole range of implementations. We discovered that the state machines of all these protocol implementations are different. ... and then sometimes there are mistakes. So for instance in one implementation we actually discovered a serious issue, which meanwhile has been fixed, the implementation has been changed due to our efforts.
03:11 This method has been used to create new versions of outdated software, and has even exposed flaws in a bank card system used by millions of people.
03:21 DR. VAANDRAGER: What fascinates me about model learning is that you have a very interesting combination of nice theory -- automata theory is very elegant and nice -- and lots of applications. ... So finding bugs in some of the major protocols that underpin our Internet, that is a real application.
03:44 Get all the details in the February 2017 issue of Communications of the ACM, in the Review Article, Model Learning.
03:52 [Outro and credits]