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 ith token matches the jth 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 ith token matches the jth 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 ith vertex in n and an nth 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