For C experts

[wgarvin]

I don't think you need any kind of "negative reference" when comparing the code, that would just mean a lot of extra work for little gain.

It's enough to compile with same compiler/settings and then look for fragments of assembly that are structurally very similar, and then figure out what kind of C snippets would generate something like that and decide if you've found something significant or not. Is the snippet something "unusual"? something extremely unlikely for another author to write by hand? Per Bob's example, if it exactly duplicates a very specific bug from an old version of Crafty, then that would be pretty suspicious. There's no reason for someone to write that code on purpose, and its very unlikely to be written again by anyone else by accident.

This is just like the map-makers who intentionally put small mistakes into their maps so that they can detect if their maps were copied by other vendors (except that bugs in early versions of Crafty were of course put there by accident, not on purpose.)

Finding something in another program that exactly reproduced a bug like that would be strong circumstantial evidence that the other program had copied that particular part of Crafty's source code. If you only found one "red flag" like that, it might not mean much. But if you found many different occurrences like that, it would be very strong evidence of copying.

[wgarvin]

The voodoo aspects, and more importantly the difficulties of comparing disassemblies, are increased when you throw different compilers into the mix. Here gcc 4.0 and gcc 4.2 produce two arrangements of the same instructions, whereas clang is completely different; it converts 0.0 to 0 at compile time.

I guess Clang is being clever here (one of those "weird optimizations" alluded to in the first post). It knows that "(double)x" can't be NaN because x is an integer, and it is able to find a constant integer to compare it with that gives the same result as the floating-point comparison your source code actually asked for, and the generated code for most platforms will be smaller and/or faster.

Its a good example of a compiler optimization that leaves no trace in the output. It also shows that the output of different compilers with different compiler settings active can have recognizable characteristics. If you start with only a compiled program and some source that you want to compare it against, a good starting point is to figure out what compiler and approximately what compiler options were used to produce the compiled program, and compile your source the same way.

Edit: About the gcc output... Instruction ordering is a complex topic, and differences in ordering dont necessarily mean anything, even with the exact same compiler and optimization settings. Especially for x86/x64, what matters is the dependencies between the instructions. So compare the dependency graph of the two snippets instead.

[IQ]

This is plain wrong and leads to bias. Your mapmaker analogy shows this, because the "mistake" is only a valid point of proof if they can show that this "mistake" is really a "mistake" after all. And they can only do that if they provide a "reference" which clearly shows that the "correct" data is different from the alleged mistake. In fact in a couple of lawsuits they did EXACTLY this. They showed that the telephone number and names do not exist in any other database (the reference) then their own and the alleged copyright infringer. Without reference this would not have been enough proof. I as a programmer know what you mean and the probabilities of exact matches over a reasonable chunk of code are near zero. But to for a couple of snippets (especially the short ones) one should go the extra mile and make sure the proof is watertight.

I don't think you need any kind of "negative reference" when comparing the code, that would just mean a lot of extra work for little gain.

It's enough to compile with same compiler/settings and then look for fragments of assembly that are structurally very similar, and then figure out what kind of C snippets would generate something like that and decide if you've found something significant or not. Is the snippet something "unusual"? something extremely unlikely for another author to write by hand? Per Bob's example, if it exactly duplicates a very specific bug from an old version of Crafty, then that would be pretty suspicious. There's no reason for someone to write that code on purpose, and its very unlikely to be written again by anyone else by accident.

This is just like the map-makers who intentionally put small mistakes into their maps so that they can detect if their maps were copied by other vendors (except that bugs in early versions of Crafty were of course put there by accident, not on purpose.)

Finding something in another program that exactly reproduced a bug like that would be strong circumstantial evidence that the other program had copied that particular part of Crafty's source code. If you only found one "red flag" like that, it might not mean much. But if you found many different occurrences like that, it would be very strong evidence of copying.

[bob]

I don't see why we keep having to "go here". The assembly language is generally unambiguous for simple issues like this. FILD only gives you one choice for the single operand. An integer 2's complement value. To do the floating compare, one could do a couple of different things, from fldz, to flid from an int word containing zero. No compiler would do the latter if 0.0 was used, unless the programmer forced it by loading from a variable containing 0.0 that was initialized elsewhere so that it can't be discovered at compile time.

Some seem to think that assembly language and C comparisons are some sort of voodoo...

