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} & \mathtt{00} & \mathtt{1c} & \mathtt{1b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{1c} & \mathtt{00} & \mathtt{00} & \mathtt{1e} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{0c} & \mathtt{00} & \mathtt{1b} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{1b} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} $$ $$ \xrightarrow{SB} \begin{bmatrix} \mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{SR} \begin{bmatrix} \mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{MC} \begin{bmatrix} \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} $$ $$ \xrightarrow{SB} \begin{bmatrix} \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{SR} \begin{bmatrix} \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{MC} \begin{bmatrix} \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} $$ $$ \xrightarrow{SB} \begin{bmatrix} \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{SR} \begin{bmatrix} \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{MC} \begin{bmatrix} \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} $$ $$ \xrightarrow{SB} \begin{bmatrix} \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{08} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{SR} \begin{bmatrix} \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\ \mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{MC} \begin{bmatrix} \mathtt{02} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\ \mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\ \mathtt{02} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\ \end{bmatrix} $$ $$ \xrightarrow{SB} \begin{bmatrix} \mathtt{06} & \mathtt{00} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1d} \\ \mathtt{00} & \mathtt{00} & \mathtt{0c} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1b} \\ \mathtt{01} & \mathtt{00} & \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \mathtt{03} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{03} \\ \end{bmatrix} \xrightarrow{SR} \begin{bmatrix} \mathtt{06} & \mathtt{00} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1d} \\ \mathtt{00} & \mathtt{0c} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1b} & \mathtt{00} \\ \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{01} & \mathtt{00} \\ \mathtt{03} & \mathtt{03} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\ \end{bmatrix} \xrightarrow{MC} \begin{bmatrix} \mathtt{01} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1a} & \mathtt{00} \\ \mathtt{07} & \mathtt{03} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{01} & \mathtt{1d} \\ \mathtt{05} & \mathtt{0f} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1b} & \mathtt{1d} \\ \mathtt{04} & \mathtt{0c} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1a} & \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) &\ge 4d \\ d &\ge x_i \\ d &\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 &\ge 0 \\ 4\sum x_i - \sum y_i &\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.
