]>
git.sthu.org Git - pgp-tools.git/blob - keyanalyze/keyanalyze.c
2 * Does some analysis of pre-monged pgp keyrings for some interesting data.
3 * Some code (c)2001 M. Drew Streib <dtype@dtype.org>
4 * Some code (c)2001 Thomas Roessler <roessler@does-not-exist.org>
5 * Some code (c)2001 Hal J. Burch <hburch@halport.lumeta.com>
6 * Some code (c)2001 Matt Kraai <kraai@alumni.carnegiemellon.edu>
7 * Some Code (c)2001 Steve Langasek <vorlon@netexpress.net>
9 * You are licenced to use this code under the terms of the GNU General
10 * Public License (GPL) version 2.
13 /* some configurables */
14 static char *infile
= "preprocess.keys";
15 static char *outdir
= "output/";
16 static int outsubdirs
= 1; /* create output/12/12345678 or output/12345678 */
17 #define MAXKEYS 160000 /* MUST be > `grep p preprocess.keys | wc` */
18 #define MINSETSIZE 10 /* minimum set size we care about for strong sets */
19 #define MAXHOPS 30 /* max hop count we care about for report */
25 #include <sys/types.h>
36 typedef struct sig sig
;
41 typedef struct threadparam threadparam
;
50 struct keydata keys
[MAXKEYS
];
51 FILE *fpin
,*fpout
,*fpstat
,*fpsets
,*fpmsd
;
54 int component
[MAXKEYS
];
57 int reachable
[MAXKEYS
];
60 pthread_mutex_t mean_l
;
63 void AddKey (unsigned char *newid
);
64 void AddSig (int src
, int dst
);
66 int CountSigs(sig
*current
);
67 unsigned int ConvertFromHex (const unsigned char *c
);
68 int GetKeyById(const unsigned char* searchid
);
69 void MeanCrawler(int *distset
, int id
, int len
);
70 float MeanDistance(int id
, int *hops
, int *hophigh
, sig
**farthest
);
72 /* ################################################################# */
73 /* helper functions, in alpha order */
75 void AddKey (unsigned char *newid
) {
76 struct keydata
*key
= &keys
[numkeys
++];
78 /* assume no dupes for now */
79 key
->id1
= ConvertFromHex(newid
);
80 key
->id2
= ConvertFromHex(newid
+8);
83 void AddKeyToList(sig
**pptr
, int id
)
86 pptr
= &(*pptr
)->next
;
88 *pptr
= (sig
*) calloc (1,sizeof(sig
));
92 void AddSig (int src
, int dst
) {
93 /* if GetKeyById returned -1, then we exit here */
94 if ((src
== -1) || (dst
== -1))
97 AddKeyToList(&keys
[dst
].to
, src
);
98 AddKeyToList(&keys
[src
].from
, dst
);
108 int CountSigs(sig
*current
) {
111 while (current
->next
) {
112 current
= current
->next
;
119 unsigned int ConvertFromHex (const unsigned char *c
) {
120 unsigned char buf1
[5];
121 unsigned char buf2
[5];
128 ret
= strtol(buf1
,NULL
,16)*65536 + strtol(buf2
,NULL
,16);
132 void DeleteKeyList(sig
**pptr
)
134 sig
*current
= *pptr
;
137 current
= (*pptr
)->next
;
143 /* recursive function to mark connected keys in the connected set */
144 int DFSMarkConnected (int *markset
, int id
) {
147 /* mark this node, call this function for all subnodes that aren't
150 for (psig
= keys
[id
].from
; psig
; psig
= psig
->next
) {
151 if (!markset
[psig
->id
])
152 num
+= DFSMarkConnected (markset
, psig
->id
);
158 int GetKeyById(const unsigned char* searchid
) {
162 s1
= ConvertFromHex(searchid
);
163 s2
= ConvertFromHex(searchid
+8);
164 for (i
= 0; i
< numkeys
; i
++) {
165 struct keydata
*key
= &keys
[i
];
166 if ((s1
== key
->id1
) && (s2
== key
->id2
)) {
173 /* new _much_ faster BFS version of MeanCrawler() contributed by
174 * Hal J. Burch <hburch@halport.lumeta.com> */
175 void MeanCrawler(int *distset
, int id
, int len
) {
180 memset(queue
,0,sizeof(int)*MAXKEYS
);
186 while (qtail
> qhead
) {
191 if ((len
+1) < distset
[psig
->id
]) {
192 distset
[psig
->id
] = len
+1;
193 queue
[qtail
++] = psig
->id
;
200 float MeanDistance(int id
, int *hops
, int *hophigh
, sig
**farthest
) {
205 /* init to a large value here, so shortest distance will always be
207 memset(dist
,100,sizeof(int)*MAXKEYS
);
209 MeanCrawler(dist
,id
,0);
211 for (i
=0;i
<numkeys
;i
++) {
212 if (component
[i
] == max_component
) {
213 totaldist
+= dist
[i
];
214 if (dist
[i
] < MAXHOPS
) hops
[dist
[i
]]++;
215 if (dist
[i
] > *hophigh
) {
217 DeleteKeyList(farthest
);
219 if (dist
[i
] == *hophigh
) {
220 AddKeyToList(farthest
, i
);
225 if (*hophigh
> MAXHOPS
) *hophigh
= MAXHOPS
;
227 return ((float)totaldist
/ max_size
);
230 FILE *OpenFileById(unsigned int id
) {
234 sprintf(idchr
,"%08X",id
);
236 /* first the directory */
240 strncat(buf
,idchr
,2);
241 mkdir(buf
,(mode_t
)493);
245 return fopen(buf
,"w");
248 /* ################################################################# */
249 /* program block functions, not predeclared */
254 fpin
= fopen(infile
, "r");
257 /* create output dir if necessary. this will just fail if it exists */
258 mkdir(outdir
, (mode_t
)493);
263 strcat(buf
,"status.txt");
264 fpstat
= fopen(buf
,"w");
265 if (!fpstat
) return 1;
267 /* msd output file */
270 strcat(buf
,"msd.txt");
271 fpmsd
= fopen(buf
,"w");
272 if (!fpmsd
) return 1;
274 /* othersets output file */
277 strcat(buf
,"othersets.txt");
278 fpsets
= fopen(buf
,"w");
279 if (!fpsets
) return 1;
281 /* other output file */
284 strcat(buf
,"other.txt");
285 fpout
= fopen(buf
,"w");
286 if (!fpout
) return 1;
291 void ParseArgs(int argc
, char **argv
)
296 int option
= getopt(argc
, argv
, "hi:o:1");
301 printf ("Usage: %s [-h1] [-i infile] [-o outdir]\n", argv
[0]);
309 outdirlen
= strlen(outdir
);
310 if (outdir
[outdirlen
- 1] != '/') {
311 outdir
= malloc(outdirlen
+ 2);
312 memcpy(outdir
, optarg
, outdirlen
);
313 outdir
[outdirlen
] = '/';
314 outdir
[outdirlen
+ 1] = '\0';
324 /* Assume it's infile */
325 infile
= argv
[optind
];
329 int PrintKeyList(FILE *f
, sig
*s
)
333 struct keydata
*key
= &keys
[s
->id
];
334 fprintf(f
, " %08X %08X\n", key
->id1
, key
->id2
);
342 unsigned char buf
[20];
345 fprintf(fpstat
,"Importing pass 1 (keys)...\n");
346 while (fread(buf
,1,18,fpin
) == 18) {
347 if (buf
[17] != '\n') continue;
352 fprintf(fpstat
,"done.\n");
353 fprintf(fpstat
,"%d keys imported\n",numkeys
);
356 fprintf(fpstat
,"Importing pass 2 (sigs)...\n");
357 while (fread(buf
,1,18,fpin
) == 18) {
358 if (buf
[17] != '\n') continue;
360 currentkey
= GetKeyById(buf
+1);
361 if (currentkey
== -1) {
362 fprintf(fpstat
,"Error finding key in pass 2.\n");
367 AddSig(GetKeyById(buf
+1),currentkey
);
368 if ((numsigs
%1000) == 0) {
369 fprintf(fpstat
,"%d sigs imported...\n",numsigs
);
374 fprintf(fpstat
,"done.\n");
375 fprintf(fpstat
,"%d sigs imported\n",numsigs
);
378 /* This is intended for later use. As it takes a lot of time for the
379 * signature imports, this will save time for future runs of the program
380 * with the same data set. */
383 /* not yet implemented. need to figure out how to best handle the
384 * linked lists of sigs first */
389 int removed
[MAXKEYS
];
394 void DFSVisit(int id
) {
397 dfsnum
[id
] = lownum
[id
] = ++lastdfsnum
;
398 stack
[stackindex
++] = id
;
400 for (psig
= keys
[id
].to
; psig
; psig
= psig
->next
) {
401 int neighbor
= psig
->id
;
403 if (removed
[neighbor
])
406 if (!dfsnum
[neighbor
]) {
409 if (lownum
[neighbor
] < lownum
[id
])
410 lownum
[id
] = lownum
[neighbor
];
411 } else if (dfsnum
[neighbor
] < lownum
[id
])
412 lownum
[id
] = dfsnum
[neighbor
];
415 if (lownum
[id
] == dfsnum
[id
]) {
420 i
= stack
[--stackindex
];
425 fprintf(fpsets
, "%08X %08X\n", key
->id1
, key
->id2
);
429 "*** %d keys in this strongly connected set\n\n", size
);
431 if (max_size
< size
) {
438 void TestConnectivity() {
441 for (i
= 0; i
< numkeys
; i
++)
445 num_reachable
= DFSMarkConnected (reachable
, max_component
);
447 fprintf(fpstat
,"reachable set is size %d\n", num_reachable
);
448 fprintf(fpstat
,"strongly connected set is size %d\n", max_size
);
451 /* ################################################################# */
452 /* report functions, sort of top level */
454 void IndivReport(FILE *fp
,int key
) {
455 int totalsigsto
, totalsigsfrom
;
458 fprintf(fp
,"KeyID %08X %08X\n\n", keys
[key
].id1
, keys
[key
].id2
);
460 fprintf(fp
,"This individual key report was generated as part of the monthly keyanalyze\n");
461 fprintf(fp
,"report at http://dtype.org/keyanalyze/.\n\n");
463 fprintf(fp
,"Note: Key signature counts and lists are from a pruned list that only\n");
464 fprintf(fp
,"includes keys with signatures other than their own.\n\n");
466 fprintf(fp
,"Signatures to this key:\n");
467 totalsigsto
= PrintKeyList(fp
, keys
[key
].to
);
468 fprintf(fp
,"Total: %d signatures to this id from this set\n\n",totalsigsto
);
470 fprintf(fp
,"Signatures from this key:\n");
471 totalsigsfrom
= PrintKeyList(fp
, keys
[key
].from
);
472 fprintf(fp
,"Total: %d signatures from this id to this set\n\n",totalsigsfrom
);
475 /* ################################################################# */
478 void *thread_slave(void *arg
) {
481 sig
*distant_sigs
= NULL
;
484 int hops
[MAXHOPS
]; /* array for hop histogram */
485 int hophigh
; /* highest number of hops for this key */
487 threadparam data
= *(threadparam
*)arg
;
489 for (i
=0;i
<numkeys
;i
++) {
490 struct keydata
*key
= &keys
[i
];
491 /* do this for all set2 now */
492 if (reachable
[i
] && ((i
%2)==data
.threadnum
)) {
493 /* zero out hop histogram */
494 memset(hops
,0,sizeof(int)*MAXHOPS
);
497 threadmean
= MeanDistance(i
,hops
,&hophigh
,&distant_sigs
);
499 pthread_mutex_lock(&mean_l
);
500 meantotal
+= threadmean
;
501 fprintf(fpmsd
,"%08X %08X %8.4f\n"
502 ,key
->id1
, key
->id2
, threadmean
);
504 pthread_mutex_unlock(&mean_l
);
506 /* individual report */
507 fpindiv
= OpenFileById(key
->id2
);
508 IndivReport(fpindiv
,i
);
509 fprintf(fpindiv
, "This key is %sin the strong set.\n",
510 component
[i
] == max_component
? "" : "not ");
511 fprintf(fpindiv
,"Mean distance to this key from strong set: %8.4f\n\n",threadmean
);
512 fprintf(fpindiv
,"Breakout by hop count (only from strong set):\n");
513 for (j
=0;j
<=hophigh
;j
++) {
514 fprintf(fpindiv
,"%2d hops: %5d\n",j
,hops
[j
]);
517 fprintf(fpindiv
,"\nFarthest keys (%d hops):\n", j
-1);
518 PrintKeyList(fpindiv
, distant_sigs
);
519 DeleteKeyList(&distant_sigs
);
527 /* ################################################################# */
530 int main(int argc
, char **argv
)
532 pthread_t
*slave0
,*slave1
;
533 threadparam arg0
,arg1
;
536 ParseArgs(argc
, argv
);
538 fprintf(stderr
, "Error opening files.\n");
544 pthread_mutex_init(&mean_l
,NULL
);
545 slave0
= (pthread_t
*) calloc(1, sizeof(pthread_t
));
546 slave1
= (pthread_t
*) calloc(1, sizeof(pthread_t
));
550 if (pthread_create(slave0
,NULL
,thread_slave
,&arg0
)) {
551 fprintf(stderr
,"Cannot create thread 0.");
553 if (pthread_create(slave1
,NULL
,thread_slave
,&arg1
)) {
554 fprintf(stderr
,"Cannot create thread 1.");
556 pthread_join(*slave0
, &retval
);
557 pthread_join(*slave1
, &retval
);
559 fprintf(fpout
,"Average mean is %9.4f\n",meantotal
/num_reachable
);
560 /* ReportMostSignatures(); */