A method and intermediate device for dynamically modifying a stateful inspection of data. In one embodiment, the present invention is comprised of an intermediate device such as, for example, a router. The intermediate device is adapted to perform a stateful inspection of data passing therethrough. In one approach, the intermediate device performs the stateful inspection by inspecting the data to determine state information for the data. Next, the intermediate device modifies a state graph used to perform the stateful inspection of the data based upon the state information found during the aforementioned inspection. The intermediate device then utilizes the modified state graph to perform continued stateful inspection of the data. In so doing, the present invention enables an enhanced use of Quality of Service (QoS) classification based upon the high level application of the data. The present invention further provides a classification engine which can readily be adapted to new protocols.