Sound and Complete Neural Network Repair with Minimality and Locality Guarantees
Authors: Feisi Fu
Wenchao Li
Venue: ICLR 2022 Poster (2022)
Keywords: Neural Network Repair

Abstract: We present a novel methodology for repairing neural networks that use ReLU activation functions. Unlike existing methods that rely on modifying the weights of a neural network which can induce a global change in the function space, our approach applies only a localized change in the function space while still guaranteeing the removal of the buggy behavior. By leveraging the piecewise linear nature of ReLU networks, our approach can efficiently construct a patch network tailored to the linear region where the buggy input resides, which when combined with the original network, provably corrects the behavior on the buggy input. Our method is both sound and complete -- the repaired network is guaranteed to fix the buggy input, and a patch is guaranteed to be found for any buggy input. Moreover, our approach preserves the continuous piecewise linear nature of ReLU networks, automatically generalizes the repair to all the points including other undetected buggy inputs inside the repair region, is minimal in terms of changes in the function space, and guarantees that outputs on inputs away from the repair region are unaltered. On several benchmarks, we show that our approach significantly outperforms existing methods in terms of locality and limiting negative side effects.

Published as a conference paper at ICLR 2022
SOUND AND COMPLETE NEURAL NETWORK REPAIR WITH MINIMALITY AND LOCALITY GUARANTEES
Feisi Fu Division of System Engineering Boston University fufeisi @bu.edu
Wenchao Li
Department of Electrical and Computer Engineering Boston University wenchao bu edu
ABSTRACT
We present a novel methodology for repairing neural networks that use ReLU ac- tivation functions. Unlike existing methods that rely on modifying the weights of neural network which induce a global change in the function space, our approach applies only a localized change in the function space while still guar- anteeing the removal of the buggy behavior. By leveraging the piecewise linear nature of ReLU networks, our approach can efficiently construct a patch network tailored to the linear region where the buggy input resides, which when combined with the original network, provably corrects the behavior on the buggy input. Our method is both sound and complete the repaired network is guaranteed to fix the buggy input, and a patch is guaranteed to be found for any buggy input. Moreover, our approach preserves the continuous piecewise linear nature of ReLU networks. automatically generalizes the repair to all the points including other undetected buggy inputs inside the repair region, is minimal in terms of changes in the fune- tion space, and guarantees that outputs inputs away from the repair region are unaltered. On several benchmarks, we show that our approach significantly out- performs existing methods in terms of locality and limiting negative side effects.
INTRODUCTION
Deep neural networks (DNNs) have demonstrated impressive performances on wide variety of applications ranging from transportation Bojarski et al. (2016) to health care Shahid et al. (2019). However, DNNs are not perfect. In many cases, especially when the DNNs are used in safety-critical contexts, is important to correct erroncous outputs of DNN as they are discovered after training. For instance, neural network in charge of giving control advisories to the pilots in aircraft collision avoidance system, such as the ACAS Xu network from Julian et al. (2019), may produce an incorrect advisory for certain situations and cause the aircraft to turn towards the incoming aircraft, thereby jeopardizing the safety of both airplanes. In this paper, we consider the problem of neural network repair, i.e. given trained neural network and a set of buggy inputs (inputs on which the neural network produces incorrect predictions), repair the network so that the resulting network on those buggy inputs behave according some given correctness specification. Ideally, the changes to the neural network function should be small so that the outputs on other inputs are either unchanged or altered in small way. Existing works on neural network repair roughly fall into three categories.
1. Retrainingffine-tuniin tuming The idea is to retrain or fine-tune the network with the newly identified buggy inputs and the corresponding corrected outputs. Methods include counterexample guided data augmentation Dreossi et al. (2018); Ren et al. (2020), editable training Sinitsin et al. (2020) and training input selection Ma al. (2018). One major weakness of these approaches is the lack of formal guarantees at the end of retraining/fine-tuiii inputs are fixed and no new bugs are introduced. In addition, retraining can be very expensive and requires access to the original training data which is impractical in cases where the neural network is obtained from a third party or the training data is private. tuning, on the other hand, often faces the issue of catastrophic forgetting Kirkpatrick et al. (2017).
there is guarantee that the given buggy
2. Direct weight modification. These approaches directly manipulate the weights in a neural network to fix the buggy inputs. The repair problem is typically cast into an optimization problem

---

Published as a conference paper at ICLR 2022
X
X
X
Retraining or direct weight modification
Decoupled DNN
Our approach
Figure 1: Comparison of different approaches to the neural network repair problem. The black lines represent the original neural network function. The red dot represents the buggy input. The colored lines represent the functions after the repairs are done.
or a verification problem. For example, Dong et al. (2020) proposes to minimize loss defined on the buggy inputs. Goldberger et al. (2020) uses an SMT solver to identify minimal weight changes to the output layer of the network so that the undesirable behaviors are removed. Usman el. (2021) first locates potentially faulty weights in layer and then uses constraint solving to find weights modification that can fix the failures. In general, the optimization-bann removal of the buggy behaviors, and the verification- based approach does not scale beyond networks of a few hundred neurons. In addition, these approaches can suffer from substantial accuracy drops on normal inputs since weight changes may be a poor proxy for changes in the function space.
approach cannot guarantee
3. Architecture extension. The third category of approaches extends the given NN architecture, such as by introducing more weight parameters, to facilitate more efficient repairs. The so-called Decoupled DNN architecture Sotoudeh & Thakur (2021) is the only work we know that falls into this category. Their idea is to decouple the activations of the network from values of the network by augmenting the original network. Their construction allows the formulation of any single-layer repair as an linear programming (LP) problem. The decoupling, however, causes the repaired net- work to become discontinuous (in the functional sense). In addition, it still cannot isolate the output change to a single buggy input from the rest of the inputs.
In addition to the aforementioned limitations, a common weakness that is shared amongst these methods that the induced changes, as a result of either retraining or direct weight modification, are global. This means that correct behavior on another input, regardless of how far it is away from the buggy input, may not be preserved by the repair. Worse still, the repair on new buggy input can end up invalidating the repair on previous buggy input. The fundamental issue here is that limiting the changes to a few weights or a single layer only poses a structural constraint (often for ease of computation); it does not limit the changes on the input-output mapping of the neural network. It is known that even a single weight change can have a global effect on the output of a neural network.
In this paper, we propose REASSURE, novel methodology for neural network repair with locality, minimality, soundness and completeness guarantees. Our methodology targets continuous piecewise linear (CPWL) neural networks, specifically those that use the ReLU activation functions. The key idea of our approach is to leverage the CPWL property of ReLU networks to synthesize a patch network tailored to the linear region where the buggy inpul resides, which when combined with the original network, provably corrects the behavior on the buggy input. Our approach is both sound and complete- the repaired network guaranteed fix the buggy input, and a patch is guaranteed to be found for any buggy input. Moreover, our approach preserves the CPWI. nature of ReLU networks, automatically generalizes the repair to all the points including other undetected buggy inputs inside the repair region, is minimal in terms of changes in the function space, and guarantees that outputs on inputs away from the repair region are unaltered. Figure I provides an illustrative comparison of our approach with other methods. Table I compares our approach with representative related works in terms of theoretical guarantees. We summarize our contributions below.
1. We present REASSURE, the first sound and complete repair methodology for ReLU networks with strong thcoretical guarantees.
2. Our technique synthesizes patch network, which when combined with the original neural network, provably corrects the behavior on the buggy input. This approach is a significant departure from existing methods that rely on retraining direct weight manipulation.
3. Across a set of benchmarks, REASSURE can efficiently correct a set of buggy inputs or buggy areas with little change to the accuracy and overall functionality of the network.
2

---