The voodoo aspects, and more importantly the difficulties of comparing disassemblies, are increased when you throw different compilers into the mix. Here gcc 4.0 and gcc 4.2 produce two arrangements of the same instructions, whereas clang is completely different; it converts 0.0 to 0 at compile time.

Code: Select all

int test( int x ) 
{ 
  if ( x > 0.0 ) return 1;
  return 0; 
}  

gcc 4.0
LC0:
	.long	0
	.long	0
_test:
	pushl	%ebp
	xorl	%eax, %eax
	movl	%esp, %ebp
	cvtsi2sd	8(%ebp), %xmm0
	ucomisd	LC0, %xmm0
	leave
	seta	%al
	ret

gcc 4.2
_test:
	pushl	%ebp
	movl	%esp, %ebp
	cvtsi2sd	8(%ebp), %xmm0
	xorl	%eax, %eax
	ucomisd	LC0, %xmm0
	seta	%al
	leave
	ret
LC0:
	.long	0
	.long	0

clang
_test:
	pushl	%ebp
	movl	%esp, %ebp
	cmpl	$0, 8(%ebp)
	setg	%al
	movzbl	%al, %eax
	popl	%ebp
	ret

Previously mentioned. But the ideas still work. Yes, syntax to semantics is a many-to-one mapping. Semantics to implementation is also. But you can compare C to asm with high accuracy. If you have 50 lines of C, and 300 lines of ASM, and you convert the asm into something that matches the 50 lines of C accurately, is semantically equivalent, and leaves no instructions "left over" then the comparison is accurate...

[bob]

I don't think you need any kind of "negative reference" when comparing the code, that would just mean a lot of extra work for little gain.

It's enough to compile with same compiler/settings and then look for fragments of assembly that are structurally very similar, and then figure out what kind of C snippets would generate something like that and decide if you've found something significant or not. Is the snippet something "unusual"? something extremely unlikely for another author to write by hand? Per Bob's example, if it exactly duplicates a very specific bug from an old version of Crafty, then that would be pretty suspicious. There's no reason for someone to write that code on purpose, and its very unlikely to be written again by anyone else by accident.

This is just like the map-makers who intentionally put small mistakes into their maps so that they can detect if their maps were copied by other vendors (except that bugs in early versions of Crafty were of course put there by accident, not on purpose.)

For the record, not _all_ of those were accidental. I did introduce at least two bugs in early versions of the parallel search when it became obvious that we were seeing new parallel programs overnight... However, this case is way beyond that time-frame. But there are still some unusual "program signatures" here and there where I tried something unusual, or, on occasion, left code in that should have been removed. In one current case, I left something in, but it had no effect because the condition being tested was never true...

Finding something in another program that exactly reproduced a bug like that would be strong circumstantial evidence that the other program had copied that particular part of Crafty's source code. If you only found one "red flag" like that, it might not mean much. But if you found many different occurrences like that, it would be very strong evidence of copying.

[bob]

This is plain wrong and leads to bias. Your mapmaker analogy shows this, because the "mistake" is only a valid point of proof if they can show that this "mistake" is really a "mistake" after all. And they can only do that if they provide a "reference" which clearly shows that the "correct" data is different from the alleged mistake. In fact in a couple of lawsuits they did EXACTLY this. They showed that the telephone number and names do not exist in any other database (the reference) then their own and the alleged copyright infringer. Without reference this would not have been enough proof. I as a programmer know what you mean and the probabilities of exact matches over a reasonable chunk of code are near zero. But to for a couple of snippets (especially the short ones) one should go the extra mile and make sure the proof is watertight.

I don't think you need any kind of "negative reference" when comparing the code, that would just mean a lot of extra work for little gain.

It's enough to compile with same compiler/settings and then look for fragments of assembly that are structurally very similar, and then figure out what kind of C snippets would generate something like that and decide if you've found something significant or not. Is the snippet something "unusual"? something extremely unlikely for another author to write by hand? Per Bob's example, if it exactly duplicates a very specific bug from an old version of Crafty, then that would be pretty suspicious. There's no reason for someone to write that code on purpose, and its very unlikely to be written again by anyone else by accident.

This is just like the map-makers who intentionally put small mistakes into their maps so that they can detect if their maps were copied by other vendors (except that bugs in early versions of Crafty were of course put there by accident, not on purpose.)

Finding something in another program that exactly reproduced a bug like that would be strong circumstantial evidence that the other program had copied that particular part of Crafty's source code. If you only found one "red flag" like that, it might not mean much. But if you found many different occurrences like that, it would be very strong evidence of copying.

