Is It Me or is the Source Comparison Page Rigged?

[bob]

yes there is non-equivalent code. But in a large program, one expects to find very little semantically equivalent code. That is the issue. Do you actually believe that in writing a 44,000 line program, that I will by pure chance duplicate what others have done _exactly_ here and there? when I don't even see this happen in 100-1000 line student programs???

I read things like these and I can only wonder if we are talking about the same things. We are talking about the UCI parser -- that has nowhere near 44 000 lines of code, more like 100-150, and their purpose is by design extremely similar to nearly identical. Of course you should expect similarities in such a procedure.

I also note that Robert sometimes says something with which I agree, but then adds that I should "go read" something to see that it is true.

There is a lot of mis-communication taking place -- I'm not going to participate in all these post and my lack of participation should not be taken as either agreement or disagreement.

Alex, is it too much to ask that you follow the entire discussion before making statements that simply do not belong? "go_parser()" is not the _only_ thing being looked at. It was the _first_ thing. when you disassemble something you have to start near the main() entry point and work your way out from there. So this was the _first_ place where the similarity was discovered. It was not the last. There are more to come.

The problem right now, is that the small group that are looking at this are just going in the order that the program dictates. I have already asked Chris to give some idea of what he would consider reasonable evidence. What function(s). What kind of data. Etc. He is not happy with what has been presented so far. But I doubt he will offer any specific data he would accept, because I don't believe there is any. So the group has a "natural order" for analysis, and that seems to be unacceptable. There are only two choices... (1) wait until they find something everyone agrees is suspicious; or (2) direct their analysis by telling them what they should look at. Right now all that is being written is "that is not evidence", "that is not core AI", and so forth. No helpful suggestions, just cries of "this can't be..." "this is faked"... "this is dishonest"... "this is misleading..." and so forth, repeated ad nauseum.

[chrisw]

I've tried to follow this scientific discussion about methodology of research.
I can guess John Sidles and Alex K. are mostly worried about that translated code of Rybka is not exactly the same as the original code of Rybka. They are insisting on view that translated code can not be exactly the same as the original source code so from the results of comparision can not be drawn any valid (by scientific means) conclusions.
Have I got it right?

Well, they're saying several things.

The Go Parser has, by force, to carry out several operations to parse the input text string. The input text string contains words from a restricted list of word, such as "infinite" or "ponder". The Go Parser parses the text and sets variables for the engine to tell it what it to, again forced.

Go Parser must carry out operations A,B,C,D,E,F,G,H and it must leave the results of its parse in variables, call them a,b,c,d,e,f,g,h

Operation A might be comparestrings("infinite", inputstring); if true, set variable a.

Operation A's across a range of programs doing Go Parser will be semantically identical usually. Likewise B,C,D,E,F,G,H. No reason why not. Too trivial for anything else.

Fruit does them in order ABCDEFGH, declaring variables abcdefgh
Rybka does them in order BDCEFGHA, declaring variable dcbfghab
Even Zach's ZCT does them, slightly differently, but basically if you look at his code, there they are. "infinite", "ponder" etc. Has to be so.
Each program has its own idiosyncracities in addition, some more so, some less so.

We have Go Parsers, all doing the same thing, by force, and composed of sub-components also doing the same things by force. The sub-components being so trivial and so forced that they are reasonably likely to be semantically identical. Not always, not necessarily, but usually.

The main likely differences are in the ordering of it all. It matters not very much what order the parsing is donea nd the variable filled.

It's mostly in the ordering that differences between program writers will emerge. With some differences in style. Some differences in variable type. Some differences in initial values. All of these differences we see in the Rybka and Fruit code.

What the antis did was to take the ordering, both of variables and program flow and make them identical. They converted Rybka's BDCEFGHA to be identical to Fruit's ABCDEFGH, didnt reveal that they'ld done this, implying that the Rybka source was just a natural disassembly and misled the forum and the computer chess community in order to cause damage to Vas and Rybka.

The Go Parser evidence is completely busted. If this was a court case and this information of misleading by hidden manipulation of evidential data revealed part way through the case, the prosection barristers would resign and the judge would throw the case out. With costs.

So you in general do not challenge the results of the experiment but has different explanation of them. Do I understand it right?

