Presented herein are probabilistic flow management techniques in which flow objects are probabilistically evaluated in view of the current contents of a flow table to determine if the flow object should be added to the flow table. An untrusted packet flow may be received at a feature or function of a networking device. The feature initiates addition of an untrusted flow object corresponding to the untrusted packet flow into a flow table. A probabilistic flow management mechanism determines if the number of untrusted flow objects in the flow table is below a predetermined lower limit. If the number of untrusted flow objects exceeds the lower limit and prior to addition of the untrusted flow object into the flow table, the probabilistic flow management mechanism probabilistically determines if the untrusted flow object may be added to the flow table.