## Abstract

The present disclosure describes systems and methods to enable inspecting of byte streams using a bipartite match algorithm to detect use of evasive techniques to defeat Uniform Resource (URL) filtering. According to an aspect of the present disclosure, a two stage dynamic programming algorithm is provided that matches signatures once and only once just like DFA in the first stage, and uses polynomial runtime to select a matching pattern in the second stage. According to an example implementation of the present disclosure, the patterns are compiled into an *n*m* binary matrix plus one additional column to describe the modifiers, where *n* is the number of patterns and *m* is the number of unique signatures used in the patterns. In the first stage of runtime, an *n*m* binary matrix is built where *n* is the number of tokens matched against the DFA and *m* is the number of signatures such that *e*(*i*,*j*)=true if and only if the *i*th token matches the *j*th signature. In the second stage of runtime, the sub runtime *n*m* matrix is obtained for a particular pattern such that *e*(*i*,*j*)=true if and only if the *i*th token matches the *j*th signatures in the pattern. A bipartite graph can be built where there are two sets of vertex, *n* and *m*, where *n* is token and *m* is signature. There is a weight 1 edge between an *i*th vertex in *n* and an *n*th vertex in *m* if *e*(*i*,*j*) in the matrix is true.

## Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 License.

## Recommended Citation

Lin, Mu; d'Abreu Noronha, Sanjay; Yan, Kan; Cai, Zhifeng; and Hayes, Kevin, "Detecting Evasive Malicious URL Using Graph Algorithm", Technical Disclosure Commons, (May 25, 2018)

https://www.tdcommons.org/dpubs_series/1208