Published as a conference paper at ICLR 2022
REASSURE
Retrain
MINN
Editable Fine- Fine-Tuning
PRINN
Preservation of CPWL Soundness Completeness Area Repair
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
No
No
No
Yes
No
No
Minimal Change
Yes (Function Space)
No
Yes (Weight Space)
No
Yos (Weight Space)
Localized Chunge
Yes
No
No
No
No
Limited Side Effect
Yes
No
No
No
No
Comparing REAS with representative related works in terms of theoretical guarantees. CPWL, stands for continuous piecewise linearity. Area repair means repairing all the (infinitely many) points inside an area. Limited side effect means the repair can limit potential adverse effects on other inputs. MDNN is the verification-bass approach from Goldberger et al. (2020), PRDNN is the Decoupled DNN approach from Sotoudeh & Thakur (2021). REASSURE is the only method that can provide the guarantees.
Table 1:
2
BACKGROUND
2.1 DEEP NEURAL NETWORKS
An R-layer feed-forward DNN f O 00000 X + Y is a composition of linear functions Kr, 1,2,... R and activation function o, where X C m is a bounded input domain and Y S 8nt is the output domain. Weights and biases of linear function {Kr (rr,r=1,..., parameters of the DNN.
We call the first R - layers hidden layers and the R-th layer the output layer. We use 2f to denote i-th neuron (before activation) in the j-th hidden layer.
In this paper, focus ReLU DNNs, i.c. DNNs that use only the ReLU activation functions. is known that an IRm + E function representable by ReLU DNN if and only if a continuous piecewise linear (CPWL) function Arora et al. (2016). The ReLU function is defined as (x) = max(x,00) 0). We say that (I) is activated if (xx x.
2.2 LINEAR REGIONS
A linear region A is the of inputs that correspond to the same activation pattern in ReLU DNN Serra et al. (2017). Geometrically, this corresponds to a convex polytope, which an intersection of half spaces, in the input space which is linear. We use flA denote the part of f on A.
2.3 CORRECTNESS SPECIFICATION
A correctness specification & = (2in 4 out) is tuple of two polytopes, where 2,n is the union of some linear regions and c out convex polytope. DNN f is said to meet specification + = (Pin. T D, denoted as f = Φ. if and only if Vz E Pin. f(x) Dout-
Example 1. For classification problem, we can formally write the specification that "the pre- diction of any point in an area A is class k" as $ = (Iin Pout), where Pin = A and Dout= R ys 2 vs Vi k}
2.4 PROBLEM DEFINITION
In this paper, we consider the following two repair problems.
Definition 1 (Area repair). Given correctness specification 4 = (4 D and ReLU DNN + T. the area repair problem is find modified ReLU DNN f such that T.
Note that we do not require f to have the same structure or parameters as f in this definition. If Pi.. contains single (buggy) linear region, we refer this as single- regior repair. If 4in. contains multiple (buggy) linear regions, we refer to it as multi-region repair.
Note that here y is the output of the layer right hefore the softmax layer in classification network.
3

---

Published as a conference paper at ICLR 2022
Definition 2 (Point-wise repair). Given set of buggy inputs (Ø1...., FL C Din with their corre- sponding correct outputs fy1..... and a ReLU DNN f, the point-wise repair problem is to find modified ReLU DNN f such that vi, f(z:) Vi-
We call the minimal variants of area repair and point-wise repair minimal area repair and minimal point-wise repair respectively. Minimality here is defined with respect to the maximum distance between f and I over the whole input domain X. A point-wise repair can be generalized to area repair through the following result.
2.5 FROM BUGGY INPUTS TO BUGGY LINEAR REGIONS
The linear region where input resides can be computed as follows.
Lemma 1. Lee al. (2019) Consider ReLU DNN f and an input x X. For every neuron zf. induces a feasible set
Az(x) ( { E X XI (V=2)) -V==) 0}
if 2
if <0
The set A(x) A)) is the linear region that includes x. Note that A(x) is essentially the H-representation of the corresponding convex polytope.
2.6 REPAIR DESIDERATA
We argue that an effective repair algorithm for ReLU DNN should satisfy the following criteria.
Preservation of CPWL: Given that the original network f models a CPWL function, the repaired network f should still model a CPWL function. 2. Soundness: sound repair should completely remove the known buggy behaviors, i.c. it is a solution to the point-wiss repair problem defined in Definition 2. 3. Completeness: Ideally, the algorithm should always be able find a repair for any given buggy input if it exists. 4. Generalization: If there exists another buggy input F' in the neighborhood of (e.g. the same linear region), then the repair should also fix it. For example, suppose have an T that violates specification which requires the output be within some range. is almost guaranteed that there exists another (and infinitely many) F' in the same linear region that also violates the specification. 5. Locality: We argue that good repair should only induce localized change to f in the function space. For example, in the context of ReLU DNN, if linear region B does not border the repair region A, i.e. Bn = 0. then flx(x) fls(z). 6. Minimality: Some notion of distance between and such as max I fl should be minimized. Note that this is significant departure from existing methods that focus on minimizing the change in weights which has no guarantee on the amount of change in the funetion space. 7. Limited side effect: Repairing buggy point should not adversely affect points that were originally correct. For example, repairing a buggy input T in region A should not change another region from correct to incorrect. Formally, for any linear region who is a neighbor of A, i.e. Cn A * 6, if fle += 6 then Aee }= $ 8. Efficiency: The repair algorithm should terminate in polynomial time with respect the size of the neural network and the number of buggy inputs.
3
OUR APPROACH
We will first describe our approach to single-region repair and then present our approach multi- region repair which builds on results obtained from the single-region case.
Given a linear region A, our overarching approach is to synthesize a patch network hA such that f= + A and f } Φ. The patch network l is a combination of two sub-networks: a support network 9.4. which behaves like characteristic function, to determine whether an input is in A, and an affine patch function network (Λ(x) = Cx + d to ensure (f + PA) }= T on A.
3.1 RUNNING EXAMPLE
We use the following example illustrate our idea.
4

---

