Okay, can you all hear me? Is that all right? Good morning. I'm Jake Edge. I'm here from LWN.net. If you haven't checked out LWN, it's, we like to think of it as the premier news source for news of the Linux and free software development communities. So go give it a look if you haven't visited before. I put together the weekly security page for LWN and also write articles about various other topics that are hopefully of interest to free software developers of various sorts and Linux developers. And today we're here to talk about name spaces for security. So this is something of an agenda, I suppose, what we're going to be talking about. So we'll start off talking about the kinds of threats that systems face these days, the kinds of effects that attacks against systems can have, the defenses that are used typically, and then we'll start talking about name spaces in particular, the types of name spaces, how you create them, how you use them, some examples of ideas of things that you might do. As with any security technique, name spaces are no silver bullet. There is no silver bullet in security or perhaps anywhere else. So this is sort of part of a defense in depth. You could add name space based security to other techniques that you're already using or plan to use. So he talked about questions anytime you have one raise your hand and we'll get the mic to you and you don't have to wait until the end. So what kind of threats are we talking about? Typically there are, well there's lots of different kinds of threats of course, but you have targeted attacks where somebody is after your data in particular or your or access to your system in particular, those are much harder to defend against and sort of maybe outside of the scope of what we're talking about today. These days I guess it's not just attackers we're worried about, but maybe governments going after data in a particular location, doing a lot of reconnaissance and so on. That's a very hard, hard threat to defend against. So what we're talking about here are mass attacks where someone is running a particular script against a million web servers trying to exploit a particular web application flaw say or or that sort of thing. No problem. So typically one of the things that gets attacked is network facing services, right? I mean the attacks that we suffer today come from the network typically, but network clients shouldn't be forgotten as a potential attack. If a network client is talking to an attacker controlled server, it's possible that that server could induce some behavior in the client that could lead to a compromise of one sort or another. DNS cache poisoning is one that I think gets less attention than it deserves in that there are millions, hundreds of millions perhaps of Linux routers out there, generally Linux based routers out there that people are using to access the internet. They often have a caching name server on them and if an attacker can poison the cache on that name server then they can redirect any traffic for your bank.com to an IP address they control. That's a pretty powerful, pretty powerful technique I suppose. Web application flaws of course, you know, they're reported daily if not hourly or even minutely. There are any number of them at any given time and they often don't get patched necessarily all that quickly, so then these mass attacks try to exploit those flaws. And then there are the cross site attacks, cross site scripting, cross site request forgery. So those are the kinds of threats that systems under our control face these days. So what kinds of effects can a typical attack have? What can an attacker do when they successfully attack a system? Typically it's whatever the network service that's running, generally they'll be running under their own user, let's say you know the Apache user will be running the web server and that account gets compromised which means that the attacker can now run any code with the permissions of that user. And the Apache user on most systems is not a privileged user but that almost doesn't matter. That's not typically what attackers are looking for. You know the Apache user can typically access the network, it can access the file systems and generally can only access some subset of the file systems that are set up for it to use. It can access other processes. So where does that lead us? Well, network access gives an attacker the ability to set and spam. That's one of the things that is very common these days to do distributed denial service attacks. There are lots of botnets out there and these botnets get rented or sold or whatever to people who want to do these kinds of attacks or want to send spam and so the network access on a regular user allows an attacker to do that. They don't need any privileged access at all. File system access, of course, confidential information, configuration settings, keys to be able to log into some other system, whatever else. I mean there's a lot of stuff. Now one would hope that the Apache user wouldn't have access to all that information on the system using traditional UNIX access control mechanisms, but that is certainly a danger. And if you can see and deal with other processes, you can do things like P-trace them or send them signals or kill them outright so that you have a denial of service. P-traces particularly pernicious in the sense that, for instance, if you had multiple Apache servers running and one of them was compromised, then the Apache user can P-trace the other Apache servers that are running and possibly extract confidential information like usernames passwords or some kind of credentials or whatever. And then privilege escalation, I think it's fairly well accepted by most kernel developers. Matthew Garrett said something similar to this in a talk yesterday that on any given kernel there's some way to escalate your privileges to root available. It's probably not known. It's some sort of zero day, but they exist. And so compromising a regular user always seems like such a, maybe not a minor event, but not a major event, maybe. But in any case, if you can then escalate your privileges beyond the Apache user, say, to root, the whole system is compromised at that point. So our standard toolbox to avoid these kinds of threats are things like Unix permissions, your traditional RWX on the file system that restricts access to particular files or sets of files. Users and groups kind of go hand in hand with that. Certain users have certain access and so on. We also have mandatory access control in the Linux kernel. There's SE Linux and SMAC and App Armor and Temoyo. All of these add additional layers of security for protecting different kinds of resources. There's capabilities, which was an attempt that I don't think really worked out very well overall to separate the, you know, root has an enormous number of things it can do. And capabilities was an idea to separate those out into individual capabilities that could be granted to a program or a user to give them a limited set of the abilities of root without having to become root. The idea was good, I think, but it turns out that it's very difficult to specify what those capabilities should be and the way they were implemented now, it's a little difficult to add new ones. It's difficult for programs to know which are available and which aren't. And then they're a handful of the privileges that are supposed to be less than root can be leveraged to become root. So they are essentially the equivalent of root. It's a bit of a mess. A more recent one is the SecComp Sandbox. It's a way to put processes into a sandbox and only allow them to do to make certain system calls or make those system calls with certain arguments. So you could put a process into a sandbox and say it can't make the right system call or it can only make the right system call to standard error and standard out. It's used by a number of things or it's in the process of being used. It's pretty recent. Chromium, the Chromium browser was sort of the genesis of it, I think, at some level and the idea there was to put the rendering process into a sandbox with a restricted set of things that it was allowed to do so that if the JPEG renderer had a flaw in it of some sort, what an attacker could do with that was very limited. It could only call the system calls that the normal rendering process would call. There are lots more. Linux certainly does not suffer from a lack of security techniques, I suppose.  The original namespace was put in in the two, four days, I believe. But the set of namespaces has been growing over time and at some level they may be reaching completeness, though people keep proposing new ones. The most recent one that was added and I guess more or less completed in the 312 kernel, the last piece of the puzzle was finally dealt with, is the user namespaces. But the idea of a namespace is a way to partition the global resources of the system in a way that members of the namespace can see a different view than members of a different namespace of that global resource. The global resource could be things like process IDs or the mounted file systems or the host name. So the idea is that it sort of provides invisibility. If you have two namespaces that are siblings to each other, let's say you have the root namespace, which is your standard default namespace. If you don't do anything to add namespaces and you have two children of that that are siblings, essentially, they can't see that resource that the other one is using. So they each get their own view of it. It's kind of a lightweight virtualization technique. You can combine it with things like C groups, control groups to make containers, which are almost like virtual machines in that they have their own view of the system. They believe that they are the only things running on that system. The processes in that container are the only things running on that system, but in reality, they're all running on the same Linux kernel. That's the difference. That's the lightweight part. VMs, of course, are running on their own kernel, each running on their own kernel. They can be used for a number of different things, containers being one of them testing and debugging. You can isolate a process, a program that you're working on or a program that you've gotten maybe from a dodgy location that you're worried might do something unexpected and you can isolate it from the global resources like the global file system and so on. And then what we're here to talk about today is they can be used as an isolation mechanism for security purposes. So if you run a distro kernel, which probably lots of folks do, you probably have most of the namespaces already built in. User namespaces would be the exception for a couple of reasons. One is that the 312 kernel that finally completes the picture isn't even out yet. That's not due into Halloween. But also, there are some questions about user namespaces. I'll get to in a second. But in any case, to configure a kernel, to use namespaces, it's in the general setup menu. There's a namespace support. And so then you have config namespaces, which is the overall namespace support. And then you have configuration options for each of the different kinds of namespaces. And we'll get to those kinds in just a second. So depending on which kernel you're using, config user namespaces, the user namespaces were not available depending on what file systems you also had built into that kernel. And all of that goes away with code that Linus just merged last week for 312. So post Halloween, at least if you're using the most recent kernel, those problems go away. User namespaces allow regular users to become root in their own namespaces. And as you might guess, there are a number of subtle bugs that have been found, where there are sort of assumptions in the kernel about what root can and cannot do without considering the namespace issue. So I suspect it'll be a while before distributions will turn those on or at least turn them on so that regular users can create user namespaces. They may well turn it on so that root can do it. But there are almost certainly a handful of subtle bugs still out there that need to be shaken out. So you create namespaces, generally with the clone command. I'm sorry, system call. Clone is underlies fork. Unshare and setns do different operations on namespaces. All three of them share this set of clone flags that talk about which kind of namespace or namespaces are to be created. So if we look at this clone new NS, that is actually the mount namespace. At the time it was added, mount namespaces were added. It was the only namespace. This was way back when. And no one, I guess, at that point, envisioned other namespaces. So it was just create a new namespace. And the other ones are UTS, PID, NET, IPC, and user. And we'll talk about what each of those does in a minute. But clone is the system call that starts a new process. And so if you pass one or more of these flags to the clone call, then that process will be started in a new namespace. Unshare does sort of a similar thing, except that it doesn't create a process. It creates the namespaces. It takes the existing process, the current process, and puts it in those namespaces. And setns is used to join an existing namespace. The trick there is in order to join a namespace, you have to have some sort of handle for the namespace it is that you want to join. And we'll see how you go about getting that. One thing to note, the system D program has a mixed reputation, I guess you could say. A lot of people like it. A lot of people don't. I tend to like it. But in any case, whether you like it or not, system D N spawn is a useful tool for messing around with, with namespaces. It's also very useful. The code, of course, is available. And, you know, it's pretty nice clean code that's easy to look at to take a peek at how it uses namespaces, how it sets them up, etc. And when I do my demo, you'll see that I use it. It's certainly nothing to be feared, even if you don't like system D. But did I skip over? Yeah, we didn't do this, did we? Sorry. Yeah, I thought it got a little confusing there in the middle. Keyboard bounce or something. So backtracking a little bit. These we have these different kinds of namespaces. The mount, as I was saying, was actually the first created. But the UTS is probably the simplest that UTS stands for Unix time sharing. And it all it does is essentially virtualize the host and domain names. So if you create a different, two different UTS namespaces, and we'll see this, they will have, they can have different host names. So this is all part of the idea of doing a lightweight virtualization. Mount namespaces will give you a different view of the mounted file systems. This is another thing we'll see in the demo. The process or PID namespace virtualizes PIDs. So each PID namespace has from one to PID max, whatever that is, to itself, it has, you know, it has, it has a mapping of those process IDs. And those, those process ID numbers in the namespace map back to an actual process ID, a real process ID, if you will, in the root namespace. But the view, you know, if you're inside of that namespace, you can't see the process IDs in the root namespace, you can only see the process IDs in your PID namespace. Similarly, with the inner process communication, that's the system five stuff, the message cues and shared memory and so on. The IPC namespace virtualizes those networking is an interesting one, it separates all the networking devices, you know, your ETH zero, or whatever into separate, separate namespaces so that when you create a new networking namespace, it has no networking devices. You have to actually add the networking devices that you want that namespace to be able to use and processes inside of that namespace cannot use the global networking devices, thus the global networking setup, unless you configure things that way. And then the username space is the most recent one, and it virtualizes the UIDs and GIDs. And so that you can have a user 1000 in two separate sibling namespaces that have no correspondence to one another, that this 1000 can't look at this 1000's files and vice versa. And more interestingly and importantly, you can have a root in both, neither of which is the root in the global of the root namespace, but is root for that username space and can operate as a privileged user within the namespaces. So let's see if I can go a little slow back to where we were. Okay, so this, pardon me, is my attempt to use LibreOfficeDraw to show how this is sort of a diagram of what you're about to see in the demo. We've got the root namespace and it's got its set of PIDs, and it's got a particular file system or directory in this case. And that directory SRVF19, sorry about that. SRVF19 is it's just a directory with a stripped down Fedora 19 in it that I use for the demo. And it gets mapped to the slash directory inside of the namespace. And this is a namespace that gets created by system DN spawn. It has, you know, its own set of PIDs that correspond to the PIDs in the root namespace, but processes inside of this namespace cannot see, though it's to see or use these numbers at all, right? If they refer to process 444, it doesn't exist. There is no such PID inside of the namespace. So then I talked about needing to be able to get a handle on namespaces. And the way that you do that is with the proc file system, you use the, for a particular process ID, there is a names, an NS directory, namespaces directory, and it has files and which files it has depends on which namespaces you have configured into your kernel, but it could have as many as six files for all the different namespaces. And those files are references to the namespace so that you can for set NS, you can open those files. So you have an open F file descriptor that you can pass to set NS to say this is the this is the namespace of interest. This is where I put my process in this namespace. So and we'll see, see what those look like. I mean, when you do an LS, they sort of look like symbolic links, but they're actually some magic kernel object that that you can use to to reference reference the namespace. So this is almost by way of a caveat, or at least it really confused me early on when I first started playing around with this stuff early in the year, sort of in the abstract, based on what I've already told you, you would expect that given two separate mount namespaces, if you mounted something in one, you would not see it in the other. And if you mounted something in the other, you would not see it in the one. And that can be true. But in general, may not be true. Evidently, that sort of conceptually correct behavior was painful for some of the kinds of applications people were trying to do with with mountain namespaces, and may still be. So this whole idea of shared private and slave mounts came about. And so if you if a particular file source system hierarchy is Mount shared or has the shared flag, then child namespaces see what gets mounted in it, and parent namespaces see what gets mounted in it. If it's private, then neither of those things is true. And then the third is slave, where child namespaces see it, and parent namespaces do not. And you can change the behavior using these mount commands that I have here. And you can use the recursive variant to change that for all mount points underneath. It's basically a question of where further mounts will actually show up. And a lot of, well, maybe not a lot, certainly Fedora defaults to shared mounts. So if you start noodling around with this stuff like I did, and you, you know, mount some things in one place and don't expect them to show up in the other, you will be very surprised. So you'll see when I do the demo that I set them all to private so that that doesn't happen. Oh wait, you should wait for the in. So for shared, it's really just children and parents. And it's not just, it's not all namespaces on the system. It's just the children and the parents of the current one. If they are shared, all namespaces in the system see it. And if they are, yeah, if the slave only the child, only the children will see it. So now, assuming all goes well, I'm going to show you a little demo of how this all works. So first off, is this font big enough for people? Can everybody see that? Is that reasonable? Okay. So these are just regular. I have two shells here.  And I'm gonna log them in as route because messing with namespaces requires route privileges. So okay, so first off, let's start by making the mount space private. So that recursively sets the mount the mount space private for the entire hierarchy on the system. And then we'll start. So there I have told system to end spawn that I wanted to use SRV F 19 as the root file system for the set of namespaces that it's going to create. And we'll see in a second which which namespaces it created. And it runs this bash process as the init within that within that set of namespaces. So if we look here, all we have is just the the bash init process. And then the PS that I just ran, that's within the namespace. And if we go outside of the namespace and we look, we'll see this bash here to 402 is actually the one that it reported right over here as the init process in that container. And so but if we let's say wanted to try and kill the system to end spawn from within the namespace, there is no process that 24 01 it exists, it's the bash, but it's not, it's not, you know, mapped to that process ID within the namespace. If we look at the, if we look at the namespaces now, okay, so if we look at the namespaces for that process, and this is this is the the process, the init process in the namespace, you can see the different namespaces that it is associated with. And if we look at the same information for something outside of the namespace, we can see that we have some different values. The IPC namespace is different between them. The Mount namespace is different. The net namespace is the same. The PID namespace is different. And the user and the user is the same and the UTS is different. So the hostname on my laptop, it was about land. The hostname over here is F 19. And then if we just touch a file in the temporary file system, so now I guess I should have shown it wasn't there, but it doesn't really matter, I don't think. So anyway, so it's there. And we can actually see it on this side because we can see same same file is there. But if we bind mount, if we bind mount the password file on that, we see that the password file is is bind mounted on that particular file. But we come over here, still empty, append something to the file. They're not they're not related. They're in separate namespaces. And and the Mount propagation was set up such that such that that won't the mount that was done in the root namespace won't show up as part of the child namespace. So if we talk about a few examples of the kinds of things and once you start thinking about this and you can you can come up with with lots of different ideas. And when you start doing things like adding in usernamespaces or network, well, network namespaces I talked about here, there there are additional ideas that you can come up with of ways that you can further isolate your processes so that if they are compromised, the amount of damage is limited or or eliminated, depending on the situation. So if you have some sort of update checker that checks for updates, but you're concerned, perhaps that the that the other end might be compromised or that your DNS cache gets poisoned sometimes and and you go off and and actually check for updates at a at an attacker controlled site. Maybe you would set up a mountain namespace to run that update checker, allow the the access it needs to the libraries to run and has its own private temp. And then if it finds that there actually needs to be an update applied, it you know communicates that to the system somehow some other way, or you know, via some mechanism. And another might be to run multiple instances of a web application in a in separate pid namespaces. In that case, then if that web application got compromised in some fashion, whatever program or shell or whatever the attacker was doing would not have access to the process IDs of the other processes that might be of interest so that the P trace thing that I talked about earlier wouldn't wouldn't work. You could combine the two those two things and have a separate mountain namespace and pid namespace for a web application. So that you know, if it gets compromised, it can't actually access any of the files elsewhere in the file system. Network namespaces, you could set up a separate network namespace to run a HTTPD web server worker process. And that network namespace has no networking, essentially, and you pass it a file descriptor with the with the connection from the client. So it can still read read and write information to that client, but it can do no other networking. So if it gets compromised, it has no access to the network. You could also separate your network namespaces in such a way that you have some for local access, local network access and some for internet access. And so any internet client, let's say someone runs, you know, something that talks to the internet and, you know, gets a bad JPEG or whatever that the compromise that results from that can't access your internal network, because it doesn't have any of the of the networking devices and configuration to do so. And you can keep keep going from there. So that's all I have today. I'm happy to take questions. So what are the any performance penalties you might incur on like large servers that you're trying to isolate applications? Do you take any hits and performance that are noticeable? That's a very good question. I don't know the answer to that. That's probably something I should look into. The if if you are running a distro kernel, you know, you already have those checks in there, even if you don't have namespaces enabled, right?  I would think the impact should be minimal, but it's definitely something I should look into. Thanks. So why would this be preferable to just charooting an app? I'm sorry? Why would this be preferable to just charooting an application? Well, charoot is has its own set of problems, right? I mean, charoot is is is fairly easy to escape if you can be if you become root on the box. And charoot does not do things like separate PIDs or separate a network devices or, you know, it's only focused on the file system. So if that's the only piece that you think you need to protect, then, you know, it really depends on your application, of course, but but you could, you know, namespaces are a more foolproof charoot in the in the file system area, and then add all these other kinds of capabilities. Does that make sense? I could just point out that if you're charooted in and then someone manages to get root within the charoot, then they can make nod your root file system device and then mount it within the charoot and it's rooting to that and now they have root on your system. Any other questions, comments, thoughts? Well, thank you very much for your time and attention.


