forked from Keysight/Jlsca
-
Notifications
You must be signed in to change notification settings - Fork 0
/
mia.jl
129 lines (102 loc) · 2.73 KB
/
mia.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
# This file is part of Jlsca, license is GPLv3, see https://www.gnu.org/licenses/gpl-3.0.en.html
#
# Author: Cees-Bart Breunesse
#
# Implements Mutual Information Analysis, as described in https://eprint.iacr.org/2007/198.pdf
#
# TODO: the caller of mia will attack each key byte individually, causing the
# MiaColumnData for the samples to be recomputed each time. Should be improved
# although the bulk of the work is in the p(x,y) computation
module Mia
export mia
using ProgressMeter
using StatsBase
type MiaColumnData{T}
uniques::Set{T}
where::Dict{T,IntSet}
p::Dict{T, Float64}
numobs::Int
function MiaColumnData(X::Vector{T})
uniques = Set{T}()
where = Dict{T,IntSet}()
p = Dict{T, Float64}()
numobs = length(X)
for (idx,val) in enumerate(X)
push!(uniques, val)
if !(val in keys(where))
where[val] = IntSet()
end
push!(where[val], idx)
end
for x in uniques
wherex = where[x]
px = length(wherex) / numobs
where[x] = wherex
p[x] = px
end
return new(uniques, where, p, numobs)
end
end
function dump(c::MiaColumnData)
# print(c.uniques)
@printf("%s\n", c.where)
# print(c.p)
# print(c.numobs)
@printf("entropy: %f\n", - sum(map(x-> x*log2(x), values(c.p))))
@printf("sum(p): %f\n", sum(values(c.p)))
end
function mia(X::MiaColumnData, Y::MiaColumnData, normalized=false)
X.numobs == Y.numobs || throw(DimensionMismatch())
numobs = X.numobs
mutual_info::Float64 = 0
uniq_x = X.uniques
uniq_y = Y.uniques
for x in uniq_x
wherex = X.where[x]
px = X.p[x]
for y in uniq_y
wherey = Y.where[y]
py = Y.p[y]
pxy = length(intersect(wherex, wherey)) / numobs
if pxy > 0
mutual_info += pxy * log2(pxy / (px * py))
end
end
end
if normalized
mutual_info = mutual_info / log2(numobs)
end
return mutual_info
end
function bucket(X::Vector{Float64}, nrXbuckets::Int)
minX = minimum(X)
maxX = maximum(X)
stepX = (maxX - minX) / nrXbuckets
Xbucketed = zeros(Int, length(X))
for (idx,val) in enumerate(X)
Xbucketed[idx] = min(Int(div(val,stepX)), nrXbuckets - 1)
end
return Xbucketed
end
function mia(O::Matrix, P::Matrix, nrOfObuckets=9)
(ro,co) = size(O)
(rp,cp) = size(P)
C = zeros(Float64, co, cp)
if eltype(O) <: AbstractFloat
Ocolumndata = vec(mapslices(x -> MiaColumnData{Int}(bucket(x, nrOfObuckets)), O, 1))
else
Ocolumndata = vec(mapslices(MiaColumnData{eltype(O)}, O, 1))
end
# dump(Ocolumndata[1])
progress = Progress(co*cp,1)
for p in 1:cp
Pcolumndata = MiaColumnData{eltype(P)}(P[:,p])
for o in 1:co
C[o,p] = mia(Ocolumndata[o], Pcolumndata)
next!(progress)
end
end
finish!(progress)
return C
end
end