Published as a conference paper at ICLR 2022
X1
P
hA
Z1
X-2
1
7/2
Left: the target DNN with buggy inputs. Right: the REASSURE-repaired DNN with the patch network shown red. Support network 9.A is for approximating the characteristic function on A; Affine patch function PA ensures the satisfaction & on A: The design of the patch network ha ensures locality for the final patch.
Figure 2:
Example Consider repairing the ReLU DNN f in Figure 2 according the correctness specifi- cation Vo E [0, 1]2 1 y E [0, The DNN consists of a single hidden layer with two neurons ž and 22. where y = ( o (22), 21 I1 + 2x and 22
2x1
22.
The only linear region that violates our specification is A {x 12 x1, 32 + 2x² 1 2 0, 2x,
x2 2 0). ( = 0.9) E [0, 1]² but f(z) = 2.6 $ [0.2]
The network fx) the linear region is the affine function fla(x) 3x, x ----2-1 1. Our algorithm first sets up an affine function PA(x)) that minimally repairs on A, such that Vo e (x) 2). Later in the paper, we will show (x))) can be found by solving LP problem. The resulting patch function is Pa(x) - - 2.2
A, f() +
However, directly apply f(x) + Pa(x) as the patch network will have side effects on areas outside of A. Our strategy is to combine (x) with support network g4(2) which outputs 1 on A and drops to quickly outside of A. The final repaired network f(x) + (p)( + 9.4 9 10)
1) o)-A(-)((z) + (x, 10) - 1). This structure makes PA almost only active on A and achieve localized repair. Observe that this still a ReLU DNN.
3.2 SUPPORT NETWORKS
Support networks are neural networks with special structure that can approximate the characteristic function of convex polytope. They are keys to ensuring localized repairs in our algorithm.
Assume that the linear region we need to repair is A = {ar aax S b, E 1}, where |/] is the number of linear inequalities. The support network of AA is defined as:
gA(x,7) 7) a( Σ g(b: a, 17)+1)
iE!
where g(x, 7) = o(v + 1) - (7z=) and 7 is parameter of our algorithm that controls how quickly SA(x, 7) goes to zero outside of A.
Remark: For any x E A, we have 9.4 (xr, 7) = 1, i.e. the support network fully activated. For any
E A. if for one of i E T, we have 0,2 44 S - 1177, then 9A (x, 7)
Observe that (z. 7) is not zero when very close to due the requirement for preserving CPWL. In Theorem 3, prove that we can still guarantee limited side effects the whole input domain outside A with this construction.
3.3 AFFINE PATCH FUNCTIONS
We consider an affine patch function (z) = cr+ where matrix c and vector are undetermined coefficients. In later section, the design of patch network will ensure that on the patch area A, the repaired network is f()) + (z)). We will first consider finding appropriate e and such that [() (*) satisfy the specification on A.
5

---

Published as a conference paper at ICLR 2022
To satisfy the specification Q. we need f(z) + pa(x) Dout for all x E A. To obtain a minimal repair, we minimize max maxxEA/PA(()) Thus, we can formulate the following optimization problem
mine, max (axx=ealp(()) -cr + (c, {(c,d) f()) + cr + d & Pout: Vo E A}
Notice that this is not an LP since both c and z are variables and we have ca term in the objective.
In general, one can solve it by enumerating all the vertices of A. Suppose that {va|s 1, ..... S} the set of vertices of A. Since Pott a convex polytope, we have
f(x) + pA(x)) E Pout for all x E A + f(v.) + PA(Vs) E Pout = 2.... S.
(4)
and
max Jez + d max (Cu, +
(5)
Hence, we can solve the following equivalent LP.
mine,d H H (ov, d)i, H 2 -cvv, + d)r,for 1,2,..., and 1,2,... + PP(u)) E Pout. for
(6)
1.2..... 1,,,,....,
where H E IR and will take m2... s/cv, + dl when optimal.
In general, the number of vertices of convex polytope can be exponential in the size of its H- representation Henk et al. (1997) and enumerating the vertices of a convex polytope is known to be expensive especially when the input dimension is large Bremner (1997). In Appendix 7.1. we show that we can solve programming 3 via LP without verfex emumeration for many useful cases such as the classification problem Example and make our algorithm much more efficient.
3.4 SINGLE-REGION REPAIRS
With a support network 9A and an affine patch function PA. we can synthesize the final patch network as follows:
ha(a, 7) (p)(#)) + K 24(2, 7) K) o--PA(()) + K g2(x,)) K)
(7)
where K is vector where every entry is equal to the upper bound of (Ipd E X}.
Remark: For x E A, (2 7) 1, then we have ha(z,)) (p)((x)) o(-pa(=)) = pa(x). For & A. 9. (2, 7) goes to zero quickly if y is large. When gA(5,)) = 0, we have (
(pA(T) K) (-P.A(s)) K) =0
The repaired network f(x) ((x) + (4
7). Since I and hA are both ReLU DNNs, we have also a ReLU DNN. We will give the formal guarantees correctness in Theorem 1.
3.5 MULTI-REGION REPAIRS
Suppose there two linear regions, An and A2, that need to be repaired, and we have generated the affine patch function PAd (x) for A₁ and P.Aa (I) for Ag.
If Ai n.42 = 0. then we can repair [() with f(x) [(x) hA, (z, 7) + hay (ar, 7) directly, since hA, (z. 7) and h,,, (I, 7) will not be nonzero at the same time when 7 is large enough.
However, if A1 n Ag * 0. for any Ai O Ag, both h,, (z, 7) and hA, (z, will alter the value of f on æ, which will invalidate both repairs and cannot guarantce that the repaired DNN will meet the specification कb To avoid such over-repairs, and then repair A₂ with P.,, (x) PA, (z). Figure provides an illustration of a three-region case.
strategy is to first repair Ai U Ag with P.A, (x),
In general, for multi-region repair, note {Ai 1=1.2..... all the buggy linear regions. Then compute the support network 9.4, (z, 7) and affine patch function P.A, (x) for each A,. Note that this computation can be done in parallel.

---

Published as a conference paper at ICLR 2022
Ag PA
As 1.M
P.Ao
As
As
Aa PM
A PM
Ao Pa.
:
PA
Figure 3: An illustration of multi-region repair with three different repair regions. Left: the original DNN; Middle Left: repair Ai U A2 U A3 with PAi Middle Right: repair A U A3 with PAa PA1 Right:
repair Ag with P.g. P.A.
Once we have (I, 7) and P.A. (2), we can "stitch" multiple local patches into a final patch as follows.
h(x,7)
Σ (o(p) PAi (2)
max (2, 7)] Ki)
f2!
-0 + PA._, (x) + max
(94, (z, Ji Ki)l
j24
where K₁ is the upper bound of {IPA, (z) PA (z) bc } and (A) = 0.
Remark: max/21(04, (2, is a support function for ررورА and its value for any æ e Uj2(Aj-
THEORETICAL GUARANTEES
In this section, we present the theoretical guarantees that REASSURE provides, and point the readers to proofs of the theorems in the Appendix.
Theorem (Soundness). The repaired DNN f returned by REASSURE is guaranteed to satisfy the specification d
Theorem (Completeness). REASSURE can always solution to the minimal point-wise repair or the minimal area repair problem.
For any A, the support network ensures that the patch network goes to zero quickly when æ is away from A. However, it still makes small change the neighbors of A. The following theorem shows that for a big enough 7, the patch network would not change correct region into incorrect. Theorem 3 (Limited Side Effect). Given correctness property 4 (o Lous), patch region A and the corresponding patch network h(x, 7), there exists a positive number such that for any y D, we have
1. for any linear region B, if A then f(x,)) = f(x):
2. for any linear region C who is neighbor of A 0), if fle - d, then fe(x, 7) T &. Corollary (Incremental Repair). For multiple-region repair, the patch for new region A' would not cause previous patched region A to become incorrect.
Theorem 4 (Minimum Repair). For any ReLU DNN f. which is linear on patch region A and satisfies the specification 4 there exists a positive number I, such that for all 7 2
max ff(z) ff=)) 2 max hA( 7))- xEX
(9)
zEX
Theorem's (Polynomial- Time Efficiency). REASSURE terminates polynomial in the size of
the neural network and the number of buggy linear regions when Pout takes the form of (y S Py S }u} where is a full row rank matrix and - oc (rl1) S quli +00 (g((1) and qu (i) are the i-th elements of and qu respectively).
5 EXPERIMENTS
In this Section, we compare REASSURE with otate-of-the-art methods on both point-wise repairs and area repairs. The experiments were designed to answer the following questions: (Effectiveness)

---

Published as a conference paper at ICLR 2022
REASSURE
Retrain (Requires Training Data)
AP
(D(
NDKL,)
NDP(L.)))
NDP(L)
Ace
NDCL..)
ND(Lg)
NDP(L.>))
NDP(Lg)
Acc
0.01%
0.01%
25.75%
24.78%
98.1%
1.13%
1.09%
77.80%
77.60%
98.1%
20
0.03%
0.02%
19.17%
18.70%
98.2%
0.92%
0.89%
77.14%
76.
98.4 %
0.06%
0.06%
24.64%
23.79%
98.5%
0.84%
0.82%
84.17%
82.15%
98.7% %
0.11%
0.12%
25.40%
24.44%
99.0%
0.84%
0.82%
84.83%
83.05%
99.0%
Fine- TiniinTunigg
PRDNN
ND(
2D(
(DP(L.))
NDP(L))
Acc
ND(
ND(2g)
(DP(L2)
Acc
10 2.20%
2.11%
67.61%
65.52%
97.6%
1.41%
1.34%
34.00%
33.59%
97.8%
20
23.199
22.35%
82.87%
78.55%
78.
2.88%
2.74%
43.63%
41.78%
97.1%
35.78%
34.04%
84.73%
80.58%
67.0%
4.79%
4.47%
49.37%
46.31%
96.7%
100
23.83%
22.11%
79.73%
76.57%
81.9%
9.16%
8.20%
51.23%
46.34%
96.1%
Table 2: Point-wise Repairs on MNIST. We use the first hidden layer as the repair layer for PRDNN. The test accuracy of the original DNN is 98.0%. #P: number of buggy points to repair. ND(L.)), ND(L2): average (L L2) norm difference on both training and test data. NDP(L.c). 22)( average (Io In) norm difference on random sampled points near the buggy points. Acc: accuracy on test data. Note that REASSURE automatically performs area repairs on 784-dimensional inputs.
How effective is repair in removing known buggy behaviors? (Locality) How much side effect (i.e. modification outside the patch area in the function space) does repair produce? (Function Change How much does a repair change the original neural network in the function space? (Performance) Whether and how much does repair adversely affect the overall performance of the neural network?
Efficacy (E); % of given buggy points or buggy linear regions that are repaired. 2. Norm Difference (ND): average normalized norm (Le or L2) difference between the original DNN and the repaired DNN on a set of inputs (e.g. training and testing data; more details in the tables). We use ND measure how repair change the original neural network on function space. 3. Norm Difference on Patch Area (NDP): average normalized norm (Tox 12) difference between the original DNN and the repaired DNN on patch areas (calculated on random sampled points on patch areas or near the buggy points; details in the tables). We use NDP to measure the locality of a repair. 4. Accuracy (Ace): accuracy on training or testing data to measure the extent to which a repair preserves the performance of the original neural network. 5. Negative Side Effeet (NSE): NSE is only for area repair. It is the percentage of correct linear regions (outside of patch area) that become incorrect after repair. If a repair has nonzero NSE, the new repair may invalidate a previous repair and lead a circular repair problem.
We consider the following evaluation criteria:
We compared REASSURE with the representative related works in Table 1. REASSURE, MDNN and PRDNN guarantee to repair all the buggy points (linear regions). Retrain and Fine-Tuning cannot guarantee 100% efficacy in general and we run them until all the buggy points are repaired.
5.1 POINT-WISE REPAIRS: MNIST
We train a ReLU DNN on the MNIST dataset LeCun (1998) as the target DNN. The goal of repair fix the behaviors of the target DNN buggy inputs that found in the test dataset. Thus, the repaired DNN is expected to produce correct predictions for all the buggy inputs.
The results shown in Table 2. REASSURE achieves almost
modification outside the patch area (ND) amongst all four methods. In addition, REASSURE produces the smallest modification on the patch area (NDP) and preserves the performance of the original DNN (almost drop on Acc).
5.2 AREA REPAIRS: HCAS
To the best of our knowledge, Sotoudeh & Thakur (2021) is the only other method that supports area repairs. In this experiment, we compare REASSURE with Sotoudch & Thakur (2021) 1) on an experiment where the setting similar to the 2D Polytope ACAS Xu repair in their paper.
Sotoudeh & Thakur (2021) does not include a vertex enumeration tool (which is required for setting up their LP problem) in their code. We use pyeddlib ib Troffaes (2018) to perform the vertex enumeration step when evaluating PRDNN. Note that the vertex enumeration tool does not affect the experimental results except running time.
8

---

Published as a conference paper at ICLR 2022
REASSURE
PRDNN NSE
#A
(D(L)))
NSE
Acc
T
ND(L.))
Acc
T
10
0.00%
0.0%
0%
98.1%
1.0422
0.10%
31.0%
4%
89.6%
7.90+0.100
20
0.00%
2.2%
0%
98.1%
1.1856
0.15%
37.2%
8%
83.1%
5.81+0.188
50
0.00%
17.6%
0%
98.1%
1.8174
0.15%
38.4%
8%
83.8%
14.54+0.388
87
0.04%
45.9%
0%
97.8%
2.4571
0.14%
46.6%
0%
85.6%
25.30+0.714
Table 3: Area Repairs on HCAS. We use the the first hidden layer as the repair layer for PRDNN. Results PRDNN using the last layer (which are inferior to using the first layer) shown in
Table 6 in the Appendix 7.4. The test accuracy of the original DNN is 97.9%. #A: number of buggy linear regions repair. ND(Le)): average Loo norm difference on training data. NDP(L average Loo norm difference on random sampled data on input constraints of specification 1. NSE: % of correct linear regions changed incorrect by the repair. Acc: accuracy on training data (no testing data available). T: running time in seconds. For PRINN, the first running time is for enumerating all the vertices of the polytopes and the second for solving the LP problem in PRDNN.
REASSURE (feature space)
Retrain (Requires Training Data)
Tine-Tuning
PRDNN
#P
ND(
ND(1))
Acc
ND
NDKLa)
Acc
ND(
ND(Lg)
Acc
ND(L.))
ND(L,)
Acc
10
0.15%
0.13%
82.5%
43.43%
36.04%
80.1%
29.45%
25.27%
77.9%
22.93%
21.13%
82.1%
0.11%
35.69%
82.9%
69.16%
57.47%
68.5%
20.03%
80.1%
50
0.79%
0.70%
81.3%
50.23%
42.86%
82.1%
76.69%
63.46%
66.9%
30.96%
26.94%
68.9%
Table 4: Point-wise Repairs on ImageNet. PRDNN uses parameters in the last layer for repair. The test accuracy for the original DNN is 83.1%. #P: number of buggy points to repair. ND(Ls)), ND(L2): average (Le,, L2) norm difference validation data. Ace: accuracy validation data. means Retrain only repair 96% buggy points in 100 epochs.
We consider an area repair where the target DNN is the HCAS network (simplified version of ACAS Xu)² N1.1 1 (previous advisory equal to 1 and time loss of vertical separation equal to 20s) from Julian & Kochenderfer (2019). We use Specification 1 (details in Appendix 7.4), which is similar to Property 5 in Katz al. (2017). We compute all the linear regions for N1,4 in the area a... of Specification 1 and 87 buggy linear regions were found. We apply both REASSURE and PRDNN to repair those buggy linear regions. We use Specification 2 (details Appendix 7.4), the dual of Specification 1, to test the negative side effect (NSE) of repair.
The results are shown in Table Both REASSURE and PRDNN successfully repair all the buggy linear regions. REASSURE produces repairs that are significantly better in terms of locality (ND), minimality (NDP) and performance preservation (Acc).
5.3 SEATURE-SPACE REPAIRS
In general, when repairing a large DNN with a high input dimension, the number of linear constraints for one patch area A will be huge and pose challenge solving the resulting LP.
One advantage of our approach, which can be used to mitigate this problem, is that it allows for point-wise and area repairs in the feature space in principled manner, i.e. constructing patch network starting from an intermediate layer. This approach still preserves soundness and complete- ness, and is fundamentally different from just picking a single layer for repair in PRDNN or MDNN. Experimental results on repairing AlexNet Krizhevsky et al. (2012) for the ImageNet dataset Rus- sakovsky et al. (2015) in Appendix 7.4 show REASSURE (feature space) is still significantly better in term of locality(ND) and minimality (NDP).
CONCLUSION
We have presented novel approach for repairing ReLU DNNs with strong theoretical guarantees. Across a set of benchmarks, our approach significantly outperforms existing methods in terms of efficacy, locality, and limiting negative side effects. Future directions include further investigation on feature-space repairs and identifying a lower-bound for
"The technique in PRDNN for computing linear regions does not scale beyond two dimensions as stated in their paper. The input space of HCAS is 3D and that of ACAS Xu is SD we use HCAS in order to run their tool in our evaluation of repairs.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
This effort was partially supported by the Intelligence Advanced Research Projects Agency (IARPA) under the contract W91 INF20C0038. The content of this paper does necessarily reflect the position or the policy of the Government, and no official endorsement should be inferred.
REFERENCES
Yossi Adi, Carsten Baum, Moustapha Cisse, Benny Pinkas, and Joseph Keshet. Turning your weak- ness into a strength: Watermarking deep neural networks by backdooring. In 27th {USENIX)
Security Symposium (!USENIX) Security 18), pp. 1615-1631, 2018. 16
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. CoRR, abs/1611.01491, 2016. URL http:://axxx
org/abs/ /aaaas//1l. 01491.4 18
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, Xin Zhang, Jake Zhao, and Karol Zieba. End to end learning for self-driving cars. CoRR, abs/1604.07316, 2016.
David D Bremner. On the complexity of vertex and facet enumeration for convex polytopes. PhD thesis, Citeseer, 1997. 6
Guoliang Dong, Jun Sun, Jingyi Wang, Xinyu Wang, and Ting Dai. Towards repairing neural net- works correctly. arXiv preprint arXiv:2012.01872. 2020. 2
Tommaso Dreossi, Shromona Ghosh, Xiangyu Yue, Kurt Keutzer, Alberto Sangiovanni- Vincentelli, and Sanjit A Seshia. Counterexample-guiee data augmentation. arXiv preprint
/rX5vv/805.06960 2018.
Ben Goldberger, Guy Katz, Yossi Adi, and Joseph Keshet. Minimal modifications of deep neural
networks using verification. In LPAR, volume 2020, pp. 23rd, 2020. 2, 3, 16
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. URL https://www.
gurobi com. 16
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adver- sarial examples. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15262-15271, 2021. 16
Martin Henk, Jürgen Richter Gebert, and Günter M. Ziegler. Basic properties of convex polytopes. In HANDBOOK OF DISCRETE AND COMPUTATIONAL GEOMETRY, CHAPTER 13, pp. 243- 270. CRC Press, Boca, 1997.
Kyle Julian and Mykel Kochenderfer. Guaranteeing safety for neural network-based aircraft col- lision avoidance systems. In 2019 IEEE/AIAA 38th Digital Avionics Systems Conference (DASC), pp. 1-10. IEEE, 2019.
Kyle D Julian, Mykel J Kochenderfer, and Michael P Owen. Deep neural network compression for aircraft collision avoidance systems. Journal of Guidance, Control, and Dynamics, 42(3): 598-608, 2019.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pp. 97-117. Springer, 2017.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinske Demis Hass- abis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. Overcoming catastrophic forget- ting in neural networks. Proceedings of the National Academy of Sciences, 114(13):3521-355 2017. ISSN 8424. doi: 10.1073/pnas.. 10.1073/pnas.611188 1833511114, content/114/10
URL https:/ /www. pnas org/
10