Alright, today let us formally solve this problem of a continuous time random walk on a lattice in D dimensions. Just to be specific let us take a hyper cubic lattice. So here is the problem we are going to solve. It is a continuous time random walk on a hyper cubic lattice in D dimensions and we could specialize to D equal to 1, 2, 3, etc., etc. So just to recapitulate we already know a lot about this. What I would like to do is to write the formal solution down. It is fairly straightforward to do it for a class of continuous time random walks governed by some renewal process in time and then we will look at the diffusive behavior the first moments and second moments of the displacement and so on and understand how diffusion comes about in this case. So all the while we will have the Markov case as a check on our calculations because we must reduce to the known results in the Markovian random walk case which we solved completely. So here is what happens. Let me denote by J an element of hyper cubic lattice in D dimensions labeled by the integers infinite lattice. So this J is shorthand for J 1, J 2 up to J D where these are all integers. So that is a lattice point and we are going to look at walks which by translation variance we started the origin in this D dimensional lattice and we take steps in time. Now the first thing is we ask what is the probability of being at the side J at time n. So just to avoid confusion with what happens in continuous time let me put the subscript outside to show that this is equal to the probability of being probably probability of being at of the walker being at J at time n given that the walker was at the origin at time 0. We already know this. We know this is some combinatorial factor it depends on whether there is a bias in the problem or not. We already know what this quantity is it is some multinomial coefficient because remember that in the case of one dimension it was just a binomial coefficient with some factors which depended on the bias to the right or to the left etc. We could as well take a bias in this problem also. So let us suppose that you have bias factors alpha i and beta i equal to 1 minus alpha i so these are bias factors but i is any one of these directions okay. So in the dimensionality 1 to D any one of them could have a bias but we also need to know the total probability must be 1. So we also need to write summation i equal to 1 to D alpha i plus beta i sorry alpha i and beta i in general after you sum this is equal to 1. So in each Cartesian component you have a bias and the total probability of a jump out of a site into any one of its nearest neighbor sites is equal to 1 okay. So each of these is a fraction the unbiased case the unbiased case would be every one of these factors is equal to 1 over 2 D alpha i equal to beta i. So it says if you are in three dimensions for example there are six nearest neighbors and the probability of jumping right or left each of these is one sixth or top or bottom etc okay. So this is some multinomial coefficient in fact we know what this fellow is explicitly we looked at its generating function and let me call the generating function let us call that G sub n of Z 1 up to Z D this is equal to a summation over all components of J elements of Z D over all the integers for each component P n of J Z 1 to the J 1 dot dot dot Z D to the J D that is the generating function what is the random variable here J is the random variable you are given a time and this components the components of J they are random numbers they are random integers you want to know which site you ended up at etc. And this is the generating function okay this coefficient here as we know is a multinomial coefficient right we already know what this P J looks like we know what this generating function looks like remember for one dimension this was P times Z alpha times Z plus beta times Z inverse to the power n. So in the general case this quantity here is equal to summation I equal to 1 to D alpha I Z I plus beta I over Z I the whole thing to the power n because this is the generating function for a single step which could be in any one of the sec 2D directions okay. So we already know this and therefore what you are asking for is of this quantity when you take this fellow and you expand it in powers of each of the Z's the coefficient of this combination is this quantity which you want here so it is a multinomial coefficient. So let us call give it a give this fellow a name this is equal to G of let us collectively call it Z to the power n okay I want to make the notation straight that is the reason I am taking pains to do this that this is just a shorthand for Z 1 Z 2 up to Z D okay. Now let us introduce so this in a sense this problem is trivial we know how to solve it once you know how to make a multinomial expansion this identifying this quantity is trivial okay. Now let us ask what happens we put continuous time on this right so let us go to continuous time and the way to do this is very simple. Now I ask what is the probability of being at the site J at time t since t is a continuous variable I put this index inside here okay this is obviously equal to a summation over n from 0 to infinity in principle P n J times W of n comma t where this fellow here is the probability of n jumps in the time interval 0 exactly n jumps and you are going to allow for all possibilities so you sum over n okay remember the different jump events are independent events so the probability that you have 10 jumps in time t is distinct from the probability that you have 15 jumps and so on these are mutually exclusive events the number of jumps and therefore I sum over all these guys so I have separated out the spatial and the temporal parts all the time dependence is sitting here the space part is right here and that is just pure combinatorial factors now you can generalize this to other lattices you do not need this hyper cubic lattice you have to tell me what is the quote unquote generating function or characteristic function for a single event jump event and that is what this quantity is so on any lattice you can find out what are the nearest neighbor vectors etc and find out what this quantity is and after that you are guaranteed that since the jumps are independent of each other this is the generating function for this probability distribution now you could ask what happens if the system remembers its previous jump and so on all that is happening in time so that is going here that input is going here so the jumps could all be uncorrelated with each other and that will show up in w of n, t so as it stands this is the very general framework out here now we can ask what about what can we say about the generating function for this so let me call I need a new symbol so let us call it L of z, t to be equal to the generating function for this this is equal to summation over j all lattice points j over z d p of j t times z 1 to the j 1 z d to the j that is this follow here it is the continuous time analog of this generating function here so instead of p of p n of j I got p of j, t so what I have to do is to multiply this by z 1 z 2 etc this factor and sum over all the j's components of j's and when I do that this becomes equal to summation n equal to 0 to infinity w of n, t and then here I have to multiply this by these factors and sum it but that factor we already know explicitly it is this guy g n so it is just g n because I multiply this by these things and sum over all the j's and that gives me this but this fellow is already known to me in terms of this characteristic function so finally I get this is equal to summation n equal to 0 to infinity w of n, t g of z to the power I still do not know anything about this I have not specified anything about it at all but I have a formal expression of this kind now w of n, t is the probability of the distribution of the random variable n which is the number of jumps in any given time interval t okay so we can define a generating function for that quantity. So let us define so w of n, t generating function h of xi and t this is equal to summation n equal to 0 to infinity w of n, t sum xi to the power n I do not want to put a z here z here because I use that for the space variables conjugate so this is the definition of the generating function of this probability distribution in n so once I do that it is clear what this is this is by definition now equal to h of g of z, t because it is just this to the power n. So in principle the problem is solved because if you give me this characteristic function or generating function little g which depends on the lattice structure what are the nearest neighbors etc and you give me the statistics of this number of jumps in time t I compute a generating function and there it is and I write that in that expression that gives me the generating function for p of j, t which is what I want to find. So once you have this L which is this crazy power series in multiple variables formally formally we can write what its inversion is so p of j, t is equal to the coefficient of z 1 to the j 1 z 2 to the j 2 etc till z d to the power j d right. In the moment you have an expansion of this kind it is a Laurent expansion because there are positive and negative powers of each z this can be written now as a product from i equal to 1 to d 1 over 2 pi i an integral around the origin d z i over z i to the j i plus 1 times this guy here h of v of z product acting on that so just inverting this Laurent transform this Laurent series to find the coefficients. This is around a small circle around the origin in the z i plane and you got to do this for each of the z i is in principle you got the answer or you have to differentiate it a sufficient number of times is some suitable derivative of this quantity or of this quantity with respect to each of the z i's will give at z i equal to 0 will give me the coefficients right but the difficulty with that is that you got negative powers of z so therefore that is not a trick which is easily doable this is a much more reasonable formulas so that is it this solves the problem but now let us see whether we can do something more in this matter in particular I want to say something about w of n comma t and I want to say that it is a renewal process w of n t given by a renewal process that is what a continuous time random walk is in other words there is a certain function a waiting time density which tells you the density that in time for the random interval between two jumps so the idea is that if you give me time 0 and t the first jump may occur here the second may occur here t n t n minus 1 and so on this interval between jumps successive jumps is given by a specifying a waiting time density which is the same for all the intervals okay so we introduce a waiting time or holding time density waiting time density let us call it psi of t so it says if you start at t equal to 0 then the probability that you have a jump between t and t plus dt is psi of t dt and it is obvious that psi of t must decrease as a function of time clearly you wait long enough there is going to be a jump it is a density so psi of t must be non-negative it is integral from 0 to infinity must be 1 it is a normalized probability density function so these are the properties we require of it the Markov case is given by an exponential waiting time density as I mentioned and it is not hard to see then the w of n comma t will be a Poisson distribution with intensity lambda okay but we will do it more generally than that does not have to be exponential just has to satisfy these conditions at all what happens then because the waiting time density is the same for all of these guys that is why it is called a renewal process with a common waiting time density I could generalize this a little bit by saying this jump has a waiting time density different from the second different from the third etc. But in the simplest instance that is not what we look at we look at just the simplest case where you got a common waiting time density okay not necessarily exponential okay then it is clear that in this geometry here t 1 is less than t 2 is less than etc etc it is clear that this t 1 appears anywhere between 0 and t 2 t 2 appears anywhere between t 1 and t 3 and so on and it is in the form of a convolution because these intervals the size are the arguments for the size right. So it is immediately clear that if you take a Laplace transforms and you write w tilde of n comma s being the transform variable it is a convolution after all this guy here has a psi of t 1 this fellow here has a psi of t 2 minus t 1 because that is the time you waited for and so on till out here you have a psi of t n minus t n minus 1 and it is a convolution of all these fellows because each ti is bounded by the next ti plus 1 in the upper limit right. So the n of these guys so it is immediately clear that this is psi tilde of s to the power n but we got to be a little careful that is not w tilde of n comma s because you can ask what happens if n is 0 then you need the probability that in the time interval t no events have occurred at all nothing has happened at all and what would that probability be because if I just took this to be the case w tilde of 0 comma s is 1 and the inverse Laplace transform of 1 is a delta function that is not what is happening at all right. So what is the correct situation what is the correct w tilde of w of 0 t what is this equal to nothing should happen in this interval right if a jump occurs it occurs with density psi of t. So this must be equal to 1 minus integral 0 to t dt prime psi of t prime that is the total probability that a jump occurs in time t and 1 minus that is the probability that no jump occurs what is the Laplace transform of this guy what is the Laplace transform of 1 1 over s yeah 1 over s minus the transform of this guy is the convolution of 1 times i of t. So it is 1 of 1 over s times psi tilde of s right the Laplace transform of this integral is psi tilde of s over s when you differentiate you multiply by s when you integrate you divide by s. So this in fact is the correct answer so this is 1 minus psi tilde of s over s and check this check this against the case we already know against the Markovian case Markov psi of t equal to lambda e to the minus lambda t lambda some positive constant right this is guaranteed to give you immediately trivial to check that w of n comma t is going to be the correct answer which is a Poisson distribution and what is w of 0 comma t when you have such a Poisson distribution w of n comma t is lambda t to the n over n factorial e to the minus lambda t. So what is w of 0 comma t e to the minus lambda t you should have it should come out because this will imply that psi tilde of s lambda over s plus lambda 1 minus psi tilde of s over s is this fellow here it is 1 over s plus lambda. So that tells you that w of 0 t equal to e to the minus lambda t so that checks that checks so indeed that is the correct answer for w tilde of 0 comma s otherwise you end up with this inconsistency that you have a delta function it jumps immediately which is not true w of 0 comma t has a delta function at t and then it is 0 thereafter it is not true okay. So what is the correct expression now for this w tilde of n comma s we took into account a jump here a jump here a jump here a jump here with this convolution but we must be careful we want w of n comma t is the probability density probability that exactly n jumps have occurred in time interval t.  So the correct expression is this times 1 minus psi tilde of s over s that is the correct expression for w tilde of course you put n equal to 0 you end up with this correct. So we are all set we have an expression for w tilde and therefore we know what h is let us put that in see what happens. So we have h of psi t equal to summation n equal to 0 to infinity w of n t psi to the power n but this is one my so therefore h tilde of psi s equal to summation n equal to 0 to infinity w tilde which of course is very conveniently 1 minus psi tilde of s over s times psi times psi tilde of s to the power n which is a geometric series. So that is trivially summed and this gives you 1 minus psi tilde of s divided by s times 1 minus psi times psi tilde of s and therefore finally we have our l of v comma s the plus transform this is the generating function for p of j comma t now I take it so plus transform instead that is equal to 1 minus psi tilde of s divided by s times 1 minus not psi but g of z psi tilde of s and that is the Laplace transform with respect to time of the generating function of my probability distribution p of j comma t okay quote unquote all I have to do is to invert this transform and to invert the power series itself I mean the Laurent series itself but in principle that is a solution that actually finishes it completely explicitly what we need to know now do is to ask how do we extract information from this in principle we can solve this once again but let us first check the Markovian case quickly and see whether this works or not so again Markov case psi tilde of s equal to lambda over s plus lambda so what does this give you for l this is equal to 1 minus this guy is s over s plus lambda and the s cancels out so it is 1 over s plus lambda 1 over 1 minus g of z psi tilde of s so there is a lambda sitting there over s plus lambda so let us take this and write it as s plus lambda minus this guy and this s plus lambda goes away right and I take out this lambda and I get 1 minus g of z and of course we can invert this transform in time 1 over s plus anything s plus a constant independent of s is e to the minus that constant times t right so that immediately tells us so it says l tilde l of z t equal to e to the minus lambda t e to the lambda g of z lambda t that is it of course if you look at the case we are looking at this is e to the minus lambda t on this hyper cubic lattice e to the lambda t summation i equal to 1 to d alpha i g i plus beta i g i inverse and what is the usual trick well take out alpha i beta i so write this as alpha i beta i times alpha i over beta i square root z i plus square root beta i over alpha i 1 over z and that is the generating function for pardon me for which one yes so what is the function that you get this is generating function for the modified Bessel function we know that of course right so recall exactly the skellum distribution so recall that e to the power xi over 2 z plus 1 over z equal to summation j equal to minus infinity to infinity i j of xi z to the power j and that is the modified Bessel function on the with the integer order and i minus j is identically equal to i plus j so this is a product this is equal to e to the minus lambda t product i equal to 1 to d should not forget this factor so alpha i over beta i to the j i over 2 that is sitting there and then i j sub i of twice root alpha i beta i so it is a product of these Bessel functions that is the solution to the bias random walk in a hyper cubic lattice the Markovian case so this general answer this guy here reproduces that immediately but you do not always have such a simple function to invert unless this is 1 over s plus lambda or something simple this is not such a trivial matter to invert this always in general the solution could be much more complicated in particular we are interested in the asymptotic behavior of both the mean displacement and the mean square displacement of the variance now we know by symmetry that if you do not have a bias in the problem if each alpha i equal to beta i equal to 1 over 2d then there is no bias at all and the mean displacement should go to 0 let us see if that emerges let us see if that emerges from this general case even without inverting the transform you see what I want is j any one of the j so j i as a function of t this is equal to a summation over all the j is p of j t times j sub i any particular j right so the transform of this guy j i of s transform in t is with a p tilde here so over j p tilde j sub i I need to pull down a j i how do I do that from the generating function we already have a generating function because this fellow here if you recall this guy equal to summation over j element of d dimensional lattice p of j comma s p tilde and then z 1 to the j 1 z d to the j d I want to pull this down pull the one power of j i down what should I do differentiate with respect to that particular z and then set all the z is equal to 1 so this is equal to delta l over delta z i at all the z equal to 1 so this is 1111 all z all z components are equal to 1 now when I differentiate that what is going to happen recall that we had a formula for this fellow here this was you have to remind me of the what this formula was 1 minus psi tilde of s in general divided by s times 1 minus now I am not very sure what really happened there was a g of z and then psi tilde of s and we have to differentiate this and then set z equal to 1 all the z components equal to 1 you differentiate this guy remember that so if you differentiate this fellow here delta l over delta z i l tilde is going to have all these factors as before but it is going to have a g prime of z on top with respect to that particular z and this g so I would not belabor the point very much because if you put g all the z equal to 1 what do you get here you get summation alpha i plus beta i which is equal to 1 so it is very clear that g of 1 equal to 1 so after you differentiate you are going to put g equal to 1 so you are going to get 1 minus psi tilde divided by this fellow squared you put g equal to z equal to 1 it cancels one factor between top and bottom but you are going to have this factor here and remember the corresponding g i dependence was in the form alpha z i plus beta over z i plus other stuff but when I differentiate this I get alpha z i minus beta over z i squared and I put all z i is equal to 1 so it is immediately clear that this fellow is going to be proportional to alpha i minus beta i that is going to come out as a factor indeed it should because if there is no bias in that direction that particular coordinates average value must be 0 so this is where it is coming from moreover if it is a Markovian walk we know it must be linear and that emerges also because what is psi tilde of 0 equal to that is the integral of psi of t from 0 to infinity so it must be 1 right so this must be 1 but now I ask what is psi tilde so you got to be careful when you put s equal to 0 this vanishes here so you have to ask what is the small s behavior of psi tilde of s now it is clear that in the Markov case if psi tilde of s equal to lambda over s plus lambda this is equal to a pull out a lambda and equal to 1 plus s over lambda inverse this is equal to 1 minus s over lambda plus order s squared near s equal to 0 so you have to be careful because we have got factors like 1 minus psi tilde of s so we better be careful so now look at what happens if you differentiate this guy gives me alpha minus beta multiplied by a psi tilde but that is equal to 1 if I put s equal to 0 this gives me a 1 over 1 minus psi tilde between this and the square of this so that gives me a factor s this gives me an s so the whole thing for small s is going like 1 over s squared what is the inverse Laplace transform of 1 over s squared it is a ramp function it is t because we know that the t to the power alpha the transform is 1 over s to the alpha plus 1 so if you have large t behavior like that you have small s behavior like this that is a useful thing to remember so you got a 1 over s squared so the whole thing it will tell you that ji of t average for t turning to infinity will go like this in general as long as psi tilde of s has an expansion 1 plus order s as long as that this factor is not relevant I mean the fact that in this case it happens with this is not relevant so if psi tilde of s is analytic at s equal to 0 the leading term must be 1 at s equal to 1 0 by conservation of probability the next term if it is analytic must be of order s there is a Taylor series which exists then you immediately get this result now look at what happens to diffusive behavior in the case of diffusive behavior let us let us we must look at the variance but let us be simple and look at just the mean square displacement let us put the bias factor equal to 0 so all alpha is equal to beta i's and so on and then this g of z just becomes z i plus 1 over z i sum over 1 over 2 d outside common factor so let us look at the unbiased case and see how diffusion comes out so we want ji squared of t so ji squared of s has a square here you still have this but now you want twice ji you want to differentiate right what should you do if you differentiate once you are going to get a ji if you differentiate a second time you are going to get a ji times ji minus 1 so a second derivative is really d 2 l tilde over d z i 2 is going to give you this moment ji times ji minus 1 but that is ji squared average minus ji average but if there is no bias ji average is 0 what does that imply that says g prime remember this no bias implies g prime of z equal to 1 equal to 0 because each time you differentiate this fellow you get alpha minus beta over z squared but if alpha equal to beta this is 1 minus 1 over z squared you put z equal to 1 it goes to 0 right what I am saying is g of z is 1 over 2 d alpha 1 plus z 1 plus beta 1 over z 1 plus dot dot dot if I differentiate this guy in the unbiased case it is just this if I differentiate this g prime of z i equal to 1 over 2 d if I differentiate with respect to one of the z it is z i minus 1 over z i squared this is delta d z over delta z i so g prime if I put z equal to 1 vanishes in that stage therefore it is sufficient to take the second derivative of this guy and that will tell me what the behavior of this is at long times immediately so let us go back quickly do that I have l tilde of z s equal to 1 minus psi tilde of s over s times 1 minus g of z psi tilde of s I have to differentiate this twice I differentiate it once I am going to get a g prime on top this fellow squared and then I am going to get psi tilde times g prime I use prime for the partial derivative with respect to one of the z i's for the moment I differentiate second time I differentiate this guy and I am going to get another g prime factor on top but g prime is equal to 0 at z equal to 1 so that does not contribute and in the second derivative it is only the second derivative of this that contributes but what is the second derivative of this it is just 2 over z i cubed and I put z i equal to 1 so it is just some number 2 some finite number so this guy goes the second derivative of this fellow at z equal to 1 1 this goes to 1 minus psi tilde psi tilde over times a number here times s into 1 minus psi tilde the square this goes away that is it times a number into some number times that there is no s dependence what this is now what this is equal to J i squared what does it do for small s that will tell me what this guy does at the inverse transform does at long t what does it do at small what does this fellow do at s equal to 0 this is 1 so this is harmless and you just have this so all we got to do is to look at the small s behavior of this guy here if psi tilde of s equal to 1 plus order s analytic then this gives you an s here you get an s squared and the inverse Laplace transform of s squared is t diffuser behavior you have normal diffusion everything therefore depends on the small s behavior of this or the large t behavior of the waiting time density if it is exponential or anything which has got a Laplace transform which is analytic at s equal to 0 the first term is order s other than 1 then immediately you have diffusive behavior in general but suppose it turns out that if psi tilde of s equal to 1 plus s to the beta order s to the beta less than 1 not analytic like square root of s for example what is going to happen is that this whole thing is going to go like 1 over s to the 1 plus beta because there is 1 cancels and you have s to the 1 plus beta and what will it imply for the mean square displacement which is sub diffuser this is the famous anomalous diffusion it is entirely therefore dependent on the long tail behavior of psi of t because what does it mean if for instance psi of t went like 1 over t to the 3 halves what would it mean for the Laplace transform you have take the Laplace transform of t to the alpha where alpha is minus 3 halves so that is 1 over minus 3 halves plus 1 which is s to the half on top so this will immediately tell you that this fellow here would not be true you get s to the half that will immediately lead to sub diffusive behavior which says the mean square displacement will go like the square root of the time rather than the time itself so the root mean square behavior will go like t to the 1 fourth in that case it is slower than normal sub diffuser and as a huge literature on anomalous diffusion the practical implications of anomalous diffusion etc will we will say a little more about this but this is one mechanism by which you can see a huge variety of behavior will emerge and it is essentially exact you solve the problem on an arbitrary lattice and we have seen that everything depends finally on this waiting time density what it is long tail behavior if it has a long tail then you have anomalous diffusion okay if on the other hand it cuts off exponentially then it is Laplace transform is analytic at s equal to 0 and then you do not have any problem you have normal diffusion the process is still non mark of as soon as you do not have an exponential waiting time density but it could lead to all kinds of anomalous diffusion if this has a long term t so we have done this without actually writing down a master equation for p of j, t which we cannot in the normal in most non Markov in cases so we did this by this trick of writing down generating functions and then looking at the statistics of the time the step distribution separately from that the geometrical problem of finding out where you are on this lattice and so on we can go ahead with this and find first passage time distributions recurrence properties and so on and so forth the matters of detail but I thought this will give you some idea of how anomalous diffusion arises how this non analytic behavior arises we stop here today.


