QA tools for FOSS distributions
CC Attribution 2.0 Belgium:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Abate, Pietro
FOSS distributions are increasingly over pressure to deliver stable releases including the most up to date upstream software. Time-based release strategies has exacerbated this problem putting even more pressure on QA teams. The recently concluded Mancoosi project has developed a number of tools to automatically analyse large packages collections for a range of problems, from installability checks to speculative analysis of software repositories. In this talk I'll present four command line tools to identify and correct potential problems as soon as possible during the release cycle.
 Hello, everybody. My name is Pietro Abat. I'm talking here for the Mancuzzi project, that it's a project that I recently concluded about six months ago. It's a project about trying to manage the complexity of open source distributions, any particular component-based systems. There are other people working with me in this project, one is Ralph Trinan, then Yapp Bonder, Stefano Cacchiroli, Roberto Di Cosmo, Jean Bouillon, Yassine Goussard, and other people in Paris. So, why we come over here? The Mancuzzi project has been academically a really successful project, it's been very well rated by the European community and everybody clapped hands. We're very happy about our job that we're done over there. It's a bit of... But one main goal of this project was to reach on the developer community and to try to integrate our work in open source distributions and to try to make a difference. After all, this is a European project that's been founded with your money and it would be nice to actually benefit about the results of this project. So, the Mancuzzi project has finished about six months ago and we develop a bunch of tools that today I'm going to present. I'm not going to go in the specificity of every tool and every small algorithm and there is a lot of academic blah blah published on our website. Today what I'm going to present is just how you can use and how you can benefit from these tools. So, what we wanted to do was to basically work on four different aspects of the distributions. One, we wanted to detect those packages that were broken, not installable. This is already part of an old project that was the predecessor of the Mancuzzi project that is called the Edo's project and probably many people here know about the utility Edo's list check that it's in Debian, Mandreva, and Kaixa Magic and other distributions. Another something novel tool that we developed recently was a package to detect those packages that need manual interventions because their metadata is outdated and there is no other way of fixing this package than to change the metadata. So, this is basically a subset of the broken packages in the first category. Then we wanted to give a stab to try to detect those packages that are somehow important in the distributions just looking at the metadata. These packages are those packages that if changed, they're going to break or affect a large number of other packages. And just by looking at the dependency web, this is a bit difficult. So, we try to actually shed a bit of light on this problem and try to untangle this web. And the last point is we wanted to actually see and guess what happens in the future if we modify, if we upgrade a package to a newer version. So, this is a kind of going in a direction of predicting what is going to happen in the future when we upgrade just one component or a cluster of components. So, the first tool that I'm going to present is this check. This is a, this check is a bit of history because it's been developed for the Edo's project back in 2005. And the first version was a standalone tool written by Jean Bouillon. Then it's been integrated in the suite dose that it's an OCam library that it's meant to study dependencies for software distributions. And nowadays, just on component-based systems, not just focusing on software distribution, it's more general. Even though here we look at software distribution in particular. In 2006, we uploaded a head of step check in many distributions and has been integrated in many QA tools so far. And then in 2009, we started rewriting those suite end as part of this check. So, the feature of this check is just a tool to detect which packages cannot be installed. How we do it, we encode the entire distribution in a Satsolver. We use a bit of logic and we use a specific Satsolver that has been written for this purpose. That it's very fast and performant and allow us to answer this question in a matter of a few seconds. It accepts different input formats. So, as I was saying, it's not just for one distribution, but we can talk with Debian, RPM and nowadays, now we can also look at the Eclipse plug-in system that it's another component-based system. And other formalism that we're going to add in the future. So, it handles Compress Archive so we don't have to bother about Bzip or Gzip or anything else. It uses UDF. UDF is a generic format that tries to be one of these interchange formats for all the metadata in different distributions. What we do, we translate the different inputs in UDF and then we use UDF for the analysis. This allows us to be more modular and to add backends as they come. One goal of this check was to be easily scriptable. So, we choose a YAML as output format and that it's a nice format that can be interpreted by human and easily parsed by a machine. And, at least, it's twice as fast as a spread assessor and there is still a bit of room for improvement. This is very good as if you have 10 architectures and five releases and I don't know what you want to, not to spend half a day testing if your packages can be broken or not. So, the output of this check more or less looks like this. It's you have a list of packages where you have a report for every broken package and at the end they give you the number of background, the number, give you a few of the information. These are the total number of packages that you analyze. These are the number of broken packages, packages that are not installable. And these two are the foreground and the background packages. As you can specify, for example, use, I don't know, about 20,000 binary packages but analyze only 10 of them. And in this way, it's a nice way to select which package we want to focus on. If we go deeper, we, I'll give you two examples of how a package can be broken. So, in this case, a PTRPM repository is broken. We have different information and the reason why this package is broken is because there is a dependency that is not satisfied, basically, because this package is not in the archive at the moment. Another example that it's a bit more complicated, it's an example of a conflict. So, you say that the G4 web package cannot be installed because there is a conflict between these two packages. And on the other hand, we have the chain of dependencies because when you have a conflict between two packages, there are not, it might be not a conflict that is direct to the package that you're looking at, but it can be hidden deep in the dependency tree. And our tool kind of give you the how to reach that package and show you that there is a conflict between this package that you're trying to analyze and the Python 2.6 minimal that is deep in the dependency tree. So, as I said, it's easily scriptable and if you want to load the output of this check, you can extract very easily all the information with a few lines of Python. And if you're wondering, actually, it's useful. For example, this is the core of Ubuntu where one package is not installable because it depends on a package that is outside the core. And while the core is meant to be self-contained, it depends on FGL, RX, that it's a non-free component. You can get somewhere you can have nice results. So, a demo. So, I've prepared a few comments and I'm going to run a few of them we do just because they are nice and fast and few others. I'm not going to show you the result itself. Here, what I'm going to do is to run this check. I'm going to ask it to give me all the packages that are broken, to give me explanation, to tell me something, to show me the progress. And I'm going to tell to us to analyze what's in my machine at the moment. And if I cut and paste this and run it, it takes about five, six seconds to do it. At least, he did it this morning. So, what it does, I initialize the solver and then I start spitting out all the packages that are broken. And as you might notice today, there are a lot of broken packages. There are about 300 broken packages in the IBNAS table. If you don't ask to print everything on screen, maybe it's a bit faster. Okay. I love to demo automatic tools because they don't require too much effort from me. So, it's used in an embedding to check in the tool chain of embedding. It's internally used by the Mandriva QA team and the Katz Magica QA team. It's the engine of Debian weather that you might have heard of, that it's maintained by our team. And I recently discovered that it's used in simple CDD, that it's a small utility to create custom Debian installation in CDD and in file conflicts that it's another small tool written by us. So, another something else about problem detection, it's Debian build check. Now, when using this check, we're just basically looking only on the binary packages. But this problem can be extended also on the source packages. And we want to make sure that before actually trying to build a package, we're going to be able to build a package. Otherwise, we're going to maybe set up a virtual machine and download all the packages just to find out that there was one package missing and all this time was just wasted. So, what we do is we encode the build dependencies as normal dependencies and then we run the same tool on this encoding. This allows us to discover if a package can be installed or not. It runs a bit faster. This is an old application as well from the Edo's project. It runs a bit faster than Edo's build check. It's just a wrapper around Edo's disk check and has the same output of this check. That is, YAML, et cetera, et cetera. So, an example of this tool. It's very similar to what I've shown you before. Now, you see that certain packages have a small prefix that is serves semicolon and name of the package. And basically tells you that this is a source package. And what we have done is we try to see if all the build dependencies of these source packages actually, they are satisfied. And here we found that this package cannot be installed because in their build dependencies, it depends by two packages that actually are in conflict with each other. And this is one of the small problems that we can find compiling packages. So, second demo that as you might have guessed, it's not going to be too exciting either. It's about this one. So, here, oops, here I'm using the all the binary packages in the demo unstable and trying to recompile all the source packages in the demo unstable. Looking at only one architecture and I want to know the broken packages and have some kind of explanation from it. So, now, this one is a bit slower because before we are analyzing about 30,000 packages, 35,000 packages. Here we are jumping and we are analyzing about, I think, about 50,000 packages or something. I forgot progress and stuff. So, we analyze the source file and then we analyze the binary packages and then we may encode the build dependencies. So, here we analyze about 36,000 packages and a lot of broken packages up and down. Outdated packages. So, the first two were two applications that were already known. It's kind of easy to figure out what they are doing because they were just looking at the broken packages. Outdated packages look for a subset of the broken packages that require manual intervention. And I'm going a bit deeper here to explain what manual intervention means. So, a package is broken for basically two reasons. Either it's a transient problem. So, it depends on the package that is not available or it depends on a package that is not installable. But we also have non-transient problem. These are the problems where the package itself need to have this metadata fixed to be installable again because maybe it depends on the package that is never going to be in the distribution again because these packages become outdated and a new version of packages been already uploaded in this distribution. So, I have to change the metadata in order to fix this problem. So, I'm going to give you a couple of examples. So, for example, here we're focusing on the package foo. If you look at foo that depends on the package bar version two and we ask the question, is this going to be installable in the future? Well, the answer is clearly yes. We don't have to do anything on foo. We just need to upgrade the bar to version two and foo is going to be installable again. This often happens when we upgrade the new package. That depends, for example, on a package, well, I'm talking in Debian and in Debian Experimental and we need to wait for the new package to get in Debian unstable. So, there is a small delay and we don't have to do anything to foo. We just need to wait for bar to version two to appear. If we change a bit the situation now, bar depends on a version that is less than two. So, doesn't matter what bar is going to become in the future, for example, version three, version four, version five, foo is never going to be installable because I need something that is smaller than two. So, in this case, I need to change this metadata to make sure that foo is going to be installable again. So, if we go in a more complex example, so we look at foo and we have package bar and package bars. Now, the dependencies are a bit more complex and the question that we ask is always the same. Is foo going to be installable in the future? Surely it's not installable now because it depends on bar version 2.5 or bar version 2.3 and on bar and bars. But in the future, we can kind of think of a situation where the package foo is going to be installed without requiring any modification to the metadata foo itself because if we go to a future where baz is of version 2.5 and without any conflict because in the future, packages can evolve in any way. So, we can imagine that the package bar in version 2.5 dropped the conflict. We are taking an over approximation here. Packages sometimes they are a bit more conservative. And we get the version of bar of version in between 2.6 and 3, then this constraint here is going to be satisfied. So, this is another situation where even with a complex constraint, we can kind of figure out what's going to happen in the future. However, if we look at the situation like this, now the package foo requires my intervention because if we choose, now here we have two possibilities. Either we choose bars or we choose bars or we choose bars. If we choose bars of version 2.5, this is going to be, this is going to select this package that is going to be in conflict with bar 2.5 and this is going to be in conflict with this, with this constraint up here. If we choose bar 2.3, then this is not possible because if we choose bar 2.3, I have to choose something that is less than 2.3 here, but in the repository of version 2.5. So, these are all these kind of strange situations where we can bump into and we developed a tool to actually identify all these packages, mainly foo and try to flag the author of this package that this package needs, its dependencies to be modified in order to be installable again. So, now, got demo. So, here, oops, here again. I'm going to, I'm going to run this, this tool and this tool is going to take a bit longer. It basically used the same engine of this check, but this time, since I have to consider all possible features, all possible way of how these packages are going to evolve, I need to consider a much larger universe and in this case, it's going to be about 80,000 packages. I also try to make sure that I consider the source cluster, so I don't let packages to advance one by one, but in clusters because we don't want to end up in the situation where, for example, we have a version of GNOME 3 and a version of GNOME 2 in my distribution, I want either GNOME 2 or the cluster of GNOME 3 all together. This is going to take a bit of time. Okay. We're going to come back to that. So, now, I've been talking about these three tools that are meant to detect broken packages, to flag maintainers about broken packages and to try to release distributions that, where every package can be installed. Now we're going on something that it's more on the try to figure out how the distribution is going to evolve and what are the important packages and how packages can evolve and what they will break in the future if they evolve in a certain way. So, the first thing I want to do is about talking about this concept of strong dependencies. We already talked about it, I think, about two years ago. And this kind of came back a while ago, it was at Linux and at GNOME Australia and one of the release managers of Ubuntu gave a presentation that was exactly about this. So, I raise my hand and say we have all the solutions of your problems. And so, since this seems relevant to them, I wanted to come back to it and to try to explain what this is all about. So, the idea is to try to understand which packages are important for our distributions. The notion of important is related if I have a bug in a package, which other packages are going to be impacted by this bug. So, it's kind of try to understand how a bug spread in my distribution. Or if I upgrade one package, which other packages are going to be impacted by this upgrade. So, if I look only at the web of dependencies, this is a bit too course and it's a bit too complex for a human to analyze. What we wanted is we wanted to have a certain measure of the packages that are going to be affected by a change. So, we define the notion of strong dependencies and the notion of impact set. The impact set are those packages that are potentially affected by changes in a given package. So, it's kind of a measure of how sensitive is this package and how careful we need to be when touching this package. If, as I said, if we get the direct dependencies too little, if you get the transitive closure of all dependencies, it's too much. So, we want to, we need a stronger definition. The definition of strong dependency is actually very easy. We said that P is strong depending on Q if it's not possible to install P without installing Q. So, let's consider this small graph. Here we have packages that they have either a disjunctive dependency or they have a direct dependency. Or in this case, there is a conflict between easy and George. And here at the bottom, we have Charlie and Doug that both depend on Fox. So, what we want to do is to actually try to understand which are the important dependencies, which are the strong dependencies, and which are all the others. So, in this case, George is a, George is a conjunctive dependency. So, in order to install Able, I must install George because I really need it. But if I install George that is in conflict with easy, automatically, these dependencies can never be satisfied. And this implied that Baker must be installed all the time. And at the same time, since Able depends both on Charlie or on Doug, and both of them depend on Fox, Fox must be installed all the time. So, we end up in a situation where Able, in order to install Able, we always need Baker, George, and Fox. It doesn't matter what. So, this gives us a way of trying to find out which are the packages that are really, really important. And then we kind of end up with a kind of a table where we can have this list of packages that, where we show the impact set of the, for each package. When we compare the impact set to the direct dependencies, actually, we found out that the direct dependencies didn't tell us a lot of things. As we, in the first five, we have packages that maybe don't have that many direct dependencies, but they have a lot of packages that depends on them. And so, if we touch them that are really at the bottom of our web of dependencies, we're going to break a lot, a lot of packages because these dependencies are going to be propagated upward. And this gives us a nice notion to say, if I migrate DPKG to a newer version, probably I'm going to break about 13,000 packages. So, at least, these are very important packages. So, I'm going to upgrade this to a newer version. Maybe I need to check that all the packages are strong dependents, strong depend on them, they're going to be compatible with this migration, with this upgrade. Another, so, these are on the strong dependency side, we also have kind of a notion of, that I'm not going to present today, but the notion of domination. So, if you look at the dependency, the web dependency of a distribution, you can kind of think, what if I run one of the Google rank algorithm on this bank, on these dependencies. This is going to give us the packages where most of the other packages depend. And it's going to give you these kind of hubs everywhere. What we've done is we have used a similar notion of strong dependencies that we have run a flow graph algorithm, where we were able to find out the important packages, even if those were hidden under other packages. So, imagine there was, imagine if there is a very, very important package where everybody depends, but this one depends on another one. This means that actually there is one package hidden down there that is not detected by our previous analysis. This, this, this dominator algorithm allow us also to untangle this kind of hidden packages and try to find out a bit more about the structure. The last tool that I'm going to present, it's the challenge packages. Here, we're going to try to predict what is going to happen if, and since it's a prediction about the future, it's going to be an over approximation. So, I'm not going to go deep in how we did it as it's, I don't have enough time today, but what we wanted to do, it's, it's we wanted to have a bit more than what we had with the strong dependencies. With the strong dependencies, we had this notion of impact set and trying to understand what, which packages were important. Now we want to, to answer to this question, what if we upgrade the package P to a version of a version V to a future version and how many packages are going to be affected by this upgrade? And in particular, the, the main problem is which future version I'm going to, to consider because I can't consider all the future versions as it's, I mean, the future it's, it's, it's infinite. I have to, to try to find out specific versions that in relation with my, my repository today, today are going to be the most important tomorrow. So, as I said, I wanted to do this, but only by looking at the, at the current repository and I'm not going to use other kind of sources to predict how the packages are going to be upgraded. And I also want to be consistent with the clustering information. So packages, packages don't are not upgraded by, by themselves in, in isolation, but always upgraded in a, in a cluster, in a cluster. So all packages that stem from the same source package, they're going to be upgraded all together. And this, in the challenge at the moment, it's very debian specific because of this reason, because we did this clustering analysis on the Debian packages. I'm sure that it can be done also on the RPM packages. And the, the idea that in Debian packages of the same source probably have the same version. This is not, this is not a rule anywhere. But if they have the same versions, they are going to evolve all together. If they don't have the same versions, then all bets are off because we can't, we can actually predict how these packages can, can move all together. So what we find is that by analyzing source clusters, most of them, they move all together to a newer version. Some of them from a source package, you have different sub clusters, for example, with different epochs. Some of them from a source package, they, they have binary packages with versions that evolve in completely different directions. And in this case, we really can't say how different, how these packages and versions are going to evolve in isolation. So this, this challenge algorithm, it takes, it takes sometimes, it's not something that you want to do on your machine. It's something that distributions want to run once a day. It takes about, about 35 minutes, 40 minutes, a bit too much for an all demo, a demo here. But I kind of give you the idea of how packages are going to evolve. And this is particularly useful if you have a point-wise distribution. And you want to modify only specific, specific packages. Then once in a while, you want to run this algorithm. And kind of to, to see, I'm, I'm here in this, in this point in time with these packages. And I want to, to migrate this component of my distributions. What is going to happen when I do that? So as I said, we have source packages with versions. And then we have target versions. The target version is the, the, this idea. What is going to happen when I upgrade to a version that is bigger than? So in this case, the first four, so these are for, for Debian squeeze. And we see that in Debian squeeze, the, one of the most problematic, problematic. One package that, that emerged as problematic dependency-wise when upgraded. It means that the dependencies on this, on the, on the Perl package are very tight. It's this one. But it's this one for many different reasons. So if we upgrade from this version to a version that is in between 10.5, 0.2, and 10.12, I break 2060, 652 packages. If I upgrade to a version that is in between here, I break as many. But if I upgrade to a versions that is in between this one, then I break a bit less. This basically is telling me that the, the, the upgrade to specific version is going to break a number, a number of packages. But not, not all the, all the upgrades are, are the same. So Python is also, is also another one. I mean, there, there are many different, different examples. If you get a G-Lib C, if you migrate to something that it's larger than 2.12, I'm going to break about 400 packages. If I migrate something that is in between this version and 2.12, I'm going to break a bit less packages and so on and so forth. This will give us a way of kind of picking into the future and trying to understand what is going to happen if we migrate to a specific version. So when actually going to change a component of your distribution and you run this, this algorithm, you might be careful at where you're going to, to end up with your migration. So one last, one last tool that I'm going to, to present. Actually, I'm not going really to present as it's, it's a bit, it's a bit outside the scope of, of this presentation. It's the co-inst tools that has been developed recently by one member of our group. And it's, it's a tool to, to compute the installability kernel of distribution. What are the installability kernels? So if we, we want to, to understand about how packages can be co-installable together. In particular, we find out that in Debian, about 80% of the packages can be installed, installed together. If you want to find the, the, the largest installation with the Debian packages, you probably can install in Debian unstable about 30,000 packages all together. But there are a number of packages that they, they can't coexist together. And what this tool does is try to identify these classes of packages that can coexist, coexist together. So for example, think about the, the mail agents. You can't install send mail and postfix at the same time because the, the, the conflicts, the, the structure of conflicts doesn't allow you to do that. This is a, this is a simple example about two packages or actually it's a family of packages that come, cannot coexist together. But if you look carefully at the distribution, there are not that many family of these packages that cannot coexist together. And this, this tool just allow you to, to identify this, this class of packages and to have a simple graph to, to analyze what's how, how the, the structure of conflict actually works in your distribution. These are all kind of hidden structures that we are trying to, to let surface, to let, to, to allow people to, to look a bit, a bit at the general, at the general picture. So it's been written by Jean-Brouillon and if you're interested, there is a website with a lot of explanations and very nice graphs. So my presentation finished here that I think it's about 45 minutes and I'll be, I'll be very happy to take questions. Yeah, it's, we, the question was about how deep we go in, in the dependency graph. We consider the, the entire dependency graph. We're going to, we consider the entire, the entire distribution. Give me one package file that it's our universe and, and, and we consider all the packages. And with our tool, we, I think we analyze universe that are up to 100,000 packages. So I think we are in a good position to scale. The question was about how long does it take for 30,000, 30,000 packages. It's about five seconds, 80,000 packages, that's about two minutes. Yes. Do any of the tools that you developed have the capability of working with packages different than Debian's? Yeah, we work with, so this check accept Debian HD list synthesis file, CDF, that is this interchange format and Eclipse file. And once upon a time, we have a filter for BSD, but it's not being rewritten. All these tools are, so every year we, we promise a release. This year, actually, we are very, very close. We are so close that there is a release of the source code on our website. And we are so close that there are packages in Debian experimental. And we are so close that Ralph is working right now to, to finish up the Debian package that we should be up sometimes next week. So this is a way to put a bit of pressure on ourselves because we say we're going to release these tools and then we never do it. Okay. Thank you very much.
 Hello, everybody. My name is Pietro Abat. I'm talking here for the Mancuzzi project,  that it's a project that I recently concluded about six months ago. It's a project about  trying to manage the complexity of open source distributions, any particular component-based  systems. There are other people working with me in this project, one is Ralph Trinan, then  Yapp Bonder, Stefano Cacchiroli, Roberto Di Cosmo, Jean Bouillon, Yassine Goussard, and other people  in Paris. So, why we come over here? The Mancuzzi project has been academically a really successful  project, it's been very well rated by the European community and everybody clapped hands. We're very  happy about our job that we're done over there. It's a bit of... But one main goal of this project  was to reach on the developer community and to try to integrate our work in open source  distributions and to try to make a difference. After all, this is a European project that's  been founded with your money and it would be nice to actually benefit about the results  of this project. So, the Mancuzzi project has finished about six months ago and we develop  a bunch of tools that today I'm going to present. I'm not going to go in the specificity of  every tool and every small algorithm and there is a lot of academic blah blah published  on our website. Today what I'm going to present is just how you can use and how you can benefit  from these tools. So, what we wanted to do was to basically work on four different aspects  of the distributions. One, we wanted to detect those packages that were broken, not installable.  This is already part of an old project that was the predecessor of the Mancuzzi project  that is called the Edo's project and probably many people here know about the utility Edo's  list check that it's in Debian, Mandreva, and Kaixa Magic and other distributions. Another  something novel tool that we developed recently was a package to detect those packages that  need manual interventions because their metadata is outdated and there is no other way of fixing  this package than to change the metadata. So, this is basically a subset of the broken  packages in the first category. Then we wanted to give a stab to try to detect those packages  that are somehow important in the distributions just looking at the metadata. These packages  are those packages that if changed, they're going to break or affect a large number of  other packages. And just by looking at the dependency web, this is a bit difficult. So,  we try to actually shed a bit of light on this problem and try to untangle this web.  And the last point is we wanted to actually see and guess what happens in the future if  we modify, if we upgrade a package to a newer version. So, this is a kind of going in a  direction of predicting what is going to happen in the future when we upgrade just one component  or a cluster of components. So, the first tool that I'm going to present is this check.  This is a, this check is a bit of history because it's been developed for the Edo's  project back in 2005. And the first version was a standalone tool written by Jean Bouillon.  Then it's been integrated in the suite dose that it's an OCam library that it's meant  to study dependencies for software distributions. And nowadays, just on component-based systems,  not just focusing on software distribution, it's more general. Even though here we look  at software distribution in particular. In 2006, we uploaded a head of step check in  many distributions and has been integrated in many QA tools so far. And then in 2009,  we started rewriting those suite end as part of this check. So, the feature of this check  is just a tool to detect which packages cannot be installed. How we do it, we encode the  entire distribution in a Satsolver. We use a bit of logic and we use a specific Satsolver  that has been written for this purpose. That it's very fast and performant and allow us  to answer this question in a matter of a few seconds. It accepts different input formats.  So, as I was saying, it's not just for one distribution, but we can talk with Debian,  RPM and nowadays, now we can also look at the Eclipse plug-in system that it's another  component-based system. And other formalism that we're going to add in the future. So,  it handles Compress Archive so we don't have to bother about Bzip or Gzip or anything else.  It uses UDF. UDF is a generic format that tries to be one of these interchange formats  for all the metadata in different distributions. What we do, we translate the different inputs  in UDF and then we use UDF for the analysis. This allows us to be more modular and to add  backends as they come. One goal of this check was to be easily scriptable. So, we choose  a YAML as output format and that it's a nice format that can be interpreted by human and  easily parsed by a machine. And, at least, it's twice as fast as a spread assessor and  there is still a bit of room for improvement. This is very good as if you have 10 architectures  and five releases and I don't know what you want to, not to spend half a day testing if  your packages can be broken or not. So, the output of this check more or less looks like  this. It's you have a list of packages where you have a report for every broken package  and at the end they give you the number of background, the number, give you a few of  the information. These are the total number of packages that you analyze. These are the  number of broken packages, packages that are not installable. And these two are the foreground  and the background packages. As you can specify, for example, use, I don't know, about 20,000  binary packages but analyze only 10 of them. And in this way, it's a nice way to select  which package we want to focus on. If we go deeper, we, I'll give you two examples of  how a package can be broken. So, in this case, a PTRPM repository is broken. We have different  information and the reason why this package is broken is because there is a dependency  that is not satisfied, basically, because this package is not in the archive at the  moment. Another example that it's a bit more complicated, it's an example of a conflict.  So, you say that the G4 web package cannot be installed because there is a conflict between  these two packages. And on the other hand, we have the chain of dependencies because  when you have a conflict between two packages, there are not, it might be not a conflict  that is direct to the package that you're looking at, but it can be hidden deep in the  dependency tree. And our tool kind of give you the how to reach that package and show  you that there is a conflict between this package that you're trying to analyze and the  Python 2.6 minimal that is deep in the dependency tree. So, as I said, it's easily scriptable  and if you want to load the output of this check, you can extract very easily all the  information with a few lines of Python. And if you're wondering, actually, it's useful.  For example, this is the core of Ubuntu where one package is not installable because it  depends on a package that is outside the core. And while the core is meant to be self-contained,  it depends on FGL, RX, that it's a non-free component. You can get somewhere you can have  nice results. So, a demo. So, I've prepared a few comments and I'm going to run a few  of them we do just because they are nice and fast and few others. I'm not going to show  you the result itself. Here, what I'm going to do is to run this check. I'm going to ask  it to give me all the packages that are broken, to give me explanation, to tell me something,  to show me the progress. And I'm going to tell to us to analyze what's in my machine  at the moment. And if I cut and paste this and run it, it takes about five, six seconds  to do it. At least, he did it this morning. So, what it does, I initialize the solver  and then I start spitting out all the packages that are broken. And as you might notice today,  there are a lot of broken packages. There are about 300 broken packages in the IBNAS  table. If you don't ask to print everything on screen, maybe it's a bit faster. Okay.  I love to demo automatic tools because they don't require too much effort from me. So,  it's used in an embedding to check in the tool chain of embedding. It's internally used  by the Mandriva QA team and the Katz Magica QA team. It's the engine of Debian weather  that you might have heard of, that it's maintained by our team. And I recently discovered that  it's used in simple CDD, that it's a small utility to create custom Debian installation  in CDD and in file conflicts that it's another small tool written by us. So, another something  else about problem detection, it's Debian build check. Now, when using this check, we're  just basically looking only on the binary packages. But this problem can be extended  also on the source packages. And we want to make sure that before actually trying to build  a package, we're going to be able to build a package. Otherwise, we're going to maybe  set up a virtual machine and download all the packages just to find out that there was one  package missing and all this time was just wasted. So, what we do is we encode the build  dependencies as normal dependencies and then we run the same tool on this encoding. This  allows us to discover if a package can be installed or not. It runs a bit faster. This  is an old application as well from the Edo's project. It runs a bit faster than Edo's build  check. It's just a wrapper around Edo's disk check and has the same output of this check.  That is, YAML, et cetera, et cetera. So, an example of this tool. It's very similar to  what I've shown you before. Now, you see that certain packages have a small prefix that  is serves semicolon and name of the package. And basically tells you that this is a source  package. And what we have done is we try to see if all the build dependencies of these  source packages actually, they are satisfied. And here we found that this package cannot  be installed because in their build dependencies, it depends by two packages that actually are  in conflict with each other. And this is one of the small problems that we can find  compiling packages. So, second demo that as you might have guessed, it's not going to  be too exciting either. It's about this one. So, here, oops, here I'm using the all the  binary packages in the demo unstable and trying to recompile all the source packages in the  demo unstable. Looking at only one architecture and I want to know the broken packages and  have some kind of explanation from it. So, now, this one is a bit slower because before  we are analyzing about 30,000 packages, 35,000 packages. Here we are jumping and we are analyzing  about, I think, about 50,000 packages or something. I forgot progress and stuff. So, we analyze  the source file and then we analyze the binary packages and then we may encode the build  dependencies. So, here we analyze about 36,000 packages and a lot of broken packages up and  down. Outdated packages. So, the first two were two applications that were already known.  It's kind of easy to figure out what they are doing because they were just looking at  the broken packages. Outdated packages look for a subset of the broken packages that require  manual intervention. And I'm going a bit deeper here to explain what manual intervention  means. So, a package is broken for basically two reasons. Either it's a transient problem.  So, it depends on the package that is not available or it depends on a package that  is not installable. But we also have non-transient problem. These are the problems where the  package itself need to have this metadata fixed to be installable again because maybe  it depends on the package that is never going to be in the distribution again because these  packages become outdated and a new version of packages been already uploaded in this  distribution. So, I have to change the metadata in order to fix this problem. So, I'm going  to give you a couple of examples. So, for example, here we're focusing on the package  foo. If you look at foo that depends on the package bar version two and we ask the question,  is this going to be installable in the future? Well, the answer is clearly yes. We don't  have to do anything on foo. We just need to upgrade the bar to version two and foo is  going to be installable again. This often happens when we upgrade the new package. That  depends, for example, on a package, well, I'm talking in Debian and in Debian Experimental  and we need to wait for the new package to get in Debian unstable. So, there is a small  delay and we don't have to do anything to foo. We just need to wait for bar to version  two to appear. If we change a bit the situation now, bar depends on a version that is less  than two. So, doesn't matter what bar is going to become in the future, for example, version  three, version four, version five, foo is never going to be installable because I need  something that is smaller than two. So, in this case, I need to change this metadata  to make sure that foo is going to be installable again. So, if we go in a more complex example,  so we look at foo and we have package bar and package bars. Now, the dependencies are  a bit more complex and the question that we ask is always the same. Is foo going to be  installable in the future? Surely it's not installable now because it depends on bar  version 2.5 or bar version 2.3 and on bar and bars. But in the future, we can kind of think  of a situation where the package foo is going to be installed without requiring any modification  to the metadata foo itself because if we go to a future where baz is of version 2.5 and  without any conflict because in the future, packages can evolve in any way. So, we can  imagine that the package bar in version 2.5 dropped the conflict. We are taking an over  approximation here. Packages sometimes they are a bit more conservative. And we get the  version of bar of version in between 2.6 and 3, then this constraint here is going to be  satisfied. So, this is another situation where even with a complex constraint, we can kind  of figure out what's going to happen in the future. However, if we look at the situation  like this, now the package foo requires my intervention because if we choose, now here  we have two possibilities. Either we choose bars or we choose bars or we choose bars.  If we choose bars of version 2.5, this is going to be, this is going to select this  package that is going to be in conflict with bar 2.5 and this is going to be in conflict  with this, with this constraint up here. If we choose bar 2.3, then this is not possible  because if we choose bar 2.3, I have to choose something that is less than 2.3 here, but  in the repository of version 2.5. So, these are all these kind of strange situations where  we can bump into and we developed a tool to actually identify all these packages, mainly  foo and try to flag the author of this package that this package needs, its dependencies  to be modified in order to be installable again. So, now, got demo. So, here, oops, here  again. I'm going to, I'm going to run this, this tool and this tool is going to take a  bit longer. It basically used the same engine of this check, but this time, since I have  to consider all possible features, all possible way of how these packages are going to evolve,  I need to consider a much larger universe and in this case, it's going to be about 80,000  packages. I also try to make sure that I consider the source cluster, so I don't let packages  to advance one by one, but in clusters because we don't want to end up in the situation where,  for example, we have a version of GNOME 3 and a version of GNOME 2 in my distribution,  I want either GNOME 2 or the cluster of GNOME 3 all together. This is going to take a bit  of time. Okay. We're going to come back to that. So, now, I've been talking about these  three tools that are meant to detect broken packages, to flag maintainers about broken  packages and to try to release distributions that, where every package can be installed.  Now we're going on something that it's more on the try to figure out how the distribution  is going to evolve and what are the important packages and how packages can evolve and what  they will break in the future if they evolve in a certain way. So, the first thing I want  to do is about talking about this concept of strong dependencies. We already talked about  it, I think, about two years ago. And this kind of came back a while ago, it was at Linux  and at GNOME Australia and one of the release managers of Ubuntu gave a presentation that  was exactly about this. So, I raise my hand and say we have all the solutions of your  problems. And so, since this seems relevant to them, I wanted to come back to it and to  try to explain what this is all about. So, the idea is to try to understand which packages  are important for our distributions. The notion of important is related if I have a bug in  a package, which other packages are going to be impacted by this bug. So, it's kind of  try to understand how a bug spread in my distribution. Or if I upgrade one package, which other packages  are going to be impacted by this upgrade. So, if I look only at the web of dependencies,  this is a bit too course and it's a bit too complex for a human to analyze. What we wanted  is we wanted to have a certain measure of the packages that are going to be affected  by a change. So, we define the notion of strong dependencies and the notion of impact set.  The impact set are those packages that are potentially affected by changes in a given  package. So, it's kind of a measure of how sensitive is this package and how careful  we need to be when touching this package. If, as I said, if we get the direct dependencies  too little, if you get the transitive closure of all dependencies, it's too much. So, we  want to, we need a stronger definition. The definition of strong dependency is actually  very easy. We said that P is strong depending on Q if it's not possible to install P without  installing Q. So, let's consider this small graph. Here we have packages that they have  either a disjunctive dependency or they have a direct dependency. Or in this case, there  is a conflict between easy and George. And here at the bottom, we have Charlie and Doug  that both depend on Fox. So, what we want to do is to actually try to understand which  are the important dependencies, which are the strong dependencies, and which are all  the others. So, in this case, George is a, George is a conjunctive dependency. So, in  order to install Able, I must install George because I really need it. But if I install  George that is in conflict with easy, automatically, these dependencies can never be satisfied.  And this implied that Baker must be installed all the time. And at the same time, since  Able depends both on Charlie or on Doug, and both of them depend on Fox, Fox must be installed  all the time. So, we end up in a situation where Able, in order to install Able, we always  need Baker, George, and Fox. It doesn't matter what. So, this gives us a way of trying to  find out which are the packages that are really, really important. And then we kind of end  up with a kind of a table where we can have this list of packages that, where we show  the impact set of the, for each package. When we compare the impact set to the direct dependencies,  actually, we found out that the direct dependencies didn't tell us a lot of things. As we, in  the first five, we have packages that maybe don't have that many direct dependencies,  but they have a lot of packages that depends on them. And so, if we touch them that are  really at the bottom of our web of dependencies, we're going to break a lot, a lot of packages  because these dependencies are going to be propagated upward. And this gives us a nice  notion to say, if I migrate DPKG to a newer version, probably I'm going to break about  13,000 packages. So, at least, these are very important packages. So, I'm going to upgrade  this to a newer version. Maybe I need to check that all the packages are strong dependents,  strong depend on them, they're going to be compatible with this migration, with this  upgrade. Another, so, these are on the strong dependency side, we also have kind of a notion  of, that I'm not going to present today, but the notion of domination. So, if you look  at the dependency, the web dependency of a distribution, you can kind of think, what  if I run one of the Google rank algorithm on this bank, on these dependencies. This is  going to give us the packages where most of the other packages depend. And it's going  to give you these kind of hubs everywhere. What we've done is we have used a similar  notion of strong dependencies that we have run a flow graph algorithm, where we were  able to find out the important packages, even if those were hidden under other packages.  So, imagine there was, imagine if there is a very, very important package where everybody  depends, but this one depends on another one. This means that actually there is one package  hidden down there that is not detected by our previous analysis. This, this, this dominator  algorithm allow us also to untangle this kind of hidden packages and try to find out a bit  more about the structure. The last tool that I'm going to present, it's the challenge packages.  Here, we're going to try to predict what is going to happen if, and since it's a prediction  about the future, it's going to be an over approximation. So, I'm not going to go deep  in how we did it as it's, I don't have enough time today, but what we wanted to do, it's,  it's we wanted to have a bit more than what we had with the strong dependencies. With  the strong dependencies, we had this notion of impact set and trying to understand what,  which packages were important. Now we want to, to answer to this question, what if we  upgrade the package P to a version of a version V to a future version and how many packages  are going to be affected by this upgrade? And in particular, the, the main problem is  which future version I'm going to, to consider because I can't consider all the future versions  as it's, I mean, the future it's, it's, it's infinite. I have to, to try to find out specific  versions that in relation with my, my repository today, today are going to be the most important  tomorrow. So, as I said, I wanted to do this, but only by looking at the, at the current  repository and I'm not going to use other kind of sources to predict how the packages  are going to be upgraded. And I also want to be consistent with the clustering information.  So packages, packages don't are not upgraded by, by themselves in, in isolation, but always  upgraded in a, in a cluster, in a cluster. So all packages that stem from the same source  package, they're going to be upgraded all together. And this, in the challenge at the  moment, it's very debian specific because of this reason, because we did this clustering  analysis on the Debian packages. I'm sure that it can be done also on the RPM packages.  And the, the idea that in Debian packages of the same source probably have the same version.  This is not, this is not a rule anywhere. But if they have the same versions, they are  going to evolve all together. If they don't have the same versions, then all bets are  off because we can't, we can actually predict how these packages can, can move all together.  So what we find is that by analyzing source clusters, most of them, they move all together  to a newer version. Some of them from a source package, you have different sub clusters,  for example, with different epochs. Some of them from a source package, they, they have  binary packages with versions that evolve in completely different directions. And in  this case, we really can't say how different, how these packages and versions are going  to evolve in isolation. So this, this challenge algorithm, it takes, it takes sometimes, it's  not something that you want to do on your machine. It's something that distributions want to  run once a day. It takes about, about 35 minutes, 40 minutes, a bit too much for an  all demo, a demo here. But I kind of give you the idea of how packages are going to evolve.  And this is particularly useful if you have a point-wise distribution. And you want to  modify only specific, specific packages. Then once in a while, you want to run this algorithm.  And kind of to, to see, I'm, I'm here in this, in this point in time with these packages.  And I want to, to migrate this component of my distributions. What is going to happen  when I do that? So as I said, we have source packages with versions. And then we have target  versions. The target version is the, the, this idea. What is going to happen when I upgrade  to a version that is bigger than? So in this case, the first four, so these are for, for  Debian squeeze. And we see that in Debian squeeze, the, one of the most problematic, problematic.  One package that, that emerged as problematic dependency-wise when upgraded. It means that  the dependencies on this, on the, on the Perl package are very tight. It's this one.  But it's this one for many different reasons. So if we upgrade from this version to a version  that is in between 10.5, 0.2, and 10.12, I break 2060, 652 packages. If I upgrade to  a version that is in between here, I break as many. But if I upgrade to a versions that  is in between this one, then I break a bit less. This basically is telling me that the,  the, the upgrade to specific version is going to break a number, a number of packages. But  not, not all the, all the upgrades are, are the same. So Python is also, is also another  one. I mean, there, there are many different, different examples. If you get a G-Lib C, if  you migrate to something that it's larger than 2.12, I'm going to break about 400 packages.  If I migrate something that is in between this version and 2.12, I'm going to break  a bit less packages and so on and so forth. This will give us a way of kind of picking  into the future and trying to understand what is going to happen if we migrate to a specific  version. So when actually going to change a component of your distribution and you run  this, this algorithm, you might be careful at where you're going to, to end up with your  migration. So one last, one last tool that I'm going to, to present. Actually, I'm not  going really to present as it's, it's a bit, it's a bit outside the scope of, of this presentation.  It's the co-inst tools that has been developed recently by one member of our group. And it's,  it's a tool to, to compute the installability kernel of distribution. What are the installability  kernels? So if we, we want to, to understand about how packages can be co-installable together.  In particular, we find out that in Debian, about 80% of the packages can be installed,  installed together. If you want to find the, the, the largest installation with the Debian  packages, you probably can install in Debian unstable about 30,000 packages all together.  But there are a number of packages that they, they can't coexist together. And what this  tool does is try to identify these classes of packages that can coexist, coexist together.  So for example, think about the, the mail agents. You can't install send mail and postfix  at the same time because the, the, the conflicts, the, the structure of conflicts doesn't allow  you to do that. This is a, this is a simple example about two packages or actually it's  a family of packages that come, cannot coexist together. But if you look carefully at the  distribution, there are not that many family of these packages that cannot coexist together.  And this, this tool just allow you to, to identify this, this class of packages and to  have a simple graph to, to analyze what's how, how the, the structure of conflict actually  works in your distribution. These are all kind of hidden structures that we are trying  to, to let surface, to let, to, to allow people to, to look a bit, a bit at the general, at  the general picture. So it's been written by Jean-Brouillon and if you're interested,  there is a website with a lot of explanations and very nice graphs. So my presentation  finished here that I think it's about 45 minutes and I'll be, I'll be very happy to take questions.  Yeah, it's, we, the question was about how deep we go in, in the dependency graph. We  consider the, the entire dependency graph. We're going to, we consider the entire, the  entire distribution. Give me one package file that it's our universe and, and, and we consider  all the packages. And with our tool, we, I think we analyze universe that are up to  100,000 packages. So I think we are in a good position to scale. The question was about  how long does it take for 30,000, 30,000 packages. It's about five seconds, 80,000 packages,  that's about two minutes. Yes. Do any of the tools that you developed have the capability  of working with packages different than Debian's? Yeah, we work with, so this check accept Debian  HD list synthesis file, CDF, that is this interchange format and Eclipse file. And once upon a time,  we have a filter for BSD, but it's not being rewritten. All these tools are, so every year  we, we promise a release. This year, actually, we are very, very close. We are so close that  there is a release of the source code on our website. And we are so close that there are  packages in Debian experimental. And we are so close that Ralph is working right now to,  to finish up the Debian package that we should be up sometimes next week. So this is a way  to put a bit of pressure on ourselves because we say we're going to release these tools  and then we never do it. Okay. Thank you very much.
QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_0_83.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_84_203.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_204_491.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_492_719.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_720_1127.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_1128_5867.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_5868_15239.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_15240_17255.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_17256_20651.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_20652_20819.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_20820_21431.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_21432_23135.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_23136_23963.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_23964_24971.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_24972_25067.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_25068_25115.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_25116_25307.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_25308_26411.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_26412_26459.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_26460_26531.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_26532_26627.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_26628_26819.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_26820_32447.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_32448_32567.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_32568_32939.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_32940_35099.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_35100_35471.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_35472_35591.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_35592_44951.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_44952_45299.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_45300_45383.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_45384_45731.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_45732_45875.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_45876_45959.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_45960_46223.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_46224_46571.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_46572_46631.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_46632_46907.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_46908_46967.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_46968_50903.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_50904_50999.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_51000_51143.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_51144_51515.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_51516_51731.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_51732_52211.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_52212_52367.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_52368_52439.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_52440_52595.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_52596_53243.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_53244_54659.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_54660_57143.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_57144_57419.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_57420_57635.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_57636_61211.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_61212_61427.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_61428_61895.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_61896_62003.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_62004_62051.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_62052_62135.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_62136_62195.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_62196_62447.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_62448_62495.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_62496_62975.png QA_tools_for_FOSS_distributions_FjaDQO_yLTc_2_62976_65349.png