Using the same example from the quickstart, we explore how to get more out of the function find_adversarial_example
using MIPVerify
using HiGHS
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.
invert_target_selection = false
pp = MIPVerify.UnrestrictedPerturbationFamily()
norm_order = 1
adversarial_example_objective = closest
tightening_algorithm = mip
tightening_options: same as main solver, but with output suppressed and a time limit of 20s per solve.
solve_if_predicted_in_targeted = true
We explore what some 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,
HiGHS.Optimizer,
Dict("output_flag" => false),
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.105),
norm_order = Inf,
tightening_algorithm = lp,
)
print_summary(d)
[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. Objective Value: 0.104073, Solve Time: 105.14
d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
HiGHS.Optimizer,
Dict("output_flag" => false),
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.105),
norm_order = Inf,
tightening_algorithm = lp,
)
print_summary(d)
[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. Objective Value: 0.046085, Solve Time: 281.74
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],
HiGHS.Optimizer,
Dict("output_flag" => false),
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.105),
norm_order = Inf,
tightening_algorithm = lp,
)
print_summary(d)
[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. Objective Value: 0.046085, Solve Time: 545.51
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],
HiGHS.Optimizer,
Dict("output_flag" => false),
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.105),
norm_order = Inf,
tightening_algorithm = lp,
)
print_summary(d)
[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. Objective Value: 0.046085, Solve Time: 2708.19
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,
HiGHS.Optimizer,
Dict("output_flag" => false),
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.105),
norm_order = Inf,
tightening_algorithm = lp,
invert_target_selection = true,
)
print_summary(d)
[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. Objective Value: 0.046085, Solve Time: 2711.58
d = @time MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
HiGHS.Optimizer,
Dict("output_flag" => false),
tightening_algorithm = lp,
norm_order = Inf,
)
print_summary(d)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
[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. 546.409633 seconds (4.17 M allocations: 191.573 MiB, 0.17% compilation time) Objective Value: 0.046085, Solve Time: 545.13
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,
HiGHS.Optimizer,
Dict("output_flag" => false),
tightening_algorithm = lp,
norm_order=Inf,
)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
[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. 546.924763 seconds (1.90 M allocations: 72.457 MiB)
d = @time MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
HiGHS.Optimizer,
Dict("output_flag" => false),
tightening_algorithm = lp,
norm_order=Inf,
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.05)
)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
[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. 21.179666 seconds (2.99 M allocations: 102.860 MiB, 0.07% compilation time)
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,
HiGHS.Optimizer,
Dict("output_flag" => false),
tightening_algorithm = lp,
norm_order=Inf,
pp = MIPVerify.LInfNormBoundedPerturbationFamily(0.03)
)
[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. 0.336244 seconds (2.75 M allocations: 91.080 MiB, 20.55% gc time)
Dict{Any, Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 0.0551291 :TotalTime => 0.336011 :Perturbation => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :PerturbedInput => [_[785] _[786] … _[811] _[812];;; _[813] _[814] … _[83… :TighteningApproach => "lp" :PerturbationFamily => linf-norm-bounded-0.03 :SolveStatus => INFEASIBLE :Model => A JuMP Model… :Output => AffExpr[0.0014746447222673583 _[785] + 0.0086289714433… :PredictedIndex => 8
d[:SolveStatus]
INFEASIBLE::TerminationStatusCode = 2
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,
HiGHS.Optimizer,
Dict("output_flag" => false),
tightening_algorithm = lp,
norm_order=Inf,
pp = MIPVerify.BlurringPerturbationFamily((5, 5))
)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
[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. 164.483624 seconds (4.45 M allocations: 210.833 MiB, 0.56% compilation time)
diff = value.(d[:Perturbation])
view_diff(diff[1, :, :, 1])
d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
HiGHS.Optimizer,
Dict("output_flag" => false),
tightening_algorithm = lp,
norm_order=1
)
print_summary(d)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
[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. Objective Value: 4.641859, Solve Time: 364.94
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,
HiGHS.Optimizer,
Dict("output_flag" => false),
tightening_algorithm = lp,
norm_order=Inf
)
print_summary(d)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[1, :, :, 1])
[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. Objective Value: 0.046085, Solve Time: 545.87
diff = value.(d[:Perturbation])
view_diff(diff[1, :, :, 1])
HiGHS is unable to solve MIQPs. With a solver that can (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,
HiGHS.Optimizer,
Dict("output_flag" => false),
tightening_algorithm = lp,
norm_order=2
)
print_summary(d)
perturbed_sample_image = value.(d[:PerturbedInput])
colorview(Gray, perturbed_sample_image[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,
HiGHS.Optimizer,
Dict("output_flag" => true),
tightening_algorithm = interval_arithmetic,
norm_order=Inf
)
[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. Running HiGHS 1.4.2 [date: 1970-01-01, git hash: f797c1ab6] Copyright (c) 2022 ERGO-Code under MIT licence terms Presolving model 1203 rows, 1020 cols, 66828 nonzeros 1203 rows, 1020 cols, 66828 nonzeros Solving MIP model with: 1203 rows 1020 cols (60 binary, 0 integer, 0 implied int., 960 continuous) 66828 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s 0 0 0 0.00% 0 inf inf 0 0 36 1463 0.1s R 0 0 0 0.00% 0 0.9762283995 100.00% 2171 33 470 1944 1.2s L 0 0 0 0.00% 0 0.1207006013 100.00% 2957 57 470 2173 9.2s 1.7% inactive integer columns, restarting Model after restart has 1201 rows, 1019 cols (59 bin., 0 int., 0 impl., 960 cont.), and 66040 nonzeros 0 0 0 0.00% 0 0.1207006013 100.00% 28 0 0 32363 9.4s 0 0 0 0.00% 0 0.1207006013 100.00% 28 25 7 33215 9.5s 25 0 3 0.01% 0 0.1207006013 100.00% 343 21 30 56164 14.5s 73 7 26 0.01% 0 0.1207006013 100.00% 442 21 151 79215 19.6s 112 24 39 0.01% 0 0.1207006013 100.00% 545 25 206 157481 49.4s 130 26 48 0.02% 0 0.1207006013 100.00% 607 25 268 181462 54.6s 169 27 66 0.03% 0 0.1207006013 100.00% 665 25 333 205801 59.8s 243 46 96 0.71% 0 0.1207006013 100.00% 809 29 410 230041 64.8s 314 68 121 0.88% 0 0.1207006013 100.00% 903 34 483 451096 136.0s 440 102 164 0.96% 0 0.1207006013 100.00% 909 20 551 473896 141.1s 556 124 210 1.02% 0 0.1207006013 100.00% 859 24 634 499140 146.2s 662 158 244 1.12% 0 0.1207006013 100.00% 892 31 683 526871 151.2s 844 216 305 1.23% 0 0.1207006013 100.00% 1022 24 793 559188 157.4s Restarting search from the root node Model after restart has 1195 rows, 1016 cols (56 bin., 0 int., 0 impl., 960 cont.), and 63676 nonzeros 927 0 0 0.00% 0 0.1207006013 100.00% 24 0 0 563551 158.5s 927 0 0 0.00% 0 0.1207006013 100.00% 24 14 10 564129 158.6s 1041 32 35 8.05% 0 0.1207006013 100.00% 628 30 49 581479 164.2s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 1258 93 111 9.97% 0 0.1207006013 100.00% 744 34 168 606167 169.3s 1531 205 200 10.06% 0 0.1207006013 100.00% 845 20 292 630027 174.4s 1743 272 269 10.14% 0 0.1207006013 100.00% 934 32 387 662384 180.4s 1945 339 337 10.17% 0 0.1207006013 100.00% 1028 30 463 692459 186.4s 2027 351 370 10.19% 0 0.1207006013 100.00% 1067 30 527 723490 191.7s 2152 401 406 10.23% 0 0.1207006013 100.00% 1228 38 572 752213 198.3s 2289 443 456 10.26% 0 0.1207006013 100.00% 1320 44 630 779367 203.3s 2445 483 516 10.27% 0 0.1207006013 100.00% 1400 49 694 803101 208.3s Restarting search from the root node Model after restart has 1195 rows, 1016 cols (56 bin., 0 int., 0 impl., 960 cont.), and 63676 nonzeros 2556 0 0 0.00% 0 0.1207006013 100.00% 52 0 0 826221 213.1s 2556 0 0 0.00% 0 0.1207006013 100.00% 52 17 4 826873 213.2s 2618 14 13 5.04% 0 0.1207006013 100.00% 539 26 21 847429 218.2s 2875 98 106 13.04% 0 0.1207006013 100.00% 746 22 135 871799 223.2s 3010 142 149 14.14% 0 0.1207006013 100.00% 898 30 189 896571 228.3s 3195 199 218 15.41% 0 0.1207006013 100.00% 1140 26 282 918971 233.4s 3408 251 295 17.36% 0 0.1207006013 100.00% 1533 29 429 946021 239.2s 3607 299 371 17.62% 0 0.1207006013 100.00% 1649 37 564 972977 244.4s 3766 335 430 17.72% 0 0.1207006013 100.00% 2468 39 638 999802 250.5s 3841 349 462 18.91% 0 0.1207006013 100.00% 2845 33 678 1022k 255.6s 3940 371 502 19.55% 0 0.1207006013 100.00% 3091 49 726 1043k 260.6s 4162 417 586 20.03% 0 0.1207006013 100.00% 3253 41 836 1069k 265.6s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 4322 450 649 25.87% 0 0.1207006013 100.00% 3551 27 923 1094k 271.3s 4459 477 700 28.72% 0 0.1207006013 100.00% 4440 54 1000 1110k 276.3s 4628 528 761 29.38% 0 0.1207006013 100.00% 4616 67 1076 1131k 281.6s 4828 574 838 29.87% 0 0.1207006013 100.00% 4521 47 1182 1152k 286.8s 4998 617 899 32.86% 0 0.1207006013 100.00% 4732 62 1249 1174k 291.9s 5130 649 950 35.91% 0 0.1207006013 100.00% 4997 62 1315 1195k 297.2s 5337 703 1025 37.47% 0 0.1207006013 100.00% 5348 51 1410 1217k 303.0s 5502 740 1087 38.39% 0 0.1207006013 100.00% 5520 48 1499 1237k 308.0s 5695 797 1153 39.44% 0 0.1207006013 100.00% 5860 64 1586 1257k 313.0s 5952 871 1247 41.17% 0 0.1207006013 100.00% 5719 34 1721 1276k 318.4s 6080 892 1297 41.37% 0 0.1207006013 100.00% 5155 50 1784 1296k 323.4s 6364 975 1392 41.73% 0 0.1207006013 100.00% 5127 69 1907 1327k 330.2s 6451 998 1426 41.74% 0 0.1207006013 100.00% 5157 69 1947 1353k 335.4s 6601 1030 1479 41.86% 0 0.1207006013 100.00% 5170 46 2025 1380k 340.7s 6677 1051 1507 42.13% 0 0.1207006013 100.00% 5177 50 2055 1408k 345.8s 6738 1057 1535 42.13% 0 0.1207006013 100.00% 5255 54 2085 1431k 350.9s 6777 1057 1554 42.13% 0 0.1207006013 100.00% 5299 60 2112 1461k 356.1s 6915 1090 1605 42.16% 0 0.1207006013 100.00% 5238 42 2171 1484k 361.1s 7095 1125 1678 42.18% 0 0.1207006013 100.00% 5280 54 2253 1507k 366.2s 7207 1143 1724 42.18% 0 0.1207006013 100.00% 5289 23 2324 1533k 371.3s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 7352 1178 1777 42.18% 0 0.1207006013 100.00% 5384 29 2396 1558k 376.3s 7467 1201 1822 42.21% 0 0.1207006013 100.00% 4597 60 2447 1576k 381.8s 7606 1227 1876 43.14% 0 0.1207006013 100.00% 4782 70 2520 1598k 386.8s 7747 1262 1927 43.93% 0 0.1207006013 100.00% 5006 56 2578 1621k 392.0s 7954 1303 2009 45.17% 0 0.1207006013 100.00% 5143 40 2675 1639k 397.1s 8135 1351 2072 45.57% 0 0.1207006013 100.00% 5310 45 2750 1659k 402.1s 8239 1377 2112 45.72% 0 0.1207006013 100.00% 5488 77 2804 1680k 407.2s 8412 1422 2171 45.75% 0.000200475575 0.1207006013 99.83% 5718 47 2865 1702k 412.2s 8538 1446 2221 45.89% 0.000200475575 0.1207006013 99.83% 6062 49 2922 1724k 417.9s 8665 1476 2271 45.89% 0.000200475575 0.1207006013 99.83% 6279 48 2981 1741k 422.9s 8824 1497 2337 45.92% 0.000200475575 0.1207006013 99.83% 6710 41 3074 1761k 428.7s 8969 1524 2396 47.19% 0.000200475575 0.1207006013 99.83% 6997 70 3140 1782k 433.7s 9107 1550 2447 48.49% 0.000211862717 0.1207006013 99.82% 7319 89 3200 1803k 438.7s 9193 1571 2484 48.49% 0.000211862717 0.1207006013 99.82% 7392 54 3247 1824k 443.9s 9267 1584 2513 48.50% 0.000211862717 0.1207006013 99.82% 7178 80 3288 1842k 448.9s 9315 1589 2533 48.52% 0.000211862717 0.1207006013 99.82% 7672 92 3314 1859k 454.2s 9416 1604 2572 49.32% 0.000211862717 0.1207006013 99.82% 8122 126 3371 1876k 459.2s 9486 1614 2605 49.76% 0.000211862717 0.1207006013 99.82% 8264 73 3426 1895k 464.3s 9553 1620 2636 49.81% 0.00259246277 0.1207006013 97.85% 8339 91 3470 1919k 469.4s 9695 1646 2693 49.82% 0.00259246277 0.1207006013 97.85% 7849 62 3537 1940k 474.4s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time T 9753 922 2711 53.59% 0.00259246277 0.1106506926 97.66% 7864 62 3555 1945k 475.5s 9802 934 2734 53.67% 0.00259246277 0.1106506926 97.66% 7613 62 3580 1961k 480.5s 9888 951 2767 53.77% 0.00259246277 0.1106506926 97.66% 7414 73 3614 1984k 485.6s 9933 952 2791 53.78% 0.00259246277 0.1106506926 97.66% 7620 52 3642 2001k 490.7s 10034 974 2830 53.78% 0.00259246277 0.1106506926 97.66% 7539 77 3684 2023k 496.4s 10145 994 2871 53.80% 0.0031911298 0.1106506926 97.12% 7326 60 3730 2040k 501.4s 10260 1015 2917 53.81% 0.0031911298 0.1106506926 97.12% 7227 77 3778 2058k 506.5s T 10275 648 2919 58.89% 0.0031911298 0.1009421341 96.84% 7229 77 3780 2059k 506.7s T 10280 306 2922 67.04% 0.0031911298 0.0785359347 95.94% 7232 77 3782 2059k 506.7s 10373 324 2962 68.98% 0.0031911298 0.0785359347 95.94% 7220 98 3825 2080k 511.8s 10496 348 3012 69.29% 0.0031911298 0.0785359347 95.94% 7316 83 3896 2099k 517.2s 10547 350 3038 69.65% 0.00392446141 0.0785359347 95.00% 7491 75 3929 2124k 522.2s 10714 385 3102 70.25% 0.00392446141 0.0785359347 95.00% 7675 39 4011 2149k 527.2s 10779 404 3125 70.30% 0.00392446141 0.0785359347 95.00% 8495 76 4039 2163k 532.3s 10854 407 3161 70.36% 0.0044718657 0.0785359347 94.31% 8471 47 4095 2185k 537.3s 10962 432 3203 70.36% 0.0044718657 0.0785359347 94.31% 8392 63 4151 2205k 542.4s 11016 438 3227 70.38% 0.0044718657 0.0785359347 94.31% 8420 102 4185 2222k 547.5s 11076 444 3254 70.38% 0.0044718657 0.0785359347 94.31% 7699 77 4216 2243k 552.6s 11151 450 3287 70.39% 0.00598983999 0.0785359347 92.37% 7705 71 4262 2267k 559.0s 11207 460 3311 70.53% 0.00598983999 0.0785359347 92.37% 8162 103 4297 2285k 564.2s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time T 11224 443 3314 70.56% 0.00598983999 0.0776398122 92.29% 8165 103 4301 2285k 564.4s T 11236 430 3320 70.64% 0.00598983999 0.076787908 92.20% 8170 103 4306 2286k 564.6s 11351 455 3368 70.92% 0.00598983999 0.076787908 92.20% 7919 91 4381 2304k 569.8s 11474 475 3419 71.51% 0.00598983999 0.076787908 92.20% 8302 56 4457 2325k 574.8s 11558 496 3451 71.54% 0.00598983999 0.076787908 92.20% 8476 65 4493 2343k 579.9s 11643 514 3482 71.55% 0.00598983999 0.076787908 92.20% 8298 92 4534 2362k 584.9s 11740 526 3527 71.71% 0.00598983999 0.076787908 92.20% 8464 25 4589 2383k 590.0s 11863 546 3577 72.83% 0.00598983999 0.076787908 92.20% 8758 38 4663 2406k 595.1s 11893 548 3593 73.36% 0.00598983999 0.076787908 92.20% 8727 104 4684 2420k 600.1s 11952 549 3621 73.39% 0.00598983999 0.076787908 92.20% 8700 91 4718 2439k 605.5s 12043 562 3658 73.53% 0.00598983999 0.076787908 92.20% 8736 91 4774 2460k 610.8s 12096 568 3678 73.57% 0.00598983999 0.076787908 92.20% 8976 66 4795 2477k 615.9s 12180 589 3708 73.59% 0.00598983999 0.076787908 92.20% 9194 74 4833 2497k 621.0s 12245 604 3732 73.64% 0.00598983999 0.076787908 92.20% 8986 92 4863 2514k 626.0s 12345 625 3770 73.73% 0.00598983999 0.076787908 92.20% 7805 65 4920 2536k 632.4s 12437 645 3806 73.74% 0.00598983999 0.076787908 92.20% 7841 65 4963 2556k 637.4s 12543 667 3849 74.41% 0.00598983999 0.076787908 92.20% 7640 76 5024 2576k 642.6s 12576 664 3867 74.57% 0.00598983999 0.076787908 92.20% 7910 113 4907 2591k 647.7s 12655 670 3901 74.61% 0.00598983999 0.076787908 92.20% 7570 74 4760 2609k 652.8s 12748 681 3942 74.94% 0.00598983999 0.076787908 92.20% 7484 80 4718 2627k 657.8s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 12816 698 3968 74.95% 0.00598983999 0.076787908 92.20% 7682 57 4654 2641k 663.1s 12885 707 3997 75.03% 0.00598983999 0.076787908 92.20% 8156 71 4572 2660k 668.1s 13027 734 4056 80.85% 0.00598983999 0.076787908 92.20% 8237 82 4583 2683k 673.2s T 13041 438 4059 86.15% 0.00598983999 0.0635998471 90.58% 8240 82 4586 2683k 673.4s T 13054 392 4065 86.25% 0.00598983999 0.0592820117 89.90% 8245 82 4593 2684k 673.6s 13126 403 4098 86.58% 0.00598983999 0.0592820117 89.90% 7902 32 4546 2703k 679.1s 13180 400 4126 86.92% 0.00598986619 0.0592820117 89.90% 7658 60 4454 2718k 684.5s T 13268 390 4158 88.66% 0.00598986619 0.0570215405 89.50% 7595 22 4335 2728k 688.2s T 13272 389 4160 88.66% 0.00598986619 0.0569527392 89.48% 7597 22 4336 2728k 688.2s T 13276 338 4162 89.12% 0.00598986619 0.0537550613 88.86% 7598 22 4337 2728k 688.3s T 13305 285 4173 89.20% 0.00598986619 0.0502852709 88.09% 7572 28 4289 2731k 689.3s T 13320 221 4180 91.15% 0.00598986619 0.0460846816 87.00% 7579 28 4296 2733k 689.7s 13380 227 4209 91.18% 0.0102990452 0.0460846816 77.65% 7830 64 4144 2748k 694.7s 13446 222 4241 91.25% 0.0102990452 0.0460846816 77.65% 7507 56 3976 2764k 699.7s 13508 217 4273 93.70% 0.0116816257 0.0460846816 74.65% 7369 56 3691 2789k 705.0s 13585 220 4311 93.70% 0.0136657429 0.0460846816 70.35% 6358 36 3402 2805k 710.3s 13650 217 4345 93.72% 0.0136657429 0.0460846816 70.35% 5314 50 3181 2823k 715.5s 13706 214 4374 94.60% 0.013766096 0.0460846816 70.13% 5002 57 2939 2841k 720.6s 13768 217 4403 94.61% 0.013766096 0.0460846816 70.13% 5317 31 2794 2855k 725.6s 13820 207 4434 94.66% 0.0155336272 0.0460846816 66.29% 4638 38 2548 2877k 730.9s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 13879 202 4465 94.84% 0.015877494 0.0460846816 65.55% 5070 49 2341 2893k 736.4s 13915 190 4489 94.88% 0.0178616536 0.0460846816 61.24% 5231 46 2113 2917k 741.5s 13956 178 4514 94.91% 0.0186892675 0.0460846816 59.45% 5499 44 2061 2941k 746.5s 14029 170 4554 95.36% 0.0210823955 0.0460846816 54.25% 5564 24 2012 2960k 751.5s 14085 165 4586 96.18% 0.0222289664 0.0460846816 51.76% 5230 53 1933 2978k 756.6s 14124 158 4609 96.23% 0.0232147138 0.0460846816 49.63% 5507 50 1790 2995k 761.8s 14178 149 4640 97.03% 0.023214715 0.0460846816 49.63% 5776 47 1714 3014k 767.2s 14241 144 4674 97.89% 0.0232580021 0.0460846816 49.53% 5797 27 1689 3035k 772.5s 14282 135 4699 97.90% 0.0268318457 0.0460846816 41.78% 6003 47 1664 3055k 777.7s 14317 124 4719 98.45% 0.027303379 0.0460846816 40.75% 5974 68 1475 3078k 782.7s 14427 127 4774 98.69% 0.0274429983 0.0460846816 40.45% 5481 35 1443 3096k 787.7s 14464 110 4801 98.81% 0.0296721541 0.0460846816 35.61% 5438 42 1407 3120k 792.8s 14512 95 4832 98.89% 0.0299705275 0.0460846816 34.97% 5062 66 1314 3145k 798.7s 14540 83 4852 98.96% 0.0320819699 0.0460846816 30.38% 5349 48 1209 3165k 804.0s 14615 75 4894 99.30% 0.0333533213 0.0460846816 27.63% 5311 75 1130 3184k 809.0s 14645 58 4917 99.43% 0.0342174555 0.0460846816 25.75% 5531 37 1094 3209k 814.5s 14699 47 4950 99.55% 0.0375726102 0.0460846816 18.47% 5265 39 987 3230k 819.5s 14779 45 4989 99.57% 0.0377911387 0.0460846816 18.00% 4670 63 892 3245k 824.5s 14832 32 5023 99.65% 0.0382345969 0.0460846816 17.03% 4616 57 853 3265k 829.5s 14906 29 5062 99.69% 0.0387795214 0.0460846816 15.85% 4573 60 851 3281k 834.6s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 14966 24 5092 99.74% 0.0394675701 0.0460846816 14.36% 4758 69 859 3304k 839.6s 15044 9 5140 99.98% 0.0413783822 0.0460846816 10.21% 5126 43 883 3320k 844.9s Solving report Status Optimal Primal bound 0.0460846815889 Dual bound 0.0460828522316 Gap 0.00397% (tolerance: 0.01%) Solution status feasible 0.0460846815889 (objective) 0 (bound viol.) 7.77156117238e-16 (int. viol.) 0 (row viol.) Timing 846.96 (total) 0.11 (presolve) 0.00 (postsolve) Nodes 15055 LP iterations 3330503 (total) 162466 (strong br.) 127990 (separation) 298572 (heuristics) 847.007279 seconds (1.67 M allocations: 56.719 MiB)
Dict{Any, Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 846.962 :TotalTime => 847.007 :Perturbation => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :PerturbedInput => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :TighteningApproach => "interval_arithmetic" :PerturbationFamily => unrestricted :SolveStatus => OPTIMAL :Model => A JuMP Model… :Output => AffExpr[-0.012063867412507534 _[865] + 0.6606525778770… :PredictedIndex => 8
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
HiGHS.Optimizer,
Dict("output_flag" => true),
tightening_algorithm = lp,
norm_order=Inf
)
[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. Running HiGHS 1.4.2 [date: 1970-01-01, git hash: f797c1ab6] Copyright (c) 2022 ERGO-Code under MIT licence terms Presolving model 1203 rows, 1020 cols, 66828 nonzeros 1203 rows, 1020 cols, 66828 nonzeros Solving MIP model with: 1203 rows 1020 cols (60 binary, 0 integer, 0 implied int., 960 continuous) 66828 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s 0 0 0 0.00% 0 inf inf 0 0 36 1504 0.1s R 0 0 0 0.00% 0 0.2260962872 100.00% 2331 37 517 1954 1.2s L 0 0 0 0.00% 0 0.1207006013 100.00% 2331 37 517 1954 17.7s 30 3 5 0.00% 0 0.1207006013 100.00% 2351 25 540 91672 22.7s 47 6 13 0.00% 0 0.1207006013 100.00% 2371 25 569 121937 28.8s 75 8 27 0.03% 0 0.1207006013 100.00% 2408 25 624 145223 33.9s 150 30 51 3.21% 0 0.1207006013 100.00% 2595 28 698 169067 39.1s 279 62 105 3.66% 0 0.1207006013 100.00% 2794 24 857 190646 44.1s 380 83 144 5.26% 0 0.1207006013 100.00% 2965 28 936 216571 49.1s 511 113 198 7.34% 0 0.1207006013 100.00% 3497 36 1029 246199 55.3s 641 133 251 8.14% 0 0.1207006013 100.00% 3587 42 1117 269990 60.3s 801 162 318 8.92% 0 0.1207006013 100.00% 4411 60 1208 292809 65.4s 892 179 354 9.20% 0 0.1207006013 100.00% 4501 67 1273 316203 70.4s 975 187 392 9.59% 0 0.1207006013 100.00% 4962 68 1344 339590 75.6s 1121 194 461 11.14% 0 0.1207006013 100.00% 5127 59 1487 365961 80.9s 1392 252 566 11.93% 0 0.1207006013 100.00% 5104 70 1640 389203 86.0s 1631 306 659 12.06% 0 0.1207006013 100.00% 4712 33 1787 420206 92.0s 1866 340 758 12.11% 0 0.1207006013 100.00% 4470 41 1908 445735 97.0s 1982 353 810 12.17% 0 0.1207006013 100.00% 4868 73 1986 467685 102.1s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 2046 354 843 17.26% 0 0.1207006013 100.00% 5341 91 2051 484751 107.1s 2099 354 869 18.39% 0 0.1207006013 100.00% 5371 91 2110 506422 112.1s 2223 367 922 18.45% 0 0.1207006013 100.00% 5005 35 2195 529729 117.1s 2421 412 998 18.47% 0 0.1207006013 100.00% 4698 45 2297 560674 122.7s 2618 440 1084 18.48% 0 0.1207006013 100.00% 4629 55 2418 589772 130.1s 2754 470 1136 18.48% 0 0.1207006013 100.00% 4479 36 2495 613498 135.8s 2863 485 1182 19.00% 0 0.1207006013 100.00% 4880 65 2557 634866 140.8s 3019 518 1244 21.15% 0 0.1207006013 100.00% 5261 59 2678 657805 146.6s 3222 540 1334 21.16% 0 0.1207006013 100.00% 4204 52 2848 684903 153.1s 3420 561 1424 21.16% 0 0.1207006013 100.00% 4337 62 2996 710144 158.2s 3618 586 1509 21.16% 0 0.1207006013 100.00% 4370 54 3102 732712 163.2s 3776 601 1578 21.17% 0 0.1207006013 100.00% 4457 50 3209 751994 168.2s T 3899 142 1628 28.11% 0 0.0942444257 100.00% 4480 54 3270 765037 171.2s T 3908 141 1632 28.11% 0 0.0936965516 100.00% 4484 54 3273 765423 171.3s 4082 167 1707 32.59% 0 0.0936965516 100.00% 4742 31 3427 789962 176.4s 4318 200 1810 33.07% 0 0.0936965516 100.00% 4912 44 3622 814536 181.4s 4432 210 1863 33.20% 0 0.0936965516 100.00% 5150 101 3711 845771 189.5s 4534 212 1912 33.54% 0 0.0936965516 100.00% 5051 111 3823 871244 194.5s 4616 215 1951 33.97% 0 0.0936965516 100.00% 5088 111 3937 891790 199.6s 4746 222 2012 35.49% 0 0.0936965516 100.00% 5479 53 4119 911313 204.7s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 4833 228 2054 35.88% 0 0.0936965516 100.00% 6096 77 4242 928367 210.0s 5037 259 2140 35.88% 0 0.0936965516 100.00% 6284 93 4395 948731 215.0s 5054 254 2150 36.43% 0 0.0936965516 100.00% 6254 140 4417 961433 220.3s 5142 257 2192 37.45% 0 0.0936965516 100.00% 6296 140 4500 980546 225.3s 5221 260 2231 37.65% 0 0.0936965516 100.00% 6518 149 4574 1000k 230.6s 5263 258 2253 37.72% 0 0.0936965516 100.00% 6806 98 4625 1017k 235.6s 5476 299 2339 44.70% 0 0.0936965516 100.00% 6995 66 4770 1034k 240.7s 5580 312 2384 46.24% 0 0.0936965516 100.00% 9323 100 4897 1047k 246.6s 5636 309 2413 48.01% 0 0.0936965516 100.00% 9703 83 4943 1063k 252.4s 5745 318 2462 51.03% 0 0.0936965516 100.00% 9998 94 5059 1083k 257.4s 5980 373 2549 52.08% 4.39241073e-05 0.0936965516 99.95% 10038 111 5191 1098k 262.5s 6151 407 2621 52.17% 4.39241073e-05 0.0936965516 99.95% 9723 42 5300 1115k 267.6s T 6325 424 2681 52.28% 4.39241073e-05 0.0933310059 99.95% 10026 46 5371 1132k 271.6s L 6340 94 2687 68.08% 4.39241073e-05 0.0592820117 99.93% 9899 50 5378 1133k 292.7s 6464 108 2741 68.08% 4.39241073e-05 0.0592820117 99.93% 9763 81 5452 1239k 299.4s 6512 109 2761 68.44% 4.39241073e-05 0.0592820117 99.93% 9547 68 5476 1259k 304.5s 6632 131 2813 68.46% 4.39241073e-05 0.0592820117 99.93% 9498 68 5547 1276k 309.8s 6787 150 2879 68.52% 4.39241073e-05 0.0592820117 99.93% 9303 73 5648 1295k 314.8s 6885 167 2918 68.62% 0.000211862717 0.0592820117 99.64% 9435 59 5699 1311k 319.9s T 6892 159 2920 68.72% 0.000211862717 0.0584730533 99.64% 9437 59 5701 1311k 319.9s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 6943 160 2949 70.35% 0.000211862717 0.0584730533 99.64% 9995 87 5736 1331k 325.7s 7148 195 3032 71.29% 0.00406013893 0.0584730533 93.06% 9603 45 5864 1350k 331.2s 7321 228 3102 71.40% 0.00406013893 0.0584730533 93.06% 9854 55 5978 1370k 336.2s 7407 232 3143 71.46% 0.00406013893 0.0584730533 93.06% 10953 75 6050 1388k 341.9s 7528 254 3192 71.53% 0.00406013893 0.0584730533 93.06% 9751 85 6111 1407k 347.2s 7639 278 3237 72.31% 0.00406013893 0.0584730533 93.06% 10369 74 6174 1425k 352.2s 7688 280 3261 72.74% 0.00436601528 0.0584730533 92.53% 10859 82 6218 1436k 357.4s 7852 297 3333 72.78% 0.00436601528 0.0584730533 92.53% 10148 98 6350 1456k 362.4s 7969 308 3386 72.98% 0.00436601528 0.0584730533 92.53% 9936 117 6429 1470k 367.8s 8040 307 3422 75.13% 0.0044718657 0.0584730533 92.35% 9841 59 6485 1488k 372.9s 8183 326 3482 76.48% 0.0044718657 0.0584730533 92.35% 9309 60 6568 1502k 377.9s 8339 342 3553 76.50% 0.0044718657 0.0584730533 92.35% 9803 74 6699 1523k 383.0s 8458 359 3603 77.92% 0.0044718657 0.0584730533 92.35% 9066 42 6759 1543k 388.0s 8569 365 3655 78.44% 0.0044718657 0.0584730533 92.35% 9965 68 6831 1562k 393.1s 8758 379 3742 79.19% 0.0044718657 0.0584730533 92.35% 10122 35 6958 1579k 398.1s 8888 390 3802 79.26% 0.0044718657 0.0584730533 92.35% 9238 52 7047 1597k 403.1s 9006 390 3861 79.79% 0.0044718657 0.0584730533 92.35% 9849 59 7122 1616k 408.2s 9060 386 3890 80.07% 0.00598983999 0.0584730533 89.76% 9735 50 7157 1631k 413.3s 9165 386 3941 80.95% 0.00598983999 0.0584730533 89.76% 9992 63 7239 1649k 418.3s 9310 406 4005 82.05% 0.00598983999 0.0584730533 89.76% 10489 76 7357 1667k 423.7s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 9495 429 4085 82.10% 0.00598983999 0.0584730533 89.76% 9488 42 7516 1686k 428.8s 9662 455 4153 82.12% 0.00598983999 0.0584730533 89.76% 9765 51 7620 1703k 433.9s 9724 462 4183 82.13% 0.00598983999 0.0584730533 89.76% 9129 90 7666 1712k 439.4s 9861 475 4244 82.14% 0.00598983999 0.0584730533 89.76% 10095 78 7755 1729k 444.4s 9982 492 4298 82.15% 0.00599172376 0.0584730533 89.75% 7654 83 7836 1748k 449.5s 10104 513 4346 82.15% 0.00599172376 0.0584730533 89.75% 8425 94 7898 1766k 454.6s Restarting search from the root node Model after restart has 1152 rows, 990 cols (39 bin., 0 int., 0 impl., 951 cont.), and 42855 nonzeros 10182 0 0 0.00% 0.00599172376 0.0584730533 89.75% 90 0 0 1780k 458.6s 10182 0 0 0.00% 0.00599172376 0.0584730533 89.75% 90 9 9 1781k 458.8s 10403 31 91 53.29% 0.00599172376 0.0584730533 89.75% 1224 26 154 1802k 463.8s 10587 57 168 70.08% 0.00599172376 0.0584730533 89.75% 3366 53 283 1830k 470.2s 10836 95 262 74.17% 0.0070120559 0.0584730533 88.01% 4494 46 412 1850k 475.5s 10965 112 317 80.94% 0.0070120559 0.0584730533 88.01% 5549 55 493 1867k 481.8s 11139 145 385 82.52% 0.0146594215 0.0584730533 74.93% 4710 50 604 1885k 487.7s 11325 178 459 85.03% 0.0176698194 0.0584730533 69.78% 4895 51 695 1903k 492.8s 11516 220 535 85.17% 0.0223330481 0.0584730533 61.81% 5411 48 792 1916k 497.8s 11638 222 589 86.93% 0.0224681328 0.0584730533 61.58% 5291 33 854 1931k 503.0s T 11676 174 606 88.29% 0.0224681328 0.0554554748 59.48% 5431 35 871 1937k 504.9s T 11687 118 612 93.91% 0.0224681328 0.0498354344 54.92% 5437 35 877 1937k 505.0s T 11730 97 633 94.22% 0.0224681328 0.0460846816 51.25% 5457 35 897 1939k 505.7s 11835 103 682 95.19% 0.0317301163 0.0460846816 31.15% 6578 55 981 1952k 510.8s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 11926 94 732 95.41% 0.0354774217 0.0460846816 23.02% 6661 26 1043 1966k 515.9s 11987 75 773 95.63% 0.0365260193 0.0460846816 20.74% 5865 27 1094 1978k 521.2s 12090 67 822 96.13% 0.037204082 0.0460846816 19.27% 5267 49 1164 1990k 526.8s 12154 51 862 97.74% 0.0389159787 0.0460846816 15.56% 4599 46 1206 2004k 532.0s 12198 37 891 97.95% 0.0399985534 0.0460846816 13.21% 5138 40 1243 2015k 537.1s 12261 25 928 99.16% 0.0416131647 0.0460846816 9.70% 5358 45 1294 2023k 542.2s Solving report Status Optimal Primal bound 0.0460846815889 Dual bound 0.0460828522316 Gap 0.00397% (tolerance: 0.01%) Solution status feasible 0.0460846815889 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 546.32 (total) 0.11 (presolve) 0.00 (postsolve) Nodes 12314 LP iterations 2037617 (total) 139358 (strong br.) 70276 (separation) 149604 (heuristics) 546.723810 seconds (1.90 M allocations: 72.456 MiB)
Dict{Any, Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 546.327 :TotalTime => 546.724 :Perturbation => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :PerturbedInput => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :TighteningApproach => "lp" :PerturbationFamily => unrestricted :SolveStatus => OPTIMAL :Model => A JuMP Model… :Output => AffExpr[-0.012063867412507534 _[865] + 0.6606525778770… :PredictedIndex => 8
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
HiGHS.Optimizer,
Dict("output_flag" => true),
tightening_algorithm = mip,
norm_order=Inf
)
[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. Running HiGHS 1.4.2 [date: 1970-01-01, git hash: f797c1ab6] Copyright (c) 2022 ERGO-Code under MIT licence terms Presolving model 1203 rows, 1020 cols, 66828 nonzeros 1203 rows, 1020 cols, 66828 nonzeros Solving MIP model with: 1203 rows 1020 cols (60 binary, 0 integer, 0 implied int., 960 continuous) 66828 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s 0 0 0 0.00% 0 inf inf 0 0 36 1529 0.1s R 0 0 0 0.00% 0 0.5055138665 100.00% 1571 26 61 1999 0.8s L 0 0 0 0.00% 0 0.1263064504 100.00% 2642 56 541 2281 10.0s 27 4 5 0.78% 0 0.1263064504 100.00% 2659 27 576 94655 19.3s 32 6 8 0.80% 0 0.1263064504 100.00% 2673 27 590 125764 25.6s 71 6 27 0.87% 0 0.1263064504 100.00% 2700 27 632 150407 31.0s 111 23 42 1.04% 0 0.1263064504 100.00% 2767 31 658 218206 73.1s 289 53 112 1.18% 0 0.1263064504 100.00% 2934 37 805 243133 78.3s 333 71 130 2.05% 0 0.1263064504 100.00% 4347 72 841 254737 83.3s 475 102 183 25.22% 0 0.1263064504 100.00% 4295 81 923 297104 93.0s 605 125 235 25.43% 0 0.1263064504 100.00% 4284 50 1014 314179 98.0s 680 130 269 25.52% 0 0.1263064504 100.00% 4499 64 1060 324104 103.0s 769 133 313 26.07% 0 0.1263064504 100.00% 4200 73 1141 341366 108.1s 987 175 400 27.11% 0 0.1263064504 100.00% 4401 44 1297 364500 113.2s 1131 194 461 28.39% 0 0.1263064504 100.00% 4493 49 1458 388798 118.3s 1299 237 519 28.66% 0 0.1263064504 100.00% 4631 60 1550 412797 123.3s 1475 290 584 29.08% 0 0.1263064504 100.00% 4701 42 1639 435131 128.8s 1675 347 655 29.42% 0 0.1263064504 100.00% 4905 57 1767 458317 134.0s 1816 380 706 29.86% 0 0.1263064504 100.00% 4984 40 1846 478946 139.0s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 2020 434 779 29.92% 0 0.1263064504 100.00% 5017 53 1965 502224 144.1s Restarting search from the root node Model after restart has 1183 rows, 1008 cols (52 bin., 0 int., 0 impl., 956 cont.), and 57224 nonzeros 2067 0 0 0.00% 0 0.1263064504 100.00% 53 0 0 503816 144.6s 2067 0 0 0.00% 0 0.1263064504 100.00% 53 19 10 504795 144.7s 2274 45 78 5.13% 0 0.1263064504 100.00% 2622 65 157 524177 151.2s 2475 107 147 21.15% 0 0.1263064504 100.00% 4593 73 240 540305 157.2s 2883 192 303 23.88% 0 0.1263064504 100.00% 5074 91 425 561309 162.6s 3148 246 407 23.88% 0 0.1263064504 100.00% 5147 41 576 589631 167.6s 3360 297 488 23.88% 0 0.1263064504 100.00% 5931 77 709 605003 172.6s 3630 366 585 24.05% 0 0.1263064504 100.00% 6700 86 902 624299 177.7s 3902 433 691 33.71% 0.000211862717 0.1263064504 99.83% 7954 106 1049 643033 182.9s 4185 504 792 36.07% 0.000211862717 0.1263064504 99.83% 8519 63 1213 659393 188.0s 4398 536 882 36.13% 0.000211862717 0.1263064504 99.83% 8563 70 1337 677955 193.0s 4572 559 955 36.13% 0.000211862717 0.1263064504 99.83% 8579 52 1434 700075 198.0s 4789 604 1042 36.29% 0.00344401548 0.1263064504 97.27% 9256 77 1604 719635 203.1s 5038 655 1137 36.29% 0.00344401548 0.1263064504 97.27% 9755 91 1715 740368 208.1s 5215 696 1205 36.29% 0.00344401548 0.1263064504 97.27% 9707 74 1786 757310 213.1s T 5388 674 1275 36.41% 0.00344401548 0.1257451692 97.26% 10036 81 1918 767123 215.8s 5637 734 1376 36.48% 0.00344401548 0.1257451692 97.26% 9606 69 2101 786571 220.9s Restarting search from the root node Model after restart has 1183 rows, 1008 cols (52 bin., 0 int., 0 impl., 956 cont.), and 57224 nonzeros 5807 0 0 0.00% 0.00344401548 0.1257451692 97.26% 70 0 0 802547 224.7s 5807 0 0 0.00% 0.00344401548 0.1257451692 97.26% 70 23 4 802949 224.7s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 5943 27 53 1.52% 0.00344401548 0.1257451692 97.26% 5103 94 114 815132 229.7s 6113 65 121 8.37% 0.00344401548 0.1257451692 97.26% 7480 83 198 826891 234.8s 6220 92 159 16.44% 0.00344401548 0.1257451692 97.26% 9625 75 239 840856 240.2s 6455 134 254 21.11% 0.00344401548 0.1257451692 97.26% 9168 61 352 858283 245.2s 6628 183 318 26.69% 0.0050858007 0.1257451692 95.96% 10044 77 419 874537 250.7s 6826 210 405 27.71% 0.00915599642 0.1257451692 92.72% 10127 122 543 892977 257.4s 6899 219 435 33.16% 0.0102639993 0.1257451692 91.84% 9905 104 587 907336 262.5s 7091 255 515 33.42% 0.013059906 0.1257451692 89.61% 10048 107 683 925110 267.5s 7307 302 597 33.43% 0.013059906 0.1257451692 89.61% 9111 67 779 941716 272.8s 7438 326 650 34.23% 0.013059906 0.1257451692 89.61% 9971 81 873 956774 277.9s 7613 370 716 34.74% 0.0152686057 0.1257451692 87.86% 9900 71 959 971775 283.0s 7744 393 769 34.80% 0.0152686057 0.1257451692 87.86% 9621 94 1019 987959 288.1s 8052 466 886 34.83% 0.0152686057 0.1257451692 87.86% 9551 63 1167 1001k 293.4s 8249 510 961 34.84% 0.0152686057 0.1257451692 87.86% 9888 69 1282 1014k 298.5s T 8426 520 1029 34.90% 0.0152686057 0.1253687397 87.82% 9701 77 1362 1023k 301.5s T 8429 362 1031 35.34% 0.0152686057 0.1190512883 87.17% 9704 77 1364 1023k 301.6s 8502 389 1060 35.49% 0.0152686057 0.1190512883 87.17% 9602 130 1398 1033k 306.7s 8604 401 1105 35.63% 0.0202044379 0.1190512883 83.03% 10137 162 1454 1048k 311.7s 8803 445 1183 35.63% 0.0202044379 0.1190512883 83.03% 9846 86 1548 1062k 316.7s T 8884 171 1208 39.38% 0.0202044379 0.1006031462 79.92% 9912 93 1578 1070k 319.3s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time T 8891 120 1211 40.85% 0.0202044379 0.0935000065 78.39% 9915 93 1580 1071k 319.5s T 8898 120 1215 40.85% 0.0202044379 0.0931519259 78.31% 9919 93 1585 1071k 319.6s T 8920 120 1225 40.85% 0.0202044379 0.0930568574 78.29% 9929 93 1601 1072k 320.0s T 8965 105 1239 41.28% 0.0202044379 0.0859343767 76.49% 10050 100 1619 1075k 321.2s T 8970 99 1242 41.69% 0.0202044379 0.0826614026 75.56% 10053 100 1621 1075k 321.3s T 9002 86 1257 46.63% 0.0202044379 0.0785995753 74.29% 10066 100 1637 1078k 322.1s T 9164 119 1316 46.67% 0.0202044379 0.0771396194 73.81% 9704 54 1693 1090k 326.2s 9285 137 1369 47.35% 0.02286829 0.0771396194 70.35% 8251 57 1752 1105k 331.4s T 9301 117 1375 60.46% 0.02286829 0.0719610622 68.22% 8256 57 1757 1106k 331.8s T 9304 109 1377 60.47% 0.02286829 0.0705787676 67.60% 8257 57 1758 1106k 331.9s T 9319 77 1384 60.68% 0.02286829 0.0640056205 64.27% 8262 57 1764 1107k 332.1s T 9348 37 1397 64.45% 0.02286829 0.0502852709 54.52% 8272 57 1774 1109k 332.8s T 9403 43 1417 66.92% 0.02286829 0.0462748346 50.58% 8309 61 1794 1114k 334.3s 9522 59 1472 88.96% 0.02286829 0.0462748346 50.58% 9645 48 1847 1126k 339.4s 9614 64 1511 90.86% 0.0285839663 0.0462748346 38.23% 8644 99 1898 1138k 345.2s 9735 79 1560 93.09% 0.0285839663 0.0462748346 38.23% 10086 82 1963 1153k 350.2s T 9762 77 1570 93.14% 0.0285839663 0.0460846816 37.98% 10095 82 1978 1154k 350.7s 9860 97 1612 93.53% 0.0297893072 0.0460846816 35.36% 8848 77 2040 1164k 355.9s 9986 115 1663 94.02% 0.0299705275 0.0460846816 34.97% 8833 65 2110 1176k 361.1s 10049 109 1700 94.33% 0.0304193203 0.0460846816 33.99% 8270 80 2171 1187k 366.5s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 10147 106 1749 94.78% 0.0331486664 0.0460846816 28.07% 8095 62 2233 1197k 371.5s 10225 60 1811 98.10% 0.0390949049 0.0460846816 15.17% 7431 84 2337 1214k 377.1s 10285 18 1862 98.81% 0.0405902561 0.0460846816 11.92% 7800 67 2409 1227k 382.2s Solving report Status Optimal Primal bound 0.0460846815889 Dual bound 0.0460828522316 Gap 0.00397% (tolerance: 0.01%) Solution status feasible 0.0460846815889 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 386.12 (total) 0.13 (presolve) 0.00 (postsolve) Nodes 10319 LP iterations 1236081 (total) 172574 (strong br.) 33659 (separation) 98217 (heuristics) 1062.210358 seconds (1.81 M allocations: 63.485 MiB)
Dict{Any, Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 386.127 :TotalTime => 1062.21 :Perturbation => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :PerturbedInput => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :TighteningApproach => "mip" :PerturbationFamily => unrestricted :SolveStatus => OPTIMAL :Model => A JuMP Model… :Output => AffExpr[-0.012063867412507534 _[865] + 0.6606525778770… :PredictedIndex => 8
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
for Gurobi
, and time_limit
for HiGHS
.
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
HiGHS.Optimizer,
Dict("time_limit" => 10.0),
tightening_algorithm = lp,
norm_order=Inf
)
[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. Running HiGHS 1.4.2 [date: 1970-01-01, git hash: f797c1ab6] Copyright (c) 2022 ERGO-Code under MIT licence terms Presolving model 1203 rows, 1020 cols, 66828 nonzeros 1203 rows, 1020 cols, 66828 nonzeros Solving MIP model with: 1203 rows 1020 cols (60 binary, 0 integer, 0 implied int., 960 continuous) 66828 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s 0 0 0 0.00% 0 inf inf 0 0 36 1504 0.1s R 0 0 0 0.00% 0 0.2260962872 100.00% 2331 37 517 1954 1.3s L 0 0 0 0.00% 0 0.1244550462 100.00% 2331 37 517 1954 10.0s Solving report Status Time limit reached Primal bound 0.124455046182 Dual bound 0 Gap 100% (tolerance: 0.01%) Solution status feasible 0.124455046182 (objective) 0 (bound viol.) 2.22044604925e-16 (int. viol.) 0 (row viol.) Timing 10.00 (total) 0.02 (presolve) 0.00 (postsolve) Nodes 0 LP iterations 23376 (total) 0 (strong br.) 450 (separation) 21422 (heuristics) 10.397745 seconds (1.90 M allocations: 72.457 MiB)
Dict{Any, Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 10.0061 :TotalTime => 10.3976 :Perturbation => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :PerturbedInput => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :TighteningApproach => "lp" :PerturbationFamily => unrestricted :SolveStatus => TIME_LIMIT :Model => A JuMP Model… :Output => AffExpr[-0.012063867412507534 _[865] + 0.6606525778770… :PredictedIndex => 8
Set BestBdStop
for Gurobi
, and objective_bound
for HiGHS
.
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
HiGHS.Optimizer,
Dict("objective_bound" => 0.02),
tightening_algorithm = lp,
norm_order=Inf
)
[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. Running HiGHS 1.4.2 [date: 1970-01-01, git hash: f797c1ab6] Copyright (c) 2022 ERGO-Code under MIT licence terms Presolving model 1203 rows, 1020 cols, 66828 nonzeros 1203 rows, 1020 cols, 66828 nonzeros Solving MIP model with: 1203 rows 1020 cols (60 binary, 0 integer, 0 implied int., 960 continuous) 66828 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 0.02* inf 0 0 0 0 0.0s 0 0 0 0.00% 0 0.02* inf 0 0 36 1504 0.1s 0 0 0 0.00% 0 0.02* inf 1861 25 100 18761 9.0s 26.7% inactive integer columns, restarting Model after restart has 1109 rows, 963 cols (23 bin., 0 int., 0 impl., 940 cont.), and 28917 nonzeros 0 0 0 0.00% 0 0.02* inf 5 0 0 18761 9.2s 0 0 0 0.00% 0 0.02* inf 5 0 10 19398 9.2s 4.3% inactive integer columns, restarting Model after restart has 1107 rows, 962 cols (22 bin., 0 int., 0 impl., 940 cont.), and 28888 nonzeros 0 0 0 0.00% 0.0025720269 0.02* inf 19 0 0 21505 12.5s 0 0 0 0.00% 0.00257202869 0.02* inf 19 19 6 22200 12.6s 0 0 0 0.00% 0.00451757418 0.02* inf 2848 52 54 22810 17.8s Solving report Status Infeasible Primal bound inf Dual bound inf Gap inf Solution status - Timing 19.69 (total) 0.23 (presolve) 0.00 (postsolve) Nodes 1 LP iterations 28939 (total) 5423 (strong br.) 3569 (separation) 16473 (heuristics) ERROR: No invertible representation for getDualRay 20.191234 seconds (2.13 M allocations: 85.322 MiB, 0.59% compilation time)
Dict{Any, Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 19.6953 :TotalTime => 20.1219 :Perturbation => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :PerturbedInput => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :TighteningApproach => "lp" :PerturbationFamily => unrestricted :SolveStatus => INFEASIBLE :Model => A JuMP Model… :Output => AffExpr[-0.012063867412507534 _[865] + 0.6606525778770… :PredictedIndex => 8
Set BestObjStop
for Gurobi
, and objective_target
for HiGHS
.
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
HiGHS.Optimizer,
Dict("objective_target" => 0.2),
tightening_algorithm = lp,
norm_order=Inf
)
[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. Running HiGHS 1.4.2 [date: 1970-01-01, git hash: f797c1ab6] Copyright (c) 2022 ERGO-Code under MIT licence terms Presolving model 1203 rows, 1020 cols, 66828 nonzeros 1203 rows, 1020 cols, 66828 nonzeros Solving MIP model with: 1203 rows 1020 cols (60 binary, 0 integer, 0 implied int., 960 continuous) 66828 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s 0 0 0 0.00% 0 inf inf 0 0 36 1504 0.1s R 0 0 0 0.00% 0 0.2260962872 100.00% 2331 37 517 1954 1.2s L 0 0 0 0.00% 0 0.1207006013 100.00% 2331 37 517 1954 17.7s 30 3 5 0.00% 0 0.1207006013 100.00% 2351 25 540 91672 22.9s 47 6 13 0.00% 0 0.1207006013 100.00% 2371 25 569 121937 29.1s 75 8 27 0.03% 0 0.1207006013 100.00% 2408 25 624 145223 34.1s 150 30 51 3.21% 0 0.1207006013 100.00% 2595 28 698 169067 39.3s 279 62 105 3.66% 0 0.1207006013 100.00% 2794 24 857 190646 44.4s 380 83 144 5.26% 0 0.1207006013 100.00% 2965 28 936 216571 49.4s 511 113 198 7.34% 0 0.1207006013 100.00% 3497 36 1029 246199 55.5s 641 133 251 8.14% 0 0.1207006013 100.00% 3587 42 1117 269990 60.6s 801 162 318 8.92% 0 0.1207006013 100.00% 4411 60 1208 292809 65.6s 892 179 354 9.20% 0 0.1207006013 100.00% 4501 67 1273 316203 70.6s 975 187 392 9.59% 0 0.1207006013 100.00% 4962 68 1344 339590 75.8s 1121 194 461 11.14% 0 0.1207006013 100.00% 5127 59 1487 365961 81.1s 1387 252 563 11.93% 0 0.1207006013 100.00% 5101 70 1637 389021 86.2s 1631 306 659 12.06% 0 0.1207006013 100.00% 4712 33 1787 420206 92.4s 1866 340 758 12.11% 0 0.1207006013 100.00% 4470 41 1908 445735 97.4s 1979 353 809 12.17% 0 0.1207006013 100.00% 4867 73 1985 467604 102.4s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 2046 354 843 17.26% 0 0.1207006013 100.00% 5341 91 2051 484751 107.5s 2099 354 869 18.39% 0 0.1207006013 100.00% 5371 91 2110 506422 112.5s 2223 367 922 18.45% 0 0.1207006013 100.00% 5005 35 2195 529729 117.6s 2421 412 998 18.47% 0 0.1207006013 100.00% 4698 45 2297 560674 123.2s 2618 440 1084 18.48% 0 0.1207006013 100.00% 4629 55 2418 589772 130.7s 2754 470 1136 18.48% 0 0.1207006013 100.00% 4479 36 2495 613498 136.3s 2863 485 1182 19.00% 0 0.1207006013 100.00% 4880 65 2557 634866 141.3s 3019 518 1244 21.15% 0 0.1207006013 100.00% 5261 59 2678 657805 147.1s 3222 540 1334 21.16% 0 0.1207006013 100.00% 4204 52 2848 684903 153.5s 3420 561 1424 21.16% 0 0.1207006013 100.00% 4337 62 2996 710144 158.6s 3618 586 1509 21.16% 0 0.1207006013 100.00% 4370 54 3102 732712 163.6s 3776 601 1578 21.17% 0 0.1207006013 100.00% 4457 50 3209 751994 168.6s T 3899 142 1628 28.11% 0 0.0942444257 100.00% 4480 54 3270 765037 171.6s T 3908 141 1632 28.11% 0 0.0936965516 100.00% 4484 54 3273 765423 171.7s 4085 168 1708 32.59% 0 0.0936965516 100.00% 4743 31 3428 790164 176.8s 4318 200 1810 33.07% 0 0.0936965516 100.00% 4912 44 3622 814536 181.8s 4432 210 1863 33.20% 0 0.0936965516 100.00% 5150 101 3711 845771 189.9s 4534 212 1912 33.54% 0 0.0936965516 100.00% 5051 111 3823 871244 195.0s 4616 215 1951 33.97% 0 0.0936965516 100.00% 5088 111 3937 891790 200.0s 4746 222 2012 35.49% 0 0.0936965516 100.00% 5479 53 4119 911313 205.0s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 4833 228 2054 35.88% 0 0.0936965516 100.00% 6096 77 4242 928367 210.3s 5039 258 2141 35.89% 0 0.0936965516 100.00% 6763 60 4396 950565 216.2s 5069 255 2157 37.06% 0 0.0936965516 100.00% 6261 140 4426 964519 221.2s 5154 260 2197 37.51% 0 0.0936965516 100.00% 6485 149 4508 984868 226.6s 5237 260 2239 37.66% 0 0.0936965516 100.00% 6525 149 4595 1005k 231.7s 5300 261 2268 40.72% 0 0.0936965516 100.00% 6912 61 4645 1022k 236.8s 5507 300 2350 45.41% 0 0.0936965516 100.00% 7028 78 4791 1037k 241.8s 5587 312 2387 46.78% 0 0.0936965516 100.00% 9326 100 4901 1049k 246.8s 5636 309 2413 48.01% 0 0.0936965516 100.00% 9703 83 4943 1063k 252.1s 5748 319 2463 51.04% 0 0.0936965516 100.00% 9999 94 5060 1083k 257.1s 5980 373 2549 52.08% 4.39241073e-05 0.0936965516 99.95% 10038 111 5191 1098k 262.2s 6147 405 2619 52.16% 4.39241073e-05 0.0936965516 99.95% 9721 42 5297 1115k 267.5s T 6325 424 2681 52.28% 4.39241073e-05 0.0933310059 99.95% 10026 46 5371 1132k 271.9s L 6340 94 2687 68.08% 4.39241073e-05 0.0592820117 99.93% 9899 50 5378 1133k 293.2s 6464 108 2741 68.08% 4.39241073e-05 0.0592820117 99.93% 9763 81 5452 1239k 300.0s 6512 109 2761 68.44% 4.39241073e-05 0.0592820117 99.93% 9547 68 5476 1259k 305.1s 6632 131 2813 68.46% 4.39241073e-05 0.0592820117 99.93% 9498 68 5547 1276k 310.3s 6787 150 2879 68.52% 4.39241073e-05 0.0592820117 99.93% 9303 73 5648 1295k 315.3s 6885 167 2918 68.62% 0.000211862717 0.0592820117 99.64% 9435 59 5699 1311k 320.4s T 6892 159 2920 68.72% 0.000211862717 0.0584730533 99.64% 9437 59 5701 1311k 320.5s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 6936 161 2945 68.79% 0.000211862717 0.0584730533 99.64% 9628 72 5730 1327k 325.6s 7093 184 3010 71.25% 0.00406013893 0.0584730533 93.06% 10457 94 5827 1344k 330.6s 7272 222 3080 71.37% 0.00406013893 0.0584730533 93.06% 9833 55 5934 1362k 335.8s 7359 229 3121 71.41% 0.00406013893 0.0584730533 93.06% 9974 68 6012 1380k 341.1s 7506 256 3181 71.52% 0.00406013893 0.0584730533 93.06% 9403 78 6099 1401k 346.6s 7607 265 3226 71.54% 0.00406013893 0.0584730533 93.06% 9785 85 6161 1419k 351.7s 7653 277 3244 72.33% 0.00436601528 0.0584730533 92.53% 10012 65 6185 1431k 357.3s 7807 292 3312 72.78% 0.00436601528 0.0584730533 92.53% 10129 98 6311 1450k 362.3s 7969 308 3386 72.98% 0.00436601528 0.0584730533 92.53% 9936 117 6429 1470k 369.1s 8040 307 3422 75.13% 0.0044718657 0.0584730533 92.35% 9841 59 6485 1488k 374.2s 8185 326 3483 76.48% 0.0044718657 0.0584730533 92.35% 9310 60 6569 1503k 379.2s 8339 342 3553 76.50% 0.0044718657 0.0584730533 92.35% 9803 74 6699 1523k 384.2s 8458 359 3603 77.92% 0.0044718657 0.0584730533 92.35% 9066 42 6759 1543k 389.3s 8569 365 3655 78.44% 0.0044718657 0.0584730533 92.35% 9965 68 6831 1562k 394.3s 8758 379 3742 79.19% 0.0044718657 0.0584730533 92.35% 10122 35 6958 1579k 399.4s 8888 390 3802 79.26% 0.0044718657 0.0584730533 92.35% 9238 52 7047 1597k 404.4s 9006 390 3861 79.79% 0.0044718657 0.0584730533 92.35% 9849 59 7122 1616k 409.5s 9063 386 3891 80.07% 0.00598983999 0.0584730533 89.76% 9736 50 7158 1631k 414.5s 9168 386 3942 80.96% 0.00598983999 0.0584730533 89.76% 9993 63 7241 1649k 419.6s 9310 406 4005 82.05% 0.00598983999 0.0584730533 89.76% 10489 76 7357 1667k 424.9s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 9495 429 4085 82.10% 0.00598983999 0.0584730533 89.76% 9488 42 7516 1686k 430.0s 9662 455 4153 82.12% 0.00598983999 0.0584730533 89.76% 9765 51 7620 1703k 435.0s 9724 462 4183 82.13% 0.00598983999 0.0584730533 89.76% 9129 90 7666 1712k 440.5s 9861 475 4244 82.14% 0.00598983999 0.0584730533 89.76% 10095 78 7755 1729k 445.5s 9982 492 4298 82.15% 0.00599172376 0.0584730533 89.75% 7654 83 7836 1748k 450.6s 10104 513 4346 82.15% 0.00599172376 0.0584730533 89.75% 8425 94 7898 1766k 455.6s Restarting search from the root node Model after restart has 1152 rows, 990 cols (39 bin., 0 int., 0 impl., 951 cont.), and 42855 nonzeros 10182 0 0 0.00% 0.00599172376 0.0584730533 89.75% 90 0 0 1780k 459.7s 10182 0 0 0.00% 0.00599172376 0.0584730533 89.75% 90 9 9 1781k 459.8s 10401 29 89 53.21% 0.00599172376 0.0584730533 89.75% 1222 26 148 1801k 464.9s 10587 57 168 70.08% 0.00599172376 0.0584730533 89.75% 3366 53 283 1830k 471.4s 10836 95 262 74.17% 0.0070120559 0.0584730533 88.01% 4494 46 412 1850k 476.6s 10965 112 317 80.94% 0.0070120559 0.0584730533 88.01% 5549 55 493 1867k 482.9s 11139 145 385 82.52% 0.0146594215 0.0584730533 74.93% 4710 50 604 1885k 488.9s 11317 176 457 85.03% 0.0176698194 0.0584730533 69.78% 4893 51 692 1902k 493.9s 11516 220 535 85.17% 0.0223330481 0.0584730533 61.81% 5411 48 792 1916k 499.1s 11638 222 589 86.93% 0.0224681328 0.0584730533 61.58% 5291 33 854 1931k 504.2s T 11676 174 606 88.29% 0.0224681328 0.0554554748 59.48% 5431 35 871 1937k 506.1s T 11687 118 612 93.91% 0.0224681328 0.0498354344 54.92% 5437 35 877 1937k 506.3s T 11730 97 633 94.22% 0.0224681328 0.0460846816 51.25% 5457 35 897 1939k 506.9s 11835 103 682 95.19% 0.0317301163 0.0460846816 31.15% 6578 55 981 1952k 512.0s Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 11926 94 732 95.41% 0.0354774217 0.0460846816 23.02% 6661 26 1043 1966k 517.2s 11987 75 773 95.63% 0.0365260193 0.0460846816 20.74% 5865 27 1094 1978k 522.5s 12090 67 822 96.13% 0.037204082 0.0460846816 19.27% 5267 49 1164 1990k 528.1s 12154 51 862 97.74% 0.0389159787 0.0460846816 15.56% 4599 46 1206 2004k 533.4s 12197 38 890 97.93% 0.0397913885 0.0460846816 13.66% 5137 40 1242 2014k 538.4s 12261 25 928 99.16% 0.0416131647 0.0460846816 9.70% 5358 45 1294 2023k 543.6s Solving report Status Optimal Primal bound 0.0460846815889 Dual bound 0.0460828522316 Gap 0.00397% (tolerance: 0.01%) Solution status feasible 0.0460846815889 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 547.73 (total) 0.12 (presolve) 0.00 (postsolve) Nodes 12314 LP iterations 2037617 (total) 139358 (strong br.) 70276 (separation) 149604 (heuristics) 548.116698 seconds (1.90 M allocations: 72.457 MiB)
Dict{Any, Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 547.737 :TotalTime => 548.117 :Perturbation => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :PerturbedInput => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :TighteningApproach => "lp" :PerturbationFamily => unrestricted :SolveStatus => OPTIMAL :Model => A JuMP Model… :Output => AffExpr[-0.012063867412507534 _[865] + 0.6606525778770… :PredictedIndex => 8
Set MIPGap
for Gurobi
, and mip_abs_gap
for HiGHS
.
@time d = MIPVerify.find_adversarial_example(
n1,
sample_image,
10,
HiGHS.Optimizer,
Dict("mip_abs_gap" => 0.4),
tightening_algorithm = lp,
norm_order=Inf
)
[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. Running HiGHS 1.4.2 [date: 1970-01-01, git hash: f797c1ab6] Copyright (c) 2022 ERGO-Code under MIT licence terms Presolving model 1203 rows, 1020 cols, 66828 nonzeros 1203 rows, 1020 cols, 66828 nonzeros Solving MIP model with: 1203 rows 1020 cols (60 binary, 0 integer, 0 implied int., 960 continuous) 66828 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s 0 0 0 0.00% 0 inf inf 0 0 36 1504 0.2s R 0 0 0 0.00% 0 0.2260962872 100.00% 2331 37 517 1954 1.2s Solving report Status Optimal Primal bound 0.22609628722 Dual bound 0 Gap 100% (tolerance: 176.92%) Solution status feasible 0.22609628722 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 1.23 (total) 0.02 (presolve) 0.00 (postsolve) Nodes 1 LP iterations 1954 (total) 0 (strong br.) 450 (separation) 0 (heuristics) 1.617358 seconds (1.90 M allocations: 72.457 MiB)
Dict{Any, Any} with 11 entries: :TargetIndexes => [10] :SolveTime => 1.23475 :TotalTime => 1.61724 :Perturbation => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :PerturbedInput => [_[1] _[2] … _[27] _[28];;; _[29] _[30] … _[55] _[56];… :TighteningApproach => "lp" :PerturbationFamily => unrestricted :SolveStatus => OPTIMAL :Model => A JuMP Model… :Output => AffExpr[-0.012063867412507534 _[865] + 0.6606525778770… :PredictedIndex => 8
Whew! That was a lot. The next tutorial will introduce you to everything you can extract from the results dictionary.