Interpretation of matching fragments?

[tsieger]

Let me please ask for clarification of the colored matching fragments shown in the console.
My intuition was that there come selected fragments with some overlap (shown in green) in between the two sources under comparison.
In some cases, the overlaps are excellent and directly identify a shared piece of code. However, in other cases, the overlap is poor. I came across several weird cases, where a comment seemed to match with some real code (I would expect that you filter comments out?), or where a large piece of code (400 lines) matched just a line or two! (This often happens when using small values of the w parameter, but this could be just a coincidence).

Also, what does the X kgrams in the heading of each fragment refer to? Is it the number of all kgrams in the fragment, or the number of shared kgrams? Also, what is the relation between this number and the highlighted code (are they supposed to relate to each other?)?

Consider e.g. the following example with 1 kgrams (I'm using the default -k here):

                                                                                 Fragment 1321/1380: 1 kgrams

Tokens: 'null'

390             // cout << data[j] << " ";                                                    37              cycles += count_cycles(neighbors, visited, start, v, maxlen - 1);
391             combinationsVec.push_back(data[j]);                                           38          }
392         }                                                                                 39          if(!visited[v]) {
393         int temp = countFastServers();                                                    40              cycles++;
394         if (temp >= currentMaxOfFastServers)                                              41          }
395         {                                                                                 42          if(v == start) {
396             bfs(combinationsVec[0], temp);                                                43              cycles+=43;
397         }                                                                                 44          }
398         // cout << endl;                                                                  45      }

where part of lines 393-396 is highlighted in green on the left, and lines 40-43 are highlighted on the right.
Here I'm totally confused: what does 1 kgrams mean and what it relates to?
Why the highligted codes do not match?

Consider also another example with 10 kgrams:

                                                                                 Fragment 1367/1380: 10 kgrams

Tokens: 'null'

420        std::default_random_engine rng(seed);                                              95      }
421        std::shuffle(std::begin(orderedServers), std::end(orderedServers), rng);*/         96      int C2[N2][N2];
422     }                                                                                     97      for(int i = 0; i < N2; i++) {
423     for (int i = 0; i < N2; i++)                                                          98          for(int j = 0; j < N2; j++) {
424     {                                                                                     99              C2[i][j] = -1;
425         if (!fastServers[i])                                                              100         }
426         {                                                                                 101     }
427             orderedServers.push_back(i);

Here only line 423 and 98 match (this makes sense), but what is the meaning of the 10 kgrams here?

Thanks for clarification.

[rien]

The size of a fragment is expressed in kgrams (k subsequent tokens in the syntax tree) and this is also shown for each fragment. This means that on either size of the fragment, there are X kgrams with the same hash. How much actual tokens are matching is difficult to say, because we do not compare all kgrams in a file (we compare roughly only one kgram per window). If you desire more information about the algorithm: there is a description in our publication (let me know if you don't have access).

There are multiple reasons why matches can be off or look weird:

• We hash the kgrams, so there is a small posibility that two different kgrams actually are considered the same because of an accidental collision
• We match tokens in the syntax tree, so if for example a function declaration amtches (but not the body), Dolos will sometimes highlight the full function

If you pass the --compare flag with Dolos, it will show you the tokens that are actually matching instead of null. This does slow down the analysis a bit however. This will show you something like this:

 ../samples/javascript/copied_function.js                      ../samples/javascript/copy_of_sample.js

 Total overlap: 16 kgrams
 Similarity score: 0.15384615384615385


                                                   Fragment 1/1: 8 kgrams

Tokens: '(,identifier,),),(,statement_block,(,lexical_declaration,(,variable_declarator,(,identifier,),(,number,),),),(,for_
in_statement,(,identifier,),(,identifier,),(,statement_block,(,expression_statement,(,assignment_expression,(,identifier,),(
,subscript_expression,(,member_expression,(,this,),(,property_identifier,),),(,call_expression,(,member_expression,(,this,),
(,property_identifier,),),(,arguments,(,identifier,),(,call_expression,(,member_expression,(,identifier,),(,property_identif
ier,),),(,arguments,(,number,),),)'

1  /**                                                      12     this.combineer = combineer || ((h, v) => (h + v) %
                                                            256);
2   * This is a function copied from sample.js              13   }
3   */                                                      14
4  function hash(s) {                                       15   hash(s) {
5    let h = 0;                                             16     let h = 0;
6    for (let c of s) {                                     17     for (let c of s) {
7      h = this.tabel[this.combineer(h, c.charCodeAt(0))];  18       h = this.tabel[this.combineer(h, c.charCodeAt(0))];
8    }                                                      19     }
9    return h; 

Where each token is separated by a comma. Parentheses mean descending in the tree to a child ( and ascending in the tree to a parent ).

[tsieger]

Thanks for the explanation.
It would be great if you could share the paper - I don't have access to it (I've already asked for a full text on researchgate a few days ago, but got no response.) Thanks.