Welcome, I'm going to do the first presentation, so I think everything is going to be
in Cretando, but I'm going to present you a statistical path coverage that this is a technique
or a method that we started working on, still to Linux and P project, lead by us at the end.
This was a project based on researching on Linux safety projects, and we started with a statistical
path coverage there. It was very focused for safety related systems, but we think it's interesting
for all type of critical systems, not only safety ones, and it may be interesting for
increasing the testing of strategy of these systems. So, first of all, let's put it a little
bit in context. The critical system that we are building today, we say the next generation
critical system, but we are already building them, have or are running deep learning algorithms,
we see trying with the break of AI. Also, they have...
Okay, okay, so loader? Okay, I'm going to start again. So, first of all, the context is that the critical
system that we are building currently, have different requirements, they are running deep learning
algorithms, some of them, they also security plays a key role in all these applications, and
they have high performance requirements. Different industries, as far as to employ the commercial
of the self-smaltical, the performance provided by the commercial of the multiple processors,
but these hardware was designing from an average maximum performance and not for critical
systems. For example, if we check it for safety related systems, right now we don't have a 35
multi-core hardware to use it. With all these points in siltyling example, we saw that there
was a need of an operating system to run complex algorithms with high performance requirements
and also with security requirements. If we check the Linux kernel, I will say we can see that
it's the key, I will say. It's the non-critical domain. It's the linear operating system
in embedded systems, in smartphones, it's almost the only solution in supercomputers, and it
works also in the majority of web servers. There are different reasons for this, but the
main ones it has white hardware support. We have lots of drivers in the Linux kernel, and
this provides all this support. It has really good, or significantly better than all
those multi-core capabilities, and also security capabilities are important, and that's
why different companies choose or even governments choose Linux. Also, let's develop
a new system and why the developers community like here, right? So the question that
racist here is, can we use Linux for critical systems? Right now, we have thousands of Linux
based computer orbiting their Earth. So different companies and governments rely on Linux to
build their satellites. We can find Linux even in a space rocket, in control units of a space
rocket, and we can find Linux even in other planets like in Mars. NASA deployed a small
drone, or a small helicopter based on Linux, and a Snapdragon multicore. Also, different
governments and companies rely on Linux for the telecommunications, critical servers, and for
instance, banking systems. So can we use it for critical system? I would say that, yeah, we are
already using it, how do we test the Linux 40s. So here, when we start it into Linux, we
identify some problems, and it's that we know that this in an analysis of a critical
system is crucial, and that we need to quantify this testing effort. When we are doing testing,
we need to know how much do we test. Traditionally, the objective of the testing process was to get
100% test coverage, but we are going to see that in the presentation, sometimes this is not possible,
not feasible, and even not the syllable. We don't need 100% test coverage. I'm going to put some
definition from functional safety. It's only for functional safety, but I think it's interesting
to have this ideas for all critical systems. And when we talk about functional safety, we are talking
about systems with credible risk, or freedom from an acceptable risk. Sometimes we can hear from
some people that safety systems without any risk, and any developer in this room will say that
the system has no back, right? So every system has some risk, but we need to achieve an acceptable
risk. So therefore, in system safety, when we are doing engineering processes, tools, the
objective is to get this achieve our risk. For that, we use testing analysis, and testing helps us
to fix bugs, or mitigate them, also we understand better the system while we are doing this testing,
and therefore, consequently, we need to quantify this testing effort, right? This testing process.
We need to know how much do we know about the system or how tested it is it?
To quantify this testing effort, we always talk about test coverage, and there are different
metrics for test coverage. We can find French coverage, function coverage, land coverage, there are
different types. For the SILT-LINUXMP project, as the objective was a SILT, we focus in path coverage,
but that's not an important point here, and the presentation goes about path coverage, but it's not
my idea. The important note here is that, for instance, in the SILT-LINUXMP, SILT-LINUXMP, we can consider that
it is the general standard for SILT-LINUXMP systems. It notes world 100 coverage cannot be achieved,
and a property explanation should be given. This is one point that we need to remember through
the presentation. So let's try to get 100% test coverage, right? We take the LINUXMP
kernel, we start like that, let's download the LINUX kernel and check it. LINUXMP has
over 27 million lives of code, so it's a huge project. It is treated from this
almost 13 million lives of code, or maybe it's by now it's over 30, I don't know. Half of it
remains for drivers, it's for hardware, so we are not going to use all this 27 million lives of code,
right? Also, our application is going to use only part of this kernel, only some features that
we need only for our application, so it's not going to exercise. It's also important to know
that LINUXMP is continuously evolving. We have already this critical system needs to be
updated, traditionally we have the systems critical and we didn't have it, but now it's
going to be important to update the system for the security requirements. We have a six
patcher per hour rate of update and LINUXMP has been developed every day in all the year,
weekdays, weekends, every day. So what is going to be exercise in the LINUX kernel for
our critical application? Yes, starting like that, it was like, okay, just take us, that the
code analysis and see what is going to be exercise. We got this huge call graph, enormous call graphs,
there were not to suffer for anything. You cannot deal with that, it's enormous, it makes no sense.
Amor, this call graph only gives partial results because they cannot solve some problems that are
selected in runtime. They cannot solve integrated calls, they cannot solve aliases, they provide
that code also that it's not going to be used and therefore it's not going to be tested and they
cannot solve assembly code. To this problem, we need to add another feature of the LINUX
kernel that it's non-determinist. LINUX kernel is non-deterministic, this means that the same application
with the same inputs may follow different execution paths. So traditionally, we have deterministic
systems. This means that for the same input, always the function sequence that it was the
executed, it was always the same and therefore it was easier to test it. But right now, LINUX kernel
is non-deterministic and this is due to the global state of the system. It will select which
execution path to follow depending on the global state of the system. So as example, if we do an
application that it's writing in DevNull for instance, we write some string in DevNull, we have
a really clean and nice looking execution phrase like this. Very short time, taking into account
that the LINUX kernel is designed or developed from performance point of view, perfect sense. But
sometimes there will happen as synchronous events like RCQ that we can find almost anywhere in the
execution phrase. So for non-determinist, it's important to have
to account that it's not possible to force the execution of a specific path because it
doesn't rely only in the input. We cannot force the execution because depending on the input,
there can be many execution paths. It relates on the state of the system. And this
state is not generally reproducible due to the complexity. There are enormous amount of asynchronous
events and concurrency going on in hardware and software. So with all these, we identify the
many issues we will have due in testing. We see that one iteration of a testing, it's not enough.
And this is why many kernel developers struggle finding some facts. They know that
some time, a bug is happening, but they are not able to force the execution of that bug. And they
once per week find it and something is going on. Therefore, we need to execute all the tests
repeatedly. And one conclusion is that we need continuous testing, continuous testing is okay.
But the problem is that we don't know which traces can be executed,
which execution path can be executed. So the question that arises here is, which traces need to
be tested, how many traces do we need to test? And how do we quantify this testing effort?
And that's why we start thinking on it and say, let's go to a statistical work. Let's use probabilities
to do it. So we are going to show a statistical pulse coverage that it's based on a statistical analysis
to do test quantification and also to be able to estimate the residual risk in software.
The approach is to based on probability and not only in possibilities,
we are going to be focused on credible risk of our critical system and not all risk,
because it makes no sense. We are going to focus in the credible risk of our system.
And therefore, for doing that, we are going to record the behavior of our system with this
recording, we are going to get some data, where we can provide some statistical analysis.
And finally, we can quantify the testing of software selection likeliness.
Statistical path coverage, we can divide it in three faces. Collect data, model data and risk estimation.
For the first one, for the first one, data collection, we built a tool called DV4C2
that it's based on dynamic data collection, that it's F trace. It's well known in kernel developers.
It's including in the Linux kernel and it allows to record a execution that it's going on in the Linux kernel.
And these two, it's publicly available. It's in our first repository in GitLab.
So you can view it or you can test it if you want. And basically what it does, it has a client and a server.
In the client we have our critical system that it's recording, what it's going on.
Once we have all these recordings, we send it to the server and we post-process them.
In this first processing, we identify the system calls right now.
This is not complete, but it has a prototype, it works well.
Because we consider the system calls the entry point in the kernel.
We do an analysis of independence within system calls and we check that system calls are independent.
And we calculate the MD5 hash of these execution traces.
Why do we calculate the hash? Because this permits us to do analysis matches here.
We can see how the sequence is closed, the frequency of the its system call.
To calculate the statistical analysis later, it matches here. So we deal with MD5.
We are working also in a graphical interface unit for the tool to be matches here.
This is not yet publicly available, but I think it is to have it.
Where we can solve different data. In this data we can solve for instance the sequence diagram.
The execution sequence diagrams by system calls. So we have the system calls.
In black lines we find the common one, the one that I showed you before for instance.
And in red lines, it's around here and if the color is the best one,
we identify the sapaths that have happened and when they happen, we switch frequency.
Also we are able to plot the histograms. So we see how many times its trace has been executed within the testing process.
And we get an idea that normally as Linux it's developed from an upper promise point of view.
They come on for a security a lot of times, but we have some faces.
Sometimes there are some pretty tries that are happening and there are a huge amount of these pretty tries.
So once we have all this data, we can continue to fetch you that it's model in data.
And for this data model we choose to have a parametric approach. Why a parametric approach?
Because if we get a model with a fixed parameters that describe the behavior of the system,
we are able to extrapolate from the model we have.
So if we get this model, we can extrapolate to say, okay, I get the decay during 10,000 hours of testing.
Let's coat and thin it, right?
So for this events, I'm not going to go deep in the statistics. If you want to
can ask me or send me an email, but we just choose over your events that it's a
personal distribution, but for that we need to focus in the execution traces that happened
directly. To select these execution traces, the very ones we use entropy theory that basically
we divide the groups into two with the same amount of information. And we can focus on them.
So here, in the plot we saw the number of traces that have appeared, the rate traces that has
appeared during the testing process, during the test cycles that we have managed,
test cycles that test campaigns. And we see that while we are testing the system,
the number of these rate traces goes, it's decreasing, it makes sense, right? Because we know more
about our system. Therefore, if we are able to model, we get the model that it's code decreasing.
And after we can do, we can extrapolate this model and think, okay, instead of 250 test
campaigns of test cycles, if we go to infinity, how many traces would be appear? And just doing an
improper integral, calculating the area, we can do this estimation. So in this use case that we
have that it was a autonomous emergency braking system, we got a test coverage of 85%. So 15% was
not tested in 10,000 hours of testing process. Is this 15% an acceptable risk or not? That's the
question, right? We have 85, but what does 85 mean in this case? We need to know if it is a acceptable risk
or not. So for that we need to estimate the risk. And if you remember, we were thinking that
100% coverage cannot be achieved and appropriate estimation should be given. So let's calculate
the risk as an explanation. And therefore, we can see if it is freedom from an acceptable risk or not.
Risk can be calculated probability by severity. So let's go to the work system area where
the severity is one because we consider that the execution of an untested trace, it's an acceptable
or it's catastrophic, right? We need to calculate the probability for that. And to calculate
the probability of an event that didn't happen, we can use simple good terrain, that it's
known in statistics and we calculate that probability. So we know now, which is the probability
of executing one of unknown tests, right? And in hardware, it is common to find in different
standards or in manuals, not as it's probability of failure per hour. But in software, it's not at home.
There are some standards, but it's not with software developers don't talk about that much, right?
And I think that for this case, it's interesting to have these ranges. So we can get this range
each and say, okay, it's this acceptable or it is not acceptable.
Furthermore, this probability can be proof and this can be proof capitalizing on complexity
of the systems. So if we know that the Linux kernel is not deterministic, we can use
redundant architecture that are well known in critical system and safety system. And let's say,
okay, execute application, same time in two containers, for instance, and the probability that
two containers execute at the same time and untested races, the probability will decrease.
So we can reduce also this probability by using or capitalizing the non-determinist
of the Linux kernel, using redundant architectures. Instead of two channels, if we have three
channels or four channels, this risk also will go decreasing. So just to end, some conclusions about
the presentation and the method, we proposed this statistical method to estimate the number of
traces that we are going to exercise and have relevant probability of being executed.
We can estimate this execution probability of what we haven't tested and therefore we can calculate
also the residual risk of this untested races. I will say that this can be a problem or also a
possibility and if we capitalize on complexity and we don't focus on all possible risks but
incredible risk in all possible paths but in paths with a probability of being executed,
we can save to a probability world and capitalize on that. So it will be an opportunity and not only
a problem and we are open to other statistics. The idea was not to select a statistic, which wants to
use. The idea was to see if it is feasible to use a statistical world for this and we think the
objective was achieved and we know that the technique is only possible if continuous monitoring
is done but I think for the next generation, next generation, critical system, continuous monitoring
would be mandatory anyway. And it will be great to have additional experts review or certification
authorities review. As future long, we want to extend analysis not by system call but we want
to include all the calls that are in the Linux kernel. We know that this is limited. We want to
publish the graphical interface in the public repository soon and it's working adequately and also
we note that this is an argument to be updating continuously and we know that our statistic has
some parameters that will detect if an update changes the behavior of the system. Right now it's working
correctly but we need further analysis on this also and this is the next big step that we are doing
in this statistical path coverage. And this is in context technique that depends on the use case.
It's great to have different use case to be analyzed and being continuous monitoring to do it.
So thank you very much. If anyone has any question, you can ask it right now or you can send
me an email if you want.
I would like to ask a question about the unique traces and experiments as a whole. Where you have
dates in the kernel version or user space during these 10,000 hours? No, in this 10,000 hours it was
a question. Okay. So he asked the result if we saw that if the system was being updated and
it was not, it was a static kernel that it was not being updated. So the update part, it's been
tested right now, we are dealing with that. So all these statistical models has some parameters that
will detect if changing the behavior of the system happens. Right now in this result is
it was not. Okay, thank you. All clear? Okay, great.
What is the question? Do you have a target of the reduction on the number of tests of our testing
when you start to expect that to save 20 percent of the time? No, no, the about the percentage of
the test coverage, no, about the residual risk. That's why I talk about probability per
value per hour. There are some in hardware, well known and 65,58, that it's the generic
standards, so some values and we did this comparison with these values and we using redundant
architecture we can achieve them in this case. But there is no well-known ranks right now selected.
You gave the example and showed us that for the test that you did, you got about 85 percent
test coverage and you asked if that wasn't added. You have any metrics to find out whether or not
that is enough, you get any results on that. Can you repeat it? Can you have any anecdotes of whether
or not 85 percent is a good number for testing in this kernel? Or is this enough in use cases
Okay, so tradition, if you go to a tradition, I'm sorry, so he asked if the 80 percent
test coverage is it enough or not. So traditionally one will say that if you have not 100 percent
it's not enough, I say that that's why we do the risk estimation and that's the important thing.
The test coverage it can give you some feelings, so if it is enough or not, but the important
thing is the risk. So I can say that it's 99, but if this one percent is catastrophic, 99
it's not enough. If this is 10 percent it's non-catastrophic, it's enough. So it's not about getting
the number and this happened to every developer. When you are testing, the objective of testing
it's to fix it and not to get 100 percent, but sometimes you are doing the test and you need to
be objective on that. You are doing the test to get the number and that doesn't make sense, right?
It's not about getting the number, it's making the system safe. Thank you.
Yeah? You talked about needs continuous monitoring, what you mean by continuous monitoring
and what purpose? Okay, so yes, asking about continuous monitoring.
So continuous monitoring here should be, I think, deciding in context of the use case,
we need to doubt that because the test will be designed depending on the use case,
but like in real-time Linux they are using continuous monitoring to see how it's
pre-altime Linux working on, for that we also will need to do that for these systems.
And before for instance, we have to unafter to the critical system that it's in the route or in the
street or in an industry, we need to do this continuous monitoring and our labs. So that's why
we need these systems running in our labs, being tested continuously and checking all these
topics, it's going to be okay, you're not okay. That's it. Thank you very much.