Here is a good question for Chris. He dislikes the "go_parser" analysis. OK. What _would_ he need to see to begin to have doubts, then the group that are looking at this can focus precisely on what he thinks is necessary to offer acceptable evidence. Evaluation is a part of the code where duplication is inconceivable. So how about the evaluation constants? Would a long list of duplicate numbers be significant? What about a list of identical positional ideas using similar (can't be identical here since A is mailbox, B is bitboard) positional concepts? Or maybe something easier to find like identical data structures, or identical hash implementations? Or identical approaches to ordering moves, including 'quirks" that do not appear in other programs?

Exactly what would be considered acceptable proof? I suspect there is _nothing_ that would be accepted myself, just another one of those things that make you go hmmm...

Am I right to intuit you just consigned the go_parser disassembly to the dustbin of history

Make your case, if there is one. It will be apparent if the forum accepts it or not after you've made it and others have had a chance to unpick it. Will it be a good case? We'll see ....

[bob]

I've tried to follow this scientific discussion about methodology of research.
I can guess John Sidles and Alex K. are mostly worried about that translated code of Rybka is not exactly the same as the original code of Rybka. They are insisting on view that translated code can not be exactly the same as the original source code so from the results of comparision can not be drawn any valid (by scientific means) conclusions.
Have I got it right?

No, you have not. It is perfectly true that the compiler adds a layer of uncertainty by changing the code around -- that's just part of the picture though. The real point is that a certain degree of similarity in not unlikely in programs that are short, simple and need to provide extremely similar if not identical output.

OK. but we are talking about chess programs. My program (crafty) currently has 44,864 lines of code. That is hardly "small". the final part about "similar output" is meaningless. We have so many ways to search trees, so many ways to extend and reduce, so many ways to order the moves to make the search more efficient, a nearly limitless number of ways to turn a position into a numeric value that can be passed thru the search to find the best move, that this point is simply meaningless. Finding semantically equivalent code can happen on two levels. Nobody cares about tiny pieces of code such as PopCnt(), LSB(), MSB() and the like. But when you get into procedures that are hundreds of lines long, big chunks of semantically identical code leads to but one conclusion. Again, for a given algorithm, there are an infinite number of ways syntactically to express it. So duplication is _highly_ improbable. And that is the basis that caused a couple of people to start to look at this more closely. It is simply so improbable unless code was physically copied.

The actual source comparison shows some similarities but also lots of dissimilarities -- which is what is to be expected.

Partially true. There will necessarily be parts of the code that are different, since program B (supposedly derived from A) is significantly stronger. But chunks of duplicated code is _not_ normal in any program of more than a few lines. So that concept I do not agree with.

But if you see 10 or 15 variables which are initialized in the same order in machine code, then despite the changes made by the compiler, something is fishy -- not necessarily conclusive, but fishy.

Agreed. And if they are all initialized, even if _not_ in the same order, it is _still_ fishy In fact, the compiler could change that order for other reasons if it wanted to For example, it is more efficient to initialize things in the order they appear in memory to take advantage of cache prefetching. And if you are trying to de-compile, you see the final order, not the programmed order, and rearranging makes perfect sense when trying to match things up.

It turns out though, that the order of variable initialization was faked to make the code look more similar than the disassembler made it look -- the same goes for the order in which various "if" clauses are checked. So there is really nothing fishy in the code regarding the order.

EXTREMELY poor choice of wording with "faked". Nothing being done in this investigation is "faked". If you want to use words that are inflammatory or accusatory, feel free. But don't expect much in the way of discussion if that is the way you want to proceed. Get some experience or knowledge about the field and you will see how wrong "faked" is.

There is plenty of semantic non-equivalent code, and what similarity there is, is mostly about the general structure of the program -- making allowance for the fact that even in the structure there are dissimilarities.

again, that is baloney. yes there is non-equivalent code. But in a large program, one expects to find very little semantically equivalent code. That is the issue. Do you actually believe that in writing a 44,000 line program, that I will by pure chance duplicate what others have done _exactly_ here and there? when I don't even see this happen in 100-1000 line student programs???

The situation with your students is different because one student does not study the work of another student.

Uri

That has to be the single most naive statement I have ever read. I asked another faculty member his opinion, and his reply was "what planet is _this_ guy from?" that pretty much says it all. Fraternities have copies of every test I have ever given, every assignment I have given and member's papers that go with them. Foreign students have the same sort of "underground". That is why I keep old assignments.

It is _really_ time to get serious here and stop that kind of nonsensical remark. Again, talk to _anybody_ that works in a University CS department. This is a problem _everywhere_.

[bob]

Or perhaps it might destroy the credibility of the greatest detractor, when he keeps making statements that every computer scientist on the planet knows is nonsense.

"secret". "dishonest". "misleading". All words you have used, to explain a process that you should instead have called "mysterious" because you don't have a clue how it is carried out. Sadly...

[bob]

Fine. you are unable to follow the discussion.

Baseless assertion, followed by verbiage.

Aha. so you do _not_ understand "semantical equivalence". This is simply proving that for the same inputs, the two pieces of code produce the same output. "

Then the Rybka code and the Fruit code are not semantically equivalent -- there are plenty of differences in their outcome for the same input.

But of course, that's not what you mean. You mean that you should get to ignore differences --including semantic non-equivalence-- and focus only on what you find similar.

Order is immaterial so long as changes do not violate data depenencies, name dependencies or control dependencies.

Order makes the source codes look much more similar that they really are. If ten variables in a row are initialized in the same order in machine code then that's alarming. Having variables initialized all over the place, and many of them nonexistent is not at all alarming.

Changing the order without saying so is at best sneaky, at worst dishonest.

It is worth going back to the first presentation of the misleading source comparison data, the "Here's something to start with" thread ....

Norman Schmidt explains the "methodology", with absolutely no mention at all of any reordering of either variable or program flow. No mention of "semantics".

Norman wrote:
Please note that: Fruits ASSERTs have been removed comments have been removed there are differences between the two...mainly: where Fruit has TRUE, Rybka has 1 where Fruit has FALSE, Rybka has 0
where Fruit has double data types, Rybka uses integer
search->info struct has been replaced with a direct reference to the independant variable.
truthfully many of the differences reflect the implementation of backend C bitboard routines in place of object-oriented C++ class references
Fruit often does error checking that is absent in Rybka,
if (ptr == NULL) my_fatal("parse_go(): missing argument\n");
Another difference:
Fruit calls string_equal to accept input, whereas Rybka uses the C function:
int strcmp( const char *string1, const char *string2 )
but these functions are essentially equivilent...
string_equal is simply a Fabien re-write with ASSERTs included:
string_equal( const char s1 [], const char s2 [] )
{
ASSERT(s1 != NULL);
ASSERT(s2 != NULL);
return strcmp(s1, s2) == 0;
}
which is something he did often...see Fruit 2.1 util.cpp
one click...a global search and replace (for ex: replace true with 1, would recifiy some of the larger differences).

Sven Schule challenged on the variable ordering:

Sven wrote:
since you don't have the Rybka source, how can you know about the location and order of variable declarations in Rybka? Declarations of local variables often do not produce assembler code, you just see the variables when they are used.

Hyatt replied without any reference to the creative reordering that had been done:

Bob wrote:
If you look at the order of the variables as they either appear in memory or on the stack, you can almost infer the order they were declared.

And Alexander Schmidt was convinced:

Alexander wrote:
TY Norman, this is completely convincing. I have not much programming experience (mainly vba) but this are too many similaries for a coincidence.
Unfortunately people will not read it and not believe it...

And Christophe Theron remained absolutely silent on the creative reordering:

Christophe wrote:
Nothing at all.

Can we possibly use the _same_ vocabulary here, which includes the definition of words.

We have a set of sticks in pile A that are colored, where each stick is a different color. We have a second set of sticks and have been asked to answer the question "are the sticks in pile B identical to the sticks in pile A".

Of course your sets of sticks match. They're the necessary and forced sub-components of the Go Parser.

And that is where you keep stepping right into the "trap". "go_parser()" is not explicitly defined. There are optional commands you can ignore. There is optional data you can choose to provide or omit. You overlook that minor detail. It isn't like a sqrt() function. Even the _way_ you parse has lots of flexibility.

[bob]

No, I use solid knowledge to _enumerate_ the possibilities.

No, you don't -- there is no enumeration going on -- just the presentation of a single source, a presentation tilted heavily towards proving rather than disproving your case.

Again, lack of experience is leading to lack of communication. I have a string I want to match with a regular expression that I believe produced the string. this _is_ an enumeration process. I use the regexp to enumerate the possibilities and compare them. If I am intelligent, I can avoid a _full_ enumeration by matching bits and pieces to anchor the string at certain points, and then try to "fill in the gaps" which is easier. but it is simply an enumeration. Assembly language to C is not exactly one-to-one. The assembly language instruction set leaves some options for how to do things. Ditto for C. And in C there are multiple ways to write different source that produces the same assembly language output. And _that_ is the enumeration I am talking about. I have no idea what you are talking about however.'

Not only do you not try to avoid it -- but you think that it is good methodology to chose exactly the code reconstruction that justifies your hunch!

correct...

Then you are simply not a reliable source when it comes to objectively analyzing the similarities between two sources -- your technical expertise not-withstanding. But at least you're honest about it.

I am interested only in the original postulate, "Program B was derived from program A." In order to prove that, they need to prove that parts of B can be found in A. Parts will not be there as well, and that is expected. But the issue is to prove that parts are there. Nothing more, nothing less. All this stuff about proving vs disproving and so forth is leading away from the base discussion.

I know how to discover plagiarism. So do thousands of others. It is done daily. All done the same way.

[bob]

I've tried to follow this scientific discussion about methodology of research.
I can guess John Sidles and Alex K. are mostly worried about that translated code of Rybka is not exactly the same as the original code of Rybka. They are insisting on view that translated code can not be exactly the same as the original source code so from the results of comparision can not be drawn any valid (by scientific means) conclusions.
Have I got it right?

Well, they're saying several things.

The Go Parser has, by force, to carry out several operations to parse the input text string. The input text string contains words from a restricted list of word, such as "infinite" or "ponder". The Go Parser parses the text and sets variables for the engine to tell it what it to, again forced.

Go Parser must carry out operations A,B,C,D,E,F,G,H and it must leave the results of its parse in variables, call them a,b,c,d,e,f,g,h

Operation A might be comparestrings("infinite", inputstring); if true, set variable a.

Operation A's across a range of programs doing Go Parser will be semantically identical usually. Likewise B,C,D,E,F,G,H. No reason why not. Too trivial for anything else.

Fruit does them in order ABCDEFGH, declaring variables abcdefgh
Rybka does them in order BDCEFGHA, declaring variable dcbfghab
Even Zach's ZCT does them, slightly differently, but basically if you look at his code, there they are. "infinite", "ponder" etc. Has to be so.
Each program has its own idiosyncracities in addition, some more so, some less so.

We have Go Parsers, all doing the same thing, by force, and composed of sub-components also doing the same things by force. The sub-components being so trivial and so forced that they are reasonably likely to be semantically identical. Not always, not necessarily, but usually.

The main likely differences are in the ordering of it all. It matters not very much what order the parsing is donea nd the variable filled.

It's mostly in the ordering that differences between program writers will emerge. With some differences in style. Some differences in variable type. Some differences in initial values. All of these differences we see in the Rybka and Fruit code.

What the antis did was to take the ordering, both of variables and program flow and make them identical. They converted Rybka's BDCEFGHA to be identical to Fruit's ABCDEFGH, didnt reveal that they'ld done this, implying that the Rybka source was just a natural disassembly and misled the forum and the computer chess community in order to cause damage to Vas and Rybka.

The Go Parser evidence is completely busted. If this was a court case and this information of misleading by hidden manipulation of evidential data revealed part way through the case, the prosection barristers would resign and the judge would throw the case out. With costs.

So you in general do not challenge the results of the experiment but has different explanation of them. Do I understand it right?

Here is a good question for Chris. He dislikes the "go_parser" analysis. OK. What _would_ he need to see to begin to have doubts, then the group that are looking at this can focus precisely on what he thinks is necessary to offer acceptable evidence. Evaluation is a part of the code where duplication is inconceivable. So how about the evaluation constants? Would a long list of duplicate numbers be significant? What about a list of identical positional ideas using similar (can't be identical here since A is mailbox, B is bitboard) positional concepts? Or maybe something easier to find like identical data structures, or identical hash implementations? Or identical approaches to ordering moves, including 'quirks" that do not appear in other programs?

Exactly what would be considered acceptable proof? I suspect there is _nothing_ that would be accepted myself, just another one of those things that make you go hmmm...

Am I right to intuit you just consigned the go_parser disassembly to the dustbin of history

Make your case, if there is one. It will be apparent if the forum accepts it or not after you've made it and others have had a chance to unpick it. Will it be a good case? We'll see ....

No. You are not right to intuit that. You could intuit that I have become convinced that _you_ are not going to accept that similarity level as anything but coincidental. I consider the probability for such duplication to be _very_ low. .

I simply asked the question, "what would be convincing?" I really didn't expect an answer, although the question was not a rhetorical one. Let them work their way thru this. Perhaps go_parser() is the only function that is similar. Perhaps not. Based on my experience, if one module is similar, there are going to be others. we will see.

[John]

"... I know how to discover plagiarism. So do thousands of others. It is done daily. All done the same way...."

Yes it is. And that way is "Show me your source code." But the present case is completely different, isn't it? Because modern optimizing compilers scrub away the idiosyncratic human traits that teachers (and automated tools too) use to detect plagiarism.

To the best of my knowledge, there are no peer-reviewed accounts, and no automated tools, and few or no people with professional experience, relating to the machine-code detection methods being discussed here on the CCC.

That is not to say that such detection is not possible. But it would be exceedingly difficult---many orders of magnitude more difficult than showing classroom plagiarism via source code comparisons. Even a long list of identical numerical coefficients would *not* constitute evidence of plagiarism, because it is neither illegal nor immoral to copy algorithms.

To assert otherwise, would imply that the On-Line Encyclopedia of Integer Sequences is evidence of a massive global conspiracy of plagiarism among mathematicians ... hmmm ... wait a minute ... who *are* these mathematicians? ... what is their motive in setting up their web site? ... maybe they *are* plagiarizing one another?

It is remarkable how avidly the human mind embraces conspiracy-based explanations. Careful protocol design helps guard against this.

[bob]

"... I know how to discover plagiarism. So do thousands of others. It is done daily. All done the same way...."

Yes it is. And that way is "Show me your source code." But the present case is completely different, isn't it? Because modern optimizing compilers scrub away the idiosyncratic human traits that teachers (and automated tools too) use to detect plagiarism.

To the best of my knowledge, there are no peer-reviewed accounts, and no automated tools, and few or no people with professional experience, relating to the machine-code detection methods being discussed here on the CCC.

I do not know about peer-reviewed articles. The people that do this do so in private to detect copyright/patent infringements commercially. University types generally have both source programs where there are automated tools and peer-reviewed articles.

Doing things this way is not very common. But the approach is taught in my classes. we often use C code to produce assembly language programs. And I sometimes give assembly language programs and ask students to give me the C program it came from. machine language is harder still, and I don't use that in class more than once or twice when talking about symbol tables and such. But the ideas are hardly witchcraft and superstition.

That is not to say that such detection is not possible. But it would be exceedingly difficult---many orders of magnitude more difficult than showing classroom plagiarism via source code comparisons. Even a long list of identical numerical coefficients would *not* constitute evidence of plagiarism, because it is neither illegal nor immoral to copy algorithms.

I believe I have made that exact statement multiple times. It _is_ much harder. But for clarity "much harder" != "impossible". If you agree with my last sentence, then we are likely in complete agreement on this complete point.

To assert otherwise, would imply that the On-Line Encyclopedia of Integer Sequences is evidence of a massive global conspiracy of plagiarism among mathematicians ... hmmm ... wait a minute ... who *are* these mathematicians? ... what is their motive in setting up their web site? ... maybe they *are* plagiarizing one another?

It is remarkable how avidly the human mind embraces conspiracy-based explanations. Careful protocol design helps guard against this.

Couldn't say it better if I tried. The original post on this topic pointed out some unexpected similarities. 99% of the posts since have been about "conspiracy theories" and "ulterior motives"...

[glorfindel]

Changing the order without saying so is at best sneaky, at worst dishonest.

it is actually neither. Unless you consider your compiler and processor to be "sneaky or dishonest"...

That's pretty silly. I don't expect my compiler to try to make arguments and present evidence in a honest and straightforward manner -- I do expect that from human interlocutors, and it's clear that humans changed the code to make it look more similar than it is, without mentioning anything about it.

Alex, if somebody takes the source code of a program and starts switching variable names and starts moving lines of code up and down (while making sure those moves do not change anything significant), they will come up with a new file.c.
Do you know how little time it will take them, for this small piece of code we are talking about?
This transformation is trivial. It can even be done automatically, for crying out loud, without even opening a text editor to edit the file! If such a trivial transformation can fool you into believing that their program is not derived from the original source, imagine other transformations, like reorganising the code differently into files, taking code out of a function and placing it elsewhere, creating new functions etc. They could give you both programs' sources and you would still not recognize the fraud, because they would not be 'similar'.

So, coming to the examples you gave of "humans changing the code to make it look more similar than it is", the following two pieces of code

Code: Select all

depth = -1;
mate = -1;
nodes = -1;

infinite = false;
ponder = false;
movestogo = -1;
winc = -1.0;
wtime = -1.0;
binc = -1.0;
btime = -1.0;
movetime = -1.0; 

Code: Select all

infinite = false;
ponder = false;

depth = -1;
mate = -1;
movestogo = -1;

nodes = -1;

binc = -1.0;
btime = -1.0;
movetime = -1.0;
winc = -1.0;
wtime = -1.0; 

are not similar. They are the same. And the second piece is not a modified form of the first. It is the same.