Perception Point

The Gödel Proof
& The Malware Detection Spoof

Perception Point

Kurt Gödel changed the face of mathematics with the stroke of two sentences, by proving that a foreknown truth about the completeness of the natural numbers system was actually improvable. Computer science, which relies on the axioms of the natural numbers system, continues bearing the weaknesses exposed by Gödel’s refute, and modern software detection is one specific niche which suffers from this flaw.

Gödel was an Austrian mathematician, logician and philosopher of the 20th century who specialized in logic and its implications on the foundations of mathematics. He studied at the Vienna University and focused his inquiries on the fundamental concepts of the natural numbers system (i.e 0,1,2,3…), which is the base of algorithmic logic and computer science. This system has a set of axioms defining the borders of its logic, for example, that 0 is actually a natural number, and not a null representation.

A logical system has axioms of completeness and consistency: It is complete in the sense that its axioms enable the creation of all possible true statements comprised of the system’s objects, and is consistent in the sense that these axioms do not contradict each other. Gödel used these two axioms to form an unprovable claim, as is portrayed in the following demonstration:


S is a logical system, such as the natural numbers system.
C is a claim comprised of objects and rules from the system S.


Completeness: any claim (C) within the system (S) is provable by the axioms of the system.
Consistency: all claims within the logic of the system (S) do not contradict each other.

Gödel used these articles and principles to create the following paradoxical statement: CS cannot be proved within the system S.

Apparently – this is a provable claim, but practically it is unprovable; the claim follows the logic of the system S, but states a claim that if proven – will refute the rule of completeness (any claim should be provable), and if unproven – will refute the rule of consistency (no claims within the same system contradict each other). By this, Gödel demonstrated what the linguist and philosopher Wittgenstein, described as the inability of language to refer to itself because the reference itself uses language. Gödel showed mathematically that systems have a limited capability of self attribution, due to their dependence on a closed logical subbase.

Like Wittgenstein’s claim and its Gödelian mathematical manifestation, anti-virus and its resembling platforms are incapable of examining the entire system while being a part of it, because they too are subject to its logical rules.
Zero-day attacks take advantage of unprecedented vulnerabilities, and thus undermine the rules of the system that they are attacking. Cyber security platforms are unable to identify these hostile utilizations because they are incapable of seeing beyond the logic of the operating system.

Cyber security companies continue offering software level solutions and promise top notch detection, while factually they are subject to this logical knot, and are blindsided to malicious activity conducted outside their limited visibility scope. Enterprises continue putting their trust in these myopic solutions, believing that it’s the best they can do, and accept the recurrences of zero-day attacks and their containment as an arms race between attackers and defenders. However, it is difficult to overlook the fact that visibility limitation are an innate attribute of software based cyber security solutions.

Share the joy

More Articles

Analysis and exploitation of a Linux kernel vulnerability (CVE-2016-0728)

The Perception Point Research team has identified a 0-day local privilege escalation vulnerability in the Linux kernel.
Read More