For the record, we are not going to be satisfied with "a couple of snippets". So this is not going to be an issue... But finding something inside Crafty that is interesting, and then locating that in a binary is a PITA. Takes time.

[wgarvin]

This is plain wrong and leads to bias. Your mapmaker analogy shows this, because the "mistake" is only a valid point of proof if they can show that this "mistake" is really a "mistake" after all. And they can only do that if they provide a "reference" which clearly shows that the "correct" data is different from the alleged mistake. In fact in a couple of lawsuits they did EXACTLY this. They showed that the telephone number and names do not exist in any other database (the reference) then their own and the alleged copyright infringer. Without reference this would not have been enough proof. I as a programmer know what you mean and the probabilities of exact matches over a reasonable chunk of code are near zero. But to for a couple of snippets (especially the short ones) one should go the extra mile and make sure the proof is watertight.

You might want to re-read Bob's post earlier in the thread. It had this incorrect code:

Code: Select all

(pawn_hash_table+i)->passed_w=0;
(pawn_hash_table+i)->passed_w=0;

Now the correct code is totally obvious, one of them should say passed_b instead of passed_w. You don't need any kind of "reference" of some other engine to see this. And other engines might not even use the same kind of data structure at all, so including them in the comparison is not helpful.

So in summary: If you disassemble an engine and find that it has a data structure with very similar fields to this pawn_hash_table thing from Crafty, and you figure out which field is equivalent to passed_w and passed_b, and you find the piece of code that's supposed to initialize all of these fields to 0 and you discover that it initializes all of the other fields but NOT the passed_b field... then that is highly suspicious. There are only a couple of possible explanations for a finding like that. By far the most plausible is that the source code for that routine was copied, bug and all, from Crafty.

Its exactly as Bob said -- if you find one "coincidence" like that, it doesn't mean much. If you find lots of them, that amounts to very strong evidence of source code copying.

I'm sure the team doing this examination is not going to rush to any conclusions, they know what they are doing and they are going to be very thorough. When they are finished, I hope there will be some kind of public report with the findings? It should be very interesting.

[Zach Wegner]

This is plain wrong and leads to bias. Your mapmaker analogy shows this, because the "mistake" is only a valid point of proof if they can show that this "mistake" is really a "mistake" after all. And they can only do that if they provide a "reference" which clearly shows that the "correct" data is different from the alleged mistake. In fact in a couple of lawsuits they did EXACTLY this. They showed that the telephone number and names do not exist in any other database (the reference) then their own and the alleged copyright infringer. Without reference this would not have been enough proof. I as a programmer know what you mean and the probabilities of exact matches over a reasonable chunk of code are near zero. But to for a couple of snippets (especially the short ones) one should go the extra mile and make sure the proof is watertight.

You might want to re-read Bob's post earlier in the thread. It had this incorrect code:

Code: Select all

(pawn_hash_table+i)->passed_w=0;
(pawn_hash_table+i)->passed_w=0;

Now the correct code is totally obvious, one of them should say passed_b instead of passed_w. You don't need any kind of "reference" of some other engine to see this. And other engines might not even use the same kind of data structure at all, so including them in the comparison is not helpful.

So in summary: If you disassemble an engine and find that it has a data structure with very similar fields to this pawn_hash_table thing from Crafty, and you figure out which field is equivalent to passed_w and passed_b, and you find the piece of code that's supposed to initialize all of these fields to 0 and you discover that it initializes all of the other fields but NOT the passed_b field... then that is highly suspicious. There are only a couple of possible explanations for a finding like that. By far the most plausible is that the source code for that routine was copied, bug and all, from Crafty.

Just to set the record straight, this is not yet confirmed. I haven't yet decoded the meaning of each struct member. At the very least, the struct members have been reordered. All I have said is that not all members are initialized, they are initialized out order, and one field is initialized twice.

Its exactly as Bob said -- if you find one "coincidence" like that, it doesn't mean much. If you find lots of them, that amounts to very strong evidence of source code copying.

I'm sure the team doing this examination is not going to rush to any conclusions, they know what they are doing and they are going to be very thorough. When they are finished, I hope there will be some kind of public report with the findings? It should be very interesting.

I will most likely make a report on this as well. I won't be quite as thorough, since there's just copied code everywhere--I have stopped keeping track of all the similarities I find. It's quite obviously a derivative.

