Based on the technique for nding errors in new object intents a method of debugging source code is presented. This method is capable of nding strict implicative dependencies between lines of source code covered in successful and failed runs. The output is a logical expression. Using the new method it is possible to come closer to debugging programs on a logical level not checking executions line by line. An example of applying the new method is presented. Possibilities of further development are discussed.
Automatic debugging is not a new topic in science and is investigated by many
computer scientist. For example, in [
In this work we use recent advance in Formal Concept Analysis in an attempt to nd logical dependencies between fails and successful runs of a program. For example, it could be that as long as a particular part of \if" statement is not covered during the program run (i.e. a particular conditional clause is not satis ed) the program runs successfully; this would mean that a bug lies probably in this particular part of the program.
Implications which can be derived from data tables (formal context) represent strong logical dependencies between attributes. We use this advantage of implications to introduce a way of debugging program code following the logic of a program.
Several studies were performed to discover the possibilities of using Formal
Concept Analysis in software development. For example, in [17] and [
In our previous work [
After that we present a method of debugging based on the discussed above technique of nding errors in data. We provide an example and discuss the possibilities of further development. 2
In what follows we keep to standard de nitions of FCA [
The set G is called a set of objects. The set M is called a set of attributes.
Consider mappings ' : 2G ! 2M and : 2M ! 2G: '(X) := fm 2 M j gIm for all g 2 Xg; (A) := fg 2 G j gIm for all m 2 Ag: Mappings ' and de ne a Galois connection between (2G; ) and (2M ; ), i.e. '(X) A , (A) X. Hence, for any X1; X2 G, A1; A2 M one has Usually, instead of ' and a single notation ( )0 is used. ( )0 is usually called a derivation operator. For X G the set X0 is called the intent of X. Similarly, for A M the set A0 is called the extent of A.
Let Z M or Z G. (Z)00 is called the closure of Z in K. Applying Properties 1 and 2 consequently one gets the monotonicity property: for any Z1; Z2 G or Z1; Z2 M one has Z1 Z2 ) Z100 Z200.
Let m 2 M; X G, then m is called a negated attribute. m 2 X0 whenever no x 2 X satis es xIm. Let A M ; A X0 i all m 2 A satisfy m 2 X0.
An implication of K := (G; M; I) is de ned as a pair (A; B), written A ! B, where A; B M . A is called the premise, B is called the conclusion of the implication A ! B. The implication A ! B is respected by a set of attributes N if A * N or B N . The implication A ! B holds (is valid) in K if it is respected by all g0, g 2 G, i.e. every object, that has all the attributes from A, also has all the attributes from B. Implications satisfy Armstrong rules : A ! A ;
A ! B A [ C ! B ;
A ! B; B [ C ! D
A [ C ! D A support of an implication in context K is the set of all objects of K, whose intents contain the premise and the conclusion of the implication. A unit implications is de ned as an implication with only one attribute in the conclusion, i.e. A ! b, where A M; b 2 M . Every implication A ! B can be regarded as the set of unit implications fA ! b j b 2 Bg. One can always observe only unit implications without loss of generality.
An implication basis of a context K is de ned as a set L of implications of K, from which any valid implication for K can be deduced by the Armstrong rules and none of the proper subsets of L has this property.
A minimal implication basis is an implication basis minimal in the number of
implications. A minimal implication basis was de ned in [
We say that an object g is reducible in a context K := (G; M; I) i 9X G : g0 = T j0.
j2X
All sets and contexts we consider in this paper are assumed to be nite. 3
In this section we use the idea of data domain dependency. Usually objects and attributes of a context represent entities. Dependencies may hold on attributes of such entities. However, such dependencies may not be implications of a context as a result of an error in object intents. Thereby, data domain dependencies are such rules that hold on data represented by objects in a context, but may erroneously be not valid implications of a context.
Every object in a context is described by its intent. In the data domain there may exist dependencies between attributes. In this work we consider only dependencies that do not have negations of attributes in premises. As mentioned above there is no need to specially observe non-unit implications. In this work we try to nd the algorithm to reveal the following two most simple and common types of dependencies (A M; b; c 2 M ): 1. If there is A in an object intent, there is also b, which is represented by the implication A ! b 2. If there is A in an object intent, there is no b, which can be symbolically represented as A ! b If we have no errors in a context, all the dependencies of Type 1 are deducible from implication basis. However, if we have not yet added enough objects in the context, we may get false consequence. Nevertheless, it is guaranteed that none of valid dependencies is lost, and, as we add objects without errors we reduce the number of false consequences from the implication basis.
The situation is di erent if we add an erroneous object. It may violate a dependency valid in the data domain. In this case, until we nd and correct the error, we are not able to deduce all dependencies valid in the data domain from the implication basis, no matter how many correct objects we add afterwards.
We aim to restore valid dependencies and therefore correct errors.
Below we assume that we are given a context (possibly empty) with correct data and a number of new object intents that may contain errors. This data is taken from some data domain and we may ask an expert whose answers are always correct. However, we should ask as few questions as possible.
We quickly recall two di erent approaches to nding errors introduced in our previous works. The rst one is based on inspecting the canonical basis of a context. When adding a new object to the context one may nd all implications from the canonical basis of the context such that the implications are not respected by the intent of the new object. These implications are then output as questions to an expert in form of unit implications. If at least one of these implications is accepted, the object intent is erroneous. Since the canonical basis is the most compact (in the number of implications) representation of all valid implications of a context, it is guaranteed that the minimal number of questions is asked and no valid dependencies of Type 1 are left out.
Although this approach allows one to reveal all dependencies of Type 1, there
are several issues. The problem of producing the canonical basis with known
algorithms is intractable. Recent theoretical results suggest that the canonical
base can hardly be computed even with polynomial delay ([
However, since we are only interested in implications corresponding to an object, it may be not necessary to compute a whole implication basis. Here is the second approach. Let A M be the intent of the new object not yet added to the context. m 2 A00 i 8g 2 G : A g0 ) m 2 g0, in other words, A00 contains the attributes common to all object intents containing A. The set of unit implications fA ! b j b 2 A00 n Ag can then be shown to the expert. If all implications are rejected, no attributes are forgotten in the new object intent. Otherwise, the object is erroneous. This approach allows one to nd errors of Type 1.
However, the following case is possible. Let A M be the intent of the new object such that @g 2 G : A g0. In this case A00 = M and the implication A ! A00 n A has empty support. This may indicate an error of Type 2, because the object intent contains a combination of attributes impossible in the data domain, but the object may be correct as well. An expert could be asked if the combination of attributes in the object intent is consistent in the data domain. For such a question the information already input in the context is not used. More than that, this question is not su cient to reveal an error of Type 1. Proposition 1. Let K = (G; M; I); A
M . The set
IA = fB ! d j B 2 MCA; d 2 B00 n A [ A n Bg; where MCA = fB 2 CAj@C 2 CA : B Cg and CA = fA \ g0 j g 2 Gg, is the set of all unit implications (or their non-trivial consequences with some attributes added in the premise) of Types 1 and 2 such that implications are valid in K, not respected by A, and have not empty support.
Proposition 1 allows one to nd an algorithm for computing the set of questions to an expert revealing possible errors of Types 1 and 2. The pseudocode is pretty straightforward and is not shown here for the sake of compactness.
Since computing the closure of a subset of attributes takes O(jGj jM j) time in the worst case, and we need to compute respective closures for every object in the context, the time complexity of the whole algorithm is O(jGj2 jM j).
We may now conclude that we are able to nd possibly broken dependencies of two most common types in new objects. However, this does not always indicate broken real dependency, as we not always have enough information already input in our context. That is why we may only develop a hypothesis and ask an expert if it holds.
For more details, example, and the proof of Proposition 1, please, refer to
[
Normally debugging starts with a failure report. Such a report contains the input on which the program failed. By this we mean that our program was not able to output the expected result or did not nish at all. This implicitly de nes \goal" function which is capable of determining either a program run was successful or not. We could imagine a case where we do not have any successful inputs, i.e. those inputs which were processed successfully by the program. However, it does not seem reasonable. In a such a case the best option seems to rewrite the code or look for obvious mistakes. Modern techniques of software development suggest running tests even before writing code itself; unless the tests are passed code is not considered nished. Therefore, successful inputs are at least those contained in the test suites.
As discussed in the beginning of this paper the problem of nding appropriate inputs was considered by di erent authors. This problem is indeed of essential importance for debugging. However, we do not aim at solving it. Instead we assume that inputs are already found (using user reports, random generator, or something else), processed (it is better if inputs are minimized, however, not necessary), and are at hands. We focus on processing the program runs on given inputs.
Our method consists in the following. We construct two contexts: rst with successful runs as objects, second with failed runs. In both cases attributes are the lines of the code (conveniently presented via line numbers). We put a cross if during the processing of the input the program has covered the corresponding line. So in both cases we record the information about covered lines during the processing of the inputs. After the contexts are ready we treat all the objects from the context with failed runs as new objects and try to nd errors as described in the previous sections. Expected output is implication of the form A ! B. The interpretation is as follows: in successful runs whenever lines A are covered, lines B are covered as well. However, in the inspected failed run lines A were covered and lines B were not covered. Debugging consists now in nding the reason why lines B were not covered in the processing of the failed run.
This is not absolutely automatic debugging, however, we receive some more clues and may nd a bug without checking the written code line by line. More than that, this method is logically strict, it does not deal with any kind of probability. This corresponds to the real situation: the bug is or is not there, not with any probability. 4.2
Consider the following function written in Python (example taken from [18]):
Listing 1.1: remove html markup [18] 1 def remove html markup ( s ) : 2 t a g = F a l s e 3 q u o t e = F a l s e 4 out = " " 5 f o r c in s : 6 i f ( c == '< ' and 7 not q u o t e ) : 8 t a g = True 9 e l i f ( c == '> ' and 10 not q u o t e ) : 11 t a g = F a l s e 12 e l i f ( c == ' " ' or 13 c == " ' " and 14 t a g ) : 15 q u o t e = not q u o t e 16 e l i f not t a g : 17 out = out + c 18 return out
The goal of the function, as follows from its name, is to remove html markup from the input, no matter if it occurs inside or outside quotes. Therefore, we may formulate our goal as: no < in output. Such a formulation does not allow us to catch all the bugs (as seen from the contexts below the input "foo" has enabled the program to reach the line 15 which should not have happened, but it is considered as a successful run), but it su ces for our purposes.
The function works as follows. After initialisation we have four \if" cases. The rst and the second one checks if we have encountered a tag symbol outside of quotes. If so, the value of \tag" is changed. The third one checks if we have encountered a quote symbol inside tag. This is important for not closing a tag if the closing symbol happens to be in one of the parameters (see inputs). If so, the value of \quote" is changed. The last \if" adds the current character to the output if we are outside the tag.
We consider the following set of inputs: foo, <b>foo</b>, "<b>foo</b>", "<b>a</b>", "<b></b>", "<>", "foo", 'foo', <em>foo</em>, "", <"">, <p>, <a href=">">foo</a>
We run the function on every input and check if the output contains the symbol \<". If it does not, the run was successful. We also record the lines coverage during every run, gather this information, and construct two context:
It is easy to notice that in the processing of every failed input the same lines are covered. Therefore, the only di erence between di erent objects in the context with failed runs is the names of the objects.
Inspecting any of the failed inputs in the context with successful runs using the described above technique for nding errors yields the following implication: 7; 13; 15 ! 8; 11
What is essentially said is the following: in a successful run if the lines 7, 13, and 15 were covered then the lines 8 and 11 were also covered; in every failed run the lines 7, 13, and 15 were covered, but the lines 8 and 11 were not covered. We now expect the mentioned above lines and their impact to the program run.
If the line 7 is covered then the condition in the line 6 was met. Therefore, the line 7 is covered whenever there is the symbol \<" in the input.
If the line 13 is covered then the condition in the line 12 was not met and the conditions of the rst two \if" clauses were not met. This means that for some symbol from the input we should not change the value of \tag" and the symbol is not \"".
If the line 15 was covered then the condition of the third \if" clause was met and the conditions of the rst two \if" clauses were not met. Therefore, some symbol in the input was either \"" or \'" and the \tag" was set to True.
If the line 8 was not covered then the value of \tag" was never set to True (because we do not have this variable set to True elsewhere in our program and originally it is initialized to False). There is no need to go further to the line 11 in our investigation, because we have already found a contradiction. The value of \tag" should have been set to True to reach the line 15, but it was never set to True. From this we can deduce that possibly the condition of the third \if" clause erroneously evaluates to True without checking that \tag" equals True.
The key to this puzzle is the following. In Python as well as in many other languages logical operation \and" has a higher priority than \or", so condition of the third \if" (c == '"' or c == "'" and tag) is implicitly transformed in (c == '"' or (c == "'" and tag)). In other words on lines 12 and 13 brackets are forgotten. After debugging the condition should look as follows: ((c == '"' or c == "'") and tag) and the program runs correctly. 4.3
The sequence in which the lines of code were covered contains even more information about the execution of a program. This information may reveal even more dependencies in the working ow of a program. It may also happen that the only di erence between successful and failed runs is in the sequence in which the lines are covered, whereas the set of covered lines remains the same. In this manner we also take into account the sequential aspect of the loop that is not taken into account in the previous example.
It is not di cult to extend the introduced method with this new feature. For this purpose we change the attributes of our context. Now an attribute contains two numbers: the rst number corresponds to the preceding covered line and the second number corresponds to the succeeding covered line. The information from the original modi cation of the method may still be captured with attributes that have the same line number two times. However, we may be not interested in the absolute precedence relation between the lines, because this information is excessive and di cult to interpret while the size of the set of attributes increases dramatically. That is why we also introduce a new parameter containing information about the delay of interest. Below we are only interested in the precedence relation within this delay, i.e. not more than the dealy number of lines should be covered between the two speci ed lines in order to add them to the relation I.
The number of attributes for this case, assuming that any line may precede and succeed any other line including itself, is jM jd, where d is the delay.
Unfortunately, the result obtained using this modi cation may be di cult to interpret even if the delay is small. It makes sense to consider this modi cation only if the standard modi cation does not yield any results.
For the remove_html_markup function and d = 1 we obtain the following results: 1. (10; 10); (12; 15) ! (8; 8); (11; 11); (10; 11); (11; 5); (9; 10); (7; 8); (17; 17); (9; 12); (15; 5); (13; 13); (13; 16); (16; 16); (16; 17); 2. (17; 17); (15; 5) ! (10; 10); (7; 7); 3. (13; 13); (15; 15); (7; 7) ! (9; 12); (16; 17); (12; 15); (15; 5);
(8; 8); (11; 11); (10; 11); (11; 5); (9; 10); (7; 8); (12; 13).
In the result we still have the same obtained dependency as we had before, namely Implication 3. However, we have two more obtained results that reveal more structural features of the bug. An interpretation of this result is left to the reader.
For example, we consider Implication 1. Actually already in the premise of this implication we can recognize a clue to nding the bug. Indeed, having a pair 12 and 15 with delay 1 means the following: after the line 12 the execution jumped to the line 15. After checking only condition in the line 12 (which happened to be true) execution jumped to the consequence. As already described, the interpreter has understood the condition as a disjunction and has only evaluated the rst expression (which would be enough in case of disjunction). 5
Based on the procedure for nding errors in new object intents a method of debugging source code was proposed. This method nds strict dependencies between source code coverage in successful and failed runs. The output of the debugging method is a logical expression which allows one to nd bugs following the implicit logic of the program. Further modi cation of the method is possible (described above), however, it leads to results that are di cult to interpret. Acknowledgements The author was supported by German Academic Exchange Service (DAAD).
Author thanks Sergei Kuznetsov and other participants of the project Mathematical Models, Algorithms, and Software Tools for Intelligent Analysis of Structural and Textual Data supported by the Basic Research Program of the National Research University Higher School of Economics for discussion and useful remarks. 17. Gregor Snelting and Frank Tip. Reengineering class hierarchies using concept analysis. SIGSOFT Softw. Eng. Notes, 23(6):99{110, November 1998. 18. Andreas Zeller. Software debugging course.
https://www.udacity.com/course/cs259. 19. Andreas Zeller and Ralf Hildebrandt. Simplifying and isolating failure-inducing input. IEEE Trans. Software Eng., 28(2):183{200, 2002.