Sometimes the Most Definite Thing is a Maybe

Security testing automation is stranded by Gödel

Everyone who has dealt with developing a comprehensive automated security testing tool knows that it is a challenging task. Staying on top of new security bugs and making the tool performant is one thing and keeping false alarms (false positives) and missed bugs (false negatives) as low as possible is something else. But there’s a one more and inherent limitation to any automated software security testing solution; SAST or DAST…

Image for post
Image for post
Sometimes, the most definite answer we can get out of a security testing tool is just a MAYBE

The limitation which is always there

Automated application security tools whether they are dynamic or static suffer from Rice’s Theorem which goes like;

  • For a static analysis, the behaviour of the program should be predicted through the flow of the data from a taint source to a dangerous SQL API sink.
Image for post
Image for post
Gödel at the age of 25 provided a disproof for Hilbert’s Program.

Undecidability through Control Flow Graphs

One of the most important techniques to use in order to analyze a program statically is constructing Control Flow Graphs (CFG). Coupled with Data Flow Analysis, CFGs allow us to follow tainted data to dangerous API calls, which mean a security weakness.

void Greet(string name)
{
string msg = "Welcome"

if(name is not Empty)
msg.Append(", " + name)

myLabel.SetText(msg)
}
Image for post
Image for post
A simple CFG representation of the code block shown previously

A Basic disproof

Pursing reductio ad absurdum, let’s assume that it’s possible to write such a program which can answer reachability problem for any two nodes of any given CFG. Let’s call this R. Here’s the representation of R.

Image for post
Image for post
We assume there exists a program R solving the CFG reachability problem
Image for post
Image for post
A simple extension to R, called H

It’s all incomplete, we just approximate

Albeit along similar lines, it’s also not possible to write a tool that is both consistent and complete at the first place. Let’s hear what Gödel’s Theorems say about this;

Conclusion

From time to time, we all hear marketing mambo jambo concerning the quality of security automated testing tools such as producing “zero false-alarms” or revealing “every existing bug”.

CodeThreat is a static application security testing (SAST) solution. Visit codethreat.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store