Thread (26 posts)

Why ReLU is “special”

1. Piece-wise linearity
   For a ReLU neuron
   $g(u)=\max(0,u)=\begin{cases}0&u<0\\u&u\ge 0\end{cases}$

   the input space is split by a single hyper-plane
   $H:=\{x\mid w^{\top}x+b=0\}$.

   • On each side of H the neuron is perfectly linear.
   • Crossing H flips the Jacobian contribution of that neuron from 0 to $w^{\top}(\cdot)$.
   • Along any straight line $\mu(\lambda)=x_1+\lambda(x_2-x_1)$ the global network output $f^*(\lambda)=f(\mu(\lambda))$ is therefore piece-wise linear: its first derivative has a jump exactly when $\mu(\lambda)$ hits a hyper-plane belonging to one ReLU.

   Detecting that jump with two finite differences is what lets Canales-Martínez et al. (and Carlini-Jagielski-Mironov 2020) pinpoint a critical point and say: “between $\lambda_1$ and $\lambda_2$ one and only one ReLU flipped – recover its weight/sign now”.

2. Algebraic simplifications
   Once the layer is known to be linear on both sides of a critical point, solving for weights reduces to solving linear (or at worst bilinear) systems. That is why the whole attack ultimately becomes polynomial.

What if the activation is still piece-wise linear but not ‘hard’?

• Leaky-ReLU, PReLU, hard-tanh, hard-sigmoid, ReLU6, etc.
These all keep the same “kink” – the derivative is discontinuous (slope changes from $a$ to $b$).
The attack generalises almost verbatim: in place of “slope = 0 vs slope = 1” you test “slope = a vs slope = b”, which is even easier because both sides remain informative.

• ‘ReLU with noise’ (e.g. dropout, quantisation error).
As long as the measurement noise is bounded and you can average a few repeated queries, the jump in the first derivative is still categorical; the paper already uses 200 samples per neuron in the “neuron-wiggle” stage exactly for this purpose.

Truly smooth activations (sigmoid, tanh, GELU, Swish)

Here the derivative is continuous, so the clean “one-bit jump” disappears:

1. No unique boundary:
   A sigmoid neuron transitions gradually over an $O(\|w\|^{-1})$ wide slab instead of a zero-measure hyper-plane. Two neighbouring neurons’ transition regions easily overlap, so following a line $\mu(\lambda)$ you see a sum of many smooth bumps; separating them is a de-convolution problem, not a simple change-point detection.

2. Ambiguous scaling:
   For ReLU you can absorb any positive scalar into the next layer, but negative scalars are forbidden by the sign of the kink. With sigmoids the function $\sigma(\alpha u)$ for $\alpha>0$ is still monotone and can be re-absorbed by re-scaling the outgoing weights, so recovering the exact scale of $w$ (and its sign) from black-box queries alone becomes ill-posed.

3. Higher-order derivatives help only with a gradient oracle:
   If the attacker could query $\nabla f(x)$ exactly, one could in principle solve non-linear systems that involve $\sigma'(\cdot)$ in place of the ReLU mask. In the pure prediction-only model you would have to estimate those gradients with finite differences; the error grows as $O(\varepsilon^{-1})$ for first derivatives and $O(\varepsilon^{-2})$ for second, so the number of queries blows up quickly.

Known theoretical results mirror this: with sigmoids, even deciding consistency of a 2-layer 3-neuron network given labeled samples is NP-complete (Blum–Rivest 1993). Allowing chosen queries helps, but no polynomial-time black-box extraction algorithm is currently known.

Practical take-away

• Piece-wise-linear (kinky) activations ⇒ the Crypto ’20 / TII ’23 extraction works.

• Mild modification (leaky-ReLU, ReLU6, hard-sigmoid, etc.) ⇒ same attack with minor slope accounting.

• Smooth activations ⇒ sharp “critical-point” trick disappears; you would have to shift to optimisation-based model stealing (train a surrogate on many query/response pairs) or to side-channel / gradient-oracle attacks.

