A Taint Analysis Optimization for SQL Injection with a Union Applying a Rank and Path Compression Disjointed Set Forest


  • Aditya Kurniawan, Agung Trisetyarso, Agung Trisetyarso, Agung Trisetyarso


Injection vulnerability is the most commonly exploited flaw in web technology. A
taint analysis can be used to detect the source code pattern of injection
vulnerability. Hence, a taint analysis searches for tainted sources, from the bottom
of the source code to the root of the tainted source. A taint analysis also has an
?{n} complexity, which means that if the number of nodes increases, all higher
level of paths will be affected. Consequently, this paper proposes an optimized
method which reduces the number of paths from the tainted variable node to the
tainted source node by applying the union by rank and path compression methods.
This method has been tested on ansql injection vulnerability pattern test case to
prove the slicing correctness. The combination of the union by rank and path
compression methods obtained O(m?(n)) complexity, where ?(n) is a extremely
slow growing function.