Using the same example from the quickstart, we explore how to get more out of the function find_adversarial_example
using MIPVerify
using Gurobi
using JuMP
using Images
using Printf
mnist = MIPVerify.read_datasets("MNIST")
n1 = MIPVerify.get_example_network_params("MNIST.n1")
sample_image = MIPVerify.get_image(mnist.test.images, 1);
function print_summary(d::Dict)
# Helper function to print out output
obj_val = JuMP.objective_value(d[:Model])
solve_time = JuMP.solve_time(d[:Model])
println("Objective Value: $(@sprintf("%.6f", obj_val)), Solve Time: $(@sprintf("%.2f", solve_time))")
end
function view_diff(diff::Array{<:Real, 2})
n = 1001
colormap("RdBu", n)[ceil.(Int, (diff .+ 1) ./ 2 .* n)]
end
view_diff (generic function with 1 method)
find_adversarial_example
¶find_adversarial_example
takes five positional arguments
find_adversarial_example(nn, input, target_selection, optimizer, main_solve_options)
It also takes named arguments, each with the default value specified.
norm_order = 1
invert_target_selection = false
pp = MIPVerify.UnrestrictedPerturbationFamily()
tightening_algorithm = mip
tightening_options: same as main solver, but with output suppressed and a time limit of 20s per solve.
We explore what each of these options allow us to do.
target_selection
and invert_target_selection
control what the category we want the adversarial example to be classified in.
target_selection
accepts either a single integer or a list of integers.
For example, if I wanted the original image (which is the digit 7) to be classified as the digit 8 or 9, I could run two separate solves with target_selection=9
and target_selection=10
(Julia is 1-indexed), finding closest adversarial examples at an $L_\infty$ distance 0.104073
and 0.046085
...
d = MIPVerify.find_adversarial_example(
n1,
sample_image,
9,
Gurobi.Optimizer,
# OutputFlag=0 prevents any output from being printed out
Dict("OutputFlag" => 0),
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.15),
norm_order = Inf,
tightening_algorithm = lp,
)
print_summary(d)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [9] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only
Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00 Imposing relu constraint: 100%|███████████████████████| Time: 0:00:00 Calculating upper bounds: 10%|██▎ | ETA: 0:02:50
Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:19 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00 Imposing relu constraint: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Objective Value: 0.104073, Solve Time: 531.95
d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("OutputFlag" => 0),
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.15),
norm_order = Inf,
tightening_algorithm = lp,
)
print_summary(d)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 40%|█████████▎ | ETA: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Objective Value: 0.046085, Solve Time: 44.76
Or I can can pass the targets as target_selection = [9, 10]
, where the same optimal value of 0.046085
is found.
Solve times for multiple target labels are typically on par with or faster than the aggregate solve times when solving with each target label in sequence.
d = MIPVerify.find_adversarial_example(
n1,
sample_image,
[9, 10],
Gurobi.Optimizer,
Dict("OutputFlag" => 0),
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.15),
norm_order = Inf,
tightening_algorithm = lp,
)
print_summary(d)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [9, 10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 10%|██▎ | ETA: 0:00:01
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Objective Value: 0.046085, Solve Time: 24.28
A common use case is to have the adversarial example being in any category but the original:
d = MIPVerify.find_adversarial_example(
n1,
sample_image,
[1, 2, 3, 4, 5, 6, 7, 9, 10],
Gurobi.Optimizer,
Dict("OutputFlag" => 0),
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.15),
norm_order = Inf,
tightening_algorithm = lp,
)
print_summary(d)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [1, 2, 3, 4, 5, 6, 7, 9, 10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 25%|█████▊ | ETA: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00 Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Objective Value: 0.046085, Solve Time: 102.45
Rather than typing the full list of other categories, we can set target_selection = 8
, and invert_target_selection = true
.
d = MIPVerify.find_adversarial_example(
n1,
sample_image,
8,
Gurobi.Optimizer,
Dict("OutputFlag" => 0),
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.15),
norm_order = Inf,
tightening_algorithm = lp,
invert_target_selection = true,
)
print_summary(d)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [1, 2, 3, 4, 5, 6, 7, 9, 10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 25%|█████▊ | ETA: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00 Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Objective Value: 0.046085, Solve Time: 107.32
d = @time MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("OutputFlag" => 0),
tightening_algorithm = lp,
norm_order = Inf,
)
print_summary(d)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 15%|███▌ | ETA: 0:00:01
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only 46.896601 seconds (4.36 M allocations: 177.896 MiB) Objective Value: 0.046085, Solve Time: 44.07
We can bound the $L_\infty$-norm of the perturbation.
As long as the size of the $L_\infty$-norm bound we choose is larger than the actual ($L_\infty$-)minimal perturbation, we will find the same result, and often more quickly.
d = @time MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("OutputFlag" => 0),
tightening_algorithm = lp,
norm_order=Inf,
)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 25%|█████▊ | ETA: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only 41.363017 seconds (2.07 M allocations: 68.034 MiB)
d = @time MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("OutputFlag" => 0),
tightening_algorithm = lp,
norm_order=Inf,
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.05)
)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only 14.070512 seconds (2.93 M allocations: 95.636 MiB)
If the $L_\infty$-norm bound you choose is smaller than the actual minimal perturbation, the problem is infeasible. If you observe the following solve status, there is provably no perturbation within the selected $L_\infty$-norm bound (in this case 0.03
) that is an adversarial example.
d = @time MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("OutputFlag" => 0),
tightening_algorithm = lp,
norm_order=Inf,
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.03)
)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Academic license - for non-commercial use only Academic license - for non-commercial use only 0.631356 seconds (2.27 M allocations: 75.066 MiB)
Dict{Any,Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 0.233993 :TotalTime => 0.609287 :Perturbation => VariableRef[noname noname … noname noname]… :PerturbedInput => VariableRef[noname noname … noname noname]… :TighteningApproach => "lp" :PerturbationFamily => linf-norm-bounded-0.03 :SolveStatus => INFEASIBLE_OR_UNBOUNDED :Model => A JuMP Model… :Output => GenericAffExpr{Float64,VariableRef}[0.0014746447222673… :PredictedIndex => 8
d[:SolveStatus]
INFEASIBLE_OR_UNBOUNDED::TerminationStatusCode = 6
We can restrict the perturbations to a blur; in this case, we select a 5x5 kernel. (Note that we are still minimizing over the norm of the perturbation.)
d = @time MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("OutputFlag" => 0),
tightening_algorithm = lp,
norm_order=Inf,
pp = MIPVerify.BlurringPerturbationFamily((5, 5))
)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 10%|██▎ | ETA: 0:00:01
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only 48.396935 seconds (4.98 M allocations: 216.330 MiB, 0.18% gc time)
diff = value.(d[:Perturbation])
view_diff(diff[1, :, :, 1])
d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("OutputFlag" => 0),
tightening_algorithm = lp,
norm_order=1
)
print_summary(d)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 10%|██▎ | ETA: 0:00:01
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Objective Value: 4.641859, Solve Time: 55.99
We also show the difference between the perturbed image and the original image. Red is areas of decreased brightness and blue is areas of increased brightness.
diff = value.(d[:Perturbation])
view_diff(diff[1, :, :, 1])
We can also minimize over the $L_\infty$ norm. This generally results in large patches of the image being changed.
In this case, the minimum $L_\infty$ norm perturbation required for the image to be classified as a 9
is 0.046085.
d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("OutputFlag" => 0),
tightening_algorithm = lp,
norm_order=Inf
)
print_summary(d)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 25%|█████▊ | ETA: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Objective Value: 0.046085, Solve Time: 42.74
diff = value.(d[:Perturbation])
view_diff(diff[1, :, :, 1])
With solvers that can handle MIQPs (like Gurobi), we can minimize over the $L_2$ norm. This generally takes a bit more time.
In this case, the minimum $L_2$ norm perturbation required for the image to be classified as a 9
is 0.705367 = sqrt(0.497542).
d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("OutputFlag" => 0),
tightening_algorithm = lp,
norm_order=2
)
print_summary(d)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 40%|█████████▎ | ETA: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Objective Value: 0.497542, Solve Time: 815.09
diff = value.(d[:Perturbation])
view_diff(diff[1, :, :, 1])
tightening_algorithm
¶By default, we tighten the bounds on each intermediate value by solving an MIP using the optimize
with the tightening_options
specified. Compare total solve times for three different tightening algorithms. As the tightening algorithm gets more complex (interval_arithmetic -> lp -> mip
), the time spent on tightening bounds increases, but generally (not in this case with mip
) with a reduction in the amount of time for the main solve.
You'll have to find the sweet spot for your own application.
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict(),
tightening_algorithm = interval_arithmetic,
norm_order=Inf
)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit. Academic license - for non-commercial use only Academic license - for non-commercial use only Academic license - for non-commercial use only Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64) Optimize a model with 1263 rows, 1020 columns and 66888 nonzeros Model fingerprint: 0xdc39e74c Variable types: 960 continuous, 60 integer (60 binary) Coefficient statistics: Matrix range [2e-05, 8e+02] Objective range [1e+00, 1e+00] Bounds range [5e-01, 4e+02] RHS range [4e-03, 8e+02] Presolve added 0 rows and 10 columns Presolve removed 50 rows and 0 columns Presolve time: 0.07s Presolved: 1213 rows, 1030 columns, 62933 nonzeros Variable types: 970 continuous, 60 integer (60 binary) Root relaxation: objective 0.000000e+00, 938 iterations, 0.05 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 0.00000 0 2 - 0.00000 - - 0s H 0 0 0.4967121 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 2 0.00000 0 2 0.49671 0.00000 100% - 0s H 29 31 0.0710671 0.00000 100% 250 1s 151 93 0.00448 7 10 0.07107 0.00000 100% 259 5s 406 136 cutoff 14 0.07107 0.00000 100% 202 10s H 420 131 0.0635998 0.00000 100% 200 10s H 546 154 0.0539995 0.00000 100% 189 12s H 567 144 0.0539995 0.00000 100% 188 12s 683 160 0.04687 8 4 0.05400 0.00448 91.7% 185 15s 973 183 infeasible 15 0.05400 0.00600 88.9% 171 20s 1308 212 cutoff 24 0.05400 0.00940 82.6% 166 25s 1801 234 cutoff 20 0.05400 0.02198 59.3% 146 30s * 1816 209 31 0.0502775 0.02198 56.3% 145 31s 2254 230 0.03211 13 10 0.05028 0.02944 41.4% 132 35s * 2352 191 31 0.0462748 0.02981 35.6% 129 35s H 2586 164 0.0460847 0.03250 29.5% 126 38s 2679 151 0.04096 25 3 0.04608 0.03325 27.9% 126 42s 2831 119 cutoff 19 0.04608 0.03599 21.9% 129 46s 3001 57 cutoff 23 0.04608 0.03950 14.3% 133 50s Cutting planes: Cover: 5 Implied bound: 35 MIR: 3 Flow cover: 7 Inf proof: 6 Explored 3276 nodes (429716 simplex iterations) in 52.10 seconds Thread count was 4 (of 4 available processors) Solution count 7: 0.0460847 0.0462748 0.0502775 ... 0.496712 Optimal solution found (tolerance 1.00e-04) Best objective 4.608468158892e-02, best bound 4.608468158892e-02, gap 0.0000% 52.207113 seconds (1.03 M allocations: 36.524 MiB)
Dict{Any,Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 52.0963 :TotalTime => 52.1851 :Perturbation => GenericAffExpr{Float64,VariableRef}[noname noname … no… :PerturbedInput => VariableRef[noname noname … noname noname]… :TighteningApproach => "interval_arithmetic" :PerturbationFamily => unrestricted :SolveStatus => OPTIMAL :Model => A JuMP Model… :Output => GenericAffExpr{Float64,VariableRef}[-0.012063867412507… :PredictedIndex => 8
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict(),
tightening_algorithm = lp,
norm_order=Inf
)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 35%|████████ | ETA: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64) Optimize a model with 1263 rows, 1020 columns and 66888 nonzeros Model fingerprint: 0x0202e6a7 Variable types: 960 continuous, 60 integer (60 binary) Coefficient statistics: Matrix range [2e-05, 7e+02] Objective range [1e+00, 1e+00] Bounds range [5e-01, 3e+02] RHS range [4e-03, 7e+02] Presolve added 0 rows and 10 columns Presolve removed 50 rows and 0 columns Presolve time: 0.09s Presolved: 1213 rows, 1030 columns, 62933 nonzeros Variable types: 970 continuous, 60 integer (60 binary) Root relaxation: objective 0.000000e+00, 837 iterations, 0.08 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 0.00000 0 1 - 0.00000 - - 0s H 0 0 0.4967121 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 2 0.00000 0 2 0.49671 0.00000 100% - 0s H 29 31 0.3535137 0.00000 100% 429 2s 67 89 0.01071 20 16 0.35351 0.00000 100% 423 5s H 95 102 0.2051025 0.00000 100% 369 5s * 145 139 42 0.2051025 0.00000 100% 320 6s 254 233 0.15085 15 8 0.20510 0.00000 100% 273 10s H 315 227 0.1476387 0.00000 100% 241 11s H 360 216 0.1309385 0.00000 100% 226 12s 496 245 infeasible 30 0.13094 0.00000 100% 196 15s * 736 285 40 0.1084155 0.00000 100% 178 19s H 764 249 0.0958362 0.00000 100% 178 21s H 810 268 0.0696157 0.00000 100% 176 24s 816 270 0.02997 25 5 0.06962 0.00000 100% 177 25s * 892 259 42 0.0574457 0.00447 92.2% 172 27s * 893 246 42 0.0574449 0.00447 92.2% 172 27s 985 240 0.03383 24 2 0.05744 0.00808 85.9% 168 30s * 1148 201 41 0.0564840 0.02084 63.1% 156 32s * 1149 191 41 0.0537551 0.02084 61.2% 156 32s * 1252 168 40 0.0502853 0.02545 49.4% 149 34s * 1255 145 40 0.0460847 0.02545 44.8% 149 34s 1334 124 0.03878 25 10 0.04608 0.02679 41.9% 144 35s 1734 111 cutoff 26 0.04608 0.03239 29.7% 127 40s Cutting planes: Gomory: 5 Projected implied bound: 3 MIR: 1 Flow cover: 3 Explored 2020 nodes (244073 simplex iterations) in 42.99 seconds Thread count was 4 (of 4 available processors) Solution count 10: 0.0460847 0.0502853 0.0537551 ... 0.130938 Optimal solution found (tolerance 1.00e-04) Best objective 4.608468158892e-02, best bound 4.608468158892e-02, gap 0.0000% 43.813121 seconds (2.18 M allocations: 73.722 MiB)
Dict{Any,Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 42.9934 :TotalTime => 43.6904 :Perturbation => GenericAffExpr{Float64,VariableRef}[noname noname … no… :PerturbedInput => VariableRef[noname noname … noname noname]… :TighteningApproach => "lp" :PerturbationFamily => unrestricted :SolveStatus => OPTIMAL :Model => A JuMP Model… :Output => GenericAffExpr{Float64,VariableRef}[-0.012063867412507… :PredictedIndex => 8
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict(),
tightening_algorithm = mip,
norm_order=Inf
)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 10%|██▎ | ETA: 0:00:42
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:02:17 Calculating lower bounds: 100%|███████████████████████| Time: 0:02:35
Academic license - for non-commercial use only Academic license - for non-commercial use only Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64) Optimize a model with 1263 rows, 1020 columns and 66888 nonzeros Model fingerprint: 0x04b67a3b Variable types: 960 continuous, 60 integer (60 binary) Coefficient statistics: Matrix range [2e-05, 7e+02] Objective range [1e+00, 1e+00] Bounds range [5e-01, 4e+02] RHS range [4e-03, 7e+02] Presolve added 0 rows and 10 columns Presolve removed 50 rows and 0 columns Presolve time: 0.06s Presolved: 1213 rows, 1030 columns, 62933 nonzeros Variable types: 970 continuous, 60 integer (60 binary) Root relaxation: objective 0.000000e+00, 792 iterations, 0.04 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 0.00000 0 4 - 0.00000 - - 0s H 0 0 0.5984254 0.00000 100% - 0s 0 0 0.00000 0 6 0.59843 0.00000 100% - 0s 0 0 0.00000 0 8 0.59843 0.00000 100% - 0s 0 0 0.00000 0 8 0.59843 0.00000 100% - 0s 0 0 0.00000 0 6 0.59843 0.00000 100% - 0s 0 0 0.00000 0 6 0.59843 0.00000 100% - 0s 0 0 0.00000 0 3 0.59843 0.00000 100% - 0s 0 0 0.00000 0 2 0.59843 0.00000 100% - 0s 0 0 0.00000 0 2 0.59843 0.00000 100% - 0s 0 0 0.00000 0 2 0.59843 0.00000 100% - 0s 0 2 0.00000 0 2 0.59843 0.00000 100% - 0s H 29 31 0.3535137 0.00000 100% 315 1s H 43 47 0.0976870 0.00000 100% 352 2s 140 106 0.00078 13 10 0.09769 0.00000 100% 289 5s H 226 109 0.0719725 0.00000 100% 234 6s * 265 107 30 0.0712215 0.00000 100% 235 7s H 336 119 0.0613848 0.00000 100% 227 9s 361 119 0.03817 23 5 0.06138 0.00000 100% 221 10s H 392 118 0.0584827 0.00000 100% 220 10s * 396 118 30 0.0584544 0.00000 100% 221 10s 546 144 0.03002 8 6 0.05845 0.00000 100% 226 15s 753 183 cutoff 17 0.05845 0.01146 80.4% 210 20s 928 239 cutoff 14 0.05845 0.02208 62.2% 208 26s 1138 266 0.03425 14 4 0.05845 0.02460 57.9% 203 30s * 1194 265 26 0.0565325 0.02491 55.9% 205 31s H 1318 197 0.0498354 0.02712 45.6% 203 34s 1367 203 0.02847 15 5 0.04984 0.02838 43.1% 202 35s * 1431 181 24 0.0460847 0.02863 37.9% 203 36s 1651 190 infeasible 25 0.04608 0.03074 33.3% 201 41s 1868 170 0.04118 29 2 0.04608 0.03473 24.6% 203 46s 2170 130 0.04593 22 2 0.04608 0.03748 18.7% 198 51s 2370 63 0.04523 12 4 0.04608 0.03884 15.7% 198 56s Cutting planes: Cover: 3 Implied bound: 15 MIR: 7 Flow cover: 15 Inf proof: 1 RLT: 7 Relax-and-lift: 1 Explored 2616 nodes (505401 simplex iterations) in 59.17 seconds Thread count was 4 (of 4 available processors) Solution count 10: 0.0460847 0.0498354 0.0565325 ... 0.353514 Optimal solution found (tolerance 1.00e-04) Best objective 4.608468158892e-02, best bound 4.608468158892e-02, gap 0.0000% 359.844930 seconds (1.54 M allocations: 53.731 MiB)
Dict{Any,Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 59.1741 :TotalTime => 359.826 :Perturbation => GenericAffExpr{Float64,VariableRef}[noname noname … no… :PerturbedInput => VariableRef[noname noname … noname noname]… :TighteningApproach => "mip" :PerturbationFamily => unrestricted :SolveStatus => OPTIMAL :Model => A JuMP Model… :Output => GenericAffExpr{Float64,VariableRef}[-0.012063867412507… :PredictedIndex => 8
We can also modify many of the parameters of the solver to change behavior:
We will be focusing on the parameters available via Gurobi (http://www.gurobi.com/documentation/9.0/refman/parameters.html), but other solvers often have similar options.
Sometimes, finding an adversarial example takes a long time:
You may want to terminate early when a particular condition is satisfied. Common reasons are:
BestBd
increases above a pre-determined threshold)Incumbent
adversarial image found that is closer to the original image than expected).Incumbent
and BestBd
falls below a pre-determined threshold.Fortunately, Gurobi has a parameter for all of these cases.
Set TimeLimit
:
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("TimeLimit" => 10),
tightening_algorithm = lp,
norm_order=Inf
)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 10%|██▎ | ETA: 0:00:01
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64) Optimize a model with 1263 rows, 1020 columns and 66888 nonzeros Model fingerprint: 0x0202e6a7 Variable types: 960 continuous, 60 integer (60 binary) Coefficient statistics: Matrix range [2e-05, 7e+02] Objective range [1e+00, 1e+00] Bounds range [5e-01, 3e+02] RHS range [4e-03, 7e+02] Presolve added 0 rows and 10 columns Presolve removed 50 rows and 0 columns Presolve time: 0.11s Presolved: 1213 rows, 1030 columns, 62933 nonzeros Variable types: 970 continuous, 60 integer (60 binary) Root relaxation: objective 0.000000e+00, 837 iterations, 0.07 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 0.00000 0 1 - 0.00000 - - 0s H 0 0 0.4967121 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 2 0.00000 0 2 0.49671 0.00000 100% - 0s H 29 31 0.3535137 0.00000 100% 429 2s 88 102 0.02818 25 9 0.35351 0.00000 100% 379 5s H 95 102 0.2051025 0.00000 100% 369 5s * 145 139 42 0.2051025 0.00000 100% 320 6s 254 228 0.15085 15 8 0.20510 0.00000 100% 273 10s Cutting planes: MIR: 3 Flow cover: 4 Explored 300 nodes (75240 simplex iterations) in 10.00 seconds Thread count was 4 (of 4 available processors) Solution count 3: 0.205102 0.353514 0.496712 Time limit reached Best objective 2.051024945226e-01, best bound 0.000000000000e+00, gap 100.0000% 10.854215 seconds (2.07 M allocations: 68.026 MiB)
Dict{Any,Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 10.0028 :TotalTime => 10.8295 :Perturbation => GenericAffExpr{Float64,VariableRef}[noname noname … no… :PerturbedInput => VariableRef[noname noname … noname noname]… :TighteningApproach => "lp" :PerturbationFamily => unrestricted :SolveStatus => TIME_LIMIT :Model => A JuMP Model… :Output => GenericAffExpr{Float64,VariableRef}[-0.012063867412507… :PredictedIndex => 8
Set BestBdStop
.
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("BestBdStop" => 0.02),
tightening_algorithm = lp,
norm_order=Inf
)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 40%|█████████▎ | ETA: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64) Optimize a model with 1263 rows, 1020 columns and 66888 nonzeros Model fingerprint: 0x0202e6a7 Variable types: 960 continuous, 60 integer (60 binary) Coefficient statistics: Matrix range [2e-05, 7e+02] Objective range [1e+00, 1e+00] Bounds range [5e-01, 3e+02] RHS range [4e-03, 7e+02] Presolve added 0 rows and 10 columns Presolve removed 50 rows and 0 columns Presolve time: 0.09s Presolved: 1213 rows, 1030 columns, 62933 nonzeros Variable types: 970 continuous, 60 integer (60 binary) Root relaxation: objective 0.000000e+00, 837 iterations, 0.07 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 0.00000 0 1 - 0.00000 - - 0s H 0 0 0.4967121 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 2 0.00000 0 2 0.49671 0.00000 100% - 0s H 29 31 0.3535137 0.00000 100% 429 2s 88 102 0.02818 25 9 0.35351 0.00000 100% 379 5s H 95 102 0.2051025 0.00000 100% 369 5s * 145 139 42 0.2051025 0.00000 100% 320 6s 313 263 0.10418 23 10 0.20510 0.00000 100% 242 10s H 315 227 0.1476387 0.00000 100% 241 10s H 360 216 0.1309385 0.00000 100% 226 11s 599 286 0.12051 22 11 0.13094 0.00000 100% 186 15s * 736 285 40 0.1084155 0.00000 100% 178 18s H 764 249 0.0958362 0.00000 100% 178 19s 765 248 0.09385 21 2 0.09584 0.00000 100% 178 20s H 810 268 0.0696157 0.00000 100% 176 22s 871 273 0.03477 19 9 0.06962 0.00447 93.6% 175 25s * 892 259 42 0.0574457 0.00447 92.2% 172 25s * 893 246 42 0.0574449 0.00447 92.2% 172 25s * 1148 201 41 0.0564840 0.02084 63.1% 156 29s * 1149 191 41 0.0537551 0.02084 61.2% 156 29s Cutting planes: Gomory: 5 Projected implied bound: 3 MIR: 1 Flow cover: 3 Explored 1153 nodes (180859 simplex iterations) in 29.40 seconds Thread count was 4 (of 4 available processors) Solution count 10: 0.0537551 0.056484 0.0574449 ... 0.205102 Optimization achieved user objective limit Best objective 5.375506126689e-02, best bound 2.084402587199e-02, gap 61.2241% 30.399972 seconds (2.31 M allocations: 80.203 MiB, 0.22% gc time)
Dict{Any,Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 29.3971 :TotalTime => 30.2711 :Perturbation => GenericAffExpr{Float64,VariableRef}[noname noname … no… :PerturbedInput => VariableRef[noname noname … noname noname]… :TighteningApproach => "lp" :PerturbationFamily => unrestricted :SolveStatus => OBJECTIVE_LIMIT :Model => A JuMP Model… :Output => GenericAffExpr{Float64,VariableRef}[-0.012063867412507… :PredictedIndex => 8
Set BestObjStop
.
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("BestObjStop" => 0.2),
tightening_algorithm = lp,
norm_order=Inf
)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 30%|██████▉ | ETA: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64) Optimize a model with 1263 rows, 1020 columns and 66888 nonzeros Model fingerprint: 0x0202e6a7 Variable types: 960 continuous, 60 integer (60 binary) Coefficient statistics: Matrix range [2e-05, 7e+02] Objective range [1e+00, 1e+00] Bounds range [5e-01, 3e+02] RHS range [4e-03, 7e+02] Presolve added 0 rows and 10 columns Presolve removed 50 rows and 0 columns Presolve time: 0.07s Presolved: 1213 rows, 1030 columns, 62933 nonzeros Variable types: 970 continuous, 60 integer (60 binary) Root relaxation: objective 0.000000e+00, 837 iterations, 0.05 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 0.00000 0 1 - 0.00000 - - 0s H 0 0 0.4967121 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 2 0.00000 0 2 0.49671 0.00000 100% - 0s H 29 31 0.3535137 0.00000 100% 429 1s 67 89 0.01071 20 16 0.35351 0.00000 100% 423 5s H 95 102 0.2051025 0.00000 100% 369 5s * 145 139 42 0.2051025 0.00000 100% 320 7s 254 233 0.15085 15 8 0.20510 0.00000 100% 273 10s H 315 227 0.1476387 0.00000 100% 241 11s Cutting planes: Implied bound: 2 MIR: 3 Flow cover: 4 Explored 349 nodes (80689 simplex iterations) in 11.58 seconds Thread count was 4 (of 4 available processors) Solution count 4: 0.147639 0.205102 0.353514 0.496712 Optimization achieved user objective limit Best objective 1.476386863211e-01, best bound 0.000000000000e+00, gap 100.0000% 12.117183 seconds (2.07 M allocations: 68.014 MiB)
Dict{Any,Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 11.5785 :TotalTime => 12.0981 :Perturbation => GenericAffExpr{Float64,VariableRef}[noname noname … no… :PerturbedInput => VariableRef[noname noname … noname noname]… :TighteningApproach => "lp" :PerturbationFamily => unrestricted :SolveStatus => OBJECTIVE_LIMIT :Model => A JuMP Model… :Output => GenericAffExpr{Float64,VariableRef}[-0.012063867412507… :PredictedIndex => 8
Incumbent
and BestBd
is below threshold¶Set MIPGap
.
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
Gurobi.Optimizer,
Dict("MIPGap" => 0.4),
tightening_algorithm = lp,
norm_order=Inf
)
Academic license - for non-commercial use only [notice | MIPVerify]: Attempting to find adversarial example. Neural net predicted label is 8, target labels are [10] [notice | MIPVerify]: Determining upper and lower bounds for the input to each non-linear unit.
Calculating upper bounds: 20%|████▋ | ETA: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only
Calculating upper bounds: 100%|███████████████████████| Time: 0:00:00 Calculating lower bounds: 100%|███████████████████████| Time: 0:00:00
Academic license - for non-commercial use only Academic license - for non-commercial use only Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64) Optimize a model with 1263 rows, 1020 columns and 66888 nonzeros Model fingerprint: 0x0202e6a7 Variable types: 960 continuous, 60 integer (60 binary) Coefficient statistics: Matrix range [2e-05, 7e+02] Objective range [1e+00, 1e+00] Bounds range [5e-01, 3e+02] RHS range [4e-03, 7e+02] Presolve added 0 rows and 10 columns Presolve removed 50 rows and 0 columns Presolve time: 0.09s Presolved: 1213 rows, 1030 columns, 62933 nonzeros Variable types: 970 continuous, 60 integer (60 binary) Root relaxation: objective 0.000000e+00, 837 iterations, 0.07 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time 0 0 0.00000 0 1 - 0.00000 - - 0s H 0 0 0.4967121 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 0 0.00000 0 2 0.49671 0.00000 100% - 0s 0 2 0.00000 0 2 0.49671 0.00000 100% - 0s H 29 31 0.3535137 0.00000 100% 429 2s H 95 102 0.2051025 0.00000 100% 369 4s 101 117 0.05359 29 9 0.20510 0.00000 100% 364 5s * 145 139 42 0.2051025 0.00000 100% 320 6s 313 263 0.10418 23 10 0.20510 0.00000 100% 242 10s H 315 227 0.1476387 0.00000 100% 241 10s H 360 216 0.1309385 0.00000 100% 226 10s 599 286 0.12051 22 11 0.13094 0.00000 100% 186 16s * 736 285 40 0.1084155 0.00000 100% 178 18s H 764 249 0.0958362 0.00000 100% 178 20s H 810 268 0.0696157 0.00000 100% 176 23s 865 267 infeasible 38 0.06962 0.00447 93.6% 175 25s * 892 259 42 0.0574457 0.00447 92.2% 172 25s * 893 246 42 0.0574449 0.00447 92.2% 172 25s * 1148 201 41 0.0564840 0.02084 63.1% 156 29s * 1149 191 41 0.0537551 0.02084 61.2% 156 29s 1199 182 cutoff 26 0.05376 0.02293 57.3% 153 30s * 1252 168 40 0.0502853 0.02545 49.4% 149 30s * 1255 145 40 0.0460847 0.02545 44.8% 149 30s Cutting planes: Gomory: 5 Projected implied bound: 3 MIR: 1 Flow cover: 3 Explored 1401 nodes (197770 simplex iterations) in 31.95 seconds Thread count was 4 (of 4 available processors) Solution count 10: 0.0460847 0.0502853 0.0537551 ... 0.130938 Optimal solution found (tolerance 4.00e-01) Best objective 4.608468158892e-02, best bound 2.895634473127e-02, gap 37.1671% 32.665103 seconds (2.07 M allocations: 68.027 MiB)
Dict{Any,Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 31.9488 :TotalTime => 32.6446 :Perturbation => GenericAffExpr{Float64,VariableRef}[noname noname … no… :PerturbedInput => VariableRef[noname noname … noname noname]… :TighteningApproach => "lp" :PerturbationFamily => unrestricted :SolveStatus => OPTIMAL :Model => A JuMP Model… :Output => GenericAffExpr{Float64,VariableRef}[-0.012063867412507… :PredictedIndex => 8
Whew! That was a lot. The next tutorial will introduce you to everything you can extract from the results dictionary.