So the “sharpness” is not a small implementation detail—it is the linchpin that turns a messy non-linear identification problem into a clean linear-algebra one.

This is an excellent observation about the paper's methodology. You're right that the authors make essential use of ReLU's discontinuous derivative at the critical points where neurons switch from inactive to active states. The paper explicitly states they cannot generalize to smooth activation functions:

"We can generalize the attack to any other type of activation function that looks like a piecewise linear function (with possibly more than one sharp bend), such as a leaky ReLU, but not to smooth activation functions such as a sigmoid which have no critical points."

However, your insight about the statistical nature of their methods is intriguing. Even for ReLUs, they:

1. Use the "Neuron Wiggle" technique which samples ~200 critical points per neuron
2. Employ confidence levels (α) to handle uncertainty
3. Deal with finite precision arithmetic that introduces noise

For smooth activation functions like sigmoid or tanh, while we lose the sharp critical points, we might consider:

Potential approaches:

• Gradient-based methods: Since smooth functions have well-defined gradients everywhere, we could potentially use gradient information more directly
• Linearization regions: Even smooth activations have regions where they're approximately linear (e.g., sigmoid near x=0)
• Higher-order derivatives: The curvature information might reveal network parameters

Challenges:

• Without critical points, identifying individual neuron behaviors becomes much harder
• The piecewise linear structure that enables layer-by-layer "peeling" disappears
• The signal-to-noise ratio would likely be much worse

The statistical sampling approach might help, but you'd probably need a fundamentally different algorithm architecture rather than adapting their critical-point-based method. It's an interesting research direction though - perhaps combining ideas from this paper with other model extraction techniques designed for smooth activations.

Looking at this paper's style and cultural markers, several elements immediately identify it as cryptographic rather than machine learning work:

Language and Framing

The adversarial framing permeates everything - neural networks aren't "analyzed" or "understood," they're attacked. The authors speak of "cryptanalytic extraction," "oracle queries," and "black-box implementations." This combative vocabulary treats the neural network as an adversary to be defeated rather than a system to be studied.

The term "polynomial time" appears in the title itself - a dead giveaway. ML researchers care about wall-clock time; cryptographers care about asymptotic complexity classes.

Mathematical Culture

The paper exhibits the cryptographer's compulsion for complete formal specification. Definitions 1-10 lay out precise mathematical frameworks before any actual work begins. Compare this to ML papers that often jump straight to architecture descriptions and experimental setup.

The assumptions section (3.2) reads like a security model specification: "Full-domain inputs," "Complete outputs," "Fully precise computations." ML papers rarely enumerate their assumptions so explicitly - they're more likely to mention them informally as needed.

Perfectionism vs. Pragmatism

Cryptographers want to extract parameters with "arbitrarily high precision" and recover "all the real-valued parameters." ML researchers would be thrilled with 90% accuracy. This reflects crypto's binary security model (broken/not broken) versus ML's continuous performance metrics.

The careful discussion of edge cases ("unlucky events," "neurons whose values before the ReLU almost never change sign") shows crypto's obsession with completeness. An ML paper would likely ignore such corner cases as practically irrelevant.

Historical Positioning

The introduction reaches back to "cryptographers and mathematicians in the early nineties" - positioning this as a theoretical problem with deep roots. ML papers typically cite work from the last 5 years and position themselves within current benchmarks.

Complexity Focus

The exponential-to-polynomial improvement (from 2^256 to 30 minutes) is presented as the headline result. An ML paper would lead with accuracy metrics or benchmark performance. The detailed query complexity analysis (counting exact oracle calls) is quintessentially cryptographic.

Writing Style

The prose is dense, formal, and assumes mathematical sophistication. Sentences like "The space of control is the vector space containing all possible small changes at the input to layer i" would be simplified in an ML paper to something like "We can only change the input in certain directions."

The paper uses "we" in the mathematical sense ("we thus have to qualify our assertion") rather than the empirical sense ("we trained the network for 100 epochs") common in ML work.

Cultural Blind Spots

