Debian Codegraph @

examples/rahisto/qosient/rahisto.pm

raw
1 package qosient::rahisto;
2
3 # Argus-5.0 Client Software. Tools to read, analyze and manage Argus data.
4 # Copyright (c) 2017-2024 QoSient, LLC
5 # All Rights Reserved
6 #
7 # THE ACCOMPANYING PROGRAM IS PROPRIETARY SOFTWARE OF QoSIENT, LLC,
8 # AND CANNOT BE USED, DISTRIBUTED, COPIED OR MODIFIED WITHOUT
9 # EXPRESS PERMISSION OF QoSIENT, LLC.
10 #
11 # QOSIENT, LLC DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
12 # SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
13 # AND FITNESS, IN NO EVENT SHALL QOSIENT, LLC BE LIABLE FOR ANY
14 # SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
16 # IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
17 # ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
18 # THIS SOFTWARE.
19 #
20 # This library contains routines for accessing the rahisto SQL tables.
21
22 use strict;
23 use warnings;
24 use Carp;
25 use DBI;
26 use POSIX qw(strftime);
27 use Try::Tiny;
28 use Net::IP;
29 use Math::BigInt;
30 use Exporter;
31 use vars qw($VERSION @ISA @EXPORT);
32 $VERSION = "1.00";
33 @ISA = qw(Exporter);
34 @EXPORT = qw(
35 DURATION_SEC
36 DURATION_MIN
37 DURATION_HOUR
38 DURATION_DAY
39 DURATION_WEEK
40 DURATION_MONTH
41 DURATION_YEAR
42 ONE_MINUTE
43 ONE_HOUR
44 ONE_DAY
45 ONE_WEEK
46 ONE_MONTH
47 ONE_YEAR
48 TIMEFMT_YEAR
49 TIMEFMT_MONTH
50 TIMEFMT_WEEK
51 TIMEFMT_DAY
52 TIMEFMT_HOUR
53 TIMEFMT_MINUTE
54 rahisto_metric_by_name
55 rahisto_metric_by_num
56 rahisto_get_model
57 rahisto_get_range
58 rahisto_get_bincount
59 rahisto_get_logscale
60 rahisto_opendb
61 rahisto_closedb
62 rahisto_create_index_table
63 rahisto_update_index_table
64 rahisto_create_values_table
65 rahisto_update_values_table
66 strs2prefix_array
67 rahisto_index_search_prefixes
68 rahisto_aggregate_query
69 rahisto_stimes_query
70 rahisto_kldiv
71 rahisto_jsdiv
72 rahisto_jsdist
73 );
74
75 my $debug = 0; # print debugging messages (includes DBI messages)
76 my $dbuser = 'root';
77 my $dbase = 'baseline';
78 my $password = q{};
79 my %attr = ( PrintError => $debug, RaiseError => 0 );
80 my $errcount = 0;
81
82 sub rahisto_opendb {
83 my $dsn = "DBI:mysql:";
84 my $dbh = DBI->connect( $dsn, $dbuser, $password, \%attr );
85
86 if (defined $dbh) {
87 $dbh->do("CREATE DATABASE IF NOT EXISTS $dbase");
88 $dbh->do("USE $dbase");
89 }
90 return $dbh; # undefined on error
91 }
92
93 sub rahisto_closedb {
94 my ($dbh) = @_;
95
96 $dbh->disconnect();
97 return 0;
98 }
99
100 use constant {
101 DURATION_SEC => 0,
102 DURATION_MIN => 1,
103 DURATION_HOUR => 2,
104 DURATION_DAY => 3,
105 DURATION_WEEK => 4,
106 DURATION_MONTH => 5,
107 DURATION_YEAR => 6,
108 };
109
110 use constant {
111 ONE_MINUTE => 60,
112 ONE_HOUR => 3600,
113 ONE_DAY => 86400,
114 ONE_WEEK => 86400 * 7,
115 ONE_MONTH => 86400 * 28,
116 ONE_YEAR => 86400 * 365,
117 };
118
119 use constant {
120 TIMEFMT_YEAR => '%Y',
121 TIMEFMT_MONTH => '%Y_%m',
122 TIMEFMT_WEEK => '%Y_w%W',
123 TIMEFMT_DAY => '%Y_%m_%d',
124 TIMEFMT_HOUR => '%Y_%m_%d_%H',
125 TIMEFMT_MINUTE => '%Y_%m_%d_%H_%M',
126 };
127
128 # This is a bit less than the max double value (inf), but all arithmetic
129 # on inf always results in inf.
130 my $DBL_MAX = 1.7e+308;
131
132
133 # Based on the ARGUSPRINT* C macros
134 my %metric_by_name = (
135 'stime' => 0,
136 'ltime' => 1,
137 'trans' => 2,
138 'dur' => 3,
139 'mean' => 4,
140 'min' => 5,
141 'max' => 6,
142 'saddr' => 7,
143 'daddr' => 8,
144 'proto' => 9,
145 'sport' => 10,
146 'dport' => 11,
147 'stos' => 12,
148 'dtos' => 13,
149 'sdsb' => 14,
150 'ddsb' => 15,
151 'sttl' => 16,
152 'dttl' => 17,
153 'bytes' => 18,
154 'sbytes' => 19,
155 'dbytes' => 20,
156 'appbytes' => 21,
157 'sappbytes' => 22,
158 'dappbytes' => 23,
159 'pkts' => 24,
160 'spkts' => 25,
161 'dpkts' => 26,
162 'load' => 27,
163 'sload' => 28,
164 'dload' => 29,
165 'loss' => 30,
166 'sloss' => 31,
167 'dloss' => 32,
168 'ploss' => 33,
169 'sploss' => 34,
170 'dploss' => 35,
171 'rate' => 36,
172 'srate' => 37,
173 'drate' => 38,
174 'srcid' => 39,
175 'flgs' => 40,
176 'smac' => 41,
177 'dmac' => 42,
178 'dir' => 43,
179 'sintpkt' => 44,
180 'dintpkt' => 45,
181 'sintpktact' => 46,
182 'dintpktact' => 47,
183 'sintpktidl' => 48,
184 'dintpktidl' => 49,
185 'sintpktmax' => 50,
186 'sintpktmin' => 51,
187 'dintpktmax' => 52,
188 'dintpktmin' => 53,
189 'sintpktactmax' => 54,
190 'sintpktactmin' => 55,
191 'dintpktactmax' => 56,
192 'dintpktactmin' => 57,
193 'sintpktidlmax' => 58,
194 'sintpktidlmin' => 59,
195 'dintpktidlmax' => 60,
196 'dintpktidlmin' => 61,
197 'xxx' => 62,
198 'sjit' => 63,
199 'djit' => 64,
200 'sjitact' => 65,
201 'djitact' => 66,
202 'sjitidl' => 67,
203 'djitidl' => 68,
204 'state' => 69,
205 'dldur' => 70,
206 'dlstime' => 71,
207 'dlltime' => 72,
208 'dlspkt' => 73,
209 'dldpkt' => 74,
210 'dspkts' => 75,
211 'ddpkts' => 76,
212 'dsbytes' => 77,
213 'ddbytes' => 78,
214 'pdspkts' => 79,
215 'pddpkts' => 80,
216 'pdsbytes' => 81,
217 'pddbytes' => 82,
218 'suser' => 83,
219 'duser' => 84,
220 'tcpext' => 85,
221 'swin' => 86,
222 'dwin' => 87,
223 'jdelay' => 88,
224 'ldelay' => 89,
225 'seq' => 90,
226 'bins' => 91,
227 'binnum' => 92,
228 'smpls' => 93,
229 'dmpls' => 94,
230 'svlan' => 95,
231 'dvlan' => 96,
232 'svid' => 97,
233 'dvid' => 98,
234 'svpri' => 99,
235 'dvpri' => 100,
236 'sipid' => 101,
237 'dipid' => 102,
238 'srng' => 103,
239 'erng' => 104,
240 'stcpb' => 105,
241 'dtcpb' => 106,
242 'tcprtt' => 107,
243 'stddev' => 109,
244 'rtime' => 110,
245 'offset' => 111,
246 'snet' => 112,
247 'dnet' => 113,
248 'sdur' => 114,
249 'ddur' => 115,
250 'stcpmax' => 116,
251 'dtcpmax' => 117,
252 'synack' => 118,
253 'ackdat' => 119,
254 'sstime' => 120,
255 'sltime' => 121,
256 'dstime' => 122,
257 'dltime' => 123,
258 'senc' => 124,
259 'denc' => 125,
260 'spktsz' => 126,
261 'smaxsz' => 127,
262 'sminsz' => 128,
263 'dpktsz' => 129,
264 'dmaxsz' => 130,
265 'dminsz' => 131,
266 'sco' => 132,
267 'dco' => 133,
268 'shops' => 134,
269 'dhops' => 135,
270 'icmpid' => 136,
271 'label' => 137,
272 'sas' => 169,
273 'das' => 170,
274 'ias' => 171,
275 'cause' => 172,
276 'bssid' => 173,
277 'ssid' => 174,
278 'nstroke' => 175,
279 'snstroke' => 176,
280 'dnstroke' => 177,
281 'smeansz' => 178,
282 'dmeansz' => 179,
283 'rank' => 180,
284 'sum' => 181,
285 'runtime' => 182,
286 'idle' => 183,
287 'tcpopt' => 184,
288 'resp' => 185,
289 'sgap' => 186,
290 'dgap' => 187,
291 'soui' => 188,
292 'doui' => 189,
293 'cor' => 190,
294 'laddr' => 191,
295 'raddr' => 192,
296 'lnet' => 191,
297 'rnet' => 192,
298 'abr' => 195,
299 'pcr' => 196,
300 'tf' => 197,
301 'stf' => 198,
302 'dtf' => 199,
303 'ico' => 200,
304 'slat' => 201,
305 'slon' => 202,
306 'dlat' => 201,
307 'dlon' => 202,
308 'ilat' => 201,
309 'ilon' => 202,
310 'sloc' => 207,
311 'dloc' => 208,
312 'loc' => 209,
313 'sid' => 210,
314 'node' => 211,
315 'inf' => 212,
316 'status' => 213,
317 'sgrp' => 214,
318 'dgrp' => 215,
319 'hash' => 216,
320 'ind' => 217,
321 'score' => 218,
322 'sname' => 219,
323 'dname' => 220,
324 'etype' => 221,
325 );
326
327 my %metric_by_num = (
328 0 => 'stime',
329 1 => 'ltime',
330 2 => 'trans',
331 3 => 'dur',
332 4 => 'mean',
333 5 => 'min',
334 6 => 'max',
335 7 => 'saddr',
336 8 => 'daddr',
337 9 => 'proto',
338 10 => 'sport',
339 11 => 'dport',
340 12 => 'stos',
341 13 => 'dtos',
342 14 => 'sdsb',
343 15 => 'ddsb',
344 16 => 'sttl',
345 17 => 'dttl',
346 18 => 'bytes',
347 19 => 'sbytes',
348 20 => 'dbytes',
349 21 => 'appbytes',
350 22 => 'sappbytes',
351 23 => 'dappbytes',
352 24 => 'pkts',
353 25 => 'spkts',
354 26 => 'dpkts',
355 27 => 'load',
356 28 => 'sload',
357 29 => 'dload',
358 30 => 'loss',
359 31 => 'sloss',
360 32 => 'dloss',
361 33 => 'ploss',
362 34 => 'sploss',
363 35 => 'dploss',
364 36 => 'rate',
365 37 => 'srate',
366 38 => 'drate',
367 39 => 'srcid',
368 40 => 'flgs',
369 41 => 'smac',
370 42 => 'dmac',
371 43 => 'dir',
372 44 => 'sintpkt',
373 45 => 'dintpkt',
374 46 => 'sintpktact',
375 47 => 'dintpktact',
376 48 => 'sintpktidl',
377 49 => 'dintpktidl',
378 50 => 'sintpktmax',
379 51 => 'sintpktmin',
380 52 => 'dintpktmax',
381 53 => 'dintpktmin',
382 54 => 'sintpktactmax',
383 55 => 'sintpktactmin',
384 56 => 'dintpktactmax',
385 57 => 'dintpktactmin',
386 58 => 'sintpktidlmax',
387 59 => 'sintpktidlmin',
388 60 => 'dintpktidlmax',
389 61 => 'dintpktidlmin',
390 62 => 'xxx',
391 63 => 'sjit',
392 64 => 'djit',
393 65 => 'sjitact',
394 66 => 'djitact',
395 67 => 'sjitidl',
396 68 => 'djitidl',
397 69 => 'state',
398 70 => 'dldur',
399 71 => 'dlstime',
400 72 => 'dlltime',
401 73 => 'dlspkt',
402 74 => 'dldpkt',
403 75 => 'dspkts',
404 76 => 'ddpkts',
405 77 => 'dsbytes',
406 78 => 'ddbytes',
407 79 => 'pdspkts',
408 80 => 'pddpkts',
409 81 => 'pdsbytes',
410 82 => 'pddbytes',
411 83 => 'suser',
412 84 => 'duser',
413 85 => 'tcpext',
414 86 => 'swin',
415 87 => 'dwin',
416 88 => 'jdelay',
417 89 => 'ldelay',
418 90 => 'seq',
419 91 => 'bins',
420 92 => 'binnum',
421 93 => 'smpls',
422 94 => 'dmpls',
423 95 => 'svlan',
424 96 => 'dvlan',
425 97 => 'svid',
426 98 => 'dvid',
427 99 => 'svpri',
428 100 => 'dvpri',
429 101 => 'sipid',
430 102 => 'dipid',
431 103 => 'srng',
432 104 => 'erng',
433 105 => 'stcpb',
434 106 => 'dtcpb',
435 107 => 'tcprtt',
436 109 => 'stddev',
437 110 => 'rtime',
438 111 => 'offset',
439 112 => 'snet',
440 113 => 'dnet',
441 114 => 'sdur',
442 115 => 'ddur',
443 116 => 'stcpmax',
444 117 => 'dtcpmax',
445 118 => 'synack',
446 119 => 'ackdat',
447 120 => 'sstime',
448 121 => 'sltime',
449 122 => 'dstime',
450 123 => 'dltime',
451 124 => 'senc',
452 125 => 'denc',
453 126 => 'spktsz',
454 127 => 'smaxsz',
455 128 => 'sminsz',
456 129 => 'dpktsz',
457 130 => 'dmaxsz',
458 131 => 'dminsz',
459 132 => 'sco',
460 133 => 'dco',
461 134 => 'shops',
462 135 => 'dhops',
463 136 => 'icmpid',
464 137 => 'label',
465 169 => 'sas',
466 170 => 'das',
467 171 => 'ias',
468 172 => 'cause',
469 173 => 'bssid',
470 174 => 'ssid',
471 175 => 'nstroke',
472 176 => 'snstroke',
473 177 => 'dnstroke',
474 178 => 'smeansz',
475 179 => 'dmeansz',
476 180 => 'rank',
477 181 => 'sum',
478 182 => 'runtime',
479 183 => 'idle',
480 184 => 'tcpopt',
481 185 => 'resp',
482 186 => 'sgap',
483 187 => 'dgap',
484 188 => 'soui',
485 189 => 'doui',
486 190 => 'cor',
487 191 => 'laddr',
488 192 => 'raddr',
489 191 => 'lnet',
490 192 => 'rnet',
491 195 => 'abr',
492 196 => 'pcr',
493 197 => 'tf',
494 198 => 'stf',
495 199 => 'dtf',
496 200 => 'ico',
497 201 => 'slat',
498 202 => 'slon',
499 201 => 'dlat',
500 202 => 'dlon',
501 201 => 'ilat',
502 202 => 'ilon',
503 207 => 'sloc',
504 208 => 'dloc',
505 209 => 'loc',
506 210 => 'sid',
507 211 => 'node',
508 212 => 'inf',
509 213 => 'status',
510 214 => 'sgrp',
511 215 => 'dgrp',
512 216 => 'hash',
513 217 => 'ind',
514 218 => 'score',
515 219 => 'sname',
516 220 => 'dname',
517 221 => 'etype',
518 );
519
520 sub rahisto_metric_by_name {
521 my ($name) = @_;
522
523 return $metric_by_name{$name};
524 }
525
526 sub rahisto_metric_by_num {
527 my ($num) = @_;
528
529 return $metric_by_num{$num};
530 }
531
532 my %range = (
533 rahisto_metric_by_name('dur') =>
534 '0-5', # appliances use a 5 second status interval
535 rahisto_metric_by_name('spkts') =>
536 '0-1500000', # slightly over 1 gbps of 64-byte packets
537 rahisto_metric_by_name('dpkts') =>
538 '0-1500000', # slightly over 1 gbps of 64-byte packets
539 rahisto_metric_by_name('sbytes') => '0-125000000', # 1 gbps / 8 bits
540 rahisto_metric_by_name('dbytes') => '0-125000000', # 1 gbps / 8 bits
541 rahisto_metric_by_name('pcr') => '-1-1', # -1 to +1
542 );
543
544 my %bincount = (
545 rahisto_metric_by_name('dur') => 25,
546 rahisto_metric_by_name('spkts') => 25,
547 rahisto_metric_by_name('dpkts') => 25,
548 rahisto_metric_by_name('sbytes') => 25,
549 rahisto_metric_by_name('dbytes') => 25,
550 rahisto_metric_by_name('pcr') => 25,
551 );
552
553 my %logscale = (
554 rahisto_metric_by_name('dur') => 1,
555 rahisto_metric_by_name('spkts') => 1,
556 rahisto_metric_by_name('dpkts') => 1,
557 rahisto_metric_by_name('sbytes') => 1,
558 rahisto_metric_by_name('dbytes') => 1,
559 rahisto_metric_by_name('pcr') => 0,
560 );
561
562 my $_rahisto_get_config = sub {
563 my ( $href, $mod ) = @_;
564
565 if ( !exists $href->{$mod} ) {
566 return;
567 }
568 return $href->{$mod};
569 };
570
571 # $datum is an href containing one json-decoded histogram from rahisto
572 my $_rahisto_parse_instance = sub {
573 my ($datum) = @_;
574 my @failure = (undef, undef);
575 my $instance = $datum->{'instance'};
576
577 if ( exists( $instance->{'saddr'} ) ) {
578 my $saddr = $instance->{'saddr'};
579 chomp $saddr;
580 $saddr =~ s/ *$//;
581
582 my $prefix = Net::IP->new($saddr);
583
584 if ( defined $prefix ) {
585 return ($prefix->ip(), $prefix->prefixlen());
586 }
587 else {
588 carp "Invalid IP address '$saddr' found in json data";
589 return @failure;
590 }
591 }
592 return @failure;
593 };
594
595 # from the Perl Maven:
596 sub uniq {
597 keys { map { $_ => 1 } @_ };
598 }
599
600 # mostly the same as rahisto_metric_by_num
601 sub rahisto_get_model {
602 my ($mod) = @_;
603 return $_rahisto_get_config->( \%metric_by_num, $mod );
604 }
605
606 sub rahisto_get_range {
607 my ($mod) = @_;
608 return $_rahisto_get_config->( \%range, $mod );
609 }
610
611 sub rahisto_get_bincount {
612 my ($mod) = @_;
613 return $_rahisto_get_config->( \%bincount, $mod );
614 }
615
616 sub rahisto_get_logscale {
617 my ($mod) = @_;
618 return $_rahisto_get_config->( \%logscale, $mod );
619 }
620
621 sub rahisto_create_index_table {
622 my ($dbh) = @_;
623
624 # previous_stime is used to find prevous entry when adding new histogram data.
625 # histo_bins and histo_size cannot change from one run of rahisto to the next.
626 my $query =
627 q{CREATE TABLE IF NOT EXISTS histograms (}
628 . q{address VARBINARY(16), masklen INTEGER UNSIGNED, }
629 . q{model TINYINT UNSIGNED, }
630 . q{sid VARCHAR(64), tablename VARCHAR(64),}
631 . q{inf VARCHAR(4), previous_stime DOUBLE(18,6) UNSIGNED, }
632 . q{histo_bins INTEGER UNSIGNED, histo_size DOUBLE, }
633 . q{PRIMARY KEY (address, masklen, model, tablename))};
634 my $sth = $dbh->prepare($query);
635
636 if ( !defined $sth ) {
637 carp "unable to prepare SQL create table statement";
638 return;
639 }
640
641 my $res = $sth->execute;
642
643 $sth->finish;
644 if ( !defined $res ) {
645 return;
646 }
647 return 1;
648 }
649
650 # These can go in yet another table . . . if needed, that has one row
651 # per histogram (one row per rahisto run)
652 # . q{histo_mean DOUBLE, histo_stddev DOUBLE, }
653 # . q{histo_min DOUBLE, histo_max DOUBLE))};
654
655 sub rahisto_update_index_table {
656 my ( $dbh, $address, $masklen, $sidinf_href, $times_aref, $histo_href,
657 $tablename, $model )
658 = @_;
659 my $query =
660 q{INSERT INTO histograms (address, masklen, model, sid, tablename, }
661 . q{inf, previous_stime, histo_bins, histo_size) VALUES }
662 . q{(INET6_ATON(?), ?, ?, ?, ?, ?, ?, ?, ?) ON DUPLICATE KEY UPDATE }
663 . q{previous_stime=?};
664
665 my $sth = $dbh->prepare($query);
666
667 if ( !defined $sth ) {
668 carp "unable to prepare SQL create table statement";
669 return;
670 }
671
672 my $aref = [$histo_href]; # reference to array of one href element
673 my $_model = $model;
674 my $_address = $address;
675 my $_masklen = $masklen;
676
677 if ( ref $histo_href eq 'ARRAY' ) {
678
679 # the json data already contains the array. use it and
680 # assume that each element is a hash reference.
681 $aref = $histo_href;
682 }
683
684 for my $datum ( @{$aref} ) {
685
686 # rahisto adds a key named "metric" when generating histograms
687 # for multiple metrics.
688 if ( exists( $datum->{'metric'} ) ) {
689 $_model = rahisto_metric_by_name( $datum->{'metric'} );
690
691 # the try/catch block will turn croak into a SQL rollback
692 if ( !defined $_model ) {
693 croak "invalid metric found in rahisto output";
694 }
695 }
696 if ( !defined $_model ) {
697 croak "no model found for histogram";
698 }
699
700 if ( exists( $datum->{'instance'} ) ) {
701 ($_address, $_masklen) = $_rahisto_parse_instance->($datum);
702 if ( !defined $_address || !defined $_masklen ) {
703 carp "No address found for histogram";
704 $sth->finish;
705 return;
706 }
707 }
708
709 my @params = ( $_address, $_masklen, $_model, $sidinf_href->{'sid'} );
710 push @params, $tablename;
711 push @params, ( $sidinf_href->{'inf'}, $times_aref->[0] );
712 push @params, ( $datum->{'bins'}, $datum->{'size'} );
713 push @params, $times_aref->[0];
714
715 my $res = $sth->execute(@params);
716
717 $sth->finish;
718 if ( !defined $res ) {
719 carp "Unable to update histograms index";
720 return;
721 }
722 }
723
724 return 1;
725 }
726
727 # times_aref is an array of (start, end) times in seconds since unix
728 # epoch, utc
729 # Many SELECT statements filter by stime which go MUCH faster with
730 # an index containing only stime (PRIMARY is not used when only one
731 # of the columns from the PRIMARY KEY is used).
732 sub rahisto_create_values_table {
733 my ( $dbh, $times_aref, $sidinf_href ) = @_;
734 my $sidinfstr = $sidinf_href->{'sid'} . '_' . $sidinf_href->{'inf'};
735
736 $sidinfstr =~ s/-//g;
737
738 # Add win_mean, win_stddev, win_variance when we're ready to calculate
739 # running stddev, etc. For now leave them out because rahisto-update
740 # does not populate these columns but they still use a lot of disk.
741 my $timestr = strftime( TIMEFMT_MONTH, gmtime $times_aref->[0] );
742 my $tablename = "histo_${sidinfstr}_${timestr}";
743 my $query =
744 qq{CREATE TABLE IF NOT EXISTS $tablename (}
745 . q{masklen INTEGER UNSIGNED, address VARBINARY(16), }
746 . q{model TINYINT UNSIGNED, stime DOUBLE(18,6) UNSIGNED, }
747 . q{ltime DOUBLE(18,6) UNSIGNED, samples INTEGER UNSIGNED, }
748 . q{class INT, }
749 . q{bin_interval DOUBLE, freq BIGINT, }
750 . q{min DOUBLE, max DOUBLE, }
751 . q{PRIMARY KEY (address, masklen, class, model, stime), }
752 . q{INDEX start_time (stime)) };
753 my $sth = $dbh->prepare($query);
754
755 if ( !defined $sth ) {
756 carp "unable to prepare SQL create table statement";
757 return;
758 }
759
760 my $res = $sth->execute;
761
762 if ( !defined $res ) {
763 return;
764 }
765 $sth->finish;
766
767 return $tablename;
768 }
769
770 sub rahisto_update_values_table {
771 my ( $dbh, $tablename, $data, $model, $address, $masklen, $times ) = @_;
772 my $query =
773 qq{INSERT INTO $tablename (masklen, address, model, }
774 . q{stime, ltime, class, bin_interval, freq, }
775 . q{samples, min, max) VALUES (?, INET6_ATON(?), }
776 . q{?, ?, ?, ?, ?, ?, ?, ?, ?)};
777
778 # +--------------+-----------------------+------+-----+---------+-------+
779 # | Field | Type | Null | Key | Default | Extra |
780 # +--------------+-----------------------+------+-----+---------+-------+
781 # | masklen | int(10) unsigned | NO | PRI | NULL | |
782 # | address | varbinary(16) | NO | PRI | NULL | |
783 # | model | tinyint(4) | NO | PRI | NULL | |
784 # | stime | double(18,6) unsigned | NO | PRI | NULL | |
785 # | ltime | double(18,6) unsigned | YES | | NULL | |
786 # | samples | int(10) unsigned | YES | | NULL | |
787 # | class | int(11) | NO | PRI | NULL | |
788 # | bin_interval | double | YES | | NULL | |
789 # | freq | bigint(20) | YES | | NULL | |
790 # | min | double | YES | | NULL | |
791 # | max | double | YES | | NULL | |
792 # +--------------+-----------------------+------+-----+---------+-------+
793
794 my $sth = $dbh->prepare($query);
795
796 if ( !defined $sth ) {
797 carp "unable to prepare SQL create table statement";
798 return;
799 }
800
801 $dbh->{AutoCommit} = 0;
802 $dbh->{RaiseError} = 1;
803
804 # rahisto's json output is an object (record / struct / dictionary
805 # / etc.) when there is only one metric (one -H option) and is an
806 # array of objects when multiple metrics are requested. Create our
807 # own array by default and if the parsed json output is an array,
808 # use it instead.
809
810 my $success = 1;
811 try {
812 my $aref = [$data]; # reference to array of one href element
813 my $_model = $model;
814 my $_address = $address;
815 my $_masklen = $masklen;
816
817 if ( ref $data eq 'ARRAY' ) {
818
819 # the json data already contains the array. use it and
820 # assume that each element is a hash reference.
821 $aref = $data;
822 }
823
824 for my $datum ( @{$aref} ) {
825
826 # rahisto adds a key named "metric" when generating histograms
827 # for multiple metrics.
828 if ( exists( $datum->{'metric'} ) ) {
829 $_model = rahisto_metric_by_name( $datum->{'metric'} );
830
831 # the try/catch block will turn croak into a SQL rollback
832 if ( !defined $_model ) {
833 croak "invalid metric found in rahisto output";
834 }
835 }
836 if ( !defined $_model ) {
837 croak "no model found for histogram";
838 }
839
840 if ( exists( $datum->{'instance'} ) ) {
841 ($_address, $_masklen) = $_rahisto_parse_instance->($datum);
842 if ( !defined $_address || !defined $_masklen ) {
843 carp "No address found for histogram";
844 $sth->finish;
845 return;
846 }
847 }
848
849 for my $value ( @{ $datum->{'values'} } ) {
850 my $interval = $value->{'Interval'};
851 if ( $interval =~ /-inf/ ) {
852 $interval = -1 * $DBL_MAX;
853 }
854
855 my @params =
856 ( $_masklen, $_address, $_model, $times->[0], $times->[2] );
857 push @params, $value->{'Class'};
858 push @params, $interval;
859 push @params, $value->{'Freq'};
860
861 # InnoDB, using the compact row format, uses less space to
862 # store NULL values than non-NULL values. We only need one
863 # copy of the N, min and max values.
864 if ( $value->{'Class'} == 1 ) {
865 push @params, $datum->{'N'};
866 push @params, $datum->{'min'};
867 push @params, $datum->{'max'};
868 }
869 else {
870 push @params, undef;
871 push @params, undef;
872 push @params, undef;
873 }
874 $sth->execute(@params);
875 }
876 }
877 $dbh->commit;
878 }
879 catch {
880 carp "Transaction aborted because $_";
881 eval { $dbh->rollback };
882 $success = undef;
883 };
884
885 $dbh->{AutoCommit} = 1;
886 $dbh->{RaiseError} = 0;
887 return $success;
888 }
889
890 # given an array of IP prefix strings, return reference to an array of
891 # Net::IP objects.
892 sub strs2prefix_array {
893 my ($prefixstr_aref) = @_;
894 my $prefixes = [];
895
896 if ( defined $prefixstr_aref ) {
897 my @addresses; # remove the prefix for now
898 my $oneprefix;
899
900 for my $oneprefix (@$prefixstr_aref) {
901 my $ip = Net::IP->new($oneprefix);
902
903 if ( !defined $ip ) {
904 carp( Net::IP::Error() );
905 return;
906 }
907 push $prefixes, $ip;
908 }
909 }
910 return $prefixes;
911 }
912
913 my $_format_query_address_clause = sub {
914 my ($prefixstr_aref) = @_;
915 my $addresses = strs2prefix_array($prefixstr_aref);
916 my $hostonly = 1;
917 my @result = ();
918
919 if ( !defined $addresses ) {
920 return;
921 }
922
923 for my $pfx (@{ $addresses }) {
924 if (($pfx->version == 4 && $pfx->prefixlen < 32)
925 || ($pfx->version == 6 && $pfx->prefixlen < 128)) {
926 $hostonly = undef;
927 last;
928 }
929 }
930
931 if ($hostonly) {
932 my $addresses_str = 'address IN ('
933 . join( ',', map( 'INET6_ATON(?)', @$addresses ) )
934 . ')';
935 push @result, $addresses_str;
936 push @result, map( $_->ip(), @$addresses );
937 return @result;
938 }
939
940 # Only ipv4 prefixes are handled, for now.
941 my $pfxcount = 0;
942 my $where = q{};
943 for my $pfx (@{ $addresses }) {
944 if ($pfxcount > 0) {
945 $where .= ' OR ';
946 }
947
948 if ($pfx->version == 6) {
949 # Carve up the 128-bit address into 64-bit chunks so that MariaDB
950 # deal with it as VARBINARY. MySQL 8 doesn't have this problem. . .
951 my $mask_upper = Math::BigInt->new($pfx->hexmask)->brsft(64);
952 my $mask_lower = Math::BigInt->new($pfx->hexmask)
953 ->band(Math::BigInt->new('0xffffffffffffffff'));
954 my $prefix_upper = $pfx->intip()->copy()->brsft(64);
955 my $prefix_lower = $pfx->intip()->copy()
956 ->band(Math::BigInt->new('0xffffffffffffffff'));
957
958 $where .= '(LENGTH(address) = 16 AND ('
959 . '(CAST(CONV(HEX(SUBSTRING(address, 1, 8)), 16, 10) AS UNSIGNED) '
960 . ' & ' . $mask_upper->as_hex . ' = (0 | ' . $prefix_upper->as_hex . '))'
961 . ' AND '
962 . '(CAST(CONV(HEX(SUBSTRING(address, 9, 8)), 16, 10) AS UNSIGNED) '
963 . ' & ' . $mask_lower->as_hex . ' = (0 | ' . $prefix_lower->as_hex . '))'
964 . '))';
965 } else {
966 $where .= '(LENGTH(address) = 4 AND '
967 . '(CAST(conv(HEX(address), 16, 10) AS UNSIGNED) & '
968 . $pfx->hexmask . ') = (0 | ' . $pfx->hexip . '))';
969 }
970 $pfxcount++;
971 }
972
973 if ($pfxcount > 0) {
974 $where = "($where" . ')';
975 }
976
977 return ($where, ());
978 };
979
980 # $dbh DBI handle
981 # $prefixstr_aref reference to array of IP prefix strings
982 # $sidstr_aref reference to array of Argus SIDs (UUIDs)
983 # $infstr_aref reference to array of Argus interface names
984 #
985 # Returns a hash reference containing the tablenames, sids and infs. The
986 # hash is keyed by tablename.
987 sub rahisto_index_search_prefixes {
988 my ( $dbh, $prefixstr_aref, $sidstr_aref, $infstr_aref, $model ) = @_;
989 my $addresses;
990 my $usewhere;
991 my $where = q{ WHERE};
992 my @params = ();
993
994 if ( $prefixstr_aref && scalar(@$prefixstr_aref) > 0 ) {
995 my ($addresses_str, my @aparams) =
996 $_format_query_address_clause->( $prefixstr_aref );
997
998 if (length($addresses_str) > 0) {
999 $where = " $addresses_str";
1000 $usewhere = 1;
1001 if (@aparams) {
1002 push @params, @aparams;
1003 }
1004 }
1005 }
1006
1007 if ($sidstr_aref) {
1008 if ( scalar(@$sidstr_aref) > 0 ) {
1009 if ($usewhere) {
1010 $where .= q{ AND};
1011 }
1012 my $template = join( ',', map( '?', @$sidstr_aref ) );
1013 push @params, @$sidstr_aref;
1014 $usewhere = 1;
1015 $where .= " sid IN ($template)";
1016 }
1017 }
1018
1019 if ($infstr_aref) {
1020 if ( scalar(@$infstr_aref) > 0 ) {
1021 if ($usewhere) {
1022 $where .= q{ AND};
1023 }
1024 my $template = join( ',', map( '?', @$infstr_aref ) );
1025 push @params, @$infstr_aref;
1026 $usewhere = 1;
1027 $where .= " inf IN ($template)";
1028 }
1029 }
1030
1031 my $query = qq{SELECT tablename, sid, inf FROM histograms};
1032 if ($usewhere) {
1033 $query .= " WHERE $where";
1034 }
1035 $query .= qq{ GROUP BY tablename};
1036 if ($debug) {
1037 print STDERR "$query\n";
1038 print STDERR "VALUES @params\n";
1039 }
1040
1041 my $sth = $dbh->prepare($query);
1042
1043 if ( !defined $sth ) {
1044 carp "unable to prepare SQL create select statement";
1045 return;
1046 }
1047
1048 my $res = $sth->execute(@params);
1049
1050 if ( !defined $res ) {
1051 return;
1052 }
1053 my $hash_ref = $sth->fetchall_hashref('tablename');
1054 $sth->finish;
1055
1056 return $hash_ref;
1057 }
1058
1059 use constant {
1060 QUERY_STIMES => 0,
1061 QUERY_AGGREGATE => 1,
1062 };
1063
1064 # results of prepare() indexed by table name, #prefixes, #times
1065 # sql_statements->{$tablename}->{$num_prefixes}->{$num_times} = $dbh->prepare()
1066 my $sql_statements = {};
1067
1068 my $find_sql_statement = sub {
1069 my ( $tablename, $num_prefixes, $num_times ) = @_;
1070 if ( exists $sql_statements->{$tablename}->{$num_prefixes}->{$num_times} ) {
1071 return $sql_statements->{$tablename}->{$num_prefixes}->{$num_times};
1072 }
1073 return;
1074 };
1075
1076 my $insert_sql_statement = sub {
1077 my ( $tablename, $num_prefixes, $num_times, $stmt ) = @_;
1078 if ( !exists $sql_statements->{$tablename}->{$num_prefixes}->{$num_times} )
1079 {
1080 $sql_statements->{$tablename}->{$num_prefixes}->{$num_times} = $stmt;
1081 }
1082 return;
1083 };
1084
1085 my $_format_query_histo_values = sub {
1086 my ( $querytype, $dbh, $prefixstr_aref, $tablename, $times, $model ) = @_;
1087 my $query =
1088 qq{SELECT class, bin_interval, SUM(freq) as freq from $tablename};
1089 my $where = q{ WHERE model = ?};
1090 my $groupby = q{ GROUP BY class WITH ROLLUP};
1091 my @params = ($model);
1092 my $addresses;
1093
1094 if ( $querytype == QUERY_STIMES ) {
1095 $query = qq{SELECT DISTINCT stime from $tablename};
1096 $groupby = q{};
1097 }
1098
1099 if ( $prefixstr_aref && scalar(@$prefixstr_aref) > 0 ) {
1100 my ($addresses_str, @aparams) = $_format_query_address_clause->( $prefixstr_aref );
1101 if (length($addresses_str) > 0) {
1102 $where .= " AND $addresses_str";
1103 if (@aparams) {
1104 push @params, @aparams;
1105 }
1106 }
1107 }
1108
1109 if ( defined $times ) {
1110 my $cnt = scalar(@$times);
1111 my $clause = q{};
1112
1113 $clause .= q{ AND};
1114
1115 if ( $cnt > 0 ) {
1116 $clause .= qq{ stime >= ?};
1117 push @params, $times->[0];
1118 if ( $cnt > 2 ) {
1119 $clause .= qq{ AND stime < ?};
1120 push @params, $times->[2];
1121 }
1122 $where .= $clause;
1123 }
1124 }
1125
1126 $query .= $where;
1127 $query .= $groupby;
1128 if ($debug) {
1129 print STDERR "$query\n";
1130 print STDERR "VALUES " . join( ', ', @params ) . "\n";
1131 }
1132 return ( $query, \@params );
1133 };
1134
1135 my $_aggregate_histo_values = sub {
1136 my ( $dbh, $prefixstr_aref, $tablename, $times, $model ) = @_;
1137 if ( !defined $times ) {
1138 $times = [];
1139 }
1140 if ( !defined $prefixstr_aref ) {
1141 $prefixstr_aref = [];
1142 }
1143
1144 my $num_prefixes = scalar( @{$prefixstr_aref} );
1145 my $num_times = scalar( @{$times} );
1146
1147 my $sth = $find_sql_statement->( $tablename, $num_prefixes, $num_times );
1148
1149 my ( $query, $params ) = $_format_query_histo_values->( QUERY_AGGREGATE, @_ );
1150 if ( !$sth ) {
1151 $sth = $dbh->prepare($query);
1152 if ( !defined $sth ) {
1153 carp "unable to prepare SQL create select statement";
1154 return;
1155 }
1156 $insert_sql_statement->( $tablename, $num_prefixes, $num_times, $sth );
1157 }
1158
1159 my $res = $sth->execute( @{$params} );
1160
1161 if ( !defined $res ) {
1162 return;
1163 }
1164 my $hash_ref = $sth->fetchall_hashref('class');
1165 $sth->finish;
1166
1167 return $hash_ref;
1168 };
1169
1170 my $_query_histo_stimes = sub {
1171 my ( $dbh, $prefixstr_aref, $tablename, $times, $model ) = @_;
1172 my ( $query, $params ) = $_format_query_histo_values->( QUERY_STIMES, @_ );
1173 my $sth = $dbh->prepare($query);
1174
1175 if ( !defined $sth ) {
1176 carp "unable to prepare SQL create select statement";
1177 return;
1178 }
1179
1180 my $res = $sth->execute( @{$params} );
1181
1182 if ( !defined $res ) {
1183 return;
1184 }
1185 my $aref = $sth->fetchall_arrayref;
1186 $sth->finish;
1187
1188 return $aref;
1189 };
1190
1191
1192
1193 # aggregate_histo_results: sum up the values from all of the tables
1194 #
1195 # $results_href a hash reference containing one or more histograms
1196 # (which are, in turn, also hash refs) keyed by SQL
1197 # table name, although any unique value will do.
1198 #
1199 # returns a hash reference containing a single histogram
1200 my $aggregate_histo_results = sub {
1201 my ($results_href) = @_;
1202 my %agg = ();
1203 for my $tbl ( keys $results_href ) {
1204 my $href = $results_href->{$tbl};
1205 for my $class ( keys $href ) {
1206 if ( exists $agg{$class} ) {
1207 $agg{$class}->{'freq'} += $href->{$class}->{'freq'};
1208 }
1209 else {
1210 $agg{$class} = { %{ $href->{$class} } }; # shallow copy of hash
1211 }
1212 }
1213 }
1214 return \%agg;
1215 };
1216
1217 # rahisto_aggregate_query parameters:
1218 # $dbh DBI handle as returned by rahisto_opendb()
1219 # $index_href hash reference returned by rahisto_index_search_prefixes()
1220 # $query_prefixes array reference to IP address prefixes
1221 # $query_times array reference to start and stop times in seconds GMT.
1222 # Second element is '-'.
1223 # $metric hash table metric specified with -H on rahisto commandline
1224 #
1225 # returns a hash ref containing a single histogram that represents the aggregate
1226 # of all histograms found for the requested prefixes during the requested times
1227 # in all of the tables listed in $index_href.
1228 sub rahisto_aggregate_query {
1229 my ( $dbh, $index_href, $query_prefixes, $query_times, $metric ) = @_;
1230 my %results_hash = ();
1231
1232 for my $tbl ( keys $index_href ) {
1233 my $results =
1234 $_aggregate_histo_values->( $dbh, $query_prefixes, $tbl, $query_times,
1235 $metric );
1236 if ($results) {
1237 $results_hash{$tbl} = $results;
1238 }
1239 }
1240 return $aggregate_histo_results->( \%results_hash );
1241 }
1242
1243 # $dbh DBI handle as returned by rahisto_opendb()
1244 # $index_href hash reference returned by rahisto_index_search_prefixes()
1245 # $query_prefixes array reference to IP address prefixes
1246 # $query_times array reference to start and stop times in seconds GMT.
1247 # Second element is '-'.
1248 # $metric hash table metric specified with -H on rahisto commandline
1249 sub rahisto_stimes_query {
1250 my ( $dbh, $index_href, $query_prefixes, $query_times, $metric ) = @_;
1251 my @results_array = ();
1252
1253 for my $tbl ( keys $index_href ) {
1254 my $results =
1255 $_query_histo_stimes->( $dbh, $query_prefixes, $tbl, $query_times,
1256 $metric );
1257 if ($results) {
1258
1259 # fetchall_arrayref returns an array ref of array refs.
1260 # For this query, each inner arrayref has only one element.
1261 push @results_array, map( $_->[0], @{$results} );
1262 }
1263 }
1264
1265 # pick out the distinct values and sort in ascending numeric order
1266 my @uniq_values = sort { $a <=> $b } uniq(@results_array);
1267 return \@uniq_values;
1268 }
1269
1270
1271 # equal(NUM1, NUM2, ACCURACY) : returns true if NUM1 and NUM2 are
1272 # equal to ACCURACY number of decimal places
1273 # Borrowed from Perl Cookbook by Nathan Torkington, Tom Christiansen
1274 # Seems like it will be slow. maybe (abs($A-$B) < .0000001) instead?
1275 sub float_equal {
1276 my ( $A, $B, $dp ) = @_;
1277
1278 return sprintf( "%.${dp}g", $A ) eq sprintf( "%.${dp}g", $B );
1279 }
1280
1281 # Determine if the two histograms / frequency distributions have the
1282 # same number of bins and that each bin in $A represents the same range
1283 # of values as its corresponding bin in $B.
1284 my $_rahisto_are_similar = sub {
1285 my ( $A, $B ) = @_;
1286 my $acount = scalar( keys($A) );
1287 my $bcount = scalar( keys($B) );
1288
1289 if ( $acount != $bcount ) {
1290 return;
1291 }
1292
1293 my $i;
1294 for ( $i = 1 ; $i <= $acount ; $i++ ) {
1295 if ( !exists $A->{$i} ) {
1296 if ( !exists $B->{$i} ) {
1297
1298 # this will skip the "rollup" hash
1299 next;
1300 }
1301
1302 # found a mismatch in class values
1303 return;
1304 }
1305 if (
1306 !float_equal(
1307 $A->{$i}->{'bin_interval'},
1308 $B->{$i}->{'bin_interval'}, 6
1309 )
1310 )
1311 {
1312 return;
1313 }
1314 }
1315 return 1;
1316 };
1317
1318 # Calculating the Kullback-Leibler Divergence requires that if there
1319 # are zero values in the Q(i) frequency distribution, the corresponding
1320 # frequencies in P(i) must also be zero, else the resulting divergence
1321 # in undefined. In terms of just arithmetic this is a problem with
1322 # dividing by zero -- ln(P[i]/Q[i]). However, simply skipping the
1323 # offending term(s) in Q removes one of the basic properties of the KL
1324 # divergence: that it is always non-negative.
1325 #
1326 # The approach to work around this problem tried here, since many of the
1327 # frequency distributions generated from flow data will have such "zero
1328 # entries", is to sub-sample the data; neighboring probabilities (bins
1329 # in the histogram) will be combined, in pairs, until there are no 0%
1330 # probabilities left. A lower limit can be provided to this function to
1331 # prevent the algorithm continuing all the way to a single bin of 100%.
1332 # In the event there are an odd number of bins, the center bin will be
1333 # carved in twain and, if non-zero, half of its value will be contributed
1334 # to each of its two neighbors.
1335 my $_rahisto_subsample = sub {
1336 my ( $P, $Q, $lowerlimit_param ) = @_;
1337 my $lowerlimit = 4;
1338
1339 if ( defined $lowerlimit_param ) {
1340 $lowerlimit = $lowerlimit_param;
1341 }
1342
1343 if ($debug) {
1344 if ( !$_rahisto_are_similar->( $P, $Q ) ) {
1345 carp "Q and P must be similar";
1346 return ( undef, undef );
1347 }
1348 }
1349
1350 my $pcount = scalar( keys($P) );
1351 my $qcount = scalar( keys($Q) );
1352 my $qzerocount = 0;
1353
1354 for my $val ( values $P ) {
1355 if ( !defined $val->{'class'} ) {
1356 $pcount --; # don't count the rollup value
1357 next;
1358 }
1359 }
1360
1361 for my $val ( values $Q ) {
1362 if ( !defined $val->{'class'} ) {
1363 $qcount --; # don't count the rollup value
1364 next;
1365 }
1366 if ( $val->{'freq'} == 0 ) {
1367 $qzerocount++;
1368 }
1369 }
1370
1371 if ( $qzerocount == 0 || $qcount < ( $lowerlimit * 2 ) ) {
1372 return ( undef, undef );
1373 }
1374
1375 my $splitbin;
1376 my $psplitval;
1377 my $qsplitval;
1378 my $Pnew = {};
1379 my $Qnew = {};
1380
1381 if ( $qcount % 2 == 1 ) {
1382 $splitbin = ( $qcount >> 1 ) + 1;
1383 $psplitval = $P->{$splitbin}->{'freq'} / 2.0;
1384 $qsplitval = $Q->{$splitbin}->{'freq'} / 2.0;
1385 }
1386
1387 my $i;
1388 my $off = 1;
1389 for ( $i = 1 ; $i < $pcount ; ) {
1390 if ( $splitbin && $i == $splitbin ) {
1391
1392 # skip this one for now
1393 $i++;
1394 $off = 0;
1395 next;
1396 }
1397
1398 my $class = ( $i >> 1 ) + $off;
1399 my $bin_interval =
1400 ( $P->{$i}->{'bin_interval'} + $P->{ $i + 1 }->{'bin_interval'} ) /
1401 2.0;
1402
1403 $Pnew->{$class} = {
1404 'class' => $class,
1405 'freq' => $P->{$i}->{'freq'} + $P->{ $i + 1 }->{'freq'},
1406 'bin_interval' => $bin_interval,
1407 };
1408 $Qnew->{$class} = {
1409 'class' => $class,
1410 'freq' => $Q->{$i}->{'freq'} + $Q->{ $i + 1 }->{'freq'},
1411 'bin_interval' => $bin_interval,
1412 };
1413
1414 $i += 2;
1415 }
1416
1417 # Now carve up the center bin and give each of the two center-most
1418 # bins in $Pnew half. A subsampled histo will always have an even
1419 # number of bins, numbered from bin "1".
1420
1421 if ( defined $splitbin ) {
1422 my $newcenter = ( $pcount >> 2 );
1423 $Pnew->{$newcenter}->{'freq'} += $psplitval;
1424 $Pnew->{ $newcenter + 1 }->{'freq'} += $psplitval;
1425 $Qnew->{$newcenter}->{'freq'} += $qsplitval;
1426 $Qnew->{ $newcenter + 1 }->{'freq'} += $qsplitval;
1427 }
1428
1429 my $class = ( $i >> 1 ) + $off;
1430 $Pnew->{''} = $P->{''};
1431 $Qnew->{''} = $Q->{''};
1432 $Pnew->{$class} = $P->{$pcount};
1433 $Qnew->{$class} = $Q->{$qcount};
1434
1435 return ( $Pnew, $Qnew );
1436 };
1437
1438 # Kullback-Leibler Divergence
1439 # Calculates D_{KL}(P||Q)
1440 # P and Q are references to hashes as returned by $_aggregate_histo_values()
1441 # in rahisto-querysql (should that function be moved here?)
1442 # P is assumed to be the "true" distribution.
1443 my $_rahisto_kldiv = sub {
1444 my ( $P, $Q ) = @_;
1445 my $diverg = 0;
1446 my $P_total;
1447 my $Q_total;
1448
1449 if ( scalar( keys $Q ) != scalar( keys $P ) ) {
1450 carp "Q and P must have the same number of bins";
1451 return;
1452 }
1453
1454 # rollup value, including outliers
1455 $P_total = 1.0 * $P->{''}->{'freq'};
1456 $Q_total = 1.0 * $Q->{''}->{'freq'};
1457
1458 for my $k ( keys($P) ) {
1459
1460 # The hash contains a "ROLLUP" of all frequencies with an
1461 # undefined class, as returned by the sql query. Skip this
1462 # element.
1463 if ( !defined $P->{$k}->{'class'} ) {
1464 next;
1465 }
1466
1467 my $p = $P->{$k}->{'freq'};
1468 my $q = $Q->{$k}->{'freq'};
1469 my $term = 0;
1470
1471 if ( $q == 0 && $p != 0 ) {
1472
1473 # KL Divergence is undefined for this case. Attempt to
1474 # sub-sample and try again.
1475 my ( $Pss, $Qss ) = $_rahisto_subsample->( $P, $Q );
1476 if ( defined $Pss && defined $Qss ) {
1477 return rahisto_kldiv( $Pss, $Qss );
1478 }
1479
1480 if ($debug) {
1481 print STDERR "subsample FAILED!!\n";
1482 }
1483
1484 # Unable to subsample. Give up.
1485 return;
1486 }
1487
1488 if ( $p != 0 && $q != 0 ) {
1489
1490 # here we can also be sure that P_total and Q_total are
1491 # not zero.
1492 $p /= $P_total;
1493 $q /= $Q_total;
1494 $term = $p * log( $p / $q );
1495 $diverg += $term;
1496 }
1497 }
1498 return $diverg;
1499 };
1500
1501 sub rahisto_kldiv {
1502 my ( $P, $Q ) = @_;
1503
1504 if ( !$_rahisto_are_similar->( $P, $Q ) ) {
1505 carp "Q and P must be similar";
1506 return;
1507 }
1508 return $_rahisto_kldiv->( $P, $Q );
1509 }
1510
1511 # $A and $B are histograms -- references to hashes as returned by
1512 # $_aggregate_histo_values().
1513 #
1514 # Returns $scale * ($A + $B)
1515 my $_rahisto_add = sub {
1516 my ( $A, $B, $scale ) = @_;
1517 my $res = { %{$A} };
1518
1519 for my $class ( keys $A ) {
1520 $res->{$class} = { %{ $A->{$class} } }; # shallow copy of has
1521 $res->{$class}->{'freq'} += $B->{$class}->{'freq'};
1522 if ( defined $scale ) {
1523 $res->{$class}->{'freq'} *= $scale;
1524 }
1525 }
1526
1527 # adjust min, max, times?
1528 return $res;
1529 };
1530
1531 # Jensen–Shannon divergence
1532 sub rahisto_jsdiv {
1533 my ( $P, $Q ) = @_;
1534
1535 if ( !$_rahisto_are_similar->( $P, $Q ) ) {
1536 carp "P and Q must be similar";
1537 return;
1538 }
1539
1540 my $M = $_rahisto_add->( $P, $Q, 0.5 );
1541 my $P_M = $_rahisto_kldiv->( $P, $M );
1542 my $Q_M = $_rahisto_kldiv->( $Q, $M );
1543
1544 if ( !defined $P_M || !defined $Q_M ) {
1545 carp "Jensen-Shannon divergence failed??";
1546 return;
1547 }
1548
1549 return ( ( $P_M + $Q_M ) * 0.5 );
1550 }
1551
1552 # Jensen-Shannon distance
1553 sub rahisto_jsdist {
1554 my ( $P, $Q ) = @_;
1555 my $div = rahisto_jsdiv( $P, $Q );
1556
1557 if ( !defined $div ) {
1558 return;
1559 }
1560 return sqrt($div);
1561 }
1562
1563 1;