Hi, so can we start? I'm Julian. I've come to talk about memcheck versus optimizing compilers I'm kind of the de facto maintainer of memcheck, so I spend a lot of time dealing with Problems caused by optimizing compilers Which seems to have got worse over the years Or better optimizing but more problematic So this is a something of a a bit mathematical talk I'll show a bit about how memcheck tracks valid tracks definateness of stuff, and then I'll talk a bit about some problems Come in come in come in So basically memcheck With which you may have used it basically does two things it it determines whether you're reading and writing in the wrong place So checks the location of all memory accesses, and that's relatively simple because There's not much ambiguity about whether this place is okay place to read or write or not You know where the bounds of the heat blocks are But the other thing that it does is to check whether branches and some other program constructions basically addresses depend on undefined data and That that's Considerably more difficult because you have to follow undefined in this through the whole program to do this That's really the whole process Shall I pause please welcome Yeah, it's kind of crazy Can I can I continue I continue So So for a tool like memcheck we put a lot of effort into Making sure that the false positive rate is very low and in particular the false positive rate for undefined value errors I think it's sort of somewhat known for that so when it comes long it says this is You know undefined value use here. It's likely to be correct. This is important because Lots of false positives make tools less useful for developers So back in the good old days of 2005 that was all fine. We had most stuff under control You know the occasionally you got false positives, but they we could get rid of them and 10 years later We have clang 3 and GCC 5 and their successes generating all sorts of problems Some of which are not easy to get rid of So What I want to show you is some basics about defining this tracking. I'm sorry if it's a bit mathematical Some problems where we have some solutions and some problems where actually I have no idea what to do and it's actually I think it's quite serious So here's some math so you can throw things at me if it's too boring Now here's some basics. Sorry. So what memcheck does to cut out all the Intermediate stuff is for every literally every bit of the state in your process That's all the memory and all the registers it has a second bit a shadow bit which follows it around everywhere and Tells you whether that be that bit is defined or undefined and We use the I could use this we use this We use one to encode undefined and zero to encode defined which sounds a bit Perhaps not what you'd expect, but it makes the co-generation more efficient so when When we come to actually calculate the value from off around like r equals x plus y I mean when the program does that then memcheck has these You know the shadow values of the same size which I write as x hash and y hash So literally if x is 16 bits then x hash is also going to be a 16-bit thing Concerning shadow bits and then we want to compute somehow the defineness of the result our hash and So by doing this it follows tries to follow defineness through all the arithmetic in the program and when it gets to a like an if or the use of a Value in a for in a memory address or for a couple of other obscure things It actually checks whether the value is defined and it generates an error at that point if it's not So we write wrote this all down quite nicely in this paper, which you can look at if you like this kind of stuff So here is some some basic building blocks Which I'll talk about a bit Sorry, it's all bit Matthew so we are most important building block is you if you which it means undefined if either argument is undefined So this takes two How can you say vectors of Defined in this bits is an example and produces another vector so this I'm writing a four-bit vector d d d u meaning three bits saying defined in the fourth one undefined and You know we combine it with this one here d d u d so we get two bits which are defined and then two bits which are undefined and because Defined is zero and undefined is one that means you can just implement it using a standard or operation So then there's a dual operation D. If D means defined if defined if either argument is defined Which we'll use much more rarely Here's another one called left I called it left which finds the right most undefined bit in the word and then propagates it left Was like that so it finds this bit here, and then you get all of the bits above it are undefined So we'll we'll see how that gets used Bizarrely you can implement that by negation and oring There's a lot of bit twiddling tricks and the last Building block is this thing called a pessimistic cast which takes some vector of defining this bits and produces a vector of defining them Defining the spits of some different size and The idea is that if all of the input bits are Defined then there is all of the output bits are undefined But if any of the input bits are undefined Then the whole output is undefined So that's why it's sort of pessimistic because anything bad that comes in produces to complete badness at the result So the most important case is when we want to take a bunch of bits and Check if any of them is undefined so that we will just be P casting down to a single bit there And there's even more weird bit twiddling should which implements this So a mem check spends half its time well a large amount of this time running all these sort of weird Low-level arithmetic operations. That's what you're actually waiting for So let's see some simple case So let's instrument or instrument addition so We're going to take some simple operation in the original program some you know R is X plus Y I mean integer addition here as well and The simpler thing we could say is if if we find a bit in either input operand which is undefined and the resulting Output bit is also going to be undefined so we can use you if you on the Define in this input to produce the output but that's actually kind of too simplistic right because When you add things and you get this carry which can go arbitrarily far up the word towards the most significant bit so we need to actually do something about carry propagation and So the simple thing is to assume the worst case that the carry is going to come all the way along the word Upwards and this is my most significant bits here They fit here for you so We're going to assume in particular that well you're going to get a propagation all the way along so we're going to pull in our left Building block that we just saw there. So we first merge the two arguments getting in a single word and then we propagate badness left And that's actually really cheap to co-generate is couple of moves a couple of oars and the negation And that works like pretty well But it's excessively conservative because this You know defined zero is actually stopped the propagation and unfortunately LLVM has come to a know this fact and So what LLVM does is sometimes when it wants to set a bit in a word it doesn't do it by oring it does it by addition and This cause causes You know false errors because LLVM knows that I'm not exactly sure of the details But that knows that there's some strategically places zero bits in one of the arguments which will stop the carries propagating upwards Even in the presence of undefined values So that's a bummer and we need to do something more expensive sometimes. So it's like mmm. Thanks LLVM Yeah, so I enjoy the improved performance of the code, but I don't like to have having to deal with these problems So let me move on to instrumenting something which is actually even simpler sounding which is and and or So here we go again say same kind of deal Program does bitwise and of two operands and so we're going to say well Obviously, you know the result is undefined if I the input bit is undefined for all input bits So we're going to use you if you again But the problem is that this is actually excessively simplistic and Obviously if you take any bit which is undefined and and it with a defined zero bit then the result is zero so I Say it matters because what compilers endlessly do things like Pull a big piece of like 32 bits out of memory Even though some of them are undefined and then use and to mask out the undefined bits and we need You know and with a mask and we need to be able to track that exactly so At this point. I don't want to get too much into the mass, but what I want to show is that We're going to take our initial naive simplistic term and Then we're going to improve it by using defined if defined and we're going to generate two sort of improvement terms from the operands Which tell you where you have defined zeros in the input So one one thing that you can take from this is that to instrument and and operation You need to know not only the Definedness of the inputs, but you also need to know the actual input values now, so you have four inputs and It's turns beginning to turn into a big complicated piece of code You know you have a bunch of ants and oars and knots and stuff So it's kind of suboptimal, but you you have to do it Same deal for all, you know when you turn everything upside down swap the ones and zeros But the good news is that this is an exact interpretation It gives you exactly the right results and that's a fact which we will come back to shortly So I want to show you one more Example which has actually become a big problem recently Which sounds so harmless And it's in instrumenting integer equality on not not equality so the program is going to compute a single bit result by comparing two Integers like whatever size Sounds harmless, right? so We're gonna use P cast Ufu again to merge them sort of in parallel then we're going to use P cast to Merge all the bits down to a single bit So the result of this is that we say the result is going to be undefined if any input bit is undefined and It's like okay sounds reasonable and Actually, this worked pretty well for about 10 years until about 2015 But actually it don't work no more Because clang 3 came along and then I think a GCC picks up its bad habits from clang so That's my theory anyway So what clang will do nowadays Imagine that we have this structure Which contains two 16-bit ints and we want to compare, you know, both of them and then do something so What clang will do and probably what GCC will do now as well It's just generate a 32-bit load for both fields of the structure and then and then compare You know it is a single thing so if In the original source code if this num if this is not true Then it never looks at that because of the C semantics, but here it's going to look at it anyway so We wind up doing a comparison on partially uninitialized data. I'm thinking I want to kill myself. No, no, it's not that bad So what can we do about this? So you observe that the program actually still works right when the compiler Compiles it like this so it must actually be correct The question is to make the instrumentation actually match reality now So what is the the key observation? The key observation is that if you you need to find two different two corresponding bits in the input here I write x zero and one and if they are Different and they're both defined then we know that the two that the whole two words here are Not the same right So we don't we know that these two words are not the same regardless of the fact that we don't know All these x's are because the one and zero make it so In this case the two zeros don't help us because we still need to look at the x's to determine whether they're different yeah undefined You're right, it's a bug. Yes. Yes result is defined Well, I checked it so carefully this morning too. Well, thank you So yes, we can fix up the scheme like we did before So we're going to take our our naive version which is you if you again But this time we're going to generate some improving term which kind of improves the result makes it more defined Exactly by looking for bit pairs Like this which they're different but the same So it gets calm I'm not expecting you to understand this but the point is it gets complex It gets complicated fast and it gets expensive fast so You know we have an improver term and then we have this weird function which actually Does a kind of optimistic cast it's a the parallel to the the pessimistic cast talked about earlier You can look at the gory details in the code base if you really want to Want to see this stuff But the real point about it is that this is expensive to do It's like going to be ten instructions now in the in the code in in the generated code instead of three or four It's actually difficult to prove right so I had my prop here somewhere So I have this whole bundle of bits of paper, which is my proof attempts to prove This is several pages not just one attempts to prove that this transformation actually is correct and It's generally I'm good also this function Ocast Which is a kind of a shortcut way of saying if any input is defined and the whole result is defined I had a less efficient version before and this weird version is generated by the GNU super optimizer So that actually improve the form performance a lot, but it makes it even more obscure So the question is well, that's kind of rubbish. Can we do anything better? so We can kind of do it something better so we cannot necessarily do it faster, but at least there's at least that's a way to to prove whether the these interpretations are correct or not and What you can see from sort of basic Boolean algebra is that you can write any function any combinatorial logic function, you know, this is like billion algebra 101 using just and or and not on individual bits, right? Or also XOR because it's kind of convenient here so we can we can take some subset of these three and Like I said in my previous slide for and and or we have an exact interpretation exact instrumentation and the same is true for not an XOR so That means that if we first take any operation we want to instrument write it in terms of single bits and then Apply our instrumentation scheme to that then we will have something which is actually correct Even if it's not optimal and then what you need to do is prove that that's the same as what you're generating code with So my My prop here is my proof that for equality So No No So I wanted to say first. This is just what you do for a three-bit input three-bit equality So you expand it like this and then you expand it with these not an XORs and then you apply the Interpretation to this What you try and do or what I tried to do is prove that the Instrumentation of this is the same as what I actually implemented Which is no fun, but it's doable Well, I think ups and actually I don't know how exactly how it works But I think it probably has a simpler instrumentation scheme that just determines Observes when you're reading on initialized memory But I don't know if it actually tracks In this much detail, but I I would say I do not know how OBSAN works I actually was talking about M-SAN. So OBSAN is something a bit different as well Anyways Please thank you for volunteering It's like yes, you probably could if I knew about that stuff and I hadn't enough time to do it I mean, yes, it would be good But there's also a lot of other things like We have an expensive interpretation for ad and subtract which is exact and I would like to prove that that is correct And not only prove it's correct, but maybe find a faster way to do it because it's slow So anyway enough about bit twiddling I wanted to actually sort of show what the current status more or less is So in the in the current trunk, which will be in 3.14, which is not released. We have Exact interpretation of ad and subtract Which is actually driven by an analysis. So when of the block being instrumented So when it knows that we don't actually care about or whether In certain circumstances it can show that the cheap and expensive interpretations are going to produce the same result and So it uses a cheap when it When it whenever it can and we do an exact integer equality by default now So that actually would produce the performance loss of about three to four percent in mem check But it's like well, it's either that or just have all these Force positives occurring to everybody. He uses, you know clang optimized code and now gcc7 optimized code It's like no don't want to go there Because having a low force positive rate. I think it's really important Sort of for the record we have long since implemented and or and not and Shifts and some other stuff widening exactly because but all the basic bit twiddling stuff that gets done Most other stuff including floating point is just approximated on the basis that you know any input that's undefined produces the Causes whole output to be undefined and that's sort of good enough so Result is it's kind of works fairly well for gcc7 and clang 5. It also works for rust See compiled code because that's for me a priority because that's a priority for Mozilla and rust is a big deal in Mozilla now Some somewhat open questions I'm still dealing with three way in comparisons of the power instruction set the how they do comparisons is different Like I said, I'd like add and subtract the and equality and not equality to be faster And So maybe some clever person can figure out how to do this We could also be some somewhat clever about the instrumentation because you can kind of see optimize up Opportunities for optimization where you do all this exact tracking of bits But then at the end of the end of this chain of computation All you care about is are any of them undefined or not and it might be possible in that case to actually do the whole sequence more cheaply so that sort of Pertains this old game called abstract interpretation. Yeah For the You can have a cheaper Yeah Some kind of speculative thing maybe Maybe I don't know So I just wanted to end by showing two Questions one of which is not a big deal and the other which is a big deal So the one that's not a big deal is about exclusive or so exclusive or is kind of weird and it doesn't really fit in the framework properly because if you take any value and put it into both arguments of an exclusive or operation and you get zero as a result and It doesn't matter what those values were What actually matters is the identity of the values So if I have a value here, which I put in one side of my exclusive or I send the other values sort of all around the place You know behind the moon and back into the other side of the exclusive or then you get the same you get a defined value and So we do not have anything that tracks identity of The values I don't even know how to do it For some simple cases like X soaring to register, you know the same register together twice to produce zero Which is a standard idiom then it's fine But in some more complicated cases like bit field assignments from the visual studio compiler, then you get problems so Yes, we try and rewrite it on the fly, but it's sort of difficult and limited But that's not the big deal. So much more serious problem is that Clang 4 started Violating a basic assumption about memcheck so memcheck has always assumed that every conditional branch you make Has importance in the final result of the program, but that's not actually true anymore because what Both compilers will do is to in certain circumstances compile a and b in the in the C semantics as if it was B and a So this is a pretty hard to get your head around But if if it's always the case that A is false whenever B is undefined then you can switch these around and you still get the same result Because you're doing either if false and undefined which is false and here you're doing if undefined and false So it's either true and false or false and false, but the problem is this conditional branch is now on undefined data and I think that some fancy kind of inter procedural analysis that Clang does in this kind of situation if it analyzes the behavior of this this function we're calling Yeah, it will do that transformation so I Actually have no idea what to do about this and Like you know it produces false positives on optimized Clang code and optimized Rust code and to some extent optimized GCC code generated code You think well, you know, maybe this machine code analysis game Has its limitations and this is sort of the end of the road or maybe we need some new framework to do this But I do not know how to fix this Yeah, that's how I felt Is it a accident or is there a a reason why Switching the conditions around well, you mean does it have a does it have a performance benefit? You'd have to ask a GCC or Clang person that I cannot tell you that I Do not know the reason for it. I wish they wouldn't do it, but it They succeeded Maybe it's it's just a Transformation that doesn't really matter but make something simpler for the compiler, but if it doesn't really Maybe we can convince the compiler Yes, that would be nice The the I know almost nothing about this the only thing I know is that I have the impression This was something to do with some transformation which split basic blocks into pieces or something Yeah Why would it be difficult to solve it's not much different from your end-on-bits if you you know one is zero So you don't care about that here you will probably have a series of jumps So so we come to a jump a conditional problem Second one is defined zero and there's no change to state of the program I've no change to me anything between job those jumps. Yeah Well, so I was considering that and I thinking maybe I can fix it up, but then I kind of got lost in the details So maybe it's fixable. I Mean that will be it would be great if it was fixable Anyway, let me just say in conclusion. We saw some simple cases We saw some cases where we needed to have a better Precision we saw a bunch of complexity and expense in the implementation, which I don't like But I don't know how to really avoid it It would be nice to have some some mathematicians to grind away at these problems and produce shorter sequences for common stuff like addition and equality Because you know, I don't like the performance losses and thank you. Any questions Yeah, so some kind of speculative instrumentation, yeah, yeah, so that would be doable, but that You know, that's a whole framework, you know jit framework jit runtime framework decision To produce a piece of code which you can execute and say then oh, we don't like that. We're gonna do this one instead Yeah, I haven't considered well, I have thought about that, but you know, that's a lot of engineering Well, we really runs Valgrind on Valgrind before every release to find any badness. Yeah, but yeah, we do Regressions Well, not really. We're actually very careful to avoid on initialized values, but yeah, we do do this sometimes Mainly the problem is that sort of two levels of virtual machine you get that's the real tricky part Especially if you have like like the older stuff on the newer stuff, yeah Yeah Yeah, the real thing we find when we do these runs is stuff like But usually Pre-initializing everything anyway, I think our heap allocator internal heap allocator