Tellingly, the actual machine learning aspects are almost afterthoughts. The CIFAR10 model description is relegated to a brief section, training details are minimal, and there's an apologetic note that "better test accuracies are achieved using more advanced neural network architectures." A cryptographer's interest in the neural network extends only as far as necessary to break it.

The paper treats neural networks as mathematical objects to be reverse-engineered rather than as tools for solving problems - a fundamentally different relationship to the technology than ML researchers have.

You're right that in real neural networks both the input and output are high-dimensional vectors. The key insight is that the method doesn't need to find corners in a high-dimensional output space. Instead, it analyzes each output coordinate separately as a scalar function.

When you interpolate between two input points $x_1$ and $x_2$ in the high-dimensional input space via $\mu(\lambda) = x_1 + \lambda(x_2 - x_1)$, each output coordinate $f_j(\mu(\lambda))$ becomes a scalar function of $\lambda \in [0,1]$. So if your network has 10 outputs, you get 10 separate piecewise linear functions, each of which can be analyzed for critical points.

The critical points (where ReLUs toggle) affect all output coordinates simultaneously. When a neuron in some hidden layer switches from active to inactive (or vice versa) as you move along the interpolation path, this creates a sharp corner in the piecewise linear function for each output coordinate. The slopes before and after this point will be different for each output, but the location $\lambda^*$ where the corner occurs is the same across all outputs.

The paper's algorithm finds these corners by:

1. Measuring slopes at different points along the interpolation
2. Finding where slopes change (indicating a corner)
3. Mapping back from $\lambda^*$ to the actual input point $x^* = \mu(\lambda^*)$

This approach works because ReLU networks are piecewise linear - the high-dimensional output function is linear within each region where all neurons maintain their active/inactive states, with sharp transitions only at the boundaries where neurons toggle.

The signature of a neuron is a clever representation that captures what's actually recoverable in a neural network extraction attack. Let me unpack the layers:

The Setup

Starting from a neuron's basic operation:

• A neuron in layer $i$ has weights $(a_1, a_2, ..., a_\ell)$ where $\ell = d_{i-1}$
• It computes: $\sigma(a_1 x_1 + a_2 x_2 + ... + a_\ell x_\ell + b)$

The Fundamental Problem

ReLU networks have an inherent symmetry: if you scale all weights of a neuron by a positive constant $c$:

• Neuron computes: $\sigma(c \cdot (a_1 x_1 + ... + a_\ell x_\ell + b))$
• Then scale all outgoing connections by $1/c$ in the next layer
• The overall network function remains identical

This means we can never recover the absolute scale of the weights through black-box queries.

Why the Signature?

The signature $(1, a_2/a_1, ..., a_\ell/a_1)$ represents what we can uniquely recover:

1. Scale-invariant representation: Dividing by $a_1$ normalizes the weight vector, removing the unknown scaling factor

2. Unique identifier: Different neurons (with different weight directions) will have different signatures, allowing us to:

   • Group critical points by which neuron they belong to
   • Track neurons across different observations

