# 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 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.

1 INTRODUCTION

Deep neural networks (DNNs) have demonstrated impressive performances on a 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, it is important to correct erroneous outputs of a DNN as they are discovered after training.
For instance, a neural network in charge of giving control advisories to the pilots in an 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 a 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 to 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 a small way. Existing works on neural network repair roughly fall into three categories.

1. Retraining/fine-tuning. 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 et al. (2018). One major weakness of these approaches is the lack of
formal guarantees – at the end of retraining/fine-tuning, there is no guarantee that the given buggy
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. Fine-tuning, on the other hand, often
faces the issue of catastrophic forgetting Kirkpatrick et al. (2017).

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


-----

𝑥 𝑥 𝑥

Retraining or direct Decoupled DNN **Our approach**

weight modification


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 a 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 et al. (2021)
first locates potentially faulty weights in a layer and then uses constraint solving to find a weights
modification that can fix the failures. In general, 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. 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.

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 network 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 is that the induced changes, as a result of either retraining or direct weight modification,
are global. This means that a 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 a new buggy input can
end up invalidating the repair on a 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, a 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 input 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 is guaranteed to fix the buggy input, and a patch is guaranteed
to be found for any buggy input. Moreover, our approach preserves the CPWL 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 1 provides an illustrative
comparison of our approach with other methods. Table 1 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 theoretical guarantees.

2. Our technique synthesizes a 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 or direct weight manipulation.

3. Across a set of benchmarks, REASSURE can efficiently correct a set of buggy inputs or buggy
areas with little or no change to the accuracy and overall functionality of the network.


-----

REASSURE Retrain MDNN Editable Fine-Tuning PRDNN

Preservation of CPWL Yes Yes Yes Yes No
Soundness Yes No Yes No Yes
Completeness Yes No No No No
Area Repair Yes No No No Yes
Minimal Change Yes (Function Space) No Yes (Weight Space) No Yes (Weight Space)
Localized Change Yes No No No No
Limited Side Effect Yes No No No No

Table 1: Comparing REASSURE 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-based approach from Goldberger et al. (2020). PRDNN
is the Decoupled DNN approach from Sotoudeh & Thakur (2021). REASSURE is the only method
that can provide all the guarantees.

2 BACKGROUND

2.1 DEEP NEURAL NETWORKS

An R-layer feed-forward DNN f = κR _σ_ _κR_ 1 _..._ _σ_ _κ1 : X_ _Y is a composition of_
linear functions κr, r = 1, 2, ..., R and activation function ◦ _◦_ _−_ _◦_ _◦ σ, where ◦_ _X ⊆ →R[m]_ is a bounded input
domain and Y ⊆ R[n] is the output domain. Weights and biases of linear function {κr}r=1,2,...,R are
parameters of the DNN.

We call the first R − 1 layers hidden layers and the R-th layer the output layer. We use zj[i] [to denote]
the i-th neuron (before activation) in the j-th hidden layer.

In this paper, we focus on ReLU DNNs, i.e. DNNs that use only the ReLU activation functions.
It is known that an R[m] _→_ R function is representable by a ReLU DNN if and only if it is a
continuous piecewise linear (CPWL) function Arora et al. (2016). The ReLU function is defined as
_σ(x) = max(x, 0). We say that σ(x) is activated if σ(x) = x._

2.2 LINEAR REGIONS

A linear region A is the set of inputs that correspond to the same activation pattern in a ReLU DNN
_f Serra et al. (2017). Geometrically, this corresponds to a convex polytope, which is an intersection_
of half spaces, in the input space X on which f is linear. We use f to denote the part of f on .
_|A_ _A_

2.3 CORRECTNESS SPECIFICATION

A correctness specification Φ = (Φin, Φout) is a tuple of two polytopes, where Φin is the union
of some linear regions and Φout is a convex polytope. A DNN f is said to meet a specification
Φ = (Φin, Φout), denoted as f = Φ, if and only if _x_ Φin, f (x) Φout.
_|_ _∀_ _∈_ _∈_

**Example 1. For a classification problem, we can formally write the specification that “the pre-**
_diction of any point in an area A is class k” as Φ = (Φin, Φout), where Φin = A and_
Φout = {y ∈ R[n] _| yk ≥_ _yi, ∀i ̸= k}[1]._

2.4 PROBLEM DEFINITION

In this paper, we consider the following two repair problems.

**Definition 1 (Area repair). Given a correctness specification Φ = (Φin, Φout) and a ReLU DNN**
_f ̸|= Φ, the area repair problem is to find a modified ReLU DNN_ _f such that_ _f |= Φ._

Note that we do not require _f to have the same structure or parameters as[b]_ _f[b] in this definition. If_
Φin contains a single (buggy) linear region, we refer to this as single-region repair. If Φin contains
multiple (buggy) linear regions, we refer to it as multi-region repair.

[b]

1Note that here y is the output of the layer right before the softmax layer in a classification network.


-----

**Definition 2 (Point-wise repair). Given a set of buggy inputs {x1, . . .,** _xL} ⊂_ Φin with their corre_sponding correct outputs_ _y1, . . ., yL_ _and a ReLU DNN f_ _, the point-wise repair problem is to find_
_{_ _}_
_a modified ReLU DNN_ _f such that_ _i,_ _f_ (xi) = yi. e e
_∀_

We call the minimal variants of area repair and point-wise repair minimal area repair and minimal

[b] [b] e

_point-wise repair respectively. Minimality here is defined with respect to the maximum distance_
between f and _f over the whole input domain X. A point-wise repair can be generalized to an area_
repair through the following result.

[b]

2.5 FROM BUGGY INPUTS TO BUGGY LINEAR REGIONS

The linear region where an input x resides can be computed as follows.
**Lemma 1. Lee et al. (2019) Consider a ReLU DNN f and an input x ∈** _X. For every neuron zj[i][, it]_
_induces a feasible set_