Yeah, yeah, I think I'm going to go with it. Yeah, it's fairly minor. Man, that's awesome. Yeah, I think there's enough stuff and it shows it. Sure. Alright, it is four o'clock and we will call the April 28th architecture review board to order. Steve, if you could please run us through the rolls. Sounds good. Joe Clark. Present. Alderperson Savaglio. Jerry Jones. Here. Richard Lindy. Here. Pam Lanyon. Here. And Robert Heimerle and Charlie Wiggs said that they would not be making today's meeting. Alderperson Savaglio. Right, but we do have a quorum so we can get rolling. If everyone could please stand for the Pledge of Allegiance. I pledge allegiance to the flag of the United States of America and to the republic for which it stands, one nation under God, indivisible with liberty and justice for all. Thank you. And any of our board members have a potential conflict of interest with anything on the agenda today. Hearing nothing, it looks like we're all good. Move to item 2.1. Approval of the minutes from April 12th. Motion in a second. Any further discussion? Hearing none. All those in favor signify by saying aye. Aye. Opposed? Minutes are carried. Thank you very much. Items 3.1 and 3.2. We've got some housekeeping to take care of. Need to elect a chair and vice chair. Do we have any volunteers? I'd like to nominate Joe Clark as chairman. I thought you were going to vote yourself in there, Dick. So we've got a motion and a second on the chair. Any further discussion? Hearing none. All those in favor signify by saying aye. Aye. Opposed? All right. Thank you for your confidence, everyone. Vice chair, I would, we have a motion and a second. Well played, Dick. Any further discussion? If not, all those in favor signify by saying aye. Aye. Opposed? Congratulations, Jerry, and thank you very much. Thank you. All right. Now we can get down to business. Item 3.3 is the proposed exterior remodeling of 1234 Kentucky Avenue. I believe we've got the applicants on the phone. Good afternoon, everyone. Scott Myers here. Are there other folks who are part of the group? Yes, there are. Yeah. We have Gary Gertman and Sam Leroy with questions construction. All right. Thanks, guys. If you could give a brief introduction. We've got the images that were sent through. They're up on the screen here. I think we've all had a chance to look at them. But if you could just give us a quick rundown of what you're proposing. And then we'll, we'll have further discussion. Yep. With regards to the exterior, we'll let the pictures do much of the talking, but first of all, there is going to be an abatement of the siding as well as the removal of the window coverings. Window openings are going to stay mostly intact with the exception of the second floor. And then many of those windows are going to be moved over or replaced with windows just in the corners of the building. So we've got a mixture of a couple of different types of windows. So we're just going to go on the exterior of the building. We'll be replacing doors, meaning both the, the rollup doors, a garage style doors, as well as dock doors and the, the man doors. Gary, would you want to add on anything to that? I believe Sam correct me if I'm wrong, but I think we have samples for you to look at. So the orange panel is actually an ACM panel, a positive metal panel that has concealed fasteners. And there's two types of metal panel that will, they'll have a color steel color and the charcoal color will be a complimenting metal panel siding. Gary, could you walk us around the elevations of the building and just kind of describe a little bit of what's going on on each of those elevations? Sure. Sam probably could do a little bit of help here too, but I think the, the featured corner is the Southwest entrance points. The featured entrance with the canopies with feedback from, from the city. Good feedback. That's going to have the orange aluminum composite material accenting that area. And just trying to carry some consistency on every elevation, both in highlighting the corners, the orange panel and then consistently carrying around the, the charcoal band to break up by the building and floors with compliment gray color, the lighter color and the darker color. So then this is your south elevation you're looking at there with the main entrance Southwest and then the accenting corner to the Southeast. As you roll around to the East side, we'll show the dock doors that are currently there would access to the lower level storage. And again, then from your viewpoint for me, and I'm going to see the accent corners, the orange accent. And then again, I'm going to see the accent corners of the building, that's the north elevation. Again, to keep it in consistency of the dark gray lines wrapping around the building with the, with the lighter gray sighting. And again, it kind of repeats again on the, on the West elevation to keep it consistent around the perimeter of the building. And maybe you can mention the second floor and that there were no windows on that floor in terms of the uses that are available. Correct. So the, the second floor is planned to be storage units. The, the windows have been eliminated. So, you know, you can't visually see the, the storage units and then the accent band again, breaks up that floor, the floor right now. We do have windows on the second level that'll be obscured. So you can't see the storage units through the windows, but we want to maintain the kind of consistent look with the windows at the corners at the second level with, you will not be able to see the storage units through the glass. But again, just keeping the consistent look and then also just maintaining the existing openings on levels one and three, filling in those with new window openings. Great. Thank you very much. I guess first comment from my end is, it's fantastic to see something actually proposed to happen with this building. We've seen it come before several times and never get beyond discussion. Certainly an eyesore now and fantastic to see it being done so nicely. I think your general approach deals with the huge massing of the building really nicely. It's, it's simple but effective. My only concerns with it come from the proximity of the window edges to your orange trim bands. And that's maybe just a, a detailing or proportion issue. The areas where you have the windows right up flush to the edge. I don't know if it's possible to either eliminate a window to have three instead of the four grouping to leave a little more space there or just to give just a little more space to the orange so that it runs continuous. The one that you're indicating there was fine. The other one looked to be right up at the edge of the windows. Is there any elevation you would prefer to show it, Joe? So like the south elevation is a good example that at that feature corner, that south elevation, the orange band at the edge of that feature corner is right up at the edge of the jam of the windows or maybe just a little sliver beyond it. And that, that's just a little awkward to me. It's just not balanced nicely. A couple of thoughts had been either run the orange over to sort of the midpoint between the banks of windows or in that instance, if you did three windows instead of four, just to give yourselves a little more breathing room there. And then that same sort of philosophy carrying around the corners. Some of them, the windows are completely within the orange trim. Others, they're up to the edge. Just looking to get that a little more consistent would be good. I think that's a good feedback. I think that's a good feedback. I would like the idea of splitting between the windows to give it enough material around the windows and then maintaining the window with. So they're consistent rather than eliminating windows. So I think as we work through the construction documents, and we're going to be using all the recommended manufacturer trim transitions that I like the idea of maybe splitting between the windows where we transition the orange to the gray. I prefer that option as well. I think if we stick a different window size in there, I think that that's a good thing. That sounds like a good idea. Thanks, John. It seems to me that solution from where I'm sitting, I would be happy with staff approval on that when it comes back. But once again, I'm monopolizing the conversation. Thoughts from everyone else? Dick. Sorry. We need to get your mic. Yes. On the corner of the south, the Southwest corner of the building, there's two canopies, both independent. They don't touch at the corner. if it would be possible to continue them to create a continuous cover at the entrance to make it a little more welcoming as a shelter in there. Yeah I think that was just a design consideration but as far as uh connecting them connecting them at the corner wouldn't be an issue if that's uh desired. Thank you and did everyone hear Dick's comment? It sounds like everyone did even though the mic wasn't on. Great. Any other comments or concerns? Feedback from the board? Chad. So I know you guys can't see me I'm behind the podium but anyway I just want to state that we've worked diligently Steve and I with cautious and with Scott Meyer to come to a plan that we think works for everybody on this property. The planning commission denied a use back in 2017 that was all storage at this location. I think we've come to a compromise that works for both the city and for the developer and you know we've hear over and over every day complaints about this building particularly from the neighbors so we're happy to see a design that we think kind of fits at industrial look and deals with some of the issues and we're excited to see this project move forward. Thank you Chad. We are too. And thank you to everyone for the time and effort gone into this to make this an improvement to the neighborhood. I much appreciate it. I make a motion to approve subject to staff recommendations including the change in the setback for the windows as Joe mentioned and also the continuation of the awning all the way around as Dick recommended. We have a motion and a second from Pam. Further discussion is one item Steve you would include it in your notes was the outbuilding it's a pump house or something. Oh yeah thanks for mentioning that. That was one of the things that staff would be able to work with the applicant on. They are going to see if they need that. I believe Scott that was something you guys are going to think about raising if it's not needed otherwise if it was needed the applicant was going to work with staff with regards to making that outbuilding similar material and design and look as to the structure. Absolutely correct with the goal of eliminating it if at all possible and if not then coming back and making a mini version of the larger building out of it with the same ethos and materials and colors. If all the nominating members are okay with that we'll include that in the motion. If there is no further discussion Steve if you could read the roll for the vote. Joe Clark. Aye. Jerry Jones. Aye. Richard Lindy. Aye. Pam Langen. Looks like that passes congratulations and thank you guys very much. Thank you very much I appreciate it looking forward to get it started. What is your sketch on that one of you anticipating it actually starting to see construction? Getting out final numbers of farm cautious obviously from that point we're at least 90 days out from getting bank financing and then also raising the balance of our capital so if I had to guess I would say roughly 120 120 days. Okay great fantastic to hear it's actually moving forward thanks again. Thank you. Appreciate it. Any further items from the board? If not do we have a motion to adjourn?  Aye. Anyone opposed? We are adjourned and next meeting is looking like May 10th. Yeah and we will have a meeting. Great thanks everyone see you then. All right thanks everybody. Thank you.