---

Published as a conference paper at ICLR 2022
Alex Krizhevsky, Ily Sutskever, and Geoffrey E Hinton. Imagenet classification with deep volutional neural networks. Advances in neural information processing systems, 25:1097-1105,, 2012. 9, 16, 17
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist// 1998.
Hu Lee, David Alvarez-Melis, and Tommi S Jaakkola. Towards robust, locally linear deep networks. arXiv preprint arXiv: (atp:::077007777 2019. 4
Shiqing Ma, Yingqi Liu, Wen-Chuan Lec, Xiangyu Zhang, and Ananth Grama. Mode: automated neural network model debugging via state differential analysis and input selection. In Proceed- ings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium the Foundations of Software Engineering, pp. 175-186, 2018.
Xuhong Ren, Bing Yu, Hua Qi, Felix Juefei-Xu, Zhuo Li, Wanli Xue, Lei Ma, and Jianjun Zhao. Few-shot guided mix for dnn repairing. In 2020 IEEE International Conference on Software Maintenance and Evolution (ICSME), pp. 717-721. IEEE, 2020.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy. Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3)211-255 1522, 2015. doi: 10. 1263-015-0816-- 9,
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. CoRR, abs//711. 0ts/1711.02114,, 2017. URL http: htttp://arxiv...o /argiv..rggg
b.bs/1711 02114.
Nida Shahid, Tim Rappon, and Whitney Berta. Applications of artificial neural networks in health care organizational decision-making: A scoping review. PLOS ONE, 14(2):1-22, 02 2019. doi: 10.1371/journal, pon.maolpone.021233666 URL https: http:////aa.oorg11..13////////// pone 0212356.
Anton Sinitsin, Vsevolod Plokhotnyuk, Dmitriy Pyrkin, Sergei Popov, and Artem Babenko. Editable neural networks. arXiv preprint arXiv:2004.00::4 00345, 2020.
Matthew Sotoudeh and Aditya V Thakur. Provable repair of deep neural networks. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, pp. 588-603, 2021. 2, 8,8
Matthias Troffaes. pycddlib-a python wrapper for komei fukudals cddlib, 2018. 8
Muhammad Usman, Divya Gopinath, Youcheng Sun, Yannic Noller, and Corina S Päsăreanu. Nn repair: Constraint-based repair of neural network classifiers. In International Conference on Computer Aided Verification, pp. 3-25. Springer, 2021.