Rybka 1.6.1 does have the EvaluateMates() 99999 bug found in Crafty, the same one that outed El Chinito. It's even a little funnier in Rybka, though--perhaps as an attempt to disguise the function, all the values in the BN mate tables are divided by 5, and the final value is multiplied by 2 before returning, so it's always even. So it will _definitely_ never return 99999.

[Zach Wegner]

Edit: About the gcc output... Instruction ordering is a complex topic, and differences in ordering dont necessarily mean anything, even with the exact same compiler and optimization settings. Especially for x86/x64, what matters is the dependencies between the instructions. So compare the dependency graph of the two snippets instead.

Definitely true. Although writes to memory are often not reordered, since it's hard for the compiler to prove that the order doesn't matter due to memory aliasing (one of those really nasty things I hate about C).

For pure register code, though, it can sometimes be reordered quite a bit. For out-of-order cores it's usually just ordered to minimize register pressure enough so that no spill/fill occurs, and let register renaming take care of the rest.

[bob]

This is plain wrong and leads to bias. Your mapmaker analogy shows this, because the "mistake" is only a valid point of proof if they can show that this "mistake" is really a "mistake" after all. And they can only do that if they provide a "reference" which clearly shows that the "correct" data is different from the alleged mistake. In fact in a couple of lawsuits they did EXACTLY this. They showed that the telephone number and names do not exist in any other database (the reference) then their own and the alleged copyright infringer. Without reference this would not have been enough proof. I as a programmer know what you mean and the probabilities of exact matches over a reasonable chunk of code are near zero. But to for a couple of snippets (especially the short ones) one should go the extra mile and make sure the proof is watertight.

You might want to re-read Bob's post earlier in the thread. It had this incorrect code:

Code: Select all

(pawn_hash_table+i)->passed_w=0;
(pawn_hash_table+i)->passed_w=0;

Now the correct code is totally obvious, one of them should say passed_b instead of passed_w. You don't need any kind of "reference" of some other engine to see this. And other engines might not even use the same kind of data structure at all, so including them in the comparison is not helpful.

So in summary: If you disassemble an engine and find that it has a data structure with very similar fields to this pawn_hash_table thing from Crafty, and you figure out which field is equivalent to passed_w and passed_b, and you find the piece of code that's supposed to initialize all of these fields to 0 and you discover that it initializes all of the other fields but NOT the passed_b field... then that is highly suspicious. There are only a couple of possible explanations for a finding like that. By far the most plausible is that the source code for that routine was copied, bug and all, from Crafty.

Just to set the record straight, this is not yet confirmed. I haven't yet decoded the meaning of each struct member. At the very least, the struct members have been reordered. All I have said is that not all members are initialized, they are initialized out order, and one field is initialized twice.

Its exactly as Bob said -- if you find one "coincidence" like that, it doesn't mean much. If you find lots of them, that amounts to very strong evidence of source code copying.

I'm sure the team doing this examination is not going to rush to any conclusions, they know what they are doing and they are going to be very thorough. When they are finished, I hope there will be some kind of public report with the findings? It should be very interesting.

I will most likely make a report on this as well. I won't be quite as thorough, since there's just copied code everywhere--I have stopped keeping track of all the similarities I find. It's quite obviously a derivative.

Rybka 1.6.1 does have the EvaluateMates() 99999 bug found in Crafty, the same one that outed El Chinito. It's even a little funnier in Rybka, though--perhaps as an attempt to disguise the function, all the values in the BN mate tables are divided by 5, and the final value is multiplied by 2 before returning, so it's always even. So it will _definitely_ never return 99999.

I think these are key. The only thing I wish I had a better handle on is the exact version.

One question: Can you check both option.c and init.c in Crafty, where you will find code that initializes the pawn hash table. In version 19.0, init.c had the _b/_w bug we are talking about in init.c and option.c (in option.c where the hashp command is handled as I have to do a malloc() for the new size, then initialize everything to be clean). So 19.0 screwed this up in both places. In 19.1, the init.c code was fixed. But the bug remained in option.c for many versions. If you find identical initialization code in both places in the rybka 1.6.1 binary, we would then know it is 19.0 or earlier. If it is in only one place, we would know it is 19.1 or later. Which narrows it down a bit. If I had some idea of when 1.6.1 was first released, I might could look thru a zillion games I have saved and find what crafty version was current around that time. However, I am not sure how complete the game coverage is since Crafty has played a _bunch_ of games on ICC and FICS over the years...