issue-#134 interface change not detected

luowy
Posts: 234
Joined: Mon Oct 20, 2014 12:52 pm

Re: issue-#134 interface change not detected

Post by luowy »

indeed,fingerprint collision always in this situation,I cant believed it.
different input, same output. after a test,I am sure it is a collision, a pattern collision!

Code: Select all

MODULE ObxFingerPrint;

	IMPORT Log := StdLog, DevCPM;
	
	PROCEDURE Do* ();
		VAR x: INTEGER; f: INTEGER;
	BEGIN
		x := 1506223704; f := -1481896756;
		DevCPM.FPrint(x, f); Log.Int(x); Log.Ln;
		
		x := 1550329001; f := -1576858051;
		DevCPM.FPrint(x, f); Log.Int(x); Log.Ln;
	
	END Do;
	
	
END ObxFingerPrint.
User avatar
Robert
Posts: 1024
Joined: Sat Sep 28, 2013 11:04 am
Location: Edinburgh, Scotland

Re: issue-#134 interface change not detected

Post by Robert »

Josef Templ wrote:In our example, what happens is that we not only have two examples that produce a collision
but a pattern, where every instance produces a collision. The effect of the array length
on the fingerprint calculation is canceled out by the sequence of fingerprint update steps because it is effectively
applied twice and just by accident that effect occurs.

The compiler does not have a real bug. It just happens that there is a pattern that systematically leads to a collision.
This is very odd! I can't (quickly) disentangle the Oms code. I have rather simpler code that hashes data into a 32 degree irreducible polynomial over GF2 (ie the same theory as CRC32, but probably a different polynomial than the Oms one) which could easily be tried, and should be safer than an ad hoc fix - which seems to be what you are suggesting?

Would changing the hash function be a compatibility disaster?

Code: Select all

  Hash*     =  POINTER  TO  ABSTRACT  RECORD
                 code-  :  SET
               END;
  StdHash   =  POINTER  TO  RECORD (Hash) END;

PROCEDURE (h : Hash)    Check* (byte : BYTE), NEW, ABSTRACT;
PROCEDURE (h : StdHash) Check  (byte : BYTE);
  CONST
    mask  =  {0, 1, 27, 28};
  VAR
    s  :  SET;
    k  :  INTEGER;
  BEGIN
    s  :=  BITS (byte);
    FOR  k  :=  0  TO  7  DO
      IF  k  IN  s  THEN  h.code  :=  h.code / {0}  END;
      IF  31  IN  h.code
        THEN  h.code  :=  SYSTEM.LSH (h.code, 1); h.code  :=  h.code / mask
        ELSE  h.code  :=  SYSTEM.LSH (h.code, 1)  END
    END
  END  Check;
User avatar
Josef Templ
Posts: 2047
Joined: Tue Sep 17, 2013 6:50 am

Re: issue-#134 interface change not detected

Post by Josef Templ »

Robert wrote: Would changing the hash function be a compatibility disaster?
Yes.
User avatar
Robert
Posts: 1024
Joined: Sat Sep 28, 2013 11:04 am
Location: Edinburgh, Scotland

Re: issue-#134 interface change not detected

Post by Robert »

Josef Templ wrote:
Robert wrote: Would changing the hash function be a compatibility disaster?
Yes.
Not surprised!

I don't understand your proposal.
Either you are making a change to the fingerprint (and courting disaster) or you are not (so not avoiding collisions). I must be missing something here.
luowy
Posts: 234
Joined: Mon Oct 20, 2014 12:52 pm

Re: issue-#134 interface change not detected

Post by luowy »

the collision pattern occured in this way,

Code: Select all

MODULE ObxFP;

	IMPORT S := SYSTEM, Log := StdLog, DevCPM;
	


	(* BB standard *)
	PROCEDURE FPrint(VAR fp: INTEGER; val: INTEGER);
	BEGIN 
		DevCPM.FPrint(fp, val);
	END FPrint;
	
	(* A2 *)
	PROCEDURE FPrintA2 (VAR fp: INTEGER; val: INTEGER);
	BEGIN 
		fp := ORD(BITS(S.ROT(fp, 7)) / BITS(val))
	END FPrintA2;
	
	
	PROCEDURE FP* (VAR fp: INTEGER; pb, x: INTEGER);
	BEGIN
		FPrint(fp, x);
		FPrint(x, pb);
		FPrint(fp, x);
	END FP;
	
	PROCEDURE FPA2* (VAR fp: INTEGER; pb, x: INTEGER);
	BEGIN
		FPrintA2(fp, x);
		FPrintA2(x, pb);
		FPrintA2(fp, x);
	END FPA2;
	
			
	PROCEDURE Do* ();
		VAR fp: INTEGER;
	BEGIN
		(* BB *)
		fp := 100; FP(fp, 10, 2); Log.Int(fp); Log.Ln;
		fp := 100; FP(fp, 10, 20); Log.Int(fp); Log.Ln;
		(* A2 *)
		fp := 100; FPA2(fp, 10, 2); Log.Int(fp); Log.Ln;
		fp := 100; FPA2(fp, 10, 20); Log.Int(fp); Log.Ln;
	END Do;
	
	
END ObxFP.
the "x" can be any val,the fp'a val depend on "fp",and "bp";
User avatar
Josef Templ
Posts: 2047
Joined: Tue Sep 17, 2013 6:50 am

Re: issue-#134 interface change not detected

Post by Josef Templ »

Robert wrote: I don't understand your proposal.
Either you are making a change to the fingerprint (and courting disaster) or you are not (so not avoiding collisions). I must be missing something here.
The trick is, and this is also in luowy's proposal, to restrict the change to this specific pattern
by adding not only some constant but by first testing for the pattern.
This testing is done in "IF (btyp.comp = Array) & ((bstrobj = NIL) OR (bstrobj.name = null)) THEN".
Only if the pattern occurs (the base type of a Pointer is an anonymous fixed size array) there is a change in the fingerprint.
This pattern is very rare. It does not show up in the BlackBox distribution.
If you use a POINTER TO ARRAY structure, you typically use a dynamic array not a fixed size array.
And if you use a fixed size array there are some chances that you use a named type for that, not an anonymous one.

- Josef
User avatar
Robert
Posts: 1024
Joined: Sat Sep 28, 2013 11:04 am
Location: Edinburgh, Scotland

Re: issue-#134 interface change not detected

Post by Robert »

Josef Templ wrote:The trick is, .., to restrict the change to this specific pattern
So there is a remote possibility that someone's existing code will fail to load after this change (with an alleged compatibility problem), but after a recompile it will be fine?

Seems like an acceptable risk to me.
User avatar
Josef Templ
Posts: 2047
Joined: Tue Sep 17, 2013 6:50 am

Re: issue-#134 interface change not detected

Post by Josef Templ »

That is true.
User avatar
Josef Templ
Posts: 2047
Joined: Tue Sep 17, 2013 6:50 am

Re: issue-#134 interface change not detected

Post by Josef Templ »

The changes for this issue have been added to branch issue-#134.

For the diffs see http://redmine.blackboxframework.org/pr ... ype=inline.

- Josef
Ivan Denisov
Posts: 1700
Joined: Tue Sep 17, 2013 12:21 am
Location: Russia

Re: issue-#134 interface change not detected

Post by Ivan Denisov »

Ready for voting?
Post Reply