>>Matt Lowrie: So let's get right to it.
Next lightning talk is from Fedor, or he goes by Ted, but he also has a fascinating history
about his name that you should ask about afterwards.
And I'll hand it over to you.
Take it away.
>>Fedor Strok: Okay.
Thank you.
Oh, okay.
Here it is.
So my talk will be about using formal concept analysis, whichever it is.
I guess that nobody here have ever heard about formal concept analysis.
Am I right?
Yeah.
That's the case.
So I have a double affiliation.
So one of them is Yandex, and the other one is Higher School of Economics.
It is -- the theory comes from the Higher School of Economics, and the practical tasks
are from Yandex.
So it would be a challenge.
So I would wish to be able to use the previous experience, but nobody to date told any words
about model-based.
So just to remember some key facts about this, it is a kind of cycle between the abstract
things like models and abstract tests, and the real life where you have the system and
the test bed you run.
And there are several ways how to get, actually, the model.
It could be obtained either by Oracle that is a kind of implementation that works, just
the requirements are.
And so the other hand is to get test sequences that should be run on the system under test.
And after implement the model, you can get the test output, either it is pass or fail.
And as for the modeling, there are several approaches how to do this.
Exactly, first of all is to extract from existing system how does it really work.
It is of special interest, and the project has a long history and a lot of product features.
The other hand is to model before implementation.
That will be quite applicable to crucial things.
And so the third approach is just what we see in real life and just to build both the
system and the model.
So the alternative is just to do it online or offline, whether we use the system under
test or not.
And so in offline case, we could just generate test cases and somehow postpone them to the
system under test.
So for possible implementations of the model base, there is a set of them, or theorem proving,
state machines, and so on and so forth.
And now I would like to say some words about the theory that is completely from the other
hand in terms of test case duration.
So it comes from algebraic theories.
It is rather new.
It is called formal concept analysis.
And it's -- mainly works with such things as formal context.
And it's a triple when you have a set of objects, a set of attributes, and a binary relation
over these things.
And this binary relation means that an object has an attribute.
Quite intuitive.
And so then have special operator that is shown with this quotation mark.
And they say that from the set of objects, we can get all the attributes that are common
for them.
And vice versa.
From a set of attributes gets the set of objects that has all of these attributes.
And how can we use this?
Actually, we can find in some sense maximal subsets of objects entered, attributes they
share, and form the ideal concept.
The concept, it means that you have set objects, they share some set of attributes, and this
set of attributes is general for all the objects.
And these objects can be -- This concept could be naturally ordered with such kind of thing
like set theory operations.
You mean that one concept is more general than the other, if all objects are just included.
So the intuition behind this is like this, that you have all attributes and in the real
world, usually no object has all attributes.
It is a kind of bottom concept.
And on the top, you have the vice versa situation, where you have all objects, and usually they
do not have any common attributes.
And then we can proceed to such a concept as implication.
Implication is just then to show the dependencies between sets of attributes.
So there is a mathematical concept how to show the implication.
But in natural world, it's -- can be described in the following way.
If you have an implication from A to B, it means that all objects that have A also have
B. There is some system that could make more
implications from the basic theories.
They are call Armstrong Rules.
For example, you can have always written the rule if you have A, then you have A. And some
more interesting things, like you can add attributes to the left-hand side, which is
called promise.
And it is a restriction on the set of objects that you are just interested in.
And so how can we use this?
To get from our concept set of implications, there is a procedure called attribute exploration.
The main advantage of this procedure, that it is interactive, and it cooperates with
two types of data.
On the one hand, it is a set of implications.
So you have the dependencies that are expressed in the form if A, then B. And on the other
hand, you have a set of counter examples.
And they are just your formal context.
So I have demo available on GitHub.
You can just proceed with the following example with me.
So make things easier and more intuitive for what is considered an example, let us have
a simple program.
And input just one number, and the output is a set of features of a given number.
I took into consideration just five of them, like, even, odd, prime, factorial, and if
the number is divided by three.
So attribute expiration procedure starts with the following.
It just asks you whether some implications are true or false.
For example, it starts with -- like following: Is it true that all numbers share all the
features from the given set?
And we have to provide the counter-example for the system to make it understand that
the world is built in some other way.
For instance, I took the number 2 and had to describe it in some features, that it is
even, factorial, and prime.
Then the system thinks all numbers are just like the two, that every number is even, factorial,
and prime.
And so on and so forth.
I could provide counter-examples, fill in my table, which is just the representation
of binary relation or formal context, just the same things.
And when I proceed with answering the questions at some moment, I give the implication that
really should stay true.
For example, we have -- if you have a factorial divided by three, then it is even.
We can think of theory of numbers.
And if we consider a factorial number which is divided by three, it already has a three
in its divisor, so it has two just by the definition of factorial.
So, yes, it should be even.
And then, after the procedure just takes you the whole way from all the implications, you
get two types of knowledge, actually.
On the one hand, you get these sets of counter-examples which say that they're a typical number that
you should check.
And for this procedure to work, you need -- and the main expert that should precisely know
how the domain is just organized.
So it would be difficult for an arbitrary person to fill the feature if he is not acquainted
with the main specific features.
And so in the end, there are two types.
On the left-hand side, we can see all their implications that hold for our small world
of numbers described in terms of five attributes.
That, for example, if the number is prime and divided by three, then it is odd, and
so on.
And in some sense, it is very likely to work like a model-based, because you have a set
of dependencies, and somehow you could generate the things on the right-hand side.
But to make the difference more clear, we could try to write so there's an example in
terms of model-based.
So we have a set of outputs, and there are two possibilities for them, true or false.
So everything is quite easy.
And we're, for example, using pair-wise, for get the sets of outputs that could be in no
way described in the real world.
Then we have to think of conditions and check that not all of these numbers are just in
the set of N. And then we have to consider that if we would
like to have the (indiscernible) same numbers, we could add them as a result.
And moreover, we have to consider the implications.
For the model-based they are just written in the previous thing.
If you have something, then you have something.
And there's implications for the case of model-based would be of two types.
First of them is just to say what are the implication that we get through attribute
expiration.
And on the other hand, so there should be some data-driven just to match the result
with the output.
So in the end, we finally set up with the same representation, so the binary table is
just like I get from the formal concept analysis.
So what are the main pros of the approach of using attributed expiration?
You have to parts of the result.
On the one hand, it is test cases just written in the form of objects.
And then on the other hand, you have dependencies between attributes and you do not have to
keep track in your head of all of the possibilities that are just able to be.
So this procedure is just stored information.
Also, the set of attributes can be ex- -- extended at any moment, and you can start from any
part.
You can provide some counter-examples and ask what are the implications for these examples,
and then to proceed.
And if you just decided to extend the set of attributes, what you have to do for the
existing objects, you have to mark what's -- objects just really have these attributes.
So there are other very nice -- the other very nice approach how to use the formal concept
analysis for software testing, we consider the following.
The formal context is just using Whitebox 16.
For example, usually the program has a set of ifs, and then it proceeds to the output
to their return statement.
And how to get all the cases done.
We just can get labels to each statement, and then we can see all the arrays from the
beginning just to the end.
And in this way, it's still a formal context.
So you'll have a set of objects that correspond to the (indiscernible) across your program.
And on the other hand, you have labels which (indiscernible) you have covered.
Then you just do this intuitive procedure of covering all the paths in your graph.
And you end with such a nice picture that all the test should you -- that you should
do is just shown on the right-hand side.
One thing that is not very intuitive, that's the implications in this form, they are just
about the presence attributes.
So on the left-hand side, there is a small formal context.
And according to the theory behind it, you have to write that there is a dependency that
even you have just one attribute -- just one object and it has just one attribute, B, then
you have the implication then from A, B, and C. It is so because there's a nice rule that
if you have something wrong on the left-hand side, then any statement will be right just
from the definition of implication.
And how to avoid it?
You could just consider all attributes as a pair of attributes.
It's actually -- in the case of the numbers, when we have even an odd -- odd numbers, there
is no number which is simultaneously even and odd.
So another quite good thing to think about from a contact analysis, that you can use
this natural order on concepts, for example, to get a nice test report.
So this partial order by subassumption on extents or intents, on the sets of objects,
on the sets of attributes, and all these concepts form analysis.
Just to be brief.
For example, we have such kinds of test report.
So some tests are just failed, and some of them are not.
We're interested in the failed part.
We start from drawing the whole diagram of the lattice.
They're ordered from the bottom, there are no objects, and on the top they are all tests
in some sense.
So then we focus on the failed part and we get the most common feature that they share
is just login feature, and down side you have some more details about why there are several
cases that have failed.
So this lattice usage is a good thing because iceberg analysis is equivalent to finding
the most common descriptions of failed tests.
So this is extremely used in big systems with tons of tests, and there is a graphical representation
how to get a (indiscernible).
On the other hand, in big systems, this technique could be very useful to get a good representation
for finding similar functionality.
That would be of special interest if you just deal with a feature that is quite common and
you have almost the same tests and how to find this same test.
So about the future work.
This framework is quite useful, but unfortunately, there are some borders.
For example, we do not use nonbinary attributes, but it is doable.
It is called pattern structures and is part of future work.
And another thing, we could use machine learning based on these formal concept analysis.
We can just find the hypothesis why some tests failed.
And this iceberg picture is just a good (indiscernible) how to do this.
So thank you.
I just hope that this talk was a bit inspiring, and you could find me in the break and give
the questions or use the online contacts.
[ Applause ] >>Matt Lowrie: All right.
Excellent.
Thank you.
I just have to wonder is -- if we use this model, can we use it to actually figure out
JavaScript operations?
[ Laughter ] That might be a good --
>>Fedor Strok: Actually yeah, because there are some research that use these techniques
to explore the (indiscernible) structures, and I believe the JavaScript is more bounded.
>>Matt Lowrie: Oh, wow.
That would be -- I kid JavaScript because I care, people.
I actually like JavaScript.
And we just have one question.
Do you have to provide counter examples manually or can it be automated?
>>Fedor Strok: Counter examples should be provided manually, but there are some researchers
when you have to find out the features of the counter example, so this part could be
automated.
So if you could find here is an object and what attributes are typical for him, this
part could be automated.
So the procedure overall is semi-automated.
You don't have to keep track of all the possibilities because you just answer one question at a
time.
But this knowledge of domain is really useful here.
>>Matt Lowrie: Thank you.
Another round of applause for Fedor.
[ Applause ]