diff options
author | tsyrogit <tsyrogit@users.noreply.github.com> | 2017-12-09 16:31:36 +0000 |
---|---|---|
committer | GitHub <noreply@github.com> | 2017-12-09 16:31:36 +0000 |
commit | 3218efa6eaf4f8067e86a7db6297c7eb215f4120 (patch) | |
tree | 2ca545164d4a99902add03be3911dbc866b3be10 | |
parent | a64315ede3c54e2d6d6548bce3791f52c2e3cca5 (diff) | |
parent | f7037ff39bdff62f20ba325f25c86c035840691d (diff) | |
download | zxcvbn-c-3218efa6eaf4f8067e86a7db6297c7eb215f4120.tar.gz |
Merge pull request #20 from Perlbotics/bugfix-kbd
Bugfix kbd
-rw-r--r-- | makefile | 12 | ||||
-rw-r--r-- | test-internals.c | 145 | ||||
-rw-r--r-- | test.c | 1 | ||||
-rw-r--r-- | testcases.txt | 4 | ||||
-rw-r--r-- | zxcvbn.c | 18 |
5 files changed, 171 insertions, 9 deletions
@@ -15,7 +15,7 @@ SONAME = libzxcvbn.so.0 WORDS = words-eng_wiki.txt words-female.txt words-male.txt words-passwd.txt words-surname.txt words-tv_film.txt -all: test-file test-inline test-c++inline test-c++file test-shlib test-statlib +all: test-file test-inline test-c++inline test-c++file test-shlib test-statlib test-internals test-shlib: test.c $(TARGET_LIB) if [ ! -e libzxcvbn.so ]; then ln -s $(TARGET_LIB) libzxcvbn.so; fi @@ -44,6 +44,10 @@ test-inline: test.c zxcvbn-inline.o $(CC) $(CPPFLAGS) $(CFLAGS) \ -o test-inline test.c zxcvbn-inline.o $(LDFLAGS) -lm +test-internals: test-internals.c zxcvbn.c dict-crc.h zxcvbn.h + $(CC) $(CPPFLAGS) $(CFLAGS) \ + -o test-internals test-internals.c $(LDFLAGS) -lm + zxcvbn-inline-pic.o: zxcvbn.c dict-src.h zxcvbn.h $(CC) $(CPPFLAGS) $(CFLAGS) -fPIC -c -o $@ $< @@ -80,7 +84,9 @@ zxcvbn-c++file.o: zxcvbn.c dict-crc.h zxcvbn.h $(CXX) $(CPPFLAGS) $(CXXFLAGS) \ -DUSE_DICT_FILE -c -o zxcvbn-c++file.o zxcvbn.cpp -test: test-file test-inline test-c++inline test-c++file test-shlib test-statlib testcases.txt +test: test-internals test-file test-inline test-c++inline test-c++file test-shlib test-statlib testcases.txt + @echo Testing internals... + ./test-internals @echo Testing C build, dictionary from file ./test-file -t testcases.txt @echo Testing C build, dictionary in executable @@ -97,7 +103,7 @@ test: test-file test-inline test-c++inline test-c++file test-shlib test-statlib clean: rm -f test-file zxcvbn-file.o test-c++file zxcvbn-c++file.o - rm -f test-inline zxcvbn-inline.o zxcvbn-inline-pic.o test-c++inline zxcvbn-c++inline.o + rm -f test-inline test-internals zxcvbn-inline.o zxcvbn-inline-pic.o test-c++inline zxcvbn-c++inline.o rm -f dict-*.h zxcvbn.dict zxcvbn.cpp test.cpp rm -f dictgen rm -f ${TARGET_LIB} ${SONAME} libzxcvbn.so test-shlib libzxcvbn.a test-statlib diff --git a/test-internals.c b/test-internals.c new file mode 100644 index 0000000..0ccd0de --- /dev/null +++ b/test-internals.c @@ -0,0 +1,145 @@ + +/* Internal tests that cannot be run against the library without unnecessary export of symbols. + Copyright (c) 2017, Perlbotics / see LICENSE.txt + */ + + +#include "zxcvbn.h" +/* need access to internals for testing; not linked against library, just inlined */ +#include "zxcvbn.c" + + +/********************************************************************************** + * Internal checks: Validate if the first element of each group is sorted in + * ascending order. CharBinSearch(...) fails otherwise. + * Returns 0 on success. + * Returns element index [1..] of first error entry that is less than previous one. + */ +static int check_order(const uint8_t *Ents, unsigned int NumEnts, unsigned int SizeEnts) { + const uint8_t *last; + unsigned int i; + + if (!Ents) return 0; + last = 0; + + for (i = 0; i < NumEnts; ++i, Ents += SizeEnts) { + if (last && *last > *Ents) { + unsigned int j; + + printf("Entry#%d [%d]: '%c' > '%c' (0x%02X > 0x%02X)\n A: ", i, i * SizeEnts, *last, *Ents, *last, *Ents); + for (j = 0; j < SizeEnts; ++j) { + printf("'%c' ", last[j] ? last[j] : ' '); + } + printf("\n >\n B: "); + for (j = 0; j < SizeEnts; ++j) { + printf("'%c' ", Ents[j] ? Ents[j] : ' '); + } + printf("\n"); + + return i; + } + last = Ents; + } + + return 0; /* cannot be a misordered position; first possible one: 1 */ +} + +/********************************************************************************** + * Internal checks: Checks keyboard data integrity. + * Returns 0 on succes. + * Otherwise, number of errors are reported. + */ +static unsigned int selftest_keyboards() { + unsigned int errors; + const Keyboard_t *k; + unsigned int Indx; + const uint8_t *keys; + int i,j,errpos, blanks; + + errors = 0; + for(k = Keyboards, Indx = 0; Indx < (sizeof Keyboards / sizeof Keyboards[0]); ++Indx, ++k) { + /* if one of these assrtion fails, we cannot use binary search algorithm */ + if (k->Shifts && strlen((const char*)k->Shifts) % 2 == 1) { + printf("ERROR: Keyboard[%d]: Shifts-string has odd number of entries.\n", Indx); + ++errors; + } + + if ( (errpos = check_order(k->Shifts, k->NumShift, 2)) ) { + printf("ERROR: Keyboard[%d]: Error above in sort order of Shifts-string near item #%d.\n", Indx, errpos); + ++errors; + } + + if ( (errpos = check_order(k->Keys, k->NumKeys, k->NumNear)) ) { + printf("ERROR: Keyboard[%d]: Error above in sort order of keyboard-entries! Problem near item #%d.\n", Indx, errpos); + ++errors; + continue; + } + + /* For each key (c0), check all its neighbours (ci): + * Does the neighbour key (c1==ci) have an entry (cx) in the opposite direction [rev_idx] + * pointing back to the current key c0? + * c0: ...ci.. --> c1: ..cx... --> cx==c0? + */ + keys = k->Keys; + blanks = 0; + for(i = 0; i < k->NumKeys; ++i) { + uint8_t c0; + c0 = keys[i * k->NumNear]; + + for (j = 0; j < k->NumNear - 1; ++j) { + const uint8_t *c1; + uint8_t ci, cx; + int rev_idx; + + /* rev_idx: reverse/opposite index to find opposite key location [0..6|8] --> [0..6|8] */ + rev_idx = (j + (k->NumNear - 1)/2) % (k->NumNear - 1); + ci = keys[i * k->NumNear + j + 1]; + + if (ci) { + c1 = CharBinSearch(ci, keys, k->NumKeys, k->NumNear); + if (c1) { + if (ci == c0) { + printf("ERROR: Keyboard[%d]: recursion - key '%c' cannot be its own neighbour!\n", Indx, *c1); + ++errors; + } else { + if ( (cx = c1[ 1 + rev_idx ]) ) { + if ( cx != c0 ) { + printf("ERROR: Keyboard[%d]: c0='%c':...(ci=%c)... -> c1='%c':...(cx=%c)... --!--> c0='%c':... \n", + Indx, c0, ci, *c1, cx, c0); + ++errors; + } + } else { /* reverse pointer is NULL */ + printf("ERROR: Keyboard[%d]: reverse entry missing in row c1='%c'[%d] pointing back to c0='%c'!\n", Indx, *c1, 1+rev_idx, c0); + ++errors; + } + } + } else { + printf("ERROR: Keyboard[%d]: no entry (neighbour list) found for src-char c1==ci='%c'\n", Indx, ci); + ++errors; + } + } else { /* blank neighbour key reference found */ + ++blanks; + } + } + } + if (blanks != k->NumBlank) { + printf("ERROR: Keyboard[%d]: number of blank keys announced (%d) does not match number of blank keys counted (%d)!\n", + Indx, k->NumBlank, blanks); + ++errors; + } + } + return errors; +} + + + + +int main() { + unsigned int errors; + + if( (errors = selftest_keyboards()) ){ /* currently only these */ + printf("FAILED: [KEYBOARDS] - selftest returned %d error(s).\n", errors); + } + + return errors ? 1 : 0; +} @@ -210,6 +210,7 @@ int main(int argc, char **argv) Quiet = 0; Checks = 0; White = 0; + if (!ZxcvbnInit("zxcvbn.dict")) { printf("Failed to open dictionary file\n"); diff --git a/testcases.txt b/testcases.txt index 8eaeac3..cddf519 100644 --- a/testcases.txt +++ b/testcases.txt @@ -59,4 +59,8 @@ pass.word.pass.word.pass.word. 60.41 passpasswordword 17.28 quvpzquvpz 24.50 +#-- with UK KBD (US-KBD=17.08) +jkl;'# 11.12 + magicfavoriteunclepromisedpublicbotherislandjimseriouslycellleadknowingbrokenadvicesomehowpaidblairlosingpushhelpedkillingusuallyearlierbosslaurabeginninglikedinnocentdocruleselizabethsabrinasummerexcoplearnedthirtyrisklettingphillipspeakingofficerridiculoussupportafternoonericwithsobutallwellareheohaboutrightyou're 545.9 + @@ -29,6 +29,13 @@ #include <math.h> #include <float.h> +/* printf */ +#ifdef __cplusplus +#include <cstdio> +#else +#include <stdio.h> +#endif + #ifdef USE_DICT_FILE #if defined(USE_FILE_IO) || !defined(__cplusplus) #include <stdio.h> @@ -932,19 +939,19 @@ static const uint8_t UK_Shift[] = "!1\"2$4%5&7(9)0*8:;<,>.?/@'AaBbCcDdEeFfGgHhIi static const uint8_t US_Shift[] = "!1\"'#3$4%5&7(9)0*8:;<,>.?/@2AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz^6_-{[|\\}]~`"; -/* Neighour tables */ +/* Neighbour tables */ static const uint8_t UK_Qwerty[48*7] = { /* key, left, up-left, up-right, right, down-right, down-left */ '#', '\'',']', 0, 0, 0, 0, '\'',';', '[', ']', '#', 0, '/', - ',', 'm', 'k', 'l', '.', 0, 0, '-', '0', 0, 0, '-', 'p', 'o', + ',', 'm', 'k', 'l', '.', 0, 0, '-', '0', 0, 0, '=', '[', 'p', '.', ',', 'l', ';', '/', 0, 0, '/', '.', ';', '\'', 0, 0, 0, '0', '9', 0, 0, '-', 'p', 'o', '1', '`', 0, 0, '2', 'q', 0, '2', '1', 0, 0, '3', 'w', 'q', '3', '2', 0, 0, '4', 'e', 'w', '4', '3', 0, 0, '5', 'r', 'e', '5', '4', 0, 0, '6', 't', 'r', '6', '5', 0, 0, '7', 'y', 't', '7', '6', 0, 0, '8', 'u', 'y', '8', '7', 0, 0, '9', 'i', 'u', '9', '8', 0, 0, '0', 'o', 'i', - ';', 'l', 'o', 'p','\'', '/', '.', '=', '-', 0, 0, 0, ']', '[', + ';', 'l', 'p', '[','\'', '/', '.', '=', '-', 0, 0, 0, ']', '[', '[', 'p', '-', '=', ']', '\'',';', '\\', 0, 0, 'a', 'z', 0, 0, ']', '[', '=', 0, 0, '#','\'', '`', 0, 0, 0, '1', 0, 0, 'a', 0, 'q', 'w', 's', 'z','\\', 'b', 'v', 'g', 'h', 'n', 0, 0, @@ -990,7 +997,7 @@ static const uint8_t US_Qwerty[47*7] = 'x', 'z', 's', 'd', 'c', 0, 0, 'y', 't', '6', '7', 'u', 'h', 'g', 'z', 0, 'a', 's', 'x', 0, 0, }; -static const uint8_t Dvorak[48*7] = +static const uint8_t Dvorak[47*7] = { '\'', 0, '1', '2', ',', 'a', 0, ',','\'', '2', '3', '.', 'o', 'a', '-', 's', '/', '=', 0, 0, 'z', '.', ',', '3', '4', 'p', 'e', 'o', @@ -1148,9 +1155,9 @@ static void SpatialMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, for(CurLen = MaxLen; CurLen >= MIN_SPATIAL_LEN;CurLen = Len - 1) { Len = 0; - memset(&Extra, 0, sizeof Extra); for(k = Keyboards, Indx = 0; Indx < (sizeof Keyboards / sizeof Keyboards[0]); ++Indx, ++k) { + memset(&Extra, 0, sizeof Extra); Len = DoSptlMatch(Passwd, CurLen, k, &Extra); if (Len > 0) { @@ -1201,7 +1208,6 @@ static void SpatialMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, p->Length = Len; AddMatchRepeats(Result, p, Passwd, MaxLen); AddResult(Result, p, MaxLen); - break; } } } |