More about testing in Yandex with robots

From the point of view of testing, Yandex is thousands of man-hours of work to check a large number of services. There is a lot of functionality, interaction scenarios - millions. We try to make sure that people are engaged only in complex and interesting tasks, and all the routine work could be entrusted to the robot.

Ideally, it is the robot that should verify that as a result of a simple page load or complex interaction with the input form, there are no exceptions flying out, "NaN", "undefined" or empty lines in place of the loaded data. The experimental project for the creation and implementation of such a robot has the code name "Robotester".

image

We already told how to implement it and learn how to work with forms. Today we will talk about how our robot is trying to find the maximum amount of functionality of the service, and then "understand" it.

Once, each site was a static page, the content of which was formed with a single request to the server. Now, many sites can be classified as Rich Internet Applications (RIA): they have become much more interactive and their content varies depending on the behavior of the user on the page. Web applications differ from traditional sites using technologies such as Javascript and AJAX, which allow you to significantly change the appearance and contents of the application without changing the address in the browser.

To test the site, the tester needs to not only complete the search crawler task and go through all the pages of the site, but also to visit all their states, or rather, to visit all the states of all pages on which various actions can be performed.

In the most general form, you can imagine a site in the form of a state graph and look for approaches to visit all the vertices in the graph, or at least their maximum number. But in this form, the task is meaningless - even for a simple Yandex service, the number of states is so large that it can be considered infinite. For example, entering each new query in the search field and pressing the “find” button leads us to a new state. That is, there are at least as many of them as you can enter various search queries. Therefore, we use the standard testing approach when states are divided into a relatively small number of classes. For example, it would be wise to divide many pages with search results into the following groups: lack of results, a small number of results, several pages of results. All classes must be given some kind of equivalence relation, after which we try to check at least one representative of this class. But how to teach this Robotester?

We have acted as follows. Still, we divided the task into two parts: by “crawler of pages” we go around the site by links, selecting a certain number of pages, and then on each of the selected pages we launch a “crawler of forms”, which, according to the algorithm described below, changes the page and stops only moving to a new one. That’s what we did because these two crawlers have slightly different tasks: if the maximum “depth” of clicks on links is rarely more than 5-6, then to go to a new page using forms, sometimes you need to do a hundred or two actions. As an example, you can look at the form for creating a campaign in Yandex.Direct , which you will see after authorization. Therefore, it is reasonable to use different workaround algorithms.

Of course, there are both outdated sites where there are almost no reasonable elements (only the first crawler will actually work there), and, conversely, modern RIAs, where the page url may not change at all (then only the second crawler will work). Nevertheless, we got a rather flexible system, which is easy to configure for almost any service.

How the page crawler works


So, our first task is to select those pages on which the form crawler will be launched. How to get a set of these "entry points"? At first, we generally decided that it could be done manually. Here's an example of a small list of pages:


As you can see, the page address contains a large number of parameters. If any of the parameters changes, the link becomes invalid. In addition, new page classes appear, and some of them become obsolete. Therefore, it became clear to us that we need to be able to dynamically compile and maintain a list of pages that need to be tested.

Suppose the graph of pages on our site has the form shown in the figure:
Let each edge of the graph be a link. A tool like CrawlJax begins to go from one peak in all possible ways. This method of crawling a site can take a very long time. But we decided that we would act differently: we select the “entry points” in the graph (green vertices in the figure) in such a way that, ideally, the set of green vertices becomes a 1-network . As a rule, in this case, the entry points are pages with forms, and available at a distance of 1 page is the result of a search. Thus, to test the site, it is enough for us to find the entry points, perform various actions on them and check for errors on the page to which we switched. It is worth noting that most pages of the 1-neighborhood of an entry point are identical in functionality, so not all representatives of such a neighborhood can be tested.

So, in order to test the site, the robot must have a list of some of its pages.

Web crawler is a fairly standard and very widely lit task. In the classic interpretation, the crawler needs to find as many pages as possible. The more pages, the larger the index, the better the search. In the context of our task, the requirements for the crawler are:

  • It should be possible to crawl in a reasonable amount of time.
  • The crawler should select as different as possible page structure.
  • The number of pages to be tested should be limited in output.
  • The crawler must collect from the page even those links that are loaded dynamically (initially not contained in the page code).
  • It should be possible to support authorization, regional dependence and other settings of Yandex services.

Requirement No. 1: time.
It may be necessary to control the duration of the testing process. Let's say you need to roll out a release and want to quickly check the basic functionality. Duration of crawling can be put in some framework by limiting the depth and number of pages visited.

Requirement No. 2: coverage
The second requirement follows from the need to cover tests with as much functionality as possible in as little time as possible. Obviously, the content service has classes of equivalent (in functionality) pages. You can cluster such pages based on the URL of the page and its html-code. We have developed a method that allows you to quickly and efficiently divide such pages into clusters.

We use two types of page spacing:

  • UrlDistance is responsible for the difference in urls. If the length of two urls is the same, then the distance between the urls is inversely proportional to the number of matching characters. If the length is different, then the distance is proportional to the difference in lengths.
  • TagDistance is responsible for the difference in the html-code of the pages. The distance between two DOM trees is the difference in the number of tags of the same name.

It is worth noting that the implementation of the second requirement must be consistent with the first requirement. Let's say we need to select pages for testing the Yandex.Market site. Suppose that each page leads N links and we are interested in the depth of the crawl K. To compare all the pages, we have to download the html-code O (N K ) pages. This can take a lot of time, given that there may be 20-30 links leading from each page of the content site. This method does not suit us. We will filter the pages not at the very end, but at every step.

