A method of revalidating a connection tracking table of a flow-based managed forwarding element (MFE) that stores a set of firewall rules associated with each of a set of network connections and a connection table that stores a firewall rule identification and a set of state values associated with each of said network connections. The method receives a change in one or more firewall rules stored at the MFE. The method receives a packet that requires stateful firewall rule check on a particular connection after the change in the firewall rules. When the rule identification retrieved from the connection table is not the same as the new firewall rule associated with the particular connection, the method updates the firewall rule identification and the set of state values associated the particular connection using the new firewall rule identification associated with the particular connection.