What Is The Number of Active S-boxes over 5 Rounds of Fides AE cipher? It is mention in the paper "
Fides: Lightweight Authenticated Cipher with Side-Channel Resistance for Constrained Hardware" , the number of active S-boxes of Fides cipher is 22 over 5 rounds but my result shows it is 25((9-3-1-3-9))using the same concept used in midori (same almost MDS matrix) to construct MILP model.

Q. Is anyone else got same results as mine? if not , is there any steps should i take to find the correct answer other than exhaustive search?
Your result is accurate: 25 active S-boxes is the best you can do in a 5-round trail. Here's an example for the 5-bit S-box variant, respecting the S-box constraints (and assuming I read the specification correctly):
$$
\begin{bmatrix}
\mathtt{19} &amp; \mathtt{00} &amp; \mathtt{1c} &amp; \mathtt{1b} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\ 
\mathtt{00} &amp; \mathtt{1c} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{1e} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\ 
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{0c} &amp; \mathtt{00} &amp; \mathtt{1b} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\ 
\mathtt{00} &amp; \mathtt{1b} &amp; \mathtt{04} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\ 
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{11} &amp; \mathtt{00} &amp; \mathtt{04} &amp; \mathtt{10} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{11} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{10} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{11} &amp; \mathtt{00} &amp; \mathtt{04} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{04} &amp; \mathtt{10} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{11} &amp; \mathtt{00} &amp; \mathtt{04} &amp; \mathtt{10} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{11} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{10} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{11} &amp; \mathtt{00} &amp; \mathtt{04} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{04} &amp; \mathtt{10} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{04} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{10} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{11} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{0f} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{0f} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{0f} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{0f} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{0f} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{0f} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{00} &amp; \mathtt{0f} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{00} &amp; \mathtt{11} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{00} &amp; \mathtt{11} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{11} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{11} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{11} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{02} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{08} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{04} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{02} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{08} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{04} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{02} &amp; \mathtt{00} &amp; \mathtt{04} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{08} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{04} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{08} \\
\mathtt{02} &amp; \mathtt{00} &amp; \mathtt{04} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{02} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{08} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{06} &amp; \mathtt{00} &amp; \mathtt{0b} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{1d} \\
\mathtt{00} &amp; \mathtt{00} &amp; \mathtt{0c} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{1b} \\
\mathtt{01} &amp; \mathtt{00} &amp; \mathtt{02} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\mathtt{03} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{03} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{06} &amp; \mathtt{00} &amp; \mathtt{0b} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{1d} \\
\mathtt{00} &amp; \mathtt{0c} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{1b} &amp; \mathtt{00} \\
\mathtt{02} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{01} &amp; \mathtt{00} \\
\mathtt{03} &amp; \mathtt{03} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{01} &amp; \mathtt{0f} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{1a} &amp; \mathtt{00} \\
\mathtt{07} &amp; \mathtt{03} &amp; \mathtt{0b} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{01} &amp; \mathtt{1d} \\
\mathtt{05} &amp; \mathtt{0f} &amp; \mathtt{0b} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{1b} &amp; \mathtt{1d} \\
\mathtt{04} &amp; \mathtt{0c} &amp; \mathtt{0b} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{00} &amp; \mathtt{1a} &amp; \mathtt{1d} \\
\end{bmatrix}
$$

So where does the 22 come from? Well, modeling the S-box and the linear layer exactly can be costly. Instead, we can represent each nibble by a single bit and use the branch number $4$ of the almost-MDS layer to obtain a lower bound of active S-boxes. That is, for each column of the state in MixColumns, we have
$$
\begin{align*}
\sum (x_i + y_i) &amp;\ge 4d \\
d &amp;\ge x_i \\
d &amp;\ge y_i \,,
\end{align*}
$$
for dummy variable $d$, input and output variables $x_i$ and $y_i$.
Because this is an almost-MDS matrix, we also need to additionally ensure that the output is nonzero if the input is (as described here):
$$
\begin{align*}
4\sum y_i - \sum x_i &amp;\ge 0 \\
4\sum x_i - \sum y_i &amp;\ge 0 \,.
\end{align*}
$$

However, when one does this, it results in the looser bound of $\ge 18$ active S-boxes over 5 rounds, not 22! So it remains a mystery where the 22 came from. The same observations also apply to 6 rounds, and possibly above.