White box testing

The development of high quality programs implies that the program and its parts are being tested. Classic unit testing involves breaking a large program into small blocks suitable for testing. Or, if test development takes place in parallel with code development or tests are developed prior to a program (TDD - test driven development), then the program is initially developed in small blocks that meet the requirements of the tests.

One of the varieties of unit testing can be considered propery-based testing (this approach is implemented, for example, in the libraries of QuickCheck , ScalaCheck ). This approach is based on finding universal properties that should be valid for any input data. For example, serialization followed by deserialization should produce the same object . Or, re-sorting should not change the order of the elements in the list . To test such universal properties in the above libraries, a mechanism for generating random input data is supported. This approach works especially well for programs based on mathematical laws that serve as universal properties valid for a wide class of programs. There is even a library of ready-made mathematical properties - discipline - which allows you to check the implementation of these properties in new programs (a good example of re-use of tests).

Sometimes it turns out that it is necessary to test a complex program without being able to disassemble it into independently verifiable parts. In this case, the program being tested is the black white box (white - because we have the opportunity to study the internal structure of the program).

Under the cat described several approaches to testing complex programs with a single entrance with different degrees of complexity (involvement) and different degrees of coverage.

* In this article, we assume that the program under test can be represented as a pure function without an internal state. (Some of the considerations given below can be applied even if the internal state is present, but there is a possibility of resetting this state to a fixed value.)

Test bench

First of all, since only one function is being tested, the calling code of which is always the same, we do not need to create separate unit tests. All such tests would be the same with the accuracy of the input data and checks. It is quite enough to transfer source data ( input ) in a loop and check the results ( expectedOutput ). In order to detect the problem set of test data in case of an error, all test data must be labeled. Thus, one set of test data can be represented as a triple:

 case class TestCase[A, B](label: String, input: A, expectedOutput: B) 

The result of a single run can be represented as TestCaseResult :

 case class TestCaseResult[A, B](testCase: TestCase[A, B], actualOutput: Try[B]) 

(We present the result of the launch using Try to catch possible exceptions.)

