Page 2 of 3

Re: issue-#134 interface change not detected

Posted: Thu Oct 13, 2016 4:22 pm
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.

Re: issue-#134 interface change not detected

Posted: Thu Oct 13, 2016 9:19 pm
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;

Re: issue-#134 interface change not detected

Posted: Fri Oct 14, 2016 5:52 am
by Josef Templ
Robert wrote: Would changing the hash function be a compatibility disaster?
Yes.

Re: issue-#134 interface change not detected

Posted: Fri Oct 14, 2016 7:40 am
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.

Re: issue-#134 interface change not detected

Posted: Fri Oct 14, 2016 8:51 am
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";

Re: issue-#134 interface change not detected

Posted: Fri Oct 14, 2016 9:00 am
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

Re: issue-#134 interface change not detected

Posted: Fri Oct 14, 2016 11:01 am
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.

Re: issue-#134 interface change not detected

Posted: Fri Oct 14, 2016 11:43 am
by Josef Templ
That is true.

Re: issue-#134 interface change not detected

Posted: Sat Jan 07, 2017 9:52 am
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

Re: issue-#134 interface change not detected

Posted: Thu Jan 19, 2017 7:28 pm
by Ivan Denisov
Ready for voting?