Assume every failure, retry and race goes the worst possible way ('adversarial non-determinism' or the gremlin), model the system as a small abstract state space with explicit properties and assumptions, and check the properties against every state — bugs like double-execution and infinite retry loops surface at the design stage, before any code is written.
Alloy is an open-source language and analyzer for formal software modeling. It lets users specify software systems and uses model-finding engines and accompanying solvers to explore those specifications, including mutable state and temporal behavior in Alloy 6. The project has been applied to security mechanisms, telephone switching networks, and other software-design problems. The Alloy website provides language documentation, downloads, case studies, and links to extensions and tools built on Alloy Analyzer and Kodkod.
Dafny is a programming language dedicated to directly proving code correct.
Frama-C is an open-source, extensible platform for modular source-code analysis and formal verification of C software. Developed for uses ranging from code navigation and teaching to research, safety certification, and security analysis, it combines analyzers implemented as plug-ins. The Eva plug-in uses abstract interpretation to soundly analyze all possible program behaviors and detect supported undefined behaviors, including invalid memory accesses, uninitialized reads, integer overflows, divisions by zero, and dangling pointers. The WP plug-in uses weakest-precondition calculus to verify functional correctness from ACSL contracts, loop invariants, and assertions, generating verification conditions for SMT solvers or interactive proof strategies. E-ACSL translates executable ACSL annotations into C code for runtime assertion checking and can be combined with Eva and WP; it uses runtime-error checks, GMP integers, and shadow memory while restricting translation to the executable fragment of ACSL. Frama-C also provides a graphical interface for browsing analyzed code, emitted alarms, inferred variable ranges, and dead code. Its plug-in architecture supports combining analyses, and the project includes the ACSL specification language and documentation for developing analyses and applying them to critical software.
Learn TLA+ is a free online guide by Hillel Wayne for learning TLA+, a formal specification language used to design systems and test designs for flaws. It is organized into a linear Core covering the TLA+ language, independent advanced Topics, and Examples showing how to write and understand specifications. The guide is a work in progress, with updates and a roadmap documented on the site; questions and feedback are directed to its GitHub repository.
Logic for Programmers is a book by Hillel Wayne covering formal methods, property-based and stateful testing, design by contract, SMT solving, and logic programming. During its development, a purchasable PDF was updated as the book progressed toward its final version.
Spark is a data-curation tool used to run jobs that prepare prompts and documents for synthetic-data generation. In DatologyAI's workflow, it supports the curation and synthesis stages used to produce large-scale training data.
A formal verification and model-checking tool used to specify and check major software user flows, such as cross-device notifications.
A service where clients bring a description of a system they want to build, and you analyse it for resilience bugs by assuming every failure, retry and race goes the worst possible way — catching bugs at the design stage, before code exists. The core method is explicit version of intuitive reasoning: encode the system as a small state machine, define properties it must hold (safety: nothing bad ever happens; liveness: something good eventually happens), explore the state space, and replace every source of nondeterminism with a 'gremlin' that always chooses the worst outcome.
Searchable transcript of Find Distributed Systems Bugs Before You Write Code — InfoQ (44:13). Search for a phrase, then click its timestamp to jump straight to that moment in the video.
Captions sourced from the original video on YouTube, published by InfoQ. The video, its captions and all related intellectual property remain the property of their respective owners; AINotes claims no ownership. Provided for research, accessibility and search — see the Transcript Notice and Copyright Policy.
00:11 I have a bit of a weird job. Companies pay me to find bugs in systems that don't exist, or more specifically, don't yet exist. They come to me with some sort of idea for a system they want, but they're also afraid the system might lose them customers if it goes wrong. and they asked me to look at their description and tell them if there's a really bad bug somewhere.
00:31 Growing up in sort of extreme programming and agile shops, this kind of felt verboden to me when I first started doing it. After all, we all kind of know that we can only find bugs at the very end when we have the whole coding system that we can test possibly in production. But it's actually a relatively simple process that all of us can do. And to show you that this is just even possible in the first place, let's walk through the thing doer.
00:51 The thing doer does a thing. It first checks to see if the thing has been marked done and then it marks the thing as done and then it actually does the thing. Would anybody like to shout out the problem with this thing doer? >> Yes, there you found a bug system that didn't exist. The problem with this is that we all know this is not how an actual system works.
01:20 The actual system is going to look like this. Doing the thing might fail. And if it fails, we have to retry. And if we retry, we get to this point where we check the thing is marked done and see, oh, it's been marked done. And then we just never do the thing. That's a bug. Now, the client might try to fix this by saying, okay, what if we instead do the thing and then mark it as done.
01:44 Now, if we fail and we retry, we have it marked as done, so maybe we can actually get it finished. This though has a new bug and it even has this bug if we even remove the possibility of it ever failing. This bug is the two thing doer bug. If we have two thing doers, the first might do the thing, but before it marks it as done, it might the second one might start up and do the same thing leading the thing to being done twice.
02:10 So this also has a bug, a different kind of bug. Question for everybody actually. Who here has built anything that looks like a thinger? lot of hands. Yes, because this is an abstract version of a very real kind of system, one that I see very often in our designs. I've also seen it fail many times in the real world. I have seen package senders that end up sending people two packages for the price of one, which is very good for the consumer, but makes the company a little bit sad.
02:37 I have seen scheduling systems that can end up accidentally scheduling two people to the same slot. And I really don't want to be shouting over somebody to try to get my point across. Although I might want to listen to their talk which would make it hard to give mine. I've even and this is was the worst I saw something that allowed you to install an app on a device twice which doesn't seem as bad as the first two but I'm thinking of very particular system where if it was trying to install something and you told it to
03:02 install the same thing it would first stop running and start randomly deleting files on the device. So hopefully I've established that this is something we all can do implicitly and intuitively. Finding bugs in descriptions of systems. My work is an explicit version of this. It's called formal methods. The way of taking systems, encoding them in mathematical notation and then using tools to find errors in those systems by exploring the entire state space.
03:32 I've been doing this for about 8 10 years now and I've talked about it a lot and I found out two things about this. One, any talk about formal methods can only have one possible conclusion which is you should try formal methods. This is a really terrible um conference talk though because most engineers do not need formal methods in the same way that most engineers do not need to learn graphics programming or geographic information services.
03:56 It's useful to a lot of people but not useful to far more people. Two, using formal methods has changed how I think about regular software in ways that I think are actually quite useful for people to understand. So instead of just talking about methods, I want to talk about the ideas I've learned from this that I use in everyday coding. We're going to be looking at three different aspects.
04:19 The ideas of properties, verification, and environments. or to be a bit less technical, what it means for systems to be correct, how we can verify this correctness, and what is needed to make correctness possible even in the first place. Now, I do have to admit something is that I was working on these slides until about like 9:36 a.m. today. So, while I uploaded the most recent version to the UCON site, it might not be up to date.
04:44 If you want to get the current version, um, you can go to this link over here which has the abstract current version of the slides and also if people ask me questions afterwards, I will do my very best to remember and write up the answers here. So with that housekeeping out of the way, let's start with what it means for a system to be correct. To formalize this notion, we have the idea of a property.
05:04 A property is something that should be true of a working system. If it is false, then the system is wrong in some way. Needs to be fixed. properties notably are booleans. They are either true or false. They are not partially true. An example of a property is that we have 99.9 59s of uptime. This is something that is verifiably true or false. If we are down for more than 5 and a half minutes a year, our system does not have this property and we need to make a more sophisticated system or migrate cloud providers
05:34 depending. This is a property. It is also a relatively complex property that is hard to verify. We are often interested in automatically verifiable properties that we can easily check. An example of this might be that all the messages we send in our system follow the appropriate schema. Did anybody here um see Ian Cooper's talk um on Monday night? Yeah, good talk.
05:56 I'd recommend checking it out. But that's kind of one some things he was talking about the ways of enforcing this property in his systems. But properties can get much more detailed than that or much more lowle. Even something like a unit test is a property. Testing that max of one two three is three is the property that a given input always gives a certain output.
06:14 If your system does not give that output for that input, something is wrong and must be fixed. Our thing doer had two properties that we talked about it failing. We don't do the thing more than once or a safety property, something bad that we want to prevent. And we do the thing at least once or livveness, something good that we want to make sure happens.
06:39 Now, I said that properties are booleans and this leads to a very interesting consequence. Take the property that a system can handle 10,000 queries per second. Think of the set of every possible system you could build that to some degree of abstraction satisfies this property. Now take the property of can satisfy two queries per second. Every possible system that can satisfy two queries a second.
07:04 The set of properties that can satisfy 10,000 queries is a strict subset of those that can satisfy two queries. So if a system can satisfy 10,000, it can satisfy two. We would say that being able to satisfy 10,000 having this property implies you have this property too or implication and this is an extremely useful thing that comes out of mathematics.
07:27 Some other examples of properties that satisfy this is that if you have no memory errors this implies you have no use after free errors. If you have exactly once delivery somehow you have at least once delivery and also at most once delivery. And something like GDPR compliance implies that you have cookie banners on every goddamn page of your site. Now notice that these properties on the lefth hand side are harder to satisfy than the properties on the right hand side.
07:52 But also if you know you have the property on the lefth hand side, you automatically have the one on the right hand side. This gives us a notion of property strength. The properties on the lefth hand side are stronger than the ones on the right hand side. Some properties are stronger than others. And this is really important for verification because if we have a property that is strong and we know it's satisfied like a test that a user can buy something with a coupon.
08:15 If this passes, we automatically know the system has all the weaker properties too. Like you can apply coupons and you can complete orders. If you run this test and it passes, you don't even need to run these tests hypothetically. But the other consequence is actually more important. the consequence of the contraositive. Notice in this space that there are three distinct regions.
08:39 The region that satisfies both 10,000 and 2 QPS. The region that satisfies two but not 10,000 and the region that satisfies neither. There is no region that satisfies 10,000 QPS but not two QPS. So if 10,000 implies two, two not holding implies 10,000 doesn't hold either. If your system breaks at three queries a second, it's clearly not going to handle 10,000.
09:04 This is called the contraositive and leads to something quite interesting. If we have our set of tests, our weaker tests, if we have a set of weaker properties, and we know one isn't satisfied, like you can't actually add shipping, we don't even need to look at the stronger property. We know it doesn't hold either. And question for you all, if you're trying to figure out what's wrong with your system, which is more helpful, knowing that this test fails or knowing that 70 of these tests pass and this one fails, which
09:31 will isolate the error more? Yes, the second one. It is pretty much universal that strong properties passing show that a system is correct while weak properties failing show why a system is incorrect. And this actually explains a lot of practice in how we verify systems. Think about the testing pyramid. You have endto-end tests, just a few of them, and then some more integration tests, and then a whole lot of unit tests.
09:58 The reason we do things this way is there's many reasons, but one of the big ones is that often we are trying to debug broken systems versus verifying correct ones. And this means that the unit tests provide us way more information about what could be going wrong than a single endto-end test. That's why we often want many more of these. In our thing doer, we had two versions of the thing doer.
10:22 Two different systems and two properties. We don't do the thing more than once and we do the thing at least once. The next step is to now that we have those properties figure out how we can represent a system in a way that can verify them or show them wrong. As before, we can do this intuitively, but the goal here is to find some sort of rigorous process.
10:40 Then we can apply it to way more complicated systems where this might not be as evident. Now the way we do this in formal methods is to first encode the system as a set of logical formula and then encode the properties as a set of logical formula probably linear temporally logically formula and then we try to run some sort of model check or SMT solver or proof theorem or proof assistant to do this and we're not covering any of that because again this is not about using these tools this is about thinking like these
11:05 tools so how do we actually represent a system in a way that can be verified the goal here is abstraction we want to find the simplest possible system that covers the expected behavior. The simplest system will have fewer error modes than the more complex real world system. But at the same time, if there's an issue in the small system, there's definitely going to be an issue in the larger system.
11:29 If thing doer is going to fail, the package center is also going to fail and probably much worse. So, this isn't perfect, but it is a very cheap way to find very dangerous bugs quickly. So at the highest level, what is the actual state of the thing? I'm going to propose three kinds of an algorithm we're on. This will be an enumeration. Check, mark, do, and done.
11:58 If we're on the check step, that means we're about to do check. If we're on do, we are about to do either do or fail. We also have whether or not we have marked the thing as done. This will be a boolean. In the real system, it'll probably be like a database record or a file somewhere or a date time stamp. But a boolean is and is all we really need to do this kind of analysis.
12:17 And then finally, we have how many times a thing has been done. It's not enough to make this a boolean whether it's been done or not because we want to make sure it's not done twice. So, it has to be an integer. This is all the state we really need to represent the system. And in looking at this, there's actually a really useful insight I already see here, which is that step and marked are machine variables.
12:37 They are internal to the system that we design ourselves. Done. The number of times something is done is a world variable. It represents some exterior part of reality. The difference matters a lot to us because machine variables are entirely in our control because we can design the system however we want. We can do whatever we want to these values. Whereas the world variables we have very limited control over.
13:03 We can do some things but not anything we want. I can design a system that can if I really want to I can design a system where marked goes from true to false again but if number of times done is two I can't make it one again. I can never unend the package. Okay. So now we have our states and now it's time to figure out what our system can actually do.
13:36 The first thing to do is figure out what are the initial possible configurations that the system can be in. There is only one that we're on the check step. We have not marked it as done and we have not done it any number of times. From here we ask what possible evolutions can happen in the check step. This is deterministic meaning there's only one possible thing that can happen in this step.
13:56 We go to the mark step. We have seen that marked is false. So we go from check to marked as opposed from check to done. From here again there's only one possible step. We go from mark to do. Here though we have two possible things that can happen. We can do the thing or we can fail. This is called non-determinism when more than one thing can happen from a given point in time a given state of the system.
14:22 So we can go to either the done step where we also set the number of times things has been done to one or we can fail and go down here back to the check step in a retry where marked is true and it's not been done zero times. Once we've done this, we have to explore both possible states. Figure out what can happen from those situations. And both of these are once again deterministic.
14:42 From the right-h hand state, we can go down. We can try to retry. We go back to check. But we see it's already been done. So we go back to done. Similarly, over here, if we try to retry over, if if we retry over here, we see it's already been done. So we go to the done step. And if we try to retry over here, we go back here. This is every possible configuration of the system.
15:01 We call this the state space. Each of these individual things is a state and each state has state. The word's overloaded. I know. I'm sorry. And every possible path through the system is called a behavior. I will try to use the word path because it's more colloquial, although I think behavior is the more technical term. So if I slip into that, I'm sorry.
15:22 Now that we have our state space, we have to verify our properties. Starting with we don't do thing more than once. That's a much simpler property to verify because that is what we call an invariant. Something that must be true in every given state. I would write it mathematically as it is always the case that the number of times it has been done is less than two.
15:42 Actual like if you look at actual notations they use a we squared thingy but I'm going to use always to be explicit. So to verify this property we just have to go through every possible state and see whether it holds this property. So for example this state over here we're done a zero that holds it. Same with this state same with that state. Same with that state.
15:59 Same with that state etc. Every single state satisfies this. So this holds. Now as to the bottom property what we call livveness. This is not a property on states. If it was we would immediately fail in the initial state because the initial state we have not done it. It is actually a property on paths. In this top path, we enter a state where it has been done.
16:27 Therefore, this path satisfies that property. This path on the this path on the other hand does not. If we go down to this state over here, this check true zero state, there is nothing we can possibly do that would get done to be one. Therefore, because at least one path does not satisfy this property, it does not satisfy to the system. there's the potential for a bug in the real world.
16:54 So V1 satisfies one property but not the other. That's bad. What about V2? In V2, instead of check, mark, do, we check, do mark. The new state space looks like this. And it seems from the state space that we now satisfy the below property. Even if we fail on the due step, we go back to a step where it is possible to still reach the done step. So it seems like this property is satisfied.
17:21 And if you leave now, you're going to be horribly misled. But before we explain why you'll be horribly misled, we have to talk about the other property, the safety property up above. I said this fails when we have two thing doers. So the question is how do we use this process of exploring the state space to repres on two thinkers. There's two aspects to this.
17:43 The first is to decide what is a local variable to each process and what is global to the whole system. World variables like the number of times something's been done are almost universally global variables. They are shared between all processes and the external world. On the other hand, machine variables can depend. I will argue that these are probably sharing a database somewhere.
18:07 So the marked is going to be a global variable, but the step each process is on is local. So I would say that each one has its own checks is has its own step and we start in check check. Marked is a global variable that's false and the number of times it's been done is zero. The next question is how do we represent concurrency? How do we decide which process happens first?
18:26 Well, that's just nondeterminism. I can say either the blue process happens or the red process takes a step. And from here I can say blue cross pro red happens or red happens. And I can just keep doing this. Eventually I'll reach a point where number of times this has been done is two following blue blue red red or red blue red or blue etc. So we can say that this property up above is not satisfied by the thing doer mark 2.
19:01 That is property checking in a nutshell. In practice though, we don't usually do things this way in our heads. And the reason why is, did it just shut off? Oh, no. Okay. Is because usually we're not dealing with 12 states, but 800 or more likely 10 million or 100 million states. So this is something but this is how the tools often work. This is something that can be done by tools.
19:21 It works the same way. We take an initial state. Then we find every state that we can that then we find every possible succeeding state from that initial state and then we repeat the process in every state we found. Sometimes this will bring us back to a state which we've seen already which is fine. It just means that we have found a a different path to the same state.
19:43 And then we just keep doing this hoping to god that our state space is finite. And eventually we have seen the whole state space and we can check it for properties. I covered this kind of brute force analysis because that's how tools work and I think it's the best demonstration that this is something that is totally possible not magic. But again, this is not how we do things in our heads.
20:02 When you do enough formal methods, you start to develop an intuition for how things can go wrong. And the way this intuition works is by taking advantage of something called adversarial non-determinism or the gremlin. You take every source of non-determinance in your system, things like randomness, user inputs, concurrency, whether or not US East1 decided to do the better or not that morning, and at the abstract level, replace them all with a gremlin.
20:31 Whenever you have an undeterministic choice, you ask the gremlin what should happen. And the gremlin always gives you the worst possible answer. You can get pretty good at doing this in your head once you've done enough of this, just always figuring out what's the worst possible thing that can happen. And this gremlin is why this system does not actually satisfy the blow property because think about this.
20:48 We start in the check step. We go to the do step. And then here comes the gremlin and we ask the gremlin, hey, what should happen? Should we do the thing or should we fail? And the gremlin goes fail. So, okay, we're back here. And then we try again. We go to the doep and we ask the gremlin, okay, what should happen? Should we do the thing or fail? And the gremlin goes fail.
21:09 And then we get back to the check step and we go to the do step and we look at the gremlin and we decide, you know what, no, this is just not satisfied. Simply put, if we have any kind of loop like this, it is possible for us to enter the loop an infinite number of times and never actually get to the um and never actually get to a valid state. That's the easy case.
21:30 The much worst case is this. This does not satisfy livveness either, even if we remove the fail state. How does that work? Well, we get to the check state, we go to the do state, and then the gremlin pops up, and we're like, "Gremlin, what are you even doing here? There's determinism here. There's not even anything that can happen." The gremlin goes like, and he goes, "Okay, gremlin, what's going to happen?"
21:55 And the gremlin goes, "Meteor." or more realistically a server outage or a timeout or latency just being high enough that you don't get a response in the window you want or any number of things that can cause the system to just not do what you think it needs to do. And this brings me to the last aspect of this talk environment. Environment is all the assumptions that need to be true for our system to work.
22:29 In the first version of the thing doer, we need the assumption that the system never crashes to guarantee livveness. And this may or may not be like a good assumption, but it probably is one we kind of have to have. I mean, even think of something like trying to click a clicker, right? If you you have to assume it always works because it is totally valid for to have the error that you try to press a button, but before you do it catches fire.
22:52 Without the ability to say that things always make progress, you simply cannot have any properties at all. But this still reiterates that properties are things outside of our control. Our assumptions come from and often these assumptions come from other people's systems we don't have control over. If a vendor decides to switch from always consistent um delivery of messages to eventual consistency, what can you do about that?
23:14 You could change vendors maybe, but you can't tell them to go back to the old behavior. Now, so this is a really defensible assumption. But if we add in the fail state, we now need a much stricter assumption that do thing never fails. And this is a lot less defensible. If I see a um if I see like a client say, hey, we're just going to make this assumption that this never ever fails.
23:39 I'm going to be like, your system has a bug. Just saying. And this would honest this is something that might push us to using V2 where instead of the system in I realize I've only been 23 minutes, so I think I can like slow down by about like 45%. So in this case in V2, we no longer need the assumption that do thing never fails. We could have a much weaker assumption that do thing fails only a finite number of times.
24:17 Even if we fail at this step a million times, we still on the million and first go past this, we're done. We have satisfied livveness. And this kind of really fine grain assumption is what portal methods is really good at. It really forces you to think about all the kinds of assumptions of so many different types that go into a system. I would also like to point out that do thing never fails and do thing fails only by a number of times are very qualitatively similar similar properties if not quantitatively.
24:49 And this brings us back to strength and weakness. Some assumptions are stronger than others just like some properties are stronger than others. No failures is a stronger property than finite failures. Strong consistency is a stronger assumption than eventual consistency. When we have stronger assumptions, we can have stronger properties for the same level of sophistication of our system.
25:15 And correspondingly, weaker assumptions can be compensated by system design. Um, one good example of this I think about is I used to work for a company where we knew for a fact that every single one of our users would stop using our software at 4:00 New York time. This made deployments extraordinarily easy. we could just turn off everything around 6 p.m.
25:37 update it and turn it back on. We had a very strong assumption that made it easy for us to guarantee deployment properties. Imagine Google doing the same thing. Just imagine it. It would be very funny to imagine. Another thing though is that different systems require different levels of assumption for different properties. It's not monotonic. one system a system design doesn't make all properties necessarily easier to guarantee for the same assumptions.
26:05 We see this in version two. Again, in version two, we need a weaker assumption to guarantee livveness, but we need a stronger assumption to guarantee safety. We need to guarantee that we need to assume there is only one thing doer acting at a time. Now, it might be possible for there to exist V3 of the thing doer where V3 does not require either of these strong properties.
26:30 It might be able to work even with only finite failures, but also guarantee safety with only one with even if there's more than one thing doer. But that system, if it exists, is probably going to be a lot more sophisticated than either V1 or V2. I've found empirically that there's this relationship between sophistication of the system, the properties you want to guarantee and the strength of the assumptions you have where either one of these can be fixed and the other two kind of change based on that.
26:58 For example, if you want to guarantee livveness for the same level of assumption of say a message being passed like like are all messages processed? You can actually do that even with weak assumptions by weakening the property from all messages are processed to all messages are either processed or go into a dead letter Q. Similarly, if you look at something like um a spaceship just off the top of my head, a spaceship cannot even assume that the sorry a spaceship can even assume that the RAM is going to be consistent.
27:30 It's constantly being flipped by cosmic rays and radiation effects. So they have to have a much more sophisticated ass system for the same level of property. And one of the other consequences of this is that weakening a system weakening assumption often weakens the properties you have. If you take a fixed system that works and guarantees all your properties and then weaken one of the assumptions that are currently in this operating environment, it may not satisfy the properties it started out satisfying.
27:56 And I find this often leads to an enormous amount of bugs in practice where people build a system for an operating environment and it works and then the operating environment changes. I keep going back to this example because it's the one that I have the most vitriol over. But when a client changes a database from saying okay we're always going to give you update information to we're going to give it to you five minutes from now maybe we'll be consistent at some point.
28:18 You built I built that dep on we built that depending on it being always consistent strongly consistent. When it switches to a weaker assumption our properties start failing. Theirs might be satisfied ours are not. So those are three of the perspectives I use very often coming from formal methods. In a summary of what I've talked about, systems have assumptions and properties.
28:46 These can be related in terms of strength. Some properties are stronger than others and some assumptions are stronger than others. A for a given property and assumption, the system sophistication depends on both these things. A system needs to be more sophisticated to handle a stronger property and it needs to be less sophisticated given a stronger assumption.
29:08 Strong properties show correctness. When they pass, we know our system is correct. Weak properties show incorrectness. They're used to debug why things are going wrong. And we can look at a simplified model to find a real world bug in the system. And then finally, beware the gremlin. I hate the gremlin. Yes. So ultimately, a lot of this comes out of mathematical analysis of software.
29:30 We don't necessarily have to do this mathematical analysis oursel, but we can still gain the benefits of the things it gave us. We see this in a lot of fields, in formal methods, in functional programming, in type systems. I honestly find the mathematics behind this all really cool, and I'm glad that it actually gives us so many benefits. So to quickly wrap up, I want to talk about a couple of resources.
29:48 If you've decided after this whole talk that's not about formal methods that you just really want to learn formal methods, well I'm sorry I I failed. But I do have this resource that I've been working on called learntla.com which is designed to teach one such method called TA plus which is relatively popular relatively popular in the industry. It's pretty good for this kind of concurrent system and finding bugs in that.
30:14 It's not the only formal method out there though and there's not really like zealot wars about this. This isn't like emacs versus vim. So if you come to me afterwards and you just talk about the quest about the um system you have I can tell you whether this is the most appropriate thing or recommend resources for another one like alloy or p or quint or prism or I can keep going like this or you can just hire me to like work with you.
30:35 I do that too. The other thing is though as mentioned I've really been fascinated by how we can derive useful insights into everyday software engineering from mathematical perspectives and for that reason I've spent the past 3 four years working on this book called logic for programmers. It covers methods but also things like property and stateful testing design by contract SMT solving logic programming.
30:58 If this is something that might interest you it's currently in it's not done yet. It's currently in copy editing. I'm waiting on copy editing and the technical reviewer, but I've actually done the first um printing proof to actually make it into a physical real book you can buy. So, that should hopefully be ready in like July, I'm hoping, assuming everything goes according to schedule, it will not.
31:14 But, if you're interested, you can buy the PDF of the current version, which will automatically update to the final version when it's done, at this link for $10 off. And I realize I am currently 10 minutes under time, so that gives a lot of time for questions, either now or in the hallway track. Thank you so much for coming and I'm happy to answer any questions.
31:39 And finally, I brought this book just so I can do this. >> Yeah. >> Over there. So I see one one person over there and then one person in the front row. >> Thank you. Um do you find a difference applying the technique of formal methods in kind of legacy messy systems versus you know brand new starting from scratch green field projects? Um yeah actually so it's a lot easier to apply it in in um green field but it's actually I found there's this interesting thing that happens in legacy systems where it's easier to
32:15 demonstrate the value of it and the reason why is because in a green field system you can't really argue that like any given bug it finds is actually a realistic like oh we would have found that later but in a legacy system you can be like hey I modeled our old system that had this critical bug found it in 2 seconds and then show that okay now that we can establish it can find the real bugs that we have faced let's use it to model ASP changes to that.
32:37 That's actually how I got started doing this. There was like systems that were going horribly wrong and we'd basically make a patch and they go horribly wrong and they make a patch and go horribly wrong. And then I when we were thinking of another patch, I like was just investigating these methods and I was like, okay, I've managed to reproduce the past five things that went horribly wrong in like 50 lines of spec.
32:57 This new patch has something else that went horribly wrong. Let's not do it just yet. Hello, my name is Hazel Weekly and I lead guardrails at ING. So, this is actually very relevant for me. One thing that I'm curious about is when we talk about these properties, when we talk about proving things, it's often easy to show it or to demonstrate it or to cur it in a small isolated component.
33:19 But if you have multiple different components and you want to reason about them as a whole, proofs don't compose. Properties don't necessarily compose. And so in the real world, what strategies have you found pragmatically for addressing that in a way that works? >> How much time do you have? >> How much time do you want? >> Okay, so generally there is this is like a big question in sort of the space and there is like but this is a kind of a big problem in any kind of space, right?
33:46 Like how do you compose when things are things can be independently correct but interact in ways that make them all break? This is known as feature interaction or boundary error. There's a really great book by Nancy Leon called Engineering a Safer World about trying to find these issues after the fact and that's really the best that we can do for the most part in formal methods.
34:03 The way that we can do this is by basically titrating the amount of abstraction we do. We can make a really abstract system of all the components working together and then we can do what's called a refinement to take one chunk of that global system and make a detailed version of that then plug that back into the abstraction to see if it behaves correctly with everything else still being abstract.
34:21 And you can do this progressively. Um, it's just really annoying and really hard to do because it's like really complicated and you're dealing with like multiple layers of abstraction. So, it's like not fun, but it's possible. And if this was fun, a lot more people would be doing it back there. And I'm just going to write down on this thing right now so I don't forget there was the first question was about leg.
34:47 I'm going to go back here and use the fact that I can do annotations to go legacy and then global interaction. That way I'll remember okay back there. >> Uh thank you for the talk. uh you were talking about uh correlation between assumptions uh properties and sophistication of the system and I wonder uh >> uh sometimes uh it's just impossible to meet the assumption uh to meet the properties if assumptions goes weaker.
35:19 Yeah, >> sometimes it is possible by uh making system more complex and do you have any tools in formal systems that helps to answer that question? Is it uh possible or not uh to uh make the system u comp uh to in change the system that way so it can uh meet uh properties with weaker assumption. >> Okay, there are two answers to your so just to um summarize the question if I miss this correctly.
35:55 Is it possible for methods to tell you whether if a assumption is weakened, it's possible to fix it with a more complicated system or if it's impossible? >> Yeah. Is it possible to uh fix it with uh change to the system uh without lowering the properties? >> So there's two answers to that. There's the um theoretical answer and the practical answer. Theoretical answer is no that it's not possible because that basically gets into like how do you prove anything like you could basically it is possible for a property to be
36:19 weak in such a way that is literally impossible to make it to make it it is possible to weaken an assumption in a way that makes the property always impossible to verify but it's not easy to necessarily show that's the case right that's like gets into like what is a proof how do we prove anything in practice it's very easy to sort of run I found it's very easy to sort of run like multiple like for given system multiple layers of assumptions and changes to it so you can say okay these properties always hold in our
36:41 system These properties hold if we have this assumption. If we have this assumption which is weaker than this assumption, this weaker version of these properties hold too but not these stronger versions. If this property is weakened, this refinement of the system satisfies the stronger property. So it is possible to do that through engineering effort but you can't automatically deduce that something would be impossible.
37:03 >> Okay, thanks. >> Um, great talk. Super interested in that. So unfortunately I mostly work in like non-deterministic systems. I'm sorry. >> Uh like agents or machine learning models? >> Yeah. >> Um how much of this can be applicable? Can we talk can you measure like the potential state space of the solution space or something like that or >> Yeah.
37:27 Like is there are there methods available that help sort of like find these failure states before the agent inevitably trips up into it? I think the challenge with agents is that it's kind of a non-determinism that we really haven't seen before. Like we think of nondeterminism as being like A or B can happen due to like the confluence of real world factors, but I feel with AI it's to some extent like it could do A or B.
37:51 Why? Temperature. So there hasn't yet been a lot of work in applying formal methods to make the agents themselves work correctly. Most of the work has been in either making sure the code that agents generate is valid or making sure the pipelines that the agents work in are valid, but actually verifying the agents themselves. It's not yet been established how to do that.
38:19 I was thinking maybe something like if you've got the trifecta of you know you can have stuff that can be exported and you you could find those links and the potential combinatorial sort of like if you combine three APIs and you give an agent that you you may not immediately get a an error but you've created the sort of potential for a complete >> yeah I mean I think that I think that that can be thought of as like an error in the three API If a human uses three APIs, couldn't ever happen.
38:49 If a poorly written program uses those three APIs, could they ever happen? In that case, I think that is verifiable. But the agent itself is something that I cannot I cannot like give you a professional answer on without misleading you and myself. I do not I do not have the expertise to really speak about that. >> Thank you. >> Agents and APIs. That's the newest um version of Dungeons and Dragons.
39:14 >> Hello. Hello. Um, so, uh, moving >> actually I'm sorry. Okay, thank I'm over there. Thank you. Hello. >> Hello. U, moving back to the world of systems that are supposed to be deterministic. Um, is there any work on deriving properties or assumptions from the source code or the comments or anything like that? >> Um, yes. So, that actually gets into a couple of ways we can take this question.
39:40 The first is how do we can we generate a specification from the source code? And there's actually been some really good work of using LLM to do that. >> Yay. >> Um, but the other thing is can we just if we have a deterministic system, it is possible to just prove it directly correct with the code itself. And that gets into a space called the formal verification of code which is its own entire can of worms.
40:01 Um, but like you'd be using tools like Daphne or Frammise or Spark to do that. either a dedicated language that can be directly proved to be correct or a augmented harness that goes on an existing language like framacy on CC code to prove existing CC code correct. >> Yeah. Does that answer your question or am I missing it by a bit? >> No, I I was just wondering.
40:24 Thank you. >> Okay. >> Hi. Uh one more one more question. Um, if I want to give this a go, um, am I looking at months of research and experimentation to kind of really really get the value from it or >> if you're looking at what, >> uh, giving giving formal methods a go on on a kind of an existing piece of software. >> Talk to me afterwards and I'll figure out the best learning path for you.
40:52 >> Okay. >> Um, yep. >> Um, related to that question, but a little bit more specific. Um, I've I've seen in like my workplace folks using uh skills to try and automate some of these like initial bug searches and security reviews and stuff like that. Have you seen in your experience people successfully try to adopt formal methods through skills using AI?
41:13 And if you have, have you seen it go successfully or poorly? >> Um, yeah. So, one of the things that's been really interesting about the new LLM age is that it's revealed a lot of revealed preferences to us. Like one thing it's revealed is that a lot of people really want to ruin other people's day by putting slop on the internet. But it also has shown me that a lot of people really want to use this kind of formal methods and they're just intimidated by the skill threshold required to get into it.
41:35 So there's been a lot more specifications both of code and of systems being written with LM which is a problem because they're really bad at it. Um the biggest problem with LLMs and like doing this stuff right now is that LM are just really really bad at figuring out properties. like they cannot do liveness at all and often their safety properties their invariance are things like oh if x and y is true and I know x is true y must also be true right so that again might change I mean these things get way too good way too
42:06 fast and my answer could be wrong by like May but right now it requires somebody who's already experienced in doing this stuff to get an AI to do it well but if you are experienced it does save a lot of boiler plate and a lot of pain and I love using them and I feel bad about loving using them. >> So you mentioned how uh your formal systems formal methods background help you to identify weaknesses in the systems.
42:35 Yeah. >> Um did you build an intuition how to build correct systems from it as well? I wonder. >> I think so. For example, for one thing I now hate any kind of graph data with a burning passion. The cycles they're everywhere. Yeah. I've I've definitely also noticed that like there's more of like an intuitive sense of like okay this is going to fail because this has a race condition so how can we design the system so that way this race condition doesn't matter.
42:57 I feel like I built that intuition but it could also be the case that I've built that intuition but it's totally wrong and I'm just overconfident. So I don't want to say like oh you too will become perfect at distributed systems if you do this intuition. Yeah. And again, this is all going to go I'm going to try to write all these answers on the flight back and just put them on that link over there.
43:18 So, if you want to find the answers afterwards or leave anything. Um, I think we've been going for 45 minutes. So, maybe time for one more question, then we should move to the hallway. >> So, is this a time consuming effort? Yes, you have. Yeah. So it is timeconuming but you but with the goal of being money saving and either a few days of specifying saving you like a couple weeks of development or saving you a couple weeks of trying to tell an angry customer no please do not cancel I'm sorry we lost our data but like
43:50 we won't do it again. Okay. So, so >> it is a time investment. >> If you do it early then it's not that then you can save money but >> yeah it late on a >> but yes but it will it will be timeconuming. >> Yeah.