To simplify the run of all test data through the program under test, you can use an auxiliary function that will call the program for each input value:

 def runTestCases[A, B](cases: Seq[TestCase[A, B])(f: A => B): Seq[TestCaseResult[A, B]] = cases .map{ testCase => TestCaseResult(testCase, Try{ f(testCase.input) } ) } .filter(r => r.actualOutput != Success(r.testCase.expectedOutput)) 

This helper function will return problem data and results that differ from those expected.

For convenience, you can format test results

 def report(results: Seq[TestCaseResult[_, _]]): String = s"Failed ${results.length}:\n" + results .map(r => r.testCase.label + ": expected " + r.testCase.expectedOutput + ", but got " + r.actualOutput) .mkString("\n") 

and display the report only in case of errors:

 val testCases = Seq( TestCase("1", 0, 0) ) test("all test cases"){ val testBench = runTestCases(testCases) _ val results = testBench(f) assert(results.isEmpty, report(results)) } 

Input preparation

In the simplest case, you can manually create test data to test the program, write it directly in the test code, and use it, as demonstrated above. It often turns out that interesting cases of test data have much in common and can be represented as some basic instance, with minor changes.

 val baseline = MyObject(...) //        val testCases = Seq( TestCase("baseline", baseline, ???), TestCase("baseline + (field1 = 123)", baseline.copy(field1 = "123"), ???) ) 

When working with nested immutable data structures, lenses are a great help, for example, from the Monocle library:

 val baseline = ??? val testObject1 = (field1 composeLens field2).set("123")(baseline) //    : val testObject1 = baseline.copy(field1 = baseline.field1.copy(field2 = "123")) 

Lenses allow you to elegantly "modify" deeply nested parts of data structures: Each lens is a getter and setter for one property. Lenses can be connected and get lenses that "focus" on the next level.

Using DSL to present changes

Next, we will consider the formation of test data by making changes to some initial input object. Usually a few changes are required to get the test object we need. It is very useful to include a list of changes in the text description of the TestCase:

 val testCases = Seq( TestCase("baseline", baseline, ???), TestCase("baseline + " + "(field1 = 123) + " + //  1-  "(field2 = 456) + " + // 2- "(field3 = 789)", // 3- baseline .copy(field1 = "123") // 1-  .copy(field2 = "456") // 2-  .copy(field3 = "789"), // 3-  ???) ) 

Then we will always know for which test data the test is performed.

So that the text list of changes does not differ from the actual changes, it is necessary to follow the principle of the "one version of truth". (If the same information is required / used at several points, then you should have a single primary source of unique information, and all other points of use should be distributed automatically, with the necessary conversions. If this principle is violated and the information is copied manually, then . discrepancy version information at different points in other words in the description of the test data, we see one, and test data -. another example, copying a change field2 = "456" and adjusting it in the field3 = "789" we Mauger accidentally forget to correct the description. As a result, the description will only reflect two changes of three.)

In our case, the primary source of information is the changes themselves, or rather, the source code of the program that makes the changes. We would like to derive from them the text describing the changes. Offhand, as a first option, you can suggest using a macro that will capture the source code of the changes, and use the source code as documentation. This seems to be a good and relatively uncomplicated way to document actual changes, and it may well be applied in some cases. Unfortunately, if we present changes in the form of plain text, we lose the ability to perform meaningful transformations of the list of changes. For example, to detect and eliminate duplicate or overlapping changes, draw up a list of changes in a convenient way for the end user.

To be able to operate with changes, it is necessary to have their structured model. The model should be expressive enough to describe all the changes we are interested in. Part of this model, for example, will be addressing the fields of objects, constants, assignment operations.

The change model should allow to solve the following tasks:

1. Generating instances of the change model. (That is, in fact, the creation of a specific list of changes.)
2. Formation of the text description of changes.
3. Apply changes to domain objects.
4. Perform optimization transformations on the model.

If a universal programming language is used to make changes, it can be difficult to represent these changes in the model. In the source code of the program can be used complex constructions that are not supported by the model. Such a program to change the fields of an object can use secondary patterns, like lenses or the copy method, which are lower-level abstractions relative to the level of the change model. As a result, an additional analysis of such patterns may be required to display instances of changes. Thus, initially a good option using a macro is not very convenient.

Another way to create instances of a change model can be a specialized language (DSL), which creates objects of change models using a set of extension-methods and auxiliary operators. Well, in the simplest cases, instances of the change model can be created directly, via constructors.

 val target: Entity[Target] // ,     val updateField1 = target \ field1 := "123" val updateField2 = target \ subobject \ field2 := "456" // ,   DSL: val updateField1 = SetProperty(PropertyAccess(target, Property(field1, typeTag[String])), LiftedString("123")) val updateField2 = SetProperty(PropertyAccess(PropertyAccess(target, Property(subobject, typeTag[SubObject])), Property(field2, typeTag[String])), LiftedString("456")) 

 def eval(expression: DslExpression, gamma: Map[String, Any]): Any = expression match { case LiftedString(str) => str case PropertyAccess(obj, prop) => Getter(prop)(gamma).get(obj) } def change[T] (expression: DslChangeExpression, gamma: Map[String, Any], target: T): T = expression match { case SetProperty(path, valueExpr) => val value = eval(valueExpr, gamma) Setter(path)(gamma).set(value)(target) } 

This approach generally works, and really allows you to describe the changes once, but gradually there is a need to introduce more and more complex changes and the model of changes is growing somewhat. For example, if you need to change a property using the value of another property of the same object (for example, field1 = field2 + 1 ), you need to support variables at the DSL level. And if the property change is nontrivial, then at the DSL level, support for arithmetic expressions and functions will be required.

Branch testing

The code under test can be linear, and then by and large we only need one set of test data to see if it works. In the case of a branch ( if-then-else ), it is necessary to run a white box at least twice with different input data so that both branches are executed. The number of input data sets sufficient to cover all the branches appears to be numerically equal to the cyclomatic complexity of the code with branches.

How to generate all the input data sets? Since we are dealing with a white box, we can isolate the branch conditions and double-modify the input object so that in one case one branch is fulfilled, in the other case the other. Consider an example:

 if (object.field1 == "123") A else B 

Having such a condition, we can form two test cases:

 val testCase1 = TestCase("A", field1.set("123")(baseline), /* result of A */) val testCase2 = TestCase("B", field1.set(/*  "123", , , */"123" + "1">)(baseline), /*result of B*/) 

(If one of the test scripts cannot be created, then we can assume that a dead code has been detected, and the condition along with the corresponding branch can be safely removed.)

If independent properties of an object are checked in several branches, then it is quite easy to form an exhaustive set of modified test objects that completely covers all possible combinations.

 val change1: T => T = field1.set("123")(_) // val change1: T => T = _.copy(field1 = "123") val change2: T => T = field2.set("456") 

 val changes = change1 compose change2 

 val rawChangesList: Seq[T => T] = Seq(change1, change2) val allChanges: T => T = rawChangesList.foldLeft(identity)(_ compose _) 

 val tests: Seq[(String, T => T)] = IF("field1 == '123'") //  ,    THEN( field1.set("123"))( //  target \ field1 := "123" IF("field2 == '456') THEN(field2.set("456"))(TERMINATE) ELSE(field2.set("456" + "1"))(TERMINATE) ) ELSE( field1.set("123" + "1") )(TERMINATE) 

 val tests2: Seq[(String, T)] = tests.map(_.map_2(_(baseline))) 

Automatic generation of test data

Since we are dealing with a white box, we can see all the branches. This makes it possible to build a model of logic contained in a white box and use the model to generate test data. If the code under test is written in Scala, you can, for example, use scalameta to read the code, and then convert it into a logic model. Again, as in the previously discussed issue of modeling the logic of change, it is difficult for us to simulate all the capabilities of a universal language. Further, we will assume that the code under test is implemented using a limited subset of the language, either in another language or DSL, which is initially restricted. This allows us to focus on those aspects of the language that are of interest to us.

Consider a sample code containing a single branch:

 if(object.field1 == "123") A else B 

The condition divides the set of field1 values ​​into two equivalence classes: == "123" and != "123" . Thus, the entire set of input data is also divided into two equivalence classes with respect to this condition - ClassCondition1IsTrue and ClassCondition1IsFalse . From the point of view of completeness of coverage, it is enough for us to take at least one example from these two classes to cover both branches A and B For the first class, we can build an example, in a certain sense, uniquely: take a random object, but change the field field1 to "123" . In this case, the object is sure to be in the equivalence class ClassCondition1IsTrue and the calculations will go along branch A For the second class there are more examples. One way to generate some kind of second class example is to generate arbitrary input objects and discard those with field1 == "123" . Another way is to take a random object, but change the field field1 to "123" + "*" (for modification, you can use any change in the control line, ensuring that the new line is not equal to the control line).

The Arbitrary and Gen Arbitrary from the ScalaCheck library are quite suitable as random data Arbitrary .

Essentially, we are reversing the boolean function used in the if . That is, we find all the values ​​of the input object for which this boolean function is true - ClassCondition1IsTrue , and all the values ​​of the input object for which it is false - ClassCondition1IsFalse .

Similarly, you can generate data that is suitable for constraints generated by simple conditional operators with constants (more / less constants, part of a set, starts with a constant). Such conditions are not difficult to reverse. Even if simple functions are called in the code being tested, we can replace their call with their definition (inline) and still implement the inversion of conditional expressions.

Hard reversible functions

The situation is different when the condition uses a function that is difficult to reverse. For example, if a hash function is used, then it will not be possible to automatically generate an example giving the desired hash code value.

In this case, you can add an additional parameter to the input object, which represents the result of the function calculation, replace the function call with a call to this parameter, and update this parameter, regardless of the violation of the functional connection:

 if(sha(object.field1)=="a9403...") ... //     ==> if(object.sha_field1 == "a9403...") ... 

An additional parameter allows to ensure the execution of code inside a branch, but, obviously, it can lead to actually incorrect results. That is, the program being tested will produce results that can never be observed in reality. Nevertheless, verification of a part of the code that is otherwise unavailable to us is still useful and can be considered as a type of unit testing. After all, during unit testing, the subfunction is called with such arguments that may never be used in the program.

With such manipulations, we replace (replace) the test object. However, in a sense, the newly built program includes the logic of the old program. Indeed, if as the values ​​of the new artificial parameters we take the results of the calculation of the functions that we replaced with the parameters, then the program will produce the same results. Apparently, testing a modified program may still be of interest. It is only necessary to remember under what conditions the changed program will behave in the same way as the original one.

Dependent conditions

, . , , , . , . (, , x > 0 , — x <= 1 . , — (-∞, 0] , (0, 1] , (1, +∞) , — .)

, , , true false . , , " " .

, , :

 if(x > 0) if(y > 0) if (y > x) 

( > 0 , — y > x .)
"", , , , , . , " " .
, "", ( y == x + 1 ), , .
"" ( y > x + 1 && y < x + 2 ), , .

, , - , "c " ( Symbolic Execution , ), . ( field1 = field1_initial_value ). , . :

 val a = field1 + 10 //    a = field_initial_value + 10 val b = a * 3 //    b = 3 * field_initial_value + 30 

— true false . . . For example,

 if(a > 0) A else B //   A ,  field_initial_value + 10 > 0 //   B ,  field_initial_value + 10 <= 0 

, , , , . , (, , ).

. , , . , . , .

, . . , , . , , , . , , , , , ?

Y- ( " " , stackoverflow:What is a Y-combinator? (2- ) , habr: Y- 7 ). , . ( , , .) . , . , "" . Y- " " ( ).

( ). , . , . , . , , , TestCase '. , , ( throw Nothing bottom , ). .

, . . , , . , . , , . , , , , . , . , .

, , , , 100% . , , . Hm . , , , ? , , - .

:

1. .
2. ( ).
3. , .
4. , .

, , . -, , , , . -, , , ( , ), , , "" . / , .

Conclusion

" " " ". , , , , . , .

, , , , . -, , ( ), . -, -, . DSL, , . -, , . -, , ( , , ). .

, , . , , - .

Thanks

@mneychev .