3. But preserves sign ambiguity: The signature alone doesn't tell us if we have $(a_1, a_2, ...)$ or $(-a_1, -a_2, ...)$. This is crucial because:

   • Positive scaling is a symmetry (doesn't change function)
   • Negative scaling is NOT a symmetry (ReLU blocks negative values)

The Attack Strategy

The paper's approach is:

1. Find critical points where neurons transition between active/inactive
2. Use these to recover signatures (relative weight ratios)
3. Separately determine signs to resolve the $(+)$ vs $(-)$ ambiguity
4. Combine to get actual weights (up to a positive scale that doesn't matter)

The signature definition is essentially encoding "what information about the weights can we extract from observing input-output behavior, given the symmetries of ReLU networks?"

Yes! Definition 6's linear neighborhood has deep connections to several concepts from convex optimization:

1. Polyhedral Regions and Linear Programming

The linear neighborhood is actually a polyhedron - specifically, the intersection of half-spaces defined by the activation constraints. For each neuron $\eta_j$ in layer $i$, we have:

• If active at $x$: $\langle A_j^{(i)}, F_{i-1}(u) \rangle + b_j^{(i)} \geq 0$
• If inactive at $x$: $\langle A_j^{(i)}, F_{i-1}(u) \rangle + b_j^{(i)} \leq 0$

This creates a system of linear inequalities defining a convex polytope, exactly like the feasible region in linear programming.

2. Piecewise Affine Functions

ReLU networks are piecewise affine functions, where each linear neighborhood corresponds to one "piece." This connects to:

• DC (Difference of Convex) programming: ReLU networks can be expressed as differences of convex functions
• Tropical geometry: The max operations in ReLUs relate to tropical algebra used in some optimization contexts

3. Subdifferential Calculus

At boundaries between linear neighborhoods, the network is non-differentiable. The subdifferential at these points is the convex hull of the gradients from adjacent linear regions. This is crucial for:

• Understanding critical points in the paper's attack
• Non-smooth optimization algorithms like subgradient methods

4. Normal Cones and Optimality Conditions

The normal cone at a point $x$ on the boundary of a linear neighborhood contains the directions that point "outward" from the region. This relates to:

• KKT conditions when neurons are at critical points ($\mathcal{V}(\eta; x) = 0$)
• Complementarity conditions in mathematical programming

5. Locally Linear Optimization

Within each linear neighborhood, any optimization problem involving the neural network becomes a convex problem (actually affine). This means:

• The attack can exploit local convexity
• Gradient information is constant throughout the region
• The "wiggle" directions in the attack stay within these convex regions

The paper's attack fundamentally exploits this piecewise linear structure - by finding critical points (boundaries between linear neighborhoods) and analyzing the network's behavior as it transitions between these convex polyhedral regions.

The neuron wiggle technique can identify inputs that maximally wiggle a target neuron because by this stage of the attack, the adversary already knows the signatures (relative weight ratios) of all neurons, even though they don't know the signs.

Here's how it works:

Key Prerequisites

Before using neuron wiggle, the attack has already:

1. Recovered the signatures of all neurons using critical points (the ratios like $(1, \frac{a_2}{a_1}, \ldots, \frac{a_\ell}{a_1})$)
2. Fully recovered all previous layers (which have been "peeled off")
3. Obtained $\hat{A}^{(i)}$ - the weight matrix for layer $i$ up to unknown signs

Creating the Wiggle

The crucial insight is that maximizing the size of a wiggle doesn't require knowing the sign. If you have weights $(a_1, a_2, \ldots, a_n)$ up to sign, you can create a wiggle $\delta$ parallel to these weights:

$\delta \parallel \hat{A}_j^{(i)} = (\pm |a_1|, \pm |a_2|, \ldots, \pm |a_n|)$

This wiggle maximizes $|\langle \hat{A}_j^{(i)}, \delta \rangle|$ regardless of whether the true weights are positive or negative, because:

• If the true weights are $(a_1, a_2, \ldots)$, the dot product gives $|a_1|^2 + |a_2|^2 + \ldots$
• If the true weights are $(-a_1, -a_2, \ldots)$, you still get the same magnitude

The Process

1. Project onto space of control: They project $\hat{A}_j^{(i)}$ onto $V^{(i-1)}$ (the subspace they can actually control at layer $i$)

2. Find input difference: They compute $\Delta \in \mathbb{R}^{d_0}$ by finding a pre-image of $\delta$ under $F^{(i-1)}$ (the fully recovered previous layers)

3. Test at critical point: At a critical point $x^*$ for the target neuron, they evaluate:

   • $L = f(x^* - \Delta) - f(x^*)$
   • $R = f(x^* + \Delta) - f(x^*)$

4. Determine sign: If $|L| > |R|$, the neuron has negative sign; if $|R| > |L|$, it has positive sign

The key is that they can create an input perturbation that maximally affects the target neuron using only the signature information, then use the asymmetric behavior around critical points to determine which sign is correct.