So, we have at our disposal a list of links from the current page, from which we need to choose the most different ones.

  • The first stage of filtering: compare url by UrlDistance, leaving the L most different.
  • The second stage of filtering: load the html code of the L most pages that differ in the UrlDistance metric and save them using TagDistance.

Thus, we need to download the code only for O (L · K) pages. With all these simplifications of the page filtering process, the quality of the resulting "entry points" suits us!

Requirement No. 3: the number of pages tested.
The implementation of the third requirement will allow us to limit the number of pages on which tests will be conducted. Roughly speaking, we are telling the robot “select the N most functional pages and test them.”

Requirement 4: consider dynamically loaded content
. WebDriver allows you to collect links even from blocks that are loaded dynamically and only click on visually accessible links (modeling human behavior) .

Requirement No. 5: context
In order to take into account a context like a region or user rights (different issuance, different functionality), the crawler must be able to work with cookies . For example, did you know that even the Yandex main page in different regions can be different?

So, we have fulfilled all the above requirements and were able to quickly and efficiently find the largest possible amount of site functionality. The robot has found "entry points." Now you need to visit the 1-neighborhood, or, more simply, interact with the form.

Crawler forms


To test the functionality of the site, you need to be able to use it. If you start thoughtlessly clicking on everything and enter any values ​​in the input text fields (how to enter not any), then you won’t be able to qualitatively test the form in a reasonable time. For example, it’s quite difficult to interact with such forms on Yandex.Direct as in the figure below.

image

So when you click on the “change” button, a new block appears, in which when you select the next value of the radio button, the shape on the gray background changes, which in turn dynamically changes when filling in the fields. Obviously, with so many input fields, as in this form, some strategy is needed, otherwise the robot will stand still for a long time.

Let's formalize the task. We can assume that all input fields are drop-down lists. In fact, the text input field for us actually becomes a drop-down list when we determine its type and select a finite number of values ​​that we can enter into it. Our task is to test the form in an optimal way, which implies the maximum coverage with a fixed number of test cases or the minimum number of test cases with a given coverage (depending on what is more important to us - test speed, or coverage level).

A simple case . The input fields are a fixed number, and they do not change, that is, they do not depend on each other. This task is quite popular and widely covered. For example, we use a program with a beautiful name Jenny .

It takes as input the desired coverage depth and a set of numbers that are responsible for the number of options in each input field. Consider an example of a small form. Suppose we are interested in coverage of degree 2 for a form of three input fields, each of which has two options. The instructions for filling out will look like this:
Number is the number of the input field, letter is the number of the option to be selected. A coverage of degree N means that if you fix any N columns, then all possible combinations will be found in them.

Difficult case . The form is dynamic and the number of input fields changes. For example, as a result of filling in the first three fields, a fourth and fifth input field appears, or the “send” button immediately appears. A “state graph” is suitable as a model of this form. Each vertex of the graph is a state of form. It can change by removing the input field from the form, changing the value of the input field, or adding a new one.
We have formulated several assumptions that are not critical for us, under which the algorithm should work:

  • Input fields are rarely deleted, so we do not consider such a case.
  • If, when filling in the field A, the field B has changed, then it is necessary to topologically sort the input fields, having received the order in which we will first fill A, and then B, if B depends on A. In practice, we believe that the higher ones (it’s physical location on the page) elements do not depend on subordinate.
  • If as a result of the interaction a new input field appears, then we believe that it depends on only one of the previous input fields. In fact, this is not so, but this assumption greatly simplifies the task.

The transition to another vertex is carried out by changing the state of one input field.

Suppose, initially, a form consists of elements A 1 ... A n . For each A i we perform:

  • We are trying to interact with A i in all possible ways. Let these methods have k pieces.
  • We fix those elements B i1 ... B ik that appeared during various fillings of Ai.
  • Repeat the procedure recursively for each of B ij .

With this approach, the algorithm can work for a very long time, since the number of interaction methods will grow exponentially from the number of elements. In order for the form crawling to end in the foreseeable future, enumeration of all possible methods of interaction is carried out only for elements located at a depth of no more than 2, and for all others we select one random value. This approach is necessary for testing forms in which a certain number of required fields is required.

Algorithm


Suppose, initially, a form consists of elements A 1 ... A n . For each A i we perform:

1. We are trying to interact with A i in all possible ways. Let these methods have k pieces.
2. We fix those elements B i1 ... B ik that appeared during various fillings of A i .
3. For each element B ij , until we reach the end of filling out the form, perform:
3.1. We interact with the element B ij in all possible ways.
3.2. With each element that becomes available when filling in B ij , we interact in a unique random way.

image

The optimal coverage is generated on the basis that A i is a drop-down list with as many options as there are ways to level 3.
Let us give a concrete example.

image

From the peak A 1 there are five paths to level 3, from the peak A 2 four and from the peak A 3 four too. Accordingly, A 1 can be represented as a drop-down list with five fields, and A 2 and A 3 with four. Следовательно запускать Jenny . обот будет с аргументами «5 4 4».

We taught the robot to find the functionality of the service and thoughtlessly (regarding a person) to use it. Of course, you should not expect that in the near future he will register with Yandex.Direct, independently create an advertising company for his beloved and become famous throughout the world, although he already knows how to create projects on the internal service (though they are, oddly enough, until they shot :)). However, we do not expect this from him! He fills out the forms competently and to the end. We expect him to do quality testing of web interfaces, and he lives up to our expectations.