A packet is compared to a pattern defined by a regular expression with back-references (backref-regex) in a single pass of a non-deterministic finite automaton corresponding to the backref-regex (backref-NFA) that includes representations for all backref-regex's back-references. The packet's characters are sequentially selected and analyzed against the backref-NFA until a match or no-match between the packet and pattern is determined. Upon selecting a character, a corresponding configurations-set is updated, where the set includes configurations associated with respective NFA-states of the backref-NFA and indicating whether the selected character is being matched against a back-reference. With the configurations-set being updated the comparison process proceeds along backref-NFA's NFA-states. The updated configurations-set includes configurations associated with NFA-states reachable from the configurations in the pre-updated set. When the configurations-set includes a final state, a match is determined. When the configurations-set becomes empty, or upon selection of all characters lacks the final state, a no-match is determined.