---

Published as a conference paper at ICLR 2022
7 APPENDIX
7.1 REPAIR VIA LINEAR PROGRAMMING
We consider the case o out can be expressed as fyla: I Py S qu} where P is a row rank matrix and -00 Σ q: [1] qu [i] I too (q [i] and quli] are the i-th elements of qi and qu respectively).
Consider the following optimization problem.
ming max (T(())) f(x) q S P(T(f(=)) S qa Vo E A
(10)
where T: R + R" is a linear transformation on the DNN's output space RR..
Theorem 6. On linear region A, we have fla(z)= = f1r + fz for some matrix f1 and vector f2- Assuming that f1 is full rank', the optimization problem in (3) and the optimization problem in (10)
are equivalent.
Note that qi & P(T((())) 2 qu can be achieved row by row, Thus, we can find one-dimensional linear transformation via LPs and combine them into single linear transformation to solve opti- mization problem 10.
For every of P. say the i-th row, (P(f(z)) Vo E A} on the i-th dimension by solving the following LP problems
check the lower bound and upper bound of
[b|1] = min P[i](f())) ublt = max (f)(((())
(11)
zEA
zEA
where Pli] the i-th row of
Then for each row i, we take minimal linear transformation [[([2)) = 01 (x) #2li to transfer
interval [[b[i]. ub[t] inside interval qq [i), qu [i]]. We can take u 1 qu [i] 9: > ub[i] [b[i],
else v1 [i] 2- - And vy[i] = q [i]o]bb[i] if [q []]]666[0] s [ibbb]bb[]] - g. else
wh 166
en [i]bb[ qr. [i).
Since matrix P is full row rank, we can find a linear transformation 7 that is equivalent to V:
T= PーPーーー P
(12)
P
where p
is an orthogonal extension of P (P and p- are orthogonal to each other and
pl
P is full rank square matrix).
Once we have T, we can obtain an affine patch function pa(x) T(f(x)) - f(x).
7.2 THE REASSURE ALGORITHM
Algorithm REASSURE
Input: A specification & (hh.. Dout), ReLU DNN f and set of buggy points (Z1...., "5.....,,1...... C
i...
Output: A repaired ReLU DNN
1: for - 1 to L do
2: Generate the patch area Ar from buggy point ž according to Equation (1);
3: Generate support network 9A4 according to Equation (2);
4: Solve the linear programming problem (6) to find the optimal affine patch network PA-
5: end for
6: Combine all support networks SA, and the corresponding patch networks PAA, to get the overall
patch network h according Equation (8).
7: return = f
Note that for neural networks that trained by stochastic method, with probability one fi full rank.
12

---

Published as a conference paper at ICLR 2022
7.3 PROOFS OF THEOREMS
We prove Theorem after Corollary 1, since the proof of Theorem 1 uses the result of Corollary 1.
Theorem 6. On linear region A, we have fa f1x + f2 for some matrix fı and vector f2. Assuming that f1 is full rank", the optimization problem in (3) and the optimization problem in (10) are equivalent.
Proof. On one side, for any c, d. since fi is full rank, there exists linear transformation T, such that T(f(x)) = T(hx + f2) (fi c) + (f2 + d) = f(x) + cx + d.
On the other side, for any T, since T(f(z)) f(x) is linear, there exist c, d, such that cr + d T(f(x)) f(x).
Lemma 2. The repaired DNN f returned by REASSURE is guaranteed to satisfy the specification on patch area in tingl-rregon repair case.
Proof. By the definition of P.A. we have (xx - PA(x) E Pou for all A.
For any I E A, we have 9A(x, 7) = and hA(I,7) - o(pA(T)) - -o(-PA(2)) = PA((). There-
fore,
((x = f(x) (A( = f(x) PA(x)) (z) E Bout
(13)
Thus, the patched neural network î meets the specification + on A.
Theorem 2 (Completeness). REASSURE can always a solution to the minimal point-wise repair or the minimal area repair problem.
Proof. For every patch area A, we can always find a support network JA- For any & Dout and A, there exists an affine function P.A such that (a( Pout, Vo E A. Therefore, the I.P (6) always feasible and REASSURE can find an affine patch function P.4-
Once we have 94 and P.a for patch area REASSURE returns a patch network either by Equation (7) by Equation (8).
Theorem 3 (Limited Side Effect). Given a correctness property = (oin. Dot)), patch region A and the corresponding patch network h(x, there exists positive number I such that for any
2 1, we have
1. for any linear region B, if =00, then f(x,7) = f(z);
2. for any linear region C who is a neighbor of (CnA + 0), if fle F 4, then fe(x, 7) } T
Proof. Since a multi-region repair composition of multiple singe-region repairs according to Equation (8), we can prove the limited side effect of multi-region repair by proving the limited side effect of its constituent singe-region repairs. Below, we prove the limited side effect of a singe- region repair.
Consider patch area A (xc agæ S by i [} and Aso(7) (x [xx, 7) > 0}.
1. Since the number of neighbors for A are finite, we can take big enough 7, such that for any B, if B 1BAA- = 0. B Aso(7) 0. Thus, we have f(x,7) fxx on B.
For any linear region C who neighbor of A, i.e. C + and C + V. is no longer linear function on C, since there are some hyperplanes introduced by our repair that will divide C into multiple linear regions.
Specifically, those hyperplanes are {Ir 7(a,0 - -b) + 0} for i I, far Eierglaza bi,7) [4] + 1 = 0}. {a p(x) + K g2( - K = 0} and {- p(z) + K 9A(x, K = 0}.
For any point in those hyperplanes, it will fall into one of the following four cases.
Note that for neural networks that trained by stochastic method, with probability one fi full rank.
13

---

Published as a conference paper at ICLR 2022
(a) fo Maax - bb) +
0} for some I, then ga(2,7) h(x, 7) 0 and
f(x) E Pouti
(b) x E {x EiEr -(0:3 - b2, - + = 0}, then ga(I, = 0. M(2, 7) = 0 and
f(x) Pouti
(0) x E {o p(x) + K 9A(x,) - K = 0}. then p(z) = = - K ga(x,7) 2 0.
-p(x) + K -A(x,,)) - K S h(2,7) = 0 and f(x) Douti
(d) x E {z p(x) + KK (9, -K}, then p(z) K )a(a,)) K 0.p(()) (A(x.7) K 0. h(x, 7) = and f(x) E + Douei
By the above analysis, we have (x) E Pous for the boundary of the new linear regions. Since is linear on the new linear regions and Pout is convex, f(z) E Pout for any x E C.
Remark: By Theorem 3, we have that patch would not change correct linear region to an incorrect one.
Corollary (Incremental Repair). For multiple-region repair, the patch for new region A' would not cause previous patched region A to become incorrect.
Proof. After applying the patch linear region A. we have that the resulting network correct on A. When applying a new patch to another linear region A', by Theorem 3, the new patch would not make a correct linear region incorrect.
Theorem (Soundness). The repaired DNN f returned by REASSURE is guaranteed to satisfy the specification 4
Proof. The proof has two parts:
1. to show that satisfies the specification & on A, and
2. to show that satisfies the specification & outside of A.
Part 1:
Lemma (2) satisfy the specification & for single-region repair A.
For the multi-region case, consider a set of buggy linear regions U with the corresponding support neural network 9.A, and affine patch function PA for each A,. For the multi-region repair construction in Equation (8), we refer to (PA, -PA,1 + ( Ky) as the j-th patch
and J, = f Eys, o(PAy - PAy-1 + maxx2 (gA,) K, K2) as the network after the j-th patch.
For any x in patch area Uis we can find j such that E A, but & Au for all k > j. After the first j patches a (pA, (I) + max421 (x. k) K1), oPA, (x) - PA,, (x) + max+22194, (z, 7)))), - K2), (PA, (z) PAy-, (z) + max (94. (I. 7)} K 1 the
DNN's output at x becomes fx(x) = f(x) + PA, (z) which meets our specification & at x by the definition of PA, (x).
Since x & As for k > j. then by Corollary 1, the rest of the patches would not change a correct area to an incorrect area. Therefore, we have the final patched neural network f meets specification on UI
Part 2:
To show that / satisfies & outside of A.
14

---

Published as a conference paper at ICLR 2022
For any a outside the patch area UıgigIA,, we have lies on correct linear region (linear region that satisfies the specification +). By Theorem 3, we have either f(x) ((x or f(x) E oout- Therefore, I satisfies outside of A.
Theorem 4 (Minimum Repair). For any ReLU DNN f. which is linear on patch region A and satisfies the specification 4, there exists a positive number I, such that for all y 2 I,
max xex
- f(x) 2 max h 7))-
(14)
=EX
Proof. We consider the general case where the linear patch function is obtained from Equation (3). For any DNN f. which is linear on patch region A and satisfies the specification 2, we have max, If fl 2 max cer + d = max ()) on patch area A by Equation (3). Therefore, only need to show:
max |h 7)1 max (h((-,)) 7)l
(15)
aęA
zEA
Since parameter 7 controls the slope of h,(,,,) 7) outside of patch area A, large y means that (.( 7) will drop to zero quickly outside A. Therefore, we can choose a large enough I' such that ha(,, 7) drops to zero faster than the change of linear patch function cr + d.
Therefore, have that for any 7 2 r.
max aeA
IhA 7)1 S max ( 7)1 -axx [ 7)1 ZEX
DEA
< max I/ - -11
max / zEX
(16)
zEA
Theorem (Polynomial- Time Efficiency). REASSURE terminates polynomial-tims in the size of
the neural network and the number of buggy linear regions when & takes the form of {y qi S
Py S )u where P is a full row rank matrix and oo [ ga(il S +o0 (gili) and qu [i] are the i-th elements of qu and qu respectively).
= {ar E X|a,2 S b,, I}. For the LPs in Equation (11), /Z| is the number of constraints and it is polynomial in the size of the neural network. Thus, REASSURE runs in polynomial time in the size of the neural network.
Proof. We consider the affine patch function solved via Equation (10). Suppose A=
In addition, since REASSURE computes the support network 94 and affine patch function PA for each A one by one (see Algorithm 1), the time complexity of REASSURE is linear in the number of buggy linear regions.
7.4 ADDITIONAL EXPERIMENT DETAILS
Details Feature-Space Repairs:
For an R-layer DNN f, we split f into two submodels fi and f2 according to hidden layer, say the jth hidden layer, where fi is the first j layers function, f2 is the last Rt - layers function and f == fo f1. We note the output space fi the feature space. And for any buggy imput T, we note (T) the buggy feature.
Repairing in a feature space is to repair the behavior f2 on buggy features Note this will automatically repair the behavior of on buggy points (T1,..., #1).
((LL))
Repairing in a feature space has the benefit of making the repair process more computation-fi friiendly and reducing the parameter overhead of the additional networks, and has the potential to generalize the repair to undetected buggy inputs with similar features. However, loses the locality guarantee in the input space (but still preserves locality in the feature space).
15

---

Published as a conference paper at ICLR 2022
REASSURE
MONN
#P
ND(
ND(La)
NoP(
NDP(L)
Acc
ND(
ND(L2)
NDP(L.))
NDP(L)
Acc
0.0%
0.0%
9.0%
9.1%
96.8%
8.9%
8.9%
7.1%
0.2%
87.5%
5 0.0%
0.0%
12.7%
12.8%
96.8%
48.1%
48.2%
44.3%
39.9%
57.1%
25 0.0%
0.0%
29.9%
29.7%
96.8%
90.4%
90.6%
63.7%
57.8%
6.7%
50 0.0%
0.0%
42.9%
42.6%
96.8%
92.5%
92.8%
82.1%
72.6%
4.8%
100
0.0%
0.0%
46.2%
45.9%
96.8%
95.5%
95.7%
90.9%
76.8%
5.1%
Table Watermark Removal. The test accuracy of the original DNN is 96.8%. #P: number of buggy points to repair; ND(Ls)). ND(L2): average (Loo. L2) norm difference on both training data and testing data; oe)( NDP(L2): average (Loo, L2) norm difference on random sampled points near watermark images; Acc: accuracy on test data.
Point-wise Repair ImageNet (Feature-Space Repairs)
We use AlexNet Krizhevsky et al. (2012) on ImageNet dataset Russakovsky et al. (2015) as the target DNN. The size of image is (224, 224, 3) and the total number of classes for ImageNet is 1000. We slightly modified AlexNet: we only consider 10 output classes that our buggy images may lie on and use multilayer perceptron with three hidden layers (512, 256, 256 nodes respectively) to mimic the last two layers of AlexNet.
The goal of the repair is fix the behaviors of the target DNN on buggy inputs, which are found on ImageNet-A Hendrycks et al. (2021). For REASSURE, we construct the patch network starting from the third from the last hidden layer (i.e. repair feature space).
The results are shown in Table 4. REASSURE, PRDNN and Fine- Thme-Tunig repair all the buggy points while Retrain only repair 96% buggy points in 100 epochs. REASSURE achieves almost zero modifi- cation on validation images to the original DNN. In addition, REASSURE, preserves the performance of the original DNN.
Watermark Removal
We compare REASSURE with MDNN on the watermark removal experiment from their paper. We were not able to run the code provided in the MDNN Github repository, but we were able to run on the target DNN models, watermark images, and MDNN-repaired models in the same repository.
The target DNN is from Goldberger et al. (2020), which is watermarked by the method proposed in Adi et al. (2018) on a set randomly chosen images x; with label fx;)).
The goal is to change the DNN's predictions on all watermarks to any other label y + fa;) while preserving the DNN's performance on the MNIST test data. For REASSURE, we set the prediction y f(x,) 1 if f(x,) 1, and y 10 otherwise.
The results are shown in Table 5. Both REASSURE and MDNN remove all the watermarks. How- MDNN introduces significant distortion to the target DNN and as result the test accuracy drops rapidly as the number of repair points increases. In comparison, REASSURE removes all the watermarks with no harm test accuracy.
Area Repair: HCAS
Table 6 is the comparison with PRDNN using the last layer the repair layer. All other settings the same as those in Section 5.2.
Experiment Platform
All experiments were run on an Intel Core i5 @ 3.4 GHz with 32 GB of memory. We use Gurobi Gurobi Optimization, LLC (2021) to solve the linear programs.
Size of Neural Networks:
Point-wise Repairs MNIST: The DNN model is multilayer perceptron with ReLU activation functions. has an input layer with 784 nodes, 2 hidden layers with 256 nodes in each layer, and a final output layer with 10 nodes.
Watermark Removal on MNIST: The DNN model has an input layer with 784 nodes, a single hidden layer with 150 nodes, and final output layer with 10 nodes.
16

---

Published as a conference paper at ICLR 2022
REASSURE
PRDNN (Last Layer)
#A
ND(L)))
NDP(L..)
NSE
Acc
T
(D(L.))
(DP(
NSE
Acc
T
10
2.662e-03%
1.318e-03%%
0%
98.1 %
1,0422
0.30%
20.5%
16%
71.4%
2,90+0.100 100
20
2.918e-03%
2.2%
0%
98.1
1.1856
0.31%
46.7%
66%
70.5%
5.81-0.169
50
8.289e-03%
17.6%
0%
98.1 %
1.8174
0.31%
46.7%
66%
70.5%
14.54+0.353
87
0.04%
45.9%
0%
97.8%
2.4571
0.31%
46.7%
66%
70.5%
25.30+0:467
Table 6: Area Repairs on HCAS. We use the the last hidden layer as the repair layer for PRDNN. The test accuracy of the original DNN is 97.9%. #A: number of buggy linear regions repair; ND(L,e): average Loo norm difference on training data: NDP( average Los norm difference on random sampled data on input constraints of Specification 1; NSE: % of correct linear regions that is repaired to incorrect; Ace: accuracy on training data (no testing data available); T: running time in seconds. For PRDNN, the first running time is for enumerating all the vertices of the polytopes and the second is for solving the LP problem in PRDNN.
Area Repair on HCAS: The DNN model has an input layer with nodes, 5 hidden layers with 25 nodes in each hidden layer, and final output layer with 5 nodes. DNN outputs of five possible control advisories ('wrong left', 'weak left', "Clearoof-Conflict,, 'weak right' and 'wrong right').
Point-wise Repairs on ImageNet: modified AlexNet Krizhevsky et al. (2012) has 650k neurons, consists of five convolutional layers, some of which are followed by max-pooling layers, and five fully-connected layers.
Hyperparameterss used in Repair:
We 7 0.5 for Point-wise Repair MNIST, 7 0.02 for Watermark Removal, 7 1 for Area Repair: HCAS and = 0.0005 for Point-wise Repair on ImageNet.
We set learning rate to 10-3 for Retrain in the point-wise repair experiment.
We set learning rate to 10-2 and momentum to 0.9 for Fine-Tuning in the point-wise repair experi- ment.
PRDNN requires specifying a layer for weight modification. We use the first hidden layer as the repair layer, which has the best performance in experiment settings, unless otherwise specified.
Specifications in HCAS:
Specification 1. If the intruder is near and approaching from the left, the network advises "strong
right."
Input constraints: Pin = {(x, y. 10 < x 5000, 10 S y < 5000, - S & S -1/2m). Output constraint: f(x, y. v 2 fIx y. ) for = 0, 2,
We calculate all the linear regions for N1.4 in the area i... of Specification 1 and totally 165 linear regions are found, including 87 buggy linear regions (DNN did not meet the specification) and 78 correct linear regions (DNN meet the specification).
Specification 2. If the intruder is near and approaching from the right. the network advises "strong left."
Input constraints: 4in = {z, y, 10 < 5000, 5500 - < -0,, S + S t). Output constraint: f(x, y. 1/) 2 fI, y. 3) for = 1,2,3,,44
Also calculate all the linear regions in the area o... of Specification 2. And 79 correct linear regions are found. We will test if repair will make those correct linear regions incorrect.
Point-wise Repairs vs. Area Repairs:
REASSURE automatically performs area repair on the point-wise repair experiments. This means area repair method scales well to high-dimensional polytopes (the input dimension of MNIST is 784) whereas PRDNN does not scale beyond 2D linear regions/polytopes.
Parameter Overhead for REASSURE:
REASSURE introduces an additional network, patch network, and as a result adds new parameters to the original network. The number of new parameters depends on |7], which is the number of linear
17

---

Published as a conference paper at ICLR 2022
constraints for the H-representation of A. We can remove redundant constraints in this representa- tion in polynomial time to make the additional network smaller. For the area repair experiment on HCAS, the average number of constraints for one linear region is 3.28 and the average number of new parameters that REASSURE introduces is 66. As comparison, the number of parameters in the original network is around 3000 and PRDNN doubles the number of parameters (as a result of the Decoupled DNN construction) regardless of the number of point-wise or area repairs.
7.5 APPLYING REASSURE To GENERAL CPWL NETWORKS
Recall the result that an T -+ R function representable by ReLU DNN if and only if continuous piecewise lincar (CPWL) function Arora et al. (2016). We convolutional neural networks as an example to show how REASSURE can be applied to more general CPWL networks. Convolutional neural networks (CNNs) neural networks with convolution layers and maxpooling layers. For simplicity, we assume the CNNs also use ReLU activation functions (but in general other CPWL activation functions will also work). The convolutional layers be viewed special linear layers. The maxpooling layers can be converted to linear operations with ReLU activation functions follows.
max( #2 ..... In) max wwx.mmaaa22..m.. 43, .... In)) max(F;, zÿ) = max(x; - 2j, 0) + 2, = o(x, - 2z) + Iz
where a is the ReLU activation function. Thus, REASSURE can be used repair CNNs as well.
18


Reviews:
[{"review_id": "vwfy7FCbnOC", "reviewer": "Reviewer_Bt2t", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a very well written paper which was a pleasure to read.  The paper\ndraws a clear picture of the state-of-the-art in neural network repair which is\nused to  adequately motivate the present contribution. In particular, I think\nthat the potential side effects that the current state-of-the-art may have\nwhilst repairing a network, such as introducing a new bug in a previously\nnon-buggy input, is an important limiting factor of the practical significance\nof  neural network repair. It is nice to see an approach towards overcoming\nthis shortcoming.  I think that the claimed advantages of the approach over\nrelated work are adequately evaluated on an MNIST network and a variant of the\nACAS networks. The scalability of the method is also discussed and additional\nexperiments on AlexNet are provided. A minor concern that I have regarding the\nevaluation is the following.\n\nI think it would be impractical to remove all buggy behaviour (outside of a\ntest set) from image classifiers. In light of this a metric that is potentially\nmore important than the ones measured in the experiments is  the robustness of\nclassifiers w.r.t to input transformations such as noise perturbations. Data\naugmentation schemes often aim at improving  precisely this, thus I think that\ndata augmentation and the present method should be compared on this. So,\nalthough the MNIST dataset was successfully used to showcase the advantages of\nREASSURE over related methods, the inclusion of experimental results on\nrobustness would in my view strengthen the evaluation of the approach.\n \nSome minor comments:\n\n- Page 1-2. loss defined based on -> loss defined on\n\n- Page 3. linear functions -> affine functions.\n\n- Page 6. can solve it is -> can solve it.\n\n- Page 6. with every entry is equal -> where every entry is equal.\n\n- Page 7. REASSURE provide -> REASSURE provides.\n\n- Shouldn't the distance the Theorem 4 be bounded from above?\n", "summary_of_the_paper": "The paper develops a method for repairing neural networks with ReLU activation\nfunctions. The method works by augmenting a given network with a patch function that\ncorrects the output of the network on a given buggy input. This enables the\nmethod to be the only one among related work that is not only sound and\ncomplete but also guarantees (i) minimal distances between  the functions\nimplemented by the original and repaired networks; (ii) unaltered behaviour of\nthe repaired network for inputs different than the buggy one.\n", "summary_of_the_review": "The paper alleviates some significant limitations in neural network repair in a\nmethod that is adequately evaluated, thereby making for a solid ICLR\ncontribution.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "s-RfWMyeuM2", "reviewer": "Reviewer_Jhi1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The presented techniques are quite interesting and are novel to my knowledge. The presentation of the technique is also clear. I like the running example in section 3. I do have some concerns and questions.\n1. Point-wise repair.\nTo me, the main motivation of point-wise repair is to improve the overall performance (e.g., accuracy) of the network instead of simply making the network perform correctly on a small set of input points. If our goal were the latter, then instead of using the proposed techniques, we could just put the network in a big if-statement which returns the desired output on those points. In other words, in the point-wise repair scenario, we do hope the repair to have side effects, for instance, increase of test accuracy beyond those repaired test images (are the buggy points images in the test set?). It would be beneficial to demonstrate whether this is the case, as right now it looks like the increase in test accuracy results only from fixing the buggy points (with the neural network outputs minimally unchanged).\n2. Affine-region repair.\nPartitioning the input space into regions where the network is affine and fixing each of those regions sounds feasible for small networks like HCAS. However, it seems challenging to partition the input region into affine sub-regions for large networks or high-dimensional inputs. I do think it is important to show in the main paper 1) the application of the techniques on more complex models; 2) area repairs (for robustness properties for instance) on perception networks. \nFor HCAS, how are the linear regions represented, boxes?\n3. Can the authors comment on the (initial) architectures of the evaluated networks?\n\nOverall, while I think the idea is interesting, more work needs to be done to show the benefit beyond minimal change for point-wise repair and to address the scalability issues.", "summary_of_the_paper": "This paper presents a new methodology for repairing ReLU neural networks. Concretely, for a single affine region, a patch function is synthesized from an affine function that performs the repair and a support network to make sure the repair only applies to the affine region. Multiple affine regions can be fixed iteratively. The techniques are evaluated on the MNIST and HCAS benchmarks.", "summary_of_the_review": "Interesting ideas for neural network repair but there are concerns regarding motivation and scalability.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "lv_JnqMdTLb", "reviewer": "Reviewer_fkMv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1. The paper tackles a very relevant but relatively unexplored problem. While there is substantial literature on proving robustness of neural networks, there is only limited work on providing algorithms for provable repair which is as important when considering the deployment of neural networks in the real world. I enjoyed reading the paper, it is well-written. I appreciate that the authors provide intuitive examples to explain the meanings of the different symbols and equations in their algorithmic construction.\n\n2. The technical contributions are novel and solid. \n\n3. The authors provide theoretical results which shows that their algorithms provide stronger guarantees than the state-of-the-art for provable neural network repair.\n\n4. The evaluation is performed on similar benchmarks as prior work and shows significant improvement on obtaining provable repair while minimizing changes to the network.\n\nCons:\n1. The claim about preserving the continuity property needs to be toned down.  The first row in Table 1 says that the proposed repair preserves the continuity property however, the text in Section 3.2 mentions that this is not the case.\n\n2. Scalability to area repairs defined over higher-dimensional polytopes is limited but that is also a limitation of all existing work.\n\n\nI have a few other comments/questions:\n\n1. The notation in eq. (3) that (c,d) \\in {(c,d)...} is weird.\n\n2. For multi-area repair, does different ordering of patch areas yield different repaired networks?.\n\n3. What is the running time for all the tools in Table 2?  Does the timing in Table 3 also include the time to generate vertices?\n\n4. Is it possible to obtain results on a CIFAR10 network in the same setting as the MNIST network or it would be too expensive?\n\n5. What is the value of \\gamma used in the experiments? It would be good to show the different metrics vary as a function of /gamma?\n\n6. Similar to DDNN, is extension to arbitrary activations possible for pointwise repair?", "summary_of_the_paper": "The paper presents a new method for the provable repair of neural networks. Both point-wise and polytope-based repairs are considered. The main idea is to synthesize a patch network and combine it with the buggy network. The patch network consists of two subcomponents: a support network that is only activated for the inputs in the linear region containing buggy inputs and an affine patch network that repairs the network in the buggy region. The experimental evaluation is performed on similar datasets and networks as prior work and shows the effectiveness of the new methodology.", "summary_of_the_review": "The paper presents a complete and sound methodology for the provable repair of neural networks while minimizing the side effects of the repair. The ideas presented in the paper are new, come with solid theoretical guarantees and advance the state-of-the-art. Based on the contributions, I would recommend acceptance of this work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Eg6r8Xnl5bG", "reviewer": "Reviewer_DRaE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths:\n1) This paper aims to address an important problem.\n2) This paper is well-written and easy to follow.\n3) The approach has some novelty.\n\n# Weakness:\n1) This paper only focuses on CPWL neural networks, which limit its usefulness.\n2) Point-wise repair is a more practical scenario. In real world applications, there are usually a set of buggy inputs such as the misclassified images, texts or audio. Most of existing repair techniques aim to focus on this problem (e.g., retraining). However, this paper requires the linear area for repairing, which is not always provided. Although it provides a way to transform one input point to the linear region in 2.5, there are still some concerns: a) how to guarantee the correctness of the transformed linear regions, the linear region is an over-approximation of the input x?  b) if there are too many failed inputs, then many linear regions will be generated, which may cause the scalability issues. The usage of LP solving may also introduce the scalability issues.  c) In Eq.1, what do you mean $z_j^i <0$? Is it the neuron output of one input $x$?\n3) Some description is over-claimed. For example, in Section 1, this paper claimed that, for existing approaches, ''there is no guarantee that the given buggy inputs are fixed and no new bugs are introduced, the Generalization in Section 2.6. It seems that the approach can also not guarantee that no new bugs are introduced  and the claimed generalization, especially for the point-wise repair. Consider the comments (2) above, how to guarantee them? Any support for this claim \"the optimization-based approach cannot guarantee removal of the buggy behaviors, and the verification-based approach does not scale beyond networks of a few hundred neurons.\"?\n4) Ensuring the locality is important, but why  Minimality is required? It seems that if we can fix the errors and do not affect the correct inputs, it should be okay. Why Minimality is so important?\n5) In Section 3.2, you suppose the linear region is $\\{x| a_ix\\le b_i, i \\in I\\}$, is it general for all linear regions?\n6) The evaluation is weak. It only compares the proposed method with the existing methods on MNIST for point-wise repair, which may confirm the scalability concerns? Although there are some results on AlexNet, the results are not complete and systematic. For Section 5.1, more discussions are required. For example,  how many failed inputs are fixed by each method? The performance is also not included. How many linear regions are used in different configurations? How is the generalization, i.e., can the repair fix unseen buggy inputs? \n\n\n", "summary_of_the_paper": "This paper proposed an approach for repairing neural networks that use ReLU activation functions. Different with existing techniques that retrain the model or change the weights, the proposed approach generates a patch in the original model, i.e., add sub-models. The LP solver is used to solve the patch function for a linear region. The experimental  results demonstrated that the approach could outperform existing methods. ", "summary_of_the_review": "Overall, this paper is well-written and interesting. However, considering the limited application, the little discussion on the point-wise repair and the weak experiments, I think the paper should be still improved before it is accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers were almost unanimous in favor of this paper, with scores of 5,8,6,8.
I think it's a neat idea and am inclined to accept despite some issues w/ motivation / scalability. 
Science proceeds in increments, and it's OK to propose something with scalability issues that someone else later tries to fix, etc.
Decision: Accept (Poster)