The　prosperity　of　network　function　virtualization　(NFV)　pushes　forward　the　paradigm　of　migrating　in-house　middleboxes　to　third-party　providers,　i.e.,　software　(virtualized)　middlebox　services.　A　lot　of　enterprises　have　outsourced　traffic　processing　such　as　deep　packet　inspection(DPI),　traffic　classification,　and　load　balancing　to　middleboxes　provided　by　cloud　providers.　However,　if　the　traffic　is　forwarded　to　the　cloud　provider　without　careful　processing,　it　will　cause　privacy　leakage,　as　the　cloud　provider　has　all　the　rights　to　access　the　data.　To　solve　the　security　issue,　recent　efforts　are　made　to　design　secure　middleboxes　that　can　directly　conduct　network　functions　over　encrypted　traffic　and　middlebox　rules.　However,　security　concerns　from　dynamic　operations　like　dynamic　DPI　and　rule　updates　are　still　not　yet　fully　addressed.　In　this　paper,　we　propose　a　privacy-preserving　dynamic　DPI　scheme　with　forward　privacy　for　outsourced　middleboxes.　Our　design　can　enable　cloud　side　middlebox　to　conduct　secure　packet　inspection　over　encrypted　traffic　data.　Besides,　the　middlebox　providers　cannot　analyze　the　relationship　between　the　newly　added　rules　and　the　previous　data.　Several　recent　papers　have　proven　that　it　is　a　strong　property　that　resist　adaptive　attacks.　Furthermore,　we　design　a　general　method　to　inspect　stateful　packets　while　still　ensuring　the　state　privacy　protection.　We　formally　define　and　prove　the　security　of　our　design.　Finally,　we　implement　a　system　prototype　and　analyze　the　performance　from　experimental　aspects.　The　evaluation　results　demonstrate　our　scheme　is　effective　and　efficient.　©　2021