_x¯_ _X_ (▽xzj[i][)][T][ ¯]x + zj[i] _j[)][T][ x][ ≥]_ [0][}] _if zj[i]_
_j[(][x][) =]_ _{_ _∈_ _|_ _[−]_ [(][▽][x][z][i] _[≥]_ [0] (1)
_A[i]_ _x¯_ _X_ (▽xzj[i][)][T][ ¯]x + zj[i] _j[)][T][ x][ ≤]_ [0][}] _if zj[i]_ _[<][ 0]_
{ _∈_ _|_ _[−]_ [(][▽][x][z][i]

_The set A(x) = ∩i,jAj[i]_ [(][x][)][ 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.

**1. 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: A sound repair should completely_
remove the known buggy behaviors, i.e. it is a solution to the point-wise repair problem defined
in Definition 2. 3. Completeness: Ideally, the algorithm should always be able find a repair for

[b]
any given buggy input if it exists. 4. Generalization: If there exists another buggy input _x[′]_ in
the neighborhood of _x (e.g. the same linear region), then the repair should also fix it. For example,_
suppose we have an _x that violates a specification which requires the output to be within some range._
e
It is almost guaranteed that there exists another (and infinitely many) _x[′]_ in the same linear region
e
that also violates the specification. 5. Locality: We argue that a good repair should only induce a
e
localized change to f in the function space. For example, in the context of ReLU DNN, if a linear
e
region does not border the repair region, i.e. =, then _f_ (x) = f (x). 6. Minimality:
_B_ _A_ _B∩A_ _∅_ _|B_ _|B_
Some notion of distance between f and _f such as max |f −f[b]| should be minimized. Note that this is_
a significant departure from existing methods that focus on minimizing the change in weights which[b]
has no guarantee on the amount of change in the function space. 7. Limited side effect: Repairing

[b]
a buggy point should not adversely affect points that were originally correct. For example, repairing
a buggy input _x in region A should not change another region from correct to incorrect. Formally,_
for any linear region who is a neighbor of, i.e. =, if f = Φ, then _f_ = Φ. 8.
**Efficiency: The repair algorithm should terminate in polynomial time with respect to the size of the e** _C_ _A_ _C ∩A ̸_ _∅_ _|C |_ _|C |_
neural network and the number of buggy inputs.

[b]

3 OUR APPROACH

We will first describe our approach to single-region repair and then present our approach to multi_region repair which builds on results obtained from the single-region case._

Given a linear region, our overarching approach is to synthesize a patch network h such that
_A_ _A_
_f = f + h_ and _f_ = Φ. The patch network h is a combination of two sub-networks: a support
_A_ _|_ _A_
network g, which behaves like a characteristic function, to determine whether an input is in, and
_A_ _A_
an affine patch function networkb [b] _pA(x) = cx + d to ensure (f + pA) |= Φ on A._

3.1 RUNNING EXAMPLE

We use the following example to illustrate our idea.


-----

𝑔!

𝑥! 1 𝑧! 1 𝑥! 𝑝! Support Network 𝑔!

2 𝑦 ℎ%

2 𝑧! 𝑦

𝑥" 1 𝑥"

−1 𝑧"

𝑧"


Figure 2: Left: the target DNN with buggy inputs. Right: the REASSURE-repaired DNN with the
patch network shown in red. Support network g is for approximating the characteristic function
_A_
on ; Affine patch function p ensures the satisfaction of Φ on ; The design of the patch network
_A_ _A_ _A_
_h_ ensures locality for the final patch.
_A_

**Example 2. Consider repairing the ReLU DNN f in Figure 2 according to the correctness specifi-**
_cation Φ :_ _x_ [0, 1][2], y [0, 2]. The DNN consists of a single hidden layer with two neurons z1
_∀_ _∈_ _∈_
_and z2, where y = σ(z1) + σ(z2), z1 = x1 + 2x2 −_ 1 and z2 = 2x1 − _x2._

The only linear region that violates our specification is0, 2x1 _x2_ 0 . ( _x = (0.9, 0.9)_ [0, 1][2] but f (x) = 2 A. =6 / {x[0 |, 1 2] ≥) _x1, 1 ≥_ _x2, x1 + 2x2 −_ 1 ≥
_−_ _≥_ _}_ _∈_ _∈_

The network f (x) on the linear region is the affine function f (x) = 3x1 + x2 1. Our
algorithm first sets up an affine function e _A p_ (x) that minimally repairse _|A_ _f on_, such that − _x_
_A_ _A_ _∀_ _∈_
_, f_ (x) + p (x) [0, 2]. Later in the paper, we will show p (x) can be found by solving a LP
_A_ _A_ _∈_ _A_
problem. The resulting patch function is pA(x) = − 2[1] _[x][1][ −]_ [1]2 _[x][2][.]_

However, directly apply f (x) + p (x) as the patch network will have side effects on areas outside
_A_
of . Our strategy is to combine p (x) with a support network g (x) which outputs 1 on and
_A_ _A_ _A_ _A_
drops to 0 quickly outside of . The final repaired network is f (x) + σ(p (x) + g (x, 10)
_A_ _A_ _A_ _−_
1) _σ(_ _p_ (x) + g (x, 10) 1). This structure makes p almost only active on and achieve a
_−_ _−_ _A_ _A_ _−_ _A_ _A_
localized repair. Observe that this is still a ReLU DNN.

3.2 SUPPORT NETWORKS

Support networks are neural networks with a special structure that can approximate the characteristic
function of a convex polytope. They are keys to ensuring localized repairs in our algorithm.

Assume that the linear region we need to repair is = _x_ _aix_ _bi, i_ _I_, where _I_ is the number
_A_ _{_ _|_ _≤_ _∈_ _}_ _|_ _|_
of linear inequalities. The support network of A is defined as:


_g(bi_ _aix, γ)_ _I_ + 1) (2)

Xi∈I _−_ _−|_ _|_


_g_ (x, γ) = σ(
_A_


where g(x, γ) = σ(γx + 1) − _σ(γx) and γ ∈_ R is a parameter of our algorithm that controls how
quickly g (x, γ) goes to zero outside of .
_A_ _A_

**Remark: For any x**, we have g (x, γ) = 1, i.e. the support network is fully activated. For any
_∈A_ _A_
_x /∈A, if for one of i ∈_ _I, we have aix −_ _bi ≤−1/γ, then gA(x, γ) = 0._

Observe that g (x, γ) is not zero when x is very close to due to the requirement for preserving
_A_ _A_
CPWL. In Theorem 3, we prove that we can still guarantee limited side effects on the whole input
domain outside of A with this construction.

3.3 AFFINE PATCH FUNCTIONS

We consider an affine patch function p (x) = cx+d, where matrix c and vector d are undetermined
_A_
coefficients. In a later section, the design of patch network will ensure that on the patch area A, the
repaired network is f (x) + p (x). We will first consider finding appropriate c and d such that
_A_
_f_ (x) + p (x) satisfy the specification on .
_A_ _A_


-----

To satisfy the specification Φ, we need f (x) + p (x) Φout for all x . To obtain a minimal
_A_ _∈_ _∈A_
repair, we minimize maxx∈A |pA(x)|. Thus, we can formulate the following optimization problem
minc,d maxx _p_ (x) = **_cx + d_**
_∈A |_ _A_ _|_ _|_ _|_ (3)
(c, d) (c, d) _f_ (x) + cx + d Φout, _x_
 _∈{_ _|_ _∈_ _∀_ _∈A}_

Notice that this is not an LP since both c and x are variables and we have a cx term in the objective.

In general, one can solve it by enumerating all the vertices of . Suppose that _vs_ _s = 1, 2, ..., S_
_A_ _{_ _|_ _}_
is the set of vertices of A. Since Φout is a convex polytope, we have

_f_ (x) + p (x) Φout for all x _f_ (vs) + p (vs) Φout for s = 1, 2, ..., S. (4)
_A_ _∈_ _∈A ⇔_ _A_ _∈_

and

maxx **_cx + d_** = maxs=1,2,...,S _cvs + d_ (5)
_∈A |_ _|_ _|_ _|_

Hence, we can solve the following equivalent LP.


minc,d H
_H ≥_ (cvs + d)i, H ≥−(cvs + d)i, for s = 1, 2, ..., S and i = 1, 2, ..., m
_f_ (vs) + pA(vs) ∈ Φout, for s = 1, 2, ..., S


(6)


where H ∈ R and will take maxs=1,2,...,S |cvs + d| when optimal.

In general, the number of vertices of a convex polytope can be exponential in the size of its Hrepresentation 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 vertex enumeration for many useful cases such as
the classification problem in Example 1 and make our algorithm much more efficient.

3.4 SINGLE-REGION REPAIRS

With a support network g and an affine patch function p, we can synthesize the final patch
_A_ _A_
network as follows:

_h_ (x, γ) = σ(p (x) + K _g_ (x, γ) _K)_ _σ(_ _p_ (x) + K _g_ (x, γ) _K)_ (7)
_A_ _A_ _·_ _A_ _−_ _−_ _−_ _A_ _·_ _A_ _−_

where K is a vector where every entry is equal to the upper bound of {|pA(x)|+∞|x ∈ _X}._

**Remark: For x**, g (x, γ) = 1, then we have h (x, γ) = σ(p (x)) _σ(_ _p_ (x)) = p (x).
_∈A_ _A_ _A_ _A_ _−_ _−_ _A_ _A_
For x /, g (x, γ) goes to zero quickly if γ is large. When g (x, γ) = 0, we have h (x, γ) =
_∈A_ _A_ _A_ _A_
_σ(p_ (x) _K)_ _σ(_ _p_ (x) _K) = 0._
_A_ _−_ _−_ _−_ _A_ _−_

The repaired network _f_ (x) = f (x) + h (x, γ). Since f and h are both ReLU DNNs, we have _f_
_A_ _A_
is also a ReLU DNN. We will give the formal guarantees on correctness in Theorem 1.

[b] [b]

3.5 MULTI-REGION REPAIRS

Suppose there are two linear regions, A1 and A2, that need to be repaired, and we have generated
the affine patch function p 1 (x) for 1 and p 2 (x) for 2.
_A_ _A_ _A_ _A_

If 1 2 =, then we can repair f (x) with _f_ (x) = f (x) + h 1 (x, γ) + h 2 (x, γ) directly, since
_hA A1_ (x, γ ∩A) and ∅ hA2 (x, γ) will not be nonzero at the same time whenA _γ is large enough.A_

ofHowever, if f on x, which will invalidate both repairs and cannot guarantee that the repaired DNN will meet A1 ∩A2 ̸= ∅, for any x ∈A1 ∩A[b]2, both hA1 (x, γ) and hA2 (x, γ) will alter the value
the specification Φ. To avoid such over-repairs, our strategy is to first repair 1 2 with p 1 (x),
and then repair 2 with p 2 (x) _p_ 1 (x). Figure 3 provides an illustration of a three-region case. A _∪A_ _A_
_A_ _A_ _−_ _A_

In general, for multi-region repair, we note {Al}l=1,2,...,L are all the buggy linear regions. Then we
compute the support network gAl (x, γ) and affine patch function pAl (x) for each Al. Note that this
computation can be done in parallel.


-----

_A3 : f + pA3_


_A3 : f + pA1_


_A3 : f + pA1_


_A3 : f + pA2_


_A3 : f_

_A2 : f_

_A1 : f_


: f + pA1

1 : f + pA1


: f + pA2

1 : f + pA1


: f + pA2

1 : f + pA1


Figure 3: An illustration of multi-region repair with three different repair regions. Left: the original
DNN; Middle Left: repair 1 2 3 with p 1 ; Middle Right: repair 2 3 with p 2 _p_ 1 ;
Right: repair 3 with p 3 A _p ∪A2_ _∪A_ _A_ _A_ _∪A_ _A_ _−_ _A_
_A_ _A_ _−_ _A_

Once we have gAl (x, γ) and pAl (x), we can “stitch” multiple local patches into a final patch as
follows.

_h(x, γ) =_ [σ(pAl (x) − _pAl−1_ (x) + maxj _l_

_l_ _≥_ _[{][g][A][j]_ [(][x, γ][)][}][K][l][ −] _[K][l][)]_

X

_−σ(−pAl_ (x) + pAl−1 (x) + maxj _l_ (8)
_≥_ _[{][g][A][j]_ [(][x, γ][)][}][K][l][ −] _[K][l][)]]_

where Kl is the upper bound of {|pAl (x) − _pAl−1_ (x)|∞|x ∈ _X} and pA0_ (x) = 0.

**Remark: maxj** _l_ _g_ _j_ (x, γ) is a support function for _j_ _l_ _j and its value is 1 for any x_
_≥_ _{_ _A_ _}_ _∪_ _≥_ _A_ _∈_
_∪j≥lAj._

4 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 1 (Soundness). The repaired DNN** _f returned by REASSURE is guaranteed to satisfy the_
_specification Φ._
**Theorem 2 (Completeness). REASSURE can always find a solution to the minimal point-wise repair[b]**
_or the minimal area repair problem._

For any A, the support network ensures that the patch network goes to zero quickly when x is away
from A. However, it still makes a small change on the neighbors of A. The following theorem
shows that for a big enough γ, the patch network would not change a correct region into incorrect.
**Theorem 3 (Limited Side Effect). Given a correctness property Φ = (Φin, Φout), a patch region**
_A and the corresponding patch network h(x, γ), there exists a positive number Γ such that for any_
_γ ≥_ Γ, we have

_1. for any linear region B, if B ∩A = ∅, then_ _f_ (x, γ) = f (x);

_2. for any linear region_ _who is a neighbor of_ _(_ = _), if f_ = Φ, then _f_ (x, γ) = Φ.
_C_ _A[b]_ _C∩A ̸_ _∅_ _|C |_ _C_ _|_

**Corollary 1 (Incremental Repair). For multiple-region repair, the patch for a new region A[′]** _would_
_not cause a previous patched region_ _to become incorrect._ [b]
_A_

**Theorem 4 (Minimum Repair). For any ReLU DNN** _f[˜], which is linear on a patch region A and_
_satisfies the specification Φ, there exists a positive number Γ, such that for all γ ≥_ Γ,

max _f_ (x) _f_ (x) max (9)
_x_ _X_ _−_ _| ≥_ _x_ _X_
_∈_ _[|][ ˜]_ _∈_ _[|][h][A][(][x, γ][)][|][.]_

**Theorem 5 (Polynomial-Time Efficiency). REASSURE terminates in polynomial-time in the size of**
_Pythe neural network and the number of buggy linear regions whenqu_ _where P is a full row rank matrix and_ _ql[i]_ _qu Φ[i]out takes the form of+_ _(ql[i] and qu {[i]y are the | ql ≤_
_≤_ _}_ _−∞≤_ _≤_ _≤_ _∞_
_i-th elements of ql and qu respectively)._

5 EXPERIMENTS

In this Section, we compare REASSURE with state-of-the-art methods on both point-wise repairs
and area repairs. The experiments were designed to answer the following questions: (Effectiveness)


-----

REASSURE Retrain (Requires Training Data)

#P ND(L∞) ND(L2) NDP(L∞) NDP(L2) Acc ND(L∞) ND(L2) NDP(L∞) NDP(L2) Acc

10 **0.01%** **0.01%** **25.75%** **24.78%** **98.1%** 1.13% 1.09% 77.86% 77.60% **98.1%**
20 **0.03%** **0.02%** **19.17%** **18.70%** 98.2% 0.92% 0.89% 77.14% 76.29% **98.4%**
50 **0.06%** **0.06%** **24.64%** **23.79%** 98.5% 0.84% 0.82% 84.17% 82.15% **98.7%**
100 **0.11%** **0.12%** **25.40%** **24.44%** **99.0%** 0.84% 0.82% 84.83% 83.05% **99.0%**


Fine-Tuning PRDNN

#P ND(L∞) ND(L2) NDP(L∞) NDP(L2) Acc ND(L∞) ND(L2) NDP(L∞) NDP(L2) Acc

10 2.20% 2.11% 67.61% 65.52% 97.6% 1.41% 1.34% 34.60% 33.59% 97.8%
20 23.19% 22.35% 82.87% 78.55% 78.6% 2.88% 2.74% 43.63% 41.78% 97.1%
50 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∞), NDP(L2):
average (L∞, L2) 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 a repair in removing known buggy behaviors? (Locality) How much side effect (i.e.
modification outside the patch area in the function space) does a repair produce? (Function Change)
How much does a repair change the original neural network in the function space? (Performance)
Whether and how much does a repair adversely affect the overall performance of the neural network?

We consider the following evaluation criteria: 1. Efficacy (E): % of given buggy points or
buggy linear regions that are repaired. 2. Norm Difference (ND): average normalized norm
(L∞ 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 to measure how a repair change the
original neural network on function space. 3. Norm Difference on Patch Area (NDP): average
normalized norm (L∞ or L2) 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 (Acc): 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 Effect (NSE): NSE is only for area repair. It is the percentage
of correct linear regions (outside of patch area) that become incorrect after a repair. If a repair has a
nonzero NSE, the new repair may invalidate a previous repair and lead to a circular repair problem.

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 a repair
is to fix the behaviors of the target DNN on buggy inputs that are found in the test dataset. Thus, the
repaired DNN is expected to produce correct predictions for all the buggy inputs.

The results are shown in Table 2. REASSURE achieves almost zero 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 no 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 Sotoudeh & Thakur (2021) on an
experiment where the setting is 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 pycddlib 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.


-----

REASSURE PRDNN

#A ND(L ) NDP(L ) NSE Acc T ND(L ) NDP(L ) NSE Acc T
_∞_ _∞_ _∞_ _∞_

10 **0.00%** **0.0%** **0%** **98.1%** **1.0422** 0.10% 31.6% 4% 89.6% 2.90+0.100
20 **0.00%** **2.2%** **0%** **98.1%** **1.1856** 0.15% 37.2% 8% 83.1% 5.81+0.185
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 on PRDNN using the last layer (which are inferior to using the first layer) are 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 to repair. ND(L ): average L norm difference on training data. NDP(L ): average
_∞_ _∞_ _∞_
_L_ norm difference on random sampled data on input constraints of specification 1. NSE: % of
_∞_
correct linear regions changed to incorrect by the repair. Acc: 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.

REASSURE (feature space) Retrain (Requires Training Data) Fine-Tuning PRDNN

#P ND(L∞) ND(L2) Acc ND(L∞) ND(L2) Acc ND(L∞) ND(L2) Acc ND(L∞) ND(L2) 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%
20 **0.12%** **0.11%** 81.3% 42.78% 35.69% **82.9%** 69.16% 57.47% 68.5% 21.91% 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(L ),
_∞_
ND(L2): average (L∞, L2) norm difference on validation data. Acc: accuracy on 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)[2] _N1,4 (previous advisory equal to 1 and time to 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 et al. (2017). We compute all the linear regions for N1,4 in the area Φin 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 in Appendix 7.4), the dual of
Specification 1, to test the negative side effect (NSE) of a repair.

The results are shown in Table 3. 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 FEATURE-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 a challenge to 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 a principled manner, i.e. constructing a patch
network starting from an intermediate layer. This approach still preserves soundness and completeness, 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 Russakovsky et al. (2015) in Appendix 7.4 show REASSURE (feature space) is still significantly better
in term of locality(ND) and minimality (NDP).

6 CONCLUSION

We have presented a 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 γ.

2The 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 5D so we use HCAS in order to run their
tool in our evaluation of area repairs.


-----

ACKNOWLEDGEMENT

This effort was partially supported by the Intelligence Advanced Research Projects Agency (IARPA)
under the contract W911NF20C0038. The content of this paper does not 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 weakness 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://arxiv.](http://arxiv.org/abs/1611.01491)
[org/abs/1611.01491. 3, 18](http://arxiv.org/abs/1611.01491)

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. 1

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 networks correctly. arXiv preprint arXiv:2012.01872, 2020. 2

Tommaso Dreossi, Shromona Ghosh, Xiangyu Yue, Kurt Keutzer, Alberto SangiovanniVincentelli, and Sanjit A Seshia. Counterexample-guided data augmentation. arXiv preprint
_arXiv:1805.06962, 2018. 1_

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.](https://www.gurobi.com)
[gurobi.com. 16](https://www.gurobi.com)

Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern
_Recognition, pp. 15262–15271, 2021. 16_

Martin Henk, J¨urgen Richter-Gebert, and G¨unter M. Ziegler. Basic properties of convex polytopes.
In HANDBOOK OF DISCRETE AND COMPUTATIONAL GEOMETRY, CHAPTER 13, pp. 243–
270. CRC Press, Boca, 1997. 6

Kyle D Julian and Mykel J Kochenderfer. Guaranteeing safety for neural network-based aircraft collision avoidance systems. In 2019 IEEE/AIAA 38th Digital Avionics Systems Conference (DASC),
pp. 1–10. IEEE, 2019. 9

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. 1

Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An
efficient smt solver for verifying deep neural networks. In International Conference on Computer
_Aided Verification, pp. 97–117. Springer, 2017. 9_

James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A.
Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, 114(13):3521–3526,
[2017. ISSN 0027-8424. doi: 10.1073/pnas.1611835114. URL https://www.pnas.org/](https://www.pnas.org/content/114/13/3521)
[content/114/13/3521. 1](https://www.pnas.org/content/114/13/3521)


-----

Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional 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.

8

Guang-He Lee, David Alvarez-Melis, and Tommi S Jaakkola. Towards robust, locally linear deep
networks. arXiv preprint arXiv:1907.03207, 2019. 4

Shiqing Ma, Yingqi Liu, Wen-Chuan Lee, 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 on the Foundations of Software Engineering, pp. 175–186, 2018. 1_

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. 1_

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–252, 2015. doi: 10.1007/s11263-015-0816-y. 9, 16_

Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear
[regions of deep neural networks. CoRR, abs/1711.02114, 2017. URL http://arxiv.org/](http://arxiv.org/abs/1711.02114)
[abs/1711.02114. 3](http://arxiv.org/abs/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.pone.0212356. URL https://doi.org/10.1371/journal.](https://doi.org/10.1371/journal.pone.0212356)
[pone.0212356. 1](https://doi.org/10.1371/journal.pone.0212356)

Anton Sinitsin, Vsevolod Plokhotnyuk, Dmitriy Pyrkin, Sergei Popov, and Artem Babenko. Editable
neural networks. arXiv preprint arXiv:2004.00345, 2020. 1

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, 3, 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˘as˘areanu. Nn
repair: Constraint-based repair of neural network classifiers. In International Conference on
_Computer Aided Verification, pp. 3–25. Springer, 2021. 2_


-----

7 APPENDIX

7.1 REPAIR VIA LINEAR PROGRAMMING

We consider the caseand −∞≤ _ql[i] ≤_ _qu Φ[iout] ≤ can be expressed as+∞_ (ql[i] and qu[i {] are they _|_ _ql ≤ iPy-th elements of ≤_ _qu} where q Pl and is a q full row ranku respectively). matrix_

Consider the following optimization problem.

minT maxx _T_ (f (x) _f_ (x)
_∈A |_ _−_ _|_ (10)
_ql_ _P_ (T (f (x))) _qu,_ _x_
 _≤_ _≤_ _∀_ _∈A_

where T : R[n] _→_ R[n] is a linear transformation on the DNN’s output space R[n].

**Theorem 6. On linear region** _, we have f_ (x) = f1x + f2 for some matrix f1 and vector f2.
_A_ _|A_
_Assuming that f1 is full rank[3], the optimization problem in (3) and the optimization problem in (10)_
_are equivalent._

Note thatlinear transformation via LPs and combine them into a single linear transformation to solve opti- ql ≤ _P_ (T (f (x))) ≤ _qu can be achieved row by row. Thus, we can find a one-dimensional_
mization problem 10.

For every row of P, say the i-th row, we can check the lower bound and upper bound of
_{P_ (f (x)) | ∀x ∈A} on the i-th dimension by solving the following LP problems

_lb[i] = min_ _ub[i] = max_ (11)
_x_ _[P]_ [[][i][](][f] [(][x][))] _x_ _[P]_ [[][i][](][f] [(][x][))]
_∈A_ _∈A_

where P [i] is the i-th row of P .

Then for each row i, we take a minimal linear transformation V [i](x) = v1[i](x) + v2[i] to transfer
interval [lb[i], ub[i]] inside interval [ql[i], qu[i]]. We can take v1[i] = 1 if qu[i] _ql[i] > ub[i]_ _lb[i],_
_−_ _−_
else v1[i] = _[q]ub[u][[][[i]i[]]][−][q]lb[l][[[]i[i]][]]_ [. And][ v][2][[][i][] =][ q][l][[][i][]][ −] _[v][1][[][i][]][lb][[][i][]][ if][ |][q][l][[][i][]][ −]_ _[v][1][[][i][]][lb][[][i][]][| ≤|][v][1][[][i][]][ub][[][i][]][ −]_ _[q][u][[][i][]][|][, else]_

_−_
_v1[i]ub[i]_ _qu[i]._
_−_

Since matrix P is full row rank, we can find a linear transformation T that is equivalent to V :

_T = P[ˆ][−][1]V_ _P[ˆ] ⇒_ _P_ (T (f (x))) = V (P (f (x))) (12)

_P_
where _P[ˆ] =_ _P_ _[⊥]_ is an orthogonal extension of P (P and P _[⊥]_ are orthogonal to each other and
 

_Pˆ is a full rank square matrix)._


Once we have T, we can obtain an affine patch function p (x) = T (f (x)) _f_ (x).
_A_ _−_

7.2 THE REASSURE ALGORITHM

**Algorithm 1 REASSURE**
**Input: A specification Φ = (Φin, Φout), a ReLU DNN f and a set of buggy points {x1, . . .,** _xL} ⊂_
Φin.
**Output: A repaired ReLU DNN** _f_ . e e

1: for l = 1 to L do
2: Generate the patch area _l from buggy point[b]_ _xl according to Equation (1);_
_A_

3: Generate a support network g according to Equation (2);
_A_

4: Solve the linear programming problem (6) to find the optimal affine patch network p .

e _A_

5: end for
6: Combine all support networks gAl and the corresponding patch networks pAl to get the overall
patch network h according to Equation (8).

7: return _f = f + h_

3Note that for neural networks that are trained by a stochastic method, with probability one[b] **_f1 is full rank._**


-----

7.3 PROOFS OF THEOREMS

We prove Theorem 1 after Corollary 1, since the proof of Theorem 1 uses the result of Corollary 1.
**Theorem 6. On linear region** _, we have f_ (x) = f1x + f2 for some matrix f1 and vector f2.
_A_ _|A_
_Assuming that f1 is full rank[4], the optimization problem in (3) and the optimization problem in (10)_
_are equivalent._

_Proof. On one side, for any c, d, since f1 is full rank, there exists a linear transformation T_, such
that T (f (x)) = T (f1x + f2) = (f1 + c)x + (f2 + d) = f (x) + cx + d.

On the other side, for any T, since T (f (x)) − _f_ (x) is linear, there exist c, d, such that cx + d =
_T_ (f (x)) − _f_ (x).

**Lemma 2. The repaired DNN** _f returned by REASSURE is guaranteed to satisfy the specification_
Φ on patch area A in single-region repair case.

[b]

_Proof. By the definition of p_, we have f (x) + p (x) Φout for all x .
_A_ _A_ _∈_ _∈A_

For any x, we have g (x, γ) = 1 and h (x, γ) = σ(p (x)) _σ(_ _p_ (x)) = p (x). There_∈A_ _A_ _A_ _A_ _−_ _−_ _A_ _A_
fore,

Thus, the patched neural networkfb(x) = f (x) +f meets the specification hA(x, γ) = f (x) + p ΦA( onx) A ∈.Φout (13)

**Theorem 2 (Completeness). REASSURE can always find a solution to the minimal point-wise repair**
_or the minimal area repair problem.[b]_

_Proof. For every patch area_, we can always find a support network g . For any Φout and,
_A_ _A_ _A_
there exists an affine function p such that p (x) Φout, _x_ . Therefore, the LP (6) is always
_A_ _A_ _∈_ _∀_ _∈A_
feasible and REASSURE can find an affine patch function p .
_A_

Once we have g and p for patch area, REASSURE returns a patch network either by Equation
_A_ _A_ _A_
(7) or by Equation (8).

**Theorem 3 (Limited Side Effect). Given a correctness property Φ = (Φin, Φout), a patch region**
_A and the corresponding patch network h(x, γ), there exists a positive number Γ such that for any_
_γ ≥_ Γ, we have

_1. for any linear region B, if B ∩A = ∅, then_ _f_ (x, γ) = f (x);

_2. for any linear region_ _who is a neighbor of_ _(_ = _), if f_ = Φ, then _f_ (x, γ) = Φ.
_C_ _A[b]_ _C∩A ̸_ _∅_ _|C |_ _C_ _|_

_Proof. Since a multi-region repair is a composition of multiple singe-region repairs according to[b]_
Equation (8), we can prove the limited side effect of a multi-region repair by proving the limited
side effect of its constituent singe-region repairs. Below, we prove the limited side effect of a singeregion repair.

Consider patch area = _x_ _aix_ _bi, i_ _I_ and _>0(γ) =_ _x_ _h(x, γ) > 0_ .
_A_ _{_ _|_ _≤_ _∈_ _}_ _A_ _{_ _|_ _}_

1. Since the number of neighbors for A are finite, we can take a big enough γ, such that for any B,
if =, _>0(γ) =_ . Thus, we have _f_ (x, γ) = f (x) on .
_B ∩A_ _∅_ _B ∩A_ _∅_ _B_

2. For any linear region C who is a neighbor of[b] A, i.e. C ̸= A and C ∩A ̸= ∅, _f is no longer a_
linear function on C, since there are some hyperplanes introduced by our repair that will divide C
into multiple linear regions.

[b]

Specifically, those hyperplanes are {x | γ(aix − _bi) + 1 = 0} for i ∈_ _I, {x |_ _i∈I_ _[g][(][a][i][x][ −]_ _[b][i][, γ][)][ −]_

_I_ + 1 = 0, _x_ _p(x) + K_ _g_ (x, γ) _K = 0_ and _x_ _p(x) + K_ _g_ (x, γ) _K = 0_ .
_|_ _|_ _}_ _{_ _|_ _·_ _A_ _−_ _}_ _{_ _| −_ _·_ _A_ _−_ _}_

For any point x in those hyperplanes, it will fall into one of the following four cases.[P]

4Note that for neural networks that are trained by a stochastic method, with probability one f1 is full rank.


-----

(a) x ∈{x | γ(aix − _bi) + 1 = 0} for some i ∈_ _I, then gA(x, γ) = 0, h(x, γ) = 0 and_
_f_ (x) Φout;
_∈_

(b)b x ∈{x | _i∈I_ _[g][(][a][i][x][ −]_ _[b][i][, γ][)][ −|][I][|][ + 1 = 0][}][, then][ g][A][(][x, γ][) = 0][,][ h][(][x, γ][) = 0][ and]_
_f_ (x) Φout;
_∈_

[P]

(c) x _x_ _p(x) + K_ _g_ (x, γ) _K = 0_, then p(x) = K _K_ _g_ (x, γ) 0,

b _∈{_ _|_ _·_ _A_ _−_ _}_ _−_ _·_ _A_ _≥_

_−p(x) + K · gA(x, γ) −_ _K ≤_ 0, h(x, γ) = 0 and _f_ (x) ∈ Φout;

(d) x _x_ _p(x) + K_ _g_ (x, γ) _K_, then p(x) = K _g_ (x, γ) _K_ 0, p(x) + K
_∈{_ _| −_ _·_ _A_ _−_ _}_ [b] _·_ _A_ _−_ _≤_ _·_

By the above analysis, we havegA(x, γ) − _K ≤_ 0, h(x, γf (x) = 0) ∈ Φ andout for the boundary of the new linear regions. Sincef[b](x) ∈ Φout; _f is_
linear on the new linear regions and Φout is convex, _f_ (x) ∈ Φout for any x ∈C.

[b] [b]

**Remark: By Theorem 3, we have that a patch would not change a correct linear region to an[b]**
incorrect one.

**Corollary 1 (Incremental Repair). For multiple-region repair, the patch for a new region A[′]** _would_
_not cause a previous patched region A to become incorrect._

_Proof. After applying the patch to linear region A, we have that the resulting network is 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 A incorrect.

**Theorem 1 (Soundness). The repaired DNN** _f returned by REASSURE is guaranteed to satisfy the_
_specification Φ._

[b]

_Proof. The proof has two parts:_

1. to show that _f satisfies the specification Φ on A, and_

2. to show that _f satisfies the specification Φ outside of_ .

Part 1: [b][b] _A_


Lemma (2) shows _f satisfy the specification Φ for single-region repair on A._

For the multi-region case, consider a set of buggy linear regions 1 _l_ _I_ _l with the corresponding_
support neural network[b] _gAl and affine patch function pAl for each ∪_ _A≤_ _l≤. For the multi-region repairA_
construction in Equation (8), we refer to σ(pAj − _pAj−1 +maxk≥j{gAk_ _}Kj −_ _Kj) as the j-th patch_
and _fj = f +_ _j[′]≤j_ _[σ][(][p][A]j[′][ −]_ _[p][A]j[′]_ _−1_ [+ max][k][≥][j][′] _[{][g][A]k_ _[}][K][j][ −]_ _[K][j][)][ as the network after the][ j][-th]_

patch.

For any[b] _x in patch area[P]_ 1 _l_ _I_ _l, we can find a j such that x_ _j but x /_ _k for all k >_
_∪_ _≤_ _≤_ _A_ _∈A_ _∈A_
maxj. After the firstk≥2{gAk (x, γ j) patches}K2 − _K σ2()p, ...,A1_ (x σ) + max(pAj (x)k −≥1p{AgAj−k1((x, γx) + max)}K1 −k≥Kj{1g)A, σk ((x, γpA2)(}xK) −j −pAK1j()x, the) +
DNN’s output at x becomes _fj(x) = f_ (x) + pAj (x) which meets our specification Φ at x by the
definition of pAj (x).

Since x /∈Ak for all k > j, then by Corollary[b] 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 ∪1≤l≤I _Al._

Part 2: [b]

To show that _f[b] satisfies Φ outside of A._


-----

For any x outside the patch area ∪1≤l≤I _Al, we have x lies on a correct linear region (linear region_
that satisfies the specification Φ). By Theorem 3, we have either _f_ (x) = f (x) or _f_ (x) Φout.
_∈_
Therefore, _f satisfies Φ outside of A._

[b] [b]

**Theorem 4[b] (Minimum Repair). For any ReLU DNN** _f[˜], which is linear on a patch region A and_
_satisfies the specification Φ, there exists a positive number Γ, such that for all γ ≥_ Γ,

max _f_ (x) _f_ (x) max (14)
_x_ _X_ _−_ _| ≥_ _x_ _X_
_∈_ _[|][ ˜]_ _∈_ _[|][h][A][(][x, γ][)][|][.]_

_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 Φ, we have_
maxx∈A |f[˜] − _f_ _| ≥_ maxx∈A |cx + d| = maxx∈A |hA(., γ)| on patch area A by Equation (3).

Therefore, we only need to show:

max (15)
_x/∈A_ _[|][h][A][(][., γ][)][| ≤]_ [max]x∈A _[|][h][A][(][., γ][)][|]_

Since parameter γ controls the slope of h (., γ) outside of patch area, a large γ means that
_A_ _A_
_h_ (., γ) will drop to zero quickly outside of . Therefore, we can choose a large enough Γ such
_A_ _A_
that h (., γ) drops to zero faster than the change of linear patch function cx + d.
_A_

Therefore, we have that for any γ ≥ Γ,

max
_x/∈A_ _[|][h][A][(][., γ][)][| ≤]_ [max]x∈A _[|][h][A][(][., γ][)][|][ = max]x∈X_ _[|][h][A][(][., γ][)][|]_

max _f_ _f_ max _f_ _f_ (16)
_≤_ _x_ _A_ _−_ _| ≤_ _x_ _X_ _−_ _|_
_∈_ _[|][ ˜]_ _∈_ _[|][ ˜]_

**Theorem 5 (Polynomial-Time Efficiency). REASSURE terminates in polynomial-time in the size of**
_Pythe neural network and the number of buggy linear regions whenqu_ _, where P is a full row rank matrix and_ _ql[i]_ Φquout[i] takes the form of+ _(ql[i] and { qyu |[i q] arel ≤_
_≤_ _}_ _−∞≤_ _≤_ _≤_ _∞_
_the i-th elements of ql and qu respectively)._

_Proof. We consider the affine patch function solved via Equation (10). Suppose_ = _x_ _X_ _aix_
_A_ _{_ _∈_ _|_ _≤_
_bi, i_ _I_ . For the LPs in Equation (11), _I_ 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.

In addition, since REASSURE computes the support network g and affine patch function p for
_A_ _A_
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 on Feature-Space Repairs:**

For an R-layer DNN f, we split f into two submodels f1 and f2 according to a hidden layer, say
the jth hidden layer, where f1 is the first j layers function, f2 is the last R − _j layers function and_
_ff =1(x f) the buggy feature.2 ◦_ _f1. We note the output space of f1 the feature space. And for any buggy input_ _x, we note_

Repairing in a feature space is to repair the behavior ofNote this will automatically repair the behavior ofe _f on buggy points f2 on buggy featuresx1, . . ., {fx1L(x1.), . . ., f e_ 1(xL)}.
_{_ _}_

Repairing in a feature space has the benefit of making the repair process more computation-friendlye e
and reducing the parameter overhead of the additional networks, and has the potential to generalizee e
the repair to undetected buggy inputs with similar features. However, it loses the locality guarantee
in the input space (but still preserves locality in the feature space).


-----

REASSURE MDNN

#P ND(L∞) ND(L2) NDP(L∞) NDP(L2) Acc ND(L∞) ND(L2) NDP(L∞) NDP(L2) Acc

1 **0.0%** **0.0%** **9.0%** **9.1%** **96.8%** 8.9% 8.9% 7.1% 6.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 5: Watermark Removal. The test accuracy of the original DNN is 96.8%. #P: number of buggy
points to repair; ND(L∞), ND(L2): average (L∞, L2) norm difference on both training data and
testing data; NDP(L∞), NDP(L2): average (L∞, L2) norm difference on random sampled points
near watermark images; Acc: accuracy on test data.

**Point-wise Repair on 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 a 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 to 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 in a feature space).

The results are shown in Table 4. REASSURE, PRDNN and Fine-Tuning repair all the buggy points
while Retrain only repair 96% buggy points in 100 epochs. REASSURE achieves almost zero modification 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 of randomly chosen images xi with label f (xi).

The goal is to change the DNN’s predictions on all watermarks xi to any other label y ̸= f (xi) while
preserving the DNN’s performance on the MNIST test data. For REASSURE, we set the prediction
_y = f_ (xi) 1 if f (xi) > 1, and y = 10 otherwise.
_−_

The results are shown in Table 5. Both REASSURE and MDNN remove all the watermarks. However, MDNN introduces significant distortion to the target DNN and as a result the test accuracy
drops rapidly as the number of repair points increases. In comparison, REASSURE removes all the
watermarks with no harm to test accuracy.

**Area Repair: HCAS**

Table 6 is the comparison with PRDNN using the last layer as the repair layer. All other settings are
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 on MNIST: The DNN model is a multilayer perceptron with ReLU activation
functions. It 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 a final output layer with 10 nodes.


-----

REASSURE PRDNN (Last Layer)

#A ND(L ) NDP(L ) NSE Acc T ND(L ) NDP(L ) 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
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 to repair;
ND(L ): average L norm difference on training data ; NDP(L ): average L norm difference
_∞_ _∞_ _∞_ _∞_
on random sampled data on input constraints of Specification 1; NSE: % of correct linear regions that
is repaired to incorrect; Acc: 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 3 nodes, 5 hidden layers with 25
nodes in each hidden layer, and a final output layer with 5 nodes. DNN outputs one of five possible
control advisories (’wrong left’, ’weak left’, ’Clear-of-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.

**Hyperparameters used in Repair:**

We set γ = 0.5 for Point-wise Repair on MNIST, γ = 0.02 for Watermark Removal, γ = 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 experiment.

PRDNN requires specifying a layer for weight modification. We use the first hidden layer as the
repair layer, which has the best performance in our 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: Φin = {(x, y, ψ)|10 ≤_ _x ≤_ 5000, 10 ≤ _y ≤_ 5000, −π ≤ _ψ ≤−1/2π}. Output_
_constraint: f_ (x, y, ψ)4 ≥ _f_ (x, y, ψ)i for i = 0, 1, 2, 3.

We calculate all the linear regions for N1,4 in the area Φin 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: Φin = {(x, y, ψ)|10 ≤_ _x ≤_ 5000, −5000 ≤ _y ≤−10, 1/2π ≤_ _ψ ≤_ _π}. Output_
_constraint: f_ (x, y, ψ)0 ≥ _f_ (x, y, ψ)i for i = 1, 2, 3, 4.

Also we calculate all the linear regions in the area Φin of Specification 2. And 79 correct linear
regions are found. We will test if a 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
our 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 |I|, which is the number of linear


-----

constraints for the H-representation of A. We can remove redundant constraints in this representation 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 a 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 R[m] _→_ R function is representable by a ReLU DNN if and only if it is
a continuous piecewise linear (CPWL) function Arora et al. (2016). We use convolutional neural
networks as an example to show how REASSURE can be applied to more general CPWL networks.
Convolutional neural networks (CNNs) are 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 can be viewed as special linear
layers. The maxpooling layers can be converted to linear operations with ReLU activation functions
as follows.

max(x1, x2, ..., xn) = max(x1, max(x2, x3, ..., xn))
max(xi, xj) = max(xi − _xj, 0) + xj = σ(xi −_ _xj) + xj_

where σ is the ReLU activation function. Thus, REASSURE can be used to repair CNNs as well.


-----

